计算机操作系统算法题（最全）(7)

考虑其他不同调度算法，设在此调度算法下的作业调度次序为ji1,ji2,...jin,其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，则类似上面可以得出：

T1=((n*ti1+(n-1)*ti2+...+tin)/n)

根据不等式结论：如果有a1<=a2<=...<=an 且b1<=b2<=...<=bn，则

a1bn+a2bn-1+...+anb1<=a1bi1+a2bi2+...+anbn<=a1b1+a2b2+...+anbn

其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，不难得出T<=T1。 200602. 采用银行家算法防止死锁，用Pi→n表示Pi 进程申请n个资源，用Pi←n表示Pi 进程占有n个资源。如果占有n个资源的进程被阻塞，可以用Pi*←n 来表示，假设系统中有某类资源10个，进程P1, P2, P3各自的最大需求量为3,7,10个,各进程T0时刻开始运行:

T1时刻发生: P1→2, P2→3, P3→3 T2时刻发生: P2→1, P3→2 T3时刻发生: P1→1, P2→1

根据银行家算法,填写三个时刻的进行占有和阻塞情况. 此题答案为：解：

进程 T0 T1 T2 T3 P1 P1←0 P1←2 P1←2 P1←3 P2 P2←0 P2←3 P2←4 P2*←4

26

P3 P3←0 P3←3 P3*←3 P3*←3

200604. 有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。

(1)试说明A、B两进程之间存在什么样的制约关系？

答：A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用

(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。

此题答案为：答：mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1

进程A 进程B ... ...

P(mutex)； P(mutex)； 申请打印机； 申请打印机； 使用打印机； 使用打印机； V(mutex)； V(mutex)；

200605. 设 input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：

27

（1）这两个进程有何相互制约关系？ 答：这两个进程的相互制约关系为同步关系；

（2）试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。

此题答案为：答：设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q中是否有信息，初值为0，表示Q中无信息。 两进程的代码段如下：

input进程 output进程 …… ……

While 信息未处理完毕 While 信息未处理完毕 { 加工一个信息； { P（S2）； P（S1）； 从Q中读出一个信息； 将信息放入Q中； V（S1）；} V（S2）；} ……

200606. 假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：

作业 进入系统时间 估计运行时间/分钟 1 8:00 40 2 8:20 30 3 8:30 12

28

4 9:00 18 5 9:10 5

此题答案为：(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。

作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟

1 8:00 40 8：00 8：40 40 2 8:20 30 8：40 9：10 50 3 8:30 12 9：10 9：22 52 4 9:00 18 9：22 9：40 40 5 9:10 5 9：40 9：45 35 作业平均周转时间T= 43.4 217

（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。

作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟

1 8:00 40 8：00 8：40 40 2 8:20 30 8：52 9：22 62 3 8:30 12 8：40 8：52 22 4 9:00 18 9：27 9：45 45 5 9:10 5 9：22 9：27 17 作业平均周转时间T= 37.2 186

29

200607. 在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问：

（1）逻辑地址084B（H）对应的物理地址是多少？（用十六进制表示）

（2）逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示）

（3）当该用户进程欲访问24A0H单元时，会出现什么现象？ 页号 块号 0 3 1 7 2 4 3 1 4 12 5 9 6 61 7 20

此题答案为： (1)答：104B(H) (2)答：13192

(3)答： 24A0（H）的页号为9，而其页面当前不在内存，所以会发一个缺页中断，请求系统调页。

30