EM Notebook

Appearance

第六章 同步 ​

6.1 同步问题 ​

同步指在多进程（或多线程）环境下，通过特定机制协调多个进程的执行顺序，确保它们有序、安全地访问共享资源（如内存、文件、设备等），避免因竞态条件导致的数据不一致或系统错误。

6.1.1 竞态条件 ​

竞态条件 (Race Condition) 指的是两个或多个进程同时访问和操作共享数据，最终结果依赖于它们的执行顺序。即当多个进程的执行顺序不同时，可能产生不同的结果。不确定的结果一定不是我们想要的。

这一现象通常出现在并发/并行环境中。比如，两个进程同时读取计数器值，分别递增，再写回，最终只递增了一次而非两次。

c
// 进程1执行
register1 = count;
register1 = register1 + 1;
count = register1;
c
// 进程2执行
register2 = count;
register2 = register2 + 1;
count = register2;

假设初始count=5，并发执行后count=6（而非预期的7）。

6.1.2 临界区 ​

一、临界区与内核调度 ​

临界区 (Critical Section) 指的是进程中访问共享资源的代码段，需要互斥访问。例如写一块内存数据、使用一台打印机。

在操作系统中，内核可以是非抢占式的或抢占式的。

非抢占式内核 (nonpreemptive kernel) 在内核态下不允许中断。一个进程在内核态执行时，其他进程不能打断它。非抢占式内核简化了内核的设计，因为不需要考虑内核态的上下文切换。在内核态中不需要使用锁来保护数据结构，因为不会被中断。

抢占式内核 (preemptive kernel) 则允许在内核态下被中断。内核可以在任何时候中断一个进程，以调度另一个进程。

在处理临界区问题时，非抢占式内核通过避免中断来确保临界区的互斥性，但现代操作系统几乎都是抢占式内核，则需要相关机制来保证互斥访问。

二、临界区问题 ​

如何确保当一个进程在临界区内执行时，其他进程不能进入临界区，这称为临界区问题。

c
do {
    入口区 entry section;
    临界区 critical section;
    退出区 exit section;
    剩余区 remainder section;
} while (1);

这是一个通常的临界区处理的代码结构。临界区指的是实际操作需要互斥的资源的代码片段，入口区和退出区则是解决临界区问题的关键。

临界区问题的解决方案需要满足的三个要求：

  • 互斥 (Mutual Exclusion)：同一时刻只有一个进程可以在临界区内

  • 空闲让进 (Progress)：如果没有进程在临界区且有进程希望进入，则必须允许其中一个进程进入

  • 有限等待 (Bounded Waiting)：进程请求进入临界区后，在有限时间内必须获准进入

三、软件解决方案 ​

1. Peterson 算法 ​

适用于两个进程的临界区互斥控制算法。

  • 基本思想：使用两个共享变量实现互斥

    • flag[] 数组：表示进程希望进入临界区的意愿
    • Turn 变量：表示哪个进程应该让步

  • 算法实现：

    c
    // 全局变量
boolean flag[2] = {false, false};  // 初始化为false
int turn = 0;                     // 初始值可以是0或1

// 进程i (i=0,1; j=1-i)的代码
// 进入区
flag[i] = true;                   // 表示进程i想进入临界区
turn = j;                         // 让另一个进程j先进入(谦让)
while (flag[j] && turn == j)      // 如果j想进且轮到j进入，则等待
    ; // 忙等待

// 临界区
// ...临界区代码...

// 退出区
flag[i] = false;                  // 表示进程i已离开临界区

