JPS5983249A - 待ち行列制御方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の分＊］ 本発明は、マルチプロセッサ（ＭＰ）システムの各プロ
セッサで非同期的に実行されている複数のプログラムが
１つの待ち行列に対する挿入及び削除を並列に行なえる
ようにすることによって、Ｍｒ’システムの動作効率を
改善する方法に係る。

［発明の背景］ 待ち行列は過去及び現在のデータ処理システムで一般に
使用されている。ある待ち行列はハードウェア論理回路
によって管理され、他の待ち行列はプログラム式または
マイクロプログラム式のルーチンによって管理されてい
る。多数の待ち行列は一般に、データ処理システムの再
使用可能なハードウェア及びソフトウェアの資源（待ち
行列自身を含む）を制御するためにシステム制御プログ
ラムによって用いられる。

各々の待ち行列は一般に複数の要素から成る。

例えば、ある待ち行列は現在レコードを読取りまたは書
込むプロセス中のすべての■／○装置を追跡するシステ
ムで用いられることがあり、その場合、待ち行列の要素
の数は使用中のＩ１０装置がないことを表わすゼロから
、多数のＩ１０装置が使用中であることを表わす大きな
数までの間を変動する。別の例は、実行可能なユーザー
・プログラム・タスクにＣＰＵを割振るシステム資源で
ある監視ディスパッチャ・プログラムの使用に関する全
てのユーザー要求を受取るのに用いらＩＬる待ち行列で
ある。

待ち行列は待ち行列中の要素の相対的な位置関係によっ
て次の２つの一般的なタイプに分類されることがある。

第１は物理的に連続した位置に要素を有する連続待ち行
列である。

第２は物理的に主記憶（Ｍ　Ｓ　）内のどこにでも分散
さ汎うる要素を有する連鎖待ち行列であ、る。

連続待ち行列の例は、Ｍ　、　Ｔ　ａ　ｒ　ａ　ｄ　ａ
　］、ｓ　ｋ　ｙ、”ＦｊｒｓＬ−Ｔ＋＋／Ｆｉｒｓｔ
；−０ｕｌ；　　Ｑｕｅｕｅｉｎｇ　　丁ｅｃｌ＋ｒ＋
１ｑｕｅ　　ｔｊｓｉｎｇＣｏｍｐａｒｅ　ａｎｄ　Ｓ
ｗＲｐ″、ＩＢＭ　Ｔｅｃｈｎｉｃａｌ、　Ｄｉｓｃｌ
ｏｓｕｒｅ１３ｕｌｌｅｔｉｎ、　■ｏ１．　　　１８
　、　Ｎａ　５　、　　Ｏｃｔ；ｏｂｅｒ　　　　ｉ　
　９　７５．１５４７頁に示されている。

本発明は連続待ち行列は取扱わず、連鎖待ち行列だけ、
特にアンカーを有する単−系（ｓｉｎｇｌｅｌ；ｈｒｅ
ａｄ）の連鎖待ち行列だけを取扱う。各々の連鎖待ち行
列は主記憶の所定の位置にアンカー・ブロックを有し、
その待ち行列を制御する。アンカー・ブロックはその待
ち行列を構成する要素の連鎖をアドレス指定する（アン
カー・ポインタと呼ばれる）アドレスを含み、各々の要
素はその待ち行列中の次の要素へのポインタを含む。待
ち行列の最後の要素はそれを最後の要素として識別する
標識コード（しばしば全０）をそのポインタ位置に有す
る。現在もし待ち行列中に要素がない（すなわち、その
待ち行列は空である）ならば、アンカー・ブロックはそ
のアンカー・ポインタの位置に空のコード（例えば、全
０）を含む。

要素はそのアンカー・ブロックを変更することによって
待ち行列に挿入されたり、待ち行列から１４１１除され
たりする。最も容易モ最も速い挿入と削除はアンカー・
ポインタ自身を変えることによって行なわ］し、その場
合、挿入はアンカー・ポインタを待ち行列に置かれる新
しい要素のアドレスに変更することを伴ない、削除はア
ンカー・ポインタをそれによってアドレス指定された要
素中のポインタに変更することを伴なう。アンカー・ポ
インタによって直接アドレス指定される待ち行列の先頭
要素は「アンカー・ポイント要素」と呼ばれる。後入先
出（Ｌ　Ｊ　ＦＯ）型の待ち行列はアンカー・ポイン１
−要素を挿入し削除する。アンカー・ポイント要素はＬ
ＩＦＯ待ち行列において最新かつ最後の要素であり、削
除される要素の候補である。

しかしながら、多くのデータ処理活動は１．　ｉ　ｌ？
０型の削除操作を使用できず、先入先出（１７１ＦＯ）
型または他の非ＬＩＦＯ型の削除操作を必要とする。

本発明は、ＩｊＦＯ削除操作及び非し、ＩＦＯ削除操作
の組合せに対しても使用できるが、基本的には純粋なＬ
ＩＦＯ削除操作以外の操作を必要とする連鎖待ち行列に
重点が置かｊｂている。

ＭＳを共有する２台以上のプロセッサあるいはＣＰＵが
同時に且つ非同期で別個の命令ス１〜リームを実行しう
る多重処理は、共有Ｍ’Ｓ中の待ち行列の変更に関する
特殊な問題を呈すること力１ｄ忍ぬられている。例えば
、第１のプロセッサ力へ待ち４１列要素の挿入または削
除を完了する前Ｌ；、第２のプロセッサが別の待ち行列
要素の挿入また番よＩＪ＋Ｊ　Ｐｆｉを試みることは望
ましくなく、どのプロセッサも別のプロセッサによる待
ち行列中の不完全な変更に基づいた動作をしてはならな
い。

