[CS:APP 3e] 关于对 第 12 章 读/写者的一点思考和题解 (作业 12.19,12.20,12.21)

CSAPP-3e 并发和读/写者 (作业 12.19,12.20,12.21)

前言

最近刚学完 Linux 的进程部分, 接下来就是研究并发了. 正好, 去年 12 月到今年 1 月份那会, 我浅浅学了 CS:APP 的第 12 章。
但是, 当时因为我出了一点事情(主要是严重感冒+一些杂七杂八的事情), 所以没有好好研究, 粗略理解了一下概念就过去了, 习题也没好好做.
现在, 我重新复习了一下这一章, 并且重做了一下这些题目. 先从读/写者模型开始吧.
1. 什么是读/写者模型?

想象一张很大的白纸, 我们可以往白纸上写字, 擦掉字, 也可以用眼睛在白纸上看别人写的字然后记住.
我们把往白纸上写字的人叫做写者, 把记住别人所写的字的人叫做读者.
在计算这个大系统中, 也有类似的场景. 如 CS:APP 中所讲, 内存其实就是白纸, 负责从资源中读取的进程叫做读者, 而负责往资源中写数据的进程叫做写者.
但是, 要是读者和写者不按照一定的规律来的话, 那整个系统就会乱套了. 所以, 为了保证顺序, 操作系统引入了信号量, 用来保证读写的操作是原子操作. 这部分在 CS:APP 的 12.5 节, 就不多讲了.
2. 读/写者的实现

为了实现上述的代码, 我们来写一下读/写者的实现逻辑:

1. sem_t w;
2. void reader() {
3.     P(&w);
4.     //Read
5.     V(&w);
6. }
8. void writer() {
9.     P(&w);
10.     //Write
11.     V(&w);
12. }

复制代码

由此可见, 给 reader 和 writer 都加上一个 w 的互斥锁后, 下面的这段读/写代码就能实现原子操作了. 但是, 这样又带来了一个问题--太慢!
你想啊, 这样子会导致读写操作完全串行, 等于把多任务变成了单任务了, 这已经不是并发了. 这怎么行?
那你可能会说, 那我把读者的锁去掉, 行不行? 反正读者不改数据. 那接下来看一个例子---

1. typedef struct {
2.     int a;
3.     int b;
4. } obj_t;
6. static volatile obj_t o;
7. /**
8. * 假设 o = {.a = 1, .b = 2};
9. */
10. sem_t w;
12. void reader() {
13.     obj_t o2 = o;
15.     /**
16.      * 这段代码反汇编后重新翻译, 大概是这样的:
17.      * o2.a = o.a;
18.      * o2.b = o.b;
19.      */
20.     //Operate
21. }
23. void writer(obj_t o2) {
24.     P(&w);
25.     o = o2; //同上
26.     V(&w);
27. }

复制代码

那我们来验证一下, 假设 writer 函数写入一个数据如下:

1. obj_t o3 = {
2.     .a = 3;
3.     .b = 4;
4. };

复制代码

有如下表格:
时刻谁在执行?执行的指令数据1writerP(&mutex)-2readero2.a = o.ao2.a = 13writero.a = o2.ao.a = 34writero.b = o2.bo.b = 45readero2.b = o.bo2.b = 46writerV(&mutex)-最终 reader 读取到的结果:

1. o2 = {
2.     .a = 1;
3.     .b = 4;
4. }

复制代码

这缝合怪可不是我们想要的啊! 也就是说, 这种方案, 可能会导致数据的残缺! 那怎么办? CS:APP 给我们提供了一段既可以加速, 又保证数据安全的示例代码 ---
2. 对于图 12.26 代码的一点研究

先摆上这段代码, 它位于 CSAPP 的图 12.26:

1. int readcnt; // 刚开始=0
2. sem_t mutex, w; // 刚开始全部都为1
4. void reader(void) {
5.     while(1) {
6.         P(&mutex);
7.         readcnt++;
8.         if(readcnt == 1) {
9.             P(&w);
10.         }
11.         V(&mutex);
13.         // 读取操作
15.         P(&mutex);
16.         readcnt--;
17.         if(readcnt == 0) {
18.             V(&w);
19.         }
20.         V(&mutex);
21.     }
22. }
24. void writer(void) {
25.     while(1) {
26.         P(&w);
27.         // 写入操作
28.         V(&w);
29.     }
30. }

复制代码

很明显, 这段代码相对于上面的示例代码, 有了如下改动:

• 读写者都有一个互斥锁 w 保护着, 保证数据在写的同时不会被读取, 数据在读取的时候不会被写入.
  
• 增加了一个变量 readcnt, 用来记录此时此刻读者的数量.
  
• 为了保证变量 readcnt 原子性, 让它不受并发的影响, 新增了一个 mutex 互斥锁用来保护它.
  
• 当 readcnt == 1 的时候, 代表有读者在读了, 第一个读者获取了 w.
  
• 一旦有一个读者获取了锁, 其他读者都可以直接读数据, 不用再受 w 的约束了, 也就是说, 它真正实现了并发.
  
• 当写者获取锁之后, 由于第一个读者卡在了锁 &w 的获取, 其他多余的读者都卡在了 mutex 的锁的获取, 所以此时读者不能读取数据.
  

这相当于是上述两个方案的结合体, 也就是说, 它既能保证读者的并发, 也能保证数据的安全.
但是, 随之而来的又有一些问题:

• 假设写者来的时候, 读者正在读取数据, 然后读取数据的时候又有读者来, readcnt++, 这样下去的话, 写者就没机会执行了, 这咋整?
  
• 这种方案, 虽然读者的优先级比写者高, 但是其实这种优先级很弱, 因为写者执行了 V(&w) 后, 可能立马又绕回到 while 开头了, 从而导致
  

