搜索
操作系统专升本复习----计算题计算题类型1：作业调度、进程调度算法根据先来先服务、短作业优先、优先级、高响应比优先、轮转（RR）等调度算法求作业的执行顺序、作业的周转时间、带权周转时间、平均周转时间和平均带权周转时间。2008年（8分）：短作业优先、先来先服务调度算法2014年（7分）：短作业优先调度算法2015年（8分）：先来先服务、短作业优先调度算法2017年（10分）：先来先服务调度算法、抢占式优先级调度算法；例1：在单机系统中，系统中各个进程到达就绪队列的时刻、执行时间和优先级（越小者越高）如下表所示。假设进程的调度时间忽略不计。1、请给出采用FCFS、短作业优先调度算法时各个进程的调度顺序，并计算平均周转时间和平均带权周转时间。2、请计算采用抢占式优先级调度算法时各个进程的平均周转时间和平均带权周转时间。进程到达时间执行时间(ms)优先级P1033P2265P3441P4652P5824平均周转时间：（3+7+9+12+12）/5=8.6平均带权周转时间：（1+1.17+2.25+2.4+6）/5=2.56进程到达时间执行时间(ms)优先级完成时间周转时间带权周转时间P1033P2265P3441P4652P582431318209379121211.172.252.461、FCFS调度算法平均周转时间：（3+7+3+11+14）/5=7.6平均带权周转时间：（1+1.17+2.25+2.4+6）/5=1.84进程到达时间执行时间(ms)优先级完成时间周转时间带权周转时间P1033P2265P5824P3441P465231115209373111411.171.52.752.8短作业优先调度算法平均周转时间：（3+18+4+7+7）/5=7.8平均带权周转时间：（1+3+1+1.4+3.5）/5=1.98进程到达时间执行时间(ms)优先级完成时间周转时间带权周转时间P1033P2265P3441P4652P5824381315203184771311.43.52、采用抢占式优先级调度算法作业进入系统时间计算时间开始时间完成时间周转时间19:0060分钟9:0010:00⑴29:1045分钟⑵⑶⑷39:1525分钟⑸⑹⑺例2：在一个单道批处理系统中，采用响应比高者优先的作业调度算法。当一个作业进入系统后就可以开始调度，假定作业都是仅计算，忽略调度花费的时间。现有三个作业，进入系统的时间和需要计算的时间如下表所示。求出每个作业的开始时间、完成时间及周转时间并填入表中。作业进入系统时间计算时间开始时间完成时间周转时间（分钟）19:0060分钟9:0010:00⑴29:1045分钟⑵⑶⑷39:1525分钟⑸⑹⑺60响应比=（服务时间+等待时间）/服务时间=1+等待时间/服务时间10:00计算作业2、3的响应比，如下：作业2响应比：1+50/45=2.11作业3响应比：1+45/25=2.8作业3的响应比高，因此10:00开始执行作业3，10:25完成。最后执行作业2。10:0010:257010:2511:10120计算题类型2：银行家算法如果判断某时刻是否为安全状态采用安全性算法（若安全，执行安全性算法结束写明安全序列和系统状态是安全的）；如果某进程提出资源请求采用银行家算法（写清1、2、3、4步）。2008年（8分）、2011年、2012年、2013年进程最大需求已分配ABABP13211P26440P331212013年真题例3：已知系统内有三个进程P1、P2、P3共享A、B两类资源，A类资源的数量为8，B类资源的数量为5。设在T时刻资源分配情况如下表所示:（1）问T时刻A、B的可利用资源数分别是多少?（2）T时刻系统是否处于安全状态?为什么?计算题类型3：地址变换1.动态可重定位分区分配的地址变换2.分页存储管理方式的地址变换3.分段存储管理方式的地址变换2012年（选择题1分）、2016年（10分）例4：（2012年真题）一个32位的虚拟地址分为4个域，每个域的长度分别为a、b、c、d位，其中d为页内地址，则系统最多可有（B）个虚拟页面。A.a+b+cB.2a+b+cC.dD.2d1.动态可重定位分区分配的地址变换例5：在分区存储管理中，已知某作业空间如图所示，采用动态重定位进行地址映射。假设分给该作业的主存空间起始地址为4000。（1）指出在图中的地址1和地址2中，哪个是逻辑地址，哪个是物理地址？（2）在图中填写出执行指令MOVL1，[2000]时，所取数据“100”的逻辑地址、物理地址以及动态重定位寄存器的内容（用十进制表示）。（3）在图中填写出指令“MOVL1，[2000]”的主存地址。+动态重定位寄存器0MOVL1[2000]100作业空间500200049990MOVL1[2000]100内存空间40009999地址1地址2例6：在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？2.分页存储管理方式的地址变换解析：方法1逻辑地址2F6AH的二进制：0010111101101010由于逻辑地址长度为16位，页面大小为4096字节，即212，所以低12为表示页内地址所以页号为2，对应块号为11（二进制1011），因为块内地址=页内地址，所以物理地址表示如下：其二进制1011111101101010，即BF6AH0010111101101010页号页内地址1011111101101010块号块内地址例6：在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？解析：方法2由于逻辑地址长度为16位，页面大小为4096字节，即212，所以低12为表示页内地址所以页号为2，对应块号为11（十六进制B），因为块内地址=页内地址，所以物理地址表示如下：所以，物理地址为BF6AH2F6A页号页内地址BF6A块号块内地址例7：某虚拟存储器的用户空间共有32个页面，每页1KB，内存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，给定虚拟地址093CH，请将其变换为物埋地址。逻辑地址093CH的二进制：0000100100111100有已知得逻辑地址长度为15位，页面大小为1KB，即210，所以低10为表示页内地址所以页号为2，对应块号为4（二进制0100），因为块内地址=页内地址，所以物理地址表示如下：其二进制0001000100111100，即113CH0000100100111100页号页内地址0001000100111100块号块内地址解析：段号内存起始地址段长02105001235020210090313505904193895段号段内位移043011025003400例8：在一个段式存储管理系统中，其段表为：试求下列逻辑地址对应的物理地址是什么？3.分段存储管理方式的地址变换物理地址210+430=6402350+10=2360段内地址越界1350+400=1750解析：计算题类型4：分页存储的数据访问时间例9：假定快表检索时间为20ns，内存访问时间为100ns。1.若能在快表中找到CPU给出的页号，CPU存取一个数据将需要的访问时间是多少？2.若不能在快表中找到CPU给出的页号，则为存取一个数据需要的访问时间是多少？3.若假定快表查找命中率为80%，则其有效访问时间为多少？解析：1.则若能在快表中找到CPU给出的页号，CPU存取一个数据将需要(20+100)=120ns。2.若不能在快表中找到CPU给出的页号，则为存取一个数据将需要(20+100+100)=220ns。3.若假定快表查找命中率为80%，则其有效访问时间为120*80%+220*(1-80%)=140ns。计算题类型5：页面置换算法根据最佳、先进先出、最近最久未使用页面置换算法计算缺页次数和缺页率。2012年、2014年（LRU(最近最久未使用)页面置换算法）例10（2012年真题）：在请求分页系统中，一个进程初始执行连续访问页面的次序为：0、2、1、3、0、2、4、0、2、1、3、4，利用FIFO页面淘汰算法，进程内存只能保存3个页面，共发生的缺页次数为（B）。A.8B.9C.7D.10例11：假定分页虚拟存储系统中，某进程的页面访问踪迹为：4，3，2，1，4，3，5，4，3，2，1，5，分配给它的内存物理块数为3。1.按最佳页面置换算法，计算缺页率。2.按先进先出页面置换算法，计算缺页率。3.按LRU页面置换算法，计算缺页率。计算题类型6：磁盘调度算法根据先来先服务、最短寻道时间优先、扫描算法、循环扫描算法，给出寻道顺序，并计算寻道总数和平均寻道长度。2008年（8分）：最短寻道时间优先、扫描算法例12：一个可移动磁头的磁盘具有200个磁道，其编号为0--199，当它刚刚结束了125道的存取后，现正在处理143道的请求，假设系统当前I/0请求序列以FIFO顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几种磁盘调度算法而言，满足以上请求序列，磁头将如何移动？平均寻道长度是多少？1.先来先服务算法2.最短寻道时间优先算法SSTF3.扫描算法SCAN4.循环扫描算法先来先服务算法FCFS从143号磁道开始被访问的下一个磁道号移动距离（磁道数）865714761915617786948315056102481757313045平均寻道长度：565/9=最短寻道时间优先算法SSTF从143号磁道开始被访问的下一个磁道号移动距离（磁道数）147415031302010228948913865175891772平均寻道长度：162/9=扫描算法SCAN从143号磁道开始被访问的下一个磁道号移动距离（磁道数）147415031752517721304710228948913865平均寻道长度：125/9=循环扫描算法CSCAN从143号磁道开始被访问的下一个磁道号移动距离（磁道数）147415031752517728691915943102813028平均寻道长度：169/9=计算题类型7：索引分配与文件最大长度计算索引文件最大长度、计算增量式文件最大长度。2011年例13（2011年真题）：简述在UNIX系统中采用混合索引方式。如果每个盘块大小是4KB，每个盘的地址要用4个字节，那么在UNIX系统中文件最大是多少？给出步骤说明。例13（2011年真题）：简述在UNIX系统中采用混合索引方式。如果每个盘块大小是4KB，每个盘的地址要用4个字节，那么在UNIX系统中文件最大是多少？给出步骤说明。解析：由已知得每个盘块大小4KB，每个盘块号占4B，因此一个盘块内可以存放4KB/4B=1K个盘块。1.直接地址10项（i.add(0)-i.add(9)），可以存放10个盘块号，文件大小为10*4KB=40KB；2.一级索引地址是i.add(10)，存放1个索引表，1个索引表内含1K个盘块，文件大小为：1K*4KB=4MB3.二级索引地址是i.add(11)，文件大小为：1K*1K*4KB=4GB4.二级索引地址是i.add(12)，文件大小为：1K*1K*1K*4KB=4TB所以文件的最大长度为：40KB+4MB+4GB+4TB例14：多级索引分配方式允许文件最大长度两级索引，盘块大小1KB、盘块号占4B，允许文件最大长度为多少？解析：由已知得一个索引块可含1KB/4B=256个盘块号，于是两级索引最多可含256*256=64K个盘块号，允许文件最大长度为64K*1KB=64MB例15：已知某系统中磁盘的每个盘块大小为1KB，外存分配方法采用中的混合索引结构，其中索引节点中直接地址6项，一级索引地址2项，二级索引地址1项，每个盘块号占用4个字节，请问该系统中允许