Bab 23. Deadlock

23.1. Pendahuluan

Deadlock dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem operasi adalah kebuntuan proses. Jadi Deadlock ialah suatu kondisi dimana proses tidak berjalan lagi atau pun tidak ada komunikasi lagi antar proses. Deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses lain yang sedang menunggu sumber daya yang dipegang oleh proses tersebut. Dengan kata lain setiap proses dalam set menunggu untuk sumber yang hanya dapat dikerjakan oleh proses lain dalam set yang sedang menunggu.

 

23.4. Kondisi untuk Terjadinya Deadlock

Ada empat kondisi yang dapat menyebabkan terjadinya deadlock. Keempat kondisi tersebut tidak dapat berdiri sendiri, saling mendukung.

1. Mutual Eksklusif. Hanya ada satu proses yang boleh memakai sumber daya, dan proses lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut.
   
2. Memegang dan Menunggu. Proses yang sedang memakai sumber daya boleh meminta sumber daya lagi maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak dipakai oleh proses lain, hal ini dapat menyebabkan kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.
   
3. Tidak ada Preemption. Sumber daya yang ada pada sebuah proses tidak boleh diambil begitu saja oleh proses lainnya. Untuk mendapatkan sumber daya tersebut, maka harus dilepaskan terlebih dahulu oleh proses yang memegangnya, selain itu seluruh proses menunggu dan mempersilahkan hanya proses yang memiliki sumber daya yang boleh berjalan.
   
4. Circular Wait. Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.
   

Banyak cara untuk menanggulangi Deadlock

1. Mengabaikan masalah Deadlock.
   
2. Mendeteksi dan memperbaiki
   
3. Penghindaran yang terus menerus dan pengalokasian yang baik dengan menggunakan protocol untuk memastikan sistem tidak pernah memasuki keadaan Deadlock. Yaitu dengan Deadlock avoidance sistem untuk mendata informasi tambahan tentang proses mana yang akan meminta dan menggunakan sumber daya.
   
4. Pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya Deadlock dengan Deadlock prevention sistem untuk memasti- kan bahwa salah satu kondisi yang penting tidak dapat menunggu.
   
   
    

23.5. Mengabaikan Masalah Deadlock

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. Metode ini lebih dikenal dengan Algoritma Ostrich.

 

Dalam algoritma ini dikatakan bahwa untuk menghadapi Deadlock ialah dengan berpura-pura bahwa tidak ada masalah apa pun. Hal ini seakan-akan melakukan suatu hal yang fatal, tetapi sistem operasi Unix menanggulangi Deadlock dengan cara ini dengan tidak mendeteksi Deadlock dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak terjadi apa pun. Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga proses yang menjalankan proses melalui operator harus menunggu pada waktu tertantu dan mencoba lagi.

 

23.6. Mendeteksi dan Memperbaiki

Caranya ialah dengan cara mendeteksi jika terjadi Deadlock pada suatu proses maka dideteksi

sistem mana yang terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka

diadakan proses untuk memperbaiki dan menjadikan sistem berjalan kembali. 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 sistem karena sumber daya tidak dapat digunakan oleh proses sehingga proses-proses yang lain juga terganggu. Akhirnya sistem akan berhenti dan harus direstart.

Hal-hal yang terjadi dalam mendeteksi adanya Deadlock adalah:

1. Permintaan sumber daya dikabulkan selama memungkinkan.
   
2. Sistem operasi memeriksa adakah kondisi circular wait secara periodik.
   
3. Pemeriksaan adanya Deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah proses.
   
4. Memeriksa dengan algoritma tertentu.
   

 

Ada beberapa jalan untuk kembali dari Deadlock.

1. Lewat Preemption
   
   Dengan cara untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya pada proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh pemilik dari sumber daya tersebut tergantung dari sifat sumber daya itu sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak mungkin.
   
   
    
   Cara ini dapat dilakukan dengan memilih korban yang akan dikorbankan atau diambil sumber dayanya utuk sementara, tentu saja harus dengan perhitungan yang cukup agar waktu yang dikorbankan seminimal mungkin. Setelah kita melakukan preemption dilakukan pengkondisian proses tersebut dalam kondisi aman. Setelah itu proses dilakukan lagi dalam kondisi aman tersebut.
   
   
    
2. Lewat Melacak Kembali
   

Setelah melakukan beberapa langkah preemption, maka proses utama yang diambil sumber dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu dibutuhkan langkah untuk kembali pada keadaan aman dimana proses masih berjalan dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan sangat sulit menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara mematikan program tersebut lalu memulai kembali proses.

 

Meski pun sebenarnya lebih efektif jika hanya mundur beberapa langkah saja sampai Deadlock tidak terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke disk, sehingga saat terjadi Deadlock dapat mulai dari tempat terakhir penandaannya berada.

 

1. Lewat membunuh proses yang menyebabkan Deadlock
   

Cara yang paling umum ialah membunuh semua proses yang mengalami Deadlock. Cara ini paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun, untuk beberapa sistem, kita juga dapat membunuh beberapa proses saja dalam siklus Deadlock untuk menghindari Deadlock dan mempersilahkan proses lainnya kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber dayanya, dengan cara ini maka masalah pemilihan korban menjadi lebih selektif, sebab telah diperhitungkan beberapa kemungkinan jika si proses harus melepaskan sumber dayanya.

