Pengantar dan Karakteristik Deadlock

Back to: IF2130 Sistem Operasi

Topic

Questions/Cues

• Definisi & contoh deadlock?
• Apa itu model sistem?
• Siklus penggunaan sumber daya?
• Perbedaan deadlock & livelock?
• Empat syarat mutlak deadlock?
• Struktur Resource-Allocation Graph?
• Kapan siklus di RAG berarti deadlock?

Reference Points

• Apa hayo

Definisi dan Masalah Deadlock

Definisi: Sebuah situasi di lingkungan multiprogramming di mana satu set thread (atau proses) saling menunggu tanpa batas waktu. Setiap thread dalam set tersebut menunggu sebuah sumber daya yang hanya dapat dilepaskan oleh thread lain dalam set yang sama. Akibatnya, tidak ada thread yang dapat melanjutkan eksekusinya. Ini adalah bentuk kegagalan kelangsungan hidup (liveness failure).

Contoh Sederhana:

1. Hukum Lalu Lintas Kansas: Analogi di mana dua kereta tiba di persimpangan rel pada saat yang sama. Hukum mengharuskan keduanya berhenti dan tidak ada yang boleh jalan sampai yang lain lewat. Keduanya akan menunggu selamanya.
2. Dining Philosophers: Beberapa filsuf duduk di meja bundar dengan satu sumpit di antara masing-masing dari mereka. Jika setiap filsuf mengambil sumpit di sebelah kirinya secara bersamaan, maka semua akan menunggu sumpit di sebelah kanan mereka, yang saat ini dipegang oleh tetangga mereka.
3. Dua Tape Drive: Proses P1 memegang Tape Drive 1 dan meminta Tape Drive 2. Pada saat yang sama, Proses P2 memegang Tape Drive 2 dan meminta Tape Drive 1. Keduanya terjebak dalam deadlock.

Model Sistem:

• Sistem diasumsikan memiliki sejumlah sumber daya yang terbatas (finite number of resources).
• Sumber daya ini dibagi ke dalam beberapa tipe (atau kelas), misalnya tipe CPU, tipe mutex lock, tipe file.
• Setiap tipe sumber daya memiliki satu atau lebih instance yang identik. Contoh: tipe CPU mungkin punya 4 instance (pada prosesor quad-core). Sebuah thread yang meminta instance dari suatu tipe dapat dipuaskan oleh instance mana pun dari tipe tersebut.

Siklus Penggunaan Sumber Daya: Sebuah thread harus menggunakan sumber daya dalam urutan yang jelas:

1. Request (Minta): Thread meminta sumber daya. Jika sumber daya tidak tersedia, thread memasuki keadaan menunggu (waiting state).
2. Use (Gunakan): Thread dapat mengoperasikan atau menggunakan sumber daya tersebut (misalnya, menulis ke file atau mengakses critical section).
3. Release (Lepas): Thread melepaskan sumber daya, membuatnya tersedia untuk thread lain.

Empat Karakteristik (Syarat) Deadlock: Deadlock hanya dapat terjadi jika keempat kondisi berikut terpenuhi secara bersamaan dalam sistem.

• Mutual Exclusion (Eksklusi Bersama): Setidaknya ada satu sumber daya yang dipegang dalam mode non-sharable (tidak dapat dibagi). Artinya, hanya satu thread yang dapat menggunakan sumber daya tersebut pada satu waktu.
• Hold and Wait (Memegang dan Menunggu): Sebuah thread sedang memegang setidaknya satu sumber daya dan pada saat yang sama sedang menunggu untuk mendapatkan sumber daya tambahan yang saat ini dipegang oleh thread lain.
• No Preemption (Tanpa Paksaan): Sumber daya tidak dapat diambil secara paksa dari thread yang memegangnya. Sumber daya hanya dapat dilepaskan secara sukarela oleh thread tersebut setelah menyelesaikan tugasnya.
• Circular Wait (Menunggu Siklik): Terdapat sebuah set thread yang menunggu {T₀, T₁, …, Tₙ} di mana T₀ menunggu sumber daya yang dipegang T₁, T₁ menunggu sumber daya yang dipegang T₂, …, dan Tₙ menunggu sumber daya yang dipegang oleh T₀, membentuk sebuah rantai siklik.

Livelock:

• Bentuk kegagalan kelangsungan hidup lain yang mirip dengan deadlock.
• Perbedaannya adalah, dalam livelock, thread-thread tidak terblokir. Mereka terus-menerus mencoba melakukan suatu tindakan, tetapi tindakan itu selalu gagal karena saling mengganggu, sehingga tidak ada kemajuan yang dibuat.
• Analogi: Dua orang mencoba berpapasan di lorong sempit. Keduanya bergerak ke sisi yang sama untuk memberi jalan, lalu ke sisi lain secara bersamaan, dan terus begitu tanpa ada yang berhasil lewat.

Resource-Allocation Graph (RAG):

