JP2544896B2 - スケジュ―リング方法およびスケジュ―リング装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、タスク管理をスタック
領域において行なう際のスケジューリング方法およびス
ケジューリング装置に関するものである。

【０００２】

【従来の技術】従来、タスク管理をスタック領域におい
て行なうに際しては、各タスクが使用するスタック領域
をタスク毎に割り当て、各タスクの実行状態を、中央処
理装置で実行中である走行状態と、中央処理装置の割り
当てを待っている走行可能状態と、他のタスクからの信
号などの事象を待っている走行待ち状態との３つの状態
に分けてスケジューリングを行なっていた。

【０００３】

【発明が解決しようとする課題】しかし上記従来のスケ
ジューリング方法では、走行状態となる可能性を全ての
タスクが有しているため、各タスクが使用するスタック
領域をタスク毎に割り当てる必要があり、このため、ス
タック領域の容量が少ない場合にはタスクが走行状態と
なるだけの領域を確保できず、その結果、スケジューリ
ングできないという問題点があった。

【０００４】本発明はかかる事情に鑑みて成されたもの
であり、複数のタスクが、同一のスタックを使用するこ
とによりスタック領域の容量の低減を図った場合におい
てもスケジューリングを可能とするスケジューリング方
法およびスケジューリング装置を提供することを目的と
する。

【０００５】

【課題を解決するための手段】請求項１の発明は、走行
可能状態と走行待ち状態と走行状態と走行不可能状態と
の少なくとも４つの実行状態とシステム内で一意の識別
子とを持つタスクが、タスク切り替えにより複数個実行
されるシステムにおけるスケジューリング方法であっ
て、各タスクの識別子と実行状態とを格納するタスク情
報格納部と、各タスクの識別子と各タスクが使用する最
大のスタック容量とを格納すると共に、タスクの実行状
態が走行不可能状態でありかつスタックが割り当てられ
ていない場合に実行状態が走行状態か走行待ち状態か走
行可能状態かのいずれかの状態となり、かつタスクの実
行状態が走行状態か走行待ち状態か走行可能状態かのい
ずれかの状態である場合に走行不可能状態となる実行保
護タスクの識別子と、実行保護タスクが走行不可能状態
となる場合に使用する最大のスタック容量とを格納する
実行保護タスク格納部とを用い、タスクの切り替え要求
を発生するタスク切り替え要求ステップと、タスク切り
替え要求ステップにおいてタスク切り替え要求が発生さ
れることにより、タスク情報格納部と実行保護タスク格
納部とを検索して、いずれのタスクに対しても実行保護
タスクではなくかつ実行状態が走行不可能状態であるタ
スクの識別子を抽出する実行可能タスク抽出ステップ
と、タスクの実行状態が走行状態であるタスクの実行状
態を走行可能状態に変更し、タスク情報格納部を検索し
てタスクの実行状態が走行待ち状態または走行可能状態
であるタスクの識別子を抽出する実行中タスク抽出ステ
ップと、実行中タスク抽出ステップにおいて抽出された
識別子を第１の識別子とし、実行可能タスク抽出ステッ
プにおいて抽出された識別子を第２の識別子としたとき
に、実行保護タスク格納部を検索して、第１の識別子に
対応するタスクが第２の識別子に対応するタスクの実行
保護タスクである第１の識別子と第２の識別子との組合
せを抽出するスタック使用可能タスク抽出ステップと、
実行保護タスク格納部を検索して、スタック使用可能タ
スク抽出ステップにおいて抽出された第１の識別子と第
２の識別子との組合せにおける第１の識別子に対応する
タスクが実行不可能状態となる場合に使用する最大のス
タック容量を得、そのスタック容量よりも第１の識別子
に対応するタスクが現在使用しているスタック容量が小
さい第１の識別子と第２の識別子との組合せを抽出する
スタック使用可能タスク選択ステップと、スタック使用
可能タスク選択ステップにおいて抽出された第１の識別
子と第２の識別子との組合せにおける第１の識別子に対
応するタスクの実行状態を走行不可能状態にし、第２の
識別子に対応するタスクの実行状態を走行状態にするタ
スク切り替えステップと、を実行することを特徴として
いる。

【０００６】請求項２の発明は、走行可能状態と走行待
ち状態と走行状態と走行不可能状態との少なくとも４つ
の実行状態とシステム内で一意の識別子とを持つタスク
が、タスク切り替えにより複数個実行される計算機シス
テムにおけるスケジューリング装置であって、各タスク
の識別子と実行状態とを格納するタスク情報格納部と、
各タスクの識別子と各タスクが使用する最大のスタック
容量とを格納すると共に、タスクの実行状態が走行不可
能状態でありかつスタックが割り当てられていない場合
に実行状態が走行状態か走行待ち状態か走行可能状態か
のいずれかの状態となり、かつタスクの実行状態が走行
状態か走行待ち状態か走行可能状態かのいずれかの状態
である場合に走行不可能状態となる実行保護タスクの識
別子と、実行保護タスクが走行不可能状態となる場合に
使用する最大のスタック容量とを格納する実行保護タス
ク格納部と、タスクの切り替え要求を発生するタスク切
り替え要求部と、タスク切り替え要求部がタスク切り替
え要求を発生したときに、タスク情報格納部と実行保護
タスク格納部とを検索して、いずれのタスクに対しても
実行保護タスクではなくかつ実行状態が走行不可能状態
であるタスクの識別子を抽出する実行可能タスク抽出部
と、タスクの実行状態が走行状態であるタスクの実行状
態を走行可能状態に変更し、タスク情報格納部を検索し
てタスクの実行状態が走行待ち状態または走行可能状態
であるタスクの識別子を抽出する実行中タスク抽出部
と、実行中タスク抽出部により抽出された識別子を第１
の識別子とし、実行可能タスク抽出部により抽出された
識別子を第２の識別子としたときに、実行保護タスク格
納部を検索して、第１の識別子に対応するタスクが第２
の識別子に対応するタスクの実行保護タスクである第１
の識別子と第２の識別子との組合せを抽出するスタック
使用可能タスク抽出部と、実行保護タスク格納部を検索
して、スタック使用可能タスク抽出部により抽出された
第１の識別子と第２の識別子との組合せにおける第１の
識別子に対応するタスクが実行不可能状態となる場合に
使用する最大のスタック容量を得、そのスタック容量よ
りも第１の識別子に対応するタスクが現在使用している
スタック容量が小さい第１の識別子と第２の識別子との
組合せを抽出するスタック使用可能タスク選択部と、ス
タック使用可能タスク選択部により抽出された第１の識
別子と第２の識別子との組合せにおける第１の識別子に
対応するタスクの実行状態を走行不可能状態にし、第２
の識別子に対応するタスクの実行状態を走行状態にする
タスク切り替え部と、を備えたことを特徴としている。

【０００７】請求項３の発明は、走行可能状態と走行待
ち状態と走行状態と走行不可能状態との少なくとも４つ
の実行状態とシステム内で一意の識別子とを持つタスク
が、タスク切り替えにより複数個実行される計算機シス
テムにおけるスケジューリング方法であって、各タスク
の識別子と実行状態とを格納するタスク情報格納部と、
各タスクの識別子と各タスクが使用する最大のスタック
容量とを格納すると共に、タスクの実行状態が走行不可
能状態でありかつスタックが割り当てられていない場合
に実行状態が走行状態か走行待ち状態か走行可能状態か
のいずれかの状態となり、かつタスクの実行状態が走行
状態か走行待ち状態か走行可能状態かのいずれかの状態
である場合に走行不可能状態となる実行保護タスクの識
別子と、実行保護タスクが走行不可能状態となる場合に
使用する最大のスタック容量とを格納する実行保護タス
ク格納部と、タスクの実行状態とスタックポインタとを
格納するスタックポインタ格納部とを用いて、タスクの
切り替え要求を発生するタスク切り替え要求ステップ
と、タスク切り替え要求ステップにおいてタスク切り替
え要求が発生されることにより、タスク情報格納部と実
行保護タスク格納部とを検索して、いずれのタスクに対
しても実行保護タスクではなくかつ実行状態が走行不可
能状態であるタスクの識別子を抽出する実行可能タスク
抽出ステップと、タスクの実行状態が走行状態であるタ
スクの実行状態を走行可能状態に変更し、タスク情報格
納部を検索してタスクの実行状態が走行待ち状態または
走行可能状態であるタスクの識別子を抽出する実行中タ
スク抽出ステップと、実行中タスク抽出ステップにおい
て抽出された識別子を第１の識別子とし、実行可能タス
ク抽出ステップにおいて抽出された識別子を第２の識別
子としたときに、実行保護タスク格納部を検索して、第
１の識別子に対応するタスクが第２の識別子に対応する
タスクの実行保護タスクである第１の識別子と第２の識
別子との組合せを抽出するスタック使用可能タスク抽出
ステップと、スタック使用可能タスク抽出ステップにお
いて抽出された第１の識別子と第２の識別子との組合せ
において実行保護タスクとなり得る識別子に対応するタ
スクの実行状態をスタックポインタ格納部に格納し、実
行保護タスクとなり得るタスクの実行状態を走行待ち状
態に変更し、実行保護タスクとなり得るタスクが使用し
ているスタック内のデータを圧縮し、実行保護タスクと
なり得るタスクのスタックポインタをスタックポインタ
格納部に格納するスタックデータ圧縮ステップと、実行
保護タスク格納部を検索して、スタック使用可能タスク
抽出ステップにおいて抽出された第１の識別子と第２の
識別子との組合せにおける第１の識別子に対応するタス
クが実行不可能状態となる場合に使用する最大のスタッ
ク容量を得、そのスタック容量よりも第１の識別子に対
応するタスクが現在使用しているスタック容量が小さい
第１の識別子と第２の識別子との組合せを抽出するスタ
ック使用可能タスク選択ステップと、スタック使用可能
タスク選択ステップにおいて抽出された第１の識別子と
第２の識別子との組合せにおける第１の識別子に対応す
るタスクの実行状態を走行不可能状態にし、第２の識別
子に対応するタスクの実行状態を走行状態にするタスク
切り替えステップと、タスク情報格納部を検索して実行
状態が走行待ち状態であるタスクの識別子を全て抽出
し、スタックポインタ格納部を検索してタスク情報格納
部から抽出した識別子に対応するタスクのスタックポイ
ンタと実行状態とを抽出し、スタックポインタ格納部か
らスタックポインタと実行状態とを抽出したタスクが使
用しているスタック内のデータを展開し、スタックポイ
ンタ格納部からスタックポインタと実行状態とを抽出し
たタスクの実行状態をスタックポインタ格納部から抽出
した実行状態に変更し、スタックポインタ格納部からス
タックポインタと実行状態とを抽出したタスクのスタッ
クポインタと実行状態とをスタックポインタ格納部から
削除するスタックデータ展開ステップと、を実行するこ
とを特徴としている。

