2022年操作系统计算题 .pdf
计算题：一、生产消费者问题为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2 表示，初值为。由于在此问题中有M 个生产者和N 个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。二、地址转换例 1：假设在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024 字节，试将逻辑地址1011，2148，3000，4000，5012 转化为相应的物理地址。页号块号0 2 1 3 2 1 3 6 解：此题中，为了描述方便，设页号为P，页内位移为W，逻辑地址为A，页面大小为L，则：p=int(A/L) w=A mod L 对于逻辑地址1011 p=int(1011/1024)=0 w=1011 mod 1024=1011 查页表第0 页在第二块，所以物理地址为3059。对于逻辑地址2148 p=int(2148/1024)=2 w=2148 mod 1024=100 查页表第2 页在第 1 块，所以物理地址为1124。对于逻辑地址3000 p=int(3000/1024)=2 w=3000 mod 1024=928 查页表第2 页在第 1 块, 所以物理地址为1796。Q：j = 0;while (1) P(S2);P(mutex);从 Bufferj取产品 ;j = (j+1) % n;V(mutex);V(S1);消费产品 ;P：i = 0; while (1) 生产产品 ; P(S1); P(mutex); 往 Buffer i 放产品; i = (i+1) % n; V(mutex); V(S2); ; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页对于逻辑地址4000 p=int(4000/1024)=3 w=4000mod 1024=928 查页表第3 页在第 6 块, 所以物理地址为7072。对于逻辑地址5012 p=int(5012/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 6464 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 物理块 1 1 1 3 1 1 1 3 4 物理块 2 2 2 2 4 2 2 2 缺页缺缺缺缺缺缺缺缺精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页在一个请求分页存储管理系统中，一个作业的页面走向为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 4 2 2 块 2 3 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 页
