操作系统-8章
线程的同步
1. 进程锁
什么是线程竞争
线程竞争(Threads Contention): 本质上是多个线程同时又想占用某个共享资源的趋势。竞争中的线程的速度比单线程要低。这有多重意义：
有锁必然有竞争。通常的竞争是指一个线程必须等待一个被占用的资源释放后才能继续，这就降低了此线程的速度。
- 没有锁也会有竞争。如，A 线程和 B 线程并发，A 操作的某个变量 x 和 B 操作的某个变量 y 在同一个高速缓存线中，那么 A、B 线程事实上就存在竞争。或者更有，A、B操作同一个变量 z，那么在同一时刻 CPU 只会让一个线程使用 L2缓存线，另一个就只能将数据放在了低速线上，这样就使得速度比单线程要低，产生竞争。
- 不是因为锁的存在才有竞争，锁正是为了减少竞争而引进的，因为如果不加锁那么多个线程可以在同时操作某个资源，这会带来更大的损耗。
什么是“临界区”
临界区(Critical Section): 是指某个共享资源可以被多个线程访问，我们要保证在一个时间段内只有一个线程可以访问，即一个线程的不可分割的、原子性的一串操作，否则会造成非预期的运行结果。如一个变量，网络连接，外围设备等。我们要保护这个临界区在一段时间内只能被一个线程使用。
一般的，假设对于一个线程来说它总要做以下的事情：
2. 单机中线程”同步”方法的发展
便条(Note)
留下便条高速别人将要使用临界区。有两种方式：
- 先检测Note，再留 Note，操作，移除 Note
检测Note与留 Note 之间的空隙，可能会使 A、B 线程都留下 Note，然后都操作了资源。都进入了临界区。这是非法的。
先留 Note，再检测Note，移除 Note/操作后移除 Note
严格交叉操作后，A、B 都直接移除了Note，最终都没有对资源操作。都没有进入临界区。这是非法的。
本质上是检测、留 Note、临界区操作的间隙引起，需要引入原子性操作。
当引入了原子性操作后，不再会重复操作或都不操作。但是当 A 在临界区操作时，B 只能原地等待，即不断的检测 Note 是否已经移除。造成了CPU资源的浪费。
锁(Lock)
便条同步方法的缺陷在于一个线程指令之间的空隙会被另一个线程所“钻入”跑指令，我们一直在把每条指令作为调整对象，并试图为了不让 A 线程钻入 B 线程的指令间隙而让 A 线程循环等待，看似可行但浪费了 CPU 的资源耗在了循环等待上，且不具有对称性（只不能让任意的线程来进行这种循环等待而解决问题）。
当在细节中很难处理时，我们或许可以调整一下思考的维度，既然指令间隙是关键，我们提高抽象的层次，把一组原子性操作的指令作为调整对象，这是一个“块”的概念，怎么让只有一个线程获得这个块是现在要做的？
比如，之前的指令都是在房间内喂鱼，现在我们考虑怎么用锁锁住房间，只有锁打开另一个线程才能拿起锁、进入、锁上。一个线程要做的就是：
等待锁开->拿到锁并锁上（一个原子性操作，否则要是存在间隙，拿到锁后没有锁上，CPU 切到另一个线程看到没锁上，前去以为自己也拿到锁，然后临界区就会有2个线程，非法的）->完成临界区步骤->开锁
如下图，lock() 就代表房间被锁上，这样另一个人（线程）就进不去。lock() 与 unlock() 之间的部分已经可以看成是 Critical Section。但这样带来一个问题，一旦这个 Critical Section 如果很费时间，那另一个线程就只能干等（CPU 还会在其间切换的为它工作）这么长时间。
现在考虑，可否将锁定的临界区的时间消耗减少，我们把喂鱼这个操作从临界区中踢出来，用一个指示性的标志（这个标志一定在喂鱼前会检查一下，或留下这个标志），那么如果我们锁住了这个“标志”，其他线程即使后来进了房间看到标志后也会再出去。
我们依然引入 Note 这个标志，在喂鱼操作前一定要执行检查 Note 或者留下 Note 这个操作，那么线程即使有两个线程前后进了房间，一个在喂鱼，一个在检查 Note 标志，根据留言判断：是否是出去还是去喂鱼。因而，我们现在用锁锁住“检查 Note” 和“留下 Note” 这个指令组，目的是把它们变成原子性操作，这个 Note 就将其他线程都挡下来。
现在 Critical Section 就是 检查 Note 这个条件语句。这样其他线程在
等待锁开这里不再需要太多的等待，因为和后面实际操作没有联系。
！！！ 这里是否有问题，当第一次检查是由 Note, 然后就不会留下 Note，当继续下一次检查时 Note 已经被移除，那么进入条件句，最后却要移除 Note？？？
睡眠与唤醒(Sleep and Wakeup)
Sleep and Wakeup 机制是为了解决 Critical Section Lock 期间CPU 资源浪费的问题,即使如上的最后的改进方案还是需要等待 Critical Section 直到 Unlock.
Sleep and Wakeup采用的是，当线程得知资源暂时不可用（lock）就 Sleep，即挂起状态，CPU 不会分配资源给它；一旦资源得到释放（unlock），释放资源的那个线程就会发送 Wakeup 信号给正在 Sleeping 的排队在最前的那位，那这个线程就会被Wakeup，得到资源使用权。
生产者与消费者(Producer and Consumer):
当队列空的，当CPU 切换到Consumer， 当一个 Consumer 想去消费，然后进入 Sleep
当队列满的，当CPU 切换到 Producer，当一个 Producer 想继续生产，然后进入 Sleep
当队列是满的，此时 Producer 是 Sleep，当CPU 切换到Consumer，在消费一个后，发信号给 Producer 需要生产了
当队列是空的，此时 Consumer 是 Sleep，当CPU 在切换到 Producer，在生产一个后，发信号给Consumer可以来消费了
生产者消费者模式也称为“有限缓存模型”，缓存的存在主要是为了减少每一次生产、消费都要进行锁的操作。当缓存不是满或空的状态，生产者和消费者都能自己正常工作，不会进入 Sleep，自然也就不需要Wakeup。
Sleep and Wakeup 的信号丢失问题，将产生死锁，生产者与消费者都不会继续推进：
原因是，Consumer接收Sleep信号后与 Sleep动作 有间隙。
解决办法：引入旗语，把对方发的信号都累积起来，避免丢失。
旗语(semaphore)
本质上是一个计数器，有Up 与 Down 操作，且 Up、Down 都是原子性操作。旗语对线程的操作和 Sleep and Wakeup 类似，当值=0时，消费线程就会Sleep；当值=上界，生产线程就会 Sleep。
一般的旗语可以类比公共图书馆，而且不会有滞纳金。比如图书馆里有5本 Python cookbook，当先到的前5个人都借去了，再来的人只能先回去；等其中一个（不管哪个）还来一本，图书馆就会通知之前排队在前的来取，若是没有人在排队，图书馆就会上架图书。
常见的是二元信号量，只有0 、1两个取值。那么 Down 至0 和 Up 至 1 就类似于锁的获得和释放。注意的是，二元信号量是有Sleep 和 Wakeup的，不同于锁的等待。以下的 Busy / Free 就相当于锁的获得，锁的释放。
管程(Monitor)
Monitor = Lock + Condition Variables
Lock：锁住 Critical Section
Condition Variables：在 Critical Section 中控制线程 Sleep 或 Wakeup。线程 sleep 与释放锁操作是原子性的，没有间隙；否则会出现有两个线程同时活跃在 Critical Section 的情况。 尽可能的让在Monitor 中让线程做的工作少，在 Monitor 外的部分处理 Monitor 内部分的结果，让不同的线程在 Monitor 中可以更快的响应。
3. 多计算机之间的线程同步
Monitor的缺点：
- 依赖于编译器将同步源语加在 Monitor 的开始和结尾
- 只能在单机上使用
消息传递：Send/Receive，以下是用消息传递实现 Producer and Consumer，并定义了缓存大小100
消息传递可以在多态计算机之间进行线程同步，是目前流行的方法。其特有的方式使得不存在像 Sleep and Wakeup的死锁，也不会有繁忙的等待消耗 CPU。
4. 参考
https://en.wikipedia.org/wiki/Critical_section
https://cs162.eecs.berkeley.edu/static/lectures/7.pdf
https://cs162.eecs.berkeley.edu/static/lectures/8.pdf
https://www.justsoftwaresolutions.co.uk/threading/locks-mutexes-semaphores.html
https://9p.io/sys/doc/sleep.html
https://www.cs.cornell.edu/courses/cs4410/2008fa/lectures.html
http://www.personal.kent.edu/~rmuhamma/OpSystems/os.html
http://www.cse.iitm.ac.in/~chester/courses/15o_os/syllabus.html