4、堆栈法

　　用栈顶至栈底的先后次序来记录Cache同一组内的各个块被访问的先后次序。栈顶是最近被访问过的块，栈底是最久没有被访问过的块。当要替换时，从栈顶压入新的块，很自然，最久没有被访问过的块就从栈的底部被挤出堆栈。如图3.38所示。

图3.38 堆栈法的工作原理

　　堆栈法实际上是一种LRU替换算法，其管理规则为：把本次访问的块号与堆栈中保存的所有块号进行相联比较。如果发现有相等的，则Cache命中，这时，把本次访问的块号从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。如果没有发现相等的，则Cache块失效，这时，本次访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底。栈底单元中的块号被移出堆栈，它就是要被替换的块号。
　　因此，在堆栈法中，栈底永远保存着最久没有被访问过的块号，也就是下次要被替换出Cache的块号。