JPH0570177B2 - - Google Patents

Description

【発明の詳細な説明】 Ａ 産業上の利用分野 本発明は一般的にはデータ処理アーキテクチヤ
に関し、さらに詳しくいえば、データ待ち行列の
アーキテクチヤに関する。

Ｂ 従来技術及びその問題点 多くのデータ処理アプリケーシヨンにおいて
は、データはその操作についての固有の優先度な
いし優先順位と関連付けられている。たとえば、
ネツトワークに接続されている複数のノードが共
通資源へのアクセスについて競合しなければなら
ないようなローカル・エリア・ネツトワークの競
合解決において、データ伝送の要件がネツトワー
クの全体的な動作にとつて固有的により重要であ
るようなノードに好適なサービスを提供すること
は意味のあることである。典型的には、従来技術
はノードによつて処理される幾つかのセツシヨン
を指定する記述子を優先式待ち行列に優先順位を
もつて記憶していた。各々の新しいセツシヨン及
び関連する優先順位がノードに割り当てられるの
で、そのセツシヨンはそのノードで既存のセツシ
ヨンの優先順位に対する優先順位でもつて編成し
なければならない。従来、これは複数の既存のセ
ツシヨンを表わす優先順位付けされた待ち行列の
内容を調べてその優先度に応じてランク付けされ
る位置で新しいセツシヨンの記述子をその待ち行
列に書き込むことによつて行なわれていた。した
がつて、ノードにおいて新しいセツシヨンの記述
子を優先式待ち行列に書き込んだ後、待ち行列は
新しく割り当てられた優先順位で再編成されるこ
ととなる。新しいセツシヨンについての割当ての
発生は時間的にランダムなので、このような動作
モードには問題が生じる。優先式待ち行列に記録
すべき新しい事象またはセツシヨンが非同期的に
発生することから、従来の優先式待ち行列のメカ
ニズムでは待ち行列での新しいデータのエントリ
に短時間でしかも繰り返して応答することは困難
となる。というのは、各エントリは優先式待ち行
列における既存のエレメントの優先順位に対する
新しいエレメントの相対的な優先順位に関する割
当てを必要とするからである。

優先式待ち行列が用いられるようなデータ処理
アプリケーシヨンは他にもある。たとえば、多重
プログラミング・アプリケーシヨンである。多重
プログラミング式コンピユータ・アーキテクチヤ
の１つのタイプは複数のプログラムが各プログラ
ムの実行についてタイム・スライス・オペレーシ
ヨンを課することによつて単一資源CPUで実行
されるような作業ステツプ・アーキテクチヤであ
る。時間は複数の期間に分けられて、CPUの実
行すべき複数のプログラムの各々には実行のため
の相対的な優先順位が割り当てられる。タイム・
スライスされた各期間の始まりで、各プログラム
の優先度が調べられ、最高の優先順位を有するプ
ログラムがそのタイム・スライスされた期間中、
実行のために選択される。プログラムまたはサブ
ルーチンが事象駆動方式に基づいて割り当てられ
るような場合、実行すべきプログラムを表わす優
先式待ち行列の増加は多重プログラミング・プロ
セスのタイム・スライス・オペレーシヨンと非同
期的であるようなやり方で行なわれなければなら
ない。次のサイクルの実行のためにどのプログラ
ムが最高の優先順位を有するのかを追跡する優先
式待ち行列が、新しいプログラムまたはサブルー
チンがその待ち行列に対して割り当てられた優先
順位を有するたびごとに再編成されなければなら
ないとすれば、優先式待ち行列への新しいプログ
ラムの割当てに関する高速の繰返しは不可能とな
り、同時に、次のサイクルの実行のため正確に識
別された最高優先順位のプログラムを利用するこ
ともできない。したがつて、本発明の目的は従来
に比してより効率的な方法で優先式待ち行列を管
理することである。

本発明の他の目的は従来に比してより高速に優
先式待ち行列を管理することである。

本発明の他の目的は優先式待ち行列への新しい
エレメントの非同期的な割当てを従来に比してよ
り高速にできるようにすることである。

本発明の他の目的は優先式待ち行列の先頭のエ
レメントをより改善された方法ですぐに利用でき
るようにすることである。

