5 Process Synchronization

5.1 Background

多道程序环境下，进程是并发执行的，不同进程间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，达到资源共享和进程协作，避免进程之间的冲突，引入了进程同步的概念。

我们以生产者消费者为背景引入

Producer process(thread)：
item nextProduced;
while (1) {
    while (counter == BUFFER_SIZE) ; /* do nothing */
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

Consumer process (thread)：
item nextConsumed;
while (1) {
    while (counter == 0) ; /* do nothing */
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

在这里

counter++;
counter--;

必须要是原子操作，因为在机器指令中，一句 count++ 可能有三条指令

register1 = counter
register1 = register1 + 1
counter = register1

如果生产者和消费者同时更新 buffer，那么汇编语句可能发生交叉，进而出现不同的结果

Example

---

竞争条件（Race condition）：多个进程并发地访问并操作共享数据时发生的情况。共享数据的最终值取决于哪个进程最后完成操作。程序执行的结果依赖于这些访问发生的具体顺序。

为了防止竞争条件，并发进程必须被同步。

进程之间竞争资源面临三个控制问题：

• 互斥（mutual exclusion )指多个进程不能同时使用同一个资源

• 死锁（deadlock )指多个进程互不相让，都得不到足够的资源。永远得不到资源

• 饥饿（starvation )指一个进程长时间得不到资源（其它进程可能轮流占用资源）。资源分配不公平

5.2 The Critical-Section Problem

有 n 个进程都在竞争使用某些共享数据。其中每个进程都有一个代码段，称为 临界区（critical section），在这个区域内会访问共享数据。

问题就是我们必须确保当一个进程正在执行它的临界区时，其他任何进程都不能进入自己的临界区。

临界资源和临界区

临界资源:一次只允许一个进程使用(访问)的资源。如：硬件打印机、磁带机等，软件的消息缓冲队列、变量、数组、缓冲区等。

临界区：访问临界资源的那段代码

一个程序基本的结构如下

do {
    entry section;        // 进入区
    critical section;     // 临界区
    exit section;         // 退出区
    remainder section;    // 剩余区
} while (true);

区域	功能说明
entry section（进入区）	负责检查是否可以进入临界区。 若允许进入，则设置“正在访问临界资源”的标志（可理解为“上锁”），防止其他进程同时进入。
critical section（临界区）	实际访问共享资源的代码段。 例如：读写缓冲区、修改计数器等。 必须保证互斥执行（一次只允许一个进程执行）。
exit section（退出区）	负责解除“正在访问临界资源”的标志（可理解为“解锁”），允许其他等待的进程进入临界区。
remainder section（剩余区）	进程完成临界区操作后执行的其余代码，不涉及共享资源，无特殊要求。

任何解决“临界区问题”（Critical-Section Problem）的算法，都必须满足以下 三个基本要求

• 互斥（Mutual Exclusion）：如果进程 \(P_i\) 正在执行其临界区代码，则其他任何进程都不能进入各自的临界区。

• 空闲让进（Progress）：如果没有进程正在执行临界区，并且存在一些进程希望进入临界区，那么下一个进入临界区的进程选择不能被无限期推迟。

• 有限等待（Bounded Waiting）：当一个进程发出请求要进入临界区后，在它被批准之前，其他进程最多只能进入临界区有限次

还有一个不是必须的要求是让权等待：当一个进程无法进入临界区时，主动释放 CPU，让其他进程运行

为解决这个问题，有三种机制在接下来几节会介绍

• 软件方法
• 硬件方法
• 信号量机制

对于访问共享的内核数据(shared kernel data)，非抢占的内核基本上不受竞态条件（race conditions）的影响，为什么？

因为非抢占式内核（non-preemptive kernel） 在执行时不会被中断，所以一旦一个进程进入内核态并开始访问共享内核数据，它会一直运行直到完成该操作，不会被其他进程打断。

5.3 Peterson’s Solution

实现两个进程之间的互斥访问共享资源，使用纯软件方法（无需硬件支持），满足临界区问题的三个条件

我们假设 LOAD 和 STORE 指令都是原子操作，不可被打断。我们一步一步从简到难展示 Peterson 算法

首先我们一个最简单的思路就是用一个标志位来表示当前资源有没有被占领，提出单标志法

用 turn = i 表示“当前轮到进程 \(P_i\) 进入临界区”

