内存块数 3

置换算法 FIFO 16

LRU 15

OPT

11 (3’)

2考虑下面存储访问序列，该程序大小为460字：10，11，104，170，73，309，185，245，

246，434，458，364 设页面大小是100字，请给出该访问序列的页面走向。又设该程序基本可用内存是200字，采用FIFO置换算法，求出缺页率。如果采用LRU算法，缺页率是多少？如果采用最优淘汰算法，其缺页率又是多少？ 解:

该序列的页面走向为：0、1、0、3、1、2、4、3。 (1’) FIFO 0 1 0 3 1 2 4 3 0 0 0 3 3 3 4 2 1 1 1 1 2 2 3 × × × × × × (2’)

LRU 0 1 0 3 1 2 4 3 0 0 0 0 1 1 4 4 1 1 3 3 2 2 3 × × × × × × × (2’)

OPT 0 1 0 3 1 2 4 3 0 0 0 3 3 3 3 3 1 1 1 1 2 4 4 × × × × × (2’)

算法 FIFO LRU OPT 缺页次数 6 7 5 缺页率 6/12=0.5 7/12=0.583 5/12=0.417 (3’)

3设某页系统中，页帧大小为100字。一个程序大小为1200字，可能的访问序列如下： 10，205，110，735，603，50，815，314，432，320，225，80，130，270

系统采用LRU算法。当为其分配4个主存块时，给出该作业驻留的各个页的变化情况及页故障数。 答：

首先将逻辑地址变换成页号。这样10，205，110，735，603，50，815，314，432，320，225，80，130，720，通过除以页的大小100，页号分别为0，2，1，7，6，0，8，3，4，2，0，1，2。(3’)

系统为运行进程分配4个主存块，采用LRU算法，因此可以列表给出进程的缺页情况： 0 2 1 7 6 0 8 3 4 3 2 0 1 2

0

2

1

7

6

0

8

3

4

3

2

0

1

2

0 2 1 7 6 0 8 3 4 3 2 0 1 0 2 1 7 6 0 8 8 4 3 2 0 0 2 1 7 6 0 0 8 4 3 3 F F F F F F F F F S F F F S (5’)

由上表可见，被淘汰的页依次为0，2，1，7，6，0，8，4。缺页次数为12次 (2’)

4某请求页式管理系统，用户编程空间有40个页面，每个页面为200H字节。假定某时刻用户页表中虚页号和物理块号对照表如下： 虚页号 0 2 5 17 20 物理块号 5 20 8 14 36

求虚地址0A3CH、223CH分别对应的物理地址。 答：

虚地址0A3CH转换成十进制数为2620，每个页为200H，即512B，由2620/512可得，页号为5，页内地址为60。查页表可知，其主存块号为8。(3’) 因此地址为2620的物理地址为：8*512+60=4156。(2’)

虚地址223CH转换成十进制数为8762，由8762/512可得，其页号为17，页内地址为58。查页表可知，其主存块号为14。(3’)

因此地址为8762的物理地址为14*512+58=7226。(2’)

5某系统采用页式存储管理策略，拥有逻辑空间32页，每页2KB；拥有物理空间1MB。 1） 写出逻辑地址的格式

2） 若不考虑访问权限位，进程的页表有多少项？每项至少多少位？ 3） 如果物理空间减少一半，页表结构应作怎样的改？ 答：

1）逻辑空间32页，占5个二进制位。每页2KB，占11位。故描述逻辑空间需要16位(2’)。 15 … 11 10 … 0

逻辑地址的格式：[ | ] (1’)

2)进程的页表有32项，每项的位数由主存的分块数决定(2’)。1MB的空间可划分为512个2KB的块，每个块用9个二进制位表示(2’)。

3）如果物理空间减少一半时，主存地址需要19位表示，仍大于逻辑空间的大小，故页表结构可以不变。(3’)

6有一虚拟存储系统，采用先进先出（FIFO）的页面淘汰算法。在主存忠为每一个作业进程开辟3页。某作业运行中使用的操作数所在的页号依次为：4，3，2，1，4，3，5，4，3，2，1，5。

1） 该作业运行中总共出现多少次缺页？

2） 若每个作业进程在主存拥有4页，又将产生多少次缺页？ 3） 如何解释所出现的现象？ 解：

先进先出算法的实质是：总是选择作业中在主存驻留时间最长的一页进行淘汰。 若在主存中为每一作业进程开辟3页，对于题中的页面访问过程，其页面调度过程如下所示

4 3 2 1 4 3 5 4 3 2 1 5

页面1 页面2

4

4 3

4 3

1 3

1 4

1 4

5 4

5 4

5 4

5 2

5 2

5 2

页面3 2 2 2 3 3 3 3 3 1 1 缺页中断 F F F F F F F F F (3’) 1） 该作业运行中总共出现9次缺页(1’)

