Deadlock and StarvationDeadlock Permanent blocking of a set of processes that either compete for system resources or communicate with each other Involve conflicting needs for resources by two or more processes No efficient solution2Reusable 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 other3Preemptible resources It can be taken away from the owning process with no ill effects Can be restored to the process at a later time Examples: memory processor Cannot cause deadlock4Nonpreemptible resources It can not be taken away from the owning process without adversely affecting its computation The resource must be voluntarily released by the process Examples: printer tape disk Semaphores Can cause deadlock5Bridge 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.6Consumable 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 deadlock7Consumable resource example Deadlock occurs if receive is blocking8P1. . .. . .Receive(P2);Send(P2, M1);P2. . .. . .Receive(P1);Send(P1, M2);System model - reusable resources Resource types R1, R2, . . ., RmCPU cycles, memory space, I/O devices Each resource type Rihas Wiinstances Each process utilizes a resource as follows: request use release9Necessary conditions for deadlock Mutual exclusion Only one process may use a resource at a time Hold-and-wait A process holding one resource is waiting to acquire additional resources held by other processes No preemption No resource can be forcibly removed form a process holding it10Deadlocked condition Circular wait There exists a permanent, circular sequence of processes such that each process is waiting for a resource held by the preceding process11Resource-Allocation Graph (RAG) A set of Vertices V and a set of Edges E V is partitioned into two types: P = {P1, P2, …, Pn}, the set consisting of all the processes in the system. R = {R1, R2, …, Rm}, the set consisting of all resource types in the system. request edge – directed edge Pi Rj assignment edge – directed edge RjPi12RAG example with a deadlock13Cycle but no deadlock14Basic 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.15Approaches to deadlock handling Ignore Deadlock (Ostrich approach) If infrequent enough and result is not serious Deadlock Prevention Prevent one of the necessary/sufficient conditions Deadlock Avoidance Allow the 3 necessary conditions Dynamically make choices to avoid deadlock decide based on knowledge of future requests i.e., find a safe path16Approaches to deadlock handling Deadlock Detection Periodically run algorithm to detect circular waiting After detecting deadlock, run a recovery algorithm to remove deadlock17Ostrich approach Deadlocks are annoyances that occur rarely Simply ignore them It is not a reasonable strategy for applications that involve life and death situations, e.g., mission critical applications or business critical applications Used by most operating systems, including Windows and UNIX18Deadlock prevention Restrain ways a request can be made Indirect method: prevent any one of the three necessary conditions from occurring Mutual Exclusion Hold and Wait No preemption Direct method: prevent circular wait from occurring19Deadlock prevention: indirect method Mutual Exclusion Not required for sharable resources Must hold for non-sharable resources Never Hold-and-Wait Must guarantee that whenever a process requests a resource, it does not hold any other resources. Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. Low resource utilization; starvation possible.20 Allow Preemption If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released. Preempted resources are added to the list of resources for which the process is waiting. Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.21Deadlock prevention: indirect methodDeadlock prevention: direct method Prevent Circular Wait impose a total ordering of all resource types require that each process requests resources in an increasing order of enumeration22Deadlock avoidance Require system has a priori information Each process declare the maximum number of resources of each type that it may need The deadlock-avoidance algorithm dynamicallyexamines the resource-allocation state to ensure that there can never be a circular-wait condition Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands/claims of the processes23Two deadlock avoidance strategies Do not start a process if its demands will result in deadlock Do not grant an incremental resource request if this allocation could result in deadlock24Process initiation denial Conditions that must hold All resources are either available or allocated No process can claim more than the total amount of resources No process can claim or hold more resources than it originally claimed Start a process only if all the needs of the current processes and the new process can be met Pessimistic approach as the assumption is that all processes will require their maximum claims at the same
View Full Document