JPH0533410B2

JPH0533410B2 -

Info

Publication number: JPH0533410B2
Application number: JP59149850A
Authority: JP
Inventors: Erudoretsudo Hafu Rojaa
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1983-12-14
Filing date: 1984-07-20
Publication date: 1993-05-19
Also published as: JPS60128537A; EP0145889B1; DE3477972D1; US4604694A; EP0145889A3; CA1213066A; EP0145889A2

Description

【発明の詳細な説明】［産業上の利用分野］本発明は、一般に多重タスク・コンピユータ環
境において制御を確立し待行列（キユーイング）
するためのロツクワードの使用に係り、特に、ス
ピン・ロツキングを避けるタスク・ロツキングに
係る。

［従来技術］単一のプロセツサが常に単一のタスクを実行す
るコンピユータ・システムでは、コンピユータ資
源の制御にかかわる問題は存在しない。関連する
資源の種類には、大容量記憶装置、テープ装置、
印刷装置、通信チヤンネルまたは他の種類の資源
がある。資源をアクセスするタクスが１つしか存
在しない場合、このタスクは要求資源がその活動
を完了するまでは、資源ならびに中央演算処理装
置の全てにわたつて制御を維持する。

しかしながら、多重タスク・システム及びマル
チプロセツサ・システムが普及し、同時実行中の
タスクの間でともかく資源を共用して複数のタス
クの同時またはインタリーブ実行ができるように
なつた。印刷装置またはテープ装置のようなある
資源は、少なくともある期間中は要求タスクがそ
の資源に対し排他的アクセスを必要とする動作を
行なう。共通記憶領域の一部分のような他の資源
は、種々のタスク間で共用することができる。資
源アクセスの制御を解決するために、資源アクセ
スを要求したが直ちにアクセスが許可されない全
タスクのキユー（queue）即ち待ち行列がセツト
アツプされる。キユーはそのキユーにあるタスク
が資源の共用アクセスまたは排他的アクセスのど
ちらを要求しているか、そして資源は現在、共用
アクセスまたは排他的アクセスのどちらで使用さ
れているかについての情報を含んでいなければな
らない。

このようにタスクが資源アクセスを要求した
が、直ちにアクセスすることを拒否されたとき、
オペレーテイング・システムは、要求タスクをキ
ユーに挿入し、キユーを再配列する。しかしなが
ら、多重タスク環境では、２つまたはそれ以上の
タスクがほとんど同時に１つの特定の資源へのア
クセスを要求する可能性があり、そしてそれらタ
スクが並行してそのキユーの再配列にとりかかる
可能性がある。この再配列は主としてキユーの直
列化にかかわる、すなわちキユーにおける順番を
示すリストをセツトアツプする。この再配列を２
つの異なつたタスクが同時に実行しようとする場
合、それら要求タスクの１つはキユーに挿入され
ないことがあり、もつと悪い場合には、そのキユ
ーの全体の構成が破壊されることがある。

これらの問題を避けるために、資源ごとにロツ
クワードが確立される。もし、その資源のキユー
が現在再配列中であるなら、ロツクワードはその
事実を表示し、オペレーテイング・システムは次
のタスクがキユーを操作できないようにする。し
かしながら、もし、キユーが操作中ではないこと
をロツクワードが表示すれば、要求タクスは、先
ず、ロツクワードを変更して、その資源について
のキユー操作権を主張し、その要求によりキユー
再配列に着手する。

キユー操作が終了すると、ロツクワードは、キ
ユー操作が現在行なわれていないことを表示する
ステータスにリセツトされる。

２つのタスクが並行してキユーを再配列する可
能性を完全になくするには、ロツクワードの最初
の検査をいつでも単一のタスクしかこの動作を実
行できないようロツクワードの初期テスト及びセ
ツトを行なわなければならない。

多重タスク環境用に設計されたIBMシステ
ム／370には“テスト・アンド・セツト”命令
（TS命令）がある。この命令は、メモリから１つ
のワードを取出し、特定ビツトについて検査し、
１つの修正されたワードをメモリに戻すことがで
きる命令であり、その動作の間、全ての他のタス
クまたはプロセツサはメモリ中のその特定のワー
ドをアクセスすることが禁止される。記憶の取出
しとその再記憶はアトム単位（atom unitまたは
atom reference）を構成する。アトム単位はい
つたん開始すると、マルチプロセツサにおける他
のCPUによつて割込まれたり、またはインタリ
ーブされることのない動作単位である。従つて、
TS命令はロツクワードを検査し、所有権確保の
ためにロツクワードをセツトする。下記の第１表
に示された１組の命令では、LOCKWORDバイ
トの中の１ビツトが、ロツクワードの使用可能性
を表わす０であるかどうかを検査される。もし、
該ビツトが０なら、LOCKWORDは、直ちにそ
のビツトを“１”にセツトされ再書込みされる。
この結果は保持され、条件付分岐BCにより次の
ステツプで使われる。もし、該ビツトが０ではな
かつた、すなわちロツクワードが別のタスクまた
はプロセツサに占有されていたなら、ブランチ動
作が行なわれTS命令の再試行（retry）に戻る。
ロツクワードが使用可能となりそしてその所有権
が確立されると、１組の命令が実行され、キユー
はその要求タスクまたはプロセツサによつて操作
される。この操作が行なわれている間、そのタス
クがロツクワードを所有しているから、他のタス
クはキユーを操作することができない。操作が完
了すると、最後の命令はロツクワードを再書込み
し、ロツクワードが再び使用可能であることを表
示する。LOCKWORDは０にセツトされ、他の
要求タスクまたはプロセツサが再びキユーを使用
できることを表わす。

第１表（スピン・ロツク） retry TS LOCKWORD BC CCI、retry 〓〓 alter queue 〓〓 MVI LOCKWORD、０第１表の一連の動作はスピン・ロツキングと呼
ばれる。その理由は、タスクがロツクワードの所
有権を得ることができない場合、そのタスクは
（ロツクワードを）使用中タスクが最後に制御を
手放すまでスピンする、すなわちロツクワードの
所有権を得ようとし続けるからである。このよう
なスピンは無駄であり、状況によつては、多重タ
スク・コンピユータのスループツトを著しく低下
させることがある。特に深刻な影響が生じるの
は、ロツクワードを所有しているプロセツサがロ
ツクワードを手放す前に障害が生じたためにスピ
ン・ロツク状態になり、それが無限にスピンし続
ける場合である。

TS命令によつて実現されるタスク・ロツキン
グに関連する階層が第２Ａ図に示されている。
TS命令はあまりにも原始的であるので、CPUに
傷害が生じたときロツクワードを所有しているタ
スクまたはプロセツサを直接識別したり、または
１つの資源に対し２以上の所有者を与えることは
できない。従つて、TS命令は、単一の要素から
成る小さなキユーの操作を制御するのに用いら
れ、一方、その要素は他のキユーの操作及び検査
を制御する。これらの要素は、CPUに傷害が生
じたときキユーを所有しているタスクまたはプロ
セツサを識別することを可能にし、複数のタスク
が同時に１つのキユーの所有権を得る能力を与え
る。これはキユーを変更することなくそれを検査
するタスクにとつては有用なものかもしれない。

改善されたスピン・ロツクとしては、要求され
た使用可能性が得られるまでタスク（プロセツサ
ではない）を中断させるようにキユーの操作を制
御するのに使われるものがある。他者との所有権
の共有を許すような要求は“共用”要求と呼ばれ
る。他者に所有権の共有を許さない要求は“専
用”要求と呼ばれる。プロセツサを中断せずにタ
スク中断させる要求は“タスク・ロツク”とよば
れる。

第１レベルのタスク・ロツクはオペレーテイン
グ・システムその動作の続行に関して依存する資
源及びキユーに対して制御を行なうものである。
このタスク・ロツクは監視プログラムにだけ使用
可能であるので、“タスク・ロツク監視プログラ
ム”と呼ばれる。

タスク・ロツク監視プログラムの１つは、オペ
レーテイング・システムの動作続行に無関係であ
る資源及びキユーに対して制御を与えるキユーの
操作を制御するのに用いられる。これらのタス
ク・ロツクは、どのプログラムにも使用可能であ
るので、“タスク・ロツク・アプリケーシヨン”
と呼ばれる。

階層の重要性は、タスク・ロツク・アプリケー
シヨンが４レベルの動作を必要とする点にある。
レベルが複数になると、オペレーテイング・シス
テムは複雑で低速になる。

前記システム／370シリーズのプロセツサの重
要な能力は、“コンペア・アンド・スワツプ”
（CS）命令及び“コンペア・ダブル・アンド・ス
ワツプ”（CDS）命令と呼ばれる２つの命令によ
つて可能になつた。これらの２つの命令の異なる
点は、CS命令が１ワード長で動作するのに対し、
CDS命令は２ワード長で動作するという点だけ
である。１ワード命令は４バイト（32ビツト）長
であり、２ワード命令はその倍の長さである。後
述の実施例では２ワード命令が用いられるので、
ここでは、CDS命令についてだけ説明する。

CDS命令は、CDS（OLD、NEW、LOCK）の
形式の３つのオペランドで動作する。この場合、
OLD、NEW及びLOCKはそれぞれ２ワード長で
ある。CDS命令の動作を第３図に示す。もし、
LOCKとOLDの値が一致するなら、LOCKに
NEWの値が代入される。しかし、もし、LOCK
とOLDの値が一致しなければ、OLDにLOCKの
値が代入される。LOCKは不変である。状態コー
ドCCは、LOCK＝OLDについての検査結果に応
じてセツトされる。この状態コードは、検査の結
果によつて動作の流れを分岐するのに使うことが
できる。

CDS命令とTS命令はアトム単位であるという
属性を持つている。すなわち、それは単一の動作
で、メモリからの取出しとメモリへの再記憶を行
ない、従つて他のプロセツサが割込むことはでき
ない。第３図は５ステツプの動作を示している
が、CDS命令は、あたかも単一動作であるかの
ように実行される。CDS命令とTS命令は類似の
アトム特性があるので、スピン専用監視プログラ
ムにおいて、TS命令の代りにCDS命令を用いる
ことができる。事実、ほかの場合にも、スピン共
用監視プログラム及びタスク専用監視プログラム
の両者にCDS命令を使用する手段が知られてい
る。CDS命令の可能な用途が第２Ｂ図の階層に
示されている。それによれば専用タスクの場合、
タスク・ロツキング・アプリケーシヨンには３つ
の動作レベルしか必要としない。今日まで、共用
アクセス・タスク・ロツキングは、制御に対する
アクセスを制御するのにスピンまたは専用タス
ク・ロツクの監視プログラムの使用を必要として
おり、一方それら制御は共用アクセスを与え、そ
の共用アクセスと、同じキユーまたは資源の専用
アクセス要求とを調整するのに用いられる。

タスクの中断及び再開はそれ自身では中断でき
ず、タスクとして再開することはできないから、
そのキユーを制御するロツクは必然的にスピン・
ロツクでなければならない。もし、このスピン・
ロツクが、共用アクセスを与えるのに用いた制御
へのアクセスを制御するのに用いたのと同じロツ
クでないなら、資源の使用可能性またはそれの再
現がないためにタスクを中断または再開しなけれ
ばならないときに、もう１つのレベルのロツキン
グを導入することができる。これらの３つのレベ
ルは、TS命令に必要な４つのレベルよりもすぐ
れている。しかし、これらの３つのレベルは、依
然として共用タスクによるシステムの複雑さを持
つており、更に、システムを不必要に複雑にした
り、その動作速度を低下させる原因になる。

［発明が解決しようとする問題点］本発明の目的は、命令セツトとアプリケーシヨ
ン・タスク・ロツキングとの間に、最小限の動作
レベルしか持たないタスク・ロツキングを提供す
ることである。

本発明の他の目的は、他のロツクの使用をでき
るだけ避けた共用及び専用のタスク・ロツキング
を提供することである。

［問題点を解決するための手段］本発明はマルチプロセツサ・システムにおいて
１つの資源に対する共用アクセス及び専用アクセ
スの両方を制御するためのものであり、アクセス
を持つている間中断されるタスクに対して先入
り／先出し（FIFO）キユーが設けられる。その
キユーにおける各メンバー即ち制御ブロツクはそ
のメンバーが要求したアクセスの標識とそのメン
バーのすぐ前にキユーに入つたメンバーの標識を
有する。資源が共用状態にあるか専用状態にある
かを表わすロツク・フラツグと最も新しくキユー
に入つたタスクに対するロツク・ポインタとを有
するロツクワードが設定される。アクセスを要求
又は解除する際に、そのロツクワードに関する初
期推定が行なわれ、その推定に基いて１つの予測
ロツクワードが計算される。そこで、他のプロセ
ツサがそのロツクワードへアクセスし得ないアト
ム単位の動作がそのロツクワードに対して行なわ
れる。その動作において、そのロツクワードは予
測ロツクワードと比較され、そしてその推定が正
しかつた場合そのロツクワードが予測ロツクワー
ドで置換され、アクセスを要求又は解除するタス
クに対してキユーを再構成する。その推定が正し
くなかつた場合、他の予測ロツクワードを計算す
るためにそのロツクワードが使用される。次のタ
スクがアクセスを得るのに他のタスクの影響を受
ける場合、アトム単位の動作によるそのプロセス
はアトム単位動作相互間の介在する変化が生じな
くなるまで繰返される。

［実施例］本発明によるタスク・ロツキングのアーキテク
チヤを第１図のブロツク図によつて説明する。も
し、１つまたはそれ以上のタスクが資源アクセス
を要求したが、要求を受入れられなければ、その
要求はキユーに挿入される。資源上で現在実行中
のタスクがその資源に対し専用アクセスを必要と
するタスクであつたり、または既に資源が専有ま
たは共有されているときにその要求中のタスク自
身が専用アクセスを必要とすることがあるから、
最初にキユーに入れられた要求は資源アクセスを
拒絶されることがある。もし、資源が現在使用中
でないなら、要求は直ちに受入れられ、キユーは
生成されない。キユーがなく且つ１つまたはそれ
以上のタスクが、現在、資源に対する共用アクセ
スを得ている場合、共用アクセスの追加要求は直
ちに受入れられ、従つてキユーを生成する理由が
ない。本発明においてキユーはFIFOキユーのア
ーキテクチヤを有する。すなわち、最も先に出さ
れた資源アクセス要求が受入れられた後、その後
に出された要求が受入れられる。これは先に出さ
れた要求が専用アクセス要求であるなら、たとえ
資源が現在、共用アクセスで使用中であつても、
後に出された共用アクセス要求は拒絶されてキユ
ーに入れられることを意味する。資源が現在、共
用アクセスで使用中であれば、キユーの先頭、す
なわち、最も先にキユーに挿入されるタスクは、
必然的に専用アクセス要求であろう。共用アクセ
ス要求が先に出された場合、それは受入れられて
しまうので、その関連するタスクはキユーには存
在しないはずである。しかしながら、キユーに入
つている専用要求よりも先順位ではない共用アク
セス要求はキユーの中に存在することになる。キ
ユーは、マルチプロセツサ・システムのメモリ２
２の任意の場所に配列された一連のタスク遅延制
御ブロツク（TDCB）として形成される。また、
資源はメモリ２２の一部分を構成するものであつ
てもよい。資源アクセス要求が拒絶されたために
中断されている各タスクに対してTDCBが個々
にセツトアツプされる。TDCBの各々は種々の
情報を含んでいる。タスク・ポインタ、または送
られるべき制御プログラム事象制御ブロツクのよ
うな、中断されているタスクを再開するのに必要
な全ての情報がTDCBに含まれなければならな
い。また共用または専用アクセスのどちらがその
タスクに要求されたかの表示（SH／EXCL）も
TDCBに含まれなければならない。もちろん、
この表示は、１つのアクセス方式しか許されない
場合には、省略することができる。本発明の目的
のためには、各TDCBはそれのすぐ前にキユー
に挿入されたTDCBに対するポインタNCBも含
んでいる。キユーの先頭、すなわち最も先にキユ
ー挿入されたTDCBのNCBは０にセツトされる。

ロツクワードはダブルワード（LOCKFLAG：
LOCKTPTR）であり、メモリ２２の一定の場
所に記憶される。ロツクワードは資源アクセスを
持つタスクの、資源及びキユーに対するアクセス
を制御する。ロツクワードの前半の第１のワード
LOCKFLAGは現在の資源使用状況を表示する。
もし、資源が現在使用中ではなく、どのタスクも
資源アクセスを行なつていないなら、
LOCKFLAG＝０である。もし、資源が現在共用
されているなら、その資源の共用アクセスを有す
るタスクのLOCKFLAGは負数である。もし、資
源が現在専用されているなら、LOCKFLAGは正
数であり、更に、その専有タスクを指定するもの
でもよい。ロツクワードLOCKの後半の第２のワ
ードLOCKTPTRは、最も後にキユーに挿入さ
れたタスクのTDCBを指すポインタである。も
し、タスクがキユーに入つていない、すなわちキ
ユーがないなら、LOCKTPTR＝０である。

前述のように、キユーは動的なアーキテクチヤ
を有する。キユーの先順位のものが資源アクセス
を与えられるので、その場合TDCB−１はメモ
リ２２から割振りを解除される。そして、次にキ
ユーに挿入されたタスクのTDCB−２のポイン
タNCBは０にセツトされ、TDCB−２が今やキ
ユーの先頭にあることを表わす。また、ロツクワ
ードの第１のワードLOCKFLAGはリセツトさ
れ、資源の新しい状態を表わす。このように４番
目のタスクがキユーに入る場合、TDCB−４が
割振られ、ロツクワードの第２のワード
LOCKTPTRは、この新たに割振られたTDCB
−４を指すようにセツトされる。この新しい
TDCB−４のポインタNCBは、これの前にキユ
ーに入れられたタスクノTDCB、例えばTDCB
−３を指すようにセツトされる。

本発明によれば、資源アクセスを要求しまたは
解除するためにキユーを再構成することを希望す
るタスクは現在のロツクワードが何であるかを推
測し、その推測に基づいて新しい予想ロツクワー
ドNEWを形成する。CDS命令で、そのタスクは
推測されたロツクワードを現在のロツクワード
LOCKと比較させる。もし、推測が正しかつたな
ら、現在のロツクワードに新しいロツクワード
NEWの値が代入され、キユーの再配列は完了す
る。CDS命令のアトム特性によつてキユーの再
配列が完了するが、他のマルチプロセツサにおけ
る他のタスクは、ロツクワードを変更するための
アクセスを禁止される。

