JPS6027962A

JPS6027962A - 構造体メモリ管理方式

Info

Publication number: JPS6027962A
Application number: JP13612683A
Authority: JP
Inventors: Shinichi Habata; 幅田　伸一
Original assignee: NEC Corp; Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1983-07-26
Filing date: 1983-07-26
Publication date: 1985-02-13

Abstract

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

Description

【発明の詳細な説明】本発明は、プロローグの構造体の実現、ならびに、動的
メモリ管理装置の管理方式に関するものである。

近年、知的システムへの関心の高まりとともに、述語論
理型言語プロローグが注目されている。その理由の１つ
として、可変側の要素から構成される構造体を直接扱え
ることがあげられる。

例えば、プロローグでは、かごの中に“りんご”“みか
ん”、“なし″が入っている状態を構造体温“かご”　
要素数３の構造体を使って次のように表現できる。

かご（りんご、みかん、なし）さらに、太部がこのかごを持っているという事実を、構
造体温°“持つ″、要素数２の構造体を用いて次のよう
に記述できる。

持つ（太部、かご（りんご、みかん、なし））プロロー
グは、このような可変側の要素を持つ構造体を用いるこ
さに、よりデータの記述を容易にしている。

一方、プロローグを実行すると多数の構造体が、動的に
生成・消滅するため、構造体の領域として多量のメモリ
セルが必要となる。そこで、メモリセルの使用効率を高
めるために、一度、使用済みとなったメモリセルを回収
し、再度、構造体を格納するのに使用するカーベージコ
レクションが行なわれる。しかし、カーベージコレクシ
ョンにかが７）処理コストは大きく、全体の処理コスト
の３０％から５０％以上になる場合がある。

本発明は、このようなカーベージコレクションを高速に
処理できる構造体の管理方式を提供するものである。

構造体を実現するための良く知られた実現方式の１つは
、固定長の領域をポインタで複数個つなぐ方式である。

以下、この方式を第１の構造体実現方式と称す。ｈ第１
図に２進木リストセル１０を用いて構造体持つ（太部、かご（りんご、みかん、なし））を表現し
た時の概念図を示す。この方式の最大の特徴は、メモリ
セルを確保する単位が固定長となっているため、未使用
領域が連続領域になくてもよい点にある。すなわち、カ
ーベージコレクションにより使用済みメモリセルを回収
する作業は固定領域（２進木リストでは２連続のメモリ
セル）をポインタで結ぶだけでよい。しかしながら、固
定長領域をポインタで接続する方式は、構造体の要素を
アクセスする際のオーバーヘッドが大きいという欠点を
持つ。例えば、構造体のｎ番目の要素をアクセスするた
めにはポインタをｎ回辿らねばならず、メモリアクセス
ネックの要因となる。

前記方式の欠点を解消する他の方式としては、構造体の
要素を連続領域に並べ、各要素へのアクセスをヘッダ部
からのオフセットで行なう方式が知られている（以下、
この方式を第２の構造体実現方式と称す。）。第２図は
、第２の方式による構造体持つ（太部、かご（りんご、みかん、なし））を表現す
る概念図である。第２図において、２０は構造体毛領域
、２１は要素数頭域、２２はカーベージコレクション時
に、その構造体が使用中又は、使用済みであることを示
すのに使用するマークピット、詔はデータ領域を表わす
。構造体毛領域２０、要素数頭域２１およびマークビッ
ト２２の３つの領域を合わせて、以下、特にヘッダ領域
と称ず。

この方式では、構造体はヘッダ領域と構造体の各要素を
格納するデータ領域ｎが連続領域に割り当てられている
。したがって、構造体を要素として含むときは構造体ヘ
ッダ領域へのポインタを要素とすればよい。また、要素
へのアクセスはヘッダ領域からのオフセットを用いて高
速に行なうことができる。

しかしながら、この方式では構造体は可変長の連続領域
に格納される必要があるため、カーベージコレクション
のオーバーヘッドが太きいという問題点を持つ。又、構
造体の性質上１つの構造体を複数の構造体が共有する可
能性がある。第３図（１）　、　（２）は、構造体Ａと
構造体Ｃが構造体Ｂを共有している時のカーベージコレ
クションによるメモリ領域の遷移を示す概念図である。

