JP4176682B2 - メモリ管理方式 - Google Patents

Description

本発明は，情報処理装置や画像処理装置などのメモリを使用する装置におけるメモリ管理方式に関し，特に，メモリ上の可変長領域に予め確保された所定のデータサイズの複数の固定長メモリ領域からなる固定長メモリブロックの領域を元の可変長領域に変更するメモリ管理方式に関するものである。

従来からメモリを管理する方式として様々な方式が提案，実施されているが，それらの方式は，可変長メモリ管理方式と固定長メモリ管理方式とに大別される。
上記可変長メモリ管理方式では，例えば，ＣＰＵ等によりサイズαのデータの割付要求が出されると，メモリの先頭アドレスから順に上記サイズαのデータを収容し得る空き領域（未使用領域），即ち開放されたメモリ領域があるか否かが探索され（探索処理），この探索結果に基づいて上記割付要求を満たす空き領域があると判断されると，上記空き領域が上記サイズαと残りの空き領域とに分割され（領域分割処理），その後，上記サイズαの空き領域にデータが割り付けられる。また，割り付けられたデータの開放要求が出されると，ＣＰＵ等により指定されたメモリアドレスの割付領域内のデータが消去された後に開放された領域の前後のメモリ領域の使用状況を確認して，隣接する空き領域があれば複数の空き領域を併合する処理（領域併合処理）が行われる。
このように，可変長メモリ管理方式によれば，データを収容し得る空き領域さえ存在しておれば，任意のサイズのメモリ割り付けが要求されたサイズどおりに行えるため，メモリ内に無駄なメモリ領域が生じ難い。従って，効率よくメモリ領域を使用することができる。しかし，その反面，割り付け時に行われる空き領域の上記探索処理或いは上記領域分割処理等の前処理や，開放時に行われる上記領域併合処理や空き領域のチェーン処理等の後処理が付随することになるため，メモリ管理における各処理の速度が遅くなる。特に，メモリの末端アドレス部分ほど前記した割付時探索処理に時間がかかり，処理速度が極端に落ちる傾向にある。
一方，上記固定長メモリ管理方式では，メモリ領域を所定のサイズの複数のメモリセル（固定長メモリ領域と同義）に区切り，上記メモリセル単位でメモリが管理される。そのため，メモリ領域の割り付けや開放が高速に行えるという利点がある。しかし，上記メモリセルのサイズを大きくするほど，管理されるメモリセルの数が減って処理速度は上がるが，上記メモリセルにデータが割り付けられたときの上記メモリセルにおける端数が拡大するため，上記メモリセル内に使用することのできない無駄なメモリ領域が生じ，メモリの使用効率が悪くなるという問題がある。

そこで，特許文献１に示すように，メモリを所定のデータサイズからなる複数の固定長のメモリセルに分割して，固定長メモリ管理方式の利点を生かしつつ，可変長領域の割付，開放要求に対しては，各メモリセルの使用状況を「０」又は「１」のビット値として記録するビットマップを管理用データとして設けて，このビットマップを管理してメモリの可変長の割付，開放を行うことにより，従来の可変長メモリ管理方式の問題を低減させるメモリ管理方法が提案されている。
特開平８−２２１８１７号公報

しかしながら，特許文献１に提案されるメモリ管理方式は，固定長の複数のメモリセルを使用して可変長データに対応するものであるため，以下の（１）〜（３）に記載する問題があった。
（１）一の可変長データに対して，連続するメモリセルを割り付ける必要があるため，メモリセルの割り付けと開放が繰り返された場合は，未使用のメモリセルが動的メモリ領域内に分散して，連続した未使用のメモリセルが減少することになり却ってメモリの使用効率が低下する。
（２）固定長のメモリセルを使用するため，可変長データに対しては従来と同様に，メモリセルのサイズ以下の割り付け要求が発生した場合に，割り付けられた複数のメモリセルの最後のメモリセルに，無駄な割り付け端数が発生するため，メモリの使用効率が低下する。
（３）メモリ内に，実データ以外の前記ビットマップ等のデータを格納しておく必要があるため，メモリ管理領域内における実データの記憶管理領域が相対的に減少する。

