[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

[OSASK 1745] Re: 仮想記憶.

  こんにちは、川合です。


Koyanagi Masaaki さんは 2001/06/09 11:53:18 の「[OSASK 1744] 仮
想記憶(Re:  OSASKの記憶域管理(1).)」で書きました：

>OSASK での仮想記憶管理はどのようになるのでしょうか？

  はい、お答えします。OSASKでの仮想記憶管理は、LRU(least recentl
y used)アルゴリズムで管理されます。これは、基本的に「ページング
ゲーム」で示されたものと全く同じです。しかし、ルール10が僕には明
確な表現ではないと思われるので、LRUにおけるルール10をここに書い
ておきます。

>10. zarkされない物は、だんだん汚くなっていく。

10.あるプレイヤーがzarkすると、zarkされた物は他のどの物よりもき
   れいになる。そして、それ以外の作業場にある物はそれぞれ汚さが1
   つ増す。なお、汚いという概念は、作業場に置かれたものにしかな
   い。

  一般に、LRUアルゴリズムは双方向リストによって管理されます。

    page000 page001 page002 page005 page003 page004 page008

  仮にメモリが7つのページを保持できるとしたら、ある時点でのLRUス
タック（LRUのためのリストのこと）は上記のようになっているでしょ
う。ここで、一番左がスタックトップで、もっとも最近にアクセスされ
たことを意味します。この時点で、もしpage003へのアクセスが起これ
ば、

    page003 page000 page001 page002 page005 page004 page008

と並べ替えられます。つまり、page003が双方向リストから切り離され
、左端につながれます。これをアクセスがある度に行い、この中にない
ページへのアクセスが生じたら、一番右にあるページをスワップアウト
してLRUスタックから切り離し、スワップインしたページは左端に加え
られます。たとえば、page007へのアクセスがあれば、

    page007 page003 page000 page001 page002 page005 page004

となるわけです（page008はスワップアウト）。

  このLRUアルゴリズムは大変ポピュラーなもので、この手の問題の解
決のほとんどで利用されています。たとえば、CPUのキャッシュ管理ア
ルゴリズムもLRUです（CPUで言われているキャッシュ用語でOSのページ
ング手法を説明するなら、full associative キャッシュということに
なるでしょう・・・これは、2 way set associativeや4 way set assoc
iativeよりもずっと高いヒット率を実現できます。CPUのキャッシュで
はキャッシュメモリに空きがあってもキャッシュラインの入れ替えをや
らなければいけないんです。full associativeでは、キャッシュがいっ
ぱいになるまで入れ替えはありません）。

  CPUのキャッシュ管理と仮想記憶管理が似ているからこそ、「メモリ
は所詮ファイルキャッシュでしかない」というOSASKの発想になるわけ
です。「本来メモリにあるのだが、あふれてしまったからHDDに書き出
す」という普通の仮想記憶ではなく、「本来メモリの外にあるものを、
アクセスのためにメモリに持ってくる」と考えるわけです。

  この違いは、言葉の違いでしかないという主張もあるでしょうし、本
質的な違いがあるという主張もあるでしょう。ただ、損をすることはま
ずないと思っています。誤解されるのは、「空きメモリが十分にあって
もHDDへのアクセスが起きるんじゃないか」という点です。それは遅延
書き込みの設定次第ですが、普通は起きないと考えてよいでしょう。

  仮にHDD上に適当な1MBのファイルを作り、アクセスし、デリートする
という作業を考えます。これを、普通のOSで1MBのメモリをアロケート
して、アクセスしてフリーするというのと比べてみようというわけです
。

  (1)メモリに1MB以上の空きがある場合：
    最高遅延時間が十分に長ければ、HDDのアクセスは全く起きない。
  ファイルを作ったばかりの時、その中身は不定であり、最初にアクセ
  スしてもロードは起きない。また、遅延書き込みのため、変更内容を
  HDDへストアするのはアクセスの直後ではなく、もし遅延書き込みが
  始まる前にデリートされてしまえば、結局HDDへはアクセスしないこ
  とになる。

  (2)メモリに十分な空きがない場合：
    おそらく、1MBをメモリに保持できなくなって、書き出し・読み込
  みするはめになるだろう。でも、それは普通のOSの仮想記憶であって
  もスワップアウト・スワップインすることになるので同じである。

  OSASKの方法のよいところは、メモリアクセスに相当するアクセスだ
けでなく、いわゆる普通のファイルアクセスも自然にキャッシュされる
というところです。普通のOSの仮想記憶だと、仮想記憶管理とファイル
キャッシュ管理は別であり、ややこしくなります。

---

  ついでなので、現在の開発状況を少し書いておきます。あと数日のう
ちに「えせ」仮想記憶ルーチンができそうです。なぜ「えせ」なのかは
ベータ公開時に説明します。


  それでは。

--
    川合 秀実(KAWAI Hidemi)
川合堂社長 / OSASK計画総指揮 / カーネル開発班
E-mail:kawai !Atmark! imasy.org
Homepage http://www.imasy.org/~kawai/