第３図において、３０はメモリ、３１は使用中の構造体
領域、３２は使用済みあるいは未使用の領域を示す。又
、第３図（１）はカーベージコレクションを行なう前の
メモリ状態、第３図（２）はカーベージコレクションを
行なった後のメモリ状態を表わす。

この方式におけるカーベージコレクションは、次のよう
にして実現される。初めζこ、現在使用中の構造体に印
をつける操作を行なう。これは、次のアルゴリズムによ
って、外部処理装置が処理を行なう時に現在使用中の構
造体の情報を格納しているスタックを調べて、スタック
から直接又は、間接に参照されている構造体のマークピ
ット領域のフラグをセットすることにより実現される。

スタックより指される全ての構造体について、構造体の
マークピットが既にセットされていれば何もせず、セク
トされていなければ、前記構造体のマークピットをセッ
トし、前記構造体が要素としてさらに構造体を含むとき
は要素となっている全ての構造体について処理を繰り返
す。

上記アルゴリズムでマークピットがセットさね。

なかった構造体は、使用済み領域として回収できる。し
かし、固定領域を用いた前記第１の構造体実現方式のよ
うに単ζこ使用済み領域をポインタで結ぶたけでは、次
に新しい構造体の領域として連続領域を確保することが
できない。したがって、未使用領域を連続領域上に確保
するためには、第３図（１）　、　＋２）に図示しであ
るように、使用中の構造体領域３１をリロケートして、
使用済領域３２を集める必要がある。

この方式の問題点は、ｉ遺体をリロケートする際に、リ
ロケートした構造体を指すポインタを全て書き換える必
要がある点にある。

本発明の目的は、上記第２の構造体表現実現方式の問題
点を解決し、要素へのアクセスが高速で、カッ、カーベ
ージコレクション時の構造体のりロケーションのオーバ
ヘッドが最小となるような構造体を実現する構造体メモ
リ管理方式を提供することにある。

本発明によれば、固定長のヘッダ部と可変長のデータ部
とから成る構造体を貯える大容量メモリと、前記大容量
メモリの一部を貯え、外部装置によってアクセスされる
キャッシュメモリと、前記大容量メモリの使用中領域と
未使用中領域とを識別するための情報を保持する階層化
ピットマツプと、前記大容量メモリ及び、前記キャッジ
−メモリに格納されている個々の構造体を識別するため
の番号と前記大容量メモリ上の格納番地との間の変換処
理と、前記大容量メモリに新たな構造体を格納するため
の連続領域が確保できなくなった時、前記大容量メモリ
上の構造体で使用中のものを、前記階層化ビットマツプ
の情報を使用して前記大容量メモリ中でリロケートし、
前記性たな構造体の格納領域を確保する操作を前記外部
装置が前記キャッジ−メモリを用いて処理を実行するの
と並行して行なうブロック管理ユニットと、前記キャシ
ュメモリに格納されている構造体の識別番号と前記キャ
ッシュメモリ上の格納番地間の変換と、前記キャッシュ
メモリ上に存在しない構造体を前記大容量メモリから取
ってきたり、新たに生成された構造体を前記大容量メモ
リに格納する処理を実行するキャッジ−管理ユニットと
を備え、前記ブロック管理ユニットが前記大容量メモリ
へアクセスするのと並行して、前記外部装置が前記キャ
ッジ−管理ユニットを使用して前記キャッシュメモリを
アクセスできる構造体メモリ管理方式が得られる。

次に、本発明について図面を用い、詳細に説明する。