// 剩余区
// ...其他代码...

  • 工作原理：

    1. 当进程 i 想进入临界区时，先设置 flag[i]=true 表明意愿
    2. 然后设置 turn=j 表示愿意让另一个进程 j 先进入
    3. 然后检查：如果进程 j 想进入 (flag[j]=true) 且轮到 j (turn=j)，则进程 i 等待
    4. 否则，进程 i 进入临界区
    5. 完成临界区操作后，设置 flag[i]=false 表示不再需要访问临界区

  • 正确性证明：满足临界区问题三个条件

    1. 互斥性：两个进程不可能同时在临界区

      • 假设进程0和进程1同时在临界区，则 flag[0]=flag[1]=true
      • turn 只能是0或1，假设 turn=0
      • 那么进程1在进入临界区前必须经过 while(flag[0] && turn==0) 判断
      • 由于条件为真，进程1应该等待，不可能进入临界区
      • 这与假设矛盾，因此互斥性成立

    2. 进展性：如果没有进程在临界区且有进程想进入，则某个进程一定能进入

      • 如果只有一个进程i想进入，则 flag[j]=false，while条件为假，i可以进入
      • 如果两个进程都想进入，则至少有一个进程的while条件为假（因为turn只能有一个值）

    3. 有限等待：进程等待进入临界区的时间是有限的

      • 如果进程 j 在临界区内，当它退出时会设置 flag[j]=false，进程 i 的while条件为假，可以进入
      • 如果进程 j 也在等待，则由于进程 i 已设置 turn=j，当 j 设置 turn=i 时，i可以进入临界区

  • 局限性：

    1. 仅适用于两个进程的情况
    2. 使用忙等待方式，浪费CPU资源
    3. 需要用户级代码自行保证互斥，容易出错
2. 面包店算法 ​

适用于多个进程的临界区互斥控制算法。

  • 基本思想：模拟面包店排号取号的场景

    • choosing[] 数组：表示进程是否正在选择号码
    • number[] 数组：表示每个进程的号码（优先级）

  • 算法实现：

    c
    // 全局变量
boolean choosing[n] = {false, ..., false};  // 初始化为false
int number[n] = {0, ..., 0};                // 初始化为0

// 进程i的代码
// 进入区
choosing[i] = true;                         // 表示进程i正在选择号码
number[i] = max(number[0], ..., number[n-1]) + 1;  // 选择一个号码
choosing[i] = false;                        // 选择完成

for (int j = 0; j < n; j++) {
    // 等待进程j选择号码完成
    while (choosing[j])
        ; // 忙等待
    
    // 等待所有号码更小的进程或号码相同但ID更小的进程
    while (number[j] != 0 && 
          (number[j] < number[i] || 
          (number[j] == number[i] && j < i)))
        ; // 忙等待
}

// 临界区
// ...临界区代码...

// 退出区
number[i] = 0;                             // 表示进程i已离开临界区

// 剩余区
// ...其他代码...

  • 工作原理：

    1. 当进程 i 想进入临界区时，先设置 choosing[i]=true 表示正在选号
    2. 然后选择一个比当前所有号码都大的号码（这保证了新来的进程优先级较低）
    3. 设置 choosing[i]=false 表示选号完成
    4. 进程 i 等待所有其他进程 j 完成选号
    5. 然后等待所有号码比自己小的进程或号码相同但ID更小的进程优先进入临界区
    6. 当满足条件后，进程 i 进入临界区
    7. 完成临界区操作后，设置 number[i]=0 表示不再需要访问临界区

  • 正确性证明：满足临界区问题三个条件

    1. 互斥性：两个进程不可能同时在临界区

      • 假设进程 i 和进程 j 同时在临界区
      • 则它们都有号码：number[i]>0 和 number[j]>0
      • 若 number[i]<number[j]，则j在进入前必须等待 i 完成
      • 若 number[i]=number[j] 且 i<j，则j必须等待 i 完成
      • 若 number[i]>number[j]，则 I 在进入前必须等待 j 完成
      • 这与假设矛盾，因此互斥性成立

    2. 进展性：如果没有进程在临界区且有进程想进入，则某个进程一定能进入

      • 如果进程i想进入，它会获得一个号码
      • 具有最小号码（或相同号码但ID最小）的进程不会被阻塞

    3. 有限等待：进程等待进入临界区的时间是有限的

      • 每个进程获得的号码是有限的
      • 进程进入临界区的顺序是按号码（和ID）严格排序的
      • 因此每个获得号码的进程最终都会进入临界区

  • 局限性：

    1. 寻找最大号码需要扫描所有进程的号码，开销较大
    2. 使用忙等待方式，浪费CPU资源
    3. 需要用户级代码自行保证互斥，容易出错
    4. 需要n个进程共享的变量较多(2n个)，不适合大规模进程

四、硬件解决方案 ​

TS (Test-and-Set) ​
c
boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}
CAS (Compare-and-Swap) ​
c
int CompareAndSwap(int *value, int expected, int new_value) {
    int temp = *value;
    if (temp == expected)
        *value = new_value;
    return temp;
}

6.1.3 生产者-消费者问题 ​

