计算机操作系统专升本复习题-计算题演示课件

操作系统专升本复习----计算题好好的计算题类型1：作业调度、进程调度算法好好的根据先来先服务、短作业优先、优先级、高响应比优先、轮转（RR）等调度算法求作业的执行顺序、作业的周转时间、带权周转时间、平均周转时间和平均带权周转时间。2008年（8分）：短作业优先、先来先服务调度算法2014年（7分） ：短作业优先调度算法2015年（8分） ：先来先服务、短作业优先调度算法2017年（10分）：先来先服务调度算法、抢占式优先级调度算法；2、请计算采用抢占式优先级调度算法时各个进程的平均周转时间和平均带权周转时间。进程

到达时间

执行时间(ms)

优先级好好的P1例01：在单机系3

统中，系统中3

各个进程到达就绪队列的时P2刻2、执行时6间和优先级（5越小者越高）如下表所示。假P3设4进程的调4度时间忽略不1计。P41、6

请给出采用5

FCFS、短作业2

优先调度算法时各个进程的P5调8度顺序，2并计算平均周4转时间和平均带权周转时间。平均周转时间：（3+7+9+12+12）/5=8.6平均带权周转时间：（1+1.17+2.25+2.4+6）/5=2.56好好的913312进08程到达时间执行时间(ms)优先级完成时间周转时间带权周转时间P711.17033P92.22521、FCFS调6度算法5P213.24441P6124652P58243平均周转时间：（3+7+3+11+14）/5=7.6平均带权周转时间：（1+1.17+2.25+2.4+6）/5=1.84好好的9111231进50程到达时间执行时间(ms)优先级完成时间周转时间带权周转时间17P.11703313P2.52短作业优先6调度算法5P1251.75824P1234.8441P46523平均周转时间：（3+18+4+7+7）/5=7.8平均带权周转时间：（1+3+1+1.4+3.5）/5=1.98好好的20831进53程到达时间执行时间(ms)优先级完成时间周转时间带权周转时间1P318033P4122、采用抢占6

式优先级调度5算法P71.3444173P4.5652P582431好好的29:10 45分钟

⑵

⑶

⑷3作业

例进2入：系在统时一间个单计算道时批间处理开始系时统间中，完成采时用间响应周比转高时间者优先的作业调度算法。当一个作业进入系统后就可以开始调度，假9定:0作0

业都6是0分仅钟计算，9:忽00

略调度10花:00费的时间⑴。现有三个作业，进入系统的时间和需要计算的时间如下表所示。作业2的5分开钟始时间⑸、完成时⑹间及周转时⑺间并填入求出9每:1个5表中。周转时间10:00⑴⑸⑹⑺作业响应进比入系=（统服时间务时计间算+时等间待时开间始时）间/服务完时成间时间=1+等（待分时钟间）/服务时间10:00计算作业2、3的响应比，如下：1

作业2响9:应00比：1+6500分/4钟5=2.119:00作业3响应比：1+45/25=2.82

作业3的9:响10应比高4，5分因钟此10:00⑵开始执行作⑶业3，10:⑷25完成。3

最后执9行:1作5

业2。25分钟6010:2511:1012010:0010:2570好好的计算题类型2：银行家算法好好的如果判断某时刻是否为安全状态采用安全性算法（若安全，执行安全性算法结束写明安全序列和系统状态是安全的）；如果某进程提出资源请求采用银行家算法（写清1、2、3、4步）。2008年（8分）、2011年、2012年、2013年最大需求

已分配好好的P3进程2013年真题例3：已知系统内A有三B个进程P1、P2、AP3共B享A、B两类资P1

源，A类资源的数3量为28，B类资源的数1量为15。设在T时刻资源分配情况如下表所示:P2

（1）问T时刻A、6B的可4

利用资源数分别4

是多0

少?（2）T时刻系统是3

否处1

