2024年5月10日发(作者:)
第2章 进程管理解答
一、单项选择题
[解答]
1.d。.
2.c。 进程的实体由PCB、程序与数据3部分组成。
3.b。
4.b。 允许3个进程同时进入互斥段的互斥信号量初值设为3。
5.d。 并发进程之间可能存在同步与互斥关系,也可能不存在任何关系。
6.a。
7.c。 由于互斥信号量的初值是1,则极端情况是一个进程访问临界资源而其
余N-1个进程处于等待状态,即信号量的值为-(N-1)
8.d。 当资源总数为4,并发进程为2,每个进程的最大需求是3时,可能够出
现每个进程都占用2个资源而又申请第3个资源的死锁状态。
9.a。 先来先服务、响应比高者优先和均衡调度算法都属于作业调度算法。
10.b。进程从执行态变成就绪态通常有两种情况:(1)分时操作系统下时间片
到;(2)剥夺式进程调度方式下有更高优先级的进程进入就绪状态。
11.b。
12.c。
13.d。如果存在就绪进程且处理机空闲时,进程调度程序就必然选中一个就绪
进程使之投入运行;所以d错误。
14.d。 a~c概念都不完全。
15.d。 a~c都会引进操作系统选择新进程运行,仅d不会。
16.a 17. a 18。d 19。d 20。b 21。a 22。d 23。d 24。a
25.b 26.c 27。b 28。d 29。c 30。B
二、填空题[解答]
1.线性表 链接表 (或队列) 2.删除 剥夺
3.因为PCB是进程存在的唯一标志,故填PCB 4.资源竞、 进程推进顺序不当
5.非剥夺条件 逐次请求条件 环路条件 6.就绪 运行
7.进程中访问临界资源的那段程序代码
8.当出现死琐的极端情况时,处于等待的进程数为n,故填n
9.可用资源的数目 ,因请求该资源而被阻塞的进程数目
10.剥夺式调度总是将优先级高的进程(不包括等待队列上的进程)投入运行,故填
“剥夺式” 11.P V
12.当信号量知小于零时,其绝对值为被阻塞的进程个数,故填4
13.互斥、同步、条件变量 14. —2~2 15.临界区(或互斥段) 16.程序 数据 PCB.
17.银行家算法 18.同步 19.运行态 进程调度 20.创建 消亡
21.资源分配 独立运行 调度 22.临界区 P操作 V操作
23.引起进程调度的原因 进程调度算法的选择 就绪队列的组织.
三、问答题
1. 操作系统中为什么要引入进程的概念?为了实现并发进程间的合作和协调工作,以及
保证系统的安全,操作系统在进程管理方面应做哪些工作?
[解答]在多道程序环境下,程序的并发执行代替了程序的顺序执行,并发执行破坏了程序的
封闭性和可再现性,使得程序和计算不再一一对应。此外,并发执行又导致了资源共享和资
源竞争,这造成了各并发执行的程序间可能存在相互制约的关系。因此,并发执行的程序已
不再处于一个封闭的系统中,从而出现了许多新的特征,即独立性、并发性、动态性以及并
发程序相互间的制约性。程序这个静态概念已经无法真实地反映并发程序执行的特征,所以
我们需要一个能够描述并发程序执行过程且用来共享资源的基本单位——进程,即“可以并
发执行的程序在一个数据集合上的一次执行过程。”
操作系统对进程管理方面应做的工作如下。
运行过程中的状态转换。
(2)进程同步:系统必须设置同步机制来实现对所有进程的运行进行调节,协调的方式包
括继承的互斥和进程的同步。
(3)进程通信:多道程序环境下可能需要诸进程合作完成一个任务,这些进程相互间需要
通过交换信息来协调各自工作的进度。因此系统必须具有进程之间通信(交换信息)的能力。
(4)进程调度:系统必须能够在处理机空闲中,按一定算法从就绪进程队列中选择一个就
绪进程,把处理机分配它,并为之设置运行的现场使其投入运行。
2. 试比较进程和程序的区别。
[解答] 进程和程序的区别如下:
(1)程序是指令的有序集合,是一个静态的概念,其本身没有任何运行的含义,进程是程
序在处理机上的一次执行过程,是一个动态的概念。
(1)进程控制:系统必须设置一套控制机构来实现进程创建、进程撤消以及进程在
(2)程序作为软件资料可长期保存,而进程则是有生命期的,因创建而产生、因调度而执
行、因得不到资源而暂停、因撤消而消亡。
(3)程序是记录在介质上指令的有序集合,而进程则由程序、数据和进程控制块3部分
组成。
(4)进程与程序之间无一一对应关系。不同的进程可以包含同一个程序,同一个程序在
执行中也可以产生多个进程。
(5)进程是一个独立运行的单位,也是系统进行资源分配和调度的独立单位,而程序无此
概念。
3. 进程和线程的主要区别是什么?
[解答] 进程和线程的主要区别如下:
(1)线程是进程的一个组成部分。一个进程可以有多个线程,而且至少有一个可执行线
程。
(2)进程是资源分配的基本单位,它拥有自己的地址空间和各种资料。线程是处理机调
度的基本单位,它只能和其他线程共享进程的资源,而本身并不具有任何资源。
(3)进程的多个线程都在进程的地址空间内活动。这样,在以线程为单位进行独立机调
度和切换时,由于不发生资源变化特别是地址空间的变化,因此切换时间较短。而以进程为
单位进行处理机调度和切换时,由于涉及到资源转移及现场保护等问题,将导致切换时间变
长和资源利用率降低。
(4)线程和进程一样,都有自己的状态和相应的同步机制。但是,由于线程没有自己单
独的程序数据空间,因而不能像进程的程序和数据那样交换到外存去。
(5)进程的调度和控制大多由操作系统的内核完成,而线程的控制既可以由操作系统的
内核完成,也可以由用户控制完成。
4. 进程之间存在哪几种相互制约的关系?各是什么原因引起的?下列活动分别属于哪种
制约关系?
(1)
(2)
(3)
(4)
若干同学去图书借书;
两队举行篮球比赛;
流水线生产的各道工序;
商品生产和社会消费;
[解答] 进程之间的制约关系分为直接制约(即同步)和间接制约关系(即互斥)。同步是因
合作进程之间协调彼此的工作而控制自己的执行速度,即因相互合作、相互等待而产生的制
约关系;而互斥是进程之间竞争临界资源而禁止两个以上的进程同时进入临界区所发生的制
约关系。
(1) 属于互斥关系,因为一本书只能借给一个同学。
(2) 属于互斥关系,篮球只有一个,两队都要争夺。
(3) 属于同步关系,各道工序的开始都依赖前一道工序的完成。
(4) 属于同步关系,商品没有生产出来则消费无法进行,商品没有消费完则无须再
生产。
6. 进程基本状态变迁如图3-8所示。问:
(1) 在什么情况下将发生下述状态的因果变迁?
a .2 1 b. 3 2 c. 4 1 d.. 3 1
(2) 在什么情况下,下述状态变迁不会立即引起其他变迁?
a .1 b . 2 c. 3 d . 4
运行
1 2 3
等待
就绪
4
图 3-8 进程基本状态变迁图
[解答]
(1) 各种状态因果变迁发生的情况如下:
a. 正运行的进程因时间片到变为就绪状态的变迁2,必然引起一个就绪进程被调
度执行的变迁1。
b. 3 2不可能产生。
c. 当一进程从等待状态变为就绪状态的变迁4,在该进程的优先级最高且系统采
用抢占式调度时,就会引起该进程又被调度执行的变迁1。
d. 正在运行的进程因请求资源未得到满足而变为等待状态的变迁3,必然引起一
个就绪进程被调度执行的变迁1。
(2) 不引起其他变迁的情况如下:
a. 由就绪状态变为运行状态的变迁1不会引起其他变迁。
b. 变迁2必然引起变迁1。
c. 仅当无就绪进程时,变迁3不会引起变迁1。
非抢占式调度下或从等待状态变为就绪状态时的进程优先级较低,则不引起变迁1,
d. 非抢占式调度下或从等待状态变为就绪状态时的进程优先级较低,则不引起
变迁1,当然也不引起其他变迁。
7. 下述程序是解决两个进程互斥访问临界区问题的一种方法,试从“互斥”、“有空即进”、
“有限等待”3个方面讨论它的正确性,如果它是正确的,则证明之;如果它不正确,请说
明理由。
Program sample;
Var c1 ,c2 :integer ;
Procedure p1 ; /*第一个进程p1*/
Begin
Repeat
Other section 1;
Repeat
C1 :=1-c2
Until c2 <>0;
Critical section ;/*临界区*/
C1 :=1
Until false
End
Procedure p2 ;
Begin
Repeat
Other section 2;
Repeat
C2 :=1-c1
Until c1 <>0;
Critical section ;/*临界区*/
C2 :=1
Until false
End ;
Begin
C1 :=1;
C2 :=1;
Cobegin
P1 ;
P2 ;
Coend
End
[解答]
(1) 从“互斥”方面讨论。已知c1、c2的初值为1,假若进程p1执行到c1:=1-c2
时进程p2也同时执行c2:=1-c2。这样,c1和c2的值都变为0,接着再各自
循环执行到c1:=1-c2和c2:=1-c1时就变为1。此时进程p1和p2将同时进
入临界区,从而破坏了“互斥”条件。
(2) 从“有空即进”方面讨论。假定初始临界区为空,进程p1执行了c1:=1-c2,
由于c2的初值为1 ,这使得c1的值变为0,但c2值仍为1,这保证了进程
p1进入临界区。当进程p1的情况也类似。因此,该程序满足“有空即进”的
原则。
(3) 从“有限等待”方面讨论。由(2)可知,假定进程p1正在临界区执行,进程
p2申请进入临界区,则因进程p1会在有限时间内执行完临界区代码并退出临
界区,然后将执行c1:=1,这使得进程p2因c1的值变为1而立即即进入临
界区。因此,该程序满足“有限等待”的原则。
8. 产生死锁的必要条件是什么?解决死锁问题常用哪几种措施?
【解答】产生死锁的必要条件如下:
(1) 互斥条件:进程对所需要的资源进行排它性控制,即在一段时间内某资源为一
进程所独占。
(2) 请求和保持条件:进程因请求资源阻塞时,对已分配它的资源保持不放。
(3) 不剥夺条件:进程所获得的资源在未使用完之前,不能被其他进程强占,而只
能由该进程自己释放。
(4) 环路条件:在发生死锁时,进程――资源图必构成一环路,即前一个进程保持
着后一个进程所需要的资源。
解决死锁问题常用的措施有:
(1) 死锁的预防;
(2) 死锁的检测与解除。
9. 要使一个系统不发生死锁,一般可采用哪些方法?简述它们的实现原理。
【解答】要使一个系统不发生死锁,一般可采用如下方法:
(1) 死锁检测:当系统为进程分配资源时,若未彩任何限制性措施,则必须保存有
关资源的请求和分配信息,并采用某种算法根据这些信息来检测系统是否已进
入死锁状态。
(2) 死锁解除:当死锁出现常采用撤消某些进程或剥夺某些进程资源的方法来解除
死锁。
(3) 死锁避免:该方法把系统的状态分为安全和不安全两种,并保证系统始终处于
安全状态,从而避免死锁的发生。最有代表性的算法是Dijkstra的银行家算法。
(4) 死锁预防:通过破坏死锁的4个必要条件中的2~4条件之一来预防死锁的出现,
即:
① 破坏“请求和保持”条件;
② 破坏“不剥夺”条件;
③ 破坏“环路等待”条件。
10. Dijkstra 1965年提出的银行家算法其主要思想是什么?它能够用来解决实际中的死
锁问题吗?为什么?
【解答】银行家算法是解决死锁的一种策略,其主要思想是:在每次实施资源分配之前,先
进行试探分配,并对这种试探分配进行安全性计算,即查找这种试探分配中是否存在某种顺
序,按此顺序进行资源分配和使回收使全部进程都能够正常运行结束。如果存在这种顺序,
则正式实施这次资源分配,否则就拒绝此次资源分配。
银行家算法虽然具有很好的理论意义,但在实际系统中却难以实施,其原因一是难以事
先获得进程申请的最大资源数;二是在运行过程中进程的个数是不断变化的,原先预计将发
生死锁的情况,可能不会出现死锁。所以,银行家算法难以用来解决实际中的死锁问题。
四、解答题
1. 设有8个程序prog1,prog2,„„prog8,它们在并发系统中执行时有如图4-1所示的
制约关系,试用P,V操作实现这些程序间的同步。
Prog1
Prog3
Prog2
Prog5
Prog4
Prog6
Prog7
Prog8
图4-1 prog1~prog8执行关系图
【解答】本题是典型同步问题,即前一进程执行完后才可执行一进程。因此,只需在有后制
约关系的两进程间设置一信号量,当前一进程执行结束时执行V操作来通知后一进程可以
开始;而后一进程在开始进必须先执行P操作,在确定前一进程已执行结束时方可执行,否
则继续等待,即由此来保持同步关系。为编程方便起见,我们将图3-10改为如图3-11
所示的制约关系图,其中,结点代表进程,边代表制约关系,而边上的符号即为制约信号量。
Prog1 Prog2
Prog5
Prog3
Prog4
Prog7
Prog6
Prog8
由图3-11可得到prog1~prog8的同步关系如下:
begin
a1:=0; a2:=0; a3:=0;
b1:=0; b2:=0; b3:=0;
c:=0; d:=0; e:=0;
f:=0; g:=0;
cobegin
prog1:begin prog1;V(a1); V(a2); V(a3)end;
prog2:begin prog2;V(b1); V(b2); V(b3)end;
prog3:begin P(a1); P(b1); prog3;V(c)end;
prog4:begin P(a2); P(b2); prog4;V(d)end;
prog5:begin P(a3); P(b3); prog5;V(e)end;
prog6:begin P(c); prog6;V(f)end;
prog7:begin P(e); prog7;V(g)end;
prog8:begin P(f); P(g) P(d) prog8end;
coend end;
2. 两个可以并发执行的程序都分别包含输入、计算的打印3个程序段,即I1、C1、P1、
和I2、C2和P2。两程序的前趋关系如图3-12所示,试用P、V操作实现它们的同步关系。
I
1
I
2
C
1
C
2
图 3-12 两并发程序的前趋关系
P
1
P
2
【解答】 构造两程序的制约关系如图3-13所示,则两程序的同步关系如下:
I
1
I
2
C
1
C
2
P
2
图 3-13 两并发程序的制约关系图
Begin
A:=0; b:=0;
c:=0; d:=0; e:=0;
f:=0; g:=0;
I1: begin I1; V(a); V(c) end;
C1: begin P(a); C1; V(b); V(d)end;
P1: begin P(b); P1; V(e) end;
I2: begin P(c); I2; V(f) end;
C2: begin P(d); P(f); C2; V(g)end;
P2: begin P(e); P(g); P2 end
Coend
End;
3. 有3个并发进程R、M、P,它们共享同一缓冲区。进程R负责从输入设备读信息,
每读入一个记录后,就把它放进缓冲区中;进程M在缓冲区中加工读入的记录;进程P把加
P
1
工后的记录打印输出。读入的记录经加工输出后,缓冲区又可以存放下一个记录。试写出它
们能够正确执行的并发程序。
【解答】 这是一个简单的生产者――消费者问题。由于3个并发进程R、M和P共享一
个缓冲区,因此它们之前存在如图3-14所示的制约关系。
a
M
b
P
图3-14R、M和P的制约关系图
R、M和P的同步关系如下:
Begin
a:=0; b:=0; c:=0;
cobegin
R: begin
Repeat
P(c);
从输入设备读入一记录到缓冲区;
V(a);
4 until false
End;
M: begin
Repeat
P(a);
在缓冲区中加工读入的记录;
v(b);
until false
end;
p:begin
repeat
p(b);
打印加工后的记录;
v(c)
until false
end
coend
c
R
end;
注意:为了保证首先执行,所以信号量C的初植应设为“1”。此外,由制约关系图3-4可以看出来,
R,M和P不会竞争缓冲区资源,故无须设置用于互斥的公用信号量。
4. 设有进程A,B,C分别调用过程 Get, Copy, Put对缓冲区S和T进行操作。其中Get负责把数据
块输入缓冲区S,Copy负责从缓冲区S中提取数据块复制到缓冲区T中,PUT负责从缓冲区T中提
取信息打印,如图3-15所示。试描述Get, Copy,Put的操作过程。
Get 缓冲区S Copy 缓冲区T Put
图 3-15 三进程工作示意图
[解答] 由于本题缓冲区变成了两个,所以除了同步关系之外,进程A与进程B之间,进程B与进程
C之间还分别存在着互斥使用缓冲区S和缓冲区T这样的互斥关系,即两个缓冲区应视为临界资源。
但仔细分析可以发现:A与B不可能同时申请缓冲区S,因为缓冲区S为空时,只有进程A可以提出
申请使用;而缓冲区S满时,只有进程B可以提出申请并使用。由此得知,仅通过同步机制便可使进
程A 与进程B互斥地使用缓冲区S。进程B与进程C之间的关系也完全类同进程A 与进程B之间的
关系。三进程之间的制约关系如图3-16所示。特别注意,进程B对进程A来说是消费者,而对进程
C 来说有是生产者,进程B兼有消费者和生产者的功能,在编写程序时要特别注意,此外,为了在
初启时能保证三个进程按制约关系少年了执行,信号量empty1和empty2的初植应置为“1”。
A
full1
empty1
B
Full2
empty2
C
图3-16 三进程A,B,C之间制约关系图
三进程对应的并发程序如下:
begin
empty1:=1;empty2:=1;
full1:=0; full2:=0;
cobegin
a:begin
repeat
p(empty1);
将数据块输入缓冲区S;
v(full);
butyl false
end;
B:begin
Repeat
P(full1);
从缓冲区S中提取数据;
v(empty1);
p(empty2);
将数据复制到缓冲区T;
v(full2)
until false
end;
c:begin
repeat
p(full2);
从缓冲区T中取信息打印;
v(empty2)
until false
end
coend
end;
5. 进程A1,A2……..,An1通过m个缓冲区向进程B1,B2,….Bn2不断发送消息,发送
和接受工作遵循如下规则:
(1) 每个发送进程一次发送一个消息,写入一个缓冲区,缓冲区大小与消息长度一样;
(2) 对每一个消息,B1,B2,…….Bn2都需要各接受一次,读入各自的数据区内:
(3) m个缓冲区都满时,发送进程等待,没有可读的消息时,接受进程等待。
试用P、V操作组织正确的发送和接受操作。
【解答】
本题是生产者,消费者问题的一种变形,既对M个缓冲区中的人一个缓冲区,都要写一次和读
N2次,因此在出来中、一主要这样的两个方面:
(1)进程A I与进程Bj的同步控制;由于对每个消息B1~Bn2都需要各接受一次,所以应为
每个Bj(j=1,2,3,4…..n2)设置标志空缓冲区个数和满缓冲区个数的两个信号量empty[j]和
full[j].当Ai需要向缓冲区发送消息时首先判断信号量empty[1]~empty[n2]是否大于0,只
有在empty[1]~empty[2]都大于0的情况下,才表明有空缓冲区存在,当Ai把消息发送
到缓冲区后,还应使信号量full[1]~full[n2]每一个都增加1(既对B1~Bn2中的每一个进
程来说,需要读的消息都多了一个)。
(2)确定Bj待读出的消息缓冲区起始位置;对经典生产者-消费直到来说,由于对每个缓冲区
写,读只有一次,因此待读出的消息缓冲区起起始位置很容易缺点,即采用一个位置指针指示即
可。本题中,由于并发执行的B1~Bn2推进速度不一样,即读出消息的多少也不一样,所以对没
每个Bj(j=1,2…..n2)来说,还未读出的消息的个数是不一样的(即未读消息的起始位置不一样——。
那么,但Bj运行时如何确定其未读消息(缓冲区)的起始位置呢?由于full[j]和in来获得Bj戴
读消息缓冲区的起始位置out。由于采用环行缓冲区(如图3-17所示),所以这个起始位置out分
为full[j]值大于in值和full[j]值小于in值两种情况处理,(因判断full[j]值是在执行p(full[j])后进行
的,故full[j]值比实际装有消息的缓冲区个数少一)。与通常生产者-消费者问题不同,输出指针
out在输出消息后不用进行加1保存。
由于多个Ai 多个Bj 都可能同时访问缓冲区,因此缓冲区需当作临界资源互斥访问,即用斥
信号量mutex来进行控制。
in
……
m-1
0
2 1
B[j]的
out
图3-17 由进程B[j]看到的环行队列
本题的并发进程如下:
begin
mutex:=1;in:=0
for i:=1to n2 do
begin
begin
empty[i]:=m;
full[i]:=0
end;
cobegin
Ai(i=1,2…..n1):
Begin
Repeat
For i :=1 to n2 do
P(empty[i]);
P(mutex);
Buffer(in):=message i;
In:=(in+1)mod m;
For i:=1to n2 do
V(full[i]);
V(mutex)
Until falsee
End;
Bj(j=I,2……..,n2):
Begin
Repeat
P(full[j]);
P(mutex);
发布评论