JPH09106357A - 排他制御装置及びその方法 - Google Patents

Abstract

(57)【要約】 【課題】 ロック操作に係るオーバヘッドを削減して排
他制御の高速化を図る。 【解決手段】 ロック要求に対してロックできない場合
には、タスク情報登録手段２１０はそのタスクに関する
タスク情報を待ちリストに加える。待ち時間監視手段２
２０は、タスクがロック待ち状態にある時間を監視し
て、所定の監視時間を経過するとデッドロックが発生し
たものと解して上記待ちリストから削除する。その旨を
通知されたタスクは、タスク情報削除手段２３０を通じ
て既に取得していたロックを解除する。

Description

【発明の詳細な説明】

【発明の属する技術分野】本発明は、排他制御装置及び
その方法に関する。

【０００１】

【従来の技術】複数のプロセッサにより資源が共有され
ている場合において、その資源の使用権を確保するため
の操作をロックという。一般に、書込みのためのロック
が取得されていると、他のプロセッサは同一資源に関す
るロックを取得することができない。

【０００２】一方、複数のプロセッサ間で共通する資源
に対してロックを取得しようとした場合、他のプロセッ
サが取得しているロックを互いに待ってしまい処理が進
まなくなるおそれがある。この状態をデッドロックとい
う。このデッドロック状態に陥ると、その待ち状態を強
制的に停止させなければならない。

【０００３】そこで、従来は、あるタスクからのロック
取得要求が失敗して待ち合わせが発生している各タスク
について、デッドロック発生有無のチェックが行われて
いた。たとえば、特開昭６２−１７７６３１号公報に
は、資源確保待ちタスク登録テーブルに登録されている
各タスクについて「デッドロック監視間隔」でデッドロ
ック検出処理を行うデッドロック検出方式の技術が記載
されている。

【０００４】

【発明が解決しようとする課題】上述の従来技術では、
待ち合わせが発生している各タスクについて、所定の時
間間隔でデッドロック発生をチェックするため、管理し
ているテーブル中の全ての待ちタスクを順番に基点とし
てデッドロック発生の有無を調べていかなければならな
い。一般的にはデッドロックの発生頻度は少ないにも拘
わらず、デッドロックを検出するために大きなオーバヘ
ッドが生じることになる。

【０００５】本発明の目的は、ロック操作に係るオーバ
ヘッドを削減して排他制御の高速化を図ることにある。

【０００６】また、本発明の他の目的は、タスク間にお
けるデッドロックの発生を簡易に検出することにある。

【０００７】

【課題を解決するための手段】上記課題を解決するため
に本発明の排他制御装置は、監視時間が指定されたロッ
ク取得要求に対してロック待ちとなったタスクについ
て、そのロック待ちとなっている時間が前記監視時間を
越えた場合にそのロック待ちを強制的に解除する。

【０００８】また、本発明の他の排他制御装置は、タス
クからの監視時間が指定されたロック取得要求に応答し
てロックを取得した旨のロック登録又はロック待ちであ
る旨のロック待ち登録を行うタスク情報登録手段と、こ
のタスク情報登録手段においてロック待ち登録されてい
る時間を監視してロック待ち登録されている時間が前記
監視時間を越えた場合にロック待ち登録を削除する待ち
時間監視手段と、前記ロック登録又はロック待ち登録を
削除し、前記待ち時間監視手段によって削除されたロッ
ク待ち登録に係るタスクが既に取得していたロックのロ
ック登録を削除するタスク情報削除手段とを含む。

【０００９】また、本発明の他の排他制御装置は、ロッ
クの対象となる最小単位であるブロック毎に設けられ当
該ロックを取得しているタスクに関する情報を管理する
ロックリストと、前記ブロック毎に設けられ当該ロック
を待っているタスクに関する情報を管理する待ちリスト
とを格納するロック管理テーブルと、タスクからの監視
時間が指定されたロック取得要求に応答して前記ロック
リスト又は前記待ちリストに当該タスクに関する情報を
登録するタスク情報登録手段と、このタスク情報登録手
段において前記待ちリストに接続されている時間が前記
監視時間を越えた場合に前記待ちリストから前記タスク
に関する情報を削除する待ち時間監視手段と、前記ロッ
ク登録又はロック待ち登録を削除し、前記待ち時間監視
手段によって前記待ちリストから削除されたタスクに関
する情報を前記ロックリストから削除するタスク情報削
除手段とを含む。

