几种高速缓存算法

缓存是在CPU和内存之间的一块存取速度极快的存储单元，CPU在处理数据时，如果在寄存器中找不到目标数据，则优先从缓存中寻找。而缓存的容量远远小于内存的容量，当缓存已满而又要继续往其中添加新的数据的时候，如何替换缓存中已有的数据就是高速缓存算法要解决的问题。假设CPU要使用的页面依次为{1,2,4,1,5,7,4}，而缓存的最大容量为3，以下分别以此为例介绍往缓存的中添加数据的两种算法

(a) LRU算法（Least Recently Used，最久未使用算法）。将最久未使用的页面舍弃，给新数据腾空间。步骤如下：

1) 将页面1调入缓存：1

2) 将页面2调入缓存： 2，1

3）将页面4调入缓存： 4，2，1

4）将页面1调入缓存： 1，4，2

5）将页面5调入缓存： 5，1，4；缓存已满，将最久未使用的页面2舍弃，给新页面5腾空间

6）将页面7调入缓存： 7，5，1；将最久未使用的页面4舍弃

7）将页面4调入缓存： 4，7，5；将最久未使用的页面1舍弃

(b)LFU算法（Least Frequently Used，最不经常使用算法）。将使用最少的页面舍弃，给新页腾空间。需要给要使用的所有页面分别维护一个变量，用来记录其被使用的次数。每一次需要置换时，用新页面替换缓存中使用次数最少的页面。

        现基于这两种算法，创建一个函数，用于记录CPU在使用一组页面时，从缓存中获取目标页面失败的次数，例如，当CPU要使用页面4时，此时缓存中恰好存有页面4时，则从缓存中获取目标页面成功，否则认为获取失败。函数的输入为缓存的最大容量capasity和要使用的页面数组。具体代码如下：

package javaTest;

public class CacheAlgorithm {
	public static void main(String[] args){
		int capacity = 4;
		int[] pages = {1,2,3,2,5,2,6,7,4,8,3};
		System.out.println(lru(capacity,pages));
		System.out.println(lfu(capacity,pages));
	}

	public static int lru(int capacity, int[] pages){
		int count = 0;
		int[] cacheUnit = new int[capacity];
		for(int i=0; i<pages.length; i++){
			boolean flag = false;
			for(int j=0; j<capacity; j++){
				if(cacheUnit[j]==pages[i]){
					add(cacheUnit, pages[i], j);
					flag = true;
					break;
				}
			}
			if(!flag){
				count++;
				add(cacheUnit,pages[i],capacity-1);
			}
		}
		return count;
	}

	public static int lfu(int capacity, int[] pages){
		int[] cacheUnit = new int[capacity];
		int count = 0;
		int max = 0;
		for(int i:pages){
			if(i>max){max = i;}
		}
		int[] state = new int[max+1];
		for(int i:pages){
			state[pages[i]]++;
			boolean flag = false;
			for(int j=0; j<capacity; j++){
				if(cacheUnit[j]==i){
					flag = true;
					break;
				}
			}
			if(!flag){
				count++;
				int index = 0;
				for(int j=0; j<capacity; j++){
					if(state[cacheUnit[j]]<state[cacheUnit[index]]){
						index = j;
					}
				}
				cacheUnit[index] = i;
			}
		}
		return count;
	}

	
	public static void add(int[] cacheUnit, int value, int index){
		for(int i=0; i<index; i++){
			cacheUnit[i+1] = cacheUnit[i];
		}
		cacheUnit[0] = value;
	}
}