上述した特許文献１のメモリ管理方式が有する上記各問題は，以下のメモリ管理方式Ｘにより解決され得る。即ち，所定サイズのデータの割付，開放要求がなされたときに，前記可変長メモリ管理方式により管理される可変長メモリ上の可変長メモリ領域に複数の固定長メモリ領域（固定長のメモリセルと同義）からなる固定長メモリブロックを確保して，該確保された固定長メモリブロック内の複数の固定長メモリ領域に対して上記所定サイズのデータの割付，開放を行い，上記固定長メモリブロック内の複数の固定長メモリ領域が全て開放されたときには，該固定長メモリブロックを元の可変長メモリ領域に変更するメモリ管理方式Ｘを採用することにより，上記各問題を生じさせずに，メモリ領域を有効に使用することが可能となる。なお，上記メモリ管理方式Ｘの詳細については，後段の発明の詳細な説明の欄で説明する。
しかし，上記メモリ管理方式Ｘを用いて上記固定長メモリブロックを元の可変長領域に変更する場合，以下の問題が生じるおそれがある。例えば，上記固定長メモリブロック内の複数の固定長メモリ領域が全て開放されたために上記固定長メモリブロックを元の可変長領域に変更する処理が行われ，その直後に上記所定サイズのデータの割付要求がなされた場合は，上記固定長メモリブロックを新たに再確保する処理が行われる。そのため，固定長メモリ領域への割付，開放が連続して行われた場合に，上記変更処理，確保処理が繰り返し行われることになる。このように変更処理，確保処理が繰り返し行われると，上記固定長メモリブロックのサイズは単純に割付，開放されるメモリ領域のサイズと較べて格段に大きいため，上記変更処理や確保処理を実行するＣＰＵやメモリコントローラ等の負担が増大するという問題がある。
そこで，本発明は上記事情に鑑みてなされたものであり，その目的とするところは，一旦，可変長メモリ領域に確保された固定長メモリブロックの領域を元の可変長領域に変更する際に生じ得る処理負担の大きい繰り返し処理を排除してメモリの割付及び開放処理を高速に行い，且つ，メモリ内に使用することができない未使用領域を生じさせずに使用効率のよいメモリ管理方式を提供することにある。

上記目的を達成するために本発明は，メモリ上の可変長領域に予め確保された所定のデータサイズの複数の固定長メモリ領域からなる固定長メモリブロックの領域を元の可変長領域に変更するメモリ管理方式において，上記メモリ上の可変長領域に二以上の上記固定長メモリブロックが確保されている場合に，上記確保された二以上の上記固定長メモリブロックのうちの少なくとも二以上の固定長メモリブロック内の全ての上記固定長メモリ領域が開放されたことを条件に，該固定長メモリ領域が全て開放された二以上の固定長メモリブロックのうちのいずれか一つの固定長メモリブロック全体の領域を元の可変長領域に変更し，上記固定長メモリ領域が全て開放された上記固定長メモリブロックが一つである場合には該固定長メモリブロックを元の可変長領域に変更しないことを特徴とするメモリ管理方式として構成されている。
また，上記固定長ブロックの固定長メモリ領域の割り付け・開放に伴ってチェーンの張り替えを実行することにより該固定長メモリ領域がチェーン管理される構成では，上記メモリ上の可変長領域に二以上の上記固定長メモリブロックが確保されている場合に，上記可変長領域に確保された二以上の上記固定長メモリブロックのいずれか一つの固定長メモリブロック内の上記固定長メモリ領域が全て開放されたとき，該一つの固定長メモリブロックの他に上記固定長メモリ領域が全て開放された上記固定長メモリブロックが存在しない場合には該一つの固定長メモリブロックの固定長メモリ領域を元の可変長領域に変更せず，該一つの固定長メモリブロックの他に上記固定長メモリ領域が全て開放された上記固定長メモリブロックが存在する場合には該一つの固定長メモリブロックの固定長メモリ領域をチェーンの張り替えの実行前に元の可変長領域に変更することが望ましい。

以上説明したように，本発明は，メモリ上の可変長領域に所定のデータサイズの複数の固定長メモリ領域からなる固定長メモリブロックが予め二以上確保されている場合に，上記確保された二以上の上記固定長メモリブロックのうちの少なくとも二以上の固定長メモリブロック内の全ての上記固定長メモリ領域が開放されたことを条件に，該固定長メモリ領域が全て開放された二以上の固定長メモリブロックのうちのいずれか一つの固定長メモリブロック全体の領域を元の可変長領域に変更し，上記固定長メモリ領域が全て開放された上記固定長メモリブロックが一つである場合には該固定長メモリブロックを元の可変長領域に変更しないよう構成されているため，一旦確保された一つの固定長メモリブロック内の全ての固定長メモリ領域が開放された場合であっても，上記固定長メモリ領域が全て開放された上記固定長メモリブロックが一つである場合には上記一つの固定長メモリブロックは元の可変長領域に変更されず，全ての固定長メモリ領域が開放された固定長メモリブロックが二以上存在する場合に初めて上記固定長メモリブロックが一つだけ元の可変長領域に変更される。そのため，新たに固定長メモリ領域に対するデータの割付要求がなされたとしても，未使用の（空の）固定長メモリブロックが既に存在し，該固定長メモリブロックを再確保する必要が無いため，メモリ管理における割付及び開放処理の負担が軽減されるだけでなく，総合的に高速な割付，開放処理が実現され得る。
また，上記固定長ブロックの固定長メモリ領域の割り付け・開放に伴ってチェーンの張り替えを実行することにより該固定長メモリ領域がチェーン管理される構成では，上記メモリ上の可変長領域に二以上の上記固定長メモリブロックが確保されている場合に，上記可変長領域に確保された二以上の上記固定長メモリブロックのいずれか一つの固定長メモリブロック内の上記固定長メモリ領域が全て開放されたとき，該一つの固定長メモリブロックの他に上記固定長メモリ領域が全て開放された上記固定長メモリブロックが存在しない場合には該一つの固定長メモリブロックの固定長メモリ領域を元の可変長領域に変更せず，該一つの固定長メモリブロックの他に上記固定長メモリ領域が全て開放された上記固定長メモリブロックが存在する場合には該一つの固定長メモリブロックの固定長メモリ領域をチェーンの張り替えの実行前に元の可変長領域に変更するように構成することにより，該一つの固定長メモリブロックに対してのチェーンの張り替えのための処理負担が軽減される。