【０００８】請求項４の発明は、走行可能状態と走行待
ち状態と走行状態と走行不可能状態との少なくとも４つ
の実行状態とシステム内で一意の識別子とを持つタスク
が、タスク切り替えにより複数個実行される計算機シス
テムにおけるスケジューリング装置であって、各タスク
の識別子と実行状態とを格納するタスク情報格納部と、
各タスクの識別子と各タスクが使用する最大のスタック
容量とを格納すると共に、タスクの実行状態が走行不可
能状態でありかつスタックが割り当てられていない場合
に実行状態が走行状態か走行待ち状態か走行可能状態か
のいずれかの状態となり、かつタスクの実行状態が走行
状態か走行待ち状態か走行可能状態かのいずれかの状態
である場合に走行不可能状態となる実行保護タスクの識
別子と、実行保護タスクが走行不可能状態となる場合に
使用する最大のスタック容量とを格納する実行保護タス
ク格納部と、タスクの実行状態とスタックポインタとを
格納するスタックポインタ格納部と、タスクの切り替え
要求を発生するタスク切り替え要求部と、タスク切り替
え要求部がタスク切り替え要求を発生したときに、タス
ク情報格納部と実行保護タスク格納部とを検索して、い
ずれのタスクに対しても実行保護タスクではなくかつ実
行状態が走行不可能状態であるタスクの識別子を抽出す
る実行可能タスク抽出部と、タスクの実行状態が走行状
態であるタスクの実行状態を走行可能状態に変更し、タ
スク情報格納部を検索してタスクの実行状態が走行待ち
状態または走行可能状態であるタスクの識別子を抽出す
る実行中タスク抽出部と、実行中タスク抽出部により抽
出された識別子を第１の識別子とし、実行可能タスク抽
出部により抽出された識別子を第２の識別子としたとき
に、実行保護タスク格納部を検索して、第１の識別子に
対応するタスクが第２の識別子に対応するタスクの実行
保護タスクである第１の識別子と第２の識別子との組合
せを抽出するスタック使用可能タスク抽出部と、スタッ
ク使用可能タスク抽出部により抽出された第１の識別子
と第２の識別子との組合せにおいて実行保護タスクとな
り得る識別子に対応するタスクの実行状態をスタックポ
インタ格納部に格納し、実行保護タスクとなり得るタス
クの実行状態を走行待ち状態に変更し、実行保護タスク
となり得るタスクが使用しているスタック内のデータを
圧縮し、実行保護タスクとなり得るタスクのスタックポ
インタをスタックポインタ格納部に格納するスタックデ
ータ圧縮部と、実行保護タスク格納部を検索して、スタ
ック使用可能タスク抽出部により抽出された第１の識別
子と第２の識別子との組合せにおける第１の識別子に対
応するタスクが実行不可能状態となる場合に使用する最
大のスタック容量を得、そのスタック容量よりも第１の
識別子に対応するタスクが現在使用しているスタック容
量が小さい第１の識別子と第２の識別子との組合せを抽
出するスタック使用可能タスク選択部と、スタック使用
可能タスク選択部により抽出された第１の識別子と第２
の識別子との組合せにおける第１の識別子に対応するタ
スクの実行状態を走行不可能状態にし、第２の識別子に
対応するタスクの実行状態を走行状態にするタスク切り
替え部と、タスク情報格納部を検索して実行状態が走行
待ち状態であるタスクの識別子を全て抽出し、スタック
ポインタ格納部を検索してタスク情報格納部から抽出し
た識別子に対応するタスクのスタックポインタと実行状
態とを抽出し、スタックポインタ格納部からスタックポ
インタと実行状態とを抽出したタスクが使用しているス
タック内のデータを展開し、スタックポインタ格納部か
らスタックポインタと実行状態とを抽出したタスクの実
行状態をスタックポインタ格納部から抽出した実行状態
に変更し、スタックポインタ格納部からスタックポイン
タと実行状態とを抽出したタスクのスタックポインタと
実行状態とをスタックポインタ格納部から削除するスタ
ックデータ展開部と、を備えたことを特徴としている。

【０００９】

【作用】請求項１の発明においては、タスク切り替え要
求ステップで、タスクの切り替え要求を発生し、実行可
能タスク抽出ステップで、タスク切り替え要求ステップ
においてタスク切り替え要求が発生されることにより、
タスク情報格納部と実行保護タスク格納部とを検索し
て、いずれのタスクに対しても実行保護タスクではなく
かつ実行状態が走行不可能状態であるタスクの識別子を
抽出し、実行中タスク抽出ステップで、タスクの実行状
態が走行状態であるタスクの実行状態を走行可能状態に
変更し、タスク情報格納部を検索してタスクの実行状態
が走行待ち状態または走行可能状態であるタスクの識別
子を抽出し、スタック使用可能タスク抽出ステップで、
実行中タスク抽出ステップにおいて抽出された識別子を
第１の識別子とし、実行可能タスク抽出ステップにおい
て抽出された識別子を第２の識別子としたときに、実行
保護タスク格納部を検索して、第１の識別子に対応する
タスクが第２の識別子に対応するタスクの実行保護タス
クである第１の識別子と第２の識別子との組合せを抽出
し、スタック使用可能タスク選択ステップで、実行保護
タスク格納部を検索して、スタック使用可能タスク抽出
ステップにおいて抽出された第１の識別子と第２の識別
子との組合せにおける第１の識別子に対応するタスクが
実行不可能状態となる場合に使用する最大のスタック容
量を得、そのスタック容量よりも第１の識別子に対応す
るタスクが現在使用しているスタック容量が小さい第１
の識別子と第２の識別子との組合せを抽出し、タスク切
り替えステップで、スタック使用可能タスク選択ステッ
プにおいて抽出された第１の識別子と第２の識別子との
組合せにおける第１の識別子に対応するタスクの実行状
態を走行不可能状態にし、第２の識別子に対応するタス
クの実行状態を走行状態にする。

【００１０】請求項２の発明において、タスク情報格納
部は、各タスクの識別子と実行状態とを格納する。実行
保護タスク格納部は、各タスクの識別子と各タスクが使
用する最大のスタック容量とを格納すると共に、タスク
の実行状態が走行不可能状態でありかつスタックが割り
当てられていない場合に実行状態が走行状態か走行待ち
状態か走行可能状態かのいずれかの状態となり、かつタ
スクの実行状態が走行状態か走行待ち状態か走行可能状
態かのいずれかの状態である場合に走行不可能状態とな
る実行保護タスクの識別子と、実行保護タスクが走行不
可能状態となる場合に使用する最大のスタック容量とを
格納する。タスク切り替え要求部は、タスクの切り替え
要求を発生する。実行可能タスク抽出部は、タスク切り
替え要求部がタスク切り替え要求を発生したときに、タ
スク情報格納部と実行保護タスク格納部とを検索して、
いずれのタスクに対しても実行保護タスクではなくかつ
実行状態が走行不可能状態であるタスクの識別子を抽出
する。実行中タスク抽出部は、タスクの実行状態が走行
状態であるタスクの実行状態を走行可能状態に変更し、
タスク情報格納部を検索してタスクの実行状態が走行待
ち状態または走行可能状態であるタスクの識別子を抽出
する。スタック使用可能タスク抽出部は、実行中タスク
抽出部により抽出された識別子を第１の識別子とし、実
行可能タスク抽出部により抽出された識別子を第２の識
別子としたときに、実行保護タスク格納部を検索して、
第１の識別子に対応するタスクが第２の識別子に対応す
るタスクの実行保護タスクである第１の識別子と第２の
識別子との組合せを抽出する。スタック使用可能タスク
選択部は、実行保護タスク格納部を検索して、スタック
使用可能タスク抽出部により抽出された第１の識別子と
第２の識別子との組合せにおける第１の識別子に対応す
るタスクが実行不可能状態となる場合に使用する最大の
スタック容量を得、そのスタック容量よりも第１の識別
子に対応するタスクが現在使用しているスタック容量が
小さい第１の識別子と第２の識別子との組合せを抽出す
る。タスク切り替え部は、スタック使用可能タスク選択
部により抽出された第１の識別子と第２の識別子との組
合せにおける第１の識別子に対応するタスクの実行状態
を走行不可能状態にし、第２の識別子に対応するタスク
の実行状態を走行状態にする。

