Deadlock Dan Starvation

Diposting pada

Pengertian Deadlock, Starvation, Perbedaan, Mencegah, Mengatasi dan Penyebab : suatu kondisi dimana dua proses atau lebih saling menunggu proses yang lain untuk melepaskan resource yang sedang dipakai.

Deadlock Dan Starvation


Baca Juga Artikel Yang Mungkin Berhubungan : Pengertian Sistem Informasi


Pengertian DEADLOCK

Deadlock adalah suatu kondisi dimana dua proses atau lebih saling menunggu proses yang lain untuk melepaskan resource yang sedang dipakai. Karena beberapa proses itu saling menunggu, maka tidak terjadi kemajuan dalam kerja proses-proses tersebut. Deadlock dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem operasi adalah kebuntuan proses. Deadlock adalah masalah yang biasa terjadi ketika banyak proses yang membagi sebuah resource yang hanya boleh dirubah oleh satu proses saja dalam satu waktu. Jadi deadlock ialah suatu kondisi dimana proses tidak berjalan lagi atau pun tidak ada komunikasi lagi antar proses.


Salah satu contoh sebuah deadlock:

  1. Proses A menggunakan CD-ROM.
  2. Proses B menggunakan Scanner.
  3. Proses A meminta Scanner (tanpa melepas CD-ROM) → menunggu.
  4. Proses B meminta CD-ROM (tanpa melepas Scanner) → menunggu.
  5. Menunggu… menunggu… DEADLOCK.

Model Sistem Deadlock

Untuk memodelkan kondisi deadlock, maka bayangkan sebuah sistem dengan:

  1. Sekumpulan proses, P = {P1, P2, …, Pn}
  2. Sekumpulan tipe sumber daya yang berbeda, R = {R1, R2, …, Rm}
  3. Sumber daya Ri memiliki n bagian (instans) yang identik dan masing-masing digunakan.

Pada model operasi normal, sebuah proses menggunakan sumber daya dengan urutan sebagai berikut:

  • Mengajukan permohonan (request)
    Bila permohonan tidak dapat dikabulkan dengan segera (misal karena sumber daya sedang digunakan proses lain), maka proses itu harus menunggu sampai sumber daya yang dimintanya tersedia.


  • Menggunakan sumber daya (use)
    Proses dapat menggunakan sumber daya, misalnya printer untuk mencetak, disk drive untuk melakukan operasi I/O, dan sebagainya.


  • Melepaskan sumber daya (relase)
    Setelah proses menyelesaikan penggunaan sumber daya, maka sumber daya harus dilepaskan sehingga dapat digunakan oleh proses lain.


model operasi Deadlock


Resource Deadlock

Deadlock bisa terjadi pada saat proses akan mengakses obyek secara tidak semestinya. Obyek tersebut dinamakan sumber daya. Sumber daya ada dua jenis, yaitu:


Preemptable

Sumber daya dikatakan preemptable jika sumber daya tersebut dapat diambil (dilepas) dari proses yang sedang memakainya tanpa member efek apapun pada proses tersebut. 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, kanal M/K, disk, semafor. 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. Contohnya dapat dilihat dari kode berikut ini:

Loading...

Preemptable

Setelah proses P dan Q telah melakukan fungsi meminta untuk pertama kali, maka sumber daya yang tersedia dalam banyak ialah 50 (200-70-80). Maka saat P menjalankan fungsi meminta lagi sebanyak 60, maka P tidak akan menemukan sumber daya dari banyak sebanyak 60, maka P akan menunggu hingga sumber daya yang diminta dipenuhi. Demikian juga dengan Q, akan menunggu hingga permintaannya dipenuhi, akhirnya terjadi deadlock. Cara mengatasinya dengan menggunakan memori maya.


Non-preemtable

Pada sumber daya jenis ini, sumber daya tidak dapat diambil dari proses yang sedang membawanya karena akan menimbulkan kegagalan komputasi. Printer adalah salah satu contohnya. Jika suatu proses sedang menggunakan printer untuk mencetak sesuatu, maka printer tersebut tidak dapat diambil untuk mencetak sesuatu dari proses lain. Sumber daya jenis ini biasanya berpotensi terjadinya deadlock. Contohnya seperti berikut:


Non-preemtable


Dari kedua fungsi tersebut ada yang bertindak untuk menerima dan memberi sumber daya, tetapi ada kalanya proses tidak mendapat sumber daya yang dibuat sehingga terjadi blok, karena itu terjadi deadlock. Tentu saja hal ini sangat jarang terjadi mengingat tidak ada batasan untuk memproduksi dan mengkonsumsi, tetapi ada suatu keadaan seperti ini yang mengakibatkan deadlock. Hal ini mengakibatkan deadlock jenis ini sulit untuk dideteksi. Selain itu deadlock ini dihasilkan oleh beberapa kombinasi yang sangat jarang terjadi.


