JPH02263233A

JPH02263233A - データ管理方式

Info

Publication number: JPH02263233A
Application number: JP1059390A
Authority: JP
Inventors: Hirotoshi Maekawa; 博俊前川; Hiroyuki Yasuda; 弘幸安田
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1988-12-14
Filing date: 1989-03-10
Publication date: 1990-10-26
Also published as: KR950005525B1; KR910700498A

Abstract

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

Description

【発明の詳細な説明】Ａ　産業上の利用分野本発明は、コンピュータの主記憶のデータ管理方式に関
し、特に、人工知能、数式処理、自然言語処理等の記号
処理分野で基本的かつ不可欠なリスト構造データの仮想
化を効率良く実現するものである。

Ｂ　発明の概要本発明は、コンピュータによりデータを管理するにあた
り、実記憶空間ではその実記憶空間内のアドレスにてポ
インタを表し、仮想記憶空間ではその仮想記憶空間内の
アドレスと上記実記憶空間へのアドレスにてポインタを
表し、上記実記憶空間上のノードから仮想記憶空間上の
ノードを間接参照するようにして、ノード間がポインタ
でリンクされた構造のデータを実記憶空間と仮想記憶空
間とに亘って表現し、上記ノード間がポインタでリンク
された構造のデータをそのリンク情報を用いたリスト構
造単位で実記憶空間と仮想記憶空間との間で移動させる
ことにより、人工知能、数式処理、自然言語処理等の記
号処理分野で基本的がつ不可欠なリスト構造データの仮
想記憶化を効率良く実現したものである。

Ｃ従来の技術一般に、コンピュータによる人工知能、数式処理、自然
言語処理等の記号処理分野では、リスト構造のデータを
メモリ上で管理しながら、目的の記号処理を行うように
している。

従来より、上記リスト構造のデータとしては、ノード間
がポインタでリンクされている構造を持った所謂ｐｏｉ
ｎｔｅｒ−１ｉｎｋｅｄ　ｄａｔａが広く知られている
。上記ｐｏｉｎｔｅｒ−１ｉｎｋｅｄ　ｄａｔａにおい
て、ポインタは、多くの場合一方向にだけ持ち、また、
ノードは、（ｌｈのノードへのポインタと自身のデータ
を持ち、そのポインタ数が二つの所謂２分木（ｂｉｎａ
ｒｙ　ｔｒｅｅ）構造が多い。

例えば、リスト構造のデータを扱う代表的な言語として
知られているリスプ（ＬＩＳＰ）言語では、第１３図に
リスト構造のデータ例を示しであるように、中間ノード
（Ｎｌｏ）、（Ｎｌｔ）、（Ｎ＋４）、（Ｎｌ５）、（
Ｎｌ？）。

（Ｎｚｏ）　、（Ｎｚｇ）　、（Ｎｌ４）　、　（Ｎ１
６）がポインタを二つ持ち、端末に位置するノード（Ｎ
＋＋）、（Ｎ＋＋）、（Ｎｌｉ）、（Ｎｌｓ）。

（Ｎ＋＊）、　（Ｎｒ＋）、　（Ｎｚｓ）、　（Ｎｚｇ
）　、　（Ｎｚｔ）　、　（Ｎｔ、）に具体的データを
持ち、上記端末の構成状態が情報を持っている。

また、上述のようなリスト構造のデータをメモリ上で扱
う場合は、例えば第１４図に示すように、番地付けられ
たメモリ上の記憶空間（Ｍ）にノード（Ｎｌ。）、（Ｎ
１１）、（Ｎｌり、（Ｎｌｓ）・・・・・を表現し、そ
の記憶空間（Ｍ）のアドレスにてポインタを表現するよ
うにして、コンピュータにて上記データを管理するよう
にしている。

ところで、上記記号処理分野で扱われている上記リスト
構造のデータは、切れたり繋がったり、伸びたり縮んだ
りして、そのデータ構造として与えられる情報が自在に
変化する動的構造を有し、試行１！誤的な振る舞いをす
る。

また、このようなリスト構造のデータをコンピュータに
てメモリ上で管理する場合、そのデータ構造がメモリ上
に分散され、メモリ上に新たなノードが無くなってしま
ったり、使用済で不要なノードができるので、不要なノ
ードを回収して新しいノードとして再使用するガーベジ
コレクションＣＧＣ：Ｇａｒｂａｇｅ　（：ｏｆｌｅｃ
ｔｉｏｎ）が行われる。

さらに、ガーベジコレクションを行っても実記憶空間が
足りないときには、記憶空間（Ｍ）を仮想化により拡張
するようにして、例えば第１５図や第１６図に示すよう
に、記憶空間をページ単位で管理して実記憶空間（ＲＭ
）と仮想記憶空間（ＩＭ）との間でページ単位でのデー
タ転送（ｓｗａｐｐｉｎｇ）が行われている。

Ｄ　発明が解決しようとする課題ところで、現在のコンピュータアーキテクチャは、静的
構造を有する局所的なデータを処理するようにデザイン
されており、上記記号処理分野で扱われているような上
記リスト構造のデータの処理には適さず、例えば処理対
象が動的に分散されているガーベジコレクションを実行
するのに非常に長い時間を要する。また、従来、データ
の局所性を前提として記憶空間をページ単位で管理する
ようにして記憶空間を仮想化しており、上記ページは記
憶空間上の固定領域であるが、上記リスト構造のデータ
は動的に変化していくので、その構造は複数のページ間
に複雑に入り組んでしまい、ページフォルトが頻繁に発
生し効率が悪い。特に、仮想化した記憶空間に対してガ
ーベジコレクシジンを実行した場合には、実記憶空間と
仮想記憶空間との間でページ単位でのデータ転送を行う
ために、実行効率が著しく低下する。

そこで、本発明は、上述の如き従来の実情に鑑み、人工
知能、数式処理、自然言語処理等の記号処理分野で基本
的かつ不可欠なリスト構造データの仮想記憶化を効率良
く実現することを目的とする。

Ｅ　課題を解決するための手段本発明に係るデータ管理方式は、上述の目的を達成する
ために、実記憶空間ではその実記憶空間内のアドレスに
てポインタを表し、仮想記憶空間ではその仮想記憶空間
内のアドレスと上記実記憶空間へのアドレスにてポイン
タを表し、上記実記憶空間上のノードから仮想記憶空間
上のノードを間接参照するようにして、ノード間がポイ
ンタでリンクされた構造のデータを実記憶空間と仮想記
憶空間とに亘って表現し、上記ノード間がポインタでリ
ンクされた構造のデータをそのリンク情報を用いたリス
ト構造単位で実記憶空間と仮想記憶空間との間で移動さ
せることを特徴とする。

Ｆ　作用本発明に係るデータ管理方式では、実記憶空間ではその
実記憶空間内のアドレスにてポインタを表し、仮想記憶
空間ではその仮想記憶空間内のアドレスと上記実記憶空
間へのアドレスにてポインタを表し、上記実記憶空間上
のノードから仮想記憶空間上のノードを間接参照するよ
うにして、ノード間がポインタでリンクされた構造のデ
ータを実記憶空間と仮想記憶空間とに亘って表現するこ
とによって、ポインタにて全記憶空間を表現する必要が
無くなる。また、上記ノード間がポインタでリンクされ
た構造のデータをそのリンク情報を用いたリスト構造単
位で実記憶空間と仮想記憶空間との間で移動させること
により、動的なデータを静的に区分することなく動的デ
ータ構造をそのまま反映させた状態で管理する。

Ｇ　実施例以下、本発明の一実施例について、図面に従い詳細に説
明する。

第２図は、本発明に係るデータ管理方式を適用してリス
ト構造のデータを取り扱うようにしたマルチプロセッサ
システムの概念的な構成を示すブロック図である。この
マルチプロセッサシステムは、複数のプロセッサ（ｌａ
）　、　（ｌｂ）〜（Ｉｎ）によりそれぞれメモリコン
トローラ（２ａ）　、　（２ｂ）〜（２ｎ）を介してア
クセスされる実記憶空間をなす主記憶装置（３）と仮想
記憶空間をなすハードディスク装置等の二次記憶装置（
４）とを備え、仮想化による記憶容量の拡張が図られて
いる。

なお、上記主記憶装置（３）は複数のメモリバンク（３
ａ）　、　（３ｂ）　〜（３ｎ）と上記各メモリバンク
（３ａ）　。

（３ｂ）〜（３ｎ）の接続回路（３Ａ）にて構成されて
いる。

このマルチプロセッサシステムにて取り扱うリスト構造
のデータは、実記憶空間ではその実記憶空間内のアドレ
スにてポインタを表し、また、仮想記憶空間ではその仮
想記憶空間内のアドレスと上記実記憶空間へのアドレス
にてポインタを表し、上記実記憶空間上のノードから仮
想記憶空間上のノードを間接ポインタにて参照するよう
にして、第１図に示すようにノード間がポインタでリン
クされたリスト構造のデータとして上記主記憶装置（３
）による実記憶空間（ＲＭ）と上記二次記憶装置（４）
による仮想記憶空間（ＩＭ）とに亘って表現され、上記
第１図に破線で囲んで示すようなリスト構造単位（０１
）、　（ｕｚ）で上記実記憶空間（ＲＭ）と仮想記憶空
間（ＩＭ）との間でデータ転送（Ｓｗａｐｐｉｎｇ）さ
れる。

なお、上記第１図中には、上記仮想記憶空間上のノード
を参照する間接ポインタを設定した上記実記憶空間上の
ノードを口にて示し、他のノードをＯにて示しである。

ここで、上記リスト構造のデータの具体的表現例につい
て説明する。

例えば第３図に示すように、上記主記憶装置（３）によ
る実記憶空間（ＲＭ）上に表現された９個のノード（Ｎ
、。）、（Ｎ＋＋）、（Ｎ＋ｚ）、（Ｎ＋ｆｆ）、（Ｎ
ｚ。）、（Ｎｚ＋）、（Ｎｚｚ）。

（Ｎｚｓ）　、　（Ｎｘ。）が上記実記憶空間（ＲＭ）
上の実記憶空間アドレスで表現したポインタにてリンク
されてなるリスト構造のデータは、上記第３図中に破線
にて囲んで示す４個のノード（Ｎ＋＋）、（Ｌｘ）、（
Ｎ□）。

（Ｎ２りによるリスト構造単位（Ｕｏ）を上記二次記憶
装置（４）による仮想記憶空間（Ｉ？ｌ）上に移した場
合、第４図のように表現される。

第４図において、上記仮想記憶空間（ＩＭ）上に移した
上記リスト構造単位（Ｕ、）を構成する４個のノード（
ｎ、１）、　（ｎｌｚ）、　（ｎｔ＋）、　（ｎｘｘ）
は、上記仮想記憶空間（ＩＭ）上の各ノード（ｎｔ、）
、　（ｎ−）の仮想記憶空間アドレスおよび上記実記憶
空間（ＲＭ）上の各ノード（Ｎ＋＋）、（Ｎ＋ｚ）、（
Ｎ＋３）、（Ｎｔｚ）の実記憶空間アドレスを直接表現
した各ポインタにて、上記各ノード（ｎｔｔ）、（ｎｔ
ｔ）、（Ｎｅｔ）、（Ｎｅｔ）、（ＮＩｓ）、（Ｉｂｓ
）　　とリンクされる。また、上記実記憶空間（１２Ｍ
）上の各ノード（Ｎｅｔ）、（Ｎｅｔ）は、上記仮想記
憶空間（ＩＭ）上の上記リスト構造単位（Ｕ、）の各ノ
ード（ｎ、）、（ｎｌ−）の仮想記憶空間アドレスを表
現した間接ポインタにて、上記各ノード（ｎ、）、（ｎ
ｌりとリンクされる。

上述の如きリスト構造のデータを取り扱うこのシステム
では、上記リストデータの動的な変化過程において、上
記実記憶空間（ＲＭ）上に必要なノードが無く、リスト
フォールトが発生し、そのノードが上記仮想記憶空間（
ＩＭ）上にある場合に、そのノードを含む一連のリスト
構造単位のデータを上記仮想記憶空間（ＬＭ）から上記
実記憶空間（ＲＭ）にデータ転送（Ｓｗａｐ−ｉｎ）す
ることにより、後述する手順に従ってリストインを行う
。

また、このシステムでは、上記実記憶空間（ＲＭ）上の
フリーノードの数を監視しており、上記実記憶空間（Ｒ
Ｍ）上のフリーノードが無くなると、不要なノードをフ
リーノードとして回収するガーベジコレクシロンを行い
、このガーベジコレクションによりフリーノードの数が
所定の閾（ｔＩ　Ｓ　ｈ以上になれば、本来のデータ処
理に復帰する。上記ガーベジコレクションによりフリー
ノードの数が所定の闇値ｓｈ以上にならない場合には、
その時点で上記実記憶空間（ＲＭ）上に不要なリストデ
ータへのポンダを抽出して、後述する手順に従って上記
実記憶空間（ＲＭ）から上記仮想記憶空間（ＩＭ）への
リスト構造単位のデータ転送（Ｓｗａｐ−ｏｕｔ）する
ためのリストアウド動作を上記実記憶空間（ＲＭ）上で
行う。

上記実記憶空間（１？Ｍ）上でリストアウドしたリスト
構造単位のデータ数が少なく所定の閾（！！ＳＳに満た
ない場合には、上記実記憶空間（ＲＭ）上に不要なリス
トデータへのボンダをさらに抽出して、新たなリストデ
ータのリストアウド動作を上記実記憶空間（ＲＭ）上で
繰り返し行う、そして、上記実記憶空間（ＲＭ）上でリ
ストアウドしたリスト構造単位のデータ数が上記闇値Ｓ
ｓに達すると、上記実記憶空間（ＲＭ）でリストアウド
されたリスト構造単位のデータを上記実記憶空間（Ｒ’
Ｍ　）から上記仮想記憶空間（■ＦＩ）へデータ転送（
Ｓｗａｐ−ｏｕｔ）　シ、リストアウドの動作を終了し
て、本来のデータ処理に復帰する。

上記実記憶空間（ＲＭ）から上記仮想記憶空間（ＩＭ）
へのリストアウドの動作は、リスト構造を掃査して、各
ノードのリンク数をリファレンスカウンタにより参照し
ながら間接ポインタを用いて次のように行われる。

例えば第５図に示すように、実記憶空間（ＲＭ）上の７
個のノード（Ｎｅ。）、（Ｎｅ　＋）　、（Ｎｅ　ｚ）
　、（ＮＩｓ）　、（Ｎｘ。）。

（Ｔｏ＋）、（Ｎｚｚ）間がポインタにてリンクされた
リスト構造単位（υ、。）を上記実記憶空間（ＲＭ）か
ら仮想記憶空間（ＩＭ）ヘリスドアウドする場合につい
て説明すると、先ず、上記実記憶空間（ＲＭ）上におい
て、その作業領域（ＩＩＡ）に上記リスト構造単位（Ｕ
、。）を第６図Ａ〜第６図Ｆに示すような手順でリスト
アウドする。

すなわち、先ず、上記実記憶空間（ＲＭ）上の上記リス
ト構造単位（Ｅｌ　ｔ　＠）の開始位置にあるノード例
えばノード（Ｎ１６）に着目して、第６図Ａに示すよう
に、上記ノード（Ｎｅ・）に対するリンクを実記憶空間
アドレスで表現した逆参照ポインタと上記ノード（Ｎｅ
。）のポインタにてリンクされているノード（Ｎ、）に
対するリンクを実記憶空間アドレスで示した逆参照ポイ
ンタを有するノード（ｎｌ。）を上記仮想記憶空間（Ｉ
Ｍ）に移すノードとして上記実記憶空間（ＲＭ）上の作
業領域（阿＾）に設け、上記仮想記憶空間（ＩＭ）に移
す上記ノード（ｎｅｏ）へのリンクを表現した間接ポイ
ンタを上記実記憶空間（ＲＭ）上のノード（Ｎｅ。）に
設定する。

次に、上記実記憶空間（ＲＭ）上の上記ノード（Ｎｌ。

）にリンクしていた上記ノード（Ｎｌ＋）に着目して、
第６図Ｂに示すように、上記ノード（Ｎｉ＋）に対する
リンクを実記憶空間アドレスで表現した逆参照ポインタ
と上記ノード（Ｎｅｔ）のポインタにてリンクされてい
る各ノード（Ｎｅｔ）、（Ｎｚ＋）に対する各リンクを
実記憶空間アドレスで表現した各逆参照ポインタを有す
るノード（ｎ、）を上記作業領域（Ｗ＾）に設ける。そ
して、上記作業領域（賀Ａ）の上記ノード（ｎ１１）へ
のリンクを表現した間接ポインタを上記ノード（Ｎ　１
．＋　）に設定するとともに、上記作業領域（−＾）の
上記ノード（ｎｌ。）のポインタによる上記実記憶空間
（１２Ｍ）上の上記ノード（Ｎ１２）へのリンクを該ノ
ード（Ｎ　＋　ｔ）に対応する上記作業領域（ＨＡ）の
上記ノード（ｎ、ｔ）へのリンクに移して、上記ノード
（Ｌｘ）への逆参照ポインタを上記ノード（ｎｌ、）へ
のリンクを仮想記憶空間アドレスにて表現した内容のポ
インタに変更する。

その次に、上記実記憶空間（ＲＭ）上の上記ノード（Ｎ
１１）にリンクしていた上記ノード（Ｎ、□）に着目し
て、二〇ノード（Ｎｉｚ）のポインタによるノード（Ｎ
ｉ３）へのリンクを手繰って、上記実記憶空間上゛の各
ノード（Ｎ、□）、（Ｎ’３）を上記作業領域（ＨＡ）
に移して、第６図Ｃに示すように、上記ノード（ｎ、１
）のポインタにてリンクされるノード（ｎＩｚ）　　と
、このノード（ｎＩｚ）のポインタにてリンクされるノ
ード（ｎｌ３）を上記作業領域（−八）に設ける。

次に、上記作業領域（ＨＡ）の上記ノード（ｎ、）の逆
参照ポインタにてリンクされている上記実記憶空間（Ｒ
Ｍ）上の上記ノード（Ｎｚ＋）に着目して、このノード
（ＮＺ＋）のポインタによるノード（Ｎｏ）へのリンク
を手繰ることにより、上記実記憶空間（ＲＭ）上の各ノ
ード（Ｎ２　＋）、　（Ｎ２２）を上記作業領域（ＩＡ
Ａ）に移して、第６図りに示すように、上記ノード（ｎ
、）のポインタにてリンクされるノード（ｎｚ＋）　　
と、このノード（ｎｚ＋）のポインタにてリンクされる
ノード（ｎ、）を上記作業領域（ＷＡ）に設ける。さら
に、上記作業領域（１１Ａ）の上記ノード（ｎｚ□）の
逆参照ポインタによる上記実記憶空間（ＲＭ）上の上記
ノード（Ｎｉ１）へのリンクを上記ノード（Ｎｌ＋）に
対応する上記作業領域（畦）の上記ノード（ｎ、）への
リンクに付は替える。

さらに、上記実記憶空間（ＲＭ）上の上記リスト構造単
位（Ｕ、。）の他の開始位置にある未掃査のノード（Ｎ
！。）に着目して、第６図已に示すように、上記ノード
（Ｎｚｏ）に対するリンクを実記憶空間アドレスで表現
した逆参照ポインタと上記ノード（Ｎｚ。）のポインタ
にてリンクされている上記ノード（Ｎ、）に対するリン
クを実記憶空間アドレスで示した逆参照ポインタを有す
るノード（ｎｔＪ　を上記作業領域（−Ａ）に設けると
ともに、このノード（ｎｚ。）へのリンクを表現した間
接ポインタを上記実記憶空間（ＲＭ）上のノード（Ｎｔ
Ｏ）に設定する。

そして、上記作業領域（−＾）の上記ノード（ｎｚ。）
の逆参照ポインタによる上記実記憶空間（ＲＭ）上の上
記ノード（Ｎ＋＋）へのリンクを該ノード（Ｎ＋＋）に
対応する上記作業領域（ＨＡ）の上記ノード（ｎ、、）
へのリンクに付は替えて、第６図Ｆに示すように、上記
実記憶空間上（ＲＭ）の上記ノード（Ｎ、）を上記作業
領域（紳Ａ）の上記ノード（ｎｌ、）に完全に移動させ
ることにより、上記実記憶空間（ＲＭ）上の作業領域（
ＨＡ）への上記リスト構造単位（Ｕ、。）のリストアウ
ドを終了する。

最後に、上記リスト構造単位（υ、。）のデータを上記
主記憶装置（３）による実記憶空間（ＲＭ）上の作業領
域（諭）から上記二次記憶装置（４）による仮想記憶空
間（ＩＭ）へデータ転送（Ｓｉ１ａｐ−ｏｕｔ）するこ
とにより、上記リスト構造単位（Ｕ＋Ｏ）を上記仮想記
憶空間（ＩＭ）へ第７図に示すようにリストアウドする
。

このように、間接ポインタを用いることにより上記リス
ト構造単位（υ、。）′の如き環状リスト構造も旨くリ
ストアウドすることができ、しかも、上記主記憶袋Ｗ（
３）による実記憶空間（ＲＭ）上でリストアウドしたリ
スト構造単位のデータを上記実記憶空間（ＲＭ）から上
記二次記憶装置（４）による仮想記憶空間（ＩＭ）への
データ転送（Ｓｗａｐ−ｏｕｔ）することにより、上記
仮想記憶空間（ＩＭ）に効率よく迅速にリストアウドす
ることができる。

ここで、上記実記憶空間（ＲＭ）上のノードに対するリ
ンクを実記憶空間アドレスにて表現し、また、上記仮想
記憶空間（ＩＭ）上のノードに対するリンクを仮想記憶
空間アドレスをそれぞれ各記憶空間内で表現して、それ
ぞれの記憶空間内でのリンクを直接表現した通常のポイ
ンタと、上記仮想記憶空間（ＩＭ）上のノードの仮想記
憶空間アドレスを表現した上記実記憶空間（ＲＭ）上の
ノード（Ｎ＋＋）、（Ｎｉｔ）等の間接ポインタや、上
記実記憶空間（ＲＭ）上のノードに対するリンクを実記
憶空間アドレスで表現した上記仮想記憶空間（ＩＭ）上
のノード（ｎｌ。）、（ｎｌ）等の逆参照ポインタとは
、例えばそのポインタで指されているノードの種ＩＦを
示すタグをポインタに付加しておくことにより、上記タ
グの内容にて識別される。

次に、上記二次記憶装置（４）による仮想記憶空間（団
）から上記主記憶装置（３）による実記憶空間（ＲＭ）
へのリストインは、アクセスしようとするノードが上記
実記憶空間（Ｒ？り上になく間接ボンインクにて示され
る仮想記憶空間（ＩＭ）上のノードであった場合に、次
のように行われる。

例えば、第８図に示すように、上記実記憶空間（ＲＭ）
上の各ノード（Ｎｌ。）、（Ｎｌｌ）の間接ポインタに
てリンクされた上記仮想記憶空間（ＩＭ）上のノード（
ｎｌ−）、　（ｎ＋＋）＋　（ｒ＋＋ｚＬ　（ｎＩｓ）
、　（ｎｔ−＞、　（ｎ−、）、（ｎｇｚ）によるリス
ト構造単位（Ｕ！。）を上記仮想記憶空間（■旧から上
記実記憶空間（Ｒ？Ｉ）ヘリストインする場合について
説明すると、先ず、上記リスト構造単位（Ｕｉｏ）のデ
ータ上記実記憶空間（Ｒ１’ｌ）上の作業領域（−八）
にデータ転送（Ｓｗａｐ−ｉｎ）　Ｌ／、上記実記憶空
間（ＲＭ）上において、第９図Ａ〜第９図りに示すよう
な手順で上記作業領域（ＨＡ）から上記リスト構造単位
（Ｏｘ。）のリストインの動作を行う。

すなわち、上記仮想記憶空間（ＩＭ）から上記実記憶空
間（ＲＭ）にデータ転送（Ｓｗａｐ−ｉｎ）　、された
第９図Ａに示す如き上記作業領域（ＨＡ）のリスト構造
単位（Ｕｚ。）について、先ず、上記リスト構造単位（
Ｕオ。）を掃査し、第９図Ｂに示すように、上記リスト
構造単位（Ｌｈ。）を構成している各ノード（ｎ＋＋）
＋（ｒ＋＋□）。

（ｎｌ−）、　（ｎｚ＋）＋　（ｎｚｚ）に逆参照ポイ
ンタを設定して、上記ノード（ｎ、）、　（ｎＩｓ）＋
　（ｎｌｆｆ）＋　（ｎ−５）、　（ｎ−）に対応する
各ノード（Ｎｌｌ）、（Ｎｌｚ）、（Ｎ＋３）、（Ｎｚ
＋）、（Ｔｏｗ）を上記実記憶空間（ＲＭ）上に設ける
。

次に、再度上記リスト構造単位（ＵＺ。）を掃査し、第
９図Ｃに示すように、上記作業領域（目）の上記リスト
構造単位（ＵＺ。）を構成している上記各ノード（ｎ、
−）、　（ｒ＋＋＋）、　（ｎＩｓ）＋　（ｎ＋３）、
（ｎ、ｏ）、　（ｎｚ＋）、（ｎｚｚ）の仮想記憶空間
アドレスで表現されているポインタを上記実記憶空間（
ＩｉＭ）上の上記各ノード（Ｎｌｌ）。

（Ｎｌｚ）、（Ｎ＋３）、（ｌＪｚ＋）、（Ｎｚｚ）に
リンクする実記憶空間アドレスによる逆参照ポインタに
付は替える。

そして、三度上記リスト構造単位（ＵＺ。）を掃査して
、第７図りに示すように、上記作業領域（賀Ａ）の上記
リスト構造単位（ＵｔＯ）を構成している上記各ノード
（ｎ＋ｏＬ（ｎ＋＋）＋（ｎＩｓ）＋（ｎＩｓ）＋（ｎ
ｚｏＬ（ｎｚ＋）＋（ｎ＝−）の内容を上記実記憶空間
（ＲＭ）上の各ノード（ＮＩＰ）、　（Ｎｌｌ）ｌ（Ｎ
ｌり、　（Ｎｌ３）、　（Ｎｘ。）、（Ｎ□）、（Ｎｚ
□）に移すことにより、上記リスト構造単位（Ｕ２゜）
を上記作業領域（−八）から上記実記憶空間（ＲＭ）に
全て移動し、上記二次記憶装置（４）による仮想記憶空
間（ＩＭ）から上記主記憶装置（３）による実記憶空間
（ＲＭ）への上記リスト構造単位（Ｕｚ。）のリストイ
ンを終了する。

なお、上記仮想記憶空間（ＩＭ）から上記実記憶空間（
ＲＭ）へのリストインは、上述の実記憶空間（ＲＭ）か
ら仮想記憶空間（ＩＭ）へのリストアウドと同様な方法
で行うこともできる。

ここで、上記主記憶装置（３）による実記憶空間（ＲＭ
）を上記二次記憶装置（４）による仮想記憶空間（ＩＭ
）にて拡張して処理を行う際には、上記仮想記憶空間（
ＩＭ）上のリストアウドされたリスト構造単位のノード
から上記実記憶空間（ＲＭ）上のノードへの参照がしば
しばしば発生し、例えば、第１０図に示すように、上記
仮想記憶空間（ＩＭ）上のリスト構造単位（υ、）のノ
ード（ＮＡ）から参照されている上記実記憶空間（ＲＭ
）上のノード（Ｎ、）が、上記実記憶空間（ＲＭ）上の
他のノードから参照されることなく、上記仮想記憶空間
（ＩＭ）上のリスト構造単位（ＵＣ）のノード（Ｎ、）
への間接ポインタとなることがある。

このような場合には、上記実記憶空間（ＲＭ）上のノー
ド（Ｎｌ）に対する上記仮想記憶空間（ＩＭ）からの参
照を書き替えることにより、第１１図に示すように、上
記間接ポインタを削除して、上記実記憶空間（ＲＭ）上
のフリーノードの数を増やすことが可能である。

上述の如き間接ポインタを削除するための一連の操作は
、原理的には、各々の間接ポインタへの逆参照表を作成
して、リストアウドの際にリストアウドされたリスト構
造単位内の該当する間接ポインタへの参照を書き替える
ことで実現可能である。この操作では、仮想記憶空間内
のリスト構造を操作する動作を含んでいるので、アクセ
ス時間の長い上記仮想記憶空間へのアクセスが増加する
。

そこで、このシステムでは、第１２図Ａに示すように、
仮想記憶空間（１？Ｉ）にリストアウドされた各リスト
構造単位を一括して管理するストラフチャ参照表（ＳＲ
Ｔ）と、上記仮想記憶空間（Ｉｌ＋）にリストアウドさ
れたリスト構造単位で外部ノードへの参照を管理する外
部参照表（ＸＲＴ）とを実記憶空間（ＲＭ）上に設ける
とともに、第１２図Ｂに示すように、上記仮想記憶空間
（Ｉ？Ｉ）から実記憶空間（ＲＭ）への弁型を管理する
逆参照表（ＤＲＴ）を上記実記憶空間（ＲＭ）上に設け
て、上記仮想記憶空間にリストアウドされた各リスト構
造単位間の参照を一括して扱い、上記仮想記憶空間（１
？Ｉ）へのアクセスを減少させるようにしている。

上記ストラフチャ参照表（ＳＲＴ）は、上記仮想記憶空
間（Ｒ）にリストアウドされた各リスト構造単位を特定
する情報ｓｒｔ、　ｉｄと、リスト構造単位のノードの
外部からの参照数ｒｅｆ、ｃと、上記外部参照表（ＸＲ
Ｔ）へのポインタｘｒｔが格納されており、上記外部参
照表（ＸＲＴ）の管理、検索等に用いられる。

また、上記外部参照表（ＸＲＴ、）は、リストアウドさ
れたリスト構造単位毎に割り当てられ、対応するリスト
構造単位内で、外部を参照しているノードを特定する情
報ｐｔｒ、ｉｄと、上記ノードが参照している外部のノ
ードを特定するポインタｄａｔが格納される。さらに、
上記逆参照表（ＤＲＴ）は、上記実記憶空間（ＩＩＭ）
上のノードを参照している上記仮想記憶空間（ＩＭ）上
のノードをリスト構造単位で特定するデータｐｔｒ、１
ｉｓｔと、上記上記実記憶空間（ＲＭ）上のノードを特
定するデータｄｓｔ、ｉｄが格納される。

上記各参照表（ＳＲＴ）　、　（ＸＩ？Ｔ）　、　（Ｄ
ＲＴ）のエントリは、例えば上記ストラフチャ参照表（
ＳＲＴ）はリスト構造単位のストラフチャ番号で、また
、外部参照表（ＸＲＴ）はリスト構造単位のストラフチ
ャ内アドレスで、そして、上記逆参照表（ＤＲＴ）は実
記憶空間アドレスでハシシュすれば良く、各参照表（Ｓ
ＲＴ）　。

（ＸＲＴ）　、　（ＤＲＴ）の検索などを高速化するこ
とができる。なお、被参照ノードが実記憶空間に存在し
ない場合には、上記逆参照表（ＤＲＴ）へのハツシュは
できないが、上記仮想記憶空間上のリスト構造単位のノ
ードからの逆参照ポインタを逆参照表（ＤＲＴ）へのエ
ントリとすることができる。

ここで、上述の実施例では２分木のリスト構造データの
管理を行ったが、本発明に係るデータ管理方式において
取り扱うことのできるリスト構造データは、２分木のリ
スト構造データに限定されることなく、ｎ分木構造のリ
スト構造データに拡張することができる。また、本発明
に係るデータ管理方式は、上述の実施例の如きマルチプ
ロセッサシステムのみに通用なものではなく、−船釣な
プロセッサシステムに適用することも勿論可能である。

Ｈ発明の効果本発明に係るデータ管理方式では、実記憶空間ではその
実記憶空間内のアドレろにてポインタを表し、仮想記憶
空間ではその仮想記憶空間内のアドレスと上記実記憶空
間へのアドレスにてポインタを表し、上記実記憶空間上
のノードから仮想記憶空間上のノードを間接参照するよ
うにして、ノード間がポインタでリンクされた構造のデ
ータを実記憶空間と仮想記憶空間とに亘って表現するこ
とによって、ポインタにて全記憶空間を表現する必要が
無いので、記憶容量を節約することができ実質的に記憶
容量を増加させることがきる。

また、本発明に係るデータ管理方式では、上記ノード間
がポインタでリンクされた構造のデータをそのリンク情
報を用いたリスト構造単位で実記憶空間と仮想記憶空間
との間で移動させることにより、動的データを静的に区
分することなく動的データ構造をそのまま反映させた状
態で管理するので、仮想記憶空間のアクセス回数を減ら
してメモリアクセス効率を著しく向上させることができ
る。特に、ガーベジコレクションの実行効率を顕著に高
めることができ極めて有効である。

従って、本発明に係るデータ管理方式を適用することに
よって、人工知能、数式処理、自然言語処理等の記号処
理分野で基本的かつ不可欠なリスト構造データの仮想化
を効率良く実現することができるようになる。

【図面の簡単な説明】

第１図は本発明を適用したプロセッサシステムにおいて
扱うリスト構造のデータを実記憶空間と仮想記憶空間に
亘って表現したデータ例を示す模式図、第２図は本発明
を適用したマルチプロセッサシステムの構成を示すブロ
ック図、第３図は実記憶空間に表現したリスト構造のデ
ータの具体例を示す模式図、第４図は上記第３図に示し
たリスト構造のデータを実記憶空間と仮想記憶空間に亘
って表現した具体例を示す模式図、第５図は実記憶空間
から仮想記憶空間にリストアウドするリスト構造単位の
構成例を示す模式図、第６図Ａ、第６図Ｂ、第６図Ｃ２
第６図り、第６図Ｅおよび第６図Ｆは上記第５図に示し
たリスト構造単位を実記憶空間から仮想記憶空間にリス
トアウドするための上記実記憶空間上でのリストアウド
動作の手順を説明するための各模式図、第７図は上記第
５図に示したリスト構造単位を実記憶空間から仮想記憶
空間にリストアウドした状態を示す模式図、第８図は仮
想記憶空間から実記憶空間にリストインするリスト構造
単位の構成例を示す模式図、第９図Ａ、第９図Ｂ、第９
図Ｃおよび第９図りは上記第８図に示したリスト構造単
位を仮想記憶空間から実記憶空間にリストインするため
の上記実記憶空間上でのリストイン動作の手順を説明す
るための各模式図、第１０図はリストアウドにより実記
憶空間上に間接ポインタが残存した状態のリスト構造を
示す模式図、第１１図は上記第１０図に示した間接ポイ
ンタを削除したリスト構造を示す模式図、第１２図Ａお
よび第１２図Ｂは仮想記憶空間上にリストアウドされた
各リスト構造単位を一括管理するために設けられる各種
参照表の構成を示す各模式図である。第１３図は一般的なリスト構造のデータ例を示す模式図
、第１４図はリスト構造のデータを記憶空間上に表現し
た模式図、第１５図および第１６図は従来の一般的な仮
想化にて拡張した記憶空間の構成例を示す各模式図であ
る。（ｌａ）、（ｌｂ）〜（Ｉｎ）　＝プロセッサ（２ａ）
　、　（２ｂ）〜（２ｎ）・・・・・・メモリコントロ
ーラ（３）・・・・・・・・・・・・・・・・・・主記
憶装置（３ａＬ（３ｂ）〜（３ｎ）−・・−＝（４）・
・・・・・・・・・・・・・・・・・（ＲＭ）　　・・
・・・・・・・・・・・・・・・（ＩＭ）　　・・・・
・・・・・・・・・・・・・バンクメモリ二次記憶装置実記憶空間仮想記憶空間

Claims

【特許請求の範囲】実記憶空間ではその実記憶空間内のアドレスにてポイン
タを表し、仮想記憶空間ではその仮想記憶空間内のアド
レスと上記実記憶空間へのアドレスにてポインタを表し
、上記実記憶空間上のノードから仮想記憶空間上のノー
ドを間接参照するようにして、ノード間がポインタでリ
ンクされた構造のデータを実記憶空間と仮想記憶空間と
に亘って表現し、上記ノード間がポインタでリンクされた構造のデータを
そのリンク情報を用いたリスト構造単位で実記憶空間と
仮想記憶空間との間で移動させることを特徴とするデー
タ管理方式。