物理块号为1
（3）可得：物理地址 1*1024+990＝2014B 所存数据为3478
十四，若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。
（1）先来先服务（FCFS） （2）最短寻找时间优先调度（SSTF） （3）电梯调度法（SCAN） （4）单向扫描（循环扫描C－SCAN）
（1）40 → 20 → 44 → 40 → 4 → 80 → 12 → 76
20+24+4+36+76+68+64＝292，共移动292柱面，292*3＝876ms （2）40 → 40 → 44 → 20 → 12 → 4 → 76 → 80
0+4+24+8+8+72+4=120, 共移动120柱面，120*3＝360ms
（3）40 → 40 → 44 → 76 → 80 → 20 → 12 → 4
0+4+32+4+60+8+8＝116，共移动116柱面，116*3＝348ms or 40 → 40 → 20 → 12 → 4 → 44 → 76 → 80
0+20+8+8+40+32+4=112,共移动112柱面，112*3＝336ms
(4) 40 → 40 → 44 → 76 → 80 → 4 → 12 → 20 0+4+32+4+76+8+8=132, 共移动132柱面，132*3＝396ms
(C-SCAN算法总是从0号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后，立即快速返回到0号柱面。
约定：按教材的解释，C-SCAN算法磁头只移到每个方向上最远的道上，一旦在当前方向上没有请求了，磁头的移动方向就反过来。)
十五，考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分
别为3时，试问FIFO、LRU这两种置换算法的缺页次数各是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）
所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
当内存块数量为3时：
FIFO 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 6
2 2 2 1 1 1 2 2 2 7 7 7 1 1 1
3 3 3 5 5 5 1 1 1 6 6 6 3 3
发生缺页中断的次数为16。
LRU 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
1 1 1 4 4 5 5 5 1 1 7 7 2 2 2
2 2 2 2 2 6 6 6 3 3 3 3 3 3
3 3 1 1 1 2 2 2 2 6 6 1 6
发生缺页中断的次数为15。
十六，某移动臂磁盘的柱面由外向里顺序编号，假定当前磁头停在100号柱面且移动臂方向是向里的，现有如下表所示的请求序列在等待访问磁盘： 表 访问磁盘请求序列 请求次序 柱面号 1 190 2 10 3 160 4 80 5 90 6 125 7 30 8 20 9 140 10 25 回答下面的问题： ① 写出分别采用“最短查找时间优先算法”和“电梯调度算法”时，实际处理上述请求的次序。
）SSTF：100→90→80→125→140→160→190→30→25→20→10
SCAN：100→125→140→160→190→90→80→30→25→20→10
② 针对本题比较上述两种算法，就移动臂所花的时间（忽略移动臂改向时间）而言，哪种算法更合适？简要说明之。
SSTF：10+10+45+15+20+30+160+5+5+10＝310
SCAN：25+15+20+30+100+10+50+5+5+10＝270
SCAN更合适。
十七，有一个系统其内存容量为1024KB，有8个作业同时到达，各作业需要的内存量和运行时间如表所示。
作业编号 需要内存量（KB） 运行时间（S） A 140 3 B 80 1 C 100 3 D 60 2 E 50 1 F 30 3 G 15 2 H 20 3 假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行。试问：
令内存剩余空闲分区为K，容量为：
1024－（140+80+100+60+50+30+15+20）＝529（KB）
（1） 1S后，内存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？
首次适应算法：B → E → K
最佳适应算法：E → B → K
（2） 2S后，其内存空白区按上述两种算法如何链接？
首次适应算法：B → D+E → G → K
最佳适应算法：G → B → D+E → K
（3） 在（2）后，此时有一个作业I要求进入内存，它需要内存量为12KB，按上述
两种算法，将把哪一块空白区分给它？
首次适应算法：B 最佳适应算法：G
十八，某计算机系统的内存容量为128KB，对存储器采用可变分区的存储管理办法，现有3个作业(J1，J2，J3)在内存，其存储器的分配如图所示。
操作系统 J1 空闲区 J2 空闲区 J3 空闲区 0K 5K 20K 40K 50K 90K 100K 128K
(1)现有一个需要25KB存储空间的作业J4请求装入内存，若采用最先适应分配算法
来给J4分配空间。请给出装入J4后的内存分配表。
操作系J1 空闲J2 J4 空闲J3 空闲区 统 区 区 0K 5K 20K 4050K 75K 90100K 128K K K
(2)若采用最优适应算法来给J4分配空间，给出装入J4后的内存分配表。
操作系 J1 空闲区 J2 空闲区 J3 J4 碎片 统 0K
5K 20K 40K
50K 90K 100K 125K
128K
(3)在只有J1，J2，J3三个作业的情况下，J2运行结束撤离后，请给出J2撤离后的内
存分配表。
操作系J1 统 0K 5K 20K 空闲区 J3 90K 空闲区 100128K K
十九，某程序在逻辑地址100处有一条取数指令LOAD l，500，而500单元内存放数据51888。假设程序被分配到内存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应地址的变换过程。 (1)静态重定位。
(2)采用重定位寄存器实现动态重定位。
(3)采用页表映像(映射)方式，假定页面大小为100单元，其负表各页映射到50，51、
52，53，54，55，?，59物理页上。
二十，对于如下的页面访问序列： 1，2，3，4，1，2，5，1，2，3，4，5。当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少（画出详细过程）？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）
FIFO，3块空间 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 5 5 5 2 2 2 1 1 1 1 1 3 3 3 3 3 3 2 2 2 2 2 4 4 缺3页 4567次 89次 FIFO，4块空间 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 1 1 5 5 5 5 4 4 2 2 2 2 2 2 1 1 1 1 5 3 3 3 3 3 3 2 2 2 2 4 4 4 4 4 4 3 3 3 缺4页 5次 67次 89次 10次 LRU，3块空间 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 3 3 3 2 2 2 1 1 1 111 4 4 3 3 3 2 2 222 2 5 缺3页 45次 67次 8910次 LRU，4块空间
