计算机操作系统19，20

第十九课：读者-写者问题（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(readcount==1)P(rw);V(mutex);读数据;P(mutex);readcount--;if(readcount==0)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

必须知道：

第一个：

锁门。

最后：

开门。

必须知道：

读者优先：

可能：

导致：

写者：

饥饿。

十六、同步章节总结（★★★★★）

到这里，我们已经学完了操作系统同步的四大经典模型：

你会发现，这些模型虽然场景不同，但本质都是在回答一个问题：

如何让多个线程安全、高效地共享资源。

第二十课：死锁（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 ↓ 等C

C：

没有：

等任何人。

那么：

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

是不是：

形成：

一个：

环？

如果：

每种资源：

只有：

一个实例。

那么：

有环 = 死锁。

这是考试非常喜欢考的结论。

注意：如果资源有多个实例，仅仅有环并不一定死锁，需要进一步分析。

九、死锁有哪些处理方法？

教材：

一般：

分：

四类。

这里只先认识名字，后面几课详细展开。

可以把它们理解成四种不同策略。

十、一个形象比喻

假设：

十字路口。

四辆车：

都进入：

路口。

每辆车：

都堵住：

别人。

结果：

东 等 南 等 西 等 北 等 东

这就是：

现实中的：

死锁。

交警：

怎么办？

有四种办法：

• 预防：红绿灯设计好，不让这种情况出现。
• 避免：发现快堵住了，提前拦下一辆车。
• 检测：先让车走，堵了再发现。
• 解除：拖走一辆车，恢复交通。

这四种方法对应操作系统处理死锁的四种策略。

十一、本课重点（★★★★★）

必须掌握

死锁定义

多个进程互相等待资源，导致都无法继续执行。

四个必要条件

口诀：

一次一个，拿着等；不能抢，等成环。

死锁与饥饿

一定要会区分。

死锁：

大家：

都停。

饥饿：

只是：

有人：

一直：

没机会。

资源分配图

一定要会：

• 圆圈：进程
• 方框：资源
• 进程→资源：申请
• 资源→进程：分配

对于每种资源只有一个实例的情况：

资源分配图有环 ⇔ 发生死锁。

🎯 课堂练习

请自己思考：

①

为什么：

如果：

允许：

资源：

被强行：

抢走。

就不会：

发生：

死锁？

（提示：四个必要条件中的哪一个被破坏了？）

②

为什么：

如果：

所有进程：

必须：

一次：

申请：

全部资源。

也能：

避免：

死锁？

（提示：又破坏了哪一个必要条件？）

③

下面哪一种属于死锁？

A.

A 等 B。

B 等 A。

B.

低优先级：

一直：

排不到CPU。

🎓 学习进度

到目前为止，我们已经完成：

操作系统 │ ├── 操作系统基础 ✅ ├── 进程 ✅ ├── CPU调度 ✅ ├── 线程 ✅ ├── 同步与互斥 ✅ └── 死锁（基础） ✅

下一课预告（408 最难算法之一）

下一课进入：

第二十一课：死锁预防与死锁避免

你将学会：

• 如何通过破坏四个必要条件来预防死锁。
• 什么是安全状态（Safe State）和危险状态（Unsafe State）。
• 为什么危险状态不等于死锁。
• **银行家算法（Banker’s Algorithm）**的核心思想。

银行家算法是很多同学觉得最难的内容，但我们会从最简单的生活例子开始，一步步推导，让你真正理解，而不是死记硬背。

很好！👏

这一课非常重要。

前面我们已经把操作系统的主要章节全部学完了：

操作系统 ├── 进程管理 ├── 内存管理 ├── 文件系统 ├── I/O设备管理 └── 保护与安全

但是很多同学学完操作系统后：

会出现一个问题：

“每个知识点都会，但是不知道它们之间有什么关系。”

所以今天：

我们把整个操作系统：

从零串成一套完整体系。