第４図は本発明の実施例の１つである構造体メモリ管理
装置のブロック図である。図において、１００はブロッ
ク管理ユニットであり、１０１はブロック番号領域、１
０２はマークピット領域、１０３は構造体を格納してい
るメモリ上の領域の先頭を指すポインタ領域、１０４は
ブロックの大きさを格納するサイズ領域である。又、１
１０はキャッシュメモリを管理するキャッジ−管理ユニ
ットであり、１１１はキャッシュメモリ上に格納されて
いる構造体に割り付けられたブロック番号を格納するキ
ャリー用ブロック番号領域、１１２はキャッシュメモリ
上の未使用領域決定に用いるキャッシュ用マークピット
領域、１１３は構造体を格納しているキャッシュメモリ
上の領域の先頭を指すキャッジ−用ポインタ領域である
。１２０は構造体メモリ管理ユニットであり、１２１は
階層化ビットマツプである。

さらに、１３０はメモリであり、１４０はキャッシュメ
モリである。１６０はプロローグを実行するのに使用す
る情報が蓄積されるスタックメモリである。

構造体メモリ管理ユニッ）　１２０は、前記階層化ビッ
トマソプ１２１、ブロック管理ユニット１００、キャッ
シュ管理ユ′二、／ト１１０の情報を使用し、て、メモ
リ１３０とキャッシュメモリ１４０を管理し、かつ、前
記スタックメモリ１６０に格納されている使用中の構造
体に対応したブロック番号から、現在使用中の構造体の
マーキングを指示するユニットである。１７０は前記キ
ャッシュメモリ１４０、メモリ１３０、スタックメモリ
１６０及び、図示されていない外部処理ユニットを結合
するデータバスであり、１９０は前記キャッシュ管理ユ
ニ、　ト１１０とブロック管理ユニット１００、構造体
メモリ管理ユニット１２０、スタックメモリ１６０及び
、図示されていない外部処理ユニットを結合するアドレ
スバスである。又、１８０はメモリ１３０、ブロック管
理ユニット１００、構造体メモリ管理ユニット１２０を
結合する内部バスである。１９０は、キャッシュメモリ
１４０、キャッシュ管理ユニッｌ−’１１０　、構造体
メモリ管理ユニット１２０を結合する内部バスである。

本実施例における構造体メモリ管理方式を図を参照しつ
つ説明する。第５図は本実施例における構造体メモリ管
理方式を説明する概念図である。

なお、１０２のマークビット領域で、１１″は使用中ブ
ロック、“０”は未使用ブロックを表わしている。

構造体が定義されていない状態では、ブロック管理ユニ
ット中のマークビット領域１０２は“０″である。

図示されていない外部処理ユニット（例えば、プロロー
グプロセッサ）から構造体メモリ管理ユニット１２０へ
、新しく構造体を作成せよという要求が出された時の構
造体メモリ管理ユニツ）　１２０の動作は次のようにな
る。

例えば、構造体　かご（りんご、みかん、なし）をメモ
リ上に置く場合を考える。初めに、構造体を格納するた
めのブロックの大きさ４が、構造体メモリ管理ユニット
１２０へ送られ、構造体メモリ管理ユニット１２０は、
階層化ビットマツプ１２１を使用して、大きさ４以上の
未使用領域を捜す。未使用領域を捜す動作と並行して、
構造体メモリ管理ユニッ）　１２０は、ブロック管理ユ
ニット１００へ、未使用ブロック番号を１つ確保するこ
とを要求する。

ブロック管理ユニット１００は、新しい構造体のために
確保したブロック番号（第５図では、ブロック番号１）
を図示されていない外部処理ユニットへ通知する。その
後、サイズ領域に要求されたフロックのサイズを格納す
る。新しい構造体を格納する領域に与えられたブロック
番号とそのブロックの何番目の要素であるかを指定する
ことで、図示されていない外部処理ユニ、トはメモリ１
３０上に新しい構造体を生成することができる。

前記ブロック管理ユニット１００が、新しい構造体を格
納する領域のために割り当てるブロック番号を決定して
いる間に、構造体メモリ管理ユニット１２０は階層化ビ
ットマツプ１２１を使用して、新しい構造体を格納でき
る未使用領域を捜し、未使用領域の先頭アドレスをフロ
ック管理ユニットｉｏｏに通知する。

