Deadlock

Deadlock secara harfiah adalah kebuntuan, Di dalam sistem operasi berarti suatu kondisi di mana sekumpulan proses tidak dapat berjalan kembali atau tidak adanya komunikasi antar proses. Definisi lainnya yaitu sekumpulan proses yang terblok yang tiap proses tersebut memegang sumber daya dan menunggu untuk mendapatkan sumber daya yang dipegang oleh proses di dalam kumpulan tersebut.

IlustrasiDeadlock
Penyebab utama terjadinya deadlock adalah terbatasnya sumber daya yang akan digunakan oleh proses-proses. Tiap proses berkompetisi untuk memperebutkan sumber daya yang ada. Jadi deadlock berhubungan erat dengan tersedianya sumber daya dari komputer.

Penyebab utama terjadinya deadlock adalah terbatasnya sumber daya yang akan digunakan oleh proses-proses. Tiap proses berkompetisi untuk memperebutkan sumber daya yang ada. Jadideadlock berhubungan erat dengan tersedianya sumber daya dari
komputer.

Karakteristik Deadlock

Menurut Coffman(1971) ada empat kondisi yang dapat menyebabkan terjadinya deadloock. Keempat kondisi tersebut tidak dapat berdiri sendiri, saling mendukung.

1. Mutual Eksklusif: hanya ada satu proses yang bisa menggunakan sumber daya tersebut. Jika ada proses lain yang meminta sumber daya tersebut, maka proses itu harus menunggu sampai sumber daya dilepaskan.

2. Memegang dan Menunggu: proses yang meminta sumber daya sudah memegang sumber daya lainnya(meminta sumber daya tambahan).

3. Tidak ada Preemption: sumber daya yang sudah dialokasikan untuk sebuah proses tidak bisa diminta oleh proses lain. Sumber daya hanya bisa dilepaskan secara sukarela atau setelah proses tersebut selesai menggunakannya.

4. Circular Wait(menunggu berputar): kondisi seperti rantai yaitu saling menunggu smber daya yang dipakai oleh proses yang menunggu sumber daya tersebut.

Method untuk Menangani Deadlock

Pada prinsipnya kita dapat menangani deadlock dengan beberapa cara:

1. Menggunakan protokol untuk pencegahan atau penghindaran deadlock, memastikan bahwa sistem tidak akan memasuki kondisi deadlock.

2. Kita bisa mendeteksi terjadinya deadlock lalu memperbaiki.

3. Kita juga bisa mengabaikan deadlock, hal ini dilakukan pada sistem operasi berbasis UNIX.
Untuk memastikan sistem tidak memasuki deadlock, sistem dapat menggunakan pencegahan deadlock atau penghindaran deadlock. Penghindaran deadlock membutuhkan informasi tentang sumber daya yang mana yang akan suatu proses meminta dan berapa lama akan digunakan. Dengan informasi tersebut dapat diputuskan apakah suatu proses harus menunggu atau tidak. Hal ini disebabkan oleh keberadaan sumber daya, apakah ia sedang digunakan oleh proses lain atau tidak. Jika sebuah sistem tidak memastikan deadlock akan terjadi, dan juga tidak didukung dengan pendeteksian deadlock serta pencegahannya, maka kita akan sampai pada kondisi deadlock yang dapat berpengaruh terhadap performance system karena sumber daya
tidak dapat digunakan oleh proses sehingga proses-proses yang lain juga terganggu. Akhirnya sistem akan berhenti dan harus direstart.

Pencegahan Deadlock

Pencegahannya sebagai berikut:

1. Masalah Mutual Eksklusif

Kondisi ini tidak dapat dilarang, jika aksesnya perlu bersifat spesial untuk satu proses,maka hal ini harus didukung oleh kemampuan sistem operasi. Jadi diusahakan agar tidak menggunakan kondisi spesial tersebut sehingga sedapat mungkin deadlock dapat dihindari.

2. Masalah Kondisi Menunggu dan Memegang Penanggulangan deadlock

dari kondisi ini lebih baik dan menjanjikan, asalkan kita dapat memegang sumber daya untuk menunggu sumber daya lain, kita dapat mencegah deadlock. Caranya ialah dengan meminta semua sumber daya yang ia butuhkan sebelum proses berjalan. Tetapi masalahnya sebagian proses tidak mengetahui keperluannya sebelum ia berjalan. Jadi untuk mengatasi hal ini, kita dapat menggunakan algoritma bankir. Sistem operasi atau sebuah protokol mengatur hal ini. Hasil yang dapat terjadi adalah sumber daya lebih harus dispesifikasikan dan kelaparan sumber daya, atau proses yang membutuhkan sumber daya yang banyak harus menunggu sekian lama untuk mendapatkan sumber daya yang ia butuhkan.

3. Masalah tidak preemption

Hal ketiga ialah jangan sampai ada preemption pada sumberv daya yang telah dialokasikan. Untuk memastikan hal ini, kita dapat menggunakan protocol. Jadi jika sebuah proses meminta sumber daya yang tidak dapat ia penuhi saat itu juga, maka proses mengalami preempted. Dengan kata lain ada sumber daya dilepaskan dan diberikan ke proses yang menunggu, dan proses itu akan menunggu sampai kebutuhan sumber dayanya dipenuhi. Cara lain yaitu dengan mengecek apakah sumber daya yang dicari proses tersedia atau tidak. Jika ada maka langsung dialokasikan tetapi jika tidak maka kita cek apakah ada proses lain yang sedang menunggu sumber daya juga. Jika ya maka kita ambil sumber daya dari proses yang sedang menunggu tersebut dan memberikan kepada proses yang meminta sumber daya tersebut. Jika tidak tersedia juga maka proses tersebut harus menunggu. Dalam menunggu beberapa dari sumber dayanya dapat saja dipreempted jika ada proses yang memintanya. Cara ini efektif untuk proses yang menyimpan dalam memory atau register.

