JPS5878238A - 待ち行列制御方式 - Google Patents

Abstract

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

Description

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

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

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

ところで、待ち行列を形成する場合には、従来より待ち
行列に登録される可能性のあるすべての制御テーブルに
、待ち行列を形成するために必要なポインタ・−リアを
設けている。しかし、２れらの閣御テーブルのすべてが
同時に待ち行列につながれることはなく、また待ち行列
に接続されたとき、運営、その数は少ないため、多くの
制御テーブルのポインタ・エリアが無駄になっている。

しかも、１！１ｌＩｌテーブルの数が増加すればする纜
ど、無駄なポインタ・エリアが増大するので、オペレー
ティング・システム（以下０８と記す）全体が占有する
メモリ容量は膨大となり、それｋともないユーザ領域が
圧迫されるという問題がある。

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

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

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

上記の各種待ち行列け、該当する待ち行列用キューヘッ
ダにタスク管理テーブル１００，１１０゜１２０．１３
０４１−接続することによって管理されるのであるが、
そのため各タスク管理テーブル１００．１１０，１２０
．１３０　にはタスクの状ｌ！！Ｊを管理する情報１１
０の他に、実行待ち行列用の前向きポインタ１０２、後
向きポインタ１０４、および共有リソース占有待ち行列
用の前向きポインタ１０６、後向きポインタ１０８を設
けている。

前向きと後向きの両ポインタを設ける必要性は、リング
状に結合されるアドレスのうちの途中の一部を取り外す
とき、あるいは順次発生するタスクを待ち行列の最＠に
結合させると１１の制御を高速に行うためである。

また、各キューヘッダ１５０．１５５．１６０．１７０
にも、それぞれ前向ｔＩフインタ１５２．１６２と後向
きポインタ１５４，１６４　を設ける。これらの前向き
ｌインタと後向きポインタの大きさは、それぞれ冬バイ
シである。

第２図ｃ＆）伽）は、それぞれ従来の待ち行列管理状ｓ
ｔ−示す説明図である。

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

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

一方、実行中に共有リソースの占有待ちを生じたタスク
があると、０８はその共有リソースに対応する占有待ち
キューヘッダ１６０によって管理される共有リソース占
有待ち行列の末尾にそのタスクの管理テーブル全挿入し
、この共有リソースの占有待ちが解除されるｔ″′Ｃそ
のタスクの実行を中断させる。

この場合、第２図ｃｂ）Ｋ示すように、すでに宥行待ち
行列用キューヘッダ１５５にタスク管理テーブル１８０
，１９０　が接続されているとＩ！には、タスクの管理
テーブル１９０は実行待ち行列から取り外されて新たに
共有リソース占有待ち行列用中ニーヘッダ１６０に接続
されるのではなく、実行要求が出された時点での先着順
序ｔｍ持するために、実行待ち行列に接続した１１．さ
らに別の共有リソース占有待ち行列ＫＩｅ１棲続する方
法を用いている。すなわち、タスク管理テーブル１９０
に対応するタスクを実行中に、キューヘッダ１６０に対
応する共有リソースの占有待ちが生じた場合、［Ｋ、−
？ニーヘッダ１６０にはどのテーブルも接続されていな
いものとすると、Ｏ８はキューヘッダ１６０の前向きポ
インタ１６２および後向きメインタ１６４にテーブル１
９０の先頭アドレスを設定し、テーブル１９０の前向き
ポインタ１９６および後向きポインタ１９８にキューへ
ラダ１６０の先頭アドレスｔＶ定することｋより、テー
ブル１９０をキューヘッダ１６０にて管理される共有リ
ソース占有待ち行列に登録する。そして、共有リンース
占有待ちが解除されると、そのタスクの管理テーブル１
９０は、Ｏ８により占有待ち行列から取り外される。

このように、従来は、タスク管理テープＮ１００に対し
て、待ち行列を形成するための前向きポインタ１０２，
１０６、後向きポインタ１６４，１０８を設ける必替が
あり、管理テーブル１ケースごとに１６バイシががイン
タとして使用されている。

例えば、登録されたタスク１１２５６個とすると、管理
テーブルのポインタに要する全体のメモリ容量は４０９
６バイト（−１６Ｘ２５６）であり、また同時に実行待
ち行列に接続されるタスク数を多めに予測して３２４Ｊ
ｉＡとすると、そのときに有効に利用しているポインタ
・エリアは５１２バイト（−１６Ｘ３２）しかないこと
になり、その他の５５８４バイトは無駄になっている。

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

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

