Chapter 8: Deadlocks: Prevention, Avoidance, Detection, and Recovery

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Welcome to the Deep Dive, the show where we take your sources, extract the most important nuggets of insight, and transform complex ideas into knowledge you can actually use.

Today, we're plunging into a classic conundrum in the world of computing, one that can bring even the most powerful systems to a grinding halt.

I'm talking about a situation where everyone's waiting for everyone else and absolutely no one can move.

Imagine that famous, almost comical law from the Kansas legislature back in the early 20th century.

It famously declared, when two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.

Now that sounds like a joke, right, but it's actually a perfect illustration of what we call a deadlock.

Yeah, the Kansas train law.

It's a great analogy.

You immediately get the idea of being completely stuck.

Exactly.

And in computing, a deadlock isn't about trains, obviously, but the feeling is just as frustrating.

It's a complete standstill in a multitasking environment.

You've got a group of running programs, or threads as we call them, and they're all waiting for resources.

Resources that can only be released by other threads within that exact same group.

It's like a digital Mexican standoff.

Everyone's pointing a metaphorical gun, waiting for someone else to lower theirs first, but no one can.

Precisely.

So our mission today is to unpack this absolutely crucial operating system concept.

We'll explore how deadlocks actually happen, the specific conditions that create them, and then look at the clever strategies that both application developers and operating systems use to prevent them, or maybe avoid them, or sometimes just detect and recover from them.

And understanding this isn't just, you know, academic theory, it's really vital as modern computing pushes for more and more concurrency, things running at the same time all over the place.

Absolutely.

The more things run in parallel, the higher the chance they might, well, step on each other's toes.

It's fascinating how these computer science problems mirror real world dilemmas like that train law, really helps visualize the core issue.

It truly does.

So let's start with that core concept.

When we talk about deadlocks in computing, we keep saying resources.

What exactly are we talking about?

Resources is pretty broad here.

It can mean physical stuff like CPU cycles,

specific files or I .O.

devices, printers, scanners, that sort of thing.

But, and this is really important, it also includes logical resources, things like mutex locks and semaphores.

Ah, right.

Those software tools used to control access to shared data.

Exactly.

They're essential for coordination.

Think of resources as having a type, like CPU, and then multiple instances.

So maybe you have four CPUs, that's four instances of the CPU resource type.

And if any instance will do the job, they're basically interchangeable.

That's the idea, yeah.

And threads, these individual units of execution within a program, they usually follow a pretty standard pattern when they use these resources.

What's that pattern?

It's kind of a three -step dance.

First, a thread requests the resource.

If it's free, great.

If not, the thread has to wait.

Step one, ask.

Right.

Step two, it uses the resource.

Maybe it's reading from that file or doing some calculation protected by that mutex lock.

Step two, do the work.

And step three, it releases the resource when it's finished, makes it available for others.

Request, use, release.

Simple enough.

Seems simple, but today, mutex locks and semaphores are honestly the most common culprits in deadlocks.

Precisely because they manage access to shared data structures that lots of threads might want to touch simultaneously.

And the operating system, it's constantly keeping track who has what resource, who's waiting for which one.

It's like a resource accountant.

Let's make this really concrete.

Can you walk us through a simple example of how a deadlock might actually pop up in a multi -threaded program?

Sure.

Let's use those POCX mutex locks we mentioned.

Match we have two of them.

Let's call them first mutex and second mutex.

Okay, two locks.

Now, picture two threads.

Threat needs both locks.

Its plan is first grab first mutex, then grab second mutex.

Got it.

Thread one goes one, then two.

But simultaneously, we have thread two.

It also needs both locks, but it tries to acquire them in the opposite order.

First second mutex, then first mutex.

Uh -oh.

I think I see where this is going.

Thread two goes two, then one.

Exactly.

Here's the deadlock scenario.

What if threading successfully acquires first mutex?

Okay.

It has lock one.

And it pretty much the exact same moment.

Thread two successfully acquires second mutex.

It has lock two.

Now threading is holding first mutex, but it's stuck waiting for second mutex.

But second mutex is held by thread two.

And thread two.

Thread two is holding second mutex, and it's stuck waiting for first mutex, which threading has.

So they're both blocked permanently, waiting for each other.

Yep.

That's your classic deadlock.

