JP2011170414A - ロック競合管理装置、ロック競合管理方法およびプログラム - Google Patents

Abstract

【課題】無駄なロック競合の発生が多くなり、コンピュータシステムが十分なスループットを得られないという問題を解決するロック競合管理装置を提供する。
【解決手段】検出部は、特定の計算主体がロックを獲得するためのロック獲得処理が予め設定された設定時間内に失敗した失敗回数である競合頻度を検出する。ロック獲得命令発行部１４は、検出部にて検出された失敗回数が予め設定された第一閾値以下の場合、ロック獲得処理を実行する。
【選択図】図１

Description

本発明は、ロックの競合を管理するロック競合管理装置、ロック競合管理方法およびプログラム

従来、ＣＰＵ（Central Processing Unit）のマルチコア化が進んでおり、複数のＣＰＵコアを含むマルチプロセッサ型のＣＰＵを搭載したコンピュータシステムが一般化している。これにより、コンピュータシステムは複数の計算主体（プロセスやスレッドなど）を並列に実行することが可能になり、コンピュータシステムのスループットが向上している（特許文献１および２参照）。

マルチプロセッサ型のＣＰＵを搭載したコンピュータシステムでは、複数の計算主体の共有資源を特定の計算主体が使用する場合、その特定の計算主体は、共有資源を排他的に使用する権限であるロックを獲得するためのロック獲得処理を行う。そして、ロック獲得処理が成功すると、特定の計算主体は共有資源を使用することができる。

しかしながら、複数の計算主体が特定の共有資源に対するロック獲得処理を同時に行うロック競合が発生すると、ＣＰＵはロック競合を解消するための処理を行う必要が生じ、ＣＰＵにオーバーヘッドが発生する。このため、ロック競合がボトルネックとなり、コンピュータシステムのスループットの向上が図れないことがあった。

これに対して、ロック競合を避けるための技術として、ＣＰＵの負荷などからロック競合が発生する発生確率を推定し、その発生確率が高い場合にロック獲得処理を停止する確率論的な技術がある。

特開昭６０‐１００２５９号公報 特開平２‐２６００４３号公報

近年、マルチプロセッサ型のＣＰＵでは、ＣＰＵコアが大量に搭載されており、並列に実行される計算主体の数が非常に増えている。このため、ロック競合が発生する状況が非常に複雑化してきており、ＣＰＵの負荷などからロック競合の発生確率を正確に推定することが困難になっている。このため、ロック競合を避けるための確率論的な技術では、無駄なロック競合が多くなり、コンピュータシステムが十分なスループットを得られないという問題がある。

本発明の目的は、上記の課題である、無駄なロック競合の発生が多くなり、コンピュータシステムが十分なスループットを得られないという問題を解決する、ロック競合管理装置、ロック競合管理方法およびプログラムを提供することである。

本発明によるロック競合管理装置は、プロセッサで実行される複数の計算主体の共有資源を、特定の計算主体が排他的に使用する権限であるロックの競合を管理するロック競合管理装置であって、前記特定の計算主体が前記ロックを獲得するための獲得処理が失敗するたびに、当該獲得処理が失敗した失敗回数をカウントするカウント部と、前記検出部にて検出された失敗回数が予め設定された第一閾値以下の場合、前記獲得処理を実行するロック獲得部と、を有する。

本発明によるロック競合管理方法は、プロセッサで実行される複数の計算主体の共有資源を、特定の計算主体が排他的に使用する権限であるロックの競合を管理するロック競合管理方法であって、前記特定の計算主体が前記ロックを獲得するための獲得処理が失敗するたびに、当該獲得処理が失敗した失敗回数をカウントし、前記検出された失敗回数が予め設定された第一閾値以下の場合、前記獲得処理を実行する。

本発明によるプログラムは、プロセッサで実行される複数の計算主体の共有資源を排他的に使用する権限であるロックを特定の計算主体が獲得するための獲得処理が失敗するたびに、当該獲得処理が失敗した失敗回数をカウントする手順と、前記検出された失敗回数が予め設定された第一閾値以下の場合、前記獲得処理を実行する手順と、をコンピュータに実行させる。

