Understanding Deadlocks in Operating Systems
Deadlocks in operating systems occur when processes hold resources and wait for others, leading to a state where none can progress. Processes may hold resources while requesting more, resulting in a standstill known as a deadlock. This deadlock arises from conditions like mutual exclusion, hold and wait, and no preemption. Understanding the types of resources, sequence of events, and principles of deadlock is essential in managing and preventing such situations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Deadlocks Deadlocks
What is Deadlock? What is Deadlock? Imagine processes P1 and P2. Imagine resources R1 and R2. Both processes need both recourses. Process P1 lock resource R1 and process P2 lock recourse R2. After both finish their job with their resources, instead of releasing it, they will hold it and look for other resource. They will stay in this state and never get out. This state call deadlock. Ali Akbar Mohammadi 2
Resources Resources A resource can be a hardware device (e.g., a tape drive) or a piece of information (e.g., a locked record in a database). Ali Akbar Mohammadi 3
Fungible Resources Fungible Resources For some resources, several identical instances may be available, such as three tape drives. When interchangeable copies of a resource are available, called fungible resources, any one of them can be used to satisfy any request for the resource. Ali Akbar Mohammadi 4
Types of Resources Types of Resources Preemptable resource: A preemptable resource is one that can be taken away from the process owning it with no ill effects. Nonpreemptable resource: Is one that cannot be taken away from its current owner without causing the computation to fail. In general, deadlocks involve nonpreemptable resources. Ali Akbar Mohammadi 5
The Sequence of Events Required to Use a Resource The Sequence of Events Required to Use a Resource 1. Request the resource. 2. Use the resource. 3. Release the resource. Ali Akbar Mohammadi 6
Principles of Deadlock Principles of Deadlock Deadlock can be defined formally as follows: 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. Ali Akbar Mohammadi 7
Conditions for Deadlock Conditions for Deadlock 1. Mutual exclusion condition. Each resource is either currently assigned to exactly one process or is available. 2. Hold and wait condition. Processes currently holding resources that were granted earlier can request new resources. 3. No preemption condition. Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them. 4. Circular wait condition. There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain. Ali Akbar Mohammadi 8
Deadlock Modeling Deadlock Modeling Ali Akbar Mohammadi 9
An Example An Example of how of how Deadlock Deadlock Occurs Occurs Ali Akbar Mohammadi 10
How How Deadlock Deadlock Can be Can be Avoided Avoided Ali Akbar Mohammadi 11
Strategies are Used for Dealing with Deadlocks Strategies are Used for Dealing with Deadlocks 1. Just ignore the problem altogether. Maybe if you ignore it, it will ignore you. 2. Detection and recovery. Let deadlocks occur, detect them, and take action. 3. Dynamic avoidance by careful resource allocation. 4. Prevention, by structurally negating one of the four conditions necessary to cause a deadlock. Ali Akbar Mohammadi 12
The Ostrich Algorithm The Ostrich Algorithm Stick your head in the sand and pretend there is no problem at all. Ali Akbar Mohammadi 13
Detection and Recovery Detection and Recovery The system does not do anything except monitor the requests and releases of resources. Every time a resource is requested or released, the resource graph is updated, and a check is made to see if any cycles exist. If a cycle exists, one of the processes in the cycle is killed. If this does not break the deadlock, another process is killed, and so on until the cycle is broken. Ali Akbar Mohammadi 14
Deadlock Prevention 1 Deadlock Prevention 1 First let us attack the mutual exclusion condition. If no resource were ever assigned exclusively to a single process, we would never have deadlocks. Example: Printers can have spool and all processes requesting printer, write in spool. The only process the work with printer s spool is printer Daemon. Exception: Not all recourses can be spooled. If the only available memory will be 64 MB and 2 process ask for that much, and take half of it, the deadlock will accure. Ali Akbar Mohammadi 15
Deadlock Prevention 2 Deadlock Prevention 2 If we can prevent processes that hold resources from waiting for more resources, we can eliminate deadlocks. One way to achieve this goal is to require all processes to request all their resources before starting execution. If everything is available, the process will be allocated whatever it needs and can run to completion. If one or more resources are busy, nothing will be allocated and the process would just wait. The problem arise cause all processes don t know which resource they need beforehand. Ali Akbar Mohammadi 16
Deadlock Prevention 3 Deadlock Prevention 3 If a process has been assigned the printer and is in the middle of printing its output, forcibly taking away the printer because a needed plotter is not available is tricky at best and impossible at worst. Ali Akbar Mohammadi 17
Deadlock Prevention 4 Deadlock Prevention 4 The circular wait can be eliminated in several ways. One way is simply to have a rule saying that a process is entitled only to a single resource at any moment. If it needs a second one, it must release the first one. For a process that needs to copy a huge file from a tape to a printer, this restriction is unacceptable. Another way to avoid the circular wait is to provide a global numbering of all the resources. Ali Akbar Mohammadi 18
(a) Numerically Ordered Resources (a) Numerically Ordered Resources (b) A Resource Graph (b) A Resource Graph Ali Akbar Mohammadi 19
Summary of Approaches to Deadlock Prevention Summary of Approaches to Deadlock Prevention Condition Mutual exclusion Hold and wait No preemption Circular wait Approach Spool everything Request all resources initially Take resources away Order resources numerically Ali Akbar Mohammadi 20
Deadlock Avoidance Deadlock Avoidance The Banker's Algorithm for a Single Resource Resource Trajectories Ali Akbar Mohammadi 21
The Banker's Algorithm for a Single Resource The Banker's Algorithm for a Single Resource It is modeled on the way a small-town banker might deal with a group of customers to whom he has granted lines of credit. The banker does not necessarily have enough cash on hand to lend every customer the full amount of each one's line of credit at the same time. Ali Akbar Mohammadi 22
Three Resource Allocation States: Three Resource Allocation States: (a) Safe. (b) Safe. (c) Unsafe. (a) Safe. (b) Safe. (c) Unsafe. Ali Akbar Mohammadi 23
The Banker's Algorithm for a Single Resource The Banker's Algorithm for a Single Resource The banker's algorithm considers each request as it occurs, and sees if granting it leads to a safe state. If it does, the request is granted; otherwise, it is postponed until later. To see if a state is safe, the banker checks to see if he has enough resources to satisfy some customer. If so, those loans are assumed to be repaid, and the customer now closest to the limit is checked, and so on. If all loans can eventually be repaid, the state is safe and the initial request can be granted. Ali Akbar Mohammadi 24
Resource Trajectories Resource Trajectories Ali Akbar Mohammadi 25