この問題は先行技術では一般に２つの異なる方法で解決
されている。先行技術における第１の解決方法は待ち行
列をロックするもので、それ（こよりその待ち行列を使
用しているプログラムの全てを直列化し、任意の時間に
おいて１つのプログラムだけがその待ち行列をアクセス
できるよう番こする。このようなロッキング動作は、例
えば１８Ｍシステム／３７０のテスト設定命令（ＴＳ）
または比較置換命令（Ｃ５，ＣＤ’Ｓ）の実行によって
サポートされる。待ち行列を使用する全てのプログラム
の間のプログラミング規約として、全てのプログラムは
待ち行列の変更を試みる前に自発的に待ち行列ロック・
フィールドを検査してその状態を確認することが要求さ
れ、１つのプログラムだけが選択されてロック・フィー
ルドをセラ１−シてからその待ち行列を変更する。選択
されたプログラムは、待ち行列の変更を完ｒすると、ロ
ック・フィールドをアンロック状態に変更し、かくて別
のプログラムがその後で待ち行列をロックして使用する
ことができる。この方法では、−・度に単一挿入操作ま
たは単一削除操作だけが遂行可能であって、同時遂行は
不可能である。

先行技術における第２の解決方向はロックを使用せず、
Ｌ、ＩＦＯ待ち行列だけを対象にしている。

Ｌ　Ｔ　Ｉ”　０待ち行列はその保全性を維持しつつ、
複数のＣＰＵにおける異なるプロゲラ１１からの同時要
求によってアンカー・ポイント要素が挿入されたり削除
されたりすることを可能にする。第２の解決方法は１３
Ｍシステム／３７０のＯ８命令またはＣＩ）　Ｓ命令を
待ち行列アンカー・ポイントに直接用いて、アンカー・
ポイン１〜要素の挿入または削除を成しとげる。第２の
解決方法の背景は１８Ｍシステム／３７０解説書（Ｎ　
：　ＧＡ　２２−７比較置換命令は、単一ワード・フィ
ールド（ＣＳ）命令及び２重ワード・フィールド（ＣＤ
Ｓ命令）を扱う２つの形式があり、待ち行列アンカー・
フィールドの大きさく１ワードまたは２ワード）によっ
ていずｔｙかが選択される。Ｃ８命令またはＣＬ）　Ｓ
命令の実行中は、ＭＰシステ１１におけるどのプロセッ
サも別のプロセッサによる削除操作または挿入操作に干
渉することはできない。

全ての待ち行列管理プログラムは、指定された汎用レジ
スタＢ２の現在の内容に変位Ｄ２を加算した値を待ち行
列アンカー・ポインタの主記憶アドレスとして使用する
。有効アドレス１）２（Ｂ２）を用いて取出されたアン
カー・ポインタは汎用レジスタＲ１にロードされ、それ
により最初の待ち行列要素が指定される。Ｌ　Ｔ　’Ｆ
　Ｏ挿入ルーチンは最初に、待ち行列に挿入されるべき
新しい要素をセラ１−アップし、その中にアンカー・ポ
インタを書込み、そして汎用レジスタＲ３にこの要素の
アドレスを記憶せねばならない。ＬｆＦＯ削除ルーチン
は最初に、待ち行列から削除されるべきアンカー・ポイ
ン１〜要素内のポインタの内容を汎用レジスタＲ３に記
憶せねばならない。次に、要求された挿入または削除を
行なうためにＣ８命令が実行される。そのときＣ８命令
はＲ１を検査してアンカー・ポインタの内容が変更さ］
したかどうかを決定する。それが変更されていない場合
は、Ｒ３にあるアドレスがアンカー・ポインタに記憶さ
れ、待ち行列においてアンカー・ポイント要素の挿入ま
たは削除が行なわれる。アンカー・ポインタがＲ１で変
更されていると５挿入または削除の試みは失敗するが、
Ｒ１には現アンカー・ポインタが再ロードされる。Ｃ８
命令の条件コード（ＣＣ）はその実行が成功したかまた
は失敗したかを表わす。

ＬＴＦＯ方式で要素を挿入または削除するためにＣ８命
令によってアンカー・ポインタだけが置換される場合に
は、挿入操作または削除操作の間に待ち行列を破壊する
大きな危険が存在することが経験によって知られている
。

待ち行列の保全性が危険にされされるのは＝（１）　　
第１のプログラムが、アンカー・ポイント要素中のポイ
ンタがゼロであることを発見した後に、そのとき待ち行
列における単一の要素を削除することを試みている間に
；（２）第２のプログラムがその要素を削除して、新し
い要素を挿入し、次いで前に削除した要素を新しいアン
カー・ポイン１−要素として再び挿入したときであって
；（３）これらが第１のプログラムにおけるＣ８命令の
実行前に全て行なわれたときである。この場合、第１の
プログラムは、再挿入されたアンカー・ポインタとの比
較で一致が得られる為、そのＣ８命令の実行を成功裏に
完了する。その結果、アンカー・ポインタに全０フイー
ルドが挿入され、待ち行列が空であることを表わす。こ
れは、途中で別の要素が待ち行列に置かれたこと゛を第
１のプログラムが知らないからである。この全０のアン
カー・ポインタがポインタ連鎖を壊し、それによって待
ち行列（そのとき空ではない）における要素の存在を無
視するので、待ち行列が破壊される。

待ち行列障害は多分、データ処理動作が停止するか、ま
たは正しくない結果を生じる原因となるから、高速デー
タ処理システムにおいては危険性の高い待ち行列は無用
のものである。このタイプのソフトウェア障害の検出は
、発見して訂正することが困難なことがあり、これはシ
ステｔトダウンにつながる。

待ち行列の保全性に対するこの危険性は先行技術ではカ
ウンタ・フィールドのイ１加によって軽減されている。

カウンタ・フィールドはアンカー・ブロック内でアンカ
ー・ポインタの隣りに置かれる。アンカー・ポインタ及
びカウンタ・フィールドはいずれも１ワ一ド幅であり、
そり両方がＣＤＳ命令によって１単位として置換される
。

ＣＳ命令またはＣＤＳ命令に条件付き分岐命令が続き、
実行されたＣ８命令またはＣＤＳ命令の条件コードを検
査して、要求された挿入または削除が成功したかどうか
を決定する。不成功の場合は、ルーチンはループを戻っ
てＲ３の内容を再検査したのちＣ８４命令またはＣＤＳ
命令を再実行し、必要ならばＣ８命令またはＣＤＳ命令
の実行が成功するまでこのループを反復する。

