JPH0324696B2 - - Google Patents

Description

【発明の詳細な説明】

［発明の分野］ 本発明は、マルチプロセツサ（MP）システム
の各プロセツサで非同期的に実行されている複数
のプログラムが１つの待ち行列に対する挿入及び
削除を並列に行なえるようにすることによつて、
MPシステムの動作効率を改善する方法に係る。 ［発明の背景］ 待ち行列は過去及び現在のデータ処理システム
で一般に使用されている。ある待ち行列はハード
ウエア論理回路によつて管理され、他の待ち行列
はプログラム式またはマイクロプログラム式のル
ーチンによつて管理されている。多数の待ち行列
は一般に、データ処理システムの再使用可能なハ
ードウエア及びソフトウエアの資源（待ち行列自
身を含む）を制御するためにシステム制御プログ
ラムによつて用いられる。 各々の待ち行列は一般に複数の要素から成る。
例えば、ある待ち行列は現在レコードを読取りま
たは書込むプロセス中のすべてのＩ／Ｏ装置を追
跡するシステムで用いられることがあり、その場
合、待ち行列の要素の数は使用中のＩ／Ｏ装置が
ないことを表わすゼロから、多数のＩ／Ｏ装置が
使用中であることを表わす大きな数までの間を変
動する。別の例は、実行可能なユーザー・プログ
ラム・タスクにCPUを割振るシステム資源であ
る監視デイスパツチヤ・プログラムの使用に関す
る全てのユーザー要求を受取るのに用いられる待
ち行列である。 待ち行列は待ち行列中の要素の相対的に位置関
係によつて次の２つの一般的なタイプに分類され
ることがある。 第１は物理的に連続した位置に要素を有する連
続待ち行列である。 第２は物理的に主記憶（MS）内のどこにでも
分散されうる要素を有する連鎖待ち行列である。 連続待ち行列の例は、M.Taradalsky、“First
−In／First−Out Queueing Technique Using
Compare and Swap”、IBM Technical
Disclosure Bulletin、Vol.18、No.５、October
1975、1547頁に示されている。 本発明は連続待ち行列は取扱わず、連鎖待ち行
列だけ、特にアンカーを有する単一系（single
thread）を連鎖待ち行列だけを取扱う。各々の連
鎖待ち行列は主記憶の所定の位置にアンカー・ブ
ロツクを有し、その待ち行列を制御する。アンカ
ー・ブロツクはその待ち行列を構成する要素の連
鎖をアドレス指定する（アンカー・ポインタと呼
ばれる）アドレスを含む、各々の要素はその待ち
行列中の次の要素へのポインタを含む。待ち行列
の最後の要素はそれを最後の要素として識別する
標識コード（しばしば全０）をそのポインタ位置
に有する。現在もし待ち行列中に要素がない（す
なわち、その待ち行列は空である）ならば、アン
カー・ブロツクはそのアンカー・ポインタの位置
に空のコード（例えば、全０）を含む。 要素はそのアンカー・ブロツクを変更すること
によつて待ち行列に挿入されたり、待ち行列から
削除されたりする。最も容易で最も速い挿入と削
除はアンカー・ポインタ自身を変えることによつ
て行なわれ、その場合、挿入はアンカー・ポイン
タを待ち行列に置かれる新しい要素のアドレスに
変更することを伴ない、削除はアンカー・ポイン
タをそれによつてアドレス指定された要素中のポ
インタに変更することを伴なう。アンカー・ポイ
ンタによつて直接アドレス指定される待ち行列の
先頭要素は「アンカー・ポイント要素」と呼ばれ
る。後入先出（LIFO）型の待ち行列はアンカ
ー・ポイント要素を挿入し削除する。アンカー・
ポイント要素はLIFO待ち行列において最新かつ
最後の要素であり、削除される要素の候補であ
る。 しかしながら、多くのデータ処理活動はLIFO
型の削除操作を使用できず、先入先出（FIFO）
型または他の非LIFO型の削除操作を必要とする。 本発明は、LIFO削除操作及び非LIFO削除操作
の組合せに対しても使用できるが、基本的には純
粋なLIFO削除操作以外の操作を必要とする連鎖
待ち行列に重点が置かれている。 MSを共有する２台以上のプロセツサあるいは
CPUが同時に且つ非同期で別個の命令ストリー
ムを実行しうる多重処理は、共有MS中の待ち行
列の変更に関する特殊な問題を呈することが認め
られている。例えば、第１のプロセツサが待ち行
列要素の挿入または削除を完了する前に、第２の
プロセツサが別の待ち行列要素の挿入または削除
を試みることは望ましくなく、どのプロセツサも
別のプロセツサによる待ち行列中の不完全は変更
に基づいた動作をしてはならない。 この問題は先行技術では一般に２つの異なる方
法で解決されている。先行技術における第１の解
決方法は待ち行列をロツクするもので、それによ
りその待ち行列を使用しているプログラムの全て
を直列化し、任意の時間において１つのプログラ
ムだけがその待ち行列をアクセスできるようにす
る。このようなロツキング動作は、例えばIBM
システム／370のテスト設定命令（TS）または比
較置換命令（CS、CDS）の実行によつてサポー
トされる。待ち行列を使用する全てのプログラム
の間のプログラミング規約として、全てのプログ
ラムは待ち行列の変更を試みる前に自発的に待ち
行列ロツク・フイールドを検査してその状態を確
認することが要求され、１つのプログラムだけが
選択されてロツク・フイールドをセツトしてから
その待ち行列を変更する。選択されたプログラム
は、待ち行列の変更を完了すると、ロツク・フイ
ールドをアンロツク状態に変更し、かくて別のプ
ログラムがその後で待ち行列をロツクして使用す
ることができる。この方法では、一度に単一挿入
操作または単一削除操作だけが遂行可能であつ
て、同時遂行は不可能である。 先行技術における第２の解決方法はロツクを使
用せず、LIFO待ち行列だけを対象にしている。
LIFO待ち行列はその保全性を維持しつつ、複数
のCPUにおける異なるプログラムからの同時要
求によつてアンカー・ポイント要素が挿入された
り削除されたりすることを可能にする。第２の解
決方法はIBMシステム／370のCS命令またはCDS
命令を待ち行列アンカー・ポイントに直接用い
て、アンカー・ポイント要素の挿入または削除を
成しとげる。第２の解決方法の背景はIBMシス
テム／370解説書（Ｎ：GA22−7000−５）の311
頁〜314頁に見出される。比較置換命令は、単一
ワード・フイールド（CS）命令及び２重ワー
ド・フイールド（CDS命令）を扱う２つの形式
があり、待ち行列アンカー・フイールドの大きさ
（１ワードまたは２ワード）によつていずれかが
選択される。CS命令またはCDS命令の実行中は、
MPシステムにおけるどのプロセツサも別のプロ
セツサによる削除操作または挿入操作に干渉する
ことはできない。 全ての待ち行列管理プログラムは、指定された
汎用レジスタB2の現在の内容に変位D2を加算し
た値を待ち行列アンカー・ポインタの主記憶アド
レスとして使用する。有効アドレスD2（B2）を
用いて取出されたアンカー・ポインタは汎用レジ
スタR1にロードされ、それにより最初の待ち行
列要素が指定される。LIFO挿入ルーチンは最初
に、待ち行列に挿入されるべき新しい要素をセツ
トアツプし、その中にアンカー・ポインタを書込
み、そして汎用レジスタR3にこの要素のアドレ
スを記憶せねばならない。LIFO削除ルーチンは
最初に、待ち行列から削除されるべきアンカー・
ポイント要素内のポインタの内容を汎用レジスタ
R3に記憶せねばならない。次に、要求された挿
入または削除を行なうためにCS命令が実行され
る。そのときCS命令はR1を検査してアンカー・
ポインタの内容が変更されたかどうかを決定す
る。それが変更されていない場合は、R3にある
アドレスがアンカー・ポインタに記憶され、待ち
行列においてアンカー・ポイント要素の挿入また
は削除が行なわれる。アンカー・ポインタがR1
で変更されていると、挿入または削除の試みは失
敗するが、R1には現アンカー・ポインタが再ロ
ードされる。CS命令の条件コード（CC）はその
実行が成功したかまたは失敗したかを表わす。 LIFO方式で要素を挿入または削除するために
CS命令によつてアンカー・ポインタだけが置換
される場合には、挿入操作または削除操作の間に
待ち行列を破壊する大きな危険が存在することが
経験によつて知られている。 待ち行列の保全性が危険にされされるのは： (1)第１のプログラムが、アンカー・ポイント要
素中のポインタがゼロであることを発見した後
に、そのとき待ち行列における単一の要素を削除
することを試みている間に；(2)第２のプログラム
がその要素を削除して、新しい要素を挿入し、次
いで前に削除した要素を新しいアンカー・ポイン
ト要素として再び挿入したときであつて；(3)これ
らが第１のプログラムにおけるCS命令の実行前
に全て行なわれたときである。この場合、第１の
プログラムは、再挿入されたアンカー・ポインタ
との比較で一致が得られる為、そのCS命令の実
行を成功裏に完了する。その結果、アンカー・ポ
インタに全０フイールドが挿入され、待ち行列が
空であることを表わす。これは、途中で別の要素
が待ち行列に置かれたことを第１のプログラムが
知らないからである。この全０のアンカー・ポイ
ンタがポインタ連鎖を壊し、それによつて待ち行
列（そのとき空ではない）における要素の存在を
無視するので、待ち行列が破壊される。 待ち行列障害は多分、データ処理動作が停止す
るか、または正しくない結果を生じる原因となる
から、高速データ処理システムにおいては危険性
の高い待ち行列は無用のものである。このタイプ
のソフトウエア障害の検出は、発見して訂正する
ことが困難なことがあり、これはシステム・ダウ
ンにつながる。 待ち行列の保全性に対するこの危険性は先行技
術ではカウンタ・フイールドの付加によつて軽減
されている。カウンタ・フイールドはアンカー・
ブロツク内でアンカー・ポインタの隣りに置かれ
る。アンカー・ポインタ及びカウンタ・フイール
ドはいずれも１ワード幅であり、そり両方が
CDS命令によつて１単位として置換される。 CS命令またはCDS命令に条件付き分岐命令が
続き、実行されたCS命令またはCDS命令の条件
コードを検査して、要求された挿入または削除が
成功したかどうかを決定する。不成功の場合は、
ルーチンはループを戻つてR3の内容を再検査し
たのちCS命令またはCDS命令を再実行し、必要
ならばCS命令またはCDS命令の実行が成功する
までこのループを反復する。 下記の表は前掲のIBMシステム／370解説書の
314頁に載つているものと殆んど同じ挿入ルーチ
ン及び削除ルーチンを示したもので、コーデイン
グはシステム／370アセンブラによつている。
CDS命令を実行すると、１ワード幅のアンカ
ー・ポインタ及びその隣りに位置する１ワード幅
のカウンタ値を１単位として待ち行列アンカー・
ブロツクに記憶することができる。

