What Causes Deadlock in an Operating System?

TL;DR

Deadlock occurs when two or more processes remain blocked because each is waiting for an event that cannot happen. In resource allocation, it requires four conditions to exist together: mutual exclusion, no pre-emption, hold and wait, and circular wait. If any one condition is absent, the described deadlock situation may not occur.

Transcript

Deadlock, deadlock is what? If 2 and more processes are waiting on happening of some event but that event doesn't happen, that is called the deadlock. And those 2 processes are in the deadlock state. Means to understand by a simple example, Let's say that I want to open an account in a bank. I go to the bank and tell the bank personnel that I want ... Read More

Key Insights

• Deadlock is a blocked state in which two or more processes wait for events that cannot happen. Because the awaited events depend on actions from processes that are themselves blocked, none of the participating processes can continue execution.
• A bank account dispute illustrates deadlock when the customer insists that the account must be opened before depositing money, while the bank insists that money must be deposited before opening the account. Both sides wait for the other to act first.
• Two opposing cars illustrate deadlock when each driver waits for the other to reverse. If neither driver moves because both insist on proceeding in their chosen direction, both cars remain stuck and the event required for progress never occurs.
• A semaphore deadlock occurs when P1 holds S1 and requests S2 while P2 holds S2 and requests S1. Each process has made one semaphore unavailable and cannot obtain the other, so both enter a blocked state without anyone available to unblock them.
• Mutual exclusion means a resource is used by only one process at a time. A printer demonstrates this condition because pages from separate processes should not be printed simultaneously through interleaved use of the same resource.
• No pre-emption means a resource is not forcibly taken from the process holding it. The holding process keeps the resource until it executes, rather than being stopped and required to release the resource when another process requests access.
• Hold and wait means a process retains resources already allocated to it while requesting additional resources. For example, P1 can keep R1 while waiting for R2, as P2 keeps R2 while waiting for R1.
• Circular wait is a dependency loop among processes and resources. In the three-process example, P1 holds R1 and requests R3, P3 holds R3 and requests R2, and P2 holds R2 and requests R1, completing the circle.

Questions & Answers

Q: What is deadlock in an operating system?

Deadlock is a state in which two or more processes are waiting for events that cannot happen. Each process remains blocked because its progress depends on another blocked process or an unavailable resource. Since none of the involved processes can perform the action required by another, they cannot continue or unblock one another.

Q: What are the four necessary conditions for deadlock?

The four necessary conditions are mutual exclusion, no pre-emption, hold and wait, and circular wait. Mutual exclusion restricts a resource to one process at a time. No pre-emption prevents forced resource removal. Hold and wait allows retained resources during new requests, while circular wait creates a loop of dependencies. All four must exist together.

Q: How does mutual exclusion contribute to deadlock?

Mutual exclusion requires each relevant resource to be used by only one process at a time. Other processes must wait until the current holder finishes. A printer is an example because two processes should not interleave their printed pages through simultaneous use. This exclusive access can contribute to deadlock when combined with the other three necessary conditions.

Q: What does no pre-emption mean in a deadlock?

No pre-emption means that a resource allocated to a process cannot be forcibly removed simply because another process requests it. The process holding the resource keeps it until it executes. In the resource example, P1 continues holding R1 while requesting R2, rather than being stopped and ordered to release R1 for P2.

Q: What is the hold-and-wait condition in deadlock?

Hold and wait occurs when a process retains one or more allocated resources while waiting for additional resources. P1 can hold R1 while requesting R2, and P2 can hold R2 while requesting R1. Neither releases what it already possesses while waiting, so both processes can remain blocked when their requested resources are unavailable.

Q: What is circular wait in resource allocation?

Circular wait is a closed loop in which each process holds a resource needed by another process in the loop. In the example, P1 holds R1 and requests R3, P3 holds R3 and requests R2, and P2 holds R2 and requests R1. These linked requests return to P1 and complete the dependency circle.

Q: How do two semaphores create a deadlock?

Two semaphores create the described deadlock when P1 acquires S1 and waits for S2, while P2 acquires S2 and waits for S1. Each semaphore has been made unavailable by one process, and each process needs the semaphore held by the other. Both enter the blocked state, and neither can perform the action needed to release its semaphore.

Q: Why is a resource dependency loop not enough by itself to confirm deadlock?

A resource dependency loop represents circular wait, but circular wait is only one of the four required conditions discussed. Mutual exclusion, no pre-emption, and hold and wait must also be present. The resource diagram can therefore look like a deadlock situation, but the complete set of conditions must be checked before declaring that deadlock is occurring.

Summary & Key Takeaways

• Deadlock is a state in which two or more processes wait for events that cannot occur, leaving every involved process blocked. Everyday examples include a bank and customer each demanding the other act first, or two drivers refusing to move their cars back so either vehicle can proceed.

• A technical example uses two processes and two semaphores. P1 holds S1 while requesting S2, and P2 holds S2 while requesting S1. Because neither process can obtain its requested semaphore or release its held semaphore through execution, both remain blocked and no process can unblock the other.

• Deadlock depends on four conditions existing together: mutual exclusion, no pre-emption, hold and wait, and circular wait. Resources must be exclusively used, cannot be forcibly removed, remain held while additional resources are requested, and form a loop of dependencies among processes. All four must hold to identify deadlock.