Penyebab Deadlock

Setelah kita melihat beberapa illustrasi di atas, mungkin kita sekarang mulai bisa membayangkan apa itu deadlock. Sebenarnya deadlock itu akan terjadi apabila syarat-syarat dari deadlock tersebut terpenuhi. Adapun 4 kondisi penyebab deadlock adalah sebagai berikut:


  • a. 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.


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


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


  • d. Circular Wait
    Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.

Penanganan dan Masalah Deadlock

Penanganan Deadlock

Terdapat beberapa cara dalam menangani deadlock, yang secara umumnya ada 4 cara untuk menanganinya, yaitu:

  1. Mengabaikan masalah.
  2. Mendeteksi dan memperbaiki.
  3. Penghindaran.
  4. Pencegahan.

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 seakan-akan 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.


Baca Juga Artikel Yang Mungkin Berhubungan : Manajemen SDM : Pengertian, Fungsi, Tujuan, Unsur, Pendekatan


Mendeteksi dan Penghindaran

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:

  1. Permintaan sumber daya dikabulkan selama memungkin-kan.
  2. Sistem operasi memeriksa adakah kondisi circular wait secara periodik.
  3. Pemeriksaan adanya Deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah proses.
  4. Memeriksa dengan algoritma tertentu.

Penghindaran Deadlock

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.


Kondisi aman yang dimaksudkan selanjutnya disebut sebagai safe-state, sedangkan keadaan yang tidak memungkinkan untuk diberikan sumber daya yang diminta disebut unsafe-state.


  • a. Kondisi Aman (Safe State)
    Suatu keadaan dapat dinyatakan sebagai safe state jika tidak terjadi deadlock dan terdapat cara untuk memenuhi semua permintaan sumber daya yang ditunda tanpa menghasilkan deadlock. Dengan cara mengikuti urutan tertentu.


  • b. Kondisi Tak Aman (Unsafe State)
    Suatu state dinyatakan sebagai state tak selamat (unsafe state) jika tidak terdapat cara untuk memenuhi semua permintaaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.

Penghindaran

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.


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.


Status Aman Status ini terjadi jika sistem dapat mengalokasikan sumber daya bagi tiap proses dalam keadaan tertentu dan masih dapat terjadi deadlock. Status aman bukanlah status deadlock, jadi  status deadlock merupakan status tidak aman, tetapi tidak selamanya status tidak aman mengakibatkan status deadlock melainkan ada kemungkinan dapat terjadi.


Pencegahan Deadlock

Metode Pencegahan dianggap sebagai solusi yang bersih dipandang dari sudut tercegahnya deadlock. Tetapi pencegahan akan mengakibatkan kinerja utilisasi sumber daya yang buruk. Metode pencegahan menggunakan pendekatan dengan cara meniadakan empat syarat yang dapat menyebabkan deadlock terjadi pada saat eksekusi. Coffman (1971)


Syarat pertama yang akan dapat ditiadakan adalah Mutual Exclusion, jika tidak ada sumber daya yang secara khusus diperuntukkan bagi suatu proses maka tidak akan pernah terjadi deadlock. Namun jika membiarkan ada dua atau lebih proses mengakses sebuah sumber daya yang sama akan menyebabkan chaos. Langkah yang digunakan adalah dengan spooling sumber daya, yaitu dengan mengantrikan job-job pada antrian dan akan dilayani satu-satu.


Beberapa masalah yang mungkin terjadi adalah:

  1. Tidak semua dapat di-spool, tabel proses sendiri tidak mungkin untuk di-spool.
  2. Kompetisi pada ruang disk untuk spooling sendiri dapat mengarah pada deadlock.

Hal inilah yang menyebabkan mengapa syarat pertama tidak dapat ditiadakan, jadi mutual exclusion benar-benar tidak dapat dihilangkan.


Cara kedua dengan meniadakan kondisi hold and wait terlihat lebih menjanjikan. Jika suatu proses yang sedang menggunakan sumber daya dapat dicegah agar tidak dapat menunggu sumber daya yang lain, maka deadlock dapat dicegah. Langkah yang digunakan adalah dengan membuat proses agar meminta sumber daya yang mereka butuhkan pada awal proses sehingga dapat dialokasikan sumber daya yang dibutuhkan. Namun jika terdapat sumber daya yang sedang terpakai maka proses tersebut tidak dapat memulai prosesnya.