进程 \(P_0\)

while (turn != 0);        // ① 检查：是否轮到我？
critical section;         // ② 临界区：访问共享资源
turn = 1;                 // ③ 谦让：下次轮到 P1
remainder section;        // ④ 剩余区：做其他事情

进程 \(P_1\)

while (turn != 1);        // ⑤ 检查：是否轮到我？
critical section;         // ⑥ 临界区：访问共享资源
turn = 0;                 // ⑦ 谦让：下次轮到 P0
remainder section;        // ⑧ 剩余区：做其他事情

缺点就是强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在 \(P_i\) 出让临界区之后，\(P_j\) 使用临界区之前，\(P_i\) 不可能再次使用临界区；

---

为解决这个问题，引入一个标志位来表达意愿

boolean flag[2];  // 两个布尔标志，分别表示 P0 和 P1 是否想进入临界区
flag[0] = false;  // P0 不想进入
flag[1] = false;  // P1 不想进入

进程 \(P_0\)

while (flag[1]);        // ① 检查：P1 是否想用？是 → 等待
flag[0] = true;         // ② 标记：我想要用了（上锁）
critical section;       // ③ 访问资源
flag[0] = false;        // ④ 解锁：我不用了
remainder section;      // ⑤ 做其他事

进程 \(P_1\)

while (flag[0]);        // ⑤ 检查：P0 是否想用？是 → 等待
flag[1] = true;         // ⑥ 标记：我想要用了（上锁）
critical section;       // ⑦ 访问资源
flag[1] = false;        // ⑧ 解锁：我不用了
remainder section;      // ⑨ 做其他事

问题就是 \(P_0\) 和 \(P_1\) 可能同时进入临界区。当 flag [0] = flag [1] = false 时， \(P_0\) 执行了 while (flag[1]) 后，\(P_1\) 执行 while (flag[0]) ，这样两个进程同时进入了临界区

---

为解决这个问题，可以选择后检查

P0:
flag[0] = true;           // ① 我想要用了（上锁）
while (flag[1]);          // ② 检查：P1 是否也想用？是 → 等待
critical section;         // ③ 访问资源
flag[0] = false;          // ④ 解锁：我不用了
remainder section;        // ⑤ 做其他事

P1:
flag[1] = true;           // ⑤ 我想要用了（上锁）
while (flag[0]);          // ⑥ 检查：P0 是否也想用？是 → 等待
critical section;         // ⑦ 访问资源
flag[1] = false;          // ⑧ 解锁：我不用了
remainder section;        // ⑨ 做其他事

这个方法也有类似的问题：\(P_0\) 和 \(P_1\)可能都进入不了临界区。当 \(P_0\) 执行了 flag[0] := true 后， 然后 \(P_1\) 执行了 flag[1] := true，这样两个进程都无法进入临界区

---

综合上述三种方法，提出 Peterson 算法，从而解决上述三个方法的一些问题。

它有三个标志位

bool flag[2];    // 表示每个进程是否想进入临界区
int turn;        // 表示当前轮到哪个进程进入

初始值

flag[0] = flag[1] = false;
turn = 0;

进程 \(P_0\)

flag[0] = true;               // ① 我想要用了（上锁）
turn = 1;                     // ② 让对方先走（谦让）
while (flag[1] == true && turn == 1); // ③ 等待：直到对方不想用 或 轮到我
critical section;             // ④ 访问资源
flag[0] = false;              // ⑤ 解锁：我不用了
remainder section;            // ⑥ 做其他事

进程 \(P_1\)

flag[1] = true;               // ⑤ 我想要用了（上锁）
turn = 0;                     // ⑥ 让对方先走（谦让）
while (flag[0] == true && turn == 0); // ⑦ 等待：直到对方不想用 或 轮到我
critical section;             // ⑧ 访问资源
flag[1] = false;              // ⑨ 解锁：我不用了
remainder section;            // ⑩ 做其他事

---

但是这个算法只适用于两个进程，面对多个进程，Lamport 提出了 Bakery Algorithm（面包房算法）。

核心思想就是每个进程在请求进入临界区时，都会获得一个“时间戳”（即编号），然后按照这个编号排序执行。

int number[n];   // 每个进程的“票号”，初始为 0
bool choosing[n]; // 是否正在选号，防止并发修改

