Implementasi Algoritma Mutual Exclusion Menggunakan Metode Instruksi Test and Set Lock Pada Sistem Operasi .
Metode dengan instruksi test and set lock
Pada system multiprocessor, pemroses-pemroses bertindak independent. Interupsi di satu pemroses tidak mempengaruhi pemroses- pemroses lain. Pemroses- pemroses yang memakai memori bersama maka pengaksesan terhadap suatu memori dijaga pada tingkat perangkat keras agar pemroses lain tidak boleh meakses suatu lokasi yang sama disaat yang sama.
Perancang perangkat keras menyediakan instruksi-instruksi atomic yang tidak dapat di interupsi, instruksi dilaksanakan sampai selesai. Instruksi ini biasanya dilaksanakan dengan cara mengunci bus sehingga pemroses- pemroses lain tidak dapat menggunakan bus. Pemroses yang mengunci bus dengan leluasa membaca dan/atau memodifikasi suatu lokasi memori.
Instruksi-instruksi dirancang untuk menyelesaikan mutual exclusion di system multiprocessor. Beragam instruksi disediakan perancang pemroses guna membantu implementasi mutual exclusion. Di antara instruksi-instruksi itu adalah
- tsl (test and set lock)
- tas atau ts (test and set), digunakan IBM S/360, keluarga Motorola M68000, dan lain-lain
- cs (compare and set), digunakan IBM 370 series
- xchg (exchange), digunakan intel x86
- dan sebagainya.
Instruksi tsl (test and set lock)
Instruksi ini membaca isi memori ke register dan kemudian menyimpan nilai bukan nol ke alamat memori itu. Operasi membaca isi memori dan menyimpan ke memori atomic dijamin tidak dapat diinterupsi. Tidak ada pemroses lain yang dapat mengakses memori itu sampai instruksi berakhir. Pemroses yang mengkesekusi instruksi tsl mengunci bus memori, mencegah pemroses- pemroses lain mengakses memori.
Dengan instruksi tsl, kita dapat menggunakan flag untuk koordinasi pengaksesan ke memori bersama. Ketika flag bernilai 0, proses boleh menge-set-nya menjadi 1 menggunakan instruksitsl dan kemudian masuk critical section. Ketika telah selesai dengan critical region, proses menge-set flag dengan 0.
Dengan adanya instruksi ini maka dapat dibuat prosedur
- prosedur tsl_to_critical_section
- prosedur tsl_leave_critical_section
prosedur-prosedur itu adalah sebagai berikut:
Maka program untuk mutual exclusion dengan instruksi tsl adalah sebagai berikut:
Sebelum masuk critical section, proses memanggil tsl_to_critical_section yang melakukan busy waiting sampai flag terbebas. Setelah selesai dengan critical section, proses memanggiltsl_leave_section yang menyimpan 0 ke flag agar proses lain dapat memasuki critical section itu.
Metode dengan instruksi Exchange (XCHG)
Instruksi Exchange (xchg)
Instruksi xchg disediakan mesin. Intel menyediakan instruksi ini. Instruksi ini menukarkan dua isi memori. Dalam pascal instruksi itu dapat di tulis sebagai berikut:
Operasi pembacaan dan penukaran itu di pandang sebagai atomik, tidak dapat disela. Instruksi dapat digunakan untuk implementasi mutual exclusion. Dengan instruksi xchg tersebut dapat dibuat
- prosedur Xchg_to_critical_section
- prosedur Xchg_leave_critical_section
prosedur- prosedur itu sebagai berikut:
maka program mutual exclusion dengan xchg adalah sebagai berikut:
Sebelum mengeksekusi seluruh proses maka flag diinisialisasi dengan nilai 0. Proses sebelum masuk critical_section, proses menge-set dengan kunci (key) proses itu sebagai 1 kemudian memanggil xchg_to_enter_section. Proses melakukan busy waiting sampai terbebas. Selesai dengan critical section, proses memanggil xchg_leave_critical_section menukarkan nilai 0 ke flag agar proses lain dapat memasuki critical section itu.
Karakteristik Pendekatan dengan Instruksi Mesin
Penggunaan instruksi mesin untuk memaksakan mutual exclusion mempunyai keunggulan dan kelemahan.
Keunggulan
- sederhana dan mudah di verifikasi.
- Dapat diterapkan ke sembarang jumlah proses baik di pemroses tunggal maupun banyak pemroses yang memakai memori bersama.
- Dapat digunakan untuk mendukung banyak critical region, masing-masing critical region didefinisikan dengan suatu variable.
Kelemahan Serius
- Merupakan metode dengan Busy waiting, sangat tidak efisien. Selagi proses menunggu memasuki critical region, proses berlanjut mengkonsumsi waktu pemroses.
- Adanya busy waiting memungkinkan deadlock dan startvation.
Dampak Adanya Busy Waiting
Metode metode dengan busy waiting mempunyai keterbatasan yaitu tidak dapat diterapkan pada system dengan penjadwalan berprioritas. Pada system – system dengan penjadwalan berprioritas, metode dengan busy waiting dapat menimbulkan deadlock.
Aturan penjadwalan berprioritas selalu menjadwalkan proses – proses berprioritas lebih tinggi di antrian proses Ready.
Misalnya terdapat dua proses,
1. Proses H berprioritas tinggi
2. Proses L berprioritas rendah
Maka penjadwalan berprioritas akan selalu menjadwalkan H bila proses H Ready.
Perhatikan scenario berikut:
- Saat L masuk critical section.
- H menjadi Ready (yaitu operasi masukan/keluaran proses H selesai dilayani).
- H segera dijadwalkan dan ingin masuk critical section.
- Karena ingin masuk critical region yang telah dimasuki L maka H dalam busy waiting menunggu L keluar dari critical section.
- Tapi karena L tidak pernah di jadwalkan saat proses H Ready yang lebih tinggi prioritasnya daripada L maka L tidak pernah berkesempatan keluar dari critical section.
- H loop selamanya dan L tidak pernah dijadwalkan. H dan L saling menunggu. H menunggu L keluar dari critical section, L menunggu H selesai agar dapat dijadwalkan dan keluar dari critical section.
- H dan L tidak pernah membuat kemajuan apapun setelah itu terjadilah deadlock yakni H dan L tidak membuat kemajuan apapun.
6,004 comments so far