| 缩写 | 全称 | 中文 |
|---|---|---|
| PCB | Process Control Block | 进程控制块 |
为保证多个进程有条不紊地运行，在多道程序系统中必须引入进程同步机制。 否则，进程对系统资源的无序争夺将造成系统混乱， 每次处理的结果显现出不可再现性。
生产者-消费者 (producer-consumer) 问题 输入进程 A 和计算进程 B 相互合作，它们共享一个缓冲区。 进程 A 作为生产者，通过缓冲区向进程 B 提供数据， 进程 B 作为消费者，从缓冲区取出数据并处理。 尽管两个进程以异步方式运行，但它们之间必须保持同步。 既不允许消费者进程到空缓冲区取产品， 也不允许生产者向装满尚未取走的产品的缓冲区中投放产品。
以生产者-消费者问题为例，用数组 buffer 表示具有 n
个缓冲区的缓冲池，并以循环队列形式组织数据的进出，变量 in
和 out分别表示队尾与队头。此外，引入计数器
count，其初值为 0。
// 共享变量
int in = 0, out = 0, count = 0;
item buffer[n];
// 生产者
void producer()
{
while (true) {
nextp = produce();
while (count == n) {}
buffer[in] = nextp
in = (in + 1) % n;
++count;
}
}
// 消费者
void consumer()
{
while (true) {
while (count == 0) {}
nextc = buffer[out]
out = (out + 1) % n;
--count;
consume(nextc);
}
}
虽然生产者与消费者的程序在顺序执行时是正确的，但并发执行就会出差错。
问题就在于这两个进程拥有共享变量。生产者执行 ++count，
而消费者执行 --count。这两个操作用底层语言可以描述为：
mov reg1 [count] mov reg2 [count] inc reg1 dec reg2 mov [count] reg1 mov [count] reg2
当这些语句之间交错执行，就会产生错误结果。如
; [count] = 5 mov reg1 [count] ; reg1 = 5 inc reg1 ; reg1 = 6 mov reg2 [count] ; reg2 = 5 dec reg2 ; reg2 = 4 mov [count] reg1 ; [count] = 6 mov [count] reg2 ; [count] = 4
先使 count 增加 1，再使它减 1，结果却是 4！
解决此问题的关键是把变量 count 作为临界资源处理，
即令生产者和消费者进程互斥地访问它。
临界区 (critical section)指进程中访问临界资源的那段代码。 每个进程在进入临界区前，应先检查欲访问的资源是否正被访问， 如果该资源正被访问，则不能进入临界区； 否则应当设置资源正被访问的标志，并进入临界区。 相应地，退出临界区后，应清除资源被访问的标志，表示资源现在可用。 在进入临界区前做检查的这段代码称为进入区 (entry section)， 退出后的代码则称为退出区 (exit section)。 与临界区无关的其它代码称为剩余区 (remainder section)。 一般地，访问临界资源的循环进程描述为：
while (true) {
entry_section();
critical_section();
exit_section();
remainder_section();
}
虽然可以用软件方法解决进程互斥进入临界区的问题，但有一定难度， 并且有很大局限性，故现在已很少采用。目前许多计算机提供了硬件指令， 可用于解决临界区管理问题。
管理临界区时，可将标志看做一个锁，锁开时进入并上锁，锁关时等待。 测试和关锁操作必须是连续的，不允许分开进行。
下面列举实现进程互斥的具体方法。
许多计算机都提供了硬件指令 TS (Test-and-Set) 以实现进程互斥。 这条指令可以看作一个不可分割的过程，即一条原语。
bool TS(bool *lock)
{
bool old = *lock;
*lock = true; // 上锁
return old; // 返回测试结果
}
相应的循环进程结构为：
while (true) {
while (TS(&lock)) {}
critical_section();
lock = false;
remainder_section();
}
硬件指令 swap 称为对换指令，在 Intel 80x86 中又称 xchg 指令， 用于交换两个字的内容。
void swap(bool *a, bool *b)
{
bool tmp = *a;
*a = *b;
*b = tmp;
}
相应的循环进程为：
while (true) {
key = true;
do {
swap(&lock, &key);
} while (key == true);
critical_section();
lock = false;
remainder_section();
}
TS 和 swap 指令能有效实现进程互斥，然而当临界资源忙碌时， 其它进程必须不断测试，处于“忙等”状态，不符合“让权等待”原则。
1965 年，荷兰学者 Dijkstra 提出信号量 (semaphores，字面意为旗语) 机制。
整型信号量定义为一个用于表示资源数目的整型量 s，
除初始化外，仅能通过两个原子操作 wait 和
signal 来访问。在荷兰语中，这两个操作称为 P
(passeren，通过)、V (vrijgeven，释放) 操作。
wait(s)
{
while (s ≤ 0) {}
--s;
}
signal(s)
{
++s;
}
s ≤ 0，就会不断测试， 不符合“让权等待”原则。
记录型信号量采取“让权等待”策略后，
会出现多个进程等待访问同一临界资源的情况。
为此，除了代表资源数目的整型变量 value 外，
还应增加一个进程链表指针 list，用于链接等待中的进程。
记录型信号量因它采用记录型的数据结构而得名。
typedef struct {
int value; // ≥ 0 时表示资源数, < 0 时其绝对值表示等待中的进程数
struct PCB *list; // 等待队列
} semaphore;
// 请求资源
wait(semaphore *s)
{
--s→value;
if (s→value < 0) // 资源分配完毕?
block(s→list); // 使用 block 原语自我阻塞，插入到等待链表中
}
// 释放资源
signal(semaphore *s)
{
++s→value;
if (s→value ≤ 0) // 仍有等待的进程?
wakeup(s→list); // 使用 wakeup 原语唤醒等待链表中的第一个进程
}
特别地，如果设 value 初值为 1，
则表示只允许一个进程访问临界资源，可用于进程互斥管理。
一般场合中，一个进程往往要获得两个或更多共享资源后才能执行任务。
假定两个进程 A, B 都要访问共享数据 D, E，为此，分别设置互斥信号量
Dmutex = 1 和 Emutex = 1，
在两个进程中包含相应的请求代码：
processA() processB()
{ {
wait(Dmutex); wait(Emutex);
wait(Emutex); wait(Dmutex);
... ...
} }
若进程 A 和 B 按下列次序操作：
A: wait(Dmutex); // Dmutex = 0 B: wait(Emutex); // Emutex = 0 A: wait(Emutex); // Emutex = -1, A 阻塞 B: wait(Dmutex); // Dmutex = -1, B 阻塞
最后，两个进程就处于僵持状态。在无外力作用下，两者都无法解除僵持。 称此时的进程 A，B 已进入死锁状态。 进程同时要求的共享资源越多，发生进程死锁的可能性就越大。
and 同步机制的基本思想是：将进程在整个运行过程中所需的全部资源， 一次性分配给进程。即对若干临界资源的分配采取原子操作方式： 要么全部分配，要么一个也不分配。这样就可避免上述死锁的发生。 为此在 wait 操作中增加了 “and” 条件，故称为 and 同步，或同时 (simultaneous) wait 操作。