JPH09237193A - 並列計算機における動的負荷分散方法 - Google Patents

Abstract

(57)【要約】 【課題】 リアルタイムな並列計算機において、各プロ
セッサで発生した全てのタスクを定められたフレームタ
イム内で処理するような動的負荷分散を可能にする。 【解決手段】 システム内のあるプロセッサで新規タス
ク生成要求が発生した場合、該プロセッサ内で要求タス
クを処理可能であるかを先に判定し、処理不可能である
と判定したときに初めて他のプロセッサにタスク割当を
依頼するようなネットワーク内での動的負荷分散が行わ
れる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、リアルタイムな並
列計算機において、各プロセッサで発生した全てのタス
クを定められたフレームタイム内で処理することが可能
になるような動的負荷分散を行う方法に関するものであ
る。

【０００２】

【従来の技術】図２５は従来の並列計算機装置を示すも
ので、複数のプロセッサ１０２〜１ｍｎがネットワーク
１０１によって接続されている。システム内の全てのプ
ロセッサが効率良く稼働するために、逐次発生するタス
クをこれらのプロセッサに順次割り当てて分散処理を行
う。各プロセッサは割り当てられたタスクの処理時間か
ら負荷情報を生成する。

【０００３】従来、このような並列計算機装置では各プ
ロセッサは自身の負荷が重い状態で新たにタスクの生成
要求が生じた場合、他のプロセッサの負荷情報を調べる
ことによって最も負荷の軽いプロセッサを探して、該プ
ロセッサに対して該タスクの割当を依頼するか、あるい
は重い負荷のプロセッサが他のプロセッサを無作為に選
び、選んだ該プロセッサの負荷情報を調べて自分より負
荷が軽いかどうか判断し、相手プロセッサの方が負荷が
軽かった場合に、該プロセッサに対して該タスクの割当
を依頼する等して、全てのプロセッサの負荷を平均化し
てシステム全体の効率を上げようとしていた。

【０００４】

【発明が解決しようとする課題】上記のような従来の並
列計算機においては、負荷の重いプロセッサがタスク割
当を依頼するために最も負荷の軽いプロセッサを探すに
当たり、相手のプロセッサの負荷情報を逐次調べて行か
ねばならないので場合によっては多くの時間を要するこ
とになり、無作為に相手を選ぶ方法では選定したプロセ
ッサの負荷が自分の負荷より重く、そのために再度選定
を重ねるなどで多くの時間を要したり、また相手のプロ
セッサの負荷が自分より軽くても余り差が無く、該タス
クの割当に要した処理時間の方が多くて意味のない負荷
分散を行ったりする場合があり、結果として動的負荷分
散を行うための負荷が大きくなり、本来のアプリケーシ
ョンタスクの処理効率が低下してしまうという課題があ
った。

【０００５】本発明はかかる課題を解決するためになさ
れたものであり、各プロセッサが定められたフレームタ
イム内に割り当てられたタスクを処理しなければならな
いようなリアルタイムマルチプロセッサシステムにおい
て、システム内のあるプロセッサで新規生成要求タスク
が発生した場合に、該プロセッサ内で要求タスクを処理
可能であるかを先に判定し、処理不可能であると判明し
た場合にのみ該プロセッサはセンダとなり他のプロセッ
サにタスク割当を依頼すべく動的負荷分散を行う。これ
により、常時負荷分散を試みなくて良いので不必要にプ
ロセッサの負荷量が増加することを防ぐ。また、センダ
からタスク割当を依頼された各プロセッサ同士でレシー
バの決定を行うことにより、結果としてセンダのレシー
バ決定に要する負荷量を減らすことが出来る。以上によ
り、システム全体として動的負荷分散に要する負荷量を
減らし、処理効率の向上を目的としている。

【０００６】

【課題を解決するための手段】第１の発明によるリアル
タイムな並列計算機における動的負荷分散方法は、ある
プロセッサにタスク生成要求が生じたとき、該プロセッ
サでの実行可否判定を行う手段と、負荷判定の結果該タ
スクの処理実行が不可能であるとなった場合、該プロセ
ッサがセンダとなって自分の次のプロセッサ番号のプロ
セッサをレシーバ候補として選定する手段と、該レシー
バ候補に対して負荷情報の送信を１対１で要求する通信
手段と、受信した負荷情報を基にそのレシーバ候補がレ
シーバとしての資格があるかどうかを判定する手段と、
判定の結果が合格であったレシーバ有資格者が一定数に
達するまで、またはフレームタイム終了までにタスクの
処理や割当要求を行う時間的余裕がある限り新たなレシ
ーバ候補の選択および資格判定を繰り返す手段と、全レ
シーバ有資格者に対してレシーバ決定指令を出す手段
と、レシーバ有資格者が有資格者同士でお互いの負荷情
報を交換する手段と、全有資格者の負荷情報を基に各レ
シーバ有資格者が最も負荷の軽いレシーバ有資格者を一
つ決定する手段と、レシーバに決定したプロセッサがセ
ンダに決定報告を行う手段と、決定報告を受けたセンダ
がレシーバに該タスクの処理代行を依頼する手段を備え
ることにより達成される。

【０００７】また、第２の発明によるリアルタイムな並
列計算機における動的負荷分散方法は、あるプロセッサ
にタスク生成要求が生じたとき、該プロセッサでの実行
可否判定を行う手段と、各プロセッサが定期的に自分の
負荷情報を他のプロセッサへ放送する手段と、負荷判定
の結果該タスクの処理実行が不可能であるとなった場
合、該プロセッサがセンダとなって予め該放送手段によ
り取得している各プロセッサの負荷情報を基に各プロセ
ッサのレシーバとしての資格判定を行う手段と、判定の
結果が合格であったレシーバ有資格者全てに対してレシ
ーバ決定指令を出す手段と、レシーバ有資格者が有資格
者同士で該放送手段を用いてお互いの負荷情報を交換す
る手段と、全有資格者の情報を基に各レシーバ有資格者
が最も負荷の軽いレシーバ有資格者を一つ決定する手段
と、レシーバに決定したプロセッサがセンダに決定報告
を行う手段と、決定報告を受けたセンダがレシーバに該
タスクの処理代行を依頼する手段を備えることにより達
成される。

【０００８】また、第３の発明によるリアルタイムな並
列計算機における動的負荷分散方法は、あるプロセッサ
にタスク生成要求が生じたとき、該プロセッサでの実行
可否判定を行う手段と、各プロセッサが共有メモリに自
由にアクセスできる手段と、負荷判定の結果該タスクの
処理実行が不可能であるとなった場合、該プロセッサが
センダとなり、該共有メモリを読み込むことによって各
プロセッサの負荷情報を取得する手段と、各プロセッサ
の負荷情報を基に各プロセッサのレシーバとしての資格
判定を行う手段と、判定の結果が合格であったレシーバ
有資格者全てに対してレシーバ決定指令を出す手段と、
レシーバ有資格者が有資格者同士で該共有メモリを用い
てお互いの負荷情報を交換する手段と、全有資格者の情
報を基に各レシーバ有資格者が最も負荷の軽いレシーバ
有資格者を一つ決定する手段と、レシーバに決定したプ
ロセッサがセンダに決定報告を行う手段と、決定報告を
受けたセンダがレシーバに該タスクの処理代行を依頼す
る手段を備えることにより達成される。

【０００９】また、第４，５，６の発明によるリアルタ
イムな並列計算機における動的負荷分散方法は、レシー
バ決定後にレシーバがタスク生成要求を受諾できなかっ
た場合、レシーバがセンダにリジェクト信号を送信する
手段と、フレームタイム終了までにタスクの処理や割当
要求を行う時間的余裕がある場合にセンダが残ったレシ
ーバ有資格者に対して新たにレシーバ決定指令を出す手
段を備えることにより達成される。

【００１０】また、第７，８，９の発明によるリアルタ
イムな並列計算機における動的負荷分散方法は、レシー
バ決定の際に各レシーバ有資格者がレシーバ有資格者の
リストを作成する手段と、レシーバ決定後にレシーバが
タスク生成要求を受諾できなかった場合、フレームタイ
ム終了までにタスクの処理や割当要求を行う時間的余裕
がある限りレシーバが有資格者リストに登録されている
プロセッサの中から新たにレシーバを決定する手段を備
えることにより達成される。

【００１１】また、第１０，１１，１２の発明によるリ
アルタイムな並列計算機における動的負荷分散方法は、
レシーバ候補の資格判定時に判定結果が合格であるとな
った場合に、レシーバ候補が生成要求のあるタスクを生
成するのに必要なメモリやフレームタイム内での処理時
間等のリソースを予め確保する手段を備えることにより
達成される。

【００１２】

【発明の実施の形態】

