Sistem Operasi: Pengertian Deadlock

Posted on

Pengertian Deadlock ialah 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.

Pengertian Deadlock
Contoh Deadlock di Persimpangan Jalan

 

Pengertian Deadlock_2
Deadlock pada jembatan
  • Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses.
  • 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.

Contoh

Contohnya prosesor, Channel I/O, disk. 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

 

Pengoperasian I/O

  • lmeminta (request) : meminta pelayanan perangkat masukan / keluaran
  • lmemakai (use) : memakai perangkat masukan / keluaran
  • lmelepaskan (release) : melepaskan pemakaian perangkat masukan / keluaran

 

RESOURCE

  Resource dapat berupa hardware device (seperti tape drive, memori) atau berupa informasi (record dalam suatu basis data, variable global, dll).

    Resource ada 2 jenis, yaitu:

  • Preemptable
  • Nonpreemtable.

 

Dua Jenis Resource :

Resource preemtable adalah resource yang dapat diambil (dilepas) dari proses yang sedang memakainya tanpa memberi efek apapun pada proses tersebut.

Resource nonpreemtable adalah resource yang tidak dapat diambil dari proses yang sedang membawanya karena akan menimbulkan kegagalan komputasi. Resource jenis ini yang sering Menyebabkan deadlock.

 

DIAGRAM GRAF

Sebuah sistem komputer terdiri dari berbagai macam sumber daya (resources), seperti:

  1. Fisik (Perangkat, Memori)
  2. Logika (Lock, Database record)
  3. Sistem Operasi (PCB Slots)
  4. Aplikasi (Berkas)

Mekanisme hubungan dari proses-proses dan sumber-daya yang dibutuhkan/digunakan dapat di diwakilkan dengan graf.

 

 

Proses Pi meminta sumber daya Rj
Proses Pi meminta sumber daya Rj

 

Sumber daya Rj yang mengalokasikan salah satu
Sumber daya Rj yang mengalokasikan salah satu

 

Graf Alokasi Sumber daya
Graf Alokasi Sumber daya

 

Untuk mengetahui ada atau tidaknya deadlock (Pendeteksian) dalam suatu graf dapat dilihat dari perputaran dan resource yang dimilikinya, yaitu:

  • Jika tidak ada perputaran berarti tidak deadlock.
  • Jika ada perputaran, ada potensi terjadi deadlock.
  • Resource dengan instan tunggal dan perputaran mengakibatkan deadlock.

 

 

Fakta tentang Deadlock dalam OS

Pada windows NT, deteksi deadlock yaitu berupa BSOD(Blue Screen Of Death), recoverynya adalah reboot sederhana

Pada linux untuk mengetahui apakah terjadi deadlock yaitu dengan menggunakan xosview untuk mengetahui proses yang menggunakan CPU 100%, lalu kill saja proses tersebut.

 

Deadlock di Linux

Beberapa kasus deadlock juga terjadi ketika OS Linux dijalankan dari kondisi sleep, proses yang mengakses USB device akan mengalami deadlock

Hal ini disebabkan fungsi scheduler pada kernel yang digunakan tidak menyimpan state sebelum sleep, sehingga ketika kernel dijalankan kembali, Proses-proses yang mengakses USB device tersebut menunggu giliran mengakses, sementara scheduler belum menjadwalkan masing-masing proses.

 

Kondisi untuk Terjadinya Deadlock

1. Mutual exclusion (mutual exclusion conditional)

  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. Kondisi genggam dan tunggu (hold and wait)

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. Kondisi non-preemption (non-preemption condition)

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. Kondisi menunggu secara sirkuler (circular wait condition)

Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.

 

Kondisi untuk Terjadinya Deadlock

  1. Terjadi deadlock bila terdapat ketiga kondisi itu, tetapi adanya ketiga kondisi itu belum berarti terjadi deadlock.
  2. Deadlock benar-benar terjadi bila syarat keempat terpenuhi. Kondisi keempat  merupakan keharusan bagi terjadinya deadlock.
  3. Deadlock bisa terjadi pada saat proses akan mengakses objek seperti file,device, dll secara tidak semestinya. Objek tersebut dinamakan resource.

 

Metode Mengatasi Deadlock

1.Mengabaikan masalah deadlock

2.Mendeteksi dan memperbaiki

3.Menghindari deadlock (avoidance)

4.Pencegahan deadlock (prevention)

 

