JPH02224039A - 記憶装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は記憶装置に関し　特に記憶装置に対するアクセ
スと同装置　ガーベジコレクシジンのためのマーキング
を行なう回路を内蔵した記憶装置に関すん 従来の技術 ］ンピュータの利用が数値計算分野ばかりでなく、人工
知献　自然言諧処理などの応用分野に広がっていくにっ
札　それを処理するためのプログラムの実行時において
、動的に記憶領域の構造が変化するデータ構造が必要に
なってくム　それには動的記憶管理を必要とずム　その
動的記憶管理を行なう場合、不必要になった領域を回収
して再利用するガーベジコレクションという方法が使わ
れている。ガーベジコレクションで不要領域の回収を行
なう＠台の−・っの方法と（２，“−使用されている領
域にマーク付けをしでいき、このマークが付けられてい
ない領域　ずなわぢ不要領域を回収するというものであ
６ｏ　　ＪＪ上のことは、、　　Ｋｎｕｔｈ、Ｄ。

Ｅ、１ｔｒコンビユークプログラミング技術ＪＶｏ１．
１「基本アルゴリズムＪ、　Ａｄｄｉｇｏｎ−Ｗｅｓｌ
ｅｙ、　１９７３に記載されている。

発明が解決しようとする課題 近年、半導体技術の著しい発達により記憶装置の記憶容
量が増大（７ていも　これに伴ｂ〜　上述した従来の方
法ではガーベジコレクションに長時間かかって（７ま）
とい・）欠点がある。本発明の目的（上　ガーベジコレ
クシ１ンに必要なマーク付けを行なう回路を記憶装置内
部にもっことによ、って、記憶装置のデ・−タへのアク
セスと同時にマーク付けを行なうことにより、ガーベジ
コレクション処理の高速化が図れる記憶装置を提供する
ことにあ課題を解決するための手段 本発明は、　アドレス入力手段と、前記アドレス入力手
段に入力されたアドレスをデコードする第１のデコード
手段と、デー・夕を格納する２ボ・−トの格納手段と、
前記格納手段の各ワー＝ド毎に付けられたタグ欄と、前
記格納手段の第１のポートからのデ・−夕の読み出１．
を行なうための・ト段と、前記格納手段の第２のボー・
トからのデータの書き込み及び読み出１．を行なうデー
タ入出力手段と、前記第１のポートから読み出されたデ
ー・−・夕または外部から前記デ・−々入出力手段１．
ご入力されたデータを選択するセ１ノクト丁段と、前記
セ１．ノクト手段からのデータをアドレスとしてデコー
　ドする第２のデコード手段と、前記格納手段の第１の
ポ・−トからデ・−夕の読み出しを行い、第２のボ・−
トからデータの書き込み及び読ろ出しを行ない、外部ク
ロワクに同期して前記デー・タ入出力手段から外部入力
されたアドレスより遂次セレクトされたタグ欄に印付（
うを行な、うための制？、ｆｌｌ舎行へ、う３；制御手
段とを備えた記憶装置Ｃある。

