JPH04262425A - 共有資源排他制御方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は電子計算機システムにお
ける共有資源排他制御方式に関するものである。

【０００２】

【従来の技術】電子計算機システムにおいて、複数のタ
スクから使用される資源（共有資源）については、それ
らへのアクセスを逐次化するために排他制御が必要であ
る。

【０００３】このような排他制御のために、電子計算機
システムには、ロック／アンロックあるいはＥＮＱ（エ
ンキュー）／ＤＥＱ（デキュー）と呼ばれる基本機能が
備えられている。なお、ロック要求には排他モードと共
有モードとの２種類がある。

【０００４】排他制御の基本的動作は次のように行われ
る。

【０００５】あるタスクがロック要求を出した場合、ロ
ック要求対象の資源が他のタスクによりロックされてい
ない場合、または、その資源のロックモードとそのタス
クのロック要求のモードがともに共有モードの場合には
、要求したタスクに対してすぐにロック権が付与される
。

【０００６】しかし、その資源がロックされている場合
、その資源のロックモードまたはタスクのロック要求の
モードのいずれかが排他モードの時は、ロック待ちとな
る。

【０００７】一方、資源をロックしていたタスクが資源
の使用を終えてアンロック要求を出した場合は、そのタ
スクのロック権の行使が終了する。

【０００８】この場合、アンロック要求を出したタスク
が排他モードでロックをしていた場合には、待ち合わせ
していたタスクがあれば、最も早くロック要求をしたタ
スクの要求モードが排他モードであれば、そのタスクの
みにロック権を付与し、共有モードであれば現在共有モ
ードでロック待ちしているタスク全てにロック権を付与
する。

【０００９】また、アンロック要求を出したタスクが共
有モードでロックをしていた場合には、待ち合わせをし
ていた排他モードのタスクがあれば、そのタスクにロッ
ク権を付与する。

【００１０】なお、アンロック要求をした時点で待ち合
わせをしているタスクがない場合には、当然のことなが
らロック権の付与は行わない。

【００１１】

【発明が解決しようとする課題】上述したように、従来
の共有資源排他制御方式では、複数の資源を同時に使用
して処理する場合、各資源に対し逐次にロック要求をす
るが、いくつかの資源のロックが成功し、次の資源をロ
ックしようとしてロック待ちとなった場合、既にそのタ
スクがロックした資源に対してロック待ちしている他の
タスクの待ち時間が不必要に長くなり、資源の使用効率
が低下するという欠点があった。

【００１２】なお、このような場合、必要な資源を全て
確保できない限り何も資源を確保しないというオールオ
アナッシングの技法等を適用すれば解決できるが、制御
が複雑になり、処理性能に影響を与えるので好ましくな
い。

【００１３】本発明は上記の点に鑑み提案されたもので
あり、その目的とするところは、後続のロック待ちタス
クのロック待ち時間を減少させ、共有資源の使用効率を
向上させることのできる共有資源排他制御方式を提供す
ることにある。

【００１４】

【課題を解決するための手段】本発明は上記の目的を達
成するため、電子計算機システムの共有資源排他制御方
式において、タスク対応にロック優先度を設け、タスク
が資源をロックした時、およびタスクがロック権の行使
を終了した時、当該タスクのロック中資源の数ｘにつき
ｆ（ａ）≧ｆ（ｂ）が成立するａ＞ｂなるａ，ｂが存在
し、かつｆ（ｃ）＞ｆ（ｄ）が成立するｃ＞ｄなるｃ，
ｄが存在する関数ｆ（ｘ）によって算出された値を当該
タスクのロック優先度として設定するロック優先度設定
手段と、タスクがロック待ちとなった時、ロック待ちタ
スクへのロック権付与順序がロック優先度の高い順とな
るようロック待ち行列を並べ換えるロック順序変更手段
とを備えるようにしている。

【００１５】

