![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
삼 년 전, 저는 유명한 온라인 최적화(online optimization) 문제 중 하나인 온라인 캐싱(online caching)을 소개하고, 이를 해결하는 유명한 방법인 LRU(least recently used) 알고리즘의 경쟁성을 증명하였습니다.
[캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까?
세세한 부분을 많이 놓치기는 하겠지만, 간략히 말해 컴퓨터는 다음과 같이 동작합니다. 메모리에서 데이터를 프로세서로 가지고 와서 사칙 연산, 대소 비교 등과 같이 어떠한 작업을 수행한 다
gazelle-and-cs.tistory.com
글의 서론에서 저는 캐시 미스가 발생했을 때 캐시 메모리 상에서 가장 마지막에 사용되는 자료를 삭제하는 정책인 LFD(longest forward distance) 알고리즘이 최적의 전략이라는 것을 언급하였습니다. 하지만 이에 대한 증명은 보이지 않았죠. 삼 년이 지난 현재, 개인적으로 한번 증명에 도전해 봤는데 생각보다 간단하더군요. 그 증명 방법을 이번 포스트에서 보여 드리고자 합니다.
문제 정의 및 알고리즘 소개
간략히 문제부터 정의하죠. 우리에게는 수 개의 페이지를 담을 수 있는 캐시 메모리가 주어집니다. 프로세서는 매 시각 페이지를 하나씩 호출합니다. 다만, 프로세서가 캐시 메모리와만 소통한다고 가정하겠습니다. 따라서 매번 어떤 페이지를 호출한다면 해당 페이지가 캐시 메모리에 올라가 있어야 합니다.
만약 캐시 메모리에 그 페이지가 이미 있었다면 아무런 문제가 없습니다. 하지만 반대로 캐시 메모리에 그 페이지가 없다면 주 메모리에서 해당 페이지를 캐시 메모리에 옮겨 와야 합니다. 문제는 캐시 메모리에 공간이 부족할 수 있다는 것입니다. 이때 우리는 캐시 메모리에서 단위 비용을 지불하여 한 페이지를 지우고 호출된 페이지를 올려 두어야 합니다. 여기서 우리의 목표는 당연히 페이지 교체를 최소로 하는 전략을 찾는 것입니다.
이번 글에서 다룰 알고리즘은 LFD입니다. 고안자의 이름을 따서 벨라디의 알고리즘(Bélády's algorithm)이라고도 불리는데요. 이는 다음과 같이 동작합니다.
캐시 메모리에 공간이 부족하여 페이지를 교체해야할 때, 가장 나중에 호출되는 페이지 (중 아무나 하나)를 교체한다.
가장 나중에 호출되는 페이지를 알기 위해서는 당연히 미래를 완벽히 알고 있어야 합니다. 따라서 이 알고리즘은 오프라인 알고리즘(offline algorithm)입니다.
증명
이제 LFD가 가장 적은 교체 횟수를 보이는 최적의 알고리즘임을 증명해 보겠습니다. 증명의 방법은 탐욕 알고리즘(greedy algorithm)을 증명할 때 사용하는 정석적인 방법 중 하나인 "exchange argument"입니다. 이와 관련된 전반적인 내용이 궁금하신 분들은 아래 포스트를 참고하시기 바랍니다.
탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms)
탐욕 알고리즘(greedy algorithm)은 매번 현재로써 최선인 선택을 "탐욕스럽게" 취하는 알고리즘 기법으로, 문제 해결 및 다양한 분야에서 활용되고 있습니다. 알고리즘의 동작이 매우 단순하기 때문
gazelle-and-cs.tistory.com
본 증명을 소개하기에 앞서 한 가지 작업을 소개하겠습니다. 만약 어떤 알고리즘이 입력된 페이지가 캐시 메모리에 존재하지 않을 때에만 저장된 페이지 중 하나를 지우고 현재 들어온 페이지를 올려 놓을 때, 우리는 이 알고리즘을 게으르다(lazy)고 부릅니다. 우리는 어떤 게으르지 않은 알고리즘이 주어졌을 때, 이보다 많지 않은 횟수의 페이지를 교체하는 게으른 알고리즘을 만들 수 있습니다. 이를 먼저 증명해 보죠.
만약 어떤 알고리즘이 게으르지 않다고 해 봅시다. 그러면 분명 입력으로 들어온 페이지와 캐시 메모리에 올린 페이지가 서로 다른 시각
이제 페이지
게으른 알고리즘을 만드는 과정에서 한 가지 주목할 부분이 있습니다. 바로 페이지를 올리는 시점이 늦어지기만 한다는 것입니다. 이 사실은 본 증명에서도 요긴하게 활용됩니다.
이제 본 증명을 시작하죠. 우리는 어떤 게으른 최적 알고리즘에서 시작하여 이를 차례로 수정할 것입니다. 이때 매번 수정을 거칠 때마다 페이지 교체 횟수는 증가하지 않고, 게으르면서,
이제
시각
그렇지 않고
증명을 마치기 전에 한 가지 고쳐야할 부분이 있습니다. 바로
이로써
마치며
이것으로 미래의 입력을 모두 아는 경우 최소의 횟수로 페이지를 교체하는 LFD 알고리즘에 대해서 알아 보았습니다. 이 알고리즘을 증명한 이유는 이 알고리즘이 요새 온라인 최적화 세계에서 가장 뜨거운 분야 중 하나인 예측이 주어진 알고리즘(algorithms with prediction) 분야에서 요긴하게 활용되기 때문입니다. 다음에는 이와 관련하여 포스팅을 해 보도록 하겠습니다.
읽어 주셔서 고맙습니다.
'온라인 알고리즘 > Caching' 카테고리의 다른 글
LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm) (0) | 2023.03.18 |
---|---|
[캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까? (0) | 2020.04.04 |