JPH0247772B2 - Machigyoretsuseigyohoshiki - Google Patents

Description

【発明の詳細な説明】 本発明は、待ち行列制御方式に関し、詳しくは
待ち行列を形成するために必要なデータ・エリア
を最小にして、主メモリの容量増大を防止するこ
とが可能な制御方式に関するものである。

コンピユータ・システムには、種々の共有リソ
ース（資源）、例えば中央処理装置（CPU）、チ
ヤネル、メモリ、回線等が存在する。そして、コ
ンピユータ・システムの使用効率を向上するため
に多重プログラミングが導入された結果、システ
ム内では多数のプロセスが存在することになり、
使用可能な共有リソースの制限から、これらリソ
ースの奪い合いによる待ち行列が生じている。

一方、コンピユータ・システムのメモリには、
共有リソースの管理、ジヨブや制御の流れのスケ
ジユーリング、プログラムの結合の管理、コマン
ド、ジヨブ制御言語等ユーザからジヨブ処理の指
令を受けたり、ジヨブの出力を出す等のユーザと
のインタフエース、ユーザのプログラムからサブ
ルーチン的に利用されるフアイルのアクセス等に
関する機能をもつオペレーテイング・システムが
格納されている。

ところで、待ち行列を形成する場合には、従来
より待ち行列に登録される可能性のあるすべての
制御テーブルに、待ち行列を形成するために必要
なポインタ・エリアを設けている。しかし、それ
らの制御テーブルのすべてが同時に待ち行列につ
ながれることはなく、また待ち行列に接続された
とき、通常、その数は少ないため、多くの制御テ
ーブルのポインタ・エリアが無駄になつている。
しかも、制御テーブルの数が増加すればするほ
ど、無駄なポインタ・エリアが増加するので、オ
ペレーテイング・システム（以下OSと記す）全
体が占有するメモリ容量は膨大となり、それにと
もないユーザ領域が圧迫されるという問題があ
る。

コンピユータ・システムにおいて発生する待ち
行列の代表的なものは、ユーザ・プログラム（以
下タスクと呼ぶ）の実行待ち行列や、タスク間で
の共有リソース占有待ち行列である。

第１図は、従来の待ち行列を形成するために必
要なOSの制御テーブルの説明図である。

OSは、各タスクごとにタスクの状態を管理す
るテーブル１００，１２０，…１３０を設け、そ
れらをタスク番号順に並べ、その先頭アドレスを
ポインタ１４０により管理する。また、OSは、
実行待ち行列を管理するために、タスクの優先レ
ベルに対応した実行待ち行列用キユーヘツダ１５
０，１５５および各種共有リソースに対応した共
有リソース占有待ち行列用キユーヘツダ１６０，
１７０を、それぞれ設ける。

上記の各種待ち行列は、該当する待ち行列用キ
ユーヘツダにタスク管理テーブル１００，１１
０，１２０，１３０等を接続することによつて管
理されるのであるが、そのため各タスク管理テー
ブル１００，１１０，１２０，１３０にはタスク
の状態を管理する情報１１０の他に、実行待ち行
列用の前向きポインタ１０２、後向きポインタ１
０４、および共有リソース占有待ち行列用の前向
きポインタ１０６、後向きポインタ１０８を設け
ている。前向きと後向きの両ポインタを設ける必
要性は、リング状に結合されるアドレスのうちの
途中の一部を取り外すとき、あるいは順次発生す
るタスクを待ち行列の最後に結合させるときの制
御を高速に行うためである。

また、各キユーヘツダ１５０，１５５，１６
０，１７０にも、それぞれ前向きポインタ１５
２，１６２と後向きポインタ１５４，１６４を設
ける。これらの前向きポインタと後向きポインタ
の大きさは、それぞれ４バイトである。

第２図ａ，ｂは、それぞれ従来の待ち行列管理
状態を示す説明図である。

