Apa itu Deadlock dalam Sistem Operasi: Algoritma Kondisi & Deteksi

Apa itu Deadlock dalam Sistem Operasi: Algoritma Kondisi & Deteksi

Tujuan utama dari sistem operasi adalah untuk menyediakan komunikasi yang tepat antara sumber daya perangkat keras dan perangkat lunak dan juga memberikan layanan umum untuk program. Ketika proses sistem operasi ingin mengakses sumber daya apa pun, pertama-tama ia mengirimkan permintaan ke sumber daya tertentu yang ingin diaksesnya, kemudian menggunakan sumber daya dan akhirnya melepaskan sumber daya setelah digunakan. Untuk misalkan banyak proses mencoba mengakses satu sumber daya pada saat yang sama, menjadi sulit untuk menyediakan satu sumber daya untuk semua proses pada suatu waktu dalam situasi seperti itu konsep bernama kebuntuan muncul. Karenanya artikel ini menjelaskan bagaimana kebuntuan terjadi dan bagaimana mengatasi situasi kebuntuan tersebut.



Apa itu Deadlock dalam Sistem Operasi?

Definisi: Dead-Lock adalah situasi di mana dua atau lebih prosesor sedang menunggu beberapa peristiwa terjadi, tetapi peristiwa yang tidak terjadi tersebut adalah kondisi kebuntuan, dan prosesor dikatakan dalam keadaan buntu. Misalnya, mari kita asumsikan skenario waktu nyata, di mana ada dua mobil A & B, yang dikendarai oleh dua pengemudi individu di jalan satu arah. Sekarang situasi muncul di mana pengemudi Mobil A mengatakan bahwa dia bergerak ke arah utara adalah arah yang benar, sedangkan pengemudi Mobil B mengatakan bahwa dia bergerak ke arah selatan adalah benar. Namun tidak ada satupun yang mundur untuk membiarkan mobil lain maju, kondisi ini disebut kondisi deadlock.


Mobil-Contoh

contoh mobil





Untuk pemahaman yang lebih baik mari kita pertimbangkan contoh lain di mana ada dua sumber daya R1, R2, dan dua proses P1 dan P2, di mana R1 ditugaskan ke P1 dan R2 ditugaskan ke P2. Sekarang jika P1 ingin mengakses R2, seperti yang telah kita ketahui R2 dipegang oleh P2, dan sekarang P2 ingin mengakses R1, yaitu P1 hanya dijalankan ketika ia diakses ke R2, juga P2 hanya dijalankan jika ia diakses ke R1 situasi ini adalah keadaan buntu.

Prosesor-Contoh

prosesor-contoh



Kondisi Dead-Lock

Berikut ini adalah empat kondisi kebuntuan yang penting terjadi jika semua kondisi terjadi secara bersamaan dan ada peluang tertentu untuk terjadinya kebuntuan.

Pengecualian Bersama

Artinya, sumber daya apa pun yang kita gunakan harus digunakan dengan cara yang saling eksklusif. Dimana hanya satu proses yang menggunakan satu resource dalam satu waktu saja. Misalnya, proses pencetakan sedang berlangsung dan tiba-tiba ada proses lain yang mencoba menghentikan proses pencetakan. Jadi di sini dalam situasi saling pengecualian, hanya setelah tugas pencetakan selesai maka hanya tugas berikutnya yang diproses. Pengecualian timbal balik dapat dihilangkan dengan berbagi sumber daya secara bersamaan, yang secara praktis tidak mungkin dilakukan.

Mutual-Exclusion

saling pengecualian

Tidak ada Pre-emption

Berdasarkan pre-emptive berdasarkan algoritma, jika ada tugas prioritas yang mencoba mengganggu tugas saat ini. Algoritme pre-emptive yang menahan tugas saat ini dan pertama-tama menjalankan tugas prioritas dan kembali ke tugas pertamanya. Sebuah situasi dijelaskan seperti contoh di atas di mana suatu proses memegang sumber daya selama itu dijalankan, yaitu P1 dapat melepaskan R1 hanya setelah dieksekusi, demikian pula P2 melepaskan R2 hanya setelah eksekusi. Jika tidak ada pencegahan, kebuntuan dapat terjadi.


Tanpa-Preemption-Contoh

no-preemption-example

Tahan dan Tunggu

Suatu proses memegang beberapa sumber daya dan menunggu sumber daya tambahan tetapi sumber daya tersebut diperoleh oleh beberapa proses lain. Dari contoh di atas, P1 menahan R1 dan menunggu R2, di mana R2 diakuisisi oleh P2, dan P2 menahan R2 dan menunggu R1, di mana R1 diakuisisi oleh P1 adalah buntu situasi tunggu dan tunggu yang mungkin terjadi di sistem.

Tahan-dan-Tunggu-Contoh

tahan-dan-tunggu-contoh

Penantian Melingkar

Serangkaian proses dikatakan mengalami kebuntuan jika satu proses menunggu sumber daya yang dialokasikan ke proses lain dan proses tersebut menunggu sumber daya, ini mirip dengan contoh yang dijelaskan di atas di mana ia berada dalam bentuk loop. Dimana P1 menunggu R2 dan R2 dialokasikan untuk P2 dan P2 menunggu R1 dan R1 dialokasikan untuk P1 yang merupakan bentuk tunggu melingkar jika kondisi ini memenuhi deadlock terjadi.

Edaran-Tunggu-Contoh

melingkar-tunggu-contoh