生产者-消费者问题是操作系统中一个经典的进程同步问题，也是许多实际系统的抽象模型。

生产者-消费者问题涉及两类进程：

  • 生产者：负责生产数据项（产品）并将其放入共享缓冲区
  • 消费者：负责从共享缓冲区取出数据项并消费（处理）它们

在这个问题中，生产者和消费者共享一个固定大小的缓冲区，并且需要遵循以下规则：

  1. 生产者不能在缓冲区已满时放入数据
  2. 消费者不能从空缓冲区取出数据
  3. 在任何时刻，只能有一个进程可以访问缓冲区（互斥）

根据缓冲区的容量是否有限，还可以分为无界缓冲区、有界缓冲区两种情况。

6.2 同步工具 ​

6.2.1 互斥锁 ​

互斥锁 (mutual lock) 是一种用于多线程/多进程编程的同步机制，用于确保在任意时刻只有一个线程能访问共享资源。当一个进程进入临界区前应该得到 acquire() 锁，退出之后则释放 release() 锁，用锁保护临界区从而防止出现竞态条件。

对 acquire() 和 release() 的调用必须原子地执行，可以使用 CAS 操作实现互斥锁。

c
acquire() {
  while (!available)
    ; // 忙等待
  available = false;
}

release() {
  available;
}

这种实现的主要缺点是需要忙等待，这显然造成了 CPU 时间的浪费。这种互斥锁也被称为自旋锁 (spinlock)，因为在等待锁可用的过程中一直在“自旋”。自旋锁并非没有优点，当进程必须获取锁时，持续忙等待可以避免上下文切换的开销。

互斥锁可视为计数为1的信号量。

6.2.2 信号量 ​

一、信号量 ​

信号量 (Semaphore) 是一个具有整数值的变量，只能通过两个标准原子操作访问：wait (P, 荷兰语proberen) 和 signal (V, 荷兰语verhogen)，由荷兰计算机科学家 Dijkstra 提出。

  • P操作 (wait)：

    c
    wait(S) {
    while (S <= 0)
        ; // 等待
    S--;
}

  • V操作 (signal)：

    c
    signal(S) {
    S++;
}

操作系统通常区分计数信号量 (Counting Semaphore)和二进制信号量 (Binary Semaphore)。

计数信号量值不受限，二进制信号量的值只能为0或1。二进制信号量类似于互斥锁。

二进制信号量（互斥锁）一般用于实现互斥访问临界区，计数信号量用于控制有限资源的访问。

二、信号量的使用 ​

  1. 互斥：使用二进制信号量确保临界区互斥访问

    c
    semaphore mutex = 1;

// 进程代码
wait(mutex);    // 进入临界区
// 临界区代码
signal(mutex);  // 离开临界区

  2. 生产者-消费者问题：

    c
    semaphore empty = n;   // 初始值为缓冲区大小n
semaphore full = 0;    // 初始值为0
semaphore mutex = 1;   // 互斥访问缓冲区

// 生产者
wait(empty);     // 等待空槽位
wait(mutex);     // 进入临界区
// 添加项到缓冲区
signal(mutex);   // 离开临界区
signal(full);    // 通知有新项可用

// 消费者
wait(full);      // 等待有数据项
wait(mutex);     // 进入临界区
// 从缓冲区取出项
signal(mutex);   // 离开临界区
signal(empty);   // 通知有空槽位

6.2.3 管程 ​

一、管程 ​

管程 (Monitor) 是一种高级同步结构，将共享数据和操作封装在一个模块中。外部只能通过管程定义的过程访问管程内的数据，管程内部自动实现互斥，任何时刻只有一个进程可以在管程内活动。

管程的组成：

  • 共享变量声明
  • 操作过程（函数）
  • 初始化代码
  • 条件变量（用于进程同步）

条件变量操作

  • P (wait)：当前进程等待条件满足，释放管程
  • V (signal)：通知等待该条件的一个进程，表示条件可能已满足

二、管程的实现 ​

解决生产者-消费者问题为例：

c
// 1. 定义管程结构
typedef struct {
    mutex lock;          // 互斥锁
    cond notFull;        // 缓冲区未满的条件变量
    cond notEmpty;       // 缓冲区非空的条件变量
    int buffer[MAX];     // 共享缓冲区
    int count = 0;       // 当前数据量
} Monitor;