以下、本発明の実施＠を、ｗＡ−により説明する。

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

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

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

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

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

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

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

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

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

タスク管理テーブル６δ０で示されるタスクに実行要求
が出されると、Ｏ８は空き管理キューヘッダ４８０によ
り管理されている空きキューブＶツタ行列の先頭から１
つのキューブシック５００を取り外し、タスク管理テー
ブルδδ０のポインタ５５２に＋ニーブロック５００の
先頭アドレスを設定し、一方そのキューブシック５００
のテーブル用ポインタ５０９にテーブル６δ０の先頭ア
ドレス全設定することにより、そのテーブル５δ０トキ
ユーブロツク５００との対応づけを行う。

さらに１・Ｏ８は、そのキューブロック５００に関して
従来と同じように実行待ち行列への挿入操作を行う。す
なわち、キューブロック６００の前向きポインタ５０２
は次に並んでいるキューブロック５１０の先頭アドレス
を保持し、彼向きポインタ５０４はその口σに並んでい
る実行待ち行列用キューヘッダ４５０の先頭アドレス全
保持するように情報を設定する。なお、実行待ち行列用
キューヘッダ４−５０の次に他のキューブロックが接続
されているときには、前に並んでいるキューブシックの
先頭アドレスを保持することになる。

次に、第５図伽）においては、タスク管理テーブルδ９
０で表されるタスクの実行中に、共有リソース占有待ち
行列用キューヘッダ４６０に対応する共有リソースの占
有待ちが生じたものとする。

この場合には、テーブル５９０に対応するキューブロッ
ク５４０に一キューヘッダ４６０により管理される占有
待ち行列に挿入する操作全行うが、キューヘッダ４６０
およびキューブロック５４０のポインタ値は、キューヘ
ッダ４６０の先頭アドレスあるいはキューブロック５４
００第２キュー用前向きポインタ５４６のアドレス七す
る。すなわち、Ｏ８は、キューヘッダ４６０の彼向きポ
インタ４６キにはキューブシックδ４ｏの前向きポイン
タ５４６のアドレスを設定し、キューブロック５４０の
前向きポインタ５４６．後向きポインタ５４８にはキュ
−ヘッダ４６００先頭アドレスを設定する。

第６図は、本発明の実施例を示す待ち行列繰作命令の説
明図である・ 第６図において、大文字′（英字）は各命令のニモニッ
クを示し、子文字（英字）はオペランドを示す。ｔｏ）
ｑｈｄはキューヘッダの先頭アドレスを、ｔｏｐｔｂｊ
はテーブルの先頭アドレスを、ｒ・ｇはレジスタ番号を
、また・ａｄ４ｒ　は異常時のジャンプ先アドレスを、
それぞれ示す。

（ａ）　Ｇ　Ｔ　Ｉ　Ｑ　Ｔ命令は、ｔｏｐｑｈｄで示
す空き管理中ニーヘッダ（Ｉ　Ｑ　Ｂ　Ｈ）によって管
理されている空きのキューブロック・リストの先頭から
キューブロック（ＱＩｍ）を１つ外し、ｔｏｐｔｂｊで
示すタスク管理テーブル（Ｔ　ＯＢ）とそのキューブリ
ック（ＱＩｍ）との対応づけを行い、そのキューブロッ
ク（Ｑ　Ｂ）の先頭アドレスをｒ＠ｇで示すレジスタに
設定する機能を果す。このとき、ｔｏｐｑｈｄで示す空
き管理キューヘッダ（ｇｑ、ｎａ）　　に空きのキュー
ブロック（ＱＢ）Ｓ全くない場合には、何もせずに、ｅ
ｉｄ４ｒで示される番地にジャンプする。

％）ｆｆＲＢＱ’ｊ’命令は、ｔｏｐｔｂｊで示すタス
ク管理テーブル（Ｔ　ＯＢ）に対応づけられているキュ
ーバッファ（ＱＢ）とそのタスク管理テーブル（Ｔ　Ｏ
！１）との対応づけ全解消し、そのキューブシック（Ｑ
　Ｂ））ｔｏｐｑｈｄて示す空き管理キューヘッダ（鵞
ＱＢＭ）により管理されている空きキューブシック・リ
ストの先頭に挿入する機能を果す。

