세세한 부분을 많이 놓치기는 하겠지만, 간략히 말해 컴퓨터는 다음과 같이 동작합니다. 메모리에서 데이터를 프로세서로 가지고 와서 사칙 연산, 대소 비교 등과 같이 어떠한 작업을 수행한 다음 결과값을 다시 메모리에 저장합니다. 여기서 많은 경우 프로세서의 수행 시간에 비해 메모리 접근 시간이 훨씬 오래 걸리기 때문에 전체 수행 시간의 병목은 얼마나 많이 메모리에 접근했는가로 결정됩니다.
캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 자그마하지만 처리 속도는 빠른 기억 장치를 의미합니다. 프로세서가 어떤 자료를 필요로 할 때 만약 캐시 메모리에 최신의 그 자료가 존재한다면 프로세서는 굳이 주 메모리에서 자료를 가지고 올 필요가 없습니다. 캐시 메모리에서 바로 가지고 오면 되니까요. 이는 컴퓨터의 수행 시간을 줄이는 데 큰 공헌을 하며 이제는 하나의 표준으로 자리잡았습니다.
캐시 메모리의 크기를 무한정 키우는 것은 금전적으로 큰 부담이 되는 일이기 때문에 그 크기는 대체로 주 메모리의 크기보다 훨씬 작습니다. 따라서 캐시 메모리를 사용하면 필연적으로 다음과 같은 문제를 마주하게 됩니다. 바로 어떤 자료를 캐시 메모리에 저장하고 싶은데 더이상 공간이 없는 경우입니다. 이를 해결하려면 이미 저장된 자료 중 무언가를 버려야 합니다. 이때 무엇을 버릴지 선택하는 것은 꽤 중대한 사항입니다. 생각 없이 막 버렸는데 그 자료가 다음번에 바로 호출될 수도 있죠. 그런 일이 너무 자주 발생한다면 캐시 메모리는 없느니만 못한 것이 됩니다.
만약 이후에 어떤 자료가 호출될지 모두 알고 있는 상황이라면 이 문제는 쉽게 해결할 수 있습니다. 바로 현재 캐시 메모리에 남아있는 자료 중에서 가장 늦게 호출될 자료를 버리는 것입니다. 이는 최적의 전략이라고 잘 알려져 있습니다. 증명은 약간 까다롭지만 직관적으로 받아들이기 힘든 전략은 아닙니다. 캐시 메모리 상에서 가장 마지막까지 쓰이지 않을 자료를 삭제하는 것이니까요. 이 전략을 우리는 longest forward distance(LFD)라고 부릅니다.
하지만 우리가 마주하는 문제는 그다지 간단하지 않습니다. 우리는 미래에 어떤 자료가 언제 사용될지 모릅니다. 따라서 지금까지 들어온 정보만 가지고 캐시 메모리에서 어떤 자료를 제거할지 결정해야 합니다. 여러 방법이 있겠지만 컴퓨터 과학을 전공하신다면, 특히 운영체제 과목을 수강하셨다면 least recently used(LRU)에 대해서 익숙하실 것입니다. 이는 현재 캐시 메모리 상에서 사용된 지 가장 오래된 자료를 버리는 전략입니다. 이번 글에서는 유명한 LRU가 얼마큼 괜찮은 알고리즘인지를 공부해 보도록 하죠.
문제 정의
함께 고민할 문제를 좀더 적확히 정의해 보도록 하겠습니다. 주 메모리와 캐시 메모리에서 자료가 전송되고 저장되는 단위를 페이지(page)라고 하겠습니다. 사용할 서로 다른 페이지의 총 개수를 \(n\)이라고 하고 각 페이지는 \(1, \cdots, n\)으로 부르겠습니다. 여기서 페이지의 크기는 모두 동일하다고 가정하겠습니다. 캐시 메모리는 최대 \(k\) 개의 페이지를 저장할 수 있다고 하겠습니다. 프로세서가 호출하는 페이지를 시간의 순서대로 나열한 것을 \(\sigma\)라고 하겠습니다. 예를 들어 \[ \sigma = 1, 4, 3, 1, 5, 2, 4, 1, 3, 1, 5, 1, 2, 2, 3 \tag{1} \]라고 하면, 프로세서는 맨 처음 페이지 \(1\)을 호출하고 다음에는 페이지 \(4\), 그다음에는 페이지 \(3\)을 호출합니다. 문제를 좀더 간단히 만들기 위해 이 모델에서는 프로세서가 캐시 메모리랑만 소통한다고 가정하겠습니다. 즉, 페이지가 호출되면 반드시 캐시 메모리에 그 페이지를 올려 놓아야 합니다.
우리의 목표는 캐시 메모리를 최대한 적은 횟수로 수정하면서 프로그램을 문제 없이 돌리는 것입니다. 여기서 캐시 메모리를 수정한 횟수가 애매할 수 있는데, 이 글에서는 이를 캐시 메모리에서 페이지가 삭제된 횟수로 하겠습니다. 엄밀히 따지면 어떤 페이지를 캐시 메모리에서 삭제한 횟수보다 어떤 페이지를 캐시 메모리에 저장한 횟수가 더 중요합니다. 왜냐하면 캐시 메모리에서 삭제하는 작업은 캐시 메모리 안에서만 동작하면 되는 일이지만, 캐시 메모리에 쓰는 작업은 주 메모리로부터 해당 페이지를 받아 오는 작업이 필요하기 때문입니다. 하지만 두 수치의 차이는 \(k\)를 넘지 않습니다.(왜 그럴까요?) 따라서 삭제된 횟수를 세는 것이 그렇게 나쁘지 않은 목표임을 알 수 있습니다.
Marking algorithm
LRU를 바로 분석하기에 앞서 재미있는 알고리즘을 하나 소개하겠습니다. 이는 일견 멍청해 보이는 알고리즘일 수 있지만, 나중에 LRU를 분석하는 데 큰 도움이 됩니다. 바로 LRU가 이 알고리즘으로 표현될 수 있기 때문입니다.
이 알고리즘을 설명하기 위해서는 입력의 나열 \(\sigma\)를 적절하게 분할해 주어야 합니다. 이를 하는 방법은 다음과 같습니다. 맨 처음부터 시작해서 처음으로 서로 다른 페이지의 개수가 \(k\)를 초과할 때 그전까지를 하나의 묶음으로 생각합니다. 그러고는 그 위치에서 위 작업을 반복하죠. 이 작업은 미래의 정보를 알 필요 없이 그때그때 만들어줄 수 있습니다. 이렇게 얻은 묶음 하나하나를 \(k\)-phase라고 부르겠습니다. 실례로 \(k = 3\)이라고 했을 때, 예시 1의 \(\sigma\)를 \(k\)-phase로 분할한 것은 다음과 같습니다. \[ \begin{array}{rl} \sigma_1 & := 1, 4, 3, 1, \\ \sigma_2 & := 5, 2, 4, \\ \sigma_3 & := 1, 3, 1, 5, 1, \\ \sigma_4 & := 2, 2, 3. \end{array} \]
이 phase의 특징 중 하나는 마지막 phase를 제외하고는 모두 서로 다른 \(k\) 개의 페이지로 이루어져 있다는 것입니다. 위 예시에서도 \(\sigma_1, \sigma_2, \sigma_3\)는 모두 세 개의 서로 다른 페이지로 이루어져 있고 마지막 \(\sigma_4\)만 두 개로 이루어져 있는 것을 확인하시기 바랍니다.
이제 알고리즘을 구경해 보죠.
알고리즘 1. Marking algorithm
초기 입력: 페이지 \( \{ 1, \cdots, n \} \), 캐시 메모리 크기 \(k\)
출력: 호출된 모든 페이지를 그때마다 캐시 메모리에 올려 두는 전략
- 모든 페이지 \(p = 1, \cdots, n\)에 대해, \( \mathsf{mark}(p) \in \{0, 1\} \)이라는 boolean flag를 만든다.
- 매번 새로운 페이지 \( \sigma(t) \)가 호출되면 다음을 수행한다.
- 만약 이 페이지가 어떤 \(k\)-phase의 시작이면, \( \mathsf{mark}(p) \gets 0 \quad \forall p = 1, \cdots, n \).
- 만약 캐시 메모리에 여분의 공간이 없는데 \( \sigma(t) \)가 캐시 메모리 상에 존재하지 않는 경우, \(\mathsf{mark}(p) = 0\)인 \(p\)를 지우고 \( \sigma(t) \)를 저장한다. 단, 그러한 \(p\)가 여러 개 존재하는 경우에는 아무거나 지운다.
- \( \mathsf{mark}(\sigma(t)) \gets 1 \).
어떻게 동작하는지 간단하게 살펴보면, 이 알고리즘은 모든 페이지에 \( \mathsf{mark}(p) \)라는 boolean flag를 둡니다. 이는 새로운 \(k\)-phase가 시작될 때마다 \(0\)으로 초기화되죠. 캐시 메모리에 공간이 없는데 호출된 페이지가 그 위에 없다면 마킹되지 않은 임의의 페이지를 하나 지우고 거기에 저장을 합니다. 그러고는 호출된 페이지를 마킹하죠.
일단 이 알고리즘이 오류를 일으키지 않는다는 것부터 보이죠. 가장 문제가 되는 부분은 단계 2-b입니다. 마킹되지 않은 \(p\)가 존재하지 않는 경우는 없을까요? 이는 \(k\)-phase의 정의를 통해 보일 수 있습니다.
정리 1. 알고리즘의 정확성
알고리즘 1은 정확히 동작한다. 다시 말해, 단계 2-b에서 캐시 메모리에 여분의 공간이 없는데 \( \sigma(t) \)가 그 위에 없는 경우 \( \mathsf{mark}(p) = 0\)인 \(p\)가 적어도 하나는 존재한다.
[증명] 어떤 \(k\)-phase 안에서 \( \mathsf{mark}(p) = 1 \)이려면 그 phase 중에 호출이 한 번이라도 되었어야 합니다. 그 안에서 호출되는 서로 다른 페이지의 개수는 \(k\)를 넘지 않습니다. \( \sigma(t) \)가 캐시 메모리에 존재하지 않았다는 뜻은 지금까지 나오지 않았다는 뜻이므로 그전까지 호출된 서로 다른 페이지의 개수는 \(k - 1\)을 넘지 않습니다. 여기서 캐시 메모리에 여분의 공간이 없었다면 최소한 한 페이지는 마킹이 되어 있지 않았다는 뜻입니다. ■
이제 이 알고리즘이 얼마큼 경쟁적인(competitive) 전략을 제시하는지 알아보겠습니다. 먼저 한 \(k\)-phase 안에서 이 알고리즘은 그다지 많은 페이지를 삭제하지 않는다는 것을 보이겠습니다.
정리 2. \(k\)-phase 안에서 marking algorithm의 최대 삭제 횟수
임의의 \( k \)-phase에서 알고리즘 1은 최대 \(k\) 번 페이지를 삭제한다.
[증명] \(k\)-phase의 정의를 사용하면 어렵지 않게 보일 수 있습니다. 한 \(k\)-phase에는 서로 다른 페이지의 개수가 \(k\)를 넘지 않습니다. 그러므로 기존의 페이지도 \(k\) 번 이하 지워지게 됩니다. ■
마지막으로 어떤 알고리즘이라도 \(k\)-phase에서는 최소 한 번 이상 삭제를 해야한다는 것을 보이겠습니다.
정리 3. \(k\)-phase 안에서 알고리즘의 최소 삭제 횟수
이 문제를 해결하는 임의의 알고리즘에 대해, 마지막을 제외한 어떤 \(k\)-phase의 첫 번째 페이지가 처리된 이후부터 그다음 \(k\)-phase의 첫 번째 페이지가 처리될 때까지 최소한 한 번은 캐시 메모리에서 페이지를 삭제한다.
[증명] 마지막이 아닌 어떤 \(k\)-phase의 첫 번째 페이지 \(p\)를 시작으로 그다음 \(k\)-phase의 첫 번째 페이지 \(q\)가 호출될 때까지 그동안 호출된 페이지 중 서로 다른 것의 개수는 \(k\)-phase의 정의에 의해 \(k + 1\)이 됩니다. 우리가 고려하는 모델에서는 어떤 페이지가 호출되면 반드시 그 페이지는 당시의 캐시 메모리 위에 존재해야 합니다. 그런데 캐시 메모리의 크기는 \(k\)이므로 어떤 알고리즘이든지 간에 분명히 \(p\)가 처리된 이후부터 \(q\)를 호출할 때까지 한 번 이상은 페이지를 삭제해야 합니다. ■
이제 위 정리들을 활용하면 알고리즘의 경쟁성을 분석할 수 있습니다.
정리 4. Competitiveness of marking algorithm
알고리즘 1은 이 문제를 해결하는 \(k\)-competitive algorithm이다.
[증명] 정리 1을 통해 이 알고리즘의 정확성을 보였습니다. 정리 2와 3에 의해 (마지막이 아닌) 매 \(k\)-phase마다 이 알고리즘은 최대 \(k\) 번의 페이지를 삭제하고, 어떤 알고리즘이라도 그동안 최소 한 번은 페이지를 삭제해야 하므로, 알고리즘이 최종적으로 삭제하는 횟수를 \(\mathsf{ALG}\), 최적의 삭제 횟수를 \( \mathsf{OPT} \)라고 할 때, \[ \mathsf{ALG} \leq k \cdot \mathsf{OPT} + k \]를 만족합니다. 여기서 마지막에 \(k\)가 더해진 이유는 마지막 \(k\)-phase에서 이 알고리즘은 최대 \(k\) 번 삭제할 수 있지만 최적해에서는 삭제하지 않을 수도 있기 때문입니다. ■
LRU와 marking algorithm의 관계
드디어 우리의 이번 글의 주 관심사인 LRU로 돌아오겠습니다. 과연 LRU의 경쟁성은 어떨까요? 위 절에서 이미 스포하기도 했고, 그러지 않았더라도 쉽게 예상하셨으리라고 생각합니다. 바로 LRU는 일종의 marking algorithm입니다. 따라서 동일한 경쟁비(competitive ratio)를 가지게 됩니다. 이를 증명해 보도록 하겠습니다.
정리 5. LRU와 marking algorithm
LRU는 일종의 marking algorithm이다. 다시 말해, LRU가 어떤 페이지 \(p\)를 캐시 메모리에서 삭제할 때, \( \mathsf{mark}(p) = 0\)이다.
[증명] 귀류법으로 보이겠습니다. LRU가 \(p\)를 삭제할 때 대신 저장할 페이지를 \(q\)라고 하겠습니다. 만약 \(\mathsf{mark}(p) = 1\)이라면 이는 \(p\)와 \(q\)가 어떤 같은 \(k\)-phase에 들어있다는 뜻입니다. 그런데 지금 \(q\)를 넣지 못해서 \(p\)를 제거하려고 하고 있으므로 \(q\)는 현재 캐시 메모리에 저장된 페이지 모두와 다릅니다. 여기서 \(p\)는 가장 오래전에 호출된 페이지면서 \( \mathsf{mark}(p) = 1\)이므로 현재 캐시 메모리에 저장된 페이지 모두 \( \mathsf{mark} \) 값이 \(1\)이 됩니다. 이는 현재 캐시 메모리에 저장된 \(k\) 개의 페이지가 하나의 \(k\)-phase에 들어가 있다는 뜻이죠. 그런데 그 모두와 상이한 \(q\)가 이 \(k\)-phase에 속하면 이 phase에는 총 \(k+1\) 개의 서로 다른 페이지가 존재하게 됩니다. 이는 \(k\)-phase의 정의에 모순이 됩니다. ■
마치며
이 글에서는 유명한 페이지 교체 알고리즘인 LRU가 \(k\)-competitive algorithm이라는 것을 알아보았습니다. 이를 위해서 좀더 일반적인 알고리즘인 marking algorithm에 대해서 공부하고 그것의 \(k\)-competitiveness를 보임으로써 원하는 바를 증명할 수 있었죠. 이것이 의미하는 바를 잘 살펴보면, 캐시 메모리의 크기가 작은 경우에 LRU는 최적해에 매우 근접하는 전략이지만 반대로 큰 경우에는 잘 못한다는 것을 알 수 있습니다. 아무래도 그럴 것 같은 게, 캐시 메모리가 크다는 뜻은 선택지가 늘어났다는 뜻이고 따라서 우리는 잘못된 선택을 하기는 쉬운 반면 최적해에서는 큰 캐시 메모리를 십분 활용해 먹을 것이기 때문이죠.
사실 marking algorithm의 조건에 부합하는 모든 알고리즘은 \(k\)-competitive 합니다. 한 가지 간단한 예시로, 캐시 메모리에 더이상 저장할 공간이 없을 때마다 현재 저장된 내용을 모두 삭제하는 전략도 \(k\)-competitive algorithm입니다. LRU보다 훨씬 멍청하게 동작하는 것처럼 보이지만 실제로 캐시 메모리를 초기화하는 작업은 알고리즘 1의 단계 2-a에 대응합니다. 이 전략을 flush when full(FWF)라고 부르기도 합니다.
LRU의 경쟁비는 \(k\)보다 좋아질 수 없습니다. 간단한 예시로, \(k = 3\)일 때, \[ \sigma = 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, \cdots \]로 입력이 주어지면 \(3\)의 경쟁비를 갖게 된다는 것을 확인할 수 있습니다. 이는 직접 해보시기 바랍니다. 이 논의를 조금만 더 확장하면 실제로는 marking algorithm 자체가 \(k\) 보다 좋은 경쟁비를 가질 수 없다는 것을 보일 수 있습니다.
다만 임의의 모든 deterministic algorithm이 \(k\)보다 좋은 경쟁비를 가질 수 없는지는 잘 모르겠습니다. 아마도 연구된 게 있을 것 같기는 한데 나중에 알게되면 공유해 보도록 하겠습니다. 대개 그렇듯이 randomness를 도입하면 더 좋은 경쟁비를 얻을 수 있습니다. 최근에 공부하는 중인데 포스팅할 만하다고 판단되면 이것도 다음에 다루어 보도록 하겠습니다. 읽어 주서셔 고맙습니다.
참조
[1] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 2005.
'온라인 알고리즘 > Caching' 카테고리의 다른 글
| 최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm) (0) | 2023.03.25 |
|---|---|
| LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm) (0) | 2023.03.18 |
