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

1. URL
2. 担当教員
3. 講義目的
4. 到達目標
5. 授業方法
6. 参考書
7. 成績評価
8. スケジュール
9. 大崎が担当する科目に共通の連絡事項・アドバイス
10. 1. オペレーティングシステムの概要
11. 2. CPU の原理
12. 3. プロセスとスレッド
13. 4. プロセス間通信
14. 5. スケジューリング (1)
15. 6. スケジューリング (2)
16. 7. 前半の総復習
17. 8. メモリ管理 (1)
18. 9. メモリ管理(2)

8. メモリ管理 (1)

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

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

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

内容目標

- マルチプログラミング環境における CPU の利用率を計算できるようになる。

- スワッピングとページングの違いを理解し、ページングの利点を他人に説明できるようになる。

- ページングにおける仮想アドレスと物理アドレスの違いを理解し、他人に説明できるようになる。

- ページングの原理を理解し、仮想アドレス、物理アドレス、ページテーブル、ページサイズの関係を他人に理解できるようになる。

課題

課題 1

主記憶上に同時に 4 つのプロセスを配置できるシステムにおける CPU 利用率を求めよ。 ただし、 各プロセスが実行中に I/O 待ちとなる割合を 50% とする。

課題 2

一般に、 スワッピング (swapping) よりも、 ページング (paging) のほうが効率的である理由を説明せよ。

課題 3

仮想アドレス (virtual address) と物理アドレス (physical address) の違いを説明せよ。

課題 4

16 ビットの仮想アドレス空間を持つページングにおいて、ページテーブルの大きさが 8 であった。 ページサイズを答えよ。

略解

課題 1

1 - (0.5)^4 = 0.9375 より約 94%。 各プロセスが I/O 待ちとなる確率が 0.5 であり、 すべてのプロセスが I/O 待ちとなった時に CPU が無駄となるから。

課題 2

スワッピングは主記憶上にあるプロセス全体を外部記憶装置に書き出す。 一方、 ページングは主記憶上にある (例えば 4K バイトの) ページ単位で外部記憶装置に書き出す。 このため、 ページングは、 プログラムが有する参照の局所性 (locality of reference) を活かせるから。

Locality of reference
https://en.wikipedia.org/wiki/Locality_of_reference

課題 3

「物理アドレス」とは、 プログラムが実際に格納されている主記憶上のアドレスである。 例えば、 主記憶の大きさが 256K バイトであれば、 物理アドレスの大きさは 18 ビットである。 「仮想アドレス」とは、 (オペレーティングシステムの仮想メモリによって) 各プロセスが利用できるアドレスである。 例えば、 主記憶の大きさが 256K バイトであっても、 仮想アドレスの大きさが 24 ビットであれば、 各プロセスには 16M バイトのメモリ空間が利用できるように見える。

課題 4

ページテーブルの大きさが 8 (= 2^3) であるから、 ページアドレスは 3 ビットである。 16 ビットの仮想アドレスの上位 3 ビットがページアドレスであるから、 下位 13 ビットがページ内オフセットを表す。 従って、 ページサイズは 8,192 バイトである。

課題 4 の補足

通常は、 仮想アドレス空間の大きさを決定し、 それとともにページングで用いるページサイズを決める。 仮想アドレス空間の大きさとページサイズが決まれば、 自動的に必要なページテーブルの大きさが決まる。

例えば、仮想アドレス空間の大きさが 24 ビットで、 ページサイズが 4 KB のページングを実現しようと決めたなら、 ページテーブルの大きさは 2^24 [B] / 4 [KB] = 4,096 だけ必要となる。 つまり、

(アドレス空間の大きさ) / (ページの大きさ) = (ページテーブルの大きさ)

という関係である。 上記の関係から、 「アドレス空間の大きさ」、 「ページの大きさ」、 「ページテーブルの大きさ」のうち 2 つがわかれば、 もう一つが求められる。

課題 4 は上記の関係を理解しているかを問う問題である (現実には、 ページテーブルの大きさからページサイズを推測するということは普通はしない (それが必要となる場面はほとんどない))。

レポート課題 2025-05-30

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

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

質問

- 仮想記憶について調べていたら、キャッシュメモリとの違いについてが出てきました。キャッシュメモリも、参照の局所性を利用していると思うのですか、これらはどのように違うのでしょうか?

「外部記憶装置のうち、頻繁に使用するものを主記憶に載せて効率化する仕組み」と
考えれば仮想記憶はキャッシュメモリとしての機能も持っている、と言えると思います。

- ページングの参照の局所性についてあまり理解できなかったのですが、よく実行する命令は主記憶に長く置いておくことで、すぐ実行できるようにするということですか?それとも仮想アドレスで前回使ったメモリの周辺を見れば良いから参照する時間が早くなるということですか?

  どちらでもありません。参照の局所性は「局所性」という性質のことです。参照され
  るアドレスが同じようなところに集まる傾向がある、ということです。

  参照の局所性を活かせば「よく実行する命令は主記憶に長く置いておくことで、すぐ
  実行できるようにする」こともできますし、「前回使ったメモリの周辺を見れば良い
  から (正確には「見ることが多いから」) (ページフォールトの発生頻度下がり) 参
  照する時間が早く」することもできます。


[<16. 7. 前半の総復習] [>18. 9. メモリ管理(2)]