Hugo's Cyber Heritage

Shine or Die

OS-06 Process Synchronization

Posted on Edited on In
Symbols count in article: 8.8k Reading time ≈ 8 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; // 轮到哪个进程进入临界区
boolean flag[2]; // 进程是否准备好进入临界区

void P0() 
{
    flag[0] = true; // 进程P0准备进入临界区
    turn = 1; // 轮到进程P1进入临界区
    while (flag[1] && turn == 1); // 如果进程P1准备好进入临界区且轮到进程P1进入临界区，则进程P0等待
    critical section // 进程P0进入临界区
    flag[0] = false; // 进程P0退出临界区
}

void P1() 
{
    flag[1] = true; // 进程P1准备进入临界区
    turn = 0; // 轮到进程P0进入临界区
    while (flag[0] && turn == 0); // 如果进程P0准备好进入临界区且轮到进程P0进入临界区，则进程P1等待
    critical section // 进程P1进入临界区
    flag[1] = false; // 进程P1退出临界区
}

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)); // 如果lock为true，则等待
    critical section // 进程P0进入临界区
    lock = false; // 进程P0退出临界区
}

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); // 自旋等待
    m->available = false;  // 获得锁
}

void release(mutex *m) {
    m->available = true;   // 释放锁
}

Usage example:

1
2
3
4
5
6
mutex lock;  // 初始化时available为true
// ...
acquire(&lock);
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;      // 信号量的值
    struct process *list;  // 等待队列
} semaphore;

void wait(semaphore *S) 
{  // P操作
    S->value--;
    if (S->value < 0) 
    {
        // 将当前进程加入等待队列
        add_to_list(S->list);
        block();  // 阻塞当前进程
    }
}

void signal(semaphore *S) 
{  // V操作
    S->value++;
    if (S->value <= 0 && S->list != NULL) 
    {
        // 从等待队列中唤醒一个进程
        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
// 互斥访问示例
semaphore mutex = 1;  // 初始化为1

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

// 生产者-消费者问题示例
semaphore empty = n;    // 初始化为缓冲区大小
semaphore full = 0;     // 初始化为0
semaphore mutex = 1;    // 用于互斥访问

// 生产者
wait(&empty);          // 等待空槽
wait(&mutex);          // 进入临界区
    // 添加数据到缓冲区
signal(&mutex);        // 离开临界区
signal(&full);         // 增加满槽

// 消费者
wait(&full);           // 等待满槽
wait(&mutex);          // 进入临界区
    // 从缓冲区取出数据
signal(&mutex);        // 离开临界区
signal(&empty);        // 增加空槽

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 {
    // 共享变量声明
    
    // 管程的初始化代码
    
    // 操作共享变量的过程
    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];       // 缓冲区
    int count = 0;       // 缓冲区中的项目数
    int in = 0, out = 0; // 放入和取出的位置
    
    condition not_full;  // 缓冲区不满条件
    condition not_empty; // 缓冲区不空条件
    
    procedure deposit(item) 
    {
        if (count == N)
            wait(not_full);    // 如果缓冲区满，等待
            
        buffer[in] = item;     // 放入项目
        in = (in + 1) % N;     // 更新位置
        count++;               // 增加计数
        
        signal(not_empty);     // 唤醒等待的消费者
    }
    
    procedure remove() 
    {
        if (count == 0)
            wait(not_empty);   // 如果缓冲区空，等待
            
        item = buffer[out];    // 取出项目
        out = (out + 1) % N;   // 更新位置
        count--;               // 减少计数
        
        signal(not_full);      // 唤醒等待的生产者
        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;   // 创建管程实例

// 生产者进程
void producer() 
{
    while (true) 
    {
        item = produce_item();
        bb.deposit(item);
    }
}

// 消费者进程
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;     // 当前读者数量
    boolean writing = false; // 是否有人在写
    
    condition read;      // 读者等待条件
    condition write;     // 写者等待条件
    
    procedure startRead() 
    {
        if (writing || !write.empty())
            wait(read);    // 如果有人在写或有写者等待，则读者等待
            
        readers++;       // 增加读者数量
        signal(read);    // 允许下一个读者进入
    }
    
    procedure endRead() 
    {
        readers--;       // 减少读者数量
        
        if (readers == 0)
            signal(write);  // 如果没有读者了，唤醒写者
    }
    
    procedure startWrite() 
    {
        if (readers > 0 || writing)
            wait(write);   // 如果有人在读或写，则写者等待
            
        writing = true;    // 标记有人在写
    }
    
    procedure endWrite() 
    {
        writing = false;   // 标记没人在写
        
        if (!read.empty())
            signal(read);   // 优先唤醒读者
        else
            signal(write);  // 否则唤醒写者
    }
}
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;   // 创建管程实例

// 读者进程
void reader() 
{
    while (true) 
    {
        rw.startRead();
        // 读取共享资源
        rw.endRead();
    }
}

// 写者进程
void writer() 
{
    while (true) 
    {
        rw.startWrite();
        // 修改共享资源
        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;
        // 尝试让左右邻居吃
        test((i+4) % 5);
        test((i+1) % 5);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
DiningPhilosophers dp;   // 创建管程实例

// 哲学家进程
void philosopher(int i) 
{
    while (true) 
    {
        think();        // 思考
        dp.pickup(i);   // 拿起筷子
        eat();          // 吃饭
        dp.putdown(i);  // 放下筷子
    }
}

Translated from the Chinese original.

Welcome to my other publishing channels

中文