文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
（2）P2提出请求Request2(1,2,2,2),按银行家算法进行检查： Request2(1,2,2,2)≤Need2(2,3,5,6) Request2(1,2,2,2)≤Available(1,6,2,2) 试分配并修改相应数据结构，资源分配情况如下：
Allocation Need Available 进 程 A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 0 4 0 0 P1 1 0 0 0 1 7 5 0 P2 2 5 7 6 1 1 3 4 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 再利用安全性算法检查系统是否安全,可用资源Available (0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。
3某请求分页系统，用户空间为32KB，每个页面1KB，主存16KB。某用户程序有7页长，某时刻该用户进程的页表如下： 页号 0 1 2 3 4 5 6 物理块号 8 7 4 10 5 3 2 是否在TLB 是 是 否 否 否 是 是 （1）计算两个逻辑地址：0AC5H、1AC5H对应的物理地址。
（2）已知主存的一次存取为1.5us，对于TLB表（快表）的查询时间可以忽略，则访问上述两个逻辑地址共耗费多少时间？
答 （1） 每页1kb代表页内偏移量为低地址10位，剩余的为页号，所以0AC5H对应的页号为2，物理块为4，说以物理地址为12C5H, 同理可得1AC5H对应的物理地址为0AC5H.
（2）耗时为1×1.5us+2×1.5us=4.5us
4什么叫重定位？它有哪两种方式？这两种方式有什么区别？
由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据
5
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
5在具有快表的段页式存储管理方式中，如何实现地址变换？
答：物理地址=该段在主存的起始地址+页框号*大小+页内地址。
第二次作业：
1、 在某请求分页管理系统中，一个作业共5页，作业执行时一次访问如下页面：1，4，3，
1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为3，分别采用FIFO，LRU，Clock页面置换算法，试求出缺页中断的次数及缺页率。 答 FIFO 缺页次数为9，缺页率为3/4
LRU缺页数为9，缺页率为3/4 Clock缺页数为9，缺页率为3/4
2、 某请求分页管理系统，假设进程的页表如下： 页号 0 1 2 页框号 101H — 254H 有效位 1 0 1 装入时间 2 — 4 页面大小为4KB，一次内存的访问时间为100纳秒（ns），一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为100毫秒（已含更新TLB和页表的时间），进程的驻留集大小固定为2个页框，采用FIFO法置换页面。假设1）TLB初始为空；2）地址转换时，先访问TLB，若TLB未命中时再访问页表（忽略TLB更新时间）；3）有效位为0表示页面不在内存中。 请问：
（1）该系统中，一次访存的时间下限和上限各是多少？（给出计算过程）
（2）若已经先后访问过0、2号页面，则虚地址1565H的物理地址是多少？（给出计算过程）
答（1）一次访存时间下限10ns+100ns+100ns，上限10ns+100ns+100ms+100ns
（2）基于上述访问序列，当访问虚地址1565H时产生缺页中断，合法驻留集为2，必须从表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H
3、设某计算机的逻辑地址空间和物理地址空间均为128KB，按字节编址。若某进程最多需要6页数据存储空间，页面大小为1KB，操作系统采用固定分配局部置换策略为该进程分配4个页框（物理块）。在时刻300前该进程各页面的访问情况如下表所示：
页号 0 1 2 3 页框号（块号） 7 4 2 9 装入时间 130 230 200 180 6
访问位 1 1 1 1 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
当进程执行到时刻300时，要访问逻辑地址为17CAH的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？
（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。设搜索下一页的指针顺时针方向移动，且当前指向2号页框，示意图如下：
9号页框2号页框3号页2号页
17CAH=(0001 0111 1100 1010)2
（1）页大小为1K，则页内偏移地址为10位，前6位是页号，所以逻辑地址对应的页号为：5
（2）FIFO：被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2=1FCAH
（3）CLOCK：被置换的页面所在页框为2，所以对应的物理地址为（0000 1011 1100 1010）2=0BCAH
并有一下请求序列等待访问磁盘：
请求序列： 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 预访问柱面号：150，50 ，178，167 ，87，43 ，23 ，160 ，85
试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述请求的次序 第一题：序列（柱面号） 最短寻找时间优先算法
9(85)、5(87)、2(50)、6(43)、7(23)、1(150)、8(160)、4(167)、3(178) 电梯调度算法
9(85)、5(87)、1(150)、8(160)、4(167)、3(178)、2(50)、6(43)、7(23)
第二题：
磁盘有199个磁道，当前磁头在54#磁道上，并向磁道号减小的方向上移动，现有一下请求序列等待访问磁盘：
请求序列 1 2 3 4 5 6 7 8 带访问的柱面号 99 184 38 123 15 125 66 68 试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述请求的次序，并计算出他们的平均寻道长度 第二题：序列（柱面号） 最短寻找时间优先算法
7(66) 8(68) 3(38) 5(15) 1(99) 4(123) 6(125) 2(184)
7
7号页框0号页1号页4号页框文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
12+2+30+23+84+24+2+59=236 平均寻道长度236/8=29.5 电梯调度算法
3(38) 5(15) 7(66) 8(68) 1(99) 4(123) 6(125) 2(184) 16+23+51+2+31+24+2+59=208 平均寻道长度208/8=26
四、计算题
1、假定在单CPU条件下有下列要执行的作业：
作业 1 2 3 运行时间 10 4 3 优先级 2 3 5
作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。
（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。
（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？
（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？ 1．解：
(1) 非抢占式优先级算法（3分）
作业1 作业3 作业2
| | | | t 0 10 13 17
(2) 和（3） 作业 1 2 3 到达时间 运行时间 0 1 2 10 4 3 完成时间 10 17 13 2.9 周转时间 10 16 11 12.3 带权周转时间 1.0 4.0 3.7 平均周转时间 平均带权周转时间
2、若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行 时间为a、b、c，且满足a 作业周转时间。 2．证明：采用短作业优先算法调度时，三个作业的总周转时间为： T1=a+(a+b)+(a+b+c)=3a+2b+c ① 若不按短作业优先算法调度，不失一般性，设调度次序为：J2、J1、J3。则三个作业的 总周转时间为： T2=b+(b+a)+(b+a+c)=3b+2a+c ② 8