下記の表は前掲のＩＢＭシステム／３７０解説書の３１
４頁に載っているものと殆んど同じ挿入ルーチン及び削
除ルーチンを示したもので、コーディングはシステム／
３７０アセンブラによっている。ＣＤ　Ｓ命令を実行す
ると、■ワード幅のアンカー・ポインタ及びその隣りに
位置するＪワード幅のカウント値を１単位として待ち行
列アンカー・ブロックに記憶することができる。

要素挿入ルーチンまたは要素削除ルーチンの実行を開始
する時点から、Ｃ８命令またはＣＤＳ命令の条件コード
が０である（挿入または削除が成功であったことを表わ
す）ことを各々のルーチンが発見するまで、ｃ　ｐ　ｕ
は待ち行列の要素を挿入または削除するプロレス中であ
ると考えらＡしる。

従って、Ｍ　Ｉ）システ１１においては、異なるＣ　Ｐ
　Ｕのいくつかのプログラムが同時に同じＬ　Ｉ　Ｆ”
　Ｏ待ち行列において挿入ルーチンまたは削除ルーチン
を実行することがあり、そのＣ８命令またはＣＩ）Ｓ命
令の実行が成功して各々のルーチンの競合が終るまでそ
］しらのルーチンのいくつかは競合によ−〕でルーピン
グを行なう。

２台のＣＩ）　Ｕが同じＬＩＦＯ待ち行列に対して同時
に待ち行列管理ルーチンを実行している場合を例にとっ
てもう少し詳しく説明する。これらのＣＰＵの間では、
互いにＬＩＦＯ待ち行列をアクセスしようとしているこ
とが分らない、すなわち両者の間には同期通信手段がな
いので、どちらのＣＰＵもＬＩＦＯ待ち行列に対し非同
期で挿入ま一チンがそのオペランドをセラ１〜アツプす
ることによって実行を開始したが、第２のＣＰＵのルー
チンがそのＣｌ）　Ｓ命令の実行に成功して現アンカー
・ポインｌ−要素を挿入または削除し、それによって記
憶場所Ｉ）２（Ｂ２）にあるアンカー・ポインタの内容
が変更されたときに、まだ自身のＣＩ）Ｓ命令を実行し
ていなかったものと仮定すれば、第１のＣＩ）　Ｕのル
ーチンがそのＣＤＳ命令を実行しても成功しない。その
理由は、Ｂ２（Ｂ２）にある実際のアンカー・ポインタ
またはカウンタが前にロードさｔしてＲ１のアンカー・
ポインタまたはＲ１＋　１のカウンタに一致しないから
である。

しかしながら、ＣＩ）　Ｓ実行の失敗はＲ１に新しい実
際のポインタ値を再びロードし、第１のＣＰＵによる次
のＣＤＳ実行のため′の準備をする。もしＢ２（Ｂ２）
にある実際のポインタ及びカウンタ値が次のＣＤＳ実行
の時点でＲ１及びＲ１＋１の内容と変っていなかったな
らば、その実行は成功である。従って、ＣＤＳ命令はＬ
ＩＦＯ待ち行列の不適当な変更を防ぎ、その保全性を維
持する。

先行技術の待ち行列管理プログラムは、ロックなしのＬ
ＩＦＯ待ち行列のための挿入ルーチン及び削除ルーチン
を多年にわたり行なって％Ｎる。その理由は、複数のプ
ログラム及びＣ’ＰＴＪが挿入及び削除を並行して行な
えるからである。あシ）シこく、このタイプのロックさ
れない待ち行列の処理番よ、ＬＩＦＯ（先入先出）のよ
うな非ＬＩＦＯ待ち行列に対して使用できない。

第３図及び第４図は、ＬＩＦＯ待ち行列におり）で新た
なアンカー・ポイント要素の挿入または現アンカー・ポ
イン１−要素の削除を行なう在来の待ち行列オペレーシ
ョンで使用されることがある前述の先行技術のＬＩＦＯ
挿入及び削除ルーチンの流れ図を示す。これらのルーチ
ンは待ち行列サービスを必要とするプログラムに挿入さ
れている。

第３図のＬＩＦＯ要素挿入ルーチンにおいて、要素挿入
はステップ３４で、与えられたＣＰＵにおけるＣＤＳ命
令の実行の成功によって得られる。

すなわち、Ｒ１にロードさＡしたアンカー・ポインタ及
び次の汎用レジスタＲ１＋１にロードされたカウンタ（
これらはステップ３１によって、またはこのルーチンの
前回の反復でステップ３４によってＭＳのＢ２（Ｂ２）
に位置するアンカー・ポインタ及びカウンタにロードさ
れている）を、現在アンカー・ブロックに存在している
実際のアンカー・ポインタ及びカウンタと比較し、それ
己が依然として同じでいる（ステップ３１からステップ
３４でのＣＤＳ命令の実行までの間に、他のいず４しの
ルーチンも待ち行列の挿入または削除を行なっていない
ことを表わす）かどうかを決定する。

もし１り１とＲ１＋１の内容がＣＤＳ命令実行時にＢ２
（１３２）における値に依然と−して同じてあれば、Ｍ
Ｓのアンカー・ブロックにレジスタＲ３からの新しい要
素のアドレス及びＲ３＋１からの増加さ］ｔたカウンタ
値を記憶するとともに、そのＣＰＵにおける条件コード
（ＣＣ）を０にセットする。しかしながら、もしＲ１及
びＲ１＋１の内容がＢ２　（Ｂ２）における実際のアン
カー・ポインタ及びカウンタの値と異なるならば、ＣＤ
Ｓ命令は代りにレジスタＲ１及びＲ１＋１にアドレスＤ
２（Ｂ２）の実際のアンカー・ポインタ及びカウンタの
値をロードするとともに、そのＣＩ）　Ｕの条件コード
（ｃｃ）を１にセラ１−する。

レジスタＲ３は前にステップ３３で、挿入さＪＬる新し
い要素のアドレスによってセットアツプ済であり、その
隣接汎用レジスタＲ３＋１は１だけ増分されたカウンタ
の値によってセラ１〜アツプ済みである。

