操作系统计算题.doc

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

1、计算题:一、 生产消费者问题为解决生产者消费者问题,应该设两个同步信号量,一个说明空缓冲区得数目,用S1表示,初值为有界缓冲区得大小,另一个说明已用缓冲区得数目,用表示,初值为0。由于在此问题中有M个生产者与N个消费者,它们在执行生产活动与消费活动中要对有界缓冲区进行操作。由于有界缓冲区就是一个临界资源,必须互斥使用,所以，另外还需要设置一个互斥信号量mtex,其初值为1。P:i = 0;while (1) 生产产品; P(S1); P(mutex); 往Buffer i放产品; i = (i+1) % n; V(mutex); V(S2); ;Q: j = 0; while (1) P(S2

2、); P(mutex); 从Bufferj取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品; ;二、 地址转换例:若在一分页存储管理系统中,某作业得页表如下所示。已知页面大小为104字节,试将逻辑地址11,18，300，4000,512转化为相应得物理地址。页号 块号 2 32 解:本题中,为了描述方便,设页号为P,页内位移为W,逻辑地址为A,页面大小为,则: p=i(AL)Amo L对于逻辑地址111 =int(11/12)0 w=011 md 10=101查页表第0页在第二块,所以物理地址为3059。对于逻辑地址2148 pt(2148/1024)=2 w

3、=2148 mod10=10查页表第2页在第1块，所以物理地址为112。对于逻辑地址00 int(3000/024)=2w00 mod10249 查页表第2页在第1块, 所以物理地址为179。对于逻辑地址4000 p=nt(4000/024) =4000mod 1024=2 查页表第3页在第块, 所以物理地址为072。对于逻辑地址512 int(5012/124) w012mo102=916因页号超过页表长度，该逻辑地址非法。例2:在一分页存储管理系统中，逻辑地址长度为16位,页面大小为406字节,现有一逻辑地址为2F6AH,且第0,1, 2页依次存放在物理块， 10 ,11中,问相应得物理地

4、址为多少?解：由题目所给给条件可知，本页式系统得逻辑地址结构为:逻辑地址2FAH得二进制表示如下:由此可知逻辑地址2F6AH得页号为2,该页存放在第11号物理块中,用十六进制表示志号为B，所以物理地址为BF6AH、三、 求文件最大长度例：设文件索引节点中有个地址项,其中4个地址项为直接地址索引,2个地址项就是一级间接地址索引，1个地址项就是二级间接地址索引,每个地址项大小为4字节，若磁盘索引块与盘块大小均为56字节，则可表示得单个文件得最大长度就是多少?解答:本题得文件结构属混合索引分配方式。每个地址项大小为4字节,索引块与盘块大小为6字节,每个索引块中得项目数=26B/4B=64个。4个地址

5、项为直接地址索引,对应得文件大小为56B=1B。2个地址项就是一级间接地址索引,对应得文件大小就是26456=32,一个地址项就是二级间接地址索引,对应得文件大小为1646256=24KB。所以单个文件得最大长度=1K+32K02K1057B。四、 磁盘调度算法:1. 先来先服务CFS2. 最短寻道时间优先SSF3. SCAN算法4. 循环扫描(CC)算法例:假设一个活动头磁盘有00道, 编号从0-19、 当前磁头正在43道上服务, 并且刚刚完成了125道得请求、 现有如下访盘请求序列（磁道号）: 86, 17， 9, 177, 4, 150,102, 175,13 试给出采用下列算法后磁头移

