Supplementary materials for OS Chapter 6

## Three requirements on critical section problem solutions

### Definetion

- Mutual Exclusion
- Progress
- Bounded Waiting

### Explaintion for the example on the slide 11

#### Mutual Exclusion: **Yes**

The solution enforces mutual exclusion through the `turn` variable. Here's why:

- If process $ P_i $ is in the critical section, it must have passed its entry condition (`while (turn == j)`), meaning $ \text{turn} = i $ at that moment.
- While $ P_i $ is in the critical section, $ \text{turn} $ remains $ i $ (since $ P_i $ only updates $ \text{turn} $ to $ j $ in its exit section).
- Process $ P_j $, attempting to enter, checks $ \text{turn} == i $ in its entry loop. Since $ \text{turn} = i $, $ P_j $ is forced to wait until $ P_i $ exits and sets $ \text{turn} = j $.
- By symmetry, if $ P_j $ is in the critical section, $ P_i $ is blocked in its entry loop. Thus, only one process can be in the critical section at a time.

#### Progress: **No**

Progress fails because a process may be indefinitely blocked by a non-responding process. For example:

- Suppose $ P_i $ has exited the critical section and set $ \text{turn} = j $. Now $ P_j $ can enter, and after exiting, it sets $ \text{turn} = i $.
- If $ P_i $ is now *not interested* in the critical section (e.g., it stays in its remainder section), $ P_j $ will attempt to re-enter. However, $ P_j $’s entry loop checks $ \text{turn} == i $, which is now true (since $ P_j $ set $ \text{turn} = i $ on exit).
- $ P_j $ is stuck waiting for $ \text{turn} $ to change, but $ P_i $ (not interested) never updates $ \text{turn} $. Thus, $ P_j $ cannot proceed even though the critical section is idle.

#### Bounded Waiting: **Yes**

Bounded waiting is satisfied because the `turn` variable ensures alternating access. Here’s why:

- After a process (e.g., $ P_i $) exits the critical section, it sets $ \text{turn} = j $, forcing $ P_j $ to get the next opportunity.
- When $ P_j $ exits, it sets $ \text{turn} = i $, allowing $ P_i $ to enter next.
- This alternation guarantees that no process waits forever; each process gets a turn after at most one entry by the other process.

**Summary**: The `turn` variable enforces mutual exclusion and bounded waiting by strictly alternating access. However, progress fails because a non-responding process can block others indefinitely.

## Synchronization Hardware

### Atomic operations

- Definition: Non-interruptible, the atomic hardware instruction will do the following work

1. Test memory *word*and set value

2. Swap contents of two memory *words*

- `test and set(boolean *target)` 指令会读取 `target` 变量的旧值，同时将 `target` 设置为 `true`，并返回旧值。这个读和写的操作是原子完成的。这里的 `*target` 参数，以及在互斥实现中使用到的 `lock`变量，就是被这些原子操作作用的变量。

- **Mutual Exclusion: Yes; Progress: Yes; Bounded Waiting: No**

- `compare and swap(value, expected, new_value)` 指令则是在一个原子操作中完成比较和潜在的交换：如果 `value` 的当前值等于 `expected`，则将 `value` 设置为 `new_value`；无论是否设置，都返回 `value` 的原值。这里的 `value` 参数，以及在互斥实现中使用到的 `lock` 变量，也是被原子操作作用的变量。

- **Mutual Exclusion: Yes; Progress: Yes; Bounded Waiting: No**

### 信号量实现（无忙等待）

#### 整体架构说明

这段代码描述了一种基于信号量的同步机制实现，其核心目标是避免传统信号量实现中可能出现的“忙等待（Busy waiting）”问题。忙等待是指进程/线程在获取资源（如进入临界区）时，不断地循环检查条件（如锁是否可用），这会浪费CPU资源。该实现通过引入等待队列（`list`）和相关的阻塞（`block`）、唤醒（`wakeup`）操作来解决这个问题。

#### 数据结构定义

```c
typedef struct {
    int value;
    struct process *list;
} semaphore;
```

