Microsoft PowerPoint - OS09.pptx

Similar documents
Microsoft PowerPoint - OS11.pptx

Microsoft PowerPoint - OS08.pptx

Microsoft PowerPoint - OS07.pptx

Microsoft PowerPoint - OS12.pptx

Microsoft PowerPoint - No6note.ppt

Microsoft PowerPoint - No7note.ppt

Microsoft PowerPoint - os ppt [互換モード]

Microsoft PowerPoint - sp ppt [互換モード]

Operating System 仮想記憶

Microsoft PowerPoint - No15›¼‚z‰L›¯.ppt

OS

Microsoft PowerPoint - OS04.pptx

Microsoft PowerPoint - os ppt [互換モード]

PowerPoint プレゼンテーション

Microsoft PowerPoint - sp ppt [互換モード]

10-vm1.ppt

Microsoft PowerPoint - OS12.pptx

講義計画 1. コンピュータの歴史 1 2. コンピュータの歴史 2 3. コンピュータの歴史 3 4. 論理回路と記憶, 計算 : レジスタとALU 5. 主記憶装置とALU, レジスタの制御 6. 命令セットアーキテクチャ 7. 演習問題 8. パイプライン処理 9. メモリ階層 : キャッシュ

この方法では, 複数のアドレスが同じインデックスに対応づけられる可能性があるため, キャッシュラインのコピーと書き戻しが交互に起きる性のミスが発生する可能性がある. これを回避するために考案されたのが, 連想メモリアクセスができる形キャッシュである. この方式は, キャッシュに余裕がある限り主記憶の

メモリ管理

Microsoft PowerPoint - OS10.pptx

OS

MMUなしプロセッサ用Linuxの共有ライブラリ機構

020105.メモリの高機能化

メモリ管理

スライド 1

Microsoft PowerPoint - ARC-SWoPP2011OkaSlides.pptx

Microsoft PowerPoint ppt

Microsoft PowerPoint - pc11.ppt

C5

コンピュータのしくみ

Microsoft PowerPoint mm

システムLSIとアーキテクチャ技術  (part II:オンチップ並列            アーキテクチャ)

C に必要なコンピュータ知識 C はコンピュータの力を引き出せるように設計 コンピュータの知識が必要

04-process_thread_2.ppt

Microsoft PowerPoint - 11_4-4-5pagerepl.pptx

21 章のお話

< B8CDD8AB B83685D>

計算機概論

システムLSIとアーキテクチャ技術  (part II:オンチップ並列            アーキテクチャ)

今週の進捗

V8_教育テキスト.dot

Microsoft PowerPoint - ICD2011TakadaSlides.pptx

PowerPoint Presentation

Microsoft PowerPoint - OS08 [互換モード]

Microsoft Word - nvsi_050110jp_netvault_vtl_on_dothill_sannetII.doc

Microsoft PowerPoint - 11Web.pptx

OS 論文購読チャレンジ 仮想マシンのメモリ管理 浅井明里 王力捷

TFTP serverの実装

PowerPoint プレゼンテーション

計算機アーキテクチャ

Microsoft PowerPoint - OS06.pptx

スライド 1

メモリについて考えてみよう_REL_

OS

Microsoft PowerPoint - No3.ppt

Microsoft PowerPoint - 11.pptx

スライド 1

arduino プログラミング課題集 ( Ver /06/01 ) arduino と各種ボードを組み合わせ 制御するためのプログラミングを学 ぼう! 1 入出力ポートの設定と利用方法 (1) 制御( コントロール ) する とは 外部装置( ペリフェラル ) が必要とする信号をマイ

C プログラミング 1( 再 ) 第 5 回 講義では C プログラミングの基本を学び演習では やや実践的なプログラミングを通して学ぶ

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

メモリ管理

Microsoft PowerPoint - chap4_slide a.ppt

Microsoft PowerPoint - sp ppt [互換モード]

Microsoft PowerPoint - OS02.pptx

CPUスケジューリング

Microsoft PowerPoint - ARC2009HashiguchiSlides.pptx

Microsoft Word - レポート回答集.docx

出 アーキテクチャ 誰が 出 装置を制御するのか 1

