pv操作典型例题_pv操作经典例题

pv操作典型例题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“pv操作经典例题”。

例1 在某展示厅设置一个自动计数系统，以计数器count表示在场的人数，count是动态变化的，若有一个人进入展示厅进程pin对计数器count加1，当有一个人退出展示厅时，进程pout实现计数器减1。由于进、出所以展示厅的人是随机的，用P-V操作实现。（并发进程之间的互斥问题）

解：定义信号量：S——表示是否有进程进入临界区，初值为1.（表示没有进程进入临界区）begin count: Integer;S: semaphore;count:=0;S:=1;cobegin proce Pin R1: Integer;begin P(S);R1:=count;R1:=R1+1;count:=R1;V(S);end;Proce Pout R2: Integer;begin P(S);R2:=count;R2:=R2-1;count:=R2;V(S);end;count;end;

例2 与生产者和消费过者相似的问题，把―A进程将记录送入缓冲器‖看生产者生产了一件物品且把物品存入缓冲器，把―B进程从缓冲器中取出记录并加工‖看作是消费者从缓冲器取出物品去消费，缓冲器中只能放一个记录（一件物品），用P-V操作实现。（并发进程之间的同步问题）

解：定义两个信号量为：sp和sg。

sp:表示生产者是否右以把物品存入缓冲器。由于缓冲器只能存放一个物品，因此sp的初值为1，即sp:=1。

sg：表示缓冲是否存有物品，它的初值应该为0，即sg：=0，表示缓冲器中还没有物品存在。

生产者和消费者两个进程并发执行时，可按以下的方式实现同步：

sp:=1;sg:=0;cobegin proce producer(生产者进程)begin L1:produce a product;P(sp);Buffer:=product;V(sg);goto L1 end proce consumer(消费者进程)begin L2: P(sg);Take a product;V(sp);consume;goto L1 end;coend;

例3 如果一个生产者和一个消费共享缓冲器容量为可以存放n件物品时，生产者总可继续存入物品；同时当缓冲器的物品不为―0‖时，消费者总可从缓冲器中取走物品，用P-V操作实现。（并发进程之间的同步问题）

解：sp：表示生产者是否可以把物品存入，初值为n；（因为，缓冲器的容量为n件物品）； sg：表示缓冲器中是否存有物品，初值为0.B: away[0:n-1]of integer;k, t: integer;k:=0;t:=0;sp:=n;sg:=0;cobegin proce producer begin L1:produce a product;B[k]:=product;k:=(k+1)mod n;V(sg);goto L1 coend;proce consumer begin L2:P(sg);Tack a product from B[t];t:=(t+1)mod n;V(sp);consume;goto:= L2 end coend

例4 桌上有一只盘子，每一次放入一个水果，爸爸向盘中放苹果，妈妈向盘中放桔子，一个女儿专吃盘中的苹果，一个儿了专等吃盘中的桔子。试用P-V操作定出他们能同步的流程图。（并发进程之间同步与互斥的混合问题）

解：定义信号量：dish:表明盘子中是否为空，初值为1； Apple:表明盘子中是否有苹果，初值为0； Orange:表明盘子中是否有桔子，初值为0； main(){cobegin father();mother();son();daughter();coend } father(){ P(dish);…

放苹果 … V(apple);} mother(){ P(dish);… 放桔子

… V(orange);} son(){ P(orange);… 取桔子

… V(dish);} daughter(){ P(apple);…

取苹果

… V(dish);}

例5 设公共汽车上，司机和售票员的活动分别为：司机的活动是启动车辆、正常开驶、到站停车；售票员的活动是关门、售票、开门。①试指出在汽车出站、行驶、到站过程中，述两种活动有什么同步关系？②用P-V操作实现它们之间的同步关系。（并发进程之间的同步问题）

解：①司机启动车辆与售票员关车门为同步关系；

司机到站停车与售票员开车门为同步关系。

②定义两个信号量： S1——表示门是否关了,初始值为0； S2——表示汽车是否到站，初始值为0 main(){cobegin Proce司（）；

Proce售（）；

coend } Proce司（）{ P(S1);启动；

行驶；

到站停车；

V(S2);} Proce售（）{ 关车门；

V（S1）;售票；

P（S2）；

开车门；

}

