Process Synchronization in Operating System

1962 年，Dijkstra 离开数学中心进入位于荷兰南部的 Eindhoven Technical University 任数学教授。在这里，他参加了 X8 计算机的开发，设计与实现了具有多道程序运行能力的操作系统——THE Multiprogramming System（后面简称 THE）。狄克斯特拉在 THE 系统中所提出的一系列方法和技术奠定了计算机现代操作系统的基础，尤其是关于多层体系结构，顺序进程之间的同步和互斥机制这样一些重要的思想和概念都是狄克斯特拉在 THE 中首先提出并为以后的操作系统如 UNIX 等所采用的。

为了在单处理机的情况下确定进程能否占有处理机，狄克斯特拉将每个进程分为“就绪”（ready）、“运行”（running）和“阻塞”（blocking）三个工作状态：

• 由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。
  
• 当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程处于“就绪”状态。
  
• 当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞”状态，待造成其退出运行的条件解除，再进入“就绪”状态。
  

广义的进程同步包含两个概念：“互斥”和“同步”：

• 互斥是指某一资源同时只允许一个访问者对其进行访问，具有 唯一性和排它性 。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
  
• 同步是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的 有序访问 。比如，进程 A 产生数据，而进程 B 打印数据，显然进程 B 在打印之前必须等待，直到进程 A 已经产生一些数据。
  

一个比较好的临界区问题的解决方案应该满足下面三个要求：

1. 互斥 ：临界区内最多只有一个进程在运行，这是最基本的要求。
   
2. 有空让进 ：如果没有进程处于临界区内且有进程希望进入临界区，则只有那些不处于剩余区(remainder section)的进程可以决定哪个进程获得进入临界区的权限。也就是 在临界区外运行的进程不得阻塞其他进程进入临界区。 这个要求也称为“前进”要求。
   
3. 有限等待 ：不得使进程无限期等待进入临界区。
   

在描述算法时，我们只定义用于同步目的的变量，只描述一种典型的进程，它具有图 1 所示的通用结构。

为简化问题，只考虑同一时间仅有两个进程的临界区问题解决办法。两个进程分别标记为 $P_0$ 和 $P_1$ ，为了方便，当一个进程用 $P_i$ 表示时，另一个进程用 $P_j$ 表示，即有 $j=1-i$ 。

一种直观的解法（严格轮换法）是，让两个进程共享一个整数变量 turn，初始值为 0（或者 1），用于记录“轮到”哪个进程进入临界区。进程 0 离开临界区时，它将 turn 的值设置为 1，以便允许进程 1 进入临界区；进程 1 离开临界区时，它将 turn 的值设置为 0，以便允许进程 0 进入临界区。如图 2 所示。

不过，严格轮换法仅满足“互斥”和“有限等待”要求，不满足“有空让进”的要求。比如，当进程 0 离开临界区后，无法立刻再进入临界区（除非进程 1 进入一次临界区后，把 turn 修改为 0）。

1981 年，G.L.Peterson 发现了一种互斥算法可解决两进程的临界区问题，它同时满足“互斥”，“有空让进”，“有限等待”这三个要求，称为 Peterson算法 ，如图 3 所示。 在 Peterson 算法出现之前，T.Dekker 已经提出了解决两进程临界区问题的算法，称为 Dekker算法 。不过由于 Peterson 算法非常简洁，使得 Dedder 算法不再有任何新意。

Peterson 算法的思路是：进程共享两个变量：

boolean flag[2];   // 初始必须都为FALSE
int turn;          // 初始值无所谓，但两个进程初始值要不相同

为了进入临界区，进程 $P_i(i=0,1)$ 首先设置 flag[i]的值为 TRUE，且设置 turn 的值为 $j(j=1-i)$ ，从而表示如果另一个进程希望进入临界区，那么它能进入。如果两个进程同时试图进入，那么 turn 会几乎在同时设置成 $i$ 和 $j$ 。只有一个赋值语句的结果会被保持，另一个也会发生，但会立即被重写。最终的 turn 值决定了哪个进程能被允许先进入临界区。
当 $P_i$ 退出临界区时，它会设置 flag[i]为 FALSE，以允许进程 $P_j$ 进入临界区（进程 $P_j$ 进入临界区前会先测试 flag[i]，当它为 TRUE 时 $P_j$ 会一直等待）。