Just like those Kansas trains, neither can proceed.

And I guess the really frustrating part is that this might not happen every time you run the program.

Precisely.

That's a huge challenge.

Deadlocks are often incredibly hard to find during development and testing.

Whether it happens can depend entirely on the system's CPU scheduler, the specific timing, how busy the system is.

It might only occur once in a blue moon under very specific load conditions.

Makes them a nightmare to debug.

Right.

Speaking of things that stop progress, there's something related called livelock.

Also aliveness failure, right?

Meaning the system isn't making progress.

I always think of two people trying to pass in a narrow hallway.

You both step right, bump.

You both step left, bump again.

You're constantly moving, but you're not actually getting anywhere.

That's a perfect analogy for livelock.

The key difference from deadlock is that the threads aren't technically blocked.

They're not suspended waiting for an event.

Instead, they're actively, continuously trying an action that fails, maybe releasing resources they hold, and then immediately retrying, often in sync.

So how would that look in our lock example?

Okay, imagine our two threads again.

But instead of using thread mutex lock, which blocks until the lock is free, they use thread mutex draw lock.

Trylock attempts to grab the lock, but if it can't get it immediately, it just returns an error instead of waiting.

Okay, so it doesn't block.

Right.

Now imagine the threads are programmed like this.

Try to get lock one.

If successful, try to get lock two.

If that fails, release lock one and start over.

And the other thread does the same, but in a reverse order.

If they get into a bad timing cycle, they could both continuously succeed in getting their first lock, fail to get the second, release the first, and immediately retry, over and over.

Burning CPU cycles, looking busy, but achieving absolutely nothing, like the hallway dance.

Exactly.

They're live, but making no progress.

So how do you break that kind of loop, the digital hallway dance?

Live lock usually happens because the threads are retrying their failing operations in lockstep, or too quickly.

The common solution is to introduce some randomness, or at least a backoff period.

Each thread, when it fails, should wait a random amount of time before retrying.

That breaks the synchronized failing pattern.

Ah, randomness to the rescue.

It's actually a fundamental technique.

Ethernet networks use exactly this strategy.

When two computers try to send data at the same time and cause a collision,

they both back off for a random period before trying to send again.

That avoids constant collisions.

Fascinating.

Okay, so we've got deadlock and live lock.

Let's go back to deadlock and really dissect the ingredients.

You said there are four conditions that all have to be true at the same time for a deadlock to occur.

That's right.

All four are necessary.

If you can break even one of these conditions, you prevent the deadlock from ever forming.

Okay, let's walk through them.

What's the first one?

First is mutual exclusion.

This just means at least one resource involved must be non -shareable.

Only one thread can use it at a time.

Like a printer, maybe?

Or that mutex lock we talked about.

Exactly.

If another thread requests that resource while it's in use, it has to wait.

For many resources like mutex locks designed to protect critical data, this condition is just inherent.

You can't really share them safely.

So denying this condition is often not practical.

You can't share the scissors if you both need to cut the same piece of paper at the same instant.

Got it.

Condition two.

Second is hold and wait.

This means a thread is currently holding at least one resource.

Okay, it's got something.

And at the same time, it's waiting to acquire additional resources that are currently held by other threads.

So holding some resources hostage while demanding more.

Okay, what's number three?

Third is no preemption.

This means resources can't be forcibly taken away from a thread once they've been allocated.

They can only be released voluntarily by the thread holding them, usually after that thread has finished its task with the resource.

Right.

You can't just snatch the scissors out of someone's hand mid -cut.

Not according to this rule, no.

Okay, mutual exclusion, hold and wait, no preemption.

What's the final piece of the puzzle?

The fourth condition is circular weight.

This is the one that really ties the knot.

It means there must exist a set of waiting threads, let's say T0, T1, all the way to Tn, such that T0 is waiting for a resource held by T1, T1 is waiting for a resource held by T2, and so on.

And crucially, the last thread, Tn, is waiting for a resource held by the first thread, T0.

It forms a closed loop, a circle of dependencies.

Ah, the circle.

Like in our two -thread example, thread 1 waits for thread 2's lock, and thread 2 waits for thread 1's lock.

That's a simple circle.

Precisely.

That's a circular weight involving just two threads.

