(57)【要約】【課題】アドレステーブルの迅速かつ柔軟なアクセスが実現でき、特定消去ブロックへの書き換えの集中も防止でき、アドレステーブルの管理や操作もシンプルとなる記憶装置、コンピュータシステム、および記憶装置のアクセス方法を提供することにある。【解決手段】アドレステーブル４２を分割し、その各々をユーザーデータと混在した状態で、分散させてフラッシュメモリ内に格納するとともに、両者を統一的に管理する。この時フラッシュメモリ上のアドレステーブル４２は、ユーザーデータと殆ど同様の手順でアクセスされる。これによりアドレス変換を用いたユーザーデータの効率的な管理手法を、フラッシュメモリ上のアドレステーブルの操作にもそのまま適用することが可能になり、アドレステーブルの迅速かつ柔軟なアクセスが実現できる。特定消去ブロックへの書き換えの集中も防止でき、アドレステーブルの管理や操作もシンプルになる。【選択図】図６
2007334852.tif 000002
【特許請求の範囲】
【請求項１】
アドレステーブルと、
キャッシュメモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、
上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、上記キャッシュメモリ上に展開される
記憶装置。
【請求項２】
上記キャッシュメモリはライトバック方式でアクセスされる
請求項１記載の記憶装置。
【請求項３】
上記キャッシュメモリは、上記小アドレステーブルをエントリとして、小アドレステーブルを複数格納する
請求項１記載の記憶装置。
【請求項４】
上記小アドレステーブルは、上記フラッシュメモリデバイスにおける一括読み出し／書き込み単位であるページごとに、上記フラッシュメモリデバイスに格納されている
請求項１記載の記憶装置。
【請求項５】
第２のアドレステーブルを、さらに有し、
上記第２のアドレステーブルにおいては、初期論理アドレスに対応する上記小アドレステーブルの上記フラッシュメモリデバイス上の所在情報が取得され、
上記制御回路によるフラッシュメモリ上のユーザーデータへのアクセス管理においては、
初期論理アドレス情報をもとに、上記第２のアドレステーブルが参照され、対応する小アドレステーブルの所在情報が取得され、
上記所在情報を基に、まずキャッシュメモリ内の所望の小アドレステーブルの有無がチェックされ、
ミスヒットの場合はフラッシュメモリから対応する小アドレステーブルが読み出されて、上記メモリ領域上に展開され、
初期論理アドレス情報をもとに、上記小アドレステーブルが参照され、アクセスすべきユーザーデータの所在情報が取得され、
上記ユーザーデータの所在情報を基に、フラッシュメモリ上のユーザーデータがアクセスされる
請求項１記載の記憶装置。
【請求項６】
第２のアドレステーブルを、さらに有し、
上記第２のアドレステーブルにおいては、初期論理アドレスに対応する上記小アドレステーブルの上記フラッシュメモリデバイス上の所在情報が取得され、
上記制御回路によるフラッシュメモリ上のユーザーデータへのアクセス管理においては、
初期論理アドレス情報をもとに、キャッシュメモリ内の所望の小アドレステーブルの有無がチェックされ、
ミスヒットの場合、初期論理アドレス情報をもとに、上記第二のアドレステーブルが参照され、対応する小アドレステーブルの所在情報が取得され、さらにフラッシュメモリから対応する小アドレステーブルが読み出されて、上記メモリ領域上に展開され、
初期論理アドレス情報をもとに、上記小アドレステーブルが参照され、アクセスすべきユーザーデータの所在情報が取得され、
上記ユーザーデータの所在情報を基に、フラッシュメモリ上のユーザーデータがアクセスされる
請求項１記載の記憶装置。
【請求項７】
第１のアドレステーブルと、
第２のアドレステーブルと、
メモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、
上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記第１のアドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記第１のアドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記メモリ上に展開され、
上記第２のアドレステーブルにおいては、初期論理アドレスに対応する上記小アドレステーブルの上記フラッシュメモリデバイス上の所在情報が取得され、
上記小アドレステーブルがフラッシュメモリに保存される際には、上記第２のアドレステーブル上の、上記小アドレステーブルに対応する所在情報が、同時並列的に更新され、上記第２のアドレステーブルの更新箇所を示す情報が、フラッシュメモリ上に保存される小アドレステーブルを含むデータグループ内の予備領域に同時に保存される
記憶装置。
【請求項８】
第１のアドレステーブルと、
第２のアドレステーブルと、
メモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、
上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記第１のアドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記第１のアドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記メモリ上に展開され、
上記第２のアドレステーブルにおいては、初期論理アドレスに対応する上記小アドレステーブルの上記フラッシュメモリデバイス上の所在情報が取得され、
上記第２のアドレステーブルは、不揮発性ＲＡＭに格納されている
記憶装置。
【請求項９】
アドレステーブルと、
キャッシュメモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、
上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該小アドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記キャッシュメモリに展開され、
上記キャッシュメモリには複数のエントリが登録でき、ユーザーデータが格納された第１のエントリと、上記小アドレステーブルが格納された第２のエントリとが、混在して登録されている
記憶装置。
【請求項１０】
上記キャッシュメモリ上の全てのユーザーデータに対して、対応するアドレステーブルが同時にキャッシュメモリ上に存在していることを保証するように、アドレステーブルの開放順位が設定される
請求項９記載の記憶装置。
【請求項１１】
少なくともユーザーデータが上記キャッシュメモリに追加される際には、対応するテーブルの開放順位が、その下位に設定される
請求項１０記載の記憶装置。
【請求項１２】
記憶媒体であるフラッシュメモリデバイスと、
制御回路と、を有し、
上記制御回路は、ホストから入力されたユーザーデータと、当該記憶装置内部で生成され、使用される管理用データの双方をフラッシュメモリに保存し、
上記ユーザーデータと管理用データは、各々複数の格納領域をフラッシュメモリデバイス上に動的に確保され、それらの領域は互いに混在して存在している
記憶装置。
【請求項１３】
上記制御回路は、
上記フラッシュメモリデバイスの物理アドレスまたは論理アドレスに沿って共通のポインタを進め、
上記ポインタ位置またはその近傍に第１の空き領域を確保して、当該第１の空き領域にユーザーデータを記録し、あるいは第２の空き領域を確保して、当該第２の空き領域に管理用データを記録する
請求項１２記載の記憶装置。
【請求項１４】
ユーザーデータの格納領域および管理用データの格納領域は、上記フラッシュメモリデバイスの一括消去単位であるブロック領域ごとに確保される
請求項１２記載の記憶装置。
【請求項１５】
ユーザーデータの格納領域および管理用データの格納領域は、上記フラッシュメモリデバイスの一括消去単位であるブロック領域ごとに確保される
請求項１３記載の記憶装置。
【請求項１６】
ユーザーデータおよび管理用データは、上記フラッシュメモリデバイスの一括書き込み単位であるページ領域ごとに、確保されたブロック領域内の下位アドレスから下詰で格納される
請求項１４記載の記憶装置。
【請求項１７】
ユーザーデータおよび管理用データは、上記フラッシュメモリデバイスの一括書き込み単位であるページ領域ごとに、確保されたブロック領域内の下位アドレスから下詰で格納される
請求項１５記載の記憶装置。
【請求項１８】
アドレステーブルと、
メモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、
上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記メモリ上に展開され、
上記小アドレステーブルの格納領域は、上記フラッシュメモリデバイスの一括消去単位であるブロック領域ごとに、ユーザーデータが格納されたブロックと混在して動的に確保され、各ブロック領域には複数の小アドレステーブルが格納される
記憶装置。
【請求項１９】
複数の小アドレステーブルを含む連続したインデックス領域ごとに、上記格納用ブロックは各々確保され、各インデックス領域に対応するフラッシュメモリデバイス上の各ブロックの所在が第２のテーブルとしてメモリ上に保存されている
請求項１８記載の記憶装置。
【請求項２０】
各小アドレステーブルは、上記フラッシュメモリデバイスの一括書き込み単位であるページ領域ごとに、確保されたブロック領域内の下位アドレスから下詰で格納される
請求項１８記載の記憶装置。
【請求項２１】
アドレステーブルと、
キャッシュメモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、
上記フラッシュメモリデバイスのユーザーデータにアクセス可能な処理装置と、を有し、
上記制御回路は、上記処理装置が上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、上記キャッシュメモリ上に展開される
コンピュータシステム。
【請求項２２】
上記キャッシュメモリはライトバック方式でアクセスされる
請求項２１記載のコンピュータシステム。
【請求項２３】
上記キャッシュメモリは、上記小アドレステーブルをエントリとして、小アドレステーブルを複数格納する
請求項２１記載のコンピュータシステム。
【請求項２４】
アドレステーブルと、
キャッシュメモリと、
ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、
上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、
上記フラッシュメモリデバイスのユーザーデータにアクセス可能な処理装置と、を有し、
上記制御回路は、上記処理装置が上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該小アドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記キャッシュメモリに展開され、
上記キャッシュメモリには複数のエントリが登録でき、ユーザーデータが格納された第１のエントリと、上記小アドレステーブルが格納された第２のエントリとが、混在して登録されている
コンピュータシステム。
【請求項２５】
フラッシュメモリデバイスのユーザーデータにアクセスする記憶装置のアクセス方法であって、
上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、キャッシュメモリ上に展開される
記憶装置のアクセス方法。
【請求項２６】
上記キャッシュメモリはライトバック方式でアクセスされる
請求項２５記載の記憶装置のアクセス方法。
【請求項２７】
上記キャッシュメモリは、上記小アドレステーブルをエントリとして、小アドレステーブルを複数格納する
請求項２５記載の記憶装置のアクセス方法。
【請求項２８】
フラッシュメモリデバイスのユーザーデータにアクセスする記憶装置のアクセス方法であって、
上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、
上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、
上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該小アドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、キャッシュメモリに展開され、
上記キャッシュメモリには複数のエントリが登録でき、ユーザーデータが格納された第１のエントリと、上記小アドレステーブルが格納された第２のエントリとが、混在して登録される
記憶装置のアクセス方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不揮発性メモリを含む記憶装置およびコンピュータシステムに関し、特にフラッシュメモリを主記憶媒体とする記憶装置、コンピュータシステム、および記憶装置のアクセス方法に関するものである。
【背景技術】
【０００２】
近年、デジタルスチルカメラやモバイルコンピュータ機器の記憶媒体として、フラッシュメモリが注目されている。
【０００３】
フラッシュメモリは、トンネリングやホットエレクトロン加速を用いて、電子にゲート絶縁膜を通過させ、それらを浮遊ゲートやトラップ層に注入し、セルトランジスタの閾値を変化させることでデータを記憶させる半導体メモリである。積層ゲート構造やＭＮＯＳ構造等を用いたトランジスタ１つのみでメモリセルを構成できるため、安価かつ大容量のメモリを実現できる。
その代表例として、ＮＡＮＤ型フラッシュメモリが挙げられる。
【０００４】
図１は、ＮＡＮＤ型フラッシュメモリの内部構成例を示す図である。
図１のＮＡＮＤ型フラッシュメモリは、ビット線ＢＬ１〜ＢＬｎに接続された複数のメモリユニット１−１〜１−ｎがアレイ状に（縦横）に配列されている。
たとえば、選択用トランジスタ２のゲートが選択ゲート線ＳＬ１に接続され、選択用トランジスタ３のゲートが選択ゲート線ＳＬ２に接続されている。また、各メモリセルＮ０〜Ｎ１５のゲートがワード線ＷＬ０〜ＷＬ１５に接続されている。
【０００５】
各メモリセルＮ０〜Ｎ１５は積層ゲート構造を持ち、浮遊ゲートへの電荷蓄積量に従ってデータを記憶する。すなわち、浮遊ゲートに多くの電子が蓄積されていると、トランジスタの閾値が上昇するので、チャージされたビット線ＢＬ１〜ＢＬｎからのメモリユニット１（−１〜−ｎ）への電流貫通の有無を、センスアンプ等を含むアクセス回路４で検出してデータ判定を行う。
【０００６】
このようなＮＡＮＤ型フラッシュメモリは、メモリセル毎にビット線へのコンタクト領域を設ける必要もないので、特に大容量で安価な記憶装置の媒体に適している。
【０００７】
ところで、一般にフラッシュメモリのプログラム速度は非常に遅く、セルあたり数百マイクロ（μ）秒を必要とする。またデータの上書きはできないので、プログラムに先立って消去を行う必要があり、これには数ｍ秒もの時間がかかる。このような問題に対しては、多くのメモリセルを並列処理することで対処している。
【０００８】
すなわち、たとえば同一ワード線ＷＬ０に接続され、ページ単位を成すメモリセル群５を、同時一括に書き込み、さらに互いにメモリユニットを共有するページ群で構成されるセルブロック６を全て一括で消去することにより、プログラムの転送速度を向上させている。
【０００９】
具体的には、たとえば非特許文献１には１ＧｂのＮＡＮＤ型フラッシュメモリが掲載されており、ページサイズを２ｋバイト、消去ブロックサイズを１２８ｋＢとしている。すなわち、一つのメモリアレイ内で１２８ｋバイトのメモリセル群を並列消去し、そこにメモリセルを２ｋバイト毎に並列でプログラムしていくことによって、１０ＭＢ／ｓのプログラム転送速度を実現している。
【００１０】
なお、ＮＡＮＤ型フラッシュメモリの分野内においても、微細化や多値化の進展により、メモリの内部構成にはさまざまなバリエーションが存在する。しかしメモリとしてみれば、そのアクセスはページと呼ばれる一括書き込み／読み出しの単位と、ブロックもしくは消去ブロックと呼ばれる一括消去単位を用いて実行され、ブロックが複数のページを含む構成であることは変わらない。
【００１１】
または、メモリデバイスが複数のフラッシュメモリチップを有し、それら複数チップを同時に動作させて並列書き込みを実施することもある。その場合、各々のチップにおけるページの集合体がメモリデバイスにおける実ページを構成し、それがこのメモリデバイスの一括書き込みの単位となる。このとき、各々のチップにおいて対応する消去ブロックの集合体もメモリデバイスの実消去ブロックを構成し、それらがメモリデバイスにおける一括消去単位となる。したがって、このようなメモリデバイスにおいても、一括消去単位である実消去ブロックは、互いに独立した書き込み単位たる実ページを複数含んで構成される。
【００１２】
さらに、近年微細化に伴う内部構造と書き込みメカニズムの変化から、ブロック内の各ページの書き込み順序にも制約がつくようになった。すなわち、各ページの書き込みは下位アドレスから上位アドレスへの順方向に制限されており、逆方向の書き込みは禁止されている。たとえば、一旦どこかのページに書き込みを実施したら、同一ブロック内のそれより下位のアドレスが未書き込みの状態でも、そこにデータを書き込むことはできない。
【００１３】
なお、通常ＮＡＮＤ型フラッシュの各ページは、たとえば２ｋバイトのユーザーデータ格納領域に対して６４バイトの予備領域を有している。この予備領域には、ＮＡＮＤ型フラッシュを使用するシステム側で、パリティビット等の各種管理データを格納することが可能である。この予備領域への書き込みは、通常ユーザーデータ領域への書き込みと一括で行う必要があり、両者は常にセットとして扱われる。
【００１４】
ところで、通常のファイルストレージでは、最小の書き換え単位は５１２Ｂのセクタであり、この単位でランダムなアクセスがなされる。その場合、たとえば１つのページ領域の一部のみを書き換える要求が発生する。
しかし、上述のようなフラッシュメモリでそのようなアクセスを行うと、結局実消去ブロック領域全体を消去せねばならない。かつその中の非選択領域に有効ファイルがあれば、それを消失から保護する必要がある。
【００１５】
図２にそのようなデータ更新の一例を示す。更新手順は以下の通りである。
【００１６】
１．まずフラッシュメモリ２０から、バッファメモリ２３に、実消去ブロック領域２１全体のデータを読み出す。
２．次にバッファメモリ２３内で、相当するデータを更新する。
３．次にフラッシュメモリ上のブロック領域２１の消去を実行する。
４．最後に上記消去済の領域２１に、バッファメモリ２３から、更新後のブロックデータを全て書き戻す。
【００１７】
このように、わずか数セクタの書き換えに伴う一連の作業には、１００倍近いデータ量の読み出しと書き込み、さらにブロック消去という、多大なオーバーヘッドが含まれる。その結果ハードディスク装置のフルシークに相当する時間が費やされる。
【００１８】
実際にファイルを更新する場合、該当ファイルのみではなく、その管理領域やログの記載等、関連する複数の小領域を同時に更新するのが普通である。また、ファイル自体も複数の小領域に断片化して存在しているケースがある。したがって、上述の如き制約があると、現実の転送性能は著しく低いものになってしまう。
【００１９】
このような作業を効率化するために、アドレス変換を用いた、より柔軟なメモリ管理が各種提案されている。現在最も頻繁に使用されているのは、消去ブロック単位でアドレス変換を実施するやり方である。
【００２０】
図３（Ａ），（Ｂ）は、消去ブロック単位でアドレス変換を実施する方法の例を示す図である。
図３（Ａ）はフラッシュメモリの記憶領域を示し、図３（Ｂ）はアドレステーブルを示している。
アドレステーブル２７は、論理ブロックアドレス（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ  ＝ＬＢＡ）をインデックスとして、対応する消去ブロックのフラッシュメモリ上のアドレスである物理ブロックアドレス（Ｐｈｉｓｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ  ＝ＰＢＡ）を取得することができる。
たとえば、ホストまたはアプリケーションが“０ｘ５５”のブロックアドレスへのアクセスを要求した場合、そのアドレスはテーブルにより“０ｘ６Ｂ”に変換され、フラッシュメモリ２０の消去ブロック２１にアクセスが実施される。
【００２１】
このような管理下におけるフラッシュメモリ上のデータ更新手順は以下の通りである。
１．予め予備の消去済みブロック２５を用意しておく。その物理アドレスは“０ｘＡＡ”とする。
２．論理ブロックアドレス“０ｘ５５”が指定され、対応する物理ブロックアドレス“０ｘ６Ｂ”が取得され、ブロック２１内のページ２２にアクセスがなされたとする。このとき、フラッシュメモリ２０の書き換え対象ブロック２１から、別途設けられたページバッファ２４を介して、予備ブロック２５にデータを順次コピーしていく。
３．更新対象となるページ２２のコピー時には、ページバッファ２４上で所望の箇所を更新してコピーを行い、コピー先ページ２６にそれが反映される。
４．有効なページデータのコピーが全て完了したら、アドレステーブル２７上で、ブロック２１と予備ブロック２５のアドレスを張り替える。
５．最後に元ブロック２１の消去を実施する。
【００２２】
このような手順によって、以降論理ブロックアドレス“０ｘ５５”に対しては、物理ブロックアドレス“０ｘＡＡ”に対応する消去ブロック、すなわち予備ブロック２５がアクセスされるようになり、全体との整合性が保たれる。
更新後のブロック２５には、上記処理４．の時点で既にアクセスが可能になり、消去の時間を節約できる。
予備ブロックを複数設けて全体の中で循環させれば、特定ブロックへの書き換えの集中も緩和できる。また、このようなアドレス変換は欠陥ブロックへのアクセスを防止する目的にも有用である。
【００２３】
さらに、特許文献１には、フラッシュメモリの一括書き込み単位であるページごとのアドレス変換を用いた、追記型記憶システムにおける管理方法の詳細が記載されている。
【００２４】
図４（Ａ），（Ｂ）は、追記型記憶システムにおける管理方法を説明するための図である。
図４（Ａ）はフラッシュメモリの記憶領域を示し、図４（Ｂ）はアドレステーブルを示している。
【００２５】
この場合、アドレステーブル２８からは、論理ページアドレス（Ｌｏｇｉｃａｌ  Ｐａｇｅ  Ａｄｄｒｅｓｓ  ＝ＬＰＡ）をインデックスとして、対応するページのフラッシュメモリ上のアドレスである物理ページアドレス（Ｐｈｉｓｉｃａｌ  Ｐａｇｅ  Ａｄｄｒｅｓｓ  ＝ＰＰＡ）を取得することができる。
たとえば、ホストから指定された論理ページアドレス“０ｘ５５０２”への書き込みに対して、アドレステーブルを用いてページ単位でアドレス変換を実施し、フラッシュメモリ上の物理ページアドレス“０ｘ６Ｂ０５”を取得する。これによりブロック２１内の対応するページ領域２２へアクセスが実施される。
一方、同ページに更新を行う際には、フラッシュメモリ内で直接書き込める適当な空きページ領域が検索される。たとえば、物理ブロックアドレス“０ｘＡＡ”に相当する消去済み空きブロック２５の先頭ページ領域２９が適切な書き込み先として選択された場合、ページ領域２２のデータのみがページバッファ２４を介して更新され、ページ領域２９に書き込まれる。この際、論理ページアドレス“０ｘ５５０２”はページ領域２９の物理アドレス“０ｘＡＡ００”にリマッピングされる。ページ領域２２上の旧データは、当面そのまま残して無効扱いとしておく。
【００２６】
このような管理を実施すれば、フラッシュメモリ内に空き領域が存在する限りは、各ページデータの更新に対して１ページ分のデータ書き込みで良い。
したがって、高速に書き換えを実施することができる。その間消去の必要も無いので、フラッシュメモリの書き換え回数も大幅に低減でき、その寿命も向上させることができる。
【００２７】
さらに発明者らは、特願２００５−１１４７１１号、特願２００５−１６５２３４号、特願２００５−１７１４号等において、上記ページ単位のアドレス変換を活用した、より発展的な管理手法を提案している。
あるいは、上記ページ単位のアドレス変換とブロック単位のアドレス変換の中間的な形態も存在する。たとえば各ブロックと、その中に含まれるページ群の関係は保ったままで、ブロック内部の各ページの位置関係をリマッピングする。これによるオーバーヘッドの低減効果は先述の二手法の中間である。
【００２８】
このようにアドレステーブルを用いたリマッピングによる、フラッシュメモリ上のユーザーデータの管理には、様々なバリエーションが存在する。
いずれも初期論理アドレスから生成されたアドレス値をインデックスとしてアドレステーブルを参照し、対応するユーザーデータの所在情報（フラッシュメモリ上の物理アドレス等）を取得する。それをもとにフラッシュメモリへのデータアクセスを実施する。
特に、一括書き込み単位である各ページグループについて、互いの相対位置を変えるリマッピングを実施すれば、アクセス効率の向上に顕著な効果を獲得することができる。
【非特許文献１】ＩＳＳＣＣ２００２予稿集のｐ１０６、セッション６．４
【特許文献１】特開平８−３２８７６２号公報
【発明の開示】
【発明が解決しようとする課題】
【００２９】
上述の如く、アドレステーブルを用いたリマッピングを活用すれば、より柔軟で効率的なデータアクセスが実現できる。
しかし、効果的な管理を行おうとすれば、それだけ微細な単位でのアドレス変換が必要になり、テーブルの大きさが巨大になって、多量のメモリ領域を占有してしまう。
たとえばページサイズが２ｋＢで、総容量２ＧＢのストレージの場合、その中には１Ｍ個ものページグループが格納される。ここにページ単位で完全なアドレス変換を実施すれば、そのアドレッシングには２０ビットが必要なので、アドレステーブルは２０Ｍビットもの大きさになってしまう。
【００３０】
このような問題に対処するには、フラッシュメモリ内にアドレステーブルを格納し、必要な箇所のみをＲＡＭ上に読み出すのが有効である。
しかし、アドレステーブルは常時更新されていくので、フラッシュメモリ上のアドレステーブルも適時更新されなければならない。しかし、前述の如くフラッシュメモリの書き換えには制限が多く、読み出しや書き込みでエラーが発生すると、その対処も必要である。
【００３１】
一般的に、アドレステーブルのフラッシュメモリへの格納には、専用の消去ブロック、あるいは専用のアドレス領域が割り当てられるので、特定の物理領域のみに集中的な書き換えがなされてしまう。そのため、書き換え疲労が加速され、寿命が低下するという不利益があった。
またその読み出しや書き込みには専用の管理が施され、ユーザーデータのような迅速なアクセスは困難であった。したがって、そのために多くの操作が追加され、煩雑な上、テーブルの入れ替えにも時間がかかるという不利益があった。
【００３２】
また、上述の如く、テーブル入れ替えに伴う書き換え疲労と所要時間は深刻な問題であり、従来は頻繁なテーブル入れ替え自体が前提とされていなかった。すなわち、大容量のストレージに対処すべく、やむを得ずテーブルを分割していたに過ぎない。
したがって、分割数は最小限に留め、一塊の大きな連続アドレス領域をＲＡＭ上のテーブルでカバーして、通常のユーザーアクセスはその範囲に留まることが期待されていた。
すなわち、アドレステーブルを展開したＲＡＭはキャッシュとして使用されてはいるが、従来のアドレステーブルのキャッシングについては、単なるバッファというべきプリミティブな形態で実施されていたに過ぎず、上述の如く１エントリのみの最も単純なキャッシングが行われるのみであった。また、それらはユーザーデータとは独立したテーブル専用のキャッシュメモリとして使用されていた。
【００３３】
しかし、テーブルが巨大化する中でＲＡＭ容量を減らそうとすれば、テーブル分割数も増加するので、そのような単純なキャッシュではミスヒットが多発して効率が悪くなるという不利益がある。
さらに、このようなキャッシュを使用した場合、電源瞬断が発生した際にキャッシュ内のテーブル更新内容が消失し、その回復には非常に時間がかかるという不利益がある。
【００３４】
本発明は、アドレス変換を用いたユーザーデータの効率的な管理手法を、フラッシュメモリ上のアドレステーブルの操作にもそのまま適用することが可能になり、アドレステーブルの迅速かつ柔軟なアクセスが実現でき、特定消去ブロックへの書き換えの集中も防止でき、アドレステーブルの管理や操作もシンプルとなる記憶装置、コンピュータシステム、および記憶装置のアクセス方法を提供することにある。
【課題を解決するための手段】
【００３５】
本発明の第１の観点の記憶装置は、アドレステーブルと、キャッシュメモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、上記キャッシュメモリ上に展開される。
【００３６】
本発明の第２の観点の記憶装置は、第１のアドレステーブルと、第２のアドレステーブルと、メモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記第１のアドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記第１のアドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記メモリ上に展開され、上記第２のアドレステーブルにおいては、初期論理アドレスに対応する上記小アドレステーブルの上記フラッシュメモリデバイス上の所在情報が取得され、上記小アドレステーブルがフラッシュメモリに保存される際には、上記第２のアドレステーブル上の、上記小アドレステーブルに対応する所在情報が、同時並列的に更新され、上記第２のアドレステーブルの更新箇所を示す情報が、フラッシュメモリ上に保存される小アドレステーブルを含むデータグループ内の予備領域に同時に保存される。
【００３７】
本発明の第３の観点の記憶装置は、第１のアドレステーブルと、第２のアドレステーブルと、メモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記第１のアドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記第１のアドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記メモリ上に展開され、上記第２のアドレステーブルにおいては、初期論理アドレスに対応する上記小アドレステーブルの上記フラッシュメモリデバイス上の所在情報が取得され、上記第２のアドレステーブルは、不揮発性ＲＡＭに格納されている。
【００３８】
本発明の第４の観点の記憶装置は、アドレステーブルと、キャッシュメモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該小アドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記キャッシュメモリに展開され、上記キャッシュメモリには複数のエントリが登録でき、ユーザーデータが格納された第１のエントリと、上記小アドレステーブルが格納された第２のエントリとが、混在して登録されている。
【００３９】
本発明の第５の観点の記憶装置は、記憶媒体であるフラッシュメモリデバイスと、制御回路と、を有し、上記制御回路は、ホストから入力されたユーザーデータと、当該記憶装置内部で生成され、使用される管理用データの双方をフラッシュメモリに保存し、上記ユーザーデータと管理用データは、各々複数の格納領域をフラッシュメモリデバイス上に動的に確保され、それらの領域は互いに混在して存在している。
【００４０】
本発明の第６の観点の記憶装置は、アドレステーブルと、メモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、を有し、上記制御回路は、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記メモリ上に展開され、上記小アドレステーブルの格納領域は、上記フラッシュメモリデバイスの一括消去単位であるブロック領域ごとに、ユーザーデータが格納されたブロックと混在して動的に確保され、各ブロック領域には複数の小アドレステーブルが格納される。
【００４１】
本発明の第７の観点のコンピュータシステムは、アドレステーブルと、キャッシュメモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、上記フラッシュメモリデバイスのユーザーデータにアクセス可能な処理装置と、を有し、上記制御回路は、上記処理装置が上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、上記キャッシュメモリ上に展開される。
【００４２】
本発明の第８の観点のコンピュータシステムは、アドレステーブルと、キャッシュメモリと、ユーザーデータの記憶媒体であるフラッシュメモリデバイスと、上記フラッシュメモリデバイスのアクセス管理を行う制御回路と、上記フラッシュメモリデバイスのユーザーデータにアクセス可能な処理装置と、を有し、上記制御回路は、上記処理装置が上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該小アドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記キャッシュメモリに展開され、上記キャッシュメモリには複数のエントリが登録でき、ユーザーデータが格納された第１のエントリと、上記小アドレステーブルが格納された第２のエントリとが、混在して登録されている。
【００４３】
本発明の第９の観点は、フラッシュメモリデバイスのユーザーデータにアクセスする記憶装置のアクセス方法であって、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該分割されたアドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、キャッシュメモリ上に展開される。
【００４４】
本発明の第１０の観点は、フラッシュメモリデバイスのユーザーデータにアクセスする記憶装置のアクセス方法であって、上記フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行い、上記アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、当該インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得され、上記アドレステーブルの全体は、上記インデックスの領域ごとに複数の小アドレステーブルに分割されており、当該小アドレステーブルは上記フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、キャッシュメモリに展開され、上記キャッシュメモリには複数のエントリが登録でき、ユーザーデータが格納された第１のエントリと、上記小アドレステーブルが格納された第２のエントリとが、混在して登録される。
【００４５】
本発明によれば、制御回路は、フラッシュメモリデバイスのデータにアクセスする際、アクセスはアドレステーブルを介して行う。そして、アドレステーブルにおいては、初期論理アドレスより生成されたアドレス値をインデックスとして、インデックスに対応するフラッシュメモリデバイス上のユーザーデータの所在情報が取得される。そして、アドレステーブルの全体は、インデックスの領域ごとに複数の小アドレステーブルに分割されている。この分割されたアドレステーブルは、フラッシュメモリデバイス内に格納され、ユーザーデータがアクセスされる際、必要に応じて読み出され、上記小アドレステーブルをエントリとして、キャッシュメモリ上に展開される。
【発明の効果】
【００４６】
本発明によれば、アドレス変換を用いたユーザーデータの効率的な管理手法を、フラッシュメモリ上のアドレステーブルの操作にもそのまま適用することが可能になり、アドレステーブルの迅速かつ柔軟なアクセスが実現でき、特定消去ブロックへの書き換えの集中も防止でき、アドレステーブルの管理や操作もシンプルとなる利点がある。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の実施形態を図面に関連付けて説明する。
【００４８】
図５は、本発明の第１の実施形態に係る記憶装置を採用したコンピュータシステムの構成例を示す図である。
【００４９】
本コンピュータシステムＣＯＭＳＹＳは、ファイル記憶装置３０、およびホストシステム（処理装置）５０を主構成要素として有している。
ファイル記憶装置３０は、インターフェース回路（Ｉ／Ｆ）３１、制御回路３２、内部バス３３、ページバッファ３４、ＮＡＮＤ型フラッシュメモリ３５，３６、制御回路３７、およびメモリバス３８を有する。
制御回路３２は、ＲＡＭ４０を含み、ＲＡＭ４０にはテーブルリスト４１、アドレステーブル４２、および検索テーブル４３を有する。
ホストシステム５０は、ＣＰＵ、ＲＡＭ、ＲＯＭ、システムバス等を含んで構成されている。
【００５０】
ファイル記憶装置３０の内部においては、３２ビットのメモリバス３８に、１６ビットの入出力を持つ２チップの８ＧｂＮＡＮＤ型フラッシュメモリ（フラッシュメモリチップという場合もある）３５，３６が並列接続されている。２つのチップは読み出しや書き込みにおいて、同時並列にアクセスされる。すなわち、メモリバス３８は１６ビットバスを２チャンネル備えた構成となっている。各々のフラッシュメモリは書き込みや読み出しのアクセスをたとえば４ｋＢのページ単位で行う。したがって、実ページサイズとしては８ｋＢが一括アクセスされることになる。
また後述するように、簡単のため各々のフラッシュメモリチップは、たとえば消去を１ＭＢの消去ブロック単位で行い、各ブロックは２５６個のページを含むとする。この時実消去ブロックサイズとしては２ＭＢが一括消去されることになり、実消去ブロックは２５６個の実ページにより構成される。
ページバッファ３４はアクセスされたページ領域のデータを一時記憶する。フラッシュメモリ３５，３６とページバッファ３４との間のデータの送受は、制御回路３７で制御されている。
さらに、制御回路３７は、必要に応じて転送データにＥＣＣ符号化によるエラー補正を施したり、フラッシュメモリ内の欠陥ブロックの管理を実施する。両フラッシュメモリ３５，３６は，ページバッファ３４を介して記憶装置の内部バス３３との間でデータを入出力する。
すなわち、ページバッファ３４、ＮＡＮＤ型フラッシュメモリ３５，３６、制御回路３７、およびメモリバス３８の回路群は実質的に一つのフラッシュメモリデバイス（フラッシュメモリモジュールという場合もある）３９を構成し、記憶装置の内部バス３３に接続されているとみなすことができる。その総容量は１６Ｇｂ（２ＧＢ）であり、実ページサイズは８ｋＢである。すなわち装置内には２５６ｋ個のページデータが格納される。
【００５１】
さらに、内部バス３３にはインターフェース回路３１、および制御回路３２が接続されている。
インターフェース回路３１は、ＡＴＡやＰＣＩエクスプレス等の規格に従ってホストシステム５０との間で、データやコマンドの送受を行う。
制御回路３２は、記憶装置の内部においてページバッファ３４とインターフェース回路３１の間のデータの送受を管理する。
制御回路３２に内蔵されたＲＡＭ４０には、プログラムを実行するためのコードエリアやワーキングエリアが設けられており、さらにページ単位の仮想アドレスを管理するアドレステーブル４２、アドレステーブルを管理するテーブルリスト４１、およびデータ書き込みのために適切な空きページを検索するための検索テーブル４３が構築されている。
【００５２】
本コンピュータシステムＣＯＭＳＹＳにおいては、ホストシステム５０は内蔵するＣＰＵによって制御され、アプリケーションやオペレーティングシステム（ＯＳ）の要求に応じて、ファイル記憶装置３０を介して、フラッシュメモリデバイス３９にユーザーデータを保存する。
制御回路３２はその間のデータ授受に介在し、テーブルリスト４１やアドレステーブル４２等を用いてアドレス変換を伴うアクセス管理を実施する。
【００５３】
ファイル記憶装置３０は、ハードディスクと同様に５１２バイト（Ｂｙｔｅ）のセクタをアクセス単位とする。
記憶装置内部では簡単のため、１６進数のアドレスが次のように割り振られるとする。
たとえば、外部入力アドレスが“０ｘ０５５０２Ｃ”であった場合、上位２０ビットの“０ｘ０５５０２”はページアドレスであり、最大１Ｍページを管理できる。一方、下位４ビットの“０ｘＣ”はページ領域内のセクタアドレスであり、１ページ中には１６のセクタが含まれる。
本記憶装置はページバッファ３４内のデータを選択することで、１セクタ単位のランダムアクセスが可能である。
【００５４】
本実施形態においては、ページ単位の仮想アドレス管理が採用されている。
図６（Ａ）〜（Ｃ）は、第１の実施形態に係るテーブルリスト４１、アドレステーブル４２、および検索テーブル４３の構成例を示す図である。また、図７は、第１の実施形態に係るテーブルリスト４１、アドレステーブル４２、および検索テーブル４３を使用したデータアクセスを示すフローチャートである。
ファイル記憶装置３０の内部におけるフラッシュメモリモジュール３９への具体的アクセスは、図７のフローチャートに従って、以下のような手順で実行される。
【００５５】
ステップＳＴ１：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、制御回路３２はまずその上位アドレスを受けて内蔵ＲＡＭ４０にアクセスし、そこに常駐するテーブルリスト４１から、対応するアドレステーブル４２の所在情報を取得する。
テーブルリスト４１に設けられたテーブルインデックス（Ｔ−Ｉｎｄｅｘ）は２ｋページ分の論理ページアドレス領域ごとに分割されており、ここではセクタアドレスの上位ビット“００００＿０１０１＿０１０１” （“０ｘ０５５”の二進数表記）中の“００００＿０１０１＿０”までがインデックスとして使用される。すなわち“０ｘ０５０”のインデックスに対応するアドレステーブルの所在を示す物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。
【００５６】
ステップＳＴ２：
上記物理ページアドレスをもって、フラッシュメモリモジュール３９がアクセスされ、ページバッファ３４内にアドレステーブルが格納されたページグループが読み出される。これがＲＡＭ４０上に展開されて、アドレステーブル４２が構築される。
アドレステーブル４２は各論理ページアドレスＬＰＡに対応して４バイトの（３２ビット）情報を保持しており、その内２０ビットがフラッシュメモリモジュール上の物理ページアドレスＰＰＡである。残りのビットには、たとえば更新時のタイムスタンプや更新回数等、履歴情報等が格納されている。
前述の如く、１アドレステーブルは２ｋページ分の論理ページアドレスをカバーする。したがって、その総容量は（４バイト  ｘ  ２ｋ  ＝  ８ｋバイト）となり、一括書き込み単位である１ページ分の容量に相当する。
【００５７】
ステップＳＴ３：
次に、再度セクタの論理アドレス“０ｘ０５５０２Ｃ”より、論理ページアドレス部ＬＰＡ“０ｘ０５５０２”をインデックスにアドレステーブル４２が参照され、アクセス対象たるユーザーデータの物理ページアドレスＰＰＡ“０ｘ０６０Ｂ０”が取得される。
【００５８】
ステップＳＴ４：
上記物理ページアドレスＰＰＡをもって、再度フラッシュメモリモジュール３９がアクセスされ、ページバッファ３４内にユーザーデータが格納されたページグループが読み出される。この操作はステップＳＴ２におけるアドレステーブルの読み出し時と全く同様であり、統一した管理で実施することができる。
その後セクタアドレス“０ｘＣ”に相当する部分がページバッファ３４から選択的にホストシステム５０側に出力され、読み出し動作が完了する。
【００５９】
さらに、データの更新は以下のように実施する。同じ“０ｘ０５５０２Ｃ”のセクタを更新するとする。その場合、まずページバッファ３４に所望のページを読み出す必要があり、その手順はステップＳＴ１〜ステップＳＴ４と同様である。
【００６０】
ステップＳＴ１〜ＳＴ４：
読み出し時と同様に、フラッシュメモリモジュール３９より読み出した所望のデータをページバッファ３４に格納する。
【００６１】
ステップＳＴ５：
ページバッファ３４上で所望のセクタ箇所を更新する。
【００６２】
ステップＳＴ６：
更新したユーザーデータのフラッシュメモリモジュール３９への書き込み先として、ＲＡＭ４０内に常駐した検索テーブル４３から、適当なページ領域の物理ページアドレスＰＰＡが選択される。ここでは簡単のため、物理ページアドレスは、上位１２ビットの物理ブロックアドレス部（Ｐｈｉｓｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ  ：ＰＢＡ）と下位８ビットのページオフセット部よりなるとする。この時各消去ブロックは２５６ページ（２８）より構成される。
検索テーブル４３には、各ブロックごとに、内部に含まれるページの有効／無効がフラグとして格納されている。後述するように、ページが無効化されると対応するフラグに“１”が立つ。さらに各ブロックが現在使用されているか、もしくは消去済みの空き状態であるかが、“Ｕｓｅｄ  Ｆｌａｇ”でマークされている。
データの書き込みは、消去済みブロックの先頭ページから順に実行されていく。前回の書き込んだページの物理アドレスは、レジスタ４４に保存されており、書き込み先にはそれがインクリメントされたページが順次選択される。選択がブロックの末尾に達したら、それ以降のブロックの“Ｕｓｅｄ  Ｆｌａｇ”がスキャンされ、次の未使用ブロックが検出されて、その先頭ページが選択される。
レジスタ４４の値は現在“０ｘ０ＡＡ０１”であり、制御回路３２はまずユーザーデータの書き込み先として、それをインクリメントした物理ページアドレス“０ｘ０ＡＡ０２”を選択する。
【００６３】
ステップＳＴ７：
上記物理ページアドレスＰＰＡをもって、フラッシュメモリモジュール３９がアクセスされ、ページバッファ３４内のユーザーデータがフラッシュメモリモジュールに一括書き込みされる。書き込みが完了すると、アドレステーブル４２が更新され、論理ページアドレスＬＰＡ“０ｘ０５５０２”に対応する物理ページアドレスＰＰＡは“０ｘ０ＡＡ０２”に更新される。また、旧物理ページアドレス“０ｘ０６０Ｂ０”に相当するページ領域は無効となり、検索テーブル４３の対応するページのフラグが“１”に変わる。
【００６４】
ステップＳＴ８：
さらに、アドレステーブル４２の更新は、フラッシュメモリモジュール上にも反映される必要がある。この際アドレステーブルのフラッシュメモリモジュールへの書き込み先として、検索テーブル４３から、再度適当な空きページ領域の物理ページアドレスＰＰＡが選択される。
すなわち、ステップＳＴ６に示されたユーザーデータの更新と同様に、レジスタ４４の値がインクリメントされ、物理ページアドレス“０ｘ０ＡＡ０３”が選択される。
【００６５】
ステップＳＴ９：
上記物理ページアドレスをもって、フラッシュメモリモジュール３９が再度アクセスされる。まずアドレステーブル４２はＲＡＭ４０からページバッファ３４にコピー転送され、さらにページグループとしてフラッシュメモリモジュールに一括書き込みされる。
書き込みが完了すると、テーブルリスト４１が更新され、テーブルインデックス（Ｔ−Ｉｎｄｅｘ）“０ｘ０５０”に対応する物理ページアドレスＰＰＡは“０ｘ０ＡＡ０３”に更新される。また、旧物理ページアドレス“０ｘ０３０Ｂ０”に相当するページ領域は無効となり、検索テーブル４３の対応するページのフラグが“１”に変わる。
【００６６】
上記手順を要約すれば、以下のようになる。
１．テーブルリスト４１から取得した所在情報をもとに、フラッシュメモリモジュール３９からアドレステーブル４２を取得する（ステップＳＴ１，ＳＴ２）。
２．アドレステーブル４２から取得した所在情報をもとに、フラッシュメモリモジュール３９からユーザーデータを取得する（ステップＳＴ３，ＳＴ４）。
３．ページバッファ３４上でユーザーデータを更新する（ステップＳＴ５）。
４．フラッシュメモリモジュールの空き領域へユーザーデータを格納し、アドレステーブル４２を更新する（ステップＳＴ６，ＳＴ７）。
５．フラッシュメモリモジュールの空き領域へアドレステーブル４２を格納し、テーブルリスト４１を更新する（ステップＳＴ８，ＳＴ９）。
【００６７】
上述の如く、アドレステーブル４２のフラッシュメモリモジュール３９からの読み出し取得、および書き込み格納は、いずれもユーザーデータと同形式または互換形式の所在情報（ここでは物理ページアドレス）をもとに、同じデータサイズ（ここでは一括書き込みの単位である８ｋバイトのページグループ）を単位として実施されている。また、前者のページグループと後者のページグループは、フラッシュメモリモジュール内に順不同に混在して格納されている。たとえば、上記ステップＳＴ７およびＳＴ９では、ＰＢＡ“０ｘ０ＡＡ”に相当する消去ブロック内に、ユーザーデータとアドレステーブル４２がページグループ単位で相次いで書き込まれており、両者は同一の消去ブロックに混在して格納されている。
このような構成を取った結果、制御回路３２は両者を統一的に管理することが可能となり、アドレステーブル４２はユーザーデータと同様に柔軟かつ迅速にアクセスできるようになった。
【００６８】
ところで、本実施形態のコンピュータシステムにおいて、たとえばファイル記憶装置３０がモバイルメディアの場合、急な引き抜き等の電源瞬断に対する耐性が必要となる。また組み込み型であっても、コンピュータ機器そのものの電源瞬断に備える必要がある。
このようなケースでは、特にＲＡＭ４０がＳＲＡＭやＤＲＡＭの場合、そこに常駐するテーブルリスト４１の消失が問題となる。以下にその対策を述べる。
【００６９】
まず、ステップＳＴ９において、アドレステーブル４２をフラッシュメモリ３５，３６に書き込む際には、データに予備領域を設けておき、そこに対応するテーブルリスト４１上のテーブルインデックスを格納しておくことが望ましい。これはアドレステーブル４２のフラッシュメモリへの書き込みに伴う、テーブルリストの更新箇所の情報に相当する。
これによって、たとえばアドレステーブルの物理ページアドレスＰＰＡが与えられれば、フラッシュメモリ内に格納されたアドレステーブルにアクセスし、対応するテーブルインデックス（Ｔ−Ｉｎｄｅｘ）が取得できる。すなわち、テーブルリストの逆引きが可能である。
これにより、テーブルリストが事故的に消失した際には、物理ページアドレスをスキャンして各ページグループを読み出すことで、各アドレステーブルにおける物理ページアドレスとテーブルインデックス（Ｔ−Ｉｎｄｅｘ）の関係を調べ、テーブルリスト４１を再構築することが可能である。
また、そのような再構築のケースを想定した場合、予備領域にはテーブルインデックスとともにタイムスタンプ等の履歴情報を格納し、同じテーブルインデックスが格納されていた場合にどちらが新しいアドレステーブルであるか、判別できるようにしておくことが望ましい。
【００７０】
ただし、フラッシュメモリモジュールの容量が巨大化し、ページ数が増えてくると、スキャンに多大な時間が消費されるようになる。したがって、このようなバックアップのみではなく、より簡便な対策が望まれる。そのようなケースでは、強誘電体メモリ等の不揮発性ＲＡＭの使用が有効である。
すなわち、ＲＡＭ４０の少なくとも一部を不揮発性ＲＡＭで構成し、そこにテーブルリスト４１を常駐させておけば、電源瞬断による消失からは完全に保護することが可能である。
【００７１】
なお、不揮発性ＲＡＭとしては、強誘電体膜を用いたＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  ＲＡＭ）、強磁性体を用いたＭＲＡＭ（Ｍａｇｎｅｔｉｃ  ＲＡＭ）や、相変化材料を用いたＯＵＭ（Ｏｖｏｎｉｃ  Ｕｎｉｆｉｅｄ  Ｍｅｍｏｒｙ）、ＲＲＡＭ等が提案されている。
ＦｅＲＡＭは強誘電体キャパシタの分極方向の違いでデータを記憶する半導体メモリである。たとえばＵＳＰ４８７３６６４においてＳ．Ｓｈｅｆｆｅｉｅｌｄらがその一形態を提案している。
【００７２】
ＭＲＡＭは強磁性膜のスピン方向の違いでデータを記憶する半導体メモリである。たとえばＩＳＳＣＣ２０００の論文ダイジェストの１２８ページに、Ｒ．Ｓｃｈｅｕｅｒｌｅｉｎらが論文を掲載している。
ＯＵＭはたとえばカルコゲナイド膜の相転移でデータを記憶する半導体メモリである。たとえばＩＥＤＭ２００１の論文ダイジェストの８０３ページに、Ｓ．Ｌａｉらが論文を掲載している。近年はＰＲＡＭとも呼称されている。
ＲＲＡＭは磁気抵抗効果材料の抵抗ヒステリシスでデータを記憶する半導体メモリである。たとえばＩＥＤＭ２００２の論文ダイジェストの７．５にはＷ．Ｗ．Ｚｈｕａｎｇらが論文を掲載している。
それらの不揮発性メモリは、いずれもセルレベルのアクセス速度や書き換え回数において、フラッシュメモリより数桁性能が高い。
【００７３】
ところで、本実施形態における「フラッシュメモリデバイスのページグループ」との表現は、たとえばフラッシュメモリモジュール３９に一括で書き込みまれる連続データの基本単位を示すが、モジュールが複数チップ３５，３６から構成される場合、各チップへのデータ転送や書き込みのタイミング設定には依存しない。
本実施形態においては、１６ビットＩＯのチップ２個を３２ビットバスに接続することで完全な並列動作としたが、１６ビットのバスを両チップで共有すれば、転送は個々に行なわざるを得ない。その場合、ページバッファ３４から片側のメモリチップにデータを転送している間に、もう片側のメモリチップ内で書き込みをスタートしても良いし、両者への転送を順次行った後に、書き込みを同時スタートしても良い。
すなわち、複数のフラッシュメモリチップ３５，３６、あるいはそれらと制御回路等を含むフラッシュメモリモジュール３９は実質的に一つのフラッシュメモリデバイスとみなすことが可能であり、内部の動作タイミングに関わらず、その一括書き込みの基本単位がページグループと表現されている。
【００７４】
また、上記実施形態では、アドレステーブルやテーブルリストのインデックスには、ホストから与えられた論理アドレスの一部が使用されたが、論理アドレスに特定の変換や演算を施した値、またはその一部が使用されるケースもある。
たとえば、一部のハードディスク用インターフェースでは、初期論理アドレスは上述のようなシリアルなセクタアドレスではなく、シリンダー番号、ヘッド番号、セクタ番号を組み合わせた３次元アドレスで与えられる。インデックスにはその値の一部を使用しても良いが、それをシリアルなセクタアドレスに変換し、その値の一部を使用しても良い。その他初期論理アドレスがどのような形態をとろうとも、それに基づいて一意的に得られた値であれば、インデックスとして使用できる。
【００７５】
また、ここではアドレステーブルやテーブルリストから取得されるページグループの所在情報をフラッシュメモリモジュール３９内の物理ページアドレスとしたが、たとえばここで中間的な所在情報を獲得し、さらにその値に演算や変換を施して物理ページアドレスを取得しても良い。一例としては、欠陥ブロックへのアクセスを避けるため、上述の例で得られたアドレスから、さらにそのブロックアドレス部分に変換を施し、真の物理ページアドレスを取得する等の変形が想定される。
【００７６】
以上、第１の実施形態においては、トータルとして巨大な容量を持つアドレステーブルを、フラッシュメモリモジュール３９内にユーザーデータと同列に混在して格納し、必要に応じて適時迅速にアクセスするための手法を提案した。
【００７７】
次に、本発明の第２の実施形態として、アドレステーブルのキャッシングについて記載する。
【００７８】
第１の実施形態のように、ユーザーデータにアクセスする都度にフラッシュメモリにアクセスし、アドレステーブルの操作を行うと、それ自体が高速であっても、データアクセスには無視し得ぬオーバーヘッドが発生する。したがって、上記ＲＡＭ４０の領域をアドレステーブルのキャッシュメモリとして確保し、フラッシュメモリモジュール３９への直接的なアクセス回数を低減することが望ましい。
また、キャッシュされたアドレステーブルの更新時には更新の都度にその結果をフラッシュメモリに反映させるライトスルー方式ではなく、たとえばエントリ開放の際にまとめて反映させるライトバック方式を採用した方が効率が良い。
さらに、そのようなキャッシュには単一エントリではなく、複数のアドレステーブルをエントリとして格納し、キャッシュテーブルを用いた高度なキャッシュ管理を導入することが望ましい。それによって高いヒット率を獲得し、上記オーバーヘッドは殆ど消失させることが可能になる。
【００７９】
図８は、本発明の第２の実施形態に係る記憶装置を採用したコンピュータシステムの構成例を示す図である。図８は、アドレステーブルのキャッシュメモリを導入した実施形態を示す。
ハードウエア構成は、図５に示した第１の実施形態と同様であるが、内蔵ＲＡＭ４０Ａにはテーブルリスト４１）、複数のアドレステーブル４２＿０，４２＿１・・・、検索テーブル４３に加え、キャッシュテーブル４５が構築されている。アドレステーブル４２＿０，４２＿１・・・の個々の構成、および検索テーブル４３は図６に示した第１の実施形態と同様である。
【００８０】
図９（Ａ），（Ｂ）は、第２の実施形態において、アドレステーブルをアクセスするための、アドレスインデックスとキャッシュテーブルの一例を示す図である。また、図１０は、第２の実施形態に係るデータアクセスのフローチャートである。
ファイル記憶装置３０Ａの内部におけるフラッシュメモリモジュール３９への具体的アクセスは、図１０のフローチャートに従って、以下のような手順で実行される。
【００８１】
ステップＳＴ１１：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、制御回路３２はまずその上位アドレスを受けて内蔵ＲＡＭ４０Ａにアクセスし、そこに常駐するテーブルリスト４１から、対応するアドレステーブルの所在情報を取得する。第１の実施形態と同様に、論理アドレスの上位９ビットが使用されて、“０ｘ０５０”のテーブルインデックスに対応するアドレステーブルの所在を示す物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。
【００８２】
ステップＳＴ１２：
上記物理ページアドレスＰＰＡをもとに、キャッシュテーブル４５が検索され、キャッシュへのヒットの有無が検査される。キャッシュテーブル４５はそれぞれがＲＡＭ４０Ａ内の所定の格納領域に対応した８つのエントリを持っている。エントリは先入先出しのラウンドロビン方式で管理され、新規エントリは末尾に追加される。エントリの先頭と末尾はそれぞれレジスタ４６および４７で管理されている。
なお、図９（Ａ），（Ｂ）の例では、物理ページアドレス“０ｘ０３０Ｂ０”はいずれのエントリの物理ページアドレスフィールドＰＰＡにも一致していない。したがって、所望のアドレステーブルはＲＡＭ４０Ａ内には存在しておらず、キャッシュミスが発生している。
【００８３】
ステップＳＴ１３：
キャッシュミスした場合、フラッシュメモリモジュール３９から所望のアドレステーブルが読み出され、内蔵ＲＡＭ４０Ａ内の空き領域に展開される。この際、以下のような手順でＲＡＭ内の空き領域が確保され、アドレステーブルが展開される。
＜＜既存エントリの開放＞＞
ステップＳＴ１３１：
キャッシュテーブル４５において、レジスタ４６，４７を参照すると、末尾エントリは“０”、先頭エントリはその直後の“１”となっている。すなわちエントリに空きが無いことが解る。
ステップＳＴ１３２〜ＳＴ１３４：
まず先頭エントリ“１”を開放するため、そこに格納されたアドレステーブルをフラッシュメモリモジュール３９に書き戻す。この際の手順は第１の実施形態における（図７のステップＳＴ８，ＳＴ９）と同様であり、検索テーブル４３から空き領域の物理ページアドレスを取得して、そこに書き込みを行った後、テーブルリスト４１の対応箇所を更新する。なお、キャッシュ上のアドレステーブルにもデータ予備領域を設け、対応するテーブルリスト上のテーブルインデックス（Ｔ−Ｉｎｄｅｘ）を格納しておくと、更新すべき箇所が瞬時に確定できる。しかる後にエントリが開放され、先頭エントリレジスタ４６の値は“２”にインクリメントされる。
＜＜アドレステーブルの展開＞＞
ステップＳＴ１３５：
フラッシュメモリモジュール３９より物理ページアドレス“０ｘ０３０Ｂ０”のページを読み出して、ＲＡＭ４０Ａのエントリ“１”で指定された領域に展開する。この際、新たにエントリ“１”が追加される。これに伴って末尾エントリレジスタ４７の値は“１”にインクリメントされる。キャッシュテーブル４５上のエントリ“１”に対応する物理ページアドレスは“０ｘ０３０Ｂ０”に更新される。
【００８４】
ステップＳＴ１４：
内蔵ＲＡＭ４０Ａに展開されたアドレステーブルのキャッシュデータから、論理ページアドレス“０ｘ０５５０２”に対応するユーザーデータの物理ページアドレスを取得する（ＳＴ１４１）。それを元にフラッシュメモリモジュール３９より所望のユーザーデータが格納されたページグループをページバッファ３４に読み出し（ＳＴ１４２）、それを介したデータアクセスが可能になる。この手順は第１の実施形態において（図７のステップＳＴ３，ＳＴ４）で例示したものと同じである。
【００８５】
ステップＳＴ１５：
ページバッファ３４上で所望のセクタ箇所を更新する。
【００８６】
ステップＳＴ１６：
ページバッファ３４上のページグループを、フラッシュメモリモジュール３９に書き戻す。この際の手順は第１の実施形態における（図７のステップＳＴ６，ＳＴ７）と同様であり、検索テーブル４３から空き領域の物理ページアドレスＰＰＡを取得して（ＳＴ１６１）、そこに書き込みを行った後、上記アドレステーブルの対応箇所、すなわち論理ページアドレス“０ｘ０５５０２”に対応する物理ページアドレスを、新規書き込み先に更新する（ＳＴ１６２）。
【００８７】
本第２の実施形態においては、アドレステーブルのフラッシュメモリモジュールへの書き戻しを、ステップＳＴ１３のエントリ開放時に初めて実施している。すなわち、ライトバック型のキャッシュ方式を採用している。また、複数のエントリが格納可能となっている。
【００８８】
また、テーブルリスト４１を用いて各アドレステーブルのフラッシュメモリモジュール３９上の位置情報を管理することで、フラッシュメモリモジュール３９へのアドレステーブルの柔軟かつ動的な割り付けと、複雑なキャッシュエントリの管理を両立している。
このような管理は、フラッシュメモリモジュール内にアドレステーブルがユーザーデータと混在し、分散格納される際には特に有効である。しかしそれらが特定の消去ブロックに集約的に格納される場合でも、格納順序等の柔軟性を向上させる上で効果がある。
【００８９】
なお、本実施形態においては、キャッシュの各エントリは、初期論理アドレスからテーブルリスト４１を介して取得された物理ページアドレスで管理されている。すなわち、キャッシュテーブル４５内の各エントリのタグフィールドには、物理ページアドレスＰＰＡが格納されている。
【００９０】
また、キャッシュおよびフラッシュメモリモジュール内に格納された各々のアドレステーブルには予備のデータ領域が存在しており、そこには各アドレステーブルに対応した、テーブルリスト４１のテーブルインデックス（Ｔ−Ｉｎｄｅｘ）が格納されている。
これによってアドレステーブルの物理ページアドレスＰＰＡが与えられれば、キャッシュまたはフラッシュメモリモジュール内に格納されたアドレステーブルにアクセスし、対応するテーブルインデックス（Ｔ−Ｉｎｄｅｘ）が取得できる。このような逆引き機能があれば、ステップＳＴ１３のエントリ開放時に、開放エントリに対応するインデックスを即座に取得して、テーブルリスト４１を更新することが可能になる。
さらに、第１の実施形態で述べたように、テーブルリストが消失しても、フラッシュメモリモジュール３９に格納された各アドレステーブルをスキャンすることで、それを再構築することができる。
【００９１】
キャッシュメモリおよびフラッシュメモリモジュール３９へのアクセス手順を変えた、第２の実施形態の変形例を第３の実施形態として以下に述べる。
【００９２】
図１１は、第３の実施形態において、アドレステーブルをアクセスするための、アドレスインデックスとキャッシュテーブルの一例を示す図である。また、図１２は、第３の実施形態に係るデータアクセスのフローチャートである。
【００９３】
第３の実施形態においては、キャッシュされたテーブルのエントリはテーブルリスト４１ｂのテーブルインデックス（Ｔ−Ｉｎｄｅｘ）に対応する形で管理されている。すなわち、キャッシュテーブル４５ｂ内の各エントリのタグフィールドには、テーブルインデックス（Ｔ−Ｉｎｄｅｘ）が格納されている。
【００９４】
以下、図１２のアクセスのフローチャートに関連付けて第３の実施形態におけるユーザーデータのアクセス手順を説明する。
【００９５】
ステップＳＴ２１，ＳＴ２２：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、まずその上位アドレスからテーブルインデックス“０ｘ０５０”が生成され、その値でキャッシュテーブル４５ｂが検索されて、キャッシュへのヒットの有無が検査される。
キャッシュテーブル４５ｂはそれぞれがＲＡＭ４０Ａ内の所定の格納領域に対応した８つのエントリを持っている。エントリは先入先出しのラウンドロビン方式で管理され、新規エントリは末尾に追加される。エントリの先頭と末尾はそれぞれレジスタ４６ｂおよび４７ｂで管理されている。
なお、図１１の例では、テーブルインデックス“０ｘ０５０”はいずれのエントリのテーブルインデックスフィールド（Ｔ−Ｉｎｄｅｘ）にも一致していない。したがって、所望のアドレステーブルはＲＡＭ４０Ａ内には存在しておらず、キャッシュミスが発生している。
【００９６】
ステップＳＴ２３：
キャッシュミスした場合、フラッシュメモリモジュール３９から所望のアドレステーブルが読み出され、内蔵ＲＡＭ４０Ａ内の空き領域に展開される。この際以下のような手順でＲＡＭ内の空き領域が確保され、アドレステーブルが展開される。
＜＜既存エントリの開放＞＞
ステップＳＴ２３１：
キャッシュテーブル４５ｂにおいて、レジスタ４６ｂ，４７ｂを参照すると、末尾エントリは“０”、先頭エントリはその直後の“１”となっている。すなわち、エントリに空きが無いことが解る。
ステップＳＴ２３２〜ＳＴ２３４：
まず先頭エントリ“１”を開放するため、そこに格納されたアドレステーブルをフラッシュメモリモジュール３９に書き戻す。この際の手順は第１の実施形態における（図７のステップＳＴ８，ＳＴ９）と同様であり、検索テーブル４３から空き領域の物理ページアドレスＰＰＡを取得して、そこに書き込みを行った後、テーブルリスト４１ｂの対応箇所、すなわちテーブルインデックス“０ｘ０２０”に対応した所在情報を更新する。しかる後にエントリが開放され、先頭エントリレジスタ４６ｂの値は“２”にインクリメントされる。
＜＜アドレステーブルの展開＞＞
ステップＳＴ２３５：
しかる後に、テーブリスト４１ｂのテーブルインデックス“０ｘ０５０”がアクセスされ、対応する物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。
ステップＳＴ２３６：
フラッシュメモリモジュール３９より物理ページアドレス“０ｘ０３０Ｂ０”のページを読み出して、ＲＡＭ４０Ａのエントリ“１”で指定された領域に展開する。この際、新たにエントリ“１”が追加される。これに伴って、末尾エントリレジスタ４７ｂの値は、“１”にインクリメントされる。キャッシュテーブル４５ｂ上のエントリ“１”に対応するテーブルインデックスは“０ｘ０５０”に更新される。
【００９７】
ステップＳＴ２４：
内蔵ＲＡＭ４０Ａに展開されたアドレステーブルのキャッシュデータから、論理ページアドレス“０ｘ０５５０２”に対応するユーザーデータの物理ページアドレスＰＰＡを取得する（ＳＴ２４１）。それを元にフラッシュメモリモジュール３９より所望のユーザーデータが格納されたページグループをページバッファ３４に読み出し（ＳＴ２４２）、それを介したデータアクセスが可能になる。この手順は第１の実施形態において（図７のステップＳＴ３，ＳＴ４）で例示したものと同じである。
【００９８】
ステップＳＴ２５：
ページバッファ３４上で所望のセクタ箇所を更新する。
【００９９】
ステップＳＴ２６：
ページバッファ上のページグループを、フラッシュメモリモジュール３９に書き戻す。この際の手順は第１の実施形態における（図７のステップＳＴ６，ＳＴ７）と同様であり、検索テーブル４３から空き領域の物理ページアドレスＰＰＡを取得して（ＳＴ２６１）、そこに書き込みを行った後、上記アドレステーブルの対応箇所、すなわち論理ページアドレス“０ｘ０５５０２”に対応する物理ページアドレスを、新規書き込み先に更新する（ＳＴ２６２）。
【０１００】
なお、上記第３の実施形態においては、ステップＳＴ２３のエントリ開放の際、開放すべきエントリのテーブルインデックスは、キャッシュテーブル４５ｂより直接に取得できるので、テーブルリスト４１ｂの逆検索は不要である。
【０１０１】
ところで、アドレステーブルをライトバック方式でキャッシュする場合、キャッシュに無いアドレステーブルは全てフラッシュメモリに保存されているが、キャッシュ上のアドレステーブルのみはその更新がフラッシュメモリに直ちに反映しておらず、消失の危険にさらされる。
アドレステーブルをバックアップするためには、通常はユーザーデータを保存する際、その予備領域にアドレステーブル４２＿ｎ上の対応するインデックスたる論理ページアドレスＬＰＡを同時に保存する。これにより、電源瞬断でアドレステーブルが破壊されても、フラッシュメモリモジュール内の全物理ページアドレスをスキャンすることで、物理ページアドレスと論理ページアドレスとの対応を取得して、アドレステーブルを再構築できる。
ただし、フラッシュメモリモジュールの容量が巨大化し、ページ数が増えてくると、スキャンに多大な時間が消費されるようになる。したがって、このようなバックアップのみではなく、より簡便な対策が望まれる。
【０１０２】
そのようなケースでは、強誘電体メモリ等の不揮発性ＲＡＭの使用が有効である。
すなわちＲＡＭ４０Ａの少なくとも一部を不揮発性ＲＡＭで構成し、その領域をアドレステーブルのキャッシュに使用すれば、全アドレステーブルを電源瞬断から完全に保護できる。なお、第１の実施形態においても述べたように、テーブルリスト４１についても、不揮発性ＲＡＭ内に格納しておくことが望ましい。さらにキャッシュテーブル４５、検索テーブル４３も不揮発性ＲＡＭ内に格納しておけば、システムの主要情報は完全に保存され、電源瞬断からも瞬時の復帰が可能である。
【０１０３】
以上、第２および第３の実施形態においては、アドレステーブルのキャッシングについて述べた。
【０１０４】
次に、本発明の第４の実施形態として、アドレステーブルとユーザーデータを混在させたキャッシュアーキテクチャーについて記載する。
【０１０５】
第１の実施形態においては、フラッシュメモリモジュール上にユーザーデータとアドレステーブルを同列に混在させて格納し、統一的に管理した。これと類似した概念で、キャッシュメモリ上においてもユーザーデータとアドレステーブルを同列のエントリとして混在させて格納し、統一的に管理することができる。
【０１０６】
そのような例を以下に述べる。
ハードウエアの構成例は図８に示した第２および第３の実施形態と同様である。
【０１０７】
図１３（Ａ）〜（Ｃ）は、第４の実施形態に係るテーブルリスト、アドレステーブル、およびキャッシュテーブルの例を示す図である。また、図１４は、第４の実施形態に係るデータアクセスのフローチャートである。
【０１０８】
キャッシュテーブル４５ｃ上には、エントリとしてアドレステーブルとユーザーデータを混在させて登録できる。本例の場合、両者のタグは物理ページアドレスＰＰＡで統一されており、この値を用いてキャッシュメモリ、さらにはフラッシュメモリに全く同列にアクセスできる。
これにより、ユーザーデータとアドレステーブルの管理は統一され、単純化される。さらに両者の違いに関わらず、最も使用頻度の高いものを優先してキャッシングでき、ＲＡＭの有効活用が可能である。
【０１０９】
以下、図１４のアクセスのフローチャートに関連付けて第４の実施形態におけるユーザーデータのアクセス手順を説明する。図１４のステップＳＴ３１〜ＳＴ３４はアドレステーブルの取得であり、ステップＳＴ３５〜ＳＴ３８はユーザーデータの取得である。両者は相似形となっており、統一したアルゴリズムで管理することができる。
【０１１０】
ステップＳＴ３１：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、制御回路３２はまずその上位アドレスを受けて内蔵ＲＡＭ４０Ａにアクセスし、そこに常駐するテーブルリスト４１ｃから、対応するアドレステーブルの所在情報を取得する。第１の実施形態と同様に、論理アドレスの上位９ビットが使用されて、“０ｘ０５０”のテーブルインデックスに対応するアドレステーブルの所在を示す物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。
【０１１１】
ステップＳＴ３２，ＳＴ３３：
上記物理ページアドレスＰＰＡをもとに、キャッシュテーブル４５ｃが検索され、キャッシュへのヒットの有無が検査される。キャッシュテーブル４５ｃはそれぞれがＲＡＭ４０Ａ内の所定の格納領域に対応した８つのエントリを持っている。エントリは先入先出しのラウンドロビン方式で管理され、新規エントリは末尾に追加される。エントリの先頭と末尾はそれぞれレジスタ４６ｃおよび４７ｃで管理されている。
なお、図１４の例では、物理ページアドレス“０ｘ０３０Ｂ０”はいずれのエントリの物理ページアドレスのフィールドＰＰＡにも一致していない。したがって、所望のアドレステーブルはＲＡＭ４０Ａ内には存在しておらず、キャッシュミスが発生している。
【０１１２】
ステップＳＴ３４：
キャッシュミスした場合、フラッシュメモリモジュール３９から所望のアドレステーブルが読み出され、内蔵ＲＡＭ４０Ａ内の空き領域に展開される。この際、必要があればエントリを開放する。一連の手順は第２の実施形態における処理（図１０のステップＳＴ１３）とほぼ同様である。すなわち、以下のような手順でＲＡＭ内の空き領域が確保され、アドレステーブルが展開される。
＜＜既存エントリの開放＞＞
ステップＳＴ３４１：
キャッシュテーブル４５ｃにおいて、レジスタ４６ｃ，４７ｃを参照すると、末尾エントリは“０”、先頭エントリはその直後の“１”となっている。すなわちエントリに空きが無いことが解る。
ステップＳＴ３４２〜ＳＴ３４４：
まず先頭エントリ“１”を開放するため、そこに格納されたデータをフラッシュメモリモジュール３９に書き戻す。ここでアドレステーブルを開放する際には、第１の実施形態の（図７のステップＳＴ８，ＳＴ９）の手順に従う。すなわち、検索テーブル４３から空き領域の物理ページアドレスＰＰＡを取得して、そこに書き込みを行った後、テーブルリスト４１ｃの対応箇所を更新する。一方、ユーザーデータを開放する際には、第１の実施形態の（図７のステップＳＴ６，ＳＴ７）の手順に従う。すなわち、検索テーブル４３から空き領域の物理ページアドレスＰＰＡを取得して、そこに書き込みを行った後、アドレステーブル上の対応箇所を更新する。しかる後にエントリが開放され、先頭エントリレジスタ４６ｃの値は“２”にインクリメントされる。
ところで、開放しようとしたエントリがユーザーデータの場合、対応するアドレステーブルもキャッシュ上に存在している必要がある。これが無いと上記操作に例外が生じ、別途アドレステーブルをフラッシュメモリモジュールより読み出す操作が必要になる。この対策については後述する。
＜＜アドレステーブルの展開＞＞
ステップＳＴ３４５：
フラッシュメモリモジュール３９より物理ページアドレス“０ｘ０３０Ｂ０”のページを読み出して、ＲＡＭ４０Ａのエントリ“１”で指定された領域に展開する。この際新たにエントリ“１”が追加される。これに伴って末尾エントリレジスタ４７ｃの値は“１”にインクリメントされる。キャッシュテーブル４５ｃ上のエントリ“１”に対応する物理ページアドレスは“０ｘ０３０Ｂ０”に更新される。
【０１１３】
ステップＳＴ３５：
内蔵ＲＡＭ４０Ａに展開されたアドレステーブル４２ｃのキャッシュデータから、論理ページアドレス“０ｘ０５５０２”に対応するユーザーデータの物理ページアドレス“０ｘ０６０Ｂ０”を取得する。
【０１１４】
ステップＳＴ３６，ＳＴ３７：
上記物理ページアドレスＰＰＡをもとに、キャッシュテーブル４５ｃが検索され、キャッシュへのヒットの有無が検査される。手順はステップＳＴ３２，ＳＴ３３と同様である。
なお、図１４の例では、物理ページアドレス“０ｘ０６０Ｂ０”はいずれのエントリの物理ページアドレスフィールドＰＰＡにも一致していない。したがって、所望のアドレステーブルはＲＡＭ４０Ａ内には存在しておらず、キャッシュミスが発生している。
【０１１５】
ステップＳＴ３８：
キャッシュミスした場合、フラッシュメモリモジュール３９から所望のユーザーデータが読み出され、内蔵ＲＡＭ４０Ａ内の空き領域に展開される。この際、以下のような手順でＲＡＭ内の空き領域が確保され、アドレステーブルが展開される。
＜＜既存エントリの開放＞＞
ステップＳＴ３８１〜ＳＴ３８４：
上記ステップＳ３４のＳＴ３４１〜ＳＴ３４４の工程と全く同様の手順で先頭エントリ“２”が開放され、先頭エントリレジスタ（４８ｃ）の値は“３”にインクリメントされる。
＜＜ユーザーデータの展開＞＞
ステップＳＴ３８５：
所望のユーザーデータがエントリとして追加される。すなわち、フラッシュメモリモジュール３９より物理ページアドレス“０ｘ０６０Ｂ０”のページを読み出して、ＲＡＭ４０Ａのエントリ“２”で指定された領域に展開する。この際、新たにエントリ“２”が追加される。これに伴って末尾エントリレジスタ４７ｃの値は“２”にインクリメントされる。キャッシュテーブル４５ｃ上のエントリ“２”に対応する物理ページアドレスは“０ｘ０６０Ｂ０”に更新される。
【０１１６】
ステップＳＴ３９：
キャッシュメモリ３４上で所望のユーザーデータの読み出しまたは更新を実施する。
【０１１７】
本発明の第３の実施形態である、アドレステーブルとユーザーデータを混在させたキャッシュアーキテクチャーについて、もうひとつの実施形態を第５の実施形態として以下に述べる。
ハードウエアの構成例は図８に示した第２および第３の実施形態例と同様である。
【０１１８】
図１５（Ａ）〜（Ｃ）は、第５の実施形態に係るテーブルリスト、アドレステーブル、およびキャッシュテーブルの例を示す図である。また、図１６は、第５の実施形態に係るデータアクセスのフローチャートである。
【０１１９】
キャッシュテーブル４５ｄ上には、エントリとしてアドレステーブルとユーザーデータを混在させて登録できる。本例の場合、両者のタグは論理ページアドレスＬＰＡとテーブルインデックス（Ｔ−Ｉｎｄｅｘ）を統合したアドレス値で統一されている。
すなわち、２０ビットの論理ページアドレス中、上位８ビットが“０ｘ４０”に相当する論理ページは本記憶装置には存在しない。したがって、その値を、このエントリがアドレステーブルであることを識別するフラグとし、下位１２ビットにテーブルインデックスを挿入した。この値を用いてキャッシュメモリ、さらにはフラッシュメモリに全く同列にアクセスできる。
【０１２０】
以下、図１６のアクセスのフローチャートに関連付けて第５の実施形態におけるユーザーデータのアクセス手順を説明する。ステップＳＴ４３〜ＳＴ４５はアドレステーブルの取得であり、ステップＳＴ４１，ＳＴ４２，ＳＴ４６はユーザーデータの取得である。両者は相似形となっており、統一したアルゴリズムで管理することができる。
【０１２１】
ステップＳＴ４１，ＳＴ４２：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、まずその上位アドレス“０ｘ０５５０２”からキャッシュテーブル４５ｄが検索され、キャッシュへのヒットの有無が検査される。キャッシュテーブル４５ｄはそれぞれがＲＡＭ４０Ａ内の所定の格納領域に対応した８つのエントリを持っている。エントリは先入先出しのラウンドロビン方式で管理され、新規エントリは末尾に追加される。エントリの先頭と末尾はそれぞれレジスタ４６ｄおよび４７ｄで管理されている。
なお、図１５の例では、論値ページアドレス“０ｘ０５５０２”はいずれのエントリのテーブルインデックスフィールドにも一致していない。したがって、所望のユーザーデータはＲＡＭ４０Ａ内には存在しておらず、キャッシュミスが発生している。
【０１２２】
ステップＳＴ４３，ＳＴ４４：
次にセクタアドレス“０ｘ０５５０２Ｃ”の上位アドレスからテーブルインデックス“０ｘ０５０”が生成され、さらにフラグを追加した検索タグ“０ｘ４００５０”が生成されて、再度キャッシュテーブル４５ｄが検索され、キャッシュへのヒットの有無が検査される。
なお、図１５の例では、検索タグ“０ｘ４００５０”はいずれのエントリのテーブルインデックスフィールドにも一致していない。従って所望のアドレステーブルはＲＡＭ４０Ａ内には存在しておらず、キャッシュミスが発生している。
【０１２３】
ステップＳＴ４５：
キャッシュミスした場合、フラッシュメモリモジュール３９から所望のアドレステーブルが読み出され、内蔵ＲＡＭ４０Ａ内の空き領域に展開される。この際、必要があればエントリを開放する。一連の手順は第３の実施形態における処理（図１２のステップＳＴ２３）とほぼ同様である。すなわち、以下のような手順でＲＡＭ内の空き領域が確保され、アドレステーブルが展開される。
＜＜既存エントリの開放＞＞
ステップＳＴ４５１：
第４の実施形態におけるステップＳＴ３４の工程と全く同様の手順で先頭エントリ“１”が開放され、先頭エントリレジスタ４６ｄの値は“２”にインクリメントされる。
＜＜アドレステーブルの展開＞＞
ステップＳＴ４５２：
しかる後に、テーブリスト４１ｄのテーブルインデックス“０ｘ０５０”がアクセスされ、対応する物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。
ステップＳＴ４５３：
フラッシュメモリモジュール３９より物理ページアドレス“０ｘ０３０Ｂ０”のページを読み出して、ＲＡＭ４０Ａのエントリ“１”で指定された領域に展開する。この際、新たにエントリ“１”が追加される。これに伴って、末尾エントリレジスタ４７ｄの値は、“１”にインクリメントされる。キャッシュテーブル４５ｄ上のエントリ“１”に対応するテーブルインデックスは“０ｘ４００５０”に更新される。
【０１２４】
ステップＳＴ４６：
さらに、フラッシュメモリモジュール３９から所望のユーザーデータが読み出され、内蔵ＲＡＭ４０Ａ内の空き領域に展開される。この際、以下のような手順でＲＡＭ内の空き領域が確保され、アドレステーブルが展開される。
＜＜既存エントリの開放＞＞
ステップＳＴ４６１：
上記ステップＳＴ４５の工程と全く同様の手順で先頭エントリ“２”が開放され、先頭エントリレジスタ４６ｄの値は“３”にインクリメントされる。
＜＜ユーザーデータの展開＞＞
ステップＳＴ４６２：
内蔵ＲＡＭ４０Ａに展開されたアドレステーブルのキャッシュデータから、論理ページアドレス“０ｘ０５５０２”に対応するユーザーデータの物理ページアドレス“０ｘ０６０Ｂ０”を取得する。
ステップＳＴ４６３：
所望のユーザーデータがエントリとして追加される。すなわち、フラッシュメモリモジュール３９より上記物理ページアドレスＰＰＡ“０ｘ０６０Ｂ０”のページを読み出して、ＲＡＭ４０Ａのエントリ“２”で指定された領域に展開する。この際、新たにエントリ“２”が追加される。これに伴って末尾エントリレジスタ４７ｄの値は“２”にインクリメントされる。キャッシュテーブル４５ｄ上のエントリ“２”に対応する論理ページアドレスは“０ｘ０５５０２”に更新される。
【０１２５】
ステップＳＴ４７：
キャッシュメモリ３４上で所望のユーザーデータの読み出しまたは更新を実施する。
【０１２６】
ところで、上述のような第３の実施形態においては、以下の改善すべき点がある。
キャッシュメモリへのエントリ追加に際し、空き領域を確保するために開放しようとしたエントリがユーザーデータであった場合、それらをフラッシュメモリモジュール上に書き戻すには、対応するアドレステーブルの操作が必要になる。
しかし、そのようなテーブルがキャッシュ上に存在しないと、それらを再度フラッシュメモリから取得し、ＲＡＭ上に展開させる必要がある。それを同じキャッシュメモリ内に展開する場合、一旦開放したエントリはそのテーブルで消費され、再度エントリの開放から操作はやり直しとなる。最悪の場合、何度も同じループを繰り返す無駄な操作が発生してしまうおそれがある。
【０１２７】
このような無駄を避けるには、キャッシュ上の全てのユーザーデータに対して、対応するアドレステーブルが同時にキャッシュ上に存在していることを保証することが望ましい。
すなわち、それを保証するように、アドレステーブルの開放順位を操作する。またはそれが保証されるようなキャッシュアルゴリズムを採用する。
【０１２８】
具体例としては、少なくともユーザーデータがキャッシュに追加される際には、対応するテーブルの開放順位が、常にその下位に設定されるようにする。
すなわち、新規データがキャッシュにエントリされる際、必ずアドレステーブルへのアクセスがなされている。しかし、たとえば上述の先入先だしのラウンドロビン方式では、先に読み込まれたアドレステーブルの開放順位が新規データより上位になってしまい、ユーザーデータよりアドレステーブルの方が先に開放されることになる。
これに対して、ユーザーデータが追加された際には、対応するアドレステーブルの開放順位がその下位にくるように、キャッシュテーブルを操作する。あるいはラウンドロビン方式ではなく、先入後だしのスタック方式を採用すれば、自動的にそのような状態が実現される。
【０１２９】
図１７〜図１９は、キャッシュメモリ内の開放優先順位の操作例を示す概念図である。図１７は付け替えによる順位操作例を示し、図１８はスワップによる順位操作例を示し、図１９はスタック方式による順位操作例を示している。
いずれもユーザーデータがキャッシュに追加される際には、対応するテーブルの開放順位が、常にその下位に設定される。
【０１３０】
（操作例１：付け替えによる順位操作）
＜１＞：  ＡＢＣＤＥＦＧＨと順次追加されたエントリは、基本的には先入れ先だしで開放される。ここにユーザーデータＩが追加される。既にキャッシュ内にはＩに対応したアドレステーブルＤがエントリされている。
＜２＞：  まずアドレステーブルＤがアクセスされ、その情報を元に、フラッシュメモリからＩが読み出されてキャッシュメモリに追加される。この際Ａが開放され、Ｂ〜Ｈの順位が右にシフトする。
＜３＞  ここでＤはエントリ列の末尾に付け替えられる。それに伴なってＥＦＧＨＩの順位は一つ右にシフトする。
【０１３１】
このような開放順位の付け替え操作は、各エントリをリンクリストにして管理すれば、容易に実現できる。また開放されるべきエントリであるＡが丁度Ｉのテーブルであった場合は、たとえば＜２＞の処理においてＡの替わりにＢを開放し、Ｃ〜Ｈの順位を右にシフトすれば良い。
【０１３２】
（操作例２：スワップによる順位操作）
＜１＞，＜２＞：  操作例１と同じである。
＜３＞：  ＤとＩとのエントリの開放順位がスワップされて入れ替わる。
【０１３３】
（操作例３：スタック方式）
＜１＞：  ＡＢＣＤＥＦＧＨと順次追加されたエントリは、基本的には先入れ後だしで開放される。すなわちエントリはスタック方式で追加されている。ここにユーザーデータＩが追加される。既にキャッシュ内にはＩに対応したアドレステーブルＤがエントリされている。
＜２＞：  まずアドレステーブルＤがアクセスされ、その情報を元に、フラッシュメモリからＩが読み出されてキャッシュメモリに追加される。この際その直前に追加したエントリのＨが開放される。
【０１３４】
いずれの場合も、少なくともユーザーデータがキャッシュに追加される際には、対応するテーブルの開放順位が常にその下位に設定される。自然にそのようになるスタック方式については一般にヒット率が低いので、より高ヒット率が見込めるラウンドロビン方式等を採用しつつ、積極的にエントリの開放順位を操作する方が、より望ましい。
またさらに、キャッシュヒット率を向上させるには、新規エントリの追加時のみならず、キャッシュ上のデータが更新された際にも、それを開放順位上のエントリ列の末尾に付け替えるのが効果的である。ユーザーデータにおいてこのような処理が実施されたら、さらに対応するテーブルをその後ろに付け替えるのが望ましい。これによってキャッシュ上の全てのユーザーデータに対して、対応するアドレステーブルが同時にキャッシュ上に存在していることを保証できる。
【０１３５】
このようなキャッシュテーブルの保証は、ユーザーデータをアドレステーブルとを混在させず、別個のキャッシュ領域に格納しても、同様に必要である。しかし本実施形態のように同じキャッシュメモリ内にエントリとして混在させる方が、そのような保証は容易である。すなわち本実施形態では、ユーザーデータとアドレステーブルの各々のエントリ間での自在な付け替えやスワップが可能であり、これによって上述の如き強固な保証が簡単に実現できている。
【０１３６】
なお、フラッシュメモリに対するキャッシュメモリの設置に関しては、これまでユーザーデータをキャッシュすることを目的として、各種の提案がなされてきた。たとえば特開平０５−２１６７７５号公報、特開平０６−３４９２８６号公報等にもキャッシュメモリの使用が記載されている。我々はさらに特願２００５―１７１１４１号、特願２００５−２２０９４０号等において、より発展したキャッシュメモリのアルゴリズムをユーザーデータ用に提案した。
【０１３７】
本発明を採用すれば、アドレステーブルはユーザーデータと同列扱うことができ、統一的に管理できる。特にテーブルリストとキャッシュテーブルの活用で、複雑なキャッシュ管理にも容易に対応できるようになる。
したがって、第２〜第５の実施形態においては、上述のような各種キャッシュアルゴリズムも同様に適用することができる。たとえばフラッシュメモリモジュールの一括書き込み単位であるページグループをさらに１／Ｎ（Ｎは２以上の整数）に分割し、その中に同様に分割したアドレステーブルを格納して、それをキャッシュエントリの単位にしても良い。
【０１３８】
ところで、上述の各実施形態においては、ファイル記憶装置内にＲＡＭを設け、そこにアドレステーブルを展開して、内蔵する制御回路で管理を行なった。メモリカード等、特にモバイルタイプのファイル記憶装置では、各種ホストに対応するため、このような変換処理を記憶装置内部で実施することが有効である。
しかし、組み込み型のストレージを搭載したコンピュータシステムでは、ホストＣＰＵがシステムメモリ内にアドレステーブルを展開し、ドライバソフト等を用いて自らその管理を実施するケースも多い。そのようなケースでも、本発明の概念は全く同様に適用することが可能である。
【０１３９】
すなわち、ホストＣＰＵはアドレステーブルをユーザーデータと同列に扱い、統一した管理でフラッシュメモリデバイスに混在させて格納する。システムメモリ内には各アドレステーブルのフラッシュメモリ内での所在地を示す情報が、テーブルリストとして常駐している。
ＯＳやアプリケーションからの要求に応じで、ホストＣＰＵは以下の手順でフラッシュメモリデバイスをアクセスする。
【０１４０】
１．まずテーブルリストを参照し、ＯＳやアプリケーションが要求する論理アドレスに対応したアドレステーブルの、フラッシュメモリデバイス上の所在情報を取得する。
２．次に上記所在情報をもとにフラッシュメモリをアクセスし、アドレステーブルを読み出して、システムメモリ上に展開する。
３．次にアドレステーブルを参照し、ＯＳやアプリケーションが要求する論理アドレスに対応したユーザーデータの、フラッシュメモリデバイス上の所在情報を取得する。
４．最後に上記所在情報をもとにフラッシュメモリをアクセスし、ユーザーデータの読み出し、さらには必要に応じて更新を行う。
【０１４１】
その際の具体的なアドレステーブルやテーブルリストの操作等は、前述の第１の実施形態と全く同様に実施できる。
【０１４２】
また、システムメモリをアドレステーブルのキャッシュとして使用することもでき、複数のエントリを設けたり、ユーザーデータのエントリと混在させることもできる。その際のキャッシュテーブルの操作も第２〜第５の実施形態と全く同様に実施すれば良い。
【０１４３】
ところで、フラッシュメモリデバイスの管理には、上述のアドレステーブル以外にも多くの管理テーブルを使用する。
たとえば、図６における検索テーブル４３や、図には記載されていない欠陥ブロックをスペアの良品ブロックと置き換えるための置換情報を格納したテーブル等が使用されるが、それらもストレージの容量の増大に伴ってテーブルサイズが巨大化し、ＲＡＭ領域を圧迫するようになる。
【０１４４】
前述の実施形態の如く、アドレステーブルについてはそれらを分割し、フラッシュメモリ内にユーザーデータと混在させて分散格納することで、ユーザーデータとの統一的管理を実現した。
しかし、上記管理データ一般については、ユーザーデータと全く同様には扱えないケースがある。
【０１４５】
たとえば検索テーブル４３を分割してユーザーデータと全く同様に管理した場合、その一部を更新してフラッシュメモリに書き込もうとすると、それらが保存されていたフラッシュメモリ上の旧エリアを無効化しなければならない。そのため、再度検索テーブル４３の該当箇所のページ使用フラグ（ｐａｇｅ  ｄｉｓａｂｌｅｄ）を更新しなければならなくなる。すなわち検索テーブル４３のある箇所を更新しようとすれば、それに伴って同じテーブルの全く別の箇所の更新が必要になる。このような更新は延々繰り返されるかもしれない。
【０１４６】
このような管理用データは、ユーザーデータと管理を一体化することはできない。しかし、本発明の基本概念を次のようにモディファイして適用することで、殆どの管理用データについて書き換えの集中を防止しつつ、良好なアクセス性能を得ることが可能になる。
すなわち、それらの格納には専用の消去ブロックをあてがうものの、各専用ブロックはユーザーデータと同様に、フラッシュメモリ上に動的に確保される。この際、それらの格納にはユーザーデータと共通したフラッシュメモリ上の領域が使用される。すなわち上記領域内には、管理用データが格納されたブロックとユーザーデータが格納されたブロックが、互いに分散して混在することになる。
【０１４７】
以下に、本発明の第６の実施形態として、管理用データが格納されたブロックとユーザーデータが格納されたブロックが、互いに分散して混在する場合の領域確保について説明する。
【０１４８】
図２０（Ａ）〜（Ｄ）は、第６の実施形態に係る領域確保の概念を示す図である。
図２０（Ａ）〜（Ｄ）において、ｚ１はフラッシュメモリデバイスを、ｚ２はユーザーデータを、ｚ３は書き込みポインタを、ｚ４はローカルポインタをそれぞれ示している。
【０１４９】
ステップＳＴ５１
図２０（Ａ）に示すように、フラッシュメモリデバイスｚ１における消去ブロックのアドレス“０ｘ００１”〜“０ｘ３ＥＦ”の領域内に、ユーザーデータと管理用データが保存される。ここでは書き込みポインタｚ３が順次インクリメントされ、それに従ってユーザーデータｚ２がページ単位で書き込まれている。書き込みポインタｚ３の上位“０ｘ００２”はブロックアドレスであり、下位“０ｘＡ０”はページアドレスである。
【０１５０】
ステップＳＴ５２
この状態から管理用データを書き込むとする。図２０（Ｂ）に示すように、書き込みポインタｚ３のあるブロック“０ｘ００２”の次の空きブロック“０ｘ００３”が検索され、そこに管理用データの保存領域が確保される。その先頭に管理用データ書き込み用のローカルポインタｚ４が設定され、そのポインタのインクリメントに従って“０ｘ００３”のブロック内に管理用データが順次ページ単位で書き込まれる。
【０１５１】
ステップＳＴ５３
図２０（Ｃ）に示すように、さらにユーザーデータが書き込まれ、“０ｘ００２”が一杯になると、書き込みポインタｚ３は次の空きブロック“０ｘ００４”の先頭に移動し、そこにユーザーデータ用の保存領域が確保される。ポインタｚ３のインクリメントに従ってユーザーデータの書き込みが継続される。
【０１５２】
ステップＳＴ５４
図２０（Ｄ）に示すように、さらに管理用データが書き込まれ、“０ｘ００３”が一杯になると、書き込みポインタｚ３のあるブロック“０ｘ００４”の次の空きブロック“０ｘ００５”が検索され、そこに管理用データの保存領域が確保される。ローカルポインタｚ４はその先頭に移動し、そのインクリメントに従って“０ｘ００５”のブロック内に管理用データが順次書き込まれる。
【０１５３】
このように，ユーザーデータと管理用データはフラッシュメモリｚ１における共通領域“０ｘ００１〜０ｘ３ＥＦ”の内部に、その格納領域が各々ブロック単位で動的に確保されている。書き込みポインタｚ３は上記共通領域内の空きブロックを循環し、これに伴ってユーザーデータが書き込まれるが、同時に管理用データの格納領域も、必要に応じて該ポインタの近傍に、ブロック単位で動的に確保される。
【０１５４】
このようにすることでユーザーデータと管理用データを個別に管理しつつ、管理用データ格納領域への書き換え集中を防止することができる。
このような手法は前述のアドレス変換テーブルの格納にも適用できる他、多くの管理用データに適用できる。なお、本手法においては、複数種の管理用データに個別のローカルポインタとブロックを割り当てて、それらを独立に管理することも可能である。
【０１５５】
なおここではユーザーデータの書き込みポインタｚ３を領域確保の共通の基準としたが、これはユーザーデータの書き込み頻度が最も高く、このポインタの進行が最も速いと見込まれるためである。必要があれば別途基準ポインタを設けても良い。すなわち書き込みポインタｚ３とローカルポインタｚ４のうち前方にある側のブロックを指すポインタを基準ポインタとして別途保存し、その前方の空き領域にユーザーデータや管理用データの格納領域を確保しても良い。
【０１５６】
ここで、第１の実施形態と第６の実施形態に係る本手法を比較すると、管理用データ（アドレス変換テーブルを含む）とユーザーデータの格納領域が、フラッシュメモリ内の共通領域に各々動的に確保され、それらが互いに順不同で混在している点は、両者同様である。ただし、第１の実施形態においては、その領域は書き込み単位に一致するページ単位で確保されている。一方、本第６の実施形態においては格納領域が消去ブロック単位で確保されている。前者には両者の管理を統一できる利点があるが、後者には両者を独立に管理することで、広範な管理用データを扱える利点がある。また、後者には、テーブルの所在を管理するために使用するＲＡＭ容量を小型化できる利点もある。
【０１５７】
本第６の実施形態を第１の実施形態と同様にアドレス変換テーブルの格納に適用し、より具体化した例を以下に説明する。ハードウエア構成は図５に示した第１の実施形態と同様である。また、第１の実施形態と同様にページ単位の仮想アドレス管理が採用されている。ただし管理手法に違いに伴って、テーブル構成が異なる。
【０１５８】
図２１（Ａ）〜（Ｃ）はテーブルリスト４１ｅ、アドレステーブル４２ｅ、および検索テーブル４３ｅの構成例を示す図である。また、図２２は、テーブルリスト４１ｅ、アドレステーブル４２ｅ、および検索テーブル４３ｅを使用したデータアクセスを示すフローチャートである。
ファイル記憶装置３０の内部におけるフラッシュメモリモジュール３９への具体的アクセスは、図２２のフローチャートに従って、以下のような手順で実行される。
【０１５９】
ステップＳＴ６１：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、制御回路３２はまずその上位アドレスを受けて内蔵ＲＡＭ４０にアクセスし、そこに常駐するテーブルリスト４１ｅから、対応するアドレステーブル４２ｅの所在情報を取得する。
テーブルリスト４１ｅに設けられたテーブルインデックス（Ｔ−Ｉｎｄｅｘ）は２ｋページ分の論理ページアドレス領域ごとに分割されており、ここではセクタアドレスの上位ビット“００００＿０１０１＿０１０１” （“０ｘ０５５”の二進数表記）中の“００００＿０１０１＿０”までがインデックスとして使用される。
さらに本実施形態においては、アドレステーブルの格納領域には３２個の小テーブル（３２個のインデックスに相当）ごとに専用ブロックが動的に割り当てられている。すなわち、ここではアドレステーブル全体は１２８個の小テーブルに分割されており、それらは３２個ごとにグループを成して４個の消去ブロックに各々格納されている。各格納ブロックはアドレステーブル格納用の専用ブロックとして動的に領域が確保されており、さらに各々独立したローカルポインタを有する。
上記インデックス“００００＿０１０１＿０”の上位４ビット“００００”に対しては共通のブロックアドレス“０ｘ０３０”が割り当てられている。また、下位５ビット“０１０１＿０”に対してはこのブロック内におけるページのオフセット値（ＰＯＦＦ）“０ｘＢ０”が割り当てられている。すなわち“０ｘ０５０”のインデックスに対応するアドレステーブルの所在を示す物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。また、この専用ブロックに対するローカルポインタはレジスタ４８ｅに格納されており、その値は“０ｘＣ０”である。このようにブロックごとに領域が確保された場合、複数ページに対してブロックアドレス部分を共通にできる。したがって、ＲＡＭに常駐するテーブルリスト４１ｅの容量は、ページごとに領域を確保するより小さくなる。
【０１６０】
ステップＳＴ６２：
上記物理ページアドレスをもって、フラッシュメモリモジュール３９がアクセスされ、ページバッファ３４内にアドレステーブルが格納されたページグループが読み出される。これがＲＡＭ４０上に展開されて、アドレステーブル４２ｅが構築される。
アドレステーブル４２ｅは各論理ページアドレスＬＰＡに対応して４バイトの（３２ビット）情報を保持しており、その内２０ビットがフラッシュメモリモジュール上の物理ページアドレスＰＰＡである。残りのビットには、たとえば更新時のタイムスタンプや更新回数等、履歴情報等が格納されている。
前述の如く、１アドレステーブルは２ｋページ分の論理ページアドレスをカバーする。したがって、その総容量は（４バイト  ｘ  ２ｋ  ＝  ８ｋバイト）となり、一括書き込み単位である１ページ分の容量に相当する。
【０１６１】
ステップＳＴ６３：
次に、再度セクタの論理アドレス“０ｘ０５５０２Ｃ”より、論理ページアドレス部ＬＰＡ“０ｘ０５５０２”をインデックスにアドレステーブル４２ｅが参照され、アクセス対象たるユーザーデータの物理ページアドレスＰＰＡ“０ｘ０６０Ｂ０”が取得される。
【０１６２】
ステップＳＴ６４：
上記物理ページアドレスＰＰＡをもって、再度フラッシュメモリモジュール３９がアクセスされ、ページバッファ３４内にユーザーデータが格納されたページグループが読み出される。
その後セクタアドレス“０ｘＣ”に相当する部分がページバッファ３４から選択的にホストシステム５０側に出力され、読み出し動作が完了する。
さらに、データの更新は以下のように実施する。同じ“０ｘ０５５０２Ｃ”のセクタを更新するとする。その場合、まずページバッファ３４に所望のページを読み出す必要があり、その手順はステップＳＴ６１〜ステップＳＴ６４と同様である。
【０１６３】
ステップＳＴ６１〜ＳＴ６４：
読み出し時と同様に、フラッシュメモリモジュール３９より読み出した所望のデータをページバッファ３４に格納する。
【０１６４】
ステップＳＴ６５：
ページバッファ３４上で所望のセクタ箇所を更新する。
【０１６５】
ステップＳＴ６６：
更新したユーザーデータのフラッシュメモリモジュール３９への書き込み先として、ＲＡＭ４０内に常駐した検索テーブル４３ｅから、適当なページ領域の物理ページアドレスＰＰＡが選択される。ここでは簡単のため、物理ページアドレスは、上位１２ビットの物理ブロックアドレス部（Ｐｈｉｓｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ  ：ＰＢＡ）と下位８ビットのページオフセット部よりなるとする。この時各消去ブロックは２５６ページ（２８）より構成される。
検索テーブル４３ｅには、各ブロックごとに、内部に含まれるページの有効／無効がフラグ（ｐａｇｅ  ｄｉｓａｂｌｅｄ）として格納されている。ページが無効化されると対応するフラグに“１”が立つ。さらに各ブロックが現在使用されているか、もしくは消去済みの空き状態であるかが、“Ｕｓｅｄ  Ｆｌａｇ”でマークされている。
データの書き込みは、消去済みブロックの先頭ページから順に実行されていく。前回の書き込んだページの物理アドレスは、レジスタ４４ｅに保存されており、書き込み先にはそれがインクリメントされたページが順次選択される。選択がブロックの末尾に達したら、それ以降のブロックの“Ｕｓｅｄ  Ｆｌａｇ”がスキャンされ、次の未使用ブロックが検出されて、その先頭ページが選択される。
レジスタ４４ｅの値は現在“０ｘ０ＡＡ０１”であり、制御回路３２はまずユーザーデータの書き込み先として、それをインクリメントした物理ページアドレス“０ｘ０ＡＡ０２”を選択する。
【０１６６】
ステップＳＴ６７：
上記物理ページアドレスＰＰＡをもって、フラッシュメモリモジュール３９がアクセスされ、ページバッファ３４内のユーザーデータがフラッシュメモリモジュールに一括書き込みされる。書き込みが完了すると、アドレステーブル４２が更新され、論理ページアドレスＬＰＡ“０ｘ０５５０２”に対応する物理ページアドレスＰＰＡは“０ｘ０ＡＡ０２”に更新される。また、旧物理ページアドレス“０ｘ０６０Ｂ０”に相当するページ領域は無効となり、検索テーブル４３ｅの対応するページのフラグが“１”に変わる。
【０１６７】
ステップＳＴ６８：
さらに、アドレステーブル４２ｅの更新は、フラッシュメモリモジュール上にも反映される必要がある。第１の実施形態と異なり、本第６の実施形態におけるアドレステーブルのフラッシュメモリ上への書き込み先は、更新前と同一のブロック“０ｘ０３０”の空き領域が選択される。
アドレステーブル格納用の専用ブロックには１ブロックに２５６ページが格納できるにも拘らず、各ブロックには３２インデックス分のアドレステーブルしか割り当てられていないので、通常ブロック内には多くの空き領域が残存する。その領域に、レジスタ（４８ｅ）に格納されたローカルポインタのインクリメントに従って更新データが追記されることになる。ここではローカルポインタが一つインクリメントされ、物理ページアドレス“０ｘ０３０Ｃ１”が選択される。
【０１６８】
なお、更新が繰り返された結果ローカルポインタがブロック“０ｘ０３０”の末尾にある場合、次のように新規ブロックが確保され、そちらにデータが移される。
まずレジスタ４４ｅの指すブロック“０ｘ０ＡＡ” から“Ｕｓｅｄ  Ｆｌａｇ”がスキャンされ、次の未使用ブロックが検出される。そこにアドレステーブルの新たな書き込み領域が確保され、ローカルポインタはその先頭を指す。新規ブロックの“Ｕｓｅｄ  Ｆｌａｇ”は“１”に更新される。さらに、テーブルリスト４１ｅの情報を参照し、元ブロック“０ｘ０３０”に格納されていた各小テーブルが、ローカルポインタのインクリメントに従って新規ブロックに順次コピーされる。それが完了するとテーブルリスト４１ｅの各フィールドが更新され、元ブロックは消去される。消去後の元ブロックの“Ｕｓｅｄ  Ｆｌａｇ”は“０”となる。これにより書き込み先ブロックの移動が行なわれた。
最後にローカルポインタはもう一つインクリメントされ、新規に確保されたブロックの次の空きページ領域が、更新された小アドレステーブルの書き込み先として選択される。
【０１６９】
ステップＳＴ６９：
上記物理ページアドレスをもって、フラッシュメモリモジュール３９が再度アクセスされる。まずアドレステーブル４２ｅはＲＡＭ４０からページバッファ３４にコピー転送され、さらにページグループとしてフラッシュメモリモジュールに一括書き込みされる。
書き込みが完了すると、テーブルリスト４１ｅが更新され、テーブルインデックス（Ｔ−Ｉｎｄｅｘ）“０ｘ０５０”に対応するページオフセットＰＯＦＦは“０ｘＣ１”に更新される。
なお、第１の実施形態のようにブロックテーブル４３ｅのページフラグ（ｐａｇｅ  ｄｉｓａｂｌｅｄ）は更新する必要は無い。
【０１７０】
上述のような書き込み制御においては、アドレステーブル４２ｅのフラッシュメモリ上へのアクセスに使用されるのは、テーブルリスト４１ｅと検索テーブル４３ｅ内のＵｓｅｄフラグのみである。
したがって、たとえばアドレステーブルに次いで大きな容量を持つ検索テーブル（４３ｅ）のページフラグ（ｐａｇｅ  ｄｉｓａｂｌｅｄ）部分について、それをＵｓｅｄフラグと分離し、必要があれば同様の手法で分割して、フラッシュメモリデバイス内に格納できる。
その場合、上記Ｕｓｅｄフラグはユーザーデータやアドレステーブルと共有することになる。一方、ページフラグ（ｐａｇｅ  ｄｉｓａｂｌｅｄ）の格納場所を示すテーブルとして、テーブルリスト（４１ｅ）に相当するリストを、もう一つ追加する必要がある。
【０１７１】
なお、上述のような管理データをフラッシュメモリデバイスに格納するための分割単位は、フラッシュメモリデバイスの一括アクセス単位であるページ領域のサイズ以下に留め、一回のアクセスで一単位を読み出しまたは保存できるようにすることが望ましい。
【０１７２】
また、第１の実施形態にアドレステーブルのキャッシュメモリを設けて第１の実施形態に発展させたように、本第６の実施形態についても全く同様に、フラッシュメモリデバイス内に格納された各種管理データに対して、読み出し先のＲＡＭ上にキャッシュメモリを設けることが可能である。この場合、そのエントリは上記分割の一単位とすることが望ましく、各キャッシュメモリは複数のエントリを持つことが望ましい。
【０１７３】
同様にブロック単位で領域を確保し、ＲＡＭ内に常駐するテーブルリストをさらに小型化した第７の実施形態について以下に説明する。ハードウエア構成は図５に示した第１および第６の実施形態と同様である。
【０１７４】
図２３（Ａ）〜（Ｃ）は、第７の実施形態に係るテーブルリスト４１ｆ、アドレステーブル４２ｆ、および検索テーブル４３ｆの構成例を示す図である。
【０１７５】
第７の実施形態のテーブルリスト４１ｆでは、さらに各小アドレステーブルごとに設置されていたページオフセットの常駐も廃止した。すなわち、３２個の小アドレステーブルよりなるグループごとに、格納先ブロックのアドレスとブロック内の書き込み先を示すローカルポインタのみが設置されている。ブロックアドレスに２バイト、ローカルポインタに１バイトを消費した場合、テーブルリスト４１ｆ格納に必要なＲＡＭ容量は、ストレージ全体、すなわち１２８個の小アドレステーブルに対して僅か１２バイトである。
【０１７６】
また、図２４は、第７の実施形態に係るテーブルリスト４１ｆ、アドレステーブル４２ｆ、および検索テーブル４３ｆを使用したデータアクセスを示すフローチャートである。
ファイル記憶装置３０の内部におけるフラッシュメモリモジュール３９への具体的アクセスは、図２４のフローチャートに従って、以下のような手順で実行される。
【０１７７】
ステップＳＴ７１：
ホストシステム５０からユーザーデータのアクセスコマンドとともに“０ｘ０５５０２Ｃ”のセクタアドレスが入力されると、制御回路３２はまずその上位アドレスを受けて内蔵ＲＡＭ４０にアクセスし、そこに常駐するテーブルリスト４１ｆから、対応するアドレステーブル４２ｆの所属するブロックアドレスを取得する。
【０１７８】
各小アドレステーブルに対応するテーブルインデックス（Ｔ−Ｉｎｄｅｘ）は２ｋページ分の論理ページアドレス領域ごとに分割されており、ここではセクタアドレスの上位ビット“００００＿０１０１＿０１０１” （“０ｘ０５５”の二進数表記）中の“００００＿０１０１＿０”までがインデックスとして使用される。
【０１７９】
さらにアドレステーブルの格納領域には３２個の小テーブル（３２個のインデックスに相当）ごとに専用ブロックが動的に割り当てられている。すなわち、ここではアドレステーブル全体は１２８個の小テーブルに分割されており、それらは３２個ごとにグループを成して４個の消去ブロックに各々格納されている。各格納ブロックはアドレステーブル格納用の専用ブロックとして動的に領域が確保されており、さらに各々独立したローカルポインタを有する。
【０１８０】
上記インデックス“００００＿０１０１＿０”の上位４ビット“００００”に対しては共通のブロックアドレス“０ｘ０３０”が割り当てられている。なお、第６の実施形態と異なり、この時点ではこのブロック内における各小テーブルを格納したページのオフセット値（ＰＯＦＦ）は不明である。また、この専用ブロックに対するローカルポインタはレジスタ４８ｆに格納されており、その値は“０ｘＣ０”である。
【０１８１】
ステップＳＴ７１Ｂ：
ブロック“０ｘ０３０”の先頭ページ“０ｘ００”から、ローカルポインタのある“０ｘＣ０”までの全ページの冗長領域をスキャンし、所望の小テーブルが格納されたページを検索する。各ページの冗長領域には、格納された小テーブルのテーブルインデックスが記載されている。この値が所望の小テーブルのテーブルインデックス“００００＿０１０１＿０”に一致し、かつ最も下位のアドレスにある（すなわち最も新しく書き込まれた）ページが、該当ページである。このようにして、たとえば所望の小テーブルの物理ページアドレスＰＰＡ“０ｘ０３０Ｂ０”が取得される。
【０１８２】
ステップＳＴ７２：
所望の小アドレステーブル４２ｆをＲＡＭ内に読み出す。この工程は第６の実施形態のステップＳＴ６２と同様の作業である。
【０１８３】
ステップＳＴ７３：
アドレステーブル４２ｆからユーザーデータの物理ページアドレスＰＰＡ“０ｘ０６０Ｂ０”を取得する。この工程は第６の実施形態のステップＳＴ６３と同様の作業である。
【０１８４】
ステップＳＴ７４：
ユーザーデータをフラッシュよりページバッファに読み出す。この工程は第６の実施形態のステップＳＴ６４と同様の作業である。
【０１８５】
ステップＳＴ７５：
ページバッファ３４上で所望のセクタ箇所を更新する。この工程は第６の実施形態のステップＳＴ６５と同様の作業である。
【０１８６】
ステップＳＴ７６：
検索テーブル４３ｆおよびポインタ４６ｆから、更新データの書き込み先アドレスを取得する。ここではポインタ４６ｆがインクリメントされて、“０ｘ０ＡＡ０２”が書き込み先物理ページアドレスとして選択される。この工程は第６の実施形態のステップＳＴ６６と同様の作業である。
【０１８７】
ステップＳＴ７７：
ユーザーデータをフラッシュに書き込む。アドレステーブル４２ｆにおける論理ページアドレスＬＰＡ“０ｘ０５５０２”に対応する物理ページアドレスＰＰＡは“０ｘ０ＡＡ０２”に更新される。また、旧物理ページアドレス“０ｘ０６０Ｂ０”に相当するページ領域は無効となり、検索テーブル４３ｆの対応するページのフラグが“１”に変わる。この工程は第６の実施形態のステップＳＴ６７と同様の作業である。
【０１８８】
ステップＳＴ７８：
更新されたアドレステーブル４２ｆの書き込み先が、更新前と同一のブロック“０ｘ０３０”の空き領域から選択される。すなわちレジスタ４８ｆに格納されたローカルポインタが一つインクリメントされ、物理ページアドレス“０ｘ０３０Ｃ１”が選択される。
ここまでは第６の実施形態のステップＳＴ６８と同様の作業である。
【０１８９】
なお、更新が繰り返された結果ローカルポインタがブロック“０ｘ０３０”の末尾にある場合、次のように新規ブロックが確保され、そちらにデータが移される。
まずレジスタ４４ｆの指すブロック“０ｘ０ＡＡ” から“Ｕｓｅｄ  Ｆｌａｇ”がスキャンされ、次の未使用ブロックが検出される。そこにアドレステーブルの新たな書き込み領域が確保され、ローカルポインタはその先頭を指す。新規ブロックの“Ｕｓｅｄ  Ｆｌａｇ”は“１”に更新される。
【０１９０】
ここでデータの移動には第６の実施形態とは異なる手順が必要になる。
まず旧ブロック“０ｘ０３０”の各ページの冗長領域を全てスキャンして、ＲＡＭ上に論理ページアドレスとページオフセットを対応させたテーブル４９ｆを一時的に生成する。
このテーブル情報を参照し、元ブロック“０ｘ０３０”に格納されていた各小テーブルが、ローカルポインタのインクリメントに従って新規ブロックに順次コピーされる。それが完了するとテーブル４９ｆは開放される。テーブルリスト４１ｆの物理ブロックアドレスフィールド“０ｘ０３０”は新規ブロックのアドレスに書き換えられ、元ブロックは消去される。消去後の元ブロックの“Ｕｓｅｄ  Ｆｌａｇ”は“０”となる。これにより書き込み先ブロックの移動が行われた。
最後にローカルポインタはもう一つインクリメントされ、新規に確保されたブロックの次の空きページ領域が、更新された小アドレステーブルの書き込み先として選択される。
【０１９１】
ステップＳＴ７９：
アドレステーブル４２ｆがフラッシュモジュールに書き込まれる。ただし、第６の実施形態６と異なり、そのページオフセットをテーブルリスト４１ｆに更新記入する必要は無い。
【０１９２】
以上説明したように、本発明の実施形態によれば、アドレステーブルはフラッシュメモリ内に分散して格納されており、ユーザーデータと同列に扱われて、統一的に管理される。したがって、各アドレステーブルは必要に応じて柔軟かつ迅速に取り出すことができ、更新も容易であり、特定の消去ブロックへの書き換え集中も防止できる。かつ、煩雑な機能の追加を必要としない。
このようなコンピュータシステムでは、巨大なアドレステーブルを活用して、フラッシュメモリ上のデータに効率的なアクセスを実施できる。さらにアドレステーブルの格納に大きなＲＡＭ領域を占有しない。したがって、高速、柔軟かつ安価で、信頼性の高いコンピュータシステムを構築することが可能である。
さらに、アドレステーブル以外の管理用データについても、ユーザーデータと同じフラッシュメモリ領域に、それらと混在する形で動的に格納領域が確保される。したがって、特定の消去ブロックへの書き換え集中は、同様に防止することが可能である。
【図面の簡単な説明】
【０１９３】
【図１】ＮＡＮＤ型フラッシュメモリの内部構成例を示す図である。
【図２】フラッシュメモリにおけるデータ更新の一例を示す図である。
【図３】消去ブロック単位でアドレス変換を実施する方法の例を示す図である。
【図４】追記型記憶システムにおける管理方法を説明するための図である。
【図５】本発明の第１の実施形態に係る記憶装置を採用したコンピュータシステムの構成例を示す図である。
【図６】第１の実施形態に係るテーブルリスト、アドレステーブル、および検索テーブルの構成例を示す図である。
【図７】第１の実施形態に係るテーブルリスト、アドレステーブル、および検索テーブルを使用したデータアクセスを示すフローチャートである。
【図８】第２の実施形態に係る記憶装置を採用したコンピュータシステムの構成例を示す図である。
【図９】第２の実施形態において、アドレステーブルをアクセスするための、アドレスインデックスとキャッシュテーブルの一例を示す図である。
【図１０】第２の実施形態に係るデータアクセスのフローチャートである。
【図１１】第３の実施形態において、アドレステーブルをアクセスするための、アドレスインデックスとキャッシュテーブルの一例を示す図である。
【図１２】第３の実施形態に係るデータアクセスのフローチャートである。
【図１３】第４の実施形態に係るテーブルリスト、アドレステーブル、およびキャッシュテーブルの例を示す図である。
【図１４】第４の実施形態に係るデータアクセスのフローチャートである。
【図１５】第５の実施形態に係るテーブルリスト、アドレステーブル、およびキャッシュテーブルの例を示す図である。
【図１６】第５の実施形態に係るデータアクセスのフローチャートである。
【図１７】キャッシュメモリ内の開放優先順位の操作例を示す概念図であって、付け替えによる順位操作例を示す図である。
【図１８】キャッシュメモリ内の開放優先順位の操作例を示す概念図であって、スワップによる順位操作例を示す図である。
【図１９】キャッシュメモリ内の開放優先順位の操作例を示す概念図であって、スタック方式による順位操作例を示す図である。
【図２０】第６の実施形態に係る領域確保の概念を示す図である。
【図２１】第６の実施形態に係るテーブルリスト、アドレステーブル、および検索テーブルの構成例を示す図である。
【図２２】第６の実施形態に係るテーブルリスト、アドレステーブル、および検索テーブルを使用したデータアクセスを示すフローチャートである。
【図２３】第７の実施形態に係るテーブルリスト、アドレステーブル、および検索テーブルの構成例を示す図である。
【図２４】第７の実施形態に係るテーブルリスト、アドレステーブル、および検索テーブルを使用したデータアクセスを示すフローチャートである。
【符号の説明】
【０１９４】
３０，３０Ａ・・・ファイル記憶装置、３１・・・インターフェース回路、３２・・・制御回路、３３・・・内部バス、３４・・・ページバッファ、３５，３６・・・ＮＡＮＤ型フラッシュメモリ、３７・・・制御回路、３８・・・メモリバス、３９・・・フラッシュメモリデバイス（フラッシュメモリモジュール）、４０，４０Ａ・・・ＲＡＭ、４１，４１ｂ，４１ｃ，４１ｄ，４１ｅ・・・テーブルリスト、４２，４２ｂ，４２ｃ，４２ｄ，４２ｅ・・・アドレステーブル、４３，４３ｂ，４３ｃ，４３ｄ・・・検索テーブル、４５，４５ｂ，４５ｃ，４５ｄ，４５ｅ・・・キャッシュテーブル、５０・・・ホストシステム
【図１】
2007334852.tif 000003
【図２】
2007334852.tif 000004
【図３】
2007334852.tif 000005
【図４】
2007334852.tif 000006
【図５】
2007334852.tif 000007
【図６】
2007334852.tif 000008
【図７】
2007334852.tif 000009
【図８】
2007334852.tif 000010
【図９】
2007334852.tif 000011
【図１０】
2007334852.tif 000012
【図１１】
2007334852.tif 000013
【図１２】
2007334852.tif 000014
【図１３】
2007334852.tif 000015
【図１４】
2007334852.tif 000016
【図１５】
2007334852.tif 000017
【図１６】
2007334852.tif 000018
【図１７】
2007334852.tif 000019
【図１８】
2007334852.tif 000020
【図１９】
2007334852.tif 000021
【図２０】
2007334852.tif 000022
【図２１】
2007334852.tif 000023
【図２２】
2007334852.tif 000024
【図２３】
2007334852.tif 000025
【図２４】
2007334852.tif 000026