JPH02297232A - メモリ管理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、情報処理装置等におけるメモリ管理方法に関
し、特に２次元座標系によって定義されたメモリ空間上
のメモリ領域の割り付は管理方法に関する。

従来の技術 従来、画像等の２次元的な広がりを持つ情報の領域をメ
モリ上に割シ付ける際、画像におけるビクセル（画像）
のメモリ上のマツピングやウィンドウクリッピングのよ
うな機能を容易にするため、ビクセル・アドレスをメモ
リの物理的アドレスで定義せず、°画像上のビクセルの
ロケーションに対応した２次元ＸＹ座標系によってビク
セルアドレスを定義する方法が採られることが多い。

従来、このようなＸＹ座標系によって定義されたメモリ
空間に画像情報等のメモリ領域を割シ付ける場合、ソフ
トウェアによって、メモリをクリアしてから、先頭アド
レスよシ最初のメモリ領域を割シ付け、そのメモリ領域
の管理情報（開始アドレスおよび終了アドレスまたはデ
ータ量）を記憶しておき、次にメモリ領域を割シ付ける
ときには、それまでに割シ付けられているメモリ領域の
管理情報を調べることによシ、割シ付は可能な空き領域
を捜し、そこに割り付けるという方法であった。

なお、ＸＹ座標系によって定義されたメモリ空間上に割
り付けた矩形のメモリ領域を、実メモリ上に確保するに
は、その矩形領域の開始アドレス（Ｘ、　Ｙ）を２次元
のＸＹアドレスから実メモリのリニアアドレス（１次元
アドレス）に変換する必要がある。この変換は基本的に
は次の計算式によって行われる。

リニアアドレス＝　（メモリ領域の幅）ＸＹ＋Ｘ・・・
式（１） ここで、Ｙ成分のリニアアドレスの変換の際の乗算は、
ＣＰＵに対する負荷が大きく時間がかかるので、実際に
は、メモリ空間のピッチを２のべき乗にとることにより
、Ｙ成分のリニアアドレスへの変換を、単にｌｏｇ２（
メモリ領域の幅）分だけＹの値をシフトする操作で行う
ようにしている。ただし、最大（２のｎ乗−１）ビット
幅の領域が未使用となる。

発明が解決しようとする課題 しかし、上述のようなメモリ管理方法によれば、割り付
けたいメモリ領域の大きさに応じて、無駄な空き領域が
できるだけ少なくなるようにメモリ領域の割シ付は位置
を最適化することが容易でない。特に、−旦割シ付けた
メモリ領域を開放し、それを再び空き領域に含めて以後
のメモリ領域の割り付けを行う、というようなことは極
めて困難で、実際的には一旦割シ付けたメモリ領域は、
メモリをクリアするまで使用中となってしまう。その結
果、効率的なメモリの使用ができないという問題があっ
た。

本発明は、上述の問題点に鑑みてなされたもので、２次
元的な広がシを持つ画像情報等のメモリ領域の割り付は
容易かつ効率的に行うだめのメモリ管理方法を提供する
ことを目的とする。

課題を解決するための手段 本発明は上述の課題を解決するため、２次元座標系によ
って定義されたメモリ空間を一定の大きさのブロックに
分割するとともに、各ブロックに１対１に対応した、各
ブロックの使用状況を示すフラグを記憶するための２次
元の管理テーブルを設け、この管理テーブル上において
ブロックを単位として前記メモリ空間に対するメモリ領
域の割り付けを管理するという構成を備えたものである
。

作用 上述の管理テーブルの内容はブロックを単位としたメモ
リ空間の使用状況のマツプであるから、この管理テーブ
ルを参照することによって、任意の時点において割シ付
けたいメモリ領域の大きさに対応した、最適な（メモリ
の無駄が最小となるような）空き領域を簡単に見つけ、
そこに割シ付けることができる。また、−旦割シ付けた
メモリ領域であっても、管理テーブル上の対応ブロック
のフラグを更新するだけで割り付けを開放し、空き領域
として次のメモリ領域の割シ付けの際に利用できる。し
たがって、複雑なソフトウェア処理を行うことなく、メ
モリ領域の割シ付けを最適化し、効率的なメモリ使用が
可能である。

