2010年春学期 MOS輪講第４回 Move!B4 rossi

Presentation on theme: "2010年春学期 MOS輪講第４回 Move!B4 rossi"— Presentation transcript:

1 2010年春学期 MOS輪講第４回 Move!B4 rossi
メモリ管理 2010年春学期 MOS輪講第４回 Move!B4 rossi

2 RAM(Random-Access-Memory)
メモリの仕組み メモリは階層構造になっている メモリを管理するのがmemory managerと呼ばれる場所 高速 高価 小容量 ROM (Read-Only-Memory) 主メモリ RAM(Random-Access-Memory) BIOSはフラッシュメモリの一つで、一応書き換えはできる。 ROMとRAMの中間に位置するもの、らしい。 ていうかROMは今使われていないとの事。 ディスク(ハードディスク等) 低速 安価 大容量

3 メモリ管理方法は主に２種類 実行中のプロセスを、ディスクと主メモリ間で行き来 させるもの それ以外のもの
主メモリに全てのプログラミングを格納できない時に使 われる 例：スワッピング、ページング等 それ以外のもの 主メモリに全てのプログラミングを格納できる時 例：単一プログラミング等

4 スワッピングもページングも使わないメモリ管理方法

5 単一プログラミング 最も単純なメモリ管理方法 単一のプログラムに全メモリを割り当てる 初期のMS-DOSパソコンで使われていた
現在は組み込みシステム以外は使われず 全てのプログラムをメモリにぶち込む手法。 一番単純です。 組み込みシステム以外ではもう使われていません。

6 固定パーティションを使った マルチプログラミング(MFT)
メモリに固定パーティションを作り、複数のプログラム に割り当てる 複数のプログラムを同時実行できる 複数の 入力キュー 単一の 入力キュー 複数のプログラムを同時実行できるってのは、CPUの待ち時間を減らして、効率よく使えるって意味です。 他のプロセスが入出力待ちでブロックされている間、CPUを他のプロセスに使えます。

7 複数の入力キューをもつ マルチプログラミング
複数のプログラムがそれぞれ、ギリギリ入るサイズのパ ーティションに割り振られていく 大きいサイズのパーティションが無駄になりやすい 複数の 入力キュー このサイズに相応しい 大きさのキューが無いので この部分が無駄になってしまう パーティション３は大きいけれど、そこに入れるのに相応しい大きなプロセスが無い場合、使われる事なく無駄になってしまう。 現在の生協食堂は、麺類と通常メニューに分けています。 そこに、多くの職員を割いてサルミアッキのコーナーを作った場合を想像してください。

8 単一の入力キューをもつ マルチプログラミング
全てのキューを一列にする 空き次第、先頭から順に割り振る方法 小さなキューが大きなキューに配置され、無駄になる 先頭キューの大きさを調べて割り振る方法 パーティション全体を埋める事のできない、小さなキューが処理 されづらくなる 小さなパーティションを必ず一つ は用意する方法 小さなキューが処理されやすくなる k回以上スキップしてはいけない というルールを設ける方法 単一の 入力キュー 小さなキューが処理されなくなると会話型プログラムで困った事になる ルール方式では、体育の予約を想像するとわかりやすいです。 何回か落ちると、その人が最優先で予約される事になる。 ただ、これらの方式は朝、管理者が手動でパーティションを設定して放置していた時代のもので、現在は使われてません。 やる意味なさそうだな

9 メモリ管理 マルチプログラミングのモデル化

10 （マルチプログラミングの多重度とも呼ばれる）
CPU使用率について マルチプログラミングによってCPU使用率が改善され る CPU使用率は以下で表す事ができる CPU使用率=1-pn p=あるプロセスが入出力待ちになる確率 n=同じメモリ内にあるプロセスの数 （マルチプログラミングの多重度とも呼ばれる）

11 マルチプログラミングの多重度（同時にメモリ内にあるプロセスの数）
CPU使用率の例 CPU使用率=1-pn CPU使用率 マルチプログラミングの多重度（同時にメモリ内にあるプロセスの数）