実行要求が出されたタスクがあると、OSはそ
のタスクの優先レベルに対応した実行待ち行列用
キユーヘツダ１５０により管理される実行待ち行
列の末尾にそのタスクの管理テーブルを挿入し、
そのタスクの実行の順番を待機させる。

いま、第２図ａに示すように、実行待ち行列用
キユーヘツダ１５０にタスク管理テーブル１０
０，１２０が接続されており、タスク管理テーブ
ル１３０をテーブル１２０の次に挿入する場合に
は、OSは、タスク管理テーブル１２０の前向き
ポインタ１２２にテーブル１３０の先頭アドレス
を設定し、テーブル１３０の前向きポインタ１３
２に実行待ち行列用キユーヘツダ１５０の先頭ア
ドレスを設定し、テーブル１３０の後向きポイン
タ１３４にテーブル１２０の先頭アドレスを設定
し、実行待ち行列用キユーヘツダ１５０の後向き
ポインタ１５４にテーブル１３０の先頭アドレス
を設定することによつて、タスク管理テーブル１
３０をキユーヘツダ１５０に管理される実行待ち
行列に登録する。実行の順番がきて、処理が終了
すると、そのタスクの管理テーブルは、OSによ
り実行待ち行列から取り外される。

一方、実行中に共有リソースの占有待ちを生じ
たタスクがあると、OSはその共有リソースに対
応する占有待ちキユーヘツダ１６０によつて管理
される共有リソース占有待ち行列の末尾にそのタ
スクの管理テーブルを挿入し、この共有リソース
の占有待ちが解除されるまでそのタスクの実行を
中断させる。

この場合、第２図ｂに示すように、すでに実行
待ち行列用キユーヘツダ１５５にタスク管理テー
ブル１８０，１９０が接続されているときには、
タスクの管理テーブル１９０は実行待ち行列から
取り外されて新たに共有リソース占有待ち行列用
キユーヘツダ１６０に接続されるのではなく、実
行要求が出された時点での先着順序を維持するた
めに、実行待ち行列に接続したまま、さらに別の
共有リソース占有待ち行列にも接続する方法を用
いている。すなわち、タスク管理テーブル１９０
に対応するタスクを実行中に、キユーヘツダ１６
０に対応する共有リソースの占有待ちが生じた場
合、仮に、キユーヘツダ１６０にはどのテーブル
も接続されていないものとすると、OSはキユー
ヘツダ１６０の前向きポインタ１６２および後向
きポインタ１６４にテーブル１９０の先頭アドレ
スを設定し、テーブル１９０の前向きポインタ１
９６および後向きポインタ１９８にキユーヘツダ
１６０の先頭アドレスを設定することにより、テ
ーブル１９０をキユーヘツダ１６０にて管理され
る共有リソース占有待ち行列に登録する。そし
て、共有リソース占有待ちが解除されると、その
タスクの管理テーブル１９０は、OSにより占有
待ち行列から取り外される。

このように、従来は、タスク管理テーブル１０
０に対して、待ち行列を形成するための前向きポ
インタ１０２，１０６、後向きポインタ１０４，
１０８を設ける必要があり、管理テーブル１ケー
スごとに16バイトがポインタとして使用されてい
る。例えば、登録されたタスク数を256個とする
と、管理テーブルのポインタに要する全体のメモ
リ容量は4096バイト（＝16×256）であり、また
同時に実行待ち行列に接続されるタスク数を多め
に予測して32個とすると、そのときに有効に利用
しているポインタ・エリアは512バイト（＝16×
32）しかないことになり、その他の3584バイトは
無駄になつている。

本発明の目的は、このような従来の欠点を除去
するため、待ち行列を形成するために必要な制御
テーブルの容量を最小限にして、無駄なエリアを
なくすことができ、しかも従来と同一のインタフ
エースでユーザにより待ち行列の操作が可能な待
ち行列制御方式を提供することにある。