実施の形態１．図１，２はこの発明の実施の形態１を示
す処理フロー図である。図１はあるプロセッサにタスク
生成要求が生じた場合の処理フロー図、図２はセンダに
レシーバ候補として選定され、レシーバ決定指示を送信
されたプロセッサの処理フロー図である。図１におい
て、あるプロセッサにおいてタスク生成要求が生じた場
合、該プロセッサはタスクスケジューリングの結果得ら
れるフレームタイム終了までのタスク割当のタイムスケ
ジュールやメモリ使用状況等の負荷情報と、該タスクの
所要メモリ量や所要処理時間等に関するタスク情報を基
に該タスクの実行可否判定１を行う。現在時刻からフレ
ームタイム終了時刻までの時間より該タスクの所要処理
時間の方が長かったり、現在時刻からフレームタイム終
了時刻までに既に他のタスクが割り当てられているため
該タスクの処理を行う余裕がない場合は実行不可能と判
定され、そうでなければ実行可能と判定される。実行可
能と判定された場合には該プロセッサにおいてタスク生
成２を行い、実行を開始する。実行不可能と判定された
場合には、該プロセッサはセンダとなり、センダは自分
の次のプロセッサ番号のプロセッサをレシーバ候補とし
て選択３し、該レシーバ候補に対して負荷情報を送信す
るように要求４する。図２（ａ）においてレシーバ候補
はセンダから負荷情報送信要求を受信すると、自身の現
在のタスクスケジュール状況から負荷計測５１を行い、
得られた負荷情報をセンダに返信５２する。

【００１３】図１において、センダは負荷情報を受信５
すると、該負荷情報と該タスクのタスク情報を基にレシ
ーバ候補が該タスクの処理代行の資格があるかどうかを
判定６する。現在時刻からフレームタイム終了時刻まで
に既に他のタスクが割り当てられているため該タスクの
処理を行う余裕がない場合は資格無しと判定され、そう
でなければ資格有りと判定される。判定の結果、資格有
りと判定されたレシーバ有資格者の数が一定数に達した
場合７は、各レシーバ有資格者に対してレシーバ決定指
示を送信８する。図２（ｂ）において、レシーバ決定指
示を受信した各レシーバ有資格者は、自分以外のレシー
バ有資格者の負荷情報を取得５３し、該負荷情報を基に
最も負荷の軽いレシーバ有資格者を１つレシーバとして
決定５４する。レシーバに決定したプロセッサ５５は、
その旨をセンダに報告５６する。図１において、センダ
はレシーバ決定報告を受信９すると、そのレシーバに対
してタスク割当要求１０を行い、動的負荷分散を終了す
る。有資格者数が一定数に達していないとき７は、フレ
ームタイム終了までにタスクの処理や割当要求を行う時
間的余裕がある場合１１はレシーバ候補の選択３から再
実行し、時間に余裕がない場合１１は有資格者数が一定
数に達していないときにおいてもその時点でレシーバ有
資格者が１つ以上あれば１２、レシーバ決定指示を送信
８する。レシーバ有資格者が１つもない場合は、該タス
クの生成要求をリジェクトする。

【００１４】実施の形態２．図３，４はこの発明の実施
の形態２を示す処理フロー図である。図３はあるプロセ
ッサにタスク生成要求が生じた場合の処理フロー図、図
４はセンダにレシーバ候補として選定され、レシーバ決
定指示を送信されたプロセッサの処理フロー図である。
図３において、あるプロセッサにおいてタスク生成要求
が生じた場合、該プロセッサはタスクスケジューリング
の結果得られるフレームタイム終了までのタスク割当の
タイムスケジュールやメモリ使用状況等の負荷情報と、
該タスクの所要メモリ量や所要処理時間等に関するタス
ク情報を基に該タスクの実行可否判定１を行う。現在時
刻からフレームタイム終了時刻までの時間より該タスク
の所要処理時間の方が長かったり、現在時刻からフレー
ムタイム終了時刻までに既に他のタスクが割り当てられ
ているため該タスクの処理を行う余裕がない場合は実行
不可能と判定され、そうでなければ実行可能と判定され
る。判定の結果、実行が可能である場合には該プロセッ
サにおいてタスク生成２を行い、実行を開始し、該タス
クの生成によって変動した自プロセッサの負荷情報を更
新１３する。

【００１５】図４（ａ）において、各プロセッサの負荷
情報は、他の全プロセッサに対して定期的に放送５７を
行う。図３において、該実行可否判定の結果、実行が不
可能である場合には、該プロセッサはセンダとなり、該
放送機能５７によって予め取得している負荷情報と該タ
スクのタスク情報を元に、各レシーバ候補に該タスクの
処理代行の資格があるかどうかを判定１４する。現在時
刻からフレームタイム終了時刻までに既に他のタスクが
割り当てられているため該タスクの処理を行う余裕がな
い場合は資格無しと判定され、そうでなければ資格有り
と判定される。判定の結果、資格有りと判定された有資
格者が一定数に達した場合７、各レシーバ有資格者に対
してレシーバ決定指示を送信８する。図４（ｂ）におい
て、レシーバ決定指示を受信した各レシーバ有資格者
は、自プロセッサの負荷情報を他の各レシーバ有資格者
へ放送５８することによって自分以外のレシーバ有資格
者の負荷情報を取得５３し、この情報を基に最も負荷の
軽いレシーバ有資格者を１つレシーバとして決定５４す
る。自分がレシーバに決定した場合５５は、その旨をセ
ンダに報告５６する。図３において、センダはレシーバ
決定報告を受信９すると、そのレシーバに対してタスク
割当要求１０を行い、動的負荷分散を終了する。有資格
者数が一定数に達していないとき７は、フレームタイム
終了までにタスクの処理や割当要求を行う時間的余裕が
ある場合１１はレシーバ候補の資格判定１４から再実行
し、時間に余裕がない場合１１は有資格者数が一定数に
達していないときにおいてもその時点でレシーバ有資格
者が１つ以上あれば１２、レシーバ決定指示を送信８す
る。レシーバ有資格者が１つもない場合は、該タスクの
生成要求をリジェクトする。

【００１６】実施の形態３．図５，６はこの発明の実施
の形態３を示す処理フロー図である。図５はあるプロセ
ッサにタスク生成要求が生じた場合の処理フロー図、図
６はセンダにレシーバ候補として選定され、レシーバ決
定指示を送信されたプロセッサの処理フロー図である。
図５において、あるプロセッサにおいてタスク生成要求
が生じた場合、該プロセッサはタスクスケジューリング
の結果得られるフレームタイム終了までのタスク割当の
タイムスケジュールやメモリ使用状況等の負荷情報と、
該タスクの所要メモリ量や所要処理時間等に関するタス
ク情報を基に該タスクの実行可否判定１を行う。現在時
刻からフレームタイム終了時刻までの時間より該タスク
の所要処理時間の方が長かったり、現在時刻からフレー
ムタイム終了時刻までに既に他のタスクが割り当てられ
ているため該タスクの処理を行う余裕がない場合は実行
不可能と判定され、そうでなければ実行可能と判定され
る。判定の結果、実行が可能である場合には該プロセッ
サにおいてタスク生成２を行い、実行を開始し、該タス
クの生成によって変動した自プロセッサの負荷情報を更
新１３する。

【００１７】図６（ａ）において、各プロセッサの負荷
情報は、全プロセッサからアクセス可能な共有メモリに
定期的に書き込む５９。図５において、該実行可否判定
の結果、実行が不可能である場合には、該プロセッサは
センダとなって該共有メモリに予め書かれている負荷情
報を読み込み１５、この情報と該タスクのタスク情報を
元に各レシーバ候補に該タスクの処理代行の資格がある
かどうかを判定６する。現在時刻からフレームタイム終
了時刻までに既に他のタスクが割り当てられているため
該タスクの処理を行う余裕がない場合は資格無しと判定
され、そうでなければ資格有りと判定される。判定の結
果、資格有りと判定されたレシーバ有資格者が一定数に
達した場合７、各レシーバ有資格者に対してレシーバ決
定指示を送信８する。図６（ｂ）において、レシーバ決
定指示を受信した各レシーバ有資格者は、自プロセッサ
の負荷情報を該共有メモリへ書き込み６０ことによって
自分以外のレシーバ有資格者の負荷情報を該共有メモリ
より取得６１し、この情報を基に最も負荷の軽いレシー
バ有資格者を１つレシーバとして決定５４する。自分が
レシーバに決定した場合５５は、その旨をセンダに報告
５６する。図５において、センダはレシーバ決定報告を
受信９すると、そのレシーバに対してタスク割当要求１
０を行い、動的負荷分散を終了する。有資格者数が一定
数に達していないとき７は、フレームタイム終了までに
タスクの処理や割当要求を行う時間的余裕がある場合１
１は負荷情報の読み込み１５から再実行し、時間に余裕
がない場合１１は有資格者数が一定数に達していないと
きにおいてもその時点でレシーバ有資格者が１つ以上あ
れば１２、レシーバ決定指示を送信８する。レシーバ有
資格者が１つもない場合は、該タスクの生成要求をリジ
ェクトする。