And you mentioned that understanding each condition separately is important for figuring out how to stop deadlocks, even though circular weight kind of implies hold and wait is also happening.

Absolutely.

Knowing these four distinct conditions gives us different angles of attack when we think about prevention strategies.

Okay, speaking of understanding, visualizing these situations seems helpful, especially when you have more than just two threads and two resources.

Definitely.

We can model these situations very precisely using something called a resource allocation graph.

Okay, how does that work?

Picture a directed graph.

It has two kinds of nodes.

We use circles to represent the threads, the active processes or threads in the system.

Circles for threads, got it.

And we use rectangles to represent the resource types, like CPU or printer or mutex lock typing.

Rectangles for resource types, and didn't you say resources can have multiple instances?

How is that shown?

Good point.

Inside each resource type rectangle, we put dots or marks to represent the number of available instances of that resource type.

So four CPUs means four dots inside the CPU rectangle.

Okay, circles, rectangles, dots.

What about the connections, the edges?

Right, there are two types of directed edges.

An arrow going from a thread circle to a resource type rectangle means the thread has requested an instance of that resource and is currently waiting.

That's a request edge.

Thread wants resource.

Arrow points from thread to resource box.

Yep.

And an arrow going from a resource instance, one of those dots inside the rectangle to a thread circle, means that specific instance has been allocated to that thread.

That's an assignment edge.

Resource instance given to thread, arrow points from dot to circle.

Okay, so this graph maps out who has what and who wants what.

And the really crucial insight comes when we look for cycles in this graph.

Cycles, like the circular weight condition.

Precisely.

Here's the rule.

If the resource allocation graph contains no cycles at all,

then we can be certain there is no deadlock in the system.

Everyone can eventually finish.

No cycles, no deadlocks, simple enough.

But if the graph does contain a cycle, things get a little more nuanced.

If there's a cycle and every resource type involved in that cycle has only one instance, only one dot in its rectangle.

Single instance resources.

Then a cycle definitely means a deadlock exists.

All the threads involved in that cycle are deadlocked.

Cycle plus single instances equals deadlock, guaranteed.

Correct.

However, if some resource types in the cycle have multiple instances.

More than one dot in the box.

Then a cycle is a necessary condition for deadlock, but it's not sufficient.

You might have a cycle, but the system might not actually be deadlocked.

Wait, how can you have a cycle but no deadlock?

That sounds weird.

Can you give an example?

Sure.

Imagine thread A holds an instance of resource 1 and is waiting for resource 2.

Thread B holds an instance of resource 2 and is waiting for resource 1.

That's a cycle, right?

Yep.

A waits for B, B waits for A.

Classic cycle.

But now, let's say resource 2 actually has two instances.

Thread B holds one, but maybe thread C holds the other instance of resource 2, and thread C isn't part of this cycle at all.

Okay, so there's a spare resource 2 instance held by C.

Now if thread C finishes its work and releases its instance of resource 2,

that instance becomes available.

It could then be allocated to thread A who was waiting for it.

And once thread A gets resource 2, it can finish its work, release both resource 1 and 2.

And then resource 1 becomes available for thread B, breaking the original dependency.

So the cycle existed temporarily, but because there was an extra instance and another thread, C, that could release a needed resource, the potential deadlock was avoided.

Okay, that makes sense.

So a cycle is a big warning sign, especially with multiple instances.

But it doesn't automatically mean doom.

There might be a way out if other resources become free.

That's a really key distinction.

It is.

It influences how we detect deadlocks later on.

So given these complexities, what are the main ways systems actually try to handle deadlocks?

What are the broad strategies?

Generally there are three main approaches people take.

First, you can pretty much just ignore the problem.

Pretend deadlocks don't happen.

The ostrich algorithm, right?

Bury your head in the sand.

Yeah.

Yeah, that's the nickname.

It sounds irresponsible, but we'll see why it's sometimes used.

Okay, ignoring it is option 1.

What else?

Option 2 is to be proactive.

Use specific protocols or algorithms to either prevent deadlocks from ever occurring in the first place, or to avoid entering any state that could lead to a deadlock.

So prevention and avoidance.

Proactive measures.

Got it.

And the third way.

The third way is reactive.

You basically allow deadlocks to happen, but you have mechanisms in place to detect when one has occurred, and then other mechanisms to recover from it basically break the deadlock after the fact.

