第3章 进程同步
一、进程同步的基本概念
1.在多道程序环境下，进程之间可能存在两种关系：资源共享、相互合作
进程同步的任务就是：
在资源共享的情况下：保证诸进程以互斥的方式访问临界资源—必须以互斥方式访问的共享资源
在相互合作的关系中：进程同步的主要任务是保证相互合作的诸进程在执行次序上协调，（有些教材把这种功能称做“同步”）。相互合作的进程可能同时存在资源共享的关系
2.临界资源
多道程序系统中存在许多进程，它们共享各种资源，然而有很多资源一次只能供一个进程使用。一次仅允许一个进程使用的资源称为临界资源（以互斥方式访问的共享资源）。
许多物理设备都属于临界资源，如输入机、打印机、磁带机等。
对于临界区的访问过程分为四个部分：
进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志(可理解为“上锁")，以阻止其他进程同时进入临界区
临界区：在临界区做操作，访问临界资源的那段代码
退出区：清除临界区被占用的标志，负责解除正在访问临界资源的标志(可理解为“解锁”）
剩余区：进程与临界区不相关部分的代码
do {
entry section; // 进入区
critical section ; // 临界区
exit section; // 退出区
remainder section; // 剩余区
} while (true)
3.进程同步
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作
4.进程互斥
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:
1.空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2.忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待
3.有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
4.让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
二、进程互斥的软件实现方法
1.单标志法
在进入区只做"检查"，不"上锁"
在退出区把临界区的使用权转交给另一个进程
(相当于在退出区既给另一进程"解锁"， 又给自己"上锁")
主要问题:不遵循"空闲让进"原则
2.双标志先检查
在进入区先"检查"后"上锁"，退出区“解锁”
主要问题:不遵循"忙则等待"原则
3.双标志后检查
在进入区先"加锁"后"检查"，退出区"解锁"
主要问题:不遵循"空闲让进、有限等待"原则，可能导致"饥饿"
4.Peterson算法
在进入区"主动争取-主动谦让-检查对方是否想进、己方是否谦让”
主要问题:不遵循”让权等待"原则，会发生"忙等”
三、进程互斥的硬件实现方法
1.中断屏蔽方法
利用“开/关中断指令”实现
(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)
…
关中断; // 关中断后不允许当前进程被中断，也必然不会发生进程切换
临界区;
开中断; // 直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区
…
优点:简单、高效
缺点:不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)
2.TestAndSet指令 (TS指令/TSL指令)
TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成
相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作
优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境
缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
3.Swap指令(XCHG指令)
和TestAndSet 基本一致
四、信号量机制
信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为1的信号量
一对原语: wait(S) 原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal,括号里的信号量S其实就是函数调用时传入的一个参数。wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为P(S)、V(S)
1.整形信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
与普通整数变量的区别: 对信号量的操作只有三种，即初始化、P操作、V操作
int S = 1; // 初始化整型信号量s，表示当前系统中可用的打印机资源数
// wait 原语，相当于“进入区” ,“检查”和“上锁”一气呵成，避免了并发、异步导致的问题
void wait (int S) {
while (S <= 0); // 如果资源数不够，就一直循环等待
S=S-1; // 如果资源数够，则占用一个资源
}
// signal 原语，相当于“退出区”
void signal (int S) {
S=S+1; // 使用完资源后，在退出区释放资源
}
进程P0:
wait(S); // 进入区，申请资源
使用打印机资源… // 临界区， 访问资源
signal(S); // 退出区，释放资源
进程P1:
wait(S) ;
使用打印机资源…
signal(S);
存在的问题:不满足“让权等待”原则，会发生“忙等”
（既然wait原语不可被中断，那当前执行while的进程就一直不会被切换，怎么办？）
2.记录型信号量
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量
/*记录型信号的定义*/
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} semaphore;
/*某进程需要使用资源时，通过wait原语申请*/
void wait ( semaphore S) {
S.value--;
if(S.value<0){
// 如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列(即阻塞队列)中
block (S.L);
}
}
/*进程使用完资源后，通过signal原语释放*/
void signal (semaphore S) {
S.value++;
if (S.value <= 0) {
wakeup(S.L); // 释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
}
}
3.用信号量实现进程互斥
/*信号机制实现互斥*/
semaphore mutex=1; // 初始化信号
P1(){
...
P(mutex); // 使用临界资源前需要加锁
临界区代码段...
V(mutex); // 使用临界资源后需要解锁
...
}
P2(){
...
P(mutex);
临界区代码段...
V(mutex);
...
}
注意:对不同的临界资源需要设置不同的互斥信号量。
P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒
4.用信号量实现进程同步
进程同步:要让各并发进程按要求有序地推进, 让本来异步并发的进程互相配合，有序推进
/*信号量机制实现同步*/
semaphore S=0; // 初始化同步信号量，初始值为0
// 保证了代码4一定是在代码2之后执行
P1(){
代码1;
代码2;
V(S);
代码3;
}
P2(){
P(S);
代码4;
代码5;
代码6;
}
若先执行到V(S)操作，则S++ 后S=1。之后当执行到P(S)操作时，由于S=1，表示有可用资源，会执行S–，S的值变回0,P2进程不会执行block原语，而是继续往下执行代码4。
若先执行到P(S)操作，由于S=0，S-- 后S=-1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码2，继而执行V(S)操作，S++， 使S变回0,由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了
5.用信号量实现前驱关系
为每一对前驱关系设置同步信号量，初值为0
六、经典进程互斥同步问题
1.生产者消费者问题
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注: 这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
缓冲区是临界资源，各进程必须互斥地访问。
1.1 关系分析（找出题目中描述的各个进程，分析它们之间的互斥、同步关系）
两个进程：生产者、消费者
互斥关系：生产者-生产者，消费者-消费者
对生产者进程、消费者进程的“协调”，即：有产品时才能消费，无产品时，必须先生产后消费；有空间
时才能生产，空间满时，必须先消费再生产
1.2 整理思路（根据各进程的操作流程确定P、V操作的大致顺序）
生产者每次要消耗 ( P ) 一个空闲缓冲区，并生产( V )一个产品
消费者每次要消耗 ( P )一个产品，并释放一个空闲缓冲医( V )
往缓冲区放入/取走产品需要互斥
1.3 设置信号量 (设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少))
semaphore mutex = 1; // 互斥信号量， 实现对缓冲区的互斥访问
semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0; // 同步信号量，表示产品的数量，也即非空缓冲区的数量
producer () {
while (1) {
生产一个产品;
P(empty); // 消耗一个空闲缓冲区
P(mutex);
把产品放入缓冲区; // 实现互斥是在同一进程中进行一对PV操作
V(mutex);
V(full); // 增加一个产品
}
}
consumer() {
while(1) {
P(full); // 消耗一个产品(非空缓冲区)
P(mutex);
从缓冲区取出一个产品;
V(mutex);
V(empty); // 增加一个空闲缓冲区
使用产品;
}
}
// 实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V
2.读者-写者问题
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误
因此要求:
①允许多个读者可以同时对文件执行读操作
②只允许一个写者往文件中写信息
③任一写者在完成写操作之前不允许其他读者或写者工作
④写者执行写操作前，应让已有的读者和写者全部退出
2.1 关系分析（找出题目中描述的各个进程，分析它们之间的同步、互斥关系）
两类进程:写进程、读进程
互斥关系:写进程-写进程、写进程-读进程
读进程-读进程不存在互斥问题
2.2 整理思路（根据各进程的操作流程确定P、V操作的大致顺序）
写者进程和任何进程都互斥，设置一个互斥信号量rw,在写者访问共享文件前后分别执行P、V操作。读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw执行P、V操作。如果所有读者进程在访问共享文件之前都执行P(rw) 操作，那么会导致各个读进程之间也无法同时访问文件。
P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量count来记录当前有几个读进程在访问文件。
2.3 设置信号量 (设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少))
semaphore rw=1; // 用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 用于保证对count变量的互斥访问
writer() {
while (1) {
P(rw); // 写之前“加锁"
写文件...
V(rw); // 写之后“解锁"
}
}
reader() {
while (1) {
P(mutex); // 各读进程互斥访问count
if (count==0)
P(rw) ; // 第一个读进程负责“加锁"
count++; // 访问文件的读进程数+1
V(mutex);
读文件...
P(mutex); // 各读进程互斥访问count
count--;
if (count==0)
V(rw)
V(mutex);
}
}
潜在的问题:只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的
// 读写公平法：
semaphore rw=1; // 用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 用于保证对count变量的互斥访问
semaphore w = 1; // 增加一个互斥变量，用于实现“写优先”
writer() {
while (1) {
P(w);
P(rw); // 写之前“加锁"
写文件...
V(rw); // 写之后“解锁"
V(w);
}
}
reader() {
while (1) {
P(w);
P(mutex); // 各读进程互斥访问count
if (count==0)
P(rw) ; // 第一个读进程负责“加锁"
count++; // 访问文件的读进程数+1
V(mutex);
V(w);
读文件...
P(mutex); // 各读进程互斥访问count
count--;
if (count==0)
V(rw)
V(mutex);
}
}
七、管程
1.为什么要引入管程
信号量机制存在的问题:编写程序困难、易出错
1973年，Brinch Hansen 首次在程序设计语言(Pascal)中引入了“管程”成分, 一种高级同步机制
2.管程的定义
管程是一种特殊的软件模块，由这些部分组成:
1.局部于管程的共享数据结构说明
2.对该数据结构进行操作的一组过程
3.对局部于管程的共享数据设置初始值的语句
4.管程有一个名字
3.管程的基本特征:
3.1 局部于管程的数据只能被局部于管程的过程所访问
3.2 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3.3 每次仅允许一个进程在管程内执行某个内部过程
4.拓展1:用管程解决生产者消费者问题
monitor ProducerConsumer
condition full, empty; // 条件变量用来实现同步(排队)
int count=0; // 缓冲区中的产品数
// 把产品item放入缓冲区
void insert (Item item) {
if (count == N)
wait (full);
count++;
insert_ item ( item);
if (count == 1)
signal(empty);
}
// 从缓冲区中取出一个产品
Item remove () {
if (count == 0)
wait (empty);
count-- ;
if (count == N-1)
signal(full);
return remove_ item();
}
end monitor;
//生产者进程
producer() {
while(1){
item = 生产一个产品;
ProdecerConsumer.insert(item);
}
}
//消费者进程
consumer() {
while(1){
item = ProdecerConsumer.remove( );
消费产品item;
}
}
5.拓展2: Java中类似于管程的机制
Java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用
static class monitor {
private Item buffer[] = new Item[N] ;
private int count = 0;
public synchronized void insert (Item item) {
// ...
}
}