【００１８】実施の形態４．図７，８はこの発明の実施
の形態４を示す処理フロー図である。図７はあるプロセ
ッサにタスク生成要求が生じた場合の処理フロー図、図
８はセンダにレシーバ候補として選定され、レシーバ決
定指示を送信されたプロセッサの処理フロー図である。
図７において、あるプロセッサにおいてタスク生成要求
が生じた場合、該プロセッサはタスクスケジューリング
の結果得られるフレームタイム終了までのタスク割当の
タイムスケジュールやメモリ使用状況等の負荷情報と、
該タスクの所要メモリ量や所要処理時間等に関するタス
ク情報を基に該タスクの実行可否判定１を行う。現在時
刻からフレームタイム終了時刻までの時間より該タスク
の所要処理時間の方が長かったり、現在時刻からフレー
ムタイム終了時刻までに既に他のタスクが割り当てられ
ているため該タスクの処理を行う余裕がない場合は実行
不可能と判定され、そうでなければ実行可能と判定され
る。判定の結果、実行が可能である場合には該プロセッ
サにおいてタスク生成２を行い、実行を開始する。判定
の結果、実行が不可能である場合には、該プロセッサは
センダとなり、センダは自分の次のプロセッサ番号のプ
ロセッサをレシーバ候補として選択３し、該レシーバ候
補に対して負荷情報を送信するように要求４する。図８
（ａ）において、レシーバ候補はセンダから負荷情報送
信要求を受信すると、自身の現在のタスクスケジュール
状況から負荷計測５１を行い、得られた負荷情報をセン
ダに返信５２する。図７において、センダは負荷情報を
受信５すると、この情報と該タスクのタスク情報を元に
レシーバ候補が該タスクの処理代行の資格があるかどう
かを判定６する。現在時刻からフレームタイム終了時刻
までに既に他のタスクが割り当てられているため該タス
クの処理を行う余裕がない場合は資格無しと判定され、
そうでなければ資格有りと判定される。判定の結果、資
格有りと判定されたレシーバ有資格者の数が一定数に達
した場合７は、各レシーバ有資格者に対してレシーバ決
定指示を送信８する。

【００１９】図８（ｂ）においてレシーバ決定指示を受
信した各レシーバ有資格者は、自分以外のレシーバ有資
格者の負荷情報を取得５３し、該負荷情報を基に最も負
荷の軽いプロセッサを１つレシーバとして決定５４す
る。自分がレシーバに決定した場合５５は、その旨をセ
ンダに報告５６する。図７において、センダはレシーバ
決定報告を受信９すると、そのレシーバに対してタスク
割当要求１０を行う。図８（ｃ）において、タスク割当
要求を受信したレシーバは、自身の負荷情報と該タスク
のタスク情報を元にタスクの実行が可能であるか可否判
定６２を行い、可能であればタスク生成を実行６３し、
センダに対してアクセプト信号を送信６４し、該タスク
割当要求を受け入れた旨を報告する。ネットワークにお
いて遅延が発生した等の理由でレシーバがタスク割当要
求を受信するのが遅れたため、その間にレシーバが他の
プロセッサからの他のタスクの割当要求を受け付けてし
まった等の理由で実行不可能と判定された場合は、セン
ダに対してリジェクト信号を送信６５する。図７におい
て、センダはタスク割当要求１０を行った後、レシーバ
からの応答を待ち１６、アクセプト信号が返ってきたと
きは負荷分散を終了し、リジェクト信号が返ってきたと
きは、フレームタイム終了までにタスクの処理や割当要
求を行う時間的余裕がある場合１７には残ったレシーバ
有資格者に対してレシーバ決定指示を再送信８し、時間
に余裕がない場合１７は該タスクの生成要求をリジェク
トする。有資格者数が一定数に達していないとき７は、
時間に余裕がある場合１１はレシーバ候補の選択３から
再実行し、時間に余裕がない場合１１は有資格者数が一
定数に達していないときにおいてもその時点でレシーバ
有資格者が１つ以上あれば１２、レシーバ決定指示を送
信８する。レシーバ有資格者が１つもない場合は、該タ
スクの生成要求をリジェクトする。

【００２０】実施の形態５．図９，１０はこの発明の実
施の形態５を示す処理フロー図である。図９はあるプロ
セッサにタスク生成要求が生じた場合の処理フロー図、
図１０はセンダにレシーバ候補として選定され、レシー
バ決定指示を送信されたプロセッサの処理フロー図であ
る。図９において、あるプロセッサにおいてタスク生成
要求が生じた場合、該プロセッサはタスクスケジューリ
ングの結果得られるフレームタイム終了までのタスク割
当のタイムスケジュールやメモリ使用状況等の負荷情報
と、該タスクの所要メモリ量や所要処理時間等に関する
タスク情報を基に該タスクの実行可否判定１を行う。現
在時刻からフレームタイム終了時刻までの時間より該タ
スクの所要処理時間の方が長かったり、現在時刻からフ
レームタイム終了時刻までに既に他のタスクが割り当て
られているため該タスクの処理を行う余裕がない場合は
実行不可能と判定され、そうでなければ実行可能と判定
される。判定の結果、実行が可能である場合には該プロ
セッサにおいてタスク生成２を行い、実行を開始し、該
タスクの生成によって変動した自プロセッサの負荷情報
を更新１３する。

【００２１】図１０（ａ）において、各プロセッサの負
荷情報は、他の全プロセッサに対して定期的に放送５７
を行う。図９において、該実行可否判定の結果、実行が
不可能である場合には、該プロセッサはセンダとなり、
該放送機能５７によって予め取得している負荷情報と該
タスクのタスク情報を元に、各レシーバ候補に該タスク
の処理代行の資格があるかどうかを判定１４する。現在
時刻からフレームタイム終了時刻までに既に他のタスク
が割り当てられているため該タスクの処理を行う余裕が
ない場合は資格無しと判定され、そうでなければ資格有
りと判定される。判定の結果、資格有りと判定されたレ
シーバ有資格者が一定数に達した場合７は、各レシーバ
有資格者に対してレシーバ決定指示を送信８する。図１
０（ｂ）において、レシーバ決定指示を受信した各レシ
ーバ有資格者は、自プロセッサの負荷情報を他の各レシ
ーバ有資格者へ放送５８することによって自分以外のレ
シーバ有資格者の負荷情報を取得５３し、この情報を基
に最も負荷の軽い有資格者を１つレシーバとして決定５
４する。自分がレシーバに決定した場合５５は、その旨
をセンダに報告５６する。センダはレシーバ決定報告を
受信９すると、該レシーバに対してタスク割当要求１０
を行う。

【００２２】図１０（ｃ）において、タスク割当要求を
受信したレシーバは、自身の負荷情報と該タスクのタス
ク情報を元にタスクの実行が可能であるか可否判定６２
を行い、可能であればタスク生成を実行６３し、センダ
に対してアクセプト信号を送信６４し、該タスク割当要
求を受け入れた旨を報告する。ネットワークにおいて遅
延が発生した等の理由でレシーバがタスク割当要求を受
信するのが遅れたため、その間にレシーバが他のプロセ
ッサからの他のタスクの割当要求を受け付けてしまった
等の理由で実行不可能と判定された場合は、センダに対
してリジェクト信号を送信６５する。図９において、セ
ンダはタスク割当要求１０を行った後、レシーバからの
応答を待ち１６、アクセプト信号が返ってきたときは負
荷分散を終了し、リジェクト信号が返ってきたときは、
フレームタイム終了までにタスクの処理や割当要求を行
う時間的余裕がある場合１７には残ったレシーバ有資格
者に対してレシーバ決定指示を再送信８し、時間に余裕
がない場合１７には該タスクの生成要求をリジェクトす
る。有資格者数が一定数に達していないとき７は、時間
に余裕がある場合１１は各レシーバ候補の資格判定１４
から再実行し、時間に余裕がない場合１１は、有資格者
数が一定数に達していないときにおいてもその時点でレ
シーバ有資格者が１つ以上あれば１２、レシーバ決定指
示を送信８する。レシーバ有資格者が１つもない場合
は、該タスクの生成要求をリジェクトする。