【００１１】請求項３の発明においては、タスク切り替
え要求ステップで、タスクの切り替え要求を発生し、実
行可能タスク抽出ステップで、タスク切り替え要求ステ
ップにおいてタスク切り替え要求が発生されることによ
り、タスク情報格納部と実行保護タスク格納部とを検索
して、いずれのタスクに対しても実行保護タスクではな
くかつ実行状態が走行不可能状態であるタスクの識別子
を抽出し、実行中タスク抽出ステップで、タスクの実行
状態が走行状態であるタスクの実行状態を走行可能状態
に変更し、タスク情報格納部を検索してタスクの実行状
態が走行待ち状態または走行可能状態であるタスクの識
別子を抽出し、スタック使用可能タスク抽出ステップ
で、実行中タスク抽出ステップにおいて抽出された識別
子を第１の識別子とし、実行可能タスク抽出ステップに
おいて抽出された識別子を第２の識別子としたときに、
実行保護タスク格納部を検索して、第１の識別子に対応
するタスクが第２の識別子に対応するタスクの実行保護
タスクである第１の識別子と第２の識別子との組合せを
抽出し、スタックデータ圧縮ステップで、スタック使用
可能タスク抽出ステップにおいて抽出された第１の識別
子と第２の識別子との組合せにおいて実行保護タスクと
なり得る識別子に対応するタスクの実行状態をスタック
ポインタ格納部に格納し、実行保護タスクとなり得るタ
スクの実行状態を走行待ち状態に変更し、実行保護タス
クとなり得るタスクが使用しているスタック内のデータ
を圧縮し、実行保護タスクとなり得るタスクのスタック
ポインタをスタックポインタ格納部に格納し、スタック
使用可能タスク選択ステップで、実行保護タスク格納部
を検索して、スタック使用可能タスク抽出ステップにお
いて抽出された第１の識別子と第２の識別子との組合せ
における第１の識別子に対応するタスクが実行不可能状
態となる場合に使用する最大のスタック容量を得、その
スタック容量よりも第１の識別子に対応するタスクが現
在使用しているスタック容量が小さい第１の識別子と第
２の識別子との組合せを抽出し、タスク切り替えステッ
プで、スタック使用可能タスク選択ステップにおいて抽
出された第１の識別子と第２の識別子との組合せにおけ
る第１の識別子に対応するタスクの実行状態を走行不可
能状態にし、第２の識別子に対応するタスクの実行状態
を走行状態にし、スタックデータ展開ステップで、タス
ク情報格納部を検索して実行状態が走行待ち状態である
タスクの識別子を全て抽出し、スタックポインタ格納部
を検索してタスク情報格納部から抽出した識別子に対応
するタスクのスタックポインタと実行状態とを抽出し、
スタックポインタ格納部からスタックポインタと実行状
態とを抽出したタスクが使用しているスタック内のデー
タを展開し、スタックポインタ格納部からスタックポイ
ンタと実行状態とを抽出したタスクの実行状態をスタッ
クポインタ格納部から抽出した実行状態に変更し、スタ
ックポインタ格納部からスタックポインタと実行状態と
を抽出したタスクのスタックポインタと実行状態とをス
タックポインタ格納部から削除する。

【００１２】請求項４の発明において、タスク情報格納
部は、各タスクの識別子と実行状態とを格納する。実行
保護タスク格納部は、各タスクの識別子と各タスクが使
用する最大のスタック容量とを格納すると共に、タスク
の実行状態が走行不可能状態でありかつスタックが割り
当てられていない場合に実行状態が走行状態か走行待ち
状態か走行可能状態かのいずれかの状態となり、かつタ
スクの実行状態が走行状態か走行待ち状態か走行可能状
態かのいずれかの状態である場合に走行不可能状態とな
る実行保護タスクの識別子と、実行保護タスクが走行不
可能状態となる場合に使用する最大のスタック容量とを
格納する。スタックポインタ格納部は、タスクの実行状
態とスタックポインタとを格納する。タスク切り替え要
求部は、タスクの切り替え要求を発生する。実行可能タ
スク抽出部は、タスク切り替え要求部がタスク切り替え
要求を発生したときに、タスク情報格納部と実行保護タ
スク格納部とを検索して、いずれのタスクに対しても実
行保護タスクではなくかつ実行状態が走行不可能状態で
あるタスクの識別子を抽出する。実行中タスク抽出部
は、タスクの実行状態が走行状態であるタスクの実行状
態を走行可能状態に変更し、タスク情報格納部を検索し
てタスクの実行状態が走行待ち状態または走行可能状態
であるタスクの識別子を抽出する。スタック使用可能タ
スク抽出部は、実行中タスク抽出部により抽出された識
別子を第１の識別子とし、実行可能タスク抽出部により
抽出された識別子を第２の識別子としたときに、実行保
護タスク格納部を検索して、第１の識別子に対応するタ
スクが第２の識別子に対応するタスクの実行保護タスク
である第１の識別子と第２の識別子との組合せを抽出す
る。スタックデータ圧縮部は、スタック使用可能タスク
抽出部により抽出された第１の識別子と第２の識別子と
の組合せにおいて実行保護タスクとなり得る識別子に対
応するタスクの実行状態をスタックポインタ格納部に格
納し、実行保護タスクとなり得るタスクの実行状態を走
行待ち状態に変更し、実行保護タスクとなり得るタスク
が使用しているスタック内のデータを圧縮し、実行保護
タスクとなり得るタスクのスタックポインタをスタック
ポインタ格納部に格納する。スタック使用可能タスク選
択部は、実行保護タスク格納部を検索して、スタック使
用可能タスク抽出部により抽出された第１の識別子と第
２の識別子との組合せにおける第１の識別子に対応する
タスクが実行不可能状態となる場合に使用する最大のス
タック容量を得、そのスタック容量よりも第１の識別子
に対応するタスクが現在使用しているスタック容量が小
さい第１の識別子と第２の識別子との組合せを抽出す
る。タスク切り替え部は、スタック使用可能タスク選択
部により抽出された第１の識別子と第２の識別子との組
合せにおける第１の識別子に対応するタスクの実行状態
を走行不可能状態にし、第２の識別子に対応するタスク
の実行状態を走行状態にする。スタックデータ展開部
は、タスク情報格納部を検索して実行状態が走行待ち状
態であるタスクの識別子を全て抽出し、スタックポイン
タ格納部を検索してタスク情報格納部から抽出した識別
子に対応するタスクのスタックポインタと実行状態とを
抽出し、スタックポインタ格納部からスタックポインタ
と実行状態とを抽出したタスクが使用しているスタック
内のデータを展開し、スタックポインタ格納部からスタ
ックポインタと実行状態とを抽出したタスクの実行状態
をスタックポインタ格納部から抽出した実行状態に変更
し、スタックポインタ格納部からスタックポインタと実
行状態とを抽出したタスクのスタックポインタと実行状
態とをスタックポインタ格納部から削除する。

【００１３】

【実施例】以下、本発明の実施例を図面を用いて詳細に
説明する。 （実施例１）図１は本発明の実施例１におけるスケジュ
ーリング装置の構成図で、このスケジューリング装置
は、タスク情報格納部１と、実行保護タスク格納部２
と、タスク切り替え要求部３と、実行可能タスク抽出部
４と、実行中タスク抽出部５と、スタック使用可能タス
ク抽出部６と、スタック使用可能タスク選択部７と、タ
スク切り替え部８とを備えている。タスク情報格納部１
は、各タスクの識別子と実行状態とを格納する。実行保
護タスク格納部２は、各タスクの識別子と各タスクが使
用する最大のスタック容量とを格納すると共に、タスク
の実行状態が走行不可能状態でありかつスタックが割り
当てられていない場合に実行状態が走行状態か走行待ち
状態か走行可能状態かのいずれかの状態となり、かつタ
スクの実行状態が走行状態か走行待ち状態か走行可能状
態かのいずれかの状態である場合に走行不可能状態とな
る実行保護タスクの識別子と、実行保護タスクが走行不
可能状態となる場合に使用する最大のスタック容量とを
格納する。タスク切り替え要求部３は、タスクの切り替
え要求を発生する。実行可能タスク抽出部４は、タスク
切り替え要求部３がタスク切り替え要求を発生したとき
に、タスク情報格納部１と実行保護タスク格納部２とを
検索して、いずれのタスクに対しても実行保護タスクで
はなくかつ実行状態が走行不可能状態であるタスクの識
別子を抽出する。実行中タスク抽出部５は、タスクの実
行状態が走行状態であるタスクの実行状態を走行可能状
態に変更し、タスク情報格納部１を検索してタスクの実
行状態が走行待ち状態または走行可能状態であるタスク
の識別子を抽出する。スタック使用可能タスク抽出部６
は、実行中タスク抽出部５により抽出された識別子を第
１の識別子とし、実行可能タスク抽出部４により抽出さ
れた識別子を第２の識別子としたときに、実行保護タス
ク格納部２を検索して、第１の識別子に対応するタスク
が第２の識別子に対応するタスクの実行保護タスクであ
る第１の識別子と第２の識別子との組合せを抽出する。
スタック使用可能タスク選択部７は、実行保護タスク格
納部２を検索して、スタック使用可能タスク抽出部６に
より抽出された第１の識別子と第２の識別子との組合せ
における第１の識別子に対応するタスクが走行不可能状
態となる場合に使用する最大のスタック容量を得、その
スタック容量よりも第１の識別子に対応するタスクが現
在使用しているスタック容量が小さい第１の識別子と第
２の識別子との組合せを抽出する。タスク切り替え部８
は、スタック使用可能タスク選択部７により抽出された
第１の識別子と第２の識別子との組合せにおける第１の
識別子に対応するタスクの実行状態を走行不可能状態に
し、第２の識別子に対応するタスクの実行状態を走行状
態にする。

【００１４】上記スケジューリング装置の動作につい
て、図２のフローチャートを参照しながら説明する。先
ずタスク切り替え要求部３が、タイマー割り込みなどに
よる従来周知の方法により、タスク切り替え要求を発生
する（ステップＳ１）。次に実行可能タスク抽出部４
が、タスク切り替え要求部３からのタスク切り替え要求
を受けて、タスク情報格納部１および実行保護タスク格
納部２から、いずれのタスクに対しても実行保護タスク
ではなく、かつ実行状態が走行不可能状態であるタスク
の識別子を検索し（ステップＳ２）、候補となる識別子
が見つからなかった場合、処理を終了する。なお、候補
となる識別子が見つからなかった場合に処理を終了する
とは、通常のスケジューリング装置に処理を戻す又はタ
スク切り替えを行わないということであり、このことは
以下も同様である。候補となる識別子が１つ以上存在す
れば、それらを抽出する（ステップＳ３）。次に実行中
タスク抽出部５が、実行状態が走行状態であるタスクを
走行可能状態に変更し、タスク情報格納部１から、実行
状態が走行可能状態または走行待ち状態であるタスクの
識別子を検索し（ステップＳ４）、候補となる識別子が
見つからなかった場合、処理を終了する。候補となる識
別子が１つ以上存在すれば、それらを抽出する（ステッ
プＳ５）。次にスタック使用可能タスク抽出部６が、実
行保護タスク格納部２から、第１の識別子に対応するタ
スクが第２の識別子に対応するタスクの実行保護タスク
である第１の識別子と第２の識別子との組合せを検索し
（ステップＳ６）、候補となる識別子が見つからなかっ
た場合、処理を終了する。候補となる識別子が１つ以上
存在すれば、それらを抽出する（ステップＳ７）。次に
スタック使用可能タスク選択部７が、スタック使用可能
タスク抽出部６により抽出された第１の識別子と第２の
識別子との組合せにおける第１の識別子に対応するタス
クの実行状態が走行不可能状態となる場合に使用する最
大のスタック容量を実行保護タスク格納部２から取得
し、そのスタック容量よりも第１の識別子に対応するタ
スクが現在使用しているスタック容量が小さい組合せを
検索し（ステップＳ８）、候補となる識別子が見つから
なかった場合、処理を終了する。候補となる識別子が１
つ以上存在すれば、それらを抽出する（ステップＳ
９）。次にタスク切り替え部８が、スタック使用可能タ
スク選択部７により抽出された第１の識別子に対応する
実行保護タスクの実行状態を走行不可能状態とし、第２
の識別子に対応するタスクの実行状態を走行状態として
（ステップＳ１０）、処理を終了する。

【００１５】次に、上記スケジューリング装置のさらに
具体的な動作の一例について説明する。図３はタスク情
報格納部１に格納されている内容の概念図で、識別子１
のタスクの実行状態は走行状態、識別子２のタスクの実
行状態は走行不可能状態、識別子３のタスクの実行状態
は走行可能状態である。なお、タスク情報格納部１に格
納されている実行状態は、タスクの実行状態の変化に伴
って適宜変更される。

【００１６】図４は実行保護タスク格納部２に格納され
ている内容の概念図で、識別子１のタスクが使用する最
大のスタック容量は５０であり、対応する実行保護タス
クはない。識別子２のタスクが使用する最大のスタック
容量は５０であり、対応する実行保護タスクの識別子は
１である。本実施例の場合、識別子２のタスクに対応す
る実行保護タスクの識別子が１であるということは、識
別子２のタスクが走行可能状態、走行待ち状態、走行状
態のいずれかの状態になるためには、識別子１のタスク
が使用するスタック容量が３０以下でなければならない
ということである。識別子３のタスクが使用する最大の
スタック容量は７０であり、対応する実行保護タスクは
ない。

【００１７】いま、走行状態である識別子１が使用して
いるスタック容量は２５であるとする。先ずタスク切り
替え要求部３が、タスク切り替え要求を発生し、実行可
能タスク抽出部４に渡す。これにより実行可能タスク抽
出部４が、タスク情報格納部１と実行保護タスク格納部
２とから、タスク情報格納部１に格納されている識別子
に対応するいずれのタスクに対しても実行保護タスクで
はなく、かつ実行状態が走行不可能状態であるタスクの
識別子を抽出する。抽出した結果、識別子２が候補とな
る。次に実行中タスク抽出部５が、実行状態が走行状態
であるタスクを走行可能状態に変更し、タスク情報格納
部１に格納されているタスクの実行状態が走行待ち状態
または走行可能状態であるタスクの識別子を抽出する。
抽出した結果、識別子１と識別子３とが候補となる。次
にスタック使用可能タスク抽出部６が、実行中タスク抽
出部５によって抽出された識別子１または識別子３に対
応する実行保護タスクの識別子を、実行保護タスク格納
部２から抽出し、実行可能タスク抽出部４によって抽出
された識別子２と照合する。抽出した結果、識別子１と
識別子２との組み合わせが候補として抽出される。次に
スタック使用可能タスク選択部７が、スタック使用可能
タスク抽出部６によって抽出された組合せより、実行保
護タスクとなり得る識別子１に対応するタスクが走行不
可能状態となる場合に使用する最大のスタック容量を実
行保護タスク格納部２から抽出し、３０を得る。さらに
スタック使用可能タスク選択部７が、識別子１に対応す
るタスクが使用しているスタック容量を従来周知の方法
により抽出し、２５を得る。この結果、２５は３０以下
であるので、識別子１と識別子２との組合せが候補とし
て抽出される。次にタスク切り替え部８が、スタック使
用可能タスク選択部７によって抽出された識別子１のタ
スクを走行不可能状態とし、識別子２のタスクを走行状
態とし、識別子１のタスクが使用していたスタックを使
用して識別子２のタスクを実行する。かくして、タスク
情報格納部１の内容は図５のようになる。このように、
実行可能なタスクとスタックを使用することができる別
のタスクとの組合せを選択できるので、スタックの有効
利用を図ることができ、スタックの容量が少ない場合に
はスケジューリングできないという従来の問題を良好に
低減できる。

