4004 (R3) B(R1) Access B[i] using index register R1 4005 (R3) (R3) + C(R1) Add C[i] using index register R1 4006 A(R1) (R3) Store sum in A[i] using index register R1 4007 (R1) (R1) + ONE Increment i 4008 branch 4002 6000-6999 storage for A 7000-7999 storage for B 8000-8999 storage for C 9000 storage for ONE 9001 storage for n 8.10

?假设需要i级，则可以表示的地址空间大小 ?=

?要求表示64位地址空间，则要求10i+12>=64，所以i至少取6

?8.11 ?a. 400ns

?b. 15%*420+85%*220=250

?8.12

?a. 缺页下限=n ?b. 缺页上限=p

?8.17

?a. 每段的最大尺寸=8*2K=16K

?b. 该任务的逻辑地址空间最大=4*16K=64K

?c. 逻辑地址格式是：2位表示段号，3位表示页号，其他11位表示页内偏移。最后的11

位转换为十六进制为2BC

?8.18

?a. 逻辑地址格式是：前5位表示页号，后11位表示页内偏移。 ?b. 页表长度：25=32个条目；页表宽度：20-11=9位。 ?c. 页表宽度由9位变为8位。

9.1 每个方块表示一个执行单元，方块中的数字表示当前执行的进程。 FCFS RR, q = 1 RR, q = 4 SPN SRT HRRN A A A B B B B B C C D D D D D E E E E E A B A B C A B C B D B D E D E D E D E E A A A B B B B C C B D D D D E E E E D E A A A C C B B B B B D D D D D E E E E E A A A C C B B B B B D D D D D E E E E E A A A B B B B B C C D D D D D E E E E E Feedback, q = 1 A B A C B C A B B D B D E D E D E D E E Feedback, q = 2i A B A A C B B C B B D D E D D E E D E E FCFS RR, q = 1 RR, q = 4 SPN SRT HRRN A A A B B B B B C C D D D D D E E E E E A B A B C A B C B D B D E D E D E D E E A A A B B B B C C B D D D D E E E E D E A A A C C B B B B B D D D D D E E E E E A A A C C B B B B B D D D D D E E E E E A A A B B B B B C C D D D D D E E E E E Feedback, q = 1 A B A C B C A B B D B D E D E D E D E E Feedback, q = 2i A B A A C B B C B B D D E D D E E D E E 9.7

首先，调度器计算在时间t+r1+r2+r3时刻的响应 比，此时，三个作业都已经完成。这个时候第三个 作业具有最小的响应比（图中可以看出），所以， 调度器决定最后执行第三个作业；继续查看在时间 t+r1+r2时，第一和第二个作业都已完成，此时， 第一个任务的响应比要小些，所以，在时间t的时 候第二个作业被选择执行,既执行顺序为r2,r1,r3。 这个算法在每完成一个作业之后重新查看作业的响

应比，跟高响应比优先算法是有区别的，如果是后 者那么在时间t的时候就会选择第一个作业。 9.14

?在多级反馈队列调度器的调度下，I/O-bound的进程比CPU-bound的进程更有利，也就是

说，调度器更倾向于选择I/O-bound的进程进行分派。原因在于I/O-bound的进程会比较长时间地阻塞；在阻塞过程中，CPU-bound的进程得到多次分派执行，因而会很快进入低优先级的反馈队列中。这样，I/O-bound的进程被唤醒之后，通常具有比CPU-bound的进程高得多的优先级，所以会得到调度器的“青睐”。 9.16 11.3

第二问，如果沿着磁道号增大的方向移动，则只有扫描算法和循环扫描算法需要改变。 11.8 a.

物理块大小=（10逻辑记录/物理记录）*（120字节/逻辑记录）=1200字节 物理块长度=1200字节/（1600字节/寸）=0.75寸 传输时间=0.75/120+0.6/60=0.01625 块数量=2400*12/（0.75+0.6）=21333 花费的时间=21333*0.01625=346（s） b.

物理块大小=（30逻辑记录/物理记录）*（120字节/逻辑记录）=3600字节 物理块长度=3600字节/（1600字节/寸）=2.35寸 传输时间=2.35/120+0.6/60=0.02875 块数量=2400*12/（2.35+0.6）=10105 花费的时间=10105*0.02875=291（s）

c.对于a，物理块为21333，逻辑记录=10*21333=213330 对于b，物理块为10105，逻辑记录=30*10105=303150 d.对于a,

r=（213330个记录*120个字节/记录）/346秒 = 73987字节/秒 对于b，

r=（303150个记录*120个字节/记录）/291秒 = 125010字节/秒

e.对于a，

容量=213330个记录*120字节/记录 = 25599600字节 对于b，

容量=303150个记录*120字节/记录 =36378000字节

11.10

每个扇区有512个字节，每个字节产生一次中断，那么就有512次中断，总共的中断处理时间=2.5*512=1280us.

磁盘旋转速度为360r/m=6r/s，既转一圈要1/6秒。 所以，读一个扇区的时间

=（1/6s）/（96扇区/磁道）=0.001736s =1736us

处理器花费在处理I/O上的时间百分比 =1280/1736=74% 12.3 a.索引

b.索引顺序 c.哈希或索引 12.6

?a

?可以，一种简单的方式是：首先，建立一个数据结构以表示文件系统所在磁盘的所有块。

然后，从文件系统的根目录开始遍历整个系统，并为每个文件所使用的每个块在前述数据结构中打上标记。最后，当遍历完成，没有被打上标记的块既为空闲块。

?b

?可以使用空闲空间链的备份链。

12.7

?a

?一个磁盘块的大小是8K，每个磁盘块指针是32位，则，一个磁盘块中可以容纳的块指针

数=8*1024*(8/32)=2048

?因

此，最大文件的大小

=12*8K+2048*8K+2048*2048*8K+2048*2048*2048*8K=96K+16M+32G+64T

?b

? ?8K=16M?8K=128G

?c

?地址12,423,956大约在11M的范围内，需要用到单重链接。所以需要两次磁盘访问。