Ｃ 問題点を解決するための手段 この目的を達成するため、データ処理システム
において優先式待ち行列を管理する本発明の方法
は、(a)最高優先順位のデータの要求に応答してデ
ータ部分及び優先順位部分を有する保持レジスタ
の内容を読み取るスキツプと、(b)各々優先順位部
分及びデータ部分を有するスタツク内の複数のエ
レメントのうちスタツク先頭ポインタによつて指
示される先頭のエレメントを読み取つてその内容
を上記保持レジスタに書き込むステツプと、(c)初
期的に上記スタツク先頭ポインタと等しくセツト
されているスタツク探索ポインタによつて指示さ
れるスタツク内の最初のエントリを見つけること
によつてスタツク内の複数のエレメントを探索し
て上記スタツク探索ポインタによつて指示される
エントリの内容と上記保持レジスタの内容とを比
較するステツプと、(d)上記スタツク内のエントリ
の内容の優先順位部分が上記保持レジスタの内容
の優先順位部分よりも高いものである損合に上記
スタツク探索ポインタによつて指示される上記ス
タツク内のエントリの内容と上記保持レジスタの
内容とをスワツプするステツプと、(e)新しいデー
タが上記スタツクに書き込まれるかどうかを判断
するステツプと、(f)上記新しいデータの優先順位
部分が上記保持レジスタの内容の優先順位部分よ
りも高いものであるかどうかを判断するため上記
スタツクに書き込むべき新しいデータを比較する
ステツプと、(g)上記新しいデータの優先順位部分
が上記保持レジスタの内容の優先順位部分よりも
高いものである場合に上記スタツク先頭ポインタ
の内容を増分して上記保持レジスタの内容を上記
スタツク先頭ポインタによつて新たに指示される
上記スタツク内のロケーシヨンに書き込み、さら
に上記新しいデータを上記保持レジスタに書き込
むステツプと、(h)上記新しいデータの優先順位部
分が上記保持レジスタの内容の優先順位部分より
も高くない場合に上記新しいデータを上記スタツ
クに書き込むステツプと、(i) 上記スタツク内の
すべてのエントリの比較が完了するまで上記ス
テツプ(c)以降のステツプを繰り返すステツプ
と、を含むことにより最高優先順位のエントリ
が上記保持レジスタに記憶されるようにしたこ
とを特徴としている。

以下、本発明の作用を実施例と共に説明する。

Ｄ 実施例 はじめに本発明の実施例を概説する。本発明に
従つて、優先式待ち行列の処理において、それら
のエレメントが未記憶のスタツク内に保存され、
最高優先順位のエレメントがその保持レジスタか
ら読み取られた後にのみ次に高い優先順位を有す
るエレメントについてこれらのエレメントが探索
される。本発明はこれを実行することができる。
というのは、新しいエレメントがこの待ち行列に
書き込まれるたびに、新しいエレメントの優先度
と保持レジスタに存する既存のエレメントの優先
度との比較が行なわれるからである。新しいエレ
メントの方が高い優先度を有するときは、保持レ
ジスタに存する既存のエレメントはスタツクの先
頭に書き込まれる。一方、保持レジスタ中のエレ
メントの方が高い優先度を有するときは、新しい
エレメントがスタツクの先頭に書き込まれる。し
たがつて、保持レジスタが最高優先順位を有する
エレメントを常に保有することが保証される。そ
の結果、保持レジスタの内容を読み取ることによ
る優先式待ち行列の読取りは、最高優先順位のエ
レメントがそこに存在しかつ待ち行列のさらなる
探索なしにすぐにこれをアクセスできることを保
証する。前述のごとく、探索オペレーシヨンが関
与するのは、保持レジスタの内容を読み取つた後
だけである。高速の読取りオペレーシヨンを提供
するため、はじめにスタツクの先頭のエレメント
を保持レジスタに入れる。次に、優先順位探索オ
ペレーシヨンが、優先式待ち行列の残りの各エレ
メントが保持レジスタの内容の優先順位と比較さ
れる優先順位を持つように実行される。保持レジ
スタ中のエレメントの優先順位が優先式待ち行列
に存するエレメントの優先順位より低いときは、
必ずスワツプ・オペレーシヨンが行なわれる。探
索オペレーシヨンが、スタツクの後尾まで行なわ
れるところまでには、保持レジスタは最高優先順
位を有する待ち行列エレメントを含む。

以下、図面を参照して実施例を詳細に説明す
る。

