0 知识总览

1 进程互斥的软件实现方法

1.1 单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。（每个进程是否能进入临界区，其实这件事，是另一个进程说了算的，两个进程会交替的使用临界区）

turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按P0→P1→P0→P1→.…这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。
因此，单标志法存在的主要问题是：违背“空闲让进”原则。

turn的初值为0，即刚开始只允许0号进程进入临界区。
若P1先上处理机运行，则会一直卡在⑤序号语句处。直到P1的时间片用完，发生调度，切换P0上处理机运行。
代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回P1，P1依然会卡在⑤。
只有P0在退出区将turn改为1后，P1才能进入临界区。

单标志法可以实现所谓的互斥，也就是同一时刻最多只允许一个进程访问临界区。

1.2 双标志先检查法

会设置一个标志数组，当数组元素对应为true，就会让几号进程进入临界区。之后，在每一个进程想进入临界区之前，会把这个标志改成true，即可进入临界区，用这种方式告诉别的进程，我想进入临界区。当访问完临界区之后，会把对应的标志位改成false。

但是也有一个问题，进程并发执行，当一个进程在访问临界区，另一个进程可能也会同时访问临界区，这就违背了忙则等待的原则。

原因在于，进入区的“检查”（检查别的进程是否想进入临界区）和“上锁”（告诉别的进程此时我想进入临界区）两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换，从而导致了违背忙则等待的原则。

1.3 双标志后检查法

基于上述的改进，先上锁（先把坑占了），后来检查的方法。但是，也有问题，进程并发执行，两个进程都设置为true，那么到底是哪个进程进入临界区呢？这样循环会一直进行下去，因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

1.4 Peterson(皮特森)算法

算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”主动让对方先使用临界区。

还是会设置数组，表示意愿，还会有turn，表示是哪个进程，在下方会修改turn的数值。

两种双标志法的问题都是由于进入区的几个操作不能一气呵成导致的。我们可以推理验证在Peterson算法中，两个进程进入区中的各个操作按不同的顺序穿插执行会发生什么情况：
①②③⑥⑦⑧.
①⑥②③.
①③⑥⑦⑧.

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

2 总结

先区分哪个是进入区，做了哪些事情，然后模拟并发环境下是否产生了新的问题，这就是进程互斥分析的思路。