Sistem Operasi

DeadLock

soni@its-sby.edu

Deadlocks Masalah Deadlock - System Model - Karakteristik Deadlock

Metode mengatasi Deadlock - Mencegah Deadlock

Menghindari Deadlock

Mendeteksi Detection - Recovery dari Deadlock

Tujuan

Mendefinisikan deadlock, yang dapat mencegah proses menyelesaikan tugasnya

Mengetahui berbagai cara mencegah dan menghindari deadlock dalam sistem komputer.

Masalah Deadlock

Kakak beradik ingin menggambar masing-masing membutuhkan crayon dan kertas gambar

Mereka harus berbagi Kertas dan crayon

Mereka akan melakukan operasi ATOMIC yang harus selesai menggambar dan memberikan kertas/crayon sesudahnya

Masalah Deadlock

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.

Example

– System has 2 tape drives.

– P1 and P2 each hold one tape drive and each needs another one.

Example

– semaphores A and B, initialized to 1

P0 P1

wait (A); wait(B)

wait (B); wait(A)

Menyebrangi Jembatan

Lalu lintas di jembatan hanya satu jalur

Setiap bagian dari jembatan bisa disebut dengan resource.

Jika terjadi deadlock, dapat diselesaikan jika salah satu mobil mundur (preempt resources dan melakukan rollback).

Mungkin akan ada banyak mobil yang harus mundur karena deadlock.

Sangat mungkin terjadi Starvation.

System Model

Tipe Resource R1, R2, . . ., Rm

CPU cycles, memory space, peralatan I/O

Tiap resource Ri memiliki Wi instances

Tiap process menggunakan resource :

request , use dan release

Karakteristik Deadlock

1. Mutual exclusion : hanya ada satu proses yang menggunakan resource.

2. Hold and wait : ada sebuah proses yang menggunakan(hold) minimal 1 resource sedang menunggu (wait) tambahan resource yang sedang dipegang oleh proses-proses lain.

3. No preemption: sebuah resource hanya dapat dilepas (released) hanya oleh proses yang sedang menggunakannya, setelah proses menyelesaikan tugasnya.

4. Circular wait: kumpulan proses {P0, P1, . . . , Pn} dalam status menunggu. P0 menunggu resource yang digunakan P1, P1 menunggu resource yang digunakan P2, Pn–1 menunggu resource yang digunakan Pn, and Pn menunggu resource yang digunakan by P0.

Deadlock akan terjadi jika semua kondisi ini terjadi :

Resource-Allocation Graph

• V terdiri dari dua tipe : – P = {P1, P2,. . ., Pn}, berisi kumpulan semua proses

yang ada dalam sistem.

– R = {R1, R2,. . ., Rm}, berisi kumpulan semua resource yang ada dalam sistem.

• Meminta edge – dilambangkan dengan P1 Rj • Memberi edge – dilambangkan dengan Rj Pi

Berupa kumpulan vertices V dan edges E.

Resource-Allocation Graph (Cont.)

Proses

Resource dengan 4 instance

Pi meminta instance of Rj

Pi menggunakan sebuah instance Rj

Pi

Pi Rj

Rj

Contoh Resource Allocation Graph

Contoh Resource Allocation Graph (deadlock)

Resource Allocation Graph dengan circular tapi tidak terjadi Deadlock

jika graph tidak memiliki siklus (circular) maka

tidak terjadi deadlock.

jika graph memiliki siklus (circular) maka

– Jika satu instance per resource, maka deadlock.

– Jika lebih dari satu instance per resource, kemungkinan terjadi deadlock.

Metode menangani Deadlock Memastikan sistem tidak akan memasuki kondisi deadlock.

Boleh berada dalam kondisi deadlock baru dilakukan recovery.

Tidak memperdulikan problem dan berpura-pura tidak pernah terjadi deadlocks, masih digunakan oleh banyak sistem operasi

Mencegah Deadlock Menghindari request yang mungkin yang dapat menyebabkan :

• Mutual Exclusion – tidak menggunakan resource yang share; harus menggunakan resource yang tidak di share.

• Hold and Wait – memastikan jika ada proses yang meminta resource, proses tersebut tidak sedang menggunakan resource lain.

• No Preemption –Jika sebuah proses menggunakan beberapa resource meminta resource lain yang tidak dapat segera dipenuhi maka semua resource yang sedang digunakan harus dilepas

• Circular Wait – memberikan penomoran pada resource

Menghindari Deadlock

Paling mudah dan berguna, setiap proses harus mendeklarasikan jumlah maksimum resource yang

dibutuhkan

Secara dinamis algoritma deadlock-avoidance memeriksa kondisi pengalokasian resource sehingga

