第2章 进程和线程（进程的并发）

2.2进程的并发

2.2.1进程的PV操作2.2.2进程的互斥2.2.3进程的同步

本节目标理解与掌握进程的临界区、PV操作的基本知识。理解与掌握进程的互斥与同步的基本知识。理解与掌握进程通信的信箱的基本知识。2.2.1进程的PV操作1.进程的并发性2.临界区和临界资源3.PV操作1.进程的并发性

在多道程序设计的系统中，若干个作业可以同时执行，而每一个作业又需要有多个进程的协作来完成。因此，系统中会同时存在许多进程，在单处理器的情况下，这些进程轮流地占用处理器．即一个进程的工作没有全部完成之前，另一个进程就可开始工作，我们说这些可同时执行的进程具有并发性，并且把可同时执行的进程称为并发进程。

I1I2I3I4C1C2C3C4P1P2P3P42.临界区和临界资源1.临界资源

一次仅允许一个进程使用的资源称为临界资源。2.临界区每个进程中访问临界资源的那段程序称为临界区。3.与时间有关的错误4.临界区的管理要求：①一次至多一个进程能够进人临界区，当有进程在临界区执行时，其它想进人临界区执行的进程必须等待；②不能让一个进程无限制地在临界区执行，即任何一个进人临界区的进程必须在有限的时间内退出临界区；③不能强迫一个进程无限地等待进入它的临界区，即有进程退出临界区时应让一个等待进入临界区的进程进入它的临界区执行。空则让进、忙则等待、等则有限、等则让权。

例如，某游乐场设置了一个自动计数系统，用一个计数器count指示在场的人数,。当有1人进人时，进程P1实现计数加１，当退出1人时，进程P2实现计数减１。假定某时刻的计数值count=n，这时有一个人要进入，正好另一个人要退出，于是进程P1和P2都要执行。那么各自完成了count+1和count-1的工作后，计数器的值为多少？intcount=0;…P1: intR1；R1=count；

R1=R1+1；

count=R1；…P2: intR2；

R2=count；

R2=R2-1；

count=R2；占用CPU的进程执行的操作count值P1R1=countR1=R1+1np1被打断，由P2占用CPU并运行到结束R2=countR2=R2-1count=R2n-1P1继续运行count=R1n+1占用CPU的进程执行的操作count值P2R2=countR2=R2-1np2被打断，由P1占用CPU并运行到结束R1=countR1=R1+1count=R1n+1P2继续运行count=R2n-1这两个进程的执行次序对结果是有影响的，关键是它们涉及到共享变量count，且两者交替访问了count，在不同的时间里访问count，就可能使count的值不同。所以，造成计数值不正确的因素是与进程被打断的时间和能占用处理的时间有关，由于这种原因造成的错误称为“与时间有关的错误”。

3.PV操作PV操作是由两个操作P操作和V操作组成。这两个操作是两个不可中断的过程，它们在屏蔽中断的情况下连续执行。把不可中断的过程称作原语，于是P操作和V操作也可称为P操作原语和V操作原语简称PV操作。PV操作是对信号量进行操作，它们的定义如下：

P操作P（S）将信号量S减去1，若S<0则调用P（S）的进程被置成等待信号量Ｓ的状态。

V操作V（S）：将信号量S加1，若S≤0，则释放一个等待信号量S的进程。（1）信息号S是一个特殊的整型变量，信量号S的值描述了可用资源的数量或等待该资源的进程个数，当S≥0时表示可用资源数；当S＜0时其绝对值|S|表示等待该资源的进程数。（2）W（S）表示将调用过程的进程置成等待信号量Ｓ的状态。（3）R（S）表示释放一个等待信号量S的进程。信号量S的初值为0或1或其它整数，它应在系统初始化时确定。P操作和V操作可表示成如下两个过程：semaphoreS=1；

voidP(){S=S-1；

if(s<0)W(S);}；（P）

voidV(){S=S+1；

if(S<=0)R(S);}；（V）2.2.2进程的互斥

进程的互斥是指：当有若干个进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用，其它要使用该资源的进程必须等待，直到占用资源者释放了该资源。利用P-V操作实现互斥：

A进程B进程

…….……..p(s)p(s)

临界区临界区

v(s)v(s)…….…….intcount；semaphoreS；

