DJ2-4 进程同步（第一节课）

2.4.1 进程同步的基本概念

1. 两种形式的制约关系

2. 临界资源（critical resource）

3. 生产者-消费者问题

4. 临界区（critical section）

5. 同步机制应遵循的规则

2.4.2 硬件同步机制

1. 关中断

2. Test-and-Set 指令

3. Swap 指令

4. 小结

进程的异步性必然导致若干进程对系统资源进行无序争夺，从而导致系统混乱。为保证多个进程能有条不紊地运行，在多道程序系统中，必须引入进程同步机制。

进程同步进制的主要任务：是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

2.4.1 进程同步的基本概念

1. 两种形式的制约关系

1）间接相互制约关系。由于共享系统资源。

2）直接相互制约关系。由于进程之间的相互合作。

2. 临界资源（critical resource）

一次仅允许一个进程访问的资源为临界资源。

3. 生产者-消费者问题

1）问题描述

有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有 n 个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。

2）解决方法

变量定义如下：

int in = 0;        //数组单元输入指针
int out = 0;       //数组单元输出指针
int count = 0;     //记录缓冲池产品数
item buffer[n];    //具有n个缓冲区的缓冲池

缓冲池是被组织成循环缓冲的。

在生产者进程中使用一个局部变量 nextp，用于暂时存放每次刚刚生产出来的产品；而在消费者进程中，则使用一个局部变量 nextc，用于存放每次要消费的产品。

生产者

void producer() {
    while(1) {

        //produce an item in nextp

        while(count == n);      //缓冲池已满，do no-op

        buffer[in] = nextp;     //放入产品
        in = (in + 1) % n;      //指向下一个数组单元
        count = count + 1;      //缓冲池产品数加一
    }
}

消费者

void consumer() {
    while(1) {
        while(count == 0);      //缓冲池已空，do no-op

        nextc = buffer[out];    //取出产品
        out = (out + 1) % n;    //指向下一个数组单元
        count = count - 1;      //缓冲池产品数减一

        //consume the item in nextc
    }
}

3）存在问题

虽然上面的生产者程序和消费者程序在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时就会出现差错，问题就在于这两个进程共享变量 count 。

假设 count 初值为 5 。生产者对它做加 1 操作，消费者对它做减 1 操作，这两个操作在用机器语言实现时，分别可用以下形式描述。

reg1 = count;       |reg2 = count;
reg1 = reg1 + 1;    |reg2 = reg2 - 1;
count = reg1;       |count = reg2;

祖传计组图。

实际执行时，由于时间片完可能导致两段程序中各语句穿插执行。

reg1 = count;        (reg1=5)
reg1 = reg1 + 1;     (reg1=6)
reg2 = count;        (reg2=5)
reg2 = reg2 - 1;     (reg2=4)
count = reg1;        (count=6)
count = reg2;        (count=4)

倘若再将两段程序中各语句交叉执行的顺序改变，将可看到其它答案。这表明程序的执行已经失去了再现性。为了预防产生这种错误，解决此问题的关键是把变量 count 作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量 count 。

4. 临界区（critical section）

把在每个进程中访问临界资源的那段代码称为临界区。

把一个访问临界资源的循环进程描述如下：

while(true) {
    进入区：检查有无进程进入。
    临界区：进程访问临界资源。
    退出区：将访问标志复位。
    剩余区：其它部分的代码。
}

5. 同步机制应遵循的规则

1）空闲让进

当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区。

2）忙则等待

当已有进程进入临界区时，其它试图进入临界区的进程必须等待。

3）有限等待

对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入 “死等” 状态。

4）让权等待

当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入 “忙等” 状态。

2.4.2 硬件同步机制

利用计算机硬件指令来解决临界区问题。对临界区管理时，将标志看作一把 “锁” 。

初始时锁是打开的。
进入临界区前，进程必须先进行 “锁测试” 。
“锁开” 则进入，“锁关” 则等待。
“锁开” 进入时，应立即将其锁上，以防止其它进程进入。
“锁测试” 和关锁操作必须是连续的（原子操作）。

计算机硬件提供了三大指令：关中断、Test-and-Set 指令、Swap 指令。

1. 关中断

原理：在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度。

缺点：

滥用关中断权利可能导致严重后果（与系统安全相关的中断无法被响应）
关中断时间过长会影响系统效率
不适用于多 CPU 系统（这个关了还有那个）

2. Test-and-Set 指令

TS 指令的一般性描述如下：

boolean TS(boolean * lock) {
    boolean old;
    old = * lock;
    * lock = true;
    return old;
}

利用 TS 指令实现互斥的循环进程结构可描述如下：

do {
    //...

    while TS(&lock);    //entry section
    //...               //critical section
    lock = false;       //exit section
    //...               //remainder section
} while(true);

do ... while ... 记得最后的分号。

在进入区，若恒有 lock == true，则代表临界区已上锁，其它试图进入临界区的进程必须等待。

3. Swap 指令

Swap 指令在 8086/8088 中又称为 XCHG 指令，用于交换两个字的内容。

Swap 指令的一般性描述如下：

void swap(boolean * a, boolean * b) {
    boolean temp;
    temp = * a;
    * a = * b;
    * b = temp;
}

为每个临界资源设置一个全局的 boolean 变量 lock，其初值为 false（代表没有上锁）。再设置一个局部的 boolean 变量 key 。利用 Swap 指令实现互斥的循环进程结构可描述如下：

do {
    key = true;
    do {                //entry section
        swap(&lock, &key);
    } while(key != false);
    //...               //critical section
    lock = false;       //exit section
    //...               //remainder section
} while(true);

由于 lock 的初值为 false，因此第一个进入临界区的进程内循环一次即退出循环。此时，lock 值为 true，其它试图进入临界区的进程将一直在内循环中循环。直到第一个进入临界区的进程执行到退出区，lock 值被设置为 false 。