프로그래밍/JAVA2009. 6. 26. 18:16

1. LRU 알고리즘
운영체계의 페이지 교체 알고리즘 중 하나로서, 기억장치 바깥으로 내보낼 페이지를 선정할 때, 최근에 다른 어떤 페이지보다도 적게 사용된(읽혀지거나 기록되거나) 페이지를 고르는 알고리즘이다. 이와 같은 규칙은 캐시에도 적용될 수 있다.

이 규칙은, 일반적으로 가장 오랫동안 액세스되지 않았던 페이지는, 조만 간에도 액세스되지 않을 확률이 가장 크다는 시간적 집약성에 기반을 두고 있다. LRU는 Belady의 변이를 나타내지 않는다.


2. 구현
Jakarta Common Collection API에서 제공하는 org.apache.commons.collections.LRUMap을 이용하면 손쉽게 LRU캐쉬 엔진을 구현할 수 있다. 

** Jakarta Common Collection API 다운로드 [http://commons.apache.org/collections/]

Jakarta Common Collection API에서는 LRUMap외에도 다양한 자료구조를 제공해주고 있으니, 한번쯤 찾아보도록 하자.
LRUMap cache = new LRUMap(3);
위 코드는 크기가 3인 LRUMap을 생성한다.
cache.put("key1", "value1");
cache.put("key2", "value2");
cache.put("key3", "value3");
cache.put("key4", "value4");
위 코드는 LRUMap에 4개의 엔트리를 삽입하고 있다. 일반적인 Map과 같은 경우 저장공간을 확대한후 "Key4"에 대한 엔트리를 저장하지만 LRUMap은 지정된 크기 이상으로 저장공간이 증가하지 않는다. 대신 기존에 존재하던 엔트리중에 한개를 삭제하고 새로운 엔트리를 삽입한다. 여기서 과연 어떤 엔트리를 제거해야 하는가? 라는 의문이 생기는데 LRUMap은 그 이름에서 알수 있듯이 LRU 알고리즘을 이용한다. 즉, 최근 가장 오랫동안 사용되지 않았던 엔트리를 삭제하게 되는 것이다.

운영체제 이론의 페이지 교체 알고리즘에서 OPT알고리즘은 가장 효율성이 좋다고 알려져 있지만, 실제로 구현이 불가능 하기 때문에 차선책으로 사용되는 알고리즘이 LRU이다. 따라서 OPT알고리즘까지는 아니지만 다른 어떤 페이지 교체 알고리즘보다 LRU 알고리즘은 상대적으로 우수하다고 볼 수 있다.

LRU 캐쉬 엔진의 구현은 다음과 같다.
public class LRUCacheEngine {

	protected int limitSize;
	protected int totalAcces;
	protected int hitRate;

	protected int missRate;
	protected LRUMap lruMap;

	public LRUCacheEngine(int limitSize) {    
		this.limitSize = limitSize;    
		this.totalAcces = 0;    
		this.hitRate = 0;    
		this. missRate = 0;    
		lruMap = new LRUMap(limitSize);
	}

	public synchronized Object put(Object key, Object value) {    
		return lruMap.put(key, value);
	}

	public synchronized Object get(Object  key) {    
		totalAcces++;    
		Object value = lruMap.get(key);    
		if( rules != null ) {        
			hitRate++;        
			return value;    
		}    
		else        
			missRate++;   
		return null;
	}

	public synchronized void clear() {    
		lruMap.clear();
	}

	public synchronized int size() {    
		return lruMap.size();
	}

	public int getTotalAcces() {    
		return totalAcces;
	}

	public int getHitRate() {    
		return hitRate;
	}

	public int getMissRate() {    
		return missRate;
	}

	public int getLimitSize() {    
		return limitSize;
	}
}

'프로그래밍 > JAVA' 카테고리의 다른 글

Java 쓰레드  (0) 2009.12.04
스트러츠 properties 한글 편집  (0) 2009.12.03
Java XML Parser JDOM  (2) 2009.09.03
JRE Detection  (0) 2009.08.11
자바 웹 스타트(Java Web Start)  (0) 2009.08.07
JFreeChart with SWT  (0) 2009.07.14
자바 데몬(daemon) 만들기  (2) 2009.07.08
LRU 캐쉬 엔진의 구현  (0) 2009.06.26
JAVA Memory Leak  (2) 2009.06.25
Out Of Memory Error(OOME)에 대하여  (0) 2009.06.25
JAVA Heap 메모리 모델  (2) 2009.06.24
Posted by devop

댓글을 달아 주세요