JPH01303527A - 共有資源の管理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は共有資源の管理方法に関し、特に電子計算機上
のマルチプロセス、マルチプログラミング環境において
、並行処理を行うプ凸セス間で資源を共有するためにア
クセスを直列化することに係る、大量の共有資源を対象
とする共有資源の管理方法に関する。

〔従来の技術〕

共有資源に対するアクセスの排他制御は、一般に「ロッ
ク」および「アンロック」操作と呼ばれる命令系列によ
って実現され、通常、オペレーティングシステムの一機
能として提供される。この方法では、アクセスに競合が
発生した場合、ロックを獲得したプロセス以外のプロセ
スは、処理を中断して待機しなければならない。しかし
、このような中断は、特に、複数の命令プロセッサが主
記憶を共有する密結合型のマルチプロセッサ環境１こお
いては、しばしば、重大なオーバヘッドとなる。

上述のようなロックなしで並行処理プロセス間のアクセ
スを直列化する方法としては、例えば、特開昭６２−９
２０６１号公報に開示されているように。

プロセス間の競合があるときは、処理を競合する他のプ
ロセスの一つに伝達するものがある。この方法によれば
、主記憶上のデータリストに対する要素の検索、追加、
削除を、プロセスの中断なしに行うことが可能である。

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

上記従来技術は、ポインタチェーンでつながれた一次元
のリスト構造のデータを主な対象としている。しかし、
このようなデータリストは、順検索および要素の数が少
ない場合の直接検索には適しているが、検索オーバヘッ
ドが要素数に関して線型に増加するため、大量の要素に
対してランダムなアクセスが発生するような場合には、
必ずしも最適のデータ構造ではない。

大量の要素に対してランダムなアクセスが発生するよう
な場合に適したデータ構造としては、高速なデータ検索
手段であるハツシングの手法を用いることが可能なもの
が望ましいが、上記従来技術は、このようなデータ構造
には適用できないという問題があった。

本発明は上記事情に鑑みてなされたもので、その目的と
するところは、主記憶上の大量のデータ要素を高速にア
クセスするのに適したデータの管理を、マルチプロセッ
サ環境においてロックなしで行うことが可能な共有資源
の管理方法を提供することにある。

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

本発明の上記目的は、並行処理を行うプロセス間での共
用資源要素に対するアクセスをハツシュテーブルにより
管理する方法において、前記ハツシュテーブルの各エン
トリは、資源要素へのポインタ情報と、ハツシュテーブ
ルへの追加の発生を記憶するカウンタ情報と、テーブル
走査回数を制限するためのカウンタ情報とを含み、前記
ハツシュテーブルのエントりを、主記憶上の状態変数を
参照しその値に応じて状態変数を更新する不可分の動作
を実行する命令により更新することを特徴とする共有資
源の管理方法により達成される。

〔作用〕

上記ハツシュテーブルエントリ中の、要素の追加を記憶
するカウンタ情報（以下、簡単のため「追加カウンタ」
という）は、あるプロセスがハツシュテーブルにデータ
要素を追加しようとする動作中に、並行する他のプロセ
スが同一のハツシュ値を持つデータ要素を追加しなかっ
たかどうかを検証する手段を与える。これにより、ハツ
シュテーブルへの、同一データ要素の二重登録を防ぐこ
とができる。また、追加カウンタをハツシュテーブル全
体に対して一つ設けるのではなく、テーブルエントリ毎
に持たせることにより、追加カウンタへのアクセスの競
合発生の確率を低減できる。

一方、テーブルサーチ回数を制限するためのカウンタ情
報（以下、「サーチカウンタ」という）は、与えられた
キー情報を基に、ハツシュテーブルに登録されているデ
ータ要素を検索する場合に、最悪どの程度のハツシュテ
ーブルエントリを走査しなければならないかを示すもの
である。これにより、特定のデータ要素の登録の有無を
、全テーブルを走査せずに、高速に判定することができ
るようになる。

