JPH0318935A - データリストに対するアクセスの直列化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 【産業上の利用分野］ 本発明は、データリストに対するアクセスの直列化方式
、すなわち、電子計算機上のマルチプロセス、マルチプ
ログラミング環境において、並行処理を行うプロセス間
でデータリストを共有するためにアクセスを直列化する
方式に関し、特に、複数の命令プロセッサが主記憶装置
を共有するような密結合マルチプロセッサ環境に好適な
、共有データリストに対するアクセスの直列化方式に関
する。 〔従来の技術〕 電子計算機上のマルチプロセス、マルチプログラミング
環境においては、多数のプロセスが並行して動作するこ
とが可能である。なお、本明細書においては、「プロセ
ス」とは、オペレーティングシステムがＣＰＵを割当て
るための仕事の単位を意味するものとする。一般には、
屡々、同じ意味で「タスク」という用語も用いられる。 プロセスは、その動作のために、ｃｐｕ、メモリ、ｌ１
０（入出力装置）等の各種資源を必要とするが、これら
の資源は複数プロセスによって共有されるものであるた
め、資源に対するアクセスにおいての競合が、屡々、生
ずる。 プログラム中では、一般に各種の資源は主記憶（仮想記
憶）装置上のデータブロックとして表現されるため、資
源に対するアクセスの競合は、これらデータブロックの
リスト（データリスト）に対するアクセスの競合として
具体化される。データリストに対するアクセスの要素的
操作は、リスト要素の付加・リスト要素の検索・リスト
要素からの削除から成り、一般の操作は上記要素的操作
の系列によって実現される。オペレーティングシステム
は、このようなデータリストに対するアクセスを直列化
するための機構を提供する必要がある。 例えば、Ｓ　、Ｅ　０Ｍａｄｎｉｃｋ他による“Ｏｐｅ
ｒａｔｉｎｇＳ　ｙｓｔｅ＠ｓ”（ＭｃＧｒａｗ−Ｈｉ
ｌ１社、１９７４年）の４．５章に示されている如く、
データリストに対するアクセスを直列化するための典型
的な機構は、〔ロック」および「アンロック」と呼ばれ
る命令系列によって実現される。この機構においては、
ロックバイトもしくはロックワードと呼ばれる状態変数
が設けられ、対応するデータリストが使用中であるかど
うかを表示する。 ロック動作においては、ロック要求プロセスは上記状態
変数を調べ、もし、使用中でなければ状態を使用中に変
更する。もし、使用中であれば、使用中でなくなるまで
待つ、アンロック動作においては、上記状態変数を使用
中から非使用中に変更し、もし、必要であれば、ロック
待ちとなっている他プロセスにロック解放を連絡する。 この方式においては、ロックを確保しているプロセスは
、データリストに対して排他的な使用権を有し、他のプ
ロセスは、ロック保有プロセスがアンロックを行うまで
、データリストにアクセスすることができない。この間
、ロック待ちプロセスは、実行を中断してサスペンド状
態となるか、もしくは、繰り返し状態変数を調べる、い
わゆるスピン状態に入るが、いずれにせよ、当該プロセ
スによるデータ処理は一時中断される。 この方式においては、上記状態変数を参照／更新するた
めに、変数値の「読取り〜比較−変更−書き込み」の動
作を不可分の一動作として実行する。 リード・モディファイ・ライト型命令と呼ばれる機械命
令を使用する。これは、あるプロセスが、状態変数が使
用中でないことを調べてから状態変数を使用中に変更す
る処理の間に、他プロセスが同じ状態変数を書き換えて
しまうことを防ぐための機構である。例えば、ＨＩＴＡ
ＣＭ　シリーズ処理装置においてはＴ　Ｓ　（Ｔｅｓｔ
　ａｎｄ　５ｅｔ）命令。 ＣＳ　（Ｃｏｍｐａｒｅ　ａｎｄ　Ｓｗａｐ）命令、　
ＣＤ　Ｓ　（ＣｏｍｐａｒｅＤｏｕｂｌｅ　ａｎｄ　Ｓ
ｗａｐ）命令が、これに相当する。 上記［ロック／アンロック」機構の改良として、ロック
に複数のモードを持たせる方式がある。この方式におい
ては、共有ロックと排他ロックの二つのモードを設け、
共有ロックを確保したプロセスは、データリストの参照
動作だけを行い、排池ロック炙確保したプロセスは、デ
ータリストの参照および更新動作を行う、複数のプロセ
スが同時に参照ロックを確保することは可能であるが、
参照ロックと排他ロックおよび排他ロック同志は、背反
的である。この方式は、ＡｉＪ述のデータリストの要素
的操作のうち、複数の検索処理が競合した場合に、並行
して同時に実行できる如く構成されている点で、前述の
単純な［ロック／アンロックＪ方式より優れている。し
かし、それ以外の処理の競合においては、逐次的な実行
しか許されない。 これに対して、特開昭６２−９２０６１号公報には、デ
ータリストに対する付加、検索、削除操作をすべて並行
処理可能とする方式が示されている。この方式において
は、不連続なワードを含む状態変数が設けられ、データ
リストの要素的操作は、並行動作可能な開始操作と、逐
次的にしか実行できない終了操作に分解される。 プロセスは、状態変数を変更し、データリストに関する
開始操作を実行する。この場合、他のプロセスが同時に
並行して開始操作を行っていてもよい。プロセスは、他
に競合するプロセスが存在しなければ、終了操作を実行
するが、もし、競合するプロセスが存在する場合は、終
了操作を棚上げして操作を終了してしまう。その後、競
合していたプロセスのいずれかが、この棚上げされた操
作を引き取って完了させる。 この機構は、「義務の伝達」と呼ばれ、上記状態変数の
部分的変更によって制御される。データリストの操作に
即して言えば、リスト要素の決められた一端への付加お
よび任意のリスト要素の検索については、「義務の伝達
」は不要である。リスト要素の削除に関しては、リスト
要素に無効フラグをセットする論理削除操作と、実際に
要素をポインタチェーンから外して解放する物理削除操
作とに、操作が分割され、後者が［義務の伝達」の対象
となる。ここで、「義務の伝達」は、データリストを表
現するポインタチェーンとは別に設けられた削除対象要
素をつなぐポインタチェーンへの要素の付加によって行
われる。 〔発明が解決しようとする課題〕 前述の単純なロック方式では、ロック確保要求の競合が
発生した場合に、ロックを確保できたただ一つのプロセ
スを除いては、プロセスが中断されてしまう。これは、
複数の命令プロセッサが主記憶装置を共有する如き、い
わゆる密結合マルチプロセッサ環境においては、無視で
きない性能の低下を惹きおこす、共有ロックと排他ロッ
クの二モードのロックを設けることによって、プロセス
の中断を伴なう如きロックの競合確率は幾分かは小さく
なるが、それでもまだ充分ではない。 「義務の伝達」機構を使用すれば、プロセスが中断され
ることなく、データリストの参照／更新を行うことが可
能であるが、この方式は、適用対象がある程度限定され
る。すなわち、複数プロセスにより並行動作可能な開始
処理と、逐次的に処理され、かつ、−旦、棚上げされた
後に、他のプロセスによって処理されることが可能な終
了処理にうまく分割できるような処理に適用が限られる
。 従って、例えば、リスト要素の削除要求を行ったその時
点で、要素のポインタチェーンからの取外しが完了して
いなければならないような場合には、この方式は使えな
い。データリストから削除した要素を、そのプロセスで
続いて使用するような処理が、このような場合に相当す
る。また、この方式では、並行処理度を上げるための代
償として、個々の要素処理自体のオーバヘッドは、単純
なロック方式に比べて増加している。そのため、リスト
中の要素を一括して大量かつ複雑に処理しなければなら
ないような場合には、かえって全体としての処理能力が
低下することがあり得る。このような場合には、単純に
ロックを確保して一括処理を行う方が、処理の自由度が
高く、また、オーバヘッドも抑え易い。 本発明は上記事情に鑑みてなされたもので、その目的と
するところは、従来の技術における上述の如き問題を解
消し、単純で、処理の自由度が高く、かつ、競合発生率
が充分に低いような、改良されたロック方式を提供する
こと、すなわち、単純なロック方式と同じ程度に適用範
囲が広く、同時に、「義務の伝達」方式と同じ程度に並
行処理度が高いような、データリストに対するアクセス
の直列化方式を提供することにある。 （課題を解決するための手段） 本発明の上記目的は、並行処理を行うプロセス間での共
有データリストに対するアクセスの直列化方式において
、排他モード／共有モードのニモードのロックを設け、
共有ロックを解放する場合に、もしその解放の結果ロッ
クを確保しているプロセスがなくなるのであれば、共有
ロックを解放すると同時に排他ロックを確保することを
特徴とするデータリストに対するアクセスの直列化方式
によって達成される。 より具体的には、排他ロックフラグと共有ロックカウン
タを含むロックエリアを設け、排他フラグのセット／リ
セットによって排他ロックの確保／解放を表現し、共有
ロックカウンタの加算／減算によって共有ロックの確保
／解放を表現するようにし、共有ロックカウンタの値を
減じたときにその結果がＯであれば、排他ロックフラグ
をセットする動作を不可分の一動作として実行するもの
である。 （作用〕 データリスト処理の要素的操作のうち、リスト要素の付
加、検索、論理削除は、複数プロセスで並行して処理可
能であるが、物理削除はただ一つのプロセスによって排
他的に処理されなければならない。 本発明に係るデータリストに対するアクセスの直列化方
式においては、上述の、リスト要素の付加、検索、論理
削除を共有ロックを確保して行うため、これらの操作は
複数プロセスによって同時に実行され得る。一方、物理
削除操作は、付加。 検索、論理削除操作のために確保した共有ロックを解放
する時点で、他に競合するプロセスがないことを確認し
、排他ロックを確保してから行う。 もし、競合するプロセスが存在するならば、物理削除操
作を実行しないで、単に共有ロックを解放するだけで、
次の処理に移る。 論理的には、リストから削除されてはいるが、物理的に
は残っている、すなわち、削除フラグはセットされてい
るが、ポインタチェーンにつながれているリスト要素が
残ることになるが、このリスト要素は、遅かれ早かれ物
理削除操作を実行するプロセスによってポインタチェー
ンから外される。言い換えれば、複数のプロセスが同時
にデータリストにアクセスを行っている場合、最後にア
クセスを完了して共有ロックを解放するただ一つのプロ
セスが物理削除操作をまとめて行うことになる。 この方式によれば、物理削除を行うために必要な排他ロ
ックを確保するためにロック待ちが発生することがない
。この方式によってロック待ちが発生するのは、排他ロ
ックを確保して物理削除操作を行っている間に、データ
リストにアクセスしようとするプロセスが現われた場合
だけであり、その確率は、単純なロック方式においてロ
ック待ちが発生する確率に比べて、十分に小さいもので
ある。なお、リスト全体を一括して更新するような処理
、および、リスト要素の論理削除と物理削除が分離不可
能なような処理に関しては、まず、排他ロックを確保し
てから、処理を実行すればよい。この場合、ロック待ち
が発生する確率は、単純なロック方式と同程度である。 上述の如く、本方式は、単純なロック方式の自然な拡張
になっており、従来、単純なロック方式を採用していた
プログラムが、変更なしに動作できる。これは、本ロッ
ク方式における排他フラグや共有ロックカウンタは、単
純なロック方式におけるそれと完全に同じ意味を持つた
めである。 【実施例】 以下、本発明の実施例を図面に基づいて詳細に説明する
。 第２図は、本発明を実施するためのコンピュータシステ
ムの構成図である。本図においては、複数の命令プロセ
ッサＩＯａ、ｆｏｂ、・・・、ｌＯｎが主記憶装置３０
を共有するような密結果マルチプロセッサの構成が示さ
れている。各命令プロセッサは、キャッシャ記憶装置２
０ａ、２０ｂ、・・・、２０ｎを備えていてもよい、ま
た、複数の命令プロセッサで共有されるようなキャッシ
ュ記憶装置や、多段のキャッシュ記憶装置があってもよ
い。 各命令プロセッサＩＯは、他命令プロセッサとの間での
命令実行の直列化を行うための特殊な命令（例えば、前
述のＣ８命令およびＣＤＳ命令）を実行可能である。Ｃ
８命令およびＣＤＳ命令の詳細については、後述する。 なお、本発明は、命令プロセッサ数が一つであるような
コンピュータシステムにおいても実施可能であり、マル
チプロセスによるデータリストへのアクセスを効率的に
直列化する効果を有するものである。 以下に、本発明の二つの実施例を説明する。 第一の実施例は、一般的にリスト処理に本発明を適用し
たものであり、第二の実施例は、プロセスの待ち合わせ
を管理するキュー操作への適用例である。 （１）第一の実施例：リスト操作 （ｌ−■）概要 第３図は、本発明の第一の実施例の概要を示すコンピュ
ータシステムのブロック図である。第３図においては、
並行に動作する複数のプロセス１００ａ、１００ｂ、・
−，１００ｎが、リストコントロールエリア１２０によ
って管理されるデータリスト　＋３０中の、複数のリス
ト要素１３１ａ、１３１ｂ、−・、１３１ｎに対して、
リスト操作論理１１０を介してアクセスを行う例が示さ
れている。複数プロセスによるデータリストへのアクセ
スの直列化は、リスト操作論理が、リストコントロール
エリアの情報を定められた手順に従って参照／更新する
ことによって実現される。 第４図に、リスト操作論理１１０．リストコントロール
エリア１２０．およびデータリスト１３０の詳細な構造
を示す、リスト操作論理１１０は、データリスト中の任
意の位置へ、新たなリスト要素を付加する付加論理１１
１．データリスト中から、指定された条件に合致するリ
スト要素を検索する検索論理ＩＩ２．データリスト要素
中の任意のリスト要素を削除する削除論理１１３．複数
プロセスによるデータリストへのアクセスを直列化する
ロック／アンロック論理１１４を含む。削除論理＋１３
は、更に、論理削除論理と物理削除論理に分けられる。 論理削除は、リスト要素に削除フラグをセットするだけ
であり、リスト要素は、ポインタチェーンにつながれた
ままである。これに対して、物理削除では、リス：・要
素のポインタチェーンからの取外しが実行される。また
、ロック／アンロック論理１１４は、排他モードおよび
共有モードのニモードのロックを制御するものであり、
付加論理、検索論理、削除論理によってコールされる。 並行動作するプロセスが、これらのリスト操作論理を、
定められたインタフェースに従ってコールすることによ
り、リスト要素への直列的なアクセスが保証される。並
行動作するプロセスは、付加論理、検索論理、削除論理
をコールすることにより、高い並行処理炭を保って、デ
ータリストを操作することができる。また、並行動作す
るプロセスは、ロック／アンロック論理をコールするこ
とにより、データリストを共有もしくは占有して自由に
参照・更新することができる。このように処理の並列度
と自由度を両立させたことが本発明の顕著な効果である
。 リストコントロールエリア１２０は、第４図に示す如く
、主記憶（仮想記憶）上の領域であり、アンカポインタ
＋２１と削除カウンタ　１２２、および、排他フラグ１
２４と共有カウンタ　１２５から成るロックワード１２
３によって構成される。上記アシカポインタ＋２１．削
除カウンタ１２２．ロックワード１２３の領域は、必ず
しも隣接している必要はない。アンカポインタ＋２１は
、リスト要素をつなぐポインタチェーンの起点であり、
付加論理、検索論理。 削除論理によって参照・更新される。また、削除カウン
タ１２２は、論理的には削除されているが、物理的には
削除されていないリスト要素の数を示すカウンタであり
、削除処理によって参照・更新される。ロックワード１
２３は、排他ロック、共有ロックを管理するためのエリ
アであり、ロック／アンロック論理によって参照・更新
される。 ロックワード１２３中の排他フラグ１２４は、もしそれ
がセットされている場合は、あるプロセスがデータリス
トに対する排他ロックを保持し、データリストを占有し
て、アクセスしていることを示す。共有カウンタ　１２
５は、データリストに対して共有ロックを保持している
プロセスの数を示すカウンタである。従来のロック方式
では、共有ロックを保有しているプロセスは、データリ
ストに対して参照アクセスだけしか行えなかったが、本
発明では、データリストを更新する付加論理、削除論理
も共有ロックを保有して実行される。 データリスト　１３０中のリスト要素１３１　ａ　、　
１３１　ｂ　。 ・・・・、　１３１　ｎは、リスト中での次のリスト要
素を示すネクストポインタ、リスト要素の状態を示すユ
ーザフラグ、リスト要素をアクセス中のプロセスの数を
示すユーザカウンタおよび任意内容のユーザデータによ
り構成される。上述のユーザフラグは、リスト要素の状
態を表現する任意数のフラグから成るが、本発明に関係
するのは、リスト要素が論理的には削除されたことを示
す削除フラグだけである。ユーザカウンタは、一つのリ
スト要素を同時に複数のプロセスが共有してアクセスす
るような場合に、同時アクセス中のプロセス数を示す、
リスト要素単位の共有カウンタであるが、これは必須で
はない、また、上述のユーザデータの内容は、データリ
ストの具体的な応用により異なるものであり、リスト要
素を一意的に識別するためのキー情報を含んでいてもよ
い。 （ｌ−■）Ｃ３命令およびＣＤＳ命令 リスト操作論理の詳細に入る曲に、そこで使用される特
殊な機械命令である前述のＣ８命令およびＣＤＳ命令に
ついて簡単に説明しておく、　ＣＳ命令は、第一のレジ
スタと主記憶（仮想記憶）上の１語の内容とを比較し、
もし両者が等しければその１Ｍを第二のレジスタの内容
で書き換え、両者が異なれば、第一のレジスタにその１
語の内容をロードする動作を、不可分の一動作として実
行する、いわゆるリード・モディファイ・ライト型の命
令である。 ＣＤＳ命令も、Ｃ８命令と同様の動作を実行するが、こ
ちらは、１語ではなく、倍語を操作するところが異なる
。複数の命令プロセッサが主記憶を共有する密結合マル
チプロセッサでは、あるプロセッサで実行中のプロセス
が主記憶上の状態変数の内容を変更しようとする場合、
通常のロード／コンベア／ストア命令を使用したのでは
、比較（コンベア）から書き換え（ストア）までの間に
、状態変数が他のプロセッサによって書き換えられてし
まい、処理の整合性が失われてしまうことがある得る。 このため、Ｃ８命令やＣＤＳ命令を使用して、比較と書
き換えとを一動作で行うようにするのである。 以下、リスト操作論理を、フローチャートに基づいて詳
細に説明する。 （ｌ−■）排他ロック／アンロック 排他モードのロックは、一つのプロセスにデータリスト
を占有させるための機構である。プロセスは、排他モー
ドのロックを確保すると、データリストに対して任意の
参照・更新アクセスを行うことができる。一方、あるプ
ロセスが排他モードのロックを確保している間は、他の
プロセスはデータリストに一部アクセスできない。 排他ロックの処理の流れを、第７図に示す。まず、ロッ
クワードをＣ８命令で使用する第一のレジスタにロード
しくステップ＋００１）、排他フラグがセットされてお
らず、かつ、共有カウンタが０であるか否かを確かめる
（ステップ１００２）。もしそうであれば、排他フラグ
がセットされたようなロックワード内容を、Ｃ３命令の
第二のレジスタに設定して（ステップ１００３）、Ｃ８
命令でロックワードを書き換える。Ｃ８命令の比較が成
功すれば、主記憶（仮想記憶）上のロックワードに排他
フラグがセットされたことになり、コール元にリターン
する（ステップ１００４）。また、もしＣ８命令の比較
が不一致であれば、ステップ１００＋でのロックワード
のロードから、ステップ１００３でのＣ８命令実行まで
の間に、他のプロセスがロックワードを書き換えたこと
になるため、ステップ１００２から処理を再試行する。 なお、この場合、Ｃ８命令の仕様により、第一のレジス
タには新たなロックワードの値がロードされているため
、ステップ＋００１からではなく、ステップ＋００２か
らの再試行となる。 ステップ１００２において、既に排他フラグがセットさ
れている場合、もしくは、共有カウンタが１以上である
場合には、他のプロセスが排他ロックまたは共有ロック
を確保しているのであり、それらすべてのロックが解放
されるまで、スピンしてウェイトする（ステップ１００
５）、スピンウェイトとは、ステップ！００１およびス
テップ１００２をその一部として含むような無限ループ
処理であり、プロセス処理の中断となる。ロックの競合
率が高くなると、スピンウェイトが長くなり、性能が著
しく低下する。 第８図は、排他ロックのアンロック処理の流れを示した
ものである。排他ロックの解放は、ロックワードの排他
フラグをリセットするだけである（ステップｎｏｌ）。 この処理では、Ｃ８命令を使う必要はない、何故ならば
、排他ロックを確保しているのは、ただ一つのプロセス
であり、排他ロックのアンロック処理が他プロセスと競
合することはあり得ないからである。 （１−■）共有ロック／アンロック 共有ロックは、複数のプロセスによって同時に保有され
ることが可能であり、排他ロックとだけ競合するため、
ロック競合による性能低下の可能性が、排他ロックの場
合に比べて小さい。共有ロック処理の流れを、第９図に
示した。まず、ロックワードをレジスタにロードしくス
テップ＋２０１）、排他フラグがセットされていないこ
とを確かめる（ステップ１２０２）。 排他フラグがセットされていなければ、共有カウンタを
１だけ増分したロックワード内容をＣ８命令でセットす
る（ステップ＋２０３）。Ｃ８命令の比較が成功すれば
、共有ロックが確保されたことになり、コール元にリタ
ーンする（ステップ！２０４）。 Ｃ８命令の比較が失敗するのは、ステップ１２０＋でロ
ックワードをロードしてから、ステップ＋２０３でＣ８
命令で実行するまでの間に、他のプロセスがロックワー
ドを書き換えた場合であり、ステップ１２０２から処理
を再試行する。既に他のプロセスが排他ロックを確保し
ている場合には、その排他ロックが解放されるまでスピ
ンウェイトすることになる（ステップ＋２０５）。 以上の排他ロック／アンロックおよび共有ロック処理は
、従来の排他・共有二モードロック処理でのそれと同じ
であり、特に本発明に独自のものではないが、実施例の
記述を正しく理解できるように説明を行・〕たものであ
る。 第１図は、共有アンロック処理の流れを示したものであ
る。共有アンロック処理は、本発明の中心となるもので
あり、従来のロック方式とは異なるものである。共有ア
ンロック処理では、まず、ロックワードをＯ８命令で使
用する第一のレジスタにロードしくステップ＋３０１）
、共有カウンタが１である、すなわち、自プロセスが共
有ロックを解放する最後のプロセスであるかどうかを確
認する（ステップ１３０２）、もしそうであれば、Ｃ８
命令で使用する第二のレジスタに、共有カウンタが０で
かつ排他フラグがセットされているロックワード内容を
設定し、Ｃ８命令でロックワードを書き換える（ステッ
プ＋３０３）。Ｃ８命令が成功すれば、そのプロセスは
、共有ロックを解放すると同時に排他ロックを確保した
ことになる（ステップ＋３０４）。 この状態で、後述するリスト要素の物理削除処理を呼び
（ステップ＋３０５）、排他アンロックを行って（ステ
ップ＋３０６）からリターンする。 ステップ１３０２において、共有カウンタが２以上であ
ることは、自プロセスの他に共有ロックを保有している
プロセスが存在することを意味している。この場合は、
共有カウンタを１減じたロックワードをＣ８命令でセッ
トしくステップ１３０７）、Ｃ８命令が成功すれば、即
時にリターンする。ステップ１３０４またはステップ！
３０８で、Ｃ８命令による比較が失敗するのは、ステッ
プ１３０１でロックワードをロードしてから、ステップ
１３０３またはステップ１３０７でＣ８命令を実行する
までの間に、他のプロセスがロックワードを書き換えた
ためであり、ステップ１３０２から処理を再試行する。 このような場合は、複数プロセスによる共有アンミック
処理同志、もしくは、共有アンロック処理と共有ロック
処理とが競合したときに発生し得る。第１図において、
ステップ１３０２〜ステツプ１３０６を取り除き、ステ
ップ１３０１の１ａ後にステップ】３０７を持ってくれ
ば、従来の方式による共有アンロック処理になる。 前述の、付加、検索、削除というデータリストの要素的
操作のうち、排他ロックを確保して、データリストを占
有して実行しなければならないのは、リスト要素の物理
削除処理だけである。物理削除処理を行うための排他ロ
ックの確保を、最後の共有ロックの解放と同時に行うこ
とにより、排他ロック確保時のスピンウェイトの発生を
なくすることができる。本発明によるデータリストの要
素的操作でスピンウェイトが発生するのは、あるプロセ
スが、第１図のステップ２３０３からステップ１３０６
までの処理を行っている間に、別のプロセスがリスト要
素の付加、検索、削除を行おうとした場合だけであり、
従来のロック方式によるものと比較して、ロック競合に
よる並行処理度の低下が大幅に少なくなっている。また
、本発明のロック方式は、従来のニモードロック方式と
上位互換性があり、容易に既存のプログラムに組み込む
ことができる。これは、本発明が、ロックワードの意味
は従来のものを踏襲し、その使い方に工夫を加えたもの
であるためである。 （ｌ−■）リスト要素の付加 第１０図に、リスト要素の付加処理の流れを示した。ま
ず、共有ロックを確保しくステップ１４０１）、付加処
理要求元の指定に従って、リスト要素を付加すべきポイ
ンタチェーン上の位置を決定する（ステップ１４０２）
、次に、付加リスト要素のネクストポインタを設定しく
ステップ＋４０３）、ステップ１４０４では、既存のポ
インタチェーンをＣ８命令で更新する。Ｃ３命令が成功
すれば（ステップ＋４０５）、共有ロックを解放して（
ステップ１４０６）リターンする。Ｃ８命令が失敗する
のは、同じ位置に別のリスト要素を付加しようとした他
プロセスとの付加処理同志の競合が発生したためであり
、ステップ１４０２から処理を再試行する。 付加処理がどのように行われるかは、第５図および第６
図を参考にすれば理解し易い。第５図および第６図では
、リスト要素＋３２および１３３を含む既存のデータリ
ストに、新たにリスト要素１３４を付加する場合が示さ
れている。リスト要素＋３４をリスト要素＋３２とリス
ト要素１３３の間に付加することが決定されたら、まず
、リスト要素１３４のネクストポインタにリスト要素１
３３のアドレスをセットする（第１０図のステップ１４
０３参照）。リスト要素１３４は、この時点では、付加
しようとしているプロセスしかアクセスしないため、ネ
クストポインタのセットは、通常のストア命令によって
行うことができる。 次に、リスト要素１３２のネクストポインタを。 リスト要素１３３のアドレスがらりスト要素１３４のア
ドレスに変更する（第１θ図のステップ＋４０４）。リ
スト要素＋３２は、共有ロックを確保している他プロセ
スによって同時にアクセスされる可能性があるので、ネ
クストポインタの設定には、ｃｓ命令を使用する。もし
他のプロセスによる同じ位置への付加処理と競合した場
合には、リスト要素１３２のネクストポインタは、リス
ト要素１３３のアドレスと異なる値になるため、第１θ
図ステップ１４０４のＣ８命令は失敗する。また、リス
ト要素＋３４をデータリストの先頭に付加したい場合は
、直前のリスト要素のネクストポインタの代りに、アン
カポインタ１２１をＣ８命令で更新すればよい。 上述の付加操作によれば、データリストの任意の位置に
新たなリスト要素を付加可能である。従来のロック方式
による付加処理では、第１θ図のステップ１４０１とス
テップ１４０６において、共有ロックではなく、排他ロ
ックを確保／解放し、データリストを占有して処理を行
っていたことを注意しておく。 （ｌ−■）リスト要素の検索 リスト要素の検索処理の流れを、第１！図に示した。検
索処理では、まず、共有ロックを確保して（ステップ１
５０１）、指定された検索条件に合致するリスト要素を
、ポインタチェーンを辿って検索する（ステップ１５０
２）、検索条件に合致するリスト要素が存在し、かつ、
そのリスト要素の削除フラグがセットされていない（ス
テップ１５０３．１５０４）、すなわち論理的に削除さ
れたリスト要素ではないならば、そのリスト要素のユー
ザフラグまたはユーザカウンタをＣ８命令で変更してリ
スト要素を使用中状態にしくステップ１５０５．１５０
６）、共有ロックを解放してから（ステップ＋５０７）
、リターンする。 検索条件に合致するリスト要素が存在しないか、もしく
は、そのリスト要素が既に論理的に削除されている場合
には、その旨をリターン情報に設定してエラーリターン
する。ステップ１５０５のＣ８命令が失敗するのは、他
プロセスによる削除処理と競合した場合であり、ステッ
プ１５０３から処理を再試行する。この検索処理は、共
有アンロック処理の内容が、本発明のものと置き換わっ
ていることを除けば、従来のロック方式によるものと同
一である。 （ｌ−■）リスト要素の削除 リスト要素の削除は、論理削除と物理削除の二段層で実
施される。ここで、論理削除と物理削除を実行するプロ
セスは、必ずしも同一とは限らない、第１２図に、リス
ト要素の論理削除処理の流れを示した。まず、ステップ
１６０１では、共有ロックを確保し、ステップ１６０２
では、削除対象リスト要素をサーチして、そのリスト要
素の削除フラグをＣ８命令でセットする（ステップ＋６
０３）、ＣＳ命令が成功すれば（ステップ＋６０４）、
リストコントロールエリアの削除カウンタをＣ８命令で
カウンタアップする（ステップ１６０５）。このＣ３４
を令が成功すれば（ステップ１６０６）、ステップ１６
０７で、共有ロックを解放して、リターンする。ステッ
プ１６０３およびステップ１６０５のＣ８命令が失敗し
た場合は、そのＣ８命令の処理を再試行し、フラグまた
はカウンタを更新する。 第＋３図は、物理削除処理の流れを示している。 物理削除処理では、まず、ステップ１７０１で、削除カ
ウンタの値を調べもし１以上であれば、アンカポインタ
から順にリスト要素を走査し、削除フラグがセットされ
ているリスト要素をポインタチェーンから外して、解放
する（ステップ＋７０２）。全リスト要素を走査し終っ
たら、削除カウンタをＯに戻す（ステップ１７０３）。 この物理削除処理は、排他ロックを確保した状態で実行
されなければならない。 削除処理は、第１４図および第１５を参照すると理解し
易い。第１４図は、前述のリスト要素１３３が論理的に
削除された状態を、また、第１５図は、リスト要素＋３
３が物理的に削除された状態を、それぞれ示している。 このような二段階の削除処理が有効であるのは、削除し
たリスト要素をその後のプロセスの処理で使用しない場
合である。データリストから削除したリスト要素を、そ
の後のプロセスで使用する場合には、削除処理からリタ
ーンする時点で、リスト要素のポインタチェーンからの
切り離しが完了していなければならず、排他ロックを確
保して論理削除処理と物理削除処理とを同時に行う必要
がある。本発明では、そのような場合にも柔軟に対応で
き、並行処理炭を従来と同様にできる。 以下、本発明の第二の実施例を説明する。 第一の実施例は、一般的にリスト処理に本発明を適用し
たものであったが、以下に説明する第二の実施例は、プ
ロセスの待ち合わせを管理するキュー操作への適用例で
ある。 （２）第二の実施例：キュー操作 （２−■）概要 第１６図は、本発明の第二の実施例の概要を示すコンピ
ュータシステムのブロック図である。第１６図において
は、並行に動作する複数のプロセス１００ａ、１００ｂ
、・・・・、１００ｎが、キューコントロールエリア２
２０によって管理されるキュー要１２３１ａ。 ２３１ｂ、−，２３Ｉｎを含むキュー２３０を、キュー
操作論理２１０を介してアクセスすることにより、プロ
セスの待ち合わせを実現している例が示されている。こ
こでは、複数のプロセスのうち、規定された一定数以下
のプロセスだけが実行権を得て実行可能となり、それ以
外のプロセスは先入れ先出しくＦ　Ｉ　ＦＯ）のキュー
に入って実行権の確保を待つという形で制御される。こ
のようなキューは、第一の実施例におけるデータリスト
の特別な一形態でもある。 第１７図に、キュー操作論理２１０．キューコントロー
ルエリア２２０．およびキュー２３０の詳細な構造を示
す。キュー操作論理２】０は、プロセス実行権を確保し
、もし確保できなければ実行権が与えられるのを待つエ
ンキュー論理２１１．確保したプロセス実行権を返却す
るデキュー論理２１２．キュー要素へのアクセスの直列
化を制御するロック／アンロック論理２１３から成る。 なお、エンキュー論理２＋１およびデキュー論理２１２
は、ロック／アンロック論理をコールする。 上記キューコントロールエリア２２０は、キュー要素の
ポインタチェーンの起点となるアンカポインタ２２２と
プロセス実行権の付与状況を示すラッチ２２３を含むア
ンカダブルワード２２１と、排他フラグ２２５および共
有カウンタ２２６を含むロックワード２２４から構成さ
れる。上記アンカダブルワード２２＋とロックワード２
２４は、主記憶（仮想記憶）上で必ずしも隣接している
必要はない、ここで、アンカダブルワードはＣＤＳ命令
によって、ロックワードはＣ８命令によって更新される
。アンカポインタおよびロックワードの使い方は、第一
の実施例のそれと、基本的には同じである。 上記ラッチ２２３には、初期状態では、ある正の整数が
格納されている。この整数値は、付与可能なプロセス実
行権の最大値を示している。プロセスがエンキュー操作
によって実行権を得る度に、ラッチはｌずつ減じられる
。ラッチがＯであることは、それ以上プロセスに実行権
を付与できないことを示す。この状態でプロセスがエン
キュー操作を行うと、ラッチは負の値となり、そのプロ
セスは待ち状態となる。また、ラッチは、デキュー操作
によって１ずつ増加する。 キュー要素は、待ち状態となったプロセスを表現してお
り、ポインタチェーン上での次のキュー要素を示すネク
ストポインタ、キュー要素の状態を示すフラグおよびキ
ュー要素に対応するプロセスの情報を含むキューデータ
により構成される。 フラグのうちで本発明に関係するのは、そのキュー要素
に対応するプロセスにプロセス実行権が付与されたこと
を示す付与フラグである。この付与フラグは、第一の実
施例における削除フラグの役目を合わせ持っている。 キュー操作論理のうち、ロック／アンロック操作は、第
一の実施例のそれと同じであるため、ここでは説明を省
略する。以下の説明では、第二の実施例に特有なエンキ
ュー操作およびデキュー操作について説明する。 （２−■）エンキュー エンキュー操作の処理の流れを、第１８図に示した。エ
ンキュー処理では、まず、前述のアンカダブルワードを
ＣＤＳ命令で使用する第一のレジスタ（より正確には、
連続する二つのレジスタ）にロードする（ステップ１８
０１）。次に、レジスタにロードされたアンカダブルワ
ードを中のラッチの値を調べ（ステップ＋８０２）、も
し１以上であれば、すなわちまだ付与可能なプロセス実
行権が残っていれば、ステップ１８０３で、ラッチの値
を１だけ減じたアンカダブルワードの内容を、ＣＤＳ命
令で使用する第二のこれも連続する二つのレジスタに設
定し、ＣＤＳ命令によってアンカダブルワードを更新す
る。 ステップ１８０４における、ＣＤＳ命令が成功すれば、
プロセス実行権が付与されたことになり、コール元ヘリ
ターンする。ステップ１８０２で、ラッチが０以下、す
なわち付与可能なプロセス実行権が存在しない場合は、
待ち合わせのためのキュー要素を作成しくステップ１８
０５）、ＣＤＳ命令によってラッチを１だけ減じると同
時に、キュー要素をキュー終端すなわちアンカポインタ
側の端に付加しくステップ＋８０６）、ステップ１８０
７における、ＣＤＳ命令が成功すれば、プロセスをウェ
イト状態にする（ステップ＋８０８）、このウェイト状
態は、他プロセスのデキュー処理によってプロセス実行
権が返却されるのに伴ない、順次解除される。 ステップ１８０３またはステップ１８０６で、ＣＤＳ命
令が失敗するのは、ステップ１８０１でアンカダブルワ
ードをロードしてから、ステップ１８０３またはステッ
プ１８０６でＣＤＳ命令を実行するまでの間に、他のプ
ロセスがアンカダブルワードを書き換えた場合、すなわ
ち、他プロセスのエンキューまたはデキュー処理とアン
カダブルワードアクセスの競合が発生した場合であり、
ステップ１８０２から処理を再試行する。 （２−■）デキュー 第１９図（こ、デキュー操作の処理の流れを示す。 デキュー操作は、まず、ステップ１９０１で共有ロック
を確保し、アンカダブルワードを前述の連続する二つの
レジスタにロードする（ステップ＋９０２）。 次に、ロードされたアンカダブルワード中のラッチの値
を調べ（ステップ１９０３）、ラッチが０以上である、
すなわちプロセス実行権の付与を待っているプロセスが
存在しない場合には、ＣＤＳ命令によってラッチをｌだ
け増加させ（ステップ＋９０４）、共有ロックを解放し
くステップ１９０６）、リターンする。このバスを通る
場合は、ステップ１９０７の判定処理は常に偽となる。 ステップ１９０５で、ＣＤＳ命令が失敗するのは、ステ
ップ１９０４でアンカダブルワードをロードしてから、
ステップ１９０４でＣＤＳ命令を実行するまでの間に、
アンカダブルワードが他プロセスによって書き換えられ
た、すなわち他プロセスによるエンキューまたはデキュ
ー処理との間でアンカダブルワードに対するアクセス競
合が発生した場合であ番ハステップ１９０３から処理を
再試行する。 ステップ＋９０３で、ラッチがＯより小さいということ
は、プロセス実行権の付与を待っているプロセスがキュ
ーに存在することを意味する。この場合は、アンカポイ
ンタからのポインタチェーンを辿ってすべてのキュー要
素を調べて、付与フラグが設定されていない最後のキュ
ー要素を決定する（ステップ１９０９）、キュー要素は
、アンカポインタから付加されるため、このようにして
サーチしたキュー要素は、最も古くにウェイトしたプロ
セスに対応する（ＦＩＦＯによる待ちの管理の果合）。 プロセス実行権の付与対象プロセスがみつかったなら（
ステップ＋９１０）、ステップ＋９１１で、Ｃ８命令に
よってそのキュー要素に付与フラグをセットする。ステ
ップ１９１２で、このＣ８命令が成功したならば、ＣＤ
Ｓ命令によってラッチを１だけ増加させ（ステップ１９
１３）、ステップ１９１４で、ＣＤＳ命令が成功すれば
、ステップ１９０６で、共有ロックを解放して、プロセ
ス実行権を付与したプロセスの待ち状態を解除する（ス
テップ１９０７．１９０８）。 ステップ１９０６の共有アンロック処理では、もし他に
共有ロックを保有しているプロセスが存在しない場合に
は、排他ロックを確保して、キュー中の、付与フラグが
セットされているキュー要素の物理削除を行う、すなわ
ち、第二の実施例におけるキュー要素の付与フラグは、
プロセス実行権の付与状態を制御すると同時に、第一の
実施例における削除フラグの意味をも合わせ持つ。 ステップ１９０９で、プロセス実行権の付与対象プロセ
スがみつからないという升態は、複数プロセスによって
デキュー処理が同時に実行され、ステップ１９０３で待
ちプロセスありと判断してから、ステップ１９０９で待
ちプロセスをサーチするまでの間に、既に他のプロセス
によって付与が完了していた場合に起こり得る。この場
合は、ステップ１９１３にジャンプし、ラッチの増分を
行う、同様に、ステップ１９１０で、付与フラグをセッ
トするＣ８命令が失敗するのも、複数プロセスが同一の
待ちプロセスに対して同時にプロセス実行権の付与を行
おうとして、付与フラグに対するアクセスの競合が発生
した場合であり、他に待ちプロセスがないかどうかを、
ステップｌ９０９に戻って再調査する。 ステップ１９１４のＣＤＳ命令が失敗するのは、他プロ
セスのエンキューもしくはデキュー処理とアンカダブル
ワードに対するアクセスが競合した場合である。この場
合、既に待ちプロセスにプロセス実行権を付与した、す
なわちキュー要素に付与フラグをセットしたのであれば
（ステップ＋９１５）、処理をステップ１９１３から再
試行して、ラッチを１増分するだけでよい、もしプロセ
ス実行権を付与していなかったのならば、新たに待ちプ
ロセスが発生している可能性もあるので、ステップ＋９
０３から再試行する。これにより、エンキュー処理とデ
キュー処理のすれ違いによって生ずる、有効なプロセス
実行権数の低下を防止することができる。 従来のロック方式によるキューの管理では、エンキュー
／デキュー操作を、排他ロックを確保して処理していた
。しかし、本実施例によれば、排他ロックがかかるのは
、デキュー操作の共有アンロック処理（ステップ＋９０
６）の一部に関してのみであり、並行処理度が大幅に向
上している。 上記実施例は、いずれも本発明の一例として示したもの
であり、本発明はこれらに限定されるべきものではない
。 〔発明の効果〕 以上、詳細に説明した如く、本発明によれば、並行処理
を行うプロセス間での共有データリストに対するアクセ
スの直列化方式において、排他モード／共有モードのニ
モードのロックを設け、共有ロックを解放する場合に、
もしその解放の結果ロックを確保しているプロセスがな
くなるのであれば、共有ロックを解放すると同時に排他
ロックを確保するようにしたので、共有データリストに
対する複数プロセスのアクセスを、高い並行処理度を保
って、かつ、処理の柔軟性を失わずに実行可能な、改良
されたロック方式を実現できるという顕著な効果を奏す
るものであり、特に複数の命令プロセッサが主記憶装置
を共有する密結合マルチプロセッサ環境において効果が
大きい。また、本発明によれば、従来のロック方式から
、より並行処理炭の高いロック方式に容易に移行できる
効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の特徴的動作を示すフローチ
ャート、第２図は実施例のコンピュータシステムの構成
図、第３図は第一の実施例を示すブロック図、第４図は
リスト操作論理、リストコントロールエリア、データリ
ストの説明図、第５図および第６図はデータリストへの
リスト要素の付加操作の説明図、第７図〜第１３図はリ
スト操作論理を説明するフローチャート、第１４図はリ
スト要素の論理削除操作の説明図、第１５図はリスト要
素の物理削除操作の説明図、第１６図は第二の実施例を
示すブロック図、第１７図はキュー操作論理の説明図、
第１８図、第１９図は第二の実施例におけるキュー操作
論理を示すフローチャートである。 ｌ吐命令プロセッサ、２０：キャッシュ記憶装置、３０
：主記憶装置、１００：プロセス、１１０：リスト操作
論理、Ｉｌｌ　：付加操作、１１２：検索操作、＋１３
：削除操作、１１４：ロックｌアンロック操作、＋２０
　：リストコントロールエリア、１２１：アンカポイン
タ、１２２：削除カウンタ、１２３：ロックワード、１
２４：排他フラグ、＋２５；共有カウンタ、１３０：デ
ータリスト、１３１〜１３４：リスト要素、２１０　：
キュー操作論理、２１１：エンキュー操作、２１２：デ
キュー操作、２１３：ロックｌアンロック操作、２２０
：キューコントロールエリア、２２１：アンカダブルワ
ード、２２２：アンカポインタ、２２３：ラッチ、２２
４：ロックワード、２２５：排他フラグ、２２６：共有
カウンタ、２３０：キュー、２３１：キュー要素。 第 図 １００ａ 第 ００ｂ 図 ００ｎ 第 図 第 図 ２６３ 第 ７ 図 第 図 第 区 第 図 第 １ 図 第 図 第 図 第 図 ３２ ３３ ３４ 第 図 第 １ 図 第 図 −２６（

Claims (1)

1. 【特許請求の範囲】 １、並行処理を行うプロセス間での共有データリストに
   対するアクセスの直列化方式において、排他モード／共
   有モードの二モードのロックを設け、共有ロックを解放
   する場合に、もしその解放の結果ロックを確保している
   プロセスがなくなるのであれば、共有ロックを解放する
   と同時に排他ロックを確保することを特徴とするデータ
   リストに対するアクセスの直列化方式。 ２、排他ロックフラグと共有ロックカウンタを含むロッ
   クワードを設け、共有ロックカウンタの値を減じ、その
   結果が０であれば排他ロックフラグをセットすることを
   特徴とする請求項１記載のデータリストに対するアクセ
   スの直列化方式。 ３、共有ロックを確保してリスト要素の論理削除を行い
   、共有ロックを解放すると同時に排他ロックを確保でき
   た場合に、リスト要素の物理削除処理を行うことを特徴
   とする請求項１または２記載のデータリストに対するア
   クセスの直列化方式。 ４、前記データリストに対するアクセスが、キュー操作
   であることを特徴とする請求項１〜３のいずれかに記載
   のデータリストに対するアクセスの直列化方式。