【００１８】なお上記具体例においては、スタック使用
可能タスク選択部７により候補として抽出される識別子
の組み合わせが１組である例について説明したが、複数
の組み合わせが抽出される場合も考えられる。この場
合、抽出された識別子の組み合わせの中から、任意の１
つの組み合わせを選択する。 （実施例２）図６は本発明の実施例２におけるスケジュ
ーリング装置の構成図で、このスケジューリング装置
は、タスク情報格納部１１と、実行保護タスク格納部１
２と、タスク切り替え要求部１３と、実行可能タスク抽
出部１４と、実行中タスク抽出部１５と、スタック使用
可能タスク抽出部１６と、スタック使用可能タスク選択
部１７と、スタックポインタ格納部１８と、スタックデ
ータ圧縮部１９と、スタックデータ展開部２０と、タス
ク切り替え部２１とを備えている。タスク情報格納部１
１は、各タスクの識別子と実行状態とを格納する。実行
保護タスク格納部１２は、各タスクの識別子と各タスク
が使用する最大のスタック容量とを格納すると共に、タ
スクの実行状態が走行不可能状態でありかつスタックが
割り当てられていない場合に実行状態が走行状態か走行
待ち状態か走行可能状態かのいずれかの状態となり、か
つタスクの実行状態が走行状態か走行待ち状態か走行可
能状態かのいずれかの状態である場合に走行不可能状態
となる実行保護タスクの識別子と、実行保護タスクが走
行不可能状態となる場合に使用する最大のスタック容量
とを格納する。タスク切り替え要求部１３は、タスクの
切り替え要求を発生する。実行可能タスク抽出部１４
は、タスク切り替え要求部１３がタスク切り替え要求を
発生したときに、タスク情報格納部１１と実行保護タス
ク格納部１２とを検索して、いずれのタスクに対しても
実行保護タスクではなくかつ実行状態が走行不可能状態
であるタスクの識別子を抽出する。実行中タスク抽出部
１５は、タスクの実行状態が走行状態であるタスクの実
行状態を走行可能状態に変更し、タスク情報格納部１１
を検索してタスクの実行状態が走行待ち状態または走行
可能状態であるタスクの識別子を抽出する。スタック使
用可能タスク抽出部１６は、実行中タスク抽出部１５に
より抽出された識別子を第１の識別子とし、実行可能タ
スク抽出部１４により抽出された識別子を第２の識別子
としたときに、実行保護タスク格納部１２を検索して、
第１の識別子に対応するタスクが第２の識別子に対応す
るタスクの実行保護タスクである第１の識別子と第２の
識別子との組合せを抽出する。スタック使用可能タスク
選択部１７は、実行保護タスク格納部１２を検索して、
スタック使用可能タスク抽出部１６により抽出された第
１の識別子と第２の識別子との組合せにおける第１の識
別子に対応するタスクが走行不可能状態となる場合に使
用する最大のスタック容量を得、そのスタック容量より
も第１の識別子に対応するタスクが現在使用しているス
タック容量が小さい第１の識別子と第２の識別子との組
合せを抽出する。スタックポインタ格納部１８は、タス
クの識別子と実行状態とスタックポインタとを格納す
る。スタックデータ圧縮部１９は、スタック使用可能タ
スク抽出部１６により抽出された第１の識別子と第２の
識別子との組合せにおいて実行保護タスクとなり得る識
別子に対応するタスクの実行状態をスタックポインタ格
納部１８に格納し、実行保護タスクとなり得るタスクの
実行状態を走行待ち状態に変更し、実行保護タスクとな
り得るタスクが使用しているスタック内のデータを圧縮
し、実行保護タスクとなり得るタスクのスタックポイン
タをスタックポインタ格納部１８に格納する。スタック
データ展開部２０は、タスク情報格納部１１を検索して
実行状態が走行待ち状態であるタスクの識別子を全て抽
出し、スタックポインタ格納部１８を検索してタスク情
報格納部１１から抽出した識別子に対応するタスクのス
タックポインタと実行状態とを抽出し、スタックポイン
タ格納部１８からスタックポインタと実行状態とを抽出
したタスクが使用しているスタック内のデータを展開
し、スタックポインタ格納部１８からスタックポインタ
と実行状態とを抽出したタスクの実行状態をスタックポ
インタ格納部１８から抽出した実行状態に変更し、スタ
ックポインタ格納部１８からスタックポインタと実行状
態とを抽出したタスクのスタックポインタと実行状態と
をスタックポインタ格納部１８から削除する。タスク切
り替え部２１は、スタック使用可能タスク選択部１７に
より抽出された第１の識別子と第２の識別子との組合せ
における第１の識別子に対応するタスクの実行状態を走
行不可能状態にし、第２の識別子に対応するタスクの実
行状態を走行状態にする。

【００１９】次に上記スケジューリング装置の動作につ
いて、図７のフローチャートを参照しながら説明する。
先ずタスク切り替え要求部１３が、タイマー割り込みな
どによる従来周知の方法により、タスク切り替え要求を
発生する（ステップＳ１１）。次に実行可能タスク抽出
部１４が、タスク切り替え要求部１３からのタスク切り
替え要求を受けて、タスク情報格納部１１および実行保
護タスク格納部１２から、いずれのタスクに対しても実
行保護タスクではなく、かつ実行状態が走行不可能状態
であるタスクの識別子を検索し（ステップＳ１２）、候
補となる識別子が見つからなかった場合、処理を終了す
る。候補となる識別子が１つ以上存在すれば、それらを
抽出する（ステップＳ１３）。次に実行中タスク抽出部
１５が、実行状態が走行状態であるタスクを走行可能状
態に変更し、タスク情報格納部１１から、実行状態が走
行可能状態または走行待ち状態であるタスクの識別子を
検索し（ステップＳ１４）、候補となる識別子が見つか
らなかった場合、処理を終了する。候補となる識別子が
１つ以上存在すれば、それらを抽出する（ステップＳ１
５）。次にスタック使用可能タスク抽出部１６が、実行
保護タスク格納部１２から、実行中タスク抽出部１５に
より抽出された第１の識別子の候補と実行可能タスク抽
出部１４により抽出された第２の識別子の候補とのう
ち、第１の識別子に対応するタスクが第２の識別子に対
応するタスクの実行保護タスクである第１の識別子と第
２の識別子との組合せを検索し（ステップＳ１６）、候
補となる識別子が見つからなかった場合、処理を終了す
る。候補となる識別子が１つ以上存在すれば、それらを
抽出する（ステップＳ１７）。次にスタックデータ圧縮
部１９が、スタック使用可能タスク抽出部１６により抽
出された識別子の組合せのうち実行保護タスクとなり得
る識別子に対応するタスクの実行状態をスタックポイン
タ格納部１８に格納し、実行保護タスクとなり得る識別
子に対応するタスクの実行状態を走行待ち状態に変更
し、実行保護タスクとなり得る識別子に対応するタスク
が使用しているスタック内のデータを圧縮し、実行保護
タスクとなり得る識別子に対応するタスクのスタックポ
インタをスタックポインタ格納部１８に格納する（ステ
ップＳ１８）。次にスタック使用可能タスク選択部１７
が、スタック使用可能タスク抽出部１６により抽出され
てスタックデータ圧縮部１９により圧縮された第１の識
別子と第２の識別子との組合せのうち、第１の識別子に
対応するタスクの実行状態が走行不可能状態となる場合
に使用する最大のスタック容量を実行保護タスク格納部
１２から取得し、そのスタック容量よりも第１の識別子
に対応するタスクが現在使用しているスタック容量が小
さい組合せを検索し（ステップＳ１９）、候補となる識
別子が見つからなかった場合、処理を終了する。候補と
なる識別子が１つ以上存在すれば、それらを抽出する
（ステップＳ２０）。次にタスク切り替え部２１が、ス
タック使用可能タスク選択部１７により候補として抽出
された第１の識別子に対応する実行保護タスクの実行状
態を走行不可能状態とし、第２の識別子に対応するタス
クの実行状態を走行状態とし、処理を実行する（ステッ
プＳ２１）。タスク切り替え部２１により切り替えられ
たタスクの処理が終了した場合、スタックデータ展開部
２０が、タスク情報格納部１１から、実行状態が走行待
ち状態であるタスクの識別子を全て抽出し、抽出された
それぞれの識別子に対して、スタックポインタ格納部１
８から識別子に対応するスタックポインタと実行状態と
を抽出し、その識別子に対応するタスクが使用している
スタック内のデータを展開し、そのタスクの実行状態を
スタックポインタ格納部１８から抽出した実行状態に変
更し、そのタスクのスタックポインタと実行状態とをス
タックポインタ格納部１８から削除する（ステップＳ２
２）。

【００２０】次に、上記スケジューリング装置のさらに
具体的な動作の一例について説明する。図８はタスク情
報格納部１１に格納されている内容の概念図で、識別子
１のタスクの実行状態は走行状態、識別子２のタスクの
実行状態は走行不可能状態、識別子３のタスクの実行状
態は走行待ち状態である。なお、タスク情報格納部１１
に格納されている実行状態は、タスクの実行状態の変化
に伴って適宜変更される。

【００２１】図９は実行保護タスク格納部１２に格納さ
れている内容の概念図で、識別子１のタスクが使用する
最大のスタック容量は５０であり、対応する実行保護タ
スクはない。識別子２のタスクが使用する最大のスタッ
ク容量は５０であり、対応する実行保護タスクの識別子
は１である。本実施例の場合識別子２のタスクに対応す
る実行保護タスクの識別子が１であるということは、識
別子２のタスクが走行可能状態、走行待ち状態、走行状
態のいずれかの状態になるためには、識別子１のタスク
が使用するスタック容量が３５以下でなければならない
ということである。識別子３のタスクが使用する最大の
スタック容量は７０であり、対応する実行保護タスクは
ない。

【００２２】ここで、データ圧縮の一例を示す。例えば
８ビットのマイクロコンピュータで、プログラムが４キ
ロバイト以内である場合、２バイトをスタックとして使
用する。スタック内で実際に使用するのは１２ビットで
あるため、４ビットは不要である。そこで、４ビット分
を削除する。上述の圧縮方法により、スタックが５回積
まれたと考えると、（１２×５＋４）／１６×５＝０．
８という計算より、圧縮しない場合の８割の容量に圧縮
される。

