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 Used by most operating systems, including UNIX 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 deadlock17Deadlock 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 occurring18Deadlock 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.19 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.20Deadlock 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 enumeration21Deadlock 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 processes22Two 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 deadlock23Process 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 time24Resource allocation denial Banker’s Algorithm  Multiple instances of resources Each process must a priori claim maximum resource usage: can not exceed the total number of resources in the system When a process requests a resource it may have to wait 