12 再配置問題 ・メモリ番地200~300に格納した場合呼び出すのは200+50番地となる
メモリ番地100〜200に格納した場合 バイナリファイル 番地　０ ここにある手続きを呼び出したい メモリ 番地　０ 5０ 10０ 呼び出すのは 100+50番地 10０ 20０ 30０ それぞれのバイナリファイルに自分が格納される番地を覚えておく事で再配置を可能にする ただし、指定した番地の数を書き換える事で、悪意のあるプログラムがある番地のプログラムを実行させる事もできちゃう ・メモリ番地200~300に格納した場合呼び出すのは200+50番地となる ・それぞれのバイナリファイルは自分が格納された番地の情報を記憶する 　・悪意のあるプログラムに誘導する事が可能になってしまう

13 再配置問題 ・メモリ番地200~300に格納した場合呼び出すのは200+50番地となる
メモリ番地100〜200に格納した場合 バイナリファイル 番地　０ ここにある手続きを呼び出したい メモリ 番地　０ 5０ 10０ 呼び出すのは 100+50番地 10０ 20０ 30０ それぞれのバイナリファイルに自分が格納される番地を覚えておく事で再配置を可能にする ただし、指定した番地の数を書き換える事で、悪意のあるプログラムがある番地のプログラムを実行させる事もできちゃう ・メモリ番地200~300に格納した場合呼び出すのは200+50番地となる ・それぞれのバイナリファイルは自分が格納された番地の情報を記憶する 　・悪意のあるプログラムに誘導する事が可能になってしまう

14 メモリの保護 バイナリが書き換えられると他の番地のプログラムを 実行するように誘導できる 解決法
メモリを分割し、それぞれに状態や権限を記述した保護 コードを割り振っておく 保護コードとプログラムの権限が違う場合、トラップする 保護コードはOSだけが干渉できる ベースレジスタとリミットレジスタの二つのハードウェアを 用意する ベースレジスタにはメモリの先頭番地 リミットレジスタにはメモリの長さ（リミット）が格納される レジスタ方式だと、メモリアクセスの度に比較と加算を行う 比較はたいした事ないが、加算は時間がかかるため、全体的な処理がおそくなる 昔のスパコンに使われただけで、今はもうほとんど使われてません

15 メモリ管理 スワッピング

16 スワッピング プロセス全体を、メモリとディスクの間で行き来させる メモリに全てのプロセスが入り切らない場合に使う パーティションサイズは可変

17 メモリコンパクション (memory compaction)
メモリ上のプロセスを丸ごと寄せて まとまったホール（空き領域）を確保する方法 ただし時間がかかる この領域を下にまとめて この二つの部分を 併せた大きなホールを確保する

18 プロセス成長分の場所確保 プロセスが成長する（大きくなる）時がある そのため成長分として空間を余分に確保する方法
プログラムの外部に拡張する方式 プログラムの 内部に成長分を確保する 方式

19 ビットマップを用いたメモリ管理 方法：メモリはある割当領域ごとに分割される
割当領域ごとに１ビット設け、メモリの使用状況を表現する（空き であれば０、使用中なら１） ０（空き）がk個以上続けば、プロセスに割り当てる 問題点：いちいちビットマップの状態（１か０か）を調べなければ ならないので遅くなる

20 連結リストを用いたメモリ管理 メモリをセグメントとして管理し、連結する セグメントには 一番最後の項目は次のエントリへのポインタ
状態（プロセスかホールか＝空きの状態） 開始番号 長さ　　　　　　　が含まれる 一番最後の項目は次のエントリへのポインタ プロセス毎に検索する事ができ、検索が楽になる

21 連結リストの検索方法 ファーストフィット 始めから検索して最初に見 つかったホールにプロセスを 割り当てる方法 ネクストフィット
最後に検索した位置を記憶 しておく方法 ベストフィット 全てのホールの中で、一番 ギリギリで入るホールにプロ セスを割り当てる方法 クイックフィット ホールをよく使うサイズ毎に 分類してとっておく方法 ファーストフィットだと大きいホールにも小さなプロセスをいれてしまう ベストフィットだと、全てのホールにギリギリ入るプロセスが入れられるため、何も入らないような小さなホール（無駄）が大量にできてしまう クイックフィットは、4KB、８KB、１６KB、２０KBというように、よく使われるサイズ毎にホールを分類してとっておく方法

22 メモリ管理 仮想メモリ

