JPH1124946A - タスクスケジューリング装置および方法 - Google Patents

Abstract

(57)【要約】 【課題】 システムの信頼性を高めることができるタス
クスケジューリング装置を提供する。 【解決手段】 スケジューリング調整機構によって、共
有資源と無関係な全てのタスクおよび共有資源にアクセ
スするタスクのうちから１つをプリエンプトスケジュー
リング機構に登録し、残った共有資源にアクセスするタ
スク全てをラウンドロビンスケジューリング機構に順序
付けて登録し、プリエンプトスケジューリング機構によ
るスケジューリングで共有資源にアクセスするタスクが
実行権を放棄（中断状態に遷移）した時、ラウンドロビ
ンスケジューリング機構に順序付けて登録された共有資
源にアクセスするタスクのうち先頭のものと入れ替え
る。そして、中断状態に遷移したタスクを中断要因が解
除された時にラウンドロビンスケジューリング機構の順
序付けの最後尾に登録する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、タスクスケジュー
リング装置および方法に関する。

【０００２】

【従来の技術】従来、マルチタスク間で共有資源アクセ
スを行う際、排他制御を必要とするシステムでは、以下
の方式により排他制御を実現していた。

【０００３】第１の方式では、各タスクで共有資源アク
セスの直前にオペレーティングシステム（ＯＳ）に対し
てセマフォ（アクセス権）を獲得し、共有資源アクセス
が終了すると、ＯＳに対してセマフォを返却することに
より排他制御を実現する。

【０００４】第２の方式では、ラウンドロビンスケジュ
ーリングを使用し、自タスクから明示的にＣＰＵ使用権
を放すまでタスクスイッチングをしないこと（ノンプリ
エンティブであること）を保証することにより排他制御
を実現する。

【０００５】

【発明が解決しようとする課題】しかしながら、上記従
来の排他制御方式には以下に掲げる問題があった。すな
わち、第１の方式では、共有資源に対するアクセス毎に
該当するセマフォの獲得、返却を行うので、オーバーヘ
ッドがかかってしまう（問題点１）。

【０００６】また、複雑なデータ構造中に複数の共有資
源が含まれ、複数のタスクからのアクセス時にもデータ
構造全体の整合性を保証する必要がある場合、セマフォ
を割り当てるための共有資源の切り出しが難しい（問題
点２）。

【０００７】さらに、複数の共有資源に対し、タスク毎
に異なる連続したアクセス順番を保証しなければならな
い場合、デッドロックする危険性がある（問題点３）。

【０００８】一方、第２の方式では、ラウンドロビンス
ケジューリングを用いることにより上記問題を解決して
いるが、イベントドリブンやタイムスライスによるプリ
エンブト（横取り）スケジューリングができないので、
共有資源をアクセスしているタスクがＣＰＵを占有して
実行し続けると、共有資源とは無関係なタスクであって
も実行されず、システム全体に影響を及ぼしてしまう
（問題点４）。

【０００９】また、タイムスライスによるプリエンプト
（横取り）スケジューリングができないので、複数の共
有資源がある場合、それぞれの共有資源毎の累積アクセ
ス時間を均等に割り振ることができず、アクセスするタ
スクの数が多い共有資源の方が累積アクセス時間が長く
なる（問題点５）。

【００１０】これらの問題のうち、１つまたは部分的に
解決する手段はいくつか提案されている。例えば、問題
点１を改善する手段として、特開平５−１２００３９号
公報では高速処理が必要なタスクは別にテーブルを設
け、資源の確保、解放処理を不要とする方式が提案され
ている。

【００１１】また、問題点３の単純なケースである１つ
の共有資源に対するタスクの優先度逆転現象（プライオ
リティインバージョン）に対応する手段として、特開平
５−２５０１８８号公報や特開平８−７７０２５号公報
に示されるように、共有資源占有期間のみタスクの優先
度を上げる方式が提案されている。

【００１２】そこで、本発明は、上記問題点１〜４、問
題点１〜３および問題点５、または問題点１〜５を解決
することにより、システムの信頼性を高めることができ
るタスクスケジューリング装置を提供することを目的と
する。

【００１３】

【課題を解決するための手段】上記目的を達成するため
に、本発明の請求項１に記載のタスクスケジューリング
装置は、マルチタスクプログラムのスケジューリングを
行うタスクスケジューリング装置において、スケジュー
リング調整機構と、プリエンプトスケジューリング機構
と、ラウンドロビンスケジューリング機構とを備え、共
有資源をアクセスするタスク群ではラウンドロビンスケ
ジューリングを用い、前記共有資源と無関係なタスク群
ではプリエンプトスケジューリングを用い、両タスク群
の間ではプリエンプトスケジューリングを実現する処理
を行うことを特徴とする。

【００１４】請求項２に記載のタスクスケジューリング
装置は、マルチタスクプログラムのスケジューリングを
行うタスクスケジューリング装置において、スケジュー
リング調整機構と、プリエンプトスケジューリング機構
と、ラウンドロビンスケジューリング機構とを備え、共
有資源毎にアクセスするタスク群をタスクグループとし
て切り出し、各タスクグループ内で独立してラウンドロ
ビンスケジューリングを用い、前記タスクグループの間
ではプリエンプトスケジューリングを実現する処理を行
うことを特徴とする。

【００１５】請求項３に記載のタスクスケジューリング
装置は、マルチタスクプログラムのスケジューリングを
行うタスクスケジューリング装置において、スケジュー
リング調整機構と、プリエンプトスケジューリング機構
と、ラウンドロビンスケジューリング機構とを備え、共
有資源毎にアクセスするタスク群をタスクグループとし
て切り出し、各タスクグループ内で独立してラウンドロ
ビンスケジューリングを用い、前記共有資源と無関係な
タスク群ではプリエンプトスケジューリングを用い、前
記タスクグループの間および前記タスクグループと前記
共有資源とは無関係なタスク群の間ではプリエンプトス
ケジューリングを実現する処理を行うことを特徴とす
る。

【００１６】請求項４に記載のタスクスケジューリング
方法は、マルチタスクプログラムのスケジューリングを
行うタスクスケジューリング方法において、共有資源を
アクセスするタスク群ではラウンドロビンスケジューリ
ングを用い、前記共有資源と無関係なタスク群ではプリ
エンプトスケジューリングを用い、両タスク群の間では
プリエンプトスケジューリングを実現する処理を行うこ
とを特徴とする。

【００１７】請求項５に記載のタスクスケジューリング
方法は、マルチタスクプログラムのスケジューリングを
行うタスクスケジューリング方法において、共有資源毎
にアクセスするタスク群をタスクグループとして切り出
し、各タスクグループ内で独立してラウンドロビンスケ
ジューリングを用い、前記タスクグループの間ではプリ
エンプトスケジューリングを実現する処理を行うことを
特徴とする。

【００１８】請求項６に記載のタスクスケジューリング
方法は、マルチタスクプログラムのスケジューリングを
行うタスクスケジューリング方法において、共有資源毎
にアクセスするタスク群をタスクグループとして切り出
し、各タスクグループ内で独立してラウンドロビンスケ
ジューリングを用い、前記共有資源と無関係なタスク群
ではプリエンプトスケジューリングを用い、前記タスク
グループの間および前記タスクグループと前記共有資源
とは無関係なタスク群の間ではプリエンプトスケジュー
リングを実現する処理を行うことを特徴とする。

【００１９】

【発明の実施の形態】本発明のタスクスケジューリング
装置および方法の実施の形態について説明する。

【００２０】［第１の実施の形態］第１の実施形態で
は、前述した問題点１〜問題点４を解決するタスクスケ
ジューリング装置について説明する。図１は第１の実施
形態におけるタスクスケジューリング装置が適用された
システムの構成を示すブロック図である。タスクスケジ
ューリング装置が適用されるシステムはＣＰＵ１４０、
ＲＯＭ１１０、ＲＡＭ１００、タイマ１５０およびＩ／
Ｏインターフェース１３０から構成される。

【００２１】図において、ＲＯＭ１１０にはＲＡＭ１０
０内の全てのコードおよび初期化データが格納されてい
る。ＣＰＵ１４０にリセットがかかると、システムは立
ち上がり、ＲＯＭ１１０に格納されているコードおよび
データを全てＲＡＭ１００にコピーし、スケジューリン
グ調整機構６００の初期化処理６１０に起動をかける
（図２参照）。

【００２２】初期化処理６１０では、Ｉ／Ｏインターフ
ェース１３０およびタイマ１５０のハードウェアを初期
化することで、Ｉ／Ｏ割込み処理４００およびタイマ割
込み処理４１０を有効にする。

