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

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は計算機システムにおける共存資源排他制御方式
に関する。

〔従来の技術〕

計算機システムにおいて複数のタスクから使用される資
源については、それへのアクセスを逐次化するために排
他制御が必要である。このような排他制御のために、計
算機システムには、ロック／アフロツタおよびエンキュ
ー／デキューと呼ばれる基本機能が備えられており、ロ
ック要求には通常排他モードと共有モードとの２種類が
ある。

従来の排他制御の基本的動作は次のようになっている。

即ち、あるタスクがロック要求を出した場合、ロック要
求対象資源が他のタスクによりロックされていないなら
ば、すぐにロック権が与えられる。しかし、他のタスク
によりすでにロックされている場合は、その資源がロッ
クされたモードまたは要求を出したタスクのロック要求
のモードが排他モードのときはロック待ちとなる。その
資源がロックされたモードと要求を出したタスクのロッ
ク要求のモードとがともに共有モードのときは、 （１）ロック待ちタスクがない場合は、要求を出したタ
スクにロック権を与え、ロック待ちタスクがある場合は
、要求を出したタスクをロック待ちとする。

（２）要求を出したタスクに直ちにロック権を与える。

のいずれかの方法がとられる。

また、資源をロックしていたタスクがアンロツタ要求を
出した場合はこのタスクのロック権の行使が終了する。

このとき、他にロックしているタスクがなく、かつロッ
ク待ちタスクがある場合には、それらの内、最も早くロ
ック要求したタスクの要求モードが排他モードならば、
このタスクのみにロック権を与え、共有モードならば上
述の（１）（２）に対応して、 （１）現在排他モードでロック待ちしているどのタスク
よりも早く共有モードでロック待ちしているタスクすべ
てにロック権を与える。

（２）現在共有モードでロック待ちしているタスクすべ
てにロック権を与える。

のいずれかの方法がとられる。

〔発明が解決しようとする課題〕

上述した（１）の方法を採用した従来の共有資源排他制
御方式では、いかなる場合も共有モードのロック要求を
出したタスクが排他モードのロック要求を出したタスク
を追越してロックできないため、現在のロックが解け、
次のロック待ちタスクにロック権を与える際、ロック待
ちタスクのロックモードが共有モードであるときは、排
他モードのロック待ちタスクがあると、それ以後に共有
モードでロック待ちになったタスクにはロック権が与え
られず、資源を効率良く使用できない。

また、上述した（２）の方法を採用した従来の共有資源
排他制御方式では、共有モードのロック要求が排他モー
ドのロック要求よりも頻繁に行われると、いつまでも排
他モードでロック要求したタスクにロック権が与えられ
ない状況、即ち永久封鎖が発生するという欠点がある。

〔課題を解決するための手段〕

本発明の共有資源排他制御方式は、計算機システムの共
有資源排他制御方式において、共有モードのロック要求
に対し、 資源がロックされていない場合は、前記要求を出したタ
スクにロック権を与え、 資源が共有モードでロックされている場合は、排他モー
ドのロック待ちタスクがなければ前記要求を出したタス
クにロック権を与え、排他モードのロック待ちタスクが
あり、このロック待ちのいずれにおいても、その排他モ
ードのロック要求の要求順序を追越した共有モードロッ
ク要求タスクの数（以下「追越しタスク数」という）が
最大追越しタスク数Ｎ未満であれば前記要求を出したタ
スクにロック権を与え、 最大追越しタスク数Ｎの排他モードのロック待ちタスク
があり、さらに最大追越しタスク数Ｎ未満の排他モード
ロック待ちタスクがある場合は、最大追越しタスク数Ｎ
未満のタスクの中で最も多く共有モードロック要求タス
クに追越されたタスクの前にロック権が与えられるよう
ロック権の付与順序を変更して前記要求を出したタスク
をロック待ちとし、 最大追越しタスク数Ｎの排他モードロック待ちタスクが
ある場合は、現在のロック待ちタスクの中で最後にロッ
ク権が与えられるよう前記要求を出したタスクをロック
待ちとする共有要求処理手段と、 アンロック要求に対し、次にロック権を与えるべきロッ
ク待ちタスクが共有モードで要求している場合は、どの
排他モードのロック待ちタスクよりも先にロック権を与
えるべき共有モードのロック要求を出したタスクすべて
にロック権を与えるアンロック要求処理手段とを有する
ことにより構成される。

〔実施例〕

次に、本発明について図面を参照して説明する。

第１図は本発明の一実施例の構成図である。本実施例に
おいて、共有資源排他制御機能９はロック要求処理部６
とアンロック要求処理部７と排他制御テーブル８とから
なる。ロック要求処理部６は共有モードのロック要求を
処理する共有要求処理手段１と、排他モードのロック要
求を処理する排他要求処理手段２とからなる。また、ア
ンロック要求処理部７はアンロック要求したタスクのロ
ック解除を行うロック解除手段３と、次のロック待ちタ
スクの要求モードが共有モードの場合のロック処理を行
う共有待ちロック手段４と、次のロック待ちタスクの要
求モードが排他モードの場合のロック処理を行う排他待
ちロック手段５とからなる。

第２図は第１図の排他制御テーブル８の構成図である。

排他制御テーブル８は、システム内の排他制御対象資源
を一意に識別するための名前である資源名をキーとする
。各資源に対するエントリは、資源名部８１とロックモ
ード部８２とロック中タスクリスト８３とロック待ちタ
スクキュー８４とからなる。ロックモード部８２は資源
がロックされているときのロックモードを記録する。ロ
ック中タスクリスト８３はその資源をロックしているタ
スクのタスク識別子を記録する。ロック待ちタスクキュ
ー８４は待ち状態にあるロック要求の待ち行列であり、
共有モードのロック要求を出しているタスクではタスク
識別子とロックモードとの組を、排他モードのロック要
求を出しているタスクではタスク識別子とロックモード
と追越しタスク数との組を記録する。

次に第１図の各処理部の動作について説明する。

共有要求処理手段１は、共有モードのロック要求の処理
を行う。即ち、 （１）ロックモード部８２が空の場合、共有モードをロ
ックモード部８２に記録し、要求を出したタスクのタス
ク識別子をロック中タスクリスト８３に追加し、このタ
スクにロック権を与える。

（２）ロックモード部８２が空でない場合、ロック待ち
タスクキュー８４内のロック要求を先頭がら順に走査し
、追越しタスク数が最大追越しタスク数Ｎ未満の場合は
走査を終了する。また、全てのロック要求を検査し終わ
った場合は走査を終了する。この走査の結果、最大追越
しタスク数がＮ未満の排他モードロック要求が見っから
ながった場合は、ロック待ちタスクキュー８４の最後に
この共有モードロック要求を出したタスクのタスク識別
子とロックモードとの組を追加し、このタスクの処理を
中断させてロック待ちとする。ロック待ちタスクキュー
８４の先頭の要求で走査が終了し、資源が共有モードで
ロックされている場合は、この要求を出したタスクのタ
スク識別子をロック中タスクリスト８３に追加してこの
タスクにロック権を与え、ロック待ちタスクキュー８４
のすべての排他モードロック要求の追越しタスク数に１
を加える。その他の場合は、走査を終了した排他モード
ロック要求の直前にこの共有モードロック要求を出した
タスクのタスク識別子とロックモードとの組を挿入し、
このタスクの処理を中断させて、ロック待ちとし、走査
を終了した排他モードロック要求を含め、後続するすべ
ての排他モードロック要求の追越しタスク数に１を加え
る。

上記（２）により、資源が共有モードでロックされてお
り、かつ排他モードでロック待ちしているタスクがある
場合、新たな共有モードのロック要求タスクが追越せる
排他モードのロック待ちタスクは、追越した共有モード
ロック要求タスク数が最大追越しタスク数Ｎ未満のタス
クに限られることになり、永久封鎖は発生しない。

共有待ちロック手段４は、アンロツタ要求処理において
、次のロック待ちタスクが共有モードで要求している場
合のロック処理を行う。即ち、（１）ロックモード部８
２に共有モードを記録し、ロック待ちタスクキュー８４
の先頭から、連続するすべての共有モードロック要求の
タスク識別子をロック中タスクリスト８３に記録する。

次に、この記録が行われたロック要求をロック待ちタス
クキュー８４から削除し、これらのタスクの処理を再開
させ、ロック権を与える。

排他要求処理手段２は、排他モードのロック要求の処理
を行う。即ち、 （１）ロックモード部８２が空の場合、要求のロックモ
ードをロックモード部８２に記録し、この要求を出した
タスクのタスク識別子をロック中タスクリスト８３に記
録し、ロック権を与える。

（２）ロックモード部８２が空でない場合、要求を出し
たタスクのタスク識別子とこの要求のロックモードと追
越しタスク数Ｏとの組をロック待ちタスクキュー８４の
最後に追加し、この要求を出したタスクの処理を中断さ
せ、ロック待ちとする。

ロック解除手段３は、アンロツタ要求された場合のロッ
ク解除処理を行い、ロック待ちタスクがある場合には、
次のロック待ちタスクのロック処理を行うため共有待ち
ロック手段４、または排他待ちロック手段５を呼出す。

即ち、 （１）アンロツタ要求したタスクのタスク識別子をロッ
ク中タスクリスト８３から削除し、ロック中タスクリス
ト８３が空になったならば、ロックモード部８２の内容
を消去する。