- **`int value`**：
  - 这是信号量的核心整数值，其含义类似于传统信号量的计数值。
  - 当`value > 0`时，表示当前有`value`个可用的资源（例如，如果用于互斥场景，初始化为1，此时`value`表示是否有一个“许可”让进程进入临界区；如果用于资源池场景，`value`表示可用资源的数量）。
  - 当`value = 0`时，可能表示没有可用资源，但也没有进程在等待（具体语义可能根据上下文微调）。
  - 当`value < 0`时，其绝对值表示正在等待该信号量的进程数量（这与传统信号量的概念类似，用于记录等待队列的长度）。
 - **`struct process *list`**：
   - 这是一个指向进程结构体的指针，用于构建一个等待队列。当进程调用`block`操作（类似于传统信号量的`P`操作但此处无忙等待）时，如果资源不可用（根据`value`判断），该进程会被添加到这个队列中。队列的具体实现（如链表的类型，是单链表还是双链表等）未在这段代码中详细给出，但从`struct process *list`可以推测是一个以`struct process`为节点的链表结构，用于存储等待该信号量的进程。

#### 操作说明

- **`block`操作**：
   - 当一个进程调用`block`操作（对应于传统信号量想要获取资源的操作，类似`P`操作）时，它会检查信号量的`value`。
   - 如果`value`表明资源不可用（例如，对于互斥信号量`value`变为0或负数，对于计数信号量`value`变为负数），那么该进程会被放置到与该信号量关联的等待队列（`list`）中。这意味着进程会从运行状态切换到阻塞状态，不会占用CPU资源进行忙等待，而是等待被其他进程通过`wakeup`操作唤醒。
 - **`wakeup`操作**：
   - 当另一个进程调用`wakeup`操作（对应于传统信号量释放资源的操作，类似`V`操作）时，它会从等待队列（`list`）中移除一个进程。
   - 被移除的进程会被放置到就绪队列中，这意味着该进程可以重新参与CPU调度，再次尝试获取信号量（即再次执行类似`block`操作的逻辑，不过此时信号量的`value`可能已经改变，资源可能变得可用）。

#### 与传统信号量实现对比（以忙等待实现为例）

- **传统忙等待实现（如基于`test_and_set`的自旋锁）**：
  - 进程在获取资源（如进入临界区）时，会不断循环检查锁（类似信号量的`value`）的状态（例如`while(test_and_set(&lock)){ ; }`），这期间CPU一直在执行循环指令，造成资源浪费。
 - **此无忙等待实现**：
   - 当资源不可用时，进程通过`block`操作进入等待队列，不会占用CPU，只有当其他进程通过`wakeup`操作释放资源并唤醒等待队列中的进程时，被唤醒的进程才会重新参与CPU调度去竞争资源，避免了CPU资源的浪费。

#### 示例场景（以互斥为例）

假设我们有两个进程`P1`和`P2`竞争进入一个临界区，使用上述信号量实现：

1. **初始化**：
   - `semaphore mutex;`，并将`mutex.value`初始化为`1`（表示有一个“许可”进入临界区），`mutex.list`初始化为`NULL`（等待队列为空）。
2. **`P1`尝试进入临界区（调用类似`block`操作逻辑）**：
   - 检查`mutex.value`，此时`value = 1`，将`value`减`1`（变为`0`），`P1`进入临界区执行代码。
3. **`P2`尝试进入临界区（调用类似`block`操作逻辑）**：
   - 检查`mutex.value`，此时`value = 0`，`P2`会被添加到`mutex.list`等待队列中，进入阻塞状态。
4. **`P1`离开临界区（调用类似`wakeup`操作逻辑）**：
   - 将`mutex.value`加`1`（变为`1`），然后检查等待队列`mutex.list`（此时有`P2`），通过`wakeup`操作将`P2`从等待队列移除并放入就绪队列。`P2`之后在合适的时机（CPU调度）会再次检查`mutex.value`（此时为`1`），获取“许可”进入临界区。

这种实现方式通过等待队列和`block`/`wakeup`操作，更高效地管理了进程对共享资源的访问，避免了忙等待带来的性能开销。

