Mutual Exclusion And DeadLock

1.      MUTUAL EXCLUSION

Mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya pada satu interval waktu tertentu. Sumber daya yang tidak dapat dipakai bersama pada saat bersamaan.

Sering terjadi pada peralatan pencetakan (printer). Daemon printer adalah proses yang melakukan penjadwalan dan pengendalian pencetakan berkas-berkas di printer. Ruang disk ini disebut direktori spooler. Direktori spooler membagi disk menjadi sejumlah slot. Slot-slot diisi berkas yang akan dicetak. Terdapat variabel in yang menunjuk slot bebas pada ruang disk yang akan dipakai untuk menyimpan berkas yang ingin dijadwalkan untuk dicetak. Bagian program yang sedang mengakses memory atau sumber daya yang dipakai bersama disebut critical section. Jika proses pada critical section memblokir proses-proses lain dalam antrian, maka akan terjadi startvation dan deadlock.

Kesuksesan proses-proses konkurensi memerlukan pendefinisian critical section dan memaksakan mutual exclusion di antara proses-proses konkuren yang sedang berjalan. Pemaksaan mutual exclusion merupakan landasan pemrosesan konkuren. Fasilitas atau kemampuan menyediakan dukungan mutual exclusion harus memenuhi kriteria sbb:

o   Mutual exclusion harus dijamin, bahwa tidak ada proses lain, kecuali dirinya sendiri. Di sini terjadi proses tunggal.

o   Proses yang berada di noncritical section, dilarang mem-blocked proses-proses lain yang ingin masuk critical section. Hal ini bisa terjadi startvation.

o   Harus dijamin bhwa proses yang ingin masuk critical section tidak menunggu selama waktu yang tak terhingga. Ini bisa mengakibatkan masalah deadlock dan antrian proses bertambah panjang.

o   Ketika tidak ada proses pada critical section, maka proses yang ingin masuk critical section harus ijinkan masuk tanpa waktu tunda.

o   Tidak ada asumsi mengenai kecepatan relatif proses atau jumlah yang ada.

o   Proses hanya tinggal pada critical section selama satu waktu yang berhingga

Beberapa metode yang diusulkan untuk menjamin Mutual Exclusion, antara lain:

-       Metode Variable Lock

Locking adalah salah satu mekanisasi pengontrol konkuren. Konsep dasar : pada saat suatu transaksi memerlukan jaminan kalau record yang diinginkan tidak akan berubah secara mendadak, maka diperlukan kunci untuk record tersebut. Fungsi kunci (lock) adalah menjaga record tersebut agar tidak dimodifikasi transaksi lain.

Cara kerja dari kunci :

1.      Pertama kita asumsikan terdapat 2 macam kunci :

-       Kunci X : kunci yang eksklusif.

-       Kunci S : kunci yang digunakan bersama-sama.

2.      Jika transaksi A menggunakan kunci X pada record R, maka permintaan dari transaksi B untuk suatu kunci pada R ditunda, dan B harus menungggu sampai A melepaskan kunci tersebut.

3.      Jika transaksi A menggunakan kunci S pada record R, maka :\

a.       Bila transaksi B ingin menggunakan kunci X, maka B harus menunggu sampai A melepaskan kunci tersebut.

b.      Bila transaksi B ingin menggunakan kunci S, maka B dapat menggunakan kunci S bersama A.

Tabel Kunci

4.      Bila suatu transaksi hanya melakukan pembacaan saja, secara otomatis ia memerlukan kunci S 􀃆 baca (S).

Bila transaksi tersebut ingin memodifikasi record maka secara otomatis ia memerlukan kunci X 􀃆 memodifikasi (X).

Bila transaksi tersebut sudah menggunakan kunci S, setelah itu ia akan memodifikasi record, maka kunci S akan dinaikan ke level kunci X.

5.      Kunci X dan kunci S akan dilepaskan pada saat synchpoint (synchronization point). Synchpoint menyatakan akhir dari suatu transaksi dimana basis data berada pada state yang konsisten. Bila synchpoint ditetapkan maka :

-       Semua modifikasi program menjalankan operasi commit atau rollback.

-       Semua kunci dari record dilepaskan.

Metode ini sederhana ketika proses masuk critical section lebih dahulu
memeriksa variable lock.

-       Jika variable lock bernilai 0, proses men-set variable locknya menjadi 1 kemudian masuk ke dalam critical section.

-       Jika variable lock bernilai 1, maka proses menunggu sampai nilai variable lock nya menjadi 0.

Metode ini tidak menjamin proses tidak masuk critical section yang telah dimasuki proses lain.

-       Metode bergantian secara ketat

Metode ini mengasumsikan dapat mengalir masuk critical section secara bergantian terus-menerus. Metode ini melakukan refleksi terhadap variabel yang berfungsi untuk memenuhi critical section.

2.      DEADLOCK

Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya oleh pemroses. Pada umumnya deadlock terjadi karena proses mengalami startvation, yaitu suatu job yang sedang dieksekusi dan eksekusi job tersebut tidak ada hentinya, tidak diketahui kapan berhentinya proses tersebut atau bahkan job yang antri bisa dikatakan mempunyai status mati, padahal proses-proses lain sedang menunggu sumber daya proses.

Deadlock merupakan kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar.

a.       Resource

Sistem operasi di sini berperan sebagai pengatur berbagai tipe resource yang
berlainan,  krena  pada  dasarnya  proses-proses  maupun  job-job  tersebut  ingin
mengakses resource yang sama.

Shareable resource misalnya printer, tape drive.

b.      Karakteristik Deadlock

Kondisi yang dapat menimbulkan terjadinya deadlock:

1.      Mutual exclusion. Apabila proses telah menggunakan suatu resource, mka tidak boleh ada proses lain yang menggunakan resource tsb. Hanya satu proses yang dapat menggunakan sebuah resource pada satu waktu.

2.      Hold & Wait. Pada suatu proses sedang mengakses suatu resource, proses tsb dapat meminta ijin untuk mengakses resource lain yang dipakai oleh proses lain.

3.      No Preemption. Jika suatu proses meminta ijin untuk mengakses resource, sementara resource tersebut tidak tersedia, maka permintaan ijin tidak dapat dibatalkan.

4.      Circular Wait Condition. Jika proses P0 sedang mengakses Resource R1 dan minta ijin untuk mengakses resource R1 dan minta ijin untuk mengakses resource R2, dan pada saat yang bersamaan P1 sedang mengakses resource R2 dan mint ijin untuk mengakses R1.

Metode Mengendalikan Deadlock

1.      Menggunakan suatu protokol untuk meyakinkan bahwa sistem tidak akan pernah mengalami deadlock.

2.      Mengijinkan sistem mengalami deadlock, namun kemudian harus segera dapat memperbaikinya.

3.      Mengabaikan semua masalah dan menganggap deadlock tidak akan pernah terjadi lagi di dalam sistem.

Strategi untuk menghadapi deadlock dapat dibagi menjadi tiga pendekatan, yaitu:

a.       Mengabaikan adanya  deadlock.

b.      Memastikan bahwa  deadlock tidak akan pernah  ada, baik  dengan metode Pencegahan, dengan mencegah empat kondisi  deadlock agar tidak akan  pernah terjadi. Metode Menghindari  deadlock, yaitu mengizinkan  empat kondisi deadlock,  tetapi  menghentikan setiap proses yang kemungkinan mencapai  deadlock.

c.       Membiarkan deadlock  untuk terjadi, pendekatan ini membutuhkan dua metode yang  saling mendukung, yaitu:

-       Pendeteksian deadlock, untuk mengidentifikasi ketika deadlock terjadi.

-       Pemulihan deadlock, mengembalikan kembali sumber daya yang dibutuhkan pada proses yang memintanya.

Pencegahan Deadlock

1.      Mutual exclusion.

Harus tetap menjaga resource-resource yang bersifat non-shareable. Yaitu, proses menahan sebuah resource, proses lain yang meminta resource tsb harus menunggu sampai proses melepaskannya. Jika terjadi pada perangkat I/O dan berkas, maka sulit untuk menghindari mutual exclusion pada sumber daya non shareable.

2.      Hold & Wait.

Apabila suatu proses minta ijin untuk mengakses suatu resource, maka proses tersebut tidak boleh membawa resource yang lainnya. Sebleum proses meminta resource, maka harus melepas semua resource yang dibawa.

3.      Non Preemption.

Jika suatu proses minta ijin mengakses resource, sementara resource tersebut tidak dapat dipenuhi secepatnya, maka proses tersebut harus membebaskan semua resourcenya terlebih dahulu.

4.      Circular Wait.

Memberi nomor pada setiap resource yang ada, dan setiap resource hanya boleh mengakses resource2 secara berurutan.

5.      Untuk menghindari deadlock ikuti prinsip preemptive.

Penghindaran Deadlock

1.      State Selamat

Contoh            :

Pada sistem dengan 10 sumber daya setipe, proses A memerlukan sumber daya maksimum sebanyak 10, sedang saat ini menggenggam 2. Proses B memerlukan sumber daya maksimum sebanyak 3, sedang saat ini menggenggam 1. Proses C memerlukan sumber daya maksimum sebanyak 7, sedang saat ini menggenggam 3. Maka, masih tersedia 4 sumber daya.

2.      State Tak Selamat (unsafe state)

State dikatakan sebagai state tak selamat jika tidak terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.

Mendeteksi Deadlock dan Memulihkan Deadlock

Metode ini mengunakan pendekatan dengan teknik untuk menentukan apakah deadlock sedang terjadi serta proses-proses dan sumber daya yang terlibat dalam deadlock tersebut. Setelah kondisi deadlock dapat dideteksi, maka langkah pemulihan dari kondisi deadlock dapat segera dilakukan. Langkah pemulihan tersebut adalah dengan memperoleh sumber daya yang diperlukan oleh proses-proses yang membutuhkannya. Beberapa cara digunakan untuk mendapatkan sumber daya yang diperlukan, yaitu dengan terminasi proses dan pre-emption (mundur) suatu proses. Metode ini banyak digunakan pada komputer mainframe berukuran besar.

a.       Terminasi Proses

Metode ini akan menghapus proses-proses yang terlibat pada kondisi deadlock dengan mengacu pada beberapa syarat. Beberapa syarat yang termasuk dalam metode ini adalah, sebagai berikut:

-     Menghapus semua proses yang terlibat dalam kondisi deadlock (solusi ini terlalu mahal).

-     Menghapus satu persatu proses yang terlibat, sampai kondisi deadlock dapat diatasi (memakan banyak waktu).

-     Menghapus proses berdasarkan prioritas, waktu eksekusi, waktu untuk selesai, dan kedalaman dari rollback.

b.      Resources Preemption

Metode ini lebih menekankan kepada bagaimana menghambat suatu proses dan sumber daya, agar tidak terjebak pada unsafe condition. Beberapa langkahnya, yaitu:

-       Pilih salah satu - proses dan sumber daya yang akan di-preempt.

-       Rollback ke safe state yang sebelumnya telah terjadi.

SUMBER :

iwansantosa.files.wordpress.com/2009/04/makalah-konkurensi-2.doc

disusun oleh : nama: Dimas kusuma ajinim 

                       nim   : 12.5.00029