これらの情報を含むハツシュテーブルエントリの全体ま
たは一部の更新には、前述の、主記憶上の状態変数を参
照してその値に応じて状態変数を更新する不可分の動作
を実行する命令を用いる。

こうすることにより、前述のカウンタ情報やポインタ情
報の一貫性が保証される（通常の、ロード／スト？系の
命令を用いると、状態変数の参照から更新の間に、他の
プロセスがその状態変数を更新できるため、データの整
合性が保てない）。

〔実施例〕

以下１本発明の実施例を図面に基づいて詳細に説明する
。

第１図は、本発明の一実施例を示すコンピュータシステ
ムのブロック図である。第１図においては、並行に動作
する複数のプロセス１０が、データ要素プール４０中の
各データ要素４１に対して、ハツシュテーブル操作論理
２０を介してアクセスを行う例が示されている６ハツシ
ユテ一ブル操作論理２０は、ハツシュテーブル３０中の
ハツシュテーブルエントリ３１を操作することにより、
複数プロセス１０からのデータ要素４１へのアクセスを
直列化する。

データ要素４１は、複数プロセスで共用されるシステム
資源を主記憶上で表現するものであれば、何でも良い。

このようなシステム資源の例としては、仮想記憶システ
ムにおける主記憶フレーム。

ファイル管理システムにおける入出力バッファ等がある
。本発明は、これら主記憶上の有限個の、しかし、大量
のデータ要素を、マルチプロセッサ環境において効率良
くアクセスする手段を供給するものである。

本発明は、主記憶上の状態変数を参照し、その値に応じ
て状態変数を更新する不可分の動作を実行する命令を有
する任意のプロセッサ上で実現できる。このような命令
は、多くのプロセッサが備えており、例えば、ＨＩＴＡ
ＣＭシリーズ（（株）日立製作所商品名）処理装置にお
いては、Ｃ８（Ｃｏｍｐａｒｅ　ａｎｄ　Ｓｗａｐ）、
ＣＤ　Ｓ　（Ｃｏｍｐａｒｅ　Ｄｏｕｂｌｅａｎｄ　８
％１ａｐ）命令が、これに相当する。上記命令の詳細に
ついては、（株）日立製作所発行のマニュアルｒＨＩＴ
ＡｃＭシリーズ処理装置」に記載されている。以下、本
実施例の説明には、上記２つの命令を用いる。この２つ
の命令の異なっている点は、ＣＳ命令では語長の状態変
数を扱うのに対して、ＣＤＳ命令では倍語長の状態変数
を対象とする点である。

ハツシュテーブル操作論理２０は、要素的機能として、
データ要素の検索、追加、無効化および削除の機能を含
む。後述するように、これらの要素機能を組合せて、よ
り高度な複合機能を実現することは自由である。上記各
要素機能の詳細および複合機能の例については、後述す
る。

第２図は、ハツシュテーブルエントリの内容を示すもの
である。ハツシュテーブルエントリは、データ要素への
ポインタとサーチカウンタと追加カウンタから成る。ハ
ツシュテーブルエン１−りは倍語長であり、前述のＣＤ
Ｓ命令により更新される。データ要素へのポインタは１
語であり、Ｃ８命令により更新される。サーチカウンタ
と追加カウンタはそれぞれ半語長であり、この２つのカ
ウンタは同時にＣ８命令により更新される。各フィール
ドの長さと配置は、使用するプロセッサの命令仕様によ
り異なっていて良いが、最低限ハツシュテーブルエント
リ全体をＯ８命令またはＣＤＳ命令に類似した命令で更
新できる必要がある。

追加カウンタは、そのハツシュテーブルエントリをホー
ムポジションとするデータ要素が、ハツシュテーブルに
登録されたときにカウントアツプされる。カウンタが最
大値まで使用された場合にはラップアラウンドする。こ
こで、ホームポジションとは、１回目のハツシングで決
定されたハツシュテーブルエン１−りのことをいう。あ
るデータ要素をハツシュテーブル中に登録しようとする
とき、ホームポジションは既に他のデータ要素によって
占有されている場合（衝突の発生）がある。この場合、
データ要素は、オーバフローポジションに登録される。

