データ記憶装置
【課題】メモリ管理アルゴリズムに基づいてエントリデータの並べ替えを行う場合でも少ないメモリ消費量で動作し、処理速度の低下を抑制できるデータ記憶装置を提供する。
【解決手段】データ記憶装置１１は、エントリデータを保持する複数のデータ記憶領域を有するエントリ保持回路１２を備える。各データ記憶領域は、エントリデータを有効にする有効値またはエントリデータを無効にする無効値を持つ有効フラグを格納する有効フラグ領域と、実体データを格納するデータ領域とを有する。エントリ制御回路１３は、エントリデータの書き込みが実行されない間に、空き領域の順位よりも上位のデータ記憶領域に保持されているエントリデータを下位のデータ記憶領域にシフトさせ、最上位のデータ記憶領域に無効値を持つ有効フラグを書き込む。
【解決手段】データ記憶装置１１は、エントリデータを保持する複数のデータ記憶領域を有するエントリ保持回路１２を備える。各データ記憶領域は、エントリデータを有効にする有効値またはエントリデータを無効にする無効値を持つ有効フラグを格納する有効フラグ領域と、実体データを格納するデータ領域とを有する。エントリ制御回路１３は、エントリデータの書き込みが実行されない間に、空き領域の順位よりも上位のデータ記憶領域に保持されているエントリデータを下位のデータ記憶領域にシフトさせ、最上位のデータ記憶領域に無効値を持つ有効フラグを書き込む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置に対するデータの保存や読み出しを行う技術に関し、特に、ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）アルゴリズムなどのメモリ管理アルゴリズムに基づいて記憶装置に対するデータの保存や読み出しを行う技術に関する。
【背景技術】
【０００２】
従来から、ハードディスクドライブ（ＨＤＤ）やキャッシュメモリや仮想メモリなどの記憶装置に対するデータの保存や読み出しを制御する手段として、記憶装置に保存されるデータまたはその記憶領域に優先順位を付与するメモリ管理アルゴリズムが広く使用されている。メモリ管理アルゴリズムを使用すれば、記憶装置に保存されているデータのうち最も優先順位の低いデータを選択し、これを必要に応じて記憶装置から削除する（追い出す）ことにより、記憶装置の限られた記憶領域内にできるだけ有意なデータを保存する領域を確保することができる。この種のメモリ管理アルゴリズムとしては、たとえば、時間的な局所性原理（Ｌｏｃａｌｉｔｙ Ｐｒｉｎｃｉｐｌｅ）に基づくＬＲＵアルゴリズムやＬＦＵ（Ｌｅａｓｔ Ｆｒｅｑｕｅｎｔｌｙ Ｕｓｅｄ）アルゴリズムが広く知られている。ＬＲＵアルゴリズムは、最も長い間参照されていないデータを、近い将来参照される可能性が最も低いものとして選択するアルゴリズムであり、ＬＦＵアルゴリズムは、最も参照頻度が低いデータを、近い将来参照される可能性が最も低いものとして選択するアルゴリズムである。
【０００３】
ＬＲＵアルゴリズムに関する先行技術文献としては、たとえば、特開平９−２８８６１７号公報（特許文献１）及び特許第４３６９５２４号明細書（特許文献２）が挙げられる。特許文献１に開示されているＬＲＵ制御方式は、検索対象データをテーブルから検索する手段と、この検索対象データがテーブル内に存在したときは、検索対象データをテーブルの先頭に位置するように並び替える手段とを有するものである。一方、特許文献２に開示されているＬＲＵ制御装置は、複数のエントリをそれぞれ識別するための複数の識別情報（たとえば、エントリごとに一意に付与されたＩＤ）からなるＬＲＵ情報を記憶する記憶手段と、これら複数のエントリの中のいずれかのエントリが使用された場合に、ＬＲＵ情報の中から使用されたエントリの識別情報を取り出すとともに最後尾に移動させてＬＲＵ情報を更新する手段とを備えている。ＬＲＵ情報を構成する複数の識別情報は、エントリの最終使用時の古い順に書き込まれる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平９−２８８６１７号公報
【特許文献２】特許第４３６９５２４号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
メモリ管理アルゴリズムの１つとして並べ替え方式と呼ばれるものがある。並べ替え方式は、エントリの登録や削除や更新ごとに、データ記憶領域においてエントリデータを優先順位に従って並べ替える方式である。特許文献１に開示されているＬＲＵ制御方式は、並べ替え方式の一種である。しかしながら、並べ替え方式には、エントリデータを並べ替えている間は、エントリデータを格納するデータ記憶領域にアクセスすることができない期間が発生し、これが処理速度の低下を招くという問題がある。
【０００６】
特許文献２に開示されているＬＲＵ制御装置は、エントリデータを格納するデータ記憶領域とは別の記憶領域にＬＲＵ情報を構築し、エントリの登録や削除や更新ごとに、ＬＲＵ情報内の複数の識別情報を最終使用時が古い順に並べ替えて記憶することでＬＲＵ情報を更新する。このため、ＬＲＵ制御により識別情報が並べ替えられている最中であっても、データ記憶領域にアクセスしてエントリデータを読み出すことができる。しかしながら、ＬＲＵ制御のために別の記憶領域を確保する必要があるのでメモリ消費量が多くなる。また、ＬＲＵ制御の対象となるエントリ数が増えると、ＬＲＵ制御を実現するために必要なビット数が増大するという問題もある。
【０００７】
上記に鑑みて本発明の目的は、メモリ管理アルゴリズムに基づいてエントリデータの並べ替えを行う場合でも少ないメモリ消費量で動作し、処理速度の低下を抑制することができるデータ記憶装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明によるデータ記憶装置は、所定のメモリ管理アルゴリズムに基づく優先順位を有する複数のエントリデータをそれぞれ保持し、該複数のエントリデータの優先順位に対応する順位がそれぞれ割り当てられた複数のデータ記憶領域を有するエントリ保持回路と、外部装置からのアクセス要求に応じて、前記複数のデータ記憶領域に対して前記エントリデータの読み出し及び書き込みを実行するエントリ制御回路と、を備え、前記各データ記憶領域は、当該各データ記憶領域に保持されるエントリデータを有効にする有効値及び当該各データ記憶領域に保持されるエントリデータを無効にする無効値のうちのいずれか一方の値を持つ有効フラグを格納する有効フラグ領域と、実体データを格納するデータ領域と、を有し、前記エントリ制御回路は、前記複数のデータ記憶領域の中から前記無効値を持つ有効フラグを保持する無効化データ領域を空き領域として検出する領域検出部と、前記複数のデータ記憶領域に対して前記エントリデータの書き込みが実行されない間に、前記複数のデータ記憶領域のうち前記無効化データ領域の順位よりも上位のデータ記憶領域に保持されているエントリデータを、前記上位のデータ記憶領域よりも下位の当該データ記憶領域にシフトさせるシフト操作を行うとともに、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記無効値を持つ有効フラグを書き込むメモリ制御部と、を含むことを特徴とする。
【発明の効果】
【０００９】
本発明によれば、有効フラグと実体データとを含むエントリデータがデータ記憶領域に保持される。データ記憶領域に対するエントリデータの書き込みが実行されない間に、有効フラグを使用したシフト操作によりエントリデータの並び替えを効率的に行うことができる。
【図面の簡単な説明】
【００１０】
【図１】本発明に係る実施の形態１のデータ処理システムの概略構成を示す機能ブロック図である。
【図２】実施の形態１のデータ記憶装置のエントリ保持回路内のデータ記憶領域の構成を示す図である。
【図３】実施の形態１のデータ記憶装置のエントリ制御回路の構成の一例を示す機能ブロック図である。
【図４】実施の形態１のエントリ保持回路の好適な構成を示す図である。
【図５】実施の形態１に係るエントリ並べ替え処理の手順を概略的に示すフローチャートである。
【図６】図５のエントリ並べ替え処理が実行されたときのデータ記憶領域の状態遷移の様子を示す図である。
【図７】実施の形態１に係るエントリ削除処理の手順を概略的に示すフローチャートである。
【図８】実施の形態１に係るエントリ登録処理の手順の一例を概略的に示すフローチャートである。
【図９】実施の形態１に係るエントリ登録処理の手順の他の例を概略的に示すフローチャートである。
【図１０】本発明に係る実施の形態２のデータ記憶領域の構成を示す図である。
【図１１】実施の形態２に係るエントリ削除処理の手順を概略的に示すフローチャートである。
【図１２】実施の形態２に係るエントリ登録処理の手順を概略的に示すフローチャートである。
【図１３】図１２のエントリ検索処理（ステップＳ３２６）の手順を示すフローチャートである。
【図１４】本発明に係る実施の形態３のデータ記憶領域の構成を示す図である。
【図１５】実施の形態３に係る制御処理の一例を概略的に示すフローチャートである。
【図１６】本発明に係る実施の形態４に係るエントリ更新処理の手順を概略的に示すフローチャートである。
【図１７】実施の形態４に係るエントリ更新処理が実行されたときのデータ記憶領域の状態遷移の様子を示す図である。
【図１８】実施の形態１〜４の変形例のデータ記憶領域の構成を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明に係る種々の実施の形態について図面を参照しつつ説明する。
【００１２】
実施の形態１．
図１は、本発明に係る実施の形態１のデータ処理システム１の概略構成を示す機能ブロック図である。このデータ処理システム１は、データ処理を実行する入出力装置１４と、そのデータ処理の際に参照される実体データを含むエントリデータを一時的に記憶するデータ記憶装置１１とを備える。入出力装置１４としては、たとえば、通信ネットワークにおいて通信データを処理する通信装置（中継装置や集線装置など）が挙げられるが、これらに限定されるものではない。データ処理にメモリを必要とする装置であれば、任意の装置にデータ記憶装置１１を適用することが可能である。
【００１３】
データ記憶装置１１は、複数のエントリデータを記憶する複数のデータ記憶領域を有するエントリ保持回路１２と、ＬＲＵアルゴリズムなどのメモリ管理アルゴリズムに基づいてエントリ保持回路１２に対するエントリデータの書き込み及び読み出しを制御するエントリ制御回路１３とを含む。エントリ制御回路１３は、メモリ管理アルゴリズムに基づいて複数のエントリデータのうち優先順位の最も低いエントリデータを選択し、選択されたエントリデータを無効化することによりエントリ保持回路１２内に空き領域を確保する機能を有する。
【００１４】
図２（Ａ），（Ｂ），（Ｃ）は、エントリ保持回路１２内のｎ個のデータ記憶領域Ｍ０，Ｍ１，Ｍ２，…，Ｍｎ−３，Ｍｎ−２，Ｍｎ−１（ｎは正整数）を模式的に示す図である。ここで、ｎは、エントリ保持回路１２に確保可能な最大エントリ数を示す整数値である。図２（Ａ）には６個以上のデータ記憶領域Ｍ０〜Ｍｎ−１が示されているが、少なくとも２個のデータ記憶領域が確保されていればよい。データ記憶領域Ｍ０〜Ｍｎ−１はそれぞれエントリデータを保持するための記憶容量を有する。また、データ記憶領域Ｍ０，Ｍ１，…，Ｍｎ−１には、エントリデータの優先順位に対応する順位（以下、アクセス順位と呼ぶ。）がそれぞれ割り当てられている。エントリ制御回路１３においては、データ記憶領域Ｍ０，Ｍ１，…，Ｍｎ−１に対してそれぞれのアクセス順位に対応する識別子＃（０），＃（１），…，＃（ｎ−３），＃（ｎ−２），＃（ｎ−１）が設定されている。エントリ制御回路１３は、これら識別子＃（０）〜＃（ｎ−１）に基づいて、データ記憶領域Ｍ０〜Ｍｎ−１に保持されているエントリデータにアクセスすることができる。
【００１５】
図２（Ａ）に示されるように、識別子＃（ｎ−１）を有するデータ記憶領域Ｍｎ−１のアクセス順位が最上位であり、この最上位のデータ記憶領域Ｍｎ−１に優先順位の最も高いエントリデータが格納される。ＬＲＵアルゴリズムが採用される場合には、最後に参照された時からの経過時間が短いほどエントリデータの優先順位は高くなる。また、識別子＃（０）を有するデータ記憶領域Ｍ０のアクセス順位が最下位であり、この最下位のデータ記憶領域Ｍ０に優先順位の最も低いエントリデータが格納される。後述するように、エントリ保持回路１２にエントリデータが登録されるとき、このエントリデータは、最初に最上位のデータ記憶領域Ｍｎ−１に記憶される。その後、エントリデータは、他のエントリデータの登録や更新や削除のたびに、上位のデータ記憶領域Ｍｉ（ｉは１〜ｎ−１のいずれかの整数）から１つ下位のデータ記憶領域Ｍｉ−１にシフトさせられる。
【００１６】
図２（Ｂ）は、識別子＃（ｉ）のデータ記憶領域Ｍｉの構成の一例を示す概略図である。図２（Ｂ）に示されるように、各データ記憶領域Ｍｉは、データ処理の際に参照される実体データ（エントリデータ本体）を格納するデータ領域２１と、データ記憶領域Ｍｉに保持されるエントリデータの有効性を示す制御フラグの一種である有効フラグを格納するフラグ領域２２とを有する。有効フラグは、エントリデータを有効にする有効値（たとえば「１」の値）及びエントリデータを無効にする無効値（たとえば「０」の値）のうちのいずれか一方の値を有する。以下、無効値を持つ有効フラグを「無効フラグ」と呼ぶこととする。また、エントリ制御回路１３は、フラグ領域２２に無効フラグを保持するデータ記憶領域Ｍｉをエントリの欠けた空き領域であると判断する。エントリ制御回路１３は、データ記憶領域Ｍｉのフラグ領域２２に無効フラグを書き込むことによりデータ記憶領域Ｍｉにおけるエントリを無効化して空き領域をつくることができる。
【００１７】
本実施の形態では、データ領域２１には、単一の実体データが格納されるが、これに限定されるものではない。データ領域２１は、構築すべきシステムに応じて、図２（Ｃ）に示されるように互いに関連する複数の実体データをそれぞれ格納する領域２１Ａ，２１Ｂ，…に機能的に分割されていてもよい。これにより、エントリ保持回路１２を検索テーブルとして利用することができる。たとえば、入出力装置１４がＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）に接続された集線装置の場合には、データ領域２１内の２つの領域２１Ａ，２１Ｂにアドレス検索テーブルの実体データを格納することができる。具体的には、データ領域２１内の２つの領域２１Ａ，２１Ｂに、データ送信元のＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）アドレスと通信ポート番号という２つの実体データを格納すれば、エントリ保持回路１２を、ＭＡＣアドレステーブルを保持するアドレス検索回路として利用できる。エントリ制御回路１３は、入出力装置１４からの問い合わせ要求に応じて、ＭＡＣアドレスに対応する通信ポート番号をエントリ保持回路１２から取得しこれを検索結果として返すことができる。
【００１８】
また、本実施の形態では、フラグ領域２２に単一の制御フラグ（有効フラグ）が格納されるが、これに限定されるものではない。図２（Ｃ）に示されるように、フラグ領域２２が複数の制御フラグを格納する領域２２Ａ，２２Ｂ，…を有していてもよい。後述するように実施の形態２，３では、フラグ領域２２に２種類の制御フラグが格納される。
【００１９】
図３は、エントリ制御回路１３の構成の一例を示す機能ブロック図であり、図４は、エントリ保持回路１２の好適な構成を示す図である。図３に示されるように、エントリ制御回路１３は、入出力装置１４との間でデータの送受信を行う送受信部１３１と、エントリ保持回路１２内の全てのデータ記憶領域Ｍ０〜Ｍｎ−１から並列に出力されたエントリデータ群３１を受信するエントリデータ受信部１３２と、エントリ更新制御部１３３とを含む。エントリデータ受信部１３２は、エントリ保持回路１２から受信したエントリデータ群３１を送受信部１３１とエントリ更新制御部１３３とに供給する。エントリ更新制御部１３３は、処理サイクルごとに、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいてエントリ保持回路１２の状態を把握し、エントリ保持回路１２の動作状態を制御することができる。ここで、１処理サイクルは、１クロックサイクルまたは所定数のクロックサイクルからなる。エントリ更新制御部１３３は、データ検索部１３３Ａ、領域検出部１３３Ｂ及びメモリ制御部１３３Ｃを含む。
【００２０】
また、エントリ更新制御部１３３は、制御データ群３２をエントリ保持回路１２に供給している。エントリ保持回路１２は、処理サイクルごとに、エントリ更新制御部１３３から供給された制御データ群３２に従って動作する。
【００２１】
送受信部１３１は、入出力装置１４からアクセス要求ＲＱを受信し解析する機能を有する。送受信部１３１は、アクセス要求ＲＱの解析結果をエントリ更新制御部１３３に出力する。エントリ更新制御部１３３は、その解析結果に応じた処理を実行し、その処理結果ＲＳを送受信部１３１を介して入出力装置１４に返す。アクセス要求ＲＱとしては、たとえば、エントリ登録指示、エントリ削除指示、有効エントリ数の通知指示、データ検索要求及びデータ読み出し指示が挙げられる。これらアクセス要求ＲＱのうち、データ検索要求、データ読み出し指示及び有効エントリ数の通知指示は、データ記憶領域Ｍ０〜Ｍｎ−１におけるエントリの変更を伴わないものである。
【００２２】
データ読み出し指示を含むアクセス要求ＲＱを受信したとき、送受信部１３１は、エントリデータ受信部１３２から供給されるエントリデータ群３１から全ての実体データを抽出し、これら実体データを入出力装置１４に送信する機能を有する。
【００２３】
送受信部１３１が検索キーデータ付きのデータ検索要求を含むアクセス要求ＲＱを受信したときは、データ検索部１３３Ａは、データ検索要求に応じて、エントリデータ受信部１３２から供給されるエントリデータ群３１のうち有効値を持つ有効フラグを含むエントリデータの中から検索キーデータと一致する実体データを検索し、その検索結果を送受信部１３１を介して入出力装置１４に返す。たとえば、エントリ保持回路１２が上記ＭＡＣアドレステーブルを保持する場合、データ検索部１３３Ａは、ＭＡＣアドレスを検索キーデータとして使用し、対応する通信ポート番号を検索結果として返すことができる。
【００２４】
有効エントリ数の通知指示を含むアクセス要求ＲＱが受信されたときは、データ検索部１３３Ａは、通知指示に応じて、エントリデータ受信部１３２から供給されるエントリデータ群３１のうち有効値を持つ有効フラグを含むエントリデータを計数し、その計数結果、すなわちエントリ保持回路１２における有効なエントリの数を送受信部１３１を介して入出力装置１４に通知する。
【００２５】
エントリ登録指示やエントリ削除指示といったエントリの変更を伴う指示（以下、エントリ操作指示と呼ぶ。）を含むアクセス要求ＲＱを送受信部１３１が受信されたときは、メモリ制御部１３３Ｃがそのエントリ操作指示に応じた処理を実行するエントリ操作機能を有する。
【００２６】
エントリ登録指示を含むアクセス要求ＲＱが受信されたとき、メモリ制御部１３３Ｃは、エントリ登録指示に応じて、最上位のデータ記憶領域Ｍｎ−１に無効フラグが保持されているか否かを判定する。領域検出部１３３Ｂは、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいて、データ記憶領域Ｍ０〜Ｍｎ−１の中から無効フラグを有する空き領域Ｍｅ（ｅは１〜ｎ−１の整数）を検出し、その検出結果をメモリ制御部１３３Ｃに与える機能を有する。メモリ制御部１３３Ｃは、領域検出部１３３Ｂによる検出結果から最上位のデータ記憶領域Ｍｎ−１に無効フラグが保持されているか否かを判定することができる。
【００２７】
データ記憶領域Ｍｎ−１が無効フラグを保持する空き領域であると判定した場合、メモリ制御部１３３Ｃは、有効値を持つ有効フラグと登録すべき実体データとを含むエントリデータを空き領域Ｍｎ−１に書き込む。これによりエントリの登録が完了する。一方、データ記憶領域Ｍｎ−１に無効フラグが保持されていない場合、言い換えれば、データ記憶領域Ｍｎ−１が有効値を持つ有効フラグを含むエントリデータを保持する場合は、メモリ制御部１３３Ｃは、先ず、最下位のデータ記憶領域Ｍ０に無効フラグを書き込む。その後、後述するシフト操作の実行によりデータ記憶領域Ｍ１〜Ｍｎ−１のエントリデータはそれぞれ１つ下位のデータ記憶領域Ｍ０〜Ｍｎ−２にシフトされるので、このシフト操作の実行後、メモリ制御部１３３Ｃは、有効値を持つ有効フラグと登録すべき実体データとを含むエントリデータを最上位のデータ記憶領域Ｍｎ−１に書き込む。これによりエントリの登録が完了する。
【００２８】
エントリ削除指示を含むアクセス要求ＲＱが受信されたときは、データ検索部１３３Ａが、このエントリ削除指示に応じて、エントリデータ受信部１３２から供給されるエントリデータ群３１のうち有効値を持つ有効フラグを含むエントリデータの中から特定データと一致する削除すべき実体データを検索する。データ検索部１３３Ａは、実体データを探し出すことができなかったときは、その検索結果を送受信部１３１を介して入出力装置１４に通知する。一方、実体データが探し出されたときは、メモリ制御部１３３Ｃが、その一致する実体データを保持するデータ記憶領域Ｍｄ（ｄは０〜ｎ−１の整数）に無効フラグを書き込むことでデータ記憶領域Ｍｄのエントリを無効化する。そして、メモリ制御部１３３Ｃは、その結果を送受信部１３１を介して入出力装置１４に通知する。この空き領域Ｍｄには、後述するシフト操作により１つ上位のデータ記憶領域Ｍｄ＋１に保持されているエントリデータがシフトさせられる。
【００２９】
全てのエントリの削除指示（一斉削除指示）を含むアクセス要求ＲＱが受信されたときは、メモリ制御部１３３Ｃは、１処理サイクル内に、データ記憶領域Ｍ０〜Ｍｎ−１の全てに無効フラグを書き込むことで全てのエントリを無効化し、一斉削除が完了した旨を送受信部１３１を介して入出力装置１４に通知する。
【００３０】
また、メモリ制御部１３３Ｃは、データ記憶領域Ｍ０〜Ｍｎ−１において有効値を持つ有効フラグを含むエントリデータを並び替えて（再配置して）有効なエントリを連続的に詰めて配置するエントリ並べ替え機能（エントリ再配置機能）を有する。具体的には、データ記憶領域Ｍ０〜Ｍｎ−１に対してエントリデータの書き込みが実行されない処理サイクル期間内に、メモリ制御部１３３Ｃは、空き領域Ｍｄの順位よりも上位のデータ記憶領域Ｍｄ＋１〜Ｍｎ−１に保持されているエントリデータを、１つ下位のデータ記憶領域Ｍｄ〜Ｍｎ−２にシフトさせるシフト操作を実行し、最上位のデータ記憶領域Ｍｎ−１に無効フラグを書き込む。シフト操作は、１処理サイクルで実行される。たとえば、識別子＃（１）のデータ記憶領域Ｍ１が空き領域である場合、メモリ制御部１３３Ｃは、空き領域Ｍ１よりも上位のデータ記憶領域Ｍ２〜Ｍｎ−１に保持されるエントリデータを、それぞれ、１つ下位のデータ記憶領域Ｍ１〜Ｍｎ−２にシフトさせる。あるいは、識別子＃（ｎ−２）のデータ記憶領域Ｍｎ−２が空き領域である場合は、メモリ制御部１３３Ｃは、空き領域Ｍｎ−２よりも上位のデータ記憶領域Ｍｎ−１に保持されているエントリデータを、１つ下位のデータ記憶領域Ｍｎ−２にシフトさせる。
【００３１】
このようなエントリ並べ替え機能により、データ記憶領域Ｍ０〜Ｍｎ−１において有効値を持つ有効フラグを含むエントリデータを連続的に配置する（並び替える）ことができ、有効値を持つ有効フラグを保持するデータ記憶領域間に空き領域が介在すること（空き領域の断片化）を解消することができる。また、最上位のデータ記憶領域Ｍｎ−１を含む上位のデータ記憶領域群をできるだけ空き領域にすることができる。上記のエントリ登録指示に応じて新規エントリを最上位のデータ記憶領域Ｍｎ−１に登録する際、最上位のデータ記憶領域Ｍｎ−１が空き領域であれば、シフト操作によりデータ記憶領域Ｍｎ−１が空き領域になるのを待つことなく、このデータ記憶領域Ｍｎ−１に実体データを書き込むことができる。
【００３２】
また、エントリ並べ替え機能により、有効値を持つ有効フラグを含むエントリデータが連続的に配置されるようになるので、データ検索指示や特定エントリの削除指示があったときに検索範囲を限定することができる。したがって、データ検索処理とエントリ削除処理の高速化を実現することができる。
【００３３】
次に、図４を参照しつつ、エントリ保持回路１２の好適な構成について説明する。エントリ保持回路１２は、ｎ段のレジスタ回路４００，…，４０ｎ−３，４０ｎ−２，４０ｎ−１を有するシフトレジスタ回路である。各レジスタ回路４０ｊ（ｊは０〜ｎ−１のうちの任意の整数）は、図４に示されるように、たとえばクロック信号に同期して動作するフリップ・フロップなどのレジスタ５０ｊと、エントリセレクタ６０ｊと、自エントリデータ制御回路７０ｊとを有する。レジスタ５００，…，５０ｎ−１はそれぞれ図２のデータ記憶領域Ｍ０，…，Ｍｎ−２，Ｍｎ−１を構成する記憶素子である。
【００３４】
エントリ制御回路１３は、制御データ群３２をエントリ保持回路１２に供給する。制御データ群３２は、エントリセレクタ６００，…，６０ｎ−２，６０ｎ−１にそれぞれ供給される選択制御信号ＳＥＬ０，…，ＳＥＬｎ−２，ＳＥＬｎ−１と、自エントリデータ制御回路７００，…，７０ｎ−２，７０ｎ−１にそれぞれ供給される制御信号Ｃ０，…，Ｃｎ−２，Ｃｎ−１とからなる。各エントリセレクタ６０ｊは、選択制御信号ＳＥＬｊの値に応じて３個の入力端子のいずれか１つに入力したデータを選択し、このデータをレジスタ５０ｊの入力端子に出力する機能を有する。
【００３５】
最上位のレジスタ回路４０ｎ−１では、エントリセレクタ６０ｎ−１の３個の入力端子には、エントリ制御回路１３から供給された登録データ（実体データ）ＯＤｎと、自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１と、レジスタ５０ｎ−１のフィードバック出力ＯＤｎ−１とが入力される。エントリセレクタ６０ｎ−１がレジスタ５０ｎ−１のフィードバック出力ＯＤｎ−１を選択したとき、レジスタ５０ｎ−１の出力端子と入力端子との間にフィードバックループが形成され、レジスタ５０ｎ−１は同一のビット値（エントリデータ）を保持し続ける。エントリセレクタ６０ｎ−１が自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１を選択したときは、レジスタ５０ｎ−１は、クロック信号のパルスエッジに応じて、自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１をラッチ（保持）する。そして、エントリセレクタ６０ｎ−１がエントリ制御回路１３から供給されたデータＯＤｎを選択したときは、レジスタ５０ｎ−１は、クロック信号のパルスエッジに応じてデータＯＤｎをラッチする。
【００３６】
自エントリデータ制御回路７０ｎ−１は、制御信号Ｃｎ−１に応じて、レジスタ５０ｎ−１に保持されているエントリデータの一部または全てを変更するための置換データＡＤｎ−１を生成する機能を有する。レジスタ５０ｎ−１の出力データＯＤｎ−１はフィードバックして自エントリデータ制御回路７０ｎ−１にも入力されている。自エントリデータ制御回路７０ｎ−１は、制御信号Ｃｎ−１の値に応じて有効値を持つ有効フラグ及び無効フラグのうちのいずれか一方の制御フラグと、フィードバック出力ＯＤｎ−１に含まれる実体データとを含むエントリデータＡＤｎ−１を構成し、このエントリデータＡＤｎ−１をエントリセレクタ６０ｎ−１に出力することができる。
【００３７】
一方、他のレジスタ回路４０ｋ（ｋは０〜ｎ−２のいずれか）では、エントリセレクタ６０ｋの３個の入力端子には、前段のレジスタ５０ｋ＋１の出力データＯＤｋ＋１と、自エントリデータ制御回路７０ｋの出力データＡＤｋと、レジスタ５０ｋの出力データＯＤｋとが入力される。エントリセレクタ６０ｋがレジスタ５０ｋのフィードバック出力ＯＤｋを選択したとき、レジスタ５０ｋの出力端子と入力端子との間にフィードバックループが形成され、レジスタ５０ｋは同一のビット値（エントリデータ）を保持し続ける。エントリセレクタ６０ｋが自エントリデータ制御回路７０ｋの出力データＡＤｋを選択したときは、レジスタ５０ｋは、クロック信号のパルスエッジに応じて、自エントリデータ制御回路７０ｋの出力データＡＤｋをラッチ（保持）する。そして、エントリセレクタ６０ｋが前段のレジスタ５０ｋ＋１の出力データＯＤｋ＋１を選択したときは、レジスタ５０ｋは、クロック信号のパルスエッジに応じてデータＯＤｋ＋１をラッチする。
【００３８】
自エントリデータ制御回路７０ｋは、制御信号Ｃｋに応じて、レジスタ５０ｋに保持されているエントリデータの一部または全部を変更するための置換データＡＤｋを生成する機能を有する。レジスタ５０ｋの出力データＯＤｋはフィードバックして自エントリデータ制御回路７０ｋにも入力されている。自エントリデータ制御回路７０ｋは、制御信号Ｃｋの値に応じて有効値を持つ有効フラグ及び無効フラグのうちのいずれか一方の制御フラグと、フィードバック出力ＯＤｋに含まれる実体データとを含むエントリデータＡＤｋを構成し、このエントリデータＡＤｋをエントリセレクタ６０ｎ−１に出力することができる。
【００３９】
レジスタ５００〜５０ｎ−１は、出力データＯＤ０〜ＯＤｎ−１からなるエントリデータ群３１をエントリ制御回路１３に並列に出力しているので、エントリ制御回路１３は、レジスタ５００〜５０ｎ−１に保持されている全てのエントリデータを一度に取得することができる。
【００４０】
エントリ制御回路１３は、制御データ群３２を供給することでエントリ保持回路１２の動作を制御することができる。エントリ登録指示やエントリ削除指示といったエントリ操作指示に応じた処理を実行しない処理サイクル期間には、メモリ制御部１３３Ｃは、全てのエントリセレクタ６００〜６０ｎ−１にレジスタ５００〜５０ｎ−１のフィードバック出力ＯＤ０〜ＯＤｎ−１を選択させる選択制御信号ＳＥＬ０〜ＳＥＬｎ−１を出力する。これによりレジスタ５００〜５０ｎ−１は同一のエントリデータ群を保持し続ける。
【００４１】
エントリデータを無効化してエントリ保持回路１２からエントリを削除するときは、メモリ制御部１３３Ｃは、無効化対象のエントリデータを保持するレジスタ回路４０ｄのエントリセレクタ６０ｄに自エントリデータ制御回路７０ｄの出力データＡＤｄを選択させる選択制御信号ＳＥＬｄを供給し、自エントリデータ制御回路７０ｄに無効フラグを含む置換データＡＤｄを生成させる制御信号Ｃｄを供給する。これによりレジスタ５０ｄは無効フラグを保持する。
【００４２】
エントリ登録指示に応じてエントリデータをエントリ保持回路１２に記憶させるときは、メモリ制御部１３３Ｃは、最上位のエントリセレクタ６０ｎ−１に置換データＯＤｎを選択させる選択制御信号ＳＥＬｎ−１を供給し、エントリセレクタ６０ｎ−１に新たなエントリデータを置換データＯＤｎとして供給する。レジスタ５０ｎ−１は、クロック信号のパルスエッジに応じて、エントリセレクタ６０ｎ−１を介して入力されたエントリデータＯＤｎをラッチ（保持）する。これにより、最上位のレジスタ５０ｎ−１にエントリデータが登録される。
【００４３】
データ記憶領域Ｍ０〜Ｍｎ−１内に空き領域Ｍｅが存在するとき、エントリ操作指示に応じたエントリデータの書き込みが実行されない処理サイクル期間内に、有効値を持つ有効フラグを含むエントリデータが再配置される。具体的には、メモリ制御部１３３Ｃは、空き領域Ｍｅを有するレジスタ回路４０ｅの順位よりも上位のレジスタ回路４０ｅ＋１〜４０ｎ−１内のレジスタ５０ｅ＋１〜５０ｎ−１の出力データＯＤｅ＋１〜ＯＤｎ−１を選択させる選択制御信号ＳＥＬｅ〜ＳＥＬｎ−２をエントリセレクタ６０ｅ〜６０ｎ−２に供給する。さらに、メモリ制御部１３３Ｃは、最上位のレジスタ回路４０ｎ−１のエントリセレクタ６０ｎ−１に自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１を選択させる選択制御信号ＳＥＬｎ−１を供給し、自エントリデータ制御回路７０ｎ−１に無効フラグを含む置換データＡＤｎ−１を生成させる制御信号Ｃｎ−１を供給する。これによりレジスタ５０ｅ〜５０ｎ−２は、それぞれ、前段のレジスタ５０ｅ＋１〜５０ｎ−１の出力データＯＤｅ＋１〜ＯＤｎ−１をラッチ（保持）するシフト動作を実行する。また、最上位のレジスタ５０ｎ−１に無効フラグが保持される。
【００４４】
次に、図５〜図９を参照しつつ、上記構成を有する実施の形態１のデータ記憶装置１１の動作を説明する。
【００４５】
図５は、入出力装置１４からのエントリ操作指示がない場合に実行されるエントリ並べ替え処理の手順を概略的に示すフローチャートであり、図６は、エントリ並べ替え処理が実行されたときのデータ記憶領域の状態遷移の様子を示す図である。また、図７は、エントリ削除指示に応じて実行されるエントリ削除処理の手順を概略的に示すフローチャートであり、図８及び図９は、エントリ登録指示に応じて実行されるエントリ登録処理の手順を概略的に示すフローチャートである。なお、データ検索要求、データ読み出し指示及び有効エントリ数の通知指示といったエントリの変更を伴わないアクセス要求ＲＱに対する処理は、エントリ保持回路１２がシフトレジスタ回路の構成を有するので、常時実行可能な処理である。これらの処理は、エントリ並べ替え処理、エントリ削除処理及びエントリ登録処理が実行される処理サイクル期間中でも、並行して実行することができる。
【００４６】
最初に、図５を参照しつつ、エントリ操作指示がない場合に実行されるエントリ並べ替え処理について説明する。エントリ更新制御部１３３のメモリ制御部１３３Ｃは、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいてエントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間にエントリ並べ替え処理を開始する。
【００４７】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ１０１）。次に、メモリ制御部１３３Ｃは、識別子＃（ｉ）を有するレジスタ回路４０ｉに保持されているエントリデータ（以下、識別子＃（ｉ）のエントリデータと呼ぶ。）が無効であるか否かを判定する（ステップＳ１０３）。識別子＃（ｉ）のエントリデータが有効であると判定したとき（ステップＳ１０３のＮＯ）、メモリ制御部１３３Ｃは、変数ｉがｎ−２に達したかどうかを判定する（ステップＳ１１５）。変数ｉがｎ−２に達したとき（ステップＳ１１５のＹＥＳ）、エントリ並べ替え処理は終了する。一方、変数ｉがｎ−２に達していないとき（ステップＳ１１５のＮＯ）、メモリ制御部１３３Ｃは、変数ｉを１だけインクリメントし（ステップＳ１１７）、ステップＳ１０３に手順を戻す。
【００４８】
最下位のエントリデータから上位のエントリデータに向かって順番に無効か否かの判定（ステップＳ１０３）を実行した結果、無効フラグを含む無効なエントリデータが存在していたとき（ステップＳ１０３のＹＥＳ）、メモリ制御部１３３Ｃは、変数ｊに変数ｉの値を設定する（ステップＳ１０５）。次いで、メモリ制御部１３３Ｃは、識別子＃（ｊ）のエントリに識別子＃（ｊ＋１）のエントリデータをシフトさせる制御を実行する（ステップＳ１０７）。具体的には、メモリ制御部１３３Ｃは、識別子＃（ｊ）を有するレジスタ回路４０ｊのエントリセレクタ６０ｊに、識別子＃（ｊ＋１）を有する前段レジスタ回路４０ｊ＋１の出力データＯＤｊ＋１を選択させる選択制御信号ＳＥＬｊを供給する。次いで、変数ｊを１だけインクリメントする（ステップＳ１０９）。その後、メモリ制御部１３３Ｃは、変数ｊが最上位のレジスタ回路４０ｎ−１の識別子番号ｎ−１に達したか否かを判定する（ステップＳ１１１）。変数ｊがｎ−１に達していなければ（ステップＳ１１１のＮＯ）、処理手順はステップＳ１０７に戻る。このようにステップＳ１１１で変数ｊがｎ−１に達するとの判定（ステップＳ１１１のＹＥＳ）がなされるまで、上記ステップＳ１０７，Ｓ１０９の処理が繰り返し実行される。この結果、レジスタ５０ｉ〜５０ｎ−２は、それぞれ、前段のレジスタ５０ｉ＋１〜５０ｎ−１の出力データＯＤｉ＋１〜ＯＤｎ−１をラッチ（保持）するシフト動作を実行する。
【００４９】
シフト動作の実行後（ステップＳ１１１のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）の最上位エントリを無効化する（ステップＳ１１３）。具体的には、メモリ制御部１３３Ｃは、最上位のレジスタ回路４０ｎ−１のエントリセレクタ６０ｎ−１に自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１を選択させる選択制御信号ＳＥＬｎ−１を供給し、自エントリデータ制御回路７０ｎ−１に無効フラグを含む置換データＡＤｎ−１を生成させる制御信号Ｃｎ−１を供給する。これによりレジスタ５０ｎ−１に無効フラグが保持される。その後、ステップＳ１１５で変数ｉがｎ−２に達するとの判定（ステップＳ１１５のＹＥＳ）がなされるまで、ステップＳ１１７以後の処理が実行される。
【００５０】
図６（Ａ）〜（Ｃ）は、上記エントリ並べ替え処理が実行されたときに、最大エントリ数ｎが７の場合のデータ記憶領域Ｍ０〜Ｍ６の状態遷移の様子を示す図である。図６（Ａ）に示すように、最初の状態では、識別子＃（１），＃（２），＃（４）のエントリが有効であり、その他のエントリは無効であるとする。
【００５１】
上記エントリ並べ替え処理の実行により、先ず、識別子＃（ｉ＝０）のエントリデータが無効であると判定される（ステップＳ１０３のＹＥＳ）。次いで、識別子＃（０）のエントリに識別子＃（１）のエントリデータをシフトさせ、識別子＃（１）のエントリに識別子＃（２）のエントリデータをシフトさせ、識別子＃（２）のエントリに識別子＃（３）のエントリデータをシフトさせ、識別子＃（３）のエントリに識別子＃（４）のエントリデータをシフトさせ、識別子＃（４）のエントリに識別子＃（５）のエントリデータをシフトさせ、識別子＃（５）のエントリに識別子＃（６）のエントリデータをシフトさせるというシフト操作が実行される（ステップＳ１０５〜Ｓ１１１）。その後、識別子＃（６）のエントリの無効化処理が実行される（ステップＳ１１３）。これにより、図６（Ｂ）に示されるように識別子＃（０），＃（１），＃（３）のエントリに有効なエントリデータがシフトする。以上のシフト操作及びエントリの無効化処理は、最初の処理サイクル期間内に実行される。
【００５２】
次の処理サイクル期間では、識別子＃（ｉ＝２）のエントリデータが無効であると判定される（ステップＳ１０３のＹＥＳ）。次いで、識別子＃（２）のエントリに識別子＃（３）のエントリデータをシフトさせ、識別子＃（３）のエントリに識別子＃（４）のエントリデータをシフトさせ、識別子＃（４）のエントリに識別子＃（５）のエントリデータをシフトさせ、識別子＃（５）のエントリに識別子＃（６）のエントリデータをシフトさせるというシフト操作が実行される（ステップＳ１０５〜Ｓ１１１）。その後、識別子＃（６）のエントリの無効化処理が実行される（ステップＳ１１３）。この結果、図６（Ｃ）に示されるように識別子＃（０），＃（１），＃（２）のエントリに有効なエントリデータがシフトする。
【００５３】
次の処理サイクル期間では、識別子＃（ｉ＝３）のエントリデータが無効であると判定される（ステップＳ１０３のＹＥＳ）。次いで、識別子＃（３）のエントリに識別子＃（４）のエントリデータをシフトさせ、識別子＃（４）のエントリに識別子＃（５）のエントリデータをシフトさせ、識別子＃（５）のエントリに識別子＃（６）のエントリデータをシフトさせるというシフト操作が実行される（ステップＳ１０５〜Ｓ１１１）。その後、識別子＃（６）のエントリの無効化処理が実行される（ステップＳ１１３）。
【００５４】
メモリ制御部１３３Ｃは、上記エントリ並べ替え処理を、エントリデータの書き込みを実行しない処理サイクル期間に常に実行することで、図６（Ｃ）に示すように有効なエントリが詰まって配置された状態を実現することができる。図６（Ａ）〜（Ｃ）に示したように、エントリデータの並び替えが完了するまで複数の処理サイクルを要することになるが、図４に示したように、レジスタ５００〜５０ｎ−１はエントリデータ群３１をエントリ制御回路１３に供給しているので、並び替え処理を中断することなく、エントリデータ群３１を読み出すことができる。
【００５５】
次に、図７を参照しつつ、特定データと一致する実体データを含むエントリデータを無効化するためのエントリ削除処理について説明する。
【００５６】
エントリ保持回路１２は、シフトレジスタ回路の構成を有し、エントリデータをシフトさせるので、ある処理サイクル期間に識別子＃（ｉ）のデータ記憶領域Ｍｉに存在していたエントリデータが、その次の処理サイクル期間に同じ識別子＃（ｉ）のデータ記憶領域Ｍｉに存在している保証はない。そのため、本実施の形態では、特定データを検索キーとした検索を実行して削除対象となるエントリを特定する方法が採用される。入出力装置１４からエントリ削除指示を含むアクセス要求ＲＱが受信されると、メモリ制御部１３３Ｃは、このエントリ削除指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間にエントリ削除処理を開始する。
【００５７】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ２０１）。次に、メモリ制御部１３３Ｃは、レジスタ回路４０ｉに保持されている識別子＃（ｉ）のエントリデータが、特定データと一致する削除すべき実体データを含むか否かを判定する（ステップＳ２０３）。エントリデータが削除すべき実体データを含まない場合（ステップＳ２０３のＮＯ）、メモリ制御部１３３Ｃは、変数ｉが最上位のエントリを指す識別子番号ｎ−１に達したか否かを判定し（ステップＳ２０９）、変数ｉがｎ−１に達していなければ（ステップＳ２０９のＮＯ）、変数ｉを１だけインクリメントして（ステップＳ２１３）、処理手順をステップＳ２０３に戻す。全てのエントリについて削除すべき実体データを含むエントリデータを探し出すことができなかったときは、変数ｉはｎ−１に達する（ステップＳ２０９のＹＥＳ）。このとき、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に削除不能の旨を通知し（ステップＳ２１１）、エントリ削除処理を終了する。
【００５８】
一方、識別子＃（ｉ）のエントリデータが削除すべき実体データを含むと判定された場合（ステップＳ２０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリを無効化する（ステップＳ２０５）。具体的には、データ検索部１３３Ａは、削除すべき実体データを保持するデータ記憶領域Ｍｉに無効フラグを書き込む。その後、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に削除完了の旨を通知し（ステップＳ２０７）、エントリ削除処理を終了する。
【００５９】
なお、上記エントリ削除処理は、エントリ保持回路１２において同一の実体データが重複して記憶されていない場合に適用されるものである。そのため、ステップＳ２０３において識別子＃（ｉ）のエントリデータが削除すべき実体データを含むと判定されれば、識別子＃（ｉ＋１）のエントリに削除すべき実体データが存在しないことが保証されている。同一の実体データの重複が許可されている場合には、ステップＳ２０５の実行後、メモリ制御部１３３Ｃは、変数ｉをインクリメントしてステップＳ２０３を実行する手順を採用することができる。
【００６０】
次に、図８を参照しつつ、エントリ保持回路１２に実体データを登録するためのエントリ登録処理について説明する。メモリ制御部１３３Ｃは、入出力装置１４からのエントリ登録指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間でエントリ登録処理を開始する。
【００６１】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ３０１）。次に、メモリ制御部１３３Ｃは、レジスタ回路４０ｉに保持されている識別子＃（ｉ）のエントリデータが、登録すべき特定データと一致する実体データを含むか否かを判定する（ステップＳ３０３）。エントリデータが当該実体データを含まない場合（ステップＳ３０３のＮＯ）、メモリ制御部１３３Ｃは、変数ｉが最上位のエントリを指す識別子番号ｎ−１に達したか否かを判定し（ステップＳ３２１）、変数ｉがｎ−１に達していなければ（ステップＳ３２１のＮＯ）、変数ｉを１だけインクリメントして（ステップＳ３２３）、処理手順をステップＳ３０３に戻す。
【００６２】
一方、識別子＃（ｉ）のエントリデータが、登録すべき特定データと一致する実体データを含むと判定された場合（ステップＳ３０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリを無効化する（ステップＳ３０５）。具体的には、データ検索部１３３Ａは、当該実体データを保持するデータ記憶領域Ｍｉに無効フラグを書き込む。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）のエントリが無効化されるまで待機する（ステップＳ３０７のＮＯ）。
【００６３】
識別子＃（ｎ−１）のエントリの無効化が完了したとき（ステップＳ３０７のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）のエントリ（空きエントリ）への特定データの書き込み制御を行う（ステップＳ３０９）。具体的には、メモリ制御部１３３Ｃは、最上位のエントリセレクタ６０ｎ−１に置換データＯＤｎを選択させる選択制御信号ＳＥＬｎ−１を供給し、エントリセレクタ６０ｎ−１に特定データを含む新たなエントリデータを置換データＯＤｎとして供給する。これによりレジスタ５０ｎ−１は、エントリセレクタ６０ｎ−１を介して入力されたエントリデータＯＤｎをラッチ（保持）する。その後、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に更新完了の旨を通知し（ステップＳ３１１）、エントリ登録処理を終了する。
【００６４】
一方、全てのエントリについて、登録すべき特定データと一致する実体データを含むエントリデータを探し出すことができなかったときは、変数ｉはｎ−１に達する（ステップＳ３０３のＮＯ及びステップＳ３２１のＹＥＳ）。このとき、メモリ制御部１３３Ｃは、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいて、識別子＃（ｎ−１）の最上位のエントリが無効か否かを判定する（ステップＳ３２５）。最上位のエントリが無効である場合（ステップＳ３２５のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）のエントリへの特定データの書き込み制御を行う（ステップＳ３３１）。その後、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に登録完了の旨を通知し（ステップＳ３３３）、エントリ登録処理を終了する。
【００６５】
上記ステップＳ３２５において最上位のエントリが無効ではない場合（ステップＳ３２５のＮＯ）、メモリ制御部１３３Ｃは、識別子＃（０）の最下位のエントリを無効化する（ステップＳ３２７）。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）のエントリが無効化されるまで待機する（ステップＳ３２９のＮＯ）。識別子＃（ｎ−１）のエントリの無効化が完了したとき（ステップＳ３２９のＹＥＳ）、メモリ制御部１３３Ｃは、ステップＳ３３１，Ｓ３３３を順次実行し、エントリ登録処理を終了する。
【００６６】
上記の図８のエントリ登録処理は、エントリ保持回路１２に同一の実体データが重複して記憶されることを許可しない場合の処理である。図９は、エントリ保持回路１２において同一の実体データが重複することを許可する場合のエントリ登録処理の手順を概略的に示すフローチャートである。図９のフローチャートは、図８のステップＳ３０３〜３１１が存在しない点を除いて図８のフローチャートと同じである。図８のステップＳ３０３の判定処理が行われないため、特定データは常に登録される。
【００６７】
なお、図２（Ｃ）に示したようにデータ領域２１が、複数の実体データを格納する複数の領域に機能的に分割されている場合、メモリ制御部１３３Ｃは、これら複数の実体データのうちの一部を書き換えることもできる。具体的には、メモリ制御部１３３Ｃは、レジスタ回路４０ｉのエントリセレクタ６０ｉに自エントリデータ制御回路７０ｉの出力データＡＤｉを選択させる選択制御信号ＳＥＬｉを供給し、自エントリデータ制御回路７０ｉにフィードバック出力ＯＤｉの中の複数の実体データの一部を別の実体データに置換させる制御信号Ｃｉを供給する。ここで、メモリ制御部１３３Ｃは、当該別の実体データを制御信号Ｃｉに含めて自エントリデータ制御回路７０ｉに供給することができる。たとえば、上記したように入出力装置１４が集線装置であり、ＭＡＣアドレスと通信ポート番号との対応関係を登録するアドレス検索回路としてエントリ保持回路１２を使用する場合、メモリ制御部１３３Ｃは、ＭＡＣアドレスに対応する通信ポート番号を書き換えることができる。また、メモリ制御部１３３Ｃは、必ず、エントリ保持回路１２に保持されているエントリデータ群３１の内容を確認することができるので、特定の対応関係を有する実体データの組み合わせをエントリ保持回路１２に保持させないようにすることができる。たとえば、エントリ保持回路１２において、１つのＭＡＣアドレスが関連付けられた通信ポート番号が複数個存在しないように制御することができる。
【００６８】
以上に説明したように、実施の形態１のデータ記憶装置１１では、エントリ制御回路１３のメモリ制御部１３３Ｃは、データ記憶領域Ｍ０〜Ｍｎ−１に対してエントリデータの書き込みを実行しない処理サイクル期間に、データ記憶領域Ｍ０〜Ｍｎ−１の中の空き領域Ｍｅの順位よりも上位のデータ記憶領域Ｍｅ＋１〜Ｍｎ−１に保持されているエントリデータを、下位のデータ記憶領域にシフトさせるシフト操作を行い、最上位のデータ記憶領域Ｍｎ−１に無効フラグを書き込む。これにより、有効値を持つ有効フラグを含むエントリデータを連続的に配置することができ、最上位のデータ記憶領域Ｍｎ−１を含む上位のデータ記憶領域を空き領域にすることができる。よって、上記特許文献２（特許第４３６９５２４号明細書）に開示されている技術のようにメモリ管理制御のために別の記憶領域を確保する必要がない。また、メモリ制御部１３３Ｃは有効なエントリを連続的に再配置して上位の空き領域を形成するので、データ検索処理、エントリ登録処理（図８及び図９）及びエントリ削除処理（図７）の処理速度を高速化することができる。データ記憶装置１１を実装する際には、エントリデータの登録や削除（無効化）といった操作と、エントリデータに対するシフト操作とが競合しないようにシステムを容易に設計することができ、しかも、ＬＲＵアルゴリズムなどのメモリ管理アルゴリズムに基づく制御に必要な記憶領域を別に確保せずに済むという利点がある。
【００６９】
また、エントリ保持回路１２がシフトレジスタ回路の構成を有しているので、エントリ制御回路１３は、メモリ制御部１３３Ｃによるエントリ保持回路１２に対する操作に影響を与えることなく、レジスタ５００〜５０ｎ−１の並列出力（エントリデータ群３１）から所望の実体データを取得する（読み出す）ことができる。また、メモリ制御部１３３Ｃは、レジスタ５００〜５０ｎ−１の並列出力に基づいて、エントリ保持回路１２の動作状態及び記憶内容を常時監視しながら最適な制御を行うこともできる。
【００７０】
したがって、実施の形態１のデータ記憶装置１１は、メモリ管理アルゴリズムに基づく制御を少ないメモリ消費量で効率良く実行することができる。特に、ＬＲＵアルゴリズムに基づく完全な制御を少ないメモリ消費量で効率良く実行することが可能である。
【００７１】
実施の形態２．
次に、本発明に係る実施の形態２について説明する。実施の形態２のデータ記憶装置の構成は、動作モードが異なる点を除いて、実施の形態１のデータ記憶装置１１の構成と同一である。実施の形態１については、エントリ保持回路１２におけるデータ記憶領域Ｍｉのフラグ領域２２が単一の制御フラグ（有効フラグ）を格納する場合の動作を説明した。本実施の形態では、データ記憶領域Ｍｉのフラグ領域２２は、図１０（Ａ），（Ｂ）に示されるように２つの領域２２Ａ，２２Ｂに機能的に分割されており、一方の領域２２Ａには上記有効フラグが格納され、他方の領域２２Ｂには静的フラグが格納される。静的フラグは、データ記憶領域Ｍｉに保持されるエントリデータの無効化を許可する許可値（たとえば「０」の値）と、エントリデータの無効化を許可しないマスク値（たとえば「１」の値）とのうちのいずれか一方を有するものである。
【００７２】
エントリ更新制御部１３３のメモリ制御部１３３Ｃは、上記実施の形態１に関して説明したエントリ登録処理やエントリ削除処理の際に、マスク値を持つ静的フラグを保持するデータ記憶領域Ｍｍ（ｍは０〜ｎ−１のいずれかの整数）を検出した場合には、そのデータ記憶領域Ｍｍに無効フラグを書き込まない、言い換えれば、データ記憶領域Ｍｍにおける登録済みのエントリを無効化しない機能を有する。これにより、データ記憶領域Ｍ０〜Ｍｎ−１のフラグ領域２２に要する記憶容量が増加するものの、より柔軟にエントリデータの登録や削除（無効化）などの操作を行うことが可能となる。
【００７３】
静的フラグは、新規の実体データの登録の際に設定される。実体データと無効フラグと静的フラグとを含むエントリデータがエントリ保持回路１２に登録された後、メモリ制御部１３３Ｃは、静的フラグの値に基づいて、登録済みのエントリデータに対する削除操作を行うのか否かを決めることができる。このため、メモリ管理アルゴリズムに基づく制御に関わらず、変更されないエントリデータをエントリ保持回路１２に記憶させることができる。
【００７４】
以下、図１１〜図１３を参照しつつ、実施の形態２のデータ記憶装置１１の動作を説明する。図１１は、実施の形態２に係るエントリ削除処理の手順を概略的に示すフローチャートである。図１１のフローチャートは、ステップＳ２０４，Ｓ２１４を除いて、図７のフローチャートと同じ手順を有する。また、図１２は、実施の形態２に係るエントリ登録処理の手順を概略的に示すフローチャートであり、図１３は、図１２のエントリ検索処理（ステップＳ３２６）の手順を示すフローチャートである。図１３のフローチャートは接続子Ｃ１を介して図１２のフローチャートと接続されている。また、図１２のフローチャートは、ステップＳ３０４，Ｓ３２６，Ｓ３２８，Ｓ３３５を除いて、図８のフローチャートと同じ手順を有する。
【００７５】
最初に、図１１を参照しつつ、エントリ削除処理について説明する。入出力装置１４からエントリ削除指示を含むアクセス要求ＲＱが受信されると、メモリ制御部１３３Ｃは、このエントリ削除指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間にエントリ削除処理を開始する。
【００７６】
ステップＳ２０３で識別子＃（ｉ）のエントリデータが削除すべき実体データを含むと判定された場合（ステップＳ２０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）を有するレジスタ回路４０ｉに保持されている静的フラグ（以下、識別子＃（ｉ）の静的フラグと呼ぶ。）が有意か否かを判定する（ステップＳ２０４）。静的フラグが有意である場合、すなわち、静的フラグがマスク値を有する場合（ステップＳ２０４のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリの無効化（ステップＳ２０５）を実行せずに、静的フラグによる更新不能の旨を送受信部１３１を介して入出力装置１４に通知し（ステップＳ２１４）、エントリ削除処理を終了する。一方、静的フラグが有意でない場合（ステップＳ２０４のＮＯ）、メモリ制御部１３３Ｃは、ステップＳ２０５，Ｓ２０７を実行した後に、エントリ削除処理を終了する。
【００７７】
ところで、メモリ制御部１３３Ｃは、静的フラグを参照せずにエントリ削除を実行する動作モードをも有する。具体的には、入出力装置１４からエントリ強制削除指示を含むアクセス要求ＲＱが受信されたとき、メモリ制御部１３３Ｃは、このエントリ強制削除指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に、静的フラグを参照するエントリ削除処理（図１１）ではなく、図７のエントリ削除処理を実行する。これにより、状況に応じて、有意な静的フラグを含むエントリデータを強制的に無効化して空き領域を確保することができる。
【００７８】
次に、図１２及び図１３を参照しつつ、特定データと一致する実体データを含むエントリデータを登録するためのエントリ登録処理について説明する。入出力装置１４からエントリ登録指示を含むアクセス要求ＲＱが受信されると、メモリ制御部１３３Ｃは、このエントリ登録指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に図１２のエントリ登録処理を開始する。
【００７９】
ステップＳ３０３で識別子＃（ｉ）のエントリデータが、登録すべき特定データと一致する実体データを含むと判定された場合（ステップＳ３０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）を有するレジスタ回路４０ｉに保持されている静的フラグが有意か否かを判定する（ステップＳ３０４）。静的フラグが有意である場合、すなわち、静的フラグがマスク値を有する場合（ステップＳ３０４のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリの無効化（ステップＳ３０５）をせずに、静的フラグによる更新不能の旨を送受信部１３１を介して入出力装置１４に通知し（ステップＳ３３５）、エントリ登録処理を終了する。
【００８０】
一方、全識別子＃（０）〜＃（ｎ−１）のエントリデータが、登録すべき特定データと一致する実体データを含まず、識別子＃（ｎ−１）のエントリが有効であると判定した場合（ステップＳ３２５のＮＯ）、メモリ制御部１３３Ｃは、空き領域をつくるためにエントリ検索処理（ステップＳ３２６）を実行する。
【００８１】
図１３を参照すると、メモリ制御部１３３Ｃは、変数ｋにゼロ値を設定し（ステップＳ３４１）、識別子＃（ｋ）の静的フラグが有意か否かを判定する（ステップＳ３４２）。識別子＃（ｋ）の静的フラグが有意である場合（ステップＳ３４２のＹＥＳ）、メモリ制御部１３３Ｃは、変数ｋが最上位のエントリを指す識別子番号ｎ−１に達したか否かを判定し（ステップＳ３４３）、変数ｋがｎ−１に達していなければ（ステップＳ３４３のＮＯ）、変数ｋを１だけインクリメントして（ステップＳ３４５）、手順をステップＳ３４２に戻す。
【００８２】
図１３のフローチャートにおいて全識別子＃（０）〜＃（ｎ−１）の静的フラグが有意である場合は、変数ｋはｎ−１に達する（ステップＳ３４３のＹＥＳ）。この場合、メモリ制御部１３３Ｃは、登録不能の旨を送受信部１３１を介して入出力装置１４に通知し（ステップＳ３４７）、エントリ登録処理を終了する。なお、登録不能の旨の通知（ステップＳ３４７）に代えて、別の処理を行うことも可能である。
【００８３】
ステップＳ３４２で識別子＃（ｋ）の静的フラグが有意ではないと判定した場合（ステップＳ３４２のＮＯ）、メモリ制御部１３３Ｃは、図１２のフローチャートに処理を戻す。次いで、メモリ制御部１３３Ｃは、識別子＃（ｋ）のエントリを無効化する（ステップＳ３２８）。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）のエントリが無効化されるまで待機する（ステップＳ３２９のＮＯ）。識別子＃（ｎ−１）のエントリの無効化が完了したとき（ステップＳ３２９のＹＥＳ）、メモリ制御部１３３Ｃは、ステップＳ３３１，Ｓ３３３を順次実行し、エントリ登録処理を終了する。
【００８４】
ところで、メモリ制御部１３３Ｃは、静的フラグを参照せずにエントリ登録を実行する動作モードを有する。具体的には、入出力装置１４からエントリ強制登録指示を含むアクセス要求ＲＱが受信されたとき、メモリ制御部１３３Ｃは、このエントリ強制登録指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に、静的フラグを参照するエントリ登録処理（図１２及び図１３）ではなく、図８のエントリ登録処理を実行する。これにより、状況に応じて、静的フラグの値に関わりなくエントリ登録を強制的に行うことができる。
【００８５】
以上に説明したように実施の形態２によれば、特定のエントリデータが変更されないようにすることができるので、エントリデータの登録や削除（無効化）などの操作の柔軟性を向上させることができる。
【００８６】
なお、メモリ制御部１３３Ｃは、データ記憶領域Ｍ０〜Ｍｎ−１のうち有意な静的フラグを保持しないデータ記憶領域に無効フラグを書き込むことで、有意ではない静的フラグを含むエントリデータを一斉に削除する操作を簡易に組み込むこともできる。
【００８７】
実施の形態３．
次に、本発明に係る実施の形態３について説明する。実施の形態３のデータ記憶装置の構成は、動作モードが異なる点を除いて、実施の形態１のデータ記憶装置１１の構成と同一である。実施の形態１については、エントリ保持回路１２におけるデータ記憶領域Ｍｉのフラグ領域２２が単一の制御フラグ（有効フラグ）を格納する場合の動作を説明した。本実施の形態では、データ記憶領域Ｍｉのフラグ領域２２は、図１４（Ａ），（Ｂ）に示されるように２つの領域２２Ａ，２２Ｂに機能的に分割されており、一方の領域２２Ａには上記有効フラグが格納され、他方の領域２２Ｂには削除フラグが格納される。削除フラグは、データ記憶領域Ｍｉに保持されているエントリデータの無効化が予定されていることを示す有効値（たとえば「１」の値）と、データ記憶領域Ｍｉに保持されているエントリデータの無効化が予定されていないことを示す無効値（たとえば「０」の値）とのうちのいずれか一方の値を有する。以下、有効値を持つ削除フラグを「有効な削除フラグ」と呼び、無効値を持つ削除フラグを「無効な削除フラグ」と呼ぶこととする。
【００８８】
メモリ制御部１３３Ｃは、或る処理サイクル期間ＴＡにデータ記憶領域Ｍ０〜Ｍｎ−１の全部または一部に有効な削除フラグを書き込み、所定の設定期間ΔＴ経過後の処理サイクル期間ＴＢに、有効な削除フラグを保持する当該データ記憶領域の全てに無効フラグを書き込むことにより有効な削除フラグを含むエントリデータを一括して無効化（削除）する機能を有する。これにより、エントリ保持回路１２に空き領域をまとめて確保することができる。ただし、メモリ制御部１３３Ｃは、設定期間ΔＴ内にエントリデータのいずれかを更新したとき、当該更新されたエントリデータを保持するデータ記憶領域には無効な削除フラグを書き込む。設定期間ΔＴ内に登録されたエントリデータはいずれも無効な削除フラグを含む。よって、設定期間ΔＴ経過後の処理サイクル期間ＴＢでは、設定期間ΔＴ内に更新または登録されたエントリデータが無効化（削除）されない。
【００８９】
また、メモリ制御部１３３Ｃは、外部の入出力装置１４から削除フラグ付与指示を含むアクセス要求ＲＱが受信されたとき、この削除フラグ付与指示に応じて、データ記憶領域Ｍ０〜Ｍｎ−１の全部または一部に有効な削除フラグを書き込み、所定の設定期間ΔＴ経過後の処理サイクル期間に、有効な削除フラグを保持する当該データ記憶領域の全てに無効フラグを書き込むことにより有効な削除フラグを含むエントリデータを一括して削除する機能をも有する。この場合も、メモリ制御部１３３Ｃは、設定期間ΔＴ内にエントリデータのいずれかを更新したとき、当該更新されたエントリデータを保持するデータ記憶領域には無効な削除フラグを書き込む。また、設定期間ΔＴ内に登録されたエントリデータはいずれも無効な削除フラグを含む。
【００９０】
さらに、メモリ制御部１３３Ｃは、外部の入出力装置１４からの空き領域確保指示に応じて、設定期間ΔＴの経過を待つことなく、有効な削除フラグを保持する当該データ記憶領域の全てに無効フラグを書き込むことにより有効な削除フラグを含むエントリデータを一括して無効化（削除）する機能をも有する。
【００９１】
上記機能を有することにより、データ記憶装置１１は、エントリ保持回路１２の空き領域をまとめて確保する制御を行うことができる。たとえば、エントリ保持回路１２が有効なエントリで満杯となる前であっても、登録または更新されてから一定期間経過したエントリデータを自動的に抹消し、優先順位の低いエントリデータをエントリ保持回路１２内に残さないような制御を行うことができる。
【００９２】
次に、図１５を参照しつつ、上記削除フラグを使用する実施の形態３のデータ記憶装置１１の動作を説明する。図１５は、実施の形態３に係るエントリ操作の制御処理の一例を概略的に示すフローチャートである。或る時刻に達したとき、あるいは、外部の入出力装置１４から削除フラグ付与指示を含むアクセス要求ＲＱが受信されたとき、これに応じて図１５の制御処理が開始される。
【００９３】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ４０１）。次に、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリに有効な削除フラグを設定する（ステップＳ４０３）。具体的には、メモリ制御部１３３Ｃは、識別子＃（ｉ）のレジスタ回路４０ｉ（図４）のエントリセレクタ６０ｉに自エントリデータ制御回路７０ｉの出力データＡＤｉを選択させる選択制御信号ＳＥＬｉを供給し、自エントリデータ制御回路７０ｉに有効な削除フラグを含む置換データＡＤｉを生成させる制御信号Ｃｉを供給する。有効な削除フラグの設定（ステップＳ４０３）の後、変数ｉが識別子番号ｎ−１に達したか否かを判定する（ステップＳ４０５）。変数ｉがｎ−１に達していなければ（ステップＳ４０５のＮＯ）、メモリ制御部１３３Ｃは、変数ｉを１だけインクリメントし（ステップＳ４０７）、手順をステップＳ４０３に戻す。
【００９４】
変数ｉがｎ−１に達すると（ステップＳ４０５のＹＥＳ）、メモリ制御部１３３Ｃは、設定期間ΔＴが経過して設定時刻が到来するまで待機する（ステップＳ４０９のＮＯ）。設定時刻が到来すると（ステップＳ４０９のＹＥＳ）、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ４１１）。次に、メモリ制御部１３３Ｃは、識別子＃（ｉ）の削除フラグが有効であるか否かを判定する（ステップＳ４１３）。削除フラグが有効であれば（ステップＳ４１３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリを無効化する（ステップＳ４１５）。次いで、変数ｉがｎ−１に達したか否かを判定する（ステップＳ４１７）。一方、削除フラグが有効でなければ（ステップＳ４１３のＮＯ）、メモリ制御部１３３Ｃは、エントリの無効化（ステップＳ４１５）をスキップして、変数ｉがｎ−１に達したか否かを判定する（ステップＳ４１７）。変数ｉがｎ−１に達していなければ（ステップＳ４１７のＮＯ）、メモリ制御部１３３Ｃは、変数ｉを１だけインクリメントし（ステップＳ４１９）、手順をステップＳ４１３に戻す。その後、変数ｉがｎ−１に達すると（ステップＳ４１７のＹＥＳ）、処理を終了する。
【００９５】
以上の処理により、一定期間経過後、登録あるいは更新のなされていないエントリデータの削除を行うことができる。なお、上記ステップＳ４０１〜Ｓ４０７の処理は１処理サイクル期間内に完了し、ステップＳ４１１〜Ｓ４１７の処理も１処理サイクル期間内に完了する。
【００９６】
ところで、上記制御処理においては、有効な削除フラグを含むエントリデータの無効化（ステップＳ４１５）を実行後、後に無効化すべきエントリに有効な削除フラグを設定する処理を実行する手順を追加してもよい。また、上記ステップＳ４０１〜Ｓ４０７の処理と、ステップＳ４１１〜Ｓ４１９の処理とは別々の処理として実行されてもよい。さらに、ステップＳ４１１〜Ｓ４１９の処理の実行後、ステップＳ４０１〜Ｓ４０７の処理が実行されてもよい。
【００９７】
以上に説明したように、実施の形態３のデータ記憶装置を用いれば、エントリデータに要する記憶容量が増加するものの、一定期間内に登録または更新されなかったエントリデータに対して一括削除を行うことができる。また、ＬＲＵアルゴリズムなどのメモリ管理アルゴリズムに基づく制御を継続して実行することができる。
【００９８】
実施の形態４．
次に、本発明に係る実施の形態４について説明する。実施の形態４のデータ記憶装置は、実施の形態１のデータ記憶装置１１と同一の構成を有する。実施の形態４では、エントリ更新制御部１３３が、上記機能に加えて、エントリ保持回路１２内のデータ記憶領域Ｍ０〜Ｍｎ−１に保持されているエントリデータのうち、直近に参照されたエントリデータを最上位のデータ記憶領域Ｍｎ−１に保持させる機能を有している。図１６は、この機能を実現するためのエントリ更新処理の手順を概略的に示すフローチャートである。
【００９９】
入出力装置１４からデータ参照要求を含むアクセス要求ＲＱが受信されると、データ検索部１３３Ａは、このデータ参照要求に応じて、エントリデータ群３１の中からデータ参照要求で指定される実体データを取得し、この実体データを送受信部１３１を介して入出力装置１４に送信する。一方、メモリ制御部１３３Ｃは、データ参照要求に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に図１６のエントリ更新処理を開始する。
【０１００】
まず、メモリ制御部１３３Ｃは、データ参照要求により参照されたエントリデータ（以下「参照データ」と呼ぶ。）を保持するデータ記憶領域Ｍｐのアクセス順位が最上位であるか否かを判定する（ステップＳ５０１）。参照データが最上位のデータ記憶領域Ｍｎ−１に保持されていると判定したとき（ステップＳ５０１のＹＥＳ）、メモリ制御部１３３Ｃは、エントリ更新処理を終了する。一方、参照データが最上位のデータ記憶領域Ｍｎ−１に保持されていないと判定したとき（ステップＳ５０１のＮＯ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）の最上位のエントリが無効か否かを判定する（ステップＳ５０３）。最上位のエントリが無効である場合（ステップＳ５０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）のエントリへの参照データの書き込み制御を実行する（ステップＳ５０９）。具体的には、メモリ制御部１３３Ｃは、最上位のエントリセレクタ６０ｎ−１に置換データＯＤｎを選択させる選択制御信号ＳＥＬｎ−１を供給し、エントリセレクタ６０ｎ−１に参照データを置換データＯＤｎとして供給する。これによりレジスタ５０ｎ−１は、エントリセレクタ６０ｎ−１を介して入力された参照データＯＤｎをラッチ（保持）する。
【０１０１】
一方、ステップＳ５０３で最上位のエントリが無効ではないと判定したとき（ステップＳ５０３のＮＯ）、メモリ制御部１３３Ｃは、参照データを保持する識別子＃（ｐ）のエントリを無効化する（ステップＳ５０５）。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）の最上位エントリが無効化されるまで待機する（ステップＳ５０７のＮＯ）。最上位エントリの無効化が完了したとき（ステップＳ５０７のＹＥＳ）、メモリ制御部１３３Ｃは、最上位エントリに対する参照データの書き込み制御を実行し（ステップＳ５０９）、エントリ更新処理を終了する。
【０１０２】
図１７（Ａ）〜（Ｄ）は、最大エントリ数が７の場合のデータ記憶領域Ｍ０〜Ｍ６に対して図１６のエントリ更新処理が実行されたときの、データ記憶領域Ｍ０〜Ｍ６の状態遷移の様子を示す図である。図１７（Ａ）に示されるように、最初の状態では、全てのデータ記憶領域Ｍ０〜Ｍ６のエントリは有効であり、データ記憶領域Ｍ０〜Ｍ６はそれぞれエントリデータＤ０〜Ｄ６を保持している。データ参照要求に応じてエントリデータＤ３が参照されたとき、図１７（Ｂ）に示されるように、参照データＤ３を保持する識別子＃（３）のエントリが無効化される（図１６のステップＳ５０５）。次の処理サイクル期間にシフト操作と最上位エントリの無効化処理とが実行される。これにより、図１７（Ｃ）に示されるように、識別子＃（３），＃（４），＃（５）のエントリにそれぞれエントリデータＤ４，Ｄ５，Ｄ６がシフトする。その後、図１７（Ｄ）に示されるように、識別子＃（６）のデータ記憶領域Ｍ６に参照データＤ３が書き込まれる（図１６のステップＳ５０９）。
【０１０３】
以上に説明したように、実施の形態４によれば、直近に参照されたエントリデータを最上位のデータ記憶領域Ｍｎ−１に常に保持させることができる。したがって、直近に参照されたエントリデータの優先順位を最も高くするメモリ管理アルゴリズムを実現することができる。
【０１０４】
実施の形態１〜４の変形例．
以上、図面を参照して本発明に係る種々の実施の形態について述べたが、これらは本発明の例示であり、上記以外の様々な形態を採用することができる。たとえば、図１８（Ａ），（Ｂ）に示されるように、データ記憶領域Ｍｉのフラグ領域２２を３つの領域２２Ａ，２２Ｂ，２２Ｃに機能的に分割し、領域２２Ａには上記有効フラグを格納し、領域２２Ｂに上記静的フラグを格納し、領域２２Ｃに上記削除フラグを格納してもよい。これにより、データ記憶装置１１は、有効フラグ、静的フラグ及び削除フラグを用いた処理を実行することができる。具体的には、設定期間ΔＴ内に未登録あるいは未更新のエントリデータでも、有意な静的フラグを含むエントリデータは一括削除の対象外とすることができる。たとえば、識別子＃（ｉ）の静的フラグが有意であるか否かを判定し、静的フラグが有意であれば、図１５のステップＳ４０３において有効な削除フラグを設定せず、静的フラグが有意でなければ、ステップＳ４０３において有効な削除フラグを設定してもよい。
【０１０５】
また、上記実施の形態１〜３においては、エントリ保持回路１２はシフトレジスタ回路の構成を有しているが、これに限定されるものではない。エントリ保持回路１２へのアクセス速度が高速であることが要求されないシステムにデータ記憶装置１１が適用される場合は、エントリ保持回路１２をＲＡＭ（ランダム・アクセス・メモリ）で構成してもよい。
【０１０６】
また、エントリ制御回路１３の全部または一部の機能は、ハードウェアで実現されてもよいし、あるいは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などのマイクロプロセッサにより実行されるコンピュータプログラムで実現されてもよい。当該機能がコンピュータプログラムで実現される場合、マイクロプロセッサは、コンピュータ読み取り可能な記録媒体からコンピュータプログラムをロードし実行することにより当該機能を実現することが可能である。
【符号の説明】
【０１０７】
１ データ処理システム、 １１ データ記憶装置、 １２ エントリ保持回路、 １３ エントリ制御回路、 １３１ 送受信部、 １３２ エントリデータ受信部、 １３３ エントリ更新制御部、 １３３Ａ データ検索部、 １３３Ｂ 領域検出部、 １３３Ｃ メモリ制御部、 １４ 入出力装置、 Ｍ０〜Ｍｎ−１ データ記憶領域、 ２１ データ領域、 ４００〜４０ｎ−１ レジスタ回路、 ５００〜５０ｎ−１ レジスタ、 ６００〜６０ｎ−１ エントリセレクタ、 ７００〜７０ｎ−１ 自エントリデータ制御回路。
【技術分野】
【０００１】
本発明は、記憶装置に対するデータの保存や読み出しを行う技術に関し、特に、ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）アルゴリズムなどのメモリ管理アルゴリズムに基づいて記憶装置に対するデータの保存や読み出しを行う技術に関する。
【背景技術】
【０００２】
従来から、ハードディスクドライブ（ＨＤＤ）やキャッシュメモリや仮想メモリなどの記憶装置に対するデータの保存や読み出しを制御する手段として、記憶装置に保存されるデータまたはその記憶領域に優先順位を付与するメモリ管理アルゴリズムが広く使用されている。メモリ管理アルゴリズムを使用すれば、記憶装置に保存されているデータのうち最も優先順位の低いデータを選択し、これを必要に応じて記憶装置から削除する（追い出す）ことにより、記憶装置の限られた記憶領域内にできるだけ有意なデータを保存する領域を確保することができる。この種のメモリ管理アルゴリズムとしては、たとえば、時間的な局所性原理（Ｌｏｃａｌｉｔｙ Ｐｒｉｎｃｉｐｌｅ）に基づくＬＲＵアルゴリズムやＬＦＵ（Ｌｅａｓｔ Ｆｒｅｑｕｅｎｔｌｙ Ｕｓｅｄ）アルゴリズムが広く知られている。ＬＲＵアルゴリズムは、最も長い間参照されていないデータを、近い将来参照される可能性が最も低いものとして選択するアルゴリズムであり、ＬＦＵアルゴリズムは、最も参照頻度が低いデータを、近い将来参照される可能性が最も低いものとして選択するアルゴリズムである。
【０００３】
ＬＲＵアルゴリズムに関する先行技術文献としては、たとえば、特開平９−２８８６１７号公報（特許文献１）及び特許第４３６９５２４号明細書（特許文献２）が挙げられる。特許文献１に開示されているＬＲＵ制御方式は、検索対象データをテーブルから検索する手段と、この検索対象データがテーブル内に存在したときは、検索対象データをテーブルの先頭に位置するように並び替える手段とを有するものである。一方、特許文献２に開示されているＬＲＵ制御装置は、複数のエントリをそれぞれ識別するための複数の識別情報（たとえば、エントリごとに一意に付与されたＩＤ）からなるＬＲＵ情報を記憶する記憶手段と、これら複数のエントリの中のいずれかのエントリが使用された場合に、ＬＲＵ情報の中から使用されたエントリの識別情報を取り出すとともに最後尾に移動させてＬＲＵ情報を更新する手段とを備えている。ＬＲＵ情報を構成する複数の識別情報は、エントリの最終使用時の古い順に書き込まれる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平９−２８８６１７号公報
【特許文献２】特許第４３６９５２４号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
メモリ管理アルゴリズムの１つとして並べ替え方式と呼ばれるものがある。並べ替え方式は、エントリの登録や削除や更新ごとに、データ記憶領域においてエントリデータを優先順位に従って並べ替える方式である。特許文献１に開示されているＬＲＵ制御方式は、並べ替え方式の一種である。しかしながら、並べ替え方式には、エントリデータを並べ替えている間は、エントリデータを格納するデータ記憶領域にアクセスすることができない期間が発生し、これが処理速度の低下を招くという問題がある。
【０００６】
特許文献２に開示されているＬＲＵ制御装置は、エントリデータを格納するデータ記憶領域とは別の記憶領域にＬＲＵ情報を構築し、エントリの登録や削除や更新ごとに、ＬＲＵ情報内の複数の識別情報を最終使用時が古い順に並べ替えて記憶することでＬＲＵ情報を更新する。このため、ＬＲＵ制御により識別情報が並べ替えられている最中であっても、データ記憶領域にアクセスしてエントリデータを読み出すことができる。しかしながら、ＬＲＵ制御のために別の記憶領域を確保する必要があるのでメモリ消費量が多くなる。また、ＬＲＵ制御の対象となるエントリ数が増えると、ＬＲＵ制御を実現するために必要なビット数が増大するという問題もある。
【０００７】
上記に鑑みて本発明の目的は、メモリ管理アルゴリズムに基づいてエントリデータの並べ替えを行う場合でも少ないメモリ消費量で動作し、処理速度の低下を抑制することができるデータ記憶装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明によるデータ記憶装置は、所定のメモリ管理アルゴリズムに基づく優先順位を有する複数のエントリデータをそれぞれ保持し、該複数のエントリデータの優先順位に対応する順位がそれぞれ割り当てられた複数のデータ記憶領域を有するエントリ保持回路と、外部装置からのアクセス要求に応じて、前記複数のデータ記憶領域に対して前記エントリデータの読み出し及び書き込みを実行するエントリ制御回路と、を備え、前記各データ記憶領域は、当該各データ記憶領域に保持されるエントリデータを有効にする有効値及び当該各データ記憶領域に保持されるエントリデータを無効にする無効値のうちのいずれか一方の値を持つ有効フラグを格納する有効フラグ領域と、実体データを格納するデータ領域と、を有し、前記エントリ制御回路は、前記複数のデータ記憶領域の中から前記無効値を持つ有効フラグを保持する無効化データ領域を空き領域として検出する領域検出部と、前記複数のデータ記憶領域に対して前記エントリデータの書き込みが実行されない間に、前記複数のデータ記憶領域のうち前記無効化データ領域の順位よりも上位のデータ記憶領域に保持されているエントリデータを、前記上位のデータ記憶領域よりも下位の当該データ記憶領域にシフトさせるシフト操作を行うとともに、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記無効値を持つ有効フラグを書き込むメモリ制御部と、を含むことを特徴とする。
【発明の効果】
【０００９】
本発明によれば、有効フラグと実体データとを含むエントリデータがデータ記憶領域に保持される。データ記憶領域に対するエントリデータの書き込みが実行されない間に、有効フラグを使用したシフト操作によりエントリデータの並び替えを効率的に行うことができる。
【図面の簡単な説明】
【００１０】
【図１】本発明に係る実施の形態１のデータ処理システムの概略構成を示す機能ブロック図である。
【図２】実施の形態１のデータ記憶装置のエントリ保持回路内のデータ記憶領域の構成を示す図である。
【図３】実施の形態１のデータ記憶装置のエントリ制御回路の構成の一例を示す機能ブロック図である。
【図４】実施の形態１のエントリ保持回路の好適な構成を示す図である。
【図５】実施の形態１に係るエントリ並べ替え処理の手順を概略的に示すフローチャートである。
【図６】図５のエントリ並べ替え処理が実行されたときのデータ記憶領域の状態遷移の様子を示す図である。
【図７】実施の形態１に係るエントリ削除処理の手順を概略的に示すフローチャートである。
【図８】実施の形態１に係るエントリ登録処理の手順の一例を概略的に示すフローチャートである。
【図９】実施の形態１に係るエントリ登録処理の手順の他の例を概略的に示すフローチャートである。
【図１０】本発明に係る実施の形態２のデータ記憶領域の構成を示す図である。
【図１１】実施の形態２に係るエントリ削除処理の手順を概略的に示すフローチャートである。
【図１２】実施の形態２に係るエントリ登録処理の手順を概略的に示すフローチャートである。
【図１３】図１２のエントリ検索処理（ステップＳ３２６）の手順を示すフローチャートである。
【図１４】本発明に係る実施の形態３のデータ記憶領域の構成を示す図である。
【図１５】実施の形態３に係る制御処理の一例を概略的に示すフローチャートである。
【図１６】本発明に係る実施の形態４に係るエントリ更新処理の手順を概略的に示すフローチャートである。
【図１７】実施の形態４に係るエントリ更新処理が実行されたときのデータ記憶領域の状態遷移の様子を示す図である。
【図１８】実施の形態１〜４の変形例のデータ記憶領域の構成を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明に係る種々の実施の形態について図面を参照しつつ説明する。
【００１２】
実施の形態１．
図１は、本発明に係る実施の形態１のデータ処理システム１の概略構成を示す機能ブロック図である。このデータ処理システム１は、データ処理を実行する入出力装置１４と、そのデータ処理の際に参照される実体データを含むエントリデータを一時的に記憶するデータ記憶装置１１とを備える。入出力装置１４としては、たとえば、通信ネットワークにおいて通信データを処理する通信装置（中継装置や集線装置など）が挙げられるが、これらに限定されるものではない。データ処理にメモリを必要とする装置であれば、任意の装置にデータ記憶装置１１を適用することが可能である。
【００１３】
データ記憶装置１１は、複数のエントリデータを記憶する複数のデータ記憶領域を有するエントリ保持回路１２と、ＬＲＵアルゴリズムなどのメモリ管理アルゴリズムに基づいてエントリ保持回路１２に対するエントリデータの書き込み及び読み出しを制御するエントリ制御回路１３とを含む。エントリ制御回路１３は、メモリ管理アルゴリズムに基づいて複数のエントリデータのうち優先順位の最も低いエントリデータを選択し、選択されたエントリデータを無効化することによりエントリ保持回路１２内に空き領域を確保する機能を有する。
【００１４】
図２（Ａ），（Ｂ），（Ｃ）は、エントリ保持回路１２内のｎ個のデータ記憶領域Ｍ０，Ｍ１，Ｍ２，…，Ｍｎ−３，Ｍｎ−２，Ｍｎ−１（ｎは正整数）を模式的に示す図である。ここで、ｎは、エントリ保持回路１２に確保可能な最大エントリ数を示す整数値である。図２（Ａ）には６個以上のデータ記憶領域Ｍ０〜Ｍｎ−１が示されているが、少なくとも２個のデータ記憶領域が確保されていればよい。データ記憶領域Ｍ０〜Ｍｎ−１はそれぞれエントリデータを保持するための記憶容量を有する。また、データ記憶領域Ｍ０，Ｍ１，…，Ｍｎ−１には、エントリデータの優先順位に対応する順位（以下、アクセス順位と呼ぶ。）がそれぞれ割り当てられている。エントリ制御回路１３においては、データ記憶領域Ｍ０，Ｍ１，…，Ｍｎ−１に対してそれぞれのアクセス順位に対応する識別子＃（０），＃（１），…，＃（ｎ−３），＃（ｎ−２），＃（ｎ−１）が設定されている。エントリ制御回路１３は、これら識別子＃（０）〜＃（ｎ−１）に基づいて、データ記憶領域Ｍ０〜Ｍｎ−１に保持されているエントリデータにアクセスすることができる。
【００１５】
図２（Ａ）に示されるように、識別子＃（ｎ−１）を有するデータ記憶領域Ｍｎ−１のアクセス順位が最上位であり、この最上位のデータ記憶領域Ｍｎ−１に優先順位の最も高いエントリデータが格納される。ＬＲＵアルゴリズムが採用される場合には、最後に参照された時からの経過時間が短いほどエントリデータの優先順位は高くなる。また、識別子＃（０）を有するデータ記憶領域Ｍ０のアクセス順位が最下位であり、この最下位のデータ記憶領域Ｍ０に優先順位の最も低いエントリデータが格納される。後述するように、エントリ保持回路１２にエントリデータが登録されるとき、このエントリデータは、最初に最上位のデータ記憶領域Ｍｎ−１に記憶される。その後、エントリデータは、他のエントリデータの登録や更新や削除のたびに、上位のデータ記憶領域Ｍｉ（ｉは１〜ｎ−１のいずれかの整数）から１つ下位のデータ記憶領域Ｍｉ−１にシフトさせられる。
【００１６】
図２（Ｂ）は、識別子＃（ｉ）のデータ記憶領域Ｍｉの構成の一例を示す概略図である。図２（Ｂ）に示されるように、各データ記憶領域Ｍｉは、データ処理の際に参照される実体データ（エントリデータ本体）を格納するデータ領域２１と、データ記憶領域Ｍｉに保持されるエントリデータの有効性を示す制御フラグの一種である有効フラグを格納するフラグ領域２２とを有する。有効フラグは、エントリデータを有効にする有効値（たとえば「１」の値）及びエントリデータを無効にする無効値（たとえば「０」の値）のうちのいずれか一方の値を有する。以下、無効値を持つ有効フラグを「無効フラグ」と呼ぶこととする。また、エントリ制御回路１３は、フラグ領域２２に無効フラグを保持するデータ記憶領域Ｍｉをエントリの欠けた空き領域であると判断する。エントリ制御回路１３は、データ記憶領域Ｍｉのフラグ領域２２に無効フラグを書き込むことによりデータ記憶領域Ｍｉにおけるエントリを無効化して空き領域をつくることができる。
【００１７】
本実施の形態では、データ領域２１には、単一の実体データが格納されるが、これに限定されるものではない。データ領域２１は、構築すべきシステムに応じて、図２（Ｃ）に示されるように互いに関連する複数の実体データをそれぞれ格納する領域２１Ａ，２１Ｂ，…に機能的に分割されていてもよい。これにより、エントリ保持回路１２を検索テーブルとして利用することができる。たとえば、入出力装置１４がＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）に接続された集線装置の場合には、データ領域２１内の２つの領域２１Ａ，２１Ｂにアドレス検索テーブルの実体データを格納することができる。具体的には、データ領域２１内の２つの領域２１Ａ，２１Ｂに、データ送信元のＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）アドレスと通信ポート番号という２つの実体データを格納すれば、エントリ保持回路１２を、ＭＡＣアドレステーブルを保持するアドレス検索回路として利用できる。エントリ制御回路１３は、入出力装置１４からの問い合わせ要求に応じて、ＭＡＣアドレスに対応する通信ポート番号をエントリ保持回路１２から取得しこれを検索結果として返すことができる。
【００１８】
また、本実施の形態では、フラグ領域２２に単一の制御フラグ（有効フラグ）が格納されるが、これに限定されるものではない。図２（Ｃ）に示されるように、フラグ領域２２が複数の制御フラグを格納する領域２２Ａ，２２Ｂ，…を有していてもよい。後述するように実施の形態２，３では、フラグ領域２２に２種類の制御フラグが格納される。
【００１９】
図３は、エントリ制御回路１３の構成の一例を示す機能ブロック図であり、図４は、エントリ保持回路１２の好適な構成を示す図である。図３に示されるように、エントリ制御回路１３は、入出力装置１４との間でデータの送受信を行う送受信部１３１と、エントリ保持回路１２内の全てのデータ記憶領域Ｍ０〜Ｍｎ−１から並列に出力されたエントリデータ群３１を受信するエントリデータ受信部１３２と、エントリ更新制御部１３３とを含む。エントリデータ受信部１３２は、エントリ保持回路１２から受信したエントリデータ群３１を送受信部１３１とエントリ更新制御部１３３とに供給する。エントリ更新制御部１３３は、処理サイクルごとに、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいてエントリ保持回路１２の状態を把握し、エントリ保持回路１２の動作状態を制御することができる。ここで、１処理サイクルは、１クロックサイクルまたは所定数のクロックサイクルからなる。エントリ更新制御部１３３は、データ検索部１３３Ａ、領域検出部１３３Ｂ及びメモリ制御部１３３Ｃを含む。
【００２０】
また、エントリ更新制御部１３３は、制御データ群３２をエントリ保持回路１２に供給している。エントリ保持回路１２は、処理サイクルごとに、エントリ更新制御部１３３から供給された制御データ群３２に従って動作する。
【００２１】
送受信部１３１は、入出力装置１４からアクセス要求ＲＱを受信し解析する機能を有する。送受信部１３１は、アクセス要求ＲＱの解析結果をエントリ更新制御部１３３に出力する。エントリ更新制御部１３３は、その解析結果に応じた処理を実行し、その処理結果ＲＳを送受信部１３１を介して入出力装置１４に返す。アクセス要求ＲＱとしては、たとえば、エントリ登録指示、エントリ削除指示、有効エントリ数の通知指示、データ検索要求及びデータ読み出し指示が挙げられる。これらアクセス要求ＲＱのうち、データ検索要求、データ読み出し指示及び有効エントリ数の通知指示は、データ記憶領域Ｍ０〜Ｍｎ−１におけるエントリの変更を伴わないものである。
【００２２】
データ読み出し指示を含むアクセス要求ＲＱを受信したとき、送受信部１３１は、エントリデータ受信部１３２から供給されるエントリデータ群３１から全ての実体データを抽出し、これら実体データを入出力装置１４に送信する機能を有する。
【００２３】
送受信部１３１が検索キーデータ付きのデータ検索要求を含むアクセス要求ＲＱを受信したときは、データ検索部１３３Ａは、データ検索要求に応じて、エントリデータ受信部１３２から供給されるエントリデータ群３１のうち有効値を持つ有効フラグを含むエントリデータの中から検索キーデータと一致する実体データを検索し、その検索結果を送受信部１３１を介して入出力装置１４に返す。たとえば、エントリ保持回路１２が上記ＭＡＣアドレステーブルを保持する場合、データ検索部１３３Ａは、ＭＡＣアドレスを検索キーデータとして使用し、対応する通信ポート番号を検索結果として返すことができる。
【００２４】
有効エントリ数の通知指示を含むアクセス要求ＲＱが受信されたときは、データ検索部１３３Ａは、通知指示に応じて、エントリデータ受信部１３２から供給されるエントリデータ群３１のうち有効値を持つ有効フラグを含むエントリデータを計数し、その計数結果、すなわちエントリ保持回路１２における有効なエントリの数を送受信部１３１を介して入出力装置１４に通知する。
【００２５】
エントリ登録指示やエントリ削除指示といったエントリの変更を伴う指示（以下、エントリ操作指示と呼ぶ。）を含むアクセス要求ＲＱを送受信部１３１が受信されたときは、メモリ制御部１３３Ｃがそのエントリ操作指示に応じた処理を実行するエントリ操作機能を有する。
【００２６】
エントリ登録指示を含むアクセス要求ＲＱが受信されたとき、メモリ制御部１３３Ｃは、エントリ登録指示に応じて、最上位のデータ記憶領域Ｍｎ−１に無効フラグが保持されているか否かを判定する。領域検出部１３３Ｂは、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいて、データ記憶領域Ｍ０〜Ｍｎ−１の中から無効フラグを有する空き領域Ｍｅ（ｅは１〜ｎ−１の整数）を検出し、その検出結果をメモリ制御部１３３Ｃに与える機能を有する。メモリ制御部１３３Ｃは、領域検出部１３３Ｂによる検出結果から最上位のデータ記憶領域Ｍｎ−１に無効フラグが保持されているか否かを判定することができる。
【００２７】
データ記憶領域Ｍｎ−１が無効フラグを保持する空き領域であると判定した場合、メモリ制御部１３３Ｃは、有効値を持つ有効フラグと登録すべき実体データとを含むエントリデータを空き領域Ｍｎ−１に書き込む。これによりエントリの登録が完了する。一方、データ記憶領域Ｍｎ−１に無効フラグが保持されていない場合、言い換えれば、データ記憶領域Ｍｎ−１が有効値を持つ有効フラグを含むエントリデータを保持する場合は、メモリ制御部１３３Ｃは、先ず、最下位のデータ記憶領域Ｍ０に無効フラグを書き込む。その後、後述するシフト操作の実行によりデータ記憶領域Ｍ１〜Ｍｎ−１のエントリデータはそれぞれ１つ下位のデータ記憶領域Ｍ０〜Ｍｎ−２にシフトされるので、このシフト操作の実行後、メモリ制御部１３３Ｃは、有効値を持つ有効フラグと登録すべき実体データとを含むエントリデータを最上位のデータ記憶領域Ｍｎ−１に書き込む。これによりエントリの登録が完了する。
【００２８】
エントリ削除指示を含むアクセス要求ＲＱが受信されたときは、データ検索部１３３Ａが、このエントリ削除指示に応じて、エントリデータ受信部１３２から供給されるエントリデータ群３１のうち有効値を持つ有効フラグを含むエントリデータの中から特定データと一致する削除すべき実体データを検索する。データ検索部１３３Ａは、実体データを探し出すことができなかったときは、その検索結果を送受信部１３１を介して入出力装置１４に通知する。一方、実体データが探し出されたときは、メモリ制御部１３３Ｃが、その一致する実体データを保持するデータ記憶領域Ｍｄ（ｄは０〜ｎ−１の整数）に無効フラグを書き込むことでデータ記憶領域Ｍｄのエントリを無効化する。そして、メモリ制御部１３３Ｃは、その結果を送受信部１３１を介して入出力装置１４に通知する。この空き領域Ｍｄには、後述するシフト操作により１つ上位のデータ記憶領域Ｍｄ＋１に保持されているエントリデータがシフトさせられる。
【００２９】
全てのエントリの削除指示（一斉削除指示）を含むアクセス要求ＲＱが受信されたときは、メモリ制御部１３３Ｃは、１処理サイクル内に、データ記憶領域Ｍ０〜Ｍｎ−１の全てに無効フラグを書き込むことで全てのエントリを無効化し、一斉削除が完了した旨を送受信部１３１を介して入出力装置１４に通知する。
【００３０】
また、メモリ制御部１３３Ｃは、データ記憶領域Ｍ０〜Ｍｎ−１において有効値を持つ有効フラグを含むエントリデータを並び替えて（再配置して）有効なエントリを連続的に詰めて配置するエントリ並べ替え機能（エントリ再配置機能）を有する。具体的には、データ記憶領域Ｍ０〜Ｍｎ−１に対してエントリデータの書き込みが実行されない処理サイクル期間内に、メモリ制御部１３３Ｃは、空き領域Ｍｄの順位よりも上位のデータ記憶領域Ｍｄ＋１〜Ｍｎ−１に保持されているエントリデータを、１つ下位のデータ記憶領域Ｍｄ〜Ｍｎ−２にシフトさせるシフト操作を実行し、最上位のデータ記憶領域Ｍｎ−１に無効フラグを書き込む。シフト操作は、１処理サイクルで実行される。たとえば、識別子＃（１）のデータ記憶領域Ｍ１が空き領域である場合、メモリ制御部１３３Ｃは、空き領域Ｍ１よりも上位のデータ記憶領域Ｍ２〜Ｍｎ−１に保持されるエントリデータを、それぞれ、１つ下位のデータ記憶領域Ｍ１〜Ｍｎ−２にシフトさせる。あるいは、識別子＃（ｎ−２）のデータ記憶領域Ｍｎ−２が空き領域である場合は、メモリ制御部１３３Ｃは、空き領域Ｍｎ−２よりも上位のデータ記憶領域Ｍｎ−１に保持されているエントリデータを、１つ下位のデータ記憶領域Ｍｎ−２にシフトさせる。
【００３１】
このようなエントリ並べ替え機能により、データ記憶領域Ｍ０〜Ｍｎ−１において有効値を持つ有効フラグを含むエントリデータを連続的に配置する（並び替える）ことができ、有効値を持つ有効フラグを保持するデータ記憶領域間に空き領域が介在すること（空き領域の断片化）を解消することができる。また、最上位のデータ記憶領域Ｍｎ−１を含む上位のデータ記憶領域群をできるだけ空き領域にすることができる。上記のエントリ登録指示に応じて新規エントリを最上位のデータ記憶領域Ｍｎ−１に登録する際、最上位のデータ記憶領域Ｍｎ−１が空き領域であれば、シフト操作によりデータ記憶領域Ｍｎ−１が空き領域になるのを待つことなく、このデータ記憶領域Ｍｎ−１に実体データを書き込むことができる。
【００３２】
また、エントリ並べ替え機能により、有効値を持つ有効フラグを含むエントリデータが連続的に配置されるようになるので、データ検索指示や特定エントリの削除指示があったときに検索範囲を限定することができる。したがって、データ検索処理とエントリ削除処理の高速化を実現することができる。
【００３３】
次に、図４を参照しつつ、エントリ保持回路１２の好適な構成について説明する。エントリ保持回路１２は、ｎ段のレジスタ回路４００，…，４０ｎ−３，４０ｎ−２，４０ｎ−１を有するシフトレジスタ回路である。各レジスタ回路４０ｊ（ｊは０〜ｎ−１のうちの任意の整数）は、図４に示されるように、たとえばクロック信号に同期して動作するフリップ・フロップなどのレジスタ５０ｊと、エントリセレクタ６０ｊと、自エントリデータ制御回路７０ｊとを有する。レジスタ５００，…，５０ｎ−１はそれぞれ図２のデータ記憶領域Ｍ０，…，Ｍｎ−２，Ｍｎ−１を構成する記憶素子である。
【００３４】
エントリ制御回路１３は、制御データ群３２をエントリ保持回路１２に供給する。制御データ群３２は、エントリセレクタ６００，…，６０ｎ−２，６０ｎ−１にそれぞれ供給される選択制御信号ＳＥＬ０，…，ＳＥＬｎ−２，ＳＥＬｎ−１と、自エントリデータ制御回路７００，…，７０ｎ−２，７０ｎ−１にそれぞれ供給される制御信号Ｃ０，…，Ｃｎ−２，Ｃｎ−１とからなる。各エントリセレクタ６０ｊは、選択制御信号ＳＥＬｊの値に応じて３個の入力端子のいずれか１つに入力したデータを選択し、このデータをレジスタ５０ｊの入力端子に出力する機能を有する。
【００３５】
最上位のレジスタ回路４０ｎ−１では、エントリセレクタ６０ｎ−１の３個の入力端子には、エントリ制御回路１３から供給された登録データ（実体データ）ＯＤｎと、自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１と、レジスタ５０ｎ−１のフィードバック出力ＯＤｎ−１とが入力される。エントリセレクタ６０ｎ−１がレジスタ５０ｎ−１のフィードバック出力ＯＤｎ−１を選択したとき、レジスタ５０ｎ−１の出力端子と入力端子との間にフィードバックループが形成され、レジスタ５０ｎ−１は同一のビット値（エントリデータ）を保持し続ける。エントリセレクタ６０ｎ−１が自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１を選択したときは、レジスタ５０ｎ−１は、クロック信号のパルスエッジに応じて、自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１をラッチ（保持）する。そして、エントリセレクタ６０ｎ−１がエントリ制御回路１３から供給されたデータＯＤｎを選択したときは、レジスタ５０ｎ−１は、クロック信号のパルスエッジに応じてデータＯＤｎをラッチする。
【００３６】
自エントリデータ制御回路７０ｎ−１は、制御信号Ｃｎ−１に応じて、レジスタ５０ｎ−１に保持されているエントリデータの一部または全てを変更するための置換データＡＤｎ−１を生成する機能を有する。レジスタ５０ｎ−１の出力データＯＤｎ−１はフィードバックして自エントリデータ制御回路７０ｎ−１にも入力されている。自エントリデータ制御回路７０ｎ−１は、制御信号Ｃｎ−１の値に応じて有効値を持つ有効フラグ及び無効フラグのうちのいずれか一方の制御フラグと、フィードバック出力ＯＤｎ−１に含まれる実体データとを含むエントリデータＡＤｎ−１を構成し、このエントリデータＡＤｎ−１をエントリセレクタ６０ｎ−１に出力することができる。
【００３７】
一方、他のレジスタ回路４０ｋ（ｋは０〜ｎ−２のいずれか）では、エントリセレクタ６０ｋの３個の入力端子には、前段のレジスタ５０ｋ＋１の出力データＯＤｋ＋１と、自エントリデータ制御回路７０ｋの出力データＡＤｋと、レジスタ５０ｋの出力データＯＤｋとが入力される。エントリセレクタ６０ｋがレジスタ５０ｋのフィードバック出力ＯＤｋを選択したとき、レジスタ５０ｋの出力端子と入力端子との間にフィードバックループが形成され、レジスタ５０ｋは同一のビット値（エントリデータ）を保持し続ける。エントリセレクタ６０ｋが自エントリデータ制御回路７０ｋの出力データＡＤｋを選択したときは、レジスタ５０ｋは、クロック信号のパルスエッジに応じて、自エントリデータ制御回路７０ｋの出力データＡＤｋをラッチ（保持）する。そして、エントリセレクタ６０ｋが前段のレジスタ５０ｋ＋１の出力データＯＤｋ＋１を選択したときは、レジスタ５０ｋは、クロック信号のパルスエッジに応じてデータＯＤｋ＋１をラッチする。
【００３８】
自エントリデータ制御回路７０ｋは、制御信号Ｃｋに応じて、レジスタ５０ｋに保持されているエントリデータの一部または全部を変更するための置換データＡＤｋを生成する機能を有する。レジスタ５０ｋの出力データＯＤｋはフィードバックして自エントリデータ制御回路７０ｋにも入力されている。自エントリデータ制御回路７０ｋは、制御信号Ｃｋの値に応じて有効値を持つ有効フラグ及び無効フラグのうちのいずれか一方の制御フラグと、フィードバック出力ＯＤｋに含まれる実体データとを含むエントリデータＡＤｋを構成し、このエントリデータＡＤｋをエントリセレクタ６０ｎ−１に出力することができる。
【００３９】
レジスタ５００〜５０ｎ−１は、出力データＯＤ０〜ＯＤｎ−１からなるエントリデータ群３１をエントリ制御回路１３に並列に出力しているので、エントリ制御回路１３は、レジスタ５００〜５０ｎ−１に保持されている全てのエントリデータを一度に取得することができる。
【００４０】
エントリ制御回路１３は、制御データ群３２を供給することでエントリ保持回路１２の動作を制御することができる。エントリ登録指示やエントリ削除指示といったエントリ操作指示に応じた処理を実行しない処理サイクル期間には、メモリ制御部１３３Ｃは、全てのエントリセレクタ６００〜６０ｎ−１にレジスタ５００〜５０ｎ−１のフィードバック出力ＯＤ０〜ＯＤｎ−１を選択させる選択制御信号ＳＥＬ０〜ＳＥＬｎ−１を出力する。これによりレジスタ５００〜５０ｎ−１は同一のエントリデータ群を保持し続ける。
【００４１】
エントリデータを無効化してエントリ保持回路１２からエントリを削除するときは、メモリ制御部１３３Ｃは、無効化対象のエントリデータを保持するレジスタ回路４０ｄのエントリセレクタ６０ｄに自エントリデータ制御回路７０ｄの出力データＡＤｄを選択させる選択制御信号ＳＥＬｄを供給し、自エントリデータ制御回路７０ｄに無効フラグを含む置換データＡＤｄを生成させる制御信号Ｃｄを供給する。これによりレジスタ５０ｄは無効フラグを保持する。
【００４２】
エントリ登録指示に応じてエントリデータをエントリ保持回路１２に記憶させるときは、メモリ制御部１３３Ｃは、最上位のエントリセレクタ６０ｎ−１に置換データＯＤｎを選択させる選択制御信号ＳＥＬｎ−１を供給し、エントリセレクタ６０ｎ−１に新たなエントリデータを置換データＯＤｎとして供給する。レジスタ５０ｎ−１は、クロック信号のパルスエッジに応じて、エントリセレクタ６０ｎ−１を介して入力されたエントリデータＯＤｎをラッチ（保持）する。これにより、最上位のレジスタ５０ｎ−１にエントリデータが登録される。
【００４３】
データ記憶領域Ｍ０〜Ｍｎ−１内に空き領域Ｍｅが存在するとき、エントリ操作指示に応じたエントリデータの書き込みが実行されない処理サイクル期間内に、有効値を持つ有効フラグを含むエントリデータが再配置される。具体的には、メモリ制御部１３３Ｃは、空き領域Ｍｅを有するレジスタ回路４０ｅの順位よりも上位のレジスタ回路４０ｅ＋１〜４０ｎ−１内のレジスタ５０ｅ＋１〜５０ｎ−１の出力データＯＤｅ＋１〜ＯＤｎ−１を選択させる選択制御信号ＳＥＬｅ〜ＳＥＬｎ−２をエントリセレクタ６０ｅ〜６０ｎ−２に供給する。さらに、メモリ制御部１３３Ｃは、最上位のレジスタ回路４０ｎ−１のエントリセレクタ６０ｎ−１に自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１を選択させる選択制御信号ＳＥＬｎ−１を供給し、自エントリデータ制御回路７０ｎ−１に無効フラグを含む置換データＡＤｎ−１を生成させる制御信号Ｃｎ−１を供給する。これによりレジスタ５０ｅ〜５０ｎ−２は、それぞれ、前段のレジスタ５０ｅ＋１〜５０ｎ−１の出力データＯＤｅ＋１〜ＯＤｎ−１をラッチ（保持）するシフト動作を実行する。また、最上位のレジスタ５０ｎ−１に無効フラグが保持される。
【００４４】
次に、図５〜図９を参照しつつ、上記構成を有する実施の形態１のデータ記憶装置１１の動作を説明する。
【００４５】
図５は、入出力装置１４からのエントリ操作指示がない場合に実行されるエントリ並べ替え処理の手順を概略的に示すフローチャートであり、図６は、エントリ並べ替え処理が実行されたときのデータ記憶領域の状態遷移の様子を示す図である。また、図７は、エントリ削除指示に応じて実行されるエントリ削除処理の手順を概略的に示すフローチャートであり、図８及び図９は、エントリ登録指示に応じて実行されるエントリ登録処理の手順を概略的に示すフローチャートである。なお、データ検索要求、データ読み出し指示及び有効エントリ数の通知指示といったエントリの変更を伴わないアクセス要求ＲＱに対する処理は、エントリ保持回路１２がシフトレジスタ回路の構成を有するので、常時実行可能な処理である。これらの処理は、エントリ並べ替え処理、エントリ削除処理及びエントリ登録処理が実行される処理サイクル期間中でも、並行して実行することができる。
【００４６】
最初に、図５を参照しつつ、エントリ操作指示がない場合に実行されるエントリ並べ替え処理について説明する。エントリ更新制御部１３３のメモリ制御部１３３Ｃは、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいてエントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間にエントリ並べ替え処理を開始する。
【００４７】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ１０１）。次に、メモリ制御部１３３Ｃは、識別子＃（ｉ）を有するレジスタ回路４０ｉに保持されているエントリデータ（以下、識別子＃（ｉ）のエントリデータと呼ぶ。）が無効であるか否かを判定する（ステップＳ１０３）。識別子＃（ｉ）のエントリデータが有効であると判定したとき（ステップＳ１０３のＮＯ）、メモリ制御部１３３Ｃは、変数ｉがｎ−２に達したかどうかを判定する（ステップＳ１１５）。変数ｉがｎ−２に達したとき（ステップＳ１１５のＹＥＳ）、エントリ並べ替え処理は終了する。一方、変数ｉがｎ−２に達していないとき（ステップＳ１１５のＮＯ）、メモリ制御部１３３Ｃは、変数ｉを１だけインクリメントし（ステップＳ１１７）、ステップＳ１０３に手順を戻す。
【００４８】
最下位のエントリデータから上位のエントリデータに向かって順番に無効か否かの判定（ステップＳ１０３）を実行した結果、無効フラグを含む無効なエントリデータが存在していたとき（ステップＳ１０３のＹＥＳ）、メモリ制御部１３３Ｃは、変数ｊに変数ｉの値を設定する（ステップＳ１０５）。次いで、メモリ制御部１３３Ｃは、識別子＃（ｊ）のエントリに識別子＃（ｊ＋１）のエントリデータをシフトさせる制御を実行する（ステップＳ１０７）。具体的には、メモリ制御部１３３Ｃは、識別子＃（ｊ）を有するレジスタ回路４０ｊのエントリセレクタ６０ｊに、識別子＃（ｊ＋１）を有する前段レジスタ回路４０ｊ＋１の出力データＯＤｊ＋１を選択させる選択制御信号ＳＥＬｊを供給する。次いで、変数ｊを１だけインクリメントする（ステップＳ１０９）。その後、メモリ制御部１３３Ｃは、変数ｊが最上位のレジスタ回路４０ｎ−１の識別子番号ｎ−１に達したか否かを判定する（ステップＳ１１１）。変数ｊがｎ−１に達していなければ（ステップＳ１１１のＮＯ）、処理手順はステップＳ１０７に戻る。このようにステップＳ１１１で変数ｊがｎ−１に達するとの判定（ステップＳ１１１のＹＥＳ）がなされるまで、上記ステップＳ１０７，Ｓ１０９の処理が繰り返し実行される。この結果、レジスタ５０ｉ〜５０ｎ−２は、それぞれ、前段のレジスタ５０ｉ＋１〜５０ｎ−１の出力データＯＤｉ＋１〜ＯＤｎ−１をラッチ（保持）するシフト動作を実行する。
【００４９】
シフト動作の実行後（ステップＳ１１１のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）の最上位エントリを無効化する（ステップＳ１１３）。具体的には、メモリ制御部１３３Ｃは、最上位のレジスタ回路４０ｎ−１のエントリセレクタ６０ｎ−１に自エントリデータ制御回路７０ｎ−１の出力データＡＤｎ−１を選択させる選択制御信号ＳＥＬｎ−１を供給し、自エントリデータ制御回路７０ｎ−１に無効フラグを含む置換データＡＤｎ−１を生成させる制御信号Ｃｎ−１を供給する。これによりレジスタ５０ｎ−１に無効フラグが保持される。その後、ステップＳ１１５で変数ｉがｎ−２に達するとの判定（ステップＳ１１５のＹＥＳ）がなされるまで、ステップＳ１１７以後の処理が実行される。
【００５０】
図６（Ａ）〜（Ｃ）は、上記エントリ並べ替え処理が実行されたときに、最大エントリ数ｎが７の場合のデータ記憶領域Ｍ０〜Ｍ６の状態遷移の様子を示す図である。図６（Ａ）に示すように、最初の状態では、識別子＃（１），＃（２），＃（４）のエントリが有効であり、その他のエントリは無効であるとする。
【００５１】
上記エントリ並べ替え処理の実行により、先ず、識別子＃（ｉ＝０）のエントリデータが無効であると判定される（ステップＳ１０３のＹＥＳ）。次いで、識別子＃（０）のエントリに識別子＃（１）のエントリデータをシフトさせ、識別子＃（１）のエントリに識別子＃（２）のエントリデータをシフトさせ、識別子＃（２）のエントリに識別子＃（３）のエントリデータをシフトさせ、識別子＃（３）のエントリに識別子＃（４）のエントリデータをシフトさせ、識別子＃（４）のエントリに識別子＃（５）のエントリデータをシフトさせ、識別子＃（５）のエントリに識別子＃（６）のエントリデータをシフトさせるというシフト操作が実行される（ステップＳ１０５〜Ｓ１１１）。その後、識別子＃（６）のエントリの無効化処理が実行される（ステップＳ１１３）。これにより、図６（Ｂ）に示されるように識別子＃（０），＃（１），＃（３）のエントリに有効なエントリデータがシフトする。以上のシフト操作及びエントリの無効化処理は、最初の処理サイクル期間内に実行される。
【００５２】
次の処理サイクル期間では、識別子＃（ｉ＝２）のエントリデータが無効であると判定される（ステップＳ１０３のＹＥＳ）。次いで、識別子＃（２）のエントリに識別子＃（３）のエントリデータをシフトさせ、識別子＃（３）のエントリに識別子＃（４）のエントリデータをシフトさせ、識別子＃（４）のエントリに識別子＃（５）のエントリデータをシフトさせ、識別子＃（５）のエントリに識別子＃（６）のエントリデータをシフトさせるというシフト操作が実行される（ステップＳ１０５〜Ｓ１１１）。その後、識別子＃（６）のエントリの無効化処理が実行される（ステップＳ１１３）。この結果、図６（Ｃ）に示されるように識別子＃（０），＃（１），＃（２）のエントリに有効なエントリデータがシフトする。
【００５３】
次の処理サイクル期間では、識別子＃（ｉ＝３）のエントリデータが無効であると判定される（ステップＳ１０３のＹＥＳ）。次いで、識別子＃（３）のエントリに識別子＃（４）のエントリデータをシフトさせ、識別子＃（４）のエントリに識別子＃（５）のエントリデータをシフトさせ、識別子＃（５）のエントリに識別子＃（６）のエントリデータをシフトさせるというシフト操作が実行される（ステップＳ１０５〜Ｓ１１１）。その後、識別子＃（６）のエントリの無効化処理が実行される（ステップＳ１１３）。
【００５４】
メモリ制御部１３３Ｃは、上記エントリ並べ替え処理を、エントリデータの書き込みを実行しない処理サイクル期間に常に実行することで、図６（Ｃ）に示すように有効なエントリが詰まって配置された状態を実現することができる。図６（Ａ）〜（Ｃ）に示したように、エントリデータの並び替えが完了するまで複数の処理サイクルを要することになるが、図４に示したように、レジスタ５００〜５０ｎ−１はエントリデータ群３１をエントリ制御回路１３に供給しているので、並び替え処理を中断することなく、エントリデータ群３１を読み出すことができる。
【００５５】
次に、図７を参照しつつ、特定データと一致する実体データを含むエントリデータを無効化するためのエントリ削除処理について説明する。
【００５６】
エントリ保持回路１２は、シフトレジスタ回路の構成を有し、エントリデータをシフトさせるので、ある処理サイクル期間に識別子＃（ｉ）のデータ記憶領域Ｍｉに存在していたエントリデータが、その次の処理サイクル期間に同じ識別子＃（ｉ）のデータ記憶領域Ｍｉに存在している保証はない。そのため、本実施の形態では、特定データを検索キーとした検索を実行して削除対象となるエントリを特定する方法が採用される。入出力装置１４からエントリ削除指示を含むアクセス要求ＲＱが受信されると、メモリ制御部１３３Ｃは、このエントリ削除指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間にエントリ削除処理を開始する。
【００５７】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ２０１）。次に、メモリ制御部１３３Ｃは、レジスタ回路４０ｉに保持されている識別子＃（ｉ）のエントリデータが、特定データと一致する削除すべき実体データを含むか否かを判定する（ステップＳ２０３）。エントリデータが削除すべき実体データを含まない場合（ステップＳ２０３のＮＯ）、メモリ制御部１３３Ｃは、変数ｉが最上位のエントリを指す識別子番号ｎ−１に達したか否かを判定し（ステップＳ２０９）、変数ｉがｎ−１に達していなければ（ステップＳ２０９のＮＯ）、変数ｉを１だけインクリメントして（ステップＳ２１３）、処理手順をステップＳ２０３に戻す。全てのエントリについて削除すべき実体データを含むエントリデータを探し出すことができなかったときは、変数ｉはｎ−１に達する（ステップＳ２０９のＹＥＳ）。このとき、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に削除不能の旨を通知し（ステップＳ２１１）、エントリ削除処理を終了する。
【００５８】
一方、識別子＃（ｉ）のエントリデータが削除すべき実体データを含むと判定された場合（ステップＳ２０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリを無効化する（ステップＳ２０５）。具体的には、データ検索部１３３Ａは、削除すべき実体データを保持するデータ記憶領域Ｍｉに無効フラグを書き込む。その後、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に削除完了の旨を通知し（ステップＳ２０７）、エントリ削除処理を終了する。
【００５９】
なお、上記エントリ削除処理は、エントリ保持回路１２において同一の実体データが重複して記憶されていない場合に適用されるものである。そのため、ステップＳ２０３において識別子＃（ｉ）のエントリデータが削除すべき実体データを含むと判定されれば、識別子＃（ｉ＋１）のエントリに削除すべき実体データが存在しないことが保証されている。同一の実体データの重複が許可されている場合には、ステップＳ２０５の実行後、メモリ制御部１３３Ｃは、変数ｉをインクリメントしてステップＳ２０３を実行する手順を採用することができる。
【００６０】
次に、図８を参照しつつ、エントリ保持回路１２に実体データを登録するためのエントリ登録処理について説明する。メモリ制御部１３３Ｃは、入出力装置１４からのエントリ登録指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間でエントリ登録処理を開始する。
【００６１】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ３０１）。次に、メモリ制御部１３３Ｃは、レジスタ回路４０ｉに保持されている識別子＃（ｉ）のエントリデータが、登録すべき特定データと一致する実体データを含むか否かを判定する（ステップＳ３０３）。エントリデータが当該実体データを含まない場合（ステップＳ３０３のＮＯ）、メモリ制御部１３３Ｃは、変数ｉが最上位のエントリを指す識別子番号ｎ−１に達したか否かを判定し（ステップＳ３２１）、変数ｉがｎ−１に達していなければ（ステップＳ３２１のＮＯ）、変数ｉを１だけインクリメントして（ステップＳ３２３）、処理手順をステップＳ３０３に戻す。
【００６２】
一方、識別子＃（ｉ）のエントリデータが、登録すべき特定データと一致する実体データを含むと判定された場合（ステップＳ３０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリを無効化する（ステップＳ３０５）。具体的には、データ検索部１３３Ａは、当該実体データを保持するデータ記憶領域Ｍｉに無効フラグを書き込む。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）のエントリが無効化されるまで待機する（ステップＳ３０７のＮＯ）。
【００６３】
識別子＃（ｎ−１）のエントリの無効化が完了したとき（ステップＳ３０７のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）のエントリ（空きエントリ）への特定データの書き込み制御を行う（ステップＳ３０９）。具体的には、メモリ制御部１３３Ｃは、最上位のエントリセレクタ６０ｎ−１に置換データＯＤｎを選択させる選択制御信号ＳＥＬｎ−１を供給し、エントリセレクタ６０ｎ−１に特定データを含む新たなエントリデータを置換データＯＤｎとして供給する。これによりレジスタ５０ｎ−１は、エントリセレクタ６０ｎ−１を介して入力されたエントリデータＯＤｎをラッチ（保持）する。その後、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に更新完了の旨を通知し（ステップＳ３１１）、エントリ登録処理を終了する。
【００６４】
一方、全てのエントリについて、登録すべき特定データと一致する実体データを含むエントリデータを探し出すことができなかったときは、変数ｉはｎ−１に達する（ステップＳ３０３のＮＯ及びステップＳ３２１のＹＥＳ）。このとき、メモリ制御部１３３Ｃは、エントリデータ受信部１３２から供給されるエントリデータ群３１に基づいて、識別子＃（ｎ−１）の最上位のエントリが無効か否かを判定する（ステップＳ３２５）。最上位のエントリが無効である場合（ステップＳ３２５のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）のエントリへの特定データの書き込み制御を行う（ステップＳ３３１）。その後、メモリ制御部１３３Ｃは、送受信部１３１を介して入出力装置１４に登録完了の旨を通知し（ステップＳ３３３）、エントリ登録処理を終了する。
【００６５】
上記ステップＳ３２５において最上位のエントリが無効ではない場合（ステップＳ３２５のＮＯ）、メモリ制御部１３３Ｃは、識別子＃（０）の最下位のエントリを無効化する（ステップＳ３２７）。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）のエントリが無効化されるまで待機する（ステップＳ３２９のＮＯ）。識別子＃（ｎ−１）のエントリの無効化が完了したとき（ステップＳ３２９のＹＥＳ）、メモリ制御部１３３Ｃは、ステップＳ３３１，Ｓ３３３を順次実行し、エントリ登録処理を終了する。
【００６６】
上記の図８のエントリ登録処理は、エントリ保持回路１２に同一の実体データが重複して記憶されることを許可しない場合の処理である。図９は、エントリ保持回路１２において同一の実体データが重複することを許可する場合のエントリ登録処理の手順を概略的に示すフローチャートである。図９のフローチャートは、図８のステップＳ３０３〜３１１が存在しない点を除いて図８のフローチャートと同じである。図８のステップＳ３０３の判定処理が行われないため、特定データは常に登録される。
【００６７】
なお、図２（Ｃ）に示したようにデータ領域２１が、複数の実体データを格納する複数の領域に機能的に分割されている場合、メモリ制御部１３３Ｃは、これら複数の実体データのうちの一部を書き換えることもできる。具体的には、メモリ制御部１３３Ｃは、レジスタ回路４０ｉのエントリセレクタ６０ｉに自エントリデータ制御回路７０ｉの出力データＡＤｉを選択させる選択制御信号ＳＥＬｉを供給し、自エントリデータ制御回路７０ｉにフィードバック出力ＯＤｉの中の複数の実体データの一部を別の実体データに置換させる制御信号Ｃｉを供給する。ここで、メモリ制御部１３３Ｃは、当該別の実体データを制御信号Ｃｉに含めて自エントリデータ制御回路７０ｉに供給することができる。たとえば、上記したように入出力装置１４が集線装置であり、ＭＡＣアドレスと通信ポート番号との対応関係を登録するアドレス検索回路としてエントリ保持回路１２を使用する場合、メモリ制御部１３３Ｃは、ＭＡＣアドレスに対応する通信ポート番号を書き換えることができる。また、メモリ制御部１３３Ｃは、必ず、エントリ保持回路１２に保持されているエントリデータ群３１の内容を確認することができるので、特定の対応関係を有する実体データの組み合わせをエントリ保持回路１２に保持させないようにすることができる。たとえば、エントリ保持回路１２において、１つのＭＡＣアドレスが関連付けられた通信ポート番号が複数個存在しないように制御することができる。
【００６８】
以上に説明したように、実施の形態１のデータ記憶装置１１では、エントリ制御回路１３のメモリ制御部１３３Ｃは、データ記憶領域Ｍ０〜Ｍｎ−１に対してエントリデータの書き込みを実行しない処理サイクル期間に、データ記憶領域Ｍ０〜Ｍｎ−１の中の空き領域Ｍｅの順位よりも上位のデータ記憶領域Ｍｅ＋１〜Ｍｎ−１に保持されているエントリデータを、下位のデータ記憶領域にシフトさせるシフト操作を行い、最上位のデータ記憶領域Ｍｎ−１に無効フラグを書き込む。これにより、有効値を持つ有効フラグを含むエントリデータを連続的に配置することができ、最上位のデータ記憶領域Ｍｎ−１を含む上位のデータ記憶領域を空き領域にすることができる。よって、上記特許文献２（特許第４３６９５２４号明細書）に開示されている技術のようにメモリ管理制御のために別の記憶領域を確保する必要がない。また、メモリ制御部１３３Ｃは有効なエントリを連続的に再配置して上位の空き領域を形成するので、データ検索処理、エントリ登録処理（図８及び図９）及びエントリ削除処理（図７）の処理速度を高速化することができる。データ記憶装置１１を実装する際には、エントリデータの登録や削除（無効化）といった操作と、エントリデータに対するシフト操作とが競合しないようにシステムを容易に設計することができ、しかも、ＬＲＵアルゴリズムなどのメモリ管理アルゴリズムに基づく制御に必要な記憶領域を別に確保せずに済むという利点がある。
【００６９】
また、エントリ保持回路１２がシフトレジスタ回路の構成を有しているので、エントリ制御回路１３は、メモリ制御部１３３Ｃによるエントリ保持回路１２に対する操作に影響を与えることなく、レジスタ５００〜５０ｎ−１の並列出力（エントリデータ群３１）から所望の実体データを取得する（読み出す）ことができる。また、メモリ制御部１３３Ｃは、レジスタ５００〜５０ｎ−１の並列出力に基づいて、エントリ保持回路１２の動作状態及び記憶内容を常時監視しながら最適な制御を行うこともできる。
【００７０】
したがって、実施の形態１のデータ記憶装置１１は、メモリ管理アルゴリズムに基づく制御を少ないメモリ消費量で効率良く実行することができる。特に、ＬＲＵアルゴリズムに基づく完全な制御を少ないメモリ消費量で効率良く実行することが可能である。
【００７１】
実施の形態２．
次に、本発明に係る実施の形態２について説明する。実施の形態２のデータ記憶装置の構成は、動作モードが異なる点を除いて、実施の形態１のデータ記憶装置１１の構成と同一である。実施の形態１については、エントリ保持回路１２におけるデータ記憶領域Ｍｉのフラグ領域２２が単一の制御フラグ（有効フラグ）を格納する場合の動作を説明した。本実施の形態では、データ記憶領域Ｍｉのフラグ領域２２は、図１０（Ａ），（Ｂ）に示されるように２つの領域２２Ａ，２２Ｂに機能的に分割されており、一方の領域２２Ａには上記有効フラグが格納され、他方の領域２２Ｂには静的フラグが格納される。静的フラグは、データ記憶領域Ｍｉに保持されるエントリデータの無効化を許可する許可値（たとえば「０」の値）と、エントリデータの無効化を許可しないマスク値（たとえば「１」の値）とのうちのいずれか一方を有するものである。
【００７２】
エントリ更新制御部１３３のメモリ制御部１３３Ｃは、上記実施の形態１に関して説明したエントリ登録処理やエントリ削除処理の際に、マスク値を持つ静的フラグを保持するデータ記憶領域Ｍｍ（ｍは０〜ｎ−１のいずれかの整数）を検出した場合には、そのデータ記憶領域Ｍｍに無効フラグを書き込まない、言い換えれば、データ記憶領域Ｍｍにおける登録済みのエントリを無効化しない機能を有する。これにより、データ記憶領域Ｍ０〜Ｍｎ−１のフラグ領域２２に要する記憶容量が増加するものの、より柔軟にエントリデータの登録や削除（無効化）などの操作を行うことが可能となる。
【００７３】
静的フラグは、新規の実体データの登録の際に設定される。実体データと無効フラグと静的フラグとを含むエントリデータがエントリ保持回路１２に登録された後、メモリ制御部１３３Ｃは、静的フラグの値に基づいて、登録済みのエントリデータに対する削除操作を行うのか否かを決めることができる。このため、メモリ管理アルゴリズムに基づく制御に関わらず、変更されないエントリデータをエントリ保持回路１２に記憶させることができる。
【００７４】
以下、図１１〜図１３を参照しつつ、実施の形態２のデータ記憶装置１１の動作を説明する。図１１は、実施の形態２に係るエントリ削除処理の手順を概略的に示すフローチャートである。図１１のフローチャートは、ステップＳ２０４，Ｓ２１４を除いて、図７のフローチャートと同じ手順を有する。また、図１２は、実施の形態２に係るエントリ登録処理の手順を概略的に示すフローチャートであり、図１３は、図１２のエントリ検索処理（ステップＳ３２６）の手順を示すフローチャートである。図１３のフローチャートは接続子Ｃ１を介して図１２のフローチャートと接続されている。また、図１２のフローチャートは、ステップＳ３０４，Ｓ３２６，Ｓ３２８，Ｓ３３５を除いて、図８のフローチャートと同じ手順を有する。
【００７５】
最初に、図１１を参照しつつ、エントリ削除処理について説明する。入出力装置１４からエントリ削除指示を含むアクセス要求ＲＱが受信されると、メモリ制御部１３３Ｃは、このエントリ削除指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間にエントリ削除処理を開始する。
【００７６】
ステップＳ２０３で識別子＃（ｉ）のエントリデータが削除すべき実体データを含むと判定された場合（ステップＳ２０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）を有するレジスタ回路４０ｉに保持されている静的フラグ（以下、識別子＃（ｉ）の静的フラグと呼ぶ。）が有意か否かを判定する（ステップＳ２０４）。静的フラグが有意である場合、すなわち、静的フラグがマスク値を有する場合（ステップＳ２０４のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリの無効化（ステップＳ２０５）を実行せずに、静的フラグによる更新不能の旨を送受信部１３１を介して入出力装置１４に通知し（ステップＳ２１４）、エントリ削除処理を終了する。一方、静的フラグが有意でない場合（ステップＳ２０４のＮＯ）、メモリ制御部１３３Ｃは、ステップＳ２０５，Ｓ２０７を実行した後に、エントリ削除処理を終了する。
【００７７】
ところで、メモリ制御部１３３Ｃは、静的フラグを参照せずにエントリ削除を実行する動作モードをも有する。具体的には、入出力装置１４からエントリ強制削除指示を含むアクセス要求ＲＱが受信されたとき、メモリ制御部１３３Ｃは、このエントリ強制削除指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に、静的フラグを参照するエントリ削除処理（図１１）ではなく、図７のエントリ削除処理を実行する。これにより、状況に応じて、有意な静的フラグを含むエントリデータを強制的に無効化して空き領域を確保することができる。
【００７８】
次に、図１２及び図１３を参照しつつ、特定データと一致する実体データを含むエントリデータを登録するためのエントリ登録処理について説明する。入出力装置１４からエントリ登録指示を含むアクセス要求ＲＱが受信されると、メモリ制御部１３３Ｃは、このエントリ登録指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に図１２のエントリ登録処理を開始する。
【００７９】
ステップＳ３０３で識別子＃（ｉ）のエントリデータが、登録すべき特定データと一致する実体データを含むと判定された場合（ステップＳ３０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）を有するレジスタ回路４０ｉに保持されている静的フラグが有意か否かを判定する（ステップＳ３０４）。静的フラグが有意である場合、すなわち、静的フラグがマスク値を有する場合（ステップＳ３０４のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリの無効化（ステップＳ３０５）をせずに、静的フラグによる更新不能の旨を送受信部１３１を介して入出力装置１４に通知し（ステップＳ３３５）、エントリ登録処理を終了する。
【００８０】
一方、全識別子＃（０）〜＃（ｎ−１）のエントリデータが、登録すべき特定データと一致する実体データを含まず、識別子＃（ｎ−１）のエントリが有効であると判定した場合（ステップＳ３２５のＮＯ）、メモリ制御部１３３Ｃは、空き領域をつくるためにエントリ検索処理（ステップＳ３２６）を実行する。
【００８１】
図１３を参照すると、メモリ制御部１３３Ｃは、変数ｋにゼロ値を設定し（ステップＳ３４１）、識別子＃（ｋ）の静的フラグが有意か否かを判定する（ステップＳ３４２）。識別子＃（ｋ）の静的フラグが有意である場合（ステップＳ３４２のＹＥＳ）、メモリ制御部１３３Ｃは、変数ｋが最上位のエントリを指す識別子番号ｎ−１に達したか否かを判定し（ステップＳ３４３）、変数ｋがｎ−１に達していなければ（ステップＳ３４３のＮＯ）、変数ｋを１だけインクリメントして（ステップＳ３４５）、手順をステップＳ３４２に戻す。
【００８２】
図１３のフローチャートにおいて全識別子＃（０）〜＃（ｎ−１）の静的フラグが有意である場合は、変数ｋはｎ−１に達する（ステップＳ３４３のＹＥＳ）。この場合、メモリ制御部１３３Ｃは、登録不能の旨を送受信部１３１を介して入出力装置１４に通知し（ステップＳ３４７）、エントリ登録処理を終了する。なお、登録不能の旨の通知（ステップＳ３４７）に代えて、別の処理を行うことも可能である。
【００８３】
ステップＳ３４２で識別子＃（ｋ）の静的フラグが有意ではないと判定した場合（ステップＳ３４２のＮＯ）、メモリ制御部１３３Ｃは、図１２のフローチャートに処理を戻す。次いで、メモリ制御部１３３Ｃは、識別子＃（ｋ）のエントリを無効化する（ステップＳ３２８）。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）のエントリが無効化されるまで待機する（ステップＳ３２９のＮＯ）。識別子＃（ｎ−１）のエントリの無効化が完了したとき（ステップＳ３２９のＹＥＳ）、メモリ制御部１３３Ｃは、ステップＳ３３１，Ｓ３３３を順次実行し、エントリ登録処理を終了する。
【００８４】
ところで、メモリ制御部１３３Ｃは、静的フラグを参照せずにエントリ登録を実行する動作モードを有する。具体的には、入出力装置１４からエントリ強制登録指示を含むアクセス要求ＲＱが受信されたとき、メモリ制御部１３３Ｃは、このエントリ強制登録指示に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に、静的フラグを参照するエントリ登録処理（図１２及び図１３）ではなく、図８のエントリ登録処理を実行する。これにより、状況に応じて、静的フラグの値に関わりなくエントリ登録を強制的に行うことができる。
【００８５】
以上に説明したように実施の形態２によれば、特定のエントリデータが変更されないようにすることができるので、エントリデータの登録や削除（無効化）などの操作の柔軟性を向上させることができる。
【００８６】
なお、メモリ制御部１３３Ｃは、データ記憶領域Ｍ０〜Ｍｎ−１のうち有意な静的フラグを保持しないデータ記憶領域に無効フラグを書き込むことで、有意ではない静的フラグを含むエントリデータを一斉に削除する操作を簡易に組み込むこともできる。
【００８７】
実施の形態３．
次に、本発明に係る実施の形態３について説明する。実施の形態３のデータ記憶装置の構成は、動作モードが異なる点を除いて、実施の形態１のデータ記憶装置１１の構成と同一である。実施の形態１については、エントリ保持回路１２におけるデータ記憶領域Ｍｉのフラグ領域２２が単一の制御フラグ（有効フラグ）を格納する場合の動作を説明した。本実施の形態では、データ記憶領域Ｍｉのフラグ領域２２は、図１４（Ａ），（Ｂ）に示されるように２つの領域２２Ａ，２２Ｂに機能的に分割されており、一方の領域２２Ａには上記有効フラグが格納され、他方の領域２２Ｂには削除フラグが格納される。削除フラグは、データ記憶領域Ｍｉに保持されているエントリデータの無効化が予定されていることを示す有効値（たとえば「１」の値）と、データ記憶領域Ｍｉに保持されているエントリデータの無効化が予定されていないことを示す無効値（たとえば「０」の値）とのうちのいずれか一方の値を有する。以下、有効値を持つ削除フラグを「有効な削除フラグ」と呼び、無効値を持つ削除フラグを「無効な削除フラグ」と呼ぶこととする。
【００８８】
メモリ制御部１３３Ｃは、或る処理サイクル期間ＴＡにデータ記憶領域Ｍ０〜Ｍｎ−１の全部または一部に有効な削除フラグを書き込み、所定の設定期間ΔＴ経過後の処理サイクル期間ＴＢに、有効な削除フラグを保持する当該データ記憶領域の全てに無効フラグを書き込むことにより有効な削除フラグを含むエントリデータを一括して無効化（削除）する機能を有する。これにより、エントリ保持回路１２に空き領域をまとめて確保することができる。ただし、メモリ制御部１３３Ｃは、設定期間ΔＴ内にエントリデータのいずれかを更新したとき、当該更新されたエントリデータを保持するデータ記憶領域には無効な削除フラグを書き込む。設定期間ΔＴ内に登録されたエントリデータはいずれも無効な削除フラグを含む。よって、設定期間ΔＴ経過後の処理サイクル期間ＴＢでは、設定期間ΔＴ内に更新または登録されたエントリデータが無効化（削除）されない。
【００８９】
また、メモリ制御部１３３Ｃは、外部の入出力装置１４から削除フラグ付与指示を含むアクセス要求ＲＱが受信されたとき、この削除フラグ付与指示に応じて、データ記憶領域Ｍ０〜Ｍｎ−１の全部または一部に有効な削除フラグを書き込み、所定の設定期間ΔＴ経過後の処理サイクル期間に、有効な削除フラグを保持する当該データ記憶領域の全てに無効フラグを書き込むことにより有効な削除フラグを含むエントリデータを一括して削除する機能をも有する。この場合も、メモリ制御部１３３Ｃは、設定期間ΔＴ内にエントリデータのいずれかを更新したとき、当該更新されたエントリデータを保持するデータ記憶領域には無効な削除フラグを書き込む。また、設定期間ΔＴ内に登録されたエントリデータはいずれも無効な削除フラグを含む。
【００９０】
さらに、メモリ制御部１３３Ｃは、外部の入出力装置１４からの空き領域確保指示に応じて、設定期間ΔＴの経過を待つことなく、有効な削除フラグを保持する当該データ記憶領域の全てに無効フラグを書き込むことにより有効な削除フラグを含むエントリデータを一括して無効化（削除）する機能をも有する。
【００９１】
上記機能を有することにより、データ記憶装置１１は、エントリ保持回路１２の空き領域をまとめて確保する制御を行うことができる。たとえば、エントリ保持回路１２が有効なエントリで満杯となる前であっても、登録または更新されてから一定期間経過したエントリデータを自動的に抹消し、優先順位の低いエントリデータをエントリ保持回路１２内に残さないような制御を行うことができる。
【００９２】
次に、図１５を参照しつつ、上記削除フラグを使用する実施の形態３のデータ記憶装置１１の動作を説明する。図１５は、実施の形態３に係るエントリ操作の制御処理の一例を概略的に示すフローチャートである。或る時刻に達したとき、あるいは、外部の入出力装置１４から削除フラグ付与指示を含むアクセス要求ＲＱが受信されたとき、これに応じて図１５の制御処理が開始される。
【００９３】
先ず、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ４０１）。次に、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリに有効な削除フラグを設定する（ステップＳ４０３）。具体的には、メモリ制御部１３３Ｃは、識別子＃（ｉ）のレジスタ回路４０ｉ（図４）のエントリセレクタ６０ｉに自エントリデータ制御回路７０ｉの出力データＡＤｉを選択させる選択制御信号ＳＥＬｉを供給し、自エントリデータ制御回路７０ｉに有効な削除フラグを含む置換データＡＤｉを生成させる制御信号Ｃｉを供給する。有効な削除フラグの設定（ステップＳ４０３）の後、変数ｉが識別子番号ｎ−１に達したか否かを判定する（ステップＳ４０５）。変数ｉがｎ−１に達していなければ（ステップＳ４０５のＮＯ）、メモリ制御部１３３Ｃは、変数ｉを１だけインクリメントし（ステップＳ４０７）、手順をステップＳ４０３に戻す。
【００９４】
変数ｉがｎ−１に達すると（ステップＳ４０５のＹＥＳ）、メモリ制御部１３３Ｃは、設定期間ΔＴが経過して設定時刻が到来するまで待機する（ステップＳ４０９のＮＯ）。設定時刻が到来すると（ステップＳ４０９のＹＥＳ）、メモリ制御部１３３Ｃは、変数ｉを初期化して変数ｉにゼロ値を設定する（ステップＳ４１１）。次に、メモリ制御部１３３Ｃは、識別子＃（ｉ）の削除フラグが有効であるか否かを判定する（ステップＳ４１３）。削除フラグが有効であれば（ステップＳ４１３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｉ）のエントリを無効化する（ステップＳ４１５）。次いで、変数ｉがｎ−１に達したか否かを判定する（ステップＳ４１７）。一方、削除フラグが有効でなければ（ステップＳ４１３のＮＯ）、メモリ制御部１３３Ｃは、エントリの無効化（ステップＳ４１５）をスキップして、変数ｉがｎ−１に達したか否かを判定する（ステップＳ４１７）。変数ｉがｎ−１に達していなければ（ステップＳ４１７のＮＯ）、メモリ制御部１３３Ｃは、変数ｉを１だけインクリメントし（ステップＳ４１９）、手順をステップＳ４１３に戻す。その後、変数ｉがｎ−１に達すると（ステップＳ４１７のＹＥＳ）、処理を終了する。
【００９５】
以上の処理により、一定期間経過後、登録あるいは更新のなされていないエントリデータの削除を行うことができる。なお、上記ステップＳ４０１〜Ｓ４０７の処理は１処理サイクル期間内に完了し、ステップＳ４１１〜Ｓ４１７の処理も１処理サイクル期間内に完了する。
【００９６】
ところで、上記制御処理においては、有効な削除フラグを含むエントリデータの無効化（ステップＳ４１５）を実行後、後に無効化すべきエントリに有効な削除フラグを設定する処理を実行する手順を追加してもよい。また、上記ステップＳ４０１〜Ｓ４０７の処理と、ステップＳ４１１〜Ｓ４１９の処理とは別々の処理として実行されてもよい。さらに、ステップＳ４１１〜Ｓ４１９の処理の実行後、ステップＳ４０１〜Ｓ４０７の処理が実行されてもよい。
【００９７】
以上に説明したように、実施の形態３のデータ記憶装置を用いれば、エントリデータに要する記憶容量が増加するものの、一定期間内に登録または更新されなかったエントリデータに対して一括削除を行うことができる。また、ＬＲＵアルゴリズムなどのメモリ管理アルゴリズムに基づく制御を継続して実行することができる。
【００９８】
実施の形態４．
次に、本発明に係る実施の形態４について説明する。実施の形態４のデータ記憶装置は、実施の形態１のデータ記憶装置１１と同一の構成を有する。実施の形態４では、エントリ更新制御部１３３が、上記機能に加えて、エントリ保持回路１２内のデータ記憶領域Ｍ０〜Ｍｎ−１に保持されているエントリデータのうち、直近に参照されたエントリデータを最上位のデータ記憶領域Ｍｎ−１に保持させる機能を有している。図１６は、この機能を実現するためのエントリ更新処理の手順を概略的に示すフローチャートである。
【００９９】
入出力装置１４からデータ参照要求を含むアクセス要求ＲＱが受信されると、データ検索部１３３Ａは、このデータ参照要求に応じて、エントリデータ群３１の中からデータ参照要求で指定される実体データを取得し、この実体データを送受信部１３１を介して入出力装置１４に送信する。一方、メモリ制御部１３３Ｃは、データ参照要求に応じて、エントリ保持回路１２の動作状態を把握し、適切な処理サイクル期間に図１６のエントリ更新処理を開始する。
【０１００】
まず、メモリ制御部１３３Ｃは、データ参照要求により参照されたエントリデータ（以下「参照データ」と呼ぶ。）を保持するデータ記憶領域Ｍｐのアクセス順位が最上位であるか否かを判定する（ステップＳ５０１）。参照データが最上位のデータ記憶領域Ｍｎ−１に保持されていると判定したとき（ステップＳ５０１のＹＥＳ）、メモリ制御部１３３Ｃは、エントリ更新処理を終了する。一方、参照データが最上位のデータ記憶領域Ｍｎ−１に保持されていないと判定したとき（ステップＳ５０１のＮＯ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）の最上位のエントリが無効か否かを判定する（ステップＳ５０３）。最上位のエントリが無効である場合（ステップＳ５０３のＹＥＳ）、メモリ制御部１３３Ｃは、識別子＃（ｎ−１）のエントリへの参照データの書き込み制御を実行する（ステップＳ５０９）。具体的には、メモリ制御部１３３Ｃは、最上位のエントリセレクタ６０ｎ−１に置換データＯＤｎを選択させる選択制御信号ＳＥＬｎ−１を供給し、エントリセレクタ６０ｎ−１に参照データを置換データＯＤｎとして供給する。これによりレジスタ５０ｎ−１は、エントリセレクタ６０ｎ−１を介して入力された参照データＯＤｎをラッチ（保持）する。
【０１０１】
一方、ステップＳ５０３で最上位のエントリが無効ではないと判定したとき（ステップＳ５０３のＮＯ）、メモリ制御部１３３Ｃは、参照データを保持する識別子＃（ｐ）のエントリを無効化する（ステップＳ５０５）。その後、次の処理サイクル期間に上記エントリ並べ替え処理（図５）が実行されて識別子＃（ｎ−１）の最上位エントリが無効化されるまで待機する（ステップＳ５０７のＮＯ）。最上位エントリの無効化が完了したとき（ステップＳ５０７のＹＥＳ）、メモリ制御部１３３Ｃは、最上位エントリに対する参照データの書き込み制御を実行し（ステップＳ５０９）、エントリ更新処理を終了する。
【０１０２】
図１７（Ａ）〜（Ｄ）は、最大エントリ数が７の場合のデータ記憶領域Ｍ０〜Ｍ６に対して図１６のエントリ更新処理が実行されたときの、データ記憶領域Ｍ０〜Ｍ６の状態遷移の様子を示す図である。図１７（Ａ）に示されるように、最初の状態では、全てのデータ記憶領域Ｍ０〜Ｍ６のエントリは有効であり、データ記憶領域Ｍ０〜Ｍ６はそれぞれエントリデータＤ０〜Ｄ６を保持している。データ参照要求に応じてエントリデータＤ３が参照されたとき、図１７（Ｂ）に示されるように、参照データＤ３を保持する識別子＃（３）のエントリが無効化される（図１６のステップＳ５０５）。次の処理サイクル期間にシフト操作と最上位エントリの無効化処理とが実行される。これにより、図１７（Ｃ）に示されるように、識別子＃（３），＃（４），＃（５）のエントリにそれぞれエントリデータＤ４，Ｄ５，Ｄ６がシフトする。その後、図１７（Ｄ）に示されるように、識別子＃（６）のデータ記憶領域Ｍ６に参照データＤ３が書き込まれる（図１６のステップＳ５０９）。
【０１０３】
以上に説明したように、実施の形態４によれば、直近に参照されたエントリデータを最上位のデータ記憶領域Ｍｎ−１に常に保持させることができる。したがって、直近に参照されたエントリデータの優先順位を最も高くするメモリ管理アルゴリズムを実現することができる。
【０１０４】
実施の形態１〜４の変形例．
以上、図面を参照して本発明に係る種々の実施の形態について述べたが、これらは本発明の例示であり、上記以外の様々な形態を採用することができる。たとえば、図１８（Ａ），（Ｂ）に示されるように、データ記憶領域Ｍｉのフラグ領域２２を３つの領域２２Ａ，２２Ｂ，２２Ｃに機能的に分割し、領域２２Ａには上記有効フラグを格納し、領域２２Ｂに上記静的フラグを格納し、領域２２Ｃに上記削除フラグを格納してもよい。これにより、データ記憶装置１１は、有効フラグ、静的フラグ及び削除フラグを用いた処理を実行することができる。具体的には、設定期間ΔＴ内に未登録あるいは未更新のエントリデータでも、有意な静的フラグを含むエントリデータは一括削除の対象外とすることができる。たとえば、識別子＃（ｉ）の静的フラグが有意であるか否かを判定し、静的フラグが有意であれば、図１５のステップＳ４０３において有効な削除フラグを設定せず、静的フラグが有意でなければ、ステップＳ４０３において有効な削除フラグを設定してもよい。
【０１０５】
また、上記実施の形態１〜３においては、エントリ保持回路１２はシフトレジスタ回路の構成を有しているが、これに限定されるものではない。エントリ保持回路１２へのアクセス速度が高速であることが要求されないシステムにデータ記憶装置１１が適用される場合は、エントリ保持回路１２をＲＡＭ（ランダム・アクセス・メモリ）で構成してもよい。
【０１０６】
また、エントリ制御回路１３の全部または一部の機能は、ハードウェアで実現されてもよいし、あるいは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などのマイクロプロセッサにより実行されるコンピュータプログラムで実現されてもよい。当該機能がコンピュータプログラムで実現される場合、マイクロプロセッサは、コンピュータ読み取り可能な記録媒体からコンピュータプログラムをロードし実行することにより当該機能を実現することが可能である。
【符号の説明】
【０１０７】
１ データ処理システム、 １１ データ記憶装置、 １２ エントリ保持回路、 １３ エントリ制御回路、 １３１ 送受信部、 １３２ エントリデータ受信部、 １３３ エントリ更新制御部、 １３３Ａ データ検索部、 １３３Ｂ 領域検出部、 １３３Ｃ メモリ制御部、 １４ 入出力装置、 Ｍ０〜Ｍｎ−１ データ記憶領域、 ２１ データ領域、 ４００〜４０ｎ−１ レジスタ回路、 ５００〜５０ｎ−１ レジスタ、 ６００〜６０ｎ−１ エントリセレクタ、 ７００〜７０ｎ−１ 自エントリデータ制御回路。
【特許請求の範囲】
【請求項１】
所定のメモリ管理アルゴリズムに基づく優先順位を有する複数のエントリデータをそれぞれ保持し、該複数のエントリデータの優先順位に対応する順位がそれぞれ割り当てられた複数のデータ記憶領域を有するエントリ保持回路と、
外部装置からのアクセス要求に応じて、前記複数のデータ記憶領域に対して前記エントリデータの読み出し及び書き込みを実行するエントリ制御回路と、
を備え、
前記各データ記憶領域は、
当該各データ記憶領域に保持されるエントリデータを有効にする有効値及び当該各データ記憶領域に保持されるエントリデータを無効にする無効値のうちのいずれか一方の値を持つ有効フラグを格納する有効フラグ領域と、
実体データを格納するデータ領域と、
を有し、
前記エントリ制御回路は、
前記複数のデータ記憶領域の中から前記無効値を持つ有効フラグを保持する無効化データ領域を空き領域として検出する領域検出部と、
前記複数のデータ記憶領域に対して前記エントリデータの書き込みが実行されない間に、前記複数のデータ記憶領域のうち前記無効化データ領域の順位よりも上位のデータ記憶領域に保持されているエントリデータを、前記上位のデータ記憶領域よりも下位の当該データ記憶領域にシフトさせるシフト操作を行うとともに、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記無効値を持つ有効フラグを書き込むメモリ制御部と、
を含むことを特徴とするデータ記憶装置。
【請求項２】
請求項１に記載のデータ記憶装置であって、
前記エントリ保持回路は、
前記複数のデータ記憶領域をそれぞれ構成する複数段のレジスタと、
前記メモリ制御部から供給された選択制御信号に応じて、前記複数段のレジスタの中から指定されたレジスタにより出力された当該エントリデータを選択し、当該選択されたエントリデータを、前記指定されたレジスタよりも１つ後段の当該レジスタに出力する複数のセレクタと、
を含むシフトレジスタ回路であり、
前記メモリ制御部は、前記領域検出部により前記無効化データ領域が検出されたとき、前記複数段のレジスタのうち前記上位のデータ記憶領域を構成するレジスタを指定する制御信号を前記選択制御信号として前記複数のセレクタに供給する、
ことを特徴とするデータ記憶装置。
【請求項３】
請求項２に記載のデータ記憶装置であって、前記複数段のレジスタの並列出力が前記エントリ制御回路に供給されていることを特徴とするデータ記憶装置。
【請求項４】
請求項３に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記アクセス要求として検索キーデータとともに検索要求が受信されたとき、前記検索要求に応じて、前記複数段のレジスタの並列出力に基づいて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータの中から前記検索キーデータと一致する実体データを検索し、その検索結果を前記外部装置に返すデータ検索部
をさらに含むことを特徴とするデータ記憶装置。
【請求項５】
請求項４に記載のデータ記憶装置であって、
前記データ記憶領域は、互いに関連付けされた複数の前記実体データを含み、
前記データ検索部は、前記複数のデータ記憶領域を検索テーブルとして使用する、
ことを特徴とするデータ記憶装置。
【請求項６】
請求項３に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記アクセス要求として有効エントリ数通知指示が受信されたとき、前記有効エントリ数通知指示に応じて、前記複数段のレジスタの並列出力に基づいて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータを計数し、その計数結果を前記外部装置に通知するデータ検索部
をさらに含むことを特徴とするデータ記憶装置。
【請求項７】
請求項１から３のうちのいずれか１項に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記アクセス要求として特定データの削除指示が受信されたとき、前記削除指示に応じて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータの中から前記特定データと一致する削除すべき実体データを検索するデータ検索部
をさらに含み、
前記メモリ制御部は、前記データ検索部により前記削除すべき実体データが探し出されたとき、前記複数のデータ記憶領域のうち前記削除すべき実体データを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込み、その結果を前記外部装置に通知する、
ことを特徴とするデータ記憶装置。
【請求項８】
請求項７に記載のデータ記憶装置であって、前記データ検索部は、前記削除すべき実体データを探し出すことができなかったとき、その結果を前記外部装置に通知することを特徴とするデータ記憶装置。
【請求項９】
請求項１から８のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ制御部は、前記アクセス要求として一斉削除指示が受信されたとき、前記複数のデータ記憶領域の全てに前記無効値を持つ有効フラグを書き込み、その結果を前記外部装置に通知することを特徴とするデータ記憶装置。
【請求項１０】
請求項１から３のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ制御部は、前記アクセス要求としてエントリ登録指示が受信されたとき、前記エントリ登録指示に応じて、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記無効値を持つ有効フラグが保持されている場合は、前記エントリ登録指示で指定される登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記最上位のデータ記憶領域に書き込む、ことを特徴とするデータ記憶装置。
【請求項１１】
請求項１０に記載のデータ記憶装置であって、前記メモリ制御部は、前記エントリ登録指示に応じて、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記有効値を持つ有効フラグが保持されている場合は、前記複数のデータ記憶領域のうち最下位のデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、前記登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記最上位のデータ記憶領域に書き込む、ことを特徴とするデータ記憶装置。
【請求項１２】
請求項１０または１１に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記エントリ登録指示に応じて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータの中から、前記登録すべき実体データと一致する実体データを検索するデータ検索部、
をさらに含み、
前記メモリ制御部は、前記データ検索部により前記登録すべき実体データと一致する実体データが探し出されたときは、前記登録すべき実体データと一致する実体データを含むエントリデータを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、前記登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記複数のデータ記憶領域のうち最上位のデータ記憶領域に書き込む、
ことを特徴とするデータ記憶装置。
【請求項１３】
請求項１から９のうちのいずれか１項に記載のデータ記憶装置であって、
前記各データ記憶領域は、
当該各データ記憶領域に保持されるエントリデータの無効化を許可する許可値及び当該各データ記憶領域に保持されるエントリデータの無効化を許可しないマスク値のうちのいずれか一方の値を持つ静的フラグを格納する静的フラグ領域をさらに有し、
前記メモリ制御部は、前記複数のデータ記憶領域のうち前記マスク値を持つ静的フラグを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込まないことを特徴とするデータ記憶装置。
【請求項１４】
請求項１３に記載のデータ記憶装置であって、
前記メモリ制御部は、前記アクセス要求としてエントリ登録指示が受信されたとき、前記エントリ登録指示に応じて、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記有効値を持つ有効フラグが保持されている場合は、前記複数のデータ記憶領域のうち前記許可値を持つ静的フラグを保持する最も優先順位の低いデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、前記エントリ登録指示で指定される登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記最上位のデータ記憶領域に書き込む、
ことを特徴とするデータ記憶装置。
【請求項１５】
請求項１から１４のうちのいずれか１項に記載のデータ記憶装置であって、
前記各データ記憶領域は、
当該各データ記憶領域に保持されているエントリデータの無効化が予定されていることを示す値と当該各データ記憶領域に保持されているエントリデータの無効化が予定されていないことを示す値とのうちのいずれか一方の値を持つ削除フラグを格納する削除フラグ領域をさらに有し、
前記メモリ制御部は、前記複数のデータ記憶領域のいずれかに前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを書き込み、所定の設定期間経過後、前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを保持する当該データ記憶領域の全てに前記無効値を持つ有効フラグを書き込む、
ことを特徴とするデータ記憶装置。
【請求項１６】
請求項１５に記載のデータ記憶装置であって、前記メモリ制御部は、前記設定期間内に、前記複数のエントリデータのいずれかを更新したとき、当該更新されたエントリデータを保持する当該データ記憶領域に前記エントリデータの無効化が予定されていないことを示す値を持つ削除フラグを書き込むことを特徴とするデータ記憶装置。
【請求項１７】
請求項１から１４のうちのいずれか１項に記載のデータ記憶装置であって、
前記各データ記憶領域は、
当該各データ記憶領域に保持されているエントリデータの無効化が予定されていることを示す値と当該各データ記憶領域に保持されているエントリデータの無効化が予定されていないことを示す値とのうちのいずれか一方の値を持つ削除フラグを格納する削除フラグ領域をさらに有し、
前記メモリ制御部は、前記アクセス要求として削除フラグ付与指示が受信されたときに前記複数のデータ記憶領域のいずれかに前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを書き込み、所定の設定期間経過後、前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを保持する当該データ記憶領域の全てに前記無効値を持つ有効フラグを書き込む、ことを特徴とするデータ記憶装置。
【請求項１８】
請求項１から１７のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ管理アルゴリズムは、最も長い間参照されていない実体データを含むエントリデータの優先順位を最も低くするアルゴリズムであることを特徴とするデータ記憶装置。
【請求項１９】
請求項１から１８のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ制御部は、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち、直近に参照された実体データを含む参照データを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、最上位の前記データ記憶領域に前記参照データを書き込むことを特徴とするデータ記憶装置。
【請求項２０】
請求項１に記載のデータ記憶装置であって、前記エントリ保持回路は、ランダム・アクセス・メモリであることを特徴とするデータ記憶装置。
【請求項１】
所定のメモリ管理アルゴリズムに基づく優先順位を有する複数のエントリデータをそれぞれ保持し、該複数のエントリデータの優先順位に対応する順位がそれぞれ割り当てられた複数のデータ記憶領域を有するエントリ保持回路と、
外部装置からのアクセス要求に応じて、前記複数のデータ記憶領域に対して前記エントリデータの読み出し及び書き込みを実行するエントリ制御回路と、
を備え、
前記各データ記憶領域は、
当該各データ記憶領域に保持されるエントリデータを有効にする有効値及び当該各データ記憶領域に保持されるエントリデータを無効にする無効値のうちのいずれか一方の値を持つ有効フラグを格納する有効フラグ領域と、
実体データを格納するデータ領域と、
を有し、
前記エントリ制御回路は、
前記複数のデータ記憶領域の中から前記無効値を持つ有効フラグを保持する無効化データ領域を空き領域として検出する領域検出部と、
前記複数のデータ記憶領域に対して前記エントリデータの書き込みが実行されない間に、前記複数のデータ記憶領域のうち前記無効化データ領域の順位よりも上位のデータ記憶領域に保持されているエントリデータを、前記上位のデータ記憶領域よりも下位の当該データ記憶領域にシフトさせるシフト操作を行うとともに、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記無効値を持つ有効フラグを書き込むメモリ制御部と、
を含むことを特徴とするデータ記憶装置。
【請求項２】
請求項１に記載のデータ記憶装置であって、
前記エントリ保持回路は、
前記複数のデータ記憶領域をそれぞれ構成する複数段のレジスタと、
前記メモリ制御部から供給された選択制御信号に応じて、前記複数段のレジスタの中から指定されたレジスタにより出力された当該エントリデータを選択し、当該選択されたエントリデータを、前記指定されたレジスタよりも１つ後段の当該レジスタに出力する複数のセレクタと、
を含むシフトレジスタ回路であり、
前記メモリ制御部は、前記領域検出部により前記無効化データ領域が検出されたとき、前記複数段のレジスタのうち前記上位のデータ記憶領域を構成するレジスタを指定する制御信号を前記選択制御信号として前記複数のセレクタに供給する、
ことを特徴とするデータ記憶装置。
【請求項３】
請求項２に記載のデータ記憶装置であって、前記複数段のレジスタの並列出力が前記エントリ制御回路に供給されていることを特徴とするデータ記憶装置。
【請求項４】
請求項３に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記アクセス要求として検索キーデータとともに検索要求が受信されたとき、前記検索要求に応じて、前記複数段のレジスタの並列出力に基づいて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータの中から前記検索キーデータと一致する実体データを検索し、その検索結果を前記外部装置に返すデータ検索部
をさらに含むことを特徴とするデータ記憶装置。
【請求項５】
請求項４に記載のデータ記憶装置であって、
前記データ記憶領域は、互いに関連付けされた複数の前記実体データを含み、
前記データ検索部は、前記複数のデータ記憶領域を検索テーブルとして使用する、
ことを特徴とするデータ記憶装置。
【請求項６】
請求項３に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記アクセス要求として有効エントリ数通知指示が受信されたとき、前記有効エントリ数通知指示に応じて、前記複数段のレジスタの並列出力に基づいて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータを計数し、その計数結果を前記外部装置に通知するデータ検索部
をさらに含むことを特徴とするデータ記憶装置。
【請求項７】
請求項１から３のうちのいずれか１項に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記アクセス要求として特定データの削除指示が受信されたとき、前記削除指示に応じて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータの中から前記特定データと一致する削除すべき実体データを検索するデータ検索部
をさらに含み、
前記メモリ制御部は、前記データ検索部により前記削除すべき実体データが探し出されたとき、前記複数のデータ記憶領域のうち前記削除すべき実体データを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込み、その結果を前記外部装置に通知する、
ことを特徴とするデータ記憶装置。
【請求項８】
請求項７に記載のデータ記憶装置であって、前記データ検索部は、前記削除すべき実体データを探し出すことができなかったとき、その結果を前記外部装置に通知することを特徴とするデータ記憶装置。
【請求項９】
請求項１から８のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ制御部は、前記アクセス要求として一斉削除指示が受信されたとき、前記複数のデータ記憶領域の全てに前記無効値を持つ有効フラグを書き込み、その結果を前記外部装置に通知することを特徴とするデータ記憶装置。
【請求項１０】
請求項１から３のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ制御部は、前記アクセス要求としてエントリ登録指示が受信されたとき、前記エントリ登録指示に応じて、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記無効値を持つ有効フラグが保持されている場合は、前記エントリ登録指示で指定される登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記最上位のデータ記憶領域に書き込む、ことを特徴とするデータ記憶装置。
【請求項１１】
請求項１０に記載のデータ記憶装置であって、前記メモリ制御部は、前記エントリ登録指示に応じて、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記有効値を持つ有効フラグが保持されている場合は、前記複数のデータ記憶領域のうち最下位のデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、前記登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記最上位のデータ記憶領域に書き込む、ことを特徴とするデータ記憶装置。
【請求項１２】
請求項１０または１１に記載のデータ記憶装置であって、
前記エントリ制御回路は、
前記エントリ登録指示に応じて、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち前記有効値を持つ有効フラグを含むエントリデータの中から、前記登録すべき実体データと一致する実体データを検索するデータ検索部、
をさらに含み、
前記メモリ制御部は、前記データ検索部により前記登録すべき実体データと一致する実体データが探し出されたときは、前記登録すべき実体データと一致する実体データを含むエントリデータを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、前記登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記複数のデータ記憶領域のうち最上位のデータ記憶領域に書き込む、
ことを特徴とするデータ記憶装置。
【請求項１３】
請求項１から９のうちのいずれか１項に記載のデータ記憶装置であって、
前記各データ記憶領域は、
当該各データ記憶領域に保持されるエントリデータの無効化を許可する許可値及び当該各データ記憶領域に保持されるエントリデータの無効化を許可しないマスク値のうちのいずれか一方の値を持つ静的フラグを格納する静的フラグ領域をさらに有し、
前記メモリ制御部は、前記複数のデータ記憶領域のうち前記マスク値を持つ静的フラグを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込まないことを特徴とするデータ記憶装置。
【請求項１４】
請求項１３に記載のデータ記憶装置であって、
前記メモリ制御部は、前記アクセス要求としてエントリ登録指示が受信されたとき、前記エントリ登録指示に応じて、前記複数のデータ記憶領域のうち最上位のデータ記憶領域に前記有効値を持つ有効フラグが保持されている場合は、前記複数のデータ記憶領域のうち前記許可値を持つ静的フラグを保持する最も優先順位の低いデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、前記エントリ登録指示で指定される登録すべき実体データと前記有効値を持つ有効フラグとを含むエントリデータを前記最上位のデータ記憶領域に書き込む、
ことを特徴とするデータ記憶装置。
【請求項１５】
請求項１から１４のうちのいずれか１項に記載のデータ記憶装置であって、
前記各データ記憶領域は、
当該各データ記憶領域に保持されているエントリデータの無効化が予定されていることを示す値と当該各データ記憶領域に保持されているエントリデータの無効化が予定されていないことを示す値とのうちのいずれか一方の値を持つ削除フラグを格納する削除フラグ領域をさらに有し、
前記メモリ制御部は、前記複数のデータ記憶領域のいずれかに前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを書き込み、所定の設定期間経過後、前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを保持する当該データ記憶領域の全てに前記無効値を持つ有効フラグを書き込む、
ことを特徴とするデータ記憶装置。
【請求項１６】
請求項１５に記載のデータ記憶装置であって、前記メモリ制御部は、前記設定期間内に、前記複数のエントリデータのいずれかを更新したとき、当該更新されたエントリデータを保持する当該データ記憶領域に前記エントリデータの無効化が予定されていないことを示す値を持つ削除フラグを書き込むことを特徴とするデータ記憶装置。
【請求項１７】
請求項１から１４のうちのいずれか１項に記載のデータ記憶装置であって、
前記各データ記憶領域は、
当該各データ記憶領域に保持されているエントリデータの無効化が予定されていることを示す値と当該各データ記憶領域に保持されているエントリデータの無効化が予定されていないことを示す値とのうちのいずれか一方の値を持つ削除フラグを格納する削除フラグ領域をさらに有し、
前記メモリ制御部は、前記アクセス要求として削除フラグ付与指示が受信されたときに前記複数のデータ記憶領域のいずれかに前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを書き込み、所定の設定期間経過後、前記エントリデータの無効化が予定されていることを示す値を持つ削除フラグを保持する当該データ記憶領域の全てに前記無効値を持つ有効フラグを書き込む、ことを特徴とするデータ記憶装置。
【請求項１８】
請求項１から１７のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ管理アルゴリズムは、最も長い間参照されていない実体データを含むエントリデータの優先順位を最も低くするアルゴリズムであることを特徴とするデータ記憶装置。
【請求項１９】
請求項１から１８のうちのいずれか１項に記載のデータ記憶装置であって、前記メモリ制御部は、前記複数のデータ記憶領域に保持されている前記複数のエントリデータのうち、直近に参照された実体データを含む参照データを保持するデータ記憶領域に前記無効値を持つ有効フラグを書き込み、前記シフト操作の実行後、最上位の前記データ記憶領域に前記参照データを書き込むことを特徴とするデータ記憶装置。
【請求項２０】
請求項１に記載のデータ記憶装置であって、前記エントリ保持回路は、ランダム・アクセス・メモリであることを特徴とするデータ記憶装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１１−２２１９００（Ｐ２０１１−２２１９００Ａ）
【公開日】平成２３年１１月４日（２０１１．１１．４）
【国際特許分類】
【出願番号】特願２０１０−９２２５５（Ｐ２０１０−９２２５５）
【出願日】平成２２年４月１３日（２０１０．４．１３）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２３年１１月４日（２０１１．１１．４）
【国際特許分類】
【出願日】平成２２年４月１３日（２０１０．４．１３）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]