本発明に基づく高速アクセス優先式待ち行列は
優先式待ち行列が読み取られるときについて一定
の規則性が存在するようなデータ処理アプリケー
シヨンにおいて動作する。このことは、第５図に
示すようなローカル・エリア・ネツトワークにつ
いて第４図に示すごときタイミング・フレームで
例示的に示されている。第５図に示すようなロー
カル・エリア・ネツトワークにおいては、、リン
グ１（以下、「通信媒体」または「通信ネツトワ
ーク」ともいう）のごとき中央通信リンクまたは
スター式バスが複数の通信ノード（たとえばノー
ド３とノード３′）を論理的に相互接続する。各
ノードはネツトワーク・インターフエース・ユニ
ツト５（以下、「ネツトワーク・コントローラ」
ともいう）及びローカル装置７を含む。ローカル
装置７は、たとえば、コンピユータ、データ・イ
ンターフエースまたは他のデータ処理通信装置で
ある。多くのLANアプリケーシヨンにおいては、
各ノードは複数の他のノードとの複数の通信セツ
シヨンを管理するためのネツトワーク・コントロ
ーラ５を有する。ネツトワーク・インターフエー
ス・ユニツト５で管理すべき各通信セツシヨンは
各自に割り当てられた関連する優先度の値を有す
る。この値は、そのノード３によつて及びシステ
ム内の他のノード３′によつて管理すべき他の通
信セツシヨンにに対してその通信セツシヨンが有
する固有の相対的な重要度を示すものである。こ
うしたアプリケーシヨンにおいて本発明は特に有
益である。ネツトワークのすべてのノード及びす
べてのセツシヨンに各自の情報を送信する機会を
与えるため、時間が一連のタイム・フレームに分
けられる（第４図参照）。１つのタイム・フレー
ムは同期ヘツダ、肯定応答部分及び競合解決部分
を有する制御部を含む。このフレームは制御部に
続くデータ部を有する。データ部は通信媒体１を
介してシステム内の宛先ノードに伝送される関連
データを有する。典型的には、フレームの制御部
はたとえば40マイクロ秒であり、フレームのデー
タ部はたとえば40マイクロ秒から400マイクロ秒
までの可変の期間である。あるノードが第４図の
タイム・フレームの制御部の競合解決部分で対象
となりうるセツシヨンを選択するためには、ネツ
トワーク・インターフエース・ユニツト５が優先
式待ち行列を保持しなければならない。優先式待
ち行列は２つの部分を有するエントリを含む第３
図に示すような１つのスタツクを保有する。第３
図のスタツク内の１つのエントリの第１の部分は
そのエントリについての優先度の値であり、競合
解決部分の間に他のセツシヨンについての他の優
先度の値と比較すべき優先度の値である。第３図
のスタツク内のエントリの優先順位部分の他に、
この優先順位部分に関連するデータ部分がある。
ここで説明する例においては、このデータ部分は
１つのアドレス・ポインタでもよい。このアドレ
ス・ポインタは、ネツトワーク・インターフエー
ス・ユニツト５に関連して記憶され、選択された
セツシヨンで伝送されるデータを指し示すもので
ある。第３図のスタツク１６へのエントリのデー
タ部分は実際のデータであつてもよい。たとえ
ば、通信ネツトワーク１を介して伝送すべきメツ
セージ・パケツトの実際のデータ部分でもよい。
以上のようなタイプのアプリケーシヨンにおいて
本発明は特に有益である。

第２図は高速アクセス優先式待ち行列のコント
ローラ９のアーキテクチヤを示す図である。この
図からわかるように、待ち行列コントローラ９
は、バス・コントローラ１５及び当該ノードが競
合解決の勝者となつたときに通信ネツトワーク１
に出力されるデータを用いて最高の優先度のセツ
シヨンを選択するためメモリ・マネジメント・プ
ロセツサ１１及びセツシヨン・データRAMに相
互接続される。待ち行列コントローラ９は複数の
エントリを有するスタツク１６を保持する。各エ
ントリはそのエントリの優先順位及び１つのアド
レスポインタを含む。その待ち行列及び機能選択
入力が待ち行列コントローラ９に最高優先順位エ
レメントがスタツクから読み取られかつ出力され
るということを指示すると、その最高優先順位の
エレメントは、バス・コントローラ１５に供給さ
れる優先順位部分及びメモリ・マネジメント・プ
ロセツサ１１に供給されるポインタ部分と共にス
タツクから出力される。メモリ・マネジメント・
プロセツサ１１はポインタ部分を用いて、競合解
決に勝つた場合に通信リンクを介して伝送すべき
セツシヨン・データRAM１３中のデータ・セグ
メントを識別する。バス・コントローラ１５は優
先度の値を用いて通信ネツトワーク１についての
バス競合解決オペレーシヨンに関与する。