于安全状态?为2什么1?计算题类型3：地址变换好好的动态可重定位分区分配的地址变换分页存储管理方式的地址变换分段存储管理方式的地址变换2012年（选择题1分）、2016年（10分）例4：（2012年真题）一个32位的虚拟地址分为4个域，每个域的长度分别为a、b、c、d位，其中d为页内地址，则系统最多可有（

B ）个虚拟页面。B.2a+b+cA.a+b+c

C.d

D.2d1.动态可重定位分区分配的地址变换例5：在分区存储管理中，已知某作业空间如图所示，采用动态重定位进行地址映射。假设分给该作业的主存空间起始地址为4000。指出在图中的地址1和地址2中，哪个是逻辑地址，哪个是物理地址？在图中填写出执行指令MOV

L1，[2000]时，所取数据“100”的逻辑地址、物理地址以及动态重定位寄存器的内容（用十进制表示）。在图中填写出指令“MOV L1，[2000]”的主存地址。+动态重定位寄存器0MOV

L1

[2000]100作业空间500200049990MOV

L1

[2000]100内存空间40009999地址1 地址2好好的储管理方式的地址变换例6：在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？解析

逻辑地址2F6AH的二进制：0010

1111

0110

1010：

由于逻辑地址长度为16位，页面大小为4096字节，即212，所以低方法1

12为表示页内地址所以页号为2，对应块号为11（二进制1011），因为块内地址=页内地址，所以物理地址表示如下：其二进制1011

1111

0110

1010，即BF6AH1010011011111

01102.1分1010页存页块号页块内地址好好的例6：在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？解析：方法2由于逻辑地址长度为16位，页面大小为4096字节，即212，所以低12为表示页内地址所以页号为2，对应块号为11（十六进制B），因为块内地址=页内地址，所以物理地址表示如下：所以，物理地址为BF6AH2B2BF6A页块号页块内地址好好的、3页分别分配的物理块号为5、10、4、7，给定虚拟地址093CH，请将其变换为物埋地址。逻辑地址093CH的二进制：0000

1001

0011

1100有已知得逻辑地址长度为15位，页面大小为1KB，即210，所以低10为表示页内地址所以页号为2，对应块号为4（二进制0100），因为块内地址=页内地址，所以物理地址表示如下：其二进制0001

0001

0011

1100，即113CH0001010

01010好好的01

00111100页块号例7：块页某内虚地址拟存储器的用户空间共有32个页面，每页1KB，内存16KB。假定某时刻系统为用户的第0、1、2解析：401234001350

5901938

95例1082：35在0一个段2式0

存储管理系统中，其段表为：试50求0

10下0

列逻辑地90址对应的物理地址是什么？430

2130.分段存500储管理方式的地址变换段2段231号5物内号0+理地413段址0地0内=内=越址26存3位4界60起0移始地址 段长好好的1350+400=1750解析：计算题类型4：分页存储的数据访问时间好好的例9：假定快表检索时间为20ns，内存访问时间为100ns。若能在快表中找到CPU给出的页号，CPU存取一个数据将需要的访问时间是多少？若不能在快表中找到CPU给出的页号，则为存取一个数据需要的访问时间是多少？若假定快表查找命中率为80%，则其有效访问时间为多少？解析：则若能在快表中找到CPU给出的页号，CPU存取一个数据将需要(20+100)=120ns。若不能在快表中找到CPU给出的页号，则为存取一个数据将需要(20+100+100)=220ns。若假定快表查找命中率为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。按最佳页面置换算法，计算缺页率。按先进先出页面置换算法，计算缺页率。按LRU页面置换算法，计算缺页率。好好的计算题类型6：磁盘调度算法好好的根据先来先服务、最短寻道时间优先、扫描算法、循环扫描算法，给出寻道顺序，并计算寻道总数和平均寻道长度。2008年（8分）：最短寻道时间优先、扫描算法例12：一个可移动磁头的磁盘具有200个磁道，其编号为0--199，当它刚刚结束了125道的存取后，现正在处理143道的请求，假设系统当前

