[페이징 교체 알고리즘] 페이징 교체 알고리즘 구현하기

페이징 교체 알고리즘은 페이징기법으로, 메모리를 관리하는 운영체제에서 페이지의 부재가 발생하여

새로운 페이지를 기존의 어떤 페이지와 교체할 것인가? 를 결정 하기 위해 필요한 알고리즘이다.

 

FIFO 알고리즘 : 페이지가 적재된 시간을 기준으로 교체되는 알고리즘 (First in First out 관련 알고리즘 이다. )

- 가장 오래된 페이지가 교체되나, 중요한 페이지가 오래되었다는 이유로 교체될 수 있기 때문에 불합리 하다.

 

LFU 알고리즘 : 가장 적게 사용된 페이지를 교체하는 알고리즘, 참조될 가능성이 많은데 가장 적게 사용되었다는 이유로 최근에 사용되었지만 교체될 가능성이 있다. 참조된 횟수를 증가 시키기 때문에 오버헤드를 발생시킨다.

 

LRU 알고리즘 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

-프로세스가 주 기억장치에 접근 할때마다 참조된 페이지의 시간을 기록해야한다. 큰 오버헤드가 발생한다.

 

LRU 알고리즘의 구현 방식 개념

설명을 붙이자면, LRU 캐시 알고리즘은, 더블 링크드 형태를 가진다.

즉 헤드와 테일을 가지고 구현이 되는 구현체이다.

 

처음에 1,2 가 들어왔을때는 캐시에 없기 때문에 miss로 스택처럼 head에 들어온 순서대로 붙이고

3초 때 1이 입력되면 캐시에 존재하는 값이기 때문에 해당 1의 값을 스택처럼 head쪽으로 다시 올린다.

대부분 캐시 사이즈가 정해져 있는데, 만약에 이 캐시사이즈가 꽉차게 되면 교체가 발생한다.

4가 입력될떄 Miss이기때문에 4는 head다음으로 위치하게 되고, 가장 tail 쪽에 있는, 즉 가장 덜 최근에 사용된 2가 삭제가 된다.

 

즉, LRU 알고리즘은 정리해서 생각하면 아래와 같다.

Cache hit 상태일때는 head다음인덱스로 해당 값을이동

Cache miss 상태인경우

- Cache size가 꽉차지 않는 경우 : 그냥 단순 Stack처럼 head 다음 값에 위치하게 된다. (단순 Cache Hit 상태처럼 링크드 리스트에 입력)

-Cache size가 꽉찬 경우(교체 발생이 필요한 경우) : 가장 마지막의 tail이 가르키는 녀석을 삭제 후에, 입력된 값을 head쪽 구현체로 넣는다.

 

이제 이 개념을 자바로 구현하면 아래와 같다.

 

 

 

LRU 알고리즘은 우선 아까 말했듯이 더블 링크드 리스트 구조를 가진다.

기억해야할? 구조 함수는 총 4개이다.

insertHead(처음에 헤드바로 뒤에 넣는 함수)

remove(다른 함수에서 사용하는 유틸함수이다. 우선 사용되면 Map에서 삭제 + 링크드 리스트에서 해당 참조를 뺀다.)

put (삽입 하는 함수)

-> 해당 함수 호출시에 이미 존재한다면, 해당 값을 remove하고 insertToHead

-> 해당 함수 호출시에 이미 존재하지 않는다면, 캐시 사이즈 체크하고 마지막 remove를 진행 필요시에 진행하고 insertTohead

get(호출 함수)

-> 해당 호출된 것을 찾는 함수, 해당 값이 있다면, 기존에 존재하는 것을 삭제하고 insertToHead를 하여, 헤드 앞으로 넣는다.

 

위의 개념 공부 과정에서 넣는 순서를 그대로하면, 해당 링크드 리스트의 자료구조는 아래와 같이된다(캐시 사이즈 3으로 했을때 가정)