実施例 第１図は本発明の一実施例によるメモリ管理装置の機能
構成図である。

第１図において、１は画像情報の記憶のための実メモリ
空間を提供するメモリ部である。この実メモリ空間は、
管理上は２次元のＸＹ座標系によって定義されたメモリ
空間として扱われる。また、このＸＹ座標系によって定
義されたメモリ空間は、一定の大きさのブロックに分割
して使用が管理される。

２はメモリ部１に記憶させたい画像情報のメモリ領域の
大きさを得るサイズ設定部である。ここではメモリ領域
を矩形領域とし、そのサイズはＸ方向とＸ方向の大きさ
で表される。

３はメモリ空間の使用状況をブロックを単位として管理
するための管理テーブルであって、メモリ空間上の各ブ
ロックに１対１に対応した、使用状況を示すフラグを記
憶するための２次元のテーブルである。

４はサイズ設定部２によって得られたメモリ領域の大き
さに対応上だ必要プロンク数を求めるフロック数決定部
である。ここでは、メモリ領域のＸ方向およびＹ方向Ω
大きさをブロックのＸ方向およびＸ方向の大きさでそれ
ぞれ割り算することＫｉ、Ｘ、Ｙ各方向の必要ブロック
数ＩＩ　ｋを求める。

５は必要ブロック数ｉ、にの矩形のメモリ領域を割り付
けるだめの空き領域を管理テーブル３よシ検索し、また
割り付は結果に応じて管理チーフル３上の対応ブロック
のフラグを制御する割り付は制御部である。割シ付けの
結果は、割シ付けたメモリ領域の原点の管理テーブル３
上の位置パラメータ（Ｘ、Ｙ）として出力される。

６は割シ付は制御部５よシ出力された原点の位置パラメ
ータ（Ｘ、Ｙ）と、ブロック数決定部４からの入力パラ
メータ（ｉ、ｋ）より、割シ付けられたメモリ領域をメ
モリ部ｌによって提供された実メモリ空間上に確保し、
そこに実際に画像情報を割シ付ける（書き込む）だめの
メモリ制御部である。ここでは、ＸＹ座標系のアドレス
から実メモリ空間のリニアアドレスへの変換が行われる
が、この変換方法は従来と同様でよい。

第３図は上述の機能的構成を実現するための実際的なハ
ードウェア構成の一例を示すもので、７は中央処理装置
、８はプログラムや管理テーブル３（第１図）を格納す
るための主メモリ、９はメモリ部１　（第１図）として
の画像メモリ、１０はバスである。サイズ設定部２、ブ
ロック数決定部４、割シ付は制御部５およびメモリ制御
部６は、主メモリ８に格納された各プログラム１１．１
２．１３．１４によって中央処理装置７上でそれぞれ実
現される。

なお、画像メモリ９（メモリ部１）へ格納すべき画像情
報は、バスｌＯに接続された外部入出力装置（図示せず
）よ多入力される。

第３図はメモリ管理テーブル３の説明図である。

この例では、２次元のＸＹ座標系で定義されたメモリ空
間の幅（Ｘ方向の大きさ）を１６３８４　（２′４）ビ
ット、高さ（Ｙ方向の大きさ）を８１９２（＝２１３）
ビットとしている。ただし、このメモリ空間は表示メモ
リ９（メモリ部１）によって提供される実メモリ空間の
一部であってもよい。また、ブロックの幅および高さを
１０４８（＝２”）ビットとしている。

管理テーブル３上の各フラグ（第３図中の一つの桝目）
はメモリ空間上の一つのブロックと１対１に対応し、１
”（オン〕の７ラグは対応ブロックが使用中であること
を意味し、′０”（オフ）のフラグは対応ブロックが未
使用（空き状態）であることを意味する。この未使用と
は、メモリがクリアされてから全く割り付けられていな
い場合、または−旦割シ付けられたが開放された場合を
意味する。

したがって、第３図に示すように管理テーブル３上のフ
ラグがセットされている場合、表示メモリ１上のメモリ
空間のＸＹアドレス（０，０）を原点とし、幅５２４０
ビット　（＝１０２４Ｘ５）ビット、高さ６２６４　　
（＝１０２４Ｘ６）　　ビットの矩形のメモリ領域が使
用中である（画像情報が割シ付けられている）というこ
とである。

