LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm)

Photo by Laura Ockel on Unsplash

캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 위치한 용량은 작지만 속도는 빠른 저장 장치를 의미합니다. 이 장치의 용도는 어떤 프로세스가 동작할 때 많이 접근하는 자료를 저장해 두는 것이죠. 프로세스가 특정한 자료를 필요로 할 때 해당 자료가 최신의 상태로 캐시 메모리에 존재한다면, 주 메모리에 직접 접근하지 않고 캐시 메모리에 접근하여 자료를 가져옴으로써 상당한 시간적 이득을 꾀할 수 있습니다.

 

프로세스가 호출하는 자료의 단위를 페이지(page)라고 부르겠습니다. 만약 프로세스가 어떤 페이지를 필요로 하는데, 최신의 해당 페이지가 캐시 메모리에 존재하는 때를 캐시 히트(cache hit), 그렇지 않을 때를 캐시 미스(cache miss)라고 부릅니다. 전자의 경우에는 캐시 메모리의 자료를 곧장 참조하면 되므로 빠른 시간에 수행할 수 있지만, 후자의 경우에는 주 메모리에서 해당 페이지를 읽어 와야 하므로 상당한 시간이 소요됩니다. 그러니 당연히 우리는 캐시 히트의 수는 늘리고 캐시 미스의 수는 최소화하고 싶겠죠. 만약 캐시 메모리의 용량이 프로세스가 필요로 하는 페이지를 몽땅 올릴 수 있을 정도로 충분하다면 캐시 미스는 일어나지 않을 것입니다. 문제는 캐시 메모리의 용량이 상대적으로 매우 작다는 점입니다. 그러므로 어떤 페이지를 캐시 메모리에 올려 두려고 할 때 캐시 메모리는 이미 가득 찬 경우가 부지기수일 터입니다. 이때, 캐시 메모리에 저장된 페이지 중 어떤 페이지를 지울지 결정하는 것은 캐시 메모리의 성능과 직결되는 대단히 중요한 문제입니다.

 

벌써 3년 전, 저는 유명한 페이지 교체 전략 중 하나인 LRU(least recently used)를 분석하는 글을 적었습니다. 이 전략은 페이지 교체가 필요할 때 가장 오랫동안 사용되지 않은 페이지를 지우는 방법입니다. 그 글에서 저는 이 전략이 사실은 보다 일반적인 알고리즘인 마킹 알고리즘(marking algorithm)의 하나의 구현에 해당함을 보였습니다. 또한, 모든 마킹 알고리즘은 캐시 메모리의 용량을 \(k\)라고 했을 때 \(k\)-경쟁 알고리즘(\(k\)-competitive algorithm)이라는 사실을 보였습니다. 이로써 LRU의 이론적인 경쟁성도 증명할 수 있었죠. 관련하여 궁금하신 분들은 아래 글을 참고하시기 바랍니다.

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

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

글의 말미에는 다음과 같은 질문을 던졌습니다. 이는 컴퓨터 과학의 숙명과도 같은 질문입니다.

• 과연 더 적은 캐시 미스를 보장하는 알고리즘이 존재하는가?

이번 포스트에서 이 질문에 대한 긍정적인 답변을 드리도록 하겠습니다. 좀더 엄밀히 말하자면, 훨씬 적은 횟수의 캐시 미스를 이론적으로 기대할 수 있는 알고리즘이 존재합니다. 제가 '기대'라는 표현을 사용한 것에서 유추하셨겠지만, 이 알고리즘은 내부에 확률 시행이 존재하는 랜덤 알고리즘(randomized algorithm)입니다. 결론을 미리 말씀 드리자면, 이 알고리즘은 입력이 어떻게 주어지든지 간에 평균적으로 \(2 \ln k\)의 경쟁비를 가집니다. 이는 기존의 경쟁비인 \(k\)보다 지수적으로 좋은 수치라는 것을 확인하시기 바랍니다.

 

글의 제목은 마치 본문에서 소개할 알고리즘이 LRU보다 모든 면에서 뛰어나다는 인상을 주는 것 같습니다. 제목이 자극적이라는 것을 인정하는 바입니다. LRU는 (이론적으로는 부족할지언정) 실제로는 굉장히 좋은 성능을 보이며, 이 때문에 페이지 교체 알고리즘의 표준으로 자리잡았습니다. 반면 본문에서 소개할 알고리즘은 랜덤 알고리즘이기 때문에 필연적으로 상당한 비용을 필요로 하는 랜덤 연산(random operation)을 수행해야 합니다. 그러므로 현실적으로는 본문의 알고리즘이 LRU보다 항상 좋다고 말하기 어렵겠다는 생각이 듭니다. 다만 이론적으로는 더 좋은 것이 분명하고 이를 분석하는 것 또한 흥미롭기에 (약간 '어그로'가 있지만) 현재의 제목으로 글을 게재하였습니다. 독자분들의 너그러운 양해를 바랍니다.