ホームポジションおよびオーバフローポジションを決定
するハツシングのアルゴリズムは、どのようなものを用
いても良い。

追加カウンタは、あるプロセスがデータ要素をハツシュ
テーブルに追加しようとするときに、他のプロセスが同
一のホームポジションを有するデータ要素の追加を並行
して行っていないかを確認するために使用される。追加
論理は、入力として与えられる追加カウンタ値を退避し
ておき、追加処理の終了時点で現在の追加カウンタ値と
退避したカウンタ値を比較する。両者が等しければ現在
のカウンタ値に１を加えたものを新しい追加カウンタ値
とし、等しくなければ、競合発生を要求元に知らせる。

この比較とカウンタ値の更新は、Ｃ８またはＣＤＳ命令
により不可分の一動作として実行される。

サーチカウンタは、そのハツシュテーブルエントリをホ
ームポジションとするデータ要素が何個ハツシュテーブ
ル中に登録されているかの上限を示すものである。サー
チカウンタは、採用したハツシングアルゴリズムに従っ
てデータ要素の検索を行う場合に、Ｉ＆悪どれだけのハ
ツシュテーブルエントリを走査しなければならないかの
目安を与える。

第３図は、データ要素の内容を示したものである。各デ
ータ要素はそのキーによって一意に識別されるが、デー
タ要素とキーの対応は固定的でなくても良い。そのデー
タ要素をハツシュテーブルから削除してしまえば、デー
タ要素中のキーを変更して別データを表現するようにし
て構わない。

これをデータ要素のリプレースと呼ぶ。フラグはデータ
要素の状態を示すものであり、本発明の具体的応用毎に
適した内容を設定すれば良い１本実施例では、そのデー
タ要素の内容が無効であることを示す無効インジケータ
を設けている。ユーザカウンタは、そのデータ要素を現
在アクセスしているプロセスの多重度を示す。フラグお
よびユーザカウンタは１語中に納められ、Ｃ８命令によ
って更新される。データ要素の他のフィールドは、任意
である。本実施例では、データ要素の削除論理を高速に
するため、ハッシユテーブルの登録位置、すなわち、本
データ要素が登録されているハツシュテーブルエントリ
のアドレス、ハツシュサーチ回数、すなわち、何回目の
ハツシングによって登録位置を見つけたか、および、ホ
ームポジションをセットするフィールドを設けている。

第４図から第６図は、同一のホームポジションを持つ２
つのデータ要素４２と４３が、ハツシュテーブルに登録
される様子を示している。ここで、データ要素４２と４
３のホームポジションは、ハツシュテーブルエントリ３
２であり、ハシシテーブルエントす３３は、オーバフロ
ーポジションである。第４図では、まだ、データ要素は
１つも登録されていない。第５図では、データ要素４２
がホームポジション３２にＷｔａされ、サーチカウンタ
、追加カウンタが、それぞれカウントアツプされた状態
が示されている。第６図は、第５図の状態で更にデータ
要素４３を追加した場合を表わしている。この場合、デ
ータ要素４３はオーバフローポジションに登録される。

ここで注意すべき点は、データ要素４３をハツシュテー
ブルエントリ３３に５１　ｋｋしたとき、オーバフロー
ポジションのサーチカウンタおよび追加カウンタは変化
せず、ホームポジションのカウンタが更新されているこ
とである。

以下、各々のハツシュテーブル操作論理について、流れ
図を参照しながら詳細に説明する。ただし、本実施例に
添付しである流れ図では、図が必要以上に複雑になるの
を防ぐために、細かなエラー処理等は省いである。

〔検　索〕

