关于对 第 12 章 读/写者的一点思考和题解 (作业 12.19,12.20,12.21)

近刚学完 Linux 的进程部分, 接下来就是研究并发了. 正好, 去年 12 月到今年 1 月份那会, 我浅浅学了 CS:APP 的第 12 章。但是, 当时因为我出了一点事情(主要是严重感冒一些杂七杂八的事情), 所以没有好好研究, 粗略理解了一下概念就过去了, 习题也没好好做.现在, 我重新复习了一下这一章, 并且重做了一下这些题目. 先从读/写者模型开始吧.1. 什么是读/写者模型?想象一张很大的白纸, 我们可以往白纸上写字, 擦掉字, 也可以用眼睛在白纸上看别人写的字然后记住.我们把往白纸上写字的人叫做写者, 把记住别人所写的字的人叫做读者.在计算机这个大系统中, 也有类似的场景. 如 CS:APP 中所讲, 内存其实就是白纸, 负责从资源中读取的进程叫做读者, 而负责往资源中写数据的进程叫做写者.但是, 要是读者和写者不按照一定的规律来的话, 那整个系统就会乱套了. 所以, 为了保证顺序, 操作系统引入了信号量, 用来保证读写的操作是原子操作. 这部分在 CS:APP 的 12.5 节, 就不多讲了.2. 读/写者的实现为了实现上述的代码, 我们来写一下读/写者的实现逻辑:sem_t w;void reader() {P(w);//ReadV(w);}void writer() {P(w);//WriteV(w);}由此可见, 给 reader 和 writer 都加上一个w的互斥锁后, 下面的这段读/写代码就能实现原子操作了. 但是, 这样又带来了一个问题--太慢!你想啊, 这样子会导致读写操作完全串行, 等于把多任务变成了单任务了, 这已经不是并发了. 这怎么行?那你可能会说, 那我把读者的锁去掉, 行不行? 反正读者不改数据. 那接下来看一个例子---typedef struct {int a;int b;} obj_t;static volatile obj_t o;/*** 假设 o {.a 1, .b 2};*/sem_t w;void reader() {obj_t o2 o;/*** 这段代码反汇编后重新翻译, 大概是这样的:* o2.a o.a;* o2.b o.b;*///Operate}void writer(obj_t o2) {P(w);o o2; //同上V(w);}那我们来验证一下, 假设writer函数写入一个数据如下:obj_t o3 {.a 3;.b 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 读取到的结果:o2 {.a 1;.b 4;}这缝合怪可不是我们想要的啊! 也就是说, 这种方案, 可能会导致数据的残缺! 那怎么办? CS:APP 给我们提供了一段既可以加速, 又保证数据安全的示例代码 ---3. 对于图 12.26 代码的一点研究先摆上这段代码, 它位于 CSAPP 的图 12.26:int readcnt; // 刚开始0sem_t mutex, w; // 刚开始全部都为1void reader(void) {while(1) {P(mutex);readcnt;if(readcnt 1) {P(w);}V(mutex);// 读取操作P(mutex);readcnt--;if(readcnt 0) {V(w);}V(mutex);}}void writer(void) {while(1) {P(w);// 写入操作V(w);}}很明显, 这段代码相对于上面的示例代码, 有了如下改动:读写者都有一个互斥锁w保护着, 保证数据在写的同时不会被读取, 数据在读取的时候不会被写入.增加了一个变量readcnt, 用来记录此时此刻读者的数量.为了保证变量readcnt原子性, 让它不受并发的影响, 新增了一个mutex互斥锁用来保护它.当readcnt 1的时候, 代表有读者在读了, 第一个读者获取了w.一旦有一个读者获取了锁, 其他读者都可以直接读数据, 不用再受w的约束了, 也就是说, 它真正实现了并发.当写者获取锁之后, 由于第一个读者卡在了锁w的获取, 其他多余的读者都卡在了mutex的锁的获取, 所以此时读者不能读取数据.这相当于是上述两个方案的结合体, 也就是说, 它既能保证读者的并发, 也能保证数据的安全.但是, 随之而来的又有一些问题:假设写者来的时候, 读者正在读取数据, 然后读取数据的时候又有读者来,readcnt, 这样下去的话, 写者就没机会执行了, 这咋整?这种方案, 虽然读者的优先级比写者高, 但是其实这种优先级很弱, 因为写者执行了 V(w) 后, 可能立马又绕回到while开头了, 从而导致但是, 很明显, 这段代码也有一点缺陷:这段代码中, 读者的优先级比写者高, 因为就算写者先来, 只要读者在读数据, 写者永远都没机会执行, 导致写者饥饿.(习题 12.10)这段代码中, 读者的优先级虽然比写者高, 但也只是高一点. 对于锁w的操作, 读者和写者优先级相同, 万一有一堆写者, 读者很少, 那么读者就不能保证这个优先级了, 写者执行完V(w)后, 下一个P(w)照样大概率是写者, 导致读者饥饿.那么, 接下来我们要做一些改动, 就是下面的几道题目:4. 课后作业的题解4.1 作业 12.19这道题可以看作是 习题12.10 的延续:翻译成人话就是:写者执行完V(w)后, 由读者来执行下一个P(w).这道题我想了好久, 有好多方案都依赖操作系统的调度器(例如 CFS 就能保证先睡醒的进程先执行)或者额外的 API(例如sched_yield), 或者writer部分就只能充当自旋锁(也就是dreamanddead的版本, 这个reader_first 1条件过后, 不停的continue当自旋锁, 这太耗费 CPU 了).后面参考了知乎用户Decay的一个专栏, 秒懂://省略 while(1), 下同void writer() {//前面省略V(w);P(mutex);V(mutex);}逻辑也比较简单:如果此时此刻有读者在等待w, 那么mutex锁肯定是被锁住的所以writer只需要等待mutex, 也就是等待读者释放mutex锁, 而读者要是能释放mutex锁, 那肯定就已经获取w了, 也就是说, 这个是能保证读者强优先的.如果没读者锁住mutex, 那么就自己锁住自己解锁.问题得以解决.4.2 作业 12.20ok, 解决了 12.19 后, 接下来就是 12.20.翻译成人话, 就是:先到先得读者来就先执行读者写者来就先执行写者。但是这并不等同于串行, 例如这种情况:读者 A, 读者 B, 写者 C, 读者 D读者 A 先读取, 读者 B 接下来发现目前状态是在读, 也进去读.但是写者 C 就直接停住了, 因为当前状态是在读, 而它要进行写操作.由于先到先得, 读者 D 也停住了, 等待 C 执行完.题目给了我们提示:最多 N 个读者, 一个计数信号量, 一个互斥锁.ok, 现在开始写代码.sem_t num; //初始化为 Nsem_t mutex;int write 0;void reader() {P(mutex);P(num); //read_num - 1;V(mutex);//ReadV(num);}void writer() {P(mutex);//WriteV(mutex);}我认为是这样的逻辑:num就是读者剩下的读写者, 题目中说最多 N 个, 所以初始化为N.每个读者进来一次, 就P(num).mutex是reader和writer的竞争锁. 在前一个reader来了后, 分为两种情况:若writer来了,writer要等写入完后, 才能执行reader, 所以接下来的reader全部阻塞在mutex上, 就没法执行了.若reader来了, 由于reader在将剩下的读写者-1后, 立马释放了锁, 所以reader还是可以继续并发执行的.OK, 问题解决.4.3 作业 12.21继续看下一道题目:这难度看样子不小, 其实就根据 图12.26作业 12.10 照葫芦画瓢就好了. 话不多说开始写代码:sem_t mutex;sem_t w;void reader() {P(w);//ReadV(w);P(mutex);V(mutex);}void writer() {P(mutex);P(w);V(mutex);//WriteV(w);}这儿确实和上面的有些不一样, 我没有设置writecnt, 因为writer和reader不一样,writer不可能并发运行, 否则乱套了.而上面的mutex也是用于等待writer的, 逻辑和上面的一样, 要是writer在等待,mutex肯定是锁住的.