（２）続いて、ロック中タスクリスト８２が空になった
場合、ロック待ちタスクキュー８４の先頭のロック要求
が共有モードなら共有待ちロック手段４を、排他モード
なら排他待ちロック手段５を呼出す。

排他待ちロック手段５はロック解除手段３から呼出され
、排他モードのロック待ちタスクのロック処理を行う。

即ち、 （１）ロック待ちタスクキュー８４の先頭にある要求の
ロックモードをロックモード部８２に、タスク識別子を
ロック中タスクリスト８３にそれぞれ記録し、このロッ
ク要求をロック待ちタスクキュー８４から削除し、ロッ
ク要求を出したタスクの処理を再開させ、ロック権を与
える。

次に、本実施例の具体的動作について、第３図の排他制
御テーブル８の内容例を参照して説明する。本実施例で
は最大追越しタスク数Ｎは固定値２であると仮定する。

第３図（ａ）〜（ｆ）は、いずれもある時点での排他制
御テーブル８の状態を示している。

第３図（ａ）は資源ＲをタスクＴ１が共をモードでロッ
クし、タスクＴ２が排他モード、追越しタスク数Ｏでロ
ック待ちしている。このときタスクＴ３が共有モードで
ロック要求すると、共有要求処理手段１が呼ばれる。資
源Ｒは共有モードでロックされているので、ロック待ち
タスクキュー８４を先頭から走査し、タスクＴ２の排他
モードのロック要求を見つける。この要求の追越しタス
ク数は０であり、最大追越しタスク数２より小さいので
走査を終了する。ロック待ちタスクキュー８４の先頭で
走査を終了し、かつ資源Ｒが共有モードでロックされて
いるので、要求したタスクのタスク識別子Ｔ３がロック
中タスクリスト８３に追加され、要求したタスクにロッ
ク権が与えられる。また、タスクＴ２の追越しタスク数
に１が加えられる。この結果、排他制御テーブル８は第
３図（ｂ）の状態となる。

次にタスクＴ４が排他モードでロック要求すると、排他
要求処理手段２が呼ばれる。すでに資源Ｒがロックされ
ているため、このタスクのタスク識別子Ｔ４と要求モー
ドＥと追越しタスク数Ｏとの組がロック待ちタスクキュ
ー８４に記録され、このタスクの処理が中断され、ロッ
ク待ちとなる。

この結果、排他制御テーブル８は第３図（Ｃ）の状態と
なる。

次にタスクＴ５が共有モードで口・ツク要求すると、共
有要求処理手段１が呼ばれる。資源Ｒかすでに共存モー
ドでロックされているため、口、ツク待ちタスクキュー
８４を先頭から順に走査し、タスクＴ２の排他モードの
ロック要求を見つける。

追越しタスク数は１であり、最大追越しタスク数２より
も小さいので走査を終了する。ロック待ちタスクキュー
８４の先頭の要求で終了し、かつ資源Ｒが共有モードで
ロックされているので、口・ツタ中タスクリスト８３に
タスク識別子Ｔ５が追加され、タスクＴ５にロック権が
与えられる。また、走査が終了したロック要求以降のす
べての排他モードロック要求の追越しタスク数に１が加
えられる。この結果、排他制御テーブル８は第３図（ｄ
）の状態となる。

次にタスクＴ６が共有モードでロック要求すると、共有
要求処理手段１が呼ばれる。資源Ｒがすでに共有モード
でロックされているため、ロック待ちタスクキュー８４
を先頭から順に走査し、タスクＴ２の排他モードロック
要求を見つける。追越しタスク数は２であり、最大追越
しタスク数２と等しいので走査を継続する。次に、タス
クＴ４の排他モードロック要求を見つける。追越しタス
ク数は１であり、最大追越しタスク数２より小さいので
走査を終了する。ロック待ちタスクキュー８４の先頭で
の終了ではないので、走査を終了した要求の直前に新し
くロック要求したタスクのタスク識別子Ｔ６と要求モー
ドＳとの組が挿入され、タスクＴ６の処理が中断されて
、ロック待ちとなる。また、走査を終了したタスクＴ４
の排他モードロック要求の追越しタスク数に１が加えら
れる。

続いて、タスクＴ７が共有モードでロック要求すると、
共有要求処理手段１が呼ばれる。資源Ｒがすでに共有モ
ードでロックされているため、ロック待ちタスクキュー
８４を先頭から順に走査する。追越しタスク数が最大追
越しタスク数２未満の排他モードロック要求はないので
、ロック待ちタスクキュー８４の最後にタスク識別子Ｔ
７と要求モードＳとの組が追加され、タスクＴ７の処理
が中断されてロック待ちとなる。この結果、排他制御テ
ーブル８は第３図（ｅ）の状態となる。

