Show
Both processes need resources to continue execution. P1 requires additional resource R1 and is in possession of resource R2, P2 requires additional resource R2 and is in possession of R1; neither process can continue. Four processes (blue lines) compete for one resource (grey circle), following a right-before-left policy. A deadlock occurs when all processes lock the resource simultaneously (black lines). The deadlock can be resolved by breaking the symmetry. In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock.[1] Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement process synchronization.[2] In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process.[3] If a process remains indefinitely unable to change its state because resources requested by it are being used by another process that itself is waiting, then the system is said to be in a deadlock.[4] In a communications system, deadlocks occur mainly due to loss or corruption of signals rather than contention for resources.[5] Two processes competing for two resources in opposite order.
Individually necessary and jointly sufficient conditions for deadlock[edit]A deadlock situation on a resource can arise only if all of the following conditions hold simultaneously in a system:[6]
These four conditions are known as the Coffman conditions from their first description in a 1971 article by Edward G. Coffman, Jr.[9] While these conditions are sufficient to produce a deadlock on single-instance resource systems, they only indicate the possibility of deadlock on systems having multiple instances of resources.[10] Deadlock handling[edit]Most current operating systems cannot prevent deadlocks.[11] When a deadlock occurs, different operating systems respond to them in different non-standard manners. Most approaches work by preventing one of the four Common conditions from occurring, especially the fourth one.[12] Major approaches are as follows. Ignoring deadlock[edit]In this approach, it is assumed that a deadlock will never occur. This is also an application of the Ostrich algorithm.[12][13] This approach was initially used by MINIX and UNIX.[9] This is used when the time intervals between occurrences of deadlocks are large and the data loss incurred each time is tolerable. Ignoring deadlocks can be safely done if deadlocks are formally proven to never occur. An example is the RTIC framework.[14] Detection[edit]Under the deadlock detection, deadlocks are allowed to occur. Then the state of the system is examined to detect that a deadlock has occurred and subsequently it is corrected. An algorithm is employed that tracks resource allocation and process states, it rolls back and restarts one or more of the processes in order to remove the detected deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler of the operating system.[13] After a deadlock is detected, it can be corrected by using one of the following methods:[citation needed]
Prevention[edit](A) Two processes competing for one resource, following a first-come, first-served policy. (B) Deadlock occurs when both processes lock the resource simultaneously. (C) The deadlock can be resolved by breaking the symmetry of the locks. (D) The deadlock can be prevented by breaking the symmetry of the locking mechanism. Deadlock prevention works by preventing one of the four Coffman conditions from occurring.
Deadlock avoidance[edit]Similar to deadlock prevention, deadlock avoidance approach ensures that deadlock will not occur in a system. The term "deadlock avoidance" appears to be very close to "deadlock prevention" in a linguistic context, but they are very much different in the context of deadlock handling. Deadlock avoidance does not impose any conditions as seen in prevention but, here each resource request is carefully analyzed to see whether it could be safely fulfilled without causing deadlock. 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. Deadlock avoidance algorithm analyzes each and every request by examining that there is no possibility of deadlock occurrence in the future if the requested resource is allocated. The drawback of this approach is its requirement of information in advance about how resources are to be requested in the future. One of the most used deadlock avoidance algorithm is Banker's algorithm.[17] Livelock[edit]A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. The term was coined by Edward A. Ashcroft in a 1975 paper[18] in connection with an examination of airline booking systems.[19] Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.[20] Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can be repeatedly triggered. This can be avoided by ensuring that only one process (chosen arbitrarily or by priority) takes action.[21] Distributed deadlock[edit]Distributed deadlocks can occur in distributed systems when distributed transactions or concurrency control is being used. Distributed deadlocks can be detected either by constructing a global wait-for graph from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing. Phantom deadlocks are deadlocks that are falsely detected in a distributed system due to system internal delays but do not actually exist. For example, if a process releases a resource R1 and issues a request for R2, and the first message is lost or delayed, a coordinator (detector of deadlocks) could falsely conclude a deadlock (if the request for R2 while having R1 would cause a deadlock). See also[edit]
References[edit]
Further reading[edit]
External links[edit]
Which of the events that causes the processes to be created when an operation system is booted?There are four principal events that cause processes to be created they are system initialization, execution of a process creation system call by a running process, a user request to create a new process, and initiation of a batch job. When an operating system is booted, typically several processes are created.
Which of the following is a hardware solution to the critical region problem?Synchronization hardware is a hardware-based solution to resolve the critical section problem.
What is the advantage of the Exokernel scheme?Exokernels saves a layer of mapping which is the advantage of the exokernel scheme. In the client-server model, as shown in the figure given below, all the kernel does is handle the communication between the clients and the servers.
Which of the following process state transitions is incorrect?Answer : - 'Wait to Run' is invalid state transition.
|