A.9 B.10 C.11 D.12

8)在下列解决死锁的方法中，属于死锁预防策略的是：

A.银行家算法 B.资源有序分配法 C.死锁检测法 D.资源分配图化简法 9)资源的按序分配策略可以破坏（）条件。

A.互斥使用资源 B.占有且等待资源 C.非抢占资源 D.循环等待资源 10)进程的调度方式有两种，一种是（），另一种是（）

11)在（）调度算法中，按照进程进入就绪队列的先后次序来分配处理机。 12)死锁产生的必要条件有四个，即（）、（）、（）、（）。

13)银行家算法中，当一个进程提出的资源请求将导致系统从（）进入（）时，系统就拒绝它的资源请求。 14)对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于（），破坏环路等待条件是属于（），而剥夺资源是（）的基本方法。

15)某分时系统中的进程可能出现如下图所示的状态变化，回答下列问题： （1）根据图示，该系统采用的是什么进程调度策略？ （2）指出图示中的每一个状态变化的原因。

16) n个进程共享某种资源Ｒ，该资源共有m个可分配单位，每个进程一次一个的申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m+n，试证明在这个系统中不可能发生死锁。

设max(i)表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：

max(1)+?+ max(n)=(need(1)+?+need(n))+(alloc(1)+?+alloc(n))

另一方面所有进程将陷入无限等待状态。 由上述两式可得：need(1)+?+need(n)

上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，need(i)=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。

17) 有一个内存中只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。有如下表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高.列出所有作业进入内存的时刻以及结束的时刻。计算作业的平均周转时间。

10：00 A到达，无竞争，开始运行；

10：20 B到达，进入主存，优先数为3，优于A,B开始运行 10：30 C到达，不可进入；

10：50 B结束，同时D到达，同C争夺内存，D运行时间短，被调度进入内存；A的优先数高，开始运行；

第9页 共22页

11：10 A结束，C进入内存，C的优先数高于D,开始运行； 12：00 C结束, D开始运行；

12：20 D结束。平均周转时间=280/4=70分钟 18) 在银行家算法中，若出现下述资源分配情：

试问：⑴ 该状态是否安全？⑵ 若进程P2提出请求Request(1，2，2，2)后，系统能否将资源分配给它？

⑴该状态是安全的，因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。

⑵若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。

19）某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2

和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：(南京大学1999年试题) J1: IO2(30ms), CPU(10ms), IO1(30ms), CPU(10ms). J2: IO1(20ms), CPU(20ms), IO2(40ms). J3: CPU(30ms), IO1(20ms).

处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题： （1）分别计算作业J1、J2和J3从开始到完成所用的时间。 （2）3个作业全部完成时CPU的利用率。 （3）3个作业全部完成时外设I01的利用率。

20)

假设有4道作业，它们的提交时刻及执行时间由下表给出：计算在单道程序环境下，采用先来先服

先来先服务：1，2，3，4

务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序

第10页 共22页

平均周转时间： （2+2.8+3.1+3.3)/4=2.8 平均带权周转时间：(1+2.8/1+31/5+11)/4=5.25

最短作业优先： 1，4，3，2平均周转时间（2+1.8+2.4+3.6)/4=2.45 平均带权周转时间（2+9/5+12/5+18/5)/4=3.85 最高响应比算法：1，4，3，2 R=1+W/T t1=2 执行1

t2=1 w2=12-10.2=1.8 r2=1+1.8/1=2.8 t3=0.5 w3=12-10.4=1.6 r3=1+1.6/0.5=4.2 t4=0.3 w4=12-10.5=1.5 r4=1+1.5/0.3=6 执行4 w2=1.8+0.3=2.1 r2=1+2.1/1=2.1

w3=1.6+0.3=1.9 r3=1+1.9/0.5=4.8 执行3，2 平均周转时间同最短作业优先法。 21)

设有P1、P2、P3、P4共4个进程同时依次进入就绪队列中，它们需要的处理器时间和优先级别如下

所示：忽略调度所花费的时间，请回答下列问题：(1)写出分别采用“先来先服务”和“非抢占式的优先数”调度算法选中的进程执行的次序。(2)在上述两种算法下，分别算出每个进程在就绪队列的等待时间和平均等待时间。

(1)用先来先服务的调度算法时，4个进程的调度次序是P1、

P2、P3、P4。

用非抢占式的优先数调度算法时，4个进程的调度次序是P2、P4、P1、P3。

(2)用先来先服务调度算法，每个进程在就绪队列中的等待时间分别为： P1：0秒 P2：0+20=20秒 P3：0+20+30=50秒 P4：0+20+30+10=60秒

平均等待时间为：(0+20+50+60)／4=32.5秒

用非抢占式的优先数调度算法，每个进程在就绪队列中的等待时间分别为； P1：30+5=35秒 P2：0秒

P3：20+30+5=55秒 P4：30秒

平均等待时间为：(35+0+55+30)／4=30秒 22)

在单处理器环境下，有4道作业，其进入系统的时间和所需要的执行时间如下所示试分别用“先来

（1）先来先服务调度算法

平均周转时间：（1.5+1.7+1.4+1.4）/4=1.5 （2）非抢占式的优先数调度算法

平均周转时间：（1.5+2.3+O.7+0.7）/4=1.3

先服务”和“非抢占式的优先数”调度算法，求出每个作业的周转时间和平均周转时间

23）某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情

第11页 共22页

况见表2.2，此刻系统的可用资源向量为（2, 1, 2），

①将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；②如果此时P1和P2均发出资源请求向量Request(1, 0, 1)，为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因；③如果②中两个请求立刻得到满足后，系统此刻是否处于死锁状态？

①系统资源总数向量为（9, 3, 6）各进程对资源需求矩阵为：

②采用银行家算法进行计算分析可知：系统可以满足P2进程对资源的请求，将资源分配给P2之后，至少可以

找到一个安全的执行序列，如（P2, P1, P3, P4）使各

进程正常运行终结。系统不可以将资源分配给进程P1，虽然可利用资源还可以满足进程P1现在的需求，但是一旦分配给进程P1后，就找不到一个安全执行的序列保证各进程能够正常运行终结。所以进程P1应该进入阻塞状态。③系统满足进程P1和P2的请求后，并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态。

第四章

28. 分区存储管理中常采用的分配策略有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法。

a.首次适应算法的优缺点：保留了高址部分的大空闲区，有利于后到来的大型作业的分配；低址部分不断被划分，留下许多难以利用的、小的空闲区，且每次分区分配查找时都是从低址部分开始，会增加查找时的系统开销。

b.循环首次适应算法的优缺点：使内存中的空闲分区分布得更为均匀，减少了查找时的系统开销；缺乏大的空闲分区，从而导致不能装入大型作业。

c.最佳适应算法的优缺点：每次分配给文件的都是最适合该文件大小的分区；内存中留下许多难以利用的小的空闲区。

d.最坏适应算法的优缺点：给文件分配分区后剩下的的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利；使存储器中缺乏大的空闲区，对大型文件的分区分配不利。

例 1）某采用页式管理的系统，把主存分成大小为128的相等长度的块。有一个用户要把一个128×128

的数组置成初值“0”，在分页时把数组中的每一行放在一页中。假定分给用户可用来存放数组信息的工作

第12页 共22页