Deadlock

Dalam komputasi serentak, **kebuntuan** adalah setiap situasi di mana tidak ada anggota dari beberapa kelompok entitas yang dapat melanjutkan karena masing-masing entitas menunggu anggota lain, termasuk dirinya sendiri, untuk mengambil tindakan, seperti mengirim pesan atau, lebih umum, melepaskan kunci. Kebuntuan adalah masalah umum dalam sistem multipengolahan, komputasi paralel, dan sistem terdistribusi, karena dalam konteks ini sistem sering kali menggunakan kunci perangkat lunak atau perangkat keras untuk menengahi sumber daya bersama dan menerapkan sinkronisasi proses.

Dalam sistem operasi, kebuntuan terjadi ketika suatu proses atau utas memasuki keadaan menunggu karena sumber daya sistem yang diminta ditahan oleh proses menunggu lainnya, yang kemudian menunggu sumber daya lain ditahan oleh proses menunggu lainnya. Jika suatu proses tetap tidak dapat mengubah keadaannya tanpa batas waktu karena sumber daya yang diminta sedang digunakan oleh proses lain yang sedang menunggu, maka sistem dikatakan mengalami kebuntuan.

Dalam sistem komunikasi, kebuntuan terjadi terutama karena hilangnya atau rusaknya sinyal, bukan karena perebutan sumber daya.

## Kondisi yang diperlukan secara individu dan kondisi yang cukup secara bersama untuk terjadinya kebuntuan
Situasi kebuntuan pada suatu sumber daya hanya dapat muncul jika seluruh kondisi berikut terjadi secara bersamaan dalam suatu sistem:

# *Pengecualian bersama :* Setidaknya satu sumber daya harus disimpan dalam mode yang tidak dapat dibagikan; artinya, hanya satu proses pada satu waktu yang dapat menggunakan sumber daya tersebut. Jika tidak, proses tidak akan dicegah untuk menggunakan sumber daya bila diperlukan. Hanya satu proses yang dapat menggunakan sumber daya pada waktu tertentu.
# *Tahan dan tunggu* atau *simpan sumber daya:* suatu proses saat ini memegang setidaknya satu sumber daya dan meminta sumber daya tambahan yang ditahan oleh proses lain.
# *Tidak ada perubahan siaran :* sumber daya hanya dapat dilepaskan secara sukarela oleh proses yang memegangnya.
# *Tungguan melingkar:* setiap proses harus menunggu sumber daya yang ditahan oleh proses lain, yang pada gilirannya menunggu proses pertama melepaskan sumber daya tersebut. Secara umum, ada serangkaian proses menunggu, *P* = { *P* 1, *P* 2, ..., *P* *N* }, sehingga *P* 1 menunggu sumber daya yang dimiliki oleh *P* 2, *P* 2 menunggu sumber daya yang dimiliki oleh *P* 3 dan seterusnya hingga *PN* menunggu sumber daya *dimiliki* oleh *P* 1.

Keempat kondisi ini dikenal sebagai *kondisi Coffman* dari uraian pertamanya dalam artikel tahun 1971 oleh Edward G. Coffman,

Meskipun kondisi ini cukup untuk menghasilkan kebuntuan pada sistem sumber daya contoh tunggal, kondisi ini hanya menunjukkan kemungkinan kebuntuan pada sistem yang memiliki banyak contoh sumber daya.

## Penanganan kebuntuan
Kebanyakan sistem operasi saat ini tidak dapat mencegah kebuntuan. Ketika kebuntuan terjadi, sistem operasi yang berbeda meresponsnya dengan cara non-standar yang berbeda. Sebagian besar pendekatan bekerja dengan mencegah terjadinya salah satu dari empat kondisi umum, terutama yang keempat. Pendekatan utama adalah sebagai berikut.

### Mengabaikan kebuntuan
Dalam pendekatan ini diasumsikan bahwa kebuntuan tidak akan pernah terjadi. Ini juga merupakan penerapan algoritma Burung Unta. Pendekatan ini awalnya digunakan oleh MINIX dan UNIX. Hal ini digunakan ketika interval waktu antara terjadinya kebuntuan besar dan kehilangan data yang terjadi setiap kali dapat ditoleransi.

