操作系统复习例题 2

例3.1一个单cpu的操作系统共有n个进程，不考虑进程状态过度情况：

1）给出运行进程的个数。

2）给出就绪进程的个数。

3）给出等待进程的个数。

解（1）一个运行进程（2）m个就绪进程（3）n-m-1个等待进程。

例3.2进程之间存在哪几种相互制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？

1）若干同学去图书馆借书；

2）两队举行篮球比赛；

3）流水线生产的各道工序；

4）商品生产和社会消费。

解有直接制约关系（即同步问题）和间接制约关系（即互斥问题）。同步问题是存在逻辑关系的进程之间相互等待所产生的制约关系，互斥问题是相互无逻辑关系的进程间竞争使用资源所发生的制约关系。

1）属于互斥关系，因为书的数目是有限的，一本书只能借给一个同学；

2）属于互斥关系，因为篮球只有一个，两队都要争夺；

3）属于同步关系，各道工序的开始都依赖前道工序的完成；

4）属于同步关系，商品没有生产出来，消费无法进行，商品未消费完，生产也无须进行。

例3.3设有8个程序prog1,prog2,…prog8。它们在并发系统中执行时有如图3.4所示的制约关系，试用p、v操作实现这些程序间的同步。

并发系统执行图。

分析本题是用来检查考生对使用p、v操作实现进程间同步的掌握情况。一般地，若要求进程b在进程a之后方可执行时，只需在进程b执行前进行p操作，而在进程a执行完时对同一信号量进行v操作即可。本题要求列出8个进程（程序）的控制关系，使题目显得较为复杂。

但当对进程间的同步理解透彻后，应不难写出对应的程序。解这一类问题还应注意的一点是，要看清图示的制约关系，不要漏掉或多出制约条件。

解图并发程序间的同步如下所示：

设置信号量初值：s1:=s2:=s3:=s4:= s5:=0

parbegin

prog1:begin

do all work;

v(s1);

endprog2:begin

do all work;

v(s2);

endprog3:begin

p(s1);

p(s2);

do all work;

v(s3);

endprog4:begin

p(s1);

p(s2);

do all work;

v(s5);

endprog5:begin

p(s1);

p(s2);

do all work;

v(s4);

endprog6:begin

p(s3);

do all work;

v(s5);

endprog7:begin

p(s4);

do all work;

v(s5);

endprog8:begin

p(s5);

do all work;

endparend

例3.4有个寺庙，庙中有小和尚和老和尚若干人，有一只水缸，由小和尚提水入缸给老和尚饮用。水缸可容10桶水，水取自同一口水井中。

水井径窄，每次仅能容一只水桶取水，水桶总数为3个。若每次只能入缸1桶水和取缸中1桶水，而且还不可以同时进行。试用一种同步工具写出小和尚和老和尚入水、取水的活动过程。

解本题为两个进程共享两个缓冲区的问题。

首先考虑本题有几个进程：从井中取水后向缸中倒水此为连续动作，为一个进程；从缸中取水为另一个进程。

其次，考虑信号量。有关互斥的资源有：水井和水缸。

水井依次仅能一个水桶进出，水缸一次入水为一桶。分别设互斥信号量为：mutex1和mutex2控制互斥。

有关同步问题为：三个水桶无论从井中取水还是入处水缸都是一次一个，应为它设信号量count，抢不到水桶的进程只好等待。水缸满时不可入水，设信号量empty，控制水量，水缸空时不可出水，设信号量full，控制水量。

设置信号量初值：mutex1:=mutex2:=1; count:=3; empty:=10; full:=0;

parbegin

小和尚打水进程：

