Deadlock pada Sistem Operasi

• Sistem Operasi: Deadlock
• Pokok bahasan meliputi Model Sistem, Metode Penanganan Deadlock, serta Deteksi dan Pemulihan Deadlock (Recovery).

Model Sistem dan Deadlock

• Sistem komputer terdiri dari berbagai sumber daya (resources) seperti CPU, blok memori, dan perangkat I/O.
• Setiap sumber daya menangani setidaknya satu pekerjaan (task) sebagai representasi dari sebuah proses.
• Proses menggunakan sumber daya melalui instruksi seperti request, use, dan release.
• Kepentingan proses yang berbeda dapat memunculkan kompetisi yang berujung pada kondisi deadlock.
• Deadlock terjadi jika empat kondisi berikut terjadi bersamaan:
  • Mutual Exclusion: Hanya satu proses yang dapat menggunakan sumber daya.
  • Hold and Wait: Proses yang memegang setidaknya satu sumber daya, menunggu sumber daya lain.
  • No Preemption: Sumber daya hanya dapat dilepaskan oleh proses yang memegangnya setelah tugasnya selesai.
  • Circular Wait: Sekelompok proses saling menunggu sumber daya yang digunakan oleh proses lain dalam kelompok tersebut.
• Hubungan antara proses dan sumber daya dapat digambarkan dalam graf alokasi sumber daya.
• Verteks (simpul) dalam graf dapat berupa:
  • Kumpulan proses/thread T = {T₁, T₂, ..., Tₙ}
  • Kumpulan sumber daya R = {R₁, R₂, ..., Rₙ}
• Edge (sisi) dalam graf dapat berupa:
  • Request: Proses meminta sumber daya (Tᵢ → Rⱼ).
  • Assignment: Sumber daya dialokasikan ke proses (Rⱼ → Tᵢ).
• Contoh graf alokasi tanpa deadlock: R₁ dan R₃ memiliki satu "instance", R₂ memiliki dua instance, dan R₄ terdiri dari tiga instance. T₁ menggunakan satu instance R₂ dan memerlukan satu instance lagi dari R₁. T₂ memiliki dua instance, masing-masing satu dari R₁ dan R₂, serta memerlukan satu instance dari R₃. T₃ masih menggunakan satu instance dari R₃.
• Pada contoh graf alokasi dengan deadlock, terdapat loop seperti R₂-T₂-R₃-T₃-R₂ atau R₂-T₁-R₁-T₂-R₃-T₃-R₂.
• Tidak semua cycle (loop) dalam graf alokasi sumber daya menimbulkan deadlock.

Metode Penanganan Deadlock

• Terdapat tiga pendekatan utama untuk menangani deadlock:

  • Deadlock prevention dan avoidance: Memastikan sistem tidak akan pernah mengalami deadlock.
  • Deadlock recovery: Mengatasi deadlock jika terjadi.
  • Mengabaikan masalah deadlock: Mengasumsikan deadlock tidak akan pernah terjadi.

• Deadlock prevention mencegah terjadinya deadlock dengan membatasi empat kondisi penyebabnya:

  • Mutual Exclusion: Tidak dapat dicegah jika sumber daya memang tidak bisa digunakan bersamaan.
  • Hold and Wait: Proses yang meminta sumber daya lain harus melepaskan sumber daya yang sedang dipegang.
  • No Preemption: Sumber daya dapat diambil paksa dari proses yang memegangnya.
  • Circular Wait: Menentukan urutan perolehan sumber daya yang ketat.

• Deadlock avoidance memerlukan informasi tentang kebutuhan sumber daya maksimum setiap proses sebelum dieksekusi.

• Algoritme avoidance mengecek penggunaan sumber daya untuk memastikan tidak terjadi circular waiting.

• Safety state adalah status alokasi sumber daya yang menjamin sistem dapat menyelesaikan semua proses tanpa deadlock.

• Dua algoritme deadlock avoidance:

  • Graf Alokasi untuk sumber daya dengan instance tunggal. Siklus edge terdiri dari claim edge, request edge, assignment edge, dan claim edge
  • Banker's Algorithm untuk sumber daya dengan multiple instance. Dalam algoritma ini, setiap proses mendefinisikan jenis dan jumlah sumber daya yang dibutuhkan sebelumnya. Jika sebuah proses meminta resource, proses mungkin harus menunggu dan dilepaskan kembali setelah kurun waktu tertentu.

Deadlock Recovery

• Jika terjadi deadlock, sistem operasi menjalankan prosedur perbaikan:
  • Memilih proses yang terlibat sebagai korban.
  • Mengembalikan sistem ke safe state sebelumnya, dan me-restart proses.
  • Metode ini dapat menyebabkan starvation, di mana satu proses terus-menerus dipilih sebagai korban.