学习日期：2024.7.8
内容摘要：进程同步/互斥的概念和意义，基于软/硬件的实现方法
进程同步与互斥的概念和意义
为什么要有进程同步机制？
回顾：在《进程管理》第一章中，我们学习了进程具有异步性的特征，即各个并发执行的进程以各自独立、不可预知的速度向前推进。
但是，有的情况下，我们希望某几个特定的进程按一定的顺序执行。比如说在进程通信——管道通信的时候，读进程和写进程是并发运行的，但是我们当然是希望是写数据的进程先传输信息，然后读数据的进程再接收。
所以，为了解决进程的异步性和我们对进程有序执行的需求的矛盾，操作系统需要提供进程同步机制。
什么是进程同步？
同步又称直接制约关系，它是指为了完成某种任务而建立的两个或多个进程，因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的同步就是源于它们之间的相互合作。
为什么要有进程互斥机制？
进程的“并发”需要“共享”的支持，各个并发执行的进程不可避免的需要共享一些系统资源，比如说内存或打印机、摄像头这样的I/O设备，而不是所有的系统资源都有足够的量，或者能同时分配给多个进程共享的，为了解决系统资源的有限性和多个进程对同一资源的需求的矛盾，需要提供进程互斥机制。
我们把一个时间段内只允许一个进程使用的资源称为临界资源，很多I/O设备（打印机、摄像头）都属于临界资源，此外还有许多变量、数据、内存缓冲区等都属于临界资源，对临界资源的访问必须互斥进行。
什么是进程互斥？
互斥又称间接制约关系，它是指当一个进程访问某个临界资源时，其它想访问该临界资源的进程必须等待，直到该进程的访问结束，释放该资源以后，另一个进程才能访问。
进程互斥的逻辑分区
临界区是进程中访问临界资源的代码段，进入区和退出区是负责实现互斥的代码段
进程互斥的四大原则
为了实现对对临界资源的互斥访问，同时保证系统整体性能，需要满足：
1.空闲让进。临界区空闲时允许一个请求进入临界区的进程立即进入。
2.忙则等待。当已有进程进入临界区时，其它试图进入的进程必须等待。
3.有限等待。对请求访问的进程，应保证其能在有限时间内进入临界区，不会饥饿。
4.让权等待。当进程不能进入临界区时，立即释放处理机，避免进程占用处理机的同时等待（忙等待）。
进程互斥的软件实现方法
单标志法
算法思想：两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予。
如图，turn的初始值为0，即刚开始只允许0号进程进入临界区。
若P1先上，则会一直卡在⑤，直到P1的时间片用完，切换回P0，直到P0正常访问完临界资源，退出时将turn改为1，P1才能进入临界区。
两个进程互相“谦让”，轮流使用临界资源。每次使用前，先检查是否轮到自己使用，如果没轮到就等待，如果轮到就使用，然后在使用完之后把使用权让出。
缺点：进程必须轮流访问临界区，但如果此时允许进入临界区的进程是P0，P0却一直不访问临界区，就会导致在临界区资源空闲的前提下，P1一直不能访问临界区。这违背了“空闲让进”原则。
双标志先检查法
算法思想：设置一个布尔型数组flag[],数组中的各个元素用来标记各个进程想进入临界区的意愿。比如"flag[0]=true''表示0号进程现在想进入临界区，每个进程在进入临界区之前，先检查有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。
好比两个人互斥的使用公共厕所（这个确实不太能共享），进去之前先看一下厕所是不是显示“有人”（检查其它进程意愿），如果没人就打开门进去，挂上“有人”的牌子（标记为本进程想进入临界区），最后在上完厕所之后，再把牌子取下来。（访问完之后修改标记）
缺点：P0和P1在某些情况下，可能同时访问临界区，违背了“忙则等待”原则。
因为进入区的“检查”和“上锁”两个步骤不是一气呵成的。生活中我们可以看到旁边有人也想上厕所，但是进程不行。进程在“检查”后看到门口没有牌子就打开了厕所门，但此时是可能发生进程切换的，若进程A检查完还没有挂上牌子时，切换到了进程B，进程B此时发现厕所门没有牌子，就打开进去上厕所了，但一段时间之后进程A又切换回来，因为之前已经检查过了，所以进程A不会看牌子，会直接打开厕所门，导致A和B同时使用一个厕所（没能互斥）。即上述代码顺序为①⑤②⑥...时，会导致P0和P1同时访问临界区。
双标志后检查法
算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“标记”，但是这两个操作无法一气呵成，导致两个进程同时进入临界区的问题，因此该方法是先“标记”后“检查”。
与上一方法对比来看，就是交换了检查和标记的位置。
还是以上厕所来举例，此方法就是在进入厕所前先不看有没有牌子，只要自己想上，就先挂一个“有人”的牌子，然后再检查有没有别人的牌子，如果没有就直接进去，如果有就等待别人的牌子被取下。
缺点：与前一个算法有类似的问题，因为标记和检查的过程不连贯，当上述代码顺序为①⑤②⑥...时，会出现明明临界区空闲，但P0和P1都无法访问临界区的情况，违背了“空闲让进”和“有限等待”原则，会导致进程饥饿。
进程A首先给厕所门挂上了牌子，但是此时发生了进程切换，换到进程B，进程B也会直接挂上牌子，然后又切换回了进程A，此时进程A执行检查步骤，发现门上有进程B的牌子，会开始等待。当进程A的时间片用完后，切到进程B，B发现门上有进程A的牌子，也不敢进去，这样其实厕所里根本没人，但是AB双方都误以为有人，会无限的等待下去，导致进程饥饿（憋死了）。
Peterson算法（重难点）
算法思想：结合双标志法、单标志法的思想，同时设置布尔数组flag[]和整型变量turn。如果双方都想进入临界区，那么可以让进程互相谦让。
进程首先表达意愿，然后把turn设为对方的编号表示谦让，注意理解此处while判断的含义，（while通过的意思是被循环卡住了，循环等待），检查是否是对方想进，且自己表达了最后一次的“谦让”
很绕，我们结合例子来理解
进程P0首先声明自己想上厕所，挂上牌子，然后表示我愿意谦让给对方先上（更新turn值），然后判断是否厕所门上有对方的牌子，且最后是自己表达了谦让，如果都满足就等待对方结束，否则开始上厕所。
谁在最后谦让了（修改turn值了），说“客气话”了，谁就会失去行动的优先权。
P0说：“你也想上厕所？那你先请吧”，但是P1说：“不了不了，还是你先。”然后P0就会去上厕所
因为P1已经说了你先请（turn=0），P1就“不好意思”在P0谦让之前上厕所，对P0也是同理。
当执行顺序为①⑥②⑦时，首先进程P0挂上牌子，切到P1挂上牌子，然后P0谦让，turn=1，切到P1谦让，turn=0。
此时若切回P0，下一步是③，则门上有P1的牌子，但是turn=0，对于P0来说，上一次谦让的不是自己（上一步不是②），所以P0不会等待，直接开始使用。
若P1谦让后继续执行，下一步是⑧，则门上有P0的牌子，且turn=0，对于P1来说，上一次谦让的是自己（⑦和⑧连续执行），所以要等待，直到切换回P0，P0会直接开始使用。
当执行顺序为①⑥②时，首先进程挂上P0牌子，切到P1挂上牌子，然后P0谦让，turn=1。
若下一步是⑦则同上，若下一步是③，此时门上有P1的牌子，且turn=1，对于P0来说，上一次谦让的是自己（②和③连续执行），所以要等待，直到切换回P1，P1会直接开始使用。
同理，当执行顺序是①⑥⑦时，和①⑥②没有区别，只相当于对换了P0和P1进程而已。
至此，我们已经列举了前两步是①⑥的所有情况，都不会产生问题，所以Peterson算法不会因为检查和标记的不连贯产生问题。
缺点：Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是没有遵循让权等待的原则，会发生“忙等”。（进程缺乏临界资源却占用处理机等待）
其相较于之前介绍的三种软件解决方案来说是最好的，但是依然不够好。
进程互斥的硬件实现方法
前面介绍的方法中，很多问题都是由于标记和检查的过程不连贯，不能一气呵成导致的，这让我们想到之前在《进程控制》章节中学习过的“原语”，如果可以用某种方法一气呵成，中间不发生进程切换，不就解决问题了吗？
中断屏蔽方法
利用“开/关中断指令实现”（与原语的实现思想相同，即在某进程开始访问临界区到结束为止，都不允许被中断，也就不能发生进程切换）
优点：简单，高效。
缺点：不适用于多处理机，因为如果是多核处理机，处理机A和处理机B上的进程可能同时访问同一个临界资源，且都不能被中断。
而且开/关中断指令的权限非常高，只适用于内核进程，不适用于用户进程，应用范围不够广泛。
TestAndSet指令
简称TS指令或TSL指令，L代表Lock，TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
以下是C语言描述的逻辑演示：
若刚开始lock是false（未上锁），则TestAndSet指令返回的old值为flase，while循环条件不满足，不会卡住，会跳过循环进入临界区
若刚开始是true，则TS指令返回的old值也是true，while循环条件满足，循环等待，直到当前访问临界区的进程更新lock值“解锁”。
TS指令中每次都设成true是因为每次TS指令运行都是有程序想访问临界区，要上锁。
实际上TS指令不是真的return一个值，而是把这个值存到某个物理寄存器里面，是用汇编语言执行的。
优点：实现简单，无需像软件实现方法那样严格检查逻辑漏洞，且适用于多处理机环境。
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程依然会占用CPU并且循环等待，即“忙等”。
Swap指令
又称Exchange指令或者XCHG指令（Exchange，什么天才简称），Swap指令是用硬件实现的，执行的过程同样不允许被中断，只能一气呵成。
逻辑描述如下：
其实和TSL在逻辑上是相同的，先给old赋值为true，然后交换lock和old的值，事实上就是给lock赋值true（上锁），然后判断old的值是不是true，如果是，说明之前就是上锁的，则循环等待直到解锁，如果不是，则跳出循环开始运行。
优缺点同TS指令一样，实现简单、适用于多处理机环境，但不满足让权等待原则，会导致忙等。
补充：互斥锁
互斥锁是解决临界区的简单工具，可以理解为一个布尔型的变量，通常用硬件操作实现。
以上方法（除中断屏蔽法）都依赖于内部的一个while循环语句来实现互斥，这是最简单的互斥锁，这种需要连续循环忙等的锁叫自旋锁（spin lock），顾名思义就是在自己循环转圈，其最大缺点就是忙等待。
使用这种方法，进程在时间片用完后才会下处理机，会违反“让权等待”原则，但优点是等待期间不用切换进程上下文，常用于多处理器系统，一个核忙等，另外的核正常工作，并快速释放临界资源，不必频繁切换进程。但不太适用于单处理机系统，忙等的过程不可能解锁，白白浪费时间和CPU资源。
内容总结自王道计算机考研《操作系统》 和 人民邮电出版社《操作系统导论》