beginl1：p(empty水缸满否？

p(count取得水桶。

p(mutex1互斥从井中取水。

从井中取水；

v(mutex1);

p(mutex2互斥使用水缸。

倒水入缸；v(mutex2);

v(count归还水桶。

v(full多了一桶水。

goto l1;

end老和尚取水进程：

beginl2: p(full有水吗？

p(count申请水桶。

p(mutex2互斥取水。

从缸中取水；

v(mutex2);

v(count归还水桶。

v(empty水缸中少了一桶水。

goto l2;

endparend.

例3.5 有三个并发进程ｒ、ｍ共享一个缓冲区ｂ，进程ｒ负责从输入设备读入一条记录，每读一条记录后把它存放在缓冲区ｂ中；进程ｍ在缓冲区ｂ中加工进程ｒ存入的记录；进程ｐ把加工后的记录打印输出。缓冲区ｂ中每次只能存放一条记录，当记录被加工输出后，缓冲区ｂ中才可存放另一条新记录。

请用ｐ、ｖ操作为同步机制来描述它们并发执行时能正确工作的程序。

分析本题是三个进程共享一个缓冲区的问题。从题中看出，r、m、p这三个进程严格按照先做进程r，然后做进程m，最后做进程p。只有进程p执行完后，才可以做下一次的r，m，p。

因此，要合理设计p、v操作的顺序与设置信号量的初值。

解设置信号量初值：r:=１m:=p:=0；

parbegin

进程ｒ l1：

从输入设备中读取一条记录；

p(r)；

将读入记录存入缓冲区；

v（m）；

goto l1

进程m l2：

p（m）；

从缓冲区中取出数据信息进行加工，并将其存入缓冲区；

v（p）goto l2

进程p： l3：

p（p）输出缓冲区的信息；

v（r）goto l3

parend；

例3.6 若有三个进程a、b和c协作解决文件打印问题；a将文件记录从磁盘读入主存的缓冲区buffer1，每执行一次读一个记录；b将缓冲区buffer1的内容复制到缓冲区buffer2，每执行一次复制一个记录；c打印缓冲区buffer2的内容，每执行一次打印一个记录。缓冲区的大小和一个记录大小一样。

请用p、v操作来保证文件的正确打印。

分析本题是三个进程共享二个缓冲区的问题。它是一个典型的生产者—消费者问题，其中的难点在于进程b既是生产者又是消费者，处理不好可能造成同步错误或死锁。

解 a、b、c三个进程协作解决文件打印问题的流程为：

设置信号量初值：

mutex1:=mutex2:=1;

**ail1:=**ail2:=1;

full1:=full2:=0;

beginparbegin

进程al1：read from disk;

p(**ail1);

p(mutex1);

put to buffer 1;

v(full1);

v(mutex1);

goto l1;

进程bl2：p(full1);

p(mutex1);

get form buffer 1;

v(**ail1);

v(mutex1);

p(**ail2);

p(mutex2);

put to buffer 2;

v(full2);

v(mutex2);

goto l2;

进程cl3：p(full2)

p(mutex2);

get form buffer 2;

v(**ail2);

v(mutex2);

print record;

goto l3;

parend

end程序中mutex1和mutex2是两个公用信号量，用于控制进程对缓冲区buffer1和缓冲区buffer2这两个临界资源访问的互斥。**ail1、full1、**ail2和full2分别对应两个缓冲区，其中**ail1、**ail2初值为1，表示可以利用的缓冲区数目为1；full1、full2的初值为0，表示存在于缓冲区内的数据的个数为0。通过对这两组私用信号量p、v操作，就实现了进程的同步。

例3.7 进程p1使用缓冲区buffer向进程p2,p3,p4发送消息，要求每当p1向buffer中发消息时，只有当p2,p3,p4进程都读取这条消息后才可再向buffer中发送新的消息。利用p、v原语描述如图所示进程的动作序列。

图进程的动作序列。

分析本题是一个生产者三个消费者共享一个缓冲区问题。它是生产者和消费者问题的一个变形，在生产者和消费者问题中是共用一组缓冲区，每一个缓冲区只需要写一次，读一次。而在这个问题中，每个缓冲区只需写一次，但需读三次。

本题在解题的过程中，我们可以把这一组缓冲区看做三组缓冲区。这样一来，每一个生产者需要同时写缓冲区组中相应的三个缓冲区，而每一个消费者只需读它自己所对应的那组缓冲区中对应的单元即可。生产者须在三个缓冲区都为空时才可写入。

解设信号量初值为：s1=s2=s3=0，s =3

进程p1 进程p2进程 p3进程p4

p（sp（s1p（s2p（s3）

p（s读取消息读取消息读取消息。

p（sv（sv（sv（s）

操作系统复习例题 2

操作系统复习试卷 2

上海大学操作系统2复习

操作系统复习

其他用户还读了