최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm)

Photo by Liam Briese on Unsplash

삼 년 전, 저는 유명한 온라인 최적화(online optimization) 문제 중 하나인 온라인 캐싱(online caching)을 소개하고, 이를 해결하는 유명한 방법인 LRU(least recently used) 알고리즘의 경쟁성을 증명하였습니다.

[캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까?

글의 서론에서 저는 캐시 미스가 발생했을 때 캐시 메모리 상에서 가장 마지막에 사용되는 자료를 삭제하는 정책인 LFD(longest forward distance) 알고리즘이 최적의 전략이라는 것을 언급하였습니다. 하지만 이에 대한 증명은 보이지 않았죠. 삼 년이 지난 현재, 개인적으로 한번 증명에 도전해 봤는데 생각보다 간단하더군요. 그 증명 방법을 이번 포스트에서 보여 드리고자 합니다.

문제 정의 및 알고리즘 소개

간략히 문제부터 정의하죠. 우리에게는 수 개의 페이지를 담을 수 있는 캐시 메모리가 주어집니다. 프로세서는 매 시각 페이지를 하나씩 호출합니다. 다만, 프로세서가 캐시 메모리와만 소통한다고 가정하겠습니다. 따라서 매번 어떤 페이지를 호출한다면 해당 페이지가 캐시 메모리에 올라가 있어야 합니다.

 

만약 캐시 메모리에 그 페이지가 이미 있었다면 아무런 문제가 없습니다. 하지만 반대로 캐시 메모리에 그 페이지가 없다면 주 메모리에서 해당 페이지를 캐시 메모리에 옮겨 와야 합니다. 문제는 캐시 메모리에 공간이 부족할 수 있다는 것입니다. 이때 우리는 캐시 메모리에서 단위 비용을 지불하여 한 페이지를 지우고 호출된 페이지를 올려 두어야 합니다. 여기서 우리의 목표는 당연히 페이지 교체를 최소로 하는 전략을 찾는 것입니다.

 

이번 글에서 다룰 알고리즘은 LFD입니다. 고안자의 이름을 따서 벨라디의 알고리즘(Bélády's algorithm)이라고도 불리는데요. 이는 다음과 같이 동작합니다.

캐시 메모리에 공간이 부족하여 페이지를 교체해야할 때, 가장 나중에 호출되는 페이지 (중 아무나 하나)를 교체한다.

가장 나중에 호출되는 페이지를 알기 위해서는 당연히 미래를 완벽히 알고 있어야 합니다. 따라서 이 알고리즘은 오프라인 알고리즘(offline algorithm)입니다.

증명

이제 LFD가 가장 적은 교체 횟수를 보이는 최적의 알고리즘임을 증명해 보겠습니다. 증명의 방법은 탐욕 알고리즘(greedy algorithm)을 증명할 때 사용하는 정석적인 방법 중 하나인 "exchange argument"입니다. 이와 관련된 전반적인 내용이 궁금하신 분들은 아래 포스트를 참고하시기 바랍니다.

탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms)

본 증명을 소개하기에 앞서 한 가지 작업을 소개하겠습니다. 만약 어떤 알고리즘이 입력된 페이지가 캐시 메모리에 존재하지 않을 때에만 저장된 페이지 중 하나를 지우고 현재 들어온 페이지를 올려 놓을 때, 우리는 이 알고리즘을 게으르다(lazy)고 부릅니다. 우리는 어떤 게으르지 않은 알고리즘이 주어졌을 때, 이보다 많지 않은 횟수의 페이지를 교체하는 게으른 알고리즘을 만들 수 있습니다. 이를 먼저 증명해 보죠.

 

만약 어떤 알고리즘이 게으르지 않다고 해 봅시다. 그러면 분명 입력으로 들어온 페이지와 캐시 메모리에 올린 페이지가 서로 다른 시각 \(s\)가 존재합니다. 그때 알고리즘이 올린 페이지를 \(p\), 이 페이지 대신 캐시 메모리에서 제거한 페이지를 \(p'\), 마지막으로 해당 \(p\)가 이후 캐시 메모리에서 내려간 시각을 \(t\)라고 하겠습니다. 만약 \(s\)에서 \(t\)까지 \(p\)가 한 번도 불리지 않았다면 우리는 \(s\)에서 \(t\)까지 \(p\)를 올리는 대신 \(p'\)을 그대로 두는 것으로 페이지 교체 횟수를 줄일 수 있습니다.

 

이제 페이지 \(p\)가 \(s\)에서 \(t\) 사이에 한 번은 입력이 된 경우를 생각해 봅시다. 처음으로 입력이 된 때를 시각 \(x\)라고 하겠습니다. 이제 시각 \(s\)에서 \(p'\)을 내리고 \(p\)를 올리는 대신, 이 작업을 시각 \(x\)에서 진행하는 상황을 생각해 봅시다. 어차피 \(s\)에서 \(x\) 사이에는 \(p\)가 입력되지 않을 것이므로 수정 후의 동작도 유효한 동작입니다. 수정 전후로 페이지 교체의 횟수 차이는 없습니다. 위 수정 작업을 계속 진행한다면 종국에는 게으른 알고리즘을 만들 수 있습니다. (사실, \(p'\)이 없는 경우나 \(t\)가 존재하지 않는 경우도 생각해야 합니다. 이는 어렵지 않으니 직접 확인해 보시기 바랍니다.)

 