それぞれのルーチンはステップ３５で条件イ・１き分岐
命令を用いて条件コード（ＣＣ）を検査する。

もしＣＣが１であることが分れば、挿入は生じなかった
ことになり、ルーチンはステップ３２に戻り、次の反復
動作で新しい要素のポインタを新しいアンカー・ポイン
タにセラ１〜し、ステップ３３でＲ３＋１の増分された
カウンタ値を再決定し、次いでステップ３４で、もう１
つの挿入の試みとして、成功するかどうかは分らないが
ＣＤＳ命令を再実行する。それによってルーチンは必要
な挿入がなされる（ＣＣ＝Ｑ）までＣＤＳ命令を１回以
上実行する。

第４図のＬＩＦＯ要素削除ルーチンにおいて、こＪＬが
呼出しプログラムによって開始されると、ステップ４１
で汎用レジスタＲ１及びＲ１＋１が第３図のステップ３
１で行なわれたようにロードされる。汎用レジスタＩｔ
　ｉ　＋　ｔにロードされたカウンタ値は挿入または削
除の度に増分される。空の待ち行列から要素を削除しえ
ないから、次にステップ４２で待ち行列が空である（す
なわち、要素を１つも持たない）かどうがが決定される
。もし待ち行列が空であれば、アンカー・ポインタが全
Ｏになっている。よって、ステップ４２では、アンカー
・ポインタの全０値に関して検査が行なわれ、待ち行列
が空でない、すなわち１つ以上の要素を有する場合にの
みステップ４３以下の削除動作が続行する。

ステップ４３では、Ｒ１の内容によってアドレス指定さ
れるアンカー・ポイント要素にある現在のポインタ値が
Ｒ３にロードされる。ステップ４４では、新しいカウン
タ値、すなわちアンカー・ブロックから取出されＩだけ
増分されたカウンタ値が次の汎用レジスタＲ３＋１にロ
ードされる。

次にステップ４５では、Ｒ１の値とＲＩ＋１のカウンタ
値が依然としてＭＳのＢ２　（Ｂ２）におけるアンカー
・ポインタ及びカウンタの値と同じであるかどうかを検
査して、他のいすＪＬかのプログラムが実際のアンカー
・ポインタを変更するように干渉したか、例えば要素の
挿入または削除を行なったかどうかを決定する。次のス
テップ４６では、得ら汎だ条件コードを検査してＣＤＳ
実行によって挿入がなされたかどうかを決定する。ＣＣ
ＣＯＯ場合は、削除がなされており、アンカー・ブロッ
クは新しいポインタ及び新しいカウンタ値を有する。ス
テップ４７は、Ｒ１にあるアドレスが削除された要素を
表わし、ルーチンがその呼出プログラムにリターンする
ときＲ１が削除操作の出力を含むことを表わす。

しかしながら、もしステップ４６でＣＣが１であること
を表わせば、挿入は行なわｈなかったが、ＣＤＳ命令が
実際の現アンカー・ポインタ及びカウンタの値をＲ１及
びＲ１＋１に各々ロードしている。従って干渉するプロ
グラムが待ち行列を空にしていることがありうるので、
条件付き分岐によってルーチンはステップ４２に戻り、
待ち行列の空のステータスを再検査する。ステップ４２
〜４６は、削除が行なわれ、ステップ４６でＣＣＣＯＯ
検出されるまで反復される。

アンカー・ポインタと共にカウンタが使用されている理
由は、ステップ４３とステップ４４の間で他のプロセッ
サが介入して複数の挿入操作及び削除操作を行なったた
めに、アンカー・ポインタの値は同じままであるが、ア
ンカー・ポイント要素のポインタ・フィールドの値が変
えられていることがあるからである。このような可能性
に対する保護どしてＣＤＳ命令が使用され、各々の挿入
または削除のカウンタ値を調整するとともに、ステップ
４４で新しいカウンタ値を比較する。等しくないカウン
タ値はｃｃ＝ｉを生じ、ルーチンはステップ４６からス
テップ４２に戻って再び削除を試みる。

先行技術において、同じ要素を含む２つの待ち行列、即
ち要素挿入用の入力待ち行列及び要素削除用の出力待ち
行列を用いることにより、ＦＩＦＯ方式のオペレーショ
ンが行なわれている。この方法は従来のＩＢＭ　　ＭＶ
Ｓプロゲラ１１のＩＥＡＶＥＤＳＯモジュール及びＩＥ
ＡＶＥＳＣ１モジュールで用いられている。前にＬＩＦ
Ｏ要素挿入について説明したように、比較置換技法を用
いれば、入力待ち行列をロックせずにその保全性を失う
ことなく複数のＣＰＵによって要素を人力待ちｆＴ列に
効率的に挿入することができる。ある状態（例えば、人
力待ち行列のサイズが最大であるが、または出力待ち行
列が空である状Ｓ）が生じると、両方の待ち行列がロッ
クされてその使用が阻止されるとともに、第１の待ち行
列の全要素が除去さＪ＋、て、（例えば、そのポインタ
・チェーンを逆にすることによって）ＦＩＦＯシーケン
スに再配列された後、第２の待ち行列である出力待ち行
列に挿入される。第１の待ち行列からの出力及び第２の
待ち行列への入力は、この待ち行列再構成プロセスの間
はロックされている。出力待ち行列はその後、挿入ロッ
クを維持して挿入を阻止するが、アンカー・ポイント要
素を削除することによって、削除ロックなしにＦＩＦＯ
方式での削除操作を可能にする。よって、第２の待ち行
列が空にされている間に新しい要素がその中に挿入され
ることはない。第２の待ち行列の挿入可能な唯一の要素
は、ロック制御の下に第１の待ち行列から与えらｈる要
素である。