しかしながら、もし現在のロツクワードの推測
が間違つていたなら、LOCKの実際の値が予想ロ
ツクワードNEWを生じるのに使われる。そし
て、CDS命令が繰返され、他のタスクが差当つ
てキユーを再配列せず、ロツクワードLOCKを変
更せずにいるものと仮定して、次のCDS命令が
キユーを再配列する。

本発明の実施例の説明は、資源を１つのタスク
が専用できる場合、または複数のタスク間で共用
できる場合の４つの異なつた状況：専用アクセス
要求、共用アクセス要求、専用アクセス解除なら
びに共用アクセス解除について行なう。以下の説
明において、ダブルワードのロツクワードは２つ
のシングルワードを含み（LOCK＝
LOCKFLAG：LOCKTPTR）、ダブルワード及
びシングルワード表現はどちらも、動作に応じて
使用される。同様に、推測されたロツクワード
NEWは２つのシングルワードから成り（NEW
＝NEWFLAG：NEWTPTR）、後述のように、
取り出されたロツクワードOLDも、２つのシン
グルワードから成る（OLD＝OLDFLAG：
OLDTPTR）。第３図の流れ図において、条件コ
ードCCによる条件付き分岐は、暗黙のうちに
CDS動作に含まれるので、この動作からの出口
はLOCKとOLDの比較結果によつて２つの経路
のうちの１つを選択する。

タスクからの専用アクセス要求を処理する方法
が第４図に示される。プロセスが開始されると、
ブロツク30において、最初の推測で、資源は現在
使用中ではなく、従つてLOCKの値は（０、０）
と推測される。この値はダブルワードOLDに記
憶される。もし、これが正しければ、要求中のタ
スクはただちに資源アクセスを得ることができ、
その場合、LOCKFLAGがセツトされてこの要求
中のタスクを専有者として指定し、且つ
LOCKTPTRが０にセツトされて他のタスクが
キユーに加えられないことを表わす。もし現在、
実際にキユーが存在するなら、資源は必然的に使
用中でなければならない。ロツクワードのこれら
の新しい値はそれぞれNEWFLAGおよび
NEWTPTRにセツトされる。つぎに、ブロツク
31で、アトム単位のCDS命令が実行される。ロ
ツクワードLOCKが取出され、ダブルワード
OLDと比較される。２つの値が一致すれば、推
測は正しかつたことになり、LOCKにNEWの値
が代入され、資源の専用アクセスが得られる。こ
の場合、遅延させられた要求中のタスクがないた
め、キユーは存在せず、かつキユーを作る必要も
ない。

しかしながら、もし、OLDがLOCKに一致し
なければ資源使用可能の推測は間違つている。

よつて、現在のロツクワードの値はOLDに記
憶される。ここで、重要な点は、前述のように、
CDSはアトム単位であるので、もし、CDSの実
行開始的に推測が正しかつたならば、動作中に別
のマルチプロセツサに状況を変更されずに資源ア
クセスが得られること及びOLDに記憶されてい
るLOCKの値がCDS実行開始時の値であるという
ことである。

もし、資源の専用アクセスが現在得られないな
らば、要求の実行はブロツク32に達し、現在のタ
スクすなわち要求タスクをキユーに入れる準備が
行なわれる。TDCBが用意され、このブロツク
の内容は、現在のタスクが専用アクセス要求をし
ていることを表示するように設定される。そし
て、現在のタスクをキユー−−これは前に存在し
ていないこともある−−に入れる用意が行なわれ
る。ブロツク34において、ロツクワードの値につ
いて現在の最善の推測は、ブロツク31のCDSで
得た値OLDである。現在のタスクがキユーに挿
入される場合、LOCKFLAGの値は変らないの
で、NEWFLAGにOLDFLAGの値が代入され
る。しかしながら、更新されたLOCKRTRは現
在のタスクを指す。現在のタスクはキユーに挿入
されると、最も後にキユーに挿入されたタスクと
なるであろう。現在のタスクのTDCBのNCBは、
前のLOCKTPTRによつて指示されたTDCB−
−その時点では最も後にキユーに挿入されたタス
ク−−を指示するであろう。従つて、
NEWTPTRの値に、現像要求中のタスクの
TDCBの標識ID−−普通はアドレス−−が代入
され、現在のTDCBにある次のブロツク・ポイ
ンタNCBに、OLDTPTRの値が代入される。次
にブロツク36で、もう１つのアトム単位CDSが
実行される。もし、ロツクワードが前のままで保
持され、従つてOLD＝LOCKなら、LOCKに
NEWの値が代入され、現在のタスクハキユーに
挿入され、ポインタは再配列されたキユーに対応
して修正される。現在のタスクは、資源アクセス
を待つ間、実行を中断し、キユーに挿入される。
しかしながら、もし、最後のCDS（ブロツク31）
以後、他のタスクが、ロツクワードを変更するこ
とにより、キユーを再配列しているならば、
OLDとLOCKは一致せず、LOCKの現在の値が
OLDに代入される。

ブロツク38において、状態の変更は資源が使用
可能になることによるものか、または資源は再び
使用不可能になるキユーが再配列されているかど
うかについての判断がなされる。もしOLD＝
（０、０）なら、最善の推測な資源は現在使用可
能であるので、もはやキユーを形成しなくてもよ
いということである。現在のタスクのTDCBの
記憶空間は、もし必要なら、割振りを解除され、
手順は開始点のブロツク30に戻る。しかしなが
ら、もしOLD≠（０、０）なら、キユーは変更さ
れているが、資源は作用不可能である。そして、
ブロツク31の最初のアトム単位ではなく、後のブ
ロツク36のアトム単位のCDSから得たOLDの値
によつて、手順はブロツク34に戻る。

第５図の流れ図に示すように共用アクセス要求
の実行は、資源が現在共用アクセスされている
が、キユーは現在存在せず、資源要求タスクが共
用アクセスを得ることができる場合を含む必要が
ある場合を除き、専用アクセス要求と同様に実行
される。FIFOキユーについて前に説明したよう
に、キユーにおいて、共用アクセス要求は専用ア
クセス要求の先に飛越すことができない。また、
もし資源の所有権が共有されているなら、資源は
全ての共用アクセス要求に対応できるものと仮定
しているので、資源が共用されている場合にキユ
ーが存在することは、キユーの先頭、すなわち最
も先順位の、最も先にキユーに挿入されたタスク
は専用アクセスを要求していることを意味する。

