(57)【特許請求の範囲】
【請求項１】
実行待ち状態のタスクのタスク名を優先度の順に記憶する複数のワード記憶部を含み、前記優先度が前記タスク名として割り当てられた、ハードウエアで構成されたプロセッサキュー手段、
イベントの生起に応答して前記プロセッサキュー手段に置かれるべき前記タスク名を記憶する複数のワード記憶部を含む、ハードウエアで構成されたイベントキュー手段、
イベントの生起のシグナルを与えるプロセッサ手段、及び
前記プロセッサ手段から非同期的にシグナルによって通知されたイベントに応答して、前記イベントキュー手段中の前記複数のワード記憶部を並列にサーチして、前記シグナルによって通知された前記イベントの生起に関連付けられた前記タスク名を見出し、前記見出されたタスク名を前記プロセッサキュー手段へ転送する、ハードウエアで構成された照合論理手段
を含む、マルチタスキングデータ処理システム。
【請求項２】
前記プロセッサキュー手段に置かれている複数のタスク名を前記ワード記憶部の一つの組から他の一つの組へ同時に転送するシフト論理手段を更に含む、請求項１記載のマルチタスキングデータ処理システム。
【請求項３】
前記シフト論理手段は、前記プロセッサ手段から生成されたコマンド信号に従って、前記複数のタスク名を前記ワード記憶部から前記キュー手段の各々に沿って一方向に同時に転送し、又は前記キューの各々に沿って逆方向に同時に転送する手段を含む、請求項２記載のマルチタスキングデータ処理システム。
【請求項４】
前記シフト論理手段は、前記複数のワード記憶部によるアドレスの制御の下で、前記タスク名の同時転送をアドレス指定されたワード記憶部から始めるとともに、
前記同時転送されるタスク名は、前記アドレスされたワード記憶部中に入っているタスク名から始まり、前記プロセッサキュー中で当該アドレスされたワード記憶部から前記一方向又は前記逆方向に設けられているワード記憶部中に入っているタスク名を含む、
請求項３記載のマルチタスキングデータ処理システム。
【請求項５】
複数のレジスタを含み、該レジスタの各々は前記プロセッサ手段から非同期的にシグナルによって通知されるイベントを待っているタスクの数を記憶する、ハードウエアのイベント計数手段と、
非同期的にシグナルが与えられたイベントに応答して前記タスクの数を記憶するハードウエアのイベント計数手段内の前記複数のレジスタの全てを並列にサーチし、タスクが前記非同期的にシグナルによって通知されるイベントを待っているか否かを判定し、待っている場合には前記照合論理手段を動作させて前記イベントキュー手段をサーチして前記非同期的にシグナルによって通知されるイベントを待っているタスクのタスク名を見つけるように動作するサーチ手段と
を含む、請求項１記載のマルチタスキングデータ処理システム。
【請求項６】
前記イベントキュー手段の前記複数のワード記憶部の各々は、タスク名及び関連するイベント名を記憶し、指定されたイベントの発生によって指定されたタスクが前記プロセッサキュー手段に転送される、
請求項５記載のマルチタスキングデータ処理システム。
【請求項７】
前記イベントキュー手段中の前記タスク名は、前記タスク名の各々に対応づけられた優先度に沿って記憶され、
前記照合論理手段による前記イベントキュー手段の並列サーチはシグナルが与えられた前記シグナルによって通知されたイベントに関係する全てのタスク名の読み出しを並列にサーチするとともに、
前記サーチ結果の出力は前記優先度に従って行う、
請求項６記載のマルチタスキングデータ処理システム。
【請求項８】
複数のワード記憶部を含み、該複数のワード記憶部の各々は、遅延時間値及び前記遅延時間値の発生時にシグナルによって通知されるイベント名を記憶する、ハードウエアの遅延キュー手段と、
前記遅延時間値をシグナルによって通知するタイマ手段と、
前記タイマ手段のシグナルによって通知された前記遅延時間値に応答して、前記遅延キュー手段の前記複数のワード記憶部を並列にサーチして前記遅延時間値がシグナルによって通知されたときにシグナルによって通知するためのイベントを見出し、シグナルによって通知された前記イベントを前記照合論理手段に転送し、これによって前記イベントがシグナルによって通知された際に前記プロセスキュー手段に転送されるべき前記イベントキュー手段中のタスク名を認識する手段と
を更に含む、請求項１記載のマルチタスキングデータ処理システム。
【請求項９】
前記タスク名の各々は他と重複しない値で示され、
前記他と重複しない値はそれが示すタスクの全てのタスクの中での優先度を示す、
請求項１記載のマルチタスキングデータ処理システム。
【請求項１０】
接続されたデータ処理システムからアドレス及びデータを受け取るとともに、前記データ処理システムにデータを渡す、ハードウェアのコマンド及び状態レジスタ、
優先度がタスク名として割り当てられたタスク名のキューを記憶する複数のワード記憶部を含むＣＰＵキューであって、前記タスク名のキューは前記タスク名で指示されたタスクの優先度に基づいて構成され、これらの対応するタスクは全て実行待ち状態であるＣＰＵキュー、
タスク名のキューを優先度の順に記憶する複数のワード記憶部を含み、前記タスク名の各々はイベント名と関連付けて記憶され、当該イベントが生起すると当該関連付けられた前記タスク名が実行待ち状態になるハードウエアで構成されたイベントキュー、及び
前記コマンド及び状態レジスタ内で非同期的に発生したイベントデータに応答して前記イベントキューの並列サーチを行わせ、前記非同期的に発生したイベントデータに関連付けられた全てのタスク名を見出し、前記見出された前記タスク名を前記ＣＰＵキューに転送できるようにするキュー状態機械
を含む、ハードウエアで構成されたオペレーティング・システム・カーネル。
【請求項１１】
前記キュー状態機械は、前記タスク名を前記タスク名の前記優先度順で前記ＣＰＵキュー内に記憶せしめる、請求項１０記載のカーネル。
【請求項１２】
前記タスク名の各々は他と重複しない値であり、前記他と重複しない値は前記指示されたタスクの優先度を示す、請求項１１記載のカーネル。
【請求項１３】
遅延時間値及び関連付けられたイベント名のキューを記憶する複数のワード記憶部を含み、前記イベント名は前記関連付けられた遅延時間値の値の大きさに従って前記キュー内に配置される、遅延キューを更に設け、
前記キュー状態機械は、前記遅延時間値になったことに応答して、前記それに関連付けられたイベント名のシグナルが与えられるようにし、これにより前記イベントキューからのタスク名の転送が起こるようにする、
請求項１２記載のカーネル。
【請求項１４】
前記キューの各々における前記複数のワード記憶部のそれぞれに接続され、データが前記複数のワード接続部のいずれかから選択的に読み出され、又はそれに選択的に書き込まれることを可能にするアドレス手段を更に有する、請求項１３記載のカーネル。
【請求項１５】
前記キューの各々の中にある前記複数のワード記憶部の各々を相互に接続し、選択されたワード記憶部間の同時データ転送を可能にするバス手段を更に有する、請求項１４記載のカーネル。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は多数のタスクに対して並列に動作するようプログラムされるプロセッサに関し、更に詳細には、プロセッサのオペレーティングシステムの一部をハードウェアで構成してマルチタスク動作を一層迅速に進行させることに関する。
【０００２】
【従来技術及びその問題点】
リアルタイムデータプロセッサは多数のタスクの処理を同時に取扱うことができる。マルチプロセッサはこの機能をタスクに対して並列に動作する多数のプロセッサを設けることにより行う。リアルタイム動作する単一プロセッサシステムは、「並列」処理をマルチタスキングで取扱う。マルチタスキングとは幾つかのタスクを同時につまり並列に実行するプロセスである。同時に処理されるタスクは、物理的には同時に実行し得ないかもしれないが、論理的には同時に実行される。
【０００３】
マルチタスキング動作はコンピュータのオペレーティングシステムの制御のもとで、特に、同時に実行されるタスクのスケジューリングを制御するその「エグゼクティブ」部の制御のもとで行われる。エグゼクティブ部（今後ＥＸＥＣと呼ぶ）はタスクと中央処理装置との間のインターフェースとなる。各タスクにとって、ＥＸＥＣはそのタスク自身の中央処理装置のように見える。ＥＸＥＣは、物理的ＣＰＵをシステムの全てのタスクと共有する際に関係する細目の全てを処理する。従って、ＥＸＥＣは、各タスクに割当てられた優先度及び実行可能度のレベルを調べることにより、どんなときにどのタスクがＣＰＵを所有すべきかを制御する。
【０００４】
一般に、ＥＸＥＣは、ＣＰＵを使用する別の要求を優先度が更に高いタスクから受取るまで１つのタスクがＣＰＵ上で実行できるようにする。実行中のタスクは「サスペンド（ｓｕｓｐｅｎｄ）」され、優先度の高いタスクの実行が許される。このプロセスは多数回起こるかもしれないが、最高の優先度のタスクは遅かれ早かれその処理を完了し、自発的に自分自身をサスペンドする。従って、優先度の低いタスクがその完了前多数回サスペンドされることがあったとしても、そのタスクは結局は完了し、それが割込まれずに実行された場合と同じ結果を生じる。
【０００５】
タスクには種々の実行状態がある。アクティブタスクはＣＰＵの制御を有し、実行されているものである。唯１つのタスクが任意の所与の時間にマルチタスキングＣＰＵ上でアクティブであることができる。非アクティブタスクは実行されておらず、また実行されるのを待ってもいない。非アクティブタスクは単にアイドル状態であるだけである。動作準備完了タスクは、ＣＰＵ時間が利用可能になり実行することができるようになるのを待っているものである。待ちタスクは、或るイベントが発生するまで動作をサスペンドしているものである。イベントは他のタスクにより発生されることもあるし、あるいはハードウェアイベントのこともある。イベントが発生すると、タスクは待ち状態から、現在活動的なタスクの優先度により、動作準備完了状態またはアクティブ状態に移る。
【０００６】
タスクは、優先度、タスクの作動可能状態、あるいは両者の組合わせにより同期させることができる。一般に、ＥＸＥＣはタスクが必要な制御機能を行うのに使用する多数のユーティリティルーチンを備えている。これらユーティリティルーチンのもとで、任意のタスクが他のタスクをスケジューリングしたり、それ自身または他のタスクをサスペンドしたり、イベントのシグナルを与えたり、ある時間イベントを待ったり遅らせたりすることができる。ＥＸＥＣの主要なユーティリティルーチンは次の通りである：Ｓｃｈｅｄｕｌｅ、Ｓｕｓｐｅｎｄ、Ｓｉｇｎａｌ、Ｗａｉｔ、Ｄｅｌａｙ。Ｓｃｈｅｄｕｌｅユーティリティは、当該アクティブタスクが他のタスクの実行を開始あるいは再開させたいときにこのアクティブタスクが使用する。Ｓｃｈｅｄｕｌｅは最高の優先度の動作準備完了タスクを実行できるようにする。Ｓｕｓｐｅｎｄユーティリティは、アクティブタスクによって使用され、自分自身を動作準備完了状態でなくしたりあるいは他のタスクを非アクティブ状態に移す。このとき、制御は現在最高の優先度を持つ動作準備完了タスクに与えられる。
【０００７】
Ｓｉｇｎａｌユーティリティはアクティブタスクまたは割り込みサービスルーチンにより特定のイベントを発生するのに使用される。シグナルが与えられたイベントに付随するタスクがなければ、ＥＸＥＣは制御をアクティブタスクに戻す。そのシグナルが与えられたイベントに付随するタスクがあれば、制御は最高優先度のタスクに戻される。
【０００８】
Ｗａｉｔユーティリティは、アクティブタスクが自分の実行をサスペンドし特定の１つまたは複数のイベントが発生したときその実行を再開したい場合に使用される。
【０００９】
Ｄｅｌａｙユーティリティは、アクティブタスクがそれ自身かまたは他のタスクに特定の時間だけ待たせてから実行を再開させる必要があるとき、このアクティブタスクによって使用される。このユーティリティは、時間を基準として使用することにより、非同期タスクを同期されるようにする。
【００１０】
オペレーティングシステムは、フォームウェアの動作をハードウェアのイベントに同期させる主要な手段である割込み機構を組込んでいる。割込みが発生すると、制御は、そのときどんなタスクが実行中であってもそのタスクから割込み処理モジュールに移る。発生することができる割込みの各形式毎に１つの割込みモジュールが存在する。
【００１１】
上述のユーティリティを実現するために、多様なデータ構造がＥＸＥＣにより採用されている。ＣＰＵキューは作動準備完了状態にあるタスクのリストである。最高優先度のタスクは現在のアクティブタスクである。同じ優先度の作動準備完了タスクが２つ存在すれば、最初に作動準備完了したタスクがアクティブタスクになる。イベントキューは待ち状態にあるタスクのリストである。遅延キューは、遅延の継続時間後、イベントを待っているタスクをＣＰＵキューに移して作動準備完了タスクにする遅延イベントのもう１つのリストである。
【００１２】
前述のキュー構造はダイナミック、即ち更新される必要があり、少なくとも４つの基本動作、すなわち項目の挿入、項目の削除、項目の位置決め、及び項目の修正ができるようになっていなければならない。各キューは線形リスト、単一リンク付きリスト、または二重リンク付きリストとして構成することができる。単一リンク付きリストは、各項目がリスト内の次の項目を示すポインタを持っているものである。二重リンク付きリストは、２つのリンクフィールドを持っている項目を備えている。二重リンク付きリスト内の各項目は、右側の隣の項目及びその左側の隣の項目を指すポインタを備えている。
【００１３】
上に示したように、ＥＸＥＣは一般に、オペレーティングシステムの一部（「カーネル」）としてソフトウェアで構成されている。しばしば、ＥＸＥＣはキューの内容の比較及びシフトを含むキューの幅に渡る動作（ｑｕｅｕｅ−ｗｉｄｅ  ｏｐｅｒａｔｉｏｎ）を行う必要がある。このような動作は直列に行われ、その実行時間はキューの長さと共に少なくとも直線的に変わる。このような実行時間はオペレーティングシステムの性能に有害な影響を及ぼすことがあり、システムの性能の向上に対して現実に障害となる。
【００１４】
【目的】
従って、直列処理動作から制約を受けないＥＸＥＣを備えたマルチタスキングデータ処理システムを提供することが本発明の目的である。
【００１５】
本発明の他の目的は、マルチタスキングデータ処理システムを一層効率良く動作させることができるＥＸＥＣを提供することである。
【００１６】
本発明の他の目的は、カーネルに保持されているキューが別個の優先度表示を必要としないハードウェア構成オペレーティングシステムカーネルを備えたマルチタスキングデータ処理システムを提供することである。
【００１７】
【概要】
本発明の一実施例によれば、ハードウェア構成オペレーティングシステムカーネルを備えているマルチタスキングデータ処理システムが与えられている。システムは、各々が処理についての準備が完了しているタスク名を、実行優先度の順序で格納している複数のワード記憶部を備えたプロセッサキューを備えている。カーネル内のイベントキューは、イベントの発生を待ってプロセッサキューに置かれるタスク名を格納する複数のワード記憶部を備えている。関連するプロセッサがイベントの発生のシグナルを与えると、照合論理部はイベントキュー内の全てのワード記憶部を並列にサーチして、シグナルされたイベントに関連付けられたタスクを見出し、そのタスクをプロセッサキューに転送する。プロセッサキュー中の複数のタスク名を同時に並列に転送して、イベントキューから転送されるタスク名のための空き場所を作るシフト論理部も設けられている。
【００１８】
【実施例】
簡潔に述べれば、本発明は、オペレーティングシステム中のクリティカルな機能をオペレーティングシステムのソフトウェアから除去し、これらの機能をハードウェア構造で実現する。この機構により、頻繁に現れるある種のデータ再組織動作を並列に且つ予め定められた時間幅内に行うことができる。ハードウェアカーネルは、主として５つのコマンド、すなわち、Ｓｃｈｅｄｕｌｅ、Ｓｕｓｐｅｎｄ、Ｓｉｇｎａｌ、Ｗａｉｔ、及びＤｅｌａｙを採用する。これらのコマンド及びその組合わせにより、取付けられたプロセッサの動作パラメータを大幅に改善することができる一組のリアルタイムオペレーティングシステムプリミティブが作り出される。カーネル内のキューがハードウェア構成であるため、キューの幅に渡る動作を、ソフトウェア環境で同様の動作を行うのに必要な時間の数分の１の時間で容易に行うことができる。
【００１９】
○ＥＸＥＣモジュール（カーネル）
さて、図１を見ると、システムの高レベルブロック図が示されている。マイクロプロセッサ１０には、ハードウェアで実現されているＥＸＥＣモジュール１２が組み込まれている。ＥＸＥＣモジュール１２は、３つの主要機能ブロック、すなわち、コマンド及びステータスレジスタセット１４、キュー状態機械１６、及びキューシステム１８を含んでいる。キューシステム１８は全てのユーティリティが操作するデータ構造を含んでいる。キューシステム１８には物理的に同一の３つのキュー、すなわち、ＣＰＵキュー２０、遅延キュー２２、及びイベントキュー２４がある。
【００２０】
ＣＰＵキュー２０は、タスク制御ブロック（ＴＣＢ）の名前及びこのＴＣＢをＣＰＵキューに配置させるするところの当該ＴＣＢに関連するイベントの優先度の順に並べられたリストである。ＣＰＵキュー２０は各種タスクがマイクロプロセッサ１０の内部で実行されるシーケンスを制御する。ＴＣＢはタスクのステータスに関する全ての情報を含んでおり、マイクロプロセッサ１０の内部でこのようなタスクを制御するのに使用される。各ＴＣＢの名前は、その優先度を示しまたＴＣＢを特定する値（例えば、０から２５５）である。タスクの優先度はタスクのＴＣＢ名で参照されるが、タスクにマイクロプロセッサ１０の所有権が与えられたことを判定するのに使用される。ＣＰＵキュー２０の「先頭」にあるＴＣＢはそのタスクのためにマイクロプロセッサ１０の所有権を保持している。より優先度の高いタスクがキューに置かれれば、現在実行中のタスクがＣＰＵキュー２０の先頭にある優先度がより高いタスクで置き換えられ、その優先度の高いタスクが実行される。どんなときでも、ＣＰＵキュー２０にあるタスクのＴＣＢの数は全タスクの数（全てのタスクが実行の準備が完了している場合）からゼロ（アクティブタスクすなわち実行準備が完了しているタスクがない場合）までの範囲にわたることができる。
【００２１】
イベントキュー２４はＴＣＢの名前を優先度順に並べたリストを含んでおり、リスト内の各ＴＣＢはイベント名と結合されている。イベントが発生すると、そのイベントに結合されているＴＣＢはＣＰＵキュー２０に移される。遅延キュー２２はイベント名のリストを含んでおり、各イベント名はそれに関連付けられたイベントがどれだけ待ってからシグナルを受取るかを示す遅延と関連付けられている。遅延キュー２２にあるイベント名は、それに関連付けられた遅延の値に基づいて優先度が決められている。
【００２２】
キューシステム１８はまた、システム内で発生することができる所定数の可能なイベントのうちの利用可能性を常に掌握しておく一組のイベントカウントレジスタ２６を含んでいる。イベントはシステムタスクがシグナルすることがあり、またシステムタスクがこれを待つことがあるということを想起すべきである。システムにより収容され得るイベントの数はアドレスのサイズで示され、システムの制限と考えるべきではない。説明の目的でシステムは最大２５６の可能なイベントを収容することができ、このようなどのイベントに対しても８ビットのアドレスを使用すると仮定する。
【００２３】
コマンド及びステータスレジスタ１４の内部に、マイクロプロセッサ１０がＥＸＥＣユーティリティを開始するために書き込むコマンドレジスタがある。その他に、マイクロプロセッサ１０が「読み出しアクセス可能」であり、またＥＸＥＣモジュール１２の内部の動作により発生されたデータを含む多数のレジスタが存在する。これらレジスタのリストを下に示す。
【００２４】
キュー状態機械１６はＥＸＥＣモジュール１２の動作を制御する。マイクロプロセッサ１０からコマンド及びステータスレジスタ１４のレジスタにＥＸＥＣ命令を受取ると、キュー状態機械１６はキューシステム１８の１つまたは複数のキューについて必要な動作を実行する。キュー状態機械１６はまたコマンド及びステータスレジスタ１４中のレジスタについて必要な動作を行い、または更に、タイマ２８及びポート制御モジュール３０を制御する。ポート制御モジュール３０はＥＸＥＣモジュール１２に対するＩ／Ｏコマンド機能を提供する。マイクロプロセッサ１０とＥＸＥＣモジュール１２との間のアドレス及びデータの接続は、コマンド及びステータスレジスタ１４により、それぞれ線３１及び３３を経由して、直接行われる。
【００２５】
○信号線の定義
マイクロプロセッサ１０とＥＸＥＣモジュール１２との間に存在する信号線は次の通りである。
【００２６】
・ＥＸＥＣモジュール１２への入力
ＣＳ−チップ選択
Ｒ／Ｗ−読み出し／非読み出し（書き込み）線
ｕＰＡｄｄｒ（０〜７）−アドレス線
ＳＣＬＫ−ＥＸＥＣシステムクロック（図示せず）
ＮＲＳＴ−外部リセット線
ＮＴＳＴ−試験線（試験モード動作用）
・ＥＸＥＣモジュール１２への双方向線
ｕＰ  Ｄａｔａ（０〜１５）−データ線
・ＥＸＥＣモジュール１２からの出力
ＮＤＴＡＣＫ−データ転送アクノレッジ（非同期アクノレッジ）
ＮＩＮＩＴ−ＣＰＵへの割込線
【００２７】
次の信号はキュー状態機械１６とキュー２０、２２、及び２４の各々との間をバス３２を経由して進む（ただし図１には特に図示してはない）。
【００２８】
Ｄ（０〜７）−ＥＸＥＣ内部データバス
ＡＤＤＲ（０〜１５）−ＥＸＥＣ内部アドレスバス
ＣＭＤ（０〜３）−キューシステム１８へのコマンド線
ＱＥＮ（０〜３）−キューコマンドイネーブル（キュー及びアレイの各々に１つずつ）
【００２９】
各キューには２５６個のキュー要素がある。各キュー要素は２つの８ビットワードを格納する。それ故、キュー内のワードにアクセスするには８本のデータ線と９本のアドレス線が必要である。９番目のアドレス線はＣＭＤ（３）信号線である。ＣＭＤ（０〜２）は異なる８個のコマンドのうちのどれを実行するかを指定するのに使用される。ＣＭＤ（３）は動作が２つのキュー要素ワードのどれで実行されるかを決定する。ＱＥＮ（０〜３）線はキューの１つだけをイネーブルするのに使用される。
【００３０】
コマンドは、算術比較を実行するために特定のキューに送ることができる。これら算術比較は全てのキュー要素について並列に行われる。このような比較の結果は、項目を挿入または削除するためキュー内で並列シフトを行うのに使用される。こうすることにより、これらデータを、通常、リスト中へのポインタを用いて行うように操作するよりもかなりな速さの改善が得られる。
【００３１】
下記の別の信号はキュー状態機械１６からイベントカウントレジスタ２６までバス３２を通って進む（図１には特に図示してない）。
【００３２】
ＥＣＯＰ（０〜１）−イベントカウンタ操作
ＥＣＯＣ−イベントカウンタ出力制御
ＥＣＣＬＫ−イベントカウンタクロック
ＥＣＬＲ−イベントレジスタアレイクリア
ＥＯＣ−イベントレジスタ出力制御
【００３３】
これら信号は、イベントカウントレジスタ２６の２５６個の８ビットレジスタ、及びレジスタ２６中にあって、これら値をロードしてインクリメントまたはデクリメントすることができるカウンタを制御するのに使用される。
【００３４】
イベントカウンタレジスタ２６の中の各レジスタのロケーションは対応して番号の付いたイベントと関連付けられている。特定のイベントのシグナルが発生すると、適切なレジスタ値が読み出され、インクリメントされ、再書き込みされる。同様に、特定のイベントについてＷａｉｔが実行されると、適切なレジスタの値が読み出され、デクリメントされ、再び書き込まれる。
【００３５】
○キューの構造
次に図２を見ると、ＣＰＵキュー２０の基本構造が示されている。各キューのハードウェア構造は同一であることが想起されよう。ＴＣＢ名は優先度の順序にＣＰＵキュー２０に格納されている。別々の優先度値をＴＣＢ名に割当てるのではなく、当該ＴＣＢに割当てられた実際の優先度値をＴＣＢ名として割当てることにより実質的な記憶領域を保持できると定められた。従って、名前０を有するＴＣＢは最高の優先度値を持っており、このＴＣＢは、ＥＸＥＣモジュール１２のアドレス表示では、全てが０であるアドレスによって参照される。優先度のより低い他のＴＣＢは同様に命名される。
【００３６】
ＣＰＵキュー２０は複数のキュー要素３５を含んでいる。説明の都合上、ＣＰＵキュー２０を、８ビットアドレスで使用することができる２５６個ではなく、キュー要素４個だけしかないように示してある。キュー要素の構造を図３に図示し、下に詳細に説明することにする。データ線（０〜７）は、各キュー要素３５のデータポートへ、またデータポートから、データを運ぶ（図２を参照）。ＣＭＤ（０〜３）は異なる８つのコマンドのどれを各キュー要素３５で実行するかを指定するのに使用されるアドレス線である。ＣＭＤ（３）線は、キュー要素３５の２つのワードのうちの何れで操作を行うかを決めるレベルを与える。ＱＥＮ（０）はイネーブル線であって、３つのキュー（２０，２２，２４）の１つをイネーブルする。
【００３７】
アドレスバスＡＤＤＲ（０〜７）はアドレスデコーダ３６によりデコードされ、個別のキュー要素３５を（２５６本の別々のワード線から成るケーブル３８の出力を経由して）選択するのに使用される。ワードバス３８の各ワード線は個々のキュー要素３５に接続されて、アドレスデコーダ３６に受けられたアドレスに従ってどれか１つの選ばれたキュー要素中での論理操作ができるようにする。このような接続は図を複雑にし過ぎないよう、図２には図示してない。
【００３８】
アドレスバスＡＤＤＲ（０〜７）はまた、比較動作中アドレス情報をキュー状態機械１６に返送する。このような動作中、比較判定基準を満たすキュー要素３５のアドレスはアドレスバスＡＤＤＲ（０〜７）上に返送される。
【００３９】
レゾルバ／エンコーダ４０は、複数のキュー要素３５が比較判定基準を満たした場合の事態を解決する。例えば、「数値０」を含む１つのキュー要素のアドレスを返送するというコマンドが発せられ且つ全てのキュー要素が「０」を含んでいれば、レゾルバ／エンコーダ４０は、アドレスバスＡＤＤＲ（０〜７）が最小の番号の付いたキュー位置をキュー状態機械１６に返送するようにする。上に示した例では、レゾルバ／エンコーダ４０は位置１をアドレスバスＡＤＤＲ（０〜７）上に返送する。
【００４０】
各キュー要素３５はタスクに関する２ワードの情報を含んでいる。一般に、ＣＰＵキュー２０の位置１にあるキュー要素３５は、操作を待っている最高優先度のタスクに関する２ワードを含んでいる。これらのワードは、最小の数値（優先度）を有するＴＣＢ名、及びこのＴＣＢ名をＣＰＵキュー２０に移動させるイベントの名前である。位置３、４等にあるキュー要素は更に低い優先度（数値としてはもっと大きな値）を有するＴＣＢ名を含んでいる。
【００４１】
各キュー要素３５をその次に大きな数字の付いた隣のキュー要素に接続し、項目をキューに対して挿入または削除するときに使用される２つのローカルバス４２及び４４がある。各キュー要素３５はその構造に組込まれている２つの比較動作を持っており、その結果はＧＴ出力４６及びＭ出力４８に現れる。信号「ＧＴ」及び「Ｍ」はそれぞれ「より大きい（Ｇｒｅａｔｅｒ  Ｔｈａｎ）」及び「一致（Ｍａｔｃｈ）」を意味する。簡潔に述べれば、データをデータバスＤ（０〜７）に印加すると、各キュー要素３５は、自分に含まれているデータワードの値が印加されたデータワードに対して一致するかあるいは大きいか判定する。自分にストアされているワードの値がデータバスの値より大きいことがわかれば、出力は出力ＧＴ線４６に与えられる。値が一致していることがわかれば、Ｍ出力４８が付勢される。マルチプレクサ５０は全てのキュー要素３５に接続され、キュー要素３５からの全ての「より大きい」出力４６かまたはキュー要素３５からの全ての「一致」出力４８のいずれかを選択するように制御される。図２に示した例では、マルチプレクサ５０は、図示した４つのキュー要素から選定された「より大きい」または「一致」出力からの４つの出力を与える。どの信号群が選択されるかは入力データに一致する最も小さい番号のキュー要素３５を知りたいのかあるいは入力データより大きい値を保持する最も小さい番号のキュー要素３５を知りたいのかによって決まる。
【００４２】
○キュー要素の構造
次に図３に転ずると、キュー要素３５の構造が図示されている。各キュー要素３５では、一対のワード記憶部５２及び５４が２つの８ビット値、すなわちワードＡ及びワードＢを保持している。その他に、各ワード記憶部は、入来データワードと自分が持っているワードとの間の比較を行うことを可能とするに必要な論理を含んでいる。その論理構造の詳細を図４に示し、下で更に考察することにする。
【００４３】
キュー要素３５は下記の情報を保持している。
【００４４】
0003604091.tif 000002
【００４５】
タスク名／優先度は（上に記した通り）その値がその優先度と直接関係しているＴＣＢ名によって表される。「イベントケース（ｅｖｅｎｔ  ｃａｓｅ）」は、ワードＡのＴＣＢにより指示されたタスクをＣＰＵキュー２０に移させた、生起したイベントの名前の値である。「イベント名」はマイクロプロセッサ１０の内部の特定の動作に与えられた名前つまり値である。例えば、イベント名はハードウェア割込、Ｉ／Ｏ割込等に割当てられた値とすることができる。「遅延値」はイベントが発生するまでに経過しなければならない時間に割当てあられた値である。
【００４６】
各ワード記憶部５２、５４は、それぞれ、マルチプレクサ５６及び５８に印加されるＧＴ及びＭ出力を含んでいる。ＣＭＤ（３）線はマルチプレクサ５６及び５８に印加され、その出力レベルにより、どのワード（ワードＡまたはワードＢ）を比較して所要出力をＧＴ線４６またはＭ線４８のいずれかに発生するかが選択される。
【００４７】
ＬＡＳＴバス４２及び４４、及びＮＥＸＴバス４２’及び４４’は、キュー要素３５の間でワードをシフトするのに使用される。各ワード記憶部５２、５４は、全キュー要素３５の内容を１回の並行動作でシフトできるようにする自分自身のＬＡＳＴ及びＮＥＸＴバスを持っている。ワード記憶部５２及びワード記憶部５４の内容は常に、同じキュー要素３５を共に占めている。
【００４８】
○ワード記憶部の構造
図４に、ワード記憶部５２の詳細を示してある。マルチプレクサ７０はワード記憶部５２（ワードＡ）についての入力データの４つのデータ源を受信する。これらのデータ源は次の通りである。
【００４９】
ＬＡＳＴ  Ａ（０〜７）−次に低位にあるキュー要素ワード
Ｄ（０〜７）−ＥＸＥＣ内部データバス
ＮＥＸＴ  Ａ（０〜７）−次に高位にあるキュー要素ワードＡ
ＶＤＤ−連想メモリ（ｃｏｎｔｅｎｔ−ａｄｄｒｅｓｓａｂｌｅ  ｍｅｍｏｒｙ）７２で比較中にＢＩＴ及びｎＢＩＴ（ＢＩＴのコンプリメント）線にプリチャージするのに使用される。
【００５０】
連想メモリ（ＣＡＭ）７２はワードＡについての８個の並列接続ビットセルを含んでいる。各ビットセルはそのそれぞれのビットについての真の出力及びコンプリメント出力の双方を発生する。一対のマルチプレクサ７４及び７６により、ＣＡＭ７２に保持されている８ビットワードに関して比較動作を行うことができるようになる。
【００５１】
１ビットＣＡＭセルの詳細を図５に示す。ビット線８２及び８４は別になっているが、８個全ての１ビットＣＡＭセルのワード線８１及び８３は共通接続され（図示せず）共通の８ビットワード線を形成している。基本メモリセルは既知の構造のＣＭＯＳフリップフロップ８５である。セル８５に書き込むには、データをビット線８２に乗せ、コンプリメントデータをコンプリメントビット線８４に乗せる。次に、印加された入力に従ってセル８０が切換えられるように、ワード線８１、８３をアサートする。読み出し動作はビット線及びコンプリメントビット線８２及び８４をプリチャージすることから始まる。次にワード線８１、８３をアサートすると、ビット線８２がセルの値を示す。
【００５２】
比較動作については、比較を行うべき真データをコンプリメントビット線８４に印加し、コンプリメントデータをビット線８２に置く。印加されたデータがセル８５にあるデータに一致すれば、一致トランジスタ８６が非導通状態のままとなり、これにより一致線８８がセル８０の状態に影響されないようになる。各メモリセルには一致線８８が１つ存在する。
【００５３】
図４に戻って、キュー要素論理モジュール７３はＣＭＤ（０〜２）線を通して複数のコマンドを受取り、各コマンドをワイヤード論理を使用してデコードし、従ってその出力線Ｓ１〜Ｓ５、Ｅ、及びＷの中の１つあるいは複数のものを付勢する。キュー要素論理モジュール７３からの出力線はマルチプレクサ７０、７４、７５、連想式ワード記憶部７２、及びデマルチプレクサ７６に印加されて、受取ったコマンドを実行することができるようにする。
【００５４】
比較器７７は、ＣＡＭ７２からの一致線出力及びデータバス（０〜７）に現れるデータ入力を調べ、受取ったデータの値がワード記憶部７２に格納されている値より大きいかどうか判定する。比較器７７は、格納されているデータワードを一致線出力から再構築し、以後の入力値の大きさの比較ができるようにする排他的ＮＯＲ入力段（図示せず）を含んでいる。入力データの値が格納されているワードの値より小さければ、比較器７７からのＧＴ出力がアサートされる。入力データの値が格納ワードの値に等しければ、ＡＮＤゲート７８はそのＭ出力をアサートする。
【００５５】
○キューコマンド
各ワード記憶部５２／５４は下記コマンドに応答する。
【００５６】
Ｍａｔｃｈ＝  −  比較されたワードを含むものの内の最大の番号の付いたロケーションを戻す。
Ｍａｔｃｈ＞  −  比較されたワードより次に高い値を含むものの中の最大の番号の付いたロケーションを戻す。
ＳＲ          −  キューの内容を右（次に大きな番号の付いたロケーション）にシフトする。
ＳＬ          −  キューの内容を左（次に小さな番号の付いたロケーション）にシフトする。
ＲＤ          −  アドレスされたワード記憶部の内容をＤ（０〜７）上に読み出す。
ＬＤ          −  Ｄ（０〜７）をアドレスされたワード記憶部にロードする。
Ｉｎｉｔ      −  全てのキュー要素ワードを全てのビットが１である値に初期設定する。
【００５７】
「Ｍａｔｃｈ」コマンドは比較コマンドであり、選択されたワード記憶部（ワードＡまたはワードＢ）に関してキュー内の各キュー要素で実行される。ＲＤコマンド及びＬＤコマンドはキュー内の１つのアドレスされたワードだけで実行される。
【００５８】
ＳＲコマンド及びＳＬコマンドは共に、そこからデータシフトが起こるべきキュー要素ワード記憶部を指示するアドレスを含んでいる。従って、ＳＲ及びＳＬシフトコマンドはそのアドレスロケーションが指定されたアドレスに等しいか大きいキュー要素内部だけで実行される。選択的シフト動作は、指定されたアドレスをキュー状態機械１６からそれぞれのキューのアドレスデコーダ３６（図２）に送ることによりイネーブルされる。アドレスデコーダ３６は、このアドレスに応答して、各キュー要素に入力される、バス３８上の所要のワード線（例えば、図４のキュー要素論理モジュール７３に入力されるＷｏｒｄ（０））を付勢する。
【００５９】
Ｉｎｉｔコマンドは、キュー内の全てのワード記憶部を１の状態に初期設定するのに使用される。
【００６０】
図４に戻って、Ｍａｔｃｈ＝、ＲＤ、ＬＤ、及びＳＲの各コマンドに応答するワード記憶部５２の動作を考察することにする。
【００６１】
コマンドＭａｔｃｈ＝は、キュー要素論理モジュール７７に流入するＣＭＤ（０〜２）線及びＱＥＮ（０）線に適切な値が置かれることにより開始される。これらの値は、ワード記憶部５２が存在している特定のキューに対するＭａｔｃｈ＝コマンドを示す。一致を取るべき値はデータバスからＤ（０〜７）線を通してワード記憶部５２に提示される。キュー要素論理モジュール７３は出力信号Ｓ１及びＳ２を活性化してマルチプレクサ７０がＤ（０〜７）入力をマルチプレクサ７４、７５に伝えるようにする。キュー要素論理モジュール７３からの信号Ｓ３がアサートされ、Ｄ（０〜７）を選択して、ワード記憶部７２に入力するＮＢＩＴ（０〜７）に流す。信号Ｓ３は更にＤ（０〜７）のコンプリメントをワード記憶部７２に入力するＢＩＴ（０〜７）に流す。Ｄ（０〜７）がワード記憶部７２に保持されている値に一致すれば、一致線上に得られる出力によりＡＮＤゲート７８が一致出力Ｍをアサートする。
【００６２】
今度は、内容読み出し（ＲＤ）コマンドがＱＥＮ（０）イネーブル信号を伴ってＣＭＤ（０〜２）線上に現れたと仮定する。キュー要素論理モジュール７３はこれらのレベルをＲＤ−Ａ（ワードＡを読み出す）コマンドであると解釈する。キュー要素論理モジュール７３に入力されるワード（０）に印加されたレベルは、この特定のキュー要素のワードＡがデータバスＤ（０〜７）上に読み出されることを示す。読み出し動作はビット線をワード記憶部７２の各ビットセルにプリチャージする（論理１の状態に上げる）ことにより開始される。これはマルチプレクサ７４及び７６からの出力を、キュー要素論理モジュール７３からのＥ線のアサートによりトライステート状態にすることにより行われる。ワード記憶部７２の各ビットセルへのワード線が次にアサートされ、そこに格納されている８ビット値がキュー要素論理モジュール７３からの信号Ｓ４及びＳ５の制御のもとにマルチプレクサ７６を通してデータバスＤ（０〜７）に読み出される。
【００６３】
ロード（ＬＤ）コマンドは、ＱＥＮ（０）イネーブル信号を伴うキュー要素論理モジュール７３へのＣＭＤ（０〜２）入力に印加されるコマンド値により開始される。キュー要素論理モジュール７３に入力するワード（０）のアサートは、この特定のキュー要素ワードＡがデータバスＤ（０〜７）からロードされることを示す。ＬＤコマンドに応答して、キュー要素論理モジュール７３は信号Ｓ１及びＳ２をマルチプレクサ７０に対してアサートし、マルチプレクサ７０は、Ｄ（０〜７）入力をマルチプレクサ７４及び７５の入力に接続する。次に、キュー要素論理モジュール７３からのＳ３及びＳ４出力でアサートされたレベルにより、データ値Ｄ（０〜７）及びそのコンプリメントがそれぞれワード記憶部７２へのビット（０〜７）入力及びＮＢＩＴ（０〜７）入力に接続されるように選択する。キュー要素論理モジュール７３からのワード線Ｗが次にアサートされ、データ値をワード記憶部７２に格納させる。
【００６４】
右シフトコマンド（ＳＲ）を遂行するには、ＱＥＮ（０）上のイネーブル信号を伴う適切なコマンド値でＣＭＤ（０〜２）線をアサートする。ワード線Ｗｏｒｄ（０）がアサートされて、この特定のキュー要素ワードＡが部分的または全体的キュー位置シフトの一部分となることを示す。ＳＲ（またはＳＬ）コマンドは上述のＲＤコマンドとＬＤコマンドを連結したものである。相違点は、キュー要素論理モジュール７３からの論理信号Ｓ４及びＳ５が読み出し機能の出力としてＮＥＸＴＡ（０〜７）を選択し、Ｓ１及びＳ２出力がロードへの（ＳＲコマンドに対する）入力としてＬＡＳＴＡ（０〜７）を選択することだけである。
【００６５】
並列操作右シフトは、全てのキュー要素ワードを同時に別々のＮＥＸＴＡバスに読み出し、次に全てのキュー要素ワードをその別々のＬＡＳＴＡバスから同時にロードすることにより行われる。明確には図示してないが、各キュー要素ＮＥＸＴＡバスは次に高い位置のキュー要素ＬＡＳＴＡバスに接続されている。上述のことから、キュー要素間のデータのシフトは並列に且つ同時に行われ、選択されたキュー要素間でまたはキュー内の全てのキュー要素間で発生し得ることがわかる。
【００６６】
○イベントカウントレジスタ
ＥＸＥＣモジュール１２は、各々の可能なイベントに１つずつ、２５６個のイベントカウントレジスタ２６を含んでいる（８ビットアドレスで限定される）。図６に、８ビットイベントカウンタ１００及びイベントカウントレジスタの最初の３個、１０２、１０４、及び１０６を示してある。イベントカウンタ１００はプログラム可能であり、データバスＤ（０〜７）を経由してロードされるイベントカウントまたはレジスタ１０２、１０４、または１０６のうちの１つからのイベントカウントに応答する。
【００６７】
各イベントカウントレジスタは、システムで生じる可能性のある２５６のイベントの１つを示す割当て値を含んでいる。レジスタがプラスのカウントを示せば、それは複数のタスクがイベントの発生を待っていることの指示である。イベントカウントレジスタがマイナスの値を示せば、その指示は、イベントの発生を待っているタスクが存在するよりも多い回数のイベントがシグナルされた（発生した）ということである。イベントが発生すると、そのイベントに対応するイベントカウントレジスタを調べてそのカウントの状態を確認する。カウントが正であることがわかれば、キュー状態機械１６は、タスクがイベントキュー２４に存在し、この特定のイベントの発生を待っていることを知る。このような場合には、イベントキュー２４を並列にサーチし、この特定のイベントを指定する全てのＴＣＢを見出す。こうしてイベントを指定する最高の優先度のＴＣＢを選択して実行する。キュー状態機械１６はイベントキュー２４から選択したＴＣＢをＣＰＵキュー２０に転送し、そこでそのＴＣＢは優先度の順に置かれる。タスクをイベントキュー２４から取出すと、イベントカウントレジスタの中の値が、カウンタ１００の動作によりデクリメントされる。
【００６８】
イベントが発生すると、Ｓｉｇｎａｌユーティリティは対応するイベントカウントレジスタの値を読み出させカウンタ１００をプログラムするのに使用させる。次に、カウンタ１００は値をデクリメントし、、このデクリメントされた値は適切なレジスタに書き戻される。Ｗａｉｔユーティリティは、値をデクリメントすることを除いては、同じシーケンスを発生させる。どのイベントカウントレジスタ（１０２，１０４，１０６等）の値もデータバスＤ（０〜７）を経由してキュー状態機械１６が読み出すのに利用できる。キュー状態機械１６からの以下に示すコマンド線はカウンタ１００に与えられる：
【００６９】
ＥＣＯＰ（０〜１）：カウンタ１００をインクリメント、デクリメント、ロード、またはクリアすべきかを指定するのに使用される。
ＥＣＯＣ：カウンタ１００からデータ線Ｄ（０〜７）への出力をイネーブルするのに使用される。
ＥＣＣＬＫ：カウンタ１００での動作を起こさせるのに使用されるクロックである。
ＥＣＬＲ：全てのイベントカウントレジスタ１０２、１０４、１０６等を０に初期設定するのに使用される。
【００７０】
○遅延タイマ
図７に、図１の遅延タイマ２８の詳細を示す。遅延タイマ２８はシステムクロックサイクルをカウントし、キュー状態機械１６がその遅延が終了したイベントにシグナルを与えるようにする。１遅延単位（すなわち、遅延時間の単位）内のクロックサイクル数はプログラム可能であり、この数はコマンド及びステータスレジスタ１４の中のタイマインターバルレジスタに保持されている。遅延単位の値は、タイマインターバルレジスタからＴＩＲ（０〜７）線を通って遅延タイマ２８の８ビットカウンタ１１０に入る。８ビットカウンタ１１２は各遅延単位内でクロックサイクル数を累積し、次の遅延単位のカウントにインクリメントすることにより、遅延単位の数をカウントする。８ビットカウンタ１１２は最大２５５までカウントし、次には０に戻る。Ｄｅｌａｙユーティリティは、絶対時間ではなく、相対時間だけイベントを遅らす。
【００７１】
○コマンド及びステータスレジスタ
図１を参照すれば、コマンド及びステータスレジスタ１４は、１６ビットデータ（及びコマンド）をマイクロプロセッサ１０から、及び８ビットデータをＥＸＥＣモジュール１２の中の各種要素から受取る多数のマイクロプロセッサからアクセス可能なレジスタを有している。全てのレジスタは６ビット幅であり、各レジスタは読み出しまたは書き込みのいずれかが可能であるが、両方は可能とはなっていない。例えば、図８に、書き込みレジスタ１２０及び読み出しレジスタ１２２の例がその相互接続及び制御回路と共に示してある。レジスタ１２２は読み出しレジスタであり、データをＥＸＥＣモジュールデータバスＤ（０〜７）から受取る。このようなデータは次に、イネーブル信号ＲＯＥＮ（５）を印加するとマイクロプロセッサ１０に読み出すことができる。同様に、書き込みレジスタ１２０はデータをマイクロプロセッサ１０から受取り、イネーブル信号ＲＩＥＮ（０）を印加すると、このようなデータを出力としてデータバスＤ（０〜７）に与える。
【００７２】
以下に、コマンド及びステータスレジスタ１４の内部にあるマイクロプロセッサからアクセス可能なレジスタ（図示せず）のリスト、及びそれに関連するユーティリティ動作を実行中のそれぞれのレジスタの動作の説明を与える。
【００７３】
Ｓｃｈｅｄｕｌｅレジスタ（書き込みレジスタ）：タスクＴＣＢをこのレジスタに書き込むと、ＴＣＢはその優先度（ＴＣＢ値）に従ってＣＰＵキュー２０に置がれる。
【００７４】
Ｓｕｓｐｅｎｄレジスタ（書き込みレジスタ）：タスクＴＣＢをこのレジスタに書き込むと、このＴＣＢが実際にＣＰＵキュー２０中にあれば、このＴＣＢはＣＰＵキュー２０から取り除かれる。このＴＣＢがＣＰＵキュー２０になければ、割込条件がマイクロプロセッサ１０に対して発生する。この条件を示すステータスがステータスレジスタに設定される。
【００７５】
Ｓｉｇｎａｌレジスタ（書き込みレジスタ）：イベント制御ブロックがマイクロプロセッサ１０からこのレジスタに書き込まれると、このイベントがシグナルされる。このイベントを待っているタスクがなければ、これに対して取られる処置はこのイベントに対するイベントカウントをデクリメントすることだけである。タスクがこのイベントを待っていれば、最高の優先度（最低のＴＣＢ値）を持つＴＣＢがイベントキュー２４から取出され、ＣＰＵキュー２０に置かれる。
【００７６】
Ｗａｉｔレジスタ（書き込みレジスタ）：イベント制御ブロックがマイクロプロセッサ１０からこのレジスタに書き込まれると、実行中のタスクのＴＣＢがイベントキュー２４に置かれ、指定されたイベントを待つ。実行中のタスクのＴＣＢはＣＰＵキュー２０の最初のキュー位置（位置０）で見いだされる。このＴＣＢはＣＰＵキュー２０から取出され、イベントキュー２４の中にその優先度（ＴＣＢ値）に従って置かれる。
【００７７】
Ｄｅｌａｙレジスタ（書き込みレジスタ）：イベント制御ブロック及び８ビット遅延値がマイクロプロセッサ１０からこのレジスタに書き込まれると、イベント制御ブロック名が遅延キュー２２に置かれ、その遅延値により優先度を与えられる。遅延が少ければ少いほど、このブロック名はキューの先頭に近いところに置かれる。
【００７８】
Ｓｔａｔｕｓレジスタ（読み出しレジスタ）：ＳｔａｔｕｓレジスタはＥＸＥＣチップ内部で生じる異常ステータスに関する情報を含んでいる。
【００７９】
タイマインターバルレジスタ（書き込みレジスタ）：ユーザは、各遅延値を構成するシステムクロックの数を表す１６ビットの値をこのレジスタに書き込む。
【００８０】
ＣＰＵＱレジスタ、イベントＱレジスタ、遅延Ｑレジスタ（読み出しレジスタ）：これらのレジスタは、マイクロプロセッサ１０により読み出されると、適切なキューにある全てのキュー要素ワードの内容を順次与える。これらは診断レジスタである。
【００８１】
診断ポインタレジスタ（書き込みレジスタ）：値を書き込むと、上述の診断レジスタは、読み出しに当ってキュー内のこの値のロケーションから読み出されるように設定される。
【００８２】
アクティブＴＣＢレジスタ（読み出しレジスタ）：読み出されると、ＣＰＵキュー内で最高の優先度を持つ現在のタスクのＴＣＢ名が戻される。
【００８３】
イベントケースレジスタ（読み出しレジスタ）：読み出されると、タスクに実行を再開させたイベントのイベント制御ブロック名が戻される。このタスクがＷａｉｔユーティリティ呼び出しを行っていた場合にのみ、この値が意味を有する。
【００８４】
○キュー状態機械
キュー状態機械１６はＥＸＥＣモジュール１２の作業を制御する。キュー状態機械１６は、コマンド及びステータスレジスタ１４に書き込まれたコマンドに応答する内部ハードウェアにより制御され、制御線を順次付勢してシステム動作を指定コマンドに従って発生させる。全ての局面でキュー状態機械１６は従来どおりであり、その構成は当業者に既知である。
【００８５】
○ＥＸＥＣモジュール動作−スケジューリングユーティリティ
マイクロプロセッサ１０は、スケジューリングしたいタスクのＴＣＢをＥＸＥＣモジュール１２のコマンド及びステータスレジスタ１４の内部にあるＳｃｈｅｄｕｌｅレジスタに書き込む。これにより、ＴＣＢ値はＳｃｈｅｄｕｌｅレジスタの中にラッチされる。これに応答して、キュー状態機械１６はＣＰＵキュー２０の並列サーチを行って、スケジューリングされているＴＣＢ中から、格納されている次に低い優先度のＴＣＢを見つける。これが見つかると、ＣＰＵ２０の中のＴＣＢは、入来ＴＣＢのキュー位置から出発して、１位置右にシフトされる。この右シフトにより空になったＣＰＵ２０の中の位置にスケジューリングすべきタスクのＴＣＢをロードする。
【００８６】
ＥＸＥＣモジュール１２は今度はポート制御モジュール３０からハンドシェーク信号ＮＤＴＡＣＫをアサートして、処理を今や終ってよいということを示す。これに応答して、マイクロプロセッサ１０はポート制御モジュール３０へのそのＣＳ信号のアサートを解除する。この信号はＥＸＥＣモジュール１２との全てのトランザクションに先行する。
【００８７】
ＣＰＵキュー２０は、今や、スケジューリングすべきタスクのＴＣＢ名がＣＰＵキュー２０のその適切な優先度の位置に存在するように修正されている。マイクロプロセッサ１０は、現在実行を待っている最高優先度タスクが何であるかを判定するため、コマンド及びステータスレジスタ１４からアクティブＴＣＢレジスタを読み出す。マイクロプロセッサ１０はイベントケースレジスタを読み出すこともできる。マイクロプロセッサ１０がアクティブＴＣＢレジスタにアクセスすると、キュー状態機械１６はＣＰＵキュー２０の第１のキュー要素（最高優先度）からＴＣＢ名を読み出し、この値をマイクロプロセッサのデータ線ＮＤＴＡＣＫ（０〜１５）に乗せる。ポート制御モジュール３０は次にＮＤＴＡＣＫ線をアサートして、アクティブＴＣＢレジスタの値がマイクロプロセッサ１０から利用可能であることを示す。
【００８８】
イベントケースとはタスクの名前をＣＰＵキュー２０に移動させたイベントの名前であることを想起されたい。マイクロプロセッサ１０はイベントケースレジスタにアクセスしてＣＰＵキュー２０の中のイベント値を判定することができる。このアクセスによりイベント名をＣＰＵキュー２０の最初のキュー要素からイベントケースレジスタに読込まれ、マイクロプロセッサ１０のデータバスＤＡＴＡ（０〜１５）に乗せられる。信号ＮＤＴＡＣＫがアサートされて、マイクロプロセッサ１０にこのレジスタの値が出力データバス上で利用可能であることを示す。
【００８９】
○キュー状態機械の動作−Ｓｃｈｅｄｕｌｅユーティリティ
以下にＳｃｈｅｄｕｌｅユーティリティの期間中に生起する状態を示す。キュー状態機械１６への入力は小文字で表記してあり、出力は大文字で表記してある。イベントは全てシステムクロックに同期している。特定のイベントが発生するまで起こらない状態の各々について、そのイベントを示してある。所与の状態についてイベントが指定されていなければ、その状態からは次の状態機械のクロックで抜け出す。
【００９０】
１．ＩＤＬＥ  −  ＥＸＥＣチップ選択（ｃｓ）がアサートされておらず、ｎｔｓｔがアサートされておらず、ｎｒｓｔがアサートされておらず、タイマキャリ出力（ｔｉｍｅｒ  ｃａｒｒｙ  ｏｕｔ，  ｔｃｏ）がアサートされていない。
イベント  −  チップ選択（ｃｓ）がアサートされ、ＣＰＵはオペレーティングシステムを呼出すことを欲している。
【００９１】
２．ＣＭＤ  ＲＣＶＤ  −  ＥＸＥＣコマンドが受信された
動作  −  ＳｃｈｅｄｕｌｅレジスタはＣＰＵがｕＰアドレス線に発生した値をラッチする。この値は実行のためスケジューリングすべきタスクのＴＣＢ名である。
【００９２】
３．ＳＥＴＵＰ  ＭＡＴＣＨ  ＣＭＤ  −  Ｓｃｈｅｄｕｌｅユーティリティルを始める。「Ｍａｔｃｈ＞．」コマンドを設定する。
動作  −  ＣＭＤ（０〜３）線をコマンド「Ｍａｔｃｈ＞Ａ」で設定する。Ｄ（０〜７）線はＳｃｈｅｄｕｌｅレジスタにある値を得る。ＱＥＮ（０〜３）はＣＰＵＱ値をこの動作がＣＰＵキューで行われることを示すように設定する。
【００９３】
４．ＦＩＮＩＳＨ  ＭＡＴＣＨ  ＣＭＤ  −  「一致」線をアサートする。
動作  −  最後の状態の動作のアサートを解除し、一致線をアサートする。
【００９４】
５．ＲＥＡＤ  ＭＡＴＣＨ＞  ＡＤＤ  −  最高優先度ｍａｔｃｈ＞アドレスに対するアドレス線を読み出す。
動作  −  ＡＤＤＲ（０〜７）にある値を一時レジスタに格納し、一致線のアサートを解除する。
【００９５】
６．ＳＥＴＵＰ  ＳＲ  ＣＭＤ  −  右シフトコマンドを設定する。
動作  −  一時レジスタにある値をＡＤＤＲ（０〜７）線に乗せる。ＣＭＤ（０〜３）線を「ＳＲ」（右シフト）コマンドに設定し、ＱＥＮ（０〜３）線をＣＰＵＱ値に等しく設定する（ＣＰＵキューに関する動作を示す）。
【００９６】
７．ＦＩＮＩＳＨ  ＳＲ  ＣＭＤ  −  右シフトコマンドを終了する。
動作  −  最後の動作のアサートを解除する。
【００９７】
８．ＳＥＴＵＰ  ＬＤ  ＣＭＤ  −  「ＬＤ」（ロード）コマンドの設定。
動作  −  ＣＭＤ（０〜３）線が「ＬＤＡ」コマンド値を得る。Ｄ（０〜７）線がＳｃｈｅｄｕｌｅレジスタの内容を得る。ＡＤＤＲ（０〜７）線が一時レジスタにある値を得る。ＱＥＮ（０〜３）線をＣＰＵＤＱ値に等しく設定する（ＣＰＵキューに関する動作を示す）。
【００９８】
９．ＦＩＮＩＳＨ  ＬＤ  ＣＭＤ  −  ロードコマンドを終了する。
動作  −  最後の状態の動作のアサートを解除する。
【００９９】
１０．ＳＥＴＵＰ  ＥＮＤ  ｕＰ  ＸＡＣＴＩＯＮ（ＣＰＵとのトランザクションを終了するように設定する
動作  −  ＤＴＡＣＫ（データ転送アクノーレッジ）をアサートする。
【０１００】
１１．ＥＮＤ  ｕＰ  ＸＡＣＴＩＯＮ  −  ＣＰＵとのトランザクションを終了する
動作  −  ＤＴＡＣＫ（データ転送アクノーレッジ）のアサートを解除する。
【０１０１】
１２．ＩＤＬＥ  −  上の状態１に行く
【０１０２】
この時点で、タスクのＴＣＢはＣＰＵキューに置かれている。最新のキュー情報を使用するためには、マイクロプロセッサ１０は「ＲＥＡＤ＿ＡＣＴＩＶＥＴＣＢ」コマンドを実行しなければならない。これに加えて、マイクロプロセッサ１０は、このタスクに実行を再開させたイベントを判定するために「ＲＥＡＤ＿ＥＶＥＮＴＣＡＳＥ」を実行することができる。これら動作はＳｃｈｅｄｕｌｅ、Ｓｕｓｐｅｎｄ、Ｓｉｇｎａｌ、Ｗａｉｔ、及びＤｅｌａｙを含むどんなユーティリティ呼び出しに対しても行うことができる。
【０１０３】
ＲＥＡＤ＿ＡＣＴＩＶＥＴＣＢコマンド
【０１０４】
１．ＩＤＬＥ  −  ＥＸＥＣチップ選択（ｃｓ）、ｎｔｓｔ、ｎｒｓｔ、及びｔｃｏ（タイマキャリ出力）のアサートを全て解除する。
【０１０５】
２．ＳＥＴＵＰ  ＲＤ  ＣＭＤ  −  「ＲＤ」（読み出し）コマンドの設定。
動作  −  ＣＭＤ（０〜３）線がコマンド「ＲＤＡ」（ワードＡを読み出す）を得る。ＱＥＮ（０〜３）線がＣＰＵＱ値を得る。ＡＤＤＲ（０〜７）線が０に（つまりＣＰＵキューの最初のロケーション  −キューの先頭−  に対して）設定される。
【０１０６】
３．ＷＲＩＴＥ  ＡＣＴＩＶＥＴＣＢ  ＲＥＧ  −  ＣＰＵキューの先頭にあるＴＣＢ名をアクティブＴＣＢレジスタに書き込む。
動作  −  アクティブＴＣＢレジスタに現在Ｄ（０〜７）線に現れている値が書き込まれる。これは、その優先度のため、ＣＰＵ資源を使用することになっている次のタスクのＴＣＢ名である。
【０１０７】
４．ＳＥＴＵＰ  ＥＮＤ  ｕＰ  ＸＡＣＴＩＯＮ  −  ＣＰＵによる処理を終るよう設定する。
動作  −  ＤＴＡＣＫ（データ転送アクノーレッジ）をアサートする。
イベント  −  ｃｓのアサートを解除する。
【０１０８】
５．ＥＮＤ  ｕＰ  ＸＡＣＴＩＯＮ  −  ＣＰＵによる処理を終了する。
動作  −  ＤＴＡＣＫ（データ転送アクノーレッジ）のアサートを解除する。
【０１０９】
６．ＩＤＬＥ（上の状態１）
【０１１０】
ＲＥＡＤ＿ＥＶＥＮＴＣＡＳＥコマンド
【０１１１】
１．ＩＤＬＥ  −  ＥＸＥＣチップ選択（ｃｓ）、ｎｔｓｔ、ｎｒｓｔ、及びｔｃｏ（タイマキャリ出力）のアサートを全て解除する。
【０１１２】
２．ＳＥＴＵＰ  ＲＤ  ＣＭＤ  −  「ＲＤ」（読み出し）コマンドを設定する。
動作  −  ＣＭＤ（０〜３）線が「ＲＤＢ」（ワードＢを読み出す）値に設定される。ＱＥＮ（０〜３）がＣＰＵＱ値に設定される。ＡＤＤＲ（０〜７）線が０に設定される。ＣＰＵキューの最初の要素のワードＢを読み出したいのである。
【０１１３】
３．ＷＲＩＴＥ  ＥＶＥＮＴＣＡＳＥ  ＲＥＧ  −  次のタスクのイベントケース値をイベントケースレジスタに書き込み、ＣＰＵで実行する。
動作  −  イベントケースレジスタが線Ｄ（０〜７）の値に等しく設定される。最後の状態の動作がアサート解除される。
【０１１４】
４．ＳＥＴＵＰ  ＥＮＤ  ｕＰ  ＸＡＣＴＩＯＮ  −  ＣＰＵとのトランザクションを終了するように設定する。
動作  −  ＤＴＡＣＫ（データ転送受領）をアサートする。
イベント  −  ｃｓのアサートを解除する。
【０１１５】
５．ＥＮＤ  ｕＰ  ＸＡＣＴＩＯＮ  −  ＣＰＵとのトランザクションを終了する。
動作  −  ＤＴＡＣＫ（データ転送アクノーレッジ）のアサートを解除する。
【０１１６】
６．ＩＤＬＥ（上の状態１）
【０１１７】
前述の説明は本発明の例示的解説に過ぎないことを理解すべきである。当業者は本発明から逸脱することなく種々の代案及び修正を工夫することができる。従って、本発明は特許請求の範囲に入るこのような代案、修正、及び変形を全て包含することを意図している。
【０１１８】
【効果】
以上詳細に説明したように、本発明によればイベントの発生に応答して優先度に基づいたタスク切替を極めてわずかのオーバーヘッドで実現することができる。
【図面の簡単な説明】
【図１】本発明の一実施例を用いたシステムの高レベルブロック図。
【図２】図１のシステムで使用されるＣＰＵキューのブロック図。
【図３】図２のＣＰＵキュー内のキュー要素のブロック図。
【図４】図３のキュー要素内のワード記憶部の更に詳細な論理回路図。
【図５】連想メモリセルの回路図。
【図６】本発明の一実施例で使用される一組のイベントカウントレジスタのブロック図。
【図７】本発明の一実施例で使用される遅延タイマのブロック図。
【図８】図１のコマンド及びステータスレジスタ内に含まれる一組の読み出し／書き込みレジスタの例を示す図。
【符号の説明】
１０：マイクロプロセッサ
１２：ＥＸＥＣモジュール
１４：コマンド及びステータスレジスタ
１６：キュー状態機械
１８：キューシステム
２０：ＣＰＵキュー
２２：遅延キュー
２４：イベントキュー
２８：遅延タイマ
３０：ポート制御モジュール
３５：キュー要素
３６：アドレスデコーダ
４０：レゾルバ／エンコーダ
４２，４４：ＬＡＳＴバス
４２’，４４’：ＮＥＸＴバス
５０，５６，５８：マルチプレクサ
５２，５４：ワード記憶部
７３：キュー要素論理モジュール
７６：デマルチプレクサ
７７：比較器
８１，８３：ワード線
８２，８４：ビット線
８５：ＣＭＯＳフリップフロップ
８８：一致線
１００：イベントカウンタ
１０２，１０４，１０６：イベントカウントレジスタ
１２０：書き込みレジスタ
１２２：読み出しレジスタ
【図１】
0003604091.tif 000003
【図２】
0003604091.tif 000004
【図３】
0003604091.tif 000005
【図４】
0003604091.tif 000006
【図５】
0003604091.tif 000007
【図６】
0003604091.tif 000008
【図７】
0003604091.tif 000009
【図８】
0003604091.tif 000010