2.RL78 での割り込み処理 ( 割り込み受け付け ) マスクが解除された (xxmk ビットが 0 の ) 割り込み要求信号は 2 つの用途で使用されます 一つ目は,CPU のスタンバイ状態の解除です この動作は, 割り込み優先順位とは全く無関係で, マスクされていない (xxmk=0 の )

Microsoft PowerPoint - OS02.ppt

Microsoft PowerPoint - ARCEMB08HayashiSlides.ppt [互換モード]

コンピュータ工学Ⅰ

ソフトウェア基礎技術研修

命令セットの構成例 a) 算術 演算命令 例 )ADD dest, source : dest dest + source SUB dest, source : dest dest - source AND dest, source : dest dest AND source SHR reg, c

05-scheduling.ppt

hard5.pptx

Microsoft Word - r0703.doc

Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]

Microsoft PowerPoint ppt

コンピュータ工学Ⅰ

データセンターの効率的な資源活用のためのデータ収集・照会システムの設計

スライド タイトルなし

メモリと記憶装置 2

マニュアル訂正連絡票

FIT2015( 第 14 回情報科学技術フォーラム ) RC-003 ファイル格納位置制御による Hadoop MapReduce ジョブの性能の向上 藤島永太山口実靖 工学院大学大学院工学研究科電気 電子工学専攻工学院大学工学部情報通信工学科 1. はじめに近年, 世界中の情報量が爆発的に増加し

また RLF 命令は 図 2 示す様に RRF 命令とは逆に 各ビットを一つずつ 左方向に回転 ( ローテイト ) する命令である 8 ビット変数のアドレスを A とし C フラグに 0 を代入してから RLF A,1 を実行すると 変数の内容が 左に 1 ビットシフトし 最下位ビット (LSB)

Microsoft PowerPoint - 09_2008_0619.pptx

型名 RF007 ラジオコミュニケーションテスタ Radio Communication Tester ソフトウェア開発キット マニュアル アールエフネットワーク株式会社 RFnetworks Corporation RF007SDK-M001 RF007SDK-M001 参考資料 1

PowerPoint プレゼンテーション

-2 外からみたプロセッサ GND VCC CLK A0 A1 A2 A3 A4 A A6 A7 A8 A9 A10 A11 A12 A13 A14 A1 A16 A17 A18 A19 D0 D1 D2 D3 D4 D D6 D7 D8 D9 D10 D11 D12 D13 D14 D1 MEMR

システムソフトウエア2013/1/30 演習問題 学科 学籍番号 氏名 1. つぎの文章の空白を埋めなさい. コンピュータは,CPU( 中央処理装置 ) とメモリ, およびその他の入出力装置から構成されて いる. このうち,CPU は命令の (a) とデコードなどを行う制御部と, 実際の計 算を行う

第 7 章 ユーザー データ用表領域の管理 この章では 表や索引を格納するユーザー データ用表領域の作成や 作成後のメンテナンスに ついて解説します 1. ユーザー データ用表領域の管理概要 2. ユーザー データ用表領域作成時の考慮事項 3. ユーザー データ用表領域の作成 4. ユーザー データ

増設メモリ 1. 機能 型名 N N N N N GB 16GB 3 (x2 枚 ) (x2 枚 ) (x2 枚 ) (8GBx2 枚 ) (16GBx2 枚 ) DDR3-1066(PC3-8500) 動作クロック

Microsoft PowerPoint ppt

増設メモリ 1. 機能 型名 N N N (x1 枚 ) (x1 枚 ) (x1 枚 ) DDR3-1333(PC ) SDRAM-DIMM, Unbuffered,ECC 動作クロック 667MHz( 差動 ) 1.5V 型名 N8102

組込み Linux の起動高速化 株式会社富士通コンピュータテクノロジーズ 亀山英司 1218ka01 Copyright 2013 FUJITSU COMPUTER TECHNOLOGIES LIMITED

ex04_2012.ppt

PowerPoint プレゼンテーション

スライド 1

Transcription:

この資料は 情報工学レクチャーシリーズ松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために 名古屋工業大学松尾啓志 津邑公暁が作成しました 主記憶管理 ページング パワーポイント 7 で最終版として保存しているため 変更はできませんが 授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ 編集可能なバージョンをお渡しする事も可能です 復習 復習 主記憶管理 プログラムの実行には, ディスクから主記憶へのプログラムのロードが必要 マルチプログラミング環境では複数プロセスが並行して主記憶を使用 主記憶上でプログラムおよびデータを格納するための領域を管理する必要 記憶領域確保の方式 固定区画方式 可変区画方式 可変区画方式 空き領域の割り当て方式 ベストフィット ワーストフィット ファーストフィット 割当を適切に行わないと, プロセスが使用できない断片的な空き領域が多く発生 ( フラグメンテーション ) 空き領域の管理方式 リスト方式 ビットマップ方式

復習 静的ライブラリ リンク時にロードモジュールに埋込み ( 静的リンク ) 複数プログラムで使用されるライブラリがある場合, 主記憶領域の無駄 共有ライブラリ ロードモジュールはリンク情報のみを持ち, 実行時にリンク ( 動的リンク ) 複数プログラムで使用される場合でも, 各ライブラリは つのイメージだけ主記憶上に存在すればよい 主記憶領域 ( およびディスク領域 ) の有効活用 9. 主記憶の動的再配置 仮想化 主記憶の時間分割による多重化 有限のリソースを無限に見せる 空間分割 ハードウェアリソースを複数領域に区切る CPUでは不可能 時間分割 複数プログラムが交互に使う CPU タイムシェアリング 主記憶 オーバレイ 主記憶の動的再配置 オーバレイをより一般化した手法 主記憶に配置する対象 プログラム領域 現在実行中のプログラムカウンタの近傍 データ領域 最近アクセスした領域の近傍 それ以外は二次記憶装置 ( ハードディスク ) に

き領域 オーバーレイ 仮想記憶 キーワード } funca(); funca(){ funcb(); } funcb(){ funcc(); } ( 論理空間 ) main ret; funca ret; funcb ret; funcc ret; (物空理空 間)main(){ 仮想記憶 主記憶の動的再配置により, プロセスが使用できる主記憶領域を無限大にする 実際には, アドレスレジスタの有効ビット数を超えるアドレスにはアクセスできないし, ハードディスク容量にも依存するため, 厳密には無限大ではない 記憶容量に制限のない論理アドレス 仮想記憶実現のための操作 スワップイン 実行中のプログラムが, 必要となる領域を二次記憶から主記憶に転送する操作 スワップアウト 上記スワップインを行う際, その空き領域を確保するために, 当面必要としない領域を主記憶から二次記憶に転送する操作 主記憶 CPU 二次記憶 仮想記憶領域 ( スワップ, 仮想メモリ ) 9. ページング

ページング ページング 記憶領域の仮想化 空間の一部が物理メモリに存在 との対応付けが必要 物理メモリ上に存在する 仮想記憶の一部 は時々刻々変化する ( 動的再配置 ) 対応付けも時々刻々変化 ページング ページ と呼ばれる単位で動的再配置を行う x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 空間 4 5 6 7 8 9 ページ x xfff x xfff x xfff x xfff 空間 各空間のアドレスを上位 下位ビットに分割 上位ビット共通部分を単位ブロックとして扱う ページフレーム x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 空間 4 5 6 7 8 9 x xfff x xfff x xfff x xfff 空間 ページング x は x7456 x はに対応 x456 に対応 下位ビットは共通上位ビットの変換が必要 仮想 物理 7 ページテーブル からへの変換 ページ番号からページフレーム番号への変換 ページ V P C ページフレーム Virtual Memory flag Change 5 flag Permission flag

ページテーブル V フラグ (Virtual Memory flag) そのページが主記憶上に存在するか否かを示す P フラグ (Permission flag) そのページに対するアクセス条件を表す 例 ) 読み込み可, 書き込み可, など C フラグ (Change flag) スワップイン後, そのフレームに対して書き込みが行われたか ( 変更されたか ) 否かを示す ページフォルト割込 x xfff x xfff x xfff x xfff V 主記憶上に読み書き P C ページフレーム 可ない 4主記憶上 5 あり 未変更 6 7 8 スワップイン物理空間 ページングの動作 x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 4 5 6 7 8 9 ページングの動作 ページングの動作 7 456 456 4 5 6 7 8 x xfff x xfff x xfff x xfff V P C ページフレーム 主記憶上にない 物理空間 x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 4 5 6 7 8 9 4 5 6 7 8 x xfff x xfff x xfff x xfff 物理空間 7 5 V P C ページフレーム x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 4 5 6 7 8 9

