操作系统习题集 - 2 - 进程管理

习题集 - 2 - 进程管理

1. 在优先级调度中，__________类进程可能被“饿死”，即长时间得不到调度。 A． 短进程 B． 长进程 C． 低优先级进程 D． 大内存进程

解： C。优先级调度算法（PRI）的基本思想是：内核为每个进程赋予一个优先级，进程按照优先级的大小顺序在就绪队列中排队，内核将CPU分配给就绪队列头部的第一个进程——优先级最大的进程。因此，进程的优先级越低，在就绪队列中的排队位置就越靠近队列尾，获得运行之前的等待时间就越长。低优先级的进程必须等待所有高优先级进程运行结束后才会被调度运行。如果不断有高优先级的进程加入就绪队列，那么低优先级进程就会一直等待下去。这就是所谓的“饿死”现象。

2. 在下面的系统调用中，__________不会导致进程阻塞。

A． 读/写文件 B． 获得进程PID C． 申请内存 D． 发送消息

解： B。当正在执行的进程需要使用某种资源或等待某个事件时，如果资源已被其他进程占用或事件尚未出现，该进程不能获得所需的资源而无法继续运行，于是，进程将被阻塞。进程在阻塞状态中等待资源被释放，或等待事件的发生。所以，进程在执行系统调用时，如果需要使用某种资源，就可能导致进程阻塞。“读/写文件”需要使用设备和文件缓冲区；“申请内存”需要分配内存资源；“发送消息”需要使用消息缓冲区。

3. 下面关于临界区的叙述中，正确的是__________ A． 临界区可以允许规定数目的多个进程同时执行 B． 临界区只包含一个程序段 C． 临界区是必须互斥地执行的程序段 D． 临界区的执行不能被中断

解： C。临界段（临界区）的概念包括两个部分：① 临界资源：必须互斥访问的资源。例如，需要独占使用的硬件资源，多个进程共享的变量、结构、队列、栈、文件等软件资源。② 临界区：访问临界资源的、必须互斥地执行的程序段。即，当一个进程在某个临界段中执行时，其他进程不能进入相同临界资源的任何临界段。

1

4. 资源顺序分配法破坏了死锁发生的__________必要条件。 A． 互斥占用 B． 占有等待 C． 非剥夺 D． 循环等待

解： D。资源顺序分配方法是：给系统中的每类资源赋予一个自然数的序号，限制进程只能严格按照资源序号由小到大的顺序申请资源。该方法可以避免“循环等待”的情况发生。因为，若出现循环等待，则必会有进程在获得大序号资源后申请小序号资源。

5. 假设某操作系统采用RR调度策略，分配给A类进程的时间片为100 ms，分配给B类进程的时间片为400 ms，就绪进程队列的平均长度为5（包括正在运行的进程），其中A类进程有4个，B类进程有1个，所有进程的平均服务时间为2 s，问A类进程和B类进程的平均周转时间各为多少？（不考虑IO情况）

解析:时间片轮转调度（RR）是轮流地调度就绪队列中的每个进程，进程每次占用CPU的时间长度限制为时间片的大小。当采用固定的时间片大小时，每个进程按照固定周期被循环地执行。所以，进程的执行速度是由该进程的时间片大小在一个循环周期中所占的比例决定的，比例越高，进程的相对执行速度就越快。

解:因为就绪进程队列的平均长度为5，单个RR调度循环周期的时间为 4×100＋1×400＝800（ms）

A类进程需要20个时间片的执行时间，B类进程需要5个时间片的执行时间（1 s＝1 000 ms）。 A类进程的平均周转时间为 20×0.8＝16(s)

B类进程的平均周转时间为 5×0.8=4(s)

6. 某多道程序设计系统中配有一台处理器CPU和两台输入/输出设备IO1、IO2，现有优先级由高到低

2

