JPH02129726A - 相互排他を効率的に行う方法 - Google Patents
相互排他を効率的に行う方法Info
- Publication number
- JPH02129726A JPH02129726A JP1184882A JP18488289A JPH02129726A JP H02129726 A JPH02129726 A JP H02129726A JP 1184882 A JP1184882 A JP 1184882A JP 18488289 A JP18488289 A JP 18488289A JP H02129726 A JPH02129726 A JP H02129726A
- Authority
- JP
- Japan
- Prior art keywords
- count
- production process
- consumption
- wait
- block
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F9/526—Mutual exclusion algorithms
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Multi Processors (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
Ａ、産業上の利用分野
本発明はデータ処理分野に係るもので、特に高度なセマ
フォによるマルチ・プロセスの相互排他制御システムに
関する。ここではこの高度なセマフォを“フルフｌｒ
” （ｆｕｌｌｐｈｏｒｅ）と呼び、多重コンピュー
タシステムにおける複数タスク間の相互排除の効率化を
図ったものである。
フォによるマルチ・プロセスの相互排他制御システムに
関する。ここではこの高度なセマフォを“フルフｌｒ
” （ｆｕｌｌｐｈｏｒｅ）と呼び、多重コンピュー
タシステムにおける複数タスク間の相互排除の効率化を
図ったものである。
Ｂ、従来技術及びその問題点
一般的な多重コンピュータシステムは複数タスクを並行
処理する能力を有している。しかし、このようなシステ
ムにおいては不要な結果や競合状態を避けるためこれら
の並行プロセスを同期させる機構が必要となる。従来、
この同期を行うためにセマフォが使用されてきた。当業
者には周知であるように従来のセマフォはカウント、リ
ミット。
処理する能力を有している。しかし、このようなシステ
ムにおいては不要な結果や競合状態を避けるためこれら
の並行プロセスを同期させる機構が必要となる。従来、
この同期を行うためにセマフォが使用されてきた。当業
者には周知であるように従来のセマフォはカウント、リ
ミット。
そしてタスクの待ち行列から構成されていた１通常処理
のため２つのセマフォ命令が必要とされていた （ｊ
Ｖ Ｉｔタイプのセマフォ命令は消費（ｃｏｎｓｕｍｅ
ｒ）プロセスに用いるための情報の生産時に生産（ｐｒ
ｏｄｕｃｅｒ）プロセスによって使用される。Ｐ”タイ
プのセマフォ命令は生産（ｐｒｏｄｕｃｅｒ）プロセス
によって生成された情報の要求があったときに消費（ｃ
ｏｎｓｕｍｅｒ）プロセスによって使用される。ｔｔ
Ｐ”処理は相互排除に入りこむときに使用され、ＩＩＶ
″′処理は相互排除から出るときに使用される。従来の
セマフォについては“５ｔｒｕｃｔｕｒｅｄ Ｃｏｍｐ
ｕｔｅｒ Ｏｒｇａｎｉｚａｔｉｏｎ”セクション５．
３３に詳細に述べられている。米国特許筒４，３２０，
４５１号にも同様の記載がある。
のため２つのセマフォ命令が必要とされていた （ｊ
Ｖ Ｉｔタイプのセマフォ命令は消費（ｃｏｎｓｕｍｅ
ｒ）プロセスに用いるための情報の生産時に生産（ｐｒ
ｏｄｕｃｅｒ）プロセスによって使用される。Ｐ”タイ
プのセマフォ命令は生産（ｐｒｏｄｕｃｅｒ）プロセス
によって生成された情報の要求があったときに消費（ｃ
ｏｎｓｕｍｅｒ）プロセスによって使用される。ｔｔ
Ｐ”処理は相互排除に入りこむときに使用され、ＩＩＶ
″′処理は相互排除から出るときに使用される。従来の
セマフォについては“５ｔｒｕｃｔｕｒｅｄ Ｃｏｍｐ
ｕｔｅｒ Ｏｒｇａｎｉｚａｔｉｏｎ”セクション５．
３３に詳細に述べられている。米国特許筒４，３２０，
４５１号にも同様の記載がある。
セマフォ処理はこれに類するたとえ話を使用して説明す
ると理解しやすい。
ると理解しやすい。
あるハロウィンの夕暮れのこと、家の主であるバリーは
キャンデイ皿に３つのキャンデイを入れました。キャン
デイ皿は３つのキャンデイでちょうど満杯です。バリー
は一晩中、子供達（ハロウィンの夜、各家をまわってキ
ャンデイを集めてまわる。）に悩まされたくなかったの
でキャンデイ皿をポーチに置くとともにそのわきに次の
ように書きました。′このキャンデイ皿から１つキャン
デイを、おとりなさい。キャンデイが全て無くなったら
、皿にキャンデイが追加されるまで、あなたはポーチに
すわって待っていてかまいません”最初、３つのキャン
デイは全て消費（カウント＝３）され得る状態で、かつ
キャンデイ皿（リミット＝３）にストアされている。ど
の子供（プロセス）もキャンデイ皿からキャンデイをと
ることが出来る（消費プロセス）、これは他の子供の動
きには無関係（多重システム）である。バリーは新たに
キャンデイを追加すること（生産プロセス）ができる。
キャンデイ皿に３つのキャンデイを入れました。キャン
デイ皿は３つのキャンデイでちょうど満杯です。バリー
は一晩中、子供達（ハロウィンの夜、各家をまわってキ
ャンデイを集めてまわる。）に悩まされたくなかったの
でキャンデイ皿をポーチに置くとともにそのわきに次の
ように書きました。′このキャンデイ皿から１つキャン
デイを、おとりなさい。キャンデイが全て無くなったら
、皿にキャンデイが追加されるまで、あなたはポーチに
すわって待っていてかまいません”最初、３つのキャン
デイは全て消費（カウント＝３）され得る状態で、かつ
キャンデイ皿（リミット＝３）にストアされている。ど
の子供（プロセス）もキャンデイ皿からキャンデイをと
ることが出来る（消費プロセス）、これは他の子供の動
きには無関係（多重システム）である。バリーは新たに
キャンデイを追加すること（生産プロセス）ができる。
最初の子供がキャンデイ１つをキャンデイ皿から取りま
した（消費プロセス）、今、キャンデイの残りは２つ（
カウント＝２）です。さらに、２人の子供がキャンデイ
を１つづつ皿から取りました。今、キャンデイの残りは
ありません（カウント＝０）。もし、４番目の子供がキ
ャンデイを欲しがっても、彼はバリーがキャンデイ皿に
新たにキャンデイを追加する（カウントを１へ増加）ま
でキャンデイを手に入れることはできません（力ラント
＝０）、もし、この４番目の子供が待つことができるな
ら、彼はポーチにすわってバリーがキャンデイ皿を満杯
にしてくれるのを待ちます（１人の子供が１つのキャン
デイを待っていることを示すカウント＝−１）。バリー
がキャンデイ皿に新たにキャンデイを追加すれば、待っ
ている子供はそれをとります（カウントは０に増加）。
した（消費プロセス）、今、キャンデイの残りは２つ（
カウント＝２）です。さらに、２人の子供がキャンデイ
を１つづつ皿から取りました。今、キャンデイの残りは
ありません（カウント＝０）。もし、４番目の子供がキ
ャンデイを欲しがっても、彼はバリーがキャンデイ皿に
新たにキャンデイを追加する（カウントを１へ増加）ま
でキャンデイを手に入れることはできません（力ラント
＝０）、もし、この４番目の子供が待つことができるな
ら、彼はポーチにすわってバリーがキャンデイ皿を満杯
にしてくれるのを待ちます（１人の子供が１つのキャン
デイを待っていることを示すカウント＝−１）。バリー
がキャンデイ皿に新たにキャンデイを追加すれば、待っ
ている子供はそれをとります（カウントは０に増加）。
もし、この４番目の子供が待つことができなかったら、
彼はがっかりして隣の家へ移動します（消費要求失敗）
。
彼はがっかりして隣の家へ移動します（消費要求失敗）
。
バリーはキャンデイ皿をポーチへ出しておけば、静かな
平和なハロウィンの夜を過ごせると考えたのですが、結
局、彼は数分ごとにキャンデイ皿にキャンデイを追加す
るためにポーチへ駆は出さなければならないことに気が
ついたのです。そこでバリーはキャンデイ皿の隣にさら
に余分のキャンデイを、待つ子供のために置いておけば
、もっと効率的であると考えました（１つのキャンデイ
が１人の子供を待っていることを示すカウント＝４）。
平和なハロウィンの夜を過ごせると考えたのですが、結
局、彼は数分ごとにキャンデイ皿にキャンデイを追加す
るためにポーチへ駆は出さなければならないことに気が
ついたのです。そこでバリーはキャンデイ皿の隣にさら
に余分のキャンデイを、待つ子供のために置いておけば
、もっと効率的であると考えました（１つのキャンデイ
が１人の子供を待っていることを示すカウント＝４）。
バリーはハロウィン協会からそれは規則が許さないから
出来ないと言われました。
出来ないと言われました。
この話は従来のセマフォ構造の問題の１つを提示してい
ます。なぜなら、ＩＩＶ”タイプのセマフォ命令はカウ
ントがリミットと一致すると失敗（フェイル）するから
です。すなわち、″生産″プロセスはカウントがリミッ
トと一致すると１′消費″プロセスを待つことは出来ま
せん。この失敗（フェイル）は、消費プロセスが生産プ
ロセスを待つことを許可する゛′Ｐ″タイプ命令とは非
対称的です。このＰ及びＶ命令の非対称的性格は通常の
多重処理環境において、両者とも必要とされるものです
。この要求がセマフォと多重処理システムプロセッサ間
の処理インタフェースを複雑にしているのです。
ます。なぜなら、ＩＩＶ”タイプのセマフォ命令はカウ
ントがリミットと一致すると失敗（フェイル）するから
です。すなわち、″生産″プロセスはカウントがリミッ
トと一致すると１′消費″プロセスを待つことは出来ま
せん。この失敗（フェイル）は、消費プロセスが生産プ
ロセスを待つことを許可する゛′Ｐ″タイプ命令とは非
対称的です。このＰ及びＶ命令の非対称的性格は通常の
多重処理環境において、両者とも必要とされるものです
。この要求がセマフォと多重処理システムプロセッサ間
の処理インタフェースを複雑にしているのです。
Ｃ０発明の目的
本発明の第１の目的は、生産プロセス、消費プロセス両
方を扱うことのできる一つの命令を有する高度なマルチ
・プロセスの相互排他制御システムを提供することであ
る。
方を扱うことのできる一つの命令を有する高度なマルチ
・プロセスの相互排他制御システムを提供することであ
る。
本発明のもう一つの目的は、カウントがリミットよりも
大であるか等しいときでも、生産プロセスが消費プロセ
スを待つことができるマルチ・プロセスの相互排他制御
システムを提供することである。
大であるか等しいときでも、生産プロセスが消費プロセ
スを待つことができるマルチ・プロセスの相互排他制御
システムを提供することである。
Ｄ０発明の概要
これらの目的は本発明で示される高度なセマフォで達成
される。
される。
ここで１′フルフオ″と呼ぶ高度なセマフォは、ｒｔ
ｐ ｕ及び１１ Ｖ ＋＋処理を結合したＩＩ Ｓ Ｉ
＋焙処理呼ぶ消費プロセスと生産プロセス両者を扱うこ
との出きる処理を待つ。フルフォはカウント、リミット
、待機プロセスのための待ち行列、待機許可フラグ、そ
して処理フラグを有する。処理フラグによってカウント
が１つ増加したか、減少したかを判断する。フルフォの
Ｓ”処理の構造はｓ （Ｆ。
ｐ ｕ及び１１ Ｖ ＋＋処理を結合したＩＩ Ｓ Ｉ
＋焙処理呼ぶ消費プロセスと生産プロセス両者を扱うこ
との出きる処理を待つ。フルフォはカウント、リミット
、待機プロセスのための待ち行列、待機許可フラグ、そ
して処理フラグを有する。処理フラグによってカウント
が１つ増加したか、減少したかを判断する。フルフォの
Ｓ”処理の構造はｓ （Ｆ。
○Ｐ、すＡＩＴＪＥＲＭＩＴＴεＤ）であり、ここでＦ
はフルフオが実行されることを示し、ＯＰは生産プロセ
スを示す＋１、消費プロセスを示す−１，１１ＡＩ’ｊ
ＰＥＲＭＩ丁ＴＥＤ （待機許可）は必要時に処理が待
つ場合はＹＥＳ、そうでない場合はＮＯとなる。
はフルフオが実行されることを示し、ＯＰは生産プロセ
スを示す＋１、消費プロセスを示す−１，１１ＡＩ’ｊ
ＰＥＲＭＩ丁ＴＥＤ （待機許可）は必要時に処理が待
つ場合はＹＥＳ、そうでない場合はＮＯとなる。
フルフォが消費処理要求（ＯＰ＝−１で示される）を受
けると、まず最初にカウントがＱより小かあるいは等し
いかがチエツクされる。もし、そうテアル場合の要求は
ＷＡＩＴ−ＰＥＲＭＩＴＴＥＤ （待機許可）がＹＥＳ
でなければ失敗（フェイル）となる。もし、ＷＡＩＴ−
ＰＥＲＭＩＴＴＥＤ （待機許可）がＹＥＳであれば、
ＯＰ（−１）がカウントに加えられカウントは減少する
。プロセスは生産プロセスによって指名されるまで待ち
行列に待つこととなる。もし、カウントが０より小でも
等しくもないときで、かつカウントがリミットを越えて
いないときは、０Ｐ（−４）がカウントに加えられカウ
ントが減少し、要求は成功する。もし、カウントがリミ
ットより大であり、待ち生産プロセスがあるときは待ち
生産プロセスが指定され、ＯＰ（−１）がカウントに加
えられ、どちらのプロセス要求も成功して終了する。
けると、まず最初にカウントがＱより小かあるいは等し
いかがチエツクされる。もし、そうテアル場合の要求は
ＷＡＩＴ−ＰＥＲＭＩＴＴＥＤ （待機許可）がＹＥＳ
でなければ失敗（フェイル）となる。もし、ＷＡＩＴ−
ＰＥＲＭＩＴＴＥＤ （待機許可）がＹＥＳであれば、
ＯＰ（−１）がカウントに加えられカウントは減少する
。プロセスは生産プロセスによって指名されるまで待ち
行列に待つこととなる。もし、カウントが０より小でも
等しくもないときで、かつカウントがリミットを越えて
いないときは、０Ｐ（−４）がカウントに加えられカウ
ントが減少し、要求は成功する。もし、カウントがリミ
ットより大であり、待ち生産プロセスがあるときは待ち
生産プロセスが指定され、ＯＰ（−１）がカウントに加
えられ、どちらのプロセス要求も成功して終了する。
フルフォが生産処理要求（ＯＰ＝＋１で示される）を受
けると、まず最初にカウントがリミットより大かあるい
は等しいかがチエツクされる。もし、そうである場合の
要求はＷＡＩＴ、−ＰＥＲＭＩＴＴＥＤ （待機許可）
がＹＥＳでなければ失敗となる。もし、ＷＡＩＴ−ＰＥ
ＲＭＩＴＴＥＤがＹＥＳであれば、ＯＰ （＋１）がカ
ウントに加えられカウントは増加する。プロセスは消費
プロセスによって指名されるまで待ち行列に待つことと
なる。もし、カウントがリミットより大でも等しくもな
いときで、かつカウントがＯより小でないときは、ＯＰ
（＋１）がカウントに加えられカウントが増加し、要
求は成功する。
けると、まず最初にカウントがリミットより大かあるい
は等しいかがチエツクされる。もし、そうである場合の
要求はＷＡＩＴ、−ＰＥＲＭＩＴＴＥＤ （待機許可）
がＹＥＳでなければ失敗となる。もし、ＷＡＩＴ−ＰＥ
ＲＭＩＴＴＥＤがＹＥＳであれば、ＯＰ （＋１）がカ
ウントに加えられカウントは増加する。プロセスは消費
プロセスによって指名されるまで待ち行列に待つことと
なる。もし、カウントがリミットより大でも等しくもな
いときで、かつカウントがＯより小でないときは、ＯＰ
（＋１）がカウントに加えられカウントが増加し、要
求は成功する。
もし、カウントが０より小であり、待ち消費プロセスが
あるときは待ち消費プロセスが指名され、ＯＰ （＋１
）がカウントに加えられ、どちらのプロセス要求も成功
して終了する。
あるときは待ち消費プロセスが指名され、ＯＰ （＋１
）がカウントに加えられ、どちらのプロセス要求も成功
して終了する。
第２図は消費プロセス（または消費タスク）において使
用される従来のセマフォＰ処理を示すブロック図である
。Ｐ処理構造はＰ （Ｓ 、 ＩＩＡＩＴ−ＰＥＲにＩ
ＴＴＥＤ ）で表され、ここでＳはセマフォの実行を表
しＷＡＩＴ−ＰＥＲＭＩＴＴＥＤ （待機許可）ハフロ
セスノ実行が出来ない場合、該プロセスが待つか否かを
表すフラグである。セマフォによってＰ処理が受は取ら
れたとき、ブロック１１においてカウントＣがＯより小
かあるいは等しいかをチエツクする。
用される従来のセマフォＰ処理を示すブロック図である
。Ｐ処理構造はＰ （Ｓ 、 ＩＩＡＩＴ−ＰＥＲにＩ
ＴＴＥＤ ）で表され、ここでＳはセマフォの実行を表
しＷＡＩＴ−ＰＥＲＭＩＴＴＥＤ （待機許可）ハフロ
セスノ実行が出来ない場合、該プロセスが待つか否かを
表すフラグである。セマフォによってＰ処理が受は取ら
れたとき、ブロック１１においてカウントＣがＯより小
かあるいは等しいかをチエツクする。
もしこの条件に該当しなければ、ブロック１２において
カウントが減少され、ブロック１３において要求が達成
する。もしこの条件に該当すれば、ブ０７り１４におい
てｖＡＩＴＪＥＲＭＩＴＴＥＤ （待機許可）フラグが
ＹＥＳかＮｏかの確認がなされる。フラグがＮｏであれ
ばブロック１５において要求は失敗する。フラグがＮｏ
であれば、ブロック１６においてカウントが減少され、
生産プロセスによって指名されるまで処理が待ち行列に
おいて待つことになる。
カウントが減少され、ブロック１３において要求が達成
する。もしこの条件に該当すれば、ブ０７り１４におい
てｖＡＩＴＪＥＲＭＩＴＴＥＤ （待機許可）フラグが
ＹＥＳかＮｏかの確認がなされる。フラグがＮｏであれ
ばブロック１５において要求は失敗する。フラグがＮｏ
であれば、ブロック１６においてカウントが減少され、
生産プロセスによって指名されるまで処理が待ち行列に
おいて待つことになる。
第３図は生産プロセス（または生産タスク）において使
用される従来のセマフォＶ処理を示すブロック図である
。■処理構造はＶ （Ｓ）で表され。
用される従来のセマフォＶ処理を示すブロック図である
。■処理構造はＶ （Ｓ）で表され。
ここでＳはセマフォの実行を表す。セマフォによってＶ
処理が受は取られたとき、ブロック２１においてカウン
トＣがリミットＬに等しいかをチエツクする。もしこの
条件に該当すれば、要求はブロック２２において失敗と
なる。カウントがリミットＬより小となるのを待つこと
の許されないプロセスは自動的に要求失敗となるのみで
ある。
処理が受は取られたとき、ブロック２１においてカウン
トＣがリミットＬに等しいかをチエツクする。もしこの
条件に該当すれば、要求はブロック２２において失敗と
なる。カウントがリミットＬより小となるのを待つこと
の許されないプロセスは自動的に要求失敗となるのみで
ある。
カウントがＬに等しくなければ、ブロック２２において
カウントがＯより小であるかの確認がなされる。もしそ
うでなければ、ブロック２４においてカウントが減少さ
れ、要求はブロック２５において達成される。カウント
が０より小であれば消費プロセスは待ち行列において待
機しく第２図のブロック１６参照）、ブロック２６にお
いて消費プロセスを指名しブロック１３において達成さ
れる。カウントはブロック２４において１だけ増加され
、生産プロセスはブロック２５において達成される。
カウントがＯより小であるかの確認がなされる。もしそ
うでなければ、ブロック２４においてカウントが減少さ
れ、要求はブロック２５において達成される。カウント
が０より小であれば消費プロセスは待ち行列において待
機しく第２図のブロック１６参照）、ブロック２６にお
いて消費プロセスを指名しブロック１３において達成さ
れる。カウントはブロック２４において１だけ増加され
、生産プロセスはブロック２５において達成される。
Ｅ、実施例
第１図に本発明におけるフルフォ“Ｓ ｌｊ処理のブロ
ック図を示す、フルフォにおいては、セマフォの“Ｐ”
及びｔｚｖ”処理を結合して消費プロセスと生産プロセ
スの両者を扱うことのできる単一の“Ｓ”処理を有する
。フルフォはカウント、リミット、処理待ち行列、ＷＡ
ＩＴ−ＰＥＲＭＩＴＴＥＤ ７ラグ、そしてＯＰ（処理
）フラグを待つ。ＯＰ（処理）フラグはカウントを１だ
け増加させるか、減少させるかを決定する。フルフォ“
Ｓ”処理はｓ （Ｆ。
ック図を示す、フルフォにおいては、セマフォの“Ｐ”
及びｔｚｖ”処理を結合して消費プロセスと生産プロセ
スの両者を扱うことのできる単一の“Ｓ”処理を有する
。フルフォはカウント、リミット、処理待ち行列、ＷＡ
ＩＴ−ＰＥＲＭＩＴＴＥＤ ７ラグ、そしてＯＰ（処理
）フラグを待つ。ＯＰ（処理）フラグはカウントを１だ
け増加させるか、減少させるかを決定する。フルフォ“
Ｓ”処理はｓ （Ｆ。
ＯＰ 、 ＶＡＩＴＪＥＲＭＩＴＴＥＤ） テあり、こ
こでＦはフルフォが実行されることを示し、ＯＰは生産
プロセスを示す＋１、消費プロセスを示す−１、ＷＡＩ
ＴＪＥＲＭＩＴＴＥＩ）は必要時に処理が待つ場合はＹ
ＥＳ、そうでない場合はＮＯとなる。
こでＦはフルフォが実行されることを示し、ＯＰは生産
プロセスを示す＋１、消費プロセスを示す−１、ＷＡＩ
ＴＪＥＲＭＩＴＴＥＩ）は必要時に処理が待つ場合はＹ
ＥＳ、そうでない場合はＮＯとなる。
フルフォが消費プロセス要求（、ＯＰ ＝ −１）を受
けると、まずブロック３１においてカウントが０より小
かあるいは等しいかのチエツクがなされる。もしこの条
件が満たされれば、ブロック３２におイテ、ＷＡＩＴｊ
ＥＲＭＩＴＴＥＤ ７ラグがＹＥＳかＮ。
けると、まずブロック３１においてカウントが０より小
かあるいは等しいかのチエツクがなされる。もしこの条
件が満たされれば、ブロック３２におイテ、ＷＡＩＴｊ
ＥＲＭＩＴＴＥＤ ７ラグがＹＥＳかＮ。
かがチエツクされる。フラグがＮｏであればブロック３
３において、要求失敗となる。 ＷＡＩＴＪＥＲに工Ｔ
ＴＥＤフラグがＹＥＳであれば、ブロック３４において
カウントにＯＰ＝ （−１）が加えられカウントが減少
する。プロセスは生産プロセスによる指名があるまで待
ち行列で待機する。
３において、要求失敗となる。 ＷＡＩＴＪＥＲに工Ｔ
ＴＥＤフラグがＹＥＳであれば、ブロック３４において
カウントにＯＰ＝ （−１）が加えられカウントが減少
する。プロセスは生産プロセスによる指名があるまで待
ち行列で待機する。
カウントがＯより小か、あるいは等しい場合はブロック
３５においてカウントがリミットを越えているかがチエ
ツクされる。カウントがリミットを越えていなければ、
ブロック３６において０Ｐ（−１）がカウントに加えら
れる。これによりカウントが減少しブロック３７におい
て要求は達成される。カウントがリミットを越えており
、待機生産プロセスが示されていれば、ブロック３８に
おいて待機生産プロセスが指名され実行が成功する。Ｏ
Ｐ （−１）がブロック３６においてカウントに加えら
れ、ブロック３７において消費要求は達成される。従来
のセマフォ構造では生産プロセスが消費プロセスを待つ
ことは出来ないことに留意されたい。上述したごとく、
これはフルフオ構造においてのみ実現できる。
３５においてカウントがリミットを越えているかがチエ
ツクされる。カウントがリミットを越えていなければ、
ブロック３６において０Ｐ（−１）がカウントに加えら
れる。これによりカウントが減少しブロック３７におい
て要求は達成される。カウントがリミットを越えており
、待機生産プロセスが示されていれば、ブロック３８に
おいて待機生産プロセスが指名され実行が成功する。Ｏ
Ｐ （−１）がブロック３６においてカウントに加えら
れ、ブロック３７において消費要求は達成される。従来
のセマフォ構造では生産プロセスが消費プロセスを待つ
ことは出来ないことに留意されたい。上述したごとく、
これはフルフオ構造においてのみ実現できる。
フルフオが生産プロセス要求（○Ｐ＝＋１）を受けると
、まずブロック３１においてカウントがリミットより大
かあるいは等しいかのチエツクがなされる。もしこの条
件が満たされれば、ブロック３２において、ＷＡＩＴ
ＰＥＲＭＩＴＴＥＯ７ラグがＹＥＳかＮｏかがチエツク
される。フラグがＮｏであればブロック３３において、
要求失敗となる。ＩＩＡＩＴＰＥＲＭＩＴＴＥＤフラグ
がＹＥＳであれば、ブロック３４においてカウントにＯ
Ｐ＝ （＋１）が加、えられカウントが増加する。プロ
セスは消費プロセスによる指名があるまで待ち行列で待
機する。
、まずブロック３１においてカウントがリミットより大
かあるいは等しいかのチエツクがなされる。もしこの条
件が満たされれば、ブロック３２において、ＷＡＩＴ
ＰＥＲＭＩＴＴＥＯ７ラグがＹＥＳかＮｏかがチエツク
される。フラグがＮｏであればブロック３３において、
要求失敗となる。ＩＩＡＩＴＰＥＲＭＩＴＴＥＤフラグ
がＹＥＳであれば、ブロック３４においてカウントにＯ
Ｐ＝ （＋１）が加、えられカウントが増加する。プロ
セスは消費プロセスによる指名があるまで待ち行列で待
機する。
カウントがリミットより大か、あるいは等しい場合はブ
ロック３５においてカウントがＯより小かがチエツクさ
れる。もしそうでなければ、ブロック３６においてＯＰ
（＋１）がカウントに加えられる。これによりカウン
トが増加しブロック３７において要求は達成される。カ
ウントがＯより小であり、待機消費プロセスが示されて
いれば、ブロック３８において待機消費プロセスが指名
され実行が成功する。ＯＰ （＋１）がブロック３６に
おいてカウントに加えられ、ブロック３７において消費
要求は達成される。
ロック３５においてカウントがＯより小かがチエツクさ
れる。もしそうでなければ、ブロック３６においてＯＰ
（＋１）がカウントに加えられる。これによりカウン
トが増加しブロック３７において要求は達成される。カ
ウントがＯより小であり、待機消費プロセスが示されて
いれば、ブロック３８において待機消費プロセスが指名
され実行が成功する。ＯＰ （＋１）がブロック３６に
おいてカウントに加えられ、ブロック３７において消費
要求は達成される。
フルフォ構造はフルフォ及び多重処理システムプロセッ
サ間の操作インターフェースを著しく簡略化した。フル
フォはセマフォの使用されるいかなる場所でも使用可能
である。また、フルフォは単一のセマフォでは不十分な
所でも使用できる。
サ間の操作インターフェースを著しく簡略化した。フル
フォはセマフォの使用されるいかなる場所でも使用可能
である。また、フルフォは単一のセマフォでは不十分な
所でも使用できる。
フルフォの最も適した使用例として、環状バッファに対
する同期アクセスがある。環状バッファは例えば情報生
産側から情報消費側へ受渡しが行なわれるようなハウス
インフォメーションに使用される。情報の処理を消費側
が生産側の供給よりも早く処理が出きる時には消費側は
待たなければならない。同様に生産側が消費側の処理よ
り早く情報を送出したときは、生産側が待たなければな
らない、これは環状バッファが満杯となり、さらに未処
理の情報を保持できないからである。
する同期アクセスがある。環状バッファは例えば情報生
産側から情報消費側へ受渡しが行なわれるようなハウス
インフォメーションに使用される。情報の処理を消費側
が生産側の供給よりも早く処理が出きる時には消費側は
待たなければならない。同様に生産側が消費側の処理よ
り早く情報を送出したときは、生産側が待たなければな
らない、これは環状バッファが満杯となり、さらに未処
理の情報を保持できないからである。
環状バッファに保持可能な情報の数と同数のリミットセ
ットを有し、イニシャルカウントが０である単一フルフ
ォは要求された同期に提供する。
ットを有し、イニシャルカウントが０である単一フルフ
ォは要求された同期に提供する。
カウントは環状バッファ中の情報の数を表す。生産側は
カウントを増加させ、バッファが満杯のときは待機する
。消費側はカウントを減少させ、バッファが空のときは
待機する。この同期をセマフォによってのみ達成しよう
とすると３つのセマフォが必要となる。１つはモニタと
して、２つはバッファが満杯あるいは空のときの待機メ
カニズムを支援するのに使用される。モニタは２つのセ
マフォの交換を同期するのに必要とされる。というのは
これらの交換は非常に微妙なタイミングで行なわれなけ
ればならないからである。フルフォはモニタを必要とし
ない、１つの同期対象がすべてを処理するからである。
カウントを増加させ、バッファが満杯のときは待機する
。消費側はカウントを減少させ、バッファが空のときは
待機する。この同期をセマフォによってのみ達成しよう
とすると３つのセマフォが必要となる。１つはモニタと
して、２つはバッファが満杯あるいは空のときの待機メ
カニズムを支援するのに使用される。モニタは２つのセ
マフォの交換を同期するのに必要とされる。というのは
これらの交換は非常に微妙なタイミングで行なわれなけ
ればならないからである。フルフォはモニタを必要とし
ない、１つの同期対象がすべてを処理するからである。
フルフォのもう１つの使用として、パラメータ無しＡＤ
Ａランデブー装置がある。ＡＤＡランデブーは、単一の
実行道筋が２つに分岐し、分岐した２つの道筋が終了し
たときにこれらが集まり単一路となるようなシステムで
ある。まず最初、フルフオは０のリミットを待ち、カウ
ントはＯである。そして１つの道筋はフルフォカウント
の増加、２つの道筋はフルフォカウントの減少、ランデ
ブーは両道筋が終了したときに起こる。どちらの道筋が
先に完了しても待機することとなる。カウントエリミツ
ト＝Ｏだからである。２番目に終了した道筋のみが待機
せず、１番目の待機の終了を指示する。ＡＤＡランデブ
ーはランデブー時のパラメータの受渡しを支援する。こ
の支援はフルフォによって、より一層効率的にできる。
Ａランデブー装置がある。ＡＤＡランデブーは、単一の
実行道筋が２つに分岐し、分岐した２つの道筋が終了し
たときにこれらが集まり単一路となるようなシステムで
ある。まず最初、フルフオは０のリミットを待ち、カウ
ントはＯである。そして１つの道筋はフルフォカウント
の増加、２つの道筋はフルフォカウントの減少、ランデ
ブーは両道筋が終了したときに起こる。どちらの道筋が
先に完了しても待機することとなる。カウントエリミツ
ト＝Ｏだからである。２番目に終了した道筋のみが待機
せず、１番目の待機の終了を指示する。ＡＤＡランデブ
ーはランデブー時のパラメータの受渡しを支援する。こ
の支援はフルフォによって、より一層効率的にできる。
フルフオを使用しないランデブー装置は、どちらの道筋
が先に終了するかを確認するモニタセマフォ、そして２
番目に終了した道筋が１番目に終了した道筋の指名を許
可するもうひとつのセマフォを必要とする。
が先に終了するかを確認するモニタセマフォ、そして２
番目に終了した道筋が１番目に終了した道筋の指名を許
可するもうひとつのセマフォを必要とする。
Ｆ０発明の効果
本発明によれば、生産プロセス及び消費プロセス両方を
統一的に、かつ対称的に扱うことのできる高度なマルチ
・プロセスの相互排他制御システムを提供する。
統一的に、かつ対称的に扱うことのできる高度なマルチ
・プロセスの相互排他制御システムを提供する。
第１図は本発明のフルフォ構造におけるＳ処理を示すブ
ロック図、第２図は従来のセマフォ構造におけるＰ処理
を示すブロック図、第３図は従来のセマフォ構造におけ
るＶ処理を示すブロック図である。 第１図
ロック図、第２図は従来のセマフォ構造におけるＰ処理
を示すブロック図、第３図は従来のセマフォ構造におけ
るＶ処理を示すブロック図である。 第１図
Claims (2)
- （１）コンピュータシステムにおける消費プロセス及び
生産プロセス間の相互排他の実行システムに関し、； 処理フラグに応答して増加、減少を実行するカウント手
段と、 上記カウントに対するリミット値保持手段と、待機状態
にある上記消費プロセス及び生産プロセスの待ち行列を
形成・維持する手段とを有することを特徴とするマルチ
・プロセスの相互排他制御システム。 - （２）処理フラグに応答して増加、減少を実行するカウ
ント手段と、上記カウント手段によるカウントと比較さ
れるリミット値保持手段と、待ち行列とを有するコンピ
ュータシステムにおける消費タスク及び生産タスク間の
相互排他の実行方法に関し、； プロセス毎に待機許可フラグと処理フラグとをセット可
能とし、 生産プロセスについて実行されるステップは：上記処理
フラグを増加状態にセットし； 上記カウントが上記リミットより大かあるいは等しく、
かつ上記待機許可フラグがオフであるときに上記生産プ
ロセスを強制的にフェイルとし；上記カウントが上記リ
ミットより大かあるいは等しく、かつ上記待機許可フラ
グがオンであるとき、上記カウントを増加させ、上記生
産プロセスを上記待ち行列に待機させて、上記消費プロ
セスのための指名ステップによる指名があるまで待機状
態となし； 上記カウントが上記リミットより小かあるいは等しいと
き、上記カウントを増加させ、上記生産プロセスを実行
し； 上記カウントが上記リミットより大であるとき、待機消
費プロセスを指名し、上記カウントを増加させ上記生産
プロセスを実行する； ステップからなり、 消費プロセスについて実行されるステップは：上記処理
フラグを減少状態にセットし； 上記カウントが０より小かあるいは等しく、かつ上記待
機許可フラグがオフであるときに上記消費プロセスを強
制的にフェイルとし； 上記カウントが０より小かあるいは等しく、かつ上記待
機許可フラグがオンであるとき、上記カウントを減少さ
せ、上記消費プロセスを上記待ち行列に待機させて、上
記生産プロセスのための指名ステップによる指名がある
まで待機状態となし；上記カウントが０より大かあるい
は等しいとき、上記カウントを減少させ、上記消費プロ
セスを実行し； 上記カウントが０より小であるとき、待機生産プロセス
を指名し、上記カウントを減少させ上記消費プロセスを
実行する； ステップからなることを特徴とするマルチ・プロセスの
相互排他制御方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US265088 | 1981-05-19 | ||
| US07/265,088 US4928222A (en) | 1988-10-31 | 1988-10-31 | Enhanced semaphore architecture |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02129726A true JPH02129726A (ja) | 1990-05-17 |
| JPH0769843B2 JPH0769843B2 (ja) | 1995-07-31 |
Family
ID=23008927
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1184882A Expired - Lifetime JPH0769843B2 (ja) | 1988-10-31 | 1989-07-19 | 相互排他を効率的に行う方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4928222A (ja) |
| EP (1) | EP0367701B1 (ja) |
| JP (1) | JPH0769843B2 (ja) |
| DE (1) | DE68925462T2 (ja) |
Families Citing this family (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5179708A (en) * | 1989-04-07 | 1993-01-12 | At&T Bell Laboratories | System inhibiting message delivery to destination process until priority of process excuting on distination processor is no higher than priority of sending process |
| US5057996A (en) * | 1989-06-29 | 1991-10-15 | Digital Equipment Corporation | Waitable object creation system and method in an object based computer operating system |
| US5255387A (en) * | 1990-04-27 | 1993-10-19 | International Business Machines Corporation | Method and apparatus for concurrency control of shared data updates and queries |
| US5307487A (en) * | 1991-10-03 | 1994-04-26 | The United States Of America As Represented By The Secretary Of The Navy | Method of database synchronization with consistency determined by entry and exit counters used on both update and retrieval |
| US5261106A (en) * | 1991-12-13 | 1993-11-09 | S-Mos Systems, Inc. | Semaphore bypass |
| US5440746A (en) * | 1992-11-06 | 1995-08-08 | Seiko Epson Corporation | System and method for synchronizing processors in a parallel processing environment |
| JPH08137799A (ja) * | 1994-11-08 | 1996-05-31 | Sony Corp | サイバースペースシステム |
| US6532487B1 (en) | 1995-12-04 | 2003-03-11 | International Business Machines Corporation | Method and system for managing semaphores in an object-oriented multi-tasking computer system |
| US5872980A (en) * | 1996-01-25 | 1999-02-16 | International Business Machines Corporation | Semaphore access control buffer and method for accelerated semaphore operations |
| JP2000090057A (ja) * | 1998-09-11 | 2000-03-31 | Omron Corp | グループオブジェクト及び制御システム |
| EP1033654A1 (en) * | 1999-03-01 | 2000-09-06 | Sony International (Europe) GmbH | Buffered communication between entities operating at different data rates |
| FR2829848A1 (fr) * | 2001-09-20 | 2003-03-21 | Cp8 | Procede de gestion d'acces a des ressources partagees dans un systeme embarque et systeme embarque pour la mise en oeuvre d'un tel procede |
| EP1449060A1 (en) * | 2001-11-13 | 2004-08-25 | Koninklijke Philips Electronics N.V. | P- and v-semaphore operation |
| US7395527B2 (en) | 2003-09-30 | 2008-07-01 | International Business Machines Corporation | Method and apparatus for counting instruction execution and data accesses |
| US7421681B2 (en) * | 2003-10-09 | 2008-09-02 | International Business Machines Corporation | Method and system for autonomic monitoring of semaphore operation in an application |
| US8381037B2 (en) | 2003-10-09 | 2013-02-19 | International Business Machines Corporation | Method and system for autonomic execution path selection in an application |
| US7895382B2 (en) | 2004-01-14 | 2011-02-22 | International Business Machines Corporation | Method and apparatus for qualifying collection of performance monitoring events by types of interrupt when interrupt occurs |
| US7415705B2 (en) | 2004-01-14 | 2008-08-19 | International Business Machines Corporation | Autonomic method and apparatus for hardware assist for patching code |
| US9553951B1 (en) | 2013-04-24 | 2017-01-24 | Amazon Technologies, Inc. | Semaphores in distributed computing environments |
| CN103761155A (zh) * | 2014-01-29 | 2014-04-30 | 赛凡信息科技（厦门）有限公司 | 一种带配额的信号量 |
| US9760529B1 (en) | 2014-09-17 | 2017-09-12 | Amazon Technologies, Inc. | Distributed state manager bootstrapping |
| US9852221B1 (en) | 2015-03-26 | 2017-12-26 | Amazon Technologies, Inc. | Distributed state manager jury selection |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2253423A5 (ja) * | 1973-11-30 | 1975-06-27 | Honeywell Bull Soc Ind | |
| FR2253425A5 (ja) * | 1973-11-30 | 1975-06-27 | Honeywell Bull Soc Ind | |
| FR2253420A5 (ja) * | 1973-11-30 | 1975-06-27 | Honeywell Bull Soc Ind | |
| FR2253418A5 (ja) * | 1973-11-30 | 1975-06-27 | Honeywell Bull Soc Ind | |
| US4320451A (en) * | 1974-04-19 | 1982-03-16 | Honeywell Information Systems Inc. | Extended semaphore architecture |
| US4369494A (en) * | 1974-12-09 | 1983-01-18 | Compagnie Honeywell Bull | Apparatus and method for providing synchronization between processes and events occurring at different times in a data processing system |
| US4380798A (en) * | 1980-09-15 | 1983-04-19 | Motorola, Inc. | Semaphore register including ownership bits |
| US4412285A (en) * | 1981-04-01 | 1983-10-25 | Teradata Corporation | Multiprocessor intercommunication system and method |
| US4594657A (en) * | 1983-04-22 | 1986-06-10 | Motorola, Inc. | Semaphore for memory shared by two asynchronous microcomputers |
| CA1239227A (en) * | 1984-10-17 | 1988-07-12 | Randy D. Pfeifer | Method of and arrangement for ordering of multiprocessor operations in a multiprocessor system |
| US4722048A (en) * | 1985-04-03 | 1988-01-26 | Honeywell Bull Inc. | Microcomputer system with independent operating systems |
| US4725946A (en) * | 1985-06-27 | 1988-02-16 | Honeywell Information Systems Inc. | P and V instructions for semaphore architecture in a multiprogramming/multiprocessing environment |
| US4754398A (en) * | 1985-06-28 | 1988-06-28 | Cray Research, Inc. | System for multiprocessor communication using local and common semaphore and information registers |
| US4780822A (en) * | 1986-09-17 | 1988-10-25 | Integrated Device Technology, Inc. | Semaphore circuit for shared memory cells |
-
1988
- 1988-10-31 US US07/265,088 patent/US4928222A/en not_active Expired - Fee Related
-
1989
- 1989-07-19 JP JP1184882A patent/JPH0769843B2/ja not_active Expired - Lifetime
- 1989-09-12 EP EP89480140A patent/EP0367701B1/en not_active Expired - Lifetime
- 1989-09-12 DE DE68925462T patent/DE68925462T2/de not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| DE68925462T2 (de) | 1996-09-05 |
| US4928222A (en) | 1990-05-22 |
| EP0367701A2 (en) | 1990-05-09 |
| DE68925462D1 (de) | 1996-02-29 |
| JPH0769843B2 (ja) | 1995-07-31 |
| EP0367701A3 (en) | 1992-05-20 |
| EP0367701B1 (en) | 1996-01-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0769843B2 (ja) | 相互排他を効率的に行う方法 | |
| JP6797880B2 (ja) | マルチタイル、マルチチップ処理構成における同期 | |
| US5666523A (en) | Method and system for distributing asynchronous input from a system input queue to reduce context switches | |
| EP0527301A2 (en) | Controlled scheduling of program threads in a multitasking operating system | |
| US20050240924A1 (en) | Prerequisite-based scheduler | |
| JPH0640324B2 (ja) | マルチプロセッサ・システムおよびそのプロセス同期方法 | |
| CN110187956B (zh) | 一种多智能体平台的分层实时任务调度方法和系统 | |
| CN119487493A (zh) | 进程间通信的同步机制 | |
| Wu et al. | Switchflow: preemptive multitasking for deep learning | |
| Bakkers et al. | Transputer based control of mechatronic systems | |
| US20200073351A1 (en) | Approach and mechanism for execution of critical system operations | |
| Janowski et al. | Dynamic scheduling in the presence of faults: Specification and verification | |
| US20230367633A1 (en) | Gpu and gpu method | |
| Chen et al. | Satyr and the nymph: Software archetype for real time robotics | |
| Ghosh et al. | A Survey of Real-Time Operating Systems {Draft | |
| JP2553526B2 (ja) | マルチタスク処理装置 | |
| JPS63101957A (ja) | プロセツサ | |
| CN110716801B (zh) | 一种具有多个竞争代理的多任务调度方法 | |
| TWI308718B (en) | Arbitrating structure and method responding to interrupt service request for use in multi-processor system | |
| JPH061466B2 (ja) | ロック排他制御方式 | |
| TW202443340A (zh) | 光電計算系統及資料處理方法 | |
| JPH11306037A (ja) | 並列演算処理装置およびその方法 | |
| Buchanan | Processes and Scheduling | |
| Wheatley et al. | Requirements for implementing real-time control functional modules on a hierarchical parallel pipelined system | |
| JPH0340416B2 (ja) |