【００１０】また、本発明の他の排他制御装置は、前記
ロック取得要求は、読出しのためのロックか書込みのた
めのロックかを示すロック種別をさらに含み、前記タス
ク情報登録手段は、ロック対象となるブロックが既に読
出しのためにロックされていても前記ロック種別が読出
しのためのロックである旨を示していれば前記ロックリ
ストに登録し、ロック対象となるブロックが既に書込み
のためにロックされていれば前記ロック種別に拘わらず
前記待ちリストに登録する。

【００１１】また、本発明の排他制御方法は、ロックの
対象となる最小単位であるブロック毎に設けられ当該ロ
ックを取得しているタスクに関する情報を管理するロッ
クリストと、前記ブロック毎に設けられ当該ロックを待
っているタスクに関する情報を管理する待ちリストとを
格納するロック管理テーブルを含む排他制御装置におい
て、タスクからの監視時間が指定されたロック取得要求
に応答して前記ロックリスト又は前記待ちリストに当該
タスクに関する情報を登録するタスク情報登録ステップ
と、前記待ちリストに接続されている時間が前記監視時
間を越えた場合に前記待ちリストから前記タスクに関す
る情報を削除する待ち時間監視ステップと、前記待ちリ
ストから削除されたタスクに関する情報を前記ロックリ
ストから削除するタスク情報削除ステップとを含むこと
を特徴とする排他制御方法。

【００１２】

【発明の実施の形態】次に本発明の排他制御装置及びそ
の方法の一実施例について図面を参照して詳細に説明す
る。

【００１３】図１を参照すると、本発明の一実施例であ
る排他制御装置２００は、複数のプロセッサ１００と、
これらプロセッサ１００に共有される共有資源３００と
を含む情報処理システムに適用される。共有資源３００
としては、メモリの一部の領域やファイル等が対象とな
ることが多い。ここでは、ロック制御の対象となる最小
単位をブロックとよぶ。

【００１４】図２を参照すると、本発明の一実施例であ
る排他制御装置２００は、各プロセッサ１００とのやり
とりを行うコマンドインタフェース２５０と、ロックま
たはロック待ちしているタスクに関する情報（以下、タ
スク情報という）を管理するロック管理テーブル２４０
と、各タスクのタスク情報を登録するタスク情報登録手
段２１０と、各タスクがロック待ち状態にある時間を監
視する待ち時間監視手段２２０と、タスク情報登録手段
２１０により登録されたタスク情報を削除するタスク情
報削除手段２３０とを含む。

【００１５】図３を参照すると、ロック管理テーブル２
４０は、ブロック毎にブロック情報２４１と、そのブロ
ックをロックまたはロック待ちしているタスクのタスク
情報２４２の集合を格納する。ブロック情報２４１は、
そのブロックを識別するためのブロック識別子と、ロッ
クリストの先頭に対するポインタであるロックリストポ
インタと、待ちリストの先頭に対するポインタである待
ちリストポインタとを有する。ここで、ロックリストと
は、ロック中のタスクのタスク情報を連結リストにより
接続したものである。また、待ちリストとは、ロック待
ちにあるタスクのタスク情報を連結リストにより接続し
たものである。各タスク情報は、タスクを識別するため
のタスク識別子と、読出しか書込みか等のロックの種別
を表すロック種別とを有し、連結リストを形成する次の
タスク情報へのポインタをも有している。

【００１６】図４を参照すると、待ち時間監視手段２２
０で使用される監視エントリは、ロック管理テーブル２
４０中のタスク情報へのポインタである対象エントリポ
インタと、タスクからのロック要求によりロック管理テ
ーブル２４０に登録された際の時刻を表す登録時刻と、
タスクからのロック要求時に指定された監視時間とを有
する。

【００１７】図５を参照すると、各プロセッサ上のタス
クからのコマンドの形式としては、要求の種類を表すコ
マンドコードと、要求元タスクを示すタスク識別子と、
要求対象のブロックを示すブロック識別子と、ロックの
種別を表すロック種別と、ロック待ちを生じた場合に許
容される監視時間とを含んでいる。

【００１８】次に本発明の排他制御装置の上記一実施例
の動作について図面を参照して説明する。

【００１９】図２を参照すると、排他制御装置２００に
おいて、コマンドインタフェース２５０は、プロセッサ
１００上のタスクから図５の形式のコマンドを受け取る
と、コマンドコードを解析する。コマンドコードがロッ
ク要求を示していれば、タスク情報登録手段２１０は、
ロック管理テーブル２４０にタスク情報を登録する。コ
マンドコードがアンロック要求を示していれば、タスク
情報削除手段２３０はロック管理テーブル２４０のタス
ク情報を削除する。

