Deadlock

Deadlock

1.       Definisi deadlock

2.       Model deadlock

3.       Syarat terjadinya deadlock dan Penyebab deadlock

4.       Menghindari deadlock

5.       Mencegah deadlock

6.       Mengatasi deadlock

7.       Algoritma deadlock

1. Definisi deadlock

Deadlock ialah suatu kondisi permanen dimana proses tidak berjalan lagi ataupun tidak ada komunikasi lagi antar proses. Proses dikatakan deadlock jika proses menunggu suatu kejadian tertentu yang tidak pernah terjadi. Sekumpulan proses dikatakan deadlock jika setiap proses yang  berada dikumpulan itu menunggu suatu kejadian yang  dapat dilakukan proses lain yang juga berada dikumpulan itu. Deadlock terjadi ketika proses-proses mengakses sumber daya secara ekslusif. Semua deadlock yang terjadi melibatkan persaingan untuk memperoleh sumber daya eksklusif oleh 2 proses atau lebih.

Resource (sumber daya) adalah komoditas/bahan yang dibutuhkan oleh proses untuk dapat melakukan task tertentu. Tipe-tipe resource: Reusable resource dan Consumable resource.

Sumber daya bersifat:

–          Preemptible: masih boleh diambil dari proses yg sedang memakainya tanpa memberi efek apapun  pada proses tersebut. Contoh: memorycontoh: CPU, memori utama.

–          non-preemptible: tidak boleh diambil dari proses yg sedang memakainya. Contoh: printer. Ada potensi menyebabkan deadlock contoh: tape drives

Sumber daya bisa digunakan secara:

–           Bersama, oleh beberapa proses

–           Terdedikasi, secara eksklusif oleh satu proses

2. Model deadlock

Pada sistem terdapat beberapa sumber daya (resource) yang digunakan untuk proses-proses untuk menyelesaikan task. Sumber daya yang pada sistem terdiri dari tipe resource CPU cycle, ruang memori, perangkat I/O yang disebut dengan tipe sumber daya R1, R2, . . ., Rm. Setiap tipe sumber daya Ri mempunyai beberapa anggota Wi. Setiap proses yang menggunakan sumber daya menjalankan urutan operasi sebagai berikut:

•  Meminta (request) : meminta sumber daya

•  Memakai (use) : memakai sumber daya

•  Melepaskan (release) : melepaskan sumber daya

Contoh Deadlock Sederhana

Pada gambar diatas, tidak ada yang dapat maju karena keduanya memperebutkan jalan yang sama ( yang dilingkari ), demikian juga deadlock saat semua proses memperebutkan sumber yang sama. Contoh lain yang dapat merepresentasikan deadlock ialah jembatan gantung sebagai berikut :

disadur dari Modern Operating Systems , Tanenbaum , 1992

sehingga orang yang ada di sebelah kiri jembatan tidak dapat melaju sebab terjadi deadlock di tengah jembatan ( bagian yang dilingkari ). Contoh lain ialah di persimpangan jalan jalan berikut ini:

disadur dari buku Stallings, William, “Operating Systems — Fourth Edition”, Prentice Hall, 2001

Dalam kasus ini setiap mobil bergerak sesuai nomor yang ditentukan,tetapi tanpa pengaturan yang benar, maka setiap mobil akan bertemu pada satu titik yang permanen( yang dilingkari )atau bisa dikatakan bahwa setiap mobil tidak bisa meanjutkan perjalanan lagi atau dengan kata lain terjadi deadlock. Contoh lain pada proses yang secara umum terdiri dari tiga tahap, yaitu untuk meminta, memakai, dan melepaskan sumber daya yang di mintanya. Contoh kode-nya :

public class Proses {

public synchronized void getA() {

//proses untuk mendapat sumber daya a

}

public synchronized void getB(){

//proses untuk mendapat sumber daya b

}

public void releaseA(){

//proses untuk melepaskan sumber daya a

}

public void releaseB(){

//proses untuk melepaskan sumber daya b

}

}

