Deadlock (Sistem Informasi)

I.          Pengertian Deadlock

                 Deadlock adalah Suatu kondisi di mana sekumpulan proses tidak dapat berjalan kembali atau tidak adanya komunikasi antar proses. Deadlock merupakan kumpulan proses yang terblok yang tiap proses tersebut memegang sumber daya dan menunggu untuk mendapatkan sumber daya yang dipegang oleh proses di dalam kumpulan tersebut.

Model Deadlock

Bila beberapa proses ingin menggunakan resource yang sama dalam satu waktu, maka hal ini akan berpotensi menimbulkan deadlock.

Ø  Resources

Ada 2 jenis yaitu

a.       Preempatable

-          Preempatable resource adalah resource yang dapat diambil dari proses yang memilikinya tanpa menimbulkan efek. Sistemnya terdiri dari : user memory (32MB), 1 pointer, dan 2 proses cetak (@30MB)

-          Proses A request printer dan mendapatkannya sebelum komputasinya selesai (lewat batas waktu), A keluar dari user memory (A masih punya printer). Proses B sekarang run dan berusaha mengakses printer (B tidak berhasil, karena printer masih dimiliki A), maka bisa timbul deadlock. Pada kondisi ini, B dapat dikeluarkan dari user memori, A masuk lagi dan di run lagi menggunakan user memory, mencetak dan release printer

b.      Non Preemptable resource

Non Preemptable resource adalah resource tidak dapat diambil dari proses tanpa menimbulkan efek kegagakan komputasi. Contohnya proses yang sedang mulai melakukan ‘burning CD’ adalah non preemtable resource. Proses ini tidak memungkinkan untuk dilakukan swapping dengan proses lain, karena akan berakibat proses ‘burning’ akan gagal

II.       Analogi Deadlock                       

Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses. Deadlock bisa digambarkan sebagai berikut :

                 Kejadian Deadlock selalu tidak lepas dari sumber daya, bahwa hampir seluruhnya merupakan masalah sumber daya yang digunakan bersama-sama. Oleh karena itu, kita juga perlu tahu tentang jenis sumber daya, yaitu: sumber daya dapat digunakan lagi berulang-ulang dan sumber daya yang dapat digunakan dan habis dipakai atau dapat dikatakan sumber daya sekali pakai. Sumber daya ini tidak habis dipakai oleh proses mana pun.Tetapi setelah proses berakhir, sumber daya ini dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian sumber daya ini. Contohnya prosesor, Channel I/O, disk, semaphore. Contoh peran sumber daya jenis ini pada terjadinya Deadlock ialah misalnya sebuah proses memakai disk A dan B, maka akan terjadi Deadlock jika setiap proses sudah memiliki salah satu disk dan meminta disk yang lain. Masalah ini tidak hanya dirasakan oleh pemrogram tetapi oleh seorang yang merancang sebuah sistem operasi. Cara yang digunakan pada umumnya dengan cara memperhitungkan dahulu sumber daya yang digunakan oleh proses-proses yang akan menggunakan sumber daya tersebut. Contoh lain yang menyebabkan Deadlock dari sumber yang dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses yang memakai memori utama.

III.    Penyebab Deadlock

1.       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.       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 dapat menyebabkan kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.

3.       No 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.

IV.    Menghindari Deadlock

-          Sistem perlu memiliki informasi awal mengenai kebutuhan sumber daya

-          Tiap proses menyatakan kebutuhan maksimum tiap jenis sumber yg dibutuhkan

-          Algoritma deadlock-avoidance secara dinamis memeriksa state alokasi sumber daya untuk menjamin tdk terjadinya kondisi circular-wait

-          State alokasi sumber daya didefinisikan oleh banyaknya sumber daya yg tersedia dan yg dialokasikan, dan permintaan sumber daya maksimum oleh proses

-          Jika proses telah sedang memegang resource tertentu, untuk permintaan berikutnya proses harus melepas dulu resource yg dipegangnya.

