sylabus materials for system when deadlock

materi terkait deadlock, apa itu deadlock? kapan terjadi deadlock? dan bagaimana bisa terjadi deadlock?

1. Deadlock

2. Materi
•Model system
•Karakteristik deadlock
•Metode penanganan deadlock
•Pencegahan deadlock
•Pengabaian deadlock
•Pendeteksian deadlock
•Perbaikan dari deadlock
•Kombinasi penanganan deadlock

3. Sumber Pembelajaran Mandiri
•Buku
•Textbook Silberschatz chapter 7
•File : Diktat Deadlock.pdf
•Video
•https://www.youtube.com/watch?v=Lm-i4JW1NUY
•https://www.youtube.com/watch?v=SLx6w0IMJkw
•Slide

4. Permasalahan Deadlock
•Kondisi dimana masing-masing proses membawa resource dan saling
menunggu mendapatkan resource yang dibawa proses lain
•Contoh
•Sistem mempunyai 2 tape drive
•P1 dan P2 masing-masing membawa satu tape drive dan masing-masing
memerlukan tape drive lainnya.
•Contoh lain
•semaphore A dan B diinisialisasi 1

5. Contoh Jembatan Penyebrangan
•Jalur hanya untuk satu arah
•Setiap bagian jembatan dianggap sebagai resource
•Jika terjadi deadlock, dapat dipecahkan jika satu mobil mundur
(melepas resource dan rollback)
•Beberapa mobil harus mundur jika terjadi deadlock
•Kemungkinan starvation

6. Model Sistem
•Jenis Resource R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
•Setiap jenis resource Ri mempunyai anggota Wi
•Setiap proses yang menggunakan resource melakukan hal di bawah ini:
orequest
ouse
orelease

7. Karakteristik Deadlock
Deadlock dapat terjadi jika terdapat 4 kondisi yang terjadi secara simultan
•Mutual exclusion: hanya satu proses pada satu waktu yang dapat menggunakan satu
resource.
•Hold and wait: sebuah proses membawa sedikitnya satu resource sedang menunggu
mendapatkan resource tambahan yang dibawa oleh proses-proses lain
•No preemption: sebuah resource dapat dibebaskan hanya oleh proses yang
membawanya, setelah proses menyelesaikan task/pekerjaan
•Circular wait: terdapat sekumpulan {P0, P1, …, P0} dari proses yang menunggu
dimana P0 menunggu resource yang dibawa oleh P1, P1 menunggu resource yang
dibawa oleh P2 , …, Pn–1 menunggu resource yang dibawa oleh Pn, dan P0 menunggu
resource yang dibawa oleh P0

8. Resource-Allocation Graph
Sekumpulan vertek V dan sekumpulan edge/garid E.
•V dibagi menjadi dua jenis:
oP= {P1, P2, …, Pn}, sekumpulan semua proses dalam sistem
oR= {R1, R2, …, Rm}, sekumpulan semua jenis resource yang berada dalam sistem
•request edge – garis berarah P1 Rj
→
•assignment edge – garis berarah Rj P
→

9. Resource-Allocation Graph (Cont.)
•Proses
•Jenis resource dengan 4 anggota
•Pi meminta anggota dari Rj
•Pi membawa satu anggota dari Rj
P
i
R
j
P
i
R
j

10. Contoh Resource Allocation Graph

11. Resource Allocation Graph dengan
Deadlock

12. Resource Allocation Graph dengan Siklus
tetapi Tidak Terjadi Deadlock

13. Fakta Dasar
•Jika graph tidak terdapat siklus tidak terjadi deadlock.
→
•Jika graph terdapat siklus
→
•Jika hanya satu anggota tiap jenis resource, maka terjadi
deadlock.
•Jika terdapat beberapa anggota pada satu jenis resource, maka
kemungkinan terjadi deadlock.

14. Metode Penanganan Deadlock
•Menjamin bahwa sistem tidak pernah memasuki deadlock state.
•Mengijinkan sistem memasuki deadlock state dan kemudian dilakukan
perbaikan.
•Mengabaikan permasalahan deadlock dan menganggap deadlock tidak
pernah terjadi dalam sistem; digunakan sebagian besar sistem operasi,
termasuk UNIX.

