地址变换和缺页置换习题

1.设某进程页面的访问序列为4,3,2,1,4,3,5,4,3，2,1,5，当分配给该进程的内存页框数分别为3和4时，对于先进先出，最近最少使用，最佳页面置换算法，分别发生多少次缺页中断？

答：

分配的页框数为3时：

FIFO:

	4	3	2	1	4	3	5	4	3	2	1	5
内存块1	4	4	4	1	1	1	5	5	5	5	5	5
内存块2		3	3	3	4	4	4	4	4	2	2	2
内存块3			2	2	2	3	3	3	3	3	1	1
是否缺页	×	×	×	×	×	×	×	√	√	×	×	√

共缺页9次

扩充：先进先出置换算法（FIFO):每次选择淘汰的页面是最早进入内存的页面

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。

当到内存块为 1 4 3时，队列为4-3-5,这时候下一个访问4，因为内存块有，就不改变队列，继续下一个，3也在队列不改变，2的时候改变，于是队列变为了3-5-2，内存块为4内容的改为2.

OPT:

	4	3	2	1	4	3	5	4	3	2	1	5
内存块1	4	4	4	4	4	4	4	4	4	2	2	2
内存块2		3	3	3	3	3	3	3	3	3	1	1
内存块3			2	1	1	1	5	5	5	5	5	5
是否缺页	×	×	×	×	√	√	×	√	√	×	×	√

共缺页7次

扩充; 最佳置换算法（OPT，Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

注意最后从倒数第四个到倒数第三个，4 3 5 改为2 3 5，因为后期都不会有4 3的访问了，所以先改变4，从倒数第三个到倒数第二个，2 3 5 下一个时2 1 5，改变3的原因时尽管感觉3与2都可以修改，但是3的时间不妨问比2的久，因为2刚刚访问过了。

分配的页框数为4时：

FIFO:

	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
是否缺页	×	×	×	×	√	√	×	×	×	×	×	×

共缺页10次

LRU:

	4	3	2	1	4	3	5	4	3	2	1	5
内存块1	4	4	4	4	4	4	4	4	4	4	4	5
内存块2		3	3	3	3	3	3	3	3	3	3	3
内存块3			2	2	2	2	5	5	5	5	1	1
内存块4				1	1	1	1	1	1	2	2	2
是否缺页	×	×	×	×	√	√	×	√	√	×	×	×

共缺页8次

扩充：最近最久未使用置换算法（LRU，least recently used):每次淘汰的页面是最近最久未使用的页面。简单来说就是看有4个内存块，那么往前看4个不同的，把最后一个改变，比如，到5的时候，前面4个依次是2 1 4 3，所以从5往前看正好是不同的4个，删除最后一个2，5给换上。

倒数第3个是2，按照方法从前数发现是1 5 4 3

OPT：

	4	3	2	1	4	3	5	4	3	2	1	5
内存块1	4	4	4	4	4	4	4	4	4	4	1	1
内存块2		3	3	3	3	3	3	3	3	3	3	3
内存块3			2	2	2	2	2	2	2	2	2	2
内存块4				1	1	1	5	5	5	5	5	5
是否缺页	×	×	×	×	√	√	×	√	√	√	×	√

共缺页6次

2. 某分页存储管理中，页面大小为4KB,某进程的页号0~8对应的物理块号分别为8、9、 10、15、18、20、21、22、23，计算该进程的逻辑地址05AF8H对应的物理地址（描述计算过程）

答：因为：页号为0-8，所以：前4位为页号

           页面大小为4KB，4K=2^12 所以：后12位为页内地址

                  05AF8H的二进制为0101 1010 1111 1000

                  所以：页号为0101  十进制表示为5

查表得物理快号为20，即10100（B）

与页内地址拼接得10100 1010 1111 1000     十六进制为14AF8H

3. 在一个请求页式存储管理系统中，进程P共有5页，访问串为3，2，1，0，3，2，4，3，2，1，0，4时，试用LRU置换算法和FIFO置换算法，计算当分配给该进程的页面数为3时，访问过程中发生的缺页次数和缺页率。

LRU：

	3	2	1	0	3	2	4	3	2	1	0	4
内存块1	3	3	3	0	0	0	4	4	4	1	1	1
内存块2		2	2	2	3	3	3	3	3	3	0	0
内存块3			1	1	1	2	2	2	2	2	2	4
是否缺页	×	×	×	×	×	×	×	√	√	×	×	×

缺页次数：10  缺页率：10/12=5/6

FIFO：

	3	2	1	0	3	2	4	3	2	1	0	4
内存块1	3	3	3	0	0	0	4	4	4	4	4	4
内存块2		2	2	2	3	3	3	3	3	1	1	1
内存块3			1	1	1	2	2	2	2	2	0	0
是否缺页	×	×	×	×	×	×	×	√	√	×	×	√

