Pencegahan dan Penghindaran Deadlock

Back to: IF2130 Sistem Operasi

Topic

Questions/Cues

• Prinsip pencegahan (prevention)?
• Cara mencegah 4 syarat deadlock?
• Strategi circular wait (urutan total)?
• Prinsip penghindaran (avoidance)?
• Konsep Safe State vs Unsafe State?
• Algoritma RAG (1 instance)?
• Algoritma Banker (multi-instance)?
• Struktur data Algoritma Banker?
• Langkah-langkah Algoritma Banker?

Reference Points

• Page 34-36

Deadlock Prevention (Pencegahan)

1. Bekerja dengan cara memastikan setidaknya satu dari empat kondisi deadlock tidak akan pernah terpenuhi. Ini adalah pendekatan yang bersifat statis dan restriktif, dengan memberlakukan aturan ketat pada cara thread meminta sumber daya.
2. Menyerang 4 Kondisi:
   • Mutual Exclusion: Umumnya tidak bisa dicegah karena banyak sumber daya (seperti printer atau mutex lock) yang secara inheren bersifat non-sharable.
   • Hold and Wait: Dapat dicegah dengan dua protokol, namun keduanya memiliki kelemahan signifikan:
     • Protokol 1: Thread harus meminta dan mendapatkan semua sumber daya yang dibutuhkan sebelum eksekusi dimulai. Kelemahan: Pemanfaatan sumber daya sangat rendah.
     • Protokol 2: Thread hanya boleh meminta sumber daya jika ia tidak sedang memegang sumber daya lain. Kelemahan: Bisa jadi tidak efisien dan menyebabkan starvation.
   • No Preemption: Dapat dicegah dengan mengizinkan sistem mengambil paksa (preempt) sumber daya. Jika sebuah thread yang memegang sumber daya meminta sumber daya lain yang tidak tersedia, semua sumber dayanya saat ini dilepaskan. Kelemahan: Sangat sulit diimplementasikan untuk sumber daya seperti mutex lock, namun lebih memungkinkan untuk sumber daya yang keadaannya mudah disimpan dan dipulihkan (misalnya, register CPU).
   • Circular Wait (Paling Praktis):
     • Ini adalah metode pencegahan yang paling sering digunakan dan paling praktis.
     • Strategi: Terapkan urutan total (total ordering) pada semua tipe sumber daya di sistem (misal, beri nomor unik pada setiap kunci: Kunci1, Kunci2, Kunci3, …).
     • Aturan: Setiap thread wajib meminta sumber daya dalam urutan menaik. Contoh: Jika sebuah thread memegang Kunci3, ia hanya boleh meminta Kunci4, Kunci5, dst., tetapi tidak boleh meminta Kunci2.
     • Hasil: Dengan aturan ini, siklus permintaan secara matematis menjadi tidak mungkin terjadi.

Deadlock Avoidance (Pencegahan)

• Prinsip: Pendekatan yang lebih dinamis daripada pencegahan. Sistem tidak melarang kondisi deadlock, tetapi menggunakan informasi tambahan (a priori) tentang kebutuhan sumber daya setiap thread untuk membuat keputusan alokasi yang cerdas. Tujuannya adalah untuk tidak pernah memasuki unsafe state.
• Safe State vs. Unsafe State:
  • Safe State (Keadaan Aman): Sebuah keadaan di mana sistem dapat menjamin adanya setidaknya satu urutan aman (safe sequence), yaitu urutan eksekusi thread yang memungkinkan semua thread selesai tanpa mengalami deadlock.
  • Unsafe State (Keadaan Tidak Aman): Keadaan apa pun yang tidak aman. Keadaan ini memiliki potensi untuk mengarah ke deadlock, tetapi belum tentu merupakan deadlock.
  • Tujuan Penghindaran: Memastikan sistem tidak pernah meninggalkan safe state. Setiap permintaan yang dapat membawa sistem ke unsafe state akan ditunda.
• Algoritma Penghindaran:
• Resource-Allocation Graph (untuk 1 instance/tipe):
  • Menggunakan jenis panah baru: claim edge (panah putus-putus), yang menandakan thread mungkin akan meminta sumber daya tersebut di masa depan.
  • Permintaan hanya akan dikabulkan jika pengubahan request edge menjadi assignment edge tidak menciptakan siklus dalam graf.