作用 本発明は、前記ｉ−た構成；により、データ入出力手段
からある特定の値を設定し７、この値を゛アドレスとし
てデータの読み出しを行なうと同時にセレクトされたワ
ー　ドのタグ欄の設定（印付υ）を行１、Ｘ、前記セ１
ノクトされたワー・ドブ・−夕の値をアドレスとし、て
次のワードをセｌノクト・ずへ　そ１．で前記１１−同
様にワ・−・ドのタグ欄の設定（印イ・」け）を行うと
いう動作を繰り返していき、印付けを行なっていく。こ
の印付けは外部クロックに同期し″Ｃ１記憶装置の外部
△・データを読み出すことなく行えも　従って、ガーベ
ジコレクシ１ンに於げる印イ」けが高速に行え　ガーベ
ジコレクションの処理の高速化が図れる１、また　デー
タ格納手段とｔ、　””（：　２ボーＩ・、メモリを持
ったぬ　前記の印付ＩＪと並行（２て、ｎｆＪ記ダーク
格納手段へのデー−夕の格納および読み出［、が可能で
あム 実施例 第１図は本発明であるガーベジコレクシニ１）に於ける
印付は回路内蔵記憶装置の一実施例を示すブロック図で
あム　第１図に示す記憶装置の主要部（太　アドレス入
力手段であるアドレス入力バッフ１７と、アドレス入力
バッファ７に入力されたアドレスをテコ−・ドする第１
のアドレスデコーダ６と、書き込みと読み出しが同時に
行なえる二つのボ・−トを有限　各ワード毎にその領域
が使用中であるか否かを表すだめのタグ欄４をもった２
ポートメモリ５と、　２ポートメモリ５の第１のポート
２２からのデータの読み出しを行なうデータラッチ１と
、　２ポートメモリ５の第２のポート２３からのデータ
の書き込み及び読み出しを行なうデータラッチ９と人出
力バッファ１０からなるデータ入出力手段と、第１のポ
ート２２から読み出されたデータまたは外部から前記デ
ータ入出力手段に入力されたデータを選択するセレクト
手段である入力バッファ２と、入力バッファ２からのデ
ータをアドレスとしてデコードする第２のアドレスデコ
ーダ３と、　２ポートメモリ５の第１のポート２２から
データの読み出しを行１．Ｘ、第２のポート２３からデ
ータの書き込み及び読み出しを行な八　外部クロックに
同期して前記データ入出力手段から外部入力されたアド
レスより遂次セレクトされたタグ欄４に印付けを行なう
ための制御を行なう制御部８から構成されていも　通常
の処理であるデータの書き込みと読み出しを行なう場合
、外部からアドレス入力バッファ７をとおして制御部８
から出されるアドレス入力制御信号１４によりアドレス
ＡＯ〜Ａｎを久方ヒ　さらにこのアドレスＡＯ−Ａｎが
アドレスデコーダ６でデコードさべ　２ポートメモリ５
の一ワードを特定すム　この特定されたーワードデータ
を読み出す場合ζ上　書き込み／読み出し制御信号Ｒ／
Ｗによって読み出しを指定し　制御部８から出される第
１データ入出力ラツチ信号１５によりデータラッチ９に
保持され　制御部８から出されるデータ人出力制御信号
１６によって入出力バッファ１０をとおして外部にデー
タＤＯ〜Ｄｎが読み出されも　前記特定されたーワード
に外部からデータＤＯ〜Ｄｎを書き込む場合、書き込み
／読み出し７制御部号Ｒ／Ｗによって書き込みを指定し
　人出力バッファ１０から前記書き込みデータＤｏ”Ｄ
ｎを制御部８から出されるデータ入出力制御信号１６に
よって入力し　制御部８から出される第１データ入出力
ラツチ信号１５によってデータラッチ９に保持さ札２ポ
ートメモリ５の前記特定されたーワードに書き込まれａ
　またガーベジコレクションのマーキングを行なう場合
（入出力バッファ１０から最初のリスト要素のアドレス
をＤＯ−Ｄｎとし“Ｃ入力し、、印付は開始信号５ＦＬ
Ｇを外部から与えることにより制御部８から出される第
１データ入出力ラツチ信号１５によって前記最初のリス
ト要素のアドレスＤＯ〜Ｄｎがデータラッチ９に格納さ
れ　制御部８からのセレクト手段１２によって入力バッ
ファ２からアドレスデコーダ３に移され　ここで２ポー
トメモリ５中の一ワードが特定される。ここで、外部か
ら入力されたクロック信号ＣＬＫに同期して、特定され
）；ワードのタグ欄４に制御部８からの印付１ブ信号１
９によって１が設定され、特定されたワー・ドブ−・夕
が制御部８からの第２データ入出力ラツチ信号１３によ
って第１のポート２２をとおりデータラッチｌに格納さ
れる。更鳳　デルタラッチｌに格納されたデータと予め
設定された印−りけ終了デ・−り（ＮＩＬ）１８とがコ
ンパレータ１７によって比較され　その結果一致してい
れば一致検出信号１１が制御部８に送られ　印付けの完
了を知らせる印付は終了信号ＥＦＬＧを外部に出力し印
付けを完了すム　一致していなければ　クロック信号Ｃ
ＬＫに同期してデ・−タラッチ１に格納されているデー
タが大力バッファ２に送ら札　セレクト信］】２によっ
てアドレスデコーダ３でデコードされて２ポートメモリ
５の一ワードを特定し　印付は信号１９によってタグ欄
４に１が設定されも　第１図に示した２ポートメモリ５
にリストデータが格納されている様子を第２図に示ｔｏ
　　第２図に於゛Ｃ１各リスｌ−要素１〜７はそのリス
ト要素が現在使用中であるかを示すタグ欄４と、他のリ
スト要素のアドレスが格納される左アドレス欄３６と、
文字列データ３１の格納されているアトｌメスが格納さ
れイ）右アドレス欄３７から構成される。各リスト要素
の左アドレス欄３６．右アドレス欄３７をそれぞれ−ワ
ードずつ連続したアドレスに割当ても　リスト要素１の
左アドレス欄３６にはリスト要素２のアトｌメスが格納
されており、ポインタ３０ａによりそのこ、惠〜を示し
ている。同様にポインタ３０ｂによりリスト要素２はリ
スト要素３につながっており、リス［・要素３は書換え
前のポインタ３２によりリスト要、１につながり、さら
にリスト要素４はボイー／夕３０ｐによりリスト要素５
につながっていム　リスト要素５の左アドレス欄３６に
ｌ上　ＮＩＬが格納され　次のリスト要素につながって
いないことを示していも　また各リスト要素の右アドレ
ス欄３７はポインタ２９により文字列データ３１にそれ
ぞれつながっていも　プログラムの実行時に第２図に示
したリスト構造が変化し　リスト要素３の左アドレス欄
３６が変更され　書換え前のポインタ３２から書換え後
のポインタ３３に変更した場合について考えム　ごの場
合−書換え後のポインタ３３により、リスト要素３はリ
スト要素６につながっている。また　ポインタ３０ｄに
よりリスト要素６はリスト要素７につながっていム　リ
スト要素１から順に左アドレス欄３６を辿ってくと次に
リスト要素２、リスト要素３、リスト要素６、リスト要
素７の順に辿ることができ、最後のリスト要素７の左ア
ドレス欄３６にはＮＩＬが格納されており、これ以上先
のリスト要素に辿ることはできなし〜　従って、リスト
要素４、リスト要素５は不要リスト要素ということにな
も　以上のように構成された第１図に示すガーベジコレ
クションに於ける印つけ回路内蔵記憶装置を用いて第２
図に示したようなポインタの書換え操作によって不要な
リスト要素４，５を回収するために印付けを行なう処理
手順を示も　また　第３図にその時の印付けを行なう動
作を示すタイミング図を示す。印付けを開始するにあた
り、まず人出カバッファ１０から印付けが行なわれる最
初のリスト要素ｌのアドレスＤＯ−Ｄｎを入力し、印付
は開始信号５ＦＬＧを与えも　この５ＦＬＧ信号により
制御部８から出される第１のデ・−タ入出力うッヂ信号
１５によってリスト要素１のアドレスＤＯ〜Ｄｎがデー
タラッチ９に格納さ株　第３図に示すように制御部８か
らのセレクト信号１２がハイであるたべ　第１のバス２
０から入力バッファ２をとおりアドレスデコーダ３に移
され　ここで２ポートメモリ５中のリスト要素１の左ア
ドレス欄３６が特定される。ここで、外部から入力され
たクロックＣＬ　Ｋに同期して、　リスト要素１の左ア
ドレス欄３６のタグ欄４に制御部８からの印付は信号１
９によって１が設定さヘ　リスト要素１の左アドレス欄
３６の値が制御部８からの第２データ入出力ラツチ信号
１３によって第１のポート２２をとおってデータラッチ
１に格納されも　ここに格納された値はリスト要素２の
左アドレス欄３６のアドレスであり、これと印付は終了
データ（ＮＩＬ）１８とがコンパレータ１７で比較され
るが一致してなく、また第３図に示すようにセレクト信
号１２がローであるため、第２のバス２１のデー久　即
ち次のリスト要素２のアドレスが選択さ第１、入力バッ
ファ２をとおしてアドレスデコーダ３でデコードされ次
のリスト要素２の左アドレス欄３６が特定される。ここ
”べ　外部から入力されたクロック信号ＣＬＫに同期し
て、リスト要素２の左アドレス欄３６のタグ欄４に制御
部８からの印付は信号１９によって１が設定さ株」スト
要素２の左アドレス欄３６の値が制御部８からの第２デ
ータ入出力ラツヂ信号１３によってデータラッチ１に格
納される。ここに格納された値はリスト要素３の左アド
レス欄３６のアドレスであり、これと印付は終了データ
（ＮＩＬ）１Ｂとがコンパレータ１７で比較されるが一
致しないので更に同様の処理がなさ株　最後にリスト要
素７の左アドレス欄３６の値がデータラッチ１に格納さ
れ　コンパレータ１７によって印付は終了データ（ＮＩ
Ｌ）１８と比較した結果一致するので、一致検出信号１
１が制御部８に送ら株　印付けは完了し印付は終了信号
ＥＦＬＧが外部に出力されも　第４図に印付けが完了し
た後の様子を示す。また不要領域の回収は、　以トの印
付けが完了したあとで、タグ欄４を調べて１が設定され
ていないリスト要素４，５を回収することにより行なわ
れへ　回収作業が全て終了し、た時点ですべてのワード
のタグ欄４を０に設定ずも　データの格納のために２ポ
ートメモリ５を用いているたべ　上記で説明した印付け
の一連の動作とは全く独立にアドレスバッファ７からア
ドレスΔ０〜Ａｎを入力して第２のポート２３をとおし
て人出力バッフ７１０からデータの書き込み及び読み出
しが可能であも　以」二説明したよう鳳　本実施例（上
　データの格納手段として２ポートメモリ５を持板　こ
の２ポートメモリ５にはメモリ領域が使用中であるかど
うかを表すタグ欄４があり、外部からクロック信号を入
力することによって、遂次データを読み出しでマーク付
けを行うことにより、従来のように記憶装置から遂次デ
ータを読み出し　その値からマーク付けを行うことなく
、高速にマーク付けが行え　ガーベジコレクションの高
速化が図れる効果がある。また　ガーベジコレクション
に於ける印付は力丈　通常の記憶装置に対する書き込み
及び読み出し動作と並行して行なえ　ガーベジコレクシ
ョンのために通常の処理を中断させる必要がなくなる。