• Graf berarah yang digunakan untuk menggambarkan keadaan alokasi sumber daya secara visual.
• Komponen Graf:
• Vertices (Node): Terdiri dari dua jenis.
  • Threads (T): Digambarkan sebagai lingkaran.
  • Tipe Sumber Daya (R): Digambarkan sebagai persegi panjang. Titik di dalam persegi panjang merepresentasikan instance dari sumber daya tersebut.
• Edges (Panah):
  • Request Edge (T → R): Panah dari thread ke persegi sumber daya. Artinya, thread T sedang meminta sebuah instance dari tipe sumber daya R.
  • Assignment Edge (R → T): Panah dari titik (instance) di dalam persegi sumber daya ke thread. Artinya, instance tersebut telah dialokasikan ke thread T.

Hubungan Siklus RAG dengan Deadlock:

• Aturan ini adalah kunci untuk mendeteksi deadlock secara visual.
• Jika RAG tidak mengandung siklus: Dapat dipastikan TIDAK ADA deadlock dalam sistem.
• Jika RAG mengandung siklus:
• Kasus Khusus (1 Instance per Tipe): Jika setiap tipe sumber daya hanya memiliki satu instance, maka adanya siklus PASTI BERARTI telah terjadi deadlock.
• Kasus Umum (Beberapa Instance per Tipe): Jika ada tipe sumber daya yang memiliki beberapa instance, maka siklus hanyalah INDIKASI KEMUNGKINAN deadlock. Deadlock belum tentu terjadi jika ada thread dalam siklus yang permintaannya masih bisa dipenuhi oleh instance lain yang bebas.

Summary

Deadlock adalah kondisi kritis di mana sekelompok proses atau thread saling menunggu sumber daya dalam sebuah siklus tertutup, yang hanya bisa terjadi jika empat kondisi—mutual exclusion, hold and wait, no preemption, dan circular wait—terpenuhi secara bersamaan. Keadaan ini dapat divisualisasikan menggunakan Resource-Allocation Graph (RAG), di mana adanya siklus merupakan indikator kuat (dan syarat pasti jika sumber daya hanya memiliki satu instance) terjadinya deadlock.

Fitur	Deadlock	Livelock	Starvation
Keadaan Proses	Blocked (Menunggu)	Running (Aktif)	Running / Ready
Kemajuan	Tidak ada kemajuan	Tidak ada kemajuan	Mungkin ada kemajuan, tapi satu proses diabaikan
Penyebab	Menunggu siklik	Upaya pemulihan yang terus-menerus gagal & sinkron	Algoritma penjadwalan yang tidak adil (mis. prioritas rendah)
Analogi	Mobil di persimpangan 4 arah yang macet total	Dua orang di lorong yang terus bergerak ke arah yang sama	Orang yang antre tapi selalu diserobot

Additional Information (Optional)

• Formalisasi Kondisi Circular Wait: Secara matematis, kondisi circular wait berarti ada sebuah himpunan proses P0​,P1​,…,Pn​ sedemikian rupa sehingga P0​ menunggu sumber daya yang dipegang oleh P1​, P1​ menunggu sumber daya yang dipegang oleh P2​, dan seterusnya, hingga Pn​ menunggu sumber daya yang dipegang oleh P0​. Ini adalah permutasi siklik dalam ketergantungan sumber daya.
• RAG dalam Konteks Teori Graf: Deteksi siklus dalam sebuah Resource-Allocation Graph adalah masalah klasik dalam teori graf. Algoritma yang paling umum digunakan adalah Depth-First Search (DFS). Algoritma ini menjelajahi graf sedalam mungkin di setiap cabang sebelum mundur. Jika selama penjelajahan ia menemukan sebuah node yang sudah pernah dikunjungi dalam jalur rekursi saat ini, maka sebuah siklus telah terdeteksi. Kompleksitas algoritma ini adalah O(V+E), di mana V adalah jumlah vertex (threads + tipe sumber daya) dan E adalah jumlah edge (requests + assignments).

Eksplorasi Mandiri:

• Latihan Menggambar RAG:
  1. Gambarkan RAG untuk skenario deadlock Dining Philosophers dengan 3 filsuf (F1, F2, F3) dan 3 sumpit (S1, S2, S3). Asumsikan F1 memegang S1 dan menunggu S2, F2 memegang S2 dan menunggu S3, dan F3 memegang S3 dan menunggu S1. Anda akan melihat siklus dengan jelas.
  2. Gambarkan RAG untuk skenario tanpa deadlock berikut: Tipe sumber daya R1 memiliki 2 instance dan R2 memiliki 1 instance.
  • T1 memegang satu instance R1 dan menunggu R2.
  • T2 memegang satu instance R1 dan satu instance R2, lalu menunggu instance R1 yang lain.
  • T3 memegang instance R1 yang diminta oleh T2. Identifikasi siklus yang ada, dan jelaskan mengapa skenario ini belum tentu deadlock. (Petunjuk: Pikirkan urutan pelepasan sumber daya yang mungkin).