algorithm
온라인 알고리즘

비고

페이징 (온라인 캐싱)

머리말

공식적인 정의로 시작하는 대신 목표는 일련의 예제를 통해 이러한 주제에 접근하여 그 길을 따라 정의를 도입하는 것입니다. 발언 섹션 이론 은 모든 정의, 정리 및 명제로 구성되어 특정 정보를 더 빠르게 찾을 수 있도록 모든 정보를 제공합니다.

발언 섹션 소스는이 주제에 사용 된 기본 자료와 추가 읽기를위한 추가 정보로 구성됩니다. 또한 예제에 대한 전체 소스 코드를 찾을 수 있습니다. 예제의 소스 코드를 더 읽기 쉽고 짧게 만드는 것은 오류 처리 등과 같은 것을 삼가는 데주의를 기울이십시오. 또한 고급 라이브러리를 광범위하게 사용하는 것과 같은 예제의 명확성을 흐리게하는 특정 언어 기능을 전달합니다.

페이징

페이징 문제는 유한 공간의 제한으로 인해 발생합니다. 캐시 C 가 k 페이지를 가지고 있다고 가정합시다. 이제 m 페이지 요청 시퀀스를 처리하기 전에 캐시에 저장해야하는 일련의 m 페이지 요청을 처리하려고합니다. 물론 m<=k 이면 모든 요소를 ​​캐시에 넣으면 작동하지만 일반적으로 m>>k 입니다.

페이지가 이미 캐시에있을 때 요청이 캐시 히트 라고하고, 그렇지 않으면 캐시 미스 라고합니다. 이 경우 요청 된 페이지를 캐시로 가져와 캐시가 가득 차 있다고 가정하고 다른 페이지를 제거해야합니다. 목표는 퇴거 횟수 를 최소화 하는 퇴거 일정입니다.

이 문제에 대한 수많은 전략이 있습니다. 몇 가지를 살펴 보겠습니다.

1. 선입 선출 (FIFO) : 가장 오래된 페이지가 축출됩니다.
2. 마지막 입력, 처음 출력 (LIFO) : 가장 새로운 페이지가 제거됨
3. 가장 최근에 사용한 액세스 (LRU) : 가장 최근에 액세스 한 액세스 페이지가 가장 먼저 있었던 페이지 삭제
4. 자주 사용하지 않는 항목 (LFU) : 가장 자주 요청하지 않은 페이지 비우기
5. LFD (Longest forward distance) : 캐시에서 가장 멀리 떨어져있을 때까지 요청되지 않은 페이지를 제거합니다.
6. 풀 때 플러시 (FWF) : 캐시 미스가 발생하면 즉시 캐시를 지우십시오.

이 문제에 접근하는 데는 두 가지 방법이 있습니다.

1. 오프라인 : 페이지 요청 순서가 미리 알려짐
2. 온라인 : 페이지 요청 순서가 미리 알려지지 않았습니다.

오프라인 접근법

첫 번째 접근 방식 은 Greedy 기술의 응용 프로그램 주제를 살펴보십시오. 세 번째 예제 Offline Caching 은 위의 처음 다섯 가지 전략을 고려하고 다음에 대한 좋은 진입 점을 제공합니다.

예제 프로그램은 FWF 전략으로 확장되었습니다.

class FWF : public Strategy {
public:
    FWF() : Strategy("FWF")
    {
    }

    int apply(int requestIndex) override
    {
        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            // after first empty page all others have to be empty
            else if(cache[i] == emptyPage)
                return i;
        }

        // no free pages
        return 0;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {

        // no pages free -> miss -> clear cache
        if(cacheMiss && cachePos == 0)
        {
            for(int i = 1; i < cacheSize; ++i)
                cache[i] = emptyPage;
        }
    }
};

전체 소스 코드는 여기에서 볼 수 있습니다 . 우리가 주제에서 예제를 재사용하면 다음과 같은 결과를 얻는다.

Strategy: FWF

Cache initial: (a,b,c)

Request cache 0 cache 1 cache 2 cache miss
  a       a       b       c
  a       a       b       c
  d       d       X       X       x
  e       d       e       X
  b       d       e       b
  b       d       e       b
  a       a       X       X       x
  c       a       c       X
  f       a       c       f
  d       d       X       X       x
  e       d       e       X
  a       d       e       a
  f       f       X       X       x
  b       f       b       X
  e       f       b       e
  c       c       X       X       x

Total cache misses: 5

LFD 가 최적이지만 FWF 는 캐시 미스가 적습니다. 그러나 주된 목표는 퇴거 횟수를 최소화하는 것이었고, FWF 5 회 미스에 대해서는 15 회 퇴거를 의미 했기 때문에이 예에서는 최악의 선택이었습니다.

온라인 접근법