【００２３】実施の形態６．図１１，１２はこの発明の
実施の形態６を示す処理フロー図である。図１１はある
プロセッサにタスク生成要求が生じた場合の処理フロー
図、図１２はセンダにレシーバ候補として選定され、レ
シーバ決定指示を送信されたプロセッサの処理フロー図
である。図１１において、あるプロセッサにおいてタス
ク生成要求が生じた場合、該プロセッサはタスクスケジ
ューリングの結果得られるフレームタイム終了までのタ
スク割当のタイムスケジュールやメモリ使用状況等の負
荷情報と、該タスクの所要メモリ量や所要処理時間等に
関するタスク情報を基に該タスクの実行可否判定１を行
う。現在時刻からフレームタイム終了時刻までの時間よ
り該タスクの所要処理時間の方が長かったり、現在時刻
からフレームタイム終了時刻までに既に他のタスクが割
り当てられているため該タスクの処理を行う余裕がない
場合は実行不可能と判定され、そうでなければ実行可能
と判定される。判定の結果、実行が可能である場合には
該プロセッサにおいてタスク生成２を行い、実行を開始
し、該タスクの生成によって変動した自プロセッサの負
荷情報を更新１３する。

【００２４】図１２（ａ）において、各プロセッサの負
荷情報は、全プロセッサからアクセス可能な共有メモリ
に定期的に書き込む５９。図１１において、該実行可否
判定の結果、実行が不可能である場合には、該プロセッ
サはセンダとなって該共有メモリに予め書かれている負
荷情報を読み込み１５、この情報と該タスクのタスク情
報を元に、各レシーバ候補に該タスクの処理代行の資格
があるかどうかを判定６する。判定の結果、資格有りと
判定されたレシーバ有資格者が一定数に達した場合７、
各レシーバ有資格者に対してレシーバ決定指示を送信８
する。図１２（ｂ）において、レシーバ決定指示を受信
した各レシーバ有資格者は、自プロセッサの負荷情報を
該共有メモリへ書き込む６０ことによって自分以外のレ
シーバ有資格者の負荷情報を該共有メモリより取得６１
し、この情報を基に最も負荷の軽い有資格者を１つレシ
ーバとして決定５４する。自分がレシーバに決定した場
合５５は、その旨をセンダに報告５６する。図１１にお
いて、センダはレシーバ決定報告を受信９すると、その
レシーバに対してタスク割当要求１０を行う。図１２
（ｃ）において、タスク割当要求を受信したレシーバ
は、自身の負荷情報と該タスクのタスク情報を元にタス
クの実行が可能であるか可否判定６２を行い、可能であ
ればタスク生成を実行６３し、センダに対してアクセプ
ト信号を送信６４し、該タスク割当要求を受け入れた旨
を報告する。ネットワークにおいて遅延が発生した等の
理由でレシーバがタスク割当要求を受信するのが遅れた
ため、その間にレシーバが他のプロセッサからの他のタ
スクの割当要求を受け付けてしまった等の理由で実行不
可能と判定された場合は、センダに対してリジェクト信
号を送信６５する。

【００２５】図１１においてセンダはタスク割当要求１
０を行った後、レシーバからの応答を待ち１６、アクセ
プト信号が返ってきたときは負荷分散を終了し、リジェ
クト信号が返ってきたときは、フレームタイム終了まで
にタスクの処理や割当要求を行う時間的余裕がある場合
１７には残ったレシーバ有資格者に対してレシーバ決定
指示を再送信８し、時間に余裕がない場合１７には該タ
スクの生成要求をリジェクトする。有資格者数が一定数
に達していないとき７は、時間に余裕がある場合１１は
共有メモリの負荷情報読み込み１５から再実行し、時間
に余裕がない場合１１は、有資格者数が一定数に達して
いなくてもその時点でレシーバ有資格者が１つ以上あれ
ば１２、レシーバ決定指示を送信８する。レシーバ有資
格者が１つもない場合は、該タスクの生成要求をリジェ
クトする。

【００２６】実施の形態７．図１３，１４はこの発明の
実施の形態７を示す処理フロー図である。図１３はある
プロセッサにタスク生成要求が生じた場合の処理フロー
図、図１４はセンダにレシーバ候補として選定され、レ
シーバ決定指示を送信されたプロセッサの処理フロー図
である。図１３において、あるプロセッサにおいてタス
ク生成要求が生じた場合、該プロセッサはタスクスケジ
ューリングの結果得られるフレームタイム終了までのタ
スク割当のタイムスケジュールやメモリ使用状況等の負
荷情報と、該タスクの所要メモリ量や所要処理時間等に
関するタスク情報を基に該タスクの実行可否判定１を行
う。現在時刻からフレームタイム終了時刻までの時間よ
り該タスクの所要処理時間の方が長かったり、現在時刻
からフレームタイム終了時刻までに既に他のタスクが割
り当てられているため該タスクの処理を行う余裕がない
場合は実行不可能と判定され、そうでなければ実行可能
と判定される。判定の結果、実行が可能である場合には
該プロセッサにおいてタスク生成２を行い、実行を開始
しする。判定の結果、実行が不可能である場合には、該
プロセッサはセンダとなり、センダは自分の次のプロセ
ッサ番号のプロセッサをレシーバ候補として選択３し、
該レシーバ候補に対して負荷情報を送信するように要求
４する。図１４（ａ）において、レシーバ候補はセンダ
から負荷情報送信要求を受信すると、自身の現在のタス
クスケジュール状況から負荷計測５１を行い、得られた
負荷情報をセンダに返信５２する。図１３において、セ
ンダは負荷情報を受信５すると、この情報と該タスクの
タスク情報を元にレシーバ候補が該タスクの処理代行の
資格があるかどうかを判定６する。現在時刻からフレー
ムタイム終了時刻までに既に他のタスクが割り当てられ
ているため該タスクの処理を行う余裕がない場合は資格
無しと判定され、そうでなければ資格有りと判定され
る。判定の結果、資格有りと判定されたレシーバ有資格
者の数が一定数に達した場合７は、各レシーバ有資格者
に対してレシーバ決定指示を送信８する。

【００２７】図１４（ｂ）において、レシーバ決定指示
を受信した各レシーバ有資格者は、自分以外のレシーバ
有資格者の負荷情報を取得５３し、この情報を基にレシ
ーバ有資格者のリストを作成６６し、同時に最も負荷の
軽い有資格者をレシーバとして１つ決定５４する。自分
がレシーバに決定した場合５５は、その旨をセンダに報
告５６する。図１３において、センダはレシーバ決定報
告を受信９すると、そのレシーバに対してタスク割当要
求１０を行う。図１４（ｃ）において、タスク割当要求
を受信したレシーバは、自身の負荷情報と該タスクのタ
スク情報を元にタスクの実行が可能であるか可否判定６
２を行い、可能であればタスク生成を実行６３し、セン
ダに対してアクセプト信号を送信６４し、該タスク割当
要求を受け入れた旨を報告する。ネットワークにおいて
遅延が発生した等の理由でレシーバがタスク割当要求を
受信するのが遅れたため、その間にレシーバが他のプロ
セッサからの他のタスクの割当要求を受け付けてしまっ
た等の理由で実行不可能と判定された場合は、フレーム
タイム終了までにタスクの処理や割当要求を行う時間的
余裕がある場合６７は該レシーバ有資格者リストを検索
６８し、有資格者がある場合６９は該リストの中からレ
シーバを１つ決定５４し、そのレシーバに対して新たに
タスク割当要求７０を行う。時間に余裕がない場合６７
や有資格者がない場合６９は、センダに対してリジェク
ト信号を送信６５する。

【００２８】図１３において、センダはタスク割当要求
１０を行った後、レシーバからの応答を待ち１６、アク
セプト信号が返ってきたときは負荷分散を終了し、リジ
ェクト信号が返ってきたときは該タスクの生成要求をリ
ジェクトする。有資格者数が一定数に達していないとき
７は、時間に余裕がある場合１１はレシーバ候補の選択
３から再実行し、時間に余裕がない場合１１は、有資格
者数が一定に達していないときにおいてもその時点でレ
シーバ有資格者が１つ以上あれば１２、レシーバ決定指
示を送信８する。レシーバ有資格者が１つもない場合
は、該タスクの生成要求をリジェクトする。

【００２９】実施の形態８．図１５，１６はこの発明の
実施の形態８を示す処理フロー図である。図１５はある
プロセッサにタスク生成要求が生じた場合の処理フロー
図、図１６はセンダにレシーバ候補として選定され、レ
シーバ決定指示を送信されたプロセッサの処理フロー図
である。図１５において、あるプロセッサにおいてタス
ク生成要求が生じた場合、該プロセッサはタスクスケジ
ューリングの結果得られるフレームタイム終了までのタ
スク割当のタイムスケジュールやメモリ使用状況等の負
荷情報と、該タスクの所要メモリ量や所要処理時間等に
関するタスク情報を基に該タスクの実行可否判定１を行
う。現在時刻からフレームタイム終了時刻までの時間よ
り該タスクの所要処理時間の方が長かったり、現在時刻
からフレームタイム終了時刻までに既に他のタスクが割
り当てられているため該タスクの処理を行う余裕がない
場合は実行不可能と判定され、そうでなければ実行可能
と判定される。判定の結果、実行が可能である場合には
自プロセッサにおいてタスク生成２を行い、実行を開始
し、該タスクの生成によって変動した自プロセッサの負
荷情報を更新１３する。