对于进程 \(P_i\) 来说

do { 
    choosing[i] = true;
    number[i] = max(number[0], number[1], …, number [n – 1])+1;
    choosing[i] = false;
    for (j = 0; j < n; j++) 
    { 
        while (choosing[j]) ; 
        while ((number[j] != 0) && (number[j],j) < (number[i],i)) ;
    }
    critical section
    number[i] = 0;
    remainder section
} while (1);

5.4 Synchronization Hardware

通过硬件支持来实现进程间的互斥访问，解决临界区问题。硬件方案比纯软件方法更高效、可靠，是现代操作系统的基础。

在多进程/多线程环境中，仅靠软件算法（如 Peterson 算法）存在局限性：

• 需要复杂的逻辑
• 存在忙等待（busy-waiting）
• 可扩展性差

因此，现代计算机系统提供了专门的硬件指令，确保关键操作的原子性。

对于单处理器来说，可以在一个进程进入临界区时，关闭 CPU 的中断，防止其他进程被调度执行。这样就很自然地满足了互斥，但是这个方法显然不适用于多核系统，因为关闭一个 CPU 的中断，其他 CPU 仍然可以运行其他进程，同时这个方法效率比较低，长时间禁用中断会影响系统响应性和实时性。

对于多处理器来说，核心的解决方法是提供 原子硬件指令，保证其执行过程中不会被中断，从而实现对共享变量的原子操作。

常见的原子指令有

• Test-and-Set（TAS）：测试内存字并设置值（读取后立即写入）
• Compare-and-Swap（CAS）：比较两个值是否相等，若相等则交换内容

---

TAS 执行以下操作

bool TS(boolean *lock) {
    bool old_value = *lock;   // 读取原值
    *lock = true;             // 设置为 true（上锁）
    return old_value;           // 返回旧值
}

利用这个操作完成互斥，只有一个进程可以进入到临界区

Shared data: 
    boolean lock = false;

while(1) {
    while (TS(&lock)) ;
        critical section
    lock = false;
    remainder section
};

---

CAS 是一个比较操作

void Swap (boolean *a, boolean *b)
{
    boolean temp = *a;
    *a = *b;
    *b = temp:
}

Shared data (initialized to false):

boolean lock;

进程 \(P_i\)

while(1) {
    key = TRUE;
    while (key == TRUE) 
        Swap(&lock , &key);
    critical section
    lock = false;
    remainder section
}

---

硬件方法的优点

• 适用于任意数目的进程，在单处理器或多处理器上

• 简单，容易验证其正确性

• 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量

硬件方法的缺点

• 等待要耗费CPU时间，不能实现"让权等待"

• 可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上

• 可能死锁：单CPU情况下, \(P_1\) 执行特殊指令(swap)进入临界区，这时拥有更高优先级 \(P_2\) 执行并中断\(P_1\), 如果 \(P_2\) 又要使用 \(P_1\) 占用的资源，按照资源分配规则拒绝 \(P_2\) 对资源的要求，陷入忙等循环。然后 \(P_1\) 也得不到CPU，因为 \(P_1\) 比 \(P_2\) 优先级低。【\(P_2\) 以为 \(P_1\) 占用，实际上 \(P_1\) 已被抢占】

为解决上述问题，我们进行改进

定义共享变量

boolean waiting[n];  // 排队队列，表示每个进程是否正在等待进入临界区
boolean lock;        // 锁变量，初始为 false

for (int i = 0; i < n; i++) {
    waiting[i] = false;
}
lock = false;

对于进程 \(P_i\)

while (1) {
    waiting[i] = true;                    // ① 表达“我想进”的意愿
    key = true;                           // ② 初始化 key
    while (waiting[i] && key)             // ③ 忙等：直到我拿到锁
        key = test_and_set(&lock);        // ④ 尝试获取锁
    waiting[i] = false;                   // ⑤ 我拿到了锁，不再等待
    critical_section();                   // ⑥ 执行临界区
    j = (i + 1) % n;                      // ⑦ 下一个候选进程
    while (j != i && !waiting[j])         // ⑧ 找到下一个正在等待的进程
        j = (j + 1) % n;
    if (j == i)                           // ⑨ 如果没有其他进程在等待
        lock = false;                     //   释放锁
    else                                  // ⑩ 否则，让下一个进程准备进入
        waiting[j] = false;               //   标记它为“已准备好”
    remainder_section();                  // ⑪ 剩余区
}

