2.3、进程同步

1、进程同步的基本概念

多道程序环境下，进程是并发执行的，不同进程间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，达到资源共享和进程协作，避免进程之间的冲突，引入了进程同步的概念。

（1） 临界资源

多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次只允许一个进程使用的资源成为临界资源。

对临界资源的访问，必须互斥的进行。每个进程中，访问临界资源的那段代码成为临界区。

为了保证临界资源的正确使用，可以把临界资源的访问过程分为四个部分。

1） 进入区。为了进入临界区使用临界资源，在进入去要检查可否进入临界区。

2） 临界区。进程中访问临界资源的那段代码。

3） 退出区。将正在访问临界区的标志清除。

4） 剩余区。代码中的其余部分。

do {

entry section;

critical section;

exit section;

remainder section;

}while (true)

（2） 同步

同步已成为直接制约关系，它是为完成某种任务而建立的两个或多个进程。这些进程因为需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是它们之间的相互合作。

（3） 互斥

互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此临界资源。

2、实现临界区互斥的基本方法

在进入区设置和检查一些标志来表名是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

（3） 硬件实现方法

本节对硬件实现的具体理解对后面的信号量学习很有帮助。计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，活着是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。

1） 中断屏蔽方法。当一个进程正在使用处理器执行他的临界区代码时，要防止去其他进程在进入其临界区访问的最简单方法就是禁止一切中断的发生，或称之为屏蔽中断、关中断。因为CPU只有在发生中断时引起进程的调度和切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利的执行完，然后再开中断。

这种方法限制了处理器交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再打开终端，则系统可能会因此终止。

2） 硬件爱你指令法。

TestAndSet指令：这条指令是原子操作。及执行该代码是不允许被中断。其功能是独处制定标志后把该标志设置为真。

Boolean TestAndSet( Boolean *lock){

Boolean old;

Old=*lock;

*lock=true;

Return old;

}

Lock为每个临界资源设置的共享布尔变量，true表示正在被占用，false表示没被占用。

While TestAndSet(&lock);

进程的临界区代码；

Lock=false；

进程剩余代码；

Swap指令：该指令的功能是交换两个字的内容。

Swap(Boolean a, Boolean b){

Boolean temp;

Temp= *a;

a=b;

*b=temp;

}

以上对TestAndSet和Swap指令仅仅是功能实现，并非软件实现定义，事实上他们是由硬件逻辑直接实现的，不会被中断。

硬件方法优点：使用与任意数目的进程，不管是单处理器还是多处理器：简单、容易验证其正确性。可以支持进程内有多个临界区，只需要为每个临界区设立一个布尔变量。

硬件方法的缺点：进程等待进入临界区时要耗费处理器时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

3、信号量

信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准原语wait和signal来访问，也可以记作p操作和v操作。

原语是指完成某种功能且不被分割不被中断执行的操作序列，有时也成为原子操作，通常可用硬件来实现完成某种功能的不可分割执行特性。

（1） 整形信号量

整形信号量被定义为一个用于表示资源个数的整型量S。

（2） 记录性信号量

记录性信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数的整型变量value外，再增加一个进程链表L，用于连接所有等待该资源的进程，记录型信号量是由于采用了记录型的数据结构得名。记录型信号量可描述为：

Typedef struct{

Int value；

Struct process * L；

}semaphore；

Wait操作，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程调用block原语，进行自我阻塞，放弃处理器，并插入到S.L中，可见该机制遵循了“让权等待”的原则。Signal 操作，表示进程释放一个资源，使系统中可供分配资源数增加一，故S.value++。若加1后仍是S.value<=0，则表示S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L中的第一个等待进程唤醒。

（3） 利用信号量实现同步

信号量机构能用于解决进程间各种同步问题。

（4） 利用信号量实现互斥

信号量机构能很方便的解决进程互斥问题。

互斥的实现是不同进程对同一信号量进行P操作和V操作，一个进程在成功地对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作，表示当前没有进城进入临界区，可让其他进程进入。

（5） 利用信号量实现前驱关系

信号量也可以用来描述程序之间或者语句之间的前驱关系。