6、动得顺序与移动总量(总磁道数)、 ()、 先来先服务(FFS)磁盘调度算法、 （2)、 最短寻道时间优先(TF)磁盘调度算法、(3)、扫描法（SCA）磁盘调度算法、(假设沿磁头移动方向不再有访问请求时，磁头沿相反方向移动、)答案:三、(1)86,147,91，77,94,10,102,175，130 (2)当前磁头在143道上: 147，150,0,2,94,1,6，175,177 (）当前磁头在1道上,并且刚刚完成25道得请求 47，150,175,177,3，10，94,91,86五、 调度算法(求周转时间,加权周转时间)1.先来先服务调度算法FCS:该算法按照进程进入就绪队列得先后顺序选

7、择最先进入该队列得进程,把处理机分配给它,使之投入运行。例.优先级调度算法:总就是选择具有最高优先级得进程首先使用处理机。在这种算法中,首先考虑得问题就是如何确定进程得优先数。 分为： 静态优先权:在创建进程得时候便确定得,且在进程得运行期间保持不变。(简单易行,系统开销小,但不够精确,很可能出现优先权低得作业(进程）长期不被调度得情况。所以,只在要求不太高得系统中,才使用静态优先数(权）)动态优先权:在创建进程时所赋予得优先权,可以随进程得推进而改变，以便获得更好得调度性能例：、最短作业/进程优先法(SJSF）:SJ：从后备队列中选择估计运行时间最短得作业,先调入内存运行。F：从就绪队列中选

8、择估计运行时间最短得进程，先将处理机分配给它，使它立即执行。4、最高响应比作业优先算法(HRN）:就是对FCFS方式与SF方式得一种综合平衡响应比。=(作业等待时间+需运行时间)/ 需运行时间 =+已等待时间/ 需运行时间 1W/T例：六:页面置换算法先进先出页面淘汰算法(FIFO) 选择在内存中驻留时间最长得页并淘汰之理想淘汰算法最佳页面算法(T） 淘汰以后不再需要得或最远得将来才会用到得页面最近最久未使用页面淘汰算法(R) 选择最后一次访问时间距离当前时间最长得一页并淘汰之即淘汰没有使用得时间最长得页1 已知页面走向为1、2、1、3、1、1、3、,且开始执行时主存中没有页面。若只给该作业分

9、配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有一种淘汰算法,该算法淘汰页面得策略为当需要淘汰页面时,就把刚使用过得页面作为淘汰对象,试问就相同得页面走向,缺页率又为多少?分析及相关知识 在进行内存访问时,若所访问得页已在主存,则称此次访问成功;若所访问得页不在主存,则称此次访问失败,并产生缺页中断。若程序P在运行过程中访问页面得总次数为，其中产生缺页中断得访问次数为F,则其缺页率为：s、 解:根据所给页面走向，采用FIFO淘汰算法得页面置换情况如下:页面走向 1 1 3 1 2 2 1 物理块1 3 3 2 2 4物理块2 2 1 4 3 3缺页 缺 缺 缺 缺 缺 缺 缺

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

11、最佳页面淘汰 算法时,页面置换情况如下:走向 4 3 2 1 4 5 4 3 2 1 5块1 4 4 4 4 4 2 2块 3 3 3 3 块 2 1 5 5 5缺页 缺 缺 缺 缺 缺 缺缺缺页率为:7/12走向 4 1 34 3 2 1 5块1 4 4 4 1块 3 3 3 3块3 22 块4 1 5 5缺页 缺 缺 缺缺 缺 缺 缺缺页率为：/2由上述结果可以瞧出，增加分配 给作业得内存块数可以降低缺页率（2）根据所给页面走向,使用最佳页面淘汰算法时,页面置换情况如下：走向 3 2 1 4 5 4 1 块1 4 1 1 1 5 5块 3 3 4 4 3 2块3 2 2 3 3 2 1缺页

12、 缺 缺 缺缺 缺 缺 缺缺页率为:9/1走向 2 1 4 3 5 4 3 1 5块1 4 4 4 4 55 5 1 1块2 3 3 4 4 块3 2 3 3 3 3块4 1 1 1 2 2缺页 缺 缺 缺 缺 缺 缺 缺缺页率为:10/1由上述结果可以瞧出,对先进先出算法而言,增加分配给作业得内存块数反而使缺页率上升，这种异常现象称为Bead 现象 。()根据所给页面走向,使用最佳页面淘汰 算法时，页面置换情况如下:走向 3 2 4 3 5 4 2 1 块1 4 4 4 1 1 1 5 22块2 4 4 1块3 2 3 2 3 3 3 5缺页 缺 缺 缺 缺 缺 缺 缺缺页率为:0/12走向 43 1 4 3 5 4 3 2 块1 4 4 4 4 4 4 5块 3 3 3 3 3 3块3 2 2 5 5 1 1块4 1 2 2缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为:8/12 由上述结果可以瞧出,增加分配给作业得内存块数可以降低缺页率、