计算机理论基础

操作系统（四）：进程互斥

整理《Operating System Concepts》 第七版第六章进程互斥部分的理论和概念，内容均为原书和中文版翻译的摘录，其中原书摘录部分由我 按个人理解简化、翻译为中文，可能存在一些不准确之处 。

生产者-消费者冲突模型

  • 生产者-消费者（producer-consumer） 问题：生产者进程产生用来被消费者进程消耗的数据，例如一个编译器产生汇编代码，此代码交由汇编器生成对象。生产者、消费者进程之间可通过共享内存来传递数据，可分为：
    • 无限缓冲（unbounded buffer） ：共享内存大小没有限制，当缓冲区为空时，消费者进程需要等待；生产者进程在任何时候都可以直接向缓冲区中投放数据而无需等待
    • 有限缓冲（bounded buffer） ：内存共享的缓冲区域大小固定，若缓冲区为空则消费者进程需要等待；若缓冲区已满则生产者进程需要等待。

雏形

  • 采用共享内存、有限缓冲的生产者消费者代码如下（原书 99 页第三章初次介绍共享内存模型时的代码）。共享缓冲通过循环数组和两个逻辑指针 in、out 实现，变量 in 指向缓冲中下一个空位，out 指向缓冲中的下一个待取走的数据位，(in+1)%BUFFER_SIZE == out 时缓冲区满。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define BUFFER_SIZE 10
