algorithm
オンラインアルゴリズム

備考

ページング（オンラインキャッシュ）

序文

正式な定義から始めるのではなく、一連の例を介してこれらのトピックにアプローチし、その途中で定義を導入することです。発言セクションの理論は、すべての定義、定理、命題から構成され、特定の側面をより速く探すためのすべての情報を提供します。

発言セクションのソースは、このトピックで使用した基本マテリアルと、さらに読むための追加情報で構成されています。さらに、そこにあるサンプルの完全なソースコードを見つけることができます。サンプルのソースコードをより読みやすく、短くすることは、エラー処理などのことを控えるように注意してください。また、先進的なライブラリなどの広範な使用のように、サンプルの明快さを不明瞭にする特定の言語機能を渡します。

ページング

ページングの問題は有限空間の限界から生じる。キャッシュCにkページがkます。今度は、処理される前にキャッシュに置かれていなければならない一連のmページ要求を処理したいと考えています。もちろん、 m<=kならば、すべての要素をキャッシュに入れるだけで動作しますが、通常はm>>kです。

リクエストは、ページがすでにキャッシュに入っている場合はキャッシュヒット 、そうでなければキャッシュミスと呼ばれます。その場合、キャッシュがいっぱいであると仮定して、要求されたページをキャッシュに持ち込み、別のページを追い出す必要があります。目標は、退去の回数を最小限に抑える退去スケジュールです。

この問題の戦略は数多くありますが、いくつかを見てみましょう：

1. 先入れ先出し（FIFO） ：最も古いページが追い出されます
2. 最後に、先入れ先出し（LIFO） ：最新のページが追い出される
3. 最近使用されたLRU（Least Recently Used） ：最も最近のアクセスが最も早いEvictページ
4. 最低限頻繁に使用される（LFU） ：最も頻繁に要求されなかったページを削除する
5. 最長前方距離（LFD） ：将来最も遠くまで要求されないキャッシュ内のページを退去させる。
6. 満杯になったらフラッシュする（FWF） ：キャッシュミスが発生するとすぐにキャッシュをクリアする

この問題には2つの方法があります。

1. オフライン ：ページ要求の順序は事前にわかっています
2. オンライン ：ページ要求の順序が事前にわかっていない

オフラインアプローチ

最初のアプローチについては、欲張りテクニックのトピックのトピックを見てください。 3番目の例です。 オフラインキャッシュは、上記の最初の5つの戦略を考慮して、次の点を説明します。

このサンプルプログラムは、 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：と定数τ∈ℜがある場合Πをr≥1の競合的比が最小化問題のためのオンラインアルゴリズムA

w _A （σ）= _fσ （A（σ））≦r・OPT（σ）+τ

すべてのインスタンス_σ∈ΣΠため。 Aはr競争力のあるオンラインアルゴリズムと呼ばれます。偶数である

w _A （σ）≦r・OPT（σ）

すべてのインスタンスに対して_σ∈ΣΠは 、Aは、 厳密にはR-オンライン対戦アルゴリズムと呼ばれています。

だから問題は、オンラインアルゴリズムが最適なオフラインアルゴリズムと比較してどれほど競争力があるかということです。有名な本の Allan BorodinとRan El-Yanivは、別のシナリオを使ってオンラインページングの状況を説明しました。

あなたのアルゴリズムと最適なオフラインアルゴリズムを知っている邪悪な敵がいる。すべてのステップで、彼は最悪のページを要求し、同時にオフラインアルゴリズムに最適です。あなたのアルゴリズムの競争力の要素は、あなたのアルゴリズムが敵の最適なオフラインアルゴリズムに対してどれほどひどく悪いかの要因です。あなたが敵になろうとするなら、敵対ゲームを試すことができます（ページング戦略を打ち破ろう）。

マーキングアルゴリズム

別々にすべてのアルゴリズムを分析する代わりに、 マーキングアルゴリズムと呼ばれるページング問題のための特別なオンラインアルゴリズムファミリを見てみましょう。

