SS & OS Module 4 PART 2.pdf

System Software and Operating System Module 4 (Part 2) Dead Locks : System Model, Dead Lock Characterization, Methods of Handling Dead Locks, Dead Lock Prevention System Model A system consists of a finite number of resources to be distributed among a number of co...

System Software and Operating System Module 4 (Part 2) Dead Locks : System Model, Dead Lock Characterization, Methods of Handling Dead Locks, Dead Lock Prevention 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, and I/O devices (such as printers and DVD drives) are examples of resource types. If a system has two CPUs, then the resource type CPU has two instances. Similarly, the resource type printer may have five instances. If a process requests an instance of a resource type, the allocation of any instance of the type may satisfy the request. 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 designated task. Under the normal mode of operation, a process may utilize a resource in only the following sequence: 1. Request. If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource. 2. Use. The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer). 3. Release. The process releases 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. Deadlock In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; and if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock. 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 four conditions hold simultaneously in a system: 1. Mutual exclusion. At least one resource must be held in a non sharable mode; that is, 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; that is, 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 a 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 by P0. All the four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and- wait condition, so the four conditions are not completely independent. Methods for Handling Deadlocks We can deal with the deadlock problem in one of three ways. 1. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state. 2. We can allow the system to enter a deadlock state, detect it, and recover. 3. We can ignore the problem altogether and pretend that deadlocks never occur in the system. The third solution is the one used by most operating systems, including UNIX and Windows. To ensure that deadlocks never occur, the system can use either a deadlock prevention or a deadlock-avoidance scheme. Deadlock prevention provides a set of methods for ensuring that at least one of the necessary conditions cannot hold. Deadlock avoidance requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, it can decide for each request whether or not the process should wait.  If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may arise. Here the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred and an algorithm to recover from the deadlock. If a system neither ensures that a deadlock will never occur nor provides a mechanism for deadlock detection and recovery, then we may arrive at a situation where the system is in a deadlocked state yet has no way of recognizing what has happened. In this case, the undetected deadlock will result in decrease of the system's performance, because resources are being held by processes that cannot run and because more and more processes, as they make requests for resources, will enter a deadlocked state. Finally, the system will stop functioning and will need to be restarted manually.  Deadlock Prevention For a deadlock to occur, each of the four necessary conditions must hold. By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of a deadlock. Deadlock-prevention algorithms prevent deadlocks by restraining how requests can be made. The side effects of preventing deadlocks by this method are low device utilization and reduced system throughput. 1. Mutual Exclusion The mutual-exclusion condition must hold for non sharable resources. For example, a printer cannot be simultaneously shared by several processes. Sharable resources, do not require mutually exclusive access and thus cannot be involved in a deadlock. Read-only files are a good example of a sharable resource. If several processes attempt to open a read-only file at the same time, they can be granted simultaneous access to the file. A process never needs to wait for a sharable resource. Ie We cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are intrinsically non sharable. 2. Hold and Wait To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever a process requests a resource, it does not hold any other resources. One protocol that can be used requires each process to request and be allocated all its resources before it begins execution. An alternative protocol allows a process to request resources only when it has none. A process may request some resources and use them. Before it can request any additional resources, it must release all the resources that it is currently allocated. Both these protocols have two main disadvantages. First, resource utilization may be low, since resources may be allocated but unused for a long period. Second, starvation is possible. A process that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other process. 3. No Preemption The third necessary condition for deadlocks is that there be no preemption of resources that have already been allocated. To ensure that this condition does not hold, we can use the following protocol. If a process is holding some resources and requests another resource that cannot be immediately allocated to it , then all resources currently being held are preempted. The process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting. Alternatively, if a process requests some resources, we first check whether they are available. If they are, we allocate them. If they are not, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process. If the resources are neither available nor held by a waiting process, the requesting process must wait. While it is waiting, some of its resources may be preempted, but only if another process requests them. A process can be restarted only when it is allocated the new resources it is requesting and recovers any resources that were preempted while it was waiting. 4. Circular Wait The fourth and final condition for deadlocks is the circular-wait condition. One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration. To illustrate, we let R = {R1 , R2,... , Rn} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering. Formally, we define a one-to-one function F: R -> N, where N is the set of natural numbers. For example, if the set of resource types R includes tape drives, disk drives, and printers, then the function F might be defined as follows: F(tape drive) = 1 F(disk drive) = 5 F(printer) = 12 We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration.