JPH0430219A - データ・リロケート処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［概要〕 コンパイラが使用する中間言語のようなポインタを含む
データ群を、ある記憶領域から他の記憶領域へ再配置す
るデータ処理装置におけるデータ・リロケート処理方法
に関し ポインタを含むデータ群の再配置を、効率的に行うこと
ができるようにすることを目的とし移動または複写対象
となる記憶領域を、複数のデータが含まれる所定の大き
さのページに分割し。

ページごとの移動または複写を行い、移動または複写し
たページごとのアドレス変換情報を持つ変換テーブルを
作成し、移動または複写したページに含まれるデータ群
中のポインタを、変換チーフルに従って更新するように
構成する。

［産業上の利用分野〕 本発明は、コンパイラが使用する中間言語のようなポイ
ンタを含むデータ群を、ある記憶領域から他の記憶領域
へ再配置するデータ処理装置におけるデータ・リロケー
ト処理方法に関する。

ソースプログラムにおいて出現した変数名２手続き名、
ラヘルなどの、ソースプログラム内での使用状況のリス
トに、オブジェクトプログラム内のアドレスを埋め込ん
だり、オブジェクトプログラム内にソースプログラムに
由来するデバッグ情報を与えたりする場合に、ソースプ
ログラムに関する情報を、ソースプログラムの解析が終
了した後まで保存しなければならない。

しかしながら、このために主記憶を使用すると巨大なプ
ログラムを処理するためには、膨大な量の主記憶が必要
となる。また、無条件に外部記憶を使用すると、小規模
プログラムを処理する場合などに、主記憶に十分余裕が
あっても５翻訳速度を低下させる原因となる。

このようなソースプログラムの解析結果である中間言語
を複写して保存する場合に、処理効率および主記憶の利
用効率を向上させる手段が望まれている。

〔従来の技術〕

ポインタを含むデータにリロケータビリティを持たせる
ためには、アドレス変換が必要である。

この機能を一般的に実現するためには、特殊なハードウ
ェアと相当大規模な管理用のソフトウェアが必要であり
、これらのもたらすオーバヘンドが。

ＣＰＵ自身の性能と実際の処理能力との単離を引き起こ
す場合も少なくなかった。

このような場合、オペレーティング・システムとの密接
なインタフェースを持たない処理プログラムにおいては
、ポインタを含むデータの再配置にあたって５次のよう
な方法が用いられていた。

１）同時に存在し得るあらゆるデータを、単一の線型空
間上にマツピングする方法（通常の仮想記憶方式を用い
る方法）。

１１）アドレスの代わりに、単純な演算でアドレスと１
対１に対応する（それ自身はアドレスでない）データを
、アドレスデータの代わりに使用し、ポインタ参照の度
に２所定の演算を行って実際のアドレスを決定する方法
。

しかし、ｉ）の方法は、オペレーティング・システムの
負荷が大きいうえ、オペレーティング・システムが得る
記憶領域のアクセス頻度は、あくまで“結果パであり、
ある記憶領域と他の記憶領域との間でアクセス頻度に圧
倒的な差があった場合にも、それが偶然の所産であるの
か、あるいは定性的な特徴であるのかを知ることができ
ない。

その一方で、１１）の方法は処理速度が著しく低下する
という問題点があるので、実用には適さないという一面
があった。以下２具体例に従って説明する。

第４図は従来技術の例を説明するための図である。

コンパイラが、ソースプログラムの解析結果として管理
する中間言語のレコードｒ１．ｒｚ、・・・には第４回
（イ）に示すように、多くのポインタ（アドレスデータ
）が含まれている。このような中間言語のレコードは、
頻繁に追加、更新、削除が行われるが、後の処理のため
に、途中結果を複写して保存することが必要になる場合
がある。

例えば、第４図（ロ）に示す記憶領域Ｓ内のレコードを
、他の記憶領域Ｓ′に複写する場合を考える。このとき
、レコードｒがレコードｒ′に移動すると、レコード「
を指す他のレコードが持つポインタ変数Ｘの内容を、レ
コードｒ′を指すように変更する必要がある。

このため、従来、レコードを複写するごとに。

複写元アドレスと複写先アドレスの対応表を作成し、全
複写が終了した時点で３作成した対応表を参照すること
により、全ポインタ変数を更新する処理を行ったり、い
わゆるハンシングなどを用いたりして、アドレス変換を
行うようにしていた。

この方法は、対応表に大きな領域を必要とするだけでな
く、対応表の検索に時間がかかり５またノ＼ソシング演
算等を用いた場合には、変換の処理時間が長くかかると
いう問題がある。

また、第４図（ハ）に示すように、全レコードｒ’＋＋
ｒｚ、・・・を、不要領域も含めてそのままの形で複写
し、ポインタ変数の更新は、−律に一定値を加算または
減算するというような線型空間上のマツピングも考えら
れているが、記憶領域に無駄が生じるという問題がある
。

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

以上のように、従来技術では、主記憶上の無駄が多くな
ったり、処理時間が長くかかるという問題があった。

本発明は上記問題点の解決を図り、ポインタを含むデー
タ群の再配置を、効率的に行うことができるようにする
ことを目的としている。

〔課題を解決するための手段］ 第１図は本発明の原理説明図である。

本発明では、ポインタを含むデータ群を他の記憶領域に
再配置する場合に、第１図（イ）に示す処理１０〜処理
１３によって、再配置したデータ群中のポインタを更新
する。

以下、第１図（ロ）に示す記憶領域２０から記憶領域２
１にデータを複写する例に従って１本発明の詳細な説明
する。

あらかじめ、移動または複写対象となる記憶領域２０を
、複数のデータレコードが含まれる所定の大きさのペー
ジＰ　Ｉ＋　Ｐ　ｔ、・・・、Ｐｆｉに分割しておく　
（処理１０）、１つのページ内に複数個のレコードカ存
在してもいいが、１つのレコードが複数のページにまた
がらないようにする。

記憶領域２０から新しい記憶領域２１に、データを複写
する場合に、処理１１により、各ページごとに複写を行
う。ページ単位に複写するのでページ内における各レコ
ードのページ先頭からの相対位置は変わらない。

各ページについて複写を行うごとに、変換テーブルＴに
、複写したページアドレス情報を設定する。例えば、ペ
ージＰ１をページＰ１′に複写した場合、ページＰ１に
対応する変換テーブルＴのエントリに、ページＰ　ｒ’
のページアドレスを設定する。同様に、他のページにつ
いても複写する。なお、有効なレコードが１つも存在し
ないページは不要ページであるので、その複写は行わな
い。

必要なページの複写が終了したならば、処理１３により
、＊写した記憶領域２１における各レコードのポインタ
部を検索し、そのポインタの内容を、変換テーブルＴに
従って更新する。この更新では、ポインタの内容から２
元の記憶領域２０におけるページアドレスを抽出し、変
換テーブルＴにおけるそのページアドレスに対応するエ
ントリを参照して、記憶領域２１の新しいページアドレ
スを求める。その新しいページアドレスにページ内変位
を加えたものを、新しいポインタの内容とする。

例えば、１ページの大きさを、４０９６ハイトとして、
レコードのアドレスを３１ビツトで表す場合、第１図（
ハ）に示すように、各レコードのアドレスは、１９ピン
トのページアドレスと１２ビツトのページ内変位とから
構成される。

そこで、記憶領域２０のベーンを、複写先の記憶領域２
１のページにマツピングする変換チーフルＴを作成する
場合、記憶領域２０のページアドレス情報を変換テーブ
ルＴ内に格納するのではなく、対象となるページが、先
頭のページＰ９，２から何番目のページであるかによっ
て、それを変換テーブルＴを参照する際のインデックス
として使用する。

すなわち、変換テーブルＴには１？ｘ写対象となる記憶
領域２０の最小アドレスのページＰ　ＰＩＩＮから、最
大アドレスのページＰ　ＭＡＸまでのページ数分のエン
トリを設け、複写対象のページが先頭から何番目のペー
ジであるかによって、複写先ページのアドレス情報を格
納するエントリを決める。

〔作用〕

第１図（ロ）に示すように、工己憶領域２０のベジＰ１
を、記憶領域２１のページＰ１′に複写しページＰ２を
ページＰ　２’に複写したとする。ページＰ２は、最小
アドレスのページＰ、０、から３番目のページであるの
で、変換チーフルＴの３番目のエントリには、ページＰ
２′のアドレスが設定される。

すべての必要なページについての複写が終わった後、記
憶領域２１に複写されたレコードのポインタを更新する
。例えば、レコード　、Ｉは、更新前には、記憶領域２
０内のレコードｒ２へのアドレスＡを持っている。この
アドレスＡを、複写後のレコードｒ２’のアドレスＡ′
に変換する必要がある。

そこでアドレスへの上位ビットにより、ページＰ２のア
ドレスを求め、そのアドレスから最小のページＰ　ＭＩ
Ｎのアドレスを引いて、それをページサイズで割る。そ
の値を変換テーブルＴのインデ／クスに利用し、ページ
Ｐ２′のアドレスを求める。

レコーＦ’　ｒ　ｚおよびレコードｒ２＋のページ内変
位ｄ、ｄ’　は、同しであるので、ページＰ２’のアド
レスに２ペ一ジ内変位ｄ’　　（＝ｄ）を加えたものを
、レコードｒ２′のアドレスＡ′とする。この結果をレ
コード　、Ｉに設定する。

他のレコードが持つポインタについての更新も。

同様に実行することができる。

変換テーブルＴは、記憶領域２０における限られたアド
レス範囲のページ数分のエントリを持てばよく、変換テ
ーブルＴに必要となる記憶容量は少ない。また、変換テ
ーブルＴを検索する場合にすべてのエントリについての
複写元アドレスの照合を行う必要がなく、ページアドレ
スからダイレクトに該当エントリを参照できるので、処
理の高速化も可能になる。

〔実施例〕

第２図は本発明の詳細な説明図、第３図は本発明の一実
施例処理フローを示す。

あるソフトウェア内部で使用されるを限個のデタレコー
１−の集合Ｒ−［ｒｓ、ｒｚ、−、ｒｓ　ｌを考える。

各レコードを″レコード内部こδ５するアドレスを表す
データのレコード内分布゛に基づいてｈ種類の型乙こ分
類する。この各々の型をＴ、とする（１≦」≦Ｎ）。

第２圓（イ）は、そのレコードの型の例を示している。

Ｔ１型レコードは、内部に３つのアドレスデータを持ち
、そのアト−レスデータのレコード内オフセットは、０
１１　＋　　０１□、０１３である。また下２型レコー
ドは、２つのアドレスデータを持ちそのアドレスデータ
のレコード内オフセットは０２１１　　ｏｚ□である。

なお、各オフセｙトＯＪ１はＴ、型のレコードに含まれ
る１番目のアドレスブタが、レコードの先頭からどれだ
けの距Ｈｃこあるかを示す定数である。

このオフセットを管理するために、テンプレートｔ、を
定義する。テンプレート１Ｊは、第２図（ロ）に示すよ
うに、ＴＪ型のレコード内のアドレスデータの分布（オ
フセットＯｊ□）を表すチーフルで実現する。

これから、　　ｆ　　（ｒ）　＝　ｆＯＪｌ、ｏ４２．
　、−１（ただし、ｒがＴ、型の場合）であるような関
数ｆを定義できる。「（「）の演算およびアドレスの再
決定を効率的に行うことができれば、データレコードの
移動の際のコストを低減できる。

処理の効率化のため、以下の仮定をおく。

（１）　　Ｔ、と１対１に対応する識別子１．を定義し
すべてのレコードｒ、はＩＪの内の】つを内部に持つ。

複写したレコードの］、により、ポインタの変換時に利
用するテンプレートシ、を選択するためである。

（２）使用可能な記憶領域を、各々同一の寸法のＬ（Ｌ
＝２’″）である連続領域Ｐ、（１≦ｋ）の面相に分割
する。各々のＰｋを″ページ″という。また各ページの
先頭アドレスは、記憶域空間上において、Ｌの４＝数と
する。

（３）１つのページ内に複数個のレコードが存在しても
構わない。しかし、１つのレコードが複数のページにま
たがって存在してはならない。

（４）記憶域空間内のページの分布は、記憶域空間上で
局所的であるとする。すなわち、ある領域の先頭アドレ
スを取り出す関数ａ　（ｘ）において　　ａ　　（Ｐ、
　　）　　＜ａ　　（Ｐｚ　　）　　＜−＜ａ　　（Ｐ
ｈ　　）＜ａ　（Ｐｋ−１）　＜ａ　（Ｐｍ−ｚ　）ま
たはａ　（Ｐ＋　）＞ａ　（Ｐ２　）　＞−＞ａ　（ｐ
ｍ　）　＞ａ　（Ｐｋ、ｌ　）＞ａ　（Ｐ’ｗ−ｚ　）
というように、各ページが、アドレスの昇順または降順
に並んでいる場合にＰ、、Ｐ、、・・・、Ｐｋが使用中
であり＋　　Ｐ　Ｘ＋ｌ、Ｐ　１１．２・・・が空き領
域であるならば１次に使用する領域はＰア、１であると
する。

また、Ｐ、、Ｐ、、・・・、Ｐｌ−、、Ｐ、。１．・・
・、Ｐｋが使用中であり、Ｐ、、ＰＫ、、、Ｐｋ。２．
・・・が空き領域であるならば１次に使用する領域はＰ
、とする。

（５）　　レコードの移動は、必ずページ単位に行う。

すなわち、あるページが他のアドレスに移動される際に
は、同一ページ内に存在するすべてのレコードも一括し
て移動される。

以上の仮定の下では、以下の規則が成立する。

（ａ）　　あるレコードｒの先頭アドレスａ　（ｒ）は
ａ　（ｒ）÷Ｌの商であるＢと、その剰余りとの論理的
な和に等しい。かつ、Ｂはいずれかのべ一ノの先頭アド
レスに等しい。

（ｂ）１≠ｊである任意のＰ、とＰ、の位置関係は内部
に含まれるレコードの内容乙こ規定されない。

すなわち、Ｐ、内でａ　（ｒ）　−ａ　（Ｐ、　）　＋
Ｄであるレコードｒが、ＰＪ内のＰ′に移動された場合
、ａ　（ｒ’　）−ａ　（ＰＪ）＋Ｄである。

（Ｃ）　　ａ　ＣＰｉ　）呻ａ　（Ｐ、　）の変換は“
アドレス空間の幅÷Ｌ個パの要素を持つテーブルの参照
により、繰り返し演算をせずに可能になる。

ここで、上記（４）の仮定から、レコードを含むページ
の集合をＳとすると、　　ａ　（Ｐ＋　）→ａ　　（Ｐ
Ｊ　）の変換に必要な変換テーブルＴは 要素数が （ａ　　（Ｐ）ＩＡＸ　）　−ａ　（ＰＭＩＮ　）　）
÷Ｌ個である。

各要素の内容が。

Ｔ”ｔ　（ａ　（Ｐ；　）　−ａ　（Ｐｌ、ｌＩＮ　）
　）　÷Ｌ］＝ａ’（ＰＪ）である。

ただし、　　ＰＭＡＸはＳ中で先頭アドレスが最大のペ
ージであり、Ｐ、ｌ１ｌｌはＳ中で先頭アドレスが最小
のページである。

Ｓ内に未使用ページＰｕが存在する場合、当然ａ　（Ｐ
ＭＩＮ　）≦ａ（Ｐ、）≦ａ　（Ｐｓａｘ　）　Ｔ：あ
るが、　Ｔ　Ｃ（ａ　（ＰＬＩ　）　　ａ　（ＰＭＩＮ
　）　）÷ｌ　ｌの値は任意である。

ページの再配置が行われる際に１　この変換テーブルＴ
を用意する。物理的な再配置が完了し、すべてのページ
移動後のアドレスが確定した時点で。

以下の処理を行う。

（１）内部のレコードｒ、の各々について、ＩＪを調べ
、テンプレートｔＪからオフセントの集合ｆ　ｏｊｌ＋
　　ｏｊ□、・・・）を決定する。

（ｉｉ）ａ　（ｒ、）＋ＯＪｋの示すアドレスの内容を
ｄｉｊｋ　とするとき、ａ；ｉｂをＢ　、Ｊｋ＋　Ｄ　
ｒｉｋに分解する。

（■）　Ｔ［（Ｂ；＝ｈ　−ａ　（Ｐｌ、ｌｌＮ　）　
）　＋Ｌｉ　＋Ｄ１Ｊｋを新しいアドレスとする。

例えば１第２図（ハ）に示す記憶領域２０のＰ。

を、記１１！領域２１のＰＪに再配置したとする。元の
レコードｒ。が、このＰ１中のレコード「３に対するポ
インタを持っているとすると、それに対応する再配置後
のレコード「。′が持つポインタを、レコードｒお′を
指すように変換する必要かある。

この場合、元のＰ、のアドレスａ　（Ｐ、　）からＰＭ
ＩＮ（図示省略）のア）レスａ　（ＰＭＩＮ　）を弓き
、それを１−で割った値を添字として変換チーフルＴを
参照する。そこから得た値ａ　（Ｐ、　）とレコードｒ
ｋのページ内変位ｄを加えて、変更すべきａ　（ｒｋ’
　）を求める。

第３図は１本発明の一実施例シこ係るデータ再配置の処
理フローを示している。以下の説明における■〜■は、
第３０に示す処理■〜■に対応する。

■　（ＰＭＡＸ　−ＰＨ１，）　／Ｌ個の要素を持つ大
きさの変換テーブルＴを用意する。

■　処理対象のページＰを、Ｐ′で始まる領域に複写す
る。

■　Ｐ′のアドレスを、変換テーブルＴの先頭から［（
Ｐ−Ｐ□１１）／ＬＪ番百のエントリに設定する。

■　まだ、複写していないページがあれば、処理■へ戻
り、すべて複写したならば、処理■へ移る。

■　Ｐ′で始まる領域から未処理ページを取り出す。

■　取り出した未処理ページから、未処理レコードを取
り出す。

■　レコード中の型の識別子から、テンプレートを決定
する。

■　テンプレートから得たオフセントで示されるポイン
タ変数Ａについて、変換テーブルＴの［（Ａ−Ｐ□ｓ）
／Ｌ］番目のエントリから得た値と、Ａをして割った剰
余とを合わせて、新しいポイント値Ａ′を求め３元のポ
インタ変数に代入する。

■　レコード内のすべてのポインタ変数について処理し
たかどうかを判定し、未処理データがあれば１次のオフ
セントについて処理■を繰り返す。

ａＯｌ）ルコードについての処理が終了したならばペー
ジ内に未処理レコードがあるかどうかを判定する。未処
理レコードがあれば、処理■へ戻って同様に処理を繰り
返す。

＠　１ページについての処理が終了したならば。

他に未処理ページがあるかどうかを判定する。

未処理ページが残っていれば、処理■へ戻って次のペー
ジについて同様に処理を繰り返す。全ページについての
処理が終了したならば、データの再配置処理を終了する
。

以上のデータ再配置におけるアドレス変換は。

オペレーティング・システムにおけるメモリ管理のよう
に、非常に高い頻度でデータの主記憶上での移動が起こ
る場合には不適当であるが、マルチフェーズ構成のコン
パイラ、あるいは類ｆ以の構造を持つソフトウェアのよ
うに、記憶域へのアクセス頻度の変動が時系列的かつ定
性的な場合には。

オペレーティング・システムによるアクセス頻度の監視
よりは少ないコストで実現が可能である。

〔発明の効果〕

以上説明したように、本発明によれば、データの再配置
に伴う静的なアドレス変換を一括して高速に行うことが
でき、また、大量の作業域を必要としないので、王記憶
の有効利用を回ることが可能になる。

【図面の簡単な説明】

第１図は本発明の原理説明図 第２図は本発明の詳細な説明図 第３図は本発明の一実施例処理フロー 第４図は従来技術の例を示す。 図中、１０〜１３は本発明に係る処理、２０゜２１は記
憶領域、Ｔは変換テーブルを表す。 特許出１人　富士通株式会社 代　理　人　　弁理士　小笠原吉義（外２名）本部ＩＩ
Ｐｌり片理詰１図 第　１　区 すシフ０レート デンフルート 崎 大Ｌ 口［■］石ニー 区口面Ｔ口 （ＣＩ） 勇′了ドレスデ２夕ｒ【 滲光明の一亥他任１を光門図 ≧ト奈ａＲ／１４！イラ・１ヌ四ｉす１フロー＄　３　
図

Claims (1)

1. 【特許請求の範囲】 １、ポインタを含むデータ群を、ある記憶領域から他の
   記憶領域へ移動または複写し、移動または複写したデー
   タ群中のポインタを移動または複写結果に合わせて更新
   するデータ処理装置におけるデータ・リロケート処理方
   法において、 移動または複写対象となる記憶領域を、複数のデータが
   含まれる所定の大きさのページに分割しておき（１０）
   、 ページごとの移動または複写を行い（１１）、移動また
   は複写したページごとのアドレス変換情報を持つ変換テ
   ーブル（Ｔ）を作成し（１２）、移動または複写したペ
   ージに含まれるデータ群中のポインタを、変換テーブル
   （Ｔ）に従って更新する（１３）ことを特徴とするデー
   タ・リロケート処理方法。 ２、前記変換テーブル（Ｔ）は、移動または複写対象と
   なる記憶領域における先頭のページアドレスから最終の
   ページアドレスまでの大きさを、１ページの大きさで割
   った数分のエントリを有し、各エントリに、対応する移
   動または複写先のページアドレスを設定するようにした
   ことを特徴とする請求項１記載のデータ・リロケート処
   理方法。