このテキストは、運営している韓国のブログを日本語に翻訳したものです。
韓国のブログ：https://yunsuu.notion.site/e379eccd32c545419f0651f743c12c13?v=35310b282de24cc5a292fe45cc498a32&pvs=74
この記事は「Operating Systems: Three Easy Pieces」を読んでまとめた本です。
著者が無料で公開しているので、興味のある方はぜひ読んでみてください。
本にある良い問題は解いてgithubにアップロードしています。
github：https://github.com/yunsuu/ostep-homework-solution
本のリンク：https://pages.cs.wisc.edu/~remzi/OSTEP/
ページをどのようにエクスポートするか？
ポリシーが必要である
ディスクスワッピングの基本的なアイデアは、メモリとディスクの特性を活かして、プロセスが大きなメモリを所有していると思わせることである。
このとき、最も重要なアイデアがキャッシングである。比較的高速なメモリをディスクのキャッシュとして使うことで、ディスクスワッピングポリシーが最高のコストパフォーマンスを出す方法である。
良いポリシーかどうかの判断基準は、AMAT（average memory access time）を通じて決定する。
例えば、キャッシュヒット率が90%であるとしよう。
このとき、メモリへのアクセスコストが100 nsec、ハードディスクへのアクセスコストが10 msであるとしよう。
このときのAMATは100 nsec + 0.1*10msと計算する。
キャッシュヒット率が100%だとすると、10%改善したように見えますが、パフォーマンスは数十倍、数百倍向上します。
最適技法
最適技法は、利用可能な方法の中で最適な方法で動作させる方法である。
言葉で聞くと何を言っているのかよくわからないかもしれません。
次の図は、0,1,2,0,1,3…といったようにアクセス順序が決まっているときに、最適なキャッシュヒット率を示すポリシーです。
このポリシーは、実際に現実で適用するための技法というよりは、キャッシングポリシーを作る際に、できるだけこの方法に近い方法で作るという目標が研究的な意味があると理解してください。
ポリシーを実装する際に、スタックやキューを一つ設置して実装する方法もありますが、単純な実装方法では最適技法に近づくことができないため、より複雑な実装技法を使用します。しかし、単純な技法も、ワークロードの特性によっては、複雑に実装した技法よりも効率的な状況が出てきます。
例えば、循環ワークロードでは、FIFOやLRUはほとんどヒットしないが、ランダムポリシーはヒット率を示すことができる。
全てのエンジニア最適化技法は、反復する特性や共通特性を見つけて、これを基に最適化します。同様に、キャッシングポリシーも特性を利用しますが、その代表的なものは頻度（どのくらい頻繁に使用されたか）と最近性（どのくらい最近に使用されたか）の二つを活用します。
LRU (Least-Recently-Used), LFU (Least-Frequently-Used)
LRU
最も古いものを交換します
LFU
最も少なく使用されたものを交換します
ダーティビット
もし、あるページが変更されている状態（ダーティ状態）になっていたら、そのページはディスクに出力するためには、変更内容がRAMにしか適用されていないため、DISkにも変更内容を伝える必要があります。
つまり、追加のIO操作が必要ということです。そのため、ページを交換するときには、ダーティ状態にあるページは交換対象から優先順位が後ろにずれます。これを表現するために作られたビットを修正ビットまたはダーティビットと言います。