本発明によれば、無駄なロック競合を低減することが可能になり、コンピュータシステムが十分なスループットを得ることが可能になる。

本発明の第一の実施形態のロック競合管理装置の構成を示したブロック図である。 ロック獲得命令発行部の動作の一例を説明するためのフローチャートである。 ロック獲得命令発行部の動作の他の例を説明するためのフローチャートである。 ロック獲得命令発行部の動作の他の例を説明するためのフローチャートである。

以下、本発明の実施形態について図面を参照して説明する。

図１は、本発明の第一の実施形態のロック競合管理装置の構成を示すブロック図である。

図１で示されたロック競合管理装置１は、プロセッサで実行される計算主体の共有資源を、特定の計算主体が排他的に使用する権限であるロックを管理するものである。なお、計算主体は、プロセッサで実行されるソフトウェアのプロセスやスレッドなどである。また、プロセッサは、複数のＣＰＵコアを含むマルチプロセッサ型のＣＰＵなどである。以下では、プロセッサをマルチプロセッサ型のＣＰＵであるとして説明する。また、マルチプロセッサ型のＣＰＵを単にＣＰＵと称する。

図１において、ロック競合管理装置１は、時刻測定部１１とロック獲得失敗回数計測部１２と競合頻度記憶部１３とを有する検出部と、ロック獲得命令発行部１４とを有する。

検出部は、特定の計算主体がロックを獲得するためのロック獲得処理が予め設定された設定時間内に失敗した失敗回数である競合頻度を検出する。

より具体的には、時刻測定部１１、ロック獲得失敗回数計測部１２および競合頻度記憶部１３が以下の機能を実現することで、競合頻度を検出する。

時刻測定部１１には、設定時間が設定される。なお、設定時間は、例えば、ロック競合管理装置１の利用者にて予め設定される。

時刻測定部１１は、設定時間ごとに、ロック獲得失敗回数計測部１２からロック獲得処理が失敗した失敗回数を取得し、その失敗回数を競合頻度として競合頻度記憶部１３に記憶する。

ロック獲得失敗回数計測部１２は、ロック獲得処理の失敗回数を一時的に保持するカウンター機能を有する。ロック獲得失敗回数計測部１２は、ロック獲得命令発行部１４からロック獲得処理が失敗した旨のロック獲得失敗情報を受信するたびに、カウンター機能にて保持されているロック獲得失敗回数をカウントアップして、ロック獲得処理の失敗回数を計測する。

また、ロック獲得失敗回数計測部１２は、時刻測定部１１がロック獲得処理の失敗回数を取得するたびに、カウンター機能にて保持されている失敗回数をゼロにリセットする。

以上により、検出部は、競合頻度を検出することになり、その競合頻度を競合頻度記憶部１３に記憶することになる。

ロック獲得命令発行部１４は、ロック獲得部と呼ばれることもある。ロック獲得命令発行部１４には、ロック獲得処理の実行を停止するか否かを判断するための第一閾値が予め設定される。第一閾値は、例えば、利用者にて設定される。

ロック獲得命令発行部１４は、検出部にて検出された競合頻度（つまり、競合頻度記憶部１３に記憶された競合頻度）が予め設定された第一閾値より大きいか否かを判断する。

競合頻度が第一閾値以下の場合、ロック獲得命令発行部１４は、ロックを獲得するためのロック獲得処理を実行する。ここで、ロック獲得処理が失敗すると、ロック獲得命令発行部１４は、ロック獲得失敗情報をロック獲得失敗回数計測部１２に送信する。

一方、ロック獲得失敗回数が第一閾値より大きい場合、ロック獲得命令発行部１４は、特定の計算主体に対するＣＰＵの割り当てを解除して、特定の計算主体を休眠状態にする。なお、スケジューラ待ち行列は、コンピュータシステムのメモリ（図示せず）などに記憶されている。

休眠状態は、ＣＰＵへの割り当てを待つ計算主体を優先順位が高い方から順に示すスケジューラ待ち行列が特定の計算主体を示さないようにすることで、ＣＰＵに空きがあっても直ぐには実行できない状態である。特定の計算主体が休眠状態になると、他の計算主体がＣＰＵに割り当てられる回数が増えるので、コンピュータシステム全体のスループットを向上させることができる。

