OS Unit 3 - Deadlocks 2023 PDF

UNIT 3 Introduction To DEADLOCK ©OS by Dr. Shivani Vats  System Model A system consist of a finite number of resources to be distributed among a number of competing processes. Resources may be partitioned into several types, each consisting of some number of identical...

UNIT 3 Introduction To DEADLOCK ©OS by Dr. Shivani Vats  System Model A system consist of a finite number of resources to be distributed among a number of competing processes. Resources may be partitioned into several types, each consisting of some number of identical instances. Files, I/O device (such as printers and DVD drives) are examples of resource types. If a system has two CPU, then the resource type CPU has two instances ©OS by Dr. Shivani Vats  A process must request a resource before using it and must release the resource after using it. A process may request as many resource as it requires to carry out its designated task. Number of resource requested may not increase the total number of resources available. ©OS by Dr. Shivani Vats  Under the normal mode of operation, a process may utilize a resource in only the following sequence: 1. Request : the process request the resource. If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource. 2. Use: The process can operate on the resource(if the resource is a printer, the process can print on the printer). 3. Release: the process released the resource. ©OS by Dr. Shivani Vats  2015 What is deadlock? List necessary condition for a deadlock to occur.(5 marks) What are deadlock prevention techniques? What do you mean by deadlock avoidance?(5 marks) 2016 Is it possible to have a deadlock involving only one process? Explain.(2.5 marks) What are the various ways for deadlock prevention? Explain (4 marks) ©OS by Dr. Shivani Vats  Introduction to Deadlock Every process needs some resources to complete its execution. However, the resource is granted in a sequential order. 1. The process requests for some resource. 2. OS grant the resource if it is available otherwise let the process waits. 3. The process uses it and release on the completion. ©OS by Dr. Shivani Vats  A Deadlock is a situation where each of the computer process waits for a resource which is being assigned to some another process. In this situation, none of the process gets executed since the resource it needs, is held by some other process which is also waiting for some other resource to be released. ©OS by Dr. Shivani Vats  Let us assume that there are three processes P1, P2 and P3. There are three different resources R1, R2 and R3. R1 is assigned to P1, R2 is assigned to P2 and R3 is assigned to P3. After some time, P1 demands for R2 which is being used by P2. P1 halts its execution since it can't complete without R2. P2 also demands for R3 which is being used by P3. P2 also stops its execution because it can't continue without R3. P3 also demands for R1 which is being used by P1 therefore P3 also stops its execution. ©OS by Dr. Shivani Vats  In this scenario, a cycle is being formed among the three processes. None of the process is progressing and they are all waiting. The computer becomes unresponsive since all the processes got blocked. ©OS by Dr. Shivani Vats  Necessary conditions for Deadlocks 1. Mutual Exclusion 2. Hold and Wait 3. No preemption 4. Circular Wait ©OS by Dr. Shivani Vats  1. Mutual Exclusion There should be a resource that can only be held by one process at a time. In the diagram below, there is a single instance of Resource 1 and it is held by Process 1 only. ©OS by Dr. Shivani Vats  2. Hold and Wait A process can hold multiple resources and still request more resources from other processes which are holding them. In the diagram given below, Process 2 holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held by Process 1. ©OS by Dr. Shivani Vats  3. No preemption A resource cannot be preempted from a process by force. A process can only release a resource voluntarily. In the diagram below, Process 2 cannot preempt Resource 1 from Process 1. It will only be released when Process 1 relinquishes it voluntarily after its execution is complete. ©OS by Dr. Shivani Vats 3. No preemption ©OS by Dr. Shivani Vats  4. Circular Wait A process is waiting for the resource held by the second process, which is waiting for the resource held by the third process and so on, till the last process is waiting for a resource held by the first process. This forms a circular chain. For example: Process 1 is allocated Resource2 and it is requesting Resource 1. Similarly, Process 2 is allocated Resource 1 and it is requesting Resource 2. This forms a circular wait loop. ©OS by Dr. Shivani Vats 4. Circular Wait ©OS by Dr. Shivani Vats  NOTE If all the four conditions are fulfilled than deadlock may or may not happen. If any one of the condition is not fulfilled then deadlock will never happen. ©OS by Dr. Shivani Vats  Strategies for handling Deadlock 1. Deadlock prevention: means design such a system which violates at least one of the four necessary condition of deadlock and ensure independency from deadlock.(deadlock never occur) 2. Deadlock avoidance: System maintain a set of data using which it takes a decision entertain a new request or not to be in safe state.(avoid problem at runtime) 3. Deadlock detection and recovery: deadlock occurs and ones we detect it we will recover. ©OS by Dr. Shivani Vats  2015 What are deadlock prevention techniques? What do you mean by deadlock avoidance?(5 marks) ©OS by Dr. Shivani Vats  1. Deadlock prevention If we simulate deadlock with a table which is standing on its four legs then we can also simulate four legs with the four conditions which when occurs simultaneously, cause the deadlock. if we can be able to violate one of the four necessary conditions and don't let them occur together then we can prevent the deadlock. ©OS by Dr. Shivani Vats  1. Deadlock prevention In real time system we can not take risk for deadlock so we use deadlock prevention. Guarantees deadlock will never occur ©OS by Dr. Shivani Vats  1. Mutual Exclusion Mutual exclusion from the resource point of view is the fact that a resource can never be used by more than one process simultaneously which is fair enough but that is the main reason behind the deadlock. If a resource could have been used by more than one process at the same time then the process would have never been waiting for any resource. However, if we can be able to violate resources behaving in the mutually exclusive manner then the deadlock can be prevented. ©OS by Dr. Shivani Vats  Spooling For a device like printer, spooling can work. There is a memory associated with the printer which stores jobs from each of the process into it. Later, Printer collects all the jobs and print each one of them according to FCFS. By using this mechanism, the process doesn't have to wait for the printer and it can continue whatever it was doing. Later, it collects the output when it is produced. ©OS by Dr. Shivani Vats Example ©OS by Dr. Shivani Vats  Explanation A process can only print at a time because of hardware property of printer. So we can not avoid mutual exclusive condition. ©OS by Dr. Shivani Vats  2. Hold and Wait Hold and wait condition lies when a process holds a resource and waiting for some other resource to complete its task. Deadlock occurs because there can be more than one process which are holding one resource and waiting for other in the cyclic order. ©OS by Dr. Shivani Vats  2. Hold and Wait(Cont..) However, we have to find out some mechanism by which a process either doesn't hold any resource or doesn't wait. That means, a process must be assigned all the necessary resources before the execution starts. A process must not wait for any resource once the execution has been started. This approach is known as Conservative approach. ©OS by Dr. Shivani Vats  2. Hold and Wait(Cont..) No deadlock exists in system using Conservative approach. Process will not start execution until it get all the resources which are required. One process will get all the resources out of many process and it will execute and release the lock for other. ©OS by Dr. Shivani Vats This approach is inefficient and not implementable because a process can't determine necessary resources initially ©OS by Dr. Shivani Vats  3. No Preemption To ensure this condition does not hold we use pre-empt the resource and use the following protocol: If a process is holding some resource and requests another resource that cannot be immediately allocated to it, then all resources the process is currently holding are pre-empted. ©OS by Dr. Shivani Vats  P1 B A P2 If we have a process P1 and which is holding resource A and waiting for resource B. Since P1 is waiting for B. So it is not doing any fruitful work so another process P2 wants resource A can pre-empt A from P1. ©OS by Dr. Shivani Vats  If we allow pre-emption of resource then in worst case no process will be completed. So it is not a good approach. ©OS by Dr. Shivani Vats  4. Circular Wait To violate circular wait, we can assign a priority number to each of the resource. A process can't request for a lesser priority resource. Process always request a resource in increasing order. If this case occurs P2 cannot request from resource 1. ©OS by Dr. Shivani Vats  R1 P1 P2 R2 Now Process P2 will complete the execution and release the resource R2 R2 can be assigned to P1 process and P1 process completes the execution using resource R1 and R2. ©OS by Dr. Shivani Vats No deadlock occurs in this case Summary Chart ©OS by Dr. Shivani Vats  2. Deadlock avoidance Deadlock avoidance can be done with Banker’s Algorithm. In deadlock avoidance, the request for any resource will be granted if the resulting state of the system doesn't cause deadlock in the system and state is safe The state of the system will continuously be checked for safe and unsafe states. ©OS by Dr. Shivani Vats ©OS by Dr. Shivani Vats Banker’s algorithm consists of Safety algorithm and Resource request algorithm ©OS by Dr. Shivani Vats 1. Safe State A state is safe if the system can allocate resources to each process in some order and still avoid deadlock. A system is in safe state if there exists a safe sequence. A safe state is not in deadlocked state. A deadlock state is an unsafe. Not all unsafe state are deadlock. A unsafe state may lead to deadlock. ©OS by Dr. Shivani Vats  Safety Algorithm The algorithm for finding out whether or not a system is in a safe state can be described as follows: ©OS by Dr. Shivani Vats  Resource-Request Algorithm Let Requesti be the request array for process Pi. Requesti [j] = k means process Pi wants k instances of resource type Rj. When a request for resources is made by process Pi, the following actions are taken: ©OS by Dr. Shivani Vats Safe, unsafe, and deadlocked state spaces ©OS by Dr. Shivani Vats ©OS by Dr. Shivani Vats Need =Max-Allocation Need Matrix P-id A B C D P0 0 0 0 0 P1 0 7 5 0 P2 1 0 0 2 P3 0 0 2 0 P4 0 6 4 2 Available A B C D 1 5 2 0 ©OS by Dr. Shivani Vats  Next Question Asked in paper If P1 request for resource (0,4,2,0) then is it safe or not? We apply resource request algorithm and than we apply safety algorithm to check to find if system is in safe state or not. Request