이제 우리는 페이징의 온라인 문제에 접근하려고합니다. 그러나 먼저 그것을하는 방법을 이해할 필요가 있습니다. 분명히 온라인 알고리즘은 최적의 오프라인 알고리즘보다 우수 할 수 없습니다. 그러나 얼마나 더 나쁜가? 우리는 그 질문에 답하기 위해 공식적인 정의가 필요합니다.

정의 1.1 :는 최적화 문제 Π는 인스턴스 Σ _Π의 집합으로 구성되어 있습니다. 모든 인스턴스 σ∈Σ _{Π에 대해} 솔루션 의 집합 Ζ _σ 와 객관적인 함수 f _σ : Ζ _σ → ℜ _≥0 이 모든 솔루션에 양의 실수 값을 할당합니다.
OPT (σ)는 최적 해의 값이고 A (σ)는 문제 Π에 대한 알고리즘 A의 해이며, w _A (σ) = f _σ (A (σ)) 값이다.

정의 1.2 : 최소화 문제에 대한 온라인 알고리즘 A τ는 상수 τ∈ if가있는 경우 r ≥ 1의 경쟁 비율 을 갖는다.

w _A (σ) = f _σ (A (σ)) ≤ r ∙ OPT (σ) + τ

모든 인스턴스 σ∈Σ _{Π에 대해} . A는 r 경쟁 온라인 알고리즘이라고합니다. 짝수이다

w _A (σ) ≤ r ∙ OPT (σ)

모든 인스턴스 σ∈Σ _Π에 대해 A는 엄격하게 r 경쟁적인 온라인 알고리즘이라고 불린다.

따라서 문제는 온라인 알고리즘이 최적의 오프라인 알고리즘과 비교하여 얼마나 경쟁력 이 있는지입니다. 유명한 책 Allan Borodin과 Ran El-Yaniv는 온라인 페이징 상황을 설명하기 위해 또 다른 시나리오를 사용했습니다.

당신의 알고리즘과 최적의 오프라인 알고리즘을 아는 사악한 적도 있습니다. 모든 단계에서 그는 최악의 페이지를 요청하고 동시에 오프라인 알고리즘에 가장 적합한 페이지를 요청합니다. 귀하의 알고리즘의 경쟁 요소 는 귀하의 알고리즘이 적의 최적 오프라인 알고리즘에 비해 얼마나 나쁜지에 대한 요인입니다. 적수가 되려고한다면, 적대적인 게임을 시도 할 수 있습니다 (페이징 전략을이기십시오).

마킹 알고리즘

모든 알고리즘을 개별적으로 분석하는 대신 마킹 알고리즘 이라는 페이징 문제에 대한 특별한 온라인 알고리즘 제품군을 살펴 보겠습니다.

하자 σ = (σ ₁ , ..., σ _p ) 우리의 문제에 대한 인스턴스와 케이 우리의 캐시 크기, σ보다 단계로 나눌 수 있습니다 :

• 1 단계는 최대 k 개의 다른 페이지가 요청 될 때까지 시작부터 σ의 최대 부분 시퀀스입니다.
• 페이즈 i ≥ 2는 최대 k 개의 다른 페이지가 요청 될 때까지 pase i-1의 끝에서 σ의 최대 부분 시퀀스입니다.

예를 들어 k = 3 :

마킹 알고리즘 (암시 적 또는 명시 적)은 페이지 표시 여부를 유지합니다. 각 단계의 시작 부분에 모든 페이지가 표시되지 않습니다. 페이지가 표시되는 단계 중에 요청되었는지 나타냅니다. 이 캐시에서 표시된 페이지를 축출하지 IFF에 알고리즘은 마킹 알고리즘이다. 즉, 단계에서 사용 된 페이지는 축출되지 않습니다.

명제 1.3 : LRU 와 FWF 는 마킹 알고리즘이다.

증명 : 각 단계의 시작 부분 (첫 번째 단계 제외)에서 FWF 는 캐시 미스를 가지며 캐시를 지 웁니다. 그건 빈 페이지가 있다는 뜻입니다. 모든 단계에서 최대 k 개의 서로 다른 페이지가 요청되므로 단계 중에 퇴거가 발생합니다. 따라서 FWF 는 마킹 알고리즘입니다.
LRU 가 마킹 알고리즘이 아니라고 가정합시다. 그런 다음 인스턴스 σ가 있는데 여기서 LRU 는 단계 i에서 표시된 페이지 x를 축출합니다. x가 축출되는 단계 i에서 σ _t 를 요청하자. x가 표시되기 때문에 동일한 위상에서 x에 대한 이전 요청 σ _{t *가} 있어야하므로 t * <t입니다. 시퀀스 σ의 _{t *} t _{+ 1에서} 축출되었다하도록 * t의 후 X는 최신 캐시의 페이지, ..., σ _t는 서로 다른 페이지 (X)로부터 적어도 K를 요청한다. 이는 단계 i가 적어도 k + 1 개의 서로 다른 페이지를 요구했음을 의미하며 이는 단계 정의와 모순됩니다. 따라서 LRU 는 마킹 알고리즘이어야합니다.

