JPH09152988A - 循環待ち行列作成者エンティティ - Google Patents

循環待ち行列作成者エンティティ

Info

Publication number
JPH09152988A
JPH09152988A JP8231701A JP23170196A JPH09152988A JP H09152988 A JPH09152988 A JP H09152988A JP 8231701 A JP8231701 A JP 8231701A JP 23170196 A JP23170196 A JP 23170196A JP H09152988 A JPH09152988 A JP H09152988A
Authority
JP
Japan
Prior art keywords
queue
index
entity
creator
data item
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
Application number
JP8231701A
Other languages
English (en)
Other versions
JP3715724B2 (ja
Inventor
Pascal Regache
レガシー・パスカル
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
HP Inc
Original Assignee
Hewlett Packard Co
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Hewlett Packard Co filed Critical Hewlett Packard Co
Publication of JPH09152988A publication Critical patent/JPH09152988A/ja
Application granted granted Critical
Publication of JP3715724B2 publication Critical patent/JP3715724B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F5/00—Methods or arrangements for data conversion without changing the order or content of the data handled
    • G06F5/06—Methods or arrangements for data conversion without changing the order or content of the data handled for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2205/00—Indexing scheme relating to group G06F5/00; Methods or arrangements for data conversion without changing the order or content of the data handled
    • G06F2205/06—Indexing scheme relating to groups G06F5/06 - G06F5/16
    • G06F2205/064—Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Memory System (AREA)

Abstract

(57)【要約】 【課題】ページ・メモリの形態で形成される循環待ち行
列を使用して作成者エンティティと使用者エンティティ
の間のデータ転送のバッファリングを行うデータ処理シ
ステムにおいて、循環待ち行列の状態情報の導出を容易
にする。 【解決手段】複数ページにわたる循環待ち行列に対応す
る連続的論理記憶位置空間を使用し、作成者エンティテ
ィが次にデータ項目を書き込むべき論理空間上の記憶位
置を示すＰ(作成者)インデックスを維持し、一方使用者
エンティティは次にデータ項目を読み込むべき論理空間
上の記憶位置を示すＣ(使用者)インデックスを維持す
る。作成者は、Ｐインデックスの位置が、Ｃインデック
スの直前の位置を示していれば待ち行列はいっぱいで書
き込みを行う余地がないと判断し、使用者は、Ｃインデ
ックスとＰインデックスが同一位置を示せば待ち行列は
空で読み取るべきデータ項目がないと判断する。

Description

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

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】少なくとも２つのメモリ・ページにわたっ
    てＮ個のデータ項目記憶位置で形成される循環待ち行列
    へデータ項目を順次書き込む作成者エンティティであっ
    て、 ページ化メモリにおいて次に書き込まれるべき記憶位置
    のアドレスを標示するインジケータを維持する書き込み
    アドレス管理機構と、 上記書き込みアドレス管理機構によって維持されるイン
    ジケータによって標示される記憶位置にデータ項目を書
    き込む待ち行列書き込み手段と、 Ｎ個の連続的記憶位置からなる論理的循環待ち行列を用
    いて次にデータ項目が書き込まれるべき記憶位置を示す
    作成者インデックスを記憶する作成者インデックス管理
    機構と、 作成者エンティティの外部から供給され、Ｎ個の連続的
    記憶位置からなる論理的循環待ち行列を用いて次にデー
    タ項目が読み取られるべき記憶位置を示す使用者インデ
    ックスを上記作成者インデックスと比較することによっ
    て、循環待ち行列の状態を判断する状態判断手段と、 を備える作成者エンティティ。
JP23170196A 1995-09-04 1996-09-02 循環待ち行列作成者エンティティ Expired - Fee Related JP3715724B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP95410092A EP0760501B1 (en) 1995-09-04 1995-09-04 Data handling system with circular queue formed in paged memory
FR95410092.1 1995-09-04

Publications (2)

Publication Number Publication Date
JPH09152988A true JPH09152988A (ja) 1997-06-10
JP3715724B2 JP3715724B2 (ja) 2005-11-16

Family

ID=8221565

Family Applications (1)

Application Number Title Priority Date Filing Date
JP23170196A Expired - Fee Related JP3715724B2 (ja) 1995-09-04 1996-09-02 循環待ち行列作成者エンティティ

Country Status (4)

Country Link
US (1) US5873089A (ja)
EP (1) EP0760501B1 (ja)
JP (1) JP3715724B2 (ja)
DE (1) DE69525531T2 (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7041893B2 (en) 2001-08-09 2006-05-09 Yamaha Corporation Electronic musical instrument with customization of auxiliary capability
JP2010532518A (ja) * 2007-06-29 2010-10-07 エミュレックス デザイン アンド マニュファクチュアリング コーポレーション 効率的な待ち行列管理のための方法およびシステム
JP2023148176A (ja) * 2022-03-30 2023-10-13 公立大学法人会津大学 テンソルメモリ及びテンソルプロセッサ

Families Citing this family (60)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0825506B1 (en) * 1996-08-20 2013-03-06 Invensys Systems, Inc. Methods and apparatus for remote process control
US6519686B2 (en) * 1998-01-05 2003-02-11 Intel Corporation Information streaming in a multi-process system using shared memory
US6308167B1 (en) * 1998-04-09 2001-10-23 Compaq Computer Corporation Computer system using a queuing system and method for managing a queue and heterogeneous data structures
US6691183B1 (en) 1998-05-20 2004-02-10 Invensys Systems, Inc. Second transfer logic causing a first transfer logic to check a data ready bit prior to each of multibit transfer of a continous transfer operation
US6314478B1 (en) 1998-12-29 2001-11-06 Nec America, Inc. System for accessing a space appended to a circular queue after traversing an end of the queue and upon completion copying data back to the queue
US6304924B1 (en) * 1999-02-02 2001-10-16 International Business Machines Corporation Two lock-free, constant-space, multiple-(impure)-reader, single-writer structures
US7089530B1 (en) * 1999-05-17 2006-08-08 Invensys Systems, Inc. Process control configuration system with connection validation and configuration
US6754885B1 (en) 1999-05-17 2004-06-22 Invensys Systems, Inc. Methods and apparatus for controlling object appearance in a process control configuration system
WO2000070417A1 (en) 1999-05-17 2000-11-23 The Foxboro Company Process control configuration system with parameterized objects
US7096465B1 (en) 1999-05-17 2006-08-22 Invensys Systems, Inc. Process control configuration system with parameterized objects
US7272815B1 (en) 1999-05-17 2007-09-18 Invensys Systems, Inc. Methods and apparatus for control configuration with versioning, security, composite blocks, edit selection, object swapping, formulaic values and other aspects
US7100000B1 (en) * 1999-05-28 2006-08-29 International Business Machines Corporation System and methods for processing audio using multiple speech technologies
US6501995B1 (en) 1999-06-30 2002-12-31 The Foxboro Company Process control system and method with improved distribution, installation and validation of components
US6788980B1 (en) 1999-06-11 2004-09-07 Invensys Systems, Inc. Methods and apparatus for control using control devices that provide a virtual machine environment and that communicate via an IP network
US6757679B1 (en) * 1999-06-25 2004-06-29 International Business Machines Corporation System for building electronic queue(s) utilizing self organizing units in parallel to permit concurrent queue add and remove operations
US6510352B1 (en) 1999-07-29 2003-01-21 The Foxboro Company Methods and apparatus for object-based process control
US6507343B1 (en) 1999-11-30 2003-01-14 International Business Machines Corp. Arrangement of information to allow three-dimensional navigation through information displays
US6556225B1 (en) 1999-11-30 2003-04-29 International Business Machines Corp. Graphical display of path through three-dimensional organization of information
US6593943B1 (en) 1999-11-30 2003-07-15 International Business Machines Corp. Information grouping configuration for use with diverse display devices
US6473660B1 (en) 1999-12-03 2002-10-29 The Foxboro Company Process control system and method with automatic fault avoidance
US6873658B2 (en) * 1999-12-20 2005-03-29 Texas Instruments Incorporated Digital still camera system and method
US6779128B1 (en) 2000-02-18 2004-08-17 Invensys Systems, Inc. Fault-tolerant data transfer
US6625335B1 (en) 2000-05-11 2003-09-23 Matsushita Electric Industrial Co., Ltd. Method and apparatus for assigning keywords to documents
US6647505B1 (en) * 2000-06-23 2003-11-11 Unisys Corporation Deletion system and method for removing temporary timer entries having a weight value of zero from a circular queue of sequential fixed timer entries
US7126969B1 (en) * 2000-07-06 2006-10-24 Cisco Technology, Inc. Scalable system and method for reliably sequencing changes in signaling bits in multichannel telecommunication lines transmitted over a network
KR100414052B1 (ko) * 2000-10-14 2004-01-07 엘지전자 주식회사 주기억장치 데이터베이스의 인덱스 데이터 관리방법
JP2004531002A (ja) * 2001-06-29 2004-10-07 コーニンクレッカ　フィリップス　エレクトロニクス　エヌ　ヴィ データ処理装置及びデータ処理装置における第１及び第２の処理手段を同期させる方法
US7158964B2 (en) 2001-12-12 2007-01-02 Intel Corporation Queue management
US7107413B2 (en) 2001-12-17 2006-09-12 Intel Corporation Write queue descriptor count instruction for high speed queuing
US7269179B2 (en) 2001-12-18 2007-09-11 Intel Corporation Control mechanisms for enqueue and dequeue operations in a pipelined network processor
US7895239B2 (en) * 2002-01-04 2011-02-22 Intel Corporation Queue arrays in network devices
US7181573B2 (en) 2002-01-07 2007-02-20 Intel Corporation Queue array caching in network devices
US7149226B2 (en) 2002-02-01 2006-12-12 Intel Corporation Processing data packets
US6862639B2 (en) * 2002-03-11 2005-03-01 Harris Corporation Computer system including a receiver interface circuit with a scatter pointer queue and related methods
US6813658B2 (en) * 2002-03-27 2004-11-02 Intel Corporation Dynamic data queuing mechanism for packet networks
US7242991B2 (en) * 2002-04-15 2007-07-10 Invensys Systems, Inc. Workflow control configurator for use with process, factory-floor, environmental, computer aided manufacturing-based or other control system
US7761923B2 (en) * 2004-03-01 2010-07-20 Invensys Systems, Inc. Process control methods and apparatus for intrusion detection, protection and network hardening
US20060153185A1 (en) * 2004-12-28 2006-07-13 Intel Corporation Method and apparatus for dynamically changing ring size in network processing
WO2006129226A2 (en) * 2005-05-30 2006-12-07 Nxp B.V. Data pipeline management system and method for using the system
WO2007123753A2 (en) 2006-03-30 2007-11-01 Invensys Systems, Inc. Digital data processing apparatus and methods for improving plant performance
DE602008004500D1 (en) * 2007-05-16 2011-02-24 Nxp Bv Fifo-puffer
US8122168B2 (en) * 2007-05-17 2012-02-21 International Business Machines Corporation Method for implementing concurrent producer-consumer buffers
WO2009083027A1 (en) * 2007-12-27 2009-07-09 Nokia Corporation Method and system for managing data in a memory
CN104407518B (zh) 2008-06-20 2017-05-31 因文西斯系统公司 对用于过程控制的实际和仿真设施进行交互的系统和方法
US8127060B2 (en) * 2009-05-29 2012-02-28 Invensys Systems, Inc Methods and apparatus for control configuration with control objects that are fieldbus protocol-aware
US8463964B2 (en) * 2009-05-29 2013-06-11 Invensys Systems, Inc. Methods and apparatus for control configuration with enhanced change-tracking
US7970927B1 (en) 2009-12-31 2011-06-28 Qlogic, Corporation Concurrent transmit processing
US9055011B2 (en) * 2010-08-31 2015-06-09 Intel Corporation Methods and apparatus for linked-list circular buffer management
US8533390B2 (en) * 2010-08-31 2013-09-10 Intel Corporation Circular buffer in a redundant virtualization environment
CN102402486B (zh) * 2010-09-17 2014-07-23 腾讯科技（深圳）有限公司 读取数据的方法及装置
US8930568B1 (en) * 2011-12-20 2015-01-06 Emc Corporation Method and apparatus for enabling access to storage
KR20150129460A (ko) * 2014-05-12 2015-11-20 현대모비스 주식회사 차량용 지능형 배터리 센서 및 이를 이용한 데이터 저장 방법
US9489173B2 (en) * 2014-06-04 2016-11-08 Advanced Micro Devices, Inc. Resizable and relocatable queue
US9942324B2 (en) * 2015-08-05 2018-04-10 Futurewei Technologies, Inc. Rebalancing and elastic storage scheme with elastic named distributed circular buffers
CN106250323B (zh) * 2016-07-27 2019-04-19 陕西黄河集团有限公司 利用动态链表实现内存实时分配方法
CN106533977B (zh) * 2016-11-02 2019-05-17 南京邮电大学 一种云数据中心的数据处理方法
CN110209493B (zh) * 2019-04-11 2023-08-01 腾讯科技（深圳）有限公司 内存管理方法、装置、电子设备及存储介质
US11558309B1 (en) 2021-07-08 2023-01-17 Mellanox Technologies, Ltd. Expandable queue
CN118819399A (zh) 2023-04-19 2024-10-22 美光科技公司 用于单片系统的计数器队列
US20260099481A1 (en) * 2024-10-07 2026-04-09 Nvidia Corporation Efficient management of queue entry state

Family Cites Families (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4507760A (en) * 1982-08-13 1985-03-26 At&T Bell Laboratories First-in, first-out (FIFO) memory configuration for queue storage
US4611322A (en) * 1984-08-03 1986-09-09 At&T Bell Laboratories Traffic load control arrangement and method for a packet switching system
US4713754A (en) * 1984-10-09 1987-12-15 Wang Laboratories, Inc. Data structure for a document processing system
US4682284A (en) * 1984-12-06 1987-07-21 American Telephone & Telegraph Co., At&T Bell Lab. Queue administration method and apparatus
US5497489A (en) * 1987-05-05 1996-03-05 Menne; David M. Data storage and retrieval systems having labelling for data
US4807111A (en) * 1987-06-19 1989-02-21 International Business Machines Corporation Dynamic queueing method
US4816996A (en) * 1987-07-24 1989-03-28 Motorola, Inc. Queued serial peripheral interface for use in a data processing system
US4888739A (en) * 1988-06-15 1989-12-19 Cypress Semiconductor Corporation First-in first-out buffer memory with improved status flags
US4914652A (en) * 1988-08-01 1990-04-03 Advanced Micro Devices, Inc. Method for transfer of data between a media access controller and buffer memory in a token ring network
ATE92657T1 (de) * 1988-09-28 1993-08-15 Siemens Nixdorf Inf Syst Warteschlange, bestehend aus mehreren speicherelementen.
US5115504A (en) * 1988-11-01 1992-05-19 Lotus Development Corporation Information management system
US4951280A (en) * 1988-12-09 1990-08-21 Advanced Micro Devices, Inc. Method and apparatus for configuring data paths within a supernet station
JP2535615B2 (ja) * 1989-08-14 1996-09-18 株式会社東芝 デ―タ同期伝送方式
US5136582A (en) * 1990-05-29 1992-08-04 Advanced Micro Devices, Inc. Memory management system and method for network controller
US5043981A (en) * 1990-05-29 1991-08-27 Advanced Micro Devices, Inc. Method of and system for transferring multiple priority queues into multiple logical FIFOs using a single physical FIFO
US5202988A (en) * 1990-06-11 1993-04-13 Supercomputer Systems Limited Partnership System for communicating among processors having different speeds
US5303367A (en) * 1990-12-04 1994-04-12 Applied Technical Systems, Inc. Computer driven systems and methods for managing data which use two generic data elements and a single ordered file
US5594927A (en) * 1992-01-09 1997-01-14 Digital Equipment Corporation Apparatus and method for aligning data transferred via DMA using a barrel shifter and a buffer comprising of byte-wide, individually addressabe FIFO circuits
US5539899A (en) * 1992-04-03 1996-07-23 International Business Machines Corporation System and method for handling a segmented program in a memory for a multitasking data processing system utilizing paged virtual storage
US5530957A (en) * 1992-08-07 1996-06-25 At&T Corp. Storing trees in navigable form
US5553220A (en) * 1993-09-07 1996-09-03 Cirrus Logic, Inc. Managing audio data using a graphics display controller
US5581705A (en) * 1993-12-13 1996-12-03 Cray Research, Inc. Messaging facility with hardware tail pointer and software implemented head pointer message queue for distributed memory massively parallel processing system
US5412483A (en) * 1993-12-16 1995-05-02 Xerox Corporation Apparatus and method for managing storage of print-related information in a print file
US5448558A (en) * 1994-04-05 1995-09-05 International Business Machines Corporation Method and apparatus for managing packet FIFOS
US5548759A (en) * 1994-07-05 1996-08-20 Microsoft Corporation System for storing executable code within a resource data section of an executable file
US5519701A (en) * 1995-03-29 1996-05-21 International Business Machines Corporation Architecture for high performance management of multiple circular FIFO storage means

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7041893B2 (en) 2001-08-09 2006-05-09 Yamaha Corporation Electronic musical instrument with customization of auxiliary capability
JP2010532518A (ja) * 2007-06-29 2010-10-07 エミュレックス デザイン アンド マニュファクチュアリング コーポレーション 効率的な待ち行列管理のための方法およびシステム
JP2023148176A (ja) * 2022-03-30 2023-10-13 公立大学法人会津大学 テンソルメモリ及びテンソルプロセッサ

Also Published As

Publication number Publication date
DE69525531D1 (de) 2002-03-28
US5873089A (en) 1999-02-16
DE69525531T2 (de) 2002-07-04
JP3715724B2 (ja) 2005-11-16
EP0760501A1 (en) 1997-03-05
EP0760501B1 (en) 2002-02-20

Similar Documents

Publication Publication Date Title
JP3715724B2 (ja) 循環待ち行列作成者エンティティ
US6542971B1 (en) Memory access system and method employing an auxiliary buffer
US6581142B1 (en) Computer program product and method for partial paging and eviction of microprocessor instructions in an embedded computer
US6032179A (en) Computer system with a network interface which multiplexes a set of registers among several transmit and receive queues
US5450564A (en) Method and apparatus for cache memory access with separate fetch and store queues
TW200301438A (en) Method and apparatus to reduce memory latency
US10642740B2 (en) Methods for performing a memory resource retry
US7080220B2 (en) Page replacement with a re-reference indicator
JP3798049B2 (ja) データメモリおよびその動作方法
CN112559389A (zh) 存储控制装置、处理装置、计算机系统和存储控制方法
JPS6217876Y2 (ja)
US8424014B2 (en) Method for pushing work request-associated contexts into an IO device
US5555379A (en) Cache controller index address generator
US20060190689A1 (en) Method of addressing data in a shared memory by means of an offset
KR950033914A (ko) 디지탈 영상/그래픽 프로세싱을 위한 데이타 프로세서 회로 및 프로세싱 방법
US4737908A (en) Buffer memory control system
GB2037466A (en) Computer with cache memory
US6742073B1 (en) Bus controller technique to control N buses
JPH06301600A (ja) 記憶装置
JPH09282231A (ja) ライトバック型キャッシュ装置
TW538374B (en) Instruction cache device and method using instruction read buffer
JPS6063650A (ja) バッファメモリ一致制御方式
JPH0833869B2 (ja) データ処理装置
JPH0290345A (ja) メモリシステム
CN120723167A (zh) 一种地址访问控制系统、方法、电子设备及存储介质

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20050222

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20050315

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20050608

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20050613

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20050728

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20050823

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20050826

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

LAPS Cancellation because of no payment of annual fees