(57)【要約】      （修正有）【課題】スレッドを疑似並列的に実行する方法を提供する。【解決手段】タイムスライス内で、スレッドに対して、プリエンプティブな第１のスケジューラ（１１）によって、スレッドの優先度を用いて、時間的に限定されたリソース、特に演算時間が割り当てられ、第１のスケジューラ（１１）が、他のスケジューラ（１２、１３、１４）と組み合される。【選択図】図１
2017130205.tif 000002
【特許請求の範囲】
【請求項１】
スレッドを疑似並列的に実行する方法（６０）であって、
‐タイムスライス（１、２、３）内で、前記スレッドに対して、プリエンプティブな第１のスケジューラ（１１）によって、前記スレッドの優先度（２０）を用いて、時間的に限定されたリソース、特に演算時間（ｔ）が割り当てられる（６３）、
という特徴を有することを特徴とする、方法（６０）。
【請求項２】
‐適合的な第２のスケジューラ（１２）は、前記タイムスライス（１、２、３）を、比率により設定可能な実行時間割り当て（４０）が当該タイムスライス（１、２、３）内で前記スレッドに与えられるように、分割し（６２）、及び、
‐前記リソースの割り当て（６３）は、前記実時間割り当て（４０）内で行われる、
という特徴を有することを特徴とする、請求項１に記載の方法（１０）。
【請求項３】
‐特権が付与された管理プロセス（１４）が、タイムスライス（１、２、３）内で、オペレーティングシステムのコア（５１）を用いて、前記スレッドにより引き起こされた動作事象を監視し（５３）、及び、
‐前記管理プロセス（１４）が前記動作事象を用いて、設定可能な実行時間（５２）が前記タイムスライス（１、２、３）内で前記スレッドに与えられるように、前記スレッドを制御する（５３）、
という特徴を有することを特徴とする、請求項１に記載の方法（１０）。
【請求項４】
‐前記監視及び制御（５３）は、前記オペレーティングシステムのコア（５１）により前記管理プロセス（１４）に提供される管理インタフェースを介して行われる、
という特徴を有することを特徴とする、請求項３に記載の方法（１０）。
【請求項５】
‐少なくとも前記制御（５３）は、前記管理インタフェースを介して前記オペレーティングシステムのコア（５１）に与えられる前記管理プロセス（１４）の管理命令によって行われ、及び、
‐前記管理命令に応じて、前記オペレーティングシステムのコア（５１）は、前記スレッドの逸脱した実行時挙動を無効化し、又は、代替応答、特に前記スレッドのうちの１つの再起動を開始する、
という特徴を有することを特徴とする、請求項４に記載の方法（６０）。
【請求項６】
‐前記無効化は、前記スレッドのうちの１つの終了を含み、
‐前記無効化は、前記スレッドのうちの１つの一時的な中断を含み、又は、
‐前記無効化は、前記優先度（２０）における前記スレッドのうちの１つの格下げを含む、
という特徴のうちの少なくとも１つを有することを特徴とする、請求項５に記載の方法（６０）。
【請求項７】
開始時点（ｔ０）を起点として、第３のスケジューラ（１３）は、前記スレッドに対して、前記タイムスライス（１、２、３）を規則的な時間間隔（３０）で周期的に対応付ける（６１）、
という特徴を有することを特徴とする、請求項１〜６のいずれか１項に記載の方法（１０）。
【請求項８】
請求項１〜７のいずれか１項に記載の方法（６０）を実行するよう構成されたコンピュータプログラム。
【請求項９】
請求項８のコンピュータプログラムが格納された機械読み取り可能な記憶媒体。
【請求項１０】
請求項１〜７のいずれか１項に記載の方法（６０）を実行するよう構成された装置（７０）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スレッドを疑似並列的に実行する方法に関する。さらに、本発明は、対応する装置、対応するコンピュータプログラム、及び、対応する記憶媒体に関する。
【背景技術】
【０００２】
国際規格ＩＳＯ／ＩＥＣ／ＩＥＥＥ９９４５で標準化されたポータブルオペレーティングシステムインタフェース（ＰＯＳＩＸ：ｐｏｒｔａｂｌｅ  ｏｐｅｒａｔｉｎｇ  ｓｙｓｔｅｍ  ｉｎｔｅｒｆａｃｅ）は、開放型（ｏｐｅｎ）マルチタスク（ｍｕｌｔｉ−ｔａｓｋｉｎｇ）システムのための一連の固有のアプリケーション環境プロファイル（ＡＥＰｓ：ａｐｐｌｉｃａｔｉｏｎ  ｅｎｖｉｒｏｎｍｅｎｔ  ｐｒｏｆｉｌｅｓ）を含んでいる。その中には、特に、ＩＥＥＥ１００３．１３−２００３に従って定められた、実時間処理が可能な組込み（ｅｍｂｅｄｄｅｄ）ポータブルアプリケーションのための環境プロファイルも含まれる。
【０００３】
これに対して、オペレーティングシステムのコアの管轄領域に真っ先に入る調整論理回路であって、アプリケーションの疑似並列的な実行、即ち、少なくとも並列して行われているように見える実行を制御する上記調整論理回路は標準化されていない。対応する制御プログラムは、オペレーティングシステム理論においてはスケジューラと称される。実時間処理が可能なオペレーティングシステムの注目する領域では、さらに、所謂割り込み又はプリエンプティブスケジューラが使用される。その際に、ポシックス（ＰＯＳＩＸ）に準拠したオペレーティングシステムの、前提部で記載のプリエンプティブスケジューラは、優先度管理スケジューリング（Ｐｒｉｏｒｉｔａｅｔｓｓｃｈｅｄｕｌｉｎｇ）のストラテジに従っており、このストラテジによれば、優先度が各プロセスに割り当てられ、優先度が最も高い実行可能な各プロセスがその都度実行される。
【０００４】
米国特許出願公開第２００８０２３５７０１号明細書には、アダプティブパーティショニングスケジューラ（ａｄａｐｔｉｖｅｒ  Ｐａｒｔｉｔｉｏｎｓ−Ｓｃｈｅｄｕｌｅｒ）として知られる、革新的なクラスのアルゴリズムの可能な利用が開示されている。これによれば、対称型マルチプロセッサシステムは、複数の処理ユニットと、アダプティブパーティショニングスケジューラの対応するインスタンスと、を含む。このアダプティブパーティショニングスケジューラの各インスタンスは、適合区画（ａｄａｐｔｉｖｅ  Ｐａｒｔｉｔｉｏｎ）のベキ関数値間の比較に基づいて、複数の適合区画のスレッド（ｔｈｒｅａｄ）に対して、各処理ユニットを選択的に対応付ける。適合区画のうちの特定の区画のためのベキ関数は、適合区画が、該当する処理ユニット上に実行時間割り当てを有するかどうかに依存しうる。追加的又は代替的に、アダプティブパーティショニングスケジューラの或るインスタンスと関連付けられた特定の区画のためのベキ関数は、適合区画が、対称型マルチプロセッサシステム上に大局的な実行時間割り当てを有するかどうかに依存しうる。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明は、独立請求項に係るスレッドを疑似並列的に実行する方法、対応する装置、対応するコンピュータプログラム、及び対応する記憶媒体を提供する。
【０００６】
上記解決策の利点は、様々なスケジューリングアルゴリズムを、その個々の長所を利用して短所を相殺するという目的でフレキシブルに組み合わせることである。ここでは特に、オリジン、複雑性、機能的安全性、及び情報安全性について時間的な要求及び特性が非常に様々なアプリケーションが、同じ実行時環境において駆動可能であることに注意されたい。このために、マルチレイヤ（ｍｕｌｔｉ‐ｌａｙｅｒ）スケジューラが、オペレーティングシステムのコア（ケルネル（ｋｅｒｎｅｌ））と、場合によっては、スレッドを監視及び制御するための管理プロセスのような補助構要素と、によって実現される。その際に、スケジューラの層が階層的に互いに重なって形成され、その際に、各スケジューラレベルは、自身の下位に位置付けられたレベルに対して無制限の優先権を享受する。一番上には、タイムスライス法（ｔｉｍｅ  ｓｌｉｃｉｎｇ）が位置付けられ、タイムスライスは、バジェット（Ｂｕｄｇｅｔ）内でさらに分割されて、監視されうる。
【０００７】
従属請求項に記載した処置によって、独立請求項で示した基本思想を有利に更に発展させ及び改良することが可能である。従って、任意の開始時点を起点として、第３のレベルのスケジューラが、スレッドに対して、タイムスライスを定期的な時間間隔で周期的に対応付けるということが構想されうる。時間間隔は、周期的に繰り返される。この時間間隔内で、タイムスライスのあらゆる任意の組み合わせが存在しうる。例えば、イベントへのより良好な待ち時間を獲得するために、１つの間隔内にアプリケーションに複数のタイムスライスを与えることも可能である。この構成は、例えばＰｉｋｅＯＳ（パイクオーエス）又は完全性（Ｉｎｔｅｇｒｉｔｙ）の動作原則に従って、調整能力が低いアプリケーションレベルでの厳しい実時間要求及び厳格な決定論（Ｄｅｔｅｒｍｉｎｉｓｍｕｓ）により特徴付けられる中規模マルチアプリケーションシステムの通常の適用ケースに対応している。
【０００８】
他の観点によれば、適合的な（ａｄａｐｔｉｖ）スケジューラが、スレッドに提供されるタイムスライス（ｔｉｍｅ  ｓｌｉｃｅ）を、比率により設定可能なバジェット（Ｂｕｄｇｅｔ）又は実行時間割り当てが当該タイムスライス内でスレッドに与えられるように、分割することが構想されうる。この実行時間割り当て内で、スレッドに対して、最下位レベルのプリエンプティブスケジューラによって、スレッドの優先度を用いて演算時間が割り当てられる。この構成は、プロプライエタリ（ｐｒｏｐｒｉｅｔａｅｒ）・リアルタイムオペレーションシステムＱＮＸの標準モデルに従って個々のスレッドに固定の実行時間割り当てを保証する大規模マルチアプリケーションシステムの通常の適用ケースに対応している。
【０００９】
他の観点によれば、第２のレベルにおいて、アダプティブパーティションスケジューラの代わりに、特権が付与された管理プロセスが、オペレーティングシステムのコアを用いて、スレッドにより引き起こされた動作事象を監視し、かつ、比率により設定可能な実行時間割り当てがタイムスライス内でスレッドに与えられるように、上記動作事象を用いてスレッドを制御することが構想されうる。この構成は、カーエレクトロニクス分野で普及しているリアルタイムオペレーティングシステムＲＴＡ‐ＯＳと比較可能な、個々のスレッドのレベルでの厳しい実時間要求及び厳格な決定論により特徴付けられる小規模マルチアプリケーションシステムの通常の適用ケースに対応している。ここでは、第２のレベルで使用されるスケジューラの選択は、タイムスライスごとに、本発明の範囲を逸脱することなく様々に行われうると理解されたい。
【図面の簡単な説明】
【００１０】
本発明の実施例が図面に示され、以下の明細書の記載において詳細に解説される。
【図１】スケジューリング構想の本発明に係る様々な組み合わせを示す。
【図２】一実施形態の枠組みにおいて適用される優先度管理スケジューリングを示す。
【図３】一実施形態の枠組みにおいて適用されるタイムスライススケジューリングを示す。
【図４】一実施形態の枠組みにおいて適用されるパーティションスケジューリングを示す。
【図５】一実施形態の枠組みにおいて実行される監視及び制御を示す。
【図６】第１の実施形態に係る方法のフロー図を示す。
【図７】本発明の第２の実施形態に係る制御装置を概略的に示す。
【発明を実施するための形態】
【００１１】
図１は、多種多様な時間特性を有するアプリケーションが存在するソフトウェア実行時環境において、時間的な無干渉（ＦＦＩ：ｆｒｅｅｄｏｍ  ｆｒｏｍ  ｉｎｔｅｒｆｅｒｅｎｃｅ）を具現するための方法を図示している。この方法は、図２で示される、スレッドのための優先度ベースのプリエンプティブスケジューラ（１１）を利用する。
【００１２】
上記方法はさらに、図３に係るタイムスライススケジュータ（１３）を利用する。各タイムスライス（１、２、３）には、１つ以上のプロセスからのスレッドを対応付けることが可能である。タイムスライス（１、２、３）は、設定可能な一定の時間間隔（３０）で、定期的に繰り返される。タイムスライス（１、２、３）は、設定可能なスキームに従って、上記周期的な時間間隔に渡って分割される。その際に、タイムスライス（１、２、３）ごとに、開始点（ｔ０）、及び、間隔開始に対して相対的な終了点が一意にかつ絶対的に定められる。
【００１３】
上記方法はさらに、第４に係る適合的な優先度管理スケジューラ（１２）を利用する。その際に、図４に示される実行時間割り当て（４０）には、１つ以上のプロセスからのスレッドを対応付けることが可能である。この実行時間割り当て（４０）は、図４の円グラフが例示的なパーセンテージで明示するように、トータルで提供されるタイムスライス（ここでは例としてタイムスライス１）の長さと比較して定められる。これにより、実行時間割り当て（４０）は、タイムスライス（１）内の予め決定可能ではない時点に利用し尽されうる。
【００１４】
上記の方法はさらに、図５に係る管理プロセス（１４）を利用し、この管理プロセス（１４）のタスクには、スレッドの監視及び制御（５３）が含まれる。これは、その機能安全性及び情報安全性に対する最も高い要求に従って開発され、従って信頼できるとして等級付けされたプロセスが関わっている。これに応じて、管理プロセス（１４）は、アプリケーションプロセス（５０）の、監視される全てのスレッドが信頼できないという基本的想定の下で作成された。管理プロセス（１４）は、オペレーティングシステムのコア(５１)のスレッドの時間的挙動についての全ての必要な情報を含んでいる。このオペレーティングシステムのコア（５１）は、上記管理プロセス（１４）自体と同じ機能安全性及び情報安全性に対する要件に対応している。管理プロセスは、信頼できるカーネル機構を介して自身に報知されるスレッドの実際の時間的挙動を、信頼できる設定（Ｋｏｎｆｉｇｕｒａｔｉｏｎ）と継続的に比較する。管理プロセス（１４）が、予期される時間的挙動との相違を確認した場合には、誤った挙動を無効化し又は代替応答を開始するために、対応する命令をオペレーティングシステムのコア（５１）に与える。
【００１５】
スケジューラ（１１、１２、１３、１４）は、図１に明示されるように、階層的な秩序に従って互いに組み合わされている。その際に、スケジューラ（１１、１２、１３、１４）は、様々なレベルに対応付けられる。レベルごとに、かつタイムスライスに関して、最大で１つのスケジューラ（１１、１２、１３、１４）が存在しうる。或るレベルにあるスケジューラ（１１、１２、１３、１４）は、下位に位置づけられたレベルの全てのスケジューラ（１１、１２、１３、１４）に対して絶対的な優先権を有する。
【００１６】
優先度（１０）が最も高い最上位レベルには、タイムスライススケジューラ（１３）が含まれている。このアルゴリズムが必要とされない場合には、このレベルは無くてもよい。これは、無限の長さを有するタイムスライス（１、２、３）から成る無限の時間間隔という仮定に対応している。任意の真ん中のレベルは、タイムスライス（１、２、３）ごとに優先度管理スケジューラ（１２）によって形成され、又は、上記の管理プロセス（１４）による監視及び制御（５３）によって形成されうる。優先度が最も低い最下位レベルは、優先度ベースのプリエンプティブスケジューラ（１１）により形成される。このようにして、特に、先に挙げた典型的な適用ケース（１５、１６、１７）が実施される。
【００１７】
図６は、個々のタイムスライス（１、２、３）の期間に渡る、方法（６０）のざっと簡素化された例示的な経過を図示しており、その際には、最下位レベルでは、第１のプリエンプティブスケジューラ（１１）が使用され、真ん中のレベルでは、第２の適合的なスケジューラ（１２）が使用され、最上位レベルでは、第３のスケジューラ（１３）が使用される。これにより、第３のスケジューラ（１３）が、スレッドにタイムスライス（１、２、３）を対応付ける（工程６１）。第２のスケジューラ（１２）自体は、上記対応付けられたタイムスライス（１、２、３）を、比率により設定可能な実行時間割り当て（４０）が当該タイムスライス（１、２、３）内でスレッドに与えられるように、分割する（工程６２）。最後に、この実行時間割り当て（４０）内で、第１のスケジューラ（１１）によって、演算時間（ｔ）がスレッドに、その各優先度（２０）を用いて割り当てられる（工程６３）。
【００１８】
本方法（６０）は、例えば、ソフトウェア若しくはハードウェアにおいて、又はソフトウェアとハードウェアとの混合形態において、例えば、図７に概略的に示すような制御装置（７０）で実現されうる。
【図１】
2017130205.tif 000003
【図２】
2017130205.tif 000004
【図３】
2017130205.tif 000005
【図４】
2017130205.tif 000006
【図５】
2017130205.tif 000007
【図６】
2017130205.tif 000008
【図７】
2017130205.tif 000009
【手続補正書】
【提出日】平成29年1月20日(2017.1.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
スレッドを疑似並列的に実行する方法（６０）であって、
‐タイムスライス（１、２、３）内で、前記スレッドに対して、プリエンプティブな第１のスケジューラ（１１）によって、前記スレッドの優先度（２０）を用いて、時間的に限定されたリソース、特に演算時間（ｔ）が割り当てられる（６３）、
という特徴を有することを特徴とする、方法（６０）。
【請求項２】
時間的に限定されたリソースとして演算時間（ｔ）が割り当てられる（６３）ことを特徴とする、請求項１に記載の方法（６０）。
【請求項３】
‐適合的な第２のスケジューラ（１２）は、前記タイムスライス（１、２、３）を、比率により設定可能な実行時間割り当て（４０）が当該タイムスライス（１、２、３）内で前記スレッドに与えられるように、分割し（６２）、及び、
‐前記リソースの割り当て（６３）は、前記実行時間割り当て（４０）内で行われる、
という特徴を有することを特徴とする、請求項１又は２に記載の方法（６０）。
【請求項４】
‐特権が付与された管理プロセス（１４）が、タイムスライス（１、２、３）内で、オペレーティングシステムのコア（５１）を用いて、前記スレッドにより引き起こされた動作事象を監視し（５３）、及び、
‐前記管理プロセス（１４）が前記動作事象を用いて、設定可能な実行時間（５２）が前記タイムスライス（１、２、３）内で前記スレッドに与えられるように、前記スレッドを制御する（５３）、
という特徴を有することを特徴とする、請求項１〜３のいずれかに記載の方法（６０）。
【請求項５】
‐前記監視及び制御（５３）は、前記オペレーティングシステムのコア（５１）により前記管理プロセス（１４）に提供される管理インタフェースを介して行われる、
という特徴を有することを特徴とする、請求項４に記載の方法（６０）。
【請求項６】
‐少なくとも前記制御（５３）は、前記管理インタフェースを介して前記オペレーティングシステムのコア（５１）に与えられる前記管理プロセス（１４）の管理命令によって行われ、及び、
‐前記管理命令に応じて、前記オペレーティングシステムのコア（５１）は、前記スレッドの逸脱した実行時挙動を無効化し、又は、代替応答、特に前記スレッドのうちの１つの再起動を開始する、
という特徴を有することを特徴とする、請求項５に記載の方法（６０）。
【請求項７】
‐前記無効化は、前記スレッドのうちの１つの終了を含み、
‐前記無効化は、前記スレッドのうちの１つの一時的な中断を含み、又は、
‐前記無効化は、前記優先度（２０）における前記スレッドのうちの１つの格下げを含む、
という特徴のうちの少なくとも１つを有することを特徴とする、請求項６に記載の方法（６０）。
【請求項８】
開始時点（ｔ０）を起点として、第３のスケジューラ（１３）は、前記スレッドに対して、前記タイムスライス（１、２、３）を規則的な時間間隔（３０）で周期的に対応付ける（６１）、
という特徴を有することを特徴とする、請求項１〜７のいずれか１項に記載の方法（６０）。
【請求項９】
請求項１〜８のいずれか１項に記載の方法（６０）を実行するよう構成されたコンピュータプログラム。
【請求項１０】
請求項９のコンピュータプログラムが格納された機械読み取り可能な記憶媒体。
【請求項１１】
請求項１〜８のいずれか１項に記載の方法（６０）を実行するよう構成された装置（７０）。

【手続補正書】
【提出日】平成29年2月3日(2017.2.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
スレッドを疑似並列的に実行する方法（６０）であって、
‐タイムスライス（１、２、３）内で、前記スレッドに対して、プリエンプティブな第１のスケジューラ（１１）によって、前記スレッドの優先度（２０）を用いて、時間的に限定されたリソースが割り当てられる（６３）、
という特徴を有することを特徴とする、方法（６０）。
【請求項２】
時間的に限定されたリソースとして演算時間（ｔ）が割り当てられる（６３）ことを特徴とする、請求項１に記載の方法（６０）。
【請求項３】
‐適合的な第２のスケジューラ（１２）は、前記タイムスライス（１、２、３）を、比率により設定可能な実行時間割り当て（４０）が当該タイムスライス（１、２、３）内で前記スレッドに与えられるように、分割し（６２）、及び、
‐前記リソースの割り当て（６３）は、前記実行時間割り当て（４０）内で行われる、
という特徴を有することを特徴とする、請求項１又は２に記載の方法（６０）。
【請求項４】
‐特権が付与された管理プロセス（１４）が、タイムスライス（１、２、３）内で、オペレーティングシステムのコア（５１）を用いて、前記スレッドにより引き起こされた動作事象を監視し（５３）、及び、
‐前記管理プロセス（１４）が前記動作事象を用いて、設定可能な実行時間（５２）が前記タイムスライス（１、２、３）内で前記スレッドに与えられるように、前記スレッドを制御する（５３）、
という特徴を有することを特徴とする、請求項１〜３のいずれかに記載の方法（６０）。
【請求項５】
‐前記監視及び制御（５３）は、前記オペレーティングシステムのコア（５１）により前記管理プロセス（１４）に提供される管理インタフェースを介して行われる、
という特徴を有することを特徴とする、請求項４に記載の方法（６０）。
【請求項６】
‐少なくとも前記制御（５３）は、前記管理インタフェースを介して前記オペレーティングシステムのコア（５１）に与えられる前記管理プロセス（１４）の管理命令によって行われ、及び、
‐前記管理命令に応じて、前記オペレーティングシステムのコア（５１）は、前記スレッドの逸脱した実行時挙動を無効化し、又は、代替応答、特に前記スレッドのうちの１つの再起動を開始する、
という特徴を有することを特徴とする、請求項５に記載の方法（６０）。
【請求項７】
‐前記無効化は、前記スレッドのうちの１つの終了を含み、
‐前記無効化は、前記スレッドのうちの１つの一時的な中断を含み、又は、
‐前記無効化は、前記優先度（２０）における前記スレッドのうちの１つの格下げを含む、
という特徴のうちの少なくとも１つを有することを特徴とする、請求項６に記載の方法（６０）。
【請求項８】
開始時点（ｔ０）を起点として、第３のスケジューラ（１３）は、前記スレッドに対して、前記タイムスライス（１、２、３）を規則的な時間間隔（３０）で周期的に対応付ける（６１）、
という特徴を有することを特徴とする、請求項１〜７のいずれか１項に記載の方法（６０）。
【請求項９】
請求項１〜８のいずれか１項に記載の方法（６０）を実行するよう構成されたコンピュータプログラム。
【請求項１０】
請求項９のコンピュータプログラムが格納された機械読み取り可能な記憶媒体。
【請求項１１】
請求項１〜８のいずれか１項に記載の方法（６０）を実行するよう構成された装置（７０）。
【外国語明細書】
2017130205000001.pdf