ページング

ページング

1

ページングの効能

2

ページングの効能

•

→ メモリ上の場所を移動させる

ページングの効能

•

→ メモリ上の場所を移動させる

•

→ （外部）フラグメンテーションを防止

4

記憶管理の問題点の復習

• フラグメンテーション ⇒ 詰めたい

5

記憶管理の問題点の復習

• フラグメンテーション ⇒ 詰めたい

⇒ プロセスの場所を動かすのが難しい

基底アドレシング（ハードの助け）なら 動かせる

• フラグメンテーション ⇒ 詰めたい

⇒ プロセスの場所を動かすのが大変

基底アドレシング（ハードの助け）なら 動かせる

6

記憶管理の問題点の復習

アドレスの変換（⾜し算）をハードで⾏う

⇒ ほとんど時間がかからないので遅くならない

オペランド OP

ベースレジスタ

＋ ^メモリへ ハードの追加必要

更なる改良

• では、アドレスの変換を

もっと本格的にしたらどうなる︖

8

更なる改良

• では、アドレスの変換を

もっと本格的にしたらどうなる︖

⇒ ここでは

• すべてのアドレスをそれぞれに変換する、

つまりアドレスｘに対してｙに変換するという 表を持ったらどうなるか、考えてみる

先頭アドレス分 だけ足しこむ

ベースレジスタ プロセス による方法

１ワードごとに 好きなように

アドレスを変換 ワード ワード ワード

9

更なる改良

• では、アドレスの変換を

もっと本格的にしたらどうなる︖

⇒ ここでは

• すべてのアドレスをそれぞれに変換する、

つまりアドレスｘに対してｙに変換するという 表を持ったらどうなるか、考えてみる

CPUがアクセスしたい アドレス

実際にメモリへ アクセスするアドレス

234 5678

CPU メモリ

アドレス変換表

234 番地

5678 番地

10

ページングへ

• 表のよい点︓

• 変換の仕方をアドレスごとに変えられる

CPUがアクセスしたい アドレス

実際にメモリへ アクセスするアドレス

234 5678 235 8989

CPU メモリ

アドレス変換表

234 5678

235 8989

ページングへ

• 表のよい点︓

• 変換の仕方をアドレスごとに変えられる

• 表のまずい点︓

• 非常に表が大きくなる

⇒ いくつエントリーが必要だろうか︖

CPUがアクセスしたい アドレス

実際にメモリへ アクセスするアドレス

234 5678 235 8989

CPU メモリ

アドレス変換表

234 5678

235 8989

12

ページングへ

• 表のよい点︓

• 変換の仕方をアドレスごとに変えられる

• 表のまずい点︓

• 非常に表が大きくなる

⇒ いくつエントリーが必要だろうか︖

⇒ 表のためのメモリはどれだけ必要か︖ ⇒ 困る

CPUがアクセスしたい アドレス

実際にメモリへ アクセスするアドレス

234 5678 235 8989

CPU メモリ

アドレス変換表

234 5678

235 8989

13

ページングの仕掛

• そこで、昔の人は考えた （1960年代か︖）

14

ページングの仕掛

• そこで、昔の人は考えた （1960年代か︖）

• （アドレス１つ１つを変換するのではなくて）

ブロック単位（例えば4096バイト）毎に変換

ページングの仕掛

• そこで、昔の人は考えた （1960年代か︖）

• （アドレス１つ１つを変換するのではなくて）

ブロック単位（例えば4096バイト）毎に変換

• ブロック内の位置（例︓先頭から５バイト目）は そのまま使う

ブロックの番号（始めからＸブロック目）は

CPUからの指定を、表で変換してメモリに渡す

16

ページングの仕掛

• そこで、昔の人は考えた （1960年代か︖）

• （アドレス１つ１つを変換するのではなくて）

ブロック単位（例えば4096バイト）毎に変換

• ブロック内の位置（例︓先頭から５バイト目）は そのまま使う

ブロックの番号（始めからＸブロック目）は

CPUからの指定を、表で変換してメモリに渡す

42ブロック 目の 5バイト目 7ブロック

目の 5バイト目

CPUがアクセスしたい ブロックの番号

実際にメモリへ アクセスするブロック番号

7 42

CPU メモリ

ブロック番号の変換表

17

ページングの仕掛

• ブロックのことを「ページ」と呼ぶ

18

ページングの仕掛

• ブロックのことを「ページ」と呼ぶ

• ページの大きさを２^Xバイトにする 例えば 4096 (=2¹²) ^バイト

ページングの仕掛

