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


メモリ管理 (Memory Management)

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


メモリ階層

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

メモリ管理方式


ページング (Paging)

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

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

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

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

アドレス変換

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

ページサイズ

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

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

ページサイズが大きい場合はこの逆の特徴になります。


置換アルゴリズム

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

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

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

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


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

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

    CPU --- キャッシュ --- メモリ
のうち「CPUとキャッシュの間」と「キャッシュとメモリの間」 のどちらにいれるかが問題になります。


練習問題

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

    12, 14, 2, 34, 56, 23, 14, 56, 34, 12
主記憶には4ページしか入らないと仮定します。 置換アルゴリズムとして を使った場合それぞれについて、最後のページを転送した後に主記憶内に 存在するページを列挙して下さい。

[解答1]
以下のようにページが置換されるので最終状態では、 FIFOの場合は「56,23,14,12」、LRUの場合は「14,56,34,12」の ページが主記憶内にあります。
参照ページ主記憶内のページ
FIFOの場合LRU場合
121212
1412,1412,14
212,14,212,14,2
3412,14,2,3412,14,2,34
5614,2,34,5614,2,34,56
232,34,56,232,34,56,23
1434,56,23,1434,56,23,14
5634,56,23,1434,23,14,56
3434,56,23,1423,14,56,34
1256,23,14,1214,56,34,12

[問題2]
実アドレスキャッシュを用いたシステムがあり、 このシステムの動作時間が以下のように与えられているとします。
TLB変換時間25ns
キャッシュにその場所があるかどうかを判断する時間25ns
キャッシュにあるときデータをフェッチする時間25ns
主記憶を読む時間200ns
TLBのヒット率0.9
キャッシュのヒット率0.95
このときの平均アクセス時間を求めて下さい。 ただし簡単のため、TLBによる変換とキャッシュのアクセスは オーバーラップさせないものと仮定します。

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

実アドレス
の在処
データ
の在処
アクセス時間
(ns)
確率
TLBキャッシュ25+25+25=750.9×0.95=0.855
TLB主記憶25+25+200=2500.9×0.05=0.045
キャッシュキャッシュ25+25+25+25+25=1250.1×0.95×0.95=0.09025
キャッシュ主記憶25+25+25+25+200=3000.1×0.95×0.05=0.00475
主記憶キャッシュ25+25+200+25+25=3000.1×0.05×0.95=0.00475
主記憶主記憶25+25+200+25+200=4750.1×0.05×0.05=0.00025
この表の「アクセス時間×確率」の和を考えて
平均アクセス時間= 75 × 0.855 + 250 × 0.045 + 125 × 0.09025 + 300 × 0.00475 + 300 × 0.00475 + 475 × 0.00025
= 89.625 ns
となります。


nitta@tsuda.ac.jp