（Ｑ）工ＮＱＬテ命令は、ｔｏｐｑｂｌで示すキュー　
ヘッダ（ＩＱＢＨ）により管理されている待ち行列の末
尾に、ｔｏｐｔｂｊで示すタスク管理テーブル（実際に
はこのタスク管理テープ、１％／（ＴＣＢ）に対応する
キューブ・ロック（ＱＢ））’？その待ち行列が第１キ
ユーになるように挿入する機能を果す。

（ａ）工ＮＱＬＳ命令は、ｔｏｐｑｂ４で示すキューヘ
ッダ（ＫＱＢＨ）により管理されている待ち行列の末尾
に、ｔ−ｏｐｔｂｌで示すテーブル（実際には、このデ
ープル（テＯＢ）に対応するキューブロック（ＱＢ））
をその待ち行列が第２キユーになるように挿入する機能
を果す。

（ｅ）　ＲＭ　Ｖ　Ｑ　Ｔ命令け、ｔｏｐｔｂｊで示す
テーブル（実際には、このテーブル（’！’　ＯＢ）に
対応するキューブロック（ＱＢ））を第１キユーから取
り外す機能を果す。

（ｆ）ＲＭＴＱＳ命令は、ｔｏｐｔｂｊで示すテーブル
（実際には、このテーブルに対応するキューブロック）
を第２キユーから取り外す機能を果す。

第７図は、第６図に示すＧＴＦＱＴ命令の処理手順の７
０−チャート、第８図は同じ（ＧＴＦＱ、Ｔ命令のデー
タ操作説明図である。

ブロック７０５では、第８図（ａ）に示すよう如、ｔｏ
ｐｑｈｄ　６０２　　で示される空き管理キューヘッダ
４８０の前向きポインタ４８２の内容を取り出す。

次に、ブロック７１０では、前向きポインタ４８２の内
容とｊｏｐｑｈｄ　６０２　（すなわち、管理キューヘ
ッダ４８０の先頭アドレス）を比較し、空きキューブロ
ックがないか否かをチェックする。

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

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

次に、ブリック７２０では、以下の操作を行うことによ
り空きキューブロック・リストの先頭のキューブロック
８１０奢リストから取り外す。

すなわち、キューブロック８１０の前向きポインタ８１
２の内容を空き管理キューヘッダ４８０の前向きポイン
タ４８２に？定しく第８図の点線矢印）、キューブロッ
ク８１０の後向きポインタ８１４０内容管前向きポイン
タ８１２の内容によって示されるキューブジッタ８２０
の後向きポインタ８２４（あるいは管理キューヘッド＋
８０の後向きポインタ４８４）に設定する（第８図の点
線矢印）０ 次に、ブロック７２５では、以下の操作によりキューブ
−ツタ８１・０とｔｏｐｔｂ１６０４で示されるテーブ
ル８３０との対応づけを行う（第８図６）参照）。すな
わち、キューブロック８１０のテーブル用ポインタ８１
９にｔｏｐｔｂｚ６０４　（すなわち、テーブル８３０
の先頭アドレス）Ｙｔ段設定、テーブル８３０のポイン
タ８３２にブロック７１５においてレジスタ８００に設
定したキューブロック８１０の先頭アドレスを設定する
（第８図の点線矢印）。ブロック７２５の処理を終了す
ると、本命令は終了するので、次の番地の命令実行に移
る（７３０）。

第８図（荀の状態から、第ａ　ｍ　ｃｂ＞の状態に移る
ことにより、空きキューブロック０１つ８１０がｔｏｐ
ｔｂ／　　で示すテーブル８３０と対応づけられたこと
になる。

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

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

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

第１１図（Ａ）は、第６図における工ＮＱＬＴ命令の処
理手順を示す７ｕ−チャートであり、第１２Ｗ１は同じ
くそのデータ操作図である。

ブロック１１０５では、ｔｏｐｔｂ１６２４で示される
テーブル１２３０のポインタ１２３２の内界を取り出す
。次に、ブロック１１１０では、ｔｏＨ，ｈａ６２２で
示されるタスク実行待ち行列キューヘッダ４５０の後向
きポインタ４６４の内容を取り出す。

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

第１１図（Ｂ）は、第６図における工ＮＱＬＢ命令の処
理手順を示すフリーチャートであり、第１３図は同じく
そのデータ操作しＩである。