但是, 很明显, 这段代码也有一点缺陷:

• 这段代码中, 读者的优先级比写者高, 因为就算写者先来, 只要读者在读数据, 写者永远都没机会执行, 导致写者饥饿.
  
• (习题 12.10) 这段代码中, 读者的优先级虽然比写者高, 但也只是高一点. 对于锁 w 的操作, 读者和写者优先级相同, 万一有一堆写者, 读者很少, 那么读者就不能保证这个优先级了, 写者执行完 V(&w) 后, 下一个 P(&w) 照样大概率是写者, 导致读者饥饿.
  

那么, 接下来我们要做一些改动, 就是下面的几道题目:
3. 课后作业的题解

3.1 作业 12.19

这道题可以看作是 习题12.10 的延续:

翻译成人话就是: 写者执行完 V(&w) 后, 由读者来执行下一个 P(&w).
这道题我想了好久, 有好多方案都依赖操作系统的调度器(例如 CFS 就能保证先睡醒的进程先执行)或者额外的 API(例如 sched_yield), 或者 writer 部分就只能充当自旋锁(也就是 dreamanddead 的版本, 这个 reader_first == 1 条件过后, 不停的 continue 当自旋锁, 这太耗费 CPU 了).
后面参考了知乎用户 Decay 的一个专栏, 秒懂:

1. //省略 while(1), 下同
2. void writer() {
3.     //前面省略
4.     V(&w);
5.     P(&mutex);
6.     V(&mutex);
7. }

复制代码

逻辑也比较简单:

• 如果此时此刻有读者在等待 w, 那么 mutex 锁肯定是被锁住的
  
• 所以 writer 只需要等待 mutex, 也就是等待读者释放 mutex 锁, 而读者要是能释放 mutex 锁, 那肯定就已经获取 w 了, 也就是说, 这个是能保证读者强优先的.
  
• 如果没读者锁住 mutex, 那么就自己锁住自己解锁.
  

问题得以解决.
对于 dreamanddead 答案的一些额外的思考
关于 dreamanddead 的答案, Decay说是错的, 鄙人也有一点属于自己的看法(叠个甲, 只是我认为):

1.     if (readcnt == 1)  // e1. 没有进行读写保护
2.       reader_first = 1;  // e2. race condition!

复制代码

• 边读边写 (也就是e1的读写保护) 在多成员数据结构的情况下确实会出问题, 但是针对基元数据类型 (例如 int) 的读取, 我认为不存在问题, 因为在绝大多数情况下, 读取这个变量的汇编指令也是一条, 读取过程是能保证原子性的.
  
• 上面这段代码, race condition 不存在, 因为 reader_first 的读写是受到 w 的保护的.
  

所以, dreamanddead 的答案确实有有待商榷之处(例如边读边写的操作, 没有加锁, 确实有点不规范, 但是在这种特殊情况下也是合理的), 但是我认为这段代码大体上是合理的, 唯一的不合理之处就是使用了自旋锁, 导致 writer 占用了大部分的资源.
3.2 作业 12.20

ok, 解决了 12.19 后, 接下来就是 12.20.

翻译成人话, 就是: 先到先得，读者来就先执行读者，写者来就先执行写者。 但是这并不等同于串行, 例如这种情况:

1. 读者 A, 读者 B, 写者 C, 读者 D
2. 读者 A 先读取, 读者 B 接下来发现目前状态是在读, 也进去读.
3. 但是写者 C 就直接停住了, 因为当前状态是在读, 而它要进行写操作.
4. 由于先到先得, 读者 D 也停住了, 等待 C 执行完.

复制代码

题目给了我们提示: 最多 N 个读者, 一个计数信号量, 一个互斥锁.
ok, 现在开始写代码.

1. sem_t num; //初始化为 N
2. sem_t mutex;
4. int write = 0;
5. void reader() {
6.     P(&mutex);
7.     P(&num); //read_num -= 1;
8.     V(&mutex);
9.     //Read
10.     V(&num);
11. }
13. void writer() {
14.     P(&mutex);
15.     //Write
16.     V(&mutex);
17. }

复制代码

我认为是这样的逻辑:

• num 就是读者剩下的读写者, 题目中说最多 N 个, 所以初始化为N.
  
• 每个读者进来一次, 就 V(&num).
  
• mutex 是 reader 和 writer 的竞争锁. 在前一个 reader 来了后, 分为两种情况:
  
  
  
  • 若 writer 来了, writer 要等写入完后, 才能执行 reader, 所以接下来的 reader 全部阻塞在 mutex 上, 就没法执行了.
    
  • 若 reader 来了, 由于 reader 在将剩下的读写者-1后, 立马释放了锁, 所以 reader 还是可以继续并发执行的.
    
  
  

OK, 问题解决.
3.3 作业 12.21

继续看下一道题目:

这难度看样子不小, 其实就根据 图12.26+作业 12.10 照葫芦画瓢就好了. 话不多说开始写代码:

1. sem_t mutex;
2. sem_t w;
3. void reader() {
4.     P(&w);
5.     //Read
6.     V(&w);
7.     P(&mutex);
8.     V(&mutex);
9. }
11. void writer() {
12.     P(&mutex);
13.     P(&w);
14.     V(&mutex);
16.     //Write
17.     V(&w);
18. }

复制代码

这儿确实和上面的有些不一样, 我没有设置 writecnt, 因为 writer 和 reader 不一样, writer 不可能并发运行, 否则乱套了.
而上面的 mutex 也是用于等待 writer 的, 逻辑和上面的一样, 要是 writer 在等待, mutex 肯定是锁住的.
The End

本期文章写到这, 感谢大家的观看哦~萌新初涉系统编程, 有错误也请多多指正~

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！