문제 정의

함께 고민할 문제를 다시 한 번 정의해 보겠습니다. 우리에게는 최대 \(k\) 개의 페이지를 저장할 수 있는 캐시 메모리가 주어집니다. 프로세서에는 여러 프로세스들이 수행되고 있으며, 매 \(t\) 번째 시각마다 페이지 \( \sigma(t) \)를 호출합니다. 프로세서는 캐시 메모리와만 소통한다고 가정하겠습니다. 따라서, 매 \(t\) 번째 시각이 끝날 때 캐시에는 \(\sigma(t)\)가 저장되어 있어야 합니다. 우리의 목표는 가능한 적은 횟수로 캐시 메모리를 수정하여 프로세스가 매 시각 요구하는 페이지를 올바르게 제공하는 것입니다. 여기서 캐시 메모리를 수정한 횟수는 이전 포스트에서 논의한 바와 같이 어떤 페이지를 캐시 메모리에서 삭제한 횟수로 정하겠습니다.

\(k\)-페이즈와 마킹 알고리즘

이전 포스트에서는 위 문제를 \(k\)의 경쟁비로 해결하는 마킹 알고리즘을 소개하였습니다. 이번 글에서도 마킹 알고리즘이 매우 요긴하게 사용될 예정이므로 다시 정의해 보도록 하겠습니다.

 

이 알고리즘을 이해하기 위해서는 우선 \(k\)-페이즈(\(k\)-phase)에 대해서 먼저 알아야 합니다. 이는 앞에서부터 처음으로 등장한 서로 다른 페이지의 수가 \(k\) 개를 초과하기 직전까지를 매번 분할한 것을 의미합니다. 지난 포스트의 예시를 그대로 가져오겠습니다. 만약 \(k = 3\)이고 \[ \sigma = 1, 4, 3, 1, 5, 2, 4, 1, 3, 1, 5, 1, 2, 2, 3 \]이라고 하였을 때, 이를 \(k\)-페이즈로 분할한 것은 \[ \sigma = 1, 4, 3, 1 \mid 5, 2, 4 \mid 1, 3, 1, 5, 1 \mid 2, 2, 3 \]와 같습니다.

 

이제 마킹 알고리즘을 소개하겠습니다. 알고리즘이 이전과는 다른 방식으로 기술되었습니다. 이전에는 모든 페이지마다 \( \mathsf{mark} \) 비트를 두었는데, 사실 이는 불필요한 작업일 뿐더러 프로세서와 캐시 메모리의 동작을 제대로 담아내지 못한 처사였습니다. 아래에서는 해당 부분을 보완하여 작성하였습니다. 캐시 메모리의 한 단위에는 페이지를 저장할 공간과 함께 \( \mathsf{mark} \) 비트를 갖고 있습니다.

알고리즘 1. 마킹 알고리즘 (Marking algorithm)

---

초기 입력: 캐시 메모리 크기 \(k\)

출력: 호출된 모든 페이지를 그때마다 캐시 메모리에 올려 두는 전략

 

1. 매 \(t\) 번째 시각에 페이지 \( \sigma(t) \)가 호출되면 아래를 수행한다.
   1. 만약 \( \sigma(t) \)가 캐시 메모리에 이미 존재하면 아무것도 하지 않는다.
   2. 만약 캐시 메모리에 빈 공간이 있으면 거기에 \( \sigma(t)  \)를 기록하고 그것의 \( \mathsf{mark} \) 비트를 올린다.
   3. 만약 \( \sigma(t) \)가 캐시 메모리에 존재하지 않으면서 빈 공간도 없으면 아래를 수행한다.
      1. 만약 이 페이지가 어떤 \(k\)-페이즈의 시작이면, 캐시 메모리의 모든 \( \mathsf{mark} \) 비트를 내린다.
      2. \( \mathsf{mark} \) 비트가 내려간 페이지를 하나 찾는다. 만약 여러 개 존재하면 아무거나 고른다.
      3. 앞에서 고른 페이지가 저장된 공간에 \( \sigma(t) \)를 기록하고 그것의 \( \mathsf{mark} \) 비트를 올린다.