【００３０】図１６（ａ）において、各プロセッサの負
荷情報は、他の全プロセッサに対して定期的に放送５７
を行う。図１５において、該実行可否判定の結果、実行
が不可能である場合には、該プロセッサはセンダとな
り、該放送機構５７によって予め取得している負荷情報
と該タスクのタスク情報を元に、各レシーバ候補に該タ
スクの処理代行の資格があるかどうかを判定４する。現
在時刻からフレームタイム終了時刻までに既に他のタス
クが割り当てられているため該タスクの処理を行う余裕
がない場合は資格無しと判定され、そうでなければ資格
有りと判定される。判定の結果、資格有りと判定された
レシーバ有資格者が一定数に達した場合７は、各レシー
バ有資格者に対してレシーバ決定指示を送信８する。図
１６（ｂ）において、レシーバ決定指示を受信した各レ
シーバ有資格者は、自プロセッサの負荷情報を他の各レ
シーバ有資格者へ放送５８することによって自分以外の
レシーバ有資格者の負荷情報を取得５３し、この情報を
基にレシーバ有資格者のリストを作成６６し、同時に最
も負荷の軽い有資格者を１つレシーバとして決定５４す
る。自分がレシーバに決定した場合５５は、その旨をセ
ンダに報告５６する。図１５において、センダはレシー
バ決定報告を受信９すると、該レシーバに対してタスク
割当要求１０を行う。

【００３１】図１６（ｃ）において、タスク割当要求を
受信したレシーバは、自身の負荷情報と該タスクのタス
ク情報を元にタスクの実行が可能であるか可否判定６２
を行い、可能であればタスク生成を実行６３し、該タス
クの生成によって変動した自プロセッサの負荷情報を更
新７１し、センダに対してアクセプト信号を送信６４
し、該タスク割当要求を受け入れた旨を報告する。ネッ
トワークにおいて遅延が発生した等の理由でレシーバが
タスク割当要求を受信するのが遅れたため、その間にレ
シーバが他のプロセッサからの他のタスクの割当要求を
受け付けてしまった等の理由で実行不可能と判定された
場合は、フレームタイム終了までにタスクの処理や割当
要求を行う時間的余裕がある場合６７は該レシーバ有資
格者リストを検索６８し、有資格者がある場合６９は該
リストのうち既にレシーバとして決定されたものを除い
て最も負荷の軽い有資格者を１つレシーバとして決定５
４し、そのレシーバに対して新たにタスク割当要求７０
を行う。時間に余裕がない場合６７や有資格者がない場
合６９は、センダに対してリジェクト信号を送信６５す
る。図１５において、センダはタスク割当要求１０を行
った後、レシーバからの応答を待ち１６、アクセプト信
号が返ってきたときは負荷分散を終了し、リジェクト信
号が返ってきたときは該タスクの生成要求をリジェクト
する。有資格者数が一定数に達していないとき７は、時
間に余裕がある場合１１は各レシーバ候補の資格判定１
４から再実行し、時間に余裕がない場合１１は有資格者
数が一定数に達していないときにおいてもその時点でレ
シーバ有資格者が１つ以上あれば１２、レシーバ決定指
示を送信８する。レシーバ有資格者が１つもない場合
は、該タスクの生成要求をリジェクトする。

【００３２】実施の形態９．図１７，１８はこの発明の
実施の形態９を示す処理フロー図である。図１７はある
プロセッサにタスク生成要求が生じた場合の処理フロー
図、図１８はセンダにレシーバ候補として選定され、レ
シーバ決定指示を送信されたプロセッサの処理フロー図
である。図１７において、あるプロセッサにおいてタス
ク生成要求が生じた場合、該プロセッサはタスクスケジ
ューリングの結果得られるフレームタイム終了までのタ
スク割当のタイムスケジュールやメモリ使用状況等の負
荷情報と、該タスクの所要メモリ量や所要処理時間等に
関するタスク情報を基に該タスクの実行可否判定１を行
う。現在時刻からフレームタイム終了時刻までの時間よ
り該タスクの所要処理時間の方が長かったり、現在時刻
からフレームタイム終了時刻までに既に他のタスクが割
り当てられているため該タスクの処理を行う余裕がない
場合は実行不可能と判定され、そうでなければ実行可能
と判定される。判定の結果、実行が可能である場合には
自プロセッサにおいてタスク生成２を行い、実行を開始
し、該タスクの生成によって変動した自プロセッサの負
荷情報を更新１３する。

【００３３】図１８（ａ）において、各プロセッサの負
荷情報は、全プロセッサからアクセス可能な共有メモリ
に定期的に書き込む５９。図１７において、該実行可否
判定の結果、実行が不可能である場合には、該プロセッ
サはセンダとなって該共有メモリに予め書かれている負
荷情報を読み込み１５、この情報と該タスクのタスク情
報を元に、各レシーバ候補に該タスクの処理代行の資格
があるかどうかを判定６する。現在時刻からフレームタ
イム終了時刻までに既に他のタスクが割り当てられてい
るため該タスクの処理を行う余裕がない場合は資格無し
と判定され、そうでなければ資格有りと判定される。判
定の結果、資格有りと判定されたレシーバ有資格者が一
定数に達した場合７、各レシーバ有資格者に対してレシ
ーバ決定指示を送信８する。図１８（ｂ）において、レ
シーバ決定指示を受信した各レシーバ有資格者は、自プ
ロセッサの負荷情報を該共有メモリへ書き込む６０こと
によって自分以外のレシーバ有資格者の負荷情報を該共
有メモリより取得６１し、この情報を基にレシーバ有資
格者のリストを作成６６し、同時に最も負荷の軽い有資
格者を１つレシーバとして決定５４する。自分がレシー
バに決定した場合５５は、その旨をセンダに報告５６す
る。

【００３４】図１７において、センダはレシーバ決定報
告を受信９すると、該レシーバに対してタスク割当要求
１０を行う。図１８（ｃ）において、タスク割当要求を
受信したレシーバは、自身の負荷情報と該タスクのタス
ク情報を基にタスクの実行が可能であるか可否判定６２
を行い、可能であればタスク生成を実行６３し、該タス
クの生成によって変動した自プロセッサの負荷情報を更
新７１し、センダに対してアクセプト信号を送信６４
し、該タスク割当要求を受け入れた旨を報告する。ネッ
トワークにおいて遅延が発生した等の理由でレシーバが
タスク割当要求を受信するのが遅れたため、その間にレ
シーバが他のプロセッサからの他のタスクの割当要求を
受け付けてしまった等の理由で実行不可能と判定された
場合は、フレームタイム終了までにタスクの処理や割当
要求を行う時間的余裕がある場合６７は該レシーバ有資
格者リストを検索６８し、有資格者がある場合６９は該
リストのうち既にレシーバとして決定されたものを除い
て最も負荷の軽い有資格者を１つレシーバとして決定５
４し、そのレシーバに対して新たにタスク割当要求７０
を行う。時間に余裕がない場合６７や有資格者がない場
合６９は、センダに対してリジェクト信号を送信６５す
る。図１７において、センダはタスク割当要求１０を行
った後、レシーバからの応答を待ち１６、アクセプト信
号が返ってきたときは負荷分散を終了し、リジェクト信
号が返ってきたときは該タスクの生成要求をリジェクト
する。有資格者が一定数に達していないとき７は、時間
に余裕がある場合１１は共有メモリの負荷情報読み込み
１５から再実行し、時間に余裕がない場合１１は有資格
者が一定数に達していないときにおいてもその時点でレ
シーバ有資格者が１つ以上あれば１２、レシーバ決定指
示を送信８する。レシーバ有資格者が１つもない場合
は、該タスクの生成要求をリジェクトする。