上記目的を達成するため、本発明の待ち行列制
御方式は、待ち行列の形成に必要なポインタを、
タスクの状態を管理する情報を含む第１の制御テ
ーブルから分離して該ポインタのみからなる第２
の制御テーブルを構成し、該第２の制御テーブル
上に上記第１の制御テーブルの先頭アドレスを設
定して、待ち行列に登録した後、処理が終了する
と、上記第２の制御テーブル上の設定を取り消し
て上記待ち行列から切り離すことを特徴としてい
る。

以下、本発明の実施例を、図面により説明す
る。

第３図は、本発明の実施例を示す待ち行列制御
システムの概略ブロツク図である。

主メモリ３００上のOSを格納するエリアには、
タスク管理テーブル４００，４２０…がタスク番
号順に配置され、テーブル４００の先頭アドレス
をもつポインタ４４０、タスクの実行待ち行列用
キユーヘツダ４５０、各種共有リソース占有待ち
行列用キユーヘツダ４６０が設けられる他に、本
発明により設定された行列ポインタ・テーブル
（以下キユーブロツクと記す）４９０，４９５お
よびそれらの空きを管理するキユーヘツダ４８０
等の制御テーブル類が設けられる。その他、プロ
グラム３１０，３１５等も格納されている。

共有リソースである処理装置３７０には、演算
回路３４０、制御回路３５０、制御メモリ３６０
およびメモリ・アドレス・レジスタ３３０、メモ
リ・データ・レジスタ３３５等を含むインタフエ
ース回路が設けられ、その動作は従来と同じであ
る。すなわち、制御回路３５０の指令により次に
実行すべき命令のアドレスが演算回路３４０を経
由してメモリ・アドレス・レジスタ３３０にセツ
トされ、主メモリ３００にアクセス要求が出され
ることにより、主メモリ３００から次に実行すべ
き命令が読み出されて、メモリ・データ・レジス
タ３３５にセツトされる。メモリ・データ・レジ
スタ３３５にセツトされた命令は直ちに制御回路
３５０に送られ、そこで解読されて制御メモリ３
６０に格納されているマイクロプログラムのう
ち、その命令を実行するマイクロプログラム７０
０，９００，１１００，１１５０，１４００，１
４５０に制御が渡される。制御回路３５０は、マ
イクロプログラムを逐次、制御メモリ３６０から
読み出して解読し、それに基づいて演算回路３４
０やメモリ・インタフエースやメモリ制御回路３
２０を制御する。

本発明により新設された待ち行列操作命令は、
マイクロプログラム７００，９００，１１００，
１１５０，１４００，１４５０である。

第４図は、本発明の実施例を示す制御テーブル
の構造図である。

タスク管理テーブル４００，４２０，…４３０
は、従来と同じようにタスク番号順に配置され、
その先頭アドレスがポインタ４４０によつて管理
される。タスク管理テーブル１ケースの構成は、
従来のタスク管理テーブルから待ち行列用のポイ
ンタ群（16バイト）を取り除いた残りのタスク状
態情報エリア４０４と、待ち行列に接続するとき
にキユーブロツク４９０，４９５…を対応づける
ためのポインタ４０２（４バイト）を設けたもの
である。

キユーブロツク４９０，４９５は、待ち行列を
形成するときに必要なポインタ情報を持つテーブ
ルであり、１ケースの構成は第１キユー（実行待
ち行列）用の前向きポインタ４９２、後向きポイ
ンタ４９４、第２キユー（共有リソース占有待ち
行列）用の前向きポインタ４９６、後向きポイン
タ４９８、および対応づけられたテーブル用のポ
インタ４９９からなり、全部で20バイト（４バイ
ト×５）である。これらのキユーブロツク４９
０，４９５は、初期状態時、つまり不使用時には
空きのキユーブロツク・リストとして管理され、
この管理のために空き管理キユーヘツダ４８０が
新たに設けられる。空き管理キユーヘツダ４８０
は、空きキユーブロツクを接続するための前向き
ポインタ４８２、後向きポインタ４８４を持つ。
実行待ち行列用キユーヘツダ４５０，４５５は従
来と同じように双方向ポインタをもつタスクの優
先レベル対応の実行待ち行列キユーヘツダであ
り、共有リソース占有待ち行列用キユーヘツダ４
６０，４７０も、従来と同じように双方向ポイン
タをもつ各共有リソース対応の占有待ち行列キユ
ーヘツダである。