【表】 る。
BNE TRYAGN

【表】 る。
要素挿入ルーチンまたは要素削除ルーチンの実
行を開始する時点から、CS命令またはCDS命令
の条件コードが０である（挿入または削除が成功
であつたことを表わす）ことを各々のルーチンが
発見するまで、CPUは待ち行列の要素を挿入ま
たは削除するプロセス中であると考えられる。従
つて、MPシステムにおいては、異なるCPUのい
くつかのプログラムが同時に同じLIFO待ち行列
において挿入ルーチンまたは削除ルーチンを実行
することがあり、そのCS命令またはCDS命令の
実行が成功して各々のルーチンの競合が終るまで
それらのルーチンのいくつかは競合によつてルー
ピングを行なう。 ２台のCPUが同じLIFO待ち行列に対して同時
に待ち行列管理ルーチンを実行している場合を例
にとつてもう少し詳しく説明する。これらの
CPUの間では、互いにLIFO待ち行列をアクセス
しようとしていることが分らない、すなわち両者
の間には同期通信手段がないので、どちらの
CPUもLIFO待ち行列に対し非同期で挿入または
削除を試みることがある。第１のCPUのルーチ
ンがそのオペランドをセツトアツプすることによ
つて実行を開始したが、第２のCPUのルーチン
がそのCDS命令の実行に成功して現アンカー・
ポイント要素を挿入または削除し、それによつて
記憶場所D2（B2）にあるアンカー・ポインタの
内容が変更されたときに、まだ自身のCDS命令
を実行していなかつたものと仮定すれば、第１の
CPUのルーチンがそのCDS命令を実行しても成
功しない。その理由は、D2（B2）にある実際の
アンカー・ポインタまたはカウンタが前にロード
されてR1のアンカー・ポインタまたはR1＋１の
カウンタに一致しないからである。しかしなが
ら、CDS実行の失敗はR1に新しい実際のポイン
タ値を再びロードし、第１のCPUによる次の
CDS実行のための準備をする。もしD2（B2）に
ある実際のポインタ及びカウンタ値が次のCDS
実行の時点でR1及びR1＋１の内容と変つていな
かつたならば、その実行は成功である。従つて、
CDS命令はLIFOの待ち行列の不適当な変更を防
ぎ、その保全性を維持する。先行技術の待ち行列
管理プログラムは、ロツクなしのLIFO待ち行列
のための挿入ルーチン及び削除ルーチンを多年に
わたり行なつている。その理由は、複数のプログ
ラム及びCPUが挿入及び削除を並行して行なえ
るからである。あいにく、このタイプのロツクさ
れない待ち行列の処理は、LIFO（先入先出）のよ
うな非LIFO待ち行列に対して使用できない。 第３図及び第４図は、LIFO待ち行列において
新たなアンカー・ポイント要素の挿入または現ア
ンカー・ポイント要素の削除を行なう在来の待ち
行列オペレーシヨンで使用されることがある前述
の先行技術のLIFO挿入及び削除ルーチンの流れ
図を示す。これらのルーチンは待ち行列サービス
を必要とするプログラムに挿入されている。 第３図のLIFO要素挿入ルーチンにおいて、要
素挿入はステツプ34で、与えられたCPUにおけ
るCDS命令の実行の成功によつて得られる。す
なわち、R1にロードされたアンカー・ポインタ
及び次の汎用レジスタR1＋１にロードされたカ
ウンタ（これはステツプ31によつて、またはこの
ルーチンの前回の反復でステツプ34によつてMS
のD2（B2）に位置するアンカー・ポインタ及び
カウンタにロードされている）を、現在アンカ
ー・ブロツクに存在している実際のアンカー・ポ
インタ及びカウンタと比較し、それ己が依然とし
て同じでいる（ステツプ31からステツプ34での
CDS命令の実行までの間に、他のいずれのルー
チンも待ち行列の挿入または削除を行なつていな
いことを表わす）かどうかを決定する。もしR1
とR1＋１の内容がCDS命令実行時にD2（B2）に
おける値に依然として同じてあれば、MSのアン
カー・ブロツクにレジスタR3からの新しい要素
のアドレス及びR3＋１からの増加されたカウン
タ値を記憶するとともに、そのCPUにおける条
件コード（CC）を０にセツトする。しかしなが
ら、もしR1及びR1＋１の内容がD2（B2）におけ
る実際のアンカー・ポインタ及びカウンタの値と
異なるならば、CDS命令は代りにレジスタR1及
びR1＋１にアドレスD2（B2）の実際のアンカ
ー・ポインタ及びカウンタの値をロードするとと
もに、そのCPUの条件コード（CC）を１にセツ
トする。 レジスタＲ３は前にステツプ33で、挿入される
新しい要素のアドレスによつてセツトアツプ済で
あり、その隣接汎用レジスタR3＋１は１だけ増
分されたカウンタの値によつてセツトアツプ済み
である。 それぞれルーチンはステツプ35で条件付き分岐
命令を用いて条件コード（CC）を検査する。も
しCCが１であることが分れば、挿入は生じなか
つたことになり、ルーチンはステツプ32に戻り、
次の反復動作で新しい要素のポインタを新しいア
ンカー・ポインタにセツトし、ステツプ33でR3
＋１の増分されたカウンタ値を再決定し、次いで
ステツプ34で、もう１つの挿入の試みとして、成
功するかどうかは分らないがCDS命令を再実行
する。それによつてルーチンは必要な挿入がなさ
れる（CC＝０）までCDS命令を１回以上実行す
る。 第４図のLIFO要素削除ルーチンにおいて、こ
れが呼出しプログラムによつて開始されると、ス
テツプ41で汎用レジスタR1及びR1＋１が第３図
のステツプ31で行なわれたようにロードされる。
汎用レジスタR1＋１にロードされたカウンタ値
は挿入または削除の度に増分される。空の待ち行
列から要素を削除しえないから、次にステツプ42
で待ち行列が空である（すなわち、要素を１つも
持たない）かどうかが決定される。もし待ち行列
が空であれば、アンカー・ポインタが全０になつ
ている。よつて、ステツプ42では、アンカー・ポ
インタの全０値に関して検査が行なわれ、待ち行
列が空でない、すなわち１つ以上の要素を有する
場合にのみステツプ43以下の削除動作が続行す
る。 ステツプ43では、R1の内容によつてアドレス
指定されるアンカー・ポイント要素にある現在の
ポインタ値がR3にロードされる。ステツプ44で
は、新しいカウンタ値、すなわちアンカー・ブロ
ツクから取出され１だけ増分されたカウンタ値が
次の汎用レジスタR3＋１にロードされる。 次にステツプ45では、R1の値とR1＋１のカウ
ンタ値が依然としてMSのD2（B2）におけるアン
カー・ポインタ及びカウンタの値と同じであるか
どうかを検査して、他のいずれかのプログラムが
実際のアンカー・ポインタを変更するように干渉
したか、例えば要素の挿入または削除を行なつた
かどうかを決定する。次のステツプ46では、得ら
れた条件コードを検査してCDS実行によつて挿
入がなされたかどうかを決定する。CC＝０の場
合は、削除がなされており、アンカー・ブロツク
は新しいポインタ及び新しいカウンタ値を有す
る。ステツプ47は、R1にあるアドレスが削除さ
れた要素を表わし、ルーチンがその呼出プログラ
ムにリターンするときR1が削除操作の出力を含
むことを表わす。 しかしながら、もしステツプ46でCCが１であ
ることを表わせば、挿入は行なわれなかつたが、
CDS命令が実際の現アンカー・ポインタ及びカ
ウンタの値をR1及びR1＋１に各々ロードしてい
る。従つて干渉するプログラムが待ち行列を空に
していることがありうるので、条件付き分岐によ
つてルーチンはステツプ42に戻り、待ち行列の空
のステータスを再検査する。ステツプ42〜46は、
削除が行なわれ、ステツプ46でCC＝０が検出さ
れるまで反復される。 アンカー・ポインタと共にカウンタが使用され
ている理由は、ステツプ43とステツプ44の間で他
のプロセツサが介入して複数の挿入操作及び削除
操作を行なつたために、アンカー・ポインタの値
は同じままであるが、アンカー・ポイント要素の
ポインタ・フイールドの値が変えられていること
があるからである。このような可能性に対する保
護としてCDS命令が使用され、各々の挿入また
は削除のカウンタ値を調整するとともに、ステツ
プ44で新しいカウンタ値を比較する。等しくない
カウンタ値はCC＝１を生じ、ルーチンはステツ
プ46からステツプ42に戻つて再び削除を試みる。 先行技術において、同じ要素を含む２つの待ち
行列、即ち要素挿入用の入力待ち行列及び要素削
除用の出力待ち行列を用いることにより、FIFO
方式のオペレーシヨンが行なわれている。この方
法は従来のIBM MVSプログラムのIEAVEDSO
モジユール及びIEAVESCIモジユールで用いら
れている。前にLIFO要素挿入について説明した
ように、比較置換技法を用いれば、入力待ち行列
をロツクせずにその保全性を失うことなく複数の
CPUによつて要素を入力待ち行列に効率的に挿
入することができる。ある状態（例えば、入力待
ち行列のサイズが最大であるか、または出力待ち
行列が空である状態）が生じると、両方の待ち行
列がロツクされてその使用が阻止されるととも
に、第１の待ち行列の全要素が除去されて、（例
えば、そのポインタ・チエーンを逆にすることに
よつて）FIFOシーケンスに再配列された後、第
２の待ち行列である出力待ち行列に挿入される。
第１の待ち行列からの出力及び第２の待ち行列へ
の入力は、この待ち行列再構成プロセスの間はロ
ツクされている。出力待ち行列はその後、挿入ロ
ツクを維持して挿入を阻止するが、アンカー・ポ
イント要素を削除することによつて、削除ロツク
なしにFIFO方式での削除操作を可能にする。よ
つて、第２の待ち行列が空にされている間に新し
い要素がその中に挿入されることはない。第２の
待ち行列の挿入可能な唯一の要素は、ロツク制御
の下に第１の待ち行列から与えられる要素であ
る。 ［発明の概要］ 本発明は単一の連鎖された待ち行列に対する並
列オペレーシヨンを可能にする。すなわち複数の
プロセツサが要素挿入ルーチンを同時に実行する
こと、及びそれと同時に任意のプロセツサが要素
削除ルーチンを実行することによつて待ち行列か
ら任意の要素を取り除くことが可能である。削除
プロセスの間、削除ロツクがオンにセツトされる
が、これはアンカー・ポイント要素を挿入するた
めに並列に実行される１以上のルーチンの処理に
は影響しない。 非LIFI待ち行列をロツクしてそこから非アン
カー・ポイント要素を削除する場合には、まず要
求された非アンカー・ポイント要素を見つけるた
めに待ち行列が探索され（アンカー・ポインタか
ら始める）、待ち行列中の先行要素にあるポイン
タが削除される要素のアドレスとして出力され
る。そして、削除される要素にあるポインタをそ
の先行要素へ移すことによつて目的とする非アン
カー・ポイント要素が削除される。 待ち行列をロツクしてアンカー・ポイント要素
を削除する場合は、待ち行列においてアンカー・
ポイント要素に続く要素をアドレス指定するよう
にアンカー・ポインタが変更され、そして削除さ
れるアンカー・ポイント要素のアドレスが出力さ
れる。 非LIFO処理のうちで重要なのは、待ち行列の
最後の要素を要求された要素と考えるFIFO処理
である。最後の要素はそのポインタ・フイールド
にある待ち行列終結コードによつて識別される。 本発明は非純粋LIFO待ち行列（ユーザのオプ
シヨンによつて待ち行列がLIFO方式または非
LIFO方式で削除されるという意味で「非純粋」
である）において効率的な処理を与える。本発明
は、待ち行列にアンカー・ポイント要素を挿入す
る場合は、いかなるロツクも使用しない。そのと
きの待ち行列の保全性は、前述のCS命令の使用
によつて維持される。 本発明の目的は多重プログラミングあるいは多
重処理のための新規な待ち行列管理方法を提供す
ることにあり、それにより下記のことが可能にな
る。 (1) 非LIFO待ち行列及びLIFO待ち行列として働
く単一の待ち行列の処理効率を増大しながら、
カウンタ・フイールドを用いずに待ち行列の保
全性に関する危険を除く。 (2) 同じ待ち行列に対し、あるユーザ・プログラ
ムによる非LIFO削除操作と、１以上の他のユ
ーザー・プログラムによるアンカー・ポイント
要素の挿入操作と平行して行なえる。 (3) 待ち行列を破壊するおそれなしに、任意の
CPUにより非アンカー・ポイント要素または
アカー・ポイント要素の削除操作と、他の任意
のCPUによる１つ以上のアンカー・ポイント
要素の挿入操作とを並列に遂行し得る非LIFO
待ち行列出力ロツクを与える。 (4) 非LIFO待ち行列及びLIFO待ち行列として効
率的に動作可能であつて、その待ち行列に挿入
されている１つ以上のアンカー・ポイント要素
の処理と平行していかなる要素の削除処理をも
可能にする待ち行列を与える。 (5) 異なるタイプのLIFO及び非LIFO削除操作が
待ち行列の保全性を害する危険なしにいずれの
プログラムによつても任意に実行可能である効
率的な並列挿入／削除操作を可能にする単一待
ち行列を与える。 (6) 従来は挿入操作及び削除操作の間、待ち行列
の保全性を維持するために必要とされていた待
ち行列アンカー・ブロツク中のカウンタを使用
することなく、待ち行列の並列LIFO／非LIFO
オペレーシヨンを可能にする。 ［良好な実施例の説明］ 第１図は、主記憶にある連鎖待ち行列（以下、
単に「待ち行列」という）１０を共有する複数の
CPUで複数のプログラム（１〜Ｋ）が実行され
ているMPシステムにおいて、本発明に従い単一
の待ち行列１０に対してなされる一般的なオペレ
ーシヨンを示す。プログラム１〜プログラムＪは
同時に待ち行列１０に要素を挿入することができ
それと同時にプログラムＫはアンカー・ポイント
要素を含む得る１つ以上の要素を同じ待ち行列１
０から削除することができる。 本発明は挿入操作及び削除操作を並列に遂行し
ている間、フイールドなしに待ち行列の保全性を
維持しうるからカウンタ・フイールドは待ち行列
１０に対して与えられていない。 プログラム１〜Ｊのどれも待ち行列１０におい
て、いかなるロツクも用いず、これらのプログラ
ムの各々はＳ／370CS命令を用いて要素を待ち行
列のアンカー端に挿入する。しかしながら、プロ
グラムＫはその削除操作を遂行するためには、削
除ロツク１１を得なければならない。プログラム
Ｋはアンカー・ポイント要素の場合を除き、要素
（単数または複数）を削除するのにCS命令または
CDS命令を用いなくてもよい。（非同期に動作し
ている他のCPUが削除ロツク１１を要求してい
ることがあるので、削除ロツク１１を得るため、
CS命令、CDS命令またはTS命令を用いる必要が
あるかも知れない。） 第２図は、アンカー・ブロツク２０及び要素Ｎ
〜０（これらはアンカー・ブロツクと各々の待ち
行列要素Ｎ〜０に含まれたポインタによつてアン
カー・ブロツク２０に連鎖されている）を含む待
ち行列１０において要素を挿入または削除するた
め同時に遂行できるプロセスの構造例である。ア
ンカー・ポインタ２１は待ち行列１０におけるア
ンカー・ポイント要素Ｎの位置を示すアドレスで
ある。アンカー・ポイント要素Ｎはアンカー・ポ
インタ２１に含まれたアドレスによつて直接アド
レス指定される。 アンカー・ポイント要素Ｎのポインタは次の待
ち行列要素（Ｎ−１）の位置に示し、要素（Ｎ−
１）のポインタはその次の待ち行列要素の位置を
示す。以下同様な位置指定が最後の要素０に達す
るまで続けられる。最後の要素０はポインタ・フ
イールド中の特殊なコード、例えば全０によつて
識別される。ゼロ（アンカー・ポインタ２１は全
０）を含む任意の数の要素が任意の時点において
待ち行列１０に存在し得る。このように、待ち行
列１０における要素の連鎖順序は最も新しい要素
Ｎから最も古い要素０に至る。 待ち行列１０に入力される各々の要素はアンカ
ー・ポイント要素Ｎとして挿入され、それによつ
て前のアンカー・ポイント要素は待ち行列１０に
おいて２番目の要素（Ｎ−１）になる。アンカ
ー・ポイント要素Ｎは待ち行列10の先頭に位置
し、論理的にアンカーに最も近いとみなされるの
に対し、要素０は待ち行列１０の末尾に位置し、
論理的にアンカーから最も遠いとみなされる。 待ち行列１０のアンカー・ブロツク２０及び
各々の要素は、ポインタ・フイールドの他に、待
ち行列によつて管理されている。要素情報を含む
他の周知のフイールドを有することがある。 フイールド１１（アンカー・ブロツク２０に存
在しなくてもよい）は削除ロツクを含む、削除ロ
ツクは全０を含む場合にはオフ（アンロツク状
態）にセツトされ、それ以外の場合にはオン（ロ
ツク状態）にセツトされる。削除ロツクは、削除
ルーチンを呼出して削除ロツクを渡す待ち行列ア
クセス・プログラムによつてセツトされることが
ある。この場合、削除ルーチンは「削除ロツクを
保持する」とみなされる。 待ち行列１０の各要素は、普通はMSの異なる
領域に位置し、待ち行列１０の他の要素と物理的
に連続して配置されることはめつたにない。この
ように、これらの要素は待ち行列１０でアンカ
ー・ポインタ２１で始まる要素のポインタの連鎖
によつて位置が示されるから、MS内のどこにで
も広く散在しうる。従つて、アンカー・ポイント
要素Ｎは物理的にアンカー・ブロツク２０の近く
に存在しなくてもよい。 待ち行列アクセス・プログラムはアンカー・ブ
ロツク２０のMSアドレス及びその中のアンカ
ー・ポインタ２１に対する指標を知ることによつ
て待ち行列１０をアクセスする。待ち行列アクセ
ス・プログラムの要素削除ルーチンは、アンカ
ー・ポインタ２１を含む待ち行列中のポインタの
連鎖を用いることによつて待ち行列１０の任意の
要素を見つけることができる。 第２図において３台のCPU１，２及び３は同
時に待ち行列アクセス・プログラムを実行してい
る。CPU１及び２はそれぞれ独立して待ち行列
挿入ルーチンを実行して新しいアンカー・ポイン
ト要素を待ち行列１０に挿入しようとしており、
CPU３は並行して削除ルーチン５０を実行して
待ち行列１０の非アンカー・ポイント要素、例え
ば要素（０）を削除しようとしている。CPU１
またはCPU２の一方が最初に新しい要素Ｎの挿
入に成功し、次いで他方のCPUがもう１つの新
しい要素Ｎを挿入し、これらの２つの新しい要素
は待ち行列１０の要素Ｎ及び要素（Ｎ−１）にな
る。 詳細に説明すれば、第２図で実行される各々の
挿入ルーチンはそれぞれの新しい要素Ｎ２６及び
２７をセツトアツプした後、CS命令のオペラン
ドとしてそれぞれのCPUの汎用レジスタR1及び
R3をロードする。すなわち、各々のR1は、MS
において待ち行列１０の全てのユーザに知られて
いるアドレスD2（B2）に置かれているアンカ
ー・ポインタ２０のアドレスを受取る。CPU１
及び２のR3のそれぞれの挿入ルーチンによつて、
新たにセツトアツプされた要素２６及び２７の
MSアドレスをそれぞれロードされる。各挿入ル
ーチンは、待ち行列をロツクしない従来のルーチ
ン（第３図）に似ているが、カウンタ・フイール
ドを使用しない点が異なつている。 第２図において、削除ルーチン５０は同時に待
ち行列１０から要素を削除するように働く。削除
ルーチン５０は最初に待ち行列１０に対する削除
ロツク１１を保持せねばならない。これは削除ル
ーチン５０の実行が完了するまで保持される。削
除ロツク１１は削除ルーチン、または削除ルーチ
ンを呼出してオンにセツトされた削除ロツクを渡
すルーチンによつてオンにセツトされる。 第２図において、削除ルーチン５０は非LIFO
オペレーシヨンの場合、非アンカー・ポイント要
素を削除するものとして示されている。しかしな
がら、本発明によつて、アンカー・ポイント要素
を含む任意の要素を削除ルーチン５０によつて削
除することができる。 良好な削除ロツクに関するプログラミング上の
規約は次の通りである。MPシステムで待ち行列
削除ルーチンを実行する事がある全てのユーザ・
プログラムは待ち行列で要素の削除を試みる前に
そのロツク・フイールドの状態を検査し、非０値
によつてオンにセツトされたロツク・フイールド
を見つけた時は待ち行列からの削除は行なわな
い。 この規約は待ち行列挿入ルーチンを実行するこ
とがあるユーザ・プログラムがロツク・フイール
ドの状態を検査することを必要としない。 この規約を用いる場合、削除ロツク・フイール
ドは削除ルーチンを呼出す前にユーザ・プログラ
ムによつて検査されてもよい。もしロツクがオフ
にセツトされていることをユーザ・ルーチンが発
見すれば、ユーザ・ルーチンは自身に割当てられ
たロツク・コード（非０のユーザ識別コードでも
よい）を書込むことによりロツクをオンにセツト
しうる。次いで、ユーザ・ルーチンは削除ルーチ
ンを呼出してそれに削除ロツク・アドレスを渡
す。削除ルーチンは削除操作を試みる前に、正し
いロツク・コードが書込まれているかどうかを検
査する。要素削除が終了した後、削除ルーチンは
ロツク・フイールドをオフ状態、すなわち全０値
にリセツトせねばならない。これは任意の他のユ
ーザ・プログラムに対し、待ち行列が削除のため
に使用可能であることを表わす。 しかしながら、この規約は挿入ルーチンが削除
ロツク・フイールドの状態を検査することを必要
としないから、たとえそれがオンにセツトされて
いても、要素の同時挿入を阻止しない。よつて、
たとえ削除ロツクが保持されている間でも、待ち
行列の保全性に危険を及ぼさずに、要素挿入及び
要素削除を同時に行なうことができ、その際同時
に実行される任意の数の要素挿入ルーチンによつ
て複数の新しい要素を待ち行列のアンカー端に挿
入することができる。 ロツクされた削除操作においては、待ち行列を
探索して要求された要素を見つけるのに任意のユ
ーザ基準が使用可能であり、それを削除ルーチン
に含ませておくこともできる。例えば、各々の待
ち行列要素中の既知の位置に優先順位標識が与え
られ、そして削除ルーチンは探索引数として特定
の優先順位標識を指定することにより、待ち行列
においてその優先順位を含む最初の要素を探す。 例えば、所与の優先順位を有する要素を見つけ
るために、各要素に含まれるポインタを用いて要
素が次々にアクセスされ、その中の優先順位標識
が指定された優先順位標識と比較される。指定さ
れた優先順位標識がどれかの要素で見つかると探
索は停止され、その要素が削除される。 要求された優先順位を有する要素の全部を削除
するのであれば、待ち行列の最後の要素に達する
まで探索は続く。 よつて、第２図において、例えばCPU３のプ
ログラムによる削除ロツクの保持は、アンカー・
ポイント要素がCPU１またはCPU２によつて並
行して挿入されるのを妨げない。削除ロツクは同
じ待ち行列の削除操作に現在１台のCPUだけが
携つていることを保証する。 このように、第２図のCPU３で実行中の削除
ルーチンは次の基本ステツプを含む： (A) 待ち行列１０を使用して削除操作を行なつて
いることを他のユーザに知らせるためにロツ
ク・フイールドを保持する。 (B) 削除される要素を見つけるため待ち行列１０
を探索する。 (C) 削除ルーチンの出力領域に見つかつた要素の
アドレスを書込む。このアドレスは待ち行列中
の先行要素にあるポインタであつて、削除され
るべき要素をアドレス指定する。 (D) 見つかつた要素内のポインタを先行要素のポ
インタ・フイールドに移し、それによつて先行
要素のポインタは見つかつた要素の次にある要
素をアドレス指定する。この動作は見つかつた
要素を削除するためそれに対するポインタを待
ち行列から除去し、見つかつた要素がもはや待
ち行列でアドレス指定されないようにする。も
しアンカー・ポイント要素が削除されるのであ
れば、先行要素は存在せずそしてアンカー・ポ
インタは、CS命令を用いて削除されるアンカ
ー・ポイント要素にあるポインタに変更され、
その次にある要素をアドレス指定せねばならな
い。CS命令は、他のCPUで同時に遂行されて
いる挿入操作によるアンカー・ポインタの変化
に対して待ち行列の保全性を保証するのに必要
である。 (E) 待ち行列１０がもはや削除操作で使用されて
おらず、従つて新たに削除操作が可能であるこ
とを他のユーザ・プログラムに知らせるために
ロツク・フイールドをオフにセツトする。 挿入または削除ルーチンを実行するには、最
初に第２図のアンカー・ポインタ２０の内容を
アクセスして待ち行列１０の最初のアンカー・
ポイント要素を見つける。 削除探索はアンカー・ポイント要素にあるポ
インタをもアクセスして次の要素を見つけねば
ならない。このステツプは、要求された要素が
見つかるまで、または待ち行列１０の終りを示
す全０のポインタが見つかるまで続けられる。
CPU３によつて実行されることがある特殊な
削除ルーチンの例は、待ち行列から要素を
FIFO方式で取出す技術を表わす次の表のシス
テム／370アセンブラ言語ルーチンの目的コー
ドによつて与えられる。