// 2. 生产者操作
void produce(Monitor *mon, int item) {
    lock(mon->lock);                // 进入管程（加锁）
    while (mon->count == MAX) {     // 缓冲区满则等待
        wait(mon->notFull, mon->lock); // 释放锁并阻塞
    }
    mon->buffer[mon->count++] = item; // 生产数据
    signal(mon->notEmpty);          // 唤醒一个消费者
    unlock(mon->lock);              // 离开管程（解锁）
}

// 3. 消费者操作
int consume(Monitor *mon) {
    lock(mon->lock);                // 进入管程（加锁）
    while (mon->count == 0) {       // 缓冲区空则等待
        wait(mon->notEmpty, mon->lock); // 释放锁并阻塞
    }
    int item = mon->buffer[--mon->count]; // 消费数据
    signal(mon->notFull);           // 唤醒一个生产者
    unlock(mon->lock);              // 离开管程（解锁）
    return item;
}

6.2.4 条件变量 ​

条件变量 (Condition Variable) 本身并不是锁，它是一种同步机制，总是与互斥锁一起使用，用于在多线程环境下等待某个特定条件满足。当一个线程发现某个条件不满足时，它可以释放互斥锁并阻塞在条件变量上；当另一个线程改变了条件并希望唤醒等待的线程时，它会通知（signal）或广播（broadcast）条件变量。

  • 特点:
    • 总是与互斥锁结合使用：条件变量不能单独使用，它需要一个互斥锁来保护对共享条件的访问。
    • 等待与通知：线程通过 wait 操作等待条件满足并释放互斥锁，通过 signal (或 notify) 和 broadcast (或 notifyAll) 操作来通知等待的线程。
    • 用途：主要用于线程间的协作，例如生产者-消费者问题中，生产者在缓冲区满时等待“未满”条件，消费者在缓冲区空时等待“非空”条件。
  • 操作:
    • wait(cond_var, mutex)：原子地释放 mutex 并阻塞在 cond_var 上，直到被唤醒。被唤醒后，重新获取 mutex。
    • signal(cond_var) (或 notify)：唤醒一个（如果存在）在 cond_var 上等待的线程。
    • broadcast(cond_var) (或 notifyAll)：唤醒所有在 cond_var 上等待的线程。
特性互斥锁 (Mutex)信号量 (Semaphore)条件变量 (Condition Variable)
用途保护临界区，实现互斥访问。控制资源访问（计数信号量），或实现互斥（二进制信号量），实现进程同步。线程间协作，等待特定条件满足。
本质一种锁机制，用于独占访问。一个整数值变量，通过P/V操作控制对共享资源的访问权限。一种通知机制，用于线程在特定条件不满足时挂起，以及在条件满足时被唤醒。
状态锁定/未锁定。一个非负整数值。没有自身状态，依赖于互斥锁保护的共享条件。
与锁的关系本身就是锁。二进制信号量可作为互斥锁使用。必须与互斥锁一起使用，互斥锁保护条件变量所依赖的共享状态。
阻塞机制获取锁失败时阻塞。P操作时，如果信号量为0则阻塞。在 wait 操作时阻塞，并释放关联的互斥锁。
唤醒机制锁被释放时，等待的线程被唤醒。V操作时，唤醒一个（或多个）等待的进程。通过 signal 或 broadcast 操作唤醒等待的线程。

6.2.5 经典同步问题 ​

一、读者-写者问题 ​

  • 问题描述：多个进程共享一个数据资源，分为两类：

    • 读者 (Readers)：只读取数据，不对数据进行任何修改。多个读者可以同时读取数据。
    • 写者 (Writers)：修改数据。写者必须独占访问，即在写者修改数据时，不允许任何其他读者或写者访问数据。

  • 核心冲突：

    1. 多个读者可以并发执行，互不影响。
    2. 写者与任何其他进程（包括其他写者和读者）之间必须是互斥的。
    3. 需要避免饥饿问题，即读者或写者不应无限期等待。

  • 第一读者-写者问题 (Readers-Preference)：读者优先，只要有读者正在读取数据，新的读者可以直接进入，写者必须等待所有读者完成。这可能导致写者饥饿。

    c
    semaphore mutex = 1;    // 保护readcount的互斥访问
semaphore wrt = 1;      // 控制写者和第一个读者/最后一个读者的互斥访问
int readcount = 0;      // 当前正在读的进程数

