计算机操作系统专升本复习题计算题.ppt

操作系统专升本复习-计算题.计算题类型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:0029:1045分钟39:1525分钟例2：在一个单道批处理系统中，采用响应比高者优先的作业调度算法。当一个作业进入系统后就可以开始调度，假定作业都是仅计算，忽略调度花费的时间。现有三个作业，进入系统的时间和需要计算的时间如下表所示。求出每个作业的开始时间、完成时间及周转时间并填入表中。.作业进入系统时间计算时间开始时间完成时间周转时间（分钟）19:0060分钟9:0010:0029: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年.进程进程最大最大需求需求已已分配分配 A B A B P1 3 2 1 1 P2 6 4 4 0P3 3 1 2 12013年真题例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+c B.2a+b+c C.d D.2d.1.动态可重定位分区分配的地址变换例5：在分区存储管理中，已知某作业空间如图所示，采用动态重定位进行地址映射。假设分给该作业的主存空间起始地址为4000。（1）指出在图中的地址1和地址2中，哪个是逻辑地址，哪个是物理地址？（2）在图中填写出执行指令MOV L1，2000时，所取数据“100”的逻辑地址、物理地址以及动态重定位寄存器的内容（用十进制表示）。（3）在图中填写出指令“MOV L1，2000”的主存地址。+动态重定位寄存器0MOV L1 2000100作业空间500200049990MOV L1 2000100内存空间4000 9999地址1地址2 .例6：在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？2.分页存储管理方式的地址变换解析：方法1逻辑地址2F6AH的二进制：0010 1111 0110 1010由于逻辑地址长度为16位，页面大小为4096字节，即212，所以低12为表示页内地址所以页号为2，对应块号为11（二进制1011），因为块内地址=页内地址，所以物理地址表示如下：其二进制1011 1111 0110 1010，即BF6AH00101111 0110 1010页号页内地址1011 1111 0110 1010块号块内地址.例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的二进制：0000 1001 0011 1100有已知得逻辑地址长度为15位，页面大小为1KB，即210，所以低10为表示页内地址所以页号为2，对应块号为4（二进制0100），因为块内地址=页内地址，所以物理地址表示如下：其二进制0001 0001 0011 1100，即113CH0000 1001 0011 1100 页号页内地址0001 0001 0011 1100 块号块内地址解析：.段号内存起始地址段长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.8 B.9 C.7 D.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.最短寻道时间优先算法SSTF 3.扫描算法SCAN 4.循环扫描算法.先来先服务算法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个字节，请问该系统中允许的文件最大长度是多少？解析：由已知得每个盘块大小1KB，每个盘块号占4B，因此一个盘块内可以存放1KB/4B=256个盘块。1.直接地址6项，可以存放6个盘块号，文件大小为 6*1KB=6KB；2.一级索引地址2项，每个存放1个索引表，1个索引表内含256个盘块，文件大小为：256*1KB*2=512KB3.二级索引地址1项，文件大小为：256*256*1KB=64MB所以文件的最大长度为：6KB+512KB+64MB.计算题类型8：计算FAT的大小例16：有一个大小为500M的硬盘，盘块的大小为1KB,试计算其FAT的大小。计算步骤：1.求FAT中的表项数：磁盘大小/盘块大小 2.求FAT中每个表项所占存储空间(是半个字节的整数倍)3.求FAT的大小 FAT所占存储空间=FAT中的表项数*每个表项所占存储空间1.求FAT中的表项数：500MB/1KB=500K2.求FAT中每个表项所占存储空间 256K500K=512K 所以每个表项所占19位，扩展为20位，即2.5B3.求FAT的大小=500K*2.5B=1250KB.例17：假定盘块的大小为1KB，硬盘的大小为10GB，采用显示链接分配方式时，请问文件分配表只是占用多大空间？.计算题类型9：查找与磁盘启动次数例18：假定每次启动磁盘只装入一个目录盘块盘块大小1KB，文件目录共3200个FCB引入索引结点前FCB占64B，查找一个文件平均需启动磁盘次数为多少？引入索引结点后FCB占16B(文件名和索引结点指针分别占用14B和2B)，查找一个文件平均需启动磁盘次数为多少？解析：1.由已知得每盘块中包含1KB/64B=16个FCB，文件目录共需占用3200/16=200个盘块，故查找一个文件平均需启动磁盘100.5次(顺序查找).2.引入索引结点后，每盘块包含1KB/16B=64个目录项，文件目录共需占用3200/64=50个盘块，故查找一个文件平均需启动磁盘25.5次(顺序查找，读索引结点取地址信息只需一次，因为索引结点在外存上是连续存放的).计算题类型10：位示图中盘块的分配和回收教材276页第14题0123456789101112131415011111111111111111111111111111111121101111111111111311111101111011114000000000000000056例19：有一计算机系统采用如下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从0开始编号，每个盘块的大小为1KB。1.现要为文件分配两个盘块，试具体说明分配过程。2.若要释放磁盘的第300块，应如何处理？.解析：1.盘块的分配过程根据位示图进行盘块分配时，可分三步进行：(1)顺序扫描位示图，从中找出两个值为“0”的二进制位分别为map2,2和map3,6。(2)将所找到的两个二进制位转换成与之相应的盘块号。其相应的盘块号应按下式计算：b=16*i+j map2,2对应的盘块号为：34 map3,6对应的盘块号为：54(3)修改位示图，令map2,2=1，map3,6=1。.2.盘块回收的过程盘块的回收分两步：(1)将回收盘块的盘块号300转换成位示图中的行号和列号。转换公式为：i=bDIV16j=bMOD 16所以300号盘块对应的行号和列号分别是18和12。(2)修改位示图。令map18,12=0。.