Ignore, prevent avoid, or detect recover.

Those are the choices.

Broadly speaking, yes.

And it's kind of surprising, isn't it, that many widely used operating systems like Linux and Windows often lean towards that first option, ignoring the problem.

Why would they do that?

Well, it often boils down to a tradeoff between cost and frequency.

Implementing robust deadlock prevention or avoidance adds overhead.

It takes extra computation, extra checks, maybe restricts how resources can be used.

In many general purpose systems,

serious deadlocks might actually be quite rare.

Maybe they happen once a month, maybe less.

So the performance cost of constantly running prevention or detection logic might be higher than the cost of, say, rebooting the system occasionally when a deadlock does occur.

That's often the calculation, yes.

They prioritize average case performance, accepting a small risk of deadlock, rather than slowing everything down slightly all the time to guarantee no deadlocks.

Of course, for critical systems, that calculation is very different.

Okay, that makes sense for general use.

But what if you can't accept that risk?

Let's dive into those proactive strategies, prevention and avoidance.

You said prevention means ensuring at least one of those four necessary conditions can never happen.

That's the core idea.

Let's look at each condition again.

Can we prevent mutual exclusion?

Make everything shareable.

Generally no.

Some resources, like printers or mutex -protected data, must be accessed exclusively.

So denying mutual exclusion usually isn't feasible.

Okay, scratch that one.

What about hold...

Wait, can we stop threads from holding one thing while waiting for another?

There are protocols for this.

One idea is a thread must request all the resources it will ever need right at the beginning before it starts running.

Get everything up front.

Yeah.

Or, another protocol says,

if a thread holds some resources and needs another, it must first release all the resources it currently holds before making the new request.

Wow, both of those sound inefficient.

They really are.

Requesting everything up front often means resources sit allocated but unused for long periods leading to really low resource utilization.

And releasing everything just to get one more thing.

That can lead to starvation, where a thread keeps releasing and re -requesting but never manages to get everything it needs because someone else always grabs a piece.

Yeah, neither seems like a great general solution.

Okay, what about no preemption?

Can we just take resources away?

We could try.

The protocol would be, if a thread is holding resources and requests another one that isn't available, the system could forcibly take away all the resources the thread is currently holding.

Oh, preempt everything.

Those preempted resources get added back to the available pool.

The thread would then have to wait until it can get its old resources plus the new one it wanted, all at once.

Where might that work?

This can work for resources whose state is easy to save and restore, like CPU registers or memory pages.

Some database systems use forms of preemption for transactions.

But – and this is a big but – it generally cannot apply to things like mutex locks and semaphores.

Why not?

Because you can't just snatch a mutex away from a thread while it's in the middle of updating a shared data structure.

Doing that would likely corrupt the data.

And mutexes are where deadlocks are most common in software.

Right, so preemption is tricky and doesn't solve the common lock problem.

That leaves us with the last condition.

Circular weight.

Right.

And breaking this condition turns out to be the most practical and widely used prevention technique, especially in software development.

Okay, how do you prevent circular weights?

The strategy is elegant.

You impose a total ordering on all resource types in the system.

Basically, you assign a unique number or rank to every type of resource – every mutex, every semaphore, every file type, etc.

Give everything a number.

Like mutex A is 1, mutex B is 5, file X is 10.

Exactly.

Then you enforce a strict rule.

Threads must request resources only in increasing order of this enumeration.

So if you need mutex A, number 1, and mutex B, number 5, you always have to request A before B.

Precisely.

You could request A, then later request B.

But you could never request B first and then request A.

How does that stop circular weights?

Think about it.

For a circular weight to happen, thread 1 needs something held by thread 2, and thread 2 needs something held by thread 1.

Let's say thread 1 holds resource re and wants rj, while thread 2 holds rj and wants re.

If we enforce the ordering rule, one of these requests must violate it.

If re has a lower number than rj, then thread 1's request, wanting rj after holding rye, is fine.

But thread 2's request, wanting re after holding rj, is illegal because it's asking for a lower numbered resource.

The system wouldn't allow it, or the programmer shouldn't write it.

A circle becomes impossible to form.

Ah, because every step in the potential circle has to follow the increasing order, you can never loop back around to the beginning resource, which would have the lowest number in that chain.

