計算機システム概論・４回目 本日のトピック：メモリの管理と仮想記憶 メモリ管理におけるOSの役割 メモリの割当方法について ページングと補助記憶 仮想記憶について

メモリ管理におけるOSの役割 メモリ（主記憶装置）： プロセッサと情報をやりとりできる唯一の装置 プログラムや計算の途中経過，結果などを格納 プロセスに何かをさせようとすると，必ずメモリが必要 有限の容量しかない 複数のプロセスに対し，メモリを配分する仕組みが必要 ...OSのお仕事

実現したい仕組み OS とプロセスの間で，「メモリの貸し借り」を行う仕組みが必要 プロセスは，OS からメモリを借りる メモリを「割当て」てもらう 借りたメモリが不要になったとき，OS にメモリを返す メモリを「解放する」 メモリ 要求 プロセス OS メモリ 管理 機構 割当 プロセス 解放

メモリ管理機構の仕事 メモリ管理機構が行うべき仕事： メモリの貸し出し状況把握 どのプロセスに，メモリのどの部分を貸し出しているか メモリの中で，利用可能な部分（未使用領域）はどこか 割当要求への対処 未使用領域のどこを切り取って，プロセスに貸し出すか プロセス（仮想計算機）のアドレス解決 プロセスから見える仮想的な住所（アドレス）と， 実メモリのアドレスとの対応付けを行う

メモリの使用状況 メモリの貸し出し状況把握とは... どのプロセスに，メモリのどの部分を貸し出しているか メモリの中で，利用可能な部分（未使用領域）はどこか を管理，把握すること OS プロセス１ プロセス４ プロセス３ プロセス５ プロセス２ 貸出中の領域 未使用の領域

状況把握の方法 どのプロセスに，メモリのどの部分を貸し出しているか プロセスごとに，どの領域を使っているか記録しておく レジスタ状態 メモリの開始アドレス 使用メモリサイズ 　： プロセス メモリの中で，利用可能な部分（未使用領域）はどこか 連結リスト，双方向リストなどを利用して記憶しておく ．．． 連結リスト： ．．． 双方向リスト：

未使用領域の管理方式例 未使用領域の最初の数バイトを用いて，リストを表現 最初の未使用領域の場所 サイズ 次の未使用領域の場所 30 50 120 30 170 30 -1 30 80 120 150 170 200 あらかじめ決められたアドレス サイズの昇順（降順）で連結することも可能 上図は連結リストとしての実現．双方向リストも可

メモリの解放 プロセスからメモリが解放（返却）されたとき... 当該領域を「未使用」扱いに 必要に応じて，他の未使用領域と併合 解放 併合 使用中 未使用

メモリの割当 プロセスからメモリの割当を要求されたとき... 未使用領域の一部を切り出して，プロセスに貸し出す どの未使用領域から切り出すか ... いくつかの戦略あり 使える未使用領域がない場合の対応は？ 要求サイズ A B 基本的には， すし屋のカウンターに グループ客を座らせる問題...と同じ

メモリ割当の戦略 要求サイズより大きな未使用領域の中で... (A) 最初に見つかったところから切り出す (first-fit) (B) もっとも大きな未使用領域から切り出す (worst-fit) 細かな未使用領域が多数発生することになり，損 (C) もっとも小さい未使用領域から切り出す (best-fit) 大きな領域を後に残しておけるので，全体的には得 要求サイズ A C B

戦略の違い 要求： の後に が来る場合 worst-fit戦略 割当不能！ best-fit戦略 割当可能！

割当不能時の対処法 要求されたメモリ割当に使える未使用領域がないときは... 未使用領域ができるまで待つ 小さな要求が先に処理され，いつまでも空かないかも 使用中の領域を移動して，大きなスペースを作りだす メモリ内部の他の場所に移動 補助記憶装置等，メモリの外部に，一時的に追い出す 要求サイズ

領域の再配置について 使用中領域の再配置（移動，追い出し）： 配置場所の変更を，プロセスには意識させたくない プロセス（プログラム）による「メモリの使い方」を十分理解し， その視野の外で動作する仕組みを作りだす必要アリ コンピュータのプログラム： 抽象化された仮想計算機上で動作するよう作成される メモリは，第 0番地から順番にすべて利用可能，と想定 仮想的なアドレスを使って，データ等の場所を指示 実動作時には，メモリ内のどこかに配置される

仮想計算機上のプログラム 仮想計算機内でのプログラム 100番地に配置 400番地に配置 仮想アドレスを実アドレスに変換する必要アリ 000: JMP 100 : 100: LOAD B, 200 200: 2Ah 仮想計算機内でのプログラム 100 JMP 200 : 200 LOAD B, 300 300 2Ah 100番地に配置 400 JMP 500 : 500 LOAD B, 600 600 2Ah 400番地に配置 仮想アドレスを実アドレスに変換する必要アリ

アドレス解決の仕組み 方式1) メモリ割当時に，どのラベルが何番地になるか計算する 配置場所の移動はきわめて困難になる 方式2) メモリベースレジスタ(MBR)をプロセスに持たせる アドレスの参照は，MBRの値により補正 MBRの値を変えれば，配置場所の移動は比較的容易 400番地に配置 MBR 400 仮想計算機内 400 JMP 100 (+ MBR) : 500 LOAD B, 200 (+ MBR) 600 2Ah 000: JMP 100 : 100: LOAD B, 200 200: 2Ah

