操作系统习题

期中复习：进程同步与互斥

例1：

四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：（1）应定义的信号量及初值：。

（2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作：

例2：一个表达式(a+b) ⨯ (c+d) - (e/f)，可以分成如下几个语句来完成，

t1 = a + b

t2 = c + d

t3 = e / f

t4 = t1 ⨯ t2

t5 = t4 – t3

画出这些语句的前驱关系，并写出一个可并发执行的程序。

例3：桌上有一空盘，允许存放一个水果。爸爸可向盘中放苹果，或放橘子，儿子专门等着吃盘中的橘子，女儿专门等着吃盘中的苹果。规定当盘空时一次只能放一个水果供取用，试实现爸爸、儿子和女儿三个并发进程的同步。

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

例1参考答案：

A() B() C() D()

{ { { {

[1]; [3]; [5]; [7];

read F; read F; read F; read F;

[2]; [4]; [6]; [8];

} } } }

思考题解答：

（1）定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。

（2）从[1]到[8]分别为：P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

例2参考答案：

Semaphore a, b, c, d = 0, 0 , 0 ,0

Begin

Parbegin

Begin t1; signal(a); end;

Begin t2; signal(b);end;

Begin t3; signal(c);end;

Begin wait(a);wait(b); t4; signal(d); end;

Begin wait(c); wait(d); t5; end.

Parend

End

例3参考答案：

分析在本题中，爸爸、儿子、女儿共用一个盘子，盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

信号量:empty=1;orange=0;apple=0;

爸爸进程:

while(1)

{

wait(empty);

放水果;

if (橘子) signal(orange);

if(苹果) signal (apple);

}

儿子进程:

while(1)

{

wait (orange);

取橘子;

signal (empty);

}

女儿进程:

while(1)

{

wait (apple);

取苹果;

signal (empty);

}

例4参考答案：

解法1：

（1）因阅览室有100个座位可容纳100个读者同时阅读，基于这种并行性，因此可为每一个读者设立一个进程。因为任何读者进出阅览室都做相同的工作（登记阅读和取消登记）。所以对于100个读者进程可以共同对应一个程序。此程序功能是入室时查表登记，入室阅读和离室时查表取消登记。

（2）设置信号量（S位）来表示空座位个数，处置为100，用来控制进入阅览室的读者进程个数不超过100。设置信号量（S表）来表示被共享的登记表这一临界资源。处置为1，用来防止两个以上读者进程同时查表。

每个进程和其他进程之间的同步关系如下：

解法2：

（1）将读者入室查表登记和离室查表取消登记各编一个程序，这样每个读者需设两个进程，分别执行入室和离室程序。

（2）原设信号量S为座位入室进程私有信号量，增设离室进程私有信号量S人---入室读者数，初值为0，这时进程间的同步关系如下：

处理机的调度：

例1：假定在单CPU条件下有下列要执行的作业：

①用一个执行时间图描述在下列算法时各自执行这些作业的情况：先来先服务法FCFS、时间片轮转法RR（时间片＝1）和短进程优先（SPF）。

②对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？

③对于上述每种算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？例1参考答案：

时间片轮转法（RR）

例2：银行家算法

填空题选择题：

1、如果系统中有N个进程，处于运行状态的进程最多几个(1)，最少几个(0)；就绪进程最多几个(N-1)最少几个(0)；阻塞进程最多几个(N)，最少几个(0)？

2、若信号量S初值为2，当前值为−1，则表示有 B 个进程在与S相关的队列上等待。

A．0 B．1 C．2 D．3

3、若两个并发进程相关临界区的互斥信号量MUTEX现在取值为0，则正确的描述应该是 B 。

A．没有进程进入临界区

B．有一个进程进入临界区

C．有一个进程进入临界区，另一个在等待进入临界区

D．不定

4、系统中有2份共享资源，有3个并行进程，每个进程都需要该共享资源2份，则在这3个进程之间__C___。

A.一定会发生死锁

B.一定不会发生死锁

C.不一定会死锁

D.以上都不对

5、关于线程的说法中错误的是__B___。

A.引入线程是为了减少程序并发执行时所付出的时空开销，使OS具有更好的并发

性。