dan memastikan tidak ada circular-wait.

kondisi pengalokasian resource jumlah resource available (tersedia) dan allocated (sudah dialokasikan),

dan jumlah maksimum permintaan dari proses.

Safe State Jika ada proses meminta resource, sistem harus menentukan apakah permintaan tersebut nantinya akan safe (safe state). Sistem dalam kondisi safe jika semua rangkaian proses-proses juga safe.

Urutan proses <P1, P2, … , Pn> yang safe adalah jika resource yang diinginkan Pi bisa diambilkan dari resource tersedia + resource yang digunakan Pj, dengan j < i.

– Jika resource yang dikehendaki Pi tidak bisa segera dipenuhi, makaPi

menunggu sampai semua Pj selesai.

– Saat Pj selesai, Pi bisa menggunakan, mengembalikan resource, dan terminate.

– Saat Pi terminate, Pi+1 bisa mendapatkan resource yang dibutuhkandan seterusnya.

Fakta Safe State Jika sistem dalam kondisi safe

Tidak ada deadlocks.

Jika sistem dalam kondisi tidak safe

Kemungkinan terjadi deadlock.

Menghindari Deadlock

Memastikan sistem tidak masuk dalam kondisi unsafe.

Resource-Allocation Graph Algorithm

Clain Edge Pi Rj menunjukkan proses Pj meminta resource Rj; dilambangkan dengan garis putus-putus.

Claim edge berubah menjadi request edge saat proses meminta resource.

Saat resource dilepas oleh proses, assignment edge diubah menjadi claim edge.

Resource-Allocation Graph For Deadlock Avoidance

Unsafe State In Resource-Allocation Graph

Banker’s Algorithm Ada beberapa instance dalam 1 resource

Tiap proses meng-klaim jumlah maksimum penggunaan instance.

Proses mungkin menunggu untuk mendapatkan resource

Setelah mendapatkan resource yang diinginkan, dan selesai dalam waktu tertentu proses harus mengembalikan semuanya.

Struktur Data Algoritma Banker

N = number proces, and m = number resource. • Available: Vector m. – jika available [j] = k, artinya ada instance sebanyak kyang

Rj available.

• Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.

• Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj.

• Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.

Need [i,j] = Max[i,j] – Allocation [i,j].

Safety Algorithm 1. Let Work and Finish be vectors of length m and

n, respectively. Initialize: Work = Available Finish [i] = false for i - 1,3, … , n.

2. Find and i such that both:

(a) Finish [i] = false

(b) Needi Work

If no such i exists, go to step 4.

3. Work = Work + Allocationi Finish[i] = true go to step 2.

4. If Finish [i] == true for all i, then the system is in a safe state.

Resource-Request Algorithm for Process Pi

Request = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj.

1. If Requesti Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.

2. If Requesti Available, go to step 3. Otherwise Pi must wait, since resources are not available.

3. Pretend to allocate requested resources to Pi by modifying the state as follows:

Available = Available = Requesti; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti;

If safe the resources are allocated to Pi.

If unsafe Pi must wait, and the old resource-allocation state is restored

Example of Banker’s Algorithm • Snapshot at time T0. 5 processes P0 through P4;

• 3 resource types A (10 instances), B (5instances), and C (7 instances).

Allocation Max Need Available

A B C A B C A B C

P0 0 1 0 7 5 3

P1 2 0 0 3 2 2

P2 3 0 2 9 0 2

P3 2 1 1 2 2 2

P4 0 0 2 4 3 3

Example (Cont.) • The content of the matrix. Need is defined to be

Max – Allocation. Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1

• The system is in a safe state since the sequence <

P1, P3, P4, P0, P2> satisfies safety criteria.

Example P1 Request (1,0,2) (Cont.) • Check that Request Available (that is, (1,0,2) (3,3,2)

true. Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 • Executing safety algorithm shows that sequence <P1, P3,

P4, P0, P2> satisfies safety requirement. • Can request for (3,3,0) by P4 be granted? • Can request for (0,2,0) by P0 be granted?

Recovery from Deadlock: Process Termination

Abort all deadlocked processes.

Abort one process at a time until the deadlock cycle is eliminated.

In which order should we choose to abort?

Priority of the process. How long process has computed, and how much longer to

completion. Resources the process has used.

Resources process needs to complete. How many processes will need to be terminated.

Is process interactive or batch?

Recovery from Deadlock: Resource Preemption

Selecting a victim – minimize cost.

Rollback – return to some safe state, restart process for that state.

Starvation – same process may always be picked as victim, include number of

rollback in cost factor.

THE END

Referensi

1. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating System Concepts

With Java, Wiley

operating system – Threads 32