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

周转时间 3 7 9 12 12 8.6 带权周转时

间 1.00 1.17 2.25 2.40 6.00 2.56

SPF(非抢占) 完成时间 3 9 15 20 11 周转时间 3 7 11 14 3 7.6 带权周转时

间 1.00 1.17 1.75 2.80 1.50 1.84

SPF(抢占) 完成时间 3 15 8 20 10 周转时间 3 13 4 14 2 7.2 带权周转时

间 1.00 2.16 1.00 2.80 1.00 1.59

200377. 一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。问：（1）有效的逻辑地址由多少位？（2）有效的物理地址由多少位？

此题答案为：答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64＝26，则： （1）逻辑地址有16位。 （2）物理地址有15位。

说明：解此题的关键是要知道在分页管理中，\页\和\块\是一样大小的，这样才知道物理存储器是32KB。

200380. 在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。

6

（1）CPU的利用率为15%，磁盘利用率为95%。 （2）CPU的利用率为88%，磁盘利用率为3%。 （3）CPU的利用率为13%，磁盘利用率为5%。

此题答案为：答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下： （1）可能已出现了抖动现象，应减少系统的进程数。

（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。 （3）CPU和磁盘的利用率都较低，必须增加并发进程数。 200381. 对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO和LRU替换算法的缺页次数。结果说明了什么？

此题答案为：答：首先采用FIFO，当m=3时，缺页次数＝9，当m=4时，缺页次数＝10。

采用LRU算法，当m=3时，缺页次数＝10；当m=4时，缺页次数＝8。

结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。 200389. 一个分页存储器的页表存放在内存。

（1）若内存的存取周期为0.6ms，则CPU从内存取一条指令（或一个操作数）需多少时间？

7

（2）若使用快表且快表的命中率为75%，则内存的平均存取周期为多少？

此题答案为：答：一个分页存储器的页表存放在内存

（1）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需0.6ms×2=1.2ms的时间。

（2）这里家假设访问快表的时间忽略不计，命中快表时，取数只要一次访问，故此时的平均存取周期为0.6ms×0.75+1.2ms×(1-0.75)=0.75ms

200392. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。 此题答案为：

当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。 当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。 可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。

200394. 对于一个使用快表的页式虚存，设快表的命中率为70%，内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns，问可接受的最大缺页率是多少？

8

此题答案为：答：设可接受的最大缺页率位p，则有 1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns 即 0.7+0.6-2p+3200p+12000p=2 15198p=0.7 P=0.000046

200396. 在分页存储管理系统中，存取一次内存的时间是8ns，查询一次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现在开始执行一作业，系统连续对作业的2，4，5，2，7，6，4，8页面的数据进行一次存取，如分别采用FIFO算法和最优页面置换算法，求每种上存取这些数据需要的总时间。 此题答案为：答： （1）FIFO

第2页面：20＋8×3 第4页面：20＋8×3 第5页面：20＋8×3 第2页面：8＋1 第7页面：20＋8×3 第6页面：20＋8×3 第4页面：20＋8×3 第8页面：20＋8×3

9

因此总的时间是（20＋8×3）×7＋（8＋1）ns (2) OPT

第2页面：20＋8×3 第4页面：20＋8×3 第5页面：20＋8×3 第2页面：8＋1 第7页面：20＋8×3 第6页面：20＋8×3 第4页面：8＋1 第8页面：8＋1

因此总的时间是（20＋8×3）×5＋（8＋1）×3ns

200532. 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。 此题答案为：

当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。 当M=4时，缺页次数为4次，缺页率为4/12=0.33=33%。 可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。

200592. 在一个请求分页系统中，采用OPT页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当

10