(57)【要約】  対象スレッドがＣＰＵ＃０に割り当てられると、ＣＰＵ＃０が、対象スレッドの実行終了予定時刻が対象スレッドに後続して実行される後続スレッドの実行開始時刻（後続スレッドの生成元スレッドの実行終了予定時刻）以前であるか否かを判断する。対象スレッドの生成時刻から生成元スレッドの終了時刻までのＴ０が２５０［ｍｓ］であり、対象スレッドの生成時刻から対象スレッドの実行終了予定時刻までのＴ１が２８０［ｍｓ］であるため、対象スレッドの実行終了前に後続スレッドの実行が開始されてしまう。ＣＰＵ＃０のタイムスライスが３０［ｍｓ］であるため、対象スレッドが処理終了までに実行される実行回数は４回である。該実行回数を１回とすると、ＣＰＵ＃０のタイムスライスは１００［ｍｓ］となり、生成元スレッドの実行終了予定時刻が対象スレッドの実行終了予定時刻以降となり、後続スレッドを対象スレッドの後に実行させることができる。
2012093496.tif 000002
【特許請求の範囲】
【請求項１】
マルチタスクスケジューリング方法において、
第１スレッドを第１のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）に割り当て、
前記第１スレッドの後に実行される第２スレッドを検出し、
前記第２スレッドを生成する第３スレッドが割り当てられたＣＰＵの負荷に基づいて前記第２スレッドが開始されるまでの第１時間を算出し、
前記第１スレッドの実行が終了するまでの第２時間を算出し、
前記第２時間が前記第１時間よりも大きいときに前記第１のＣＰＵの第１タイムスライスを第２タイムスライスに変更すること、
を特徴とするマルチタスクスケジューリング方法。
【請求項２】
前記第１時間が前記第２時間と実質的に等しくなるように前記第２タイムスライスが計算されること、
を特徴とする請求項１に記載のマルチタスクスケジューリング方法。
【請求項３】
前記計算によって前記第２タイムスライスが得られないときには前記第２スレッドを前記第１のＣＰＵに割り当てること、
を特徴とする請求項２に記載のマルチタスクスケジューリング方法。
【請求項４】
前記第２スレッドを負荷が最小であるＣＰＵに割り当てること、
を特徴とする請求項１または請求項２に記載のマルチタスクスケジューリング方法。
【請求項５】
前記第１スレッドが実行される間、クロック周波数を変更すること、
を特徴とする請求項１、請求項２および請求項４の何れか一に記載のマルチタスクスケジューリング方法。
【請求項６】
スレッド依存関係情報に基づいて前記第２スレッドが検出されること、
を特徴とする請求項１乃至請求項４の何れか一に記載のマルチタスクスケジューリング方法。
【請求項７】
第１スレッドを第１のＣＰＵに割り当てる割当手段と、
前記割当手段によって前記第１のＣＰＵに割り当てられた第１スレッドの後に実行される第２スレッドを検出する検出手段と、
前記検出手段により検出された第２スレッドを生成する第３スレッドが割り当てられたＣＰＵの負荷に基づいて前記第２スレッドが開始されるまでの第１時間を算出する第１の算出手段と、
前記第１スレッドの実行が終了するまでの第２時間を算出する第２の算出手段と、
前記第２の算出手段により算出された第２時間が前記第１の算出手段により算出された第１時間よりも大きいときに前記第１のＣＰＵの第１タイムスライスを第２タイムスライスに設定する設定手段と、
を備えることを特徴とするマルチコアプロセッサシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコアプロセッサにスレッドを割り当てるマルチタスクスケジューリング方法、およびマルチコアプロセッサシステムに関する。
【背景技術】
【０００２】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が、複数のアプリケーションプログラムを順番に切り替えて実行することにより、ユーザには複数のアプリケーションプログラムが同時に実行されているように見せる技術（マルチタスク）が知られている。ここでは、アプリケーションプログラムをプロセスと称する。【０００３】
さらに、１プロセスが複数の機能に分割され、ＣＰＵが時分割処理により複数の機能を平行して実行する技術（マルチスレッド）が知られている。ここで、分割された各機能をスレッドと称する。シングルコアプロセッサシステムにおいて、マルチスレッドを行う場合、スレッド間の実行順序は固定である。【０００４】
マルチコアプロセッサシステムにおいて、マルチタスク・マルチスレッドを行う場合、各ＣＰＵ上で複数のプロセスのスレッドが混在する。一のプロセスの一のスレッドと同一ＣＰＵに割り当てられた他のプロセスのスレッドの影響により、一のプロセスで定められた実行順序が変動する場合がある。【０００５】
シングルコアプロセッサシステム上で動作していたマルチスレッドプログラム（従来のプログラム）がマルチコアプロセッサシステムに移行された場合、スレッド間の実行順序のずれにより、スレッド間で共有する共有データへのアクセス順序がずれる問題点があった。これにより、共有データが不正確な値となる問題点があった。従来、共有データが不正確な値となる問題点を解決するために、開発者が従来のプログラムコード中に同期コードを埋め込むこと（たとえば、以下特許文献１参照。）により、スレッド間の実行順序が固定されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００９−６９９２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来のプログラムコードは膨大な規模であり、コードの埋め込みおよび品質保証を行うと、開発コストが大幅に増大してしまう。タイミングクリティカルな箇所などはアセンブラ言語で書かれていることもあり、その箇所に対しても同期コードを埋め込むと、埋め込みによる性能劣化が要求性能に対して大きくなるという問題点があった。【０００８】
本発明は、上述した従来技術による問題点を解消するため、コードを変更することなく、スレッド間の実行順序を遵守することができるマルチタスクスケジューリング方法、およびマルチコアプロセッサシステムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一観点によれば、第１スレッドを第１のＣＰＵに割り当て、第１スレッドの後に実行される第２スレッドを検出し、第２スレッドを生成する第３スレッドが割り当てられたＣＰＵの負荷に基づいて第２スレッドが開始されるまでの第１時間を算出し、第１スレッドの実行が終了するまでの第２時間を算出し、第２時間が第１時間よりも大きいときに第１のＣＰＵの第１タイムスライスを第２タイムスライスに変更するマルチタスクスケジューリング方法、およびマルチコアプロセッサシステムが提供される。
【発明の効果】
【００１０】
本マルチタスクスケジューリング方法、およびマルチコアプロセッサシステムによれば、コードを変更することなく、スレッド間の実行順序を遵守することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】本発明の一実施例を示す説明図である。
【図２】マルチコアプロセッサシステムのハードウェアを示すブロック図である。
【図３】スレッド依存関係情報の一例を示す説明図である。
【図４】スレッド管理テーブルの一例を示す説明図である。
【図５】マルチコアプロセッサシステム２００の機能ブロック図である。
【図６】各スレッドの割り当て例を示す説明図である。
【図７】Ｔ０とＴ１とを示す説明図である。
【図８】ｎ１’が１の場合のｔ１’を示す説明図である。
【図９】マスタＣＰＵによるスケジュール処理手順を示すフローチャート（その１）である。
【図１０】マスタＣＰＵによるスケジュール処理手順を示すフローチャート（その２）である。
【図１１】対象ＣＰＵによる算出処理手順を示す説明図である。
【図１２】図１１で示したＴ１の算出処理（ステップＳ１１０３）の詳細な一例を示すフローチャートである。
【図１３】図１１で示した処理（ステップＳ１１０４）の詳細な一例を示すフローチャートである。
【図１４】図１１で示したタイムスライスの算出処理（ステップＳ１１０７）の詳細な一例を示すフローチャート（その１）である。
【図１５】図１１で示したタイムスライスの算出処理（ステップＳ１１０７）の詳細な一例を示すフローチャート（その２）である。
【図１６】図１１で示したＴ１の算出処理（ステップＳ１１１４）の詳細な一例を示すフローチャート（その１）である。
【図１７】図１１で示したＴ１の算出処理（ステップＳ１１１４）の詳細な一例を示すフローチャート（その２）である。
【図１８】図１１で示したＴ０の算出処理（ステップＳ１１１５）の詳細な一例を示すフローチャート（その１）である。
【図１９】図１１で示したＴ０の算出処理（ステップＳ１１１５）の詳細な一例を示すフローチャート（その２）である。
【図２０】図１１で示したタイムスライスの算出処理（ステップＳ１１１６）の詳細な一例を示すフローチャート（その１）である。
【図２１】図１１で示したタイムスライスの算出処理（ステップＳ１１１６）の詳細な一例を示すフローチャート（その２）である。
【図２２】各ＣＰＵによる情報処理手順を示すフローチャートである。
【図２３】クロック供給回路２１０による設定処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、本発明にかかるマルチタスクスケジューリング方法、およびマルチコアプロセッサシステムの好適な実施の形態を詳細に説明する。ここで、マルチコアプロセッサシステムにおいて、マルチコアプロセッサとは、コアが複数搭載されたプロセッサである。コアが複数搭載されていれば、複数のコアが搭載された単一のプロセッサでもよく、シングルコアのプロセッサが並列されているプロセッサ群でもよい。なお、本実施の形態では、説明を単純化するため、シングルコアのプロセッサが並列されているプロセッサ群を例に挙げて説明する。
【００１３】
図１は、本発明の一実施例を示す説明図である。マルチコアプロセッサのうちのＣＰＵ＃０には、他のスレッド１と他のスレッド２とが割り当てられている。マルチコアプロセッサのうちのＣＰＵ＃１には、対象スレッドに後続して実行されると定義された後続スレッドの生成元スレッドと他のスレッド３とが割り当てられている。
【００１４】
ＣＰＵ＃０のタイムスライスは３０［ｍｓ］であり、ＣＰＵ＃１のタイムスライスは９０［ｍｓ］である。タイムスライスとは、各ＣＰＵにおいて、該ＣＰＵに割り当てられた複数のスレッドを切り替えて実行する際に、各スレッドの１実行あたりの処理時間である。対象スレッドの割当先ＣＰＵのタイムスライスをｔ１とし、生成元スレッドの割当先ＣＰＵのタイムスライスをｔ０とする。
【００１５】
対象スレッドがＣＰＵ＃０に割り当てられると、ＣＰＵ＃０が、対象スレッドの後続スレッドを検出する。対象スレッドの実行終了予定時刻が後続スレッドの実行開始時刻以前であるか否かを判断する。ここでは、後続スレッドの実行開始時刻は該後続スレッドを生成する生成元スレッドの実行終了予定時刻とする。対象スレッドの生成時刻から生成元スレッドの実行終了予定時刻までの第１時間（Ｔ０）が２５０［ｍｓ］である。対象スレッドの生成時刻から対象スレッドの実行終了予定時刻までの第２時間（Ｔ１）が２８０［ｍｓ］である。
【００１６】
よって、生成元スレッドの実行終了予定時刻が先行スレッドの実行終了予定時刻より前であると判断されるため、ＣＰＵ＃０が、生成元スレッドの実行終了予定時刻が対象スレッドの実行終了予定時刻以降となるようにＣＰＵ＃０のタイムスライスを調整する。具体的には、たとえば、ＣＰＵ＃０が、ＣＰＵ＃０に割り当てられたスレッドの処理時間と、対象スレッドが実行終了までに実行される実行回数とに基づいてＣＰＵ＃０のタイムスライスを算出する。なお、生成元スレッドの実行終了予定時刻が対象スレッドの実行終了予定時刻以降となる対象スレッドの割当先ＣＰＵのタイムスライスをｔ１’とする。
【００１７】
ＣＰＵ＃０のタイムスライスが３０［ｍｓ］の場合、対象スレッドの実行回数は４回である。ここでは、対象スレッドの実行回数（ｎ１’）を１回として算出されるタイムスライスをｔ１’とする。詳細な算出式については実施例１で後述する。他のスレッド１の処理時間が５０［ｍｓ］であり、他のスレッド２の処理時間が１５０［ｍｓ］であり、対象スレッドの処理時間が１００［ｍｓ］である。そして、ＣＰＵ＃０が、ＣＰＵ＃０のタイムスライスを下記のように算出する。
【００１８】
Ｔ０＝他のスレッド１の処理時間＋ｎ１’×ｔ１’＋対象スレッドの処理時間
２５０［ｍｓ］＝５０［ｍｓ］＋ｔ１’＋１００
ｔ１’＝１００［ｍｓ］
【００１９】
そして、ＣＰＵ＃０が、対象スレッドの割当先ＣＰＵであるＣＰＵ＃０のタイムスライスを１００［ｍｓ］に設定する。これにより、生成元スレッドの実行終了予定時刻が対象スレッドの実行終了予定時刻以降となるため、後続スレッドの実行を対象スレッドの実行終了後に開始させることができる。
【００２０】
また、図１で説明した例では、対象スレッドの割当先ＣＰＵのタイムスライスが調整されているが、これに限らず、後続スレッドを生成する生成元スレッドの割当先ＣＰＵのタイムスライスが調整されてもよい。
【００２１】
（マルチコアプロセッサシステムのハードウェア）
図２は、マルチコアプロセッサシステムのハードウェアを示すブロック図である。図２において、マルチコアプロセッサシステム２００は、ＣＰＵ＃０と、ＣＰＵ＃１と、１次キャッシュ２０１と、１次キャッシュ２０２と、スヌープ回路２０３と、２次キャッシュ２０４と、を有している。さらに、マルチコアプロセッサシステム２００は、キーボード２０６と、ディスプレイ２０５と、Ｉ／Ｆ２０７（ＩｎｔｅｒＦａｃｅ）と、メモリコントローラ２０８と、共有メモリ２０９と、クロック供給回路２１０と、を有している。２次キャッシュ２０４と、キーボード２０６と、ディスプレイ２０５と、Ｉ／Ｆ２０７と、メモリコントローラ２０８と、クロック供給回路２１０とは、バス２１６を介して接続されている。
【００２２】
まず、ＣＰＵ＃０とＣＰＵ＃１とは、それぞれレジスタとコアとを有している。ＣＰＵ＃０はマスタＣＰＵであり、マルチコアプロセッサシステム２００の全体の制御を司り、ＯＳ２２１（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）を実行する。ＯＳ２２１はマスタＯＳであり、生成されたスレッドをどのマルチコアプロセッサのうちのいずれのＣＰＵに割り当てるかを制御する機能を有し、該ＣＰＵ＃０に割り当てられたスレッドを実行する。ＯＳ２２１はスケジューラ２３１を有し、スケジューラ２３１はＣＰＵ＃０に割り当てられたスレッドをタイムスライスごとに切り替えて実行する機能を有する。
【００２３】
ＣＰＵ＃１はスレーブＣＰＵであり、ＯＳ２２２を実行する。ＯＳ２２２は、スレーブＯＳであり、該ＣＰＵ＃１に割り当てられたスレッドを実行する。ＯＳ２２２はスケジューラ２３２を有し、スケジューラ２３２はＣＰＵ＃１に割り当てられたスレッドをタイムスライスごとに切り替えて実行する機能を有する。
【００２４】
ＣＰＵ＃０は、１次キャッシュ２０１とスヌープ回路２０３と２次キャッシュ２０４とを介して各部に接続されている。１次キャッシュ２０１と１次キャッシュ２０２とは、それぞれキャッシュメモリとキャッシュコントローラとを有している。１次キャッシュ２０１はＯＳ２２１が実行するスレッドから共有メモリ２０９への書込処理を一時的に記憶する。
【００２５】
また、１次キャッシュ２０１は、共有メモリ２０９から読み出されたデータを一時的に記憶する。１次キャッシュ２０２はＯＳ２２２が実行するスレッドから共有メモリ２０９への書込処理を一時的に記憶する。また、１次キャッシュ２０２は、共有メモリ２０９から読み出されたデータを一時的に記憶する。
【００２６】
スヌープ回路２０３は、１次キャッシュ２０１と１次キャッシュ２０２とで共有するデータがいずれか一方のキャッシュで更新された場合、該更新を検出し、他方のキャッシュも更新する。
【００２７】
２次キャッシュ２０４は、キャッシュメモリとキャッシュコントローラとを有している。２次キャッシュ２０４では、１次キャッシュ２０１や１次キャッシュ２０２から追い出されたデータを記憶する。２次キャッシュ２０４では、ＯＳ２２１とＯＳ２２２とで共有するデータを記憶する。２次キャッシュ２０４は、１次キャッシュ２０１や１次キャッシュ２０２よりも、記憶容量が大きくかつＣＰＵからのアクセス速度が遅い。２次キャッシュ２０４は共有メモリ２０９より、記憶容量が小さくかつＣＰＵからのアクセス速度が速い。
【００２８】
ディスプレイ２０５は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ２０５は、たとえば、ＴＦＴ液晶ディスプレイなどを採用することができる。
【００２９】
キーボード２０６は、数字、各種指示などの入力のためのキーを有し、データの入力を行う。また、キーボード２０６は、タッチパネル式の入力パッドやテンキーなどであってもよい。
【００３０】
Ｉ／Ｆ２０７は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワークに接続され、ネットワークを介して他の装置に接続される。そして、Ｉ／Ｆ２０７は、ネットワークと内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２０７には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００３１】
共有メモリ２０９は、ＣＰＵ＃０とＣＰＵ＃１に共有されるメモリであり、具体的には、たとえば、ＲＯＭ２１２（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）と、ＲＡＭ２１１（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、フラッシュＲＯＭ２１３と、フラッシュＲＯＭコントローラ２１４と、フラッシュＲＯＭ２１５と、などを有している。
【００３２】
ＲＯＭ２１２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ２１１は、ＣＰＵのワークエリアとして使用される。フラッシュＲＯＭ２１３は、ＯＳ２２１やＯＳ２２２などのシステムソフトウェアやアプリケーションソフトウェアや後述するスレッド管理テーブルおよびスレッド依存関係情報などを記憶している。たとえば、各ＯＳを更新する場合、マルチコアプロセッサシステム２００は、Ｉ／Ｆ２０７によって新しいＯＳを受信し、フラッシュＲＯＭ２１３に格納されている古いＯＳを、受信した新しいＯＳに更新する。
【００３３】
フラッシュＲＯＭコントローラ２１４は、各ＣＰＵの制御に従ってフラッシュＲＯＭ２１５に対するデータのリード／ライトを制御する。フラッシュＲＯＭ２１５は、フラッシュＲＯＭコントローラ２１４の制御で書き込まれたデータを記憶する。データの具体例としては、マルチコアプロセッサシステム２００を使用するユーザがＩ／Ｆ２０７を通して取得した画像データ、映像データなどである。フラッシュＲＯＭ２１５は、たとえば、メモリカード、ＳＤカードなどを採用することができる。
【００３４】
クロック供給回路２１０は各部にクロックを供給する。ここで、本実施の形態では、各ＣＰＵへは、５００［ＭＨｚ］と１［ＧＨｚ］のうちのいずれか一方の周波数のクロックを供給できることとする。たとえば、クロック供給回路２１０はＣＰＵごとにフラグを有している。該フラグは１ビットであり、クロック供給回路２１０は、フラグが０であれば５００［ＭＨｚ］のクロックを該フラグに対応するＣＰＵに供給し、フラグが１であれば１［ＧＨｚ］のクロックを該フラグに対応するＣＰＵに供給する。
【００３５】
たとえば、クロック供給回路２１０は、各ＣＰＵからＣＰＵの識別情報とフラグの設定値との通知（「クロック周波数の設定通知」と称する。）を受信すると、受信したＣＰＵの識別情報に対応するフラグを受信したフラグの設定値に設定する。そして、設定後、クロック供給回路２１０は、変更完了をクロック周波数の設定通知の送信元ＣＰＵに送信する。
【００３６】
図３は、スレッド依存関係情報の一例を示す説明図である。スレッド依存関係情報３００は、スレッド間で定義された実行順序を示す情報と各スレッドの処理時間とを有する情報である。スレッド依存関係情報３００は、プロセスＩＤの項目３０１と、スレッドＩＤの項目３０２と、処理時間の項目３０３と、先行スレッドの項目３０４と、後続スレッドの項目３０５と、生成元スレッドの項目３０６と、を有している。
【００３７】
プロセスＩＤの項目３０１にはプロセスの識別情報が記憶されている。スレッドＩＤの項目３０２にはプロセスＩＤの項目３０１に識別情報が記憶されているプロセスが有するスレッドの識別情報が記憶されている。ここで、スレッドは、周知のようにアプリケーションプログラム内で行われる処理の実行単位である。そして、プロセスは少なくとも１以上のスレッドを含む実行単位である。スレッドを１のみしか含まないプロセスは、実質的にスレッドである。よって、スレッドＩＤの項目３０２に識別情報が記憶されていないプロセスはスレッドを１のみしか含まないことを示している。
【００３８】
処理時間の項目３０３には各スレッドの処理時間が記憶されている。ここでは、処理時間は、開発者がＥＳＬ（Ｅｌｅｃｔｒｏｎｉｃ  Ｓｙｓｔｅｍ  Ｌｅｖｅｌ）などの検証ツールを用いて各ＣＰＵの基準となるクロック周波数（「基準クロック周波数」と称する。）を用いて算出した時間である。
【００３９】
先行スレッドの項目３０４は、スレッドＩＤの項目３０２に識別情報が記憶されているスレッドと出力順序に依存関係があり、該スレッドよりも先行して実行されるスレッドの識別情報が記憶されている。後続スレッドの項目３０５は、スレッドＩＤの項目３０２に識別情報が記憶されているスレッドと出力順序に依存関係があり、該スレッドに後続して実行されるスレッドの識別情報が記憶されている。生成元スレッドの項目３０６は、スレッドＩＤの項目３０２に識別情報が記憶されているスレッドを生成する生成元スレッドの識別情報が記憶されている。
【００４０】
たとえば、プロセス＃０は、スレッド＃０〜スレッド＃３を有している。プロセス＃０のスレッド＃０はプロセス＃０のスレッド＃１とプロセス＃０のスレッド＃２とを生成し、プロセス＃０のスレッド＃１はプロセス＃０のスレッド＃３を生成する。プロセス＃０のスレッド＃２とプロセス＃０のスレッド＃３とには出力依存関係があり、プロセス＃０のスレッド＃２の実行終了後に、プロセス＃０のスレッド＃３が後続して実行される。プロセス＃０のスレッド＃０と、プロセス＃０のスレッド＃１と、プロセス＃１と、プロセス＃２とは、出力依存関係が他のスレッドとない。また、上述のようにスレッド依存関係情報３００は共有メモリ２０９に記憶されているが、２次キャッシュ２０４にも記憶されていてもよい。
【００４１】
図４は、スレッド管理テーブルの一例を示す説明図である。スレッド管理テーブル４００は、各プロセスのスレッドがどのＣＰＵにわりあてられているかが登録される情報である。スレッド管理テーブル４００では、プロセスが起動されると、マスタＯＳであるＯＳ２２１によってプロセスごとにスレッドの識別情報が登録される。スレッド管理テーブル４００は、プロセスＩＤの項目４０１と、スレッドＩＤの項目４０２と、割当先ＣＰＵの項目４０３と、クロック周波数の項目４０４と、実行開始時刻の項目４０５と、実行終了予定時刻の項目４０６と、を有している。
【００４２】
プロセスＩＤの項目４０１にはプロセスの識別情報が記憶されている。スレッドＩＤの項目４０２にはプロセスＩＤの項目４０１に識別情報が記憶されているプロセスが有するスレッドの識別情報が記憶されている。スレッドＩＤの項目４０２に識別情報が記憶されていないプロセスはスレッドを１のみしか含まないことを示している。
【００４３】
割当先ＣＰＵの項目４０３には、スレッドＩＤの項目４０２に識別情報が記憶されているスレッドの割当先ＣＰＵの識別情報が記憶されている。また、スレッドの生成時に、該スレッドに対応する割当先ＣＰＵの項目４０３にＣＰＵの識別情報が登録されている場合、該ＣＰＵにスレッドが割り当てられることとする。
【００４４】
クロック周波数の項目４０４には、スレッドＩＤの項目４０２に識別情報が記憶されたスレッドを実行するときのＣＰＵのクロック周波数が記憶されている。本実施の形態では基準クロック周波数を５００［ＭＨｚ］とする。
【００４５】
実行開始時刻の項目４０５には、スレッドＩＤの項目４０２に識別情報が記憶されたスレッドの生成時刻が登録される。実行終了予定時刻の項目４０６は、スレッドの生成時刻に本実施の形態で算出する第２時間が加算された時刻が記憶される。
【００４６】
（マルチコアプロセッサシステム２００の機能ブロック図）
図５は、マルチコアプロセッサシステム２００の機能ブロック図である。マルチコアプロセッサシステム２００は、割当部５０１と、検出部５０２と、第１の算出部５０３と、第２の算出部５０４と、タイムスライス算出部５０５と、設定部５０６と、変更部５０７５０７と、を有している。具体的には、割当部５０１〜変更部５０７を有するプログラムが共有メモリ２０９などの記憶装置に記憶されている。ＣＰＵ＃０やＣＰＵ＃１が該記憶装置にアクセスして該プログラムを読み出し、該プログラム内にコーディングされている処理を実行することにより、該割当部５０１から変更部５０７の処理が実行される。
【００４７】
割当部５０１は、第１スレッドを第１のＣＰＵに割り当てる。検出部５０２は、第１スレッドの後に実行される第２スレッドを検出する。さらに、検出部５０２は、スレッド依存関係情報に基づいて第２スレッドを検出する。第１スレッドが対象スレッドであり、第２スレッドが後続スレッドである。
【００４８】
第１の算出部５０３は、第２スレッドを生成する第３スレッドが割り当てられたＣＰＵの負荷に基づいて第２スレッドが開始されるまでの第１時間を算出する。第３スレッドが後続スレッドの生成元スレッドである。
【００４９】
第２の算出部５０４は、第１スレッドの実行が終了するまでの第２時間を算出する。設定部５０６は、第２時間が第１時間よりも大きいときに第１のＣＰＵの第１タイムスライスを第２タイムスライスに変更する。第１のＣＰＵの第１タイムスライスは設定済のタイムスライスである。
【００５０】
タイムスライス算出部５０５は、第１時間が第２時間と実質的に等しくなるように第２タイムスライスを算出する。また、設定部５０６は、第２時間が第１時間よりも大きいときに第１のＣＰＵの第１タイムスライスをタイムスライス算出部５０５により算出された第２タイムスライスに変更する。
【００５１】
変更部５０７は、第１スレッドが実行される間、クロック周波数を変更する。さらに、割当部５０１は、第２スレッドを負荷が最小であるＣＰＵに割り当てる。
【００５２】
また、割当部５０１は、タイムスライス算出部５０５によって第２タイムスライスが得られないときには第２スレッドを第１のＣＰＵに割り当てる。以上を踏まえて、詳細を実施例１と実施例２を用いて説明する。
【００５３】
（実施例１）
実施例１では、実行順序が定義されたスレッドのうちの、先行スレッドが割り当てられた場合の例について説明する。具体的には、マルチコアプロセッサシステム２００が、マルチコアプロセッサのうちの第１のＣＰＵに先行スレッドが割り当てられたことを検出する。そして、マルチコアプロセッサシステム２００が、第１のＣＰＵと異なる第２のＣＰＵに割り当てられ、先行スレッドに後続する後続スレッドの生成元スレッドの実行終了予定時刻が先行スレッドの実行終了予定時刻より前であるか否かを判断する。
【００５４】
そして、マルチコアプロセッサシステム２００が、生成元スレッドの実行終了予定時刻が先行スレッドの実行終了予定時刻より前であると判断した場合、第１のコアまたは第２のコアのうちの少なくとも一方のコアのタイムスライスを生成元スレッドの実行終了予定時刻が先行スレッドの実行終了予定時刻以降となるように調整する。具体的には、マルチコアプロセッサシステム２００が、該一方のコアのタイムスライスを、一方のコアに割り当てられたスレッドの処理時間と、先行スレッドまたは生成元スレッドの処理が終了するまでに実行する実行回数とに基づいて算出する。マルチコアプロセッサシステム２００が、一方のコアのタイムスライスを算出されたタイムスライスに設定する。
【００５５】
マルチコアプロセッサシステム２００が、生成元スレッドの実行終了予定時刻が先行スレッドの実行終了予定時刻以降となる一方のＣＰＵのタイムスライスが算出できなかった場合、対象スレッドを第２のＣＰＵに割り当てる。そして、マルチコアプロセッサシステム２００が、対象スレッドが第２のＣＰＵに割り当てられた場合、一方のコアのタイムスライスを変更しない。さらに、対象スレッドが第２のＣＰＵに割り当てられた場合、後続スレッドが生成されると、マルチコアプロセッサシステム２００が、後続スレッドを第２のＣＰＵに割り当てる。
【００５６】
また、マルチコアプロセッサシステム２００が、生成元スレッドの実行終了予定時刻が先行スレッドの実行終了予定時刻以降であると判断された場合、一方のコアのタイムスライスを変更しない。詳細については図６〜図８を用いて説明する。
【００５７】
図６は、各スレッドの割り当て例を示す説明図である。図６では、ＣＰＵ＃０にプロセス＃０のスレッド＃１が割り当てられ、ＣＰＵ＃１にプロセス＃１とプロセス＃２とが割り当てられている。
【００５８】
まず、ＯＳ２２１が、プロセス＃０のスレッド＃２の生成を検出する。そして、ＯＳ２２１が、プロセス＃０のスレッド＃２の生成時刻を特定する。ＯＳ２２１が、プロセス＃０のスレッド＃２の後続スレッドをスレッド依存関係情報３００に基づいて検出する。具体的には、たとえば、ＯＳ２２１が、スレッド依存関係情報３００内のプロセス＃０のスレッド＃２に対応する後続スレッドの項目３０５に登録されているスレッドの識別情報を参照することにより、後続スレッドを検出することができる。ここでは、スレッド依存関係情報３００内のプロセス＃０のスレッド＃２に対応する後続スレッドの項目３０５から、プロセス＃０のスレッド＃２の後続スレッドとして、プロセス＃０のスレッド＃３が検出される。
【００５９】
そして、ＯＳ２２１が、スレッド依存関係情報３００に基づいて各ＣＰＵに割り当てられているスレッドの処理時間の合計を算出することにより、最も負荷が小さいＣＰＵを特定する。ここでは、ＣＰＵ＃０に割り当てられているスレッドの処理時間の合計は２５０［ｍｓ］であり、ＣＰＵ＃１に割り当てられているスレッドの処理時間の合計は２００［ｍｓ］である。よって、最も負荷が小さいＣＰＵとしてＣＰＵ＃１が特定される。つぎに、ＯＳ２２１が、特定したＣＰＵ＃１をプロセス＃０のスレッド＃２の仮割当先ＣＰＵとし、ＯＳ２２１がＯＳ２２２へスヌープ回路２０３を介してプロセス＃０のスレッド＃２の仮割当を通知する。
【００６０】
ＯＳ２２２がプロセス＃０のスレッド＃２の仮割当を受け付けると、ＯＳ２２２がプロセス＃０のスレッド＃２の生成時刻からプロセス＃０のスレッド＃２の実行終了予定時刻までの第２時間（Ｔ１）を算出する。ＯＳ２２２が下記式（１）を用いてＴ１を算出する。
【００６１】
【数１】
2012093496.tif 000003
【００６２】
ここで、Ｎは、仮割当先ＣＰＵ（ここではＣＰＵ＃１）に割当済のスレッドと対象スレッドとのスレッドの総数である。ｎ番目のスレッドとは、仮割当先ＣＰＵ（ここではＣＰＵ＃１）に割当済のスレッドと対象スレッドとのうちのスレッドから、順に選択されたスレッドを示している。ｔ１は仮割当先ＣＰＵのタイムスライスである。ｎ１は対象スレッドが処理終了するまでに他のスレッドと切り替えられることにより実行される実行回数である。ｎ１については下記式（２）によって算出される。ｎ１は小数点以下を切り上げている。
【００６３】
ｎ１＝対象スレッドの処理時間／ｔ１                                ・・・（２）
【００６４】
ＯＳ２２２が、プロセス＃０のスレッド＃２の生成時刻から、プロセス＃０のスレッド＃２の後続スレッドであるプロセス＃０のスレッド＃３を生成する生成元スレッドの実行終了予定時刻までの第１時間（Ｔ０）を算出する。ここで、プロセス＃０のスレッド＃３を生成する生成元スレッドは、プロセス＃０のスレッド＃１である。ＯＳ２２２が下記式（３）を用いてＴ０を算出する。
【００６５】
【数２】
2012093496.tif 000004
【００６６】
ここで、Ｍは、後続スレッドを生成する生成元スレッドの割当先ＣＰＵ（ここではＣＰＵ＃０）に割当済のスレッドのスレッド数である。ｍ番目のスレッドとは、生成元スレッドの割当先ＣＰＵ（ここではＣＰＵ＃０）に割当済のスレッドから、順に選択されたスレッドを示している。ｔ０は生成元スレッドの割当先ＣＰＵのタイムスライスである。ｎ０は対象スレッドが実行終了するまでに切り替えられる切り替え回数であり、下記式（４）によって算出される。ｎ０は小数点以下を切り上げている。
【００６７】
ｎ０＝生成元スレッドの処理時間／ｔ０                              ・・・（４）
【００６８】
図７は、Ｔ０とＴ１とを示す説明図である。ここで、対象スレッドの仮割当先ＣＰＵであるＣＰＵ＃１と、後続スレッドを生成する生成元スレッドの割当先ＣＰＵであるＣＰＵ＃０と、それぞれのタイムスライスが３０［ｍｓ］であるとする。ＣＰＵ＃０にはプロセス＃０のスレッド＃１のみが割り当てられているため、Ｔ０は２５０［ｍｓ］である。
【００６９】
つぎに、Ｔ１の算出について説明する。
・Ｔ１＝０
・ｎ１＝プロセス＃０のスレッド＃２の処理時間／ＣＰＵ＃１のタイムスライス
＝１００［ｍｓ］／３０［ｍｓ］
＝４
・ｎ１×ｔ１＝４×３０［ｍｓ］
＝１２０［ｍｓ］
【００７０】
すなわち、ｎ１が４であるため、４回に分割されてプロセス＃０のスレッド＃２が実行される。ＣＰＵ＃１にはプロセス＃１とプロセス＃２が割り当てられている。プロセス＃１の処理時間は５０［ｍｓ］であり、プロセス＃０のスレッド＃２の処理時間は１００［ｍｓ］であるため、プロセス＃１の処理時間が対象スレッドであるプロセス＃０のスレッド＃２以下である。よって、Ｔ１にプロセス＃１の処理時間が加算される。
【００７１】
プロセス＃２の処理時間は１５０［ｍｓ］であり、プロセス＃０のスレッド＃２の処理時間は１００［ｍｓ］であるため、プロセス＃２の処理時間が対象スレッドであるプロセス＃０のスレッド＃２より大きい。よって、Ｔ１にｎ１×ｔ１が加算される。さらに、対象スレッドであるプロセス＃０のスレッド＃２の処理時間がＴ１に加算される。
【００７２】
・Ｔ１＝プロセス＃１の処理時間＋ｎ１×ｔ１＋プロセス＃０のスレッド＃２の処理時間
＝５０［ｍｓ］＋１２０［ｍｓ］＋１００［ｍｓ］
＝２７０［ｍｓ］
【００７３】
ＯＳ２２２が、算出したＴ１が算出したＴ０以下であるか否かを判断する。Ｔ０が２５０［ｍｓ］であり、Ｔ１が２７０［ｍｓ］であるため、ＯＳ２２２がＴ１はＴ０以下でないと判断する。Ｔ１がＴ０以下でないとは、プロセス＃０のスレッド＃２が終了する前に、プロセス＃０のスレッド＃１の実行が終了してしまい、プロセス＃０のスレッド＃２の後続スレッドであるプロセス＃０のスレッド＃３の実行が開始されてしまうことを示している。
【００７４】
そして、ＯＳ２２２が、下記式（５）を用いてＴ１’とＴ０が一致するタイムスライス（ｔ１’）を算出する。
【００７５】
【数３】
2012093496.tif 000005
【００７６】
ここで、ｎ１’については１から順にｔ１’の値がｔ１以下となるまで算出する。
・ｎ１’＝１
・Ｔ１’＝プロセス＃１の処理時間＋ｎ１’×ｔ１’＋プロセス＃０のスレッド＃２の処理時間＝Ｔ０
５０［ｍｓ］＋ｔ１’＋１００［ｍｓ］＝２５０［ｍｓ］
ｔ１’＝２５０［ｍｓ］−１５０［ｍｓ］
ｔ１’＝１００［ｍｓ］
【００７７】
図８は、ｎ１’が１の場合のｔ１’を示す説明図である。Ｔ０は２５０［ｍｓ］のままである。ｎ１’が１であると、ｔ１’が１００［ｍｓ］となり、Ｔ０とＴ１とが一致する。すなわち、プロセス＃０のスレッド＃２の実行が終了すると共に、プロセス＃０のスレッド＃１の実行が終了するため、プロセス＃０のスレッド＃２に後続する後続スレッドとの実行順序を保つことができる。
【００７８】
つぎに、ｎ１’が２の場合について説明する。
・ｎ１’＝２
・Ｔ１’＝プロセス＃１の処理時間＋ｎ１’×ｔ１’＋プロセス＃０のスレッド＃２の処理時間＝Ｔ０
５０［ｍｓ］＋２×ｔ１’＋１００［ｍｓ］＝２５０［ｍｓ］
２×ｔ１’＝２５０［ｍｓ］−１５０［ｍｓ］
ｔ１’＝５０［ｍｓ］
【００７９】
つぎに、ｎ１’が３の場合について説明する。
・ｎ１’＝３
・Ｔ１’＝プロセス＃１の処理時間＋ｎ１’×ｔ１’＋プロセス＃０のスレッド＃２の処理時間＝Ｔ０
５０［ｍｓ］＋３×ｔ１’＋１００［ｍｓ］＝２５０［ｍｓ］
３・ｔ１’＝２５０［ｍｓ］−１５０［ｍｓ］
ｔ１’＝３３．３３［ｍｓ］
【００８０】
つぎに、ｎ１’が４の場合について説明する。
・ｎ１’＝４
・Ｔ１’＝プロセス＃１の処理時間＋ｎ１’×ｔ１’＋プロセス＃０のスレッド＃２の処理時間＝Ｔ０
５０［ｍｓ］＋４×ｔ１’＋１００［ｍｓ］＝２５０［ｍｓ］
２５０［ｍｓ］−１５０［ｍｓ］＝４・ｔ１’
ｔ１’＝２５［ｍｓ］
【００８１】
ｎ１’が４の場合、ｔ１’がｔ１よりも小さくなるため、ＯＳ２２２が、ｎ１’が１〜３のうちのいずれかのｔ１’をあらたなＣＰＵ＃１のタイムスライスに決定する。ＯＳ２２２が、ｔ１’と対象スレッドの割当許可をマスタＯＳであるＯＳ２２１へスヌープ回路２０３を介して通知する。そして、マスタＯＳであるＯＳ２２１が、ｔ１’と対象スレッドの割当許可を受け付けると、ＯＳ２２１が、対象スレッドを対象ＣＰＵに割り当て、対象ＣＰＵのタイムスライスをｔ１からｔ１’に変更する。
【００８２】
（実施例２）
つぎに、実施例２では、後続スレッドを有するスレッドの実行時にクロック周波数を変更する例について説明する。基準クロック周波数は上述の５００［ＭＨｚ］であり、後続スレッドを有するスレッドを実行する場合のクロック周波数（「オーバークロック周波数」と称する。）は１［ＧＨｚ］とする。Ｔ０とＴ１の算出における実施例１との違いについて説明する。
【００８３】
後続スレッドを有するスレッドの実処理時間は、スレッド依存関係情報３００に記憶されている処理時間に（基準クロック周波数／オーバークロック周波数）を掛けた値である。
・後続スレッドを有するスレッドの実処理時間＝スレッド依存関係情報３００内の処理時間×（基準クロック周波数／オーバークロック周波数）
【００８４】
・Ｔ１＝０
・プロセス＃０のスレッド＃２の実処理時間＝プロセス＃０のスレッド＃２の処理時間×（５００［ＭＨｚ］／１［ＧＨｚ］）
＝１００［ｍｓ］×（１／２）
＝５０［ｍｓ］
・ｎ１＝プロセス＃０のスレッド＃２の実処理時間／ＣＰＵ＃１のタイムスライス
＝５０［ｍｓ］／３０［ｍｓ］
＝２（小数点以下切り上げ）
・ｎ１×ｔ１＝２×３０［ｍｓ］
＝６０［ｍｓ］
【００８５】
ＣＰＵ＃１にはプロセス＃１とプロセス＃２が割り当てられている。プロセス＃１の処理時間は５０［ｍｓ］であり、プロセス＃０のスレッド＃２の実処理時間が５０［ｍｓ］であるため、プロセス＃１の処理時間がプロセス＃０のスレッド＃２の実処理時間以下である。よって、Ｔ１にプロセス＃１の処理時間が加算される。
【００８６】
プロセス＃２の処理時間は１５０［ｍｓ］であり、プロセス＃０のスレッド＃２の実処理時間が５０［ｍｓ］であるため、プロセス＃２の処理時間がプロセス＃０のスレッド＃２の実処理時間より大きい。よって、Ｔ１にｎ１×ｔ１が加算される。さらに、プロセス＃０のスレッド＃２の実処理時間がＴ１に加算される。
【００８７】
・Ｔ１＝プロセス＃１の処理時間＋ｎ１×ｔ１＋プロセス＃０のスレッド＃２の実処理時間
＝５０［ｍｓ］＋６０［ｍｓ］＋５０［ｍｓ］
＝１６０［ｍｓ］
【００８８】
Ｔ０は２５０［ｍｓ］であり、Ｔ１が１６０［ｍｓ］であるため、ＯＳが、Ｔ０＞Ｔ１であると判断し、ＯＳが、割当許可をマスタＯＳであるＯＳへ通知する。ＯＳが、割当許可を受け付けると、対象スレッドをＣＰＵ＃１に割り当てる。ＯＳが、対象スレッドに後続スレッドがある場合、対象スレッドの識別情報に対応するスレッド管理テーブル４００のクロック周波数の項目４０４に１［ＧＨｚ］を登録する。
【００８９】
（スケジュール処理手順）
つぎに、マスタＣＰＵと対象スレッドの仮割当先である対象ＣＰＵによる対象スレッドのスケジュール処理手順について図９から図１４を用いて説明する。図９から図１４は上述の実施例１に対応するフローチャートであり、図９から図１４は上述の実施例２に対応するフローチャートである。
【００９０】
図９および図１０は、マスタＣＰＵによるスケジュール処理手順を示すフローチャートである。まず、マスタＣＰＵであるＣＰＵ＃０が、スレッドの生成を検出したか否かを判断し（ステップＳ９０１）、スレッドの生成を検出していないと判断した場合（ステップＳ９０１：Ｎｏ）、ステップＳ９０１へ戻る。
【００９１】
ＣＰＵ＃０が、スレッドの生成を検出したと判断した場合（ステップＳ９０１：Ｙｅｓ）、生成されたスレッドの生成時刻を特定し（ステップＳ９０２）、対象スレッドの割当先ＣＰＵが決定済か否かを判断する（ステップＳ９０３）。ＣＰＵ＃０が、対象スレッドの割当先ＣＰＵが決定済であると判断した場合（ステップＳ９０３：Ｙｅｓ）、割当部５０１により、決定済の割当先ＣＰＵに対象スレッドを割り当てる（ステップＳ９０４）。そして、ＣＰＵ＃０が、割当結果と対象スレッドの生成時刻を出力し（ステップＳ９０５）、一連の処理を終了する。
【００９２】
対象スレッドの割当先ＣＰＵが決定済であるとは、スレッド管理テーブル４００内の対象スレッドに対応する割当先ＣＰＵの項目４０３にＣＰＵの識別情報が登録されていることを示している。ここで、対象スレッドの割手先ＣＰＵが決定されている場合について説明する。たとえば、対象スレッドに先行スレッドがあるとする。該先行スレッドの生成時に、該先行スレッドの実行終了予定時刻が該対象スレッドの実行開始予定時刻より後であると判断された場合、対象スレッドが該先行スレッドと同一のＣＰＵに割り当てる。そのため、先行スレッドの割り当て時に、対象スレッドの割当先が先行スレッドの割当先ＣＰＵに決定される。
【００９３】
ステップＳ９０３において、ＣＰＵ＃０が、対象スレッドの割当先ＣＰＵが決定済でないと判断した場合（ステップＳ９０３：Ｎｏ）、最小負荷のＣＰＵを対象ＣＰＵとして特定する（ステップＳ９０６）。つぎに、ＣＰＵ＃０が、検出部５０２により、対象スレッドの後続スレッドを検出し（ステップＳ９０７）、後続スレッドが検出されたか否かを判断する（ステップＳ９０８）。具体的には、ＣＰＵ＃０が、スレッド依存関係情報３００内の対象スレッドに対応する後続スレッドの項目３０５を参照することにより、後続スレッドを検出する。
【００９４】
ＣＰＵ＃０が、後続スレッドが検出されなかったと判断した場合（ステップＳ９０８：Ｎｏ）、ステップＳ９１１へ移行する。後続スレッドが検出されないとは、対象スレッドに後続スレッドがないことを示し、スレッド依存関係情報３００内の対象スレッドに対応する後続スレッドの項目３０５にスレッドの識別情報が登録されていないことを示している。ＣＰＵ＃０が、後続スレッドが検出されたと判断した場合（ステップＳ９０８：Ｙｅｓ）、対象ＣＰＵに対象スレッドの仮割当を通知し（ステップＳ９０９）、対象ＣＰＵから割当許可または割当不可を受け付けたか否かを判断する（ステップＳ９１０）。
【００９５】
ＣＰＵ＃０が、対象ＣＰＵから割当許可または割当不可を受け付けていないと判断した場合（ステップＳ９１０：Ｎｏ）、ステップＳ９１０に戻る。ＣＰＵ＃０が、対象ＣＰＵから割当許可を受け付けたと判断した場合（ステップＳ９１０：割当許可）、対象ＣＰＵに対象スレッドを割り当て（ステップＳ９１１）、割当結果を出力し（ステップＳ９１２）、一連の処理を終了する。
【００９６】
ステップＳ９１０において、ＣＰＵ＃０が、対象ＣＰＵから割当不可を受け付けたと判断した場合（ステップＳ９１９：割当不可）、後続スレッドの生成元スレッドの割当先ＣＰＵに対象スレッドを割り当てる（ステップＳ９１３）。ＣＰＵ＃０が、対象スレッドの後続スレッドの割当先ＣＰＵを該後続スレッドの生成元スレッドの割当先ＣＰＵに決定し（ステップＳ９１４）、割当結果および決定結果を出力する（ステップＳ９１５）。具体的には、たとえば、ＣＰＵ＃０が、共有メモリ２０９に記憶されたスレッド管理テーブル４００内において識別情報が一致するスレッドの割当先ＣＰＵの項目４０３へ決定した割当先ＣＰＵの識別情報を登録する。
【００９７】
図１１は、対象ＣＰＵによる算出処理手順を示す説明図である。図１１において、対象スレッドの仮割当先ＣＰＵとされた対象ＣＰＵが、対象スレッドの仮割当を受け付けたか否かを判断する（ステップＳ１１０１）。対象ＣＰＵが、対象スレッドの仮割当を受け付けていないと判断した場合（ステップＳ１１０１：Ｎｏ）、ステップＳ１１０１へ戻る。
【００９８】
対象ＣＰＵが、対象スレッドの仮割当を受け付けたと判断した場合（ステップＳ１１０１：Ｙｅｓ）、後続スレッドを生成する生成元スレッドを特定する。（ステップＳ１１０２）。具体的には、対象ＣＰＵが、スレッド依存関係情報３００内の後続スレッドに対応する生成元スレッドの項目３０５を参照することにより、生成元スレッドを特定する。そして、対象ＣＰＵが、第２の算出部５０４により、Ｔ１の算出処理を実行する（ステップＳ１１０３）。Ｔ１は対象スレッドの生成時刻から対象スレッドの実行終了予定時刻までの第２時間である。対象ＣＰＵが、第１の算出部５０３により、Ｔ０の算出処理を実行する（ステップＳ１１０４）。Ｔ０は対象スレッドの生成時刻から後続スレッドの実行開始時刻までの第１時間である。
【００９９】
そして、対象ＣＰＵが、Ｔ０＞Ｔ１であるか否かを判断し（ステップＳ１１０５）、Ｔ０＞Ｔ１であると判断した場合（ステップＳ１１０５：Ｙｅｓ）、割当許可をマスタＣＰＵに通知し（ステップＳ１１０６）、ステップＳ１１１３へ移行する。ステップＳ１１０５において、対象ＣＰＵが、Ｔ０＞Ｔ１でないと判断した場合（ステップＳ１１０５：Ｎｏ）、タイムスライス算出部５０５により、タイムスライス（ｔ１’）の算出処理を実行する（ステップＳ１１０７）。対象ＣＰＵが、対象スレッドと後続スレッドとの依存関係を満たすｔ１’が算出されたか否かを判断する（ステップＳ１１０８）。
【０１００】
対象ＣＰＵが、対象スレッドと後続スレッドとの依存関係を満たすｔ１’を算出されたと判断した場合（ステップＳ１１０８：Ｙｅｓ）、設定部５０６により、対象ＣＰＵのタイムスライス＝ｔ１’とする（ステップＳ１１０９）。対象ＣＰＵが、割当許可をマスタＣＰＵに通知し（ステップＳ１１１０）、対象スレッドの生成時刻および実行終了予定時刻を出力し（ステップＳ１１１１）、一連の処理を終了する。具体的には、対象ＣＰＵが、スレッド依存関係情報３００内の対象スレッドに該当する識別情報の実行開始時刻の項目４０５に生成時刻を登録し、該識別情報の実行終了予定時刻の項目４０６に実行終了予定時刻を登録する。実行終了予定時刻は生成時刻にＴ１’が加算された時刻である。
【０１０１】
ステップＳ１１０８において、対象ＣＰＵが、対象スレッドと後続スレッドとの依存関係を満たすｔ１’が算出されなかったと判断した場合（ステップＳ１１０８：Ｎｏ）、割当不可をマスタＣＰＵに通知する（ステップＳ１１１２）。そして、対象ＣＰＵが、対象スレッドの生成時刻を出力し（ステップＳ１１１３）、一連の処理を終了する。
【０１０２】
図１２は、図１１で示したＴ１の算出処理（ステップＳ１１０３）の詳細な一例を示すフローチャートである。対象ＣＰＵが、対象スレッドの仮割当先ＣＰＵに割当済のスレッドを特定する（ステップＳ１２０１）。対象ＣＰＵが、ｔ１＝仮割当先ＣＰＵのタイムスライスとし（ステップＳ１２０２）、ｎ１（小数点以下切り上げ）＝対象スレッドの処理時間／ｔ１とし（ステップＳ１２０３）、Ｔ１＝０とする（ステップＳ１２０４）。対象スレッドの処理時間は、スレッド依存関係情報３００から対象スレッドの識別情報に基づいて特定される。
【０１０３】
対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあるか否かを判断する（ステップＳ１２０５）。対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあると判断した場合（ステップＳ１２０５：Ｙｅｓ）、未選択のスレッドから任意のスレッド（選択スレッド）を選択する（ステップＳ１２０６）。
【０１０４】
対象ＣＰＵが、対象スレッドの処理時間＞選択スレッドの処理時間であるか否かを判断する（ステップＳ１２０７）。選択スレッドの処理時間は、スレッド依存関係情報３００から選択スレッドの識別情報に基づいて特定される。対象ＣＰＵが、対象スレッドの処理時間＞選択スレッドの処理時間であると判断した場合（ステップＳ１２０７：Ｙｅｓ）、Ｔ１＝Ｔ１＋選択スレッドの処理時間とし（ステップＳ１２０８）、ステップＳ１２０５へ戻る。対象ＣＰＵが、対象スレッドの処理時間＞選択スレッドの処理時間でないと判断した場合（ステップＳ１２０７：Ｎｏ）、Ｔ１＝Ｔ１＋ｎ１×ｔ１とし（ステップＳ１２０９）、ステップＳ１２０５へ戻る。
【０１０５】
ステップＳ１２０５において、対象ＣＰＵが、未選択のスレッドがないと判断した場合（ステップＳ１２０５：Ｎｏ）、Ｔ１を出力し（ステップＳ１２１０）、ステップＳ１１０４へ移行する。出力形式としては、たとえば、対象ＣＰＵが、アクセス可能な記憶装置に記憶する。
【０１０６】
図１３は、図１１で示した処理（ステップＳ１１０４）の詳細な一例を示すフローチャートである。まず、対象ＣＰＵが、対象スレッドの後続スレッドを生成する生成元スレッドの割当先ＣＰＵを特定する（ステップＳ１３０１）。対象ＣＰＵが、生成元スレッドの割当先ＣＰＵに割当済のスレッドを特定する（ステップＳ１３０２）。対象ＣＰＵが、ｔ０＝生成元スレッドの割当先ＣＰＵのタイムスライスとし（ステップＳ１３０３）、ｎ０（小数点以下切り上げ）＝生成元スレッドの処理時間／ｔ０とする（ステップＳ１３０４）。生成元スレッドの処理時間は、スレッド依存関係情報３００から生成元スレッドの識別情報に基づいて特定される。
【０１０７】
対象ＣＰＵが、Ｔ０＝０とし（ステップＳ１３０５）、生成元スレッドの割当先ＣＰＵに割当済のスレッドのうち、未選択のスレッドがあるか否かを判断する（ステップＳ１３０６）。対象ＣＰＵが、未選択のスレッドがあると判断した場合（ステップＳ１３０６：Ｙｅｓ）、未選択のスレッドから任意のスレッド（選択スレッド）を選択し（ステップＳ１３０７）、生成元スレッドの処理時間＞選択スレッドの処理時間であるか否かを判断する（ステップＳ１３０８）。選択スレッドの処理時間は、スレッド依存関係情報３００から選択スレッドの識別情報に基づいて特定される。
【０１０８】
対象ＣＰＵが、生成元スレッドの処理時間＞選択スレッドの処理時間であると判断した場合（ステップＳ１３０８：Ｙｅｓ）、Ｔ０＝Ｔ０＋選択スレッドの処理時間とし（ステップＳ１３０９）、ステップＳ１３０６へ戻る。対象ＣＰＵが、生成元スレッドの処理時間＞選択スレッドの処理時間でないと判断した場合（ステップＳ１３０８：Ｎｏ）、Ｔ０＝Ｔ０＋ｎ０×ｔ０とし（ステップＳ１３１０）、ステップＳ１３０６へ戻る。
【０１０９】
また、ステップＳ１３０６において、対象ＣＰＵが、生成元スレッドの割当先ＣＰＵに割当済のスレッドのうち、未選択のスレッドがないと判断した場合（ステップＳ１３０６：Ｎｏ）、Ｔ０を出力し（ステップＳ１３１１）、ステップＳ１１０５へ移行する。出力形式としては、たとえば、対象ＣＰＵがアクセス可能な記憶装置に記憶する。
【０１１０】
図１４および図１５は、図１１で示したタイムスライスの算出処理（ステップＳ１１０７）の詳細な一例を示すフローチャートである。まず、対象ＣＰＵが、対象スレッドの仮割当先ＣＰＵに割当済のスレッドを特定し（ステップＳ１４０１）、ｎ１’＝１とし（ステップＳ１４０２）、Ｔ１’＝０とする（ステップＳ１４０３）。ここで、ｎ１’は対象スレッドが処理終了までに実行される実行回数を示している。
【０１１１】
対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあるか否かを判断する（ステップＳ１４０４）。対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあると判断した場合（ステップＳ１４０４：Ｙｅｓ）、未選択のスレッドから任意のスレッド（選択スレッド）を選択する（ステップＳ１４０５）。
【０１１２】
つぎに、対象ＣＰＵが、対象スレッドの処理時間＞選択スレッドの処理時間であるか否かを判断する（ステップＳ１４０６）。対象スレッドの処理時間は、スレッド依存関係情報３００から対象スレッドの識別情報に基づいて特定される。選択スレッドの処理時間は、スレッド依存関係情報３００から選択スレッドの識別情報に基づいて特定される。
【０１１３】
対象ＣＰＵが、対象スレッドの処理時間＞選択スレッドの処理時間でないと判断した場合（ステップＳ１４０６：Ｎｏ）、Ｔ１’＝Ｔ１’＋ｎ１’×ｔ１’とし（ステップＳ１４０８）、ステップＳ１４０３へ戻る。対象ＣＰＵが、対象スレッドの処理時間＞選択スレッドの処理時間であると判断した場合（ステップＳ１４０６：Ｙｅｓ）、Ｔ１’＝Ｔ１’＋選択スレッドの処理時間とし（ステップＳ１４０７）、ステップＳ１４０３へ戻る。
【０１１４】
ステップＳ１４０４において、対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがないと判断した場合（ステップＳ１４０４：Ｎｏ）、Ｔ１’＝Ｔ０となるｔ１’を算出し（ステップＳ１４０９）、解があるか否かを判断する（ステップＳ１４１０）。Ｔ１’＝Ｔ０となるｔ１’を算出するとは、具体的には、たとえば、上記式（５）＝Ｔ０の一次方程式の解を算出することである。
【０１１５】
対象ＣＰＵが、解があると判断した場合（ステップＳ１４１０：Ｙｅｓ）、ｔ１’＜ｔ１であるか否かを判断する（ステップＳ１４１１）。対象ＣＰＵが、ｔ１’＜ｔ１でないと判断した場合（ステップＳ１４１１：Ｎｏ）、ｎ１’とｔ１’とを関連付けて出力し（ステップＳ１４１２）、ｎ１’＝ｎ１’＋１とし（ステップＳ１４１３）、ステップＳ１４０３へ戻る。出力形式としては、たとえば、対象ＣＰＵがアクセス可能な記憶装置に記憶する。
【０１１６】
ステップＳ１４１０において、解がないと判断した場合（ステップＳ１４１０：Ｎｏ）、実行回数が１からｎ１’−１の算出したタイムスライスから、任意のタイムスライスをｔ１’として選択し（ステップＳ１４１４）、ステップＳ１１０８へ移行する。ただし、ｎ１’＝１において、解が無い場合、何も選択されていないこととする。１からｎ１’−１の実行回数のうちのいずれの実行回数のタイムスライスが選択されるかについては任意であり、設計者が決定することとしてよい。ステップＳ１４１１において、対象ＣＰＵが、ｔ１’＜ｔ１であると判断した場合（ステップＳ１４１１：Ｙｅｓ）、ステップＳ１４１４に移行する。
【０１１７】
つぎに、上述の実施例２に対応するフローチャートについて説明する。上述したように、実施例２では、後続スレッドを有するスレッドを実行中には該スレッドが割り当てられたＣＰＵのクロック周波数をオーバークロック周波数に設定する。実施例１と実施例２との違いは、図１１で示したステップＳ１１０３とステップＳ１１０４とステップＳ１１０７である。実施例２ではステップＳ１１０３に代わってステップＳ１１１４が実行され、ステップＳ１１０４に代わってステップＳ１１１５が実行され、ステップＳ１１０７に代わってステップＳ１１１６が実行される。
【０１１８】
図１６および図１７は、図１１で示したＴ１の算出処理（ステップＳ１１１４）の詳細な一例を示すフローチャートである。対象ＣＰＵが、対象スレッドの仮割当先ＣＰＵに割当済のスレッドを特定する（ステップＳ１６０１）。対象ＣＰＵが、ｔ１＝仮割当先ＣＰＵのタイムスライスとし（ステップＳ１６０２）、対象スレッドに後続スレッドがあるか否かを判断する（ステップＳ１６０３）。
【０１１９】
対象ＣＰＵが、対象スレッドに後続スレッドがあると判断した場合（ステップＳ１６０３：Ｙｅｓ）、対象スレッドの実処理時間＝対象スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）とし（ステップＳ１６０４）、ステップＳ１６０６へ移行する。対象スレッドの処理時間は、スレッド依存関係情報３００から対象スレッドの識別情報に基づいて特定される。
【０１２０】
対象ＣＰＵが、対象スレッドに後続スレッドがないと判断した場合（ステップＳ１６０３：Ｎｏ）、対象スレッドの実処理時間＝対象スレッドの処理時間とし（ステップＳ１６０５）、ステップＳ１６０６へ移行する。ステップＳ１６０４またはステップＳ１６０５のつぎに、対象ＣＰＵが、ｎ１＝対象スレッドの実処理時間／ｔ１とする（ステップＳ１６０６）。
【０１２１】
対象ＣＰＵが、Ｔ１＝０とし（ステップＳ１６０７）、割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあるか否かを判断する（ステップＳ１６０８）。対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあると判断した場合（ステップＳ１６０８：Ｙｅｓ）、未選択のスレッドから任意のスレッド（選択スレッド）を選択する（ステップＳ１６０９）。
【０１２２】
そして、対象ＣＰＵが、選択スレッドに後続スレッドがあるか否かを判断する（ステップＳ１６１０）。対象ＣＰＵが、選択スレッドに後続スレッドがあると判断した場合（ステップＳ１６１０：Ｙｅｓ）、選択スレッドの実処理時間＝選択スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）とし（ステップＳ１６１１）、ステップＳ１６１３へ移行する。選択スレッドの処理時間は、スレッド依存関係情報３００から選択スレッドの識別情報に基づいて特定される。対象ＣＰＵが、選択スレッドに後続スレッドがないと判断した場合（ステップＳ１６１０：Ｎｏ）、選択スレッドの実処理時間＝選択スレッドの処理時間とし（ステップＳ１６１２）、ステップＳ１６１３へ移行する。
【０１２３】
ステップＳ１６１１またはステップＳ１６１２のつぎに、対象ＣＰＵが、対象スレッドの実処理時間＞選択スレッドの実処理時間であるか否かを判断する（ステップＳ１６１３）。対象ＣＰＵが、対象スレッドの実処理時間＞選択スレッドの実処理時間であると判断した場合（ステップＳ１６１３：Ｙｅｓ）、Ｔ１＝Ｔ１＋選択スレッドの実処理時間とし（ステップＳ１６１４）、ステップＳ１６０８へ戻る。対象ＣＰＵが、対象スレッドの実処理時間＞選択スレッドの実処理時間でないと判断した場合（ステップＳ１６１３：Ｎｏ）、Ｔ１＝Ｔ１＋ｎ１×ｔ１とし（ステップＳ１６１５）、ステップＳ１６０８へ戻る。
【０１２４】
ステップＳ１６０８において、対象ＣＰＵが、割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがないと判断した場合（ステップＳ１６０８：Ｎｏ）、Ｔ１を出力し（ステップＳ１６１６）、ステップＳ１１１５へ移行する。出力形式としては、たとえば、対象ＣＰＵが、アクセス可能な記憶装置に記憶する。
【０１２５】
図１８および図１９は、図１１で示したＴ０の算出処理（ステップＳ１１１５）の詳細な一例を示すフローチャートである。対象ＣＰＵが、対象スレッドの後続スレッドを生成する生成元スレッドの割当先ＣＰＵを特定し（ステップＳ１８０１）、生成元スレッドの割当先ＣＰＵに割当済のスレッドを特定する（ステップＳ１８０２）。対象ＣＰＵが、ｔ０＝生成元スレッドの割当先ＣＰＵのタイムスライスとし（ステップＳ１８０３）、対象スレッドに後続スレッドがあるか否かを判断する（ステップＳ１８０４）。
【０１２６】
対象ＣＰＵが、対象スレッドに後続スレッドがあると判断した場合（ステップＳ１８０４：Ｙｅｓ）、生成元スレッドの実処理時間＝生成元スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）とし（ステップＳ１８０５）、ステップＳ１８０７へ移行する。生成元スレッドの処理時間は、スレッド依存関係情報３００から生成元スレッドの識別情報に基づいて特定される。対象ＣＰＵが、対象スレッドに後続スレッドがないと判断した場合（ステップＳ１８０４：Ｎｏ）、生成元スレッドの実処理時間＝生成元スレッドの処理時間とし（ステップＳ１８０６）、ステップＳ１８０７へ移行する。
【０１２７】
ステップＳ１８０５またはステップＳ１８０６のつぎに、ｎ０（小数点以下切り上げ）＝生成元スレッドの実処理時間／ｔ０とする（ステップＳ１８０７）。ｎ０は生成元スレッドが処理終了までに実行される実行回数である。対象ＣＰＵが、Ｔ０＝０とし（ステップＳ１８０８）、割当先ＣＰＵに割当済のスレッドのうち、未選択のスレッドがあるか否かを判断する（ステップＳ１８０９）。対象ＣＰＵが、割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあると判断した場合（ステップＳ１８０９：Ｙｅｓ）、未選択のスレッドから任意のスレッド（選択スレッド）を選択する（ステップＳ１８１０）。
【０１２８】
そして、対象ＣＰＵが、選択スレッドに後続スレッドがあるか否かを判断する（ステップＳ１８１１）。対象ＣＰＵが、選択スレッドに後続スレッドがあると判断した場合（ステップＳ１８１１：Ｙｅｓ）、選択スレッドの実処理時間＝選択スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）とし（ステップＳ１８１２）、ステップＳ１８１４へ移行する。選択スレッドの処理時間は、スレッド依存関係情報３００から選択スレッドの識別情報に基づいて特定される。対象ＣＰＵが、選択スレッドに後続スレッドがないと判断した場合（ステップＳ１８１１：Ｎｏ）、選択スレッドの実処理時間＝選択スレッドの処理時間とし（ステップＳ１８１３）、ステップＳ１８１４へ移行する。
【０１２９】
ステップＳ１８１２またはステップＳ１８１３のつぎに、対象ＣＰＵが、生成元スレッドの実処理時間＞選択スレッドの実処理時間であるか否かを判断する（ステップＳ１８１４）。対象ＣＰＵが、生成元スレッドの実処理時間＞選択スレッドの実処理時間であると判断した場合（ステップＳ１８１４：Ｙｅｓ）、Ｔ０＝Ｔ０＋選択スレッドの実処理時間とし（ステップＳ１８１５）、ステップＳ１８０９へ戻る。対象ＣＰＵが、生成元スレッドの実処理時間＞選択スレッドの実処理時間でないと判断した場合（ステップＳ１８１４：Ｎｏ）、Ｔ０＝Ｔ０＋ｎ０×ｔ０とし（ステップＳ１８１６）、ステップＳ１８０９へ戻る。
【０１３０】
ステップＳ１８０９において、対象ＣＰＵが、割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがないと判断した場合（ステップＳ１８０９：Ｎｏ）、Ｔ１を出力し（ステップＳ１８１７）、ステップＳ１１０５へ移行する。出力形式としては、たとえば、対象ＣＰＵが、アクセス可能な記憶装置に記憶する。
【０１３１】
また、スレッドごとに該スレッドの実行時のクロック周波数が異なるため、各ＣＰＵではタスクスイッチ、タスクディスパッチ、処理終了ごとにクロックの周波数が変更される。クロック周波数が変更される例を図２０と図２１を用いて説明する。
【０１３２】
図２０および図２１は、図１１で示したタイムスライスの算出処理（ステップＳ１１１６）の詳細な一例を示すフローチャートである。まず、対象ＣＰＵが、対象スレッドの仮割当先ＣＰＵに割当済のスレッドを特定し（ステップＳ２００１）、ｎ１’＝１とし（ステップＳ２００２）、Ｔ１’＝０とする（ステップＳ２００３）。ここで、ｎ１’は対象スレッドが処理終了までに実行される実行回数を示している。
【０１３３】
対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあるか否かを判断する（ステップＳ２００４）。対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがあると判断した場合（ステップＳ２００４：Ｙｅｓ）、未選択のスレッドから任意のスレッド（選択スレッド）を選択する（ステップＳ２００５）。
【０１３４】
つぎに、対象ＣＰＵが、選択スレッドに後続スレッドがあるか否かを判断する（ステップＳ２００６）。対象ＣＰＵが、選択スレッドに後続スレッドがあると判断した場合（ステップＳ２００６：Ｙｅｓ）、選択スレッドの実処理時間＝選択スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）とし（ステップＳ２００７）、ステップＳ２００９へ移行する。選択スレッドの処理時間は、スレッド依存関係情報３００から選択スレッドの識別情報に基づいて特定される。対象ＣＰＵが、選択スレッドに後続スレッドがないと判断した場合（ステップＳ２００６：Ｎｏ）、選択スレッドの実処理時間＝選択スレッドの処理時間とし（ステップＳ２００８）、ステップＳ２００９へ移行する。
【０１３５】
ステップＳ２００７またはステップＳ２００８のつぎに、対象ＣＰＵが、対象スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）＞選択スレッドの実処理時間であるか否かを判断する（ステップＳ２００９）。対象ＣＰＵが、対象スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）＞選択スレッドの処理時間でないと判断した場合（ステップＳ２００９：Ｎｏ）、Ｔ１’＝Ｔ１’＋ｎ１’×ｔ１’とし（ステップＳ２０１０）、ステップＳ２００３へ戻る。対象スレッドの処理時間は、スレッド依存関係情報３００から対象スレッドの識別情報に基づいて特定される。
【０１３６】
対象ＣＰＵが、対象スレッドの処理時間×（基準クロック周波数／オーバークロック周波数）＞選択スレッドの処理時間であると判断した場合（ステップＳ２００９：Ｙｅｓ）、Ｔ１’＝Ｔ１’＋選択スレッドの処理時間とし（ステップＳ２０１１）、ステップＳ２００３へ戻る。ステップＳ２００４において、対象ＣＰＵが、仮割当先ＣＰＵに割当済のスレッドおよび対象スレッドのうち、未選択のスレッドがないと判断した場合（ステップＳ２００４：Ｎｏ）、Ｔ１’＝Ｔ０となるｔ１’を算出し（ステップＳ２０１２）、解があるか否かを判断する（ステップＳ２０１３）。Ｔ１’＝Ｔ０となるｔ１’を算出するとは、具体的には、たとえば、上記式（５）＝Ｔ０の一次方程式の解を算出することである。
【０１３７】
対象ＣＰＵが、解があると判断した場合（ステップＳ２０１３：Ｙｅｓ）、ｔ１’＜ｔ１であるか否かを判断する（ステップＳ２０１４）。対象ＣＰＵが、ｔ１’＜ｔ１でないと判断した場合（ステップＳ２０１４：Ｎｏ）、ｎ１’とｔ１’とを関連付けて出力し（ステップＳ２０１５）、ｎ１’＝ｎ１’＋１とし（ステップＳ２０１６）、ステップＳ２００３へ戻る。出力形式としては、たとえば、対象ＣＰＵがアクセス可能な記憶装置に記憶する。
【０１３８】
ステップＳ２０１３において、解があると判断した場合（ステップＳ２０１３：Ｎｏ）、ステップＳ２０１７へ移行する。ステップＳ２０１４において、対象ＣＰＵが、ｔ１’＜ｔ１であると判断した場合（ステップＳ２０１４：Ｙｅｓ）、ステップＳ２０１７に移行する。ステップＳ２０１３のＮｏの場合またはステップＳ２０１４のＹｅｓの場合のつぎに、実行回数が１からｎ１’−１の算出したタイムスライスから、任意のタイムスライスをｔ１’として選択し（ステップＳ２０１７）、ステップＳ１１０８へ移行する。ただし、ｎ１’＝１において、解が無い場合、何も選択されていないこととする。１からｎ１’−１の実行回数のうちのいずれの実行回数のタイムスライスが選択されるかについては任意であり、設計者が決定することとしてよい。
【０１３９】
図２２は、各ＣＰＵによる情報処理手順を示すフローチャートである。各ＣＰＵによる処理であるが、代表してＣＰＵ＃０を例に挙げて説明する。ＣＰＵ＃０が、イベントを検出したか否かを判断する（ステップＳ２２０１）。ＣＰＵ＃０が、イベントを検出していないと判断した場合（ステップＳ２２０１：Ｎｏ）、ステップＳ２２０１へ戻る。
【０１４０】
ＣＰＵ＃０が、スレッドの処理終了を検出したと判断した場合（ステップＳ２２０１：スレッドの処理終了）、実行可能なスレッドがあるか否かを判断する（ステップＳ２２０２）。ＣＰＵ＃０が、実行可能なスレッドがないと判断した場合（ステップＳ２２０２：Ｎｏ）、ステップＳ２２０１へ戻る。ＣＰＵ＃０が、実行可能なスレッドがあると判断した場合（ステップＳ２２０２：Ｙｅｓ）、実行可能なスレッドから任意のスレッドを選択し（ステップＳ２２０３）、ステップＳ２２０４へ移行する。
【０１４１】
ＣＰＵ＃０が、タスクディスパッチまたはタスクスイッチを検出したと判断した場合（ステップＳ２２０１：タスクディスパッチまたはタスクスイッチ）、イベントが検出されたスレッドまたは選択したスレッドが後続スレッドを有するか否かを判断する（ステップＳ２２０４）。ＣＰＵ＃０が、イベントが検出されたスレッドまたは選択したスレッドが後続スレッドを有すると判断した場合（ステップＳ２２０４：Ｙｅｓ）、クロック供給回路２１０にオーバークロック周波数の設定を通知する（ステップＳ２２０５）。
【０１４２】
ＣＰＵ＃０が、イベントが検出されたスレッドまたは選択したスレッドが後続スレッドを有さないと判断した場合（ステップＳ２２０４：Ｎｏ）、変更部５０７により、クロック供給回路２１０に基準クロック周波数の設定を通知する（ステップＳ２２０６）。周波数の設定通知については、具体的には、ＣＰＵの識別情報と、周波数と、を関連付けてクロック供給回路２１０に送信する。
【０１４３】
ステップＳ２２０５またはステップＳ２２０６のつぎに、ＣＰＵ＃０が、周波数の変更完了を受信したか否かを判断する（ステップＳ２２０７）。ＣＰＵ＃０が、周波数の変更完了を受信していないと判断した場合（ステップＳ２２０７：Ｎｏ）、ステップＳ２２０７へ戻る。ＣＰＵ＃０が、周波数の変更完了を受信したと判断した場合（ステップＳ２２０７：Ｙｅｓ）、実行開始し（ステップＳ２２０８）、ステップＳ２２０１へ戻る。
【０１４４】
図２３は、クロック供給回路２１０による設定処理手順を示すフローチャートである。クロック供給回路２１０が、周波数の設定通知を受信したか否かを判断する（ステップＳ２３０１）。そして、クロック供給回路２１０が、周波数の設定通知を受信していないと判断した場合（ステップＳ２３０１：Ｎｏ）、ステップＳ２３０１へ戻る。
【０１４５】
一方、クロック供給回路２１０が、周波数の設定通知を受信したと判断した場合（ステップＳ２３０１：Ｙｅｓ）、設定通知の送信元ＣＰＵへ供給する周波数を該設定通知に含まれる周波数に設定する（ステップＳ２３０２）。クロック周波数の設定については、上述したように、クロック供給回路２１０が各ＣＰＵからクロック周波数の設定通知を受信すると、受信したＣＰＵの識別情報に対応するフラグを受信したフラグの設定値に設定する。そして、クロック供給回路２１０が、周波数の変更完了を通知する（ステップＳ２３０３）。
【０１４６】
また、実施例１および実施例２ではＴ０とＴ１とが一致するタイムスライスは計算式で算出されているが、これに限らず、タイムスライスを所定時間ごとに変化させながら、Ｔ０とＴ１が一致するタイムスライスが特定されてもよい。
【０１４７】
以上説明したように、マルチタスクスケジューリング方法、およびマルチコアプロセッサシステムによれば、第１のＣＰＵに割り当てられた先行スレッドの実行終了が第２のＣＰＵに割り当てられた、後続スレッドの生成元スレッドの実行終了以前か否かを判断する。すなわち、後続スレッドの実行開始を生成元スレッドの実行終了として、第１のＣＰＵに割り当てられた先行スレッドの実行終了が生成元スレッドの実行終了以前となるように、各ＣＰＵのタイムスライスを調整する。これにより、プログラムコードが不要となり、実行待ちによって性能劣化させずにスレッド間で定義された実行順序を保つことができる。
【０１４８】
また、第１時間が第２時間と実質的に等しくなるように第１のＣＰＵのタイムスライスを計算することにより、先行スレッドの処理終了後に、後続スレッドを実行させることができるため、実行順序を保つことができる。
【０１４９】
また、第１時間が第２時間と実質的に等しくなる第１のＣＰＵのタイムスライスが計算により得られなかった場合、後続スレッドを先行スレッドと同様に第１のＣＰＵに割り当てる。これにより、先行スレッドと後続スレッドとをシングルコアプロセッサシステムで実行させることと同一となり、実行順序を保つことができる。
【０１５０】
また、第１時間が第２時間と実質的に等しくなるように第１のＣＰＵのタイムスライスが調整された場合、後続スレッドを負荷が最小であるＣＰＵに割り当てる。これにより、先行スレッドと後続スレッドと生成元スレッドとを含むプロセスの処理時間を短縮させることができる。
【０１５１】
また、先行スレッドが実行される間、第１のＣＰＵに供給するクロックのクロック周波数を他のスレッドを実行時のクロック周波数よりも早くする。これにより、先行スレッドの実処理時間を短縮させることができる。さらに、先行スレッドが実行される間のみクロック周波数を早くし、他のスレッドが実行される間はクロック周波数を早くしないことで、省電力化を図ることができる。
【０１５２】
また、スレッド依存関係情報に基づいて後続スレッドを検出する。これにより、スケジューリング時に後続スレッドを有するプロセスのコードを解析する処理を省くことができ、該プロセスの処理時間を短縮させることができる。
【０１５３】
なお、マルチタスクスケジューリング方法は、予め用意されたプログラムをマルチコアプロセッサのうちのいずれかのコアで実行することにより実現することができる。また、該プログラムは、フラッシュＲＯＭなどのＣＰＵ＃０またはＣＰＵ＃１が読み取り可能な記録媒体に記録され、ＣＰＵ＃０またはＣＰＵ＃１によって記録媒体から読み出されることによって実行されてもよい。また、該プログラムは、インターネット等のネットワークを介して配布されてもよい。
【符号の説明】
【０１５４】
２００  マルチコアプロセッサシステム
３００  スレッド依存関係情報
５０１  割当部
５０２  検出部
５０３  第１の算出部
５０４  第２の算出部
５０５  タイムスライス算出部
５０６  設定部
５０７  変更部
【図１】
2012093496.tif 000006
【図２】
2012093496.tif 000007
【図３】
2012093496.tif 000008
【図４】
2012093496.tif 000009
【図５】
2012093496.tif 000010
【図６】
2012093496.tif 000011
【図７】
2012093496.tif 000012
【図８】
2012093496.tif 000013
【図９】
2012093496.tif 000014
【図１０】
2012093496.tif 000015
【図１１】
2012093496.tif 000016
【図１２】
2012093496.tif 000017
【図１３】
2012093496.tif 000018
【図１４】
2012093496.tif 000019
【図１５】
2012093496.tif 000020
【図１６】
2012093496.tif 000021
【図１７】
2012093496.tif 000022
【図１８】
2012093496.tif 000023
【図１９】
2012093496.tif 000024
【図２０】
2012093496.tif 000025
【図２１】
2012093496.tif 000026
【図２２】
2012093496.tif 000027
【図２３】
2012093496.tif 000028
【国際調査報告】
2012093496.tif 000029
2012093496.tif 000030
2012093496.tif 000031