说明 1： 采用 Peterson 算法时，当进程 $P_0$ 进入了临界区，如果它停留在临界区的时间比较长，此时进程 $P_1$ 也要进入临界区，则它会一直不停地测试 while 中的条件，这会浪费 CPU 资源。
说明 2：图 3 所示算法中，子图 a)中对 turn 的赋值并不一定要写为“turn=1”，只要它和下一行 while 中的测试“turn==1”一致就行。比如，在赋值时可以写为“turn=3”，测试时写为“turn==3”即可，当然这个值要和图 b)中的不相同。在某些参考资料中，也可能见到如图 4 所示的 Peterson 算法，它也是正确的。

前面介绍的 Peterson 算法可以解决两个进程的临界区问题。这里将介绍 Lamport面包店算法 它可解决多进程临界区问题。

Lamport 面包店算法是一种用于面包店、冰淇淋店、熟食店、摩托车登记处等必须在混乱中找到顺序的场合中的调度算法。该算法为分布式环境而开发，但是这里只关心与集中式环境有关的算法特性。

Lamport 面包店算法的思想： 在进入商店时，每个客户接收一个号码。具有最小号码的客户先得到服务。然而，面包店算法不能保证两个进程（客户）不会收到同样的号码。在出现相同号码时，具有最小名称的进程先得到服务。即如果 $P_i$ 和 $P_j$ 收到同样号码，且 $i<j$ ，那么 $P_i$ 先得到服务。 由于进程名称是唯一的，所以这个算法是完全确定的。

进程之间共享下面数据：

boolean choosing[n];  //表示进程是否正在抓号。初值为false。若进程Pi正在抓号，则choosing[i]=true
int number[n];        //记录进程获得的号码。初值为0。若number[i]=0，则表示进程Pi没有抓号

为了方便，用符号 “(a, b) < (c, d)” 表示 “a < c” 或者 “a == c && b < d” 。

采用 Lamport 面包店算法，进程 $P_i$ 的结构如图 5 所示。

Lamport 面包店算法的最多等待次数为 $n-1$ 。

参考：操作系统概念（第六版），7.2

在 Lamport 发明面包店算法之前，Eisenberg 和 Mcguire 提出过解决 $n$ 个进程临界区问题的解决，称为 Eisenberg-Mcguire算法 。

和 Lamport 面包店算法一样，Eisenberg-Mcguire 算法的最多等待次数也为 $n-1$ 。这里不介绍它，可参考：操作系统概念（第六版），习题 7.5

前面介绍的那些方法都是临界区问题的软件解决方案，我们还可以利用硬件提供的指令来更有效地解决临界区问题。

可以借助下面这些硬件指令解决临界区问题：
(1) 测试并设置（Test-and-Set）；
(2) 获取并增加（Fetch-and-Increment）；
(3) 交换（Swap）；
(4) 比较并交换（Compare-and-Swap，CAS）；
(5) 加载链接/条件存储（Load-Linked/Store-Conditional，LL/SC）。

参考：
操作系统概念（第六版），7.3 同步硬件
现代操作系统（原书第 3 版），2.3.3 忙等待的互斥

信号量的值仅能由 P 操作和 V 操作来改变。P操作和 V 操作是不可中断的程序段，称为原语。在荷兰文中，“通过”叫 Passeren，“释放”叫 Vrijgeven，PV 操作因此得名。后文将用 wait 表示 P 操作，signal 表示 V 操作。

信号量（Semaphore）是一个资源计数器，(1) 当某进程获取某信号量时，信号量计数首先减 1，如果计数小于 0，那么该进程被阻塞（这个过程是 wait 操作）；(2) 当某进程释放某信号量时，信号量计数首先加 1，如果计数大于或等于 0，那么唤醒某个阻塞的进程并执行之（这个过程是 signal 操作）。

显然，对于信号量，有：
(1) 如果信号量 m 大于 0，表示还有 m 个资源可以访问，此时信号量进程等待队列中没有进程被阻塞，新的进程访问资源也不会被阻塞；
(2) 如果信号量 m 等与 0，表示没有资源可以访问，此时信号量进程等待队列中没有进程被阻塞，但新的进程访问资源会被阻塞；
(3) 如果信号量 m 小于 0，表示没有资源可以访问，此时信号量进程等待队列中有|m|个进程被阻塞，新的进程访问资源会被阻塞。

下面是信号量的简单语义实现。

typedef int semaphone;
semaphone S = N;                  // 信号量S初始化为可用资源的个数。如果用于互斥，则初始化为1

