Deadlock

*Session 13 & Session 14

A)   Deadlock

• Satu set proses menemui jalan buntu jika setiap proses dalam set menunggu untuk sebuah event.
• Pemblokiran permanen dari serangkaian proses yang baik bersaing untuk sumber daya sistem atau berkomunikasi satu sama lain.
• Tidak ada solusi yang efisien.
• Melibatkan kebutuhan yang bertentangan untuk sumber daya oleh dua atau lebih proses.

 

• Contoh Deadlock :

* Diagram progress joint menunjukkan kemajuan dua proses bersaing untuk dua sumber.
* Setiap proses membutuhkan penggunaan eksklusif dari kedua sumber.

 

• Contoh No Deadlock

 

 

B)   Kondisi Sumber Daya Deadlock

• Mutual Exclusion = hanya satu proses sekaligus yang dapat menggunakan sumber daya.
• Hold dan Wait = proses menahan setidaknya satu sumber daya yang menunggu untuk mendapatkan sumber daya tambahan yang ditahan oleh proses lainnya.
• No Preemption = sumber daya dapat dilepaskan hanya secara sukarela oleh proses yang menahannya, setelah proses telah menyelesaikan tugasnya.
• Circular Wait = ada satu set {P0, P1, …, P0} dari proses menunggu sehingga P0 menunggu sumber daya yang ditahan oleh P1, P1 menunggu sumber daya yang ditahan oleh P2, …, Pn-1 menunggu sumber daya yang ditahan oleh Pn, dan P0 menunggu sumber daya yang ditahan oleh P0.

C)   Deadlock Model

*Grafik alokasi sumber daya. (a) Memegang sumber daya. (b) Meminta sumber daya. (c) Deadlock.

 

*Jika permintaan datang dalam urutan atas dan CPU memproses A, B dan C dalam urutan -> tidak ada deadlock tetapi tidak ada paralelisme.

 

*Jika dilakukan seperti pada (d) -> Deadlock.

 

*Contoh bagaimana deadlock terjadi dan bagaimana hal itu dapat dihindari.

 

D)   Contoh Deadlock menggunakan RAG

 

 

E)   Contoh No Deadlock menggunakan RAG

 

F)   Strategi Menghadapi Deadlock

• Abaikan saja masalahnya. (Algoritma Ostrich)
• Deteksi dan pemulihan. Biarkan deadlock terjadi, deteksi mereka, ambil tindakan.
• Penghindaran dinamis oleh alokasi sumber daya.
• Pencegahan, secara struktural meniadakan salah satu dari empat kondisi yang diperlukan.

G)   Deteksi Deadlock

(a) Grafik sumber daya.    (b) Siklus diambil dari (a).

 

H)   Penghindaran Deadlock

Mensyaratkan bahwa sistem memiliki beberapa tambahan informasi priori yang tersedia.

• Model paling sederhana dan berguna mengharuskan setiap proses menyatakan jumlah maksimum sumber daya dari setiap jenis yang dibutuhkan.
• Algoritma deadlock-avoidance secara dinamis memeriksa state alokasi sumber daya untuk memastikan bahwa tidak akan pernah ada kondisi circular-wait.
• State sumber daya alokasi didefinisikan dengan jumlah sumber daya yang tersedia dan teralokasikan, dan tuntutan maksimum proses.

 

I)   Penghindaran Deadlock dengan RAG

• Klaim rusuk Pi -> Rj menunjukkan bahwa proses Pj dapat meminta sumber daya Rj; diwakili oleh garis putus-putus.
• Klaim rusuk mengkonversi untuk meminta rusuk ketika proses meminta sumber daya.
• Ketika sumber daya dilepaskan oleh proses, tugas rusuk mengkonversi ulang ke klaim rusuk.
• Sumber daya harus diklaim sebuah priori di dalam sistem.

 

J)   Safe and Unsafe State

*Demonstrasi bahwa state di dalam (a) aman.

 

Demonstrasi bahwa state di dalam b tidak aman.

 

K)   Algoritma Banker untuk sumber daya tunggal (penghindaran deadlock)

Tiga state alokasi sumber daya :

1. Safe.
2. Safe
3. Unsafe.

 

L)   Algoritma Banker untuk beberapa sumber (penghindaran deadlock)

Contoh algoritma banker dengan beberapa sumber.
M)   Pemrograman: alokasi sumber daya

 

N)   Logika Algoritma Banker

 

O)   Pencegahan Deadlock

Menahan cara permintaan dapat dibuat.

• Mutual Exclusion = tidak diperlukan untuk sumber sharable; harus menahan untuk sumber daya nonsharable.
• Hold dan Wait = harus menjamin bahwa setiap kali proses meminta sumber daya, proses tidak menahan sumber daya lainnya.
  – Membutuhkan proses untuk meminta dan dialokasikan semua sumber dayanya sebelum memulai eksekusi, atau mengizinkan proses untuk meminta sumber daya hanya ketika proses tidak ada.
  – Pemanfaatan sumber daya yang rendah; kemungkinan starvation.
• Circular Wait

(a) Biasanya sumber diurutkan.
(b) Grafik sumber daya.

• No Preemption

– Ini bukan pilihan yang layak.

– Pertimbangkan sebuah proses yang diberikan printer.
* setengah jalan melalui tugasnya.
* sekarang paksa mengambil printer.
* !! ??

P)   Ringkasan untuk Pencegahan deadlock

 

Q)   Starvation

• Algoritma untuk mengalokasikan sumber daya.
  – mungkin untuk memberikan pekerjaan terpendek terlebih dahulu.
• Bekerja dengan baik untuk beberapa pekerjaan singkat dalam suatu sistem.
• Dapat menyebabkan pekerjaan lama ditunda tanpa batas waktu
  – meskipun tidak diblok.
• Solusi :
  – kebijakan First-come, first-serve.

 

R)   Deadlock Recovery (Proses Termination)

• Membatalkan semua proses deadlock.
• Batalkan satu proses sekaligus sampai siklus deadlock dihilangkan.
• Dalam rangka apa yang harus kita pilih untuk membatalkan proses?
  – Prioritas proses.
  – Berapa lama proses telah dihitung, dan berapa lama lagi sampai selesai.
  – Sumber daya proses telah digunakan.
  – Proses sumber daya perlu dilengkapi.
  – Berapa banyak proses harus dihentikan.
  – Apakah proses interaktif atau berkelompok?

S)   Deadlock Recovery (Sumber daya Preemption)

• Selecting a victim = meminimalkan biaya.
• Rollback = kembali ke beberapa state aman, proses restart untuk state tersebut.
• Starvation = proses yang sama selalu dapat dipilih sebagai victim, termasuk jumlah rollback di faktor biaya.

T)   Deadlock Handling (Pendekatan Gabungan)

• Menggabungkan tiga pendekatan dasar
  – prevention.
  – avoidance.
  – detection.
  *memungkinkan penggunaan pendekatan yang optimal untuk setiap sumber daya dalam sistem.
• Sumber daya partisi ke dalam kelas uruta secara hierarki.
• Menggunakan teknik yang paling tepat untuk menangani deadlock dalam setiap kelas.