That's clever.

It is quite clever.

But establishing and enforcing that total order across a huge complex system with maybe thousands of different locks sounds like a massive headache in practice.

Oh, it absolutely is.

It requires significant discipline from developers.

There's no magic OS enforcement usually.

It's a programming convention.

How do people manage it?

Well, some development teams use tools or conventions.

For example, Java developers sometimes use the object system .identity hash code, basically,

a unique -ish number associated with each lock object to decide the order in which to acquire multiple locks.

Using the hash code as the rank?

Yeah, as a way to impose an arbitrary but consistent order.

But even then, you have to be careful, especially with dynamic situations.

Think about transferring funds between two bank accounts.

Each account probably has its own mutex lock.

Right.

If your transfer function just naively locks the from account, then the to account, what happens if thread one transfers A to B and thread two transfers B to A at the same time?

Deadlock.

If thread one locks A and thread two locks B.

Exactly.

Unless the transfer function is smart enough to always lock the account with the, say, lower account number or lower hash code first, regardless of whether it's the from or to account, you need that consistent ordering within the operation.

So preventing circular weight is powerful, but needs careful design and discipline.

Okay, that covers prevention.

What about the other proactive strategy?

Deadlock avoidance.

Sounds a bit more predictive.

It is.

Avoidance is more dynamic than prevention.

It doesn't break one of the four conditions outright.

Instead, it uses advanced information about what resources threads might need in the future.

Like an oracle predicting resource needs.

Sort of.

The OS needs each thread to declare upfront the maximum number of each resource type it might ever possibly claim during its execution.

Maximum claim declaration.

Armed with this information, the operating system's goal is to make allocation decisions that always keep the system in a safe state.

A safe state.

What does that mean exactly?

A system is in a safe state if there exists some sequence called a safe sequence in which the system can allocate resources to each thread up to its declared maximum and allow it to run to completion without causing a deadlock.

Basically, a safe state means the OS can see at least one path forward where everyone eventually finishes, even in the worst case where everyone asks for their maximum resources.

So if the system is in a safe state, it's guaranteed not to be deadlocked currently and also guaranteed that it can avoid deadlock in the future.

Correct.

The crucial link is this.

A safe state is never a deadlock state.

However, an unsafe state is not necessarily a deadlocked state, but it might lead to one.

There's no guarantee of finishing from an unsafe state.

Okay, safe is good, unsafe is risky.

So the goal of avoidance is to never ever let the system enter an unsafe state.

Precisely.

Every time a thread requests a resource, the OS pretends to grant it, then checks if the resulting state would still be safe.

If yes, grant the request.

If no, the thread must wait, even if the resource is currently free, because granting it could lead to a future deadlock.

Wow.

That sounds like it involves some serious checking.

How does it work?

Well, for the simpler case, where each resource type only has a single instance, there's a variation of the resource allocation graph algorithm.

It adds a new kind of edge, maybe a dashed line, called a claim edge.

A claim edge?

Yeah, it points from a thread to a resource type it might request in the future, based on its maximum declaration.

When the thread actually requests it, the claim edge becomes a request edge, solid line.

When granted, it becomes an assignment edge.

The avoidance rule is,

only grant a request if converting the request edge to an assignment edge does not create a cycle in the graph, including potential cycles involving claim edges, creating a cycle with signal in unsafe state.

Okay, graph checking for single instances.

But what about the much more common case with multiple instances of resources?

Ah, for that we have the famous or perhaps infamous banker's algorithm.

The banker's algorithm.

Sounds important.

It is, conceptually.

It's named after the analogy of a banker who has a limited amount of cash, resources,

and several customers, threads,

who have each been granted a certain maximum credit line, maximum resource claim.

The banker needs to make loans,

allocate resources, in a way that ensures they can always satisfy the potential future requests of all customers up to their credit limit without running out of cash and causing a bank run deadlock.

Okay, the analogy helps.

How does the algorithm actually work?

What does the OS track?

It needs to maintain several pieces of data.

It knows the total number of instances of each resource type available.

For each thread, it knows the maximum number of instances it might ever request, max, and how many it currently holds, allocation.

Available max, allocation.

What else?

For max and allocation, it can calculate the need for each thread that's just max minus allocation.

This represents the remaining resources the thread might still request to complete its task.