void wait(semaphone *ptrSem) {    // 即P操作，要实现为原子地，这里仅是介绍其语义
    while ((*ptrSem) <= 0) {
        ;                         // 忙等待，浪费CPU资源，后文将介绍更高级的实现
    }
    (*ptrSem)--;
}

void signal(semaphone *ptrSem) {  // 即V操作，要实现为原子地，这里仅是介绍其语义
    (*ptrSem)++;
}

可以用信号量解决 $n$ 个进程的临界区问题，这 $n$ 个进程共享一个信号量 mutex，并初始化为 1。每个进程的组织结构为：

do {
    wait(&mutex);
    // critical section
    signal(&mutex);
    // remainder section
} while (1);

还可以使用信号量解决其它进程同步问题。假如，考虑有两个并发进程：进程 $P_1$ 有语句 S1，而进程 $P_2$ 有语句 S2，假设 要求只有在 S1 执行后之后才执行 S2。 利用信号量很容易地实现这一要求。办法如下：让进程 $P_1$ 和 $P_2$ 共享一个共同的信号量 synch，且初始化为 0。在进程 $P_1$ 的语句 S1 后插入语句“signal(&synch);”，而有进程 $P_2$ 的语句 S2 前插入语句“wait(&synch);”。即：

// P1
    S1;
    signal(&synch);
    // others

// P2:
    wait(&synch);
    S2
    // others

由于 synch 初始化为 0，所以只有当进程 $P_1$ 调用 signal(&synch);（即执行 S1 后），才会执行 S2。

前面介绍的信号量简单实现的主要缺点是“忙等待”。如，当一个进程位于其临界区内时，任何其他试图进入临界区的进程都会连续地执行空循环（即 wait 实现中的 while 语句）。如果进程待在临界区的时间比较长，这会大大浪费 CPU 资源。

为了克服“忙等待”导致浪费 CPU 资源，可修改信号量操作 wait（P 操作）和 signal（V 操作）的定义。当一个进程执行 wait 操作时，发现信号量不为正，则它必须等待。然而，该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放入到与信号量相关的等待队列中，且该进程的状态被切换成阻塞状态。接着，控制被转到 CPU 调试程序，以选择另一个进程来执行。
一个进程阻塞且等待信号量 S，可以在其他进程执行 signal 操作之后被重新执行。该进程的重新执行是通过 wakeup 操作来进行的，该操作会让进程回到就绪状态。

为了实现这样定义的信号量，可以将信号量定义为：

typedef struct {
    int value;
    struct process *L;
} semaphore;

每个信号量都有一个整数值和一个进程链表，当一个进程必须等待信号量时，就加入到进程链表上。操作 signal 会从等待进程链表中取一个进程以唤醒。
信号量操作 wait 和 signal 可按如下来定义：

void wait(semaphore *ptrSem) {     // 即P操作，要实现为原子地，这里仅是介绍其语义
    ptrSem->value--;
    if (ptrSem->value < 0) {
        add this process to ptrSem->L;
        block();                    // 使当前进程进入阻塞状态，不会浪费CPU资源
    }
}

void signal(semaphore *ptrSem) {    // 即V操作，要实现为原子地，这里仅是介绍其语义
    ptrSem->value++;
    if (ptrSem->value <= 0) {
        remove a process P from ptrSem->L;
        wakeup(P);                  // 使进程P回到就绪状态
    }
}

假设缓冲区大小固定。如果缓冲区为空，那么消费者必须等待；如果缓冲区为满，那么生产者必须等待。

假定缓冲池有 n 个缓冲项，每个缓冲项能存一个数据项。
信号量 mutex 提供了对缓冲池访问的互斥要求，并初始化为 1。
信号量 empty 和 full 分别用来表示空缓冲项和满缓冲项的数量。信号量 empty 初始化为 n；而信号量 full 初始化为 0。

生产者进程和消费者进程的代码如图 8 所示。可以这样来理解代码： 生产者为消费者生产满缓冲项，消费者为生产者生产空缓冲项。

前面讨论的是单生产者和单消费者的情况，如果生产者有多个或消费者有多个，或缓冲区有多个，怎么解决呢？可参考，《UNIX 网络编程第 2 卷：进程间通信(第 2 版)》第 10 章。

Readers-Writers problems 是指：一个数据对象（如文件）可以为多个并发进程所共享，有的进程（称为读者）只需要读取共享对象内容，而有的进程（称为写者）需要更新共享对象。如何协调读者和写者？使得多个读者可以同时读文件，但写者在写文件时不允许有读者在读文件，同样读者在读文件时写者也不去能写文件。