JPH0436422B2

JPH0436422B2 -

Info

Publication number: JPH0436422B2
Application number: JP61056581A
Authority: JP
Inventors: Masami Yamazaki
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1986-03-14
Filing date: 1986-03-14
Publication date: 1992-06-16
Also published as: JPS62221748A

Description

【発明の詳細な説明】〔目次〕概要産業上の利用分野従来の技術（第５図）発明が解決しようとする問題点問題点を解決するための手段（第１図）作用実施例 (a) 実施例の構成（第２図、第３図） (b) 実施例の動作（第４図）発明の効果〔概要〕複写ガーベジ・コレクシヨン方式を使用する
Lisp処理系において、ガーベジ・コレクシヨンの
対象となる記憶域であるセル領域を管理するセル
領域管理テーブルと、前記セル領域管理テーブル
を作成す記憶域管理手段と、ガーベジ・コレクシ
ヨン処理を行うガーベジ・コレクタを設け、前記
記憶域管理手段が前記セル領域を３以上の領域に
分割して各分割領域毎に前記セル領域管理テーブ
ルにより現在使用中の領域、複写用の領域、自由
セル数及び不要セル数を管理し、前記ガーベジ・
コレクシヨンを行う場合、前記ガーベジ・コレク
クタが前記分割領域の１つの複写用セル領域とし
て用い、その他の分割領域のうちその不要セルの
もつとも多い分割領域を複写対象として不要セル
を自由セルに再生するものである。

〔産業中の利用分野〕

本発明はガーベジ・コレクシヨン方式に係り特
にLispおよびそれを該言語とした上位言語
（Plolog等）処理系において複写式ガーベジ・コ
レクシヨンを行うとき、これを高速に遂行できる
ようにしたものに関する。

Lisp（リスト・プロセツサ）言語で制御される
Lisp処理系のデータ処理装置では、データやプロ
グラムがリスト構造で表わされている。これはセ
ルと呼ばれるポインタの対で構成されている。

〔従来の技術〕

従来の複写式ガーベジ・コレクシヨンを採用す
るLisp処理系では、第５図に示す如く、セル領域
をＡ、Ｂに２分割し、一方を処理系の自由セル領
域としてセルの作成に使用し、他方をガーベジ・
コレクシヨン用の複写用セル領域として使用して
いる。第５図は、Ａが自由セル領域として使用さ
れ、Ｂが複写セル領域として使用中のケースであ
る。

データ処理の進行にともなつてセルを作成する
ことが必要なときには自由セル領域を使用する。
そしてセルが不必要となつたとき、そのセルに不
要フラグを記入してこれを表示する。

このようにしてデータ処理が進行し、自由セル
領域Ａがセルで満され、新しいセルに対して割当
てる自由領域がなくなると、その自由セル領域Ａ
において使用中のセルのみを複写用セル領域Ｂに
コピーする。このとき不要フラグの記入されたセ
ルはコピーされず、その不要なセルの部分は圧縮
されるので、領域Ｂには新しいセルに割当てるこ
とのできる領域が得られることになる。このよう
にしてガーベジ・コレクシヨンが行われると、今
度は逆にＢが自由セル領域として使用され、Ａは
複写用セル領域となる。

〔発明が解決しようとする問題点〕

このように、従来の複写形のガーベジ・コレク
シヨン方式では、セル領域を２分割して使用して
いるため、処理系の自由セル領域が全セル領域の
半分になつて大量のデータを取扱うことができな
い。またガーベジ・コレクシヨンの際に、全自由
セル領域をサーチして、不要フラグの記入された
不要セルを検出し、これを除いて使用中のセルを
複写用セル領域に圧縮して複写するので、ほとん
ど全仮想空間へのアクセスとなり、その結果ペー
ジフオルトが多発したり、プログラムのような固
定的な部分的なセル領域の無駄な複写などで処理
速度が低下する等の問題点がある。

本発明の目的は、これらの問題点を解決するた
め、自由セル領域が広くできるのみならず、もつ
と速くガーベジ・コレクシヨンすることが可能な
ガーベジ・コレクシヨン方式を提供するものであ
る。

〔問題点を解決するための手段〕

前記目的を達成するため、本発明では、第１図
に示す如く、セル領域を複数の区分（この例では
４区分）に分割し、その１つを複写用セル領域と
し他を自由セル領域とする。またセル領域管理テ
ーブルを作成する。このセル領域管理テーブルに
は、複写用セル領域がどれか、また現在使用中の
自由セル領域がどれか、自由セル領域の区分毎の
不要フラグが記入された不要セル数等が記入され
ている。第１図のセル領域テーブルは、実線丸印
で示す如く、使用中の区分がNo.３であり、複写用
セル領域がNo.４であることを示している。