第２図に示す待ち行列コントローラ９は第１図
の流れ図で示すプロセスを実行する待ち行列状態
機械を有する。待ち行列状態機械はスタツク先頭
ポインタ１２、スタツク探索ポインタ１４及び
RAM制御（これはスタツク１６に接続されてい
る）への出力を有する。待ち行列ポインタ９はさ
らに保持レジスタ１０、一時レジスタ１８、入力
レジスタ２２及び比較論理２０を含む。

次に動作を説明する。第３図のスタツク１６が
複数のスタツク・エントリを記憶し、その各々が
優先順位部分とデータ部分を含むものと仮定す
る。スタツクの後尾は固定値を有する。たとえば
アドレス値０でもよい。スタツクの先頭はスタツ
ク先頭ポインタ１２の内容（以下、「Imax」とい
う）によつて示される。第４図のタイム・フレー
ムにおいて、制御部の肯定応答部分の終了の際、
たとえば、待ち行列コントローラ９は待ち行列及
び機能選択入力ラインを介して、最高優先順位の
エントリがスタツク１６からアクセスされること
を要求する１つの入力を受け取る。このとき、第
１図の流れ図において、現に最高優先順位のエン
トリを含む保持レジスタ１０が読み取られ、その
値がコントローラのＩ／Ｏドライバから出力され
データ・バスを介してバス・コントローラ１５及
びメモリ・マネジメント・プロセツサ１１に供給
される。そうして第１図の流れ図に示すように、
スタツク先頭ポインタ１２によつて指示されるス
タツクの先頭のところにあるスタツクの内容が読
み取られる。その値が保持レジスタ１０に新たに
書き込まれるエントリの値である。このとき、ス
タツク先頭ポインタ１２の値は１単位だけ減分さ
れ、それはスタツクの先頭が次の下位アドレス値
のところにあることを示す。

保持レジスタ１０の内容は本発明に従つて待ち
行列コントローラ９からのアクセスのためにすぐ
に利用できる。こうして待ち行列コントローラ９
はタイム・フレームの肯定応答部分の終了により
待ち行列及び機能選択要求に対してすぐに応答で
きたので、待ち行列コントローラ９は次のタイ
ム・フレームの次の制御部が発生するまで、待ち
時間を有する。スタツク１６を探索して最高優先
順位のエレメントを識別してこれを保持レジスタ
１０に置くのは、この待ち時間の間である。これ
は第１図の流れ図に示される１つのループによつ
て遂行される。このループは、スタツク先頭ポイ
ンタ１２と同じ内容を有することでスタツクの先
頭を指示するスタツク探索ポインタ１４によつて
スタツク１６を順次的に探索することから始ま
る。スタツク探索ポインタ１４によつて指示され
るエントリのうちの優先順位部分の内容は保持レ
ジスタ１０に記憶されたエントリの優先順位の値
と比較される。前者が後者よりも高いものである
ときは、スタツク探索ポインタ１４によつて指示
されるロケーシヨンにあるスタツクの内容と保持
レジスタ１０の内容とをスワツプするためスワツ
プ・オペレーシヨンを行なわなければならない。
これは、スタツク探索ポインタ１４によつて指示
されるエントリの内容を取り出してこれを待ち行
列コントローラ９の一時レジスタ１８に置くこと
によつて行なわれる。次に、保持レジスタ１０の
内容がスタツク探索ポインタ１４によつて指示さ
れるロケーシヨンでスタツクに書き込まれる。そ
うして、一時レジスタ１８の内容が保持レジスタ
１０に書き込まれる。このスワツプ・オペレーシ
ヨンが行なわれると、保持レジスタの内容はスタ
ツク内の任意のエントリについて最高優先順位の
エントリを有する可能性が高い。第１図のループ
が完了し、スタツク内のすべてのエントリについ
ての比較が完了することまでには、保持レジスタ
の内容はスタツク１６内のすべてのエントリが最
高優先順位を有することが保証される。

第１図の流れ図からわかるように、比較論理２
０によつて実行される比較が、スタツク探索ポイ
ンタ１４によつて指示されるスタツク内のエント
リの内容が保持レジスタ１０の内容より高いもの
でないことを示す場合、このプロセスはスタツク
１６に書き込まれるべき新しいエントリが待ち行
列コントローラ９に入力されたかどうかを調べる
ステツプに進む。

