(57)【要約】  たとえば、端末（１００）が、端末（１００）が受信する処理要求に応じて端末（１００）の周辺の端末の数または端末（１００）および端末（１００）の周辺の端末の数を端末数として取得する。たとえば、端末（１００）の周辺の端末とは、端末（１００）が接続する基地局とハンドシェイクしている端末や端末（１００）が属するアドホックネットワークに属する端末である。たとえば、端末（１００）が、取得した端末数に応じて処理のスケジューリング方法を決定する。たとえば、端末（１００）が、端末数が閾値未満の場合には第１スケジューリング方法で処理をスケジューリングし、端末数が閾値以上の場合には第２スケジューリング方法で処理をスケジューリングする。
2012131922.tif 000002
【特許請求の範囲】
【請求項１】
第１装置が受信する処理要求に応じて前記第１装置の周辺の装置の数または前記第１装置および前記第１装置の周辺の装置の数を装置数として取得し、
前記第１装置のＣＰＵは前記装置数に基づいて前記処理要求に対応する処理のスケジューリング方法を決定すること、
を特徴とするスケジューリング方法。
【請求項２】
前記装置数が閾値未満の場合には第１スケジューリング方法で前記処理をスケジューリングし、
前記装置数が閾値以上の場合には第２スケジューリング方法で前記処理をスケジューリングすること、
を特徴とする請求項１に記載のスケジューリング方法。
【請求項３】
前記装置数が閾値以上の場合には、前記閾値の数以下のデータブロックに対応する第１データに対する前記処理を第１スケジューリング方法でスケジューリングし、
前記第１データ以外の第２データがある場合には前記第２データに対する前記処理を第２スケジューリング方法でスケジューリングすること、
を特徴とする請求項１に記載のスケジューリング方法。
【請求項４】
前記処理が行われるデータを複数の前記データブロックに分割し、
前記処理が完了した後に前記複数のデータブロックを結合すること、
を特徴とする請求項３に記載のスケジューリング方法。
【請求項５】
前記第１スケジューリング方法においては、分割情報と優先度情報とパラメータに基づいて前記処理のスケジューリングが行われ、
前記第２スケジューリング方法においては、分割情報と優先度情報とに基づいて前記処理のスケジューリングが行われること、
を特徴とする請求項２乃至請求項４の何れか一に記載のスケジューリング方法。
【請求項６】
前記パラメータは、前記第１装置および前記第１装置の周辺の装置のバッテリ残量または通信速度を含むこと、
を特徴とする請求項５に記載のスケジューリング方法。
【請求項７】
前記第１装置の周辺の装置の数は、前記第１装置に対応する基地局が通信可能である装置の数または前記第１装置に対応するアドホックネットワークに含まれる装置の数であること、
を特徴とする請求項１乃至請求項６の何れか一に記載のスケジューリング方法。
【請求項８】
処理を受け付けるインターフェース部と、
前記処理の受信に応じて第１装置の周辺の装置の数または前記第１装置および前記第１装置の周辺の装置の数を装置数として取得する取得部と、
前記装置数に基づいて前記処理のスケジューリング方法を設定するスケジューリング設定部と、
を含むことを特徴とするスケジューリングシステム。
【請求項９】
前記スケジューリング設定部は、
前記装置数と閾値とを比較する比較部を含むこと、
を特徴とする請求項８に記載のスケジューリングシステム。
【請求項１０】
前記処理を第１スケジューリング方法でスケジューリングする第１スケジューリング部と、
前記処理を前記第１スケジューリング方法とは異なる第２スケジューリング方法でスケジューリングする第２スケジューリング部と、
を含むことを特徴とする請求項８または請求項９に記載のスケジューリングシステム。
【請求項１１】
前記処理の対象であるデータを所定数のデータブロックに分割する分割部を含み、
前記第１スケジューリング部は前記所定数のデータブロック内の前記装置数以下のデータブロックに対する前記処理をスケジューリングし、
前記第２スケジューリング部は、前記装置数以下のデータブロック以外のデータブロックに対する前記処理をスケジューリングすること、
を特徴とする請求項１０に記載のスケジューリングシステム。
【請求項１２】
前記第１スケジューリング部は、分割情報と優先度情報とパラメータに基づいて前記処理のスケジューリングを行い、
前記第２スケジューリング部は、分割情報と優先度情報とに基づいて前記処理のスケジューリングを行うこと、
を特徴とする請求項１０または請求項１１に記載のスケジューリングシステム。
【請求項１３】
前記パラメータは、前記第１装置および前記第１装置の周辺の装置のバッテリ残量または通信速度を含むこと、
を特徴とする請求項１２に記載のスケジューリングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理の割当先を決定するスケジューリング方法、およびスケジューリングシステムに関する。
【背景技術】
【０００２】
従来、ある端末で実行中の処理を、複数の端末に分散させて処理を行う負荷分散処理の技術が知られている。たとえば、サーバの負荷分散処理において負荷が基準値以上になったら、端末からの接続要求を他のサーバに振り向ける負荷制御技術が知られている（たとえば、下記特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−２３７９３５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、アルゴリズムによっては、最適な計算ノードに処理を割り当てるスケジューリング問題を解くのにかかる計算量は、処理やノード数に対して指数関数的に増える。たとえば、ＣＰ／ＭＩＳＦ法（Ｃｒｉｔｉｃａｌ  Ｐａｔｈ／Ｍｏｓｔ  Ｉｍｍｅｄｉａｔｅ  Ｓｕｃｃｅｓｓｏｒｓ  Ｆｉｒｓｔ法）の時間複雑度は、処理の数をｍ、ノード数をＮとしたときにＯ（ｍ2＋Ｎｍ）である。そのため、計算ノード数が増えるにつれてその計算量は膨大となりスケジューリングを行うノードの処理能力を大きく超えてしまうため、時間内にスケジューリングを終えることができない問題点がある。【０００５】
本発明は、上述した従来技術による問題点を解消するため、スケジューリングの時間を短縮することができるスケジューリング方法、およびスケジューリングシステムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するため、本発明の一側面によれば、第１装置が受信する処理要求に応じて前記第１装置の周辺の装置の数または前記第１装置および前記第１装置の周辺の装置の数を装置数として取得し、前記第１装置のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）は前記装置数に基づいて前記処理要求に対応する処理のスケジューリング方法を決定するスケジューリング方法、およびスケジューリングシステムが提案される。
【発明の効果】
【０００７】
本発明の一側面によれば、スケジューリングの時間を短縮することができるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】図１は、本発明の一例を示す説明図である。
【図２】図２は、端末のハードウェア構成例を示すブロック図である。
【図３】図３は、ＯＳ２２１の機能例を示すブロック図である。
【図４】図４は、端末数の取得例を示す説明図である。
【図５】図５は、端末のパラメータ例を示す説明図である。
【図６】図６は、優先度例を示す説明図である。
【図７】図７は、描画処理のデータ６００の分割例を示す説明図である。
【図８】図８は、閾値の例を示す説明図である。
【図９】図９は、割当例を示す説明図（その１）である。
【図１０】図１０は、割当例を示す説明図（その２）である。
【図１１】図１１は、処理結果の結合例を示す説明図である。
【図１２】図１２は、ＯＳ２２１によるスケジューリング手順の一例を示すフローチャート（その１）である。
【図１３】図１３は、ＯＳ２２１によるスケジューリング手順の一例を示すフローチャート（その２）である。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、本発明にかかるスケジューリング方法、およびスケジューリングシステムの実施の形態を詳細に説明する。本実施の形態では、スケジューリングシステムの一例として携帯端末を挙げて説明する。
【００１０】
図１は、本発明の一例を示す説明図である。たとえば、端末１００が、端末１００が受信する処理要求に応じて端末１００の周辺の端末の数または端末１００および端末１００の周辺の端末の数を端末数として取得する。たとえば、端末１００が受信する処理要求は、図１では地図の描画処理である。たとえば、端末１００の周辺の端末とは、端末１００が接続する基地局とハンドシェイクしている端末や端末１００が属するアドホックネットワークに属する端末である。
【００１１】
たとえば、端末１００が、取得した端末数に応じて処理のスケジューリング方法を決定する。たとえば、端末１００が、端末数が閾値未満の場合には第１スケジューリング方法で処理をスケジューリングし、端末数が閾値以上の場合には第２スケジューリング方法で処理をスケジューリングする。
【００１２】
図１における第１スケジューリング方法では、端末１００の周辺の端末のいずれの端末にいずれの処理を割り当てるかを、周辺の端末の負荷情報や電池残量や端末１００と周辺端末との間の通信速度によって決定する。たとえば、端末１０１−１はいずれのアプリケーションも動作していないが、端末１０１−２はいくつかのアプリケーションを動作している。そこで、端末１００が、描画処理のうちの２／３の描画処理を端末１０１−１に割り当て、描画処理のうちの１／３の描画処理を端末１０１−２に割り当てる。
【００１３】
たとえば、図１における第２スケジューリング方法では、周辺の端末の能力に関係なく、処理の割当先端末を決定する。たとえば、端末１００が、描画処理を６分割し、端末１０１−１〜端末１０１−６のそれぞれに分割した１／６の描画処理を割り当てる。
【００１４】
（端末のハードウェア例）
図２は、端末のハードウェア構成例を示すブロック図である。図２において、端末２００は、ＣＰＵ２０１と、ディスプレイ２０３と、キーボード２０４と、Ｉ／Ｆ２０２（ＩｎｔｅｒＦａｃｅ）と、ＲＡＭ２０６（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、ＲＯＭ２０５（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）と、を有している。端末２００は、フラッシュＲＯＭ２０７と、フラッシュＲＯＭコントローラ２０８と、フラッシュＲＯＭ２０９と、を有している。ＣＰＵ２０１と、ディスプレイ２０３と、キーボード２０４と、Ｉ／Ｆ２０２と、ＲＡＭ２０６と、ＲＯＭ２０５と、フラッシュＲＯＭ２０７と、フラッシュＲＯＭコントローラ２０８とは、バス２１０を介して接続されている。
【００１５】
ここで、ＣＰＵ２０１は、それぞれレジスタとコアとキャッシュを有している。コアは、演算機能を有している。ＣＰＵ２０１は端末２００の全体の制御を司り、ＯＳ２２１を実行する。ＯＳ２２１はＣＰＵ２０１に割り当てられたアプリケーションの実行順序を制御する機能やアプリケーションから分散処理要求がある場合、周辺の端末に処理を割り当てる機能を有する。
【００１６】
図２では、ＯＳ２２１にアプリ２２２が割り当てられている。たとえば、アプリ２２２は、地図検索ソフトウェアとし、描画処理が発生した場合にＯＳ２２１へ分散処理要求を通知することとする。
【００１７】
ディスプレイ２０３は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。ディスプレイ２０３は、たとえば、ＴＦＴ液晶ディスプレイなどを採用することができる。キーボード２０４は、数字、各種指示などの入力のためのキーを有し、データの入力を行う。また、キーボード２０４は、タッチパネル式の入力パッドやテンキーなどであってもよい。
【００１８】
Ｉ／Ｆ２０２は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのアドホックネットワーク２１１に接続され、アドホックネットワーク２１１を介して他の端末に接続される。そして、Ｉ／Ｆ２０２は、アドホックネットワーク２１１と内部のインターフェースを司り、外部端末からのデータの入出力を制御する。Ｉ／Ｆ２０２には、たとえば、モデムやＬＡＮアダプタなどを採用することができる。
【００１９】
ＲＯＭ２０５は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ２０６は、ＣＰＵ２０１のワークエリアとして使用される。フラッシュＲＯＭ２０７は、ＯＳ２２１などのシステムソフトウェアやアプリケーションのプログラムを記憶している。ＲＡＭ２０６はフラッシュＲＯＭ２０７よりもＣＰＵ２０１からのアクセス速度が速い。
【００２０】
フラッシュＲＯＭコントローラ２０８は、ＣＰＵ２０１の制御に従ってフラッシュＲＯＭ２０９に対するデータのリード／ライトを制御する。フラッシュＲＯＭ２０９は、フラッシュＲＯＭコントローラ２０８の制御で書き込まれたデータを記憶する。データの具体例としては、端末２００を使用するユーザがＩ／Ｆ２０２を通して取得した画像データ、映像データなどである。フラッシュＲＯＭ２０９は、たとえば、メモリカード、ＳＤカードなどを採用することができる。
【００２１】
（ＯＳ２２１の機能例）
図３は、ＯＳ２２１の機能例を示すブロック図である。ＯＳ２２１は、アプリＩＦ部３０１と、端末数取得部３０２と、パラメータ取得部３０３と、分割部３０４と、スケジューリング設定部３０５と、を有する。ＯＳ２２１は、第１スケジューリング部３０６と、第２スケジューリング部３０７と、ディスパッチャー３０８と、結合部３０９と、を有する。
【００２２】
具体的には、たとえば、アプリＩＦ部３０１〜結合部３０９の処理がＯＳ２２１にコーディングされている。ＣＰＵ２０１が、ＲＯＭ２０５やフラッシュＲＯＭ２０７などの記憶装置に記憶されたＯＳ２２１を読み出し、ＯＳ２２１にコーディングされている処理を実行する。これにより、アプリＩＦ部３０１〜結合部３０９の処理が実現される。
【００２３】
図４は、端末数の取得例を示す説明図である。たとえば、ＯＳ２２１が、アプリＩＦ部３０１により、アプリ２２２から地図の描画処理の分散処理要求を受け付ける。たとえば、ＯＳ２２１が、端末数取得部３０２により、端末２００の周辺の端末の端末数を取得する。具体的には、たとえば、ＯＳ２２１が、アドホックネットワーク２１１を介して他の端末に対して通信可能かを通知する。たとえば、ＯＳ２２１が、応答のあった端末の端末数を端末２００の周辺の端末数とする。ここでは、端末４００−１〜端末４００−ｉが端末２００の周辺の端末であり、端末２００の周辺の端末の端末数は、ｉである。
【００２４】
また、上述のように、端末２００が接続する基地局とハンドシェイクしている端末２００の端末数を基地局にアクセスすることで取得し、取得結果を端末２００の周辺の端末の端末数としてもよい。
【００２５】
つぎに、たとえば、ＯＳ２２１が、パラメータ取得部３０３により、通信可能な端末４００―１〜端末４００−ｉに対して各端末のパラメータの送信依頼を通知する。端末４００―１〜端末４００−ｉは、パラメータの送信依頼を受け付けると、それぞれ端末２００へパラメータを送信する。たとえば、ＯＳ２２１が、パラメータ取得部３０３により、端末４００―１〜端末４００−ｉのそれぞれからの端末のパラメータを受け付ける。ここで、端末のパラメータとは、たとえば、電池残量、負荷情報や通信速度である。
【００２６】
図５は、端末のパラメータ例を示す説明図である。テーブル５００では、各端末の負荷情報を示している。テーブル５００は、端末ＩＤ、負荷情報のフィールドを有する。端末ＩＤは、端末の周辺の端末を識別する識別情報である。負荷情報は、各端末で実行中の処理の処理時間の合計値である。各フィールドに情報が設定されることで、端末負荷５０１−１〜端末負荷５０１−ｉがレコードとして記憶されている。
【００２７】
テーブル５１０では、各端末の電池残量を示している。テーブル５１０は、端末ＩＤ、電池残量のフィールドを有する。端末ＩＤは、端末２００の周辺の端末を識別する識別情報である。電池残量は、各端末の電池がどの程度残っているかをパーセンテージで表記した値である。各フィールドに情報が設定されることで、端末負荷５１１−１〜端末負荷５１１−ｉがレコードとして記憶されている。
【００２８】
本実施の形態では、各周辺の端末の負荷情報を用いてスケジューリングする例を説明するが、端末の電池残量を用いてスケジューリングしてもよい。また、図示していないが端末２００と端末２００の周辺の端末との間の通信速度を用いてスケジューリングしてもよい。また、端末の負荷情報と端末の電池残量と端末の通信速度とを組み合わせて判断し、スケジューリングしてもよい。
【００２９】
たとえば、ＯＳ２２１が、アプリＩＦ部３０１により、アプリ２２２から描画処理に関する優先度情報と、描画処理のデータと、分割数または分割サイズを取得する。たとえば、描画処理のデータ６００とは、描画処理に関するプログラムコードや変数や変数値が挙げられる。
【００３０】
図６は、優先度例を示す説明図である。図６では、取得した描画処理のデータ６００を大きく４つの描画処理のデータに分けている。ここでは、理解の容易化のために、描画処理のデータ６００を描画領域のように示している。描画処理のデータ６００のうち、左上の描画処理のデータの優先度が１番高く、左下の描画処理のデータの優先度が２番目に高く、右上の描画処理のデータの優先度が３番目に高く、右下の描画処理のデータの優先度が最も低い。
【００３１】
優先度情報は、描画処理うちのいずれの処理の優先度が高いかに関する情報である。具体的には、たとえば、優先度情報は、たとえば、優先度と、描画処理のデータ６００のアドレスまたはステップ番号とが関連付けられている。
【００３２】
図７は、描画処理のデータ６００の分割例を示す説明図である。たとえば、ＯＳ２２１が、取得した描画処理のデータ６００を分割数に応じて分割する。図７では、描画処理のデータ６００が、部分描画処理のデータ７００−１〜部分描画処理のデータ７００−１６の１６のデータに分割される。たとえば、分割結果は、ＲＡＭ２０６、フラッシュＲＯＭ２０７などの記憶装置に記憶される。
【００３３】
たとえば、ＯＳ２２１が、部分描画処理のデータ７００−１〜部分描画処理のデータ７００−１６のそれぞれの分割情報を作成する。図７では、分割情報群７１０は、部分描画処理のデータＩＤ、サイズのフィールドを有している。部分描画処理のデータＩＤは、部分描画処理のデータを示す識別情報である。ここでは、部分描画処理のデータＩＤと各部分描画処理のデータに付された符号とを同一としている。サイズは、部分描画処理のデータのサイズである。各フィールドに情報が設定されることで分割情報７１１−１〜分割情報７１１−１６がレコードとして記憶されている。たとえば、分割情報群７１０は、ＲＡＭ２０６、フラッシュＲＯＭ２０７などの記憶装置に記憶される。
【００３４】
つぎに、たとえば、ＯＳ２２１が、スケジューリング設定部３０５の比較部３１０により、端末２００の周辺の端末の端末数が閾値未満であるか否かを判断する。または、たとえば、ＯＳ２２１が、スケジューリング設定部３０５の比較部３１０により、端末２００と端末２００の周辺の端末との端末数が閾値未満であるか否かを判断する。ここで、図８を用いて閾値について詳細に説明する。
【００３５】
図８は、閾値の例を示す説明図である。グラフ８００では、通常スケジューリングを行った場合の処理時間と端末数の関係と、簡易スケジューリングを行った場合の処理時間と端末数の関係とを示している。ここで、処理時間とは、スケジューリング時間を含めたトータルの処理時間である。
【００３６】
ここで、通常スケジューリングとは、周辺の端末の負荷情報や周辺の端末の電池残量などに基づいて、アプリケーションの部分描画処理を割り当てる割当先端末を決定することを示している。ここで、簡易スケジューリングとは、周辺の端末の負荷情報や周辺の端末の電池残量などに関わらず、順にアプリケーションの部分描画処理を割り当てる割当先端末を決定することを示している。
【００３７】
上述したように、スケジューリング・アルゴリズムでは、処理時間は理想的には計算ノード数に反比例して減少するが、スケジューリング時間は指数関数的に増加する。そのため、トータルの時間は、たとえば、通常スケジューリングの曲線のようになる。簡易スケジューリングの場合では、スケジューリング時間は計算ノード数に関わらずほぼ一定になるが処理の割り当ては最適とはならないため処理時間には不適切な端末に処理を割り当ててしまうリスクが含まれる。そのため、処理時間はリスクとコストを含めた期待値で表現される。
【００３８】
グラフ８００では、通常スケジューリングと簡易スケジューリングとが交差していることがわかる。よって、交差点（矢印の箇所）を閾値として用い、端末２００の周辺の端末の端末数が該閾値を超えた場合は簡易スケジューリングとする。たとえば、交差点の端末数が６であるため、閾値は６である。以下グラフ８００の求め方の例を示す。まず、トータルの処理時間ｔが式（１）で求められる。
【００３９】
ｔ＝ｔｓ＋ｔｐ・・・（１）
【００４０】
時間ｔｓはスケジューリングにかかる時間を表し、時間ｔｐは分割された処理一つあたりの処理にかかる時間を表す。通常スケジューリングを行う場合のｔｓが下記式（２）で求められる。
【００４１】
ｔｓ＝ｔｃ×Ｎ＾２・・・（２）
【００４２】
Ｎは、端末数であり、Ｎ＾２は、Ｎの２乗であり、時間ｔｃは、スケジューリング計算１回あたりにかかる時間である。また、通常スケジューリングを行う場合の時間ｔｐが下記式（３）で求められる。
【００４３】
ｔｐ＝Ｔ／Ｎ・・・（３）
【００４４】
時間Ｔは、処理全体を行うのにかかる時間である。つぎに、簡易スケジューリングを行う場合の時間ｔｓが下記式（４）、時間ｔｐが下式（５）で求められる。
【００４５】
ｔｓ＝ｔｃ´・・・（４）
ｔｐ＝Ｔ／Ｎ＋Ｔ／Ｎ×Ｐ×（Ｎ−１）＝Ｔ／Ｎ｛１＋Ｐ×（Ｎ−１）｝・・・（５）
【００４６】
時間ｔｃ´は簡易スケジューリング計算にかかる時間である。リスクＰは、最適なスケジューリングを行わないことによるリスクである。ｔｃ＝ｔｃ´＝５［ｍｓ］、Ｔ＝１０００［ｍｓ］、Ｐ＝２０［％］とした場合の式（１）〜式（４）を用いる計算結果が、グラフ８００に示されている。
【００４７】
ＯＳ２２１の処理の説明に戻って、たとえば、ＯＳ２２１が、スケジューリング設定部３０５によって、取得した端末数が閾値未満であると判断した場合、第１スケジューリング方法に決定する。具体的には、たとえば、第１スケジューリング方法では、ＯＳ２２１が、第１スケジューリング部３０６により、上述した通常スケジューリングを行う。すなわち、第１スケジューリング方法では、端末２００の周辺の端末のいずれの端末にいずれの処理を割り当てるかを周辺の端末の負荷情報や電池残量によって決定する。
【００４８】
たとえば、ＯＳ２２１が、スケジューリング設定部３０５によって、取得した端末数が閾値未満でないと判断した場合、割当済の部分描画処理の数が閾値未満であれば、第１のスケジューリング方法に決定する。たとえば、ＯＳ２２１が、スケジューリング設定部３０５によって、取得した端末数が閾値未満でないと判断した場合、割当済の部分描画処理の数が閾値以上であれば、閾値を超える割り当てについては第２のスケジューリング方法に決定する。具体的には、たとえば、第２スケジューリング方法では、ＯＳ２２１が、第２スケジューリング部３０７により、簡易スケジューリングを行う。
【００４９】
ここでは、ｉ≧６とし、ここでは、たとえば、ＯＳ２２１が、スケジューリング設定部３０５により、取得した端末数が閾値未満でないと判断し、第２スケジューリング方法に決定する。たとえば、ＯＳ２２１が、分割情報群７１０の分割情報を優先度情報に基づいて優先度の高い順に並び替える。並び替えられた分割情報群７１０は、ＲＡＭ２０６、フラッシュＲＯＭ２０７などの記憶装置に記憶される。
【００５０】
図９は、割当例を示す説明図（その１）である。たとえば、ＯＳ２２１が、（１）並び替えられた分割情報群７１０から順に分割情報を選択する。ここでは、分割情報７１１−１が選択される。ＯＳ２２１が、第２スケジューリング部３０７により、テーブル５００を参照し、最も負荷の軽い端末を特定する。ここでは、端末４００−１が、最も負荷情報の値が小さいので、最も負荷の軽い端末として特定される。そして、たとえば、ＯＳ２２１が、第２スケジューリング部３０７により、（２）特定した端末４００−１を分割情報７１１−１に関する処理の割当先端末に決定する。
【００５１】
たとえば、ＯＳ２２１が、第２スケジューリング部３０７により、（３）決定結果を割当情報９００に出力する。割当情報９００は、部分描画処理のデータＩＤ、端末ＩＤのフィールドを有する。部分描画処理のデータＩＤには、選択された分割情報７１１−１の部分描画処理のデータＩＤが登録され、端末ＩＤは、決定された割当先端末の端末ＩＤが登録される。割当情報９００の部分描画処理のデータＩＤと分割情報群７１０の部分描画処理のデータＩＤとは関連付けられていることとする。各フィールドに情報が設定されることで、割当結果９０１−１がレコードとして記憶されている。たとえば、ＯＳ２２１が、ディスパッチャー３０８により、（４）分割情報７１１−１に関する処理を決定した端末４００−１に割り当てる。
【００５２】
図１０は、割当例を示す説明図（その２）である。たとえば、ＯＳ２２１が、（１）分割情報群７１０から分割情報を選択する。閾値が６であり、分割情報群７１０から６個目の分割情報７１１−１０を選択しているため、たとえば、ＯＳ２２１が、第２スケジューリング部３０７により、簡易スケジューリングを行う。たとえば、ＯＳ２２１が、第２スケジューリング部３０７により、端末４００−２にはまだ処理が割り当てられていないため、端末４００−２を分割情報７１１−１０に関する処理の割当先端末に決定する。たとえば、ＯＳ２２１が、第２スケジューリング部３０７により、（２）決定結果を割当情報９００に出力する。これにより、割当結果９０１−６が割当情報９００に登録される。たとえば、ＯＳ２２１が、ディスパッチャー３０８により、（３）分割情報７１１−１０に関する処理を割当先端末に割り当てる。
【００５３】
図１１は、処理結果の結合例を示す説明図である。たとえば、ＯＳ２２１が、ディスパッチャー３０８により、各端末から処理結果を受け付ける。たとえば、ＯＳ２２１が、結合部３０９により、割当情報９００と分割情報群７１０に基づいて、いずれの位置の描画処理の処理結果であるかを判断する。たとえば、ＯＳ２２１が、結合部３０９により、判断結果に基づいてすべての処理結果を結合する。たとえば、ＯＳ２２１が、アプリＩＦ部３０１により、結合結果１１００をアプリ２２２へ通知する。
【００５４】
（ＯＳ２２１によるスケジューリング手順）
図１２および図１３は、ＯＳ２２１によるスケジューリング手順の一例を示すフローチャートである。まず、ＯＳ２２１が、分散処理要求を受け付け、または再スケジューリングを受け付けたか否かを判断する（ステップＳ１２０１）。ＯＳ２２１が、分散処理要求を受け付け、および再スケジューリングを受け付けたと判断しなかった場合（ステップＳ１２０１：Ｎｏ）、ステップＳ１２０１へ戻る。ＯＳ２２１が、分散処理要求を受け付け、または再スケジューリングを受け付けたと判断した場合（ステップＳ１２０１：Ｙｅｓ）、端末数取得部３０２とパラメータ取得部３０３により、周辺端末数と周辺端末のパラメータを取得する（ステップＳ１２０２）。
【００５５】
ＯＳ２２１が、アプリＩＦ部３０１により、優先度情報を分散処理要求の要求元アプリケーションから取得する（ステップＳ１２０３）。ＯＳ２２１が、分割部３０４により、分散処理要求の処理のデータを分割し（ステップＳ１２０４）、分割情報群７１０を出力する（ステップＳ１２０５）。ＯＳ２２１が、スケジューリング設定部３０５の比較部３１０により、周辺端末数＜閾値であるか否かを判断する（ステップＳ１２０６）。
【００５６】
ＯＳ２２１が、周辺端末数＜閾値であると判断した場合（ステップＳ１２０６：Ｙｅｓ）、スケジューリング設定部３０５により、第１スケジューリング方法に決定する（ステップＳ１２０７）。ＯＳ２２１が、第１スケジューリング部３０６により、優先度情報と周辺端末のパラメータに基づいて分割情報群７１０の各分割情報に関する割当先端末を決定する（ステップＳ１２０８）。ＯＳ２２１が、決定結果を割当情報９００に登録し、割当情報９００を出力する（ステップＳ１２０９）。ＯＳ２２１が、ディスパッチャー３０８により、分割情報群７１０の分割情報に関する処理を割当先端末に割り当て（ステップＳ１２１０）、一連の処理を終了する。
【００５７】
ＯＳ２２１が、周辺端末数＜閾値でないと判断した場合（ステップＳ１２０６：Ｎｏ）、分割情報群７１０の分割情報を優先度情報の優先度に基づいてソートする（ステップＳ１２１１）。
【００５８】
ＯＳ２２１が、ｎ＝０とし（ステップＳ１２１２）、分割情報群７１０のうち、未選択な分割情報があるか否かを判断する（ステップＳ１２１３）。ＯＳ２２１が、分割情報群７１０のうち、未選択な分割情報があると判断した場合（ステップＳ１２１３：Ｙｅｓ）、未選択な分割情報からソート後の順に分割情報を選択する（ステップＳ１２１４）。ＯＳ２２１が、スケジューリング設定部３０５により、ｎ＜閾値であるか否かを判断する（ステップＳ１２１５）。
【００５９】
ＯＳ２２１が、ｎ＜閾値であると判断した場合（ステップＳ１２１５：Ｙｅｓ）、スケジューリング設定部３０５により、第１スケジューリング方法に決定する（ステップＳ１２１６）。ＯＳ２２１が、選択した分割情報と各周辺端末のパラメータに基づいて分割情報に関する処理の割当先端末を決定し（ステップＳ１２１７）、ステップＳ１２２２へ移行する。ＯＳ２２１が、ｎ＜閾値でないと判断した場合（ステップＳ１２１５：Ｎｏ）、スケジューリング設定部３０５により、第２スケジューリング方法に決定し（ステップＳ１２１８）、第２スケジューリング部３０７により、周辺端末のうち、未割り当ての端末があるか否かを判断する（ステップＳ１２１９）。
【００６０】
ＯＳ２２１が、周辺端末のうち、未割り当ての端末があると判断した場合（ステップＳ１２１９：Ｙｅｓ）、第２スケジューリング部３０７により、未割り当ての端末のうちの一つの端末を分割情報に関する処理の割当先端末に決定する（ステップＳ１２２０）。ステップＳ１２２０のつぎに、ＯＳ２２１が、ステップＳ１２２２へ移行する。ＯＳ２２１が、周辺端末のうち、未割り当ての端末がないと判断した場合（ステップＳ１２１９：Ｎｏ）、第２スケジューリング部３０７により、周辺端末のうちの一つの端末を分割情報に関する処理の割当先端末に決定し（ステップＳ１２２１）、ステップＳ１２２２へ移行する。
【００６１】
ステップＳ１２１７、ステップＳ１２２０、ステップＳ１２２１のつぎに、ＯＳ２２１が、決定結果を割当情報９００に登録し、割当情報９００を出力する（ステップＳ１２２２）。ＯＳ２２１が、ディスパッチャー３０８により、分割情報に関する処理を割当先端末に割り当て（ステップＳ１２２３）、ｎ＝ｎ＋１とし（ステップＳ１２２４）、ステップＳ１２１３へ移行する。
【００６２】
ＯＳ２２１が、分割情報群７１０のうち、未選択な分割情報がないと判断した場合（ステップＳ１２１３：Ｎｏ）、一連の処理を終了する。
【００６３】
以上説明したように、スケジューリング方法、およびスケジューリングシステムによれば、周辺装置に処理を分散させる際、周辺の装置数に応じてどのスケジューリング方法が良いかを決定することで、スケジューリングの時間を短縮することができる。
【００６４】
また、装置数が閾値未満の場合には第１スケジューリング方法で処理をスケジューリングし、装置数が閾値以上の場合には第２スケジューリング方法で処理をスケジューリングする。これにより、スケジューリング方法を容易に選択でき、スケジューリングの時間を短縮することができる。
【００６５】
また、装置数が閾値以上の場合には、閾値の数以下のデータブロックに対応する第１データに対する処理を第１スケジューリング方法でスケジューリングする。第１データ以外の第２データがある場合には第２データに対する処理を第２スケジューリング方法でスケジューリングする。これにより、スケジューリングの時間が処理時間に影響を与えない範囲までは、最適なスケジューリングが実施される。これにより、スケジューリングの時間を短縮しつつ、最適なスケジューリングを行うことができる。
【００６６】
また、処理が行われるデータを複数のデータブロックに分割する。処理が完了した後に複数のデータブロックを結合する。これにより、ある端末での処理を複数の端末に分散させて実行させることができる。
【００６７】
また、第１スケジューリング方法においては、分割情報と優先度情報とパラメータに基づいて処理のスケジューリングを行う。第２スケジューリング方法においては、分割情報と優先度情報とに基づいて処理のスケジューリングを行う。これにより、スケジューリングの時間を短縮しつつ、最適なスケジューリングを行うことができる。
【００６８】
また、パラメータは、装置と周辺の装置のバッテリ残量または通信速度である。これにより、周辺の装置の状態に応じて処理を分散させることができる。
【００６９】
また、周辺の装置の数は、装置に対応する基地局が通信可能である装置の数または装置に対応するアドホックネットワークに含まれる装置の数である。これにより、容易に周辺の端末数を取得することができる。
【００７０】
なお、本実施の形態で説明したスケジューリング方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。アプリＩＦ部３０１〜結合部３０９の処理がコーディングされたスケジューリングプログラムは、たとえば、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録される。スケジューリングプログラムは、たとえば、コンピュータによって記録媒体から読み出されることによって実行される。また、スケジューリングプログラムは、インターネット等のネットワークを介して配布してもよい。
【符号の説明】
【００７１】
１００，１０１―１〜１０１−６，２００，４００−１〜４００−ｉ  端末
２０１  ＣＰＵ
２２２  アプリ
３０１  アプリＩＦ部
３０２  端末数取得部
３０４  分割部
３０５  スケジューリング設定部
３０６  第１スケジューリング部
３０７  第２スケジューリング部
７１０  分割情報群
７１１−１〜７１１−１６  分割情報
【図１】
2012131922.tif 000003
【図２】
2012131922.tif 000004
【図３】
2012131922.tif 000005
【図４】
2012131922.tif 000006
【図５】
2012131922.tif 000007
【図６】
2012131922.tif 000008
【図７】
2012131922.tif 000009
【図８】
2012131922.tif 000010
【図９】
2012131922.tif 000011
【図１０】
2012131922.tif 000012
【図１１】
2012131922.tif 000013
【図１２】
2012131922.tif 000014
【図１３】
2012131922.tif 000015
【国際調査報告】
2012131922.tif 000016
2012131922.tif 000017