-          Beri pengurutan linear terhadap resource pada semua proses

-          Jika proses meminta sumber daya yg tersedia, sistem harus memutuskan apakah alokasi sumber daya ini akan menghasilkan safe state

-          Sistem berada pada safe state jika terdapat urutan event yg tidak menyebabkan deadlock jika semua proses meminta sumber daya maksimum sekaligus. Pendekatan metode ini adalah dengan hanya memberi kesempatan ke permintaan sumber daya yang tidak mungkin akan menyebabkan deadlock. Metode ini memeriksa dampak pemberian akses pada suatu proses, jika pemberian akses tidak mungkin menuju kepada deadlock, maka sumber daya akan diberikan pada proses yang meminta. Jika tidak aman, proses yang meminta akan di-suspend sampai suatu waktu permintaannya aman untuk diberikan. Kondisi ini terjadi ketika setelah sumber daya yang sebelumnya dipegang oleh proses lain telah dilepaskan.

V.           Strategi Mengatasi Deadlock

a.       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 seakanakan 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 tertentu dan mencoba lagi.

b.      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:

-          Permintaan sumber daya dikabulkan selama memungkinkan.

-          Sistem operasi memeriksa adakah kondisi circular wait secara periodik.

-          Pemeriksaan adanya deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah proses.

-          Memeriksa dengan algoritma tertentu.

c.       Penghindaran yang terus menerus dan pengalokasian yang baik dengan menggunakan protokol 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.

d.      Pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock dengan deadlock prevention sistem untuk memastikan bahwa salah satu kondisi yang penting tidak dapat menunggu.

e.       Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku

- Mutual Exclusion : membuat file spool untuk resource yang digunakan bersama-sama

- Hold and Wait : memaksa sebuah proses untuk melepaskan resource yang dimilikinya ketika meminta resource baru

- Circular Waiting : memberikan penamaan resource berdasarkan urutan atau level

- No Preemption : membolehkan adanya preemptionAvoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker

f.       Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker

-          Resource manager menolak proses yang meminta resource yang berpotensi deadlock

-          -Jika ada permintaan resource yang maksimum digunakan, maka proses tersebut akan dipaksa untuk melepaskan resource yang sudah dimiliknya

-          Perlu adanya informasi tambahan

g.      Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery, Algoritma Ostrich. Tindakan recovery yang dilakukan adalah : melakukan preemption, membuat checkpoint untuk rollback lalu membunuh proses yang prioritasnya kecil

VI.         Mendeteksi dan memulihkan Deadlock

-          Metode ini mengunakan pendekatan dengan teknik untuk menentukan apakah deadlock sedang terjadi serta proses-proses dan sumber daya yang terlibat dalam deadlock tersebut. Setelah kondisi deadlock dapat dideteksi, maka langkah pemulihan dari kondisi deadlock dapat segera dilakukan.

-          Langkah pemulihan tersebut adalah dengan memperoleh sumber daya yang diperlukan oleh proses-proses yang membutuhkannya. Beberapa cara digunakan untuk mendapatkan sumber daya yang diperlukan, yaitu dengan terminasi proses dan pre-emption (mundur) suatu proses. Metode ini banyak digunakan pada komputer mainframe berukuran besar.

VII.      Terminasi Proses

Metode ini akan menghapus proses-proses yang terlibat pada kondisi deadlock dengan mengacu pada beberapa syarat. Beberapa syarat yang termasuk dalam metode ini adalah, sebagai berikut:

a.       Menghapus semua proses yang terlibat dalam kondisi deadlock (solusi ini terlalu mahal).

b.      Menghapus satu persatu proses yang terlibat, sampai kondisi deadlock dapat diatasi (memakan banyak waktu).

c.       Menghapus proses berdasarkan prioritas, waktu eksekusi, waktu untuk selesai, dan kedalaman dari rollback.