以下添付図面を参照しながら，本発明の実施の形態について説明し，本発明の理解に供する。尚，以下の実施の形態は，本発明を具体化した一例であって，本発明の技術的範囲を限定する性格のものではない。
ここに，図１は本発明のメモリ管理方式Ｘを実現するためのハードウェア構成を示すブロック図，図２は図１の管理領域６内に作成され，本発明のメモリ管理方式Ｘに係わる固定長メモリ領域の管理テーブルの内容を示すテーブル図，図３は図１の実データ領域７にデータが順次割り付けられたときの実データ領域７の状態を示す模式図，図４はメモリ管理手段４によって図３で示した可変長データや固定長データが割り付けられる概略手順を説明するフローチャート，図５は固定長メモリブロックの領域ＢＢ１を作成する手順を説明する模式図，図６は固定長メモリブロックの領域ＢＢ１内の固定長メモリ領域を割り付ける手順を説明する模式図，図７はメモリアドレス６１１番地の固定長メモリ領域１１を割り付けた後の後処理を説明するための模式図，図８は図１の実データ領域７に作成された３つの固定長メモリブロック領域ＢＢ１〜ＢＢ３のうちの固定長メモリブロックＢＢ３内の先頭アドレス７１１の固定長メモリ領域１１を開放する手順を説明するための模式図，図９は図１の実データ領域７に確保された固定長メモリブロック領域が可変長領域に変更されるときの実データ領域７の状態を示す模式図，図１０は図７に示すメモリアドレス６１２番地の固定長メモリ領域１１が開放された場合の新たなポインタとチェーンを示す図，図１１はメモリ管理手段４によって固定長データの格納領域として割り付けられた固定長メモリ領域を開放する概略手順を説明するフローチャートである。

まず，図１のブロック図を用いて本実施形態に係るメモリ管理方式Ｘについて具体的に説明する。図１は，本発明のハードウェア構成図であり，ＣＰＵ１によって制御が行われるＯＳ２上でプログラム３が稼働している例を示す。プログラム３やＯＳ２によってメモリを必要とするジョブが発生すると，その要求はＣＰＵ１に送られて，ＣＰＵ１からメモリ管理手段４にメモリ要求（割付要求，開放要求）として送出される。メモリ管理手段４は，例えば，従来周知のメモリコントローラ等により構成されている。このメモリ管理手段４は，上記ＣＰＵ１からのメモリ要求を受けてメモリ５の実データ領域７内に，要求されたメモリサイズの領域の割付，開放を実行する。その場合，前処理の一例である実データ領域７内における空き領域の探索処理を実行するため，メモリ５内に設けられた管理領域６で管理されている実データ領域７のメモリ使用状況に関する管理情報（管理テーブル）が上記メモリ管理手段４によって参照される。

本メモリ管理方式Ｘでは，メモリ５の管理を，可変長メモリ管理方式に基づいて行っているため，メモリに対する割付，開放要求がＣＰＵ１から発行された場合は，従来の可変長メモリ方式によって管理領域６に管理用のデータを作成し，実データ領域７のメモリ使用状況を管理する。即ち，上記実データ領域７は全域可変長メモリ領域である。従って，上記メモリ５の可変長メモリ管理を行うためのメモリ管理手段４及び管理領域６の動作と構成については従来の技術を使用して実現可能であり，その説明は省略する。

ここで，上記メモリ５の可変長メモリ管理を行う中で，本発明のメモリ管理方式Ｘにおける特異な点を図２及び図３を参照して説明する。図２は，本発明のメモリ管理方式Ｘに係わる固定長メモリ領域の管理テーブルの内容を示すテーブル図である。特に，情報処理装置や入出力装置，或いは画像処理装置などでデータ処理が行われる場合，ある特定の固定データサイズのデータが頻繁に処理されることがある。例えば，固定データサイズの入出力バッファを介して転送されて処理されるデータは２５６バイトや１０２４バイトなどのように固定長である。また，画像処理の場合は，１ラインごとに固定長のデータを処理することも行われている。

このように，頻繁に処理される固定データサイズは，装置の種類によって決まっている場合が多いため，そのサイズのデータを後述する固定長メモリブロックの領域内で固定長として処理することで可変長メモリ管理方式に伴う従来の問題点を改善するとともに，可変長メモリ管理方式に適したデータは可変長で処理することで固定長メモリ管理方式に伴う従来の問題点を改善することができる。

ここで，本発明のメモリ管理方式Ｘが利用される画像処理装置や情報処理装置等の装置において，１０２４バイトと２５６バイトの固定長データが頻繁に処理される場合を想定して上記メモリ管理方式Ｘについて説明する。図２に示される固定長メモリ領域の管理テーブル１０は，管理領域６内に設けられ，固定長としてメモリ管理が行われるデータの「固定データサイズ」と，可変長データ領域として作成された領域内に存在する上記固定データサイズと同一サイズ（所定のデータサイズに相当）の固定長メモリ領域の「総数」と，複数の上記固定長メモリ領域のうちの未使用，未割り付けになっている空き固定長メモリ領域の「空き個数」と，最初の空き固定長メモリ領域のアドレスを指す「先頭アドレス」とを管理している。なお，上記管理データ１０で管理される要素を上記各要素に限定する趣旨ではない。以下の例では，１０２４バイトと２５６バイトそれぞれの固定長データに対して管理が行われるものとする。