【００２０】図６を参照すると、タスクからコマンドが
発行された場合、タスク情報登録手段２１０は、まずロ
ック管理テーブル２４０を検索して（ステップＳ２１
１）、コマンドに含まれている「ブロック識別子」が示
すブロックのロック可否を判定する（ステップＳ２１
２）。具体的には、ロック管理テーブル２４０の中か
ら、コマンドに含まれている「ブロック識別子」と同じ
ブロック識別子を有するブロック情報２４１を検索し
て、このブロック情報２４１のロックリストポインタが
空ポインタであるか否かを調べる。ブロック情報がない
か、または、あっても空ポインタであればロック可であ
ると判断できる。空ポインタでなければ、既に他のタス
クによってロックされているため、ロックリストに接続
されている各タスク情報について「ロック種別」を参照
して同時にロックすることが可能か否かを判定する。す
なわち、対象となるブロックが既に読出しのためにロッ
クされていても、コマンドの「ロック種別」が”読出
し”であれば、これもロックできるものと判断できる。
読出し同士であれば矛盾が生じないからである。一方、
対象となるブロックが既に書込みのためにロックされて
いれば、コマンドの「ロック種別」に拘わらずロックで
きないものと判断される。

【００２１】判定の結果、ロック可能であると判断され
た場合は、コマンドに含まれている「タスク識別子」及
び「ロック種別」に基づいてタスク情報を生成して、ロ
ックリストの最後尾に接続する（ステップＳ２１３）。
そして、コマンドの「タスク識別子」の指すタスクに対
してロック許可の旨を通知する（ステップＳ２１６）。

【００２２】一方、ロックできないと判断された場合
は、コマンドに含まれている「タスク識別子」及び「ロ
ック種別」に基づいてタスク情報を生成して、待ちリス
トの最後尾に接続する（ステップＳ２１４）とともに、
ロック待ち時間を監視する（ステップ２１５）。このロ
ック待ち時間監視の動作については図７を参照して後述
する。その後、コマンドの「タスク識別子」の指すタス
クに対してロック待ちの旨を通知する（ステップＳ２１
６）。

【００２３】図７を参照すると、待ち時間監視手段２２
０は、まず図４の形式を有する監視エントリを生成する
（ステップＳ２２１）。そして、コマンドを受け取った
時刻からの経過時間が監視エントリの「監視時間」と一
致（ステップＳ２２３）するまで監視する（ステップＳ
２２２）。経過時間が監視エントリの監視時間と一致す
ると、監視エントリの「対象エントリポインタ」が指す
ロック管理テーブル２４０中のタスク情報を検索する。
その結果、ロック管理テーブル２４０にタスク情報がま
だ残っている場合にはそのタスク情報を削除する（ステ
ップＳ２２４）。そして、削除されたタスク情報の「タ
スク識別子」が示していたタスクに対して、タイムアウ
トによるタスク情報削除が発生した旨を通知する（ステ
ップＳ２２５）。

【００２４】図８を参照すると、コマンドの「コマンド
コード」がアンロック要求、すなわちロックの解除を要
求するものである場合には、タスク情報削除手段２３０
は、まずロック管理テーブル２４０からコマンドの「ブ
ロック識別子」を有するブロック情報を検索する。そし
て、そのブロック情報のロックリスト及び待ちリストに
接続されているタスク情報からコマンドの「タスク識別
子」を有するタスク情報を検索し（ステップＳ２３
１）、この検索されたタスク情報を削除する（ステップ
Ｓ２３２）。次に、この削除されたタスク情報が接続さ
れていた待ちリストに他のタスク情報が存在するか否か
を調べる（ステップＳ２３３）。もし待ちタスク情報が
存在すれば、そのタスク情報の「タスク識別子」の指す
タスクがロック可能になったか否かを判断する（ステッ
プＳ２３４）。ロック可能であると判断された場合は、
そのタスク情報を待ちリストから外して、ロックリスト
に接続する。その後、そのタスク情報の「タスク識別
子」の指すタスクに対して、ロックが許可された旨を通
知するとともに（ステップＳ２３５）、コマンドの「タ
スク識別子」の指すタスクに対してアンロックが完了し
た旨を通知する（ステップＳ２３６）。一方、待ちタス
ク情報が存在しない（ステップＳ２３３）か、またはロ
ック可能になっていなければ（ステップＳ２３４）、ロ
ックが許可された旨は通知せずに、コマンドの「タスク
識別子」の指すタスクに対してアンロックが完了した旨
のみを通知する（ステップＳ２３６）。