23 仮想メモリ プログラムやプロセスの一部を、メモリとディスクの間 でやり取りする メモリに入らない大きさのプログラムが扱える プロセスの一部
仮想アドレスは直接メモりバスに送られず、MMUで一度仮想アドレスから物理アドレスに変換される プロセスの一部

24 仮想メモリの概念 CPUから発せられた仮想アドレスはMMUで一度 物理アドレスに変換される
仮想アドレス空間の区切り（ページ）と物理アドレス 空間（ページフレーム）の関係はページテーブルに 保管されている ページテーブルの例

25 ここで一つ疑問が・・・ ページ（仮想アドレス空間）の方がページフレーム（実 在する物理メモリアドレスの空間）より多い 当然、居場所のない
ページができてしまう 図を見ると分かる通り、右側の「実在」する物理メモリアドレスよりも、左側の仮想アドレス空間の方が数が多いです。 当然、居場所のない仮想アドレス空間も出てきます。 そこで活躍するのが存在/不在ビット（1ビットで、ページ対応する存在するなら1、存在しないなら）です

26 存在/不在ビット ページ（仮想アドレス空間）に対応するページフレー ム（物理メモリ空間）が存在するかどうかを示す
１ビットで、存在するなら「１」不在なら「０」 存在/不在ビットが「１（存在）」なら、対応するページフ レームがMMUから出力される 存在/不在ビットが「０（不在）」なら、ページフォールト を起こす ほとんど使われていないページフレームの内容を一度 ディスクに退避させる 空いたページフレームを要求されたページに割りあて、 マッピングテーブルを修正する ページフォールトのイメージは、足りない部室の割当を想像するとわかるかも？ 優先度の高い部活が現れると、どうでもいい、活動していない部活は追いやられて、そこに優先度の高い部活が入り込む。

27 MMU(Memory Management Unit)の内部操作
入って来る仮想アドレスのうち、最初の４つはページテーブルの検索に使われる。 ４つのうちの最初の３つは目次というか、目録（インデックス）です。対応するページテーブルの検索に使われます。 ４つのうちの残り一つはそのまま存在/不在ビットになっています。 対応するページテーブルの３ビットと、元々あった（入って来た仮想アドレス）の１６ビットの最後の１２ビットと合体させたものが、最終的に物理アドレスとして出て行きます。 そのうちの最後の１ビットは存在／不在ビットと呼ばれ、そのページに対応するページフレームの有無を表す。

28 マルチレベルページテーブル ページテーブルには、エントリ数が巨大になる という問題があった そこで、ページテーブルを複数に分割した
仮想アドレスを分割すると、各ページテーブル内での イ ンデックスとオフセットが得られる 32ビット （例）　 10ビット 10ビット 12ビット ページサイズ4kb、仮想アドレス32ビットの場合は１００万エントリ！！ インデックスというのは、そのページアドレスの「中で」どこを見ればいいかということです。目次とか、目録みたいなものです。 仮想アドレス Page Table 1 Page Table 2 オフセット Page Table 1 Page Table 2 第１ページテーブルのインデックス 第２ページテーブルのインデックス

29 マルチページテーブルの動き 第１ページテーブルの各エントリは次のページテーブ ルへのポインタ/アドレスを含む スタック領域用のページテーブル
（第２レベルのページテーブル） エントリ0はプログラムテキスト用のページテーブルのアドレスが入っています エントリ１はデータ領域用のページテーブルのアドレスが入っています エントリ1023はスタック領域用のページテーブル（第２レベルのページテーブル）のアドレスが入っています。 データ領域用のページテーブル プログラムテキスト用のページテーブル

30 ページテーブルエントリの構造 OSによって長さが多少違うが、中身は大抵同じ 修正ビット 存在/不在ビット 参照ビット 保護ビット
キャッシング不可ビット ページフレーム番号 ページテーブルエントリは最終的にページフレーム番号を得る事を目的としていますが、いろんなビットがくっついています。 存在/不在ビットによって、そのまま割り当てるか、ページフォールトを起こすかを判断します 保護ビットで、アクセス権限を決めます（読み込み可能、書き込み可能など） 修正ビットで、そのページに変更があったかどうか 変更があったならそのページをディスクに書き戻し 変更がなかったら単にページフレーム内のページを破棄する。必要ないからねー 参照ビットは、そのページに何かしらのアクセスがあった場合に設定されます。 ページフォールトが起きると、使われていないページフレームが割り当てられますが、このページフレームが使われているかいないかは参照ビットで判断されます キャッシング不可ピットは、コマンドからの新しい入力を受け付ける場合に、古いキャッシュを使ってしまわないように設定できる 参照ビット 保護ビット