ここまでのまとめ 計算機のメモリは，OSのメモリ管理機構が管理する メモリ管理機構は，プロセスからの動的な要求に対応する 未使用領域の管理には，リスト構造の利用が便利 best-fitting戦略を使えば，割当の効率がよい MBRを用いてアドレス解決を行えば，再配置が容易 ここからのおはなし ページ単位でのメモリ管理にすれば，もっと効率アップ MBR方式を拡張する必要あり 仮想記憶方式との整合性も良い

メモリの「ページ」 ページ：メモリを管理するときの１ブロック 典型的な1ページ＝4096バイト分のメモリ 基本的なアイデア： メモリ全体を多数のページに分割する プロセスの持つメモリも，ページに分割して管理 プロセスは，ページ変換表を使ってページの対応を管理 （MBRは使わない） この方式の良いところ： 必ずしも連続したページを割り当てる必要がない

ページの管理 実際のメモリ 使用中ページ 未使用ページ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 プロセスの持つ ページ変換表 1 2 3 14 6 9 内部番号 実ページ番号 14 6 9 2 ページ変換表を利用することで， 連続したメモリ領域を保持して いる場合と同等に扱える

プロセス内でのアドレス管理 ページサイズを S とする プロセスが，自分のメモリの先頭から M 番目にアクセスする： M = PS + Q となる P と Q を計算する P．．．プロセス内で何ページ目にあたるか Q ．．．そのページ内で，先頭から何番目か ページ変換表の P 行目を参照し，実ページ番号 R を得る メモリの RS + Q 番地が，アクセスすべき番地 実際のメモリ番地への変換は，OSが行う （プロセスは，OSに対して M 番地の内容を問い合わせるだけ）

アドレス変換の例 ページサイズを S = 1000h バイトとする プロセス内の 28F4h 番地にアクセスしたいとき．．． 28F4h = 2x1000h + 8F4h 実ページ番号は 9 メモリ 9 ページ目の 8F4h 番地 　＝ 98F4h番地を参照 1 2 3 14 6 9 内部番号 実ページ番号 0000 1000 2000 3000 14 6 9 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0000 1000 2000 3000 4000 5000 6000 7000 8000 9000 A000 B000 C000 D000 E000 F000 10000 11000 12000 13000

ページ単位でメモリ管理をする利点 使い道のない，小さな未使用領域の発生を抑制 「断片化の問題」が少ない 一つのプロセスに，連続したメモリを割当てる必要がない 割当場所の違いは，ページ変換表を使ってOSが吸収 ２番目の利点をもっと積極的に利用すると... ページの場所を移動しても，比較的簡単に対応可能 （プロセスのページ変換表を書き換えるだけ） ページを，メモリ以外の場所に一時退避することも可能 実際のメモリ容量以上のページを確保することも可能 ⇒仮想記憶

主記憶装置と補助記憶装置 準備： メモリのページを一時退避するための補助記憶装置を用意 （スワップ領域：ハードディスク等の高速装置を利用） アドレス変換表を拡張 （退避中か否か，退避場所に関する情報を持たせる） メモリ（主記憶装置） アドレス変換表 ディスク（補助記憶装置）

ページアウト 主記憶上の未使用ページが少なくなってくると... OSが，補助記憶装置に掃出すページを選択する 掃出すページの内容を補助記憶装置へ転送 掃出された跡地を未使用扱いに 掃出されたページを指していたアドレス変換表を更新 ページアウト スワップアウト

ページイン ページアウトされていたページが参照されると... 割込み（ページフォルト，アドレス変換例外）が発生 主記憶の未使用ページへ，補助記憶からデータ転送 アドレス変換表を更新 ページイン スワップイン

ページアウトの戦略 ページイン：参照されたページを読み込むだけ ページアウト：どのページを掃出すか，選択の余地あり 参照される確率が低そうなページをページアウトしたい 「メモリ参照の局所性」を利用 プログラム実行中のある時点でA番地のメモリを参照 ⇒A番地付近のメモリも参照される可能性が高い メモリのページ毎に，「最近いつ参照されたか」を記録しておく 「近々には使われなさそうなメモリページ」をページアウトする

LRU法 LRU法 (Least Recently Used) 「最近最も使われなかった」ページを掃き出す戦略 グローバルLRU法： 対象ページがどのプロセスに属するか無関係に， とにかく最近使われていないものを掃き出す ローカルLRU法： 優先度の低いプロセスを特定し，そのプロセスに 属するページをLRUで掃き出す

仮想記憶 ページイン，ページアウトが可能であれば， プロセスの全てのページが，主記憶上にある必要はない 仮想記憶： プロセスに「見せる」アドレス空間を，実際のメモリの アドレス空間とは分離して管理する仕組み プロセスに対し，実際のメモリサイズよりも大きな メモリサイズを提供することが可能 ただし，頻繁にページイン・ページアウトを繰り返すようだと， 実行効率は大幅に悪化する

メモリ管理に関連するその他の概念 デマンドページング，プリページング 実際に参照されたページのみページインする（デマンド–） ページ参照を予測し，事前にページインを行う（プリ–） スラッシング メモリの割当要求が過剰で，プロセッサがページイン， ページアウトにばかり時間をとられて仕事が進まない様子 近年の計算機...巨大なメモリを持つようになった ⇒ スラッシング，ページングが発生する機会も少なくなった

本日のまとめ メモリ管理について 未使用領域の管理と割当戦略 ページング 仮想記憶 次回の講義：ファイルシステムについて 課題（結果の提出不要）： UNIXベースのOSで vmstat を実行し，メモリ使用状況や ページイン・アウトの様子を観察せよ