Unformatted text preview:

Deadlock and StarvationDeadlock Permanent blocking of a set of processes  Processes are waiting on events, but the events can only be triggered by other blocked processes  No simple, efficient solution2Bridge 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.3Can deadlock occur?Process P…Get A…Get B…Release A…Release B….Process Q…Get B…Get A…Release B…Release A….Joint Progress Diagram (Fig.6.2)The occurrence of deadlock depends on both of the execution rates and the details of the application.Can deadlock occur?Process P…Get A…Release A…Get B…Release B….Process Q…Get B…Get A…Release B…Release A….Types of Resources Reusable vs. Consumable Preemptible vs Non-preemptible7Reusable resources Description: Used by one process at a time and not depleted by that use Processes obtain resources that they later release for reuse by other processes Example: Processor time, I/O channels, main and secondary memory, files, databases, and semaphores, printers Deadlock occurs if each process holds one resource and requests the other8Deadlock with Reusable Resources P1Request diskLock disk…Request tapeLock tape…Unlock disk…Unlock tape P1Request tapeLock tape…Request diskLock disk…Unlock tape…Unlock diskConsumable Resources Description: Created (produced) and destroyed (consumed) by a process Examples: Interrupts, signals, messages, and information in I/O buffers Deadlock: May occur if a Receive message is blocking May take a rare combination of events to cause deadlock10Process P…Receive (Q)…Send (Q, message1)Process Q…Receive (P)…Send (P, message2)Example of Deadlock with a Consumable Resource• Deadlock occurs if at some point each is waiting to receive a message from the other, assuming Receive is blocking.• Caused by a design error.Preemptible Resources Can be taken away (preempted) from the owning process with no ill effects Can be restored to the process at a later time Examples: memory  processor Cannot cause deadlock12Nonpreemptible Resources  Cannot be taken away from the owning process without adversely affecting its computation Examples: printer  tape  disk  semaphore Can cause deadlock13Four Conditions for Deadlock Necessary policies 1. Mutual exclusion must be enforced.2. No preemption – no resource can be forcibly removed from the process. 3. Hold and Wait – a process may hold a resource while waiting for another. Sufficient circumstance4. Circular wait – closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain. Conditions 1-3 create a situation that could result in deadlock Condition 4 indicates that deadlock has occurred.Resource Allocation Graphs A directed graph used to represent the current snapshot of a system, i.e. current allocations and pending requests. A circle represents a process A square represents a resource (can have more than one instance of a resource) A graph edge from a resource instance to a process implies that the resource instance is allocated to the process A graph edge from a process to a resource implies that the process is requesting an instance of the resource Can be used to determine if a system is deadlocked.RAG Example with Deadlock16RAG Example with No Deadlock17Basic Facts 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.18Approaches to Deadlock Handling Ostrich Approach Prevention Avoidance Detection and Recovery19Ostrich Approach Treat deadlock as a rare annoyance by ignoring it Used by most operating systems, including Windows and UNIX20Ostrich Approach Not Always Viable A real-time control system monitoring a gasoline refinery ensures the safe and proper operation of the refinery. An avoidance strategy or prevention strategy must be employed. A computerized pacemaker – can’t afford to miss a single beat deadlock avoidance or prevention must be employed Embedded computers – cell phones, PDAs.  These are SoCs or system on chips i.e. everything is on one chip and SoCs are characterized by a small set of resources and real-time processing constraints.  Can’t have a system administrator come in and decide which process to abort after deadlock has been detected.  Either a prevention or avoidance strategy must be employed.Deadlock Prevention Restrain ways a request can be made Indirect method: prevent any one of the three necessary conditions from occurring Mutual Exclusion No preemption Hold and Wait Direct method: prevent circular wait from occurring22Prevention – Indirect Method Option 1 – Don’t enfoce mutual exclusion Rarely an option Option 2 – Allow preemption Resource(s) must be preemptible Priority must be used to decide which process should be preempted.Prevention – Indirect Method (cont.) Option 3 – Don’t allow “Hold and wait” One approach – a process must request all its resources at the same time. If it does not get all of them, then it must release all and block until all resources simultaneously available.  Another approach – a process, if denied a resource, must release all of its previously allocated resources. If necessary, it must request them all again together with the next resource.  Drawbacks: Processes can be held up for a long time waiting to acquire all resources Processes can hold on to resources they do not immediately need Processes may not know in advance all the resources they needPrevention – Direct Method Prevent circular wait Organize resources into groups that are linearly ordered: G1, G2, G3… Gn.  A process can request a resource from G1 and then from G2 and then from G3 and so on, but not vice versa. Drawbacks Processes may have to request and hold on to resources that may be used much later, thus wasting resources. Processes must know in advance all the resources they need.Deadlock Avoidance Two strategies:


View Full Document

Rose-Hulman CSSE 332 - Deadlock

Download Deadlock
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Deadlock and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Deadlock 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?