４章　メモリ管理

４．メモリ管理 概論 TLBコヒーレンス制御 高速化技法 メモリコンシステンシモデル 分散共有メモリシステム ページを基盤としたシステム 共有変数を基盤としたシステム ＮＵＭＡマルチプロセッサにおけるメモリ管理 キャッシュおよびＤＳＭとの相違 検討課題 ソフトウェア技術 実現例

４．メモリ管理：概論 検討課題 ＵＭＡアーキテクチャ ＮＵＭＡアーキテクチャ ＮＯＲＭＡアーキテクチャ メモリアクセスの高速化 キャッシング技法 コヒーレンス制御 ページ表：ＴＬＢ コード／データ ＮＵＭＡアーキテクチャ メモリアクセスの不均一性を考慮 ローカル／リモートメモリ ＮＯＲＭＡアーキテクチャ

ＴＬＢコヒーレンス制御 ＴＬＢコヒーレンス問題 データのキャッシング データ： 仮想 → 実アドレスのマッピング情報 データ：　仮想　→　実アドレスのマッピング情報 オリジナル（キャッシング元）：　ページ表 キャッシング先：ＴＬＢ（Translation Lookaside Buffer）

プロセッサ０ プロセッサ１ ＴＬＢ ＴＬＢ メモリ 図４．１ ＴＬＢコヒーレンス タスクＡの論理アドレス空間 スレッド スレッド ページ フレーム 2 スレッド ページ フレーム 2 ＴＬＢ ＴＬＢ ①ページ９をフレーム２にマッピング タスクＡの論理アドレス空間 ページフレーム２ ページフレーム１ ページフレーム０ ②間違ったアクセス ページ９ ページ１ ページ０ 変更後 の対応 変更前 の対応 メモリ 図４．１　ＴＬＢコヒーレンス

ＴＬＢコヒーレンス問題：考慮すべき問題点 ハードウェアアーキテクチャ ページ表　→　ＴＬＢへのローディング ＴＬＢ　→　ページ表への書き込み ハードウェアが行っているか否か？ コヒーレンスを保証する範囲 強いコヒーレンス保証 処理中でもコヒーレンスを保証 弱いコヒーレンス保証 処理完了後のコヒーレンスを保証 処理中のコヒーレンスは保証していない．

ＴＬＢコヒーレンス制御 ページ情報変更の分類 （１）安全な変更(safe change) （２）危険な変更(unsafe change) 変更が生じても，すぐに対処する必要がない変更 後で，ＯＳで対処できる． 例 ページ保護レベルが上がる（緩和）場合 Read-only 　→　 read-write メモリへページがロードされる場合 Invalid → valid （２）危険な変更(unsafe change) 変更が生じたら，すぐにコヒーレンスを保つ必要がある変更 ページ保護レベルが下がる場合 Read-write　→ read-only ページがページアウトされる場合 Valid 　→ invalid

ＴＬＢコヒーレンスアルゴリズム シュートダウン（TLB shootdown）アルゴリズム 修正シュートダウン（modified shootdown）アルゴリズム Read-locked TLBs Validation

シュートダウンアルゴリズム（１／４） プロセッサ０ プロセッサ１，２ ①準備を依頼 イニシエータ レスポンダ ②準備ＯＫ ③ページ表を変更 メモリ ページ表 図４．４　シュートダウンアルゴリズム概要

図４．５ シュートダウンアルゴリズム イニシエータ レスポンダ ・割込み禁止 ・active[self]:=0 ・ページ表のロック ・レスポンダにＴＬＢ無効化を通知（メッセージのキューイング） ・レスポンダに割り込み通知 ・自ＴＬＢの無効化 全レスポンダrがactive[r] = 0　になるまで繁忙待機（ロック変数上） ページ表変更 ページ表のアンロック 割込みレベルを元に戻す ・割込み ・割込み禁止 ・active[self]:=0 ページ表がアンロックされるまで繁忙待機（ロック変数上） ・無効化通知をキューから削除 ・自ＴＬＢの無効化 ・active[self] := 1 ; ・割込みレベルを元に戻す ・割込み ・割込み禁止 ・active[self]:=0 ページ表がアンロックされるまで繁忙待機（ロック変数上） ・無効化通知をキューから削除 ・自ＴＬＢの無効化 ・active[self] := 1 ; ・割込みレベルを元に戻す 図４．５　シュートダウンアルゴリズム

