操作系统计算题

1、操作系统计算题w=2148 mod 1024=100查页表第2 页在第 1 块，所以物理地址为1124。对于逻辑地址 3000p=int(3000/1024)=2w=3000 mod 1024=928查页表第 2 页在第 1 块, 所以物理地址为1796。对于逻辑地址 4000p=int(4000/1024)=3w=4000mod 1024=928查页表第3 页在第6 块, 所以物理地址为7072。对于逻辑地址 5012p=int(5012/1024)=4w=5012mod1024=916因页号超过页表长度，该逻辑地址非法。例 2：在一分页存储管理系统中 ,逻辑地址长度为 16 位,页面大小为

2、 4096 字节,现有一逻辑地址为 2F6AH, 且第 0, 1, 2页依次存放在物理块 5, 10 ,11中,问相应的物理地址为多少 ?解:由题目所给给条件可知 ,本页式系统的逻辑地址结构为 :逻辑地址 2F6AH 的二进制表示如下 :由此可知逻辑地址 2F6AH 的页号为 2,该页存放在第 11 号物理块中 ,用十六进制表示志号为 B, 所以物理地址为 BF6AH. 一、 求文件最大长度例：设文件索引节点中有 7 个地址项，其中 4 个地址项为直接地址索引， 2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4 字节，若磁盘索引块和盘块大小均为256 字节，

3、则可表示的单个文件的最大长度是多少？解答：本题的文件结构属混合索引分配方式。每个地址项大小为 4 字节，索引块和盘块大小为 256 字节，每个索引块中的项目数=256B/4B=64 个。4 个地址项为直接地址索引，对应的文件大小为 4×256B=1KB。2 个地址项是一级间接地址索引，对应的文件大小是2×64×256B=32KB，一个地址项是二级间接地址索引，对应的文件大小为 1×64× 64×256B=1024KB。所以单个文件的最大长度=1KB+32KB+1024KB=1057KB 。二、 磁盘调度算法：1.先来先服务 FCFS2

4、.最短寻道时间优先SSTF3.SCAN 算法4.循环扫描(CSCAN)算法例：假设一个活动头磁盘有 200 道, 编号从 0-199. 当前磁头正在 143 道上服务 , 并且刚刚完成了 125 道的请求 . 现有如下访盘请求序列(磁道号 ):86, 147, 91, 177, 94, 150, 102, 175,130试给出采用下列算法后磁头移动的顺序和移动总量 (总磁道数 ).(1). 先来先服务 (FCFS) 磁盘调度算法 .(2). 最短寻道时间优先(SSTF) 磁盘调度算法 .(3). 扫描法 (SCAN) 磁盘调度算法 .(假设沿磁头移动方向不再有访问请求时 , 磁头沿相反方向移动

5、 .)答案：三、（1）86，147，91，177，94，150，102，175，130（2）当前磁头在 143 道上：147，150，130，102，94，91，86，175，177（ 3）当前磁头在 143 道上，并且刚刚完成 125 道的请求147，150，175，177，130，102，94，91，86三、 调度算法（求周转时间，加权周转时间）1先来先服务调度算法FCFS：该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配给它，使之投入运行。例2优先级调度算法：总是选择具有 最高优先级的进程首先使用处理机。在这种算法中，首先考虑的问题是如何确定进程的优先数。 分为

6、：静态优先权：在创建进程的时候便确定的，且在进程的运行期间保持不变。 （简单 易行，系统开销小，但不够精确， 很可能出现优先权低的作业（进程）长期不被调 度的情况。所以，只在要求不太高的系统中， 才使用静态优先数（权）动态优先权：在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能例：3.最短作业 /进程优先法（ SJF/SPF）：SJF:从后备队列中选择估计运行时间最短的作业，先调入内存运行。SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。4.最高响应比作业优先算法（ HRN ）：是对 FCFS 方式和 SJF 方式的一种综合平衡响应比

7、。 R(作业等待时间需运行时间 )/ 需运行时间 1已等待时间 / 需运行时间 1W/T例：六：页面置换算法先进先出页面淘汰算法（FIFO ）选择在内存中驻留时间最长的页并淘汰之理想淘汰算法 最佳页面算法（ OPT ）淘汰以后不再需要的或最远的将来才会用到的页面最近最久未使用页面淘汰算法（ LRU ）选择最后一次访问时间距离当前时间最长的一页并淘汰之即淘汰没有使用的时间最长的页1 已知页面走向为1、2、1、3、1、2、4、2、1、 3、4，且开始执行时主存中没有页面。若只给该作业分配 2 个物理块，当采用 FIFO 页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰页面的策略为当需要

8、淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，缺页率又为多少？分析及相关知识 在进行内存访问时，若所访问的页已在主存， 则称此次访问成功； 若所访问的页不在主存， 则称此次访问失败， 并产生缺页中断。若程序 P 在运行过程中访问页面的总次数为 S,其中产生缺页中断的访问次数为 F,则其缺页率为： F/s.解：根据所给页面走向，采用 FIFO 淘汰算法的页面置换情况如下：页面走向12131242134物理块 1113322114物理块 222114433缺页缺缺缺缺缺缺缺缺缺从上述页面置换图可以看出： 页面引用次数为 11 次，缺页次数为 9 次，所以缺页率为 9/11。若采

9、用后一种页面淘汰策略， 其页面置换情况如下：页面走向12131242134物理块 111311134物理块 22224222缺页缺缺缺缺缺缺缺缺在一个请求分页存储管理系统中， 一个作业的页面走向为 4，3，2，1，4，3，5， 4，3，2，1，5，当分配给该作业的物理块数分别为 3，4 时，试计算采用下述页面淘汰算法时的缺页率 （假设开始执行时主存中没有页面） ，并比较所得结果。（1）最佳置换淘汰算法（2）先进先出淘汰算法（3）最近最久未使用淘汰算法解：（ 1）根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下：走向432143543215块 14444422块 2333331块 3

10、21555缺页缺缺缺 缺缺缺缺缺页率为： 7/12走向432143543215块 1444441块 233333块 32222块 4155缺页缺缺缺 缺缺缺缺缺页率为： 6/12由上述结果可以看出， 增加分配 给作业 的内存块数可以降低缺页率（ 2）根据所给页面走向， 使用最佳页面淘汰 算法时，页面置换情况如下：走向432143543215块 1444111555块 233344432块 32223321缺页缺缺缺 缺缺缺缺缺页率为： 9/12走向432143543215块 2333344445块 322223333块 41111222缺页缺缺缺 缺缺缺缺缺页率为： 10/12由上述结果可以看出， 对先进先出算法而言， 增加分配给作业的内存块数反而使缺页率上升， 这种异常现象称为 Belady 现象 。(3) 根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下：走向432143543