堆栈模拟

列：使用LRU算法的页式虚拟存储器共有9页空间准备分配给A、B两道程序。已知若给B道程序分配4页时，其命中率为8／15；若给其分配5页时，其命中率为10／15。现给出A道程序执行中的页地址流为：2、3、2、1、5、2、4、5、3、2、5、2、1、4、5。 1）画出用堆栈对A道程序页地址流的模拟过程图，分别计算给其分配4页和5页时的命中率。 2）根据已知条件和上述计算结果，给A、B两道程序各分配多少实页，可使系统效率最高？

解：

堆栈示意图：

解1：

实页/页面地址流	2	3	2	1	5	2	4	5	3	2	5	2	1	4	5
0	2	3	2	1	5	2	4	5	3	2	5	2	1	4	5
1		2	3	2	1	5	2	4	5	3	2	5	2	1	4
2				3	2	1	5	2	4	5	3	3	5	2	1
3					3	3	1	1	2	4	4	4	3	5	2
4							3	3	1	1	1	1	4	3	3
命中：n=4			H			H		H		H	H	H			H
命中:n=5			H			H		H	H	H	H	H	H	H	H

n=4时，命中率:H=7/15

n=5时，命中率:H=10/15

解2：

因为：虚拟存储器共有9页，咋a=4时，b=5，反之a=5，b=4；

命中率(a=4,b=5)：$H=\frac{\frac{7}{15}+\frac{10}{15}}{2}=\frac{17}{30}$

命中率(a=5,b=4)：$H=\frac{\frac{10}{15}+\frac{8}{15}}{2}=\frac{18}{30}$；（分子越大，值越大）

所以a、b两道程序，分配a=5，b=4时，效率最高

延伸阅读