【作用】本発明の共有資源排他制御方式にあっては、タ
スクが資源をロックした時、およびタスクがロック権の
行使を終了した時、ロック優先度設定手段が当該タスク
のロック中資源の数ｘにつきｆ（ａ）≧ｆ（ｂ）が成立
するａ＞ｂなるａ，ｂが存在し、かつｆ（ｃ）＞ｆ（ｄ
）が成立するｃ＞ｄなるｃ，ｄが存在する関数ｆ（ｘ）
によって算出された値を当該タスクのロック優先度とし
て設定し、タスクがロック待ちとなった時、ロック順序
変更手段がロック待ちタスクへのロック権付与順序がロ
ック優先度の高い順となるようロック待ち行列を並べ換
える。

【００１６】

【実施例】以下、本発明の実施例につき図面を参照して
説明する。

【００１７】図１は本発明の共有資源排他制御方式の一
実施例を示す構成図である。

【００１８】図１において、共有資源排他制御機構７は
、ロック要求の処理を行うロック要求処理手段１と、ア
ンロック要求の処理を行うアンロック要求処理手段２と
、ロック優先度の高い順にロック待ち行列を並べ換える
ロック順序変更手段３と、タスクのロック優先度として
当該タスクのロック中資源数から所定の関数で算出され
る値を設定するロック優先度設定手段４と、排他制御テ
ーブル５と、ロック優先度テーブル６とから構成されて
いる。

【００１９】図２は排他制御テーブル５およびロック優
先度テーブル６の論理的構成を示したものである。

【００２０】すなわち、排他制御テーブル５はシステム
内の排他制御対象資源を一意に識別するための名前であ
る資源名をキーとするものであり、各資源に対するエン
トリは、資源名部とロックモード部とロック中タスクリ
ストとロック待ち行列とから構成されている。ここで、
ロックモード部は、資源がロックされているときのロッ
クモードが記録され、ロック中タスクリストは、その資
源をロックしているタスクのタスク識別子が記録され、
ロック待ち行列は、待ち状態にあるロック要求の待ち行
列であり、これらの要求を出しているタスクのタスク識
別子とロックモードとの組が記録される。なお、ロック
モードは共有モードを「Ｓ」、排他モードを「Ｅ」と表
すこととする。

【００２１】また、ロック優先度テーブル６はタスク識
別子をキーとするものであり、各タスクに対するエント
リは、タスク識別子部と、ロック中資源数部と、ロック
優先度部とから構成されている。ここで、ロック中資源
数部は、そのタスクがロックしている資源数が記録され
、ロック優先度部は、そのタスクのロック優先度が記録
される。

【００２２】以下、各処理部の動作を説明する。

【００２３】（１）ロック要求処理手段１いずれかのタ
スクＴ１〜Ｔｎからロック要求がされると、ロック要求
処理手段１はロック要求の処理を行う。

【００２４】すなわち、ロック要求処理手段１は、排他
制御テーブル５の要求された資源に対応するエントリを
参照し、ロックモード部が空の場合、または、その要求
のロックモードとロックモード部の値とがともに共有モ
ードＳの場合は、ロックモード部にその要求のロックモ
ードを記録し、ロック中タスクリストにその要求を出し
たタスクのタスク識別子を追加する。

【００２５】次いで、ロック優先度テーブル６のそのロ
ック要求を出したタスクに対するエントリのロック中資
源数部に１を加えた後、そのタスクのタスク識別子をパ
ラメータとしてロック優先度設定手段４を呼び出す。

【００２６】一方、タスクＴ１〜Ｔｎからのロック要求
に際し、排他制御テーブル５の要求された資源に対応す
るロックモード部が空でなくタスクのロック要求が排他
モードＥである場合、または、ロックモード部の値が排
他モードＥである場合は、そのタスクのタスク識別子と
ロックモードとの組をロック待ち行列の最後に追加し、
ロック順序変更手段３を呼び出す。

【００２７】次いで、その要求を出したタスクの処理を
中断させる。

【００２８】（２）アンロック要求処理手段２いずれか
のタスクＴ１〜Ｔｎからアンロック要求がされると、ア
ンロック要求処理手段２は、アンロック要求の処理を行
う。

