オペレーティングシステム #10 計算機工学III オペレーティングシステム #10 主記憶管理： セグメンテーション， ページ化セグメンテーション 2006/06/23 津邑 公暁 オペレーティングシステム #10 ■ ページング ■ 主記憶の再配置システム 仮想アドレスの上位（ページ番号）を 物理アドレスの上位（ページフレーム番号）に 変換することでアドレス変換 フラグメンテーションも改善 ページテーブル 上記変換を行うためのテーブル ページに対応するエントリごとにフラグなどを配置 ➔ ページへのアクセス権などを設定可能 復習 復習：ページングの動作 オペレーティングシステム #10 スワップイン 物理空間 仮想アドレス 02 123 ＝ 0x0FFF 0x1000 0x1FFF 0x2000 物理アドレス 0 0x00000 0x0000 0x2FFF 0x3000 123 0x3FFF 00 01 02 03 04 05 06 07 08 V 1 1 01 1 1 1 1 1 1 P C 0 1 2 3 ページフレーム 0x00FFF 0x01000 0x01FFF 0x02000 0x02FFF 0x03000 0x03FFF 0x04000 0x04FFF 0x05000 0x05FFF 0x06000 011 0 0 0x06FFF 0x07000 0x07FFF 0x08000 0x08FFF 0x09000 0x09FFF 00 01 02 03 04 05 06 07 08 09 オペレーティングシステム #10 ■ ページングの改善法 ハッシュ関数 ➔ ➔ ページテーブルの巨大さを緩和 仮想アドレス空間に比例する大きさが必要だったのが， 物理アドレス空間に比例する大きさまで縮小 連想レジスタ ➔ ➔ ➔ 主記憶へのアクセス回数の緩和 最近使用した「ページ番号→ページフレーム番号」の 変換結果をCPU内で記憶 ページテーブル検索のための主記憶アクセスを削減 復習 オペレーティングシステム #10 ■ ■ ■ ページングの構成法 多重レベルページング (10.3) 0レベルページング (10.4) セグメンテーション セグメンテーション (10.1) ページ化セグメンテーション (10.2) 教科書とは違う順番でやります 今日の内容 オペレーティングシステム #10 10.3 多重レベルページング オペレーティングシステム #10 ■ ページテーブルが巨大 ■ 復習：ページングの問題点 （仮想記憶の大きさと同じエントリ数） ×（同時実行プロセス数） だけのエントリ数が必要 主記憶を圧迫 前回はハッシュ関数を利用することで改善 ➔ 仮想アドレス空間に比例する大きさが必要だったのが， 物理アドレス空間に比例する大きさまで縮小 さらに改善したい 多重レベルページング オペレーティングシステム #10 仮想アドレス 0 2 123 ＝ 物理アドレス 0 123 主記憶 0x0000 0x1000 0x2000 0x3000 0x00000 2 3 6 0 基底アドレス 6000 5000 8000 ページテーブル 0x5000 0x6000 0x7000 0x8000 ページ テーブル ページ テーブル ページ 1 0x01FFF 0x02000 ページテーブル 0x4000 0 1 2 3 4 0 0x00FFF 0x01000 ページテーブルを テーブル 0x9000 多段に 0x02FFF ページ番号 フレーム番号 2 3 0x03000 0x03FFF 0x04000 0x04FFF 0x05000 0x05FFF 0x06000 0x06FFF 0x07000 0x07FFF 0x08000 0x08FFF 0x09000 0x09FFF 0 1 2 3 仮想 4 アドレス 5 空間 6 多重レベルページング オペレーティングシステム #10 仮想アドレス 0 2 123 ＝ 物理アドレス 0 123 主記憶 0x0000 0x1000 0x2000 0x3000 0x4000 基底アドレス 0 1 2 3 4 6000 5000 8000 ページテーブル 0x5000 0x6000 0x7000 0x8000 0x9000 2 3 0x00000 0x00FFF 0x01000 0x01FFF 0x02000 0 1 2 6 0x02FFF 0x03000 当面必要でない 3 0 0x03FFF ページテーブルは， 0x04000 仮想記憶上に置いておける 仮想 4 0x04FFF アドレス 0x05000 ページ 5 空間 0x05FFF テーブル ページ テーブル ページ テーブル 0x06000 0x06FFF 0x07000 0x07FFF 0x08000 0x08FFF 0x09000 0x09FFF 6 オペレーティングシステム #10 ■ ページングを多段化 ■ 2段だけでなく，さらに多段化も可能 ページテーブルを細かく分割可能 ■ 多重レベルページング 必要なテーブルのみを主記憶上に置くことで 主記憶使用量を削減 多段化により，主記憶アクセスは増加 TLBにより解決 オペレーティングシステム #10 10.4 0レベルページング （連想写像方式） オペレーティングシステム #10 ■ 一般的なページング ■ 連想写像方式 主記憶上にページテーブル CPU内のMMUが，ページテーブルを用いて アドレス変換 0レベルページング（連想写像方式） ハードウェアとしてのMMUを持たない 一般的なページテーブルを持たず， 連想メモリで構成したTLBでアドレス変換 オペレーティングシステム #10 物理空間 仮想アドレス 02 789 0x0000 ＝ 0x0FFF 0x1000 0x1FFF 0x2000 物理アドレス 0 0レベルページングの動作 0x2FFF 0x3000 789 0x3FFF 02 0 07 1 05 2 3 00 フレーム V P ページフレーム C ページフレーム 00 01 02 03 04 05 06 07 08 0 05 011 1 02 0 00 011 1 07 1 0 011 1 0 011 1 20 0 30 1 3 0x00000 0x00FFF 0x01000 01 連想メモリ 02 0x02FFF 0x03000 インデクスを持たない 03 0x03FFF 全エントリを並列検索 0x04000 04 0x01FFF 0x02000 0x04FFF 0x05000 0x05FFF 0x06000 0 0 2 0 1 00 0x06FFF 0x07000 0x07FFF 0x08000 0x08FFF 0x09000 0x09FFF 05 06 07 08 09 オペレーティングシステム #10 ■ メリット 高クロック実装が可能 ➔ ■ MMU不要のため，CPU機構が単純化 デメリット TLBヒットしなかった場合のオーバヘッドが膨大 ➔ ■ 0レベルページングの特徴 ソフトウェア処理のため よって... 主記憶使用量の少ないプログラムには高速 主記憶使用量の多いプログラムには非常に低速 オペレーティングシステム #10 10.1 セグメンテーション オペレーティングシステム #10 ■ ■ 大きさが無制限 プロセスは主記憶の空き容量を考慮する必要なし プログラムの簡単化，バグの可能性減少 プロセスごとに固有 他のプロセスからのアクセスに対し保護 プログラム部，データ部，スタック部など分離 ■ ページングで実現可能 ■ 復習：理想的な論理アドレス空間 用途ごとに空間を分けることで， 自プロセス内での不正アクセスの可能性を低減 必要時にはプロセス間で共有も可能 並列動作するプロセス間で共有し， 高速な通信機構として使用 こちらも実現したい オペレーティングシステム #10 ■ ページ（ページング） ■ セグメンテーション 一定の大きさを割り当て単位とする セグメント（セグメンテーション） プロセスに対し複数のセグメントを割り当て ➔ 各セグメントは論理的に独立 ➔ プログラム部，データ部など固有領域として使用可能 各セグメントはその論理空間の大きさを 自由に増減可能 セグメンテーション オペレーティングシステム #10 プロセス 1 プログラム 領域 プログラム 領域 データ 領域 データ 領域 スタック 領域 プロセス間共有も 実現可 データ 領域 スタック 領域 プロセス セグメント 2 データ 領域 セグメンテーション オペレーティングシステム #10 物理空間 仮想アドレス 02 123 0x00000 0x1222 0x00FFF 0x01000 ＝ 0x0000 0x01FFF 0x02000 物理アドレス 0x02FFF 0x03000 1345 00 01 02 03 04 05 06 07 08 V 1 1 10 1 1 1 1 1 1 基底アドレス 0x3FFF 0x03FFF 0x04000 セグメント長 0x04FFF 0x05000 0x05FFF 0x06000 1222 1300 0x06FFF 0x07000 0x07FFF 0x08000 0x08FFF 0x09000 0x09FFF 1300 オペレーティングシステム #10 ■ 利点 ■ セグメンテーション プログラム部，データ部など，用途別に複数を プロセスに割り当て 各セグメンテーションは大きさを増減可 欠点 フラグメンテーション 他の手法と組み合わせて 利用 オペレーティングシステム #10 10.2 ページ化セグメンテーション オペレーティングシステム #10 ■ ページング v.s. セグメンテーション ページング 固定長ブロック ➔ ■ セグメンテーション フラグメンテーションの解 決 ➔ ページテーブル ➔ ➔ 仮想→物理アドレスの 1対1対応 動的再配置による 仮想記憶の実現 複数のアドレス空間 用途別論理空間の実現 アドレス空間の オーバラップ ➔ 複数プロセスによる 空間の共有を実現 オペレーティングシステム #10 ■ ページ化セグメンテーション ページング ＋ セグメンテーション セグメンテーションを， 複数のページフレームにより構成する セグメントごとにページテーブルを用意 ページフレーム セグメント ページフレーム ページフレーム セグメント ページフレーム ページ フレーム番号 番号 ページテーブル ページ フレーム番号 番号 ページテーブル ページフレーム ページ フレーム番号 番号 セグメント ページフレーム ページテーブル オペレーティングシステム #10 仮想アドレス 0 2 123 主記憶 0x0000 ＝ 0x1000 物理アドレス 0 ページ化セグメンテーション 123 0x2000 0x3000 2 セグメント 物理 3 アドレス 6 空間 0 0x4000 0 1 2 3 4 基底アドレス セグメント長 6000 5000 8000 2000 2000 1000 0x5000 0x6000 0x7000 セグメントテーブル 0x8000 0x9000 ページ テーブル ページ テーブル 0 セグメント0用 1 ページテーブルセグメント0 2 ページ番号 フレーム番号 2 3 セグメント 3 0 1 仮想 4 アドレス 5 空間 6 7 ページ テーブル セグメント2 8 9 セグメント1 オペレーティングシステム #10 ■ ページ化セグメンテーションにおける 仮想アドレス 仮想アドレスの構造 仮想アドレス セグメント内相対アドレス ページ セグメント内の オフセット セグメント番号 仮想アドレス セグメント番号 番号 （ページ内相対アドレス） 相対アドレス ページ オフセット 番号 （ページ内相対アドレス） セグメントがページ単位で構成されている ➔ セグメンテーションとページングの階層化 セグメント内相対アドレスが， ページングにおける仮想アドレスに相当 ➔ 仮想アドレスの構造も二階層になっていると 考えるとわかりやすい オペレーティングシステム #10 ■ フラグメンテーションの回避 ■ ■ 主記憶割り当ては基本的にページ単位 複数セグメント 各セグメントは大きさ増減可能 複数使用により，用途別に使い分け可能 プロセス間共有 ■ ページ化セグメンテーションの利点 セグメンテーションとほぼ同様に共有可能 ページテーブルの分散 ページテーブルが複数に分割されるので， 多重レベルページング同様，その一部を 仮想記憶に追い出すことで主記憶使用量削減 オペレーティングシステム #10 ■ 多重レベルページング ■ 今日のまとめ 従来のページングにおける，仮想アドレスの 「ページ番号部」を複数に分割 それぞれをページ番号とし階層化したテーブルを検索 ページテーブルの分割により，テーブルによる 主記憶使用量を削減（残りは仮想記憶へ） 0レベルページング（連想写像方式） MMUを持たず，CPUの構成を単純化（＝高速化） 連想記憶（検索のためのインデクスを持たない）で TLBを構成 オペレーティングシステム #10 ■ セグメンテーション ■ 今日のまとめ セグメント： 仮想記憶と物理記憶を対応させる可変長な単位 プロセスあたり複数のセグメントを許す セグメント間のオーバラップ（共有領域）を許す ページ化セグメンテーション ページングとセグメンテーションの利点を融合 セグメンテーションの利点を生かしつつ ➔ ➔ フラグメンテーションを回避 ページテーブルの分割により，多重ページング同様 主記憶使用量の削減
© Copyright 2024 ExpyDoc