4. Masalah lingkaran tunggu

Masalah ini dapat ditangani oleh sebuah protocol yang menjaga agar sebuah proses tidak membuat lingkaran sikus yang dapat mengakibatkan deadlock dengan cara memberikan penomoran kepada sumber daya, dan bila suatu proses meminta sumber daya lagi maka ia hanya dapat meminta sumber daya yang nomornya lebih tinggi dari yang ia minta sebelumnya.

Penghindaran Deadlock

Algoritma Bankir Menurut Djikstra(1965) algoritma penjadwalan dapat menghindari deadlock dan algoritma penjadwalan tersebut dikenal dengan algoritma bankir. Algoritma ini dapat digambarkan, ada seorang bankir yang akan meminjamkan kepada peminjam-peminjamnya. Setiap peminjam memberikan batas pinjaman maksimum. Tentu saja bankir tahu bahwa peminjam tidak akan meminjam dana maksimum secara langsung melainkan bertahap. Bankir memprioritaskan kepada peminjam yang meminjam dana lebih banyak, sedangkan yang lain disuruh menunggu hingga peminjam yang lebih besar mengembalikan dananya, baru setelah itu ia meminjamkan kepada peminjam yang lain. Jadi algoritma bankir disini mempertimbangkan apakah permintaan proses sesuai dengan jumlah sumber daya yang ada dan sekaligus memperkirakan jumlah sumber daya yang mungkin diminta lagi. Jangan sampai ketika ada proses yang meminta sumber daya tetapi sumber dayanya habis atau tidak ada lagi jika tidak maka akan terjadi deadlock.

Secara umum algoritma bankir dibagi menjadi 4 struktur data:

1. Tersedia: jumlah sumber daya yang tersedia

2. Alokasi: jumlah sumber daya yang dialokasikan untuk setiap proses

3. Maksimum: jumlah permintaan sumber daya oleh proses

4. Kebutuhan: maksimum-alokasi(sisa sumber daya yang dibutuhkan oleh proses setelah dikurangi dengan yang dialokasikan)

Pemulihan Deadlock

1. Terminasi Proses

Abort semua proses yang deadlock

Metode ini akan mematahkan deadlock cycle, tetapi bisa saja proses-proses yang deadlock telah dikomputasi dalam waktu yang lama dan hasil-hasil komputasi parsial harus dibuang, sehingga ada kemungkinan harus dikomputasi ulang. Abort satu proses pada satu waktu sampai deadlock tereliminir. Metode ini sangat mungkin mendatangkan overhead, setelah setiap proses di-abort, algoritma pendeteksian deadlock harus diminta kembali untuk menentukan apakah masih ada proses-proses yang deadlock. Jika terminasi parsial digunakan, kita harus menentukan proses-proses deadlock yang mana yang harus diterminasi. Penentuan ini pada dasarnya berkaitan dengan ekonomi. Kita harus abort proses-proses yang terminasinya minimum cost. Sayangnya, minimum cost tidak ditentukan satu hal. Banyak faktor yang mempengaruhi pemilihan proses, mencakup:

- Apa prioritas dari proses

- Berapa lama proses telah mengkomputasi dan berapa lama lagi proses akan mengkomputasi  sebelum menyelesaikan tugasnya

-  Berapa banyak dan apa tipe dari sumber daya yang digunakan oleh proses
-  Berapa sumber daya lagi yang dibutuhkan proses supaya selesai
- Berapa banyak proses yang perlu diterminasi Apakah proses interactive atau batch

2. Preempt Sumber Daya

Mengeliminasi deadlock menggunakan preempt sumber daya berarti kita berturut-turut preempt beberapa sumber daya dari suatu proses dan memberikan sumber daya ini ke proses lain sampai deadlock cycle patah.

Pada preempt sumber daya

- Memilih korban

Seperti pada terminasi proses, kita harus menentukan sumber daya dan proses mana yang akan dipreempt dengan minimum cost. Faktor cost mencakup parameter-parameter seperti jumlah dari sumber daya yang ditahan proses-proses yang deadlock dan jumlah waktu dari proses yang telah digunakan selama eksekusinya.

- Rollback

Jika kita preempt sebuah sumber daya dari sebuah proses, proses tidak dapat berlanjut dengan eksekusi normal karena proses kehilangan beberapa sumber daya yang diperlukan. Kita harus rollback proses ke beberapa safe state dan restart dari state tersebut. Secara umum, sulit untuk menentukan safe state. Solusi termudah adalah dengan total rollback, abort proses, dan restart.

- Starvation

Dalam sebuah sistem di mana pemilihan korban berdasar primer pada faktor cost, dapat terjadi suatu proses tidak pernah menyelesaikan tugasnya karena suatu sumber daya selalu di-preempt pada proses yang sama. Kita harus memastikan bahwa sebuah proses dapat dipilih sebagai korban hanya dengan batasan waktu tertentu. Solusi pada umumnya adalah dengan menambahkan jumlah rollback ke dalam faktor cost.