### 同步经典问题

#### 1. 有界缓冲区问题（Bounded Buffer Problem）

- **问题描述**
  - 有一个固定大小的缓冲区（例如数组），生产者进程不断地生产数据并放入缓冲区，消费者进程不断地从缓冲区取出数据进行消费。缓冲区的大小是有限的（有界的），这就产生了同步需求。
  - 当缓冲区已满时，生产者进程必须等待；当缓冲区为空时，消费者进程必须等待。
- **同步需求**
  - 互斥：因为缓冲区是共享资源，在同一时刻只能有一个进程（生产者或消费者）对缓冲区进行操作（放入或取出数据），以避免数据不一致。例如，使用互斥信号量（如二元信号量）来保证对缓冲区操作的互斥性。
  - 同步：生产者和消费者之间需要协调。生产者需要知道缓冲区有空间才能放入数据（通过一个表示缓冲区空槽数量的信号量来控制），消费者需要知道缓冲区有数据才能取出（通过一个表示缓冲区数据数量的信号量来控制）。
- **示例解决方案（使用信号量）**
  - 定义三个信号量：`mutex`（互斥信号量，初始值为1），`empty`（表示缓冲区空槽数量，初始值为缓冲区大小`n`），`full`（表示缓冲区数据数量，初始值为0）。
  - 生产者进程代码：

```c
while (true) {
    // 生产数据
    item = produce_item();
    sem_wait(empty);  // 等待缓冲区有空槽
    sem_wait(mutex);  // 互斥访问缓冲区
    // 将数据放入缓冲区
    insert_item(item);
    sem_post(mutex);  // 释放互斥锁
    sem_post(full);   // 缓冲区数据数量加1
}
```

- 消费者进程代码：

```c
while (true) {
    sem_wait(full);   // 等待缓冲区有数据
    sem_wait(mutex);  // 互斥访问缓冲区
    // 从缓冲区取出数据
    item = remove_item();
    sem_post(mutex);  // 释放互斥锁
    sem_post(empty);  // 缓冲区空槽数量加1
    // 消费数据
    consume_item(item);
}
```

#### 2. 读者 - 写者问题（Readers Writers Problem）

- **问题描述**
  - 有一个共享数据对象（如文件或数据库表），有两类进程：读者进程和写者进程。读者进程只读取共享数据，写者进程会修改共享数据。
  - 要求：多个读者可以同时读取共享数据（提高并发性）；写者与其他任何进程（读者或写者）不能同时访问共享数据，即写操作是互斥的。
- **同步需求**
  - 互斥：写者与其他进程（包括读者和写者）之间需要互斥。对于读者，当有写者在写时，读者不能读；当有读者在读时，写者不能写。
  - 并发控制：允许多个读者同时读，需要一个机制来统计当前正在读的读者数量，当第一个读者开始读时，阻止写者写；当最后一个读者读完时，允许写者写。
- **示例解决方案（使用信号量）**
  - 定义信号量：`rw_mutex`（用于写者与其他进程的互斥，初始值为1），`read_count_mutex`（用于保护对读者计数`read_count`的修改，初始值为1）。
  - 定义变量：`read_count`（记录当前读者数量，初始值为0）。
  - 读者进程代码：

```c
while (true) {
    sem_wait(read_count_mutex);
    if (read_count == 0) {
        sem_wait(rw_mutex);  // 第一个读者阻止写者
    }
    read_count++;
    sem_post(read_count_mutex);
    // 读取共享数据
    read_data();
    sem_wait(read_count_mutex);
    read_count--;
    if (read_count == 0) {
        sem_post(rw_mutex);  // 最后一个读者允许写者
    }
    sem_post(read_count_mutex);
}
```

- 写者进程代码：

```c
while (true) {
    sem_wait(rw_mutex);  // 互斥访问共享数据
    // 写入共享数据
    write_data();
    sem_post(rw_mutex);
}
```

#### 3. 哲学家就餐问题（Dining Philosophers Problem）

