A. Penjelasan tema Mutual Exclusion
Pada system computer terdapat sumber daya yang tidak dapat dipakai bersama pada saat yang bersamaan seperti pada penggunaan printer, Sumber daya seperti hanya dapat menjalankan satu proses pada suatu saat, sumber daya ini disebut sumber daya kritis. Program yang menggunakan sumber daya kritis disebut sedang memasuki critical region / section .
Sistem operasi memberikan fasilitas untuk pemrogram dapat memberikan indikasi keberadaan critical region. Sistem operasi menyediakan layanan ( berupa system call ) untuk mencagah suatu proses masuk kedalam critical region akan tetapi di dalam critical region terdapat proses lain yang sedang berjalan. Mutual exclusion merupakan solusi bagi masalah pada critical region / section, mutual exclusion adalah persoalan untu menjamin hanya satu proses saja yang berjalan dalam suatu critical region / section.
B. Metode-metode Penjamin Mutual Exclusion
1. Metode Naif
Sebenarnya metode ini tidak menyelesaikan mutual exclusion, karena masih terdapat scenario proses yang membuat situasi kacau. Metode ini sering disebut metode variable lock sederhana.
Ketika proses hendak masuk critical section, proses lebih dulu memeriksa variable lock dengan ketentuan :
- Jika variable lock bernilai 0, proses mengeset variable lock menjadi 1 dan segera masuk critical section.
- Jika variable lock bernilai 1, proses menunggu sampai nilai variabel lock menjadi 0.
2. Metode untuk situasi tertentu
Metode ini sering disebut metode bergantian secara ketat yang mengasumsikan proses-proses yang hendak masuk critical section secara bergantian terus menerus. Proses memeriksa terus menerus sehingga kondisi siap untuk diproses. Kondisi ini tidak dapat ditentukan lamanya waktu sehingga menyia-nyiakan waktu pemroses. Suatu saat kondisi akan crash ketika ada proses yang harus segera masuk sementara ada proses lain yang masih berjalan.
3. Metode Busy Waiting
a) Metode Penyelesaian Dekker
Algoritma Dekker mempunyai property-property berikut :
• Tidak memerlukan instruksi-instruksi perangkat keras khusus.
• Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain memasuki critical section.
• Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan.
b) Metode Penyelesaian Peterson
Sebelum masuk critical section, proses memanggil enter_critical_section, namun sebelumnya proses memeriksa sampai kondisi aman. Terjadi busy waiting, setelah selesai proses menandai pekerjaan dan mengijinkan proses lain masuk.
Keadaan awal tidak ada proses di critical section. Proses 0 akan masuk critical section. Proses menandai elemen arraynya dan mengeset turn ke 0. Proses memeriksa kondisi, dan prosedur enter_critical_section dilaksanakan. Jika kemudian, proses 1 akan masuk, proses akan menunggu sampai interest(0) menjadi FALSE. Kondisi ini hanya terjadi jika proses 0 mengeset elemen itu dan keluar dari critical section.
c) Metode Pematian Interupsi
Proses mematikan interupsi ke pemroses dan segera masuk ke critical section. Proses kembali mengaktifkan interupsi segera setelah meninggalkan critical section. Metode ini mengakibatkan :
• Pemroses tidak dapat beralih ke proses lain karena interupsi clock dimatikan sehingga penjadual pun tidak dieksekusi. Karena penjadual tidak beroperasi maka tidak terjadi alih proses.
• Proses dapat memakai memori bersama tanpa takut terinvensi proses lain karena memang tidak ada proses lain yang dieksekusi saat itu.
• Kelemahan utama :
• Bila proses yang mematikan interupsi mengalami gangguan maka proses tidak akan pernah menghidupkan interupsi kembali. Kejadian ini mengakibatkan kematian seluruh system.
• Jika terdapat dua pemroses atau lebih, mematikan interupsi hanya berpengaruh pada pemroses yang sedang mengeksekusi intruksi itu. Proses lain masih dapat memasuki critical section.
d) Metode Test and Set Lock (TSL)
Metode ini membaca isi memori ke register dan kemudian menyimpan nilai bukan 0 ke alamat memori. Pemroses yang mengeksekusi instruksi tsl mengunci bus memori, mencegah pemroses lain mengkases memori.
e) Metode Exchange (XCHG)
Metode ini menggunakan instruksi exchange (xchg). Instruksi xchg menukarkan dua isi memori.
f) Metode Instruksi Mesin
Keunggulan :
• Sederhana dan mudah diverifikasi
• Dapat diterapkan ke sembarang jumlah proses
• Dapat digunakan untuk mendukung banyak critical region
Kelemahan :
• Merupakan metode dengan busy waiting, sangat tidak efisien.
• Adanya busy waiting memungkinkan terjadi deadlock dan starvation.ü
4. Metode Penyelesaian Level Tinggi (Metode Semapore)
Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Proses berhenti sampai proses memperoleh penanda tertentu. Variabel khusus untuk penandaan ini disebut semaphore. Semaphore mempunyai dua property :
a) Semaphore dapat diinisialisasi dengan nilai bukan negative.
b) Ada dua operasi terhadap semaphore yaitu Operasi Up dan Operasi Down.
Operasi Down
Operasi ini menurunkan nilai semaphore. Jika nilai semaphore menjadi bukan positif maka proses yang mengeksekusinya diblok. Operasi Down adalah atomic (atomic action), tidak dapat diinterupsi sebelum selesai. Menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblok sebagai instruksi tunggal. Tidak ada proses lain yang dapat diakses sampai proses selesai.
Operasi Up
Operasi ini menaikkan nilai semaphore. Jika satu proses atau lebih telah diblok pada suatu semaphore tidak dapat menyelesaikan operasi down maka salah satu dipilih oleh system dan dibolehkan menyelesaikan operasi downnya. Operasi Up menaikan nilai semaphore, memindahkan dari antrian dan menempatkan satu proses ke senarai ready tidak dapat diinterupsi.
1. Metode Naif
Sebenarnya metode ini tidak menyelesaikan mutual exclusion, karena masih terdapat scenario proses yang membuat situasi kacau. Metode ini sering disebut metode variable lock sederhana.
Ketika proses hendak masuk critical section, proses lebih dulu memeriksa variable lock dengan ketentuan :
- Jika variable lock bernilai 0, proses mengeset variable lock menjadi 1 dan segera masuk critical section.
- Jika variable lock bernilai 1, proses menunggu sampai nilai variabel lock menjadi 0.
2. Metode untuk situasi tertentu
Metode ini sering disebut metode bergantian secara ketat yang mengasumsikan proses-proses yang hendak masuk critical section secara bergantian terus menerus. Proses memeriksa terus menerus sehingga kondisi siap untuk diproses. Kondisi ini tidak dapat ditentukan lamanya waktu sehingga menyia-nyiakan waktu pemroses. Suatu saat kondisi akan crash ketika ada proses yang harus segera masuk sementara ada proses lain yang masih berjalan.
3. Metode Busy Waiting
a) Metode Penyelesaian Dekker
Algoritma Dekker mempunyai property-property berikut :
• Tidak memerlukan instruksi-instruksi perangkat keras khusus.
• Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain memasuki critical section.
• Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan.
b) Metode Penyelesaian Peterson
Sebelum masuk critical section, proses memanggil enter_critical_section, namun sebelumnya proses memeriksa sampai kondisi aman. Terjadi busy waiting, setelah selesai proses menandai pekerjaan dan mengijinkan proses lain masuk.
Keadaan awal tidak ada proses di critical section. Proses 0 akan masuk critical section. Proses menandai elemen arraynya dan mengeset turn ke 0. Proses memeriksa kondisi, dan prosedur enter_critical_section dilaksanakan. Jika kemudian, proses 1 akan masuk, proses akan menunggu sampai interest(0) menjadi FALSE. Kondisi ini hanya terjadi jika proses 0 mengeset elemen itu dan keluar dari critical section.
c) Metode Pematian Interupsi
Proses mematikan interupsi ke pemroses dan segera masuk ke critical section. Proses kembali mengaktifkan interupsi segera setelah meninggalkan critical section. Metode ini mengakibatkan :
• Pemroses tidak dapat beralih ke proses lain karena interupsi clock dimatikan sehingga penjadual pun tidak dieksekusi. Karena penjadual tidak beroperasi maka tidak terjadi alih proses.
• Proses dapat memakai memori bersama tanpa takut terinvensi proses lain karena memang tidak ada proses lain yang dieksekusi saat itu.
• Kelemahan utama :
• Bila proses yang mematikan interupsi mengalami gangguan maka proses tidak akan pernah menghidupkan interupsi kembali. Kejadian ini mengakibatkan kematian seluruh system.
• Jika terdapat dua pemroses atau lebih, mematikan interupsi hanya berpengaruh pada pemroses yang sedang mengeksekusi intruksi itu. Proses lain masih dapat memasuki critical section.
d) Metode Test and Set Lock (TSL)
Metode ini membaca isi memori ke register dan kemudian menyimpan nilai bukan 0 ke alamat memori. Pemroses yang mengeksekusi instruksi tsl mengunci bus memori, mencegah pemroses lain mengkases memori.
e) Metode Exchange (XCHG)
Metode ini menggunakan instruksi exchange (xchg). Instruksi xchg menukarkan dua isi memori.
f) Metode Instruksi Mesin
Keunggulan :
• Sederhana dan mudah diverifikasi
• Dapat diterapkan ke sembarang jumlah proses
• Dapat digunakan untuk mendukung banyak critical region
Kelemahan :
• Merupakan metode dengan busy waiting, sangat tidak efisien.
• Adanya busy waiting memungkinkan terjadi deadlock dan starvation.ü
4. Metode Penyelesaian Level Tinggi (Metode Semapore)
Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Proses berhenti sampai proses memperoleh penanda tertentu. Variabel khusus untuk penandaan ini disebut semaphore. Semaphore mempunyai dua property :
a) Semaphore dapat diinisialisasi dengan nilai bukan negative.
b) Ada dua operasi terhadap semaphore yaitu Operasi Up dan Operasi Down.
Operasi Down
Operasi ini menurunkan nilai semaphore. Jika nilai semaphore menjadi bukan positif maka proses yang mengeksekusinya diblok. Operasi Down adalah atomic (atomic action), tidak dapat diinterupsi sebelum selesai. Menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblok sebagai instruksi tunggal. Tidak ada proses lain yang dapat diakses sampai proses selesai.
Operasi Up
Operasi ini menaikkan nilai semaphore. Jika satu proses atau lebih telah diblok pada suatu semaphore tidak dapat menyelesaikan operasi down maka salah satu dipilih oleh system dan dibolehkan menyelesaikan operasi downnya. Operasi Up menaikan nilai semaphore, memindahkan dari antrian dan menempatkan satu proses ke senarai ready tidak dapat diinterupsi.
Sebelum masuk critical section, proses melakukan down. Bila berhasil maka proses masuk critical section. Bila tidak berhasil maka proses diblok pada semaphore. Proses yang diblok dapat melanjutkan jika proses yang berada di critical section keluar dan melakukan operasi up dan menjadikan proses yang diblok menjadi ready dan berlanjut hingga operasi downnya berhasil.
C. Implementasi Semaphore
C. Implementasi Semaphore
- Pematian Interupsi : Sistem operasi mematikan interupsi selagi memeriksa semaphore, memperbarui, dan menjadikan proses diblok. Karena semua aksi hanya memerlukan beberapa instruksi, pematian interupsi tidak merugikan.
- Instruksi tsl : Pada banyak pemroses, tiap semaphore dilindungi variable lock dan instruksi tsl agar menjamin hanya satu pemroses yang saat itu memanipulasi semaphore
0 komentar:
Posting Komentar
Terima Kasih Komentarnya.....