(57)【特許請求の範囲】
【請求項１】
主記憶を大容量のブロックで分割し，各ブロックに対応してブロックの使用状態を表す管理テーブルであって，対応する前記ブロックを小容量のページ単位に分割して各ページに対しその使用状態を表す１ビットが割当てられた全ページ分のビットが設けられた管理テーブルと，
主記憶領域の割当て要求に対し順次異なるブロックを指定して割当てを行う主記憶管理部とを有する主記憶管理装置であって，
前記主記憶管理部は，要求に応じて指定されたブロックに対応する管理テーブルを検索して，使用可能なページ位置と，必要ページ数分の領域を獲得して，該当する管理テーブルのページの各ビットの状態を更新することを特徴とする主記憶管理装置。
【請求項２】
請求項１に記載の主記憶管理装置は，
前記主記憶の各ブロックに対応して設けられた各管理テーブル内の割当て可能なページ位置を格納したページ位置テーブルをさらに有し，
前記主記憶管理部は，割当て要求により指定されたブロックに対応する前記ページ位置テーブルを検出して，要求されたページ数分の領域を獲得することを特徴とする主記憶管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータシステムにおいてプログラムの実行領域及びデータ領域の割当てと戻しを動的に管理する主記憶管理装置に関する。
【０００２】
近年，コンピュータシステムの大規模化及び大容量化の要求に伴い，主記憶の容量は増加の一途をたどっている。従来行われていた主記憶管理方式では，割当て領域の偏りや管理テーブル容量の増加を招いており，これを防止するために主記憶を効率良く管理しなければならない。
【０００３】
【従来の技術】
図９は従来例の説明図であり，図中，８０は主記憶，８１は管理テーブルである。図９に示す従来例の情報処理装置の主記憶８０は，全体を固定の記憶容量の単位により分割して管理しており，この説明では１単位（ページという）を４ＫＢ（キロバイト）とし，主記憶８０全体がｎページ分（例えば，ｎ＝２５０）の容量を持つものとする。主記憶８０を管理するための管理テーブル８１には，主記憶８０の各ページに対応してそのページを使用するタスクの識別符号（図９の例では，Ａ，Ｂで表す）を格納する領域が設けられ，タスクの個数が２５６以下であれば，識別符号長は１バイト（８ビット）で構成される。なお，主記憶８０の使用されてない（空き）状態のページに対応する管理テーブル８１の領域には，空きを表示する情報が設定される。
【０００４】
このような主記憶８０に対して，プログラムの処理によりタスクが主記憶８０の領域を使用する要求が発生すると，図示されないＯＳ（オペレーティングシステム）の制御により，管理テーブル８１を検索して，使用中の領域に続く空き領域が見つかると，そこから要求された容量を満たすページ数（４ＫＢの倍数）を獲得すると，管理テーブル８１の獲得した各ページに対応する領域に当該タスクの識別符号を書き込む。以下，各タスクからの要求に応じて同様の方法で必要な記憶領域がページ単位で順に割り当てられる。図９の例では，先頭から３ページ分（４ＫＢ×３＝１２ＫＢ）がタスクＡにより使用され，その後の６ページ分がタスクＢにより使用されている。記憶領域の使用が終了して解放されると，管理テーブル８１の各ページに対応する領域には，未使用状態を表す情報を設定して戻す処理が行われる。
【０００５】
【発明が解決しようとする課題】
近年，主記憶の容量は増大する傾向にあるが，上記図９により説明した従来の技術によれば，記憶容量が増大しても主記憶は，先頭から順番に各タスクに対して割当てられても，それらの使用が終了すると未使用の状態に戻されて，先頭付近の記憶領域が繰り返して使用されて，主記憶の全体を満遍なく使用することがない。
【０００６】
一方，記憶装置の正常性をチェックするには，記憶領域の全体について書き込み，読み出しを行うことにより実現されるが，上記の従来の主記憶の管理方法によれば，管理テーブルの容量が増大するが主記憶の一部の領域だけを偏って頻繁に使用することになり，主記憶の正常性をチェックすることができないという問題があった。また，各ページ単位で使用するプログラムの識別符号を格納するために所定領域（図９では１バイト）を使用するため主記憶の容量の増大に対応して管理テーブルの容量も増えるという問題があった。
【０００７】
本発明は主記憶の容量が増えても全体の領域を広く均等に使用すると共に管理のためのテーブルの容量を抑制することができる主記憶管理装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明は主記憶容量が増加しても複数の管理テーブルを用い領域の割当て毎に管理テーブルを変化させることで割当て領域の偏りをなくし，管理テーブルはページ毎に１ビットのデータで管理し，割当てアドレスと領域の関係を別に管理することで，上記の問題を解決した。
【０００９】
図１は本発明の原理構成を示す図である。図中，１はＧＢ（ギガバイト）単位の大容量ｘの主記憶，１−０，１−１，…，１−ｎは主記憶１を拾数ＭＢ（メガバイト）単位程度の容量ｙで分割してｎ＋１個設けられたブロック，２−０〜２−ｎは主記憶１を分割した各ブロック１−０〜１−ｎに対応して個別に設けられ，各ブロックを小容量（例えば，数ＫＢ単位程度）のページで分割して，各ページの配列順に１ビットを割り当てて使用／空の状態を表した管理テーブルである。３は主記憶管理部であり，３ａはテーブル検索手段であり，割当て要求が発生する毎に，複数の管理テーブルの中から一つを順番に割当て，その管理テーブルにより空き領域を検索して割当てを行う手段であり，３ｂはテーブル設定手段である。３ｃは前回領域割当てを行ったブロック番号（管理テーブル番号）の次の番号を保持する番号保持部である。４はページ位置テーブルであり，各管理テーブル内のそれぞれにおける使用可能なページ位置が設定され，４−０〜４−ｎは各管理テーブル２−０〜２−ｎに対応したページ位置である。５は記憶領域の戻しを管理するのに有効なアドレス管理テーブルであり，使用した記憶領域の位置や，使用ページ数と共にその領域を使用したプログラム（タスク）の識別符号を含む。
【００１０】
主記憶管理部３は，プログラムからの記憶領域の割当て要求により起動すると，テーブル検索手段３ａは，主記憶１をブロック単位で分割した各領域に対応して設けられた管理テーブル２−０〜２−ｎの中から，今回の領域割当てのブロック番号を番号保持部３ｃから取出し，管理テーブル２−０〜２−ｎの中から取出した番号に対応する一つの管理テーブル（２−１とする）のビットを検索して，“１”（使用中を表す）の後に“０”が連続して設定されていることを検出すると，その先頭のビット位置を識別することで，主記憶１内の検出した番号のブロック内の検索により得られた「ビット位置」をページ位置として求めることができ，該当する位置から割当てを要求されたページ数分を割当て，テーブル設定手段３ｂにより当該管理テーブル２−１の割当てられたページ数分のビットを未使用を表す“０”から使用中を表す“１”に設定する。また，番号保持部３ｃの値は更新（＋１）され，次の記憶領域の割当て要求が発生すると，次のブロック（管理テーブル番号）について領域の割当てが行われる。なお，領域の使用が終了した場合は，割当てられた主記憶の領域を開放するため，管理テーブル２の対応するぺージの状態を使用中から空きの状態に設定される。
【００１１】
また，ページ位置テーブル４には，各ブロック１−０〜１−ｎに対応する各管理テーブル２−０〜２−ｎ内のそれぞれの空きページの先頭位置（アドレス）が設定されており，上記の管理テーブル２−０〜２−ｎの内容を検索する手間を無くし，ページ位置テーブル４の中から管理テーブルの番号に対応するページ位置を検出すれば良い。記憶領域が割当てられると，ページ位置テーブル４の該当する管理テーブルに対応するページ位置を割当てられたページ数だけ更新（加算）する。更に，主記憶１の記憶領域が割当てられた場合，その割当てを受けたプログラム（タスク）の識別符号と，割当てられたページのアドレスやページ数をアドレス管理テーブル５に格納する。アドレス管理テーブル５は，割当てを受けるプログラム（タスク）毎に多数個設けられる。
【００１２】
【発明の実施の形態】
図２は主記憶の具体例に対応する管理テーブルの構成例である。この例では，主記憶１が２ＧＢ（ギガバイト）の容量（図１においてｘ＝２×２30Ｂ（バイト）の場合）を備え，１ブロックが１６ＭＢ（メガバイト）の容量（図１においてｙ＝１６×２20Ｂの場合）を備えているものとする。この場合，主記憶１は，２ＧＢ／１６ＭＢ＝１２８であるから，１２８ブロックに分割することができ（図１において，ｎ＝１２７），従って管理テーブルは符号２−０〜２−１２７で表す合計１２８個設けられる。
【００１３】
この各ブロックを４ＫＢ（正確には４０９６Ｂ）の容量からなるページにより分割すると，１６ＭＢ／４ＫＢ＝４０９６ページとなり，１ブロックは４０９６ページで構成され，管理テーブルにより各ページの状態（使用中／空き）を１ビットで表すと，各ブロックに対応する各管理テーブル２−０〜２−１２７はそれぞれ４０９６ビット（５１２Ｂ）の容量となる。
【００１４】
図３は管理テーブル内の領域の位置を表すページ位置テーブルの構成例を示し，図４は割当てアドレスと割当てを受けたタスクの関係を示すアドレス管理テーブルの構成例である。
【００１５】
上記図２に示す管理テーブルの構成例の場合，各管理テーブルは４０９６ビットであり，更に１２８個の管理テーブル全体の中のどのビット位置（管理テーブル番号を含むページ番号）であるかを表すためのアドレス長は，２バイト（１６ビット）が必要になる。図３のページ位置テーブルには，複数の管理テーブル２−０〜２−１２７の各ページ位置を表す２バイトが格納され，合計２Ｂ×１２８＝２５６Ｂで構成され，図３では各ページ位置は１６進表示（０x で表す）の４桁の数値で表示されている。
【００１６】
主記憶の領域を使用したプログラム（タスク）が，使用後に領域を開放して元に戻す（空き領域にする）処理を忘れる等の状態を調査するのに必要な情報を格納したアドレス管理テーブルの構成例を図４に示す。このアドレス管理テーブルは，記憶領域の割当て毎に生成され，各割当てに対応して，割当てアドレス（４バイト），プログラムまたはタスクを表す識別ＩＤ（２バイト），当該割当てで使用するページ数（２バイト）である。アドレス管理テーブルの容量は，最大割当て個数をｍ個とした場合，ｍ×８バイトとなる。
【００１７】
図５は管理テーブルとページ位置テーブルの関係を示す。図５には上記図２に示す管理テーブルの中の一つの管理テーブル２−ｎと対応するページ位置テーブル４内のページ位置４−ｎの例が示される。
【００１８】
管理テーブルｎは上記したように４０９６ビットで１６ＭＢのブロックを管理することが可能である。このブロックの中で領域が割当てられていない状態では，全て“０”となっている。領域の割当て要求があった場合，０番地から順番に領域を探索してゆく方法が一般的であるが，本発明によるページ位置テーブルに記述されているページ位置から探索を行う。
【００１９】
図５のＡ．は，ページ位置テーブル４の中の管理テーブルｎに対応するページ位置４−ｎとして“８”が設定されている状態を表す。この状態の時，ユーザプログラムからの要求ページ数が“４”であり，管理テーブル２−ｎが割当てられたものとする。これにより図５のＢ．に示すように管理テーブル２−ｎの８番目から４ページ分の領域が確保されることで，管理テーブル２−ｎの該当する位置が“０”から“１”に書き換えられ，これに対応するページ位置テーブルのページ位置４−ｎの値も８＋４＝１２となり，次回獲得要求があると１２番目から探索する。
【００２０】
このように，ページ位置テーブルは管理テーブルの探索を開始する位置を示しており，要求ページ数が獲得された場合，要求ページ分更新する。従って，次回の探索では管理テーブルの先頭から探索する必要がないため，探索時間が短縮される。
【００２１】
図６は主記憶の領域割当て及び解除の処理フローである。図中，３０〜３３は上記図１の主記憶管理部３に対応するソフトウェアであり，３０はユーザプログラム，３１はＳＶＣ（Supervisery Call：スーパーバイザリ呼出）割り込みハンドラ，３２はメモリ獲得処理，３３はメモリ開放処理である。
【００２２】
主記憶領域の割当ての要求がユーザプログラム３０で発生すると，ＯＳ（オペレーティングシステム）とユーザプログラムが共通に参照する固定領域（プリフイックス）３０ａ内のパラメータ域へ当該ユーザプログラムが使用することができる記憶領域のデータを設定する（図６の３０内のＳ１）。この処理はマルチプロセッサで動作する場合に記憶領域が競合しないようにするためである。次にメモリ獲得のＳＶＣを発行する（図６の３０内のＳ２）。これにより，ＳＶＣ割り込みハンドラ３１が駆動され，ＳＶＣコードをデコードする処理が行われ（図６の３１内のＳ７），メモリ獲得処理であるか判別し（同Ｓ８），イエスである場合，メモリ獲得処理に移行する（同Ｓ９）。図６のメモリ獲得処理３２では，固定領域３０ａのパラメータ域からデータを得て（図６の３２内のＳ１２），領域を獲得し（同Ｓ１３），固定領域のパラメータ域へ獲得アドレスを設定し（同Ｓ１４），ＳＶＣ割込みハンドラへ復帰する（同Ｓ１５）。領域の獲得処理は，主記憶管理部により上記図２，図３に示す管理テーブル，ページ位置テーブルを用い，図５に示す方法により行う。また，領域獲得をした後に図４のアドレス管理テーブルへの登録が行われる。
【００２３】
ＳＶＣ割り込みハンドラ３１では，メモリ獲得処理が終了するとユーザプログラムへの復帰が行われ（図６の３１内のＳ１１），ユーザプログラムでは固定領域のパラメータ域のデータをユーザプログラムの領域へ退避し（図６の３０内のＳ３），処理を実施して（同Ｓ４），固定領域のパラメータ域へデータを設定し（同Ｓ５），メモリ開放ＳＶＣを発行する（同Ｓ６）。これにより，ＳＶＣ割り込みハンドラ３１が起動し，ＳＶＣコードをデコードして（図６の３１内のＳ７），デコードの結果がメモリ獲得処理かを判別し（同Ｓ８），ノーであると判別されてメモリ開放処理に移行する（同Ｓ１０）。メモリ開放処理では，固定領域のパラメータ域から獲得時に設定した獲得アドレスのデータを得て（図６の３３のＳ１６），その領域を開放し（同Ｓ１７），ＳＶＣ割り込みハンドラに復帰する（同Ｓ１８）。領域開放の処理も，主記憶管理部において上記図２〜図４に対して未使用状態に戻す制御を行う。ＳＶＣ割り込みハンドラからユーザプログラムへ復帰することで，メモリ開放の処理を終了する。
【００２４】
本発明による管理テーブル，ページ位置テーブルを用いて大容量の主記憶のランニング試験を広範囲について効率的に行うことができる。
【００２５】
図７はランニング試験における領域の獲得と開放の処理フローであり，図８にランニング試験における管理テーブルとページ位置テーブルの関係を示す。
【００２６】
試験プログラムに与える領域は現在の管理テーブルの位置（０〜ｎ）とそれぞれの管理テーブルに対応するページ位置で決定される。最初にループ番号として１を入れ（図７のＳ１），管理テーブルを初期化する（同Ｓ２）。次に現在の管理テーブルの位置をループ番号により決定する（図７のＳ３）。これにより，複数ブロックの中から試験の対象となるブロック番号が決定し，この例では，ループ番号１に対応する管理テーブル１に決定される。続いて全てのページ位置テーブルをループ番号（この時１）で初期化し（図７のＳ４），必要な領域を確保する（同Ｓ５）。必要な領域は，任意に指定することができ，複数の領域（同じ管理テーブル内の連続した複数箇所の領域）を確保する。
【００２７】
続いて，確保された領域について，リード，ライト等の試験を実行し（図７のＳ６），試験で使用した領域を全て開放し（同Ｓ７），対象とした領域についての試験が終了したか判別し（同Ｓ８），終了しない場合はループ番号に１を足し（同Ｓ９），Ｓ３に戻る。これにより，次に管理テーブル２について，対応するページ位置テーブル（ステップＳ４で２に初期化されている）により必要な領域を確保して，試験を行い，以下順番に各管理テーブルについて同様の試験が行われる。そして，試験が終了した時点では全ての領域が開放されているため，現在の管理テーブルの位置とページ位置をループ番号から決定することでループ番号が同一であれば獲得する領域のアドレスも同一となる。
【００２８】
図８は上記のランニング試験の最初の状態を表す。すなわち，上記図７のＳ１によりループ番号が１に設定された，最初のサイクルでは，全てのページ位置テーブル４−０〜４−ｎが１に設定され，管理テーブル２−０〜２−ｎについてもループ番号（最初は１番に設定）により管理テーブル２−１が設定され，この管理テーブル２−１に対応するページ位置テーブル４−１の値１を用いて領域を確保して試験を行う。また，１サイクル毎に全ての領域が初期化されて，各ブロックについてループ番号に応じて管理テーブル，ページ位置テーブルの位置を一意に決めて領域の確保と試験内容も変えて実施することができる。また，試験においてエラーが検出されると，同じループ番号に戻して試験を行うと同じ条件を再現することができる。
【００２９】
（付記１）主記憶を大容量のブロックで分割し，各ブロックに対応してブロックの使用状態を表す管理テーブルであって，対応する前記ブロックを小容量のページ単位に分割して各ページに対しその使用状態を表す１ビットが割当てられた全ページ分のビットが設けられた管理テーブルと，主記憶領域の割当て要求に対し順次異なるブロックを指定して割当てを行う主記憶管理部とを有する主記憶管理装置であって，
前記主記憶管理部は，要求に応じて指定されたブロックに対応する管理テーブルを検索して，使用可能なページ位置と，必要ページ数分の領域を獲得して，該当する管理テーブルのページの各ビットの状態を更新することを特徴とする主記憶管理装置。
【００３０】
（付記２）  付記１に記載の主記憶管理装置は，前記主記憶の各ブロックに対応して設けられた各管理テーブル内の割当て可能なページ位置を格納したページ位置テーブルをさらに有し，前記主記憶管理部は，割当て要求により指定されたブロックに対応する前記ページ位置テーブルを検出して，要求されたページ数分の領域を獲得することを特徴とする主記憶管理装置。
【００３１】
（付記３）付記１または２の何れかにおいて，前記主記憶の割当て要求に応じて記憶領域の割当てを受けると，前記要求を行ったプログラムまたはタスクを表す識別符号と，割当てられたページ位置及びページ数とを含むアドレス管理テーブルを各記憶領域の割当て毎に生成することを特徴とする主記憶管理装置。
【００３２】
（付記４）主記憶を所定の大容量のブロックで分割し，各ブロックに対応してブロックの使用状態を表した管理テーブルを設け，各管理テーブルは，対応する前記ブロックを小容量のページ単位に分割して各ページに対し１ビットの使用状態を割当てた全ページ分のビットが設定され，各管理テーブル内の割当て可能ページの位置を格納したページ位置テーブルを備え，前記主記憶をランニング試験するため，ループ番号を決定し，一意に決定するループ番号から管理テーブルの位置及び管理テーブル内のページ位置テーブルを決定して，割当てアドレスを一意に決定することを特徴とする主記憶管理装置。
【００３３】
【発明の効果】
本発明によればコンピュータシステムでのプログラムの実行領域とデータ領域の割当てと戻しを動的に管理する場合に，割当て領域の偏りを無くし，主記憶を効率良く使用することができる。
【００３４】
また，主記憶の動的管理するために使用する管理のためのテーブルの容量を削減することができる。具体的には，２ＧＢ（ギガバイト）の空間を従来方式（４ＫＢで分割し，各４ＫＢについて１バイトの管理データを設ける）の場合では，２ＧＢ／４ＫＢ＝５１２ＫＢ要するのに対し，本発明によれば，管理テーブルに６４ＫＢ（＝２ＧＢ／４ＫＢ／８Ｂ），ページ位置テーブルに２５６Ｂ（２ＧＢ／１６ＭＢ×２Ｂ），アドレス管理テーブルに６４ＫＢ（８１９２×８バイト）で，合計１２９ＫＢとなり，従来方式に比べて約１／４の削減が可能となる。
【００３５】
更に，本発明により主記憶のランニング試験を実施した場合，管理テーブルや，管理テーブル内のページ位置を一意に決定することが可能となる。
【図面の簡単な説明】
【図１】本発明の原理構成を示す図である。
【図２】主記憶の具体例に対応する管理テーブルの構成例を示す図である。
【図３】管理テーブル内の領域の位置を表すページ位置テーブルの構成例を示す図である。
【図４】割当てアドレスと割当てを受けたタスクの関係を示すアドレス管理テーブルの構成例を示す図である。
【図５】管理テーブルとページ位置テーブルの関係を示す図である。
【図６】主記憶の領域割当て及び解除の処理フローを示す図である。
【図７】ランニング試験における領域の獲得と開放の処理フローを示す図である。
【図８】ランニング試験における管理テーブルとページ位置テーブルの関係を示す図である。
【図９】従来例の説明図である。
【符号の説明】
１          主記憶
1-0 〜1-n   ブロック
2-0 〜2-n   管理テーブル
３          主記憶管理部
３ａ        テーブル検索手段
３ｂ        テーブル設定手段
３ｃ        番号保持部
４          ページ位置テーブル
4-0 〜4-n   ページ位置
５          アドレス管理テーブル
【図１】
0003808693.tif 000002
【図２】
0003808693.tif 000003
【図３】
0003808693.tif 000004
【図４】
0003808693.tif 000005
【図５】
0003808693.tif 000006
【図６】
0003808693.tif 000007
【図７】
0003808693.tif 000008
【図８】
0003808693.tif 000009
【図９】
0003808693.tif 000010