例6 多个进程共享一个文件，其中写文件的称为写者，读文件的称为读者，写者与写者、写者与读者之间要互斥地访问文件，读者之间可同时读，试用P-V操作实现它们之间的关系。（进程之间的互斥问题）

解：定义变量：count:表现当前读者个数，初值为0；

mutex:用来对共享变量count进行互斥访问，初值为1；

write:用来使写者与写者，写者与读者之间互斥访问文件，初值为1.semaphone mutex:=1;semaphone write:=1;int count:=0;main(){cobegin Reader();Writer();coend } Reader(){while(true){P(mutex);if(count==0)p(write)count++;V(mutex);读文件;P(mutex);count--;if(count==0)V(write)V(mutex);} } writer(){while(true){P(write);写文件;V(write);}}

例7 有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试问：（1）为描述读者的动作，应编写几个程序，设置几个进程？（2）试用PV操作描述读者进程之间的同步关系。

答：读者的动作有两个，一是填表进入阅览室，这时要考虑阅览室里是否有座位；一是读者阅读完毕，离开阅览室，这时的操作要考虑阅览室里是否有读者。读者在阅览室读书时，由于没有引起资源的变动，不算动作变化。

算法的信号量有三个：seats——表示阅览室是否有座位（初值为100，代表阅览室的空座位数）；readers——表示阅览室里的读者数，初值为0；用于互斥的mutex，初值为1。读者进入阅览室的动作描述getin： while(TRUE){ P(seats);/*没有座位则离开*/ P（mutex）/*进入临界区*/ 填写登记表;进入阅览室读书;V（mutex）/*离开临界区*/ V（readers）}

读者离开阅览室的动作描述getout： while(TRUE){ P（readers）/*阅览室是否有人读书*/ P（mutex）/*进入临界区*/ 消掉登记；

离开阅览室；

V（mutex）/*离开临界区*/ V（seats）/*释放一个座位资源*/ }

例8 设UNIX文件系统中的目录结构如下图所示：

¡

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ usr bin dev etc lib lost+found mnt tmp

¡ mengqc ¡ liu

sub1¡ … …

… m1.c m2.c

file_a(1)设当前工作目录是/usr，那么，访问文件file_a的绝对路径名和相对路径名各是什么？

(2)现在想把工作目录改到liu，应使用什么命令（写出完整命令行）？

(3)如果用 ls –l /usr/mengqc命令列出指定目录的内容，其中有如下所示的一项：

-r w – r--2 mengqc …… m2.c 那么，该文件m2.c对文件主、同组用户、其他用户分别规定了什么权限？ 答:(1)访问文件file_a的绝对路径名是： /usr/mengqc/sub1/file_a 访问文件file_a的相对路径名是： mengqc/sub1/file_a(2)cd /usr/liu 或者 cd liu(3)文件主权限是： 可读、可写，但不可执行

同组用户权限是：只可读

其他用户权限是：无（即：不能读、写或执行）

例9 设公共汽车上有一位司机和一位售票员，它们的活动如下：

司机： 售票员： 启动车辆 售票

正常行车 开车门

到站停车 关车门

请分析司机与售票员之间的同步关系，如何用PV操作实现。

答：为了安全起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下： 司机： 售票员： P（S1）售票 启动车辆 P（S2）

正常行车 开车门

到站停车 关车门 V（S2）V（S1）

另外，程序中PV操作出现的顺序与信号量的初值设置有关，以本题为例，算法如下描述时，S1、S2的初值均应为0。

司机： 售票员： 正常行车 售票

到站停车 P（S2）

V（S2）开车门

P（S1）关车门

启动车辆 V（S1）

例10 现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下： 段号

主存起始地址

段长度

0 120 40 1 760 30 2 480 20 3 370 20

计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？（注：括号中第一个元素为段号，第二个元素为段内地址。）

答：段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址

逻辑地址（2，15）查段表得段长度为20，段内地址15

