Synchronization and Mutual Exclusion

Synchronization and Mutual Exclusion

Basic Concepts

The Critical Section Problem

Critical section: the segment of code that accesses shared resources; only one process may execute it at a time.

Characteristics of a critical section:

1. Mutual exclusion: only one process may be inside the critical section at a time
2. Bounded waiting: the time a process waits to enter the critical section is finite
3. Progress: when no process is in the critical section, a process that requests entry must be able to enter

Structure of a critical section:

do {
    entry_section();    // entry section
    critical_section(); // critical section
    exit_section();     // exit section
    remainder_section(); // remainder section
} while (true);

Mutual Exclusion and Synchronization

Mutual exclusion: several processes must not access a shared resource at the same time.

Synchronization: several processes execute in a given order so that operations stay correct.

The difference:

• Mutual exclusion is about “not at the same time”
• Synchronization is about “executing in order”

Software Approaches

1. Single Flag

Algorithm:

• Keep a single flag variable turn
• Only the process that turn points at may enter the critical section

Implementation:

int turn = 0; // initialized to process 0

// Process 0
while (turn != 0); // wait
critical_section();
turn = 1;

// Process 1
while (turn != 1); // wait
critical_section();
turn = 0;

Problem: entry is forced to alternate, which violates the “progress” requirement.

2. Double Flag

Algorithm:

• Each process keeps its own flag
• Before entering the critical section, a process checks the flag of the other process

Implementation:

bool flag[2] = {false, false};

// Process i
flag[i] = true;
while (flag[j]); // wait for the other process
critical_section();
flag[i] = false;

Problem: two processes may enter the critical section at the same time, which violates “mutual exclusion”.

3. Improved Double Flag

Algorithm:

• Raise your own flag first, then check the other process’s flag
• On a conflict, clear your own flag and try again

Implementation:

bool flag[2] = {false, false};

// Process i
flag[i] = true;
while (flag[j]) {
    flag[i] = false;
    delay();
    flag[i] = true;
}
critical_section();
flag[i] = false;

Problem: a process may wait forever, which violates the “bounded waiting” requirement.

4. Peterson’s Algorithm

Algorithm:

• Combines the turn flag with the flag flags
• Satisfies all three requirements of the critical section problem

Implementation:

bool flag[2] = {false, false};
int turn = 0;

// Process i
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical_section();
flag[i] = false;

Characteristics:

• Satisfies mutual exclusion, bounded waiting, and progress
• Written for two processes
• Can be extended to more processes

Hardware Approaches

1. Disabling Interrupts

Principle: disable interrupts before entering the critical section and restore them on exit.

Implementation:

// Enter the critical section
disable_interrupts();
critical_section();
// Leave the critical section
enable_interrupts();

Characteristics:

• Simple and effective
• Works only on a single processor
• Hurts the responsiveness of the system

2. The Test-and-Set Instruction

Principle: atomically test and set the value of a memory location.

Implementation:

bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

bool lock = false;

// Process
while (TestAndSet(&lock));
critical_section();
lock = false;

Characteristics:

• Supported by hardware, therefore efficient
• Works on multiprocessors
• May busy-wait

3. The Compare-and-Swap Instruction

Principle: atomically compare and swap the value of a memory location.

Implementation:

int CompareAndSwap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

int lock = 0;

// Process
while (CompareAndSwap(&lock, 0, 1) != 0);
critical_section();
lock = 0;

Characteristics:

• Supported by hardware, therefore efficient
• Works on multiprocessors
• More flexible than Test-and-Set

Semaphores

Basic Concepts

Semaphore: an integer variable that, apart from initialization, may only be accessed through two atomic operations:

• P operation (wait): request a resource
• V operation (signal): release a resource

Types of semaphore:

1. Binary semaphore: the value is 0 or 1; used for mutual exclusion
2. Counting semaphore: the value may be any non-negative integer; used for synchronization

Semaphore Implementation

Structure definition:

typedef struct {
    int value;
    struct process *list;
} semaphore;

Implementation of the P operation:

void P(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add_process_to_list(S->list);
        block();
    }
}

Implementation of the V operation:

void V(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove_process_from_list(S->list);
        wakeup();
    }
}

Applications of Semaphores

1. Mutual exclusion:

semaphore mutex = 1;

// Process
P(&mutex);
critical_section();
V(&mutex);

2. Synchronization:

semaphore sync = 0;

// Process A
statement_a();
V(&sync);

// Process B
P(&sync);
statement_b();

3. Resource management:

semaphore resource = N; // N resources

// Process
P(&resource);
use_resource();
V(&resource);

Monitors

Basic Concepts

Monitor: a high-level synchronization mechanism that encapsulates shared variables together with the operations on them in one module.

Characteristics of a monitor:

