第十九课读者-写者问题Readers-Writers Problem一、先来看一个生活例子假设图书馆里有一本珍贵古籍。很多人都想看。还有管理员负责修改。例如学生A阅读 学生B阅读 学生C阅读 管理员修改内容请问什么时候可以一起情况一学生A正在看。学生B也来看。有没有问题没有。因为大家只是看。没有修改。所以可以一起。情况二管理员开始修改。学生还能看吗不能。否则学生可能看到一半旧内容。一半新内容。数据就错了。所以规则非常简单。读可以共享写必须独占。这是整章最重要的一句话。二、操作系统中的对应关系图书馆对应共享数据。例如数据库 文件 缓存 共享变量读者对应读取数据写者对应修改数据于是得到两条规则。第一条多个读者。可以同时读。例如A读 B读 C读没有问题。第二条写者写的时候。任何别人都不能进去。包括读者。也包括写者。三、为什么不能边写边读假设银行余额100写者正在修改100 ↓ 80刚改一半。读者读取。可能得到错误数据。所以写的时候必须独占。四、需要几个变量和生产者消费者一样。这里也需要信号量。最经典两个。第一个mutex 1作用保护读者数量。为什么因为多个读者同时修改readcount会冲突。第二个rw 1作用真正保护共享数据。任何写者必须获得它。还有一个普通变量。readcount 0表示现在有几个读者。五、读者怎么进入假设A开始读。第一步。修改读者人数。是不是需要互斥所以P(mutex);人数增加。readcount例如0 ↓ 1说明我是第一个读者。如果是第一个。那么要阻止写者。于是P(rw);拿到写锁。然后释放mutex因为别人可以继续统计人数。于是多个读者来了。第二个readcount 1 ↓ 2注意。不是第一个。所以不用再P(rw)。直接进去。于是很多读者一起读。六、读者退出读完。第一步。人数减少。2 ↓ 1如果还有读者。不用管。最后一个读者出来。例如1 ↓ 0说明没人读了。于是释放V(rw);写者终于可以写。七、写者怎么进入写者简单。第一步。申请P(rw);如果没人读。没人写。进去。开始写。修改数据结束。释放。V(rw);完成。八、完整流程读者P(mutex);readcount;if(readcount1)P(rw);V(mutex);读数据;P(mutex);readcount--;if(readcount0)V(rw);V(mutex);写者P(rw);写数据;V(rw);九、为什么第一个读者加锁很多同学第一次这里最迷。来看。假设已经三个读者。是不是共享读那为什么只有第一个执行P(rw)因为只需要第一个把门锁上。后面的读者。直接进去。最后一个出来。负责开门。是不是很像电影院第一个进去锁门。最后一个出来开门。十、读者优先刚才这种算法。叫读者优先Reader Preference为什么假设一直有人读。A ↓ B ↓ C ↓ D ↓ E写者一直等。是不是可能永远写不了这叫写者饥饿Writer Starvation十一、怎么办后来提出写者优先。如果写者来了。新的读者不能继续进去。等写完。再继续读。于是写者不会一直等待。现代数据库大多数采用公平策略。既不是读者优先。也不是写者优先。谁等得久。谁先。十二、和前面的区别来看三个经典题。生产者消费者关注空 满哲学家关注死锁读者写者关注共享读 独占写所以重点完全不同。十三、考试最喜欢问★★★★★问为什么多个读者可以一起答案因为不修改数据。问为什么写者必须独占答案避免数据不一致。问为什么第一个读者要P(rw)答案阻止写者。问为什么最后一个读者V(rw)答案允许写者进入。十四、一张图理解读者A ↓ 第一个 ↓ 是 ↓ P(rw) ↓ 一起读 ──────────── 读者B ↓ 不是第一个 ↓ 直接读 ──────────── 最后一个读者 ↓ V(rw) ↓ 写者进入十五、本课重点★★★★★必须记住读共享写独占。必须知道三个变量mutex rw readcount必须知道第一个锁门。最后开门。必须知道读者优先可能导致写者饥饿。十六、同步章节总结★★★★★到这里我们已经学完了操作系统同步的四大经典模型问题核心矛盾关键词生产者-消费者缓冲区空/满empty、full、mutex哲学家进餐多资源竞争死锁读者-写者共享读、独占写readcount、rw临界区问题互斥访问临界资源你会发现这些模型虽然场景不同但本质都是在回答一个问题如何让多个线程安全、高效地共享资源。第二十课死锁Deadlock这一课目标学会什么是死锁、为什么会发生死锁以及死锁的四个必要条件。一、什么是死锁教材定义死锁是指多个进程因竞争资源而造成的一种互相等待的现象。这句话比较绕我们换成人话大家都在等别人放资源但谁都不放于是所有人都卡住了。记住这个关键词互相等待。二、生活中的例子假设有两支笔A笔 B笔有两个同学。小明已经拿到了A笔现在想拿B笔但是B笔在小红手里。与此同时。小红已经拿到了B笔她又想拿A笔于是小明 拿A 等B ↓ 小红 拿B 等A两个人都在等。没人愿意放下。结果永远卡住。这就是死锁。三、操作系统中的例子假设系统有两个资源。打印机 扫描仪进程A已经占有打印机。等待扫描仪。进程B已经占有扫描仪。等待打印机。于是A 打印机 ↓ 等扫描仪 ────────── B 扫描仪 ↓ 等打印机谁也继续不了。系统进入死锁。四、死锁与饥饿有什么区别很多同学最容易混。来看。死锁例如A 等 B B 等 A大家全部停住。谁也不能继续。饥饿Starvation例如一直有新的高优先级进程。低优先级进程一直排队。但是理论上如果前面的都执行完它最终还是有机会运行。只是等得非常久。对比死锁饥饿相互等待长时间得不到资源多个进程都停住至少有一个进程还能继续运行系统可能完全停滞系统仍在运行一句话死锁是大家都走不了饥饿是只有我一直没轮到。五、死锁为什么会发生我们前面其实已经学过。只有下面四个条件同时成立。才会发生死锁。条件①互斥资源一次只能一个进程使用。例如打印机。一个人打印。别人只能等。条件②请求并保持已经拿着一个资源。继续申请新的。例如已经 拿着打印机 ↓ 继续申请扫描仪条件③不可剥夺已经得到资源。别人不能强制拿走。只能自己释放。条件④循环等待形成等待环。例如A ↓ 等B ↓ B ↓ 等C ↓ C ↓ 等A形成一个圈。六、为什么必须四个都满足举个例子。如果没有循环等待。例如A ↓ 等B ↓ B ↓ 等CC没有等任何人。那么C完成。释放资源。B继续。再释放。最后A继续。是不是不会死锁所以少一个条件。都不会真正形成死锁。七、资源分配图★★★★★教材非常喜欢画图。我们必须学。两种节点圆圈表示进程例如○P1 ○P2方框表示资源例如□R1 □R2两种箭头进程 → 资源表示申请资源例如P1 ↓ R1说明P1正在申请R1。资源 → 进程表示已经分配例如R1 ↓ P1说明R1已经给了P1。八、怎么看有没有死锁例如画出下面资源分配图。P1 → R2 R1 → P1 P2 → R1 R2 → P2画出来○P1 → □R2 ↑ │ │ ↓ □R1 ← ○P2是不是形成一个环如果每种资源只有一个实例。那么有环 死锁。这是考试非常喜欢考的结论。注意如果资源有多个实例仅仅有环并不一定死锁需要进一步分析。九、死锁有哪些处理方法教材一般分四类。这里只先认识名字后面几课详细展开。方法思想预防Prevention破坏四个必要条件之一避免Avoidance提前判断避免进入危险状态检测Detection允许死锁发生再检测出来解除Recovery检测后终止进程或回收资源可以把它们理解成四种不同策略。十、一个形象比喻假设十字路口。四辆车都进入路口。每辆车都堵住别人。结果东 等 南 等 西 等 北 等 东这就是现实中的死锁。交警怎么办有四种办法预防红绿灯设计好不让这种情况出现。避免发现快堵住了提前拦下一辆车。检测先让车走堵了再发现。解除拖走一辆车恢复交通。这四种方法对应操作系统处理死锁的四种策略。十一、本课重点★★★★★必须掌握死锁定义多个进程互相等待资源导致都无法继续执行。四个必要条件条件记忆关键词互斥一次一个请求并保持拿着等不可剥夺不能抢循环等待等成环口诀一次一个拿着等不能抢等成环。死锁与饥饿一定要会区分。死锁大家都停。饥饿只是有人一直没机会。资源分配图一定要会圆圈进程方框资源进程→资源申请资源→进程分配对于每种资源只有一个实例的情况资源分配图有环 ⇔ 发生死锁。 课堂练习请自己思考①为什么如果允许资源被强行抢走。就不会发生死锁提示四个必要条件中的哪一个被破坏了②为什么如果所有进程必须一次申请全部资源。也能避免死锁提示又破坏了哪一个必要条件③下面哪一种属于死锁A.A 等 B。B 等 A。B.低优先级一直排不到CPU。 学习进度到目前为止我们已经完成操作系统 │ ├── 操作系统基础 ✅ ├── 进程 ✅ ├── CPU调度 ✅ ├── 线程 ✅ ├── 同步与互斥 ✅ └── 死锁基础 ✅下一课预告408 最难算法之一下一课进入第二十一课死锁预防与死锁避免你将学会如何通过破坏四个必要条件来预防死锁。什么是安全状态Safe State和危险状态Unsafe State。为什么危险状态不等于死锁。**银行家算法Banker’s Algorithm**的核心思想。银行家算法是很多同学觉得最难的内容但我们会从最简单的生活例子开始一步步推导让你真正理解而不是死记硬背。很好这一课非常重要。前面我们已经把操作系统的主要章节全部学完了操作系统 ├── 进程管理 ├── 内存管理 ├── 文件系统 ├── I/O设备管理 └── 保护与安全但是很多同学学完操作系统后会出现一个问题“每个知识点都会但是不知道它们之间有什么关系。”所以今天我们把整个操作系统从零串成一套完整体系。