JPH031268A - 計算機制御方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は複数プロセッサシステムの共有メモリのキュ
ー操作の排他的計算機制御方法に関するものである。

［従来の技術］ 電子計算機で問題解決を行う場合、通常電子計算機その
ものがｔｌ！−してくれるデータ型や制御構造は原始的
なものに限られる。

そのため、オペレーティングシステムや言語処理系など
が提供する機能の助けを借りて、ユーザは問題解決を効
率的に行うことを可能とするデータ構造やアルゴリズム
を、通常自ら設計しなければならない。

主記憶装置などの上にデータ構造を実現する方法の１つ
にリンク表現（Ｉｌｎｋ　Ｉｍｐｌｅｍｅｎｔａｔｉｏ
ｎ）がある。リンク表現は、あらかじめわかっている基
準番地から始２めて、必ずしも連続的ではなく、とびと
びに情報を並べ、それぞれの情報の場所に、関係する次
の情報の所在番地をもたせる。アクセスしたい情報の取
出しは、基準番地から始めて、ポインタ情報を次々とた
どることにより、必要な情報の所在番地を求めて行う。

０個以上の基本データの並びを、線形リスト（Ｉｌｎｅ
ａｒ　１１ｓｔ）と呼ぶ。線形リストで、データ要素の
挿入と削除が許される位置に制限を加えたリンク表現の
データ構造の１つがキュー（ｑｕｅｕｅ）である。

この説明において、キューとは持ち行列を管理するため
のデータ構造で、持ち行列要素と持ち行列要素をつなぐ
ためのキューヘッダから構成されるものとする。

第２図は従来のキューの構成例を示す説明図である。図
において、１ａはキューヘッダ、１ｂ１１Ｃは持ち行列
要素である。

第２図のリンク表現について説明する。キューヘッダ１
ａは持ち行列要素への前方向と後方向の２つのポインタ
で構成される。即ちその上段ポインタには持ち行列要素
１ｂの先頭アドレス値Ｂが、また下段ポインタには持ち
行列要素１ｃの先頭アドレス値Ｃがそれぞれ格納されて
いる。

持ち行列要素の先頭はキューヘッダから前方向でポイン
トされており、持ち行列要素の先頭にはキューヘッダへ
の後方向のポインタがおかれている。また、持ち行列要
素の後尾はキューヘッダから後方向でポイントされてお
り、持ち行列要素の後尾にはキューヘッダへの前方向の
ポインタがおかれている。

例えば、持ち行列要素１ｂは前方向ポインタ（フォワー
ドリンク）として要素ＩＣのアドレス値Ｃを、後方向ポ
インタ（バックワードリンク）としてキューヘッダ１ａ
のアドレス値Ａを持つ。

各持ち行列要素の２つのポインタから後ろの部分には、
持ち行列により管理される要素情報がおかれる。

キューの操作には、（１）サーチ、（２）持ち行列要素
の追加、（３）持ち行列要素の削除の３種類の操作があ
る。

サーチとはキューヘッダからキューのリンクをたどって
キューの内容を検索することである。

第３図は持ち行列要素の追加を示す説明図であり、１ａ
〜ＩＣは第２図と同一のものである。

第３図の■〜■により持ち行列要素（以下単に要素と省
略する）ｌｃを新規に追加する例を説明する。同図の■
はキューヘッダ１ａと要素１ｂとがリンクされ、要素１
ｃはまだリンクされていない状態を示す。■では要素１
ｃのフォワードリンクにキューヘッダ１ａのアドレス値
Ａを入れる。

■では要素１ｃのバックワードリンクに要素１ｂのアド
レス値Ｂを入れる。■では要素１ｂのフォワードリンク
に要素１ｃのアドレス値Ｃを入れる。

■ではキューヘッダｋａのバックワードリンクに要素１
ｃのアドレス値Ｃを入れる。

上記■〜■の順序によるキュー操作により要素の追加が
行われる。

第４図は持ち行列要素の削除を示す説明図であり、１ａ
〜１ｃは第３図と同一のものである。

第４図の■〜■によりキューの先頭の要素１ｂを削除す
る例を説明する。同図の■はキューヘッダ１ａと要素１
ｂ及び１ｃがリンクされている状態を示す。■では要素
１ｃのバックワードリンクにキューヘッダ１ａのアドレ
ス値Ａを入れる。■ではキューヘッダ１ａのフォワード
リンクに要素１Ｃのアドレス値Ｃを入れる。上記■〜■
の順序によるキュー操作により要素の削除が行われる。

