(57)【要約】【課題】リソースの貸し出しを管理するデータベースにおいて、需要の変化に応じてロック方法を決定すること。【解決手段】需要マップ維持処理部１５が需要マップを維持し、供給マップ維持処理部１６が供給マップを維持する。そして、割り当てマップ維持処理部１７が、需要マップと供給マップを用いて割り当てマップを維持する。そして、衝突確率マップ維持処理部１８が、供給マップと割り当てマップを用いて衝突確率マップを維持する。そして、ロック戦略切り替え処理部１９が、衝突確率マップを用いてリソースプールＤＢ２のロック方法を決定する。【選択図】図２
2017078981.tif 000002
【特許請求の範囲】
【請求項１】
リソースを提供する領域を複数の領域に分割し、分割した領域毎にリソースの数及びユーザの要求数をそれぞれ供給マップ及び需要マップとして記憶し、
前記需要マップに変化があった場合に、分割した領域毎のリソースの数とユーザの要求数を基に、リソースの取り合いの確率を示す衝突確率を算出し、
リソースの使用状況を管理するリソースデータベースにおけるロック方法を、算出した衝突確率に応じて、分割した領域毎に決定する
処理をコンピュータに実行させることを特徴とする排他切り替えプログラム。
【請求項２】
前記供給マップに変化があった場合にも、前記衝突確率を算出する処理を前記コンピュータに実行させることを特徴とする請求項１に記載の排他切り替えプログラム。
【請求項３】
前記リソースは、地理的に移動するリソースであり、
リソースの地理的移動の制約を利用して、分割した領域の一部に関して前記衝突確率を算出する処理を前記コンピュータに実行させることを特徴とする請求項２に記載の排他切り替えプログラム。
【請求項４】
前記需要マップのユーザの要求数の有無を基に、分割した領域の一部に関して前記衝突確率を算出する処理を前記コンピュータに実行させることを特徴とする請求項１、２又は３に記載の排他切り替えプログラム。
【請求項５】
コンピュータが、
リソースを提供する領域を複数の領域に分割し、分割した領域毎にリソースの数及びユーザの要求数をそれぞれ供給マップ及び需要マップとして記憶し、
前記需要マップに変化があった場合に、分割した領域毎のリソースの数とユーザの要求数を基に、リソースの取り合いの確率を示す衝突確率を算出し、
リソースの使用状況を管理するリソースデータベースにおけるロック方法を、算出した衝突確率に応じて、分割した領域毎に決定する
処理を実行することを特徴とする排他切り替え方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、排他切り替えプログラム及び排他切り替え方法に関する。
【背景技術】
【０００２】
地理的な領域においてユーザの要求するリソースを貸し出すサービスがある。例えば、リソースは温度センサを備えたスマートフォンであり、ユーザは地域の平均温度を算出して提供する企業である。企業は、平均温度を提供したい地域のスマートフォンを借りて温度データを収集し、平均温度を算出して提供する。他の例では、リソースは車載の表示装置であり、ユーザは広告を出したい企業である。企業は、広告を出したい地域の車載の表示装置を借りて広告を表示する。
【０００３】
サービス提供者は、予め領域毎にリソースを管理し、ユーザのリソース要求に含まれる領域のリソースを貸し出す。このとき、リソースは複数のユーザで利用されるため、サービス提供者はリソースを貸し出す場合に排他制御を行う必要がある。
【０００４】
図２２は、リソースの排他制御を説明するための図である。図２２において、リソース利用者４は、地理的な領域９においてリソース３を必要な数だけ要求する。リソース提供者８は、提供するリソース３をサービス提供者に登録する。図２２に示すように、リソース３ａは、２人のリソース利用者４がそれぞれリソース３を要求した２つの領域にある。したがって、リソース３ａについては、２人のリソース利用者４の間で取り合いが発生する可能性がある。
【０００５】
このようなリソース３の取り合いが発生すると、リソースを管理するデータベースにおいて衝突が発生する。図２３は、リソースプールＤＢにおける衝突を説明するための図である。ここで、リソースプールＤＢとは、リソース３の情報を記憶するデータベースである。リソースプールＤＢは、リソース３を識別する識別子を用いてリソース３の貸し出し状況を記憶する。図２３では、resource_idはリソース３を識別する識別子であり、use_stateはリソース３の貸し出し状況を示す情報である。リソース３の貸し出し状況を示す情報には、貸し出し中であることを示す「used」と貸し出されていないことを示す「free」がある。
【０００６】
図２３に示すように、resource_idが「resource_02」であるリソース３は、貸し出し中ではないが、利用者Ａと利用者Ｂから割り当てを要求されている。このため、リソースプールＤＢにおいて「resource_02」へのアクセスに関して衝突が発生し、データベースの一貫性を確保するための排他制御が必要になる。
【０００７】
データベースの一貫性を確保するための排他制御には、悲観ロックと楽観ロックがある。図２４は、悲観ロックと楽観ロックを説明するための図である。図２４（ａ）は悲観ロックを示し、図２４（ｂ）は衝突がない場合の楽観ロックを示し、図２４（ｃ）は衝突がある場合の楽観ロックを示す。図２４において、ＤＢはデータベースを示し、アクセスＡ及びアクセスＢはＤＢのデータへのアクセスを示す。また、「Access」はデータベースへのアクセスを表し、「ObjectA」及び「ObjectB」はアクセスされるデータを表し、「Success」はアクセスの成功を表し、「Abort」はアクセスの失敗を表し、「additional」は衝突がない場合と比較して余分にかかる時間を表す。
【０００８】
図２４（ａ）に示すように、悲観ロックでは、アクセスに衝突が発生した場合に、後のアクセスは、先のアクセスが完了するまで待たされる。すなわち、アクセスＡによる「ObjectA」へのアクセスが発生し、アクセスＡによる「ObjectA」へのアクセスが完了しないうちにアクセスＢによる「ObjectA」へのアクセスが発生すると、アクセスＢはアクセスＡが完了するまで待たされる。このため、アクセスＢによるアクセスは、アクセスＡの「Success」後に開始され、待ち時間の分だけ余分な時間がかかる。
【０００９】
図２４（ｂ）に示すように、衝突がない場合の楽観ロックでは、後のアクセスは、先のアクセスが完了するまで待たされることなく実行され、成功する。すなわち、アクセスＡによる「ObjectA」へのアクセスが発生し、アクセスＡによる「ObjectA」へのアクセスが完了しないうちにアクセスＢによる「ObjectB」へのアクセスが発生しても、アクセスＢはアクセスＡが完了するまで待たされることはない。このため、アクセスＢによるアクセスは、待ち時間なしに実行され、余分な時間がかからない。
【００１０】
図２４（ｃ）に示すように、衝突がある場合の楽観ロックでは、後のアクセスは、先のアクセスが完了するまで待たされることなく実行されるが、失敗する。したがって、後のアクセスは再度実行される必要がある。すなわち、アクセスＡによる「ObjectA」へのアクセスが発生し、アクセスＡによる「ObjectA」へのアクセスが完了しないうちにアクセスＢによる「ObjectA」へのアクセスが発生しても、アクセスＢはアクセスＡが完了するまで待たされることはない。しかしながら、衝突のためアクセスＢによるアクセスは失敗し、失敗が通知された後で再度アクセスＢによるアクセスが行われるため、アクセスＢによるアクセスは１回のアクセス時間分だけ余分な時間がかかる。
【００１１】
したがって、悲観ロックと楽観ロックの処理時間には、
衝突がない場合の楽観ロック＜悲観ロック＜衝突がある場合の楽観ロック
という関係がある。すなわち、衝突が高頻度で発生する場合には悲観ロックの方が処理時間が短くなる可能性が高く、衝突が低頻度で発生する場合には楽観ロックの方が処理時間が短くなる可能性が高い。
【００１２】
このため、データベースのテーブル又は行単位で衝突頻度を予測し、楽観ロックと悲観ロックを切り替える技術がある。また、アクセスの傾向、負荷に応じてロック形式を動的に選択することで、性能を向上させる技術がある。また、トランザクションのコミットが失敗であった場合の再実行までの待時間を計算し、トランザクションのコミットが失敗であった場合に、待時間が経過するまでトランザクションの再実行を待機させることで、マシンリソース消費量増加を抑制する技術がある。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００９−３７５４４号公報
【特許文献２】特開２０１３−４５３５６号公報
【非特許文献】
【００１４】
【非特許文献１】M.  Sheikhan  and  S.  Ahmadluei,“An  intelligent  hybrid  optimistic/pessimistic  concurrency  control  algorithm  for  centralized  database  systems  using  modified  GSA-optimized  ART  neural  model,”Neural  Comput  &  Applic  (2013)  23:1815-1829.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
リソース３の貸し出し情報を記憶するデータベースでは、衝突頻度に影響を与える要素がリアルタイムにかつ予測不能に変化する。すなわち、データベース上の同じ行で管理される同じリソース３でも、リソース３が要求される確率は、リソース３の使用を希望する利用者の数が変化すると変化する。例えば、駅前でイベントがある場合には、駅前のリソース３の使用を希望する利用者が一時的に増大し、衝突頻度が一時的に増加する。したがって、リソースの貸し出し情報を記憶するデータベースでは、楽観ロックと悲観ロックの切り替えを衝突頻度の予測に基づいて行うことができないという問題がある。
【００１６】
本発明は、１つの側面では、リソースの貸し出し情報を記憶するデータベースにおいて、需要の変化に応じてロック方法を決定することを目的とする。
【課題を解決するための手段】
【００１７】
本願の開示する排他切り替えプログラムは、１つの態様において、リソースを提供する領域を複数の領域に分割し、分割した領域毎にリソースの数及びユーザの要求数をそれぞれ供給マップ及び需要マップとして記憶する処理をコンピュータに実行させる。そして、前記排他切り替えプログラムは、前記需要マップに変化があった場合に、分割した領域毎のリソースの数とユーザの要求数を基に、リソースの取り合いの確率を示す衝突確率を算出する処理を前記コンピュータに実行させる。そして、前記排他切り替えプログラムは、リソースの使用状況を管理するリソースデータベースにおけるロック方法を、算出した衝突確率に応じて、分割した領域毎に決定する処理を前記コンピュータに実行させる。
【発明の効果】
【００１８】
１実施態様によれば、需要の変化に応じてロック方法を決定することができる。
【図面の簡単な説明】
【００１９】
【図１Ａ】図１Ａは、実施例に係るリソース割り当てシステムの構成を示す第１の図である。
【図１Ｂ】図１Ｂは、実施例に係るリソース割り当てシステムの構成を示す第２の図である。
【図２】図２は、リソース割り当て装置の機能構成を示す図である。
【図３】図３は、セルへの分割を説明するための図である。
【図４】図４は、需要マップの一例を示す図である。
【図５】図５は、需要マップの更新例を示す図である。
【図６】図６は、供給マップの一例を示す図である。
【図７】図７は、供給マップの更新例を示す図である。
【図８】図８は、割り当てマップの一例を示す図である。
【図９】図９は、割り当てマップの作成例を示す図である。
【図１０】図１０は、割り当てマップを更新する方法を説明するための図である。
【図１１】図１１は、衝突確率マップの一例を示す図である。
【図１２】図１２は、ロック戦略マップの一例を示す図である。
【図１３】図１３は、衝突確率マップ及びロック戦略マップの作成例を示す図である。
【図１４】図１４は、マップ間の相関関係を示す図である。
【図１５】図１５は、リソース登録処理のフローを示すフローチャートである。
【図１６】図１６は、リソース割り当て処理のフローを示すフローチャートである。
【図１７】図１７は、リソース状態情報の更新処理のフローを示すフローチャートである。
【図１８】図１８は、リソース再割り当て処理のフローを示すフローチャートである。
【図１９】図１９は、需要マップの変化を確認した場合に割り当てマップ及び衝突確率マップを維持する処理のフローを示すフローチャートである。
【図２０】図２０は、供給マップの変化を確認した場合に割り当てマップ及び衝突確率マップを維持する処理のフローを示すフローチャートである。
【図２１】図２１は、実施例に係る排他切り替えプログラムを実行するコンピュータのハードウェア構成を示す図である。
【図２２】図２２は、リソースの排他制御を説明するための図である。
【図２３】図２３は、リソースプールＤＢにおける衝突を説明するための図である。
【図２４】図２４は、悲観ロックと楽観ロックを説明するための図である。
【発明を実施するための形態】
【００２０】
以下に、本願の開示する排他切り替えプログラム及び排他切り替え方法の実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例】
【００２１】
まず、実施例に係るリソース割り当てシステムの構成について説明する。図１Ａは、実施例に係るリソース割り当てシステムの構成を示す第１の図であり、図１Ｂは、実施例に係るリソース割り当てシステムの構成を示す第２の図である。
【００２２】
図１Ａに示すように、リソース割り当てシステム１０ａでは、無線通信と有線通信の境界に配置されるゲートウェイ６において、リソース３の割り当てが管理される。ゲートウェイ６はリソース割り当て装置１を有し、リソース割り当て装置１はリソースプールＤＢ２を有する。リソース割り当て装置１は、リソースプールＤＢ２を用いてリソース３の割り当てを管理する。また、リソース割り当て装置１は、リソースプールＤＢ２のロック方法を切り替える。リソースプールＤＢ２は、リソース３の割り当て情報を記憶するデータベースである。
【００２３】
リソース３は、リソース割り当て装置１と無線通信を用いて通信する。無線通信は、例えばＷｉＦｉ（Wireless  Fidelity）、３Ｇ（3rd  Generation：第３世代通信）、ＬＴＥ（Long  Term  Evolution）である。リソース３は、例えばスマートフォン、タブレット端末、ノート型パソコンである。リソース利用者４は、直接又はインターネット５を介してリソース割り当て装置１と通信する。
【００２４】
図１Ｂに示すように、リソース割り当てシステム１０ｂでは、データセンタ等のクラウド７において、リソースの割り当てが管理される。クラウド７は、リソース割り当て装置１を有する。リソース３は、基地局６ａ及びインターネット５を介してリソース割り当て装置１と通信する。リソース利用者４は、直接又はインターネット５を介してリソース割り当て装置１と通信する。
【００２５】
なお、リソース割り当て装置１は、ゲートウェイ６、クラウド７以外にも、リソース３及びリソース利用者４と通信可能な場所に配置されてよい。
【００２６】
次に、リソース割り当て装置１の機能構成について説明する。図２は、リソース割り当て装置１の機能構成を示す図である。図２に示すように、リソース割り当て装置１は、リソースプールＤＢ２と、リソース情報登録／更新処理部１１と、対リソース通信部１２と、リソース割り当て処理部１３と、対利用者通信部１４とを有する。また、リソース割り当て装置１は、需要マップ維持処理部１５と、供給マップ維持処理部１６と、割り当てマップ維持処理部１７と、衝突確率マップ維持処理部１８と、ロック戦略切り替え処理部１９と、ＤＢＩ／Ｆ２０と、定期実行デーモン部２１とを有する。なお、図２において、点線は制御信号を示し、実線は通信の流れを示し、破線はデータの流れを示す。
【００２７】
リソース情報登録／更新処理部１１は、リソース提供者８が提供するリソース３の情報を対リソース通信部１２を介してリソース３から取得し、取得したリソース情報をＤＢＩ／Ｆ２０に渡してリソース情報のリソースプールＤＢ２への登録及び更新を要求する。また、リソース情報登録／更新処理部１１は、取得したリソース情報を供給マップ維持処理部１６に渡す。リソース情報登録／更新処理部１１は、リソース３からリソース３の登録要求とリソース３の位置情報の更新通知を受信する。対リソース通信部１２は、リソース３との間で通信を行う。
【００２８】
リソース割り当て処理部１３は、リソース利用者４からリソース割り当て要求を対利用者通信部１４を介して受け取り、リソース割り当て要求に基づいてリソース３をリソース利用者４に割り当てる。そして、リソース割り当て処理部１３は、割り当てたリソース３の確保をＤＢＩ／Ｆ２０に要求する。また、リソース割り当て処理部１３は、受け取ったリソース割り当て要求を需要マップ維持処理部１５に渡す。対利用者通信部１４は、リソース利用者４との間で通信を行う。
【００２９】
リソースプールＤＢ２は、リソース３の情報をセルに対応付けて記憶する。ここで、セルとは、リソース３の分布する領域が一定の大きさに分割された領域である。図３は、セルへの分割を説明するための図である。リソース３の分布する領域は、例えば緯度経度を基準に一定の間隔で区切ることによって、セル３１に分割される。図３では、リソース３の分布する領域は、緯度方向（ｙ方向）と経度方向（ｘ方向）に一定の間隔で区切ることによって、セル３１に分割される。
【００３０】
セル３１の大きさは、リソース３が短時間で複数のセル３１にまたがって移動しない程度とする。リソース利用者４には、利用するリソース３の範囲をセル基準で指定させてもよいし、緯度経度で指定させてもよい。緯度経度での指定は、セル基準に変換される。
【００３１】
需要マップ維持処理部１５は、リソース利用者４によるリソース３の利用の変化を示すリソース３の需要の変化に基づいて需要マップを維持する処理を行う。ここで、需要マップとは、セル３１毎の需要を示すテーブルであり、需要マップ維持処理部１５内で記憶部に記憶される。
【００３２】
図４は、需要マップの一例を示す図である。図４に示すように、需要マップは、ｘ(経度)とｙ(緯度)の組に需要を対応付ける。ここで、ｘ(経度)はｘ方向のセル３１の位置を示し、ｙ(緯度)はｙ方向のセル３１の位置を示す。需要は、需要の数で表される。例えば、ｘ方向の位置が「１」であり、ｙ方向の位置が「１」であるセル３１の需要の数は「１０．０」である。なお、以下では、ｘ方向の位置が「ｐ」であり、ｙ方向の位置が「ｑ」であるセル３１の位置を（ｐ，ｑ）で表すこととする。
【００３３】
需要マップ維持処理部１５は、リソース割り当て処理部１３からリソース３の割り当て要求を受け取ると、割り当て範囲に含まれるセル３１の需要マップを更新する。図５は、需要マップの更新例を示す図である。図５は、（１＜＝ｘ＜＝２）、（１＜＝ｙ＜＝２）の範囲で８台の割り当て要求を受けた場合の更新例を示す。（１＜＝ｘ＜＝２）、（１＜＝ｙ＜＝２）の範囲には４つのセル３１が含まれるため、需要マップ維持処理部１５は、４つのセル３１のそれぞれの需要に８／４＝２を加える。例えば、（１，１）のセル３１の需要の数は、「８．０」から「１０．０」に更新される。
【００３４】
供給マップ維持処理部１６は、リソース提供者８によるリソース３の提供の変化を示すリソース３の供給の変化に基づいて供給マップを維持する処理を行う。ここで、供給マップとは、セル３１毎の供給を示すテーブルであり、供給マップ維持処理部１６内で記憶部に記憶される。図６は、供給マップの一例を示す図である。図６に示すように、供給マップは、ｘ(経度)とｙ(緯度)の組に供給を対応付ける。供給は、供給されるリソース３の数で表される。例えば、（１，１）のセル３１で供給されるリソース３の数は「２０．０」である。
【００３５】
供給マップ維持処理部１６は、リソース情報登録／更新処理部１１からリソース３の位置情報の更新通知を受け取ると、更新通知に関係するセル３１の供給マップを更新する。図７は、供給マップの更新例を示す図である。図７は、１つのリソース３が、（１，１）のセル３１から（１，２）のセル３１へ移動した場合の更新例を示す。図７に示すように、（１，１）のセル３１の供給が「２１．０」から１減らされて「２０．０」に更新され、（１，２）のセル３１の供給が「５．０」から１増やされて「６．０」に更新される。
【００３６】
割り当てマップ維持処理部１７は、需要マップと供給マップに基づいて割り当てマップを維持する処理を行う。ここで、割り当てマップとは、ある領域にリソース３の割り当て要求があった場合にその領域に含まれる各セル３１の割り当て数を示すテーブルであり、割り当てマップ維持処理部１７内の記憶部に記憶される。図８は、（１＜＝ｘ＜＝２）、（１＜＝ｙ＜＝２）の範囲で８台の割り当て要求を受けた場合の割り当てマップの一例を示す図である。図８に示すように、割り当てマップは、ｘ(経度)とｙ(緯度)の組に割り当て数を対応付ける。例えば、（１，１）のセル３１における割り当て数は「２．０８」である。
【００３７】
割り当てマップ維持処理部１７は、定期的に需要マップ及び供給マップの変化を確認し、需要マップ又は供給マップに変化があると、新たに割り当てマップを作成する。図９は、割り当てマップの作成例を示す図である。割り当てマップ維持処理部１７は、各セル３１に関して、ｍxy＝需要／供給を計算し、ｍxyに基づいて選択比率ｎxy＝ｓｕｍ(ｍxy)−ｍxyを計算する。ここで、ｓｕｍは、対象セル３１の値の総和であり、対象セル３１は、リソース３の割り当てが要求された領域に含まれるセル３１である。そして、割り当てマップ維持処理部１７は、各セル３１の割り当て数ａxyをａxy＝ｋ×(ｎxy／ｓｕｍ(ｎxy))により計算する。ここで、ｋは要求されたリソース３の台数である。
【００３８】
例えば、（１＜＝ｘ＜＝２）、（１＜＝ｙ＜＝２）の範囲で８台の割り当て要求を受けた場合、（１，１）のセル３１については、ｍ11＝１０．０／２０．０＝１／２、ｎ11＝ｓｕｍ(ｍ11)−ｍ11＝(１／２＋２／３＋３／５＋１／２)−１／２＝１．７７となる。そして、ａ11＝８×(１．７７／(１．７７＋１．６＋１．６７＋１．７７))＝２．０８となる。なお、（１，３）のセル３１については、需要がないので、割り当て数は計算されない。すなわち、割り当てマップ維持処理部１７は、需要がないセル３１については、割り当て数を計算しない。
【００３９】
割り当てマップ維持処理部１７は、定期的に供給マップの変化を確認し、供給マップに変化があると、割り当てマップを更新するが、全セル３１の変化を確認して割り当て数を更新すると、処理に時間がかかる。このため、割り当てマップ維持処理部１７は、毎回全セル３１の変化を確認するのではなく、例えば、１回に半分のセル３１の変化を確認して割り当てマップを更新する。
【００４０】
図１０は、１回に半分のセル３１の変化を確認して割り当てマップを更新する方法を説明するための図である。図１０において、Ｓxyは、時刻ｔ1における（ｘ，ｙ）のセル３１のリソース３の供給数を示し、Ｓ'xyは、時刻ｔ2における（ｘ，ｙ）のセル３１のリソース３の供給数を示す。割り当てマップ維持処理部１７は、網掛けされたセル３１と網掛けされていないセル３１を交互に確認する。
【００４１】
すなわち、割り当てマップ維持処理部１７は、定期的に実行され、定期実行毎に対象セル３１を切り替える。例えば、ｔn（ｎ＞０）において定期実行が行われるとした場合、割り当てマップ維持処理部１７は、対象セル３１を以下のように設定する。
ｎ  ｍｏｄ  ２  ＝  ０のとき、
セル３１の座標が
（ｘ  ｍｏｄ  ２＝  ０  ａｎｄ  ｙ  ｍｏｄ  ２  ＝  ０）又は
（ｘ  ｍｏｄ  ２＝  １  ａｎｄ  ｙ  ｍｏｄ  ２  ＝  １）
ｎ  ｍｏｄ  ２  ＝  １のとき、
セル３１の座標が
（ｘ  ｍｏｄ  ２＝  ０  ａｎｄ  ｙ  ｍｏｄ  ２  ＝  １）又は
（ｘ  ｍｏｄ  ２＝  １  ａｎｄ  ｙ  ｍｏｄ  ２  ＝  ０）
【００４２】
図１０では、割り当てマップ維持処理部１７は、時刻ｔ1においては、網掛けされたセル３１を対象セル３１としてリソース３の供給数の変化を確認し、時刻ｔ2においては、網掛けされていないセル３１を対象セル３１としてリソース３の供給数の変化を確認する。
【００４３】
例えば、割り当てマップ維持処理部１７は、時刻ｔ2において、｜Ｓ'21−Ｓ21｜を閾値と比較し、｜Ｓ'21−Ｓ21｜＞閾値の場合に、（２，１）のセル３１の供給数が変化したと判定する。また、リソース３の移動は２次元平面上を連続に移動するという地理的移動の制約があるため、あるセル３１の供給数が変化すると、周囲のセル３１の供給数も変化した可能性が高い。そこで、割り当てマップ維持処理部１７は、供給数の変化の確認処理に関して枝刈りを行う。
【００４４】
すなわち、割り当てマップ維持処理部１７は、あるセル３１の供給数が変化したと判定すると、周囲のセル３１については閾値との比較を行うことなく、周囲のセル３１の供給数も変化したと判定する。ここで、周囲のセル３１とは、例えば、上下左右に隣接するセル３１である。ただし、供給マップの変化の確認周期（ｔ2−ｔ1）が大きすぎると、リソース３の移動が複数セル３１にわたる可能性が高くなり、枝刈りした効果が小さくなる。このため、供給マップの変化の確認周期は、リソース３の移動速度に基づいて設定される。
【００４５】
衝突確率マップ維持処理部１８は、割り当てマップに基づいて衝突確率マップを維持する処理を行う。ここで、衝突確率マップとは、リソース３の取り合いが発生する確率をセル３１に対応付けるテーブルであり、衝突確率マップ維持処理部１８内で記憶部に記憶される。リソース３の取り合いが発生する確率は、リソースプールＤＢ２において、同じデータへのアクセスの衝突が発生する確率である。
【００４６】
図１１は、衝突確率マップの一例を示す図である。図１１に示すように、衝突確率マップは、ｘ(経度)とｙ(緯度)の組に衝突確率を対応付ける。衝突確率は、割り当て数／(供給−割り当て数)である。例えば、（１，１）のセル３１における衝突確率は「４．０」である。
【００４７】
ロック戦略切り替え処理部１９は、衝突確率マップに基づいてロック戦略マップを更新し、更新結果に基づいてリソースプールＤＢ２のロック方法を更新する。ここで、ロック戦略マップとは、ロック方法をセル３１に対応付けるテーブルであり、ロック戦略切り替え処理部１９内で記憶部により記憶される。
【００４８】
図１２は、ロック戦略マップの一例を示す図である。図１２に示すように、ロック戦略マップは、ｘ(経度)とｙ(緯度)の組に戦略を対応付ける。戦略は、対応するセル３１に属するリソース３のリソースプールＤＢ２におけるロック方法である。例えば、（１，１）のセル３１における戦略は「悲観」である。なお、戦略のデフォルト値は「楽観」である。
【００４９】
図１３は、衝突確率マップ及びロック戦略マップの作成例を示す図である。図１３に示すように、供給マップと割り当てマップから衝突確率マップが作成され、衝突確率マップからロック戦略マップが作成される。ロック戦略マップの戦略は、衝突確率を閾値と比較することにより決定される。図１３では、閾値は３．０であり、（１，１）のセル３１の戦略は「悲観」であり、（１，２）及び（２，１）のセル３１の戦略は「楽観」である。
【００５０】
なお、需要がなく、割り当て数が計算されない場合には、衝突確率は計算されない。すなわち、衝突確率マップ維持処理部１８は、需要がないセル３１については、衝突確率を計算しない。また、ロック戦略切り替え処理部１９は、衝突確率が計算されていないセル３１については、前回の戦略のままとする。図１３では、（１，３）のセル３１の戦略が前回と同じ「楽観」となっている。
【００５１】
ロック戦略切り替え処理部１９は、ロック戦略マップにおいて戦略が変更になったセル３１に存在するリソース３についてリソースプールＤＢ２のロック方法を変更するようにＤＢＩ／Ｆ２０に指示する。ＤＢＩ／Ｆ２０は、リソースプールＤＢ２を管理し、リソースプールＤＢ２に対するインタフェースとして動作する。
【００５２】
定期実行デーモン部２１は、定期的に割り当てマップ維持処理部１７を起動し、需要マップ又は供給マップに変化があった場合に、割り当てマップ、衝突確率マップ、及びロック戦略マップが更新されるようにする。
【００５３】
図１４は、マップ間の相関関係を示す図である。図１４に示すように、需要マップ及び供給マップはそれぞれ独立して作成され維持される。割り当てマップは需要と供給の大小を基に計算される。衝突確率マップは割り当て数と供給の比で計算される。ロック戦略マップは衝突確率と閾値の比較により決定される。
【００５４】
なお、需要マップ維持処理部１５と供給マップ維持処理部１６と割り当てマップ維持処理部１７と衝突確率マップ維持処理部１８とロック戦略切り替え処理部１９と定期実行デーモン部２１は、リソースプールＤＢ２のロック方法を切り替える排他切り替え部１ａとして動作する。
【００５５】
次に、リソース登録処理のフローについて説明する。図１５は、リソース登録処理のフローを示すフローチャートである。なお、リソース登録処理は、リソース提供者８からのリソース３の登録要求により実行される。図１５に示すように、リソース情報登録／更新処理部１１が、登録要求を受信したリソース３をＤＢＩ／Ｆ２０を介してリソースプールＤＢ２に登録する（ステップＳ１）。そして、供給マップ維持処理部１６が、供給マップの該当セル３１をインクリメントする（ステップＳ２）。
【００５６】
このように、リソース情報登録／更新処理部１１がリソース３をリソースプールＤＢ２に登録する際に、供給マップ維持処理部１６が供給マップの該当セルをインクリメントすることで、排他切り替え部１ａは供給マップを最新の状態に維持することができる。
【００５７】
次に、リソース割り当て処理のフローについて説明する。図１６は、リソース割り当て処理のフローを示すフローチャートである。なお、リソース割り当て処理は、リソース利用者４からのリソース３の割り当て要求により実行される。図１６に示すように、需要マップ維持処理部１５が、割り当て要求に基づいて要求台数を要求範囲に含まれるセル数で除算を行い（ステップＳ１１）、需要マップの該当セル３１に除算結果を加算する（ステップＳ１２）。
【００５８】
そして、リソース割り当て処理部１３が、該当セル３１（ｘ，ｙ）について選択比率ｎxyを計算し（ステップＳ１３）、計算した選択比率ｎxyを用いて該当セル３１の割り当て数ａxyを決定する（ステップＳ１４）。そして、リソース割り当て処理部１３は、ＤＢＩ／Ｆ２０にリソースの確保を要求する（ステップＳ１５）。
【００５９】
このように、リソース割り当て処理部１３がリソース３を割り当てる際に、需要マップ維持処理部１５が需要マップの該当セル３１を更新することで、排他切り替え部１ａは需要マップを最新の状態に維持することができる。
【００６０】
次に、リソース状態情報の更新処理のフローについて説明する。図１７は、リソース状態情報の更新処理のフローを示すフローチャートである。なお、リソース状態情報更新処理は、リソース提供者８からのリソース３の状態情報の更新要求により実行される。図１７に示すように、リソース情報登録／更新処理部１１が、リソース３の状態情報の更新要求に基づいて、ＤＢＩ／Ｆ２０を介してリソースプールＤＢ２を更新する（ステップＳ２１）。
【００６１】
そして、供給マップ維持処理部１６が供給マップの該当セル３１を更新し（ステップＳ２２）、状態情報が更新されたリソース３は、割り当て済みのリソース３であるか否かを判定する（ステップＳ２３）。その結果、供給マップ維持処理部１６は、割り当て済みのリソース３でない場合には、処理を終了し、割り当て済みのリソース３である場合には、リソース再割り当て処理をトリガし（ステップＳ２４）、処理を終了する。
【００６２】
このように、リソース情報登録／更新処理部１１がリソース３の状態についてリソースプールＤＢ２を更新する際に、供給マップ維持処理部１６が供給マップの該当セル３１を更新することで、排他切り替え部１ａは供給マップを最新の状態に維持することができる。
【００６３】
図１８は、リソース再割り当て処理のフローを示すフローチャートである。リソース再割り当て処理は、リソース状態情報の更新処理から起動される。図１８に示すように、リソース情報登録／更新処理部１１は、状態情報が更新されたリソース３は、リソース利用者４の要求する条件から外れたか否かを判定し（ステップＳ３１）、外れていない場合には、処理を終了する。
【００６４】
一方、外れた場合には、リソース情報登録／更新処理部１１は、該当セル３１（ｘ，ｙ）について選択比率ｎxyを計算する（ステップＳ３２）。そして、リソース情報登録／更新処理部１１は、計算した選択比率ｎxyを用いて該当セル３１の割り当て数ａxyを決定し、割り当て数ａxyに基づいてリソース３を割り当てるセル３１を確率的に決定する（ステップＳ３３）。そして、リソース情報登録／更新処理部１１は、ＤＢＩ／Ｆ２０にリソース３の確保要求を行う（ステップＳ３４）。
【００６５】
このように、リソース情報登録／更新処理部１１は、割り当て済のリソース３が移動してリソース利用者４の要求する条件から外れた場合に、新たなリソース３を再割り当てすることで、リソース利用者４の要求をみたすことができる。
【００６６】
次に、需要マップの変化を確認した場合に割り当てマップ及び衝突確率マップを維持する処理のフローについて説明する。図１９は、需要マップの変化を確認した場合に割り当てマップ及び衝突確率マップを維持する処理のフローを示すフローチャートである。図１９に示す処理は、定期実行デーモン部２１により定期的に実行される。
【００６７】
図１９に示すように、割り当てマップ維持処理部１７は、需要マップの各セル３１について前回との差を計算し（ステップＳ４１）、差が閾値以上であるか否かを判定する（ステップＳ４２）。その結果、差が閾値以上である場合には、該当セル３１を要更新セル３１としてマークする（ステップＳ４３）。なお、要更新セル３１としてマークされたセル３１については、後述する図２０の処理で割り当てマップ及び衝突確率マップを維持する処理、ロック方法を決定する処理が行われる。
【００６８】
そして、割り当てマップ維持処理部１７は、需要マップの全てのセル３１を確認したか否かを判定し（ステップＳ４４）、確認した場合には、処理を終了し、確認していないセル３１がある場合には、ステップＳ４１に戻る。
【００６９】
このように、割り当てマップ維持処理部１７は、前回との需要の差が閾値以上であるセル３１をマークすることで、ロック方法の更新が必要なセル３１を指定することができる。
【００７０】
次に、供給マップの変化を確認した場合に割り当てマップ及び衝突確率マップを維持する処理のフローについて説明する。図２０は、供給マップの変化を確認した場合に割り当てマップ及び衝突確率マップを維持する処理のフローを示すフローチャートである。図２０に示す処理は、定期実行デーモン部２１により定期的に実行される。
【００７１】
図２０に示すように、割り当てマップ維持処理部１７は、供給マップの対象セル３１について前回との差を計算し（ステップＳ５１）、差が閾値以上であるか否かを判定する（ステップＳ５２）。ここで、対象セル３１は、１回の定期実行で差分が計算されるセル３１であり、全セル３１の半分である。そして、差が閾値以上でない場合には、割り当てマップ維持処理部１７は、ステップＳ５５へ進む。
【００７２】
一方、差が閾値以上である場合には、割り当てマップ維持処理部１７は、自身及び周囲のセル３１について需要マップの需要が１以上であるか否かを判定し（ステップＳ５３）、需要が１以上でない場合には、ステップＳ５５へ進む。一方、需要が１以上である場合には、割り当てマップ維持処理部１７は、該当セル３１を要更新セル３１としてマークする（ステップＳ５４）。
【００７３】
そして、割り当てマップ維持処理部１７は、対象セル３１を全て確認したか否かを判定し（ステップＳ５５）、確認していない対象セル３１がある場合には、ステップＳ５１に戻る。一方、対象セル３１を全て確認した場合には、割り当てマップ維持処理部１７は、現需要マップ及び現供給マップを使って割り当てマップを再計算する（ステップＳ５６）。このとき、割り当てマップ維持処理部１７は、マークされたセル３１のみを対象として再計算する。
【００７４】
そして、衝突確率マップ維持処理部１８が、現供給マップ及び再計算した割り当てマップを使って衝突確率マップを再計算する（ステップＳ５７）。このとき、衝突確率マップ維持処理部１８は、マークされたセル３１のみを対象として再計算する。そして、ロック戦略切り替え処理部１９が、衝突確率マップのそれぞれのセル３１を確認し（ステップＳ５８）、衝突確率が閾値以上であるか否かを判定する（ステップＳ５９）。
【００７５】
その結果、閾値以上である場合には、ロック戦略切り替え処理部１９は、該当セル３１に所属するリソース３を悲観ロックに設定するようＤＢＩ／Ｆ２０に指示する（ステップＳ６０）。一方、閾値以上でない場合には、ロック戦略切り替え処理部１９は、該当セル３１に所属するリソース３を楽観ロックに設定するようＤＢＩ／Ｆ２０に指示する（ステップＳ６１）。そして、ロック戦略切り替え処理部１９は、全てのセル３１を確認したか否かを判定し（ステップＳ６２）、確認していないセル３１がある場合には、ステップＳ５８に戻り、全てのセル３１を確認した場合には、処理を終了する。
【００７６】
このように、割り当てマップ維持処理部１７は、マークされたセル３１のみを対象として割り当てマップを再計算することで、効率良く割り当てマップを再計算することができる。
【００７７】
上述してきたように、実施例では、需要マップ維持処理部１５が需要マップを維持し、供給マップ維持処理部１６が供給マップを維持する。そして、割り当てマップ維持処理部１７が、需要マップと供給マップを用いて割り当てマップを維持する。そして、衝突確率マップ維持処理部１８が、供給マップと割り当てマップを用いて衝突確率マップを維持する。そして、ロック戦略切り替え処理部１９が、衝突確率マップを用いてリソースプールＤＢ２のロック方法を決定する。したがって、排他切り替え部１ａは、需要又は供給の変化に応じてリソースプールＤＢ２のロック方法を決定することができる。
【００７８】
また、実施例では、割り当てマップ維持処理部１７は、供給が変化したセル３１及びその周囲のセル３１で需要が１以上のセル３１に要更新セル３１としてマークする。そして、割り当てマップ維持処理部１７はマークされたセル３１のみを対象として割り当てマップを再計算し、衝突確率マップ維持処理部１８はマークされたセル３１のみを対象として衝突確率マップを再計算する。したがって、排他切り替え部１ａは、リソースプールＤＢ２のロック方法を決定する処理の負荷を抑えることができる。
【００７９】
なお、実施例では、排他切り替え部１ａについて説明したが、排他切り替え部１ａが有する構成をソフトウェアによって実現することで、同様の機能を有する排他切り替えプログラムを得ることができる。そこで、排他切り替えプログラムを実行するコンピュータについて説明する。
【００８０】
図２１は、実施例に係る排他切り替えプログラムを実行するコンピュータのハードウェア構成を示す図である。図２１に示すように、コンピュータ５０は、メインメモリ５１と、ＣＰＵ（Central  Processing  Unit）５２と、ＬＡＮ（Local  Area  Network）インタフェース５３と、ＨＤＤ（Hard  Disk  Drive）５４とを有する。また、コンピュータ５０は、スーパーＩＯ（Input  Output）５５と、ＤＶＩ（Digital  Visual  Interface）５６と、ＯＤＤ（Optical  Disk  Drive）５７とを有する。
【００８１】
メインメモリ５１は、プログラムやプログラムの実行途中結果などを記憶するメモリである。ＣＰＵ５２は、メインメモリ５１からプログラムを読出して実行する中央処理装置である。ＣＰＵ５２は、メモリコントローラを有するチップセットを含む。
【００８２】
ＬＡＮインタフェース５３は、コンピュータ５０をＬＡＮ経由で他のコンピュータに接続するためのインタフェースである。ＨＤＤ５４は、プログラムやデータを格納するディスク装置であり、スーパーＩＯ５５は、マウスやキーボードなどの入力装置を接続するためのインタフェースである。ＤＶＩ５６は、液晶表示装置を接続するインタフェースであり、ＯＤＤ５７は、ＤＶＤの読み書きを行う装置である。
【００８３】
ＬＡＮインタフェース５３は、ＰＣＩエクスプレス（ＰＣＩｅ）によりＣＰＵ５２に接続され、ＨＤＤ５４及びＯＤＤ５７は、ＳＡＴＡ（Serial  Advanced  Technology  Attachment）によりＣＰＵ５２に接続される。スーパーＩＯ５５は、ＬＰＣ（Low  Pin  Count）によりＣＰＵ５２に接続される。
【００８４】
そして、コンピュータ５０において実行される排他切り替えプログラムは、ＤＶＤに記憶され、ＯＤＤ５７によってＤＶＤから読出されてコンピュータ５０にインストールされる。あるいは、排他切り替えプログラムは、ＬＡＮインタフェース５３を介して接続された他のコンピュータシステムのデータベースなどに記憶され、これらのデータベースから読出されてコンピュータ５０にインストールされる。そして、インストールされた排他切り替えプログラムは、ＨＤＤ５４に記憶され、メインメモリ５１に読み出されてＣＰＵ５２によって実行される。
【００８５】
また、実施例では、リソース３が移動して供給が変化する場合について説明したが、本発明はこれに限定されるものではなく、供給が変化することなく需要だけが変化する場合にも同様に適用することができる。
【符号の説明】
【００８６】
１    リソース割り当て装置
１ａ    排他切り替え部
２    リソースプールＤＢ
３，３ａ    リソース
４    リソース利用者
５    インターネット
６    ゲートウェイ
６ａ    基地局
７    クラウド
８    リソース提供者
９    領域
１０ａ，１０ｂ    リソース割り当てシステム
１１    リソース情報登録／更新処理部
１２    対リソース通信部
１３    リソース割り当て処理部
１４    対利用者通信部
１５    需要マップ維持処理部
１６    供給マップ維持処理部
１７    割り当てマップ維持処理部
１８    衝突確率マップ維持処理部
１９    ロック戦略切り替え処理部
２０    ＤＢＩ／Ｆ
２１    定期実行デーモン部
３１    セル
５０    コンピュータ
５１    メインメモリ
５２    ＣＰＵ
５３    ＬＡＮインタフェース
５４    ＨＤＤ
５５    スーパーＩＯ
５６    ＤＶＩ
５７    ＯＤＤ
【図１Ａ】
2017078981.tif 000003
【図１Ｂ】
2017078981.tif 000004
【図２】
2017078981.tif 000005
【図３】
2017078981.tif 000006
【図４】
2017078981.tif 000007
【図５】
2017078981.tif 000008
【図６】
2017078981.tif 000009
【図７】
2017078981.tif 000010
【図８】
2017078981.tif 000011
【図９】
2017078981.tif 000012
【図１０】
2017078981.tif 000013
【図１１】
2017078981.tif 000014
【図１２】
2017078981.tif 000015
【図１３】
2017078981.tif 000016
【図１４】
2017078981.tif 000017
【図１５】
2017078981.tif 000018
【図１６】
2017078981.tif 000019
【図１７】
2017078981.tif 000020
【図１８】
2017078981.tif 000021
【図１９】
2017078981.tif 000022
【図２０】
2017078981.tif 000023
【図２１】
2017078981.tif 000024
【図２２】
2017078981.tif 000025
【図２３】
2017078981.tif 000026
【図２４】
2017078981.tif 000027