进程同步与互斥

首先，我们看一个例子：进程P1、P2公用一个变量COUNT，初始值为0

P1、P2两个进程的执行顺序是随机的，P1、P2可能顺序执行或交错执行。

由图可见，不同的执行顺序，COUNT值会不同，这是不允许的。

在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。

1、临界资源：

然在多道程序系统中的诸进程可以共享各类资源，然而临界资源却是一次只能供一个进程使用，使用完后归还系统，才能给其他进程使用。（如上例变量COUNT是临界资源）。

进程对临界资源必须互斥使用，为实现对临界资源的互斥访问，应保证诸进程互斥地进入自己的临界区。为此，每个进程在进入其临界区前，必须先申请，经允许后方能进入。

同步机制应遵循的准则：

空闲让进

当无进程处于临界区内时，必须让一个要求进入临界区的进程立即进入，以有效地利用临界资源。

忙则等待

当已有进程处于临界区内时，其它试图进入临界区的进程必须等待，以保证它们互斥地进入临界区。

有限等待

对要求进入临界区的进程，应在有限时间内使之进入，以免陷入“死等”。

让权等待

对于等待进入临界区的进程而言，它必须立即释放处理机，以免进程“忙等”

解决互斥的锁机制：

实现互斥的一种软件方法是采用锁机制，即提供一对上锁（Lock）和开锁（UnLock）原语，以及一个锁变量W。

进程进入临界区前，通过锁变量来判断临界资源是否被占用。

2、信号量机制

号量机制是一种卓有成效的进程同步工具，被广泛应用于单处理机和多处理机系统，以及计算机网络中。

锁机制仅能表示“开”与“关”两种状态；开、关原语必须作为原子操作来进行；关锁原语中反复测试W状态，浪费了处理机的时间；锁机制只能解决互斥，不能用于同步。信号量同步机制能完满地解决上述问题，以下介绍经典信号量机制。

P操作：意味着请求分配一个单位资源 V操作：意味着释放一个单位资源

合作进程的执行次序，其进程流图如下:

进程流图

3、互斥、同步例子

互斥例子：

三个进程共用两个I/O缓冲区

解：设用信号量S表示共享资源，S初始值为2

同步例子：

有A、B两进程，A进程从卡片机读信息入缓冲区，B进程负责加工读进缓冲区的卡片

解：设信号量S1：缓冲区中有否可供加工的信息，初始值为0；

信号量S2：缓冲区是否为空，初始值为1；

在输入进程A中，可以把P（S2）调到V（S1）后面，而把信号量S2的初始值设为0。

用P-V操作描述前趋关系的例子：

信号量还可以描述程序或语句之间的前趋关系。

描述如下：

var a，b，c，d，e，f，g：=semaphore：=0，0，0，0，0，0，0；

begin

parbegin

begin S1；V(a)；V(b)；end；

begin P(a)；S2；V(c)；V(d)；end；

begin P(b)；S3；V(e)；end；

begin P(c)；S4；V(f)；end；

begin P(d)；S5；V(g)；end；

begin P(e)；P(f)；P(g)；S6；end；

parend

End

4、生产者、消费者问题

产者-消费者（Producer-Consumer）问题是著名的进程同步问题。它描述一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者向其中投放消息，消费者从中取得消息。以下用信号量解决生产者-消费者问题。

假如缓冲池中有n个缓冲区，每个缓冲区存放一个消息，可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。又假定这些生产者和消费者互相等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。

其中，mutex，empty，full的初始值分别为1，n，0；

基本概念

进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。

进程同步：指多个相关进程在执行次序上的协调。

临界资源：在一段时间内只允许一个进程访问的资源。

临界区：每个进程中访问临界资源的那段代码。