自旋锁

当一个进程欲访问已被其他进程锁定的资源时，进程循环检测该锁是否被释放，这种技术称为自旋锁（spin lock）。

5.5 Semaphores

1965年，Dijkstra 提出了“信号量”（Semaphore）机制。它最初是为了解决多进程共享资源时的互斥访问问题。经过长期发展，信号量从简单的整型变量演变为复杂的记录型信号量和信号集。现在已成为现代操作系统中实现进程同步与互斥的基础原语之一。

• 整型信号量（integer semaphore）
• 记录型信号量（record semaphore）
• AND型信号量，信号量集
• 二值信号量(binary semaphore)

---

信号量机制的两个核心操作是 wait() 操作（也称 P 操作）和 signal() 操作（也称 V 操作）

在整型信号量下，两个操作如下

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // 加入等待队列，阻塞当前进程
        block_process();
    }
}

• 表示“请求一个资源”或“等待某个事件发生”
• 如果资源可用（S > 0），则减 1 并继续执行
• 如果资源不可用（S = 0），则将进程加入等待队列并阻塞

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // 唤醒一个等待的进程
        wakeup_process();
    }
}

• 表示“释放一个资源”或“通知事件完成”
• 将信号量加 1
• 如果有进程在等待，则唤醒其中一个

对于信号量来说，不能有两个进程同时执行 wait() 或 signal() 操作在同一个信号量上。否则产生的结果跟之前一样会导致结果不可预测

为了防止并发访问，我们可以把 wait() 和 signal() 的代码本身当作一个临界区来保护。

在实现 wait() 和 signal() 时，我们需要用 test_and_set() 或其他原子指令来获取锁

• 如果这个锁被占用，调用者会进入 while 循环不断重试 → 忙等待
• 所以这也不是一个好的方案

---

于是我们引入记录型信号量，引入等待队列，避免进程在等待资源时进行“忙等待”（busy waiting）

typedef struct {
    int value;                   // 当前信号量值（可用资源数）
    struct process *list;        // 指向等待该信号量的进程链表头
} semaphore;

wait() 操作如下

void wait(semaphore *S) {
    // 原子地将 S->value 减 1
    S->value--;

    if (S->value < 0) {
        // 资源不足，将当前进程加入等待队列
        add_current_process_to(S->list);
        block_current_process();  // 阻塞当前进程
    }
}

signal() 操作如下

void signal(semaphore *S) {
    // 原子地将 S->value 加 1
    S->value++;

    if (S->value <= 0) {
        // 有进程在等待，唤醒其中一个
        process *p = remove_first_from(S->list);
        wakeup(p);  // 唤醒该进程
    }
}

信号量的物理含义

• S.value >0 表示有S.value个资源可用；

• S.value=0 表示无资源可用或表示不允许进程再进入临界区；

• S.value<0 则|S.value|表示在等待队列中进程的个数或表示等待进入临界区的进程个数。

wait、signal操作必须成对出现，有一个wait操作就一定有一个signal操作。一般情况下：当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现。

如果两个wait操作相邻，那么它们的顺序至关重要，而两个相邻的signal操作的顺序无关紧要。一个同步wait操作与一个互斥wait操作在一起时，同步wait操作在互斥wait操作前。

Example

wait(mutex);
wait(empty);  // 假设 empty=0，则会阻塞

如果 empty == 0，进程会被阻塞，但此时它已经持有 mutex，其他进程无法获取 mutex 来释放 empty → 死锁，应该为

wait(empty);
wait(mutex);

先申请资源（empty），再上锁 → 即使被阻塞，也不会持有锁，不会造成死锁。

信号量不仅可以用于互斥，还可以实现进程间的顺序控制——即“让一个进程在另一个进程完成某操作后才执行”。

比如说定义一个信号量 flag，初始值为 0

1. \(P_i\) 执行完 A 后，调用 signal(flag) → 表示“A 已完成”
2. \(P_j\) 在执行 B 前，先调用 wait(flag) → 等待“A 完成”的通知
3. 只有当 flag 被 signal() 过，\(P_j\) 才能继续执行 B

P_i                     P_j
...                     ...
A                       wait(flag)
signal(flag)            B
...                     ...