2） 在主存拥有4页，又将产生10次缺页(1’)。其页面调度过程见下图：

4 3 2 1 4 3 5 4 3 2 1 5

页面1 4 4 4 4 4 4 5 5 5 5 1 1 页面2 3 3 3 3 3 3 4 4 4 4 5 页面3 2 2 2 2 2 2 3 3 3 3 页面4 1 1 1 1 1 1 2 2 2 缺页中断 F F F F F F F F F F (3’)

3)从这个例子可以看出，当主存中为每一作业进程开辟4页时，出现了缺页次数反而增加的现象。这种现象称为Belady现象。(2’)

7关于存储管理，试问： （1） 在分页、分段和段页式存储管理中，当访问一条指令或数据时，需要访问内存几次？

各做什么处理？

（2） 假设一个分页存储系统具有快表，多数活动页表都可以存在其中，页表放在内存中，

内存访问时间是1us。若快表的命中率是85%，快表的访问时间为0.1us，则有效存取时间为多少？若快表命中率为50%，那么有效存取时间为多少？

解答：（1）分页需要访问2次，第一次访问页表，第二次执行访内操作(2’)；分段需要访问2次，第一次访问段表，第二次执行访内操作；段页式需要访问3次，第一次访问段表，第二次访问页表，第三次执行访内操作(2’)。

（2）当快表的命中率为85%时，执行一次访内操作需要的时间： T=1*0.85+2*(1-0.85)=1.15(us) (3’)

当快表的命中率为50%时，执行一次访内操作需要的时间： T=1*0.5+2*(1-0.5)=1.5(us) (3’)

8在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：

（1）按FIFO调度算法将产生多少次缺页中断，依次淘汰的页号为多少，缺页中断率为多少。 （2）按LRU调度算法将产生多少次缺页中断，依次淘汰的页号为多少，缺页中断率为多少。 答：

页面走向为：1，2，1，0，4，1，3，4，2，1

（1）按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为：0，1，2； 缺页中断率为：5/10=50% (3’) 1 2 1 0 4 1 3 4 2 1 0 0 0 0 0 4 4 4 4 4 4 1 1 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 1 × × × × × (2’)

（2）按LRU调度算法将产生6次缺页中断；依次淘汰的页号为：2，0，1，3； 缺页中断率为：6/10=60% (3’)

0 1 0 1 × 2 0 1 2 × 1 0 1 2 0 0 1 2 4 0 1 4 × 1 0 1 4 3 3 1 4 × 4 3 1 4 2 3 2 4 × 1 3 2 1

× (2’)

9一台计算机含有65536字节的存储空间，这一空间被分成许多长度为4096字节的页。有一个程序，其代码段为32768字节，数据段为16386字节，栈段为15870字节。试问该机器的主存空间适合这个进程吗？如果将每页改成512字节，合适吗？ 答：

当存储空间每块为4096B时，共可分成16块。其中： 程序代码段占：32768/4096=8块； (1’) 数据段占：16386/4096=5块； (1’) 栈段占：15870/4096=4块； (1’) 合计为：8+5+4=17块； (1’)

故该机器的主存空间不适合这个作业。 (1’)

当存储空间每块为512B时，共可分成128块。其中： 程序代码段占：32768/512=64块； (1’) 数据段占：16386/512=32块； (1’) 栈段占：15870/512=31块； (1’) 故合计为：64+32+31=127块。 (1’)

故该机器的主存空间是适合这个作业的。 (1’)

10一个请求分页系统中，内存的读/写周期为8纳秒，当配置有快表时，查快表需要1纳秒，内外存之间传送一个页面的平均时间为5000纳秒。假定快表的命中率为75%，页面失效率为10%，求内存的有效存取时间。 答：

访问主存的时间可用下面公式表示：

访问主存时间=主存的命中率*（快表的命中率*访问快表的时间+执行实际操作访问主存的时间）+页面失效率*页面失效时的访问时间 (6’)

因此 TA=(1-0.1)*[0.75*1+(1-0.75)*(8+1)+8]+0.1*5000 (4’)

11在一个虚拟存储器系统中，一次访问主存的时间用TA1表示，一个访问外存的时间用TA2表示。假定TA1=10^-7秒，TA2=10^-2秒。试问，为了使访问效率达到80%以上，命中率H至少应该达到多少？ 答：

访问效率：e=TA1/TA=0.8 (2’) TA=TA1/0.8=1.25*10^-7 s ( 2’) TA=H*TA1+(1-H)*TA2=H(TA1-TA2)+TA2 H=(TA-TA2)/(TA1-TA2) (2’)

解得 H=(1.25*10^-7-10^-2)/(10^-7 – 10^-2)=0.999975 (2’)

因此，为了使访问效率达到80%以上，命中率H至少应该达到0.999975。(2’)

第六章 文件系统