• ブロックのことを「ページ」と呼ぶ

• ページの大きさを２^Xバイトにする 例えば 4096 (=2¹²) ^バイト

ページ メモリ

ページ ページ ページ０

１ページは4096バイト

ページ１

ページＮ ページ２

ページの先頭から５バイト目

20

ページングの仕掛

• ブロックのことを「ページ」と呼ぶ

• ページの大きさを２^Xバイトにする 例えば 4096 (=2¹²) ^バイト

ページ メモリ

ページ ページ ページ０

１ページは4096バイト

ページ１

ページＮ ページ２

ページの先頭から５バイト目

この場所（バイト）は 第０ページの 先頭から５バイト目

ページ内オフセット と呼ぶ

21

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を

22

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を アドレスの上位の残り部分がページの番号を表す

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を アドレスの上位の残り部分がページの番号を表す

（ページを考えなかったときの）メモリアドレス

24

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を アドレスの上位の残り部分がページの番号を表す

ページ番号 ページ内オフセット

（ページを考えなかったときの）メモリアドレス

25

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を アドレスの上位の残り部分がページの番号を表す

ページ番号 ページ内オフセット

（ページを考えなかったときの）メモリアドレス

単にビット位置だけで分割

ページ０

26

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を アドレスの上位の残り部分がページの番号を表す

ページ番号 ページ内オフセット

（ページを考えなかったときの）メモリアドレス

ページ１

ページＮ

ページ０

ページングの仕掛

• ページの大きさを２¹²にしたので

• アドレスの下位 12 ビットがページ内の位置を アドレスの上位の残り部分がページの番号を表す

ページ番号 ページ内オフセット

（ページを考えなかったときの）メモリアドレス

ページ１

ページＮ

28

ページングの仕掛

• アドレス変換は

• ページ番号だけを変換する

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

CPUがアクセスしたいページ メモリにアクセスするページ

1 34

アドレス変換表

29

ページングの仕掛

• アドレス変換は

• ページ番号だけを変換する

ページ内オフセットはそのまま使う

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

30

ページングの仕掛

• アドレス変換は

• ページ番号だけを変換する

ページ内オフセットはそのまま使う

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

CPUがアクセスしたいページ メモリにアクセスするページ

1 34

アドレス変換表

ページングの仕掛

• アドレス変換の流れは

• CPUから出たアドレスを

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

CPU

32

ページングの仕掛

• アドレス変換の流れは

• CPUから出たアドレスを、メモリアドレスに変換

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

CPU メモリ

33

ページングの仕掛

• アドレス変換の流れは

• CPUから出たアドレスを、メモリアドレスに変換 ページ番号は表で変換、オフセットはそのまま

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

CPUがアクセスしたいページ メモリにアクセスするページ

1 34

アドレス変換表

CPU メモリ

34

ことばの追加１

• 仮想アドレス・物理アドレス

• 仮想アドレス︓ CPUから出た変換前のアドレス

ことばの追加１

• 仮想アドレス・物理アドレス

• 仮想アドレス︓ CPUから出た変換前のアドレス 物理アドレス︓ メモリに渡す変換後のアドレス

36

ことばの追加１

• 仮想アドレス・物理アドレス

• 仮想アドレス︓ CPUから出た変換前のアドレス 物理アドレス︓ メモリに渡す変換後のアドレス

ページ番号 １ _{オフセット}^ページ内 ページ番号 34 _{オフセット}^ページ内

CPU メモリ

仮想アドレス 物理アドレス

CPUがアクセスしたいページ メモリにアクセスするページ

1 34

37

ことばの追加１

• 仮想アドレス・物理アドレス

• 仮想アドレス︓ CPUから出た変換前のアドレス 物理アドレス︓ メモリに渡す変換後のアドレス

ページ番号 １ _{オフセット}^ページ内 ページ番号 34 _{オフセット}^ページ内

CPU メモリ

仮想アドレス 物理アドレス

仮想ページ番号 物理ページ番号

CPUがアクセスしたいページ メモリにアクセスするページ

1 34

38

ことばの追加２

• ページテーブル

• ページ番号を変換するアドレス変換表のこと

ページ番号 １ _{オフセット}^ページ内

ページ０

ページ１

ページ34

ページ番号 34 _{オフセット}^ページ内

ページ０

ページ１

ページ34

CPUがアクセスしたいページ メモリにアクセスするページ

1 34

アドレス変換表

CPU メモリ

ページテーブル

確認ポイント

•

仮想ページ番号 １ _{オフセット}^ページ内 物理ページ番号 34 _{オフセット}^ページ内