第５図ａ，ｂは、本発明の実施例を示す待ち行
列の形成方法の説明図である。

第５図ａでは、タスク管理テーブル５５０で示
されるタスクが、実行待ち行列用キユーヘツダ４
５０により管理される実行待ち行列に接続されて
いる場合について説明する。

タスク管理テーブル５５０で示されるタスクに
実行要求が出されると、OSは空き管理キユーヘ
ツダ４８０により管理されている空きキユーブロ
ツク行列の先頭から１つのキユーブロツク５００
を取り外し、タスク管理テーブル５５０のポイン
タ５５２にキユーブロツク５００の先頭アドレス
を設定し、一方そのキユーブロツク５００のテー
ブル用ポインタ５０９にテーブル５５０の先頭ア
ドレスを設定することにより、そのテーブル５５
０とキユーブロツク５００との対応づけを行う。
さらに、OSは、そのキユーブロツク５００に関
して従来と同じように実行待ち行列への挿入操作
を行う。すなわち、キユーブロツク５００の前向
きポインタ５０２は次に並んでいるキユーブロツ
ク５１０の先頭アドレスを保持し、後向きポイン
タ５０４はその前に並んでいる実行待ち行列用キ
ユーヘツダ４５０の先頭アドレスを保持するよう
に情報を設定する。なお、実行待ち行列用キユー
ヘツダ４５０の次に他のキユーブロツクが接続さ
れているときには、前に並んでいるキユーブロツ
クの先頭アドレスを保持することになる。

次に、第５図ｂにおいては、タスク管理テーブ
ル５９０で表されるタスクの実行中に、共有リソ
ース占有待ち行列用キユーヘツダ４６０に対応す
る共有リソースの占有待ちが生じたものとする。
この場合には、テーブル５９０に対応するキユー
ブロツク５４０をキユーヘツダ４６０により管理
される占有待ち行列に挿入する操作を行うが、キ
ユーヘツダ４６０およびキユーブロツク５４０の
ポインタ値は、キユーヘツダ４６０の先頭アドレ
スあるいはキユーブロツク５４０の第２キユー用
前向きポインタ５４６のアドレスとする。すなわ
ち、OSは、キユーヘツダ４６０の後向きポイン
タ４６４にはキユーブロツク５４０の前向きポイ
ンタ５４６のアドレスを設定し、キユーブロツク
５４０の前向きポインタ５４６、後向きポインタ
５４８にはキユーヘツダ４６０の先頭アドレスを
設定する。

第６図は、本発明の実施例を示す待ち行列操作
命令の説明図である。

第６図において、大文字（英字）は各命令のニ
モニツクを示し、子文字（英字）はオペランドを
示す。topqhdはキユーヘツダの先頭アドレスを、
toptblはテーブルの先頭アドレスを、regはレジ
スタ番号を、またeaddrは異常時のジヤンプ先ア
ドレスを、それぞれ示す。

(a) GTFQT命令は、topqhdで示す空き管理キ
ユーヘツダEQBHによつて管理されている空
きのキユーブロツク・リストの先頭からキユー
ブロツクQBを１つ外し、toptblで示すタスク
管理テーブルTCBとそのキユーブロツクQBと
の対応づけを行い、そのキユーブロツクQBの
先頭アドレスをregで示すレジスタに設定する
機能を果す。このとき、topqhdで示す空き管
理キユーヘツダEQBHに空きのキユーブロツ
クQBが全くない場合には、何もせずに、
eaddrで示される番地にジヤンプする。

(b) FREQT命令は、toptblで示すタスク管理テ
ーブルTCBに対応づけられているキユーバツ
フアQBとそのタスク管理テーブルTCBとの対
応づけを解消し、そのキユーブロツクQBを
topqhdで示す空き管理キユーヘツダEQBHに
より管理されている空きキユーブロツク・リス
トの先頭に挿入する機能を果す。