Mengabaikan kebuntuan dapat dilakukan dengan aman jika kebuntuan secara formal terbukti tidak pernah terjadi. Contohnya adalah kerangka RTIC.

### Pemeriksaan
Di bawah deteksi kebuntuan, kebuntuan diperbolehkan terjadi. Kemudian keadaan sistem diperiksa untuk mendeteksi telah terjadi kebuntuan dan selanjutnya diperbaiki. Algoritma digunakan untuk melacak alokasi sumber daya dan status proses, lalu memutar kembali dan memulai ulang satu atau lebih proses untuk menghilangkan kebuntuan yang terdeteksi. Memeriksa kebuntuan yang telah terjadi dapat dilakukan dengan mudah karena sumber daya yang telah dikunci dan/atau diminta oleh setiap proses diketahui oleh penjadwal sumber daya sistem operasi.

Setelah kebuntuan terdeteksi, kebuntuan dapat diperbaiki dengan menggunakan salah satu metode berikut:

# *Penghentian proses:* satu atau lebih proses yang terlibat dalam kebuntuan dapat dibatalkan. Seseorang dapat memilih untuk membatalkan semua proses bersaing yang terlibat dalam kebuntuan tersebut. Hal ini memastikan bahwa kebuntuan diselesaikan dengan pasti dan cepat.&#x5B; **' &#x5D;</sup> Namun biayanya tinggi karena sebagian perhitungan akan hilang. Atau, seseorang dapat memilih untuk membatalkan satu proses pada satu waktu hingga kebuntuan teratasi. Pendekatan ini mempunyai overhead yang tinggi karena setelah setiap pembatalan suatu algoritma harus menentukan apakah sistem masih dalam kebuntuan.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">&#x5B; **' &#x5D; Beberapa faktor harus dipertimbangkan saat memilih kandidat untuk penghentian, seperti prioritas dan usia proses.
# *Perubahan siar* *sumber daya:* sumber daya yang dialokasikan ke berbagai proses dapat didahulukan secara berturut-turut dan dialokasikan ke proses lain hingga kebuntuan terpecahkan.&#x5B; ** &#x5D;

### Pencegahan

Pencegahan kebuntuan bekerja dengan mencegah terjadinya salah satu dari empat kondisi Coffman.