検索論理の流れ図を、第７図に示す。検索論理の入力は
、検索対象データ要素のキーであり、このキーを基にハ
ツシングを行って、ホームポジションを決定する（ステ
ップ１００１）。ハツシングのアルゴリズムは、どのよ
うなものでも良い。ホームポジションが求まれば、その
ハツシュテーブルエントリのサーチカウンタを作業変数
■に設定する（ステップ１００２）。Ｉ＝Ｏであれば、
データ要素が見つからなかった旨のリターンコードを設
定してリターンする（ステップ１００３）。Ｉ＞Ｏであ
れば、ハツシュテーブルエントリに’！１９されている
データ要素が検索対象のデータ要素であるかを判定しく
ステップ１００４）、結果がＹＥＳであれば、ＣＳ命令
によってデータ要素のユーザカウンタを＋１する（ステ
ップ１００５）。これにより、このデータ要素が検索要
求元プロセスによってアクセスされることが宣言される
。Ｃ８命令によるユーザカウンタの更新が失敗した場合
、すなわち、他プロセスとユーザカウンタアクセスの競
合が起こった場合には（ステップ１００６）、データ要
素内容の判定からやり直す。データ要素内容の判定（ス
テップ１００４）からユーザカウンタの更新（ステップ
１００５）の間は他のプロセスも動作可能であるため、
そのデータ要素の内容が書換えられてしまう場合がある
。このようなことは、そのデータ要素のユーザカウンタ
の値が現在Ｏであり、従ってどのプロセスからもアクセ
ス中でないとみなされ、データ要素のリプレー゛スが発
生した場合に起こり得る。このため、ユーザカウンタ値
を＋１した後で、もう−度データ要素の内容を判定しく
ステップ１００７）、キーが一致すれば正常リターンす
る。また、キーが不一致の場合には、ユーザカウンタを
Ｃ８命令により一１（ステップ１０１０〜１０１１）　
ｔ、、検索を再試行する。

ステップ１００４で、データ要素が検索対象データ要素
とは異なっていることが判明した場合は、次のオーバフ
ローポジションを求め（ステップ１００９）　。

検索を続ける。なお、前述のように、オーバフロ−ポジ
ションを決定するアルゴリズムは、どのようなものを用
いても良い。

第７図から理解されるように、ハツシュテーブルエン１
−りの走査は、たかだかサーチカウンタ数のループで終
了する。操作対象データのキー分布に適したハツシュ関
数と、同時に’１Ｂされるデータ要素数に対して十分余
裕のあるハツシュテーブルエントリ総数を用意すれば、
サーチカウンタの期待値≦１とすることができ、高速な
検索が実現できる。

〔追　加〕

第８図と第９図に、追加論理の流れ図を示す。

追加論理の入力は、迫力６対象のデータ要素アドレスと
、そのデータ要素のホームポジションおよびホームポジ
ションの追加カウンタ値である。一般に、データ要素の
二重登録を避けるため、追加処理の前には検索処理を行
って、既にデータ要素が登録されているかどうかを確か
める。データ要素のホームポジションおよび追加カウン
タ値は、上記検索処理の出力を用いる。この追加カウン
タ値は、検索処理中でホームポジションが決定された時
点で退避された値であり、今回の追加処理が終了するま
での間に、他プロセスの追加処理と競合が発生したかど
うかを判定するのに用いる。

追加処理では、まず、ホームポジションが既に占有され
ているかどうかを調べ（ステップ１１０１）、占有され
ていなければ、ＣＤＳ命令により、ハツシュテーブルエ
ントリの各フィールドを更新する（ステップ１１０２，
１１０３．１１０４）。この場合、サーチカウンタ値が
Ｏであればサーチカウンタ値を１に変更する（ステップ
１１０３）が、サーチカウンタ値が１以上であれば、サ
ーチカウンタ値の更新を行わない（ステップ１１０４）
。ステップ１１０：ｌまたはステップ１１０４のＣＤＳ
命令が成功すれば、正常リターンする（ステップ１．１
０５）。ＣＤＳ命令による更新が不成功の場合は、他プ
ロセスのどのような処理と競合が発生したかを調べるた
め、追加カウンタ値を入力のカウンタ値と比較する（ス
テップ１１０６）。両者が等しければ、競合は削除処理
との間で発生したものであるから、追加処理を再試行す
れば良い。

