Mutual exclusion
Dalam ilmu
komputer , saling pengecualian
mengacu pada kebutuhan untuk menjamin bahwa tidak ada dua proses atau benang (selanjutnya disebut hanya sebagai proses) masih berada pada bagian
kritis pada waktu yang sama. Di sini, bagian kritis mengacu pada periode waktu ketika
proses mengakses sumber daya bersama, seperti memori
bersama . Masalah mutual exclusion pertama kali diidentifikasi dan
dipecahkan oleh Edsger
W. Dijkstra dalam seminal 1965 makalahnya
berjudul: Solusi dari masalah dalam kontrol pemrograman konkuren.
Contoh sederhana mengapa saling
pengecualian penting dalam praktek dapat divisualisasikan menggunakan linked list tunggal lihat gambar di bawah ini
Dalam sebuah linked list penghapusan node dilakukan dengan mengubah "berikutnya" pointer dari node sebelumnya untuk menunjuk ke simpul berikutnya (misalnya, jika node i sedang dihapus maka "berikutnya" pointer node i-1 akan diubah untuk menunjuk ke node i +1). Dalam eksekusi mana seperti linked list sedang dibagi antara beberapa proses, dua proses mungkin mencoba untuk menghapus dua node yang berbeda secara bersamaan mengakibatkan masalah berikut: biarkan node i dan i +1 menjadi node yang akan dihapus, lebih jauh lagi, janganlah dari mereka menjadi kepala atau ekor, pointer berikutnya simpul i-1 akan berubah untuk menunjuk ke node i +1 dan pointer berikutnya node i akan berubah untuk menunjuk ke node i +2. Meskipun kedua operasi penghapusan lengkap berhasil, node i +1 tetap ada dalam daftar sejak i-1 dibuat untuk menunjuk ke i +1 skipping node i (yang dibuat untuk menunjuk ke i +2). Hal ini dapat dilihat pada Gambar 1. Masalah ini dapat dihindari dengan menggunakan pengecualian bersama untuk memastikan bahwa update simultan ke bagian yang sama dari daftar tidak dapat terjadi.
Solusi perangkat keras
Pada uniprocessor
sistem, solusi yang paling sederhana untuk mencapai saling pengecualian adalah
untuk menonaktifkan interupsi
selama proses 'bagian kritis. Ini akan
mencegah rutinitas layanan interupsi dari berjalan (efektif mencegah proses dari yang mendahului
).
Solusi perangkat lunak
Selain solusi
perangkat keras yang didukung, beberapa solusi perangkat lunak yang ada yang
menggunakan sibuk menunggu
untuk mencapai saling pengecualian.
Contoh ini
meliputi:
- Algoritma Dekker
- Algoritma Peterson
- Lamport bakery algoritma
- Algoritma Szymanski
- Algoritma roti hitam-putih Taubenfeld itu.
Hal ini sering lebih baik untuk menggunakan fasilitas sinkronisasi yang disediakan oleh multithreading perpustakaan sistem operasi, yang akan mengambil keuntungan dari solusi perangkat keras jika memungkinkan, tetapi akan menggunakan solusi perangkat lunak jika tidak ada solusi perangkat keras yang ada. Misalnya, ketika sistem operasi kunci perpustakaan digunakan dan benang mencoba untuk memperoleh kunci sudah diperoleh, sistem operasi dapat menangguhkan benang menggunakan saklar konteks dan swap keluar dengan benang lain yang siap untuk dijalankan, atau bisa menempatkan prosesor ke dalam keadaan daya rendah jika tidak ada thread lain yang dapat dijalankan.
DEADLOCK
Deadlock . Deadlock adalah suatu kondisi dimana dua proses atau
lebih saling menunggu proses yang lain untuk melepaskan resource
yang sedang dipakai. Karena beberapa proses itu saling menunggu, maka tidak
terjadi kemajuan dalam kerja proses-proses tersebut.
Deadlock adalah
masalah yang biasa terjadi ketika banyak proses yang membagi sebuah resource
yang hanya boleh dirubah oleh satu proses saja dalam satu waktu. Di kehidupan
nyata, deadlock
dapat digambarkan dalam gambar berikut.
deadlock dianalogikan
sebagai dua antrian mobil yang akan menyeberangi jembatan. Dalam kasus diatas,
antrian di sebelah kiri menunggu antrian kanan untuk mengosongkan jembatan (resource),
begitu juga dengan antrian kanan. Akhirnya tidak terjadi kemajuan dalam kerja
dua antrian tersebut.Misal ada proses A mempunyai resource X, proses B
mempunyai resource
Y. Kemudian kedua proses ini dijalankan bersama, proses A memerlukan resource
Y dan proses B memerlukan resource X, tetapi kedua proses tidak akan memberikan resource
yang dimiliki sebelum proses dirinya sendiri selesai dilakukan. Sehingga akan
terjadi tunggu-menunggu.
Menghindari Deadlock
Pendekatan metode ini adalah dengan hanya memberi kesempatan ke permintaan sumber daya yang tidak mungkin akan menyebabkan deadlock. Metode ini memeriksa dampak pemberian akses pada suatu proses, jika pemberian akses tidak mungkin menuju kepada deadlock, maka sumber daya akan diberikan pada proses yang meminta. Jika tidak aman, proses yang meminta akan di-suspend sampai suatu waktu permintaannya aman untuk diberikan. Kondisi ini terjadi ketika setelah sumber daya yang sebelumnya dipegang oleh proses lain telah dilepaskan.Kondisi Aman (Safe state)
Suatu keadaan dapat dinyatakan sebagai safe state jika tidak terjadi deadlock dan terdapat cara untuk memenuhi semua permintaan sumber daya yang ditunda tanpa menghasilkan deadlock. Dengan cara mengikuti urutan tertentu.Kondisi Tak Aman (Unsafe state)
Suatu state dinyatakan sebagai state tak selamat (unsafe state) jika tidak terdapat cara untuk memenuhi semua permintaaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.Starvation
Starvation
adalah kondisi yang biasanya terjadi setelah deadlock. Proses yang
kekurangan resource (karena terjadi deadlock) tidak akan pernah
mendapat resource yang dibutuhkan sehingga mengalami starvation
(kelaparan). Namun, starvation juga bisa terjadi tanpa deadlock.
Hal ini ketika terdapat kesalahan dalam sistem sehingga terjadi ketimpangan
dalam pembagian resouce. Satu proses selalu mendapat resource,
sedangkan proses yang lain tidak pernah mendapatkannya. Ilustrasi starvation
tanpa deadlock di dunia nyata dapat dilihat di bawah ini.
2.
Starvation . Starvation adalah kondisi yang biasanya terjadi setelah deadlock.
Proses yang kekurangan resource (karena terjadi deadlock) tidak
akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation
(kelaparan). Namun, starvation juga bisa terjadi tanpa deadlock.
- Hal ini ketika terdapat kesalahan dalam sistem sehingga terjadi ketimpangan dalam pembagian resouce. Satu proses selalu mendapat resource, sedangkan proses yang lain tidak pernah mendapatkannya. Ilustrasi starvation tanpa deadlock di dunia nyata dapat dilihat di bawah ini.Pada gambar diatas, pada antrian kanan terjadi starvation karena resource (jembatan) selalu dipakai oleh antrian kiri, dan antrian kanan tidak mendapatkan giliran.
Pada gambar diatas, pada antrian kanan terjadi starvation
karena resource (jembatan) selalu dipakai oleh antrian kiri, dan antrian
kanan tidak mendapatkan giliran.
0 komentar:
Posting Komentar