Kriteria seleksi korban ialah:

1. Yang paling jarang memakai prosesor
   
2. Yang paling sedikit hasil programnya
   
3. Yang paling banyak memakai sumber daya sampai saat ini
   
4. Yang alokasi sumber daya totalnya tersedkit
   
5. Yang memiliki prioritas terkecil
   

23.7. Menghindari Deadlock

Pada sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja. Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak (tidak terkena Deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:

1. Jangan memulai proses apa pun jika proses tersebut akan membawa kita pada kondisi Deadlock, sehingga tidak mungkin terjadi Deadlock karena ketika akan menuju Deadlock sudah dicegah.
   
2. Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan membawa kita pada suatu keadaan Deadlock
   

 

1. Algoritma Bankir
   

Menurut Dijkstra (1965) algoritma penjadwalan dapat menghindari Deadlock dan algoritma

penjadwalan itu lebih dikenal dengan sebutan algoritma bankir. Algoritma ini dapat digambarkan sebagai seorang bankir yang berurusan dengan kelompok orang yang meminta pinjaman. Jadi kepada siapa dia dapat memberikan pinjamannya. Dan setiap pelanggan memberikan batas pinjaman maksimum kepada setiap peminjam dana.

Tentu saja si bankir tahu bahwa si peminjam tidak akan meminjam dana maksimum yang mereka butuhkan dalam waktu yang singkat melainkan bertahap. Jadi dana yang ia punya lebih sedikit dari batas maksimum yang dipinjamkan. Lalu ia memprioritaskan yang meminta dana lebih banyak, sedangkan yang lain disuruh menunggu hingga peminta dana yang lebih besar itu mengembalikan pinjaman berikut bunganya, baru setelah itu ia meminjamkan pada peminjam yang menunggu.

Jadi algoritma bankir ini mempertimbangkan apakah permintaan mereka itu sesuai dengan jumlah dana yang ia miliki, sekaligus memperkirakan jumlah dana yang mungkin diminta lagi. Jangan sampai ia sampai pada kondisi dimana dananya habis dantidak dapat meminjamkan uang lagi. Jika demikian maka akan terjadi kondisi Deadlock. Agar kondisi aman, maka asumsi setiap pinjaman harus dikembalikan waktu yang tepat.

Secara umum algoritma bankir dapat dibagi menjadi empat struktur data:

1. Tersedia. Jumlah sumber daya/dana yang tersedia.
   
2. Maksimum. Jumlah sumber daya maksimum yang diminta oleh setiap proses.
   
3. Alokasi. Jumlah sumber daya yang dibutuhkan oleh setiap proses.
   
4. Kebutuhan. Maksimum-alokasi, sisa sumber daya yang dibutuhkan oleh proses setelah dikurangi dengan yang dialokasikan.
   

 

Kondisi Aman

Sebuah sistem dapat mengalokasikan sumber dayanya dalam kondisi aman kepada setiap proses. Maksud kondisi aman disini yaitu kita menggunakan algoritma aman setelah menggunakan algoritma Bankir.

Gambar 23.3. Tabel 1

Algoritma aman merupakan suatu algoritma yang membantu menentukan proses siapa dahulu yang dieksekusi.

• work and finish masing-masing sebuah vektor yang diinisialisasikan:
  
  work = tersedia
  
  finish[i] = FALSE untuk i= 1,2,3,..,n.
  
• jika finish[i] == FALSE, kebutuhan i <= work else ke tahap 04
  
• work = work + Alokasi
  
  finish [i] = TRUE
  
  ke tahap 02
  
• jika finish[i]==TRUE untuk semua i,
  
  maka sistem dalam keadaan aman.
  

Gambar 23.4. Tabel 2

 

23.8. Pencegahan Deadlock

Jika pada awal bab ini kita membahas tentang ke-empat hal yang menyebabkan terjadinya

Deadlock. Maka pada bagian ini, kita akan membahas cara menanggulangi keempat penyebab Deadlock itu, sehingga dengan kata lain kita mengadakan pencegahan terhadap Deadlock.

1. Masalah Mutual Eksklusif Kondisi ini tidak dapat dilarang, jika aksesnya perlu bersifat special untuk satu proses, maka hal ini harus di dukung oleh kemampuan sistem operasi. Jadi diusahakan agar tidak mempergunakan 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 menahan proses yang memegang sumber daya untuk tidak menunggu sumber daya laun, 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 banker
   
3. 
   Masalah tidak ada Preemption Hal ketiga ialah jangan sampai ada preemption pada sumber daya yang telah dialokasikan. Untuk memastikan hal ini, kita dapat menggunakan protokol. Jadi jika sebuah proses meminta sumber daya yang tidak dapat dipenuhi saat itu juga, maka proses mengalami preempted.
   
4. Masalah Circular Wait Masalah ini dapat ditangani oleh sebuah protokol yang menjaga agar sebuah proses tidak membuat lingkaran siklus yang dapat mengakibatkan Deadlock.
   
   
    
   
    

[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems

Concepts. Seventh Edition. John Wiley & Sons.