Microsoft PowerPoint - os4.pptx

Transcription

1 Operating System 4 岩井将行 4/29

2 第 1 回 ハードウエアと OS CPUとデバイス 割り込み 記憶装置 ハードディスク装置 RAID パリティ ドとプセメリド空間 スレッドとプロセス メモリアドレス空間 ファイルシステム NIC ソケット カーネル

3 第 2 回 CUI タイピング, ログイン, コマンド操作, マニュアル, シェル ファイル操作, エディタ

4 第 3 回 プロセス, ジョブ プロセス管理プロセス管理 時分割処理とプロセス切り替え スケジューリング プロセス表

5 第 4 回 記憶装置 メモリ階層 キャッシュ アドレス空間 物理アドレスと論理アドレス ページング チェックポインティング 効率的な自動メモリ管理 GC フラッシュメモリ

6 第 5 回 シェルとアクセス権 標準入出力 フィルタコマンド シェルスクリプト ファイルのバックアップ アクセス権 ドライブ ディレク トリ ファイル open/read/write ファイルのメモリへのマッピング アクセス制御 権限 空き領域管理

7 第 6 回 ネットワークとOS ethernet,ping,socket,tcp/udp,rpc,apach,http,s sh,ftp,remotewindow 最新のOS 事情

8 試験 第 7 回

9 前回の復習

10 2 回目への ハードウエアと OS CPUとデバイス 割り込み 記憶装置 ハードディスク装置 RAID パリティ ドとプセメリド空間 スレッドとプロセス メモリアドレス空間 ファイルシステム NIC ソケット カーネル

11 第 3 回 プロセス, ジョブ プロセス管理プロセス管理 時分割処理とプロセス切り替え スケジューリング プロセス表

12 プログラムの処理形態 バッチ処理 必要な情報を前もって決定 実行してほしいジョブを一括依頼 対話 ( インタラクティブ ) 処理 そのつど プログラムに対して入力を行う

13 ジョブを一括して依頼 バッチ処理 ユーザは 必要なリソース 実行したいプログラム 処理に使うデータの全てをあらかじめ決定 それをJCL (Job Control Language) によって記述し コンピュータに投入 //JOB1 JOB (12345), CLASS=X //STEP1 EXEC PGM=TEST //DDIN DD DISP=SHR, DSN=INPUT1 //DDOUT DD DISP=(NEW, CATLG), DNS=OUTPUT(+1), // UNIT=SYSDA, SPACE=(CYL,(15,15),RLSE),DCB+*.DDIN : 各ジョブは 実行中は全てのリソースを占有する

14 待ち行列 バッチ処理 Job Job Job リソース (CPU, メモリなど ) 一定期間ごとに大量のデータを集めて処理するような場合に便利 例 ) 売り上げデータ 受注データの集計

15 バッチ処理 利点 スケジューリングが単純 前もって プログラムが必要とするリソースがわかるがわ 複数のジョブのスケジューリングが比較的楽例 ) 必要リソースの少ないジョブを優先的に実行すると全ジョブの平均待ち時間 ( ターンアラウンドタイム ) が短くなる ジョブの切り替えも少なくてすむため 無駄が少ない 欠点 欠点 前もって全てを決めないとジョブが投入できない

16 対話 ( インタラクティブ ) 処理 必要に応じて人間が入力し それを処理する 人間の反応速度は 10 1 秒程度 計算機は 10 9 秒オーダで命令を処理 人間の入力を待っている時間はすごく無駄特に昔 計算機が非常に高価だった時代はなおさら 一定時間に処理できる仕事量 ( スループット ) が低下 = もったいない タイムシアリングシステム (TSS) タイムシェアリングシステム (TSS) 使っていない CPU 時間を他に割り当てよう!

17 タイムシェアリングシステム 非常に短いCPU 時間を複数プロセスに順に割当 割り当てられる単位時間 ( クオンタム ) は数十 ms 割当が一周したらまた最初から プロセスから見ると... 細切れの CPU 使用権 ( 時間 ) が 短い間隔を置きながら与えられる プロセスは入力待ちなどの遊びも多いので この 短い間隔 はユーザからは見えにくく さもCPUを占有して使っているように見える

18 タイムシェアリングシステム 利点 自分のほかに大きなプロセスがあっても そのプロセスが終わるまで長い間待たされたりしない ( バッチ処理ではありうる) ユーザから見てもザから見ても 対話的に入力してからその反応が返ってくるまでの時間 ( レスポンスタイム ) が短くなる

