Understanding Deadlock and Starvation in Multiprogramming Systems

Slide11DEADLOCK & STARVATION

Slide22Deskripsi Deadlock & Starvation Proses pada sistem multiprogramming dikatakan deadlock jika proses itu menunggu suatu kejadian tertentu yang tak akan pernah terjadi. Deadlock terjadi ketika proses-proses mengakses secara eksklusif sumber daya Proses dikatakan sebagai mengalami starvation bila proses-proses itu menunggu alokasi sumber daya sampai tak terhingga, sementara starvation disebabkan karena bias pada kebijaksanaan atau strategi alokasi sumber daya

Slide33Model Deadlock   Urutan kejadian pengoperasian peralatan masukan / keluaran adalah: Meminta (request)  : Meminta pelayanan peralatan                masukan / keluaran Memakai (use)  : Memakai peralatan masukan/    keluaran Melepaskan (release): Melepaskan pemakaian    peralatan masukan / keluaran

Slide44Model Deadlock Didalam suatu proses dan pengalokasian sumber daya logikanya agar tidak terjadi deadlock adalah P 0 R 0 Sebuah proses meminta sumber daya R 1 P 1 Sumber daya diberikan agar proses berjalan

Slide55Model Deadlock Kondisi  di  atas  akan  dapat  menjadi  deadlock  apabila terjadi  kondisi  saling  menunggu.  Seperti  pada  gambar berikut: P 1 R 1 R 0 P 0 Pada  saat  proses  0  menggenggam sumber  daya  0  dan  menunggu  sumber daya  1,  pada  saat  itu  pula  sumber  daya 1  sedang  digenggam  oleh  proses  1 yang  sedang  menunggu  sumber  daya  0 yang  sedang  digenggam  proses  0.

Slide66Syarat-syarat perlu bagi terjadinya Deadlock Mutual exclusion (Mutual Exclution Condition) Tiap sumber daya saat itu diberikan pada tepat satu proses Kondisi genggam dan tunggu (Hold and Wait Condition) Proses-proses yang sedang menggenggam sumber daya, menunggu sumber daya - sumber daya baru Kondisi non-pre-emption (Non-Pre-Emption Condition) Sumber daya sumber daya yang sebelumnya diberikan tidak dapat diambil paksa dari proses itu. Sumber daya – sumber daya harus secara eksplisit dilepaskan dari proses yang menggenggamnya Kondisi Menunggu secara sirkuler (Circular Wait Condition) Harus terdapat rantai sirkuler dari dua proses atau lebih, masing-masing menunggu sumber daya yang digenggam oleh anggota berikutnya pada rantai itu

Slide77Metode-metode mengatasi deadlock 1. Metode pencegahan terjadinya deadlock (Deadlock Prevention) 2. Metode penghindaran terjadnya deadlock (Deadlock Avoidance) 3. Metode deteksi dan pemulihan dari deadlock (Deadlock Detection and Recovery)

Slide88Metode pencegahan terjadinya deadlock    Untuk mengatasi deadlock cara inilah yang paling aman, yaitu dengan sebelum adanya dan terjadinya deadlock kita telah melakukan upaya agar deadlock tidak terjadi.

Slide99Metode pencegahan terjadinya deadlock Meniadakan mutual exclusion Dilakukan dengan cara spooling peralatan-peralatan yang harus didedikasikan untuk suatu proses Masalah pada teknik ini :  Tidak setiap sumber daya eksklusif dapat di spooling  Kompetisi terhadap ruang disk untuk spooling dapat menuntun ke deadlock Meniadakan kondisi hold and wait Teknik ini berbasis pada semua atau tidak sama sekali Masalah pada teknik ini :  Sukar mengetahui lebih dulu semua sumber daya yang diperlukan  Sangat tidak efisien Meniadakan kondisi non-pre-emption Jika proses sedang dieksekusi maka proses yang lain jangan dieksekusi secara bersamaan Masalah pada teknik ini : Akan membuat proses-proses menghasilkan hasil tak benar Meniadakan kondisi menunggu sirkuler Kondisi ini dapat dilakukan dengan beberapa cara : Proses hanya dibolehkan menggenggam satu sumber daya pada satu saat Penomoran global semua sumber daya

