operating systems lecture note 5.pdf

Learn and www.lmu.edu.ng Live COM 306 OPERATING SYSTEMS. DEADLOCK in Operating System Lecturer: Akande Noah O. (Ph. D.)  Deadlock in OS ▪ Deadlock is a situation that occurs in OS when any proces...

Learn and www.lmu.edu.ng Live COM 306 OPERATING SYSTEMS. DEADLOCK in Operating System Lecturer: Akande Noah O. (Ph. D.)  Deadlock in OS ▪ Deadlock is a situation that occurs in OS when any process enters a waiting state because another waiting process is holding the demanded resource. ▪ Deadlock is a common problem in multi- processing systems where several processes share a specific type of mutually exclusive resource known as a soft lock or software. 2 Deadlock in OS 3  Deadlock in OS Process P1 holds resource R1 and waits for resource R2 which is held by process P2. Process P2 holds resource R2 and waits for resource R1 which is held by process P1. None of the two processes can complete and release their resource. Thus, both the processes keep waiting infinitely. 4  Deadlock in OS ▪ A real-world example would be traffic, which is going only in one direction. ▪ Here, a bridge is considered a resource. ▪ So, when Deadlock happens, it can be easily resolved if one car backs up (Preempt resources and rollback). ▪ Several cars may have to be backed up if a deadlock situation occurs. ▪ So starvation is possible. 5  Deadlock in OS ▪ A Deadlock Situation 6  Conditions for Deadlock ▪ Deadlocks occur under the following conditions: ❖ Mutual Exclusion: Two or more resources are non- shareable (Only one process can use at a time) ❖ Hold and Wait: A process is holding at least one resource and waiting for resources. ❖ No Preemption: A resource cannot be taken from a process unless the process releases the resource. ❖ Circular Wait: A set of processes are waiting for each other in circular form. 7  Circular Wait ▪ One process is waiting for the resource, which is held by the second process, which is also waiting for the resource held by the third process etc. ▪ This will continue until the last process is waiting for a resource held by the first process. This creates a circular chain. 8 ▪ 9  Deadlock Detection ▪ A deadlock occurrence can be detected by the resource scheduler. ▪ A resource scheduler helps OS to keep track of all the resources which are allocated to different processes. 10  Strategies for Handling Deadlock A. Deadlock Ignorance B. Deadlock Prevention C. Deadlock Avoidance D. Deadlock Detection and Recovery 11  A. Deadlock Ignorance ▪ Deadlock Ignorance is the most widely used approach among all the mechanism. ▪ This is being used by many operating systems mainly for end user uses. ▪ In this approach, the Operating system assumes that deadlock never occurs. ▪ It simply ignores deadlock. ▪ This approach is best suitable for a single end user system where user uses the system only for browsing and all other normal stuff. 12  B. Deadlock Prevention ▪ If it is possible to violate one of the four conditions at any time then the deadlock can never occur in the system. ▪ Prevention is done by negating one of above mentioned necessary conditions for deadlock. ▪ Prevention can be done in four different ways: – 1.Eliminate mutual exclusion – 2. Allow preemption – 3. Solve hold and Wait – 4. Circular wait Solution 13  B. Deadlock Prevention ▪ a. Eliminating Mutual Exclusion ▪ To violate this condition, all the system resources must interact in such a way that they can be used in a shareable mode. 14  2. Deadlock Prevention by Allowing Preemption ▪ This condition can by violated by forceful preemption. ▪ Consider a process is holding some resources and request other resources that can not be immediately allocated to it. ▪ Then, by forcefully preempting the currently held resources, the condition can be violated. 15  2. Deadlock Prevention by allowing preemption ▪ A process is allowed to forcefully preempt the resources possessed by some other process only if- – It is a high priority process or a system process. – The victim process is in the waiting state. 16  3. Deadlock Prevention by solving hold and Wait ▪ Approach-1: ▪ In this approach, ▪ A process has to first request for all the resources it requires for execution. ▪ It can start its execution only when it has acquired all the resources it needs. ▪ This approach ensures that the process does not hold some resources and wait for other resources. 17  3. Deadlock Prevention by Solving hold and Wait ▪ Approach-2: ▪ In this approach, a timer is set after the process acquires any resource. ▪ After the timer expires, a process has to compulsorily release the resource. 18  4. Deadlock Prevention by Circular Wait Solution ▪ This condition can be violated by not allowing the processes to wait for resources in a cyclic manner. ▪ To violate this condition, the following approach is followed: – A natural number is assigned to every resource (resource number/id). – Each process is allowed to request for the resources either in only increasing or only decreasing order of the resource number. – In case increasing order is followed, if a process requires a lesser number resource, then it must release all the resources having larger number and vice versa. – This approach is the most practical approach and implementable. – However, this approach may cause starvation but will never lead to deadlock. 19 C. Deadlock Detection and Recovery ▪ This approach let the processes fall in deadlock and then periodically check whether deadlock occur in the system or not. ▪ If it occurs then it applies some of the recovery methods to the system to get rid of deadlock. 20  D. Deadlock Avoidance ▪ In deadlock avoidance, the operating system checks whether the system is in safe state or in unsafe state at every step which the operating system performs. ▪ The process continues until the system is in safe state. ▪ Once the system moves to unsafe state, the OS has to backtrack one step. ▪ In simple words, the OS reviews each allocation so that the allocation doesn't cause the deadlock in the system. 21  D. Deadlock Avoidance ▪ Avoidance Algorithms – The deadlock-avoidance algorithm helps the OS to dynamically assess the resource-allocation state so that there can never be a circular-wait situation. ▪ For a single instance of a resource type. – Use a resource-allocation graph – Cycles are necessary which are sufficient for Deadlock ▪ For Multiple instances of a resource type. – Cycles are necessary but never sufficient for Deadlock. – Uses the banker's algorithm 22  4. Deadlock Avoidance using Resource Allocation Graph ▪ Resource Allocation Graph (RAG) is a graph that represents the state of a system pictorially. ▪ It gives complete information about the state of a system such as- – How many processes exist in the system? – How many instances of each resource type exist? – How many instances of each resource type are allocated? – How many instances of each resource type are still available? – How many instances of each resource type are held by each process? – How many instances of each resource type does each process need for execution? 23  4. Deadlock Avoidance using Resource Allocation Graph ▪ There are two major components of a Resource Allocation Graph: ▪ Vertices ▪ Edges 24 4. Deadlock Avoidance using Resource Allocation Graph 25  4. Deadlock Avoidance using Resource Allocation Graph ▪ Process Vertices- ▪ Process vertices represent the processes. ▪ They are drawn as a circle by mentioning the name of process inside the circle. 26  4. Deadlock Avoidance using Resource Allocation Graph ▪ Resource Vertices: ▪ Resource vertices represent the resources. ▪ Depending on the number of instances that exists in the system, resource vertices may be single instance or multiple instance. ▪ They are drawn as a rectangle by mentioning the dots inside the rectangle. ▪ The number of dots inside the rectangle indicates the number of instances of that resource existing in the system. 27  4. Deadlock Avoidance using Resource Allocation Graph ▪ Edges- ▪ There are two types of edges in a Resource Allocation Graph- 28  4. Deadlock Avoidance using Resource Allocation Graph ▪ Assign Edges- ▪ Assign edges represent the assignment of resources to the processes. ▪ They are drawn as an arrow where the head of the arrow points to the process and tail of the process points to the instance of the resource. 29  4. Deadlock Avoidance using Resource Allocation Graph ▪ Request Edges- ▪ Request edges represent the waiting state of processes for the resources. ▪ They are drawn as an arrow where the head of the arrow points to the instance of the resource and tail of the process points to the process. ▪ If a process requires ‘n’ instances of a resource type, then ‘n’ assign edges will be drawn. 30  Example Of RAG ▪ It gives the following information- There exist three processes in the system namely P1, P2 and P3. There exist two resources in the system namely R1 and R2. There exists a single instance of resource R1 and two instances of resource R2. Process P1 holds one instance of resource R1 and is waiting for an instance of resource R2. Process P2 holds one instance of resource R2 and is waiting for an instance of resource R1. Process P3 holds one instance of resource R2 and is not waiting for anything. 31  4. Deadlock Avoidance using Resource Allocation Graph ▪ Using Resource Allocation Graph, it can be easily detected whether a system is in a Deadlock state or not. ▪ Rule-01: ▪ In a Resource Allocation Graph where all the resources are single instance, If a cycle is formed, then system is in a deadlock state. If no cycle is formed, then system is not in a deadlock state. 32  Deadlock Avoidance ▪ Rule 02: ▪ In a Resource Allocation Graph where all the resources are NOT single instance, If a cycle is formed, then system may be in a deadlock state. Banker’s Algorithm is applied to confirm whether a system is in a deadlock state or not. If no cycle is formed, then the system is not in a deadlock state. Presence of a cycle is a necessary but not a sufficient condition for the occurrence of deadlock. 33  Deadlock Avoidance: Example 1 ▪ Method-01: ▪ The given resource allocation graph is single instance with a cycle contained in it. Thus, the system is definitely in a deadlock state. 34  Deadlock Avoidance: Example 1 ▪ Method-02: ▪ Using the given resource allocation graph, we have: 35  Deadlock Avoidance: Example 1 ▪ Now, There are no instances available currently and both the processes require a resource to execute. Therefore, none of the process can be executed and both keeps waiting infinitely. Thus, the system is in a deadlock state. 36 Deadlock Avoidance: Example 2 Find if the system is in a deadlock state otherwise find a safe sequence. Solution- The given resource allocation graph is multi instance with a cycle contained in it. So, the system may or may not be in a deadlock state. 37 Deadlock Avoidance: Example 2 Process Allocation Table Process Allocation Matrix 38  Deadlock Avoidance: Example 2 ▪ Step-01: ▪ Since process P3 does not need any resource, so it executes. After execution, process P3 release its resources. Then, ▪ Available ▪ =+ ▪ = 39  Deadlock Avoidance: Example 2 ▪ Step-02: ▪ With the instances available currently, only the requirement of process P1 can be satisfied. So, process P1 is allocated the requested resources. It completes its execution and then free up the instances of resources held by it. 40  Deadlock Avoidance: Example 2 ▪ Thus, There exists a safe sequence P3, P1, P2 in which all the processes can be executed. So, the system is in a safe state. 41 Deadlock Avoidance: Example 3 Process Allocation Table 42 Deadlock Avoidance: Example 3 43  Deadlock Avoidance: Example 3 ▪ Thus, There exists a safe sequence P2, P0, P1, P3 in which all the processes can be executed. So, the system is in a safe state. 44  Deadlock Avoidance using Banker’s Algorithm ▪ Banker’s Algorithm is a deadlock avoidance strategy. ▪ It is called so because it is used in banking systems to decide whether a loan can be granted or not. ▪ Banker’s Algorithm requires that whenever a new process is created, it specifies the maximum number of instances of each resource type that it exactly needs. 45  Data Structures Used in Banker’s Algorithm ▪ To implement banker’s algorithm, following four data structures are used: 46  Data Structures Used in Banker’s Algorithm Data Structure Definition Example It is a single dimensional array that specifies the Available[R1] = K Available number of instances of each It means K instances of resource resource type currently type R1 are currently available. available. It is a two dimensional array Max[P1][R1] = K that specifies the maximum It means process P1 is allowed to Max number of instances of each ask for maximum K instances of resource type that a process resource type R1. can request. 47  Data Structures Used in Banker’s Algorithm Data Structure Definition Example It is a two dimensional array that Allocation[P1][R1] = K specifies the number of It means K instances of Allocation instances of each resource type resource type R1 have been that has been allocated to the allocated to the process P1. process. It is a two dimensional array that Need[P1][R1] = K specifies the number of It means process P1 requires Need instances of each resource type K more instances of resource that a process requires for type R1 for execution. execution. 48  Working Principles of Banker’s Algorithm ▪ Banker’s Algorithm is executed whenever any process puts forward the request for allocating the resources. ▪ It involves the following steps- 49  Working Principles of Banker’s Algorithm ▪ Step-1: ▪ Banker’s Algorithm checks whether the request made by the process is valid or not. ▪ If the request is invalid, it aborts the request. ▪ If the request is valid, it follows step-02. ▪ A request is considered valid if and only if: – The number of requested instances of each resource type is less than the need declared by the process in the beginning. 50  Working Principles of Banker’s Algorithm ▪ Step-2: ▪ Banker’s Algorithm checks if the number of requested instances of each resource type is less than the number of available instances of each type. ▪ If the sufficient number of instances are not available, it asks the process to wait longer. ▪ If the sufficient number of instances are available, it follows step-03. 51  Working Principles of Banker’s Algorithm ▪ Step-3: ▪ Banker’s Algorithm makes an assumption that the requested resources have been allocated to the process. ▪ Then, it modifies its data structures accordingly and moves from one state to the other state. ▪ Now, Banker’s Algorithm follows the safety algorithm to check whether the resulting state it has entered in is a safe state or not. 52  Working Principles of Banker’s Algorithm ▪ Step-3: ▪ If it is a safe state, then it allocates the requested resources to the process in actual. ▪ If it is an unsafe state, then it rollbacks to its previous state and asks the process to wait longer. ▪ A system is said to be in safe state when: – All the processes can be executed in some arbitrary sequence with the available number of resources. 53  Practice Problems based on Banker’s Algorithm ▪ EX 1: A single processor system has three resource types X, Y and Z, which are shared by three processes (P1, P2, P3). There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Using the resource allovcation table below, which of these processes will finish LAST? 54 Practice Problems based on Banker’s Algorithm alloc request X Y Z X Y Z P0 1 2 1 1 0 3 P1 2 0 1 0 1 2 P2 2 2 1 1 2 0 55  Practice Problems based on Banker’s Algorithm ▪ Solution: ▪ According to the question: ▪ Total = [ X Y Z ] = [ 5 5 5 ] ▪ Total _Alloc = [ X Y Z ] = [5 4 3] ▪ Now, ▪ Available ▪ = Total – Total_Alloc ▪ = [ 5 5 5 ] – [5 4 3] = [ 0 1 2 ] 56  Practice Problems based on Banker’s Algorithm ▪ Step-1: ▪ With the instances available currently [ 0 1 2 ], only the requirement of process P1 can be satisfied. ▪ So, process P1 is allocated the requested resources. ▪ It completes its execution and then free up the instances of resources held by it. alloc request ▪ Then, X Y Z X Y Z ▪ Available P0 1 2 1 1 0 3 ▪ = [ 0 1 2 ] + [ 2 0 1] P1 2 0 1 0 1 2 ▪ = P2 2 2 1 1 2 0 57  Practice Problems based on Banker’s Algorithm ▪ Step-2: ▪ With the instances available currently [ 2 1 3 ], only the requirement of the process P0 can be satisfied. ▪ So, process P0 is allocated the requested resources. ▪ It completes its execution and then free up the instances of resources held by it. alloc request ▪ Then- X Y Z X Y Z ▪ Available P0 1 2 1 1 0 3 ▪ =+ P1 2 0 1 0 1 2 ▪ = P2 2 2 1 1 2 0 58  Practice Problems based on Banker’s Algorithm ▪ Step-3: ▪ With the instances available currently, the requirement of the process P2 can be satisfied. So, process P2 is allocated the requested resources. It completes its execution and then free up the instances of resources held by it. alloc request ▪ Then- X Y Z X Y Z ▪ Available P0 1 2 1 1 0 3 ▪ =+ P1 2 0 1 0 1 2 ▪ = P2 2 2 1 1 2 0 59  Practice Problems based on Banker’s Algorithm ▪ Thus, ▪ There exists a safe sequence P1, P0, P2 in which all the processes can be executed. ▪ So, the system is in a safe state. ▪ Process P2 will be executed at last. 60  Practice Problems based on Banker’s Algorithm ▪ Ex. 2: A system has 4 processes and 5 allocatable resource. The current allocation and maximum needs are as follows: Allocated Maximum A 1 0 2 1 1 1 1 2 1 3 If Available = [ 0 0 X 1 1 ], B 2 0 1 1 0 2 2 2 1 0 what is the smallest value C of x for which this is a 1 1 0 1 1 2 1 3 1 1 safe state? D 1 1 1 1 0 1 1 2 2 0 61  Practice Problems based on Banker’s Algorithm ▪ Let us calculate the additional instances of each resource type needed by each process. ▪ We know: Need = Maximum – Allocation Allocated Maximum Need A▪ 1 0 2 1 1 1 1 2 1 3 A 0 1 0 0 2 B 2 0 1 1 0 2 2 2 1 0 B 0 2 1 0 0 C 1 1 0 1 1 2 1 3 1 1 C 1 0 3 0 0 ▪ D 0 0 1 1 0 D 1 1 1 1 0 1 1 2 2 0 62  Practice Problems based on Banker’s Algorithm ▪ Case-01: For X = 0 ▪ If X = 0, then- ▪ Available ▪ = ▪ With the instances available currently, the requirement of any process can not be satisfied. So, for X = 0, system remains in a deadlock which is an unsafe state. 63  Practice Problems based on Banker’s Algorithm ▪ Case-02: For X = 1 ▪ If X = 1, then- ▪ Available ▪ = 64  Practice Problems based on Banker’s Algorithm ▪ Step-01: ▪ With the instances available currently, only the requirement of the process D can be satisfied. So, process D is allocated the requested resources. It completes its execution and then free up the instances of resources held by it. ▪ Then- ▪ Available ▪ =+ ▪ = With the instances available currently, the requirement of any process can not be satisfied. So, for X = 1, system remains in a deadlock which is an unsafe state. 65  Practice Problems based on Banker’s Algorithm ▪ Case-02: For X = 2 ▪ If X = 2, then- ▪ Available ▪ = 66  Practice Problems based on Banker’s Algorithm ▪ Step-01: ▪ With the instances available currently, only the requirement of the process D can be satisfied. So, process D is allocated the requested resources. It completes its execution and then free up the instances of resources held by it. 67  Practice Problems based on Banker’s Algorithm ▪ Then- ▪ Available ▪ =+ ▪ = 68  Practice Problems based on Banker’s Algorithm ▪ Step-02: ▪ With the instances available currently, only the requirement of the process C can be satisfied. So, process C is allocated the requested resources. It completes its execution and then free up the instances of resources held by it. ▪ Then-Available – =+ – = 69  Practice Problems based on Banker’s Algorithm ▪ Step-03: ▪ With the instances available currently, the requirement of both the processes A and B can be satisfied. So, processes A and B are allocated the requested resources one by one. They complete their execution and then free up the instances of resources held by it. ▪ Then- ▪ Available ▪ =++ ▪ = 70  Practice Problems based on Banker’s Algorithm ▪ Thus, ▪ There exists a safe sequence in which all the processes can be executed. ▪ So, the system is in a safe state. ▪ Thus, minimum value of X that ensures system is in safe state = 2. 71