図２に示す例では，固定データサイズ１０２４バイトに関しては，総数欄に３２が示されているので，１０２４バイトの固定長メモリ領域３２個からなる固定長メモリブロック領域を実データ領域７（図１）内に作成することが可能であることを意味し，空き個数欄と先頭アドレス欄はそれぞれ，１０進数表示で“０”を示しているため，上記固定長メモリブロックはまだ作成されていないことを意味する。２５６バイトの固定長メモリ領域についても同様であるが，総数欄に６４が示されているため，６４個の固定長メモリ領域からなる固定長メモリブロック領域が作成可能である。尚，詳細は後述するが，空き個数欄と先頭アドレス欄とがともに“０”表示でない場合は，固定長データが割り付けられる固定長メモリブロック領域は既に作成されていることを意味する。

次に，図３と図４を使用して，可変長メモリ管理方式を使用しながら特定の固定データサイズのデータに対して上記メモリ管理手段４（図１）が固定長メモリ管理を行う手順の概要を説明する。図３は，上記実データ領域７（図１）にデータが順次割り付けられたときの実データ領域７の状態を示す模式図であって，（ａ）は実データ領域７全てが空き領域Ａとなっている状態を示し，（ｂ）は可変長データの割り付け要求があり，その要求に基づいて，空き領域Ａの中に，つまり空き領域Ａを分割して，可変長データ領域ＡＡの割り付けと空き領域Ｂを確保している状態を示す。

また，図３（ｃ）は，実データ領域７が図３（ｂ）の状態となった後に，予め管理テーブル１０に登録されている１０２４バイトの固定長データの割り付けの要求を受け，それを割り付ける領域が存在しない場合に，空き領域Ｂを二分して，１０２４バイト×３２個の領域を固定長メモリブロックの領域ＢＢ１として作成し，残りを空き領域Ｃとして確保したときの実データ領域７の状態を示し，図３（ｄ）は，その後，予め管理テーブル１０に登録されている２５６バイトの固定長データのメモリ割り付け要求を受け，それを割り付ける領域が存在しない場合に，空き領域Ｃを二分して，２５６バイト×６４個の領域を固定長メモリブロックの領域ＣＣとして割り付け，残りを空き領域Ｄとして確保したときの実データ領域７の状態を示す。尚，固定長メモリブロックの領域ＢＢ１及びＣＣは，それぞれ領域としては可変長メモリ管理方式によって管理されている。

図４は，図３で示した可変長データ領域ＡＡや固定長メモリブロック領域ＢＢ１或いはＣＣが上記メモリ管理手段４（図１）によって割り付けられる概略手順を示すフローチャートである。図中のＳ１，Ｓ２，…は処理手順番号（ステップ番号）を示す。処理はＳ１から開始される。
いま，Ｓ１で，ＣＰＵ１から，あるサイズのメモリの割り付け要求がメモリ管理手段４に出されると，Ｓ２では，メモリ管理手段４により管理テーブル１０（図２）が検索され，要求された割付サイズが本メモリ管理方式Ｘによるメモリ管理を行う固定データサイズとして登録されているか否かが判断される。Ｓ３での判断が行われ，割り付け要求がなされたデータのサイズが登録されていない場合は，Ｓ８に分岐して通常の可変長メモリ管理方式に基づいて，可変長データ領域（例えば可変長データ領域ＡＡ）が実データ領域７内に確保される（図３（ｂ）参照）。

Ｓ３で，割り付け要求がなされたデータのサイズが本発明によるメモリ管理を行う固定データサイズ（例えば１０２４バイト）として登録されていると判断された場合は，その後，処理手順はＳ４に移行する。Ｓ４では，既にそのサイズの固定長メモリブロック領域が既に作成されているか否か，即ち，メモリ５内に要求された上記固定データサイズに対応する固定長メモリブロック領域が存在するか否かが判断される。この判断は，管理テーブル１０内の空き個数と先頭アドレスの値に基づいて行われる。即ち，上記空き個数と先頭アドレスの欄に“０”以外の数値が書き込まれている場合は，固定長メモリブロック領域が存在すると判断され，“０”が書き込まれている場合は固定長メモリブロック領域が存在すると判断される。Ｓ４で，図３（ｃ）に示すように，固定長メモリブロックＢＢ１が既に作成されていると判断された場合は，Ｓ６に移行する。また，まだ作成されていないと判断された場合は，Ｓ５に分岐して固定長メモリブロック領域ＢＢ１（図３（ｃ）参照）を作成した後にＳ６に移行する。

