OS論 仮想記憶装置のOptimal アルゴリズムについて

Question

ただいまオペレーティングシステムについて学んでいるものです。
仮想記憶装置のOPTアルゴリズムについて質問があります。
まず、OPTの図の書き方として

OPT：今後最も長い期間使用されないページを選択（各ページが参照されるまでの時間（実行される命令数）をもとに，最も遠い将来まで参照されないページを補助記憶装置上に追い出すページとして選択）

・（最初）上から順番に入れていく
・空きがなくなったら、入れ替える
１、まず、フレーム（ページインしている）の中の数字を上から見ていく
２、その数字がこれから先（今後出てくる数字列）で直近でどこに出るかみる
３、２と同じことを全てのフレームで確認する
４、３で確認した中で、最も遅く（遠い未来）出る数字と交換する。
・入れ替えた数字（元々入っていた数字）がPage Fault

という書き方で覚えています。

この例題についてなんですが、上記のやり方で書いていくと、最後の1,4,2,7から1と3を交換した意味がわからなくなってしまいます。先が読めない時、どのような動作になるのでしょうか。

Answer 1

こんにちは。

「最も遠い将来まで参照されないページ」を識別するには未来予知が必要になるので、不可能と思います。
「仮想という考え方」によると「一番よいアルゴリズムは、OPTアルゴリズムだが、実現不可能である。未来の情報を使うので」だそうです。

恐らく上記ページの「LRU((Least Recentry Used))アルゴリズム。最も長い時間参照されてい ない部分を二次記憶へ。」のことをOPTアルゴリズムと呼ばれているように思います。
しかし、そのように思って読んでも理解できません。最大の問題は「最も遅く（遠い未来）出る数字」の部分です。この数字がどれなのかかを判別するには未来予知が必要です。従って、その例題にそのアルゴリズムを適用することは不可能ではないかと感じるからです。

他にも不足しています。
「上から順番に入れていく」は何をどんな順番でどこへ入れていくのでしょうか？
「今後出てくる数字列」は図中のどれに該当するのでしょうか？
「直近でどこに出るかみる」は、出てこなかったらどうするのでしょうか？

この例題についてなんですが、上記のやり方で書いていくと、最後の1,4,2,7から1と3を交換した意味がわからなくなってしまいます。先が読めない時、どのような動作になるのでしょうか。

この例題を書かれた方は「最後の1,4,2,7」の時点で「最も遅く（遠い未来）出る数字」が1であると想定しているのではないでしょうか？　これは未来予知の想定なので、その想定がどこかに記載されていないと理解することは不可能と思います。
もしかして出題者は「不可能」であることを理解して貰いたかったとか？

Answer 2

・空きがなくなったら、入れ替える

１、まず、フレーム（ページインしている）の中の数字を上から見ていく
２、その数字がこれから先（今後出てくる数字列）で直近でどこに出るかみる
３、２と同じことを全てのフレームで確認する
４、３で確認した中で、最も遅く（遠い未来）出る数字と交換する。

の2で「これから先に出現することがない」場合は適当にN回先でアクセスされると考えNの実際の大きさは適当に大きな数値を選んでおくなどの方針で論理を決めると思います。いずれにせよ最終段階で3へアクセスした際、どのページに対する将来情報もないので全てのページの評価値は同じになります。なので4で最も遅いものを選ぼうとしてもページ間の優劣がつかず任意に選ぶしかありません。提示しておられる図で1が選ばれたのは単に「任意の選択しかできない場合はフレームの先頭を選ぶ」という理由だろうと思いますが、実のところその想定はあまり気にする必要がない（その教科書?で問題している事項のポイントではない）と思います。

おそらくその例題がかかれた趣旨は「未来予測が不可能なのはもちろんだが、もし予測できたとしたらPage faultの発生の程度がこんな感じになります」の例示だと思います。教科書のその部分で議論しようとしていることには「最後が1かどうか」は興味のないことで言ってみれば(書き手が)どうでもよいことと捉えているのではないかと思います。

「読者が明確な仕様・論理を是とする普通のプログラマーであることに配慮する」書き手ならどうでもよいと思っている点についても「優劣が決められない場合はフレーム先頭を選ぶ」などと注記するだろうと思います。しかし大雑把(?)な書き手なら「まぁ・・・その辺り適当に解釈してくれるだろう」と考え説明しないかも知れません。