共用アクセス要求が開始されると、ブロツク40
において、資源は使用可能でないだけではなく、
現在、他のどのタスクもその資源を共用アクセス
していないという最初の推測がなされる。LOCK
の推測値、すなわち（０、０）はOLDに代入さ
れる。もし、この推測が正しければ、共用アクセ
スは、CDSによつて首尾よく記憶されると、こ
の単一のタスクに対して確立されることになり
LOCKFLAGは“−１”にセツトされ、資源の共
用アクセスには唯一のタスクとして現在のタスク
しかないことを表わす。更に、指示すべき
TDCBがなくなるから、LOCKTPTRは０にな
る。これらの２つの値はNEWに入れられる。点
４２を経由して、アトム単位CDSのブロツク44
が実行される。ロツクワードLOCKが取出されて
OLDと比較され、もし、これらの２つのダブル
ワードが一致すれば、推測は正しく、LOCKに推
測された新しいロツクワードNEWが代入される
ので、共用アクセス要求は直ちに受入れることが
できる。そして、所有権共有のフラグがセツトさ
れ、現在のタスクによる資源の所有権共有を表示
し、異常終了から回復することができる。その結
果、共用アクセスが得られる。しかしながら、も
し、推測が間違つていたので、OLDがLOCKに
一致しないならば、ロツクワードの値はOLDに
代入される。

既にキユーにある、専用アクセスを要求する、
先順位のタスクがあるか、または、キユーはない
が、１つまたはそれ以上のタスクが既に資源アク
セスを得ていることを意味するキユーの存在によ
り、推測が失敗することがある。もし、
OLDFLAG＝＜０かつOLDTPTR＝０であれば、
キユーは存在せず、しかも資源は既に共用されて
いる。開始点はブロツク40以外のところからも、
ブロツク46を通る経路を開始できるから、ブロツ
ク46では、OLDFLAGが等しいという検査を含
めることも必要である。もし、検査結果が正し
く、従つてキユーも資源の専有権もないならば、
更新されたLOCKFLAGの値の最善の推測は、
OLDFLAGの古い値から１を減じたものになり、
もう１つのタスク、すなわち現在のタスクが資源
の共用アクセスを得ていることを表わす。従つ
て、NEWFLAGに“OLDFLAG−１”の値が代
入され、手順は点４２に戻つて、ブロツク44の
CDSを再実行することになる。

しかしながら、ブロツク46で、もし、
OLDFLAG＞０またはOLDTPTR≠０ならば、
現在のタスクはキユーに挿入されなければならな
い。TDCBが作成され、現在のタスクが共用ア
クセスを要求していることを表わす。ブロツク48
において、前に取出されたロツクワードに基づい
たキユーを再配列する準備が行なわれる。
NEWFLAGにOLDFLAGの値が代入される。
NEWTPTRにはその識別（ID）が代入され、現
在のタスクのTDCBを指示する。現在のTDCB
は、そのNCBにOLDTPTRを代入することによ
り、次に最も後にキユーに挿入されたTDCBを
指示する。

次に、CDSを用いる新しいアトム単位がブロ
ツク50で実行される。もし、ロツクワードを最後
のアトム単位以来、変更されていないなら、
OLDとLOCKは一致し、ロツクワードは、
LOCKにNEWの値を代入することにより、推測
された新しいロツクワードによつて更新され、従
つて、現在のタスクの適切にキユーに挿入され
る。そして、現在のタスクは、資源が使用可能に
なるのを待つ後中断され、その間、キユーに挿入
されている。

しかしながら、もし、アトム単位（ブロツク
50）で取出されたロツクワードが、最後のアトム
単位以来、変更されているなら、OLDとLOCK
は一致せず、OLDに現在のロツクワードLOCK
の値が代入される。この不一致は、最後のアトム
単位以来のキユーの消失、ならびに所有権共有に
より資源が使用可能であることに起因することが
ある。次に、ブロツク52で、OLDFLAG＜＝０
及びOLDTPTR＝０が検査される。これは、現
在のタスクが、多分資源の共用アクセスを直ちに
得ることを意味する。従つて、TDCBは処分さ
れ、現在のLOCKFLAGは、次のブロツクで
NEWFLAGに“OLDFLAG−１”に値を代入す
ることにより減少される。そして、手順は点４２
に戻り、CDSを用いるアトム単位がブロツク44
で再実行される。

しかしながら、ブロツク52で、もし、非０の値
がロードされているOLDTPTR、または正の値
がロードされているOLDFLAGがそれぞれ示す
ように、ロツクワードは変更されているが、キユ
ーはなお存在する、すなわち資源が専用アクセス
されているならば、手順はブロツク48に戻り、現
在のタスクをキユーに挿入しようとする試みがな
される。専用アクセス要求の場合の状況でも丁度
そうであつたように、もし、アトム単位４４また
は５０の連続実行の間に他のタスクがロツクワー
ドを変更してしないなら、タスクは適切にキユー
に挿入されるであろう。

資源の共用または専用のアクセスを有するタス
クが、その資源アクセスを解除しうる場合、アク
セス解除には単なる分離以上のものが含まれる。
アクセスが解除されるごとに、ロツクワードは適
切に更新され、いま資源アクセスを得ることにな
つている、キユーに現在あるタスクのどれかがキ
ユーから取出され、適切なアクセスが与えられる
ことを保証することにより、キユーは適切な形式
で維持される。更に、アクセスが解除されると、
それ以上の機能が実行される、すなわち、キユー
に挿入されたTDCB以来、異常終了しているタ
スクが処理される。