명제 1.4 : 모든 마킹 알고리즘 은 엄격하게 k- 경쟁적 이다.

증명 : σ를 페이징 문제의 인스턴스로, l을 σ에 대한 위상 수라고하자. l = 1이면 모든 마킹 알고리즘이 최적이며 최적의 오프라인 알고리즘이 더 좋을 수는 없습니다.
우리는 l ≥ 2라고 가정한다. 모든 마킹 알고리즘의 비용, 예를 들어, σ는 모든 상에 마킹 알고리즘이 하나의 마킹 된 페이지를 제외하지 않고 k 페이지 이상을 축출 할 수 없기 때문에 위에서 π * 경계를 갖는다.
이제 우리는 최적의 오프라인 알고리즘이 첫 번째 단계에서 σ, k에 대해 적어도 k + l-2 페이지를 제거하고 마지막 단계를 제외한 모든 후속 단계에 대해 적어도 하나를 삭제한다는 것을 보여줍니다. 증명을 위해 σ의 I-2 개의 분리 된 서브 시퀀스를 정의 할 수있다. 서브 시퀀스 i ∈ {1, ..., l-2}는 위상 i + 1의 두 번째 위치에서 시작하여 위상 i + 2의 첫 번째 위치로 끝난다.
x를 phase i + 1의 첫 페이지 라하자. 부분 시퀀스 i의 시작 부분에는 최적의 오프라인 알고리즘 캐시에 페이지 x와 대부분 k-1 개의 서로 다른 페이지가 있습니다. 서브 시퀀스에서 i는 k와는 다른 페이지 요청이므로 최적의 오프라인 알고리즘은 모든 서브 시퀀스에 대해 적어도 하나의 페이지를 제거해야한다. 1 단계에서 캐시가 아직 비어 있기 때문에 최적의 오프라인 알고리즘은 첫 번째 단계에서 k 축출을 발생시킵니다. 그것은

w _A (σ) ≤ l · k ≤ (k + l-2) k ≤ OPT (σ) · k

결론 1.5 : LRU 와 FWF 는 엄격하게 k- 경쟁적 입니다.

Excercise : FIFO 에 마킹 알고리즘은 없지만 엄격하게 k- 경쟁 임을 보여줍니다.

온라인 알고리즘 A가 R-경쟁력있는 정수를 r은 없지만, 우리는 경쟁력이 전화

명제 1.6 : LFU 와 LIFO 는 경쟁력 이 없습니다 .

증명 : l ≥ 2 상수, k ≥ 2 캐시 크기. 다른 캐시 페이지는 1, ..., k + 1의 nubered입니다. 다음 시퀀스를 살펴 봅니다.

첫 번째 페이지 1은 페이지 2보다 l 번 요청되므로 1 페이지도 마찬가지입니다. 마지막에는 페이지 k와 k + 1에 대한 교대 요청이 (l-1) 개 있습니다.
LFU 와 LIFO 는 캐시를 1-k 페이지로 채 웁니다. 페이지 k + 1이 요청되면 페이지 k가 축출되고 그 반대도 마찬가지입니다. 즉, ^서브 시퀀스 (k, k + 1) ^l-1 의 모든 요청은 하나의 페이지를 제거합니다. 또한 1- (k-1) 페이지를 처음 사용할 때의 k-1 캐시 누락이 있습니다. 따라서 LFU 와 LIFO는 정확한 k-1 + 2 (l-1) 페이지를 제거합니다.
이제 우리는 모든 상수 τ∈ℜ와 모든 상수 r ≤ 1에 대해 l이 존재한다는 것을 보여 주어야합니다.

이는

이 불평등을 만족시키기 위해서는 충분히 큰 것을 선택해야합니다. 그래서 LFU 와 LIFO 는 경쟁력이 없습니다.

명제 1.7 : r <k를 갖는 페이징을위한 r- 경쟁적 결정 론적 온라인 알고리즘은 없다 .

이 마지막 명제에 대한 증거는 다소 길며 LFD 가 최적의 오프라인 알고리즘임을 근거로합니다. 관심있는 독자는 Borodin and El-Yaniv (아래 출처 참조)에서 찾을 수 있습니다.

문제는 우리가 더 잘할 수 있는지 여부입니다. 이를 위해 우리는 결정 론적 접근 방식을 남겨두고 알고리즘을 무작위 추출해야합니다. 분명히, 공격자가 무작위로 알고리즘을 처벌하는 것이 훨씬 어렵습니다.

무작위 화 된 페이징은 다음 예제 중 하나에서 논의 될 것입니다 ...