以上がキューの操作であるが、キューに対する３つの操
作のうち追加および削除の処理はサーチ処理に比べ使用
頻度が高いため高速性が要求される。そのため従来でも
、単体で処理が行なえる要素追加用キュー操作命令、要
素削除用キュー操作命令等が提供されていた。

第５図は従来のキュー操作命令を使用したキュー操作の
フローチャートである。

第５図のフローチャートを説明する。複数プロセッサの
１つがキューの操作に対する排他制御を行なうためにメ
モリ中の特定領域を用い、ここにロックワードと呼ぶ情
報の書込みを行う。これを一般にロックをかけるか、ロ
ックするとか言い、ロックをかけてからキュー操作を行
い、キュー操作終了後ロックを解除している。このロッ
クワードをロックしたあとに、現在実行中のレベルより
高い割り込みが発生し、デッドロックが発生するのを防
止するため、第５図のステップＳ１において、マスク操
作命令により割り込みレベルを上げて上位割り込みの発
生を抑止する。次のステップＳ２において、ロックワー
ドを１にするため、ＣＳ　（Ｃｏｍｐａｒｅ　ａｎｄ　
５ｖａｐ）命令（後述）のオペランド１にロックワード
のアドレス値を、オペランド２に０を、オペランド３に
１をそれぞれ指定して命令を実行する（ロックをかける
）。この命令実行後、実行結果により命令の条件コード
は０または１に設定される。ステップＳ３において、命
令の条件コードの判定を行う。即ち命令の条件コードが
１であればロックワードは他のプロセッサによりロック
されているので再びステップＳ２に戻る。また条件コー
ドが０であれば次のステップＳ４へ進む。ステップＳ４
では２種類のキュー操作命令（追加又は削除）のいずれ
かを使用しキュー操作を行う。ステップＳ５において、
Ｃ８命令のオペランド１にロックワードのアドレス値を
、オペランド２に１を、オペランド３に０をそれぞれ指
定して命令を実行してロックワードをＯにする。

即ちロックを解除する。ステップＳ６において、マスク
操作命令により割り込みレベルを元に戻す。

上記説明の通り、従来は複数ステップの命令によりキュ
ー操作を行っていた。

第６図はロックワードを操作するＣ８命令の動作フロー
チャートである。またＣ８命令は、ロックワードのアド
レス、ロックワードと比較するデータ、ロックワードに
書き込むデータ、の３つのオペランドを持っている。

第６図のフローチャートを説明する。同図のステップＳ
ｌｌにおいて、オペランド１で指定されたアドレスに対
してインタロックをかける。ステップＳ１２において、
インタロツタが取れたかどうかの結果を検査する。イン
タロックが取れなかったときは、ステップＳｌｌに戻り
取れるまでインタロックをかけ続ける。インタロックが
取れたら、ステップＳ１３に移りその指定されたアドレ
スからデータを読込む。ステップＳ１４において、メモ
リから読込んだデータとＣ８命令のオペランド２とを比
較し、両データが一致のときはステップＳ１５へ、両デ
ータが不一致のときはステップＳｌＧへ移る。

ステップＳ１５では、両データが一致の場合なので、オ
ペランド３の内容をインタロックをかけたメモリに書込
み条件コードを０にする。ステップＳＩＧでは、両デー
タが不一致の場合なのでメモリから読込んだデータをオ
ペランド２に格納し条件コードを１にする。最後にステ
ップＳ１７において、インタロックを外し命令を終了す
る。

以上の説明がキュー操作命令を使用した従来の方法であ
る。

また上記を改良した例として、キュー操作にノ＼−ドウ
エア的にメモリをロックする命令を採用することにより
処理の高速化を図っている方法もあった。

［発明が解決しようとする課題］ 上記の第５図のフローチャートで説明したようなキュー
操作方法では、キ・）ニー操作において重要な操作であ
る追加と削除を行なうまでに多数の段階を通るため処理
が遅くなるという欠点があった。

またキュー操作中にハードウェアによりロックをかける
方法では次のような問題点がある。