逻辑地址（0，60）查段表得段长度为40，段内地址60>40，地址越界，系统发出―地址越界‖中断。

逻辑地址（3，18）查段表得段长度为20，段内地址18

例11 某段表内容如下： 段号

段首地址

段长度

0 120K 40K 1 760K 30K 2 480K 20K 3 370K 20K

一逻辑地址为（2，154）的实际物理地址为多少？

答：逻辑地址（2，154）表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。

例12 考虑下述页面走向：

1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少？ 答：缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。

当内存块数量为3时：

FIFO 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6 2 2 2 1 1 1 2 2 2 7 7 7 1 1 1 3 3 3 5 5 5 1 1 1 6 6 6 3 3 发生缺页中断的次数为16。

在FIFO算法中，先进入内存的页面被先换出。当页6要调入时，内存的状态为4、1、5，考查页6之前调入的页面，分别为5、1、2、4，可见4为最先进入内存的，本次应换出，然后把页6调入内存。

LRU 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 1 1 1 4 4 5 5 5 1 1 7 7 2 2 2 2 2 2 2 2 6 6 6 3 3 3 3 3 3 3 3 1 1 1 2 2 2 2 6 6 1 6 发生缺页中断的次数为15。

在LRU算法中，最近最少使用的页面被先换出。当页6要调入时，内存的状态为5、2、1，考查页6之前调入的页面，分别为5、1、2，可见2为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。

OPT 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 1 1 1 1 1 1 3 3 3 3 6 2 2 2 2 2 2 7 2 2 2 3 4 5 6 6 6 6 1 1 发生缺页中断的次数为11。

在OPT算法中，在最远的将来才被访问的页面被先换出。当页6要调入时，内存的状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。

例13 下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）作业号

提交时间

运行时间2 3 0.0 0.4 1.0 8.0 4.0 1.0

提示： 采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。另外，要记住以下公式：

作业i的周转时间Ti＝作业完成时间－作业提交时间

系统中n个作业的平均周转时间，其中Ti为作业i的周转时间。答：采用先来先服务调度策略，则调度次序为l、2、3。

作业号 提交时间 运行时间 开始时间 完成时间 周转时间 1 0.0 8.0 0.0 8.0 8.0 2 0.4 4.0 8.0 12.0 11.6 3 1.0 1.0 12.0 13.0 12.0 平均周转时间T＝（8＋11.6＋12）/3＝10.53 采用短作业优先调度策略，则调度次序为l、3、2。

作业号 提交时间 运行时间 开始时间 完成时间 周转时间0.0 8.0 0.0 8.0 8.0 3 1.0 1.0 8.0 9.0 8.0 2 0.4 4.0 9.0 13.0 12.6 平均周转时间T＝（8＋8＋12.6）/3＝9.53

例14 在一个单道的程序设计系统中，有3个作业J1、J2、J3，它们到达输入井的时间分别为8：50、9：00、9：30，它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在10：00按响应比高者优先算法对它们进行调度，请回答：（1）作业被选中执行的次序是什么？

（2）三个作业被选中时的响应比分别是多少？

提示： 响应比＝作业周转时间/作业运行时间＝1＋作业等待时间/作业运行时间 答：系统在10：00，计算作业的响应比：

以J1为例，它的作业计算时间是1.5小时，即90分钟；J1从8：50到达输入井，在10：00时刻，J1的等待时间为70分钟，因此作业J1的响应比为：1＋70分钟/90分钟=1.77 同理，J2：1＋60分钟/24分钟=3.5 J3：1＋30分钟/60分钟=1.5 因此按照响应比高者优先算法，优先调度J2。在10：24，J2完成。这时计算J1、J3的响应比：

J1：1＋（70＋24）分钟/90分钟=2.04 J3：1＋（30＋24）分钟/60分钟=1.9 按照响应比高者优先算法，优先调度J1。

在11：54，J1完成，系统调度J3，J3的响应比为1＋（30＋24＋90）分钟/60分钟=3.4 因此，作业被选中执行的次序是J2、J1、J3。

三个作业被选中时的响应比分别是：J1，2.04；J2，3.5；J3，3.4。