// 读者进程
wait(mutex);            // 1. 获取readcount的互斥锁，确保对readcount的修改是原子性的
readcount++;
if (readcount == 1) {   // 2. 如果是第一个读者进入，则阻止写者访问
    wait(wrt);          // P(wrt)操作，如果wrt为0，写者将被阻塞
}
signal(mutex);          // 3. 释放readcount的互斥锁

// 进行数据读取操作

wait(mutex);            // 4. 获取readcount的互斥锁
readcount--;
if (readcount == 0) {   // 5. 如果是最后一个读者离开，则允许写者访问
    signal(wrt);        // V(wrt)操作，唤醒可能的写者
}
signal(mutex);          // 6. 释放readcount的互斥锁

// 写者进程
wait(wrt);              // 1. 请求独占访问，等待wrt信号量变为1（无读者或无其他写者）
// 进行数据写入操作
signal(wrt);            // 2. 释放访问权，允许其他读者或写者进入

    分析：

    • mutex 信号量：用于保护 readcount 变量，确保多个读者同时修改 readcount 时不会发生竞态条件。
    • wrt 信号量：用于实现写者之间的互斥，以及读者与写者之间的互斥。当第一个读者进入时，它会执行 wait(wrt) 阻止写者；当最后一个读者离开时，它会执行 signal(wrt) 允许写者。写者在写入数据前后也通过 wrt 信号量进行控制。
    • 优点：读者优先，并发性较高。
    • 缺点：当读者持续不断进入时，写者可能会无限期等待，导致写者饥饿。

  • 第二读者-写者问题 (Writers-Preference)：写者优先，一旦有写者请求访问，后续的读者必须等待，直到写者完成。这可能导致读者饥饿。

    为了避免写者饥饿，通常需要引入额外的信号量和计数器来跟踪等待的写者数量。一个常见的解决方案是，当有写者等待时，新的读者不能立即进入，必须等待所有等待的写者完成。

    c
    semaphore mutex = 1;      // 保护readcount
semaphore wmutex = 1;     // 保护writecount
semaphore r_wrt = 1;      // 控制读者与写者的互斥（针对读者入口）
semaphore w_wrt = 1;      // 控制写者的互斥
int readcount = 0;        // 正在读的读者数量
int writecount = 0;       // 正在写的写者数量

// 读者进程
wait(r_wrt);              // 1. 读者进入前，先检查是否有写者在等待
wait(mutex);
readcount++;
if (readcount == 1) {
    wait(w_wrt);          // 如果是第一个读者，阻塞写者
}
signal(mutex);
signal(r_wrt);            // 允许其他读者进入

// 进行数据读取操作

wait(mutex);
readcount--;
if (readcount == 0) {
    signal(w_wrt);        // 如果是最后一个读者，允许写者进入
}
signal(mutex);

// 写者进程
wait(wmutex);             // 1. 保护writecount
writecount++;
if (writecount == 1) {
    wait(r_wrt);          // 如果是第一个写者，阻塞读者入口
}
signal(wmutex);

wait(w_wrt);              // 2. 独占访问
// 进行数据写入操作
signal(w_wrt);

wait(wmutex);
writecount--;
if (writecount == 0) {
    signal(r_wrt);        // 如果是最后一个写者，允许读者进入
}
signal(wmutex);

    分析：

    • r_wrt 信号量：控制读者入口，当有写者等待时，会阻止新的读者进入。
    • w_wrt 信号量：控制写者互斥。
    • mutex 和 wmutex：分别保护 readcount 和 writecount。
    • 优点：写者饥饿问题得到缓解。
    • 缺点：可能导致读者饥饿。

二、哲学家就餐问题 ​

  • 问题描述：有五位哲学家围坐在一张圆桌旁，每两位哲学家之间有一根筷子。哲学家们会交替地进行思考和进餐。当一位哲学家想要进餐时，他必须同时拿起他左右两边的两根筷子。如果筷子已经被其他哲学家拿走，他必须等待。

  • 核心问题：

    1. 死锁 (Deadlock)：最常见的问题是所有哲学家同时拿起他们左边的筷子，然后都等待右边的筷子，导致所有哲学家都无法进餐，陷入死锁状态。
    2. 饥饿 (Starvation)：某些哲学家可能由于调度不公而无法长时间进餐。

  • 解决方案目标：在保证互斥访问筷子的前提下，避免死锁和饥饿。

  • 解决方案一：最多允许四个哲学家同时拿起左侧筷子（限制并发数量） 通过引入一个额外的信号量 mutex，将同时拿起筷子的哲学家数量限制为最多四个。这意味着至少有一位哲学家无法拿起他左边的筷子，从而打破了循环等待条件。

    c
    semaphore mutex = 1;                  // 限制同时进餐的哲学家数量（或拿第一根筷子的数量）
