计算机四级操作系统-4-并发与同步

第4章并发与同步

在一个计算机系统中存在着多个进程（线程），这些进程（线程）之间可能有逻辑上的关系，也可能没有逻辑上的关系。进程（线程）之间无论是否存在逻辑上的关系，由于它们都要共享或竞争一个计算机系统中的资源，所以不可避免地会互相发生作用。本节专门研究进程（线程）间的相互作用。

4.1进程（线程）间相互作用

1.相关进程和无关进程

在一个多道程序系统中同时运行的并发进程通常有多个。在逻辑上具有某种联系的进程称为相关进程，在逻辑上没有任何联系的进程称为无关进程。并发进程相互之间可能是无关的，也可能是相关的。

如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则说这些并发进程的相互之间是无关的。显然，无关的并发进程一定没有共享的变量，它们分别在各自的数据集合上操作。

例如，为两个不同的源程序进行编译的两个进程，它们可以是并发执行的，但它们之间却是无关的。因为这两个进程分别在不同的数据集合上，为不同的源程序进行编译。虽然这两个进程可交叉地占用处理器为各自的源程序进行编译，但是任何一个进程都不依赖另一个进程。甚至当一个进程发现被编译的源程序有错误时，也不会影响另一个进程继续对自己的源程序进行编译，它们是各自独立的。

如果一个进程的执行依赖其他进程的进展情况，或者说，一个进程的执行可能影响其他进程的执行结果，则说这些并发进程是相关的。

例如，有三个进程，它们分别是读数据进程、处理数据进程和打印结果进程。其中读数据进程每次启动磁盘读入一批数据并把读到的数据存放到缓冲区中；处理数据进程对存放在缓冲区中的数据进行加工处理；打印结果进程把加工处理后的结果打印输出。这三个进程中的每一个进程的执行都依赖另一个进程的进展情况，即只有当读数据进程把一批数据读完并存入缓冲区后，处理数据进程才能对它进行加工处理；而打印结果进程要等数据加工处理好后才能进行；也只有当缓冲区中的数据被打印结果进程取走后，读数据进程才能把读到的第二批数据再存入缓冲区；如此循环，直至所有的数据都读入、处理过并打印输出。可见这三个进程相互依赖、相互合作，它们是一组相关进程，共享着缓冲区中的数据资源。

2.与时间有关的错误

一个进程由于自身或外界的原因而可能被中断，且断点是不固定的。至于一个进程被中断后，哪个进程可以先运行，而被中断的那个进程在什么时候再去占用处理器等问题，则与进程调度策略有关。

进程执行的速度是不能由进程自身控制的。对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一进程也开始使用，形成交替使用共享资源。

例如，两个并发程序A和B共享一个公共变量〃，程序A每执行一次循环都要作〃 + 1操

作，程序B则在每一次循环中打印出n的值并将〃重新置0。程序描述如下。

程序A:

while(true)

{

n=n+1；

…

};

…

程序B:

while(true)

{

print(n);

n=0；

}

由于程序A和程序B的执行都以各自独立的速度向前推进，它们的语句在时间上可任意穿插或交叉执行,故程序A的n=n+1操作可能在程序B的print（n）和n=0操作之前，也可能在它们之后或它们之间（即n=n+1出现在print（n）之后，而在吣0之前）。设在开始某个循环之前n的值为5，则对于上面三种情形，执行完一个循环后，打印机打印出的值分别为6、5和5，而执行后的〃值分别为0、1、0。相同的程序在可能的三种情况下分别产生了三组不同的结果，显然这不是所希望的。产生了这种情形的根本原因在于：在并发程序中共享了公共变量，使得程序的计算结果与并发程序执行的速度有关。这种错误的结果又往往是与时间有关的（如上例中的三种情形，其结果时对时错，随执行速度的不同而异），所以，把它称为“与时间有关的错误”。

下面再以民航售票系统为例说明这类“与时间有关的错误”。假设一个民航售票系统有n个售票处。在售票系统的公共数据库存放着某月某日某次航班的余票数，这些余票用单元A_i(i=1，2，3，…）代表：每个售票处通过终端访问系统的公共数据库。用P₁,P₂，…P_n表示各售票处为旅客服务的处理进程；而R₁,R₂…,R_n，为各进程执行时所使用的工作单元。

当某个售票处有旅客买票时，进程如下工作：

PROCESSP_i(i=l，2，3，...，n)

{

{按旅客订票要求找到A_j};

R_i=A_j};

if(R_i>=l){

R_j:=R_j-1;

A_J:=R_t;

{输出一张票}

}else{输出"票已售完"}

}

由于旅客到各售票处订票的时间以及要求购买的机票日期和航班是随机的，因此存在着有若干个旅客几乎在相同的时刻、不同的售票处要求购买同一天同一航班的机票的可能。于是，若干个进程都要访问同一个冷，进程并发执行时可能出现的情况如图4-1所示。

在图4-1中，两个并发进程执行的相对速度是无法控制的，进程P_i读出的A_j值与进程P_k读出的冷值相同，当A_j≥1时，这两个进程P_I和P_k都认为有票可售给旅客。于是，进程继续执行，各自在进行余票数减1的操作，然后把当前的余票数存回A_j。如果这样，售票系统的公共数据库中的票数记录就出错了。

如果在这些进程处理之前，A_j=1，即刚好只剩下一张票，那么这一张票就卖给了两个旅客，甚至是多个旅客。

图4-1售票处理进程的并发

显然，这也是与时间有关的误。

由于多进程在操作系统中的并发执行，它们之间存在着相互制约的关系。这就是进程间的同步和互斥关系。进程同步是指多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务。进程互斥是指由于共享资源所要求的排他性，进程间要相互竞争，以使用这些互斥资源。下面讨论如何实现进程同步和互斥。