Okay, available max, allocation need, got the data structures, now what?

There are two main parts.

First, there's the safety algorithm.

This checks if the current system state is safe.

How does it check for safety?

Okay, imagine you have the current available resources and the need of every thread.

The algorithm simulates trying to find a sequence of threads that can finish.

It looks for a thread whose need is less than or equal to the current available resources.

If it finds one, it pretends that thread runs to completion, releases all its allocated resources and adds them back to the available pool.

Then it looks for another thread that can run with the new available total and repeats.

Keep finding threads that can finish with what's available and adding their resources back.

Exactly.

If the algorithm can find a sequence where all threads eventually finish, the initial state was safe.

If you get stuck and can't find any more threads that can run, the state was unsafe.

Okay, that's the safety check.

What's the second part of the bankers algorithm?

The second part is the resource request algorithm.

This runs whenever a thread actually requests more resources.

What does it do?

First, it checks if the request is even valid.

Is it less than the thread's declared need?

And is it less than what's currently available?

If not, it's an error or the thread waits.

Basic sanity checks.

Right.

If the request is valid, the system pretends to grant it.

It tentatively updates the available allocation and need values as if the request happened.

It plays what if.

Exactly.

Right.

Then it runs the safety algorithm on this hypothetical new state.

Ah, it checks if granting the request would leave the system in a safe state.

Precisely.

If the safety algorithm says the hypothetical state is safe, then the system actually grants the resource request.

If the safety algorithm says the hypothetical state would be unsafe, the request is denied for now and the thread must wait, even though the resources might have been technically available.

The system state is rolled back to before the what if.

So it only grants requests that are guaranteed to maintain safety.

That sounds incredibly robust.

It is robust.

It guarantees deadlock avoidance.

But as you can imagine, running that safety algorithm check, which might involve iterating through all threads multiple times every time a resource is requested, well that's a lot of overhead.

Yeah.

Sounds computationally expensive.

Is it used much in practice?

Because of the overhead and the need for threads to declare their maximum resource needs upfront, which isn't always easy or known,

the full bankers algorithm isn't commonly used in general purpose operating systems like Windows or Linux or Mac OS.

It's more likely found in specialized high reliability systems where the cost of a deadlock is absolutely unacceptable.

That makes sense.

It's a powerful tool, but maybe too heavy for everyday use.

But you mentioned Linux has something practical called LockDep.

How does that relate?

LockDep is fascinating.

It's not strictly prevention or avoidance in the runtime sense, but it's a powerful development tool within the Linux kernel to help developers write deadlock free code.

So it helps catch problems before the code ships.

Exactly.

Kernel developers are supposed to follow locking order rules to prevent circular waits.

LockDep runs in development or debug kernels and acts like a watchdog.

It monitors every lock acquisition and release.

It builds up knowledge about the relationships between different locks, which lock is typically taken before which other lock.

It learns the locking hierarchy.

Sort of, yeah.

And if it detects an inconsistency,

like if lock A is usually taken before lock B, but then somewhere else in the code, lock B is taken before lock A, it flags it immediately as a possible deadlock condition.

Wow.

So it finds potential circular waits based on usage patterns.

Yes.

It also checks for other dangerous scenarios, like trying to acquire a regular spin lock while already holding one that disables interrupts, which could lead to deadlock if an interrupt needed that second lock.

It's very clever.

So it doesn't stop deadlocks on a running production system, but it helps eliminate them during development.

Precisely.

And the impact has been huge.

The creators reported that within a few years of its introduction, the number of deadlock bugs reported in the Linux kernel dropped dramatically, maybe by an order of magnitude.

It shows how good tooling can really help manage this complexity.

That's incredibly effective.

Okay, so we've covered prevention and avoidance.

What about the third approach?

Just let deadlocks happen, but then detect them and recover.

Right.

The reactive approach.

If you're not actively preventing or avoiding, you need a way to notice when you're stuck and a way to get unstuck.

So first step, detection.

How do you detect a deadlock after it's formed?

Again, it depends on whether resources have single or multiple instances.

For the simpler case of single instance resources, we can use a wait for graph.

A wait for graph.

How is that different from the resource allocation graph?

It's actually derived from it.