19 バッチ処理と対話処理 バッチ処理 対話処理 スパコンメインフレームパソコン 銀行の勘定系 企業の基幹 計算速度最優先 バッチと 1 ほとんどが対話処理つのジョブ自体も大きい TSS レスポンスタイム最優先が共存 レスポンスタイム重視で 対話処理を優先 オーバヘッドが少ないバッチ処理

20 リアルタイム処理は実はとても難しい ある決められた時間に必ず処理を終わらせる 例 ) 自動車の安全装置 他のプロセスにリソースが使われてスが使われていたので間に合いませんでした では済まない! クオンタムの短い TSS でも間に合わない可能性 どうやったら実現できるか = 非常に複雑 同時実行プロセス数に制限 記憶領域の使用制限 etc, etc... しかも処理速度を落としてはいけない

21 プロセスとは プロセス リソースの割当対象となる ( 仕事の ) 単位 OSに対してリソースを要求 OSからリソースの割当を受ける

22 プロセス ( プログラム ) とプロセッサ ユニプロセッサ ユニプログラミング ひとつの CPU に対してひとつのプロセス バッチ処理プロセス ユニプロセッサ マルチプログラミング ひとつの CPU に対して複数のプロセス TSS マルチプロセッサ マルチプログラミングマルチプログラミング 複数のCPUに対して複数のプロセス 並列 分散処理密結合 (tightly coupled) バスレベルで結合された複数の CPU を持つ 疎結合 (loosely coupled) プロセスプロセス 疎結合マルチプロセッサシステム ( コンピュータ クラスターとも呼ばれるプロセス ) プロセスは複数の独立したコンピュータを高速な通信システム ( たとえばギガビット イーサネットなど ) で結合したもの

23 Condor supercomputer with 1,760 ps3s tech/what the dodsplaystation powered condor cluster means for the future of p supercomputing/5720

24 マルチコア マルチスレッドスレッドプログラミング

25 GPU The GeForce GTX 560 Ti 448 Core's GPU has two disabled SMs Open cl, CUDA

26 プロセスの切り替え 複数プロセスを切替えながら実行 プロセス A プロセスB 記憶領域の圧迫 プロセス C 記憶領域の不足 置き換えコスト プロセスA また不足 また置き換え メモリ ( 主記憶 ) C A B

27 プロセスとスレッド 複数プロセスの同時実行はコストが高い メモリ使用量が増加 切り替えコストも大きい 複数 CPU を備えた計算機の一般化 デュアルプロセッサ, デュアルコア 同時実行できるプロセス数よりCPUが多いと CPU が遊んでいてもったいない スレッドッド プロセスをさらに小さい単位に分割 CPU リソースをスレッドごとに割当

28 スレッド (thread) 軽量プロセス (lightweight processes:lwp) 1 つの保護の単位としてのプロセス ( タスク あるいは アドレス空間 ) 内部にふくまれている論理的な並列処理の単位

29 スレッド 例 )Microsoft f Office プロセス Microsoft Word Microsoft Excel 各プログラムはプロセスとして処理 スレッド たとえば Word の場合 印刷 編集 など 同じ Word というプログラムの中で 同時 ( 並行 ) 動作できる単位がある!

30 スレッドの内容 スレッドごとに持つもの プログラムカウンタ スタック レジスタ プロセス全体で共有するもの アドレス空間 メモリ ファイル記述子 UID ( アクセス制御 )

31 スレッドの生成 逐次処理 ( スレッド / プロセスが 1つ ) の状態から始まる 並列性が必要になった時 fork 命令で複数のスレッド / プロセスに分かれて並列処理を行う 並列に動作できる部分が終ると join 命令で再び逐次処理に戻る

32 リソース割当 スレッド プロセス単位 メモリ, 入出力デバイス,etc... スレッド単位 CPU スレッド TSS による切り替えオーバヘッドが軽い 同一プロセスから生成されてるからメモリ領域が同じ メモリ使用量は 1 プロセス分ですむ メモリ使用量は 1 プロセス分ですむ 別名 :Light Weight Process ( 軽いプロセス )

33 プロセス プロセス = 実行中のプログラム アドレス空間 ( コアイメージ ) 実行可能プログラム データ スタック プロセス表 レジスタや実行に必要なほかの情報 プロセスにおける木構造 シグナル タイマ終了などの通知 プロセス間通信

