《计算机操作系统算法题(最全)》由会员分享，可在线阅读，更多相关《计算机操作系统算法题(最全)（39页珍藏版）》请在金锄头文库上搜索。
1、6. 算法题(共 32个题目)200348.在信号量机制中，若P (S)操作是可中断的，则会有什么 问题？此题答案为：答：P (S)的操作如下：BeginS.Value:= S.Value-1; If S.Value0 S的值表示可继续进入售票厅的人数；S=0 表示售票厅中已有20名购票者；S0 |S|的值为等待进入售票厅中的人数。（2）上框为P（S），下框为V（S）。（3）S的最大值为20, S的最小值为20-N, N为某一时刻需要进 入售票厅的最多人数。200362. 在批处理系统、分时系统和实时系统中，各采用哪几个进 程（作业）调度算法？ 此题答案为：答：（1）批处理系统中的作业调度算法
2、有：先来先服 务算法（FCFS）、短作业优先算法（SJF）、优先级调度算法（HPF） 和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进 先出算法（FIFO）、短进程优先算法（SPF）、优先级调度算法（HPF） 和高响应比优先算法（RF）。（2）分时系统中只设有进程调度（不设作业调度），其进程调度算 法只有轮转法（RR） 一种。（3）实时系统中只设有进程（不设作业调度），其进程调度算法调 度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求严格的实时系统。后者又可细分为：非抢占 式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调 度。注意，一个
3、纯粹的实时系统是针对特定应用领域设计的专用系统。作 业提交的数量不会超过系统规定的多道程序的道数，因而可全部进入 内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多 道程序道数，使优先级低的作业呆在外存的后备队列上。200372. 假设系统中有5 个进程，它们的到达时间和服务时间见下表1忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非 抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度, 请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。表 1 进程到达和需要服务时间进程 到达时间 服务时间A03B26C44D65表2 进
4、程的完成时间和周转时间E82此题答案为：进程 A B C D E 平均FCFS完成时间 39131820周转时间37912 128.6带权周转时间1.001.172.252.406.002.56SPF（非抢占）完成时间3915 2011周转时间37111437.6带权周转时间1.001.171.752.801.501.84SPF（抢占）完成时间3158 2010周转时间31341427.2带权周转时间1.002.161.002.801.001.59200377. 一个逻辑空间最多可有64 个页，每页 1KB 字节。若把它映 射到由 32 个物理块组成的存储器。问：（1）有效的逻辑地址由多 少位
5、？（2）有效的物理地址由多少位？此题答案为：答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64=26，贝U：（1 ）逻辑地址有 16 位。（2）物理地址有 15 位。说明：解此题的关键是要知道在分页管理中， 页和块是一样大小 的，这样才知道物理存储器是 32KB。200380.在某分页系统中，测得CPU和磁盘的利用率如下，试指出 每种情况下的问题和措施。（1）CPU 的利用率为 15%，磁盘利用率为95%。（2）CPU 的利用率为 88%，磁盘利用率为3%。（3）CPU 的利用率为 13%，磁盘利用率为5%。此题答案为：答：在某分页虚存系统中，在题中的CP
6、U和磁盘的利 用率的情况下，出现的问题和应采取的措施如下：（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
7、有Belady奇异现象，即不满足驻留集增大，缺页次 数一定减小的规律;另外在m=3时，LRU的缺页次数比FIFO要多， 所以LRU算法并不总优于FIFO，还要看当前访问串的特点。 200389. 一个分页存储器的页表存放在内存。（1）若内存的存取周期为0.6ms，则CPU从内存取一条指令（或一 个操作数）需多少时间？（2）若使用快表且快表的命中率为75%，则内存的平均存取周期为 多少？此题答案为：答：一个分页存储器的页表存放在内存 （1）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需0.6msx2=1.2ms的时间。（2）这里家假设访问快表的时间忽略不计，命中快表时，取数
8、只 要一次访问，故此时的平均存取周期为0.6msx0.75+1.2msx（1-0.75）=0.75ms200392.在一个请求分页系统中，采用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. 对于一个使用快表的页式
9、虚存，设快表的命中率为 70%， 内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的 页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需 20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效 存取时间不超过2 n s ，问可接受的最大缺页率是多少？此题答案为：答：设可接受的最大缺页率位p,则有1nsx0.7+2nsx(1-0.7-p)+0.4px8000ns+0.6px20000ns=2ns即 0.7+0.6-2p+3200p+12000p=215198p=0.7P=0.000046200396.在分页存储管理系统中，存取一次内存的时间是8ns,查询 一
10、次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询 与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没 有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留 3个页面在内存。现在开始执行一作业，系统连续对作业的 2， 4， 5， 2, 7, 6, 4, 8页面的数据进行一次存取，如分别采用FIFO算法和 最优页面置换算法，求每种上存取这些数据需要的总时间。 此题答案为：答：(1 )FIFO第2页面：20+8x3第4页面：20+8x3第 5 页面： 20+8x3第 2 页面： 8+1第 7 页面： 20+8x3第 6 页面： 20+8x3第 4 页面： 20+8x3
11、第 8 页面： 20+8x3因此总的时间是(20+8x3) x7+(8+1) ns(2) OPT第2页面：20+8x3第 4 页面： 20+8x3第 5 页面： 20+8x3第 2 页面： 8+1第 7 页面： 20+8x3第 6 页面： 20+8x3第 4 页面： 8+1第 8 页面： 8+1因此总的时间是(20+8x3) x5+(8+1) x3ns200532. 在一个请求分页系统中，采用 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
