操作系统习题 下载本文

5什么是死锁的安全序列?何谓系统是安全的?

答:进程的安全序列{P1,P2,?,PN}是这样组成的:若对于每个进程Pi(1<=I<=n),它需要的附加资源可以被系统中当前可用资源加上所有进程Pj(j

“系统是安全的”是指系统中的所有进程能够按照某种次序分配资源,并且依次运行完毕。即系统中的进程处于安全序列中。

6资源按序分配法为什么能够预防死锁?

证明:采用反证法来证明。 若存在循环等待,设在环路上的一组进程为{P0,P1,P2,?,Pn},这里Pi等待进程Pi+1占有资源Ri(下角标取模运算,从而,Pn等待p0占有的资源)。由于Pi+1占有资源Ri,又申请资源Ri+1,从而一定存在F(i)

F(R0)

显然,这是不可能的,因而,上述假设不成立,表明不会出现循环等待条件。

7死锁和“饥饿”之间的主要差别是什么?

答:死锁:多个并发进程相互等待对方占用的资源而产生的错误现象。

饿死:在系统中,由于系统采用的资源分配算法不当,虽然每个资源占有者都在有限时间内释放它所占的资源,但仍然使一些进程永远得不到资源的一种错误现象。

综合题

1设系统中有三种类型的资源(A,B,C)和五个进程(P1,P2,P3,P4,P5),A资源的数量为17,

B资源的数量为5,C资源的数量为20。在T0时刻系统状态如表3-9所试。系统采用银行家算法来避免死锁。

①T0时刻是否为安全状态?若试,请给出安全序列。 ②在T0时刻,若进程P2请求资源(0,3,4),能否实现资源分配?为什么? ③在②的基础上,若进程P4请求资源(2,0,1),能否实现资源分配?为什么? ④在③的基础上,若进程P1请求资源(0,2,0),能否实现资源分配?为什么? 表3-9 T0时刻系统状态 进程 最大资源需求量 已分配资源数量 系统剩余资源数量 A B C A B C A B C P1 5 5 9 2 1 2 2 3 3 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 解:

①T0时刻是安全状态,因为存在一个安全序列{P4,P5,P1,P2,P3} (2’) ②不能实现资源分配,因为所剩余的资源数量不够。 (2’)

③可以分配。当分配完成后,系统剩余的资源向量为(0,3,2),这时,仍可找到一个安全序列{P4,P5,P1,P2,P3} (3’)

④不能分配。如果分配的话,则系统剩余的资源向量为(0,1,2),这时无法找到一个安全序列。(3’)

2在银行家算法中,系统有5个进程和3个资源。若出现以下资源分配情况: 进程 资源最大请求 已分配资源 p0 7, 5, 3 0, 1, 0 p1 3, 2, 2 2, 1, 0 p2 9, 0, 2 3, 0, 2 p3 2, 2, 2 2, 1, 1 p4 4, 3, 3 0, 0, 2 系统剩余资源数量为(3,2,2)。

1) 该状态是否安全(给出详细的检查过程)? 2) 如果进程依次有如下资源请求 p1:资源请求Request(1,0,2)? p4:资源请求Request(3,3,0)? p0:资源请求Request(0,1,0)?

则系统如何进行资源分配,才能避免死锁? 解:

1)该系统状态是否安全,主要看能否找到一个进程完成序列.若能找到,系统只要按照这个序列为进程分配资源,所有进程就都可顺利完成;若找不到,系统状态就是不安全的.为此,可先求出进程的剩余请求矩阵. 进程 资源最大需求 已分配资源 剩余资源请求 P0 7, 5, 3 0, 1, 0 7, 4, 3 P1 3, 2, 2 2, 1, 0 1, 1, 2 P2 9, 0, 2 3, 0, 2 6, 0, 0 P3 2, 2, 2 2, 1, 1 0, 1, 1 P4 4, 3, 3 0, 0, 2 4, 3, 1 系统剩余资源向量A=(3,2,2),在进程剩余资源请求矩阵中找,是否有一行,其值都小于或等于A.若有,选进程P1,满足它的全部资源请求,它在有限时间内能释放全部资源,并标记它为完成使系统剩余资源向量A=(5,3,2).之后再重复上述过程,从而找到了一个进城完成序列为:P1,P3,P4,P2,P0 (2’)。由此可见,系统状态是安全的(2’)。

2)p1:资源请求Request(1,0,2)时,由1)可知,可以立即满足它,使得A=(2,2,0),P1的分配向量为(3,1,2),其剩余向量变为(0,1,0). (2’)

p4:资源请求Request(3,3,0)时,由于系统剩余资源向量A=(2,2,0),显然不能满足它的请求,因为系统剩余资源向量A小于P4的请求 (2’)

