2022年操作系统计算题 .docx

精选学习资料 - - - - - - - - - 运算题：一、生产消费者问题为解决生产者消费者问题,应当设两个同步信号量,一个说明空缓冲区的数目,用 S1表示,初值为有界缓冲区的大小 N,另一个说明已用缓冲区的数目,用 S2 表示,初值为；由于在此问题中有M 个生产者和N 个消费者,它们在执行生产活动和消费活动中要对有界缓冲区进行操作；由于有界缓冲区是一个临界资源,需要设置一个互斥信号量 mutex,其初值为；P：Q：必需互斥使用,所以,另外仍i = 0; j = 0;while 1 while 1 生产产品 ; PS2;PS1; Pmutex;Pmutex; 从 Bufferj 取产品 ;往 Buffer i 放产 j = j+1 % n;品; Vmutex;i = i+1 % n; VS1;Vmutex; 消费产品 ;VS2; ; 二、地址转换1024 字节,例 1：假设在一分页储备治理系统中,某作业的页表如下所示；已知页面大小为试将规律地址1011,2148,3000,4000,5012 转化为相应的物理地址；A,页面大小为L,页号块号0 2 1 3 2 1 3 6 解：此题中,为了描述便利,设页号为P,页内位移为W,规律地址为就：p=intA/L 3059；1124；w=A mod L 对于规律地址1011 p=int1011/1024=0 w=1011 mod 1024=1011 查页表第 0 页在其次块,所以物理地址为对于规律地址2148 p=int2148/1024=2 w=2148 mod 1024=100 查页表第 2 页在第 1 块,所以物理地址为对于规律地址3000 p=int3000/1024=2 w=3000 mod 1024=928 名师归纳总结 查页表第 2 页在第 1 块, 所以物理地址为1796；第 1 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 对于规律地址 4000 p=int4000/1024=3 w=4000mod 1024=928 查页表第 3 页在第 6 块, 所以物理地址为7072；对于规律地址5012 p=int5012/1024=4 w=5012mod1024=916 因页号超过页表长度,该规律地址非法；例 2：在一分页储备治理系统中 ,规律地址长度为 16 位 ,页面大小为 4096 字节 ,现有一规律地址为2F6AH, 且第 0, 1, 2 页依次存放在物理块 5, 10 ,11 中,问相应的物理地址为多少 . 解:由题目所给给条件可知 ,本页式系统的规律地址结构为 : 规律地址 2F6AH 的二进制表示如下 : 由此可知规律地址2F6AH 的页号为 2,该页存放在第11 号物理块中 ,用十六进制表示志号为 B,所以物理地址为 BF6AH. 三、求文件最大长度例： 设文件索引节点中有 7 个地址项,其中 4 个地址项为直接地址索引,2 个地址项是一级间接地址索引, 1 个地址项是二级间接地址索引,每个地址项大小为 4 字节,假设磁盘索引块和盘块大小均为 256 字节,就可表示的单个文件的最大长度是多少？解答：此题的文件结构属混合索引安排方式；每个地址项大小为 4 字节,索引块和盘块大小为 256 字节, 每个索引块中的项目数=256B/4B=64 个；4 个地址项为直接地址索四、引,对应的文件大小为4×256B=1KB ；2 个地址项是一级间接地址索引,对应的文件大小是 2×64× 256B=32KB ,一个地址项是二级间接地址索引,对应的文件大小为1×64×64×256B=1024KB ；所以单个文件的最大长度=1KB+32KB+1024KB=1057KB；磁盘调度算法：1.先来先服务FCFS名师归纳总结 - - - - - - -第 2 页,共 9 页精选学习资料 - - - - - - - - - 2.最短寻道时间优先SSTF3. SCAN 算法4. 循环扫描 CSCAN 算法例：假设一个活动头磁盘有 200 道, 编号从 0-199. 当前磁头正在 143 道上服务 , 并且刚刚完成了 125 道的恳求 . 现有如下访盘恳求序列 磁道号 : 86, 147, 91, 177, 94, 150, 102, 175, 130 名师归纳总结 - - - - - - -第 3 页,共 9 页精选学习资料 - - - - - - - - - 试给出采纳以下算法后磁头移动的次序和移动总量 总磁道数 . 1. 先来先服务 FCFS磁盘调度算法 . 2. 最短寻道时间优先 SSTF磁盘调度算法 . 3. 扫描法 SCAN 磁盘调度算法 .假设沿磁头移动方向不再有拜访恳求时 , 磁头沿相 反方向移动 . 答案：三、186,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优先级调度算法：总是挑选具有 最高优先级 的进程第一使用处理机；在这种算法中,第一考虑的问题是如何确定进程的优先数；分为：静态优先权：在创建进程的时候便确定的,且在进程的运行期间保持不变；简洁 易行,系统开销小,但不够精确,很可能显现优先权低的作业进程长期不被调度的情形；所以,只在要求不太高的系统中,才使用静态优先数权以便获得动态优先权： 在创建进程时所给予的优先权,可以随进程的推动而转变,更好的调度性能名师归纳总结 例：第 4 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 3.最短作业 /进程优先法 SJF/SPF：SJF:从后备队列中挑选估量运行时间最短的作业,先调入内存运行；SPF:从就绪队列中挑选估量运行时间最短的进程,先将处理机安排给它,使它立刻执行；4.最高响应比作业优先算法HRN ：是对 FCFS 方式和 SJF 方式的一种综合平稳响应比； R作业等待时间需运行时间 / 需运行时间1已等待时间 / 需运行时间1W/T 名师归纳总结 - - - - - - -第 5 页,共 9 页精选学习资料 - - - - - - - - - 例：名师归纳总结 - - - - - - -第 6 页,共 9 页精选学习资料 - - - - - - - - - 六：页面置换算法先进先出页面剔除算法FIFO 挑选在内存中驻留时间最长的页并剔除之抱负剔除算法 最正确页面算法OPT 剔除以后不再需要的或最远的将来才会用到的页面最近最久未使用页面剔除算法LRU 挑选最终一次拜访时间距离当前时间最长的一页并剔除之即剔除没有使用的时间最长的页1 已知页面走向为 1、2、1、 3、 1、2、4、2、1、3、4,且开头执行时主存中没有页面；假设只给该作业安排 2 个物理块, 当采纳 FIFO 页面剔除算法时缺页率为多少？假定现有一种剔除算法,该算法剔除页面的策略为当需要剔除页面时,就把刚使用过的页面作为剔除对象,试问就相同的页面走向,缺页率又为多少？分析及相关学问 在进行内存拜访时,假设所拜访的页已在主存,就称此次拜访胜利；假设所拜访的页不在主存,就称此次拜访失败,并产生缺页中断；假设程序 P 在运行过程中拜访页面的总次数为 S,其中产生缺页中断的拜访次数为 F,就其缺页率为：F/s. 解： 依据所给页面走向,采纳FIFO 剔除算法的页面置换情形如下：页面走向1 2 1 3 1 2 4 2 1 3 4 物理块 1 1 1 3 3 2 2 1 1 4 物理块 2 2 2 1 1 4 4 3 3 缺页缺缺缺缺缺缺缺缺缺从上述页面置换图可以看出：页面引用次数为11 次,缺页次数为9 次,所以缺页率为9/11；假设采纳后一种页面剔除策略,其页面置换情形如下：名师归纳总结 页面走向1 2 1 3 1 2 4 2 1 3 4 第 7 页,共 9 页物理块 1 1 1 3 1 1 1 3 4 物理块 2 缺2 2 2 4 2 2 2 缺页缺缺缺缺缺缺缺- - - - - - -精选学习资料 - - - - - - - - - 在一个恳求分页储备治理系统中,一个作业的页面走向为4,3,2,1,4,3,5,4,3, 2,1,5,当安排给该作业的物理块数分别为 率假设开头执行时主存中没有页面3,4 时,试运算采纳下述页面剔除算法时的缺页,并比较所得结果；（1）最正确置换剔除算法（2）先进先出剔除算法（3）最近最久未使用剔除算法解：1依据所给页面走向,使用最正确页面剔除算法时,页面置换情形如下：走向4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 3 4 2 2 块 2 3 3 3 3 1 块 3 缺缺2 1 5 5 5 缺页缺 缺缺缺缺缺页率为： 7/12 走向4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 4 缺1 块 2 3 3 3 3 3 块 3 2 2 2 2 缺块 4 缺1 5 5 缺页缺 缺缺缺缺页率为： 6/12 由上述结果可以看出,增加安排给作业的内存块数可以降低缺页率2依据所给页面走向,使用最正确页面剔除算法时,页面置换情形如下：走向4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 1 1 1 5 5 5 块 2 缺3 3 3 4 4 4 3 2 块 3 2 2 2 3 3 2 1 缺缺页缺 缺缺缺缺缺页率为： 9/12 走向4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 5 5 5 5 1 1 块 2 缺3 3 3 3 4 4 4 4 5 块 3 2 2 2 2 3 3 3 3 块 4 缺1 1 1 1 2 2 2 缺页缺 缺缺缺缺缺页率为： 10/12 由上述结果可以看出, 对先进先出算法而言, 增加安排给作业的内存块数反而使缺页率上升,这种反常现象称为 Belady 现象 ；3 依据所给页面走向,使用最正确页面剔除算法时,页面置换情形如下：名师归纳总结 走向4 3 2 1 4 3 5 4 3 2 1 5 第 8 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 块 1 4 4 4 1 1 1 5 2 2 2 块 2 缺缺3 2 4 4 4 4 1 1 块 3 2 3 2 3 3 3 3 5 缺页缺 缺缺缺缺缺页率为： 10/12 走向4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 4 4 4 5 块 2 3 3 3 3 3 3 3 块 3 缺 缺2 2 5 5 1 1 块 4 1 1 2 2 2 缺缺页缺缺缺缺缺缺页率为 :8/12 名师归纳总结 由上述结果可以看出,增加安排给作业的内存块数可以降低缺页率. 第 9 页,共 9 页- - - - - - -