〔作用〕

第１図の状態で使用中の区分No.３に新しいセル
を記入する自由領域がなくなれば、各区分毎の不
要セル数m₀、m₁、m₂を比較して、その最大の区
分をガーベジ・コレクシヨン対象とする。もし、
m₁が最大であれば、区分No.２の使用中のセルを
区分No.４にコピーし、今度は使用中の区分がNo.４
であることおよび複写用セル領域が区分No.２であ
ることを、点線丸印の如く表示する。このように
して、ガーベジ処理範囲を限定でき、またプログ
ラムのような固定的データが多く記入されている
区分は不要セル数が少ないので、このようなもの
を複写することはほとんどない。

〔実施例〕

本発明の一実施例を第２図〜第４図にもとづき
説明する。

第２図は本発明の一実施例構成図、第３図はそ
のセル領域管理テーブルの詳細図、第４図は本発
明の動作説明用フローチヤートである。

(a) 実施例の構成第２図において、１はアプリケーシヨン・プロ
グラム、２はLispインタプリタ、３は記憶域管理
部、４は入出力制御、５はガーベジ・コレクタ、
６はセル領域管理テーブル、７はOS部、８はメ
モリ空間、９は表示部、１０は外部フアイルであ
る。

アプリケーシヨン・プログラム１は、Lispで記
述されたユーザ・プログラムであり、Lispインタ
プリタ２はこのアプリケーシヨン・プログラムを
解読し、その実行を行うものである。

記憶域管理部３はLisp処理系に割当てられたメ
モリ空間を管理するものであり、例えばLispイン
タプリタ２から要求のあつた記憶域つまりセル領
域を与えたり、不要セルに不要フラグを記入した
り、セル領域管理テーブルを作成したり、セル領
域がないときはガーベジ・コレクタ５を起動して
ガーベジ・コレクシヨンを行うような動作を行う
ものである。

入出力制御部４は表示部９にデータを表示した
り、外部フアイル１０とデータを入出力処理を行
うものである。

ガーベジ・コレクタ５はセル管理テーブル６を
参照してガーベジ・コレクシヨン処理を行い不要
なセル領域を回収し、セル領域のメモリ空間の圧
縮を行うものである。

セル管理テーブル６は、セル領域の状態を表示
するテーブルであつて、第３図に示す如く、現在
複写先に用意されている区分を示すフラグ（実線
丸印）、現在セルを新たに生成するときに使用す
る自由セル領域となる区分を示すフラグ（実線丸
印）、各区分における使用可能なセル数を示す自
由セル数、不要セル数、各区分の先頭アドレスを
示すアドレス情報等が記入されるものである。な
おこの例ではセル領域を４区分に分けて使用する
例について説明するが、３区分以上であればいく
つに分けてもよい。

OS部７はデータ処理全体を総合的に制御する
ものであり、オペレーシヨン・システムを動作さ
せるものである。

メモリ空間８は、第３図に示す如く、セルが記
入されるセル領域を有する。このセル領域はこの
例ではNo.１〜No.４の４つに区分されており、その
うち３つが自由セル領域として使用され１つが複
写用セル領域として使用される。これらの各区分
のセル領域は、前記セル領域管理テーブル６によ
り管理されている。そして最初は、例えば区分
１、２、３の順で使用される。

(b) 実施例の動作本発明の動作について、第４図のフローチヤー
トにもとづき、地図を参照しつつ説明する。

Lispインタプリタ２がアプリケーシヨン・プ
ログラム１を実行するとき、セルの生成が必要
のとき、記憶域管理部３は、セル領域管理テー
ブル６を参照して、使用フラグで指示される使
用中のセル領域区分の自由セル数をみてこれに
空きがあるか否か判断する。空きがあれば使用
中のセル領域の区分から必要セルを割り当て
る。そしてこれに応じて自由セル数を書き直
す。なお、最初は、区分No.１より使用するの
で、最初にセル領域要求が行われるときセル領
域区分No.１の項目に使用中フラグを立て、これ
に割当てを行うことになる。

前記において、そのとき使用中のセル領域
区分に空きがなければ、例えば区分１のn₀＝０
のときは、記憶域管理部３は他の区分の自由セ
ル数をチエツクする。これにより他の区分に空
きがあればその自由セル数最大のセル領域区分
を使用中セル領域とし、これにより必要セルを
割当てる。