上述のスワツプ・オペレーシヨンが終了した場
合もこのステツプに進む。第１図に示すごとく、
入力レジスタ２２は任意の新しいデータをスタツ
クに加える準備が完了しているかどうかについて
判断される。入力レジスタ２２が優先順位部分及
びポインタ多分の双方を含む新しいエントリを有
するものと判断された場合は、この新しいエント
リの優先度が保持レジスタ１０に含まれるものよ
りも高いかどうかについての比較オペレーシヨン
を行なわなければならない。こうして、比較論理
２０は入力レジスタ２２の内容の優先順位部分と
保持レジスタ１０の内容の優先順位部分とを比較
して前者が後者よりも高いものであるときは、新
しいデータが保持レジスタ１０に書き込まれる。
これは次のようにして行なわれる。まず、スタツ
ク先頭ポインタ１２の値Imaxが１つだけ増分さ
れる。次に、保持レジスタ１０の内容がスタツク
先頭ポインタ１２によつて指示されるスタツク内
のロケーシヨンに書き込まれる。その後、入力レ
ジスタ２２中の新しいデータは保持レジスタ１０
に書き込まれる。このようにして、保持レジスタ
がスタツク内で任意の値の最高優先順位の値を有
するエントリを含むという可能性が高くなる。

一方、新しいデータが保持レジスタ１０の内容
よりも高いものでない優先順位部分を有するな
ら、この新しいデータはスタツクに書き込まれ
る。これは次のようにして行なわれる。スタツク
先頭ポインタ１２の値Imaxが１つだけ増分され
る。次に、入力レジスタ２２中の新しいデータが
スタツク先頭ポインタ１２によつて指示されるス
タツク内のロケーシヨンに書き込まれる。その
後、この流れ図は“Ｂ”に戻る。ポイント“Ｂ”
は待ち行列コントローラ９への新しいデータの入
力がまつたく存在しなかつた場合に到達するポイ
ントである。ポイント“Ｂ”では、、スタツク全
体についてこの比較プロセスが行なわれたかどう
かについての判断がなされる。スタツク探索ポイ
ンタ１４には変数名Ｉが与えられる。この流れ図
では、Ｉの値がゼロであるかどうかが調べられ
る。これは、スタツクの後尾に到達したか否かを
調べることを意味する。実際にスタツクの後尾に
到達したときは、流れ図はポイント“Ａ”に戻
り、新しいデータを待ち行列コントローラ９に書
き込む準備が完了するまで、またはタイム・フレ
ームの次の制御部が発生するまで待機する。一
方、スタツク探索ポインタ１４のＩの値がゼロで
ないときは、Ｉの値は１つだけ減分され、スタツ
ク１６内の次のエントリが保持レジスタ１０より
も高い優先順位の値を有するかどうかについての
判断を行なうことによりループが継続される。こ
のようにして、ループが完了すると保持レジスタ
１０の内容がスタツク１６の任意のエントリの優
先順位の値よりも高い優先順位の値を有すること
が保証される。保持レジスタ１０の内容は、上述
のLAN優先順位競合解決アプリケーシヨンのよ
うなアプリケーシヨンにとつてすぐに利用可能で
ある。

第６図は作業ステツプ・アーキテクチヤに基づ
くデータ・プロセツサにおける本発明の他のアプ
リケーシヨンを示す図である。作業ステツプ・ア
ーキテクチヤにおいては、多重プログラミング・
オペレーシヨンは複数のプログラムまたはプログ
ラム・セグメントの各々に優先順位の値が与えら
れ、その時間が一連の等時間間隔に分けられるよ
うな場合に生じる。各時間間隔の前に、最高優先
順位を有するプログラムまたはプログラム・セグ
メントが次の間隔の間で実行のために選択され
る。作業ステツプ・アーキテクチヤのオペレーシ
ヨンを実行する例示的なコンピユータ・アーキテ
クチヤが第６図に示されている。そのCPUは共
有データ処理資源であり、待ち行列制御デイスパ
ツチヤに接続される。この待ち行列制御デイスパ
ツチヤは、その時間を一連の等時間間隔に分ける
タイマ入力を有する。待ち行列制御デイスパツチ
ヤには前述のスタツク１６のごとき優先式スタツ
クが接続される。待ち行列制御デイスパツチヤに
は、さらに、大規模なメモリが接続される。この
メモリはその接続のためのアドレス入力を有し、
待ち行列制御デイスパツチヤによつて最高の優先
順位であると識別されたプログラムまたはプログ
ラム・セグメント（したがつて、このプログラム
は次の時間間隔における実行のために選択される
可能性がある）を記憶する。第２図の待ち行列コ
ントローラ９は第６図の待ち行列制御デイスパツ
チヤに含まれる。待ち行列コントローラ９は最高
の優先順位を有し、次の時間間隔で実行のために
選択される次のプログラムの識別を要求するため
の待ち行列機能選択入力を有するという点で、第
５図のLANアプリケーシヨンで説明したものと
同様にして作動する。第６図の作業ステツプ・ア
ーキテクチヤのアプリケーシヨンにおける待ち行
列コントローラ９のオペレーシヨンは、第５図の
LANアプリケーシヨンで説明したのとほとんど
同じである。特に、第６図の待ち行列制御デイス
パツチヤへの新しいプログラムまたはプログラ
ム・セグメントの割当てが第６図のタイマによつ
て設定される一連の時間間隔の発生と非同期的で
ある場合、待ち行列コントローラ９はこのことに
適応することができる。というのは、待ち行列コ
ントローラ９は各時間間隔の始まりで利用できる
最高優先順位のプログラムの識別を保持レジスタ
１０において使用可能にし、しかも待ち行列コン
トローラ９は、すでに説明したように優先式スタ
ツク１６に新しいエントリを加えることに関して
常に利用可能だからである。