I/0请求序列以FIFO顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几种磁盘调度算法而言，满足以上请求序列，磁头将如何移动？平均寻道长度是多少？先来先服务算法最短寻道时间优先算法SSTF扫描算法SCAN循环扫描算法好好的法FCFS好好的最短寻道时间优先算法SSTF从143号磁道开始被访问的先下一个磁道号来移先动服距离务算（磁道数）814675471457063191130526017072286894831951053618062458175783917370245平均寻道长度：51652/9=循环扫描算法CSCAN好好的从143号磁道开始被访问的扫下一个磁道号描移算动法距离SCAN（磁道数）14741503175251772183604971911025289483911023818360258平均寻道长度：12659/9=计算题类型7：索引分配与文件最大长度好好的计算索引文件最大长度、计算增量式文件最大长度。2011年例13（2011年真题）：简述在UNIX系统中采用混合索引方式。如果每个盘块大小是4KB，每个盘的地址要用4个字节，那么在UNIX系统中文件最大是多少？给出步骤说明。例13（2011年真题）：简述在UNIX系统中采用混合索引方式。如果每个盘块大小是4KB，每个盘的地址要用4个字节好好的，那么在UNIX系统中文件最大是多少？给出步骤说明。解析：由已知得每个盘块大小4KB，每个盘块号占4B，因此一个盘块内可以存放4KB/4B=1K个盘块。直接地址10项（i.add(0)-i.add(9)），可以存放10个盘块号，文件大小为10*4KB=40KB；一级索引地址是i.add(10)，存放1个索引表，1个索引表内含1K个盘块，文件大小为：1K*4KB=4MB二级索引地址是i.add(11)，文件大小为：1K*1K*4KB=4GB二级索引地址是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个盘块。直接地址6项，可以存放6个盘块号，文件大小为6*1KB=6KB；一级索引地址2项，每个存放1个索引表，1个索引表内含256个盘块，文件大小为：256*1KB*2=512KB二级索引地址1项，文件大小为：256*

256*1KB=64MB所以文件的最大长度为：6KB+512KB+64MB好好的计算题类型8：计算FAT的大小FAT所占存储空间=FAT中的表项数*每个表项所占存储空间计算步骤：求FAT中的表项数：磁盘大小/盘块大小求FAT中每个表项所占存储空间(是半个字节的整数倍)3例.1求6F：AT有的一大个小大小为500M的硬盘，盘块的大小为1KB,试计算其FAT的大小。求FAT中的表项数：500MB/1KB=500K求FAT中每个表项所占存储空间256K<500K<=512K所以每个表项所占19位，扩展为20位，即2.5好B好的3.求FAT的大小=500K*2.5B=1250KB例17：假定盘块的大小为1KB，硬盘的大小为10GB，采用显示链接分配方式时，请问文件分配表只是占用多大空间？好好的计算题类型9：查找与磁盘启动次数例18：假定每次启动磁盘只装入一个目录盘块 盘块大小1KB，文件目录共3200个FCB 引入索引结点前 FCB占64B，查找一个文件平均需启动磁盘次数为多少？引入索引结点后 FCB占16B(文件名和索引结点指针分别占用14B和2B)，查找一个文件平均需启动磁盘次数为多少？解析：由已知得每盘块中包含1KB

/64B=16个FCB，文件目录共需占用3200/16=200个盘块，故查找一个文件平均需启动磁盘100.5次(顺序查找).引入索引结点后，每盘块包含1KB/16B=64个目录项，文件目录共需占用3200/64=50个盘块，故查找一个文件平均需启动磁盘25.5次(顺序查找，读索引结点取地址信息只需一次，因为索引结点在外存上是连续存放的)好好的计算题类型10：位示图中盘块的分配和回收0

1

2

3

4

5

6

7

8

910

11

12

13

14