缺页次数：9  缺页率：9/12=3/4

方法：排成一个队列，替换最早的哪一个，遇到相同的页号不改变，如到了4-3-2，这时候队列为3-2-4，但是下一个页号为3，内存块已经有了，然后下一块2，内存块也有，都不改变队列，到了1的时候内存块没有，改变最早的那个，也就是3，所以存放3的那个内存块变成了1

4. 在某请求分页系统中，有一作业，它依次要访问的地址序列是：18、351、198、99、436、50、556，若该作业的第0号页已经装入主存，现分配给该作业的主存共3块，页的大小为100字节。请回答下列问题（需要详细过程）：

(1)按FIFO调度算法产生的缺页中断次数是多少？依次写出淘汰的页号？缺页中断率是多少？

（2）按LRU调度算法产生的缺页中断次数是多少？依次写出淘汰的页号？缺页中断率是多少

答：依次访问页号为 0 3 1 0 4 0 5

FIFO：

	0	3	1	0	4	0	5
内存块1	0	0	0	0	4	4	4
内存块2		3	3	3	3	0	0
内存块3			1	1	1	1	5
是否缺页	×	×	×	√	×	×	×

中断次数 6     淘汰的页号： 0 3 1   缺页率：6/7=85.71%

LRU：

	0	3	1	0	4	0	5
内存块1	0	0	0	0	0	0	0
内存块2		3	3	3	4	4	4
内存块3			1	1	1	1	5
是否缺页	×	×	×	√	×	√	×

中断次数 5    淘汰的页号（暂定）： 0 3 1  和0 4 1 缺页率：5/7=71.43%

5. 请求分页管理系统中，假设某进程的页表内容如下表所示。

   页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设：

①TLB初始为空；

②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；

③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列137H 、565H、15A5H，请问：

（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。 

（2） 基于上述访问序列，虚地址258H的物理地址是多少？请说明理由。  

页号	页框号	有效位（存在位）
0	101H	1
1	--	0
2	254H	1

（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：

 137H：P=0，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。

 565H：P=0，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。

 15A5H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈108ns。

 （2）访问1565H时,1号页面在内存中,页框号与15A5H相同。前面当访问虚地址15A5H时，访问页表发现1号页不在内存中，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，最近访问的都是0号页的内容，0号页不应被淘汰。应淘汰2号页面，因此1号页面装入时对应的页框号为254H。由此可得1565H的物理地址为254565H。

6.段式存储管理

在某个段式存储管理系统中，进程P的段表如下表，求表中各逻辑地址对应的物理地址

段号	段内位移
0	430
1	15
2	500
3	400
4	112

答：

段号	段内位移	物理地址
0	430	680
1	15	2365
2	500	越界
3	400	1750
4	112	越界

7.页式管理

在某页式管理系统，某进程页表如下，已知页面大小为1024B，试将逻辑地址1012、2248、3010、4020、5018转化为相应的物理地址。

页号	页框号
0	5
2	8
2	8
3	1
4	6

答：

逻辑地址	页号	页内地址	页框号	物理地址
1012	0	1012	5	5*1024+1012=6132
2248	2	200	8	8*1024+200=8392
3010	2	962	8	8*1024+962=9154
4020	3	948	1	1*1024+948=1972
5018	4	922	6	6*1024+922=7066

8. 假定某页式管理系统中，主存为128KB，分成32块,块号为0,1,2,3,4……31,某作业有五块,其页号为0,1,2,3,4, 被分别装主存的3,8,4,6,9块中，有一逻辑地址为[3,70],试求出相应的物理地址(其中方括号中的第一个元素为页号,第二个元素为页内地址，按十进制计算)，并画图说明地址变换过理。

9.计算物理地址

物理地址计算3步曲!

• 求出页号
• 对照页表
• 计算地址

地址转换

绝对地址 = 块号*块长 + 块内地址

例题:

在采用页式存储管理的系统中,某进程的逻辑地址空间为4页(每页2048字节),且已知该进程的页面映像表(页表)如下:

页号	块号
0	2
1	4
2	6
3	8

计算有效逻辑地址4865所对应的物理地址.

解题:

读题划重点: 每页多少字节, 页表,有效逻辑地址!

3步曲解题!

页号:

页号 = 逻辑地址/每页字节数

d = 4865/2048 = 2

对照页表:

根据页号找到块号!

看页表 ,页号2对应块号6!

数地址:

绝对地址 = 块号*块长（每页字节数） + 块内地址

块内地址= 逻辑地址%每页字节数

块内地址: 4865%2048 = 769

地址:6*2048 + 769 = 13057