PowerPoint Presentation

PRINCIPLES OF OPERATING SYSTEM CSOP1207.

Chapter 4 Deadlocks Objectives  Definition of Deadlock  Deadlock Characterization  Resource Allocation Graph  Methods for handling Deadlocks  Deadlock Avoidance  Bankers Algorithm  Deadlock Detection  Recovery from Deadlock.

Chapter 4 Deadlocks Definition of Deadlock • Set of processes which are holding a resource each and are also waiting for a resource which is held in another process. • A situation like this will create deadlock for the processes. • Processes are said to be in deadlock in such a situation. • A situation when two or more processes get blocked and cannot proceed further with their processing because of interdependency of resources is called deadlock..

Chapter 4 Deadlocks In a computer system, deadlock arises when four conditions occur simultaneously. When all these conditions occur at the same time, then only a deadlock may be created among processes. The conditions are as follows,.

Chapter 4 Deadlocks Dead lock Characterization: Mutual Exclusion: Mutual Exclusion means only one at a time. This means at a particular time stamp only one process can use a single resource at a time. Multiple processes are not allowed to use the same resource at the same time. For example, a process P locks the resource R in exclusive mode. This means no other process can acquire the resource R..

Chapter 4 Deadlocks Dead lock Characterization: Hold and Wait: When a process is holding some resources and waiting for other resources to finish execution. Such a situation is called Hold and Wait. This means a process can request new resources even if it is holding some. In other words the processes involved in a deadlock acquire a minimum of one resource in exclusive mode and wait for another resource which has been acquired by another process in exclusive mode..

Chapter 4 Deadlocks Dead lock Characterization: No preemption: A process is holding some resource, it cannot be taken from it until the process is finished with it. The process will release the acquired resource only after completing its task. This situation is called no preemption. This means resources cannot be taken from a process forcibly. In other words processes do not release the resources allotted to them voluntarily without utilizing the resources..

Chapter 4 Deadlocks Dead lock Characterization: Circular Wait: Each process is waiting to obtain a resource which is held by another process in such a way so that they form a cycle. A closed chain or a circular relationship exists among the processes involved in a deadlock. For example, there are three processes, P1, P2, and P3. The process P1 is waiting for a resource that has been exclusively acquired by the process P2, process P2 is waiting for a resource which is held by P3, and in turn P3 is waiting for a resource being held by P1. This situation will result in circular wait..

Chapter 4 Deadlocks Resource Allocation Graph(RAG) A resource allocation graph is also known as a RAG. It consists of a set of nodes P= and R= P represents a set of processes and R represents a set of various resources present in the system. Request Edge: This edge extends from a process to the resource being requested by the process. It is represented as Pi → Rj. Assignment Edge: This edge extends from resource to process. It indicates which resource is allocated to which process. It is represented as Rj → Pi..

Chapter 4 Deadlocks Purpose of a Resource Allocation Graph also termed as RAG The presence of deadlock can be indicated with the help of a RAG. If the graph contains no cycles, then there is no deadlock in the system. If the graph contains a cycle, then there may or may not be a deadlock depending on the following conditions. If there is only one instance per resource type, then deadlock is present. If several instances per resource type are present, then there is the possibility of deadlock..

Chapter 4 Deadlocks Understanding RAG.

Chapter 4 Deadlocks Understanding RAG • Process P1 holding a resource R2 and requesting for resource R1. • Process P2 holding resources R1 and R2 and requesting for resource R3. • Process P3 holding resource R3 and requesting for R2. • This completes the cycle and hence deadlocks..

Chapter 4 Deadlocks Understanding RAG Given 3 processes P1,P2, P3 and 4 resources R1 with 1 instance, R2 with 2 instances, R3 with 1 instance and R4 with 3 instances. Process P1 holds a resource R2 and requesting for Resource R1. Process P2 is holding resources R1 and R2 and requesting for resource R3. Process P3 holding resource R3. Is the system in a deadlock? Is the system in a deadlock? No deadlock.

Chapter 4 Deadlocks Understanding RAG Given 3 processes P1,P2, P3 and 4 resources R1 with 1 instance, R2 with 2 instances, R3 with 1 instance and R4 with 3 instances. Process P1 holding a resource R2 and requesting for resource R1. Process P2 holding resources R1 and R2 and requesting for resource R3. Process P3 holding resource R3 and requesting for R2. There is a cycle and Deadlock.

