《操作系统计算题》由会员分享，可在线阅读，更多相关《操作系统计算题（10页珍藏版）》请在金锄头文库上搜索。
1、计算题:生产消费者问题为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N,另一个说明已用缓冲区的数目，用S2表示，初值为0。由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进展操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex,其初值为1。P:i = 0;while (1)生产产品；P(Si)；P(mutex);往Buffer i放产 品；i = (i+1) % n;V(mutex);V(S2);；Q:j = 0；while (1)P(S2)；P(mutex)
2、;从Bufferj取产品;j = (j+1) % n；V(mutex);V(S1)；消费产品；二、地址转换例1:假设在一分页存储管理系统中，某作业的页表如下所示。页面大小为1024字节，试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地址。页号块号02132136解：此题中，为了描述方便，设页号为P,页内位移为W,逻辑地址为A,页面大小为L,那么：p=int(A/L)w=AmodL对于逻辑地址1011p=int(1011/1024)=0w=1011mod1024=1011查页表第0页在第二块，所以物理地址为3059。对于逻辑地址2148p=int(2148/1024
3、)=2w=2148mod1024=100查页表第2页在第1块，所以物理地址为1124。对于逻辑地址3000p=int(3000/1024)=2w=3000mod1024=928查页表第2页在第1块，所以物理地址为1796。对于逻辑地址4000p=int(4000/1024)=3w=4000mod1024=928查页表第3页在第6块，所以物理地址为7072。对于逻辑地址5012p=int(5012/1024)=4w=5012mod1024=916因页号超过页表长度，该逻辑地址非法。例2:在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH,且第0,1,
4、2页依次存放在物理块5,10,11中，问相应的物理地址为多少？解:由题目所给给条件可知，本页式系统的逻辑地址构造为：页号p1页内位移W逻辑地址2F6AH的二进制表示如下：0010L111Q11C1Q10由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中，用十六进制表示志号为B,所以物理地址为BF6AH.三、求文件最大长度例：设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索弓I,1个地址项是二级间接地址索引，每个地址项大小为4字节，假设磁盘索引块和盘块大小均为256字节，那么可表示的单个文件的最大长度是多少？解答：此题的文件构造属混合索引分配方
5、式。每个地址项大小为4字节，索引块和盘块大小为256字节，每个索引块中的工程数=256B/4B=64个。4个地址项为直接地址索引，对应的文件大小为4X256B=1KB。2个地址项是一级间接地址索引，对应的文件大小是2X64X256B=32KB,一个地址项是二级间接地址索引，对应的文件大小为1X64X64X256B=1024KB。所以单个文件的最大长度=1KB+32KB+1024KB=1057KB。四、磁盘调度算法：1.先来先效劳FCFS2.最短寻道时间优先融访问的F一个砥道号程地距嘤f磁道敝：55455H33919219072ItiQ7C1501O38113184146（从ico号磁道开她）平
6、均寻过长度tS5.3被访问的下一个磁道号移动犯高（磁道数）90105B325533916381182015013Z16010；18424一-d从100号磁道开始）平均寻道氏度I7.5SSTF例：假设一个活动头磁盘有200道，编号从0-199.当前磁头正在143道上效劳,并且刚刚完成了125道的请求.现有如下访盘请求序列(磁道号)：86,147,91,177,94,150,102,175,130试给出采用以下算法后磁头移动的顺序和移动总量(总磁道数).(1) .先来先效劳(FCFS潞盘调度算法.(2) .最短寻道时间优先(SSTF廨盘调度算法.(3) .扫描法(SCAN)磁盘调度算法.(假设沿磁
7、头移动方向不再有访问请求时，磁头沿相反方向移动.)答案：三、186,147,91,177,94,150,102,175,1302当前磁头在143道上：147,150,130,102,94,91,86,175,1773当前磁头在143道上，并且刚刚完成125道的请求147,150,175,177,130,102,94,91,86五、调度算法求周转时间，加权周转时间1.先来先效劳调度算法FCFS:该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配给它，使之投入运行。在单道环境卜，某批处理必然有四道作业，i_L妞他们的迸入系统的时刻估计拓算一时7川如卜=进柄!到利时翔1服务时
8、同JF好时期元成时期冏榜时网福权网转A010,111B11UO11OO1C21IU11OZ1001OOD31G01022021991.99知作Mkc的带杈周转时间高达1(XK长作业D的带权周转时网仅为1.9。2.优先级调度算法：总是选择具有最高优先级的进程首先使用处理机。在这种算法中，首先考虑的问题是如何确定进程的优先数。分为：静态优先权：在创立进程的时候便确定的,且在进程的运行期间保持不变。简单易行，系统开销小,但不够准确，很可能出现优先权低的作业进程长期不被调度的情况。所以，只在要求不太高的系统中，才使用静态优先数权动态优先权：在创立进程时所赋予的优先权,可以随进程的推进而改变，以便获得更
9、好的调度性能可：4列2,有5个进程P1、P2、P3vP4xP5,它们同时依次进入就绪队列，它们的优先数和需要的处理机时间女口下:进程处理机时间优先数P1103-P211-P323P414P552忽略进程调度所花的时间.要求：(1)分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；(2)分别计算各进程在就绪队列中的等待时间和平均等待时间.-解：1)采用先来先服务调度算法时各进程的执行次序为：Pl-P2fp3-P4-P5。.采用静态优先级调度算法时各进程的执行次序为EP4-P1-P3-P5-P2。(2)FCFS中，平均等待时间=(0+10+11+13+14)/5=9.6；静态优先
10、级法中，平均等待时间=(1+18+11+0+13)/5=8.6班机处理机时向FCF5等1354口龄者优先级法州德时力P11O01P21101KP321111P4113OP5514133最短彳业/进程优先法SJF/SPF：SJF从后备队列中选择估计运行时间最短的作业，先调入内存运行。SPF队就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。4最高响应比作业优先算法HRN：是对FCFS方式和SJF方式的一种综合平衡响应比。R=(作业等待时间+需运行时间)/需运行时间=1+已等待时间/需运行时间=1+W/T作业调度算法应用例子作业估U谢了时间册周转时何(分钟)档权周转时间JOB
11、18：00120JOB2&30J0JOB3%0010JQBI9：S201作业用均周例询T=例蹄叔平均脚翻枷W-先来先服务调度算法计算结果作业制郎胴GW带权冏注M可JOB18；00120：no10：00120IJGB28：50501U：(X)10；3012014JCR39工0011010：5011：UU12n12JCXM9:S020n：oo11：20P*XP43均确M间阳明鄂问-112.5W=4.9754fl0199最短作业优先作业算法计算结果作业恫估计运行响挣10瑙时间结前胸时间（渊）时间JOB1&0011蜀&0010：001201,K股&505(110：3011；2015(13rJ0B311
12、010：0010:107079：山2n10：1010：30402作业T颂翱晌=弊作阴淑平均同酮间W=3,2538013最高响应比优先作业算法计算结果作业以响估惭HR（珊）他响瞒搁份钩晌J0B18：00120S：Ofli10：001201J0B2503D10110山001302.6J0B3%001010：册10：1070F7JOB4%502011:(山加904.5作业平期期间T=10Z5作崎榜尚聃响W台3.77541015.1六：页面置换算法先进先出页面淘汰算法FIFO选择在内存中驻留时间最长的页并淘汰之理想淘汰算法一最正确页面算法OPT淘汰以后不再需要的或最远的将来才会用到的页面最近最久未使用
13、页面淘汰算法LRU选择最后一次访问时间距离当前时间最长的一页并淘汰之即淘汰没有使用的时间最长的页1.页面走向为1、2、1、3、1、2、4、2、1、3、4,且开场执行时主存中没有页面。假设只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就一样的页面走向，缺页率又为多少？分析及相关知识在进展内存访问时，假设所访问的页已在主存，那么称此次访问成功；假设所访问的页不在主存，那么称此次访问失败，并产生缺页中断。假设程序P在运行过程中访问页面的总次数为S,其中产生缺页中断的访问次数为F,那么其缺页率为：F/s.解：根据所给页面走向，采用FIFO淘汰算法的页面置换情