仮想ページ番号 物理ページ番号

1 34

CPU仮想アドレス ページテーブル 物理アドレスメモリ

40

確認ポイント

• CPUが⾒ているのは仮想アドレス メモリが受け取るのは物理アドレス

• ページ単位で表を使ったアドレス変換

（足し算や数式でない）

仮想ページ番号 １ _{オフセット}^ページ内 物理ページ番号 34 _{オフセット}^ページ内

仮想ページ番号 物理ページ番号

1 34

ページテーブル

CPU メモリ

41

確認ポイント

• CPUが⾒ているのは仮想アドレス メモリが受け取るのは物理アドレス

• ページ単位で表を使ったアドレス変換

（足し算や数式でない）

• ページテーブルの変換はハードウェアで速い

仮想ページ番号 １ _{オフセット}^ページ内 物理ページ番号 34 _{オフセット}^ページ内

仮想ページ番号 物理ページ番号

1 34

CPU ページテーブル メモリ

42

フラグメンテーションの問題は︖

• 可変⻑で、元より⼩さい領域を確保するから 差の分で⼩さな空地ができる

• 空きを詰めるためにプロセスをずらすのは、

アドレス書換えを伴うので難しい

フラグメンテーションの問題は︖

• 可変⻑で、元より⼩さい領域を確保するから 差の分で⼩さな空地ができる

• 空きを詰めるためにプロセスをずらすのは、

アドレス書換えを伴うので難しい

基底アドレッシングのような変換機構を使えば ずらすことができる

44

フラグメンテーションの問題は︖

• 可変⻑で、元より⼩さい領域を確保するから 差の分で⼩さな空地ができる

• 空きを詰めるためにプロセスをずらすのは、

アドレス書換えを伴うので難しい

基底アドレッシングのような変換機構を使えば ずらすことができる

• ではページングだと︖

45

フラグメンテーションの問題は︖

• 可変⻑で、元より⼩さい領域を確保するから 差の分で⼩さな空地ができる

• 空きを詰めるためにプロセスをずらすのは、

アドレス書換えを伴うので難しい

基底アドレッシングのような変換機構を使えば ずらすことができる

• ではページングだと︖

1.ページは固定⻑でどこでもピタリとはまる

2.アドレス変換 ⇒ 物理アドレスでバラバラでも 仮想アドレスでは連続にできる

46

フラグメンテーションの問題は︖

• ページングだと︖

1.ページは固定⻑でどこでもピタリとはまる

2.アドレス変換 ⇒ 物理アドレス上でバラバラでも 仮想アドレスでは連続にできる

…

仮想アドレス上の メモリ空間 ページ０

ページ１ ページ２

ページＮ

仮想ページ番号 物理ページ番号 ページ番号０ ページ番号３ ページ番号１ ページ番号２ ページ番号２ ページ番号０ ページ番号３ ページ番号１

… …

ページテーブル

（アドレス変換表）

物理アドレス上の メモリ空間

ページ０ ページ１ ページ２

ページＮ 仮想ページ０

仮想ページ１ 仮想ページ２ 仮想ページ３ 仮想ページ０

仮想ページ１ 仮想ページ２ 仮想ページ３

…

ページ３ ページ３

ここまでのまとめ ページングは

48

ここまでのまとめ ページングは

• 主記憶を固定⻑ブロック（ページ）に分割し

49

ここまでのまとめ ページングは

• 主記憶を固定⻑ブロック（ページ）に分割し

• ページ番号を変換表（ページテーブル）で 変換する

CPUから出る仮想ページ番号

⇒ 主記憶へアクセスする物理ページ番号

50

ここまでのまとめ ページングは

• 主記憶を固定⻑ブロック（ページ）に分割し

• ページ番号を変換表（ページテーブル）で 変換する

CPUから出る仮想ページ番号

⇒ 主記憶へアクセスする物理ページ番号 ページ内のアドレスはそのまま使う

ここまでのまとめ ページングは

• 主記憶を固定⻑ブロック（ページ）に分割し

• ページ番号を変換表（ページテーブル）で 変換する

CPUから出る仮想ページ番号

⇒ 主記憶へアクセスする物理ページ番号 ページ内のアドレスはそのまま使う

• 主記憶上の物理ページは、仮想ページの順番どおり でなくてよい （変換表でマップするから）

• 固定⻑＋ページ番号が順番任意（不連続でよい）

⇒ （外部）フラグメンテーションが起きない

52

ページングの仕組が 理解できましたか︖

次へ

〇 ×