4.2进程互斥

进程互斥的解决有两种做法：一是由竞争各方平等协商；二是引入进程管理者，由管理者来协调竞争各方对互斥资源的使用。这两种做法在操作系统中都存在，我们首先讨论第一种做法，即基于进程间平等协商的互斥算法。

从多道系统开始，程序的运行环境就存在资源共享问题。多个进程之间需要对有限的资源进行共享，各进程在运行时是否能得到所需要的资源，是受其他进程的影响的。如果一个进程所需要的资源已被其他进程占用，该进程就无法正常运行下去。临界资源是指计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据结构等。多个进程在对临界资源进行访问时，特别是进行写入或修改操作时，必须互斥地进行。计算机系统中也有一些可以同时访问的共享资源不是临界资源，如只读数据。

在多进程系统中，可把进程间的相互制约关系按相互感知程度分成如表4—¹所列的三种类型。计算机系统中资源共享的程度可分成三个层次：互斥（MutualExclusion）、死锁（Deadlock）和饥饿（Starvation）。保证资源的互斥使用是指多个进程不能同时使用同一个资源，这是正确使用资源的最基本要求；避免死锁是指避免多个进程互不相让，避免出现都得不到足够资源的情况，从而保证系统功能的正常运行；避免饥饿是指避免某些进程一直得不到资源或得到资源的概率很小，从而保障系统内资源使用的公平性。

为了保证临界资源的正确使用，可把临界资源的访问过程分成如图4-2所示的四个部分：

（1）进人区（Entry Section）：为了进入临界区使用临界资源，在进人区要检查可否进入临界区；如果可以进入临界区，通常设置相应的“正在访问临界区”标志，以阻止其他进程同时进入临界区。

（2）临界区（Critical Section）：进程中访问临界资源的一段代码。

（3）退出区（Exitt Section）：将“正在访问临界区”标志清除。

（4）剩余区（Remainder Section）：代码中的其余部分。

为了合理使用计算机系统中的资源，在操作系统中采用的进程同步机制应遵循以下几条准则：

（1）空闲则入:任何同步机制都必须保证任何时刻最多只有一个进程位于临界区。当有进程位于临界区时，任何其他进程均不能进人临界区。

（2）忙则等待：当已有进程处于其临界区时，后到达的进程只能在进入区等待。

（3）有限等待：为了避免死锁等现象的出现，等待进入临界区的进程不能无限期地“死等”。

（4）让权等待：因在进入区等待而不能进入临界区的进程，应释放处理机，转换到阻塞状态，以使得其他进程有机会得到处理机的使用权。

1.进程互斥的软件方法

通过平等协商方式实现进程互斥的最初方法是软件方法。其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志。其中的主要问题是设置什么标志和如何检查标志。下面讨论几种用软件方法实现的软件互斥算法。

算法1:单标志算法

假设有两个进程P_i和P_j。设立一个公用整型变量turn，描述允许进入临界区的进程标识。每个进程都在进入区循环检查变量turn是否允许本进程进入。即turn为i时，进程P,可进入；否则循环检查该变量，直到Mm变为本进程标识。在退出区修改允许进人进程标识。即进程尽退出时，改turn为进程P_j的标识j。图4-3为进程的代码。

算法1可以保证任何时刻最多只有一个进程在临界区。但它的缺点是强制轮流进人临界区，没有考虑进程的实际需要。这种算法容易造成资源利用不充分。例如，在P_i出让临界区之后，A使用临界区之前，P_i不可能再次使用临界区。

算法2:双标志、先检查算法

为了克服算法1的缺点，可考虑修改临界区标志的设置。设立一个标志数组flag[]，描述各进程是否在临界区，初值均为FALSE。在进入区的操作为：先检查，后修改。即在进入区先检查另一个进程是否在临界区，不在时修改本进程在临界区的标志，表示本进程在临界区。在退出区修改本进程在临界区的标志，表示本进程不在临界区。图4-4为进程P_i的代码。

算法2的优点是克服了算法1的缺点，两个进程不用交替进人，可连续使用。但由于使用多个标志，算法又产生一个新问题，即进程弋和Pj可能同时进入临界区，从而违反了最多只有一个进程在临界区的要求。当按序列“P_i<a>P_j<a>P_i<b>P_j<b>”执行时，就会出现进程弋和同时进入的问题。即进程在检查对方标志flag之后和切换自己标志flag之前有一段时间间隔，这个时间间隔导致两个进程都在进入区通过检查。这个问题出在检查和修改操作不能连续进行。

算法3:双标志、后检查算法

为了解决算法2的新问题，有两种选择:一是保证检查和修改操作间不出现间隔，一是修改标志含义。第一种方法是仅使用软件方法无法做到的，采用第二种方法。算法3类似于算法2，它们的区别在于进入区操作是先修改后检查。这时标志flag[i]表示进程f想进入临界区，而不再表亦进程i在临界区。图4-5为进程的代码。

算法3可防止两个进程同时进入临界区。但它的缺点是八和弋可能都进入不了临界区。当按序列“P_i<b>P_j<b>P_i<a>P_j<a>”执行时，会都进不了临界区。即在修改本进程标志flag之后和检查对方flag之前有一段时间间隔，这个间隔导致两个进程都想进入临界区，从而在检查对方标志时不通过。

算法4(Peterson’sAlgorithm):先修改、后检查、后修改者等待算法

算法4的基本思想是结合算法1和算法3。标志flag[i]表示进程f想进入临界区，标志ton表示同时修改标志时要在进入区等待的进程标识。在进入区先修改后检查。通过修改同一标志turn来描述标志修改的先后；检查对方标志flag,如果对方不想进人临界区则自己进入；否则再检查标志如爪，由于标志mm中保存的是较晚的一次赋值，则较晚修改标志的进程等待，较早修改标志的进程进入临界区。图4-6为进程P_i的代码。

