JPH08506197A - 擬似待ち行列を形成するためにメモリ・レジスタを動的に割り振るシステム - Google Patents

Abstract

(57)【要約】 それぞれが１組の基準により規定されている複数の待ち行列（20−23）を具備する待ち行列システムにおいて、該待ち行列システムは複数のヘッダー・レジスタ（１−３）と複数のタスク・レジスタとを具備し、該ヘッダー・レジスタの各々は待ち行列システムにおける待ち行列を規定し、かつ該タスク・レジスタの各々は該待ち行列システムにおける各待ち行列（20−23）と関連接続され得るものである。各ヘッダー・レジスタは独特のアドレスを有し、かつ前のフィールドと次のフィールドとを含んでいる。夫々の前のフィールドと上記次のフィールドとは、それぞれの待ち行列が二重リンク構造で形成されるように、与えられた待ち行列において別のレジスタのアドレスを記憶する。各ヘッダとタスク・レジスタにおける前のフィールドと次のフィールドにおけるアドレスを、上記タスク・レジスタの各々が常に待ち行列システムの待ち行列に指定されるように制御することにより、タスク・レジスタを待ち行列（20−23）に動的に割り振るために制御手段が設けられている。

Description

【発明の詳細な説明】 擬似待ち行列を形成するためにメモリ・レジスタを動的に割り振るシステム この特許文書の開示の部分は、著作権の保護に関する要件を含んでいる。著作 権の所有者は、特許文書または特許開示の何れかに依るファクシミリー再生に対 して、それがアメリカ特許商標庁の特許ファイルまたはレコードに記載してある ので、異議を申し立てないが、そうでない場合に全ての著作権を保留する。 関連出願のクロス・リファレンス 次に示す同時係属アメリカ特許出願は、本出願の譲受人に譲渡され、本出願と 其の開示に関連していて、引例に依ってここに包含される。 （A）Ser．No.08／006,457はStephen R.Cornabyに依って1993年１月21日に、 単一ディスク・ドライブに於いて同じ磁気ディスク媒体を作動する２つのアクチ ュエータ間でタスクを割り振するシステムという名称で出願された。 発明の背景 発明の分野 発明は、待ち行列を処理システム内部で構築し且つデータを構築された待ち行 列間で効果的に移動するためのシステムに関する。 関連技術の説明 多くのコンピュータ・システムは、タスクとデータをコンピュー タ処理システムの内部で転送することを管理するために待ち行列を採用している 。待ち行列は、待ち行列に記憶されているエントリが、エントリが待ち行列に記 憶されていた順序で待ち行列から読み取られる、先入れ先出し（FIFO）待ち行列 のように、数多くのタイプになることができる。別のタイプの待ち行列は、待ち 行列に記憶されているエントリは待ち行列から読み取られる最初のエントリであ る、後入れ先出し（LIFO）である。これは、待ち行列に記憶されている最新のデ ータが待ち行列から読み取られる最初のデータになると言うことができる。 待ち行列は、ハードウェア・レジスタから且つメモリの専用部分から構成され 、ソフトウェア・レジスタとして作動し、そこでは、待ち行列はプロセッサのプ ログラムの制御のもとで操作される。メモリから形成される待ち行列は、1982年 にEditor-In-Chief David F.Stout，McGraw-Hill Book Companyに依ってマイク ロプロセッサ・アプリケーション・ハンドブック のテキストに説明されている。 著者は、17.6項で“タスク・スケジュールの遂行”という名称で、前方連結構造 を用いるタスク待ち行列の形成について述べている。前方連結構造は、次の待ち 行列エントリのアドレスに対するポインタを含んでいる各々待ち行列のエントリ を備えて形成されている。前方連結プロセスに依って形成された待ち行列は、任 意の与えられた瞬間に待ち行列のレジスタの数と順序を定める。更に、多くの処 理システムの場合、各々待ち行列が其の待ち行列のエントリに関して行われる動 作のコースを指定するために用いられる、待ち行列の内部のエントリとして定め られたタスクを或る待ち行列から別の待ち行列に移動することが望まれる。普通 、タスクは、待ち行列から取り出されて別の待ち行列に物理的に転送される。待 ち行列間のタスクの移動は、時間消費型のプロセスになり、且つタスクの転送中 に生成されるエラーをタスクに与えるので、エラー回復手順が呼び出されること を要求したり、再転送動作を試みることを要求することになる。 発明の要約 発明の目的は、各々待ち行列が任意のタスク・レジスタをシステムに含むこと ができる複数の待ち行列を生成する待ち行列システムを提供することにある。 発明の別の目的は、待ち行列システム内部の待ち行列が固定された長さに限定 されないことにある。 発明の別の目的は、システム内部の待ち行列が種々のタイプの待ち行列になる ことを可能にする待ち行列システムを提供することにある。 発明の別の目的は、各々レジスタはレジスタが其の瞬間に位置する待ち行列の 前と次のフィールドに対するポインタを含んでいる、二重連結ポインタ構造を用 いて、待ち行列システムの待ち行列を構成することにある。 要するに、本発明は、ランダム・アクセス・メモリ・ユニットの内部で専用セ ットのメモリ・レジスタから複数の待ち行列を形成することを意図されている。 メモリ・レジスタはヘッダー・レジスタまたはタスク・レジスタになる。各々待 ち行列は、指示されたヘッダー・レジスタと、その待ち行列に指定されたタスク ・レジスタを備えている。タスク・レジスタは待ち行列システム内部の待ち行列 に常に指定される。全てのレジスタは、少なくとも２つのフィールド、すなわち 前のフィールドと次のフィールドを含んでいる。待ち行列システム内部で用いら れる任意のレジスタに対して、前のフィールドは其の待ち行列で先行するレジス タのアドレスを含んでいて 、次のフィールドは待ち行列で後続するレジスタのアドレスを含んでいる。或る 待ち行列は、待ち行列システムに於いて作動状態の待ち行列の１つに今用いられ ていないタスク・レジスタを含むことになる空の待ち行列として指示される。タ スク・レジスタは、移動されるレジスタの次と前のフィールドと、待ち行列に挿 入される或いは其こから取り出されるタスク・レジスタの挿入または取り出しに 依って影響を受ける待ち行列の他のレジスタの次と前のフィールドの内容を変更 することに依って、待ち行列間を効果的に移動される。タスク・レジスタは、待 ち行列間を物理的に移動されないが、レジスタの前と次のフィールドを制御する ことに依って効果的に移動されるので、各々疑似待ち行列の長さが任意の与えら れた瞬間に其の待ち行列のためのヘッダー・レジスタに連結されるタスク・レジ スタの数に依って定められる待ち行列システム内部の疑似待ち行列の形成を可能 にする。制御手段は、タスク・レジスタを待ち行列に挿入し且つ其こから取り出 す手順を実行するために与えられている。 最後に、異なるタイプの待ち行列が待ち行列システムに含まれることもできる 。例えば、或る待ち行列は先入れ先出し待ち行列になり、第２の待ち行列は後入 れ先出し待ち行列になり、第３の待ち行列はアドレスに依って順序設定される待 ち行列になり、第４の待ち行列はタスク・レジスタに関連する次と前のフィール ド以外のタスク・レジスタの別のフィールドの内容に依って順序設定される待ち 行列になる。 本発明の長所は、待ち行列システムが、システムのハードウェアに対する変更 を要求せずに、汎用化できることにある。 発明の別の長所は、タスクは、タスク・データに転送エラーを露呈せずに、待 ち行列から待ち行列に瞬時に転送できることにある。 図面の簡単な説明 発明は其の特定の実施例を参照して説明されていて、参照数字が図面に付記さ れている。 図１は発明の待ち行列システムを実施する処理システムを示すハイ・レベル図 であり、 図２は４つの待ち行列を採用する待ち行列システム構成を示し、 図３Ａ〜３Ｌは待ち行列システムに従って図２に表される待ち行列間のタスク の移動を示す図である。 図４はタスク・レジスタを待ち行列から取り出すルーチンＡの流れ図である。 図５は、タスク・レジスタ・アドレスに依って指示される例を用いて順序設定 された順で待ち行列にタスク・レジスタを挿入するルーチンＢの流れ図である。 図６は、タスク・レジスタが其の待ち行列の最後の位置になるように、タスク ・レジスタを待ち行列に挿入するルーチンＣの流れ図である。 好まれる実施例の説明 図１を見ると、待ち行列システムは、プロセッサ10と読取専用メモリROM 11と ランダム・アクセス・メモリRAM 12に依って部分的に構成される処理システムの 内部に実現されている。プロセッサ10は、ROM 11にライン13を介して連なり、RA M 12にライン14を介して連なっている。このプロセッサと読取専用メモリとラン ダム・アクセス・メモリの一般的な構成は、産業界の全体にわたって広く用いら れている。処理システムは、大型コンピュータ計算システムの内部に一般的に含 まれていて、全体的なシステム内の特殊なタイプの機 能の取扱のために専用化されている。例えば、このような処理システムは、ディ スク・ドライブ・ファイル制御ユニットやＩ／Ｏチャンネル制御ユニットだけで なく、主要処理ユニット自体の内部にも含まれている。プロセッサは、プロセッ サが其の設計された機能を実行できるように書き込まれたシステム・プログラム の制御のもとで実行する。 本発明の待ち行列システムは、プロセッサ10に依って制御され、疑似待ち行列 の実際の形式に相応してRAM 12を使用する。RAM 12は、各々アドレスが数多くの ビットまたはバイトのデータを含んでいる複数の記憶アドレスを含むように構成 されている。待ち行列システムは、そのアドレスをRAM内部の疑似待ち行列の形 式に相応する待ち行列システムに専用化されるランダム・アクセス・メモリの内 部で要求する。アドレスの各々はタスク・レジスタまたはヘッダー・レジスタと 考えられる。各々ヘッダーとタスク・レジスタは、少なくとも２つのフィールド 、すなわち前のフィールドと次のフィールドを含んでいる。レジスタの前のフィ ールドは待ち行列の前のレジスタのアドレスを記憶し、次のフィールドは待ち行 列の次のレジスタのアドレスを記憶する。 各々待ち行列は少なくとも２つのヘッダー・レジスタから構成されている。待 ち行列が待ち行列に関連するタスク・レジスタを有していない時に、その待ち行 列のヘッダー・レジスタは、ヘッダー・レジスタを、待ち行列のヘッダー・レジ スタの前と次のフィールドに記憶される自らのアドレスにする。従って、前と次 のフィールドは待ち行列に相応するヘッダー・レジスタの場所を指示するポイン タを備えている。各々タスク・レジスタは待ち行列に常に指定される。待ち行列 システムに於いて、１つの待ち行列は、その機能としてオペレーティング・シス テムに依って作動されるタスクに今指定 されていないタスク・レジスタを含んでいる空の待ち行列として指示される。待 ち行列システムは、数多くの異なる構成を備えているので、設計者のニーズに対 応できる。 図２は、待ち行列システムの好まれる実施例を説明するために、待ち行列シス テムの内部に於いて４つの待ち行列20と21と22と23から成る構成を示す。この構 成は、空の待ち行列として作動し且つ待ち行列システムのタスク・レジスタの全 てを最初に含むことになる、待ち行列Ｄ23から構成されている。プロセッサ10が 待ち行列システムを用いて実施されるタスクを受け取ると、タスクは最下位のア ドレスを待ち行列Ｄ23に有するタスク・レジスタに指定される。待ち行列は、待 ち行列Ｄ23から取り出されて、待ち行列Ａ20に挿入される。タスクが待ち行列Ａ 20に位置する間に、システムは、タスクの内容と、資源と動作が処理システムを 用いて其のタスクに関連して実施されなければならない内容を決定するために種 々の動作を実施する。処理システムは、タスクが待ち行列Ｂ21に関連する第１の 処理コースまたは待ち行列Ｃ22に関連する第２の処理コースに従って処理される かどうかについての決定を行う。タスク・レジスタは、タスク・レジスタを待ち 行列Ａ20から取り出し且つタスク・レジスタを待ち行列Ｂ21または待ち行列Ｃ22 に挿入することに依って、効果的に移動される。タスクが終了すると、タスク・ レジスタは、待ち行列Ｂ21または待ち行列Ｃ22から取り出されて、待ち行列Ｄ23 に挿入される。システムは、タスクが待ち行列Ｂ21または待ち行列Ｃ22に関連す る処理コースに依って処理される必要がない場合に、終了したタスクに関連する タスク・レジスタは、待ち行列Ａ20から取り出されて、待ち行列Ｄ23に挿入され る更なるオプションを備えている。 引用された同時係属出願“同じ磁気ディスク・ドライブを単一の ディスク・ドライブで作動する２つのアクチュエータ間にタスクを割り振するシ ステム”に、単一の磁気ディスク媒体を作動する二重アクチュエータ・システム が説明されている。本発明の待ち行列システムは、そこに引用されているマイク ロプロセッサとRAMユニットの内部に採用されている。本出願の付録Ａとクロス ・リファレンス出願の場合、待ち行列Ａ20はコマンド待ち行列であり、待ち行列 Ｂ21はデータを検索する或いは磁気媒体に記憶するタスクは１つ或いは２つだけ のアクチュエータを採用する１チャンネル待ち行列であり、待ち行列Ｃ22は両方 のアクチュエータを単一の磁気媒体に関してシステムからのコマンドの実行に使 用する２チャンネル待ち行列であり、最後に待ち行列Ｄ23は空の待ち行列である 。 タスクを待ち行列Ｂ21、すなわち、１チャンネル待ち行列に挿入し且つ取り出 すためのルーチンは、クロス・リファレンス同時係属出願に詳細に説明されてい るので、ここで繰り返し説明されない。本発明の待ち行列システムの説明を単純 にするために、待ち行列Ｂ21は順序設定されたアドレスである待ち行列として示 される。発明の待ち行列システムは図２に図示される構成に限定されず、待ち行 列システムの設計者は、本発明に従って、システム設計者が要望する待ち行列を できるだけ数多く構成する待ち行列システムを具備できて、これらの待ち行列の 各々は設計者が指摘し管理する規準に従って順序設定できることが理解されるべ きである。更に、ランダム・アクセス・メモリ内部のメモリ・レジスタのアドレ スは、単一ブロックの専用アドレスまたは複数のブロックの専用アドレスまたは 連続しないアドレスになる。再び、アドレス、およびランダム・アクセス・メモ リ内部のアドレスの配置は設計者の選択に依存し、メモリで用いられるアドレス の場所は待ち行列システムの構造にとって重要な問題にならない。 ここで、発明の説明を単純にするために、待ち行列Ａ20とＢ21とＤ23のタスク ・レジスタは待ち行列の内部で順序設定されるアドレスにあり、待ち行列Ｃ23の タスク・レジスタは待ち行列に対する挿入の順で順序設定される。待ち行列Ｃ23 のタスクが待ち行列Ｃ23のヘッダー・レジスタの次のフィールドに記憶されてい るタスク・レジスタ・アドレスを用いて作動される場合に、待ち行列Ｃ23は効果 的に先入れ先出し（FIFO）の待ち行列になる。待ち行列Ｃ23のタスクが待ち行列 Ｃ23のヘッダー・レジスタの前のフィールドに記憶されているタスク・レジスタ ・アドレスを用いて作動される場合、待ち行列Ｃ23は効果的に後入れ後出し（LI FO）待ち行列になる。待ち行列の文字は、待ち行列を待ち行列システム内部で順 序設定する方式およびタスクを待ち行列から取り出す方式について、システム設 計者に依って決定されることが容易に分かる。再び、待ち行列の各々を待ち行列 のタイプに区分けすることは、待ち行列システムに関連して用いられる全てのタ スク・レジスタが待ち行列システムの待ち行列の１つの内部に常に置かれること を保証するために、１つの待ち行列が空の待ち行列として専用化されなければな らないことを除けば、システム内部に於いて重要なことでない。 図４で、ルーチンＡは、タスク・レジスタを待ち行列システム内部の任意の待 ち行列から取り出す手順を示す。タスク・レジスタを或る待ち行列から別の待ち 行列に移動する移動動作中に、移動動作は、最初にルーチンＡを実行して、以降 、今のレジスタと呼ばれるタスク・レジスタを、待ち行列から取り出す。この取 り出し動作を実行するために、ルーチンＡは次に示す順序のステップを実行する 。ステップ１は前のレジスタの次のフィールドに記憶されるアドレスを作成し、 そのアドレスは、今のレジスタの前のフィールドに記憶され、今のレジスタの次 のフィールドに記憶されたアドレスと等 しくなる。ステップ２は次のレジスタの前のフィールドに記憶されるアドレスを 作成し、そのアドレスは、今のレジスタの次のフィールドに記憶され、今のレジ スタの前のフィールドに記憶されたアドレスと等しくなる。このように、待ち行 列のタスク・レジスタ間の連結は、今のレジスタが待ち行列から取り出された後 に再び構築される。これは別の待ち行列に取り出される今のレジスタの挿入ルー チン中にアドレス設定されるので、取り出される今のレジスタの次のフィールド と前のフィールドに関して、ここで何も行われないことに注目すべきである。 図５で、ルーチンＢ、タスク・レジスタが待ち行列のタスク・レジスタのアド レスの昇順で順序設定される事例を用いて、順序設定された順序で待ち行列に取 り出される今のレジスタを挿入するプロセスを示す。これは、取り出される今の レジスタは、図２に関連して説明されたような構成の待ち行列Ａ，ＢまたはＤに 挿入される時に準じるルーチンである。この動作に於いて、今のレジスタは、待 ち行列に挿入される今のレジスタのアドレスより、次の最下位のアドレスを有す るレジスタと次の最上位のアドレスを有するレジスタの間で待ち行列に挿入され ることが要求される。ヘッダー・レジスタは、その前または次のフィールドがこ の手順に依って変更されるレジスタの１つになる周囲条件に注意しなければなら ない。 ルーチンＢは、次に示す順序のステップを実施して、この動作を実行する。ス テップ１は、今のレジスタが挿入される希望された待ち行列のヘッダー・レジス タを選択する。ステップ２は、最初の事例でヘッダー・レジスタになる、選択さ れたレジスタの次のフィールドに記憶されているアドレスが、ヘッダー・レジス タのアドレスと等しいかどうか決定する。選択されたアドレスの次のフィールド に記憶されているアドレスがヘッダー・レジスタのアドレスである 場合、ルーチンはステップ５に分岐する。選択されたレジスタの次のフィールド に記憶されているアドレスがヘッダー・レジスタのアドレスと等しくない場合、 ステップ３が実行されて、今のレジスタのアドレスが選択されたレジスタの次の フィールドに記憶されているアドレスより大きいかどうかについて試験される。 この紹介が否定的である場合、ルーチンはステップ５に分岐する。ステップ３の 紹介が肯定的である場合、ステップ４が実行され、選択されたレジスタを、その アドレスがいま選択されているレジスタの次のフィールドに記憶されるレジスタ として、ステップ２に戻る。ステップ２とステップ３とステップ４のループは、 ループがステップ２またはステップ３が終了するまで繰り返される。ルーチンが ステップ２またはステップ３を終了すると、ステップ５が処理される。ステップ ５は、取り出された今のレジスタの次のフィールドに記憶されるアドレスを、選 択されたレジスタの次のフィールドに記憶されたアドレスと等しくする。ステッ プ６は、取り出された今のレジスタの前のフィールドに記憶されるアドレスを、 選択されたレジスタのアドレスと等しくする。ステップ７は、アドレスが選択さ れたレジスタの次のフィールドに記憶されるレジスタの前のフィールドに記憶さ れていたアドレスを、取り出された今のレジスタのアドレスと等しくする。最後 に、ステップ８は、選択されたレジスタの次のフィールドに記憶されるアドレス を、取り出された今のレジスタのアドレスと等しくする。ステップ５と６と７と ８は、ステップ８が今のステップ５とステップ７の次に常に続くことを除けば、 入れ替えできることに注意すべきである。ルーチンＢのステップ８が終了すると 、取り出された今のレジスタは待ち行列に挿入され、待ち行列内部の全てのタス ク・レジスタは待ち行列に於いてタスク・レジスタの昇順するアドレスの順序に なる。 ルーチンＢは昇順するタスク・レジスタ・アドレスの順でタスク・レジスタの 順序設定のために説明されてきたが、順序設定は、待ち行列システムの各々ヘッ ダーとタスク・レジスタの更なるフィールドのデータを用いて行われる。更なる フィールドが待ち行列のタスク・レジスタの順序を決定するために用いられる時 に、ルーチンＢは、ステップ１と２と３と４で、その目的のために用いられる其 の更なるフィールドに記憶されているデータに従って適切な選択されたレジスタ を決定するために修正される。選択されたレジスタが決定されると、挿入される 今のタスク・レジスタはルーチンＢのステップ５と６と７と８に挿入される。 図６で、ルーチンＣは取り出された今のレジスタを待ち行列に挿入する手順を 示し、そこに取り出された今のレジスタが待ち行列の最後のタスク・レジスタと して挿入される。効果的に、タスク・レジスタは、タスク・レジスタが待ち行列 に挿入された順序で待ち行列内部に順序設定される。ルーチンＣは、次に示す順 のステップを実施して、この動作を実行する。ステップ１は希望された待ち行列 のヘッダー・レジスタを選択する。図の待ち行列構成の場合、ルーチンＣは、取 り出された今のレジスタが待ち行列Ｃ23に挿入される時に必ず実行される。ステ ップ２は、取り出された今のレジスタの次のフィールドに記憶されるアドレスを 、ヘッダー・レジスタのアドレスと等しくする。これは、取り出された今のレジ スタが待ち行列の最後のレ スタとして待ち行列で挿入されることを保証する。 ステップ３は、取り出された今のレジスタの前のフィールドに記憶されているア ドレスを、ヘッダー・レジスタの前のフィールドに記憶されているアドレスと等 しくする。ステップ４は、アドレスがヘッダー・レジスタの前のフィールドで指 示されたレジスタの次のフィールドに記憶されるアドレスを、取り出された今の レジスタのア ドレスと等しくする。最後に、ステップ５は、ヘッダー・レジスタの前のフィー ルドに記憶されるアドレスを、取り出された今のレジスタのアドレスと等しくす る。 待ち行列のレジスタは、レジスタの次のフィールドに依って前進ループで且つ レジスタの前のフィールドに依って後退ループで連結される。待ち行列の各々の 内部のレジスタの各々の内部で次のフィールドと前のフィールドを使用すること は、システムが順序通りに待ち行列を上下に進めることを可能にする。システム は、待ち行列の内部の任意のレジスタに、待ち行列内部の其の位置に関係なしに 、システムに依って分類されるレジスタのアドレスに従ってアクセスできる。再 び、これは、システム設計者のニーズを満足するために待ち行列システムを設計 するシステム設計者に最大限度の柔軟性を与える。そのように希望される場合、 ルーチンＡとＢとＣは、待ち行列間の移動動作がオペレーティング・システムに 依って指示される時に、必ず、プロセッサ10に依ってアクセスされるROM 11の内 部に恒久的に記憶できる。 待ち行列システムの動作について、図３Ａ〜３Ｌに図示される事例を参照しな がら説明される。図は、各々アドレスＡとＢとＣとＤを有する４つのヘッダー・ レジスタを各々示している。アドレスＡは待ち行列Ａ20のヘッダー・レジスタの アドレスであり、アドレスＢは待ち行列Ｂ21のヘッダー・レジスタのアドレスで あり、アドレスＣは待ち行列Ｃ22のヘッダー・レジスタのアドレスであり、アド レスＤは待ち行列Ｄ23のヘッダー・レジスタのアドレスである。９つのタスク・ レジスタは１〜９のアドレスを有して図示されている。再び、これらの事例で使 用するために選択されたアドレスに意味がなく、アドレスはシステム設計者に依 って指定されて用いられる規準に従うヘッダー・レジスタまたはタスク・レジス タに相応して 選択される。ヘッダー・レジスタとタスク・レジスタの各々が其れに関連する前 のフィールドPFと次のフィールドNFを備えている。再び、前のフィールドPFは待 ち行列の内部に前のレジスタのアドレスを有していて、次のフィールドNFは待ち 行列の内部に次のレジスタのアドレスを有している。タスク・レジスタに関して 、２つの他のカラムが与えられていて、TNとラベル表示されたカラムはタスク・ レジスタに指定されたタスクを識別するために用いられ、Ｑとラベル表示された カラムはタスク・レジスタがいま指定されている待ち行列を指示するために用い られる。 図３は、タスク・レジスタの全てが待ち行列Ｄ23に指定される時に、タスク・ レジスタとヘッダー・レジスタの関係を示す。図から分かるように、アドレスＡ とＢとＣの待ち行列ＡとＢとＣのヘッダー・レジスタは、それらに関連するレジ スタの前のフィールドと次のフィールドに記憶されている其れら自体に関連する ヘッダー・レジスタのアドレスの各々を有している。前のフィールドと次のフィ ールドが共にヘッダー・レジスタのアドレスを含んでいる時に、その待ち行列は 空になる。従って、待ち行列ＡとＢとＣはこの時に空になり、全てのレジスタが 待ち行列Ｄ23に位置する。待ち行列Ｄ23のヘッダー・レジスタの次のフィールド はアドレス１に待ち行列の最初のタスク・レジスタのアドレスを含んでいて、待 ち行列Ｄ23のヘッダー・レジスタの前のフィールドはアドレス９に待ち行列の最 後のタスク・レジスタのアドレスを含んでいる。これから、タスク・レジスタは タスク・レジスタのアドレスに依って識別される。例えば、タスク・レジスタ１ はRAM 13のアドレス１に位置するタスク・レジスタである。タスク・レジスタ１ に於いて、前のフィールドは、アドレスＤ、ヘッダー・レジスタのアドレスを含 んでいて、次のフィールドは、アドレス２、待ち行列Ｄ23の次のタスク・レジス タのアドレスを含んでいる。タスク・レジスタ９に於いて、前のフィールドは、 アドレス８、待ち行列で先行するタスク・レジスタのアドレスを含んでいて、次 のフィールドは、アドレスＤ、ヘッダー・レジスタのアドレスを含んでいる。確 認すると、タスク・レジスタ２と３と４と５と６と７と８は、各々、待ち行列に 於いて先行するタスク・レジスタのアドレスを含んでいる其れらの前のフィール ドと、待ち行列に於いて後続するタスク・レジスタのアドレスを含んでいる其れ らの次のフィールドを備えている。待ち行列Ｄ23のヘッダー・レジスタと、タス ク・レジスタ１〜９は、従って、待ち行列Ｄ23から相互に連結される。 オペレーティング・システムは、タスクを受け取る時に、アドレスが空の待ち 行列の次のフィールドに記憶されるタスク・レジスタに其のタスクを記憶して、 そのレジスタを待ち行列Ｄ23から待ち行列Ａ20に移動すると想定する。オペレー ティング・システムはタスクＡ１を処理のために受け取ると想定する。前述の動 作を実行するために、オペレーティング・システムは、最初にタスクＡ１をタス ク・レジスタ１に記憶し、次にタスク・レジスタ１を待ち行列Ｄ23から取り出す ルーチンＡを実施する。タスク・レジスタ１はルーチンＡとＢで引用される今の レジスタになる。ルーチンＢは、順にステップ１と２と５と６と７と８を実施す ることに依って、タスク・レジスタ１を待ち行列Ａ20に挿入するために次に実施 される。この手順の結果が図３Ｂに図示されていて、そこでは、タスクＡ１を含 んでいるタスク・レジスタ１が待ち行列Ａ20に位置し、全ての他のタスク・レジ スタは待ち行列Ｄ23に残されている。待ち行列Ｄ23の次のフィールドは、いま、 タスク・レジスタ１より、むしろタスク・レジスタ２を示していることに注目す べきである。 図３Ｃを見ると、システムは、待ち行列Ａ20に移動される待ち行 列Ｄ23のタスク・レジスタ２にここで記憶されるタスクＡ２を次に受け取ると想 定している。タスクＡ２がタスク・レジスタ２にロードされた後に、タスク・レ ジスタ２は待ち行列ＤからルーチンＡに依って取り出される。ルーチンＢは、ス テップ１と２と３と４と２と５と６と７と８を実施して、レジスタ２を待ち行列 Ａ20に次に挿入する。この手順の結果が図３Ｃに図示されている。 図３Ｄを見ると、システムは、待ち行列Ｄ23のレジスタ３に記憶されているタ スクＡ３を次に受け取り且つレジスタ３は待ち行列Ｄ23から待ち行列Ａ20に移動 されることを想定している。ルーチンＡはレジスタ３を待ち行列Ｄ23から取り出 すために実施される。ルーチンＢは、ステップ１と２と３と４と２と３と４と２ と５と６と７と８を順に実施して、レジスタ３を待ち行列Ａ20の内部に挿入する 。この手順の結果が図３Ｄに図示されている。 要約すると、ここで、待ち行列Ａ20はヘッダー・レジスタＡとタスク・レジス タ１と２と３から構成し、待ち行列Ｂ21はヘッダー・レジスタＢから構成し、待 ち行列Ｃ22はヘッダー・レジスタＣから構成し、待ち行列Ｄ23はヘッダー・レジ スタＤとタスク・レジスタ４と５と６と７と８と９から構成している。 図３Ｅを見ると、システムは、タスクＡ１は更なる処理のために待ち行列Ａ20 から待ち行列Ｂ21に移動されることを次に決定すると想定している。タスクＡ１ はタスク・レジスタ１に記憶されているので、ルーチンＡはタスク・レジスタ１ を待ち行列Ａ20から取り出すために実施される。ルーチンＢは、順にステップ１ と２と５と６と７と８を実施して、タスク・レジスタ１を待ち行列Ｂ21に挿入す るために実施される。 図３Ｆを見ると、オペレーティング・システムは、待ち行列Ａ20に挿入される 待ち行列Ｄ23のタスク・レジスタ４に記憶されている タスクＡ４を次に受け取ることを想定している。ルーチンＡはタスク・レジスタ ４を待ち行列Ｄ23から取り出すために実施される。ルーチンＢは、順にステップ １と２と３と４と２と３と４と２と５と６と７と８を実施して、タスク・レジス タ４を待ち行列Ａ20に挿入するために実施される。この手順の結果が図３Ｆに図 示されている。 要約すると、待ち行列Ａ20は、いま、ヘッダー・レジスタＡとタスク・レジス タ２と３と４を含んでいて、待ち行列Ｂ21はヘッダー・レジスタＢとタスク・レ ジスタ１を含んでいて、待ち行列Ｃ22はヘッダー・レジスタＣを含んでいて、待 ち行列Ｄ23はヘッダー・レジスタＤとタスク・レジスタ５と６と７と８と９から 構成している。 図３Ｇを見ると、オペレーティング・システムは、タスクＡ３が待ち行列Ａ20 から待ち行列Ｃ22に移動されることを決定すると次に想定している。タスクＡ３ はタスク・レジスタ３に記憶されているので、ルーチンＡはタスク・レジスタ３ を待ち行列Ａ20から取り出すために実施される。ルーチンＣは、順にステップ１ と２と３と４と５を実施して、タスク・レジスタ３を待ち行列Ｃ22に挿入するた めに実施される。この手順の結果が図３Ｇに図示されている。 図３Ｈを見ると、タスクＡ５とＡ６とＡ７はシステムで処理されるシステムに 依る其の順序で受け取られることを次に想定している。これらのタスクはタスク ・レジスタ５と６と７で挿入される。タスク・レジスタ５と６と７は待ち行列Ｄ 23から待ち行列Ａ20に移動される。これらの動作の各々が、これらのタスクの各 々に相応してルーチンＡとルーチンＢを実施する動作を含んでいる。これらの手 順の結果が図３Ｈに図示されている。 要約すると、この時に、待ち行列Ａ20はヘッダー・レジスタＡと タスク・レジスタ２と４と５と６と７から構成し、待ち行列Ｂ21はヘッダー・レ ジスタＢとタスク・レジスタ１から構成し、待ち行列Ｃ22はヘッダー・レジスタ Ｃとタスク・レジスタ３から構成し、待ち行列Ｄ23はヘッダー・レジスタＤとタ スク・レジスタ８と９から構成している。 図３Ｉを見ると、オペレーティング・システムは、タスクＡ５が待ち行列Ａ20 から待ち行列Ｃ22に移動されることを決定すると想定している。タスクＡ５はタ スク・レジスタ５にあるので、ルーチンＡはタスク・レジスタ５を待ち行列Ａ20 から取り出すために実施される。ルーチンＣは、順にステップ１と２と３と４と ５を実施して、タスク・レジスタ５を待ち行列Ｃ22に挿入するために実施される 。この動作の結果が図３Ｉに図示されている。 図３Ｊを見ると、オペレーティング・システムは、タスクＡ２が処理のために 待ち行列Ａ20から待ち行列Ｃ22に移動されることを決定すると次に想定している 。タスクＡ２はタスク・レジスタ２に位置しているので、ルーチンＡはタスク・ レジスタ２を待ち行列Ａ20から取り出すために実施される。ルーチンＣは、順に ステップ１と２と３と４と５を実施して、タスク・レジスタ５を待ち行列Ｃ22に 挿入するために実施される。この手順の結果が図３Ｊに図示されている。 この時に、待ち行列Ａ20はヘッダー・レジスタＡとタスク・レジスタ４と６と ７から構成し、待ち行列Ｂ21はヘッダー・レジスタＢとタスク・レジスタ１から 構成し、待ち行列Ｃ22はヘッダー・レジスタＣとタスク・レジスタ３と５と２か ら構成し、待ち行列Ｄ23はヘッダー・レジスタＤとタスク・レジスタ８と９から 構成している。 図３Ｋを見ると、タスクＡ１が終了したことを次に決定したシス テムは、タスクＡ１を記憶している、タスク・レジスタＡ１を待ち行列Ａ20から 待ち行列Ｄ23に戻す。ルーチンＡはタスク・レジスタ１を待ち行列Ａ20から取り 出すために実施される。ルーチンＢは、順にステップ１と２と３と５と６と７と ８を実施して、タスク・レジスタを待ち行列Ｄ23に挿入するために実施される。 この手順の結果が図３Ｋに図示されている。 図３Ｌを見ると、オペレーティング・システムは、待ち行列Ａ20に挿入される 待ち行列Ｄ23のタスク・レジスタ１に記憶されているタスク８を受け取ることを 想定している。タスクＡ８がタスク・レジスタ１に記憶された後に、ルーチンＡ はタスク・レジスタ１を待ち行列Ｄ23から取り出すために実施される。ルーチン Ｂは、順にステップ１と２と３と５と６と７と８を実施して、タスク・レジスタ １を待ち行列Ａ20に挿入するために実施される。この手順の結果が図３Ｌに図示 されている。 要約すると、この時に、待ち行列Ａ20はヘッダー・レジスタＡと、各々タスク ・レジスタ１と４と６と７に記憶されているタスクＡ８とＡ４とＡ６とＡ７を含 んでいて、待ち行列Ｂ21はヘッダー・レジスタＢから構成し、待ち行列Ｃ22はヘ ッダー・レジスタＣと、各々タスク・レジスタ３と５と２に記憶されているタス クＡ３とＡ５とＡ２を含んでいて、待ち行列Ｄ23はヘッダー・レジスタＤとタス ク・レジスタ８と９から構成している。 今までの論述では、待ち行列システムの動作と、待ち行列システムが設計者の ニーズを満足するために設計者に依って汎用化できる方式について述べられてき た。待ち行列システムはメモリ場所をランダム・アクセス・メモリの内部に用い て説明されてきたが、専用ハードウェア・レジスタがランダム・アクセス・メモ リの代わりに使用できることも理解されるべきである。 待ち行列間のタスクの移動は、タスク・レジスタを待ち行列から取り出し且つ 挿入することに依って影響を受けるレジスタの前と次のフィールドの修正だけ必 要としていたことが容易に認めることができる。タスクを含んでいるタスク・レ ジスタが待ち行列間で効果的に移動された時に、タスク・レジスタ内部に記憶さ れていたタスクに関連する実際のデータを移動する必要は常にない。前述のよう に、待ち行列システムは、各々疑似待ち行列がヘッダー・レジスタと１つまたは 複数のタスク・レジスタから構成され且つ各々タスク・レジスタが待ち行列シス テムの待ち行列に常に指定される、疑似待ち行列を形成するためにレジスタを割 り振りしていた。最終的な待ち行列システムは、設計者に依って汎用化されるの で容易に使用できて、システムの要求が変わると簡単に変更できて修正できるも のになる。 図４と５と６のルーチンは、周知のデジタル・ソフトウェア方式を用いてマイ クロコードで具体的に作成され、Motorolla 68C11 Assembler，Series 5.0を用 いてアセンブルされていた。マイクロプログラムは、付録Ａに詳細に説明されて おり、且つ図４と５（タスク・レジスタ順序設定でないが更なるフィールド順序 設定に依って行われる）と６に図示される流れ図のルーチンの機能を実行する。 この方法は、他のプログラム設定可能言語を用いる他のマイクロプログラムで実 現できるが、またはコンピュータ・システム内部の読取専用メモリにも記憶でき ることが理解されるべきである。プロセッサ10の機能は、ここで説明されたルー チンを実行するために必要な機能を実施するために専用化されたハードウェア・ ステート・マシンを用いて実現できる。 発明は好まれる実施例を参照しながら特に図示され説明されてきたが、当業者 は、形式的で細部の変更は発明の精神と範囲を逸脱せ ずに其こに実施できることを理解すると思われる。前述の一般的な概念と特殊な 実施例の開示が与えられたので、要求される保護の範囲は次に示す特許請求の範 囲に依って定められる。