Ｓ６では，既に存在する固定長メモリブロック領域ＢＢ１，或いはＳ５で新たに作成された固定長メモリブロック領域ＢＢ１において，管理テーブル１０に記憶されている先頭アドレスから始まる固定長メモリ領域が，要求されたデータのメモリ格納領域として割り付けられる。この固定長メモリ領域の割り付けによって，固定長メモリブロック領域ＢＢ１内の空き固定長メモリ領域の空き個数と先頭アドレスが変動することになる。そのため，後述するＳ７においてチェーンの張り替えが行われ，管理テーブル１０の空き個数及び先頭アドレスと同時に，空き固定長メモリ領域の状態情報が最新状態に更新される。また，フローチャートに図示しないが，割り付け要求が処理されて固定長メモリ領域が割り付けられると，割り付けられたメモリ領域のアドレスがメモリ管理手段４から要求元のＣＰＵ１に戻されて割り付け処理が完了する。

次に，図４のＳ５による手順，すなわち，管理テーブル１０に登録されている固定データサイズの固定長メモリブロック領域ＢＢ１が，まだ作成されていない場合の作成手順についての詳細を，図５を参照して説明する。ここに，図５は，固定長メモリブロック領域ＢＢ１を作成する手順を説明する模式図であり，（ａ）は管理テーブル１０の内容を示し，（ｂ）は図３（ｃ）で示した固定長メモリブロック領域ＢＢ１とその内容の詳細を示す。

図５（ａ）は，図２で示した管理テーブル１０の一部であって，固定データサイズが１０２４バイトの固定長データが３２個作成可能であることを示しており，固定長メモリブロック領域ＢＢ１が作成されるまでは，空き個数欄は“０”が表示され，先頭アドレス欄にも“０”が表示される。１０２４バイトのメモリ割り付け要求を受け取ったメモリ管理手段４（図１）は，１０２４サイズが管理テーブル１０に登録されており（Ｓ３のＹｅｓ側），且つそのサイズ（１０２４バイト）に対応する固定長メモリブロック領域ＢＢ１が存在しないと判断した場合は（Ｓ４のＮｏ側），図３（ｂ）の空き領域Ｂ内に，３２個の１０２４バイトの固定長メモリ領域１１からなる固定長メモリブロックの領域ＢＢ１を作成（確保）する。上記各固定長メモリ領域１１のメモリアドレスは，１０進数で表現すると，例えば先頭の６１１番地から始まり最後の固定長メモリ領域１１は６４２番地で終わる。尚，ここでいう番地（６１１番地〜６４２番地）は，本実施形態を容易に説明するための番地であり，１０２４バイトごとに付与した番地で，実際のメモリアドレスとは異なる。実際のアドレスとしては，メモリ５の物理アドレスや論理アドレス空間を絶対アドレス或いは相対アドレスで表したものなどが使用される。

そして，それぞれの固定長メモリ領域１１は空き状態なので，管理テーブル１０の先頭アドレスの欄には，空いている最初の固定長メモリ領域１１のアドレス６１１番地が書き込まれる。つまり，管理テーブル１０の先頭アドレスの欄は，最初の空き固定長メモリ領域１１を指している。
現時点では，全ての固定長メモリ領域１１は未使用状態（空き状態）である。そのため，最初のアドレス６１１番地の固定長メモリ領域１１には，次の空いている固定長メモリ領域１１のアドレス，すなわち，６１２番地が書き込まれ，同様にして，６１２番地の固定長メモリ領域１１内には６１３番地が書き込まれる。つまり，ｎ番目の空き固定長メモリ領域１１内にはｎ＋１番目の空き固定長メモリ領域１１を指すアドレスが書き込まれることになる。そして，最後の６４２番地の固定長メモリ領域１１は次に指し示す空き固定長メモリ領域がないため，“０”が書き込まれる。このようにして，空き領域に次の空き領域のアドレスが書き込まれることにより，管理テーブル１０の先頭アドレスの欄に書き込まれた次の番地を示すアドレス（ポインタ）を順番にたどっていけば，全ての空き固定長メモリ領域１１が順番に繋がるチェーンが完成する。上記チェーンの終端は，ポインタとして“０”を持つ固定長メモリ領域１１である。
その後，管理テーブル１０の空き個数欄に，空き固定長メモリ領域１１の個数（現時点では３２個）が書き込まれる。
このようなＳ５（図４）の手順を踏むことにより，固定長メモリブロック領域ＢＢ１が作成される。
なお，その後，図４のＳ６の割り付けが行われることにより，６１１番地の空き固定長メモリ領域１１がデータの格納領域として割り付けられるため，後述するＳ７のチェーン張り替え時に，上記管理テーブル１０の空き個数欄が３１個に書き換えられる。その後，ＣＰＵ１（図１）からの要求に応じて，メモリ管理手段４（図１）により６１１番地にデータが書き込まれる。

続いて，既に，固定長メモリブロック領域ＢＢ１が作成されている場合，即ち図４のＳ４で固定長メモリブロック領域がある（Ｓ４のＹｅｓ側）と判断された後のＳ６の手順について，図６と図７を参照して具体的に説明する。図６は，固定長メモリブロック領域ＢＢ１内の固定長メモリ領域１１を割り付ける手順を説明する模式図であり，（ａ）は管理テーブル１０の内容を示し，（ｂ）は図３（ｃ）で示した固定長メモリブロック領域ＢＢ１の詳細を示す。