次に、メモリ管理の内容について第４図及び第５図を参
照しながら説明する。

第４図は、メモリ管理の主要機能部である割シ付は制御
部５の動作の概略７０−チャートである。

このフローチャートにおいて、入力パラメータ（ｉ、ｋ
）はそれぞれ、割シ付けたいメモリ領域のＸ、Ｙ方向の
必要ブロック数であシ、これはブロック数決定部４より
入力される。そして、割り付は制御部５は、返値として
、割り付けたメモリ領域の開始アドレスを、管理テーブ
ル３上の位置パラメータ（Ｘ、Ｙ）で返す。なお、管理
テーブル３の初期状態は、１６３８４Ｘ８１９２ビツト
のメモリ空間の全域が未使用で、全ブロックのフラグが
オフになっているものとする。

また、第５図は初期状態から■、■、■、■の各メモリ
領域を順に割り付けた場合の管理チーフルの内容の変遷
図である。

ステップｌにおいて、Ｘ、Ｙをそれぞれ０に初期化する
。

最初の領域■の入力パラメータ（ｉ、ｋ）は（５，３）
である。この領域■の割シ付けの場合、ステップ２にお
′いて、管理テーブル３上でＹの値に対応する行におい
て、Ｘの位置からＸ方向ヘオフされているフラグの連続
数を調べる。初めは（Ｘ、Ｙ）＝　（０，Ｏ）であるか
ら、１行目（Ｙ二〇）のＸ＝０よりオフ・フラグの連続
数を調べる。ここでは、Ｘ−Ｏの位置のフラグはオフし
ているので、ステップ３において、この連続数と入力パ
ラメータｉとを比較する。この場合、画像メモリ９は初
期状態であるから、当然、連続数≧ｉの部分が見つかる
のでステップ４へ進み、現在対象となっているブロック
のＸ座標値（ここでは０）をＸに代入し、ステップ５お
よび６において、ステップ２で検出したオフのフラグの
連続の真下の行のフラグもオフされているか調べ、真下
の行もフラグはオフしていればステップ７においてＹに
１を加え、ｋ行分だけステップ５，６を繰り返すことに
なる。

ここではに＝３であるので、Ｙ−３となったときにステ
ップ９へ進み、パラメータ（Ｘ、　Ｙ）　、！：して領
域■の原点のＸ、Ｙ座標（Ｘ、Ｙ−ｋ）＝（０，０）を
出力し、また領域■に割り付けられたブロックに対応し
たフラグをオンする。

次の領域■の割り付けの場合、領域■が既に割り付けら
れ、Ｘ二〇の位置のフラグはオンされているので、Ｘ＝
Ｏ，Ｙ二〇の段階でステップ３からステップ１１へ進む
。Ｙは最終行には当たらないので、ステップ１０に進み
Ｙに１を加え、次のステップ１５で（Ｘ＋ｉ）と管理テ
ーブル３の列数Ｃｏｌとの比較判定を行う。ここでは、
Ｘ＝Ｏ，ｉ＝２、Ｃｏ１＝１６であるから、ステップ２
に戻シ、管理テーブルの２行目（Ｙ＝１）についてＸ＝
０の位置よりオフ・フラグの連続数が調べられる。ここ
でもＸ−０の位置のフラグはオンしており、ｉを越える
オフ・フラグの連続は検出されないのでステップ１１、
ステップ１０、ステップ１５を経由してステップ２に戻
る。

結局、管理テーブル３の４行目（Ｙ＝３）でステップ３
からステップ４へ処理が進み、ステップ５からステップ
７の繰り返しによって領域■の割り付けが成功し、その
原点のＸ、　Ｙ座標値（０゜３）をパラメータ（Ｘ、　
　Ｙ）として出力し、また管理テーブル３の領域■に含
まれるブロックに対応したフラグをオンする。

次の領域■の割り付けの場合、最終行（Ｙ＝７）までＸ
−０の位置のフラグはオンしているので、ステップ１１
よりステップ１２に進む。このステップ】２において、
割り付は済みブロックの調査の繰り返しを避けるため、
その時のＸの値にｉ　（＝４）を加えた値をＸに代入し
、またＹにＯを代入してから、ステップ１５の比較判定
を行う。ここでは、Ｘ　＋　ｉ≦Ｃｏｌであるので、ス
テップ２に戻る。