次に、図１および図２を参照して、ロック競合管理装置１の動作を説明する。

先ず、図１を参照して、ロック競合管理装置１における競合頻度の検出に係る動作を説明する。

本動作では、時刻測定部１１は、設定時間ごとに、ロック獲得処理の失敗回数を取得するための取得要求をロック獲得失敗回数計測部１２に送信する。例えば、利用者が設定時間間隔を１００ｍｓｅｃと設定していれば、時刻測定部１１は、１００ｍｓｅｃごとに取得要求をロック獲得失敗回数計測部１２に送信する。

ロック獲得失敗回数計測部１２は、取得要求を受信すると、カウンター機能にて保持されている失敗回数を時刻測定部１１に送信する。

時刻測定部１１は、失敗回数を受信すると、その失敗回数を競合頻度として競合頻度記憶部１３に送信して、競合頻度記憶部１３に記憶する。

時刻測定部１１は、競合頻度を競合頻度記憶部１３に記憶すると、ロック獲得処理の失敗回数をゼロにクリアーするためのゼロクリアー要求をロック獲得失敗回数計測部１２に送信する。ロック獲得失敗回数計測部１２は、ゼロクリアー要求を受信すると、カウンター機能にて保持されている失敗回数をゼロにクリアーする。

以上により、競合頻度記憶部１３は、設定時間ごとに、その設定時間内におけるロック獲得処理の失敗回数である競合頻度を保持することになる。

次に、図１および図２を参照して、ロック獲得命令発行部１４の動作を説明する。なお、図２は、ロック獲得命令発行部１４の動作の一例を説明するためのフローチャートである。

ロック獲得命令発行部１４は、特定の計算主体からロックの取得要求を受信すると、以下の処理を開始する。

先ず、ロック獲得命令発行部１４は、競合頻度記憶部１３から競合頻度Ｎを取得する（ステップＳ２０１）。

続いて、ロック獲得命令発行部１４は、自身に設定されている第一閾値Ｍを確認する（ステップＳ２０２）。

そして、ロック獲得命令発行部１４は、競合頻度Ｎが第一閾値Ｍより大きいか否かを判断する（ステップＳ２０３）。

ステップＳ２０３で競合頻度Ｎが第一閾値Ｍ以下と判断された場合、ロック獲得命令発行部１４は、ロック獲得処理を実行する。より具体的には、ロック獲得命令発行部１４は、ロックを獲得するためのロック獲得命令を、ロックの割り当てを行うロック制御部（図示せず）に発行する（ステップＳ２０４）。なお、ロック制御部は、ＯＳ（Operating System）などにて実現される。

その後、ロック獲得命令発行部１４は、ロック制御部からロック獲得命令に対する応答情報を受信し、その応答情報がロック獲得処理の成功を示すか否かを確認する（ステップＳ２０５）
応答情報がロック獲得処理の成功を示すと、ロック獲得命令発行部１４は、ロックをロックの要求元である特定の計算主体に渡して、処理を終了する。

一方、応答情報がロック獲得処理の失敗を示すと、ロック獲得命令発行部１４は、ロック獲得失敗情報をロック獲得失敗回数計測部１２に通知し（ステップＳ２０６）、その後、ステップＳ２０１を実行する。

また、ステップＳ２０３で競合頻度Ｎが第一閾値Ｍより大きいと判断された場合、ロック獲得命令発行部１４は、ロック競合の頻度が高いために、ロックを獲得できる可能性が低いと判断し、特定の計算主体に対するＣＰＵの割り当てを解除して、特定の計算主体を休眠状態にする（ステップＳ２０７）。その後、特定の計算主体が休眠状態から起床状態に遷移し、特定の計算主体がＣＰＵに再び割り当てられて、特定の計算主体からロックの取得要求がロック獲得命令発行部１４に対して発行されると、ステップＳ２０１が実行される。

以上説明したように、本実施形態によれば、検出部は、特定の計算主体がロックを獲得するためのロック獲得処理が予め設定された設定時間内に失敗した失敗回数である競合頻度を検出する。ロック獲得命令発行部１４は、検出部にて検出された競合頻度が予め設定された第一閾値以下の場合、ロック獲得処理を実行する。