34 プロセスの概要 実行中のプログラム プログラム カウンタ レジスタ 変数を含むタ 変数を含む プロセスのメモリ イメージ stack stack segment: ローカル変数 サブルーチンの戻り番地等 ( 低アドレスへ ) data data segment: データ ( グローバル変数 ) ( 高アドレスへ ) 0x text text segment: 命令の列

35 マルチプログラミング コンピュータ上では複数のプロセスが実行されている 1つのCPUは一度に1つのプロセスのみ実行される 複数のプロセスが並列実行されているようにみせかける ( 疑似並列 :pseudoparallelism) マルチプログラミンググ 実行するプロセスを高速に切り替える ( スケジューリン実行すを高速切り替 ( ケリグ )

36 プロセスの状態 プロセスの3つの状態 実行中 (running) CPU が割り当てられている状態 実行可能状態 (ready) 実行可能だが ほかのプロセスが実行中のため 一時的に待機している状態 待ち状態 (block) 外部イベントが発生するまで実行不可能な状態

37 マルチプログラミング プロセッサは常に 1 つのプログラムしか実行できない マルチタスクでは, 複数のプログラムを切り替えて実行しなければならない プリエンプティブ方式は,OSがプロセッサの実行権限を管理し, プロセスの実行を切り替える方式である 現在のOSは, プリエンプティブ方式が主流だ ノンプリエンプティブ方式 ( 擬似マルチタスク方式 ) は, プロセスの切り替えをプログラム自身に任せる方式 ただし, ノンプリエンプティブ方式では, あるプログラムがプロセッサを長時間占有することも可能で, この場合はシングルタスクと同じになってしまう 昔のMac OS やWindows 3.1 は, ノンプリエンプティブ方式 ンプテ

38 プロセスの 3 状態遷移 1. プロセスが ( 例えば ) 入力待ちでブロック状態へ 2. スケジューラが別のプロセスを選択する 3. スケジューラがこのプロセスを選択する 4. 入力データが準備できた running 実行中 待ち 実行可能 block 4 ready

39 スケジューラ ready 状態にあるプロセス群から どのプロセスにCPUを割り当てrunning 状態にするかを決定する機能 軽いプロセス アドレス空間共有 スレッド スレッド毎に プログラムカウンタ レジスタ管理 スタック PSW( 状態 )

40 CPU の仮想化 プロセスの切り替え OSがプロセス スレッドに対して CPU の実行権を微小時間与える 割込み 通常の CPU 演算動作とは異なる事象のこと キーボード入力を受け取った 自動車がどこかに衝突した サーバからデータが送られてきた 割込み発生時にプロセスの切り替えが起こる TSS では プロセス切り替えのためにインターバルタイマーが定期的に割込みを発生

41 割込み 割込み処理 割込みは 即座に処理すべき場合が多い 高速かつ軽量に割込みを処理する実行方式

42 内部割込み 割込みの種類 実行中のプログラムを発生原因とする 例 ) プログラム自体が他の処理を要求プログラム自体の異常 外部割込み その他の要因で発生する 例 ) 他の優先的処理からの要求順番待ちしていた他の処理への移行ハードウェア異常特殊な処理

43 割込みの種類 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

44 割込みの種類 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

45 内部割込み : スーパバイザコール割込み ユーザモード アプリケーションには許されていない処理がある プロセスの切り替え 入出力デバイスへのアクセス etc.. スーパバイザモード そこでアプリケーションは OS に対して処理を依頼 OS の権限で, 処理を実行してもらう パバイザ スーパバイザコール アプリケーションが OS に処理を依頼すること

46 スーパバイザコール割込み スーパバイザコール このとき割込みが発生 CPU の実行モードが切り替わる スーパバイザコール CPU の実行モードユーザ スーパバイザモード OS を実行するモード スーパバイザモード CPU 内の全てのリソースを利用可能 ユーザモード アプリケーションを実行するモード 利用できるリソースに制限あり 割込みによる移行 モード

47 割込みの種類 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

48 内部割込み : プログラムチェック ( 例外 ) 割込み 実行中のプログラムで異常が発生したとき ゼロによる除算 division by zero 演算時のオーバフロー integer overflow 不正なメモリアドレスへのアクセス segmentation violation この割込みを検知するしくみがないと... 上記の異常が発生したときにシステム全体が停止してしまうかも...

49 割込みの種類 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