発明の効果 以上の説明から明らかなよう＆へ　本発明によれは　ガ
ーベジコレクションに於ける印付けが高速に行え　ガー
ベジコレクションの処理の高速化が図れも　また　デー
タ格納手段として２ポートメモリを持ったべ　前記の印
付けと並行し′Ｃ、データ格納手段へのデータの格納お
よび読み出しが可能であへ

【図面の簡単な説明】

第１図は本発明の一実施例を示す記憶装置のブロックは
　第２図は第１図に示しまた記憶装置内にリストデータ
が格納され印付けが行なわれる前の状態を示す皿　第３
図は印付けが行なわれる様子を示すタイミングチャート
に　第４図は印付けが完了した後の状態を示す図である
。 １．９・・・・データラッチ、　２・・・・入力バッフ
ァ、３・・・・第２のアドレスデコーダ、　４・・・・
タグ凰５・・・・２ポートメモ１九　〇・・・・第１の
アドレスデコーダ′Ｓ　７・・・・アドレス入力バッフ
ァ、　８・・・・制御餓１０・・・・人出力バッファ、
１１・・・・一致検出倍電１２・・・・セレクト信号１
３・・・・第２データ入出力ラツチ信号、１４・・・・
アドレス入力制御信号１５・・・・第１データ入出力ラ
ツチ信殊１６・・・・データ入出力制御信号　１７・・
・・コンバレー久　１８・・・・印付は終了デー久　１
９・・・・印付は信号、２０・・・・第１のバ、’Ｌ　
　２１・・・・第２のバ、Ｌ　　２２・・・・第１のポ
ート、２３・・・・第２のポート、２９・・・・文字列
データを指ずポイン久　３０ａ・・・・リスト要素２を
指すポイン久３０ｂ・・・・リスト要素３を指ずポイン
久　３０ｃ・・・・リスト要素５を指すポイン久　３０
ｄ・・・・リスト要素７を指ずポイン久　３１・・・・
文字列デー久　３２・・・・書換え前のポイン久　３３
・・・・書換え後のポイン久３６・・・・左アドレス＋
諏３７・・・・右アドレス！　　ＣＬＫ・・・・クロッ
ク倍電　Ｒ／Ｗ・・・・書き込み／読み出し制御信号、
ＳＦＩ、Ｇ・・・・印付は開始信ｕＥＦＬＧ・・・・印
付は終了信号。 代理人の氏名　、弁理士　粟野重孝　はか１名菓　ＸＩ
！ｆ ｔｙ　・− １２・〜 １５　・− １ｂ　・− １９−・− π・＝ ２Ｉ　−・− ｎ゛ ２３’゛− −賃　枚　ｌｆＩ　　信　号 セ　　し　　ウ　　ト　　惜　号 マク４−９ス）Ｈカラッチ消号 ｗ４１ナータλ出カうツチ信号 テータス出力籾ｒＩｎ鵡号 ＃１　ｆｆｔｔ［を 事ｌのバス 量２のパス 第１のポート 壕２のポート ３６−−−　　か　ア　　ド　　し　　ス　書瞬ル゛−
右アドしス慴 第 図

