随机给出一个页面执行序列,如:1,5,3,4,2,1,3,4,5,7,9,……。要求计算以下几种置换算法的缺页数、缺页率和命中率。
最佳置换算法OPT(Optimal)
先进先出算法FIFO(First In First Out)
最近最少使用算法LRU(Least Recently Used)
LRU replacement policy
解释了s3c44b0x cache的行替换策略
• each bit represents one branch point in a binary decision tree
• let 1 represent that the left side has been referenced more recently than the right side, and
0 vice-versa
are all 4 lines valid?
/ \
yes no, use an invalid line
|
|
|
bit_0 == 0? state | replace ref to | next state
/ \ ------+-------- -------+-----------
y n 00x | line_0 line_0 | 11_
/ \ 01x | line_1 line_1 | 10_