• Banker’s Algorithm (untuk beberapa instance/tipe):
  • Analogi: Seperti bank yang tidak akan mengalokasikan pinjaman jika berisiko tidak dapat memenuhi penarikan dana nasabah lain di masa depan.
  • Struktur Data Kunci:
    • Available: Vektor jumlah instance yang tersedia untuk setiap tipe sumber daya.
    • Max: Matriks [n × m] yang berisi jumlah maksimum instance yang mungkin diminta oleh setiap thread (n) untuk setiap tipe sumber daya (m).
    • Allocation: Matriks [n × m] yang berisi jumlah instance yang saat ini dialokasikan ke setiap thread.
    • Need: Matriks [n × m] yang berisi sisa instance yang masih dibutuhkan setiap thread. Dihitung dengan: Need = Max - Allocation.
  • Alur Kerja saat Ada Permintaan:
    1. Validasi: Pastikan permintaan tidak melebihi klaim maksimum (Request ≤ Need).
    2. Ketersediaan: Pastikan sumber daya yang diminta tersedia (Request ≤ Available).
    3. Simulasi & Pengecekan Keamanan: Sistem “berpura-pura” mengalokasikan sumber daya tersebut (memperbarui Available, Allocation, dan Need sementara). Kemudian, sistem menjalankan Safety Algorithm untuk memeriksa apakah keadaan baru ini masih safe.
    4. Keputusan: Jika keadaan baru terbukti safe, alokasi disetujui. Jika tidak, alokasi dibatalkan (keadaan dikembalikan seperti semula) dan thread harus menunggu.
  • Algoritma Keamanan (buat ngecek sistem aman atau tidak):
    1. Bikin vektor Work = Available.
    2. Bikin vektor Finish (isinya true/false) buat tiap thread, awalnya semua false.
    3. Cari thread i yang Finish[i]-nya false DAN Need_i ≤ Work. Kalau tidak ada, lanjut ke langkah 5.
    4. Kalau ketemu thread i: Work = Work + Allocation_i (anggap dia selesai dan balikin sumber dayanya), terus Finish[i] = true. Balik lagi ke langkah 3.
    5. Kalau semua Finish[i] jadi true, berarti sistemnya aman.
  • Algoritma Permintaan Sumber Daya (pas thread minta):
    1. Kalau permintaan thread Ti (Request_i) lebih besar dari Need_i dia, error (minta kebanyakan).
    2. Kalau Request_i lebih besar dari Available sekarang, Ti harus nunggu (sumber dayanya kurang).
    3. Kalau tidak, sistem pura-pura ngasih: Available = Available - Request_i, Allocation_i = Allocation_i + Request_i, Need_i = Need_i - Request_i. Terus cek pakai Algoritma Keamanan tadi. Kalau hasilnya aman, beneran dikasih. Kalau tidak aman, pura-puranya dibatalin, Ti harus nunggu.

Summary

Pencegahan dan Penghindaran adalah dua strategi proaktif untuk menangani deadlock, di mana Pencegahan menerapkan aturan statis yang ketat untuk mematahkan salah satu dari empat kondisi deadlock (dengan pengurutan sumber daya menjadi metode paling praktis), sementara Penghindaran menggunakan pendekatan dinamis yang memerlukan informasi kebutuhan maksimum untuk memastikan sistem tidak pernah memasuki keadaan tidak aman melalui algoritma seperti Algoritma Banker.

Additional Information (Optional)

• Trade-off Kinerja pada Pencegahan: Metode pencegahan, meskipun efektif, seringkali dibayar mahal dengan penurunan kinerja. Mencegah hold-and-wait menyebabkan utilisasi sumber daya yang rendah. Mencegah no preemption sangat kompleks. Bahkan metode terbaik, circular-wait prevention (pengurutan sumber daya), dapat menjadi beban bagi pengembang untuk dirancang dan dipatuhi dalam sistem yang sangat besar dan kompleks dengan ribuan kunci.
• Kelayakan Praktis Algoritma Banker: Meskipun secara teoretis sangat kuat, Algoritma Banker jarang sekali diimplementasikan pada sistem operasi serbaguna (seperti Windows, Linux, macOS). Hambatan utamanya adalah kewajiban untuk mengetahui kebutuhan sumber daya maksimum di muka. Pada aplikasi modern, kebutuhan sumber daya seringkali bersifat sangat dinamis dan tidak dapat diprediksi, membuat persyaratan ini hampir mustahil untuk dipenuhi. Selain itu, overhead komputasi untuk menjalankan Safety Algorithm pada setiap permintaan bisa jadi terlalu tinggi.
• Studi Kasus: Pencegahan di Level Aplikasi: Teknik pencegahan circular wait melalui pengurutan kunci sangat umum dan efektif diimplementasikan oleh programmer di level aplikasi. Contohnya, saat mentransfer dana antar dua rekening, seorang programmer dapat memberlakukan aturan untuk selalu mengunci objek rekening dengan nomor ID yang lebih kecil terlebih dahulu, baru kemudian yang lebih besar. Ini adalah cara praktis untuk mencegah deadlock dalam kode yang mereka tulis sendiri, tanpa bergantung pada sistem operasi.