【００２３】プリエンプトスケジューリング機構７００
の初期化処理７２０（図３参照）、およびラウンドロビ
ンスケジューリング機構８００の初期化処理８１０（図
４参照）により、初期化データ５００を基にしてマルチ
タスク環境を立ち上げる。

【００２４】この時点で、共有資源（変数データ等）２
００にアクセスしないタスク群（タスク１（３２０）、
タスク２（３３０）、…）、およびアクセスするタスク
群（タスクＡ（３００）、タスクＢ（３１０）、…）の
うち１つだけ（タスクＡ（３００））がプリエンプトス
ケジューリング機構７００に登録され、それ以外のタス
ク群（タスクＢ（３１０）、…）はラウンドロビンスケ
ジューリング機構８００に登録される。

【００２５】プリエンプトスケジューリング機構７００
に登録されたタスク群（タスク１（３２０）、タスク２
（３３０）…、タスクＡ（３００））のうち、スケジュ
ーリング処理７３０により、実行待キュー７７０の中で
優先順位が最も高く、待ち行列の最も先端のタスク１つ
だけがＣＰＵ１４０を占有して実行される。

【００２６】プリエンプトスケジューリング機構７００
に登録されたタスクＡが中断状態９０５に遷移した時、
ラウンドロビンスケジューリング機構８００に登録され
たタスク群（タスクＢ（３１０）、……）のうち、ラウ
ンドロビンキュー８４０の先頭のタスク（タスクＢ）１
つだけを取り出し、プリエンプトスケジューリング機構
７００に追加登録する（図５参照）。

【００２７】タスクＡ（３００）は中断状態９０５が解
除されたタイミングで、プリエンプトスケジューリング
機構７００から削除され、タスクＢ（３１０）の代わり
にラウンドロビンスケジューリング機構８００に登録さ
れる。

【００２８】このように、共有資源をアクセスするタス
ク群（タスクＡ（３００）、タスクＢ（３１０）、…
…）ではラウンドロビンスケジューリングを用いること
により、共有資源と無関係なタスク群（タスク１（３２
０）、タスク２（３３０）、……）ではプリエンプト
（横取り）スケジューリングを用いることにより、両タ
スク群の間でプリエンプト（横取り）スケジューリング
を行う。

【００２９】以下に、タスクスケジューリング装置の構
成および動作を、図面に基づいて詳細に説明する。図２
はスケジューリング調整機構６００の構成を示す図であ
る。スケジューリング調整機構６００が装備する処理６
０１は、初期化処理６１０、中断処理６２０、中断解除
処理６４０およびタイマ割込み処理６６０である。ま
た、スケジューリング調整機構６００が保持するデータ
６０２は共有資源管理テーブル６８０である。

【００３０】図３はプリエンプトスケジューリング機構
７００の構成を示す図である。プリエンプトスケジュー
リング機構７００が装備する処理７０１は、初期化処理
７２０、スケジューリング処理７３０、指定実行待キュ
ー後尾へ追加処理７４０、指定実行待キューからの取得
処理７４１、中断キュー後尾へ追加処理７４２、中断キ
ューからの取得処理７４３である。プリエンプトスケジ
ューリング機構７００が保持するデータは、現在ＣＰＵ
を占有しているタスクを示す現実行タスク７０３、各タ
スク毎にタスク状態などを管理するＴＣＢ（タスクコン
トロールブロック）７５０である。

【００３１】また、プリエンプトスケジューリング機構
７００はタスクのスケジューリングを実行するための実
行待キュー７７０および中断キュー７９０も保持してい
る。実行待キュー７７０は、優先順位毎に実行待状態９
０３のタスクのＴＣＢ７５０をリストに保持し、その並
び順を待ち行列としてＦＩＦＯのキューとして管理す
る。プリエンプトスケジューリング機構７００の処理７
０１は、これらのキューにリンクされたＴＣＢ７５０の
中で、共有資源にアクセスするタスクのＴＣＢ７５０は
１つだけ（図３ではタスクＡ（７７７））であることを
保証する。中断キュー７９０は、中断状態９０５のタス
クのＴＣＢ７５０をリストに保持し、その並び順を待ち
行列としてＦＩＦＯのキューとして管理する。

【００３２】図４はラウンドロビンスケジューリング機
構８００の構成を示す図である。ラウンドロビンスケジ
ューリング機構８００が装備する処理８０１は、初期化
処理８１０、ラウンドロビンキュー後尾へ追加処理８３
０およびラウンドロビンキューからの取得処理８３１で
ある。また、ラウンドロビンスケジューリング機構８０
０はタスクスケジューリングを実現するためのラウンド
ロビンキュー８４０を保持する。ラウンドロビンキュー
８４０は、ラウンドロビン待状態９０４のタスクのＴＣ
Ｂ７５０をリストに保持し、その並び順を待ち行列とし
てＦＩＦＯのキューとして管理する。

【００３３】図５はタスクの状態遷移を示す図である。
タスクは初期状態９０２、実行待状態９０３、実行状態
９０１、中断状態９０５、ラウンドロビン待状態９０４
の各状態を取り得る。それぞれの状態間の遷移は、スケ
ジューリング処理７３０、中断処理６２０、中断解除処
理６４０、初期化処理７２０、初期化処理８１０、タイ
マ割込み処理６６０の起動によって発生する。タスクの
状態は各タスク毎にＴＣＢ７５０内のタスク状態７５６
に保持される（図８参照）。

【００３４】初期状態９０２は、ＴＣＢ７５０が確保さ
れた直後の立ち上がり時の状態である。実行状態９０１
は、タスクがＣＰＵ１４０を占有して実行している状態
で優先順位が最高で待ち行列の先頭の１タスクだけがな
り得る状態である。この状態のタスクはＴＣＢ７５０が
実行待キュー７７０にリンクされている（図３参照）。

【００３５】実行待状態９０３は実行可能であるが、優
先順位等の関係で他のタスクがＣＰＵ１４０を占有して
いるためにこれが空くのを待っている状態である。この
状態のタスクではＴＣＢ７５０が実行待キュー７７０に
リンクされている。

【００３６】中断状態９０５はＩ／Ｏ割込処理４００な
どからのイベント待ちの状態であり、この状態の間では
ＣＰＵ１４０が空いても実行されることはない。この状
態のタスクではＴＣＢ７５０が中断キュー７９０にリン
クされている。

【００３７】ラウンドロビン待状態９０４は共有資源２
００にアクセスするタスク群だけが遷移可能な状態であ
り、共有資源２００をアクセスするタスクがすでに実行
待状態９０３または実行状態９０１に１つ存在する場
合、このタスクが中断状態９０５に遷移するのを待って
いる状態である。この状態のタスクではＴＣＢ７５０が
ラウンドロビンキュー８４０にリンクされている。

【００３８】図６は初期化データの構成を示す図であ
る。同図を参照すると、初期化データ５００は全タスク
数５１０および全タスク情報５２０を含んで格納されて
いる。全タスク情報５２０は各タスク毎にタスクの実行
アドレス（ＰＣ）、優先順位、共有資源アクセスフラグ
５２１〜５３１を含んで格納されている。共有資源アク
セスフラグ５２１〜５３１には、共有資源にアクセスす
るタスク５２１〜５２５では値１がセットされ、アクセ
スしないタスク５２６〜５３１では値０がセットされ
る。

【００３９】図７は共有資源管理テーブルを示す図であ
る。同図を参照すると、共有資源管理テーブル６８０
は、実行待キュー７７０にリンクされている共有資源を
アクセスするタスクの数を表す実行待共有資源アクセス
タスク数６８２、およびラウンドロビンキュー８４０に
リンクされているタスクの数を表すラウンドロビン待タ
スク数６８１を含んで格納されている。

【００４０】図８はタスクコントロールブロックの構成
を示す図である。同図を参照すると、ＴＣＢ（タスクコ
ントロールブロック）７５０はタスクＩＤ７５２、タス
クアドレス（ＰＣ）７５３、タスクスタックアドレス
（ＳＰ）７５４、優先順位７５５、タスク状態７５６、
リンクポインタ７５７、共有資源アクセスフラグ７５
８、その他の付加情報７５９を含んで格納されている。

【００４１】ＴＣＢ７５０は各タスク毎にデータを保持
し（ＴＣＢ［０］７５１、ＴＣＢ［１］７６０、ＴＣＢ
［２］７６１…）、プリエンプトスケジューリング機構
７００のデータとして保持されている。タスク状態７５
６の取り得る値は初期状態９０２、実行待状態９０３、
実行状態９０１、中断状態９０５、ラウンドロビン待状
態９０４である。これらの状態遷移およびその発生要因
は図５に示した通りである。