両者が異なっていれば、追加処理の競合が発生したこと
になるため、リトライ要のリターンコードを設定したエ
ラーリターンする。この場合は、追加処理の前に行った
検索処理から再試行することになる。

ホームポジションが既に占有されている場合の処理の流
れは第９図のようになる。まず、オーバフローポジショ
ンを決定しくステップ１１０７）、そのハツシュテーブ
ルエントリが他のデータ要素によって占有されていない
かを調べ（ステップ１１０８）、占有されていれば次の
オーバフローポジションを調べに行く。同時に登録され
るデータ要素の最大数が、ハツシュテーブルエントリ総
数以下であれば、空きのオーバフローポジションは必ず
存在する。ハツシュテーブルエントリ総数の方が少なけ
れば、ハツシュテーブル満杯のエラーが起こり得るが、
簡単のために、第９図ではそのようなエラー処理は割愛
しである。

ここで、今回の空きポジションサーチ回数が。

ホームポジションのサーチカウンタより太きければ、Ｃ
８命令でサーチカウンタを今回のサーチ回数に変更する
（ステップ１１０９，１１１４．１１１５）。次に、オ
ーバフローポジションのデータ要素へのポインタをＯ８
命令で設定する（ステップ１１１０）。このＣ８命令が
不成功となるのは、そのハツシュテーブルエントリへの
データ要素の登録が他プロセスと競合したときであり１
次のオーバフローポジションに登録可能か調べに行く。

上の場合、同一ホームポジションを持つデータ要素の追
加処理との競合とは限らない。また、Ｃ８命令が成功す
れば、最後にホームポジションの追加カウンタをＣＳ命
令でカウントアツプする（ステップ１１１２）。この最
後のＣＳ命令が成功す、れば、データ要素の追加は完了
し、正常リターンする。不成功であれば、同一ホームポ
ジションに対する他プロセスの追加処理と競合したこと
になり、データ要素をハツシュテーブルから削除してリ
トライ要のエラーリターンを行う（ステップ１１１６）
。

第８図と第９図を参照すればわかるように、追加処理の
競合が発生しない場合、データ要素のホ−ムポジション
への登録は、１回のＣＤＳ命令で完了するのに対して、
オーバフローポジションへの登録には、２回もしくは３
回のＣ８命令の実行が必要である。また、オーバフロー
ポジションへの登録の場合、最後のＣ８命令による追加
カウンタの更新までに多くの処理を行わなければならな
いため、競合発生の確率がそれだけ高くなる。従って、
本発明を有効に動作させるためには、できるだけ、オー
バフローポジションへの登録の確率が低くなるようなハ
ツシングアルゴリズムを使用することが望ましい。

〔無効化〕

無効化処理の流れ図を第１０図に示す。データ要素の無
効化が次に述べる削除と異なる点は、無効化の場合は、
データ要素そのものはまだハツシュテーブルに登録され
た状態であるということである。無効化されたデータ要
素は、他のキーを持つデータのために使用（データ要素
のリプレース）されたり、同一キーのデータのために再
利用されたりする。前者の場合には、データ要素のキー
が変更されるため、−旦そのデータ要素をハツシュテー
ブルから削除して新しいキーで追加処理を行わなければ
ならない。データ要素の無効化は、入力で指定されるデ
ータ要素中の無効インジケータをオンにすることにより
完了する（ステップ１２０１）。

この処理は、Ｃ８命令によって行われる必要はない。

無効化処理は、ハツシュテーブル操作論理にとって必要
不可欠な要素機能ではないが、ある方が実際上の応用に
は便利である。