- **问题描述**
  - 有`n`个哲学家围坐在一张圆桌旁，每个哲学家交替地进行思考和进餐。桌子上有`n`根筷子（对于`n`个哲学家，通常是`n`根筷子，每个哲学家左右各一根），哲学家只有同时拿到左右两根筷子才能进餐。
  - 要求：避免死锁（例如所有哲学家都同时拿起左边筷子，然后等待右边筷子，导致谁也无法进餐）和饥饿（某个哲学家一直拿不到筷子）。
- **同步需求**
  - 互斥：筷子是共享资源，同一根筷子不能同时被两个哲学家使用。
  - 避免死锁和饥饿：需要合理的调度策略，例如限制哲学家拿筷子的顺序（如奇数号哲学家先拿左边筷子，偶数号哲学家先拿右边筷子），或者使用资源分配算法（如银行家算法的思想简化版）来确保系统处于安全状态。
- **示例解决方案（使用信号量）**
  - 定义信号量数组`chopstick[n]`（每个元素初始值为1，表示筷子可用）。
  - 哲学家`i`（编号从0到`n - 1`）进程代码：

```c
while (true) {
    // 思考
    think();
    if (i % 2 == 0) {  // 偶数号哲学家先拿右边筷子（假设编号从0开始）
        sem_wait(chopstick[(i + 1) % n]);  // 右边筷子（环形桌子）
        sem_wait(chopstick[i]);  // 左边筷子
    } else {
        sem_wait(chopstick[i]);  // 左边筷子
        sem_wait(chopstick[(i + 1) % n]);  // 右边筷子
    }
    // 进餐
    eat();
    sem_post(chopstick[i]);
    sem_post(chopstick[(i + 1) % n]);
}
```

这些经典问题是测试同步方案的重要工具，它们涵盖了互斥、同步、并发控制以及死锁避免等多方面的需求，通过对这些问题的解决，可以深入理解操作系统中的进程同步机制。

在信号量机制中，`sem_wait`（通常也被称为`P`操作）和`sem_post`（通常也被称为`V`操作，有的资料里也会用`signal`来表示类似功能）是实现进程/线程同步与互斥的关键操作，下面详细解释它们的作用：

### `sem_wait`（`P`操作）的作用

1. **尝试获取资源（信号量所代表的抽象资源）**
   - 假设我们有一个信号量 `sem` 用于管理某种共享资源（比如有界缓冲区问题中的缓冲区空槽数量、读者 - 写者问题中的互斥访问等）。`sem_wait` 操作首先会对信号量的整数值（假设为 `value`）进行原子性的减 1 操作（`value--`）。
   - 以有界缓冲区问题为例，如果 `sem` 是表示缓冲区空槽数量的信号量（初始值为缓冲区大小 `n`），当生产者进程调用 `sem_wait(sem)` 时，就相当于它在尝试申请一个可以放入数据的空槽。
2. **根据信号量值决定进程状态**
   - **资源可用情况（`value >= 0`）**：
     - 如果减 1 之后 `value >= 0`，这意味着当前进程成功获取到了资源。例如在有界缓冲区问题中，说明缓冲区还有剩余空槽，生产者可以继续执行后续将数据放入缓冲区的操作；在互斥场景（如二元信号量，初始值为 1）中，说明获取到了进入临界区（互斥访问区域）的许可，进程可以进入临界区执行相关代码。
   - **资源不可用情况（`value < 0`）**：
     - 当减 1 后 `value < 0`，表示当前没有可用资源了。此时，根据信号量的实现机制（比如基于等待队列和条件变量的实现），调用 `sem_wait` 的进程会被阻塞，放入与该信号量相关联的等待队列中。例如在有界缓冲区问题中，如果缓冲区已满（`value` 减到小于 0），生产者进程就会被阻塞，直到有消费者取出数据（通过 `sem_post` 操作增加 `value`）来唤醒它。

### `sem_post`（`V`操作，类似 `signal`）的作用

