Prinsip Deadlock: Deadlock dapat didefinisikan sebagai blocking permanen pada beberapa proses yang saling berkompetisi maupun berkomunikasi untuk memperoleh suatu sumber daya
Sumber daya dapat dikategorikan secara umum menjadi:
-Reusable resource
-Consumable resource
Reusable Resource
Didefinisikan sebagai : Sumber daya yang dapat digunakan dengan aman oleh satu proses pada suatu saat.
Terdapat tiga kondisi memperlakukan sumber daya oleh proses yaitu : request – hold – release.
Contoh reusable resource :
- Processor
- I/O channel
- Main memory dan secondary memory
- Device
- File
- Database
- Semaphore
Contoh deadlock yang melibatkan reusable resource
Misal terdapat dua proses yang berkompetisi untuk mengakses disk file (D) dan tape drive (T)
P1 P2
repeat repeat
… …
Request (D); Request (T);
… …
Request (T); Request (D);
… …
Release (T); Release (D);
… …
Release (D); Release (T);
… …
forever forever
Deadlock terjadi jika masing-masing proses memegang (hold) sumber daya dan meminta (request) sumber daya yang lain yang dipegang oleh proses yang lain.
Constraint on design system Cara mengatasinya dengan memberi batasan pada disain sistem untuk perintah request
Consumable Resource
Didefinisikan : Sumber daya yang dapat dibuat atau dilenyapkan
Kondisi tidak terblock menghasilkan proses-proses yang siap melepaskan sumber daya.
Saat suatu sumber daya diperlukan oleh sebuah proses sumber daya tersebut akan muncul
Contoh consumable resource :
- interrupt
- sinyal
- message
- informasi dalam I/O buffer
Beberapa kondisi yang memungkinkan terjadinya deadlock
1. Mutual exclusion : Adanya sumber daya kritis sehingga hanya satu proses yang boleh menggunakan sebuah sumber daya kritis tersebut pada suatu saat
2. Hold and wait : suatu proses menahan (hold) sumber daya yang sebenarnya ditunggu-tunggu oleh proses lain
3. No preemption : Tidak ada sumber daya yang dapat dipaksa lepas dari suatu proses yang memegangnya
4. Circular wait : Rantai tertutup yang menyatakan suatu proses memegang/menahan sumber daya yang diperlukan oleh proses lain sehingga terjadi saling menunggu
Circular Wait
Metoda mengatasi Deadlock
Cara mengatasi deadlock :
Pencegahan deadlock (deadlock prevention)
Pendeteksian dan pemulihan deadlock (deadlock detection and recovery)
Penghindaran deadlock (deadlock avoidance)
Deadlock prevention
1. Meniadakan mutual exclusion
Deadlock disebabkan terdapatnya pengaksesan eksklusif sumber daya. Jika tidak ada sumber daya ekslusif ke satu proses tunggal, maka tidak pernah dijumpai deadlock
Cara yang ditempuh untuk mengganti pengaksesan eksklusif adalah dengan spooling sumber daya yaitu proses pengakesan sumber daya diantrikan di disk
2. Mencegah hold and wait
Proses me-request seluruh sumber daya sekaligus dan proses terblock sampai seluruh permintaan terpenuhi
Proses ini tidak efisien karena : - Proses menjadi lama karena menunggu semua sumber daya yang diminta terpenuhi yang sebenarnya dapat dikerjakan hanya dengan beberapa sumber daya - Sumber daya yang sudah dialokasikan pada proses ini mungkin saja tidak langsung digunakan tetapi karena sudah dialokasikan tidak dapat dipakai oleh proses lain
3. Mencegah no-preemption, dilakukan dengan alternatif:
Jika sebuah proses yang telah menggenggam (hold) sumber daya tidak diperbolehkan meminta (request) lagi sumber daya, proses harus melepaskan (release) sumber daya tersebut dulu jika diperlukan dapat juga meminta kembali sumber daya yang dilepaskan bersamaan dengan sumber daya tambahannya.
Jika proses meminta sumber daya yang sedang digenggam oleh proses lain, sistem operasi dapat menyela (preempt) proses yang menggenggam dengan meminta melepaskan sumber daya tersebut. Alternatif ini dapat dilakukan jika tidak ada dua proses yang memiliki prioritas yang sama. Contoh kasus ini adalah prosesor
4. Mencegah Circular wait
Dapat dilakukan dengan mendefinisikan urutan linier dari jenis sumber daya. Jika proses telah dialokasikan pada sumber daya berjenis R maka urutan permintaan berikutnya dari proses tersebut adalah hanya yang berjenis R.
Misal sumber daya Ri mendahului Rj dengan urutan i < j. Jika terdapat dua proses A dan B deadlock karena A telah memperoleh Ri dan meminta Rj dan B telah memperoleh Rj dan meminta Ri. Kondisi ini tidak akan terjadi karena pada kasus ini i < j dan juga j < I
Deadlock Detection and Recovery
Berbeda dengan Deadlock prevention, deadlock detection tidak membatasi akses sumber daya dan memberi larangan pada proses. Permintaan terhadap sumber daya akan diberikan jika memungkinkan
Pengecekan deadlock dilakukan setiap kali ada permintaan sumber daya. Pendeteksian deadlock ini menguntungkan karena algoritmanya mudah hanya didasari perubahan state dan tidak mengkonsumsi waktu prosesor yang banyak
Setelah dideteksi ada deadlock dilakukan beberapa strategi pemulihan berikut : - Keluarkan seluruh proses yang mengalami deadlock - Salin setiap proses yang deadlock ke titik pengecekan yang telah didefinisikan sebelumnya dan mulai kembali dari awal seluruh proses. Resikonya deadlock bisa terjadi lagi tapi karena proses kongkurensi tidak menentu hal ini tidak terjadi. - Sela (preempt) sumber daya sampai tidak ada deadlock
Deadlock Avoidance
Keputusan dibuat dinamik untuk mengetahui apakah suatu permintaan sumber daya jika dipenuhi dapat menyebabkan deadlock atau tidak.
Dua pendekatan penghindaran deadlock - Jangan memulai proses jika proses tersebut akan menghasilkan deadlock - Jangan penuhi permintaan penambahan sumber daya jika alokasi ini dapat menyebabkan proses jadi deadlock
Untuk mengetahui kondisi mendatang akan menyebabkan deadlock atau tidak digunakan langkah berikut
Process Initiation Denial
Misal terdapat n proses dan m jenis sumber daya. Didefinisikan dalam bentuk vektor dan matriks
Materi lengkap [PPT]Deadlock dan Starvation
Sumber : Selvia Lorena Br. Ginting, S.Si., MT, Unikom
Posting Komentar