---

并发系统需要注意这三个问题：死锁，饥饿，优先级反转

死锁是指两个或多个进程无限期地等待某个事件，而这个事件只能由其中一个等待的进程来触发。

Example

• 有两个信号量：S 和 Q，都初始化为 1。
• 两个进程：P₀ 和 P₁

P₀:                    P₁:
wait(S);               wait(Q);
wait(Q);               wait(S);
...                    ...
signal(S);             signal(Q);
signal(Q);             signal(S);

这时候就会出现死锁现象

饥饿是指一个进程长期得不到所需的资源，即使它已经准备好运行，也可能永远无法执行。

当一个低优先级进程持有一个关键资源，而一个高优先级进程需要该资源时，导致高优先级进程被阻塞，从而出现“优先级反转”。

信号量 S 的值为 S.value，S.value > 0、S.value = 0、S.value < 0 的含义是什么？

S.value	含义	说明
S.value > 0	表示有可用资源	当前可立即分配给请求进程，无需等待
S.value = 0	表示无可用资源，但没有进程在等待	下一个请求者将被阻塞
S.value < 0	表示有进程正在等待资源	其绝对值等于等待队列中的进程数量

5.6 经典进程同步问题

5.6.1 Bounded-Buffer Problem

生产者-消费者问题是最著名的同步问题，它描述一组生产者（\(P_1 ……P_m\)）向一组消费者（\(C_1……C_q\)）提供消息。它们共享一个有限缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息。

\(N\) buffers, each can hold one item

• Semaphore mutex initialized to the value 1，互斥锁，用于保护对缓冲区的访问
• Semaphore full initialized to the value 0，表示“缓冲区中已填满的槽的数量”
• Semaphore empty initialized to the value N，表示“缓冲区中空闲槽的数量”

The structure of the Producer Process

do { 
    …
    produce an item in nextp
    …
    wait(empty);
    wait(mutex);
    …
    add nextp to buffer
    …
    signal(mutex);
    signal(full);
} while (1);

The structure of Consumer Process

do { 
    wait(full);
    wait(mutex);
    …
    remove an item from buffer to nextc
    …
    signal(mutex);
    signal(empty);
    …
    consume the item in nextc
    …
} while (1);

5.6.2 Readers-Writers Problem

A data set is shared among a number of concurrent processes

• Readers （读者）– only read the data set; they do not perform any updates
• Writers （写者） – can both read and write

几个读者可以同时读些数据集，而不需要互斥。一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。

这里有两个版本的问题：

第一个读者-写者问题（First Readers-Writers Problem）

• 允许多个读者同时读（并发读）
• 只允许一个写者写，且写时不能有其他进程访问
• 缺点：写者可能饥饿（starve），因为只要不断有读者到来，写者就一直被阻塞，永远无法获得访问权

第二个读者-写者问题（Second Readers-Writers Problem）

• 一旦有写者准备就绪，它应尽快执行写操作
• 写者优先于读者
• 缺点：读者可能饥饿（starve），如果写者频繁到来，读者会一直等待，无法读取数据

---

针对第一类读者-写者问题，共享数据为

• 数据
• 信号量 mutex 初始化为 1，用于保护readcount 的访问，防止多个读者同时修改计数器时发生竞争条件。
• 信号量 wrt 初始化为 1，用于控制写者对共享数据的独占访问。
• 整型信号量 readcount 初始化为 0，记录当前正在读取的读者数量。

Reader Process:
do {
    wait(mutex);
    readcount++;
    if (readcount == 1)
        wait(wrt);
    signal(mutex);
         …
    //reading is performed
         …
    wait(mutex);
    readcount--;
    if (readcount == 0)
        signal(wrt);
    signal(mutex)；
} while (TRUE);

Writer Process:
do {
     wait (wrt) ; 
     // writing is performed
     signal (wrt) ;
} while (TRUE);

5.6.3 Dining-Philosophers Problem

N位哲学家围坐在圆桌旁，每人需要同时拿到左右两根筷子才能吃饭，而每根筷子由相邻的两位哲学家共享，且相邻的哲学家不能同时吃饭，他们轮流在思考和吃饭之间切换。

设计的共享数据为

• 数据（哲学家的饭）
• chopstick[5] 信号量，初始化为1

对于哲学家 \(i\) 来说