1. **释放资源（归还信号量所代表的抽象资源）**
   - `sem_post` 操作会对信号量的 `value` 进行原子性的加 1 操作（`value++`）。还是以有界缓冲区问题为例，如果 `sem` 是表示缓冲区数据数量的信号量（消费者取出数据前它的值会因生产者放入数据而增加），当消费者取出一个数据后调用 `sem_post(sem)`，就相当于它归还了一个“数据资源”，让信号量所代表的资源数量增加。
2. **检查并唤醒等待进程（如果有）**
   - 在 `value++` 之后，会检查 `value` 的值。如果 `value <= 0`（这意味着在 `value++` 之前 `value` 是小于等于 -1 的，也就是有进程因为 `sem_wait` 操作被阻塞在等待队列中），那么就会根据信号量的实现（比如通过条件变量）唤醒等待队列中的一个进程。
   - 例如在有界缓冲区问题中，当消费者取出数据使得表示缓冲区空槽数量的信号量 `value` 增加（通过对相应信号量的 `sem_post` 操作），如果此时该信号量 `value` 从 -1 变为 0（假设有一个生产者之前因为缓冲区满被阻塞），那么就会唤醒一个等待的生产者进程，让它可以继续尝试放入数据。

### 结合具体问题理解

- **有界缓冲区问题**：
  - 生产者通过 `sem_wait(empty)`（`empty` 是表示空槽数量的信号量）申请空槽资源，若成功（`empty` 的 `value` 减 1 后 >=0）就放入数据，然后通过 `sem_post(full)`（`full` 是表示数据数量的信号量）释放“数据资源”，可能唤醒等待的消费者；消费者通过 `sem_wait(full)` 申请数据资源，成功后取出数据，再通过 `sem_post(empty)` 释放空槽资源，可能唤醒等待的生产者。
 - **读者 - 写者问题**：
   - 读者通过一系列 `sem_wait` 操作（对 `read_count_mutex` 和根据情况对 `rw_mutex`）来协调获取读的许可（保证写者不干扰读，且多个读者能并发读）；写者通过 `sem_wait(rw_mutex)` 申请写的互斥许可（保证写操作的互斥性），完成写操作后通过 `sem_post(rw_mutex)` 释放许可，可能唤醒等待的读者或写者。
 - **哲学家就餐问题**：
   - 哲学家通过 `sem_wait` 操作申请筷子资源（信号量表示筷子是否可用），拿到筷子（`sem_wait` 成功，对应信号量 `value` 减 1 后 >=0）就可以进餐，吃完后通过 `sem_post` 释放筷子资源（对应信号量 `value` 加 1），如果有其他哲学家在等待这双筷子（信号量 `value` 加 1 后 <=0），就会唤醒等待的哲学家。

简单来说，`sem_wait` 像是“请求进入/获取资源”，如果资源不够就等待；`sem_post` 像是“离开/释放资源”，并且看看有没有等待的“小伙伴”（进程/线程）可以唤醒让它们去试试获取资源。它们相互配合实现了对共享资源的有序访问和进程间的同步互斥。

## Problem with semaphore

### Deadlock and Starvation

#### I. Analysis of Code Example

```c
// Assume S and Q are two semaphores initialized to 1
// Process P0
wait(S);
wait(Q); 
... 
signal(Q);
signal(S); 
// Process P1
wait(Q);
wait(S);
...
signal(S);
signal(Q);
```

#### II. Deadlock

1. Definition of Deadlock
   - Deadlock refers to **a state in a set of processes where each process is waiting for an event that can only be triggered by other processes in the same set (usually waiting to acquire resources held by other processes), resulting in all processes being unable to proceed.**
2. Possibility of Deadlock in this Example
   - Suppose process `P0` executes `wait(S)` (at this time, the value of `S` becomes 0), and then process `P1` executes `wait(Q)` (the value of `Q` becomes 0).
   - Next, `P0` tries to execute `wait(Q)`, but `Q` has been occupied by `P1` (the value of `Q` is 0, and `P0` will be blocked); at the same time, `P1` tries to execute `wait(S)`, but `S` has been occupied by `P0` (the value of `S` is 0, and `P1` will also be blocked).
   - In this way, a circular waiting situation is formed: `P0` is waiting for `P1` to release `Q`, and `P1` is waiting for `P0` to release `S`. Neither of the two processes can continue execution, leading to deadlock.

