一、进程并发执行

1.1问题的提出

并发是所有问题产生的基础，也是操作系统设计的基础。

1.2从进程的特征看待并发问题

• 并发
  进程的执行是间断性
  进程的相对执行速度是不可预测的
• 共享
  进程/线程之间的制约性
• 不确定性
  进程执行的结果与其执行的相对速度有关，是不确定的。

二、进程互斥

2.1 竞争条件

下面看一个打印机的例子：

1
说明：在打印的时候需要维护上面这样一个打印的目录，有一个打印机的守护进程管理此目录，其中存放了所有要打印文件的信息，当缓冲区中有某个文件的文件名时，打印机就工作。这里我们需要使用in来表示缓冲区中哪个槽是空的。加入进程A、B都需要打印了，进程A首先独到了in=7，之后应该把in的值更新为8才对，但是在更新之前进程A被切换下cpu，同时进程B上了cpu，也要读取in=7，于是两个进程都将要打印的文件信息送到了7这个单元槽，于是就将进程A的文件信息给覆盖掉了，于是进程A就再也得不到自己所要的结果了。

竞争条件：两个或多个进程读写某些共享数据，而最后的结果取决于进程的运行的精确时序。

2.2 进程互斥

• 由于各进程要求使用共享资源（变量、文件等），而这些资源需要排他性使用。个进程之间竞争使用这些资源，这一关系称为进程互斥。
• 临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。
• 临界区（互斥区）：各个进程中对某个临界资源实施操作的程序片段。

2.3 临界区（互斥区）的使用原则

2

• 没有进程在临界区时，想进入临界区的进程可进入
• 不允许两个进程同时处于其临界区中
• 临界区外运行的进程不得阻塞其他进程进入临界区
• 不得使进程无限期等待进入临界区

2.4 实现进程互斥的方案

• 软件方案
  Dekker解法、Peterson解法

• 硬件方案
  屏蔽中断、TSL（XCHG）指令

2.4.1 软件解法1

3
说明：如果free为true表示有进程在临界区，否则就没有进程在临界区，初值是false。假设进程P先上cpu，此时free初值为false，于是循环就结束了，此时如果P被切换下cpu，而进程Q上了cpu，判断之后free还是false，然后将free设置为true进入临界区；而此时如果Q被切换下cpu，P上了cpu，此时P将free还是设置为true后也进入临界区，于是在同一时刻这两个进程都在临界区中，就没有满足临界区的使用原则，是一个错误的解法。
解决： 如果我们将最开始的两条语句加锁，不允许在其中间中断。于是我们看到如果P将free设置为true之后，Q是不能进入到临界区的，其一直处于while循环中。

2.4.2 软件解法2

4
说明：如果turn为false，则P是不能进入临界区的，而Q恰恰相反，如果turn为true，则其也是不能进入临界区的。

2.4.3 软件解法3

5
说明：这里设置了两个标志位。当两个标志位的值是一样的时候就会让两个进程都不能进入临界区，这就会导致after you问题。

2.4.4 DEKKER算法

6
说明：在上个解法基础上增加了一个turn标志，用来解决after you问题。但是在最外层while内部还有一个while进行判断，用来判断是不是轮到自己执行了，一直循环直到其时间片被用完下cpu，这里有浪费的。如果都想进临界区，当turn为1时，Q就让出cpu，否则进入临界区。如果一直为1，则Q就一直在内部循环，即一直不能进入临界区。

2.4.5 PETERSON算法

7
说明：在上面的算法中由于内部循环会导致浪费。任何一个进程要想进入临界区，首先执行函数enter_region(i)，其中参数是进程号，如果运行完这个函数，则进入临界区，否则在函数内部等待。turn是一个共享的变量，如果两个进程都想进临界区，那么turn的值是后面进程的，于是while循环条件不成立，则先给turn赋值的进程先进临界区。

2.4.6 进程互斥的硬件解决方案1（中断屏蔽方法）

利用开关中断指令。即在进入临界区之前我们先把中断屏蔽掉，然后进入临界区进行相应的操作，出临界区时就开启中断（允许中断）。

• 简单、高效
• 代价高，限制cpu并发能力（临界区大小）
• 不适用于多处理器
• 适用与操作系统本身，不适于用户进程

2.4.7 进程互斥的硬件解决方案2（“测试加锁”指令）

8
说明：在这个指令中lock变量是一个共享变量，如果lock=0，则任何进程都可以将其置1，并进入临界区。如果lock=1，标明有其他进程在临界区中，不能进入临界区。如图所示，如果一个进程想进入临界区，则先复制lock的值并将其置为1，如果其为非零，则进入临界区，出临界区的时候将lock置为0。其本质是将总线锁住。而其中也有一个循环检测的过程，也是有点浪费时间的。

2.4.8 进程互斥的硬件解决方案3（“交换”指令）

9
说明：首先给寄存器中置1，然后交换锁变量和寄存器中的值，之后再判断寄存器中的值是否为零，如果是零，标明临界区中没有进程，可以进入。