【００２３】いま、走行状態である識別子１が使用して
いるスタック容量は４０であるとする。先ずタスク切り
替え要求部１３が、タスク切り替え要求を発生し、実行
可能タスク抽出部１４に渡す。これにより実行可能タス
ク抽出部１４が、タスク情報格納部１１と実行保護タス
ク格納部１２とから、タスク情報格納部１１に格納され
ている識別子に対応するいずれのタスクに対しても実行
保護タスクではなく、かつ実行状態が走行不可能状態で
あるタスクの識別子を抽出する。抽出した結果、識別子
２が候補となる。次に実行中タスク抽出部１５が、実行
状態が走行状態であるタスクを走行可能状態に変更し、
タスク情報格納部１１に格納されているタスクの実行状
態が走行待ち状態または走行可能状態であるタスクの識
別子を抽出する。抽出した結果、識別子１と識別子３と
が候補となる。次にスタック使用可能タスク抽出部１６
が、実行中タスク抽出部１５によって抽出された識別子
１または識別子３に対応する実行保護タスクの識別子
を、実行保護タスク格納部１２から抽出し、実行可能タ
スク抽出部１４によって抽出された識別子２と照合す
る。抽出した結果、識別子１と識別子２との組み合わせ
が候補として抽出される。次にスタックデータ圧縮部１
９が、スタック使用可能タスク抽出部１６によって抽出
された識別子１と識別子２との組合せにおいて、実行保
護タスクとなり得る識別子１に対応するタスクの実行状
態をスタックポインタ格納部１８に格納し、識別子１に
対応するタスクの実行状態を走行待ち状態に変更し、識
別子１に対応するタスクが使用しているスタック内のデ
ータを圧縮し、識別子１に対応するタスクのスタックポ
インタをスタックポインタ格納部１８に格納する。かく
して、タスク情報格納部１１の内容は図１０のようにな
り、スタックポインタ格納部１８の内容は図１１のよう
になる。すなわち本実施例の場合、スタックポインタは
１００である。またスタック内のデータを圧縮した結
果、識別子１に対応するタスクが使用しているスタック
容量は８０％に圧縮され、３２となる。次にスタック使
用可能タスク選択部１７が、スタック使用可能タスク抽
出部１６によって抽出された組合せより、実行保護タス
クとなり得る識別子１に対応するタスクが走行不可能状
態となる場合に使用する最大のスタック容量を実行保護
タスク格納部１２から抽出し、３５を得る。さらに、ス
タック使用可能タスク選択部が、識別子１に対応するタ
スクが使用しているスタック容量を従来周知の方法によ
り抽出し、３２を得る。この結果、３２は３５以下であ
るので、識別子１と識別子２との組合せが候補として抽
出される。次にタスク切り替え部２１が、スタック使用
可能タスク選択部１７によって抽出された識別子１のタ
スクを走行不可能状態とし、識別子２のタスクを走行状
態とし、識別子１のタスクが使用していたスタックを使
用して識別子２のタスクを実行する。かくしてタスク情
報格納部１１の内容は図１２のようになる。タスク切り
替え部２１により切り替えられたタスクの処理が終了し
た場合、スタックデータ展開部２０が、タスク情報格納
部１１から実行状態が走行待ち状態であるタスクの識別
子を全て抽出する。切り替えられたタスクの処理が終了
した直後のタスク情報格納部１１の内容は図１３のよう
になっている。抽出した結果、識別子１と識別子３とが
候補となる。抽出されたそれぞれの識別子に対して、ス
タックポインタ格納部１８より、抽出された識別子と同
一の識別子に対応するスタックポインタと実行状態とを
抽出する。抽出した結果、識別子１のスタックポインタ
は１００、実行状態は走行可能状態であり、識別子３
は、該当するスタックポインタおよび実行状態はない。
この抽出結果より、識別子１に対応するタスクが使用し
ているスタック内のデータを展開し、識別子１に対応す
るタスクの実行状態を走行可能状態に変更し、識別子１
に対応するタスクのスタックポインタと以前の実行状態
とをスタックポインタ格納部１８から削除する。かくし
てタスク情報格納部１１の内容は図１４のようになり、
スタックポインタ格納部１８の内容は図１５のようにな
る。

【００２４】このように、実行可能なタスクとスタック
を使用することができる別のタスクとの組合せを選択で
きるので、スタックの有効利用を図ることができ、スタ
ックの容量が少ない場合にはスケジューリングできない
という従来の問題を良好に低減できる。また、実行可能
なタスクとスタックを使用することができる別のタスク
との組合せの範囲を広げることができるので、スタック
をより一層有効利用できる。

【００２５】なお上記具体例においては、スタック使用
可能タスク選択部１７により候補として抽出される識別
子の組み合わせが１組である例について説明したが、複
数の組み合わせが抽出される場合も考えられる。この場
合、抽出された識別子の組み合わせの中から、任意の１
つの組み合わせを選択する。またスタックのデータの圧
縮方法は、上記具体例で説明した方法に限られるもので
はなく、例えば適応型レンペル・ジブ・コーディング法
など、他の方法を用いてもよい。

【００２６】

【発明の効果】以上説明したように本発明によれば、走
行可能状態と走行待ち状態と走行状態と走行不可能状態
との少なくとも４つの実行状態とシステム内で一意の識
別子とを持つタスクが、タスク切り替えにより複数個実
行されるシステムにおけるスケジューリング装置であっ
て、各タスクの識別子と実行状態とを格納するタスク情
報格納部と、各タスクの識別子と各タスクが使用する最
大のスタック容量とを格納すると共に、タスクの実行状
態が走行不可能状態でありかつスタックが割り当てられ
ていない場合に実行状態が走行状態か走行待ち状態か走
行可能状態かのいずれかの状態となり、かつタスクの実
行状態が走行状態か走行待ち状態か走行可能状態かのい
ずれかの状態である場合に走行不可能状態となる実行保
護タスクの識別子と、実行保護タスクが走行不可能状態
となる場合に使用する最大のスタック容量とを格納する
実行保護タスク格納部と、タスクの切り替え要求を発生
するタスク切り替え要求部と、タスク切り替え要求部が
タスク切り替え要求を発生したときに、タスク情報格納
部と実行保護タスク格納部とを検索して、いずれのタス
クに対しても実行保護タスクではなくかつ実行状態が走
行不可能状態であるタスクの識別子を抽出する実行可能
タスク抽出部と、タスクの実行状態が走行状態であるタ
スクの実行状態を走行可能状態に変更し、タスク情報格
納部を検索してタスクの実行状態が走行待ち状態または
走行可能状態であるタスクの識別子を抽出する実行中タ
スク抽出部と、実行中タスク抽出部により抽出された識
別子を第１の識別子とし、実行可能タスク抽出部により
抽出された識別子を第２の識別子としたときに、実行保
護タスク格納部を検索して、第１の識別子に対応するタ
スクが第２の識別子に対応するタスクの実行保護タスク
である第１の識別子と第２の識別子との組合せを抽出す
るスタック使用可能タスク抽出部と、実行保護タスク格
納部を検索して、スタック使用可能タスク抽出部により
抽出された第１の識別子と第２の識別子との組合せにお
ける第１の識別子に対応するタスクが実行不可能状態と
なる場合に使用する最大のスタック容量を得、そのスタ
ック容量よりも第１の識別子に対応するタスクが現在使
用しているスタック容量が小さい第１の識別子と第２の
識別子との組合せを抽出するスタック使用可能タスク選
択部と、スタック使用可能タスク選択部により抽出され
た第１の識別子と第２の識別子との組合せにおける第１
の識別子に対応するタスクの実行状態を走行不可能状態
にし、第２の識別子に対応するタスクの実行状態を走行
状態にするタスク切り替え部と、を備えたので、実行可
能なタスクとスタックを使用することができる別のタス
クとの組合せを選択できることから、スタックの有効利
用を図ることができ、スタックの容量が少ない場合には
スケジューリングできないという従来の問題を良好に低
減できる。

【００２７】また、走行可能状態と走行待ち状態と走行
状態と走行不可能状態との少なくとも４つの実行状態と
システム内で一意の識別子とを持つタスクが、タスク切
り替えにより複数個実行されるシステムにおけるスケジ
ューリング装置であって、各タスクの識別子と実行状態
とを格納するタスク情報格納部と、各タスクの識別子と
各タスクが使用する最大のスタック容量とを格納すると
共に、タスクの実行状態が走行不可能状態でありかつス
タックが割り当てられていない場合に実行状態が走行状
態か走行待ち状態か走行可能状態かのいずれかの状態と
なり、かつタスクの実行状態が走行状態か走行待ち状態
か走行可能状態かのいずれかの状態である場合に走行不
可能状態となる実行保護タスクの識別子と、実行保護タ
スクが走行不可能状態となる場合に使用する最大のスタ
ック容量とを格納する実行保護タスク格納部と、タスク
の識別子と実行状態とスタックポインタとを格納するス
タックポインタ格納部と、タスクの切り替え要求を発生
するタスク切り替え要求部と、タスク切り替え要求部が
タスク切り替え要求を発生したときに、タスク情報格納
部と実行保護タスク格納部とを検索して、いずれのタス
クに対しても実行保護タスクではなくかつ実行状態が走
行不可能状態であるタスクの識別子を抽出する実行可能
タスク抽出部と、タスクの実行状態が走行状態であるタ
スクの実行状態を走行可能状態に変更し、タスク情報格
納部を検索してタスクの実行状態が走行待ち状態または
走行可能状態であるタスクの識別子を抽出する実行中タ
スク抽出部と、実行中タスク抽出部により抽出された識
別子を第１の識別子とし、実行可能タスク抽出部により
抽出された識別子を第２の識別子としたときに、実行保
護タスク格納部を検索して、第１の識別子に対応するタ
スクが第２の識別子に対応するタスクの実行保護タスク
である第１の識別子と第２の識別子との組合せを抽出す
るスタック使用可能タスク抽出部と、スタック使用可能
タスク抽出部により抽出された第１の識別子と第２の識
別子との組合せにおいて実行保護タスクとなり得る識別
子に対応するタスクの実行状態をスタックポインタ格納
部に格納し、実行保護タスクとなり得るタスクの実行状
態を走行待ち状態に変更し、実行保護タスクとなり得る
タスクが使用しているスタック内のデータを圧縮し、実
行保護タスクとなり得るタスクのスタックポインタをス
タックポインタ格納部に格納するスタックデータ圧縮部
と、実行保護タスク格納部を検索して、スタック使用可
能タスク抽出部により抽出された第１の識別子と第２の
識別子との組合せにおける第１の識別子に対応するタス
クが実行不可能状態となる場合に使用する最大のスタッ
ク容量を得、そのスタック容量よりも第１の識別子に対
応するタスクが現在使用しているスタック容量が小さい
第１の識別子と第２の識別子との組合せを抽出するスタ
ック使用可能タスク選択部と、スタック使用可能タスク
選択部により抽出された第１の識別子と第２の識別子と
の組合せにおける第１の識別子に対応するタスクの実行
状態を走行不可能状態にし、第２の識別子に対応するタ
スクの実行状態を走行状態にするタスク切り替え部と、
タスク情報格納部を検索して実行状態が走行待ち状態で
あるタスクの識別子を全て抽出し、スタックポインタ格
納部を検索してタスク情報格納部から抽出した識別子に
対応するタスクのスタックポインタと実行状態とを抽出
し、スタックポインタ格納部からスタックポインタと実
行状態とを抽出したタスクが使用しているスタック内の
データを展開し、スタックポインタ格納部からスタック
ポインタと実行状態とを抽出したタスクの実行状態をス
タックポインタ格納部から抽出した実行状態に変更し、
スタックポインタ格納部からスタックポインタと実行状
態とを抽出したタスクのスタックポインタと実行状態と
をスタックポインタ格納部から削除するスタックデータ
展開部と、を備えたので、実行可能なタスクとスタック
を使用することができる別のタスクとの組合せを選択で
きることから、スタックの有効利用を図ることができ、
スタックの容量が少ない場合にはスケジューリングでき
ないという従来の問題を良好に低減できる。さらに、実
行可能なタスクとスタックを使用することができる別の
タスクとの組合せの範囲を広げることができることか
ら、スタックをより一層有効利用できる。