共用アクセスを解除する手順が第６図の流れ図
に示されている。資源の所有権が共用されている
とき、もし、キユーが存在すれば、そのキユーの
先頭の部分は専用アクセス要求である。それより
も先順位の共用アクセス要求は既に受入れられて
いる。共用アクセス解除が開始されると、ブロツ
ク60において、タスクはキユーに挿入されていな
いという最初の推測がなされる。これは
LOCKTPTR＝０によつて表示される。更に、
OLDFLAG＝−１によつて示すように、共用ア
クセスを解除するタスクは資源を現在使用中のタ
スクだけであると推測される。もし、この推測が
正しく、現在のタスクが共用アクセスを解除する
ならば、新しいロツクワードは、資源が使用され
ていないことと、キユーがないことを表示する。
従つて、NEWのシングルワードはどちらも０に
セツトされる。点６２を経て、ブロツク64におい
て、アトム単位CDSが実行される。もし、推測
が正しく、したがつてOLDとLOCKが一致すれ
ば、ロツクワードLOCKにNEWの値が代入され、
タスクのアクセス解除要求は成功している。資源
の所有権共有を表わすフラグは消去される。なせ
ならば、このタスクはもはやその資源の所有権を
共有していないからである。その後、そのタスク
は解除され、どのタスクもキユーに挿入されてい
ないからこれ以上の活動は必要ではない。

しかしながら、もし、最初の推測が間違つてい
れば、OLDとLOCKは一致せず、ロツクワード
の現在の値がOLDに入る。ブロツク66において、
資源を共用中の他のタスクがあつたか、またはキ
ユーが存在していなかつたので、推測が間違つて
いたかについての判断が、それぞれ、
OLDFLAG＜−１及びOLDTPTR＝０の条件に
よつてなされる。開始点のブロツク60以外からも
ブロツク66を通る経路が存在するから、
OLDTPTRの検査は含めておくことが必要であ
る。もし、他の共用アクセスが残ることになつて
いるなら、またもし、どのタスクもキユーに挿入
されていないならば、負のLOCKFLAGを後に増
加することにより、タスクが共用アクセスを解除
する準備がなされる、すなわち、NEWFLAGに
“OLDFLAG＋１”の値に代入され、手順は点６
２に戻る。もし、その最後の実行以来、他のタス
クが資源共用アクセスを得たり、または解除した
りせず、または資源アクセスをキユーに挿入して
いないならば、ブロツク64のアトム単位は首尾よ
く実行されるであろう。その間に、タスク共用ア
クセスとして解除タスクしか残されていない場合
には、OLDTPTR＝０の検査により、再び点６
２に手順が戻る。しかしながら、もしその間に、
資源共用またはキユー存在についての変更がなさ
れていないならば、次のブロツク64のCDSの実
行により、タスクは共用アクセスから解除される
が、資源は依然として少なくとも１つのタスクに
より共用されている。

前記以外の場合、共用アクセスの解除を求める
アクセスは、資源を共用アクセスしている最後の
タスクであり、それ以上のタスク（先頭、すなわ
ち最も先順位の、最も先にキユーに挿入された専
用要求）はキユーに挿入されている。そして、手
順はブロツク68に進み、現在、タスクが１つしか
キユーに挿入されていない−−これは必然的に専
用アクセス要求である−−がどうかについての判
断がなされる。この判断は、OLDTPTRにより
指定されたTDCBの次のブロツク・ポインタ
NCBが０であるかどうかを検査することによつ
て行なわれる。もし、検査の結果、OLDTPTR
＝０なら、手順はブロツク70に進み、
OLDTPTRによつて指示されたTDCBのタスク
識別（ID）にNEWFLAGをセツトすることによ
り、キユーを除去する準備が行なわれる。その結
果、キユーの先頭にあるTDCBのタスクは資源
の専用アクセスを取得し、NEWTPTR＝０の値
は、意図された記憶がCDSにより首尾よく完了
したとき、キユーが存在しないことを表わす。そ
して、ブロツク72で、CDSのアトム単位が実行
される。もし、OLD＝LOCKなら、LOCKに
NEWの値が代入され、手順はブロツク74に進
み、解除タスクによる所有権共有のフラグが消去
される。そして、ブロツク78でキユーにおける先
順位のTDCBは処分される。先順位のタスクは
中断状態から取除かれ、または、もし先順位のタ
スクが異常終了しているなら、先順位のタスクの
資源専用アクセスは解除される。これで、共有ア
クセス解除のための処理は完了する。

しかしながら、もし、ブロツク72において、
OLD＝LOCKでないなら、OLDにLOCKの値が
代入される。OLD＝LOCKが得られないのは、
前のアトム単位（ブロツク64）以来、別のタスク
がキユーに追加された場合だけであるので、この
時点では、少なくとも２つのタスクがキユーに挿
入されている。ブロツク76において、キユーの中
の最も先順位のものを発見するため、次の制御ブ
ロツク・ポインタNCBにより、キユーをその末
尾から先頭に向つて、NCB＝０のものが見つか
るまで探索する。キユーにおいて、次に最も先順
位のTDCBのNCBを０にセツトすることにより、
キユーの先順序の部分は除去される。次に、ブロ
ツク77において、MP（マルチプロセツサ）の一
貫した動作により、キユーの先順位のタスク識別
の値がLOCKFLAGに代入される。MPの一貫し
た動作はアトム単位であるから、別のMPの一貫
した動作−−CDSはその一例である−−によつ
て、その部分的実行を見ることはできない。
LOCKLAGの変更により、キユーの先順序の部
分が資源アクセスを与えられており、手順は、フ
ラグを消去するブロツク74を経て、ブロツク78で
TDCBを処理するとともに、先順位のタスクを
中断状態から外す。

もし、ブロツク68において、単一のタスクから
成るキユーの最初の検査で、OLDとLOCKが一
致しなければ、手順はブロツク76に進み、前述の
ように、キユーの先順位のタスクの探索が開始さ
れる。

解除タスクがいま資源を所有している唯一のタ
スクであることが知られている専用アクセス解除
は簡略化される。しかしながら、この簡略化は、
キユーの先頭の状態に関する知識の不足を埋合わ
せる以上のものがある。最も先にキユーに挿入さ
れたタスクは、第８Ａ図に示すように、専用要求
であるかも知れない。その場合、再配列により、
キユーの先頭部分は資源の専用アクセスを得るで
あろう。そうではなくて、キユーの先頭が、第８
Ｂ図のキユーに示すように、１つまたはそれ以上
の共用アクセス要求に占位されることもある。も
し、そうならば、最も先にキユーに挿入された専
用アクセス要求よりも先順位の全てのタスクは同
時に資源共用アクセスを与えられるであろう。