【表】 場合、先行要素の
ポインタ〓フイー
ルドを0にセツト
する。
DONE DS 0、H レジスタ4
は削除
された要素のアド
レスを含む。
(かくて非LIFOロツクが解除される。)
第５図及び第６図は同様なFIFO削除ルーチン
の流れ図である。第５図のステツプ64は持ち行列
に１よりも多くの要素があるかどうかを調べ、１
つの要素だけがある場合はステツプ67でそれを待
ち行列から削除することを試みる。ステツプ61、
62、63、68及び69については説明は不要であろ
う。 第６図は待ち行列の最後の要素を探索する。次
の要素が順次見つかるごとに、ステツプ71及び72
で現要素とその先行要素のアドレスをR7とR3に
各々保管する。R7にある先行要素のアドレスは、
ステツプ74で最後の要素が見つかると保持され
る。そして、ステツプ76で、その要素のポイン
タ・フイールド（全０）がR7の内容によつてア
ドレス指定された先行要素に移される。ステツプ
77は、削除された要素の出力アドレスがR3にあ
ることを示す。そしてステツプ78で非FIFO削除
ロツク・フイールドがオフにセツトされる。 第５図及び第６図における重要な点は第５図の
ステツプ61が終つた後は、削除ルーチンによる待
ち行列の探索が保証されていることである。要素
を削除するためには、削除ロツクを保持しなけれ
ばならないので、この削除ルーチンが削除ロツク
を保持している限り待ち行列中のどの要素も他の
CPUのプログラムによつて削除されることはな
い。しかしながら、前に説明したように、他の複
数のCPUで実行されている挿入ルーチンによつ
て新しい要素（アンカー・ポイント要素）を次々
に挿入していくことは可能である。新しい要素の
挿入は、最初に識別されたアンカー・ポイント要
素とその待ち行列の最後の要素の間にある要素の
連鎖には影響しない。 第７図及び第８図は、汎用レジスタR6で指定
された探索引数を含む最初の要素を削除する削除
ルーチンの流れ図である。待ち行列の各要素の探
索引数（SA）は、第９図に示すように、先行要
素内のポインタによつて指定されたアドレスから
指標値Ｉだけ離れたところに置かれる。 第７図のルーチンは、要素の削除を要求するプ
ログラムがR6に探索引数をロードした後に開始
される。 第７図のステツプ80において、呼出しプログラ
ムによつてオンにセツトされた状態でロツクを受
取ることによつて、またはオフの状態で受取られ
た場合にはそれをオンにセツトすることによつ
て、削除ロツクが保持される。削除ロツクのオン
の状態は他のプログラムが待ち行列中の現アンカ
ー・ポイント要素を含む任意の要素を変更するこ
とを阻止する。（ロツクは削除ルーチンから出る
ときにオフにセツトされる。）ステツプ81におい
て、アンカー・ポインタがR1にロードされる。
ステツプ82において、ロードされたアンカー・ポ
インタ値を検査して空の待ち行列であるかどうか
を調べる。空でない場合は、ステツプ83におい
て、R1の内容によつてアドレス指定されたアン
カー・ポイント要素内のポインタをR3にロード
する。よつて、R3は現アンカー・ポイント要素
にあるポインタを有する。ステツプ84において、
最初の要素の探索引数がR6の内容と比較され、
もしそれらが一致すると、ステツプ87において、
その削除を試みる。ステツプ88において、削除が
成功であるかどうかが決定され、成功の場合は、
ステツプ89において、R1が削除された要素のア
ドレスを含むことが表示され、ステツプ90におい
て、ロツクがオフにセツトされ、呼出プログラム
へのリターンが行なわれる。 しかし、ステツプ84において、最初の要素が目
的とする探索引数を有しない場合は、ステツプ85
において、R3にあるポインタを検査してそれが
最後の要素であるかどうか、すなわちそのポイン
タ値が０であるかどうかを決定する。待ち行列に
ある要素が１つだけの場合は、この時点で探索は
終了し、ステツプ86において、ルーチンはロツク
をオフにセツトし、呼出しプログラムにリターン
する。 しかしながら、ステツプ85において、待ち行列
に２つ以上の要素が見つかつた場合には、Ｂ点を
経由して第８図に進む。 第８図は待ち行列１０の探索の継続である。こ
れは待ち行列の２番目の要素から開始し、(a)所望
の探索引数を含む要素が見つかるか、または(b)そ
のような要素が見つかることなく待ち行列の終り
に達する場合に終了する。 第９図は、第８図にプロセスによつて探索され
る待ち行列の一部を表わす。汎用レジスタR3は
現在検査されている要素のアドレスをロードされ
る。汎用レジスタR5は現在検査されている要素
にあるポインタをロードされる。このポインタは
待ち行列１０の次の要素をアドレス指定する。 第８図のステツプ91が開始されるとき、R1は
アンカー・ポイント要素のアドレスを含み、R3
はアンカー・ポイント要素にあるポインタを含
む。そして、ステツプ91においてR5はアンカ
ー・ポイント要素にあるポインタをロードされ
る。ステツプ92において、現在検査されている
（すなわち、R3によつてアドレス指定された）要
素が探索引数から、それが要求された要素である
かどうかを検査する。要求された要素ではない場
合は、ステツプ93において、R5にあるポインタ
が待ち行列の終りを示しているかどうかを決定す
る。もしそれが待ち行列の最後の要素ならば、ス
テツプ94において、出力領域に「未発見」標識が
記憶され、ステツプ96において、削除ロツクがオ
フにセツトされ、呼出プログラムへのリターンが
行なわれる。現要素が最後の要素ではない場合、
ステツプ97において、R1にR3の内容をロード
し、R3にR5の内容をロードすることによつて探
索が続行される。 ステツプ92で探索引数の一致が検出されると、
ステツプ101において、現在R3にそのアドレスを
有する要素が削除される。すなわち削除される要
素内の（R5にある）ポインタが、R1の内容によ
つてアドレス指定される先行要素のポインタ・フ
イールドに記憶される。次に、ステツプ102にお
いて、R3の内容すなわち削除された要素のアド
レスが特定の出力領域に記憶される。そしてステ
ツプ96において、削除ロツクがオフにセツトさ
れ、呼出プログラムへのリターンが行なわれる。 第７図、第８図及び第９図の削除ルーチンは目
的とする探索引数を含む全ての要素を１回の探索
オペレーシヨンで削除するように、容易に変更し
うる。例えば、所与の優先順次値を有する要素を
単一の削除要求に応答してすべて削除することが
できる。

