LRU 알고리즘 : 리스트를 활용해서 구현해 봅시다.

 고급 자료구조 이론에 들어가기 전에, 복습 겸 코딩 테스트에 자주 나오는 LRU 알고리즘을 간단하게 구현해 보도록 하겠습니다. 어떠한 페이지를 찾아야 한다고 해 봅시다. 메모리에서. 그런데, 그 페이지가 없어요. p라는 페이지가. 이 때, 메모리에서 어떤 페이지를 제거해야 할까요?

 

 가장 오래 전에 사용이 된 것을 제거하는 것을 LRU 알고리즘이라고 합니다. 약어로는 Least Recently Used한 것을 제거하는 것이죠. 보통, 이러한 문제를 만났을 때, 저는 map 2개로 많이 코딩하라고 이야기를 합니다. 그런데, STL을 쓸 수 없는 환경에서는 어떻게 해야 할까요? 코딩하기도 어려운 레드 블랙 트리를 500줄 가까이 작성해야 할까요? 아니면 포인터의 향연에서 벗어날 수 없는 skip list를 작성해야 할까요?

 

 

---

 여기서, 문제 상황을 재정의 해 봅시다. 우리는 최근에 접근한 시간이, 가장 작은 것을 remove 하면 됩니다. 그러면 우리가 알아야 할 것은 단 하나입니다. 가장 최근에 접근한 시간과, 그것의 메모리 주소. 그러면 우선 순위 큐로 접근이 가능해 보입니다. 최근에 접근한 시간이 가장 오래된 것을, 꺼내기만 하면 되니까요.

 

 그런데, 아직 배우지도 않은 priority_queue를 쓰지 않고서도, 충분히 그러한 기능을 구현할 수 있습니다. 심지어 더 빠르게 구현할 수 있어요. 어떻게 하면 좋을까요? 일단, 일반적인 array는 아닌 거 같습니다. 왜냐하면, 이것은 삭제를 할 때 매우 오래 걸리기 때문입니다. remove 할 위치를 빠르게 찾을 수 있는 경우에, 삽입과 삭제가 매우 빠른 자료 구조가 무엇이 있었더라? List가 있었습니다. 맞습니다. List로 구현하시면 됩니다.

 

 

 그런데 문제가 하나 있습니다. 이 그림에서 3을 제거하기 위해서는 어떻게 해야 하나요? Head하고 Tail만 알고 있는 경우에는, 3까지 찾기는 해야 할 겁니다.

 

 

 그러면, 이 친구를 찾는데 3번의 탐색이 필요합니다. n개의 원소가 있다면, 최악의 경우 n회 가량을 search 해야 한다는 것입니다. 이렇게 하기에는 너무 끔찍해 보입니다.

 

 

 물론, LRU 알고리즘을 수행할 때, 중간의 원소를 제거해야 하는 상황이 없다고 생각하실 수도 있어요. 그런데, 메모리에 페이지 p가 있는 상황에서 p에 접근했다면, 메모리에 있는 page들 중에서는 p가 가장 최근에 접근한 것입니다. 그렇기 때문에, 중간에 있었던 p를, 가장 최근의 위치로 끌고 와야 합니다.

 

 그렇기 때문에, 중간에 있는 p를 제거하고, 다시, p를 최근의 위치에 저장을 하는 것입니다. 이 때 중간에서 remove 하는 연산이 일어나야 합니다.

 

 

---

 Random 접근이 가능한 배열을 List처럼 쓰면 어떤가요? 즉, List[x]는 x 이전에 접근한 페이지 번호와, x 이후에 접근한 페이지 번호를 저장하면 되는 것입니다.

 

 

 그렇다면 자료구조는 이렇게 선언하면 될 듯 싶네요. 이제 LRU 알고리즘에 필요한 기능들을 보기 전에, 설계를 해 봅시다.

 

 

 일단 Dummy는 0번하고 2^20 - 1로 설정해 놓습니다. 문제 상황에 따라 다르게 설정하셔도 무난합니다. 이들은 각각 더미 둘을 선언하기 위한 것입니다. 물론, 10^6 + 1과 같은 것을 tail로 설정하셔도 되고요. 이들 말고는 prev와 next는 모두 -1로 설정합니다. 이는 더 이상 해당 방향으로는 노드가 없다. 는 정보를 알려주기 위함이라고 생각하셔도 좋겠습니다.

 

 

 먼저, 2에 접근했습니다. 그러면 2가 List에 들어가야 할 겁니다. 다음에 4번 페이지에 접근을 했는데요. 4가 제일 최신 것입니다. 최근에 접근한 것은 tail에 가깝고, 오래 전에 접근한 것은 head에 가깝습니다. 그러면 4는 어디에 추가되어야 하나요? 2와 tail 사이에 추가되어야 합니다. 여기서, 2번은 tail의 이전 녀석입니다.

 

 

 다음에, 3을 추가했다면 어떻게 하면 좋을까요? tail의 prev는 4입니다. 4번과 tail 사이에 3을 넣으면 될 거에요.

 

 

 여기까지는 그렇게 어렵지 않아 보입니다. 뒤에다가만 추가하는 것이기 때문입니다.

 

 

