FIFOページ置換はどのように機能しますか？

1. 概要

オペレーティングシステムでは、メモリ管理が重要なトピックです。コンピュータのメモリを動的に制御および調整する方法を提供します。メモリ管理では、プログラムからの要求に応じてメモリの一部を割り当てることができます。また、プログラムで使用されなくなったときに、プログラムからメモリの割り当てを自動的に解除します。

メモリ管理で使用されるさまざまな手法があります。そのような方法の1つは、ページングです。 ページングでは、ページ置換アルゴリズムが重要な役割を果たし、新しいページが着信したときにメインメモリに保持するページを決定します。

先入れ先出し（FIFO）は、ページ置換アルゴリズムの中で最も単純です。 このチュートリアルでは、FIFOについて詳しく説明します。

2. 一般的なアイデア

まず、ページ置換アルゴリズムの背景について説明します。

ページ置換アルゴリズムは、ページング手法に分類されます。オペレーティングシステムのページングは、主に仮想メモリ管理に使用されます。ページングは、コンピュータがセカンダリメモリからデータを取得して保存できるようにする方法です（例： HDDまたはドラムメモリ）をメインメモリ（RAM）に挿入します。セカンダリメモリから抽出されたデータは、メモリ管理ではページと呼ばれます。

FIFOのようなページ置換アルゴリズムは、新しいページ要求があり、メインメモリに新しいページを割り当てるのに十分なスペースがない場合に使用されます。

したがって、ページ置換アルゴリズムは、新しいページにメモリを割り当てることができるように、置換するページを決定します。ページ置換の手順は、フローチャートに要約できます。

先入れ先出し（FIFO）アルゴリズムには、この問題に対する単純なアプローチがあります。メインメモリのキューを使用して、すべてのページを追跡します。ページが入ってきたらすぐにキューに入れて続行します。このように、最も古いページは常にキューの最初の場所にあります。

これで、新しいページが入力され、メモリにスペースがなくなると、キューの最初のページが削除されます。これも最も古いページです。オペレーティングシステムにページフローが含まれるまで、このプロセスが繰り返されます。

3. ページフォールト

ページフォールトは、ページ置換アルゴリズムのもう1つの重要な概念です。 プログラムによって要求されたページがメインメモリに存在しない場合、ページフォールトが発生します。

ページフォールトは、オペレーティングシステムのアラートを生成します。次に、オペレーティングシステムは、セカンダリメモリまたは仮想メモリからメインメモリにページを取得します。すべてのプロセスはバックグラウンドで実行されます。

通常、これには数ミリ秒かかります。それでも、オペレーティングシステムのパフォーマンスに大きな影響を与えます。ページフォールトの数が多いと、システム全体の速度が低下する可能性があります。現代のオペレーティングシステムではページフォールトが一般的ですが、ページフォールトが多数あると、プログラムがクラッシュしたり、予期せず終了したりする可能性があります。

ページ置換アルゴリズムの有効性は、生成されるページフォールトの数で測定されます。ページ置換アルゴリズムが効果的であるほど、アルゴリズムによって生成されるページフォールトの数は少なくなります。

4. FIFO擬似コード

FIFOページ置換アルゴリズムの背後にある理論がわかったので、擬似コードを見てみましょう。

これは、システム内の現在のページのセットを示します。キューを作成し、FIFO方式で着信ページを格納するように名前を付けました。最初に、ページフォールトの数をゼロに設定しました。

これで、新しいページが表示されたら、セットの容量を確認します。ここでは、3つのケースがあります。 1つ目は、セットが新しい受信ページを保存でき、そのページがまだセットに存在しない場合です。この場合、通常、新しいページをセットに保存します。

2番目のシナリオは、セットが新しい受信ページを保存できるが、ページがすでにセットに存在する場合です。この場合、ページヒットとしてマークし、変数の数は増えません。

3番目のケースは、セットがは満杯。ここでは、キューからページを削除するためにFIFOを実行する必要があります。

最後に、すべてのページが保存されるか、セットから削除されると、アルゴリズムはページフォールトの総数を返し、終了します。

5. 例

このセクションでは、例を取り上げて、FIFOページ置換アルゴリズムを実行します。

この例では、ページ参照文字列を使用しています。また、キューの容量はです。最初、キューは空です。次に、キューをページで埋めて、FIFOアルゴリズムを適用しましょう。

ここで、各テーブルの上部にある番号は、新しい受信ページの参照番号を表しています。このプロセスを実行している間、ページフォールトの数も計算しています。

この例では、FIFOページ置換アルゴリズムを使用して発生したページフォールトの総数はです。

6. 長所と短所

FIFOページ置換アルゴリズムの主な利点は、その単純さです。理解と実装が簡単です。また、キューデータ構造を使用します。キュー内の操作の数が制限されているため、実装が簡単になります。

ここで、いくつかの欠点について話しましょう。 受信ページ数が多いと、優れたパフォーマンスが得られない場合があります。

キューにページを格納するためのフレーム数または容量を増やすと、ページフォールトの数が少なくなるはずです。 FIFOが異常に動作する場合があり、ページフォールトの数が増える可能性があります。 このFIFOの動作は、ベラディの異常と呼ばれます。

FIFOでは、システムはすべてのフレームを追跡する必要があります。プロセスの実行が遅くなることがあります。

7. 結論

このチュートリアルでは、FIFOページ置換について詳しく説明しました。

一般的な考え方について説明し、例を使用してアルゴリズムを示しました。

FIFOページ置換アルゴリズムは、実際に使用するのに最適なページ置換アルゴリズムではありません。着信ページの数が少なく、ユーザーが単純なアプローチを探している場合は、FIFOが妥当な選択である可能性があります。