［発明の概要］ 本発明は単一の連鎖された待ち行列に対する並列オペレ
ーションを可能にする。すなわち複数のプロセッサが要
素挿入ルーチンを同時に実行すること、及びそれと同時
に任意のプロセッサが要素削除ルーチンを実行すること
によって待ち行列から任意の要素を取り除くこと゛が可
能である。削除プロセスの間、削除ロックがオンにセラ
１〜されるが、これはアンカー・ポイン１〜要素を挿入
するために並列に実行される１以上のルーチンの処理に
は影響しない。

非Ｉ、ｉＦＩ待ち行列をロックしてそこから非アンカー
・ポイント要素を削除する場合には、まず要求された非
アンカー・ポイン１〜要素を見つけるために待ち行列が
探索され（アンカー・ポインタから始める）、待ち行列
中の先行要素にあるポインタが削除される要素のアドレ
スとして出力される。そして、削除される要素にあるポ
インタをその先行要素へ移すことによって目的とする非
アンカー・ポイント要素が削除される。

待ち行列をロックしてアンカー・ポイント要素を削除す
る場合は、待ち行列においてアンカー・ポイン１−要素
に続く要素をアドレス指定するようにアンカー・ポイン
タが変更され、そして削除されるアンカー・ポイン１−
要素のアドレスが出力される。

非ＬＩＦＯ処理のうちで重要なのは、待ち行列の最後の
要素を要求された要素と考えるＦＩＦＯ処理である。最
後の要素はそのポインタ・フィールドにある待ち行列終
結コードによって識別される。

本発明は非純粋ＬＩＦＯ待ち行列（ユーザのオプション
によって待ち行列がＬＩＦＯ方式または非Ｌ　Ｉ　ＦＯ
方式で削除されるという意味で「非純粋」である）にお
いて効率的な処理を与える。本発明は、待ち行列にアン
カー・ポイン１〜要素を挿入する場合は、いかなるロッ
クも使用しない。そのときの待ち行列の保全性は、前述
のＣＳ命令の使用によって維持される。

本発明の目的は多重プロゲラミンクあるいは多重処理の
ための新規な待ち行列管理方法を提供することにあり、
それにより下記のことが可能になる。

（１）　　非ＬＩＦＯ待ち行列及びＬＴＦＯ待ち行列ど
して働く単一の待ち行列の処理効率を増大しながら、カ
ウンタ・フィールドを用いずに待ち行列の保全性に関す
る危険を除く′。

（２）　　同じ待ち行列に対し、あるユーザ・プログラ
ムによる非ＬＩＦ○削除操作と、１以上の他のユーザー
・プログラムによるアンカー・ポイン１−要素の挿入操
作とを平行して行なえる。

（３）　　待ち行列を破壊するおそれなしに、任意のＣ
ＰＵによる非アンカー・ポイン１−要素またはアンカー
・ポイン１へ要素の削除操作と、他の任意のＣＩ）　Ｕ
による１つ以上のアンカー・ポイント要素の挿入操作と
を並列に遂行し得る非Ｌ　Ｉ　Ｆ　Ｏ待ち行列出力ロッ
クを与える。

（４）非ＬＩＩ”Ｏ待ち行列及びＬＩＦＯ待ち行列どし
て効率的に動作可能であって、その待ち行列に挿入さＪ
している１つ以上のアンカー・ポイン１〜要素の処理と
平行していかなる要素の削除処理をも可能にする待ち行
列を与える。

（５）異なるタイプのＬＩＦＯ及び非ＬＩＦＯ削除操作
が待ち行列の保全性を害する危険なしにいずれのプログ
ラムによっても任意に実行可能である効率的な並列挿入
／削除操作を可能にする単−待ち行列を与える。

（６）従来は挿入操作及び削除操作の間、待ち行列の保
全性を維持するために必要とされていた待ち行列アンカ
ー・ブロック中のカウンタを使用することなく、待ち行
列の並列ＬＩＦＯ／非ＬＩＦＯオペレーションを可能に
する。

［良好な実施例の説明コ 第１図は、主記憶にある連鎖待ち行列（以下、単に［待
ち行列］という）１０を共有する複数のＯＰＵで複数の
プログラム（１〜Ｋ）が実行されているＭＰシステムに
おいて、本発明に従い単一の待ち行列１０に対してなさ
れる一般的なオペレージＡンを示す。プログラム１〜プ
ログラムＪは同時に待ち行列ＩＯに要素を挿入すること
ができそれと同時にプログラムにはアンカー・ポイン１
−要素を含み得る１つ以上の要素を同じ待ち行列１０か
ら削除することができる。

本発明は挿入操作及び削除操作を並列に遂行している間
、フィールドなしに待ち行列の保全性を維持しうるから
カウンタ・フィールドは待ち行列１０に対して与えられ
ていな゛い。

プログラム１−Ｊのどれも待ち行列】０において、いか
なるロックも用いず、こＩＬらのプログラムの各々はＳ
／３７０Ｃ８命令を用いて要素を待ち行列のアンカ一端
に挿入する。しかしながら、プログラムにはその削除操
作を遂行するため番こ（よ。

削除ロック１１を得なけオしばならなし）。ブロク゛ラ
ムにはアンカー・ポイン１へ要素の場合を除き、要素（
単数または複数）を削除するのにＣＳ命令またはＣＩ）
　Ｓ命令を用いなくてもよい。（非同期しこ動作してい
る他のＣＩ）　Ｕが削除ロック１１を要求していること
があるので、削除ロック１１を得るため、ＣＳ命令、Ｃ
Ｉ）Ｓ命令またはＴＳ命令を用いる必要があるかも知れ
ない。） 第２図は、アンカー・ブロック２０及び要素Ｎ〜０（こ
れらはアンカー・ブロックと各々の待ち行列要素Ｎ〜０
に含まれたポインタによってアンカー・ブロック２０に
連鎖されている）を含む待ち行列１０において要素を挿
入または削除するため同時に遂行できるプロセスの構造
例である。アンカー・ポインタ２１は待ち行列１０にお
けるアンカー・ポイント要素Ｎの位置を示すアドレスで
ある。アンカー・ポイン１−要素Ｎはアンカー・ポイン
タ２１に含まれたアドレスによって直接アドレス指定さ
れる。