【００２９】すなわち、アンロック要求処理手段２は排
他制御テーブル５の対応する資源のエントリのロック中
タスクリストからそのアンロック要求を出したタスクの
タスク識別子を削除し、ロック優先度テーブル６のその
タスクのエントリのロック中資源数部から１を減じた後
、そのタスクのタスク識別子をパラメータとしてロック
優先度設定手段４を呼び出す。

【００３０】次いで、排他制御テーブル５のロック中タ
スクリストが空となっている場合は、ロックモード部を
消去する。

【００３１】更に、排他制御テーブル５のロック待ち行
列にロック待ちタスクがある場合、次のロック待ちタス
クが排他モードＥでロック要求している場合は、ロック
モード部に排他モードＥを、ロック中タスクリストにそ
のタスクのタスク識別子をそれぞれ記録し、そのタスク
のタスク識別子等をロック待ち行列から削除する。

【００３２】また、次のロック待ちタスクが共有モード
Ｓでロック要求している場合は、ロックモード部に共有
モードＳを記録し、ロック待ち行列内の共有モードでロ
ック要求を出している全てのタスクのタスク識別子を、
ロック中タスクリストに記録し、ロック待ち行列内の全
ての共有モードのタスク識別子等を削除する。

【００３３】次いで、ロック中タスクリストに記録した
全てのタスク識別子のタスクについて、ロック優先度テ
ーブル６のロック中資源数部に１を加え、各タスク識別
子をパラメータとしてロック優先度変更手段４をタスク
数分だけ繰り返し呼び出した後、これらのタスクの処理
を再開させる。

【００３４】（３）ロック順序変更手段３ロック順序変
更手段３は、ロック要求処理手段１から待ち状態にした
タスクのタスク識別子をパラメータとして呼び出された
際に動作する。

【００３５】すなわち、ロック順序変更手段３は、排他
制御テーブル５のロック待ち行列を、ロック優先度テー
ブル６のロック優先度部を参照して、各要求を出したタ
スクのロック優先度の高い順に並べ換える。この時、ロ
ック優先度の等しいタスクのロック要求は先着順に並べ
る。

【００３６】（４）ロック優先度設定手段４ロック優先
度設定手段４は、ロック要求処理手段１もしくはアンロ
ック要求処理手段２からロック中資源数が変更となった
タスクのタスク識別子をパラメータとして呼び出された
際に動作する。

【００３７】すなわち、ロック優先度変更手段４は、ロ
ック優先度テーブル６のパラメータで指定されたタスク
識別子に対するエントリに関し、ロック中資源数部を参
照してロック優先度を算出し、その値を当該エントリの
ロック優先度部に記録する。ロック優先度の算出は、ロ
ック中資源の数ｘにつきｆ（ａ）≧ｆ（ｂ）が成立する
ａ＞ｂなるａ，ｂが存在し、かつｆ（ｃ）＞ｆ（ｄ）が
成立するｃ＞ｄなるｃ，ｄが存在する関数ｆ（ｘ）を用
いる。例えば、ｆ（ｘ）＝ｘとしてロック中資源数その
ものをロック優先度とすることもできる。

【００３８】次に、本実施例の具体的動作について、図
３ないし図７を参照して説明する。

【００３９】図３は４つのタスクＴ１〜Ｔ４が２つの資
源Ｒ１，Ｒ２に対して順次にロック要求およびアンロッ
ク要求を行う状況を示すタイミングチャートである。

【００４０】図４ないし図７は図３における各時刻ｔａ
〜ｔｄでの排他制御テーブル５およびロック優先度テー
ブル６の状態を示している。なお、時刻ｔより前では、
資源Ｒ１，Ｒ２はロックされていないものとする。

【００４１】また、ｆ（０）＜ｆ（１）＜ｆ（２）が成
立するような関数ｆ（ｘ）が用いられ、ロック優先度テ
ーブル６のロック中資源数部とロック優先度部とがそれ
ぞれ「０」，「ｆ（０）」に初期化されているものとす
る。

【００４２】時刻ｔでタスクＴ１が資源Ｒ１を排他モー
ドＥでロック要求すると、ロック要求処理手段１が呼び
出され、資源Ｒ１はロックされていないので、タスクＴ
１にロック権が付与され、排他制御テーブル５のロック
モード部に排他モード「Ｅ」が、ロック中タスクリスト
にタスク識別子「Ｔ１」がそれぞれ記録される。