* Menghapus kondisi *saling pengecualian* berarti tidak ada proses yang memiliki akses eksklusif ke sumber daya. Hal ini terbukti mustahil bagi sumber daya yang tidak dapat dikumpulkan. Namun bahkan dengan sumber daya yang terbatas, kebuntuan masih bisa terjadi. Algoritma yang menghindari saling pengecualian disebut algoritma sinkronisasi nirhalang.
* Kondisi *tunggu dan tahan* atau *simpanan sumber daya* dapat dihilangkan dengan mewajibkan proses untuk meminta semua sumber daya yang diperlukan sebelum memulai (atau sebelum memulai serangkaian operasi tertentu). Pengetahuan tingkat lanjut ini sering kali sulit dipenuhi dan, dalam kasus apa pun, merupakan penggunaan sumber daya yang tidak efisien. Cara lain adalah dengan mengharuskan proses meminta sumber daya hanya jika tidak ada sumber daya; Pertama, mereka harus melepaskan semua sumber daya yang mereka miliki saat ini sebelum meminta semua sumber daya yang mereka perlukan dari awal. Hal ini juga sering kali tidak praktis. Hal ini terjadi karena sumber daya mungkin dialokasikan dan tidak digunakan dalam jangka waktu lama. Selain itu, suatu proses yang membutuhkan sumber daya populer mungkin harus menunggu tanpa batas waktu, karena sumber daya tersebut mungkin selalu dialokasikan ke suatu proses, sehingga mengakibatkan kekurangan sumber daya . (Algoritma ini, seperti serialisasi token, dikenal sebagai *algoritma semua atau tidak sama sekali* .)
* Kondisi *tanpa perubahan siaran* juga mungkin sulit atau tidak mungkin dihindari karena suatu proses harus mampu memiliki sumber daya untuk jangka waktu tertentu, atau hasil pemrosesan mungkin tidak konsisten atau mungkin terjadi deraan. Namun, ketidakmampuan untuk menerapkan perubahan siaran dapat mengganggu algoritma *prioritas*. Perubahan siaran dari sumber daya yang "terkunci" umumnya menyiratkan baik-belakang, dan harus dihindari karena biaya bubungan-nya sangat mahal. Algoritma yang memungkinkan perubahsiaran mencakup algoritma bebas kunci dan bebas tunggu serta kontrol konkurensi optimis. Jika suatu proses mempunyai beberapa sumber daya dan meminta beberapa sumber daya lain yang tidak dapat segera dialokasikan padanya, maka kondisi tersebut dapat dihilangkan dengan melepaskan semua sumber daya yang ada pada proses tersebut.
* Kondisi terakhir adalah kondisi *menunggu melingkar*. Pendekatan yang menghindari menunggu melingkar termasuk menonaktifkan interupsi selama bagian penting dan menggunakan hierarki untuk menentukan pengurutan sebagian sumber daya. Jika tidak ada hierarki yang jelas, bahkan alamat memori sumber daya telah digunakan untuk menentukan pengurutan dan sumber daya diminta dalam urutan pencacahan yang meningkat. Solusi Dijkstra juga bisa digunakan.

### Penghindaran kebuntuan
Mirip dengan pencegahan kebuntuan, pendekatan penghindaran kebuntuan memastikan bahwa kebuntuan tidak akan terjadi dalam suatu sistem. Istilah "penghindaran kebuntuan" tampaknya sangat mirip dengan "pencegahan kebuntuan" dalam konteks linguistik, tetapi keduanya sangat jauh berbeda dalam konteks penanganan kebuntuan. Penghindaran kebuntuan tidak memaksakan kondisi apa pun seperti yang terlihat dalam pencegahan tetapi, di sini setiap permintaan sumber daya dianalisis secara cermat untuk melihat apakah permintaan tersebut dapat dipenuhi dengan aman tanpa menyebabkan kebuntuan.

Penghindaran kebuntuan mengharuskan sistem operasi diberikan informasi tambahan terlebih dahulu mengenai sumber daya mana yang akan diminta dan digunakan oleh suatu proses selama masa pakainya. Algoritma penghindaran kebuntuan menganalisis setiap permintaan dengan memeriksa bahwa tidak ada kemungkinan terjadinya kebuntuan di masa depan jika sumber daya yang diminta dialokasikan. Kelemahan dari pendekatan ini adalah diperlukannya informasi terlebih dahulu mengenai bagaimana sumber daya akan diminta di masa depan. Salah satu algoritma penghindaran kebuntuan yang paling banyak digunakan adalah algoritma Banker .

## Kebukaan
*Kebukaan* mirip dengan kebuntuan hanya saja keadaan proses yang terlibat dalam kebukaan terus berubah satu sama lain, tidak ada yang mengalami kemajuan.

Istilah ini diciptakan oleh Edward A. Ashcroft dalam makalah tahun 1975  sehubungan dengan pemeriksaan sistem pemesanan maskapai penerbangan. Kebukaaan adalah kasus khusus kekurangan sumber daya ; definisi umum hanya menyatakan bahwa proses tertentu tidak berjalan.

Kebukaan adalah risiko dengan beberapa algoritma yang mendeteksi dan memulihkan dari *kebuntuan*. Jika lebih dari satu proses mengambil tindakan, algoritma pendeteksi kebuntuan dapat dipicu berulang kali. Hal ini dapat dihindari dengan memastikan bahwa hanya satu proses (dipilih secara sewenang-wenang atau berdasarkan prioritas) yang mengambil tindakan.

## Referensi