アンカー・ポイン１−要素Ｎのポインタは次の待ち行列
要素（Ｎ−１）の位置を示し、要素（Ｎ−１）のポイン
タはその次の待ち行列要素の位置を示す。以下同様な位
置指定が最後の要素０に達するまで続Ｕられる。最後の
要素０はポインタ・フィールド中の特殊なコード、例え
ば全０によって識別される。ゼロ（アンカー・ポインタ
２１番よ全０）を含む任意の数の要素が任意の時点にお
り）で待ち行列ＩＯに存在し得る。このように、待ち行
列１０における要素の連鎖順序は最も新い）要素Ｎから
最も古い要素０に至る。

待ち行列１０に入力される各々の要素はアンカー・ポイ
ン１〜要素Ｎとして挿入され、それ番こよって前のアン
カー・ポイント要素は待ち行列１０番；おいて２番目の
要素（Ｎ−］、）になる。アンカー・ポイン１〜要素Ｎ
は待ち行列１０の先頭に位置し、論理的にアンカーに最
も近いとみなされるのに対し、要素０は待ち行列１０の
末尾し；位置し、論理的にアンカーから最も遠いとみな
される。

待ち行列１０のアンカー・ブロック２０及び各々の要素
は、ポインタ・フィールドの他に、待ち行列によって管
理されている要素情報を含む他の周知のフィールドを有
することがある。

フィールド１１　（アンカー・ブロック２ｏに存在しな
くてもよい）は削除ロックを含む。削除ロックは全０を
含む場合にはオフ（アンロック状態）にセットされ、そ
れ以外の場合にはオン（ロック状態）にセットされる。

削除ロックは、削除ルーチンを呼出して削除ロックを渡
す待ち行列アクセス・プログラムによってセラ１〜さＪ
Ｌることかある。

この場合、削除ルーチンは「削除ロックを保持する」と
みなされる。

待ち行列１０の各要素は、普通はＭＳの異なる領域に位
置し、待ち行列１０の他の要素と物理的に連続して配置
されることはめったにない。このように、これらの要素
は待ち行列１ｏでアンカー・ポインタ２１で始まる要素
のポインタの連鎖によって位置が示されるから、ＭＳ内
のどこにでも広く散在しうる。従って、アンカー・ポイ
ント要素Ｎは物理的にアンカー・ブロック２０の近くに
存在しなくてもよい。

待ち行列アクセス・プログラムはアンカー・ブロック２
０のＭＳアドレス及びその中のアンカー・ポインタ２１
に苅する指標を知ることによって待ち行列１０をアクセ
スする。待ち行列アクセス・プログラムの要素削除ルー
チンは、アンカー・ポインタ２１を含む待ち行列中のポ
インタの連鎖を用いることによって待ち行列１０の任意
の要素を見つけることができる。

第２図において３台のＣＰＵＩ、２及び３は同時に待ち
行列アクセス・プログラムを実行している。ＣＰＵＩ及
び２はそれぞれ独立して待ち行列挿入ルーチンを実行し
て新しいアンカー・ポイン１〜要素を待ち行列１０に挿
入しようとしており、ＣＰＵ３は並行して削除ルーチン
５０を実行して待ち行列１０の非アンカー・余インド要
素、例えば要素（０）を削除しようとしている。ＣＰＵ
　１またはＣＰＵ２の一方が最初に新しい要素Ｎの挿入
に成功し、次いで他方のＣＰＵがもう１つの新しい要素
Ｎを挿入し、これらの２つの新しい要素は待ち行列ｌＯ
の要素Ｎ及び要素（Ｎ−１）になる。

詳細に説明すれば、第２図で実行される各々の挿入ルー
チンはそオしぞれの新しい要素（Ｎ）２６及び２７をセ
ットアツプした後、Ｃ８命令のオペランドとしてそれぞ
れのＣＰＵの汎用レジスタＲ１及びＲ３をロードする。

すなわち、各々のＲ１は、ＭＳにおいて待ち行列１０の
全てのユーザに知られているアドレスＤ２（Ｂ２）に置
かれているアンカー・ポインタ２０のアドレスを受取る
。

ＣＦ）　Ｕ　１及び２のＲ３のそれぞれの挿入ルーチン
によって、新たにセットアツプされた要素２６及び２７
のＭＳアドレスをそれぞれロードされる。

各挿入ルーチンは、待ち行列をロックしない従来のルー
チン（第３図）に似ているが、カウンタ・フィールドを
使用しない点が異なっている。

第２図において、削除ルーチン５０は同時に待ち行列１
０から要素を削除するように働く。削除ルーチン５０は
最初に待ち行列１０に対する削除ロック１１を保持せね
ばならない。これは削除ルーチン５０の実行が完了する
まで保持される。削除ロック１１は削除ルーチン、また
は削除ルーチンを呼出してオンにセットされた削除ロッ
クを渡すルーチンによってオンにセットされる。

第２図において、削除ルーチン５０は非ＬＩＦＯオペレ
ーションの場合、非アンカー・ポイン１〜要素を削除す
るものとして示されている。しかしながら、本発明によ
って、アンカー・ポイン１−要素を含む任意の要素を削
除ルーチン５０によって削除することができる。

良りｒな削除ロックに関するプログラミング」二の規約
は次の通りである。ＭＰシステムで待ち行列削除ルーチ
ンを実行する事がある全てのユーザ・プログラムは待ち
行列で要素の削除を試みる前にそのロック・フィールド
の状態を検査し、非０値によってオンにセットされたロ
ック・フィールドを見つけた時は待ち行列からの削除は
行なわない。

この規約は待ち行列挿入ルーチンを実行することがある
ユーザ・プログラムがロック・フィール　、ドの状態を
検査することを必要としない。

この規約を用いる場合、削除ロック・フィールドは削除
ルーチンを呼出す前にユーザ・プログラムによって検査
されてもよい。もしロックがオフにセラ１−されている
ことをユーザ・ルーチンが発見す九ば、ユーザ・ルーチ
ンは自身に割当てられたロック・コード（非Ｏのユーザ
識別コードでもよい）を書込むことによりロックをオン
にセットしうる。次いで、ユーザ・ルーチンは削除ルー
チンを呼出してそれに削除ロック・ア１くレスを渡す。

