(57)【特許請求の範囲】
【請求項１】
各メモリ・ページが次のメモリ・ページへのリンク・エントリを含む少なくとも２つのメモリ・ページにわたってＮ個のデータ項目記憶位置で形成される循環待ち行列へデータ項目を順次書き込む作成者エンティティであって、ページ化メモリにおいて次に書き込まれるべき物理的記憶位置のアドレスを標示するインジケータを維持し、次に書き込まれるべき物理的記憶位置が所在するメモリ・ページの変更の発生に応じて、リンク・エントリにおいてポイントされている、次メモリ・ページのアドレスにインジケータを更新する書き込みアドレス管理機構と、上記書き込みアドレス管理機構によって維持されるインジケータによって標示される物理的記憶位置にデータ項目を書き込む待ち行列書き込み手段と、前記循環待ち行列を論理的に表現する、Ｎ個の記憶位置からなる循環連続的論理位置空間内の位置によって、当該インジケータによってアドレスが表示される物理的記憶位置に対応する、次にデータ項目が書き込まれるべき待ち行列記憶位置を示す作成者インデックスを記憶する作成者インデックス管理機構と、作成者エンティティの外部から供給され、Ｎ個の記憶位置からなる循環連続的論理位置空間内の位置によって、次にデータ項目が読み取られるべき待ち行列記憶位置を示す使用者インデックスと上記作成者インデックスを比較することによって、循環待ち行列の状態を判断する状態判断手段と、を備える作成者エンティティ。
【請求項２】
上記作成者インデックス管理機構が、上記作成者インデックスを記憶するための作成者インデックス・レジスタと、データ項目が上記待ち行列書き込み手段によって待ち行列に書き込まれる度毎に作成者インデックスをモジュロＮに基づいて増分させる手段と、を含む、請求項１に記載の作成者エンティティ。
【請求項３】
上記状態判断手段が、上記Ｎ個の記憶位置からなる循環連続的位置空間において使用者インデックスが示す位置の直前の位置を上記作成者インデックスが示す時、循環待ち行列がいっぱいであると判断する、請求項１に記載の作成者エンティティ。
【請求項４】
上記書き込みアドレス管理機構が、ページ化メモリにおいて次に書き込まれるべき記憶位置のアドレスを標示するインジケータを保持する書き込みアドレス・レジスタと、各データ項目の書き込みおよびメモリ・ページの変更の度毎に上記インジケータを更新する手段と、を含む、請求項１に記載の作成者エンティティ。
【請求項５】
各メモリ・ページが次のメモリ・ページへのリンク・エントリを含む少なくとも２つのメモリ・ページにわたってＮ個のデータ項目記憶位置で形成される循環待ち行列からデータ項目を順次読み取る使用者エンティティであって、ページ化メモリにおいて次に読み取られるべき物理的記憶位置のアドレスを標示するインジケータを維持し、次に読み取られるべき物理的記憶位置が所在するメモリ・ページの変更の発生に応じて、リンク・エントリにおいてポイントされている、次メモリ・ページのアドレスにインジケータを更新する読み取りアドレス管理機構と、上記読み取りアドレス管理機構によって維持されるインジケータによって標示される物理的記憶位置からデータ項目を読み取る待ち行列読み取り手段と、前記循環待ち行列を論理的に表現する、Ｎ個の記憶位置からなる循環連続的位置空間の位置によって、インジケータによってアドレスが表示される物理的記憶位置に対応する、次にデータ項目が読み取られるべき待ち行列記憶位置を示す使用者インデックスを維持する使用者インデックス管理機構と、使用者エンティティの外部から供給され、Ｎ個の記憶位置からなる循環連続的論理位置空間内の位置によって、次にデータ項目が書き込まれるべき待ち行列記憶位置を示す作成者インデックスと上記使用者インデックスを比較することによって、循環待ち行列の状態を判断する状態判断手段と、を備える使用者エンティティ。
【請求項６】
上記使用者インデックス管理機構が、上記使用者インデックスを記憶するための使用者インデックス・レジスタと、データ項目が上記待ち行列読み取り手段によって待ち行列から読み取られる度毎に使用者インデックスをモジュロＮに基づいて増分させる手段と、を含む、請求項５に記載の使用者エンティティ。
【請求項７】
上記状態判断手段が、Ｎ個の記憶位置からなる循環連続的論理位置空間内において上記作成者インデックスと上記使用者インデックスが示す位置が同一の場合、循環待ち行列が空であると判断する、請求項５に記載の使用者エンティティ。
【請求項８】
上記読み取りアドレス管理機構が、ページ化メモリにおいて次に読み取られるべき記憶位置のアドレスを標示するインジケータを保持する読み取りアドレス・レジスタと、各データ項目の読み取りおよびメモリ・ページの変更の度毎に上記インジケータを更新する手段と、を含む、請求項５に記載の使用者エンティティ。
【請求項９】
各メモリ・ページが次のメモリ・ページへのリンク・エントリを含む複数のメモリ・ページを持つページ化メモリと、上記メモリ・ページのそれぞれに形成される複数セグメントからなる待ち行列であって、上記セグメントの各々が対応するメモリ・ページに備わる複数のデータ項目記憶位置を含み、上記待ち行列全体で総計Ｎ個のデータ項目記憶位置が存在するように構成される循環待ち行列と、循環待ち行列の現在時書き込み位置に対応する循環待ち行列記憶位置にデータ項目を書き込む作成者エンティティと、循環待ち行列の現在時読み取り位置に対応する循環待ち行列記憶位置からデータ項目を読み取る使用者エンティティと、を備えるデータ処理システムであって、上記エンティティの各々が、関連するエンティティに対して、上記現在時書き込みまたは読み取り位置が上記ページ化メモリのどの物理的記憶位置に相当するかを示す物理的位置インジケータを記憶する第１レジスタと、関連するエンティティによるデータ項目の循環待ち行列への書き込みまたは循環待ち行列からの読み取りに応じて、上記物理的位置インジケータを更新し、また、現在時書き込みまたは読み取り位置に対応する物理的記憶位置が所在するメモリ・ページの変更の発生に応じて、リンク・エントリにおいてポイントされている、次メモリ・ページのアドレスに上記物理的位置インジケータを更新する第１更新手段と、前記循環待ち行列を論理的に表現する、Ｎ個の記憶位置からなる循環連続的論理位置空間内の位置によって、当該物理的位置インジケータによって示される物理的記憶位置に対応する、現在時書き込みまたは読み取り位置を標示する論理的位置インジケータを記憶する第２レジスタと、関連するエンティティによる、データ項目の循環待ち行列への書き込みまたは循環待ち行列からの読み取りに応じて、モジュロＮに基づいて上記論理的位置インジケータを増分する第２更新手段と、を含み、更に、作成者および使用者エンティティによって維持される論理的位置インジケータを使用して循環待ち行列の現在の状態に関する情報を判断する待ち行列状態手段を備える、データ処理システム。
【請求項１０】
上記待ち行列状態手段が、上記使用者エンティティにおいて上記論理的位置インジケータを比較して循環待ち行列が空である時点を判断するための待ち行列空き検出手段と、上記作成者エンティティにおいて上記論理的位置インジケータを比較して循環待ち行列がいっぱいである時点を判断するための待ち行列空きなし検出手段と、を備える、請求項９に記載のデータ処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ページ・メモリの形態で形成される循環待ち行列を使用して作成者エンティティと使用者エンティティの間のデータ転送のバッファリングを行うデータ処理システムに関するものである。
【０００２】
【従来の技術】
作成者エンティティと使用者エンティティの間におけるデータ転送をバッファリングするため循環待ち行列を使用することは周知のものである。図１には、連続ブロック・メモリ１１に形成されたＮ個のデータ項目記憶位置を含む循環待ち行列１０が示されている（ただし図１ではＮ＝７）。図１では、データ項目を持つ記憶位置は斜線が引かれ、一方、空の記憶位置はブランクのままとされている。この表記方法は本明細書全体にわたって使用される。データ項目を使用者エンティティ１３に渡すことを望む作成者エンティティ１２は、現在時書き込み位置ポインタ（すなわち「末尾」ポインタ）がポイントする循環待ち行列１０の記憶位置にデータ項目を書き込むことによって、それを実行する。末尾ポインタは作成者エンティティ１２によって維持され、データ項目が待ち行列１０に書き込まれる度毎に更新される。使用者エンティティ１３は、準備ができている場合、現在時ポインタ（すなわち「先頭」ポインタ）がポイントする待ち行列１０の記憶位置からデータ項目を読み取る。先頭ポインタは、使用者エンティティ１３によって維持され、待ち行列１０からデータ項目が読み取られる毎に更新される。
【０００３】
本発明において使用される「記憶位置」という用語は、データ項目を保持するために必要な大きさを持つ１つのメモリ領域を意味し、１つのアドレス可能なメモリ位置または複数のアドレス可能なメモリ位置に対応する。先頭および末尾ポインタの更新は、１つのデータ項目によって占有されるアドレス可能メモリ位置の数に対応する数量だけそれらポインタを増分することを伴う。待ち行列の最高位に達すると各ポインタは循環待ち行列の基底アドレスにリセットされる。
【０００４】
待ち行列記憶位置が同じメモリ・ブロック内で連続する形態をなす図１のような構成においては、待ち行列の状態（すなわち待ち行列にどれほど空きがあるか）を判断することは、待ち行列アドレス範囲として末尾ポインタから先頭ポインタを差し引くことによって判明することができるので、比較的簡単な問題である。上述のような構成は記憶位置がメモリ内で連続していることに依存するので、実際問題としては制約がある。今日のほとんどのコンピュータ・システムは、メモリは、（例えば４ＫＢの大きさである）ページとして知られる連続的メモリ・ブロックに構成されたページ・メモリ構成を使用する。大量のメモリ要求に応ずるためそのようなシステムが複数のメモリ・ページを割り当てる時、割り当てられるページが連続的である保証は一般的にない。この結果、図１のような単純な循環待ち行列構成は、単一のメモリ・ページに適合するような小さい待ち行列についてのみ使用することができるに過ぎず、図１の構成は、複数のメモリ・ページを必要とする比較的大きい待ち行列については使用することができない。そのような大きい待ち行列が必要な場合、異なるメモリ・ページにわたる待ち行列セグメントをリンクする適切な措置が講じられなければならない。
【０００５】
図２は、３つの別々のメモリ・ページにわたってセグメント２０を有する循環待ち行列１０を示す。図２に示されるように、各待ち行列セグメント２０は、当該メモリ・ページ内の最後のデータ項目位置の直後にある位置に記憶されるリンク・エントリ２１で終了する。このリンク・エントリ２１は、次の待ち行列セグメント２０の最初の記憶位置のメモリ・アドレスをポイントするアドレス・ポインタを含む。
【０００６】
作成者または使用者エンティティがリンク・エントリ２１に出会う度毎に、そのリンク・エントリにおいてポイントされているアドレスに末尾または先頭ポインタを適切に更新する。リンク・エントリの検出は、各セグメント位置に記憶される特別なフラグを使用してその位置がリンク・エントリを有しているか否かを標示することによって実施することができる。別の形態としては、作成者または使用者エンティティが待ち行列セグメント２０にあるデータ項目記憶位置の数を知っていれば、アクセスすることができる残りの記憶位置の通算数を保持して、この通算数がゼロに達する時、そのエンティティは次の位置がリンク・エントリを持つことを認識できる。
【０００７】
【発明が解決しようとする課題】
図２の待ち行列について待ち行列状態を判断するのは、待ち行列が単一のメモリ・ページで形成されている場合に比較して複雑である。待ち行列がいっぱいであるかまたは全く空である状態だけが必要とされるのであれば、先頭および末尾ポインタの両者が同一の位置をポイントしている時待ち行列がいっぱいかまたは空であると定義されている場合先頭または末尾アドレスを比較することによって、その判断は簡単にできる(後述するように、ポインタが等しい時ポインタ自体からは待ち行列がいっぱいなのか空であるのかは不明であるので、この方法は一般的に望ましくない)。しかしながら、(ほとんど空かほとんどいっぱいかなどのような）待ち行列条件について調べるには、先頭および末尾ポインタが異なる非連続的メモリ・ページの位置をポイントするため問題が直ちに発生する。この場合、待ち行列セグメントのアドレス範囲に関して、先頭および末尾ポインタが待ち行列状態の有効な情報を提供するのに役立つものであるか十分慎重な検討が行われなければならず、そして、この検討には何回かのメモリ・アクセスが必要とされる。かくして、ページ・メモリにおける循環待ち行列がページ境界にわたって形成される場合に待ち行列状態情報の導出を容易にすることが必要とされる。
【０００８】
【課題を解決するための手段】
本発明は、一般的には、物理アドレス位置をポイントする書き込み／読取りポインタに加えて、(Ｎを循環待ち行列におけるデータ項目記憶位置の総数として)概念的に循環する連続的Ｎ個の記憶位置に対するインデックスを使用し、待ち行列の論理的全体像を維持することによって、待ち行列状態の判断を実施する。
【０００９】
本発明の一面に従ってより具体的に述べれば、少なくとも２つのメモリ・ページにわたってＮ個のデータ項目記憶位置で形成される循環待ち行列へデータ項目を順次書き込む作成者エンティティが提供され、該作成者エンティティは、
＊ページ化メモリにおいて次に書き込まれるべき記憶位置のアドレスを標示するインジケータを維持する書き込みアドレス管理機構、
＊上記書き込みアドレス管理機構によって維持されるインジケータによって標示される記憶位置にデータ項目を書き込む待ち行列書き込み手段、
＊Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が書き込まれるべき記憶位置を示す作成者インデックスを記憶する作成者インデックス管理機構、および、
＊作成者エンティティの外部から供給され、Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が読み取られるべき記憶位置を示す使用者インデックスを上記作成者インデックスと比較することによって、循環待ち行列の状態を判断する状態判断手段、
を備える。
【００１０】
上記作成者インデックス管理機構は、好ましくは、上記作成者インデックスを記憶するための作成者インデックス・レジスタ、および、データ項目が上記待ち行列書き込み手段によって待ち行列に書き込まれる度毎に作成者インデックスをモジュロＮに基づいて増分させる手段を含む。
【００１１】
このような構成によって、上記Ｎ個の連続的記憶位置からなる論理的循環待ち行列内において使用者インデックスが示す位置の直前の位置を上記作成者インデックスが示す時、上記状態判断手段は循環待ち行列がいっぱいであると判断することができる。
【００１２】
一方、上記書き込みアドレス管理機構は、ページ化メモリにおいて次に書き込まれるべき記憶位置のアドレスを標示するインジケータを保持する書き込みアドレス・レジスタ、および、データ項目の書き込みおよびメモリ・ページの変更の度毎に上記書き込みアドレス・レジスタを更新する手段を含む。
【００１３】
本発明の別の一面に従えば、少なくとも２つのメモリ・ページにわたってＮ個のデータ項目記憶位置で形成される循環待ち行列からデータ項目を順次読み取る使用者エンティティが提供され、該使用者エンティティは、
＊ページ化メモリにおいて次に読み取られるべき記憶位置のアドレスを標示するインジケータを維持する読み取りアドレス管理機構、
＊上記読み取りアドレス管理機構によって維持されるインジケータによって標示される記憶位置からデータ項目を読み取る待ち行列読み取り手段、
＊Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が読み取られるべき記憶位置を示す使用者インデックスを記憶する使用者インデックス管理機構、および、
＊使用者エンティティの外部から供給され、Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が書き込まれるべき記憶位置を示す作成者インデックスを上記使用者インデックスと比較することによって、循環待ち行列の状態を判断する状態判断手段、
を備える。
【００１４】
上記使用者インデックス管理機構は、好ましくは、上記使用者インデックスを記憶するための使用者インデックス・レジスタ、および、データ項目が上記待ち行列読み取り手段によって待ち行列から読み取られる度毎に使用者インデックスをモジュロＮに基づいて増分させる手段を含む。
【００１５】
このような構成によって、上記Ｎ個の連続的記憶位置からなる論理的循環待ち行列内において上記作成者インデックスと上記使用者インデックスが示す位置が同一の場合、上記状態判断手段は循環待ち行列が空であると判断することができる。
【００１６】
一方、上記読み取りアドレス管理機構は、ページ化メモリにおいて次に読み取られるべき記憶位置のアドレスを標示するインジケータを保持する読取りアドレス・レジスタ、および、データ項目の読み取りおよびメモリ・ページの変更の度毎に上記読み取りアドレス・レジスタを更新する手段を含む。
【００１７】
本発明の更に別の１面によれば、
＊複数のメモリ・ページを持つページ化メモリ、
＊上記メモリ・ページのそれぞれに形成される複数セグメントからなり、上記セグメントの各々が対応するメモリ・ページに備わる複数のデータ項目記憶位置を含み、上記待ち行列全体で総計Ｎ個のデータ項目記憶位置が存在するように構成される循環待ち行列、
＊現在時書き込み位置に対応する循環待ち行列記憶位置にデータ項目を書き込む作成者エンティティ、および、
＊現在時読み取り位置に対応する循環待ち行列記憶位置からデータ項目を読み取る使用者エンティティ、
を備えるデータ処理システムが提供される。
【００１８】
該データ処理システムにおいて、上記エンティティの各々は、
＊上記現在時書き込みまたは読み取り位置が上記ページ・メモリのどの記憶位置に相当するかを示す物理的位置インジケータを記憶する第１レジスタ、
＊データ項目の書き込みまたは読み取りに応じて、また、現在時書き込みまたは読み取り位置に対応する記憶位置が所在するメモリ・ページの変更の発生に応じて、上記物理的位置インジケータを更新する第１更新手段、
＊連続的Ｎ個の記憶位置内の現在時書き込みまたは読み取り位置を標示する論理的位置インジケータを記憶する第２レジスタ、および
＊データ項目の書き込みまたは読み取りに応じて、モジュロＮに基づいて上記論理的位置インジケータを増分する第２更新手段、
を備え、
該データ処理システムは、更に、作成者および使用者エンティティによって維持される論理的位置インジケータを使用して循環待ち行列の現在の状態に関する情報を判断する待ち行列状態手段を備える。
【００１９】
上記データ処理システムの上記待ち行列状態手段は、好ましくは、
＊上記使用者エンティティにおいて、上記２つの論理的位置インジケータを比較して循環待ち行列が空である時点を判断するための待ち行列空き検出手段、および
＊上記作成者エンティティにおいて、上記論理的位置インジケータを比較して循環待ち行列がいっぱいである時点を判断するための待ち行列空きなし検出手段、を備える。
【００２０】
このような構成によって、上記両エンティティの論理的インジケータが上記Ｎ個の連続的記憶位置における同一の位置を示す時、上記待ち行列空き検出手段は循環待ち行列が空であると判断することができ、使用者エンティティによって維持される論理的位置インジケータによって示される位置の直前の上記Ｎ個の連続的記憶位置内の位置を上記作成者エンティティによって維持される論理的位置インジケータが示す場合、上記待ち行列空きなし検出手段が循環待ち行列がいっぱいであると判断することができる。このようにして、空きありと空きなし条件の間にいかなる混同も存在しないが、空きなし条件においては上記循環待ち行列になお１つの空き記憶位置が残る点に注意する必要がある。
【００２１】
好ましくは、循環待ち行列のセグメントの各々は、循環待ち行列における次のセグメントのメモリ・アドレスに対するポインタを記憶するリンク位置を備え、このリンク位置は、典型的には各セグメントの末尾のようなあらかじめ定められた位置に配置される。現在時セグメントの中のすべてのデータ項目記憶位置がアクセス（すなわち書き込みまたは読み取り）された時、上記いずれかのエンティティが次の待ち行列セグメントをアクセスするためにこのポインタを使用する。
【００２２】
更にまた、上記いずれかのエンティティは、現在時セグメントにおいてアクセスできる残存データ項目記憶位置の数を示す通算数を保持する第３レジスタを含むこともでき、この場合、上記第１更新手段が、
＊現在時セグメントのデータ項目記憶位置がアクセスされる度毎に上記第３レジスタの通算数を更新する手段、および、
＊上記通算数が現在時セグメントにおいてアクセスできる残存データ項目記憶位置がないことを示す場合、該セグメントのリンク位置からポインタを取り出し、そのポインタを当該エンティティの上記第１レジスタにロードする手段、
を有する。
【００２３】
このような構成と共に、各セグメントにおける記憶位置の数を異なるものにするため、各セグメントのリンク位置が、次の待ち行列セグメントにおけるデータ項目記憶位置の数を示すインジケータを含むこともできる。この場合、このインジケータは上記第１更新手段によってリンク位置から取り出され、上記第３レジスタにロードされるが、同時に同じリンク位置から上記ポインタが取り出され上記第１レジスタにロードされる。
【００２４】
現在時セグメントにおいてアクセスできる残存データ項目記憶位置の数を示す通算数を維持する上記形態に代わるものとして、各セグメント位置に記憶されるフラグを使用して、リンク位置とデータ項目記憶位置を見分けることも可能である。この場合、上記いずれのエンティティの第１更新手段も、リンク位置に出会う時そのリンク位置からポインタを取り出し、該セグメントにおけるすべての記憶位置がアクセスされた後、このポインタを第１レジスタにロードするように構成される。上記リンク位置が各セグメントの最後の位置に配置されることは好ましいことではあるが、必ずしもその必要はない。フラグの使用は使用者エンテェティについて特に適切である。なぜならば、このエンティティはいずれにしてもセグメント位置を読み取るだけであり、一方、作成者エンティティのフラグ使用は、作成者エンティティがセグメント位置への書き込みに限らず読み取りを行うことも必要とするからである。
【００２５】
【発明の実施の形態】
図３は、ページ・メモリの形態で形成され、作成者エンティティ１２と使用者エンティティ１３の間のデータ項目転送をバッファリングする循環待ち行列１０を示す。図３に示される構成全般は、循環待ち行列自体および先頭ならびに末尾ポインタの維持に関する限り図２のものと同様である。従って、図３の構成において、作成者エンティティ１２は、書き込まれるべき次の記憶位置のメモリ・アドレスに対応する末尾ポインタをレジスタ３０に維持する。このポインタは、データ項目が書き込まれる時各データ項目によって占められるメモリ・アドレスの数に対応してポインタを更新することによって、待ち行列セグメント内に（すなわち、同一のメモリ・ページ内の記憶位置について）維持される。現在時セグメントにおいてすべてのデータ項目記憶位置が使用されたことを判断するため、作成者エンティティ１２は、現在時セグメントに書き込まれるべき記憶位置の数の通算数をレジスタ３１に維持する。この通算数は、該セグメントの使用開始時点に、該セグメント中のデータ項目記憶位置の数に対応する値に初期設定される。この数は、すべてのセグメントについて同一の定数であるか、あるいは、セグメント毎に変わるものであってもよい。後者の場合、現在時セグメントの記憶位置の数は、好ましくは、先行したセグメントの末尾に維持されるリンク・エントリに記憶され、現在時セグメントの開始時にレジスタ３１にロードされる。レジスタ３１の通算数は、データ項目記憶位置に書き込みが行われる度毎に、減分される。レジスタ３１の通算数がゼロになると、作成者エンティティは、（末尾ポインタによってポイントされている）次の位置を読み、次のセグメントの最初の記憶位置のアドレスおよびそのセグメントのサイズ（すなわちデータ項目記憶位置の数）を与えるリンク・エントリを取り出す。上記２つの情報は末尾ポインタ・レジスタおよび残存セグメント・サイズ・レジスタにロードされ、異なるメモリ・ページにおける新しい待ち行列セグメントへの次のデータ項目書き込みの準備ができる。
【００２６】
同様の形態で、使用者エンティティは、先頭ポインタをレジスタ３２にロードし、現在時セグメントにおいてアクセスできる残存記憶位置数を示す通算数をレジスタ３３に保持する。
【００２７】
待ち行列状態の判断に関しては、作成者および使用者エンティティが連係してＮ個の連続的記憶位置として待ち行列の論理的視点を維持することによって、その判断が行われる（ただし、Ｎは、循環待ち行列１０によって全体として与えられるデータ項目記憶位置の総数である）。この連続性は図３において符号４０で図示されているが、それは論理的エレメントであって実物のエントリではない点注意されるべきである。
【００２８】
作成者エンティティ１２は、連続的論理記憶位置の観点から次に書き込まれるべき待ち行列の位置を示すＰインデックス(Ｐは作成者の英語Producerの頭文字からとられている)をレジスタ３４に維持する。このＰインデックスは、データ項目が待ち行列に書き込まれる毎に、モジュロＮに基づいて増分される(Ｎの値は待ち行列サイズ・レジスタ３５に維持される)。図３において、Ｐインデックスは、符号Ｐおよび矢印を用いて、連続的記憶位置空間４０と関連づけて図示されている。
【００２９】
同様の形態で、使用者エンティティが、連続的論理記憶位置４０の観点から、次に読み取られるべき待ち行列位置を表すＣインデックス(Ｃは使用者の英語Consumerの頭文字からとられている)をレジスタ３７に維持する。Ｃインデックスは、データ項目が待ち行列から読み取られる毎に、モジュロＮに基づいて増分される。この待ち行列サイズは、使用者エンティティ１３のレジスタ３５に維持される。Ｃインデックスは、図３において、符号Ｃおよび矢印を用いて、連続的記憶位置空間４０との関連において、図示されている。
【００３０】
作成者エンティティ１２には、Ｃインデックスのコピーが供給され、このコピーはレジスタ３６に維持される。使用者エンティティ１３には、Ｐインデックスのコピーが供給され、このコピーはレジスタ３９に維持される。作成者エンティティ１２は、モジュールＮに基づくＰインデックス値から、記憶したＣインデックスのコピーの値を減ずることによって待ち行列状態情報を引き出すことができる。同様に、使用者エンティティ１３は、モジュールＮに基づくＣインデックス値から、記憶したＰインデックスのコピーの値を減ずることによって待ち行列状態情報を引き出すことができる。
【００３１】
かくして、待ち行列がいっぱいかまたは空であるかを検証することが可能となる。この実施例において、ＰインデックスおよびＣインデックスが論理記憶位置４０の同一位置を表す場合、待ち行列１０は空であるとみなされる（これは待ち行列１０において先頭ポインタおよび末尾ポインタが同一の記憶位置をポイントしていることに対応する）。図４はこの条件を図示している（簡略化のため連続的論理記憶位置空間４０は図３に比較して短縮されている）。仮に待ち行列空きなし条件が空きあり条件と同様に定義されているとすれば（すなわちＰインデックスおよびＣインデックスが同じ連続的論理記憶位置を表すという条件であれば）、ＰインデックスとＣインデックスを単に調べるだけでは待ち行列が空らであるかいっぱいであるかその状態を区別することはできない。この問題を克服するため、待ち行列空きなし条件は、連続的論理記憶位置空間４０において、ＰインデックスがＣインデックスによって表される位置の直前の位置を表す場合として定義される（図５参照）。ただし、そのために、ＰインデックスおよびＣインデックスが待ち行列空きなし状態を示すと見なされる場合、待ち行列には１つの未使用記憶位置が残される。図６は、図４および図５と同様であるが、待ち行列が部分的にいっぱいにすぎない場合のＰインデックスおよびＣインデックスを表す位置を示している。
【００３２】
図７は、データ項目を循環待ち行列に書き込む場合に作成者エンティティ１２によって実行される処理ステップの流れ図を示す。この流れ図は、作成者エンティティ１２がプロセッサ型である場合プロセッサ上でプログラムとして実施されることができる。作成者エンティティが循環待ち行列にデータを渡すことを望む時、最初に待ち行列状態を検査する。そのため、作成者エンティティは、使用者エンティティによって維持されているＣインデックス値を作成者エンティティ・レジスタ３６に読み込み（ステップ５０）、次に、モジュロＮに基づいて値（Ｐインデックス＋１）をレジスタ３６のＣインデックスのコピー値と比較する（ステップ５１）。比較された値が等しければ、待ち行列はいっぱいであり、作成者エンティティは待機しなければならない。しかし、比較された値が等しくない場合、待ち行列には空きがあり、作成者エンティティは、次のステップに進み、レジスタ３０に保持される末尾ポインタによって示される次に有効なデータ項目記憶位置にデータ項目を書き込む（ステップ５２）。
【００３３】
次に、作成者エンティティ１２は、レジスタ３０、３１および３４を更新する関連処理を行う。具体的には、ステップ５３で、レジスタ３０の末尾ポインタがデータ項目のサイズに従って更新され、ステップ５４で、レジスタ３４に保持されるＰインデックスがモジュールＮに基づいて増分され、ステップ５５で、レジスタ３１に保持される残存セグメント・サイズの通算数が減分される。
【００３４】
最後に、現在時待ち行列セグメントの末尾に達したか否かの検査が行われ、末尾に到達している場合、別のメモリ・ページの新しいセグメントへの変更を必要とする。この検査は、レジスタ３１の残存セグメント・サイズ通算数を調べることを伴う（ステップ５６）。この通算数がゼロであれば、現在時セグメントの末尾に到達したことになる。この場合、末尾ポインタによってポイントされる位置が読み取られ、セグメントの末尾に記憶されたリンク・エントリが取り出され（ステップ５７）、末尾ポインタ・レジスタ３０および残存セグメント・サイズ・レジスタ３１が、リンク・エントリの内容を用いて更新される。
【００３５】
図８は、図７と同様な作成者エンティティの動作の流れ図である。この動作は、「待ち行列状態検査」ステップ６０ならびに６１、「データ項目読み取り」ステップ６２、「関連処理」ステップ６３、６４ならびに６５、および「ページ変更けんさ」ステップ６６ならびに６７を含む。これらのステップは作成者エンティティによって実行されるものとほぼ同一であるので、詳細説明は省略する。
【００３６】
空きなしまたは空き状態以外のための待ち行列しきい値を検出する必要があれば、図７のステップ５１または図８のステップ６１の後に適切なステップを追加することによってそれは達成できることは明らかであろう。例えば、図８において、書き込まれた記憶位置が３つあるという条件を検出したい場合、ステップ６１とステップ６２の間に「Ｃインデックス＋３＝Ｐインデックス・コピー値？」という検査を追加して、回答が肯定的であれば、ステップ６２が実行される前に適切な標示の生成を行う。
【００３７】
図９は、使用者エンティティに関する待ち行列メカニズムのハードウェア実施形態の一般的構造を示すブロック図である。循環待ち行列の実際の読み取りは、「次を読み取る」要求に応答して、待ち行列読み取りブロック７０によって実行される。この読み取りは、レジスタ３２に保持される先頭ポインタによって標示される位置において実行される。読み取られた項目は、線（またはバス）７２上に出力される。待ち行列管理は、読み取りアドレス管理機構７３および待ち行列状態管理機構７４によって実施される。
【００３８】
読み取りアドレス管理機構７３は、先頭ポインタを維持し、先頭ポインタ・レジスタ３２および残存セグメント・サイズ・レジスタ３３を含む。先頭ポインタ更新制御ブロック７５は、待ち行列読み取りブロック７０によってデータ項目が読み取られる毎にそれを標示する線７６上の信号に応答して、レジスタ３２を増分しレジスタ３３を減分する機能を果たす。それに加えて、先頭ポインタ更新制御ブロック７５は、レジスタ３３の値がゼロになることに応じて、待ち行列読取りブロック７０に対して、次の待ち行列位置を読みリンク・エントリ・データを取り出すことを要求する。リンク・データを受け取ると、先頭ポインタ更新制御ブロック７５は、先頭ポインタ・レジスタ３２と残存セグメント・サイズ・レジスタ３３を更新する。
【００３９】
待ち行列状態管理機構７４は、Ｃインデックスを維持し、Ｃインデックス・レジスタ３７、待ち行列サイズ・レジスタ３８およびとＰインデックス・コピー・レジスタ３９を含む。Ｃインデックス更新制御ブロック７７は、データ項目が読み取られる毎に、レジスタ３７のＣインデックス値を（モジュロＮに基づいて）増分させる機能を果たす。待ち行列状態管理機構７４は、また、Ｃインデックス・レジスタ３７とＰインデックス・コピー・レジスタ３９の内容を比較する待ち行列空き検査回路７８を含む。この回路７８は、両方のレジスタ３７および３９の内容が等しい時、待ち行列読み取りブロックが読み取り動作を行うことを禁じるため「待ち行列空ら」の信号を出力する。待ち行列読み取りブロックが「次を読み取る」要求を受け取る度毎に、または、作成者エンティティが循環待ち行列にデータ項目を書き込む度毎に、Ｐインデックス・コピー・レジスタ３９を、作成者エンティティのＰインデックス・レジスタの内容を用いて更新するように構成することができる。
【００４０】
同様のハードウェア実施形態を作成者エンティティに関しても実施できる点は当業者に容易に認められることであろうから、ここでの記述は省略する。
このようにして、上記の実施形態は、特に待ち行列が空らまたはいっぱいである条件以外のしきい値レベルが導出されるべき場合、待ち行列状態情報を効率的に導出する単純で低コストの方法を提供する。
【００４１】
上記循環待ち行列メカニズムに対する多くのバリエーションが可能であることは認められるであろう。例えば、先頭および末尾ポインタの維持に関しては、リンク・エントリに保持されるすべての情報を待ち行列自体から切り離し、リンク・エントリなしで済ますことは可能である。これは、使用者および作成者エンティティ両者が、リンク・エントリ情報のコピーを持つことを一般的には必要とし、その結果煩雑な構成となる。もう一つの代替策は、リンク・エントリを待ち行列セグメントの最初またはある固定位置に配置するものである。これは可能であるが、実際の利益がなく、作成者および使用者エンティティが要求のあるまでリンク・エントリ情報を保存していなければならないという欠点を持つ。このような理由から、リンク・エントリを各セグメントの末尾に配置することは望ましく、また、それによって、いかなるオーバーヘッドを伴うことなくリンク・エントリをデータ項目と異なる大きさにすることができる（先頭／末尾ポインタはリンク・エントリのサイズ分増分される必要は決してないので）。
【００４２】
前述のように、Ｐインデックスの使用者エンティティへのコピーおよびＣインデックスの作成者エンティティへのコピーは、データ項目送出側または受け取り側エンティのいずれによっても起動することができる。代替形態として、中間バッファ・レジスタを使用することも可能である。実際には、Ｐインデックスが更新される毎に作成者エンティティにそのＰインデックスの供給を始動させることには利点がある。なぜならば、このことを利用して、読み取られるべき新しいデータ項目があることを使用者エンティティに知らせて、新しいデータ項目を待っていたアイドル状態から使用者エンティティの状態を変移させることが可能であるからである。
【００４３】
典型的実施形態においては、循環待ち行列は、作成者エンティティである中央処理装置と使用者エンティティであるインターフェース・カードの間のバッファの役目を果たす。当然のことながら、一般的には、データ項目が両方向に流れることが望ましいので、インターフェース・カードが作成者で中央処理装置が使用者となるような第２の循環待ち行列が備えられるであろう。
【００４４】
本発明には、例として次のような実施様態が含まれる。
（１）少なくとも２つのメモリ・ページにわたってＮ個のデータ項目記憶位置で形成される循環待ち行列へデータ項目を順次書き込む作成者エンティティであって、ページ化メモリにおいて次に書き込まれるべき記憶位置のアドレスを標示するインジケータを維持する書き込みアドレス管理機構と、上記書き込みアドレス管理機構によって維持されるインジケータによって標示される記憶位置にデータ項目を書き込む待ち行列書き込み手段と、Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が書き込まれるべき記憶位置を示す作成者インデックスを記憶する作成者インデックス管理機構と、作成者エンティティの外部から供給され、Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が読み取られるべき記憶位置を示す使用者インデックスを上記作成者インデックスと比較することによって、循環待ち行列の状態を判断する状態判断手段と、を備える作成者エンティティ。
（２）上記作成者インデックス管理機構が、上記作成者インデックスを記憶するための作成者インデックス・レジスタと、データ項目が上記待ち行列書き込み手段によって待ち行列に書き込まれる度毎に作成者インデックスをモジュロＮに基づいて増分させる手段と、を含む、上記（１）に記載の作成者エンティティ。
（３）上記状態判断手段が、上記Ｎ個の連続的記憶位置からなる論理的循環待ち行列内において使用者インデックスが示す位置の直前の位置を上記作成者インデックスが示す時、循環待ち行列がいっぱいであると判断する、上記（１）に記載の作成者エンティティ。
（４）上記書き込みアドレス管理機構が、ページ化メモリにおいて次に書き込まれるべき記憶位置のアドレスを標示するインジケータを保持する書き込みアドレス・レジスタと、データ項目の書き込みおよびメモリ・ページの変更の度毎に上記書き込みアドレス・レジスタを更新する手段と、を含む、上記（１）に記載の作成者エンティティ。
【００４５】
（５）少なくとも２つのメモリ・ページにわたってＮ個のデータ項目記憶位置で形成される循環待ち行列からデータ項目を順次読み取る使用者エンティティであって、ページ化メモリにおいて次に読み取られるべき記憶位置のアドレスを標示するインジケータを維持する読み取りアドレス管理機構と、上記読み取りアドレス管理機構によって維持されるインジケータによって標示される記憶位置からデータ項目を読み取る待ち行列読み取り手段と、Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が読み取られるべき記憶位置を示す使用者インデックスを記憶する使用者インデックス管理機構と、使用者エンティティの外部から供給され、Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用いて次にデータ項目が書き込まれるべき記憶位置を示す作成者インデックスを上記使用者インデックスと比較することによって、循環待ち行列の状態を判断する状態判断手段と、を備える使用者エンティティ。
（６）上記使用者インデックス管理機構が、上記使用者インデックスを記憶するための使用者インデックス・レジスタと、データ項目が上記待ち行列読み取り手段によって待ち行列から読み取られる度毎に使用者インデックスをモジュロＮに基づいて増分させる手段と、を含む、上記（５）に記載の使用者エンティティ。
（７）上記状態判断手段が、上記Ｎ個の連続的記憶位置からなる論理的循環待ち行列内において上記作成者インデックスと上記使用者インデックスが示す位置が同一の場合、循環待ち行列が空であると判断する、上記（５）に記載の使用者エンティティ。
（８）上記読み取りアドレス管理機構が、ページ化メモリにおいて次に読み取られるべき記憶位置のアドレスを標示するインジケータを保持する読取りアドレス・レジスタと、データ項目の読み取りおよびメモリ・ページの変更の度毎に上記読み取りアドレス・レジスタを更新する手段と、を含む、上記（５）に記載の使用者エンティティ。
【００４６】
（９）複数のメモリ・ページを持つページ化メモリと、上記メモリ・ページのそれぞれに形成される複数セグメントからなり、上記セグメントの各々が対応するメモリ・ページに備わる複数のデータ項目記憶位置を含み、上記待ち行列全体で総計Ｎ個のデータ項目記憶位置が存在するように構成される循環待ち行列と、現在時書き込み位置に対応する循環待ち行列記憶位置にデータ項目を書き込む作成者エンティティと、現在時読取り位置に対応する循環待ち行列記憶位置からデータ項目を読み取る使用者エンティティと、を備えるデータ処理システムであって、上記エンティティの各々が、上記現在時書き込みまたは読み取り位置が上記ページ・メモリのどの記憶位置に相当するかを示す物理的位置インジケータを記憶する第１レジスタと、データ項目の書き込みまたは読み取りに応じて、また、現在時書き込みまたは読み取り位置に対応する記憶位置が所在するメモリ・ページの変更の発生に応じて、上記物理的位置インジケータを更新する第１更新手段と、連続的Ｎ個の記憶位置内の現在時書き込みまたは読み取り位置を標示する論理的位置インジケータを記憶する第２レジスタと、データ項目の書き込みまたは読み取りに応じて、モジュロＮに基づいて上記論理的位置インジケータを増分する第２更新手段と、を含み、更に、作成者および使用者エンティティによって維持される論理的位置インジケータを使用して循環待ち行列の現在の状態に関する情報を判断する待ち行列状態手段を備える、データ処理システム。
（１０）上記待ち行列状態手段が、上記使用者エンティティにおいて上記２つの論理的位置インジケータを比較して循環待ち行列が空である時点を判断するための待ち行列空き検出手段と、上記作成者エンティティにおいて上記論理的位置インジケータを比較して循環待ち行列がいっぱいである時点を判断するための待ち行列空きなし検出手段と、を備える、上記（９）に記載のデータ処理システム。
（１１）上記待ち行列空き検出手段が、上記両エンティティの論理的インジケータが上記Ｎ個の連続的記憶位置における同一の位置を示す時、循環待ち行列が空であると判断し、上記待ち行列空きなし検出手段が、使用者エンティティによって維持される論理的位置インジケータによって示される位置の直前の上記Ｎ個の連続的記憶位置内の位置を上記作成者エンティティによって維持される論理的位置インジケータが示す場合、循環待ち行列がいっぱいであると判断する、上記（９）に記載のデータ処理システム。
【００４７】
（１２）上記循環待ち行列のセグメントの各々が、あらかじめ定められた位置に配置され循環待ち行列における次のセグメントのメモリ・アドレスに対するポインタを記憶するリンク位置を備え、すくなくとも上記作成者エンティティが現在時セグメントにおいてアクセスできる残存データ項目記憶位置の数を示す通算数を保持する第３レジスタを含み、上記第１更新手段が、現在時セグメントのデータ項目記憶位置がアクセスされる度毎に上記第３レジスタの通算数を更新する手段と、上記通算数が現在時セグメントにおいてアクセスできる残存データ項目記憶位置がないことを示す場合該セグメントのリンク位置からポインタを取り出しそのポインタを当該エンティティの上記第１レジスタにロードする手段とを有する、上記（９）に記載のデータ処理システム。
（１３）各セグメントの上記リンク位置が、各セグメントにおける記憶位置の数を異なるものにするため、次の待ち行列セグメントにおけるデータ項目記憶位置の数を示すインジケータを含み、該インジケータが上記第１更新手段によってリンク位置から取り出され、上記第３レジスタにロードされ、同時に同じリンク位置から上記ポインタが取り出され上記第１レジスタにロードされる、上記（１２）に記載のデータ処理システム。
（１４）循環待ち行列の上記セグメントの各々が循環待ち行列の次のセグメントのメモリ・アドレスに対するポインタを含み、各セグメントのデータ記憶位置およびリンク位置のそれぞれがリンク位置を識別できるように設定されたフラグを含み、少なくとも使用者エンティティが該フラグを使用してリンク位置を識別し、該エンティティの上記第１更新手段が、当該リンク位置から上記ポインタを取り出し、該セグメントにおけるすべての記憶位置がアクセスされた後該ポインタを上記第１レジスタにロードするように構成される、上記（９）に記載のデータ処理システム。
【００４８】
【発明の効果】
本発明によって、ページ・メモリにおける循環待ち行列がページ境界にわたって形成される場合の待ち行列状態情報の導出を容易に行うことができる。特に、待ち行列が空らである場合またはいっぱいである場合以外の循環待ち行列状態を判断する単純で低コストの方法が本発明によって提供される。
【図面の簡単な説明】
【図１】作成者エンティティと使用者エンティティの間でデータ項目を受け渡すための連続メモリ・ブロックの形態をなす循環待ち行列を示すブロック図である。
【図２】図１と類似しているが、複数のページ・メモリにわたって形成される循環待ち行列を示すブロック図である。
【図３】図２と類似しているが、本発明に従って待ち行列状態情報の生成を実現するため作成者および使用者エンティティによって維持される論理的待ち行列が追加された循環待ち行列を示すブロック図である。
【図４】図３の論理的待ち行列が空の時の作成者および使用者インデックスの相対的位置を示すブロック図である。
【図５】図３の論理的待ち行列がいっぱいの時の作成者および使用者インデックスの相対的位置を示すブロック図である。
【図６】図３の論理的待ち行列が部分的にいっぱいの状態の時の作成者および使用者インデックスの相対的位置を示すブロック図である。
【図７】作成者エンティティの動作を示す流れ図である。
【図８】使用者エンティティの動作を示す流れ図である
【図９】使用者エンティティの１つのハードウェア実施形態を示すブロック図である。
【符号の説明】
１０  循環待ち行列
１１  連続ブロック・メモリ
１２  作成者エンティティ
１３  使用者エンティティ
２０  待ち行列セグメント
２１  リンク・エントリ
３０  末尾ポインタ
３１、３３  残存セグメント・サイズ・レジスタ
３２  先頭ポインタ
３４  Ｐ(作成者)インデックス・レジスタ
３５、３８  待ち行列サイズ・レジスタ
３６  Ｃインデックス・コピー・レジスタ
３７  Ｃ(使用者)インデックス・レジスタ
３９  Ｐインデックス・コピー・レジスタ
４０  連続的論理記憶位置空間
７０  待ち行列読み取りブロック
７１  次読み取り要求
７２  データ項目出力
７３  読み取りアドレス管理機構
７４  待ち行列状態管理機構
７５  先頭ポインタ更新制御ブロック
７６  項目読み取り要求
７７  Ｃインデックス更新制御ブロック
７８  待ち行列空き検査回路
【図１】
0003715724.tif 000002
【図２】
0003715724.tif 000003
【図３】
0003715724.tif 000004
【図４】
0003715724.tif 000005
【図５】
0003715724.tif 000006
【図６】
0003715724.tif 000007
【図７】
0003715724.tif 000008
【図８】
0003715724.tif 000009
【図９】
0003715724.tif 000010