主記憶管理（メモリ管理）

主記憶管理（メモリ管理）
z プログラムは主記憶上で実行される
z プログラムやデータはファイルとして補助記憶装置に格納されている
z 複数のプログラムを同時に主記憶上で実行する（マルチプロセス）
OSが管理すること：主記憶の効率的に使う
補助記憶装置
割当て済みの主記憶
主記憶
ファイル
未使用領域
プログラムC
プログラムA
プログラムB
プログラムB
プログラムC
プログラムA
プログラムD
プログラムD
主記憶の割当て方式
• 単一プロセスにおける主記憶割当て
– 単一連続割当て
： OSと一つのユーザプログラムが
主記憶領域を分割して使用する
：ユーザプログラムはOSが使用して
いる領域以外を使用する
主記憶
OS
プログラム
• マルチプロセスにおける主記憶割当て
– 固定区画方式
– 可変区画方式
(1) 再配置可能
(2) 再入可能
(3) アドレス変換
1
プログラムに
要求される性質
ハードウェアによる
支援
(1) 再配置可能（relocatable）であるということ
（主記憶のどの領域に配置されても実行可能なプログラム）
プログラム
プログラム
プログラムは主記憶のどの領域に
配置しても正しく動作しなければな
らない
プログラム
プログラム
→ データの参照やジャンプ先の
番地（アドレス）指定は主記憶の物
理的な番地（物理アドレス）で指定
しない（論理アドレスで指定する）
プログラム
主記憶
(2) 再入可能（reentrant）であるということ
プログラム部①
ﾌﾟﾛｾｽA
データ部①
プログラム部①
プログラム部①
ﾌﾟﾛｾｽB
データ部①
一つのプログラムが複数のプ
ロセスによって使用されるとき，
プログラムを個々に配置する
のは主記憶の無駄使いになる
プログラム部①
データ部①
主記憶
2
ﾌﾟﾛｾｽC
(2) 再入可能（reentrant）であるということ
（同時に複数のプロセスとして実行可能なプログラム）
ﾌﾟﾛｸﾞﾗﾑ部（手続き部）
は各ﾌﾟﾛｾｽで共有する
プログラム部①
プログラムが使用するデータ部
はプロセスごとに独立させる
プログラム部とデータ部が分離され，
プロセスごとに独立してデータ領域
を保持できる性質をもつプログラム
プログラム部①
ﾌﾟﾛｸﾞﾗﾑ部は
各プロセスに共通
データ部A
ﾌﾟﾛｾｽAのﾃﾞｰﾀ
データ部B
ﾌﾟﾛｾｽBのﾃﾞｰﾀ
データ部C
ﾌﾟﾛｾｽCのﾃﾞｰﾀ
主記憶
＝再入可能プログラム / リエントラントプログラム
ソフトウェア開発技術者試験問題（平成16年度春期）
問：再入可能（リエントラント）プログラムの説明として，最も適切
なものはどれか。
ア一度実行した後，ロードし直さずに再び実行を繰り返して
も，正しい結果が得られる。
イ実記憶上のどこのアドレスに配置しても実行することが可
能である。
ウ複数のセグメントに分割されており，セグメント単位にロー
ドして実行することが可能である。
エ複数のプロセスで並行して実行しても，正しい結果が得ら
れる。
3
基本情報技術者試験問題（平成17年度春期）
問：処理が終了していないプログラムが，別のプログラムから再
度呼出されることがある。このプログラムが正しく実行され
るために備えるべき性質はどれか。
ア
イ
ウ
エ
再帰的（リカーシブ）
再使用可能（リユーザブル）
再入可能（リエントラント）
再配置可能（リロケータブル）
物理アドレスと論理アドレス
z マルチプロセスの環境では，OSがプログラムの主記憶領域中の
配置場所を決める
→ プログラム自身は実行時の物理アドレスを意識できない
◆ プログラム実行時の命令やデータの主記憶上の番地（アドレス）：物理アドレス
◆ プログラムが想定する命令やデータの論理的な番地（アドレス）：論理アドレス
z プログラムの実行時には，「論理アドレス」は「物理アドレス」に変換
されて実行される
主記憶
（物理アドレス）
プログラム
（論理アドレス）
0番地
命令・データ
論理アドレスから
物理アドレスへ変換
0番地
A番地
（ﾍﾞｰｽｱﾄﾞﾚｽ）
X番地
命令・データ
Y番地
X+A番地
Y+A番地
4
(3) アドレス変換（address mapping/translation）
：論理アドレスから物理アドレスへの変換
• 静的再配置（static relocation)
– 補助記憶装置から主記憶へプログラムをもってくる時
（ロード時）に物理アドレスに変換する
– 実現が容易
• 動的再配置（dynamic relocation)
– 命令の実行時にハードウェア（ベースレジスタ）によって
論理アドレスを物理アドレスへ変換する（後述）
– コンパクション（後述）によって、主記憶の利用効率を向
上できる
主記憶の割当て方式
• 単一プロセスにおける主記憶割当て
– 単一連続割当て
： OSと一つのユーザプログラムが
主記憶領域を分割して使用する
：ユーザプログラムはOSが使用して
いる領域以外を使用する
主記憶
OS
プログラム
• マルチプロセスにおける主記憶割当て
– 固定区画方式
– 可変区画方式
(1) 再配置可能
(2) 再入可能
(3) アドレス変換
5
プログラムに
要求される性質
ハードウェアのよる
支援
固定区画方式
• 主記憶領域をサイズ固定の区画に分割
• 領域サイズを複数用意する
• 区画内に収まるプログラムを選んでロードする
150K
プログラム①
50K
プログラム②
50K
プログラム③
OS
区画A
300K
区画B
200K
区画C
100K
100K
• 一時にロードできるプログラム数，
大きさに制限がある
• あらかじめ設定された区画よりも
大きなプログラムを実行することができない
• 「内部断片化」が発生する
→ 主記憶の使用効率が悪化
区画D
主記憶
内部断片化
• 割り当てられた領域内
で使用されない無駄な
空き領域が生じる
OS
150K
プログラム①
区画A(300K)
• 主記憶の利用効率を
下げる
空き領域
50K
プログラム②
区画B(200K)
区画C(100K)
空き領域が450Kあって
も，300Kのプログラムを 50K
実行できない
プログラム③
主記憶
6
区画D(100K)
可変区画方式
z メモリ領域を可変長の区画で管理する
z 主記憶に格納されるプログラム数，大きさは動的に定まる
z 新しいプログラムをロードするとき，そのプログラムを格納するの
に十分な空き領域を確保し，その領域に割り当てる
z 「外部断片化」の発生
OS
150K
プログラム①
50K
プログラム②
50K
プログラム③
プログラム①
プログラム②
プログラム③
主記憶
可変区画割当ての例
（P1：200K
P2：100K
0
0
OS
50K
0
OS
50K
プロセス１
終了
未使用
P4：130K
0
OS
50K
プロセス
１
P3：160K
プロセス4
割付け
0
OS
50K
プロセス
4
プロセス
4
250K
プロセス
2
350K
プロセス
2
350K
プロセス
3
プロセス
3
未使用
550K
(a)
280K
350K
510K
未使用
未使用
550K
(c)
7
未使用
550K
550K
(b)
プロセス
3
プロセス
3
510K
510K
プロセス
5
未使用
350K
プロセス
3
未使用
550K
プロセス5
割付け
プロセス
2
350K
510K
510K
プロセス2
終了
未使用
250K
プロセス
4
180K
未使用
250K
OS
50K
180K
180K
P5：100K）
(d)
(e)
可変区画方式における
空き領域の割当てアルゴリズム
◆ 新しいプログラムをロードするための主記憶中に散在
する空き領域を探す
初適合（first-fit）... 最初に見つかった十分な空き領域を
割り当てる
– 探索が速く、実現が容易、利用効率はあまりよくない
2. 最適適合(best-fit） ... 十分な領域をもつ最小の空き領域
を割り当てる
– 利用効率はよい（空き領域は最小）が、空き領域を見
つけるオーバーヘッドが大きい
3. 最悪適合（worst-fit） ... 最大の空き領域を割り当てる
– 小さな空き領域が多くなり，領域の利用効率が悪い
1.
メモリ領域割当てアルゴリズム
30KB
割当て要求
(1) 初適合
OS
60KB
80KB
40KB
空き
検索方向
20KB
割当て
済み
(2) 最適適合
(3) 最悪適合
OS
OS
OS
20KB
20KB
20KB
60KB
60KB
30KB
80KB
80KB
40KB
10KB
8
50KB
40KB
空き領域の管理方法(1)
1. リスト方式
空き
0
150
② 150 150
空き 300 50
OS
④ 350 100
0
150K
空き 450 250
150
使用
大きさ
（Kバイト）
プロセス
開始アドレス（ユーザ
300
350
領域の先頭を0番地と
する，単位Kバイト）
プロセス②
150K
プロセス④
50K
100K
450
250K
主記憶
空き領域の管理方法(2)
2. ビットマップ方式
OS
0
0 0 0 0 0 0 1 1
1 1 1 1 0 0 1 1
150K
150
1 1 0 0 0 0 0 0
0 0 0 0
領域の未使用/使用を0と1に対
応させる（この例では25Kバイ
トを1ビットに対応させている）
300
350
プログラム②
150K
プログラム④
50K
100K
450
250K
主記憶
9
外部断片化
z ロードされたプログラムの実行が終了し，空き領域が断片的に存
在する。
z 全体としての空き領域が大きくても，一つ一つの空き領域が小さい
ため、新たなプログラムを割り当てられない。
OS
150K
プログラム①
150K
50K
100K
プログラム②
OS
150K
プログラム②
150K
プログラム④
50K
100K
プログラム③
プログラム④
250K
250K
主記憶
主記憶
外部断片化の解消：コンパクション
• 主記憶上のプログラムを移動することによって、散在す
る空き領域を１つの大きい空き領域にまとめる
→ 主記憶の利用効率が向上する
• プログラムの移動によるオーバーヘッドが大きい
• プログラムは動的再配置可能でなければならない
OS
OS
プログラムF
プログラムF
プログラムH
プログラムH
プログラムD
プログラムD
10
コンパクションを行った場合の可変区画割当ての例
（P1：200K
0
P2：100K
0
50K
250K
プロセス4
割付け
350K
未使用
550K
180K
プロセス5
割付け
390K
390K
プロセス
3
プロセス
3
510K
プロセス
5
プロセス
2
プロセス
2
プロセス
3
プロセス
4
280K
290K
290K
350K
プロセス
3
プロセス
4
未使用
プロセス
2
OS
50K
180K
250K
プロセス
2
0
50K
プロセス１
終了
未使用
P5：100K）
OS
OS
プロセス
1
P4：130K
0
OS
50K
510K
P3：160K
未使用
550K
(a)
550K
(b)
550K
(c)
(d)
動的再配置（dynamic relocation)
– 各命令の実行時に，論理アドレスから物理アドレスへ変換する
10000
プロセスごとに用意する
ベースレジスタ
（再配置レジスタ）
＋
10000
0
LOAD $R0, （500）
500
LOAD $R0, （500）
1234
10500
プログラム
（論理アドレス）
1234
主記憶（物理アドレス）
11
演習問題 5
1.
次の文に相当する方式・状況・現象を何というか。選択群から選べ。
(1)
(2)
(3)
(4)
(5)
複数のプロセスが互いに干渉することなく，同一のプログラムを同時に利用できること。
主記憶のどこに読み込まれても実行可能であること
命令が，命令やデータの記憶場所を識別するのに使用する論理的なアドレス
命令やデータの実体が存在する主記憶上の物理的なアドレス
プログラムの主記憶へのロード時に，論理アドレスを物理アドレスに変換して，主記憶に
配置する方式
(6) プログラムの実行時に，ハードウェアによって論理アドレスを物理アドレスに変換してプ
ログラムを実行する方式
(7) 割当てられた主記憶領域の中で無駄な領域が生じる現象
(8) 主記憶の空き領域が全体として大きくても，それらが主記憶内に散在しているため，プロ
グラムの実行に利用することができない現象
【選択群】
内部断片化物理アドレス
外部断片化
動的再配置
再入可能
再配置可能
論理アドレス
静的再配置
2. 右表の 5 個のプロセスが順に主記憶にロードされて実行され
プロセス大きさ
るときのメモリ内容の推移を(a),(b)の場合について図示し，すべて
P1
100kB
のプロセスの実行が終了するまでの時間を求めよ。ただし，プロ
P2
250kB
セス実行のために利用できる全メモリ容量は 500kB（OS の使用
P3
200kB
領域を除く 100kbyte～600kB の領域）とし，P1 から順番に処理
P4
150kB
を行うものとする。
P5
250kB
(a) 可変区画割付でコンパクションを行わない場合
(b) 可変区画割付で全体の実行時間が最小になるようにコンパクションを行う場合
実行時間
10 ミリ秒
20 ミリ秒
20 ミリ秒
25 ミリ秒
10 ミリ秒
(a) の場合
0
0
OS
OS
0
0
OS
0
OS
OS
0
100
100
100
100
100
100
200
200
200
200
200
200
300
300
300
300
300
300
400
400
400
400
400
400
500
500
500
500
500
500
600
600
t=0
600
t=10
600
t=
600
t=
OS
600
t=
t=
(b) の場合
0
0
OS
OS
0
0
OS
0
OS
OS
0
100
100
100
100
100
100
200
200
200
200
200
200
300
300
300
300
300
300
400
400
400
400
400
400
500
500
500
500
500
500
600
600
t=0
600
t=10
600
t=
600
t=
12
OS
600
t=
t=

Download Report