Deadlock Pada Sistem Operasi

Pengertian Deadlock

Deadlock adalah keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. 

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. Ada empat kondisi yang dapat menyebabkan terjadinya deadlock. Keempat kondisi tersebut tidak dapat berdiri sendiri, namun saling mendukung.

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.

Strategi mengatasi Deadlock :

Add beberapa cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:

a. Mengabaikan masalah deadlock.

b. Mendeteksi dan memperbaiki

c. 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.

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.

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.

Mendeteksi dan Memperbaiki

1.      Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi system 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.

Ada beberapa jalan untuk kembali dari Deadlock, yaitu:

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 untuk 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.

3.      Lewat mematikan proses yang menyebabkan Deadlock

Cara yang paling umum ialah mematikan semua proses yang mengalami deadlock. Cara ini paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun, untuk beberapa sistem, kita juga dapat mematikan 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 pemilihan korban ialah:

• Yang paling jarang memakai prosesor

• Yang paling sedikit hasil programnya

• Yang paling banyak memakai sumber daya sampai saat ini

• Yang alokasi sumber daya totalnya tersedkit

• Yang memiliki prioritas terkecil

4.      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 membawanya pada kondisi deadlock, sehingga tidak mungkin terjadi deadlock karena pada saat akan menuju deadlock, proses sudah dicegah.

2. Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan membawa kita pada suatu keadaan deadlock. Jadi diadakan dua kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan

ditambah dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar jangan sampai terjadi deadlock. Pada sistem deadlock avoidance (penghindaran) dilakukan dengan cara memastikan bahwa program memiliki maksimum permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan selalu dalam kondisi aman. Baik mengadakan permintaan awal atau pun saat meminta permintaan sumber daya tambahan, sistem harus selalu berada dalam kondisi aman.

Mutual Exclusion

Dalam ilmu komputer, saling pengecualian mengacu pada kebutuhan untuk menjamin bahwa tidak ada dua proses atau benang (selanjutnya disebut hanya sebagai proses) berada di bagian kritis mereka pada waktu yang sama. Di sini, bagian kritis mengacu pada periode waktu ketika proses mengakses sumber daya bersama, seperti memori bersama. Masalah mutual exclusion pertama kali diidentifikasi dan dipecahkan oleh Edsger W. Dijkstra dalam seminal 1965 makalahnya berjudul: Solusi dari masalah dalam kontrol pemrograman konkuren.

Contoh sederhana mengapa saling pengecualian penting dalam praktek dapat divisualisasikan menggunakan linked list tunggal. Dalam sebuah linked list penghapusan node dilakukan dengan mengubah "berikutnya" pointer dari node sebelumnya untuk menunjuk ke simpul berikutnya (misalnya, jika node i sedang dihapus maka "berikutnya" pointer node i-1 akan diubah untuk menunjuk ke node i +1). Dalam eksekusi mana seperti linked list sedang dibagi antara beberapa proses, dua proses mungkin mencoba untuk menghapus dua node yang berbeda secara bersamaan mengakibatkan masalah berikut: biarkan node i dan i +1 menjadi node yang akan dihapus, lebih jauh lagi, janganlah dari mereka menjadi kepala atau ekor, pointer berikutnya simpul i-1 akan berubah untuk menunjuk ke node i +1 dan pointer berikutnya node i akan berubah untuk menunjuk ke node i +2. Meskipun kedua operasi penghapusan lengkap berhasil, node i +1 tetap ada dalam daftar sejak i-1 dibuat untuk menunjuk ke i +1 skipping node i (yang dibuat untuk menunjuk ke i +2). Masalah ini dapat dihindari dengan menggunakan pengecualian bersama untuk memastikan bahwa update simultan ke bagian yang sama dari daftar tidak dapat terjadi. Isi Menegakkan mutual exclusion

Ada baik perangkat lunak dan solusi perangkat keras untuk menegakkan saling pengecualian. Beberapa solusi yang berbeda dibahas di bawah ini.

Solusi perangkat keras

Pada sistem prosesor tunggal, solusi yang paling sederhana untuk mencapai saling pengecualian adalah untuk menonaktifkan interupsi selama proses 'bagian kritis. Ini akan mencegah rutinitas layanan interupsi dari berjalan (efektif mencegah proses dari yang mendahului). Meskipun ini adalah solusi efektif, hal itu menyebabkan banyak masalah. Jika suatu bagian kritis adalah panjang, maka jam sistem akan melayang setiap kali bagian kritis dieksekusi karena interupsi timer tidak lagi dilayani, sehingga pelacakan waktu mustahil selama bagian kritis. Juga, jika suatu proses menghentikan selama bagian kritis, kontrol tidak akan pernah kembali ke proses lain, secara efektif menghentikan seluruh sistem. Sebuah metode yang lebih elegan untuk mencapai saling pengecualian adalah sibuk-tunggu.

