Bab 7: Deadlock. Permasalahan Deadlock

Bab 7: Deadlock  Model system  Karakteristik deadlock  Metode penanganan deadlock  Pencegahan deadlock  Pengabaian deadlock  Pendeteksian deadlock  Perbaikan dari deadlock  Kombinasi penanganan deadlock

Operating System Concepts

Silberschatz, Galvin and Gagne 2002

8.1

Permasalahan Deadlock  Sekumpulan proses yang di-blok, dimana masing-masing

proses membawa resource dan menunggu mendapatkan resource yang dibawa proses lain dalam kumpulan tersebut  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, B diinisialisasi 1 P0

P1

wait (A); wait (B);


wait(B) wait(A)

8.2


1

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


8.3


Model Sistem  Jenis Resource R1, R2, . . ., Rm CPU cycles, memory space, I/O devices  Setiap S ti jenis j i resource Ri mempunyaii anggota t Wi  Setiap proses yang menggunakan resource melakukan

hal di bawah ini:  request  use  release


8.4


2

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.5


Resource-Allocation Graph

Sekumpulan vertek V dan sekumpulan edge/garid E.  V dibagi menjadi dua jenis:  P = {P1, P2, …, Pn}, sekumpulan semua proses dalam sistem  R = {R1, R2, …, Rm}, sekumpulan semua jenis resource yang beada dalam sistem  request edge – garis berarah P1  Rj  assignment edge – garis berarah Rj  Pi


8.6


3

Resource-Allocation Graph (Lanj.)  Proses

 Jenis resource dengan 4 anggota

 Pi meminta anggota dari Rj Pi Rj

 Pi membawa satu anggota dari Rj Pi Rj Operating System Concepts

8.7


Contoh Resource Allocation Graph


8.8


4

Resource Allocation Graph dengan Deadlock


8.9


Resource Allocation Graph dengan Siklus tetapi Tidak Terjadi Deadlock


8.10


5

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.


8.11


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.


8.12


6

Pencegahan Deadlock

Mencegah dari kemungkinan 4 karakteristik deadlock.  Mutual M t l Exclusion E l i – tidak tid k ttersedia di resource yang d dapatt

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


8.13


Pencegahan Deadlock (lanj.)  No Preemption –  Jikas sebuah proses membawa beberapa resource dan meminta resource lain yang tidak dapat segera dipenuhi 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 Ci l W Wait it – memberlakukan b l k k pemesanan tterlebih l bih

dahulu untuk total jenis resource yang dibutuhkan dan setiap proses meminta resource sesuai urutan nomor.


8.14


7

Pengabaian Deadlock Sistem harus mempunyai tambahan ketersediaan informasi sebelumnya  Model y yang g sangat g sederhana dan sangat g berguna. g

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.


8.15


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 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
dapat menunggu sampai semua Pj selesai. 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.


8.16


8

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.


8.17


Safe, Unsafe , Deadlock State


8.18


9

Algoritma Resource-Allocation Graph  Claim edge Pi  Rj mengindikasikan bahwa proses Pj

kemungkinan meminta resource Rj; direpresentasikan dengan garis putus-putus 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


8.19


Resource-Allocation Graph untuk Pengabaian Deadlock


8.20


10

Unsafe State pada Resource-Allocation Graph


8.21


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.


8.22


11

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 x m. Jika Allocation[i,j] = k maka Pi sedang dialokasikan k anggota dari Rj.  Need: matriks n x m. Jika Need[i,j] = k, maka Pi mungkin memerlukan k anggota dari Rj untuk menyelesaikan task/pekerjaan. Need [i,j] = Max[i,j] – Allocation [i,j].


8.23


Algoritma Safety 1. Misalnya Work dan Finish adalah vektor dengan panjang masing-masing m dan n. Inisialisasi: Work = Available Finish [i] = false untuk i - 1,3, 1 3 …, n. 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.


8.24


12

Algoritma Resource-Request untuk Proses Pi Request = vektor untuk meminta proses Pi. Jika Requesti [j] = k maka proses Pi menginginkan k anggota dari jenis resource Rj.