(c) INQLT命令は、topqhdで示すキユーヘツダ
EQBHにより管理されている待ち行列の末尾
に、toptblで示すタスク管理テーブル（実際に
はこのタスク管理テーブルTCBに対応するキ
ユーブロツクQB）をその待ち行列が第１キユ
ーになるように挿入する機能を果す。

(d) INQLS命令は、topqhdで示すキユーヘツダ
EQBHにより管理されている待ち行列の末尾
に、toptblで示すテーブル（実際には、このテ
ーブルTCBに対応するキユーブロツク（QB））
をその待ち行列が第２キユーになるように挿入
する機能を果す。

(e) RMVQT命令は、toptblで示すテーブル（実
際には、このテーブルTCBに対応するキユー
ブロツクQB）を第１キユーから取り外す機能
を果す。

(f) RMVQS命令は、toptblで示すテーブル（実
際には、このテーブルに対応するキユーブロツ
ク）を第２キユーから取り外す機能を果す。

第７図は、第６図に示すGTFQT命令の処理手
順のフローチヤート、第８図は同じくGTFQT命
令のデータ操作説明図である。

ブロツク７０５では、第８図ａに示すように、
topqhd６０２で示される空き管理キユーヘツダ
４８０の前向きポインタ４８２の内容を取り出
す。次に、ブロツク７１０では、前向きポインタ
４８２の内容とtopqhd６０２（すなわち、管理
キユーヘツダ４８０の先頭アドレス）を比較し、
空きキユーブロツクがないか否かをチエツクす
る。

すなわち、前向きポインタ４８２がキユーヘツ
ダ自身を指示している場合には、何も接続されて
いないことになるので、ポインタ４８２の内容を
調べる。比較結果が等しいときには空きキユーブ
ロツクはないので、ブロツク７３５に進みユーザ
の処理にまかせる。つまり、eaddrに分岐するよ
うに、プログラム・カウンタにeaddrを設定す
る。eaddr番地の命令へ移る。

空きキユーブロツクがあれば、ブロツク７１５
で、前向きポインタ４８２の内容（すなわち、空
きキユーブロツクの先頭アドレス）をreg６０６
で示されるレジスタ８００に設定する（第８図の
点線矢印）。

次に、ブロツク７２０では、以下の操作を行う
ことにより空きキユーブロツク・リストの先頭の
キユーブロツク８１０をリストから取り外す。す
なわち、キユーブロツク８１０の前向きポインタ
８１２の内容を空き管理キユーヘツダ４８０の前
向きポインタ４８２に設定し（第８図の点線矢
印）、キユーブロツク８１０の後向きポインタ８
１４の内容を前向きポインタ８１２の内容によつ
て示されるキユーブロツク８２０の後向きポイン
タ８２４（あるいは管理キユーヘツド４８０の後
向きポインタ４８４）に設定する（第８図の点線
矢印）。

次に、ブロツク７２５では、以下の操作により
キユーブロツク８１０とtoptbl６０４で示される
テーブル８３０との対応づけを行う（第８図ｂ参
照）。すなわち、キユーブロツク８１０のテーブ
ル用ポインタ８１９にtoptbl６０４（すなわち、
テーブル８３０の先頭アドレス）を設定し、テー
ブル８３０のポインタ８３２にブロツク７１５に
おいてレジスタ８００に設定したキユーブロツク
８１０の先頭アドレスを設定する（第８図の点線
矢印）。ブロツク７２５の処理を終了すると、本
命令は終了するので、次の番地の命令実行に移る
（７３０）。

第８図ａの状態から、第８図ｂの状態に移るこ
とにより、空きキユーブロツクの１つ８１０が
toptblで示すテーブル８３０と対応づけられたこ
とになる。

第９図は、第６図におけるFREQT命令の処理
手順を示すフローチヤートであり、第１０図は同
じくそのデータ操作図である。