シュートダウンアルゴリズム（２／４） 利点 欠点 完全なコヒーレンスを保証 イニシエータが起動中のコヒーレンスを保証（レスポンダをアイドルにする） 欠点 同期のオーバヘッド大 イニシエータ：　全レスポンダのアイドル確認後，ページ表エントリを変更 レスポンダ　→　イニシエータの処理時間が増大 レスポンダ：　ページ表変更（イニシエータ）完了まで，繁忙待機 プロセッサ間通信（割込み）レベルが低いハードウェア上では，割込み受信が遅れる．

シュートダウンアルゴリズム（３／４） シュートダウンアルゴリズムがサポートするマシンの特徴 プロセッサ シュートダウンアルゴリズムがサポートするマシンの特徴 ＴＬＢエントリからＰＴＥへの書込みがハードウェアで行われる． （例）ＰＴＥ内の参照ビット設定の時 ＰＴＥ全体を対応するＴＬＢエントリで上書きする． ＴＬＢ MPU エントリ ヒット 上書き （ハードウェア） メモリ 　　　　　　参照ビット エントリ ページ表 図４．２　ハードウェアによるページ表の上書き

シュートダウンアルゴリズム（４／４） シュートダウンアルゴリズムの必要性 直観的方法 シュートダウン：　全レスポンダをアイドルにした後，ＰＴＥを変更． 直観的方法 イニシエータのＰＴＥ変更後，レスポンダがＴＬＢを無効化 イニシエータ レスポンダ （プロセッサ間割込み） ＴＬＢの無効化要求 ＰＴＥを変更 自エントリを無効化 応答待ち 自エントリを無効化

図 直観的方法の例（ページ５をread-writeからへread-only） イニシエータ レスポンダ ページ 番号 ページ 番号 保護属性 保護属性 タスクＡの スレッド１ タスクＡの スレッド１ 5 r/w 5 r/w ②ヒット ＴＬＢ ＴＬＢ ③上書き ①変更　ｒ／ｗ　→　ｒ 5 　　　　保護属性 ページ 番号 タスクＡのページ表 ページ表の保護属性 ① ｒ／ｗ　→　　ｒ ③　ｒ　→　　ｗ （元に戻る） 図　直観的方法の例（ページ５をread-writeからへread-only）

修正シュートダウン（modfied shootdown）（１／３） RP3上のMachで採用 RP3の特徴（TLBコヒーレンス制御の観点） ページ表の変更は，ハードウェアで暗黙的には行わない． ソフトウェアで行う． TLBミスヒット時のページ表からのローディング ページ参照ビットの設定 修正シュートダウンアルゴリズムの特徴 同期のオーバヘッドを軽減 イニシエータ：　全レスポンダからの応答を待つだけ レスポンダ：　自TLBの無効化後，直ちに走れる．

図４．６ 修正シュートダウンアルゴリズム イニシエータ レスポンダ ・ページ表のロック ・ページ表変更 ・レスポンダにＴＬＢ無効化を通知（メッセージのキューイング） ・各レスポンダについてtmp]r]:=Fetch&Add(request[r], 1) ・レスポンダに割込み通知 ・自ＴＬＢの無効化 全レスポンダrが update[r] > tmp[r]　になるまで繁忙待機 ・無効化要求の削除 ・ページ表のアンロック ・割込み ・割込み禁止 ・t := reqests[self]: ・無効化要求の検索 ・自ＴＬＢの無効化 ・updates[self] := t ; ・割込みレベルを元に戻す ・割込み ・割込み禁止 ・t := reqests[self]: ・無効化要求の検索 ・自ＴＬＢの無効化 ・updates[self] := t ; ・割込みレベルを元に戻す 図４．６　修正シュートダウンアルゴリズム