【００３５】実施の形態１０．図１９，２０はこの発明
の実施の形態１０を示す処理フロー図である。図１９は
あるプロセッサにタスク生成要求が生じた場合の処理フ
ロー図、図２０はセンダにレシーバ候補として選定さ
れ、レシーバ決定指示を送信されたプロセッサの処理フ
ロー図である。図１９において、あるプロセッサにおい
てタスク生成要求が生じた場合、該プロセッサはタスク
スケジューリングの結果得られるフレームタイム終了ま
でのタスク割当のタイムスケジュールやメモリ使用状況
等の負荷情報と、該タスクの所要メモリ量や所要処理時
間等に関するタスク情報を基に該タスクの実行可否判定
１を行う。現在時刻からフレームタイム終了時刻までの
時間より該タスクの所要処理時間の方が長かったり、現
在時刻からフレームタイム終了時刻までに既に他のタス
クが割り当てられているため該タスクの処理を行う余裕
がない場合は実行不可能と判定され、そうでなければ実
行可能と判定される。判定の結果、実行が可能である場
合には自プロセッサにおいてタスク生成２を行い、実行
を開始する。判定の結果、実行が不可能である場合に
は、該プロセッサはセンダとなり、センダは自分の次の
プロセッサ番号のプロセッサをレシーバ候補として選択
３し、該レシーバ候補に対して負荷情報を送信するよう
に要求４する。図２０（ａ）において、レシーバ候補は
センダから負荷情報送信要求を受信すると、自身の現在
のタスクスケジュール状況から負荷計測５１を行い、得
られた負荷情報をセンダに返信５２する。図１９におい
て、センダは負荷情報を受信５すると、この情報と該タ
スクのタスク情報を元にレシーバ候補が該タスクの処理
代行の資格があるかどうかを判定６する。現在時刻から
フレームタイム終了時刻までに既に他のタスクが割り当
てられているため該タスクの処理を行う余裕がない場合
は資格無しと判定され、そうでなければ資格有りと判定
される。資格有りと判定された場合、該レシーバ候補に
対してタスクの生成・実行に必要なメモリやフレームタ
イム内での処理時間等のリソースを確保するよう指示１
８する。

【００３６】図２０（ｂ）において、該レシーバ候補は
リソース予約指示を受信すると、リソースの確保７２を
行い、タスク割当要求があったときに確実に該タスクが
実行できるようにする。図１９において、該資格判定６
の結果、資格有りと判定されたレシーバ有資格者の数が
一定数に達した場合７は、各レシーバ有資格者に対して
レシーバ決定指示を送信８する。図２０（ｃ）におい
て、レシーバ決定指示を受信した各レシーバ有資格者
は、自分以外のレシーバ有資格者の負荷情報を取得５３
し、この情報を基に最も負荷の軽い有資格者を１つレシ
ーバとして決定５４する。自分がレシーバに決定した場
合５５は、その旨をセンダに報告５６する。自分がレシ
ーバに選ばれなかった場合は、該リソース予約７２によ
って確保していたリソースの予約を解除７３し、不必要
にリソースを消費することを回避する。図１９におい
て、センダはレシーバ決定報告を受信９すると、そのレ
シーバに対してタスク割当要求１０を行う。該資格判定
６の結果、資格無しと判定された場合、または有資格者
数が一定数に達していない場合７は、フレームタイム終
了までにタスクの処理や割当要求を行う時間的余裕があ
るとき１１にはレシーバ候補の選択３から再実行し、時
間に余裕がないとき１１には、有資格者数が一定数に達
していないときにおいてもその時点でレシーバ有資格者
が１つ以上あれば１２、レシーバ決定指示を送信８す
る。レシーバ有資格者が１つもない場合は、該タスクの
生成要求をリジェクトする。

【００３７】実施の形態１１．図２１，２２はこの発明
の実施の形態１１を示す処理フロー図である。図２１は
あるプロセッサにタスク生成要求が生じた場合の処理フ
ロー図、図２２はセンダにレシーバ候補として選定さ
れ、レシーバ決定指示を送信されたプロセッサの処理フ
ロー図である。図２１において、あるプロセッサにおい
てタスク生成要求が生じた場合、該プロセッサはタスク
スケジューリングの結果得られるフレームタイム終了ま
でのタスク割当のタイムスケジュールやメモリ使用状況
等の負荷情報と、該タスクの所要メモリ量や所要処理時
間等に関するタスク情報を基に該タスクの実行可否判定
１を行う。現在時刻からフレームタイム終了時刻までの
時間より該タスクの所要処理時間の方が長かったり、現
在時刻からフレームタイム終了時刻までに既に他のタス
クが割り当てられているため該タスクの処理を行う余裕
がない場合は実行不可能と判定され、そうでなければ実
行可能と判定される。判定の結果、実行が可能である場
合には自プロセッサにおいてタスク生成２を行い、実行
を開始し、該タスクの生成によって変動した自プロセッ
サの負荷情報を更新１３する。

【００３８】図２２（ａ）において、各プロセッサの負
荷情報は、他の全てのプロセッサに対して定期的に放送
５７を行う。図２１において、該実行可否判定の結果、
実行が不可能である場合には、該プロセッサはセンダと
なり、該放送機能５７によって予め取得している負荷情
報と該タスクのタスク情報を元に、各レシーバ候補に該
タスクの処理代行の資格があるかどうかを判定１４す
る。現在時刻からフレームタイム終了時刻までに既に他
のタスクが割り当てられているため該タスクの処理を行
う余裕がない場合は資格無しと判定され、そうでなけれ
ば資格有りと判定される。資格有りと判定された場合、
該レシーバ候補に対してタスクの生成・実行に必要なメ
モリやフレームタイム内での処理時間等のリソースを確
保するよう指示１８する。図２２（ｂ）において、該レ
シーバ有資格者はリソース予約指示を受信すると、リソ
ースの確保７２を行い、タスク割当要求があったときに
確実に該タスクが実行できるようにする。図２１におい
て、該資格判定１４の結果、資格有りと判定されたレシ
ーバ有資格者の数が一定数に達した場合７は、各レシー
バ有資格者に対してレシーバ決定指示を送信８する。図
２２（ｃ）において、レシーバ決定指示を受信した各レ
シーバ有資格者は、自プロセッサの負荷情報を他の各レ
シーバ有資格者へ放送５８することによって自分以外の
レシーバ有資格者の負荷情報を取得５３し、この情報を
基に最も負荷の軽い有資格者を１つレシーバとして決定
５４する。自分がレシーバに決定した場合５５は、その
旨をセンダに報告５６する。自分がレシーバに選ばれな
かった場合は、該リソース予約７２によって確保してい
たリソースの予約を解除７３し、不必要にリソースを消
費することを回避する。

【００３９】図２１において、センダはレシーバ決定報
告を受信９すると、そのレシーバに対してタスク割当要
求１０を行う。該資格判定１４の結果、資格無しと判定
された場合、または有資格者数が一定数に達していない
場合７は、フレームタイム終了までにタスクの処理や割
当要求を行う時間的余裕があるとき１１には各レシーバ
候補の資格判定１４から再実行し、時間に余裕がないと
き１１には、有資格者数が一定数に達していないときに
おいてもその時点でレシーバ有資格者が１つ以上あれば
１２、レシーバ決定指示を送信８する。レシーバ有資格
者が１つもない場合は、該タスクの生成要求をリジェク
トする。

【００４０】実施の形態１２．図２３，２４はこの発明
の実施の形態１２を示す処理フロー図である。図２３は
あるプロセッサにタスク生成要求が生じた場合の処理フ
ロー図、図２４はセンダにレシーバ候補として選定さ
れ、レシーバ決定指示を送信されたプロセッサの処理フ
ロー図である。図２３において、あるプロセッサにおい
てタスク生成要求が生じた場合、該プロセッサはタスク
スケジューリングの結果得られるフレームタイム終了ま
でのタスク割当のタイムスケジュールやメモリ使用状況
等の負荷情報と、該タスクの所要メモリ量や所要処理時
間等に関するタスク情報を基に該タスクの実行可否判定
１を行う。現在時刻からフレームタイム終了時刻までの
時間より該タスクの所要処理時間の方が長かったり、現
在時刻からフレームタイム終了時刻までに既に他のタス
クが割り当てられているため該タスクの処理を行う余裕
がない場合は実行不可能と判定され、そうでなければ実
行可能と判定される。判定の結果、実行が可能である場
合には自プロセッサにおいてタスク生成２を行い、実行
を開始し、該タスクの生成によって変動した自プロセッ
サの負荷情報を更新１３する。

【００４１】図２４（ａ）において、各プロセッサの負
荷情報は、全プロセッサからアクセス可能な共有メモリ
に定期的に書き込む５９。図２３において、該実行可否
判定の結果、実行が不可能である場合には、該プロセッ
サはセンダとなって該共有メモリに予め書かれている負
荷情報を読み込み１５、この情報と該タスクのタスク情
報を元に、各レシーバ候補に該タスクの処理代行の資格
があるかどうかを判定６する。現在時刻からフレームタ
イム終了時刻までに既に他のタスクが割り当てられてい
るため該タスクの処理を行う余裕がない場合は資格無し
と判定され、そうでなければ資格有りと判定される。資
格有りと判定された場合、該レシーバ候補に対してタス
クの生成・実行に必要なメモリやフレームタイム内での
処理時間等のリソースを確保するよう指示１８する。

