操作系统经典算法题汇总-分章节概要.ppt

操作系统计算题汇总 2013.12 内容 进程管理涉及到计算题 内存管理涉及到计算题 外设管理涉及到计算题 文件系统涉及到计算题 类似问题： 三、磁盘访问时间： 1.寻道时间：TS=m*n+s m：常量，n：磁道数，s：磁盘启动时间。 2.旋转延时间Tr（平均旋转延迟时间）： 指定扇区旋转到磁头下所需时间。 设每秒r转，则T r ＝1/(2r)（均值） 3.数据传输时间:Tt＝b/(rN) b：每次读/写字节数 N：每道上的字节数 访问时间：Ta=Ts+1/(2r)+b/(rN) 可见，由于特定磁盘，只有集中放数据，集中读写（b的值大）才能更好提高传输效率。 寻道时间: 20ms，磁盘通道传输速率: 1MB/s，转速r=3600rpm，每扇区512字节，每磁道32 扇区。目标：读 128k 数据，问：访问时间为多少？ 对于一个使用快表的页式虚存，设快表的命中率为70%，内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns，问可接受的最大缺页率是多少？ 答：设可接受的最大缺页率位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 在分页存储管理系统中，存取一次内存的时间是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 ?? 因此总的时间是（20＋8×3）×7＋（8＋1）ns (2)最优页面置换 ???????? 第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 在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。 （1）CPU的利用率为15%，磁盘利用率为95%。 （2）CPU的利用率为88%，磁盘利用率为3%。 （3）CPU的利用率为13%，磁盘利用率为5%。 答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下： （1）可能已出现了抖动现象，应减少系统的进程数。 （2）系统比较正常，可考虑适当增加进程数以提高资源利用率。 （3）CPU和磁盘的利用率都较低，必须增加并发进程数。 考虑一个有快表的请求分页系统，设内存的读写周期为1ns，内外存之间传送一个页面的平均时间为5000ns，快表的命中率为80%，页面失效率为10%，求内存的有效存取时间。 答：内存的有效存取时间EAT(Efficent Access Time)也叫平均存取时间AAT(Average Access Time)，其计算公式如下： EAT＝1ns×80%+2ns×10%+(5000ns+2ns) ×10% =0.8ns+0.2ns+500.2ns=501.2ns 一台计算机有一个Cache、内存储器和用作虚拟存储器的磁盘，假设访问Cache中的字需要20ns的定位时间；如果该字在内存储器中而不在Cache中，则需要60ns的时间载入Cache，然后在重新开始定位；如果该字不在内存储器中，则需要12ms的时间从磁盘中提取，然后需要60ns复制到Cache中，然后在定位。Cahce的命中率为0.9，内存储器的命中率为0.6，在该系统中访问一个被定位的字需要的平均时间是多少ns？ （三）、外设管理计算 因为：60*16kB=960kB/s1MB/s 顺