第７図は従来のキュー操作中にハードウェアによりロッ
クする方法の説明図である。同図において、プロセッサ
（Ｂ）がキューのサーチを行なっている途中に、ステッ
プＳ２１において別のプロセッサ（Ａ）からハードウェ
アロックキュー操作命令が行なわれると、メモリがハー
ドウェア的にロックされるため、ステップＳ２２におい
てプロセッサ（Ｂ）のキューへのアクセスが不可となる
。そしてプロセッサ（＾）のキュー操作命令の終了後の
ステップＳ２３において、プロセッサ（Ｂ）から再びキ
ューアクセスを行なうと、キューがプロセッサ（Ａ）の
キュー操作命令により改変されているためプロセッサ（
Ｂ）のキューのサーチ処理が正しく行なわれないという
問題点がある。

この発明は、上記問題点を解決しあらゆるキュー操作に
ついて矛盾が生じず、また高速性を損なわない計算機制
御方法を提供することを目的とする。

［課題を解決するための手段］ この発明に係る計算機制御方法は、複数のブロセッサか
らの操作要求に対してインタロック手段を持つ共通メモ
リ装置を設け、自己のプロセッサが制０１１Ｉｌｌｉを
得るため前記インタロック手段を用いて共通メモリ装置
の指定領域を排他的に操作する命令と、前記インタロッ
ク手段を用いて共通メモリ装置の指定領域の検査を行い
前記制御権が取れるまで持ち合わせてから、キューへの
要素の追加を行なう命令及び同様にしてキューから要素
の削除を行なう命令と、前記各命令を複数のプロセッサ
がそれぞれ備え、複数のプロセッサがそれぞれ競合しな
いように共通メモリ装置のキュー操作を行なうものであ
る。

［作用］ この発明においては、複数のプロセッサからの操作要求
に対してインタロック手段を持つ共通メモリ装置を設け
、自己のプロセッサが制御権を得るため前記インタロッ
ク手段を用いて共通メモリ装置の指定領域を排他的に操
作するためインタクロツタをかける。インタロックがか
かったら前記共通メモリ装置の指定領域のロックワード
の検査を行ない、前記制御権が取れるまで持ち合わせて
から、キューへの要素の追加を行なう命令又は削除を行
なう命令を実行する。キュー要素の追加又は削除が終了
後前記インタロックを解除し、他のプロセッサがキュー
操作を行なえるようにする。

このような計算機制御方法により複数のプロセッサがそ
れぞれ競合しないように共通メモリ装置のキュー操作を
行なうことが可能となる。

［実施例コ 第１図はこの発明に係るロック付キュー操作命令の動作
フローチャートである。

第１図のフローチャートの説明をする。まずこのロック
付キュー操作命令が起動されると、同図のステップＳ３
１において、指定されたアドレスに対してインタロック
をかける。ステップＳ２１において、インタロックが取
れたかどうか結果を検査する。もしインタロックがかか
らなかったら、ステップＳ３１に戻り取れるまで繰り返
しインタロックをかけ続ける。インタロックがかかった
ら、ステップＳ３３に移りそのアドレスからデータを読
込み、このデータをロックワードとする。次のステップ
Ｓ３４においてロックワードを検査し、ロックワードが
０でなかったら処理対象のキューは他のプロセッサによ
り使用中であるので、ステップＳ３５においてインタロ
ックを解除して、本命令を再起動する。またロックワー
ドが０ならばステップ５３１１ｉにおいて、本来のキュ
ー操作である要素の追加または削除を行なう。

最後にステップＳ３７において、インタロックを解除し
て命令を終了する。

上記ステップＳ３１〜Ｓ３７の処理は、本発明に係る単
体のロツクイ・１キユ一操作命令により行われるため、
従来よりも高速で処理が実施される。

キューのサーチを行なう場合も前述のキュー操作命令で
使用するロックワードと同じロックワードを使い、Ｃ８
命令によりキューのサーチ処理の前後にロック操作を行
なう。

第８図は本発明のキュー操作命令中に他のプロセッサか
らのキューのサーチが発生した場合の説明図である。

第８図を説明する。同図においてプロセッサ（Ａ）は、
ステップＳ４１において本発明のキュー操作命令を実行
し、この命令実行中はメモリをインタロックする。この
ためプロセッサ（Ｂ）がステップＳ４２において行った
サーチ処理のためのＣ８命令は受は付けられない。プロ
セッサ（＾）がステップＳ４３において、キュー操作命
令を終了しインタロックを解除した後に、プロセッサ（
Ｂ）がステップＳ４４において行ったサーチ処理は受は
付けられる。以上の処理により、両プロセッサの処理は
正しく行なわれる。

