(57)【要約】【課題】  劣化が起きにくく、あるいは記憶領域へのアクセスが円滑に行える記憶装置等を提供することである。【解決手段】  フラッシュメモリ１１の記憶領域には、消去の単位であるブロックより小さな単位であるグループ毎に物理グループアドレスが与えられ、グループは複数のページを含み、ページは複数のカラムを含む。ＣＰＵ１２１は、書き込む対象のデータと書込先の論理アドレスとを供給されると、書込ポインタが示すグループ内のカラムにこのデータを書き込み、供給された論理アドレスを、このカラムに与える。このカラムがあるグループの物理グループアドレス及び論理グループアドレスの対応関係は論理物理変換テーブルの形でＲＡＭ１２３に記憶される。ブロックのフラッシュイレースは、空きグループのないブロックの数が所定数以下になったとき行う。【選択図】  図１
2006079434.tif 000002
【特許請求の範囲】
【請求項１】
ユーザデータを記憶するための記憶領域を形成する複数のメモリブロックを含み、各々のメモリブロックが複数のグループより構成されており、各々のグループが複数のページより構成されている記憶手段と、
前記グループの前記記憶領域内での物理的位置を指定する物理グループアドレスと当該グループの論理グループアドレスとの対応付けを表す論理物理変換テーブルを記憶する論理物理変換テーブル記憶手段と、
前記グループのうちからユーザデータを記憶可能な状態にある空きグループを特定して、特定した空きグループの物理グループアドレスを指示する書込ポインタを記憶する書込対象グループポイント手段と、
新たなユーザデータを書き込むグループの論理グループアドレス、当該グループに属するページ内において当該ユーザデータを書き込む記憶位置を指定するグループ内アドレス、及び、当該ユーザデータが自己に供給されたとき、当該ユーザデータを、前記書込ポインタにより指示された空きグループに属するページ内において当該グループ内アドレスが指定している記憶位置に書き込み、当該空きグループの物理グループアドレスと、供給された当該論理グループアドレスとの対応付けを表すよう前記論理物理変換テーブルを更新する書込手段と、を備える、
ことを特徴とする記憶装置。
【請求項２】
前記書込手段は、
前記新たなユーザデータを書き込む記憶位置が属するグループの論理グループアドレス及び当該記憶位置のグループ内アドレスにより従前特定されていた他の記憶位置に記憶されているユーザデータを無効とする旨を指定するユーザデータ無効化手段と、
無効なユーザデータを記憶しているメモリブロックのうちからデータを消去する対象のメモリブロックを指定する消去対象指定手段と、
前記消去対象指定手段により指定されたメモリブロックに格納されているユーザデータが有効か否かを判別し、有効と判別したユーザデータを他のメモリブロックに転記し、当該指定されたメモリブロックが記憶するデータを消去する消去手段と、を備える、
ことを特徴とする請求項１に記載の記憶装置。
【請求項３】
各々のメモリブロックに空きグループが含まれているか否かを識別する情報を含むブロックステートテーブルを記憶するメモリを更に備え、
前記書込手段は、
自己に供給されたユーザデータを空きグループに書き込む結果、当該グループを含むメモリブロックから空きグループが無くなったとき、当該メモリブロックが空きグループを含んでいない旨を示すように前記ブロックステートテーブルを更新する手段と、
記憶するデータを前記消去手段により消去されたメモリブロックが空きグループを含む旨を示すように前記ブロックステートテーブルを更新する手段と、を備え、
前記消去対象指定手段は、空きグループを含まない旨が前記ブロックステートテーブルにより示されているメモリブロックのうちからデータを消去する対象のメモリブロックを指定する、
ことを特徴とする請求項２に記載の記憶装置。
【請求項４】
前記書込手段は、空きグループを含むメモリブロックの数が所定条件に満たない数になったか否かを前記ブロックステートテーブルに基づいて判別する空きブロック数判別手段を備え、
前記消去対象指定手段は、空きグループを含むメモリブロックの数が所定条件に満たない数になったと判別されたとき、無効なユーザデータを記憶しているメモリブロックのうちからデータを消去する対象のメモリブロックを指定する、
ことを特徴とする請求項３に記載の記憶装置。
【請求項５】
物理グループアドレスはサイクリックに順位付けされていて、当該物理グループアドレスが示すグループが属するブロックを示すブロックアドレスを含んでおり、
前記消去対象指定手段は、無効なユーザデータを記憶しているメモリブロックのうち、最後にデータを消去されたブロック以降で先頭のブロックアドレスを与えられているものを、データを消去する対象のメモリブロックとして指定する、
ことを特徴とする請求項２、３又は４に記載の記憶装置。
【請求項６】
前記ブロックステートテーブルは、各々のメモリブロックに無効なユーザデータが記憶されているか否かを識別する情報を更に含み、
前記ユーザデータ無効化手段は、前記新たなユーザデータを書き込む記憶位置が属するグループの論理グループアドレス及び当該記憶位置のグループ内アドレスにより従前特定されていた他の記憶位置を含むメモリブロックに無効なユーザデータが記憶されている旨を示すように前記ブロックステートテーブルを更新する手段を備え、
前記消去対象指定手段は、無効なユーザデータを記憶している旨が前記ブロックステートテーブルにより示されているメモリブロックのうちからデータを消去する対象のメモリブロックを指定する、
ことを特徴とする請求項４又は５に記載の記憶装置。
【請求項７】
物理グループアドレスはサイクリックに順位付けされており、
前記書込対象グループポイント手段は、ユーザデータが書き込まれた結果すべてのページにユーザデータが格納されるに至ったグループの物理グループアドレス以降の物理グループアドレスを与えられている空きグループのうちの先頭の空きグループを特定する、
ことを特徴とする請求項１乃至６のいずれか１項に記載の記憶装置。
【請求項８】
読み出し対象のデータが格納されているグループの論理グループアドレス、及び、当該グループに属するページ内において当該読み出し対象のデータが格納されている記憶位置を指定するグループ内アドレスが自己に供給されたとき、前記アドレス変換テーブルに基づいて、当該論理グループアドレスに対応付けられた物理グループアドレスを特定し、特定した物理グループアドレスが示すグループに属するページ内において当該グループ内アドレスが指定している記憶位置よりユーザデータを読み出して外部に出力する読出手段を備える、
ことを特徴とする請求項１乃至７のいずれか１項に記載の記憶装置。
【請求項９】
前記ページは１個以上のカラムを含んでおり、
カラムの記憶位置のグループ内アドレスは、当該カラムを含むページのグループ内での論理的位置を指定するグループ内ページアドレスと、当該ページ内での当該カラムの論理的位置を指定するカラムアドレスと、より構成されている、
ことを特徴とする請求項１乃至８のいずれか１項に記載の記憶装置。
【請求項１０】
ユーザデータを記憶するための複数のメモリブロックを含み、各々のメモリブロックが複数のグループより構成されており、各々のグループが複数のページより構成されている記憶領域を管理するためのメモリ管理方法であって、
前記グループの前記記憶領域内での物理的位置を指定する物理グループアドレスと当該グループの論理グループアドレスとの対応付けを表す論理物理変換テーブルを記憶する論理物理変換テーブル記憶ステップと、
前記グループのうちからユーザデータを記憶可能な状態にある空きグループを特定して、特定した空きグループの物理グループアドレスを指示する書込ポインタを記憶する書込対象グループポイントステップと、
新たなユーザデータを書き込むグループの論理グループアドレス、当該グループに属するページ内において当該ユーザデータを書き込む記憶位置を指定するグループ内アドレス、及び、当該ユーザデータが自己に供給されたとき、当該ユーザデータを、前記書込ポインタにより指示された空きグループに属するページ内において当該グループ内アドレスが指定している記憶位置に書き込み、当該空きグループの物理グループアドレスと、供給された当該論理グループアドレスとの対応付けを表すよう前記論理物理変換テーブルを更新する書込ステップと、より構成される、
ことを特徴とするメモリ管理方法。
【請求項１１】
ユーザデータを記憶するための記憶領域を形成する複数のメモリブロックを含み、各々のメモリブロックが複数のグループより構成されており、各々のグループが複数のページより構成されている記憶装置に接続されたコンピュータを、
前記グループの前記記憶領域内での物理的位置を指定する物理グループアドレスと当該グループの論理グループアドレスとの対応付けを表す論理物理変換テーブルを記憶する論理物理変換テーブル記憶手段と、
前記グループのうちからユーザデータを記憶可能な状態にある空きグループを特定して、特定した空きグループの物理グループアドレスを指示する書込ポインタを記憶する書込対象グループポイント手段と、
新たなユーザデータを書き込むグループの論理グループアドレス、当該グループに属するページ内において当該ユーザデータを書き込む記憶位置を指定するグループ内アドレス、及び、当該ユーザデータが自己に供給されたとき、当該ユーザデータを、前記書込ポインタにより指示された空きグループに属するページ内において当該グループ内アドレスが指定している記憶位置に書き込み、当該空きグループの物理グループアドレスと、供給された当該論理グループアドレスとの対応付けを表すよう前記論理物理変換テーブルを更新する書込手段と、
して機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置、メモリ管理方法及びプログラムに関し、特に、ブロック消去型の記憶装置、ブロック消去型の記憶装置の記憶領域を管理するメモリ管理方法及びプログラムに関する。
【背景技術】
【０００２】
コンピュータ等によりアクセス（データの読み書き及び消去）可能な記録媒体として、ＥＥＰＲＯＭ（Electrically Erasable/Programmable Read Only Memory）フラッシュメモリが用いられている。
フラッシュメモリは、データの消去が、所定の記憶容量の単位（一般に「ブロック」と呼ばれる）で行われる。
【０００３】
フラッシュメモリのうち、特にＮＡＮＤ型のものは、データの記憶が正常に行えない不良ブロックの発生を製造段階で十分に防止することが困難である。このため、従来より、各ブロックに割り当てられる物理アドレスとは別個の連続した論理アドレスを正常なブロックに動的に割り当て、論理アドレスとの対応関係を表すアドレス変換テーブルを作成して、アドレスが不連続となることによる外部からのアクセス手順の複雑化を回避している（例えば、特許文献１参照）。
【特許文献１】国際公開第９９／３０２３９号パンフレット
【０００４】
物理アドレスの割り当てはブロック単位で行われ、論理アドレスからページを特定する場合は、論理アドレスに対応付けられた物理アドレスに加え、ブロック内でのページの順位を示すページアドレスを併用して、ページを特定している。（なお、同一ブロック内では先頭のセクタから順にデータを格納していくものとすれば、連続して供給されるデータ（例えば、１個のファイルを構成するデータ）は、同一ブロック内の連続したページに格納される。）従って、データを書き換える際には、書き換える対象のデータが格納されるページの、ブロック内での順位がそのまま保たれるように配慮する必要がある。
【０００５】
具体的には、書き換える対象のデータを格納する転記元のブロックから、書き換えの対象でないデータを、転記先の空きブロックへと、データの順序が保たれるようにして転記する。つまり、ｎをページの順位として、転記元のブロックのｎ番目のページにあったデータは転記先のｎ番目のページに転記する。また、書き換えの対象であるデータは、書き換え後のデータが書き換え前のデータの順序を保つようにして書き換える。つまり、ｍをページの順位として、転記元のブロックのｍ番目のページにあったデータを書き換えたデータを、転記先のｍ番目のページに転記する。そして、転記元のブロックをフラッシュイレースする（すなわち、記憶内容を消去する）、という操作を行う。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、このような操作を行うと、データ量が１ブロック分の記憶容量に比べて非常に小さなファイルを書き換える場合には、このファイルと無関係なデータを格納するページや、データを格納していない空きページを含んだブロックがフラッシュイレースされる。
【０００７】
ＮＡＮＤ型のフラッシュメモリは、大容量の構成を安価に実現できる一方、フラッシュイレースを繰り返すことにより劣化し、データの読み書きが正常にできなくなる、という特徴がある。このため、上述の操作を行うと、少量のデータの書き換えのために効率の悪いフラッシュイレースが頻繁に行われることになり、フラッシュメモリの劣化が早まる。
【０００８】
特に、ＯＳ（Operating System）が、ハードディスク装置やフレキシブルディスクの記憶内容を管理するのと同様の手法でフラッシュメモリの記憶内容を管理する場合には、ＯＳが管理する各データとこれらデータが記憶されている論理アドレスとの対応関係を示すＦＡＴ（File Allocation Table）等がフラッシュメモリに書き込まれ、頻繁に更新される。ＦＡＴのデータ量は、通常、１ブロック分の記憶容量に比べて非常に小さいので、ＦＡＴの書き換えに伴って、効率の悪いフラッシュイレースが頻繁に行われる。
【０００９】
更に近年は、１ブロック当たりの記憶容量が極めて大きいフラッシュメモリ（例えば、１ブロックが６４ページより構成され、１ページが約２キロバイトの記憶容量を有しているもの）が製造されるようになっている。このようなフラッシュメモリの記憶内容を上述した従来の手法により管理する場合、少量のデータの書き換えに伴って膨大な記憶領域のフラッシュイレースが行われることになり、フラッシュイレースの効率が極めて悪い。
【００１０】
また、ファイルの書き換えに伴ってフラッシュイレースが行われる場合、このファイルと無関係なデータであって未だ記憶しておく必要があるデータは、このフラッシュイレースの巻き添えとならないように他のブロックに退避させる必要がある。このため一般的には、フラッシュイレースの効率が悪いほど、データの退避に要する処理も多くなり、フラッシュメモリへの円滑なアクセスが妨げられる。
【００１１】
特に、１ブロック当たりの記憶容量が極めて大きいフラッシュメモリのフラッシュイレースにおいては、フラッシュイレース１回当たりに退避させるべきデータの量が膨大となり、この結果、フラッシュメモリへの円滑なアクセスは非常に難しくなる。
【００１２】
この発明は上記実状に鑑みてなされたもので、劣化が起きにくい記憶装置や、記憶装置の劣化を起こしにくいメモリ管理方法を提供することを目的とする。
また、この発明は、記憶領域へのアクセスが円滑に行える記憶装置及びメモリ管理方法を提供することも目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するため、本発明の第１の観点に係る記憶装置は、
ユーザデータを記憶するための記憶領域を形成する複数のメモリブロックを含み、各々のメモリブロックが複数のグループより構成されており、各々のグループが複数のページより構成されている記憶手段と、
前記グループの前記記憶領域内での物理的位置を指定する物理グループアドレスと当該グループの論理グループアドレスとの対応付けを表す論理物理変換テーブルを記憶する論理物理変換テーブル記憶手段と、
前記グループのうちからユーザデータを記憶可能な状態にある空きグループを特定して、特定した空きグループの物理グループアドレスを指示する書込ポインタを記憶する書込対象グループポイント手段と、
新たなユーザデータを書き込むグループの論理グループアドレス、当該グループに属するページ内において当該ユーザデータを書き込む記憶位置を指定するグループ内アドレス、及び、当該ユーザデータが自己に供給されたとき、当該ユーザデータを、前記書込ポインタにより指示された空きグループに属するページ内において当該グループ内アドレスが指定している記憶位置に書き込み、当該空きグループの物理グループアドレスと、供給された当該論理グループアドレスとの対応付けを表すよう前記論理物理変換テーブルを更新する書込手段と、を備える、
ことを特徴とする。
【００１４】
このような記憶装置によれば、ユーザデータの書き込みはブロックより小さな単位で行われるので、ユーザデータを書き込む毎に新たな空きブロック（ユーザデータを記憶していないブロック）を探索して書き込むという操作が不要になり、ユーザデータの書き換え時にブロックに対して効率の悪いデータ消去（フラッシュイレース等）を行わずに済む。また、データの書き換えに伴って変更のない部分を転記する処理も、ブロックより小さな単位で行われる。従って、記憶装置の劣化が起きにくく、また記憶装置へのアクセスが円滑になる。
【００１５】
また、このような記憶装置では、論理アドレスと物理アドレスとの対応関係の管理は、ブロックより小さく、ページないしカラムより大きな単位で行われる。このため、論理アドレスと物理アドレスとの対応関係を示すデータを格納するテーブルの記憶容量が、論理アドレスと物理アドレスの対応関係の管理をページないしカラム単位で行う場合に比べて小さくなり、一方で、論理アドレスと物理アドレスの対応関係の管理が、ブロック単位で行う場合に比べきめ細かく行われる。
【００１６】
前記書込手段は、例えば、
前記新たなユーザデータを書き込む記憶位置が属するグループの論理グループアドレス及び当該記憶位置のグループ内アドレスにより従前特定されていた他の記憶位置に記憶されているユーザデータを無効とする旨を指定するユーザデータ無効化手段と、
無効なユーザデータを記憶しているメモリブロックのうちからデータを消去する対象のメモリブロックを指定する消去対象指定手段と、
前記消去対象指定手段により指定されたメモリブロックに格納されているユーザデータが有効か否かを判別し、有効と判別したユーザデータを他のメモリブロックに転記し、当該指定されたメモリブロックが記憶するデータを消去する消去手段と、を備えることにより、古いデータの消去を伴うユーザデータの書き込みを行えばよい。
【００１７】
前記記憶装置は、各々のメモリブロックに空きグループが含まれているか否かを識別する情報を含むブロックステートテーブルを記憶するメモリを更に備えていてもよく、
この場合、前記書込手段は、
自己に供給されたユーザデータを空きグループに書き込む結果、当該グループを含むメモリブロックから空きグループが無くなったとき、当該メモリブロックが空きグループを含んでいない旨を示すように前記ブロックステートテーブルを更新する手段と、
記憶するデータを前記消去手段により消去されたメモリブロックが空きグループを含む旨を示すように前記ブロックステートテーブルを更新する手段と、を備え、
前記消去対象指定手段は、空きグループを含まない旨が前記ブロックステートテーブルにより示されているメモリブロックのうちからデータを消去する対象のメモリブロックを指定するものであってもよい。
【００１８】
前記書込手段は、空きグループを含むメモリブロックの数が所定条件に満たない数になったか否かを前記ブロックステートテーブルに基づいて判別する空きブロック数判別手段を備え、
前記消去対象指定手段は、空きグループを含むメモリブロックの数が所定条件に満たない数になったと判別されたとき、無効なユーザデータを記憶しているメモリブロックのうちからデータを消去する対象のメモリブロックを指定するものであってもよい。
このような構成を有していれば、ユーザデータが格納されていないグループの数が十分にあるうちはメモリブロックのデータ消去が行われないので、無用のデータ消去が避けられる。このため、ブロック１個当たりの記憶容量が大きい場合であっても記憶装置の劣化が更に起きにくく、またデータの退避に要する処理も少なくなるので記憶装置へのアクセスが更に円滑になる。
【００１９】
物理グループアドレスはサイクリックに順位付けされていて、当該物理グループアドレスが示すグループが属するブロックを示すブロックアドレスを含んでいてもよく、
前記消去対象指定手段は、無効なユーザデータを記憶しているメモリブロックのうち、最後にデータを消去されたブロック以降で先頭のブロックアドレスを与えられているものを、データを消去する対象のメモリブロックとして指定するものであってもよい。
このような構成を有していれば、各ブロックは、書き込まれているデータが古い順にデータ消去の対象となっていくから、各ブロックがデータ消去される頻度が均等になる。従って、特定のメモリブロックが集中的に劣化することにより記憶装置全体の寿命が短くなる、ということが防止される。
【００２０】
前記ブロックステートテーブルは、各々のメモリブロックに無効なユーザデータが記憶されているか否かを識別する情報を更に含んでいてもよく、
この場合、前記ユーザデータ無効化手段が、前記新たなユーザデータを書き込む記憶位置が属するグループの論理グループアドレス及び当該記憶位置のグループ内アドレスにより従前特定されていた他の記憶位置を含むメモリブロックに無効なユーザデータが記憶されている旨を示すように前記ブロックステートテーブルを更新する手段を備え、前記消去対象指定手段は、無効なユーザデータを記憶している旨が前記ブロックステートテーブルにより示されているメモリブロックのうちからデータを消去する対象のメモリブロックを指定するようにしてもよい。
【００２１】
物理グループアドレスはサイクリックに順位付けされていてもよく、
前記書込対象グループポイント手段は、ユーザデータが書き込まれた結果すべてのページにユーザデータが格納されるに至ったグループの物理グループアドレス以降の物理グループアドレスを与えられている空きグループのうちの先頭の空きグループを特定するものであってもよい。
このような構成を有していれば、データを書き込むグループは物理グループアドレス順に指定されるので、特定のメモリブロックに書き込みが集中することが避けられ、従って、書き込みが集中したメモリブロックにデータ消去の機会が集中することが避けられる。従って、記憶装置の劣化が更に防止される。
【００２２】
前記記憶装置は、例えば、読み出し対象のデータが格納されているグループの論理グループアドレス、及び、当該グループに属するページ内において当該読み出し対象のデータが格納されている記憶位置を指定するグループ内アドレスが自己に供給されたとき、前記アドレス変換テーブルに基づいて、当該論理グループアドレスに対応付けられた物理グループアドレスを特定し、特定した物理グループアドレスが示すグループに属するページ内において当該グループ内アドレスが指定している記憶位置よりユーザデータを読み出して外部に出力する読出手段を備えるものであってもよい。
【００２３】
前記ページは１個以上のカラムを含んでいてもよく、
カラムの記憶位置のグループ内アドレスは、当該カラムを含むページのグループ内での論理的位置を指定するグループ内ページアドレスと、当該ページ内での当該カラムの論理的位置を指定するカラムアドレスと、より構成されていてもよい。
【００２４】
また、本発明の第２の観点に係るメモリ管理方法は、
ユーザデータを記憶するための複数のメモリブロックを含み、各々のメモリブロックが複数のグループより構成されており、各々のグループが複数のページより構成されている記憶領域を管理するためのメモリ管理方法であって、
前記グループの前記記憶領域内での物理的位置を指定する物理グループアドレスと当該グループの論理グループアドレスとの対応付けを表す論理物理変換テーブルを記憶する論理物理変換テーブル記憶ステップと、
前記グループのうちからユーザデータを記憶可能な状態にある空きグループを特定して、特定した空きグループの物理グループアドレスを指示する書込ポインタを記憶する書込対象グループポイントステップと、
新たなユーザデータを書き込むグループの論理グループアドレス、当該グループに属するページ内において当該ユーザデータを書き込む記憶位置を指定するグループ内アドレス、及び、当該ユーザデータが自己に供給されたとき、当該ユーザデータを、前記書込ポインタにより指示された空きグループに属するページ内において当該グループ内アドレスが指定している記憶位置に書き込み、当該空きグループの物理グループアドレスと、供給された当該論理グループアドレスとの対応付けを表すよう前記論理物理変換テーブルを更新する書込ステップと、より構成される、
ことを特徴とする。
【００２５】
このようなメモリ管理方法によれば、ユーザデータの書き込みはブロックより小さな単位で行われるので、ユーザデータを書き込む毎に新たな空きブロック（ユーザデータを記憶していないブロック）を探索して書き込むという操作が不要になり、ユーザデータの書き換え時にブロックに対して効率の悪いデータ消去（フラッシュイレース等）を行わずに済む。また、データの書き換えに伴って変更のない部分を転記する処理も、ブロックより小さな単位で行われる。従って、記憶装置の劣化が起きにくく、また記憶装置へのアクセスが円滑になる。
【００２６】
また、このようなメモリ管理方法では、論理アドレスと物理アドレスとの対応関係の管理は、ブロックより小さく、ページないしカラムより大きな単位で行われる。このため、論理アドレスと物理アドレスとの対応関係を示すデータを格納するテーブルの記憶容量が、論理アドレスと物理アドレスの対応関係の管理をページないしカラム単位で行う場合に比べて小さくなり、一方で、論理アドレスと物理アドレスの対応関係の管理が、ブロック単位で行う場合に比べきめ細かく行われる。
【００２７】
また、本発明の第３の観点に係るプログラムは、
ユーザデータを記憶するための記憶領域を形成する複数のメモリブロックを含み、各々のメモリブロックが複数のグループより構成されており、各々のグループが複数のページより構成されている記憶装置に接続されたコンピュータを、
前記グループの前記記憶領域内での物理的位置を指定する物理グループアドレスと当該グループの論理グループアドレスとの対応付けを表す論理物理変換テーブルを記憶する論理物理変換テーブル記憶手段と、
前記グループのうちからユーザデータを記憶可能な状態にある空きグループを特定して、特定した空きグループの物理グループアドレスを指示する書込ポインタを記憶する書込対象グループポイント手段と、
新たなユーザデータを書き込むグループの論理グループアドレス、当該グループに属するページ内において当該ユーザデータを書き込む記憶位置を指定するグループ内アドレス、及び、当該ユーザデータが自己に供給されたとき、当該ユーザデータを、前記書込ポインタにより指示された空きグループに属するページ内において当該グループ内アドレスが指定している記憶位置に書き込み、当該空きグループの物理グループアドレスと、供給された当該論理グループアドレスとの対応付けを表すよう前記論理物理変換テーブルを更新する書込手段と、
して機能させるためのものであることを特徴とする。
【００２８】
このようなプログラムを実行するコンピュータによれば、ユーザデータの書き込みはブロックより小さな単位で行われるので、ユーザデータを書き込む毎に新たな空きブロック（ユーザデータを記憶していないブロック）を探索して書き込むという操作が不要になり、ユーザデータの書き換え時にブロックに対して効率の悪いデータ消去（フラッシュイレース等）を行わずに済む。また、データの書き換えに伴って変更のない部分を転記する処理も、ブロックより小さな単位で行われる。従って、記憶装置の劣化が起きにくく、また記憶装置へのアクセスが円滑になる。
【００２９】
また、このようなプログラムを実行するコンピュータによれば、論理アドレスと物理アドレスとの対応関係の管理は、ブロックより小さく、ページないしカラムより大きな単位で行われる。このため、論理アドレスと物理アドレスとの対応関係を示すデータを格納するテーブルの記憶容量が、論理アドレスと物理アドレスの対応関係の管理をページないしカラム単位で行う場合に比べて小さくなり、一方で、論理アドレスと物理アドレスの対応関係の管理が、ブロック単位で行う場合に比べきめ細かく行われる。
【発明の効果】
【００３０】
この発明によれば、劣化が起きにくい記憶装置や、記憶装置の劣化を起こしにくいメモリ管理方法が実現される。
また、この発明によれば、記憶領域へのアクセスが円滑に行える記憶装置及びメモリ管理方法が実現される。
【発明を実施するための最良の形態】
【００３１】
以下、この発明の実施の形態を、フラッシュメモリを備えた記憶システムを例とし、図面を参照して説明する。
【００３２】
図１は、この発明の実施の形態にかかる記憶システムの物理的構成を示すブロック図である。
図示するように、この記憶システムは、メモリユニット１と、コンピュータ２とから構成されている。メモリユニット１は、コンピュータ２が備える内部バスを介して、コンピュータ２に装着されている。なお、例えば図１に示すように、メモリユニット１及びコンピュータ２が同一の筐体に組み込まれていてもよい。
【００３３】
メモリユニット１は、フラッシュメモリ１１及びコントローラ１２からなる。
【００３４】
フラッシュメモリ１１は、例えば、ＥＥＰＲＯＭ（Electrically Erasable/Programmable Read Only Memory）等の記憶装置と、論理回路等からなるシーケンサとより構成されている。
フラッシュメモリ１１は、コントローラ１２が行うアクセスに応答し、コンピュータ２から供給されたデータの記憶（書き込み）と、記憶しているデータの読み出し及びコンピュータ２への供給と、記憶しているデータの消去とを行う。
また、フラッシュメモリ１１は、データの書き込み、読み出し及び消去の動作それぞれについて、当該動作が行われている状態（ビジー状態）であるか否かを示す情報や、消去の動作が正常に行われたか否かを示すステータス情報などを生成してコントローラ１２へと供給する機能を行う。
【００３５】
図２及び図３は、フラッシュメモリ１１が有する記憶領域の構造の一例を示す図である。
フラッシュメモリ１１が有する記憶領域は、例えば図２に示すように１０２４個のブロックより構成されており、データの消去は、ブロックを単位として行われる。各ブロックには、先頭から連続的に０から１０２３までの物理ブロックアドレスが与えられている。
【００３６】
各々のブロックは、図２及び図３に示すように、例えば８個のグループを含んでいる。図２に示す例では、フラッシュメモリ１１の記憶領域全体は８１９２個のグループから構成される。
【００３７】
各グループには、フラッシュメモリ１１の記憶領域先頭から連続的に０から８１９１までの物理グループアドレスが与えられている。従って、例えば図３に示すように、物理ブロックアドレスがｎ（ｎは０以上１０２３以下の整数）であるブロックには、物理グループアドレスが（８・ｎ）以上｛（８・ｎ）＋７｝以下の８個のグループが含まれる。換言すれば、グループの物理グループアドレスを１３ビットの２進数で表記した場合、この２進数の上位１０ビットは、このグループが属するブロックの物理ブロックアドレスに相当する。
【００３８】
各々のグループは、図３に示すように例えば８個のページを含んでおり、各々のグループについて、当該グループ内の各ページには、当該グループ内の先頭のページから連続的に、０から７までのグループ内ページアドレスが付与されている。ページは、フラッシュメモリ１１が後述する動作により読み書きされるときに、コントローラ１２により、データ読み書きの単位として認識される単位である。
一方、フラッシュメモリ１１のそれぞれのページに含まれるメモリセルは、記憶容量が各１バイトである計２１１２個の記憶領域を構成しており、これらの記憶領域には、連続的に０から２１１１までの番地が与えられている。
【００３９】
なお、ページのグループ内ページアドレスを下位３ビットとし、当該ページが属するグループの物理グループアドレスの下位３ビットを上位３ビットとする計６ビットのアドレスは、当該ページが属するブロック内で当該ページに付与されたブロック内ページアドレスとして機能する。
【００４０】
各々のページは、図３に示すように、５２８バイトの記憶領域を有するカラム４個より構成されており、それぞれのページに含まれるカラムには、連続的に０から３までのカラムアドレスが与えられている。（従って、図２に示す例では、フラッシュメモリ１１の記憶容量は全体で１３２メガバイトである。）
【００４１】
それぞれのカラムは、図３に示すように、先頭から５１２バイトの領域を占めるデータ領域と、末尾１６バイトを占める冗長部とから構成される。
【００４２】
データ領域には、ユーザデータ（コンピュータ２から供給され書き込まれるデータや、コンピュータ２に供給される対象となるデータ）が格納される。
【００４３】
冗長部には、例えば、不良ブロックフラグや、旧グループフラグや、ＥＣＣ（エラー訂正コード）が格納される。
不良ブロックフラグは、この冗長部を含むブロックがデータを正常に格納することができないブロック（不良ブロック）であることを示すフラグである。
旧グループフラグは、この冗長部を含むカラムが属するグループ内のデータ領域に格納されているユーザデータが無効なデータとして扱われるべき古いデータ（以下、旧データと呼ぶ）であることを示すフラグである。
ＥＣＣは、この冗長部と同じカラムに属するデータ領域に格納されているユーザデータの内容が破壊されていないことを確認するためのデータである。
【００４４】
各々のカラムのデータ領域は、フラッシュメモリ１１が後述する動作により読み書きされる際、コンピュータ２においては、５１２バイトの記憶領域からなる単位であるセクタとして認識される。そして各々のセクタには、論理アドレスが割り当てられる。
【００４５】
セクタの論理アドレスは、例えば、当該セクタに相当するカラムが属するグループを示す上位の桁（論理グループアドレス）と、当該グループ内で当該カラムが属するページのグループ内ページアドレスに相当する中位の桁と、当該ページ内で当該カラムのカラムアドレスに相当する下位の桁と、からなっている。論理アドレスの総数は、フラッシュメモリ１１が物理的に備えるカラムの総数より小さい所定量であればよい。
【００４６】
なお、カラムの記憶位置は、カラムのカラムアドレスと、当該カラムが属するページのグループ内ページアドレスと、及び当該カラムが属するグループの物理グループアドレスとを用いても特定される。以下では、カラムのカラムアドレス、当該カラムが属するページのグループ内ページアドレス、及び当該カラムが属するグループの物理グループアドレスの３個より構成される、当該カラムを指定するデータを、当該カラムの物理アドレスと呼ぶ。
【００４７】
フラッシュメモリ１１は、メモリユニット１のコントローラ１２より、特定のブロックのデータを消去するよう指示されると、当該ブロックに含まれるすべてのメモリセルの記憶内容をフラッシュイレースする（具体的には、例えばフラッシュメモリ１１がＮＡＮＤ型のフラッシュメモリからなる場合は、各メモリセルの記憶値を“１”とする）。
【００４８】
また、フラッシュメモリ１１のデータ領域には、ディレクトリと、ＦＡＴ（File Allocation Table）とが格納され、後述する処理によって更新される。
【００４９】
図４は、フラッシュメモリ１１にＭＳ−ＤＯＳ（登録商標）のファイルシステムを適用した場合における、ディレクトリ、ＦＡＴ及び論理ブロックアドレスの相互の対応関係を例示する図である。
【００５０】
なお、ディレクトリ及びＦＡＴが格納されるカラムに相当するセクタには、所定の条件に合致する論理アドレスが付される。具体的には、例えば、論理アドレスとして先頭の４０９６個のアドレス（すなわち、０００００ｈ以上００ＦＦＦｈ以下のアドレス）が付される。（なお、本明細書及び図面において、末尾に“ｈ”が付された数字は１６進数である。）
【００５１】
ディレクトリは、フラッシュメモリ１１内に記憶されているファイル（すなわち、一括して扱う対象としてコンピュータ２が指定するデータの集合）のファイル名と、そのファイルの先頭部分が記憶されているセクタの論理アドレスとを示すテーブルである。
【００５２】
ＦＡＴは、フラッシュメモリ１１の記憶領域内でのファイルの配置を示すテーブルであり、ファイルが１つのカラム内に収まらないとき、図４に示すように、後続の部分を記憶するカラムの論理アドレスをそれぞれ示すものである。ファイルの最終部分が記憶されているカラムの論理アドレスは、図４に示すように、終了コード（ＥＣ）を付されることによって、その論理アドレスが最終部分を表すものであることが示される。
【００５３】
コントローラ１２は、図１に示すように、ＣＰＵ（Central Processing Unit）１２１と、ＲＯＭ（Read Only Memory）１２２と、ＲＡＭ（Random Access Memory）１２３とを備えている。ＲＡＭ１２３は、例えばバックアップされたＳＲＡＭ（Static RAM）やあるいはＦｅＲＡＭ（Ferroelectric RAM）などより構成されており、ＲＡＭ１２３の記憶領域の少なくとも一部は不揮発性の記憶領域を構成している。
【００５４】
ＣＰＵ１２１は、ＲＯＭ１２２、ＲＡＭ１２３、フラッシュメモリ１１及びコンピュータ２に接続されている。
ＣＰＵ１２１は、コントローラ１２の製造者等によって予めＲＯＭ１２２に格納されているプログラムの処理に従って、後述する処理を行う。
そして、ＣＰＵ１２１は、アクセス装置を構成するコンピュータ２から供給される命令を取得すると、その命令を実行する。ＣＰＵ１２１が実行する命令には、フラッシュメモリ１１にアクセスする命令が含まれる。
【００５５】
ＲＡＭ１２３が有する記憶領域は、ＣＰＵ１２１の作業領域として用いられ、また、一時記憶用領域を構成している。また、ＲＡＭ１２３の不揮発性の記憶領域は、ＣＰＵ１２１が後述する処理により作成するブロックステートテーブルと、論理物理変換テーブルと、書込ポインタと、書込ポインタ初期値と、移動先書込ポインタと、空きブロック数カウンタとを格納する。
【００５６】
一時記憶用領域は、後述するデータ書き込みの処理において、書き込みを行う対象のページを含むブロックに格納されているデータを一時的に格納するための記憶領域であり、フラッシュメモリ１１の１ページ分の記憶容量を有している。
【００５７】
ブロックステートテーブルは、例えば図５にデータ構造を模式的に示すように、フラッシュメモリ１１の記憶領域に含まれるそれぞれのブロックが、以下（１）〜（３）、（４ａ）及び（４ｂ）として示す状態、すなわち、
（１）  不良ブロック
（２）  不良ブロックでないブロックすなわち良品ブロックであって、当該良品ブロック内に、データが書き込まれているグループが存在しないブロック（空きブロック）
（３）  良品ブロックであって、当該良品ブロック内に、データが書き込まれているグループと書き込まれていないグループとが混在するブロック
（４ａ）  良品ブロックであって、当該良品ブロックに属するすべてのグループにデータが書き込まれており、書き込まれているこれらのデータのうちに、無効となった古いデータ（旧データ）が含まれていないブロック
（４ｂ）  良品ブロックであって、当該良品ブロックに書き込まれているデータのうちに旧データが含まれているブロック
のうちいずれの状態にあるかを特定する情報を、当該ブロックの物理ブロックアドレスと対応付けて格納する。（なお、図５において、（１）の状態を示すデータは「ＢＢ」、（２）の状態を示すデータは「ＥＢ」、（４ａ）の状態を示すデータは「ＵＷＯ」、（４ｂ）の状態を示すデータは「ＵＷＣ」として示されている。また、（３）の状態を示すデータは空白により示されている。）
ブロックステートテーブルは、例えばＲＡＭ１２３の不揮発性の記憶領域内に予め作成され、コントローラ１２の後述する処理に従って更新される。
【００５８】
なお、不良ブロックには、フラッシュメモリ１１の製造者等によって出荷前に不良と判断されたブロック（初期不良ブロック）と、フラッシュメモリ１１の使用中にデータの正常な格納ができないと判断されたブロック（後発不良ブロック）とがあり得る。
【００５９】
論理物理変換テーブルは、各々のグループについて、当該グループの論理グループアドレスと物理グループアドレスとの対応関係を示す情報を格納するものである。論理物理変換テーブルは、例えばＲＡＭ１２３の不揮発性の記憶領域内に予め作成され、ＣＰＵ１２１による後述の処理に従って更新される。
【００６０】
論理物理変換テーブルは、具体的には、例えば図６に示すデータ構造を有する。
すなわち、論理物理変換テーブルは、例えばＲＡＭ１２３の不揮発性の記憶領域内の所定の論理的位置を占め、各々の論理グループアドレスに対応付けられた物理グループアドレスを記憶するための記憶領域を備える。そして、論理グループアドレスの総数が８０００個であるとした場合、例えば、図示するように、先頭から１３ビット毎に付されたアドレスが１０００ｈ〜２Ｆ３Ｆｈである、合計１３０００バイトの記憶領域を備えていればよい。
【００６１】
論理物理変換テーブルが図６に示すデータ構造を有するとした場合、論理物理変換テーブルを形成する記憶領域に付された各々のアドレスは、論理グループアドレスと所定のオフセット値との和に等しい。（図６は、オフセット値が“１０００ｈ”である場合を例示するものである。）
そして、各々のアドレスを付された１３ビットの記憶領域に格納されている内容は、当該アドレスが示す論理グループアドレスに対応付けられているグループの物理グループアドレスを表す。
【００６２】
具体的には、例えば図６に示すように、アドレス１００１ｈを付された記憶領域に値“０１０Ｆｈ”（２進数“００００１００００１１１１”）が格納されており、オフセット値が１０００ｈであるとする。この場合は、物理グループアドレスが０１０Ｆｈであるグループには、論理グループアドレスとして０００１ｈが対応付けられている。
【００６３】
ただし、各々のアドレスを付された記憶領域に格納されている内容が所定の値を表す場合（例えば、図示するように、物理グループアドレスの値“１ＦＦＦｈ”を表す場合）は、その値を格納している記憶領域のアドレスが示す論理グループアドレスには、物理グループアドレスが対応付けられていないことを表す。
【００６４】
書込ポインタは、ＣＰＵ１２１がユーザデータを書き込むべきグループを指定する変数（ポインタ）であり、具体的には、該当するグループの物理グループアドレスを示しているものである。書込ポインタの値は、後述する処理に従って更新される。
【００６５】
書込ポインタ初期値は、上述の書込ポインタの最新の値を表すものであり、この記憶システムが起動後最初にフラッシュメモリ１１へのユーザデータの書き込みにおいてユーザデータを書き込むべきカラムがあるグループを指定するものとなる。
【００６６】
移動先書込ポインタは、ＣＰＵ１２１がブロック内のデータを消去して当該データの一部を他のブロックに移動させる際、移動先となるブロックを指定するポインタであり、具体的には、該当するブロック内のグループの物理グループアドレスを示しているものである。移動先書込ポインタの値は、後述する処理に従って更新される。なお、書込ポインタが移動先書込ポインタを兼ねていてもよい。
【００６７】
空きブロック数カウンタは、現存する空きブロックの数を示すデータである。空きブロック数カウンタの初期値は、例えばメモリユニット１の製造者などによりあらかじめＲＡＭ１２３の不揮発性の記憶領域に格納され、書込ポインタの値は、後述する処理に従って更新される。
【００６８】
コンピュータ２はパーソナルコンピュータ等からなり、ＯＳ及びドライバを表すプログラムデータを記憶し、電源投入後、ＯＳを実行する。そして、ＯＳの処理に従ってドライバを起動する。なお、コンピュータ２のプロセッサがＣＰＵ１２１の機能を兼ねて行ってもよい。
【００６９】
ドライバの処理を行うコンピュータ２は、コントローラ１２に上述の命令を供給したり、フラッシュメモリ１１に書き込む対象のデータを供給して、ＣＰＵ１２１に、フラッシュメモリ１１へのアクセスを行わせる。そして、自らが供給した命令に従ってＣＰＵ１２１がフラッシュメモリ１１から読み出して自らに供給したデータを、ＣＰＵ１２１より取得する。
【００７０】
（動作）
次に、この記憶システムの動作を、図７〜図１４を参照して説明する。
図７は、データ読み出しの処理を示すフローチャートである。
図８〜図１２は、データ書き込みの処理を示すフローチャートである。
図１３は、空きブロック確保の処理を示すフローチャートである。
図１４は、グループ登録の処理を示すフローチャートである。
【００７１】
（データ読み出しの処理）
この記憶システムが起動すると、メモリユニット１のＣＰＵ１２１は、コンピュータ２より、フラッシュメモリ１１へのアクセスを指示するための各種のコマンドを受け付ける状態に入る。
コンピュータ２は、ＣＰＵ１２１にフラッシュメモリ１１からのデータの読み出しを指示するときは、まず、所定の読出コマンドと、データを読み出す対象のセクタのうち先頭のセクタの論理アドレスと、読み出すセクタの数を示すデータとを、ＣＰＵ１２１に供給する（図７、ステップＳ２０１）。
【００７２】
読出コマンド、論理アドレス及びセクタの数からなるデータを供給されたＣＰＵ１２１は、供給されたこのデータを解釈してこのデータが読出コマンドを含むことを検出すると（ステップＳ２０２）、供給されたデータに含まれる論理アドレス及びセクタの数をＲＡＭ１２３の記憶領域に一時記憶させる。そして、一時記憶されている論理アドレス内の論理グループアドレスをキーとして論理物理変換テーブルを検索し、読み出す対象の先頭のセクタに相当するカラムが属するグループの物理グループアドレスを索出する。そして、索出した物理グループアドレスと、ステップＳ２０１で供給された論理アドレスに含まれるカラムアドレス及びグループ内ページアドレスとに基づいて、読み出す対象の先頭のセクタに相当するカラムの物理アドレスを特定する（ステップＳ２０３）。
【００７３】
次に、ＣＰＵ１２１は、ステップＳ２０３で特定したカラムよりデータを読み出す（ステップＳ２０４）。そして、読み出したデータのうちデータ領域に格納されていたデータに基づいてＥＣＣを生成し、生成したＥＣＣと、読み出したデータのうち冗長部に格納されていたＥＣＣとに基づいて、データ領域に格納されていたデータが正しく読み出されたか否かを判別する（ステップＳ２０５）。
【００７４】
ステップＳ２０５で、正しく読み出されたと判別すると、ＣＰＵ１２１は、データ領域に格納されていたデータをコンピュータ２に供給する（ステップＳ２１０）。
正しく読み出されていないと判別すると、ＣＰＵ１２１は、データ領域に格納されていたデータを正しい内容へと訂正することが可能か否かを、冗長部に格納されていたＥＣＣ等に基づいて判別する（ステップＳ２０６）。そして、訂正が可能であると判別すると、データ領域に格納されていたデータを訂正して（ステップＳ２０９）、コンピュータ２に供給する（ステップＳ２１０）。
【００７５】
ステップＳ２１０でデータ（カラムのデータ領域に格納されていたデータ又は当該データを訂正して得られるデータ）をコンピュータ２へと供給すると、ＣＰＵ１２１は、ステップＳ２０１で供給されたセクタの数に相当する数のカラムからのデータの読み出しを完了したか否かを判別する（ステップＳ２１１）。そして、完了したと判別するとデータ読み出しの処理を終了し（ステップＳ２１３）、完了していないと判別したときは、ＲＡＭ１２３に一時記憶されている論理アドレスをインクリメントして、次にデータを読み出す対象のセクタを示すようにしてから、処理をステップＳ２０３に戻す。
【００７６】
一方、データ領域から読み出したデータの訂正ができないとステップＳ２０６で判別すると、ＣＰＵ１２１は、訂正できない当該データを読み出したカラムが属するブロックが不良ブロックであることを表すように、ブロックステートテーブルの内容を更新する（ステップＳ２０７）。つまり、ブロックステートテーブル内でこのブロックのステータスを示す記憶位置に、「ＢＢ」を示すデータを格納する。また、ステップＳ２０７でＣＰＵ１２１は、データの読み取りに失敗したことをコンピュータ２に通知する。
【００７７】
コンピュータ２は、ステップＳ２０７でＣＰＵ１２１が発した通知を受けると、データ読み出しの処理を中断（異常終了）する（ステップＳ２０８）。
【００７８】
以上説明したステップＳ２０１〜Ｓ２１３の処理により、フラッシュメモリ１１よりデータが読み出され、コンピュータ２へと供給される。なお、読み出す対象のデータの論理アドレスはＦＡＴ及びディレクトリの内容に基づいて特定される必要があるため、コンピュータ２は、読み出す対象のデータの論理アドレスを供給するのに先立って、コンピュータ２は、ＦＡＴ及びディレクトリの読み出しをＣＰＵ１２１に行わせることとなる。
【００７９】
（データ書き込みの処理）
また、フラッシュメモリ１１へのデータの書き込みを行う場合、まずコンピュータ２は、ＣＰＵ１２１に、所定の書込コマンドと、データを書き込む対象のセクタのうち先頭のセクタの論理アドレスと、書き込むセクタの数を示すデータとを、ＣＰＵ１２１に供給する（図８、ステップＳ３０１）。
【００８０】
なお、古いデータを新しいデータに書き換える場合、古いデータの論理アドレスはＦＡＴ及びディレクトリの内容に基づいて特定される必要がある。また、データを新規に書き込む場合も、データが書き込まれていないセクタの論理アドレスがＦＡＴ及びディレクトリの内容に基づいて特定される必要がある。従って、コンピュータ２は、書き込む対象のセクタの先頭の論理アドレスを供給する場合も、これに先立ってコンピュータ２は、ＦＡＴ及びディレクトリの読み出しをＣＰＵ１２１に行わせることとなる。
【００８１】
書込コマンド、論理アドレス及びセクタの数からなるデータを供給されたＣＰＵ１２１は、このデータを解釈してこのデータが書込コマンドを含むことを検出すると（ステップＳ３０２）、供給されたデータに含まれる論理アドレス及びセクタの数をＲＡＭ１２３の記憶領域に一時記憶する。
【００８２】
次に、ＣＰＵ１２１は、書込ポインタが、ブロックの末尾のグループを指しているか否かを判別する（ステップＳ３０３）。そして、末尾以外を指していると判別すると処理をステップＳ３０５に移し、末尾を指していると判別すると、図１３に示す空きブロック確保の処理に移る（ステップＳ３０４）。そして、空きブロック確保の処理を終了すると、処理をステップＳ３０５に移す。
【００８３】
ステップＳ３０５でＣＰＵ１２１は、ＲＡＭ１２３に一時記憶されている論理アドレス内の論理グループアドレスをキーとして論理物理変換テーブルを検索する。そして、書き込む対象の先頭のセクタが属するグループの物理グループアドレスがあれば索出し、索出されたか否かを判別する（ステップＳ３０６）。
【００８４】
ステップＳ３０６で物理グループアドレスが索出されなかったと判別した場合は、データが新規に書き込まれる場合であると考えられる。この場合、ＣＰＵ１２１は、書込ポインタが現に指している物理グループアドレスと、ステップＳ３０１で供給された論理アドレスに含まれるカラムアドレス及びグループ内ページアドレスとに基づいて、書き込む対象の先頭のセクタに相当するカラムの物理アドレスを特定する。そして、書き込み対象のカラムより前にあるページ（つまり、物理アドレスを特定されたカラムが属するグループ内で当該カラムがあるページよりグループ内ページアドレスが小さなページ）に、所定のダミーデータを書き込む（ステップＳ３０７）。
そしてＣＰＵ１２１は、ＲＡＭ１２３の一時記憶用領域の全域に、所定のダミーデータを書き込む（ステップＳ３０８）。
【００８５】
一方、ステップＳ３０６で物理グループアドレスが索出されたと判別した場合は、新たに書き込むデータに置き換えられて旧データとなるべき古いデータがフラッシュメモリ１１に記憶されている場合であると考えられる。この場合、ＣＰＵ１２１は、索出された物理グループアドレスと、ステップＳ３０１で供給された論理アドレスに含まれるカラムアドレス及びグループ内ページアドレスとに基づいて、この古いデータが格納されている先頭のセクタに相当するカラムの物理アドレスを特定する。そして、当該カラムより前にあるページに格納されているデータがあれば、該当するデータを、書込ポインタが指し示すグループ内の空いているページに転記する（ステップＳ３３１）。
そしてＣＰＵ１２１は、一時記憶用領域に、ステップＳ３３１で特定したカラムを含む１ページのデータを転記する（ステップＳ３３２）。
【００８６】
ステップＳ３０８又はＳ３３２の処理を行ったＣＰＵ１２１は、フラッシュメモリ１１に書き込むべき１セクタ分以内のデータがコンピュータ２から供給されるのを待機する（図９、ステップＳ３０９又は図１１、Ｓ３３３）。そして、フラッシュメモリ１１に書き込むデータがコンピュータ２から供給されると（ステップＳ３１０又はＳ３３４）、ＣＰＵ１２１は、このデータを、一時記憶用領域のうち、カラムのデータ領域に相当する記憶位置に上書きする（ステップＳ３１１又はＳ３３５）。
【００８７】
ただし、ステップＳ３０１で供給されたデータが示す先頭セクタが、ページの先頭からｎ番目（ｎは１から４までの整数）のカラムに相当するセクタであるとして、ステップＳ３１１又はＳ３３５での上書きは、一時記憶用領域の先頭からカラム（ｎ−１）個分の記憶領域より後ろの記憶位置に行うものとする。
【００８８】
次に、ＣＰＵ１２１は、ステップＳ３１０又はＳ３３４で供給された１セクタ分以内のデータが、一時記憶用領域の末尾まで上書きされたか否かを判別する（ステップＳ３１２又はＳ３３６）。末尾まで上書きされていない場合とはつまり、一時記憶用領域内に、フラッシュメモリ１１に書き込むべきデータがまだ格納されていない部分が残っている場合である。
【００８９】
そしてＣＰＵ１２１は、一時記憶用領域の末尾まで書き込まれていないと判別すると処理をステップＳ３１２からステップＳ３１４へ（又は、ステップＳ３３６からステップＳ３３８へ）と進める。一方、一時記憶用領域の末尾まで書き込まれたと判別すると、一時記憶用領域に格納されているデータを、書込ポインタが指し示すグループ中、最後に書き込みを行ったページの次のページに書き込んで、一時記憶領域内のデータをすべてクリアする（ステップＳ３１３又はＳ３３７）。ステップＳ３１３で初めて書き込みを行う場合は更に、ブロックステートテーブルを更新して、書き込み先のページが属するブロックが状態（３）であることを示すようにする。
【００９０】
次に、ＣＰＵ１２１は、ステップＳ３０１で供給されたセクタの数に相当する数のカラムへのデータの書き込みを完了したか否かを判別する（ステップＳ３１４又はＳ３３８）。
そして、書き込みが完了したと判別すると、ＣＰＵ１２１は、処理をステップＳ３１４からステップＳ３１８へ（又は、ステップＳ３３８からステップＳ３４２へ）と移す。
【００９１】
一方、書き込みが完了していないとステップＳ３１４又はＳ３３８で判別したとき、ＣＰＵ１２１は、ＲＡＭ１２３に一時記憶されている論理アドレスをインクリメントして（ステップＳ３１５又はＳ３３９）、次にデータを書き込む対象のセクタを示すようにする。
【００９２】
次に、ＣＰＵ１２１は、インクリメント後の新たな論理アドレスが指し示すセクタが、インクリメント前の論理アドレスが指し示すセクタと共通のグループに属するか否かを判別し（ステップＳ３１６又はＳ３４０）、属すると判別すると、ステップＳ３１６からステップＳ３０９へ（又は、ステップＳ３４０からステップＳ３３３へ）と処理を戻す。
一方、属さない（すなわち、データの書き込みが複数のグループを跨いで行われる）と判別すると、インクリメント前の論理アドレスが示すセクタに相当するページを含むグループを登録対象のグループとして、図１４に示すグループ登録の処理を行う（ステップＳ３１７又はＳ３４１）。そして、グループ登録の処理を終えると、処理をステップＳ３０３へ戻す。
【００９３】
一方、ステップＳ３１８（図１０）又はＳ３４２（図１２）でＣＰＵ１２１は、ステップＳ３１０又はＳ３３４の処理でコンピュータ２より最後に供給された（１ページ分未満の量の）書き込み対象のデータが一時記憶用領域に格納されているか否かを判別する。そして、格納されていない（クリアされている）と判別すると処理をステップＳ３１８からステップＳ３２１へ（又は、ステップＳ３４２からステップＳ３４５へ）と移す。
一方、格納されている（クリアされていない）と判別すると、一時記憶用領域のうち、該当する書き込み対象のデータが格納されていない部分に所定のダミーデータを格納し（ステップＳ３１９）、又は、ステップＳ３３７で最後に旧データとされたデータがあるカラムに後続するカラムに格納されているデータを当該部分に転記する（ステップＳ３４３）。
そしてＣＰＵ１２１は、一時記憶用領域に格納されているデータを、書込ポインタが指し示すブロック中、最後に書き込みを行ったページの次のページに書き込む（ステップＳ３２０又はＳ３４４）。
【００９４】
次に、ＣＰＵ１２１は、ステップＳ３２０又はＳ３４４でデータを書き込んだページがグループの末尾のページであるか否かを、ＲＡＭ１２３に一時記憶されている論理アドレスなどに基づいて判別する（ステップＳ３２１又はＳ３４５）。そして、グループの末尾のページではないと判別すると、ＣＰＵ１２１は、所定のダミーデータ１ページ分を一時記憶用領域に書き込み（Ｓ３２２）、又は、ステップＳ３４３若しくはＳ３４６で最後に転記したデータがあるカラムに後続するカラムに格納されているデータ１ページ分を転記する（ステップＳ３４６）。
【００９５】
次にＣＰＵ１２１は、一時記憶用領域に格納されているデータを、書込ポインタが指し示すブロック中、最後に書き込みを行ったページの次のページに書き込み（ステップＳ３２３又はＳ３４７）、処理をステップＳ３２３からステップＳ３２１へ（又は、ステップＳ３４７からステップＳ３４５へ）と戻す。
【００９６】
一方、ＣＰＵ１２１は、グループの末尾のページであるとステップＳ３２１又はＳ３４５で判別すると、当該末尾のページを含むグループを登録対象のグループとして、上述のグループ登録の処理を行う（ステップＳ３２４又はＳ３４８）。そして、グループ登録の処理を終えると、データ書き込みの処理も終了する。
【００９７】
（空きブロック確保の処理）
次に、空きブロック確保の処理を説明する。空きブロック確保の処理において、まずＣＰＵ１２１は、フラッシュメモリ１１の空きブロックが所定数以上あるか否かを、空きブロック数カウンタの値に基づいて判別する（図１３、ステップＳ４０１）。そして、所定数以上あると判別すると処理をステップＳ４０９に移し、所定数未満であると判別すると、処理をステップＳ４０２に移す。
【００９８】
ステップＳ４０２でＣＰＵ１２１は、良品ブロックである空きブロック１個を、空きブロック検索位置ポインタに基づいて特定し、特定した空きブロック内の先頭のグループの物理グループアドレスを、移動先書込ポインタにセットする。そして、空きブロック数カウンタの値を１だけデクリメントする。また、ＣＰＵ１２１は、他の空きブロック１個を索出して、この空きブロックの物理ブロックアドレスを空きブロック検索位置ポインタにセットする。
【００９９】
次に、ＣＰＵ１２１は、ブロックステートテーブルに基づいて、上述の（４ｂ）の状態にあるブロック（ブロックステートテーブルに「ＵＷＣ」と示されているブロック）を特定し、特定したこれらのブロックのうちから、新たに空きブロックとする対象のブロック（整理対象ブロック）を１個以上決定する（ステップＳ４０３）。
【０１００】
次に、ＣＰＵ１２１は、ステップＳ４０３で決定した整理対象ブロックに含まれるグループのうち、データを有効に格納しているグループに格納されているデータを、移動先書込ポインタが指す空きブロックに転記する（ステップＳ４０４）。なお、ステップＳ４０４でＣＰＵ１２１は、整理対象ブロックに含まれるグループのうち、後述するグループ登録の処理で冗長部に旧グループフラグを格納されたカラムを含まないグループを、データ有効に格納しているグループとして扱うものとすればよい。また、ステップＳ４０４でＣＰＵ１２１は、論理物理変換テーブルを更新し、データが転記されたグループの論理グループアドレスが、転記先の記憶位置が属するグループの物理グループアドレスに対応付けられるようにする。
【０１０１】
整理対象ブロックから空きブロックへのデータの転記が完了すると、ＣＰＵ１２１は、整理対象ブロックをフラッシュイレースして空きブロックにし（ステップＳ４０５）、フラッシュメモリ１１よりステータス情報を取得する等して、この整理対象ブロックが正常に空きブロックになったか否かを判別する（ステップＳ４０６）。そして、空きブロックになっていなければ、ブロックステートテーブルの内容を、この整理対象ブロックが不良ブロックであることを表すように更新する（ステップＳ４０７）。つまり、ブロックステートテーブル内でこの整理対象ブロックのステータスを示す記憶位置に、「ＢＢ」を示すデータを格納する。そして、ＣＰＵ１２１は処理をステップＳ４０１に戻す。
【０１０２】
一方、正常に空きブロックになっているとステップＳ４０６で判別した場合、ＣＰＵ１２１は、ブロックステートテーブルの内容を、この整理対象ブロックが空きブロックであることを表すように更新する（ステップＳ４０８）。つまり、ブロックステートテーブル内でこの整理対象ブロックのステータスを示す記憶位置に、「ＥＢ」を示すデータを格納する。また、ステップＳ４０８でＣＰＵ１２１は、空きブロック数カウンタの値を、正常に空きブロックになった整理対象ブロックの数だけインクリメントする。そして、ＣＰＵ１２１は処理をステップＳ４０１に戻す。
【０１０３】
そして、ステップＳ４０８の処理が１回又は数回行われる結果、空きブロック数が所定数以上にまで増加すると、上述の通りＣＰＵ１２１は、処理をステップＳ４０１からステップＳ４０９へと移す。
【０１０４】
ステップＳ４０９でＣＰＵ１２１は、ブロックステートテーブルを検索することにより、新たにデータの書き込みを行う対象の空きブロックを１個特定する。そして、特定したブロック内の先頭のグループの物理グループアドレスの値を、書込ポインタにセットし（ステップＳ４１０）、空きブロック確保の処理を終了する。
【０１０５】
なお、ステップＳ４０９では、フラッシュメモリ１１の各ブロックからデータを読み出すことによって空きブロックを特定してもよい。しかし、各ブロックからデータを読み出す代わりに、ブロックステートテーブルを検索することによって空きブロックを特定した方が空きブロックの特定が迅速に行われ、また、フラッシュメモリ１１へのアクセス数が抑えられるのでフラッシュメモリ１１の劣化を防止できる。
【０１０６】
（グループ登録の処理）
次に、グループ登録の処理を説明する。グループ登録の処理において、まずＣＰＵ１２１は、登録対象のグループの物理グループアドレスが論理物理変換テーブルに登録されているか否かを判別する（図１４、ステップＳ５０１）。
【０１０７】
そして、登録されていると判別すると、ＣＰＵ１２１は、ブロックステートテーブルの内容を更新し、登録されていたこの物理グループアドレスが示すグループを含むブロックが上述の（４ｂ）の状態にあることを表すように更新する（ステップＳ５０２）。
また、ステップＳ５０２でＣＰＵ１２１は、データの転記ないし更新が行われた場合、新たに旧データとなったデータ（例えば転記元のデータや更新前のデータ）を格納しているグループ内のカラムの冗長部に旧グループフラグを書き込み、また、当該旧データに代わる新しいデータ（例えば転記先のデータや更新後のデータ）を格納しているグループの物理グループアドレスを、論理物理変換テーブルに登録し直す。つまり、論理物理変換テーブル内に格納されている、旧データとなったデータのあるグループの物理グループアドレスを、新たなデータのあるグループの物理グループアドレスに書き換える。
【０１０８】
一方、登録されていないと判別すると、ＣＰＵ１２１は、登録されていなかった当該物理グループアドレスを、論理物理変換テーブルに登録する（ステップＳ５０３）。つまり、当該物理グループアドレスを、論理物理変換テーブル内の、新たな論理アドレスに含まれる論理グループアドレスに対応付けられた記憶位置に格納する。
【０１０９】
物理グループアドレスを論理物理変換テーブルに登録すると、ＣＰＵ１２１は、登録したこの物理グループアドレスが示すグループを含むブロックが空きブロックとしてブロックステートテーブルに登録されているか否かを判別する（ステップＳ５０４）。そして、空きブロックではないブロックとして登録されていれば、グループ登録の処理を終了する。
【０１１０】
一方、空きブロックとして登録されていれば、ブロックステートテーブル内の当該ブロックのステータスを示す記憶位置に、「ＵＷＯ」を示すデータを格納して（ステップＳ５０５）、グループ登録の処理を終了する。ステップＳ５０５の処理の結果、登録した物理グループアドレスが示すグループを含むブロックが上述の（４ａ）の状態にあることを表すように、ブロックステートテーブルが更新される。
【０１１１】
以上説明した処理により、コンピュータ２から供給されたデータがフラッシュメモリ１１に格納される。また、ブロックステートテーブルの内容が、データの書き込みの結果新たに生じたブロックの状態を反映した内容へと変更される。一方、論理物理変換テーブルの内容も変更され、新たに空きブロックとなったブロック内のグループに割り当てられていた論理グループアドレスが、当該グループの内容を転記された他のグループに新たに割り当てられる。
【０１１２】
この記憶システムは、ユーザデータが格納されていないグループの数が十分にあるうちはブロックのフラッシュイレースを行わないので、無用のフラッシュイレースが避けられる。このため、ブロック１個当たりの記憶容量が大きい場合であっても、フラッシュメモリ１１の劣化が起きにくく、またデータの退避に要する処理も少なくなるのでフラッシュメモリ１１へのアクセスが円滑になる。
【０１１３】
また、この記憶システムでは、ユーザデータの書き込みはブロックより小さな単位で行われるので、ユーザデータを書き込む毎に新たな空きブロックを探索して書き込むという操作が不要になり、ユーザデータの書き換え時にブロックに対して効率の悪いフラッシュイレースを行わずに済む。また、データの書き換えに伴って変更のない部分を転記する処理も、ブロックより小さな単位で行われる。従って、フラッシュメモリ１１の劣化が起きにくく、またフラッシュメモリ１１へのアクセスが円滑になる。
【０１１４】
また、この記憶システムでは、論理アドレスと物理アドレスとの対応関係の管理は、ブロックより小さく、ページないしカラムより大きな単位で行われる。このため、論理アドレスと物理アドレスとの対応関係を示すデータを格納するテーブルの記憶容量を、論理アドレスと物理アドレスの対応関係の管理をページないしカラム単位で行う場合に比べて小さくすることができ、一方で、論理アドレスと物理アドレスの対応関係の管理をブロック単位で行う場合に比べきめ細かく行うことにより、多数のファイルを記憶することができる。
【０１１５】
また、データを書き込むグループは書込ポインタにより物理グループアドレス順に指定されるので、特定のブロックに書き込みが集中することが避けられ、従って、書き込みが集中したブロックにフラッシュイレースの機会が集中することが避けられる。この点も、フラッシュメモリ１１の劣化防止に寄与する。
【０１１６】
なお、この記憶システムの構成は、上述のものに限られない。
例えば、フラッシュメモリ１１の記憶領域のブロックの数、１ブロック当たりのグループの数、１グループ当たりのページの数、各ページの記憶容量、データ領域及び冗長部の記憶容量は、いずれも任意である。また、フラッシュメモリ１１は、ＥＥＰＲＯＭから構成されるものである必要はなく、コンピュータにより読み書き可能な任意の記憶装置であってよい。また、ディレクトリ及びＦＡＴが格納されるカラムの論理アドレスは上述の値である必要はなく、また、ディレクトリ及びＦＡＴが格納されるカラムの個数も任意である。また、１個のカラムのデータ領域及び冗長部が互いに隣接している必要はなく、従って、フラッシュメモリ１１の記憶領域は、たとえば、４個のカラムのデータ領域が１個のページ内で先頭から４個連続し、次いでこれら４個のカラムの冗長部が４個連続する、といった構造を有していてもよい。
【０１１７】
また、ＣＰＵ１２１は、ブロックステートテーブルの更新を必ずしもユーザデータの書き込みの後で行う必要はなく、ユーザデータを書き込むことによって各ブロックの状態がどのように変化するかが決定された後であれば、ユーザデータの書き込みの前にブロックステートテーブルの更新を行うようにしてもよい。
【０１１８】
また、ＣＰＵ１２１は、必ずしも内部バスを介してコンピュータ２に接続されるものでなくてもよく、ＰＣカードスタンダードに準拠したバス、ＩＥＥＥ１３９４インターフェース、ＵＳＢ（Universal Serial Bus）あるいはその他の任意のインターフェースを介してコンピュータ２に接続されていてもよい。また、ＣＰＵ１２１は必ずしもコンピュータ２に有線接続される必要はなく、例えばBluetooth等の規格に準拠したインターフェースを介してコンピュータ２に無線接続されるものであってもよい。
【０１１９】
また、論理物理変換テーブルは、物理グループアドレスの全桁を格納している必要はなく、例えば、物理グループアドレスのうち下位の所定桁数だけを仮物理グループアドレスとして格納するようにしてもよい。論理物理変換テーブルが物理グループアドレスの全桁に代えてこのような仮物理グループアドレスを格納するようにすれば、物理グループアドレス全桁を格納する場合に比べて、論理物理変換テーブルのデータ量は小さくなる。従って、論理物理変換テーブルを格納するＲＡＭ１２３の記憶容量も小さくて済み、この記憶システムを小型に構成できるようになる。
【０１２０】
また、ＲＡＭ１２３は、ステップＳ４０３で整理対象ブロックとして特定されるべきブロックの物理ブロックアドレスを指す整理対象ブロックポインタを記憶してもよい。この場合、ステップＳ４０３でＣＰＵ１２１は、整理対象ブロックポインタが現に指している物理ブロックアドレスを与えられたブロックを整理対象ブロックと決定した後、当該物理ブロックアドレス以降の状態（４ｂ）のブロックの物理ブロックアドレスをサイクリックにセットするようにしてもよい。すなわち、整理対象ブロックポインタが現に指している物理ブロックアドレスより大きな値を有する状態（４ｂ）のブロックの物理ブロックアドレスのうち値が最も小さいもの（ただし、該当するものがなければ、状態（４ｂ）のブロックの物理ブロックアドレス全体のうち値が最も小さいもの）を、次回に整理対象ブロックとして決定されるべきブロックの物理ブロックアドレスとして、整理対象ブロックポインタにセットすればよい。
このように、各ブロックが、書き込まれているデータが古い順にフラッシュイレースの対象となっていけば、ブロックがフラッシュイレースされる頻度が均等になる。従って、特定のメモリブロックが集中的に劣化することによりフラッシュメモリ１１全体の寿命が短くなる、ということが防止される。
【０１２１】
また、ＲＡＭ１２３は、ステップＳ４１０で特定されるべき空きブロックの物理ブロックアドレスを指す空きブロック検索位置ポインタを記憶してもよい。この場合、ステップＳ４０９でＣＰＵ１２１は、空きブロック検索位置ポインタが現に指している物理ブロックアドレスを与えられた空きブロックを特定し、ステップＳ４１０では、空きブロック検索位置ポインタが現に指している物理ブロックアドレス以降の空きブロックの物理ブロックアドレスをサイクリックにセットするようにしてもよい。このような構成をとれば、ブロックに書き込みがなされる頻度も均等になり、従って、特定のメモリブロックの集中的な劣化が防止される。
【０１２２】
仮物理グループアドレスが、物理グループアドレスのうち下位の所定桁数だけからなる場合、例えば、フラッシュメモリ１１のグループは複数のゾーンのいずれかへと分類されているものとし、物理グループアドレスのうちこの下位の所定桁数を除いた上位の桁は、グループが属すゾーンを示すものとする。なお、個々のゾーンの記憶容量の大きさはブロック１個分より大きくても小さくてもよく、ブロック１個分と等しくてもよい。また、ゾーンがブロックに一致していてもよい。
【０１２３】
そして、グループが複数のゾーンのいずれかへと分類されている場合、各々の論理グループアドレスはいずれか１つのゾーンに属するグループに割り当てられるものとする。従って、グループに与えられた論理グループアドレスに基づいて、このグループが属するゾーンを特定することができる。
【０１２４】
グループが複数のゾーンのいずれかへと分類されている場合、ＣＰＵ１２１は、データの読み書きの対象となるファイルがあるカラムを特定するため、論理物理変換テーブルを参照して、このカラムの論理アドレスに含まれる論理グループアドレスに対応付けられている仮物理グループアドレス（物理グループアドレスの下位の桁）を特定し、一方、この論理グループアドレスに基づいて、このカラムが属するゾーンも特定する。次に、ＣＰＵ１２１は、特定したゾーン、特定した仮物理グループアドレス、及びこのカラムが属するページのグループ内ページアドレスにより構成される物理アドレスが示すカラムにアクセスする。
【０１２５】
また、この記憶システムは、論理物理変換テーブルをフラッシュメモリ１１が記憶するようにしてもよい。この場合、ＲＡＭ１２３に、論理物理変換テーブルを構成するデータが格納されているカラム（以下、論理物理変換テーブル格納カラムと呼ぶ）の位置を示す論理物理変換テーブルカラムリストを予め記憶するようにしてもよい。
【０１２６】
論理物理変換テーブルカラムリストは、具体的には、例えば、論理物理変換テーブル格納カラムの論理アドレス（以下、論理物理変換テーブル格納カラムポインタと呼ぶ）と、当該論理物理変換テーブル格納カラムの物理アドレスを、互いに対応付けて格納するテーブルからなる。
【０１２７】
一方、ＣＰＵ１２１は、論理物理変換テーブルを構成するデータを論理物理変換テーブル格納カラムに格納する際、例えばこの論理物理変換テーブル格納カラムの冗長部に、この論理物理変換テーブル格納カラムに割り当てられた論理物理変換テーブル格納カラムポインタを格納するものとする。
【０１２８】
ＲＡＭ１２３が論理物理変換テーブルカラムリストを記憶している場合、ＣＰＵ１２１は、データ読み出しの処理において論理物理変換テーブルを参照するため、ステップＳ２０７の処理を行う代わりに、例えばまず、ＲＡＭ１２３から論理物理変換テーブルカラムリストを読み出す。次に、この論理物理変換テーブルカラムリストに含まれる論理物理変換テーブル格納カラムポインタに対応付けられている物理アドレスが示すカラムから論理物理変換テーブルの内容を読み出し、読み出した論理物理変換テーブルを用いて物理グループアドレスの特定を行う。
【０１２９】
フラッシュメモリ１１が論理物理変換テーブルを記憶している場合、ＣＰＵ１２１は、データ書き込みの処理等において論理物理変換テーブルの内容を更新する場合は、フラッシュメモリ１１から論理物理変換テーブルを読み出し、ＲＡＭ１２３に一時記憶させ、ＲＡＭ１２３に一時記憶されたこの論理物理変換テーブルの内容を更新して、書き換えが終わった論理物理変換テーブルを、書込ポインタが指しているグループに書き込むものとする。また、論理物理変換テーブルをなすデータを新たに書き込まれた各カラムの物理アドレスを、このデータが従前書き込まれていたカラムを指し示す論理物理変換テーブル格納カラムポインタに対応付けた形で、論理物理変換テーブルカラムリストに格納するものとし、一方、この論理物理変換テーブル格納カラムポインタに従前対応付けられていた物理アドレスは、論理物理変換テーブルカラムリストから削除するものとする。
【０１３０】
また、論理物理変換テーブル格納ページに対応付けられる論理物理変換テーブルカラムポインタの値は、この論理物理変換テーブル格納カラムに格納されているデータが、論理物理変換テーブルのうち、どの範囲の論理グループアドレスを示す部分かを指定するものであってもよい。この場合、ＣＰＵ１２１は、論理物理変換テーブルのうち、読み書きの対象となるファイルの内容を含むカラムが属するグループの論理グループアドレスを含む部分を論理物理変換テーブルカラムリストの内容に基づいて特定し、特定した部分のみをフラッシュメモリ１１から読み出してＲＡＭ１２３に一時記憶させ、一時記憶された当該部分を論理物理変換テーブルとして扱うようにすればよい。
このような処理を行うものとすれば、論理物理変換テーブルを参照するたびにフラッシュメモリ１１から論理物理変換テーブルの全体を逐一読み出す、という操作を要しないので、論理物理変換テーブルの参照に要する時間が短くなる。
【０１３１】
また、この記憶システムは、ブロックステートテーブルをフラッシュメモリ１１が記憶するようにしてもよい。この場合、ＣＰＵ１２１は、ＲＡＭ１２３に、ブロックステートテーブルを構成するデータが格納されているカラム（以下、ブロックステートテーブル格納カラムと呼ぶ）の位置を示すブロックステートテーブルカラムリストを記憶させるようにしてもよい。
【０１３２】
ブロックステートテーブルカラムリストは、具体的には、例えば、ブロックステートテーブル格納カラムの論理アドレス（以下、ブロックステートテーブルページポインタと呼ぶ）と、当該ブロックステートテーブル格納カラムの物理アドレスとを、互いに対応付けて格納するテーブルからなる。
【０１３３】
一方、ＣＰＵ１２１は、ブロックステートテーブルの一部をブロックステートテーブル格納カラムに格納する際、たとえばこのブロックステートテーブル格納カラムの冗長部に、このブロックステートテーブル格納カラムに割り当てられたブロックステートテーブルカラムポインタを格納するものとする。
【０１３４】
フラッシュメモリ１１がブロックステートテーブルを記憶している場合において、ＣＰＵ１２１は、データ書き込みの処理等においてブロックステートテーブルの内容を更新する場合、フラッシュメモリ１１からブロックステートテーブルを読み出し、ＲＡＭ１２３に一時記憶させ、一時記憶されたこのブロックステートテーブルの内容を更新して、書き換えが終わったブロックステートテーブルを、書込ポインタが指しているグループに書き込むものとすればよい。
また、ＣＰＵ１２１は、ブロックステートテーブルを構成するデータを新たに書き込まれた各カラムの物理アドレスを、このデータが従前書き込まれていたカラムを指し示すブロックステートテーブル格納カラムポインタに対応付けた形で、ブロックステートテーブルカラムリストに格納する一方、このブロックステートテーブル格納カラムポインタに従前対応付けられていた物理アドレスは、ブロックステートテーブルカラムリストから削除するものとすればよい。
【０１３５】
なお、ブロックステートテーブルを構成するデータが、上述したゾーンのうちいずれか所定のゾーンにのみ格納される場合、ブロックステートテーブルカラムリストには、このデータを格納するブロックステートテーブル格納カラムが属するグループの物理グループアドレスに代えて、このブロックステートテーブル格納カラムが属するグループの当該ゾーン内での位置を示す仮物理グループアドレスを格納するようにしてもよい。ブロックステートテーブルカラムリストが、ブロックステートテーブル格納カラムが属するグループの物理グループアドレスの全桁に代えて仮物理グループアドレスを格納するようにすれば、物理グループアドレス全桁を格納する場合に比べて、ブロックステートテーブルカラムリストのデータ量は小さくなる。従ってＲＡＭ１２３の記憶容量も小さくて済み、この記憶システムを小型に構成できるようになる。
【０１３６】
また、ブロックステートテーブル格納ページに対応付けられるブロックステートテーブルカラムポインタの値は、このブロックステートテーブル格納カラムに格納されているデータが、ブロックステートテーブルのうち、どの範囲の論理アドレスを示す部分かを指定するものであってもよい。この場合、ＣＰＵ１２１は、ブロックステートテーブルのうち、読み書きの対象となるファイルの内容を含むカラムの論理アドレスを含む部分をブロックステートテーブルカラムリストの内容に基づいて特定し、特定した部分のみをフラッシュメモリ１１から読み出してＲＡＭ１２３に一時記憶させ、一時記憶された当該部分をブロックステートテーブルとして扱うようにすればよい。
このような処理を行うものとすれば、ブロックステートテーブルを参照するたびにフラッシュメモリ１１からブロックステートテーブルの全体を逐一読み出す、という操作を要しないので、ブロックステートテーブルの参照に要する時間が短くなる。
【０１３７】
また、ブロックステートテーブルのデータ構造も上述のものに限られず、ブロックステートテーブルは例えば、フラッシュメモリ１１の記憶領域に含まれるそれぞれのブロックが空きブロックであるか否かを示す１ビットの情報を、当該ブロックの物理ブロックアドレスと対応付けて格納するものであってもよい。
ただしこの場合、ブロックが上述の（３）、（４ａ）あるいは（４ｂ）の状態にあるか否かを判別可能とするため、ＣＰＵ１２１は例えば、ユーザデータの書き込みを行う際には書き込みの対象となるカラムの冗長部に、ユーザデータの書き込みが行われていることを示す所定の識別用データ（例えば、当該カラムの論理アドレスなど）を書き込むものとする。そしてＣＰＵ１２１は、ブロックが上述の（３）、（４ａ）あるいは（４ｂ）の状態にあるか否かを判別する場合は、当該ブロック内でこれらの識別用データや上述の旧グループフラグを検索することにより、当該判別を行うものとする。
【０１３８】
なお、ユーザデータが書き込まれている各カラムの冗長部に当該カラムの論理アドレスが書き込まれる場合、ＣＰＵ１２１は、冗長部に書き込まれたこれらの論理アドレスを読み出して論理グループアドレスを抽出することにより、当該カラムが属するグループの論理グループアドレスと物理グループアドレスとの対応関係を特定することができる。従ってＣＰＵ１２１は、例えばこの記憶システムの起動直後等に、フラッシュメモリ１１の各カラムの冗長部に書き込まれた論理アドレスを読み出し、読み出した内容に基づいて論理物理変換テーブルを新規に作成してＲＡＭ１２３に記憶させるようにしてもよい。この場合、ＲＡＭ１２３は、論理物理変換テーブルを格納する不揮発性の記憶領域を提供するための不揮発性メモリを備えている必要はない。
【０１３９】
また、ＣＰＵ１２１は例えば、ブロックのフラッシュイレースを行った際に、新たに空きブロックとなったブロック内のカラムの冗長部に、所定の空きブロックコードを書き込むものとしてもよい。この場合、ＣＰＵ１２１は、冗長部に書き込まれた空きブロックコードを検索することにより空きブロックを特定することができる。従ってＣＰＵ１２１は、例えばこの記憶システムの起動直後等に、フラッシュメモリ１１の各カラムの冗長部に書き込まれた空きブロックコードを検索し、検索結果に基づいてブロックステートテーブルを新規に作成してＲＡＭ１２３に記憶させるようにしてもよい。（ただしこの場合のブロックステートテーブルは、フラッシュメモリ１１の記憶領域に含まれるそれぞれのブロックが空きブロックであるか否かを示す１ビットの情報を、当該ブロックの物理ブロックアドレスと対応付けて格納するものであるとする。）
なお、ＣＰＵ１２１がブロックステートテーブルを新規に作成する処理を行うものである場合、ＲＡＭ１２３は、ブロックステートテーブルを格納する不揮発性の記憶領域を提供するための不揮発性メモリを備えている必要はない。
【０１４０】
以上、この発明の実施の形態を説明したが、この発明の記憶システムは、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。例えば、フラッシュメモリ１１を装着するスロットを備えるパーソナルコンピュータに上述の動作を実行するためのプログラムを格納した媒体（フレキシブルディスク、ＣＤ−ＲＯＭ等）から該プログラムをインストールすることにより、上述の処理を実行する記憶システムを構成することができる。
【０１４１】
また、例えば、通信回線のＢＢＳに該プログラムをアップロードし、これらを通信回線を介して配信してもよく、また、該プログラムを表す信号により搬送波を変調し、得られた変調波を伝送し、この変調波を受信した装置が変調波を復調して該プログラムを復元するようにしてもよい。
そして、該プログラムを起動し、ＯＳの制御下に、他のアプリケーションプログラムと同様に実行することにより、上述の処理を実行することができる。
【０１４２】
なお、ＯＳが処理の一部を分担する場合、あるいは、ＯＳが本願発明の１つの構成要素の一部を構成するような場合には、記録媒体には、その部分を除いたプログラムを格納してもよい。この場合も、この発明では、その記録媒体には、コンピュータが実行する各機能又はステップを実行するためのプログラムが格納されているものとする。
【図面の簡単な説明】
【０１４３】
【図１】本発明の実施の形態にかかる記憶システムの構成を示すブロック図である。
【図２】フラッシュメモリの記憶領域の論理的構造を模式的に示す図である。
【図３】ブロックの論理的構造を模式的に示す図である。
【図４】ディレクトリ及びＦＡＴのデータ構造を模式的に示す図である。
【図５】ブロックステートテーブルのデータ構造を模式的に示す図である。
【図６】論理物理変換テーブルのデータ構造を模式的に示す図である。
【図７】データ読み出しの処理を示すフローチャートである。
【図８】データ書き込みの処理を示すフローチャートである。
【図９】データ書き込みの処理を示すフローチャートの続きである。
【図１０】データ書き込みの処理を示すフローチャートの続きである。
【図１１】データ書き込みの処理を示すフローチャートの続きである。
【図１２】データ書き込みの処理を示すフローチャートの続きである。
【図１３】空きブロック確保の処理を示すフローチャートである。
【図１４】グループ登録の処理を示すフローチャートである。
【符号の説明】
【０１４４】
１          メモリユニット
１１        フラッシュメモリ
１２        コントローラ
１２１      ＣＰＵ
１２２      ＲＯＭ
１２３      ＲＡＭ
２          コンピュータ
【図１】
2006079434.tif 000003
【図２】
2006079434.tif 000004
【図３】
2006079434.tif 000005
【図４】
2006079434.tif 000006
【図５】
2006079434.tif 000007
【図６】
2006079434.tif 000008
【図７】
2006079434.tif 000009
【図８】
2006079434.tif 000010
【図９】
2006079434.tif 000011
【図１０】
2006079434.tif 000012
【図１１】
2006079434.tif 000013
【図１２】
2006079434.tif 000014
【図１３】
2006079434.tif 000015
【図１４】
2006079434.tif 000016