修正シュートダウン（modfied shootdown）（２／３） 修正シュートダウンアルゴリズムが保証する範囲 イニシエータの処理完了後のコヒーレンスを保証 イニシエータの処理途中では，コヒーレンスを保証していない． イニシエータ レスポンダ ←　当該ＴＬＢエントリへアクセス 　　　（古い情報へアクセス） ＰＴＥを変更　　→

修正シュートダウン（modfied shootdown）（３／３） 「危険な変更」でもほとんどの場合，問題なし ページアウトする場合 Valid/invalidビット： valid 　→　 invalid 処理 ①ＴＬＢコヒーレンス処理 　　　　　　↓ ②実際にページを追い出す． イニシエータ レスポンダ ←　当該ＴＬＢエントリへアクセス 　　　（validなのでメモリへアクセス） 当該ページはまだメモリにある． ＰＴＥを変更　　→ valid 　→ invalid 処理完了 ページを追い出す．

高速化技法 技法の分類 処理の軽減 アクセス時間の高速化 アクセス時間の隠蔽 先行評価（eager evaluation） 予め処理しておく． プリフェッチ 予測が必要 遅延評価（lazy evaluation） 処理が本当に必要になったときに行う． コピーオンリファレンス，コピーオンライト アクセス時間の高速化 キャッシング技法 アクセス時間の隠蔽 アクセス処理のパイプライン化 マルチスレッドアーキテクチャ

高速化技法：コピーオンリファレンス Copy-on-reference アクセス（参照，リファレンス）が生じた時に実際にコード／データを移動させる． NORMAまたは分散システムのプロセス移送に適用 Accentカーネル（Mach OSの元になった）で適用

高速化技法：コピーオンライト Copy-on-write 使用する状況 UNIXの場合 Mach OSのメッセージ通信機構にも多用 オリジナルのオブジェクトからオブジェクトを生成 その後，上記２つのオブジェクトが独立（すなわち，共有なし）に動作． UNIXの場合 Forkシステムコールで子プロセスを生成 図４．７参照 Mach OSのメッセージ通信機構にも多用

図４．７ コピーオンライトを用いた仮想アドレス空間のコピー 親プロセス 仮想アドレス空間 子プロセス 仮想アドレス空間 メモリ スタックＰ データＰ テキスト スタックＣ スタックＰ データＣ データＰ テキスト スタックＣ データＣ テキスト (2)コピー (1)作成 ページ表 ページ表 (2)コピー 親プロセス （１）コピーオンライトを行わない場合 親プロセス 仮想アドレス空間 子プロセス 仮想アドレス空間 メモリ スタックＰ データＰ テキスト スタックＣ スタックＰ データＣ データＰ テキスト スタックＣ データＣ テキスト (1)fork (2)作成 ページ表 R/W (3) (7) R/W→R→R/W R ページ表 R/W (7) R→R/W R (5)ページ フォールト (4)書込み アクセス (6)コピー (7)変更 保護ビット 保護ビット （１）コピーオンライトを行なう場合 図４．７　コピーオンライトを用いた仮想アドレス空間のコピー

高速化技法：マップオンリファレンス メモリマップ要求時ではなく，実際に参照された時点で処理 適用例 メモリマップドファイル メモリマップドＩ／Ｏ

分散共有メモリ（ＤＳＭ：Distributed Shared Memory） 分散共有メモリ（ＤＳＭ）とは？ 物理的に分散されているメモリを，ユーザには共有メモリにみせる仕掛け 図４．１３ 実現レベル ハードウェア：ＮＵＭＡ ソフトウェア 対象：ＮＯＲＭＡ，分散システム IVY, Shiva, Munin, Midway, ThreadMarks ユーザ 共有メモリ メモリ MPU1 ノード１ メモリ MPU2 ノード2 メモリ MPUN ノードN ・・・ 図４．１３　ＤＳＭの概念