위 알고리즘은 올바르게 동작합니다. 크게 두 가지를 보이면 됩니다. 하나는 단계 1-c-i에서 호출된 페이지가 어떤 \(k\)-페이즈의 시작인지 판단할 수 있는지입니다. 매번 현재까지 호출된 서로 다른 페이지를 기록하는 것으로 쉽게 수행할 수 있습니다. 다음은 단계 1-c-ii에서 \( \mathsf{mark} \) 비트가 내려간 페이지가 존재하는지입니다. 이는 아래 정리에서 보이겠습니다.

정리 1. 마킹 알고리즘의 정확성

---

매 \(t\) 번째 시각에 \(\sigma(t)\)가 호출되었을 때, \( \sigma(t) \)가 캐시 메모리에 존재하지 않으면서 캐시 메모리에 빈 공간이 없으면 단계 1-c-ii를 수행할 때 반드시 \( \mathsf{mark} \) 비트가 내려간 페이지가 적어도 하나는 존재한다.

[증명] 만약 \( \sigma(t) \)가 어떤 \(k\)-페이즈의 시작이면 단계 1-c-i에 의해 모든 단위의 \( \mathsf{mark} \) 비트가 내려가 있으므로 명제가 성립합니다. 그렇지 않다면 그때의 \(k\)-페이즈의 시작부터 \( \sigma(t) \)가 들어오기 직전까지 아무리 많아도 \( k - 1 \) 개의 서로 다른 페이지가 호출되었다는 뜻입니다. \(k\)-페이즈의 시작에 모든 \( \mathsf{mark} \) 비트가 내려가므로 \( \sigma(t) \)가 들어오면 적어도 하나는 \(\mathsf{mark} \) 비트가 내려간 채입니다. ■

랜덤 마킹 알고리즘

마킹 알고리즘은 간단하지만 결정적인 단점이 있습니다. 바로 결정론적(deterministic)이라는 점입니다. 특히 마킹 알고리즘은 단계 1-c-ii에서 \( \mathsf{mark} \) 비트가 내려간 페이지 중 하나를 임의로 고릅니다. 이 결정을 악용한다면 우리는 어렵지 않게 마킹 알고리즘이 \(k\)보다 좋은 경쟁비를 가질 수 없도록 하는 적응형 상대방(adaptive adversary)을 구상할 수 있습니다. 결정론적 알고리즘의 경쟁비를 분석하기 위해 적응형 상대방을 상정하여도 괜찮은 이유는 아래 글에서 확인하실 수 있습니다.

2020.03.14 - [온라인 알고리즘/Basic] - 온라인 알고리즘 (Online Algorithm)

온라인 알고리즘 (Online Algorithm)

그러한 적응형 상대방을 만드는 방법에 대해서는 생략하도록 하겠습니다. 한번 직접 해 보시는 것을 추천합니다.

 

어떻게 하면 더 좋은 알고리즘을 만들 수 있을까요? \(\mathsf{mark}\) 비트가 내려간 페이지 중에서 어떤 페이지가 삭제될지를 상대방이 모르게 한다면 아무래도 더욱 경쟁적인 알고리즘이 될 것을 기대할 수 있겠습니다. 아래는 이 아이디어를 정형화한 것입니다. 알고리즘 1과 달라진 부분을 빨간색 굵은 글씨로 표현하였습니다.

알고리즘 2. 랜덤 마킹 알고리즘 (Randomized marking algorithm)

---

초기 입력: 캐시 메모리 크기 \(k\)

출력: 호출된 모든 페이지를 그때마다 캐시 메모리에 올려 두는 전략

 

1. 매 \(t\) 번째 시각에 페이지 \( \sigma(t) \)가 호출되면 아래를 수행한다.
   1. 만약 \( \sigma(t) \)가 캐시 메모리에 이미 존재하면 아무것도 하지 않는다.
   2. 만약 캐시 메모리에 빈 공간이 있으면 거기에 \( \sigma(t)  \)를 기록하고 그것의 \( \mathsf{mark} \) 비트를 올린다.
   3. 만약 \( \sigma(t) \)가 캐시 메모리에 존재하지 않으면서 빈 공간도 없으면 아래를 수행한다.
      1. 만약 이 페이지가 어떤 \(k\)-페이즈의 시작이면, 캐시 메모리의 모든 \( \mathsf{mark} \) 비트를 내린다.
      2. \( \mathsf{mark} \) 비트가 내려간 페이지를 하나 찾는다. 만약 여러 개 존재하면 균등한 확률로 하나를 고른다.
      3. 앞에서 고른 페이지가 저장된 공간에 \( \sigma(t) \)를 기록하고 그것의 \( \mathsf{mark} \) 비트를 올린다.