〔削　除〕

削除論理の流れ図を第１１図に示す。削除処理の入力は
、削除対象データ要素のアドレスである。

キーを指定して削除を行いたい場合は、検索要素機能と
削除要素機能を組合せた複合機能として実現すれば良い
。

削除処理では、まず、削除対象データ要素が登録されて
いるハツシュテーブルエントリのデータ要素へのポイン
タをクリアする（ステップ１３０１）。

この処理もＣ８命令で行う必要はない。もし、そのデー
タ要素を追加したときの空きポジションサーチの回数が
、ホームポジションのサーチカウンタ値と等しければ、
サーチカウンタをＣ８命令で１減じる（ステップ１３０
２．１３０３．１３０４）。ＣＳ命令が不成功となるの
は、削除対象データ要素と同一ののホームポジションを
持つデータ要素の他プロセスによる追加処理と競合が発
生した場合であり、ステップ１３０２から再試行する。

データ要素がホームポジションに登録されている場合に
は、ステップ１３０１の処理とステップ１３０２の処理
とをまとめて、１回のＣＤＳ命令によって行うことが可
能であるが、第１１図では、簡単のため割愛しである。

また、削除処理中で使用する、データ要素の登録位置、
ホームポジションおよびハツシュサーチ回数は、キーか
ら導き出すこともできるが、本実施例ではこれらの情報
を追加処理時にデータ要素中に退避し、削除処理で参照
することにより、削除処理の高速化を図っている。

第８図および第９図で示される追加処理と、第１１図で
示される削除処理中でのサーチカウンタの扱いかられか
るように、サーチカウンタは、同一のホームポジション
に属する現在登録中のデータ要素の数と常に一致してい
るのではなく、その数よりも大きな値になることがある
。例えば、あるホームポジションに属するデータ要素が
１（ｌｉ’Ｊｆ録されていて、サーチカウンタ値がｊで
ある場合を考える。ここで、ｉ−１番目に登録されたデ
ータ要素がまず削除され、次にｉ番目に登録されたデー
タ要素が削除されたとすると、この時点でサーチカウン
タはｉ−１となる。ところが、ｉ−１番目のデータ要素
は筬に削除されているため、再びサーチ回数がｉ−１よ
り大きいデータ要素がハツシュテーブルに登録されるま
で、サーチカウンタの値はｉ−１のままである。このよ
うにサーチカウンタは、あくまでも検索処理時のハツシ
ュテーブルエントリの走査回数の上限を与える意味しか
持たない。実際上は、適用対象問題に適したハツシング
アルゴリズムの選択と、豊富なエントリ数を持つハツシ
ュテーブルの用意によって、サーチカウンタの値が大き
くなる確率を充分に小さくできるため、問題はない。

〔複合機能の例〕 最後に、前述のハツシュテーブル操作論理の要素機能を
組合せた複合機能の一例を示す。第１２図は、本発明を
人出力バッファ管理に応用した場合の流れ図である。こ
こでは、データ要素は、バッファに対応した主記憶上の
制御ブロックであり、キーは入出力データ（「データペ
ージ」と呼ぶ）の２次記憶上での物理または論理アドレ
スである。

第１２図では、入力処理の流れを示している。入力デー
タページアドレスをキーとしてハツシュテーブルの検索
を行い（ステップ１４０１）、ハツシュテーブルに有効
データが登録されていればそのバッファアドレスを返却
する（ステップ１４０２）。まだデータがバッファ上に
存在しなければ、空きのバッファを１面確保して対応す
る制御ブロックをハツシュテーブルに登録して、バッフ
ァ上にデータを読込む（ステップ１４０３〜１４０８）
。空きバッファを確保するためのバッファリプレースメ
ント処理方式は、どのようなものでも良い。また、ハツ
シュテーブルへの追加処理でり１−ライ要のエラーリタ
ーンが発生したときは、目的データページが他プロセス
によって入力された可能性があるため、ステップ１４０
１の検索処理から再試行する。