15. Pencegahan Deadlock

16. Pencegahan Deadlock
Mencegah dari kemungkinan 4 karakteristik deadlock.
Mutual Exclusion – tidak tersedia resource yang dapat digunakan
bersama-sama; semua proses membawa resource yang tidak dapat
digunakan bersama-sama. tidak dapat dicegah
→
Hold and Wait – harus menjamin bahwa ketika sebuah proses meminta
resource, proses tersebut tidak sedang membawa resource
Sebelum eksekusi proses perlu meminta dan dialokasikan semua
resource, atau memperbolehkan proses meminta resource hanya jika
proses tidak membawa resource
Utilitas resource menjadi rendah; kemungkinan starvation

17. Pencegahan Deadlock (lanj.)
•No Preemption –
Jika sebuah proses membawa beberapa resource dan meminta resource lain yang
tidak dapat segera dipenuhi, maka semua resource yang sedang dibawa proses
tersebut harus dibebaskan
Resource yang dapat ditunda (preempt resource) ditambahkan ke daftar resource
untuk proses yang menunggu
Proses akan di-restart ketika proses hanya mendapatkan kembali resource lama
setelah meminta resource baru.
•Circular Wait – memberlakukan pemesanan terlebih dahulu untuk total
jenis resource yang dibutuhkan dan setiap proses meminta resource
sesuai urutan nomor.

18. Pengabaian Deadlock
Sistem harus mempunyai tambahan ketersediaan informasi sebelumnya
•Model yang sangat sederhana dan sangat berguna. Setiap proses perlu
mendeklarasikan jumlah maksimal setiap jenis resource yang
dibutuhkan.
•Algoritma deadlock-avoidance secara dinamis menguji state dari
resource-allocation untuk menjamin tidak pernah terjadi kondisi
circular-wait.
•State dari resource-allocation ditentukan dengan jumlah resource
yang tersedia dan yang dialokasikan dan jumlah maksimal kebutuhan
dari proses.

19. Safe State (state aman)
•Jika sebuah proses meminta resource yang tersedia, sistem harus
memutuskan apakah alokasi tersebut menyebabkan sistem masih
dalam safe state.
•Sistem dalam safe state jika semua proses dalam kondisi aman.
•Sekumpulan proses <P1, P2, …, Pn> dikatakan aman jika untuk setiap
Pi, resource yang diminta Pi masih dapat dipenuhi dengan resource
yang tersedia dan resource yang dibawa oleh semua Pj, dimana j<i.
•Jika resource yang diperlukan Pi tidak segera tersedia, maka Pi
dapatmenunggusampaisemua P selesai
•Jika Pj selesai, Pi dapat memperoleh resource yang diperlukan, mengeksekusinya,
menghasilkan nilai dari resource yang dialokasikan dan terminasi.
•Jika Pi diterminasi, Pi+1 dapat memperoleh resource yang diperlukan dan seterusnya.

20. Fakta Dasar
•Jika sistem dalam state aman tidak terjadi deadlock.
→
•Jika sistem dalam state tidak aman kemungkinan terjadi deadlock.
→
•Pengabaian menjamin sistem tidak pernah masuk ke state tidak
→
aman.

21. Safe, Unsafe , Deadlock State

22. Algoritma Resource-Allocation Graph
•Claim edge Pi Rj mengindikasikan bahwa proses Pj kemungkinan
→
meminta resource Rj; direpresentasikan dengan garis putus-putus
dengan garis putus-putus.
•Claim edge berubah menjadi request edge jika proses meminta
resource.
•Jika suatu resource dibebaskan oleh proses, assignment edge
berubah menjadi claim edge.
•Resource harus ditentukan sebelumnya dalam sistem

23. Resource-Allocation Graph untuk
Pengabaian Deadlock

24. Unsafe State pada Resource-Allocation
Graph

25. Algoritma Banker
•Untuk banyak anggota resource dalam satu jenis resource (Multiple
instances).
•Setiap proses harus ditentukan sebelumnya penggunaan maksimum.
•Jika sebuah proses meminta resource maka proses harus menunggu.
•Jika sebuah proses mendapatkan semua resource maka harus
dikembalikan dalam suatu batasan waktu.