Sibuk-tunggu adalah efektif untuk kedua uniprocessor dan sistem multiprosesor. Penggunaan memori bersama dan tes-dan-set instruksi atom memberikan pengecualian bersama. Sebuah proses dapat menguji-dan-set pada sebuah lokasi di memori bersama, dan karena operasi adalah atom, hanya satu proses dapat mengatur bendera pada suatu waktu. Setiap proses yang tidak berhasil dalam menetapkan bendera dapat pergi untuk melakukan tugas-tugas lain dan coba lagi nanti, lepaskan prosesor ke proses lain dan coba lagi nanti, atau terus loop sementara memeriksa bendera sampai berhasil memperolehnya. Preemption masih mungkin, jadi metode ini memungkinkan sistem untuk terus berfungsi - bahkan jika suatu proses menghentikan sambil memegang kunci.

Beberapa operasi atom lainnya dapat digunakan untuk memberikan mutual exclusion struktur data, yang paling terkenal adalah Bandingkan-Dan-Swap (CAS). CAS dapat digunakan untuk mencapai saling pengecualian menunggu gratis untuk setiap struktur data bersama dengan membuat daftar link di mana setiap node merupakan operasi yang diinginkan yang akan dilakukan. CAS kemudian digunakan untuk mengubah pointer dalam daftar terkait selama penyisipan simpul baru. Hanya satu proses dapat berhasil dalam CAS nya, semua proses lain mencoba untuk menambahkan node pada saat yang sama harus mencoba lagi. Setiap proses kemudian dapat menyimpan salinan lokal dari struktur data, dan setelah melintasi linked list, dapat melakukan setiap operasi dari daftar pada copy lokal.

Solusi Software.

Selain solusi perangkat keras yang didukung, beberapa solusi perangkat lunak yang ada yang menggunakan sibuk menunggu untuk mencapai saling pengecualian. Contoh ini meliputi:

    Algoritma Dekker

    Algoritma Peterson

    Lamport bakery algoritma.

    Algoritma Szymanski

    Algoritma roti hitam-putih Taubenfeld itu.

Algoritma ini tidak bekerja jika eksekusi out-of-order yang digunakan pada platform yang mengeksekusi mereka. Programmer harus menentukan memesan ketat pada operasi memori dalam thread.

Hal ini sering lebih baik untuk menggunakan fasilitas sinkronisasi yang disediakan oleh multithreading perpustakaan sistem operasi, yang akan mengambil keuntungan dari solusi perangkat keras jika memungkinkan, tetapi akan menggunakan solusi perangkat lunak jika tidak ada solusi perangkat keras yang ada. Misalnya, ketika perpustakaan kunci sistem operasi yang digunakan dan benang mencoba untuk memperoleh kunci sudah diperoleh, sistem operasi dapat menangguhkan benang menggunakan saklar konteks dan swap keluar dengan benang lain yang siap untuk dijalankan, atau bisa menempatkan prosesor ke dalam keadaan daya rendah jika tidak ada thread lain yang dapat dijalankan. Oleh karena itu, metode saling pengecualian yang paling modern berusaha untuk mengurangi latensi dan sibuk-menunggu dengan menggunakan antrian dan konteks switch. Namun, jika waktu yang dihabiskan menangguhkan benang dan kemudian mengembalikan itu dapat terbukti selalu lebih dari waktu yang harus menunggu untuk sebuah thread untuk menjadi siap untuk menjalankan setelah diblokir dalam situasi tertentu, maka spinlocks adalah denda solusi (untuk situasi yang hanya).

Mutual exclusion canggih

Solusi yang dijelaskan di atas dapat digunakan untuk membangun sinkronisasi primitif di bawah ini:

    Kunci

    Mutexes reentrant

    Semaphore

    Monitor

    Message passing

    Ruang tupel

Banyak bentuk mutual exclusion memiliki efek samping. Misalnya, Semaphore klasik mengizinkan deadlock, di mana satu proses mendapatkan semaphore, proses lain mendapat semaphore kedua, dan kemudian keduanya menunggu selamanya untuk semaphore lainnya akan dirilis. Lain efek samping umum termasuk kelaparan, di mana proses pernah mendapat sumber daya yang cukup untuk menjalankan sampai selesai, inversi prioritas, di mana thread prioritas yang lebih tinggi menunggu thread prioritas rendah, dan "latency tinggi", di mana respon terhadap interupsi adalah tidak cepat.

Banyak penelitian yang bertujuan untuk menghilangkan efek di atas, sering dengan tujuan menjamin kemajuan non-blocking. Tidak ada skema yang sempurna dikenal. Memblokir sistem panggilan digunakan untuk tidur seluruh proses. Sampai panggilan tersebut menjadi benang aman, tidak ada mekanisme yang tepat untuk tidur satu thread dalam proses .

Kunci eksklusif Reksa pada objek memori (dalam konteks ini berbagi proses / benang memori) yang diperlukan seperti pada objek database (kunci file). Tentu saja, objek database dapat memiliki non-eksklusif (baca) kunci dan karenanya David Hostettler Wain diusulkan nonexs - kunci memori non-eksklusif pada tahun 2006. Ini masih belum diterapkan secara luas.