789 789 4 5 6 7 8 x xfff x xfff x xfff x xfff スワップアウト物理空間 7 5 V P C ページフレーム ページングの動作 x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 4 5 6 7 8 9 46 46 4 5 6 7 8 x xfff x xfff x xfff x 物理空間スワップアウト 書込み 7 5 物理記憶上で行った変更が xfff xfff x4 仮想記憶でも有効に V P C ページフレーム x4fff x5 x5fff x6 x6fff x7 変更 x7fff x8 されている x8fff x9 x9fff ページングの動作 x xfff x xfff x xfff x 4 5 6 7 8 9 二次記憶に書戻し ページテーブル V フラグ (Virtual Memory flag) そのページが主記憶上に存在するか否かを示す の場合は既に主記憶上に存在するので, そのままアクセス可 の場合はスワップインが必要 C フラグ (Change flag) スワップイン後, そのフレームに対して書き込みが行われたか ( 変更されたか ) 否かを示す の場合は, スワップアウト時に二次記憶へのフレームの書き戻しが必要 Vフラグ V であるようなエントリが指定された場合 ページフォルト割り込みを発生 プログラムを停止 スワップ操作 必要であればスワップアウト スワップイン アクセス速度の違い 主記憶 -7 秒 二次記憶 - 秒 数千倍遅い スワップ操作は必要最低限におさえたい

Cフラグ 当該ページに対して書き込み ( 変更 ) があったか否かを示す 変更があった場合はもちろんスワップアウト時に二次記憶への書き戻しが必要 変更がなかった場合は, スワップアウト時の書き戻しをサボれる 転送コストの削減 Pフラグ ページごとにアクセス制御可能 読み出し可 不可 書き込み可 不可 実行可 不可 実行 ウィルスなどによる, 予期しないアドレスからの実行を防いだりできる 例 ) スタック領域は実行不可能に スタックは通常, プログラムを格納しない 復習 フラグメンテーション 空き領域の断片化 処理の進行に伴い, 小さな空き領域が増加空き領域が断片化 ( フラグメンテーション ) 主記憶全体の空き容量が十分でも, 新しいプロセスに連続した領域を割り当てられない 統計的には, 全領域数の約 / が無駄に ページングの場合 主記憶に割り当てられる領域は, ページ単位 全てのページが何らかのプロセスに割り当てられる 物理空間 割り当てられたが使用されない領域 ( 内部フラグメンテーション必要 ) 容量 ページが 4~8kB 程度なので, 主記憶の全容量からすると微々たる大きさ

ページングの問題点 9. ページングの問題点と解決策 ページテーブルの巨大さ 例 ) bit, ページ 8kB の場合ページエントリ数 5k 個 ( 約 5 万 ) ページテーブルはプロセス毎に独立例 ) プロセスの場合エントリ数 約 5 万 エントリ B で構成すると 5MB メモリアクセスの増大 ページテーブルは主記憶内に存在 回で 度の主記憶アクセスが必要 ページテーブルへのアクセス へのアクセス ページングの問題点と解決法 ハッシュ関数によるページテーブル ページテーブルの巨大さ ハッシュ関数によるページテーブル メモリアクセスの増大 連想レジスタ方式... のまえに

ハッシュ関数 ハッシュ関数 データを一定長のデータに要約するための関数 一種の圧縮 要約 するので, データの損失が起こる ( 不可逆変換 ) 例 ) 数値 x を 桁に要約するハッシュ関数 h(x) x % ; 94 69 84 7 97 85 h(x) 4 9 7 5 競合 ( コリジョン ) も起こる ある範囲 ( 定義域 ) のデータを, ある範囲 ( 値域 ) の値に要約する写像 定義域 < 値域 定義域 (x) y h(x) 値域 (y) ページングの問題点と解決法 ハッシュ関数によるテーブル ページテーブルの巨大さ ハッシュ関数によるページテーブル ページテーブルが大きくなる原因 ( 仮想記憶の大きさと同じエントリ数 ) ( 同時実行プロセス数 ) だけのエントリ数が必要 メモリアクセスの増大 連想レジスタ方式 ページテーブル内に格納されるフレームは V フラグが なら主記憶上のアドレスを指す V フラグが なら仮想記憶上 ( 二次記憶 ) のアドレスを指す

