第一章 The P,V Theorem
在操作系统理论中有一个非常重要的概念叫做P,V原语。在我们研究进程间的互斥的时候经常会引入这个概念，将P,V操作方法与加锁的方法相比较，来解决进程间的互斥问题。实际上，他的应用范围很广，他不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。 一 Introduction of P,V Theorem
阐述P,V原语的理论不得不提到的一个人便是赫赫有名的荷兰科学家E.W.Dijkstra。如果你对这位科学家没有什么印象的话，提起解决图论中最短路径问题的Dijkstra算法应当是我们再熟悉不过的。P,V原语的概念以及P,V操作当中需要使用到的信号量的概念都是由他在1965年提出的。 1 Some Conceptions
信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号量的变量及对它进行的两个原语操作。信号量为一个整数，我们设这个信号量为：S。很显然，我们规定在S大于等于零的时候代表可供并发进程使用的资源实体数，S小于零的时候，表示正在等待使用临界区的进程的个数。根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。
p操作和v操作是不可中断的程序段，称为原语。P,V原语中P是荷兰语的Passeren，相当于英文的pass,V是荷兰语的Verhoog，相当于英文中的incremnet。
P原语操作的动作是：
（1）S减1；
（2）若S减1后仍大于或等于零，则进程继续执行；
（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
V原语操作的动作是：
（1）S加1；
（2）若相加结果大于零，则进程继续执行；
（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。
需要提醒大家的是：P,V操作首先是一个原语操作，对于每一个进程来说，都只能进行一次。而且必须
成对使用。且在P,V愿语执行期间不允许有中断的发生。
对于具体的实现，方法非常多，可以用硬件实现，也可以用软件实现。这里不再赘述。
2 The Most Important Conceptions
临界资源是指每次仅允许一个进程访问的资源。属于临界资源可以是硬件的打印机、磁带机等，软件的有消息缓冲队列、变量、数组、缓冲区等。每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，该进程进入后不允许其他进程进入。
进程的同步和互斥互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者
对资源的访问顺序，即访问是无序的。
同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。
二Several Typical Examples
本节我们讨论几个利用信号量来实现进程互斥和同步的经典例子。这里的问题关键是如何选择信号量和如何安排P、V原语的使用顺序。
齿槽转矩依据信号量与进程的关系，我们可把进程中使用的信号量分成私有信号量和公用信号量。私有信号量是指只与制约进程和被制约进程有关的信号量；公用信号量是指与一组并发进程有关的信号量。这里请不要和C++、JAVA 等编程语言的公有、私有相混淆。这里指的是相对于共享资源来说的。
1 生产者一消费者问题(producer-consumer problem)
生产者--消费者问题(producer-consumer problem)是指若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。
问题描述：假设“生产者”进程不断向共享缓冲区写人数据(即生产数据)，而“消费者”进程不断从共享缓冲区读出数据(即消费数据)；共享缓冲区共有n个；任何时刻只能有一个进程可对共享缓冲区进行操作。所有生产者和消费者之间要协调，以完成对共享缓冲区的操作。
Figure 1.1: producer-consumer problem
我们可把共享缓冲区中的n个缓冲块视为共享资源，生产者写人数据的缓冲块成为消费者可用资源，而消费者读出数据后的缓冲块成为生产者的可用资源。为此，可设置三个信号量：full、empty和mute
x。其中：full表示有数据的缓冲块数目，初值是0；empty表示空的缓冲块数初值是n；mutex用于访问缓冲区时的互斥，初值是1。实际上，full和empty间存在如下关系：full+ empty = N
The P,V code Using Pascal
buffer: array [0..k-1]of integer;
in,out: 0..k-1;//in记录第一个空缓冲区，out记录第一个不空的缓冲区
empty,full,mutex: semaphore;
//empty控制缓冲区不满,full控制缓冲区不空,mutex保护临界区；
//初始化empty=k,full=0,mutex=1
cobegin
procedure producer: procedure consumer:
while true then while true then
begin begin
produce(&item); p(full);
p(empty); p(mutex);
p(mutex); item:=buffer[out];
buffer[in]:=item; out:=(out+1) mod k;
in:=(in+1) mod k; v(mutex);
v(mutex); v(empty);
v(full); consume(&item);
end end
coend
注意：这里每个进程中各个P操作的次序是重要的。各进程必须先检查自己对应的资源
数在确信有可用资源后再申请对整个缓冲区的互斥操作；否则，先申请对整个缓冲区的互斥操后申请
自己对应的缓冲块资源，就可能死锁。出现死锁的条件是，申请到对整个缓冲区的互斥操作后，才发现自己对应的缓冲块资源，这时已不可能放弃对整个缓冲区的占用。如果采用AND信号量集，相应的进入区和退出区都很简单。如生产者的进入区为Swait(empty，mutex)，退出区为Ssignal(full，mutex)。
2 读者--写者问题(Readers-Writers Problem)
问题描述：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)，此外还需要满足以下条件：
（1）任意多个读进程可以同时读这个文件；
（2）一次只有一个写进程可以往文件中写；
（3）如果一个写进程正在进行操作，禁止任何读进程度文件。
实验要求用信号量来实现读者写者问题的调度算法。实验提供了Semaphore类，该类通过P()、V()两个方法实现了P、V原语的功能。实验的任务是修改Reader类的Read方法以及Writer类的Write方法。
我们需要分两种情况实现该问题：
读优先： 要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。
写优先： 一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。
The P,V code Using Pascal
读者优先算法：
rwmutex 用于写者与其他读者/写者互斥的访问共享数据
rmutex 用于读者互斥的访问
readcount 读者计数器
var rwmutex, rmutex ： semaphore := 1, 1 ；
int readcount = 0;
cobegin
procedure reader_i
begin // i=1,2,?.
P(rmutex);
Readcount + +;
if (readcount = = 1) P(rwmutex);
V(rmutex);
读数据；
P(rmutex);
Readcount - -;
if (readcount = = 0) V(rwmutex);
V(rmutex);
防水伸缩缝
end
procedure Writer_j
begin // j = 1,2,?.
P(rwmutex);
写更新；
V(rwmutex);
end
coend
The P,V code Using Pascal
写者优先：
1）多个读者可以同时进行读
2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
如果读者数是固定的，我们可采用下面的算法：
rwmutex：用于写者与其他读者/写者互斥的访问共享数据
rmutex： 该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作
var rwmutex, rmutex ： semaphore := 1, 10 ；
cobegin
procedure reader_i
begin // i=1,2,?.
P(rwmutex); //读者、写者互斥
P(rmutex);
V(rwmutex); // 释放读写互斥信号量，允许其它读、写进程访问资源
读数据
；
V(rmutex);
end
procedure Writer_j
绷带装
begin // j = 1,2,?.
P(rwmutex);
for (i = 1;i <= 10;i + +) P(rmutex);
//禁止新读者，并等待已进入的读者退出
写更新；
for (i = 1;i <= 10;i + +) V(rmutex);
// 恢复允许rmutex 值为10
V(rwmutex);
end
coend
问题扩展
如果读者写者均是平等的即二者都不优先，如何实现？
3 哲学家进餐问题(The Dining Philosophers Problem)
Figure 1.2: The Dining Philosophers Problem
问题描述：
(由Dijkstra首先提出并解决)5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放
一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；
The P,V code Using Pascal
解法一：
u型吊臂semaphore Fork[i] := 1(i = 0, 1, 2, 3, 4)
begin
Thiking;
Being hangery;
P(Fork[i mod 5]);
p(Fork[(i + 1) mod 5]);
Eating;
v(Fork[i mod 5]);
v(Fork[(i + 1) mod 5]);
end
解法二：
semaphore c[0]?c[4], 初值均为1；
Integer i = 0, 1,..., 4;
procedure philosopher_i
begin
if i mod 2 = = 0 then
begin
p(c[i]);
p(c[i + 1] mod 5);
Eating;
v(c[i]);
v(c[i + 1] mod 5);
end
else
begin
p(c[i + 1] mod 5);
p(c[i]);
Eating;
v(c[i + 1] mod 5);
v(c[i]);
end
end
4 理发师问题(Barber Problem)
问题描述：
理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。
The P,V code Using Pascal
1)控制变量waiting用来记录等候理发的顾客数，初值均为0；
2)信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；
3)信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；
4)信号量mutex用于互斥，初值为1
int waiting=0 ； //等候理发的顾客数
int chairs=n； //为顾客准备的椅子数
semaphore customers=0, barbers=0,mutex=1;
cobegin
barber()
begin
while(TRUE); //理完一人，还有顾客吗?
P(cutomers); //若无顾客，理发师睡眠
P(mutex); //进程互斥
waiting := waiting – 1; //等候顾客数少一个
V(barbers); //理发师去为一个顾客理发
V(mutex); //开放临界区
cut-hair( ); //正在理发
end
customer()
begin
P(mutex); //进程互斥
if (waiting)
begin
桑拿炉waiting := waiting+1; // 等候顾客数加1
V(customers); //必要的话唤醒理发师
V(mutex); //开放临界区
P(barbers); //无理发师, 顾客坐着养神
get-haircut( ); //一个顾客坐下等理/
end
else
V(mutex); //人满了，走吧!
end
coend
5 吸烟者问题(Smoker Problem)
问题描述：
三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：
烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。
问题分析：
供应者seller随即产生两样东西，提供它们，这里用普通变量来表示
吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。
吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。
mutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。
每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。
The P,V code Using Pascal
vars , S1 ,S2 , S3 ; semaphore ;
S:=1 ; S1:=S2:=S3:=0 ;
fiag1 , flag2 , fiag3 : Boolean ;
fiag1:=flag2:=flag3:=true;
cobegin
process 供应者
begin
repeat
P(S) ;
取两样香烟原料放桌上，由flagi标记；
//nago1 、nage2 、nage3 代表烟草、纸、火柴
if flag2 & flag3 then V(S1) ; //供纸和火柴
else if flag1 & fiag3 then V(S2); //供烟草和火柴
else V(S3) ; //供烟草和纸
until false ;
end
process 吸烟者1
begin
repeat
P(S1) ;
取原料；蛇形线
做香烟；
V(S) ;
吸香烟；
until false ;
end
process 吸烟者2
begin
repeat
p(S2);
取原料；
做香烟；
V(S) ;
吸香烟；
until false ;
end
process 吸烟者3
begin
repeat
P(S3);
取原料；
做香烟；
V(S);
吸香烟；
until false ;
end
coend
第二章 典型练习题目
一生产者--消费者问题扩展
1 扩展一
设有一个可以装A、B两种物品的仓库, 其容量无限大, 但要求仓库中A、B两种物品的数量满足下述不等式: -M≤A物品数量－B物品数量≤N 其中M和N为正整数. 试用信号量和PV操作描述A、B两种物品的入库过程.
问题分析：
若只放入A，而不放入B，则A产品最多可放入N次便被阻塞；若只放入B，而不放入A，则B产品最多可放入M次便被阻塞；每放入一次A，放入产品B的机会也多一次；同理，每放入一次B，放入产品A的机会也多一次.
The P,V code Using Pascal
Semaphore mutex=1，sa=N，sb=M;
cobegin
procedure A: procedure B:
while(TURE) while(TURE)
begin
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议