前記フロック管理ユニソｌ−１００は新しい構造体のた
めに用意された未使用領域の先頭アドレスを、新しい構
造体を格納する領域に割り当てられたブロック番号のポ
インタ領域に格納する。構造体の値としては、構造体が
格納されている領域に割り当てられたブロック番号が返
されるので、構造体“持つ（太部、かご（りんご、みか
ん、なし））”のように構造体を要素として含む構造体
は、第５図に図示したように、構造体の要素を格納する
位置に、要素となる構造′体のブロック番号を格納する
ことになる。

＠５図は、さらに構造体持つ（花子、かご（りんご、みかん、なし））が構造体かご（りんご、みかん、なし）を共有している状態を示す。

新しい構造体が次々と生成されていくと、構造体メモリ
管理装置１２０が、新しい構造体を格納できる大きさの
未使用領域を確保できない状態が先生し、ガーベージコ
レクション処理を開始する。

ガーベージコレクションが開始されると、はじめにマー
クビット１０２の値を全て“０”をこセットする。同時
に、構造体メモリ管理ユニット１２０上の階層化ヒツト
マツプ１２１の値も“０”にする。次にスタックメモリ
１６０におかれている構造体を格納している領域の各ブ
ロック番号に対して、次のアルゴリズムに従って使用中
ブロックのマーキンクを行なう。

（１）マークビット１０２を“１”にセリトンた後、ポ
インタ領域１０３が指すアドレスの次のアドレスから、
構造体の要素数だけザーチし、ブロック番号を値とする
要素に対して、（２）の操作を行なう。こノ時、ポイン
タ領域１０３におかれているアドレスから、サイズ領域
１０４に格納されている大きさだけの連続領域は使用中
であることを階層化ビットマツプ１２１にセットしてや
る。マークピッ）・１０２のセットと、階層化ビットマ
ツプ１２１のセットは、夫々ブロック管理ユニッ）　１
００と構造体メモリ管理ユニット１２０により並行して
行なわ才ｌる。

（２）対応するブロックのマークピッＩ−，１０２の値
が“Ｉ　ＩＩなら、スタックメモリ１６０上の次のブロ
ック番号に対して、（１）の処理を行なう。マークピッ
ト１０２の値が“Ｏ”ならば、そのブロックに対して（
１）の処理を行なう。

この結果、ブロック９ｍユニット１００上ζこは、現在
使用中のブロック番号のマークピッｉ・領域１０２のみ
に、４１″′がセットさｎている。さらに、構造体メモ
リ管理ユニット１２０上の階層化ビットマツプ１２１上
には、メモリ１３０における１吏用中領域と未使用領域
の情報がセットされている。

次に階層化ビットマツプ１２１の使用中領域の情報を使
用して、使用中領域のりロケーションを行なう。この時
、使用中領域のりロケーションはブロック単位で行なっ
ていく。使用中領域のりロケーションと並行して、ブロ
ック管理ユニット１００のポインタ領域１０３が更新さ
れる。例えば、第５図のメモリ状態でのりロケーション
処理でブロック３がリロケートされた状態が第６図であ
る。ブロック単位に使用中領域をリロケートしていくと
、リロケーションが進むにつれて、使用済領域の大きさ
が増していく。使用済領域の大きさが、ガーベージコレ
クションの原因となった新しく生成される構造体を格納
するに充分な大きさになった時点で、その使用済領域を
新しい構造体に割り当てられたブロック番号の領域とし
て登録し、外部処理ユニットに処理再開の許可を与える
。

外部処理ユニットは、新しい構造体の生成が終了すると
、キャッシュメモリ１４０を使用して処理を再開する。

構造体メモリ管理ユニット１２０は外部処理ユニットが
新しい構造体の生成を終了し、キャッシュメモリ１４０
を使用して処理を再開したのを確認すると、中断してい
たりロケーション処理を再開する。

次に、新しい構造体を格納する領域を捜したり、リロケ
ーション処理で使用中領域の情報を提供する階層化ビッ
トマツプ１２１について説明する。

