Lecture 12: Concurrency 5

回顾：

• 并行用餐哲学家
• 读者/作者问题

哲学家进餐问题

方案三：最大化并行

需要一个更复杂的解决方案来实现最大的并行性
解决方案使用：

state[N]：每个哲学家的当前状态（THINKING， HUNGRY， EATING）

phil[N]：每个哲学家（不是forks）专用的阻塞信号量，初值为0。哲学家需要等待叉子时在此睡眠，被邻座唤醒时再 sem_post。

• 如果他/她的邻座正在吃饭，哲学家就会睡觉
• 如果邻座已经完成了同步：一个信号量/互斥锁来强制临界区的互斥（同时更新状态），则唤醒哲学家。

sync：一个信号量/互斥锁强制临界区互斥（同时更新状态）

1. 思考 → 饥饿：哲学家想吃面时，先把 state[i] = HUNGRY，然后尝试拿叉子。

2. 拿叉子条件：只有当 左右邻居都不是 EATING 时，才能把 state[i] 设为 EATING，否则就在 phi[i] 上睡眠。

3. 吃完 → 思考：吃完后把 state[i] = THINKING，并检查 左右邻居 现在是否能吃（即它们是否处于 HUNGRY 且两边都没人吃），如果可以就 sem_post 唤醒对应邻居。

4. 所有对 state[] 的读写 都必须先拿 sync 锁，保证一致性。

哲学家只有在他/她的邻座不吃东西的时候才能开始吃东西

全局数据结构

#define N 5
#define THINKING 1
#define HUNGRY 2
#define EATING 3int state[N] = {THINKING, THINKING, THINKING, THINKING, THINKING};
sem_t phil[N]; // sends philosopher to sleep
sem_t sync; // 互斥锁，保护对 state[] 的读写

哲学家主循环