【００４３】また、ロック優先度テーブル６のタスクＴ
１のロック中資源数部に「１」が加えられ、ロック優先
度設定手段４が呼び出され、タスクＴ１のロック優先度
部に「ｆ（１）」が設定される。

【００４４】時刻ｔ＋１でタスクＴ２が資源Ｒ１を排他
モードＥでロック要求すると、ロック要求処理手段１が
呼び出され、資源Ｒ１は既に排他モードＥでロックされ
ているので、タスクＴ２はロック待ちとなり、排他制御
テーブル５のロック待ち行列にタスク識別子Ｔ２と排他
モードＥとの組「Ｔ２，Ｅ」が記録される。

【００４５】続いて、ロック順序変更手段３が呼び出さ
れ、排他制御テーブル５のロック待ち行列の並べ換えが
行われるが、この時点でのロック待ちタスクはＴ２のみ
なので、実質的に意味はない。この後、タスクＴ２の処
理は中断され待ちに入る。

【００４６】時刻ｔ＋２でタスクＴ３が資源Ｒ２を共有
モードＳでロック要求し、時刻ｔ＋３でタスクＴ４が資
源Ｒ２を排他モードＥでロック要求すると、タスクＴ１
，Ｔ２の場合と同様に処理が行われ、タスクＴ３にロッ
ク権が付与され、タスクＴ４はロック待ちとなる。この
結果、時刻ｔａでの排他制御テーブル５およびロック優
先度テーブル６は図４のような状態となる。

【００４７】時刻ｔ＋４でタスクＴ３が資源Ｒ１を共有
モードＳでロック要求すると、ロック要求処理手段１が
呼び出され、資源Ｒ１は既に排他モードでロックされて
いるので、排他制御テーブル５のロック待ち行列の最後
にタスク識別子Ｔ３と共有モードＳとの組「Ｔ３，Ｓ」
が追加される。

【００４８】次に、ロック順序変更手段３が呼び出され
、タスクＴ２とタスクＴ３のロック優先度はそれぞれｆ
（０），ｆ（１）であり、ｆ（０）＜ｆ（１）であるこ
とから、タスクＴ３のロック要求，タスクＴ２のロック
要求の順にロック待ち行列が並べ換えられ、その後、タ
スクＴ３の処理が中断され、待ちに入る。すなわち、先
にロック要求したタスクＴ２をタスクＴ３が追い越し、
タスクＴ３へのロック権付与が優先される。この結果、
時刻ｔｂでの排他制御テーブル５およびロック優先度テ
ーブル６は図５のような状態となる。

【００４９】時刻ｔ＋５でタスクＴ１が資源Ｒ１をアン
ロック要求（Ｕ）すると、アンロック処理手段２が呼び
出され、排他制御テーブル５のロック中タスクリストか
らタスク識別子Ｔ１が削除される。

【００５０】続いて、ロック優先度テーブル６のタスク
Ｔ１のロック中資源数部から「１」が減じられ、タスク
識別子Ｔ１をパラメータとしてロック優先度設定手段４
が呼び出され、タスクＴ１のロック優先度部に「ｆ（０
）」が設定される。この結果、排他制御テーブル５のロ
ック中タスクリストが空となるので、ロックモード部も
消去される。

【００５１】更に、ロック待ち行列は空ではないので、
最初のロック要求タスクＴ３にロック権が付与され、ロ
ックモード部に共有モードＳが、ロック中タスクリスト
にタスク識別子Ｔ３がそれぞれ記録される。

【００５２】次に、そのタスクＴ３のロック中資源数部
に「１」を加え、タスク識別子Ｔ３をパラメータとして
ロック優先度設定手段４が呼び出され、タスクＴ３のロ
ック優先度部に「ｆ（２）」が設定された後、タスクＴ
３の処理が再開される。この結果、時刻ｔｃでの排他制
御テーブル５およびロック優先度テーブル６は図６のよ
うな状態となる。

