整理《Operating System Concepts》 第七版第六章进程同步部分的理论和概念，内容均为原书和中文版翻译的摘录，其中原书摘录部分由我 按个人理解简化、翻译为中文，可能存在一些不准确之处 。
信号量
- 基于硬件的
TestAndSet() 和 Swap() 对应用程序员而言相对复杂，可使用 信号量（semaphore） 作为同步工具。信号量 S 是整数变量，除初始化外只能通过两个原子操作访问：wait() 和 signal()，在有些地方使用 P（测试） 和 V（增加）表示。所有关于信号量的讨论均已具备以下前提：在这两个原子访问操作中，对信号量整型值的测试和修改都是不可分的，也就是说，当一个进程修改某个信号量时，其他进程都不能同时操作该信号量。
- 信号量按值域可分为
- 计数信号量（counting semaphore） ：信号量值域不受限制。此类信号量用于控制访问具有若干个实例的某类资源，初始化信号量为可用资源的数量，进程通过调用
wait() 操作获取资源（此时信号量计数也随之减少），进程使用资源后通过 signal() 操作释放资源（信号量计数随之增加）。当信号量的值小于等于 0 时，所有调用 wait() 操作的进程会被阻塞，直到某个进程调用了 signal() 释放了可用资源。
- 二进制信号量（binary semaphore） ：信号量的值只能为 0 或者 1，该类信号量也称为 互斥锁（mutex locks） ，可提供互斥操作。对于多进程的临界区问题，可以使所有进程共享一个二进制信号量 mutex，每个进程进入临界区之前调用
waiting(mutex) ，离开临界区之前调用 signal(mutex)。
- 信号量按功能可分：
- 公有（互斥）信号量：多个进程均需要同一个信号量所代表的资源，信号量起到了互斥的作用
- 私有（同步）信号量：部分进程向信号量释放资源，其他进程向信号量请求资源，信号量起到了同步的作用，保证了进程之间执行的先后顺序
实现
- 信号量的主要缺点是 忙等待（busy waiting） ，当一个进程位于临界区内时，其它试图进入临界区的进程都陷入循环检查的状态。这样的信号量也称为 旋转锁（spinlock） ，它也具有优点：进程在等待锁时不会进行上下文切换（上下文切换可能会花费很长的时间），因此如果等待锁的时间较短则旋转锁更有效。旋转锁通常用于多处理器系统，一个线程在某个处理器旋转时，另一个线程在另一个处理器的临界区内执行。
- 修改
wait() 和 signal()：
- 进程执行
wait() 时若信号量值不为正则调用 block() 操作将其阻塞，阻塞操作包括：将该进程状态切换为等待，将该进程放到信号量内部的一个等待队列中。之后 CPU 调度程序选择另一个进程执行。
- 进程执行
signal() 操作后，信号量值会增加。同时若存在进程阻塞在信号量上，则操作系统从信号量内部等待队列中选取一个进程，调用 wakeup() 操作将其唤醒，唤醒操作包括：将该进程从等待状态切换到就绪状态、放入就绪队列中（根据 CPU 调度算法，CPU 不一定会选择这个线程立刻执行）。
- 信号量的
wait() 和 signal() 操作可定义如下，每个信号量包括一个整型值和一个 PCB 链表指针，使用 FIFO 队列可确保有限等待，但一般来说链表可以使用任何排队策略，信号量的使用方式和链表排队策略无关：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| typedef struct{
int value;
struct process *list;
} semaphore;
void wait(semaphore *S){
S->value--;
if (S->value < 0){
block();
}
}
void signal(semaphore *S){
S->value++;
if (S->value <= 0){
wakeup(P);
}
}
|
- 信号量的 关键在于它们的执行具有原子性 。在单处理器上，可在调用
wait() 和 signal() 时禁止中断，而在多处理器系统上，仍需要使用其它加锁计数（如旋转锁）来确保信号量的原子性，因此信号量本身的实现还是没有完全取消忙等，仅仅是 把忙等的状态从等待进入临界区转移到了临界区执行时 ，因为经过合理设计的临界区通常比较短，因此比简单的忙等效率高一些。但在临界区很长的情况下，因为采用了忙等，导致信号量极为低效。
死锁和饥饿
- 当两个或多个进程无限等待一个事件，而该事件只能由等待该事件的某个进程来触发（执行 signal 操作），这种情况下，这些进程称为 死锁（deadlocked） 。
- 链表的出入顺序对信号量有影响，如果采用 LIFO 顺序增加、取出进程，则可能导致 无穷阻塞（indefinite blocking） 或 饥饿（starvation） 。
经典同步问题
有限缓冲问题
- 进程互斥 中的生产者-消费者问题可以通过三个信号量解决：
- 二进制信号量
mutex 保证了对缓冲池访问的互斥
- 计数信号量
empty 和 full 表示缓冲区中空余数量和已有数据数量
- 生产者和消费者进程使用如下架构保证互斥和同步：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
do {
wait(empty);
wait(mutex);
signal(mutex);
signal(full);
} while(TRUE);
do {
wait(full);
wait(mutex);
signal(mutex);
signal(empty);
} while(TRUE);
|
读者-写者问题
- 一个数据库可以被多个并发进程共享，有的进程只需要读数据库，而有的进程需要读或写数据库。将只需要读权限的进程称为 读者（Reader） ，需要写权限的进程称为 写者（Writer） 。如果一个写者和其它进程（无论读写）同时访问共享对象，则可能导致混乱。
- 有多种优先级方案：
- 第一读者-写者问题 ：读者优先，如果当前获得数据库权限的是读者进程，则其它读者进程无需等待，读者进程只有在当前操作数据库的进程是写者的情况下才需要阻塞。
- 第二读者-写者问题 ：写者优先，任何在等待获取数据库权限的写者进程都将比其它正在等待的读者进程先获得权限。
- 第三读者-写者问题 ：前两种策略都会导致写者或者读者的饥饿，此策略将保证没有任何进程会被无限阻塞。
- 读者-写者问题在以下情况非常有效：
- 当进程可以按照对共享对象所需的读写权限划分时
- 当读者进程数比写者进程数多时：因为读写锁的建立开销比信号量或互斥锁要大，此开销可通过允许多个读者并发来弥补
第一读者-写者问题
- 读优先，只要当前有读者在操作对象，所有读者都可以加入操作而不必等待。
- 进程共享如下数据：
semaphore mutex, wrt：二者均初始化为 1，信号量 wrt 用作读写进程的互斥锁，信号量 mutex 则用于确保更新变量 readcount 时互斥。int readcount：跟踪当前有多少个进程正在读对象，初始化为 0。
- 写者-读者进程结构如下，代码来自原书（英文版）第 206 页。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
do {
wait(wrt);
signal(wrt);
} while(TRUE);
do {
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
} while(TRUE);
|
第二读者-写者问题
- 写优先，只要当前有写者在操作对象，所有写者都将排队等待，中间不允许读者插入。只有所有写者完成处理后，读者才有机会访问。
- 进程之间共享如下数据：
int readcount, writecount：readcount 记录当前正在等待读对象的读者数量，writecount 记录当前正在等待写对象的写者数量，均初始化为 0。semaphore rmutex, wmutex：确保更新变量 readcount 和 writecount 时的互斥，均初始化为 1。semaphore readTry：readTry 信号量用于声明有读者加入等待队列，确保读者和写者之间的互斥，初始化为 1。semaphore resource：resource 信号量用于确保写者和写者之间的互斥，初始化为 1。
- 读者-写者结构如下，基本算法来自维基百科。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
do{
wait(readTry);
wait(rmutex);
readcount++;
if (readcount == 1)
wait(resource);
signal(rmutex);
signal(readTry);
wait(rmutex);
readcount--;
if (readcount == 0)
signal(resource);
signal(rmutex);
} while(TRUE);
do {
wait(wmutex);
writecount++;
if (writecount == 1)
wait(readTry);
signal(wmutex);
wait(resource);
signal(resource);
wait(wmutex);
writecount--;
if (writecount == 0)
signal(readTry);
signal(wmutex);
} while(TRUE);
|
第三读者-写者问题
- 保证读者和写者均不会出现饥饿现象。
- 进程之间共享的信号量有：
int readCount：当前正在访问对象的读者数量Semaphore resourceAccess：资源的控制权限，使读者、写者互斥，初始化为 1Semaphore readCountAccess：保证对 readCount 操作的互斥，初始化为 1Semaphore serviceQueue：保持请求的顺序，维护先进先出特性，初始化为 1
- 读者-写者结构如下，基本算法来自维基百科。可能有多个进程在服务队列中等待，当前进入临界区的进程离开后，等待的进程就会接替离开的进程。当
serviceQueue 中阻塞了多个进程时，选择进程唤醒的顺序取决于信号量的链表，因此 serviceQueue 的链表必须维持 FIFO 特性才能保证不会导致饥饿 。因此，解决饥饿问题实际是由链表的 FIFO 带来的。另一个值得注意的地方是，无论写者还是读者，获得了服务队列的权限后，在获取资源控制权前都将禁止其他任何进程接受服务，而因为只有紧随写者进程的读者才需要获取资源权限，所以在此算法中读者可以同时并发访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
do {
wait(serviceQueue);
wait(readCountAccess);
if (readCount == 0)
wait(resourceAccess);
readCount++;
signal(serviceQueue);
signal(readCountAccess);
wait(readCountAccess);
readCount--;
if (readCount == 0)
signal(resourceAccess);
signal(readCountAccess);
} while(TRUE);
do {
wait(serviceQueue);
wait(resourceAccess);
signal(serviceQueue);
signal(resourceAccess);
} while(TRUE);
|
哲学家进餐问题
- 问题描述：假设有 5 个哲学家共用一个圆桌，每人左右两边各有一根筷子，哲学家之间不互相交流。当哲学家感到饥饿时会依次拿起自己身边的筷子（一次只能拿起一根筷子、不能从其它哲学家手中拿筷子），当哲学家同时拥有两根筷子时可以开始进餐，否则将等待空闲的筷子（且并不放下已握在手中的筷子），吃完后他将放下两只筷子。
- 一种简单方法是每根筷子使用一个信号量，哲学家通过
wait() 请求相应的筷子，通过 signal() 释放相应的筷子。
1
2
3
4
5
6
7
| do{
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
} while(TRUE);
|
- 上面的算法解决了筷子的互斥问题，但可能导致死锁。若五个哲学家同时拿起同一边的筷子，则所有人都将永远等待。可行的解决方法有：
- 最多只允许四个哲学家同时坐在桌上
- 只有两只筷子都可用时才允许一个哲学家拿起筷子，且拿起两只筷子的操作在临界区内进行
- 编号为奇数的哲学家先拿起左边的筷子再拿起右边的筷子，编号为偶数的哲学家先拿起右边的筷子再拿起左边的筷子
- Dijkstra解法：每个哲学家都先拿起身边编号较小的筷子，再拿起编号较高的筷子
- 使用 Dijkstra 解法的哲学家就餐问题解法如下，伪代码根据维基百科的算法描述编写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void philosopher(){
leftChopstickIndex = index;
rightChopstickIndex = (index + 1) % Philosophers;
firstIndex = min(leftChopstickIndex, rightChopstickIndex);
secondIndex = max(leftChopstickIndex, rightChopstickIndex);
do{
wait(chopstick[firstIndex]);
wait(chopstick[secondIndex]);
signal(chopstick[firstIndex]);
signal(chopstick[secondIndex]);
} while(TRUE);
}
|
专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（四）：进程互斥
此专栏的下一篇文章：操作系统（六）：管程（Monitor）
参考资料：《操作系统概念 英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne
原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/11/24/os-concepts-5/) 、作者信息（Forec）和本声明。