public class Coba {

public static void main(String [] args) {

Proses P = new Proses();

Proses Q = new Proses();

P.getA();

Q.getB();

P.getB();

Q.getA();

}

}

tanpa adanya perintah untuk mereleased artinya saat P mendapatkan A dan Q mendapatkan B, tetapi tidak dilepaskan, maka saat P minta B dan Q minta A, maka keduanya akan saling menunggu hingga salah satu melepaskan sumber dayanya, sedangkan kebutuhan P ada pada Q dan Q ada pada P, sehingga terjadi deadlock. Secara umum kejadian ini dapat mudah terjadi dalam pemrograman multi-thread. Sebab ada kemungkinan lebih besar untuk menggunakan sumber daya bersama.

3. Syarat terjadinya deadlock dan Penyebab deadlock

Menurut Coffman( 1971 ) ada empat kondisi yang bisa mengakibatkan terjadinya deadlock, yaitu :

1.       Mutual Eksklusif (Mutual Exclusion): 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 (Hold and Wait): 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 bisa menyebabkan kelaparan sumber daya sebab bisa saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama

3.       Tidak ada Preemption (Non-pre-emptive): 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: adanya kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.

Ketiga syarat pertama merupakan syarat perlu (necessary conditions) bagi terjadinya  deadlock.  Keberadaan  deadlock selalu berarti terpenuhi kondisi-kondisi diatas, tak mungkin terjadi deadlock bila tidak ada ketiga kondisi itu.  Deadlock terjadi berarti terdapat ketiga kondisi itu, tetapi adanya ketiga kondisi itu belum berarti terjadi deadlock. Deadlock baru benar-benar terjadi bila syarat keempat terpenuhi.  Kondisi keempat merupakan keharusan bagi terjadinya peristiwa deadlock.  Bila salah satu saja dari kondisi tidak terpenuhi maka deadlock tidak terjadi.

4. Menghindari deadlock

Metode alternatif untuk menghindari deadlock adalah digunakan informasi tambahan tentang bagaimana sumber daya diminta.  Misalnya pada sistem dengan satu tape drive dan satu printer, proses P pertama meminta tape drive dan kemudian printer sebelum melepaskan kedua sumber daya tersebut.  Sebaliknya proses  Q pertama meminta printer kemudian tape drive.  Dengan mengetahui urutan permintaan dan pelepasan sumber daya untuk setiap proses, dapat diputuskan bahwa untuk setiap permintaan apakah proses harus menunggu atau tidak.  Setiap permintaan ke sistem harus dipertimbangkan apakah sumber daya tersedia, sumber daya sedang dialokasikan untuk proses dan permintaan kemudian serta pelepasan oleh proses untuk menentukan apakah permintaan dapat dipenuhi atau harus menunggu untuk menghindari deadlock.

Model yang sederhana dan sangat penting dibutuhkan adalah setiap proses menentukan jumlah maksimum sumber daya dari setiap tipe yang mungkin diperlukan.  Algoritma  deadlock avoidance  secara dinamis memeriksa status sumber daya yang dialokasikan untuk menjamin tidak pernah terjadi kondisi menunggu sirkular.  Status alokasi sumber daya ditentukan oleh jumlah sumber daya yang tersedia dan yang dialokasikan dan maksimum permintaan oleh proses-proses. Untuk penghindaran  deadlock diperlukan pengertian mengenai state selamat (safe state) dan state tak selamat (unsafe state). Safe state: sistem dapat mengalokasikan resource untuk tiap-tiap proses dan mencegah terjadinya deadlock. Unsafe state: sistem tidak dapat mengatur alokasi resource untuk tiap proses. Jika sistem berada dalam kondisi safe state, berarti tidak terjadi deadlock. Jika dalam kondisi unsafe state, kemungkinan bisa terjadi deadlock.

5. Mencegah deadlock

Metode ini berkaitan dengan pengkondisian sistem agar menghilangkan kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih dipandang dari sudut tercegahnya deadlock.

Metode ini sering menghasilkan utilisasi sumber daya yang buruk. Pencegahan deadlock

