已知一个采用LRU置换算法的请求分页存储管理系统中，页面大小为4

问题问答题

已知一个采用LRU置换算法的请求分页存储管理系统中，页面大小为4KB，内存访问速度为100ns/次，快表访问速度为20ns/次，缺页中断处理时间为25ms/次。现有一个长度为30KB的进程P进入系统，该进程分配有3个物理块，进程的所有页面都是在该进程运行中动态装入。若访问快表的命中率为20%，对应于下属页面访问序列：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1。计算这20个页面的平均有效访问时间是多少

答案

参考答案：采用LRU置换算法的置换过程如表4.15所示。

表4.15　　采用LRU置换算法的置换过程
页面走向	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块0	7	7	7	2		2		4	4	4	0			1		1		1
物理块1		0	0	0		0		0	0	3	3			3		0		0
物理块2			1	1		3		3	2	2	2			2		2		7
是否缺页	×	×	×	×		×		×	×	×	×			×		×		×

从表中得到缺页次数为12次，所以缺页率为12/20=60%。
EAT=命中快表的存取时间×p×(1-f)+命中内存的存取时间×(1-p)×(1-f)+缺页时的存取时间×f
=20ns×20%×(1-60%)+100ns×(1-20%)×(1-60%)+20ms×60%
=1.6ns+32ns+8ms
≈8ms

解析：本题考查页面置换的LRU置换算法和有效访问时间的相关计算。