You basically simplify the resource allocation graph by removing the resource nodes, the rectangles, and just drawing arrows directly between the threads, the circles.

If thread T is waiting for a resource currently held by thread TJ, you draw a directed edge from T to TJ in the wait for graph.

So it just shows threads waiting directly on other threads.

Exactly.

It captures the who is waiting for whom dependencies.

And in the wait for graph, the rule is simple.

A cycle indicates a deadlock and a deadlock implies a cycle.

It's a direct one -to -one correspondence.

Cycle equals deadlock.

Nice and clear.

Are there tools that can do this?

Yes.

Modern tracing toolkits like BCC on Linux or even just getting a thread dump from a Java application can often be used to construct these wait for graphs for running processes and pinpoint cycles if they exist.

They give you a snapshot of who's blocked on what lock.

Very useful for debugging.

Okay.

And what about the more complex case?

Multiple instances per resource type.

A cycle in the resource allocation graph wasn't enough there.

How do you detect deadlocks then?

For multiple instances, we need a detection algorithm that's quite similar in structure to the banker safety algorithm, actually.

Similar to the bankers.

How so?

It also uses the available allocation vectors.

But instead of need, maximum potential request, it uses the request matrix, which shows the resources each thread is currently waiting for.

The algorithm essentially tries to simulate, again if threads can finish,

it looks for a thread whose current request is less than or equal to the available resources.

Find someone who can get what they're asking for right now.

Right.

If it finds such a thread, it assumes that thread could eventually finish, so it pretends the thread releases all its allocation and adds them back to available.

It marks that thread as finished, even though it's just hypothetical.

It keeps doing this, finding threads whose requests can be met by the available pool, adding the resources back.

Okay.

Sounds like the safety check.

What's the detection part?

The detection comes to the end.

After the algorithm runs, if there are any threads that are not marked as finished.

They couldn't find a way for those threads to get their currently requested resources.

Then those unmarked threads are deadlocked.

The algorithm couldn't find a sequence for them to complete, given the current state of request and allocations.

They are part of the deadlock.

So it identifies the specific threads that are stuck in the deadlock.

Exactly.

It tells you who is actually deadlocked right now.

When would you typically run this detection algorithm?

It sounds like it might still have some overhead.

Yeah, it does.

So you have to decide how often to invoke it.

The answer depends on a couple of things.

How often do you expect deadlocks to occur?

And how many threads are likely to be affected when one does happen?

Risk versus cost, again.

Pretty much.

If deadlocks are likely and could block many threads, you might run the detection algorithm quite frequently.

Maybe even every time a thread makes a request that can't be immediately satisfied that way, you could identify exactly which thread's request triggered the deadlocked state.

But that's expensive.

What's the alternative?

A less costly approach is to run it periodically, say once an hour or maybe trigger it if the overall system CPU utilization drops below a certain threshold.

Ah, because deadlock threads aren't using the CPU, so low utilization might signal a problem.

That's a common heuristic, yes.

If this system suddenly becomes idle when there's work waiting, a deadlock might be the reason.

Clever.

And database systems must be experts at this, right?

They deal with locks and transactions constantly.

Absolutely.

Transactional databases like MySQL or Postgresql are prime examples of systems that often use deadlock detection and recovery.

When multiple transactions run concurrently, they acquire locks on rows or tables.

It's very easy to get into deadlock situations like the ABBA transfer.

So what do they do?

The database server typically runs a deadlock detection algorithm periodically, maybe every few seconds or even more frequently.

It looks for cycles in the WaitFor graph among the active transactions.

If it finds a deadlock cycle, it has a policy to select one transaction as the victim.

The victim transaction.

Yes.

It then aborts that victim transaction, forcing it to roll back all its changes.

Rolling back automatically releases all the locks held by that transaction.

Which breaks the deadlock cycle.

Exactly.

The other transactions in the cycle can now proceed.

The database might then automatically restart the aborted victim transaction later.

And how does it choose the victim?

Randomly.

Usually, not randomly.

It tries to minimize the cost.

The victim might be the transaction that started most recently, or the one that has done the least amount of work, or the one holding the fewest locks, or maybe the one with the lowest priority.

The goal is to undo the minimum necessary work.

Makes sense.

Okay, so that brings us to the final step.

Recovery.

Once you've detected a deadlock, how do you actually break it?