的3个进程P1、P2、P3同时存在，它们使用资源的先后顺序和占用时间分别是： 进程P1：IO2(30 ms)，CPU(10 ms)，IO1(30 ms)，CPU(10 ms)，IO2(10 ms)。 进程P2：IO1(20 ms)，CPU(20 ms)，IO1(40 ms)。 进程P3：CPU(30 ms)，IO2(20 ms)。

若进程调度采用“可抢占的最高优先级”调度算法，且忽略调度等所需的时间，请回答下列问题： (1) 进程P1、P2、P3从开始到完成所用的时间分别是多少?(要求用坐标画出进程P1、P2、P3的工作过程，其中横坐标表示时间，纵坐标表示CPU和IO设备。)

(2) 这3个进程从开始到全部完成时CPU的利用率为多少?IO1、IO2的利用率为多少?

解析:在“可抢占的最高优先级”调度中，任何时刻内核都将处理机分配给当前最高优先级的就绪进程。也就是说，只有当高优先级进程主动放弃CPU时，低优先级进程才有机会运行，并且，一旦高优先级进程需要使用CPU时，内核就会剥夺低优先级进程的CPU，分配给它使用。

在本题中，由于进程P1和P2在开始执行时先需要进行IO，所以最低优先级的进程P3获得了CPU。但是，P3运行了20 ms后就被P2抢占了CPU，因为P2刚好完成了IO，并且P2的优先级大于P3。同样的原因，P2运行了10 ms后，就被P1抢占了CPU。P1在CPU上运行10 ms之后再次需要进行IO而放弃CPU，于是，P2、P1获得继续运行的机会。以此方式，P1、P2和P3相继完成自己的运行过程。

解:根据“可抢占的最高优先级”调度算法，画出进程P1、P2、P3的工作过程(见图29)。

图2.9进程P1、P2、P3

进程P1、P2、P3从开始到完成所用的时间分别是90 ms、110 ms、80 ms。这3个进程从开始到全部完成时的时间为110（ms），在此期间内： CPU的利用率＝(30+20+10+10)/110=63.6% IO1的利用率=(20+30+40)/110=81.8%

3

IO2的利用率=(30+20+10)/110=54.5%

7. 论述以下解决双进程临界区问题的软件算法是错误的。 ProcessP0: do {

flag［0］=true；

①

while(flag［1］)； ③ 临界区

flag［0］=false； }while(1)； ProcessP1： do {

flag［1］=true；

②

while(flag［0］)； ④ 临界区

flag［1］=false； }while(1)；

解析: 在算法中，两个进程P1和P2各自拥有自己的标志牌flag［0］和flag［1］。当进程需要进入临界区时，举起标志牌（设置值为true）。然后观察对方是否举起标志牌，是则等待并继续观察（while语句），直到对方放下标志牌（设置值为false）。这时，进程才进入临界区。进程退出临界区时，放下标志牌（设置值为false）。

解:通过使用标志牌flag［0］和flag［1］，能够保证满足“互斥”条件。但是，当两个进程按照①②③④的顺序执行程序时，它们各自举起了标志牌，同时都因为观察到对方也举起了标志牌而等待在while语句中。由于两个进程都不会放下自己的标志牌，因此都无法进入临界区，不能满足“有限等待”的条件。所以，上述解决双进程临界区问题的算法是错误的。

4

8. 以下解决双进程访问共享变量count的程序是否存在错误？试用信号量实现。 Share：count=0； Int: flag[2]; cobegin

Process P0:

do {

flag[0]=true； ① while(flag[1])； ③ count=count+1； flag[0]=false； }while(1)；

Process P1： do {

flag[1]=true； ② while(flag[0])； ④ count=count+1； flag[1]=false；

}while(1)；

coend

解： 在上述程序中，访问共享变量的语句count=count+1构成临界区。两个进程P0和P1各自拥有自己的标志牌flag[0]和flag[1]。当进程需要进入临界区时，举起标志牌（设置值为true）。然后观察对方是否举起标志牌，是则等待并继续观察（while语句），直到对方放下标志牌（设置值为false）。这时，进程才进入临界区。进程退出临界区时，放下标志牌（设置值为false）。