merupakan metode yang banyak dipakai. Untuk mencegah deadlock dilakukan dengan meniadakan salah satu dari syarat perlu sebagai berikut :

1.       Mencegah Mutual Exclusion

Mutual exclusion benar-benar tak dapat dihindari. Hal ini dikarenakan tidak ada sumber daya yang dapat digunakan bersama-sama, jadi sistem harus membawa sumber daya yang tidak dapat digunakan bersama-sama.

2.       Mencegah kondisi hold-and-wait

o   Proses harus meminta sumber daya sebelum mulai àtidak bisa mulai sebelum semua sumber daya yg dibutuhkan diperoleh.

o   Masalah:

• Sumber daya yg diperlukan mungkin tdk diketahui pada saat proses mulai

• Mengikat sumber daya yg mungkin akan digunakan oleh proses lain

o   Alternatif:

• Jika proses membutuhkan suatu sumber daya, lepaskan dulu semua sumber daya yg telah diperolehnya, setelah itu minta kembali semua yg dibutuhkan

3.       Mencegah kondisi no-preemption

o   Jika proses yg sdg mengakses sumber daya meminta sumber daya lain yg tdk bisa segera dialokasikan utknya, maka semua sumber daya yg sdg dialokasikan pd proses tsb harus dilepas.

o   Sumber daya yg di-preempted ditambahkan ke sumber daya yg ditunggu oleh proses

o   Proses akan di-restart hanya jika proses tsb dpt memperoleh semua sumber daya yg dibutuhkan

o   Masalah: dapat menimbulkan starvation

4.       Mencegah Kondisi Menunggu Sirkular

o   Sistem mempunyai total permintaan global untuk semua tipe sumber daya. Proses dapat meminta proses kapanpun menginginkan, tapi permintaan harus dibuat terurut secara numerik. Setiap proses yang membutuhkan sumber daya dan memintanya maka nomor urut akan dinaikkan. Cara ini tidak akan menimbulkan siklus. Masalah yang timbul adalah tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.

Kesimpulan:

Syarat	Langkah	Kelemahan
Mutual Exclusion	Spooling sumber daya	Dapat menyebabkan chaos
Hold and Wait	Meminta sumber dayadi awal	Sulit memperkirakan di awal dan tidak optimal
No Pre-emptive	Mengambil sumberdaya di tengah proses	Hasil proses tidak akan baik
Circular Wait	Penomoran permintaansumber daya	Tidak ada penomoran yangmemuaskan semua pihak

6. Mengatasi  deadlock

Ada dua metode dalam mengatasi deadlock, yaitu:

1.       Metode pencegahan deadlock

–          Tiap proses harus meminta semua sumber daya yang diperlukan secara sekaligus dan tidak berlanjut sampai semuanya diberikan.

–          Jika proses sedang memegang sumberdaya tertentu, untuk permintaan berikutnya proses harus melepas dulu sumberdaya yang dipegangnya.

2.       Penghindaran deadlock

–          Menghindari deadlock dengan cara hanya memberi akses ke permintaan sumber daya yang tidak mungkin menimbulkan deadlock.

–           Jika tidak aman (memungkinkan timbulnya deadlock), proses yang meminta di suspend sampai suatu waktu permintaannya aman diberikan.

–          Agar dapat mengevaluasi safe-nya state sistem, penghindaran deadlock mengharuskan semua proses menyatakan jumlah kebutuhan sumber daya maksimum sebelum eksekusi.

–          Begitu eksekusi dimulai, tiap proses meminta sumber daya saat diperlukan sampai batas maksimum yang  dinyatakan di awal.

–           Proses-proses yang menyatakan kebutuhan sumber daya melebihi kapasitas total sistem tidak dapat dieksekusi.

7.       Algoritma deadlock

Algoritma Graf Alokasi Sumber Daya untuk Mencegah Deadlock

Algoritma ini dapat dipakai untuk mencegah deadlock jika sumber daya hanya memiliki satu instans. Pada algoritma ini ada komponen tambahan pada sisi yaitu claimed edge. Sama halnya dengan sisi yang lain, claimed edge menghubungkan antara sumber daya dan vertex.