31 連想メモリ （TLB:Translation Lookaside Buffer）
背景 仮想メモリだと、ページテーブルを参照する度にメモリにアクセスし なければならない 頻繁に参照される項目は限られている 目的 できる限りメモリアクセス無しでページテーブルを参照する 手段 コンピュータに小容量のハードウェアデバイスを装備させ、頻繁に 使う項目をまとめた小さなページテーブルをデバイスの中に格納す る 何がハッピーか 小さなページテーブルに格納されているエントリなら、メモリアクセス無しで ページフレーム番号を得る事ができる（速いし、楽）

32 TLBの構造とソフトウェアTLB ソフトウェア上でTLBを管理するものもある TLBの構造 ソフトウェアTLB
TLB用のハードウェアの代わりに、多量のキャッシュ領域を CPU上に割り当てられるようになる

33 逆引きページテーブル ページフレームをインデックスとしてページを検索す る方法 ページ （仮想アドレス空間） MMU ページフレーム
（実メモリ空間） ページフレーム CPU ページフレームは、ページより少ないです。 つまり、逆引きページテーブルだと、少ない数のページを探すだけで済みます。 仮想アドレス

34 メモリ管理 ページ置き換えアルゴリズム

35 ページ置き換えアルゴリズム ページフォールトが起きた時、ディスクに中身が書き 戻されるページフレームを選ぶアルゴリズム
一番長い間使われないページを選ぶのがベストであ り、目的でもある

36 最適ページ置き換えアルゴリズム 将来要求される命令を全て把握している場合に使用 できるアルゴリズム
将来的に最も遅いタイミングで要求されるページを選 択する 実現は不可能だが、最適である そのため、アルゴリズム最適化の基準となる 一応、シミュレーションを一度行って、その履歴を見ることで、将来要求される命令を予測する手段はある。 しかし、実システムでは不可能なため、採用されない。

37 NRU(Not Recently Used) アルゴリズム
参照ビットと変更ビットの二つを用意する ページが参照された際、参照ビットを「１（参照有）」に設 定する 定期的にOSが全ページの参照ビットを「０（参照なし）」 に設定する 各ページを参照ビットと変更ビットによってクラス分け し、数字の小さい方のページを選択する Class 0:参照なし、変更なし Class 1:参照なし、変更あり Class 2:参照あり、変更なし Class 3:参照あり、変更あり 理解と実装が簡単らしい 簡単に言うと、一定期間内に参照される（使われる）と、参照ビットが１になっていて、それ以外の使われてないやつは参照ビットが０のままだから、参照ビットが０（使われてない）ページを使っちゃおうって話です。

38 先入れ先出しページ置き換え FIFO(First-in,First-out)アルゴリズム
リストを作って、順にページを追加していく リストの先頭ページが最も古いページ 最後尾が最新のページ ページフォールト発生時には、先頭のページ（最も古いページ） を消して、新たなページが最後尾に追加される 使用頻度の高い、あるいは重要なページが消されてしまう可能 性がある 現在ではほとんど使われない 最後尾・新 先頭・旧 A B C D E F G 除去 最新 A B C D E F G H 追加

39 セカンドチャンス置き換え アルゴリズム NRUアルゴリズムと先入れ先出しアルゴリズムを併せ たもの
リスト先頭の（最も古い）ページが参照されていなかった ら、そのまま除去 リスト先頭の（最も古い）ページが参照されていたら、リス トの最後に最新のページとして追加する 先頭リストが参照されていない場合 A B C D E F G 除去 先頭リストが参照されている場合 最新として追加 A B C D E F G A

40 クロックページ置き換え アルゴリズム セカンドチャンス置き換えアルゴリズムのリストを、時計 状にしたもの 参照されてなかったらリストから除去
参照されていたら「参照無し」にして針を一つ進める