通过使用标志牌flag[0]和flag[1]，能够保证满足“单一进入”的条件。但是，当两个进

程按照①、②、③、④的顺序执行程序时，它们各自举起了标志牌，同时都因为观察到对方也举起了标志

5

牌而等待在while语句中。由于两个进程都不会放下自己的标志牌，因此都无法进入临界区，不能满足“有限等待”的条件。所以，上述程序是错误的。

设置信号量S实现对共享变量count的互斥访问。

Share：count=0； struct semaphore S=1； cobegin

Process P0:

do { P(S);

count=count+1； V(S);

}while(1)；

Process P1： do {

P(S);

count=count+1； V(S);

9. 假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作。用信号量实现该过程。 解：设置信号量S：控制进入阅览室的人数。初值=100。 设置信号量mutex：控制登记表的互斥使用。初值=1。 struct semaphore s=100,mutex=1;

6

}while(1)；

coend

cobegin

reader (i ) (i=1,2,?,k)

{

P(S); P(mutex); 写登记表； V(mutex); 阅读；

P(mutex);

写登记表; V(mutex);

V(S); 离开；

}

coend

10. 在具有N个进程的系统中，允许M个进程(N≥M≥1)同时进入它们的共享区，其信号量S的值的变化范围是（1） ，处于等待状态的进程数最多是（2）个。

解：信号量S用于控制进入共享区的进程数，初值为M。极端情况是N个进程都需要进入共享区。 （1）（M－N，M）； （2）N－M

11. 在测量控制系统中，数据采集任务把所采集的数据送一单缓冲区；计算任务从该缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步操作算法。 解：设置信号量S1和S2控制数据采集任务与计算任务之间的同步。 初值：S1=1，S2=0。

7

struct semaphore S1=1, S2=0; cobegin

数据采集任务： 计算任务： begin

end

begin

While（true）{

采集数据； P(S1);

While（true）{

P(S2);

从缓冲区读出数据；

数据写入缓冲区； V(S2);

V(S1); }

计算；

} end coend

12. 有n+1个进程A1,A2,?,An和B，A1,?,An通过同一缓冲区各自不断向B发消息，B不断取消息，它必须取走发来的每一个消息。刚开始时缓冲区为空，试用P、V操作正确实现之。 解：设置信号量S1和S2控制进程Ai与进程B之间的同步。初值：S1=1，S2=0。 设置信号量S控制进程Ai之间互斥地使用缓冲区。初值：S=1。 struct semaphore S1=1, S2=0, S=1; cobegin

进程Ai（i=1,2，···，n）： begin

进程B： begin

While（true）{

P(S2);

从缓冲区读出消息；

While（true）{

P(S1)； P(S);

8

} end

消息写入缓冲区； V(S); V(S2);

V(S1); }

end

coend

13. 桌子上有一只盘子，每次只能放入或取出一个水果。现有许多苹果和橘子。一家四口人各行其职。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用PV操作来实现四人之间的同步算法。

解：设置信号量empty表示盘子的状态。初值：empty =1。

设置信号量apple表示盘子中的苹果。初值：apple =0。 设置信号量orange表示盘子中的橘子。初值：orange =0。 struct semaphore empty =1, apple =0, orange =0; Parbegin 爸爸: begin

L1: P(empty);

放苹果; V(apple); Goto L1; End;

妈妈：begin

L2: P(empty);

放橘子; V(orange);

9

Goto L2; End;

女儿：begin

L3: P(apple);

取苹果; V(empty); Goto L3; End;

儿子：begin

L4: P(orange);

取橘子; V(empty); Goto L4; End;

Parend

14. 下面是两个并发执行的进程。它们能正确运行吗?若不能请举例说明，并改正之。 Parbegin

Var x：integer；

Process P1 Var y，z：integer； Begin x:=1； ① y:=0； ③

Process P2

Var t，u：mteger； Begin x:=0； ②

t:=0； ⑥

10

nonel none2

输入进程 Buf1 加工进程 Buf2 输出进程 nonel none2