Claims (5)

【特許請求の範囲】
1. （１）アドレス入力手段と、前記アドレス入力手段に入
   力されたアドレスをデコードする第１のデコード手段と
   、データを格納する２ポートの格納手段と、前記格納手
   段の各ワード毎に付けられたタグ欄と、前記格納手段の
   第１のポートからのデータの読み出しを行なうための手
   段と、前記格納手段の第２のポートからのデータの書き
   込み及び読み出しを行なうデータ入力手段と、前記第１
   のポートから読み出されたデータまたは外部から前記デ
   ータ入出力手段に入力されたデータを選択するセレクト
   手段と、前記セレクト手段からのデータをアドレスとし
   てデコードする第２のデコード手段と、前記格納手段の
   第１のポートからデータの読み出しを行い、第２のポー
   トからデータの書き込み及び読み出しを行ない、外部ク
   ロックに同期して前記データ入出力手段から外部入力さ
   れたアドレスより逐次セレクトされたタグ欄に印付けを
   行なうための制御を行なう制御手段とを備えた記憶装置
   。
2. （２）データ入出力手段から外部入力されたアドレスは
   、印付けを行なう最初のリスト要素のアドレスとするこ
   とを特徴とする特許請求の範囲第１項記載の記憶装置。
3. （３）セレクト手段は、最初にデータ入出力手段から外
   部入力されたアドレスを選択し、その後第１のポートか
   ら読み出されたデータを選択することを特徴とする特許
   請求の範囲第１項記載の記憶装置。
4. （４）印付けの終了は、第１のポートから読み出された
   データと印付け終了データとを比較することにより行な
   うことを特徴とする特許請求の範囲第１項記載の記憶装
   置。
5. （５）第２のポートからのデータの書き込み及び読み出
   しと並行して、タグ欄に印付けを行なうことを特徴とす
   る特許請求の範囲第１項記載の記憶装置。