【００４２】図２４（ｂ）において、該レシーバ有資格
者はリソース予約指示を受信すると、リソースの確保７
２を行い、タスク割当要求があったときに確実に該タス
クが実行できるようにする。図２３において、該資格判
定６の結果、資格有りと判定されたレシーバ有資格者の
数が一定数に達した場合７は、各レシーバ有資格者に対
してレシーバ決定指示を送信８する。図２４（ｃ）にお
いて、レシーバ決定指示を受信した各レシーバ有資格者
は、自プロセッサの負荷情報を該共有メモリへ書き込む
６０ことによって自分以外のレシーバ有資格者の負荷情
報を該共有メモリより取得６１し、この情報を基に最も
負荷の軽い有資格者を１つレシーバとして決定５４す
る。自分がレシーバに決定した場合５５は、その旨をセ
ンダに報告５６する。自分がレシーバに選ばれなかった
場合は、該リソース予約７２によって確保していたリソ
ースの予約を解除７３し、不必要にリソースを消費する
ことを回避する。図２３において、センダはレシーバ決
定報告を受信９すると、そのレシーバに対してタスク割
当要求１０を行う。該資格判定６の結果、資格無しと判
定された場合、または有資格者数が一定数に達していな
い場合７は、フレームタイム終了までにタスクの処理や
割当要求を行う時間的余裕があるとき１１には共有メモ
リの負荷情報読み込み１５から再実行し、時間に余裕が
ないとき１１には有資格者数が一定数に達していないと
きにおいてもその時点でレシーバ有資格者が１つ以上あ
れば１２、レシーバ決定指示を送信８する。レシーバ有
資格者が１つもない場合は、該タスクの生成要求をリジ
ェクトする。

【００４３】

【発明の効果】以上のように本発明は、各プロセッサが
定められたフレームタイム内に割り当てられたタスクを
処理しなければならいようなリアルタイムマルチプロセ
ッサシステムにおいて、システム内のあるプロセッサで
新規生成要求タスクが発生した場合に、そのプロセッサ
内で要求タスクを処理可能であるかを先に判定し、処理
不可能であると判明したときに初めて他のプロセッサに
タスク割当を依頼すべく動的負荷分散を行うことによ
り、不必要にプロセッサの負荷量を増加することを防
ぎ、処理効率を向上することが可能となる。

【００４４】また、新規生成要求タスクが自プロセッサ
で処理不可能と判定され、他プロセッサへ処理代行を依
頼する場合、レシーバの決定をレシーバ有資格者同士で
行うことにより、負荷を軽減すべく動的負荷分散を行お
うとするセンダが、動的負荷分散処理のために負荷を高
めてしまうことを回避することが可能となる。

【図面の簡単な説明】

【図１】 本発明による動的負荷分散方法の実施の形態
１のセンダの処理を示すフロー図である。

【図２】 本発明による動的負荷分散方法の実施の形態
１のレシーバ候補の処理を示すフロー図である。

【図３】 本発明による動的負荷分散方法の実施の形態
２のセンダの処理を示すフロー図である。

【図４】 本発明による動的負荷分散方法の実施の形態
２のレシーバ候補の処理を示すフロー図である。

【図５】 本発明による動的負荷分散方法の実施の形態
３のセンダの処理を示すフロー図である。

【図６】 本発明による動的負荷分散方法の実施の形態
３のレシーバ候補の処理を示すフロー図である。

【図７】 本発明による動的負荷分散方法の実施の形態
４のセンダの処理を示すフロー図である。

【図８】 本発明による動的負荷分散方法の実施の形態
４のレシーバ候補の処理を示すフロー図である。

【図９】 本発明による動的負荷分散方法の実施の形態
５のセンダの処理を示すフロー図である。

【図１０】 本発明による動的負荷分散方法の実施の形
態５のレシーバ候補の処理を示すフロー図である。

【図１１】 本発明による動的負荷分散方法の実施の形
態６のセンダの処理を示すフロー図である。

【図１２】 本発明による動的負荷分散方法の実施の形
態６のレシーバ候補の処理を示すフロー図である。

【図１３】 本発明による動的負荷分散方法の実施の形
態７のセンダの処理を示すフロー図である。

【図１４】 本発明による動的負荷分散方法の実施の形
態７のレシーバ候補の処理を示すフロー図である。

【図１５】 本発明による動的負荷分散方法の実施の形
態８のセンダの処理を示すフロー図である。

【図１６】 本発明による動的負荷分散方法の実施の形
態８のレシーバ候補の処理を示すフロー図である。

【図１７】 本発明による動的負荷分散方法の実施の形
態９のセンダの処理を示すフロー図である。

【図１８】 本発明による動的負荷分散方法の実施の形
態９のレシーバ候補の処理を示すフロー図である。

【図１９】 本発明による動的負荷分散方法の実施の形
態１０のセンダの処理を示すフロー図である。

【図２０】 本発明による動的負荷分散方法の実施の形
態１０のレシーバ候補の処理を示すフロー図である。

【図２１】 本発明による動的負荷分散方法の実施の形
態１１のセンダの処理を示すフロー図である。

【図２２】 本発明による動的負荷分散方法の実施の形
態１１のレシーバ候補の処理を示すフロー図である。

【図２３】 本発明による動的負荷分散方法の実施の形
態１２のセンダの処理を示すフロー図である。

【図２４】 本発明による動的負荷分散方法の実施の形
態１２のレシーバ候補の処理を示すフロー図である。

【図２５】 従来の装置及び本発明にかかる並列計算機
装置のネットワークを示す概略図である。

【符号の説明】

１０１ ネットワーク、１０２ プロセッサ、１０３
プロセッサ、１ｍｎプロセッサ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 山崎 弘巳 東京都千代田区丸の内二丁目２番３号 三 菱電機株式会社内 (72)発明者 吉岡 英明 東京都千代田区丸の内二丁目２番３号 三 菱電機株式会社内 (72)発明者 高野 博行 東京都千代田区丸の内二丁目２番３号 三 菱電機株式会社内 (72)発明者 花澤 徹 東京都千代田区丸の内二丁目２番３号 三 菱電機株式会社内 (72)発明者 ▲高▼橋 正人 東京都千代田区丸の内二丁目２番３号 三 菱電機株式会社内

Claims (12)

【特許請求の範囲】
1. 【請求項１】 同等の機能を有する複数のプロセッサを
   持ち、各プロセッサ内のタスクは定められたフレームタ
   イム内で処理しなければならず、フレームタイムの開始
   時に該フレームタイムにおいて処理すべき仕事を判定
   し、該判定結果に基づいてタスクのスケジューリングを
   行うようなリアルタイムな並列計算機において、あるプ
   ロセッサにおける該タスクスケジューリングの結果、タ
   スク生成要求が生じたとき、該プロセッサは該タスクス
   ケジューリングの結果得られるフレームタイム終了まで
   のタスク割当のタイムスケジュールやメモリ使用状況等
   の負荷情報と、該タスクの所要メモリ量や所要処理時間
   等に関するタスク情報を基に該タスクの実行可否判定を
   行い、その結果現在時刻からフレームタイム終了時刻ま
   での時間より該タスクの所要処理時間の方が長かった
   り、現在時刻からフレームタイム終了時刻までに既に他
   のタスクが割り当てられている等の理由で該タスクの処
   理実行が不可能であるとなった場合、該プロセッサは該
   タスクのセンダとなり、他のプロセッサのうち該プロセ
   ッサの次のプロセッサ番号のプロセッサをレシーバ候補
   として選定し、該レシーバ候補に対してタスクスケジュ
   ーリングの結果得られた負荷情報の送信を要求し、受信
   した該レシーバ候補の負荷情報と該タスクのタスク情報
   を基に該レシーバ候補において該タスクの実行が可能で
   あるかどうか、すなわちレシーバとしての資格があるか
   どうかの判定を行い、判定の結果が合格であるレシーバ
   有資格者が一定数に達するまで、またはフレームタイム
   終了までにタスクの処理や割当要求を行う時間的余裕が
   ある限り新たなレシーバ候補の選択および資格判定を繰
   り返し、全レシーバ有資格者に対してレシーバ決定指令
   を出し、レシーバ有資格者は有資格者同士でお互いの負
   荷情報を交換して最も負荷の軽い有資格者をレシーバと
   して決定し、レシーバに決定したプロセッサはセンダに
   決定報告を行い、センダは決定報告を受けた後にレシー
   バに該タスクの処理代行を依頼することを特徴とする並
   列計算機における動的負荷分散方法。
