【請求項１】 実メモリを管理するページテーブルを、物理アドレスに応じて二つの領域に分割し、各領域毎に異なった整列方法を適用することを特徴とするメモリ管理方式。
【０００１】
【発明の属する技術分野】 この発明は電子計算機システムにおけるメモリ管理方式に関し、特に実メモリの割り当て方式に関する。
【０００２】
【従来の技術】 仮想記憶方式を採用した電子計算機システムでは、通常、連続した仮想アドレスに対応する実メモリは連続である必要がない。しかし、Ｉ／Ｏのようにハードウェアが直接メモリにアクセスする場合は物理アドレスを使用するため、物理アドレスの連続したメモリが必要になる。
【０００３】
通常このように物理アドレスの連続した領域が必要となった場合、実メモリの使用状況が格納されているテーブルを検索し、要求された大きさの連続した空きメモリが存在する場合はこれを割り当て、存在しなかった場合はメモリ上の情報を他のメモリに移動することで連続した空きメモリ領域を生成し、これを割り当てるという方法が使用される。
【０００４】
しかし、この方法では実メモリ上の情報を移動する処理に時間を要し、また生成された連続空きメモリ領域が物理アドレスでアクセスされるようになると移動ができなくなることから、この領域がさらに連続した実メモリ確保の障害となる可能性がある。
【０００５】
このため従来は実メモリを管理するページテーブルを整列しておき、使用される実メモリを局所化するという方法が使用されていた。
【０００６】
【発明が解決しようとする課題】 上記の方式では全てのページテーブル操作に対して整列が実行されるため、ページテーブル数が多い場合は処理のオーバヘッドとなっていた。また、このオーバヘッドを避けるためにハッシュを利用すると、ハッシュのために多くのメモリが必要となり、ユーザの使用できる資源を圧迫する結果となっていた。
【０００７】
【課題を解決するための手段】 上記の問題を解決するために、実メモリをある物理アドレスで二つの領域に分離し、各領域毎に異なった整列方法を適用する。
【０００８】
二つの領域は、物理アドレスをキーにして各ページを厳密に整列する領域（高精度管理領域）と、物理アドレスがある範囲内であるページを一単位として整列を行う領域（低精度管理領域）に分けられ、できるだけ低精度領域のメモリを割り当てるようにすることで使用メモリを局所化する。
【０００９】
高精度管理領域のページは一つのキューと、ハッシュで管理され、キューに属するページは全て物理アドレス順に整列されている。ハッシュは物理アドレスをキーとして、対応する範囲にページがあればそのページを、対応する範囲にページがなければ近傍のハッシュを指している。
【００１０】
高精度管理領域からメモリを確保する際はキューの最後に繋がれているページを外し、当該ページの物理アドレスに対応するハッシュが当該ページを指していればハッシュが隣接したページか、近傍のハッシュを指すように更新する。
【００１１】
高精度管理領域のメモリを解放する際は、物理ページに対応するハッシュから近傍のページを得て、キューを検索することで戻すべき位置を見つける。物理アドレスに対応するハッシュが他のハッシュを指していた場合は当該ページを指すように更新する。
【００１２】
低精度管理領域のページはある物理アドレス範囲に対応した複数のキューで管理される。ページはキューの上では整列されない。低精度管理領域には、空きページを持つキューへのヒントが存在する。
【００１３】
低精度管理領域からメモリを確保する際はヒントの指すキューに繋がれているページを外す。キューがからになった場合はヒントを更新する。
【００１４】
低精度管理領域のメモリを解放する際は、物理アドレスの対応するキューにページを戻し、ヒントが現在操作しているキューよりも高精度管理領域側を指している場合は更新する。
【００１５】
【発明の実施の形態】 本発明の実施例について図面を参照して詳細に説明する。
【００１６】
図１は本発明の実施例を示すブロック図であり、物理メモリ１は固定長のページに分割される。各ページは対応するページテーブル８を有し、物理アドレスが境界値９よりもより小さい領域を高精度管理領域、大きい領域を低精度管理領域として管理する。高精度管理領域のページは物理アドレスをキーとするハッシュ７を持つ。低精度管理領域はある範囲の物理アドレス毎にキュー４を持ち、ページはその物理ページに対応したキューに繋がれている。空きページを持つキューへのヒント５と空きページ数を示すフリーカウント１０が存在する。
【００１７】
メモリ確保手段２は、はじめに低精度管理領域の空きページ数を調べ、空きページが存在する場合はヒント５の指すキューからページを確保する。確保したページが当該キューの最後のページであった場合は、ヒント５が現在のキューよりもひとつ高精度管理領域側のキューを指すように更新する。
【００１８】
低精度管理領域に空きページが存在しない場合は高精度管理領域のキューの最後尾に存在するページを確保する。確保したページに対応するハッシュ７が確保したページを指していた場合は、ハッシュの指すページを自分に隣接したページに更新する。ハッシュの対応する物理アドレス範囲内にページが存在しないときは隣接するハッシュを指すように更新する。
【００１９】
ページ解放手段３は、ページテーブルを調べ、低精度管理領域のページである場合は低精度管理キュー４のなかで対応するものにページを繋ぐ。ヒントがいま操作したキューよりも高精度管理領域側のキューを指していた場合は、ヒントが現在操作したキューを指すように更新する。
【００２０】
高精度管理領域のページである場合は、ページに対応するハッシュから、解放するページを挿入すべき位置の近傍に存在するページを見つけ、物理アドレスをキーにしてキューをたどり、ページを挿入すべき位置に隣接したページを見つけ、繋ぐ。
【００２１】
【発明の効果】 本発明により、キューのエレメントを整列しておく必要がある場合であっても、エレメントの使用頻度等を考慮して厳密に整列しておく領域と、ある単位で整列されていればいい領域を分離することで整列に必要なオーバヘッドおよび資源量を軽減することが可能となる。