専用アクセス解除の実行は、第７図の流れ図に
示すように、ブロツク80で動作を開始する。資源
は専用されているから、OLDFLAGの値は必然
的にタスク識別に取替えられ、アクセスを解除し
ようとする。タスクはキユーに挿入されていない
という最初の推測が行なわれので、OLDTPTR
は、LOCKTPTRと一致することを期待して０
にセツトされる。対応するNEWの値は（０、
０）である。CDSのアトム単位がブロツク82で
実行される。もし、推測が正しく、OLD＝
LOCKであつたならば、LOCKにNEWの値が代
入されるので、ロツクワードは置換えられ、専用
アクセスは首尾よく解除される。しかしながら、
もし、OLDとLOCKが一致しなかつたならば、
ある種のキユーが存在していたことを示し、
OLDにLOCKの値が代入される。

点８４において、キユーの詳細が得られなけれ
ばならない。キユーを記述するパラメータは第８
Ａ図及び第８Ｂ図に示されている。ここでは、１
群のタスクの資源アクセスが承認される。もし、
最も先にキユーの挿入されたタスクが専用タスク
であれば、BECPTRが、その先順位の専用タス
クのTDCBを指示する。BAKTPRは、次に最も
先にキユーに挿入されたタスクを、もしあれば、
指示する。しかしながら、第８Ｂ図に示すよう
に、もし、１つまたはそれ以上の共用アクセス要
求がキユーの先頭の位置を占めるなら、
BEGPTRは、キユーの先頭における共用アクセ
ス要求のうちの、最も後にキユーに挿入された
TDCBを指示し、BAKPTRは、次に最も後にキ
ユーに挿入されたTDCB−−要求が存在する場
合は必然的に専用アクセス要求−−を指示する。
いずれの場合も、もし、キユーに他のタスクがな
ければ、BAKPTR＝０である。この情報は、第
９図の流れ図に示すブロツク86の一連のステツプ
によつて得ることができる。キユーにある
TDCBはキユーの末尾から順に質問され、
TDCBが専用アクセス要求を表わすかどうかを
決定する。現在の、または最後のTDCBが専用
アクセスを表わす場合は、ポインタBEGPTR及
びBAKPTRリセツトされる。キユーの連鎖は、
TDCBの各々にある次の制御ブロツク・ポイン
タNCBによつて追跡され、次に最も後にキユー
に挿入されたタスクを指示し、キユーの先頭に達
してNCB＝０が表示されると、ブロツク88（第７
図）において、BEGPTR及びBAKPTRの現在
値は、第８Ａ図及び第８Ｂ図に示すように、
TDCBを指示する。

第７図で、BEGPTR及びBAKPTRが識別さ
れているブロツク88において、BEGPTRによつ
て指示されたTDCBが専用アクセス要求を表わ
すかどうかについて検査が行なわれる。もし、最
も先にキユーに挿入されたタスクか、第８Ａ図に
示すように、専用アクセス要求ならば、
NEWFLAGは、BEGPTRによつて指示された
TDCBのタスクのタスク識別にセツトされる。
しかしながら、もし、BEGPRが、第８Ｂ図に示
すように、専用アクセス要求を表わさない
TDCBを指示するならば、NEWFLAGは、
BEGPTRによつて指示された、共用アクセスを
要求するTDCBの連鎖長の負値にセツトされる。
第８Ｂ図に示された例では、このNEWFLAGの
値は−３である。これらの二者選一の
NEWFLAGの値はそれぞれ、キユーが再配列さ
れた後の、専用及び共用のLOCKFLAGの値であ
る。

NEWFLAGが適切な値にセツトされた後、ブ
ロツク90において、、意図されたキユーの再配列
後にキユーが存在するかどうかについて検査が行
なわれる。もしBAKPTR＝０ならば、キユーは
存在する。この場合、BAKPTRによつて指示さ
れたTDCBの、次の制御ブロツク・ポインタ
NCBが０にセツトされ、このタスクは最も先に
キユーに挿入されたタスクになることを表わし、
LOCKFLAGは、MPの一貫した動作で
NEWFLAGにセツトされる。点９４の時点で、
キユーは再配列されており、処理すべきもので残
つているのは、中断タスクの再開、もはや使用さ
れないTDCBの処分、及び異常終了タスクによ
るアクセス解除だけである。これらはブロツク96
で処理される。

しかしながら、もしブロツク90でBAKPTR＝
０ならば、キユーはこれ以上必要ではないので、
ブロツク98に進み、NEWTPTRを０にセツト
し、キユーが意図的に不在であることを意味す
る。そして、ブロツク100に進み、CDSのアトム
単位を実行する。もし、OLD＝LOCKならば、
最後のアトム単位以来、キユーの再配列が生じて
いないことを意味する。この場合、LOCKに
NEWの値が代入され、手順は点９４を介して、
ブロツク96に進み、異常終了終結処置、TDCB
の処分及び中断タスクの両開を行なう。しかしな
がら、もし、OLD＝LOCKでないならば、OLD
にLOCKの値が代入され、手順は点８４に戻り、
再びキユーのステータスを得る。

ブロツク96に示された異常終了の終結処置のス
テツプは第１０図の流れ図に示されている。終結
処置の目的はキユーで資源アクセスを待つ間に異
常終了（ABEND）したタスクのアクセスを除去
することである。一時的に資源アクセスを与えら
れているあらゆるタスクが検査され、異常終了し
ているかどうかを決定する。もし、異常終了して
いるなら、そのTDCBはキユーに似たABENDリ
ストに加えられ、その次の制御ブロツク・ポイン
タ（NCB）は、ABENDリスト中の、次に最も
後にキユーに挿入されたTDCBを、もしあれば、
指示する。もし、タスクが異常終了していないな
らば、その実行は再開され、そのTDCBは処分
され、共用アクセスのフラグは、共用アクセスす
べきタスクごとにセツトされる。最後に、異常終
了タスクはどれもアクセスを解除され、その
TDCBは処分される。

もちろん、本明細書で説明したもの以外にも、
本発明の他の実施例が存在する。前述の動作上の
約束の多くは任意に変更することができる。例え
ば、共用アクセスをLOCKFLAGの正の値で表示
したり、専用アクセスを負の値で表示したりする
ことができる。ダブルワードLOCKにおける
LOCKFLAGはLOCKTPTRの順序は任意であ
る。実際には、もし、ワード内で個々のビツトま
たはビツト・ブロツクをセツトし、検査すること
ができるなら、シングルワードをLOCKに用いる
ことができるであろう。

