第三章作业讲解
1、有5个作业进入就绪队列等待运行，预计它们的运行时间分别为 度顺序运行时会取得最小的响应时间？（答案与 X 值有关） 答：短作业优先调度算法是使响应时间最小的调度算法：
9 9
9 9 3、5、6、9、X
2、假设一个系统中有 4个进程，它们的到达时间和服务时间如表所示，忽略 分别按先来先服务（FCFS ）、非抢占及抢占的短进程优先（ SPF ）、高响应比优先（ （RR ，时间片=1 ）、多级反馈队列调度算法（FB ，第i 级队列的时间片=2i-1
）进行 进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。 3、若有4个周期性任务，任务 A 要求每30ms 执行一次，执行时间为 15ms ；任务
次，执行时间为5ms ；任务C 要求每50ms 执行一次，执行时间为15ms ；任务D 要求每100ms
执行一次, 执行时间为10ms ，应如何按最低松弛度优先算法对它们进行 CPU 调试？（要求画出0-150ms 时段的调 度
0 < X 时,调度顺序为： X 、 3、 5、 63 < X 时5调度顺序为： 3、 X 、 5、 6、 5 < X 时6调度顺序为： 3、 5、 X 、 6、 6 < X 时9调度顺序为： 3、 5、 6、
X 、
9、6、3、5与X ，它们以什么样的调 I/O 以及其他开销时间，若
HRRN ）、时间片轮转 CPU 调度，请给出各
B 要求每50ms 执行一
时，调度顺序为:
时序图，并列出每次切换时每个任务的松弛度）
0 10 1 1 20
30 1 1 40
50
1 1 60 70 80
1 1 1 90 100 110 120 130
1 1 1 1 1 140 150
1 |>
A1,B1 A2
A3
B3,C3
A5
A6,B4 ，丄」、
C1,D1
B2,C2 A4 D2
C4
到达时间 1
1 1
r
i 1 1 1
必须完成时间
t
A1
I A2 f A3 t
B2,C2 t
A4
t)
A5,B 答：对于上面的4个周期性任务，利用最低松弛度优先算法进行调度的情况如图所示:
B1,C1
D1
C3
15 30 35 50 65 80 90 95 110 125
松弛度
1
A1=15
B1=45 C1=35 D1=90
B1=30 C1=20 D1=75
A2=15 B1=15 D1=60
A2=10 D1=50
r
B2=45 C2=35 D1=10 B2=15
A4=10
A3=30
B 2=1
5
恣
任务执行
A1 ] C1 Fl A2
140 145 J
A5=10 B3=20 D2=65
D2=55 B3=5 D2=60
C2 j A3 A4 I C3 I A5
B3I D2 0
15
30 35
50
65
80
90 95
110
125
140 145
155
4、3个进程共享4个同类型的资源，每个进程最大需要 死锁？ 答：该系统不会因为竞争该类资源而死锁。因为，必有一个进程可获得 其所占用的2个资源给其他进程使用，使它们也顺利完成。
2个资源，请问该系统是否会因为竞争该资源而 2个资源故能顺利完成，并释放出
5、不安全状态是否必然导致系统进入死锁状态？举例说明。 答：不安全状态不一定导致进入死锁状态。因为，
安全性检查中使用的向量 Max 是进程执行前提供的，而
在实际运行过程中，一进程需要的最大资源量可能小于 Max ，如一进程对应的程序中有一段进行错误处理
的代码，其中需要 n 个A 种资源，若该进程在运行过程中没有碰到相应的错误，而不需要调用该段错误处 理代
码，则它实际上将完全不会请求这
n 个A 种资源。
6、在银行家算法中，若出现下面的资源分配情况:
试问：1) 2) 过程)？
3) 该状态是否安全(要求列出安全性算法检查表)？
若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它(要求根据分配算法列出检查 Available 15
2 2
如果系统立即满足 P2的上述请求，请问，系统是否立即进入死锁状态，请说明原因？
答：1)利用安全性算法对上面的状态进行分析，找到了一个安全序列 {P0、P3、P1、P2、P4},故系统是
2) P2发出请求向量 Request(1,2,2,2)后，系统按银行家算法进行检查： ① Request2(1,2,2,2)<=Need2(2,3,5,6) ② Request2(1,2,2,2)<=Available(1,5,2,2)
③ 系统先假定可为 P2分配资源，并修改 Available ，Allocation2 和Need2向量：
Available= ( 0，3，0，0) Allocati on 2=(2,5,7,6) Need2= ( 1，1，3，4)
④ 进行安全性检查：此时对所有的进程，条件Needi<=Available(0,3,0,0) 都不成立，即Available 不能满足任何进程的请求，故系统进入不安全状态。
此时当进程P2提出请求Request(1,2,2,2) 后，系统不能将资源分配给它。
3) 系统立即满足进程 P2的请求(1，2，2, 2)后，并没有马上进入死锁状态。因为，此时上述进程 并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致 所有没有执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。
7、进程资源的使用情况和可用情况如表所示，请画出资源分配图，并对资源图进行简化，这种情况下系 统会发生死锁吗
？
P3
'、、
P2
8要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目
而不是存在的资
源数）。 进程 当前分配数
最大分配数
R1 R1 P1
1 3 P2
1 2
/ /
? ? 4 R2
R3
? ?????
R1
??? ? ?
R2
?
R3
P2只有分配边，没有请求
边，所以首先可以将 P2所有
的边化简
P2释放资源后，P1与P4都可
以获得资源，运行结束。所 以选择P1化简
P4可以获得资源，运行结束。
所有结点都成为孤立结点，所以 图是可以完全化简的，不会发生 死锁
P4
R1
存在两种化简序列 1) P2-p1-p4-p3 ; 2) p2-p4-p1-p3
答：如果R1有一个资源可用，能
个可用，这将允许 P1执行完。P1释放它使用的资源后，
个R1类型的资源，如果 P3、P4请求分配最大数目的资源，
始就有3个R1类型资源，而
不是1个，P4就可以获得5个R1的可用资源并运行完。再加上 占用的2个R1资源，就可以让 P3运行。所以使该状态安全的所需可用资源的最小个数为 9、在时间片轮转法中，应如何确定时间片的大小？ 答：时间片长度可按如下方法确定：
1）系统对相应时间的要求；
2）就绪进程的数目：数目越多， 越小（当响应时间一定时）；3）系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使
响应时间，平均周转时间和平均带权周转时间延长； 10、在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法能使资源利用率最高？ 答：解决死锁问题可归纳为三种方法：预防死锁、避免死锁、检测死锁和解除死锁。其中预防死锁最容易 实现的；避免死锁使资源的利用率最高。 课本上习题
8在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？ 答：批处理系统可采用的进程调度算法有：高优先权优先调度算法、多级反馈队列调度算法、 分时系统可采用的进程调度算法有：基于时间片的轮转算法、抢占式优先权调度算法、多级反馈队列调度 算法
实时系统可采用的进程调度算法有：非抢占式优先权调度算法、抢占式优先权调度算法、最早截止时间优 先算法、最低松弛度优先算法（后两种都属于高优先权优先的实时调度算法） 5、在银行家算法中，若出现下面的资源分配情况:
试问：1）该状态是否安全？
2） 若进程P2提出请求Request （1,2,2,2）后，系统能否将资源分配给它？ 3） 如果系统立即满足 P2的上述请求，请问，系统是否立即进入死锁状态？ 答：1）利用安全性算法对上面的状态进行分析，找到了一个安全序列 {P 0、P 3、P 4、P 1、P 2},故系统是
安全的。
2）P2发出请求向量 Request （1,2,2,2）后，系统按银行家算法进行检查: ① Request2（1,2,2,2）＜=Need2（2,3,5,6） ② Request2(1,2,2,2)<=Available(1,6,2,2)
③ 系统先假定可为 P2分配资源，并修改 Available , Allocation2 和Need2向量：
Available 16 2 2
E 保证 P2运行完。然后P2释放它现在使用的资源，使得
R1类型的资源2 R1类型的资源数增加为
3个可用。只有 3
P3与P4就仍然处于死锁状态。如果一开
P4原来 3。
时间片
FCFS 、SJF
Available= (0, 4, 0, 0)
Allocati on 2=(2,5,7,6)
Need2= ( 1，1，3，4)
④进行安全性检查：此时对所有的进程，条件Needi<=Available(0,4,0,0) 都不成立，即Available 不能满
足任何进程的请求，故系统进入不安全状态。
此时当进程P2提出请求Request(1,2,2,2) 后，系统不能将资源分配给它。
3)系统立即满足进程P2的请求(1，2，2, 2)后，并没有马上进入死锁状态。因为，此时上述进程
并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没有执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。