ブロツク９０５では、toptbl６１４で示される
テーブル１０３０のポインタ１０３２の内容（そ
のテーブルに対応するキユーブロツク１０１０の
先頭アドレス）を取り出す。次に、ブロツク９１
０では、以下の操作により、キユーブロツク１０
１０をtopqhd６１２で示され、かつキユーヘツ
ダ４８０で管理される空きキユーブロツク・リス
トの先頭に挿入する。すなわち、キユーヘツダ４
８０の前向きポインタ４８２の内容をキユーブロ
ツク１０１０の前向きポインタ１０１２に設定
し、topqhd６１２をキユーブロツク１０１０の
後向きポインタ１０１４に設定し、またキユーヘ
ツダ４８０の前向きポインタ４８２の内容で示さ
れるキユーブロツク１０２０の後向きポインタ１
０２４（あるいはキユーヘツダ４８０の後向きポ
インタ４８４）にテーブル１０３０のポインタ１
０３２の内容を設定する。

次に、ブロツク９１５と９２０では、以下の操
作によりテーブル１０３０とキユーブロツク１０
１０との対応づけを解消する。すなわち、テーブ
ル１０３０のポインタ１０３２とキユーブロツク
１０１０のポインタ１０１９にそれぞれオールゼ
ロ１０００を設定する。ブロツク９２０が終了し
たとき、本命令は終了するので、次の番地の命令
を実行する（９２５）。

第１１図Ａは、第６図におけるINQLT命令の
処理手順を示すフローチヤートであり、第１２図
は同じくそのデータ操作図である。

ブロツク１１０５では、toptbl６２４で示され
るテーブル１２３０のポインタ１２３２の内容を
取り出す。次に、ブロツク１１１０では、
topqhd６２２で示されるタスク実行待ち行列キ
ユーヘツダ４５０の後向きポインタ４５４の内容
を取り出す。

次に、ブロツク１１１５では、以下の内容によ
りテーブル１２３０のポインタ１２３２で示され
るキユーブロツク１２１０を、待ち行列キユーヘ
ツダ４５０で管理される待ち行列の第１キユーと
して、その待ち行列の末尾に挿入する。すなわ
ち、キユーヘツダ４５０の後向きポインタ４５４
の内容で示されるキユーブロツク１２００の前向
きポインタ１２０２（あるいは待ち行列キユーヘ
ツダ４５０の前向きポインタ４５２）および待ち
行列キユーヘツダ４５０の後向きポインタ４５４
に設定する。ブロツク１１１５を終了することに
より、本命令を終了し、次の命令の実行に移る
（１１２０）。

第１１図Ｂは、第６図におけるINQLS命令の
処理手順を示すフローチヤートであり、第１３図
は同じくそのデータ操作図である。

INQLT命令と本命令（INQLS）との相違点
は、前者が第１キユーを対象とするのに対し、後
者は第２キユーを対象とするところにある。すな
わち、第１１図Ｂのブロツク１１５５，１１６０
は、第１１図Ａのブロツク１１０５，１１１０と
同一内容であるので、相違点であるブロツク１１
６５について説明する。

ブロツク１１６５では、以下の操作によりテー
ブル１３３０のポインタ１３３２で示されるキユ
ーブロツク１３１０を共有リソース占有待ち行列
キユーヘツダ４６０で管理される待ち行列を、第
２キユーとしてその待ち行列の末尾に挿入する。
すなわち、待ち行列キユーヘツダ４６０の後向き
ポインタ４６４の内容で示されるキユーブロツク
１３００の前向きポインタ１３０６（あるいは待
ち行列キユーヘツダ４６０の前向きポインタ４６
２）の内容をキユーブロツク１３１０の前向きポ
インタ１３１６に設定し、待ち行列キユーヘツダ
４６０の後向きポインタ４６４の内容をキユーブ
ロツク１３１０の後向きポインタ１３１８に設定
し、テーブル１３３０のポインタ１３３２の内容
に８（バイト）１３４０を加えた値（すなわち、
キユーブロツク１３１０の前向きポインタ１３１
６のアドレス）をキユーブロツク１３００の前向
きポインタ１３０６（あるいは待ち行列キユーヘ
ツダ４６０の前向きポインタ４６２）および待ち
行列キユーヘツダ４６０の後向きポインタ４６４
に設定する。

