Pengertian Deadlock

Deadlock adalah suatu keadaan dimana dua buah proses atau lebih saling menunggu proses yang lain untuk melepaskan resource yang sedang dipakai. karena ini adalah suatu sistem yang selalu nurut dengan algoritma yang dibuat maka sebelum kondisi terpenuhi, proses-proses tersebut akan terus mengalami deadlock

Dalam kasus deadlock Karena beberapa proses itu saling menunggu, maka tidak terjadi kemajuan dalam kerja proses-proses tersebut. Deadlock adalah masalah yang biasa terjadi ketika banyak proses yang membagi sebuah resource yang hanya boleh dirubah oleh satu proses saja dalam satu waktu. Di kehidupan nyata, deadlock dapat digambarkan dalam gambar berikut.Pada gambar diatas, deadlock dianalogikan sebagai dua antrian mobil yang akan menyeberangi jembatan. Dalam kasus diatas, antrian di sebelah kiri menunggu antrian kanan untuk mengosongkan jembatan (resource), begitu juga dengan antrian kanan. Akhirnya tidak terjadi kemajuan dalam kerja dua antrian tersebut.Misal ada proses A mempunyai resource X, proses B mempunyai resource Y. Kemudian kedua proses ini dijalankan bersama, proses A memerlukan resource Y dan proses B memerlukan resource X, tetapi kedua proses tidak akan memberikan resource yang dimiliki sebelum proses dirinya sendiri selesai dilakukan. Sehingga akan terjadi tunggu-menunggu.

 

Karakteristik Deadlock :
Karakteristik-karakteristik ini harus dipenuhi keempatnya untuk terjadi deadlock. Namun, perlu diperhatikan bahwa hubungan kausatif antara empat karakteristik ini dengan terjadinya deadlock adalah implikasi. Deadlock mungkin terjadi apabila keempat karakteristik terpenuhi.

Empat kondisi tersebut adalah:

  1. Mutual Exclusion : Kondisi yang pertama adalah mutual exclusion yaitu proses memiliki hak milik pribadi terhadap sumber daya yang sedang digunakannya. Jadi, hanya ada satu proses yang menggunakan suatu sumber daya. Proses lain yang juga ingin menggunakannya harus menunggu hingga sumber daya tersebut dilepaskan oleh proses yang telah selesai menggunakannya. Suatu proses hanya dapat menggunakan secara langsung sumber daya yang tersedia secara bebas.
  2. Hold and Wait : Kondisi yang kedua adalah hold and wait yaitu beberapa proses saling menunggu sambil menahan sumber daya yang dimilikinya. Suatu proses yang memiliki minimal satu buah sumber daya melakukan request lagi terhadap sumber daya. Akan tetapi, sumber daya yang dimintanya sedang dimiliki oleh proses yang lain. Pada saat yang sama, kemungkinan adanya proses lain yang juga mengalami hal serupa dengan proses pertama cukup besar terjadi. Akibatnya, proses-proses tersebut hanya bisa saling menunggu sampai sumber daya yang dimintanya dilepaskan. Sambil menunggu, sumber daya yang telah dimilikinya pun tidak akan dilepas. Semua proses itu pada akhirnya saling menunggu dan menahan sumber daya miliknya.
  3. No Preemption : Kondisi yang selanjutnya adalah no preemption yaitu sebuah sumber daya hanya dapat dilepaskan oleh proses yang memilikinya secara sukarela setelah ia selesai menggunakannya. Proses yang menginginkan sumber daya tersebut harus menunggu sampai sumber daya tersedia, tanpa bisa merebutnya dari proses yang memilikinya.
  4. Circular Wait :  Kondisi yang terakhir adalah circular wait yaitu kondisi membentuk siklus yang berisi proses-proses yang saling membutuhkan. Proses pertama membutuhkan sumber daya yang dimiliki proses kedua, proses kedua membutuhkan sumber daya milik proses ketiga, dan seterusnya sampai proses ke n-1 yang membutuhkan sumber daya milik proses ke n. Terakhir, proses ke n membutuhkan sumber daya milik proses yang pertama. Yang terjadi adalah proses-proses tersebut akan selamanya menunggu.