ハッシュ関数によるテーブル ハッシュ関数によるテーブル V なエントリの場合 ページフォルト スワップイン ( - 秒 ) ページテーブルを主記憶上に置いて高速アクセス ( -7 秒 ) 可能にしても, 結局は大きい処理時間がかかってしまう V なエントリを主記憶に置く必要はない 二次記憶上に置いても全体性能に大きな影響はない 6 46 46 ハッシュ関数 h(x) x % 4; x xfff x xfff x xfff x 6 共有されるから, このエントリが どのページ番号に関するデータを xfff 保持しているか記憶しておく必要がある flag ページ番号 ページフレーム 6 物理空間 ポインタ x xfff x xfff x xfff x xfff x4 x4fff x5 4 5 物理記憶と x5fff x6 同じサイズ 6 x6fff ( 小容量 x7 ) このエントリは 7, x7fff ハッシュ結果が x8 となる 6 8... x8fff などで共有される x9 9 x9fff ハッシュ関数によるテーブル ハッシュ関数によるテーブル 7 57 57 ハッシュ関数 h(x) x % 4; x xfff x xfff x xfff x xfff 次エントリへの 7 ポインタ 6 flag ページ番号ページフレーム 物理空間 6 ポインタ x xfff x スワップアウト xfff x xfff x xfff x4 x4fff x5 x5fff x6 4 5 ページ番号が一致しないこのエントリを使いたい6 x6fff が, 7x7 の情報を 潰してしまうのはマズいページフォルト 7 x7fff x8 8 x8fff x9 x9fff 9 57 57 ハッシュ関数 h(x) x % 4; x xfff x xfff x xfff x xfff flag ページ番号ページフレーム 7 6 物理空間 スワップアウト 6 7 ポインタ x xfff x xfff x xfff x xfff x4 x4fff x5 x5fff x6 x6fff x7 x7fff x8 x8fff x9 x9fff 4 5 6 7 8 9

ページテーブルの大きさ ハッシュ関数が持つべき条件 改良前 空間のフレーム数と同じエントリ数 ハッシュ関数によるページテーブル 空間のページフレーム数と同じエントリ数 変換結果の値域への均一分散 ハッシュ関数による変換結果の値が偏らない必要 変換結果が衝突することをコリジョンと呼ぶ 偏ると, 検索時にポインタをたどる確率が高くなり, オーバヘッド増大 変換の高速性 ハッシュ関数による変換は主記憶アクセスの度に発生 変換が低速であると, そもそも意味がない ページングの問題点と解決法 ページテーブルの参照 ページテーブルの巨大さ メモリアクセスの増大 ハッシュ関数によるページテーブル 連想レジスタ方式 7 46 46 主記憶 主記憶アクセスその 度のアクセスで 度も主記憶アクセス 主記憶アクセスその 4 5 6 7 8 x xfff x xfff x xfff x xfff 空間 7 5 V P C ページフレーム

連想レジスタ方式 連想レジスタ方式 7 46 46 主記憶 連想レジスタ ページ ページフレーム 7 5 主記憶アクセス 回 主記憶 最近使用したページの対応関係を保持 小容量 4 高速 5 6 7 8 x xfff x xfff x xfff x xfff 空間 7 5 V P C ページフレーム 今日のまとめ 連想レジスタ (TLB Translation Lookaside Buffer) 最近行われた変換結果を CPU 内で保持 小容量で高速 一般的にプログラムは, 一度アクセスしたアドレスを近いうちに再度アクセスする可能性が高い ことを利用 今日のまとめ ページング 主記憶の再配置システム の上位 ( ページ番号 ) をの上位 ( ページフレーム番号 ) に変換することでアドレス変換 フラグメンテーションも改善 ページテーブル 上記変換を行うためのテーブル ページに対応するエントリごとにフラグなどを配置 ページへのアクセス権などを設定可能 ページングの改善法 ハッシュ関数 ページテーブルの巨大さを緩和 空間に比例する大きさが必要だったのが, 空間に比例する大きさまで縮小 連想レジスタ 主記憶へのアクセス回数の緩和 最近使用した ページ番号 ページフレーム番号 の変換結果を CPU 内で記憶 ページテーブル検索のための主記憶アクセスを削減