2022年操作系统计算题.docx

《2022年操作系统计算题.docx》由会员分享，可在线阅读，更多相关《2022年操作系统计算题.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运算题：一、生产消费者问题为解决生产者消费者问题，应当设两个同步信号量，一个说明空缓冲区的数目，用S1 表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2 表示，初值为；由于在此问题中有M 个生产者和 N 个消费者，它们在执行生产活动和消费活动中要对P：i = 0;while 1生产产品 ; PS1;Pmutex;往 Buffer品;Q：j =0;while 1PS2;Pmutex;从 Bufferj取产品 ;i 放产i = i+1 % n; Vmutex;VS2;j = j+1 % n; Vmutex;VS1;消费产品 ;二、地址转换例 1：假设在一分页储备治理系统中，某作业

2、的页表如下所示；已知页面大小为试将规律地址 1011， 2148， 3000 ， 4000， 5012 转化为相应的物理地址；1024 字节，有界缓冲区进行操作；由于有界缓冲区是一个临界资源，必需互斥使用，所以，另外仍需要设置一个互斥信号量mutex，其初值为；页号0块号2132136解：此题中，为了描述便利，设页号为P，页内位移为 W，规律地址为A ，页面大小为 L， 就：p=intA/L w=A mod L对于规律地址 1011p=int1011/1024=0 w=1011 mod 1024=1011查页表第 0 页在其次块，所以物理地址为3059；对于规律地址 2148 p=int214

3、8/1024=2 w=2148 mod 1024=100查页表第 2 页在第 1 块，所以物理地址为1124；对于规律地址 3000 p=int3000/1024=2 w=3000 mod 1024=928查页表第 2 页在第 1 块, 所以物理地址为 1796；对于规律地址 4000 p=int4000/1024=3 w=4000mod 1024=928查页表第 3 页在第 6 块, 所以物理地址为 7072；对于规律地址 5012 p=int5012/1024=4 w=5012mod1024=916因页号超过页表长度，该规律地址非法；例 2：在一分页储备治理系统中,规律地址长度为16 位,

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

5、表示的单个文件的最大长度是多少？解答：此题的文件结构属混合索引安排方式；每个地址项大小为 4 字节，索引块和盘块大小为 256 字节， 每个索引块中的项目数 =256B/4B=64 个；4 个地址项为直接地址索引，对应的文件大小为 4256B=1KB ；2 个地址项是一级间接地址索引，对应的文件大小是 264256B=32KB ，一个地址项是二级间接地址索引，对应的文件大小为 16464256B=1024KB ；所以单个文件的最大长度 =1KB+32KB+1024KB=1057KB ；四、磁盘调度算法：1. 先来先服务 FCFS2. 最短寻道时间优先SSTF3. SCAN 算法4. 循环扫描

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

7、02当前磁头在 143 道上：147， 150， 130，102， 94， 91， 86， 175， 1773当前磁头在 143 道上，并且刚刚完成125 道的恳求147， 150， 175， 177， 130， 102，94， 91，86五、调度算法求周转时间，加权周转时间1. 先来先服务调度算法FCFS：该算法依据进程进入就绪队列的先后次序挑选最先进入该队列的进程，把处理机安排给它，使之投入运行；例2. 优先级调度算法： 总是挑选具有 最高优先级 的进程第一使用处理机；在这种算法中，第一考虑的问题是如何确定进程的优先数；分为：静态优先权：在创建进程的时候便确定的，且在进程的运行期间保持不变

8、；简洁易行，系统开销小，但不够精确，很可能显现优先权低的作业进程长期不被调度的情形；所以，只在要求不太高的系统中，才使用静态优先数权动态优先权： 在创建进程时所给予的优先权，可以随进程的推动而转变，以便获得更好的调度性能例：3. 最短作业 /进程优先法 SJF/SPF ：SJF: 从后备队列中挑选估量运行时间最短的作业， 先调入内存运行；SPF: 从就绪队列中挑选估量运行时间最短的进程，先将处理机安排给它，使它立刻执行；4. 最高响应比作业优先算法HRN ：是对 FCFS 方式和 SJF 方式的一种综合平稳响应比； R 作业等待时间需运行时间/ 需运行时间 1已等待时间/ 需运行时间 1 W/

9、T例：六：页面置换算法先进先出页面剔除算法FIFO 挑选在内存中驻留时间最长的页并剔除之抱负剔除算法 最正确页面算法 OPT 剔除以后不再需要的或最远的将来才会用到的页面最近最久未使用页面剔除算法LRU 挑选最终一次拜访时间距离当前时间最长的一页并剔除之即剔除没有使用的时间最长的页1 已知页面走向为 1、2、1、 3、 1、2、4、2、1、3、4，且开头执行时主存中没有页面；假设只给该作业安排2 个物理块， 当采纳 FIFO页面剔除算法时缺页率为多少？假定现有一种剔除算法， 该算法剔除页面的策略为当需要剔除页面时，就把刚使用过的页面作为剔除对象，试问就相同的页面走向，缺页率又为多少？ 分析及相

10、关学问 在进行内存拜访时，假设所拜访的页已在主存，就称此次拜访胜利；假设所拜访的页不在主存，就称此次拜访失败，并产生缺页中断；假设程序P 在运行过程中拜访页面的总次数为S,其中产生缺页中断的拜访次数为F,就其缺页率为： F/s.解： 依据所给页面走向，采纳FIFO 剔除算法的页面置换情形如下：页面走向12131242134物理块 1113322114物理块 222114433缺页缺缺缺缺缺缺缺缺缺从上述页面置换图可以看出：页面引用次数为11 次，缺页次数为9 次，所以缺页率为9/11；假设采纳后一种页面剔除策略，其页面置换情形如下：页面走向12131242134物理块 111311134物理块

11、 22224222缺页缺缺缺缺缺缺缺缺在一个恳求分页储备治理系统中，一个作业的页面走向为4， 3， 2， 1，4，3，5， 4， 3， 2， 1， 5，当安排给该作业的物理块数分别为3， 4 时，试运算采纳下述页面剔除算法时的缺页率假设开头执行时主存中没有页面，并比较所得结果；（ 1） 最正确置换剔除算法（ 2） 先进先出剔除算法（ 3） 最近最久未使用剔除算法缺页缺 缺缺 缺缺缺 缺缺页率为： 6/12由上述结果可以看出，增加安排给作业 的内存块数可以降低缺页率2依据所给页面走向，使用最正确页面剔除算法时，页面置换情形如下：走向432143543215缺页缺 缺缺 缺缺缺 缺缺页率为： 9/

12、12走向432143543215缺页缺 缺缺 缺缺缺 缺缺页率为： 10/12由上述结果可以看出， 对先进先出算法而言， 增加安排给作业的内存块数反而使缺页率上升， 这种反常现象称为Belady现象 ；3 依据所给页面走向，使用最正确页面剔除算法时，页面置换情形如下：解：1依据所给页面走向，使用最正确页面剔除算法时，页面置换情形如下：走向432143543215块 14444422块 2333331块 321555缺页缺缺缺 缺缺缺 缺缺页率为：7/12走向432143543215块 1444441块 233333块 32222块 4155块 1444111555块 233344432块 32223321块 14444555511块 2333344445块 322223333块 41111222走向432143543215块 14441115222块 232444411块 323233335缺页缺缺缺 缺缺缺缺缺页率为：10/12走向432143543215块 144444445块 23333333块 3225511块 411222缺页缺 缺缺缺缺缺缺缺缺页率为 :8/12由上述结果可以看出 ,增加安排给作业的内存块数可以降低缺页率.