게으른 알고리즘을 만드는 과정에서 한 가지 주목할 부분이 있습니다. 바로 페이지를 올리는 시점이 늦어지기만 한다는 것입니다. 이 사실은 본 증명에서도 요긴하게 활용됩니다.

 

이제 본 증명을 시작하죠. 우리는 어떤 게으른 최적 알고리즘에서 시작하여 이를 차례로 수정할 것입니다. 이때 매번 수정을 거칠 때마다 페이지 교체 횟수는 증가하지 않고, 게으르면서, \(\mathsf{LFD}\)와 처음으로 다르게 동작하는 구간은 계속 미뤄지기만 하도록 만들 것입니다. 이를 계속 적용하면 언젠간 \(\mathsf{LFD}\)와 동일해지는 때가 올 것입니다. 그런데 매번 페이지 교체 횟수는 증가하지 않는다고 하였으므로 \(\mathsf{LFD}\) 또한 최적이 된다는 것을 보일 수 있습니다. 따라서 이제 증명에서 남은 것은 어떤 게으른 알고리즘 \(\mathsf{ALG}\)가 주어졌을 때, 페이지 교체 횟수는 증가하지 않고, 게으르면서, \(\mathsf{LFD}\)와는 더 오랜 시간동안 동일하게 동작하는 \(\mathsf{ALG'}\)을 만드는 것입니다.

 

\(\mathsf{ALG}\)와 \(\mathsf{LFD}\)가 처음으로 다르게 동작하는 때를 고려하겠습니다. 그때를 시각 \(t\)라고 하겠습니다. 그 전까지 \(\mathsf{ALG}\)와 \(\mathsf{LFD}\)는 동일한 캐시 메모리 상태를 갖고 있을 것입니다. 가정에서 \(\mathsf{ALG}\)는 게으르다고 하였고, \(\mathsf{LFD}\) 또한 게으르므로 두 알고리즘이 다르게 동작한 때는 분명 캐시 미스가 일어난 때일 것입니다. 그 시각 \(t\)에 \(\mathsf{ALG}\)는 페이지 \(j\)를, \(\mathsf{LFD}\)는 페이지 \(j'\)을 제거했다고 합시다. \(\mathsf{LFD}\) 알고리즘의 특성에 의해 분명 \(j\)보다 \(j'\)이 더 늦은 시각에 입력이 될 것입니다. (논의를 간단히 하기 위해 시각 \(t\) 이후에 \(j\)와 \(j'\)이 모두 입력된다고 가정하겠습니다. 그렇지 않은 경우 증명이 어떻게 될지는 직접 생각해 보시기 바랍니다.)

 

이제 \(\mathsf{ALG}\)와 거의 비슷하게 동작하는 \(\mathsf{ALG'}\)을 정의해 봅시다. 시각 \(t\)가 되기 전까지는 \(\mathsf{ALG}\)와 동일하게 동작합니다. 대신 시각 \(t\)에 \(\mathsf{ALG'}\)은 \(\mathsf{ALG}\) 대신 \(\mathsf{LFD}\)와 같이 페이지 \(j'\)을 캐시 메모리에서 제거합니다. 시각 \(t\)가 끝났을 무렵 분명 \(\mathsf{ALG}\)와 \(\mathsf{ALG'}\)이 유지하는 캐시 메모리는 \(j\)와 \(j'\)만 차이가 있습니다. 정확히는 \(\mathsf{ALG}\)는 \(j'\)을, \(\mathsf{ALG'}\)은 \(j\)를 캐시 메모리에 두고 있습니다.

 

시각 \(t\) 이후 \(\mathsf{ALG'}\)의 동작은 다음과 같습니다. 만약 페이지 \(j\)가 입력으로 들어오기 전까지 \(\mathsf{ALG}\)가 \(j'\)을 캐시 메모리에서 삭제하여 새로운 페이지를 받는다면, \(\mathsf{ALG'}\)은 \(j\)를 삭제하고 해당 새로운 페이지를 받습니다. 그러면 \(\mathsf{ALG'}\)과 \(\mathsf{ALG}\)는 이후 동일한 캐시 메모리를 가질 것입니다. 그때부터 두 알고리즘의 동작을 동일하게 하면 \(\mathsf{ALG}\)와 \(\mathsf{ALG'}\)이 동일한 횟수의 페이지를 교체했다는 것을 보일 수 있습니다.

 

그렇지 않고 \(j\)가 들어오기 전까지 \(\mathsf{ALG}\)가 \(j'\)이 아닌 페이지만 가지고 페이지 교체를 행하였다고 합시다. 그러면 \(\mathsf{ALG'}\)도 동일한 페이지를 교체하도록 만듭니다. 그러면 페이지 \(j\)가 입력으로 들어올 때 \(\mathsf{ALG}\)와 \(\mathsf{ALG'}\)은 \(j\)와 \(j'\)을 제외하고는 동일한 페이지를 캐시 메모리에 갖고 있을 것입니다. 만약 그때 \(\mathsf{ALG}\)가 \(j'\)을 캐시 메모리에서 지우고 \(j\)를 넣었다고 합시다. 그러면 \(\mathsf{ALG'}\)은 아무것도 하지 않아도 됩니다. 반대로 이번에는 \(\mathsf{ALG}\)가 \(j'\)이 아닌 다른 페이지 \(\ell\)을 지운 후 \(j\)를 넣었다고 합시다. 이때는 \(\mathsf{ALG'}\)으로 하여금 페이지 \(\ell\)을 지우고 \(j'\)을 캐시 메모리에 올리도록 만듭니다. 그러면 두 알고리즘의 캐시 메모리 상태가 동일해 진다는 것을 확인할 수 있습니다. 이 시점부터 두 알고리즘의 동작을 동일하게 만들면 \(\mathsf{ALG'}\)이 \(\mathsf{ALG}\)보다 적거나 같은 횟수의 페이지 교체를 행한다는 것을 이끌어 낼 수 있습니다.

 

증명을 마치기 전에 한 가지 고쳐야할 부분이 있습니다. 바로 \(\mathsf{ALG'}\)이 게으르지 않을 수 있다는 점입니다. 예를 들어, \(j\)가 들어왔을 때 \(\mathsf{ALG}\)가 \(j'\)이 아닌 \(\ell\)을 교체한 경우 \(\mathsf{ALG'}\)은 \(\ell\)을 \(j'\)과 교체합니다. 앞에서 우리는 게으르지 않은 알고리즘을 게으른 알고리즘으로 바꾸는 작업을 확인했습니다. 그 작업에서 중요한 성질 중 하나는 바로 페이지를 교체하는 시점이 늦어지기만 한다는 것이었습니다. 시각 \(t\)까지 \(\mathsf{ALG'}\)은 \(\mathsf{LFD}\)와 동일하게 게을리 동작하므로 변함이 없습니다. 따라서 게으르게 변환하는 작업을 거친 후에도 \(\mathsf{ALG'}\)은 적어도 시각 \(t\)까지는 \(\mathsf{LFD}\)와 동일하게 동작하게 됩니다.

 

이로써 \(\mathsf{ALG}\)보다 많지 않은 페이지를 교체하지만 \(\mathsf{LFD}\)와는 더 오랜 시간동안 동일하게 동작하는 게으른 알고리즘 \(\mathsf{ALG'}\)을 만들었습니다. 이를 계속 적용하면 \(\mathsf{LFD}\)가 최적임을 증명할 수 있습니다.

마치며

이것으로 미래의 입력을 모두 아는 경우 최소의 횟수로 페이지를 교체하는 LFD 알고리즘에 대해서 알아 보았습니다. 이 알고리즘을 증명한 이유는 이 알고리즘이 요새 온라인 최적화 세계에서 가장 뜨거운 분야 중 하나인 예측이 주어진 알고리즘(algorithms with prediction) 분야에서 요긴하게 활용되기 때문입니다. 다음에는 이와 관련하여 포스팅을 해 보도록 하겠습니다.

 

읽어 주셔서 고맙습니다.