【図面の簡単な説明】

第１図は実施例の概略を示すブロツク図、第２
図は３台のCPUで２つの挿入ルーチン及び１つ
の削除ルーチンが同時に実行される例を示すブロ
ツク図、第３図及び第４図は先行技術のLIFO挿
入ルーチン及びLIFO削除ルーチンの流れ図、第
５図及び第６図は本発明に従うFIFO削除ルーチ
ンの流れ図、第７図及び第８図は本発明に従う他
の削除ルーチンの流れ図、第９図は第８図に従つ
て処理される待ち行列の一部分を示すブロツク図
である。

Claims (1)

1. 【特許請求の範囲】 １ １以上の要素が該要素に含まれるポインタに
   よつて連鎖されている待ち行列に対し、 オフ状態にセツトされている場合にのみ前記待
   ち行列に含まれる任意の要素の削除を可能にする
   削除ロツクと、前記待ち行列中の先頭要素をアド
   レス指定するアンカー・ポインタとを準備し、 前記削除に先立つて前記削除ロツクをオン状態
   にセツトし、 前記アンカー・ポインタによつてアドレス指定
   された新たな要素を比較置換型の命令によつて前
   記待ち行列へ挿入するときは前記削除ロツクを無
   視する、 ことを特徴とする待ち行列制御方法。