2. 【請求項２】 各プロセッサが定期的に自分の負荷情報
   を他のプロセッサへ放送する機能を備えることにより、
   あるプロセッサにタスク生成要求が生じたとき、該プロ
   セッサは該タスクスケジューリングの結果得られるフレ
   ームタイム終了までのタスク割当のタイムスケジュール
   やメモリ使用状況等の負荷情報と、該タスクの所要メモ
   リ量や所要処理時間等に関するタスク情報を基に該タス
   クの実行可否判定を行い、その結果現在時刻からフレー
   ムタイム終了時刻までの時間より該タスクの所要処理時
   間の方が長かったり、現在時刻からフレームタイム終了
   時刻までに既に他のタスクが割り当てられている等の理
   由で該タスクの処理実行が不可能であるとなった場合、
   該プロセッサは該タスクのセンダとなり、予め該放送機
   能により取得している各プロセッサの負荷情報と該タス
   クのタスク情報を基に各プロセッサにおいて該タスクの
   実行が可能かどうか、すなわちレシーバとしての資格が
   あるかどうかの判定を行い、判定の結果が合格であるレ
   シーバ有資格者全てに対してレシーバ決定指令を出し、
   レシーバ有資格者は有資格者同士で該放送機能を用いて
   お互いの負荷情報を交換して最も負荷の軽い有資格者を
   レシーバとして決定し、レシーバに決定したプロセッサ
   はセンダに決定報告を行い、センダは決定報告を受けた
   後にレシーバに該タスクの処理代行を依頼することを特
   徴とする請求項１記載の並列計算機における動的負荷分
   散方法。
3. 【請求項３】 各プロセッサが自由にアクセスできる共
   有メモリ機能を備えることにより、あるプロセッサにタ
   スク生成要求が生じたとき、該プロセッサは該タスクス
   ケジューリングの結果得られるフレームタイム終了まで
   のタスク割当のタイムスケジュールやメモリ使用状況等
   の負荷情報と、該タスクの所要メモリ量や所要処理時間
   等に関するタスク情報を基に該タスクの実行可否判定を
   行い、その結果現在時刻からフレームタイム終了時刻ま
   での時間より該タスクの所要処理時間の方が長かった
   り、現在時刻からフレームタイム終了時刻までに既に他
   のタスクが割り当てられている等の理由で該タスクの処
   理実行が不可能であるとなった場合、該プロセッサはセ
   ンダとなり、該共有メモリを読み込むことによって各プ
   ロセッサの負荷情報を取得し、該負荷情報と該タスクの
   タスク情報を基に各プロセッサにおいて該タスクの実行
   が可能かどうか、すなわちレシーバとしての資格がある
   かどうかの判定を行い、判定の結果が合格であるレシー
   バ有資格者全てに対してレシーバ決定指令を出し、レシ
   ーバ有資格者は有資格者同士で該共有メモリを用いてお
   互いの負荷情報を交換して最も負荷の軽い有資格者をレ
   シーバとして決定し、レシーバに決定したプロセッサは
   センダに決定報告を行い、センダは決定報告を受けた後
   にレシーバに該タスクの処理代行を依頼することを特徴
   とする請求項１記載の並列計算機における動的負荷分散
   方法。
4. 【請求項４】 レシーバ決定後にタスク割当要求をレシ
   ーバに送信した際に、ネットワークにおいて遅延が発生
   した等の理由でレシーバがタスク割当要求を受信するの
   が遅れたため、その間にレシーバが他のプロセッサから
   他のタスクの割当要求を受け付けてしまった等の理由
   で、レシーバが該タスク生成要求を受諾できなくなって
   しまった場合、レシーバがセンダにリジェクト信号を送
   信し、センダはフレームタイム終了までにタスクの処理
   や割当要求を行う時間的余裕がある限り、残ったレシー
   バ有資格者に対して新たにレシーバ決定指令を出すよう
   にしたことを特徴とする請求項１記載の並列計算機にお
   ける動的負荷分散方法。
5. 【請求項５】 レシーバ決定後にタスク割当要求をレシ
   ーバに送信した際に、ネットワークにおいて遅延が発生
   した等の理由でレシーバがタスク割当要求を受信するの
   が遅れたため、その間にレシーバが他のプロセッサから
   他のタスクの割当要求を受け付けてしまった等の理由
   で、レシーバが該タスク生成要求を受諾できなくなって
   しまった場合、レシーバがセンダにリジェクト信号を送
   信し、センダはフレームタイム終了までにタスクの処理
   や割当要求を行う時間的余裕がある限り、残ったレシー
   バ有資格者に対して新たにレシーバ決定指令を出すよう
   にしたことを特徴とする請求項２記載の並列計算機にお
   ける動的負荷分散方法。
6. 【請求項６】 レシーバ決定後にタスク割当要求をレシ
   ーバに送信した際に、ネットワークにおいて遅延が発生
   した等の理由でレシーバがタスク割当要求を受信するの
   が遅れたため、その間にレシーバが他のプロセッサから
   他のタスクの割当要求を受け付けてしまった等の理由
   で、レシーバが該タスク生成要求を受諾できなくなって
   しまった場合、レシーバがセンダにリジェクト信号を送
   信し、センダはフレームタイム終了までにタスクの処理
   や割当要求を行う時間的余裕がある限り、残ったレシー
   バ有資格者に対して新たにレシーバ決定指令を出すよう
   にしたことを特徴とする請求項３記載の並列計算機にお
   ける動的負荷分散方法。
7. 【請求項７】 レシーバ決定の際に各レシーバ有資格者
   がレシーバ有資格者のリストを作成しておくことによ
   り、レシーバ決定後にタスク割当要求をレシーバに送信
   した際に、ネットワークにおいて遅延が発生した等の理
   由でレシーバがタスク割当要求を受信するのが遅れたた
   め、その間にレシーバが他のプロセッサから他のタスク
   の割当要求を受け付けてしまった等の理由で、レシーバ
   が該タスク生成要求を受諾できなくなってしまった場
   合、フレームタイム終了までにタスクの処理や割当要求
   を行う時間的余裕がある限りレシーバが有資格者リスト
   に登録されているプロセッサの中から新たにレシーバを
   決定し、タスク処理代行依頼をすることを特徴とする請
   求項１記載の並列計算機における動的負荷分散方法。
8. 【請求項８】 レシーバ決定の際に各レシーバ有資格者
   がレシーバ有資格者のリストを作成しておくことによ
   り、レシーバ決定後にタスク割当要求をレシーバに送信
   した際に、ネットワークにおいて遅延が発生した等の理
   由でレシーバがタスク割当要求を受信するのが遅れたた
   め、その間にレシーバが他のプロセッサから他のタスク
   の割当要求を受け付けてしまった等の理由で、レシーバ
   が該タスク生成要求を受諾できなくなってしまった場
   合、フレームタイム終了までにタスクの処理や割当要求
   を行う時間的余裕がある限りレシーバが有資格者リスト
   に登録されているプロセッサの中から新たにレシーバを
   決定し、タスク処理代行依頼をすることを特徴とする請
   求項２記載の並列計算機における動的負荷分散方法。
9. 【請求項９】 レシーバ決定の際に各レシーバ有資格者
   がレシーバ有資格者のリストを作成しておくことによ
   り、レシーバ決定後にタスク割当要求をレシーバに送信
   した際に、ネットワークにおいて遅延が発生した等の理
   由でレシーバがタスク割当要求を受信するのが遅れたた
   め、その間にレシーバが他のプロセッサから他のタスク
   の割当要求を受け付けてしまった等の理由で、レシーバ
   が該タスク生成要求を受諾できなくなってしまった場
   合、フレームタイム終了までにタスクの処理や割当要求
   を行う時間的余裕がある限りレシーバが有資格者リスト
   に登録されているプロセッサの中から新たにレシーバを
   決定し、タスク処理代行依頼をすることを特徴とする請
   求項３記載の並列計算機における動的負荷分散方法。
10. 【請求項１０】 レシーバ候補の資格判定時に判定結果
    が合格であるとなった場合に、レシーバ候補に対して生
    成要求のあるタスクを生成するのに必要なメモリやフレ
    ームタイム内での処理時間等のリソースを予め確保する
    ように指示しておくことによって、実際に生成要求を受
    信した際に確実に該タスクの生成・実行を可能にするこ
    とを特徴とする請求項１記載の並列計算機における動的
    負荷分散方法。
11. 【請求項１１】 レシーバ候補の資格判定時に判定結果
    が合格であるとなった場合に、レシーバ候補に対して生
    成要求のあるタスクを生成するのに必要なメモリやフレ
    ームタイム内での処理時間等のリソースを予め確保する
    ように指示しておくことによって、実際に生成要求を受
    信した際に確実に該タスクの生成・実行を可能にするこ
    とを特徴とする請求項２記載の並列計算機における動的
    負荷分散方法。
12. 【請求項１２】 レシーバ候補の資格判定時に判定結果
    が合格であるとなった場合に、レシーバ候補に対して生
    成要求のあるタスクを生成するのに必要なメモリやフレ
    ームタイム内での処理時間等のリソースを予め確保する
    ように指示しておくことによって、実際に生成要求を受
    信した際に確実に該タスクの生成・実行を可能にするこ
    とを特徴とする請求項３記載の並列計算機における動的
    負荷分散方法。