OS Deadlock Concepts PDF

HCMUS - FIT Deadlock Lecturer: VU THI MY HANG OPERATING SYSTEM Plan Introduction to Deadlock Deadlock Handling OPERATING SYSTEM 2 Plan Introduction to Deadlock Deadlock Handling OPERATING SYSTEM 3 Introduction to...

HCMUS - FIT Deadlock Lecturer: VU THI MY HANG OPERATING SYSTEM Plan Introduction to Deadlock Deadlock Handling OPERATING SYSTEM 2 Plan Introduction to Deadlock Deadlock Handling OPERATING SYSTEM 3 Introduction to Deadlock Recall: Dining-Philosophers Problem semaphore forks; Philosopher (int i) {//i: philosopher number while(true) { down(forks[i]); //take left fork down(forks[(i + 1)%5]); //take right fork eating( ); up(forks[i]); //put left fork back up(forks[(i + 1)%5]); //put right fork back } } L Deadlock OPERATING SYSTEM 4 Introduction to Deadlock Resource-Allocation Graph (RAG) Resource R3 has one instance Process T3 holds one instance of R3 and requests one instance of R2 Resource R4 has three instances L Deadlock J No Deadlock OPERATING SYSTEM 5 Introduction to Deadlock Resource-Allocation Graph (RAG) Graph with no cycle à no deadlock Graph with a cycle and resources having only one instance à deadlock Graph with a cycle and resources having various instances à deadlock possibility JLNo Deadlock Deadlock J No Deadlock OPERATING SYSTEM 6 Introduction to Deadlock Deadlock Definition A set of processes is in a deadlock situation when each of them is waiting for resources allocated to other waiting processes in the set, therefore none of them can get all necessary resources to continue executing. OPERATING SYSTEM 7 Introduction to Deadlock Conditions for Deadlock All four following conditions must take place to cause deadlock Mutual Exclusion ü Only one process can hold the resource at a time Hold and Wait ü Process holds some resources while waiting for others, which are held by other waiting processes No preemption ü A resource can be released only by the process holding it Circular Wait ü There is a wait-cycle between at least two processes OPERATING SYSTEM 8 Plan Introduction to Deadlock Deadlock Handling q Ignorance q Prevention q Avoidance q Detection and Recovery OPERATING SYSTEM 9 Deadlock Handling Deadlock Ignorance Ostrich Algorithm: pretend that deadlocks do not cause any problem Deadlocks occur rarely Deadlock handling is much more costly Deadlock? I don’t care J OPERATING SYSTEM 10 Deadlock Handling Deadlock Prevention Eliminate the occurrence of one of the four conditions causing deadlocks Mutual Exclusion L Not practical Hold and Wait ü Process must require all necessary resources when starting executing ü Or release currently holding resources before requesting others L Difficult to know all necessary resources at the beginning L Low resource utilization L Starvation possibility OPERATING SYSTEM 11 Deadlock Handling Deadlock Prevention (cont.) Eliminate the occurrence of one of the four conditions causing deadlocks No preemption ü OS may preempt resources from a process in some circumstance L May cause errors for some resources (e.g., printer, files) Circular Wait ü Allocate different resource types according to a priority order OPERATING SYSTEM 12 Deadlock Handling Deadlock Avoidance Test deadlock possibility before granting resources to avoid a future deadlock OS requires processes to provide additional information (e.g., maximum requirement) to decide on resource allocation Whenever a process requests a resource, OS tests deadlock possibility by using deadlock avoidance algorithms ü If a resource request may lead to a future deadlock, the resource can NOT BE GRANTED ü One instance of resource type: RAG ü Multiple instances of resource type: Banker’s algorithm OPERATING SYSTEM 13 Deadlock Handling Deadlock Avoidance (cont.) Safe state: no deadlock ü System is safe if there exists a safe sequence for resource allocation ü All resource requests will be granted without entering a deadlock situation Unsafe state: may lead to deadlock Deadlock avoidance: ensure that the system will be in a safe state after resource allocation OPERATING SYSTEM 14 Deadlock Handling Deadlock Avoidance (cont.) Banker’s algorithm ü Also referred to as safety algorithm, developed by Edsger Dijkstra Notions used in Banker’s algorithm ü Available: available resources ü Max: maximum resource requirements of each process ü Allocation: resources allocated to each process ü Need: remaining resources needed for each process o Need = Max – Allocation ü Request: resource request chain of a process o For a request, test if the system will be in a safe state OPERATING SYSTEM 15 Deadlock Handling Deadlock Avoidance (cont.) Example of Banker’s algorithm Allocation Max Need Available (Work) C D E C D E C D E C D E P0 0 1 0 7 5 3 7 4 3 73 10 543 732 P1 2 0 0 3 2 2 1 2 2 P2 3 0 2 9 0 2 6 0 0 P3 2 1 1 2 2 2 0 1 1 P4 0 0 2 4 3 3 4 3 1 The system is safe? One possible safe sequence: (P1, P3, P0, P2, P4) OPERATING SYSTEM 16 Deadlock Handling Deadlock Avoidance (cont.) Example of Banker’s algorithm Allocation Max Need Available (Work) C D E C D E C D E C D E P0 0 1 0 7 5 3 7 4 3 3 3 2 P1 2 0 0 3 2 2 1 2 2 P2 3 0 2 9 0 2 6 0 0 P3 2 1 1 2 2 2 0 1 1 P4 0 0 2 4 3 3 4 3 1 RequestP1 = (1, 0, 2) will be granted safely? RequestP1 < NeedP1 < Available è RequestP1 granted è Update AllocationP1, NeedP1, Available OPERATING SYSTEM 17 Deadlock Handling Deadlock Avoidance (cont.) Example of Banker’s algorithm Allocation Max Need Available (Work) C D E C D E C D E C D E P0 0 1 0 7 5 3 7 4 3 2 3 0 P1 3 0 2 3 2 2 0 2 0 P2 3 0 2 9 0 2 6 0 0 One possible safe sequence: (P1, P3, P0, P2, P4) P3 2 1 1 2 2 2 0 1 1 P4 0 0 2 4 3 3 4 3 1 RequestP1 = (1, 0, 2) will be granted safely? RequestP1 < NeedP1 < Available è RequestP1 granted è Update AllocationP1, NeedP1, Available OPERATING SYSTEM 18 Deadlock Handling Deadlock Detection and Recovery Allow deadlock occurrence and then recover the system Deadlock Detection ü One instance of resource type: wait-for graph (i.e., a variation of RAG) ü Multiple instances of resource type: matrix-based detection algorithm (also referred to as a variation of Banker’s algorithm) Recovery ü Terminate deadlocked processes ü Rollback system to the previous safe checkpoint ü Preempt resources OPERATING SYSTEM 19 Deadlock Handling Deadlock Detection and Recovery (cont.) Example of using a wait-for graph to detect deadlocks Cycles existing in the wait-for graph à deadlock detected Resource-Allocation Graph Wait-For Graph OPERATING SYSTEM 20 Deadlock Handling Deadlock Detection and Recovery (cont.) Example of using matrix-based detection algorithm Allocation Request (Claim) Available C D E C D E C D E P0 0 1 0 7 5 3 73 43 52 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 Finish P3 2 1 1 2 2 2 P0 P1 P2 P3 P4 P4 0 0 2 4 3 3 0 01 0 01 01 P1, P3 and P4 can finish and release holding resources L P0 and P2 could not finish à Deadlock detected OPERATING SYSTEM 21 Topic 1