2.4　进程同步

本节概览：先建立「进程同步」的框架，再依次展开下列小节。

1. 进程同步的基本概念
2. 硬件同步机制
3. 信号量机制
4. 信号量的应用
5. 管程机制

多个程序并发执行时，会因共享资源或相互合作而形成两种制约关系。共享的 CPU、I/O 设备等临界资源需要由系统统一分配；合作进程之间则存在直接的工作依赖。

相关变量声明为：Int in=0, out=0, count=0; Item buffer[n]。

考察生产者进程先执行左列三条语句 VS 消费者进程先执行右列三条语句的执行情况。

临界资源（Critical Resource）是指一段时间内只允许一个进程访问的资源。许多硬件资源如打印机、磁带机等都属于临界资源，各进程间应采取互斥方式实现共享。

以生产者-消费者（Producer-Consumer）问题为例：为使二者并发执行，在两者间设置一个具有n个缓冲区的缓冲池。生产者进程将产品放入缓冲区，消费者进程从缓冲区取走产品，两者异步运行但必须保持同步。

不允许消费者去空缓冲区取产品，也不允许生产者向已装满产品且尚未被取走的缓冲区投放产品。

为实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程的运行。所有同步机制都应遵循下述四条准则。

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

不论是硬件临界资源还是软件临界资源，多个进程必须互斥地访问它。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。

进程中除进入区、临界区及退出区之外的其它部分代码称为剩余区。

访问临界资源的循环进程描述为：While(TRUE){ 进入区(entry section) 临界区退出区(exit section) 剩余区 }。

利用软件方法解决进程互斥进入临界区的问题有一定难度且存在很大局限性，现已很少采用。目前许多计算机提供特殊的硬件指令，可对一个字的内容进行检测和修正，或对两个字的内容进行交换，用以解决临界区问题。

关中断方法：在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才打开中断。进程在临界区执行期间计算机系统不响应中断，从而不会引发调度，也不会发生进程或线程切换，保证了锁测试和关锁操作的连续性与完整性。

关中断是实现互斥的最简单方法之一，但存在许多缺点。

1. 滥用关中断权力可能导致严重后果
2. 关中断时间过长会影响系统效率，限制处理器交叉执行程序的能力
3. 关中断方法不适用于多CPU系统，一个处理器上关中断不能防止进程在其它处理器上执行相同的临界段代码

该指令称为对换指令，在Intel 80x86中又称为XCHG指令，用于交换两个字的内容。

Void swap(Boolean *a, Boolean *b) {
    Boolean temp;
    temp= *a;
    *a= *b;
    *b=temp;
}

利用Swap指令实现进程互斥的循环进程：Do{ key=TRUE; do{ swap(&lock,&key); }while(key!=FALSE); 临界区操作; lock=FALSE; … }while(TRUE)。

这是一种借助一条硬件指令——「测试并建立」指令TS(Test-and-Set)实现互斥的方法。

TS指令的一般性描述：

Boolean TS(Boolean *lock) {
    Boolean old;
    old= *lock;
    *lock=TRUE;
    return old;
}

用TS指令管理临界区时，为每个临界资源设置一个布尔变量Lock代表其状态，可看作一把锁。利用TS指令实现互斥的循环进程：Do{ … while TS(&lock); 临界区; Lock:=FALSE; 剩余区; }while(TRUE)。

1. Lock的两种状态：
2. lock=FALSE：资源空闲
3. lock=TRUE：资源正在被使用

AND同步，或称为同时wait操作，即Swait(Simultaneous wait)。

其基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要有一个资源未能分配给该进程，其它所有可能分配的资源也不分配给它。

整型信号量最初由Dijkstra定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作很长时间以来一直被称为P、V操作。

Wait和signal操作：

Wait(S) {
    while(S<=0);
    /*do no-op*/ S--;
}
Signal(S) {
    S++;
}

wait(S)和signal(S)是两个原子操作，在执行时不可中断。即当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。在Wait操作中，对S值的测试和做S:=S-1操作都不可中断。

记录型信号量机制是一种不存在「忙等」现象的进程同步机制。在采取「让权等待」策略后，会出现多个进程等待访问同一临界资源的情况。

Typedef struct {
    int value;
    struct process_control_block *list;
}
semaphore

Wait(semaphore *S) {
    S->value--;
    if(S->value<0) block(S->list);
}

Signal(semaphore *S) {
    S->value++;
    if(S->value<=0) wakeup(S->list);
}

S->value的初值表示系统内某类资源的数目，因而又称为资源信号量。

wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，每次只能对某类临界资源进行一个单位的申请或释放。一次需要N个单位时便要进行N次wait(S)操作——低效，甚至会增加死锁概率。

进程申请某类临界资源时，在每次分配之前都必须测试资源数量，判断是否大于可分配的下限值，决定是否予以分配。对AND信号量机制加以扩充，形成一般化的「信号量集」机制：Swait(S1,t1,d1,…,Sn,tn,dn); Ssignal(S1,d1,…,Sn,dn)。

信号量集机制是对 AND 信号量的扩充：每次可申请多个单位的资源，申请前先测试资源数量是否大于下限值。

一般形式：Swait(S1,t1,d1,…,Sn,tn,dn); Ssignal(S1,d1,…,Sn,dn)。

为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。

设Mutex为互斥信号量，初值为1，取值范围(-1,0,1)。

利用信号量还可以描述进程间的前趋关系。结合图2-14前趋图举例理解。

设有两个并发执行的进程P1和P2，P1中有语句S1，P2中有语句S2。为实现在S1执行后再执行S2，只需使P1和P2共享一个公用信号量S并赋予初值0，将signal(S)放在S1后面，而在S2前面插入wait(S)。

即在进程P1中：S1; signal(S); 在进程P2中：wait(S); S2。

管程由四部分组成，结合图2-15管程示意图理解。

1. 管程的名称
2. 局部于管程的共享数据结构说明
3. 对该数据结构进行操作的一组过程
4. 对局部于管程的共享数据设置初始值的语句

在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。若一个进程调用管程后在管程中被阻塞或挂起，期间若不释放管程，其他进程无法进入管程，被迫长时间等待。为此引入条件变量condition，管程中对每个条件变量都须予以说明，形式为：condition x,y。

x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，调用x.wait将自己插入到x条件的等待队列上，并释放管程。

x.signal：正在调用管程的进程发现x条件发生变化，调用x.signal，重新启动一个因x条件阻塞而挂起的进程。

进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了x.signal操作后，进程Q被重新启动，此时P和Q的执行和等待有以下两种处理方式。

1. P等待，直至Q离开管程或等待另一条件
2. Q等待，直至P离开管程或等待另一条件

管程作为一种同步工具，具有模块化、抽象数据类型、信息隐蔽等特性。

设置管程的目的在于解决共享资源的互斥使用问题；进程为主动工作方式，管程为被动工作方式；进程之间能并发执行，管程不能与调用者并发；进程具有动态性，管程则是一个资源管理模块。