削除ルーチンは削除操作を試みる前に、正しいロック・
コードが書込まれているかどうかを検査する。要素削除
が終了した後、削除ルーチンはロック・フィールドをオ
フ状態、すなわち全Ｏ値にリセットせねばならない。こ
れは任意の他のユーザ・プログラムに対し、待ち行列が
削除のために使用可能であることを表わす。

しかしながら、この規約は挿入ルーチンが削除ロック・
フィールドの状態を検査することを必要としないから、
たとえそれがオンにセットされていても、要素の同時挿
入を阻止しない。よって、たとえ削除ロックが保持され
ている間でも、待ち行列の保全性に危険を及ぼさずに、
要素挿入及び要素削除を同時に行なうことができ、その
際同時に実行される任意の数の要素挿入ルーチンによっ
て複数の新しい要素を待ち行列のアンカ一端に挿入する
ことができる。

ロックされた削除操作においては、待ち行列を探索して
要求された要素を見つけるのに任意のユーザ基！曽が使
用可能であり、そＪＬを削除ルーチンに含ませておくこ
ともできる。例えば、各々の待ち行列要素中の既知の位
置に優先順位標識が与えられ、そして削除ルーチンは探
索引数として特定の優先順位標識を指定することにより
、待ち行列においてその優先順位を含む最初の要素を探
す。

例えば、所与の優先順位を有する要素を見つけるために
、各要素に含まれるポインタを用いて要素が次々にアク
セスされ、その中の優先順位標識が指定された優先順位
標識と比較さＪＬる。指定された優先順位標識がどれか
の要素で見つかると探索は停止され、その要素が削除さ
れる。

要求された優先順位を有する要素の全部を削除するので
あれば、待ち行列の最後の要素に達するまで探索は続く
。

よって、第２図において、例えばＣＰ　Ｕ　３のブロク
ラムによる削除ロックの保持は、アンカー・ポイント要
素がＣＰＵＩまたはＣＰ　Ｕ　２によって並行して挿入
さＪしるのを妨げない。削除ロックは同じ待ち行列の削
除操作に現在１台のｃｐｕだけが携一つでいることを保
証する。

このように、第２図のＣＰ　（Ｊ　３で実行中の削除ル
ーチンは次の基本ステップを含む： （Ａ）　　待ち行列１０を使用して削除操作を行なって
いることを他のユーザに知らせるためにロック・フィー
ルドを保持する。

（１３）　　削除される要素を見つけるため待ち行列１
０を探索する。

（Ｃ）　　削除ルーチンの出力領域に見つかった要素の
アドレスを書込む。このアドレスは待ち行列中の先行要
素にあるポインタであって、削除さオしるべき要素をア
ドレス指定する。

（Ｄ）　　見つかった要素内のポインタを先行要素のポ
インタ・フィールドに移し、それによって先行要素のポ
インタは見つかった要素の次にある要素をアドレス指定
する。この動作は見つかった要素を削除するためそれに
対するポインタを待ち行列から除去し、見つかった要素
がもはや待ち行列でアドレス指定さ］しないようにする
。もしアンカー・ポイント要素が削除されるのであれば
、先行要素は存在せずそしてアンカー・ポインタは、Ｏ
８命令を用いて削除さ］しるアンカー・ポイント要素に
あるポインタに変更され、その次にある要素をアドレス
指定せねばならない。Ｏ８命令は、他のＣＰＵで同時に
遂行されている挿入操作によるアンカー・ポインタの変
化に対して待ち行列の保全性を保証するのに必要である
。

（［Ｅ）　　待ち行列１０がもはや削除操作で使用され
ておらず、従って新たな削除操作が可能であることを他
のユーザ・プロゲラｌ＼に知らせるためにロック・フィ
ールドをオフにセットする。

挿入または削除ルーチンを実行するには、最初に第２図
のアンカー・ポインタ２０の内容をアクセスして待ち行
列１０の最初のアンカー・ポイン１〜要素を見つける。

削除探索はアンカー・ポイン１〜要素にあるポインタを
もアクセスして次の要素を見つけねばならない。このス
テップは、要求された要素が見つかるまで、または待ち
行列１０の終りを示す全Ｏのポインタが見つかるまで続
けられる。ＣＰ　［Ｊ　３によって実行さＪしることが
ある特殊な削除ルーチンの例は、待ち行列から要素をＦ
ＩＦＯ方式で取出す技術を表わす次の表のシステｌｚ／
　３７０アセンブラ言語ルーチンの目的コードによって
−Ｉｊえらｉｃる。

第５図及び第６図は同様なＦ’ＩＦＯ削除ルーチンの流
れ図である。第５図のステップ６４は待ち行列に１より
も多くの要素があるかどうかを調べ、１つの要素だけが
ある場合はステップ６７でそれを待ち行列から削除する
ことを試みる。ステップ６１．６２．６３．６８及び６
９については説明は不要であろう。

第６図は待ち行列の最後の要素を探索する。次の要素が
順次見つかるごとに、ステップ７１及び７２で現要素と
その先行要素のアドレスを１＜７と１り３に各々保管す
る。１２．７にある先行要素のアドレスは、ステップ７
４で最後の要素が見つかると保持される。ぞして、ステ
ップ７６で、その要素のポインタ・フィールド（全Ｏ）
が１テアの内容によってアドレス指定さオした先行要素
に移さ４しる。

ステップ７７は、削除された要素の出力アドレスがＲ３
にあることを示す。そしてステップ７８で非ＦＩＦＯ削
除ロック・フィールドがオフにセットされる。

第５図及び第６図における重要な点は第５図のステップ
６１が終った後は、削除ルーチンによる待ち行列の探索
が保証されていることである。要素を削除するためには
、削除ロックを保持しなければならないので、この削除
ルーチンが削除ロックを保持している限り待ち行列中の
どの要素も他のＣＰＵのプログラムによって削除される
ことはない。しかしながら、前に説明したように、他の
複数のＣＰＵで実行さ九ている挿入ルーチンによって新
しい要素（アンカー・ポイン１〜要Ｆ３）を次々に挿入
していくことは可能である。新しい要素の挿入は、最初
に識別されたアンカー・ポイント要素とその待ち行列の
最後の要素の間にある要メ４の連鎖には影響しない。