図６（ａ）の管理テーブル１０には，固定データサイズが１０２４バイトの固定長データの固定長メモリ領域１１が３２個作成されており，そのうち１０個が空いており，先頭の空き固定長メモリ領域１１を示す先頭アドレスは６１１番地であることが示されている。図４のフローチャートに基づいて説明したように，１０２４バイトのメモリ割り付け要求をメモリ管理手段４（図１）が受けると，常に，管理テーブル１０の先頭アドレス欄に書き込まれているアドレスが指す最初の空き固定長メモリ領域１１，つまりこの例では６１１番地の固定長メモリ領域１１がデータの格納領域として割り付けられる。

次に，図７の模式図を用いて，６１１番地の固定長メモリ領域１１を割り付けた後の，後処理の一例であるポインタとチェーンの張り替え手順（図４のＳ７）について説明する。図６で示されている６１１番地の固定長メモリ領域１１が割り付けられると，図７では，その６１１番地の固定長メモリ領域１１内にそれまで書き込まれていたポインタ（６１３番地）が，図７（ａ）に示される管理テーブル１０の先頭アドレス欄に書き込まれる。即ち，先頭アドレス欄に示すポインタが６１１番地から６１３番地に書き換えられる。図６と図７を比較すると分かるように，６１３番地以降の空き固定長メモリ領域１１内に書き込まれているポインタ（次の空き領域を示すアドレス）は変更されない。アドレス６１１番地の固定長メモリ領域１１内にそれまで書き込まれていたポインタは，書き込まれるデータによって消失するが，そのポインタはデータによって消失する前に管理テーブル１０の先頭アドレス欄に転記される。このとき，管理テーブル１０の空き個数が１つ減るため，空き個数の総数表示が１０個から９個に書き換えられる。このようにして図４のＳ６の割り付けが行われた後のポインタとチェーンの張り替えが行われる。

続いて，図８〜図１０を参照しながら，図１１のフローチャートを用いて，上記メモリ管理手段４によってデータの格納領域として割り付けられた固定長メモリ領域を開放する概略手順について説明する。ここに，図８は，メモリ５の実データ領域７に作成された３つの固定長メモリブロック領域ＢＢ１〜ＢＢ３のうちの固定長メモリブロックＢＢ３内の先頭アドレス７１１の固定長メモリ領域１１を開放する手順を説明するための模式図であり，（ａ）は管理テーブル１０の内容を示し，（ｂ）は固定長メモリブロック領域ＢＢ３とその内容の詳細を示す。なお，図８（ａ）は，図２で示した管理テーブル１０の一部であって，固定データサイズが１０２４バイトの固定長データが３２個作成可能であることを示す。また，図８（ｂ）に示すように，固定長メモリブロックＢＢ３（アドレス７１１〜７４２番地で構成）は，アドレス７１１の固定長メモリ領域１１のみが使用中であり，他の３１個の固定長メモリ領域は空き状態となっている。また，図９は，図１の実データ領域７に確保された固定長メモリブロック領域が可変長領域に変更されるときの実データ領域７の状態を示す模式図である。
まず，Ｓ１１で，ＣＰＵ１から上記メモリ管理手段４（図１）に対してアドレス７１１を指定して，固定長メモリブロックＢＢ３内のアドレス７１１の固定長メモリ領域１１を開放する開放要求が出されると，Ｓ１２では，指定されたアドレス７１１の固定長メモリ領域１１が開放される。その後，Ｓ１３において，固定長メモリブロックＢＢ３内の全ての固定長メモリ領域１１が開放されたか否か，即ち，固定長メモリブロックＢＢ３内の全ての固定長メモリ領域１１が空き状態（未使用）であるか否かが判断される。かかる判断は，開放を行なう前後における図８（ａ）の管理テーブルの空き個数の欄の数値に基づいて行われる。この例では，固定長メモリブロックＢＢ３のアドレス７１１の固定長メモリ領域１１のみが使用中であったため，この固定長メモリ領域１１が開放されることにより，固定長メモリブロックＢＢ３内の全ての固定長メモリ領域が開放されたと判断されて，処理はＳ１４に移行する。なお，ステップＳ１３の判断でＮｏと判断された場合は，Ｓ１６に移行して，後述するチェーンの張り替えが行われる。