第１４図Ａは、第６図におけるRMVQT命令
の処理手順を示すフローチヤートであり、第１５
図は同じくそのデータ操作図である。

ブロツク１４０５では、toptbl６４２で示され
るテーブル１５４０のポインタ１５４２の内容を
取り出す。次に、ブロツク１４１０では、以下の
操作によりテーブル１５４０のポインタ１５４２
の内容で示されるキユーブロツク１５１０をそれ
が接続されている第１キユーから取り外す。キユ
ーブロツク１５１０の前向きポインタ１５１２の
内容を、後向きポインタ１５１４の内容で示され
るキユーブロツク１５００の前向きポインタ１５
０２（あるいは実行待ち行列キユーヘツダ４５０
の前向きポインタ４５２）に設定し、キユーブロ
ツク１５１０の後向きポインタ１５１４の内容を
前向きポインタ１５１２の内容で示されるキユー
ブロツク１５２０の後向きポインタ１５２４（あ
るいは待ち行列キユーヘツダ４５０の後向きポイ
ンタ４５４）に設定する。

ブロツク１４１０の処理を終えると、本命令は
終了して、次の命令の実行に移る（１４１５）。

第１４図Ｂは、第６図におけるRMVQS命令の
処理手順を示すフローチヤートであり、第１６図
は同じくそのデータ操作図である。

先に述べたRMVQT命令と本命令との相違は、
前者が第１キユーに対するものであるのに対し
て、後者は第２キユーに対するものである点にあ
る。したがつて、第１４図Ｂのブロツク１４５５
は第１４図Ａのブロツク１４０５と同一であり、
ブロツク１４６０のみが異なるので、異なる動作
についてのみ説明する。

toptbl６５２で示されるテーブル１６４０のポ
インタ１６４２の内容により示されるキユーブロ
ツク１６１０の前向きポインタ１６１６の内容
を、後向きポインタ１６１８の内容で示されるキ
ユーブロツク１６００の前向きポインタ１６０６
（あるいは共有リソース占有待ち行列キユーヘツ
ダ４６０の前向きポインタ４６２）に設定し、キ
ユーブロツク１６１０の後向きポインタ１６１８
の内容を前向きポインタ１６１６の内容で示され
るキユーブロツク１６２０の後向きポインタ１６
２８（あるいはキユーヘツダ４６０の後向きポイ
ンタ４６４）に設定する。

以上、第６図に示す各命令について、動作を説
明したが、これらの説明から明らかなように、タ
スク管理テーブルTCBから待ち行列用のポイン
タを切り離してキユーブロツクQBとして独立さ
せ、かつキユーブロツクQBを必要最小限のケー
ス数のみ用意し、必要に応じてタスク管理テーブ
ルTCBとキユーブロツクQBを対応づけてテーブ
ルTCBの待ち行列を形成するテーブル構造にす
るので、ポインタ・エリアの無駄なメモリ容量を
削減することができる。例えば、タスク総数を
256個、キユーブロツクQBのケース数（同時に
実行可能なタスク数）を64個、同時実行中のタス
クを多めに見て32個と仮定すると、管理テーブル
TCBのポインタおよびキユーブロツク全体の容
量は2304バイト（＝４バイト×５×64＋４バイト
×256）であり、このうち有効に利用されている
エリアは768（＝４バイト×５×32＋４バイト×
32）になる。すなわち、従来は、待ち行列管理の
ために4096バイト（＝４バイト×４×256）を要
していたのに対して、2304バイトに減少すること
ができ、かつそれらのエリアの利用度を向上でき
る。

