【正确答案】采用LRU置换算法时的页面置换情况见表。
{{B}}采用LRU置换算法时的页面置换情况{{/B}}
|
| 页面走向 |
1 |
4 |
3 |
1 |
2 |
5 |
1 |
4 |
2 |
1 |
4 |
5 |
按最后访问时间排
序，越早排越后 |
1 |
4 |
3 |
1 |
2 |
5 |
1 |
4 |
2 |
1 |
4 |
5 |
|
|
1 |
4 |
3 |
1 |
2 |
5 |
1 |
4 |
2 |
1 |
4 |
|
|
1 |
4 |
3 |
1 |
2 |
5 |
1 |
4 |
2 |
1 |
| 缺页 |
√ |
√ |
√ |
|
√ |
√ |
|
√ |
√ |
|
|
√ |
访问这12个页面时，缺页次数为8，缺页率为8/12=2/3。
一次内存访问时间t为100ns。
一次快表访问时间ε为20ns。
快表命中率α为20%。
缺页率f为2/3，
一次缺页处理时间t1=25ms。
有效访问时间用EAT表示
EAT=ε+αt+(1-β)[t+f(t1+ε+t)+(1-f)(ε+t)]
=20ns+20%×100ns+(1-20%)[100ns+2/3(25ms+20ns+100ns)+(1-2/3)(20ns+100ns)]
≈13333549ns
求解方法提示：请求分页管理方式中的有效时间计算法。
归纳起来，简化的请求分页访问过程如图所示，其中方框表示的操作都要花费访问时间。
[*]
1)不考虑命中率和缺页率的有效访问时间计算。
从图可以看到，访内操作共有以下三种情况。
①访问的页在主存中，且访问页的页表项在快表中(若访问页的页表项在快表中，则一定不会缺页)。
EAT=查找快表时间+形成物理地址并访问内存数据的时间
=ε+t
②访问的页在主存中(不缺页)，且访问页的页表项不在快表中。
EAT=查找快表时间+查找页表时间+修改快表时间+形成物理地址并访问内存数据的时间
=ε+t+c+t
=2(ε+t)
③访问的页不在内存中(缺页)，设处理缺页中断的时间为t1(产生缺页中断并将该页调入内存，更新快表和页表的时间)。
EAT=查找快表时间+查找页表时间+处理缺页中断的时间t1+查找快表时间+形成物理地址并访问内存数据时间
=ε+t+t1+ε+t=t1+2(ε+t)
2)考虑命中率和缺页率的有效访问时间计算。
从图可以看出，共有3条路径(当产生缺页中断后，页表项会放入快表中)，则：
ENT=查找快表时间+α×形成物理地址并访问内存数据时间+(1-α)×[查找页表时间+f×(处理缺页中断的时间t1+查找快表时间+形成物理地址并访问内存数据时间)+(1-f)×(修改快表时间+形成物理地址并访问内存数据时间)]
=ε+αt+(1-α)[t+f(t1+ε+t)+(1-f)(ε+t)]
3)处理缺页中断的时间t1的计算。
如果题目中没有给出被置换的页面修改和不修改两种情况，则将缺页中断处理时间看成t1。如果题目中给出被置换页面修改和不修改两种情况，前者的概率为β，处理时间为ta，后者处理的时间为tb，则t1=β×ta+(1-β)×tb。
4)推论。
如果题目中没有给出快表等，也就是说，ε=0，α=0，则有效访问时间为：
EAT=c+f(t1+t)+(1-f)t
如果f等于0，则不存在缺页中断处理，其计算过程同基本分页管理方式。从有效时间的计算可以看到，考生必须牢固掌握请求分页中的访问过程。