このため、競合頻度が第一閾値以下の場合に獲得処理が実行されるので、ロック競合が発生する頻度に上限を設定することが可能になる。したがって、無駄なロック競合を低減することが可能になり、コンピュータシステムが十分なスループットを得ることが可能になる。

また、本実施形態では、ロック獲得命令発行部１４は、競合頻度が第一閾値より大きい場合、特定の計算主体を休眠状態にする。このため、特定の計算主体がロックを獲得できず、種々の処理を実行できない場合に、特定の計算主体以外の計算主体にＣＰＵを割り当てることが可能になる。したがって、コンピュータシステム全体のスループットをさらに向上させることが可能になる。

次に第二の実施形態について説明する。

本実施形態では、競合頻度が第一閾値より大きい場合、特定の計算主体の状態を段階的に変化させることで、計算主体の休眠状態から起床状態への状態遷移にかかるＣＰＵの負荷を低減させて、コンピュータシステムのオーバーヘッドのさらに低減することが可能なロック競合管理装置について説明する。

なお、本実施形態におけるロック競合管理装置の構成は図１と同じであるが、ロック獲得命令発行部１４が以下の機能を有する点が図１で示したロック競合管理装置と異なる。

つまり、ロック獲得命令発行部１４には、第一閾値に加え、計算主体の状態を選択するための第二閾値が予め設定される。第二の閾値は、第一閾値より大きい。また、第二閾値は、例えば、第一閾値と同様に利用者にて設定される。

ロック獲得命令発行部１４は、競合頻度が第二閾値を超えている場合、特定の計算主体に対するＣＰＵの割り当てを解除して、特定の計算主体を休眠状態にする。

また、ロック獲得命令発行部１４は、競合頻度が第一閾値より大きく、かつ第二閾値以下の場合、特定の計算主体に対するＣＰＵの割り当てを解除する。そして、ロック獲得命令発行部１４は、スケジューラ待ち行列の最後に特定の計算主体を追加して、特定の計算主体を待機状態にする。なお、待機状態は、特定の計算主体がＣＰＵへの割り当てを待っている状態であり、ＣＰＵに空きができると、直ぐに実行することが可能な状態である。

以上により、競合頻度が第一閾値より大きくかつ第二閾値以下の場合、特定の計算主体は、ＣＰＵへの割り当てを待つ優先順が最も低い待機状態となる。

次に、図１、図３および図４を参照して、本実施形態のロック競合管理装置１の動作を説明する。なお、ロック競合管理装置１における競合頻度の検出に係る動作は、第一の実施形態と同じなので、その説明を省略する。

図３および図４は、ロック獲得命令発行部１４の動作の一例を説明するためのフローチャートである。なお、図３において、図２と同じ処理には同じ符号を付し、その説明を省略することがある。

図３におけるステップＳ２０３で競合頻度Ｎが第一閾値Ｍより大きいと判断された場合、ロック獲得命令発行部１４は、自身に設定されている第二閾値Ｘを確認する（図４のステップＳ４０１）。

そして、ロック獲得命令発行部１４は、競合頻度Ｎが第二閾値Ｘを超えているか否かを判断する（ステップＳ４０２）。

競合頻度Ｎが第二閾値Ｘを超えている場合、ロック獲得命令発行部１４は、ロック競合の頻度が非常に高いために、ロックを獲得できる可能性が非常に低いと判断して、特定の計算主体に対するＣＰＵの割り当てを解除して、特定の計算主体を休眠状態にする（ステップＳ４０３）。

一方、競合頻度Ｎが第二閾値Ｘ以下の場合、ロック獲得命令発行部１４は、ロック競合の頻度が比較的高いために、ロックを獲得できる可能性が比較的低いと判断して、特定の計算主体に対するＣＰＵの割り当てを解除するとともに、スケジューラ待ち行列の最終列に特定の計算主体を追加して、特定の計算主体を待機状態にする（ステップＳ４０４）。