26. Struktur Data untuk Algoritma Banker
Misalnya n= jumlah proses, dan m = jumlah jenis resource.
•Available: vektor panjang m. jika available[j] = k, terdapat K anggota
dari jenis resource Rj tersedia.
•Max: matriks n x m. Jika Max [i,j] = k, maka proses Pi mungkin
meminta paling banyak k anggota dari jenis resource Rj
•Allocation: matriks n xm. Jika Allocation[i,j] = kmakaPi sedang
dialokasikan kanggota dari Rj.
•Need: matriks n xm. Jika Need[i,j] =k, makaPi mungkin memerlukan
kanggota dari Rj untuk menyelesaikan task/pekerjaan.
Need[i,j] = Max[i,j] –Allocation[i,j].
.

27. Algoritma Safety
1. Misalnya Work dan Finishadalah vektor dengan panjang masing-masing m dan
n. Inisialisasi:
Work = Available
Finish[i]=false untuki -13 n Finish [i] =false untuki -1,3, …, n.
2. Cari dan i sebagai berikut:
(a) Finish[i] = false
(b) Needi Work

Jika tidak ada i yang memenuhi, ke langkah 4.
3.Work= Work + Allocationi
Finish[i] =true
ke langkah 2.
4. Jika Finish[i] == true untuk semua i, maka sistem dalam
•safe state.

28. Algoritma Resource-Request untuk Proses
Pi
Request= vektor untuk meminta proses Pi. Jika Requesti [j] = kmaka proses Pi
menginginkan kanggota dari jenis resource Rj.
1.JikaRequesti ≤ Needi ke langkah 2. Lainnya, terjadi kondisi error, karena
proses meminta resource melebihi maksimum.
2.Jika Requesti ≤ Available, ke langkah 3. Lainnya, Pi harus menunggu, karena
resource tidak tersedia.
3.Melakukan alokasi resource yang diminta ke Pi dengan memodifikasi state
sebagai berikut:
Available= Available -Requesti;
Allocationi = Allocationi + Requesti;
Needi =Needi –Requesi;
•Jika safe resource dialokasikan ke Pi.
→
•Jika unsafe Pi harus menunggu dan state resourceallocation yang lama harus
→
disimpan

29. Contoh Algoritma Banker
•5 proses P0 sampai dengan P4; 3 jenis resource A(10 anggota), B(5
anggota) dan C(7 anggota).
•Snapshot pada waktuT:

30. Contoh Algoritma Banker (lanj.)
•Isi dari matrik Need didefinisikan Max – Allocation
•Sistem dalam safe state jika < P1, P3, P4, P2, P0> memenuhi j 1 3 4 2
0 kriteria algoritma safety.

31. Contoh: P1Meminta (1,0,2)
•Cek apakah Request ≤ Available (apakah, (1,0,2) ≤ (3,3,2) true)
→
Eksekusi algoritma safety menunjukkan bahwa < P1, P3, P4,P0, P2 > memenuhi kriteria safety.
•Apakah permintaan (3,3,0) oleh P4dapat dipenuhi?
•Apakah permintaan (0,2,0) oleh P0 dapat dipenuhi?

32. Pendeteksian Deadlock

33. Pendeteksian Deadlock
•Mengijinkan sistem memasuki deadlock state
•Algoritma deteksi
•Skema perbaikan

34. Satu Anggota untuk Setiap Jenis
Resource
•Menggunakan graf wait-for
•Node (titik) adalah proses-proses.
•P Pjika PmenungguP Pi Pj jika Pi menunggu Pj
 
•Secara periodik menjalankan algoritma yang mencari siklus pada
graf.
•Algoritma untuk mendeteksi siklus dalam suatu graf membutuhkan
operasi sebesar n2 , dimana nadalah jumlah vertek dalam graf

35. Resource-Allocation Graph dan Wait-for
Graph

