c++ - OPT アルゴリズムについて

Question

さて、私はOPTアルゴリズムを理解しようとしています。そうすれば、コーディングが簡単になります。スライドについていくことができず、意味がありません。誰かがそれを行う方法について順を追って説明してもらえますか?

これは、LRU アルゴリズムと同じように見えます。カウンターで 2 番目の配列を保持しますか?

Answer 1

どのページがどのような順序で使用されるかを事前に知っておく必要があるようです。1, 2, 3, ..., 4, 5これはあなたの例のリストです。ページを置き換える必要がある場合は、すべてのフレームの中で最後に使用されるページを含むフレームを選択します。

この例では、ページ フォールトなしでページ 1、2、3、4、1、および 2 にアクセスします (すべてのページが現在スワップインされているため)。

次のページ アクセス、ページ 5 はどのフレームにもないため、配置するフレームを選択する必要があります。次のページ ヒット (1、2、3、4) に基づいて、ページ 4 (フレーム 4 内) が最後にアクセスされるため、ページ 5 をフレーム 4 にスワップします (図に示すように)。

次のページ 1、2、3 は問題なくアクセスされます。

これでページ 4 がアクセスされますが、以前にスワップ アウトされていたため、ページ フォールトが発生しています。今後のアクセスのリストは、5 ページのみが必要であることを示しているため、1、2、および 3 のいずれかを入れ替えることができます。1 が選択されたのは、おそらくそれが最初であるためです。

Answer 2

最適なアルゴリズムは、理論的にキャッシュ ミスが最も少ないアルゴリズムです。

つまり、キャッシュがどのように使用されるかを知るまで、最適な方法を知ることは不可能です。つまり、最適なアルゴリズムを前もってコーディングすることはできません。なぜなら、キャッシュが実際にどのように使用されるかわからないからです。

最適アルゴリズムは、実際のアルゴリズムに対するベースラインとして非常に役立ちます。重要なキャッシングの問題はすべて、最終的にキャッシュミスになります。特定の実行の「絶対最小」ミス数を知ることで、2 つのキャッシュ アルゴリズムを比較するためのベースラインを提供できます。

たとえば、キャッシュを 4 回ミスする必要がある場合、キャッシュを 7 回ミスするアルゴリズムと比較して、キャッシュを 6 回ミスするアルゴリズムはかなり適切に見えます。キャッシュを 1000 回ミスする必要がある場合、キャッシュを 1006 回ミスするアルゴリズムと 1007 回キャッシュをミスするアルゴリズムはほぼ同等です。

一部のアルゴリズムは、キャッシュの使用パターンに基づいて、他のアルゴリズムよりも頻繁にキャッシュにヒットします。1 つの例は、LRU です。これは、めったに使用されないアイテムをキャッシュから削除します。短期間に同じアイテムに複数回アクセスする傾向がある場合に適しています。一方、各アイテムに何度もアクセスする必要があるが、(ループのように) 順序どおりに 1 回アクセスする必要がある場合、LRU のパフォーマンスは最悪 (~100% のキャッシュ ミス) になる可能性があります。 . 偶然にも、MRU (最近使用されたアイテムが新しいアイテムに置き換わる) キャッシュは、少なくとも最初のいくつかのアイテムに対してキャッシュが 1 回ヒットするため、これらの条件下では LRU よりも優れたパフォーマンスを発揮します。