第７図及び第８図は、汎用レジスタ１り６で指定された
探索引数を含む最初の要素を削除する削除ルーチンの流
れ図である。待ち行列の各要素の探索引数（ＳＡ）は、
第９図に示すように、先行要素内のポインタによって指
定されたアドレスから指標値■だけ離れたところに置か
れる。

第７図のルーチンは、要素の削除を要求するプログラム
がＲ６に探索引数をロードした後に開始さＡしる。

第７図のステップ８０において、呼出しプログラムによ
ってオンにセットされた状態でロックを受取ることによ
って、またはオフの状態で受取らばした場合にはそＪし
をオンにセラ１〜することによって、削除ロックが保持
される。削除ロックのオンの状態は他のプログラムが待
ち行列中の現アンカー・ポイント要素を含む任意の要素
を変更することに阻止する。（ロックは削除ルーチンか
ら出るどきにオフにセラ１−さｈる。）ステップ８１に
おいて、アンカー・ポインタがＲ１にロードさオしる。

ステップ８２において、ロードされたアンカー・ポイン
タ値を検査して空の待ち行列であるかどうかを調べる。

空でない場合は、ステップ８３において、Ｒ１の内容に
よってアドレス指定されたアンカー・ポイント要素内の
ポインタをＲ３にロードする。よって、Ｒ３は現アンカ
ー・ポイント要素にあるポインタを有する。ステップ８
４において、最初の要素の探索引数がＲ６の内容と比較
さｔシ、もしそれらが一致すると、ステップ８７におい
て、その削除を試みる。ステップ８８において、削除が
成功であるかどうかが決定され、成功の場合は、ステッ
プ８９において、Ｒ１が削除された要素のアドレスを含
むことが表示され、ステップ９０において、ロックがオ
フにセラ１−さ４シ、吐出プログラムへのリターンが行
なわ］しる。

しかし、ステップ８４において、最初の要素が目的とす
る’ＪＡＭ引数を有しない場合は、ステップ８５におい
て、Ｒ３にあるポインタを検査してそれが最後の要素で
あるかどうか、すなわちそのポインタ値が０であるかど
うかを決定する。待ち行列にある要素が１つだけの場合
は、この時点で探索は終了し、ステップ８６において、
ルーチンはロックをオフにセットし、呼出しプログラム
にリターンする。

しかしながら、ステップ８５において、待ち行列に２つ
以上の要素が見つかった場合には、ｒ３点を経由して第
８図に進む。

第８図は待ち行列１０の探索の継続である。これは待ち
行列の２番目の要素から開始し、（ａ）所望の探索引数
を含む要素が見つかるか、または（ｂ）そのような要素
が見つかることなく待ち行列の終りに達する場合に終了
する。

第９図は、第８図のプロセスによって探索される待ち行
列の一部を表わす。汎用レジスタＲ３は現在検査されて
いる要素のアドレスをロードされる。汎用レジスタＲ５
は現在検査されている要素にあるポインタをロードされ
る。このポインタは待ち行列１０の次の要素をアドレス
指定する。

第８図のステップ９Ｊが開始さＪしるとき、Ｒ１はアン
カー・ポイント要素のアドレスを含み、Ｒ３はアンカー
・ポイン１〜要素にあるポインタを含む。そして、ステ
ップ９１においてＲ５はアンカー・ポイント要素にある
ポインタをロードされる。

ステップ９２において、現在検査されている（すなわち
、Ｒ３によってアドレス指定された）要素の探索引数か
ら、それが要求された要素であるかどうかを検査する。

要求された要素ではない場合は、ステップ９３において
、Ｒ５にあるポインタが待ち行列の終りを示しているか
どうかを決定する。もしそ１しが待ち行列の最後の要素
ならば、ステップ９４において、出力領域に「未発見」
標識が記憶さ］し、ステップ９６において、削除ロック
がオフにセラ１〜され、呼出プログラムへのリターンが
行なわｉシる。現要素が最後の要素ではない場合、ステ
ップ９７において、Ｒ１にＲ３の内容をロードし、Ｒ３
にＲ５の内容をロードすることによって探索が続行され
る。

ステップ９２で探索引数の一致が検出されると、ステッ
プ］、　Ｏｌにおいて、現在Ｒ３にそのアドレスを有す
る要素が削除される。すなわち削除される要素内の（Ｒ
５にある）ポインタが、Ｒ１の内容によってアドレス指
定さＪしる先行要素のポインタ・フィールドに記憶され
る。次に、ステップ１０２において、Ｒ３の内容すなわ
ち削除さＪした要素のアドレスが特定の出力領域に記憶
される。そしてステップ９６において、削除ロックがオ
フにセットされ、呼出プログラムへのリターンが行なわ
れる。

第７図、第８図及び第９図の削除ルーチンは目的とする
探索引数を含む全ての要素を１回の探索オペレーション
で削除するように、容易に変更しうる。例えば、所与の
優先順次値を有する要素を単一の削除要求に応答してす
べて削除することができる。

【図面の簡単な説明】

第１図は実施例の概略を示すブロック図、第２図は３台
のＣＰＵで２つの挿入ルーチン及び１つの削除ルーチン
が同時に実行される例を示すブロック図、 第３図及び第４図は先行技術のＬＩＦ○挿入ルーチン及
びＬＩＦＯ削除ルーチンの流れ図、第５図及び第６図は
本発明に従うＦＩＦＯ削除ルーチンの流れ図、 第７図及び第８図は本発明に従う他の削除ルーチンの流
れ図、 第９図は第８図に従って処理される待ち行列の一部分を
示すブロック図である。 ＦＩＧ、４ ＦＩＧ、３ ＦＩＧ、４ ＦＩＧ　６　　　　　　　　　　ｎｃ、ｓカ＼４ＦＩＧ
、７ ｒｌＧ、８

Claims (1)

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