工ＮＱＬＴ命令と本命令（工ｙＱＬｓ）との相違点は、
前者が第１キユー全対象とするのに対し、後者は第２キ
ユーを対象とするところにある。すなわち、第１１図（
Ｂ）のブロック１１５５．１１６０は、第１１図（Ａ）
のブロック１１０５．１１１０と同一内容であるので、
相違点であるブロック１１６５について説明するＯ プロッタ１１６５では、以下の操作によりデープル１３
３０のポインタ１３３２で示されるキュープロツク１３
１０１共有リソース占有待ち行列キューヘッダ４６０で
管理される待ち行列を、第２キユーとしてその待ち行列
の末尾に挿入する。すなわ、ち、待ち行列キューヘッダ
４００の後向きポインタ４６４の内容で示されるキュー
ブロック１３０００前向きポインタ１３０６　（あるい
は待ち行列キューヘッダ４６０の前向きポインタ４６２
）の内容をキューブロック１５１Ｏの前向きポインタ１
３１６に設定し、待ち行列キューヘッダ４６０の後向き
ポインタ４６４の内容をキューブロック１３１０の後向
きポインタ１３１８に設定し、テーブル１３３０のｌイ
ンタ１３３２の内容に８（バイト）１３４０を加えた値
（スなわち、キューブ−ツク１３１０の前向きｌインタ
１３１６のアドレス）ｋキューブ四ツク１３００の前向
きポインタ１３０６　（あるいけ待ち行列キューヘッダ
４６０の前向きポインタＬ６２）および持ち行列キュー
ヘッダ４６０・の後向きメインタ４６４に設定する。

第１４図体）は、第６図におけるＲＭＶＱ〒命令の処理
手順を示すフローチャーｔであり、！１５ｇは同じくそ
のデータ操作図である。

ブロック１４０５では、ｔｏｐｔｂ／６４２で示される
テーブル１５４０のポインタ１５４２の内容を取り出す
・次に、ブロック１４１０では、以下の掃作によりテー
ブル１５４０のｌインタ１５４２の内容で示されるキュ
ーブロック１５１Ｏをそれが接続されている第１キユー
から取り外す。キューブロック１５１Ｏの前向きポイン
タ１５１２の内容を、後向きポインタ１５１４の内容で
示されるキューブロック１５０００前向きポインタ１５
０２　（あるいは実行待ち行列キューヘッダ４５０の前
向きポインタ４６２）に設定し、キューブロック１５１
００後向きぎインタ１５１４の内容を前向きポインタ１
５１２の内容で示されるキューブロック１５２０の後向
きポインタ１δ２４（あるいは待ち行列キューヘッダ４
５０の後向きポインタ冬５４）に設定する。

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

第１４図に）は、第６１１ＪＫおけるＲＭ’１ｒＱＢ命
令の処理手順を示す７撃−チャードであり、第１６図は
同じくそのデータ操作図である。

先忙述べたＩＬＭＶＱ、テ命令と本命令との相違は、前
者が第１キユーに対するものであるのに対して、後者は
第２キユーに対するものである点にある。

したがって、第１４図伸）のプ胃ツタ１４６５は第１４
図（（転）のブロック１４０６と同一であり、ブロック
１４６０のみが異なるので、異なる動作についてのみ説
明する。

ｔｏ）ｔ’ｂｊ６５２で示されるテーブル１６４０のポ
インタ１６４２０内容により示されるキューブジッター
１６１Ｏの前向きポインタ１６１６の内容を、後向きポ
インタ１６１８の内容で示されるキューブロック１６０
００前向きポインタ１６０６　（あるいは共有リソース
占有待ち行列キューヘッダ４６０の前向自ポインタ４６
２）に設定し、キューブロック１６１０の後向１１電イ
ンタ１６１８０内容を前向自がインク１６１６の内容で
示されるキューブロック１６２００後向きポインタ１６
２８　（あるいはキューヘッダ４６０の彼向きポインタ
４６４）Ｋ設定する。

