コンピュータ・アーキテクチャ

メモリ管理 (Memory Management)

CPUがプログラムを実行するためには、 少なくともCPUがそのコードを主記憶中から読み込もうとする 瞬間には、そのプログラムコードが主記憶中に置かれている 必要があります。 近年、プログラマが 「プログラムコードが現在主記憶にあるかどうか」 を気にすることなるプログラムを書けるのは 「OSのメモリ管理機構」のおかげなのです。

メモリ階層

• 主記憶 --- RAM(半導体メモリ)
  アクセス速度は比較的速い。容量はやや大きい。
• 2次記憶 --- ハードディスク, CDROM, 磁気テープ等
  アクセス速度は遅い。容量は非常に大きい。

OSの「メモリ管理 (memory management)」は 「使わない情報は低速なメモリに置き、必要に応じて高速な メモリに持ってくる」という動作を行います。

メモリ管理方式

• オーバレイ (overlay)
  プログラムの直接制御によって他のプログラムやその一部が必要に応じて 主記憶へ転送され、現在プログラムが使用しているメモリに上書きされる方式。 (例、50年代〜60年代の計算機、80年代でもMSDOSのリンカなど)
• ページング
  必要に応じて実記憶空間(主記憶)と仮想記憶空間(2次記憶)のデータを ブロック単位(ページ)で入れ換えて、あたかもランダムアクセス可能な 広大な主記憶があるように見せる方式。
• セグメンテーション
  メモリの中をいくつかのセグメントにわけて扱う方式。

ページング (Paging)

『ページング』とは 「主記憶と2次記憶のメモリがあたかもランダムアクセス可能な1つの主記憶 であるかのように見せる技術」のことです。

• ページ --- ひとまとまりのデータ (64byte〜4Kbyte程度)
• 仮想記憶 (virtual memory) --- 現実のメモリ空間(実記憶空間)とは 無関係に、非常に大きな主記憶空間(仮想記憶空間)があるように見せる機構。
• 実アドレス (real address) --- 実記憶空間のアドレス
• 仮想アドレス (virtual address) --- 仮想記憶空間のアドレス
• ページフィールド(page field)とラインフィールド(line field) --- アドレス(実アドレス、仮想アドレスともに)をこの２つに分けて扱います。
• ページテーブル (page table) --- 実アドレスと仮想アドレスの対応表のことです。
• ページフォールト (page fault) --- 「必要とされるページが主記憶内に ない」という状態のことです。 このときOSは、「必要なページを主記憶内に持ってきて、さらに ページテーブルを更新する」という動作を行います。
• ページ置換戦略 (page replacement algorithm) --- ページフォールトの際に、どのページを主記憶から追い出すか 決定する戦略のことです。

アドレス変換バッファ (TLB)

プログラムは局所性原理にしたがう性質をもっていますので、プログラムの 流れが変化するまで、ある特定のページの集合(ワーキングセット, working set) だけが参照されやすくなります。 使用する可能性の高いページアドレスを高速に変換するために、 高速なハードウェアによるページ検索テーブル、 「アドレス変換バッファ(TLB, Translation Look-aside buffer)」 を用います。

使う可能性が高い項目を保持しているという点では、TLBはキャッシュと 非常によく似たふるまいをします。

アドレス変換

「仮想ページアドレスを実ページアドレスに変換する」方法には 次の種類があります。

• (純粋な)直接マッピング
• 完全連想マッピング (連想マッピング)
• セット連想マッピング

一番よく使われる方式です。 仮想アドレスと実アドレスを、タグフィールド、インデックスフィールド、 ワード(オフセット)フィールドに分けて扱います。 同時に比較できるエントリの個数をセットサイズ(set size)または 連想度 (associativity)と呼びます。 セットサイズがnであることを連想度がn-way であると いいます(n-way set associative) 。

ページサイズ

ページサイズとTLBサイズの積は、TLBで直接扱えるメモリの量となります。 たとえば、ページサイズ4Kbyte, TLBが256エントリの場合、1Mbyteの メモリを直接扱うことができる)。 ページサイズはOSによってさまざまな値(64byte〜512Kbyte)をとりますが、 一般に 4Kbyte や 8Kbyteなどがよく使われているようです。

ページサイズが小さい場合は次のような特徴を持ちます。

• 主記憶とディスクメモリの間でページを転送するのにかかる時間が短い
• いろいろなプログラムから多くのページを選んで主記憶中に配置できる。
• 使われないデータを配置することが少ない
• ページテーブルが大きくなる→フラグメンテーション( page table fragmentation。マッピングテーブルがメモリを占有して しまい命令コードやデータがメモリを使えない現象)が起きる
• 各ページの最後にある未使用の空間(内部フラグメンテーション、 internal fragmentation)は少ない。

置換アルゴリズム

参照したページが主記憶内に無い場合 (＝ TLBにも主記憶用のページテーブルにもない場合)は、 ページフォールト (page fault)が起きます。 ページフォールトでは、 読み込まれるページ（＝参照するページ）は ディスクメモリ用ページテーブルを使ってディスクメモリの 中から探されます。 ページを読み込むときに主記憶内に空いている空間が なければ、使われていないページをまず主記憶から 取り除いてから読み込みます。