semaphore chopstick[5] = {1,1,1,1,1}; // 每根筷子一个二进制信号量，初始为1

// 哲学家i的代码 (i = 0, 1, ..., 4)
while (true) {
    think(); // 哲学家思考

    wait(mutex);           // 1. 获取进入临界区的权限，限制同时竞争筷子的哲学家数量
    wait(chopstick[i]);    // 2. 拿起左边的筷子
    wait(chopstick[(i+1)%5]); // 3. 拿起右边的筷子
    signal(mutex);         // 4. 释放进入临界区的权限

    eat(); // 哲学家进餐

    signal(chopstick[i]);    // 5. 放下左边的筷子
    signal(chopstick[(i+1)%5]); // 6. 放下右边的筷子
}

    分析：

    • mutex 信号量：初始值为1，哲学家在尝试拿筷子前必须先获取 mutex。这实际上创建了一个“包厢”，每次只允许一定数量的哲学家同时进入竞争筷子，从而避免了所有哲学家同时拿起左侧筷子的情况。
    • 优点：简单有效，能避免死锁。
    • 缺点：降低了并发性，因为并非所有筷子都在同一时间被利用。

  • 解决方案二：不对称地拿筷子（打破循环等待） 通过规定奇数号哲学家和偶数号哲学家拿筷子的顺序不同，来打破循环等待条件。

    • 奇数哲学家：先拿左边的筷子，再拿右边的筷子。
    • 偶数哲学家：先拿右边的筷子，再拿左边的筷子。
    c
    semaphore chopstick[5] = {1,1,1,1,1}; // 每根筷子一个二进制信号量，初始为1

// 哲学家i的代码
while (true) {
    think(); // 哲学家思考

    if (i % 2 == 0) { // 偶数哲学家
        wait(chopstick[(i+1)%5]); // 先拿右边的筷子
        wait(chopstick[i]);       // 再拿左边的筷子
    } else { // 奇数哲学家
        wait(chopstick[i]);       // 先拿左边的筷子
        wait(chopstick[(i+1)%5]); // 再拿右边的筷子
    }

    eat(); // 哲学家进餐

    if (i % 2 == 0) {
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
    } else {
        signal(chopstick[(i+1)%5]);
        signal(chopstick[i]);
    }
}

    分析：

    • 这种方法打破了哲学家总是按照相同的顺序（例如，总是先左后右）获取资源的模式，从而破坏了死锁的循环等待条件。
    • 优点：解决了死锁问题。
    • 缺点：实现上稍微复杂，且可能仍然存在饥饿问题。

三、睡眠理发师问题 ​

  • 问题描述：一个理发店里有一个理发师、一把理发椅和N把等待顾客的椅子（候客区）。

    • 如果店里没有顾客，理发师会睡觉。
    • 当有顾客到来时，如果理发师正在睡觉，则唤醒理发师。
    • 如果所有等待椅子都已满，新来的顾客会直接离开。
    • 如果理发师忙碌且有空位，新来的顾客会坐在等待椅子上。

  • 核心问题：

    1. 理发师和顾客之间的同步。
    2. 对等待椅子数量的互斥访问。

  • 解决方案目标：确保理发师和顾客之间正确协作，避免死锁和不一致的状态。

  • 解决方案：使用三个信号量和一个计数器。

    c
    semaphore customers = 0;  // 记录等待理发的顾客数（初始为0）
semaphore barber = 0;     // 记录理发师是否可用（初始为0，表示理发师在睡觉）
semaphore mutex = 1;      // 用于互斥访问waiting变量（初始为1）
int waiting = 0;          // 当前等待椅子上的顾客数
const int N = 5;          // 等待椅子的数量（示例，可根据需求修改）