이 알고리즘이 곧 이번 포스트에서 제가 분석하고자 하는 알고리즘입니다. 이 알고리즘은 알고리즘 1에서 임의로 선택하던 것을 균등한 확률로 선택하는 것으로 바꿨을 뿐이므로 알고리즘 1의 하나의 구현에 해당합니다. 따라서 정리 1에 의해 알고리즘 2가 정확하게 동작한다는 사실은 쉽게 이끌어 낼 수 있습니다.

랜덤 마킹 알고리즘 경쟁성 분석

이제 이 알고리즘의 경쟁성을 분석해 보겠습니다. 이를 위해서 몇 가지를 정의하겠습니다.

• \(P\)는 주어지는 입력의 \(k\)-페이즈의 총 개수입니다. 총 페이지의 수가 아님을 주의하세요. 일반성을 잃지 않고 \(P \geq 2\)라고 하겠습니다. \(P = 1\)의 경우는 위 알고리즘이 캐시 미스를 일으키지 않습니다.
• 주어지는 입력을 최적으로 해결하는(즉, 가장 적은 횟수로 캐시 메모리를 수정하는) 어떤 알고리즘을 하나 고정하겠습니다. 이때 \(\mathsf{OPT}\)는 이 알고리즘이 캐시 메모리를 수정한 총 횟수라고 하겠습니다. 각 \(i = 1, \cdots, P\)에 대해, 이 알고리즘이 \(i\) 번째 \(k\)-페이즈에서 수정한 횟수를 \( \mathsf{OPT}_i \)라고 부르겠습니다. 최적의 알고리즘을 하나 고정했으므로 이 값은 고정된 값이며, \[ \mathsf{OPT} = \sum_{i = 1}^P \mathsf{OPT}_i \]를 만족합니다.
• 알고리즘 2가 캐시 메모리를 수정한 총 횟수를 \( \mathsf{ALG} \)라고 하겠습니다. 위 항목과 비슷하게, 각 \(i = 1, \cdots, P\)에 대해, 알고리즘 2가 \(i\) 번째 \(k\)-페이즈에서 수정한 횟수를 \( \mathsf{ALG}_i \)라고 부르겠습니다. 이  값들은 모두 단계 1-c-ii에 의해 값이 변할 수 있는 확률 변수(random variable)입니다. 다만 \[\mathsf{ALG} = \sum_{i = 1}^P \mathsf{ALG}_i\]를 만족한다는 것을 확인하시기 바랍니다.
• 각 \(i = 1, \cdots, P\)에 대해, \(i\) 번째 \(k\)-페이즈에서 등장하는 서로 다른 페이지의 집합을 \(S_i\)라고 부르겠습니다. 예를 들어, 앞에서 소개한 \(\sigma\)에 대해서는 \[ \begin{array}{ll} S_1 & := \{1, 4, 3\}, \\ S_2 & := \{5, 2, 4\}, \\ S_3 & := \{1, 3, 5\}, \\ S_4 & := \{2, 3\} \end{array} \]가 됩니다. 일부러 순서를 고려하여 적었습니다. \(S_i\)의 페이지가 등장한 순서가 아래에서 중요하게 쓰이기 때문입니다.
• 첫 번째를 제외한 \(i\) 번째 \(k\)-페이즈에서 호출된 어떤 페이지 \(a \in S_i\)가 이전 \(i - 1\) 번째 \(k\)-페이즈에서도 호출된 경우라면(즉, \(a \in S_i \cap S_{i - 1}\)), 이 페이지를 오래된 페이지(stale page)라고 부르겠습니다. 반대로 직전 \(k\)-페이즈에서 호출되지 않았다면(즉, \(a \in S_i \setminus S_{i - 1}\)), 이 페이지를 새로운 페이지(clean page)라고 부르겠습니다.
• 어떤 자연수 \(x\)에 대해, \(H_x\)를 \(x\) 번째 조화수(harmonic number)라고 합니다. 그 정의는 \[ H_x := 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{x} \]입니다. \(H_x \approx \ln x\)임은 잘 알려진 사실입니다.

다음은 최적의 알고리즘이 적어도 몇 번의 수정을 수행해야 하는가에 관한 정리입니다.

정리 2. 최적해의 하한

---