【図面の簡単な説明】

【図１】本発明の実施例１におけるスケジューリング装
置の構成図である。

【図２】本発明の実施例１におけるスケジューリング装
置の動作を説明するフローチャートである。

【図３】タスク切り替え前におけるタスク情報格納部の
内容の概念図である。

【図４】実行保護タスク格納部の内容の概念図である。

【図５】タスク切り替え後におけるタスク情報格納部の
内容の概念図である。

【図６】本発明の実施例２におけるスケジューリング装
置の構成図である。

【図７】本発明の実施例２におけるスケジューリング装
置の動作を説明するフローチャートである。

【図８】タスク切り替え前におけるタスク情報格納部の
内容の概念図である。

【図９】実行保護タスク格納部の内容の概念図である。

【図１０】タスク切り替え前におけるタスク情報格納部
の内容の概念図である。

【図１１】スタックポインタ格納部の内容の概念図であ
る。

【図１２】タスク切り替え後におけるタスク情報格納部
の内容の概念図である。

【図１３】切り替えられたタスクの処理が終了した直後
におけるタスク情報格納部の内容の概念図である。

【図１４】処理終了後におけるタスク情報格納部の内容
の概念図である。

【図１５】処理終了後におけるスタックポインタ格納部
の内容の概念図である。

【符号の説明】

１ タスク情報格納部 ２ 実行保護タスク格納部 ３ タスク切り替え要求部 ４ 実行可能タスク抽出部 ５ 実行中タスク抽出部 ６ スタック使用可能タスク抽出部 ７ スタック使用可能タスク選択部 ８ タスク切り替え部 １１ タスク情報格納部 １２ 実行保護タスク格納部 １３ タスク切り替え要求部 １４ 実行可能タスク抽出部 １５ 実行中タスク抽出部 １６ スタック使用可能タスク抽出部 １７ スタック使用可能タスク選択部 １８ スタックポインタ格納部 １９ スタックデータ圧縮部 ２０ スタックデータ展開部 ２１ タスク切り替え部

───────────────────────────────────────────────────── フロントページの続き (72)発明者 安武 剛一 大阪府門真市大字門真1006番地 松下電 器産業株式会社内 (72)発明者 伊藤 謙次 大阪府門真市大字門真1006番地 松下電 器産業株式会社内 (72)発明者 安倍 秀二 大阪府門真市大字門真1006番地 松下電 器産業株式会社内

Claims (4)

(57)【特許請求の範囲】
1. 【請求項１】 走行可能状態と走行待ち状態と走行状態
   と走行不可能状態との少なくとも４つの実行状態とシス
   テム内で一意の識別子とを持つタスクが、タスク切り替
   えにより複数個実行されるシステムにおけるスケジュー
   リング方法であって、各タスクの識別子と実行状態とを
   格納するタスク情報格納部と、各タスクの識別子と各タ
   スクが使用する最大のスタック容量とを格納すると共
   に、タスクの実行状態が走行不可能状態でありかつスタ
   ックが割り当てられていない場合に実行状態が走行状態
   か走行待ち状態か走行可能状態かのいずれかの状態とな
   り、かつタスクの実行状態が走行状態か走行待ち状態か
   走行可能状態かのいずれかの状態である場合に走行不可
   能状態となる実行保護タスクの識別子と、前記実行保護
   タスクが走行不可能状態となる場合に使用する最大のス
   タック容量とを格納する実行保護タスク格納部とを用
   い、 タスクの切り替え要求を発生するタスク切り替え要求ス
   テップと、 前記タスク切り替え要求ステップにおいてタスク切り替
   え要求が発生されることにより、前記タスク情報格納部
   と前記実行保護タスク格納部とを検索して、いずれのタ
   スクに対しても実行保護タスクではなくかつ実行状態が
   走行不可能状態であるタスクの識別子を抽出する実行可
   能タスク抽出ステップと、 タスクの実行状態が走行状態であるタスクの実行状態を
   走行可能状態に変更し、前記タスク情報格納部を検索し
   てタスクの実行状態が走行待ち状態または走行可能状態
   であるタスクの識別子を抽出する実行中タスク抽出ステ
   ップと、 前記実行中タスク抽出ステップにおいて抽出された識別
   子を第１の識別子とし、前記実行可能タスク抽出ステッ
   プにおいて抽出された識別子を第２の識別子としたとき
   に、前記実行保護タスク格納部を検索して、前記第１の
   識別子に対応するタスクが前記第２の識別子に対応する
   タスクの実行保護タスクである第１の識別子と第２の識
   別子との組合せを抽出するスタック使用可能タスク抽出
   ステップと、 前記実行保護タスク格納部を検索して、前記スタック使
   用可能タスク抽出ステップにおいて抽出された第１の識
   別子と第２の識別子との組合せにおける第１の識別子に
   対応するタスクが実行不可能状態となる場合に使用する
   最大のスタック容量を得、そのスタック容量よりも前記
   第１の識別子に対応するタスクが現在使用しているスタ
   ック容量が小さい第１の識別子と第２の識別子との組合
   せを抽出するスタック使用可能タスク選択ステップと、 前記スタック使用可能タスク選択ステップにおいて抽出
   された第１の識別子と第２の識別子との組合せにおける
   第１の識別子に対応するタスクの実行状態を走行不可能
   状態にし、第２の識別子に対応するタスクの実行状態を
   走行状態にするタスク切り替えステップと、 を実行することを特徴とするスケジューリング方法。
2. 【請求項２】 走行可能状態と走行待ち状態と走行状態
   と走行不可能状態との少なくとも４つの実行状態とシス
   テム内で一意の識別子とを持つタスクが、タスク切り替
   えにより複数個実行される計算機システムにおけるスケ
   ジューリング装置であって、 各タスクの識別子と実行状態とを格納するタスク情報格
   納部と、 各タスクの識別子と各タスクが使用する最大のスタック
   容量とを格納すると共に、タスクの実行状態が走行不可
   能状態でありかつスタックが割り当てられていない場合
   に実行状態が走行状態か走行待ち状態か走行可能状態か
   のいずれかの状態となり、かつタスクの実行状態が走行
   状態か走行待ち状態か走行可能状態かのいずれかの状態
   である場合に走行不可能状態となる実行保護タスクの識
   別子と、前記実行保護タスクが走行不可能状態となる場
   合に使用する最大のスタック容量とを格納する実行保護
   タスク格納部と、 タスクの切り替え要求を発生するタスク切り替え要求部
   と、 前記タスク切り替え要求部がタスク切り替え要求を発生
   したときに、前記タスク情報格納部と前記実行保護タス
   ク格納部とを検索して、いずれのタスクに対しても実行
   保護タスクではなくかつ実行状態が走行不可能状態であ
   るタスクの識別子を抽出する実行可能タスク抽出部と、 タスクの実行状態が走行状態であるタスクの実行状態を
   走行可能状態に変更し、前記タスク情報格納部を検索し
   てタスクの実行状態が走行待ち状態または走行可能状態
   であるタスクの識別子を抽出する実行中タスク抽出部
   と、 前記実行中タスク抽出部により抽出された識別子を第１
   の識別子とし、前記実行可能タスク抽出部により抽出さ
   れた識別子を第２の識別子としたときに、前記実行保護
   タスク格納部を検索して、前記第１の識別子に対応する
   タスクが前記第２の識別子に対応するタスクの実行保護
   タスクである第１の識別子と第２の識別子との組合せを
   抽出するスタック使用可能タスク抽出部と、 前記実行保護タスク格納部を検索して、前記スタック使
   用可能タスク抽出部により抽出された第１の識別子と第
   ２の識別子との組合せにおける第１の識別子に対応する
   タスクが実行不可能状態となる場合に使用する最大のス
   タック容量を得、そのスタック容量よりも前記第１の識
   別子に対応するタスクが現在使用しているスタック容量
   が小さい第１の識別子と第２の識別子との組合せを抽出
   するスタック使用可能タスク選択部と、 前記スタック使用可能タスク選択部により抽出された第
   １の識別子と第２の識別子との組合せにおける第１の識
   別子に対応するタスクの実行状態を走行不可能状態に
   し、第２の識別子に対応するタスクの実行状態を走行状
   態にするタスク切り替え部と、 を備えたことを特徴とするスケジューリング装置。