以上、第６図に示す各命令について、動作を説明したが
、これらの説明から明らかなように、タスク管理テーブ
ル（Ｔ　ＯＢ）から待ち行列用のポインタを切り離して
キューブロック（Ｑ　Ｂ）として独立させ、かつキュー
ブロック（ＱＢ）　′ｆｔ必要最少限のケース数のみ用
意し、必要に応じてタスク管理テーブル（Ｔ　ＯＢ）と
キューブロック（ＱＢ）ｔ一対応づけてテーブル（Ｔ　
ＯＢ）の待ち行列全形成するテーブル構造にするので、
ポインタ・エリアの無駄なメモリ容量を側限することが
できる。例えば、タスクＩＩＨｋ’Ｔｈ　２５６個、キ
ューブロック（ＱＢ）のケース数（同時に実行可能なタ
スク数）’ｔ６４個、同時実行中のタスク全県めに見て
３２個と仮定すると、管理テーブル（Ｔ　ＯＢ）のポイ
ンタおよびキューブロック全体の容量は２３０４バイト
（−４バイト×δＸ６４＋４バイトｘ２５６）であり、
このうち有効に利用されているエリアは７６８（−４バ
イト×５×３２＋冬バイト×３２）になる。すなわち、
従来は、待ち行列Ｗ塩のために４０９６バイト（−４パ
イ）Ｘ４Ｘ２５６）を要していたのに対して、２３０’
バイトに減少することができ、かつそれらのエリアの利
用度全向上できる。

次に、第６図に示すＧＴＦＱ’Ｅ’、ＦＲＩＣｑＴ、Ｉ
ＮＱＬτ、ＩＮＱＬＳ、ＲＭＶＱＴ、ＲＭＶＱＳ　等の
命令全役けることＫよって、ユーザはキューブロックの
構造やキューブロック間の結合を意識することなく、従
来と同じようにタスク管理テーブル（ＴＯＢ）の先頭ア
ドレス全意識するのみで、タスクの待ち行列制御を行う
ことができ、かつタスク管理テーブル（ＴＣＢ）とキュ
ーブロック（Ｑ　Ｂ）の対応づけはマイクロプレグラム
により実現されるので、それらに伴うオーバヘッドは無
視できるほど少なくすることができる。

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

【図面の簡単な説明】

第１図は従来の待ち行列に関する制御テーブルの構造図
、第２図は従来の待ち行列管理状態を示す説明図、第３
図は本発明の実施例を示す待ち行列制御システムの概略
ブシツク図、第４図は本発明の実施例を示す制御テーブ
ルの構造図、第５図は本発明の実施例を示す待ち行列の
形成方法の説明図、第６図は本発明の実施例管示す待ち
行列操作命令の説明図、第７図、第９図、第１１図およ
び第１４図はいずれも第６図に示す制御命令の処理手順
のフローチャ゛−）％ｔａ８図、第１０図、第１２図、
艶１３図、第１♂馳よび第１６図はいずれも第６図に示
す制御命令に伴うデータ操作の配明図である。 ４００．４２０，４３０，５５０，５６０，５７０．．
５８０゜５９０．８３０．１０３０．１２２０．１２３
０．１３２０゜１３３０．１５３０，１５４０．１５５
０．１６３０．１６４０゜１６５０：タスク管理テーブ
ル（ＴＣＢ）、１４ｏｌ＋牛Ｏ：先頭アドレス・ポイン
タ、１６０．１５５゜４ｆｉ０．４５５　　：実行待ち
行列用キューヘッダ、１６０．１７０，４６０，４７０
　　？共有リソース占有待ち行列用キューヘッダ、４８
ｏ：空き管理キューヘッタ、４９０，４９５．５０９．
５１０．５２０．５３０゜５４０．８１０．８２０．１
０１０，１０２０．１２００゜１２１０．１３００．１
３１０．１５００．１５１０．１５２０゜ＦｆＯＯ＋　
１６１０．１６２０　：　＋：ｘ、−プｏツク、３７０
：処理装置、３００：主メモリ、３３ｏ：メモリ・アド
レス◆レジスタ、３３５８メモリ・データーレジスタ、
３４０：Ｉｆ算ａ路、３５ｏ：制御回路、３６０：制御
メモリ、７００　ｈ９００，１１００゜１１δ０，１４
００，１４５０　ｊ待ち行列操作用マイタルプログラム
。 特許出願人　株式会社　日立製作所 第１図 第２図 １７０ 第３図 兎 第４図　　　　　　　　　（ａ） 第５図 ［ 伍 第６図 第８図 句 第９図 第１０図 第１２図 ６２２６２４− 第１３図 ６３２　　　　　氏Ａ ｒ 第１４図 （Ａ）　　　　　　　　■） 第１５図 偕 ５４０

Claims (1)

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