第９図はキューのサーチ処理中に他のプロセッサからの
本発明のキュー操作命令が発生した場合の説明図である
。

第９図を説、明する。同図においてプロセッサ（Ｂ）は
ステップＳ５１において、キューのサーチをする前に、
Ｃ８命令によりロックワードを１にする。その後キュー
へのアクセス中にプロセッサ（Ａ）がステップＳ５２に
おいて、本発明のキュー操作命令を発行した場合、ロッ
クワードが０でないため本命令は実行されない。プロセ
ッサ（Ｂ）のキューのサーチが終了し、ステップＳ５３
におけるＣ８命令でロックワードが０になると、プロセ
ッサ（＾）はステップＳ５４においてキュー操作を行う
ことができる。このため両プロセッサの処理は矛盾なく
行なわれる。

以上説明したように本発明の、Ｃ８命令と共有のロック
ワードを検査することにより、キューへの要素の追加お
よびキューからの要素の削除を行なう単体のキュー操作
命令によれば、 （１）キューの要素の追加／削除処理の高速化（２）キ
ューのサーチ中の他のプロセッサによるキューの改変の
防止 の２点を同時に解決することができる。

［発明の効果］ 以上のようにこの発明によれば、複数のプロセッサから
の操作要求に対してインタロック手段を持つ共通メモリ
装置を設け、単体のキュー操作命令によって、自己のプ
ロセッサが制御権を得て前記インタロック手段を用いて
共通メモリ装置の指定領域を排他的に操作するためイン
タロックをかけ、次に前記共通メモリ装置の指定領域の
ロックワードの検査を行い、前記制御権が取れるまで持
ち合わせてから、キューへの要素の追加を行なう命令又
は削除を行なう命令を実行し、その後前記インタロック
を解除するようにしたので、キューの要素の追加又は削
除処理の高速化による性能向上の効果と、キューのサー
チ中に他のプロセッサによるキュー改変が無くなり、あ
らゆるキュー操作について矛盾が生ぜず操作の信頼性向
上の効果とが得られる。

【図面の簡単な説明】

第１図はこの発明に係るロック付キュー操作命令の動作
フローチャート、第２図は従来のキューの構造例を示す
説明図、第３図■〜■は持ち行列要素の追加を示す説明
図、第４図■〜■は持ち行列要素の削除を示す説明図、
ｍ５図は従来のキュー操作命令を使用したキュー操作の
フローチャート、第６図はロックワードを操作するＣ８
命令の動作フローチャート、第７図は従来のキュー操作
中に／Ｘ−ドウエアによりロックする方法の説明図、第
８図は本発明のキュー操作命令中に他のプロセッサから
のキューサーチ発生時の説明図、第９図はキューサーチ
処理中に他のプロセッサからの本発明のキュー操作命令
発生時の説明図である。 図において、１ａはキューヘッダ、１ｂ及びＩＣは持ち
行列要素、Ａ−Ｃはアドレス値である。 代理人　弁理士　鈴　木　敏　明（）２１この発明に係
るロックイ寸キュー、操午命宵の動作フローチャート第
　１　５η ０　：午ユ〜ヘツタ゛ Ａ　−Ｃニアドレス値 す、ｌｃ・持ち行列栗景 従来のキューの謂戊例を示す説明図 第２図 く ■ ■ ■ ■ ■ ■ 待ぢ行列要素の追７ＩＯを示財説明図 従来のキュー操作命令を使用したキュー揄信のフローチ
ャート第５図 ロッグワードを禄作ｊるＣ８命令の動作フローチャート
第６図 第 図

Claims (1)

【特許請求の範囲】
1. 複数のプロセッサからの操作要求に対してインタロック
   手段を持つ共通メモリ装置を設け、自己のプロセッサが
   制御権を得るため前記インタロック手段を用いて共通メ
   モリ装置の指定領域を排他的に操作する命令と、前記イ
   ンタロック手段を用いて共通メモリ装置の指定領域の検
   査を行い前記制御権が取れるまで持ち合わせてから、キ
   ューへの要素の追加を行なう命令及び同様にしてキュー
   から要素の削除を行なう命令と、前記各命令を複数のプ
   ロセッサがそれぞれ備え、複数のプロセッサがそれぞれ
   競合しないように共通メモリ装置のキュー操作を行なう
   ことを特徴とする計算機制御方法。