【００４２】つぎに、スケジューリング調整機構６００
の初期化処理６１０について説明する。図９は初期化処
理６１０の手順を示すフローチャートである。この初期
化処理６１０はＣＰＵリセット後の最初の処理としてＣ
ＰＵ１４０によって実行される。

【００４３】まず、ハードウェア割込みを禁止する。
（ステップＳ６１１）。ＲＯＭ１１０からＲＡＭ１００
にコードおよび初期化データ５００をコピーする（ステ
ップＳ６１２）。プリエンプトスケジューリング機構７
００の初期化処理７２０をコールする（ステップＳ６１
３）。ラウンドロビンスケジューリング機構８００の初
期化処理８１０をコールする（ステップＳ６１４）。

【００４４】ハードウェア割込みを許可する（ステップ
Ｓ６１５）。プリエンプトスケジューリング機構７００
のスケジューリング処理７３０を起動し（ステップＳ６
１６）、スケジューリング調整機構の初期化処理６１０
を終了する。

【００４５】スケジューリング処理７３０はリターンせ
ず、実行待キュー７７０の中で最も優先順位の高く、最
も待ち行列の先頭のタスクにＣＰＵ１４０の占有を与え
て実行を開始する。

【００４６】その後、タスクスケジューリングが発生す
るタイミングは、タスクから中断処理６２０または中断
解除処理６４０が起動された場合、Ｉ／Ｏ割込み処理４
００から中断解除処理６４０が起動された場合、タイマ
割込み４１０からタイマ割込み処理６６０が起動された
場合である。

【００４７】図１０はプリエンプトスケジューリング機
構７００の初期化処理７２０の手順を示すフローチャー
トである。この処理はスケジューリング調整機構６００
の初期化処理６１０から１度だけコールされる。

【００４８】まず、初期化データ５００の情報を基に各
タスクのＴＣＢ７５０の初期化（ＴＣＢ［０］−ＴＣＢ
［１０］（タスク１−６，Ａ−Ｅ））を行う（ステップ
Ｓ７２１）。

【００４９】このステップＳ７２１の処理では、初期化
データ５００の全タスク数５１０を基に全ＴＣＢの領域
をＲＡＭ１００に確保する（７２１ａ）。初期化データ
５００の全タスク情報５２０を基にＴＣＢ７５０内のタ
スクアドレス（ＰＣ）７５３／優先順位７５５／共有資
源アクセスフラグ７５８の値をセットする（７２１
ｂ）。タスクＩＤ７５２を割り振り、タスクスタックの
領域をＲＡＭ１００に確保し、スタックポインタをタス
クスタックアドレス（ＳＰ）７５４にセットする（７２
１ｃ）。全ＴＣＢのタスク状態７５６を実行待状態９０
３にセットする（７２１ｄ）。その他の付加情報７５９
があれば初期化する（７２１ｅ）。

【００５０】つづいて、ＴＣＢ［０］からＴＣＢ［（全
タスク数５１０）−１］まで以下の処理を繰り返す（ス
テップＳ７２２）。ＴＣＢ７５０の共有資源アクセスフ
ラグ７５８が値０である共有資源にアクセスしないタス
クのＴＣＢ（タスク１，２，３，４，５，６）アドレス
を優先順位７５５に対応する実行待キュー７７０の後尾
に追加する。

【００５１】現実行タスク７０３をアイドルタスクとす
る（ステップＳ７２３）。Ｉ／Ｏインターフェーおよび
タイマを初期化し、同じ優先順位のタイムスライススケ
ジューリングを必要とする場合、タイマ割込みベクタに
タイマ割込み処理６６０を登録する（ステップＳ７２
４）。そして、呼び出し元にリターンする。

【００５２】図１１はラウンドロビンスケジューリング
機構８００の初期化処理８１０の手順を示すフローチャ
ートである。この処理はスケジューリング調整機構６０
０の初期化処理６１０から１度だけコールされる。ま
ず、ループカウンタＣｏｕｎｔを初期化する（ステップ
Ｓ８１１）。ラウンドロビン待タスク数６８１を値０に
初期化する（ステップＳ８１２）。

【００５３】ＴＣＢ［０］からＴＣＢ［（全タスク数５
１０）−１］まで以下の処理を繰り返す（ステップ８１
３）。つまり、ＴＣＢ［Ｃｏｕｎｔ］の共有資源アクセ
スフラグ７５８が値１である（共有資源にアクセスする
タスク）か否かを判別する（ステップ８１４）。値１で
ある場合、ループを終了し、ステップＳ８１６の処理に
移行する。一方、ＴＣＢ［Ｃｏｕｎｔ］の共有資源アク
セスフラグ７５８が値１でなければ、Ｃｏｕｎｔをイン
クリメントする（ステップＳ８１５）。

【００５４】最初に見つかった共有資源をアクセスする
タスクを示すＴＣＢ［Ｃｏｕｎｔ］を優先順位７５５に
対応する実行待キュー７７０の後尾に追加する（ステッ
プＳ８１６）。ループカウンタＣｏｕｎｔをインクリメ
ントする（ステップＳ８１７）。実行待共有資源アクセ
スタスク数６８２に値１をセットする（ステップＳ８１
８）。

【００５５】ラウンドロビンキュー８４０に残りの共有
資源をアクセスするタスク群を追加するため、ＴＣＢ
［Ｃｏｕｎｔ］からＴＣＢ［（全タスク数５１０）−
１）］間で以下の処理を繰り返す（ステップＳ８１
９）。ＴＣＢ［Ｃｏｕｎｔ］の共有資源アクセスフラグ
７５８が値１である（共有資源にアクセスするタスク）
か否かを判別する（ステップＳ８２０）。値１である場
合、ＴＣＢ［Ｃｏｕｎｔ］のタスク状態７５６をラウン
ドロビン待９０４とし、ラウンドロビンキュー８４０の
後尾に追加し（ステップＳ８２１）、ラウンドロビン待
タスク数６８１をインクリメントし（ステップＳ８２
２）、ループカウンタＣｏｕｎｔをインクリメントする
（ステップＳ８２３）。一方、ステップＳ８２０でＴＣ
Ｂ［Ｃｏｕｎｔ］の共有資源アクセスフラグ７５８が値
１でなければ、Ｃｏｕｎｔをインクリメントする（ステ
ップＳ８２３）。また、ステップＳ８１３あるいはステ
ップＳ８１９で全て繰り返した場合、呼び出し元にリタ
ーンする。

【００５６】図１２はプリエンプトスケジューリング機
構７００のスケジューリング処理７３０の手順を示すフ
ローチャートである。この処理は、スケジューリング調
整機構６００の初期化処理６１０、中断処理６２０、中
断解除処理６４０、タイマ割込み処理６６０から起動さ
れる。

【００５７】実行待キュー７７０に基づきタスクスケジ
ューリングを実現する。まず、現実行タスク７０３が最
高優先順位の実行待キュー７７０の先頭タスクと等しい
か否かを判別する（ステップＳ７３１）。等しければリ
ターンする。等しくなければ、タスクスイッチを行うた
めに現実行タスク７０３のＴＣＢ７５０（タスクアドレ
ス７５３、タスクスタックアドレス７５４）にＣＰＵ１
４０内のＰＣ（プログラムカウンタ）とＳＰ（スタック
ポインタ）を保存し、タスク状態７５６を実行待状態９
０３にする（ステップＳ７３２）。

【００５８】最高優先順位の実行待キュー７７０の先頭
タスクのＴＣＢ７５０（タスクアドレス７５３、タスク
スタックアドレス７５４）から、ＣＰＵ１４０内のＰＣ
（プログラムカウンタ）とＳＰ（スタックポインタ）を
セットし、タスク状態７５６を実行状態９０１にする
（ステップＳ７３３）。

【００５９】現実行タスク７０３を最高優先順位の実行
待キュー７７０の先頭タスクとする（ステップＳ７３
４）。そして、タスクをスタートさせる（ステップＳ７
３５）。

【００６０】図１３はスケジューリング調整機構６００
の中断処理６２０の手順を示すフローチャートである。
この処理はタスクから任意に起動され、指定タスクを中
断状態９０５に遷移させる処理である。

【００６１】まず、指定した中断タスクのＴＣＢ７５０
内の共有資源アクセスフラグ７５８が値１と等しいか否
かを判別する（ステップＳ６２１）。等しくなければ、
中断すべきタスクは共有資源にアクセスしないタスクで
あるので、中断タスクのＴＣＢ７５０を実行待キュー７
７０から取り出し（ステップＳ６２２）、中断キュー７
９０の後尾に追加し、タスク状態７５６を中断状態９０
５にし（ステップＳ６２３）、スケジューリング処理７
３０を起動する（ステップＳ６２３Ａ）。

