Sistem Operasi 2009 Pertemuan 6
Concurrency: Deadlock & Starvation Husni Lab. Sistem Komputer & Jaringan Teknik Informatika Univ. Trunojoyo
Deadlock (1) • Permanent blocking dari sekumpulan proses yang saling bersaing mendapatkan sumber daya sistem atau komunikasi • Tidak ada solusi yang efisien • Mencakup kebutuhan yang bertentangan bagi sumber daya oleh dua atau lebih proses
2
Deadlock (2)
3
Deadlock (3)
4
Deadlock (4)
5
Sumber Daya Reusable (1) • Digunakan hanya oleh satu proses pada satu waktu dan tidak dihabiskan oleh penggunaan tersebut • Proses memperoleh sumber daya, kemudian dilepaskan agar dapat digunakan (ulang, reuse) oleh proses lain
6
Sumber Daya Reusable (2) • Termasuk: Processor, Channel I/O, memory utama & sekunder, perangkat, dan struktur data seperti file, database, dan semaphore • Deadlock terjadi jika setiap proses memegang satu sumber daya dan meminta sumber daya lain
7
Sumber Daya Reusable (3)
8
Sumber Daya Reusable (4) • Space (ruang di memory) tersedia bagi alokasi 200 KB, dan deretan kejadian berikut terjadi P1
P2
...
...
Request 80 Kbytes;
Request 70 Kbytes;
Request 60 Kbytes;
Request 80 Kbytes;
...
...
• Deadlock terjadi jika kedua proses bergerak ke permintaan kedua mereka 9
Sumber Daya Consumable • Dibuat (produced) dan dihancurkan (consumed) • Termasuk: Interrupt, signal, message, dan informasi dalam buffer I/O • Deadlock dapat terjadi jika suatu receive message di-blocking • Dapat berupa kombinasi jarang dari event-event yang menyebabkan deadlock 10
Contoh Deadlock • Deadlock terjadi jika receive di-blocking P1
P2
...
...
Receive(P2);
Receive(P1);
...
...
Send(P2, M1);
Send(P1, M2);
11
Grafik Alokasi Resource • Directed graph yang menggambarkan status dari sistem sumber daya dan proses
12
Kondisi Untuk Deadlock (1) • Mutual exclusion – Hanya satu proses yang boleh menggunakan suatu sumber daya pada satu waktu
• Hold-and-wait – Suatu proses boleh memegang sumber daya yang dialokasikan selama menunggu assignment yang lain
13
Kondisi Untuk Deadlock (2) • No preemption – Tidak ada sumber daya yang dapat dipaksa dihilangkan dari suatu proses yang memegangnya
• Circular wait – Adanya rantai tertutup (closed-chain) prosesproses, sehingga setiap proses memegang setidaknya satu sumber daya yang diperlukan oleh proses berikutnya dalam rantai tersebut 14
Contoh Grafik Alokasi Resource
15
Contoh Grafik Alokasi Resource
16
Kemungkinan Deadlock • Mutual Exclusion • No preemption • Hold and wait
17
Terwujudnya Deadlock • • • •
Mutual Exclusion No preemption Hold and wait Circular wait
18
Pencegahan Deadlock (1) • Mutual Exclusion – Harus didukung oleh SO
• Hold and Wait – Mengharuskan suatu proses meminta (request) semua sumber daya yang dibutuhkannya pada satu waktu
19
Pencegahan Deadlock (2) • No Preemption – Proses harus melepaskan sumber daya dan merequest lagi – SO boleh men-preempt suatu proses untuk mengharuskannya melepas sumber dayanya
• Circular Wait – Definisikan suatu pengurutan linier dari jenisjenis sumber daya
20
Penghindaran (Avoidance) Deadlock • Suatu keputusan dibuat secara dinamis apakah permintaan alokasi sumber daya terkini akan, jika diijinkan, secara potential mengarah ke deadlock • Memerlukan pengetahuan permintaan proses mendatang
21
Pendekatan Deadlock Avoidance • Jangan mulai suatu proses jika tuntutannya dapat mengarah ke deadlock • Jangan ijinikan suatu permintaan sumber daya berikutnya (incremental) untuk suatu proses jika alokasi ini dapat mengarah ke deadlock
22
Penolakan Alokasi Resource • Dikenal sebagai algoritma banker • Status dari sistem adalah alokasi terkini dari sumber daya kepada proses • Status aman (safe) adalah dimana terdapat setidaknya satu deretan yang tidak menghasilkan deadlock • Status unsafe adalah status yang tidak aman 23
Penentuan Status Safe (1)
24
Penentuan Status Safe (2)
25
Penentuan Status Safe (3)
26
Penentuan Status Safe (4)
27
Penentuan Status Unsafe
28
Logika Deadlock Avoidance (1)
29
Logika Deadlock Avoidance (2)
30
Deadlock Avoidance • Kebutuhan resource maksimum harus dinyatakan sebelumnya • Proses di bawah konsiderasi harus bersifat independen; tidak ada kebutuhan sinkronisasi • Harus ada sejumlah fix sumber daya yang akan dialokasikan • Tidak ada proses yang boleh exit selama memegang resource 31
Deteksi Deadlock
32
Strategi Saat Deadlock Terdeteksi • Batalkan semua proses terdeadlock • Back up setiap proses terdeadlock ke beberapa checkpoint terdefinisi sebelumnya & restart semua proses – Mungkin terjadi original deadlock
33
Strategi Saat Deadlock Terdeteksi • Berikutnya batalkan proses terdeadlock sampai deadlock tidak ada • Kemudian preempt sumber daya sampai deadlock hilang (habis)
34
Keuntungan - Kerugian
35
Masalah Dining Philosophers (1)
36
Masalah Dining Philosophers (2)
37
Masalah Dining Philosophers (3)
38
Masalah Dining Philosophers (4)
39
Masalah Dining Philosophers (5)
40
Mekanisme Concurrency UNIX • • • • •
Pipes Messages Shared memory Semaphores Signals
41
Sinyal UNIX
42
Mekanisme Concurrency Linux • Menyertakan semua mekanisme yang terdapat pada UNIX • Operasi atomic berjalan tanpa interupsi dan tanpa interferensi
43
Operasi Atomic Linux (1)
44
Operasi Atomic Linux (1)
45
Spinlock Linux
46
Semaphore di Linux
47
Operasi Barrier Memory Linux
48
Primitif Sinkronisasi Thread Solaris • Kuncian mutual exclusion (mutex) • Semaphores • Kuncian banyak reader, satu writer (readers/writer) • Variabel kondisi
49
Struktur Data Sinkronisasi Solaris
50
Obyek Sinkronisasi Windows
51
Tugas Pertemuan 6 • Jelaskan mekanisme penanganan deadlock di Windows dan Linux! • Uraikan penyelesaian masalah Dinning Philosophers Problem! • Kerjakan problems 6.1 & 6.2!
52
