Introduction

Recall — Processes may be independent or cooperating; and the scheduler may interrupt mid-execution.

• Thus, maintaining data consistency amongst cooperating processes sharing data requires special mechanisms.

We introduced the producer-consumer problem back in the process management chapter, and provided a simple solution:

Producer:

item next_produced;

while(true) {
    // produce an item in next_produced
    while (((in + 1) % BUFFER_SIZE == out)
        ; // do nothing
    
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
}

Consumer:

item next_consumed;

while (true) {
    while (in == out)
        ; // do nothing
    
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE

    // consume the item in next_consumed
}

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

Producer:

item next_produced;

while(true) {
    // produce an item in next_produced
    while (counter === BUFFER_SIZE == out) ;
        // do nothing
    
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

Consumer:

item next_consumed;

while (true) {
    while (counter == 0)
        ; // do nothing
    
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE
    counter--;

    // consume the item in next_consumed
}

Without synchronization, we could get a race condition.

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

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

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

1. Entry Section
2. Exit Section
3. 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

A:

1. x=1
2. x=2
3. x=1

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.

p q
key1 key2
key2 key1

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.

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