JPH11327931A

JPH11327931A - セマフォ操作を実行する方法及び装置

Info

Publication number: JPH11327931A
Application number: JP11074165A
Authority: JP
Inventors: Donald F Ault; ドナルド・エフ・アルト; John M Forsythe; ジョーン・エム・フォースザ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1998-03-18
Filing date: 1999-03-18
Publication date: 1999-11-30
Also published as: EP0943993A3; KR19990077481A; US6237019B1; EP0943993A2

Abstract

(57)【要約】（修正有）【課題】共有資源へアクセスするのを制御するためのセ
マフォ操作の方法。【解決手段】セマフォは、シーケンス番号を含む第１セ
マフォ・フィールドと、待ち行列へのポインターを含む
第２セマフォ・フィールドを有する。待ち行列の、各エ
ントリはセマフォのウエイターに対応し、次のエントリ
を差すポインターを有する。指定された操作に従って、
インクリメントされたシーケンス番号を含む第１の置換
値が、第１セマフォ・フィールドのために生成される。
待ち行列が変更されている場合、第２セマフォ・フィー
ルドのための第２置換値と待ち行列エントリの１つのた
めの第３置換値が生成される。第１セマフォ・フィール
ドの現在値が、シーケンス番号を含む比較値と比較さ
れ、一致する場合第１置換値で置換し、待ち行列が変更
されている場合、第２又は第３置換値で置換される。一
致しない場合、セマフォ・フィールドの新しく保管され
た値を比較値として、セマフォ操作が再試行される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、セマフォ（ｓｅｍａｐ
ｈｏｒｅ）に基づく操作を実行する方法及び装置に関す
る。より詳細には、本発明は、２進セマフォ（ｂｉｎａ
ｒｙｓｅｍａｐｈｏｒｅ）に関する操作を実行する方
法及び装置に関する。

【０００２】