【手続補正書】特許法第１８４条の７第１項 【提出日】１９９４年６月２８日 【補正内容】 訂正された請求項 「1994年６月28日に国際局に依って受理された；原請求項４は削除された；原請 求項１と２と３と５と９が訂正された；原請求項６〜８は変更されない；請求項 は１〜８として再び番号が付記された（３頁）」 請求の範囲 １．待ち行列システムであって、 複数の待ち行列であって、 前記の複数の待ち行列の各々待ち行列は独自のヘッダー・レジスタ・アドレス を有するヘッダー・レジスタをを有していて且つ前記のヘッダー・レジスタは前 のフィールドと次のフィールドを含んでいて、且つ前記の前のフィールドと前記 の次のフィールドは前記のヘッダー・レジスタの前記のヘッダー・レジスタ・ア ドレスまたはタスク・レジスタ・アドレスの何れかを記憶する、前記の複数の待 ち行列と、 複数のタスク・レジスタであって、各々前記のタスク・レジスタは独自の前記 のタスク・レジスタ・アドレスを有していて且つ前のフィールドと次のフィール ドを含んでいて、各々前記の前のフィールドと前記の次のフィールドは前記の複 数の前記の待ち行列の前記の待ち行列の１つに対して前記のヘッダー・レジスタ ・アドレスを或いは前記の複数のタスク・レジスタの前記のタスク・レジスタの 別の１つに対して前記のタスク・レジスタ・アドレスを記憶する、前記の複数の タスク・レジスタと、 前記のタスク・レジスタの各々が前記の複数の待ち行列の１つに常に位置する ように且つ前記のタスク・レジスタを物理的に移動せ ずに待ち行列間で前記のタスク・レジスタを効果的に移動できるように、前記の ヘッダー・レジスタの各々とタスク・レジスタの各々に於いて前記の前のフィー ルドと次のフィールドに記憶されているアドレスを制御することに依って、各々 前記のタスク・レジスタを動的に指定し転送し維持する制御手段を搭載する、前 記の待ち行列システム。 ２．前記の制御手段は、前記のヘッダー・レジスタを有する前記の複数の待ち 行列の前記の待ち行列が前記の制御手段に依って前記の待ち行列に指定された前 記のタスク・レジスタを有していない時に、前記のヘッダー・レジスタの前記の 次のフィールドと前記の前のフィールドに於ける前記のヘッダー・レジスタのた めに前記のヘッダー・レジスタ・アドレスを記憶する、特許請求の範囲第１項に 記載の待ち行列システム。 ３．前記の制御手段は、前記の待ち行列の他のタスク・レジスタが下位の前記 のタスク・レジスタ・アドレスを有していない場合に前記の待ち行列に対して前 記の待ち行列の前記のタスク・レジスタの次の下位のタスク・レジスタ・アドレ スを有するタスク・レジスタのタスク・レジスタ・アドレスまたは前記のヘッダ ー・レジスタ・アドレスを前記の待ち行列の前記のタスク・レジスタの各々の前 記の前のフィールドに記憶することに依って、および前記の待ち行列の他のタス ク・レジスタが上位の前記のタスク・レジスタ・アドレスを有していない場合に 前記の待ち行列に対して前記の待ち行列の前記のタスク・レジスタの次の最上位 のタスク・レジスタ・アドレスを有するタスク・レジスタのタスク・レジスタ・ アドレスまたは前記のヘッダー・レジスタ・アドレスを前記の待ち行列の前記の タスク・レジスタの各々の前記の次のフィールドに記憶するために、および前記 の待ち行列に対してヘッダー・レジスタの次のフィー ルドに最下位のタスク・レジスタ・アドレスを有する前記の待ち行列の前記のタ スク・レジスタのタスク・レジスタ・アドレスを記憶することに依って、および 前記の待ち行列に対して前記のヘッダー・レジスタの前のフィールドに前記の待 ち行列の最上位のタスク・レジスタ・アドレスを有する前記の待ち行列の前記の タスク・レジスタのタスク・レジスタ・アドレスを記憶するために、前記の複数 の待ち行列の待ち行列の前記のタスク・レジスタを順序設定する、特許請求の範 囲第１項に記載の待ち行列システム。 ４．前記の制御手段は、 前記のタスク・レジスタの１つを前記の複数の待ち行列の前記の待ち行列の１ つから取り出す削除手段と、 前記の削除手段に依って前記の待ち行列から取り除かれた前記のタスク・レジ スタの前記の１つを前記の複数の待ち行列の別の１つに挿入する挿入手段を更に 搭載している、特許請求の範囲第３項に記載の待ち行列システム。 ５．前記の挿入手段は、前記の待ち行列の前記のタスク・レジスタを、前記の 待ち行列の最後のタスク・レジスタとして挿入する第１の手段を含んでいる、特 許請求の範囲第４項に記載の待ち行列システム。 ６．前記の挿入手段は、前記の待ち行列の前記のタスク・レジスタを、前記の 待ち行列に挿入される前記のタスク・レジスタのアドレスのファンクションとし て挿入する第２の手段を含んでいる、特許請求の範囲第４項に記載の待ち行列シ ステム。 ７．前記の待ち行列システムの前記の待ち行列の１つは、空の待ち行列であり 、前記の待ち行列システムの内部で別の待ち行列に置かれないタスク・レジスタ を含んでいるので、常に各々タスク・レジスタは前記の待ち行列システムの待ち 行列に置かれることを保証 する、特許請求の範囲第１項に記載の待ち行列システム。 ８．前記の制御手段は、前記の待ち行列システムの内部に於いて第１の待ち行 列と第２の待ち行列の間でタスク・レジスタを、最初に前記の削除手段を作動し て前記のタスク・レジスタを前記の第１の待ち行列から取り出し、次に前記の取 り出されたタスク・レジスタを前記の第２の待ち行列に挿入するために前記の挿 入手段の前記の第１または第２の手段を作動することに依って効果的に移動する 、特許請求の範囲第４項に記載の待ち行列システム。 【手続補正書】特許法第１８４条の８ 【提出日】１９９５年１月１７日 【補正内容】 請求の範囲 １．待ち行列システムであって、 複数の待ち行列であって、 前記の複数の待ち行列の各々待ち行列は独自のヘッダー・レジスタ・アドレス を有するヘッダー・レジスタをを有していて且つ前記のヘッダー・レジスタは前 のフィールドと次のフィールドを含んでいて、且つ前記の前のフィールドと前記 の次のフィールドは前記のヘッダー・レジスタの前記のヘッダー・レジスタ・ア ドレスまたはタスク・レジスタ・アドレスの何れかを記憶する、前記の複数の待 ち行列と、 複数のタスク・レジスタであって、各々前記のタスク・レジスタは独自の前記 のタスク・レジスタ・アドレスを有していて且つ前のフィールドと次のフィール ドを含んでいて、各々前記の前のフィールドと前記の次のフィールドは前記の複 数の前記の待ち行列の前記の待ち行列の１つに対して前記のヘッダー・レジスタ ・アドレスを或いは前記の複数のタスク・レジスタの前記のタスク・レジスタの 別の１つに対して前記のタスク・レジスタ・アドレスを記憶する、前記の複数の タスク・レジスタと、 前記のタスク・レジスタの各々が前記の複数の待ち行列の１つに常に位置する ように且つ前記のタスク・レジスタを物理的に移動せずに待ち行列間で前記のタ スク・レジスタを効果的に移動できるように、前記のヘッダー・レジスタの各々 とタスク・レジスタの各々に於いて前記の前のフィールドと次のフィールドに記 憶されているアドレスを制御することに依って、各々前記のタスク・レジスタを 動的に指定し転送し維持する制御手段を搭載し、 前記の制御手段は、前記の待ち行列の他のタスク・レジスタが下 位の前記のタスク・レジスタ・アドレスを有していない場合に前記の待ち行列に 対して前記の待ち行列の前記のタスク・レジスタの次の下位のタスク・レジスタ ・アドレスを有するタスク・レジスタのタスク・レジスタ・アドレスまたは前記 のヘッダー・レジスタ・アドレスを前記の待ち行列の前記のタスク・レジスタの 各々の前記の前のフィールドに記憶することに依って、および前記の待ち行列の 他のタスク・レジスタが上位の前記のタスク・レジスタ・アドレスを有していな い場合に前記の待ち行列に対して前記の待ち行列の前記のタスク・レジスタの次 の最上位のタスク・レジスタ・アドレスを有するタスク・レジスタのタスク・レ ジスタ・アドレスまたは前記のヘッダー・レジスタ・アドレスを前記の待ち行列 の前記のタスク・レジスタの各々の前記の次のフィールドに記憶するために、お よび前記の待ち行列に対してヘッダー・レジスタの次のフィールドに最下位のタ スク・レジスタ・アドレスを有する前記の待ち行列の前記のタスク・レジスタの タスク・レジスタ・アドレスを記憶することに依って、および前記の待ち行列に 対して前記のへッダー・レジスタの前のフィールドに前記の待ち行列の最上位の タスク・レジスタ・アドレスを有する前記の待ち行列の前記のタスク・レジスタ のタスク・レジスタ・アドレスを記憶するために、前記の複数の待ち行列の待ち 行列の前記のタスク・レジスタを順序設定する、請求の範囲第１項に記載の待ち 行列システム。 ２．前記のヘッダー・レジスタを有する前記の複数の待ち行列の前記の待ち行 列が、前記の制御手段によって前記の待ち行列に指定された前記のタスク・レジ スタを有していない時に、前記の制御手段は、前記のヘッダー・レジスタの前記 の次のフィールドと前記の前のフィールドにおける該ヘッダー・レジスタ用の該 ヘッダー・レジスタのアドレスを記憶するものである、請求項１記載の待ち行列 システム。 ３．前記の制御手段は、 前記のタスク・レジスタの１つを、前記の複数の待ち行列の中の該待ち行列の １つから除去する削除手段；および 該削除手段により前記待ち行列から除去された前記タスク・レジスタの前記の １つを、前記複数の待ち行列の別の１つに挿入する挿入手段； とを更に具備するものである、請求項１記載の待ち行列システム。 ４．前記挿入手段は、前記の待ち行列の前記のタスク・レジスタを、該待ち行 列の最後のタスク・レジスタとして挿入する第１の手段を具備するものである、 請求項３記載の待ち行列システム。 ５．前記の挿入手段は、該待ち行列の前記タスク・レジスタを、該待ち行列に 挿入されている該タスク・レジスタのアドレスの関数として挿入する第２の手段 を具備するものである、請求項３記載の待ち行列システム。 ６．前記待ち行列システムにおける該待ち行列の１つは、空の待ち行列であり 、かつ該待ち行列システムの内部で別の待ち行列に設置されない該タスク・レジ スタを具備するので、それにより常に各々タスク・レジスタが該待ち行列システ ムの待ち行列内に設置されることを保証するものである請求項３記載の待ち行列 システム。 ７．前記の制御手段は、前記の待ち行列システムの内部において、第１の待ち 行列と第２の待ち行列の間でタスク・レジスタを、最初に前記除去手段を作動せ しめて該タスク・レジスタを該第１の待ち行列から除去し、次に前記の除去され たタスク・レジスタを該第２の待ち行列に挿入するために、前記の挿入手段の前 記の第１又は第２の手段を作動せしめることにより、効果的に移動せしめ、請求 項３記載の待ち行列システム。

