Deadlock detection & prevention

Deadlock

1. Deadlock Detection and Prevention in OS 1 Presentation On

2. Presented By Ikhtiar Uddin – 191902022 Sajib Chandra Paul – 191902013 Md. Mohshin Khan – 191902010 Asma Akter – 191902027 Ayesha Akter – 191902049 Jakia Akter – 191902046 2 Presented To Umme Habiba Lecturer, Dept of CSE Green University of Bangladesh

3. Agenda Definition of Deadlock Deadlock Characterization Strategies for handeling Deadlock Types of Deadlock Deadlock Condition Deadlock Prevention Deadlock Detection Deadlock Recovery 3

4. Deadlock In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process. 4

5. Deadlock Characterization Mutual Exclusion: There should be a resource that can only be held by one process at a time. 5

6. Deadlock Characterization (cont...) Hold and Wait: A process can hold multiple resources and still request more resources from other processes which are holding them. 6

7. Deadlock Characterization (cont...) No Preemption : A resource cannot be preempted from a process by force. A process can only release a resource voluntarily. 7

8. Deadlock Characterization (cont...) Circular Wait: A process is waiting for the resource held by the second process, which is waiting for the resource held by the third process and so on, till the last process is waiting for a resource held by the first process. This forms a circular chain. 8

9. Strategies for handling deadlocks Deadlock prevention. Prevents deadlocks by restraining requests made to ensure that at least one of the four deadlock conditions cannot occur . Deadlock avoidance. Dynamically grants a resource to a process if the resulting state is safe. A state is safe if there is at least one execution sequence that allows all processes to run to completion. Deadlock detection and recovery. Allows deadlocks to form; then finds and breaks them. 9

10. Resource-Allocation Graph With Example: 10

11. Resource Allocation Graph With A Deadlock 11

12. Graph With A Cycle But No Deadlock 12

13. Two types of deadlocks Resource deadlock: uses AND condition. AND condition: a process that requires resources for execution can proceed when it has acquired all those resources. Communication deadlock: uses OR condition. OR condition: a process that requires resources for execution can proceed when it has acquired at least one of those resources. 13

14. Deadlock conditions The condition for deadlock in a system using the AND condition is the existence of a cycle. The condition for deadlock in a system using the OR condition is the existence of a knot. A knot (K) consists of a set of nodes such that for every node a in K, all nodes in K and only the nodes in K are reachable from node a. Example: OR condition 14

15. Deadlock Prevention 1. A process acquires all the needed resources simultaneously before it begins its execution, therefore breaking the hold and wait condition. Drawback: over-cautious. 2. All resources are assigned unique numbers. A process may request a resource with a unique number I only if it is not holding a resource with a number less than or equal to I and therefore breaking the circular wait condition. Drawback: over-cautions. 15

16. Deadlock Prevention ( Cont …) 3. Each process is assigned a unique priority number. The priority numbers decide whether process Pi should wait for process Pj and therefore break the non- preemption condition. Drawback: starvation. The lower priority one may always be rolled back. Solution is to raise the priority every time it is victimized. 4. Practically it is impossible to provide a method to break the mutual exclusion condition since most resources are intrinsically non-sharable, 16

17. Deadlock Detection If resources have single instance: In this case for Deadlock detection we can run an algorithm to check for cycle in the Resource Allocation Graph. Presence of cycle in the graph is the sufficient condition for deadlock. 17

18. Deadlock Detection ( Cont …) If there are multiple instances of resources: Detection of the cycle is necessary but not sufficient condition for deadlock detection, in this case, the system may or may not be in deadlock varies according to different situations. 18

19. Deadlock Recovery Recovery method >> Killing the process: killing all the process involved in the deadlock. Killing process one by one. After killing each process check for deadlock again keep repeating the process till system recover from deadlock. Resource Preemption : Resources are preempted from the processes involved in the deadlock, preempted resources are allocated to other processes so that there is a possibility of recovering the system from deadlock. In this case, the system goes into starvation. 19

20. Thank You 20

21. Any Question ? 21