【操作系统】第九章：临界区的概念和互斥的理解
OS.StudyLog.Ch9.Synchronization and mutual exclusion.同步互斥问题
[*]背景
[*]互斥
[*]
[*]临界区的设计
[*]禁用硬件中断
[*]基于软件（同步）的解决方法
[*]
[*]小结
[*]更高级的抽象
背景 计算机系统里会有多个进程存在，这多个进程相互之间还会进行交互。交互会引起对共享资源的访问，如果对这些共享资源访问操作不当，就可能出现一些问题（死锁、饥饿）之类。
这些问题出现的原因也和调度有关。如果进程相对独立（不需要访问共享资源，进程间不需要交互），则每一个进程和线程的执行是确定的，执行的流程也是可以重复的。
但是如果进程和线程需要协助操作，可能会交互或者访问共同资源，则在调度器管理下会有不同顺序的调度。而调度的顺序由很多因素决定，可能导致对于当个进程而言它的执行时间不确定（其他进程可能会抢占），且结果不确定（因为其他进程访问共享资源而导致结果不同）而且结果可能无法重现（其他进程的抢占时机、次数和资源等变量过多）。 这种不确定性和不可重复性会引入难以发现的bug，会出现一些不稳定的现象，而这种现象又很难重复。
进程间合作是必需的。因为资源需要共享，不能为每一个访问者拷贝一份相同的资源，从负载上来说是不可能的（想象一下给每个人设置一家银行）。其次通过并行或者并发操作，可以提高系统效率，实现更有效的资源利用。在计算机中，我们为了提高效率会把大的资源拆分成小的资源，把大的工作分成小的工作，模块化之后，不同模块化之间是需要共享和交互的，因为他们本身就是一个整体。
例子）原本没有问题的代码段在并行中的问题
P1执行了两个汇编指令后产生上下文切换（调度），P2抢占P1。P2完成后调度P1再执行，这个执行过程里P1的PID是100，和预期相同。P2得到的PID也是100而且next pid应该是102，这里确实101。
一开始执行时，newpid确实是100.在这个时候做了一次调度，切换到进程2。进程2也要完成同样的操作，第一步要LOAD nexpid给寄存器1.而这个时候的nextpid是100导致接下来的三条操作，会给newpid赋100而且nextpid是101。到此为止没有问题。
但是从P2切回P1时，P1要做个+1操作，而这时候的寄存器1还是100。但是进程2切换到进程1时，P1得到的PID（存在于NEWPID）的值等于P2的值都是100，且nextpid都是101，并没有变102。因为上下文切换后，进程1的寄存器回复之后，寄存器保存的值依然是100的值使得nextpid无法进一步更新成102。
这个问题就因为四条指令产生的上下文切换就使得结果不一致了。
我们希望无论多个线程如何切换，交替执行，程序都要正常执行。不确定性要求并行程序的正确性。
我们把这些现象称为：
出现了竞态条件就会导致出现不确定性和不可重现性的现象。为了避免这种现象：其实很简单，只要那四条指令不会被打断，不会被切换，就不会出现这种现象了。那么为了保证指令不被打断，就需要原子操作：
原子操作就是不可被打断的操作，避免了不同切换点出现问题的现象。但是实际系统中，指令间是可以被打断的。通过某种软硬件结合的方式，使得指令可以按照原子操作方式执行而不是随时被打断的方式执行。
为了理解举一个例子：
两个线程，一个加操作一个减操作，谁先完成谁就赢（打印出一段话）。调度这两个线程的内存读取和存储是原子操作，但是+1 -1不是原子操作（4条汇编指令构成）。根据不同调度策略结果不同，除了A赢或者B赢，还有一种情况：谁都打印不出来，线程持续执行没有结果。
如果线程执行到i=i+1时，这时候线程切换到B，执行i=i-1。就会出现i=i+1-1=i，就会可能出现线程AB在while循环里一直在各自的循环内出不来，也就说谁都无法执行完毕。
互斥 为了理解同步互斥，需要简述以下概念：
临界区一段代码需要访问的资源是共享资源。访问共享资源的代码称为临界区。
互斥：临界区的进程只有一个，不允许出现多个进程进入临界区访问。多个进程访问会出现不确定性
死锁：当两个进程都拥有一定的资源且还需要其他资源时，有可能相互等待。A等B、B等A，谁也无法继续执行。
饥饿：一个进程持续等待，而且可能长期存在而无限期等待。
接下来根据这个问题来讲解同步互斥
把上述现象视为进程活动，就会出现买面包事件执行了两次，而我们不希望这样。
那么出现这种情况的原因有：
1.没有限制只能有一个人买面包（设定为最多一个人有一个）
2.如果需要，就会有人去买面包
那么解决的方案有以下几种：
锁上锁冰箱，粒度过大，因为冰箱内可能有其他东西是其他人需要的，所以这种方式并不可行。
方案：标签
设置标签视为加锁操作，去掉标签视为解锁操作。
逻辑：任一个体打开冰箱第一步看有木有面包，如果有则空过。如果没有再看有木有标签，如果有，则空过；如果没有说明他是第一个发现冰箱没有 面包的人，贴一个标签然后去买面包。面包买到后回来撕下标签并将面包放入冰箱。
那么这件事映射到计算机程序会怎么样呢？
如果控制逻辑变成并发进程去执行，仍然会出现问题。如果以进程的方式来执行，那么在执行过程中任何时间是可能发生上下文切换的。也就说进程A执行到一定程度也可以被OS调度切换到另一个进程去执行。这种情况下：
12步发现没有面包后，产生进程切换。跳到进程2，也会判断面包标签，发现也没有，这时候也会触发购买面包事件。然后再次跳到进程A，A买面包，之后B也会完成同样的行为。也就说，标签没有起到锁的保护机制，并没有限定到只让一个人去买面包的功能，控制逻辑失效了。而且，出现这种情况后，很难去重现这种情况，因为下一次产生调度可能不是按照这种情况进行上下文切换的。会导致间歇性失效。
调度的不确定性使得竞态条件随时会发生，不想要的结果仍然会出现。
那么如果先留标签再检查面包和标签：
如果这样放置，进程调度可能会发生谁都不去买面包的情况。A和B都放置标签，然后两个都去检查是否有标签，结果有标签，则都不会去执行接下来的行为。
考虑到上述行为，也许是因为标签没有标识，也据说不知道这个标签是谁留的。我们给标签增加一个标识，尝试着去解决这个问题。
进程A放置标签1，进程B放置标签2.然后对于进程A，他会检查是否有标签2，如果没有标签2就意味着进程B没有放置标签，则会判断是否有面包并执行买面包操作。
但是仍然会出现问题：
在上下文切换后，标签1和2全部留下，然后AB都检查到对方已留标签，则都不会继续向下执行。所以仍然会发生谁都不买面包的情况。
也就说增加标签的属性仍然不能解决这个问题。
更加复杂的标签方案：
现在这种情况对于进程而言，可以自己买也可以等别人去买，也就说进程。
进程A：如果发现B留了标签，则会一直等待B买完面包
对于B：如果发现A的标签，则可以去买面包；否则，离开。如果B离开了，则A可以去买面包。
进程AB的控制逻辑不同，但是也存在问题。对于进程A判断有标签，A不会去掉自己的标签或者执行其他操作，而是忙等，直到B去掉标签才会继续执行下一个语句。对于进程B而言，判断A是否留标签，如果设置了标签并不是忙等，而是去掉标签2。使得进程A如果执行while循环时有很大概率迅速获得后续的控制逻辑并进一步执行。
这样确实解决了问题，确保了总有一方去购买面包而且不会没有人去买面包。而且A有更大的概率买面包，B相对于A购买面包的次数会少一些。
这种方法的弊端：
1.只是解决了两个进程的问题，如果有很多进程，则这种方法无法自然扩展。
2.调度和进程设计来说，希望A与B能够均等的去执行，但是这种设计出现明显的不对称性和不公平性。
所以这个方法治标不治本。
==> 通过互斥的手段来解决
临界区：有一段代码会对共享资源进行操作，这个例子里，面包是共享资源。临界区里只允许一个进程去访问和执行，这段代码主要就是对共享资源进行读或者写操作，如果已经有一个进程在临界区执行，则其他进程必须等待。
互斥：确保只有一个进程在临界区。保证互斥就可以保证结果确定。
我们要确保互斥的执行临界区代码，也就意味着任何时候只有一个进程在执行临界区的内容。
改善代码：
这样就可以确保任何时候只有一个进程在临界区中执行，其他进程在临界区外等待，只有等临界区内进程执行完毕之后，等待的进程中也只能有一个进入临界区。很好地解决了这个面包问题。
临界区的设计
临界区的属性：
1.互斥：任何时候只有一个线程或者进程可以访问临界区
2.前进(Progress)：一个进程或者线程想进入临界区，则最终他会进入临界区，不会一直等待。
3.有限等待：如果一个进程只需等待有限的时间段就能确保它可以进入临界区去执行。
4.无忙等待【可选】：在临界区之外等着，如果是在做死循环这种忙等，如果不能确保很快进入临界区，则过于消耗CPU资源。
禁用硬件中断
中断除了产生硬件事件让OS去响应事件之外，当进程要进行切换或者调度时，我们需要时钟中断。时钟中断可以使得当前进程即使它在执行也可以被打断，切换到OS，让OS完成调度切换其他进程去执行。这个中断使得OS有强制打断进程正常执行完成进程切换的能力。这个能力是用于OS调度系统管理的重要机制，同时这个机制也会得到上述不确定结果的原因，也就说如果我们执行临界区代码时禁用该功能（退出临界区时再恢复），也就不会有面包问题了。
虽然可以解决面包问题，但是也存在其他问题：中断主要用来响应外部事件，比如外设产生的事件，用于外界交互。比如这时候来了一个网络包或者时钟信号，完成磁盘块的读写等。如果这时候屏蔽中断，也就意味着这些硬件事件无法及时响应，对整体效率有很大影响。其次临界区本身执行的时间长短是不确定的，如果很长的话，长时间禁用会对系统造成很大影响。
也就说只针对临界区很小的情况是有效的。
另外两个CPU并行的进程要执行该临界区资源时，那么中断机制只屏蔽其中一个CPU是无法解决问题的。也就说中断机制对于多CPU是有限定的。当一个CPU执行屏蔽中断指令时，会把自身的响应中断能力屏蔽，但是不会屏蔽其他CPU的中断能力，也就意味着其他CPU可以继续执行继续产生中断，导致多CPU情况下屏蔽中断无法解决互斥问题。
基于软件（同步）的解决方法
如何设计进入和离开临界区才能使得任何时刻只有一个进程或线程在临界区执行以及确定其他进程可以在有限时间内必然能够进入临界区？
第一种方法：
进程turn（次序）决定谁先进入临界区。这种情况下，turn=0意味着轮到进程0来进入临界区了。
对于每个进程，如果不是轮到自己，则会在while里打转，当轮到自己，则会进入临界区执行，执行完毕后，将turn值变更（另一个合法的值J赋给turn），然后离开临界区，跳出循环。
这种情况下，可以保证互斥。保证只有一个进程可以进入临界区执行，因为turn只有一个值。
但是不满足前进：如果A完成临界区内的操作后决定不再进入临界区执行，而B再完成临界区操作后决定再进入临界区执行，但是A因为不打算进入临界区，就不会执行进入临界区的代码，也就不会改变turn值，导致B无法继续前进。
改进
设置一个flag标识，表示是否想要进入临界区。
对于进程 i i i而言：判断 f l a g [ j ] flag flag是否等于1，意味着 j j j是否想要进入临界区。对方想进入临界区， i i i就要等待对方退出临界区之后。等待 j j j退出临界区，退出时标识应该是0，也就意味着自身有机会可以执行了。
也就说，一开始其他进程会进入临界区，则谦让一下，让其他进程先执行。如果没有，则跳出循环向下执行，会把自身标识变成1然后进入临界区，执行后再赋0。
但是这个代码无法满足互斥。开始时，所有flag都是0，也就意味着如果进程执行到while循环跳出后切换，会令两个进程都会跳出循环，来到第二语句，给各自的flag赋1，这两个进程同时都会去执行临界区代码，无法保证互斥（多买面包问题）。
再修正
交换语序，这个代码确实在任何时刻不能两个while循环都能进入（保证互斥）。但是存在死锁，两个都被挡在while循环谁都进不去。
进程A的F是1，切换到B并把F赋1。切换回来后，因为两个进程都是1，则两者都会死循环，谁都跳不出循环。
正解：Peterson算法
用了两个变量，标识进入临界区的顺序和是否准备好进入临界区。（Flag是包含n个变量的数组，所以变量可增加）
进入临界区，如果要进入临界区：
flag是否为真且当前turn是否等于j。意味着进程j想进入临界区且现在轮到他进入。此时让给j执行临界区，否则自己执行临界区并且退出，此时访问临界区的需求改为否。
满足互斥与前进。
更复杂的算法：Dekkers算法
扩展：N线程的方法
针对n个进程保持互斥。算法细节不展开讲，介绍一下大致思路：对于进程i而言，前面的进程如果有已经进入临界区或者要进入临界区的，那么i进程等待。i进程后面的进程也要等待i进程执行后才行进入临界区执行，前提是i想要进入临界区。
通过这种方式实现有序循环的方式来完成n个进程有序进入临界区执行的思路。
Bakery算法：
进程id本身和票号来排序决定进入临界区的顺序，要比两个进程的算法复杂不少。
小结
当进程无法进入临界区时，目前的设计是忙等，这样会导致CPU占用时间过大。
硬件需求低，只需要LOAD STORE操作是原子的就可以。
更高级的抽象
基于硬件的原子操作的高层抽象实现。硬件如果能过提供原子操作，就能用原子指令来辅助我们实现进入临界区和退出临界区的操作。
获得锁：可以进入临界区执行
获得锁的过程就是进入临界区的时间过程。
释放锁的过程就是退出临界区的时间过程。
抽象的实现：
Test and Set:这是一条机械指令。完成了通常的读写操作的两条指令的功能，它包含三个语义{从内存中读取，判断值（返回真假），读的内存值设置成1}
Exchange：输入参数是两个内存的单元，把两个单元的值交换并返回。
这两条指令如果有一条就能比较简单的实现临界区的进入和退出。
这两个指令被封装为机械指令，也就意味着执行这些指令时，是不允许被中断或者切换的。只有执行完整个指令的语义之后才可能产生切换或者中断。
某一进程想进入临界区，首先要获得LOCK。 while循环内的t-a-s操作一开始是0，代表没有任何一个进程进入临界区。做完t-a-s操作后，值变为1且返回0，然后跳出循环继续执行。接下来下一个进程想要进入临界区，他会调用Lock::Acquire(),这时候他发现，值是1，也就意味着返回值也是1，再赋值还是1，会一直循环出不来（忙等）。进入临界区完成之后，会做出一个 退出操作，退出操作Release（）就是把值赋0.一旦值赋0也就意味着其他等待Lock::Acquire（）的进程可以跳出循环了，因为这时候值为0了。
从这个结构看来，他除了可以很简单的支持两个进程以外，还能支持N个进程。一个访问，其他的等while循环。一个退出，值覆盖为0，其他等待进程有机会执行临界区。而且两个进程和N个进程的操作很简洁，都是一样的结构。
改进
while循环是忙等，也就意味着临界区很长，CPU开销会比较大。
等待的进程在等待时，可以去睡眠。如果一个进程在等待且暂时不能进入临界区，我们可以令其进入睡眠。也就意味着把进程挂回等待队列，就可以把CPU让出来给其他进程使用，一旦当前临界区内执行的进程退出，他会把值赋0还会同时完成唤醒操作，通过唤醒操作使得等待进入临界区的进程从新去判断可以完成t-a-s/跳出循环。如果跳不出，再次进入睡眠，否则进入临界区。
与忙等的差别：
如果临界区足够短，则我们选择忙等。因为他不需要完成上下文切换，节省开销。
如果临界区长，开销远远大于上下文切换，我们愿意选择基于上下文切换非忙等的机制来使用。
如果k=1，做交换操作，交换lock和key。lock和key都是两个内存单元，第一个进程执行时，lock值为0，执行完exchange后lock是1，key是0.一旦key是0，while循环条件被打破，可以进入临界区去执行。
进入临界区时，lock已经从0变成1.其他进程再想进入时，由于key和lock都是1，所以while死循环。直到临界区内的进程退出时，会完成一个操作lock=0，一旦lock为0，那么其他等待的进程会再次执行交换，第一个执行exchange的进程他会发现lock变0 了，那么此时key会变0，lock会变1，跳出循环，执行进入临界区的操作。
基于原子操作机械指令的同步互斥.优点：
实现简单
容易扩展
开销比较小
缺点：
忙等可能会耗费更多CPU开销
While循环会去抢lock，抢lock是一个比较随机的过程，那么可能导致某个进程一直抢不到的饥饿现象。
高优先级进入忙等，但是低优先级没有机会释放锁。可以通过优先级反转有效解决。
通过锁可以有效解决互斥问题。锁机制的实现需要一定的计算机体系结构的硬件支持。目前而言，单机OS选择基于原子操作的机械指令来完成同步互斥来进入/退出临界区是常见的方式。根据临界区执行长短的特征来完成忙等和非忙等的方式来实现同步互斥。
文档来源：51CTO技术博客https://blog.51cto.com/u_14758357/3051265
页:
[1]