图4-5互斥算法3(双标志、先修改标志） 图4-6互斥算法4(先修改、后检査、后修改者等待）

至此，算法4可完全正常工作，即实现了同步机制要求的四条准则中的前二条：空闲则入、忙则等待。但从上面的软件实现方法中可发现，对于两个进程间的互斥和三个以上进程间的互斥的进入区是要区别对待的，而这里最主要的问题就是修改标志和检查标志不能作为一个整体来执行。下面的硬件方法就是利用处理机的指令系统来解决这个问题。

2.进程互斥的硬件方法

完全利用软件方法实现进程互斥有很大局限性，例如，软件方法并不适用于数目很多的进程间的互斥，现在巳很少单独采用软件方法。目前，在平等协商时通常利用某些硬件指令来实现进程互斥。硬件方法的主要思路是用一条指令完成读和写两个操作，因而保证读操作与写操作不被打断。依据所采用的指令的不同，硬件方法分成TS指令和Swap指令两种。

1）TS(Test-and-Set)指令

TS指令的功能是读出指定标志后把该标志设置为TRUE。TS指令的功能可描述成下面的函数。

BooleanTS(Boolean*lock){

booleanold；

old=*lock；lock=TRUE；

returnold；

}

利用TS指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock，表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲，初值为FALSE。在进人区利用TS进行检查和修改标志lock。有进程在临界区时，重复检查，直到其他进程退出时检查通过。如图4-7所示，所有要访问临界资源的进程的进入区和退出区代码是相同的。

2）Swap指令（或Exchange指令）

Swap指令的功能是交换两个字（字节）的内容。可用下面的函数描述Swap指令的功能。

voidSWAP(int*a,int*b){

inttemp；

temp="a;*a=* b;*b =temp；

}

利用Swap指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock,初值为FALSE;每个进程设置一个私有布尔变量key,用于与lock间的信息交换^在进人区利用Swap指令交换lock与key的内容，然后检查key的状态;有进程在临界区时，重复交换和检查过程，直到其他进程退出时检查通过。图4-8所示为利用Swap指令的互斥算法。

与前面的软件方法相比，硬件方法由于采用处理机指令很好地把修改和检查操作结合成一个不可分的整体而具有明显的优点。具体而言，硬件方法的优点体现在以下几个方面：

（1）适用范围广：硬件方法适用于任意数目的进程，在单处理器和多处理器环境中完全相同。

（2）简单:硬件方法的标志设置简单，含义明确，容易验证其正确性。

（3）支持多个临界区：在一个进程内有多个临界区时，只需为每个临界区设立一个布尔变量。

硬件方法有许多优点，但也有一些自身无法克服的缺点。这些缺点主要包括：

（1）进程在等待进入临界区时，要耗费处理机时间，不能实现“让权等待”。

（2）由于进人临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致“饥饿”。

4.3信号量（Semaphore)

前面的互斥算法都是平等进程间的协商机制，它们存在的问题是平等协商无法解决的，需要引人一个地位高于进程的管理者来解决公有资源的使用问题。操作系统可以从进程管理者的角度来处理互斥的问题，信号量就是由操作系统提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。

信号量是荷兰学者Dijkstra于1965年提出的一种卓有成效的进程同步机制。信号量机制所使用的P、V原语就来自荷兰语的test(proberen)和increment(verhogen)。每个信号量s除一个整数值s.count(计数）外，还有一个进程等待队列s.queue，其中存放的是阻塞在该信号量的各个进程的标识。信号量只能通过初始化和两个标准的原语来访问。作为操作系统核心代码的一部分，P、V原语的执行，不受进程调度和执行的打断，从而很好地解决了原语操作的整体性。信号量的初始化可指定一个非负整数值，表示空闲资源总数。若信号量为非负整数值，表示当前的空闲资源数;若为负值，其绝对值表示当前等待临界区的进程数。

依据对临界区访问过程的分析，信号量机制中P原语相当于进入区操作，V原语相当于退出区操作。下面来分析操作系统对这两个原语操作的处理过程。

P原语所执行的操作可用下面函数wait(s)来描述。wait(s)

{

--s.count；//表示申请一个资源

if(s.count<0)//表示没有空闲资源

{

调用进程进人等待队列s.queue；

阻塞调用进程；

}

}

V原语所执行的操作可用下面函数signal(s)来描述。

signal(s)

{

++s.count；//表示释放一个资源

if(s.count<=0)//表示有进程处于阻塞状态

{

从等待队列s.queue中取出头一个进程P;

进程P进入就绪队列;

}

}

利用操作系统提供的信号量机制，可实现临界资源的互斥访问。图4-9所示为临界资源设置一个互斥信号量mutex(MUTualEXclusion)，其初值为1;在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间。

在使用信号量进行共享资源访问控制时，必须成对使用P和V原语。遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放给其他等待的进程。P、V原语的使用不能次序错误、重复或遗漏。

利用操作系统提供的信号量机制可实现进程间的同步，即所谓的前趋关系。图4-10所示前趋关系是指并发执行的进程P₁和P₂中，分别有代码C₁和C₂，要求C₁在C₂开始前完成执行。可为每个前趋关系设置一个互斥信号量S₁₂，其初值为0。这样，只有在P₁,执行到V(S₁₂)后，P₂才会结束P(S₁₂)的执行。

4.4经典的进程同步间題

下面介绍两个经典的同步互斥的例子。这两个例子及其解法都是很著名的，深入地分析和透彻地理解这些例子，对于全面解决操作系统内的同步、互斥问题将有很大启发。

Dijkstra把同步问题抽象成一种“生产者-消费者关系”。生产者-消费者问题是计算机中各种实际的同步、互斥问题的一个抽象模型。计算机系统中的许多问题都可被归结为生产者-消费者关系，例如，生产者是计算进程，消费者是打印进程;在输入时输入进程是生产者，计算进程是消费者。

1.简单生产者-消费者问题

有关简单生产者-消费者问题的描述是这样的：设有一个生产者进程P，一个消费者进程(？，它们通过一个缓冲区联系起来，如图4-11所示。缓冲区只能容纳一个产品，生产者不断地生产产品，然后往空缓冲区送产品；而消费者则不断地从缓冲区中取出产品，并消费掉。

图4-11简单生产者—消费者问题

现在对生产者-消费者问题中的同步互斥关系进行分析，并设置相应的信号量。显然，P进程不能往已经“满”的缓冲区中放入产品，设置信号量empty，其初值为1，用于指示空缓冲区数量；同样W进程也不能从已经“空”的缓冲区中取出产品，设置信号量full,初值为0，用于指示满缓冲区数量。

生产者-消费者同步问题的解决方案如下：

生产者进程P:

while(true){

P(empty);

生产一个产品；

送产品到缓冲区；

V(full)；

}；

消费者进程Q:

while(true{

P(full);

从缓冲区取产品；

V(empty)；

消费产品；

};

在这个方案之中，产品生产出来之后立即往缓冲区中存放产品，因为刚开始时缓冲区是空的，一定可以存放一个产品。

2.多个生产者-消费者问题

可以把上面介绍的简单生产者-消费者问题推广为多个生产者和多个消费者问题。

下面是有关多个生产者和多个消费者问题的描述:设有若干个生产者进程Pi，P₂，……，P_n，若干个消费者进程Q₁Q₂，……Q_n，它们通过一个环形缓冲池联系起来，如图4-12所示。该环形缓冲池由&个大小相等的缓冲区组成，每个缓冲区能容纳一个产品，生产者每次往空缓冲区送一个产品；消费者每次从满缓冲区取出一个产品。

生产者进程不断地生产产品并把它们放入缓冲池内，消费者进程不断地从缓冲池内取产品并消费之。这里既存在同步问题，也存在互斥问题。

当整个缓冲池全满时，出现了供大于求的现象。此时生产者必须暂缓生产，而消费者应该大力消费。当整个缓冲池全空时，出现了供不应求的现象。此时消费者必须等待，而生产者必须努力生产。很明显，在上述生产者和消费者之间存在一定的合作关系。

在生产者向空的缓冲区里放入产品之后，或者消费者从满的缓冲区里取出产品之后，有关的缓冲区就改变了它的状态。

另外，环形缓冲池是临界资源，因为生产者和消费者都要使用它。在某个缓冲区为空时，消费者不能从这个空的缓冲区里取出产品；同样，在某个缓冲区为满时，生产者不能向这个满的缓冲区里放人产品。可见，在生产者和消费者之间还存在着互斥关系。

1）同步问题

P进程不能往“满”的缓冲区中放产品，设置信号量empty，初值为k用于指示缓冲池中空缓冲区数目。

Q进程不能从“空”的缓冲区中取产品，设置信号量full,初值为0，用于指示缓冲池中满缓冲区数目。

2）互斥问题

设置信号量mutex，初值为1，用于实现临界区（环形缓冲池）的互斥。

另设整型量i、j，初值均为0。i用于指示空缓冲区的头指针;j用于指示有产品的满缓冲区的头指针。

3）算法

该同步互斥问题的解决方案如下：

P₁，P2，…，P_n：

i:=0；

while(true){

生产产品；

P(empty)；

P(mutex);

往Buffer[i]中放产品；

i:=(i+1)modk；

V(mutex)；

V(full)；

Q_i，Q₂，…，Q_m:

j：=0；

while(true){

P(full);

P(mutex)；

从Buffer[j]取产品；

j：=(j+1)modk；

V(mutex)；

V(empty);

消费产品；

}；

3.读者-写者问题

在计算机系统中，一个数据对象（例如一个文件或记录）是可以供若干进程共享的。

1）读者-写者问题的描述

假定有某个共享文件F，系统允许若干进程对文件F进行读或写。这里把要读文件的进程称为读者，把要写文件的进程称为写者。读者和写者必须遵守如下的规定：

（1）多个进程可以同时读文件F;

（2）任一个进程在对文件F进行写时，不允许其他进程对文件进行读或写；

（3）当有进程正在读文件时不允许任何进程去写文件。

当有多个读者和写者都要读写文件F时，按规定每次只允许一个进程执行写操作，且在有进程执行写时不允许进程读文件。显然，写者与写者之间要互斥，写者与读者之间也要互斥，但按规定多个读者可同时读文件，也就是说，只要第一个读者取得了读文件的权利，则其他读者可以跟着读文件。所以，写者与读者之间的互斥就变成了写者与第一个读者之间的互斥。

设read_count记录当前正在读的读者进程个数，由于多个读者都对reac_count进行修改，所以read_count是一个共享变量，需要互斥使用，故设置信号量mutex。再设置信号量write，用于写者之间互斥，或第一个读者和最后一个读者与写者的互斥。

2）读者-写者问题的解决方案

下面给出读者-写者问题的解决方案。

读者进程：

while(true){

P(mutex)；

read_count：=read_count+1;

if(read^count=1)P(write)；

V(mutex)；

读文件；

P(mutex);

read一count：=read_count-1；

if(read—count=0)V(write)；

V (mutex)；

写者进程：

while(true){

P(write)；

写文件；

V(write);

这里对上面的解决方案做一些具体的说明。

read_count是一个计数器，初值为0。而mutex和write都是信号量，它们的初值都是1。

read_count是一个共享变量，需要互斥使用，在每个读者进入时，对read_count的计数不能出错。另外，如果第一个读者进入，就不能再允许写者进入，这就是ifread_count=1，thenP(write)语句的作用；第一个读者负责禁止任何写者进入。以上这两个操作都要放在互斥区内。

而其他的读者可以随着第一个读者的进入而陆续进入。

当有读者完成读操作之后，相应地要对read_count进行减一操作。而且如果read_count=0，表明已经没有读者了，写者可以随时进入。

对于读者来说，只要有一个写者已经在临界区执行写操作，所有的读者就必须等待。

4.同步与互斥的综合应用

这里举一些运用经典的进程同步问题解决方案的例子，以帮助读者更好地掌握其解法的基本思想。

例1路口单双号交通管制。

1）问题

某个城市为了解决市内汽车太多、交通过于拥堵的问题，决定出台一项交通管制措施，对进入市中心区的机动车辆实行单双日限制行驶的办法。具体要求是，逢单日，只允许车辆牌号号码为单数的机动车进入市中心区；同样，逢双日，只允许车辆牌号号码为双数的机动车进入市内中心区。有一个进入市中心区的交通路口，进入该路口的道路有一条，离幵该路口的道路有两条，其中一条是通往市中心区的道路，而另一条是绕过市中心区的环路，在通往路口上准备设置自动识别车辆牌号的识别设备与放行栅栏控制设备。请设计有关的单双号交通管制控制程序。该程序能够完成如下工作：

在单日，遇有单号车辆进入路口车辆号码识别区，号码识别设备则打开通往市中心区道路的放行栅栏；遇有双号车辆，则打开绕过市中心区环路的放行栅栏。

在双日，有关的控制类似，只允许双号车辆进入市区，单号车辆则只能通行绕过市中心区的环路。显然，只有在该路口车辆号码识别区中无车时，才允许一辆车进入车辆号码识别区。同时，为了防止有车辆混过路口，两个放行栅栏平时处于关闭状态，只有在车辆号码识别区中的车辆已被识别出单双号之后，放行栅栏才会在识别设备的控制下打开对应的放行栅栏，在车辆通过之后该放行栅栏自行关闭。

2）分析

考虑单日允许进入市中心区的情况，如图4-13所示。

上述问题可以被抽象为生产者-消费者问题:进入交通路口“检查车辆牌号”被看成生产者；进入“市区放行栅栏”被看成是一种奇数消费者；而绕行“环路放行栅栏”被看成是另一种偶数消费者。于是当生产者的产品“检查车辆牌号”为奇数时，则交给奇数消费者；

当生产者的产品“检查车辆牌号”为偶数者时，则交给偶数消费。只有在奇数消费者和偶数消费者得知识别区中“检查车辆牌号”是奇数或偶数的消息之后，才能启动各自的放行栅栏，在放行之后，应给“检查车辆牌号”发一个信号，告知车辆号码识别区中又可进入一辆汽车。这样，

就有三种信号通过PV操作处理，分别定义如下：

●Check指示可否在车辆号码识别区中进入一辆汽车，由于只能进入一辆，其初值为1。

●Odd指示汽车号码是否为奇数，其初值为0，表示不是奇数。

●Even指示汽车号码是否为偶数，其初值为0，表示不是偶数。

3）算法

这里列出“检查车辆牌号”“市区放行栅栏”和“环路放行栅栏”这三个进程有关算法的关键部分如下：

vehicle一n:integer;/*车辆号码

检查车辆牌号进程：

while(true){

车辆到达识别区路口；

P(Check)；

车辆进入号码识别区；

if(vehicle_n=奇数）V(Odd);

elseV(Even)；

I.

市区放行栅栏进程：

while(true){

P(Odd)；

允许车辆进人市中心区；

V(Check);

};

环路放行栅栏进程：

while(true){P(Even)；

允许车辆绕行环路；

V(Check)；

}；

例2物流系统中的物品分拣问题。

1）问题

在某个物流系统中，有一个位于上海的集装箱中转枢纽。从不同方向进入枢纽的集装箱运输车，在这里卸下集装箱，然后依据其来自方向的不同，这些集装箱又被装上其他运输工具继续各自的行程。根据整体的物流规划，从沿长江一线进入枢纽的集装箱，要从这里直接吊装到上海至旧金山的定期集装箱班轮上。而从沪杭高速公路上进入枢纽的集装箱，要从这里换装到专门在京沪高速公路上行驶的集装箱运输车上。现在需要设计为该物流系统上海集装箱中转枢纽使用的物流软件。为简化问题起见，假设该中转枢纽的场地每次只能接收一个方向来的同一批次的集装箱。

2）分析

这个物流问题可以看作一个有两个生产者和两个消费者问题。长江一线进入的集装箱卸货是一个生产者,从沪杭高速公路上进入的集装箱卸货是第二个生产者。

这两个生产者都要使用中转枢纽的场地。由于该场地每次只能接收一个方向来的同一批次的集装箱，所以长江一线生产者和沪杭高速公路生产者必须互斥。

去旧金山的定期集装箱班轮和去北京高速公路上的集装箱运输车，分别是两个消费者，他们分别消费长江一线生产者和沪杭高速公路生产者提供的产品——集装箱。这样，两个生产者在把集装箱卸到枢纽的场地之后，应该分别通知去旧金山的班轮和去北京高速公路上的集装箱运输车。另外，在班轮和北京运输车分别装完货物之后，还应该通知中转枢纽的场地，又可以接收新的集装箱了。可见，长江一线卸货生产者和旧金山班轮装货消费者之间要同步，沪杭卸货生产者和北京运输车装货消费者之间也要同步。

下面对有关的信号量进行定义。

首先，定义一个是否允许进入的信号量Site,其初值为1，表示允许存放一批集装箱。

其次，长江一线卸货生产者和沪杭高速公路卸货生产者需要分别向旧金山的班轮和北京运输车消费者发送消息，分别用Arrive_Y和Arrive一H信号量表示，它们的初值为0，表示还没有到货。

在旧金山的班轮和北京运输车消费者分别装完货物之后，可以调用V(Site)，于是发送中转枢纽的场地又可以接收新集装箱了。

至于是长江生产者还是沪杭生产者能够把集装箱卸到枢纽的场地上，则通过两个生产者调用P(S_lte)来竞争。如上所述，安排三个信号量：

●Site指示能否在中转枢纽的场地上卸下集装箱。

●Arrive.Y指示场地上的集装箱是否来自长江。

●Arrive.H指示场地上的集装箱是否来自沪杭。

3）算法

在算法中，安排“长江集装箱卸货”“沪杭集装箱卸货”“旧金山班轮装货”和“北京运输车装货”四个进程，通过对三个信号量的PV操作，实现这四个进程的并发执行。

长江集装箱卸货进程：

while(true){

长江集装箱准备卸货；

P(Site)；

长江集装箱卸货；

V (Arrive_Y)；

沪杭集装箱卸货进程：

while(true)J

沪杭集装箱准备卸货；

P(Site)；

沪杭集装箱卸货；

V(Arrive一H)；

}

旧金山班轮装货进程:/*旧金山班轮检查场地上的集装箱是否来自长江*/while(true)j

P(Arrive_Y){

旧金山班轮装货；

V(Site)；};

北京运输车装货进程/*北京运输车检查场地上的集装箱是否来自沪*/

whilewhile(true){

P(Arrive_H);

北京运输车装货；

V(Site)；

4）说明

在算法中可以看到，进程“长江集装箱卸货”和“沪杭集装箱卸货”在卸下集装箱之前，都分别调用了P(Site)。这个调用有如下两个作用：

首先，由于Site初值为1,P(Site)起到互斥作用，无论谁先卸下了集裝箱，另一个物流方向上不能再卸货，只能等待。

其次，在集装箱已经卸下，但是还没有被装运到对应的运输工具土时，Site的值为0。在集装箱被装运到对应的运输工具上之后，Site的值为恢复为1，又可以卸下新的货物。所以P(Site)起到了测试“又可以接收新集装箱的消息”是否到达的同步作用。

再者，进程“旧金山班轮装货”和“北京运输车装货”在装完集装箱之后，都调用V(Site)，发出可以接收新集装箱的消息。

可见，在本算法中Site信号量既作为互斥的信号量，又起着同步信号量的作用。

4.5管程

1.管程的提出

采用p、v同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中，其缺点是：

（1）程序易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序。

（2）程序不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局。

（3）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的。

为了更易于编写正确的程序，BrinchHansen和Hoare提出了一种高级同步原语，称为管程(Monitor)。

2.管程的概念及组成

一个管程是一个由过程、变量及数据结构等组成的集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。

一个管程由四个部分组成:管程名称，共享数据的说明，对数据进行操作的一组过程和对共享数据赋初值的语句。管程能保障共享资源的互斥执行，即一次只能有一个进程可以在管程内活动。该性能是由管程本身实现的。因此，程序员可以不必显式地编写程序代码去实现这种同步制约。图4-14给出管程的结构，它定义了一种共享数据结构。

图4-15展示了用一种抽象的、类Pascal语言描述的管程。这里不能使用C语言，因为管程是语言特性而C语言并不支持它。

管程具有三个主要的特性：

（1）模块化。一个管程是一个基本程序单位，可以单独编译。

（2）抽象数据类型。管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码。

（3）信息隐蔽。管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的。

管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程互斥进入;管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作。

管程有一个很重要的特性，即任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥。管程是编程语言的组成部分，编译器知道它们的特殊性，因此可以釆用与其他过程调用不同的方法来处理对管程的调用。典型的处理方法是，当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进人。进人管程时的互斥由编译器负责，但通常的做法是用一个互斥量或二元信号量。因为是由编译器而非程序员来安排互斥，所以出错的可能性要小得多。在任一时刻，写管程的人无须关心编译器是如何实现互斥的。他只需知道将所有的临界区转换成管程过程即可，绝不会有两个进程同时执行临界区中的代码。

3.管程中的条件变量

尽管管程提供了一种实现互斥的简便途径，但这还不够，还需要一种办法使得进程在无法继续运行时被阻塞。在生产者-消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放到管程过程中，但是生产者在发现缓冲区满的时候如何阻塞呢？解决的方法是引入条件变量（ConditionVariables)以及相关的两个操作：wait和signal。当一个管程过程发现它无法继续运行时（例如，生产者发现缓冲区满），它会在某个条件变量（如full)上执行wait操作。该操作导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程。另一个进程，比如消费者，可以唤醒正在睡眠的伙伴进程，这可以通过对其伙伴正在等待的一个条件变量执行signal完成。

条件变量不是计数器，条件变量也不能像信号量那样积累信号以便以后使用。所以，如果向一个条件变量发送信号，但是在该条件变量上并没有等待进程，则该信号会永远丢失。换句话说，wait操作必须在signal之前。这条规则使得实现简单了许多。实际上这不是一个冋题，因为在需要时，用变量很容易跟踪每个进程的状态。一个原本要执行signal的进程，只要检查这些变量便可以知道该操作是否有必要。

如果在管程中出现多个进程时怎样考虑？例如，当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进人管程的进程执行唤醒操作（如P唤醒Q)时，管程中便存在两个同时处于活动状态的进程。处理方法有三种：

●P等待Q继续，直到Q退出或等待（Hoare提出）。

●Q等待P继续，直到P等待或退出。

●规定唤醒为管程中最后一个可执行的操作（BrinchHansen提出）。

采用第一种处理办法。因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。如果进程P唤醒进程Q，则P等待Q继续，如果进程Q在执行又唤醒进程R，则Q等待R继续……如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级signal(c）_：如果c链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部。

4.用管程解决生产者-消费者问题

下面给出了用类Pascal语言管程实现的生产者-消费者问题的解法框架。使用类Pascal语言的优点在于清晰、简单，并且严格符合Hoare/BrinchHansen模型。

monitorProducerConsumer

conditionfullempty;

integercount；

procedureinsert(item:integer);

begin

ifcount==Nthenwait(full);

insert_item(item);count++;

ifcount==1thensignal(empty);

end;

functionremove:integer;

begin

ifcount==0thenwait(empty);

remove=remove_item;count--;

ifcount==N-1thensignal(full);

end；

count：=0;

endmonitor；

procedureproducer；

begin

whiletruedo

begin

item=produce_item；

ProducerConsumer.insert(item)；

end

end；

procedureconsumer;

begin

whiletruedo

begin

item=ProducerConsumer.remove;consume_item(item);

end

end;

5.Pthread中的互斥与同步

Pthread提供了可用于线程同步与互斥的机制，它们是互斥量和条件变量，两者结合起来使用已达到管程的效果。下面分别介绍。

（1）互斥量及相关函数

解决线程互斥问题的基本思想是使用一个可以加锁和解锁的互斥量来保护临界区。一个线程如果想要进入临界区，它首先尝试锁住相关的互斥量。如果互斥量没有加锁，那么这个线程可以立即进入，并且该互斥量被自动锁定以防止其他线程进入。如果互斥量已经被加锁，则调用线程被阻塞，直到该互斥量被解锁。如果多个线程在等待同一个互斥量，当它被解锁时，这些等待的线程中只有一个得到互斥量并将其锁定。

与互斥量相关的主要函数调用见表4-2。

表4-2—些与互斥量相关的Pthread调用

（2）条件变量及相关函数

除互斥量之外，Pthread提供了一种同步机制：条件变量，它允许线程由于一些未满足的条件而被阻塞。与条件变量相关的Pthread调用见表4-3。

表4-3一些与条件变量相关的Pthread调用

条件变量与互斥量经常一起使用，其模式是:让一个线程锁住一个互斥量，如果该线程不能获得它期望的结果时，则等待一个条件变量；最后另一个线程会向它发信号，使它可以继续执行。pthread_cond_wait原子性地调用并解锁它持有的互斥量。

以生产者-消费者问题为例：一个线程将产品放在一个缓冲区内，由另一个线程将它们取出。如果生产者发现缓冲区中没有空槽可用，它阻塞起来直到有一个空槽可以使用。生产者使用互斥量可以进行原子性检查，而不受其他线程干扰。但是当发现缓冲区已经满了以后，生产者需要一种方法来阻塞自己并在以后被唤醒，这需要通过条件变量来完成。图4-16展示了一个只有一个缓冲区的生产者-消费者问题。当生产者填满缓冲区时，它在生产下一个数据项之前必须等待，直到消费者清空它。类似地，当消费者移走一个数据项时，它必须等待，直到生产者生产了另外一个数据项。

图4-16利用线程解决生产者-消费者问题

4.6进程通信

一个进程在运行过程中，可能需要与其他进程进行信息交换。进程间交换的信息量可多可少，少的只是交换一些已定义的状态值或数值，例如信号量和p、v操作；多的则可交换大量信进程通信息。P、V操作是一类低级通信原语，不能承担进程间大量信息的交换任务，因此需要引入新的通信原语，解决大量信息交换问题。

解决进程之间的大量信息通信的问题有三类方案：共享内存、消息机制以及通过共享文件进行通信，即管道通信。这三种方式可以称为高级通信原语，它们不仅要保证相互制约的进程之间的正确关系，还要同时实现进程之间的信息交换。

4.6.1共享内存

在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换。

这种通信模式需要解决两个问题:第一个问题是怎样提供共享内存;第二个是公共内存中的读写互斥问题。操作系统一般只提供要共享的内存空间，而处理进程间在公共内存中的互斥关系则是程序开发人员的责任。

4.6.2消息机制

消息机制是用于进程间通信的高级通信原语之一。进程在运行过程中，可能需要与其他的进程进行信息交换，于是进程通过某种手段发出自己的消息或接收其他进程发来的消息。这种方式类似于人们通过邮局收发信件来实现爻换信息的目的。至于通过什么手段收发消息，就像人们选择平信还是航空信一样，是一种具体的消息传递机制。

1.消息缓冲通信

消息缓冲通信技术是由Hansen首先提出的，其基本思想是:根据“生产者-消费者”原理，利用内存中公用消息缓冲区实现进程之间的信息交换。

内存中开辟了若干消息缓冲区，用以存放消息。每当一个进程（发送进程）向另一个进程(接收进程）发送消息时，便申请一个消息缓冲区，并把已准备好的消息送到缓冲区，然后把该消息缓冲区插人到接收进程的消息队列中，最后通知接收进程。接收进程收到发送进程发来的通知后，从本进程的消息队列中摘下一消息缓冲区，取出所需的信息，然后把消息缓冲区还给系统。系统负责管理公用消息缓冲区以及消息的传递。

一个进程可以给若干个进程发送消息，反之，一个进程可以接收不同进程发来的消息。显然，进程中关于消息队列的操作是临界区。当发送进程正往接收进程的消息队列中添加一条消息时，接收进程不能同时从该消息队列中取出消息；反之也一样。

消息缓冲区通信机制包含以下列内容：

（1）消息缓冲区，这是一个由消息长度、消息正文、发送者、消息队列指针组成的数据结构。

（2）消息队列首指针m_q，一般保存在PCB中。

（3）互斥信号量m_mutex，初值为1，用于互斥访问消息队列，在PCB中设置。

（4）同步信号量m_syn，初值为0，用于消息计数，在PCB中设置。

为实现消息缓冲通信，要利用发送消息原语（send)和接收消息原语（receive)。

（5）发送消息原语send(receivers)。发送进程调用send原语发送消息，调用参数receiver为接收进程名，a为发送进程存放消息的内存区的首地址。send原语先申请分配一个消息缓冲区，将由a指定的消息复制到缓冲区，然后将它挂入接收进程的消息队列，最后唤醒可能因等待消息而等待的接收进程。

send原语描述如下：send(R,M)

{

根据R找接收进程，如果没找到，则出错返回;

申请空缓冲区P(s_b);

P(b_mutex);

取空缓冲区;

V(b—mutex);

把消息从M处复制到空缓冲区;

P(m_mutex);

根据m一q，把缓冲区挂到接收进程的消息链链尾;

V(m_mutex);

V(m_syn);

}

其中，s_b是空缓冲区个数，初值为n,b_mutex是空缓冲区的互斥信号量，初值为1。

（6）接收消息原语receive(a)。接收进程调用receive原语接收一条消息，调用参数a为接收进程的内存消息区。receive原语从消息队列中摘下第一个消息缓冲区，并复制到参数a所指定的消息区，然后释放该消息缓冲区。若消息队列为空，则阻塞调用进程。

消息缓冲通信的示意图如图4-17所示。

图4-17消息缓冲通信

2.信箱通信

为了实现进程间的通信，可以设立一个通信机构——信箱，以发送信件以及接收回答信件为进程间通信的基本方式。

当一个进程希望与另一进程通信时，就创建一个链接两个进程的信箱，发送进程把信件投人信箱，而接收进程可以在任何时刻取走信件。

一个信箱的结构可以由“信箱说明”和“信箱体”两部分组成。

在“信箱说明”中，一般有如下的数据结构：

●可存信件数是在设立信箱时预先确定的，表明信箱的容量大小。

●已有信件数指出信箱中已有信件的数量。

通过“可存信件数”和“已有信件数”就能判别信箱是否满和信箱中是否有信件。

●可存信件的指针指示当前可存入一封信的位置。该指针的初始值为指向可存第一封信的位置。

当存入一封信后，则应该修改“已有信件数”和“可存信件的指针”。相应地，若信箱中有信，则每次从中取出一封信，也应该修改“已有信件数”和“可存信件的指针”。

为了实现信箱通信，必须提供相应的原语，如创建信箱原语、撤销信箱原语、发送信件原语和接收信件原语等。

例如，进程A要与进程B通信，进程A就通过创建信箱原语，创建一个连接进程A和进程B的信箱。有了这个信箱，进程A可以通过发送信件原语将信件发送到信箱中，系统将保证进程B可在任何时刻调用接收信件原语，取走信箱中的信件，而不会丢失，如图4-18所示。

图4-18信箱通信

图4-18表示的是一个发送者和一个接收者单向通信的例子。在进程A发送信件之前，信箱中至少应该有空位置，可以存放信件；同样，在进程B接收信件之前，信箱中应该有信件，否则进程应该等待。

采用信箱通信的最大好处是，发送方和接收方不必直接建立联系，没有处理时间上的限制。发送方可以在任何时间发信，接收方也可以在任何时间收信。

由于发送方和接收方都是独立工作的，如果发得快而收得慢，则信箱会溢出。相反，如果发得慢而收得快，则信箱会变空。因此，为避免信件丢失和错误地送出信件，一般而言通信应有如下的规则：

（1）若发送信件时信箱已满，则发送进程应被置成“等信箱”状态，直到信箱有空时才被释放。

（2）若取信件时信箱中无信，则接收进程应被置成“等信件”状态，直到有信件时才被释放。

下面举一个send原语和receive原语的例子如下：

send(Box，L):把信件L送到指定的信箱Box中。

功能:查信箱Box，若信箱未满则把信件L送入信箱，且释放“等信件”者；若信箱已满，置发送信件进程为“等信箱”状态。

receive(Box,Address):从指定信箱Box中取出一封信，存放到指定的地址Address中。

功能:查指定信箱Box，若信箱中有信，则取出一封信存于Address中，且释放“等信箱”者;若信箱中无信件，则置接收信件进程“等信件”状态。

3.管道通信

管道（Pipe)通信首先出现在UNIX操作系统中。作为UNIX的一大特色，管道通信立即引起了人们的兴趣。由于管道通信的有效性，一些系统继UNIX之后相继引入了管道技术，管道通信是一种重要的通信方式。

所谓管道，就是连接两个进程之间的一个打开的共享文件，专用于进程之间进行数据通信。发送进程可以源源不断地从管道一端写入数据流，每次写入的信息长度是可变的；接收进程在需要时可以从管道的另一端读出数据，读出单位长度也是可变的。显然，管道通信的基础是文件系统。

在对管道文件进行读写操作的过程中，发送进程和接收进程要实施正确的同步和互斥，以确保通信的正确性。管道通信机制中的同步与互斥都由操作系统自动进行，对用户是透明的。

管道通信具有传送数据量大的优点，但通信速度较慢。

计算机四级操作系统-4-并发与同步

原文：https://www.cnblogs.com/jtd666/p/12505414.html