Deadlock facts for kids

Two computer tasks (P1 and P2) are stuck. P1 has R2 and needs R1. P2 has R1 and needs R2. Neither can move forward!

Imagine cars at a four-way stop. If everyone tries to go at the same time, they get stuck in a deadlock. This is like computer tasks getting stuck.

In computer science, a deadlock happens when a group of computer programs or tasks get stuck. Each task is waiting for another task in the group to do something, like releasing a resource it needs. It's like a traffic jam where no one can move!

Deadlocks are a common problem in systems where many tasks run at the same time. This includes multiprocessing (many processors working together) and distributed systems (computers working together over a network). In these systems, tasks often use special "locks" to share resources like memory or files. These locks help keep things organized, but they can also cause deadlocks.

In an operating system, a deadlock occurs when a program or task is waiting for a system resource that another waiting program already has. And that other program is also waiting for a resource held by yet another program. If this cycle continues, no program can ever finish its work.

In communication systems, deadlocks can happen if messages get lost or corrupted. This is different from resource sharing problems.

Two computer tasks (processes) are trying to use two different resources. * A single task can go through easily. * If one task is using a resource, another task might have to wait. * A deadlock happens if the first task locks resource 1 at the same time the second task locks resource 2. Both are stuck! * To fix it, you might have to stop and restart one of the tasks.

What Causes a Deadlock?

A deadlock can only happen if four specific conditions are true at the same time. These are sometimes called the Coffman conditions.

Only One User at a Time

This is called mutual exclusion. It means that at least one resource can only be used by one program at a time. For example, a printer can only print one document at a time. If many programs could use it at once, there would be no waiting.

Holding and Waiting

This is called hold and wait. A program is already holding onto at least one resource. But it also needs more resources that are currently being used by other programs. It won't let go of what it has until it gets what it needs.

No Taking Back Resources

This is called no preemption. Once a program has a resource, it won't give it up until it's completely done with it. No other program can force it to release the resource.

Waiting in a Circle

This is called circular wait. Imagine a chain of programs. Program 1 is waiting for a resource held by Program 2. Program 2 is waiting for a resource held by Program 3, and so on. Finally, the last program in the chain is waiting for a resource held by Program 1. This creates a full circle where everyone is waiting for someone else.

If all four of these conditions are met, a deadlock can occur.

How Computers Handle Deadlocks

Most computer operating systems today can't stop deadlocks from happening in the first place. When a deadlock occurs, different systems deal with it in different ways. Most methods try to prevent one of the four conditions (especially the "circular wait" one) from happening.

Ignoring Deadlocks

Some systems just pretend deadlocks will never happen. This is like burying your head in the sand! It's used when deadlocks are very rare and don't cause much damage when they do occur. Older systems like MINIX and UNIX sometimes used this approach.

Finding Deadlocks

This method allows deadlocks to happen. Then, the system checks to see if a deadlock has occurred. If it finds one, it tries to fix it. The system keeps track of which programs have which resources. If a deadlock is found, the system might:

• Stop Programs: It might stop one or more of the programs involved in the deadlock. Stopping all of them fixes the problem quickly, but you lose any work those programs were doing. Stopping one at a time is slower because the system has to check for the deadlock again after each stop.
• Take Back Resources: The system might take resources away from programs and give them to others until the deadlock is broken.

Stopping Deadlocks Before They Start

This approach tries to prevent any of the four Coffman conditions from ever happening.

• Sharing Resources: If resources could always be shared, there would be no "mutual exclusion." But many resources, like a printer, can't be shared this way.
• Asking for Everything at Once: To prevent "hold and wait," a program could be forced to ask for all the resources it will ever need before it starts. This is often hard to know in advance. Or, a program could be forced to release all its resources before asking for new ones. This can be inefficient.
• Allowing Resources to Be Taken: If resources could always be taken away from a program (preemption), then "no preemption" wouldn't happen. But taking resources away can cause problems or make programs restart their work.
• Breaking the Circle: To prevent "circular wait," programs might be told to ask for resources in a specific order. For example, always ask for resource A before resource B. This breaks the circular waiting chain.

Avoiding Deadlocks

This is different from prevention. Deadlock avoidance means the system carefully checks every request for a resource. It only grants the request if it's sure that doing so won't lead to a deadlock later. This requires the system to know in advance which resources a program will need. A well-known algorithm for this is called the Banker's algorithm.

What is a Livelock?

A livelock is similar to a deadlock. Programs are stuck and can't make progress. But instead of just waiting, they are constantly changing their state. They keep trying to do something, but because of how they react to each other, they never actually get anywhere. It's like two people trying to pass each other in a narrow hallway, constantly stepping left and right at the same time, never getting past.

Livelocks can happen if a system tries to fix a deadlock but the fix itself causes the programs to keep trying and failing in a loop.

Deadlocks in Distributed Systems

Distributed deadlocks happen in distributed systems, which are computer systems spread across many different computers. These deadlocks can occur when different parts of a program on different computers are trying to use shared resources or communicate.

It's harder to detect these deadlocks because the information is spread out. Sometimes, a "phantom deadlock" can be detected. This is a deadlock that seems to exist because of delays in messages between computers, but it's not a real deadlock.

See also