（6） 分析进程同步或互斥问题的方法步骤

1） 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前去关系直接按照上面例子中的经典犯事改写。

2） 整体思路。找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。

3） 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。

4、管程

管程是一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。

1） 局部与管程的共享结构数据说明

2） 对该数据结构进行操作的一组过程

3） 对局部于管程的共享数据设置初始值的语句

1）局部于管程的数据只能被局部于管程内的过程访问。

2）一个进程只有通过调用管程内的过程才能进入广成访问的共享数据。

3）每次仅允许一个进程在管程内执行某个内部过程。

由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加，无需程序员关注，而且保证正确。

5、经典同步问题

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不为空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

问题分析：

1）关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。

2）整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是胡吃喝同步PV操作的位置。

3）信号量的设置。信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初始为1；信号量full用于记录当前缓冲池中“满”缓冲区数，初值为0.信号量empty用于记录当前缓冲池中空缓冲区，初值为n。

下面再看一个较为复杂的生产者-消费者问题：

问题描述：桌子上有一只盘子，每次孩子能向其中放入一个水果。爸爸专向盘子中放入苹果，妈妈专向盘子中放入橘子，女儿专等吃盘子中的苹果，儿子专等吃盘子中的橘子。只有盘子为空时，爸爸或妈妈就可向盘子中放一只水果2；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

问题分析：

1）关系分析。这里的关系略微复杂一些，首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进城必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发。

2）整理思路。这里有4个进程，实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。

3）信号量设置。首先设置信号量plate为互斥信号量，表示是否允许想盘子放水果，初值为1，表示允许放入，且只允许放一只。信号量apple表示盘子里是否有苹果，初值为0，表示盘子中无2苹果；信号量orange表示盘子中是否有橘子，初始量为0，表示盘子中无橘子。

问题描述：有读者和写者两组并发进程，共享一个文件，当两个以上的读进程同事访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：1）允许多个读者同时对文件执行读操作；2）只允许一个写者往文件中写信息；3）任一写者在完成写操作之前不允许其他读者或写者工作；4）写者执行完写操作前，应让已有的读者或写者全部退出。

问题分析：

1）关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥关系。

2）整理思路。两个进程，即读者和写者。写者比较简凡，它和任何进程互斥，用互斥信号量p操作、v操作即可解决。读者的问题比较复杂，它必须实现与写着互斥的关系，还要实现和其他读者同步的关系。因此，紧急简单的一对pv操作时无法解决的。那么在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候，写着是无法写文件的，此时读者会一直占用文件，当没有读者的时候，写者才可以写文件。同事这里不同读者对计数器的访问也是互斥的。

3）信号量的设置。首先设置信号量count为计数器，用来记录当前读者数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。

问题描述：一张圆桌上坐着五个哲学家，每两个哲学家之间的桌子上摆着一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考是，并不影响其他人。只有当哲学家饥饿的时候，才视图拿起左右两根筷子。如果筷子已经在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当今参悟你比猴，放下筷子继续思考。

问题分析：

1）关系分析。五个哲学家与左右邻居对其中的筷子的访问是互斥关系。

2）整理思路。显然这五个进程，要解决的问题有两个：一个是让他们同时拿起两个筷子；而是对每个哲学家的动作执行规则，避免饥饿或者死锁现象发生。

3）信号量设置。定义互斥信号组chopsticks【5】={1,1,1,1,1}用于对五个筷子的互斥访问。

对哲学家按顺序0~4编号，哲学家i左边的筷子编号为i，哲学家右边的筷子编号为（i+1）%5。

问题描述：假设一个系统有三个吸烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽调他，但是要卷起并抽掉一支烟，抽烟者必须要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个有烟草，第二个有纸，第三个有胶水。供应者进程无线地提供提供三种材料。

供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉完成了，供应者就会放另外两种材料在桌子上，这种过程一直重复。

问题分析：

1）关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或两个以上的抽烟者，三个抽烟者对抽烟这个动作是互斥关系。

2）整理思路。显然这里有四个进程。供应者作为生产者向三个抽烟者提供材料。

3）信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish 用于互斥进行抽烟动作。