41 LRU(Least Recently Used) ページ置き換えアルゴリズム
過去によく使われたページは、将来もよく使われるだろうと予 測する手法 過去に使われなかったページは、これからも使われないだ ろうと予測される 命令が実行される度にそのページのカウンタを+1する 当然、使われればカウンタは増える ページフォールトが起きると、OSは前ページのカウンタを チェックする 最もカウンタの少ない（使われてない）ページを選択する

42 そもそも・・・ 全ページの中で頻繁に参照されるのはほんの一部
頻繁に参照されるものをメモリに格納しておけばディスク とデータをやり取りせずに済む ワーキングセット（プロセスが現在使用しているページ のセット）を実行前にメモリに持って来ておけば、ディ スクからページを持って来る必要がない 実行前にワーキングセットをメモリに持って来ておく方法 は、ワーキングセットモデルと呼ばれる

43 ワーキングセットページ置き換え アルゴリズム
プロセス開始からの時間をカレント仮想時間として記憶し、最後 に使用した時間も記憶する 参照されていなければ、 最後に使用した時間−カレント仮想時間が最大のものを選択 参照されていれば、ワーキングセットとみなし、手出しはしない

44 スラッシング(thrasing) ワーキングセット全体をメモリに格納できない場合、プ ロセスは多くのページフォールトを発生させてしまい、 実行が遅くなる 命令があるたびにメモリにページを取りにいき（10ミリ秒）、 実行時間（数ナノ秒）より長くなるため 数命令ごとにページフォールトを発生させてしまう現 象をスラッシング（thrasing）という

45 WSClockページ置き換えアルゴリズム
ワーキングセットページ置き換えアルゴリズムとクロック ページ置き換えアルゴリズムの併用版 参照されているなら、そのページをワーキングセットとみなし、「参照された」事にして、針を一つ進める 参照されていなかったら、「カレント仮想時間ー最後に使用された時間」が一定以上になったらそのページを選択して、針を一つ進める

46 ページ置き換えアルゴリズムの一覧表 アルゴリズム 特徴 最適置き換え 実現不可能だが、ベンチマークとして有用
NRU(Not Recent Used) 粗悪である FIFO(First-In, First-Out) 重要なページを除去してしまう可能性あり セカンドチャンス FIFOの改良版 クロック 実用的 LRU(Least Recently Used) 優れているが、実現は困難 NFU(Not Frequently Used) LRUに時間も考慮させたもの ワーキングセット 実現に若干コストがかかる WSClock 効率のよいアルゴリズム

47 メモリ管理 ページ置き換えアルゴリズムのモデル化

48 Beladyの異常振る舞い(FOFIの時)
ページフレームが多ければ多いほど、ページフォー ルトの回数が少なくなるとは限らない 反例は以下の通り。5つのページフレーム(番号0〜4) があると仮定している。 これは、FOFI（先入先出）アルゴリズムの際の例。 ページフレーム3個だとページフォールトが９回なのに、ページフレーム4個だとページフォールトが１０回起きてしまうという不思議現象

49 スタックアルゴリズム 各ページに対するメモリ参照を仮想ページ番号でリス ト化したものを参照列という 参照列通りにページを参照する
この後も使います 参照列通りにページを参照する ページフレームが一杯になったらページ置き換え 異常振る舞いが起きないという特徴を持つらしいです

50 距離列 ページがある場所からスタックのトップ（最上位）まで の距離で表現（距離列）
参照列での表現に比べて、参照が広がってもページ フォールトが起きにくいという特徴がある

51 ページフォールト率の予測 距離列でページの関係を表現すると、以下の式で ページフォールト数を予測できるようになる
n=ページ数　m=ページフレーム数　k=参照距離　 C∞=スタックにないページ数

52 メモリ管理 ページングシステムの設計時の課題 OS設計の中でも、ページングシステムを設計する際に重要視すべき課題をいくつかご紹介

53 局所的割当て方式 or 大域的割当て方式1 局所的割当て方式 大域的割当て方式 Aのページだけ見ている 全体を 見ている

54 局所的割当て方式 or 大域的割当て方式2 一般的には大域的割当て方式の方がうまく動作す る
局所的割当て方式は各プロセスごとに局所的にペー ジの置き換えを行う ワーキングセットが成長する場合、メモリに入り切らな くなる（スラッシング） 大域的割当て方式は全プロセスをみてページの置き 換えを行う ワーキングセットのサイズが変動しても動作する 一般的には大域的割当て方式の方がうまく動作す る

