(57)【特許請求の範囲】
【請求項１】
複数の計算機上で複数のプログラムが動作する分散処理システムにおいて、各計算機は、該計算機の性能と負荷に応じて、処理の緊急度と優先順位との変換を行う優先順位変換手段と、
該優先順位変換手段が示す優先順位にしたがって、処理を実行するプログラムの優先順位を変更する優先順位変更手段とを有し、
該複数のプログラムは、別プログラムに対して処理を依頼する際に、処理の緊急度を指定することを特徴とする分散処理システム。
【請求項２】
複数の計算機上で複数のプログラムが動作する分散処理システムにおいて、各計算機は、該計算機の性能と負荷に応じて、処理の時間制約，処理量と優先順位との変換を行う優先順位変換手段と、
該優先順位変換手段が示す優先順位にしたがって、処理を実行するプログラムの優先順位を変更する優先順位変更手段とを有し、
該複数のプログラムは、別プログラムに対して処理を依頼する際に、処理の時間制約を指定することを特徴とする分散処理システム。
【請求項３】
複数の計算機上で複数のプログラムが動作する分散処理システムにおいて、各計算機は、該計算機の性能と負荷に応じて、処理の時間制約，処理量と優先順位との変換を行う優先順位変換手段と、
該優先順位変換手段が示す優先順位にしたがって、処理を実行するプログラムの優先順位を変更する優先順位変更手段と、
他計算機との通信時間を予測する通信時間予測手段とを有し、
該複数のプログラムは、別プログラムに対して処理を依頼する際に、該別プログラムの動作する計算機との通信予測時間を該通信予測手段から入力し、該通信予測時間を考慮して、処理の時間制約を指定することを特徴とする分散処理システム。
【請求項４】
複数の計算機上で複数のプログラムが動作する分散処理システムにおいて、計算機の性能，負荷，処理量に応じて、該複数のプログラムが実行中の処理の処理時間を予測する処理時間予測手段と、
該処理時間予測手段が示す予測処理時間が該処理に要求される時間制約を満足しない際に、該処理が要求された時点からの経過時間と該要求される時間制約から新たに時間制約を設定する時間制約設定手段と、
該新たな時間制約，処理量と各計算機上での優先順位との変換を行う優先順位変換手段と、
該優先順位変換手段が示す優先順位にしたがって、処理を実行するプログラムの優先順位を変更する優先順位変更手段を有する分散処理システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、複数の計算機がネットワークに接続され、複数のプログラムを協調して実行する分散処理システムに関連し、特に、優先順位を用いてリアルタイム性を実現する分散処理システムの構成および方式に関する。
【０００２】
【従来の技術】
単一計算機（マルチプロセッサ型計算機を含む）からのみ構成される計算機システムにおいて、リアルタイム性を保証する場合、従来から、優先順位を用いて順序制御を行う方法がある。このような優先順位制御の一例として、プレンティス・ホール社(Prentice-Hall, Inc.）刊行のＡ．Ｓ．タンネンバウム著「オペレーティングシステムズ・デザイン・アンド・インプリメンテーション」,１９８７年，８２〜８４頁（A.S.Tanenbaum：Operating Systems - Design and         Implementation, 1987, pp.82−84）がある。
【０００３】
さらに、例えば、特開平2−113362 号公報に記載されている方式は、分散処理システムの各処理ノード間でメッセージ通信を行う際に、該メッセージに優先度を付随させ、優先度の高いメッセージから順に処理を行うものである（以降、この方式を従来技術１と呼ぶ）。
【０００４】
また、別の従来の方式として、例えば、特開平5−35701号公報に記載されている方式がある。この方式は、複数の処理装置を有した分散処理システムで処理要求を行う際に、処理待ち許容時間を指定し、各処理装置での予定処理待ち時間を調べ、予定処理待ち時間が処理待ち許容時間より短い処理装置に該処理要求を割り当てるものがある。処理待ち許容時間を満たす処理装置がなければ、最も短い予定処理待ち時間となる処理装置に該処理要求を割り当てる。各処理装置に割り当てられた処理要求は基本的に古いものから順に処理される（以降、この方式を従来技術２と呼ぶ）。
【０００５】
またさらに、例えば、特開平5−35701号公報に記載されるように、処理要求発行の際に、処理待ち許容時間と同時に前記従来技術１と同様の優先順位も付加し、処理要求の割当て後に、割り当てられた処理装置で該優先順位の順に処理を実行させる方法（以降、これを従来技術３と呼ぶ）もある。
【０００６】
【発明が解決しようとする課題】
複数の計算機が各々個別のオペレーティングシステムによって管理される分散処理システムにおいては、各々の計算機で個別にプログラムの優先順位が管理される。このため、分散処理システム全体に渡る優先順位の統一的な管理を行えず、性能，負荷の異なる計算機を有する分散処理システムにおいては、ある計算機の優先順位が意味する緊急性と別の計算機の優先順位が表わす緊急性とが異なる場合がある。例えば、性能の高い計算機と性能の低い計算機とでは、同じ優先順位０であっても、高性能計算機で実行した方が速く終了する。同様に、負荷の重い計算機と負荷の軽い計算機との間でも、優先順位の示す意味が異なってくる。また、複数の異なった種類の計算機を有する分散処理システムでは、各々の計算機の優先順位体系自体が異なる場合がある。例えば、優先順位の範囲が０〜255である計算機と優先順位の範囲が０〜１２７である計算機とは、優先順位の値に互換性がない。同様に、優先順位０を最高優先順位と見なす計算機と優先順位
２５５を最高優先順位と見なす計算機との間で、同一の優先順位を使用することはできない。
【０００７】
前記従来技術１は、このような分散処理システムにおける個々の計算機の性能，負荷および機種の違いを考慮せず、単に優先度を付随してメッセージを送信する方法である。このため、メッセージ送信先計算機の性能が低い、若しくは、負荷が重いような条件では、望ましい速さで処理を実行して貰えない可能性があり、リアルタイム性を保証できないことがある。
【０００８】
さらに、前記従来技術１では、複数の計算機で処理が行われる際に、優先順位の低い処理依頼が優先順位の高い処理依頼よりも速く完了するという逆転現象が起こり得る。例えば、処理Ａを優先度５で計算機Ａに依頼し、処理Ｂを優先度１で計算機Ｂに依頼するとする（優先度の値が小さい方が高い優先順位を表わすものとする）。このとき、本来ならば、処理Ｂが処理Ａより速く完了していなければならないが、計算機Ｂの性能が計算機Ａに比べて低い、または、計算機Ｂの負荷が重い場合には、優先順位の低い処理Ａが優先順位の高い処理Ｂよりも速く完了してしまう可能性がある。
【０００９】
さらにまた、前記従来技術１では、一つの計算機に処理が集中すること、特に、一つの計算機に優先度の高い処理が集中することを考慮していないため、これらの優先度の高い処理が集中した計算機では、リアルタイム性保証がさらに困難となるという課題がある。
【００１０】
前記従来技術２は、各処理装置での予定処理待ち時間を正確に計算できれば、個々の処理要求に関してはある程度のリアルタイム性保証に使用することが可能である。しかし、この方式では、既に各処理装置にある程度の数の処理要求が割り当てられている場合に、新たに発生した処理待ち許容時間の短い処理要求の時間制約条件を満たせないことがある。例えば、処理待ち許容時間の長い処理要求が既に処理装置に割り当てられており、かつ、これらに先んじて新たに発生した処理要求を処理することができれば全ての処理要求の時間制約条件を満たすことができる場合にも、順に処理要求を割り当てていくため、新たに発生した処理要求の時間制約条件を満たせないことがある。すなわち、負荷がある程度高い状況で発生した緊急性の高い処理要求を直ちに処理することができず、厳密なリアルタイム性を保証することができないという問題点がある。
【００１１】
さらにまた、前記従来技術３は、（１）各処理装置への処理要求割り当ては、処理待ち許容時間を充足する処理装置を選択し、（２）各処理装置での処理要求の実行順序は指定した優先順位の示す順に実行する、という方式である。従来技術３によれば、新たに発生した処理待ち許容時間の短い処理要求に対して、高い優先順位を設定することにより、上記従来技術２の欠点をある程度解決することができる。しかし、この方式では、新たに割り当てられた高い優先順位の処理要求を優先して処理するため、既に処理待ち許容時間を満たすと判断されて、割り当てられている低い優先順位を有する処理要求の処理待ち許容時間が満たされなくなることがあるという課題がある。例えば、処理待ち許容時間１分，優先順位５の処理要求Ａが、処理待ち許容時間を満たすことができると判断されて、処理装置Ａに割り付けられている状況で、新たに、処理待ち許容時間３０秒，優先順位１の処理要求Ｂが処理装置Ａに割り付けられたとする。このとき、新たな処理要求Ｂが先に処理されることになる。これによって、既に割り付けられ、処理待ち許容時間を満たすことが保証されていた筈の処理要求Ａがこの時間制約条件を満たせないことが起こり得る。
【００１２】
さらに、前記従来技術３では、従来技術１と同様に、同一処理待ち許容時間で優先順位の異なる処理要求を複数の処理装置に割り当てた場合、該処理装置の負荷，性能の違いによって、優先順位の低い処理依頼が優先順位の高い処理依頼よりも速く完了するという逆転現象が起こり得るという課題がある。
【００１３】
本発明の目的は、これら上記のリアルタイム性保証に関する課題を解決し、分散処理システムにおける、より厳密なリアルタイム性を実現することである。特に、性能，負荷および機種の異なる計算機を含み得る分散処理システムにおいて、各々の計算機の優先順位を統一的に管理することによって、さらに厳密なリアルタイム性を実現することである。
【００１４】
【課題を解決するための手段】
本発明では、分散処理システムの個々の計算機の優先順位を統一的に管理する概念として、次の二つの概念のうち、いずれか一方を用いる。
【００１５】
・処理の緊急度：処理をどの程度の迅速さで完了させたいかを示すシステム全体で共通の相対値
・処理の時間制約：処理をどの程度の時間で完了させたいかを示す絶対値
これら各々の概念を用いて分散処理システムの個々の計算機の優先順位を統一的に管理するため手段を、以下、処理の緊急度を使用する場合と処理の時間制約を使用する場合とに分けて説明する。
【００１６】
（Ａ）処理の緊急度を用いて管理するための手段
本発明では、上記目的を達成するために、各計算機の性能，負荷の少なくとも一方と、プログラムが実行する処理の緊急度とを考慮して、プログラムの実行に適した優先順位を決定する優先順位決定手段を設けることを特徴とする。
【００１７】
具体的には、該優先順位決定手段はその構成要素として以下の五つの手段を有し、これらの手段が協調して動作することにより、処理の緊急度を使用して、上記目的を達成する分散処理システム管理を行うことができる。なお、下記五つの全ての手段を同時に設ける必要はない。
【００１８】
（１）計算機の性能と負荷に応じて、処理の緊急度と優先順位との変換を行う優先順位変換手段
（２）優先順位変換手段の示す優先順位にしたがって、処理を実行するプログラムの優先順位を変更する優先順位変更手段
（３）各計算機の性能，負荷の少なくとも一方と、プログラムが実行する処理の緊急度とを考慮して、プログラムの実行に適した計算機を決定する計算機選択手段
（４）複数の同一処理を行うプログラムが存在し、かつ、該プログラムに処理を依頼する際に、各計算機の性能，負荷の少なくとも一方と、処理の緊急度とを考慮して、該複数の同一処理を行うプログラムの中から最適な優先順位を有するプログラムを決定するプログラム選択手段
（５）プログラム選択手段が示すプログラムに対して新たに依頼された処理を転送する処理転送手段
（Ｂ）処理の時間制約を用いて管理するための手段
本発明では、上記目的を達成するために、各計算機の性能，負荷の少なくとも一方と、プログラムが実行する処理の時間制約，処理量とを考慮して、プログラムの実行に適した優先順位を決定する優先順位決定手段を設けることを特徴とする。
【００１９】
具体的には、該優先順位決定手段はその構成要素として以下の八つの手段を有し、これらの手段が協調して動作することにより、処理の時間制約を使用して、上記目的を達成する分散処理システム管理を行うことができる。なお、下記八つの全ての手段を同時に設ける必要はない。
【００２０】
（１）計算機の性能と負荷に応じて、処理の時間制約，処理量と優先順位との変換を行う優先順位変換手段
（２）優先順位変換手段の示す優先順位にしたがって、処理を実行するプログラムの優先順位を変更する優先順位変更手段
（３）他計算機との通信時間を予測する通信時間予測手段
（４）各計算機の性能，負荷の少なくとも一方と、プログラムが実行する処理の時間制約，処理量とを考慮して、プログラムの実行に適した計算機を決定する計算機選択手段
（５）複数の同一処理を行うプログラムが存在し、かつ、該プログラムに処理を依頼する際に、各計算機の性能，負荷の少なくとも一方と、処理の時間制約，処理量とを考慮して、該複数の同一処理を行うプログラムの中から最適な優先順位を有するプログラムを決定するプログラム選択手段
（６）プログラム選択手段が示すプログラムに対して新たに依頼された処理を転送する処理転送手段
（７）計算機の性能，負荷，処理量に応じて、該プログラムが実行中の処理の処理時間を予測する処理時間予測手段
（８）処理時間予測手段が示す予測処理時間が該処理に要求される時間制約を満足しない際に、該処理が要求された時点からの経過時間と該要求される時間制約から新たに時間制約を設定する時間制約設定手段
【００２１】
【作用】
前記課題を解決するための手段が有する作用について、処理の緊急度を使用する場合と処理の時間制約を使用する場合とに分けて説明する。
【００２２】
（Ａ）処理の緊急度を用いて管理する場合
優先順位決定手段は、各計算機の性能，負荷の少なくとも一方と、プログラムが実行する処理の緊急度とを考慮して、プログラムの実行に適した優先順位を決定する。これにより、同一緊急度を有した処理を複数の計算機で実行する場合に、高性能計算機では低い優先順位を、低性能計算機では高い優先順位を与え、各計算機の性能の違いにかかわらず、同程度の迅速さで処理を完了させることができる。同様に、高負荷計算機では高い優先順位を、低負荷計算機では低い優先順位を与え、各計算機の負荷の違いにかかわらず、同程度の迅速さで処理を完了させることができる。また、各計算機の性能と負荷を考慮して、処理の緊急度から個々の計算機での優先順位を決定するため、低い緊急度の処理が高い緊急度の処理に先んじて完了するという逆転現象を避けることも可能となる。すなわち、従来技術に比べて、より厳密なリアルタイム性を保証することが可能となる。優先順位決定手段の構成要素である五つの手段は以下の作用を有する。
【００２３】
優先順位変換手段は、処理の緊急度と優先順位との対応を示す優先順位対応表を有し、該優先順位対応表を用いることにより、処理の緊急度と優先順位との変換を行う。優先順位対応表の内容は計算機の性能，負荷および機種に応じて変更させる。
【００２４】
優先順位変更手段は、優先順位変換手段によって示された優先順位にしたがって、プログラムの優先順位を変更させる。優先順位変換手段と優先順位変更手段によって、同一緊急度を有する処理が性能，負荷の異なるいずれの計算機においても同程度の迅速さで実行されることを保証できるようになる。
【００２５】
計算機選択手段は、計算機性能情報と計算機負荷情報とからなる計算機情報を参照し、指定された処理の緊急度の負荷が均等に分散されるように計算機を選択し、プログラムを実行させる。計算機性能情報は各計算機の性能を示したテーブル，計算機負荷情報は各計算機の負荷を処理の緊急度毎に示したテーブルであり、計算機上の負荷が変化した場合、該変化量を計算機負荷情報に反映させる。これにより、緊急度の高い処理が一つの計算機に集中するといった現象がなくなり、各計算機におけるリアルタイム性保証をより厳密に行うことが可能となる。
【００２６】
プログラム選択手段は、同一処理を行うプログラムの情報を纏めたプログラム位置データベースを用い、複数の同一処理を行うプログラムの中から、指定された処理の緊急度に一致するプログラムを選択し、該プログラムに処理を依頼させる。プログラム位置データベースは、同一処理を行うプログラムについて、その優先順位または緊急度と、プログラムが動作する計算機とを記憶する。これにより、前記優先順位変更手段が存在しない場合でも、複数の緊急度の異なるプログラムを用意して、これらのうちから最も適した緊急度のプログラムに対して処理を依頼し、望ましい迅速さで処理を実行させることが可能となる。
【００２７】
処理転送手段は、プログラムが処理を実行中に新たに処理を依頼された際に、プログラム選択手段に別の同一処理を行うプログラムの位置を尋ね、その結果指定されたプログラムに対して処理依頼を転送する。これによって、処理実行中のプログラムに新たに依頼された処理を、該プログラムの処理が終了するまで待たせることなく、別の同程度の迅速さで処理できる（同一緊急度の）プログラムで実行させることが可能となり、より厳密なリアルタイム性保証を実現することができる。
【００２８】
（Ｂ）処理の時間制約を用いて管理する場合
優先順位決定手段は、各計算機の性能，負荷の少なくとも一方と、プログラムが実行する処理の時間制約，処理量とを考慮して、プログラムの実行に適した優先順位を決定する。これにより、各計算機の性能と負荷に応じて、処理の時間制約，処理量を個々の計算機の優先順位に変換して実行させ、新たに発生した時間制約の短い処理を、既に割り付けられている時間制約の長い処理に先んじて実行させるといったことが可能となる。また、処理の時間制約は計算機性能と負荷に応じて、計算機の優先順位に変換できるため、既に計算機に割り付けられている処理の時間制約が近付いている場合に、処理の時間制約を短くして再びより高い優先順位を決定し、新たに発生した処理が、既に割り付けられている処理の実行を妨げないようにすることもできる。すなわち、従来技術に比べて、より厳密なリアルタイム性を保証することが可能となる。優先順位決定手段の構成要素である八つの手段は以下の作用を有する。
【００２９】
優先順位変換手段は、単位処理量当たりの時間制約と優先順位との対応を示す優先順位対応表を有し、該優先順位対応表を用いることにより、処理の時間制約，処理量と優先順位との変換を行う。優先順位対応表の内容は計算機の性能，負荷および機種に応じて変更させる。
【００３０】
優先順位変更手段は、優先順位変換手段によって示された優先順位にしたがって、プログラムの優先順位を変更させる。優先順位変換手段と優先順位変更手段によって、処理を時間制約に対応した各計算機の優先順位で実行させ、時間制約の短い処理を他のより時間制約の緩い処理の前に実行させるといったことが可能となり、分散処理システムにおける各処理のリアルタイム性をより厳密に保証することができる。また、時間制約の長い処理であっても、他処理を優先的に処理させている間に、処理が行われないまま該時間制約が近付いてくることがあり、この際には、短くなった時間制約に応じて優先順位をより高く再設定し、この優先順位で処理を実行させることが可能となる。
【００３１】
通信時間予測手段は、個々の計算機間の通信時間を保持する通信時間表を有し、要求に応じて、各計算機との通信に要する時間を通知する。これにより、計算機間の通信時間が無視できない場合に、処理の時間制約をより厳密に設定することが可能となる。
【００３２】
計算機選択手段は、計算機性能情報と計算機負荷情報とからなる計算機情報を参照し、指定された単位処理量当たりの時間制約の負荷が均等に分散されるように計算機を選択し、プログラムを実行させる。計算機性能情報は各計算機の性能を示したテーブル，計算機負荷情報は各計算機の負荷を単位処理量当たりの時間制約毎に示したテーブルであり、計算機上の負荷が変化した場合、該変化量を計算機負荷情報に反映させる。これにより、処理の時間制約の短い処理が一つの計算機に集中するといった現象がなくなり、各計算機におけるリアルタイム性保証をより厳密に行うことが可能となる。
【００３３】
プログラム選択手段は、同一処理を行うプログラムの情報を纏めたプログラム位置データベースを用い、複数の同一処理を行うプログラムの中から、指定された単位処理量当たりの時間制約に一致するプログラムを選択し、該プログラムに処理を依頼させる。プログラム位置データベースは、同一処理を行うプログラムについて、その優先順位，時間制約のいずれか一つと、プログラムが動作する計算機とを記憶する。これにより、前記優先順位変更手段が存在しない場合でも、複数の時間制約の異なるプログラムを用意して、これらのうちから最も適した時間制約のプログラムに対して処理を依頼し、望ましい迅速さで処理を実行させることが可能となる。
【００３４】
処理転送手段は、プログラムが処理を実行中に新たに処理を依頼された際に、プログラム選択手段に別の同一処理を行うプログラムの位置を尋ね、その結果指定されたプログラムに対して処理依頼を転送する。これによって、処理実行中のプログラムに新たに依頼された処理を、該プログラムの処理が終了するまで待たせることなく、別の同程度の時間制約を有するプログラムで実行させることが可能となり、より厳密なリアルタイム性保証を実現することができる。
【００３５】
処理時間予測手段は、プログラムが実行しなければならない残り処理量と該プログラムの単位処理量当たりの時間制約とから、処理完了までの時間を計算する。
【００３６】
時間制約設定手段は、処理依頼時に指定された処理の時間制約と処理実行の経過時間とから、新たな処理の時間制約を決定する。処理時間予測手段と時間制約設定手段によって、プログラムが現在の優先順位で実行される場合に処理の時間制約を満たすか否かを判定し、時間制約を満たせないと判定される場合には、より短い時間制約を設定できる。新たに設定した時間制約を用いて、前記優先順位変換手段と優先順位変更手段がより高い優先順位をプログラムに与えることや、該新しい時間制約を満たし得る別の同一プログラムに処理を転送，実行させることができ、結果的に最初に与えられた時間制約を満たすように管理することが可能となる。
【００３７】
【実施例】
本発明の実施例を図面を用いて説明する。まず、緊急度を用いた一連の実施例を示し、その後、時間制約を用いた実施例を記述する。
【００３８】
（Ａ）処理の緊急度を用いる場合
図１に本発明の第一の実施例である分散処理システムの構成を示す。複数の計算機がネットワークに接続され、各計算機上のプログラムが互いに協調して動作する。１００〜１０３は計算機である。図中では４台の計算機が接続されたシステム構成を示すが、これ以上若しくはこれ以下の計算機数でシステムを構成することは可能である。１１０は通信バス，光ファイバ，クロスバ結合網等のネットワークである。各計算機上のプログラムはネットワーク１１０を介して互いに通信を行う。計算機１００および１０１のみ、計算機内部の詳細を示した。各計算機は中央処理装置１２０，主記憶装置１２１，入出力制御装置１２２等から構成され、内部バス１２５を用いてデータの授受を行う。個々の計算機では、中央処理装置１２０等の性能が異なることがある。入出力制御装置１２２はそれぞれ、通常、ディスク等の外部記憶装置１２３，端末１２４と接続され、外部とのデータの授受を行う。主記憶装置１２１上にはユーザプログラム１３０〜１３６，プライオリティキュー１４０〜１４１，スケジューラ１４２〜１４３，優先順位変換手続き手段１４４〜１４５，優先順位変更手続き手段１４６〜１４７が存在して、中央処理装置１２０によって処理される。一般には、個々の計算機にオペレーティングシステムが存在して、計算機上の各プログラムの実行状況を管理する。プライオリティキュー，スケジューラはオペレーティングシステムの一部であることが多い。図１ではオペレーティングシステムの記述を省略した。ユーザプログラム１３０〜１３６は、単独で若しくは互いに協調して処理を実行する。ユーザプログラムの数，各計算機への配置方法は任意である。
【００３９】
図１に示すようなマルチプロセッサ型計算機システムや分散処理システムにおいて複数のプログラムが協調して動作する場合には、各計算機上のユーザプログラムは、通常、オペレーティングシステムの待ち行列等によって順序管理が行われるが、ユーザプログラム間で処理の緊急性が異なることがある。このため、それぞれのプログラムに優先順位を与え、該優先順位ごとに待ち行列を構成して実行順序を管理する。プライオリティキュー１４０〜１４１が各計算機での優先順位ごとの待ち行列を構成している。図１に示す実施例では、計算機１００が０〜２５５の範囲の優先順位を、計算機１０１が０〜１２７の範囲の優先順位を所有していると仮定している。該優先順位それぞれに対して待ち行列が構成され、これを用いてスケジューラ１４２〜１４３が次に実行すべきプログラムを決定する。プライオリティキューの構成要素はプログラム構造体であり（プログラム構造体の一例が１６０〜１６６である）、それぞれ、ユーザプログラムの情報を所有する。主記憶装置１２１上に存在するユーザプログラム１３０〜１３６以外に、プログラムＤ，Ｅ，Ｆ等のプログラム構造体がプライオリティキューに存在するが、これらは、主記憶装置１２１上に配置されているプログラムではなく、外部記憶装置１２３上に存在するプログラムである。プログラムＤ，Ｅ，Ｆ等は、必要なプログラム，データを外部記憶装置１２３から主記憶装置１２１上に転送した後、実行することができる。
【００４０】
上記分散処理システムに対して処理を依頼する際には、該分散処理システムの各ユーザが、新たに各人のユーザプログラムを該分散処理システムのいずれかの計算機上で動作させるか、若しくは、既に存在しているプログラムに対して、入力手段より、データを入力して処理を行わせる。分散処理システム上の各プログラムは、必要に応じて互いに通信を行いつつ、処理を実行し、その結果をユーザに返却、若しくは、いずれかの計算機の端末に表示することとなる。すなわち、分散処理システムへの入力とは、端末などの入力手段を介して、分散処理システムへプログラム又はプログラムに対するデータを入力することである。また、分散処理システムからの出力とは、分散処理システムで処理されたプログラムの処理結果が、端末などの画面表示等として、出力されることである。
【００４１】
スケジューラ１４２〜１４３はプライオリティキュー１４０〜１４１の内容にしたがって、次に実行すべきプログラムを決定する。本実施例では、計算機100の優先順位０の待ち行列がプログラムＡ（ユーザプログラム１３０），優先順位１の待ち行列がプログラムＢ（ユーザプログラム１３１）およびプログラムＣ(ユーザプログラム１３２)から構成されている。このため、スケジューラ１４２が優先順位番号の小さいプログラムから処理を実行する方針を持つ場合、このプライオリティキューの構成では、プログラムＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，…の順に実行されることになる。プライオリティキュー１４０〜１４１およびスケジューラ１４２〜１４３は、通常、オペレーティングシステムの一部であり、オペレーティングシステムの種類によっては、スケジューラのプログラム実行順序決定方針が前述の順序と異なることがある。なお、以降、優先順位番号が小さいほど、優先順位が高い（より先に実行される）と仮定して実施例を説明する。
【００４２】
このように、プログラムの実行順序を考慮して各プログラムに優先順位を与えることにより、緊急性の異なるプログラムを同一計算機内で一様に扱うことができる。しかし、性能，負荷および機種の異なる計算機間では互いの優先順位に互換性がない。このため、本実施例では、分散処理システム内で共通の概念である緊急度を導入して、性能，負荷および機種の異なる複数の計算機から構成される分散処理システムでの優先順位の統一管理を行う。緊急度は分散処理システム全体に適用されるグローバルな優先順位と見なすことができる。本実施例では、０〜３１の範囲で緊急度を指定できると仮定している。本実施例で緊急度を導入するために設けた手段が、優先順位変換手続き手段１４４〜１４５および、優先順位変更手続き手段１４６〜１４７である。以降、優先順位と同様、緊急度の値が小さいほど、緊急性が高いと仮定して実施例を説明する。
【００４３】
優先順位変換手続き手段１４４〜１４５は、分散処理システムにおいて共通のデータである緊急度と計算機固有のデータである優先順位とを変換する手段である。本実施例は、優先順位変換手続き手段１４４〜１４５内に優先順位対応表１５０〜１５１を設ける。優先順位対応表１５０〜１５１は緊急度と計算機固有の優先順位との対応を示した表である。計算機１００では、緊急度０が優先順位０あるいは１に対応し、緊急度１が優先順位２乃至４に対応する。これに対し、計算機１００よりも性能の低い計算機１０１では、緊急度０が優先順位０に、緊急度１が優先順位１に対応し、同一の緊急度に対して高い優先順位が与えられる。これによって、同一緊急度でプログラムを実行した場合に、同程度の迅速さで処理が完了することを保証する。また、計算機の負荷に応じて優先順位対応表１５０〜１５１の内容を変更し、負荷の重い計算機では、同一緊急度が高い優先順位に対応するように設定する。優先順位変換手続き手段１４４〜１４５は優先順位対応表１５０〜１５１を用いて、与えられた緊急度から優先順位への変換、および、優先順位から緊急度への変換を行う。
【００４４】
優先順位対応表１５０〜１５１を図１に示す配列構造で作成することは可能であるが、同一緊急度に複数の優先順位が対応するため、緊急度から優先順位への変換が効率的に行えない。図２に緊急度と優先順位との変換を効率的に行うための優先順位対応表１５０のデータ構造の一例をＣ言語で記述した。緊急度と優先順位との変換を容易にするために、二つの配列を組み合わせて優先順位対応表を作成する。優先順位対応表において、優先順位から緊急度への変換は一意に行えるため、配列１７０を用いる。緊急度から優先順位への変換は１対多の変換であるため、各々の緊急度に対して、最小の優先順位と最大の優先順位を記憶する構造体を用いる（配列１７１）。各配列要素が示す値はデータ構造１７２に示すものとなる。このデータ構造を用いる場合、緊急度ｕと優先順位ｐとの変換は、以下のように行えばよい。
【００４５】
（１）優先順位から緊急度への変換：
ｕ←to_ｕrgency［ｐ］
（２）緊急度から優先順位への変換：
ｐ←to_priority［ｕ］.startからto_priority［ｕ］.endの間のいずれかかの整数値
なお、本実施例では、緊急度と優先順位とを１対多の関係に固定している。このため、優先順位から緊急度への変換を単純配列で実現しているが、緊急度の範囲が実施例に示す範囲に比べて大きい場合には、緊急度と優先順位との対応を多対多若しくは多対１の関係に設定できる。多対多の関係の場合、配列１７０を配列１７１と同様の構成とする必要がある。多対１の関係の場合には、配列１７０と配列１７１の構成を入れ換えることによって優先順位対応表を実現できる。なお、優先順位の範囲，緊急度の範囲を変更する場合には、配列１７０〜１７１の要素数を変更しなければならない。
【００４６】
図１および図２の例では、優先順位対応表１５０〜１５１を用いて緊急度と優先順位との変換を行っているが、優先順位対応表を用いない構成方法もある。図３に優先順位対応表を用いない優先順位変換手続き手段１４４の内容を示した。なお、図３ではＣ言語を用いて表現している。１８０が緊急度から優先順位への変換式であり、１８１が優先順位から緊急度への変換手続きである。本実施例では、最適な計算式として優先順位が緊急度の二乗に比例するものを選択しているが、個々の分散処理システムで最適な計算式を実験的に導出し、これを一次式、あるいは、多次式で表現することは可能である。この実施例では、比例係数として、負荷当たりの計算機性能を用いている。本実施例では、負荷をプライオリティキュー内のプログラム数（実行可能プログラム数）、性能は１０MIPS（１MIPSは一秒間に百万回命令を実行可能な性能）を単位とするＣＰＵ（中央処理装置）性能で表わすと都合がよい。この変換手続きを用いることにより、プログラム当たりのＣＰＵ性能が高ければ、同一緊急度に対して低い優先順位（優先順位番号大）を設定でき、プログラム当たりのＣＰＵ性能が低ければ、同一緊急度に対して高い優先順位（優先順位番号小）を設定できる。
【００４７】
図１の優先順位変更手続き手段１４６〜１４７は優先順位変換手続き手段144〜１４５によって計算された計算機固有の優先順位にしたがって、各プログラムの優先順位を変更する。例えば、図１では、プログラムＪ（ユーザプログラム１３３）の状態が緊急度１，優先順位４である。このプログラムの緊急度が１から０に変化すると仮定すると、優先順位変換手続き手段１４４によって緊急度から優先順位への変換が行われ、新たな優先順位として０（優先順位を１としてもよい）が得られる。この値を用いて、優先順位変更手続き手段１４６はユーザプログラム１３３の優先順位を０に変更する。同時に、プログラムＪのプログラム構造体１６３を優先順位０の待ち行列に繋ぎ換える。
【００４８】
優先順位変換手続き手段１４４〜１４５と優先順位変更手続き手段１４６〜１４７はいずれも、オペレーティングシステムの一部、若しくは、オペレーティングシステムと協調して動作するサービスプログラムである。サービスプログラムとしてこれらの手続きを構成する場合は、優先順位変更手続き手段１４６〜１４７はプログラムの優先順位の変更をオペレーティングシステムに依頼する形式を採用する必要がある。依頼されたオペレーティングシステムが実際に優先順位の変更と待ち行列におけるプログラム構造体の繋ぎ換えを行う。
【００４９】
次に、本実施例に示した優先順位変換手続き，優先順位変更手続きを用いて、計算機間で緊急度を用いて処理を依頼する方式について説明する。リアルタイム分散処理システムでは、計算機間で処理を依頼する際に、どの程度迅速に処理を完了してほしいかを示すことにより、システム構築を容易にすることができる。このため、本発明では、依頼元プログラムが処理依頼時に緊急度を指定できるようにする。図４は本発明における緊急度指定方法をＣ言語で記述した一例である。１９０は処理依頼の先頭引数に緊急度を指定する方法、１９１は処理依頼の最終引数に緊急度を指定する方法である。なお、ユーザプログラムがこれを直接記述する必要はなく、コンパイラ，トランスレータが１９０および１９１の形式に翻訳する方法を用いることも可能である。
【００５０】
図５に上記緊急度指定方法を用いた処理依頼の流れの概要を示した。符号100〜１０１，１１０，１３０〜１３６，１４０〜１４７，１５０〜１５１，１６０〜１６６は図１と同一である。計算機１０２〜１０３並びに計算機内の詳細は省略している。本実施例では、ユーザプログラム１３３がユーザプログラム１３６に処理を依頼する際の流れを示す。通信２００〜２０６が該処理の流れである。本発明では、図面において通信を示す矢印記号の隣に記したデータが、該通信で送られる重要なデータを示すものとしている。ユーザプログラム１３３はプライオリティキュー１４０内では優先順位４（プログラム構造体１６３）を有している。ユーザプログラム１３３は、第一に、優先順位から緊急度への変換を優先順位変換手続き手段１４４に対して依頼する（通信２００）。図５では、計算機１００の優先順位４が緊急度１に対応しているので、優先順位変換手続き手段１４４は変換結果として緊急度１を返答する（通信２０１）。次に、ユーザプログラム１３３は受理した緊急度１を用いて、図４の緊急度指定方式１９０または１９１で、ユーザプログラム１３６に対して処理を依頼する（通信２０２）。計算機１０１では、緊急度１指定の通信を受信すると、該緊急度を計算機固有の優先順位に変換し、変換結果の優先順位でユーザプログラム１３６を実行させなければならない。ユーザプログラム１３６は緊急度１を指定して、優先順位変更手続き手段１４７に優先順位の変更を依頼する（通信２０３）。優先順位変更手続き手段１４７は優先順位変換手続き手段１４５に緊急度から優先順位への変換を依頼する（通信２０４）。図５では、緊急度１が計算機１０１の優先順位１に対応する。優先順位変換手続き手段１４５は変換結果として、優先順位１を優先順位変更手続き手段１４７に通知し、ユーザプログラム１３６が優先順位１で実行されなければならないことを知らせる（通信２０５）。最後に、優先順位変更手続き手段１４７はプライオリティキュー１４１内のプログラム構造体１６６（ユーザプログラム１３６に対応するプログラム構造体）を優先順位１の待ち行列に繋ぎ換えさせる(通信２０６)。
【００５１】
これにより、異なる計算機上に存在する処理依頼元および依頼先プログラムの優先順位を分散処理システム全体に共通の概念である緊急度を用いて統一的に管理することができる。なお、処理依頼元プログラムが予め自己の緊急度を認識している場合には、計算機固有の優先順位から緊急度への変換処理（通信２００および２０１）は不要である。さらにまた、自己の緊急度と異なる緊急度で処理を依頼することも可能であり、この場合にも、直接緊急度を指定して処理依頼を行えばよい。
【００５２】
本実施例で図１に示した優先順位対応表１５０〜１５１はそれぞれ、計算機の性能を考慮して割り当てられるが、実際には、計算機の負荷によって処理の完了までの時間が異なってくる。このため、本実施例では、計算機負荷が変化する度に優先順位対応表１５０〜１５１を変化させる。図６に優先順位対応表の内容変更方法２１０を示した。
【００５３】
本実施例では、負荷（実行可能プログラム数）が一定量増減した場合、優先順位対応表の内容を変更する。ここで、前回優先順位対応表の内容を変更した後の負荷の変化量を総負荷変化量と呼ぶ。負荷が変化した場合、総負荷変化量に今回変化した負荷量を足し込み（処理２１１）、この結果、総負荷変化量が正の一定値以上となるか（処理２１２）、若しくは、総負荷変化量が負の一定値以下となるか（処理２１３）を判定する。正の一定値以上であれば、負荷が一定量増加したことを示すので、優先順位対応表の緊急度境界を上にずらし（処理２１４）、総負荷変化量が負の一定値以下であれば、負荷が一定量減少したことを示すため、優先順位対応表の緊急度境界を下にずらす（処理２１５）。優先順位対応表の内容を変更した場合には、最後に、総負荷変化量に０を設定し（処理２１６）、再び総負荷変化量の計数を最初から行う。
【００５４】
処理２１４および処理２１５で優先順位対応表の緊急度境界を上下にずらす意味について、図７を用いて説明する。優先順位対応表１５０の緊急度境界が負荷の増加によって上に移動すると、優先順位対応表２２０のように変化する。このとき、変化前の優先順位対応表に比べ、同一緊急度であっても、より高い優先順位にプログラムを割り当てることができる。同様に、緊急度境界が負荷の減少によって下に移動すると、対応表２２１のように変化し、同一緊急度のプログラムがより低い優先順位に割り当てられることになる。上記のように緊急度境界を上下に移動することにより、同一緊急度のプログラムを同一性能を有する計算機（あるいは、同一計算機）で動作させる場合でも、負荷が重ければ高い優先順位で、負荷が軽ければ低い優先順位で動作させることができ、各計算機上での負荷の増減をも考慮した統一的な優先順位管理を行うことができる。
【００５５】
なお、本実施例では、緊急度境界を上下に一つ移動しているが、負荷変化量に応じて、移動量を変化させることも可能である。
【００５６】
次に、図２に示した優先順位対応表のデータ構造１７０および１７１を用いた場合に緊急度境界を上下に移動する手続きを説明する。図８に、この手続きの一例をＣ言語で記述した。２３０が緊急度境界を上に移動する手続きである。データ構造１７１のto_priority［ｕ］.endおよびto_priority［ｕ＋１］.startが緊急度ｕの下の緊急度境界を示すので、これらを減少させることによって、緊急度境界を上にずらすことができる(処理２４０〜２４１)。また、優先順位対応表の緊急度境界を移動させると、優先順位から見た緊急度が変化する部分がある。例えば、図７において、優先順位１に対応する緊急度は、緊急度境界が上に移動することにより、０から１に変化する。このため、優先順位から緊急度への変換を行う配列１７０の内容を変更しなければならない。緊急度境界を上に移動させた場合、優先順位から見た緊急度が変化した部分はto_priority［ｕ＋１］.startである。したがって、to_urgency［to_priority［ｕ＋１］.start］ の値を増加させて補正する（処理２４２）。
【００５７】
ここで、上記の優先順位対応表への変更を行うと、既にプライオリティキューに存在しているプログラムの緊急度が変化することがある。例えば、図７において、緊急度０，優先順位１であったプログラムは、緊急度境界を上に移動させると、緊急度１，優先順位１の属性を有することになる。本実施例では、このプログラムを緊急度０に補正するため、後述する図９の処理を、優先順位変更手続き手段１４６〜１４７に導入できる。図９の処理は、優先順位対応表の変更により緊急度が変化したプログラムの優先順位を変更して、優先順位対応表変更前と同一の緊急度を有するように変更するものである。前記の例では、優先順位１に属する全てのプログラムの優先順位を１減少させ、優先順位を０に変化させることにより、これらのプログラムの緊急度を優先順位対応表変更前の値（緊急度０）に補正させる。２４３は優先順位変換手続き手段１４４〜１４５から図９の機能を呼び出す処理である。処理２４３では図９の処理名がchange_all_priority であると仮定し、さらに、指定すべき引数は緊急度と優先順位との対応が変化した部分to_priority［ｕ＋１］.start と優先順位の増加分である（処理２４３では優先順位の増加分が−１であり、優先順位の減少を指定していることになる）。図９に優先順位変更手続き手段１４６〜１４７の機能の内、特定の優先順位を有するプログラムを全て別の優先順位に変更する処理２５０の内容を示した。処理２５０は、指定された優先順位に対応する待ち行列をプライオリティキュー１４０〜１４１から取り出し（処理２５１）、該待ち行列が空か否かを調べる（処理２５２）。待ち行列が空でない限り、該待ち行列内のプログラム構造体を取り出して（処理２５３）、プログラムの優先順位を指定分だけ増加させる（処理２５４。指定値が負であれば優先順位は減少する。なお、優先順位が減少することは、本実施例では、より高い優先順位となることを意味するものである）。さらに、取り出したプログラム構造体を、指定分だけ増加させた優先順位の待ち行列に繋ぎ換える（処理２５５。負の値を増加させると優先順位は減少する）。これにより、処理２４３から要求される優先順位変更を行うことができ、緊急度を同一に保つようにプログラムの優先順位を変化させることができる。
【００５８】
同様に、図８の２３１が緊急度境界を下に移動する手続きであり、データ構造１７１のto_priority［ｕ］.endおよびto_priority［ｕ＋１］.startを増加させることによって、緊急度境界を下に移動させる（処理２４４〜２４５）。緊急度境界を下に移動させる場合、優先順位から見た緊急度が変化する部分は        to_priority［ｕ］.endである。したがって、to_urgency［to_priority［ｕ］. end］の値を減少させて補正する（処理２４６)。手続き２３０と同様、処理247によって、プログラムの優先順位の変更を行わせることができる。この場合には、引数として、緊急度と優先順位との対応が変化した部分to_priority［ｕ］.  endと優先順位の増加分１を指定する。
【００５９】
以上、図１乃至図９で第一の実施例の構成，動作，方法について述べた。本実施例によれば、緊急度を用いて、分散処理システム内の性能，負荷および機種の異なる複数の計算機の優先順位を統一的に管理することができ、同一緊急度を指定することにより、いずれの計算機においても同程度の迅速さで処理が完了することを期待できる。また、緊急度が計算機の性能，負荷を考慮して優先順位に変換されるため、異なる計算機上の処理であっても、低い緊急度の処理が高い緊急度の処理に先んじて完了するという逆転現象も避けることができるようになる。すなわち、分散処理システムにおけるより厳密なリアルタイム性の保証を行うことができる。
【００６０】
本実施例では、さらに、優先順位対応表の内容変更およびプライオリティキューの内容変更（図６乃至図９）を行うことができ、これにより、各計算機での動的な負荷変化に対応しつつ優先順位管理を行うことが可能となる。
【００６１】
本実施例では、さらに、上記二つの効果の上に、計算機間に跨る処理依頼において、処理の重要度に応じた緊急度を指定することができ、かつ、緊急度を指定する際には、相手計算機の性能，負荷および機種を知る必要がない。
【００６２】
なお、本実施例では、計算機の負荷を実行可能状態にあるプログラムの数で表現したが、実行可能状態にあるプログラムの処理量または処理予測時間の和で表現する方式もある。これにより、計算機の負荷計算がより正確となり、より厳密なリアルタイム性保証を行うことができる。また、本実施例では、各計算機の負荷と性能の両者を考慮して優先順位を決定しているが、いずれか一方のみを考慮して決定することもできる。特に、分散処理システムが同一計算機から構成される場合、負荷のみを考慮すればよく、緊急度と優先順位との変換を効率的に行うことができる。
【００６３】
次に、図１０に本発明の第二の実施例である分散処理システムの構成について示す。図１０に示す実施例の特徴は、分散処理システム内の全ての計算機の優先順位を管理する優先順位変換手続き手段２６０を用意したことである。符号100〜１０１，１１０，１３０〜１３６，１４０〜１４３，１４６〜１４７，１６０〜１６６は図１と同一である。計算機１０２〜１０３並びに計算機内の詳細は省略している。優先順位変換手続き手段２６０は全ての計算機の優先順位と緊急度との優先順位対応表２７０を有する。優先順位対応表２７０のデータ構造は図２に示したデータ構造１７０および１７１を計算機数だけ用意したものに等しい。したがって、優先順位対応表の変更、並びに、それに伴うプログラムの優先順位の変更は図６乃至図９で説明した処理と同一の処理を行えばよい。
【００６４】
図１０には、さらに、緊急度を指定した処理依頼の流れの概要を示している。図５と同様に、本実施例では、ユーザプログラム１３３がユーザプログラム136に処理を依頼する際の流れを示す。ユーザプログラム１３３は、第一に、優先順位から緊急度への変換を優先順位変換手続き手段２６０に対して依頼する（通信２８０）。ユーザプログラム１３３と優先順位変換手続き手段２６０とが互いに異なる計算機に存在する場合、通信２８０は計算機間通信となる。優先順位対応表２７０により、計算機１００の優先順位４が緊急度１に対応していることが判るので、優先順位変換手続き手段２６０は変換結果として緊急度１を返答する（通信２８１）。次に、ユーザプログラム１３３は受理した緊急度１を用いて、ユーザプログラム１３６に対して処理を依頼する（通信２８２）。計算機１０１では、緊急度１指定の通信を受信すると、該緊急度を計算機固有の優先順位に変換し、その優先順位でユーザプログラム１３６を実行させる。ユーザプログラム１３６は緊急度１を指定して、優先順位変更手続き手段１４７に優先順位の変更を依頼する（通信２８３）。優先順位変更手続き手段１４７は優先順位変換手続き手段２６０に緊急度から優先順位への変換を依頼する（通信２８４）。本実施例では、緊急度１が計算機１０１の優先順位１に対応する。優先順位変換手続き手段２６０は変換結果として、優先順位１を優先順位変更手続き手段１４７に通知し、ユーザプログラム１３６が優先順位１で実行されなければならないことを知らせる（通信２８５）。ユーザプログラム１３６と優先順位変換手続き手段２６０とが互いに異なる計算機に存在しているので、通信２８４および２８５は計算機間通信となる。最後に、優先順位変更手続き手段１４７はプライオリティキュー１４１内のプログラム構造体１６６を優先順位１の待ち行列に繋ぎ換えさせる（通信２８６）。
【００６５】
なお、図５と同様、処理依頼元プログラムが予め自己の緊急度を認識している場合には、計算機固有の優先順位から緊急度への変換処理（通信２８０および２８１）は不要である。さらにまた、自己の緊急度と異なる緊急度で処理を依頼することも可能であり、この場合にも、直接緊急度を指定して処理依頼を行えばよい。
【００６６】
以上に示した第二の実施例は、図１乃至図９に示した第一の実施例において、優先順位変換手続きを一つの計算機上に纏めて配置させたものに等しく、前述した第一の実施例の効果の上に、優先順位対応表の管理を纏めて容易に行うことができるという利点がある。分散処理システム内に該システム全体を管理する高性能かつ高信頼の計算機が存在し、該計算機に優先順位管理の手続きも纏めて配置させるという考えに適している。
【００６７】
次に、本発明の第三の実施例について説明する。分散処理システムにおいては、各計算機にプログラムを均等に分散させ、各計算機の負荷を均等化させることもリアルタイム性を保証することに役立つ。しかしながら、プログラムを均等に分散させても、一つの計算機に緊急性を要するプログラムが集中し、別の計算機に重要性のないプログラムが集中するような負荷分散では計算機資源を効率的に使用しているとは言えない。また、一つの計算機に緊急性の高いプログラムが集中すると、結果的に該計算機上での処理が遅れ、リアルタイム性保証を妨げることになる。本発明では、緊急度を用いて、個々のプログラムの重要性を加味した負荷分散を行うことができる。図１１に負荷分散を行う第三の実施例の分散処理システムの構成を示す。符号１００〜１０３，１１０，１３０〜１３６，１４０〜１４３，１４６〜１４７，１６０〜１６６は図１と同一、優先順位変換手続き手段２６０，優先順位対応表２７０は図１０と同一であり、その動作も同様である。ただし計算機１０１の主記憶装置上にはユーザプログラム１３０〜１３６の他、ユーザプログラム１３７も存在し、プログラム構造体１６７を用いて管理される。
【００６８】
プログラム実行・移動手続き手段２９０〜２９１はプログラムの起動や、計算機間でのプログラム移動を行うもので、通常はオペレーティングシステムの機能として提供される。プログラムの起動とは、新たに実行すべきプログラムのプログラム構造体を生成し、これをプライオリティキュー１４０〜１４１に登録することにより、プログラムを実行可能状態にすることである。また、プログラム移動とは、ある計算機で実行可能状態のプログラムを他の計算機に移動して、移動先の計算機で実行可能状態にすることであり、プロセス移送とも呼ばれ、分散オペレーティングシステムの機能として提供されることが多い。
【００６９】
計算機情報３００は計算機負荷情報３０２と計算機性能情報３０４から成る。計算機負荷情報は、各計算機の負荷、すなわち実行すべきプログラムの数を、緊急度別に記憶したものである。例えば、現在の計算機１００の負荷は緊急度０が３，緊急度１が８，緊急度２が７で、計算機１０１の負荷は緊急度０が１，緊急度１が１，緊急度２が２である。計算機性能情報は、各計算機の性能を記憶している。例えば本実施例では１０MIPSを１として性能を表現しており、計算機100の性能は１０，計算機１０１の性能は３である。なお、プログラム実行・移動手続き手段２９０〜２９１はプログラムの起動や移動を行った場合、その変化を計算機負荷情報３０２に反映する処理を行う。これにより計算機負荷情報３０２は、その時点での分散システム全体の負荷状態を正しく表わすことができる。
【００７０】
プログラム移動決定手続き手段２９２は、各計算機の負荷が性能に見合って均等に分散されているかどうかを、計算機情報３００中の計算機負荷情報３０２を調べて判定し、均等でない場合、均等になるようにプログラムを移動することを決定する。本実施例では、プログラム移動決定手続きは一定周期で定期的に起動されるものとする。計算機選択手続き手段２９４は新たに実行すべきプログラムが生じた場合それをどの計算機で実行するか、およびプログラムを計算機間で移動する場合にどの計算機に移動するかを、計算機情報３００中の計算機負荷情報３０２と計算機性能情報３０４を参照して決定する。
【００７１】
本実施例の動作を図１１乃至図１５を用いて説明する。まず、新たにプログラムを起動する場合の処理について説明する。プログラムの起動は、例えば、ユーザがプログラムの実行可能ファイル名と緊急度を指定したコマンドを入力すると、オペレーティングシステムがそのコマンドを解析し、オペレーティングシステム中のプログラム実行・移動手続き手段２９０〜２９１にプログラム起動を依頼することにより可能となる。ここでは緊急度１のプログラムの起動コマンドが計算機１００で入力され、プログラム実行・移動手続き手段２９０がプログラムの起動処理を行う場合について、以下説明する。
【００７２】
プログラム起動処理３１０の動作を図１２により説明する。まず、プログラム実行・移動手続き手段２９０が計算機選択手続き手段２９４に依頼して、緊急度の範囲が０から起動するプログラムの緊急度までの負荷／性能値を、全ての計算機について算出する（処理３１１）。ここで、負荷／性能値とは、計算機の負荷量をその計算機の性能で割った値である。本実施例では、計算機のプライオリティキューに登録されている実行可能状態のプログラムの個数をその計算機の負荷量とする。算出は図１１に示した計算機情報３００中の計算機負荷情報３０２と計算機性能情報３０４を読み出して行う。図１１の状態の各計算機の負荷情報，負荷量，負荷／性能値を図１３に示す。計算機負荷情報３０２は各緊急度ごとの実行可能状態のプログラム数を表わしているが、緊急度０から特定の緊急度の範囲に含まれる実行可能状態のプログラム数が負荷量３０６であり、これを計算機の性能で割ったものが負荷／性能値３０８である。ここでは新たに起動するプログラムが緊急度が１の場合について考えているので、緊急度範囲０〜１の負荷／性能値を算出すると、計算機１００の負荷／性能値は１.１０ ，計算機１０１の負荷／性能値は０.６７となる。
【００７３】
次に、計算機選択手続き手段２９４は最も負荷／性能値が低い計算機を、起動すべきプログラムを実行する計算機として選択する（処理３１２）。図１３では計算機１０２以降については省略しているが、計算機１０１の負荷／性能値0.67が最も小さいとすると、計算機１０１が選択される。最後にプログラム実行・移動手続きは、選択した計算機でプログラムを起動する処理を行う(処理３１３)。これは、プログラム起動処理を開始した計算機のプログラム実行・移動手続きが、選択した計算機のプログラム実行・移動手続きに、プログラムを実行可能状態にするよう依頼することにより行う。この場合、計算機１００のプログラム実行・移動手続き手段２９０が、計算機１０１内のプログラム実行・移動手続き手段２９１に対して、通信を行い、プログラムを実行可能状態にするよう依頼する。次に、実行可能状態のプログラムを移動する処理について説明する。本実施例では、プログラム移動決定手続き手段２９２が定期的に起動され、各計算機の負荷が性能に見合って均等に分散されていない場合、均等になるようにプログラムを移動することを決定し、プログラム実行・移動手続き手段２９０〜２９１に移動を依頼する。プログラム実行・移動手続き手段２９０〜２９１は、計算機選択手続き手段２９４に依頼して、移動先の計算機を決定し、移動先の計算機のプログラム実行・移動手続きと協調して、プログラムの移動処理を行う。本実施例では計算機の負荷が性能に見合って均等であるかどうかを判定するための値として、前述の負荷／性能値を用いる。
【００７４】
プログラム移動処理３２０の動作を図１４を用いて説明する。まず、プログラム移動決定手続きは緊急度の範囲を表わす変数ｎに０を代入する(処理３２１)。そして、緊急度範囲が０からｎまでについて、各計算機の負荷／性能値を算出する（処理３２２）。前述のように図１１の状態の負荷／性能値の値は図１３の負荷／性能値３０８のようになる。次に全ての計算機のうち、該緊急度範囲の最大の負荷／性能値と最小の負荷／性能値の差Ｄを算出する（処理３２３）。図１３では計算機１０２以降については省略しているが、ｎが０の場合、計算機１０１の負荷／性能値０.３３が最も大きく、計算機１００の負荷／性能値０.３０が最も小さいとすると、Ｄの値は０.０３ となる。このＤの値が閾値Ｄｔを越えているかどうかを調べる（処理３２４）。本実施例では閾値Ｄｔとして０.３ という値を用いるものとする。Ｄの値が閾値Ｄｔを越えている場合には処理３２５に移り、越えていない場合には処理３２８に移る。ここでは、ｎが０の場合にはＤの値はＤｔを越えていないので、処理３２８に移り、ｎの値に１を加える。そしてｎの値が３１を越えているかを判定し（処理３２９）、越えていれば処理を終了し、越えていなければ処理３２２に戻る。
【００７５】
ここではｎが１なので、処理３２２に戻り、各計算機の負荷／性能値を算出し、次に処理３２３でＤの値を算出する。図１３では計算機１０２以降については省略しているが、ｎが１の場合、計算機１００の負荷／性能値１.１０ が最も大きく、計算機１０１の負荷／性能値０.６７ が最も小さいとすると、Ｄの値は０.４３ となる。したがってｎが１の時、Ｄの値は閾値Ｄｔを越えている。Ｄの値が閾値Ｄｔを越えている場合には負荷が均等ではないものと判定し、移動すべきプログラムを決定する（処理３２５）。本実施例では、負荷／性能値が最大の計算機の、緊急度ｎに対応する実行可能状態のプログラムのうち、プライオリティキューにおける実行順位が最後尾のプログラムを選択することとする。この場合、図１１に示したように、計算機１００の緊急度１に対応する優先順位は２〜４であり、そのうち実行順位が最後尾なのはＫ（プログラム構造体１６７）なので、これを移動対象プログラムとする。
【００７６】
移動対象プログラムが決定したら、プログラム移動決定手続き手段２９２は、移動対象プログラムが存在する計算機のプログラム実行・移動手続きに、移動対象プログラムの移動処理を依頼する。この場合は計算機１００のプログラム実行・移動手続き手段２９０がプログラム移動処理を行う。まず、プログラム実行・移動手続き手段２９０は計算機選択手続き手段２９４に依頼して、移動対象プログラムの移動先の計算機を選択する（処理３２６）。本実施例では負荷／性能値が最小の計算機を移動先とする。したがってこの場合、ｎが１の場合の最小負荷／性能値の計算機１０１を移動先とする。
【００７７】
移動先が決定したらプログラム実行／移動手続きがプログラム移動処理を実行する（処理３２７）。この場合、計算機１００のプログラム実行・移動手続き手段２９０は、プログラム移動先計算機１０１のプログラム実行・移動手続き手段２９１と協調して、プログラム移動処理を実行する。通常、プログラム実行・移動手続きはオペレーティングシステムにより提供される。プログラム移動において、移動先の計算機１０１に移動すべきプログラムの実行可能ファイルが存在しない場合には、それを計算機１００から計算機１０１に転送するするとともに、計算機１００のプログラム構造体をプライオリティキューから削除し、移動先の計算機でプログラム構造体を生成し、それを移動先の計算機のプライオリティキューに追加することにより、実行可能状態にする処理が必要である。プログラムの移動が行われると、それによる計算機の負荷の状態は計算機負荷情報３０２に反映される。この場合、計算機負荷情報３０２は図１５に示すように、緊急度１の実行可能状態のプログラムの数が、計算機１００では７，計算機１０１では２になる。
【００７８】
このようにして、プログラムの移動が行われると、処理３２２に戻り、もう一度各計算機の負荷／性能値を算出する。この場合には図１５に示すような負荷量３０６、および負荷／性能値３０８になる。図１５では計算機１０２以降については省略しているが、ｎが１の場合、まだＤの値がＤｔを越えている場合には、さきほどと同様にプログラムの移動処理を行う。Ｄの値がＤｔ以下となったとすると、処理３２８に移る。
【００７９】
以上述べた処理をｎが３１を越えるまで行うことにより、全ての緊急度について、負荷分散、すなわち計算機性能に見合った負荷の均等化のためのプログラム移動が行われる。
【００８０】
なお、上記ではプログラム移動決定手続きによって起動される、負荷分散のためのプログラム移動について述べたが、ユーザがコマンドにより指定することにより、プログラム移動を行うこともできる。この場合には移動すべきプログラムの緊急度をｎとし、図１４の処理３２６〜３２７の処理を行うことにより、最も負荷の小さな計算機にプログラムを移動できる。
【００８１】
以上、本発明の第三の実施例について説明した。本実施例によれば、計算機の負荷が各計算機の性能に見合って均等にユーザプログラムを割り当てることができ、計算機資源を有効に活用できるという効果がある。ここで、本実施例では、計算機の負荷量と性能の両者を考慮して、負荷の均等性の評価を行っており、計算機の性能が変化しても、負荷の評価を平等に行えるという効果がある。
【００８２】
また、本実施例によれば、プログラムの緊急度の各レベルにおいて、各計算機の性能に見合って均等にユーザプログラムを割り当てることができ、分散処理システム全体で統一的な緊急度によってリアルタイム処理が可能になるという効果がある。特に、プログラムの緊急度を考慮して負荷分散を行うため、一つの計算機に緊急性を要する処理が集中することがなくなり、より厳密なリアルタイム性保証を行うことができる。
【００８３】
また、本実施例では、分散処理システム全体の負荷の管理を一つの計算機で集中的に行っており、プログラム起動先やプログラム移動先の決定を、他の計算機との通信を行うことなく、効率的に行えるという効果がある。
【００８４】
本発明の第四の実施例について図１６を用いて説明する。本実施例では上記本発明の第三の実施例と異なり、計算機の性能および負荷に関する情報を、計算機単位に保有する。図１６は本実施例の構成を表わしたものである。符号１００〜１０１，１１０，１３０〜１３６，１４０〜１４７，１５０〜１５１，１６０〜１６６は図１と同一であり、その動作も同様である。計算機１０２〜１０３および計算機内部の詳細は省略している。また記号１３７，１６７，２９０〜２９１は図１１と同一であり、その動作も同様である。
【００８５】
計算機情報３３０〜３３１は、計算機負荷情報３３２〜３３３、および、計算機性能情報３３４〜３３５を含んでいる。プログラム移動決定手続き手段２９６〜２９７は、各計算機の負荷が性能に見合って均等に分散されているかどうかを、互いに計算機間で通信しあって判定し、そのプログラム移動決定手続きが存在する計算機の負荷が他の計算機に比較して大きい場合、均等になるようにプログラムを移動することを決定する。プログラム移動決定手続き手段２９６〜２９７は、この処理を計算機情報３３０〜３３１中の計算機負荷情報３３２〜３３３を参照して実行する。計算機選択手続き手段２９８〜２９９は新たに実行すべきプログラムが生じた場合、それをどの計算機で実行するか、およびプログラムを計算機間で移動する場合にどの計算機に移動するかを、互いに計算機間で通信しあって決定する。計算機選択手続き手段２９８〜２９９はこの処理を計算機情報３３０〜３３１中の計算機負荷情報３３２〜３３３と計算機性能情報３３４〜３３５を参照して決定する。
【００８６】
本実施例において、新たにプログラムを起動する場合の処理、およびプログラム移動処理はいずれも基本的には図１１〜図１５を用いて説明した前記第三の実施例と同様である。ただし前記第三の実施例では、全計算機の負荷／性能値の計算を、一つの計算機１００上のプログラム移動決定手続き手段２９２、または計算機選択手続き手段２９４が行ったが、本実施例では、各計算機の負荷／性能値の計算をそれぞれの計算機上のプログラム移動決定手続き手段２９６〜２９７、または、計算機選択手続き手段２９８〜２９９が行い、それらの計算により得た負荷／性能値を、プログラム起動を行う計算機上の計算機選択手続きまたはプログラム移動を行う計算機上のプログラム移動決定手続きが収集することにより、プログラムの起動先およびプログラムの移動先を決定するという点が異なる。
【００８７】
本実施例では、前記第三の実施例で示した負荷分散，リアルタイム性保証の効果に加え、負荷の管理を各計算機単位で分散して行っており、各計算機がプログラムの起動や移動を行ったとき、該計算機および起動先または移動先の計算機が、自分の計算機内の計算機負荷情報を変更するのみでよいので、状態変化の計算機負荷情報への反映処理を効率的に行えるという効果がある。また、分散システム内の計算機を取り除いたり、計算機を新たに追加した場合でも、計算機情報のテーブルを変更する必要がないため、システムの拡張性が向上するという効果がある。
【００８８】
以上述べた、上記第三および第四の実施例については、いくつか別の実施例がある。上記第三および第四の実施例では、緊急度を指標としてプログラムの負荷情報を記憶し、評価することにより、プログラムの起動や移動を行ったが、緊急度ではなく各計算機の優先順位を指標として記憶し、評価する方式もある。これにより各計算機では優先順位のみを考慮して処理を行えばよく、緊急度と優先順位の変換処理が少なくなり、処理を効率化できるという効果がある。また、この場合、本発明の第一の実施例の図６乃至図９で示したように、緊急度と優先順位の対応関係を管理している優先順位変換手続き手段２６０、あるいは優先順位変換手続き手段１４４〜１４５に対して計算機の負荷に応じて対応関係を変更する機能を持たせることもでき、これにより、計算機の負荷に応じた緊急度または優先順位の制御が可能になるという効果がある。
【００８９】
さらにまた、上記第三および第四の実施例では、計算機の負荷量を実行可能状態にあるプログラムの数で表現したが、実行可能状態にあるプログラムの処理量または処理予測時間の和で表現する方式もある。これにより、計算機の負荷の評価が正確になり、より均等な負荷の分散が可能になるという効果がある。
【００９０】
さらにまた、上記第三および第四の実施例では、各計算機の負荷と性能の両者を考慮して、プログラムを起動あるいは移動する計算機を決定したが、いずれか一方のみを考慮して決定することもできる。特に、複数の同一機種の計算機から成る分散システムの場合には、各計算機の負荷のみを考慮すればよい。これにより処理が簡単になり、効率がよくなるという効果がある。
【００９１】
さらにまた、上記第三および第四の実施例では、計算機の負荷量を、緊急度が０から起動するプログラムまたは移動するプログラムの緊急度までの範囲に含まれる、実行可能状態のプログラムについて評価したが、起動するプログラムまたは移動するプログラムの緊急度に等しい、実行可能状態のプログラムについて評価するという方式もある。これにより負荷量の算出時間が短くなり、処理が効率化できるという効果がある。
【００９２】
分散処理システムにおいては、複数の同一処理を行うプログラムを複数の計算機上で動作させ、処理依頼を分散させることができる。処理依頼を分散させるに当たって、従来は、複数の同一処理を行うプログラムの中から、暇な（処理を実行していない）プログラムを選択し、該プログラムに処理依頼を行っていた。しかしながら、リアルタイム分散処理システムで上記のプログラム選択方法を行う場合、必ずしも高い優先順位のプログラムが選択されるわけではなく、依頼元に望ましい迅速さで処理が完了するとは限らない。図１７は、複数の同一プログラムから処理依頼元に望ましい優先順位のプログラムを選択し、該プログラムに対して処理を実行させるための本発明の第五の実施例である。本実施例は、望ましい迅速さで動作するプログラムを選択するというリアルタイム性保証と、処理の負荷分散とを同時に達成させるための実現システムである。本実施例は、前述した優先順位変換手続き手段２６０と該優先順位変換手続き手段２６０の変換結果を用いて処理依頼先プログラムを決定するプログラム選択手続き手段４１０を用いて実現される。
【００９３】
図１７中、符号１００〜１０３，１１０，１４０〜１４３は図１と同一である。計算機１００〜１０１のハードウェア詳細については省略してある。優先順位変換手続き手段２６０および優先順位対応表２７０は図１０と同一の手続き，データ構造を使用する。４３０〜４４２はユーザプログラムである。ユーザプログラムの内、ユーザプログラム４４０〜４４２は、プログラム選択手続き手段410の管理対象でないプログラムである。分散処理システム内で唯一のプログラム，処理依頼を受けずに単独で動作するプログラム等がプログラム選択手続き手段４１０の管理対象外とすることができる。個々のユーザプログラムにはそれぞれ優先順位が与えられ、プライオリティキュー１４０〜１４１内の優先順位毎の待ち行列で管理される。４５０〜４５１，４５４〜４５８，４６０〜４６２は各ユーザプログラムのプログラム構造体の一例であり、それぞれ、ユーザプログラム４３０〜４３１，４３４〜４３８，４４０〜４４２の情報を所有する。ユーザプログラム４３２〜４３３，４３９に対応するプログラム構造体は省略してある。本発明では、複数の同一処理を行うプログラムが複数の計算機上で同時に実行され、処理を依頼する際の緊急度に応じて依頼先プログラムを決定する。図１７の実施例では、ユーザプログラム４３１〜４３３が同一処理を行うプログラム（プログラムＢ）であると仮定している。同様に、ユーザプログラム４３５〜４３６（プログラムＤ），ユーザプログラム４３８〜４３９（プログラムＦ）がそれぞれ同一処理を行うプログラムである。
【００９４】
プログラム選択手続き手段４１０はこれらのプログラムが動作している計算機，優先順位を管理し、最適な優先順位を有するプログラムの選択を行う。このための管理用データ構造として、プログラム位置データベース４２０を設ける。プログラム位置データベース４２０は、同一処理を行うプログラムの動作している計算機，優先順位を記憶するプログラム位置情報４７０〜４７９を管理する。プログラム位置情報にプログラムの通信アドレス等の情報を含め、処理依頼を容易にする管理方法もある。プログラム位置情報４７０〜４７９は同一処理を行うプログラム毎にプログラムリスト４２１〜４２６として管理される。例えば、プログラム位置情報４７１〜４７３は同一処理を行うプログラム（プログラムＢ）の位置情報であり、これらが纏めてプログラムリスト４２２として記憶される。なお、プログラムＡ，Ｃ，Ｅはそれぞれ一つずつのプログラムしか存在しないため、これらのプログラムリストをプログラム位置データベース４２０から削除して管理することも可能である。プログラム選択手続き手段４１０に登録されているプログラムの優先順位が各計算機で変更された場合や、該プログラムが存在しなくなった場合、および、登録すべきプログラムが新たに起動された場合には、それぞれのプログラムの動作している計算機，優先順位をプログラム選択手続き手段４１０に通知し、プログラム位置データベースの内容を変更させる。
【００９５】
次に、優先順位変換手続き手段２６０とプログラム選択手続き手段４１０を用いて、優先順位を用いた処理依頼先選択方法について示す。図１８がプログラム選択手法の一例である。本実施例では、ユーザプログラム４４０がプログラムＤ（ユーザプログラム４３５またはユーザプログラム４３６）に対して緊急度０で処理を依頼するものと仮定する。ユーザプログラム４４０は、第一に、プログラム選択手続き手段４１０に対し、緊急度０に対応するプログラムＤの位置を尋ねる（通信４８０）。プログラム選択手続き手段４１０は各プログラムの動作している計算機と優先順位とを認識しているが、緊急度を認識していないので、指定された緊急度０をそのまま優先順位変換手続き手段２６０に渡し(通信４８１)、その結果、緊急度０に対応する優先順位リスト４９０を得る（通信４８２）。優先順位リスト４９０の内容は、指定された緊急度に対応する各計算機の優先順位の範囲を示している。本実施例では、緊急度０に対して、計算機１００では優先順位０〜１の範囲に、計算機１０１では優先順位０に対応することを示す優先順位リストが通信４８２でプログラム選択手続き手段４１０に返される。プログラム選択手続き手段４１０では、プログラム位置データベース４２０の内容と優先順位リスト４９０の内容とを比較して、処理依頼先プログラムを決定する。図１８の例では、プログラムＤのプログラムリスト４２４の中で、優先順位リスト４９０で指定される優先順位に対応するプログラム位置情報は４７６（ユーザプログラム４３６に対応）のみである。したがって、計算機１０１に存在するユーザプログラム４３６が処理依頼先であると判断し、これをユーザプログラム440に通知する（通信４８３）。ユーザプログラム４４０は通信４８３で得られたユーザプログラム４３６に対して処理を依頼する（通信４８４）。なお、ここで、プログラム選択手続き手段４１０がユーザプログラム４４０からの通信４８０を、直接、ユーザプログラム４３６に対して送信するという通信仲介方法を採用することも可能である（通信４８５）。
【００９６】
次に、プログラム選択手続き手段４１０がプログラムリスト４２１〜４２６と優先順位リスト４９０との比較を行い、指定された優先順位の範囲内に存在するプログラムを見つける処理５００の一例を図１９に示す。第一に、指定されたプログラムリストが示す最初のプログラム位置情報を取り出す（処理５０１）。プログラム位置情報が空であれば（処理５０２による判定）、該当する範囲の優先順位のプログラムが存在しないと見なし、これを処理依頼元プログラムに通知する（処理５０３）。プログラム位置情報が空でなければ、該プログラム位置情報内に記憶されている計算機と一致するエントリを優先順位リスト４９０から取り出す（処理５０４）。処理５０４で得られた優先順位の範囲にプログラム位置情報内の優先順位が含まれていれば（処理５０５による判定）、該プログラムを処理依頼元プログラムに通知する（処理５０６）。処理５０５の判定によって、プログラムの優先順位が指定範囲外であると判断された場合、プログラムリストの次のプログラム位置情報を取り出して（処理５０７）、処理５０２から同じ手続きを繰り返す。処理５００を用いることにより、図１８の例では、第一に、プログラムＤに関するプログラムリスト４２４の最初のプログラム位置情報４７５と優先順位リスト４９０とを比較し、次に、第二のプログラム位置情報４７６と優先順位リスト４９０とを比較する。プログラム位置情報４７６の優先順位が優先順位リスト４９０の指定する範囲内に存在しているので、これが選択されて処理依頼元プログラムに通知されることになる。
【００９７】
本発明の第五の実施例を用いることにより、優先順位の異なった複数の同一処理を行うプログラムを分散処理システムの計算機上に分散させ、緊急性に応じた処理依頼の負荷分散を行うことができる。処理依頼は同一内容の処理を依頼する場合であっても、依頼元によって、その緊急性が異なる場合が多く、本実施例の効果が期待できる。
【００９８】
さらにまた、上記した第五の実施例によれば、該複数の同一処理を行うプログラムの優先順位を予め違ったレベルに設定しておくことにより、前記優先順位変更手続きを使用することなく、異なった緊急度で同一内容の処理を依頼することができ、第一の実施例と同程度のリアルタイム性保証を実現することができる。図２０に本発明の第六の実施例を示す。図２０の実施例は、各計算機に分散させて設けた優先順位変換手続き手段１４４〜１４５と、同一処理を行うプログラムが動作している計算機と緊急度とを記憶して処理依頼先を決定するプログラム選択手続き手段５１０を組み合わせて構築した分散処理システムである。図２０中、符号１００〜１０３，１１０，１４０〜１４５，１５０〜１５１は図１と同一である。計算機１００〜１０１のハードウェア詳細については省略してある。ユーザプログラム４３０〜４４２並びにプログラム構造体４５０〜４６２は、図１７と同一の内容を示している。ユーザプログラム４３２〜４３３，４３９に対応するプログラム構造体は省略してある。
【００９９】
プログラム選択手続き手段５１０はこれらのプログラムが動作している計算機，緊急度を管理し、最適な緊急度を有するプログラムの決定を行う。このための管理用データ構造として、プログラム位置データベース５２０を設ける。プログラム位置データベース５２０は、同一処理を行うプログラムの動作している計算機，緊急度を記憶するプログラム位置情報５３０〜５３９を管理する。プログラム位置情報５３０〜５３９はそれぞれ、同一処理を行うプログラム毎にプログラムリスト５２１〜５２６を構成する。図１７におけるプログラム位置情報４７０〜４７９は、プログラムの動作している計算機，優先順位を記憶するが、プログラム位置情報５３０〜５３９は優先順位の代わりに緊急度を記憶する。プログラム位置情報にプログラムの通信アドレス等の情報を含め、処理依頼を容易にする管理方法もある。プログラム選択手続き手段５１０に登録されているプログラムの緊急度が各計算機で変更された場合や、該プログラムが存在しなくなった場合、また、登録すべきプログラムが新たに起動された場合には、それぞれのプログラムの動作している計算機，緊急度をプログラム選択手続き手段５１０に通知し、プログラムリストの内容を変更させる。また、各計算機上での優先順位と緊急度との対応関係が変化した場合にも、優先順位変換手続き手段１４４〜１４５は対応関係の変化をプログラム選択手続き手段５１０に通知し、プログラム位置情報５２０〜５２９に記憶されている緊急度を変更させる。
【０１００】
図２０は、さらに、優先順位変換手続き手段１４４〜１４５としての優先順位対応表とプログラム選択手続き手段５１０を用いて、緊急度を用いた処理依頼先選択方法についても示している。図１８と同様、ユーザプログラム４４０がプログラムＤ（ユーザプログラム４３５またはユーザプログラム４３６）に対して処理を依頼するものと仮定する。ユーザプログラム４４０は、第一に、プログラム選択手続き手段５１０に対し、緊急度０に対応するプログラムＤの位置を尋ねる（通信５４０）。プログラム選択手続き手段５１０は各プログラムの動作している計算機と緊急度とを認識しているため、この時点で、プログラムＤかつ緊急度０という条件を満たすプログラムの位置を認識できる。本実施例では、二つのプログラムＤの内、プログラム位置情報５３６(ユーザプログラム４３６に対応)のみである。したがって、計算機１０１に存在するユーザプログラム４３６が処理依頼先であると判断し、これをユーザプログラム４４０に通知する(通信５４１)。ユーザプログラム４４０は通信５４１で得られたユーザプログラム４３６に対して処理を依頼する(通信５４２)。なお、ここで、プログラム選択手続き手段５１０がユーザプログラム４４０からの通信５４０を、直接、ユーザプログラム４３６に対して送信するという通信仲介方法を採用することも可能である（通信５４３）。
【０１０１】
本発明の第六の実施例は、前記第五の実施例の効果に加え、プログラム選択手続き手段５１０が優先順位変換手続き手段１４４〜１４５に対して緊急度から優先順位への変換を行わせないため、プログラム選択を前記第五の実施例に比べて高速化することができる。ただし、プログラム位置情報５３０〜５３９において緊急度を記憶するため、各計算機の負荷の変化等によって緊急度と優先順位との対応関係が変化した場合には、各プログラム位置情報の緊急度を変化させなければならない可能性がある。このため、各計算機上の負荷が時間によって大きく変化する場合には、前記第五の実施例に示した方式が有利となる。
【０１０２】
前記第五の実施例に示した方式，前記第六の実施例に示した方式の他に、プログラム選択手続き手段５１０と優先順位変換手続き手段２６０とを組み合わせて構築する方式，プログラム選択手続き手段４１０と優先順位変換手続き手段144〜１４５とを組み合わせて構築する方式を実現することは可能である。なお、図１７，図１８および図２０においてはプログラムの優先順位を変更して動作させることを考慮していないため、優先順位変更手続き手段１４６〜１４７を記述していないが、この手続きを追加して優先順位変更を行えるようにすることも可能である。
【０１０３】
複数の同一処理を行うプログラムを有した分散処理システムでは、処理を実行中のプログラムに対して、新たに処理が依頼された場合、新たに依頼された処理を別の同一処理を行うプログラムに転送すると、個々のプログラムを効率的に使用でき、また、新たな処理依頼を迅速に実行し、リアルタイム性の向上につながる。この処理依頼転送を行う第七の実施例を次に示す。図２１は、処理実行中のプログラムに対してさらに処理を依頼した場合に、該新たな処理を別の同一処理を行うプログラムに転送させる分散処理システムの構成を示している。図２１中、符号１００〜１０３，１１０，１４０〜１４３は図１と同一である。計算機１００〜１０１のハードウェア詳細については省略してある。優先順位変換手続き手段２６０および優先順位対応表２７０は図１０と同一の手続き，データ構造を使用する。符号４１０，４２０〜４２６，４３０〜４４２，４５０〜４６２並びに４７０〜４７９は、図１７と同一の内容を示している。ユーザプログラム４３２〜４３３，４３９に対応するプログラム構造体は省略してある。
【０１０４】
本実施例では、プログラム内部に処理転送手続き手段５５０および待ち行列５５１を設けることによって処理依頼を別プログラムに転送させることを可能とする。待ち行列５５１はプログラムに対して行われた処理依頼を順に記憶するバッファ記憶である。処理転送手続き手段５５０はプログラムが処理実行中に待ち行列に到着した処理依頼を監視し、該処理依頼を別プログラムに転送する。これにより、処理依頼をプログラム間で分散処理することができ、計算機の負荷を均等に分散化させることができる。通信５６０〜５６５の流れは、上記処理依頼の転送を行う際に、処理転送手続きによってどのように処理依頼が別プログラムに送られるかを示したものである。本実施例では、ユーザプログラム４４０がユーザプログラム４３８（プログラムＦの一つ）に対して緊急度１で処理依頼を行い（通信５６０）、これが別プログラムに転送される過程を例として示している。ユーザプログラム４３８が処理実行中に処理依頼が到着した場合、これらの処理依頼は待ち行列５５１に格納される。５５２〜５５３が処理依頼である。処理転送手続き手段５５０は新たな処理依頼５５３を受信すると、該処理依頼５５３に必要な緊急度１を有しているプログラムＦが別に存在するかどうかをプログラム選択手続き手段４１０に尋ねる（通信５６１）。プログラム選択手続き手段410は緊急度１を優先順位変換手続き手段２６０に通知して（通信５６２）、該緊急度１に対応する優先順位の範囲を示す優先順位リスト４９１を受け取る（通信５６３）。図２１中、優先順位リスト４９１の計算機１０１および１０２に対応するデータは省略している。優先順位リスト４９１とプログラムＦのプログラムリスト４２６とを比較することにより、必要な緊急度を満たすプログラム位置情報を選択する。このとき、プログラム選択手続き手段４１０はユーザプログラム４３８自身を表わすプログラム位置情報は選択しないようにする。図２１の例では、プログラム位置情報４７９（ユーザプログラム４３９に対応）が優先順位リスト４９１の示す優先順位の範囲に含まれ、該位置情報に対応するユーザプログラム４３９の位置を処理転送手続き手段５５０に通知する(通信５６４)。これを受けた処理転送手続き手段５５０がユーザプログラム４３９に対して、新たに到達した処理５５３を依頼することになる（通信５６５）。
【０１０５】
本発明の第七の実施例では、処理転送手続き手段５５０並びに待ち行列５５１をプログラム内部に配置したが、これをプログラム外部に配置し、複数のプログラムが共通に使用する手続き並びにデータ構造として実現することも可能である。また、本実施例では、プログラム選択手続き手段４１０と優先順位変換手続き手段２６０との組み合わせから構成される図１７の分散処理システムに処理転送手続き手段５５０を追加した構成である。しかし、プログラム選択手続き手段５１０と優先順位変換手続き手段１４４〜１４５との組み合わせから構成される図２０の分散処理システムに処理転送手続き手段５５０を追加しても同様の処理を行うことができる。
【０１０６】
本発明の第七の実施例を用いることにより、個々のプログラムに対して依頼された処理を他の同一緊急度を持つプログラムに転送することができ、特定のプログラムに対して処理が集中することなく、処理依頼を複数のプログラムで分散させることができる。さらにまた、新たに依頼された処理が、実行中の処理の完了を待つ必要がなく、リアルタイム性保証をさらに向上させることが可能となる。以上述べた本発明の第七の実施例には、別の実施例がある。第七の実施例は、処理実行中に新たな処理が依頼された場合、該新たな処理を別のプログラムに転送するというものであったが、該新たな処理を転送せず、処理を実行するプログラムにより高い緊急度を与え、実行中の処理と新たな処理をより迅速に処理させるという方式を採用することも可能である。この方式は、一つのプログラムに対して複数の処理が依頼された場合に、該処理依頼の数に応じて高い緊急度を与え、該複数の処理依頼全体としての望ましいリアルタイム性を保証するというものである。なお、この方式を採用するためには、優先順位変更手続き手段１４６〜１４７を各計算機上に配置させ、プログラムの優先順位を変更させる必要がある。
【０１０７】
（Ｂ）処理の時間制約を用いる場合
図１〜図２１に示した実施例は、全て分散処理システム全体に共通の概念である緊急度を設け、該緊急度を用いて各計算機での優先順位を統一的に管理する方法であった。緊急度を絶対的な数値に変更して、処理の時間制約を用いることができる。処理の時間制約を用いる場合、これを直接優先順位に変換することはできない。処理の時間制約は長くても処理量が大きい場合や、時間制約は短いが処理量も小さい場合が存在するため、時間制約と処理量から優先順位を決定する必要がある。図２２に、時間制約，処理量を用いて優先順位を統一的に管理するための分散処理システムの第八の実施例を示す。
【０１０８】
図２２中、符号１００〜１０１，１１０，１３０〜１３６，１４２〜１４３，１４６〜１４７は図１と同一である。計算機１００〜１０１のハードウェア詳細、および、計算機１０２〜１０３については省略してある。５７０〜５７１はプライオリティキューであり、各計算機での優先順位毎にプログラムの待ち行列を構成して実行順序管理を行う。プライオリティキューの構成要素はプログラム構造体であり、その一例が５９０〜５９６である。プログラム構造体５９０〜596は、そのデータ構造の一部として処理量データ６００を所有する。個々のプログラムの情報として該プログラムが実行する処理量を所有させることにより、時間制約，処理量を優先順位に変換する際の支援を行う。処理量として記憶する値には、例えば、以下のような値がある。
【０１０９】
（１）プログラムの実行命令数
（２）プログラムサイズ
（３）前回実行時の処理量（前回のプログラム実処理時間／計算機性能）
いずれも、単位は千命令等を使用する。実際に、上記の三つの例の内、最も望ましいものはプログラムの実行命令数であるが、これを計数することは非常に困難である。このため、プログラムの静的なサイズ，前回プログラム実行時にどれだけの処理量であったかを測定し、この値を処理量データ６００として記憶する。処理量データ６００の初期値としてプログラムサイズを記憶し、プログラムを一回実行するたびにどれだけの処理量であったかを処理量データ６００に記憶，更新することによって、プログラム実行命令数に対する良い近似とすることができる。
【０１１０】
５７２〜５７３は優先順位変換手続きである。優先順位変換手続き手段５７２〜５７３は、時間制約，処理量と計算機固有の優先順位との変換を行う手続きである。本実施例では、優先順位変換手続き手段５７２〜５７３内に優先順位対応表５８０〜５８１を設けている。優先順位対応表５８０〜５８１は単位処理量当たりの時間制約と優先順位との対応を示した表である。プログラムに与えられた時間制約をプログラムの処理量で正規化することにより単位処理量当たりの時間制約を計算することができる。本実施例では、計算機１００が優先順位０の場合に単位処理量を０.０１７ミリ秒で実行でき、優先順位２５５では２２.７７ミリ秒で実行できることを示す。これに対し、性能の低い計算機１０１では、同一優先順位でも単位処理量当たりの実行時間が長くなる。このため、例えば、優先順位０の場合には、単位処理量を０.０３４ ミリ秒で実行すると記憶されており、計算機１００の優先順位０に比べて単位処理量実行時間が長くなっている。また、優先順位対応表５８０〜５８１の内容は負荷に応じて変更され、負荷の重い計算機では同一時間制約が高い優先順位に対応するように設定する。優先順位変換手続き手段５７２〜５７３は、優先順位対応表５８０〜５８１を用いて、時間制約，処理量と優先順位との変換を行う。
【０１１１】
優先順位対応表５８０〜５８１は、図２２に示す配列構造で、そのまま、実現できる。これをＣ言語のプログラムで記述すると図２３に示す配列６１０になる。配列６１０を用いる場合、優先順位から単位処理量当たりの時間制約への変換は容易に行えるが、時間制約は連続量（浮動小数点数）なので、時間制約から優先順位への変換は２分探索等の工夫が必要となる。２分探索については、オーム社刊行の情報処理学会編「情報処理ハンドブック」，５８頁等に記載されているが、本実施例では、時間制約timelimitに対して、
to_time［p］＜＝timelimit＜to_time［ｐ＋１］
を満たすような優先順位ｐを与える必要がある。したがって、２分探索のアルゴリズムを変形して、図２４に示す手続き６２０の探索を行う。なお、手続き620はＣ言語で記述してあり、単位処理量当たりの時間制約を引数として、手続き６２０を呼び出すことにより、時間制約から優先順位への変換を行うことができる。単位処理量当たりの時間制約と優先順位との変換方法を纏めると、次のようになる。
【０１１２】
（１）優先順位から時間制約への変換：
timelimit←to_time［ｐ］
（２）時間制約から優先順位への変換：
ｐ←to_priority(timelimit)
なお、計算機の最高優先順位で実行しても時間制約を満たせない場合、処理依頼を拒絶することも可能である。
【０１１３】
図２２乃至図２４では、優先順位対応表５８０〜５８１を用いて時間制約，処理量と優先順位との変換を行うが、緊急度を用いる場合と同様に（図３参照）、これを計算式に置き換えることも可能である。
【０１１４】
次に、本実施例に示した優先順位変換手続き手段５７２〜５７３並びに優先順位変更手続き手段１４６〜１４７を用いて計算機間で時間制約を指定して処理を依頼する方式について説明する。緊急度指定を行う通信と同様に、処理の時間制約を指定して通信を行えば、リアルタイム分散処理システム構築を容易にすることができる。このため、本発明では、依頼元プログラムが処理依頼時に時間制約を指定できるようにする。図２５が本発明の時間制約指定方法をＣ言語で記述した一例である。６３０は処理依頼の先頭引数に時間制約を指定する方法、６３１が処理依頼の最終引数に時間制約を指定する方法である。前述のように優先順位を定めるためには時間制約と処理量とを決定する必要があるが、処理量については依頼先計算機のプログラム構造体の処理量データ６００を参照することにより決定することができるため、処理依頼時に時間制約のみを指定すれば良い。
【０１１５】
図２６に上記時間制約指定方法を用いた処理依頼の流れの概要を示した。符号１００〜１０１，１１０，１３０〜１３６，１４２〜１４３，１４６〜１４７は図１と同一である。計算機１０２〜１０３並びに計算機内の詳細は省略している。符号５７０〜５７３，５８０〜５８１，５９０〜５９６，６００は図２２と同一である。本実施例では、ユーザプログラム１３３がユーザプログラム１３６に処理を依頼する際の流れを示す。ユーザプログラム１３６の行うべき処理に関してユーザプログラム１３３が何らかの時間制約を課したい場合、時間制約指定通信６３０あるいは６３１を行う（通信６４０）。図２６では、時間制約を５ミリ秒であると仮定する。計算機１０１では、時間制約指定の通信を受信すると、該時間制約を計算機固有の優先順位に変換し、変換結果の優先順位でユーザプログラム１３６を実行させなければならない。ユーザプログラム１３６は５ミリ秒の時間制約を指定して、優先順位変更手続き手段１４７に優先順位の変更を依頼する(通信６４１)。優先順位変更手続き手段１４７は優先順位変換手続き手段573に時間制約から優先順位への変換を依頼する（通信６４２）。優先順位変換手続き手段５７３はユーザプログラム１３６に対応するプログラム構造体５９６から処理量データ６００を取り出し（処理６４３）、該処理量と時間制約から優先順位を決定する。ここで、ユーザプログラム１３６の処理量が６４千命令であるとする。このとき、時間制約５ミリ秒と処理量６４千命令から、単位処理量当たりの時間制約として、０.７８ミリ秒を得ることができる（計算６４４)。優先順位対応表５８１を使用することにより、計算６４４で得られた数値に対応する優先順位は１であることが判る。優先順位変換手続き手段５７３は変換結果として、優先順位１を優先順位変更手続き手段１４７に通知し、ユーザプログラム１３６が優先順位１で実行されなければならないことを知らせる（通信６４５）。最後に、優先順位変更手続き手段１４７はプライオリティキュー５７１内のプログラム構造体５９６を優先順位１の待ち行列に繋ぎ換えさせる（通信６４６）。
【０１１６】
これにより、異なる計算機上に存在するプログラムの優先順位を時間制約という共通の概念で統一的に管理することが可能となる。なお、緊急度を使用した分散処理システムと同様に、ユーザプログラム１３３が優先順位変換手続き手段５７２に自己の優先順位４と処理量とから時間制約を計算させ、該時間制約を指定して処理依頼６４０を行うことは可能である。
【０１１７】
緊急度を用いて分散処理システムの各計算機の優先順位を管理する場合と同様、時間制約を用いる場合にも、負荷の増減によって優先順位対応表の内容を変更することができる。時間制約と優先順位との対応表を変更する方法として、次の二つの方式を例として説明する。
【０１１８】
（１）負荷に比例して優先順位対応表の時間制約を変更する方式
（２）実際に実行した時間と時間制約の差を用いて優先順位対応表の時間制約を変更する方式
図２７に第一の優先順位対応表変更方式６５０を示す。前回優先順位対応表を変更した時点の負荷量を前負荷量、その後の負荷の変化量を総負荷変化量と呼ぶ。方式６５０は負荷が変化した場合、総負荷変化量に今回変化した負荷量を足し込み（処理６５１）、この結果、総負荷変化量が増減に拘らず一定値以上（総負荷変化量の絶対値が一定値以上）となるかどうかを判定する（処理６５２）。一定値以上であれば、前負荷量と現在の負荷量との比によって優先順位対応表の時間制約の補正を行う（処理６５３）。優先順位対応表の内容を変更した場合には、最後に、総負荷変化量に０を設定、および、前負荷量に現在の負荷量を設定し（処理６５４）、再び負荷変化量の計数を開始する。
【０１１９】
処理６５３で前負荷量と現在の負荷量との比によって優先順位対応表の調節を行う意味を図２８に示した。優先順位対応表５８０が負荷量５０（実行可能プログラム数５０）を有していると仮定し、負荷が１０増減する毎に優先順位対応表５８０の変更を行うものと仮定している。負荷が１０増加した場合、優先順位対応表は６６０に示すように変化する。これは、変化前の負荷量５０と変化時点の負荷量６０の比を優先順位対応表の時間制約に各々掛け合わせたものとなる。同様に、負荷が１０減少した場合には、各々の時間制約に前負荷量５０と現在の負荷量４０の比を掛け合わせた優先順位対応表６６１を得ることができる。これにより、負荷が高い場合には、同じ優先順位に対応する時間制約が長くなり（処理完了に時間を要する）、負荷が低い場合には、時間制約を短くする（処理が速く完了する）ことができる。
【０１２０】
次に、第二の優先順位対応表変更方式を再度図２６を用いて説明する。第二の変更方式では、優先順位を１に変更してユーザプログラム１３６を実行した後、優先順位変換手続き手段５７３がユーザプログラム１３６の実際の処理時間を受け取る(通信６４７）。図２６の例では、実際の処理時間が３.４７ミリ秒であると仮定している。このとき、単位処理量当たりの実行時間が３.４７／６４＝   ０.５４ ミリ秒と計算できる（計算６４８）。この値をそのまま、優先順位１に対応する時間制約として記憶することにより、優先順位対応表５８１の補正を行うことができる（処理６４９）。なお、実際に補正を行う場合には、上記の計算値０.５４ ミリ秒に一定値（例えば、０.１ ミリ秒）を加え、安全区間を設けておくほうがよい。
【０１２１】
以上に、時間制約を用いて分散処理システムの各計算機上の優先順位を統一的に管理する第八の実施例を示した。本実施例によれば、時間制約を用いて、分散処理システム内の性能，負荷および機種の異なる複数の計算機の優先順位を統一的に管理することができる。時間制約を指定して処理依頼を行うだけで、該時間制約が各計算機の性能，負荷に応じて各計算機の優先順位に変換されるため、リアルタイム分散処理システムを容易に構築することが可能となる。
【０１２２】
さらに、本実施例によれば、各計算機の性能と負荷に応じて、処理の時間制約，処理量を個々の計算機の優先順位に変換して実行させるため、新たに発生した時間制約の短い処理を、既に割り付けられている時間制約の長い処理に先んじて実行させるといったことが可能となり、複数の計算機を効率的に利用しつつ、より厳密にリアルタイム処理を実現することが可能となる。
【０１２３】
本実施例では、さらに、優先順位対応表の内容変更を行うことができ、これにより、各計算機での動的な負荷変化に対応しつつ優先順位管理を行うことが可能となる。
【０１２４】
本実施例では、さらに、計算機間に跨る処理依頼において、処理の重要度に応じた時間制約を指定することができ、かつ、時間制約を指定する際には、相手計算機の性能，負荷および機種を知る必要がない。
【０１２５】
なお、本実施例では、計算機の負荷を実行可能状態にあるプログラムの数で表現したが、実行可能状態にあるプログラムの処理量または処理予測時間の和で表現する方式もある。これにより、計算機の負荷計算がより正確となり、より厳密なリアルタイム性保証を行うことができる。また、本実施例では、各計算機の負荷と性能の両者を考慮して優先順位を決定しているが、いずれか一方のみを考慮して決定することもできる。特に、分散処理システムが同一計算機から構成される場合、負荷のみを考慮すればよく、時間制約と優先順位との変換を効率的に行うことができる。
【０１２６】
時間制約を用いて分散処理システムの各計算機の優先順位管理を行う際に、計算機間の通信時間を考慮するとさらに精密な優先順位管理を行うことができる。図２９に、計算機間の通信時間を考慮した本発明の第九の実施例を示す。符号１００〜１０１，１１０，１３０〜１３６，１４２〜１４３，１４６〜１４７は図１と同一である。計算機１０２〜１０３並びに計算機内の詳細は省略している。符号５７０〜５７３，５８０〜５８１，５９０〜５９６，６００は図２２と同一である。通信６４１〜６４２および６４５〜６４６における時間制約と優先順位の変換過程は図２６と同一である。
【０１２７】
本実施例では、計算機間の通信時間を予測する通信時間予測手続き手段６７０〜６７１を設ける。通信時間予測手続き手段６７０〜６７１は優先順位変換手続き手段５７２〜５７３，優先順位変更手続き手段１４６〜１４７等とは独立に動作する。通信時間予測手続き手段６７０〜６７１は、内部に通信時間表６８０〜６８１を有し、計算機の番号が与えられると、該計算機と自己の計算機との通信時間を出力する。通信時間表６８０〜６８１の設定方式として、例えば、次の二つのいずれかの方法を採用するとよい。
【０１２８】
（１）計算機立上げ時に他全ての計算機と通信を行い、該通信の実行時間を記憶する。
【０１２９】
（２）通信時間予測要求があるまで通信時間表の設定は行わない。最初に通信時間予測要求があった時点で、要求された計算機と通信を行い、該通信の実行時間を記憶する。
【０１３０】
図２９は、通信時間予測手続き手段６７０〜６７１を用いて処理依頼を行う場合の通信の流れも示している。図２６と同様、ユーザプログラム１３３がユーザプログラム１３６に対して時間制約を指定して処理を依頼する例を示す。ユーザプログラム１３３はユーザプログラム１３６の行うべき処理に関して８.１４ ミリ秒の時間制約を課したいとする。このとき、ユーザプログラム１３３は図２５の６３０あるいは６３１に示した形式で時間制約指定通信６９０を行う。このとき、ユーザプログラム１３３から見れば、計算機間通信に要する時間も含めて時間制約を課したと見なしている。すなわち、この時間制約８.１４ ミリ秒から計算機間通信に要する時間を差し引くことにより、ユーザプログラム１３６から見た時間制約を得ることができる。ユーザプログラム１３６は通信時間予測手続き手段６７１に対して、計算機１００との通信時間を尋ねる（通信６９１）。これに対して通信時間予測手続き手段６７１は通信時間表６８１を参照し、指定された計算機との通信時間を返答する（通信６９２）。図２９に示した数値例では、計算機１００との通信時間は１.５７ ミリ秒である。ユーザプログラム１３６はこの通信時間を差し引くことにより、自己に課せられた時間制約を知ることができる。ここでは、８.１４ ミリ秒から、通信時間１.５７×２＝３.１４ミリ秒（処理依頼と結果返却とにそれぞれ通信時間を要するものとする）を差し引いた５ミリ秒を時間制約として得ることになる。以降の処理は、図２６と同様である。
【０１３１】
なお、ここでは、処理依頼先プログラムが通信時間を差し引く方法を示したが、処理依頼元プログラムが予め通信時間予測手続き手段６７０に通信時間を尋ね、該通信時間を差し引いておく方法もある。
【０１３２】
上記した第九の実施例を用いることにより、前記第八の実施例で用いる時間制約をさらに正確なものに変換し、使用することができる。特に、計算機間の通信時間が大きく、無視できない場合に有効である。
【０１３３】
なお、第八および第九の実施例において、優先順位変換手続き手段５７２〜５７３を各計算機に分散配置する実施例を示したが、図１０と同様、優先順位変換手続きを一つの計算機上に纏めて配置することは可能である。
【０１３４】
次に、時間制約を用いて、個々のプログラムの重要性を加味した負荷分散を行うための実施例（第十の実施例）を説明する。第十の実施例では、時間制約を指標として負荷分散を行うことにより、一つの計算機に時間制約の短いプログラムが集中するといったことを避けることができる。図３０に本実施例の構成図を示す。符号１００〜１０１，１１０，１３０〜１３６，１４２〜１４３，１４６〜１４７は図１と同一であり、その動作も同様である。計算機１０２〜１０３および計算機内部の詳細は省略している。また符号１３７，２９０〜２９１は図１１と同一、符号２９６〜２９９，３３０〜３３１，３３４〜３３５は図１６と同一であり、その動作も同様である。プライオリティキュー５７０〜５７１，優先順位変換手続き手段５７２〜５７３，優先順位対応表５８０〜５８１，プログラム構造体５９０〜５９６，処理量データ６００は図２２と同一である。また、ユーザプログラム１３７はプログラム構造体５９７によって管理されている。
【０１３５】
計算機情報３３０〜３３１は、それぞれ、計算機負荷情報３７０〜３７１と計算機性能情報３３４〜３３５とから成る。計算機負荷情報３７０〜３７１は各計算機の負荷を単位処理量当たりの時間制約毎に記憶したものである。本実施例では、計算機負荷情報中の単位処理量当たりの時間制約の区切りを等間隔に設定していないが、これを等間隔に設定し、負荷分散処理を容易にすることは可能である。
【０１３６】
本実施例の動作を図３０乃至図３４を用いて説明する。まず、新たにプログラムを起動する場合の処理について説明する。プログラムの起動は、例えば、ユーザがプログラムの実行可能ファイル名と時間制約とを指定したコマンドを入力すると、オペレーティングシステムがそのコマンドを解析し、オペレーティングシステム中のプログラム実行・移動手続き手段２９０〜２９１にプログラム起動を依頼することにより可能となる。ここでは時間制約５０ミリ秒のプログラムの起動コマンドが計算機１００で入力され、プログラム実行・移動手続き手段２９０がプログラムの起動処理を行う場合について、以下説明する。
【０１３７】
プログラム起動処理３４０の動作を図３１により説明する。まず、プログラム実行・移動手続き手段２９０が計算機選択手続き手段２９８に依頼して、新たに起動されるプログラムが計算機負荷情報中、どの時間制約間隔に含まれるかを決定する（処理３４１）。例えば、プログラムの処理量が１２８千命令と見積もられると仮定すると、単位処理量当たりの時間制約は５０／１２８＝０.３９ ミリ秒である。計算機負荷情報３７０〜３７１で時間制約０.３９ ミリ秒を含む時間制約間隔は０.０５〜１.００の範囲に当たる。次に、全ての計算機上の計算機選択手続き手段２９８〜２９９に依頼して、単位処理量当たりの時間制約の範囲が０ミリ秒から処理３４１で決定した範囲までの負荷／性能値を算出させる（処理３４２）。算出は図３０に示した計算機負荷情報３７０〜３７１と計算機性能情報３３４〜３３５を読み出して行う。図３０の状態の各計算機の負荷情報，負荷量，負荷／性能値を図３２に示す。計算機負荷情報３７０〜３７１は単位処理量当たりの時間制約ごとの実行可能状態のプログラム数を表わしているが、時間制約０ミリ秒から特定の時間制約の範囲に含まれる実行可能状態のプログラム数が負荷量３８０〜３８１であり、これを計算機の性能で割ったものが負荷／性能値３８２〜３８３である。ここでは新たに起動するプログラムが時間制約０.３９ ミリ秒の場合について考えているので、この値を含む最小の時間制約範囲０〜１ミリ秒の負荷／性能値を算出すると、計算機１００の負荷／性能値は１.１０ ，計算機１０１の負荷／性能値は０.６７となる。
【０１３８】
次に、計算機選択手続き手段２９８〜２９９は互いに通信しあって、最も負荷／性能値が低い計算機を、起動すべきプログラムを実行する計算機として選択する（処理３４３）。図３２では計算機１０２以降については省略しているが、計算機１０１の負荷／性能値０.６７ が最も小さいとすると、計算機１０１が選択される。最後にプログラム実行・移動手続きは、選択した計算機でプログラムを起動する処理を行う（処理３４４）。これは、プログラム起動処理を開始した計算機のプログラム実行・移動手続きが、選択した計算機のプログラム実行・移動手続きに、プログラムを実行可能状態にするよう依頼することにより行う。この場合、計算機１００のプログラム実行・移動手続き手段２９０が、計算機１０１内のプログラム実行・移動手続き手段２９１に対して、通信を行い、プログラムを実行可能状態にするよう依頼する。
【０１３９】
次に、実行可能状態のプログラムを移動する処理について説明する。本実施例では、プログラム移動決定手続き手段２９６〜２９７が定期的に起動され、互いに通信しあって各計算機の負荷を確認し、各計算機の負荷が性能に見合って均等に分散されていない場合、均等になるようにプログラムを移動することを決定し、プログラム実行・移動手続き手段２９０〜２９１に移動を依頼する。プログラム実行・移動手続き手段２９０〜２９１は、計算機選択手続き手段２９８〜299に依頼して、移動先の計算機を決定し、移動先の計算機のプログラム実行・移動手続きと協調して、プログラムの移動処理を行う。本実施例では計算機の負荷が性能に見合って均等であるかどうかを判定するための値として、前述の負荷／性能値を用いる。
【０１４０】
プログラム移動処理３５０の動作を図３３を用いて説明する。まず、プログラム移動決定手続きは時間制約の範囲を表わす変数に０.０５ ミリ秒を代入する（処理３５１）。この値は、計算機負荷情報３７０〜３７１において、単位処理量当たりの時間制約が最も小さくなる範囲の上限値である。そして、時間制約範囲が０からｔミリ秒までについて、各計算機の負荷／性能値を算出する（処理３５２）。前述のように図３０の状態の負荷／性能値の値は図３２の負荷／性能値３８２〜３８３のようになる。次に全ての計算機のうち、該時間制約範囲の最大の負荷／性能値と最小の負荷／性能値の差Ｄを算出する(処理３５３)。図３２では計算機１０２以降については省略しているが、ｔが０.０５ ミリ秒の場合、計算機１０１の負荷／性能値０.３３ が最も大きく、計算機１００の負荷／性能値０.３０が最も小さいとすると、Ｄの値は０.０３となる。このＤの値が閾値Ｄｔを越えているかどうかを調べる（処理３５４）。本実施例では閾値Ｄｔとして０.３ という値を用いるものとする。Ｄの値が閾値Ｄｔを越えている場合には処理３５５に移り、越えていない場合には処理３５８に移る。ここでは、ｎが０の場合にはＤの値はＤｔを越えていないので、処理３５８に移り、ｔの値が時間制約範囲の最大値（図３０の例では、２００ミリ秒）であるか否かを判定する。ｔの値が時間制約範囲の最大値であれば処理を終了し、最大値でなければ、処理３５９に移行し、変数ｔに次の時間制約範囲の上限を代入する。ここではｔが０.０５ ミリ秒なので、処理３５９に移行して１ミリ秒を代入することになる。
ここで処理３５２に戻り、各計算機の負荷／性能値を算出し、次に処理３５３でＤの値を算出する。図３２では計算機１０２以降については省略しているが、ｔが１ミリ秒の場合、計算機１００の負荷／性能値１.１０ が最も大きく、計算機１０１の負荷／性能値０.６７が最も小さいとすると、Ｄの値は０.４３となる。したがってｔが１ミリ秒の時、Ｄの値は閾値Ｄｔを越えている。Ｄの値が閾値Ｄｔを越えている場合には負荷が均等ではないものと判定し、移動すべきプログラムを決定する（処理３５５）。本実施例では、負荷／性能値が最大の計算機の、単位処理量当たりの時間制約ｔミリ秒以下に対応する実行可能状態のプログラムのうち、プライオリティキューにおける実行順位が最後尾のプログラムを選択することとする。この場合、図３０に示したように、計算機１００の時間制約０.０５ 〜１ミリ秒に対応する優先順位は２〜４であり、そのうち実行順位が最後尾なのはＫ（プログラム構造５９７）なので、これを移動対象プログラムとする。
【０１４１】
移動対象プログラムが決定したら、移動対象プログラムが存在する計算機のプログラム移動決定手続きは、同一計算機上のプログラム実行・移動手続きに、移動対象プログラムの移動処理を依頼する。この場合は計算機１００のプログラム実行・移動手続き手段２９０がプログラム移動処理を行う。まず、プログラム実行・移動手続き手段２９０は計算機選択手続き手段２９８に依頼して、移動対象プログラムの移動先の計算機を選択する(処理３５６)。計算機選択手続き手段２９８は他の計算機上の計算機選択手続きと通信しあって移動先計算機を決定する。本実施例では負荷／性能値が最小の計算機を移動先とする。したがってこの場合、ｔが１ミリ秒の場合の最小負荷／性能値の計算機１０１を移動先とする。移動先が決定したらプログラム実行・移動手続きがプログラム移動処理を実行する（処理３５７）。この場合、計算機１００のプログラム実行・移動手続き手段２９０は、プログラム移動先計算機１０１のプログラム実行・移動手続き手段２９１と協調して、プログラム移動処理を実行する。プログラムの移動が行われると、それによる計算機の負荷の状態は計算機負荷情報３７０〜３７１に反映される。この場合、計算機負荷情報３７０〜３７１は図３４に示すように、単位処理量当たりの時間制約０.０５ 〜１ミリ秒の実行可能状態のプログラムの数が、計算機１００では７，計算機１０１では２になる。
【０１４２】
このようにして、プログラムの移動が行われると、処理３５２に戻り、もう一度各計算機の負荷性能値を算出する。この場合には図３４に示すような負荷量３８０〜３８１、および負荷／性能値３８２〜３８３になる。図３４では計算機１０２以降については省略しているが、ｔが１ミリ秒の場合、まだＤの値がＤｔを越えている場合には、さきほどと同様にプログラムの移動処理を行う。Ｄの値がＤｔ以下となったとすると、処理３５８に移る。
【０１４３】
以上述べた処理をｔの値が時間制約範囲の最大値となるまで行うことにより、全ての時間制約範囲について、負荷分散、すなわち計算機性能に見合った負荷の均等化のためのプログラム移動が行われる。
【０１４４】
以上、本発明の第十の実施例について説明した。本実施例によれば、計算機の負荷が各計算機の性能に見合って均等にユーザプログラムを割り当てることができ、計算機資源を有効に活用できるという効果がある。ここで、本実施例では、計算機の負荷量と性能の両者を考慮して、負荷の均等性の評価を行っており、計算機の性能が変化しても、負荷の評価を平等に行えるという効果がある。
【０１４５】
また、本実施例によれば、プログラムの各時間制約範囲において、各計算機の性能に見合って均等にユーザプログラムを割り当てることができ、分散処理システム全体で統一的な時間制約によってリアルタイム処理が可能になるという効果がある。特に、プログラムの時間制約を考慮して負荷分散を行うため、一つの計算機に時間制約の短い処理が集中することがなくなり、より厳密なリアルタイム性保証を行うことができる。
【０１４６】
なお、図３０〜図３４では、優先順位変換手続き手段５７２〜５７３，計算機選択手続き手段２９８〜２９９，計算機情報３３０〜３３１を各計算機に分散させた構成を採用しているが、これを一つの計算機に配置し、集中管理させることは可能である。
【０１４７】
図１７〜図２１では、複数の同一処理を行うプログラムを複数の計算機上で動作させ、緊急度を指定して処理依頼を行うことにより、該同一処理を行うプログラムの中から依頼元プログラムに望ましい優先順位を有するプログラムを選択する方法を示した。次に、時間制約を用いてこのプログラム選択処理を行う本発明の第十一の実施例について示す。図３５に時間制約を用いて処理依頼を分散させるための実施例を示す。図３５は図１７に示した分散処理システムにおいて、緊急度の代わりに時間制約を用いる方法である。図３５中、符号１００〜１０３，１１０，１４０〜１４３は図１と同一である。計算機１００〜１０１のハードウェア詳細については省略してある。符号４３０〜４４２，４５０〜４５１，454〜４５８，４６０〜４６２，４７０〜４７９は図１７と同一である。優先順位変換手続き手段７２０および優先順位対応表７３０は図２２における優先順位変換手続き手段５７２〜５７３および優先順位対応表５８０〜５８１を纏めて一つの手続き、データ構造で管理するように変更したものである。優先順位変換手続き手段７２０は図２４に示した変換手続き手段６２０を使用することにより、指定された時間制約に対する各計算機上での優先順位を求めることができる。
【０１４８】
７００はプログラム選択手続き手段であり、指定された時間制約を用いて依頼元に最適なプログラムを選択する。このための管理用データ構造として、プログラム位置データベース７１０を設ける。プログラム位置データベース７１０は、同一処理を行うプログラムの動作している計算機，優先順位を記憶するプログラム位置情報４７０〜４７９を管理する。プログラム位置情報４７０〜４７９は同一処理を行うプログラム毎にプログラムリスト７１１〜７１６として管理される。本実施例では、プログラムリスト７１１〜７１６自体が図２２で示した該プログラムの処理量データ６００を記憶するものとしている。これにより、指定された時間制約とプログラムリスト７１１〜７１６で指定される処理量データ６００とから単位処理量当たりの時間制約を導き出すことができる。なお、図２２と同様に、処理量データ６００をプログラム構造体内に記憶させ、優先順位変換手続き手段７２０が処理量データ６００を読み出して単位処理量当たりの時間制約を導出することも可能である。プログラム選択手続き手段７００に登録されているプログラムの優先順位が各計算機で変更された場合や、該プログラムが存在しなくなった場合、および、登録すべきプログラムが新たに起動された場合には、それぞれのプログラムの動作している計算機，優先順位をプログラム選択手続き手段７００に通知し、プログラム位置データベースの内容を変更させる。
【０１４９】
次に、優先順位変換手続き手段７２０とプログラム選択手続き手段７００を用いて、時間制約を用いた処理依頼先選択方法について示す。図３６がプログラム選択手法の一例である。本実施例では、ユーザプログラム４４０がプログラムＤ（ユーザプログラム４３５またはユーザプログラム４３６）に対して処理を依頼するものと仮定する。ユーザプログラム４４０は、第一に、プログラム選択手続き手段７００に対し、時間制約５ミリ秒を満たすプログラムＤの位置を尋ねる（通信７５０）。プログラム選択手続き手段７００はプログラムＤに関するプログラムリスト７１４から処理量データ６００を取り出す（処理７５１）。ここで、プログラムＤの処理量が１２８千命令であったと仮定する。与えられた時間制約と処理量データ６００から、単位処理量当たりの時間制約は、５.００／128＝０.０３９ ミリ秒であると計算することができる（計算７５２）。プログラム選択手続き手段７００は計算７５２で得た結果を優先順位変換手続き手段７２０に通知し、優先順位への変換を依頼する(通信７５３)。優先順位変換手続き手段７２０は図２４に示す手続き６２０を実行することにより、時間制約０.０３９ ミリ秒に対応する各計算機の優先順位を決定し、これを優先順位リスト４９２として、プログラム選択手続き手段７００に通知する（通信７５４）。優先順位リスト４９２の内容は、指定された時間制約に対応する各計算機の優先順位を示している。本実施例では、時間制約０.０３９ ミリ秒が計算機１００では優先順位１に、計算機１０１では優先順位０に対応することを示す優先順位リストが通信７５４でプログラム選択手続き手段７００に返される。プログラム選択手続き手段７００では、プログラム位置データベース７１０の内容と優先順位リスト492の内容とを比較して、処理依頼先プログラムを決定する。プログラムリスト711〜７１６と優先順位リスト４９２との比較を行い、指定された優先順位の範囲内に存在するプログラムを見つけるためには図１９の処理５００を使用すれば良い。図３６の実施例では、プログラムＤのプログラムリスト７１４の中で、優先順位リスト４９２で指定される範囲の優先順位に対応するプログラム位置情報は４７６(ユーザプログラム４３６に対応)のみである。したがって、計算機１０１に存在するユーザプログラム４３６が処理依頼先であると判断し、これをユーザプログラム４４０に通知する（通信７５５）。ユーザプログラム４４０は通信７５５で得られたプログラム４３６に対して処理を依頼する（通信７５６）。なお、ここで、プログラム選択手続き手段７００がユーザプログラム４４０からの通信７５０を、直接、ユーザプログラム４３６に対して送信するという通信仲介方法を採用することも可能である（通信７５７）。
【０１５０】
本発明の第十一の実施例を用いることにより、優先順位の異なった複数の同一処理を行うプログラムを分散処理システムの計算機上に分散させ、時間制約に応じた処理依頼の負荷分散を行うことができる。処理依頼は同一内容の処理を依頼する場合であっても、依頼元によって、その時間制約が異なる場合が多く、本実施例の効果が期待できる。
【０１５１】
さらにまた、本第十一の実施例によれば、該複数の同一処理を行うプログラムの優先順位を予め違ったレベルに設定しておくことにより、前記優先順位変更手続きを使用することなく、異なった時間制約で同一内容の処理を依頼することができ、第八の実施例と同程度のリアルタイム性保証を実現することができる。
【０１５２】
図３７に前述のプログラム選択を行うためのさらに別の実施例である第十二の実施例を示す。図３７の実施例は、各計算機に分散させて設けた優先順位変換手続き手段５７２〜５７３と、同一処理を行うプログラムが動作している計算機と時間制約とを記憶して処理依頼先を決定するプログラム選択手続き手段７６０を組み合わせて構築した分散処理システムである。図３７中、符号１００〜１０３，１１０，１４０〜１４３は図１と同一である。計算機１００〜１０１のハードウェア詳細については省略してある。ユーザプログラム４３０〜４４２並びにプログラム構造体４５０〜４６２は、図１７と同一の内容を示している。ユーザプログラム４３２〜４３３，４３９に対応するプログラム構造体は省略してある。優先順位変換手続き手段５７２〜５７３，優先順位対応表５８０〜５８１，処理量データ６００は図２２と同一の手続き，データ構造である。
【０１５３】
プログラム選択手続き手段７６０はこれらのプログラムが動作している計算機，時間制約を管理し、最適な時間制約を有するプログラムの決定を行う。このための管理用データ構造として、プログラム位置データベース７７０を設ける。プログラム位置データベース７７０は、同一処理を行うプログラムの動作している計算機，時間制約（この場合、時間制約は処理予測時間の意味合いが強い）を記憶するプログラム位置情報７８０〜７８９を管理する。プログラム位置情報780〜７８９はそれぞれ、同一処理を行うプログラム毎にプログラムリスト７７１〜７７６を構成する。図３５におけるプログラム位置情報４７０〜４７９は、プログラムの動作している計算機，優先順位を記憶するが、プログラム位置情報780〜７８９は優先順位の代わりに時間制約を記憶する。時間制約は、プログラムの優先順位に対応する単位処理量当たりの時間制約にプログラムの処理量を掛け合わせることによって得ることができる。例えば、ユーザプログラム４３６（プログラムＤ）は計算機１０１の優先順位０で動作している。プログラムＤの処理量が128千命令であると仮定すると、その時間制約は、０.０３４×１２８＝4.35ミリ秒となる。この値がプログラム位置情報７８６（ユーザプログラム４３６に対応する位置情報）に記憶されている。プログラム選択手続き手段７６０に登録されているプログラムの処理量が各計算機で変更された場合や、該プログラムが存在しなくなった場合、また、登録すべきプログラムが新たに起動された場合には、それぞれのプログラムの動作している計算機，単位処理量当たりの時間制約をプログラム選択手続き手段７６０に通知し、プログラムリストの内容を変更させる。また、各計算機上での優先順位と時間制約との対応関係が変化した場合にも、優先順位変換手続き手段５７２〜５７３は対応関係の変化をプログラム選択手続き手段７６０に通知し、プログラム位置情報７８０〜７８９に記憶されている時間制約を変更させる。
【０１５４】
図３７は、さらに、優先順位変換手続き手段５７２〜５７３とプログラム選択手続き手段７６０を用いて、時間制約を用いた処理依頼先選択方法についても示している。図３６と同様、ユーザプログラム４４０がプログラムＤ（ユーザプログラム４３５またはユーザプログラム４３６）に対して処理を依頼するものと仮定する。ユーザプログラム４４０は、第一に、プログラム選択手続き手段７６０に対し、時間制約５ミリ秒に対応するプログラムＤの位置を尋ねる(通信７９０)。プログラム選択手続き手段７６０は各プログラムの動作している計算機と時間制約とを認識しているため、この時点で、プログラムＤかつ時間制約５ミリ秒以下という条件を満たすプログラムの位置を認識できる。本実施例では、二つのプログラムＤの内、プログラム位置情報７８６（ユーザプログラム４３６に対応）のみである。したがって、計算機１０１に存在するユーザプログラム４３６が処理依頼先であると判断し、これをユーザプログラム４４０に通知する（通信791)。ユーザプログラム４４０は通信７９１で得られたユーザプログラム４３６に対して処理を依頼する（通信７９２）。なお、ここで、プログラム選択手続き手段７６０がユーザプログラム４４０からの通信７９０を、直接、ユーザプログラム４３６に対して送信するという通信仲介方法を採用することも可能である（通信７９３）。
【０１５５】
本発明の第十二の実施例は、第十一の実施例の効果に加え、さらに、プログラム選択手続き手段７６０が優先順位変換手続き手段５７２〜５７３に対して時間制約から優先順位への変換を行わせないため、プログラム選択を図３５〜図３６に示した方式に比べて高速化することができる。ただし、プログラム位置情報７８０〜７８９において時間制約を記憶するため、各計算機の負荷の変化等によって時間制約と優先順位との対応関係が変化した場合、各プログラム位置情報の時間制約を変化させなければならない可能性がある。このため、各計算機上の負荷が時間によって大きく変化する場合には、図３５〜図３６に示した方式が有利となる。
【０１５６】
図３５〜図３６に示した方式，図３７に示した方式の他に、プログラム選択手続き手段７６０と優先順位変換手続き手段７２０とを組み合わせて構築する方式，プログラム選択手続き手段７００と優先順位変換手続き手段５７２〜５７３とを組み合わせて構築する方式を実現することは可能である。なお、図３５乃至図３７においてはプログラムの優先順位を変更して動作させることを考慮していないため、優先順位変更手続き手段１４６〜１４７を記述していないが、この手続きを追加して優先順位変更を行えるようにすることも可能である。
【０１５７】
最後に、図２１に示した分散処理システムと同様、時間制約を使用して、一つのプログラムに対して依頼された処理を別の同一処理を行うプログラムに対して転送する本発明の第十三の実施例を図３８に示す。図３８中、符号１００〜103,１１０，１４０〜１４３は図１と同一である。計算機１００〜１０１のハードウェア詳細については省略してある。優先順位変換手続き手段５７２〜５７３および優先順位対応表５８０〜５８１，処理量データ６００は図２２と同一の手続き，データ構造を使用する。ユーザプログラム４３０〜４４２，プログラム構造体４５０〜４６２は、図１７と同一の内容を示している。ユーザプログラム４３２〜４３３，４３９に対応するプログラム構造体は省略してある。また、符号760,７７０〜７７６，７８０〜７８９は図３７と同一である。ユーザプログラム438内に記述されている処理転送手続き手段５５０，待ち行列５５１，処理依頼552〜５５３は図２１と同一である。
【０１５８】
時間制約を使用する場合には、依頼された処理を別のプログラムに転送する条件として以下の２種類を代表例として挙げることができる。
【０１５９】
（１）処理実行中に新たに処理が依頼された場合。
【０１６０】
（２）現在実行中の処理が時間制約内に間に合わないと認識した場合。
【０１６１】
前者については、図２１と同様にして、処理転送手続き手段５５０および待ち行列５５１によって処理依頼を別プログラムに転送させることができる。ただし、この場合の相違点として、処理転送手続き手段５５０はプログラム選択手続き手段７６０に時間制約を指定する。
【０１６２】
後者の場合の処理転送は、プログラム内に処理時間予測手続き手段８００および時間制約設定手続き手段８０２を設けることによって達成することができる。処理時間予測手続き手段８００は現在実行中の処理が完了するまでの時間を予測する手段である。これは、プログラムの残り処理量８０１を記憶すること等によって予測することができる。例えば、ユーザプログラム４３８の残り処理量801が６０である場合、ユーザプログラム４３８（計算機１０１上での優先順位１）の単位処理量当たりの時間制約が０.０７４ ミリ秒なので、０.０７４×６０＝４.４４ ミリ秒と予測することができる。時間制約設定手続き手段８０２は新たに別プログラムに対して処理を依頼する際に、新たな時間制約を計算する手段である。これは、処理依頼を受理した時点からの経過時間８０３等を記憶することによって達成できる。
【０１６３】
通信８１０〜８１６の流れは、上記処理依頼の転送を行う際に、どのように処理依頼が別プログラムに送られるかを示したものである。本実施例では、ユーザプログラム４４０がユーザプログラム４３８（プログラムＦの一つ）に対して時間制約５ミリ秒で処理依頼を行い（通信８１０）、これが別プログラムに転送される過程を例として示している。ここで、処理依頼５５２の実行開始から経過時間１.８ ミリ秒後に残り処理量が６０千命令であったと仮定する。処理時間予測手続き手段８００は、優先順位変換手続き手段５７３から自己のプログラムの優先順位１に対応する単位処理量当たりの時間制約０.０７４ ミリ秒を受け取り（通信８１１）、上述の計算を行って処理予測時間４.４４ ミリ秒を計算する（通信８１２）。時間制約設定手続き手段８０２は時間制約５ミリ秒と経過時間１.８ ミリ秒とから新たな時間制約３.２ ミリ秒を計算する（通信８１３）。新たな時間制約内に残っている処理を完了することができないと予測されるので、この処理依頼を別プログラムに転送する。このため、新たに計算された時間制約３.２ ミリ秒を指定して、該時間制約を満たすプログラムＦが別に存在するかどうかをプログラム選択手続き手段７６０に尋ねる（通信８１４）。プログラム選択手続き手段７６０はプログラムＦのプログラムリスト７７６から時間制約3.2 ミリ秒を満たすプログラム位置情報を調べる。図３８の例では、プログラム位置情報７８９（計算機１０３上のユーザプログラム４３９に対応）を見つけることができる。プログラム選択手続き手段７６０はプログラム位置情報７８９に対応するユーザプログラム４３９の位置を処理転送手続き手段５５０に通知する（通信８１５）。これを受けた処理転送手続き手段５５０がユーザプログラム４３９に対して、時間制約に間に合わないと判断した処理５５２を依頼することになる（通信８１６）。
【０１６４】
本第十三の実施例を用いれば、個々のプログラムに対して依頼された処理を他の同一時間制約を持つプログラムに転送することができ、特定のプログラムに対して処理が集中することなく、処理依頼を複数のプログラムで分散させることができる。さらにまた、新たに依頼された処理が、実行中の処理の完了を待つ必要がなく、リアルタイム性保証をさらに向上させることが可能となる。
【０１６５】
さらに、本実施例によれば、あるプログラムに対して依頼された処理が時間制約に間に合わないと認識した時点で、他のより高速に処理を完了できるプログラムに処理依頼を転送させることができ、処理依頼の時間制約内の完了をさらに厳密に保証することができる。このような場合の処理依頼転送は、何らかの突発的な事故によりプログラムの実行が遅れた場合にも、時間制約を保証できるようにしたものである。
【０１６６】
図３８では、処理転送手続き手段５５０，待ち行列５５１，処理時間予測手続き手段８００，時間制約設定手続き手段８０２をプログラム内部に配置したが、これをプログラム外部に配置し、複数のプログラムが共通に使用する手続き並びにデータ構造として実現することも可能である。また、本実施例では、プログラム選択手続き手段７６０と優先順位変換手続き手段５７２〜５７３との組み合わせから構成される図３７の分散処理システムに処理転送手続き手段５５０，待ち行列５５１，処理時間予測手続き手段８００，時間制約設定手続き手段８０２を追加した構成となるが、プログラム選択手続き手段７００と優先順位変換手続き手段７２０との組み合わせから構成される図３５の分散処理システムにこれらの手続き，データ構造を追加しても同様の処理を行うことができる。
【０１６７】
以上述べた本発明の第十三の実施例には、別の実施例がある。第十三の実施例は、あるプログラムに対して依頼された処理が時間制約に間に合わないと判断された場合、該処理を別のプログラムに転送するというものであったが、該処理を転送せず、処理を実行するプログラムにより高い優先順位を与え、実行中の処理をより迅速に処理させるという方式を採用することも可能である。この方式は、図３８の例では、新たな時間制約３.２ ミリ秒と残り処理量６０千命令とから、単位処理量当たりの時間制約３.２／６０＝０.０５３ミリ秒を計算し、ユーザプログラム４３８の優先順位を該単位処理量当たりの時間制約を満たす優先順位０に高め、処理を続けるものである。これにより、処理を別プログラムに転送することなく、望ましいリアルタイム性を保証することができる。なお、この方式を採用するためには、優先順位変更手続き手段１４６〜１４７を各計算機上に配置させる必要がある。
【０１６８】
なお、図３０乃至図３８において、図２９の通信時間予測手続き手段６７０〜６７１を導入し、時間制約をより厳密に判断させることは可能である。
【０１６９】
以上の第一乃至第十三の実施例に述べたように、本発明は、緊急度または時間制約を用いて分散処理システムの各計算機の優先順位を統一的に管理し、より厳密なリアルタイム性保証を実現するものである。
【０１７０】
緊急度を用いて優先順位管理を行う本発明によれば、優先順位変換手段と優先順位変更手段を用いることにより、同一緊急度を有する処理が性能，負荷の異なるいずれの計算機においても同程度の迅速さで実行されることを保証できるようになる。
【０１７１】
また、計算機選択手段を用いることにより、緊急度の高い処理が一つの計算機に集中するといった現象がなくなり、各計算機におけるリアルタイム性保証をより厳密に行うことが可能となる。
【０１７２】
さらにまた、プログラム選択手段を用いることにより、前記優先順位変更手段が存在しない場合でも、複数の緊急度の異なるプログラムを用意して、これらのうちから最も適した緊急度のプログラムに対して処理を依頼し、望ましい迅速さで処理を実行させることが可能となる。
【０１７３】
さらにまた、処理転送手段を用いることにより、処理実行中のプログラムに新たに依頼された処理を、該プログラムの処理が終了するまで待たせることなく、別の同程度の迅速さで処理できるプログラムで実行させることが可能となり、より厳密なリアルタイム性保証を実現することができる。
【０１７４】
時間制約を用いて優先順位管理を行う本発明によれば、優先順位変換手段と優先順位変更手段を用いることにより、処理を時間制約に対応した各計算機の優先順位で実行させ、時間制約の短い処理を他のより時間制約の緩い処理の前に実行させるといったことが可能となり、分散処理システムにおける各処理のリアルタイム性をより厳密に保証することができる。また、時間制約の長い処理であっても、他処理を優先的に処理させている間に、処理が行われないまま該時間制約が近付いてくることがあり、この際には、短くなった時間制約に応じて優先順位をより高く再設定し、この優先順位で処理を実行させることが可能となる。
【０１７５】
また、通信時間予測手段を用いることにより、計算機間の通信時間が無視できない場合に、処理の時間制約をより厳密に設定することが可能となる。
【０１７６】
さらにまた、計算機選択手段を用いることにより、処理の時間制約の短い処理が一つの計算機に集中するといった現象がなくなり、各計算機におけるリアルタイム性保証をより厳密に行うことが可能となる。
【０１７７】
さらにまた、プログラム選択手段を用いることにより、前記優先順位変更手段が存在しない場合でも、複数の時間制約の異なるプログラムを用意して、これらのうちから最も適した時間制約のプログラムに対して処理を依頼し、望ましい迅速さで処理を実行させることが可能となる。
【０１７８】
さらにまた、処理転送手段を用いることにより、処理実行中のプログラムに新たに依頼された処理を、該プログラムの処理が終了するまで待たせることなく、別の同程度の時間制約を有するプログラムで実行させることが可能となり、より厳密なリアルタイム性保証を実現することができる。
【０１７９】
さらにまた、処理時間予測手段と時間制約設定手段を用いることにより、プログラムが現在の優先順位で実行される場合に処理の時間制約を満たすか否かを判定し、時間制約を満たせないと判定される場合には、より短い時間制約を設定できる。新たに設定した時間制約を用いて、前記優先順位変換手段と優先順位変更手段がより高い優先順位をプログラムに与えることや、該新しい時間制約を満たし得る別の同一プログラムに処理を転送，実行させることができ、結果的に最初に与えられた時間制約を満たすように管理することが可能となる。
【０１８０】
【発明の効果】
本発明によれば、分散処理システムにおいて、処理の各計算機における優先順位を統一的に管理できる。さらに、性能，負荷および機種の異なる計算機を含み得る分散処理システムにおいて、より厳密なリアルタイム性の保証を行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の第一の実施例の構成図である。
【図２】緊急度と優先順位との対応を示す優先順位対応表のデータ構造を示す図である。
【図３】優先順位変換手段の別の実現例を示す図である。
【図４】緊急度を指定して処理依頼を行う際のプログラム形式を示す図である。
【図５】本発明の第一の実施例において、緊急度指定通信を行う際の処理の流れを示す図である。
【図６】緊急度と優先順位との対応を示す優先順位対応表の内容を負荷に応じて変更するためのフローチャートである。
【図７】緊急度と優先順位との対応を示す優先順位対応表を、負荷の増減によって変更する形式を示す図である。
【図８】緊急度と優先順位との対応を示す優先順位対応表を、負荷の増減によって変更するプログラムを示す図である。
【図９】緊急度と優先順位との対応を示す優先順位対応表の変更に伴って、プログラムの優先順位を変更するためのフローチャートである。
【図１０】本発明の第二の実施例、並びに、該実施例における緊急度指定通信の処理の流れを示す図である。
【図１１】本発明の第三の実施例の構成図である。
【図１２】本発明の第三の実施例において、プログラム起動処理の流れを示すフローチャートである。
【図１３】本発明の第三の実施例において、計算機負荷情報，負荷量，負荷／性能値の計算例を示す図である。
【図１４】本発明の第三の実施例において、プログラム移動処理の流れを示すフローチャートである。
【図１５】本発明の第三の実施例において、計算機負荷情報，負荷量，負荷／性能値の別の計算例を示す図である。
【図１６】本発明の第四の実施例の構成図である。
【図１７】本発明の第五の実施例の構成図である。
【図１８】本発明の第五の実施例において、プログラム選択を行う際の処理の流れを示す図である。
【図１９】指定優先順位のプログラムを見つける処理の流れを示すフローチャートである。
【図２０】本発明の第六の実施例、並びに、該実施例におけるプログラム選択処理の流れを示す図である。
【図２１】本発明の第七の実施例、並びに、該実施例における処理依頼転送の流れを示す図である。
【図２２】本発明の第八の実施例の構成図である。
【図２３】時間制約と優先順位との対応を示す優先順位対応表のデータ構造を示す図である。
【図２４】時間制約から優先順位を導くプログラムを示す図である。
【図２５】時間制約を指定して処理依頼を行う際のプログラム形式を示す図である。
【図２６】本発明の第八の実施例において、時間制約指定通信を行う際の処理の流れを示す図である。
【図２７】時間制約と優先順位との対応を示す優先順位対応表の内容を負荷に応じて変更するためのフローチャートである。
【図２８】時間制約と優先順位との対応を示す優先順位対応表を、負荷の増減によって変更する形式を示す図である。
【図２９】本発明の第九の実施例、並びに、該実施例において通信時間を考慮した時間制約指定通信を行う際の処理の流れを示す図である。
【図３０】本発明の第十の実施例の構成図である。
【図３１】本発明の第十の実施例において、プログラム起動処理の流れを示すフローチャートである。
【図３２】本発明の第十の実施例において、計算機負荷情報，負荷量，負荷／性能値の計算例を示す図である。
【図３３】本発明の第十の実施例において、プログラム移動処理の流れを示すフローチャートである。
【図３４】本発明の第十の実施例において、計算機負荷情報，負荷量，負荷／性能値の別の計算例を示す図である。
【図３５】本発明の第十一の実施例の構成図である。
【図３６】本発明の第十一の実施例において、プログラム選択を行う際の処理の流れを示す図である。
【図３７】本発明の第十二の実施例、並びに、該実施例におけるプログラム選択処理の流れを示す図である。
【図３８】本発明の第十三の実施例、並びに、該実施例における処理依頼転送の流れを示す図である。
【符号の説明】
１００〜１０３…計算機、１１０…ネットワーク、１３０〜１３７，４３０〜４４２…ユーザプログラム、１４０〜１４１，５７０〜５７１…プライオリティキュー、１４２〜１４３…スケジューラ、１４４〜１４５，２６０，５７２〜５７３，７２０…優先順位変換手続き手段、１４６〜１４７…優先順位変更手続き手段、１５０〜１５１，２７０，５８０〜５８１，７３０…優先順位対応表、２９０〜２９１…プログラム実行・移動手続き手段、２９２，２９６〜２９７…プログラム移動決定手続き手段、２９４，２９８〜２９９…計算機選択手続き手段、３００，３３０〜３３１…計算機情報、４１０，５１０，７００，７６０…プログラム選択手続き手段、４２０，５２０，７１０，７７０…プログラム位置データベース、４９０〜４９２…優先順位リスト、５５０…処理転送手続き手段、５５１…待ち行列、６００…処理量データ、６７０〜６７１…通信時間予測手続き手段、６８０〜６８１…通信時間表、８００…処理時間予測手続き手段、８０２…時間制約設定手続き手段。
【図１】
0003658420.tif 000002
【図２】
0003658420.tif 000003
【図３】
0003658420.tif 000004
【図４】
0003658420.tif 000005
【図５】
0003658420.tif 000006
【図６】
0003658420.tif 000007
【図７】
0003658420.tif 000008
【図８】
0003658420.tif 000009
【図９】
0003658420.tif 000010
【図１０】
0003658420.tif 000011
【図１１】
0003658420.tif 000012
【図１２】
0003658420.tif 000013
【図１３】
0003658420.tif 000014
【図１４】
0003658420.tif 000015
【図１５】
0003658420.tif 000016
【図１６】
0003658420.tif 000017
【図１７】
0003658420.tif 000018
【図１８】
0003658420.tif 000019
【図１９】
0003658420.tif 000020
【図２０】
0003658420.tif 000021
【図２１】
0003658420.tif 000022
【図２２】
0003658420.tif 000023
【図２３】
0003658420.tif 000024
【図２４】
0003658420.tif 000025
【図２５】
0003658420.tif 000026
【図２６】
0003658420.tif 000027
【図２７】
0003658420.tif 000028
【図２８】
0003658420.tif 000029
【図２９】
0003658420.tif 000030
【図３０】
0003658420.tif 000031
【図３１】
0003658420.tif 000032
【図３２】
0003658420.tif 000033
【図３３】
0003658420.tif 000034
【図３４】
0003658420.tif 000035
【図３５】
0003658420.tif 000036
【図３６】
0003658420.tif 000037
【図３７】
0003658420.tif 000038
【図３８】
0003658420.tif 000039