操作系统计算题综合

综合计算题一、先来先服务（FCFS）调度算法例1：作业名到达时间服务时间A01B1100C21D3100调度次序：ABCD→→→作业名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100周转时间服务时间完成时间-到达时间开始时间+服务时间上一个进程的完成时间0111110110011011021001001022021991.99一、先来先服务（FCFS）调度算法例2：下面三个作业几乎同时到达系统并立即进行FCFS调度：作业名所需CPU时间作业128作业29作业33假设提交顺序为1、2、3，则平均作业周转时间T=若提交顺序改为作业2、1、3，则T=若提交顺序改为作业3、2、1，则T=FCFS调度算法的平均作业周转时间与作业提交的顺序有关。(28+37+40)/3=352918作业到达时间服务时间开始时间结束时间周转时间带权周转时间周转时间＝结束-到达带权周转时间＝周转/服务执行顺序：SJF/SPF__非抢占式举例A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间周转时间带权周转时间SJF完成时间周转时间带权周转时间471214184610111491225.53.52.84918613481639812.673.21.52.252.1FCFS：A→B→C→D→ESJF:A→D→B→E→CFCFS和的SJF比较课堂练习练习：有如下四个进程，它们的到达时间和服务时间如下所示，请分别计算在采用FCFS、SPF非抢占调度算法时的平均周转时间和平均等待时间。进程到达时间服务时间P107P224P341P454进程到达时间服务时间P107P224P341P454FCFSP142110P257P41612P3平均周转时间=((7-0)+(11-2)+(12-4)+(16-5))/4=8.75平均等待时间=(0+(7-2)+(11-4)+(12-5))/4=4.75课堂练习课堂练习进程到达时间服务时间P107P224P341P454SPF73160812P1P3P2P4平均周转时间=((7-0)+(12-2)+(8-4)+(16-5))/4=8平均等待时间=((0-0)+(8-2)+(7-4)+(12-5))/4=4FCFS非抢占SPF吞吐量0-7ms11平均周转时间8.758平均等待时间4.754SPF与FCFS的比较EG：进程到达时间服务时间P107P224P341P454RR（时间片为4）P1P2045678910111213141516P1P3P4平均周转时间=((16-0)+(8-2)+(9-4)+(13-5))/4=8.75平均等待时间=(9+2+4+4)/4=4.75EG1：进程到达时间服务时间优先数P1073P2242P3414P4541Gantt图平均周转时间=((7-0)+(15-2)+(16-4)+(11-5))/4=9.5平均等待时间=(0+9+11+2)/4=5.5P1P202457111516P4P3优先数越小优先级越高EG2：进程到达时间服务时间优先数P1073P2242P3414P4541Gantt图平均周转时间=((15-0)+(10-2)+(16-4)+(9-5))/4=9.75平均等待时间=(8+4+11+0)/4=5.75P1P202459101516P4P3P2P1FCFSSJFRR-4优先权-非抢占式优先权-抢占式平均周转时间8.7588.759.59.75平均等待时间4.7544.755.55.75返回优先权的变化为PR要求服务时间响应时间要求服务时间要求服务时间等待时间优先权PR为响应比。如等待时间相同,则要求服务时间愈短,其优先权愈高--SPF.如要求服务时间相同,优先权决定于等待时间----FCFS。对长作业,若等待时间足够长，优先权也高，也能获得CPU。算法HRP示例HRP的调度性能WT作业到达时间Tin服务时间Tr开始时间Ts结束时间Tc=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周转时间T=结束时间Tc-到达时间Tin=3-0=3周转时间T带权周转时间W=周转时间T/服务时间Tr=3/3=1带权周转时间W平均=[(9-4)+4]/4=2.25=[(9-6)+5]/5=1.6=[(9-8)+2]/2=1.5RCRDRERD=[(13-6)+5]/5=2.4RE=[(13-8)+2]/2=3.5五、高响应比优先权调度算法HRP不同调度算法对同一个作业/进程的性能分析:作业到达时间Tin服务时间Tr从平均周转时间及其平均带权周转时间来看，HRP刚好介于FCFS与SJP之间，即好于FCFS，次于SJP。A03B26C44D65E82FCFS8.602.56SJF7.601.84HRP8.002.14返回假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057true（1）T0时刻的安全性T0时刻存在着一个安全序列{P1P3P4P2P0}，故系统是安全的。银行家算法的例子银行家算法的例子P1请求资源时的资源分配表MaxAllocationNeedAvailableABCABCABCABCP0753010743332(230)P1322200122(302)(020)P2902302600P3222211011P4433002431WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1230020302532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057trueP1请求资源时的安全性检查表存在着一个安全序列{P1P3P4P2P0}，故系统是安全的，可以立即将P1所申请的资源分配给它。银行家算法的例子（3）P4请求资源Request4(3,3,0)P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查:1)Request4(3,3,0)≤Need4(4,3,1)2)Request4(3,3,0)Available(2,3,0),表示资源不够,则让P4等待银行家算法的例子银行家算法的例子MaxAllocationNeedAvailableABCABCABCABCP0753010743332[030][723](230)[210]P1322200122(302)(020)P2902302600P3222211011P4433002431P0请求资源时的资源分配表Available＝(2,1,0)不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配返回目录例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：（1）页式存储管理系统的逻辑地址为：其中页内地址表每页的大小即2048B=2*1024B=211B，所以页内地址为11位；页号表最多允许的页数即16页=24页，所以页号为4位。故逻辑地址至少应为15位。（2）物理地址为：其中块内地址表每块的大小与页大小相等，所以块内地址也为11位；其中块号表内存空间最多允许的块数即8块=23块，所以块号为3位。故内存空间至少应为14位，即214=16KB。页号p位移量w返回块号b块内偏移d例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。页号块号02132136解：由题知逻辑地址为：物理地址为：（1）逻辑地址1011（十进制）的二进制表示为：001111110011，由此可知逻辑地址1011的页号0，查页表知该页放在第2物理块中；其物理地址的二进制表示为：0101111110011，所以逻辑地址1011对应的物理地址为0BF3H。其地址转换图如后所示。页号2位位移量w10位块号b3位块内位移d10位（2）逻辑地址2148（十进制）的二进制为：100001100100，由此可知逻辑地址2148的页号是2，查页表知该页放入物理块1中；其物理地址的二进制是：0010001100100，所以逻辑地址2148对应的物理地址是0464H。（3）逻辑地址5012（十进制）的二进制表示为：1001110010100，可知该逻辑地址的页号为4，查页表知该页为不合法页，则产生越界中断。地址变换过程+页表长度页表始址3F30页表寄存器逻辑地址1011（03F3H）物理地址0BF3H越界中断页合法页号块号0213213623F3四、地址变换例题1例1、在一个段式存储管理系统中，其段表为：段号内存起始地址段长02105001235020210090313505904193895试求右表中逻辑地址对应的物理地址是什么？解：逻辑地址为：逻辑地址对应的物理地址为：210+430=640。逻辑地址因为段内地址120段长90，所为该段为非法段。段号段内地址0430212004302120由段表可知段号为3位，段内地址为10位。例2、某段表的内容如下：段号段首址段长度0120K40K1760K30K2480K20K3370K20K对于逻辑地址2154，它对应的物理地址为多少？解：逻辑地址为：由段表可知段号为2位，段内地址为16位，段允许的最大长度为216=210*26=1024*64=65536。所以逻辑地址2154（二进制为100001101010）的段号为0，查段表知其对应的物理地址为：120K+2154=125034段号段内地址某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。解：虚拟地址为：页号5位（25=32），页内位移10位（110=1024）；物理地址为：物理块号4位（24=16），块内位移（110=1024）10位。虚拟地址0A5C对应的二进制为：000101001011100，即虚拟地址0A5C的页号为2，页内位移为1001011100，由题意知对应的物理地址为：01001001011100即125C。同理求093C的物理地址为293C。略假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换页面淘汰算法时的缺页率？返回注：实际上这种算法无法实现，因页面访问的未来顺序很难精确预测，但可用该算法评价其它算法的优劣。页面走向123412512345物理块1物理块2物理块3缺页1缺缺缺缺缺缺缺12312121212121212333444442555555(7/12)1、假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？页面走向123412512345物理块111