logging in or signing up Deadlocks jalandhar038 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 407 Category: Education License: All Rights Reserved Like it (1) Dislike it (0) Added: September 15, 2010 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... By: jaybie_06 (18 month(s) ago) padownload Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Chapter 2.4 : Deadlocks : Ceng 334 - Operating Systems 2.4-1 Chapter 2.4 : Deadlocks Process concept Process scheduling Interprocess communication Deadlocks Threads What is Deadlock? : Ceng 334 - Operating Systems 2.4-2 What is Deadlock? Process Deadlock A process is deadlocked when it is waiting on an event which will never happen System Deadlock A system is deadlocked when one or more processes are deadlocked Necessary Conditions for a Deadlock : Ceng 334 - Operating Systems 2.4-3 Necessary Conditions for a Deadlock Mutual Exclusion Shared resources are used in a mutually exclusive manner Hold & Wait Processes hold onto resources they already have while waiting for the allocation of other resources Necessary Conditions for a Deadlock (Cont.) : Ceng 334 - Operating Systems 2.4-4 Necessary Conditions for a Deadlock (Cont.) No Preemption Resources can not be preempted until the process releases them Circular Wait A circular chain of processes exists in which each process holds resources wanted by the next process in the chain No Deadlock Situation : Ceng 334 - Operating Systems 2.4-5 No Deadlock Situation If you can prevent at least one of the necessary deadlock conditions then you won’t have a DEADLOCK The Ostrich Algorithm : Ceng 334 - Operating Systems 2.4-6 The Ostrich Algorithm Pretend there is no problem Reasonable if deadlocks occur very rarely cost of prevention is high UNIX and Windows takes this approach It is a trade off between convenience correctness Ways of Handling Deadlock : Ceng 334 - Operating Systems 2.4-7 Ways of Handling Deadlock Deadlock Prevention Deadlock Detection Deadlock Avoidance Deadlock Recovery Deadlock Prevention : Ceng 334 - Operating Systems 2.4-8 Deadlock Prevention Remove the possibility of deadlock occurring by denying one of the four necessary conditions: Mutual Exclusion (Can we share everything?) Hold & Wait No preemption Circular Wait Denying the “Hold & Wait” : Ceng 334 - Operating Systems 2.4-9 Implementation A process is given its resources on a "ALL or NONE" basis Either a process gets ALL its required resources and proceeds or it gets NONE of them and waits until it can Denying the “Hold & Wait” Slide 10: Ceng 334 - Operating Systems 2.4-10 Advantages It works Reasonably easy to code Problems Resource wastage Possibility of starvation Denying “No preemption” : Ceng 334 - Operating Systems 2.4-11 Denying “No preemption” Implementation When a process is refused a resource request, it MUST release all other resources it holds Resources can be removed from a process before it is finished with them Slide 12: Ceng 334 - Operating Systems 2.4-12 Advantages It works Possibly better resource utilisation Problems The cost of removing a process's resources The process is likely to lose work it has done. (How often does this occur?) Possibility of starvation Denying “Circular Wait” : Ceng 334 - Operating Systems 2.4-13 Denying “Circular Wait” Implementation Resources are uniquely numbered Processes can only request resources in linear ascending order Thus preventing the circular wait from occurring Slide 14: Ceng 334 - Operating Systems 2.4-14 Advantages It works Has been implemented in some OSes Problems Resources must be requested in ascending order of resource number rather than as needed Resource numbering must be maintained by someone and must reflect every addition to the OS Difficult to sit down and write just write code Deadlock Avoidance : Ceng 334 - Operating Systems 2.4-15 Deadlock Avoidance Allow the chance of deadlock occur But avoid it happening.. Check whether the next state (change in system) may end up in a deadlock situation Banker’s Problem : Ceng 334 - Operating Systems 2.4-16 Banker’s Problem Suppose total bank capital is 1000 MTL Current cash : 1000- (410+210) = 380 MTL Dijkstra's Banker's Algorithm : Ceng 334 - Operating Systems 2.4-17 Dijkstra's Banker's Algorithm Definitions Each process has a LOAN, CLAIM, MAXIMUM NEED LOAN: current number of resources held MAXIMUM NEED: total number resources needed to complete CLAIM: = (MAXIMUM - LOAN) Assumptions : Ceng 334 - Operating Systems 2.4-18 Assumptions Establish a LOAN ceiling (MAXIMUM NEED) for each process MAXIMUM NEED < total number of resources available (ie., capital) Total loans for a process must be less than or equal to MAXIMUM NEED Loaned resources must be returned back in finite time Algorithm : Ceng 334 - Operating Systems 2.4-19 Algorithm 1. Search for a process with a claim that can satisfied using the current number of remaining resources (ie., tentatively grant the claim) 2. If such a process is found then assume that it will return the loaned resources. 3. Update the number of remaining resources 4. Repeat steps 1-3 for all processes and mark them Slide 20: Ceng 334 - Operating Systems 2.4-20 DO NOT GRANT THE CLAIM if at least one process can not be marked. Implementation A resource request is only allowed if it results in a SAFE state The system is always maintained in a SAFE state so eventually all requests will be filled Slide 21: Ceng 334 - Operating Systems 2.4-21 Advantages It works Allows jobs to proceed when a prevention algorithm wouldn't Problems Requires there to be a fixed number of resources What happens if a resource goes down? Does not allow the process to change its Maximum need while processing Safe and Unsafe States (1) : Ceng 334 - Operating Systems 2.4-22 Safe and Unsafe States (1) Demonstration that the state in (a) is safe (a) (b) (c) (d) (e) Safe and Unsafe States (2) : Ceng 334 - Operating Systems 2.4-23 Safe and Unsafe States (2) Demonstration that the sate in (b) is not safe (a) (b) (c) (d) The Banker's Algorithm for a Single Resource : Ceng 334 - Operating Systems 2.4-24 The Banker's Algorithm for a Single Resource Three resource allocation states safe safe unsafe (a) (b) (c) Banker's Algorithm for Multiple Resources : Ceng 334 - Operating Systems 2.4-25 Banker's Algorithm for Multiple Resources Example of banker's algorithm with multiple resources Deadlock Detection : Ceng 334 - Operating Systems 2.4-26 Deadlock Detection Methods by which the occurrence of deadlock, the processes and resources involved are detected. Generally work by detecting a circular wait The cost of detection must be considered One method is resource allocation graphs Deadlock Recovery : Ceng 334 - Operating Systems 2.4-27 Deadlock Recovery Recover from the deadlock by removing the offending processes The process being removed may lose work A Resource Allocation Graph Example : Ceng 334 - Operating Systems 2.4-28 A Resource Allocation Graph Example resource R assigned to process A process B is requesting/waiting for resource S process C and D are in deadlock over resources T and U Problems : Ceng 334 - Operating Systems 2.4-29 Problems Most systems do not support the removal and then restarting of a process. Some processes should NOT be removed. It is possible to have deadlock involving tens or even hundreds of processes Slide 30: Ceng 334 - Operating Systems 2.4-30 Implementation Processes are simply killed off (lost forever) Usually some sort of priority order exists for killing Support for suspend/resume (rollback) Some systems come with checkpoint/restart features Developers indicate a series of checkpoints when designing a software application So a process only need be rolled back to the last checkpoint, rather than back to the beginning Question : What is the simplest and most used method to recover from a deadlock? : Ceng 334 - Operating Systems 2.4-31 Question : What is the simplest and most used method to recover from a deadlock? RE-BOOT You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Deadlocks jalandhar038 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 407 Category: Education License: All Rights Reserved Like it (1) Dislike it (0) Added: September 15, 2010 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... By: jaybie_06 (18 month(s) ago) padownload Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Chapter 2.4 : Deadlocks : Ceng 334 - Operating Systems 2.4-1 Chapter 2.4 : Deadlocks Process concept Process scheduling Interprocess communication Deadlocks Threads What is Deadlock? : Ceng 334 - Operating Systems 2.4-2 What is Deadlock? Process Deadlock A process is deadlocked when it is waiting on an event which will never happen System Deadlock A system is deadlocked when one or more processes are deadlocked Necessary Conditions for a Deadlock : Ceng 334 - Operating Systems 2.4-3 Necessary Conditions for a Deadlock Mutual Exclusion Shared resources are used in a mutually exclusive manner Hold & Wait Processes hold onto resources they already have while waiting for the allocation of other resources Necessary Conditions for a Deadlock (Cont.) : Ceng 334 - Operating Systems 2.4-4 Necessary Conditions for a Deadlock (Cont.) No Preemption Resources can not be preempted until the process releases them Circular Wait A circular chain of processes exists in which each process holds resources wanted by the next process in the chain No Deadlock Situation : Ceng 334 - Operating Systems 2.4-5 No Deadlock Situation If you can prevent at least one of the necessary deadlock conditions then you won’t have a DEADLOCK The Ostrich Algorithm : Ceng 334 - Operating Systems 2.4-6 The Ostrich Algorithm Pretend there is no problem Reasonable if deadlocks occur very rarely cost of prevention is high UNIX and Windows takes this approach It is a trade off between convenience correctness Ways of Handling Deadlock : Ceng 334 - Operating Systems 2.4-7 Ways of Handling Deadlock Deadlock Prevention Deadlock Detection Deadlock Avoidance Deadlock Recovery Deadlock Prevention : Ceng 334 - Operating Systems 2.4-8 Deadlock Prevention Remove the possibility of deadlock occurring by denying one of the four necessary conditions: Mutual Exclusion (Can we share everything?) Hold & Wait No preemption Circular Wait Denying the “Hold & Wait” : Ceng 334 - Operating Systems 2.4-9 Implementation A process is given its resources on a "ALL or NONE" basis Either a process gets ALL its required resources and proceeds or it gets NONE of them and waits until it can Denying the “Hold & Wait” Slide 10: Ceng 334 - Operating Systems 2.4-10 Advantages It works Reasonably easy to code Problems Resource wastage Possibility of starvation Denying “No preemption” : Ceng 334 - Operating Systems 2.4-11 Denying “No preemption” Implementation When a process is refused a resource request, it MUST release all other resources it holds Resources can be removed from a process before it is finished with them Slide 12: Ceng 334 - Operating Systems 2.4-12 Advantages It works Possibly better resource utilisation Problems The cost of removing a process's resources The process is likely to lose work it has done. (How often does this occur?) Possibility of starvation Denying “Circular Wait” : Ceng 334 - Operating Systems 2.4-13 Denying “Circular Wait” Implementation Resources are uniquely numbered Processes can only request resources in linear ascending order Thus preventing the circular wait from occurring Slide 14: Ceng 334 - Operating Systems 2.4-14 Advantages It works Has been implemented in some OSes Problems Resources must be requested in ascending order of resource number rather than as needed Resource numbering must be maintained by someone and must reflect every addition to the OS Difficult to sit down and write just write code Deadlock Avoidance : Ceng 334 - Operating Systems 2.4-15 Deadlock Avoidance Allow the chance of deadlock occur But avoid it happening.. Check whether the next state (change in system) may end up in a deadlock situation Banker’s Problem : Ceng 334 - Operating Systems 2.4-16 Banker’s Problem Suppose total bank capital is 1000 MTL Current cash : 1000- (410+210) = 380 MTL Dijkstra's Banker's Algorithm : Ceng 334 - Operating Systems 2.4-17 Dijkstra's Banker's Algorithm Definitions Each process has a LOAN, CLAIM, MAXIMUM NEED LOAN: current number of resources held MAXIMUM NEED: total number resources needed to complete CLAIM: = (MAXIMUM - LOAN) Assumptions : Ceng 334 - Operating Systems 2.4-18 Assumptions Establish a LOAN ceiling (MAXIMUM NEED) for each process MAXIMUM NEED < total number of resources available (ie., capital) Total loans for a process must be less than or equal to MAXIMUM NEED Loaned resources must be returned back in finite time Algorithm : Ceng 334 - Operating Systems 2.4-19 Algorithm 1. Search for a process with a claim that can satisfied using the current number of remaining resources (ie., tentatively grant the claim) 2. If such a process is found then assume that it will return the loaned resources. 3. Update the number of remaining resources 4. Repeat steps 1-3 for all processes and mark them Slide 20: Ceng 334 - Operating Systems 2.4-20 DO NOT GRANT THE CLAIM if at least one process can not be marked. Implementation A resource request is only allowed if it results in a SAFE state The system is always maintained in a SAFE state so eventually all requests will be filled Slide 21: Ceng 334 - Operating Systems 2.4-21 Advantages It works Allows jobs to proceed when a prevention algorithm wouldn't Problems Requires there to be a fixed number of resources What happens if a resource goes down? Does not allow the process to change its Maximum need while processing Safe and Unsafe States (1) : Ceng 334 - Operating Systems 2.4-22 Safe and Unsafe States (1) Demonstration that the state in (a) is safe (a) (b) (c) (d) (e) Safe and Unsafe States (2) : Ceng 334 - Operating Systems 2.4-23 Safe and Unsafe States (2) Demonstration that the sate in (b) is not safe (a) (b) (c) (d) The Banker's Algorithm for a Single Resource : Ceng 334 - Operating Systems 2.4-24 The Banker's Algorithm for a Single Resource Three resource allocation states safe safe unsafe (a) (b) (c) Banker's Algorithm for Multiple Resources : Ceng 334 - Operating Systems 2.4-25 Banker's Algorithm for Multiple Resources Example of banker's algorithm with multiple resources Deadlock Detection : Ceng 334 - Operating Systems 2.4-26 Deadlock Detection Methods by which the occurrence of deadlock, the processes and resources involved are detected. Generally work by detecting a circular wait The cost of detection must be considered One method is resource allocation graphs Deadlock Recovery : Ceng 334 - Operating Systems 2.4-27 Deadlock Recovery Recover from the deadlock by removing the offending processes The process being removed may lose work A Resource Allocation Graph Example : Ceng 334 - Operating Systems 2.4-28 A Resource Allocation Graph Example resource R assigned to process A process B is requesting/waiting for resource S process C and D are in deadlock over resources T and U Problems : Ceng 334 - Operating Systems 2.4-29 Problems Most systems do not support the removal and then restarting of a process. Some processes should NOT be removed. It is possible to have deadlock involving tens or even hundreds of processes Slide 30: Ceng 334 - Operating Systems 2.4-30 Implementation Processes are simply killed off (lost forever) Usually some sort of priority order exists for killing Support for suspend/resume (rollback) Some systems come with checkpoint/restart features Developers indicate a series of checkpoints when designing a software application So a process only need be rolled back to the last checkpoint, rather than back to the beginning Question : What is the simplest and most used method to recover from a deadlock? : Ceng 334 - Operating Systems 2.4-31 Question : What is the simplest and most used method to recover from a deadlock? RE-BOOT