(57)【要約】【課題】特定のブロックが集中的に劣化することが防止される記憶装置等を提供することである。【解決手段】コントローラ１２は、フラッシュメモリ１１の空きブロックを特定するＢＳＩ（Block Search Index）を記憶する。そして、１個の空きブロックの物理ブロックアドレスを示すポインタを記憶しているか否かを判別し、記憶していない場合、ＢＳＩに基づいて乱数を発生し、この乱数に従ってポインタの初期値を決定し、この初期値を示すポインタを記憶する。書き込み対象のユーザデータが自己に供給されると、コントローラ１２は、ポインタが示す空きブロックにユーザデータを書き込み、このブロックに後続する物理ブロックアドレスを有する空きブロックを示すようにポインタを更新する。また、ユーザデータが書き込まれたブロックが空きブロックであることを示さないようにＢＳＩを更新する。【選択図】図１
2007133541.tif 000002
【特許請求の範囲】
【請求項１】
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含む記憶手段と、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶手段と、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新手段と、を備える、
ことを特徴とする記憶装置。
【請求項２】
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含む記憶手段と、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、を備える、
ことを特徴とする記憶装置。
【請求項３】
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶手段と、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新手段と、を備える、
ことを特徴とするメモリ管理装置。
【請求項４】
前記ポインタ記憶手段は、
前記ポインタを記憶していないと判別したとき、前記空きブロックテーブルの先頭を占める所定長の部分と、当該部分に後続する当該所定長の部分との排他的論理和を表す演算データを生成し、以下、最も新しく生成された演算データと、前記空きブロックテーブル内の未だ演算データの生成に用いていない部分の先頭の当該所定長の部分との排他的論理和を表す演算データを生成する、という処理を、前記空きブロックテーブルの全部分が演算データの生成に用いられるまで繰り返す論理演算手段と、
前記論理演算手段が最後に生成した演算データを種として、現在前記空きブロックテーブルに登録されている空きブロックの総数を最大値とする自然数の疑似乱数を表す乱数データを発生する乱数発生手段と、
現在前記空きブロックテーブルに登録されている各空きブロックの物理ブロックアドレスのうち、その順位が前記乱数データの値に等しいものを前記初期値として決定し、当該初期値を示す前記ポインタを記憶する初期値決定手段と、より構成される、
ことを特徴とする請求項３に記載のメモリ管理装置。
【請求項５】
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、を備える、
ことを特徴とするメモリ管理装置。
【請求項６】
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理方法であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶ステップと、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶ステップと、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込ステップと、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新ステップと、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新ステップと、により構成される、
ことを特徴とするメモリ管理方法。
【請求項７】
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理方法であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶ステップと、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込ステップと、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新ステップと、により構成される、
ことを特徴とするメモリ管理方法。
【請求項８】
コンピュータを、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶手段と、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新手段と、を備える、
ことを特徴とするメモリ管理装置として機能させるためのプログラム。
【請求項９】
コンピュータを、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、を備える、
ことを特徴とするメモリ管理装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記録媒体を用いたデータ処理システム及び記録媒体へのアクセスを行うためのプログラムを記憶したコンピュータ読み取り可能なプログラムに関する。
【背景技術】
【０００２】
コンピュータ等によりアクセス（データの読み書き及び消去）可能な記録媒体として、ＥＥＰＲＯＭ（Electrically Erasable/Programmable Read Only Memory）フラッシュメモリが用いられている。フラッシュメモリは、データの消去が、所定の記憶容量の単位（一般に「ブロック」と呼ばれる）で行われる。
【０００３】
このようなフラッシュメモリに記憶されたデータの書き換えを行う場合、まず空きブロックを検出して、書き換え前の古いデータが格納されているブロックに格納されている他のデータを、書き換え後の新しいデータと共にこの検出された空きブロックに転記し、古いデータが格納されている転記元のブロックをフラッシュイレースする（すなわち、記憶内容を消去する）、という操作を行う。従って、フラッシュメモリの使用に際しては、フラッシュイレースによる空きブロックの作成と、空きブロックの再使用とが頻繁に行われる。
【０００４】
ブロックのフラッシュイレースは、多数回行われることにより、ブロックの劣化、つまり、データの記憶が正常に行えない不良ブロックへの変化をもたらす。このため、同一のブロックへのフラッシュイレースは必要最小限の回数に抑えることが望ましい。
この観点からすると、新しいデータを書き込む度に、書き込み対象の空きブロックを物理ブロックアドレスが若い空きブロックから順に検出していくといった手法は適切ではない。この手法では、物理ブロックアドレスが先頭に近いブロックが集中的にフラッシュイレース及びデータ書き込みの対象となるため、そのようなブロックが集中的に劣化することになるからである。
【０００５】
このため、一部のブロックの集中的な劣化を避けるため、ＣＰＵ（Central Processing Unit）が乱数を発生して、データ書き込み対象の空きブロックをこの乱数に基づいて決定する手法が考えられてきた（例えば、特許文献１参照）。
【特許文献１】特開２００３−５０７４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、ＣＰＵによる乱数の発生は、実際には、ある一定のデータを種（シード）とした疑似乱数の発生という形で行われていた。このため、生成される乱数の列は一定のパターンを有するようになり、このパターンに合致する物理ブロックアドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となり、従って集中的に劣化する、という問題がなお生じ得る。
【０００７】
この発明は上記実状に鑑みてなされたもので、特定のブロックが集中的に劣化することが防止される記憶装置、メモリ管理装置、メモリ管理方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の第１の観点に係る記憶装置は、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含む記憶手段と、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶手段と、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新手段と、を備える、
ことを特徴とする。
【０００９】
このような記憶装置によれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックテーブルに基づいて生成される乱数に従って決められる。空きブロックテーブルは、空きブロックの新規使用又はブロックのフラッシュイレースが行われるたびに変化するデータであるので、空きブロックテーブルに基づいて生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００１０】
また、本発明の第２の観点に係る記憶装置は、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含む記憶手段と、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、を備える、
ことを特徴とする。
【００１１】
このような記憶装置によれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックにユーザデータが書き込まれるたびに変更を受けるような所定のデータに基づいて生成される乱数に従って決められる。このため、生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００１２】
また、本発明の第３の観点に係るメモリ管理装置は、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶手段と、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新手段と、を備える、
ことを特徴とする。
【００１３】
このようなメモリ管理装置によれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックテーブルに基づいて生成される乱数に従って決められる。空きブロックテーブルは、空きブロックの新規使用又はブロックのフラッシュイレースが行われるたびに変化するデータであるので、空きブロックテーブルに基づいて生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００１４】
前記ポインタ記憶手段は、例えば、
前記ポインタを記憶していないと判別したとき、前記空きブロックテーブルの先頭を占める所定長の部分と、当該部分に後続する当該所定長の部分との排他的論理和を表す演算データを生成し、以下、最も新しく生成された演算データと、前記空きブロックテーブル内の未だ演算データの生成に用いていない部分の先頭の当該所定長の部分との排他的論理和を表す演算データを生成する、という処理を、前記空きブロックテーブルの全部分が演算データの生成に用いられるまで繰り返す論理演算手段と、
前記論理演算手段が最後に生成した演算データを種として、現在前記空きブロックテーブルに登録されている空きブロックの総数を最大値とする自然数の疑似乱数を表す乱数データを発生する乱数発生手段と、
現在前記空きブロックテーブルに登録されている各空きブロックの物理ブロックアドレスのうち、その順位が前記乱数データの値に等しいものを前記初期値として決定し、当該初期値を示す前記ポインタを記憶する初期値決定手段と、より構成されていればよい。
【００１５】
また、本発明の第４の観点に係るメモリ管理装置は、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、を備える、
ことを特徴とする。
【００１６】
このようなメモリ管理装置によれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックにユーザデータが書き込まれるたびに変更を受けるような所定のデータに基づいて生成される乱数に従って決められる。このため、生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００１７】
また、本発明の第５の観点に係るメモリ管理方法は、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理方法であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶ステップと、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶ステップと、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込ステップと、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新ステップと、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新ステップと、により構成される、
ことを特徴とする。
【００１８】
このようなメモリ管理方法によれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックテーブルに基づいて生成される乱数に従って決められる。空きブロックテーブルは、空きブロックの新規使用又はブロックのフラッシュイレースが行われるたびに変化するデータであるので、空きブロックテーブルに基づいて生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００１９】
また、本発明の第６の観点に係るメモリ管理方法は、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶ステップと、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込ステップと、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新ステップと、により構成される、
ことを特徴とする。
【００２０】
このようなメモリ管理方法によれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックにユーザデータが書き込まれるたびに変更を受けるような所定のデータに基づいて生成される乱数に従って決められる。このため、生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００２１】
また、本発明の第７の観点に係るプログラムは、
コンピュータを、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである空きブロックを特定する情報を格納する空きブロックテーブルを記憶する空きブロックテーブル記憶手段と、
１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、前記空きブロックテーブルに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックが空きブロックであることを示さないように前記空きブロックテーブルを更新する空きブロックテーブル更新手段と、を備える、
ことを特徴とするメモリ管理装置として機能させるためのものであることを特徴とする。
【００２２】
このようなプログラムを実行するコンピュータによれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックテーブルに基づいて生成される乱数に従って決められる。空きブロックテーブルは、空きブロックの新規使用又はブロックのフラッシュイレースが行われるたびに変化するデータであるので、空きブロックテーブルに基づいて生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００２３】
また、本発明の第８の観点に係るプログラムは、
コンピュータを、
物理アドレスを割り当てられた、ユーザデータを記憶するための複数のメモリブロックを含むメモリにユーザデータを格納するメモリ管理装置であって、
前記メモリブロックのうちユーザデータを記憶可能な状態にあるものである１個の空きブロックの物理アドレスを示すポインタを記憶しているか否かを判別し、記憶していないと判別したとき、ユーザデータが空きブロックに新たに記憶されるたびに変更を受けるような所定のデータに基づいて乱数を発生し、当該乱数に従って、書き込み対象である空きブロックの初期値を決定し、当該初期値を示す前記ポインタを記憶するポインタ記憶手段と、
書き込み対象のユーザデータが自己に供給されたとき、前記ポインタが示す空きブロックに当該書き込み対象のデータを書き込む書込手段と、
前記ポインタが示す空きブロックが前記書き込み対象のデータの書込先となったとき、当該メモリブロックに後続する物理アドレスを有する空きブロックを示すように前記ポインタを更新するポインタ更新手段と、を備える、
ことを特徴とするメモリ管理装置として機能させるためのものであることを特徴とする。
【００２４】
このようなプログラムを実行するコンピュータによれば、データを書き込む対象の空きブロックの特定が、ポインタが示す物理アドレスを基点として順次行われる。一方、ポインタの初期値は、空きブロックにユーザデータが書き込まれるたびに変更を受けるような所定のデータに基づいて生成される乱数に従って決められる。このため、生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理アドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【発明の効果】
【００２５】
この発明によれば、特定のブロックが集中的に劣化することが防止される記憶装置、メモリ管理装置、メモリ管理方法及びプログラムが実現される。
【発明を実施するための最良の形態】
【００２６】
以下、この発明の実施の形態を、フラッシュメモリを備えた記憶システムを例とし、図面を参照して説明する。
【００２７】
図１は、この発明の実施の形態にかかる記憶システムの物理的構成を示すブロック図である。図示するように、この記憶システムは、メモリユニット１と、コンピュータ２とから構成されている。
【００２８】
メモリユニット１は、コンピュータ２に接続される。メモリユニット１とコンピュータ２との接続は固定的に行われていてもよいし、あるいは、例えばコンピュータ２がPC Card Standardに準拠したバスを中継するためのスロットを備えるものとして、メモリユニット１がこのスロットを介し、コンピュータ２に着脱可能に装着されるようになっていてもよい。
【００２９】
メモリユニット１は、フラッシュメモリ１１及びコントローラ１２からなる。
【００３０】
フラッシュメモリ１１は、コントローラ１２が行うアクセスに応答し、コントローラ１２から供給されたデータの記憶と、記憶しているデータのコントローラ１２への供給と、記憶しているデータの消去とを行う。
【００３１】
フラッシュメモリ１１が有する記憶領域は、例えば図２に示すように２５６個のブロックから構成され、各ブロックは先頭から連続的に０から２５５までの物理ブロックアドレスを与えられている。各々のブロックは３２個のページから構成され、各々のブロック内の各ページには、先頭から連続的に０から３１までのページアドレスが付与されている。
【００３２】
各々のページは、各１バイトで５２８個、計５２８バイトのメモリセルから構成されており、各々のページ内のメモリセルには、先頭から連続的に０から５２７までの番地が与えられている。フラッシュメモリ１１の記憶領域全体は、８１９２個のページから構成される。
【００３３】
また、各ページは、図示するように、先頭から５１２バイトの領域を占めるデータ領域と、末尾１６バイトを占める冗長部とから構成される。
データ領域には、ユーザデータ（コンピュータ２から供給され書き込まれるデータや、コンピュータ２に供給される対象となるデータ）が格納され、冗長部には、ユーザデータの内容が破壊されていないことを確認するための誤り訂正コード等が格納される。また、ブロックが後発的に、データの正常な読み書きのできない状態になったとき、このようなブロック（後発不良ブロック）に属するページの冗長部には、コントローラ１２の後述の処理に従い、当該ブロックが後発不良ブロックであることを示すデータである不良ブロックフラグが格納される。
【００３４】
また、各々のブロックに属する各ページの冗長部には、そのブロックに割り当てられている論理ブロックアドレスの値が格納される。
論理ブロックアドレスは、フラッシュメモリ１１が後述する動作により読み書きされるときに、コントローラ１２により、データ読み書きの単位として認識される単位である。論理ブロックアドレスが割り当てられているブロック（論理ブロック）の総量は、フラッシュメモリ１１が物理的に備えるブロックの総量より小さい所定量、例えば２５０個である。
【００３５】
また、データ領域は、ＢＰＴ（Block Pointer Table）の格納にも用いられる。ＢＰＴは、後述するコントローラ１２が行う処理に従って格納されるデータであり、例えば図３に示すように、フラッシュメモリ１１の各々のブロックについて、当該ブロックの論理ブロックアドレス及び物理ブロックアドレスを互いに対応付けて格納するテーブルからなっている。なお、ＢＰＴが格納されているページの冗長部には、ＢＰＴの内容が破壊されていないことを確認するための誤り訂正コード等が格納される。
【００３６】
コントローラ１２は、ＢＰＴの内容が、実際のブロックの論理ブロックアドレス及び物理ブロックアドレスの対応関係との不一致を生じるたびに、後述の処理を行うことにより、正しい対応関係を示す新たなＢＰＴを作成してフラッシュメモリ１１のデータ領域に格納する。
【００３７】
なお、コントローラ１２は、ＢＰＴが格納されるページを含むブロックには、ユーザデータを格納しない。また、ＢＰＴが格納されるページからなるブロックの論理ブロックアドレスの値と、また、ユーザデータが格納されるページからなるブロックの論理ブロックアドレスの値がとり得る範囲とは、互いに重複しないものとする。
【００３８】
ＢＰＴ１個はフラッシュメモリ１１のデータ領域１ページ分以内の記憶容量を有しており、１個のＢＰＴは、１個のページのデータ領域内に格納される。当該ページの冗長部には、フラッシュメモリ１１に割り当てられた論理ブロックの総数より大きい値の論理ブロックアドレス（例えば“１００ｈ”）が格納される。なお、本明細書及び図面において末尾に文字“ｈ”が付された数字は、１６進数を表すものとする。
【００３９】
コントローラ１２は、ＢＰＴを、例えばまず、空きブロック（つまり、データ領域にデータが格納されたページを含まないブロック）内の先頭のページに格納し、以下、新たなＢＰＴを作成するたびに、順次、当該ブロック内の後続のページへと格納する。つまり、当該ブロック内でＢＰＴを格納していないページのうちの先頭のページへと格納する。
【００４０】
ＢＰＴは、各々の論理ブロックアドレスに対応付けられた、番地の連続する複数の記憶領域を備えている。１個の論理ブロックアドレスに対応付けられた記憶領域には、当該論理ブロックアドレスに対応付けられた物理ブロックアドレスが格納される。
【００４１】
具体的には、例えば図３に示すように、番地が（２・ｎ）及び｛（２・ｎ）＋１｝（ｎは０以上２５５以下の整数）である合計２バイトの記憶領域が論理ブロックアドレスｎに対応付けられているとして、番地１の記憶領域に値”００５Ａｈ”が格納されてとする。この場合は、物理ブロックアドレスが００５Ａｈであるブロックには、論理ブロックアドレスとして０００１ｈが対応付けられている。
【００４２】
ただし、この記憶領域に格納されている内容が所定の値を表す場合（例えば、図示するように、値“ＦＦＦＦｈ”を表す場合）は、その値を格納している記憶領域に対応付けられている論理ブロックアドレスには物理ブロックアドレスが対応付けられていないことを表す。
【００４３】
フラッシュメモリ１１は、メモリユニット１のコントローラ１２より、特定のブロックのデータを消去するよう指示されると、当該ブロックに含まれるすべてのメモリセルの記憶内容をリセットする（例えば、フラッシュメモリ１１がＮＡＮＤ型のフラッシュメモリからなる場合は、各メモリセルの記憶値を「１」とする）。
【００４４】
また、フラッシュメモリ１１は内部レジスタ及びシーケンサを備えている。フラッシュメモリ１１のシーケンサは、後述するコントローラ１２のＣＰＵ１２１からデータの書き込みを指示されると、この指示に従い、フラッシュメモリ１１のページへのデータの書き込みを行いながら書き込んだデータのベリファイを行い、このベリファイの結果（書き込みが正常に行われたか否か）を表す情報を、この内部レジスタにセットする。
【００４５】
コントローラ１２は、図１に示すように、ＣＰＵ（Central Processing Unit）１２１と、ＲＯＭ（Read Only Memory）１２２と、ＲＡＭ（Random Access Memory）１２３とを備えている。
ＣＰＵ１２１は、ＲＯＭ１２２、ＲＡＭ１２３及びフラッシュメモリ１１に接続されており、また、コンピュータ２に接続されている。ＣＰＵ１２１とコンピュータ２との接続は、固定的な接続でもよいし、あるいは、例えばコンピュータ２が備える上述のスロットを介して着脱可能に行われるようになっていてもよい。
【００４６】
ＣＰＵ１２１は、コントローラ１２の製造者等によって予めＲＯＭ１２２に格納されているプログラムの処理に従って、フラッシュメモリ１１へのデータの書き込み、フラッシュメモリ１１からのデータの読み出し、フラッシュメモリ１１が格納するデータの消去（フラッシュイレース）等、後述する処理を行う。
そして、ＣＰＵ１２１は、アクセス装置を構成するコンピュータ２から供給される命令を取得すると、その命令を実行する。ＣＰＵ１２１が実行する命令には、フラッシュメモリ１１にアクセスする命令が含まれる。
【００４７】
ＲＡＭ１２３は、例えばＳＲＡＭ（Static RAM）等より構成されており、ＣＰＵ１２１の作業領域となる記憶領域と、退避用メモリ領域とを提供する。退避用メモリ領域は、後述するデータ書き込みの処理において、書き込みを行う対象のページを含むブロックに格納されているデータを一時的に格納する（退避する）ための記憶領域である。退避する対象のデータとしては、例えばユーザデータ及びＢＰＴがある。
【００４８】
また、ＲＡＭ１２３は、ＣＰＵ１２１が作成するＢＳＩ（Block Search Index）を格納する。ＢＳＩは、フラッシュメモリ１１の各ブロックのうちどれが空きブロックであるかを特定する情報を格納する。ＢＳＩは、コントローラ１２の処理に従って作成及び更新され、ＲＡＭ１２３に格納される。
【００４９】
ＢＳＩは、フラッシュメモリ１１の各ブロックのいずれが空きブロック（すなわち、リセットされた状態にあるブロック）であるかを表す情報を格納する。
ＢＳＩは、この記憶システムが起動する度にコントローラ１２の後述する処理に従って作成され、ＲＡＭ１２３に格納される。
【００５０】
フラッシュメモリ１１のブロックの総数が２５６個であるときのＢＳＩの構造の一例を図４に示す。図示するように、ＢＳＩは、３２バイトのデータからなり、先頭のビットから順に、ブロック０からブロック２５５に１対１に対応し、対応するブロックが空きブロックであるとき“１”、空きブロックでないとき“０”を格納する。
【００５１】
また、ＲＡＭ１２３は、ＣＰＵ１２１が実行する処理に従って、初期空きブロック検索ポインタを格納する。初期空きブロック検索ポインタは、ＣＰＵ１２１が次に書き込みの対象とする空きブロックの物理ブロックアドレスを値とするポインタであり、ＣＰＵ１２１が実行する後述の処理に従って更新される。
【００５２】
コンピュータ２はパーソナルコンピュータ等からなり、ＯＳ及びドライバを表すプログラムデータを記憶し、電源投入後、ＯＳを実行する。そしてＯＳの処理に従ってドライバを起動する。
【００５３】
ドライバの処理を行うコンピュータ２は、コントローラ１２に上述の命令を供給したり、フラッシュメモリ１１に書き込む対象のデータを供給して、ＣＰＵ１２１に、フラッシュメモリ１１へのアクセスを行わせる。そして、自らが供給した命令に従ってＣＰＵ１２１がフラッシュメモリ１１から読み出して自らに供給したデータを、ＣＰＵ１２１より取得する。
【００５４】
（動作）
次に、この記憶システムの動作を、図５−図１４を参照して説明する。
図５は、初期処理を示すフローチャートである。
図６は、データ書き込みの処理を示すフローチャートである。
図７は、旧ユーザデータ読み込みの処理を示すフローチャートである。
図８及び図１０は、ＢＰＴ更新の処理を示すフローチャートである。
図９は、ユーザデータを書き込む空きブロックを決定する処理（ステップＳ２０１の処理）を示すフローチャートである。
図１１及び図１２は、新ユーザデータ書き込みの処理を示すフローチャートである。
図１３は、旧ユーザデータ消去の処理を示すフローチャートである。
図１４は、旧ＢＰＴ消去の処理を示すフローチャートである。
【００５５】
（初期処理）
この記憶システムが起動すると、メモリユニット１のコントローラ１２のＣＰＵ１２１は、図５に示す初期処理を実行する。
初期処理を開始すると、ＣＰＵ１２１は、ＲＡＭ１２３の記憶領域のうち、ＢＰＴ及びＢＳＩを格納する部分の初期化を行う（図５、ステップＳ００１）。具体的には、例えばＲＡＭ１２３の記憶領域のうちＢＰＴ又はＢＳＩを格納する部分のビットの論理値を、すべて”０”とすればよい。
【００５６】
次に、ＣＰＵ１２１は、フラッシュメモリ１１の各ブロックの先頭ページの冗長部内の論理ブロックアドレスを検索する等して、ＢＰＴが格納されているブロックを特定する（ステップＳ００２）。
【００５７】
次に、ＣＰＵ１２１は、ステップＳ００２で特定したブロック内のページのデータ領域からＢＰＴを読み出し、また、特定したページの冗長部から誤り訂正符号を読み出して、ＲＡＭ１２３の記憶領域に格納する（ステップＳ００３）。
【００５８】
次に、ＣＰＵ１２１は、ＲＡＭ１２３に記憶されているＢＰＴに含まれている訂正可能な誤りを、ステップＳ００３で読み出した誤り訂正符号を用いて公知の手法により訂正した上、処理をステップＳ００４に移す。
【００５９】
ステップＳ００４でＣＰＵ１２１は、ＢＳＩを作成する。具体的には、ＣＰＵ１２１は、フラッシュメモリ１１の、各ブロックのページの冗長部に格納されているデータを順次に（例えば、物理ブロックアドレスが先頭のブロックから末尾のブロックまで１ブロックずつ順次に）読み出す。一方、１個のブロックからデータを読み出す毎に、読み出したデータに基づき、データを読み出した当該ブロックが空きブロックであるか否かを判別する（具体的には、例えば、読み出したデータに所定の形式の空きブロックコードが格納されているか否かを判別すればよい）。そして、この判別の結果を、ＲＡＭ１２３が記憶するＢＳＩに追加する（例えば、当該ブロックが空きブロックであれば、ＢＳＩ内で当該ブロックに対応するビットの値を“１”とし、空きブロックでなければ“０”のままとする）。
【００６０】
そして、ＢＳＩの作成が完了すると、この記憶システムは初期処理を終了する。
以上説明した初期処理により、ＢＰＴがＲＡＭ１２３の記憶領域に転記され、正しい内容となるように更新され、また、ＢＳＩが作成される。
【００６１】
（データ読み出しの処理）
初期処理が終了すると、ＣＰＵ１２１は、コンピュータ２より、フラッシュメモリ１１へのアクセスの指示を受け付ける。
そして、コンピュータ２が、ユーザデータの読み出しを指示する命令と、読み出す対象のページを示すための論理ブロックアドレス及びページアドレスとをコントローラ１２に供給すると、コントローラ１２のＣＰＵ１２１は、供給された論理ブロックアドレスをキーとしてＢＰＴを検索し、この論理ブロックアドレスに対応付けられた物理ブロックアドレスを索出する。ＣＰＵ１２１は、索出した物理ブロックアドレスと、コンピュータ２より供給されたページアドレスとより特定されるページよりデータを読み出して、コンピュータ２に供給する。
この結果、フラッシュメモリ１１よりデータが読み出され、コンピュータ２へと供給される。
【００６２】
なお、フラッシュメモリ１１の記憶領域がＭＳ−ＤＯＳ（登録商標）のファイルシステムに従ったものである場合、フラッシュメモリ１１は、例えばディレクトリ及びＦＡＴ（File Allocation Table）を予め記憶していればよい。そしてコンピュータ２は、ユーザデータの読み出しに先立って、まずディレクトリ及びＦＡＴをＣＰＵ１２１に読み出させてこれらを取得し、取得したディレクトリ及びＦＡＴに基づいて、読み出す対象のページのページアドレス及び当該ページが属するブロックの論理ブロックアドレスを特定するようにすればよい。この場合、例えば、ディレクトリ及びＦＡＴが記憶されているブロックには、所定の論理ブロックアドレスが割り当てられていればよい。
【００６３】
（データ書き込みの処理）
また、フラッシュメモリ１１へのデータの書き込みを行う場合、まず、コンピュータ２はコントローラ１２に、フラッシュメモリ１１へのデータの書き込みを指示する命令と、書き込む対象のファイルに含まれるデータを書き込むページの論理ブロックアドレス及びページアドレスとを供給する。
【００６４】
なお、フラッシュメモリ１１の記憶領域がＭＳ−ＤＯＳのファイルシステムに従ったものであって、ディレクトリ及びＦＡＴを予め記憶している場合、コンピュータ２は、例えば、メモリユニット１よりまずディレクトリ及びＦＡＴを取得し、これらに基づき、データが格納されていないページのページアドレス及び論理ブロックアドレスを特定して、当該論理ブロックアドレスが登録された状態へとこれらのディレクトリあるいはＦＡＴを更新した上、フラッシュメモリ１１へと書き戻すようにしてもよい。
【００６５】
コンピュータ２より、データの書き込みを指示する命令と、論理ブロックアドレス及びページアドレスとを供給されると、メモリユニット１はまず、旧ユーザデータ読み込みの処理を行う（図６、ステップＳ１００）。
【００６６】
図７に詳細を示す旧ユーザデータ読み込みの処理において、まずＣＰＵ１２１は、コンピュータ２より供給された論理ブロックアドレスをキーとして、ＲＡＭ１２３が記憶しているＢＰＴを検索する。そして、ＣＰＵ１２１は、この論理ブロックアドレスに対応付けられた物理ブロックアドレスが索出されたか否かを判別することにより、書き換えられるべき古いデータがあるか否かを判別する（図７、ステップＳ１０１）。
【００６７】
そして、古いデータがない（つまり、該当する物理ブロックアドレスが索出されなかった）と判別すると、ＣＰＵ１２１は、ＲＡＭ１２３の退避用メモリ領域に格納されているデータを消去する（具体的には、例えば、退避用メモリ領域に格納されているデータの各ビットをすべて値“１”に更新する）ことにより、退避用メモリ領域の初期化を行い（ステップＳ１０２）、処理を、ＢＰＴ更新の処理（図６、ステップＳ２００）へと移す。
【００６８】
一方、古いデータがあるとステップＳ１０１で判別すると、ＣＰＵ１２１は、索出された物理ブロックアドレスが示すブロックに格納されている古いデータを読み出して退避用メモリ領域に格納し（ステップＳ１０３）、ＢＰＴ更新の処理（ステップＳ２００）に移る。なお、ＣＰＵ１２１は、ＢＰＴ更新の処理以降の処理では、ステップＳ１０２の処理で初期化された退避用メモリ領域も、ステップＳ１０３でデータを格納されたものとみなして扱う。
【００６９】
図８及び図１０に詳細を示すＢＰＴ更新の処理を開始すると、まず、ＣＰＵ１２１は、新たにユーザデータを書き込むための１個の空きブロックの物理ブロックアドレスを決定する（図８、ステップＳ２０１）。ステップＳ２０１の処理は、具体的には、図９に示すステップＳ２０１１〜Ｓ２０１４の処理からなっている。
【００７０】
すなわち、ステップＳ２０１でＣＰＵ１２１は、具体的にはまず、ＲＡＭ１２３が、初期空きブロック検索ポインタを記憶しているか否かを判別する（図９、ステップＳ２０１１）。そして、記憶していると判別すると処理をステップＳ２０１３へと進め、記憶していないと判別すると、処理をステップＳ２０１２へと進める。
【００７１】
ステップＳ２０１２でＣＰＵ１２１は、ＲＡＭ１２３が現に記憶しているＢＳＩに基づいて乱数を発生し、この乱数が示す空きブロックの物理ブロックアドレスの値を示すような初期空きブロック検索ポインタを、ＲＡＭ１２３に格納する。ステップＳ２０１２の処理を終えると、ＣＰＵ１２１は、処理をステップＳ２０１３に移す。
【００７２】
ステップＳ２０１２でＣＰＵ１２１は、具体的には、まずＢＳＩの先頭を占める所定長（例えば、８バイト）の部分と、この部分に後続する同一の長さの部分との排他的論理和を表す演算データを生成する。そして、以下、最も新しく生成された演算データと、ＢＳＩ内のまだ演算データの生成に用いていない部分の先頭の所定長の部分との排他的論理和を表す演算データを生成する、という処理を、ＢＳＩの全部分が演算データの生成に用いられるまで繰り返す。次いで、最後に生成された演算データを種（シード）として、公知の手法により、現在ＢＳＩに登録されている空きブロックの総数を最大値とする自然数の疑似乱数を表す乱数データを発生する。そして、現在ＢＳＩに登録されている各空きブロックの物理ブロックアドレスのうち、その順位がこの乱数データの値に等しいものを初期値として決定し、決定した物理ブロックアドレスの値を指し示す初期空きブロック検索ポインタを、ＲＡＭ１２３に格納する。
【００７３】
ステップＳ２０１３でＣＰＵ１２１は、初期空きブロック検索ポインタが現在指し示している空きブロックを、ユーザデータを書き込むための空きブロックとして決定する。そして、この空きブロックの次に物理ブロックアドレスが若い空きブロックを、ＢＳＩを検索するなどして特定し、初期空きブロック検索ポインタの値を、この特定された空きブロックを指すように更新して（ステップＳ２０１４）、処理をステップＳ２０２へ移す。ただしステップＳ２０１４でＣＰＵ１２１は、ステップＳ２０１３で決定した空きブロックの次に物理ブロックアドレスが若い空きブロックが存在しない場合には、すべての空きブロックのうち物理ブロックアドレスが最も若い空きブロックを指すように、初期空きブロック検索ポインタを更新するものとする。
【００７４】
ステップＳ２０２で、ＣＰＵ１２１は、ステップＳ２０１で空きブロックの決定が正常に行われたか否かを判別し（ステップＳ２０２）、行われなかったと判別すると、ＣＰＵ１２１は、空きブロックがなく書き込みが行えないと判断して、データ書き込みの処理を異常終了する。
【００７５】
一方、空きブロックが正常に決定されたと判別すると、ＣＰＵ１２１は、決定された空きブロックが以後は空きブロックではない旨を示すようにＢＳＩの内容を更新し（ステップＳ２０３）、また、決定された空きブロックの物理ブロックアドレスが、古いデータが格納されているブロックの現在の論理ブロックアドレスに対応付けられるように、ＲＡＭ１２３が記憶するＢＰＴを更新する（ステップＳ２０４）。
【００７６】
次にＣＰＵ１２１は、更新前のＢＰＴを記憶しているブロック内に、ＢＰＴがまだ書き込まれていない空きページがあるか否かを判別する（ステップＳ２０５）。そして、あると判別すると、更新前のＢＰＴを記憶しているページに後続する空きページのデータ領域に、ＲＡＭ１２３に記憶されている更新後のＢＰＴを書き込み、また、更新後のＢＰＴの誤り訂正符号を生成して、この誤り訂正符号を当該ページの冗長部に書き込んで（ステップＳ２０６）、処理をステップＳ２１１に移す。
【００７７】
一方、空きページがないとステップＳ２０５で判別すると、ＣＰＵ１２１は、上述のステップＳ２０１の処理と実質的に同一の処理を行うことにより、新たにＢＰＴを書き込むための１個の空きブロックの物理ブロックアドレスを決定する（ステップＳ２０７）。そしてＣＰＵ１２１は、空きブロックが正常に決定されたか否かを判別し（ステップＳ２０８）、決定されたと判別すると、図１０に示すステップＳ２０９へと処理を移す。一方、決定されなかったと判別すると、空きブロックがなくＢＰＴの書き込みが行えないと判断して、データ書き込みの処理を異常終了する。
【００７８】
ステップＳ２０９でＣＰＵ１２１は、更新前のＢＰＴの物理ページアドレスを特定する。次に、ＣＰＵ１２１は、ステップＳ２０７で決定された空きブロックの先頭のページのデータ領域に、ＲＡＭ１２３に記憶されている更新後のＢＰＴを書き込む（ステップＳ２１０）。また、ステップＳ２１０でＣＰＵ１２１は、更新後のＢＰＴの誤り訂正符号を生成して、この誤り訂正符号を、更新後のＢＰＴを書き込むページの冗長部に書き込む。
【００７９】
次に、ステップＳ２１１でＣＰＵ１２１は、ステップＳ２１０でＢＰＴを書き込んだ後、フラッシュメモリ１１の内部レジスタにセットされた値を参照することにより、ステップＳ２１０での書き込みが正常に行われたか否かを判別する。そして、正常に行われていると判別すると、新ユーザデータ書き込みの処理に移る（図６、ステップＳ３００）。
【００８０】
一方、正常に行われていないとステップＳ２１１で判別すると、ＣＰＵ１２１は、ステップＳ２１０又は後述するステップＳ２１４での書き込みが正常に行われなかったブロックが後発不良ブロックになったものとして、当該ブロック内のページの冗長部に不良ブロックフラグを書き込む（ステップＳ２１２）。
そして、更新後のＢＰＴの書き込みを再度試みるため、ステップＳ２０７及びＳ２０８の処理と実質的に同一の処理を行い（ステップＳ２１３）、空きブロックが索出されなければデータ書き込みの処理を異常終了し、索出されれば、ステップＳ２１０の処理と実質的に同一の処理を行うことにより、更新後のＢＰＴ及び誤り訂正符号の書き込みを行う（ステップＳ２１４）。
【００８１】
ステップＳ２１４の処理のあと、ＣＰＵ１２１は、ステップＳ２１４でＢＰＴを書き込んだ後、ステップＳ２１１の処理と同様、フラッシュメモリ１１の内部レジスタにセットされた値を参照することにより、ステップＳ２１４での書き込みが正常に行われたか否かを判別する（ステップＳ２１５）。そして、正常に行われていると判別すると、ＢＰＴ更新の処理を終えて新ユーザデータ書き込みの処理に移り（図６、ステップＳ３００）、正常に行われていないと判別すると、処理をステップＳ２１２に戻す。
【００８２】
図１１に詳細を示す新ユーザデータ書き込みの処理においては、まずＣＰＵ１２１が、ユーザデータを書き込む対象のページを示す変数を格納するレジスタ（書き込み用レジスタ）の使用を宣言し、書き込み用レジスタを初期化する（すなわち、書き込み用レジスタに、ステップＳ２０１で索出されたブロックの先頭ページのページアドレスをセットする）（図１１、ステップＳ３０１）。
【００８３】
次に、ＣＰＵ１２１は、書き込み用レジスタの現在の値が、ステップＳ２０１でコンピュータ２から供給されたページアドレスと一致するか否かを判別する（ステップＳ３０２）。そして、一致しないと判別すると、処理をステップＳ３０４に進める。
【００８４】
一方、２個のページアドレスが一致するとステップＳ３０２で判別すると、ＣＰＵ１２１はコンピュータ２に、書き込む対象のデータ（つまり、新しいユーザデータ）のうち、書き込み用レジスタが示すページアドレスに格納する部分を供給するよう指示し、コンピュータ２は、この指示に従って、該当するデータをＣＰＵ１２１に供給する。
するとＣＰＵ１２１は、ステップＳ１０３で退避用メモリ領域に転記したデータのうち、転記元のブロック（すなわち、ステップＳ１０３でデータを読み出したブロック）中、書き込み用レジスタに格納されているページアドレスと同一のページアドレスが示すページに格納されていた部分を、コンピュータ２より供給されたデータにより上書きし（ステップＳ３０３）、処理をステップＳ３０４に移す。
【００８５】
ステップＳ３０４でＣＰＵ１２１は、ステップＳ１０３で退避用メモリ領域に転記したデータのうち、転記元のブロック中、書き込み用レジスタに格納されているページアドレスと同一のページアドレスが示すページに格納されていた部分を、退避用メモリ領域から読み出す。そして、読み出したデータを、ステップＳ２０１で索出された物理ブロックアドレス及び書き込み用レジスタに格納されているページアドレスとより特定される転記先のページに書き込み、処理をステップＳ３０５に移す。ただしステップＳ３０４では、ページに書き込むデータのうち、冗長部内の論理ブロックアドレスに相当するデータは、転記先のブロックの論理ブロックアドレスに替えて書き込むものとする。
【００８６】
ステップＳ３０５でＣＰＵ１２１は、ステップＳ３０４でのデータの書き込みが正常に書き込まれたか否かを判別する。この判別は、データを書き込んだ後フラッシュメモリ１１の内部レジスタにセットされた値を参照することにより行えばよい。そして、データの書き込みが正常に行われたと判別すると処理をステップＳ３０７に進め、正常に行われなかったと判別すると、ステップＳ３０６へと処理を移す。
【００８７】
ステップＳ３０６でＣＰＵ１２１は、書き込みが正常に行われなかったブロックが後発不良ブロックになったものと判定して、当該ブロック内のページの冗長部に不良ブロックフラグを書き込み、ＢＰＴ更新の処理へと処理を戻す。
【００８８】
ステップＳ３０７で、ＣＰＵ１２１は、書き込み用レジスタが示すページアドレスが、書き込み対象のブロックの最終ページを示しているか否かを判別する。
そして、示していないと判別すると、書き込み用レジスタの値を１ページ分インクリメントする（ステップＳ３０８）。すなわち、書き込み用レジスタの値を、現に示すページアドレスが示すページの次のページを示すように更新する。ステップＳ３０８の処理を終えると、ＣＰＵ１２１は、処理をステップＳ３０２に戻す。
【００８９】
一方、ステップＳ３０７で、書き込み用レジスタに格納されているページアドレスが、書き込み対象のブロックの最終ページを示していると判別すると、ＣＰＵ１２１は、ステップＳ３０９に処理を進める。
【００９０】
ステップＳ３０９でＣＰＵ１２１は、新たなユーザデータの書き込みに先立って古いユーザデータがＲＡＭ１２３へと退避されたブロックがあったか否か（つまり、ステップＳ１０１で物理ブロックアドレスが索出されていたか否か）を判別し、データが退避されたブロックがなかった場合は、旧ＢＰＴ消去の処理（図６、ステップＳ５００）に移る。
【００９１】
一方、データが退避されたブロックがあった場合、この記憶システムは、図１３に詳細を示す旧ユーザデータ消去の処理を行う（図６、ステップＳ４００）。
すなわち、まずＣＰＵ１２１は、転記元のブロック（すなわち、ステップＳ１０１で索出された物理ブロックアドレスが示すブロック）に格納されているデータを消去（フラッシュイレース）し、データを消去したブロックに属するカラムの冗長部に、空きブロックコードを書き込む（図１３、ステップＳ４０１）。
【００９２】
次いで、ＣＰＵ１２１はＢＳＩにもアクセスし、ステップＳ４０１でデータを消去されたブロックが空きブロックであることを表すようにＢＳＩの内容を書き換えて（ステップＳ４０２）、旧ユーザデータ消去の処理を終え、旧ＢＰＴ消去の処理に移る（図６、ステップＳ５００）。
【００９３】
図１４に詳細を示す旧ＢＰＴ消去の処理に移ると、ＣＰＵ１２１はまず、ステップＳ２０５で、更新前のＢＰＴを記憶しているブロック内に空きページがあると判別したかを判別する（図１４、ステップＳ５０１）。そして、あると判別していた場合は、データ書き込みの処理全体を終了する。
一方、ないと判別していた場合、ＣＰＵ１２１は、更新前のＢＰＴが格納されているブロックをフラッシュイレースし、データを消去したブロックに属するカラムの冗長部に、空きブロックコードを書き込む（ステップＳ５０２）。そしてＢＳＩにもアクセスし、ステップＳ５０２でデータを消去されたブロックが空きブロックであることを表すようにＢＳＩの内容を書き換え（ステップＳ５０３）、データ書き込みの処理全体を終える。
【００９４】
以上説明したこの記憶システムでは、ユーザデータやＢＰＴを書き込む対象の空きブロックの特定が、初期空きブロック検索ポインタが示す物理ブロックアドレスを基点として順次行われる。一方、初期空きブロック検索ポインタの初期値は、ＢＳＩに基づいて生成される乱数に従って決められる。ＢＳＩは、空きブロックの新規使用又はブロックのフラッシュイレースが行われるたびに変化するデータであるので、ＢＳＩに基づいて生成される乱数の列が一定のパターンを有するといった弊害は起こらない。従って、乱数の一定のパターンに合致する物理ブロックアドレスを有するブロックが集中的にフラッシュイレース及びデータ書き込みの対象となって集中的に劣化する、という事態が防止される。
【００９５】
なお、この記憶システムの構成は、上述のものに限られない。
例えば、ステップＳ２０１２でＣＰＵ１２１がＢＳＩに基づいて乱数を発生する手法は任意であり、従って、例えばＢＳＩ全体を１個の種（シード）として乱数を発生してもよいし、ＢＳＩ全体を所定のハッシュ関数に代入して得られる値を種（シード）として用いてもよく、その他、ＢＳＩに任意の演算を施して得られた値を種（シード）として用いてよい。
【００９６】
また、ステップＳ２０１２でＣＰＵ１２１が乱数を発生するために用いるデータはＢＳＩである必要はなく、データの書き込みの度に変化し、又は変化する蓋然性の高い他のデータであってもよい。従ってＣＰＵ１２１は、乱数を発生するためにＢＰＴをＢＳＩの代わりに用いてもよく、また、フラッシュメモリ１１がＦＡＴを記憶している場合は、乱数を発生するためにこのＦＡＴをＢＳＩの代わりに用いてもよい。
【００９７】
また、ＣＰＵ１２１は、ステップ２０１１及び２０１２の処理を行う代わりに、初期処理のステップＳ００４の処理を経てＢＳＩが作成された後直ちに、このＢＳＩに基づいて乱数を発生し、この乱数が示す空きブロックの物理ブロックアドレスの値を示すような初期空きブロック検索ポインタをＲＡＭ１２３に格納するようにしてもよい。
【００９８】
また、フラッシュメモリ１１の記憶領域のブロックの数、１ブロック当たりのページの数、各ページの記憶容量、データ領域及び冗長部の記憶容量は、いずれも任意である。また、フラッシュメモリ１１は、ＥＥＰＲＯＭから構成されるものである必要はなく、コンピュータにより読み書き可能な任意の記憶装置であってよい。
【００９９】
以上、この発明の実施の形態を説明したが、この発明の記憶装置及びメモリ管理装置は、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。例えば、フラッシュメモリ１１に接続されるパーソナルコンピュータに上述のコントローラ１２及びコンピュータ２の動作を実行するためのプログラムを格納した媒体（フレキシブルディスク、ＣＤ−ＲＯＭ等）から該プログラムをインストールすることにより、上述の処理を実行する記憶システムを構成することができる。
【０１００】
また、例えば、通信ネットワークの掲示板（ＢＢＳ）に該プログラムをアップロードし、これを通信ネットワークを介して配信してもよい。そして、該プログラムを起動し、ＯＳの制御下に、他のアプリケーションプログラムと同様に実行することにより、上述の処理を実行することができる。
【０１０１】
なお、ＯＳが処理の一部を分担する場合、あるいは、ＯＳが本願発明の１つの構成要素の一部を構成するような場合には、記録媒体には、その部分を除いたプログラムを格納してもよい。この場合も、この発明では、その記録媒体には、コンピュータが実行する各機能又はステップを実行するためのプログラムが格納されているものとする。
【図面の簡単な説明】
【０１０２】
【図１】本発明の実施の形態にかかる記憶システムの構成を示すブロック図である。
【図２】フラッシュメモリの記憶領域の論理的構造を模式的に示す図である。
【図３】ＢＰＴのデータ構造を模式的に示す図である。
【図４】ＢＳＩのデータ構造を模式的に示す図である。
【図５】初期処理の手順を示すフローチャートである。
【図６】データ書き込みの処理を示すフローチャートである。
【図７】旧ユーザデータ読み込みの処理を示すフローチャートである。
【図８】ＢＰＴ更新の処理を示すフローチャートである。
【図９】ユーザデータを書き込む空きブロックを決定する処理を示すフローチャートである。
【図１０】ＢＰＴ更新の処理を示すフローチャートの続きである。
【図１１】新ユーザデータ書き込みの処理を示すフローチャートである。
【図１２】新ユーザデータ書き込みの処理を示すフローチャートの続きである。
【図１３】旧ユーザデータ消去の処理を示すフローチャートである。
【図１４】旧ＢＰＴ消去の処理を示すフローチャートである。
【符号の説明】
【０１０３】
１          メモリユニット
１１        フラッシュメモリ
１２        コントローラ
１２１      ＣＰＵ
１２２      ＲＯＭ
１２３      ＲＡＭ
２          コンピュータ
【図１】
2007133541.tif 000003
【図２】
2007133541.tif 000004
【図３】
2007133541.tif 000005
【図４】
2007133541.tif 000006
【図５】
2007133541.tif 000007
【図６】
2007133541.tif 000008
【図７】
2007133541.tif 000009
【図８】
2007133541.tif 000010
【図９】
2007133541.tif 000011
【図１０】
2007133541.tif 000012
【図１１】
2007133541.tif 000013
【図１２】
2007133541.tif 000014
【図１３】
2007133541.tif 000015
【図１４】
2007133541.tif 000016