【００２５】次に２つのタスク間でデッドロックが発生
した場合の動作の具体例について図面を参照して説明す
る。ここでは、タスク１がブロックＡ及びブロックＢの
順番でロックして更新処理を行い、タスク２がブロック
Ｂ及びブロックＡの順番でロックして更新処理を行う場
合について説明する。但し、両タスク共、ブロックＡ及
びブロックＢの両方をロックした上で更新処理を行わな
ければならないものとする。

【００２６】図９を参照すると、最初にタスク１がブロ
ックＡに対するロック要求を行い、これに対するタスク
情報登録後、タスク１に対してロック許可通知がなされ
る（ステップＳ９０１）。次に、タスク２がブロックＢ
に対するロック要求を行い、これに対するタスク情報登
録後、タスク２に対してロック許可通知がなされる（ス
テップＳ９０２）。

【００２７】その後、タスク１はブロックＢに対するロ
ック要求を行う。しかし、ブロックＢは既にタスク２に
よってロックされているため、タスク１に待ち通知がな
される（ステップＳ９０３）。また、タスク１によるブ
ロックＢに対するロック要求を待ち登録した時点からコ
マンドで指定された「監視時間」の監視を開始する（ス
テップＳ９０４）。

【００２８】また、タスク２はブロックＡに対するロッ
ク要求を行う。しかし、ブロックＡは既にタスク１によ
ってロックされているため、タスク２に待ち通知がなさ
れる（ステップＳ９０５）。また、タスク２によるブロ
ックＡに対するロック要求を待ち登録した時点からコマ
ンドで指定された「監視時間」の監視を開始する（ステ
ップＳ９０６）。

【００２９】ここまでの処理により、タスク１とタスク
２の間でデッドロックが生じている。すなわち、タスク
１がブロックＡを、タスク２がブロックＢをロックする
一方、タスク１がブロックＢを、タスク２がブロックＡ
を待っており、互いに相手のロックしているブロックを
待ってしまって硬直状態になっている。この場合、いず
れかがロックしているブロックを強制的にアンロックし
ない限り、この状態が永久に続いてしまう。そこで、本
発明では、監視エントリの「監視時間」を経過すると、
そのロック待ち状態を解除してその旨をタスクに対して
通知することにより、このデッドロックを解消する。

【００３０】タスク１とタスク２の両者が同じ値の「監
視時間」を指定していたとすると、先に登録されたタス
ク１の待ちが早くタイムアウトになる。このタイムアウ
トが検出されると、タスク１のブロックＢに対するロッ
ク待ちを表すタスク情報は、待ちリストから削除され
る。タスク１にはこの削除に関する通知がなされる（ス
テップ９０７）。

【００３１】この通知を受けて、タスク１はデッドロッ
クが発生したことを知り、ブロックＡについてのアンロ
ック要求を発行する。このアンロック要求に応答して、
タスク１のブロックＡに対するロック取得を表すタスク
情報は、ロックリストから削除される。タスク１にはこ
の削除に関する通知がなされる（ステップ９０８）。ま
た、ブロックＡのロックを待っていたタスク２にはロッ
ク許可の通知がなされる（ステップ９０８）。これによ
り、タスク２は、ブロックＡ及びブロックＢのロックが
許可されて、更新処理が可能となる。

【００３２】なお、タスク１の「監視時間」をタスク２
の「監視時間」よりも大きく指定して調整することによ
り、タスク２の待ちを早くタイムアウトさせることも可
能である。また、この「監視時間」の指定を各タスクの
優先度に応じて調整することで、システムの要求に適し
た運用を行うことができる。

【００３３】このように、本発明の一実施例である排他
制御装置２００によれば、ロック待ちとなっている時間
を待ち時間監視手段２２０によって監視して、コマンド
で指定された監視時間を経過した場合には当該待ちを待
ちリストから削除するため、デッドロックチェック処理
が不要となり、システムの処理性能が向上する。また、
監視時間をタスクから指定できるようにしたことによ
り、デッドロックが発生した場合にエラー終了させるタ
スクを陽に指定することができる。

【００３４】

【発明の効果】以上の説明で明らかなように、本発明に
よると、所定時間を経過したロック待ちを強制的に削除
することにより、デッドロックチェック処理を不要にし
て、システムの処理性能を向上できる。また、監視時間
をタスクから指定できるようにしたことにより、デッド
ロックが発生した場合にエラー終了させるタスクを明示
的に指定することができる。