\( \displaystyle \mathsf{OPT} \geq \frac{1}{2} \sum_{i = 2}^P |S_i \setminus S_{i - 1}|\)

[증명] 각 \(i = 2, \cdots, P\)에 대해, \( i - 1 \) 번째 \(k\)-페이즈와 \(i\) 번째 \(k\)-페이즈를 함께 고려해 보겠습니다. 이 두 \(k\)-페이즈에서 호출되는 서로 다른 페이지의 총 개수는 \[ |S_{i - 1} \cup S_i| = |S_{i - 1}| + |S_i \setminus S_{i - 1}| = k +|S_i \setminus S_{i - 1}| \]입니다. 여기서 두 번째 등식은 \( i - 1 \) 번째 \(k\)-페이즈는 마지막 \(k\)-페이즈가 아니어서 성립합니다. 그런데 캐시 메모리의 크기는 \(k\)이므로 어떤 페이지 교체 알고리즘이라도 이 두 \(k\)-페이즈를 거치는 동안에는 적어도 \(|S_i \setminus S_{i - 1}|\) 번의 교체가 이루어져야 합니다. 따라서 \[ |S_i \setminus S_{i - 1}| \leq \mathsf{OPT}_{i - 1} + \mathsf{OPT}_i \]가 성립합니다. 위 식을 모든 \(i = 2, \cdots, P\)에 대해서 더하면 정리의 부등식을 얻을 수 있습니다. ■

 

위 정리가 요긴한 이유는 알고리즘 2의 경쟁비를 구할 때 실제 \( \mathsf{OPT} \)의 값 대신 각 \(k\)-페이즈에서 호출된 새로운 페이지의 개수에 의거할 수 있기 때문입니다. 실지로 우리는 다음의 정리를 증명할 예정입니다.

정리 3. 각 \(k\)-페이즈의 기대 수정 횟수

---

각 \(i = 2, \cdots, P\)에 대해, \( \mathbb{E} \left[ \mathsf{ALG}_i \right] \leq H_k \cdot |S_i \setminus S_{i - 1}| \)를 만족한다.

이 정리의 증명이 이번 글의 핵심입니다. 다만, 이는 약간 미루겠습니다. 대신, 정리 3이 참이라면 정리 2와 함께 알고리즘 2의 경쟁성을 증명할 수 있다는 것을 먼저 보이겠습니다.

정리 4. 알고리즘 2의 경쟁비

---

알고리즘 2는 랜덤 \(2H_k\)-경쟁 알고리즘이다. 자세히 말해, \[ \mathbb{E} \left[ \mathsf{ALG} \right] \leq 2H_k \cdot \mathsf{OPT} \]를 만족한다.

[증명] 지금까지 확인한 정보를 토대로 아래 식을 유도할 수 있습니다. \[ \mathbb{E} \left[ \mathsf{ALG} \right] = \sum_{i = 1}^P \mathbb{E} \left[ \mathsf{ALG}_i \right] \leq \sum_{i = 2}^P H_k \cdot |S_i \setminus S_{i - 1}| \leq 2 H_k \cdot \mathsf{OPT} \] 여기서 등식은 기댓값의 선형성(linearity of expectation)에 의해, 첫 번째 부등식은 \( \mathsf{ALG}_1 = 0 \)이라는 사실과 정리 3에 의해, 두 번째 부등식은 정리 2에 의해 유도됩니다. ■

정리 3 증명

증명을 위해 \(i\) 번째 \(k\)-페이즈를 하나 고정하겠습니다. (단, \(i \geq 2\)입니다.) 앞에서 논의한 대로 우리는 이 \(k\)-페이즈 안에서 두 번 이상 호출된 페이지는 어차피 캐시 히트할 것이므로 고려할 필요가 없습니다. 따라서 이 \(k\)-페이즈가 \(S_i\)의 페이지로만 이루어져 있다고 가정하겠습니다. 또한 논의를 간단히 하기 위해 \( |S_i| = k \)라고 가정하겠습니다. 그렇지 않은 경우는 마지막 \(k\)-페이즈일 때뿐인데, 이는 아래의 분석을 확장하면 그리 어렵지 않게 보일 수 있습니다.

 

이번 \(k\)-페이즈에 정확히 \[ S_i : a_1,\; a_2,\; \cdots,\; a_k \]의 순서로 페이지가 들어왔다고 하겠습니다. 이 중에서 새로운 페이지의 개수를 \(\ell := |S_i \setminus S_{i - 1}|\)이라고 하겠습니다. 아래는 최악의 시나리오가 무엇인지를 알려 줍니다. 아래 증명은 커플링 기법(coupling method)을 비격식적인 표현으로 풀어서 적은 것임을 밝힙니다.

