オペレーティングシステム

9. メモリ管理(2)

授業の流れ・チーム分けの方針・態度目標

2025-04-25 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/os/2025/#12-1

内容目標

- C 言語で書かれたプログラムのポインタの値と仮想記憶 (ページング) における仮想アドレスの関係を理解し、他人に説明できるようになる。

- ページ置き換えアルゴリズム FIFO を理解し、その動作をトレースできるようになる。

- ページ置き換えアルゴリズム LRU を理解し、その動作をトレースできるようになる。

- 最適なページ置き換えアルゴリズムがどのようなものかを理解するとともに、その実現がなぜ困難であるかを理解する。

課題

課題 1

以下のプログラム ex1-1.c および ex1-2.c をコンパイルし、 実行ファイル ex1-1 および ex1-2 を得た。 その後、 64 ビットの OS 上で ex1-1 および ex1-2 を同時に実行したところ以下のような出力が得られた。 ex1-1 の変数 x と ex1-2 の変数 y が同じアドレスに格納されているのはなぜか。

 ex1-1.c:
 #include <stdio.h>
 #include <unistd.h>

 int x = 123;
 int
 main (void)
 {
   printf ("&x = %p\n", &x);
   sleep (60);
 }

 ex1-2.c:
 #include <stdio.h>
 #include <unistd.h>

 double y = 456.789;
 int
 main (void)
 {
   printf ("&y = %p\n", &y);
   sleep (60);
 }

 プログラムの実行
 $ ./ex1-1 &           ← バックグラウンドで実行
 &x = 0x555555558038
 $ ./ex1-2 &           ← バックグラウンドで実行
 &y = 0x555555558038

課題 2

以下のページが順番に参照された時のページフォールト数と、 最終的に主記憶装置に格納されているページの番号をすべて答えよ。 ただし、 ページ置き換えアルゴリズムは FIFO とする。 また、 主記憶に格納できるページ数を 4 とし、 初期状態ではどのページも格納されていない (空の状態である) とする。

0, 2, 1, 3, 5, 4, 6, 3, 7, 4, 7, 3, 3, 5

課題 3

課題 2 において、 ページ置き換えアルゴリズムを LRU とした時の、 ページフォールト数と最終的に主記憶装置に格納されているページの番号をすべて答えよ。

課題 4

課題 2 において、 最適なページ置き換えアルゴリズムを用いた時のページフォールト数を答えよ。 なお、 ページの参照系列があらかじめ分かっていると仮定してよい。

略解

課題 1

変数 x や変数 y のアドレスがページングによって実現されている仮想アドレスだから。 プロセスのデータ領域は独立しているため、 変数 x と変数 y は異なるデータ領域に格納されている。 OS によって各プロセスには 64 ビットの仮想空間が提供されている。 変数 x と変数 y は同じ仮想アドレスに格納されているが、 実際には主記憶上の異なる物理アドレスに格納されている。

課題 2

ページフォールト数 10、 最終的に格納されているページ 7、 6、 5、 3 (順番は入れ替わっても構わない)。

FIFO (First In First Out)

課題 3

ページフォールト数 9、 最終的に格納されているページ 3、 5、 4、 7 (順番は入れ替わっても構わない)。

LRU

課題 4

次に参照される予定が最も先であるページを優先してページアウトすればよい。 ページフォールト数 8。