typedef struct{
    ...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

// producer
item nextProduced;
while (true){
    while (((in + 1) % BUFFER_SIZE) == out) ;
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
}

// consumer
item nextConsumed;
while (true){
    while (in == out) ;
    nextConsumed = buffer[out];
    out = (out+1) % BUFFER_SIZE;
}
  • 上面的代码存在缺陷，生产者、消费者进程能够使用的最大缓冲区为 BUFFER_SIZE - 1，并且代码也没有解决生产者、消费者进程同时访问共享内存的问题。

改进

  • 为使进程能够使用全部缓冲区，使用一个初始化为 0 的整数变量 counter 记录当前缓冲区中的元素数量；每当生产者向缓冲区投放数据，counter 递增；当消费者从缓冲区取走数据，counter 递减。可修改上面代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// producer
while (true){
    while (counter == BUFFER_SIZE) ;
    buffer[in] = nextProduced;
    in = (in+1) % BUFFER_SIZE;
    counter ++;
}

// consumer
while (true){
    while (counter == 0) ;
    nextConsumed = buffuer[out];
    out = (out+1) % BUFFER_SIZE;
    counter --;
}
  • 以上代码可使用全部缓冲区资源，但当消费者进程和生产者进程并发执行时，涉及修改 counter 的语句执行顺序将由操作系统设定。由于 C 语言中 counter++ 将被拆分为 mov register, counter、inc register 和 mov counter, register 三句汇编指令，假设由于操作系统的调度，当前消费者进程和生产者进程分别执行到 counter++ 和 counter-- 的最后一条汇编指令处，则 counter 的值将不正确。
  • 竞争条件（race condition） ：多个进程同时访问和操作一个相同的数据，且执行结果和访问的特定顺序有关。
  • 进程同步（process synchronization） 和 协调（coordination） ：确保系统不同部分操作资源不会互相影响。

临界区

  • 系统中有 n 个进程{P0, P1, ..., Pn-1}，每个进程有一个代码段称为 临界区（critical section） ，在该区域中，不同的进程可能会改变相同的数据。临界区中应当最多同时存在一个进程。
  • 临界区问题 指设计一个使进程协作的协议：
    • 每个进程需先请求进入临界区（请求的代码称为 进入区，entry section ）；
    • 获得允许，进入临界区执行
    • 退出临界区（ 退出区，exit section ）
    • 执行剩余代码（ 剩余区，remainder section ）
  • 临界区问题的解决必须满足如下三个要求：
    • 互斥（mutual exclusion） ：若进程 Pi 正在其临界区内，则其他进程都不能在临界区中执行
    • 发展（前进，progress） ：如果当前没有进程在临界区内，并且有一些进程在请求进入临界区，则只有不处在剩余区的进程可以参与到选择（选择哪个进程进入临界区）中。这个选择不能被无限期推迟，即必须立刻作出决定。简单的说， 进入临界区请求的选择不应当受当前在剩余区执行进程的影响 。
    • 有限等待（bounded waiting） ：从一个进程发出进入临界区请求，到该请求被允许，这期间只能有有限的其它进程进入临界区。即保证了每个进程都有机会进入临界区而不会饥饿。
  • 假定每个进程的执行速度都不为 0，但是不能对 n 个进程的 相对速度（relative speed） 做任何假设。
  • 操作系统内部的临界区问题：操作系统内同一时刻可能有多个处于内核模式的活动进程，有两种方法解决。
    • 抢占内核（preemptive kernel） ：允许处于内核模式的进程被抢占。此模式可能导致竞争条件，在对称多处理器体系中，此模式更难设计。但此模式适合实时编程，响应更快（Linux 2.6之后内核和 Solaris、IRIX 均为抢占内核）。
    • 非抢占内核（nonpreemptive kernel） ：不允许处于内核模式的进程被抢占，处于内核模式的进程会一直运行，直到其退出内核模式、阻塞或者自动释放对 CPU 的控制。这种方式根本不会导致竞争条件的产生。Windows XP、Windows 2000 和传统 UNIX 均为非抢占内核。

Peterson 算法

  • Peterson 算法 是对基于软件的临界区问题的经典解答，但由于现代计算机体系结构执行基本语言指令的不同方式，该算法在此类机器上不能正确执行。
  • Peterson 算法仅适用于两个进程（P0和P1），它们都在临界区和剩余区间交替执行。以下当使用 Pi 表示一个进程时，使用 Pj 表示另一个（j == 1-i）。
  • Peterson 算法需要在进程间共享两个数据项：
    • int turn：指定哪个进程可以进入临界区，若 turn == i，则 Pi 被允许
    • boolean flag[2]：flag[i] 表示进程 i 已发出进入临界区请求
  • Peterson 算法中进程 Pi 的结构如下
1
2
3
4
5
6
7
8
do {
    flag[i] = TRUE;
    turn = j;
    while (flag[j] && turn == j);
    // 临界区
    flag[i] = FALSE;
    // 剩余区
} while (TRUE);
  • Peterson 算法正确性的证明：
    • 互斥：只有当 flag[j] == FALSE 或 turn == i 时 Pi 才进入临界区。假设 Pi 和 Pj 同时进入临界区，则 flag[0] == flag[1] == TRUE，因为 turn 只能为 0 或 1，所以只有一个进程（假设 turn == i）Pi 能够跳出 While 语句。此外，只要 Pi 在临界区内，flag[i] == TRUE && turn == i 就始终成立，所以 Pi 在临界区执行期间，Pj 将始终等待或执行剩余区内容。
    • 发展和有限等待：进程 Pi 仅在 flag[j] == True 且 turn == j 的情况下才会被阻塞，若 Pj 不准备进入临界区，则 flag[j] == False，此时 Pi 可以进入；若 Pj 当前也在请求进入临界区，则 flag[j] == True，此时由 turn 决定哪个进程进入临界区。假设此时 Pj 进入临界区，当 Pj 退出临界区时会设置 flag[j] 为 False 使 Pi 进入临界区；如果 Pj 剩余区执行速度非常快，又重新申请进入临界区，此时 Pj 设置 flag[j] 为 TRUE，同时 turn 被设置为 i。因此 Pi 一定会进入临界区（发展），并且最多需要等待一次。

Bakery 算法（补充）

  • Bakery 算法适用于 n 个进程的临界区问题。
  • 在进入临界区之前，进程需要申请一个号码，拥有最小号码的进程会被允许进入临界区。如果两个进程 Pi 和 Pj 申请到的号码相同（申请号码不是临界区，因此可能获得相同号码），则比较进程编号 i 和 j，编号小的先执行。
  • 进程可申请到的号码始终是递增的。定义元组比较为 (a, b) < (c, d) if a < c || a == c && b < d，定义最大值函数 max(a0, a1, ..., an-1) 为 a0 ~ an-1 中的最大值。
  • Bakery 算法使用的共享数据有：
    • boolean choosing[n]：choosing[i] == TRUE 表明进程 Pi 当前正在申请进入临界区或者正在临界区中执行
    • int number[n]：number[i] 为进程 Pi 当前申请到的号码
  • Bakery 算法流程如下
1
2
3
4
5
6
7
8
9
10
11
12
13
do {
    choosing[i] = true;
    number[i] = max(number[0], number[1], ..., number[n-1])+1;
    choosing[i] = false;
    for (j = 0; j < n; j++){
    // 此循环保证所有比当前进程持更高优先级的进程已离开临界区
        while (choosing[j]);
        while (number[j] != 0 && (number[j], j) < (number[i], i));
    }
    // 临界区
    number[i] = 0;
    // 剩余区
} while(1);
  • Bakery 算法正确性证明：
    • 首先，元组的大小比较和取号规则（只增）保证了全部进程都可维持一个严格递增的顺序，而不会出现两个进程地位相等的情况。
    • 互斥：假设进程 Pi 已进入临界区，则 for 循环保证了，当前所有进程，号码比 Pi 的号码小的进程均已不在临界区，而号码比 Pi 大的进程将因为 number[i] != 0 而被阻塞在它们自己的 for 循环中，因此仅有 Pi 可进入临界区。互斥条件满足。
    • 发展：假设一个进程 Pj 执行完临界区，则其进入剩余区之前将使 number[j] == 0，此时所有在等待进入临界区的进程中，按元组比较最小的那个进程将因为 number[j] == 0 而跳出 while 循环，此后它将跳过剩余的 for 循环（因为其它进程的元组均大于它）并进入临界区，而其它进程都将继续等待。因此在剩余区的进程（Pj）不会影响到进入临界区申请的选择。
    • 有限等待：假设一个进程 Pi 已经申请到号码 number[i]，此时所有后申请进入临界区的进程 Pj 都会有 number[j] > number[i]，且在 Pi 执行完临界区之前，Pj 都会因为 number[i] != 0 且 number[i] < number[j] 而阻塞。因此进程 Pi 至多等待 n-1 个进程即可进入临界区。

硬件同步

  • 无论软硬件方式，解决临界区问题都需要 锁（lock） ，所有解决方案都基于锁，且锁的设计可能非常复杂。进程在进入临界区之前获得锁，退出临界区时释放锁。
  • 硬件特性可以简化编程并提高效率。现代计算机系统提供了特殊硬件指令以允许程序 原子（atomically） 检查和修改字地内容或交换两个字地内容。以下的 TestAndSet() 和 Swap() 函数均为原子操作，即硬件保证了它们作为一个完整过程执行而不会被抢占。它们的定义如下：
1
2
3
4
5
6
7
8
9
10
boolean TestAndSet(boolean *target){
    boolean rv = *target;
    *target = TRUE;
    return rv;
}
void Swap(boolean *a, boolean *b){
    boolean temp = *a;
    *a = *b;
    *b = temp;
}
  • 仅使用 TestAndSet() 或仅使用 Swap() 都可以解决互斥问题。以下是单独使用这二者实现的互斥，但均未满足有限等待的要求：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// TestAndSet Lock
do {
    while(TestAndSetLock(&lock));
    // 临界区
    lock = FALSE;
    // 剩余区
} while(TRUE);

// Swap Lock
do {
    key = TRUE;
    while(key == TRUE)
        Swap(&lock, &key);
    // 临界区
    lock = FALSE;
    // 剩余区
} while(TRUE);
  • 使用 TestAndSet() 或 Swap() 也可以解决有限等待问题，以下是使用 TestAndSet() 实现的有限等待互斥，代码为进程 Pi 的结构，来自原书（英文版）第 199 页。可以看出，剩余区前的 while 循环保证一个进程 Pi 强制拉取了排在其后的进程 Pj 进入临界区（如果有的话），这保证了有限等待。使用到的共享数据有：
    • boolean waiting[n]：waiting[i] == TRUE 表明进程 i 已申请进入临界区并正在等待选择
    • boolean lock：lock 是进程间共享的锁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
do{
    waiting[i] = TRUE;
    key = TRUE;
    while (waiting[i] && key)    // 进程排队
        key = TestAndSet(&lock);
    waiting[i] = FALSE;          // 进程标注自己已进入临界区
    // 临界区
    j = (i+1) % n;
    while ((j != i) && !waiting[j])
        j = (j+1) % n;
    if (j == i)                  // 当前无其他进程排队则释放锁
        lock = FALSE;
    else
        waiting[j] = FALSE;      // 强制拉取后一个进程进入临界区
    // 剩余区
} while(TRUE);

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（三）：CPU 调度
此专栏的下一篇文章：操作系统（五）：进程同步

参考资料：《操作系统概念 英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/11/24/os-concepts-4/) 、作者信息（Forec）和本声明。

分享到