【００６２】指定した中断タスクのＴＣＢ７５０内の共
有資源アクセスフラグ７５８が値１と等しければ、中断
すべきタスクは共有資源にアクセスするタスクであるの
で、中断タスクのＴＣＢを実行待キュー７７０から取り
出し（ステップＳ６２４）、実行待共有資源アクセスタ
スク数（６８２）に値０をセットし（ステップＳ６２
５）、ステップＳ６２４で取り出したＴＣＢを中断キュ
ー７９０の後尾に追加し、タスク状態７５６を中断状態
９０５にする（ステップＳ６２６）。

【００６３】ラウンドロビン待タスク数６８１が値０に
等しいか否かを判別する（ステップＳ６２７）。値０に
等しければ、特にラウンドロビン待状態９０４のタスク
は存在しないので、スケジューリング処理７３０を起動
する（ステップＳ６３２）。

【００６４】値０に等しくなければ、指定した共有資源
をアクセスするタスクが実行待状態９０３から中断状態
９０５に遷移したため、新たにラウンドロビン待状態９
０４の共有資源をアクセスするタスク群のうちから１タ
スクを実行待状態９０３に遷移させる。まず、ラウンド
ロビンキュー８４０の先頭タスクのＴＣＢ７５０を取り
出し（ステップＳ６２８）、ラウンドロビン待タスク数
６８１をデクリメントし（ステップＳ６２９）、ステッ
プ６２８で取り出したＴＣＢを該当する優先順位７５５
の実行待キュー７７０の後尾へ追加し、タスク状態７５
６を実行待状態９０３にする（ステップＳ６３０）。

【００６５】実行待共有資源アクセスタスク数（６８
２）に値１をセットする（ステップ６３１）。スケジュ
ーリング処理７３０を起動する（ステップ６３２）。

【００６６】図１４はスケジューリング調整機構６００
の中断解除処理６４０の手順を示すフローチャートであ
る。この処理はタスクまたはＩ／Ｏ割込み処理から任意
に起動される。指定タスクを中断状態９０５から実行待
状態９０３またはラウンドロビン待状態９０４に遷移さ
せる処理である。

【００６７】まず、指定した中断状態を解除したいタス
クのＴＣＢ７５０内の共有資源アクセスフラグ７５８が
値１に等しいか否かを判別する（ステップＳ６４１）。
等しくなければ、中断状態を解除すべきタスクは共有資
源にアクセスしないタスクであるので、中断タスクのＴ
ＣＢ７５０を中断キュー７９０から取り出し（ステップ
Ｓ６４２）、該当する優先順位７５５の実行待キュー７
７０の後尾へ追加し、タスク状態７５６を実行待状態９
０３にし（ステップＳ６４３）、スケジューリング処理
７３０を起動する（ステップＳ６４３Ａ）。

【００６８】指定した中断状態を解除したいタスクのＴ
ＣＢ７５０内の共有資源アクセスフラグ７５８が値１に
等しければ、中断すべきタスクは共有資源にアクセスす
るタスクであるので、中断タスクのＴＣＢ７５０を中断
キュー７９０から取り出す（ステップＳ６４４）。

【００６９】ラウンドロビン待タスク数６８１が値０に
等しいか否かを判別する（ステップＳ６４５）。値０に
等しくなければ、ラウンドロビン待状態９０４のタスク
が既に存在するので、ステップＳ６４４で取り出したＴ
ＣＢをラウンドロビンキュー８４０の後尾へ追加し、タ
スク状態７５６をラウンドロビン待状態９０４にし（ス
テップＳ６４７）、ラウンドロビン待タスク数６８１を
インクリメントし（ステップＳ６４８）、リターンす
る。

【００７０】ステップＳ６４５で値０に等しければ、ラ
ウンドロビン待状態９０４のタスクは存在しないので、
実行待共有資源アクセスタスク数（６８２）が値０に等
しいか否かを判別する（ステップＳ６４６）。値０に等
しくなければ、既に共有資源をアクセスするタスク群の
うちから１タスクが実行待状態９０３であるため、ステ
ップＳ６４４で取り出したＴＣＢをラウンドロビンキュ
ー８４０の後尾へ追加し、タスク状態７５６をラウンド
ロビン待状態９０４にし（ステップＳ６４７）、ラウン
ドロビン待タスク数６８１をインクリメントし（ステッ
プＳ６４８）、リターンする。

【００７１】ステップＳ６４６で値０に等しければ、共
有資源をアクセスするタスク群のうち、実行待状態９０
３のタスクは存在しないので、ステップＳ６４４で取り
出したＴＣＢを該当する優先順位７５５の実行待キュー
７７０の後尾へ追加し、タスク状態７５６を実行待状態
９０３にする（ステップＳ６４９）。実行待共有資源ア
クセスタスク数（６８２）に値１をセットする（ステッ
プＳ６５０）。スケジューリング処理７３０を起動する
（ステップＳ６５１）。

【００７２】図１５はスケジューリング調整機構６００
のタイマ割込み処理６６０の手順を示すフローチャート
である。この処理は、タイマ割込み発生時、タイマ割込
み処理４１０から起動される。最高優先順位の実行待キ
ュー７７０内にリンクされているタスクをタイムスライ
ス（時分割）スケジューリングさせる処理である。タイ
ムスライスを実行したくなければ起動しなくてもよい。

【００７３】まず、最高優先順位の実行待キュー７７０
から先頭タスクを取り出し（ステップＳ６６１）、同じ
優先順位の実行待キュー７７０の後尾へ追加する（ステ
ップＳ６６２）。スケジューリング処理７３０を起動す
る（ステップＳ６６３）。

【００７４】［第２の実施形態］第２の実施形態では、
前述した問題点１〜問題点５を解決するタスクスケジュ
ーリング装置について説明する。図１６は第２の実施形
態におけるタスクスケジューリング装置が適用されたシ
ステムの構成を示す図である。第２の実施形態では、前
記第１の実施形態と異なり、共有資源が複数存在する。
共有資源１（２００）にはタスクＡ（３００）およびタ
スクＢ（３１０）がアクセスし、共有資源２（２１０）
にはタスクＸ（３４０）およびタスクＹ（３５０）がア
クセスする。

【００７５】図１７〜図２４は第２の実施形態において
前記第１の実施形態と異なる処理およびデータ構造を持
つ部分だけを示す。図２、図３、図５、図９、図１２、
図１５は前記第１の実施形態と同様の処理およびデータ
構造である。以降の説明では、図１６〜図２４、図２、
図３、図５、図９、図１２、図１５に示したものを使用
し、前記第１の実施形態と同一の構成要素には同一の符
号を使用する。

【００７６】図１６に示すＲＯＭ１１０には、ＲＡＭ１
００に示される全てのコードおよび初期化データが格納
されている。ＣＰＵ１４０にリセットがかかると、シス
テムは立ち上がり時、これらを全てＲＡＭ１００にコピ
ーし、スケジューリング調整機構６００の初期化処理６
１０に起動をかける。

【００７７】初期化処理６１０では、Ｉ／Ｏインターフ
ェース１３０およびタイマ１５０のハードウェアの初期
化を行うことで、Ｉ／Ｏ割込み処理４００およびタイマ
割込み処理４１０を有効にし、プリエンプトスケジュー
リング機構７００の初期化処理７２０、ラウンドロビン
スケジューリング機構８００の初期化処理８１０によ
り、初期化データ５００を基にマルチタスク環境を立ち
上げる。

【００７８】この時点で、全共有資源にアクセスしない
タスク群（タスク１（３２０）、タスク２（３３０）、
……）および共有資源１（２００）にアクセスするタス
ク群（タスクＡ（３００）、タスクＢ（３１０）、…
…）のうち１つだけ（タスクＡ（３００））および共有
資源２（２１０）にアクセスするタスク群（タスクＸ
（３４０）、タスクＹ（３５０）、……）のうち１つだ
け（タスクＸ（３４０））がプリエンプトスケジューリ
ング機構７００に登録され、それ以外のタスク群（タス
クＢ（３１０）、……およびタスクＹ（３５０）、…
…）はラウンドロビンスケジューリング機構８００に共
有資源毎にラウンドロビングループを作って登録され
る。

【００７９】プリエンプトスケジューリング機構７００
に登録されたタスク群（タスク１（３２０）、タスク２
（３３０）……、タスクＡ（３００）、タスクＸ（３４
０））のうち、スケジューリング処理７３０により実行
待キュー７７０内で優先順位が最も高く、待ち行列の最
も先頭のタスク１つだけがＣＰＵ１４０を占有して実行
される。