σは段階に分けることができるより_{、σ=（σ1、...、σp}値）我々の問題のためのインスタンスをしようと私たちのキャッシュサイズをk個：

• フェーズ1は、k個の異なるページが要求されるまでの開始からσの最大部分シーケンスです
• フェーズi≧2は、最大k個の異なるページが要求されるまで、pase i-1の終わりからσの最大部分シーケンスです

たとえばk = 3の場合：

マーキングアルゴリズム（暗黙的または明示的）は、ページがマークされているかどうかを維持する。各段階の初めに、すべてのページがマークされていません。フェーズで要求されたページです。アルゴリズムは、マークされたページをキャッシュから除去しない場合 、マーキングアルゴリズムである。つまり、フェーズで使用されたページは追い出されません。

命題1.3： LRUとFWFはマーキングアルゴリズムです。

証明：各フェーズの始めに（最初のフェーズを除く） FWFにキャッシュミスがあり、キャッシュをクリアしました。つまり、空のページがk個あることを意味します。すべてのフェーズで最大k個の異なるページが要求されているので、フェーズ中にエビクションが発生します。 FWFはマーキングアルゴリズムです。
LRUがマーキングアルゴリズムではないとしましょう。次に、インスタンスσが存在し、ここで、 LRUは、フェーズi内のマークされたページxを追い出す。 _σT xが追い出されるI相でリクエストしてみましょう。 xがマークされているので、同じフェーズでxに対してより早い要求σt _*がなければならないので、t * <tである。シーケンス_{σtの* + 1トン}で追い出されてしまったとしてのt *の後、xは、キャッシュ最新のページで_{、...、σtは}異なるページxからk個以上を要求しなければなりません。つまり、フェーズiはフェーズ定義と矛盾する少なくともk + 1の異なるページを要求したことを意味します。したがって、 LRUはマーキングアルゴリズムでなければなりません。

命題1.4：すべてのマーキングアルゴリズムは厳密にk競合しています。

証明： σをページング問題のインスタンスとし、lをσのフェーズ数とする。 l = 1なので、すべてのマーキングアルゴリズムが最適であり、最適なオフラインアルゴリズムが改善できません。
l≥2と仮定する。すべてのマーキングアルゴリズムのコスト、例えばσは、すべてのフェーズで1つのマーキングされたページを退避せずにkページ以上をエビクトすることができないので、
ここで、最適なオフラインアルゴリズムが、第1フェーズのσ、kに対して少なくともk + 1〜2ページ、最後のフェーズを除く後続フェーズごとに少なくとも1つを退去させることを示すことを試みる。証明のために、σのl-2個の分離された部分列を定義することができる。サブシーケンスi∈{1、...、l-2}は、フェーズi + 1の第2の位置で開始し、フェーズi + 2の第1の位置で終了する。
xをフェーズi + 1の最初のページとする。サブシーケンスiの始めには、最適なオフラインアルゴリズムキャッシュ内にページxおよび多くてk-1個の異なるページが存在する。サブシーケンスiでは、xとは異なるkページ要求であるので、最適なオフラインアルゴリズムは、各サブシーケンスに対して少なくとも1ページを退避させなければならない。第1段階では、キャッシュがまだ空であるため、最適なオフラインアルゴリズムは、第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回要求されます。最後に、ページkとk + 1の交互の要求が（l-1）あります。
LFUとLIFOはキャッシュをページ1〜kで埋めます。ページk + 1が要求されると、ページkは追い出され、その逆も同様である。これは、部分列（k、k + 1） ^l-1のすべての要求が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とEl-Yanivの本で見ることができます（以下の情報源を参照）。

質問は、私たちがもっとうまくいくかどうかです。そのためには、私たちの後ろに決定論的アプローチを残し、アルゴリズムをランダム化しなければなりません。明らかに、ランダム化されている場合、敵があなたのアルゴリズムを処罰するのがずっと難しくなります。

ランダム化されたページングは​​次の例の1つで議論されます...