Claims (1)

1. 【特許請求の範囲】 １．待ち行列システムにおいて、 複数の待ち行列であって、該待ち行列は、 複数のヘッダー・レジスタであって、各々前記のヘッダー・レジスタは前記待 ち行列の１つに独自に関連していて、各々前記のヘッダー・レジスタは独自のア ドレスを有し、且つ前のフィールドと次のフィールドを備えているもの； 複数のタスク・レジスタであって、各々前記のタスク・レジスタは独自のアド レスを有し、且つ前のフィールドと次のフィールドを備えており、ここにおいて 前記の前のフィールドと前記の次のフィールドはヘッダー・レジスタ・アドレス またはタスク・レジスタ・アドレスを夫々記憶するもの； とから構成される複数の待ち行列；および 前記のタスク・レジスタの各々が、常に前記の待ち行列の１つに相応している ので、前記のタスク・レジスタを物理的に移動せずに待ち行列間で該タスク・レ ジスタを効果的に移動できるように、前記のヘッダー・レジスタとタスク・レジ スタの各々に於いて前記の前のフィールドと次のフィールドに記憶されているア ドレスを制御することに依って、該タスク・レジスタを該待ち行列に動的に指定 するための制御手段； とを具備することを特徴とする待ち行列システム。 ２．前記の待ち行列のための前記のヘッダー・レジスタの前記の次のフィール ドと前記の前のフィールドは、前記のタスク・レジスタが前記の制御手段に依っ て前記の待ち行列に指定されていない時に、前記の待ち行列のための前記のヘッ ダー・レジスタのアドレスを記憶する、請求の範囲第１項に記載の待ち行列シス テム。 ３．前記のタスク・レジスタの前記の前のフィールドは前記のタスク・レジス タを含んでいる前記の待ち行列に於いて前記のタスク・レジスタの直前のレジス タのアドレスを記憶し、前記のタスク・レジスタの前記の次のフィールドは前記 のタスク・レジスタを含んでいる前記の待ち行列に於いて前記のタスク・レジス タの直後のレジスタのアドレスを含んでいる、請求の範囲第１項に記載の待ち行 列システム。 ４．各々前記の待ち行列のレジスタの次のフィールドに記憶されているアドレ スの順序は待ち行列に於いてヘッダー・レジスタから最後のタスク・レジスタに 向かう方向で連続するループを形成し、前記の待ち行列のレジスタの前のフィー ルドに記憶されているアドレスの順序は待ち行列に於いて最後のタスク・レジス タからヘッダー・レジスタに向かう方向で連続するループを形成する、請求の範 囲第３項に記載の待ち行列システム。 ５．前記の制御手段は、 タスク・レジスタを待ち行列から取り出す削除手段と、 タスク・レジスタを待ち行列に挿入する挿入手段を更に搭載している、請求の 範囲第１項に記載の待ち行列システム。 ６．前記の挿入手段は、前記の待ち行列の前記のタスクを、前記の待ち行列の 最後のタスク・レジスタとして挿入する第１の手段を含んでいる、請求の範囲第 ５項に記載の待ち行列システム。 ７．前記の挿入手段は、前記の待ち行列の前記のタスク・レジスタを、前記の 待ち行列に挿入される前記のタスク・レジスタのアドレスのファンクションとし て挿入する第２の手段を含んでいる、請求の範囲第５項に記載の待ち行列システ ム。 ８．前記の待ち行列システムの前記の待ち行列の１つは、空の待ち行列であり 、前記の待ち行列システムの内部で別の待ち行列に置 かれないタスク・レジスタを含んでいるので、常に各々タスク・レジスタは前記 の待ち行列システムの待ち行列に置かれることを保証する、請求の範囲第１項に 記載の待ち行列システム。 ９．前記の制御手段は、前記の待ち行列システムの内部に於いて第１の待ち行 列と第２の待ち行列の間でタスク・レジスタを、最初に前記の削除手段を作動し て前記のタスク・レジスタを前記の第１の待ち行列から取り出し、次に前記の取 り出されたタスク・レジスタを前記の第２の待ち行列に挿入するために前記の挿 入手段の前記の第１または第２の手段を作動することに依って効果的に移動する 、請求の範囲第１項に記載の待ち行列システム。