【００８０】プリエンプトスケジューリング機構７００
に登録されたタスクＡが中断状態９０５に遷移したと
き、ラウンドロビンスケジューリング機構８００のラウ
ンドロビングループ［１］８４１に登録されたタスク群
（タスクＢ（８４２）、タスクＣ（８４３）……）のう
ち、ラウンドロビングループ［１］８４１のキューの先
頭のタスク（タスクＢ８４２］１つだけを取り出し、プ
リエンプトスケジューリング機構７００に追加登録す
る。タスクＡ（３００）は中断状態９０５が解除された
タイミングで、プリエンプトスケジューリング機構７０
０から削除され、タスクＢ（８４２）の代わりにラウン
ドロビンスケジューリング機構８００のラウンドロビン
グループ［１］８４１に登録される。

【００８１】同様にプリエンプトスケジューリング機構
７００に登録されたタスクＸが中断状態９０５に遷移し
たとき、ラウンドロビンスケジューリング機構８００に
ラウンドロビングループ［２］８４６に登録されたタス
ク群（タスクＹ（８４７）、タスクＺ（８４８）……）
のうち、ラウンドロビングループ（２）８４６のキュー
の先頭のタスク（タスクＹ８４７）１つだけを取り出
し、プリエンプトスケジューリング機構７００に追加登
録する。タスクＸ（３４０）は中断状態９０５が解除さ
れたタイミングで、プリエンプトスケジューリング機構
７００から削除され、タスクＹ（８４７）の代わりにラ
ウンドロビンスケジューリング機構８００のラウンドロ
ビングループ［２］８４６に登録される。

【００８２】このように、共有資源１（２００）をアク
セスするタスク群（タスクＡ（３００）、タスクＢ（３
１０）、……）においてはラウンドロビングループ
［１］８４１でラウンドロビンスケジューリングを用
い、共有資源２（２１０）をアクセスするタスク群（タ
スクＸ（３４０）、タスクＹ（３５０）、……）におい
てはラウンドロビングループ［２］８４６でラウンドロ
ビンスケジューリングを用い、共有資源と無関係なタス
ク群（タスク１（３２０）、タスク２（３３０）、…
…）においてはプリエンプト（横取り）スケジューリン
グを用い、これら３者のタスク群の間ではプリエンプト
（横取り）スケジューリングを行う。

【００８３】以下に、第２の実施形態のタスクスケジュ
ーリング装置の構成および動作を、図面に基づいて詳細
に説明するが、前記第１の実施形態と異なる箇所につい
て詳細に説明する。

【００８４】図１７はラウンドロビンスケジューリング
機構８００の構成を示す図である。ラウンドロビンスケ
ジューリング機構８００が装備する処理８０１は、初期
化処理８１０、指定ラウンドロビンキュー後尾へ追加処
理８３２、指定ラウンドロビンキューからの取得処理８
３３である。また、タスクスケジューリングを実現する
ためにラウンドロビンキュー８４０を保持している。

【００８５】ラウンドロビンキュー８４０は、ラウンド
ロビン待状態９０４のタスクのＴＣＢ７５０を共有資源
毎にリストに保持し、その並び順をラウンドロビングル
ープ毎（ラウンドロビングループ［１］８４１、ラウン
ドロビングループ［２］８４６、ラウンドロビングルー
プ［３］８５１）に待ち行列としてＦＩＦＯのキューと
して管理する。

【００８６】図１８は初期化データの構成を示す図であ
る。初期化データ５００は全タスク数５１０、全共有資
源グループ数５１１および全タスク情報５４０を含んで
格納されている。全タスク情報５４０は、各タスク毎に
タスクの実行アドレス（ＰＣ）、優先順位、共有資源ア
クセスグループ（５４１−５５１）を含んで格納されて
いる。共有資源アクセスグループ（５４１−５５１）に
は共有資源毎にグループ番号が割り振られ、タスクＡ−
Ｃ（５４１−５４３）には値１、タスクＸ−Ｚ（５４４
−５４６）には値２、タスクＩ−Ｋ（５４７−５４９）
には値３、アクセスしないタスク１−２（５５０−５５
１）には値０をセットする。

【００８７】図１９は共有資源管理テーブルを示す図で
ある。共有資源管理テーブル６８０は、共有資源毎（グ
ループ［１］６９１、グループ［２］６９４、グループ
［３］６９７）にグループ分けされた形で、実行待キュ
ー７７０にリンクされている共有資源をアクセスするタ
スクの数を表す実行待共有資源アクセスタスク数６９
２，６９５，６９８およびラウンドロビングループ（共
有資源）毎にラウンドロビンキュー８４０にリンクされ
ているタスクの数を表すラウンドロビン待タスク数６９
３，６９６，６９９を含んで格納されている。

【００８８】図２０はタスクコントロールブロックの構
成を示す図である。ＴＣＢ（タスクコントロールブロッ
ク）７５０は、タスクＩＤ７５２、タスクアドレス（Ｐ
Ｃ）７５３、タスクスタックアドレス（ＳＰ）７５４、
優先順位７５５、タスク状態７５６、リンクポインタ７
５７、共有資源アクセスグループ７６５、その他の付加
情報７５９を含んで格納されている。

【００８９】ＴＣＢ７５０は各タスク毎にデータを保持
し、ＴＣＢ［０］７５１、ＴＣＢ［１］７６０、ＴＣＢ
［２］７６１およびプリエンプトスケジューリング機構
７００のデータとして保持されている。

【００９０】タスク状態７５６の取り得る値は初期状態
９０２、実行待状態９０３、実行状態９０１、中断状態
９０５、ラウンドロビン待状態９０４である。状態遷移
およびその発生要因は図５に示す通りである。

【００９１】図２１はプリエンプトスケジューリング機
構７００の初期化処理７２０の手順を示すフローチャー
トである。この処理はスケジューリング調整機構６００
の初期化処理６１０から１度だけコールされる。

【００９２】まず、初期化データ５００の情報を基に各
タスクのＴＣＢ７５０の初期化（ＴＣＢ［０］−ＴＣＢ
［１０］（タスク１−３，Ａ−Ｃ，Ｘ−Ｚ，Ｉ−Ｊ））
を行う（ステップＳ７２１Ａ）。このステップＳ７２１
Ａの処理では、初期化データ５００の全タスク数５１０
を基に全ＴＣＢの領域をＲＡＭ１００に確保する（７２
１ａ）。初期化データ５００の全タスク情報５２０を基
にＴＣＢ７５０内のタスクアドレス（ＰＣ）７５３／優
先順位７５５／共有資源アクセスグループ７６５の値を
セットする（７２１ｂ）。

【００９３】タスクＩＤ７５２を割り振り、タスクスタ
ックの領域をＲＡＭ１００に確保し、スタックポインタ
をタスクスタックアドレス（ＳＰ）７５４にセットする
（７２１ｃ）。全ＴＣＢのタスク状態７５６を実行待状
態９０３にセットする（７２１ｄ）。その他の付加情報
７５９があれば初期化する（７２１ｅ）。

【００９４】ＴＣＢ［０］からＴＣＢ［全タスク数（５
１０）−１］まで以下の処理を繰り返す（ステップＳ７
２２Ａ）。ＴＣＢ７５０の共有資源アクセスグループ７
６５が値０である共有資源にアクセスしないタスクのＴ
ＣＢ（タスク１，２，３）アドレスを優先順位７５５に
対応する実行待キュー７７０の後尾に追加する。

【００９５】現実行タスク７０３をアイドルタスクとす
る（ステップＳ７２３）。Ｉ／Ｏインタフェースおよび
タイマを初期化し、同じ優先順位のタイムスライススケ
ジューリングを必要とする場合、タイマ割込みベクタに
タイマ割込み処理６６０を登録する（ステップＳ７２
４）。この後、呼び出し元にリターンする。

【００９６】図２２はラウンドロビンスケジューリング
機構８００の初期化処理８１０の手順を示すフローチャ
ートである。この処理はスケジューリング調整機構６０
０の初期化処理６１０から１度だけコールされる。ま
ず、以降の処理全てをループカウンタＣｏｕｎｔ２＝１
からＣｏｕｎｔ２＝全共有資源グループ数５１１まで繰
り返したか否かを判別する（ステップＳ８１０Ａ）。繰
り返した場合、そのままリターンし、繰り返していない
場合、ループカウンタＣｏｕｎｔを値０に初期化する
（ステップＳ８１１）。グループ［Ｃｏｕｎｔ２］のラ
ウンドロビン待タスク数（６９３、６９６あるいは６９
９）を値０に初期化する（ステップＳ８１２）。