４行目（Ｙ＝３）で、Ｘ＝２よりｉを越えるオフ・フラ
グの連続が見つかるので、ステップ４でＸに２を設定し
、ステップ５からステップ７を最終行まで繰り返して領
域■を割り付ける。そして、ステップ９で領域■の原点
のＸ、　Ｙ座標値（２゜３）をパラメータ（Ｘ、Ｙ）と
して出力し、また対応するフラグをオンする。

次の領域■の割り付けの場合も領域■の割シ付けの場合
と同様の処理の流れとなシ、ステップ１２でＸ＝７．Ｙ
＝Ｏに設定されてからステップ２に戻り、領域側υ付け
が行われることになる。

なお、ステップ５で真下の行に同じオン・フラグの連続
が見つからなかったときは、ステップ６からステップ１
３に進み、Ｙ十にとＲｏｗ　（管理テーブル３の行数（
＝８）との比較判定を行う。これは、現在対象となって
いる行より下に、確保したい領域のための空き領域が残
っているか否かを調べるためである。必要な空き領域が
残っていれば、ステップ１４に進むが、残っていなけれ
ばステップ１２に進む。

また、ステップ１５でＣｏｌ＜Ｘ＋ｉの場合、確保した
い領域のための空き領域が残っていないといウコトであ
るので、ステップ１６のエラー処理を行う。

以上のようにして、割り付は制御部５によって管理テー
ブル３上でメモリ領域の割ｐ付けが行われ、各メモリ領
域の原点のＸ、Ｙ座標がパラメータ（Ｘ、　Ｙ）として
出力される。メモリ制御部６は、この出力パラメータ（
Ｘ、Ｙ）と入力パラメータ（ｉ、ｋ）′に基づき、画像
メモリ９　（メモリ部１）に実際に領域を確保し、そこ
に画像情報を書き込むことになる。このときに２次元ア
ドレスとリニアアドレスの変換が行われることは上述の
通ｐである。

なお、割シ付けられたメモリ領域の開放は、割シ付は制
御部５において管理テーブル３上の対応フラグをオフす
ることによって行う。フラグがオフされたブロックは、
空き領域として以後の割り付けに使用される。

発明の効果 以上の説明から明らかなように、本発明は、２次元座標
系によって定義されたメモリ空間を一定の大きさのブロ
ックに分割し、各ブロックと１対１に対応した管理テー
ブル上のフラグを参照することによって、ブロック単位
でメモリ領域の割シ付けを管理するため、画像等の２次
元的な広がりを持つ情報のメモリ領域の割り付け、開放
を簡単かつ効率的に行い、メモリ領域の幅に制限のある
メモリの効率的な使用が可能になるという効果を有する
ものである。

【図面の簡単な説明】

第１図は本発明の一実施例によるメモリ管理装置の機能
構成図、第２図は同メモリ管理装置の実際的なハードウ
ェア構成の例を示すブロック図、第３図は管理テーブル
の説明図、第４図は割シ付は制御部の動作の概略フロー
チャート、第５図はメモリ領域の割シ付けによる管理テ
ーブルの内容の変遷を示す図である。 １・・・メモリ部、２・・・サイズ設定部、３・・・管
理チーフル、４・・・フロック数決定部、５・・・割り
付は制御部、６・・・メモリ制御部、７・・・中央処理
装置、８・・・主メモリ、９・・・画像メモリ、１１・
・・サイズ設定プログラム、１２°°°ブロツク数決定
プログラム、１３°゛割り付は制御プログラム、１４・
・・メモリ制御プログラム。 代理人の氏名　弁理士　粟野重孝　ほか１名１図 第 図 第 図

Claims (1)

【特許請求の範囲】
1. ２次元座標系によって定義されたメモリ空間を一定の大
   きさのブロックに分割するとともに、各ブロック１対１
   に対応した、各ブロックの使用状況を示すフラグを記憶
   するための２次元の管理テーブルを設け、前記管理テー
   ブル上においてブロックを単位として前記メモリ空間に
   対するメモリ領域の割り付けを管理することを特徴とす
   るメモリ管理方法。