以上が、アトム単位CDSを用いて資源の共用
アクセス及び専用アクセスの要求または解除を行
なう方法の説明である。これらの方法を用いるタ
スク・ロツキングの階層は第２Ｃ図に示されてい
る。アプリケーシヨン・タスク・ロツキングは、
タスク・ロツクの基本動作を形成するCDSに基
づいたタスク専用監視プログラムまたはタスク共
用監視プログラムのいずれかを使用することがで
きる。従つて、この階層は専用タスクまたは共用
タスクの３つの動作レベルしか含まいので、従来
技術のタスク・ロツキングよりも簡略化されてい
る。

［発明の効果］多重タスク・マルチプロセツサのアプリケーシ
ヨンはこのようなアプリケーシヨンの範囲内のタ
スクの間のキユー及び資源を制御するため、この
ロツキング形成を利用することができる。そのよ
うに制御された資源ごとのロツクワードの所在は
関連するタスクの各々、及び異常終了に関連する
処理にとつて、分つていなければならない。これ
は、そのようなアプリケーシヨンの階層をわずか
に２レベルの動作に減少させる。そのように制御
された資源の中に、ロツクワードのキユーが存在
することができる。従つて、そのようなアプリケ
ーシヨンは、それら自身の記号のロツク処理及び
ロツキング段層を設けることができる。その性能
は監視プログラム内の対応する働らきの利用に較
べ、大幅に改善される。更に、シングル・スレツ
ド、多重タスク・アプリケーシヨン−−それら自
身のタスク指名形式を有するタスクから成り、現
在、それら自身の記号のロツク処理及びロツキン
グ段層を有する−−は、多重タスク・マルチプロ
セツサ動作に変換可能である。これは、それら自
身の記号のロツク処理及びロツキング段層有する
ことによつて得られた性能または機能を損失する
ことなく、より大きい処理能力を生じる。

タスク実行の中断または再開のときに多分要求
される場合を除き、タスク・ロツク監視プログラ
ムはスピン・ロツクなしに完了することができ
る。もちろん、CDSによつてスピン監視プログ
ラムも可能である。前述の方法においてスピンが
存在しないことの利点は、性能向上に関連する経
費を無視できること、多重タスク・マルチプロセ
ツサ・アプリケーシヨンから直接かのロツキング
形式を利用できること、ならびにCPU障害−−
スピン・ロツクが障害CPUによつて保持されて
いる−−から回復する事が重要ではなくなること
である。

更に、前述の方法の利点は、キユーのステータ
スの最初の推測に不一致が存在しないとき、ロツ
クを得るのに要する経路長が非常に短かいことで
ある。経路長が短いことは部分的には、資源を別
個に投入することのないアクセス要求または解除
要求の最初の推測に起因するほか、CDSのアト
ム単位によつては提供されないFIFOキユーの操
作に必要なアクセス制御を与える資源のアクセス
を用いることの経済性に起因する。前述の方法の
もう１つの利点は、TDCBの自由な記憶割振り、
またはTDCBの作成等が、資源の即時使用可能
時には、アクセスを必要としない事である。

本発明のタスク・ロツキング方法には、ある不
利点が存在する。もし、資源所有タスクが異常終
了すれば、資源識別子として使われたダブルワー
ドの各々の所在を知るのにABEND処理が必要で
ある。ABEND処理は、終了するタスクに代つて
資源アクセスを解除しなければならない。このロ
ツキング形式を有する共用資源アクセスの主要な
不利点は、各タスクに関連したフラグ形式が、所
有権共有を、それが保持されているとき、表示す
るようにセツトされなければならないという要求
があるということである。

【図面の簡単な説明】

第１図は本発明において使われるような資源の
キユーを表わす図、第２Ａ図及び第２Ｂ図は先行
技術のタスク・ロツキング・アプリケーシヨンに
必要な階層を示す図、第２Ｃ図は本発明によるタ
スク・ロツキング・アプリケーシヨンに関連した
階層を示す図、第３図はアトム命令CDSの動作
の流れ図、第４図は資源の専用アクセス要求を処
理する流れ図、第５図は資源の所用アクセス要求
を処理する流れ図、第６図は資源の共有権共有の
解除を処理する流れ図、第７図は資源の所有権専
有の解除を処理する流れ図、第８Ａ図及び第８Ｂ
図は第７図及び第９図を理解するのに有用な、キ
ユーを示す図、第９図は第７図のキユーの状態を
識別するステツプの流れ図、第１０図は第７図の
異常終了の終結処置のステツプの流れ図である。

Claims

【特許請求の範囲】１複数の資源のそれぞれに対するアクセス制御
を伴う多重プログラミング・システムにおいて、前記資源ごとの該資源へのアクセスを持つ要求
に関連する制御ブロツクの先入れ先出しキユーを
提供する手段と、各資源に関連して設けられ、該資源のアクセス
状態として、(イ)共用状態、(ロ)専用状態、または(ハ)
空状態を示すロツクフラツグおよび最も遅く前記
キユーに入れられた制御ブロツクを示すロツクポ
インタを含むロツクフイールドを提供する手段
と、前記制御ブロツクに備えられ、該制御ブロツク
の前にキユーに入つた制御ブロツクを示すポイン
タと、前記制御ブロツクに備えられ、該制御ブロツク
に関連する前記要求が共用要求であるか専用要求
であるかを示す標識とを有し、資源の共用を求める要求に応答して、前記ロツ
クフイールドについて、前記ロツクフラツグが空
状態を示し、かつ前記ロツクポインタが前記キユ
ーが空であることを示しているかどうかをアトム
単位動作でテストし、そうであるときは、即時ア
クセスを許可し、このテストで前記キユーに前記
制御ブロツクがあることが示されるか、または専
用状態が示されたときには、次のテストで前記ロ
ツクフイールドが前のテストで得られた値と相違
しなければ、アトム単位動作で該要求に関連する
制御ブロツクを前記キユーに入れるようにした多
重プログラミング・システム。２前記キユーに入れる試みで見つけられる前記
ロツクフラツグが前記資源の専用状態を示すか、
または該試みで見つけられる前記ロツクポインタ
ーが前記キユーの存在を示す限り、前記キユー入
れの試みを維続するようにした特許請求の範囲第
１項記載の多重プログラミング・システム。