OS UNIT - 3 DEADLOCK PDF

UNIT – 3 DEADLOCK Syllabus : System model, Deadlock Cauterization , Prevention, Avoidance and Detection, Recovery from deadlock, Combined approach. Overview Deadlock: A situation where a set of processes are blocked because each process is holding a resour...

UNIT – 3 DEADLOCK Syllabus : System model, Deadlock Cauterization , Prevention, Avoidance and Detection, Recovery from deadlock, Combined approach. Overview Deadlock: A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. Deadlock can arise if following four conditions hold simultaneously (Necessary Conditions): 1. Mutual Exclusion – One or more than one resource are non-sharable (Only one process can use at a time). 2. Hold and Wait – A process is holding at least one resource and waiting for resources. 3. No Preemption – A resource cannot be taken from a process unless the process releases the resource. 4. Circular Wait – A set of processes are waiting for each other in circular form. Methods for handling deadlock: There are three ways to handle deadlock 1. Deadlock prevention or avoidance: The idea is to not let the system into deadlock state. 2. Deadlock detection and recovery : Let deadlock occur, then do preemption to handle it once occurred. 3. Ignore the problem all together – : If deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take. Banker’s Algorithm: This algorithm handles multiple instances of the same resource. Memory Management: These techniques allow the memory to be shared among multiple processes.  Overlays – The memory should contain only those instructions and data that are required at a given time.  Swapping – In multiprogramming, the instructions that have used the time slice are swapped out from the memory.  1. System model: A system consists of a finite number of resources to be distributed among a number of competing processes. The resources are partitioned into several types, each consisting of some number of identical instances. Memory space, CPU cycles, files, I/O devices are examples of resource types. If a system has 2 CPUs, then the resource type CPU has 2 instances. A process must request a resource before using it and must release the resource after using it. A process may request as many resources as it requires to carry out its task. The number of resources as it requires to carry out its task. The number of resources requested may not exceed the total number of resources available in the system. A process cannot request 3 printers if the system has only two. A process may utilize a resource in the following sequence: (I) REQUEST: The process requests the resource. If the request cannot be granted immediately (if the resource is being used by another process), then the requesting process must wait until it can acquire the resource (II) USE: The process can operate on the resource.if the resource is a printer, the process can print on the printer. (III) RELEASE: The process release the resource. For each use of a kernel managed by a process the operating system checks that the process has requested and has been allocated the resource. A system table records whether each resource is free (or) allocated. For each resource that is allocated, the table also records the process to which it is allocated. If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource. To illustrate a deadlocked state, consider a system with 3 CDRW drives. Each of 3 processes holds one of these CDRW drives. If each process now requests another drive, the 3 processes will be in a deadlocked state. Each is waiting for the event “CDRW is released” which can be caused only by one of the other waiting processes. This example illustrates a deadlock involving the same resource type. Deadlocks may also involve different resource types. Consider a system with one printer and one DVD drive. The process Pi is holding the DVD and process Pj is holding the printer. If Pi requests the printer and Pj requests the DVD drive, a deadlock occurs.  2. DEADLOCK CHARACTERIZATION: In a deadlock, processes never finish executing, and system resources are tied up, preventing other jobs from starting. NECESSARY CONDITIONS: A deadlock situation can arise if the following 4 conditions hold simultaneously in a system: 1. MUTUAL EXCLUSION: Only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released. 2. HOLD AND WAIT: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes. 3. NO PREEMPTION: Resources cannot be preempted. A resource can be released only voluntarily by the process holding it, after that process has completed its task. 4. CIRCULAR WAIT: A set {P0,P1,…..Pn} of waiting processes must exist such that P0 is waiting for resource held by P1, P1 is waiting for a resource held by P2,……,Pn- 1 is waiting for a resource held by Pn and Pn is waiting for a resource held byP0. What is Deadlock in Operating System (OS)? 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. 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. 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 R1 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. 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.  Difference between Starvation and Deadlock Sr. Deadlock Starvation 1 Deadlock is a situation where no process got blocked Starvation is a situation where the low priority and no process proceeds process got blocked and the high priority processes proceed. 2 Deadlock is an infinite waiting. Starvation is a long waiting but not infinite. 3 Every Deadlock is always a starvation. Every starvation need not be deadlock. 4 The requested resource is blocked by the other The requested resource is continuously be used by process. the higher priority processes. 5 Deadlock happens when Mutual exclusion, hold and It occurs due to the uncontrolled priority and wait, No preemption and circular wait occurs resource management. simultaneously. Necessary conditions for Deadlocks 1. Mutual Exclusion A resource can only be shared in mutually exclusive manner. It implies, if two process cannot use the same resource at the same time. 2. Hold and Wait A process waits for some resources while holding another resource at the same time.  3. No preemption The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile. 4. Circular Wait All the processes must be waiting for the resources in a cyclic manner so that the last process is waiting for the resource which is being held by the first process. Strategies for handling Deadlock 1. 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. There is always a tradeoff between Correctness and performance. The operating systems like Windows and Linux mainly focus upon performance. However, the performance of the system decreases if it uses deadlock handling mechanism all the time if deadlock happens 1 out of 100 times then it is completely unnecessary to use the deadlock handling mechanism all the time. In these types of systems, the user has to simply restart the computer in the case of deadlock. Windows and Linux are mainly using this approach. 2. Deadlock prevention Deadlock happens only when Mutual Exclusion, hold and wait, No preemption and circular wait holds simultaneously. If it is possible to violate one of the four conditions at any time then the deadlock can never occur in the system. The idea behind the approach is very simple that we have to fail one of the four conditions but there can be a big argument on its physical implementation in the system. We will discuss it later in detail. 3. 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. 4. 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. 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. However, if we break one of the legs of the table then the table will fall definitely. The same happens with 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. Let's see how we can prevent each of the conditions. 1. Mutual Exclusion Mutual section 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. 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. Although, Spooling can be an effective approach to violate mutual exclusion but it suffers from two kinds of problems. 1. This cannot be applied to every resource. 2. After some point of time, there may arise a race condition between the processes to get space in that spool. We cannot force a resource to be used by more than one process at the same time since it will not be fair enough and some serious problems may arise in the performance. Therefore, we cannot violate mutual exclusion for a process practically. 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. 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. !(Hold and wait) = !hold or !wait (negation of hold and wait is, either you don't hold or you don't wait) This can be implemented practically if a process declares all the resources initially. However, this sounds very practical but can't be done in the computer system because a process can't determine necessary resources initially. Process is the set of instructions which are executed by the CPU. Each of the instruction may demand multiple resources at the multiple times. The need cannot be fixed by the OS. The problem with the approach is: 1. Practically not possible. 2. Possibility of getting starved will be increases due to the fact that some process may hold a resource for a very long time. 3. No Preemption Deadlock arises due to the fact that a process can't be stopped once it starts. However, if we take the resource away from the process which is causing deadlock then we can prevent deadlock. This is not a good approach at all since if we take a resource away which is being used by the process then all the work which it has done till now can become inconsistent. Consider a printer is being used by any process. If we take the printer away from that process and assign it to some other process then all the data which has been printed can become inconsistent and ineffective and also the fact that the process can't start printing again from where it has left which causes performance inefficiency. 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. This ensures that not a single process can request a resource which is being utilized by some other process and no cycle will be formed. Among all the methods, violating Circular wait is the only approach that can be implemented practically. Deadlock avoidance 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. The state of the system will continuously be checked for safe and unsafe states. In order to avoid deadlocks, the process must tell OS, the maximum number of resources a process can request to complete its execution. The simplest and most useful approach states that the process should declare the maximum number of resources of each type it may ever need. The Deadlock avoidance algorithm examines the resource allocations so that there can never be a circular wait condition.  Safe and Unsafe States The resource allocation state of a system can be defined by the instances of available and allocated resources, and the maximum instance of the resources demanded by the processes. A state of a system recorded at some random time is shown below. Resources Assigned Process Type 1 Type 2 Type 3 Type 4 A 3 0 2 2 B 0 0 1 1 C 1 1 1 0 D 2 1 4 0 Resources still needed Process Type 1 Type 2 Type 3 Type 4 A 1 1 0 0 B 0 1 1 2 C 1 2 1 0 D 2 1 1 2 1. E = (7 6 8 4) 2. P = (6 2 8 3) 3. A = (1 4 0 1) Above tables and vector E, P and A describes the resource allocation state of a system. There are 4 processes and 4 types of the resources in a system. Table 1 shows the instances of each resource assigned to each process. Table 2 shows the instances of the resources, each process still needs. Vector E is the representation of total instances of each resource in the system. Vector P represents the instances of resources that have been assigned to processes. Vector A represents the number of resources that are not in use. A state of the system is called safe if the system can allocate all the resources requested by all the processes without entering into deadlock. If the system cannot fulfill the request of all processes then the state of the system is called unsafe. The key of Deadlock avoidance approach is when the request is made for resources then the request must only be approved in the case if the resulting state is also a safe state. Resource Allocation Graph The resource allocation graph is the pictorial representation of the state of a system. As its name suggests, the resource allocation graph is the complete information about all the processes which are holding some resources or waiting for some resources. It also contains the information about all the instances of all the resources whether they are available or being used by the processes. In Resource allocation graph, the process is represented by a Circle while the Resource is represented by a rectangle. Let's see the types of vertices and edges in detail. Vertices are mainly of two types, Resource and process. Each of them will be represented by a different shape. Circle represents process while rectangle represents resource. A resource can have more than one instance. Each instance will be represented by a dot inside the rectangle. Edges in RAG are also of two types, one represents assignment and other represents the wait of a process for a resource. The above image shows each of them. A resource is shown as assigned to a process if the tail of the arrow is attached to an instance to the resource and the head is attached to a process. A process is shown as waiting for a resource if the tail of an arrow is attached to the process while the head is pointing towards the resource. Example Let'sconsider 3 processes P1, P2 and P3, and two types of resources R1 and R2. The resources are having 1 instance each. According to the graph, R1 is being used by P1, P2 is holding R2 and waiting for R1, P3 is waiting for R1 as well as R2. ADVERTISEMENT The graph is deadlock free since no cycle is being formed in the graph. Deadlock Detection using RAG If a cycle is being formed in a Resource allocation graph where all the resources have the single instance then the system is deadlocked. In Case of Resource allocation graph with multi-instanced resource types, Cycle is a necessary condition of deadlock but not the sufficient condition. The following example contains three processes P1, P2, P3 and three resources R2, R2, R3. All the resources are having single instances each. If we analyze the graph then we can find out that there is a cycle formed in the graph since the system is satisfying all the four conditions of deadlock. Allocation Matrix Allocation matrix can be formed by using the Resource allocation graph of a system. In Allocation matrix, an entry will be made for each of the resource assigned. For Example, in the following matrix, en entry is being made in front of P1 and below R3 since R3 is assigned to P1. Process R1 R2 R3 P1 0 0 1 P2 1 0 0 P3 0 1 0 Request Matrix In request matrix, an entry will be made for each of the resource requested. As in the following example, P1 needs R1 therefore an entry is being made in front of P1 and below R1. Process R1 R2 R3 P1 1 0 0 P2 0 1 0 P3 0 0 1 Avial = (0,0,0) Neither we are having any resource available in the system nor a process going to release. Each of the process needs at least single resource to complete therefore they will continuously be holding each one of them. We cannot fulfill the demand of at least one process using the available resources therefore the system is deadlocked as determined earlier when we detected a cycle in the graph. Deadlock Detection and Recovery In this approach, The OS doesn't apply any mechanism to avoid or prevent the deadlocks. Therefore the system considers that the deadlock will definitely occur. In order to get rid of deadlocks, The OS periodically checks the system for any deadlock. In case, it finds any of the deadlock then the OS will recover the system using some recovery techniques. The main task of the OS is detecting the deadlocks. The OS can detect the deadlocks with the help of Resource allocation graph. In single instanced resource types, if a cycle is being formed in the system then there will definitely be a deadlock. On the other hand, in multiple instanced resource type graph, detecting a cycle is not just enough. We have to apply the safety algorithm on the system by converting the resource allocation graph into the allocation matrix and request matrix. In order to recover the system from deadlocks, either OS considers resources or processes. For Resource Preempt the resource We can snatch one of the resources from the owner of the resource (process) and give it to the other process with the expectation that it will complete the execution and will release this resource sooner. Well, choosing a resource which will be snatched is going to be a bit difficult. Rollback to a safe state System passes through various states to get into the deadlock state. The operating system canrollback the system to the previous safe state. For this purpose, OS needs to implement check pointing at every state. The moment, we get into deadlock, we will rollback all the allocations to get into the previous safe state. For Process Kill a process Killing a process can solve our problem but the bigger concern is to decide which process to kill. Generally, Operating system kills a process which has done least amount of work until now. Kill all process This is not a suggestible approach but can be implemented if the problem becomes very serious. Killing all process will lead to inefficiency in the system because all the processes will execute again from starting.