复习

先来先服务(first-come first-served，FCFS)调度算法 当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 短作业优先(short job first，SJF)的调度算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

14. (其它, 7.8分)设有4道作业，它们的提交时间及执行时间如下：试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）

我的答案：
正确答案：
（1）若采用先来先服务调度算法，则其调度顺序为1、2、3、4。

平均周转时间 T=(2.0＋2.8＋3.1＋3.3)/4=2.8
平均带权周转时间 W=(1＋2.8＋6.2＋11)/4=5.25
（2）若采用短作业优先调度算法，则其调度顺序为1、4、3、2。

平均周转时间 T=(2.0＋1.8＋2.4＋3.6)/4=2.45
平均带权周转时间 W=(1＋6＋4.8＋3.6)/4=3.85

:::tips :::

(1) 可利用资源向量Available。 这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个　 (2) 最大需求矩阵Max。 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。 (3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Need［i,j］=Max［i,j］-Allocation［i,j］

设Requesti是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果Request i[j]≤Need[i, j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j] = Available[j] - Request i[j]; Allocation[i, j] = Allocation[i, j] + Request i[j]; Need[i, j] = Need[i, j] - Request i[j]; (4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3. (简答题, 33.4分)系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：A、B、和C。在T0时刻系统状态如下表所示。若采用银行家算法实施死锁避免策略，回答下列问题： （1）T0时刻是否为安全状态？为什么？（2）若这时P3请求资源（3，0，0），是否能实施资源分配？为什么？

|

|

| | P3 | 0 | 0 | 3 | 7 | 0 | 5 |

|

|

| | P4 | 1 | 1 | 5 | 4 | 3 | 5 |

|

|

| | P5 | 1 | 1 | 0 | 6 | 1 | 3 |

|

|

|

我的答案：

正确答案：
解：（1）安全，可以找到一个安全序列P4，P1，P5，P2，P3

（2）
Request（3 0 0）所以预分配，系统状态为

| | P3 | 303 | 705 | 302 |

| | P4 | 115 | 435 | 320 |

| | P5 | 110 | 613 | 503 |

|

此时找不到安全序列，故不能满足P3要求。

1. 两种形式的制约关系 1) 间接相互制约关系 2) 直接相互制约关系

:::tips

15. (其它, 7.6分)解答题.docx

我的答案：
P1{ S1; signal(a); signal(b); }
P2{ wait(a); S2; signal(c); }
P3{ wait(b); S3; signal(d); }
P4{ wait(c); wait(d); S4; }
Main()
{
Semaphore a,b,c,d =0,0,0,0,0,0,0;
cobegin
P1(); P2(); P3(); P4();
coend
}
正确答案：
P1{ S1; signal(a); signal(b); }
P2{ wait(a); S2; signal(c); }
P3{ wait(b); S3; signal(d); }
P4{ wait(c); wait(d); S4; }

Main()
{
Semaphore a,b,c,d =0,0,0,0,0,0,0;
cobegin
P1(); P2(); P3(); P4();
coend
} :::

:::tips

P1{S1; signal(s12); signal(s13); }
P2{wait(s12); S2; signal(s24); signal(s25); }
P3{wait(s13); S3; signal(s36); }
P4{wait(s24); S4; signal(s46); }
P5{wait(s25); S5; signal(s56); }
P6{ wait(s36); wait(s46); wait(s56); S6; }
Main()
{
Semaphore s12,s13,s24,s25,s36,s46,s56=0,0,0,0,0,0,0;
cobegin
P1(); P2(); P3(); P4(); P5(); P6();
coend
} :::

:::tips

9. (其它, 11.2分)在一分页存储管理系统中，逻辑地址长度为16位，页面大小为2048字节，现有一逻辑地址为1B6AH ，且第0、1、3页依次存放在物理块6、8、10中，问相应的物理地址为多少？

我的答案：
536AH

正确答案：
:::

8. (填空题, 11.1分)
在一个请求分页系统中，假如系统分配给某一作业的物理块数为3，且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2 。OTP算法的缺页次数为 ，LRU算法的缺页次数为 。

我的答案：

正确答案：
(1) 3
(2) 4

先来先服务(FCFS) 这是最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度 最短寻道时间优先(SSTF) 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短 扫描(SCAN)算法 扫描(SCAN)算法不仅考虑到要访问的磁道与当前磁道间的距离，更优先考虑当前磁头的移动方向。 循环扫描(CSCAN)算法 循环扫描(CSCAN)算法规定磁头单向移动