Masalah yang mungkin terjadi:

  1. Sulitnya mengetahui berapa sumber daya yang akan dibutuhkan pada awal proses.
  2. Tidak optimalnya pengunaan sumber daya jika ada sumber daya yang digunakan hanya beberapa waktu dan tidak digunakan tapi tetap dimiliki oleh suatu proses yang telah memintanya dari awal.

Meniadakan syarat ketiga non preemptive ternyata tidak lebih menjanjikan dari meniadakan syarat kedua, karena dengan meniadakan syarat ketiga maka suatu proses dapat dihentikan ditengah jalan. Hal ini tidak dimungkinkan karena hasil dari suatu proses yang dihentikan menjadi tidak baik.


Cara terakhir adalah dengan meniadakan syarat keempat circular wait. Terdapat dua pendekatan, yaitu:

  1. Mengatur agar setiap proses hanya dapat menggunakan sebuah sumber daya pada suatu waktu, jika menginginkan sumber daya lain maka sumber daya yang dimiliki harus dilepas.
  2. Membuat penomoran pada proses proses yang mengakses sumber daya. Suatu proses dimungkinkan untuk dapat meminta sumber daya kapan pun, tetapi permintaannya harus dibuat terurut.

Masalah yang mungkin terjadi dengan mengatur bahwa setiap proses hanya dapat memiliki satu proses adalah bahwa tidak semua proses hanya membutuhkan satu sumber daya, untuk suatu proses yang kompleks dibutuhkan banyak sumber daya pada saat yang bersamaan. Sedangkan dengan penomoran masalah yang dihadapi adalah tidak terdapatnya suatu penomoran yang dapat memuaskan semua pihak.


Baca Juga Artikel Yang Mungkin Berhubungan : Analisis – Pengertian, Contoh, Tahap, Tujuan, Para Ahli


Pengertian STARVATION

Berkembangannya Sistem Imformasi saat ini dan mendatang akan menuju ke sebuah  sistem multiprogramming, multi-processing, paralel dan terdistribusi yang mengharuskan adanya proses-proses yang berjalan bersama sama dalam waktu yang bersamaan


¨Starvation adalah kondisi yang biasanya terjadi setelah deadlock.

Proses yang kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan).


¨Starvation adalah kondisi yang biasanya terjadi setelah deadlock. Proses yang kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan). ¨Starvation dapat terjadi pada proses penjadwalan yang menggunakan prinsip “proses yang paling cepat diselesaikan didahulukan”, seperti pada Shortest Job First (SJF) dan Penjadwalan Prioritas.


Proses yang kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan). Starvation dapat diatasi dengan Aging dan pemrosesan dengan cara Round Robin.


KARENA  ADANYA DEADLOCK

STARVATION

Proses yang kekuranganresource (karena terjadi deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan)


TANPA  ADANYA DEADLOCK

TANPA  ADANYA DEADLOCK

Hal ini ketika terdapat kesalahan dalam sistem sehingga terjadi ketimpangan dalam pembagian resouce. Satu proses selalu mendapat resource, sedangkan proses yang lain tidak pernah mendapatkannya

Karakteristik Starvation

Starvation dapat terjadi pada proses penjadwalan yang menggunakan prinsip “proses yang paling cepat diselesaikan didahulukan”, seperti pada Shortest Job First (SJF) dan Penjadwalan Prioritas


Baca Juga Artikel Yang Mungkin Berhubungan : Riset Operasi – Penegrtian, Tahapan, Model, Definisi, Tujuan, Contoh


Mengatasi Starvation Aging & RR

Mengatasi Starvation Aging

  • ¨Proses awal yang ada diberi urutan (N) pemrosesan dengan rumus N = (P+T ) / P. N maksimum akan mulai dikerjakan dan proses yang lain dinaikkan tingkat urutan prosesnya agar nanti jika ada proses lain yang masuk, proses terdahulu mendapatkan bagian resource dan dapat dikerjakan.

  • Jika ada beberapa proses yang memiliki N maksimum, maka diantara proses tersebut dilihat dari waktu yang dibutuhkan untuk menyelesaikannya. Jika masih sama juga, maka dilihat waktu kedatangannya.

flowchart Starvation


Mengatasi Starvation RR

Ada beberapa cara untuk mengatasi Starvation, salah satunya dengan Aging,  proses awal yang ada diberi urutan
(N) pemrosesan dengan rumus N = ( P+T ) / P. N maksimum akan mulai dikerjakan dan proses yang lain dinaikkan tingkat urutan prosesnya agar nanti jika ada proses lain yang masuk, proses terdahulu mendapatkan bagian resource dan dapat dikerjakan.