do {
    wait(chopstick[i])
    wait(chopstick[(i+1) % 5])
        …
        eat
        …
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
        …
        think
        …
} while (1);

这个问题非常容易出现死锁和饥饿的情况

• 死锁：所有哲学家都拿起了左边的筷子，但都在等右边的筷子，结果谁也吃不了饭，陷入僵局。
• 饥饿：某个哲学家长期无法获得两根筷子，永远吃不上饭。

可能的解决方案有

• 最多允许4位哲学家同时饥饿，这样可以打破“所有进程同时请求资源”的条件，防止死锁。
• 只有当两只筷子都可用时才允许拿起，避免了只拿一根筷子后长时间等待另一根的情况。
• 奇数号哲学家先拿左筷，偶数号先拿右筷，这样可以打破对称性，防止所有哲学家行为一致导致死锁。
• 每个哲学家拿起第一根筷子后，如果在一定时间内拿不到第二根筷子，就放下第一根筷子，重新开始。
• Dijkstra 的状态法：把每个哲学家的状态分为三种：思考（thinking）、饥饿（hungry）、吃饭（eating），只有当一个哲学家处于“饥饿”状态且两根筷子都可用时，才能开始吃饭。否则，即使拿到了一根筷子，也不吃饭。

5.7* Monitors

信号量同步的缺点

1. 同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如wait、signal操作的次序错误、重复或遗漏）。
2. 易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；
3. 不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局。
4. 正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误。

管程（Monitor）是一种用于解决并发编程中同步问题的高级抽象机制，最早由 C. A. R. Hoare 和 Per Brinch Hansen 在 20 世纪 70 年代提出。它的核心思想是：将共享资源及其操作封装在一个模块中，并确保同一时刻最多只有一个线程能执行该模块中的代码，从而自动实现互斥访问。

一个管程通常包含：

• 局部于管程的共享变量（即受保护的数据）；
• 一组过程（或方法），用于操作这些变量；
• 一个隐式的互斥锁（mutex），保证每次只有一个线程可以进入管程；
• 条件变量（condition variables），用于线程间的等待与通知。

当多个线程试图调用管程中的某个过程时，操作系统或运行时系统会自动让它们排队，只有获得管程“所有权”的线程才能执行，其他线程必须等待。这避免了程序员手动管理锁的复杂性，降低了出错风险。

管程中的条件变量（如 wait()、signal() 或 notify()）用于协调线程行为。例如，如果某个线程发现当前无法继续执行（比如缓冲区为空），它可以调用 condition.wait()，暂时释放管程并进入等待状态；当另一个线程改变了相关状态（如向缓冲区放入数据），它可调用 condition.signal() 唤醒一个等待的线程。

管程中的多个进程进入

当一个进程 P 在管程内执行 wait() 时，它会释放管程的互斥权，进入等待状态； 当另一个进程 Q 执行 notify() 唤醒 P 时，P 被激活，但此时 Q 仍在管程中运行。

于是出现了一个问题：两个进程（P 和 Q）都处于活跃状态，该如何处理？

• Hoare 语义：P 等待，直到 Q 离开管程或下一次等待。
• Lampson & Redell 语义：Q 等待，直到 P 离开管程或下一次等待。

入口等待队列和紧急等待队列

入口等待队列(entry queue)：因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。

紧急等待队列：在管程内部，由于执行唤醒操作，可能会出现多个等待进程（已被唤醒，但由于管程的互斥进入而等待），因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。

A monitor solution to the Dining- Philosophers

monitor dp
{
    enum {thinking, hungry, eating} state[5];
    condition self[5];
    void pickup(int i) 
    void putdown(int i) 
    void test(int i) 
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

void pickup(int i) {
    state[i] = hungry;
    test[i];
    if (state[i] != eating)
        self[i].wait();
}
void putdown(int i) {
    state[i] = thinking;
    // test left and right neighbors
    test((i+4) % 5);
    test((i+1) % 5);
}

void test(int i) {
    if ( (state[(i + 4) % 5] != eating) &&
     (state[i] == hungry) &&
     (state[(i + 1) % 5] != eating)) {
        state[i] = eating;
        self[i].signal();
    }
}

Philosopher[I]:

do{ dp.pickup(I);
     eat
     dp.putdown(I);
     think
}while(1)

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！