第７図は、ビットマツプ３００を用いてメモリ３１０の
使用領域情報を管理する実施例の概念図である。第７図
ではビットマツプ３００上の１ビツトをメモリ３１０上
の２セルに対応させており、ビットマツプ３００上のビ
ットを調べることで対応するメモリ３１０上の２セルが
、使用中であるが、又は未使用であるかの情報を得るこ
とができるようになりている。

第７図では、ビットマツプ３００のビットの値が“０”
の時は、対応するメモリ３１０上の２セルが未使用領域
であることを表わし、ビットの値が“１″の時は、対応
するメモリ３１０上の２セルは使用中領域であることを
表わす。

従って、未使用領域の割り付けを要求された時は、要求
された大きさの領域に相当する長さだけ連続して“Ｏ′
であるビット列を、ビットマツプ３００上で捜し、その
先頭アドレスを出力してやる。

要求された大きさの領域に相当する長さだけ連続して“
Ｏ”であるビット列が、ビットマツプ３００上に存在し
ない時は、ガーベージコレクション処理を要求する。

本構造体メモリ管理方式で使用されている階層化ビット
マツプは、第７図のビットマツプ３ｏｏを用いて未使用
領域を捜す処理を高速化するために、複数のビットマツ
プを階層化して、上方に位置するビットマツプの１ビツ
トが、下方に位置するビットマツプの連続する数ビット
の状態に関する情報を持つようにして、大きな使用領域
の存在によるビットマツプのアクセス回数増加を抑える
ことを実現している。

第８図は、階層化ビットマツプの実施例の概念図である
。４１０．４２０．４３０．４４０は、各々ビットマ。

プであり、４５０はメモリである。ビットマツプ４１０
上の１ビツトはビットマツプ４２０上の４ビツトの状態
に対する情報を持っており、ビットの値の意味は次のよ
うになっている。

ｔｉ＞　ビットマツプ４４０上のビットは値が“０”の
時は、対応するメモＩＪ　４５０上の２セルが未使用で
あることを表わし、値が“１”の時は、対応するメモＩＪ　４５０上の２セ
ルが使用中であることを表わす。

（２）ビットマツプ４１０，４２０，４３０上のビット
は、値が“１”の時は、対応する一段下方のビットマツ
プ上の連続した４ビツトの値が全て“１″であることを
表わす。

値カ“０”の時は、対応する下方のビットマツプ上の連
続した４ビツトの値の内、少なくきも１っは“０”であ
ることを示す。

階層化ビットマツプを用いて、未使用領域を捜す方式は
、次のアルゴリズムに従う。

（１）最上方のビットマツプ４１０を使って、値が“０
″であるビットを捜す。この時、メモリ４５０の第０番
地（第８図最右端）を担当するビット４１１から調べる
。これは、ガーベージコレクション処理の時に行なわわ
るリロケーションにより、メモリ４５０の第０番地側に
、常に使用される構造体が格納される可能性が高くなる
ためである。値が“θ″であるビットを見つけたら、処
理（２）へ移る。

（２）上方のビットマツプから送られてきた、値が“０
”の上方のビットマツプ上のビットの位置から、そのビ
ットに対応する連続した４ビツトを訓べる。

要求された未使用領域の大きさが、現在調べているビッ
トマツプ上のビットに対応するメモリ４５０上の領域の
大きさより大きい時は、処理（３）を行なう。値が“０
″のビットを捜し、下方のビットマツプに対し、処理（
２）を行なう。

（３）要求された未使用領域の大きさに相当する、値が
全て“０″のビット列を捜し、そのビット列の先頭ビッ
トの位置をめ、下方のビットマツプに対し処理（２）を
行なう。但し、現在調べているビットマツプがビットマ
ツプ４４０の時は、見つかったビット列の先頭ビット位
置からメモＩＪ　４５０上の未使用領域の先頭アドレス
をめ出力する。

本構造体メモリ管理方式により、プロローグの実行時に
行なわれる多数の構造体の動的生成・消滅操作の結果生
じる一度使用済みとなったメモリセルを回収するガーベ
ージコレクション処理ヲ外部装置の負荷から切り離し、
構造体メモリを使用している外部装置からみたガーベー
ジコレクション処理時間を短縮することができる。