Mengabaikan Masalah Deadlock

  • Algoritma Ostrich
  • Menghadapi deadlock dengan berpura-pura tidak ada masalah apapun
  • Dipakai jika yakin deadlock akan sangat jarang terjadi dan biaya untuk deteksi atau pemulihan deadlock tinggi

Deteksi

  • Deteksi deadlock adalah teknik untuk menentukan apakah deadlock terjadi serta mengidentifikasi proses-proses dan sumberdaya sumberdaya yang terlibat deadlock.
  • Periode yang biasa dilakukan adalah memonitor permintaan dan pelepasan sumber daya.
  • Bila sistem terdapat deadlock maka deadlock harus diputuskan. Biasanya beberapa proses akan kehilangan sebagian atau semua kerja yang telah dilakukan. Hal ini lebih baik daripada terjadinya deadlock yang berarti semua proses tidak menghasilkan apapun

Perbaikan/Pemulihan

  • Preemption
    • Mengambil sementara sumber daya dari proses yang menggunakannya
    • Sangat sulit dilakukan
  • Melacak kembali
    • Proses yang diambil sumber dayanya ketika dilakukan preemption akan berhenti, dibutuhkan langkah untuk melanjutkan proses tersebut
    • Sulit dilakukan sehingga umumnya proses dimulai lagi dari awal
  • Menghentikan proses yang menyebabkan deadlock – cara paling umum digunakan

Kriteria Pemilihan Proses Yang Akan Disingkirkan

  • Yang paling jarang memakai prosesor
  • Yang paling sedikit hasil programnya
  • Yang paling banyak memakai sumber daya sampai saat ini
  • Yang alokasi sumber daya totalnya / maksimum sumber daya yang dibutuhkan paling sedikit
  • Yang memiliki prioritas terkecil

 

Menghindari Deadlock (Avoidance)

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

  • ljika pemberian akses sumber daya tidak mungkin menuju deadlock, sumber daya diberikan ke peminta.
  • lJika tidak aman (memungkinkan timbulnya deadlock), proses yang meminta di suspend sampai suatu waktu permintaannya aman diberikan. Kondisi ini biasanya terjadi setelah 1 sumber daya / lebih yang semula dipegang oleh proses-proses aktif lain dilepaskan.
  • lAgar 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.
  • Menggunakan algoritma bankir

 

Algoritma Bankir

  • Adanya safe state (kondisi aman) dan unsafe state (kondisi tidak aman)
  • Digambarkan sebagai seorang bankir yang memberi pinjaman ke sekelompok peminjam
  • Setiap peminjam memberikan batas pinjaman maksimum dan pengembalian wajib tepat waktu
  • Peminjaman secara bertahap, dan bankir memastikan bahwa dana selalu tersedia bagi peminjam yang lain (safe state)
  1. Tersedia. Jumlah sumber daya/dana yang tersedia.
  2. Maksimum. Jumlah sumber daya maksimum yang diminta oleh setiap proses.
  3. Alokasi. Jumlah sumber daya yang dibutuhkan oleh setiap proses.
  4. Kebutuhan. Maksimum-alokasi, sisa sumber daya yang dibutuhkan oleh proses setelah dikurangi dengan yang dialokasikan.

 

Safe State

State selamat (safe state) : jika tidak deadlock dan terdapat cara untuk memenuhi semua permintaan yang ditunda tanpa menghasilkan deadlock dengan menjalankan proses secara hati-hati mengikuti suatu urutan tertentu..

Contoh :

  • Sistem dengan 10 sumber daya setipe, proses A memerlukan sumber daya maksimum sebanyak 10, sedang saat ini menggenggam 2 sumber daya. proses B memerlukan sumber daya maksimum sebanyak 3, sedang saat ini menggenggam 1 sumber daya. Proses C memerlukan sumber dayamaksimum sebanyak 7, sedang saat ini menggenggam 3 sumber daya. Masih tersedia 4 sumber daya.

 

Pencegahan Deadlock (Prevention)

  1. Sedapat mungkin tidak mempergunakan mutual exclusion
  2. Jika proses  sedang memegang sumberdaya tertentu, untuk permintaan berikutnya proses harus melepas dulu sumberdaya yang dipegangnya.
  3. Tiap proses harus meminta semua sumber daya yang diperlukan secara sekaligus dan tidak berlanjut sampai semuanya diberikan.
  4. Beri pengurutan linier terhadap tipe-tipe sumber daya pada semua proses, yaitu jika proses telah dialokasikan suatu tipe sumber daya, proses hanya boleh meminta tipe sumber daya pada urutan berikutnya.