しかしながら全てのセル領域区分に空きがな
いとき、つまり第３図で、n₀、n₁、n₂がいずれ
も０のとき、記憶域管理部３はガーベジ・コレ
クタ５を起動され、ガーベジ・コレクシヨンを
行わせる。これにより、ガーベジ・コレクタ５
は、セル領域管理テーブル６の不要セルの不要
セル数m₀、m₁、m₂をチエツクして、その最大
のセル領域区分を選択する。例えばm₁が最大
のとき区分No.２を選択する。

これによりガーベジ・コレクタ５は、まず区
分No.２における不要セル以外のセル、つまり使
用中のセルを複写用セル領域である区分４に複
写する。このとき不要セルの部分は圧縮されて
複写される。

それからガーベジ・コレクタ５は、区分No.４
における自由セル数として区分No.２における不
要セル数を記入し、また区分No.４の不要セル数
を０とする。

次にガーベジ・コレクタ５は、複写用セル領
域区分として区分No.２に第３図の点線丸印で示
す如くフラグを記入する。そして使用中のセル
領域区分として、区分No.４に同様にフラグを記
入する。このようにしてガーベジ・コレクシヨ
ンが行われたあとで、記憶域管理部３は、前記
−における空きのなかつた要求に対し、こ
の新しい使用中セル領域の区分No.４から必要セ
ルを割当てることになる。

このように、セル領域管理テーブルをみなが
ら、前記のことを繰返し、ガーベジ・コレクシヨ
ンが行われることになる。

前記説明は自由セル領域の自由セル数がすべて
０のときに行われるセル領域要求のときのガーベ
ジ・コレクシヨンについて説明したが、明示的に
起動されたときのガーベジ・コレクシヨンも同様
である。尚、明示的起動とは、アプリケーシヨ
ン・プログラムで空き領域が存在するか否かのチ
エツク等の為に、ガーベジ・コレクシヨンを強制
的に起動し、その後のセル領域の空き領域を調べ
るために実行するものである。

それから前記説明は全セル領域を４分割した例
について説明したが、勿論本発明はこれのみに限
定されるものではない。全セル領域をｐ個（ｐ≧
３）に分割管理し、その内の１個を複写用領域と
することにより、自由セル領域と全セル領域の比
率をｐ−１／ｐとし、自由セル領域を拡大し、ま
たガーベジ・コレクシヨンを１個の自由セル領域
区分と複写用セル領域間に限定することができ
る。

〔発明の効果〕

本発明によれば全セル領域を２分割よりも多く
分割してその１つを複写用セル領域としたので、
自由セル領域が広くなりメモリ空間を有効に使用
することができる。またガーベジ・コレクシヨン
を行う領域が従来のものに比較して局所的に小さ
くなるので、高速化することができる。しかもプ
ログラム等の固定的なセルが多いセル領域区分は
その区分内に不要セルが少ないことになり、ガー
ベジ・コレクシヨンの対象より外されることが多
く、無駄な複写を防止することができる。このよ
うに本発明によれば、自由セル領域を拡大でき、
ガーベジ・コレクシヨンも比較的高速に実行でき
るので、大規模データの取扱いや、処理の高速化
等に便利なものを提供することなる。

【図面の簡単な説明】

第１図は本発明の原理説明図、第２図は本発明
の一実施例構成図、第３図はそのセル領域テーブ
ル、第４図は本発明の動作説明フローチヤート、
第５図は従来のガーベジ・コレクシヨン方式説明
図である。１……アプリケーシヨン・プログラム、２……
Lispインタプリタ、３……記憶域管理部、４……
入出力制御部、５……ガーベジ・コレクタ、６…
…セル領域管理テーブル、７……OS部、８……
メモリ空間、９……表示部、１０……外部フアイ
ル。

Claims

【特許請求の範囲】１複写ガーベジ・コレクシヨン方式を使用する
Lisp処理系において、ガーベジ・コレクシヨンの対象となる記憶域で
あるセル領域を管理するセル領域管理テーブル６
と、前記セル領域管理テーブル６を作成する記憶域
管理手段３と、ガーベジ・コレクシヨン処理を行うガーベジ・
コレクタ５を設け、前記記憶域管理手段３が前記セル領域を３以上
の領域に分割して各分割域毎に前記セル領域管理
テーブル６により現在使用中の領域、複写用の領
域、自由セル数及び不要セル数を管理し、前記ガーベジ・コレクシヨンを行う場合、前記
ガーベジ・コレクタ５が前記分割領域の１つを複
写用セル領域として用い、その他の分割領域のう
ちその不要セルのもつとも多い分割領域を複写対
象として不要セルを自由セルに再生することを特
徴とするガーベジ・コレクシヨン方式。