Algoritma Deteksi Dead-Lock

Kasus di mana kami mengalokasikan sumber daya untuk proses, dan sistem operasi memeriksa ulang jika terjadi kebuntuan dalam sistem atau tidak menggunakan 2 algoritme deteksi kebuntuan utama, yaitu

  • Contoh tunggal
  • Beberapa contoh jenis sumber daya

Instance Tunggal

Contoh tunggal adalah situasi di mana sistem memiliki contoh tunggal dari semua sumber daya. Ini juga dikenal sebagai menunggu algoritma grafik atau grafik alokasi sumber daya. Grafik alokasi sumber daya terdiri dari sekumpulan proses dan kumpulan sumber daya yang direpresentasikan sebagai dua simpul berbeda. Sumber daya dalam grafik alokasi sumber daya dimodifikasi dan ditampilkan sebagai menunggu bentuk grafik. Dimana menunggu bentuk grafik hanya memiliki proses yang direpresentasikan sebagai simpul seperti yang ditunjukkan di bawah ini dimana,

  • Grafik alokasi sumber daya: Proses P1, P2, P3 dan sumber daya R1, R2, R3 diwakili dalam grafik alokasi sumber daya.
  • Tunggu Grafik: Hanya Proses P1, P2, P3 yang disebutkan menunggu grafik.
  • Jika terdapat kondisi siklus, yaitu jika terjadi aliran proses yang kontinyu dalam satu arah berarti kondisi siklus keluar dan menunggu grafik dalam kondisi deadlock.

Contoh 1: Contoh di bawah ini menunjukkan tidak ada keadaan kebuntuan karena tidak ada aliran kontinu yang diamati dalam menunggu grafik.

Single-Instance-Example1

single-instance-example1

Contoh 2: Kondisi deadlock terjadi karena adanya aliran siklus yang kontinyu dari P1 ke P4.

Single-Instance - Example2

single-instance-example2

Jika kebuntuan terjadi sangat sering dalam sistem maka algoritma pendeteksian sering digunakan. Jika ada lebih banyak penggunaan algoritma pendeteksian maka akan ada lebih banyak overhead dan lebih banyak waktu komputasi. Oleh karena itu untuk mengatasi hal ini, kami memanggil algoritme setelahnya, memberikan jumlah waktu yang sama, ini adalah cara bobot grafik digunakan untuk mendeteksi kebuntuan.

Beberapa Contoh Jenis Sumber Daya

Beberapa contoh dari tipe sumber daya adalah situasi di mana sistem memiliki banyak contoh dari semua sumber daya, ini juga dikenal sebagai algoritma Bankir. Menurut algoritme Bankir, segera setelah proses mendapatkan semua sumber daya yang diperlukan, maka ia melepaskan sumber dayanya.

Mari kita perhatikan contoh berikut, asumsikan ada 3 proses P0, P1, P2, dan tipe sumber daya A, B, C di mana A dapat CPU , B bisa menjadi printer dan C bisa menjadi keyboard. Angka '0' di kolom mewakili ketersediaan sumber daya.

Kasus (i): Misalkan jika kita mengambil kondisi request adalah kondisi “000” yang ada di P0 dan P2, kita harus mengecek request mana yang terpenuhi, proses P0 melepaskan proses setelah mendapatkan alokasi, kemudian P2 memproses rilis setelah mendapatkan alokasi. Seperti ini, secara berurutan, satu per satu proses melepaskan P0, P2, P3, P1, P4 secara berurutan. Akhirnya, kami mendapatkan sumber daya yang tersedia sebagai P7, P2, P6. Urutan yang tersedia adalah kondisi dimana tidak ada jalan buntu.

Bankir-Algoritma-Contoh 1

bankir-algoritme-contoh1

Rumah (ii): Misalkan jika P2 adalah 001 dan bukan 000, sekarang terapkan algoritma bankir untuk memeriksa kondisi deadlock, di mana satu-satunya P0 yang dieksekusi di antara 5 proses. Oleh karena itu P1, P2, P3, P4 dalam keadaan deadlock kecuali untuk P0.

Bankir-Contoh2

bankir-contoh2

Aplikasi Deadlock

Penerapan deadlock dapat dijelaskan dengan contoh real-time hasil ujian online, dimana beberapa mahasiswa mencoba mengakses website universitas mereka pada saat rilis. Seseorang dapat mengamati bahwa kadang-kadang halaman web tidak memuat sekaligus ke banyak pengguna, ini adalah kondisi kebuntuan. Ini dapat diatasi dengan menggunakan salah satu algoritma.

Keuntungan

Keuntungan dari kebuntuan adalah

  • Tidak ada pencegahan yang diamati dalam menghindari kebuntuan
  • Tidak ada penundaan dalam prosesnya

Kekurangan

Kerugian dari kebuntuan adalah

  • Sumber daya yang akan digunakan harus diketahui sebelumnya
  • Penyumbatan proses untuk waktu yang lama
  • Kerugian pre-emption diwariskan.

Artikel ini mengulas tentang bagaimana kebuntuan terjadi ketika ada dua atau lebih proses dan tiga kondisi yang menjadi penyebab terjadinya kebuntuan, dan dua jenis algoritma yaitu algoritma berbagi sumber daya yang mendeteksi adanya kondisi kebuntuan dan algoritma bankir yang merupakan algoritma penghindaran kebuntuan. Berikut pertanyaannya “Apa yang terjadi jika kebuntuan diabaikan?”.