Claimed edge Pi -> Rj berarti bahwa proses Pi akan meminta sumber daya Rj pada suatu waktu. Claimed edge sebenarnya merupakan sisi permintaan yang digamabarkan sebagai garis putus-putus. Ketika proses Pi memerlukan sumber daya Rj, claimed edge diubah menjadi sisi permintaan. Dan setelah proses Pi selesai menggunakan Rj, sisi alokasi diubah kembali menjadi claimed edge.

Dengan algoritma ini bentuk perputaran pada graf tidak dapat terjadi. Sebab untuk setiap perubahan yang terjadi akan diperiksa dengan algoritma deteksi perputaran. Algoritma ini memerlukan waktu n ² dalam mendeteksi perputaran dimana n adalah jumlah proses dalam sistem.

Jika tidak ada perputaran dalam graf, maka sistem berada dalam status aman. Tetapi jika perputaran ditemukan maka sistem berada dalam status tidak aman. Pada saat status tidak aman ini, proses Pi harus menunggu sampai permintaan sumber dayanya dipenuhi.

Algoritma Ostrich:

Jangan lakukan apa pun, cukup restart sistem (ostrich: benamkan kepala ke pasir, dan pura2 tidak ada masalah sama sekali)

Dilakukan jika:

• Deadlock jarang terjadi
• algoritma deadlock lainnya biayanya lebih tinggi

Diterapkan oleh Windows dan UNIX

Trade off

• kenyamanan (convenience)  vs keakuratan (correctness)

Algoritma Banker’s

• Diketahui:
  • maxc[i, j] = maksimum klaim utk Rj oleh pi
  • alloc[i, j] = banyak unit Rj yg dialokasikan ke pi
  • Dapat menghitung banyaknya unit Rj yg tersedia:
    • avail[j] = cj – ∑0≤i<n alloc[i,j]
    • Menentukan jika state aman/tidak berdasarkan informasi ini
    • Salin tabel alloc[i,j] ke alloc’[i,j]
    • Jika diketahui C, maxc, and alloc’, hitung vektor sumber daya yg tersedia
    • Hitung pi: maxc[i,j] – alloc’[i,j] ≤ avail[j] untuk 0 ≤ j < m and 0 ≤ i < n
    • Jika pi tidak ada, unsafe state
    • Jika alloc’[i,j]=0 untuk semua i dan j, safe state
    • Set alloc’[i,j] ke 0; dealokasi semua sumber daya yg dimiliki pi; kembali ke langkah 2

Algoritma Safety

• Let Work and Finish be vectors of length m and n,respectively. Initialize:

Work := Available // resource yang free

Finish [i] = false for i = 1,3, …, n.

• Find and i such that both: // penjadwalan alokasi resource

(a) Finish [i] = false // asume, proses belum complete

(b) Needi £ Work // proses dapat selesai, ke step 3

If no such i exists, go to step 4.

• Work := Work + Allocationi // proses dapat selesai

Finish[i] := true

go to step 2.

• If Finish [i] = true for all i, then the system is in a safe state.
• Terdapat 3 proses: n = 3, 1 resource: m = 1
• Jumlah resource m = 12.

 

 

 

Referensi:

Klik untuk mengakses Teori9.pdf

Klik untuk mengakses SO7.pdf

http://www.idonbiu.com/2009/12/algoritma-graf-alokasi-sumber-daya.html

Klik untuk mengakses Konsep_Graph.pdf

http://journal.amikom.ac.id/index.php/KIDA/article/view/3353/1342

Klik untuk mengakses Pert-16-Ch06-Allocation-Denial-Dining-Philosopher-20101103.pdf

http://kisah-kasih-ibu.blogspot.com/2009/09/deadlock.html
http://ofy.parungky.web.ugm.ac.id/?p=75
http://journal.amikom.ac.id/index.php/KIDA/article/viewFile/3294/1355

Klik untuk mengakses Chapter6%20-%20Deadlock.pdf

Klik untuk mengakses 6.Deadlock.pdf

http://ikc.unimal.ac.id/umum/ibam/ibam-os-html/i32.html