Slide1010Metode penghindaran terjadinya deadlock    Apabila telah ada tanda-tanda akan terjadinya deadlock kita dapat mengatasinya dengan cara menghindar dari terjadinya deadlock semaksimal mungkin

Slide1111Metode penghindaran terjadinya deadlock       Dalam metode ini memiliki dua pernyataan yang harus dimengerti, yaitu : State selamat (Safe State) Metode penghindaran yang diberikan pernyataan ini dikarenakan terdapat cara memenuhi semua permintaan yang ditunda tanpa menghasilkan deadlock dengan menjalankan proses-proses secara hati-hati mengikuti suatu urutan tertentu State tak selamat (Unsafe State) Metode penghindaran yang diberikan pernyataan ini dikarenakan tidak terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan. State dapat berubah menjadi state tak selamat bila alokasi sumber daya tak terkendali. Tetapi state tak selamat bukan berarti deadlock, hanya menyatakan bahwa state tersebut berkemungkinan menuju deadlock.

Slide1212Metode penghindaran terjadinya deadlock Diberi  contoh  kasus  yang  sama  untuk  masing-masing  state:  Contoh state selamat 1 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 2 10 B 1 3 C 3 7 Tersedia                                   4 Terjadi kasus seperti diatas, dan akan diselesaikan dengan cara:

Slide1313Metode penghindaran terjadinya deadlock Contoh state selamat 2 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 2 10 B 1 3 C 7 7 Tersedia                                   0 3 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 2 10 B 1 3 C 0 - Tersedia                                   7 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 2 10 B 3 3 C 0 - Tersedia                                   5 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 2 10 B 0 - C 0 - Tersedia                                   8 4 5

Slide1414Metode penghindaran terjadinya deadlock Contoh state selamat Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 10 10 B 0 - C 0 - Tersedia                                   0 6 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 0 - B 0 - C 0 - Tersedia                                  1 0 7 Dari pengalokasian sumber daya di atas dapat kita simpulkan bahwa suatu kasus dapat kita katakan state selamat apabila pengalokasian sumber daya dilakukan secara berurutan dengan menyelesaikan lebih dulu proses mana yang dapat segera diselesaikan dengan sumber daya yang digenggam dan sumber daya yang tersedia, kemudian setelah selesai lanjut ke proses selanjutnya dengan cara yang sama dan begitu seterusnya sampai semua proses dapat diselesaikan dengan baik.

Slide1515Metode penghindaran terjadinya deadlock 4 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 2 10 B 1 3 C 3 7 Tersedia                                   4   Contoh state tak selamat Terjadi kasus seperti diatas, dan akan diselesaikan dengan cara:

Slide1616Metode penghindaran terjadinya deadlock Contoh state tak selamat 2 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 4 10 B 2 3 C 3 7 Tersedia                                   1 3 Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 4 10 B 3 3 C 3 7 Tersedia                                   0

Slide1717Metode penghindaran terjadinya deadlock Contoh state tak selamat Proses Jumlah sumber daya digenggam Maksimum sumber daya dibutuhkan A 4 10 B 0 - C 3 7 Tersedia                                   3 4 Dari pengalokasian sumber daya di atas dapat kita simpulkan bahwa suatu kasus dapat kita katakan state tak selamat apabila pengalokasian sumber daya dilakukan secara random atau acak dan tidak dapat menyelesaikan salah satu proses yang dijalankan atau lebih  karena kekurangan sumber daya.

Slide1818Metode penghindaran terjadinya deadlock Algoritma Banker oleh Dijkstra Dalam metode algoritma banker ini sistem operasi dapat memberikan akses sumber daya atau menolak masing-masing permintaan, tetapi jika ditolak, proses masih menggenggam sumber daya yang telah dialokasikan untuknya dan menunggu waktu berhingga sampai permintaan dapat diberikan. Sistem hanya memberikan permintaan yang menghasilkan state selamat. Permintaan proses yang akan menghasilkan state tak selamat secara berulang ditolak sampai permintaan dapat dipenuhi. Intinya pada algoritma banker ini sistem selalu memelihara agar dalam kondisi state selamat