なお、ステップＳ４０３またはＳ４０４が終了された後で、特定の計算主体がＣＰＵに再び割り当てられて、特定の計算主体からロックの取得要求がロック獲得命令発行部１４に対して発行されると、ステップＳ２０１が実行される。

以上説明したように、本実施形態によれば、競合頻度が第二閾値を超えている場合、ロック獲得命令発行部１４は、特定の計算主体を休眠状態にする。また、競合頻度が第一閾値より大きく、かつ第二閾値以下の場合、ロック獲得命令発行部１４は、スケジューラ待ち行列の最終列に特定の計算主体を追加して、特定の計算主体を待機状態にする。

このため、競合頻度が第一閾値より大きくかつ第二閾値以下の場合、特定の計算主体は休眠状態にはならず待機状態になるだけなので、計算主体の休眠状態から起床状態への状態遷移にかかるＣＰＵの負荷を低減することが可能になり、コンピュータシステムのオーバーヘッドのさらに低減することが可能になる。

なお、以上説明したロック競合管理装置１の機能は、計算主体の一機能として実現されてもよい。

また、ロック競合管理装置１の機能は、その機能を実現するためのプログラムを、コンピュータにて読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行するものであってもよい。さらに、本プログラムを記録した記録媒体も本発明の一実施形態である。

以上説明した各実施形態において、図示した構成は単なる一例であって、本発明はその構成に限定されるものではない。

１ ロック競合管理装置
１１ 時刻測定部
１２ ロック獲得失敗回数計測部
１３ 競合頻度記憶部
１４ ロック獲得命令発行部

Claims (7)

1. プロセッサで実行される複数の計算主体の共有資源を、特定の計算主体が排他的に使用する権限であるロックの競合を管理するロック競合管理装置であって、
   前記特定の計算主体が前記ロックを獲得するための獲得処理が予め設定された設定時間内に失敗した失敗回数を検出する検出部と、
   前記検出部にて計測された失敗回数が予め設定された第一閾値以下の場合、前記獲得処理を実行するロック獲得部と、を有するロック競合管理装置。
2. 請求項１に記載のロック競合管理装置において、
   前記ロック獲得部は、前記失敗回数が前記第一閾値より大きい場合、前記特定の計算主体を休眠状態にする、ロック競合管理装置。
3. 請求項２に記載のロック競合管理装置において、
   前記ロック獲得部は、前記失敗回数が前記第一閾値より大きい第二閾値を超えている場合、前記特定の計算主体を休眠状態にし、前記失敗回数が前記第一閾値より大きく、かつ前記第二閾値以下の場合、前記プロセッサへの割り当てを待つ計算主体を優先順位が高い方から順に示す待ち行列の最後に前記特定の計算主体を追加して、前記特定の計算主体を待機状態にする、ロック競合管理装置。
4. プロセッサで実行される複数の計算主体の共有資源を、特定の計算主体が排他的に使用する権限であるロックの競合を管理するロック競合管理方法であって、
   前記特定の計算主体が前記ロックを獲得するための獲得処理が予め設定された設定時間内に失敗した失敗回数を検出し、
   前記検出された失敗回数が予め設定された第一閾値以下の場合、前記獲得処理を実行する、ロック競合管理方法。
5. 請求項４に記載のロック競合管理方法において、
   前記失敗回数が前記第一閾値より大きい場合、前記特定の計算主体を休眠状態にする、ロック競合管理方法。
6. 請求項５に記載のロック競合管理方法において、
   前記失敗回数が前記第一閾値より大きい第二閾値を超えている場合、前記特定の計算主体を休眠状態にし、前記失敗回数が前記第一閾値より大きく、かつ前記第二閾値以下の場合、前記プロセッサへの割り当てを待つ計算主体を優先順位が高い方から順に示す待ち行列の最後に前記特定の計算主体を追加して、前記特定の計算主体を待機状態にする、ロック競合管理方法。
7. プロセッサで実行される複数の計算主体の共有資源を排他的に使用する権限であるロックを特定の計算主体が獲得するための獲得処理が予め設定された設定時間内に失敗した失敗回数を検出する手順と、
   前記検出された失敗回数が予め設定された第一閾値以下の場合、前記獲得処理を実行する手順と、をコンピュータに実行させるプログラム。

Images