반응형
1. LRU 페이지 교체 알고리즘 이란?
Least Recently Used (LRU) page replacement algorithm
LRU 알고리즘을 간단히 정리하면 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다.
2. 페이지 교체 알고리즘 (page replacement algorithm)
페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.
LRU 알고리즘은 페이지 교체 알고리즘의 한 종류이다.
3. 예제
캐시 크기가 4일 때 1, 2, 3, 1, 4, 5 순서로 페이지를 방문하는 경우, LRU 알고리즘의 동작은 다음과 같다.
- 캐시에 공간이 있으면, 가장 최근에 방문한 페이지가 캐시의 가장 최근 값으로 등록된다.
- 캐시에 참조하는 페이지가 있으면 해당 페이지를 캐시의 가장 최근 값으로 등록한다.
- (예) 캐시에 3, 2, 1 이 등록되어있는 상태에서 1을 방문하는 경우 캐시는 1, 3, 2가 된다.
- 캐시에 참조하는 페이지가 없으면 해당 페이지를 캐시의 가장 최근 값으로 등록하고, 캐시에 있는 페이지 중 가장 오랫동안 방문하지 않은 페이지를 제거한다.
- (예) 캐시에 4, 1, 3, 2 가 등록되어있는 상태에서 5를 방문하는 경우 가장 오랫동안 방문하지 않은 2를 캐시에서 제거하고 최근 방문 페이지로 5를 등록하여 캐시는 5, 4, 1, 3이 된다.
위의 내용을 그림으로 이해해보자.
4. java 코드
/**
* least recently used (LRU) page replacement algorithm
* LRU 캐시 페이지 교체 알고리즘 : Deque, HashSet 을 이용하는 방법
*/
public class LRUCache {
// 캐시의 키값 저장 (Deque 는 LIFO)
private Deque<Integer> doublyQueue;
// 캐시의 참조 키값 저장
private HashSet<Integer> hashSet;
// 캐시 최대 용량
private final int CACHE_SIZE;
// Constructor
public LRUCache(int capacity) {
doublyQueue = new LinkedList<>();
hashSet = new HashSet<>();
CACHE_SIZE = capacity;
}
// LRU 캐시 내 페이지 참조
public void refer(int page) {
// 포함되어 있지 않으면 처음방문 페이지
if (!hashSet.contains(page)) {
if (doublyQueue.size() == CACHE_SIZE) {
int last = doublyQueue.removeLast(); // 마지막 방문 페이지 제거
hashSet.remove(last);
}
} else {
// 포함되어 있으면 제거(remove()) 하고 앞으로 꺼내야함 (push())
doublyQueue.remove(page);
}
doublyQueue.push(page);
hashSet.add(page); // HashSet 은 중복 x, 순서보장 x
}
// 출력메소드
public void display() {
Iterator<Integer> itr = doublyQueue.iterator();
while (itr.hasNext()) {
System.out.print(itr.next() + " ");
}
}
// 실행
public static void main(String[] args) {
// LRU 캐시 4로 생성
LRUCache cache = new LRUCache(4);
cache.refer(1); // 1
cache.refer(2); // 2 1
cache.refer(3); // 3 2 1
cache.refer(1); // 1 3 2
cache.refer(4); // 4 1 3 2
cache.refer(5); // 5 4 1 3
cache.display();
}
}결과출력(콘솔)
5 4 1 3
참고 :
반응형