50 外部割込み : 入出力割込み 入出力装置から発生する割込み スーパバイザコールにより入力受付開始 ( スーパバイザコール割込み ) 入力が終了したことを知らせる ( 入出力割込み )

51 割込みの種類 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

52 外部割込み : タイマ割込み インターバルタイマによる割込み TSS では, 定期的な切り替えが必要 インターバルタイマが定期的に割込みを発生させることで これを実現 インターバルタイマ プロセス A プロセス B プロセス C

53 割込みの種類 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

54 外部割込み : マシンチェック割込み ハードウェアによって通知される異常時に発生する割り込み 冷却装置の異常 内部の温度が上がりすぎているのを検出 電源装置の異常 etc...

55 外部割込み : リスタート割込み システムをリセットするときに発生する割込み

56 割込みの種類 : まとめ 内部割込み スーパバイザコール割込み プログラムチェック ( 例外 ) 割込み 外部割込み 入出力割込み タイマ割込み マシンチェック割込み リスタート割込み

57 割込みによる プロセスの中断と再開

58 割込み発生時の処理 実行中のプロセスを中断 割込み処理ルーチンに移行 割込み処理が終わったら プロセスを再開

59 プロセスの中断 PSW(Program ( Status Word) プロセスは 後で再開しないといけない 再開するためには 今の途中状態を覚えておかない といけない 状態 : プログラムカウンタの値 スタックレジスタの値 汎用レジスタの値 割込みマスクの値 etc...

60 プロセスの中断 PCB (Process Control Block) メモリ上の PSW を退避するための領域 メモリ ( 主記憶 ) 割込み どこまで処理したか 今処理しようとしてたことは何か PSW どこから再開したらよいか PCB

61 割込み処理ルーチンの仕事 番地 割込みの種類を判別する必要 0x0100 種類に応じて処理を実行ディスク 割込みベクタ 割込みの種類に対応する数字 (ID) 割り込みベクタテーブル 0x0500 メモリ ( 主記憶 ) 割込処理 キーボード割込処理 0 0x0580 0x0580 ネットワーク 1 0x 割込処理 2 : 0x0500 :

62 プロセスの再開 実行可能なプロセスからプロセスを選択 割込によって中断されたプロセスが常に再開されるわけではない 選択されたプロセスの PSWからCPU 状態を復元して再開 メモリ ( 主記憶 ) プロセスAのPSW プロセスBのPSW プロセスCのPSW

63 プロセスの中断と再開 : まとめ 中断 CPU 状態をPSWという形で メモリ内の PCB へ保存 割込ルーチン 割込ベクタ ( 割込の種類を示す値 ) を放送 その値を割込ベクタテーブルでひいて 割込に対応するルーチンの主記憶アドレスを取得 ルーチン実行 再開 実行可能プロセスからスケジューラが 1 つ選択 対応する PSW から CPU 状態を復元

64 プロセスの三状態

65 プロセスの状態 実行可能なプロセス とは? プロセスの状態 yes 実行中? no 実行 yes CPU が空き次第実行できる? no 実行可能 待ち

66 プロセスの状態 実行状態 (running) プロセスを実行している状態 リソースは, そのプロセスのために確保されている 実行可能状態 (ready) 実行できるが CPU リソースが確保できていない状態 CPU リソースを確保した時点で実行開始される 待ち状態 (wait) CPU 以外のリソースも確保できていない状態 入力待ちなどもこれに含まれる

67 状態遷移 CPU 以外のリソースを獲得 or スーパバイザコール終了 実行可能 (ready) CPUリソースが割り当てられた ( 順番がまわってきた ) 割込み 待ち (wait) 実行 (running) スーパバイザコールスパバイザコル or CPU 以外のリソース喪失

68 状態遷移 入出力完了までの時間が実行可能 CPU 速度に比べて圧倒的に遅いため (ready) 人間の反応速度 : 10-1 秒 CPUの動作速度 : 10-9 秒 待ち (wait) 実行 (running) スーパバイザコール

69 CPUの仮想化

70 エミュレーション 最近は... ハードウェアが非常に高速化 他のハードウェア資源全体 ( システム ) を仮想化することも可能になってきた エミュレーション ハードウェア環境をソフトウェアで仮想化 計算機上で他の計算機環境を仮想的に提供機

71 ハードウェアエミュレーション 計算機の構造そのものを仮想化 VMware IBM/PC 環境の OS (Solaris, Linux, Windows) 上に仮想的な IBM/PC 環境を構築 Linux 仮想計算機 Windows

72 オペレーティングシステム 第 4 回 メモリとメモリ管理

73 RAM(Random Access Memory) RAMは 通電中でもデータを読み書き可能で 電源を切ると記憶内容が失われる揮発性の半導体メモリー SRAM(Static RAM; スタティックラム ) DRAM(Dynamic RAM; ダイナミックラム )

74 SRAM SRAMはフィリップフロップ回路で構成された利用した半導体メモリーでで DRAMはコンデンサーを利用した半導体メモリー フリップフロップ回路は 自己保持回路ともいわれる 論理回路で構成される コンデンサーは電気を蓄えておく部品のことである SRAM は フィリップフロップ回路で構成され DRAM はコンデンサーで構成されるということを覚えて欲しい

75 SRAM 論理回路ではなく コンデンサ ( キャパシタとも言われる ) の充電状態を使用した記憶方式である DRAM と比較した場合 コンデンサの自然放電によるデータ消失を防ぐための定期的なリフレッシュ動作 ( 再書き込み ) を与える必要がない 記憶領域へのシンプルかつ高速なアクセスが可能で ある ただし 1bitあたりのトランジスタ数やその配線が DRAM と比べ複雑になるため bit あたりのコストは高くなる 比較的小容量であっても高速性が求められる揮発性 RAM 領域 (CPUのレジスタや キャッシュメモリ )

76 DRAM Dynamic Random Access Memory リフレッシュ ( 記憶保持動作 ) を必要とするダイナミックメモリ キャパシタ ( コンデンサ ) に電荷を蓄えることにより情報を記憶し 電源供給が無くなると記憶情報も失われる揮発性メモリ 長期記録の用途には向かず 情報処理過程の一時的な作業記憶の用途に用いられる DDR3 SDRAM Double Data Rate3 Synchronous Dynamic Random Access Memory DDRでの同期クロックを4 倍に高めそれぞれの立ち上がりと立ち下り時にデータ入出力を確定するのでSDRに比べて8 倍のデータ転送速度となる 動作周波数は800MHz 1066MHz 1333MHzの3 種類 ノート向け S.O. DIMM(small outline dual in line memory module) so/

77 記憶容量 アクセス速度 リフレッシュ 価格用途回路 DRAM 大きい遅い必要安い主記憶コンデンサー キャッ SRAM 小さい 速い 不要 高い シュメモ リ フィリップフロップ

78 メモリ実効速度 実効速度 =( キャッシュメモリの速度 ヒット率 )+ ( 主記憶の速度 (1-ヒット率 )) ヒット率は CPUが必要とするデータがキャッシュメモリー上に存在する確率 NFP は CPUが必要とするデータがキャッシュメモリー上に存在しない確率である ヒット率 +NFP(not found probability)=1

79 メモリ実効速度問題 あるプロセッサが主記憶装置及びキャッシュメモリにアクセスするとき, それぞれのアクセス時間は60ナノ秒及び10ナノ秒である アクセスするデータがキャッシュメモリに存在する確率が 80% の場合, このプロセッサの平均アクセス時間は何ナノ秒か 10ns*0.8+60ns*(1 0.8)=8ns+12ns=20ns

80 演習問題 主記憶のアクセス時間 60ナノ秒, キャッシュメモリのアクセス時間 10ナノ秒のシステムがある キャッシュメモリを介して主記憶にアクセスする場合の実効アクセス時間が 15 ナノ秒であるとき, キャッシュメモリのヒット率は幾らか ア 0.1 イ 0.17 ウ 0.83 エ 0.9

81 メモリ管理

82 メモリ管理 メモリ マネージャ メモリのどの部分が使用中でどの部分がフリーか プロセスが要求するメモリを割り当て 使用後に解放 メインメモリとディスク間のスワッピングの管理 メモリ管理システム スワッピング ページングを使用しない方式 スワッピング ページングを使用する方式

83 スワッピング ページングなし ( マルチプログラミング ) 再配置 (relocation の問題 ) バイナリファイル 100 番地 0 番地 メモリに配置 100K 100K+100 番地 保護 (protection) の問題 0 ユーザ 2 のプログラム アクセス ユーザ 1 のプログラム

84 再配置と保護の問題の解決策 ベースレジスタとリミットレジスタを使用ジタを使 プログラムロード時にパーティションの先頭がベースレジスタへ パーティションの終わりがリミットレジスタへセットされるッ リミットレジスタベースレジスタ 300K 100K CALL K( ベースレジスタの値 ) に自動的に変換し かつ リミットレジスタもチェック

85 スワッピング 例 プロセス全体を一時的にディスクに退避 C C C C C B B B B E A A A D D D OS OS OS OS OS OS OS A がスワップアウト 時間

86 スワップ領域の割り当て スワップ領域 メインメモリに入りきらないものを退避させるための ディスク上の領域 スワップ領域割り当てのアルゴリズム メインメモリ管理と同様のアルゴリズム スワップアウトごとに割り当てる と異なるアルゴリズム プロセス生成時に割り当てる

87 仮想記憶 (Virtual Memory) プログラムサイズ > メインメモリサイズ オーバーレイ (overlay) というプログラム細分化 overlay0を最初に実行し 終了すると 次のoverlayを呼び出す 細分化するのはプログラマの仕事 仮想記憶の登場 プログラムサイズがメモリサイズを超えても構わないという点が発想の基本

88 ページング 仮想アドレス 仮想アドレス空間ド プログラムから見えるアドレスおよびアドレス空間 MMU( メモリ管理ユニット :Memory Management Unit) 仮想アドレスと物理メモリ アドレスとのマッピングを行うチップ 仮想アドレス CPU MMU メモリ ディスク コントローラ 物理アドレス バス

89 MMU の動作 ページとページ フレームのマップを示すページ表から物理アドレスを提供する 仮想アドレス ページ番号 プレゼント / アブセント ビット ( マップされているか否か ) オフセット 物理アドレス

90 ページフォールト (page fault) ページ フレームにマップされていないページをアクセスしようとすること CPU は OS にトラップをかける OS はあるアルゴリズムに従って選んだページ フレームをスワップアウト ( ディスクに退避 ) する ペジフルトを起こしたペジの内容を退避 ページ フォールトを起こしたページの内容を退避させたページ フレーム部にロードする

91 ページ表 (page table) 目的は 仮想ページをページ フレームにマッピングすること 問題点 ページ表が極端に大きくなる ページサイズ4K 32ビット アドレス空間の場合 100 万ページ ページ表はプロセスごとに保持 マッピングは高速である必要がある 1 命令に数回のメモリアクセスが必要な場合もある 改良案として マルチレベルページ表

92 ページ表エントリ ページ フレーム番号 プレゼント / アブセント保護修正参照キャッシング抑制 ページ フレーム番号 プレゼント / アブセント ビット 1: 物理メモリ上にある 0: 物理メモリ上にない 保護ビット 読み取り 書き込み 実行のアクセス権限を示す 修正ビット ページが編集されると 1 参照ビット ページが参照されると 1 キャッシング抑制ビット デバイス レジスタにマップされているページ用

93 ページ置換アルゴリズム ページフォルト発生時 OSは物理メモリから削除するページを選択しなければならない 削除するページが編集されていれば ディスクに書き戻す 最適ページ置換アルゴリズム もっとも次の参照までの時間が長いものを選択する 実現不可能 現実的かつ有用なアルゴリズムが必要

94 今LRU 後アク(未知スさに基づく考え方る確率)時間的局所性セれ時間的局所性 過去のアクセス間隔 ( 既知 ) アクセス確率の低いページを選びたい アクセス間隔の長いページを選べばよい LRU Least Recently Used

95 LRU アルゴリズム (1/3) LRU(Least Recent Used) 長い間使用されていないページは 今後も参照されない可能性が高い という考えに基づく ページフォルト発生時 最も長時間参照されていないものを選択 実現可能な方法は ハードウェア依存 ソフトウェアでは 近似解を使用

96 LRU アルゴリズム (2/3) 64 ビットのカウンタ C を利用 各命令後 インクリメントン ページ表のエントリにCを格納できるフィールドを用意 ページを参照した時点で 現在の C の値をそのページエントリに格納する ページエントリのカウンタの値が最小のもの ページエントリのカウンタの値が最小のものが LRU ページ

97 LRU アルゴリズム (3/3)

98 お断り 本授業資料の作成にあたり 慶應大学 SFC IPL/ITB 岩井クラス 戸辺義人先生 田浦健次朗先生 降旗大介先生 松尾啓志先生 Wikipediaなどの資料を参考にさせていただいています ありがとうございます