【図面の簡単な説明】

【図１】本発明の排他制御装置が適用される情報処理シ
ステムの一構成例を示す図である。

【図２】本発明の排他制御装置の一実施例を示す図であ
る。

【図３】本発明の一実施例の排他制御装置におけるロッ
ク管理テーブルで管理されるデータ構造を示す図であ
る。

【図４】本発明における監視エントリの構成を示す図で
ある。

【図５】本発明におけるコマンドの形式を示す図であ
る。

【図６】本発明におけるタスク情報登録手段の動作を表
す図である。

【図７】本発明における待ち時間監視手段の動作を表す
図である。

【図８】本発明におけるタスク情報削除手段の動作を表
す図である。

【図９】本発明の一実施例の排他制御装置による処理の
流れを表す図である。

【符号の説明】

１００ プロセッサ ２００ 排他制御装置 ２１０ タスク情報登録手段 ２２０ 待ち時間監視手段 ２３０ タスク情報削除手段 ２４０ ロック管理テーブル ２５０ コマンドインタフェース ３００ 共有資源

Claims (5)

【特許請求の範囲】
1. 【請求項１】 監視時間が指定されたロック取得要求に
   対してロック待ちとなったタスクについて、そのロック
   待ちとなっている時間が前記監視時間を越えた場合にそ
   のロック待ちを強制的に解除することを特徴とする排他
   制御装置。
2. 【請求項２】 タスクからの監視時間が指定されたロッ
   ク取得要求に応答してロックを取得した旨のロック登録
   又はロック待ちである旨のロック待ち登録を行うタスク
   情報登録手段と、 このタスク情報登録手段においてロック待ち登録されて
   いる時間を監視してロック待ち登録されている時間が前
   記監視時間を越えた場合にロック待ち登録を削除する待
   ち時間監視手段と、 前記ロック登録又はロック待ち登録を削除し、前記待ち
   時間監視手段によって削除されたロック待ち登録に係る
   タスクが既に取得していたロックのロック登録を削除す
   るタスク情報削除手段とを含むことを特徴とする排他制
   御装置。
3. 【請求項３】 ロックの対象となる最小単位であるブロ
   ック毎に設けられ当該ロックを取得しているタスクに関
   する情報を管理するロックリストと、前記ブロック毎に
   設けられ当該ロックを待っているタスクに関する情報を
   管理する待ちリストとを格納するロック管理テーブル
   と、 タスクからの監視時間が指定されたロック取得要求に応
   答して前記ロックリスト又は前記待ちリストに当該タス
   クに関する情報を登録するタスク情報登録手段と、 このタスク情報登録手段において前記待ちリストに接続
   されている時間が前記監視時間を越えた場合に前記待ち
   リストから前記タスクに関する情報を削除する待ち時間
   監視手段と、 前記ロック登録又はロック待ち登録を削除し、前記待ち
   時間監視手段によって前記待ちリストから削除されたタ
   スクに関する情報を前記ロックリストから削除するタス
   ク情報削除手段とを含むことを特徴とする排他制御装
   置。
4. 【請求項４】 前記ロック取得要求は、読出しのための
   ロックか書込みのためのロックかを示すロック種別をさ
   らに含み、 前記タスク情報登録手段は、ロック対象となるブロック
   が既に読出しのためにロックされていても前記ロック種
   別が読出しのためのロックである旨を示していれば前記
   ロックリストに登録し、ロック対象となるブロックが既
   に書込みのためにロックされていれば前記ロック種別に
   拘わらず前記待ちリストに登録することを特徴とする請
   求項３記載の排他制御装置。
5. 【請求項５】 ロックの対象となる最小単位であるブロ
   ック毎に設けられ当該ロックを取得しているタスクに関
   する情報を管理するロックリストと、前記ブロック毎に
   設けられ当該ロックを待っているタスクに関する情報を
   管理する待ちリストとを格納するロック管理テーブルを
   含む排他制御装置において、 タスクからの監視時間が指定されたロック取得要求に応
   答して前記ロックリスト又は前記待ちリストに当該タス
   クに関する情報を登録するタスク情報登録ステップと、 前記待ちリストに接続されている時間が前記監視時間を
   越えた場合に前記待ちリストから前記タスクに関する情
   報を削除する待ち時間監視ステップと、 前記待ちリストから削除されたタスクに関する情報を前
   記ロックリストから削除するタスク情報削除ステップと
   を含むことを特徴とする排他制御方法。