Slide1919Metode penghindaran terjadinya deadlock Algoritma Banker oleh Dijkstra Adapun kelemahan algoritma banker : Proses-proses jarang mengetahui di awal proses jumlah maksimum sumber daya yang akan diperlukan Jumlah proses tidak tetap, secara dinamis beragam begitu pemakai-pemakai baru login dan logout Sumber daya yang dihitung sebagai tersedia dapat saja tiba-tiba dicopot sehingga sebenarnya menjadi tidak tersedia Proses-proses haruslah independen, yaitu urutan proses-proses dieksekusi tidak dibatasi oleh kebutuhan sinkronisasi antar proses Algoritma menghendaki memberikan semua permintaan selama waktu yang berhingga Algoritma menghendaki client-client mengembalikan sumber daya setelah suatu waktu yang berhingga

Slide2020Metode deteksi dan pemulihan deadlock Langkah-langkah metode deteksi dan pemulihan deadlock : 1. Deteksi adanya deadlock 2. Pemulihan dari deadlock

Slide2121Metode deteksi dan pemulihan deadlock 1. Deteksi adanya deadlock Deteksi deadlock adalah teknik untuk menentukan apakah deadlock terjadi serta mengidentifikasi proses-proses dan sumber daya-sumber daya yang terlibat deadlock. Periode yang dilakukan dengan cara memonitor permintaan dan pelepasan sumber daya dengan menggunakan algoritma deteksi deadlock

Slide2222Metode deteksi dan pemulihan deadlock 2. Pemulihan dari deadlock Begitu sistem terdapat deadlock, deadlock harus diputuskan dengan menghilangkan satu syarat atau lebih. Teknik pemulihan yang biasa digunakan adalah menghilangkan (dengan suspend atau kill) proses-proses dari sistem dan pengklaiman kembali (reclaim) sumber daya yang dipegang proses-proses itu.

Slide2323Metode deteksi dan pemulihan deadlock 2. Pemulihan dari deadlock Pemulihan dari deadlock dirumitkan oleh faktor-faktor berikut : Belum tentu dapat menentukan adanya deadlock secepatnya Kebanyakan sistem mempunyai fasilitas-fasilitas buruk untuk men- suspend proses, menghilangkan dari sistem dan me-resume proses di lain waktu. Pada siste waktu nyata yang harus berfungsi terus-menerus, proses-proses tidak dapat di-suspend dan di- resume Bahkan jika terdapat kemampuan suspend dan resume yang efektif. Kemampuan ini melibatkan sejumlah overhead berarti dan memerlukan perhatian operator yang berkemampuan tinggi. Operator semacam ini tidak selalu tersedia. Pemulihan memerlukan sejumlah kerja yang berarti

Slide2424Metode deteksi dan pemulihan deadlock 2. Pemulihan dari deadlock Pendekatan-pendekaan penyelesaian pemulihan deadlock : Abaikan (singkirkan) semua proses yang terlibat deadlock Back-up semua proses yang terlibat deadlock ke suatu checkpoint yang didefinisikan sebelumnya dan jalankan kembali semua proses itu Secara berurutan abaikan (singkirkan) proses-proses sampai deadlock tidak ada lagi Secara berurutan preempt sumber daya-sumber daya sampai tidak ada deadlock lagi

Slide2525Metode-metode penanggulangan deadlock Prinsip Kebijaksanaan alokasi sumber daya Skema-skema Keunggulan utama Kelemahan utama Pencegahan Konsevatif, menurunkan efisiensi sumber daya Meminta semua sumber daya sekaligus   Bekerja bagus untuk proses-proses   yang melakukan satu barisan aktifitas   tunggal    Tidak  diperlukan  preemption    Tidak  efisien    Memerlukan  waktu     tunda  inisiasi  proses Preemption    Cocok  ketika  diterapkan  ke  sumber  daya    yang  state-nya  dapat  disimpan  dan    dikembalikan  dengan  mudah    Preempt  akan  terjadi  lebih    sring  daripada  yang  diperlukan    Dapat  menjadi  restart  yang    siklus Pengurutan sumber daya    Layak  dipaksakan  lewat  pemeriksaan    saat  kompilasi    Tidak  perlu  komputasi  saat  berjalan    karena  masalah  diselesaikan  sewaktu    perancangan  sistem    Preempt  tanpa  banyak    penggunaan    Tak  mengijinkan  permintaan    sumber  daya  yang  meningkat Deteksi Lebih bebas, sumber daya yang diminta diberikan bila mungkin Dijalankan secara periodik    Tak  pernah  terdapat  waktu  tunda  inisiasi     proses    Memberi  fasilitas  penanganan  on-line    Kehilangan  preempt  yang     inheren Penghindaran Memilih jalan tengah antara deteksi dan pencegahan Memanipulasi untuk menemukan pada setidaknya satu jalur selamat    Tidak  diperlukan  preemption    Kebutuhan-kebutuhan  sumber    daya  masa  datang  harus    diketahui    Proses-proses  dapat  diblok     untuk  periode  yang  lama Garis besar metode-metode penanggulangan deadlock Deadlock & Starvation

