deadlock

DEADLOCKDeadlock
 Terjadi jika proses menunggu suatu kejadian
tertentu yang tidak pernah terjadi
 Sekumpulan proses berkondisi deadlock bila
setiap proses yang ada di kumpulan
menunggu suatu kejadian yang hanya dapat
dilakukan proses lain yang juga berada di
kumpulan itu. Pengoperasian I/O
 meminta (request) : meminta pelayanan
perangkat masukan/keluaran
 memakai (use) : memakai perangkat
masukan / keluaran
 melepaskan (release) : melepaskan
pemakaian perangkat masukan/keluaran
Syarat Deadlock
 mutual exclusion (mutual exclusion conditional)
 tiap sumber daya saat itu diberikan pada tepat 1 proses.
 kondisi genggam dan tunggu (hold and wait)
 proses-proses yang sedang menggenggam sumber daya,
menunggu sumber daya-sumber daya baru.
 kondisi non-preemption (non-preemption condition)
 sumber daya-sumber daya yang sebelumnya diberikan
tidak dapat diambil paksa dari proses itu.Sumber daya
harus secara explisit 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. Syarat Deadlock
 Terjadi deadlock bila terdapat ketiga kondisi
itu, tetapi adanya ketiga kondisi itu belum
berarti terjadi deadlock.
 Deadlock benar-benar terjadi bila syarat
keempat terpenuhi. Kondisi keempat
merupakan keharusan bagi terjadinya
deadlock.
 Deadlock bisa terjadi pada saat proses akan
mengakses objek seperti file,device, dll secara
tidak semestinya. Objek tersebut dinamakan
resource. Jenis Resource
 preemtable resource
 resource yang dapat diambil dan dilepas dari
proses yang sedang memakainya tanpa
memberikan efek apapun pada proses tersebut.
 Non-preemtable resource
 resource tidak dapat diambil dari proses yang
sedang membawanya, karena akan
mengakibatkan kegagalan komputasi, contoh :
printer, bila suatu proses sedang menggunakan
printer untuk mencetak, maka proses lain tidak
dapat menggunakan printer tersebut. Metode Mengatasi Deadlock
 Pencegahan deadlock
 Tiap proses harus meminta semua sumber daya
yang diperlukan secara sekaligus dan tidak
berlanjut sampai semuanya diberikan.
 Jika proses sedang memegang sumberdaya
tertentu, untuk permintaan berikutnya proses
harus melepas dulu sumberdaya yang
dipegangnya.
 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. Metode Mengatasi Deadlock
 Penghindaran deadlock
 Menghindari deadlock dengan cara hanya
memberi akses ke permintaan sumber daya
yang tidak mungkin menimbulkan deadlock.
 jika pemberian akses sumber daya tidak mungkin
menuju deadlock, sumber daya diberikan ke
peminta.
 Jika 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. Metode Mengatasi Deadlock
 Agar 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.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. Safe State
• 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. Safe State
• Contoh :Safe State
• Contoh :
• State dinyatakan selamat (safe) karena
terdapat barisan pengalokasian yang dapat
memungkinkan semua proses selesai.
Dengan penjadwalan secara hati-hati, sistem
dapat terhindarkan dari deadlock. Barisan
tersebut adalah : Unsafe State
• State tak selamat (unsafe state) : jika tidak
terdapat cara untuk memenuhi semua
permintaan yang saat ini ditunda dengan
menjalankan proses-proses dengan suatu
urutan.
• Contoh :
• State dibawah ini sama dengan state
selamat sebelumnya, tapi dapat berubah
menjadi state tak selamat bila alokasi
sumber daya tak terkendali. Deteksi dan Pemulihan Deadlock
• 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 apapunDeteksi dan Pemulihan Deadlock
• Teknik pemulihan yang biasa digunakan
adalah menghilangkan (suspend / kill)
proses-proses dari sistem dan pengklaiman
kembali sumberdaya yang dipegang proses-
proses tersebut.
• Proses yang dihilangkan biasanya cacat
tetapi proses lain dapat menyelesaikan
prosesnyaPemulihan Deadlock
• singkirkan semua proses yang terlibat deadlock
• backup semua proses yang terlibat deadlock ke
suatu check point yang didefinisikan sebelumnya
dan jalankan kembali proses itu.
• secara berurutan abaikan proses-proses sampai
deadlock tidak terjadi lagi. Urutan proses yang
dipilih untuk disingkirkan berdasar kriteria ongkos
minimum.
• secara berurutan preempt sumberdaya-
sumberdaya sampai tidak ada deadlock lagi.
Proses yang kehilangan sumber daya karena
preemption harus dikembalikan (roll-back) ke titik
sebelum memperoleh sumber daya.Kriteria Pemilihan Proses Yang
Akan Disingkirkan
• waktu pemrosesan yang dijalankan paling
kecil
• jumlah baris keluaran yang diproduksi paling
kecil
• mempunyai estimasi sisa waktu eksekusi
terbesar
• jumlah total sumber daya terkecil yang telah
dialokasikan
• prioritas terkecil. Kriteria Pemilihan Proses Yang
Akan Disingkirkan
• Dalam penyingkiran proses, sistem harus
mengembalikan berkas-berkas yang telah
dimodifikasi oleh proses-proses yang
disingkirkan ke keadaan asli karena
berpengaruh terhadap konsistensi data
sistem itu.