1. Encapsulation: shared variables can only be accessed through the procedures inside the monitor
2. Mutual exclusion: only one process may execute inside a monitor at a time
3. Condition variables: used to synchronize processes with one another

Structure of a Monitor

monitor MonitorName {
    // shared variable declarations
    shared variables;

    // condition variables
    condition x, y;

    // procedure definitions
    procedure P1() {
        // procedure body
    };

    procedure P2() {
        // procedure body
    };

    // initialization code
    {
        // initialization code
    }
}

Condition Variables

Operations:

• wait(c): the process waits on condition variable c
• signal(c): a process waiting on condition variable c is woken up

Implementation:

typedef struct {
    int value;
    struct process *list;
} condition;

void wait(condition *c) {
    c->value++;
    block();
}

void signal(condition *c) {
    if (c->value > 0) {
        c->value--;
        wakeup();
    }
}

Classical Synchronization Problems

1. The Producer-Consumer Problem

Problem:

• Producer processes produce data and put it into a buffer
• Consumer processes take data out of the buffer
• The buffer is finite, so the two sides must be synchronized

Solution:

#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

// Producer
void producer() {
    while (true) {
        item = produce_item();
        P(&empty);
        P(&mutex);
        insert_item(item);
        V(&mutex);
        V(&full);
    }
}

// Consumer
void consumer() {
    while (true) {
        P(&full);
        P(&mutex);
        item = remove_item();
        V(&mutex);
        V(&empty);
        consume_item(item);
    }
}

2. The Readers-Writers Problem

Problem:

• Several readers may read the shared data at the same time
• A writer must have exclusive access
• Readers and writers may not access the data at the same time

Reader-preference solution:

semaphore mutex = 1;
semaphore wrt = 1;
int readcount = 0;

// Reader
void reader() {
    P(&mutex);
    readcount++;
    if (readcount == 1)
        P(&wrt);
    V(&mutex);

    read_data();

    P(&mutex);
    readcount--;
    if (readcount == 0)
        V(&wrt);
    V(&mutex);
}

// Writer
void writer() {
    P(&wrt);
    write_data();
    V(&wrt);
}

3. The Dining Philosophers Problem

Problem:

• 5 philosophers sit around a round table
• Each philosopher needs two chopsticks to eat
• The chopsticks lie between the philosophers

Solution:

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;

void philosopher(int i) {
    while (true) {
        think();

        P(&mutex);
        P(&chopstick[i]);
        P(&chopstick[(i+1)%5]);
        V(&mutex);

        eat();

        V(&chopstick[i]);
        V(&chopstick[(i+1)%5]);
    }
}

The Deadlock Problem

Definition of Deadlock

Deadlock: a situation in which several processes wait for one another because they compete for resources.

Deadlock Conditions

The four necessary conditions:

1. Mutual exclusion: a resource cannot be used by several processes at the same time
2. Hold and wait: a process does not release the resources it holds while waiting for other resources
3. No preemption: a resource cannot be forcibly taken away
4. Circular wait: a chain of waiting processes forms a cycle

Deadlock Prevention

Breaking mutual exclusion:

• Use shareable resources
• Use virtualization

Breaking hold and wait:

• Allocate all resources at once
• Use a resource pre-allocation policy

Breaking no preemption:

• Allow resources to be preempted
• Assign priorities to resources

Breaking circular wait:

• Allocate resources in a fixed order
• Use a resource numbering scheme

Deadlock Avoidance

The Banker’s algorithm:

• Check whether an allocation is safe before granting it
• Grant resources only in a safe state

Safety check:

bool is_safe_state() {
    int work[RESOURCES];
    bool finish[PROCESSES];

    // initialization
    for (int i = 0; i < RESOURCES; i++)
        work[i] = available[i];
    for (int i = 0; i < PROCESSES; i++)
        finish[i] = false;

    // look for a process that can finish
    for (int count = 0; count < PROCESSES; count++) {
        bool found = false;
        for (int i = 0; i < PROCESSES; i++) {
            if (!finish[i] && can_allocate(i, work)) {
                for (int j = 0; j < RESOURCES; j++)
                    work[j] += allocation[i][j];
                finish[i] = true;
                found = true;
            }
        }
        if (!found) return false;
    }
    return true;
}

Deadlock Detection

Resource allocation graph:

• Nodes represent processes and resources
• Edges represent allocation and request relationships
• Look for a cycle in the graph

Detection algorithm:

bool detect_deadlock() {
    // simplify the resource allocation graph
    while (a_simplifiable_node_exists()) {
        simplify_that_node();
    }

    // check whether any edges remain
    if (graph_has_remaining_edges())
        return true; // a deadlock exists
    else
        return false; // no deadlock exists
}

Deadlock Recovery

Process termination:

• Terminate all deadlocked processes
• Terminate deadlocked processes one at a time

Resource preemption:

• Choose a victim process
• Roll back to a safe state
• Reallocate the resources

---

Glossary