次に、タスクＴ１、Ｔ３、Ｔ５がこの順にアンロック要
求すると、各アンロック要求についてロック解除手段３
が呼出される。タスクＴ１、Ｔ３についてはロック中タ
スクリスト８３からタスク識別子Ｔｌ、Ｔ３が削除され
、いずれにおいてもロック中タスクリストは空にならな
いので、これで処理を終わる。タスクＴ５のアンロック
要求では、ロック中タスクリスト８３からタスク識別子
Ｔ５を削除すると、ロック中タスクリスト８３が空とな
るので、ロック待ちタスクキュー８４の先頭の要求を調
べる。先頭は排他モードの要求なので、排他待ちロック
手段５が呼出され、排他モードＥをロックモード部８２
に、タスク識別子Ｔ２をロック中タスクリスト８３にそ
れぞれ記録し、この排他モードのロック要求をロック待
ちタスクキュー８４から削除し、ロック要求を出したタ
スクの処理を再開させて、ロック権を与える。この結果
、排他制御テーブル８は第３図（ｆ）の状態となる。

次に、タスクＴ２がアンロック要求すると、ロック解除
手段３が呼出され、ロック中タスクリスト８３からタス
ク識別子Ｔ２が削除される。ロック中タスクリスト８３
が空となったので、ロックモード部８２を消去する。ロ
ック待ちタスクキュー８４の先頭の要求が共有モードな
ので、共有待ちロック手段４が呼出され、ロックモード
部８２に共有モードＳが、ロック中タスクリスト８３に
、ロック待ちタスクキュー８４の先頭から連続するすべ
ての共有モードロック要求のタスク識別子としてＴ６が
それぞれ記録される。ロック待ちタスクキュー８４から
タスクＴ６の要求を削除し、タスクＴ６の処理が再開さ
れてロック権が与えられる。この結果、排他制御テーブ
ル８は第３図（ｇ）の状態となる。

本実施例では、最大追越しタスク数を資源の種類にかか
わらず固定値Ｎとしたが、排他制御テーブル８内に最大
追越しタスク数の欄を設けて各資源ごとに異なった最大
追越しタスク数Ｎを記録し、これを用いて制御すること
も可能である。

〔発明の効果〕

以上説明したように本発明は、排他モードでロック待ち
しているタスクを追越した共有モードロック要求タスク
の数が、最大追越しタスク数Ｎ未満である場合に限り、
共有モードでロック要求したタスクが追越すのを許すこ
とにより、永久封鎖の問題を避けながら共有資源の使用
効率を向上させることができる効果がある。

制御テーブルの内容例の図である。

１・・・共有要求処理手段、２・・・排他要求処理手段
、３・・・ロック解除手段、４・・・共有待ちロック手
段、５・・・排他待ちロック手段、６・・・ロック要求
処理部、７・・・アンロック要求処理部、８・・・排他
制御テーブル、９・・・共有資源排他制御機能、１０・
・・共存資源使用タスク。

Claims (1)

1. 【特許請求の範囲】 計算機システムの共有資源排他制御方式において、共有
   モードのロック要求に対し、 資源がロックされていない場合は、前記要求を出したタ
   スクにロック権を与え、 資源が共有モードでロックされている場合は、排他モー
   ドのロック待ちタスクがなければ前記要求を出したタス
   クにロック権を与え、排他モードのロック待ちタスクが
   あり、このロック待ちのいずれにおいても、その排他モ
   ードのロック要求の要求順序を追越した共有モードロッ
   ク要求タスクの数（以下「追越しタスク数」という）が
   最大追越しタスク数Ｎ未満であれば前記要求を出したタ
   スクにロック権を与え、 最大追越しタスク数Ｎの排他モードのロック待ちタスク
   があり、さらに最大追越しタスク数Ｎ未満の排他モード
   ロック待ちタスクがある場合は、最大追越しタスク数Ｎ
   未満のタスクの中で最も多く共有モードロック要求タス
   クに追越されたタスクの前にロック権が与えられるよう
   ロック権の付与順序を変更して前記要求を出したタスク
   をロック待ちとし、 最大追越しタスク数Ｎの排他モードロック待ちタスクが
   ある場合は、現在のロック待ちタスクの中で最後にロッ
   ク権が与えられるよう前記要求を出したタスクをロック
   待ちとする共有要求処理手段と、 アンロック要求に対し、次にロック権を与えるべきロッ
   ク待ちタスクが共有モードで要求している場合は、どの
   排他モードのロック待ちタスクよりも先にロック権を与
   えるべき共有モードのロック要求を出したタスクすべて
   にロック権を与えるアンロック要求処理手段とを有する
   ことを特徴とする共有資源排他制御方式。