[OS] 페이지 교체 알고리즘 - LRU

서론

이번 글에서는 페이지 교체 알고리즘의 종류 중에서 LRU(Least Recently Used) 알고리즘의 동작 원리를 알아보고자 한다.

이전 포스팅 글에서 페이지 교체 알고리즘의 종류인 FIFO에 관한 내용들 다루었으므로, FIFO의 개념과 동작 원리에 대해서 궁금하신 분들은 아래 글을 참고하면 좋을 것 같다.

• [OS] 페이지 교체 알고리즘 - FIFO

[OS] 페이지 교체 알고리즘 - FIFO

LRU(Least Recently Used) Algorithm

페이지 교체 알고리즘에서 LRU는 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법이다.

해당 알고리즘은 가장 오랫동안 사용하지 않은 데이터는 미래에도 사용하지 않을 확률이 높다는 의미를 가지고 있다.

 

LRU는 각 페이지마다 계수기(Counter) 혹은 스택(Stack)을 사용하여 현 시점에서 가장 오랫동안 사용하지 않은, 다시 말하면 가장 오래 전에 사용된 페이지를 교체하는 방식으로 구현할 수 있다.

 

예제를 통해서 LRU 알고리즘을 이해해보자.

 

• 페이지 프레임은 3개로 구성되어 있고, 초기 페이지 프레임은 비어있는 상태이다.
• 참조 페이지 번호 순서는 다음과 같다 [2, 3, 2, 1, 5, 2, 3, 5]
• 다음과 같은 조건이 있을 때 페이지 결함(Page Fault)가 일어나는 횟수를 구하여라.

페이지 결함이 일어나는 경우는 FIFO 알고리즘을 다룰 때 설명했으므로 위에서 언급한 글을 참고하면 좋을 것 같다.

 

또한, 예제에서 Resulting Cache State의 값은 오래된 데이터 일수록 오른쪽으로 배치시키는 방법으로 설정했다.

Access	Hit/Miss	Evict	Resulting Cache State
2	Miss		2
3	Miss		3, 2
2	Hit		2, 3
1	Miss		1, 2, 3
5	Miss	3	5, 1, 2
2	Hit		2, 5, 1
3	Miss	1	3, 2, 5
5	Hit		5, 3, 2

해당 표를 기반으로 페이지 결함 횟수를 구해보면 답은 5가 나온다. 이제 어떻게 5가 나왔는지 과정을 살펴보자.

• 첫 번째에 들어온 2는 페이지 프레임이 비어있으므로 페이지 결함이 발생한다. (1회)
• 두 번째에 들어온 3 또한 페이지 프레임이 비어있으므로 페이지 결함이 발생한다. (2회)
• 세 번째에 들어온 2는 프레임이 비어있지만, 프레임 내에 첫 번째에서 들어온 2가 존재하므로 결함이 발생하지 않는다.
  • 이 때, 가장 최근에 사용된 참조 번호가 3에서 다시 2로 변화되었다.
  • 필자는 오른쪽에 있는 번호가 오래된 데이터라고 정의했으므로 (2, 3)으로 표현하였다.
• 네 번째에 들어온 1은 페이지 프레임이 비어있고 프레임 내에 1이 존재하지 않으므로 결함이 발생한다. (3회)
  • 마찬가지로 가장 최근에 사용 → 가장 오래전에 사용 순서이므로 (1, 2, 3)으로 표현하였다.
• 다섯 번째에 들어온 5는 페이지 프레임이 꽉 차있고, 프레임 내에 5가 존재하지 않으므로 결함이 발생한다. (4회)
  • 가장 오랫동안 사용되지 않은 3이 제거되고 5가 프레임 내에 적재된다. (5, 1, 2)
• 여섯 번째에 들어온 2는 프레임이 꽉 차있지만 프레임 내에 2가 존재하므로 결함이 발생하지 않는다.
  • 가장 최근에 2가 사용되었으므로 (5, 1, 2) → (2, 5, 1)로 순서가 교체되었다.
• 일곱 번째에 들어온 3은 프레임이 꽉 차있고, 프레임 내에 3이 존재하지 않으므로 페이지 결함이 발생한다. (5회)
  • 가장 오랫동안 사용되지 않은 1이 제거되고 3이 프레임에 적재된다. (3, 2, 5)
• 마지막으로 들어온 5는 프레임이 꽉 차있으나 프레임 내에 5가 존재하므로 결함이 발생하지 않는다.
  • 프레임 내에 있는 데이터는 바뀌지 않지만 최근 사용된 데이터 순서에 따라서 (3, 2, 5) → (5, 3, 2)로 교체된다.

Hit가 일어나도 캐시에 남아있는 데이터 순서가 바뀌지 않는 FIFO 알고리즘과 다르게 LRU는 Hit가 일어남에 따라 프레임 내에 있는 데이터의 순서가 바뀐다는 것을 확인할 수 있다.