36. Beberapa Anggota untuk Setiap Jenis
Resource
•Available : vektor panjang mmengindikasikan jumlah resource yang tersedia
untuk setiap jenis resource.
•Allocation : matriks n x m mendefinisikan jumlah resource dari setiap jenis
resource yang sedang dialokasikan untuk setiap proses.
•Request : matriks n x m mengindikasikan permintaan saat ini dari setiap
proses. Jika Request[ij] = k, maka saat ini dari setiap proses. Jika Request
[ij] k, maka proses Pi sedang meminta anggota k lebih banyak untuk jenis
resource Rj

37. Algoritma Deteksi
•Misalnya Work dan Finish adalah vektor panjang m dan n, diinisialisasi :
•Work = Available
•For i = 1,2, …,n, jika Allocation i ≠ 0, maka Finish[i] = false; lainnya, Finish[i] = true.
•Temukan indeksi yang memenuhi 2 hal di bawah ini:
•Finish[i] == false
•Requesti ≤ Work
Jika tidak adai yang memenuhi, ke langkah 4.
•Work = Work+ Allocationi
Finish[i] = true
ke langkah 2.
•Jika Finish[i] == false, untuk beberapa i, 1 ≤ i ≤ n, maka sistem dalam deadlock state.
Sehingga, jika Finish[i] == false, maka Pi deadlock.
Algoritma memerlukan operasi sebanyak O(m xn) untuk mendeteksi apakah sistem
dalam deadlock state.

38. Contoh Algoritma Deteksi
•5 proses yaitu P0 s/d P4; 3 jenis resource A (7 anggota), B (2
anggota), dan C(6 anggota).
•Snapshot pada waktuT: Snapshot pada waktu T0:

Urutan <P0, P2, P3, P1, P4> akan menghasilkan Finish[i] = true untuk semua i.

39. Contoh Algoritma Deteksi (lanj.)
•P2 meminta tambahan anggota jenis C.
•State dari sistem ?
Apakah resource yang dibawa proses P0 dapat di-klaim? Tapi resource menjadi tidak mencukupi
untuk memenuhi permintaan proses-proses yang lain.
Terjadi deadlock, terdiri dari proses P1, P2, P3, dan P4

40. Penggunaan Algoritma Deteksi
•Kapan dan berapa sering, sangat tergantung pada:
•Berapa sering deadlock yang sama terjadi?
•Berapa banyak proses yang perlu di roll back?
•Satu untuk setiap siklus disjoint
•Jika algoritma deteksi dipanggil secara sewenangwenang, mungkin ada
banyak siklus dalam resource graph sehingga kita tidak akan bisa
membedakan mana dari banyak proses deadlock yang "menyebabkan"
deadlock.

41. Perbaikan dari Deadlock

42. Perbaikan dari Deadlock: Menghentikan
Proses
•Menghentikan semua proses yang deadlock.
•Menghentikan satu demi satu proses pada satu waktu
•Menghentikan satu demi satu proses pada satu waktu sampai siklus deadlock
dieliminasi.
•Bagaimana urutan pemilihan proses yang dihentikan?
•Prioritas proses
•Berapa lama proses berjalan dan berapa lama lagi selesai
•Resource dari proses yang digunakan
•Resource dari proses yang harus dipenuhi
•Berapa proses yang perlu dihentikan
•Apakah proses interaktif atau batch?

43. Perbaikan dari Deadlock: Resource
Preemption
•Pilih korban – cost minimal.
•Rollback kembali ke beberapa safe state restart proses pada state
tersebut.
•Starvation – proses yang dipilih sebagai korban sela sama, termasuk
jumlah rollback menjadi faktor cost.

44. Pendekatan Kombinasi untuk Penanganan
Deadlock
•Kombinasi 3 pendekatan dasar
•Pencegahan (prevention)
•Pengabaian (avoidance)
•Pendeteksian (detection)
•Memungkinkan menggunakan pendekatan optimal untuk setiap
resource dalam sistem.
•Melakukan partisi resource dalam kelompok pemesanan secara
hierarki.
•Menggunakan teknik yang tepat untuk menangai deadlock dalam
setiap kelompok.

45. Deadlock pada Trafik

46. Terima Kasih