Deadlock adalah keadaan dimana dalam sistem komputasi dimana dua atau lebih proses tidak dapat melanjutkan eksekusi karena masing-masing menunggu sumber daya yang sedang digunakan oleh proses lain. Jadi, setiap proses berada dalam keadaan menunggu, dan tidak ada proses yang bisa maju karena sumber daya jenis yang dibutuhkan sedang digunakan oleh proses lain dan belum dilepaskan.
Resource deadlock, atau lebih umum disebut deadlock, merujuk ke situasi di mana dua atau lebih proses atau thread saling menunggu sumber daya yang sedang digunakan atau dimiliki oleh yang lain, sehingga tidak ada yang dapat melanjutkan eksekusi. Berikut adalah contoh sederhana:
Misalkan kita memiliki dua proses, P1 dan P2, dan dua sumber daya, R1 dan R2. P1 memegang R1 dan membutuhkan R2 untuk melanjutkan, sementara P2 memegang R2 dan membutuhkan R1 untuk melanjutkan. Kedua proses tersebut saling menunggu dan berakhir dalam keadaan buntu atau deadlock.
Contoh kasus deadlock dalam sistem operasi melibatkan penggunaan sumber daya seperti memori, I/O devices, atau CPU cycles. Misalnya, proses X bisa menunggu sumber daya yang dimiliki oleh proses Y, sementara proses Y menunggu sumber daya yang dimiliki oleh proses X. Karena masing-masing proses tidak dapat melanjutkan sampai mendapatkan sumber daya yang dibutuhkan, maka kedua proses tersebut berada dalam keadaan deadlock.
Dalam kasus ini, kedua proses tidak dapat melanjutkan karena mereka saling menunggu pembebasan sumber daya oleh proses lain. Ini adalah contoh deadlock Jadi deadlock ialah suatu kondisi proses tidak dijalankan lagi atau pun tidak ada komunikasi lagi antar proses.
Pencegahan, pendeteksian, dan pemulihan dari deadlock merupakan bagian penting dalam desain sistem operasi. Ada berbagai algoritma dan teknik yang digunakan untuk menangani situasi deadlock, seperti Ostrich Algorithm, Banker’s Algorithm, dan lainnya.
Model Sistem Deadlock
Model sistem deadlock melibatkan representasi sistem dan hubungan antara proses dan sumber daya yang membentuk potensi kondisi deadlock. Model ini sering kali menggunakan grafik alokasi sumber daya, dimana simpul mewakili proses dan sumber daya, dan tepi mewakili klaim atau alokasi sumber daya.
Berikut adalah komponen penting dalam model sistem deadlock:
- Proses: Ini adalah unit dasar dari eksekusi kode dalam sistem. Proses dapat meminta, menggunakan, dan melepaskan sumber daya.
- Sumber Daya: Sumber daya adalah apa saja yang dapat digunakan oleh proses. Ini bisa berupa memori, I/O device, file, atau sumber daya lainnya. Sumber daya dapat di kategorikan menjadi dua, yaitu: sumber daya yang dapat dibagi (shareable) dan sumber daya yang tidak dapat dibagi (non-shareable).
- Klaim: Sebuah klaim terjadi ketika proses menunjukkan bahwa ia mungkin akan meminta sumber daya di masa depan. Klaim ini tidak berarti proses saat ini memerlukan sumber daya, hanya menandakan bahwa proses tersebut mungkin memerlukannya nanti.
- Alokasi: Ini adalah tindakan pemberian atau penggunaan sumber daya oleh suatu proses.
Dalam model ini, sebuah deadlock dapat dilihat sebagai suatu siklus dalam grafik alokasi sumber daya: sebuah proses menunggu sumber daya yang dipegang oleh proses lain, yang poros tersebut juga menunggu sumber daya yang dipegang oleh proses lain, dan seterusnya, sampai ada proses yang menunggu sumber daya yang dipegang oleh proses pertama. Jika ada siklus seperti ini, maka sistem berada dalam keadaan deadlock.
Karakteristik Deadlock
Deadlock memiliki beberapa karakteristik utama:
- Mutual Exclusion: Ini berarti bahwa minimal satu sumber daya (bisa jadi sebuah file, printer, memori, dll) harus dalam keadaan tidak dapat dibagi atau secara eksklusif dimiliki oleh satu proses dalam satu waktu tertentu.
- Hold and Wait: Proses yang sudah memegang sumber daya dapat meminta sumber daya lain yang sudah dikuasai oleh proses lain.
- No Preemption: Sumber daya tidak dapat dipaksa dilepaskan dari proses yang sedang memegangnya. Sumber daya hanya bisa dilepaskan secara sukarela oleh proses yang memegangnya.
- Circular Wait: Ada sebuah rangkaian (setidaknya dua) proses dengan setiap proses memegang setidaknya satu sumber daya dan meminta sumber daya yang dimiliki oleh proses berikutnya dalam rangkaian. Ini menghasilkan lingkaran penungguan.
Kesemua kondisi ini harus terpenuhi secara bersamaan agar deadlock dapat terjadi. Jika proses sudah memiliki salah satu dari kondisi ini tidak terpenuhi, maka deadlock dapat dihindari. Pencegahan deadlock biasanya melibatkan memastikan bahwa minimal menemukan satu informasi dari kondisi ini tidak terpenuhi.
Mengelola deadlock dalam masalah yang signifikan dan melibatkan pencegahan deadlock (dengan merancang sistem sehingga kondisi di atas tidak terjadi), deteksi deadlock (mencari siklus dalam grafik alokasi sumber daya), dan pemulihan dari deadlock (sering kali dengan membatalkan proses atau merampas dan melepaskan sumber daya).
Metode Menangani Deadlock
Ada beberapa metode utama untuk menangani deadlock dalam sistem operasi:
1. Pencegahan Deadlock
Pencegahan deadlock melibatkan desain sistem dengan cara yang menjamin kondisi yang dapat menyebabkan deadlock tidak pernah terjadi. Untuk mencegah deadlock, kita perlu memastikan bahwa setidaknya satu dari empat kondisi Coffman (Mutual Exclusion, Hold and Wait, No Preemption, dan Circular Wait) untuk deadlock tidak pernah terjadi.
Cara spesifik untuk melakukan ini akan sangat bergantung pada sistem dan sumber daya yang spesifik. Misalnya, kita mungkin mencegah kondisi “HAW” dengan memastikan bahwa proses meminta semua sumber daya yang dibutuhkannya sebelum memulai, atau dengan memaksa proses untuk melepaskan semua sumber daya yang dimilikinya sebelum meminta lebih lanjut.
2. Penghindaran Deadlock
Penghindaran deadlock berfokus pada pemeriksaan kondisi sistem sebelum alokasi sumber daya untuk memastikan bahwa alokasi tersebut tidak akan membuat sistem dalam keadaan “tidak aman” yang berpotensi mengarah ke deadlock. Ini melibatkan pengetahuan awal tentang berapa banyak sumber daya yang mungkin diminta oleh setiap proses. Dalam pendekatan ini, sistem operasi mempertahankan keadaan “aman” dengan menghindari alokasi sumber daya yang bisa mengarah ke deadlock. Algoritma Bankir adalah contoh umum dari strategi penghindaran deadlock.
3. Mendeteksi Deadlock
Pendeteksian deadlock adalah proses mengidentifikasi apakah sistem berada dalam keadaan deadlock atau tidak. Biasanya, sistem operasi perlu mempertahankan beberapa jenis struktur data untuk memantau status alokasi sumber daya dan permintaan oleh proses yang berbeda. Algoritma pendeteksi deadlock kemudian dapat jalan secara periodik atau berdasarkan kondisi tertentu untuk mengecek apakah deadlock telah terjadi.
Untuk mendeteksi deadlock, biasanya digunakan model berbasis grafik. Proses dan sumber daya direpresentasikan sebagai simpul dalam grafik, dan tepi diarahkan dari proses ke sumber daya yang mereka minta (atau sebaliknya, dari sumber daya ke proses yang memegangnya). Jika ada siklus dalam grafik ini, maka itu menunjukkan adanya deadlock.
Berikut adalah cara umum untuk mendeteksi deadlock:
- Buat sebuah grafik alokasi sumber daya: simpul mewakili proses dan sumber daya, dan tepi mewakili klaim atau alokasi sumber daya.
- Cari adanya siklus dalam grafik. Jika ada siklus, maka ada potensi untuk deadlock.
Pendeteksian deadlock harus diikuti dengan mekanisme pemulihan untuk memecahkan situasi deadlock yang ditemukan. Ini bisa berarti memaksa proses untuk melepaskan sumber daya, menghentikan (kill) proses, atau melakukan rollback proses ke beberapa state sebelumnya. Bagaimana cara pemulihan dilakukan akan sangat bergantung pada spesifik sistem dan kebijakan yang ada.
Pendeteksian deadlock biasanya ditangani oleh konstruksi wait-for graph (WFG) yang menunjukkan ketergantungan transaksi, yaitu transaksi Ti tergantung pada Tj jika transaksi Tj memegang lock pada sebuah item data yang ditunggu oleh Ti.
WFG adalah sebuah directed graph G = (N, E ) yang terdiri dari satu set node N dan satu set directed edge E, yang dikonstruksi sebagai berikut
- Buat sebuah node untuk setiap transaksi.
- Buat sebuah directed edge Ti → Tj , jika transaksi Ti menunggu untuk melakukan lock sebuah item yang sedang di-lock oleh Tj.
Deadlock terjadi jika dan hanya jika WFG mengandung sebuah cycle. WFG yang menumukan deadlock dibandingkan antara dua transaksi.
4. Perbaikan Dari Deadlock
Setelah deadlock terdeteksi, ada beberapa strategi untuk memperbaikinya dan memulihkan sistem:
- Memaksa proses melepaskan sumber daya: Dalam strategi ini, sistem operasi memaksa proses yang terlibat dalam deadlock untuk melepaskan beberapa atau semua sumber daya yang mereka pegang, sehingga sumber daya tersebut bisa digunakan oleh proses lain. Ini bisa mengganggu proses yang terpaksa melepaskan sumber dayanya, tetapi bisa mencegah secara keseluruhan menjadi tidak responsif.
- Menghentikan proses (Kill process): Dalam kasus yang lebih ekstrem, sistem operasi dapat memilih untuk menghentikan satu atau lebih proses untuk membebaskan sumber daya yang mereka pegang. Ini tentu saja dapat menghasilkan kerugian data atau pekerjaan yang dilakukan oleh proses yang dihentikan, dan oleh karena itu biasanya merupakan opsi terakhir.
- Rollback: Dalam beberapa kasus, mungkin ada opsi untuk mengembalikan proses ke keadaan sebelumnya (rollback) yang bukan bagian dari keadaan deadlock. Ini bisa menjadi strategi yang efektif jika dirancang dengan kemampuan untuk membuat dan memulihkan titik pengecekan (checkpoints), tetapi juga bisa menjadi kompleks dan membutuhkan banyak sumber daya.
- Menunggu: Terkadang, bisa jadi opsi yang paling masuk akal adalah sekadar menunggu – terutama jika ada peluang bahwa proses akan melepaskan sumber daya yang dibutuhkan dalam waktu dekat. Namun, ini bisa menjadi risiko, karena jika proses tidak melepaskan sumber daya, maka deadlock akan terus berlanjut.
Dalam prakteknya, memilih strategi untuk pemulihan deadlock akan sangat bergantung pada kebijakan dan karakteristik khusus dari proses dan sumber daya yang terlibat dalam deadlock. Biasanya, akan ada beberapa jenis penyeimbangan antara menghindari gangguan pada proses individu dan menjaga agar sistem secara keseluruhan tetap berfungsi dengan baik.
Setiap metode memiliki kelebihan dan kekurangan sendiri dan pilihan metode tergantung pada sejumlah faktor seperti sumber daya sistem, jumlah dan jenis proses, dan karakteristik sumber daya yang digunakan.
Contoh Lain Yang Menyebabkan Terjadi Deadlock
Berikut ini beberapa yang bisa menyebabkan dan contohnya deadlock:
- Kontenstan dalam Jaringan Komputer: Bayangkan dua komputer, A dan B, yang berkomunikasi melalui jaringan. Komputer A mengirim pesan ke B dan tidak akan melanjutkan sampai menerima akhiran dari B. Sementara itu, B juga mengirim pesan ke A dan tidak akan melanjutkan sampai menerima akhiran dari A. Jika ada masalah dalam pengiriman akhiran, kedua komputer bisa berakhir dalam keadaan deadlock, di mana masing-masing menunggu akhiran dari yang lain.
- Sistem Database: Dalam sistem database, dua atau lebih transaksi mungkin perlu mengunci baris atau tabel yang sama untuk mencegah konflik. Jika setiap transaksi berhasil mengunci sebagian dari sumber daya yang dibutuhkan dan kemudian menunggu sumber daya lain yang dikunci oleh transaksi lain, maka bisa terjadi deadlock.
- Multithreading: Dalam pengkodean multithread, deadlock bisa terjadi jika dua atau lebih thread saling menunggu untuk mendapatkan lock pada objek yang sudah terkunci oleh thread lain. Misalnya, jika thread A memiliki lock pada objek X dan menunggu untuk mendapatkan lock pada objek Y, sementara thread B memiliki lock pada objek Y dan menunggu untuk mendapatkan lock pada objek X, maka kedua thread tersebut berada dalam keadaan deadlock.
Dalam semua kasus ini, penting untuk merancang algoritma dengan cara yang mencegah atau setidaknya mengurangi kemungkinan terjadinya deadlock. Ini bisa melibatkan teknik seperti timeout (dimana operasi dibatalkan jika tidak selesai dalam waktu tertentu), pengurutan sumber daya (dimana sumber daya selalu diminta dalam urutan tertentu untuk mencegah kondisi deadlock), atau penggunaan algoritma penghindaran atau pendeteksian deadlock.