Jika ada beberapa proses yang memiliki N maksimum, maka diantara proses tersebut dilihat dari waktu yang dibutuhkan untuk menyelesaikannya. Jika masih sama juga, maka dilihat waktu kedatangannya.
Selain itu, Starvation juga dapat diatasi dengan pemrosesan dengan cara Round Robin.


Round Robin , adalah proses yang akan dimasukkan ke dalam antrian menurut proses kedatangannya. Dalam penyelesainnya, suatu proses tidak akan langsung selesai jika waktu yang dibutuhkan melebihi waktu kuantum yang diberikan.


Waktu kuantum itu sendiri adalah waktu telah yang diberikan untuk menyelesaikan suatu proses. Ketika sutu proses telah mencapai batas waktu kuantum, sisa dari proses tersebut dikembalikan ke antrian paling belakang dan resource dipindahkan ke proses selanjutnya. Dengan cara ini, semua proses yang mengantri, akan mendapatkan resource secara bergantian ( tidak ada proses yang memonopoli resource ) sehingga semua proses dapat diselesaikan.


  • Round Robin , adalah proses yang akan dimasukkan ke dalam antrian menurut proses kedatangannya. Dalam penyelesainnya, suatu proses tidak akan langsung selesai jika waktu yang dibutuhkan melebihi waktu kuantum yang diberikan.

  • Waktu kuantum adalah waktu telah yang diberikan untuk menyelesaikan suatu proses. Ketika sutu proses telah mencapai batas waktu kuantum, sisa dari proses tersebut dikembalikan ke antrian paling belakang dan resource dipindahkan ke proses selanjutnya. Dengan cara ini, semua proses yang mengantri, akan mendapatkan resource secara bergantian ( tidak ada proses yang memonopoli resource) sehingga semua proses dapat diselesaikan.

Baca Juga Artikel Yang Mungkin Berhubungan : Sistem Informasi Manajemen – Pengertian , Fungsi, Tujuan, Proses, Kemampuan, Contohnya


Perbedaan Deadlock Dan Starvation

Deadlock

  • Deadlock adalah suatu kondisi dimana sekumpulan proses tidak dapat berjalan kembali akibat kompetisi memperebutkan sumber daya.
  • Sebuah proses berada dalam keadaan deadlock apabila semua proses berada dalam keadaan menunggu (di dalam waiting queue) peristiwa yang hanya bisa dilakukan oleh proses yang berada dalam waiting queue tersebut.

  • Sebenarnya deadlock dapat disebabkan oleh empat hal yaitu:
  1. Proses Mutual Exclusion.
  2. Proses memegang dan menunggu.
  3. Proses Preemption.
  4. Proses Menunggu dengan siklus deadlock tertentu.

Starvation

  • ¨Starvation adalah kondisi yang biasanya terjadi setelah deadlock. Proses yang kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan).
  • ¨Starvation dapat terjadi pada proses penjadwalan yang menggunakan prinsip “proses yang paling cepat diselesaikan didahulukan”, seperti pada Shortest Job First (SJF) dan Penjadwalan Prioritas.
  • ¨Starvation dapat diatasi dengan Aging dan pemrosesan dengan cara Round Robin.

Contoh

Contoh ke Pertama

Contoh Generic Host

  • Salah satu notification pop-menu yang muncul jika terjadi starvation di sistem operasi Windows.
  • Ketika pop-menu notification ini layar tidak bisa berjalan sesuai fungsi (tidak bisa meng-klik atau menjalankan program). Terjadi error atau mungkin kerusakan pada Win32 karena terjadi kekurangan memory resource akibat terlalu banyak eksekusi program yang harus dijalankan.
  • Button “Don’t Send” pada notification pop-menu diatas berakibat layar akan freeze sejenak dan melakukan auto-refresh.

Contoh ke dua

Seorang mahasiswa telah memiliki 3 tugas dan ingin juga menonton film baru. Mahasiswa tersebut mendahulukan menyelesaikan tugas dibandingkan menonton. Sebelum ketiga tugas tersebut selesai, dosen lain memberinya tugas baru. Keesokan harinya ada tugas dari asisten untuk praktikum berikutnya. Ketika tugas satu belum selesai, sudah ada tugas lain dari dosen atau asisten. Hal ini terus berulang, sehingga keinginan mahasiswa tersebut untuk menonton film baru bisa tidak terlaksana atau tidak terpenuhi.