정보처리산업기사, 정보처리기사 - LRU(Least Recentely Used) 알고리즘 집중 탐색!!

※ 공부 내용의 복습 개념으로 정리된 글입니다. 

 

LRU(Least Recentely Used) 알고리즘

LRU(Least Recentely Used) 알고리즘은 컴퓨터 시스템에서 메모리 관리 기법 중 하나입니다.

주로 캐시 메모리 관리에 사용되며, 가장 오랫동안 사용되지 않은 페이지를 우선적으로 교체하는 방식입니다.

즉 최근에 사용된 페이지는 계속 남겨두고, 사용 빈도가 낮은 페이지를 제거하여 새로운 페이지를 메모리에 할당합니다.

 

LRU 알고리즘의 동작 원리

1. 페이지 참조
   • CPU가 특정 페이지를 참조할 때마다 해당 페이지의 최근 사용 시간을 기록합니다.
2. 페이지 교체 필요
   • 새로운 페이지를 메모리에 로드해야 할 때, 현재 메모리에 로드된 페이지 중 가장 오랫동안 사용되지 않은 페이지를 찾아 교체합니다.
3. 시간 업데이트
   • 페이지가 참조될 때마다 해당 페이지의 최근 사용 시간을 업데이트하여 가장 최신의 정보를 유지합니다.

 

 

LRU 알고리즘의 장단점

• 장점
  • 최근에 사용된 데이터를 캐시에 유지하여 캐시 히트율을 높일 수 있습니다.
  • 구현이 비교적 간단하며, 다양한 방법으로 최적화가 가능합니다.
• 단점
  • 시간 복잡도가 효율적인 구현을 위해 복잡한 자료구조가 필요할 수 있습니다.
  • LRU 알고리즘이 항상 최적의 성능을 보장하는 것은 아니며, 특정 패턴의 데이터 접근에서는 성능이 저하될 수 있습니다.

 

LRU 알고리즘 예제

4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정합니다.

다음 순서로 페이지 참조가 발생할때, LRU페이지 교체 알고리즘을 사용할 경우 몇 번의 페이지 결함이 발생할까요?

 

페이지 참조 순서 : 1, 2, 3, 1, 2, 4, 1, 2, 5

 

참조페이지	1	2	3	1	2	4	1	2	5
tail	1	1	1	2	3	3	3	3	4
주기억장치		2	2	3	1	1	2	4	1
			3	1	2	2	4	1	2
haed						4	1	2	5
페이지부재	1	2	3			4			5

 

• 처음에는 주기억장치가 전부 비어 있어 1이 없기 때문에 페이지 부재가 일어납니다. (총 페이지 부재 : 1)
• 2가 들어올때에도 주기억장치에는 2가 없어 페이지 부재가 일어납니다. (총 페이지 부재 : 2)
• 3도 없기 때문에 페이지 부재가 일어납니다. (총 페이지 부재 : 3)
• 두번째 1이 들어올 때에는 주기억장치에 1이 들어있기 때문에 페이지 부재가 일어나지 않고, 가장 최신으로 사용한 페이지가 됩니다.
• 두번째 2가 들어올 때에도 주기억장치에 2가 존재하기 때문에 페이지 부재가 일어나지 않고, 가장 최신으로 사용한 페이지가 됩니다.
• 4는 존재하지 않기 때문에 페이지 부재가 일어납니다.  (총 페이지 부재 : 4)
• 세번째 1이 들어 올때도 1이 존재하기 때문에 페이지 부재가 일어나지 않고, 가장 최신으로 사용한 페이지가 됩니다.
• 세번째 2도 만찬가지로 존재하기 때문에 페이지 부재가 일어나지 않고, 가장 최신으로 사용한 페이지가 됩니다.
• 5는 존재하지 않기 때문에 가장 오래 사용한 3이 제거되면서 5가 들어오며 페이지 부재가 발생합니다. 
  (총 페이지 부재 : 5)

이렇게 총 페이지 교체가 총 5번 수행하게 되어 정답은 5회 입니다.