ＤＳＭ：設計時に考慮すべきこと（１／２） 管理対象の粒度 ユーザへの共有空間は，分割（ＤＳＭブロック）されて各ノードに配置 初期は，ページ単位 ＤＳＭブロックサイズは大 利点：管理対象数（ＤＳＭブロック数）が小さくなる． 欠点：フォールシャエアリング（false sharing）の可能性が大きくなる． False sharing：図４．１４ ＤＳＭブロックサイズが小 上記と逆

a C C b a, b, c a, b, c ノード１ ノード２ メモリ メモリ ＭＰＵ１ ＭＰＵ２ プロセス１ プロセス２ コヒーレンス制御 （１）異なるブロックへの割当て ノード１ ノード２ メモリ メモリ ブロック ブロック ピンポン現象 a, b, c a, b, c ＭＰＵ１ ＭＰＵ２ プロセス１ プロセス２ コヒーレンス制御 （２）同一ブロックへの割当て（フォールスシェアリング） 図４．１４　フォールスシェアリング

ＤＳＭ：設計時に考慮すべきこと（２／２） メモリコンシステンシモデル スケーラビリティ 非均一性（heterogeneity） 性能と使いやすさのトレードオフ Strict consistency model ユーザが慣れ親しんだモデル 各ノードでのステップごとの同期が必要． スケーラビリティ ノード数が増えても，性能低下させない． 非均一性（heterogeneity） ノードの非均質にも対処 例 データの表現方法が異なる場合は，データ変換が必要．

ＤＳＭ：実現時に考慮すべきこと（１／３） 実現レベル 書込みアクセス検出機構 カーネル空間 ユーザ空間 利点：メモリハードウェアの提供機構をフルに活用できる． 欠点：多大な労力 ユーザ空間 上記と逆 実現がＯＳに依存：　何をユーザ空間に提供しているか？ 書込みアクセス検出機構 コヒーレンス制御のために，書込みをソフトウェアに通知する機構が必要 a)ハードウェアサポートを利用する方法 アクセス保護違反を利用 ページ属性をリードオンリに設定 ページフォールトを捕まえる． 利点 コンパイラを修正する必要なし． 欠点 ＤＳＭブロックがページと大きい． フォールスシェアリングが生じる可能性が大 システムコールを用いる回数が多くなる． b)ソフトウェアによる方法 書込みアクセスコードの直後に，コヒーレンス制御ルーチンを呼び出す． 利点，欠点： a)と逆

ＤＳＭ：実現時に考慮すべきこと（２／３） キャッシュコヒーレンス制御 ブロック書き換えアルゴリズム １）書込み時無効化方式（write invalidate） 書込み時，他コピーを無効化 ２）書込み時更新方式（write update） 書込み時，他コピーを更新 ブロック書き換えアルゴリズム キャッシングしてくるローカルメモリが一杯の時，どれかを追い出す必要あり（犠牲ブロック） ページングシステムでは，LRU(Least Recently Used)が採用． キャッシュの状態，優先度とＬＲＵの組合せ．

ＤＳＭ：実現時に考慮すべきこと（３／３） 管理情報の管理方式 スラッシング キャッシング情報の管理方法 １）集中管理方式 ２）分散管理方式 論理的に一か所に集中 ２）分散管理方式 自ノードの情報 スラッシング ＤＳＭブロックのピンポン現象を防止 コンパイラによるフォールスシェアリングの抑制 データ属性に適したコヒーレンス制御の採用

ＤＳＭ：ページを基盤としたシステム（１／２） ＤＳＭブロック＝ページ 共有メモリ型マルチプロセッサのキャッシュと類似 対応関係 ローカルメモリ：キャッシュ ＤＳＭブロック（ページ）：キャッシュライン 概念図：図４．１５(a) ノード上にないページアクセス処理：図４．１５(b) ページを持ってくる方法 移動（migration） 複製（replication）