S=1；voidP1(){while(true){intR1；P（S）；

R1=count；R1=R1+1；count=R1；V（S）；

}在7.1的第一个例子中的两个并发进程都要使用共享的计数器count，从分析中看到，只有当一个进程不在使用count时另一个进程再去使用，才不会出错．如果它们交叉地使用count则会现与时间有关的错误。为了保证两个进程互斥地使用计数器count，可以用PV操作来管理。定义一个信号量S的初值为1，把两个并发进程的程序改写成如下：voidP2(){intR2；

while(true){P（S）；R2=count；

R2=R2-1；

count=R2；

V（S）；

}}2.2.3进程的同步进程的同步是并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到这才被唤醒。PV操作不仅可以用来实现互斥进入临界区而且还是一个简单而又方便的同步工具，用它来解决生产者/消费者问题。例1：现在假定有一个生产者和一个消费者，它们公用一个缓冲器，生产者不断地生产物品，每生产一件物品就要存入缓冲器，但缓冲器中每次只能存入一件物品，只有当消费者把物品取走后，生产者才能把第二件物品存入缓冲器，同样地，消费者要不断地取出物品去消费，当缓冲器中有物品他就可去取，每取走一件物品后必须等生产者放入一件物品才可再取，用PV操作实现生产者/消费者之间的同步。integerBuffer；semaphoreSP，SG；SP=1；SG=0；

voidproducer(){while(true){produceaproduct；

P（SP）；

Buffer=product；

V（SG）；

}}voidconsumer(){while(true){P（SG）；

takeaproduct；V（SP）；

consume；

}}定义两个信号量：

SP：表示是否可以把物品存入缓冲器，由于缓冲器中只能放一件物品，所以SP的初值取为1。

SG；表示缓冲器中是否存有物品，显然，它的初值应该为0，表示还没有物品。

例2：前面的例题是关于一个生产者和一个消费者共享一个只能放一件物品的缓冲器的例子，如果一个生产者和一个消费者他们共享的缓冲器容量为可以存放n件物品，那么只要把信号量SP的初值定为n。intB[n]；

intk，t；SemphoreSP，SG；k=0；t=0；SP=n；SG=0；voidproducer(){while(true){produceaproduct；

P(SP)；

B[k］=product;k：=（k+1）modn；

V（SG）；}}voidconsumer(){while(true){P（SG）；

takeaproductfromB[t];t=（t＋1）modn；

V（SP）；

consume；} }例3：再进一步讨论m个生产者和r个消费者怎样共享容量为n的缓冲器。intB[n]；

intk，t；SemphoreS，SP，SG；k=0；t=0；SP=n；SG=0；S=1；voidproduceri(inti)（i=1,2，……m）

{while(true){produceaproduct;P（SP）；

P（S）；

B［k］=product；

k：=（k＋1)modn；

V（SG）；

V（S）；}}voidconsumer(intj)(j=1,2,…,r）

{while(true){P（SG）；

P（S）；

takeaproductfromB[t]；

t=（t+1）modn；

V（SP）；

V（S）；

consume；

}}例4：假定有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。当缓冲器中无数时，进程R可以从输入设备上读入数存放到缓冲器B中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲器中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器中的数只能打印一次；W1和W2都不能从空的缓冲器中取数。写出这三个并发进程能正确工作的程序。分析进程间制约关系，定义信号量：

S：表示是否可以把数存入缓冲器，由于缓冲器中每次只能放一个数，所以它的初值取为1。

SO：表示缓冲器中是否有奇数，初值为0，表示无奇数。

SE：表示缓冲器中是否有偶数，初值为0，表示无偶数。semaphoreS，SO，SE；

S=1;SO=SE=0；voidR()

{intx；

while(true){

从输人设备读一个数；

X=读入的数；

P（S）；

B=X；

if（B==奇数）

{V（SO）；

}elseV（SE）；}}voidW1(){ inty；

while(true){P（SO）；

y=B；

V（S）；打印Y中数；

}}voidW2(){intZ；

while(true){P（SE）；

Z=B；

V（S）;

打印Z中数，

}}2.3进程通信2.3.1电子邮件2.3.2管道1.什么是进程通信在计算机系统中，并发进程之间经常要交换一些信息，把并发进程间交换信息的工作称为进程通信。2.通信方式

低级通信方式：并发进程间可以通过PV操作交换信息实现进程的互斥和同步，因此，把PV操作可看作是进程间的一种通信方式，但这种通信只交换了少量的信息，是一种低级的通信方式。

高级通信方式：进程间有时要交换大量的信息，这种大量信息的传递要有专门的通信机制来实现，由专门的通信机制实现进程间交换信息的方式称为是高级的通信方式。2.3.1电子邮件1.邮件格式电子邮件和传统的信件类似，邮件的组织分类有以下几部分内容：邮件主题、收件人地址和姓名、发件人地址和姓名（默认为编写者）、邮件大小、邮件附件及指向附件地址的指针等。2.信箱如果用户在公共的电子邮局中被分配一个信箱，表示在电子邮局的目录之下获得了一个称为信箱的文件。在每个用户的信箱中存放的是用户收到的邮件，只有邮件的接收者才有权对信箱的内容进行处理。信箱的大小决定了信箱中可以容纳的信件数，一个信箱通常由信箱头和信箱体两部分组成。3.通信原语这里介绍一种利用信箱进行高级通信的方式，用信箱实现进程间互通信息的通信机制要有两个通信原语，它们是发送（send）原语和接收（receive）原语。1.send（B，M）原语把信件M送入信箱B中，实现过程是：查指定信箱B，若信箱B未满，把信件M送入信箱B中，如果有进程在等B信箱中的信件，则释放“等信件”的进程；若信箱B已满，把向信箱B发送信件的进程还成“等信箱”的状态。

2.receive（B，X）原语从信箱B中取出一封信存放到指定的地址X中，实现过程是：查指定信箱B，若信箱B中有信，取出一封信放在指定的地址X中，如果有进程在等待把信存入信箱B中则释放“等信箱”的进程；若信箱B中无信，把要求从信箱B中取信的进程置成“等信件”状态。2.3.2管道

在两个进程的执行进程中，如果一个进程的输出是另一个进程的输入，就可以使用管道。进程A进程B管道输入进程输出进程（1）管道。一个临时文件，输入进程向管道写入信息，而输出进程从管道读出信息；（2）输入进程。从进程A的输出区读数据，并写入管道；（3）输出进程。将管道中的数据读出，并写入进程B的缓冲区.

由于输出进