Hugo's Cyber Heritage

Shine or Die

OS-06 Process Synchronization

Posted on Edited on In
Symbols count in article: 10k Reading time ≈ 9 mins.

This post introduces the process synchronization problem in operating systems.

Background: Critical-Section Problem

When multiple processes execute concurrently, each of them has a segment of code (the critical section) that accesses and modifies shared resources. Without a synchronization mechanism, multiple processes may enter their critical sections at the same time and operate on the shared resources, leading to data inconsistency and race conditions.

Requirements for a solution:

  • Mutual exclusion
  • Progress: If no process is executing in its critical section and there exist processes waiting to enter, the selection of entering processes cannot be postponed indefinitely
  • Bounded waiting

Synchronization Mechanisms

Peterson’s Solution

Assume that load and store instructions are atomic and cannot be interrupted. The two processes share two variables: int turn indicates whose turn it is to enter the critical section, and the array boolean flag[2] indicates whether a process is ready to enter its critical section; flag[i] = true means process is ready to enter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int turn; // which process's turn it is to enter the critical section
boolean flag[2]; // whether each process is ready to enter the critical section

void P0() 
{
    flag[0] = true; // process P0 is ready to enter the critical section
    turn = 1; // it is process P1's turn to enter the critical section
    while (flag[1] && turn == 1); // if process P1 is ready to enter the critical section and it is P1's turn, process P0 waits
    critical section // process P0 enters the critical section
    flag[0] = false; // process P0 exits the critical section
}

void P1() 
{
    flag[1] = true; // process P1 is ready to enter the critical section
    turn = 0; // it is process P0's turn to enter the critical section
    while (flag[0] && turn == 0); // if process P0 is ready to enter the critical section and it is P0's turn, process P1 waits
    critical section // process P1 enters the critical section
    flag[1] = false; // process P1 exits the critical section
}

Limitation:

To improve performance, modern processors and/or compilers may reorder read and write operations that have no dependencies.

When instruction reordering happens, instructions that were meant to execute sequentially may have their execution order changed, causing both processes to enter their critical sections at the same time.

Hardware Support for Synchronization

Memory barriers

A memory barrier is an instruction that forces any change in memory to be propagated (visible) to all other processors.

When a memory barrier instruction is executed, within the same process it ensures that all preceding load and store operations complete before any subsequent load / store operations are performed. Even if the processor or compiler reorders instructions, the memory barrier guarantees that the store operations are completed in memory and are visible to other processors before any future load / store operations.

Hardware Instructions

Atomic variable: the execution of one or more instructions is indivisible, either all of it executes or none of it does.

Limitation: unbounded waiting, the order in which competing processes acquire the resource is random.

Test-and-Set instruction
1
2
3
4
5
6
bool TestAndSet(bool *target)
{
    bool rv = *target;
    *target = true;
    return rv;
}

Example:

1
2
3
4
5
6
7
8
bool lock = false;

void P0() 
{
    while (TestAndSet(&lock)); // if lock is true, wait
    critical section // process P0 enters the critical section
    lock = false; // process P0 exits the critical section
}

From the perspective of other concurrently executing threads or processes, it completes instantaneously: either it executes in full or it does not execute at all.

Compare-and-Swap instruction
1
2
3
4
5
6
7
int compare_and_swap(int *value, int expected, int new_value)
{
    int temp = *value; 
    if (*value == expected) 
        *value = new_value; 
    return temp; 
}

bounded waiting version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (true) 
{
    /* entry section – acquire the lock */ 
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1) // use key to exit
    key = compare_and_swap(&lock, 0, 1); 
    waiting[i] = false; 
    /* critical section – release one process */ 
    j = (i + 1) % n; 
    while ((j != i) && !waiting[j]) 
    j = (j + 1) % n; 
    if (j == i) 
    lock = 0; 
    else 
    waiting[j] = false; 
    /* remainder section */
}

Atomic Variables

1
2
3
4
5
6
7
void increment(atomic_int *v)
{
    int temp;
    do {
        temp = *v;
    } while (temp != (compare_and_swap(v,temp,temp+1)));
}

Mutex Locks and Semaphores

Mutex Locks

The mutex lock is the simplest synchronization tool. A process must acquire the lock before entering its critical section and must release the lock when it leaves. A mutex lock contains a boolean variable available that indicates whether the lock is available:

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct 
{
    bool available;
} mutex;

void acquire(mutex *m) {
    while (!m->available); // spin (busy) waiting
    m->available = false;  // acquire the lock
}

void release(mutex *m) {
    m->available = true;   // release the lock
}

Usage example:

1
2
3
4
5
6
mutex lock;  // available is initially true
// ...
acquire(&lock);
critical section  // critical section
release(&lock);
remainder section

Main characteristics:

  1. Mutual exclusion: at any moment only one process can hold the lock
  2. Busy waiting: a process keeps occupying the CPU while waiting for the lock
  3. Suitable for:
    • Cases where the expected waiting time is short
    • Multiprocessor systems

Drawbacks:

  1. Busy waiting wastes CPU time
  2. Priority inversion may occur: when a low-priority process holds the lock, a high-priority process has to wait

Semaphores

A semaphore is a more powerful synchronization tool, proposed by Dijkstra. A semaphore S is an integer variable that, apart from initialization, can only be accessed through two atomic operations, wait (P) and signal (V):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef struct 
{
    int value;      // value of the semaphore
    struct process *list;  // waiting queue
} semaphore;

void wait(semaphore *S) 
{  // P operation
    S->value--;
    if (S->value < 0) 
    {
        // add the current process to the waiting queue
        add_to_list(S->list);
        block();  // block the current process
    }
}

