Critical Section Problem

Each process contains a critical section. From all the threads sharing some resource, only 1 thread must be allowed to run its critical section at a given point of time. If not achieved, data corruption and race conditions are possible.

Whenever critical sections are discussed, only the threads sharing a single shared resource are referred.

Requirements

Any correct solution must satisfy:

• Mutual Exclusion
• Progress
  When no thread is in its critical section and some threads want to enter, a waiting process must be selected without indefinite delay.
• Bounded Waiting
  After a thread asks to enter its critical section, there must be an upperbound on the number of threads that enter their critical section. If not satisfied, might cause starvation.

Solutions

Interrupt-based

Hardware-level solution. Turning off interrupts in entry section and turning them back on in exit section. Prevents other threads from interrupting the current thread while in the critical section. Simple. Effective.

Only available at kernel level. Not reliable. If critical section runs for too long or interrupts are not turned on again, whole system will freeze. Not scalable for multiple CPUs. Starvation is possible.

• Mutual Exclusion: Satisfied*
  Not satisfied on multiprocessor or multicore systems. Interrupts are only turned off on the current CPU/core. Other CPUs/cores can still run other threads that may enter their critical sections.
• Progress: Satisfied*
  Not satisfied on multiprocessor or multicore systems.
• Bounded Waiting: Not satisfied.
  Depends on OS scheduler. A thread may be delayed indefinitely if higher-priority threads keep getting scheduled.

Strict Alternation

Software-only solution. Explained already in Mutual Exclusion.

• Mutual exclusion: Satisfied.
• Progress: Not satisfied.
• Bounded Waiting: Satisfied.
  $N-1$ is the upperbound on the number of threads that can enter their critical section after a thread requests to enter.

Peterson’s Algorithm

A software-level solution. Explained on Peterson’s Algorithm on its own page.

Hardware Instructions

Special atomic instructions used to implement locks, semaphores, etc.

test_and_set

Aka. TSL. A shared boolean variable lock. 0 means free, 1 means busy. Sets passed parameter to true and returns the old value.

Simple. Works on multiprocessors. Widely supported.

Causes busy-waiting, which wastes clock cycles while spinning. Starvation is possible. Performs unnecessary memory writes. Might cause high contention.

// Atomic hardware primitive
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;
}

• Mutual exclusion - Satisfied.
  test_and_set ensures only one thread sees old = false and enters the critical section. Everyone else spins.
• Progress - Not satisfied. If more than 1 threads keep calling test_and_set, the CPU may keep picking the same unlucky thread, making another thread starve forever.
• Bounded waiting - No satisfied. test_and_set gives no upper bound on how long a thread waits. A thread can be overtaken infinitely many times.

compare_and_swap

Aka. CAS. Atomic. A shared word addr. Compares it with expected, if so, updates addr with new. Returns whether the update was performed.

// Atomic hardware primitive
bool compare_and_swap(int *addr, int expected, int new) {
    if (*addr == expected) {
        *addr = new;      // write happens only on success
        return true;
    } else {
        return false;
    }
}

Only writes when it actually acquires the lock. More powerful and flexible compared to test_and_set. Only has mutual exclusion similar to test_and_set.

Can be used to implement spinlocks, mutexes, semaphores, lock-free stacks/queues.

Atomic variables

Using special instructions (such as the above ones), atomic variables can be implemented.

Example: increment() for an atomic_int can be implemented as follows:

void increment(atomic_int *v){
    int temp;
    do {
        temp = *v;
    }
    while (temp != (compare_and_swap(v,temp,temp+1));
}

Related Problems

Bounded Buffer Problem

Aka. Producer–Consumer Problem (with finite buffer).

Models 2 types of processes with a shared buffer of fixed size:

• producers - insert an item into the next free slot.
• consumers - take an item from the next filled slot.

The challenge is to ensure that:

• Producers do not add data when the buffer is full.
• Consumers do not remove data when the buffer is empty.
• No two producers overwrite data of one another.
• Only one process update the buffer at a time.

If not, race conditions will be possible. Synchronization solves the above challenges. How exactly, is explained in the next topics.