55 負荷制御 メモリにあまりに多くのプロセスが存在すると、スラッシ ングが起きてしまう事がある
そこで、スラッシングが無くなるまで、いくつかのプロセス を一度ディスクにスワップアウトさせる しかし、メモリ上のプロセス数を減らしすぎると、CPUが アイドル状態になる事が多くなる

56 ページサイズ ページサイズを小さくするとよくなる事 ページサイズを小さくすると大変な事
ページ内部の無駄、内部フラグメンテーションを減らす 事ができる 小さなプログラムに対して大きくページを割り振らずに済 む（メモリの無駄を減らせる） ページサイズを小さくすると大変な事 プログラムに必要なページ数が多くなる ディスクへの移動はページ単位なので、ディスクへの データ転送がそれだけ時間がかかる ページテーブルのサイズが大きくなる 小さいと良い事 内部フラグメンテーションを減らす事ができる ４kbのプログラムに対して32kb割り振る必要が無くなる

57 命令空間とデータ空間の分離 アドレス空間が小さすぎた場合、命令（プログラムテキスト） とデータを同時に格納しきれない場合がある
命令を格納するI空間とデータを格納するD空間の二つの アドレス空間を持たせる 特別なハードウェアなしに、利用可能なアドレス空間が２倍に なる

58 共有ページ 複数のユーザが同じプロセスを使いたい場合、コピー を作るよりも、共有した方が効率的 解決法
しかし、データなどの書き込みも行うものは共有できない 解決法 UnixのForkシステムなどはプログラムテキストとデータ、 両方を親プロセス・子プロセスで共有する しかし、両プロセス内の全データページを「READ ONLY」にしな ければならない 書き込みがあった場合のみ、コピーを作成し、オリジナ ルとコピーの両方を「READ-WRITE」にする コピーオンライトと呼ばれる。 コピー回数を軽減できる（writeされたものしかコピーしないため）

59 クリーニング方策 要求がある度に、メモリ全体で空きページを検索する のは大変である
そこで、ページフレームのプールを設け、追い出すべ きページを入れておく 要求があった時は、プールの内部を調べるだけで済 む

60 仮想メモリインタフェース プログラマが、仮想アドレス空間をメモリマッピングで 制御できるようにしたもの プログラムの効率を高める事ができる
例：共有メモリの制御 メッセージを送信側から受信側にコピーする代わりに、 送信側と受信側のマッピングを変える事で高性能なメッ セージ通信も可能

61 メモリ管理 実装上の課題

62 実装上の課題 設計段階だけでなく、実装段階でも重要な課題はい くつか存在する ページングへのオペレーティングシステムの関与
プロセス生成・プロセス実行・ページフォールト発生時の対応・プ ロセス終了時の対応等 ページフォールト処理 命令のバックアップ メモリ内のページのロック（pinning） バッキングストア 方策と機構の分離 ページフォールトは、一言で言えば、複雑な処理をOSが行わなければならない事 命令のバックアップは、ページフォールトが発生した際、どこから命令で、どこからがメモリアドレスなのか区別するのはOSに対処をゆだねられるという事 バッキングストアは、ディスクのスワップ領域の話です。ページテーブル全体をディスクのスワップ領域にコピーさせる事はせず、成長領域を除いた「生きている」部分だけをコピーさせた方が効率が良い。

63 メモリ内のページのロック(pinning)
入出力待ち中のプロセスが、ページング置き換えア ルゴリズムに、追い出しページの対象として選ばれて しまう場合がある 解決策として、入出力を行っているページを、メモリ内 にロックする方法がとられる そうすれば、追い出されることはない。ハッピー。 メモリ内にページをロックする事をピンニング(pinning)と いう

64 バッキングストア ページをスワップアウトさせる時の話 ページテーブル全体よりも、使用されているページだ けをスワップアウトさせた方が効率的
ただし、ディスクマップを主メモリ内で持っていなければならないという問題は発生する

65 方策と機構の分離 ユーザ空間とカーネル空間を作り、分離させる コードをモジュール化しやすくなり、柔軟性が増す
しかし、ユーザ空間とカーネル空間を行き来する手間が かかる