次に、第６図に示すGTEQT、FREQT、
INQLT、INQLS、RMVQT、RMVQS等の命令
を設けることによつて、ユーザはキユーブロツク
の構造やキユーブロツク間の結合を意識すること
なく、従来と同じようにタスク管理テーブル
TCBの先頭アドレスを意識するのみで、タスク
の待ち行列制御を行うことができ、かつタスク管
理テーブルTCBとキユーブロツクQBにの対応づ
けはマイクロプログラムにより実現されるので、
それらに伴うオーバーヘツドは無視できるほど少
なくすることができる。

以上説明したように、本発明によれば、待ち行
列に必要なポインタを一般のテーブルから分離し
て独立した制御テーブルを形成し、かつその制御
テーブルのケース数を必要最少限だけ用意し、必
要に応じて一般のテーブルと対応づけ、待ち行列
を形成するテーブル構造とするので、待ち行列ポ
インタによる制御テーブル容量の増大および無駄
エリアの増大を減少することができる。また、ユ
ーザは上記のようなテーブル構造を全く意識せ
ず、本発明による待ち行列操作の命令を発行する
のみで、従来と同じインタフエースで待ち行列を
操作することができ、しかも一般テーブルとの対
応づけに伴うオーバヘツドも無視できるほど少な
くできる。

【図面の簡単な説明】

第１図は従来の待ち行列に関する制御テーブル
の構造図、第２図は従来の待ち行列管理状態を示
す説明図、第３図は本発明の実施例を示す待ち行
列制御システムの概略ブロツク図、第４図は本発
明の実施例を示す制御テーブルの構造図、第５図
は本発明の実施例を示す待ち行列の形成方法の説
明図、第６図は本発明の実施例を示す待ち行列操
作命令の説明図、第７図、第９図、第１１図およ
び第１４図はいずれも第６図に示す制御命令の処
理手順のフローチヤート、第８図、第１０図、第
１２図、第１３図、第１５図および第１６図はい
ずれも第６図に示す制御命令に伴うデータ操作の
説明図である。 ４００，４２０，４３０，５５０，５６０，５
７０，５８０，５９０，８３０，１０３０，１２
２０，１２３０，１３２０，１３３０，１５３
０，１５４０，１５５０，１６３０，１６４０，
１６５０：タスク管理テーブル（TCB）、１４
０，４４０：先頭アドレス・ポインタ、１５０，
１５５，４５０，４５５：実行待ち行列用キユー
ヘツダ、１６０，１７０，４６０，４７０：共有
リソース占有待ち行列用キユーヘツダ、４８０：
空き管理キユーヘツダ、４９０，４９５，５０
９，５１０，５２０，５３０，５４０，８１０，
８２０，１０１０，１０２０，１２００，１２１
０，１３００，１３１０，１５００，１５１０，
１５２０，１６００，１６１０，１６２０：キユ
ーブロツク、３７０：処理装置、３００：主メモ
リ、３３０：メモリ・アドレス・レジスタ、３３
５：メモリ・データ・レジスタ、３４０：演算回
路、３５０：制御回路、３６０：制御メモリ、７
００，９００，１１００，１１５０，１４００，
１４５０：待ち行列操作用マイクロプログラム。

Claims (1)

1. 【特許請求の範囲】 １ 主メモリと中央処理装置と周辺装置よりなる
   コンピユータ・システムにおいて、タスクあるい
   は共有リソース占有の待ち行列に必要なポインタ
   を、タスクの状態を管理する情報を含む第１の制
   御テーブルから分離して、該ポインタのみからな
   る第２の制御テーブルを構成し、該第２の制御テ
   ーブル上に上記第１の制御テーブルの先頭アドレ
   スを設定して、待ち行列に登録した後、処理が終
   了すると、上記第２の制御テーブル上の設定を取
   り消して、上記待ち行列から切り離すことを特徴
   とする待ち行列制御方式。 ２ 前記待ち行列の登録あるいは切り離しは、第
   １の制御テーブルを指定する命令のみを用いて行
   うことを特徴とする特許請求の範囲第１項記載の
   待ち行列制御方式。