11
第4 章 习题答案
4-14 内存有如下顺序排列的空闲块：10K，40K，20K，18K，7K，9K，12K和15K，有如下的请求序列：12K，10K，9K。 （1）若采用首次适应法：
? 12K的请求：将分配40K的空闲块， 40K变为剩余的（40-12）K=28K，空闲队
列变为：10K，28K，20K，18K，7K，9K，12K和15K；
? 10K的请求：将分配10K的空闲块，空闲队列变为：28K，20K，18K，7K，9K，
12K和15K；
? 9K的请求：将分配28K的空闲块，空闲队列变为：（28-9）=18K，20K，18K，
7K，9K，12K和15K； （2）若采用最佳适应法：
? 12K的请求：将分配12K的空闲块，空闲队列变为：10K，40K，20K，18K，7K，
9K和15K；
? 10K的请求：将分配10K的空闲块，空闲队列变为：40K，20K，18K，7K，9K，
12K和15K；
? 9K的请求：将分配9K的空闲块，空闲队列变为： 40K，20K，18K，7K， 12K
和15K；
（3）若采用最坏适应法：
? 12K的请求，将分配40K的空闲块，空闲队列变为：10K，28K，20K，18K，7K，
9K和15K；
? 10K的请求：将分配28K的空闲块，空闲队列变为： 20K，18K，7K，9K，12K
和15K；
? 9K的请求：将分配20K的空闲块，空闲队列变为：10K，18K，11K， 18K，7K，
12K和15K。
4-15 有如下图所示的页表中的虚地址与物理地址之间的关系，即该进程分得6个内存块。页的大小为4096。给出对应下面虚地址的物理地址：(1)20； (2) 5100； (3) 8300； (4) 47000. 0 1 2 3 4 5 6 7 2 1 6 0 4 3 x x 解：
（1）虚地址 20变为页号0 和页内偏移20
由页号查页表得0页对应内存块号为2 ，可计算得 物理地址=块号*页的大小+页内偏移=2*4096+20=8212 （2）虚地址 5100变为页号1 和页内偏移1004（5100/4096）
12
由页号查页表得1页对应内存块号为1 ，可计算得 物理地址=块号*页的大小+页内偏移=1*4096+1004=5100 （3）虚地址 8300变为页号2 和页内偏移108
由页号查页表得2页对应内存块号为6 ，可计算得 物理地址=块号*页的大小+页内偏移=6*4096+108=24684 （4）虚地址 47000变为页号11 和页内偏移1944 11＞7 页号越界
4-16?一个作业在执行过程中，按如下顺序依次访问各页，作业分得四个主存块，问分别采用FIFO、LRU和OPT算法时，要产生多少次缺页中断?设进程开始运行时，主存没有页面。
页访问串顺序为：0 1 7 2 3 2 7 1 0 3 2 5 1 7 （1）FIFO
0 1 7 2 3 2 7 1 0 3 2 5 1 7
0 1 7 2 3 3 3 3 0 0 0 5 1 7
0 1 7 2 2 2 2 3 3 3 0 5 1
0 1 7 7 7 7 2 2 2 3 0 5
0 1 1 1 1 7 7 7 2 3 0
F F F F F S S S F S S F F F
采用FIFO淘汰算法，产生9次缺页中断。
（2）LRU
0 1 7 2 3 2 7 1 0 3 2 5 1 7
0 1 7 2 3 2 7 1 0 3 2 5 1 7
0 1 7 2 3 2 7 1 0 3 2 5 1
0 1 7 7 3 2 7 1 0 3 2 5
0 1 1 1 3 2 7 1 0 3 2
F F F F F S S S F F F F F F
采用LRU算法时，产生11次缺页中断。
4-17 考虑如图所示的段表，给出如下所示的逻辑地址所对应的物理地址。
13
段始址 219 2300 92 1326 1954
段的长度 600 14 100 580 96 （1）0，430 ? 219+430=649 （2）1，10 ? 2300+10=2310
（3）2，500 ? 500＞100段内地址越界 （4）3，400 ? 1326+400=1726
（5）4，112 ? 112＞96 段内地址越界
4-18 一台计算机含有65536字节的存储空间，这一空间被分成许多长度为4096字节的页。有一程序，其代码段为32768字节，数据段为16386字节，栈段为15870字节。试问该机器的主存空间适合这个作业吗?如果每页改成512字节，适合吗? 答： （1）
存储空间每块为4096个字节，共可分成16块。
程序代码段占32768/4096=8块，数据段占16386/4096=5块，栈段占15870/4096=4块，合计为8+5+4=17块，故该机器的主存空间不适合这个作业。
（2）
当存储空间每块为512个字节，共可分成128块。
程序代码段占32768/512=64块，数据段占16386/512=33块，栈段占15870/512=31块，合计为64+33+31=128块，故该机器的主存空间是适合这个作业的。
4-19 逻辑地址中，用9位表示页号，用10位表示页内地址。
4-20 （1）缺页中断50次； 5000次 （2）缺页中断100次； 10000次
4-21 0.9×(0.75×1+0.25×8)+0.10×(8+5000+8)+8
4-23 8192/4=2048 64=7+11+11+11+11+13 5级页表
第5章 文件系统
5-9.? 文件存贮空间管理可采用成组自由块链表或位示图。若一磁盘有B个盘块，其中有F个自由块。若盘块号用D位表示。试给出使用自由块链表比使用位示图占用更少的空间的条件。当D为16时，给出满足条件的自由空间占整个空间的百分
14
比。
解：一磁盘有B个盘块，用位图表示要使用B位
现有F个自由块，若表示一个盘块需用D位。则采用链表接连F个盘块，需要F个链指针，共占F*D位。使用自由块链表比使用位示图占用更少的空间的条件是F*D 当D=16时，满足条件的自由空间占整个空间的百分比为 F/B<1/16=6.25%。 5-10.? 文件系统的执行速度依赖于缓冲池中找到盘块的比率。假设盘块从缓冲池读出用1毫秒，从盘上读出用40毫秒。从缓冲池找到盘块的比率为n，请给出一个公式计算读盘块的平均时间，并画出n从0到1.0的函数图像。 解：读一个盘块的平均时间=n+40(1-n)=40-39n 40 1 n 0 1 5-13. 1574/256=6……38， 因此，要访问文件的第7个记录内的38B处。每个块放两个记录，所要访问的字节处在第4个逻辑块内，其对应的物理块号为4，应访问4号块内的第38个字节。要访问4次磁盘才能将该字节的内容读出。 5-14．共需要4次磁盘操作 3014301416 5-15．1GB=2 ，16KB=2 ， 2/2 =2 ，每个磁盘块号需要2个字节表示，即2B。 （1）10KB<16KB, 所以，只占用1个磁盘块。 （2）1089KB/16KB=69 需一个索引块和69个数据块，共70个盘块。 （3）129MB/16KB=8256 ， 16KB/2B=8K（个索引项）<8256 所以，需2个一级索引表和一个1个二级索引表，8256个数据块。 共需8259个磁盘块。 第6章 设备管理 6-6．下列工作各是在四层I/O软件的哪一层上实现的?? 15 (1) 对于读磁盘，计算柱面、磁头和扇区?（设备驱动） (2) 维持最近所用块而设的高速缓冲?（独立于设备的软件层） (3) 向设备寄存器写命令?（设备驱动） (4) 查看是否允许用户使用设备?（独立于设备的软件层） (5) 为了打印，把二进制整数转换成ASCII码?（用户进程） 6-13．假设移动头磁盘有200个磁道(从0号到199号)。目前正在处理143号磁道上的请求，而刚刚处理结束的请求是125号，如果下面给出的是按到达时间的先后排成的等待服务队列：86，147，91，177，94，150，102，75，130。那么，用下列各种磁盘调度算法来满足这些请求所需的总磁头移动量是多少?? (1) FCFS：125 143--86--147--91--177--94--150--102--75--130 满足这些请求所需的总磁头移动量=（143-86）+（147-86）+（147-91）+（177-91）+（177-94）+（150-94）+（150-102）+（102-75）+（130-75）=57+61+56+86+83+56+48+27+55=524 (2) SSTF：125 143--147--150--130--102--94--91--86--75--177 满足这些请求所需的总磁头移动量 =(150-143)+(150-75)+(177-75)=7+75+102=182 (3)SCAN：125 143--147--150--177--199--130--102--94--91--86--75 满足这些请求所需的总磁头移动量= (199-143)+(199-75)=56+124=180 (5)C-SCAN：125 143--147--150--177--199--0--75--86--91-94—102 --130满足这些请求所需的总磁头移动量=(199-143)+（199-0）+（130-0）=56+199+130=385 (4)C-LOOK：125 143--147--150--177--75--86--91--94--102--130 满足这些请求所需的总磁头移动量 =(177-143)+(177-75)+(130-75)=33+102+55=190 16