#### III. Starvation

1. Definition of Starvation
   - Starvation means that **a process cannot obtain the resources required for execution for a long time (theoretically, it may be indefinitely) due to other processes constantly occupying resources or always obtaining resources preferentially, etc., and thus cannot progress.**
2. Possibility of Starvation in this Example (Combined with Semaphore Queue)
   - Assume that there are multiple processes (not just `P0` and `P1`) competing for the `S` and `Q` semaphores.
   - For example, each time a new process acquires the `S` or `Q` semaphore first, while a specific process (such as `P0`) is always waiting in the semaphore queue. Due to the order of `wait` and `signal` operations of the semaphore and the uncertainty of process scheduling, if other processes keep acquiring and releasing the semaphore, and `P0` is always at the back of the semaphore queue (such as the queue waiting for `S` or `Q`), and new processes keep inserting in front (after acquiring the semaphore and then releasing it, resulting in queue updates), then `P0` may not be removed from the semaphore queue for a long time (that is, it cannot obtain the semaphore to continue execution), thus falling into a starvation state.

#### IV. Priority Inversion (Potentially Related in this Example)

1. Definition of Priority Inversion
   - **Priority inversion is a scheduling problem that occurs when a low - priority process holds a lock (or resource, here the resource represented by the semaphore can be analogized) required by a high - priority process.** The high - priority process will be blocked waiting for the low - priority process to release the resource. During this process, a medium - priority process may preempt the CPU time, making it impossible for the low - priority process to release the resource in a timely manner, further prolonging the waiting time of the high - priority process.
2. Potential Connection between this Example and Priority Inversion (Assume there is a Priority Mechanism)
   - Suppose `P0` is a high - priority process and `P1` is a low - priority process.
   - `P1` first executes `wait(Q)` (acquires the `Q` semaphore), then `P0` tries to execute `wait(S)` (successfully acquires the `S` semaphore because initially `S = 1`), and then when `P0` executes `wait(Q)`, it will be blocked (because `Q` is held by `P1`).
   - At this time, if there is a medium - priority process in the system, it may preempt the CPU time, making it impossible for `P1` to execute the subsequent `signal` operation to release the `Q` semaphore in a timely manner. In this way, `P0` (the high - priority process) will be blocked for a long time because `P1` (the low - priority process) holds the `Q` semaphore, and a situation similar to priority inversion occurs (the execution of the high - priority process is hindered by the low - priority process, and may be further delayed due to the interference of the medium - priority process).

### Summary

The above code example shows that improper order of semaphore operations (the acquisition order of semaphores by two processes forms a circular waiting condition) may lead to deadlock; at the same time, based on the uncertainty of the semaphore waiting queue and process scheduling, there is a possibility of process starvation; and after introducing the concept of process priority, the problem of priority inversion may occur. These problems reflect that in concurrent programming (especially when using semaphores for process/thread synchronization), it is necessary to carefully design the synchronization mechanism and resource acquisition order to avoid these unfavorable situations. Some strategies can be used to solve these problems, such as:

- **Deadlock Prevention**: Break the necessary conditions for deadlock (mutual exclusion, hold - and - wait, non - preemption, circular wait). For example, adopt the resource sequential allocation method (number the semaphores or resources, and processes can only acquire them in ascending order of numbers) to break the circular wait condition.
- **Starvation Avoidance**: Adopt fair scheduling algorithms (such as the first - come - first - served semaphore queue scheduling strategy) or combine mechanisms such as aging (gradually increasing the process priority as the waiting time increases) in priority scheduling.
- **Solution to Priority Inversion**: Use techniques such as priority inheritance (when a low - priority process holds a resource required by a high - priority process, the priority of the low - priority process is raised to the same as that of the high - priority process until the resource is released).

## Monitor

### Definition

**A high-level abstraction that provides a convenient and effective mechanism for process synchronization**

- *Abstract data type*, internal variables only accessible via procedures
- Only **one process** may be active within the monitor at a time
- Can utilize **condition** variables to suspend or resume processes