3. 【請求項３】 走行可能状態と走行待ち状態と走行状態
   と走行不可能状態との少なくとも４つの実行状態とシス
   テム内で一意の識別子とを持つタスクが、タスク切り替
   えにより複数個実行される計算機システムにおけるスケ
   ジューリング方法であって、各タスクの識別子と実行状
   態とを格納するタスク情報格納部と、各タスクの識別子
   と各タスクが使用する最大のスタック容量とを格納する
   と共に、タスクの実行状態が走行不可能状態でありかつ
   スタックが割り当てられていない場合に実行状態が走行
   状態か走行待ち状態か走行可能状態かのいずれかの状態
   となり、かつタスクの実行状態が走行状態か走行待ち状
   態か走行可能状態かのいずれかの状態である場合に走行
   不可能状態となる実行保護タスクの識別子と、前記実行
   保護タスクが走行不可能状態となる場合に使用する最大
   のスタック容量とを格納する実行保護タスク格納部と、
   タスクの識別子と実行状態とスタックポインタとを格納
   するスタックポインタ格納部とを用いて、 タスクの切り替え要求を発生するタスク切り替え要求ス
   テップと、 前記タスク切り替え要求ステップにおいてタスク切り替
   え要求が発生されることにより、前記タスク情報格納部
   と前記実行保護タスク格納部とを検索して、いずれのタ
   スクに対しても実行保護タスクではなくかつ実行状態が
   走行不可能状態であるタスクの識別子を抽出する実行可
   能タスク抽出ステップと、 タスクの実行状態が走行状態であるタスクの実行状態を
   走行可能状態に変更し、前記タスク情報格納部を検索し
   てタスクの実行状態が走行待ち状態または走行可能状態
   であるタスクの識別子を抽出する実行中タスク抽出ステ
   ップと、 前記実行中タスク抽出ステップにおいて抽出された識別
   子を第１の識別子とし、前記実行可能タスク抽出ステッ
   プにおいて抽出された識別子を第２の識別子としたとき
   に、前記実行保護タスク格納部を検索して、前記第１の
   識別子に対応するタスクが前記第２の識別子に対応する
   タスクの実行保護タスクである第１の識別子と第２の識
   別子との組合せを抽出するスタック使用可能タスク抽出
   ステップと、 前記スタック使用可能タスク抽出ステップにおいて抽出
   された第１の識別子と第２の識別子との組合せにおいて
   実行保護タスクとなり得る識別子に対応するタスクの実
   行状態を前記スタックポインタ格納部に格納し、前記実
   行保護タスクとなり得るタスクの実行状態を走行待ち状
   態に変更し、前記実行保護タスクとなり得るタスクが使
   用しているスタック内のデータを圧縮し、前記実行保護
   タスクとなり得るタスクのスタックポインタを前記スタ
   ックポインタ格納部に格納するスタックデータ圧縮ステ
   ップと、 前記実行保護タスク格納部を検索して、前記スタック使
   用可能タスク抽出ステップにおいて抽出された第１の識
   別子と第２の識別子との組合せにおける第１の識別子に
   対応するタスクが実行不可能状態となる場合に使用する
   最大のスタック容量を得、そのスタック容量よりも前記
   第１の識別子に対応するタスクが現在使用しているスタ
   ック容量が小さい第１の識別子と第２の識別子との組合
   せを抽出するスタック使用可能タスク選択ステップと、 前記スタック使用可能タスク選択ステップにおいて抽出
   された第１の識別子と第２の識別子との組合せにおける
   第１の識別子に対応するタスクの実行状態を走行不可能
   状態にし、第２の識別子に対応するタスクの実行状態を
   走行状態にするタスク切り替えステップと、 前記タスク情報格納部を検索して実行状態が走行待ち状
   態であるタスクの識別子を全て抽出し、前記スタックポ
   インタ格納部を検索して前記タスク情報格納部から抽出
   した識別子に対応するタスクのスタックポインタと実行
   状態とを抽出し、前記スタックポインタ格納部からスタ
   ックポインタと実行状態とを抽出したタスクが使用して
   いるスタック内のデータを展開し、前記スタックポイン
   タ格納部からスタックポインタと実行状態とを抽出した
   タスクの実行状態をスタックポインタ格納部から抽出し
   た実行状態に変更し、前記スタックポインタ格納部から
   スタックポインタと実行状態とを抽出したタスクのスタ
   ックポインタと実行状態とを前記スタックポインタ格納
   部から削除するスタックデータ展開ステップと、 を実行することを特徴とするスケジューリング方法。
4. 【請求項４】 走行可能状態と走行待ち状態と走行状態
   と走行不可能状態との少なくとも４つの実行状態とシス
   テム内で一意の識別子とを持つタスクが、タスク切り替
   えにより複数個実行される計算機システムにおけるスケ
   ジューリング装置であって、 各タスクの識別子と実行状態とを格納するタスク情報格
   納部と、 各タスクの識別子と各タスクが使用する最大のスタック
   容量とを格納すると共に、タスクの実行状態が走行不可
   能状態でありかつスタックが割り当てられていない場合
   に実行状態が走行状態か走行待ち状態か走行可能状態か
   のいずれかの状態となり、かつタスクの実行状態が走行
   状態か走行待ち状態か走行可能状態かのいずれかの状態
   である場合に走行不可能状態となる実行保護タスクの識
   別子と、前記実行保護タスクが走行不可能状態となる場
   合に使用する最大のスタック容量とを格納する実行保護
   タスク格納部と、 タスクの識別子と実行状態とスタックポインタとを格納
   するスタックポインタ格納部と、 タスクの切り替え要求を発生するタスク切り替え要求部
   と、 前記タスク切り替え要求部がタスク切り替え要求を発生
   したときに、前記タスク情報格納部と前記実行保護タス
   ク格納部とを検索して、いずれのタスクに対しても実行
   保護タスクではなくかつ実行状態が走行不可能状態であ
   るタスクの識別子を抽出する実行可能タスク抽出部と、 タスクの実行状態が走行状態であるタスクの実行状態を
   走行可能状態に変更し、前記タスク情報格納部を検索し
   てタスクの実行状態が走行待ち状態または走行可能状態
   であるタスクの識別子を抽出する実行中タスク抽出部
   と、 前記実行中タスク抽出部により抽出された識別子を第１
   の識別子とし、前記実行可能タスク抽出部により抽出さ
   れた識別子を第２の識別子としたときに、前記実行保護
   タスク格納部を検索して、前記第１の識別子に対応する
   タスクが前記第２の識別子に対応するタスクの実行保護
   タスクである第１の識別子と第２の識別子との組合せを
   抽出するスタック使用可能タスク抽出部と、 前記スタック使用可能タスク抽出部により抽出された第
   １の識別子と第２の識別子との組合せにおいて実行保護
   タスクとなり得る識別子に対応するタスクの実行状態を
   前記スタックポインタ格納部に格納し、前記実行保護タ
   スクとなり得るタスクの実行状態を走行待ち状態に変更
   し、前記実行保護タスクとなり得るタスクが使用してい
   るスタック内のデータを圧縮し、前記実行保護タスクと
   なり得るタスクのスタックポインタを前記スタックポイ
   ンタ格納部に格納するスタックデータ圧縮部と、 前記実行保護タスク格納部を検索して、前記スタック使
   用可能タスク抽出部により抽出された第１の識別子と第
   ２の識別子との組合せにおける第１の識別子に対応する
   タスクが実行不可能状態となる場合に使用する最大のス
   タック容量を得、そのスタック容量よりも前記第１の識
   別子に対応するタスクが現在使用しているスタック容量
   が小さい第１の識別子と第２の識別子との組合せを抽出
   するスタック使用可能タスク選択部と、 前記スタック使用可能タスク選択部により抽出された第
   １の識別子と第２の識別子との組合せにおける第１の識
   別子に対応するタスクの実行状態を走行不可能状態に
   し、第２の識別子に対応するタスクの実行状態を走行状
   態にするタスク切り替え部と、 前記タスク情報格納部を検索して実行状態が走行待ち状
   態であるタスクの識別子を全て抽出し、前記スタックポ
   インタ格納部を検索して前記タスク情報格納部から抽出
   した識別子に対応するタスクのスタックポインタと実行
   状態とを抽出し、前記スタックポインタ格納部からスタ
   ックポインタと実行状態とを抽出したタスクが使用して
   いるスタック内のデータを展開し、前記スタックポイン
   タ格納部からスタックポインタと実行状態とを抽出した
   タスクの実行状態をスタックポインタ格納部から抽出し
   た実行状態に変更し、前記スタックポインタ格納部から
   スタックポインタと実行状態とを抽出したタスクのスタ
   ックポインタと実行状態とを前記スタックポインタ格納
   部から削除するスタックデータ展開部と、 を備えたことを特徴とするスケジューリング装置。