操作系统_第四章作业讲解

1、“整体对换从逻辑上也扩充了内存，因此也实现了虚拟存储器的功能”这种说法是否正确？请说明理由

答：上述说明法是错误的。整体对换将内存中暂时不用的某个程序及其数据换出至外存，腾出足够的内存空间以装入在外存中的、具备运行条件的进程所对应的程序和数据。虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统，它的实现必须建立在离散分配的基础上。虽然整体对换和虚拟存储器均能从逻辑上扩充内存空间，但整体对换不具备离散性。实际上，在具有整体对换功能的系统中，进程的大小仍受到实际内存容量的。

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

2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？

3）如果物理空间减少一半，页表结构应相应作怎样的改变？

答：1）该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位来描述，而每页为2KB，因此，页内地址必须用11位来描述。这样，可得到它的逻辑地址格式如下：

0

10

11

15

页内地址

页号

2）每个进程最多有32个页面，因此，进程的页表项最多为32项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块号。1MB的物理空间可分成29个内存块，故每个页表项至少有9位。

3）如果物理空间减少一半，则页表中项表项数仍不变，但每项的长度可减少1位。

3、已知某系统页面长4KB，每个页表项为4B，采用多层分页策略映射位的用户地址空间。若限定最高层页表只占1页，则它可采用几层分页策略

答：方法一：由题意可知，该系统的用户地址空间为2B，而页的大小为4KB，故作业最多可有2/212（即252）个页，其页表的大小则为252*4（即254）B。因此，又可将页表分成242个页表页，并为它建立两级页表，两级页表的大小为244B。依次类推，可知道它的3、4、5、6级页表的长度分别是234B、224B、214B、24B，故必须采取6层分页策略。

    方法二：页面大小为4KB=212B，页表项4B=22B，因此一个页面可以存放212/22=210个面表项，因此分层数=INT[/10]=6层

4、对于表所示的段表，请将逻辑地址（0，137）、（1，4000）、（2，3600）、（5，230）转换成物理地址。

              段   表

段号	内存地址	段长
0	50K	10KB
1	60K	3KB
2	70K	5KB
3	120K	8KB
4	150K	4KB

答：[0,137]：50KB+137=51337；

[1，4000]：段内地址越界；

[2，3600]：70KB+3600=75280；

[5，230]：段号越界。

5、在一个请求分页系统中，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时，访问过程中所发生的缺页次数和缺页率，并比较所得结果。 （选做括号内的内容：根据本题的结果，请查找资料，说明什么是Belady现象，在哪种置换算法中会产生Belady现象，为什么

答：1）使用OPT算法时，访问过程中发生缺页的情况为：当M=3时，缺页次数为7，缺页率为7/12；当M=4时，缺页次数为6，缺页率为6/12。可见，增加分配给作业的内存块数，可减少缺页次数，从而降低缺页率。

访问过程中的缺页情况（M=3，OPT算法）

页面引用	4	3	2	1	4	3	5	4	3	2	1	5
物 理 块	4	4	4	4			5			5	5
		3	3	3			3			2	2
			2	1			4			4	1
缺页	×	×	×	×			×			×	×
置换				√			√			√	√

访问过程中的缺页情况（M=4，OPT算法）

页面引用	4	3	2	1	4	3	5	4	3	2	1	5
物 理 块	4	4	4	4			4				1
		3	3	3			3				3
			2	2			2				2
				1			5				5
缺页	×	×	×	×			×				×
置换							√				√

2）使用LRU算法时，访问过程中发生缺页的情况为：当M=3时，缺页次数为10，缺页率为10/12；当M=4时，缺页次数为8，缺页率为8/12。可见，增加分配给作业的内存块数，可减少缺页次数，从而降低缺页率。

访问过程中的缺页情况（M=3，LRU算法）

页面引用	4	3	2	1	4	3	5	4	3	2	1	5
物 理 块	4	4	4	1	1	1	5			2	2	2
		3	3	3	4	4	3			3	3	5
			2	2	2	3	4			4	1	1
缺页	×	×	×	×	×	×	×			×	×	×
置换				√	√	√	√			√	√	√

访问过程中的缺页情况（M=4，LRU算法）

页面引用	4	3	2	1	4	3	5	4	3	2	1	5
物 理 块	4	4	4	4			4			4	4	5
		3	3	3			3			3	3	3
			2	2			5			5	1	1
				1			1			2	2	2
缺页	×	×	×	×			×			×	×	×
置换							√			√	√	√

2）使用FIFO算法时，访问过程中发生缺页的情况为：当M=3时，缺页次数为9，缺页率为9/12；当M=4时，缺页次数为10，缺页率为10/12。可见，增加分配给作业的内存块数，反而增加了缺页次数，提高了缺页率，这种现象被称做Belady现象。

访问过程中的缺页情况（M=3，FIFO算法）

页面引用	4	3	2	1	4	3	5	4	3	2	1	5
物 理 块	4	4	4	1	1	1	5			5	5
		3	3	3	4	4	4			2	2
			2	2	2	3	3			3	1
缺页	×	×	×	×	×	×	×			×	×
置换				√	√	√	√			√	√

访问过程中的缺页情况（M=3，FIFO算法）

页面引用	4	3	2	1	4	3	5	4	3	2	1	5
物 理 块	4	4	4	4			5	5	5	5	1	1
		3	3	3			3	4	4	4	4	5
			2	2			2	2	3	3	3	3
				1			1	1	1	2	2	2
缺页	×	×	×	×			×	×	×	×	×	×
置换							√	√	√	√	√	√

6、现有一请求调页系统，页表保存在寄存器中。若一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，则处理一个缺页中断需要20ms。内存存取时间为1us，访问页表的时间可忽略不计。假定70%被替换的页被修改过，为保证有效存取时间不超过2us，可接受的最大缺页率是什么？ 

答：如果用p表示缺页率，则有效访问时间不超过2us可表示为（1-p）×1us+p×(0.7×20ms+0.3×8ms+1us)≦2us

因此可计算出：p≦1/100≈0.00006

即可接受的最大缺页率为0.00006。

7、有一个二维数组：VAR  A：ARRAY（1..100, 1..100） OF integer；按先行后列的次序存储。对一采用LRU置换算法的页式虚拟存储器系统，假设每页可存放200个整数。若分配给一个进程的内存块数为3，其中一块用来装入程序和变量i、j，另外两块专门用来存放数组（不作他用），且程序段已在内存，但存放数组的页面尚未装入内存。请分别就下列程序计算执行过程中的缺页次数。

程序1：

FOR i:=1 TO 100 DO

FOR j:=1 TO 100 DO

A[i, j]:= 0

程序2： FOR j:=1 TO 100 DO FOR i:=1 TO 100 DO   A[i, j]:= 0

答：对于程序1，首次缺页中断（访问A[0，0]时产生）将装入数据的第1、2行共200个整数，由于程序是按行对数组进行访问的，只有在处理完200个整数后才会再次产生缺页中断；以后每调入一页，也能处理200个整数，因此处理100×100个整数共将发生50次缺页。

    对于程序2，首次缺页中断（访问A[0，0]时产生）将装入数据的第1、2行共200个整数，但由于程序是按列对数组进行访问的，因此在处理完2个整数后又会再次产生缺页中断；以后每调入一页，也只能处理2个整数，因此处理100×100个整数共将发生5000次缺页。