2 1 3 ページ ０ １ ２ ３ メモリ ＭＰＵ０ ノード０ メモリ ＭＰＵ１ ノード１ ノード２ メモリ ＭＰＵ２ ネットワーク 大域仮想アドレス空間 ページ 　　０ 　　１ 　　２ 　　３ メモリ ＭＰＵ０ ノード０ 2 メモリ ＭＰＵ１ ノード１ ノード２ 1 3 メモリ ＭＰＵ２ ネットワーク （a）概念図 図４．１５　ページを基盤としたＤＳＭ

（b）ノード１上でのページ０アクセス時の処理 ユーザ プロセス （２）ページフォールト （１）アドレス変換の ためのアクセス ページ表 i 1 2 v 3 （５）再開 （３）ノード２からページ０をもらい，マッピングする． （４）エントリ０の i を ｖ に変更 有効／無効ビット （Valid/ Invalid ） bit （b）ノード１上でのページ０アクセス時の処理 図４．１５　ページを基盤としたＤＳＭ

ＤＳＭ：ページを基盤としたシステム（２／２） ー書込み時無効化方式を用いたコヒーレンスプロトコル例（１／３）ー 各ページの状態 読出し専用（Ｒ） ページ表エントリ属性：　リードオンリ 各ノードに複数あってもよい． 読書き可能（Ｗ） ページ表エントリ属性：　リードライト システムで１つのみ（所有者のみ） 各ページごとに所有者を設ける． 最後に書込みを行ったノードが所有者

ＤＳＭ：ページを基盤としたシステム（２／２） ー書込み時無効化方式を用いたコヒーレンスプロトコル例（２／３）ー 状況（図４．１６） プロセッサ１が所有者 Ｒの状態，プロセッサ２にコピーなし（状態Ｓ１） Ｒの状態，プロセッサ２にコピーあり（状態Ｓ２） Ｗの状態（状態Ｓ３） プロセッサ２が所有者 Ｒの状態，プロセッサ１にコピーあり（状態Ｓ４） Ｒの状態，プロセッサ１にコピーなし（状態Ｓ５） Ｗの状態（状態Ｓ６） リード／ライトアクセス時の処理 図４．１６

ＤＳＭ：ページを基盤としたシステム（２／２）ー書込み時無効化方式を用いたコヒーレンスプロトコル例（３／３）ー 図４．１６　 各ページの状態と動作１２） プロセスAが読出しアクセス プロセッサ１　　　　プロセッサ２ R ：ページ プロセスAが書込みアクセス プロセッサ１　　　　プロセッサ２ 状態 A R 所有者 A ：プロセス A R 所有者 S1 読出し 1．ページの状態を 　　Wにする． 2．書込み 1．コピーの無効化を依頼 2．ページの状態を 　　Wにする． 3．書込み A R 所有者 A R 所有者 S2 読出し A W 所有者 A W 所有者 S3 読出し 書込み 1．コピーの無効化を依頼 2．所有権の獲得 3．ページの状態を 　　Wにする． 4．書込み A R 所有者 A R 所有者 S4 読出し 1.コピーを依頼 2．ページの状態を 　　Rにする． 3．読み出し 1．コピーの無効化を依頼 2．所有権の獲得 3．ページを送信してもらう． 4．ページの状態をWにする． 5．書込み S5 A R 所有者 A R 所有者 1．ページの状態を 　　Rにするよう依頼 2．コピーを依頼 3．ページの状態を 　　Rにする． 4．読み出し 1．コピーの無効化を依頼 2．所有権の獲得 3．ページを送信してもらう． 4．ページの状態をWにする． 5．書込み A W 所有者 A W 所有者 S6