---

 문제는 페이지 크기가 p일 때, 어떻게 t번 페이지에 대한 정보를 삭제할 거냐는 겁니다. t번이 예전에 ti초에 접근했는데, 다시 ti'초에 접근했다면 ti<ti'일 거고, ti'초가 된 순간 t번이 페이지에서 제거가 되고, t가 맨 뒤에 추가가 될 거니까. 제거 부분만 잘 어떻게 하면 될 건데요.

 

 

 

 메모리에 들어간 페이지의 갯수 자체는 그리 어렵지 않아요. 그러니, 페이지가 꽉 찬 상태인지를 알아내는 것 또한 어렵지는 않습니다. 그런데, 어떠한 페이지 t번에 대한 정보를 제거해야 할 때가 문제인데요. 이 때, List를 배열 형태로 관리하면, t번 page에 대한 정보에, 손쉽게 접근을 할 수 있습니다. 예를 들어, 다음과 같이 메모리에 페이지들이 올라갔다고 생각해 봅시다.

 

 

 그러면, 4번을 메모리에서 제거하기 위해서는 어떻게 하면 좋을까요? 일단 우리는 list[4]에 있는 prev와 next의 값들을 읽어옵니다. 이들은 각각 2와 3일 겁니다. 이들을 각각 pp, cc라고 합시다.

 

 

 그러면 list[pp]의 next는 cc가 되어야 하고, list[cc]의 prev는 pp가 되어야 합니다. 이 둘을 이으면, 다음과 같이 됩니다. 이 때, list[4]의 prev와 next는 어떤 값이 되면 좋을까요? -1을 가리키면 좋을 것입니다. 그러면 실제로 n번이 메모리에 올라가 있는지 없는지는 prev와 next가 -1인지 아닌지만 검사하면 될 거에요.

 

 그 이후로 4가 tail 이전에 추가된 경우에는 어떠한 경우인가요? page fault가 나지 않고, hit이 난 상황입니다. 즉, 이전에 4라는 것에 접근을 했고, 4가 메모리 상에서 지워지지 않은 상태에서 다시 4에 접근한 상황입니다.

 

 

 그러면 이렇게 처리하면 됩니다. 메모리에 들어갈 수 있는 페이지의 크기가 3인 상황인데, 5가 들어왔다. 그러면 어떻게 하면 될까요? 그러면 가장 오래 전에 접근한 페이지 먼저 찾아야 하는데요.

 

 

 그것은 2번 page임을 알 수 있어요. head에 가까울 수록, 오래 전에 접근한 것이라고 했기 때문입니다. 최근에 접근한 것일수록 tail에 가까운 곳에 add가 된다고 했었고요. 그렇기 때문에 2를 제거하고, 4와 tail 사이에 5를 추가하면 됩니다.

 

 

 List를 활용하면 어렵지 않게 LRU도 쉽게 구현할 수 있었습니다. 이 아이디어만 잘 활용하면, 메모리에 있는 페이지 갯수가 꽉 차서 무언가를 제거해야 한다 정도는, if문 한 줄로 쉽게 처리할 수 있어요. priority_queue로 처리한다면 O(log(page_size))만큼 걸립니다. 하지만, 이것을 List로 잘 처리한다면, O(1)에 처리할 수 있습니다.

 

 여기서 질문 하나 드리겠습니다. 페이지 번호가 10^9 이하인 경우에는 어떻게 하면 좋을까요? 동적으로 처리해야 하는 경우에는 어떻게 하면 좋을까요? 단, access 연산은 최대 20만번이라고 가정하고, 번호는 random하게 들어온다고 해 봅시다.