「主記憶から取り除くページ」を選ぶ方法が『置換アルゴリズム』です。 置換アルゴリズムは、キャッシュ・システムとページング・システム では大きく異なっています(TLBとキャッシュシステムは似ているが)。 キャッシュでは高速性が重要なのでハードウェアで実現していました。 ページング・システムでは、主記憶用のページ テーブルに含まれる多数のページ (TLBのページは最近使ったものなので取り除く対象からはずす) を扱う必要があるので、ハードウェアとソフトウェアの組合わせで 実現しています。

使用状況に基づいて置換を行うためには、いつページが参照された か、変更されたかどうかを記録しておく必要があります。 このためページごとに「使用ビット」や「修正ビット」を持たせておきます。

• 使用ビット (use bit, access bit) --- 参照されたときにセットされ、 ビットが読み込まれた時にリセットされます。
  (例)「1msごとに使用ビットを調べて使用回数を記録する」のに使います。
• 修正ビット (dirty bit, modified bit) --- ページ内に書き込みが 行われるとセットされます。このビットがセットされていると、置換される ときには書き戻す操作が必要になります。

取り除くページを決める置換アルゴリズムには次のようなものが あります。

• ランダム置換アルゴリズム --- ランダムに選ぶ方式です。 この方式はあまり使われていませんが、TLBの置換アルゴリズム としては使われることがあります。
  (例. VAX-11/780の変換バッファ, Intel i860のTLBなど)
• FIFO置換アルゴリズム --- First-In-First-Outで、読み込まれた順番で取り除く方式です。 FIFO なので「参照回数を記録する必要がない」というのが利点ですが、 「使用状況が反映されない」という欠点があります。
• クロック置換アルゴリズム --- 基本的にはFIFO方式ですが、 参照されたページをキューの後方に移動することで 使用状況を反映させる方式です。 ページが参照されたときに、参照ビットをハードウェアで セットする必要があります。
• LRU置換アルゴリズム --- 最も使われていない(Least Recently Used な)ページを取り除く方式です。 参照された順番を正確に管理するのは大変なので近似法が使われます。
  近似法の例 --- ページが参照されるたびに使用ビットをセットします。 システム割込タイマによって一定時間(例. 1ms)ごとに 全ページの使用ビットを調べます(調べた後はリセットしておきます)。 使用ビットがセットされていたら、そのページの 「参照回数の近似値」を１増やします。 「参照回数の近似値」が小さいものが最近アクセスされていないページです。
• ワーキングセットアルゴリズム --- 直前の期間Tの間に参照されなかった ページを置き換える方式です。置き換えの対象となるページが複数ある場合は、 その中でLRUアルゴリズムを使って選びます。

キャッシュを用いる仮想記憶システム

仮想記憶とキャッシュを用いるシステムでは、TLB (仮想アドレスから実アドレスへの変換をする)を

    CPU --- キャッシュ --- メモリ

• CPUとキャッシュの間 →実アドレスキャッシュ
  TLBで仮想アドレスを実アドレスに変換してからキャッシュを調べます。
• キャッシュとメモリの間 →仮想アドレスキャッシュ
  キャッシュを仮想アドレスでアクセスすると、キャッシュ内のワードを 選択する際にアドレスがすぐに得られるため、実アドレスキャッシュの 場合よりも高速に動作することが期待できます。 しかし、2つのプロセスが同じ実アドレスを2つの異なる 仮想アドレスで共有した場合も正しく動作するようにする機構が 必要で、キャッシュの機構が複雑になってしまいます。

練習問題

[問題1]
ページングシステムにおいて、ページが次の順で参照されるとします。

    12, 14, 2, 34, 56, 23, 14, 56, 34, 12

• FIFO置換アルゴリズム
• LRU置換アルゴリズム

[解答1]
以下のようにページが置換されるので最終状態では、 FIFOの場合は「56,23,14,12」、LRUの場合は「14,56,34,12」の ページが主記憶内にあります。

参照ページ	主記憶内のページ
	FIFOの場合	LRU場合
12	12	12
14	12,14	12,14
2	12,14,2	12,14,2
34	12,14,2,34	12,14,2,34
56	14,2,34,56	14,2,34,56
23	2,34,56,23	2,34,56,23
14	34,56,23,14	34,56,23,14
56	34,56,23,14	34,23,14,56
34	34,56,23,14	23,14,56,34
12	56,23,14,12	14,56,34,12

[問題2]
実アドレスキャッシュを用いたシステムがあり、 このシステムの動作時間が以下のように与えられているとします。

TLB変換時間	25ns
キャッシュにその場所があるかどうかを判断する時間	25ns
キャッシュにあるときデータをフェッチする時間	25ns
主記憶を読む時間	200ns
TLBのヒット率	0.9
キャッシュのヒット率	0.95

このときの平均アクセス時間を求めて下さい。 ただし簡単のため、TLBによる変換とキャッシュのアクセスは オーバーラップさせないものと仮定します。

[解答2]
実アドレスキャッシュなので、TLBは「CPUとキャッシュの間」に 置かれています。 実ページアドレスが『TLB or キャッシュ or 主記憶』のどれか にあり、データは『キャッシュ or 主記憶』のどれかにあるわけです。 この組合せは６通りあり、それぞれのアクセス時間と確率は以下の 表のように計算できます。