Slide2626Strategi penanggulangan deadlock terpadu        Strategi penanggulangan deadlock terpadu yang disarankan oleh Silberschatz, yaitu : Kelompokkan sumber daya-sumber daya menjadi sejumlah kelas sumber daya Gunakan strategi pengurutan linear seperti yang didefinisikan pada pencegahan menunggu sirkular. Strategi ini digunakan untuk mencegah deadlock di antara kelas-kelas sumber daya berbeda Dalam satu kelas sumber daya, gunakan algoritma yang paling cocok untuk kelas-kelas sumber daya itu

Slide2727Masalah Kongkurensi    Masalah kongkurensi adalah masalah tentang proses-proses yang berkompetisi (bersaing) mendapatkan akses eksklusif atas sejumlah sumber daya yang terbatas

Slide2828Masalah Kongkurensi Dinning Philosophers Problem Masalah ini pertama kali diberikan oleh Djikstra pada 1965, masalahnya sebagai berikut: Lima filosof duduk di sekeliling meja, tiap filosof mempunyai sepiring spaghetti. Spaghetti begitu ruwet dan licin sehingga untuk makan memerlukan dua garpu sekaligus. Hidup filosof hanya berisi dua periode bergantian, yaitu: makan dan berfikir. (ini hanya abstraksi untuk mempermudah karena aktivitas-aktivitas lain tidak relevan). Ketika filosof lapar, filosof mencoba memperoleh garpu kanan dan kiri sekaligus dengan urutan manapun. Jika sukses memperoleh dua garpu sekaligus, filosof makan. Kemudian telah selesai makan, filosof meletakkan kembali garpunya dan melanjutkan berfikir. Pertanyaan pokok: Dapatkah ditulis program yang harus dikerjakan tiap filosof dan tak pernah secara permanen mengendalikannya.

Slide2929Masalah Kongkurensi Write-Readers Problem Masalah pembaca dan penulis adalah memodelkan pengaksesan ke basis data. Masalahnya sebagai berikut: Misalkan terdapat basis data besar, seperti sistem reversi penerbangan dengan proses-proses berkompetisi untuk membaca dan menulis. Aturannya terhadap persaingan yang mengijinkan banyak proses membaca basis data pada saat yang sama. Tapi jika terdapat satu proses menulis (yaitu:mengubah) basis data, tak ada proses lain yang boleh mengakses basis data baik untuk membaca ataupun menulis. Pertanyaan pokok: Bagaimana program untuk penulis dan pembaca?

Slide3030Masalah Kongkurensi Sleeping Barber Problem Masalah pemangkas yang mengantuk sebagai berikut: Salon pangkas rambut mempunyai satu pemangkas rambut atau kursi pemangkasan, dan kursi untuk pelanggan-pelanggan menunggu, jika ada. Jika tidak ada pelanggan, pemangkas duduk di kursi pemangkasan dan tidur. Ketika pelanggan datang, dia membangunkan pemangkas. Jika pelanggan-pelanggan berikutnya datang, sementara pemangkas sedang memotong rambut pelanggan lain, pelanggan-pelanggan itu duduk di kursi tunggu (jika masih terdapat kursi tunggu yang kosong) atau meninggalkan salon (jika semua kursi tunggu telah penuh). Pertanyaan pokok: Bagaimana menulis program pemangkas(barber) dan pelanggan (customer) tanpa masuk ke kondisi pacu (race condition).