同步与互斥的基本概念

2.1.1 里留下过一个未解决的问题：并发导致失去封闭性，执行结果与推进速度有关。这一整节（2.3）就是在解决它。

本节负责把问题定义清楚：要保护的是什么、保护到什么程度算合格。后面几节才讲具体工具。

机制

两种制约关系

并发进程之间的相互制约分两类，判据是制约的方向。

互斥（间接制约关系）：多个进程都想用同一个资源，但该资源一次只能给一个人用，于是它们互相排斥。

比如两个进程都要用打印机。谁先拿到谁先用，另一个必须等。它们之间没有先后要求，只是不能同时。

之所以叫”间接”，是因为进程之间本来毫无关系，只是因为共享了资源才被迫产生了制约——制约是通过资源间接传递的。

同步（直接制约关系）：多个进程为完成同一个任务而协作，因而在执行次序上有确定的先后要求。

比如进程 A 负责往缓冲区写数据，进程 B 负责读走。B 必须等 A 写完才能读——这是任务本身决定的顺序，不是资源冲突。

之所以叫”直接”，是因为制约来自进程之间直接的协作需求。

一句话区分：互斥是”不能同时”，同步是”必须按序”。

临界资源与临界区

一段时间内只允许一个进程访问的资源，称为临界资源。打印机、共享变量都是。

访问临界资源的那段代码称为临界区（critical section）。

注意这里有一个容易忽略的要点：需要互斥的是”代码段”，不是”资源”本身。 操作系统无法阻止进程访问某块内存，它能做的是让进程在进入那段代码之前先取得许可。所以所有互斥机制的落点都在代码上。

一个进程访问临界资源的完整结构固定分为四部分：

do {
    entry section;      // 进入区：检查能否进入，能则上锁
    critical section;   // 临界区：访问临界资源
    exit section;       // 退出区：解锁
    remainder section;  // 剩余区：其余代码
} while (true);

进入区和退出区是操作系统要提供的，临界区和剩余区是进程自己的业务代码。 后面几节讲的所有工具（软件算法、硬件指令、互斥锁、信号量、管程），本质上都是在实现进入区和退出区这两段。

同步机制应遵循的四个准则

判断一个互斥方案是否合格，看四条：

① 空闲让进——临界区空闲时，应允许一个请求进入的进程立即进入。

不满足它意味着”没人用却不让进”，白白浪费资源。

② 忙则等待——已有进程进入临界区时，其他试图进入的进程必须等待。

这是互斥的底线。不满足它就等于没有互斥，会直接导致数据错误。

③ 有限等待——对请求访问的进程，应保证能在有限时间内进入临界区。

不满足它意味着可能饥饿——理论上能进，实际上永远轮不到。

④ 让权等待——当进程不能进入临界区时，应立即释放处理机，避免忙等。

不满足它意味着进程占着 CPU 空转（忙等待，busy waiting），白白浪费 CPU 周期。

四准则的分量并不相同

这一点在做题时非常有用：四条准则的严重程度是分层的。

违反②忙则等待是致命错误——互斥根本没实现，会产生错误结果。
违反①空闲让进和③有限等待是功能缺陷——结果不会错，但效率低或可能饿死。
违反④让权等待只是性能问题——功能完全正确，只是浪费 CPU。

所以后面 2.3.2 会看到：那些”有问题”的软件算法，问题的严重性各不相同。而几乎所有的硬件方法和自旋锁都违反④，但它们仍被广泛使用——因为在合适的场景下，忙等的代价比切换的代价更小。

边界

同步 vs 互斥

	互斥	同步
别名	间接制约关系	直接制约关系
要求	不能同时访问	必须按确定次序执行
起因	共享同一临界资源	协作完成同一任务
例子	两进程争打印机	生产者写完消费者才能读

一个常被忽略的关系：互斥可以看作同步的特例。因为互斥也是在规定次序（谁先谁后都行，但不能同时），只是它对次序的要求最弱——只要求”不重叠”，不要求”谁先”。

临界区 ≠ 临界资源

临界资源是资源（打印机、共享变量）。
临界区是代码（访问该资源的那段程序）。

不同进程访问同一临界资源的代码段，是不同的临界区，但它们必须互斥执行。

与”内核程序临界区”的区别

2.2.2 讲过的内核程序临界区，是临界区中的一个特殊子类——它访问的是内核数据结构。

两者在”能否调度”上规则相反：

内核程序临界区：禁止调度（否则锁住内核核心结构会导致系统卡死）
普通临界区：允许调度（否则 CPU 要陪着占用打印机的进程一起空等）

本节讨论的是普通临界区。

对照速查

准则	含义	违反的后果	严重程度
① 空闲让进	空闲时应允许进入	资源浪费	功能缺陷
② 忙则等待	有人在里面则必须等	互斥失效，结果出错	致命
③ 有限等待	有限时间内能进入	可能饥饿	功能缺陷
④ 让权等待	进不去就释放 CPU	忙等，浪费 CPU	性能问题

临界区四部分	谁提供
进入区	操作系统 / 同步机制
临界区	进程自己的业务代码
退出区	操作系统 / 同步机制
剩余区	进程自己的业务代码

考点

同步 = 直接制约 = 按序；互斥 = 间接制约 = 不能同时
四准则的名称、含义，以及违反哪一条最严重
临界区四部分，其中进入区/退出区由同步机制提供
临界区是代码，临界资源是资源
内核程序临界区禁止调度，普通临界区允许调度

考研笔记