オペレーティング・システム講座
記憶管理
概要記憶はＣＰＵと並んで、コンピュータにとってとても大切な資源です。 したがって、記憶をどのように構成し、管理するかは重要な課題なのです。 この章(記憶管理)では、メモリの構成から始まり、仮想記憶の実現について話をします。 タイトルを列挙すると次のようになります。
メモリ構成図１に示すように、コンピュータにはメモリの階層構造が存在しています。 これは、小容量な高速のキャッシュメモリをCPUの側に置き、 CPUから遠くなるに従って、大容量のメモリを配置するというものです。
CPUが大容量メモリにある内容にアクセスしたいときには、 そのメモリにある内容を上の階層に転送してから使います。 例えば、補助記憶装置にある内容にアクセスする場合、 まず、その内容を主記憶に読込みます。 そして、主記憶に読込んだ内容をキャッシュメモリに読込んで、 CPUがアクセスするようになっているのです。 この方式は一見効率が悪いように思われるかもしれませんが、 実はとても理にかなった方式です。 そのため、今日の多くのコンピュータにはこのようなメモリ階層構造があるのがあたりまえです。 メモリ階層間のデータ転送管理メモリ階層間のつながりをうまく行うためには、それらを管理する機構が必要です。 キャッシュメモリと、主記憶の間の管理はハードウェアが自動的に行いますが、 主記憶と補助記憶装置とのつながりは、オペレーティング・システムが管理しています。 また、後述する仮想記憶もオペレーティング・システムによって実現されています。 そこでこれから先は、仮想記憶、および主記憶と補助記憶装置に焦点をあてます。 仮想記憶現在のコンピュータでは、仮想記憶とは各プロセスごとに与えられるアドレス空間のことです(図2)。 それぞれのプロセスは別々のアドレス空間を持ち、それらは互いに独立になっているので、 プログラムは他のプロセスに影響されることなく実行できるようにっています。
この章では、仮想記憶空間がどのように実現されているのか解説します。 実現法はセグメンテーションとページングがあります。 なお以下の解説では、主記憶と補助記憶装置とのつながりも交えて話を進めているので、 注意して読んでください。 セグメンテーションセグメンテーションでは、まず仮想アドレス空間をセグメントという単位に分割します。 そして、主記憶にこれらの領域をセグメント単位で割当てることで、仮想記憶を実現しています(図3)。
各セグメントにはセグメント番号とセグメントサイズが与えられています。 セグメント番号は、仮想アドレスの上位ビットで指定されるエントリです。 一方、セグメントサイズは、主記憶上への領域割当ての際に用いられます。 セグメントテーブルセグメントテーブルとは、どのセグメントが、どれだけの領域を持ち、主記憶上のどこから始まるか などのセグメント情報を管理するテーブルのことです(図4)。 テーブルには次の情報が格納されています。
仮想アドレスから物理アドレスを得る方法まず、仮想アドレスが与えられると、そこからセグメント番号を読みだし、 セグメントテーブルの中から、対応するセグメント情報を抜き出します。 すると、セグメントベースアドレス(主記憶上のセグメント開始アドレス)が得られるので、 これと、仮想アドレスからセグメント内変位を取出し、和をとって物理アドレスとします。 一連の情報の流れを図5に示します。
以上が仮想アドレスから物理アドレスを得る基本的な方法です。 しかし、実際はエラーチェックが入るので、もう少し複雑な動作をします。 例外処理仮想アドレスから物理アドレスに変換された際に、 実際にそれが主記憶上に存在する領域なのかをチェックしなければなりません。 補助記憶に退避されているとしたら、それを主記憶上に読みださなければならないでしょう。 また、仮想アドレスがセグメントの枠を越えて、与えられるかもしれません。 この場合は、エラーを発生させる必要があります。 以上のように、実際に主記憶をアクセスするためには、いくつかのチェックを行わなければなりません。 チェック項目をあげると、次のようになります。
セグメントが主記憶に存在しない場合セグメントが主記憶に存在するか否かは、セグメントテーブルの存在ビットを調べることによりわかります。 セグメント情報を取出した段階で存在ビットが0であれば、 割り込みを発生させて、OSがそのセグメントを補助記憶から主記憶に読みだし(スワップイン)ます。 読み出しが完了すると、主記憶上のセグメント開始アドレスがセグメントテーブルに書き込まれます。 セグメントの枠を越えてアクセスしようとした場合セグメントの枠を越えたがどうかは、仮想アドレスのセグメント内変位と、 セグメントテーブルにあるセグメントサイズの情報を比べることでチェックできます。 セグメントの枠を越えてアクセスしようとすると、このチェック機構により割込みが入り、 OSはセグメンテーションフォルトが起きたと判断します。 アクセス権限がなかった場合セグメントテーブルには、各セグメントにたいしてアクセス保護情報(読み書き実行)があり、 特定の権限でないとアクセスできないようになっています。 権限を越えてアクセスしようとすると割込みが発生し、OSはアクセス保護エラーが起きたと判断します。 ページングページングでは、主記憶および仮想アドレス空間にページと呼ばれる単位を設定します。 そして、ページごとに仮想アドレスと物理アドレスを対応させることによって、仮想記憶を実現しています(図6)。 なお、セグメンテーションでは、セグメントと呼ばれる可変長の領域を考えましたが、 ページングでは、ページと呼ばれる固定長の領域を取扱います。
ページングを扱う利点は、主記憶と補助記憶装置との間のデータのやり取りが扱いやすくなることでしょう。 もともと補助記憶装置はページを単位として構成されているため、 ページングは主記憶と補助記憶装置との相性を良くします。 ページテーブルページテーブルもセグメントテーブルと同じようなものです。 ただし、ページサイズは固定なので、セグメントサイズはありません。 また、他にも補助記憶装置とのインタフェースを考えて、 セグメンテーションにはなかったものもあります。 以下にページテーブルに格納されている情報を示します。
仮想アドレスから物理アドレスを得る方法や、 例外処理はセグメンテーションの場合と変わりません。 ところで、修正ビットや参照ビットはセグメンテーションにはありませんでした。 以下では、これらについて解説します。 修正ビット修正ビットは、そのページが書き換えられたときにセットされるビットです。 すると、主記憶の内容を補助記憶装置に書出すときに、 このビットがセットされているページだけ書出せば良いことになります。 つまりこのビットがあることで、効率の良い退避が可能になります。 参照ビット参照ビットは、主記憶がいっぱいのとき、 どのページを補助記憶装置に掃出すかを決めるためのビットです。 参照ビットについては、LRUを取り上げるときに解説します。 多段のページングさて、ここではまず、上のページング方式での欠点を述べます。 いま、ページサイズが４ｋバイトとします。 もしこれを32ビットの仮想空間にそのまま割当てようとすると、 ２の20乗個ものページテーブルのエントリが必要です。 つまり、少なくとも４Ｍバイトもページテーブルに費やすことになり、実際的ではありません。 しかも仮想空間の数はプロセス数だけあるのですから、 ページテーブルは膨大なサイズになってしまいます。 そこで、考えだされたのがページを多段化する方法です。 図7に２段のページングを示します。１段目で得られるアドレスは２段目のページテーブルの開始地点になっています。 そして、２段目で得られるアドレスに変位を加えることにより、物理アドレスを得るのです。
この方式は「仮想アドレス空間のうち、実際に使われる領域はわずかである」という傾向に基づいています。 実際、プロセスが仮想アドレス空間に使う領域はそれ程多くないので、この方式は有効なのです。 ただし、ページングの段数が増えると、それだけオーバーヘッドも大きくなります。 そのためには、アドレス変換バッファを用いるなどして高速になるような工夫をしたりします。 仮想記憶の管理補助記憶装置と主記憶の間でデータのやり取りをする上で、 次の３つの問題を解決しなければいけません。
ページ取出しは、どのページをいつ主記憶に読込むかを扱う問題です。 また、ページの配置はページングの場合は特に問題になりません。 そして、ページ置換えは、主記憶がいっぱいのときにどのページを補助記憶装置に退避させるかを扱う問題です。 以下では、ページ取出しとページ置換えについて取り上げます。 ページ取出しページ取出しには、デマンドページングと呼ばれる方式と、 プリページングと呼ばれる方式があります。 実際のオペレーティングシステムは、基本的にはデマンドページング方式ですが、 部分的にプリページング方式も用いられています。 デマンドページングデマンドページング方式は、参照されたページが主記憶になく、 ページフォルトが発生したときに補助記憶装置からページを読込む方式です。 プリページングプリページング方式は、ページが参照される前に、 前もって補助記憶装置から主記憶にページを読込んでおく方式です。 この方式では、どのページが参照されるのかあらかじめ予測をしなければなりません。 この予測が実際には困難であることから、プリページング方式は次のような場合にだけ使われます。 プログラムの実行開始時プログラム開始時は、多くのページが参照されるので、 実行開始時にあらかじめたくさんのページを読込んでおくと、効率が良くなります。 ページフォルトが発生したときページフォルトが発生すると、 仮想記憶上でその近辺のページが参照される可能性が高まるので、 それらのページをあらかじめ読込む、という操作がなされます。 ページ置換え主記憶上に空き領域が少なくなってくると、 この先しばらく使われそうにないページは、補助記憶装置に退避させられます。 これは主記憶と補助記憶装置を効率良く使って、 仮想アドレス空間を主記憶以上にとるためにはどうしても必要な操作です。 ところが、この先しばらく使われそうにないページを予測するのは、容易ではありません。 そこで、実際にはプログラムの時間的な局所性を利用して、 LRU(Least Recently Used)というアルゴリズムが使われます。 LRUアルゴリズムLRUアルゴリズムは、最近、最も間アクセスされていないページを 補助記憶装置に退避させるというアルゴリズムです。 これは、次に述べるプログラムの時間的局所性という性質が有効性を裏付けています。 時間的局所性とは、ある限られた時間の中では、 プログラムはいくつかの特定のページのみをアクセスするという性質のことです。 つまり、もし何らかの手段で最近アクセスされたページがわかるとすれば、 そのページは近い将来再びアクセスされる確率が高いというわけです。 このような性質を裏に考えると、最も長い間アクセスされていないページは、 この先も最も長い間アクセスされない可能性が高いということになります。 これが、LRUアルゴリズムの本質です。 一方で、プログラムには空間的局所性という性質もあります。 空間的局所性とは、アクセスされるページはまとまって存在する傾向にあるということです。 つまり、最近アクセスされたページの近傍のページは、 近い将来アクセスされる確率が高いということを意味します。 これは、LRUアルゴリズムとは関係ありませんが、時間的局所性と並ぶ概念なので、 ここで解説しました。 LRUアルゴリズムの実際・・クロックアルゴリズムLRUアルゴリズムを実現するには、 アクセスされたページを順にリストとして保持し、 最も古いページを選ぶといった方法が考えられます。 しかし、この方法では実装が困難なため、実際にはクロックアルゴリズムと呼ばれる方式で 掃出すページを選びます。 ページングのところで述べましたが、ページテーブルには参照ビットがあります。 この参照ビットは、そのページがアクセスされるとハードウェアによりセットされる仕組みになっています。 さて、クロックアルゴリズムの原理を図8に示します。
いま、ポインタがページテーブルの参照ビットを調べ、 これがセットされていればクリアして次にポインタを進めます。 ここで、参照ビットがセットされていなければ、このページを補助記憶装置への掃出し対象とし、ポインタを進めます。 このようにしてポインタを進め、最後のページに到達したらまた初めのページから処理を開始します。 以上の方法で、掃出し対象になるページは少なくとも最近一定時間はアクセスされていないページです。 ページ置換えの方式は、基本的にはこのようになっているのです。 参考文献清水謙多郎著『オペレーティング・システム』情報処理入門コース,岩波書店(1992) |
Multisoft-labのホーム ご意見・ご感想等の受付
|
Copyright © 2004 Multisoft-lab All rights reserved. |