首先还是看这张图，对我们当前正在学习的地方做一个定位：
上一篇笔记我们已经讲了进程的相关概念和进程控制的知识，这篇笔记则涉及到了进程同步与进程互斥。
1. 进程同步与进程互斥
1.1 进程同步
问题：
在多道批处理系统中，多个进程是并发执行的，而并发执行的进程具有异步性，也就是说，各个进程以各自独立的、不可预知的速度向前推进。这样会带来什么问题呢？如果有 AB 两个进程分别进行读写数据的操作，那么写数据应该发生在读数据之前，而实际上，由于异步性的存在，可能会发生先读后写的情况，而此时由于缓冲区为空，该读数据进程就会被阻塞。
解决方案：
所以，我们要通过进程同步来解决此类问题。
与进程同步相关的也就是直接制约关系，指的是多个进程一起完成某个任务，这些进程因为合作、因为需要在某些位置上协调他们的工作次序而产生了某些制约关系。
1.2 进程互斥
问题：
在多道批处理系统中，多个进程是并发执行的，而并发执行的进程不可避免地需要共享一些系统资源（比如内存、打印机、摄像头等）。这样会带来什么问题呢？实际上，有些资源在一个时间段内只允许一个进程使用，诸如各种物理设备、变量、数据、内存缓冲区等，这些称之为临界资源 —— 也就是说，一方面，并发执行的进程需要共享资源；另一方面，临界资源的访问又必须是互斥地进行（不能同时共享），很显然，这会导致资源访问上的矛盾。
解决方案：
所以，我们要通过进程互斥来解决此类问题。
与进程互斥相关的也就是间接制约关系，指的是当 A 进程在访问某个临界资源时，另一个也想要访问该资源的 B 进程就必须等着，直到 A 进程访问结束并释放资源后，B 进程才能去访问。
基本实现逻辑：
为了实现临界资源的互斥访问，可以在逻辑上将一个进程对临界资源的访问过程分为四个部分：
do {
extry section; // 进入区
critical section; // 临界区
exit section; // 退出区
remainder section; // 剩余区
} while(true)- 进入区：A 进程想要访问临界资源，首先会在进入区检查是否可以进入，由于此时没有其它进程占用临界资源，所以检查通过，同时它设置了一个 Flag 标志当前自己正在访问临界资源；
- 临界区：实际访问临界资源的那段代码
- 退出区：负责解除之前的 Flag
- 剩余区：其它处理
对于 B 进程，如果此时它也想要访问这个资源，同样就会在进入区做一个检查，它知道了 A 进程正在访问，所以自己就不能访问了。这样就实现了资源访问的互斥。
四个原则：
更加具体的细节，我们需要用四个原则来约束这个互斥的过程：
- 空闲让进：临界区空闲时，说明没有进程使用临界资源，此时应该让想要进入临界区的进程立刻进来
- 忙则等待：如果已经有进程进入临界区，则其它同样想要进入的进程只能等着
- 有限等待：不能让进程一直干等着，要保证他在有限的时间内可以进入临界区
- 让权等待：当 A 进程进入临界区而导致 B 进程不能进入自己的临界区时，应该立刻释放处理机，防止进程陷入“忙等”状态。
2. 如何实现进程互斥
2.1 软件层面如何实现进程互斥
① 单标志法：
单标志法的核心是用一个 Flag 来标志哪个进程可以进入临界区，在初始给定 Flag 的情况下，一定可以确保是 Flag 对应的进程可以进入临界区。而在该进程顺利进入并完成自己的任务后，它会将 Flag 改指向另一个进程。我们通过一个例子来说明：
int turn = 0;
P0 进程： P1 进程：
while (turn != 0); while (turn != 1);
critical section; critical section;
turn = 1; turn = 0;
remainder section; remainder section;在一开始我们置 Flag 指向 0 号进程。设想有两种可能：一种是 P0 进程先上处理机，那么此时不满足 while 条件，则顺利进入自己的临界区；另一种是 P1 进程先上处理机，尽管如此，由于满足 while 条件，所以陷入了死循环，一直无法进入临界区，直到消耗完了自己的时间片，轮到了 P0 运行。P0 由于不满足循环条件，所以顺利进入临界区。值得注意的是，在这个过程中，即使由于 P0 消耗完了时间片而导致处理机使用权转让给了 P1，P1 也不会实际进入临界区，而是不断循环 —— 这就确保了整个过程中，即使进程不断来回切换，始终都只有 P0 在使用临界资源，也就是做到了我们所要的“互斥访问资源”。
但问题在于，观察整个过程会发现，P0 完成任务后将“使用权限“（Flag）转交给 P1，而 P1 完成后也转交给 P0，所以整个过程一直都是 P0 ——> P1 ——> P0 ——> P1… 这样交替进行，也就是说，即使 P0 运行完之后想要再次运行，它也不得不先等待 P1 的完成。
另一个问题是，P0 如果一直不访问临界区，那么就算此时临界区空闲、且 P1 有意愿想要访问临界资源，P1 也无法访问，也就是**”空闲不让进“**。这很明显违背了上面所说的”空闲让进“原则。
② 双标志先检查法：
双标志法不是用一个 Flag 来指示哪个进程可以进入临界区，而是为每个进程都设置一个可以起到开关作用的 Flag。它的核心是，初始所有的进程 Flag 都为 false，表示暂时都不想进入临界区。某一时刻有个进程想要进入了，他首先会检查当前是否有其他进程正在占用，有的话就作罢，自己慢慢等，没有的话就自己进入，一进入就马上打开 Flag 开关为 true，相当于”上了一把锁“，这期间只有自己拥有占有权，其他进程都是进不来的。在自己完成任务后，再置 Flag 为 false，相当于释放了占有权（把锁打开）。我们通过一个例子来说明：
bool flag[2];
flag[0] = false;
flag[1] = false;
P0 进程： P1 进程：
while (flag[1]); while (flag[0]);
flag[0] = true; flag[1] = true;
critical section; critical section;
flag[0] = false; flag[1] = false;
remainder section; remainder section;这里的过程还是和之前一样的，即使其它进程被调度，也会陷入死循环而消耗完自己的时间片，所以看起来是可以实现互斥的了。
而且，注意这里单个进程释放”权限“的不同。单标志法的释放”权限”，是把“权限”交给一个指定的进程，这说明了另一个进程想要得到“权限”，必须经过这个进程的同意（所以才有了交替运行的问题）；但是由于双标志法设置的是可以起到开关作用的 Flag，所以所谓释放“权限”不过是放开了自己的权限，其它进程想要进入临界区只管进入就可以，不用非要这个进程进行指定，所以，这个方法不会有交替运行的问题，他在一定程度上做到了解耦。
问题在于，检查 与 上锁 并不是一个原子操作，它是可以被打断的 —— 这意味着，在检查之后、没来得及上锁之前，如果进程突然切换到 B 进程，那么 B 进程就会在 A 进程“上锁”之前抢先跳过本该陷入的死循环。之后，不管进程有没有再次切换回去，对于 A、B 进程来说，它们都跳过了循环，这意味着它们都可以顺利进入临界区，进而同时使用临界资源。换句话说，双标志先检查法并不能保证互斥访问资源，它违背了“忙则等待”的原则。
③ 双标志后检查法
双标志后检查法与先检查法的区别在于，它是先“上锁”后“检查”。也就是说，先检查法的问题在于“上锁”上得太慢，给其他进程可乘之机，所以后检查法决定不管怎么样，先上了锁再说。看下面这个例子：
bool flag[2];
flag[0] = false;
flag[1] = false;
P0 进程： P1 进程：
flag[0] = true; flag[1] = true;
while (flag[1]); while (flag[0]);
critical section; critical section;
flag[0] = false; flag[1] = false;
remainder section; remainder section;后检查法解决了“忙则等待”的问题，但又违背了“空闲让进”和“有限等待”的原则 —— 由于非原子操作而引起的根本问题并未得到解决，因此极有可能导致两个进程都无法进入临界区。
比方说，P0 想要进入临界区，那么他就会抢先“上锁”，而由于“上锁”和“检查”之间有空隙，如果进程 P0 在这段空隙切换到了 P1，那么 P1 也会进行“上锁”。此后，无论进程是否有切换回去，双方都会陷入死循环无法自拔（因为此时双方都拿到了“上锁”的机会，锁死别人，也锁死了自己），进而导致谁都无法进入临界区，产生“饥饿”现象。
④ Peterson 算法
Peterson 算法实际上同时结合了单标志法和双标志后检查法，它的核心就是：在一开始还是和后检查法一样，抢先进行“上锁”，但是上锁之后又将 turn 置为对方线程，表示自己虽然想要进入临界区，但是不介意“将这个机会让给对方”。尽管如此，由于 while 的限制条件增加了，而 turn 又是公用的，所以保证了最后只会有一方的 while 满足条件。既做到了互斥访问资源，也避免了双方都访问不到资源。
还是来看下面这个例子：
bool flag[2]; flag[0] = false; flag[1] = false;
int turn = 0;
P0 进程： P1 进程：
flag[0] = true; flag[1] = true;
turn = 1; turn = 0;
while (flag[1] && turn == 1); while (flag[0] && turn == 0);
critical section; critical section;
flag[0] = false; flag[1] = false;
remainder section; remainder section;首先进入后检查法的情况，即：P0 首先表示想要进入临界区，因此它的 Flag 为 true，之后进程切换来到了 P1，P1 也表示自己想要进入临界区，因此它的 Flag 也是 true。
在后检查法中，这种情况注定了双方都陷入死循环，谁也无法进入。但是 Peterson 算法却不一样。
在这个算法中，**对方进程想进入、且最后一个做出“谦让”的进程最终将无法进入临界区。**继续上面的例子，此时可能：
继续执行
turn = 0，while (flag[0] && turn == 0)，由此进入了死循环，于是时间片用完后来到了 P0，P0 执行turn = 1，while (flag[1] && turn == 1)，同样进入了死循环，于是时间片用完后来到了 P1，注意，此时对于 P1 来说，它的 while 条件不满足，所以顺利进入了临界区，直到运行完释放“权限”，P0 的才有机会跳出自己的死循环。这种情况，由于 P0 是最后一个“谦让”的，所以是对方 P1 进入临界区
或者，切换到 P0 执行
turn = 1，while (flag[1] && turn == 1)， 由此进入了死循环，于是时间片用完后来到了 P1，执行turn = 0，while (flag[0] && turn == 0)，同样进入了死循环，于是时间片用完后来到了 P0，此时对于 P0 来说，while 条件已经不满足，所以 P0 得以顺利进入临界区。这种情况，由于 P1 是最后一个“谦让”的，所以是对方 P0 进入临界区
And others …
考虑到进程并发的异步性，其实有很多种排列组合的情况，但是不管哪种情况，可以肯定的是：即使双方都想进入临界区，由于 turn 只有一个，也肯定有一方可以顺利跳出死循环，进入临界区。这就避免了“饥饿”现象的产生；同时，只要自己进程临界区没执行完，就永远不会释放”权限“，意味着对方进程不会乘机抢着进入临界区，这就保证了”互斥“。
用一个生活案例来解释，可能更好理解：
甲乙两个人同时去图书馆借一本书，甲说：”我很想看这本书，但是你想看的话，我不介意让你先看“，而乙也说：”我也很想看这本书，但是你这么谦让我都不好意思了，还是你先看吧“，双方就这样互相你来我往。到最后甲也累了，于是在听到乙再次说了”让你先看“之后，甲拍了拍乙的肩膀，同时把书拿了过来，说：”好吧，那我先看吧，我看完，你再看。“
Peterson 算法解决了空闲让进、忙则等待、有限等待的问题，但还是没有解决让权等待的问题。也就是说，P1 进程尽管无法进入临界区，但是在时间片轮到自己的时候还是会做无意义的死循环，白白占用了处理机，而这些资源本该是给 P0 使用的。
2.2 硬件层面如何实现进程互斥
① 中断屏蔽方法
在双标志方法中，有可能出现两个进程同时进入临界区的情况，而中断屏蔽方法可以很好地避免这种情况。
它和原语的原理很像，一样是通过”开/关中断指令“，来实现原子操作。具体地说，就是让进程在进入临界区之前先执行关中断指令”上锁“，保证了此后整个执行过程不会被中断，自然也不会发生进程切换、两个进程同时访问临界资源的情况，在访问完临界区之后，再通过开中断指令”解锁“，这样其它进程才有机会访问临界区。
中断屏蔽方法的优点是简单高效，但是它不适用于多处理机，并且由于涉及到了开/关中断这两个特权指令的使用，所以其实这种方法只适用于内核进程，不能用于用户进程。
② TestandSetLock 指令
TestAndSetLock /TestAndSet 指令也叫 TSL/TS 指令。双标志方法的根本问题出在”上锁“和”检查“是非原子操作，导致某个进程可以利用这两个操作的空隙，而 TSL 指令将两个操作变成了原子操作（一气呵成，不留空隙），同时它也做到了像中断屏蔽指令那样，一旦进入临界区，执行过程就无法被中断。
虽然这是硬件操作，不过我们暂且用伪代码来进行理解：
bool TestAndSet (bool *lock){
bool old;
old = *lock;
*lock = true;
return old;
}
P0: P1:
while (TestAndSet(&lock)); while (TestAndSet(&lock));
critical section; critical section;
lock = false; lock = false;
remainder section; remainder section;其中，lock 是全局变量，记录当前临界区是否”上锁“。
首先，进程 P0 想要访问临界区，那么就会来到 while 循环，在这个循环里，它一气呵成完成了”上锁“和”检查“的工作 —— 循环里执行了 TSL 函数，一方面将全局 lock 改为 true，一方面返回旧的值为 false 的 lock 给自己。所以，对自己来说，由于返回的是 false，它得以跳过循环进入临界区；而对 P1 进程来说，每次切换到它这里，它在 while 里企图”上锁“和”检查“的时候，都会由于之前全局 lock 已经被置 true 而陷入死循环。
因此，整个过程就保证了 P0 的”上锁“和”检查“是一气呵成的原子操作，同时也让 P0 执行时绝对不会被切换。在 P0 执行完之后，全局 lock 再次置 false，以此类推。
TSL 指令的方法实现简单，无需严格检查逻辑，也适用于多处理机环境，但是它仍然不满足”让权等待“的原则 —— 从伪代码可以看出，P1 在无法如愿进入临界区后仍然可能白白地占用处理机，导致”忙等“。
③ Wrap 指令
Swap 指令或称 Exchange / XCHG 指令，它的逻辑其实和 TSL 指令差不多：
P0: P1:
bool old = true; bool old = true;
while (old == true) while (old == true)
Swap(&lock,&old) ; Swap(&lock,&old) ;
critical section; critical section;
lock = false; lock = false;
remainder section; remainder section;一开始全局 lock 还是 false，P0 想要进入临界区，首先置 old 为 true，后面用 Swap 完成交换，所以得以跳出循环进入临界区；而对于 P1 进程，由于它共享全局 lock，全局 lock = 自身 old = true，所以陷入了死循环，无法进入临界区。
和 TSL 指令一样，Swap 指令也无法解决“让权等待”的问题。
那么，是否有更加完善的方法来解决这个问题呢？
操作系统系列学习笔记：