deadlock im operating system and their solution.pptx

In this presentation, we will explore the concept of deadlocks in operating systems, one of the key challenges in concurrent processing. Deadlocks arise when a set of processes are unable to proceed because each process is waiting for resources that are held by others in the set. This leads to a situation where none of the processes can complete their tasks, resulting in a system halt or slowdown. Understanding deadlocks, how they occur, and strategies to prevent or mitigate them is critical for system stability and performance in multitasking environments.
The presentation will highlight how operating systems detect deadlocks by constructing resource allocation graphs (RAGs). In these graphs:

Processes are represented as nodes, and
Resources are represented as edges connecting processes that hold or request resources.

1. Deadlock and Starvation

2. Deadlock Permanent blocking of a set of processes that either compete for system resources or communicate with each other No efficient solution

3. 4 Bridge Crossing Example Traffic only in one direction. Each section of a bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. Starvation is possible.

4. 5 Deadlocks in the Computer World Word Processor Web browser has exclusive access of has exclusive access of needs needs

5. Deadlocks For many applications, a process needs exclusive access to not one resource, but several Suppose, for example, two processes each want to record a scanned document on a CD Process A requests permission to use the scanner and is granted it Process B is programmed differently and requests the CD recorder first and is granted it Now A asks for the CD recorder, but the request is denied until B release it Unfortunately, instead of releasing the CD recorder B asks for the scanner At this point both processes are blocked and will remain so forever. This situation is called a deadlock

6. 7 Deadlock A set of processes is deadlocked if Each process in the set is waiting for an event that only another process in the set can cause All the processes are waiting So, none will ever cause any of the events Thus, all the processes continue to wait forever

7. Starvation starvation is  a problem that is encountered   when multiple threads or processes wait for the same resource, which is called a deadlock . . 8

8. 9 Dealing with Deadlock Three principle strategies for dealing with deadlock Detection: How can deadlock be identified? Recovery: What are the “best” ways to recover from deadlock? Prevention (and Avoidance): How can deadlock be prevented in the first place? Can we avoid deadlock through careful allocation scheme?

9. Resources Sequence of events required to use a resource request the resource use the resource release the resource Must wait if request is denied

10. Deadlocks in the Computer World Word Processor Web browser has exclusive access of has exclusive access of needs needs

11. 12 Resources Reusable Used by one process at a time Example: Processor time, I/O channels, main and secondary memory, files, databases, and semaphores Consumable Created (produced) and destroyed (consumed) by a process Examples: Interrupts, signals, messages, and information in I/O buffers

12. 13 System Model - Reusable Resources Resource types R 1 , R 2 , . . ., R m CPU cycles, memory space, I/O devices Each resource type R i has W i instances. Each process utilizes a resource as follows: request use release

13. Resources A resource can be a hardware device or piece of information A preemptable resource is one that can be taken from the process owning it with no ill effects (memory) A nonpreemtable resource , in contrast is one that can’t be taken away from its current owner without causing the computation to fail (CD recorder) In general, deadlocks involve nonpreemptive resources

14. Necessary Conditions for Deadlock 1) Mutual exclusion: Only one process at a time can use a resource. 2) Hold-and-wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.

15. 16 Necessary Conditions for Deadlock 3) No preemption: No resource can be forcibly removed from a process holding it. That is, resources are voluntarily released by the process holding it. 4) Circular wait A closed chain of processes exists, such that Each process holds at least one resource needed by the next process in the chain

16. Conditions for Deadlock Circular wait Defining a linear ordering of resource types

17. Deadlock Modeling A is holding R B is requesting S D T C U D is holding T C is holding U D is requesting U C is requesting T DEADLOCK

18. Strategies for dealing with Deadlocks 1. Just ignore the problem altogether 2. Detection and Recovery 3. Deadlock Avoidance careful resource allocation Bankers algorithm Ostrich algorithm 4. Deadlock Prevention Removing one of the four necessary conditions

19. Recovery from Deadlock Recovery through preemption take a resource from some other process Recovery through rollback checkpoint a process periodically use this saved state to start the process from that state.

20. Recovery from Deadlock Recovery through killing processes simplest way to break a deadlock kill one of the processes in the deadlock cycle the other processes get its resources choose process that is less damaging.

21. Deadlock Avoidance The system must be able to decide whether granting a resource is safe or not And only make the allocation when it is safe. The OS needs more information so that it can determine if the current request can be satisfied or delayed.

22. Deadlock Detection/Resource Allocation Graph Use the Resource Allocation Graph If graph contains no cycles  no deadlock. If graph contains a cycle  if only one instance per resource type, then deadlock. if several instances per resource type, possibility of deadlock.

23. With A Deadlock

24. Cycle But No Deadlock

25. Deadlock Prevention Since all four of the conditions are necessary for deadlock to occur, it follows that deadlock might be prevented by denying any one of the conditions.

26. Elimination of “Mutual Exclusion” Condition This condition is difficult to eliminate because some resources, such as the tape drive and printer, are non-shareable. Note that shareable resources like read-only-file do not require mutually exclusive access and thus cannot be involved in deadlock.

27. Elimination of “Hold and Wait” Condition If the complete set of resources needed by a process is not currently available, then the process must wait until the complete set is available. While the process waits, however, it may not hold any resources. Thus the “wait for” condition is denied and deadlocks simply cannot occur.

28. Elimination of “No-preemption” Condition The non-preemption condition can be removed by adding preemption i-e taking resources from a process if it is waiting for some other resources which are not available.

29. Elimination of “Circular Wait” Condition This can be denied by imposing a rule i-e all processes to request the resources in order (increasing or decreasing). With this rule, we can never have a cycle.

30. For example, provide a global numbering of all the resources, as shown 1≡ Card reader 2≡ Printer 3≡ Plotter 4≡ Tape drive 5≡ Card punch Now the rule is this: processes can request resources whenever they want to, but all requests must be made in numerical order. A process may request first printer and then a tape drive (order: 2, 4), but it may not request first a plotter and then a printer (order: 3, 2).

31. Example Processes A B C R A S B T C DEADLOCK Resources R S T

32. Elimination of “Circular Wait” Condition But we will not allow process C to request R, as it is requesting higher numbered resource. In this way we have prevented a cycle and prevented deadlock also.

33. Example A B C R A S B T C DEADLOCK

34. Example A B C R A S B T C NO DEADLOCK

35. Safe and Unsafe States A state is said to be safe if it is not deadlocked and there is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum number of resources immediately.

36. 37 The Ostrich Algorithm Pretend there is no problem Reasonable if Deadlocks occur very rarely Cost of prevention is high Example: Deadlocks occur on the average once every 5 years System crashes due to hardware failures, OS bugs once a week It is a trade off between convenience correctness

37. 38 Deadlock Detection Is there a Deadlock? Use any cycle detection algorithm If there’s a cycle there’s a deadlock

38. 39 Depth First Search Take each node as root, of what it hopes is a tree Left to Right, Top to Bottom R, A, B, C, S, D, T, E, F, U, V, W, G 1. For each Node 2. For each outgoing edge 3 . Keep an empty list L 4. Follow the path and keep adding the nodes to the List L 5. If the node already exists in the List we have a cycle 6. Continue till dead end

39. 40 Depth First Search R, A, S A, S B, T, E, V, G, U, D, S B, T , E, V, G, U, D, T