Ｓ１３で全ての固定長メモリ領域１１が開放されたと判断されると，その後，Ｓ１４において，実データ領域７内に，全ての固定長メモリ領域１１が開放された固定長メモリブロックが二以上存在するかどうかが判断される。例えば，図９（ａ）及び（ｂ）に示すように，固定長メモリ領域が全て開放されている状態で実データ領域７に確保された固定長メモリブロックＢＢ２が存在している場合に，上記Ｓ１３で固定長メモリブロックＢＢ３内の全ての固定長メモリ領域が開放されたと判断された場合は，固定長メモリ領域が全て開放されている二つの固定長メモリブロックＢＢ２，ＢＢ３が存在することになるので，この場合は，処理はＳ１５に移行する。また，全ての固定長メモリ領域が開放された固定長メモリブロックが二以上存在しない場合は，処理はＳ１６に移行する。
Ｓ１５では，上記固定長メモリブロックＢＢ２又はＢＢ３のいずれかが可変長メモリ領域に変更される。即ち，固定長メモリ領域を割り付けるために確保していた固定長メモリブロックの領域が元の可変長メモリ領域に復元される。図９（ｃ）に変更後の実データ領域７の状態を示す。なお，可変長メモリ領域に変更される領域は上記固定長メモリブロックＢＢ２又はＢＢ３のいずれであってもかまわないが，先に固定長メモリ領域が全て開放されていた上記固定長メモリブロックＢＢ２では既にチェーンの張り替えが行われているため，上記固定長メモリブロックＢＢ３を可変長メモリ領域に変更することが望ましい。このほうが，固定長メモリブロックＢＢ３に対してチェーンの張り替えを行う必要が無いため，その分，処理負担が軽減される。

ところで，固定長メモリ領域が全て開放された場合は，すぐに固定長メモリブロックの領域を元の可変長メモリ領域に変更することも考えられるが，例えば，上記固定長メモリブロックＢＢ３内の複数の固定長メモリ領域が全て開放され，上記固定長メモリブロックＢＢ３が元の可変長領域に変更された直後に，固定データサイズのデータの割付要求がなされた場合は，再度，複数の固定長メモリ領域からなる固定長メモリブロックＢＢ３を新たに確保する必要が生じる。このようなことが繰り返し行われると，上記固定長メモリブロックＢＢ３のサイズは非常に大きいため，可変長領域への変更や固定長メモリブロックの再確保にかかる処理負担が増大するという問題がある。そのため，本メモリ管理方式Ｘでは，他のメモリ管理方式とは異なり，固定長メモリブロックＢＢ２内の全ての固定長メモリ領域が開放されたとしても他にそのような固定長メモリブロックが存在しない場合は上記固定長メモリブロックＢＢ２を可変長メモリ領域に変更せずに残しておき，上記固定長メモリブロックＢＢ３の固定長メモリ領域が全て開放されることによって，固定長メモリ領域が全て開放されていた上記固定長メモリブロックが二以上存在する場合にのみ，一つの上記固定長メモリブロックを可変長領域に変更することとした。これにより，実データ領域７（図１）内に，固定長メモリ領域が全て開放された上記固定長メモリブロックが少なくとも一つ存在することになるため，上述した処理負担が増大するという問題が発生することがなくなり，メモリの使用効率が向上され得る。

上記Ｓ１３或いはＳ１４でＮｏと判断されて処理がＳ１６に移行すると，このＳ１６では，ＣＰＵ１により指定されたアドレスの固定長メモリ領域が開放された後のチェーンの張り替えが行われる。ここで，図１０を用いて，それまで使用中であった固定長メモリブロックＢＢ１（図７参照）に示す６１２番の固定長メモリ領域１１が開放された場合のポインタとチェーンの張り替え手順について説明する。図１０は，図７に示す６１２番の固定長メモリ領域１１が開放された場合の新たなポインタとチェーンを示す図である。メモリ管理手段４によって６１２番地の固定長メモリ領域１１が開放されると，それまで図１０（ａ）に示す管理テーブル１０の先頭アドレス欄に書き込まれていたポインタが，６１３番地から６１２番地に書き換えられる。つまり。管理テーブル１０の先頭アドレス欄のポインタとして，開放された固定長メモリ領域１１（６１２番地）のアドレスが書き込まれる。そして，それまでの先頭アドレス欄に記憶されていた６１３番地が，開放された６１２番地の固定長メモリ領域１１にポインタとして書き込まれる。

以上説明したように，ＣＰＵ１からメモリ割り付け要求を受けると，管理テーブル１０の先頭アドレス欄に書き込まれているアドレス（ポインタ）を通知するだけで，メモリ割り付けの前処理が完了し，メモリ管理の高速化が図れる。
また，固定長メモリ領域１１がデータの格納領域として割り付けられると，その後の処理としては，管理テーブル１０の先頭アドレス欄に，割り付けられた固定長メモリ領域１１が有していたポインタを転記するだけの１つの動作ですむ。また，固定長メモリ領域１１が開放されると，後処理として，開放された固定長メモリ領域１１のアドレスを，管理テーブル１０の先頭アドレス欄にポインタとして書き込むことと，開放された固定長メモリ領域１１に，それまで管理テーブル１０の先頭アドレス欄が有していたポインタを転記することの２つの動作ですむ。つまり，チェーンの最初のポインタ，或いは最初と２番目のポインタを変更するのみで，空き固定長メモリ領域１１を繋いで示すチェーンの張り替えが完了することになり，更にメモリ管理の高速化が図れる。