sebagai contoh dalam kasus Dining Philosohers Problem

Dining Philosohers Problem dapat diilustrasikan sebagai berikut, terdapat lima orang filsuf yang sedang duduk mengelilingi sebuah meja. Terdapat lima mangkuk mie di depan masing-masing filsuf dan satu sumpit di antara masing-masing filsuf. Para filsuf menghabiskan waktu dengan berpikir (ketika kenyang) dan makan (ketika lapar). Ketika lapar, filsuf akan mengambil dua buah sumpit (di tangan kiri dan tangan kanan) dan makan. Namun adakalanya, hanya diambil satu sumpit saja. Jika ada filsuf yang mengambil dua buah sumpit, maka dua filsuf di samping filsuf yang sedang makan harus menunggu sampai sumpit ditaruh kembali.

Dalam proses perancangan perangkat lunak simulasi ini, penulis mengambil beberapa asumsi, yaitu:

  1. Hanya terdapat 5 (lima) orang filsuf dalam proses simulasi.

  2. Masing-masing filsuf memiliki kondisi sebagai berikut:

    1. Kenyang.

Filsuf akan berada dalam kondisi kenyang sesaat setelah makan.

    1. Lapar.

Beberapa saat setelah makan, filsuf akan merasa lapar.

    1. Mati.

Beberapa saat setelah merasa lapar dan apabila filsuf belum juga mendapatkan sumpit, maka filsuf akan mati.

  1. Aksi yang dapat dilakukan oleh masing-masing filsuf, yaitu:

    1. Berpikir.

Filsuf akan berpikir apabila filsuf berada dalam kondisi kenyang.

    1. Cari Sumpit.

Filsuf akan mencari dan mengambil sumpit di kedua tangannya apabila filsuf berada dalam kondisi lapar.

    1. Makan

Apabila filsuf mendapatkan dua sumpit di kedua tangannya, maka filsuf akan makan hingga kenyang. Setelah kenyang, filsuf kembali berpikir.

  1. Di dalam perangkat lunak, kondisi filsuf di atas dirancang penulis secara matematis menjadi waktu-A dan waktu-B.

    1. Waktu-A, yaitu waktu yang diperlukan untuk mengubah kondisi filsuf dari kenyang menjadi lapar (dalam sekon).

    2. Waktu-B, yaitu waktu yang diperlukan untuk mengubah kondisi filsuf dari lapar menjadi mati (dalam sekon).

    3. Masa Hidup, yaitu masa hidup filsuf pada saat itu (dalam sekon). Maksimum masa hidup adalah sebesar nilai waktu-A + waktu-B. Masa hidup filsuf akan bertambah ketika filsuf sedang makan dan akan senantiasa berkurang di luar aksi itu.

Ketiga komponen ini menjadi ukuran matematis kondisi filsuf di dalam perangkat lunak. Misalnya, seorang filsuf memiliki waktu-A = 10 sekon, waktu-B = 8 sekon dan masa hidup = 12 sekon. Karena masa hidup filsuf adalah 12 sekon atau lebih besar 4 sekon daripada waktu-B, maka dapat dihitung bahwa 4 sekon kemudian, filsuf akan mulai merasa lapar dan mulai mencari sumpit. Bila filsuf mendapatkan dua sumpit di kedua tangannya, maka filsuf akan mulai memakan mie yang ada di depannya. Ketika sedang makan, masa hidup filsuf akan bertambah kembali. Filsuf tidak akan berhenti makan hingga filsuf berada dalam kondisi kenyang atau masa hidupnya mencapai nilai maksimum yaitu 18 sekon (waktu-A + waktu-B). Setelah itu, filsuf akan berpikir dalam 10 sekon berikutnya, sebelum merasa lapar dan mencari sumpit lagi. Apabila filsuf merasa lapar dan tidak mendapatkan sumpit dalam waktu 8 sekon (waktu-B), maka masa hidup filsuf akan menjadi nol dan filsuf akan mati. Untuk mendapatkan sumpit, filsuf harus menunggu apabila sumpit sedang dipakai oleh filsuf di sampingnya. Dalam kondisi itu, masa hidup filsuf akan terus berkurang.

  1. Untuk menghindari kondisi deadlock, penulis menyediakan 3 cara yang dapat dipilih, yaitu:

    1. Solusi-A, yaitu mengizinkan paling banyak 4 orang filsuf yang duduk bersama-sama pada satu meja.

    2. Solusi-B, yaitu mengizinkan seorang filsuf mengambil sumpit hanya jika kedua sumpit itu ada.

    3. Solusi-C, yaitu filsuf pada nomor ganjil mengambil sumpit kiri dulu baru sumpit kanan, sedangkan filsuf pada nomor genap mengambil sumpit kanan dulu baru sumpit kiri. Solusi ini disebut solusi asimetrik.