【００９７】ＴＣＢ［０］からＴＣＢ［全タスク数（５
１０）−１］まで以下の処理を繰り返す（ステップＳ８
１３）。ＴＣＢ［Ｃｏｕｎｔ］の共有資源アクセスグル
ープ７６５が値０でない（共有資源にアクセスするタス
ク）か否かを判別する（ステップＳ８１４）。値０であ
る場合、ループを終了し、ステップＳ８１６に移行す
る。ＴＣＢ［Ｃｏｕｎｔ］の共有資源アクセスグループ
７６５が値０でない場合、Ｃｏｕｎｔをインクリメント
する（ステップＳ８１５）。

【００９８】最初に見つかった共有資源をアクセスする
タスクを示すＴＣＢ［Ｃｏｕｎｔ］を優先順位７５５に
対応する実行待キュー７７０の後尾に追加する（ステッ
プＳ８１６）。ループカウンタＣｏｕｎｔをインクリメ
ントする（ステップＳ８１７）。グループ［Ｃｏｕｎｔ
２］の実行待共有資源アクセスタスク数（６９２、６９
５あるいは６９８）に値１をセットする（ステップＳ８
１８）。

【００９９】ラウンドロビンキュー８４０に残りの共有
資源をアクセスするタスク群を追加するため、ＴＣＢ
［Ｃｏｕｎｔ］からＴＣＢ［（全タスク数５１０）−
１］まで以下の処理を繰り返す（ステップＳ８１９）。
ＴＣＢ［Ｃｏｕｎｔ］の共有資源アクセスグループ７６
５が値０でない（共有資源にアクセスするタスク）か否
かを判別する（ステップＳ８２０）。

【０１００】値０でない場合、ＴＣＢ［Ｃｏｕｎｔ］の
タスク状態７５６をラウンドロビン待９０４とし、ラウ
ンドロビングループ［Ｃｏｕｎｔ２］のラウンドロビン
キュー（８４１、８４６あるいは８５１）の後尾へ追加
し（ステップＳ８２１）、グループ［Ｃｏｕｎｔ２］の
ラウンドロビン待タスク数（６９３、６９６あるいは６
９９）をインクリメントし（ステップＳ８２２）、ルー
プカウンタＣｏｕｎｔをインクリメントする（ステップ
Ｓ８２３）。ＴＣＢ［Ｃｏｕｎｔ］の共有資源アクセス
グループ７６５が値０ならば、Ｃｏｕｎｔをインクリメ
ントする（ステップＳ８２３）。そして、ステップＳ８
１０ＡでＣｏｕｎｔ２＝全共有資源グループ数５１１ま
で繰り返した場合、呼び出し元にリターンする。

【０１０１】図２３はスケジューリング調整機構６００
の中断処理６２０の手順を示すフローチャートである。
この処理はタスクから任意に起動される。指定タスクを
中断状態９０５に遷移させる処理である。まず、指定し
た中断タスクのＴＣＢ７５０内の共有資源アクセスグル
ープ７６５が値０に等しくないか否かを判別する（ステ
ップＳ６２１）。値０に等しければ、中断すべきタスク
は共有資源にアクセスしないタスクなので、中断タスク
のＴＣＢ７５０を実行待キュー７７０から取り出し（ス
テップＳ６２２）、中断キュー７９０の後尾に追加し、
タスク状態７５６を中断状態９０５にし（ステップＳ６
２３）、スケジューリング処理７３０を起動する（ステ
ップ６２３Ａ）。

【０１０２】指定した中断タスクのＴＣＢ７５０内の共
有資源アクセスフラグ７５８が値０に等しくなければ、
中断すべきタスクは共有資源にアクセスするタスクであ
るので、中断タスクのＴＣＢを実行待キュー７７０から
取り出し（ステップＳ６２４）、グループ［共有資源グ
ループ７６５］の実行待共有資源アクセスタスク数（６
９２、６９５あるいは６９８）に値０をセットし（ステ
ップＳ６２５）、ステップＳ６２４で取り出したＴＣＢ
を中断キュー７９０の後尾に追加し、タスク状態７５６
を中断状態９０５にする（ステップＳ６２６）。

【０１０３】グループ［共有資源グループ７６５］のラ
ウンドロビン待タスク数（６９３、６９６あるいは６９
９）が値０に等しいか否かを判別する（ステップＳ６２
７）。値０に等しければ、特にラウンドロビン待状態９
０４のタスクは存在しないので、スケジューリング処理
７３０を起動する（ステップＳ６３２）。 一方、ステ
ップＳ６２７で値０に等しくなければ、指定した共有資
源をアクセスするタスクが実行待状態９０３から中断状
態９０５に遷移したために、新たにラウンドロビン待状
態９０４の共有資源をアクセスするタスク群のうちから
１タスクを実行待状態９０３に遷移させる。まず、ラウ
ンドロビングループ［共有資源グループ７６５］のラウ
ンドロビンキュー（８４１、８４６あるいは８５１）の
先頭タスク（８４２、８４７あるいは８５２）のＴＣＢ
７５０を取り出し（ステップＳ６２８）、グループ［共
有資源グループ７６５］のラウンドロビン待タスク数
（６９３、６９６あるいは６９９）をデクリメントし
（ステップＳ６２９）、ステップＳ６２８で取り出した
ＴＣＢを該当する優先順位７５５の実行待キュー７７０
の後尾へ追加し、タスク状態７５６を実行待状態９０３
にする（ステップＳ６３０）。

【０１０４】グループ［共有資源グループ７６５］の実
行待共有資源アクセスタスク数（６９２、６９５あるい
は６９８）に値１をセットする（ステップＳ６３１）。
スケジューリング処理７３０を起動する（ステップＳ６
３２）。

【０１０５】図２４はスケジューリング調整機構６００
の中断解除処理６４０の手順を示すフローチャートであ
る。この処理はタスクまたはＩ／Ｏ割込み処理から任意
に起動される。指定タスクを中断状態９０５から実行待
状態９０３またはラウンドロビン待状態９０４に遷移さ
せる処理である。

【０１０６】まず、指定した中断状態を解除したいタス
クのＴＣＢ７５０内の共有資源グループ７６５が値０に
等しくないか否かを判別する（ステップＳ６４１）。値
０に等しければ、中断状態を解除すべきタスクは共有資
源にアクセスしないタスクであるので、中断タスクのＴ
ＣＢ７５０を中断キュー７９０から取り出し（ステップ
Ｓ６４２）、該当する優先順位７５５の実行待キュー７
７０の後尾へ追加し、タスク状態７５６を実行待状態９
０３にし（ステップＳ６４３）、スケジューリング処理
７３０を起動する（ステップＳ６４３Ａ）。

【０１０７】指定した中断状態を解除したいタスクのＴ
ＣＢ７５０内の共有資源アクセスグループ７６５が値０
に等しくなければ、中断すべきタスクは共有資源にアク
セスするタスクであるので、中断タスクのＴＣＢ７５０
を中断キュー７９０から取り出す（ステップＳ６４
４）。グループ［共有資源グループ７６５］のラウンド
ロビン待タスク数（６９３、６９６あるいは６９９）が
値０に等しいか否かを判別する（ステップＳ６４５）。
値０に等しくなければ、ラウンドロビン待状態９０４の
タスクが既に存在するので、ステップＳ６４４で取り出
したＴＣＢをラウンドロビングループ［Ｃｏｕｎｔ２］
のラウンドロビンキュー（８４１、８４６あるいは８５
１）の後尾へ追加し、タスク状態７５６をラウンドロビ
ン待状態９０４にし（ステップＳ６４７）、グループ
［共有資源グループ７６５］のラウンドロビン待タスク
数（６９３、６９６あるいは６９９）をインクリメント
（ステップＳ６４８）、リターンする。

【０１０８】ステップＳ６４５で値０に等しければ、ラ
ウンドロビン待状態９０４のタスクは存在しないので、
グループ［共有資源グループ７６５］の実行待共有資源
アクセスタスク数（６９２、６９５あるいは６９８）が
値０に等しいか否かを判別する（ステップＳ６４６）。

【０１０９】値０に等しくなければ、既に共有資源グル
ープ７６５のタスク群のうちから１タスクが実行待状態
９０３であるため、ステップＳ６４４で取り出したＴＣ
Ｂをラウンドロビングループ［Ｃｏｕｎｔ２］のラウン
ドロビンキュー（８４１、８４６あるいは８５１）の後
尾へ追加し、タスク状態７５６をラウンドロビン待状態
９０４にし（ステップＳ６４７）、グループ［共有資源
グループ７６５］のラウンドロビン待タスク数（６９
３、６９６あるいは６９９）をインクリメントし（ステ
ップＳ６４８）、リターンする。