### Pseudocode

```
monitor BufferMonitor {
    item buffer[5];
    int count = 0;             // 当前缓冲区中项目数量
    condition notFull;         // 条件变量：缓冲区不满
    condition notEmpty;        // 条件变量：缓冲区不空

procedure insert(item x) {
        if (count == 5)
            wait(notFull);     // 等待缓冲区有空位
        buffer[count] = x;     // 插入数据
        count++;
        signal(notEmpty);      // 通知消费者：有数据可取了
    }

procedure remove() returns item {
        if (count == 0)
            wait(notEmpty);    // 等待缓冲区有数据
        item x = buffer[count - 1]; // 取出最后一个数据
        count--;
        signal(notFull);       // 通知生产者：有空位了
        return x;
    }
}
```

生产者和消费者如何使用这个 Monitor:

```
process Producer {
    loop {
        item i = produce_item();
        BufferMonitor.insert(i);
    }
}

process Consumer {
    loop {
        item i = BufferMonitor.remove();
        consume_item(i);
    }
}
```

## Three requirements on critical section problem solutions

### Definetion

- Mutual Exclusion
- Progress
- Bounded Waiting

### Explaintion for the example on the slide 11

#### Mutual Exclusion: **Yes**

The solution enforces mutual exclusion through the `turn` variable. Here's why:

#### Progress: **No**

Progress fails because a process may be indefinitely blocked by a non-responding process. For example:

#### Bounded Waiting: **Yes**

Bounded waiting is satisfied because the `turn` variable ensures alternating access. Here’s why:

**Summary**: The `turn` variable enforces mutual exclusion and bounded waiting by strictly alternating access. However, progress fails because a non-responding process can block others indefinitely.

## Synchronization Hardware

### Atomic operations

- Definition: Non-interruptible, the atomic hardware instruction will do the following work

1. Test memory *word*and set value

2. Swap contents of two memory *words*

- **Mutual Exclusion: Yes; Progress: Yes; Bounded Waiting: No**

### 信号量实现（无忙等待）

#### 整体架构说明

#### 数据结构定义

```c
typedef struct {
    int value;
    struct process *list;
} semaphore;
```

#### 操作说明

#### 与传统信号量实现对比（以忙等待实现为例）

#### 示例场景（以互斥为例）

假设我们有两个进程`P1`和`P2`竞争进入一个临界区，使用上述信号量实现：

这种实现方式通过等待队列和`block`/`wakeup`操作，更高效地管理了进程对共享资源的访问，避免了忙等待带来的性能开销。

### 同步经典问题

#### 1. 有界缓冲区问题（Bounded Buffer Problem）

- 消费者进程代码：

#### 2. 读者 - 写者问题（Readers Writers Problem）

- 写者进程代码：

```c
while (true) {
    sem_wait(rw_mutex);  // 互斥访问共享数据
    // 写入共享数据
    write_data();
    sem_post(rw_mutex);
}
```

#### 3. 哲学家就餐问题（Dining Philosophers Problem）

### `sem_wait`（`P`操作）的作用

### `sem_post`（`V`操作，类似 `signal`）的作用

### 结合具体问题理解

## Problem with semaphore

### Deadlock and Starvation

#### I. Analysis of Code Example

```c
// Assume S and Q are two semaphores initialized to 1
// Process P0
wait(S);
wait(Q); 
... 
signal(Q);
signal(S); 
// Process P1
wait(Q);
wait(S);
...
signal(S);
signal(Q);
```

#### II. Deadlock

#### III. Starvation

#### IV. Priority Inversion (Potentially Related in this Example)

### Summary

## Monitor

### Definition

**A high-level abstraction that provides a convenient and effective mechanism for process synchronization**

### Pseudocode

生产者和消费者如何使用这个 Monitor:

```
process Producer {
    loop {
        item i = produce_item();
        BufferMonitor.insert(i);
    }
}

process Consumer {
    loop {
        item i = BufferMonitor.remove();
        consume_item(i);
    }
}
```

最后修改：2025 年 05 月 25 日