JPH0642204B2 - 待ち行列又はスタックから要素を除去する方法 - Google Patents
待ち行列又はスタックから要素を除去する方法Info
- Publication number
- JPH0642204B2 JPH0642204B2 JP1276178A JP27617889A JPH0642204B2 JP H0642204 B2 JPH0642204 B2 JP H0642204B2 JP 1276178 A JP1276178 A JP 1276178A JP 27617889 A JP27617889 A JP 27617889A JP H0642204 B2 JPH0642204 B2 JP H0642204B2
- Authority
- JP
- Japan
- Prior art keywords
- operand
- queue
- memory
- pointer
- stack
- 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.)
- Expired - Lifetime
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
-
- 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/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/30003—Arrangements for executing specific machine instructions
- G06F9/30007—Arrangements for executing specific machine instructions to perform operations on data operands
- G06F9/30032—Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Advance Control (AREA)
Description
【発明の詳細な説明】 Ａ．産業上の利用分野 この発明は多重プロセツシング・ユニツトないし多重プ
ログラム・コンピユータ・システムにおける時系列リス
トの操作に関し、より具体的には、多重プロセツシング
・ユニツトが非同期でリストをアクセスするときでもロ
ツク機構なしで項目の付加または削除を行えるようにし
たものである。またこの発明はリスト操作を実行するた
めの新規なコンピユータ命令にも関連する。
ログラム・コンピユータ・システムにおける時系列リス
トの操作に関し、より具体的には、多重プロセツシング
・ユニツトが非同期でリストをアクセスするときでもロ
ツク機構なしで項目の付加または削除を行えるようにし
たものである。またこの発明はリスト操作を実行するた
めの新規なコンピユータ命令にも関連する。
Ｂ．従来の技術 この発明は待ち行列およびスタツクの双方を扱う。ＦＩ
ＦＯ（フアースト・イン・フアースト・アウト）リスト
とも呼ばれる待ち行列においては、最初にリストに付加
された項目が最初に除去される。ＬＩＦＯ（ラスト・イ
ン・フアースト・アウト）リストとも呼ばれるスタツク
においては最後にリストに付加された項目が最初に除去
される。オペレーテイン・システムやサブ・システム環
境において非同期のＦＩＦＯおよびＬＩＦＯリストの操
作は非常に一般的である。このような環境下で時系列リ
ストをすばやくかつ簡易に操作できないと、多大な制約
となつてしまう。緊密結合構成において用いられるプロ
セツサの個数が増大し続けているので、ソフトウエアに
よりシリアル化のコストも増大して行く。時系列リスト
は頻繁に用いられるので、このコストはたえがたいもの
になりつつある。
ＦＯ（フアースト・イン・フアースト・アウト）リスト
とも呼ばれる待ち行列においては、最初にリストに付加
された項目が最初に除去される。ＬＩＦＯ（ラスト・イ
ン・フアースト・アウト）リストとも呼ばれるスタツク
においては最後にリストに付加された項目が最初に除去
される。オペレーテイン・システムやサブ・システム環
境において非同期のＦＩＦＯおよびＬＩＦＯリストの操
作は非常に一般的である。このような環境下で時系列リ
ストをすばやくかつ簡易に操作できないと、多大な制約
となつてしまう。緊密結合構成において用いられるプロ
セツサの個数が増大し続けているので、ソフトウエアに
よりシリアル化のコストも増大して行く。時系列リスト
は頻繁に用いられるので、このコストはたえがたいもの
になりつつある。
現在ＦＩＦＯリストの管理手法としては２つのものがあ
る。単ヘツド待ち行列に対しては、リストはアンカ（an
chor）点を有するものとして定義され、すべてのエレメ
ントはこのアンカ点を用いて付加され、またリストをサ
ーチ・ダウンし且つ最後のエレメントを除去することに
よりすべてのエレメントが削除されていく。この手法で
は多重付加が可能となるが一方単一削除しか実現できな
い。またこの手法では削除サーチをリストの終りまで行
う必要があり、削除がページ・フオールトによつて割り
込まれることがある。ページ・フオールトを復旧するこ
とは可能だけれど、これにともなうオーバーヘツドはリ
ストが長くなると過大なものとなる。
る。単ヘツド待ち行列に対しては、リストはアンカ（an
chor）点を有するものとして定義され、すべてのエレメ
ントはこのアンカ点を用いて付加され、またリストをサ
ーチ・ダウンし且つ最後のエレメントを除去することに
よりすべてのエレメントが削除されていく。この手法で
は多重付加が可能となるが一方単一削除しか実現できな
い。またこの手法では削除サーチをリストの終りまで行
う必要があり、削除がページ・フオールトによつて割り
込まれることがある。ページ・フオールトを復旧するこ
とは可能だけれど、これにともなうオーバーヘツドはリ
ストが長くなると過大なものとなる。
二重ヘツド待ち行列に対しては、リストは２つのアンカ
点を有するものとして定義され、すべてのエレメントは
一方のアンカ点を用いて付加され、他方のアンカ点を用
いて削除される。この手法では一時に１つの付加または
削除しかリストにアクセスできない。単一アクセスしか
一時に許されないということを保障するため、何らかの
実現方法（ロツク機構）を採用しなければならない。
点を有するものとして定義され、すべてのエレメントは
一方のアンカ点を用いて付加され、他方のアンカ点を用
いて削除される。この手法では一時に１つの付加または
削除しかリストにアクセスできない。単一アクセスしか
一時に許されないということを保障するため、何らかの
実現方法（ロツク機構）を採用しなければならない。
最初の手法は、過剰なページングが予想されるので実際
的でない。第２の手法はロツク機構を必要とするという
制約の点から効率の劣化が予想される。
的でない。第２の手法はロツク機構を必要とするという
制約の点から効率の劣化が予想される。
ＬＩＦＯリストをモニタする最も一般的な手法はスタツ
ク中に１つのアンカ点をセツトし、このアンカ点を利用
してすべてのエレメントを付加（プツシユ）および削除
（ポツプ）するというものである。ＩＢＭ System／３
７０ Extended Architecture Printiples of Operatio
n（ＩＢＭ 出版物番号ＳＡ２２−７０８５−０、以下
では文献３７０ＸＡと呼ぶ）の第Ａ４５頁には多重非同
期ロツクなしの付加および削除を実現する例が示されて
いる。これは表１と同一である。このリストは標準的な
Ｓ／３７０プロセツサ・セグメントを含み、これは当業
者に周知である。第１列はニーモニツク・ラベルを列挙
し、第２列はオペレーシヨンないしインストラクシヨン
・フイールドであり、第３列はオペランド・フイールド
を列挙し、第４列はコメント欄である。これは当業者に
周知の標準的なフオーマツトである。
ク中に１つのアンカ点をセツトし、このアンカ点を利用
してすべてのエレメントを付加（プツシユ）および削除
（ポツプ）するというものである。ＩＢＭ System／３
７０ Extended Architecture Printiples of Operatio
n（ＩＢＭ 出版物番号ＳＡ２２−７０８５−０、以下
では文献３７０ＸＡと呼ぶ）の第Ａ４５頁には多重非同
期ロツクなしの付加および削除を実現する例が示されて
いる。これは表１と同一である。このリストは標準的な
Ｓ／３７０プロセツサ・セグメントを含み、これは当業
者に周知である。第１列はニーモニツク・ラベルを列挙
し、第２列はオペレーシヨンないしインストラクシヨン
・フイールドであり、第３列はオペランド・フイールド
を列挙し、第４列はコメント欄である。これは当業者に
周知の標準的なフオーマツトである。
第１の例は１０番目および１１番目のＤＥＬＥＴＥＱの
インストラクシヨン間の割り込みに対する問題しか解消
しない。７番目のおよび１０番目のインストラクシヨン
の間の割り込みに対する問題は解消しない。もしＤＥＬ
ＥＴＥＱが７番目および１０番目のインストラクシヨン
の間で割り込みを受けると、リストの第１番目のエレメ
ントが待ち行列から解除され自由になり、１０番目のイ
ンストラクシヨンが無効アドレスのためにプログラム・
チエツクにぶつかる。
インストラクシヨン間の割り込みに対する問題しか解消
しない。７番目のおよび１０番目のインストラクシヨン
の間の割り込みに対する問題は解消しない。もしＤＥＬ
ＥＴＥＱが７番目および１０番目のインストラクシヨン
の間で割り込みを受けると、リストの第１番目のエレメ
ントが待ち行列から解除され自由になり、１０番目のイ
ンストラクシヨンが無効アドレスのためにプログラム・
チエツクにぶつかる。
他の例としては米国特許第４３９４７２７号明細書およ
び米国特許第４３２０４５５号明細書およびＩＢＭ Te
chnical Disclosure Bulletion、Vol.24、pp２７１６〜
２７２３、１９８１年１１月がある。これらはロツク・
ビツトやロツク・ワードを用いている。
び米国特許第４３２０４５５号明細書およびＩＢＭ Te
chnical Disclosure Bulletion、Vol.24、pp２７１６〜
２７２３、１９８１年１１月がある。これらはロツク・
ビツトやロツク・ワードを用いている。
多重プロセツシングないし多重プログラム・コンピユー
テイング・システムにおいて所定の場合にロツク機構を
用いないですませる１つの手法が、米国特許第３８８６
５２５号明細書に記載されている。
テイング・システムにおいて所定の場合にロツク機構を
用いないですませる１つの手法が、米国特許第３８８６
５２５号明細書に記載されている。
米国特許第３８８６５２５号明細書の手法「比較および
スワツプ」（Compare and Swap）という新しいインスト
ラクシヨンを含んでいた。このインストラクシヨンを用
いることにより、共有データの各ユーザは共有データ記
憶におけるアドレス可能位置でその共有データをアクセ
スすること許され、プログラム・インストラクシヨン・
シーケンスによつてさらに処理を行える。処理ののち、
処理されたデータは共有データ記憶におけるアドレス位
置に戻される。「比較およびスワツプ」を用いると、イ
ンストラクシヨンによりアクセスされたアドレス位置の
データ内容が、処理前アドレス位置からアクセスされた
データと比較される。この比較の結果、共有データの処
理の間に他のユーザが共有データをアクセスして処理
し、値の異なつた共有データをアドレス記憶位置に戻し
たか否かを判別できる。ＣＳ（比較およびスワツプ）イ
ンストラクシヨンに応じて、アドレス位置の値が他のユ
ーザによつて修正されたことが判明すると、修正値はそ
のユーザによつて保持され、処理がその修正値について
再起動させられる。ＧＳインストラクシヨンによつてア
クセスされたアドレス位置のデータ値が処理前にそのユ
ーザによつてアクセスされたデータの値と同じであれ
ば、他のユーザが共有データにアクセスし、修正してい
ることがないと判明する。したがつて処理データはアド
レス位置に転送され、後続の処理が許される（米国特許
第３８８６５２５号明細書第２欄８〜３９行）。
スワツプ」（Compare and Swap）という新しいインスト
ラクシヨンを含んでいた。このインストラクシヨンを用
いることにより、共有データの各ユーザは共有データ記
憶におけるアドレス可能位置でその共有データをアクセ
スすること許され、プログラム・インストラクシヨン・
シーケンスによつてさらに処理を行える。処理ののち、
処理されたデータは共有データ記憶におけるアドレス位
置に戻される。「比較およびスワツプ」を用いると、イ
ンストラクシヨンによりアクセスされたアドレス位置の
データ内容が、処理前アドレス位置からアクセスされた
データと比較される。この比較の結果、共有データの処
理の間に他のユーザが共有データをアクセスして処理
し、値の異なつた共有データをアドレス記憶位置に戻し
たか否かを判別できる。ＣＳ（比較およびスワツプ）イ
ンストラクシヨンに応じて、アドレス位置の値が他のユ
ーザによつて修正されたことが判明すると、修正値はそ
のユーザによつて保持され、処理がその修正値について
再起動させられる。ＧＳインストラクシヨンによつてア
クセスされたアドレス位置のデータ値が処理前にそのユ
ーザによつてアクセスされたデータの値と同じであれ
ば、他のユーザが共有データにアクセスし、修正してい
ることがないと判明する。したがつて処理データはアド
レス位置に転送され、後続の処理が許される（米国特許
第３８８６５２５号明細書第２欄８〜３９行）。
ＣＯＭＰＡＲＥ ＡＮＤ ＳＷＡＰ（ＣＳ）インストラ
クシヨンおよびその変形ＣＯＭＰＡＲＥ ＤＯＵＢＬＥ
ＡＮＤ ＳＷＡＰ（ＣＤＳ）インストラクシヨンは現
在マルチ・プログラミングおよびマルチ・プロセツシン
グ環境で用いられカウンタ、フラグ、コントロール・ワ
ードおよび他の共通記憶領域のアクセスをシリアル化し
ている。文献３７０ＸＡはＣＳおよびＣＤＳインストラ
クシヨンの使用例を示している。多分最も留意すべき点
は、機能が割り込み用に実行可能とされるプログラムに
よつて実現され（マルチ・プログラミング）、またマル
チ・プロセツシング構成で実行されるプログラムによつ
て実現されるという点である。換言すれば、インストラ
クシヨンＣＳおよびＣＤＳにより、プログラムが、実行
可能時に記憶位置の内容を修正できる。これはルーチン
が、たとえ同一のＣＰＵにはりついている他のプログラ
ム（その記憶位置を修正する）により割り込まれ得る場
合も同じである。また他のＣＰＵが同時に同じ記憶位置
を更新する可能性がある場合ですら同じである。
クシヨンおよびその変形ＣＯＭＰＡＲＥ ＤＯＵＢＬＥ
ＡＮＤ ＳＷＡＰ（ＣＤＳ）インストラクシヨンは現
在マルチ・プログラミングおよびマルチ・プロセツシン
グ環境で用いられカウンタ、フラグ、コントロール・ワ
ードおよび他の共通記憶領域のアクセスをシリアル化し
ている。文献３７０ＸＡはＣＳおよびＣＤＳインストラ
クシヨンの使用例を示している。多分最も留意すべき点
は、機能が割り込み用に実行可能とされるプログラムに
よつて実現され（マルチ・プログラミング）、またマル
チ・プロセツシング構成で実行されるプログラムによつ
て実現されるという点である。換言すれば、インストラ
クシヨンＣＳおよびＣＤＳにより、プログラムが、実行
可能時に記憶位置の内容を修正できる。これはルーチン
が、たとえ同一のＣＰＵにはりついている他のプログラ
ム（その記憶位置を修正する）により割り込まれ得る場
合も同じである。また他のＣＰＵが同時に同じ記憶位置
を更新する可能性がある場合ですら同じである。
ＣＳインストラクシヨンは記憶位置の値をまずチエツク
し、こののち、この値がプログラムの予期したものと同
じである場合のみこの値を修正する。通常はこの値が先
にフエツチした値と同じである。記憶部内の値がプログ
ラムの予期したものと異なるならば、その位置では修正
が行われず、かわりにその位置の現行の値が汎用レジス
タに転送されて、プログラムがループ・バツクして再試
行できるようにされる。ＣＳインストラクシヨンの実行
の間、他のＣＰＵはその特定の位置にアクセスできな
い。
し、こののち、この値がプログラムの予期したものと同
じである場合のみこの値を修正する。通常はこの値が先
にフエツチした値と同じである。記憶部内の値がプログ
ラムの予期したものと異なるならば、その位置では修正
が行われず、かわりにその位置の現行の値が汎用レジス
タに転送されて、プログラムがループ・バツクして再試
行できるようにされる。ＣＳインストラクシヨンの実行
の間、他のＣＰＵはその特定の位置にアクセスできな
い。
ダブル・ワードより大きな共通記憶領域を更新すべきと
きには、特別のインターロツクを行つて、単一のプログ
ラムのみが一時に共通領域を更新するのを確実にする必
要がある。このような領域はシリアルに再利用可能なリ
ソース（シリアル・リユーザル・リソース、ＳＲＲ）と
呼ぶ。一般的にリストの更新、またはリストの走査でさ
え、リストのロツクなしに安全に行うことはできない。
しかしながら、ＣＳインストラクシヨンは所定の制限的
な場合において、ロツク／アンロツク機能を実現し、競
合を解消するに足る十分の待ち行列を提供する。ＬＩＦ
Ｏの態様でもＦＩＦＯの態様でもそうである。ロツク／
アンロツク機能は任意の複合構成のＳＲＲの更新用のイ
ンターロツク機構として用いることができる。
きには、特別のインターロツクを行つて、単一のプログ
ラムのみが一時に共通領域を更新するのを確実にする必
要がある。このような領域はシリアルに再利用可能なリ
ソース（シリアル・リユーザル・リソース、ＳＲＲ）と
呼ぶ。一般的にリストの更新、またはリストの走査でさ
え、リストのロツクなしに安全に行うことはできない。
しかしながら、ＣＳインストラクシヨンは所定の制限的
な場合において、ロツク／アンロツク機能を実現し、競
合を解消するに足る十分の待ち行列を提供する。ＬＩＦ
Ｏの態様でもＦＩＦＯの態様でもそうである。ロツク／
アンロツク機能は任意の複合構成のＳＲＲの更新用のイ
ンターロツク機構として用いることができる。
ロツク／アンロツク機能はＳＲＲに関連した「ヘツダ」
を用いる点に基礎を置く。ヘツダはＳＲＲの状態を決定
する共通開始点であり（フリーのときも使用中のとき
も）、また競合時に要求を待ち行列処理するにも用いら
れる。競合はＷＡＩＴおよびＰＯＳＴを用いて解消され
る、一般的プログラミング手法では、ＳＲＲのロツクに
遭遇したプログラムが「壁にマークを付ける」必要があ
り、これでそのプログラムがウエイトしているＥＣＢ
（イベント制御ブロツク）のアドレスを表示する。「ア
ンロツク・プログラム」はこのマークを見てＥＣＢをポ
スト（ＰＯＳＴ）する。これによつてウエイト・プログ
ラムの継続が許容される。多くの場合、個々のＳＲＲを
用いるすべてのプログラムはＬＩＦＯ待ち行列スキーム
またはＦＩＦＯスキームを用いなければならず、２つは
定まつていない。より複雑な待ち行列が必要なときに
は、文献３７０ＸＡにおいて、ＳＲＲ用の待ち行列を２
つの方法のいずれかでデロツクすることが提案されてい
る。
を用いる点に基礎を置く。ヘツダはＳＲＲの状態を決定
する共通開始点であり（フリーのときも使用中のとき
も）、また競合時に要求を待ち行列処理するにも用いら
れる。競合はＷＡＩＴおよびＰＯＳＴを用いて解消され
る、一般的プログラミング手法では、ＳＲＲのロツクに
遭遇したプログラムが「壁にマークを付ける」必要があ
り、これでそのプログラムがウエイトしているＥＣＢ
（イベント制御ブロツク）のアドレスを表示する。「ア
ンロツク・プログラム」はこのマークを見てＥＣＢをポ
スト（ＰＯＳＴ）する。これによつてウエイト・プログ
ラムの継続が許容される。多くの場合、個々のＳＲＲを
用いるすべてのプログラムはＬＩＦＯ待ち行列スキーム
またはＦＩＦＯスキームを用いなければならず、２つは
定まつていない。より複雑な待ち行列が必要なときに
は、文献３７０ＸＡにおいて、ＳＲＲ用の待ち行列を２
つの方法のいずれかでデロツクすることが提案されてい
る。
指摘したように、ＣＳおよびＣＤＳインストラクシヨン
は極めてうまく用いられてきた。これらインストラクシ
ヨンによつてユーザは共有データへのアクセスないし、
後続の処理のためのヘツダを得ることができる。他のユ
ーザがデータをアクセスしているときにアドレス位置へ
のアクセスを禁止する要請はＣＳインストラクシヨンに
よつて解消された。しかしながらＣＳおよびＣＤＳイン
ストラクシヨンは単一ワードないしダブル・ワードにし
か適用できない。
は極めてうまく用いられてきた。これらインストラクシ
ヨンによつてユーザは共有データへのアクセスないし、
後続の処理のためのヘツダを得ることができる。他のユ
ーザがデータをアクセスしているときにアドレス位置へ
のアクセスを禁止する要請はＣＳインストラクシヨンに
よつて解消された。しかしながらＣＳおよびＣＤＳイン
ストラクシヨンは単一ワードないしダブル・ワードにし
か適用できない。
これに対し、後述するとおり、この発明のＣＯＭＰＡＲ
Ｅ ＡＮＤ ＳＷＡＰ ＤＩＳＪＯＩＮＴ（ＣＳＤ）イ
ンストラクシヨンおよびＣＯＭＰＡＲＥ ＡＮＤ ＬＯ
ＡＤ（ＣＡＬ）インストラクシヨンによれば２つの隣接
していないワード（または拡張版ではダブル・ワード）
を参照することができる。
Ｅ ＡＮＤ ＳＷＡＰ ＤＩＳＪＯＩＮＴ（ＣＳＤ）イ
ンストラクシヨンおよびＣＯＭＰＡＲＥ ＡＮＤ ＬＯ
ＡＤ（ＣＡＬ）インストラクシヨンによれば２つの隣接
していないワード（または拡張版ではダブル・ワード）
を参照することができる。
Ｃ．発明が解決しようとする課題 この発明の目的は、マルチ・プロセツシング・ユニット
ないしユーザがリストにアンロツク状態で非同期にアク
セスできるようにすることである。
ないしユーザがリストにアンロツク状態で非同期にアク
セスできるようにすることである。
またこの発明の他の目的はリストの一貫性を維持しなが
ら上述の動作を保障することである。
ら上述の動作を保障することである。
またこの発明の他の目的はそのようなリストの維持を効
率良く行えるようにすることである。
率良く行えるようにすることである。
またこの発明のさらに他の目的は上述の目的を実現でき
るコンピユータ・インストラクシヨンを提供することで
ある。
るコンピユータ・インストラクシヨンを提供することで
ある。
Ｄ．課題を解決するための手段 この発明では以上の目的を達成するために、新たなコン
ピユータ・インストラクシヨンすなわち「ＣＯＭＰＡＲ
Ｅ ＡＮＤ ＳＷＡＰ ＤＩＳＪＯＩＮＴ」および「Ｃ
ＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤ」を生成する新しい手
順を採用する。このようなメモリ・アクセス・シリアル
化インストラクシヨンを用いることにより、任意の個数
の付加および削除がこれらリストを無制約に非同期に操
作を行える。またこの発明では多重プロセツサが、リス
トの一貫性を維持したままでＦＩＦＯまたはＬＩＦＯ型
の時系列リストのエレメントの付加や削除を行える。用
語「ＤＩＳＪＯＩＮＴ」（解体）は処理されている２つ
のワードが記憶領域で隣り合つていないことを意味す
る。「ＤＩＳＪＯＩＮＴ」の同義語は「ＤＩＳＣＯＮＴ
ＩＧＵＯＵＳ」である。
ピユータ・インストラクシヨンすなわち「ＣＯＭＰＡＲ
Ｅ ＡＮＤ ＳＷＡＰ ＤＩＳＪＯＩＮＴ」および「Ｃ
ＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤ」を生成する新しい手
順を採用する。このようなメモリ・アクセス・シリアル
化インストラクシヨンを用いることにより、任意の個数
の付加および削除がこれらリストを無制約に非同期に操
作を行える。またこの発明では多重プロセツサが、リス
トの一貫性を維持したままでＦＩＦＯまたはＬＩＦＯ型
の時系列リストのエレメントの付加や削除を行える。用
語「ＤＩＳＪＯＩＮＴ」（解体）は処理されている２つ
のワードが記憶領域で隣り合つていないことを意味す
る。「ＤＩＳＪＯＩＮＴ」の同義語は「ＤＩＳＣＯＮＴ
ＩＧＵＯＵＳ」である。
新たなＣＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤ（ＣＡＬ）イ
ンストラクシヨンは第１レジスタのデータをアドレス位
置と比較し、比較結果が一致であれば第２位置からの値
を第２レジスタにフエツチする。インストラクシヨンの
利点は、１の位置の内容が変わつていないことに応じて
他の位置の値をフエツチできるという点である。
ンストラクシヨンは第１レジスタのデータをアドレス位
置と比較し、比較結果が一致であれば第２位置からの値
を第２レジスタにフエツチする。インストラクシヨンの
利点は、１の位置の内容が変わつていないことに応じて
他の位置の値をフエツチできるという点である。
新たなＣＯＭＰＡＲＥ ＡＮＤ ＳＷＡＰ ＤＩＳＪＯ
ＩＮＴ（ＣＳＤ）によれば、ＣＯＭＰＡＲＥ ＡＮＤ
ＳＷＡＰ（ＣＳ）インストラクシヨンやＣＯＭＰＡＲＥ
ＤＯＵＢＬＥ ＡＮＤ ＳＷＡＰ（ＣＤＳ）インスト
ラクシヨンと違つて、プログラムが２つの隣り合つてい
ないワードやダブル・ワードを参照できる。すなわち２
つの隣接していない記憶位置を同時に更新させることが
できる。多くの実際的な場合では２つの隣接しないエン
テイテイを扱う必要があるので、これは実益がある。
ＩＮＴ（ＣＳＤ）によれば、ＣＯＭＰＡＲＥ ＡＮＤ
ＳＷＡＰ（ＣＳ）インストラクシヨンやＣＯＭＰＡＲＥ
ＤＯＵＢＬＥ ＡＮＤ ＳＷＡＰ（ＣＤＳ）インスト
ラクシヨンと違つて、プログラムが２つの隣り合つてい
ないワードやダブル・ワードを参照できる。すなわち２
つの隣接していない記憶位置を同時に更新させることが
できる。多くの実際的な場合では２つの隣接しないエン
テイテイを扱う必要があるので、これは実益がある。
Ｅ．実施例 まず２つの新しいインストラクシヨンＣＯＭＰＡＲＥ
ＡＮＤ ＬＯＡＤ、ＣＯＭＰＡＲＥ ＡＮＤ ＳＷＡＰ
ＤＩＳＪＯＩＮＴおよびその操作について説明する。
インストラクシヨンは文献３７０ＸＡのフオーマツトを
用いて記載するが、その方法はより多くのアプリケーシ
ヨンを有する。
ＡＮＤ ＬＯＡＤ、ＣＯＭＰＡＲＥ ＡＮＤ ＳＷＡＰ
ＤＩＳＪＯＩＮＴおよびその操作について説明する。
インストラクシヨンは文献３７０ＸＡのフオーマツトを
用いて記載するが、その方法はより多くのアプリケーシ
ヨンを有する。
先の説明は第１図およびＣＡＬフオーマツトとの関連で
示される。
示される。
ＣＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤインストラクシヨン
によつて特定されるアドレス可能データはつぎのとおり
である。
によつて特定されるアドレス可能データはつぎのとおり
である。
２値ビツト０−７のオペレーシヨン・コードはデコード
されてＣＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤインストラク
シヨンであることを示す。４つの異なるオペランドはイ
ンストラクシヨンの残りの部分のアドレス情報により特
定される。５つの２値ビツト８−１１（Ｒ１によつて表
示）をオペランド１を含む汎用レジスタを特定する。２
値ビツト１２−１５（Ｒ３によつて表示）は処理された
データまたはオペランド３を含む汎用レジスタを特定す
る。２値ビツト１６−１９（Ｂ２によつて表示）は、所
定のベース・アドレス情報を含む汎用レジスタを特定す
る。インストラクシヨンのビツト２０−２１（Ｄ２によ
つて表示）をこのベース・アドレス情報に付加して共有
記憶のアドレス位置を特定する。２値ビツト３２−３５
（Ｂ４によつて表示）も所定のベース・アドレス情報を
含む汎用レジスタを特定する。ビツト３６−４７（Ｄ４
によつて表示）をこのベース・アドレス情報に付加して
共有記憶のアドレス位置を特定する。
されてＣＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤインストラク
シヨンであることを示す。４つの異なるオペランドはイ
ンストラクシヨンの残りの部分のアドレス情報により特
定される。５つの２値ビツト８−１１（Ｒ１によつて表
示）をオペランド１を含む汎用レジスタを特定する。２
値ビツト１２−１５（Ｒ３によつて表示）は処理された
データまたはオペランド３を含む汎用レジスタを特定す
る。２値ビツト１６−１９（Ｂ２によつて表示）は、所
定のベース・アドレス情報を含む汎用レジスタを特定す
る。インストラクシヨンのビツト２０−２１（Ｄ２によ
つて表示）をこのベース・アドレス情報に付加して共有
記憶のアドレス位置を特定する。２値ビツト３２−３５
（Ｂ４によつて表示）も所定のベース・アドレス情報を
含む汎用レジスタを特定する。ビツト３６−４７（Ｄ４
によつて表示）をこのベース・アドレス情報に付加して
共有記憶のアドレス位置を特定する。
第１図のブロツク３０において、ＣＯＭＰＡＲＥ ＶＡ
ＬＵＥはオペランド１（Ｒ１），ＣＯＭＰＡＲＥ ＬＯ
ＣＡＴＩＯＮはオペランド２（Ｄ２（Ｂ２））、ＦＥＴ
ＣＨ ＶＡＬＵＥはオペランド３（Ｒ３）そしてＦＥＴ
ＣＨ ＬＯＣＡＴＩＯＮはオペランド４（Ｄ４（Ｂ
４））である。待ち行列操作と関連して検討するよう
に、２つの不連続ないし非隣接のエレメントはたとえば
リストのヘツドおよびリスト中の他のエレメントであ
る。
ＬＵＥはオペランド１（Ｒ１），ＣＯＭＰＡＲＥ ＬＯ
ＣＡＴＩＯＮはオペランド２（Ｄ２（Ｂ２））、ＦＥＴ
ＣＨ ＶＡＬＵＥはオペランド３（Ｒ３）そしてＦＥＴ
ＣＨ ＬＯＣＡＴＩＯＮはオペランド４（Ｄ４（Ｂ
４））である。待ち行列操作と関連して検討するよう
に、２つの不連続ないし非隣接のエレメントはたとえば
リストのヘツドおよびリスト中の他のエレメントであ
る。
記憶領域の第２オペランド位置のフル・ワードＤ２（Ｂ
２）は第１図のブロツク３２に示すようにＲ１の第１オ
ペランドと比較される。両者が等しければ、プログラム
が第３オペランドすなわち記憶領域中の第４オペランド
Ｄ４（Ｂ４）によつて定められる位置のフル・ワードを
レジスタ中へとフエツチする。これはブロツク３４に示
すようにベース／デイスプレースメントとして行う。ブ
ロツク４０に示すように条件コードＣＣはゼロに設定さ
れる。
２）は第１図のブロツク３２に示すようにＲ１の第１オ
ペランドと比較される。両者が等しければ、プログラム
が第３オペランドすなわち記憶領域中の第４オペランド
Ｄ４（Ｂ４）によつて定められる位置のフル・ワードを
レジスタ中へとフエツチする。これはブロツク３４に示
すようにベース／デイスプレースメントとして行う。ブ
ロツク４０に示すように条件コードＣＣはゼロに設定さ
れる。
判別ブロツク３２では、第２オペランド位置のフル・ワ
ードが第１オペランドと等しくなれば、第１オペランド
は第２オペランドと等しくされ、第３オペランドは不変
とする。ブロツク３６に示す通りである。第４オペラン
ドは使用されず、条件コード（ＣＣ）は１に設定され
る。ブロツク３８に示すとおりである。
ードが第１オペランドと等しくなれば、第１オペランド
は第２オペランドと等しくされ、第３オペランドは不変
とする。ブロツク３６に示す通りである。第４オペラン
ドは使用されず、条件コード（ＣＣ）は１に設定され
る。ブロツク３８に示すとおりである。
Ｒ１およびＲ３は各々任意の一般レジスタ手段を表わ
す。第２および第４オペランドはワード境界で指定され
た記憶領域中のフル・ワードである。
す。第２および第４オペランドはワード境界で指定され
た記憶領域中のフル・ワードである。
第２オペランドが第１オペランドに等しくないなら、ア
クセス例外処理は第４オペランドに対しては認識されな
い（換言すれば第４オペランドに対して参照がなされな
い）。
クセス例外処理は第４オペランドに対しては認識されな
い（換言すれば第４オペランドに対して参照がなされな
い）。
記憶領域の第２オペランドＤ２（Ｂ２）がＲ１中の第１
オペランドと等しいとき、他のＣＰＵは第２オペランド
がフエツチされてから第４オペランドがフエツチされる
までの間第２オペランドにアクセスすることができな
い。この種のステツプを通常記憶アクセス・シリアル化
と呼ぶ。
オペランドと等しいとき、他のＣＰＵは第２オペランド
がフエツチされてから第４オペランドがフエツチされる
までの間第２オペランドにアクセスすることができな
い。この種のステツプを通常記憶アクセス・シリアル化
と呼ぶ。
各オペランドに関するシリアル化はステツプ３２におい
て、値が当該位置からフエツチされる前および処理が完
了したのちに実行される。ＣＰＵの操作は当該ＣＰＵの
先行する記憶アクセスが終了し（チヤネルや他のＣＰＵ
が監視する）、さらに第２オペランドがフエツチされる
まで遅延される。第１オペランドと第２オペランドとの
比較結果が等しいというものであれば、第４オペランド
（Ｄ４）Ｂ４がフエツチされる。当該ＣＰＵは後続のイ
ンストラクシヨンやそのオペランドを、ＣＡＬインスト
ラクシヨンの実行が完了するまでアクセスしない。
て、値が当該位置からフエツチされる前および処理が完
了したのちに実行される。ＣＰＵの操作は当該ＣＰＵの
先行する記憶アクセスが終了し（チヤネルや他のＣＰＵ
が監視する）、さらに第２オペランドがフエツチされる
まで遅延される。第１オペランドと第２オペランドとの
比較結果が等しいというものであれば、第４オペランド
（Ｄ４）Ｂ４がフエツチされる。当該ＣＰＵは後続のイ
ンストラクシヨンやそのオペランドを、ＣＡＬインスト
ラクシヨンの実行が完了するまでアクセスしない。
条件コード（ＣＣ）結果： ０：第１および第２オペランドが等しく、第３オペラン
ドを第４オペランドで交換した。
ドを第４オペランドで交換した。
１：第１および第２オペランドが等しくない。第１オペ
ランドを第２オペランドで交換した。第３および第４オ
ペランドは不変。
ランドを第２オペランドで交換した。第３および第４オ
ペランドは不変。
２：・・・ ３：・・・ プログラム例外処理 ・アクセス（オペランド２および４をフエツチして記
憶） ・オペレーシヨン 第２図において、ＣＳＤ処理は全般的にブロツク５０で
開始され、第１および第２オペランドを比較し、つぎに
所定の条件下で第３および第４オペランドを比較する。
第１オペランドＲ１および記憶領域の第２オペランドＤ
２（Ｂ２）は判別ブロツク５２において比較される。こ
れらが等しければＲ３中の第３オペランドおよび記憶領
域の第４オペランドＤ４（Ｂ４）が判別ブロツク５８に
おいて比較される。さらにこれらが等しければ、Ｒ１＋
１オペランド（Replace Value １）が第２オペランド
位置（Location １）にストアされ、Ｒ３＋１オペラン
ド（Replace Value ２）が第４オペランド位置にスト
アされる。これはブロツク６４に示すとおりである。条
件コードＣＣはブロツク６６に示すようにゼロに設定さ
れる。
憶） ・オペレーシヨン 第２図において、ＣＳＤ処理は全般的にブロツク５０で
開始され、第１および第２オペランドを比較し、つぎに
所定の条件下で第３および第４オペランドを比較する。
第１オペランドＲ１および記憶領域の第２オペランドＤ
２（Ｂ２）は判別ブロツク５２において比較される。こ
れらが等しければＲ３中の第３オペランドおよび記憶領
域の第４オペランドＤ４（Ｂ４）が判別ブロツク５８に
おいて比較される。さらにこれらが等しければ、Ｒ１＋
１オペランド（Replace Value １）が第２オペランド
位置（Location １）にストアされ、Ｒ３＋１オペラン
ド（Replace Value ２）が第４オペランド位置にスト
アされる。これはブロツク６４に示すとおりである。条
件コードＣＣはブロツク６６に示すようにゼロに設定さ
れる。
第１オペランドＲ１および第２オペランドＤ２（Ｂ２）
が等しくなければ、ブロツク５４において第２オペラン
ドを第１オペランドに転送する。第１および第２オペラ
ンドが等しく、かつ第３および第４オペランドが等しく
なければ（ブロツク５８）、ブロツク６０に示すように
第４オペランドが第３オペランドに転送される。条件コ
ードＣＣはブロツク６２に示すように２に設定される。
が等しくなければ、ブロツク５４において第２オペラン
ドを第１オペランドに転送する。第１および第２オペラ
ンドが等しく、かつ第３および第４オペランドが等しく
なければ（ブロツク５８）、ブロツク６０に示すように
第４オペランドが第３オペランドに転送される。条件コ
ードＣＣはブロツク６２に示すように２に設定される。
Ｒ１およびＲ３は各々一般的レジスタの奇偶ぺアを表わ
し、偶数番のレジスタを指示する。Ｒ１＋１およびＲ３
＋１はペアの奇数番のレジスタを表わす。第２オペラン
ドＤ２（Ｂ２）および第４オペランドＤ４（Ｂ４）は記
憶領域のワードである。
し、偶数番のレジスタを指示する。Ｒ１＋１およびＲ３
＋１はペアの奇数番のレジスタを表わす。第２オペラン
ドＤ２（Ｂ２）および第４オペランドＤ４（Ｂ４）は記
憶領域のワードである。
第１および第２オペランドが等しくないという比較結果
の場合、第２オペランドは不変であり、第４オペランド
はアクセスされない。第３および第４オペランドが等し
くないという比較結果の場合、第２および第４オペラン
ドは不変である。第１および第２オペランドが等しくな
いなら、第４オペランドに対するアクセス例外処理は認
識されない。
の場合、第２オペランドは不変であり、第４オペランド
はアクセスされない。第３および第４オペランドが等し
くないという比較結果の場合、第２および第４オペラン
ドは不変である。第１および第２オペランドが等しくな
いなら、第４オペランドに対するアクセス例外処理は認
識されない。
ブロツク５２および５８での双方の比較結果が等しいこ
とを示すときには、他のＣＰＵが第２オペランド位置ま
たは第４オペランド位置にアクセスするが、対応するオ
ペランドが比較用にフエツチされてから、記憶されるま
での間、許されない。
とを示すときには、他のＣＰＵが第２オペランド位置ま
たは第４オペランド位置にアクセスするが、対応するオ
ペランドが比較用にフエツチされてから、記憶されるま
での間、許されない。
各オペランド位置に関するシリアル化は各オペランドが
ブロツク５２および５８でフエツチされるまえに実行さ
れ、またブロツク６８で処理が終了したのち再び実行さ
れる。ＣＰＵの記憶領域への先行するアクセスがすべて
完了し（チヤネルや他のＣＰＵが監視する）、第２オペ
ランドがフエツチされるまで（ブロツク５２）、ＣＰＵ
操作が遅延される。第１および第２オペランドが等しけ
れば、第４オペランドがフエツチされる（ブロツク５
８）。ＣＤＳインストラクシヨンの実行が完了するまで
ＣＰＵは後続のインストラクシヨンやそのオペランドを
アクセスしない。結果としての値があつたとしてもそれ
を供給するのも同じである（これはチヤネルや他のＣＰ
Ｕに監視される。
ブロツク５２および５８でフエツチされるまえに実行さ
れ、またブロツク６８で処理が終了したのち再び実行さ
れる。ＣＰＵの記憶領域への先行するアクセスがすべて
完了し（チヤネルや他のＣＰＵが監視する）、第２オペ
ランドがフエツチされるまで（ブロツク５２）、ＣＰＵ
操作が遅延される。第１および第２オペランドが等しけ
れば、第４オペランドがフエツチされる（ブロツク５
８）。ＣＤＳインストラクシヨンの実行が完了するまで
ＣＰＵは後続のインストラクシヨンやそのオペランドを
アクセスしない。結果としての値があつたとしてもそれ
を供給するのも同じである（これはチヤネルや他のＣＰ
Ｕに監視される。
第２および第４オペランドはワード境界に指示されてい
る。Ｒ１およびＲ３フイールドは偶数レジスタを指示す
る。そうでなければ指定例外を認識する。
る。Ｒ１およびＲ３フイールドは偶数レジスタを指示す
る。そうでなければ指定例外を認識する。
ＣＣ結果： ０：第１および第２オペランドが等しく、かつ第３およ
び第４オペランドが等しい。第２および第４オペランド
が置き換えられている。
び第４オペランドが等しい。第２および第４オペランド
が置き換えられている。
１：第１および第２オペランドは等しくない。第１オペ
ランドは第２オペランドで置き換えられている。第３お
よび第４オペランドは不変。
ランドは第２オペランドで置き換えられている。第３お
よび第４オペランドは不変。
２：第１および第２オペランドは等しいが、第３および
第４オペランドは等しくない。第３オペランドは第４オ
ペランドで置き換えられている。第１および第４オペラ
ンドは不変。
第４オペランドは等しくない。第３オペランドは第４オ
ペランドで置き換えられている。第１および第４オペラ
ンドは不変。
３：・・・ プログラム例外処理 ・アクセス（オペランド２および４をフエツチして記
憶） ・指定（Specification） ・オペレーシヨン さてつぎに以上のインストラクシヨンを用いてどのよう
に時系列リストないし待ち行列を操作するかについて説
明する。待ち行列はヘツド・ポインタおよびテイル・ポ
インタを有するものとして定義される。エレメントは待
ち行列のテイルに付加され、ヘツドから取り出される。
第３図は二重ヘツド待ち行列からエレメントを取り出す
場合を示す。既述のとおり、待ち行列はＱ ＨＥＡＤお
よびＱ ＴＡＩＬを有する。ここでＱ ＨＥＡＤは待ち
行列中の最も新しい要素をポインタし、Ｑ ＴＡＩＬは
待ち行列中の最も古い要素をポイントする。実線は操作
前のリストを示す。図示の待ち行列エレメントがＡ、
Ｂ、Ｃの順で付加され、Ａが削除されるとすると、Ｑ
ＨＥＡＤポインタは破線で示すようにエレメントＢをポ
イントしなければならない。
憶） ・指定（Specification） ・オペレーシヨン さてつぎに以上のインストラクシヨンを用いてどのよう
に時系列リストないし待ち行列を操作するかについて説
明する。待ち行列はヘツド・ポインタおよびテイル・ポ
インタを有するものとして定義される。エレメントは待
ち行列のテイルに付加され、ヘツドから取り出される。
第３図は二重ヘツド待ち行列からエレメントを取り出す
場合を示す。既述のとおり、待ち行列はＱ ＨＥＡＤお
よびＱ ＴＡＩＬを有する。ここでＱ ＨＥＡＤは待ち
行列中の最も新しい要素をポインタし、Ｑ ＴＡＩＬは
待ち行列中の最も古い要素をポイントする。実線は操作
前のリストを示す。図示の待ち行列エレメントがＡ、
Ｂ、Ｃの順で付加され、Ａが削除されるとすると、Ｑ
ＨＥＡＤポインタは破線で示すようにエレメントＢをポ
イントしなければならない。
この発明の方法は第４Ａ図および第４Ｂ図ならびに表II
のインストラクシヨンの一部で示され、これは待ち行列
解除に関する。
のインストラクシヨンの一部で示され、これは待ち行列
解除に関する。
待ち行列はヘツドおよびテイル・ポインタを有するもの
として定義されている。エレメントは待ち行列のテイル
に付加され、ヘツドから取り出される。
として定義されている。エレメントは待ち行列のテイル
に付加され、ヘツドから取り出される。
この発明によれば、何ら修正を加えることなく、Ｑ Ｈ
ＥＡＤのポインタの置き換えおよびエレメントＡの次の
ポインタの置き換えが可能になる。この結果、リストの
操作の間にリストの一貫性が保持される。
ＥＡＤのポインタの置き換えおよびエレメントＡの次の
ポインタの置き換えが可能になる。この結果、リストの
操作の間にリストの一貫性が保持される。
リスト操作 つぎに、多重プロセスがエレメントを同時に待ち行列解
除および待ち行列挿入でき、しかもイベント制御ブロツ
ク（ＥＣＢ）でロックしたり待ち状態をとつたりする必
要がなく、さらに待ち行列が改ざんされないことを保障
することについて説明しよう。これはＣＡＬおよびＣＳ
Ｄインストラクシヨンをプログラムに挿入することによ
つて達成される。
除および待ち行列挿入でき、しかもイベント制御ブロツ
ク（ＥＣＢ）でロックしたり待ち状態をとつたりする必
要がなく、さらに待ち行列が改ざんされないことを保障
することについて説明しよう。これはＣＡＬおよびＣＳ
Ｄインストラクシヨンをプログラムに挿入することによ
つて達成される。
待ち行列はヘツドおよびテイル・ポインタを有するもの
として定義される。エレメントは待ち行列のテイルに付
加され、ヘツドから取り出される。機能的に定義は第３
図および第４図の二重ヘツド待ち行列と同じである。以
下のインストラクシヨンの説明については文献３５７０
ＸＡを参照されたい。列の説明はすでに表１について行
つた。
として定義される。エレメントは待ち行列のテイルに付
加され、ヘツドから取り出される。機能的に定義は第３
図および第４図の二重ヘツド待ち行列と同じである。以
下のインストラクシヨンの説明については文献３５７０
ＸＡを参照されたい。列の説明はすでに表１について行
つた。
第４Ａ図において、プログラムＤＥＱＵＥＵＥは二重ヘ
ツドＦＩＦＯリストからこの発明にしたがつてエレメン
トを除去する。プログラムの第１のステツプはブロツク
２３１に示すように、転送すべきものがあれば自動的に
エレメントをＱ ＨＥＡＤおよびＱ ＴＡＩＬに転送す
ことである。プログラムはブロツク２３２に進んで待ち
行列が空かどうかを判別する。答えがイエスであればブ
ロツク２３３に示すようにＤＥＱＵＥＵＥプログラムを
終了する。答えがノーであれば、ＣＯＭＰＡＲＥ ＡＮ
Ｄ ＬＯＡＤルーチンをブロツク２３４で用いて最も古
い作業エレメントからつぎのポインタの値をフエツチす
る。この間Ｑ ＨＥＡＤが変わらないようにする。
ツドＦＩＦＯリストからこの発明にしたがつてエレメン
トを除去する。プログラムの第１のステツプはブロツク
２３１に示すように、転送すべきものがあれば自動的に
エレメントをＱ ＨＥＡＤおよびＱ ＴＡＩＬに転送す
ことである。プログラムはブロツク２３２に進んで待ち
行列が空かどうかを判別する。答えがイエスであればブ
ロツク２３３に示すようにＤＥＱＵＥＵＥプログラムを
終了する。答えがノーであれば、ＣＯＭＰＡＲＥ ＡＮ
Ｄ ＬＯＡＤルーチンをブロツク２３４で用いて最も古
い作業エレメントからつぎのポインタの値をフエツチす
る。この間Ｑ ＨＥＡＤが変わらないようにする。
プロセスのつぎのステツプはブロツク２３５においてＱ
ＨＥＡＤポインタが変わつたかどうかを判別すること
である。答えがイエスであれば、ルーチンは判別ブロツ
ク２３２に戻つてつぎのエレメントの待ち行列解除を試
みる。
ＨＥＡＤポインタが変わつたかどうかを判別すること
である。答えがイエスであれば、ルーチンは判別ブロツ
ク２３２に戻つてつぎのエレメントの待ち行列解除を試
みる。
ＣＡＬを用いて、Ｑ ＨＥＡＤによつてアドレスされる
チエインの第１のエレメントからつぎのポインタの値を
フエツチする。この操作は、同じＣＡＬや待ち行列解除
操作を実行する他のプロセスによつてエレメントが除去
されていないことを保障しながら実行される。Ｑ ＨＥ
ＡＤが変化したことが判別されると（これは何かがリス
トからエレメントを除去したことを示す）、上述の次検
索位置をプログラムが再フエツチしなければならない。
実際Ｑ ＨＥＡＤが変化しなつたなら、プログラムは有
効な次ポインタ位置を保持している。
チエインの第１のエレメントからつぎのポインタの値を
フエツチする。この操作は、同じＣＡＬや待ち行列解除
操作を実行する他のプロセスによつてエレメントが除去
されていないことを保障しながら実行される。Ｑ ＨＥ
ＡＤが変化したことが判別されると（これは何かがリス
トからエレメントを除去したことを示す）、上述の次検
索位置をプログラムが再フエツチしなければならない。
実際Ｑ ＨＥＡＤが変化しなつたなら、プログラムは有
効な次ポインタ位置を保持している。
処理のつぎのステツプはブロツク２３４によつてフエツ
チされたつぎのポインタをフエツチすることである。つ
ぎのポインタがゼロでなかつたら、１個以上のエレメン
トが存在し（ブロツク２３６）、プログラムはＱ ＨＥ
ＡＤ用のリプレースメント値をブロツク２３４でフエツ
チしたつぎのポインタに設定する。ブロツク２３７にお
いてプログラムはＱ ＴＡＩＬ値をＱ ＨＥＡＤと等し
い値に設定する。Ｑ ＨＥＡＤおよびＱ ＴＡＩＬが変
化しないようにしながら（自動的に）、Ｑ ＨＥＡＤお
よびＱ ＴＡＩＬをゼロに置き換える。
チされたつぎのポインタをフエツチすることである。つ
ぎのポインタがゼロでなかつたら、１個以上のエレメン
トが存在し（ブロツク２３６）、プログラムはＱ ＨＥ
ＡＤ用のリプレースメント値をブロツク２３４でフエツ
チしたつぎのポインタに設定する。ブロツク２３７にお
いてプログラムはＱ ＴＡＩＬ値をＱ ＨＥＡＤと等し
い値に設定する。Ｑ ＨＥＡＤおよびＱ ＴＡＩＬが変
化しないようにしながら（自動的に）、Ｑ ＨＥＡＤお
よびＱ ＴＡＩＬをゼロに置き換える。
他方Ｑ ＨＥＡＤ又はＱ ＴＡＩＬが変化したなら、プ
ログラムはブロツク２３２に戻り、Ｑ ＨＥＡＤを再び
テストする。Ｑ ＨＥＡＤおよびＱ ＴＡＩＬが変化し
なかつたなら、プログラムはゼロまたは待ち行列解除し
たエレメントのアドレスを伴つて終了する（ブロツク２
４３）。
ログラムはブロツク２３２に戻り、Ｑ ＨＥＡＤを再び
テストする。Ｑ ＨＥＡＤおよびＱ ＴＡＩＬが変化し
なかつたなら、プログラムはゼロまたは待ち行列解除し
たエレメントのアドレスを伴つて終了する（ブロツク２
４３）。
第４Ｂ図のブロツク２４０では、Ｑ ＨＥＡＤおよび次
のフイールドが変化しないことを確かめながら、プログ
ラムがＱ ＨＥＡＤの値を待ち行列中の２番目に古いエ
レメントと交換し、つぎのポインタの値をゼロに設定す
る。図に示すように、これはＣＯＭＰＡＲＥ ＡＮＤ
ＳＷＡＰ ＤＩＳＪＯＩＮＴ（ＣＳＤ）インストラクシ
ヨンによつて行う。判別ブロツク２４１において、Ｑ
ＨＥＡＤポインタが変化したかどうかが判別される。ポ
インタが変化していればプログラムは判別ブロツク２３
２に戻つて待ち行列が空かどうかの判別を行う。Ｑ Ｈ
ＥＡＤポインタが変わつていなければプログラムは判別
ブロツク２４２に進む。待ち行列解除ルーチンはブロツ
ク２４３で終了する。このように終了して、ゼロまたは
待ち行列解除エレメントのアドレスを得る。
のフイールドが変化しないことを確かめながら、プログ
ラムがＱ ＨＥＡＤの値を待ち行列中の２番目に古いエ
レメントと交換し、つぎのポインタの値をゼロに設定す
る。図に示すように、これはＣＯＭＰＡＲＥ ＡＮＤ
ＳＷＡＰ ＤＩＳＪＯＩＮＴ（ＣＳＤ）インストラクシ
ヨンによつて行う。判別ブロツク２４１において、Ｑ
ＨＥＡＤポインタが変化したかどうかが判別される。ポ
インタが変化していればプログラムは判別ブロツク２３
２に戻つて待ち行列が空かどうかの判別を行う。Ｑ Ｈ
ＥＡＤポインタが変わつていなければプログラムは判別
ブロツク２４２に進む。待ち行列解除ルーチンはブロツ
ク２４３で終了する。このように終了して、ゼロまたは
待ち行列解除エレメントのアドレスを得る。
判別ブロツク２３６において、待ち行列中にそれまでに
たつた１つのエレメントしかなく、かつ転送時からＱ
ＨＥＡＤおよびＱ ＴＡＩＬが変化していないなら、両
者をゼロにセツトする。プログラムはつぎに判別ブロツ
ク２３８に進みＱ ＨＥＡＤおよびＱ ＴＡＩＬが変化
したかどうかを判別する。Ｑ ＨＥＡＤおよびＱ ＴＡ
ＩＬが変化していればプロセスはステツプ２３２に戻り
待ち行列が空かどうか判別する。しかしＱ ＨＥＡＤお
よびＱ ＴＡＩＬが変化していないなら、プログラムは
終了して待ち行列解除されたエレメントのアドレスを生
じる。
たつた１つのエレメントしかなく、かつ転送時からＱ
ＨＥＡＤおよびＱ ＴＡＩＬが変化していないなら、両
者をゼロにセツトする。プログラムはつぎに判別ブロツ
ク２３８に進みＱ ＨＥＡＤおよびＱ ＴＡＩＬが変化
したかどうかを判別する。Ｑ ＨＥＡＤおよびＱ ＴＡ
ＩＬが変化していればプロセスはステツプ２３２に戻り
待ち行列が空かどうか判別する。しかしＱ ＨＥＡＤお
よびＱ ＴＡＩＬが変化していないなら、プログラムは
終了して待ち行列解除されたエレメントのアドレスを生
じる。
ＣＳＤを用いると、ＤＥＱＵＥＵＥプログラムは、Ｑ
ＨＥＡＤの値とチエインの第１のエレメントのつぎのポ
インタ位置の値とを、両者の値が変化しないことを確か
めながら変換する。つぎにＣＳＤは、Ｑ ＨＥＡＤおよ
びつぎのポインタが変化しないことを確かめながら、こ
れらの値をチエインの第２のエレメントのアドレスおよ
びゼロとそれぞれ変換する。
ＨＥＡＤの値とチエインの第１のエレメントのつぎのポ
インタ位置の値とを、両者の値が変化しないことを確か
めながら変換する。つぎにＣＳＤは、Ｑ ＨＥＡＤおよ
びつぎのポインタが変化しないことを確かめながら、こ
れらの値をチエインの第２のエレメントのアドレスおよ
びゼロとそれぞれ変換する。
Ｑ ＨＥＡＤポインタが変化したか、またはつぎのポイ
ンタが変化したなら、これは、他のエレメントがチエイ
ンに付加されたか、あるいは、ＣＡＬおよびＣＳＤの間
に他の何者かが待ち行列からエレメントを除去したこと
を示す。この時点で、プログラムは先に示したようにＣ
ＡＬインストラクシヨンを再実行する。ポインタがいず
れも変わらなかつたなら、待ち行列の第１のエレメント
が除去されて処理が成功する。
ンタが変化したなら、これは、他のエレメントがチエイ
ンに付加されたか、あるいは、ＣＡＬおよびＣＳＤの間
に他の何者かが待ち行列からエレメントを除去したこと
を示す。この時点で、プログラムは先に示したようにＣ
ＡＬインストラクシヨンを再実行する。ポインタがいず
れも変わらなかつたなら、待ち行列の第１のエレメント
が除去されて処理が成功する。
第５図は二重ヘツド待ち行列へのエレメントの付加を示
す。待ち行列はＱ ＨＥＡＤおよびＱ ＴＡＩＬを有す
るものとして定義される。ここでＱ ＨＥＡＤは待ち行
列中の最も古いエレメントをポインタし、Ｑ ＴＡＩＬ
は待ち行列中の最も新しいエレメントをポイントする。
図示の待ち行列においてＡ、Ｂ、Ｃの順でエレメントが
付加されるとすると、Ｑ ＴＡＩＬポインタはエレメン
トＮをポイントするよう変わらなければならず、またエ
レメントＣからのポインタ（Ｃの次のポインタ）もエレ
メントＮをポイントするように変わらなければならな
い。
す。待ち行列はＱ ＨＥＡＤおよびＱ ＴＡＩＬを有す
るものとして定義される。ここでＱ ＨＥＡＤは待ち行
列中の最も古いエレメントをポインタし、Ｑ ＴＡＩＬ
は待ち行列中の最も新しいエレメントをポイントする。
図示の待ち行列においてＡ、Ｂ、Ｃの順でエレメントが
付加されるとすると、Ｑ ＴＡＩＬポインタはエレメン
トＮをポイントするよう変わらなければならず、またエ
レメントＣからのポインタ（Ｃの次のポインタ）もエレ
メントＮをポイントするように変わらなければならな
い。
第６図はこの発明の待ち行列挿入を示すフローチヤート
である。この場合の事例は第５図に示すように自重ヘツ
ドＦＩＦＯリストにエレメントを付加するというもので
ある。第６図のフローチヤートに関連するインストラク
シヨンの詳細なセツトは表２の第２の部分に示してあ
る。
である。この場合の事例は第５図に示すように自重ヘツ
ドＦＩＦＯリストにエレメントを付加するというもので
ある。第６図のフローチヤートに関連するインストラク
シヨンの詳細なセツトは表２の第２の部分に示してあ
る。
ブロツク１００に示すように、Ｑ ＨＥＡＤおよびＱ
ＴＡＩＬポインタは自動的にフエツチされる。判別ブロ
ツク１０２ではＱ ＨＥＡＤをテストして待ち行列が空
かどうかを判別する。待ち行列が空でないならばプログ
ラムはブロツク１０６に進み、新しいエレメントが非空
のリストに付加される。Ｑ ＴＡＩＬのアドレスおよび
新エレメントのアドレスが確立される。何らかのレジス
タ手段を用いて最後のエレメントが待ち行列中に最後の
エレメントとしてとどまつているかどうかを確かめる。
プログラムはつぎに判別ブロツク１０８に進み、ここで
Ｑ ＴＡＩＬまたはつぎのポインタが変化しているかど
うかを判別する。両者が変化していなければ、プログラ
ムは待ち行列挿入ルーチンから出る。Ｑ ＴＡＩＬまた
はつぎのポインタが変化しているならば、プログラムは
ブロツク１００に戻り、その時点で再び開始する。Ｑ
ＴＡＩＬもつぎのポインタも変わつていないなら、待ち
行列に新エレメントが成功裡に付加されたことであり、
プログラムはブロツク１１２に示すように待ち行列挿入
から出る。
ＴＡＩＬポインタは自動的にフエツチされる。判別ブロ
ツク１０２ではＱ ＨＥＡＤをテストして待ち行列が空
かどうかを判別する。待ち行列が空でないならばプログ
ラムはブロツク１０６に進み、新しいエレメントが非空
のリストに付加される。Ｑ ＴＡＩＬのアドレスおよび
新エレメントのアドレスが確立される。何らかのレジス
タ手段を用いて最後のエレメントが待ち行列中に最後の
エレメントとしてとどまつているかどうかを確かめる。
プログラムはつぎに判別ブロツク１０８に進み、ここで
Ｑ ＴＡＩＬまたはつぎのポインタが変化しているかど
うかを判別する。両者が変化していなければ、プログラ
ムは待ち行列挿入ルーチンから出る。Ｑ ＴＡＩＬまた
はつぎのポインタが変化しているならば、プログラムは
ブロツク１００に戻り、その時点で再び開始する。Ｑ
ＴＡＩＬもつぎのポインタも変わつていないなら、待ち
行列に新エレメントが成功裡に付加されたことであり、
プログラムはブロツク１１２に示すように待ち行列挿入
から出る。
ブロツク１０８の判別結果が、Ｑ ＴＡＩＬまたは最後
のエレメントのつぎのポインタがフエツチ以後に変化し
ていることを示すなら、プロセスはブロツク１００で再
び開始されなければならない。答えがノーであれば、待
ち行列挿入処理は終了してプログラムはブロツク１１２
で終わる。
のエレメントのつぎのポインタがフエツチ以後に変化し
ていることを示すなら、プロセスはブロツク１００で再
び開始されなければならない。答えがノーであれば、待
ち行列挿入処理は終了してプログラムはブロツク１１２
で終わる。
ブロツク１０２において、待ち行列が空であれば、プロ
グラムはブロツク１０４に進む。新エレメントを付加
し、Ｑ ＨＥＡＤおよびＱ ＴＡＩＬポインタの双方が
新エレメントをポイントする（ブロツク１０４）。フロ
ーチヤートに示すように自動的に実行される。
グラムはブロツク１０４に進む。新エレメントを付加
し、Ｑ ＨＥＡＤおよびＱ ＴＡＩＬポインタの双方が
新エレメントをポイントする（ブロツク１０４）。フロ
ーチヤートに示すように自動的に実行される。
ブロツク１１０において、Ｑ ＨＥＡＤおよびＱ ＴＡ
ＩＬが、新エレメントをポイントしたあとで、変化した
かどうかを判別する。判別ブロツク１１０で示すように
それらが変化していないならプログラムは待ち行列挿入
ルーチンから出る。Ｑ ＴＡＩＬまたは最後のエレメン
トのつぎのポインタが変化しているなら、プログラムは
ブロツク１００に戻り、手続を再開する。
ＩＬが、新エレメントをポイントしたあとで、変化した
かどうかを判別する。判別ブロツク１１０で示すように
それらが変化していないならプログラムは待ち行列挿入
ルーチンから出る。Ｑ ＴＡＩＬまたは最後のエレメン
トのつぎのポインタが変化しているなら、プログラムは
ブロツク１００に戻り、手続を再開する。
繰り返していえば、ブロツク１０６はＣＳＤインストラ
クシヨンを表れす。Ｑ ＴＡＩＬがエレメントＣをポイ
ントする間、ＣＳＤインストラクシヨンがレジスタ・オ
ペランド１を位置オペランド３と比較することが保障さ
れる。両者が等しければプログラムは位置オペランド３
の値をレジスタ・オペランド２の値で置き換える。両者
が等しくなれば、レジスタ・オペランド１は位置オペラ
ンド３の値を取つて条件コードを設定する。
クシヨンを表れす。Ｑ ＴＡＩＬがエレメントＣをポイ
ントする間、ＣＳＤインストラクシヨンがレジスタ・オ
ペランド１を位置オペランド３と比較することが保障さ
れる。両者が等しければプログラムは位置オペランド３
の値をレジスタ・オペランド２の値で置き換える。両者
が等しくなれば、レジスタ・オペランド１は位置オペラ
ンド３の値を取つて条件コードを設定する。
ＣＳＤインストラクシヨンがＣＳやその改良版であるＣ
ＯＭＰＡＲＥ ＤＯＵＢＬＥ ＡＮＤ ＳＷＡＰインス
トラクシヨンとどこが違うか留意されたい。ＣＳおよび
ＣＤＳは１つの位置を比較して置き換える。１つの位置
のフル・ワードないしダブル・ワードについてである。
ＣＳＤおよびその変種のＣＤＳＤは条件付きで２つの隣
り合わないエレメントを置き換える。２つの位置のフル
・ワードないしダブル・ワードについてである。ＣＳは
たつた１つの記憶位置を比較してそれを条件付きで置き
換えるが、ＣＳＤは１つの位置を比較し、最初の位置の
比較結果が一致であることを条件に第２の位置を比較す
る。２つの比較がともに一致であれば、双方の位置を置
き換える。これによつて、待ち行列またはスタツクおよ
びリストの最初のエレメントの双方を同時に操作でき、
しかもリストの一貫性を維持できる（リストの一貫性が
ないとはたとえばエレメントが損失してしまうというこ
とである）。
ＯＭＰＡＲＥ ＤＯＵＢＬＥ ＡＮＤ ＳＷＡＰインス
トラクシヨンとどこが違うか留意されたい。ＣＳおよび
ＣＤＳは１つの位置を比較して置き換える。１つの位置
のフル・ワードないしダブル・ワードについてである。
ＣＳＤおよびその変種のＣＤＳＤは条件付きで２つの隣
り合わないエレメントを置き換える。２つの位置のフル
・ワードないしダブル・ワードについてである。ＣＳは
たつた１つの記憶位置を比較してそれを条件付きで置き
換えるが、ＣＳＤは１つの位置を比較し、最初の位置の
比較結果が一致であることを条件に第２の位置を比較す
る。２つの比較がともに一致であれば、双方の位置を置
き換える。これによつて、待ち行列またはスタツクおよ
びリストの最初のエレメントの双方を同時に操作でき、
しかもリストの一貫性を維持できる（リストの一貫性が
ないとはたとえばエレメントが損失してしまうというこ
とである）。
スタツク（ＬＩＦＯリスト）のリスト操作 第７図はスタツクからのエレメントの除去を示す。この
場合処理はエレメントＡをスタツクから除去する。
場合処理はエレメントＡをスタツクから除去する。
スタツクはＴＯＳ（TOS of Stack pointer）を有するも
のとして定義される。
のとして定義される。
ＴＯＳに示されるスタツクおよびエレメントＡ、Ｂおよ
びＣ（Ｃ、Ｂ、Ａの順でスタツクにプツシユされる）を
考えると、スタツクから第１のエレメントを除去（ない
しポツプ）するにはスタツクのトツプの値をＢすなわち
スタツクの第２のエレメントのアドレスで置き換えてＡ
のアドレスの値を戻す必要がある。
びＣ（Ｃ、Ｂ、Ａの順でスタツクにプツシユされる）を
考えると、スタツクから第１のエレメントを除去（ない
しポツプ）するにはスタツクのトツプの値をＢすなわち
スタツクの第２のエレメントのアドレスで置き換えてＡ
のアドレスの値を戻す必要がある。
この発明では、エレメントに対して多重プロセスが同時
にポツプ（スタツクからの除去）処理を行うようにで
き、そのためにとくにロツクを保持するとかＥＣＢを待
つとかがなく、またスタツクがこわれてしまうおそれも
ない。この手法は表１および第８図に示す。
にポツプ（スタツクからの除去）処理を行うようにで
き、そのためにとくにロツクを保持するとかＥＣＢを待
つとかがなく、またスタツクがこわれてしまうおそれも
ない。この手法は表１および第８図に示す。
第８図はＬＩＦＯリストからエレメントを除去する場合
のフローチヤートである。第１のステツプでブロツク７
２に示すようにスタツクのトツプ（ＴＯＳ）のアドレス
がフエツチされる。判別ブロツク７４においてスタツク
のトツプをテストしてスタツクが空なのかまたは値を有
するのかを判別する。スタツクが空であればＰＯＰプロ
グラムが７６で終了する。除去するものが何もないから
である。
のフローチヤートである。第１のステツプでブロツク７
２に示すようにスタツクのトツプ（ＴＯＳ）のアドレス
がフエツチされる。判別ブロツク７４においてスタツク
のトツプをテストしてスタツクが空なのかまたは値を有
するのかを判別する。スタツクが空であればＰＯＰプロ
グラムが７６で終了する。除去するものが何もないから
である。
しかし、スタツクが空でないから、ブロツク７８のＣＯ
ＭＰＡＲＥ ＡＮＤ ＬＯＡＤ（ＣＡＬ）インストラク
シヨンを用いて、スタツクのトツプ（ＴＯＳ）が変化し
ないことを確かめながら最新エレメントからつぎのポイ
ンタの値をフエツチする。ＴＯＳが変化したなら（ブロ
ツク８２で判別）、プログラムは判別ブロツク７４に戻
る。
ＭＰＡＲＥ ＡＮＤ ＬＯＡＤ（ＣＡＬ）インストラク
シヨンを用いて、スタツクのトツプ（ＴＯＳ）が変化し
ないことを確かめながら最新エレメントからつぎのポイ
ンタの値をフエツチする。ＴＯＳが変化したなら（ブロ
ツク８２で判別）、プログラムは判別ブロツク７４に戻
る。
ＴＯＳが変化しなつたなら、プログラムはＣＯＭＰＡＲ
Ｅ ＡＮＤ ＳＷＡＰ（ＣＳＤ）インストラクシヨンへ
とブロツク８６に示すように進む。ＴＯＳのリプレース
メント値をブロツク７８において、ＣＡＬインストラク
シヨンによりフエツチしたつぎのポインタの値に設定す
る。ブロツク８６においてつぎのフイールド用のリプレ
ースメント値をゼロに設定する。ＴＯＳおよびつぎのフ
イールドが変化しないことを確かめながら、ＴＯＳの値
をつぎのポインタの値で置き換え、つぎのポインタの値
をゼロで置き換える。これをＣＳＤインストラクシヨン
で行う。
Ｅ ＡＮＤ ＳＷＡＰ（ＣＳＤ）インストラクシヨンへ
とブロツク８６に示すように進む。ＴＯＳのリプレース
メント値をブロツク７８において、ＣＡＬインストラク
シヨンによりフエツチしたつぎのポインタの値に設定す
る。ブロツク８６においてつぎのフイールド用のリプレ
ースメント値をゼロに設定する。ＴＯＳおよびつぎのフ
イールドが変化しないことを確かめながら、ＴＯＳの値
をつぎのポインタの値で置き換え、つぎのポインタの値
をゼロで置き換える。これをＣＳＤインストラクシヨン
で行う。
判別ブロツク７９においてＴＯＳポインタが変わつたか
どうかを判別する。答えがイエスなら、プログラムは判
別ブロツク７４に戻る。答えがノーであれば、ブロツク
８４においてつぎのポインタが変わつたかを判別する。
答えがイエスであれば、プログラムはＣＯＭＰＡＲＥ
ＡＮＤ ＳＷＡＰ ＤＩＳＪＯＩＮＴインストラクシヨ
ンに戻る。ブロツク８４での答えがノーであれば、ＰＯ
Ｐルーチンをブロツク８８で終了させる。プログラムが
終了してゼロまたはエレメントのアドレスが生じる。
どうかを判別する。答えがイエスなら、プログラムは判
別ブロツク７４に戻る。答えがノーであれば、ブロツク
８４においてつぎのポインタが変わつたかを判別する。
答えがイエスであれば、プログラムはＣＯＭＰＡＲＥ
ＡＮＤ ＳＷＡＰ ＤＩＳＪＯＩＮＴインストラクシヨ
ンに戻る。ブロツク８４での答えがノーであれば、ＰＯ
Ｐルーチンをブロツク８８で終了させる。プログラムが
終了してゼロまたはエレメントのアドレスが生じる。
Ｆ．発明の効果 以上説明したようにこの発明によればＣＯＭＰＡＲＥ
ＡＮＤ ＬＯＡＤインストラクシヨンを用いて１の位置
の内容が変わつていないことに応じて他の位置の値をフ
エツチすることができる。またＣＯＭＰＡＲＥ ＡＮＤ
ＳＷＡＰ ＤＩＳＪＯＩＮＴインストラクシヨンを用
いて、２つの隣接していない記憶位置を同時に更新する
ことができる。
ＡＮＤ ＬＯＡＤインストラクシヨンを用いて１の位置
の内容が変わつていないことに応じて他の位置の値をフ
エツチすることができる。またＣＯＭＰＡＲＥ ＡＮＤ
ＳＷＡＰ ＤＩＳＪＯＩＮＴインストラクシヨンを用
いて、２つの隣接していない記憶位置を同時に更新する
ことができる。
第１図はこの発明のＣＯＭＰＡＲＥ ＡＮＤ ＬＯＡＤ
インストラクシヨンの操作を示すフローチヤート、第２
図はこの発明のＣＯＭＰＡＲＥ ＡＮＤ ＳＷＡＰ Ｄ
ＩＳＪＯＩＮＴインストラクシヨンの操作を示すフロー
チヤート、第３図は二重ヘツド待ち行列ＦＩＦＯおよび
この発明によるリスト操作後の状態を示す図、第４Ａ図
および第４Ｂ図はこの発明によつて第３図の二重ヘツド
待ち行列からエレメントを削除する場合を説明するフロ
ーチヤート、第５図はこの発明によつて二重ヘツド待ち
行列にエレメントを付加する場合を示す図、第６図は第
５図のエレメントを待ち行列へ挿入する方法を示すフロ
ーチヤート、第７図はＬＩＦＯ待ち行列リストおよびこ
の発明によるリスト操作後の状態を示す図、第８図はこ
の発明によつて第７図のスタツクからエレメントを除去
する場合を説明するフローチヤートである。
インストラクシヨンの操作を示すフローチヤート、第２
図はこの発明のＣＯＭＰＡＲＥ ＡＮＤ ＳＷＡＰ Ｄ
ＩＳＪＯＩＮＴインストラクシヨンの操作を示すフロー
チヤート、第３図は二重ヘツド待ち行列ＦＩＦＯおよび
この発明によるリスト操作後の状態を示す図、第４Ａ図
および第４Ｂ図はこの発明によつて第３図の二重ヘツド
待ち行列からエレメントを削除する場合を説明するフロ
ーチヤート、第５図はこの発明によつて二重ヘツド待ち
行列にエレメントを付加する場合を示す図、第６図は第
５図のエレメントを待ち行列へ挿入する方法を示すフロ
ーチヤート、第７図はＬＩＦＯ待ち行列リストおよびこ
の発明によるリスト操作後の状態を示す図、第８図はこ
の発明によつて第７図のスタツクからエレメントを除去
する場合を説明するフローチヤートである。
Claims (6)
- 【請求項１】各々がメモリ内の同一のデータに共有アク
セスを必要とする複数のユーザを含むマルチタスク・デ
ータ処理システムにおいて、 前記メモリ内に格納された待ち行列から要素を除去する
方法であって、 前記待ち行列は該待ち行列内の最新要素を示すキュー・
テイルと該待ち行列内の最古の要素を示すキュー・ヘッ
ドに関連し、 各待ち行列要素は、前記待ち行列内の次の要素に対する
ポインタを含み、 Ａ）前記キュー・ヘッドの値を第１オペランドに格納す
るステップと、 Ｂ）前記キュー・ヘッドのアドレスを第２オペランドに
格納するステップと、 Ｃ）前記キュー・ヘッドによりアドレスされる第１要素
に格納された次の要素のポインタのアドレスを第４オペ
ランドに格納するステップと、 Ｄ）第１の所定のコンピュータ命令を実行する実行ステ
ップであって、 (a)前記第２オペランドにより特定される前記メモリの
位置へのアクセスをロックするステップと、 (b)前記第２オペランドにより特定されるメモリの内容
と前記第１オペランドを比較するステップと、 (c)前記比較が等しい場合には、前記第４オペランドに
より特定される前記次の要素のポインタを第３オペラン
ドにロードするステップと、 (d)前記第２オペランドにより特定される前記メモリ位
置のロックを解除するステップと、 (e)前記第４オペランドにより特定される前記次の待ち
行列要素のポインタのロードの成功または失敗を示すリ
ターン・コードをセットするステップと を有する実行ステップと、 Ｅ）前記リターン・コードが前記第１の所定のコンピュ
ータ命令実行の失敗を示している場合、Ａ）乃至Ｄ）ス
テップを繰り返すステップと、 Ｆ）前記リターン・コードが前記第１の所定のコンピュ
ータ命令実行の成功を示している場合、前記(c)ステッ
プにおいて得られた前記次の要素のポインタを用いて前
記待ち行列から前記最古の要素を除去するステップと を有する待ち行列から要素を除去する方法。 - 【請求項２】前記待ち行列から前記最古の要素を除去す
るステップが Ｇ）１以上のエレメントが前記待ち行列上に存在する場
合、第２の所定のコンピュータ命令を実行する第２の実
行ステップであって、 (f)前記第２及び第４オペランドにより特定される位置
の前記メモリへのアクセスをロックするステップと、 (g)前記第２オペランドにより特定される前記メモリ内
容と前記第１オペランドを比較するステップと、 (h)前記比較が等しい場合、前記第４オペランドにより
特定される前記メモリ内容と前記第３オペランドを比較
するステップと、 (i)(h)の比較もまた等しい場合、前記第２及び第４オペ
ランドにより特定される前記メモリ位置に新たな値を記
憶するステップと、 (j)前記第２及び第４オペランドにより特定される前記
メモリ位置におけるロックを解除するステップと を有する第２の実行ステップを さらに有する請求項１記載の待ち行列から要素を除去す
る方法。 - 【請求項３】前記第２のコンピュータ命令により前記第
２オペランドの前記メモリ内容と前記第１オペランドと
の比較が等しくない場合、前記第１オペランドを再ロー
ドし、前記Ｄ）乃至Ｇ）ステップを繰り返すステップを
さらに有する請求項２記載の待ち行列から要素を除去す
る方法。 - 【請求項４】前記第２のコンピュータ命令により前記第
４オペランドの前記メモリ内容と前記第３オペランドと
の比較が等しくない場合、前記第３オペランドを再ロー
ドし、前記Ｇ）ステップを繰り返すステップをさらに有
する請求項２記載の待ち行列から要素を除去する方法。 - 【請求項５】前記待ち行列に１の要素のみ存在する場
合、前記要素を取り去り、前記待ち行列が空であること
を示すために前記メモリ内の前記キュー・テイルの値と
前記キュー・ヘッドの値をセットするステップをさらに
有する請求項１記載の待ち行列から要素を除去する方
法。 - 【請求項６】各々がメモリ内の同一のデータに共有アク
セスを必要とする複数のユーザを含むマルチタスク・デ
ータ処理システムにおいて、 前記メモリ内に格納されたスタックから要素を除去する
方法であって、 前記スタックは該スタック内の最新要素を示すキュー・
テイルと該スタック内の最古の要素を示すキュー・ヘッ
ドに関連し、 各スタック要素は、前記スタック内の次の要素に対する
ポインタを含み、 Ａ）前記キュー・ヘッドの値を第１オペランドに格納す
るステップと、 Ｂ）前記キュー・ヘッドのアドレスを第２オペランドに
格納するステップと、 Ｃ）前記キュー・ヘッドによりアドレスされる第１要素
に格納された次の要素のポインタのアドレスを第４オペ
ランドに格納するステップと、 Ｄ）第１の所定のコンピュータ命令を実行する実行ステ
ップであって、 (a)前記第２オペランドにより特定される前記メモリの
位置へのアクセスをロックするステップと、 (b)前記第２オペランドにより特定されるメモリの内容
と前記第１オペランドを比較するステップと、 (c)前記比較が等しい場合には、前記第４オペランドに
より特定される前記次の要素のポインタを第３オペラン
ドにロードするステップと、 (d)前記第２オペランドにより特定される前記メモリ位
置のロックを解除するステップと、 (e)前記第４オペランドにより特定される前記次のスタ
ック要素のポインタのロードの成功または失敗を示すリ
ターン・コードをセットするステップと を有する実行ステップと、 Ｅ）前記リターン・コードが前記第１の所定のコンピュ
ータ命令実行の失敗を示している場合、Ａ）乃至Ｄ）ス
テップを繰り返すステップと、 Ｆ）前記リターン・コードが前記第１の所定のコンピュ
ータ命令実行の成功を示している場合、前記(c)ステッ
プにおいて得られた前記次の要素のポインタを用いて前
記スタックから前記最古の要素を除去するステップと を有するスタックから要素を除去する方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/264,289 US5081572A (en) | 1988-10-28 | 1988-10-28 | Manipulation of time-ordered lists and instructions therefor |
| US264289 | 1988-10-28 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02163835A JPH02163835A (ja) | 1990-06-25 |
| JPH0642204B2 true JPH0642204B2 (ja) | 1994-06-01 |
Family
ID=23005378
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1276178A Expired - Lifetime JPH0642204B2 (ja) | 1988-10-28 | 1989-10-25 | 待ち行列又はスタックから要素を除去する方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5081572A (ja) |
| EP (1) | EP0366585B1 (ja) |
| JP (1) | JPH0642204B2 (ja) |
| DE (1) | DE68926874D1 (ja) |
Families Citing this family (38)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0418447B1 (en) * | 1989-09-20 | 1995-01-18 | International Business Machines Corporation | Device for controlling the enqueuing and dequeuing operations of messages in a memory |
| JP2781092B2 (ja) * | 1991-11-06 | 1998-07-30 | 富士通株式会社 | システム間排他制御方式 |
| US5398330A (en) * | 1992-03-05 | 1995-03-14 | Seiko Epson Corporation | Register file backup queue |
| US5448708A (en) * | 1992-10-30 | 1995-09-05 | Ward; James P. | System for asynchronously delivering enqueue and dequeue information in a pipe interface having distributed, shared memory |
| US5673307A (en) * | 1994-02-17 | 1997-09-30 | Spectralink Corporation | Handoff method for indoor cellular phone system |
| US6247064B1 (en) * | 1994-12-22 | 2001-06-12 | Unisys Corporation | Enqueue instruction in a system architecture for improved message passing and process synchronization |
| US5893157A (en) * | 1997-05-28 | 1999-04-06 | International Business Machines Corporation | Blocking symbol control in a computer system to serialize accessing a data resource by simultaneous processor requests |
| US5895492A (en) * | 1997-05-28 | 1999-04-20 | International Business Machines Corporation | Processor associated blocking symbol controls for serializing the accessing of data resources in a computer system |
| US5956714A (en) * | 1997-08-13 | 1999-09-21 | Southwestern Bell Telephone Company | Queuing system using a relational database |
| US5895494A (en) * | 1997-09-05 | 1999-04-20 | International Business Machines Corporation | Method of executing perform locked operation instructions for supporting recovery of data consistency if lost due to processor failure, and a method of recovering the data consistency after processor failure |
| US6009261A (en) * | 1997-12-16 | 1999-12-28 | International Business Machines Corporation | Preprocessing of stored target routines for emulating incompatible instructions on a target processor |
| US6496975B1 (en) | 1999-10-15 | 2002-12-17 | International Business Machines Corporation | Method, system, and program for performing conditional program operations |
| US7000234B1 (en) | 2000-01-20 | 2006-02-14 | Sun Microsystems, Inc. | Maintaining a double-ended queue as a linked-list with sentinel nodes and delete flags with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive |
| AU2001227533A1 (en) * | 2000-01-20 | 2001-07-31 | Sun Microsystems, Inc. | Double-ended queue in a contiguous array with concurrent non-blocking insert andremove operations |
| US7539849B1 (en) * | 2000-01-20 | 2009-05-26 | Sun Microsystems, Inc. | Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive |
| WO2001080015A2 (en) | 2000-04-18 | 2001-10-25 | Sun Microsystems, Inc. | Concurrent shared object implemented using a linked-list with amortized node allocation |
| AU2001259089A1 (en) | 2000-04-18 | 2001-11-07 | Sun Microsystems, Inc. | Lock-free implementation of concurrent shared object with dynamic node allocation and distinguishing pointer value |
| US7117502B1 (en) * | 2000-11-10 | 2006-10-03 | Sun Microsystems, Inc. | Linked-list implementation of a data structure with concurrent non-blocking insert and remove operations |
| US7769791B2 (en) | 2001-01-12 | 2010-08-03 | Oracle America, Inc. | Lightweight reference counting using single-target synchronization |
| US7299242B2 (en) | 2001-01-12 | 2007-11-20 | Sun Microsystems, Inc. | Single-word lock-free reference counting |
| US6880071B2 (en) * | 2001-04-09 | 2005-04-12 | Sun Microsystems, Inc. | Selective signalling of later reserve location memory fault in compound compare and swap |
| WO2003060715A2 (en) * | 2002-01-11 | 2003-07-24 | Sun Microsystems, Inc. | Value recycling facility for multithreaded computations |
| US7836228B1 (en) | 2004-06-18 | 2010-11-16 | Oracle America, Inc. | Scalable and lock-free first-in-first-out queue implementation |
| US7395274B2 (en) * | 2002-07-16 | 2008-07-01 | Sun Microsystems, Inc. | Space- and time-adaptive nonblocking algorithms |
| US9052944B2 (en) | 2002-07-16 | 2015-06-09 | Oracle America, Inc. | Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms |
| US7293143B1 (en) | 2002-09-24 | 2007-11-06 | Sun Microsystems, Inc. | Efficient non-blocking k-compare-single-swap operation |
| US7814488B1 (en) | 2002-09-24 | 2010-10-12 | Oracle America, Inc. | Quickly reacquirable locks |
| US6938054B2 (en) * | 2002-11-25 | 2005-08-30 | International Business Machines Corporation | Systems, methods, and computer program products to optimize serialization when porting code to IBM S/390 UNIX system services from a UNIX system |
| US7424477B1 (en) | 2003-09-03 | 2008-09-09 | Sun Microsystems, Inc. | Shared synchronized skip-list data structure and technique employing linearizable operations |
| US10049127B1 (en) | 2003-12-19 | 2018-08-14 | Oracle America, Inc. | Meta-transactional synchronization |
| US8074030B1 (en) | 2004-07-20 | 2011-12-06 | Oracle America, Inc. | Using transactional memory with early release to implement non-blocking dynamic-sized data structure |
| US7703098B1 (en) | 2004-07-20 | 2010-04-20 | Sun Microsystems, Inc. | Technique to allow a first transaction to wait on condition that affects its working set |
| US7395382B1 (en) | 2004-08-10 | 2008-07-01 | Sun Microsystems, Inc. | Hybrid software/hardware transactional memory |
| US7711909B1 (en) | 2004-12-09 | 2010-05-04 | Oracle America, Inc. | Read sharing using global conflict indication and semi-transparent reading in a transactional memory space |
| US7577798B1 (en) | 2004-12-30 | 2009-08-18 | Sun Microsystems, Inc. | Space-adaptive lock-free queue using pointer-sized single-target synchronization |
| US7533221B1 (en) | 2004-12-30 | 2009-05-12 | Sun Microsystems, Inc. | Space-adaptive lock-free free-list using pointer-sized single-target synchronization |
| US7680986B1 (en) | 2004-12-30 | 2010-03-16 | Sun Microsystems, Inc. | Practical implementation of arbitrary-sized LL/SC variables |
| US9990240B2 (en) * | 2015-12-11 | 2018-06-05 | Successfactors, Inc. | Event handling in a cloud data center |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP5412300B2 (ja) | 2010-01-13 | 2014-02-12 | 東京窯業株式会社 | ガス吹き込みランス |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3886525A (en) * | 1973-06-29 | 1975-05-27 | Ibm | Shared data controlled by a plurality of users |
| US4136386A (en) * | 1977-10-06 | 1979-01-23 | International Business Machines Corporation | Backing store access coordination in a multi-processor system |
| US4320455A (en) * | 1978-01-09 | 1982-03-16 | Honeywell Information Systems Inc. | Queue structure for a data processing system |
| US4394727A (en) * | 1981-05-04 | 1983-07-19 | International Business Machines Corporation | Multi-processor task dispatching apparatus |
| US4482956A (en) * | 1982-11-04 | 1984-11-13 | International Business Machines Corporation | Parallel queueing method |
| US4604694A (en) * | 1983-12-14 | 1986-08-05 | International Business Machines Corporation | Shared and exclusive access control |
| US4584640A (en) * | 1984-06-27 | 1986-04-22 | Motorola, Inc. | Method and apparatus for a compare and swap instruction |
| US4673633A (en) * | 1984-06-28 | 1987-06-16 | Cooperbiomedical, Inc. | Method of determining cystic fibrosis ciliostatic factor |
| US4858116A (en) * | 1987-05-01 | 1989-08-15 | Digital Equipment Corporation | Method and apparatus for managing multiple lock indicators in a multiprocessor computer system |
| US4807111A (en) * | 1987-06-19 | 1989-02-21 | International Business Machines Corporation | Dynamic queueing method |
-
1988
- 1988-10-28 US US07/264,289 patent/US5081572A/en not_active Expired - Lifetime
-
1989
- 1989-09-12 DE DE68926874T patent/DE68926874D1/de not_active Expired - Lifetime
- 1989-09-12 EP EP89480142A patent/EP0366585B1/en not_active Expired - Lifetime
- 1989-10-25 JP JP1276178A patent/JPH0642204B2/ja not_active Expired - Lifetime
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP5412300B2 (ja) | 2010-01-13 | 2014-02-12 | 東京窯業株式会社 | ガス吹き込みランス |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0366585A3 (en) | 1992-06-03 |
| JPH02163835A (ja) | 1990-06-25 |
| EP0366585B1 (en) | 1996-07-24 |
| DE68926874D1 (de) | 1996-08-29 |
| EP0366585A2 (en) | 1990-05-02 |
| US5081572A (en) | 1992-01-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5081572A (en) | Manipulation of time-ordered lists and instructions therefor | |
| US6668291B1 (en) | Non-blocking concurrent queues with direct node access by threads | |
| US5442763A (en) | System and method for preventing deadlock in multiprocessor multiple resource instructions | |
| US4604694A (en) | Shared and exclusive access control | |
| US6145061A (en) | Method of management of a circular queue for asynchronous access | |
| US5287521A (en) | Method and apparatus for releasing and obtaining shared and exclusive locks | |
| JP2500101B2 (ja) | 共用変数の値を更新する方法 | |
| US7703098B1 (en) | Technique to allow a first transaction to wait on condition that affects its working set | |
| US4482956A (en) | Parallel queueing method | |
| US8074030B1 (en) | Using transactional memory with early release to implement non-blocking dynamic-sized data structure | |
| US5968157A (en) | Locking of computer resources | |
| US6230230B1 (en) | Elimination of traps and atomics in thread synchronization | |
| US7533138B1 (en) | Practical lock-free doubly-linked list | |
| JPH0231419B2 (ja) | ||
| US7389291B1 (en) | Implementing optimistic concurrent data structures | |
| JPH01303527A (ja) | 共有資源の管理方法 | |
| Braginsky et al. | CBPQ: High performance lock-free priority queue | |
| US11714801B2 (en) | State-based queue protocol | |
| US6976260B1 (en) | Method and apparatus for serializing a message queue in a multiprocessing environment | |
| US6094663A (en) | Method and apparatus for implementing atomic queues | |
| US6173375B1 (en) | Method for accessing a shared resource in a multiprocessor system | |
| CN113377549B (zh) | 一种队列数据控制方法、系统及队列数据结构 | |
| KR100470555B1 (ko) | 컴퓨터 자원의 로크방법 및 장치 | |
| US7047245B2 (en) | Processing system | |
| Skudlarek | Remarks on A methodology for implementing highly concurrent data |