【００５３】時刻ｔ＋６でタスクＴ３が資源Ｒ１，Ｒ２
を続けてアンロック要求すると、タスクＴ１によるアン
ロック要求と同様に処理が行われ、資源Ｒ１においては
タスクＴ２に、資源Ｒ２においてはタスクＴ４にそれぞ
れロック権が付与される。この結果、時刻ｔｄでの排他
制御テーブル５およびロック優先度テーブル６は図７の
ような状態となる。

【００５４】上記の例では、ｆ（０）＜ｆ（１）＜ｆ（
２）であると仮定したが、ａ＜ｂに対してｆ（ａ）＝ｆ
（ｂ）のような関数ｆ（ｘ）も用いることができ、ロッ
ク中資源数が大差ない場合には先着順に処理した方がよ
いと思われるような環境では有利となる。この場合、動
作としては、ロック順序変更手段３でのロック待ち行列
の並べ換え時にロック中資源数ｂのタスクがロック中資
源数ａのタスクに優先されず、先着順に並べられる点が
異なる以外は同様の処理となる。

【００５５】また、ロック中資源数そのものをロック優
先度とした場合、ｆ（０）＜ｆ（１）＜……＜ｆ（ｎ）
＜ｆ（ｎ＋１）＜……となるので、タスクＴａ，Ｔｂに
ついてロック中資源数をそれぞれａ，ｂとすると、ａ＞
ｂならば常にタスクＴａのロック要求がタスクＴｂのロ
ック要求に優先されることになる。

【００５６】

【発明の効果】以上説明したように、本発明の共有資源
排他制御方式にあっては、ロック中資源数の増加に伴っ
て増加するようなロック優先度を導入し、ロック優先度
の高いタスクに対し、ロック優先度の低いタスクに優先
してロック権が付与されるよう制御することによって、
既にいくつかの資源をロックしているタスクが新たな資
源をロック要求してロック待ちとなった場合にロック待
ち時間を減少させることができ、当該タスクがロックし
ている資源に対しロック待ちしている他のタスクのロッ
ク待ち時間を減少させ、共有資源の使用効率を向上させ
ることができるという効果がある。

【図面の簡単な説明】

【図１】本発明の共有資源排他制御方式の一実施例を示
す構成図である。

【図２】図１における排他制御テーブルおよびロック優
先度テーブルの論理的構成を示す図である。

【図３】具体例を説明するためのタイミングチャートで
ある。

【図４】排他制御テーブルおよびロック優先度テーブル
の状態の例を示す図である。

【図５】排他制御テーブルおよびロック優先度テーブル
の状態の例を示す図である。

【図６】排他制御テーブルおよびロック優先度テーブル
の状態の例を示す図である。

【図７】排他制御テーブルおよびロック優先度テーブル
の状態の例を示す図である。

【符号の説明】

１……………ロック要求処理手段 ２……………アンロック要求処理手段 ３……………ロック順序変更手段 ４……………ロック優先度設定手段 ５……………排他制御テーブル ６……………ロック優先度テーブル ７……………共有資源排他制御機構 Ｔ１〜Ｔｎ…タスク Ｒ１，Ｒ２…資源

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　電子計算機システムの共有資源排他制
   御方式において、タスク対応にロック優先度を設け、タ
   スクが資源をロックした時、およびタスクがロック権の
   行使を終了した時、当該タスクのロック中資源の数ｘに
   つきｆ（ａ）≧ｆ（ｂ）が成立するａ＞ｂなるａ，ｂが
   存在し、かつｆ（ｃ）＞ｆ（ｄ）が成立するｃ＞ｄなる
   ｃ，ｄが存在する関数ｆ（ｘ）によって算出された値を
   当該タスクのロック優先度として設定するロック優先度
   設定手段と、タスクがロック待ちとなった時、ロック待
   ちタスクへのロック権付与順序がロック優先度の高い順
   となるようロック待ち行列を並べ換えるロック順序変更
   手段とを備えたことを特徴とする共有資源排他制御方式
   。
2. 【請求項２】　　ｆ（ｘ）＝ｘとしたことを特徴とする
   請求項１記載の共有資源排他制御方式。