Chapter 6 · Final syllabus · Lectures 18–20

Synchronization Tools

Race conditions, the critical-section problem and its three requirements, interrupt-based and software solutions, Peterson’s solution, test_and_set and compare_and_swap, atomic variables, mutex locks, semaphores and monitors with condition variables.

Start All chapters

← → move between slides · F full screen · M slide list

Before we start

Why this matters

Two processes add one to the same counter. Sometimes the counter goes up by one, not two.

When cooperating processes share data, the order of their instructions matters — and preemption can interleave them at the worst moment.

This chapter defines what a correct solution must guarantee and builds the tools for it, from Peterson’s algorithm to semaphores and monitors.

Chapter 6 · Lectures 18–20

Outline

Select a topic to jump to the slide that explains it.

Background
The critical-section problem
Peterson’s solution
Hardware support for synchronization
Mutex locks
Semaphores
Monitors

Background

Processes can execute concurrently
- May be interrupted at any time, partially completing execution
Concurrent access to shared data may result in data inconsistency
Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes

Background

Race condition

Processes P0 and P1 are creating child processes using the fork() system call
Race condition on kernel variable next_available_pid which represents the next available process identifier (pid)
Unless there is a mechanism to prevent P0 and P1 from accessing the variable next_available_pid the same pid could be assigned to two different processes!

A race condition is when the outcome depends on the particular order in which the accesses take place. Try it on the next slide.

Interactive

Race on next_available_pid

Code and output

A real race condition

race.c — two threads, one counter

#include <pthread.h>
#include <stdio.h>

#define N 1000000
long counter = 0;                       /* shared data */
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int use_lock;

void *work(void *arg)
{
    for (int i = 0; i < N; i++) {
        if (use_lock) pthread_mutex_lock(&lock);    /* entry section */
        counter++;                                  /* critical section */

Code and output

A real race condition (cont.)

        if (use_lock) pthread_mutex_unlock(&lock);  /* exit section */
    }
    return NULL;
}

int main(void)
{
    for (use_lock = 0; use_lock <= 1; use_lock++) {
        pthread_t a, b;
        counter = 0;
        pthread_create(&a, NULL, work, NULL);
        pthread_create(&b, NULL, work, NULL);
        pthread_join(a, NULL);
        pthread_join(b, NULL);

Code and output

A real race condition (cont.)

        printf("%-12s counter = %ld (expected %d)\n",
               use_lock ? "with lock:" : "no lock:", counter, 2 * N);
    }
    return 0;
}

Output

Terminal

$ gcc race.c -o race -pthread && ./race
no lock:     counter = 1032343 (expected 2000000)
with lock:   counter = 2000000 (expected 2000000)

counter++ is three machine steps (load, add, store). Without the lock the threads overwrite each other’s updates, so the total is wrong and different on every run. With the mutex around the critical section it is always 2,000,000.

The critical-section problem

Critical section problem

Consider system of n processes {p₀, p₁, … p_n−1}
Each process has critical section segment of code
- Process may be changing common variables, updating table, writing file, etc.
- When one process in critical section, no other may be in its critical section
Critical section problem is to design protocol to solve this
Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section

General structure of process P_i:

while (true) {

    entry section

        critical section

    exit section

        remainder section
}

The critical-section problem

Critical-section problem (cont.)

Requirements for solution to critical-section problem:

Mutual exclusion – if process P_i is executing in its critical section, then no other processes can be executing in their critical sections
Progress – if no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the process that will enter the critical section next cannot be postponed indefinitely
Bounded waiting – a bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
- Assume that each process executes at a nonzero speed
- No assumption concerning relative speed of the n processes

The critical-section problem

Interrupt-based solution

Entry section: disable interrupts
Exit section: enable interrupts
Will this solve the problem?
- What if the critical section is code that runs for an hour?
- Can some processes starve – never enter their critical section.
- What if there are two CPUs?

Disabling interrupts only stops preemption on one CPU. On a multiprocessor, a process on another CPU can still enter the critical section, and turning interrupts off on every CPU is too slow.

Peterson’s solution

Software solution

Two process solution
Assume that the load and store machine-language instructions are atomic; that is, cannot be interrupted
The two processes share one variable:
- int turn;
The variable turn indicates whose turn it is to enter the critical section
initially, the value of turn is set to i

Algorithm for process P_i:

while (true) {
    while (turn == j);

Peterson’s solution

Software solution (cont.)

    /* critical section */

    turn = j;

    /* remainder section */
}

Correctness of the software solution

Mutual exclusion is preserved: P_i enters critical section only if turn = i, and turn cannot be both 0 and 1 at the same time
But progress fails: the processes must strictly alternate. If P_j stays in its remainder section, P_i cannot enter twice in a row.

Peterson’s solution

Two process solution
Assume that the load and store machine-language instructions are atomic; that is, cannot be interrupted
The two processes share two variables:
- int turn;
- boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section
The flag array is used to indicate if a process is ready to enter the critical section.
- flag[i] = true implies that process P_i is ready!

Algorithm for process P_i:

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ;

    /* critical section */

    flag[i] = false;

    /* remainder section */
}

Peterson’s solution

Correctness of Peterson’s solution

Provable that the three CS requirements are met:

Mutual exclusion is preserved: P_i enters CS only if either flag[j] = false or turn = i
Progress requirement is satisfied
Bounded-waiting requirement is met

If both processes want to enter, both set their flag; turn can only hold one value, the one written last, so exactly one of them waits. A process that is not interested has its flag false and never blocks the other.

Interactive