なお，図示して説明しないが，図３（ｄ）で示した２５６バイトの固定長メモリブロック領域ＣＣも，これまで説明した固定長メモリブロック領域ＢＢ１〜ＢＢ３と同様な手順で管理される。
また，これまで，可変長メモリ管理方式によって１０２４バイトや２５６バイトの固定長メモリブロック領域ＢＢ１等やＣＣが管理され，更に，その固定長メモリブロック領域ＢＢ１内やＣＣ内では，空き固定長メモリ領域をポインタでチェーン管理することを具体的な例をあげて説明したが，本発明はこうした例や数値に限定されないことは言うまでもない。
また，１０２４バイトや２５６バイトの固定長は，本発明が実施される装置によって変わるものであり，例えば２０４８バイトや５１２バイト，或いはその他の固定データサイズであってもよい。更に，これらの固定データサイズは，本発明が実施される装置で頻繁にメモリ割り付け要求が出されるサイズに設定するとよい。そうすると，従来の固定長メモリ管理方式のように，要求されるサイズとの間に端数が発生してメモリの使用効率が低下することもない。

以上の実施例を分かり易く説明するために，メモリ５，及び管理領域６と実データ領域７を物理メモリとし，実際のアドレスを具体的な番地で示したが，本発明は，物理メモリとともに論理メモリにも適用できることは勿論のこと，メモリに限らず，ハードディスク，ＣＤ−ＲＷ，ＤＶＤ−ＲＷ，ＤＶＤ−ＲＡＭ，ＭＯ，ＭＤなどの書き換え可能な記録媒体にも適用可能である。

本発明のメモリ管理方式Ｘを実現するためのハードウェア構成を示すブロック図。 図１の管理領域６内に作成され，本発明のメモリ管理方式Ｘに係わる固定長メモリ領域の管理テーブルの内容を示すテーブル図。 図１の実データ領域７にデータが順次割り付けられたときの実データ領域７の状態を示す模式図。 メモリ管理手段４によって図３で示した可変長データや固定長データが割り付けられる概略手順を説明するフローチャート。 固定長メモリブロックの領域ＢＢ１を作成する手順を説明する模式図であり，（ａ）は管理テーブル１０の内容，（ｂ）は図３（ｃ）で示した固定長メモリブロックの領域ＢＢ１とその内容の詳細を示す。 固定長メモリブロックの領域ＢＢ１内の固定長メモリ領域を割り付ける手順を説明する模式図であり，（ａ）は管理テーブル１０の内容，（ｂ）は図３（ｃ）で示した固定長メモリブロックの領域ＢＢ１の詳細を示す。 メモリアドレス６１１番地の固定長メモリ領域１１を割り付けた後の後処理を説明するための模式図。 図１の実データ領域７に作成された３つの固定長メモリブロック領域ＢＢ１〜ＢＢ３のうちの固定長メモリブロックＢＢ３内の先頭アドレス７１１の固定長メモリ領域１１を開放する手順を説明するための模式図。 図１の実データ領域７に確保された固定長メモリブロック領域が可変長領域に変更されるときの実データ領域７の状態を示す模式図。 図７に示すメモリアドレス６１２番地の固定長メモリ領域１１が開放された場合の新たなポインタとチェーンを示す図。 メモリ管理手段４によって固定長データの格納領域として割り付けられた固定長メモリ領域を開放する概略手順を説明するフローチャート。

符号の説明

１…ＣＰＵ
２…ＯＳ
３…プログラム
４…メモリ管理手段
５…メモリ
６…管理領域
７…実データ領域
１０…管理テーブル
１１…固定長メモリ領域
Ａ，Ｂ，Ｃ，Ｄ… 空き領域
ＡＡ…可変長データ領域
ＢＢ，ＢＢ１，ＢＢ２，ＣＣ…固定長メモリブロック領域

Claims (2)

1. メモリ上の可変長領域に予め確保された所定のデータサイズの複数の固定長メモリ領域からなる固定長メモリブロックの領域を元の可変長領域に変更するメモリ管理方式において，
   上記メモリ上の可変長領域に二以上の上記固定長メモリブロックが確保されている場合に，上記確保された二以上の上記固定長メモリブロックのうちの少なくとも二以上の固定長メモリブロック内の全ての上記固定長メモリ領域が開放されたことを条件に，該固定長メモリ領域が全て開放された二以上の固定長メモリブロックのうちのいずれか一つの固定長メモリブロック全体の領域を元の可変長領域に変更し，上記固定長メモリ領域が全て開放された上記固定長メモリブロックが一つである場合には該固定長メモリブロックを元の可変長領域に変更しないことを特徴とするメモリ管理方式。
2. 上記固定長ブロックの固定長メモリ領域の割り付け・開放に伴ってチェーンの張り替えを実行することにより該固定長メモリ領域がチェーン管理されてなり，
   上記メモリ上の可変長領域に二以上の上記固定長メモリブロックが確保されている場合に，上記可変長領域に確保された二以上の上記固定長メモリブロックのいずれか一つの固定長メモリブロック内の上記固定長メモリ領域が全て開放されたとき，該一つの固定長メモリブロックの他に上記固定長メモリ領域が全て開放された上記固定長メモリブロックが存在しない場合には該一つの固定長メモリブロックの固定長メモリ領域を元の可変長領域に変更せず，該一つの固定長メモリブロックの他に上記固定長メモリ領域が全て開放された上記固定長メモリブロックが存在する場合には該一つの固定長メモリブロックの固定長メモリ領域をチェーンの張り替えの実行前に元の可変長領域に変更する請求項１に記載のメモリ管理方式。

Images