Wikipedia における「ページング」の説明について

 Memory paging
 https://en.wikipedia.org/wiki/Memory_paging

 In computer operating systems, memory paging (or swapping on some
 Unix-like systems) is a memory management scheme by which a
 computer stores and retrieves data from secondary storage[a] for
 use in main memory.[citation needed] In this scheme, the
 operating system retrieves data from secondary storage in
 same-size blocks called pages. Paging is an important part of
 virtual memory implementations in modern operating systems, using
 secondary storage to let programs exceed the size of available
 physical memory.

 For simplicity, main memory is called "RAM" (an acronym of
 random-access memory) and secondary storage is called "disk" (a
 shorthand for hard disk drive, drum memory or solid-state drive,
 etc.), but as with many aspects of computing, the concepts are
 independent of the technology used.

 Depending on the memory model, paged memory functionality is
 usually hardwired into a CPU/MCU by using a Memory Management
 Unit (MMU) or Memory Protection Unit (MPU) and separately enabled
 by privileged system code in the operating system's kernel. In
 CPUs implementing the x86 instruction set architecture (ISA) for
 instance, the memory paging is enabled via the CR0 control
 register.

 ページング方式
 https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%B3%E3%82%B0%E6%96%B9%E5%BC%8F

 ページング方式 (Paging) とは、コンピュータのオペレーティングシス
 テムにおいて記憶装置をページと呼ばれる小さな単位に分割して割り当
 てを行うアルゴリズム群である。仮想記憶のベースとなる設計の一つ。
                   == 「方式」とは「群」である??
                                     ===== 「ベース」の意味が不明
                                               === 「方式」=「群」=「設計の一つ」??

 物理メモリ空間および論理メモリ空間を、基本的に一定サイズのページ
 と呼ばれる単位に分割して管理を行う。論理メモリから物理メモリ空間
 への対応づけはページテーブルと呼ばれる構造体で実現され、この構造
                                   ===== 「データ構造」の誤り?
 体はオペレーティングシステム (OS) によって管理される。物理メモリ
 空間に対応づけられていない論理メモリを参照した時にはページフォル
 トという例外によってOS側の例外処理ルーチンに制御が移行し、OS側の
 管理によって適宜対応したページを二次記憶等から読み込み、テーブル
                                    == なぜ「等」?? 他に何があるのか??
                                          ======= 「管理」によって「読み込む」??
                                                   ======= なぜ「ページテーブル」ではなく「テーブル」??
 を更新してその参照した命令の実行に戻る。
          ============== 日本語がおかしい。

 これを実現するハードウエアであるメモリ管理ユニット (MMU) の中には
 === 「これ」が何を差すか不明。「ページング」であれば実現するのは OS。
 トランスレーション・ルックアサイド・バッファ (Translation
 Lookaside Buffer:TLB) と呼ばれる一種のキャッシュがあり、ユニット
                                                     ======== 何を差している?? MMU??
 内部ではこの対応表に基づいてメモリアドレスの対応づけを行っている。
               == 上では「キャッシュ」、ここでは「表」??
                                ============ 何と何の対応か書かれていない。
 このテーブルから参照出来なかったときをTLBミスと呼ぶ。このときの処
               ================== 意味不明
 理はMMUの設計によって異なり、MMU内にはTLBのみを持ちTLBミスが即例
 外を起こし、OSがページテーブルを引いてTLBに追加することによって
                              ===== 意味不明
 TLBミスを解決するアーキテクチャや、ページテーブル自体のフォーマッ
                 ============ 何のアーキテクチャ?? この日本語だと「処理」の「アーキテクチャ」となって意味不明。
 トがOSが使えるビットを含めた形でMMUによって定義されていて、TLBミ
 ==================================================== 意味不明。書いている人が理解していないと思われる。
 ス時にMMU自身が与えられた物理アドレスにあるページテーブルを参照す
 るアーキテクチャもある。
   ================== そもそも「ページング」の本質と関係ない話。他にもっと重要なことがたくさんある。

レポート課題 2025-06-06

「レポート課題 2025-04-11」と同じ。

https://lsnl.jp/~ohsaki/lecture/os/2025/#10-10

質問要望コメント

- 最適化アルゴリズムにおいて、最後の方になると、現在あるページが今後登場しないものだけになると思います。その際に、次の置き換えは(消去するもの)はどれでも良いのでしょうか?それとも一番古いものと置き換えればよいのでしょうか?

課題 4 の問題設定 (0, 2, 1, 3, 5, 4, 6, 3, 7, 4, 7, 3, 3, 5 というページ参照
だけ考えればよい) のであればどれを選んでも (ページフォールト数は) 同じです。

- 最適なページ置き換えアルゴリズムの詳細なやり方(考え方)について説明してください。またどのようにしたら、自分で考えた解答が最小のページフォルト数だと確認(証明)できるのでしょうか。

手法については略解を見てください。

証明はいろんな方法がありそうですが、例えば、あるスロットにおいて、「次に参照
される予定が最も先であるページを優先した場合」と比較して、「次に参照される予
定が最も先でないページを優先した場合」にページフォールトの回数が減ることはな
い、ことを示せばよいと思います。

- LRUは直近で使ったページを優先的に残しているので、これは(前回の授業にあった)参照の局所性を活かしていると言えますか?

  はい。