Deadlocks

Introduction

In this previous example, we could at most buffer a single item.

TODO

Adding a counter variable, we could track open memory spaces, allowing us to buffer more shared memory.

TODO

Without synchronization, we could get a race condition.

Imagine, for example, that a processes time slice expires before it finishes updating counter.

Example: Race condition

Suppose this producer-consumer pair interleaves execution without synchronization.

producer executes: register1 = counter
producer executes: register1 += 1

// Context Switch (producer -> consumer)

consumer executes: register2 = counter
consumer executes: register2 -= 1

// Context Switch (consumer -> producer)

producer executes: counter = register1

// Context Switch (producer -> consumer)

consumer executes: counter = register1

This race condition arose because we split the critical section.

Some ways to solve this:

1. Sequential Execution

TODO

2. Interleaved Execution

TODO

Critical Section Problem

Consider system of n processes.

Critical Section: Segment of code that may be changing common variables, updating tables, writing files, etc.

When one process is in its critical section, no other may be in its critical section.

Critical Section Problem: Design a protocol to solve this problem.

Each process must ask for permission to enter their critical section.

Three Parts of a Critical Section: TODO

Entry Section
Exit Section
Execution Section

Two Approaches:

Preemptive: Allows preemption of process when running in kernel mode.
Non-Preemptive: Run until kernel exits TODO

Example: Incorrect interleaving of code

Processes p and q execute the instructions x = x + 1 and x = x + 2, respectively. Initially, x = 0

Q: What is the value of x after execution?

p: q:
load Rp, x
        load Rq, x
add Rp, 1
        add Rq, 2
        store Rq, x
store Rq, x

p: q:
        load Rq, x
load Rp, x
add Rp, 1
        add Rq, 2
store Rq, x
        store Rq, x

p: q:
load Rp, x
add Rp, 1
        load Rq, x
        add Rq, 2
        store Rq, x
store Rq, x

If you don’t synchronize, the outcome is entirely dependent on how the CPU jumps between processes.

Solutions to Critical Section Problem

Solutions must satisfy the following:

1. Guarantee Mutual Exclusion: Only one process can be executing its critical section.

2. Prevent Lockout: Processes not attempting to enter CS mustn’t prevent other processes from entering the CS.

3. Prevent Starvation: We can’t let the same process do its CS over-and-over and starve waiting ones.

4. Prevent Deadlock: Multiple processes trying to enter their CS at the same time mustn’t block each other indefinitely.

Example: Deadlock

Suppose p and q use two keys.

p q
key1 key2
key2 key1

In this state, p and q could end up waiting forever for the other to give up their key, resulting in deadlock.

Mutex Locks

A software solution to the critical selection problem.

do {
    acquire lock
        critical section
    release lock
        remainder section
} while (TRUE);

Protect a critical section by first acquiring a lock, and then releasing the lock.

Boolean variable indicates if lock is available.
acquire() and release() must be atomic calls (usually done via hardware atomic instructions)

Atomic Call: The CPU cannot stop execution during an atomic call.

Spinlock: This lock requires busy waiting (while (!available);), so it’s also called a spinlock.

Example: acquire and release

acquire() {
  while (!available); // (busy wait)
  available = true;
}
release() {
  available = false;
}