Ｆ 発明の効果 以上説明したように、本発明によれば、保持レ
ジスタに最高優先順位のエントリが記憶されるの
で、従来に比してより効率的に優先式待ち行列を
管理することができる。

【図面の簡単な説明】

第１図は、本発明の実施例を説明する流れ図、
第２図は、本発明に基づく装置の実施例を示す
図、第３図は、本発明に基づくスタツク及び保持
レジスタの例を示す図、第４図は、本発明を適用
しうる典型的なデータ通信のタイム・フレームを
示す図、第５図は、本発明に基づいてセツシヨン
優先順位管理を行なうことができるようなLAN
のアーキテクチヤを示す図、第６図は、本発明に
基づいて優先順位の割当ての管理ができるような
作業ステツプ・データ・プロセツサのアーキテク
チヤを示す図である。

Claims (1)

1. 【特許請求の範囲】 １ データ処理システムにおいて優先式待ち行列
   を管理する方法であつて、 (a) 最高優先順位のデータの要求に応答してデー
   タ部分及び優先順位部分を有する保持レジスタ
   の内容を読み取るスキツプと、 (b) 各々優先順位部分及びデータ部分を有するス
   タツク内の複数のエレメントのうちスタツク先
   頭ポインタによつて指示される先頭のエレメン
   トを読み取つてその内容を上記保持レジスタに
   書き込むステツプと、 (c) 初期的に上記スタツク先頭ポインタと等しく
   セツトされているスタツク探索ポインタによつ
   て指示されるスタツク内の最初のエントリを見
   つけることによつてスタツク内の複数のエレメ
   ントを探索して上記スタツク探索ポインタによ
   つて指示されるエントリの内容と上記保持レジ
   スタの内容とを比較するステツプと、 (d) 上記スタツク内のエントリの内容の優先順位
   部分が上記保持レジスタの内容の優先順位部分
   よりも高いものである場合に上記スタツク探索
   ポインタによつて指示される上記スタツク内の
   エントリの内容と上記保持レジスタの内容とを
   スワツプするステツプと、 (e) 新しいデータが上記スタツクに書き込まれる
   かどうかを判断するステツプと、 (f) 上記新しいデータの優先順位部分が上記保持
   レジスタの内容の優先順位部分よりも高いもの
   であるかどうかを判断するため上記スタツクに
   書き込むべき新しいデータを比較するステツプ
   と、 (g) 上記新しいデータの優先順位部分が上記保持
   レジスタの内容の優先順位部分よりも高いもの
   である場合に上記スタツク先頭ポインタの内容
   を増分して上記保持レジスタの内容を上記スタ
   ツク先頭ポインタによつて新たに指示される上
   記スタツク内のロケーシヨンに書き込み、さら
   に上記新しいデータを上記保持レジスタに書き
   込むステツプと、 (h) 上記新しいデータの優先順位部分が上記保持
   レジスタの内容の優先順位部分よりも高くない
   場合に上記新しいデータを上記スタツクに書き
   込むステツプと、 (i) 上記スタツク内のすべてのエントリの比較が
   完了するまで上記ステツプ(c)以降のステツプを
   繰り返すステツプと、 を含むことにより最高優先順位のエントリが上記
   保持レジスタに記憶されるようにしたことを特徴
   とする優先式待ち行列管理方法。