Deadlock - Traits and Prevention - Essay Example

Insert Deadlock: Characteristics and Prevention Computing systems of our generation are created to be multiprogram systems. Multiprogramming allows computer processes to request for CPU resources and use them at specifically allocated times. When the computer resources are being used by several other processes in the CPU, the process requesting a resource will enter the waiting state. A deadlock will arise when all the other resources in the CPU are also in a waiting state for the same resource the process has requested. Therefore, a deadlock happens when the processor begins a waiting state because a resource asked for is constantly being called by an alternate waiting processor, which is also waiting for another resource. When a process cannot change its situation indefinitely due to another waiting process using the same resource, then this leads to a system being in deadlock (Kaveh and Wolfgang). Under normal circumstances, resource allocations in a system undertake the following steps. A process requests a resource and the process is suspended until the resource is available. The process then uses the resource once it has been allocated. Finally, the process releases the resource. A system might have two processes running process-A and process-B namely. Process-A requests for resource-A and gets it. Process-B requests for process-B and is allocated to it. Process-A requests for process-B and waits for it because it id being used by Process-B. Process-B requests for process-A and waits for it because it is being used by process-A. The situation above illustrates that Process-A and Process-B are in a deadlock state. Deadlocks have the following assumptions. The process cannot be allocated a resource before it requests for it. Therefore, the order it follows is request then use it and release the resource. A process can also only request more resources than the number of resources available for use by the system. Multiprogramming systems have a resource table than manages resources by showing free and occupied resources being used by processes. It also keeps queues of the processes that are waiting for certain resources. The queues will indicate the time a resource will be released by a process thus making it available for use by other resources. Characteristics of a Deadlock Deadlocks only occur mutual exclusion, hold and wait, no preemption and circular wait conditions simultaneously hold in the system. Mutual Exclusion Mutual exclusion occurs when one or at least one of the resource is not sharable. It means that only a few numbers of processes can use the resource at a time. A requesting process has to wait for a resource to be released if it requests the process when it is being used by another process. To illustrate mutual exclusion, Process-A can have an exclusive control of a resource that Process-B needs and vice versa. Process-A and Process-B will block indefinitely while waiting for one process or other processes to free the resource. Mutual exclusion is not restricted to objects in the computer memory (Bach Hansen). Resources or entities that can be given mutual exclusive access in multiprogram systems include: Hardware – tape drives, CD-ROM, printers. Information – mutexes, shared memory or records in the database. Resources in the system are anything that can be requested and acquired, utilized and released over a certain period. Resources are classified as either preemptive and non-preemptive. Preemptive resources can be taken away from the process without causing any harm. For example in main memory, swapping is implemented to give memory allocated to a Process-A to Process-B without the Process-A knowing. Non-preemptive is a resource that cannot be taken away randomly without causing computations to cause an error or fail. When burning a CD has already begun, taking away the writer will ruin the CD in question. In mutual exclusion, only one process can use a resource at a time. Hold and Wait Hold and wait occurs when at least a process ( Process-A ) that is holding one or more resources and waiting for other resources that are being held or being utilized by other processes in the system. Therefore, there must be at least one process that is holding one resource and is waiting for another resource (Bach Hansen). No Preemption No preemption means that no resource in the system can be preempted or taken away from the process before the holding process completes the task it has with that resource. Preemption is mostly done in systems in order to prevent a specific anticipated event from happening. A deadlock is present when Process-A holds resources, and a second process Process-B may need that resource in order to proceed while second process, Process-B may hold the resources needed by Process-A (Bensalem). Circular Wait Deadlock in circular wait occurs when two or more processes are in a circular chain with each process waiting for a resource that is being held by the next member in the chain. Consider a set of many processes, { Process-A, Process-B, Process-C, ….., Process-n}. Process-A is waiting for a resource being used or held by Process-B. Process-B is waiting for a resource held by Process-C. Process-n is waiting for the process being held or being used by Process-A. The chain creates a lack of resources because a process in the chain cannot release a process because it is waiting for a resource from a process in the chain. Deadlock Detection Deadlock detection is the process of finding out, and determining is a deadlock has occurred. Deadlocks can occur either unwillingly or willingly. The aim of detection is to find out if a deadlock is occurring and determine the processes and the specific resources in the deadlock. This process will enable the system to clear the deadlock. Detection of deadlocks can be done using algorithms that will determine if circular wait exists (Knapp). Resource Allocation Graphs Resource allocation graphs are created so that allocation relations of processes and resources can be easily seen. The figures that make up resource allocation graphs are: Squires – they represent processes. Large circles – represent classes of identical devices. Small circles – they are drawn inside large circles, and they indicate all the number of devices in each class. Request edge ( P1 --> R1) - depicts that the process P1 needs to use the resource R1. Allocation edge (R1 → P1) - illustrates that the process P1 is allocated the resource R1. Process PA request for resource R1 that is allocated to another process PB. Process-PB also requests for resource R2, but the resource is allocated to process PA. This process creates a cycle withhold and waits, therefore, creating a deadlock. The diagram above shows process P0, P1, P3, P4, and P5 which are using single instance resources R6, R5, R3, R4, R0, and R1. Cycles in allocation graphs suggest that there can be circular wait or a deadlock in a running CPU system. The case is not always like this since a cycle can be present in the system, but does not necessarily mean that a deadlock is present. Request graphs and resource allocation always change as the processes in the system request for resources to use, acquire them and when they release them to the computers operating system (Coffman). Reduction of Resource Allocation Graphs Graph reductions are a technique used in detecting deadlocks. Processes that are presumed to be able to execute to completion and the processes that will be left in a deadlocked state is identified. A graph may be reduced by a process if the processs resource request is granted (Kaveh and Wolfgang). The process is the same as showing the graph if a specific process is allowed to complete execution and return the resources that had been assigned to it back to the system. Reduction of a graph is shown by removing the arrows assigned to that process from resources, and by removing arrows from the process to resources. A deadlock is not present if a graph can be reduced by all its processes. But if a graph cannot be reduced by all the processes its has, then this processes that are irreducible will make up the set of deadlocked processes in the graph (Knapp). Deadlock Prevention The main aim of deadlock prevention program the system into removing any possibility of deadlocks from occurring and causing problems. Deadlock prevention methods are very useful but often result into a poor way of utilizing the resources. The basis of deadlock prevention is making sure that the four conditions that need to happen for a deadlock to happen are denied from happening. According to Havender, the following methods can be used to deny some of the conditions from happening (Havender). A process is required to request all its processes at once and will only be allowed to proceed if all the resources have been granted to it. If a process holding a specific resource is denied access to a further request, then that process must first release the original resource it is holding. It is also necessary for the resource to request the resources again together with additional resources. A linear ordering formula of all resource types on all processes should be implemented as this will only allow request of only those resources of types later in the ordering. The suggestions above are designed to deny the conditions necessary for a deadlock to happen. Denying Wait for Condition A process must request for all resources a process needs at once, and the system must, therefore, grant all of them or deny the process all the resources. The process has to wait for all the resources it needs before the system allows it to proceed. When all the resources are not available then, the said process has to wait for resources, and it cannot hold resources at this time. The process above is very effective but leads to a lot of resource wastages. Resource wastages can be eliminated through dividing a computer program into several program steps that are executed independently to each other. This process allows resource allocations to be monitored and controlled at the said steps rather than for the entire computer program. It will reduce wastes but requires advanced and great system design and execution. Another downfall on designing a system to execute in several steps is that it can cause indefinite postponements. Indefinite postponement is because not all the resources required are available at once. Therefore, the system must allow enough number of jobs to run into completion so that they can free the resources they are holding before other jobs waiting for the resources can continue to execute (Bensalem). Denying No-Preemption Condition. If a process holding a specific resource is denied access to a further request, then that process must first release the original resource it is holding. This process denies the no-preemption condition. Assume that processes in the system are allowed to hold resources while requesting other resources. If a sufficient number of resources are still left in the system so that they are available for other processes requests. The system cannot be deadlocked under these conditions. A deadlock will occur if the process A holds a resource that process B may require in order to continue with its execution while process B may hold the resource needed by process A. When a process holding resources can no longer be given additional resources, the process is supposed to free all the resources it is holding. The process will then be allowed to request all the processs at another time. The negative effect of these methods is that, the process may lose all the work it was executing at the time when it releases all the resources it is holding. Denying no-preemption can be applied when loosing work is infrequent. The biggest problem that may arise from denying no-preemption is the high frequency of indefinite postponement happening. Indefinite postponement will prompt the system to remove the process causing it so that other processes can be allowed to proceed. Indefinite postponement also consumes a lot of resources and degrades the systems performance. Denying Circular Wait Condition Linear ordering of all resource types on all processes allows the request of only those resources of types later in the ordering. This ordering denies possibilities of circular wait from happening. The denial is because all the resources have a unique id, and processes must request them in a linear ascending order. For effective denial of a circular wait, resources should be requested in ascending order by the unique id numbers or resource numbers assigned to them. Resource ids are assigned during installation time and must be retained for a longer time. Addition of new resources at installation point of other computer programs will prompt the system to rewrite existing programs, and resources ids in the system. Resource numbers should be assigned to reflect the priority of jobs as this ensures efficient operation. Processs that need resource in another order other than that specified during its installation will be required to hold resources it has acquired for a long period before using them. Holding the resources for a long period leads to wastage of resources. Havenders linear ordering eliminates circular wait but, on the other hand, in negatively affects a users ability to easily and freely write code for computer applications. The negative is because new operating systems are required to create user-friendly environments. User-friendly environments enable people to develop applications with minimal restrictions in hardware and software (Havender). Deadlock Avoidance Deadlock avoidance is implemented to avoid deadlock when all the conditions for a deadlock to occur are in place. Dijkstras Bankers algorithm is used to avoid deadlocks. The algorithm has the name bankers because its process involves a banker who makes loans and receives payments from a certain source of capital Bankers Algorithm Resources in bankers algorithm illustration refer to the resources of the same type. To understand the bankers algorithm: consider an operating system that has to share a fixed number of tape drives, y, among a specific number of users, n. The user in this case is required to specify the maximum number of tape drives she requires to execute and complete the job in the computer system. The user will be allocated y tape drive if her requests tape drives that do not exceed y. The user may release the tapes one at a time. Therefore, the total number of tapes that a user can be allocated cannot exceed the maximum number a user can be allocate. In order to ensure that the operating system satisfies users needs, the user has to guarantee that the tape drives will be released after being used to the operating system within a specified finite amount of time. The above is described as safe since the user completes their jobs in a finite amount of time. Suppose there are ,u, number of users. Let loan ( x ) represent a users xs current loan of tape drives. If user 6 has been allocated three tape drives, then loan ( 6 ) = 3. Let max ( x ) be the maximum need of user x so that if user 3 has a maximum need of two tapes then max (3 ) = 2. Let claim ( x ) be the current claim of client where a clients claim is the same as his maximum need less the users current loan. If a user 8 has a maximum need of five drives and a current loan of four tapes, then claim ( 8 ) = max ( 8 ) - loan ( 8 ) - 5 – 4 = 1 An operating system controls y tape drives. Let, a, be the number of drives that can still be allocated to other users. Then, a, is equal to y less the sum of loans to the other users in the system. Bankers algorithm states that users can only be allocated tapes when allocation results are in a safe state rather in an unsafe state. A safe state is one where the total resource situation is such that all the users requesting the resource would be able to finish eventually. An unsafe state leads to a deadlock. Safe State Current loan Maximum need User 1 1 4 User 2 4 6 User 3 5 8 Available 2 The state above is safe because all the three user are possible to finish. Therefore, the key to the state being safe is that the user is left with at least one way to execute to the end or to finish. Unsafe State Current loan Maximum need User 1 8 10 User 2 2 5 User 3 1 3 Available 1 In the figure above, 12 types are in use and only a single tape drive is available for allocation. The diagram means that whichever user request for the single available drive, the operating system cannot guarantee that all users will be able to finish. A deadlock in this state can occur if each process needs to request for at least one more drive before releasing any drives to the pool. An unsafe state implies that an unfortunate sequence of event might be able to lead to a deadlock occurring. Safe State to Unsafe State Transition A safe state can still lead to unsafe states in the future. Current loan Maximum need User 1 1 4 User 2 4 6 User 3 5 8 Available 2 The state above is a safe one but can transition into an unsafe state as illustrated in the figure. The state below arises when user three requests for one additional resource. If the system grants user three his request, then the state below would arise. Current loan Current loan Maximum need User 1 1 4 User 2 4 6 User 3 6 8 Available 1 The state above is an unsafe but does not necessarily mean that the state above is deadlocked. Therefore, completion of other user jobs cannot be guaranteed since only one resource is available for request. Banker Algorithm Resource Allocation Wait for, no-preemption and mutual-exclusion conditions are allowed, but the said processes do claim exclusive use of they have requested for and acquired or require. Processes are allowed to hold resources while waiting or requesting for additional resources, and a resource cannot be released from or preempted from a process that is holding the resource. The system can deny or grant each request from the processes. The users can request only one resource at a time as this leads to ease on the system. The system, therefore, will only grant those requests that will lead to a safe state. Requests that will lead to an unsafe state are decline until that request can be eventually satisfied as a safe one. In the end, all the requests can be satisfied so that all users can be able to execute to completion since the operating system is always maintained in a safe state at some point (Knapp). Weaknesses of Bankers Algorithm Bankers algorithm is very useful in allowing jobs under a deadlock prevention situation to proceed into completion. Despite this benefit, the weaknesses of bankers algorithm include: Bankers algorithm requires that a fixed number of resources should always be available to allocate. The number of users in the system should also always be a fixed number. This is unreasonable in multiprogram systems since the users are always increased or reduced. A modern system should allow servicing of more users due to the dynamic nature of modern systems. Bankers algorithm requires that it grants all the users requests within a known or finite time. Real system requires sophisticated guarantees than the one above. Bankers algorithm also demands that clients return all the resources within a finite time. Returning resources is not ideal for real-time systems. The bankers algorithm demands that the clients state the total number of resources they require in advance. It is very hard to know the users ultimate maximum needs (Kaveh and Wolfgang). Deadlock Recovery Deadlock in a system is broken by removing one or more of the necessary conditions for a deadlock to happen. It will lead to processes losing most or all of their work. Deadlock recovery is not an easy process because of the following factors: Knowing if a system has been deadlocked is very hard. Most systems especially real-time systems do not have proper facilities to suspend a process indefinitely, remove it completely from the system and resume it at a later time. When suspend and resume capabilities are present, a skilled operator would still be required due to the complexity of attending to its overhead. Recovery from deadlocks with many processes requires a lot of work. Modern system recovers from deadlocks by removing at least one processor more from the system forcibly so that it can reclaim its resources. The processor processes will be lost, but it will allow other remaining processs to run into completion. The processs that will be sacrificed have to follow a certain priority order. The difficulties that arise from these are: Priorities of the deadlocked processes are not always available and should the operator of the system has to make priority decisions by himself. The priorities of the processes might be incorrect due to special considerations like deadline scheduling where low priority processes have temporary high priorities. The choice of processs to require a large amount of effort to correctly determine. Real-time systems in the modern world that would cause fatal consequences when a deadlock occurs include: a gasoline refinery control system, an automated heart pacemaker must not fail as it can cause death. Deadlocks should be avoided in completely in these occasions, but they cannot be completely ruled out. Therefore, operating system designers must come up with an effective way of dealing with deadlocks in critical real-time systems (Knapp). Deadlocks with Future Systems Future and modern system needs to consider deadlock avoidance critically because: future real-time systems are designed to have asynchronous and parallel operations. The systems will be multiprogram meaning that there will be more resource conflict increasing the frequency of deadlocks happening. Future systems will have dynamic resource allocation. The processs in the system will be able to release and acquire resources freely. Data will also be viewed as a resource, and this increases the number of resources modern operating systems will be required to manage. The burden of managing deadlocks in future systems will be on the operating systems (Bensalem). Conclusion Operating systems in todays computing environments are becoming the most important component. Extensive use of operating systems to manage the resources of the system leads to problems of deadlocks and indefinite postponement of processes. Spooling systems are prone to deadlocks especially if the space for spool file is filled before the processs running have finished execution (Coffman). Deadlocks cannot happen until the four necessary conditions happen. The conditions are "wait for", mutual exclusion, no-preemption and circular wait. Dealing with deadlocks requires a system to ensure that none of the conditions above occurs. Deadlock prevention that involves preventing one of the four conditions from also happening helps to minimize deadlocks. Deadlock recovery eliminates deadlocks by removing or more processs holding resources. Enhancing suspends and resume functionalities of an operating system greatly improves deadlock recovery process. Deadlocks in modern systems are unusual an annoyance. This does not however mean that they do not happen. Real-time system designers should, therefore, come up with ways that greatly minimize the chances of deadlocks from happening. Designer of modern operating systems has a great challenge in achieving this because the current system operates with more dynamic resource allocation, many users and more processs run concurrently. Deadlocks are an annoyance in operating systems that should be avoided and removed since the effects may be fatal especially critical and complex systems. Works Cited Bach Hansen, P. OPerating System Principles. Prentice Hall, 1986. Bensalem, Sadek. Fernandez, Jean-Claude. "Confirmation of Deadlock Potentials Detection by Runtime Analysis." Proceedings of the 2006 Workshop on Parallel and Distributed Systems:Testing and Debugging(ACM) (2006). Coffman, Edward G. "System Deadlocks." ACM Computing Surveys (1971). Havender, James W. "Avoiding DEadlock in Multitasking Systems." IBM Systems Journal 7 (1968): 2:74. Kaveh, Nima and Emmeerich Wolfgang. Deadlock Detection in Distributed Object Systems. London: University College London, 1998. Knapp, Edgar. "Deadlock DEtection in Distributed Databases." ACM Computing Surveys 19 (n.d.): (4):303-328. Read More