18. 三个进程如下，试补充完整：

初值：nonel=none2=0；nonfl=nl，nonf2=n2， 输入进程： while(1){ (1) P(s1)； 输入一个字符到bufl； V(s1)；

(2) ；

} 加工进程： while(1){ P(nonel)； (3) ；

从buf1中取一个字符到ch； (4) ； V(nonfl)；

，s2=1。 16

sl=1 P(nonf2)；

P(s2)；

ch送bur2； V(s2)； V(none2)； } 输出进程：

while(1){

(5) ； (6) ；

从bur2取一个字符到打印口；

(7) ； (8) ； }

解：通过分析程序可知，信号量s1和s2分别用于实现对缓冲区buf1，buf2的互斥访问；nonel和nonfl用于实现输入进程与加工进程之间的同步，none2和nonf2用于实现加工进程与输出进程之间的同步。 (1) P(nonfl) (2) V(nonel) (3) P(s1) (4) V(s1) (5) P(none2) (6) P(s2) (7) V(s2) (8) V(nonf2)

19. 一个仓库，可以存放A和B两种产品，但要求： (1)每次只能存人一种产品(A或B)； (2)A产品数量—B产品数量

17

其中，M、N是正整数，试用P、V操作描述产品A与产品B的入库过程。 解：条件（1）说明产品A与产品B必须互斥地放入仓库。

条件（2）和（3）说明每放入一个产品B，就可以多放入一个产品A；反之亦然。 设置信号量mutex控制产品A与产品B互斥地放入仓库。初值：mutex=1。 设置信号量Sa表示可以放入仓库的产品A的数目。初值：Sa=M-1。 设置信号量Sb表示可以放入仓库的产品B的数目。初值：Sb=N-1。 产品A与产品B的入库过程如下： Semaphore： Sa, Sb, mutex;

Sa = m－1; Sb= n－1; mutex = 1; process_A ( ) { while（1）{

P(Sa)；

P(mutex)； A产品入库； V(mutex)； V(Sb)； } }

process_B ( ) { while（1）{

P(Sb)；

P(mutex)； B产品入库； V(mutex)；

18

V(Sa)； } }

20. 今有A、B两组进程共享文件P，规定同组进程可以同时读文件P，但当有A组(或B组)进程在读文件P时，就不允许B组(或A组)进程读文件P。现定义两个计数器C1和C2，分别记录A组和B组中读文件P的进程数。当用P、V操作进行管理时，需要三个信号量S1、S2和SAB才能保证正确地并发执行。程序结构如下： begin

S1, S2, SAB: semaphore; C1, C2: integer;

S1: = 1;S2: = 1;SAB: = 1;C1: =0;C2: =0; cobegin

process Ai(i = 1,2,··· ) begin ( ); /*(1)*/ C1: =C1+1;

If Cl=l then( ); /*(2)*/

( ); /*(3) */

read P; ( ); /*(4)*/ C1:=C1-1;

if C1 =0 then( ); /* (5) */ ( ); /*(6)*/ end;

19

process Bj(j = 1,2, ···) begin ( ); /*(7)*/

C2: =C2+1;

If C2=l then( ); /*(8)*/

( ); /*(9)*/

read P; ( ); /*(l0) / C2: = C2 - 1;

if C2 = 0 then( ); /*(11) */

( ); /* (12)*/

end; eoend; end； 请回答：

(1)说明信号量S1，S2，SAB的作用：

(2)在上述程序的填空处填上适当的P、V操作，以保证它们能够正确地并发执行。

解： S1的作用是控制计数器C1的互斥使用。

S2的作用是控制计数器C2的互斥使用。

SAB 的作用是控制A组和B组对文件的互斥使用。

(1) P(S1) (2) P(SAB) (3) V(S1) (4) P(S1) (5) V(SAB) (6) V(S1) (7) P(S2) (8) P(SAB) (9) V(S2) (10) P(S2) (11) V(SAB) (12) V(S2)

20

本文来源：https://www.bwwdw.com/article/ili.html