ＮＵＭＡマルチプロセッサのメモリ管理 メモリの活用方法：図４．２３ キャッシング技法におけるＮＵＭＡ，キャッシュ，ＤＳＭとの相違 a)キャッシングなし b)キャッシングあり キャッシング技法におけるＮＵＭＡ，キャッシュ，ＤＳＭとの相違 表４．１ キャッシュとの大きな相違 キャッシュは，管理対象が小さい（キャッシュライン） ＤＳＭとの大きな相違 ＤＳＭは，キャッシングは永久的に適用． ＮＵＭＡはリモートアクセス可能，ソフトウェアで制御可能 ＮＵＭＡで主に考慮すべきこと 管理対象がページと大きい（キャッシュとの違い） ページの凍結，解除方策が必要（キャッシュ，ＤＳＭとの違い）

（１）メモリをキャッシュとして使用しない場合 ページ０ ページ１ ページ２ ページ３ 仮想アドレス空間 ページ０ ページ１ ページ２ ページ３ プロセッサ メモリ プロセッサ メモリ 多対１マッピング 相　互　結　合　網 （１）メモリをキャッシュとして使用しない場合 仮想アドレス空間 ページ０ ページ１ ページ２ ページ３ プロセッサ メモリ プロセッサ メモリ 多対多マッピング キャッシュとして使用（全部，一部） キャッシュとして使用（全部，一部） 相　互　結　合　網 （２）メモリをキャッシュとして使用する場合 図４．２３　メモリの活用方法

表４．１ キャッシュ，ＤＳＭ，およびＮＵＭＡの比較 ＤＳＭ ＮＵＭＡ キャッシュブロック ページ 不可 可能 オンデマンド， プリフェッチ 表４．１　キャッシュ，ＤＳＭ，およびＮＵＭＡの比較 ハードウェアャッシュ（コヒーレントキャッシュ） ＤＳＭ ＮＵＭＡ 管理対象 キャッシュブロック ページ リモートアクセスの可否 不可 可能 キャッシング時期 オンデマンド， プリフェッチ ソフトウェアで制御可能 キャッシング方法 （コピー，移動） コピー 制御適用時間 永久

ＮＵＭＡマルチプロセッサのメモリ管理 ー実現例（１／２）ー 対象マシン：図４．２４ メモリの活用方法 グローバルメモリ：通常のメモリ ローカルメモリ：キャッシュ キャッシュコヒーレンス制御方式 ライトバック方式 書込み時無効化方式 仮想ページの状態 読出し専用（Read-Only, RO） 複数のローカルメモリに存在する可能性あり． 内要は複数間で全て一致 局所書込み可能（Local-Writable, LW） １つのローカルメモリにのみ存在 グローバルメモリと内容一致 大域書込み可能（Global-Writable, GW） ローカルメモリにはコピーなし． グローバルメモリにのみ存在 方策の決定 ローカルメモリにキャッシング（LOCAL） グローバルメモリにだけおく（GLOBAL）

ＮＵＭＡマルチプロセッサのメモリ管理 ー実現例（２／２）ー MMU ローカル メモリ プロセッサ MMU ローカル メモリ ・・・ グローバル メモリ グローバル メモリ 図２．２４　対象マシン：IBM　ACE　マルチプロセッサワークステーション

表４．２ ページの処理 RO GW LW LOCAL GLOBAL RO GW LW LOCAL GLOBAL 方策決定 仮想ページの状態 表４．２　ページの処理 （１）読出しアクセス時 方策決定 仮想ページの状態 RO GW LW 自ノードにある場合 他ノードにある場合 LOCAL ローカルへコピー 全てをunmap 何もせず 他のものをSync&flush GLOBAL 全てをflush 自分のものをSync&flush （２）書込みアクセス時 方策決定 仮想ページの状態 RO GW LW 自ノードにある場合 他ノードにある場合 LOCAL 全てをflush ローカルへコピー 全てをunmap 何もせず 他のものをSync&flush GLOBAL 自分のものをSync&flush 上段：ローカルメモリに現在ある仮想ページへの対処法 中段：ローカルメモリにキャッシングするか否か 下段：仮想ページの状態遷移先 sync：ローカルメモリ内の当該ページをグローバルメモリへ書き出す． unmap：仮想ページのローカルメモリへのマッピングを無効化する． flush：unmapに加えて，当該物理ページを解放する．

以上