【図面の簡単な説明】

第１図は、構造体を固定領域を使って実現した時の一例
を示す概念図、第２図は、構造体を可変現した時のガー
ベージコレクションの一例を示す概念図、第４図は、本
発明の一実施例である構造体メモリ管理装置のブロック
図である。また、第５図、第６図は、本発明のガーベー
ジコレクション方式を説明する概念図であり、第７図、
第８図、４話鉢跡は、本発明の階層化ビットマツプを説
明する概念図である。図において、ｌＯは２進木リストセル、２０は構造体毛
領域、２１は要素数領域、２２はマークビット、詔はデ
ータ領域、３０はメモリ、３１は使用中の構造体領域、
３２は使用済み領域、ｉｏｏはブロック管理ユニッ＋−
，ｉｏｉはブロック番号領域、１０２はマークビット領
域、１０３はポインタ領域、１０４はサイズ領域、１１
０はキャッジ−管理メモリ、１１１はキャッシュ用ブロ
ック番号領域、１１２はキャッシュ用マークビット領域
、１１３はキャッシュ用ポインタ領域、１２０は構造体
メモリ管理ユニット、１２１は階層化ビットマツプ、１
３０はメモリ、１４０はキャッシュメモリ、１６０はス
タックメモリ、１７０はデータバス、１８０は内部バス
、１９０はアドレスバス、１３１は使用中領域、１３２
，１３４は使用済領域、３００．４１０，４２０，４３
０，４４０はビットマツプ、３１０．４５０はメモリで
あり、４１１はビットマツプ４１０の１ビツトを表わし
ている。第１図ｎ第　２　図第３図（＋）　（２）躬４図第５図第６図第７図３００第　８　図手続補正書軸発）５９、１０１２２昭和　年　月　日１、　ｉＪｌ’ｌ、の表示　昭和５８年　特詐　願第１
３６１２６号２、発明の名称　構造体メモリ管理方式３
、補正をする者事件との関係　出　願　人東京都港区芝ＩＬ丁「」３３番１号４、代理人５、補正の対象明細書の発明の詳細な説明の欄図面６、補正の内容１）明細書第１１頁第１６行目に「１９０は、」とある
のを「２００は、」と補正する。２）本願添付図面の第４図を別紙図面のように補正する
。代理人　弁理士　内　原　ヨ

Claims

【特許請求の範囲】

固定長のヘッダ部と可変長のデータ部とから成る構造体
を貯える大容量メモリと、前記大容量メモリの一部を貯
え、外部装置によってアクセスされるキャッシュメモリ
と、前記大容量メモリの使用中領域と未使用中領域とを
識別するための情報を保持する階層化ビットマツプと、
前記大容量メモリ及び、前記キャッシュメモリに格納さ
れている個々の構造体を識別するための番号と前記大容
量メモリ上の格納番地との間の変換処理と、前記大容量
メモリに新たな構造体を格納するための連続領域が確保
できなくなった時、前記大容量メモリ上の構造体で使用
中のものを、前記階層化ビットマツプの情報を使用して
前記大容量メモリ中でリロケートし、前記新たな構造体
の格納領域を確保する操作を前記外部装置が前記キャッ
ジ−メモリを用いて処理を実行するのと並行して行なう
ブロック管理ユニットと、前記キャッジ−メモリに格納
されている構造体の識別番号と前記キャッシュメモリ上
の格納番地間の変換と、前記キャッシュメモリ上に存在
しない構造体を前記大容量メモリから取ってきたり、新
たに生成された構造体を前記大容量メモリに格納する処
理を実行するキャッジ−管理ユニットとを備え、前記ブ
ロック管理ユニットが前記大容量メモリへアクセスする
のと並行して、前記外部装置が前記キャッシュ管理ユニ
ットを使用して前記キャッシュメモリをアクセスできる
ことを特徴とする構造体メモリ管理方式。