Hugo's Cyber Heritage

Shine or Die

OS-06 Process Synchronization

发表于 分类于
本文字数： 4.2k 阅读时长 ≈ 4 分钟

本文介绍了操作系统中的进程同步问题。

Background: Critical-Section Problem

多个进程并发执行时，都有访问和修改共享资源的代码段（临界区）。若缺乏同步机制，会因多个进程同时进入临界区操作共享资源，导致数据不一致、产生竞争条件(race condition)。

解决方案：

  • 互斥性(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

假设加载和存储指令是原子操作，不可中断。两个进程共享两个变量，int turn用于指示轮到哪个进程进入临界区，boolean flag[2]数组用于表示进程是否准备好进入临界区，flag[i] = true表示进程准备进入。

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退出临界区
}

局限性：

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

当存在指令重排序时，原本顺序执行的指令可能会改变执行顺序，导致进程同时进入临界区。

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.

当执行内存屏障指令时，在同一进程内，它确保所有之前的加载（load）和存储（store）操作都完成后，才会执行后续的加载 / 存储操作。即使处理器或编译器对指令进行了重排序，内存屏障也能保证存储操作在内存中完成，并且在未来的加载 / 存储操作之前对其他处理器可见。

Hardware Instructions

原子变量(atomic variable)：一个或多个指令的执行是不可分割的，要么全部执行，要么全部不执行。

局限性：unbounded waiting，竞争资源时获取顺序是随机的。

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

举例：

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

void P0() 
{
    while (TestAndSet(&lock)); // 如果lock为true，则等待
    critical section // 进程P0进入临界区
    lock = false; // 进程P0退出临界区
}

从并发执行的其他线程或进程的视角看，它瞬间完成，要么完整执行，要么完全不执行。

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

互斥锁(mutex lock)是最简单的同步工具。一个进程在访问临界区时必须先获得锁；离开时必须释放锁。mutex lock包含一个布尔变量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;   // 释放锁
}

使用示例：

1
2
3
4
5
6
mutex lock;  // 初始化时available为true
// ...
acquire(&lock);
critical section  // 临界区
release(&lock);
remainder section

主要特点：

  1. 互斥性：任意时刻只有一个进程可以获得锁
  2. 自旋等待(busy waiting)：进程在等待锁时会持续占用CPU
  3. 适用于：
    • 预期等待时间短
    • 多处理器系统

缺点：

  1. 自旋等待浪费CPU时间
  2. 可能发生优先级反转(priority inversion)：低优先级进程持有锁时，高优先级进程必须等待

Semaphores

信号量(Semaphore)是一个更强大的同步工具，由Dijkstra提出。信号量S是一个整型变量，除了初始化外，只能通过两个原子操作wait(P)和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) 
    {
        // 从等待队列中唤醒一个进程
        process *p = remove_from_list(S->list);
        wakeup(p);
    }
}

信号量的类型：

  1. 二进制信号量(Binary Semaphore)

    • 值只能为0或1
    • 类似于mutex lock，但实现机制不同
    • 适用于互斥和同步

  2. 计数信号量(Counting Semaphore)

    • 值可以是任意整数
    • 用于资源管理
    • 例如：控制对有限资源的访问

使用示例：

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);        // 增加空槽

信号量的优点：

  1. 没有忙等待，进程阻塞时不消耗CPU
  2. 可以实现更复杂的同步
  3. 适用于多种同步场景

信号量的缺点：

  1. 使用不当容易导致死锁
  2. 难以保证正确性
  3. 编程容易出错（wait/signal顺序错误）

Monitors

Synchronization Problem Formulations