Untuk dapat lebih memahami proses yang terjadi, perhatikan contoh illustrasi berikut ini. Misalkan properti 5 orang filsuf dalam simulasi adalah sebagai berikut:

Tabel 3.1 Tabel Properti Filsuf

Waktu-A (sekon)

Waktu-B (sekon)

Kondisi Awal (sekon)

Filsuf-1

7

10

15

Filsuf-2

5

4

4

Filsuf-3

6

11

14

Filsuf-4

5

13

11

Filsuf-5

6

12

18

Dari tabel dapat diketahui kondisi masing-masing filsuf, yaitu filsuf-1 berada dalam kondisi kenyang karena kondisi awal 15 sekon berada di atas waktu-B yang hanya 10 sekon (filsuf-1 akan merasa lapar dan mencari sumpit 5 sekon kemudian). Filsuf-2 berada dalam kondisi lapar karena kondisi awal 4 sekon = waktu-B, filsuf-3 berada dalam kondisi kenyang, filsuf-4 berada dalam kondisi lapar dan filsuf-5 berada dalam kondisi kenyang. Kondisi awal problema dining philosophers dapat digambarkan dengan bagan illustrasi sebagai berikut:

Gambar 3.1 Bagan illustrasi kondisi awal simulasi

Proses simulasi adalah sebagai berikut:

Pada saat t = 1 sekon, filsuf-1, filsuf-3 dan filsuf-5 kenyang dan sedang berpikir, sedangkan filsuf-2 dan filsuf-4 lapar dan mendapatkan sumpit di tangan kiri. Pada saat t = 2 sekon, filsuf-2 dan filsuf-4 mendapatkan 2 sumpit dan mulai makan, sedangkan filsuf-1, filsuf-3 dan filsuf-5 masih kenyang dan sedang berpikir. Pada saat t = 3 sekon, filsuf-3 merasa lapar (karena masa hidup filsuf-3 saat ini = waktu-B yaitu 11 sekon) dan mulai mencari sumpit, tetapi tidak mendapatkan sumpit karena sumpit di sebelah kiri digunakan oleh filsuf-4 dan sumpit di sebelah kanan digunakan oleh filsuf-2. Bagan illustrasinya adalah sebagai berikut:

Gambar 3.2 Bagan illustrasi kondisi simulasi saat t=3 sekon

Pada saat t = 5 sekon, filsuf-1 merasa lapar (karena masa hidup filsuf-1 saat ini = waktu-B yaitu 10 sekon) dan mencari sumpit. Filsuf-1 mendapatkan sumpit di tangan kanan. Pada saat t = 6 sekon, filsuf-5 merasa lapar (karena masa hidup filsuf-5 saat ini = waktu-B yaitu 12 sekon) dan mencari sumpit. Filsuf-5 tidak mendapatkan sumpit. Pada saat t = 9 sekon, filsuf-2 kenyang (karena masa hidupnya sudah mencapai nilai maksimum, yaitu 9 sekon = waktu-A + waktu-B) dan mulai berpikir. Filsuf-3 mendapatkan sumpit di tangan kanan. Pada saat t = 10 sekon, filsuf-1 mendapatkan 2 sumpit dan mulai makan. Pada saat t = 11 sekon, filsuf-4 kenyang dan mulai berpikir. Filsuf-5 mendapatkan sumpit di tangan kanan. Pada saat t = 12 sekon, filsuf-3 mendapatkan 2 sumpit dan mulai makan. Bagan illustrasinya adalah sebagai berikut:

Gambar 3.3 Bagan illustrasi kondisi simulasi saat t=12 sekon

Proses simulasi akan berlanjut sesuai dengan prosedur. Simulasi hanya akan berhenti apabila terjadi kondisi deadlock. Kondisi deadlock dalam simulasi dining philosophers problem terjadi apabila pada satu saat, semua filsuf merasa lapar secara bersamaan dan semua filsuf mengambil sumpit di tangan kiri. Pada saat filsuf akan mengambil sumpit di tangan kanan, maka terjadilah kondisi deadlock, karena semua filsuf akan saling menunggu sumpit di sebelah kanannya (kondisi yang tidak akan pernah terjadi). Untuk kasus deadlock, perhatikan kondisi berikut:

Tabel 3.2 Tabel Properti Filsuf untuk Kasus Deadlock

Waktu-A (sekon)

Waktu-B (sekon)

Kondisi Awal (sekon)

Filsuf-1

17

12

27

Filsuf-2

5

3

2

Filsuf-3

15

10

25

Filsuf-4

6

5

5

Filsuf-5

20

5

20

Bagan illustrasi kondisi awal adalah sebagai berikut:

Gambar 3.4 Bagan illustrasi kondisi awal (kasus deadlock)

Pada saat t = 1 sekon, filsuf-2 dan filsuf-4 lapar dan mendapatkan sumpit di tangan kiri, sedangkan filsuf-1, filsuf-3 dan filsuf-5 kenyang dan sedang berpikir. Pada saat t = 2 sekon, filsuf-2 dan filsuf-4 mendapat 2 sumpit dan mulai makan. Pada saat t = 10 sekon, filsuf-2 dan filsuf-4 kenyang dan mulai berpikir. Pada saat t = 15 sekon, semua filsuf secara bersamaan lapar dan mengambil sumpit di tangan kiri. Pada saat ini, telah terjadi kondisi deadlock, karena semua filsuf yang sedang mengenggam sumpit di tangan kiri menunggu sumpit di sebelah kanan. Semua filsuf akan saling menunggu. Bagan illustrasi kondisi deadlock adalah sebagai berikut:

Gambar 3.5 Bagan illustrasi kondisi deadlock

Dengan input properti filsuf dan kondisi awal yang sama, kondisi deadlock yang terjadi dapat dihindari dengan memilih satu dari tiga solusi berikut:

  1. Solusi-A, yaitu mengizinkan paling banyak 4 orang filsuf yang duduk bersama-sama pada satu meja. Tidak akan terjadi kondisi deadlock apabila terdapat kurang dari 4 orang filsuf yang duduk bersama-sama mengelilingi meja dengan 5 tempat duduk (satu filsuf dianggap mati).

  2. Solusi-B, yaitu mengizinkan seorang filsuf mengambil sumpit hanya jika kedua sumpit itu ada. Apabila semua filsuf lapar secara bersamaan, maka hanya 2 orang filsuf yang dapat makan, karena filsuf mengambil 2 sumpit pada saat yang bersamaan.

  3. Solusi-C, yaitu solusi asimetrik. Filsuf pada nomor ganjil mengambil sumpit kiri dulu baru sumpit kanan, sedangkan filsuf pada nomor genap mengambil sumpit kanan dulu baru sumpit kiri. Apabila semua filsuf lapar secara bersamaan, cara pengambilan dengan solusi asimetrik akan mencegah semua filsuf mengambil sumpit kiri secara bersamaan, sehingga kondisi deadlock dapat dihindari.

Avatar of Sam

About

Mahasiswa di Jurusan Teknik Informatika Univ Brawijaya

Avatar of Sam

About Sam

Mahasiswa di Jurusan Teknik Informatika Univ Brawijaya

Leave a Reply