페이지 교체 알고리즘 feat. LRU

페이지 교체 알고리즘이요??…

아니 무슨 그냥 수학적 알고리즘 접근도 어렵던데, 메모리 관련 알고리즘까지?….

사실 코딩테스트 문제를 풀다가 LRU를 통하여 문제의 해답을 구하라는 카카오 문제가 있었습니다!

“LRU?? 그게 뭔데 씹덕아”

근데 이걸 모르면 못푸는 문제였습니다 헿….그래서 LRU에 대하여 서칭을 한 다음에 문제를 풀었죠

그때 서칭했던 LRU에 대한 정보들이 생각보다 흥미롭고 재밌어서 따로 정리를 해보고자 합니다!

---

페이지 교체 알고리즘

• 저희가 사는 지구에는 자원이 한정적이죠? 최대한 효율적으로 자원을 사용하기 위해서 세상에는 많은 규칙과 법이 존재합니다.그 알고리즘 중에서 제한된 한도내에서 최고의 효율을 얻기 위한 알고리즘을 “페이지 교체 알고리즘” 이라고 합니다!
• 그 중에서 컴퓨터의 자원 또한 역시 무한적이지 않은거죠….그 자원내에서 최고의 효율을 얻기 위한것이 바로 알고리즘입니다!
• 컴퓨터에는 휘발성 메모리(RAM) 와 비휘발성 메모리(SSD, HDD) 가 있죠? 그 중에서 RAM이 데이터를 처리하는 속도가 빠르기 때문에블록으로 구성해서 운용하는데 여기서 말하는 블록을 “페이지” 라고 부릅니다!
• 보조 기억장치로 부터 데이터를 램에 저장을 해놓고 필요할때 램에 있는 데이터를 바로 꺼내서 사용을 하니 속도가 빠릅니다. 이 때 램을 같은 크기의
• cpu가 계산을 할 때 필요한 데이터가 “페이지”에 있다면 cache hit 이라고 부르며, 없을 경우에는 데이터를 페이지로 옮겨와서 계산을 하는데 이 때를 cache miss 라고 부릅니다!
• hit일때와 miss일때는 당연히 시간의 차이가 나기 때문에 보다 빠른 연산을 위해서는 페이지에 여러 정보중에 어떤 정보를 오래 저장해 놓아야 하는지가
• 매우 중요한 문제입니다! 램의 자원이 같을때 어떤 방식의 알고리즘을 쓰냐에 따라 속도의 차이는 무궁무진 합니다.

페이지 교체 알고리즘의 예시

1. FIFO (First In First Out)
2. LRU (Least Recently Used)
3. LFU (Least Frequently Used)
4. 등등….

---

자 그러면 기본 개념은 알았으니 “LRU” 는 어떤 알고리즘 일까요?

• 가장 오랫동안 사용하지 않은 페이지를 제거하겠다는 알고리즘입니다! 이 알고리즘의 원리는 가장 오랫동안 사용하지 않은 페이지는 앞으로도
• 사용할 확률이 적다는 것입니다!
• 구현하기 위해서는 페이지에 저장된 데이터가 언제 사용되었는지를 알 수 있게하는 부분을 구현해서 제일 오랫동안 참조되지 않은 페이지를 제거하는 방법입니다.
• 또 다른 방법으로는 페이지에 데이터를 큐형식으로 저장하는것입니다. 페이지 내에 필요한 데이터가 존재한다면 데이터를 페이지 내에서 삭제하고 맨 위로
• 다시 올리고, 만약에 데이터가 존재하지 않는다면 맨 아래에 있는 데이터를 삭제하는 과정을 통해서 LRU를 구현할 수 있습니다!