この処理においては、空きのバッファを確保してデータ
の入力を行ってから、制御ブロックをハツシュテーブル
に登録しても良いが、それでは、同一データページへの
アクセスが競合した場合に無駄なＩｌｏが発生してしま
う。これを改善するためには、例えば、制御ブロック中
にデータ入力中インジケータを設け、実際の入力処理を
行う前にこのインジケータをオンにしてその時点でハツ
シュテーブルに登録してしまう方法が考えられる（ステ
ップ１４０４）、同一データページにアクセスする他プ
ロセスは、ハツシュテーブルを検索して。

データ入力中インジケータがオンの制御ブロックを見つ
けると、このインジケータがオフとなるまで（ステップ
１４０８）、−時的に待ち状態に入る。ここで発生する
プロセスの中断は、ハツシュテーブルの操作論理に起因
するもあではなく、Ｉ１０完了を待つためのものである
ことを注意しておく。

上記実施例によれば、複数プロセスの並列実行環境下で
の共用資源の管理を高速に行えるので、システムのオー
バヘッドを削減する効果がある。

また１本発明は、特に密結合型のマルチプロセッサを使
用して、主記憶上の大量のデータ要素を処理する場合に
大きな効果がある。　　　　　　　　　４なお、上記実
施例は一例として示したものであり、本発明は他の種々
の実施態様が可能であることは言うまでもない。

〔発明の効果〕

以上述べたように、本発明によれば、並行処理を行うプ
ロセス間での共用資源要素に対するアクセスをハツシュ
テーブルにより管理する方法において、前記ハツシュテ
ーブルの各エントリは、資源要素へのポインタ情報と、
ハツシュテーブルへの追加の発生を記憶するカウンタ情
報と、テーブル走査回数を制限するためのカウンタ情報
とを含み、前記ハツシュテーブルのエントリを、主記憶
上の状態変数を参照しその値に応じて状態変数を更新す
る不可分の動作を実行する命令により更新するようにし
たので、主記憶−ヒの大量のデータ要素を高速にアクセ
スするのに適したデータの管理を、マルチプロセッサ環
境においてロックなしで行うことが可能な共有資源の管
理方法を実現できるという顕著な効果を奏するものであ
る。

【図面の簡単な説明】

第１図は本発明の一実施例を示すコンピュータシステム
のブロック図、第２図はハツシュテーブルエントリの内
容を示す図、第３図はデータ要素の内容を示す図、第４
図〜第６図はデータ要素のハツシュテーブルへの登録の
様子を示す図、第７図〜第１１図はハツシュテーブル操
汁論理の要素機能の流れ図、第１２図は複合機能の一例
の流れ図である。 １０：プロセス、２０：ハツシュテーブル操作論理。 ３０：ハツシュテーブル、３１〜３３：ハッシュテーブ
ルエン１−リ、４０：データ要素プール、４１〜４３：
データ要素。 第　　　１　　　図 第　　　２　　　図 第　　　３　　　図 第　　　４　　図 第　　　５　　　図 第　　　６　　　図 第　　　７　　　図 第　　　８　　　図 第　　　９　　　図 第　　　１０　　　図 第　　　１１　　　　図

Claims (1)

【特許請求の範囲】
1. １、並行処理を行うプロセス間での共用資源要素に対す
   るアクセスをハッシュテーブルにより管理する方法にお
   いて、前記ハッシュテーブルの各エントリは、資源要素
   へのポインタ情報と、ハッシユテーブルへの追加の発生
   を記憶するカウンタ情報と、テーブル走査回数を制限す
   るためのカウンタ情報とを含み、前記ハッシュテーブル
   のエントリを、主記憶上の状態変数を参照しその値に応
   じて状態変数を更新する不可分の動作を実行する命令に
   より更新することを特徴とする共有資源の管理方法。