정리 5. 최악의 상황

---

이번 \(k\)-페이즈에서 \(\ell\) 개의 새로운 페이지가 처음에 들어오고 나머지 \(k - \ell\) 개의 오래된 페이지가 들어오는 경우가 평균적으로 캐시 미스를 가장 많이 발생시킨다.

[증명] 만약 \(S_i : a_1, a_2, \cdots, a_k\)에 \(a_j \in S_{i - 1} \cap S_i\)는 오래된 페이지인데 \(a_{j + 1} \in S_i \setminus S_{i - 1}\) 이 새로운 페이지인 어떤 \(j\)가 존재한다고 하겠습니다. 이제 이 두 페이지의 순서를 바꾼 \(S'_i\)를 생각해 보겠습니다. 다시 말해, \[ S'_i : a'_1, \cdots, a'_j, a'_{j + 1}, \cdots, a'_k  = a_1, \cdots, a_{j + 1}, a_j, \cdots, a_k\]의 순서로 들어온다고 하겠습니다. 첫 \(j-1\) 페이지에 대해서 알고리즘이 두 입력에 대해 동일하게 동작했다고 가정하겠습니다. 이제 다음 두 가지 경우를 생각해 봅시다.

 

경우 1. \(j\) 번째 페이지를 처리하려고 할 때, \(a_j\)가 캐시 메모리에 없을 때. 이 경우, \(S_i\)에서나 \(S'_i\)에서나 \(j\) 번째 페이지와 \(j + 1\) 번째 페이지에서 모두 캐시 미스를 일으킵니다. 따라서 알고리즘이 두 입력에 대해 동일하게 동작하도록 사상(mapping)시킬 수 있습니다. 따라서 캐시 미스의 횟수 차이는 없습니다.

 

경우 2. \(j\) 번째 페이지를 처리하려고 할 때, \(a_j\)가 캐시 메모리에 있을 때. \(S_i\)에서의 동작을 먼저 살펴 보겠습니다. 여기서 \(a_j\)는 캐시 히트를 하게 됩니다. 따라서 알고리즘은 \(a_j\)의 \(\mathsf{mark}\) 비트를 올릴 것입니다. 이 작업이 끝난 후 \(\mathsf{mark}\) 비트가 내려가 있는 페이지의 집합을 \(T\)라고 하겠습니다. 그러면, \(a{j + 1}\)은 새로운 페이지이므로 \(T\) 중에 하나를 균등한 확률로 골라 교체할 것입니다.

 

반대로 이번에는 \(S'_i\)에서의 동작을 생각해 보겠습니다. 앞에서 \(j - 1\) 번째 페이지까지는 알고리즘이 \(S_i\)와 \(S'_i\)에 대해 동일하게 동작했다고 가정하였습니다. 따라서 \(a'_j = a_{j + 1}\)이 들어왔을 때 분명 \(T \cup \{a_j\}\)의 페이지들이 \(\mathsf{mark}\) 비트가 내려가 있는 상태일 것입니다.

 

이제 \(S_i\)에서의 각 사건을 \(S'_i\)에서의 사건들과 다음의 방식으로 연결 지어 보도록 하겠습니다. \(T\)의 각 페이지 \(b \in T\)에 대해, 알고리즘이 \(S_i\)에서 \(a_{j + 1}\)을 처리하면서 대신 \(b\)를 제외한 사건을 \(\mathcal{E}_b\)라고 하겠습니다. 우리는 이 사건을 \(S'_i\)에서 \(a'_j\)를 처리할 때 \(b\)를 제외하는 사건 \(\mathcal{E}'_{b,1}\)과 \(a'_j\)를 처리할 때는 \(a'_{j + 1} = a_j\)를 버리고 다음 \(a'_{j + 1}\)을 처리할 때 \(b\)를 제외하는 사건 \(\mathcal{E}'_{b,2}\)와 연관 지어 보도록 하겠습니다.

 

먼저 모든 \(b \in T\)에 대해 \(\mathcal{E}'_{b, 1}\)들과 \( \mathcal{E}'_{b, 2} \) 들은 서로 배타적(mutually exclusive)이면서 전체를 포괄하는(collectively exhaustive) 사건들이라는 사실을 확인하시기 바랍니다. 만일 \(a'_j\)를 처리할 때 알고리즘이 \(T\) 중 하나가 삭제되면 \(a'_{j + 1} = a_j\)를 처리할 때는 해당 페이지의 \(\mathsf{mark}\) 비트만 올리고 끝나게 됩니다. 반대로 \(a'_j\)를 처리할 때 \(a'_{j + 1}\)을 캐시 메모리에서 지우면 다음 페이지 \(a'_{j + 1}\)을 처리할 때 \(\mathsf{mark}\) 비트가 내려간 페이지는 정확히 \(T\)와 같습니다.

 

이제 연관 지은 \(\mathcal{E}_b\)와 \(\mathcal{E}'_{b, 1} \cup \mathcal{E}'_{b, 2}\) 사이에 어떤 관계가 있는지 확인해 봅시다. 먼저, \[ Pr[\mathcal{E}'_{b, 1} \cup \mathcal{E}'_{b, 2}] = Pr[\mathcal{E}'_{b, 1}] + Pr[\mathcal{E}'_{b, 2}] = \frac{1}{|T| + 1} + \frac{1}{|T| + 1} \cdot \frac{1}{|T|} = \frac{1}{|T|} = Pr[\mathcal{E}_b] \]임을 확인하시기 바랍니다. 따라서 두 사건이 일어날 확률은 동일합니다. 또한 \(\mathcal{E}_b\)든지 \(\mathcal{E}'_{b, 1} \cup \mathcal{E}'_{b, 2}\)든지 \(j + 1\) 번째 페이지를 처리한 후에는 \(S_i\)든 \(S'_i\)든 정확히 \(T \setminus \{b\}\)의 페이지가 \(\mathsf{mark}\) 비트가 내려간 상태일 것입니다. 그러므로 두 입력에서 모두 \(j+2\) 번째 페이지부터는 동일한 캐시 미스가 발생할 것입니다. 따라서 \(j\) 번째와 \(j+1\) 번째 페이지에서 발생한 캐시 미스에 집중해 봅시다. \(S_i\)는 정확히 한 번이 일어납니다. 반대로 \(S'_i\)는 \(\mathcal{E}'_{b, 2}\) 때문에 한 번 이상 일어날 수 있죠.

 

이를 모두 종합하면 \(S'_i\)에서 일어난 캐시 미스의 횟수가 \(S_i\)에서보다 평균적으로 많다는 결론을 내릴 수 있습니다. 이 작업을 새로운 페이지 앞에 오래된 페이지가 없을 때까지 반복하는 것으로 정리의 증명이 완성됩니다. ■

 

위 정리를 통해 우리는 \(S_i\)가 \(a_1, \cdots, a_\ell\)은 새로운 페이지로 \(a_{\ell + 1}, \cdots, a_k\)는 오래된 페이지로 이루어져 있다고 가정할 수 있습니다. 이 상황에서 다음 정리는 각각의 오래된 페이지가 캐시 미스를 일으킬 확률을 알려 줍니다.

정리 6. 각 오래된 페이지가 캐시 미스를 일으킬 확률

---

정리 5를 가정했을 때, 각 \(j = \ell + 1, \cdots, k\)에 대해, \(a_j\)가 캐시 미스를 일으킬 확률은 \(\frac{\ell}{k - j + \ell + 1}\)이다.

[증명] 알고리즘이 \(a_j\)를 처리할 때 캐시 미스를 일으키는 상황을 다음의 확률 시행으로 변환하여 해석해 보겠습니다. 속을 알 수 없는 어떤 바구니에 총 \(k\) 개의 공이 들어 있습니다. 각 공에는 \(S_{i - 1}\)의 각 페이지가 새겨져 있다고 합시다. 이제 이 바구니에서 공을 총 \(\ell\) 개를 복원하지 않고 뽑으려고 합니다. 이는 \(S_i\)에서 \(a_1, \cdots, a_\ell\)이 들어왔을 때 캐시 미스가 발생하는 것에 대응시키면 편합니다. 또한 뽑힌 공은 캐시 미스가 발생했을 때 캐시 메모리에서 제거되는 페이지에 대응합니다.

 

이 확률 시행에는 한 가지 특이한 점이 있습니다. 언젠간 \(a_{\ell + 1}, \cdots, a_k\) 중 하나인 \(a_x\)를 뽑았다고 하겠습니다. 그런데 만약 \(a_x\)가 \(S_i\)에서 \(a_j\)보다 먼저 들어오는 페이지라면, 즉 \(x < j\)라면, 우리는 공을 뽑는 횟수를 차감하지 않습니다. 이러한 특이한 규칙을 두는 이유는 다음과 같습니다. 앞에서 뽑힌 공은 캐시 메모리에서 제거되는 페이지에 대응한다고 했습니다. 그런데 \(x<j\)인 \(a_x\)가 언젠간 뽑혔다면, 분명 알고리즘이 \(a_k\)를 처리할 때 캐시 미스가 발생하게 되어 \(a_j\)를 제거할 수도 있기 때문입니다. 반대로 \(x > j\)인 \(a_x\)이거나 \(S_{i - 1} \setminus S_i\)의 페이지라면 그럴 걱정이 없으므로 그대로 공을 뽑는 횟수를 차감하면 됩니다.

 

그러므로 우리의 목표는 위 확률 시행에서 \(a_j\)가 뽑힐 확률을 구하는 것입니다. 그런데 \(a_{\ell + 1}, \cdots, a_{j - 1}\) 중 하나를 뽑은 경우에는 공을 뽑는 횟수를 차감하지 않는다고 하였으므로, 처음부터 해당 공은 없다고 생각하여도 무방합니다. 따라서 바구니에 총 \(k - j + \ell + 1\) 개의 공이 있고, 이 중에서 \(\ell\) 개를 비복원 추출했을 때 \(a_j\)가 뽑힐 확률을 계산하면 됩니다. 이 확률은 정확히 \(\frac{\ell}{k - j + \ell + 1}\)입니다.^[ㄱ] ■

 

이제 정리 3을 증명할 수 있습니다. 정리 5에 의해 캐시 미스가 평균적으로 가장 많이 발생하는 때는 처음에 새로운 페이지가 몰아서 나오는 경우입니다. 정리 6과 기댓값의 선형성에 의해 \[ \mathbb{E}[\mathsf{ALG}_i] \leq \ell + \sum_{j = \ell + 1}^k \frac{\ell}{k - j + \ell + 1} = \left( 1 + \frac{1}{k} + \frac{1}{k - 1} + \cdots + \frac{1}{\ell + 1} \right) \cdot \ell \leq H_k \cdot |S_i \setminus S_{i - 1}|\]임을 유도할 수 있습니다. 이것으로 증명을 마칩니다.

마치며

이상으로 온라인 캐싱 문제에 대해 \(2 \ln k\)의 경쟁비를 갖는 랜덤 마킹 알고리즘에 대한 설명을 모두 마칩니다. 사실 이 글은 작년 여름에 처음 적기 시작했습니다. 하지만 당시 글을 적다가 이내 증명이 잘못된 것을 깨달았습니다. 참고 문헌을 확인했지만 제 기준에서는 증명에 비약이 너무 심해 제대로 이해하지 못하였습니다. 그렇게 미완성인 상태로 거진 아홉 달의 시간이 흘렀습니다.

 

최근 온라인 캐싱 문제에 대해 다시 공부를 하게 되었습니다. 예측 모델이 딸린 온라인 문제가 요새 제가 눈여겨 보고 있는 분야이기 때문입니다. 그러다 문득 저번에 작성하다가 그만둔 이 글이 기억났습니다. 증명을 다시 시도해 봤고, 이번에는 웬걸 훨씬 쉽게 증명에 성공하였습니다. 역시 문제가 잘 풀리지 않을 때에는 잠시 멀리 떨어질 필요가 있나 봅니다.

 

시간이 된다면 예측 모델이 딸린 온라인 캐싱 문제에 대해서 공부한 다음 정리해 보도록 하겠습니다. 비슷한 모델을 스키 대여 문제에서 푼 것은 이미 제 블로그에 정리하여 두었습니다. 궁금하시면 아래 글을 참고하시기 바랍니다.

예측이 있는 스키 대여 문제 (Ski Rental Problem with Predictions)

 

읽어 주셔서 고맙습니다.

참고 문헌

[1] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. "Competitive paging algorithms." Journal of Algorithms 12, no. 4 (1991): 685-699.

주석

[ㄱ] \(k\) 개의 서로 다른 공이 들어 있는 속이 보이지 않는 바구니를 \(\ell\) 번 균등한 확률로 비복원 추출하면 특정한 공이 뽑힐 확률은 \(\frac{\ell}{k}\)입니다. 증명은 간단합니다. 비복원 추출을 일종의 랜덤 순열(random permutation)으로 본 다음, 찾고자 하는 공이 처음 \(\ell\) 번째 안에 위치해 있을 확률과 동일하기 때문입니다.