Chapter 4 Deadlocks Understanding RAG Given 4 processes P1,P2, P3,p4 and 2 resources R1 and R2 with 2 instance each. Process P1 Holding a resource R2 and requesting for Resource R1. Process P2 holding resource R1. Process P3 holding resource R1 and requesting for R2. Process P4 holding resource R2 There is a cycle but processes P2 and P4 are not requesting for a Resource so any time they can release the resources. Hence no Deadlock.

Chapter 4 Deadlocks Identify whether Deadlock is there are not? A Resource Allocation Graph showing a deadlock situation Cycle in a Resource Allocation Graph with no deadlock.

Chapter 4 Deadlocks Safe State When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state System is in safe state if there exists a sequence <P1, P2, …, Pn> of all the processes is the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < I If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate When Pi terminates, Pi +1 can obtain its needed resources, and so on ..

Chapter 4 Deadlocks Basic Facts If a system is in safe state  no deadlocks If a system is in unsafe state  possibility of deadlock Avoidance  ensure that a system will never enter an unsafe state..

Chapter 4 Deadlocks Safe, Unsafe, Deadlock State.

Chapter 4 Deadlocks Methods for handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection.

Chapter 4 Deadlocks Methods for handling Deadlocks Deadlock Prevention There are four conditions which should hold simultaneously for deadlock to occur in the system. If any of these conditions can be made false, then deadlock can be prevented. 1. Mutual Exclusion: 2. Hold and Wait: 3. No Preemption: 4. Circular Wait:.

Chapter 4 Deadlocks Methods for handling Deadlocks Deadlock Avoidance • If a safe sequence does not exist, then the system is in an unsafe state, which may result in deadlock. • All safe states are free from deadlock, but unsafe states may result in deadlocks. • This means whenever a request comes from a process for a resource, the whole system is checked for a safe or unsafe state..

Chapter 4 Deadlocks Banker’s Algorithm • Banker’s Algorithm is used to determine whether a process’s request for allocation of resources be safely granted immediately. or the grant of request be deferred to a later stage. • For the banker’s algorithm to operate, each process has to a priori specify its maximum requirement of resources. • A process is admitted for execution only if its maximum requirement of resources is within the system capacity of resources. • The Banker’s algorithm is an example of resource allocation policy that avoids deadlock..

Chapter 4 Deadlocks Banker’s Algorithm Consider the following table of a system:.

Chapter 4 Deadlocks Banker’s Algorithm 2. Is the system in a Safe State? By applying the Banker’s Algorithm: Let Avail = Available; i.e . Avail = Iteration 1. Check all processes from P1 to P5. For P1 if (P1 Need < Avail )  TRUE then calculate Avail= Avail + Allocated [P1] = + = For P2: if (P2 Need < Avail )  FALSE then Check for next process. For P3: if (P3 Need < Avail )  FALSE then Check for next process. For P4: if (P4 Need < Avail )  TRUE then calculate Avail= Avail + Allocated [P4] = + = For P5: if (P5 Need < Avail ) TRUE then calculate Avail= Avail + Allocated [P5] = + = Iteration 2. Check only process P2 to P3. For P2: if (P2 Need < Avail ) TRUE then calculate Avail= Avail + Allocated [P2] = + = For P3: if (P3 Need < Avail ) TRUE then calculate Avail= Avail + Allocated [P3] = + = = System Capacity Since, all the processes got TRUE marked, no further iterations are required. Therefore, Safe Sequence = P1, P4, P5, P2 , P3 Therefore, the System is in the Safe State..

Chapter 4 Deadlocks Dead lock Detection: • Deadlock never occur in deadlock avoidance, more calculations needed to fulfill any request of the process. • These extensive calculations are a burden on the CPU, because during that time no process can occur. • In the deadlock avoidance method, before any request may be granted, a safe sequence must be found. • All these drawbacks leads us to a methods called as Deadlock Detection. • The following is true with this method: 1. Deadlocks are allowed to occur in the system. 2. They are detected from time to time. 3. Recovery methods are used to recover from deadlock..

Chapter 4 Deadlocks Thank You.