【０１１０】ステップＳ６４６で値０に等しければ、共
有資源グループ７６５のタスク群のうち、実行待状態９
０３のタスクは存在しないので、ステップＳ６４４で取
り出したＴＣＢを該当する優先順位７５５の実行待キュ
ー７７０の後尾へ追加し、タスク状態７５６を実行待状
態９０３にする（ステップＳ６４９）。グループ［共有
資源グループ７６５］の実行待共有資源アクセスタスク
数（６９２、６９５あるいは６９８）に値１をセットす
る（ステップＳ６５０）。スケジューリング処理７３０
を起動する（ステップＳ６５１）。

【０１１１】［第３の実施形態］第３の実施形態では、
前述した問題点１〜問題点４を解決するタスクスケジュ
ーリング装置について説明する。これは、前記第２の実
施形態における図１６の共有資源にアクセスしないタス
ク（タスク１（３２０）、タスク２（３３０））を除い
たケースに相当する。したがって、図１８の初期化デー
タ５００において、タスク１とタスク２に関するタスク
情報（５５０および５５１）を削除してやれば、その他
は第２の実施形態と同等の処理で実現することができ
る。

【０１１２】尚、立ち上げ時のコードおよび初期化デー
タ５００の格納場所をＲＯＭ１１０ではなく、フロッピ
ーディスクやハードディスクなどの記録媒体に置き換え
てもよい。

【０１１３】また、共有資源としては、変数データだけ
でなく、ハードディスクやＣＤ−ＲＯＭドライブ、ＲＳ
−２３２Ｃ、ＰＩＯなどの通信ポートに応用すること
で、容易にシステムの信頼性および性能を最大限に高め
て複数のタスクから資源を共有することが可能になる。

【０１１４】さらに、共有資源としては、オブジェクト
指向言語の「クラス」に対応させることが容易であり、
オブジェクト指向言語で記述したシステムの信頼性およ
び性能を最大限に高めてマルチタスクシステムとして実
装することが可能になる。

【０１１５】

【発明の効果】本発明の請求項１に記載のタスクスケジ
ューリング装置によれば、前述した問題点１〜問題点４
を解決することができる。

【０１１６】即ち、スケジューリング調整機構によっ
て、共有資源と無関係な全てのタスクおよび共有資源に
アクセスするタスクのうちから１つをプリエンプトスケ
ジューリング機構に登録し、残った共有資源にアクセス
するタスク全てをラウンドロビンスケジューリング機構
に順序付けて登録し、プリエンプトスケジューリング機
構によるスケジューリングで共有資源にアクセスするタ
スクが実行権を放棄（中断状態に遷移）した時、ラウン
ドロビンスケジューリング機構に順序付けて登録された
共有資源にアクセスするタスクのうち先頭のものと入れ
替え、この際、中断状態に遷移したタスクを中断要因が
解除された時にラウンドロビンスケジューリング機構の
順序付けの最後尾に登録することが可能になる。したが
って、共有資源をアクセスしているタスクがＣＰＵを占
有して実行し続けても、共有資源と無関係なタスクはプ
リエンプト（横取り）可能であるので、共有資源をアク
セスしているタスクより優先順位が高かったり、同じ優
先順位でもタイムスライスによりタスクスイッチが生
じ、ＣＰＵ占有権を得て実行され、システム全体に影響
を及ぼさないようにすることができ、前述した問題点４
を解決できる。

【０１１７】また、共有資源にアクセスするタスク群で
は、ラウンドロビンスケジューリングを用いることで、
セマフォによる排他制御を不要とし、その際のオーバー
ヘッドをなくすことができ、前述した問題点１を解決で
きる。

【０１１８】さらに、複雑なデータ構造もデータ構造全
体を１つの共有資源とし、共有資源とタスクとの関係を
１対多の関係で定義することを可能にしたことで、細か
い共有資源の切り出しを不要にでき、前述した問題点２
を解決できる。

【０１１９】また、連続したデータアクセスが必要な場
合もそれらを１つの共有資源として扱うことができ、デ
ッドロックの危険性をなくすことができ、前述した問題
点３を解決できる。

【０１２０】尚、請求項４に記載のタスクスケジューリ
ング方法においても同様の効果を得ることがてきる。

【０１２１】請求項２に記載のタスクスケジューリング
装置によれば、前述した問題点１〜問題点３および問題
点５を解決できる。

【０１２２】即ち、スケジューリング調整機構によっ
て、共有資源毎にアクセスするタスク群をタスクグルー
プとして切り分けて管理し、各タスクグループのうちか
ら１タスクずつプリエンプトスケジューリング機構に登
録し、残った共有資源にアクセスするタスク全てをタス
クグループ毎にラウンドロビンスケジューリング機構に
順序付けて登録し、プリエンプトスケジューリング機構
によるスケジューリングで、あるタスクグループ（該当
タスクグループ）に属するタスクが実行権を放棄（中断
状態に遷移）した時、ラウンドロビンスケジューリング
機構にタスクグループ毎に順序付けて登録されたタスク
のうち、該当タスクグループ内の順序付けの先頭のもの
と入れ替え、この際、中断状態に遷移したタスクを中断
要因が解除された時にラウンドロビンスケジューリング
機構のうち、該当タスクグループ内の順序付けの最後尾
に登録することが可能になる。したがって、複数の共有
資源がある場合、タイムスライスによるプリエンプト
（横取り）スケジューリングによって、それぞれの共有
資源毎の累積アクセス時間を均等に割り振ることがで
き、前述した問題点５を解決できる。

【０１２３】また、共有資源にアクセスするタスク群で
はラウンドロビンスケジューリングを用いることで、セ
マフォによる排他制御を不要とし、その際のオーバーヘ
ッドをなくすことができ、前述した問題点１を解決でき
る。

【０１２４】さらに、複雑なデータ構造もデータ構造全
体を１つの共有資源とし、共有資源とタスクとの関係を
１対多の関係で定義することを可能にしたことで、細か
い共有資源の切り出しを不要にでき、前述した問題点２
を解決できる。

【０１２５】また、連続したデータアクセスが必要な場
合もそれらを１つの共有資源として扱うことができ、デ
ッドロックの危険性をなくすことができ、前述した問題
点３を解決できる。

【０１２６】尚、請求項５に記載のタスクスケジューリ
ング方法においても、同様の効果を得ることができる。

【０１２７】請求項３に記載のタスクスケジューリング
装置によれば、前述した問題点１〜問題点５を解決する
ことがてきる。

【０１２８】即ち、スケジューリング調整機構によっ
て、共有資源毎にアクセスするタスク群をタスクグルー
プとして切り分けて管理し、各タスクグループのうちか
ら１タスクずつプリエンプトスケジューリング機構に登
録し、残った共有資源にアクセスするタスク全てをタス
クグループ毎にラウンドロビンスケジューリング機構に
順序付けて登録し、プリエンプトスケジューリング機構
によるスケジューリングで、あるタスクグループ（該当
タスクグループ）に属するタスクが実行権を放棄（中断
状態に遷移）した時、ラウンドロビンスケジューリング
機構にタスクグループ毎に順序付けて登録されたタスク
のうち、該当タスクグループ内の順序付けの先頭のもの
と入れ替え、この際、中断状態に遷移したタスクを中断
要因が解除された時にラウンドロビンスケジューリング
機構のうち、該当タスクグループ内の順序付けの最後尾
に登録することが可能になる。したがって、複数の共有
資源がある場合、タイムスライスによるプリエンプト
（横取り）スケジューリングによって、それぞれの共有
資源毎の累積アクセス時間を均等に割り振ることがで
き、前述した問題点５を解決できる。

【０１２９】また、共有資源をアクセスしているタスク
がＣＰＵを占有して実行し続けても、共有資源と無関係
なタスクはプリエンプト（横取り）可能であるので、共
有資源をアクセスしているタスクより優先順位が高かっ
たり、同じ優先順位でもタイムスライスによりタスクス
イッチが生じ、ＣＰＵ占有権を得て実行され、システム
全体に影響を及ぼさないようにすることができ、前述し
た問題点４を解決できる。

【０１３０】さらに、共有資源にアクセスするタスク群
では、ラウンドロビンスケジューリングを用いること
で、セマフォによる排他制御を不要とし、その際のオー
バーヘッドをなくすことができ、前述した問題点１を解
決できる。

【０１３１】また、複雑なデータ構造もデータ構造全体
を１つの共有資源とし、共有資源とタスクとの関係を１
対多の関係で定義することを可能にしたことで、細かい
共有資源の切り出しを不要にでき、前述した問題点２を
解決できる。