1. Jika Requesti  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 – Request q i;; • Jika safe  resource dialokasikan ke Pi. • jika unsafe  Pi harus menunggu dan state resourceallocation yang lama harus disimpan


8.25


Contoh Algoritma Banker  5 proses P0 sampai dengan P4; 3 jenis resource A

(10 anggota), B (5 anggota) dan C (7 anggota).  Snapshot pada waktuT0:

P0 P1 P2 P3 P4


Allocation ABC 010 200 302 211 002

Max ABC 753 322 902 222 433

8.26

Available ABC 332


13

Contoh Algoritma Banker (lanj.)  Isi dari matrik Need didefinisikan Max – Allocation.

Need ABC P0 743 P1 122 P2 600 P3 011 P4 431  Sistem dalam safe state jjika < P1, P3, P4, P2, P0> memenuhi kriteria algoritma safety.


8.27


Contoh: P1 Meminta (1,0,2)  Cek apakah Request  Available (apakah, (1,0,2)  (3,3,2) 

true). Allocation Need Available ABC ABC ABC P0 0 1 0 743 230 P1 3 0 2 020 P2 3 0 1 600 P3 2 1 1 011 P4 0 0 2 431  Eksekusi algoritma safety menunjukkan bahwa memenuhi kriteria safety.  Apakah permintaan (3,3,0) oleh P4 dapat dipenuhi?  Apakah permintaan (0,2,0) oleh P0 dapat dipenuhi? Operating System Concepts

8.28


14

Pendeteksian Deadlock  Mengijinkan sistem memasuki deadlock state  Algoritma deteksi  Skema perbaikan


8.29


Satu Anggota untuk Setiap Jenis Resource  Menggunakan graf wait-for  Node (titik) adalah proses-proses.  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 n adalah jumlah vertek dalam graf. graf


8.30


15

Resource-Allocation Graph dan Wait-for Graph

Resource-Allocation Graph


8.31

Hubungan wait-for graph


Beberapa Anggota untuk Setiap Jenis Resource  Available: vektor panjang m mengindikasikan 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 proses Pi sedang meminta anggota k lebih banyak untuk jenis resource Rj.


8.32


16

Algoritma Deteksi 1. Misalnya Work dan Finish adalah vektor panjang m dan n, diinisialisasi : (a) Work = Available (b) For i = 1,2, …, n, jika Allocationi  0, maka Finish[i] = false; lainnya, Finish[i] = true.

2. Temukan indeks i yang memenuhi 2 hal di bawah ini: (a) Finish[i] == false (b) Requesti  Work Jika tidak ada i yang memenuhi, ke langkah 4. 3. Work = Work + Allocationi Finish[i] = true ke langkah 2. 4.

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 x n2) untuk mendeteksi apakah sistem dalam deadlock state.


8.33


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 waktu T0:

Allocation Request Available ABC ABC ABC P0 0 1 0 000 000 P1 2 0 0 202 P2 3 0 3 000 P3 2 1 1 100 P4 0 0 2 002  Urutan akan menghasilkan Finish[i] = true untuk semua i.


8.34


17

Contoh Algoritma Deteksi (lanj.)  P2 meminta tambahan anggota jenis C.

Request ABC P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2  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.


8.35


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 sewenang-

wenang, mungkin ada banyak siklus dalam resource graph sehingga kita tidak akan bisa membedakan mana dari banyak proses deadlock yang "menyebabkan" deadlock.


8.36


18

Perbaikan dari Deadlock: Menghentikan Proses

 Menghentikan semua proses yang deadlock.  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 p proses yyang g harus dipenuhi p  Berapa proses yang perlu dihentikan  Apakah proses interaktif atau batch?


8.37


Perbaikan dari Deadlock: Resource Preemption  Pilih korban – cost minimal.  Rollback – kembali ke beberapa safe state state, restart proses

pada state tersebut.  Starvation – proses yang dipilih sebagai korban selalu

sama, termasuk jumlah rollback menjadi faktor cost.


8.38


19

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.


8.39


Deadlock pada Trafik


8.40


20

Bab 7: Deadlock. Permasalahan Deadlock

Recommend Documents