void signal(semaphore *S) 
{  // V operation
    S->value++;
    if (S->value <= 0 && S->list != NULL) 
    {
        // wake up one process from the waiting queue
        process *p = remove_from_list(S->list);
        wakeup(p);
    }
}

Types of semaphores:

  1. Binary Semaphore

    • The value can only be 0 or 1
    • Similar to a mutex lock, but implemented differently
    • Used for mutual exclusion and synchronization

  2. Counting Semaphore

    • The value can be any integer
    • Used for resource management
    • For example: controlling access to a finite set of resources

Usage example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Mutual exclusion example
semaphore mutex = 1;  // initialized to 11

wait(&mutex);
critical section
signal(&mutex);

// Producer-consumer problem example
semaphore empty = n;    // initialized to the buffer size
semaphore full = 0;     // initialized to 00
semaphore mutex = 1;    // for mutually exclusive access

// Producer
wait(&empty);          // wait for an empty slot
wait(&mutex);          // enter the critical section
    // add data to the buffer
signal(&mutex);        // leave the critical section
signal(&full);         // one more full slot

// Consumer
wait(&full);           // wait for a full slot
wait(&mutex);          // enter the critical section
    // remove data from the buffer
signal(&mutex);        // leave the critical section
signal(&empty);        // one more empty slot

Advantages of semaphores:

  1. No busy waiting; a blocked process consumes no CPU
  2. Can implement more complex synchronization
  3. Applicable to many synchronization scenarios

Disadvantages of semaphores:

  1. Misuse easily leads to deadlock
  2. Correctness is hard to guarantee
  3. Easy to make programming mistakes (wrong order of wait/signal)

Monitors

Abstraction: encapsulate the shared data together with the procedures that operate on it, providing a mechanism that ensures only one process can access the shared data at any given time.

1
2
3
4
5
6
7
8
9
10
11
monitor monitor_name {
    // shared variable declarations
    
    // monitor initialization code
    
    // procedures that operate on the shared variables
    procedure P1(...) { ... }
    procedure P2(...) { ... }
    ...
    procedure Pn(...) { ... }
}

1

Synchronization Problem Formulations

Bounded-Buffer Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
monitor BoundedBuffer 
{
    int buffer[N];       // buffer
    int count = 0;       // number of items in the buffer
    int in = 0, out = 0; // positions for inserting and removing
    
    condition not_full;  // condition: buffer not full
    condition not_empty; // condition: buffer not empty
    
    procedure deposit(item) 
    {
        if (count == N)
            wait(not_full);    // if the buffer is full, wait
            
        buffer[in] = item;     // insert the item
        in = (in + 1) % N;     // update the position
        count++;               // increment the count
        
        signal(not_empty);     // wake up a waiting consumer
    }
    
    procedure remove() 
    {
        if (count == 0)
            wait(not_empty);   // if the buffer is empty, wait
            
        item = buffer[out];    // remove the item
        out = (out + 1) % N;   // update the position
        count--;               // decrement the count
        
        signal(not_full);      // wake up a waiting producer
        return item;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BoundedBuffer bb;   // create a monitor instance

// Producer process
void producer() 
{
    while (true) 
    {
        item = produce_item();
        bb.deposit(item);
    }
}

// Consumer process
void consumer() 
{
    while (true) 
    {
        item = bb.remove();
        consume_item(item);
    }
}

Readers-Writers Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
monitor ReaderWriter 
{
    int readers = 0;     // current number of readers
    boolean writing = false; // whether someone is writing
    
    condition read;      // condition readers wait on
    condition write;     // condition writers wait on
    
    procedure startRead() 
    {
        if (writing || !write.empty())
            wait(read);    // if someone is writing or a writer is waiting, the reader waits
            
        readers++;       // increment the number of readers
        signal(read);    // allow the next reader to enter
    }
    
    procedure endRead() 
    {
        readers--;       // decrement the number of readers
        
        if (readers == 0)
            signal(write);  // if no readers remain, wake up a writer
    }
    
    procedure startWrite() 
    {
        if (readers > 0 || writing)
            wait(write);   // if someone is reading or writing, the writer waits
            
        writing = true;    // mark that someone is writing
    }
    
    procedure endWrite() 
    {
        writing = false;   // mark that no one is writing
        
        if (!read.empty())
            signal(read);   // wake up readers first
        else
            signal(write);  // otherwise wake up a writer
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ReaderWriter rw;   // create a monitor instance

// Reader process
void reader() 
{
    while (true) 
    {
        rw.startRead();
        // read the shared resource
        rw.endRead();
    }
}

// Writer process
void writer() 
{
    while (true) 
    {
        rw.startWrite();
        // modify the shared resource
        rw.endWrite();
    }
}

Dining-Philosophers Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
monitor DiningPhilosophers 
{
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    
    procedure initialize() 
    {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
    
    procedure test(int i) {
        if (state[i] == HUNGRY && state[(i+4) % 5] != EATING && state[(i+1) % 5] != EATING) 
        {
            state[i] = EATING;
            signal(self[i]);
        }
    }
    
    procedure pickup(int i) 
    {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            wait(self[i]);
    }
    
    procedure putdown(int i) 
    {
        state[i] = THINKING;
        // try to let the left and right neighbors eat
        test((i+4) % 5);
        test((i+1) % 5);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
DiningPhilosophers dp;   // create a monitor instance

// Philosopher process
void philosopher(int i) 
{
    while (true) 
    {
        think();        // think
        dp.pickup(i);   // pick up chopsticks
        eat();          // eat
        dp.putdown(i);  // put down chopsticks
    }
}

Translated from the Chinese original.

Welcome to my other publishing channels

中文