Database rollback is one way.

What are the general options?

Broadly, there are two main recovery methods.

The first, as we saw with databases, involves process or thread termination.

Just kill the participants.

Pretty much.

The simplest, most brutal way is to just abort all the processes or threads involved in the deadlock cycle.

That definitely breaks a deadlock, but sounds like you lose a lot of work.

You do.

It's effective, but costly in terms of lost computation.

A slightly more refined approach is to abort one process at a time, rerunning the deadlock detection algorithm after each abortion until the cycle is broken.

Less work lost, maybe, but more overhead and repeatedly detecting.

Correct.

And aborting processes isn't always clean.

If a process was in the middle of updating a file or some shared state, just killing it could leave things inconsistent.

Right.

So if you do terminate, how do you choose which ones to kill?

Similar to the database victim selection.

Not exactly the same factors come into play.

You need a policy based on minimizing cost, you might consider.

Process priority.

How long has it run?

How close is it to finishing?

What kinds of resources does it hold?

How many resources does it need?

How many other processes would need to be terminated if this one isn't?

It's a complex decision.

Definitely.

Okay, termination is one recovery option.

What's the other?

The other main approach is resource preemption.

Instead of killing threads, you forcibly take resources away from some threads in the cycle and give them to others until the deadlock is broken.

Snatching the resources back like we discussed for prevention, but doing it after a deadlock is detected.

Right.

Again, you need to select a victim, which resource from which thread to preempt.

The cost factors are similar to victim selection for termination.

And what happens to the thread you preempted from?

You can't just take its resource and let it continue, right?

No, you absolutely can't, usually.

If you preempt a resource, you need to roll back the victim thread to some earlier safe state before it had acquired that resource.

Then you can restart it from that safe state later.

Rollback.

How far back do you go?

That's the tricky part.

The simplest is total rollback, basically abort the thread and restart it entirely.

Very costly.

More sophisticated systems might try to implement partial rollback using checkpoints or logs to only undo work back to the point just before the preempted resource was acquired.

But that adds a lot of complexity.

Wow.

Yeah.

Preemption and rollback sound complicated.

And there's that starvation issue again, isn't there?

Crucial point, yes.

Whether you're terminating victims or preempting from victims, if your selection policy always picks the cheapest victim based on simple metrics, the same process might get unlucky over and over again.

It could be constantly terminated or rolled back and never make any real progress.

That's starvation.

How do you prevent that poor process from always being the victim?

You have to ensure that a process can only be selected as a victim a finite number of times.

A common technique is to include the number of times a process has already been rolled back or terminated as part of its cost calculation.

The more times it's been victimized, the higher its cost becomes, making it less likely to be chosen again.

So eventually even the unluckiest process gets a chance to run.

That's the idea.

You have to factor fairness into the recovery policy.

Wow.

We've covered a huge amount today.

We went from those those comical Kansas trains all the way to complex algorithm like the bankers algorithm, practical tools like Lindos's LockDev, and the tricky details of detection and recovery.

It's really clear that deadlocks are a persistent and, well, surprisingly deep challenge in operating systems.

They really are.

And we saw the main strategies, prevention by breaking one of the four conditions, avoidance by staying in a safe state using predictions, and detection recovery after the fact.

Each involves significant tradeoffs.

Yeah, tradeoffs between correctness, performance, and complexity.

And it really highlights that there's rarely one single best solution.

The right approach depends heavily on the specific system, the types of resources, how critical avoiding deadlocks is versus raw performance.

So what does this all mean for you, the listener?

Well, maybe next time your favorite app freezes up solid or some big online system feels sluggish.

Just maybe.

Take a moment to consider that invisible dance of resources happening behind the screen.

Think about the intricate ballets operating systems are performing to keep everything moving smoothly.

Or perhaps the silent deadlocks they might be struggling to navigate or recover from.

It makes you wonder what other hidden complexities are shaping the tech we rely on every single day.

It's a whole hidden world under the surface.

It really is.

Thank you so much for joining us on this deep dive into the fascinating and sometimes frustrating world of deadlocks.

It's been a great exploration into the heart of operating systems.

Absolutely.

It's truly remarkable how these fundamental, often invisible mechanisms are so critical for the stability and performance of pretty much our entire digital world.

Thanks for diving in with us.