2.4 同步与互斥：软硬件实现、互斥锁与信号量

临界资源与临界区，同步与互斥的概念及四条准则；单标志法、双标志法、Peterson 算法；中断屏蔽、TestAndSet、Swap 硬件指令；互斥锁；整型与记录型信号量，用信号量实现互斥、同步与前驱关系。

基本概念

• 临界资源：一次仅允许一个进程使用的资源，如打印机、共享变量。对临界资源的访问，必须互斥地进行。在每个进程中，访问临界资源的那段代码称为临界区；
• 为了保证临界资源的正确使用，可把临界资源的访问过程分成 4 个部分：

do {
    entry section;       // 进入区：检查可否进入临界区，若能进入则设置"正在访问"标志（上锁）
    critical section;    // 临界区：访问临界资源的那段代码
    exit section;        // 退出区：清除"正在访问"标志（解锁）
    remainder section;   // 剩余区：代码中的其余部分
} while (true);

• 同步（直接制约关系）：为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。例如输入进程 A 通过单缓冲向进程 B 提供数据，缓冲区空时 B 不能取，缓冲区满时 A 不能放；
• 互斥（间接制约关系）：当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

互斥的软件实现

在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。下面的实验中，你来决定每一步由哪个进程执行（相当于模拟任意的进程切换），观察每种算法会出什么问题：

互斥的硬件实现

• 中断屏蔽方法：当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简方法是关中断。因为 CPU 只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完。缺点：限制了处理机交替执行程序的能力，执行的效率会明显降低；将关中断的权利交给用户则很不明智；不适用于多处理器系统（只能关闭当前 CPU 的中断）；
• 硬件指令方法：TestAndSet（TS / TSL）指令和 Swap 指令，这是原子操作，执行该代码时不允许被中断：

bool TestAndSet(bool *lock) {   // 由硬件实现，原子执行
    bool old = *lock;
    *lock = true;
    return old;
}
while (TestAndSet(&lock));      // 进入区：上锁并检查
critical section;
lock = false;                   // 退出区：解锁

硬件方法的优点：适用于任意数目的进程，而不管是单处理机还是多处理机；简单、容易验证其正确性；可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待；从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致”饥饿”现象。

互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁 acquire()；在退出临界区时释放锁 release()。每个互斥锁有一个布尔变量 available，表示锁是否可用。acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。这种类型的互斥锁也称自旋锁。自旋锁通常用于多处理器系统——一个线程可以在一个处理器上旋转，而不影响其他线程的执行；在单处理器上自旋锁只会浪费 CPU（直到时间片用完）。自旋锁的优点是进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高。

信号量

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语 wait(S) 和 signal(S) 访问，也可记为”P 操作”和”V 操作”。

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 S：

wait(S)   { while (S <= 0); S = S - 1; }   // 不满足"让权等待"，会忙等
signal(S) { S = S + 1; }

记录型信号量

记录型信号量是不存在”忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量 value 外，再增加一个进程链表 L，用于链接所有等待该资源的进程：

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

void wait(semaphore S) {        // P 操作：申请一个资源
    S.value--;
    if (S.value < 0) {
        add this process to S.L;
        block(S.L);             // 资源已分配完，自我阻塞，放弃处理机——遵循"让权等待"
    }
}
void signal(semaphore S) {      // V 操作：释放一个资源
    S.value++;
    if (S.value <= 0) {
        remove a process P from S.L;
        wakeup(P);              // 仍有进程在等待，唤醒其中一个
    }
}

用信号量实现互斥、同步与前驱关系

semaphore mutex = 1;            // 互斥：初值为 1（只有一个"进入许可"）
P1() { P(mutex); 临界区; V(mutex); }
P2() { P(mutex); 临界区; V(mutex); }

semaphore S = 0;                // 同步：初值为 0，要求 x 在 y 之前执行
P1() { …; x; V(S); …; }         // 前操作之后执行 V
P2() { …; P(S); y; …; }         // 后操作之前执行 P

• 互斥：P、V 操作在同一个进程中成对出现，夹着临界区；初值一般为 1；
• 同步：P、V 操作分别在不同进程中，“前 V 后 P”；初值一般为 0；
• 前驱关系：对前驱图中的每一条边 $a \to b$ 设一个初值为 0 的信号量，$a$ 执行完后 V 它，$b$ 执行前 P 它。

即时练习