66 メモリ管理 セグメンテーション

67 セグメント 完全に独立なアドレス空間をセグメントという
プログラムが内部で成長する際、空きが多い別ページ テーブルからページフレームを持って来る場合がある セグメンテーションでは、セグメントを使ってこの管理を 動的に行う事を目的とする 可変である ページは固定サイズのアドレス空間だったのに対して、セグメントは可変サイズのアドレス空間の割り方 実現方法等も異なるものになる この一つ一つが セグメント

68 ページングとセグメントの違い 項目 ページング セグメンテーション プログラマはこの手法が採用されている事を意識する必要があるか いいえ
はい 存在する線形アドレス空間の数 １ 多数 アドレス空間の合計は物理メモリサイズを越えるか 命令とデータは区別され、かつ分離されて保護されるか 可変サイズのテーブル取り扱い 不可 可 ユーザ間での手続き共有が簡単に行えるか 手法の目的 限られた物理メモリで、大きな線形のアドレス空間を得るため プログラムとデータに分解して、それぞれ独立したアドレス空間に格納し、共有と保護を容易にするため

69 外部フラグメンテーション （チェッカーボーディング）
サイズの異なるセグメントを入出力させていると、多数 の小さなホールが発生する コンパクション（寄せる事）によって対処する 図のように、ちゃんと入るようにセグメントを入れ替えていくとちょこちょこホールが発生する 一番右の図のように、セグメントを寄せる（コンパクション）によって対処する事ができる この事を「チェッカーボーディングの削除」と呼ぶそうです

70 ページングを併用した セグメンテーション(MULTICSの例)１
セグメントは可変な分、巨大になりやすい メモリ内部にセグメンテーション全体を入れる事は難し い、そこで・・・ ページングの利点−セグメント全体をメモリに格納する必 要がない セグメンテーションの利点−プログラミング、モジュール 化、保護、共有が容易 以上の二つを併せた方式が開発された MULTICSは1970年代発売のHoneyWell 6000マシン上で走っていたらしいです kenzさん曰く、今ではほとんど使われていないらしいです・・・・

71 ページングを使用した セグメンテーション(MULTICSの例)２
セグメントの情報を記述した記述子セグメントをセグメ ントテーブルに格納し、それ自体ページ化 ただし、パソコンが高速TLBを実装している必要有 セグメント記述子 右のようなセグメント記述子が セグメントテーブルに格納され、テーブル全体が一つのページとなる セグメントテーブル

72 ページングを併用した セグメンテーション(MULTICSの例)３
各ページテーブルのエントリが次のページテーブル の場所を示す（マルチページテーブルと同じ）

73 ページングを併用した セグメンテーション(Intel Pentium)１
MULTICSと同じく、セグメンテーションとページングを 併用している 仮想メモリは、LDT（Local Descriptor Table）とGDT(Global Descriptor Table)の二つを持っている 各テーブル検索にはレジスタ内のセレクタを使う セレクタの構造 LDTとGDTはどちらもセグメント記述子を含んだページになっている セレクタはその中身を検索する時に使います

74 ページングを併用した セグメンテーション(Intel Pentium)2
セグメント記述子の構造 ベースアドレスは、オフセットと併せて３２ビットの線形アドレスになります リミットフィールドはセグメントのサイズを表します。ただし、単位はビットではなく、ページです。

75 線形アドレスからページを選択 基本的な検索方法はマルチページテーブルと同じです
分割されたアドレスはそれぞれのテーブルでのインデックスとなり、 各エントリは次のページテーブルへのポインタとなる

76 保護リング 以下の様に、保護のレベル分けを表す事ができる。 保護リングというそうです。
中の階層にアクセスするにはコールゲートと呼ばれる記 述子が参照されます

77 まとめ メモリは非常に重要なリソースである スワッピングを使用するとメモリの許容容量以上のプロセス を取り扱える
仮想アドレスを使うと、メモリ空間を増やせる ページング置換えアルゴリズムはWSClockが最適 メモリ管理の設計と実装には様々な課題がある セグメンテーションはサイズを変えれるデータ構造であり、 プログラムの共有やセグメントの保護が容易になる