p0:资源请求Request(0,1,0)时,由于系统剩余资源向量A=(2,2,0),若满足它的请求,使得系统剩余资源向量A=(2,1,0)。之后,系统仍可以找到一个进程完成序列P1,P4,P0,P4,P2。故可以满足它的请求。 (2’)

3系统有同类资源10个,进程p1、p2和p3需要该类资源的最大数量分别为8,6,7。它们使用资源的次序和数量如下图所示。

1) 试给出采用银行家算法分配资源时,进行第5次分配后各进程的状态及各进程占用资源

情况。

2) 在以后的申请中,那次的申请可以得到最先满足?给出一个进程完成序列。

次序 进程 申请量 次序 进程 申请量 1 P1 3 5 P2 2 2 P2 2 6 P1 3 3 P3 4 7 P3 3 4 P1 2 8 P2 2 解:1)计算第5次分配后进程的状态和占用资源情况:(`5’=1’*5)

① p1申请3个,满足,系统还剩7个

②p2申请2个,满足(因为系统的7个可以使p2运行完),系统还剩5个

③p3申请4个,因为若满足它的请求,可能使以后的任何进程都不能运行完,故p3等待

④p1申请2个,满足(系统还剩5个可以满足p1的最大请求),系统还剩3个 ⑤ p2申请2个,不能满足,等待。此时系统的分配情况如下:

p1分配5个后正在运行,p2分配2个后等待分配2个,p3等待分配4个,系统还剩3个。

2)p1接着运行,p1申请3个可满足(2’)。P1运行完成后,释放资源,使系统的资源数量变为8个。首先将p3唤醒,满足它的4个资源,系统还剩4个,可以唤醒p2,满足它的2个请求。系统还剩2个。

P3申请3个,不能满足,等待。

P2申请2个,系统满足它,p2接着运行;p2完成,释放资源,使系统资源变为6个。系统唤醒p3,满足它的资源请求,最终p3完成,释放资源,使资源数量恢复为10个。 找到的进程完成序列为p1,p2,p3。 (3’)

4设系统中有150个可用的同类资源。在某时刻系统中的进程已获得的资源和最大请求资源如下所示,请用银行家算法分别判断完成下列请求时,系统是否安全?若安全,请给出进程的完成序列。如不安全,请说明原因。 进程 最大需求量 当前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0 (1) 进程p4当前请求25个资源; (2) 之后p4又提出35个资源的请求。

解答:系统当前剩余资源量为:150 – 25 – 40 – 45 = 40 (2’)

(1) 可以满足(2’),假定先分配p4的25个资源,系统还剩15个。将这15个资源可先分配

给p3,p3达到最大请求,释放60个;之后可以分配给其他任何进程,系统中的进程都能顺利完成。由此可见,p2请求的25个资源可以满足,且能找到完成序列:p3,p1,p2,p4,…(4’)

(2) 当p4再提出35个资源请求时,系统还剩15,显然不能满足它的请求,让其阻塞等待。

(2’)

5系统中有五个进程,分别为p1\\p2\\p3\\p4\\p5,四类资源分别为r1\\r2\\r3\\r4。某一时刻,系统剩余资源向量A=(1,2,3,0)。

(1) 用银行家算法试判断系统当前状态是否安全?

(2) 当进程p3提出对资源r3的剩余请求时,能否满足她? (3) 系统初始配置的各类资源分别为多少?

?1?1? MAX??2??0??0?1?0???1 NEED??0??0212?750??356? ,

?852?636???0?1??1??0??0012?000??144? .

?632?014??解答:系统剩余资源向量 A=(1, 2, 3, 0) 。现在需求出各进程的剩余资源请求矩阵:

200?750??212? (2’)

?220?622??(1) 详细步骤省略。由于系统存在一个进程完成的安全序列P1\\P3\\P4\\P2\\P5(2’),故系统状态

是安全的(2’)。

(2) 进程P3提出对资源R3的剩余请求为1,由于系统剩余资源向量A=(1,2, 3, 0),故可以

假定分配给它。如果能找到一个安全序列,就可以真正进行分配。当分配给P3一个资源时,系统剩余资源向量A=(1 ,2 ,2 , 0)。由此可见,仍然可以找到一个与(1)相同的安全序列。故可以满足P3的请求。(3’)

(3) 系统初始配置的各类资源分别为(3 ,9 , 12 , 12 )。(1’)

第四章—调度

名词解释

1作业

用户在一次上机过程中要求计算机系统所做工作的集合。

2周转时间

是指从作业进入系统开始,到作业退出系统所经历的时间。

3响应时间

是分时系统的一个技术指标,指从用户输入命令到系统对命令开始执行和显示所需要的时间。

4作业调度

作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。

5进程调度

也称低级调度程序,它完成进程从就绪状态到运行状态的转化。实际上,进程调度完成一台物理的cpu转变成多台虚拟(或逻辑)的cpu的工作。

6交换调度