void * philosopher(void * id) {int i = *((int *) id);while(1) {printf("%d is thinking\n", i);take_forks(i); // 试图拿叉子printf("%d is eating\n", i);put_forks(i); // 吃完放叉子}
}

拿叉子

void take_forks(int i)
{sem_wait(&sync);        // 进入临界区state[i] = HUNGRY;      // 宣布“我饿了”test(i);                // 检查现在能不能吃sem_post(&sync);        // 离开临界区sem_wait(&phil[i]);     // 如果不能吃，就在 phil[i] 上睡眠
}

 放叉子

void put_forks(int i)
{int left  = (i + N - 1) % N;int right = (i + 1) % N;sem_wait(&sync);        // 进入临界区state[i] = THINKING;    // 吃完，回到思考状态test(left);             // 看左邻居现在能不能吃test(right);            // 看右邻居现在能不能吃sem_post(&sync);        // 离开临界区
}

 核心辅助函数

void test(int i)
{int left  = (i + N - 1) % N;int right = (i + 1) % N;/* 只有当自己饥饿且左右邻居都不在吃时，才能开吃 */if (state[i] == HUNGRY &&state[left]  != EATING &&state[right] != EATING) {state[i] = EATING;sem_post(&phil[i]);   // 唤醒等待的哲学家}
}

给每位哲学家配一个“状态变量 + 专属信号量”，通过“邻居吃完后主动叫醒我”的局部唤醒策略，既保证互斥又允许不相邻的人同时吃，从而无死锁且达到最大并行度。

读者-作者问题

描述

1. 场景
   并发进程（数据库事务、文件访问、I/O 设备等）分两类：
   • 读者：读取记录（变量）——只读数据，可多线程并行；
   • 写者：写入——要写数据，必须独占访问，需要同步，不能与其他读者或写者并发。

2. 三种同步方案
   • 方案 1：朴素实现
   简单粗暴地加一把大锁：任何时候只允许一个读者或一个写者访问，并行度极低。
   • 方案 2：读者优先
   只要没有写者在写，新来的读者都可以立即读；写者可能长期挨饿。
   • 方案 3：写者优先
   一旦有写者请求，就尽快让它写；读者可能长期挨饿。

→ 核心权衡：提高并行度 vs. 避免饥饿，不同方案侧重不同。

方案 1：无并行

void * reader(void * arg) {while(1) {pthread_mutex_lock(&sync);printf("reading record\n");pthread_mutex_unlock(&sync);}
}

void * writer(void * writer) {while(1) {pthread_mutex_lock(&sync);printf("writing\n");pthread_mutex_unlock(&sync);}
}

• 不管读者还是写者，都先对同一把互斥锁 sync 加锁
  pthread_mutex_lock(&sync)

• 拿到锁以后才能 读 或 写，然后立即释放锁
  pthread_mutex_unlock(&sync)

• 结果：
  任意时刻只有 一个线程（读者或写者）在访问数据，完全没有并行读的优势，并行度最低，但实现最简单、绝不会出现数据竞争。

方案 2：读者优先

• 读者可以并行：只要 iReadCount > 0，新读者无需再抢 rwSync，直接读即可。

• 写者可能饿死：如果读者源源不断，写者将长期拿不到 rwSync。

方案2的正确实现需要：

（1）iReadCount：一个跟踪读者数量的整数

• 如果iReadCount > 0: writer被阻塞（sem_wait(rwSync)）
• 如果iReadCount == 0：写入器被释放（sem_post(rwSync)）
• 如果已经写了，读者必须等待

（2）sync: 对 iReadCount 本身的互斥锁（初值 1），防止多个读者并发修改计数。

（3）rwSync：写者互斥锁（初值 1）。同步读者和写者的信号量，由第一个/最后一个读者设置。只要 iReadCount > 0 或 正在写，写者就得在 rwSync 上阻塞。

① 读者进入

sem_wait(&sync);      // 锁住计数器
iReadCount++;         // 又来一个读者
if (iReadCount == 1)  // 是第一个读者？sem_wait(&rwSync);// 把写者挡在外面
sem_post(&sync);      // 释放计数器printf("reading record");

② 读者离开

sem_wait(&sync);      // 再次锁住计数器
iReadCount--;
if (iReadCount == 0)  // 最后一个读者？sem_post(&rwSync);// 放行一个等待的写者
sem_post(&sync);

③ 写者

sem_wait(&rwSync);    // 等所有读者和别的写者退出
printf("writing");
sem_post(&rwSync);    // 写完放行

方案3：写者优先

它用了 4 个信号量 / 计数器 来确保：

• 一旦有写者到达，后续读者必须排队，正在读的读者全部结束后立即让写者执行；

• 写者之间互斥；

• 写者完成后，读者再继续。

优先考虑写作者和使用者：（以下初值均为1）

• 整数iReadCount和iWriteCount来跟踪读/写的数量。
• 互斥锁sRead和sWrite来同步读/写的临界区。
• 信号量sReadTry在有写入器等待时停止读取器。读者“入场券”。写者到来后把它降为 0，阻塞新读者。
• 信号量sResource用于同步读/写资源。真正保护数据区的锁。读者或写者要访问数据必须先拿到它。

① 读者

while (1) {sem_wait(&sReadTry);   // ① 先排队拿“读者入场券”sem_wait(&sRead);      // ② 锁计数器iReadCount++;if (iReadCount == 1)   // ③ 第一个读者抢数据锁sem_wait(&sResource);sem_post(&sRead);      // ④ 解锁计数器sem_post(&sReadTry);   // ⑤ 放行下一位读者printf("reading\n");   // ⑥ 真正读数据sem_wait(&sRead);      // ⑦ 读完，更新计数器iReadCount--;if (iReadCount == 0)   // ⑧ 最后一个读者释放数据锁sem_post(&sResource);sem_post(&sRead);
}

② 写者

while (1) {sem_wait(&sWrite);     // ① 锁写者计数器iwriteCount++;if (iwriteCount == 1)  // ② 第一位写者关闭“读者入场券”sem_wait(&sReadTry);sem_post(&sWrite);sem_wait(&sResource);  // ③ 真正拿到数据锁printf("writing\n");   // ④ 写数据sem_post(&sResource);sem_wait(&sWrite);     // ⑤ 写完，更新计数器iwriteCount--;if (iwriteCount == 0)  // ⑥ 最后一位写者重新开放“读者入场券”sem_post(&sReadTry);sem_post(&sWrite);
}

写者一旦到达，先把 sReadTry 关闸，新读者必须排队；等所有正在读的读者走光后，写者立即拿到 sResource；写者全部完成后重新开闸，读者才能继续。从而实现了 写者优先，读者可能饥饿。

约束:

• 每个人都乐于走进关灯的房间。
• 读者和作家不喜欢对方。
• 读者很乐意进入一个亮着绿灯而不是黄灯的房间。
• 作家们很乐意进入一个黄灯而不是绿灯亮着的房间。
• 只有读者可以使用底部出口