【従来の技術】コンピュータの世界において、共有資源
へのアクセスを直列するために使われる、セマフォとし
て知れてた公知の直列化（ｓｅｒｉａｌｉｚａｔｉｏ
ｎ）機構が存在する。セマフォとは、ゼロと所定の正の
数ｎの間で可変な整数であり、ｎは資源の同時使用を許
可された要求元（ｒｅｑｕｅｓｔｅｒ）の数である。２
進セマフォの場合、ｎ＝１は単に１の要求元のみが１度
に資源を使用できる。最初セマフォは、ｎとセットされ
る。資源へのアクセスを確保するために、要求元(例え
ばプロセス又はスレッドのような作業単位）は、セマフ
ォの現在値をテストする。一方現在値ゼロより大きい場
合、現在値を１ディクリメントして、要求元は中断され
（即ち、スリープ（ｓｌｅｅｐ）し）、セマフォのウエ
イター（ｗａｉｔｅｒ）として待ち行列（ｑｕｅｕｅ）
に入る。資源を解放するために、要求元はセマフォ値を
１インクリメントする。その上、セマフォの待ち行列に
幾つかウエイターが存在する場合、ウエイターの１つに
通知され、最初に行ったようにセマフォをテストして、
そのウエイターは再び資源を確保を試みる。セマフォ
（Ｓｅｍａｐｈｏｒｅｓ）は最初ジャクストラ（Ｄｉｊ
ｋｓｔｒａ）に提案され、刊行物（タネンバーム（Ｔａ
ｎｅｎｂａｕｍ）のＭｏｄｅｒｎＯｐｅｒａｔｉｎｇ
Ｓｙｓｔｅｍｓ（１９８２）ｐ．４１〜４３；ヘイズ
（Ｈｅｙｅｓ）のＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃ
ｔｕｒｅａｎｄＯｒｇａｎｉｚａｔｉｏｎ（１９９
８）Ｐ．５４０；スティーブンのＵＮＩＸＮｅｔｗｏ
ｒｋＰｒｏｇｒａｍｍｉｎｇ（１９９０）ｐ．１３７
〜１５２）に記載されている。

【０００３】計数セマフォ（ｃｏｕｎｔｉｎｇｓｅｍ
ａｐｈｏｒｅｓ：ｎ＞１）と２進セマフォ（ｂｉｎａｒ
ｙｓｅｍａｐｈｏｒｅｓ：ｎ＝１）の２つの主要なタ
イプのセマフォが存在する。本明細書では、多くのセマ
フォ実装に固有の問題を説明してから、本発明の高パフ
ォーマンスのセマフォ実装を説明する。本発明は、２進
セマフォに限定されないが、その説明は、始めは２進セ
マフォによりなされる。

【０００４】図１は、セマフォ・セットのＣ言語例であ
る。Ｃプログラムがｓｅｍｇｅｔファンクションを呼ぶ
とセマフォ・セットは初めに生成される。（ここで、Ｃ
ソース言語での記述は、説明め便宜のためである。実際
ステップを実行するコードは、もちろんソース・コード
をコンパイルして生成されたオブジェクト・コードであ
る。）呼出し元は、幾つのセマフォ１２０がセマフォ・
セット１１５にあるか定義する。セマフォ・セットが生
成されるその時、１つのｓｅｍｉｄ（セマフォｉｄ）が
呼出し元に戻される。このｓｅｍｉｄは、ｓｅｍｏｐ関
数の後続の呼出し（ｃａｌｌ）の各々の際に使われる。
オペレーティング・システムは、そのセマフォ・セットを
テーブル１０５内に記録し、そのテーブルには各エント
リ１１０と関連するセマフォ・セット１１５が記録され
る。

【０００５】図２は、セマフォ処理が通常どのように機
能するか一般的記述を与える。図は、プロセス１（２０
５）とプロセス２（２１０）が同じセマフォを求めて競
争することを示す。一般的な２進セマフォの動作は、セ
マフォ値が１に初期化される（利用可能）。アプリケー
ションがセマフォを獲得したい時、ｓｅｍｏｐ（−１）
を実行してセマフォ値をディクリメントとする。セマフ
ォの主要なルールは、セマフォ値が負になることは許さ
れないことである。従って、セマフォ値をディクリメン
トして０にするｓｅｍｏｐの最初の呼出し元は、セマフ
ォを所有する。セマフォ値をディクリメントする後続の
要求（ｒｅｑｕｅｓｔ）は、呼出し元を中断させること
になる。

【０００６】プロセス１（２０５）は、ｓｅｍｏｐ（−
１）を呼ぶ（ステップ２２０）。これは、セマフォ処理
のためにカーネル２１５に入る。カーネルは、セマフォ
の状態を見て、状態が現在１の値であることを知る。カ
ーネルはセマフォ値をディクリメントして、値を１から
０に変更し、結果的にプロセス１へのアクセスを認める
（ステップ２２２）。その後カーネルは、プロセス１に
戻る（ステップ２２４）。プロセス１は今は、セマフォ
に保護されたどんな重要な資源でもアクセス可能である
（ステップ２２６）。この資源は、メモリ、ＤＡＳＤ上
のファイル、又は、多重プロセスにおいてコンカレント
に実行できないコードのまさにクリティカル・セクショ
ンである。

【０００７】プロセス１はセマフォを所有する一方、プ
ロセス２（２１０）も同じセマフォに対してｓｅｍｏｐ
（−１）を要求する。カーネルは、その−１を実行でき
ない。なぜならその値は現在０であり、負にできないか
らである。従ってカーネルは、呼出し元（プロセス２）
を中断する（ステップ２３０）。

【０００８】最終的にプロセス１は重要資源のアクセス
を終了し、ｓｅｍｏｐ（＋１）を実行する（ステップ２
３２）。カーネルはセマフォ値を０から１に変更して、
中止しているプロセス２を再開する（ステップ２３
４）。次にプロセス２のために動作しているカーネル
は、ステップ値を０から１に変更し（ステップ２３
６）、プロセス２にセマフォの所有権を認める。その後
プロセス２は重要な資源にアクセスできる（ステップ２
４０）。最初のウエイターに通知した後、制御は呼出し
元に戻る（ステップ２３８）。プロセス２は資源にアク
セスすることを実行する時に、Ｓｅｍｏｐ（−１）を出
してセマフォを解放する（ステップ２４２）。セマフォ
を求めるウエイターは存在しないから、制御は呼出し元
に戻る（ステップ２４４）。

【０００９】これらは、セマフォ処理がどのように動く
かの論理的説明である。対称マルチプロセッサ（ＳＭ
Ｐ）環境において動作する時は異なる中央処理ユニット
（ＣＰＵｓ）上で動作するプロセスは、コンカレントに
セマフォを獲得又は解放することを試みることが出来
る。図３は、従来のセマフォ実装に関して生じ得る複雑
さを示す。

【００１０】カーネルのセマフォ・ロジックがアトミッ
クにセマフォ値と更新し、待ち行列を維持するために、
カーネルがロック（ｌｏｃｋ）又はｍｕｔｅｘ（mutual
exclusion lock）のある形式を獲得することは必要な
ことであり、それは特定のプラットフォームにとってユ
ニークなものではない。カーネルがこのロックを所有す
る時、ｓｅｍｏｐの他の呼出し元は、中断してこのロッ
クを待つ。このロックは、セマフォの概念と非常に類似
する。

【００１１】図３において、擬似コードの最初のブロッ
クは、ｓｅｍｏｐ（−１）を実行するｓｅｍｏｐ内の処
理、即ち２進セマフォの確保を表す（ステップ３１
０）。第１ステップは、セマフォ構造を直列化するため
にｌｏｃｋを確保する（ステップ３１２）。このｌｏｃ
ｋが利用可能でない場合、システムは、呼出しスレッド
を中断し、プロセスを表す待ち行列の要素３６２を生成
することにより、スレッドをｌｏｃｋ待ち行列３６０に
置く。このｌｏｃｋが利用可能になった場合、このプロ
セスは再開され、スレッドが処理されている間セマフォ
構造が変化しないことを知りながら、過去のステップ３
１２の続行可能である。セマフォが利用可能な場合（ス
テップ３１４）、セマフォ値を変更することにより、カ
ーネルは、セマフォを呼出し元に与える（ステップ３１
６）。その後カーネルは内部ｌｏｃｋを解放し（ステッ
プ３１８）、待ち行列３６０上の他のプロセスの再開し
得る。その後制御は、呼出し元に戻る（ステップ３１
９）。

【００１２】セマフォ値が利用可能でない場合（ステッ
プ３２０）、カーネルは、内部ロックを解放し（ステッ
プ３２２）、呼出し元を中断し、セマフォ待ち（ｗａｉ
ｔｅｒ）要素３７２をセマフォ待ち行列３７０に加える
（ステップ３２４）。このプロセスが再開された時に
（ステップ３２６）、ステップ３１２でプロセスが始ま
る（ステップ３２８）。

【００１３】プロセスがｓｅｍｏｐ（-１）を呼び、２
進セマフォを解放する時（ステップ３４０）、カーネル
は最初に内部ｌｏｃｋを確保してセマフォ構造へのアク
セスを直列化する（ステップ３４２）。このｌｏｃｋが
利用可能でない場合、システムは呼出しスレッドを中断
し、プロセスを表す行列要素３６２を生成することによ
りｌｏｃｋ待ち行列３６０上にスレッドを置く。このｌ
ｏｃｋが利用可能になった時に、このプロセスは再開さ
れて、プロセスが処理されている間セマフォ構造は変化
しないことを知りながら、過去のステップ３４２を続行
可能である。次にカーネルは、１つインクリメントする
ことによりセマフォ値を変更する（ステップ３４４）。
セマフォ待ち行列３７０にウエイター（ｗａｉｔｅｒ）
が存在する場合、第１の要素３７２は除かれ、それが示
すプロセスを再開する（ステップ３４６）。次にカーネ
ルは内部ｌｏｃｋを解放して（ステップ３４８）、待ち
行列３６０に存在する他のプロセスを再開する。制御
は、呼出し元に戻る（ステップ３５０）。

【００１４】今異常な例を考える。もし５００のプロセ
スが、コンカレントに１つのセマフォを要求する。１つ
のプロセスが、うまく内部ｌｏｃｋを獲得し、４９９の
プロセスは中断し内部ｌｏｃｋ待ち行列３６０に加えら
れる。次に第１のプロセスが内部ｌｏｃｋを解放して、
一つ一つ各プロセスがｌｏｃｋを獲得し、単にセマフォ
が利用不可能であることを発見する（ステップ３２０に
おいて）、そして、各プロセスは第２の時間中断され
て、この時間の間セマフォ待ち行列３７０上存在する。
今４９９プロセスの中間において、第１プロセスがまさ
にセマフォを解放しようとしている。セマフォを解放す
ることは、同じ内部ｌｏｃｋも要求するから（ステップ
３４２において）、このプロセスは内部ｌｏｃｋの待ち
行列の最後に置かれる。このことは、単に各プロセスを
内部ｌｏｃｋ待ち行列３６０からセマフォ待ち行列３７
０への移動させることを保証する。

【００１５】これを類似形態に適用すると、見世物（ｓ
ｈｏｗ）の切符を買うために待っている人の列を想像で
きる。各人が列の先頭に至ると、彼らは切符がないと言
われる。しかし彼ら、誰かがキャンセルするまで列上を
待つことができる。切符をキャンセルしたい人も来が、
しかし、切符を買いたい全ての人のために、同じ列で待
たなければならない。今これを繰返すと、多くの意味の
ない待ちをしなければならない。コンピュータ・システ
ムにおいて、これが悪いパフォーマンスと制限されたキ
ャパシティーとして現れる。

【００１６】

【発明が解決しようとする課題】本発明は、アトミック
演算を使って実装された情報処理システム内の共有資源
へアクセスするのを制御するためのセマフォ操作の方法
及び装置を与える。

【００１７】

【課題を解決するための手段】アトミック演算は、オペ
ランドを比較値で比較し、オペランドが比較値と等しい
場合、比較されたオペランドと３つまでの追加のオペラ
ンドを置換値で置換える。本発明によると、セマフォは
１つの値を含む第１セマフォ・フィールドと、セマフォ
の待ち行列へのポインターを含む第２セマフォ・フィー
ルドを有する。待ち行列は、ゼロ又はそれ以上のエント
リを有し、エントリはセマフォのウエイターに対応し、
各エントリは次のエントリを差すポインターを有する。
そのセマフォを実装するために、第１セマフォ・フィー
ルドの先の値は、比較値として蓄えられる。指定された
操作に従って、インクリメントされたシーケンス番号を
含む第１の置換値が、第１オペランドとして、第１セマ
フォ・フィールドのために生成される。待ち行列が変更
されている場合、第２セマフォ・フィールドのための第
２置換値と待ち行列エントリの１つのための第３置換値
と、第２及び第３オペランドとして生成される。第１セ
マフォ・フィールドの現在値が、後で比較値と比較され
て、その現在値がその比較値と一致するかを知る。一致
する場合、アトミックに比較ステップによって、第１オ
ペランドを第１置換値で置換する。待ち行列が変更され
ている場合、第２及び第３オペランドの一方又は両方を
対応する置換値で置換する。第１セマフォ・フィールド
の現在値が比較値を一致しない場合、比較値として、セ
マフォ・フィールドの新しく保存された値を使ってセマ
フォ操作が再試行される。

【００１８】好ましくは第１セマフォ・フィールドは、
最後のプロセスを特定するプロセスＩＤ（ＰＩＤ）も含
み、セマフォと、セマフォが更新されるごとにインクリ
メントされるシーケンス番号とを更新する。本発明は、
特定のプラットフォーム又は２進セマフォに限定される
ものではないが、ＩＢＭシステム／３９０（Ｓ／３９
０）のハードウエア・プラットフォーム上に実装された
本発明の典型的な実施例は、通常よく使われているタイ
プのセマフォ動作、２進セマフォの直列化のための、新
しいＳ／３９０のハードウエア命令ＰｅｒｆｏｒｍＬ
ｏｃｋｅｄＯｐｅｒａｔｉｏｎ（ＰＬＯ）を使用す
る。

【００１９】３つのまでの他のフィールドを置換すると
ともに比較コピーがフィールドから確保されてから、フ
ィールドが変更されてない場合、ＰＬＯ命令のｃｏｍ
ｐａｒｅａｎｄｓｗａｐ形式は、フィールドを置換
することを許容する。２進セマフォへに対する実装に制
限することにより、一般には本発明は、２進セマフォに
限定されないが、セマフォ変化の際に変更される必要な
フィールドは、ＰＬＯ命令で許される最大４つに制限で
きる。ＰＬＯ命令を用いると、セマフォ値とセマフォ待
ち行列の更新を、アトミック命令に関して直列化でき
る。２進セマフォの規則（ｒｕｌｅ）は、次の通りであ
る。１．ｓｅｍｏｐ（）上のセマフォ操作（ｓｅｍａｐｈｏ
ｒｅｏｐｅｒａｔｉｏｎｓ）の数は、１である。２．セマフォ値が０又は−１のとき、そのｓｅｍｏ
ｐ（）値は＋１でなければならない。そして０又は１の
セマフォ値を持つ。３．ＳＥＭ＿ＵＮＤＯは、ｓｅｍｏｐ（）上では許容さ
れない。４．ｓｅｍｃｔｌ（）ｓｅｔｖａｌ又はｓｅｔａｌｌ値
は、ｓｅｔａｌｌが実行された時に限定されて、０又は
＋１のみとなり得る。それは、１から０、０から０と設
定できず、単に０から１の設定が可能である。この拡張に対する規則違反は、要求された操作を失敗さ
せる。これまで既に観察されてきた大多数のセマフォの
用法は、これらの規則に従っている。

【００２０】各セマフォ値又はセマフォ待ち行列の変化
に基づくてインクリメントされ、ＰＬＯｃｏｍｐａｒ
ｅａｎｄｓｗａｐのターゲットの部分であるシーケ
ンス番号の使用は、変化のセットアップと実際の変化と
の間で、セマフォに行われるどんな変化の検出も可能に
する。変化が生じなかった場合更新が起こる。変化が現
実に起こった場合更新がされず、セットアップが再び実
行される。

【００２１】本発明の操作の特別な例として、１つの作
業（ｗｏｒｋ）単位（例えば１つのスレッド）が２進セ
マフォを要求する。スレッドは、ｃｏｍｐａｒｅａｎ
ｄｓｗａｐのエリアのコピーを手に入れる。そのエリ
アは、シーケンス番号とセマフォ値を含む。その後スレ
ッドは、セマフォが保持されているかを決定する。保持
されている場合、スレッドは待ち行列を見る。待ち行列
上にウエイターがない場合、スレッドは、ＣＯＭＰＡＲ
ＥＡＮＤＳＷＡＰパラメータをセットアップして、シ
ーケンス番号をインクリメントし、待ち行列の先頭と最
後尾のポインターがこのスレッドを差す。そしてそのＣ
ＯＭＰＡＲＥＡＮＤＳＷＡＰ命令が実行される。その
命令が成功した場合、シーケンス番号が更新され、待ち
行列ポインターはスレッドを差す。その後このスレッド
は中断する。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ命令が成
功でない場合、スレッドは戻り、プロシジャーを再開す
る。可能性として、セマフォが解放されまた待ち行列が
更新される。セマフォが今利用可能である場合、スレッ
ドをセットアップして、セマフォ値を変更し、シーケン
ス番号をインクリメントする。変更されたのが待ち行列
の場合、スレッドをセットアップして、自分自身を待ち
行列の最後に加える。どちらのケースにおいても、ＣＯ
ＭＰＡＲＥＡＮＤＳＷＡＰ命令はその時実行されて、
成功しない場合はスレッドが戻り、再び試行される。

【００２２】ここに、同様にＰＬＯＣＯＭＰＡＲＥ
ＡＮＤＳＷＡＰ命令と同じセマフォの上部からのフロ
ーがある。１．１つの作業単位（例えばスレッド）は、ｓｅｍｏｐ
要求（ｒｅｑｕｅｓｔ）を出して１つのセマフォ（ｓｅ
ｍｏｐ−１）を獲得する。２．カーネルは、ｃｏｍｐａｒｅａｎｄｓｗａｐデー
タ（セマフォを更新するセマフォ値、シーケンス番号、
及び、最後のプロセスのプロセスＩＤ）を保存する。セ
マフォが利用不可能な場合（ｓｅｍｖａｌ０）、カー
ネルをセットアップして、作業単位を待ち行列上に起
き、シーケンス番号をインクリメントする。３．カーネルは、ＰＬＯｃｏｍｐａｒｅａｎｄｓｗ
ａｐを用いて、命令をストアーして（３つまでの追加の
フィールドをストアーできる）、作業単位をセマフォ待
ち行列上に置き、シーケンス番号を更新する。ｃｏｍｐ
ａｒｅａｎｄｓｗａｐデータが変化している場合は、
カーネルを前のｓｗａｐに戻す。４．その作業は中断する（即ち待つ）。５．その作業単位は、最後に通知される（起動の準備を
される）。６．カーネルは、ｃｏｍｐａｒｅａｎｄｓｗａｐデー
タ（セマフォを更新するセマフォ値、シーケンス番号、
及び、最後のプロセスのプロセスＩＤ）を保存する。セ
マフォが利用可能な場合（ｓｅｍｖａｌ１であり、待
ち行列が空即ちこのスレッドが通知される）、カーネル
を設定して、新しいセマフォ値（ｓｅｍｖａｌ０）を
セットし、シーケンス番号をインクリメントする。７．カーネルは、ＰＬＯｃｏｍｐａｒｅａｎｄｓｗ
ａｐ命令を用いてその作業単位をセマフォ待ち行列から
除去し、新しいセマフォ値をセットし、シーケンス番号
を更新する。ｃｏｍｐａｒｅａｎｄｓｗａｐデータに
変化がない場合、更新は完了する。ｃｏｍｐａｒｅａ
ｎｄｓｗａｐデータに変化がある場合、カーネルは前
のステップに戻る。８．カーネルは、呼出し元に退出する。

【００２３】同様に、本発明の解放フローは、次のよう
に与えられる。１．作業単位は、１つのｓｅｍｏｐ要求を出し、１つの
セマフォを解放する（ｓｅｍｏｐ＋１）。２．カーネルは、ｃｏｍｐａｒｅａｎｄｓｗａｐデー
タ（セマフォを更新するセマフォ値、シーケンス番号、
及び、最後のプロセスのプロセスＩＤ）を保存する。カ
ーネルをセットアップして、新しいセマフォ値（ｓｅｍ
ｖａｌ１）をセットし、シーケンス番号をインクリメ
ントする。待ち行列が空でない場合、カーネルは除去さ
れる第１のウエイターをセットアップもする。３．カーネルはＰＬＯｃｏｍｐａｒｅａｎｄｓｗａ
ｐを用い、命令をストアして、新しいセマフォをセット
し、シーケンス番号を更新し、待ち行列が空でない場合
に、第１のウエイターを除去する。compare and swapデ
ータが変化していない場合更新は完了する。compare an
d swapデータが変化している場合、カーネルは前のステ
ップに戻る。４．カーネルは、待ち行列上の最初の作業単位にポスト
する。５．カーネルは、呼出し元に退出する。この例から解るように、本発明に関して、可能な３つの
代わりに、セマフォが利用不可能な場合に１つのみが中
断する。セマフォの解放は、１つのロックを待たない。
典型的な実装において、古い方法を用いて、セマフォを
獲得する命令の数は、本発明の約４００命令に対して、
最悪のケースで３，００００のオーダーである。

【００２４】

【発明の実施の形態】図４〜図２４は、本発明を表す。
本発明の第１の結果は、追加のロックなしにセマフォを
準備することである。

【００２５】図４は、セマフォ・セット１１５（図１）
内の１つのセマフォ１２０の構造を示す。セマフォ４１
５の見なされるこの構造の部分は、プロセスＩＤ（ＰＩ
Ｄ）４２５、シーケンス番号（ＳＥＱ）４３０、及びセ
マフォ値（ＶＡＬ）４３５で構成されている。典型的な
実施例において、セマフォ・フィールド４１５は、４バ
イト（３２ｂｉｔ）ＰＩＤ４２５、２バイト・シーケン
ス番号４３０、及び２バイト・セマフォ値４３５で構成
されたダブルワード（６４ｂｉｔ）・フィールドであ
る。セマフォ４１５とともに、待ち行列アンカー（又は
待ち行列ヘッダー）４２０が存在する。待ち行列アンカ
ー４２０は、セマフォを待つスレッドを記憶するために
用いられる。待ち行列３７０（図３）は、単一スレッド
化され（ｓｉｎｇｌｅ−ｔｈｒｅａｄｅｄ）、ダブル
・ヘッド化され（ｄｏｕｂｌｅ−ｈｅａｄｅｄ）た行列
として管理される。これは、ポインター４４０が待ち行
列３７０の先頭を差し、ポインター４４５が待ち行列の
最後尾（最後のエントリ３７２）を差すことを要求す
る。典型的な実施例において、待ち行列ヘッダー４２０
は、４バイト・ヘッダー・ポインター４４０及び４バイト
・テイル・ポインター４６０を含むダブル・ワード・フィ
ールドである。

【００２６】本明細書において、１つの作業（ｗｏｒ
ｋ）単位は、スレッドと呼ばれる（１つのプロセスには
１以上にスレッドがあるが、これがデザインに影響を及
ぶすものではない。）。スレッドは、スレッド制御ブロ
ック４５０で用いてオペレーティング・システム（Ｏ
Ｓ）のカーネル２１５（図２）により追跡される。スレ
ッド制御ブロック４５０の部分４７０は、セマフォで包
含されスレッドを追跡するために用いられる。このセマ
フォ・エリア４７０には、待ち行列３７０に対して使わ
れる、フォワード・ポインター（ＮＥＸＴ）４５５とセ
マフォ処理で使用されるフラグ・セット４６０とが存在
する。このエリアの第１のフラグは、スレッド制御ブロ
ックが待ち行列上にある在るか否かを示す。この典型的
実施例では、スレッド制御ブロック部分４７０は、４バ
イト・フォワード・ポインター４５５と４バイト・フラ
グ・エリア４６０により構成されてる。

【００２７】最初に説明したように、ｓｅｍｏｐ（−
１）はセマフォの所有権を獲得するために用い、ｓｅｍ
ｏｐ（＋１）はセマフォの所有権を解放するために用い
られる。ｓｅｍｏｐのためのハイレベルのフローが、図
５〜図８に示される。

【００２８】図５は、ｓｅｍｏｐファンクションへのエ
ントリを示す（ステップ５０２）。最初のｓｅｍｏｐ処
理の間、ｓｅｍｏｐ・ロジックは、セマフォＩＤのテー
ブル１０５（図１）内にｓｅｍｉｄ１１０を捜して、セ
マフォ・セット１１５の場所を見つける。次にセマフォ
・ロジックは、ｓｅｍｏｐ呼出しを通過したセマフォの
数に基づいて特定のセマフォ１２０の場所を位置づけ
る。これらは、セマフォ処理の従来のステップであり、
本発明の部分ではない。他の従来ステップについては本
発明ではないためここでは詳細に説明しない。しかし、
このステップは、呼出し元のパラメータの妥当性検査と
ユーザーのセマフォ・セットへのアクセスの許可検査を
行う。次に焦点を与えるのはセマフォの処理である。

【００２９】セマフォ処理が行う第１の事は、これがｏ
ｂｔａｉｎ（−１）又はｒｅｌｅａｓｅ（＋１）のどち
らかであるかを決定することである（ステップ５０
４）。それが、ｒｅｌｅａｓｅ（ＯＰ＝１）の場合、図
７に示しようなｓｅｍｏｐ処理となる（ステップ５０
６）。要求がセマフォ（ＯＰ＝−１）である場合、セマ
フォを獲得されるまで無限ループに入る（ステップ５０
８）。この処理を終了して、セマフォの様々な可能な状
態を扱う。ケース１（ステップ５１０）で示されたテス
トは、セマフォが利用不可能でないこと（ｓｅｍｖａｌ
＝０）及び（先頭ポインター４４０により指示されるよ
うに）待ち行列３７０が空であることを、決定する。こ
のケースにおいて、図１０・１１に示される処理が行わ
れる。

【００３０】ケース２として示される次のテストは、セ
マフォが利用可能でないことを決定する（ステップ５１
４）。ｓｅｍｖａｌが０の場合即ち待ち行列３７０上
にウエイターいる時は伝統的なケースは利用可能でな
い。しかし、このスレッドは、次にセマフォを獲得する
ために通知されたものではない。利用可能でないセマフ
ォを求めるこの第二の条件は、新しいセマフォ要求が既
に待っているセマフォ要求の前で切られるのを防止す
る。このケースにおいて、その処理は図１２・１３に示
されるものである（ステップ５１６）。

【００３１】これらケースのどちらもできよう出来ない
場合、処理は図６において示されるように続けられる
（ステップ５２２）。ケース１または２のための処理が
生じている場合、制御は、セマフォ操作（ｓｅｍａｐｈ
ｏｒｅｍａｎｉｐｕｌａｔｉｏｎ）の成功をテストす
るステップ５２４において、図５に戻る。全てがＯＫの
場合呼出しスレッドは待ち状態に位置する（ステップ５
２６）。そのスレッドは、所有スレッドがセマフォを解
放するまで待ち状態に残る。セマフォ操作が成功でない
場合、ループをステップ５０８に戻る。セマフォ操作の
故障の理由は別のスレッドが競争に勝ってセマフォ状態
を変更したからであり、ステップ５１０で開始する全て
テストは再度実行される。

【００３２】図６はｓｅｍｏｐ（−１）を処理しセマフ
ォが現在利用可能なケースをカバーする。待ち行列３７
０上にウエイターがなく、またはこのスレッドに通知さ
れてセマフォを獲得できる場合、これはケース３であり
（ステップ５３０）、その処理は図１４・１５に示され
るものである（ステップ５３２）。ＣＯＭＰＡＲＥＡＮ
ＤＳＷＡＰ操作が成功な場合（ステップ５４２）、制
御はセマフォを保持するユーザに戻る（ステップ５４
４）。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が失敗した
場合、処理を再開してステップ５０８で図５に戻る（ス
テップ５４６）。

【００３３】図５のテスト５０４がｓｅｍｏｐ（＋１）
を検出すると、制御が図７に流れる（ステップ５０
６）。後者の図面を参照すると、セマフォ解放ロジック
はＤＯＦＯＲＥＶＥＲループで始まる（ステップ５５
０）。セマフォを解放する時に考えられる２つのケース
がある。ケース４（ステップ５５２）は待ち行列３７０
上にウエイターがない時である。ケース４のためのＣＯ
ＭＰＡＲＥＡＮＤＳＷＡＰ操作は、図１６・１７にお
いて示されるものである（ステップ５５４）。セマフォ
操作が試みられた後、ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ
操作の結果がテストされる（ステップ５６０）。操作が
成功な場合、制御が呼出し元に戻る（ステップ５６
６）。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が成功でな
い場合、制御はステップ５５０に戻りセマフォの解放の
試みを繰返す（ステップ５６４）。セマフォ解放を失敗
した第１の理由は、新しいウエイターが待ち行列３７０
に追加されたからである。

【００３４】ケース５（ステップ５５６）は、待ち行列
上にウエイターが存在する時である。ケース５のための
ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作は、図１８・１９
に示されるものである（ステップ５５８）。ＣＯＭＰＡ
ＲＥＡＮＤＳＷＡＰ操作が成功でない場合、制御はス
テップ５５０に戻りセマフォの解放の試行を繰返す（ス
テップ５７０）。セマフォ解放を失敗した第１の理由
は、新しいウエイターが待ち行列３７０に追加されたか
らである。

【００３５】図８は、セマフォが解放された後の処理を
示す。第１ステップは、図７でのセマフォ解放操作にお
いて待ち行列３７０から除去されたウエイターに通知
（ＰＯＳＴ）する（即ち回復する）（ステップ５７
２）。通知（ＰＯＳＴ）が成功な場合（ステップ５７
４）、制御は呼び手に戻される（ステップ５７６）。通
知（ＰＯＳＴ）が失敗した場合、待ち行列３７０上ウエ
イターが存在するかを知るためにチェックされる（ステ
ップ５７８）。待ち行列３７０上にウエイターが存在す
る場合、図２０・２１に示しＣＯＭＰＡＲＥＡＮＤＳ
ＷＡＰ操作が実行され先頭のウエイターを除去する（ス
テップ５８０）。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作
が成功の場合（ステップ５８２）、以前のように待ち行
列からちょうど除去されたウエイターに通知される（ス
テップ５７２）。ステップ５７８で待ち行列３７０上に
ウエイターが存在しない場合、通知（ＰＯＳＴ）すべき
ウエイターが存在しないため、制御は呼び手に戻る（ス
テップ５７６）。通知を失敗した主な理由は、目的のス
レッドが信号を受取とり、もはや待ちの中に存在しない
からである。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作がス
テップ５８２で失敗した場合、制御はステップ５７８に
おいて多くのウエイターのためのチェックに戻る。

【００３６】スレッドが、そのスレッドに終了するよう
に（恐多分終了信号により）通知された時点でセマフォ
待ち行列上にそのスレッド制御ブロックを有している
時、ステップ５８４で始まり生ずる回復フローを図９は
示す。スレッド制御ブロックは、セマフォ待ち行列から
うまく除去され又はスレッド制御ブロックが待ち行列３
７０上にもはやなくなるまで、”ｄｏｆｏｒｅｖｅ
ｒ” ループに入る（ステップ５８６）。セマフォは、
ウエイターに通知すために調べる別のプロセスによって
除去され得ることに注意する。これは、待ち行列３７０
がスキャンされる場所のみである。セマフォシーケンス
番号４３０がループの初めで保存される（ステップ５８
８）。待ち行列３７０は、その後スキャンされて待ち行
列上のスレッド制御ブロックの位置を見つける（ステッ
プ５９０）。シーケンシャル番号４３０は待ち行列のス
キャンの間時間を変更する場合（ステップ５９２）、ル
ープ再開する（ステップ５８６）。スキャンされる要素
が回復の中のスレッド制御ブロックのための要素でない
場合（ステップ５９４）、待ち行列の終わり到達したか
を知るためにチェックされる（ステップ５９６）。待ち
行列の終りに到達した場合、スレッド制御ブロックは既
に除去され、更なる処理は要求されない（ステップ５９
９）。待ち行列がステップ５９６で終了していない場
合、ループに戻る（ステップ５９０）。ウエイター要素
はステップ５９４で見出される場合、図２２・２３に示
されるＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が実行さ
れ、待ち行列からその要素を除去する（ステップ５９
７）。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が失敗した
場合（ステップ５９８）、コードは再び試行するために
ループに戻る（ステップ５８６）。ＣＯＭＰＡＲＥＡ
ＮＤＳＷＡＰ操作が成功した場合、このスレッドは待
ちチェーン上にもはや存在せず、終了を続ける（ステッ
プ５９９）。

【００３７】図１０から図２３に示されるｃｏｍｐａｒ
ｅａｎｄｓｗａｐ操作の詳細に入る前に、本発明の好
ましい実施例によって用いられるＰｅｒｆｏｒｍＬｏ
ｃｋｅｄＯｐｅｒａｔｉｏｎ（ＰＬＯ）命令の一般的
な理解を与えることは、役に立つ。ＰＬＯ命令の使用
は、図４によって説明される。ほとんどのコンピュータ
・システムは、システム・ストレージへのアトミック更
新を実行可能にするハードウエア命令を含む。参照によ
って本明細書に組込まれるＩＢＭ刊行物ＳＡ２２−７２
０１−０２（１９９４）のＥｎｔｅｒｐｒｉｓｅＳｙ
ｓｔｅｍｓＡｒｃｈｉｔｅｃｔｕｒｅ／３９０Ｐｒｉ
ｎｃｉｐｌｅｓｏｆＯｐｅｒａｔｉｏｎに記述される
ように、ＩＢＭＳ／３９０ハードウエア・プラットフ
ォーム上の先の命令の幾つかは、ＣＯＭＰＡＲＥａｎ
ｄＳＷＡＰ（ＣＳ）、ＣＯＭＰＡＲＥＤｏｕｂｌｅ
ａｎｄＳＷＡＰ（ＣＤＳ）、ＴｅｓｔａｎｄＳｅｔ
（ＴＳ）である。ＰＬＯは、Ｓ／３９０ハードウエア
・プラットフォーム上の比較的新しいアトミック命令で
ある。上でリストされたアトミック命令は、ストレージ
のシングル・ワード又はダブルワードのアトミック更新
を許容するが、ＰＬＯ命令は、ストレージ中のバラバラ
（ｄｉｓｊｏｉｎｔ）の位置の複数フィールドのアトミ
ック更新を許容する。ＰＬＯ命令は、参照によって本明
細書に組込まれる次の出願中の特許と刊行物に記述され
ている。エス.ジェ.グリンスパンらの”Ｂｌｏｃｋｉｎ
ｇＳｙｍｂｏｌＣｏｎｔｒｏｌｉｎａＣｏｍｐｕ
ｔｅｒＳｙｓｔｅｍｔｏＳｅｒｉａｌｉｚｅＡｃｃ
ｅｓｓｉｎｇａＤａｔａＲｅｓｏｕｒｃｅｂｙＳ
ｔｉｍｕｌｔａｎｅｏｕｓＰｒｏｃｅｓｓｏｒＲｅｑ
ｕｅｓｔｓ”の１９９７年５月２８日に出願された米国
特許出願第０８／８６４，４０２号；エス. ジェ. グリ
ンスパンらの”ＰｒｏｃｅｓｓｏｒＡｓｓｏｃｉａｔ
ｅｄＢｌｏｃｋｉｎｇＳｙｍｂｏｌＣｏｎｔｒｏｌｓ
ｆｏｒＳｅｒｉａｌｉｚｉｎｇＡｃｃｅｓｓｉｎｇ
ｏｆＤａｔａＲｅｓｏｕｒｃｅｓｉｎＣｏｍｐｕ
ｔｅｒＳｙｓｔｅｍ”の１９９７年５月２８日に出願
された米国特許出願第０８／８６４，５８５号；エス.
ジェ. グリンスパンらの”ＭｅｔｈｏｄｏｆＥｘｅｃ
ｕｔｉｎｇＰｅｒｆｏｒｍＬｏｃｋｅｄＯｐｅｒａ
ｔｉｏｎＩｎｓｔｒｕｃｔｉｏｎｓｆｏｒＳｕｐｐ
ｏｒｔｉｎｇＲｅｃｏｖｅｒｙｏｆＤａｔａＣｏｎ
ｓｉｓｔｅｎｃｙＩｆＬｏｓｔＤｕｅｔｏＰｒｏ
ｃｅｓｓｏｒＦａｉｌｕｒｅ，ａｎｄａＭｅｈｔｏ
ｄｏｆＲｅｃｏｖｅｒｉｎｇｔｈｅＤａｔａＣｏ
ｎｓｉｓｔｅｎｃｙＡｆｔｅｒＰｒｏｃｅｓｓｏｒ
Ｆａｉｌｕｒｅ”の１９９７年９月５日に出願された米
国特許出願第０８／９２４，８９０号；ＩＢＭＢｏｏ
ｋＭａｎａｇｅｒＢｏｏｋＳｅｖｅｒ即ち、ｈｔｔ
ｐ：／／ｐｐｄｂｏｏｋｓ．ｐｏｋ．ｉｂｍ．ｃｏｍ／
ｃｇｉ−ｂｉｎ／ｂｏｏｋｍｇｒ．ｃｍｄ／ＢＯＯＫＳ
／ＤＺ９ＡＲ００４／７．５．６９を介する”ＥＳＡ／
３９０ＰｒｉｎｃｐｌｅｓｏｆＯｐｅｒａｔｉｏ
ｎ”７．５．７９である。

【００３８】本発明によって用いられるＰＬＯ命令によ
って与えられる操作は、１．Ｃｏｍｐａｒｅａｎｄｓ
ｗａｐは、追加のストアなしに２倍になる。これは、
ダブルワード（６４ｂｉｔ）・オペランドをダブルワー
ド比較値と比較し、そのオペランドが比較値と等しい場
合、その比較されたオペランドをダブルワード置換値で
置換える。

【００３９】セマフォが獲得又は解放されていて、待ち
行列３７０中にウエイターがない場合に、この操作は用
いられる（図１４・１５と図１６・１７）。セマフォ待
ち行列３７０に必要な更新がない場合、変更される唯一
のダブルワードは、セマフォ・フィールド４１５であ
る。１．Ｃｏｍｐａｒｅａｎｄｓｗａｐは、２倍になり、
２つの追加のダブルワードをストアする。これは、ダ
ブルワード（６４ｂｉｔ）・オペランドをダブルワード
比較値と比較し、そのオペランドが比較値と等しい場
合、その比較されたオペランドと２つの追加のダブルワ
ード・オペランドを、ダブルワード置換値で置換える。

【００４０】第１のウエイターが追加され又は待ち行列
から除去されている場合に、この操作は用いられる（図
１０・１１、図１８・１９、及び、図２０・２１）。３
つのダブルワード・フィールド即ちセマフォ・フィール
ド４１５、待ち行列ヘッダー４２０、及び待ち行列３７
０の終端（第１のウエイターが加えられている場合）又
は先頭（第１のウエイターが除去されている場合）に現
在存在するスレッドのスレッド制御ブロック７７０、が
変更される。１．Ｃｏｍｐａｒｅａｎｄｓｗａｐは、２倍になり、
３つの追加のダブルワードをストアする。これは、ダ
ブルワード（６４ｂｉｔ）・オペランドをダブルワード
比較値と比較し、そのオペランドが比較値と等しい場
合、その比較されたオペランドと３つの追加のダブルワ
ード・オペランドを、ダブルワード置換値で置換える。

【００４１】後続のウエイターが追加され又は待ち行列
３７０から除去されている場合に、この操作は用いられ
る（図１２・１３、及び、図２２・２３）。４つのダブ
ルワード・フィールド即ちセマフォ・フィールド４１
５、待ち行列ヘッダー４２０、追加され又は除去された
スレッドのスレッド制御ブロック・フィールド４７０と
７７０、及び、待ち行列３７０中のその直前の先行者が
変更される。

【００４２】ｃｏｍｐａｒｅａｎｄｓｗａｐ操作は、
フィールド４１５を背景として何時も実行される。ＣＯ
ＭＰＡＲＥＡＮＤＳＷＡＰ命令が成功する度に、フィ
ールド４１５内の古い値は、ＣＯＭＰＡＲＥＡＮＤＳ
ＷＡＰの起動ためにセットアップがスターした時からは
変化はないこを意味する。ＣＯＭＰＡＲＥＡＮＤＳＷ
ＡＰ操作が成功の場合、フィールド４１５は更新され
る。特に、シーケンス番号４３０を更新が異議がある。
シーケンス番号４３０は、いつも更新されるから、２つ
のＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が同じセマフォ
上で衝突する時はいつも、単に一つのＣＯＭＰＡＲＥ
ＡＮＤＳＷＡＰ操作のみが完結し、他方がループを戻
りセットアップを再び実行する。

【００４３】ＰＬＯ命令のｃｏｍｐａｒｅａｎｄｓｗ
ａｐ部分に関する第１のセマフォ・フィールド４１５を
更新することに加え、待ち行列フィールド４２０も変更
してその命令がセットアップされる。１つのウエイター
は、待ち行列から除去され、又第１のウエイターが追加
され時、待ち行列ヘッド４４０が更新される。１つのウ
エイターが待ち行列の最後に追加され、即ち第１ウエイ
ターが追加される毎に、テール・ポインター４４５が更
新される。スレッド制御ブロック４５０が追加又待ち行
列から除去され毎に、該ブロック４５０が待ち行列上に
存在していることを示すように、フラグ４６０を設定す
る。これらのフィールドの全ては、単一のＰＬＯＣＯ
ＭＰＡＲＥＡＮＤＳＷＡＰ命令によって変更される。

【００４４】図２４は、次の説明においてしばしば参照
されるセマフォと待ち行列のフィールド図を示す。比較
値としてセマフォ・フィールドの先の値を保存するため
に、セマフォ・フィールド４１５は古セマフォ１３１０
と呼ばれるエリアにコピーされる。古セマフォ１３１０
は、次に新セマフォ１３２０にコピーされ、新セマフォ
１３２０のフィールド内部は、セマフォ・フィールド４
１５のための置換値を生成する指定されたセマフォ操作
に従って更新される。待ち行列３７０がその操作によっ
て変更されている場合、待ち行列ヘッド４４０とテール
４４５のための置換値が１１３０とマークされたエリア
に構築されるが、スレッド制御ブロックのＮＥＸＴポ
インターとフラグ・フィールドのための置換値は１３４
０としてマーク付けされている。ＰＬＯ命令はその後に
実行された時に、セマフォ・フィールド４１５の現在値
を古セマフォ１３１０にストアされた比較値と比較す
る。値が一致する場合他のスレッドがセマフォを変更し
ていないことを示し、アトミックに比較ステップで以っ
てＰＬＯ命令は待ち行列４２０を置換値１３３０で、ス
レッド制御ブロックのＮＥＸＴポインターとフラグ・フ
ィールドを置換値１３４０で、実際のセマフォ４１５を
新セマフォ１３２０からの置換値で、更新する。

【００４５】セマフォが利用可能でなく（ｓｅｍｖａｌ
＝０４３５）、（ヘッド・ポインター４４０によって
指示されるように）待ち行列３７０が空の時のｓｅｍｏ
ｐ（−１）のための処理を、図１０は示す。我々をＣＯ
ＭＰＡＲＥＡＮＤＳＷＡＰのセットアップに導くテス
ト処理の初期で、セマフォ・フィールド４１５の現在値
が古セマフォ１３１０にストアされた。新ウエイターの
付加は、セマフォ値４３５とＰＩＤ４２５を変更しな
い。これらＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の全て
に関して、その操作はシーケンス番号４３０の値をイン
クリメントする。そのように、シーケンス番号が１大き
い場合を除き、新セマフォと呼ばれるエリア１３２０
は、古セマフォ１３１０と同じように生成される。待ち
行列３７０は現在空であるから、新スレッド制御ブロッ
ク４５０を（エントリ３７２として）待ち行列３７０に
付加することを我々が完了した時、ヘッド４４０とテー
ル４４５の両者がスレッド制御ブロック４５０を差すよ
うに設定される。そのようにこのケースにおいて、２つ
の追加のストアを有するＰＬＯｃｏｍｐａｒｅａｎｄ
ｓｗａｐｄｏｕｂｌｅは、が完了する。その追加のス
トアは、待ち行列ヘッダー４２０とスレッド制御ブロッ
ク・フィールド４７０を目的とする。他のウエイターが
存在しないため、単に待ちフラグ４６０が、フィールド
４７０内で変更される。

【００４６】図１１は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功している場合のセマフォ・フィールドの内
容を示す。そのセマフォ番号は、前より１大きい。待ち
行列ヘッダー４４０は、呼出しスレッドのスレッド制御
ブロック４５０を今差している。待ち行列テール４４５
は同じスレッド制御ブロックを差す。待ちフラグ４６０
は、スレッド制御ブロック４５０がセマフォ待ちチェー
ン上に存在することを示すように、設定される。ＣＯＭ
ＰＡＲＥＡＮＤＳＷＡＰ操作が失敗した場合、セマフ
ォ・フィールド４１５と４２０は影響されない。別のス
レッドが競争に勝ってセマフォ４１５を解放するか、又
は競争に勝って自分自身が待ち行列に加わる場合、ＣＯ
ＭＰＡＲＥＡＮＤＳＷＡＰ操作は失敗する。ＣＯＭＰ
ＡＲＥＡＮＤＳＷＡＰ操作が成功か否かのためのテス
トは、図５のステップ５２４である。

【００４７】図１２は、セマフォが利用可能でない場合
で（ｓｅｍｖａｌ＝０４３５）、待ち行列４４０が空
でない場合のｓｅｍｏｐ（−１）のための処理を示す。
ＣＯＭＰＡＲＥＡＮＤＳＷＡＰのセットアップに我々
を導くテスト処理の初期において、セマフォ・フィール
ド４１５の現在値が古セマフォ１３１０に保存された。
新ウエイターの追加はセマフォ値４３５又はＰＩＤ４２
５を変更しない。これらＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作の全てに関して、それは、シーケンス番号４３０
の値をインクリメントする。そのように、シーケンス番
号４３０が１大きい場合を除き、新セマフォと呼ばれる
エリア１３２０は、古セマフォ１３１０と同じように生
成される。待ち行列ヘッド４４０は現在スレッド制御ブ
ロック７５０を差し、そのテール４４５はスレッド制御
ブロック７５０を差す。

【００４８】我々が新スレッド制御ブロック４５０を待
ち行列４２０への追加を完了した時、ヘッド４４０はス
レッド制御ブロック７５０を差し続け、テール４４５は
スレッド制御ブロック４５０を差すように設定される。
我々は呼出しスレッドを待ち行列３７０の終りに加えて
いるから、スレッド制御ブロック７５０中のＮＥＸＴポ
インター７５５が更新されて、待ち行列に追加されるス
レッド制御ブロック４５０を差す。このケースーでは、
ＰＬＯｃｏｍｐａｒｅａｎｄｓｗａｐｄｏｕｂｌｅ
とｔｒｉｐｌｅストアは、セマフォ・フィールド４１
５、待ち行列ヘッダー４２０、及びスレッドコントロー
ル・フィールド７７０・４７０を目的とする。

【００４９】図１３は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功した時のセマフォ・フィールドの内容を示
す。シーケンス番号４３０は前より１大きい。待ち行列
ヘッダー４４０はまだスレッド制御ブロック７５０を差
す。待ち行列テール４４５は、新スレッド制御ブロック
４５０を差す。スレッド制御ブロック７５０内のＮＥＸ
Ｔポインター７５５は、現在スレッド制御ブロック４５
０を差し、スレッドが待ち行列上で待っていることを示
すようにスレッド制御ブロック４５０内の待ちフラグ４
６０が変更される。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操
作が失敗した場合、どのフィールドの変更されない。別
のスレッドが競争に勝ちセマフォを解放するか、又は競
争に勝って自分自身を待ち行列に加える場合に、ＣＯＭ
ＰＡＲＥＡＮＤＳＷＡＰ操作は失敗する。ＣＯＭＰＡ
ＲＥＡＮＤＳＷＡＰ操作が成功か否かのためのテスト
は、図５のステップ５２４である。

【００５０】図１４は、セマフォが利用可能な場合で
（ｓｅｍｖａｌ＝１４３５）、待ち行列４４０が空で
ない場合のｓｅｍｏｐ（−１）のための処理を示す。Ｃ
ＯＭＰＡＲＥＡＮＤＳＷＡＰのセットアップに我々を
導くテスト処理の初期において、セマフォ・フィールド
４１５の現在値が古セマフォ１３１０に保存された。新
セマフォ１３２０と呼ばれるエリアは生成されて、古セ
マフォ３１０のコピーにより初期化される。新セマフ１
３２０のコピーにおいて、ＰＩＤは呼出し元のプロセス
ＩＤにセットされ、シーケンス番号が１だけインクリメ
ントされ、セマフォ値が１からゼロに変更される。待ち
行列４２０はこの操作によって影響を受けないから、こ
れらフィールドは変更されない。実行されたＣＯＭＰＡ
ＲＥＡＮＤＳＷＡＰ操作は、追加のストアを有さない
簡単なｃｏｍｐａｒｅｄｏｕｂｌｅａｎｄｓｗａｐで
ある。

【００５１】図１５は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功した時のセマフォ・フィールドの内容を示
す。シーケンス番号４３０は、前より１大きい。ＰＩＤ
フィールド４２５は、呼出し元のプロセスＩＤを有す
る。セマフォ値４３５は現在０であり、セマフォが保持
されていることを示す。待ち行列４２０は、変更はな
い。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が失敗の場
合、どのフィールドも変更ない。ＣＯＭＰＡＲＥＡＮ
ＤＳＷＡＰ操作の失敗に対する可能性のある理由は、
別のスレッドが競争に勝ってセマフォを獲得したからで
ある。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が成功した
か否かのためのテストは、図６のステップ５４２であ
る。

【００５２】図１６は、先に獲得したセマフォを解放す
る呼出し元であるｓｅｍｏｐ（−１）のための処理を示
す。このケースでは、セマフォを求めるウエイターが存
在する。我々をＣＯＭＰＡＲＥＡＮＤＳＷＡＰのセッ
トアップに導くテスト処理の初期において、セマフォ・
フィールド４１５の現在値が古セマフォ１３１０に保存
されている。新セマフォ１３２０と呼ばれるエリアが生
成され、古セマフォ１３１０で初期化される。新セマフ
ォ１３２０コピーにおいて、ＰＩＤは、呼出し元のプロ
セスＩＤに対して設定され、シーケンス番号が１だけイ
ンクリメントされ、セマフォ値はゼロから１に変更され
る。ウエイターが存在しないから、待ち行列４２０は変
更されない。実行されたＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作は、追加のストアを有さない単純なｃｏｍｐａｒ
ｅｄｏｕｂｌｅａｎｄｓｗａｐである。

【００５３】図１７は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功した時のセマフォ・フィールドの内容を示
す。シーケンス番号４３０は、前より１大きい。ＰＩＤ
フィールド４２５は、呼出し元のプロセスＩＤを有す
る。セマフォ値４３５は現在０であり、セマフォが利用
可能であることを示す。待ち行列４２０は、空である。
ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が失敗の場合、ど
のフィールドも変更されない。ＣＯＭＰＡＲＥＡＮＤ
ＳＷＡＰ操作の失敗に対する主な理由は、別のスレッド
が自分自身を待ち行列に追加する最中であるからであ
る。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰを失敗させること
によって、それは、任意のウエイターに通知することな
しに、このプロセスがセマフォを解放することを阻止す
る。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が成功である
か否かのためのテストが図７のステップ５６０である。

【００５４】図１８は、先に獲得したセマフォを解放す
る呼出し元であるｓｅｍｏｐ（−１）のための処理を示
す。このケースでは、セマフォを求めるウエイターが存
在する。我々をＣＯＭＰＡＲＥＡＮＤＳＷＡＰのセッ
トアップに導くテスト処理の初期において、セマフォ・
フィールド４１５の現在値が古セマフォ１３１０に保存
されいてる。新セマフォ１３２０と呼ばれるエリアが生
成され、古セマフォ１３１０で初期化される。新セマフ
ォ１３２０コピーにおいて、ＰＩＤは、呼出し元のプロ
セスＩＤに対して設定され、シーケンス番号が１だけイ
ンクリメントされ、セマフォ値はゼロから１に変更され
る。待ち行列４２０は、第１のウエイター７５０を除去
するために変更される。唯一１つのウエイターが存在す
る場合、ヘッド４４０は変更されて７５０の第１の要素
のＮＥＸＴポインター７５５と同じ値を含み、テール４
４５は変化のない状態である。スレッド制御ブロック７
５０はもはやセマフォ待ち行列上にないことを指示する
ように、ＮＥＸＴポインター７５５とフラグ７６０は消
去される。実行されたＣＯＭＰＡＲＥＡＮＤＳＷＡＰ
操作は、第１のウエイターの待ち行列ヘッダー４２０と
スレッド制御ブロック・フィールド７７０に追加される
２つのストアを有するｃｏｍｐａｒｅｄｏｕｂｌｅａ
ｎｄｓｗａｐである。

【００５５】図１９は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功した時のセマフォ・フィールドの内容を示
す。シーケンス番号４３０は、前より１大きい。ＰＩＤ
フィールド４２５は、呼出し元のプロセスＩＤを有す
る。セマフォ値４３５は現在１であり、セマフォが利用
可能であることを示す。待ち行列ヘッダーは、今スレッ
ド制御ブロック４５０を差す。ＮＥＸＴポインター７５
５とフラグ７６０は、消去されている。ＣＯＭＰＡＲＥ
ＡＮＤＳＷＡＰ操作が失敗の場合、どのフィールドも
変更されない。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の
失敗に対する主な理由は、別のスレッドが自分自身を待
ち行列に追加する最中であるからである。ＣＯＭＰＡＲ
ＥＡＮＤＳＷＡＰを失敗させることによって、それ
は、このプロセスが待ち行列を無効な状態に置くのを阻
止する。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が成功で
あるか否かのためのテストが図７のステップ５６０であ
る。

【００５６】図２０は、待ち行列中の先頭のスレッドを
除去するための処理を示す。セマフォの解放が先頭待ち
スレッドを除去するが、その待ち行列スレッドを起こす
ための通知において失敗した時に、これはステップ５８
０（図８）で起こる。このケースにおいて、次期ウエイ
ターに停止（ｈａｎｇ）条件を回避するために、通知さ
れなければならない。我々をＣＯＭＰＡＲＥＡＮＤ
ＳＷＡＰのセットアップに導くテスト処理の初期におい
て、セマフォ・フィールド４１５の現在値は古セマフォ
１３１０に保存されいてる。新セマフォ１３２０と呼ば
れるエリアが生成され、古セマフォ１３１０で初期化さ
れる。新セマフォ１３２０のコピーにおいて、ＰＩＤと
セマフォ値は変更されない。シーケンス番号は、１だけ
インクリメントされる。待ち行列４２０は、第１のウエ
イター７５０を除去するために変更される。唯一１つの
ウエイターが存在する場合、ヘッド４４０とテール４４
５の両者は、ゼロに設定される。複数のウエイターが存
在する場合、ヘッド４４０は、第１の要素のＮＥＸＴポ
インターと同じ値を含むように変更され、テール４４５
は変化無しのままである。スレッド制御ブロック７５０
はもはやセマフォ待ち行列上にないことを示すように、
ＮＥＸＴポインター７５５とフラグ７６０は消去され
る。実行されたＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作
は、２つの追加のストアを待ち行列ヘッダー４２０及び
第１ウエイターのスレッド制御ブロック・フィールド７
７０に有するｃｏｍｐａｒｅｄｏｕｂｌｅａｎｄｓ
ｗａｐである。

【００５７】図２１は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功した時のセマフォ・フィールドの内容を示
す。シーケンス番号４３０は、前より１大きい。ＰＩＤ
フィールド４２５とセマフォ値４３５は変化しない。待
ち行列ヘッダー４４０は今スレッド制御ブロック４５０
を差し、テール・ポインター４４５は変更はない。最後
のスレッド制御ブロックが待ち行列から除去される場
合、ヘッド４４０はゼロであり、テール４４５もゼロで
ある。除去されるスレッド制御ブロック７５０におい
て、ＮＥＸＴポインター７７５と待ちフラグ７６０は消
去される。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が失敗
の場合、どのフィールドも変更されない。ＣＯＭＰＡＲ
ＥＡＮＤＳＷＡＰ操作の失敗に対する主な理由は、別
のスレッドが自分自身を待ち行列に追加する最中である
からである。ＣＯＭＰＡＲＥＡＮＤＳＷＡＰを失敗さ
せることによって、それは、このプロセスが待ち行列を
無効な状態に置くのを阻止する。ＣＯＭＰＡＲＥＡＮ
ＤＳＷＡＰ操作が成功であるか否かのためのテストが
図８のステップ５７４である。

【００５８】図２２は、スレッドが回復に入った時に、
ステップ５９７（図９）でセマフォを待つスレッドを除
去するための処理を示す。セマフォ・フィールド４１５
の現在値は、古セマフォ１３１０に保存される。新セマ
フォ１３２０と呼ばれるエリアが生成され、古セマフォ
１３１０のコピーで初期化される。新セマフォ１３２０
のコピーにおいて、ＰＩＤは変更されないままである。
なぜなら、呼出しがセマフォ４３５を変更した時に、Ｐ
ＩＤは唯一変更されるからである。シーケンス番号４３
０は、前より１大きい。図９からのフローにおいて、除
去されるべきスレッド制御ブロック４５０は待ち行列上
に位置し、そしてスレッド制御ブロック７５０は現在Ｎ
ＥＸＴ７５５のフィールドを用いて、スレッド制御ブロ
ック４５０を差している。ＣＯＭＰＡＲＥＡＮＤＳＷ
ＡＰ操作は、要素４５０を待ち行列４２０（３７０）。

【００５９】この例では、ヘッド４４０は変化しないま
まであが、テール４４５は要素７５０を差すように変更
される。なぜなら要素４５０は現在待ち行列の最後に在
り、それを除去することがテール４４５のポインターを
変更するからである。ＮＥＸＴポインター７５５は、ス
レッド制御ブロック４５０のＮＥＸＴポインター４５５
に在るものは何でも差すように変更される。このケース
において、ＮＥＸＴ４５５中の値はゼロである。ＮＥＸ
Ｔポインター４５５とフラグ４６０は消去される。実行
されたＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作は、３つの
追加のストアを待ち行列フィールド４２０、スレッド制
御ブロック・フィールド７７０、及びスレッド制御ブロ
ック・フィールド４７０の中に有するｃｏｍｐａｒｅ
ｄｏｕｂｌｅａｎｄｓｗａｐである。

【００６０】問題のスレッドが待ち行列３７０中の最初
又は最後のウエイターのどちらでもない場合、唯一セマ
フォ・フィールド４１５及びスレッド制御ブロック・フ
ィールド７７０・４７０が変更される。即ち待ち行列ポ
インター・フィールド４２０は、同じのままである。３
つの追加のストアを有するｃｏｍｐａｒｅｄｏｕｂｌ
ｅａｎｄｓｗａｐはこのシナリオのために用いられる
場合、待ち行列ポインター・フィールド４２０は、そ
の過去の内容で以って簡単に更新される。

【００６１】図２３は、ＣＯＭＰＡＲＥＡＮＤＳＷＡ
Ｐ操作が成功した時のセマフォ・フィールドの内容を示
す。シーケンス番号４３０は、前より１大きい。ＰＩＤ
フィールド４２５とセマフォ値４３５は変化しない。待
ち行列ヘッダー４４０は未だスレッド制御ブロック７５
０を差し、テール・ポインター４４５は今スレッド制御
ブロック７５０を差す。最後のスレッド制御ブロックが
待ち行列から除去される場合、ヘッド４４０はゼロであ
り、テール４４５もゼロである。ＮＥＸＴポインター７
７５は、今ゼロである。ＮＥＸＴポインター４５５と待
ち行列フラグ４６０は、スレッド制御ブロック４５０
は、もはや待ち行列上に存在しないように消去される。
ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が失敗した場合、
どのフィールドも変更されない。ＣＯＭＰＡＲＥＡＮ
ＤＳＷＡＰを失敗させることによって、それは、この
プロセスが待ち行列を無効な状態に置くのを阻止する。
ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作が成功であるか否
かのためのテストが図９のステップ５９０である。

【００６２】本発明は、典型的には、ハードウエア機械
上で実行されるソフトウエア（即ちプログラム記憶装置
上で認識可能に具体化された命令の機械可読プログラ
ム）として実装される。特定の具体例が示され、説明さ
れる一方、本発明の本質から逸脱しない種々の変更は可
能であることは、この技術分野の当業者にとっては自明
なことであろう。従って、本発明を、ＩＢＭＳ／３９
０ハードウエア・プラットフォーム上のＰＬＯ（Ｐｅ
ｒｆｏｒｍＬｏｃｋｅｄＯｐｅｒａｔｉｏｎ）を用い
て説明してきたが、本発明はこのプラットフォーム上の
この命令に限定されるものではなく、他の環境において
使用してもよい。更に本発明を２進セマフォを実装する
ように、説明してきたが、本発明は２進セマフォに限定
されるものでではなく、セマフォを考慮する適当な変更
で以って使用されてもよい。

【図面の簡単な説明】

【図１】多数のセマフォ・セットを管理するカーネルの
ためのインフラストラクチャーを示す。

【図２】同じセマフォを要求する２つのプロセスの間の
インターラクションを示す。

【図３】従来のセマフォ処理のロジック・フローを示
す。

【図４】１のセマフォ・セットの個々のセマフォと、実
行可能な作業単位を示すスレッド制御（コントロール）
ブロックとの構造を示す。

【図５】本発明に従うセマフォ処理のロジック・フロー
を示す。これは、ｓｅｍｏｐ関数（ｆｕｎｃｔｉｏｎ）
とｓｅｍｏｐが得られない時のための処理のエントリを
示す。

【図６】セマフォが得られ要求がセマフォを獲得するケ
ースのためのセマフォ処理のロジックを続行する。

【図７】セマフォを解放するためのセマフォ処理のロジ
ックを示す。２つのケースは、セマフォを待つウエイタ
ーの存在する、存在しない場合である。仮に、ウエイタ
ーが存在するなら、ウエイターは待ち行列から除去され
る。

【図８】セマフォを解放するためのセマフォ処理のロジ
ックを示す。このケースは、ウエイターに通知される場
合である。仮に、ポストが失敗であるのなら、次のウエ
イターが待ち行列から除去され通知される。ウエイター
がうまく通知されるまで、即ち亜待ち行列が空になるま
で、これを続行する。

【図９】待ち行列からスレッドコントロール・ブロック
を除去する回復処理を扱う。

【図１０】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前の
セマフォが利用可能でなく待ち行列が空でない場合のセ
マフォの要求を示す。

【図１１】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の成功
の後、セマフォが利用可能でなく、待ち行列が空である
時のセマフォの要求を示す。

【図１２】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前、
セマフォが利用可能でなく、待ち行列が空でない時のセ
マフォの要求を示す。

【図１３】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の後、
セマフォが利用可能でなく、待ち行列が空でない時のセ
マフォの要求を示す。

【図１４】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前、
セマフォが利用可能で、待ち行列が空である時のセマフ
ォの要求を示す。

【図１５】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の後、
セマフォが利用可能で、待ち行列が空である時のセマフ
ォの要求を示す。

【図１６】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前、
待ち行列上にウエイターが存在しない場合のセマフォの
解放を示す。

【図１７】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の後、
待ち行列上にウエイターが存在しない場合のセマフォの
解放を示す。

【図１８】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前、
待ち行列上にウエイターが存在しない場合のセマフォの
解放を示す。

【図１９】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の後、
待ち行列上にウエイターが存在する場合のセマフォの解
放を示す。

【図２０】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前、
セマフォが既に解放された後に、待ち行列からウエイタ
ーを除去する処理を示す。

【図２１】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の後、
セマフォが既に解放された後に、待ち行列からウエイタ
ーを除去する処理を示す。

【図２２】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の前、
スレッドが終了しているから、待ち行列からスレッド制
御ブロックを除去する回復処理を示す。

【図２３】ＣＯＭＰＡＲＥＡＮＤＳＷＡＰ操作の後、
スレッドが終了しているから、待ち行列からスレッド制
御ブロックを除去する回復処理を示す。

【図２４】ｃｏｍｐａｒｅａｎｄｓｗａｐ操作を実行
する際に用いられるセマフォと内部データ構造である。１０５：セマフォＩＤテーブル１１５：セマフォ・セット１１０：エントリ１２０：セマフォ・エントリ２０５：プロセス１２１０：プロセス２２１５：カーネル３６０：ロック待ち行列３７０：セマフォ待ち行列４１５：セマフォ・フィールド４２０：待ち行列ヘッダー４２５：プロセスＩＤ４３０：シーケンス番号４３５：セマフォ値４４０：ヘッド・ポインター４４５：テール・ポインター４５０：スレッド制御ブロック４５５：ＮＥＸＴポインター４６０：フラグ・セット４７０：スレッド制御フィールド１３１０：古セマフォ１３２０：新セマフォ１３３０：置換値１３４０：置換値

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジョーン・エム・フォースザアメリカ合衆国ニューヨーク州シュガーティス、ローレン・ティース・ロード104

Claims

【特許請求の範囲】

【請求項１】共有資源へのアクセスを直列化するために
セマフォを使用する情報処理システムにおいて、セマフ
ォ上で指定された操作を実行することの要求元からの要
求を処理する方法であって、該セマフォは１つの値を含
む第１セマフォ・フィールドとセマフォ待ち行列へのポ
インターを含む第２セマフォ・フィールドとを有し、該
待ち行列は前記セマフォのウエイターに対応してゼロ又
はそれ以上のエントリを有し、各々エントリは次のエン
トリへのポインターを有する方法であって、比較値として第１セマフォ・フィールドの先の値を蓄え
るステップと、前記指定された操作に従って、第１オペランドとして第
１セマフォ・フィールドのための第１置換値を生成し、
前記待ち行列が前記操作により変更されつつある場合第
２オペランドとして第２セマフォ・フィールドのための
第２置換値と第３オペランドとして前記待ち行列エント
リの１つのための第３置換値とを生成するステップと、その後自動的に第１セマフォ・フィールドの現在値を前
記比較値と比較し、前記現在値が前記比較値と一致する
場合第１オペランドを第１置換値で置換し、前記待ち行
列が前記操作により変更されつつある場合第２及び第３
オペランドの一方又両方を対応する前記置換値で置換す
る、比較するステップとを含む方法。
【請求項２】前記セマフォ・フィールドは、前記セマフ
ォを更新した最後の要求のＩＤを含む請求項１に記載の
方法。
【請求項３】前記セマフォ・フィールドは、シーケンス
番号を含む請求項１に記載の方法。
【請求項４】前記比較するステップは、前記第１セマフ
ォ・フィールドの現在値のシーケンス番号を前記比較値
のシーケンス番号と比較することを含む請求項４に記載
の方法。
【請求項５】前記生成ステップは、第１セマフォ・フィールドの前記先の値の中に含まれる
シーケンス番号をインクリメントして、インクリメント
されたシーケンス番号を生成する、インクリメント・ス
テップと、前記インクリメントされたシーケンス番号を含む第１置
換値を生成するステップとを含むことを特徴とする請求
項３に記載の方法。
【請求項６】前記セマフォは、２つのセマフォ値の１つ
を有する２進セマフォである請求項１に記載の方法。
【請求項７】前記指定された操作は、前記セマフォ値を
デクリメントすることを含む請求項１に記載の方法。
【請求項８】前記指定された操作は、前記セマフォ値を
インクリメントすることを含む請求項１に記載の方法。
【請求項９】第２セマフォ・フィールドは、前記セマフ
ォを待つ最初のウエイターへのポインターを含むことを
特徴とする請求項１に記載の方法。
【請求項１０】第２セマフォ・フィールドは、前記セマ
フォを待つ最後のウエイターへのポインターを含むこと
を特徴とする請求項１に記載の方法。
【請求項１１】前記要求は、前記セマフォを獲得するた
めの要求であって、前記置換値を生成するステップは、前記セマフォ値を検査して前記セマフォが利用可能であ
るかを決定するステップと、前記セマフォが利用可能でることを前記セマフォ値が示
す場合、前記セマフォ値をデクリメントして第１置換値
を生成するステップと、前記セマフォが利用可能でないことを前記セマフォ値が
示す場合、前記セマフォを待つウエイターが存在するか
どうかを決定するステップと、前記セマフォを待つウエイターが存在しない場合、前記
待ち行列ポインターを変更して、新しい最初のウエイタ
ーとしての前記要求元を差して第２置換値を生成するス
テップと、前記セマフォを待つ１以上のウエイターが存在する場
合、現在の最後のウエイターの待ち行列エントリを変更
して、新しい最後のウエイターとしての前記要求元を差
して第３置換値を生成するステップとを含むことを特徴
とする請求項１に記載の方法。
【請求項１２】前記要求は、前記セマフォを保持してい
る要求元から該セマフォを解放するための要求であっ
て、前記置換値を生成するステップは、前記セマフォ値をインクリメントとして第１置換値を生
成するステップと、前記セマフォを求める第１及び第２ウエイターが存在す
るかを決定するステップと、前記セマフォを待つ第１及び第２ウエイターが存在する
場合、前記待ち行列ポインターを変更して、新しい最初
のウエイターとしての前記要求元を差して第２置換値を
生成し、かつ、前記第１ウエイターに対応する前記待ち
行列エントリを変更し前記待ち行列から第１ウエイター
を除去して第３置換値を生成するステップと、前記セマフォを求める第１ウエイターのみが存在する場
合、前記待ち行列ポインターを変更して、ウエイターが
不在であることを示すように第２置換値を生成し、か
つ、第１ウエイターに対応する前記待ち行列エントリを
変更して、前記待ち行列から第１ウエイターを除去して
第３置換値を生成するステップとを含むことを特徴とす
る請求項１に記載の方法。
【請求項１３】前記第１セマフォ・フィールドの現在値
が前記比較値と一致しない場合、新しい比較値として、
前記第１セマフォ・フィールドの現実値を蓄え、前記生
成、比較、置換えステップを繰返す、ステップを更に含
む請求項１に記載の方法。
【請求項１４】前記比較ステップ及び置換えステップ
は、単一のハードウエア命令により実行され、前記命令
はオペランドを比較値で比較し、前記オペランドが前記
比較値に等しい場合、前記比較されたオペランド及び任
意の追加のオペランドを置換値で置換えることを特徴と
する請求項１に記載の方法。
【請求項１５】待ち行列エントリの各々は、対応する要
求元のための制御ブロックを含む請求項１に記載の方
法。
【請求項１６】制御ブロックの各々は、前記待ち行列内
の次のエントリへのポインターを含む請求項１６に記載
の方法。
【請求項１７】各制御ブロックは、前記要求元が前記待
ち行列上で待っているかを示すフラグを含む請求項１６
に記載の方法。
【請求項１８】前記生成ステップは、更に１つの待ち行
列エントリのための置換値を生成するステップを含み、
前記置換ステップは、前記待ち行列エントリの対を対応
する置換値で置換えるステップを含むことを特徴とする
請求項１に記載の方法。
【請求項１９】共有資源へのアクセスを直列化するため
にセマフォを使用する情報処理システムにおいて、セマ
フォ上で指定された操作を実行することの要求元からの
要求を処理する装置であって、該セマフォは１つの値を
含む第１セマフォ・フィールドとセマフォ待ち行列への
ポインターを含む第２セマフォ・フィールドとを有し、
該待ち行列は前記セマフォのウエイターに対応してゼロ
又はそれ以上のエントリを有し、各々エントリは次のエ
ントリへのポインターを有する装置であって、比較値として第１セマフォ・フィールドの先の値を蓄え
る手段と、前記指定された操作に従って、第１オペランドとして第
１セマフォ・フィールドのための第１置換値を生成し、
前記待ち行列が前記操作により変更されつつある場合第
２オペランドとして第２セマフォ・フィールドのための
第２置換値と第３オペランドとして前記待ち行列エント
リの１つのための第３置換値とを生成する手段と、その後自動的に第１セマフォ・フィールドの現在値を前
記比較値と比較し、前記現在値が前記比較値と一致する
場合第１オペランドを第１置換値で置換し、前記待ち行
列が前記操作により変更されつつある場合第２及び第３
オペランドの一方又両方を対応する前記置換値で置換す
る手段とを含む装置。
【請求項２０】共有資源へのアクセスを直列化するため
にセマフォを使用する情報処理システムにおいて、セマ
フォ上で指定された操作を実行することの要求元からの
要求を処理するための方法ステップを実行する該マシー
ンによって実行可能な命令のプログラムを明確に具体化
する、機械により読取り可能なプログラム記憶装置であ
って、該セマフォは１つの値を含む第１セマフォ・フィ
ールドとセマフォ待ち行列へのポインターを含む第２セ
マフォ・フィールドとを有し、該待ち行列は前記セマフ
ォのウエイターに対応してゼロ又はそれ以上のエントリ
を有し、各々エントリは次のエントリへのポインターを
有するプログラムの方法ステップは、比較値として第１セマフォ・フィールドの先の値を蓄え
るステップと、前記指定された操作に従って、第１オペランドとして第
１セマフォ・フィールドのための第１置換値を生成し、
前記待ち行列が前記操作により変更されつつある場合第
２オペランドとして第２セマフォ・フィールドのための
第２置換値と第３オペランドとして前記待ち行列エント
リの１つのための第３置換値とを生成するステップと、その後自動的に第１セマフォ・フィールドの現在値を前
記比較値と比較し、前記現在値が前記比較値と一致する
場合第１オペランドを第１置換値で置換し、前記待ち行
列が前記操作により変更されつつある場合第２及び第３
オペランドの一方又両方を対応する前記置換値で置換す
る、比較するステップとを含むことを特徴とする機械に
より読取り可能なプログラム記憶装置。