// 理发师代码
while (true) {
    wait(customers);      // 1. 如果没有顾客，理发师阻塞（睡觉）
    wait(mutex);          // 2. 获取waiting变量的互斥锁
    waiting--;            // 3. 减少等待顾客数，因为理发师要开始服务一个顾客
    signal(barber);       // 4. 通知顾客理发师已准备好理发
    signal(mutex);        // 5. 释放waiting变量的互斥锁
    cut_hair();           // 6. 理发（耗时操作）
}

// 顾客代码
// 每个顾客作为一个独立的进程或线程执行
void customer_entry() {
    wait(mutex);              // 1. 获取waiting变量的互斥锁，检查空位
    if (waiting < N) {        // 2. 检查是否有等待椅子
        waiting++;            // 3. 增加等待顾客数
        signal(customers);    // 4. 唤醒理发师（如果他在睡觉）
        signal(mutex);        // 5. 释放waiting变量的互斥锁
        wait(barber);         // 6. 等待理发师准备好（理发师会通过signal(barber)来通知）
        get_haircut();        // 7. 接受理发服务
    } else {
        signal(mutex);        // 8. 释放waiting变量的互斥锁（即使没有理发也要释放）
        leave();              // 9. 离开理发店（因为没有空位）
    }
}

    分析：

    • customers 信号量：表示等待服务的顾客数量。理发师通过 wait(customers) 来等待顾客，当有新顾客到来时，顾客通过 signal(customers) 来唤醒理发师。
    • barber 信号量：表示理发师是否可用。顾客通过 wait(barber) 来等待理发师准备好，理发师通过 signal(barber) 来通知顾客他已准备好。
    • mutex 信号量：用于保护 waiting 变量的互斥访问，防止多个顾客同时修改 waiting 时发生竞态条件。
    • waiting 变量：记录当前在等待椅子上等待的顾客数量。
    • N 常量：表示等待椅子的总数量。
    • 优点：正确地解决了理发师和顾客之间的同步问题，防止了死锁和资源浪费。
    • 缺点：仍需合理设置信号量初始值和操作顺序，以避免潜在的竞态条件或逻辑错误。

6.3 死锁 ​

死锁是并发系统中的一种常见问题，可能导致系统资源的永久阻塞。

6.3.1 必要条件 ​

死锁发生需要同时满足以下四个必要条件：

  • 互斥(Mutual Exclusion)

    • 资源必须是互斥使用的，一次只能被一个进程使用

    • 如果另一个进程请求该资源，请求进程必须等待直到资源被释放

  • 持有等待(Hold and Wait)

    • 进程至少持有一个资源，并正在等待获取其他进程持有的附加资源

    • 进程获取部分资源后，继续保持这些资源的同时等待其他资源

  • 非抢占(No Preemption)

    • 已分配给进程的资源不能被强制抢占

    • 资源只能由持有它的进程在完成任务后自愿释放

  • 循环等待(Circular Wait)

    • 存在一组等待进程{P0, P1, ..., Pn}

    • P0等待P1持有的资源，P1等待P2持有的资源，...，Pn等待P0持有的资源

    • 形成一个闭环的等待链

6.3.2 资源分配图 ​

资源分配图是一种描述进程与资源之间请求和分配关系的有向图模型。

一、图的组成 ​

  • 进程节点：通常表示为圆圈
  • 资源类型节点：通常表示为方框，内含多个资源实例
  • 请求边：从进程指向资源的有向边，表示进程请求资源
  • 分配边：从资源指向进程的有向边，表示资源已分配给进程

二、死锁检测 ​

  • 如果资源分配图中包含环，且环中的每个资源类型只有一个实例，则系统处于死锁状态
  • 如果资源有多个实例，环的存在是死锁的必要条件，但不是充分条件

三、示例 ​

  • P1持有R2，请求R1
  • P2持有R1，请求R2
  • 形成环路P1→R1→P2→R2→P1，造成死锁

6.4 死锁处理 ​

处理死锁的方法主要有四种：预防、避免、检测与恢复、忽略。

6.4.1 预防 ​

死锁预防是通过破坏死锁的四个必要条件之一来防止死锁发生。

一、破坏互斥条件 ​

  • 将资源设为可共享使用
  • 不是所有资源都可以共享（如打印机）
  • 实际应用中很难实现

二、破坏持有等待条件 ​

  • 一次性分配：进程必须一次性请求并获得所有资源
  • 释放后申请：进程需要释放当前持有的所有资源，然后一次性请求所有需要的资源
  • 缺点：资源利用率低，可能导致饥饿

