(57)【要約】データアイテムの更新された値を、格納された値が個別に上書きされることができないメモリ、例えば、フラッシュメモリのセグメントに格納する技術が提供される。更新された値の各々は、ファーポインタおよびローカルポインタ用のスペースを有するアドレスに格納される。新たな値が格納されるとき、以前の値のローカルポインタが、新たな値のアドレスを指すように設定される。このタイプのノードのチェーンが確立され、さらなる更新値が格納されるとき、新たなノードで入力され、チェーンのずっと前のノードにおけるファーポインタが、一番最近の値が、以前のノードの全てにおけるローカルポインタをたどる必要なしに、発見されることができるように新たなノードを指すように設定される。
2003077133.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する工程と、
（ｃ）該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含するメモリ制御方法。
【請求項２】
前記メモリセグメントが不揮発性であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項３】
前記メモリセグメントが、全体としてのみ消去可能であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項４】
前記メモリセグメントが、フラッシュメモリの少なくとも一部を含むことを特徴とする、請求の範囲第３項記載のメモリ制御方法。
【請求項５】
前記少なくとも一つのセットが複数のセットを含み、該複数のセットの各セットのそれぞれのファーポインタが格納されるアドレス部は、該複数のセットの各セットより前の該複数のセットのうちの該セットまたは他のセットの各々へのファーポインタが格納される該アドレスまたは各アドレスの前に割り当てられたアドレス部であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項６】
前記工程（ｂ）が、各（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目の組の各々へのポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレス部に格納し、ここで、Ａは、所定の１より大きい整数の定数であり、Ｂが０より大きい整数のパラメータであり、Ｃは、０以上の整数のパラメータであり、Ｋは、０以上の所定の整数の定数であることを特徴とする、請求の範囲第５項記載のメモリ制御方法。
【請求項７】
１≦Ｂ≦ＡおよびＫ＝０であることを特徴とする、請求の範囲第６項記載のメモリ制御方法。
【請求項８】
Ａ＝４であることを特徴とする、請求の範囲第７項記載のメモリ制御方法。
【請求項９】
各セットが単一の値を含むことを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１０】
各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１１】
前記データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納することを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１２】
前記アドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１３】
前記アドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１４】
前記メモリセグメントが一杯である場合に、前記最終値が、他のメモリセグメントにコピーされ、その後、該メモリセグメントが消去されることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１５】
前記現在値、該現在値のアドレス、および前記少なくとも一つのデータアイテムのうちのセットの数をキャッシュメモリに格納することを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１６】
少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する工程と、
（ｃ）該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含するメモリ制御方法であって、前記第１のセットに割り当てられたアドレスで開始し、
（ｉ）ファーまたはローカルポインタのアドレスを調べる工程と、
（ｉｉ）ファーポインタが存在する場合、ファーポインタが指すアドレスについて、該工程（ｉ）を行う工程と、
（ｉｉｉ）ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて、工程（ｉ）を行う工程と、
（ｖｉ）ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す工程と
を包含するメモリ制御方法。
【請求項１７】
前記工程（ｉ）が、前記アドレスにおいて少なくとも一つのポインタ位置を調べる工程と、該少なくとも一つの位置が非リセット状態であることを示す工程とを含むことを特徴とする、請求の範囲第１６項記載のメモリ制御方法。
【請求項１８】
前記工程（ｖｉ）が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスをキャッシュメモリに格納する工程を含むことを特徴とする、請求の範囲第１６項記載のメモリ制御方法。
【請求項１９】
少なくとも一つのデータアイテムの時間的に連続する値を格納する記憶装置であって、格納された値が個別に上書きされることができないタイプのメモリセグメントと、該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられた該連続する値のセットをそれぞれのアドレス部に格納する手段とを含み、該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する手段と、該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する手段とを含むことを特徴とする記憶装置。
【請求項２０】
前記メモリセグメントが不揮発性であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２１】
前記メモリセグメントが全体としてのみ消去可能であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２２】
前記メモリセグメントがフラッシュメモリの少なくとも一部を含むことを特徴とする、請求の範囲第２１項記載の記憶装置。
【請求項２３】
前記少なくとも一つのセットが複数のセットを含み、該複数のセットのそれぞれのセットのファーポインタが格納されるアドレス部は、該複数のセットのうちの該セットまたは他のセットの各々へのファーポインタが格納される該アドレスまたは各アドレスの前に割り当てられたアドレス部であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２４】
前記ファーポインタ格納手段が、ポインタを、各〔ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ〕番目のセットに、〔ＡＢ．Ｃ＋（Ａ−Ｂ）＋Ｋ〕番目のセットに割り当てられたアドレス部で格納する手段を含み、ここで、Ａは１より大きい所定の整数の定数であり、Ｂは、０より大きい整数のパラメータであり、Ｃは、０以上の整数のパラメータであり、Ｋは０以上の所定の整数の定数であることを特徴とする、請求の範囲第２３項記載の記憶装置。
【請求項２５】
１≦Ｂ≦ＡおよびＫ＝０であることを特徴とする、請求の範囲第２４項記載の記憶装置。
【請求項２６】
Ａ＝４であることを特徴とする、請求の範囲第２５項記載の記憶装置。
【請求項２７】
各セットが単一の値を含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２８】
各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２９】
前記データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納する手段を含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３０】
前記アドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３１】
前記アドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３２】
前記メモリセグメントが一杯である場合に、前記最終値または各最終値を、他のメモリセグメントにコピーする手段と、該メモリセグメントを消去する手段とを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３３】
キャッシュメモリと、前記現在値、該現在値のアドレス、および前記少なくとも一つのデータアイテムのうちのセットの数を該キャッシュメモリに格納する手段とを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３４】
前記第１のセットから開始して、ファーまたはローカルポインタのアドレスを調べ、ファーポインタが存在する場合、ファーポインタが指すアドレスについて調べ、ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて調べ、ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す読み取り手段を含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３５】
前記ファーまたはローカルポインタの存在を調べる手段が、前記アドレス部において少なくとも一つのポインタ位置を調べる手段と、該少なくとも一つの位置が非リセット状態であることを示す手段とを含むことを特徴とする、請求の範囲第３４項記載の記憶装置。
【請求項３６】
前記最新値を戻す手段が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスを、キャッシュメモリに格納する手段を含むことを特徴とする、請求の範囲第３４項記載の記憶装置。
【請求項３７】
コンピュータを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３８】
請求の範囲第１項記載のメモリ制御方法の各処理手順をコンピュータに実行させる制御プログラム。
【請求項３９】
請求の範囲第３８項記載の制御プログラムが記録された可読記録媒体。
【発明の詳細な説明】
技術分野
本発明は、時間的に連続する値を格納して、最新の値を読み出し可能とするメモリ制御方法、これを用いた記憶装置、これに用いる制御プログラムおよび、これを記録した可読記録媒体に関する。
背景技術
この種の技術は、例えば半導体チップ内に埋め込まれたシステムなどにおいて用いることができる。その記憶装置の適切な用途例としては、Ｊａｖａ  Ｃａｒｄ（登録商標）のようなスマートカード、スマートキーおよびスマートディスクのようなデジタルアクティブ記憶装置またはセキュリティデバイス、移動電話用のＳＩＭ（Ｓｕｂｓｃｒｉｂｅｒ  Ｉｄｅｎｔｉｔｙ  Ｍｏｄｕｌｅ）およびＵＳＩＭ（Ｕｎｉｖｅｒｓａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｉｄｅｎｔｉｔｙ  Ｍｏｄｕｌｅ）の他、データ記録デバイス、ユーザによる選択事項を記録し、設定内容を格納し、使用状況を記録する小型記録デバイス、車両内のコンピュータシステム、セットトップボックスおよびインターネットルーターなどが含まれる。
本明細書中で用いられる用語のＰＤＩ「パーシステントデータアイテン（パーシステントデータアイテム）または永続データアイテム」は、時間とともに、特にアプリケーションプログラムによって更新されるときに変化する変数値に関連付けられており、このような更新と更新間、特に、アプリケーションが実行されていないとき、意図的に電力が供給されていないとき、即ちアプリケーションがオフに切り換えられているとき、または、偶然、例えば停電のために電力が供給されていないときに、その記録状態を維持する必要があるデータアイテムとして定義される。
コンピュータプログラムは、変数の値を読み取り、これを更新することによって動作する。ＲＡＭにおける変数値に対しては、必要な頻度で値を書き変え、データの読み出しおよび書き込みが速いので、このことは困難ではない。プログラムが実行されていないとき、その記録状態は、より持続的なメモリに格納されている必要がある。
スマートカードのような小規模のコンピュータプラットフォーム上においては、ＲＡＭが小さく、永続メモリは、ＥＥＰＲＯＭまたはフラッシュメモリの形をとることが多い。この永続メモリは、ビット値が変化した後に、セグメント全体が消去されるまで再度変更されないという性質を有している。ＥＥＰＲＯＭにおいて、セグメントサイズは、１バイト（８ビット）の大きさであり、永続メモリは、ほとんど、非常に遅いＲＡＭとして処理することができる。フラッシュメモリにおいて、セグメントは、シリコン面積を有効に使うため、概してメモリ容量が大きく（例えば６４ＫＢ）、消去動作も遅い。また、永続メモリは、最終的には、ある程度の回数（例えば高品質フラッシュでは、１００，０００回）の消去サイクルが行われ、寿命がつきる。フラッシュメモリの利点は、所定のチップ面積に対してより多くのメモリが実装され得るので格納スペースがより大きくなることであるが、ＥＥＰＲＯＭよりも効率的に用いることが困難である。
各種処理が実行されるたびに日付および時間の記録（おそらく、カード読み取り端子から入手される）を取るスマートカードの用途を考慮して、実行と実行との間の間隔を調べる。これは、例えばキャッシュカードの日常的な引き出し金額の制限を高めるなどのセキュリティー機能のために用いられ得る。各種処理が実行されるたび、古い実行日付を読み取り、それからの間隔を調べて、新たな実行日付を格納する。これによって、その実行日付がＰＤＩ（永続データアイテム）である。この実行日付が変わるたびに同じ位置に格納される場合、物理的なメモリ制限に起因して、まず、６４Ｋブロック全体が消去される必要がある。これには、長い時間がかかり、フラッシュメモリが急速に消耗して短寿命となる。
この代わりに、新たな実行日付が書き込まれるたびに、メモリの新たな位置に書き込まれる必要がある。このプログラムでは、他のプログラムとフラッシュメモリを共有する必要があることが想定されるので、この一つのアプリケーションのためにのみ、フラッシュメモリの大きなブロックを予め割り当てることは、効率的ではない。すなわち、システムには多くのＰＤＩがあり、各種処理が実行されているアプリケーションに依存して、ＰＤＩは異なる速度で更新され得る。
Ｊｏｎａｔｈａｎ  Ｔ  Ｍｏｏｒｅ、Ｍｉｃｈａｅｌ  Ｈｉｃｋｓ、およびＳｃｏｔｔ  Ｎｅｔｔｌｅｓによる「Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ  Ｐｅｒｓｉｓｔｅｎｃｅ  Ｕｓｉｎｇ  Ｆｌａｓｈ  Ｍｅｍｏｒｙ」（Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＭＳ−ＣＩＳ−９７−３、ＣＩＳ  Ｄｅｐｔ．Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｐｅｎｎｓｙｌｖａｎｉａ、１９９７年）に開示されている公知の構成では、ＰＤＩ（永続データアイテム）を、（永続データアイテム）ログとして管理する構成である。ＰＤＩが更新されるたびに、ログエントリ（更新記録）は、ＰＤＩのアイデンティティおよび新たな値とともに書き込まれる。現在の値を見つけるため、ログがスキャンされて、一番最近の値が見つけられる必要がある。ログエントリ（更新記録）のブロックが一杯である場合、各ＰＤＩの一番最近の値のみが、新たなブロックにコピーされ、古いブロックは消去される。これは、「ガーベージコレクション」（不要となったデータ記憶領域を回収してそれをまとめて利用できるようにすること）と呼ばれる。この解決方法は、フラッシュメモリスペースの点では効率的であるが、検索時間では値の読み取りが遅い。いくつかの値が、ＲＡＭにコピーされることによってキャッチ（検索）され得るが、このことによって、貴重なＲＡＭスペースが使い果たされ、キャッシュを検索する余分な時間も必要とされる。書き込みは、ログ（更新記録）の添付のみを必要とするので速い。
また、他の公知の構成としては、添付の図１に示すように、各ＰＤＩに対する値のリンクされたチェーンを構築する。チェーンの第１の要素は、既知のアドレスにある。チェーンの各要素は、実行日付の記録についての値を格納し、チェーンの次のアイテムへのポインタのためのスペースを有する。最後のチェーンの要素は、消去されたメモリパターン（このモデルにおいて１６進法でＦＦＦＦ、あるいは、相補的なモデルにおいて００００）と等しいポインタ値を有する。現在の更新日付を読み取るため、読み取りは、チェーンの始まりで開始され、値ＦＦＦＦに達するまで各ポインタを順次たどる。新たな更新日付を加えるため、新たな値および空のポインタで、新たなチェーンの要素が作成される。その後、アドレスが、最後であった要素のポインタ部分の上に格納される。ガーベージコレクションが行われる場合には、チェーンの最後の値が新たなブロックにコピーされ、新たなチェーン（鎖）の始まりとして用いられる。
例：値「ｄａｔｅ２」（および以前の値「ｄａｔｅ１」および「ｄａｔｅ０」）を表すチェーン
アドレス  コンテンツ〔値、ポインタ〕
０１２０  〔ｄａｔｅ０，０２３６〕  ／／初期値＝ｄａｔｅ０
・・
０２３６  〔ｄａｔｅ１，０２４０〕  ／／１回目の更新後の値＝ｄａｔｅ１
・・
０２４０  〔ｄａｔｅ２，ＦＦＦＦ〕  ／／２回目の更新後の値＝ｄａｔｅ２
ここで、新たな値「ｄａｔｅ３」が加えられ、アドレス０３３２に、空いているメモリがあるとする。
０１２０  〔ｄａｔｅ０，０２３６〕
・・
０２３６  〔ｄａｔｅ１，０２４０〕
・・
０２４０  〔ｄａｔｅ２，０３３２〕
・・
０３３２  〔ｄａｔｅ３，ＦＦＦＦ〕
これを達成するプログラムコードは、簡略的であり、コンパクトである（ここでは、アルゴリズムを説明するためにＣスタイルが用いられている）。
2003077133.tif 000003
問題点は、読み取りまたは更新のたびに、チェーン全体の値を検索する必要があることである。６４Ｋメモリセグメントにおいて、チェーンが長いときには、１６，０００のエントリ（エントリ毎に２＋２バイト）まで検索する必要がある場合もあり、これを行うには時間的に遅すぎる。エントリがＮ個の場合、検索時間は、Ｎに比例し、必要なスペースは、（ｄ＋２）＊Ｎバイトである。ただし、ｄは、一つの値を格納するバイト数であり、ポインタは２バイトを必要とする。しかし、解決方法は、コンパクトである。２バイトの値は、各々、格納に４バイトしか用いず、データが更新されなくなる場合、割り当てられるが用いられないことによって無駄になるのは、チェーンの最後のせいぜい２バイトである。
さらに、他の公知の構成として、Ｍｅｉ−ｌｉｎｇ  Ｃｈｉａｎｇ、Ｐａｕｌ  Ｃ  Ｈ  Ｌｅｅ、およびＲｕｅｉ−Ｃｈｕａｎ  Ｃｈａｎｇの「Ｄａｔａ  Ｍａｎａｇｅｍｅｎｔ  ｉｎ  ａ  Ｆｌａｓｈ  Ｍｅｍｏｒｙ  Ｂａｓｅｄ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｅｒ」（Ｎａｔｉｏｎａｌ  Ｃｈｉａｏ−Ｔｕｎｇ  Ｕｎｉｖｅｒｓｉｔｙ、Ｈｓｉｎｃｈｕ，Ｔａｉｗａｎ，Ｒ．Ｏ．Ｃ．、およびＡｃａｄｅｍｉａ  Ｓｉｎｉｃａ、Ｎａｎｋａｎｇ，Ｔａｉｗａｎ，Ｒ．Ｏ．Ｃ．）に開示されている。この公知の構成において、フラッシュメモリは、システムによって管理されるサブブロックに分割されている。ブロックは、全体として、再度書き込まれる必要がある（すなわち、新たな値がフラッシュメモリの新たな領域に書き込まれ、古いブロックは最新のものではないことが何らかの方法でマーキングされている）。これは、ブロックが大きすぎる場合は、（例えば、３２バイトのブロックを用いて、２バイトのカウンタを格納することによって）メモリが無駄になることを意味する。ブロックが小さすぎる場合、ブロック自体が多すぎ、管理オーバーヘッドが、ＣＰＵ検索時間またはＲＡＭスペース、あるいはその両方を無駄にする。
さらに、他の公知の構成として、Ｂｒｉａｎ  Ｌｅｗｉｓ、Ｂｅｒｎｄ  Ｍａｔｈｉｓｋｅ、Ｎｅａｌ  Ｇａｆｔｅｒの「Ａｒｃｈｉｔｅｃｔｕｒｅ  ｏｆ  ＰＥＶＭ：  ａ  Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ  Ｏｒｔｈｏｇｏｎａｌｌｙ  Ｐｅｒｓｉｓｔｅｎｔ  Ｊａｖａ（登録商標）」（Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．、９０１  Ｓａｎ  Ａｎｔｏｎｉｏ  Ｒｏａｄ，Ｐａｌｏ  Ａｌｔｏ，ＣＡ９４３０３−４９００、ＵＳＡ）に開示されている。この構成において、フラッシュメモリのコンテンツは、コピーオンライトで、仮想メモリシステムとして管理される。更新されるフラッシュメモリは、ＲＡＭにコピーされ、変更される。入来するブロック用のスペースがない場合、古いブロックが、フラッシュに戻って書き込まれる。これによって、ブロックの中の一つのバイトが変化したことに起因して、ブロック全体が再度書き込まれることにつながり得る。このシステムは、多くのメモリコピーがＲＡＭの内外のブロックに求められているので、アクセスのたびに長い時間のオーバーヘッドが追加される。
Ｐｉｅｔｅｒ  Ｈ  Ｈａｒｔｅｌ、Ｍｉｃｈａｅｌ  Ｊ  Ｂｕｔｌｅｒ、Ｅｄｕａｒｄ  ｄｅ  Ｊｏｎｇ、およびＭａｒｋ  Ｌｏｎｇｌｅｙの「Ｔｒａｎｓａｃｔｅｄ  Ｍｅｍｏｒｙ  ｆｏｒ  Ｓｍａｒｔ  Ｃａｒｄｓ」（ｆｐｈｈ，ｍｊｂｇ＠ｅｃｓ．ｓｏｔｏｎ．ａｃ．ｕｋおよびＥｄｕａｒｄ．ｄｅＪｏｎｇ＠Ｓｕｎ．ＣＯＭ、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＤＳＳＥ−ＴＲ−２０００−９、２０００年８月１６日、Ｄｅｃｌａｒａｔｉｖｅ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ｓｏｆｔｗａｒｅ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｇｒｏｕｐ、Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｅｌｅｃｔｒｏｎｉｃｓ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｏｕｔｈａｍｐｔｏｎ、Ｈｉｇｈｆｉｅｌｄ，Ｓｏｕｔｈａｍｐｔｏｎ  ＳＯ１７  １ＢＪ，Ｕｎｉｔｅｄ  Ｋｉｎｇｄｏｍ）では、スマートカードメモリにおいて、ブロックサイズが小さいこと（例えば、３２バイト）が想定され、ここではトランザクションオブジェクトをどのように構築するかが示されている。これらのオブジェクトにおいて、任意の多くのデータアイテムの更新は、１回として（自動的に）行われ、トランザクションが、何らかの理由で完了する前に中止されると、もとの記録状態に戻すことができる。
発明の開示
本発明は、上記従来の問題を解決するもので、ＰＤＩの更新を速く行うことができて、前もって割り当てられたＰＤＩ格納用スペースを必要とせず、更新を順次進めて、利用可能なスペースを効率的に一杯にすることができるメモリ制御方法、これを用いた記憶装置、これに用いる制御プログラムおよび、これを記録した可読記録媒体を提供することを目的とする。
本発明の第１の局面によると、添付の請求項１に記載の方法が提供される。本発明の第２の局面によると、添付の請求項１９に記載の装置が提供される。本発明の第３の局面によると、添付の請求項３８に記載の制御プログラムが提供される。本発明の第４の局面によると、添付の請求項３９に記載の可読記録媒体が提供される。本発明の好適な実施形態は、他の添付の請求項に記載されている。
即ち、本発明のメモリ制御方法は、少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する工程と、
（ｃ）該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程とを包含するものであり、そのことにより上記目的が達成される。
また、好ましくは、本発明のメモリ制御方法におけるメモリセグメントが不揮発性であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法におけるメモリセグメントが、全体としてのみ消去可能であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法におけるメモリセグメントが、フラッシュメモリの少なくとも一部を含むことを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法において、少なくとも一つのセットが複数のセットを含み、該複数のセットの各セットのそれぞれのファーポインタが格納されるアドレス部は、該複数のセットの各セットより前の該複数のセットのうちの該セットまたは他のセットの各々へのファーポインタが格納される該アドレスまたは各アドレスの前に割り当てられたアドレス部であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法における工程（ｂ）が、各（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目の組の各々へのポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレス部に格納し、ここで、Ａは、所定の１より大きい整数の定数であり、Ｂが０より大きい整数のパラメータであり、Ｃは、０以上の整数のパラメータであり、Ｋは、０以上の所定の整数の定数であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法において、１≦Ｂ≦ＡおよびＫ＝０であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法において、Ａ＝４であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法における各セットが単一の値を含むことを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法における各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法において、データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納することを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法におけるアドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法におけるアドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法において、メモリセグメントが一杯である場合に、前記最終値が、他のメモリセグメントにコピーされ、その後、該メモリセグメントが消去されることを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法において、現在値、該現在値のアドレス、および前記少なくとも一つのデータアイテムのうちのセットの数をキャッシュメモリに格納することを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法は、少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する工程と、
（ｃ）該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含するメモリ制御方法であって、前記第１のセットに割り当てられたアドレスで開始し、
（ｉ）ファーまたはローカルポインタのアドレスを調べる工程と、
（ｉｉ）ファーポインタが存在する場合、ファーポインタが指すアドレスについて、該工程（ｉ）を行う工程と、
（ｉｉｉ）ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて、工程（ｉ）を行う工程と、
（ｖｉ）ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す工程とを包含するものであり、そのことにより上記目的が達成される。
さらに、好ましくは、本発明のメモリ制御方法における工程（ｉ）が、前記アドレスにおいて少なくとも一つのポインタ位置を調べる工程と、該少なくとも一つの位置が非リセット状態であることを示す工程とを含むことを特徴とする。
さらに、好ましくは、本発明のメモリ制御方法における工程（ｖｉ）が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスをキャッシュメモリに格納する工程を含むことを特徴とする。
次に、本発明の記憶装置は、少なくとも一つのデータアイテムの時間的に連続する値を格納する記憶装置であって、格納された値が個別に上書きされることができないタイプのメモリセグメントと、該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられた該連続する値のセットをそれぞれのアドレス部に格納する手段とを含み、該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する手段と、該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する手段とを含むことを特徴とするものであり、そのことにより上記目的が達成される。
また、好ましくは、本発明の記憶装置におけるメモリセグメントが不揮発性であることを特徴とする。
さらに、好ましくは、本発明の記憶装置におけるメモリセグメントが全体としてのみ消去可能であることを特徴とする。
さらに、好ましくは、本発明の記憶装置におけるメモリセグメントがフラッシュメモリの少なくとも一部を含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置において、少なくとも一つのセットが複数のセットを含み、該複数のセットのそれぞれのセットのファーポインタが格納されるアドレス部は、該複数のセットのうちの該セットまたは他のセットの各々へのファーポインタが格納される該アドレスまたは各アドレスの前に割り当てられたアドレス部であることを特徴とする。
さらに、好ましくは、本発明の記憶装置におけるファーポインタ格納手段が、ポインタを、各〔ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ〕番目のセットに、〔ＡＢ．Ｃ＋（Ａ−Ｂ）＋Ｋ〕番目のセットに割り当てられたアドレス部で格納する手段を含み、ここで、Ａは１より大きい所定の整数の定数であり、Ｂは、０より大きい整数のパラメータであり、Ｃは、０以上の整数のパラメータであり、Ｋは０以上の所定の整数の定数であることを特徴とする。
さらに、好ましくは、本発明の記憶装置において、１≦Ｂ≦ＡおよびＫ＝０であることを特徴とする。
さらに、好ましくは、本発明の記憶装置において、Ａ＝４であることを特徴とする。
さらに、好ましくは、本発明の記憶装置における各セットが単一の値を含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置における各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする。
さらに、好ましくは、本発明の記憶装置において、データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納する手段を含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置におけるアドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置におけるアドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置におけるメモリセグメントが一杯である場合に、前記最終値または各最終値を、他のメモリセグメントにコピーする手段と、該メモリセグメントを消去する手段とを含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置において、キャッシュメモリと、前記現在値、該現在値のアドレス、および前記少なくとも一つのデータアイテムのうちのセットの数を該キャッシュメモリに格納する手段とを含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置において、第１のセットから開始して、ファーまたはローカルポインタのアドレスを調べ、ファーポインタが存在する場合、ファーポインタが指すアドレスについて調べ、ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて調べ、ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す読み取り手段を含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置において、ファーまたはローカルポインタの存在を調べる手段が、前記アドレス部において少なくとも一つのポインタ位置を調べる手段と、該少なくとも一つの位置が非リセット状態であることを示す手段とを含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置において、最新値を戻す手段が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスを、キャッシュメモリに格納する手段を含むことを特徴とする。
さらに、好ましくは、本発明の記憶装置はコンピュータを含むことを特徴とする。
次に、本発明の制御プログラムは、請求項１に記載のメモリ制御方法の各処理手順をコンピュータに実行させるものであり、そのことにより上記目的が達成される。
また、本発明の可読記録媒体は、請求項３８に記載の制御プログラムが記録されたものであり、そのことにより上記目的が達成される。
上記構成により、本発明を、添付の図面を参照しながら、例示のためにさらに説明する。
本発明の典型的な一例において、単一結合チェーンを用いてＰＤＩ（データアイテム）を更新する代わりに、非環状グラフ構造体が用いられる。各要素は、一つではなく、ＬおよびＦ（ローカルおよびファー）と呼ばれる二つのポインタ、ならびにこれに関連付けられたデータ値を有する。ローカルポインタは線形のチェーンをたどるが、ファーポインタは、間にある多くの要素を越えることができる。ローカルポインタは、チェーン方法として初期化されるが、ファーポインタは、ショートカットに値するまで充分にチェーンが長くなるまで、「ＦＦＦＦ」に残される。グラフの検索において、「ＦＦＦＦ」ではない場合にはファーポインタを用い、そうでない場合には、ローカルポインタをたどる（その後、ローカルポインタも「ＦＦＦＦ」になったときに止まる）ことがここでのルールである。選択され得る可能なグラフ形状は多く、選択を効率的にする性質は以下の通りである。
１．グラフは、セグメント全体が単一のＰＤＩの更新で一杯である場合でも、検索時間を短くする必要がある。
２．現在値の検索は、一時的な値を保持する余分なＲＡＭを少量のみ必要とすべきである。
３．更新時間は、検索時間とほぼ同じであり、一時的な値を保持するために、余分なＲＡＭを少量しか用いない。
４．メモリ容量を節約するため、ノードとして添付されたＬおよびＦサブグラフノードのいずれが追加されているかについての情報を安価に計算することが可能である。好ましくは、この情報をグラフに格納する必要はない。
更新のグラフの「サイズ」は、グラフが表す値が更新された回数として定義される。したがって、新たなＰＤＩはサイズ０であり、初期値が設定されたときはサイズ１であり、最初に更新された後は、サイズ２であり、以下同様である。グラフは、常に、一度に一つのノードを追加することによって成長するので、所与のサイズのグラフの「形」（すなわち、グラフのＬおよびＦポインタのトポロジカルな配置）は、格納する値とは関係なく、予想され得る。
例示のため、形は、ＬおよびＦポインタのみを有し、データ値が依然入れられていないサイズＮｍａｘ（例えば、セグメント全体のファイリング）まで成長したグラフから考えられる。一番最近追加された値を見つける検索時間を低減するため、値は、深さの優先順、かつ、Ｆの前にＬの順で追加される。サブグラフが「一杯」であると考慮され、新たな値が新たなサブグラフに位置付けられ得るとき、効率的に検出することが可能である。これを行うためには、サブグラフが位置付けられ得る（検索時間において）利用可能なノードの記録をとることが必要である。
2003077133.tif 000004
ガーベージコレクションが行われるとき、一番最近の値が見つけられ、新たなセグメントにコピーされる。古いセグメントは消去される。
ＰＤＩグラフの始まりを見つけるため、ポインタのアレイが、各フラッシュメモリブロックまたはセグメントの始まりで保存される。アレイは、そのブロックに格納されているＰＤＩのアイデンティティによってインデックスが付けられ、その位置のコンテンツが必要なポインタである。テーブルは、ガーベージコレクションの結果としてコピーされる場合に、更新される必要がある。
このような構成は、以下のような利点を有する。
ＰＤＩの更新が速い。
ＰＤＩは、前もって割り当てられたスペースを必要とせず、更新が進んで、利用可能なスペースを効率的に一杯にすることができる。大幅に異なる成長速度を有する多くのＰＤＩが一つのセグメント内に容易に共存し得る。
総合的な格納要件を低減するため、データ自体がコンパクトになる。
アルゴリズムが実際に実行されているときに、アルゴリズムに必要な数バイトのローカル記憶装置および、セグメント内の次の利用可能な、空いているメモリへのポインタ以外にＲＡＭが必要とされない。
利用可能な場合、いくつかのＲＡＭが用いられて、いくつかのポインタおよび値をキャッシュして、アクセスおよび更新時間の速度を上げることができる。
セグメントが一杯になった場合に、最後の更新記録以外の更新記録を除去するガーベージコレクションが簡略になる。
発明を実施するための最良の形態
以下、本発明のメモリ制御方法の実施形態を、以下の記憶装置に適応させた場合について図面を参照しながら説明する。
図１は、本発明の記憶装置における多数の更新後のＰＤＩ構造体の最初の部分の図である。即ち、図１に、本発明の値が何回も更新されたある特定のＰＤＩ用の構造の初めの部分のある特定の実施例を示している。各々の丸○は、ＰＤＩ構造体内のノードを表し、ＰＤＩ（永続データアイテム）を更新する順序に数字が付けられている。その初期値は、ノード０に格納されており、ノード１〜１９は、最初の１９回の各更新を示している。
図１において、ＰＤＩ更新値の入力によってノードにＰＤＩ更新値が格納作成されるたび、直前のノードも更新されて、新たなノードのアドレスへのローカルポインタを含む。つまり、例えば６回目のＰＤＩの更新が行われた後、ノード０〜６はそれぞれ、入力順のＰＤＩ値を含み、ノード０〜５の各々は、次のノードへのローカルポインタを含む。７回目のＰＤＩ更新値が入力されるとき、その値は、ノード７に入力される。図１では、ノード６からノード７へのローカルポインタが示されているが、これは、ＰＤＩの現在値を見つけるための続いての検索がノード４〜６のローカルポインタを用いなくてよいように、ファーポインタがノード３で入力されるので、実際には必要ではなく、省略され得る。
その代わりに、ＰＤＩ更新値の検索において、ノード０からノード３までローカルポインタが進み、その後、ノード７までファーポインタがジャンプして進むので、ノード３でファーポインタが入力された後は、中間値のノード４〜６は調べられることがない。したがって、ファーポインタが構造のノードにおいて入力されたときはいつでも、例えばノード７の前のノードは、ローカルポインタを含む必要はなく、この前のノードにおいてローカルポインタにスペースを割り当てないことによって、メモリスペースが節約され得る。
図２には、複数のセグメント２０を含むフラッシュメモリ内のデータレイアウトを示している。このようなフラッシュセグメント２０の各々は、全体として消去可能であり、ここでは各セグメントのうちの一つのデータレイアウトが示されている。図２において、このセグメントは、セグメント２０に格納される各ＰＤＩ用のエントリを含むページ識別子およびステータス２２ならびに、このセグメントのＩＤテーブル２３に予めスペースが割り当てられた固定セグメントまたは「ページ」ヘッダ２１（固定ページヘッダ）を含む。各エントリは、ＰＤＩに関連付けられた識別子によってアドレス可能であり、ＰＤＩの第１のノードを含むアドレスへのポインタを含んでいる。
セグメント２０の残り領域は、ＰＤＩの到着（入力）毎の更新された値として、連続的に充填されるページデータ領域２４を含んでいる。第１の値が到着する場合、データ領域２４内の次の利用可能なアドレスにおいて格納され、アドレスは、テーブル２３において入力される。これに続いての更新は、次に利用可能なアドレスにおいて格納され、以前のノードは、ローカルまたはファーポインタを用いて適切に更新される。
図１に、概念的なノード数によって、ファーポインタの宛先を示しているが、実際には、データ領域２４内の実際のメモリアドレスが、ローカルポインタまたはファーポインタとして入力される。データ領域２４への充填は、図２のようなＰＤＩグラフ内ノード２５によって示され、更新内容の格納に利用可能なフリースペース２６で示される。
図３に、フラッシュメモリ内の典型的なＰＤＩノード構造を示している。テーブル２３における第１の値のアドレスは、第１のＰＤＩグラフ内ノード２７に示されている。第１のＰＤＩグラフ内ノード２７は、データ値２８、ファーポインタ２９およびローカルポインタ３０に割り当てられるメモリスペースを有する。この例においては、データ値２８が「ＡＢＣＤ」（１６進法）で、ファーポインタ２９が入力されておらず、入力は、消去された状態「ＦＦＦＦ」（１６進法）であることが想定される。しかし、これに続く値はノード３１に入力され、ローカルポインタ３０は、ノード３１のようなアドレスに設定される。ノード３１は、例えばデータ値ＡＥ９８（１６進法）を含むが、ローカルポインタおよびファーポインタは「ＦＦＦＦ」で、消去された状態に維持されている。
図４（ａ）〜図４（ｃ）に、本発明におけるガーベージコレクション動作の三つのステップを示している。図４（ａ）に示すように、セグメントまたはページ３２は、更新されたＰＤＩ更新値で埋められるが、次のセグメント３３は空であって利用可能である。ＰＤＩ更新値が更新され続け、セグメント３２が後で用いられるために全て消去されるためには、図４（ｂ）に示すように、ＰＤＩ更新値の最新値が、セグメント３２のデータ領域で検索されて見つけられ、それがセグメント３３にコピーされる。セグメント３３の固定ページヘッダは、ページ識別子およびステータス、ならびにＰＤＩ用のポインタのテーブルを、ページ３３の第１のエントリに入力することによって形成される。続く更新された値が、上述したように、ページ３３に格納され、図５の（ｃ）に示すように、ページ３２は消去され得、続く使用において利用可能になる。
図５には、模式的に、本発明におけるＰＤＩ更新値の格納およびその読み取りを実現し得る典型的な小型コンピュータの構成例を示している。
この小型コンピュータは記憶装置を構成しており、外部との入力／出力（Ｉ／Ｏ）インターフェース３６と、小型ランダムアクセスメモリ（ＲＡＭ）３７の形態の動作メモリと、制御部としてのＣＰＵ３５（中央処理装置）と、数ページのフラッシュメモリ３８の形態の不揮発性メモリと、これらに電力供給する内部または外部電源３９とを含む。
この記憶装置が例えばスマートカードである場合には、電源３９は、外部例えばカード読み取り器にあり、電力は、記憶装置に対して断続的にのみ供給される。この記憶装置が、例えば車両に取り付けられている場合には、電源３９は、車両電源を含み、例えば車両点火システムがオンに切り換えられた場合にのみ利用可能とすることができる。遠隔インターネットルーターのように、記憶装置が連続的に用いられることを意図される場合、電源３９は、電力を連続的に供給することを意図されており、記憶装置は、停電の場合に、その記録状態を維持することができるようになっている。これによって、記憶装置は、電力が回復することができる場合に、比較的容易に再度作動させることが可能となる。
本実施形態を示すある特定例において、各ＰＤＩは、一意的な１６ビット識別子（ＩＤ）が割り当てられ、６５５３６ＰＤＩまでの理論的なアドレススペースが与えられる。最も簡略的な実施形態において、一つのフラッシュセグメント２０のみがＰＤＩを格納するために用いられ、これは、処理され得るＰＤＩの数を制限する。ＩＤは、連続するように割り当てられる。最大のＭ  ＰＤＩが処理される場合、Ｍポインタのアレイ（ＩＤによってインデックスが付けられる）は、ブロックの初めに、テーブル２３に割り当てられ、この後、アレイのｊ番目のコンテンツはＩＤがｊと等しいＰＤＩ用データを含むように、ＰＤＩチェーンが割り当てられる。ｊ番目の要素が、「ＦＦＦＦ」（ＰＤＩが依然割り当てられていない）、または、ＰＤＩのグラフの最初のブロックにおけるオフセットを表す他の値の何れかである。
グラフ自体において、各ノードは、図１に示すように、初期値の「０」から始まり、もとの値を表す番号が付けられる。新たな要素ｎが加えられるたびに、要素ｎ−１から、かつ、可能であれば、以前の他の要素からも、結合される。以下の通りである。
形式２５６ｃ＋０の各ノードは、ノード２５６（ｃ＋１）＋０に結合される。
形式６４ｃ＋１の各ノードは、ノード６４（ｃ＋１）＋１に結合される。
形式１６ｃ＋２の各ノードは、ノード１６（ｃ＋１）＋２に結合される。
形式４ｃ＋３の各ノードは、ノード４（ｃ＋１）＋３に結合される。
数（４、１６、６４、２５６）は、６４ＫＢセグメントサイズに適切な検索時間を生成するために選択されているが、必要に応じて変更されてもよいし、四つの数のみに限定されない。この場合、倍数が２の累乗なので、非常に容易（簡略なＡＮＤおよびＣＯＭＰＡＲＥ演算）に、ノードが第２のポインタを有するか否かが判定される。各々の数は、次に大きい数を除算し、これによって、スキームがより簡略になるが、これは必要な簡略化ではない。
ノードが追加され、Ｃスタイルで与えられる以下のプログラムに従って、ポインタが更新される。
2003077133.tif 000005
2003077133.tif 000006
2003077133.tif 000007
長さ２５６、６４、１６、および４のショートカットを有する更新のリストの例が、たった一つの可能な選択肢ではない。より一般的な場合には、長さｓ（１），．．．，ｓ（Ｌ）のＬレベルのショートカットである。ただし、｛１，．．．，Ｌ−１｝の全てのｉについてｓ（ｉ）＞Ｓ（ｉ＋１）＋１およびｓ（Ｌ）＞１である。
長さｎ＞０の更新リストＵにおいて、レベル１ショートカットは、一つ以上の要素のサブリストを形成し、いくつかのｋ（１）≧０について、第１の要素から開始する。
2003077133.tif 000008
レベル１サブリストがリストの最後に達しない場合、すなわち、ｎ＞１＋ｋ（１）ｓ（１）の場合、レベル２ショートカットは、一つ以上の要素のサブリストを形成し、いくつかのｋ（２）≧０について、レベル１サブリストの終わりから一つの要素を越えたところから開始する。
2003077133.tif 000009
このパターンは、Ｌレベルまで続く。レベルｍで、ｎ＞（ｍ−１）＋ｋ（１）ｓ（１）＋ｋ（２）ｓ（２）＋．．．＋ｋ（ｍ−１）ｓ（ｍ−１）の場合、レベルｍショートカットは、
2003077133.tif 000010
2003077133.tif 000011
からなるサブリストを形成する。このサブリストの長さは、ｋ（ｍ）＋１である。
各サブリストを可能な限り長くするため、各ｋ（ｍ）は、以下のように、最大値になる必要がある。
2003077133.tif 000012
これは、
2003077133.tif 000013
の場合になる。ただし、「ｄｉｖ」は、整数除算を表す。この除算の余りは、
2003077133.tif 000014
であるが、レベルｍサブリストの最後に続く要素Ｕの数である。
ショートカットリストの長さおよび余りは、
2003077133.tif 000015
および
2003077133.tif 000016
によって制限される。レベルｍサブリストは、ｒ（ｍ）＝０の場合、ちょうどリストの最後に達する。すなわち、
2003077133.tif 000017
各ｓ（ｉ）がｓ（ｉ＋１）のちょうど倍数で、ショートカットの長さが選択される場合、この条件は、簡略化されて、
2003077133.tif 000018
または
2003077133.tif 000019
になる。
長さｎの更新リストの最後の要素を見つけるコストＣ（ｎ）は、ショートカットサブリストの長さの合計に最後のショートカットの後のリストの余りの長さを加えたものである。もっとも悪い場合には、ｎ≧Ｌであり、ショートカットがちょうど要素ｎに達するときに、コストの制限は、
2003077133.tif 000020
によって得られる。
この場合のＬおよびｓ（ｉ）の値を選択して、Ｃ（ｎ）を最適化することは、予想されたｎの値（すなわち、更新リストが成長する長さ）に依存する、工学的なトレードオフである。最大ショートカットｓ（１）の大きい値が、大きいｎのコストを決定する第１の項（（ｎ−１）ｄｉｖ  ｓ（１））を最小化する。最小ショートカットｓ（Ｌ）の小さい値は、ｎに依存しない、項ｓ（Ｌ）−１によって得られるショートカットでない工程の数を最低にする。反対に、比ｓ（１）／ｓ（Ｌ）を増大させることは、個別の比（ｓ（ｉ）ｄｉｖ  ｓ（ｉ＋１））を増大させること、または、ギャップを埋めることのいずれかによって、ショートカットレベルＬの数を増大させることによって、サブまたは商の項を増大させる。
2003077133.tif 000021
図６には、本発明によるＰＤＩ値を更新するための制御プログラムによる動作を、フローチャートの形式で表している。
図６のフローチャートにおいて、ｐは、ＰＤＩグラフにおけるノードへのポインタである。ｐのファーポインタは、ｐが指す、ＰＤＩ構造に格納されたファーフィールドである。これと同様に、ｐのローカルポインタは、ｐが指す、ＰＤＩ構造におけるローカルフィールドである。小さい変数ｐ４、ｐ１６、ｐ６４、およびｐ２５６は、ファーポインタの過去のスロットのブックマークであり、ｐＸと呼ばれ、選択は、Ｘ：４，１６，６４または２５６の値に依存する。また、フローチャートは、パラメータとして「ノード」を有するサブルーチン「ｆａｒｌｅｎ」を含む。
工程Ｓ３において、メモリの連続するブロックは、新たな値およびそのポインタを格納するために充分なスペースが割り当てられている。メモリブロックのアドレスは、可変のポインタ「ｎｅｗｐ」に格納される。
記憶装置が充分な記憶容量のＲＡＭを有する場合、現在値、最終のチェーンの位置、および最終のチェーン数が、記憶装置が動作を開始するときに、ＰＤＩの一部または全てについて、ＲＡＭに格納され得る。したがって、ＲＡＭのこの部分は、あるタイプのキャッシュメモリとして用いられる。このことは、スタートアップの間に、時間を必要とするが、その後の読み取りおよび更新のための参照は、ずっと速い。
更新値がフラッシュメモリから読み取られるときに、一番最近のポインタは、現在の値へのポインタとともにキャッシュされる。なぜなら、この値が、次に変更される可能性が最も高いからである。ファーポインタの格納は、更新をより速くする。
各ノードは、ＰＤＩの単一の値用のスペースを有し得るが、他の構成が可能であり、ノードのいずれかまたは全てが、いくつかの更新された値を格納するために利用可能なスペースを有し得る。このような構成は、図７に示されているが、ノード４０〜４２の各々が、ローカルおよびファーポインタとともに、六つの値用のスペースを有する。この場合、新たな値の各々を、新たなノードに割り当てる代わりに、値は、各ノードのスペース内に、そのノードが一杯になるまで、入力される。その後、次の値が、他のノードの第１の値のスペースに入力され、その前のノード内のローカルポインタは、新たなノードを指すように設定される。図７は、１５回更新することによって、ノード４０および４１が一杯になり、ノード４０のローカルポインタがノード４１を指し、ノード４１のローカルポインタがノード４２を指し、ノード４０、４１、および４２の他のポインタが、リセット状態にある。検索を簡略化するため、このようなノードの各々は、格納され得る、更新の回数に等しい数のビット値を有し得る。各ビット値は、更新用のスペースに対応し、ノードの検索をより簡単にするように、更新された値がスペースを占めるときに設定される。
以上により、本発明の実施形態によれば、ＰＤＩ（データアイテム）の更新された値を、格納された値が個別に上書きされることができないメモリ、例えば、フラッシュメモリのセグメントに格納する技術を提供することができる。更新された値の各々は、ファーポインタおよびローカルポインタ用のスペースを有するアドレスに格納される。新たな値が格納されるとき、以前の値のローカルポインタが、新たな値のアドレスを指すように設定される。このタイプのノードのチェーンが確立され、更なるＰＤＩ更新値が格納されるとき、新たなノードで入力され、チェーンのずっと前のノードにおけるファーポインタは、一番最近の値が、以前のノードの全てにおけるローカルポインタをたどる必要なしに、発見されることができるように新たなノードを指すように設定されるから、ＰＤＩの更新を速く行うことができる。したがって、前もって割り当てられたＰＤＩ格納用スペースを必要とせず、更新記録が順次進んで、利用可能なスペースを効率的に一杯にすることができる。また、大幅に異なる成長速度を有する多くのＰＤＩが、一つのセグメント内に容易に共存し得る。このように、総合的な格納要件を低減できるめ、データ自体をもコンパクトすることができる。
産業上の利用可能性
時間的に連続する値を格納して、最新の値を読み出し可能とするメモリ制御方法を用いた記憶装置の分野において、ＰＤＩの更新を速く行うことができる。また、前もって割り当てられたＰＤＩ格納用スペースを必要とせず、更新記録が順次進んで、利用可能なスペースを効率的に一杯にすることができる。大幅に異なる成長速度を有する多くのＰＤＩが、一つのセグメント内に容易に共存し得る。このように、総合的な格納要件を低減できるめ、データ自体もコンパクトになる。
【図面の簡単な説明】
図１は、本発明の記憶装置における多数の更新後のＰＤＩ構造体の最初の部分の図である。
図２は、本発明の記憶装置における単一フラッシュセグメント内のデータのレイアウトを示す図である。
図３は、本発明の記憶装置におけるフラッシュメモリ内のＰＤＩノードの構造を示す図である。
図４は、本発明の記憶装置におけるガーベージコレクションの一例を示す図である。
図５は、本発明の実施形態を構成する埋め込まれたシステムを示す図である。
図６は、本発明の実施形態による値の更新を示すフローチャートである。
図７は、更新を管理するハイブリッドシステムにおける値およびポインタのレイアウト構成を示す図である。
図８は、上記の公知のタイプのポインタの単一チェーンの図である。
【図１】
2003077133.tif 000022
【図２】
2003077133.tif 000023
【図３】
2003077133.tif 000024
【図４】
2003077133.tif 000025
【図５】
2003077133.tif 000026
【図６】
2003077133.tif 000027
【図７】
2003077133.tif 000028
【図８】
2003077133.tif 000029
【手続補正書】
【提出日】平成15年7月8日(2003.7.8)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（補正）少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する工程と、
（ｃ）該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含し、
該値または第１の値の新たなセットが、格納のために受け取られる場合、該アドレス部のそれぞれは割り当てられ、該ファーポインタおよび該ローカルポインタのそれぞれに示されたアドレスが該新たなセットに割り当てられた後に、該ファーポインタおよび該ローカルポインタのそれぞれが前に割り当てられたアドレス部に格納される、メモリ制御方法。
【請求項２】
前記メモリセグメントが不揮発性であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項３】
前記メモリセグメントが、全体としてのみ消去可能であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項４】
前記メモリセグメントが、フラッシュメモリの少なくとも一部を含むことを特徴とする、請求の範囲第３項記載のメモリ制御方法。
【請求項５】
前記少なくとも一つのセットが複数のセットを含み、該複数のセットの各セットのそれぞれのファーポインタが格納されるアドレス部は、該複数のセットの各セットより前の該複数のセットのうちの該セットまたは他のセットの各々へのファーポインタが格納される該アドレスまたは各アドレスの前に割り当てられたアドレス部であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項６】
削除
【請求項７】
削除
【請求項８】
削除
【請求項９】
各セットが単一の値を含むことを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１０】
各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１１】
前記データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納することを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１２】
前記アドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１３】
前記アドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１４】
前記メモリセグメントが一杯である場合に、前記最終値が、他のメモリセグメントにコピーされ、その後、該メモリセグメントが消去されることを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１５】
前記現在値、該現在値のアドレス、および前記少なくとも一つのデータアイテムのうちのセットの数をキャッシュメモリに格納することを特徴とする、請求の範囲第１項記載のメモリ制御方法。
【請求項１６】
少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する工程と、
（ｃ）該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含するメモリ制御方法であって、前記第１のセットに割り当てられたアドレスで開始し、
（ｉ）ファーまたはローカルポインタのアドレスを調べる工程と、
（ｉｉ）ファーポインタが存在する場合、ファーポインタが指すアドレスについて、該工程（ｉ）を行う工程と、
（ｉｉｉ）ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて、工程（ｉ）を行う工程と、
（ｖｉ）ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す工程と
を包含するメモリ制御方法。
【請求項１７】
前記工程（ｉ）が、前記アドレスにおいて少なくとも一つのポインタ位置を調べる工程と、該少なくとも一つの位置が非リセット状態であることを示す工程とを含むことを特徴とする、請求の範囲第１６項記載のメモリ制御方法。
【請求項１８】
前記工程（ｖｉ）が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスをキャッシュメモリに格納する工程を含むことを特徴とする、請求の範囲第１６項記載のメモリ制御方法。
【請求項１９】
（補正）少なくとも一つのデータアイテムの時間的に連続する値を格納する記憶装置であって、格納された値が個別に上書きされることができないタイプのメモリセグメントと、該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられた該連続する値のセットをそれぞれのアドレス部に格納する手段とを含み、該値のセットのうちの少なくとも一つのセットのアドレスへのファーポインタを、該少なくとも一つのセットの直前の値のセットに割り当てられたアドレスの前に割り当てられたアドレス部に格納する手段と、該少なくとも一つのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する手段とを含み、
該値または第１の値の新たなセットが、格納のために受け取られる場合、該アドレス部のそれぞれは割り当てられ、該ファーポインタおよび該ローカルポインタのそれぞれに示されたアドレスが該新たなセットに割り当てられた後に、該ファーポインタおよび該ローカルポインタのそれぞれが前に割り当てられたアドレス部に格納されることを特徴とする記憶装置。
【請求項２０】
前記メモリセグメントが不揮発性であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２１】
前記メモリセグメントが全体としてのみ消去可能であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２２】
前記メモリセグメントがフラッシュメモリの少なくとも一部を含むことを特徴とする、請求の範囲第２１項記載の記憶装置。
【請求項２３】
前記少なくとも一つのセットが複数のセットを含み、該複数のセットのそれぞれのセットのファーポインタが格納されるアドレス部は、該複数のセットのうちの該セットまたは他のセットの各々へのファーポインタが格納される該アドレスまたは各アドレスの前に割り当てられたアドレス部であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２４】
削除
【請求項２５】
削除
【請求項２６】
削除
【請求項２７】
各セットが単一の値を含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２８】
各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項２９】
前記データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納する手段を含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３０】
前記アドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３１】
前記アドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３２】
前記メモリセグメントが一杯である場合に、前記最終値または各最終値を、他のメモリセグメントにコピーする手段と、該メモリセグメントを消去する手段とを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３３】
キャッシュメモリと、前記現在値、該現在値のアドレス、および前記少なくとも一つのデータアイテムのうちのセットの数を該キャッシュメモリに格納する手段とを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３４】
前記第１のセットから開始して、ファーまたはローカルポインタのアドレスを調べ、ファーポインタが存在する場合、ファーポインタが指すアドレスについて調べ、ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて調べ、ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す読み取り手段を含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３５】
前記ファーまたはローカルポインタの存在を調べる手段が、前記アドレス部において少なくとも一つのポインタ位置を調べる手段と、該少なくとも一つの位置が非リセット状態であることを示す手段とを含むことを特徴とする、請求の範囲第３４項記載の記憶装置。
【請求項３６】
前記最新値を戻す手段が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスを、キャッシュメモリに格納する手段を含むことを特徴とする、請求の範囲第３４項記載の記憶装置。
【請求項３７】
コンピュータを含むことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項３８】
請求の範囲第１項記載のメモリ制御方法の各処理手順をコンピュータに実行させる制御プログラム。
【請求項３９】
請求の範囲第３８項記載の制御プログラムが記録された可読記録媒体。
【請求項４０】
（追加）前記ファーポインタのそれぞれは、該ファーポインタのアドレスにおけるセットの後に、前記データアイテムに対する複数のセットであって、前記ファーポインタの前記アドレスのセットが格納された後に割り当てられたアドレスを示すことを特徴とする、請求の範囲第１項記載の方法。
【請求項４１】
（追加）前記データアイテムのそれぞれについて、最後のファーポインタを除いたファーポインタのそれぞれは、別のファーポインタが格納されたアドレスを示すことを特徴とする、請求の範囲第１項記載の方法。
【請求項４２】
（追加）前記データアイテムのそれぞれについて、前記ファーポインタは、各Ｎ番目のセットの最後のファーポインタを除いたファーポインタのそれぞれが、該Ｎ番目のセットの別のファーポインタが格納されたアドレスを示し、（Ｎ−１）番目のセットの複数のファーポインタが、該Ｎ番目のセットのファーポインタの連続する対が格納されたアドレスの間に割り当てられたアドレスに格納される、ファーポインタのセットのヒエラルキーを含むことを特徴とする、請求の範囲第４１項記載の方法。
【請求項４３】
（追加）前記工程（ｂ）が、各（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目の組の各々へのポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレス部に格納し、ここで、Ａは、所定の１より大きい整数の定数であり、Ｂが０より大きい整数のパラメータであり、Ｃは、０以上の整数のパラメータであり、Ｋは、０以上の所定の整数の定数であることを特徴とする、請求の範囲第４２項記載のメモリ制御方法。
【請求項４４】
（追加）１≦Ｂ≦ＡおよびＫ＝０であることを特徴とする、請求の範囲第４３項記載のメモリ制御方法。
【請求項４５】
（追加）Ａ＝４であることを特徴とする、請求の範囲第４４項記載のメモリ制御方法。
【請求項４６】
（追加）前記ファーポインタのそれぞれは、該ファーポインタのアドレスにおけるセットの後に、前記データアイテムに対する複数のセットであって、前記ファーポインタの前記アドレスのセットが格納された後に割り当てられたアドレスを示すことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項４７】
（追加）前記データアイテムのそれぞれについて、最後のファーポインタを除いたファーポインタのそれぞれは、別のファーポインタが格納されたアドレスを示すことを特徴とする、請求の範囲第１９項記載の記憶装置。
【請求項４８】
（追加）前記データアイテムのそれぞれについて、前記ファーポインタは、各Ｎ番目のセットの最後のファーポインタを除いたファーポインタのそれぞれが、該Ｎ番目のセットの別のファーポインタが格納されたアドレスを示し、（Ｎ−１）番目のセットの複数のファーポインタが、該Ｎ番目のセットのファーポインタの連続する対が格納されたアドレスの間に割り当てられたアドレスに格納される、ファーポインタのセットのヒエラルキーを含むことを特徴とする、請求の範囲第４７項記載の記憶装置。
【請求項４９】
（追加）前記ファーポインタ格納手段が、ポインタを、各〔ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ〕番目のセットに、〔ＡＢ．Ｃ＋（Ａ−Ｂ）＋Ｋ〕番目のセットに割り当てられたアドレス部で格納する手段を含み、ここで、Ａは１より大きい所定の整数の定数であり、Ｂは、０より大きい整数のパラメータであり、Ｃは、０以上の整数のパラメータであり、Ｋは０以上の所定の整数の定数であることを特徴とする、請求の範囲第４８項記載の記憶装置。
【請求項５０】
（追加）１≦Ｂ≦ＡおよびＫ＝０であることを特徴とする、請求の範囲第４９項記載の記憶装置。
【請求項５１】
（追加）Ａ＝４であることを特徴とする、請求の範囲第５０項記載の記憶装置。
【手続補正書】
【提出日】平成16年2月23日(2004.2.23)
【手続補正００１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】（削除）
【請求項２】（削除）
【請求項３】（削除）
【請求項４】（削除）
【請求項５】（削除）
【請求項６】（削除）
【請求項７】（削除）
【請求項８】（削除）
【請求項９】（削除）
【請求項１０】（削除）
【請求項１１】（削除）
【請求項１２】（削除）
【請求項１３】（削除）
【請求項１４】（削除）
【請求項１５】（削除）
【請求項１６】（削除）
【請求項１７】（削除）
【請求項１８】（削除）
【請求項１９】（削除）
【請求項２０】（削除）
【請求項２１】（削除）
【請求項２２】（削除）
【請求項２３】（削除）
【請求項２４】（削除）
【請求項２５】（削除）
【請求項２６】（削除）
【請求項２７】（削除）
【請求項２８】（削除）
【請求項２９】（削除）
【請求項３０】（削除）
【請求項３１】（削除）
【請求項３２】（削除）
【請求項３３】（削除）
【請求項３４】（削除）
【請求項３５】（削除）
【請求項３６】（削除）
【請求項３７】（削除）
【請求項３８】（削除）
【請求項３９】（削除）
【請求項４０】（削除）
【請求項４１】（削除）
【請求項４２】（削除）
【請求項４３】（削除）
【請求項４４】（削除）
【請求項４５】（削除）
【請求項４６】（削除）
【請求項４７】（削除）
【請求項４８】（削除）
【請求項４９】（削除）
【請求項５０】（削除）
【請求項５１】（削除）
【請求項５２】少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目のセットの各々への各ファーポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレスに格納するスキームに従って、該値のセットのうちのいくつかのセットのアドレスへのファーポインタを格納する工程であって、ここで、Ａは、１より大きい所定の整数の定数であり、Ｂは、Ｂが単一の値を有する場合を除いた、１≦Ｂ≦Ａの整数のパラメータであり、Ｃは、−１より大きい整数のパラメータであり、Ｋは、−１より大きい所定の整数の定数である、工程と、
（ｃ）該いくつかのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含し、
該値または第１の値の新たなセットが、格納のために受け取られる場合、該アドレス部のそれぞれは割り当てられ、該ファーポインタおよび該ローカルポインタのそれぞれに示されたアドレスが該新たなセットに割り当てられた後に、該ファーポインタおよび該ローカルポインタのそれぞれが前に割り当てられたアドレス部に格納される、メモリ制御方法。
【請求項５３】少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目のセットの各々への各ファーポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレスに格納するスキームに従って、該値のセットのうちのいくつかのセットのアドレスへのファーポインタを格納する工程であって、ここで、Ａは、１より大きい所定の整数の定数であり、Ｂは、１≦Ｂ≦Ａのようなすべての値を有する整数のパラメータであり、Ｃは、−１より大きい整数のパラメータであり、Ｋは、−１より大きい所定の整数の定数である、工程と、
（ｃ）該いくつかのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含し、
該値または第１の値の新たなセットが、格納のために受け取られる場合、該アドレス部のそれぞれは割り当てられ、該ファーポインタおよび該ローカルポインタのそれぞれに示されたアドレスが該新たなセットに割り当てられた後に、該ファーポインタおよび該ローカルポインタのそれぞれが前に割り当てられたアドレス部に格納される、メモリ制御方法。
【請求項５４】前記メモリセグメントが不揮発性であることを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項５５】前記メモリセグメントが、全体としてのみ消去可能であることを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項５６】前記メモリセグメントが、フラッシュメモリの少なくとも一部を含むことを特徴とする、請求の範囲第５５項記載のメモリ制御方法。
【請求項５７】各セットが単一の値を含むことを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項５８】各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項５９】前記データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納することを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項６０】前記アドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項６１】前記アドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項６２】前記メモリセグメントが一杯である場合に、前記データアイテムまたは各データアイテムの一番最近に受け取った値が、他のメモリセグメントにコピーされ、その後、該メモリセグメントが消去されることを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項６３】一番最近に受け取った値、該一番最近に受け取った値のアドレス、および、前記少なくとも一つのデータアイテムのうちのセットの数をキャッシュメモリに格納することを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項６４】少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目のセットの各々への各ファーポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレスに格納するスキームに従って、該値のセットのうちのいくつかのセットのアドレスへのファーポインタを格納する工程であって、ここで、Ａは、１より大きい所定の整数の定数であり、Ｂは、Ｂが単一の値を有する場合を除いた、１≦Ｂ≦Ａの整数のパラメータであり、Ｃは、−１より大きい整数のパラメータであり、Ｋは、−１より大きい所定の整数の定数である、工程と、
（ｃ）該いくつかのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含するメモリ制御方法であって、第１のセットに割り当てられたアドレスで開始し、
（ｉ）ファーまたはローカルポインタのアドレスを調べる工程と、
（ｉｉ）ファーポインタが存在する場合、ファーポインタが指すアドレスについて、該工程（ｉ）を行う工程と、
（ｉｉｉ）ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて、工程（ｉ）を行う工程と、
（ｖｉ）ファーポインタもローカルポインタもない場合、該アドレスにおける最新値を戻す工程と
を包含するメモリ制御方法。
【請求項６５】少なくとも一つのデータアイテムの時間的に連続する値を、格納された値が個別に上書きされることができないタイプのメモリセグメントに格納するメモリ制御方法であって、
（ａ）該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられたそれぞれのアドレス部に、連続する値のセットを格納する工程と、
（ｂ）（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目のセットの各々への各ファーポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレスに格納するスキームに従って、該値のセットのうちのいくつかのセットのアドレスへのファーポインタを格納する工程であって、ここで、Ａは、１より大きい所定の整数の定数であり、Ｂは、１≦Ｂ≦Ａのような全ての値を有する整数のパラメータであり、Ｃは、−１より大きい整数のパラメータであり、Ｋは、−１より大きい所定の整数の定数である、工程と、
（ｃ）該いくつかのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する工程と
を包含するメモリ制御方法であって、第１のセットに割り当てられたアドレスで開始し、
（ｉ）ファーまたはローカルポインタのアドレスを調べる工程と、
（ｉｉ）ファーポインタが存在する場合、ファーポインタが指すアドレスについて、該工程（ｉ）を行う工程と、
（ｉｉｉ）ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて、工程（ｉ）を行う工程と、
（ｖｉ）ファーポインタもローカルポインタもない場合、該アドレスにおける最新値を戻す工程と
を包含するメモリ制御方法。
【請求項６６】前記工程（ｉ）が、前記アドレスにおいて少なくとも一つのポインタ位置を調べる工程と、該少なくとも一つの位置が非リセット状態であることを示す工程とを含むことを特徴とする、請求の範囲第６４項または第６５項記載のメモリ制御方法。
【請求項６７】前記工程（ｖｉ）が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスをキャッシュメモリに格納する工程を含むことを特徴とする、請求の範囲第６４項または第６５項記載のメモリ制御方法。
【請求項６８】少なくとも一つのデータアイテムの時間的に連続する値を格納する記憶装置であって、格納された値が個別に上書きされることができないタイプのメモリセグメントと、該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられた該連続する値のセットをそれぞれのアドレス部に格納する手段とを含み、（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目のセットの各々への各ファーポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレスに格納するスキームに従って、該値のセットのうちのいくつかのセットのアドレスへのファーポインタを格納する手段であって、ここで、Ａは、１より大きい所定の整数の定数であり、Ｂは、Ｂが単一の値を有する場合を除いた、１≦Ｂ≦Ａの整数のパラメータであり、Ｃは、−１より大きい整数のパラメータであり、Ｋは、−１より大きい所定の整数の定数である、手段と、該いくつかのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する手段とを含み、
該値または第１の値の新たなセットが、格納のために受け取られる場合、該アドレス部のそれぞれは割り当てられ、該ファーポインタおよび該ローカルポインタのそれぞれに示されたアドレスが該新たなセットに割り当てられた後に、該ファーポインタおよび該ローカルポインタのそれぞれが前に割り当てられたアドレス部に格納されることを特徴とする記憶装置。
【請求項６９】少なくとも一つのデータアイテムの時間的に連続する値を格納する記憶装置であって、格納された値が個別に上書きされることができないタイプのメモリセグメントと、該データアイテムまたは各データアイテムについて、時間的に連続するように割り当てられた該連続する値のセットをそれぞれのアドレス部に格納する手段とを含み、（ＡＢ（Ｃ＋１）＋（Ａ−Ｂ）＋Ｋ）番目のセットの各々への各ファーポインタを、（ＡＢＣ＋（Ａ−Ｂ）＋Ｋ）番目のセットに割り当てられたアドレスに格納するスキームに従って、該値のセットのうちのいくつかのセットのアドレスへのファーポインタを格納する手段であって、ここで、Ａは、１より大きい所定の整数の定数であり、Ｂは、１≦Ｂ≦Ａのようなすべての値を有する整数のパラメータであり、Ｃは、−１より大きい整数のパラメータであり、Ｋは、−１より大きい所定の整数の定数である、手段と、該いくつかのセット以外の他のセットのそれぞれに割り当てられたアドレスへのローカルポインタを、該他のセットのそれぞれの直前のセットに割り当てられたアドレス部に格納する手段とを含み、
該値または第１の値の新たなセットが、格納のために受け取られる場合、該アドレス部のそれぞれは割り当てられ、該ファーポインタおよび該ローカルポインタのそれぞれに示されたアドレスが該新たなセットに割り当てられた後に、該ファーポインタおよび該ローカルポインタのそれぞれが前に割り当てられたアドレス部に格納されることを特徴とする記憶装置。
【請求項７０】前記メモリセグメントが不揮発性であることを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７１】前記メモリセグメントが全体としてのみ消去可能であることを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７２】前記メモリセグメントがフラッシュメモリの少なくとも一部を含むことを特徴とする、請求の範囲第７１項記載の記憶装置。
【請求項７３】各セットが単一の値を含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７４】各セットがＸ値を含み、ここで、Ｘは、１より大きい整数であることを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７５】前記データアイテムまたは各データアイテムについて、第１のセットのアドレスへのポインタを、該データアイテムで識別されたアドレス部に格納する手段を含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７６】前記アドレス部の各々が、前記値のセット、ローカルポインタおよびファーポインタに充分な格納スペースを含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７７】前記アドレス部の各々が、前記値のセットおよび該アドレスに格納可能な任意のポインタのセットのみに充分な格納スペースを含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７８】前記メモリセグメントが一杯である場合に、前記データアイテムまたは各データアイテムの一番最近に受け取った値を、他のメモリセグメントにコピーする手段と、該メモリセグメントを消去する手段とを含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項７９】キャッシュメモリと、一番最近に受け取った値、該一番最近に受け取った値のアドレス、および、前記少なくとも一つのデータアイテムのうちのセットの数を該キャッシュメモリに格納する手段とを含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項８０】前記第１のセットから開始して、ファーまたはローカルポインタのアドレスを調べ、ファーポインタが存在する場合、ファーポインタが指すアドレスについて調べ、ローカルポインタが存在し、ファーポインタが存在しない場合、該ローカルポインタが指すアドレスについて調べ、ファーポインタもローカルポインタもない場合、該アドレスにおける該最新値を戻す読み取り手段を含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項８１】前記ファーまたはローカルポインタの存在を調べる手段が、前記アドレス部において少なくとも一つのポインタ位置を調べる手段と、該少なくとも一つの位置が非リセット状態であることを示す手段とを含むことを特徴とする、請求の範囲第８０項記載の記憶装置。
【請求項８２】前記最新値を戻す手段が、最新の値、一番最近ファーポインタに格納された値、および最新の値に割り当てられたアドレスを、キャッシュメモリに格納する手段を含むことを特徴とする、請求の範囲第８０項記載の記憶装置。
【請求項８３】コンピュータを含むことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項８４】請求の範囲第５２項または第５３項記載のメモリ制御方法の各処理手順をコンピュータに実行させる制御プログラム。
【請求項８５】請求の範囲第８４項記載の制御プログラムが記録された可読記録媒体。
【請求項８６】前記ファーポインタのそれぞれは、該ファーポインタが格納されたアドレスにおけるセットの後の、前記データアイテムに対する複数のセットが格納された後に割り当てられたアドレスを示すことを特徴とする、請求の範囲第５２項または第５３項記載の方法。
【請求項８７】Ｋ＝０であることを特徴とする、請求の範囲第５２項または第５３項記載のメモリ制御方法。
【請求項８８】Ａ＝４であることを特徴とする、請求の範囲第８７項記載のメモリ制御方法。
【請求項８９】前記ファーポインタのそれぞれは、該ファーポインタが格納されたアドレスにおけるセットの後の、前記データアイテムに対する複数のセットが格納された後に割り当てられたアドレスを示すことを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項９０】Ｋ＝０であることを特徴とする、請求の範囲第６８項または第６９項記載の記憶装置。
【請求項９１】Ａ＝４であることを特徴とする、請求の範囲第９０項記載の記憶装置。


【手続補正００２】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
2003077133.tif 000030
【国際調査報告】
2003077133.tif 000031
2003077133.tif 000032
2003077133.tif 000033
2003077133.tif 000034