同步与互斥

本节导读

大纲的「同步与互斥」列了：基本概念、基本实现方法（软件方法、硬件方法）、锁、信号量、条件变量、经典同步问题（生产者-消费者、读者-写者、哲学家进餐）。学完这一节，给你一个生活化的情境，要能用信号量和 P、V 操作写出各进程的同步代码。

学完你应该能判断一种互斥方法违背了哪条准则，能说出信号量的值表示什么，并能按「找关系、设信号量、写代码、查死锁」四步写出同步算法。

临界区与互斥的实现

一次只允许一个进程使用的资源叫临界资源，访问临界资源的那段代码叫临界区。进程间的关系有两种：同步（直接制约，进程之间按一定次序协作）和互斥（间接制约，争用同一临界资源）。访问临界区的代码分为进入区、临界区、退出区、剩余区，进入区和退出区要遵循四条准则：

• 空闲让进：临界区空闲时，允许一个请求的进程立即进入；
• 忙则等待：已有进程在临界区时，其他进程必须等待；
• 有限等待：请求进入的进程要在有限时间内进入，不会饥饿；
• 让权等待：进不了临界区时应立即释放处理器，不要忙等。

方法	做法	问题
单标志法	用 turn 指定轮到谁	必须轮流进入，违背空闲让进
双标志先检查法	先查对方标志，再置自己的标志	两进程可能同时进入，违背忙则等待
双标志后检查法	先置自己的标志，再查对方标志	可能都进不去，违背空闲让进和有限等待
Peterson 算法	置自己的标志，并把 turn 让给对方，对方想进且轮到对方时才等待	满足前三条，仍是忙等，不满足让权等待
关中断	进入前关中断，退出后开中断	只适合单处理机，关中断时间长会影响系统
TestAndSet、Swap 指令	用一条不可分割的指令读出并设置锁	适合多处理机，仍是忙等

/* Peterson 算法，进程 i 的代码（另一个进程为 j） */
flag[i] = true;                    /* 表示自己想进 */
turn = j;                          /* 谦让：先让对方 */
while (flag[j] && turn == j) ;     /* 对方想进且轮到对方时等待 */
/* 临界区 */
flag[i] = false;                   /* 退出区 */

锁、信号量与条件变量

互斥锁用 acquire 获得、release 释放；获得不到时一直循环等待的叫自旋锁，适合多处理机上很短的临界区。

信号量 S 只能用两个原子操作访问：P 操作（wait）申请一个资源，V 操作（signal）释放一个资源。整型信号量在 S 不大于 0 时循环等待，不满足让权等待；记录型信号量含一个整数值和一个等待队列：

void P(semaphore S) {
    S.value--;
    if (S.value < 0) block(S.list);     /* 资源不够，进程阻塞并让出 CPU */
}
void V(semaphore S) {
    S.value++;
    if (S.value <= 0) wakeup(S.list);   /* 还有进程在等，唤醒一个 */
}

value 大于 0 时表示可用资源数；小于 0 时，其绝对值是在该信号量上阻塞等待的进程数。用法：互斥时设 mutex 初值 1，P、V 夹住临界区；同步时设 S 初值 0，「前操作之后 V，后操作之前 P」；有若干个同类资源时初值设为资源数。

管程把共享数据和对它的操作封装在一起，每次只允许一个进程在管程内执行，互斥由管程自动保证。管程内用条件变量实现同步：x.wait 让调用进程阻塞在 x 上并释放管程；x.signal 唤醒一个在 x 上等待的进程，若没有进程等待则什么也不做。条件变量没有值，不像信号量那样「记账」。

经典同步问题

生产者-消费者：n 个缓冲区，生产者放、消费者取。设 mutex = 1（互斥访问缓冲区）、empty = n（空缓冲区数）、full = 0（满缓冲区数）。申请资源的 P 操作必须放在申请互斥的 P(mutex) 之前，否则缓冲区满时生产者占着 mutex 等 empty，消费者又等 mutex，就死锁了；V 操作的顺序无关紧要。

读者-写者（读者优先）：多个读者可以同时读，写者与任何人互斥。设 rw = 1（读写互斥）、count = 0（读者个数）、mutex = 1（保护 count）。第一个读者 P(rw) 把写者挡在外面，最后一个读者 V(rw) 放写者进来。只要不断有读者到来，写者就会一直等待；再加一个信号量 w 让写者到来后挡住新读者，可以实现写者优先或读写公平。