三、破坏非抢占条件 ​

  • 如果进程请求的资源被其他进程占用，则可以抢占其他进程的资源
  • 适用于状态可以保存和恢复的资源（如CPU和内存）
  • 不适用于某些资源（如打印机）

四、破坏循环等待条件 ​

  • 对所有资源类型进行全序编号
  • 每个进程按照递增顺序请求资源
  • 确保资源请求形成有序偏序关系，防止循环
  • 缺点：可能导致资源利用率低

6.4.2 避免 ​

死锁避免是指在资源分配之前进行判断，只分配不会导致死锁的资源请求。

一、安全状态 ​

  • 安全状态：系统能按某种序列（安全序列）为所有进程分配资源，使每个进程都能完成
  • 不安全状态：不存在安全序列，系统可能发生死锁
  • 死锁避免的目标：保持系统处于安全状态

二、银行家算法 ​

银行家算法是一种著名的死锁避免算法，由Dijkstra提出。

数据结构 ​
  • Available：长度为m的向量，表示每种资源的可用实例数
  • Max：n×m矩阵，表示每个进程对每种资源的最大需求量
  • Allocation：n×m矩阵，表示每个进程当前已分配的每种资源实例数
  • Need：n×m矩阵，表示每个进程还需要的每种资源实例数，Need[i,j] = Max[i,j] - Allocation[i,j]
算法步骤 ​
  1. 初始化系统数据结构
  2. 当进程Pi请求资源时，先检查请求是否超过声明的最大需求
  3. 检查是否有足够的可用资源
  4. 系统假设分配请求的资源，然后通过安全性算法检查系统是否仍处于安全状态
  5. 如果安全，分配资源；如果不安全，进程等待
安全性算法 ​
  1. 初始化Work = Available，Finish[i] = false（对所有进程i）
  2. 查找满足条件的进程Pi：Finish[i] = false 且 Need[i] ≤ Work
  3. 如果找到，则Work = Work + Allocation[i]，Finish[i] = true，转步骤2
  4. 如果所有进程的Finish都为true，则系统处于安全状态
优缺点 ​
  • 优点：可以避免死锁，不限制资源请求顺序
  • 缺点：
    • 需要预先知道进程的最大资源需求
    • 进程数量必须是固定的
    • 资源释放必须一次性完成

6.4.3 检测与恢复 ​

死锁检测与恢复是允许系统进入死锁状态，但提供机制来检测和恢复。

一、死锁检测算法 ​

  1. 单实例资源：使用等待图（资源分配图的简化版）检测是否有环
  2. 多实例资源：使用类似银行家算法的方法
多实例资源检测算法 ​
  1. 初始化Work = Available，对于每个进程Pi，如果Allocation[i] = 0，则Finish[i] = true，否则Finish[i] = false
  2. 查找满足条件的进程Pi：Finish[i] = false 且 Request[i] ≤ Work
  3. 如果找到，则Work = Work + Allocation[i]，Finish[i] = true，转步骤2
  4. 如果存在Finish[i] = false的进程，则系统处于死锁状态

二、检测频率 ​

  • 死锁检测的频率影响系统性能
  • 频繁检测：CPU开销大，但能及时发现死锁
  • 不频繁检测：延迟发现死锁，可能导致更多进程卷入死锁

三、从死锁中恢复 ​

  1. 进程终止

    • 终止所有死锁进程：简单但开销大
    • 一次终止一个进程直到死锁消除：开销小但计算复杂

  2. 资源抢占

    • 选择被抢占的资源：影响最小的资源
    • 选择被抢占的进程：考虑进程优先级和进程已运行时间
    • 回滚：将进程回滚到安全状态，需要记录进程状态
    • 饥饿问题：同一进程可能被反复抢占，需要考虑回滚次数因素

6.4.4 忽略 ​

一些操作系统采取“鸵鸟算法”，即假装死锁不会发生。

应用场景

  • 死锁发生非常罕见
  • 预防或避免死锁的代价太高
  • 系统会定期重启或有其他恢复机制

常见系统的处理方式

  • 大多数操作系统（如Windows、Linux、macOS）不直接处理死锁
  • 依靠应用程序自身的超时机制或用户干预来解决
  • 在特定领域（如数据库系统）采用更严格的死锁处理策略