【０１３２】さらに、連続したデータアクセスが必要な
場合もそれらを１つの共有資源として扱うことができ、
デッドロックの危険性をなくすことができ、前述した問
題点３を解決できる。

【０１３３】尚、請求項６に記載のタスクスケジューリ
ング方法においても、同様の効果を得ることができる。

【０１３４】このように、共有資源をアクセスしている
タスクがＣＰＵを占有して実行し続けても、共有資源と
無関係なタスクはプリエンプト（横取り）可能であるた
め、共有資源をアクセスしているタスクより優先順位が
高かったり、同じ優先順位てもタイムスライスによりタ
スクスイッチが生じ、ＣＰＵ占有権を得て実行され、シ
ステム全体に影響を及ぼさないようにすることができ、
システムの信頼性を高めることが可能である。

【０１３５】また、複数の共有資源がある場合、タイム
スライスによるプリエンプト（横取り）スケジューリン
グによってそれぞれの共有資源毎の累積アクセス時間を
均等に割り振ることができ、タスクの数が変化しても安
定したスループットを保証するシステムを構築すること
が可能である。

【０１３６】さらに、共有資源にアクセスするタスク群
ではラウンドロビンスケジューリングを用いることによ
り、セマフォによる排他制御を不要とし、その際のオー
バヘッドをなくすことができ、システムの性能を向上さ
せることが可能になる。

【０１３７】また、複雑なデータ構造もデータ構造全体
を１つの共有資源とし、共有資源とタスクとの関係を１
対多の関係で定義することを可能にしたことで、細かい
共有資源の切り出しを不要にすることができ、システム
設計を容易に行うことができ、生産性を向上させること
が可能である。

【０１３８】さらに、連続したデータアクセスが必要な
場合もそれらを１つの共有資源として扱うことを可能と
したことで、デッドロックの危険性をなくすことがで
き、システムの信頼性を高めることができる。

【０１３９】また、共有資源としては、変数データだけ
でなく、ハードディスクやＣＤ−ＲＯＭドライブ、ＲＳ
−２３２Ｃ、ＰＩＯなどの通信ポートに応用すること
で、容易にシステムの信頼性および性能を最大限に高め
て複数のタスクから資源を共有することが可能になる。

【０１４０】さらに、共有資源としては、オブジェクト
指向言語の「クラス」に対応させることが容易であり、
オブジェクト指向言語で記述したシステムの信頼性およ
び性能を最大限に高めてマルチタスクシステムとして実
装することが可能になる。

【０１４１】また、専用のハードウェアを新規に開発す
る必要がなく、固定優先順位のプリエンプトスケジュー
ル機能を持ったリアルタイムＯＳに簡単に組み込むこと
が可能であるので、既存システムであっても低コストで
信頼性および性能を向上させることができる。

【図面の簡単な説明】

【図１】第１の実施形態におけるタスクスケジューリン
グ装置が適用されたシステムの構成を示すブロック図で
ある。

【図２】スケジューリング調整機構６００の構成を示す
図である。

【図３】プリエンプトスケジューリング機構７００の構
成を示す図である。

【図４】ラウンドロビンスケジューリング機構８００の
構成を示す図である。

【図５】タスクの状態遷移を示す図である。

【図６】初期化データの構成を示す図である。

【図７】共有資源管理テーブルを示す図である。

【図８】タスクコントロールブロックの構成を示す図で
ある。

【図９】初期化処理６１０の手順を示すフローチャート
である。

【図１０】プリエンプトスケジューリング機構７００の
初期化処理７２０の手順を示すフローチャートである。

【図１１】ラウンドロビンスケジューリング機構８００
の初期化処理８１０の手順を示すフローチャートであ
る。

【図１２】プリエンプトスケジューリング機構７００の
スケジューリング処理７３０の手順を示すフローチャー
トである。

【図１３】スケジューリング調整機構６００の中断処理
６２０の手順を示すフローチャートである。

【図１４】スケジューリング調整機構６００の中断解除
処理６４０の手順を示すフローチャートである。

【図１５】スケジューリング調整機構６００のタイマ割
込み処理６６０の手順を示すフローチャートである。

【図１６】第２の実施形態におけるタスクスケジューリ
ング装置が適用されたシステムの構成を示す図である。

【図１７】ラウンドロビンスケジューリング機構８００
の構成を示す図である。

【図１８】初期化データの構成を示す図である。

【図１９】共有資源管理テーブルを示す図である。

【図２０】タスクコントロールブロックの構成を示す図
である。

【図２１】プリエンプトスケジューリング機構７００の
初期化処理７２０の手順を示すフローチャートである。

【図２２】ラウンドロビンスケジューリング機構８００
の初期化処理８１０の手順を示すフローチャートであ
る。

【図２３】スケジューリング調整機構６００の中断処理
６２０の手順を示すフローチャートである。

【図２４】スケジューリング調整機構６００の中断解除
処理６４０の手順を示すフローチャートである。

【符号の説明】

１００ ＲＡＭ １１０ ＲＯＭ １４０ ＣＰＵ ２００ 共有資源 ３００、３１０、３２０、３３０ タスク ６００ スケジューリング機構 ７００ プリエンプトスケジューリング機構 ８００ ラウンドロビンスケジューリング機構

───────────────────────────────────────────────────── フロントページの続き (72)発明者 別所 正隆 東京都大田区下丸子３丁目30番２号 キヤ ノン株式会社内

Claims (6)

【特許請求の範囲】
1. 【請求項１】 マルチタスクプログラムのスケジューリ
   ングを行うタスクスケジューリング装置において、 スケジューリング調整機構と、プリエンプトスケジュー
   リング機構と、ラウンドロビンスケジューリング機構と
   を備え、 共有資源をアクセスするタスク群ではラウンドロビンス
   ケジューリングを用い、 前記共有資源と無関係なタスク群ではプリエンプトスケ
   ジューリングを用い、両タスク群の間ではプリエンプト
   スケジューリングを実現する処理を行うことを特徴とす
   るタスクスケジューリング装置。
2. 【請求項２】 マルチタスクプログラムのスケジューリ
   ングを行うタスクスケジューリング装置において、 スケジューリング調整機構と、プリエンプトスケジュー
   リング機構と、ラウンドロビンスケジューリング機構と
   を備え、 共有資源毎にアクセスするタスク群をタスクグループと
   して切り出し、 各タスクグループ内で独立してラウンドロビンスケジュ
   ーリングを用い、 前記タスクグループの間ではプリエンプトスケジューリ
   ングを実現する処理を行うことを特徴とするタスクスケ
   ジューリング装置。
3. 【請求項３】 マルチタスクプログラムのスケジューリ
   ングを行うタスクスケジューリング装置において、 スケジューリング調整機構と、プリエンプトスケジュー
   リング機構と、ラウンドロビンスケジューリング機構と
   を備え、 共有資源毎にアクセスするタスク群をタスクグループと
   して切り出し、 各タスクグループ内で独立してラウンドロビンスケジュ
   ーリングを用い、 前記共有資源と無関係なタスク群ではプリエンプトスケ
   ジューリングを用い、 前記タスクグループの間および前記タスクグループと前
   記共有資源とは無関係なタスク群の間ではプリエンプト
   スケジューリングを実現する処理を行うことを特徴とす
   るタスクスケジューリング装置。
4. 【請求項４】 マルチタスクプログラムのスケジューリ
   ングを行うタスクスケジューリング方法において、 共有資源をアクセスするタスク群ではラウンドロビンス
   ケジューリングを用い、 前記共有資源と無関係なタスク群ではプリエンプトスケ
   ジューリングを用い、 両タスク群の間ではプリエンプトスケジューリングを実
   現する処理を行うことを特徴とするタスクスケジューリ
   ング方法。
5. 【請求項５】 マルチタスクプログラムのスケジューリ
   ングを行うタスクスケジューリング方法において、 共有資源毎にアクセスするタスク群をタスクグループと
   して切り出し、 各タスクグループ内で独立してラウンドロビンスケジュ
   ーリングを用い、 前記タスクグループの間ではプリエンプトスケジューリ
   ングを実現する処理を行うことを特徴とするタスクスケ
   ジューリング方法。
6. 【請求項６】 マルチタスクプログラムのスケジューリ
   ングを行うタスクスケジューリング方法において、 共有資源毎にアクセスするタスク群をタスクグループと
   して切り出し、 各タスクグループ内で独立してラウンドロビンスケジュ
   ーリングを用い、 前記共有資源と無関係なタスク群ではプリエンプトスケ
   ジューリングを用い、 前記タスクグループの間および前記タスクグループと前
   記共有資源とは無関係なタスク群の間ではプリエンプト
   スケジューリングを実現する処理を行うことを特徴とす
   るタスクスケジューリング方法。