(57)【特許請求の範囲】
【請求項１】
書込まれていない物理メモリ場所のみにデータを書込むことが可能であり、連続メモリ場所のゾーンを同時に消去可能なメモリのためのメモリ管理方法であって、
前記メモリを各々が少なくとも１つのゾーンを含む複数のユニットに編成するステップと、
各ユニットを複数のブロックに編成するステップとを含み、前記ブロックの各々は複数の連続物理メモリ場所からなり、
ユニットの各ブロックの状態を活性書込、非書込または削除として示す、各ユニットのための割当表を確立するステップと、
仮想アドレスを物理アドレスにマッピングするための表を確立するステップとを含み、
前記メモリの仮想アドレスにデータを書込む際には
（ａ）  前記仮想アドレスをユニットの物理ブロックアドレスにマッピングするステップと、
（ｂ）  サブパラグラフ（ａ）で前記仮想アドレスがマッピングされた前記ユニットの前記割当表を調べて前記物理ブロックアドレスのブロックの状態が活性書込であるか非書込であるかを判断するステップとを含み、
（ｃ）  前記物理ブロックアドレスの前記ブロックが活性書込状態であれば
（１）  前記ユニットの少なくとも１つの前記割当表を調べて非書込ブロックアドレスを識別するステップと、
（２）  前記データを前記メモリの前記非書込ブロックアドレスに書込むステップと、
（３）  前記仮想アドレスがマッピングされた前記ユニットの前記割当表を変更して前記物理ブロックアドレスを削除として示すステップと、
（４）  パラグラフ（ｃ）（２）において前記データが書込まれたユニットの前記割当表を変更して前記データが書込まれた前記非書込ブロックアドレスを活性書込と示すステップと、
（５）  前記表を変更して仮想アドレスを物理アドレスにマッピングし、前記表が前記仮想アドレスを、ステップ（ｃ）（２）で前記データが書込まれた前記非書込ブロックの物理アドレスにマッピングするようにさせるステップとを含む、メモリ管理方法。
【請求項２】
前記ユニットのすべてのブロックが非書込である前記メモリ内の少なくとも１つの転送ユニットを確立するステップと、
前記少なくとも１つの転送ユニット以外の、消去されるべき選択されたユニットを周期的に識別するステップと、
前記選択されたユニットの各活性書込ブロックを読出すステップと、
前記選択されたユニットの各活性書込ブロックを前記少なくとも１つの転送ユニットに書込むステップと、
前記１つの転送ユニットの前記割当表を更新してすぐ前の書込ステップで書込まれたブロックの状態を活性書込と示すステップと、
前記選択されたユニットを消去するステップと、
仮想アドレスを物理アドレスにマッピングするための前記表を更新して前記選択されたユニットが前記１つの転送ユニットに置換され前記選択されたユニットが別の前記少なくとも１つの転送ユニットになったことを示すステップとをさらに含む、請求項１に記載のメモリ管理方法。
【請求項３】
書込まれていない物理メモリ場所にのみデータを書込むことが可能であり、連続するメモリ場所からなるゾーンを同時に消去可能なメモリのためのメモリ管理方法であって、
前記メモリにコンピュータから与えられた仮想アドレスを前記メモリの物理メモリ場所を示す物理アドレスにマッピングする第１の表を記憶するステップを含み、前記第１の表は複数のページ−アドレス可能ブロックとして編成されており、
さらに
ランダムアクセスメモリ内に、ページアドレスを前記メモリ内の前記ページ−アドレス可能ブロックの物理アドレスにマッピングする第２の表を記憶するステップと、
前記メモリ内に記憶された前記第１の表のページ−アドレス可能ブロックを、変更されたページ−アドレス可能ブロックを非書込物理ブロック場所に書込むことによって変更するステップと、
前記変更されたページ−アドレス可能ブロックのページアドレスを前記変更されたページ−アドレス可能ブロックが書込まれた非書込物理ブロック場所へマッピングするように、前記ランダムアクセスメモリ内に記憶された前記第２の表を更新するステップとを含む、メモリ管理方法。
【請求項４】
書込まれていない物理メモリ場所にのみデータを書込むことが可能であり、連続メモリ場所のゾーンを同時に消去可能なメモリのためのメモリ管理方法であって、
メモリを各々が少なくとも１つのゾーンを含む複数のユニットに編成するステップと、
各ユニットを複数のブロックに編成するステップとを含み、前記ブロックの各々は複数の連続物理メモリ場所からなり、
仮想アドレスを物理アドレスにマッピングする第１の表を確立するステップと、
前記メモリ内に複数のページ−アドレス可能ブロックとして編成された前記第１の表を記憶させるステップと、
ランダムアクセスメモリ内に、ページを、前記メモリ内にストアされた前記ページ−アドレス可能ブロックの物理アドレスにマッピングする第２の表を記憶するステップとを含み、
前記メモリの仮想アドレスにデータを書込む際には
（ａ）  前記仮想アドレスからページアドレスを引出すステップと、
（ｂ）  前記ページアドレスを前記メモリ内のページ−アドレス可能ブロックにマッピングするステップと、
（ｃ）  前記ページ−アドレス可能ブロックを読出すステップと、
（ｄ）  前記ページ−アドレス可能ブロックに基づき、前記仮想アドレスを物理アドレスにマッピングするステップとを含み、
（ｅ）  前記物理アドレスの前記ブロックが活性書込状態であれば、
（１）  前記データを前記メモリの非書込ブロックアドレスに書込むステップと、
（２）  前記ページ−アドレス可能ブロックを変更して前記第１の表が前記仮想アドレスをステップ（ｅ）（１）で前記データが書込まれた非書込ブロックの物理アドレスにマッピングするようにさせるステップと、
（３）  ステップ（ｅ）（２）からの変更されたページ−アドレス可能ブロックを前記メモリ内の非書込物理ブロック場所に書込むステップと、
（４）  前記ランダムアクセスメモリに記憶された前記第２の表を更新して、変更されたページ−アドレス可能ブロックのページアドレスを前記非書込物理ブロック場所にマッピングさせるステップとを含む、メモリ管理方法。
【請求項５】
書込まれていない物理メモリ場所のみにデータを書込むことが可能であり、連続メモリ場所のゾーンを同時に消去可能なメモリのためのメモリ管理方法であって、
前記メモリを各々が少なくとも１つのゾーンを含む複数のユニットに編成するステップと、
各ユニットを複数のブロックに編成するステップとを含み、前記ブロックの各々は複数の連続物理メモリ場所からなり、
ユニット内の各ブロック状態を活性書込、非書込または削除として示す割当表を各ユニットについて確立するステップと、
仮想アドレスを物理アドレスにマッピングするための表を確立するステップとを含み、
前記メモリの仮想アドレスにデータを書込む際には、
（ａ）  前記仮想アドレスをユニット内の物理ブロックアドレスにマッピングするステップと、
（ｂ）  サブパラグラフ（ａ）で前記仮想アドレスがマッピングされた前記ユニットの前記割当表を調べて前記物理ブロックアドレスのブロックの状態を活性書込または非書込と判断するステップとを含み、
（ｃ）  前記物理ブロックアドレスの前記ブロックが活性書込状態であれば
（１）  前記ユニットの少なくとも１つの前記割当表を調べて非書込ブロックアドレスを識別するステップと、
（２）  前記メモリの前記非書込ブロックアドレスに前記データを書込むステップと、
（３）  前記仮想アドレスがマッピングされた前記ユニットの前記割当表を変更して前記物理ブロックアドレスを削除と示すステップと、
（４）  パラグラフ（ｃ）（２）で前記データが書込まれたユニットの前記割当表を変更して前記データが書込まれた前記非書込ブロックアドレスを活性書込と示すステップと、
（５）  前記表を変更して仮想アドレスを物理アドレスにマッピングし、前記表が前記仮想アドレスをステップ（ｃ）（２）において前記データが書込まれた前記非書込ブロックの物理アドレスにマッピングするようにさせるステップとを含み、
前記メモリの仮想アドレスからデータを読出す際には
（ｄ）  前記仮想アドレスをユニットの物理ブロックアドレスにマッピングするステップと、
（ｅ）  前記メモリの前記物理アドレスから前記データを読出すステップとを含む、メモリ管理方法。
【請求項６】
前記ユニットのすべてのブロックが書込まれていない前記メモリにおいて少なくとも１つの転送ユニットを確立するステップと、
前記少なくとも１つの転送ユニット以外の、消去されるべき選択されたユニットを周期的に識別するステップと、
前記選択されたユニットの各活性書込ブロックを読出すステップと、
前記選択されたユニットの各活性書込ブロックを前記少なくとも１つの転送ユニットに書込むステップと、
前記１つの転送ユニットの前記割当表を更新してすぐ前の書込ステップで書込まれたブロックの状態を書込と示すステップと、
前記選択されたユニットを消去するステップと、
前記表を更新して仮想アドレスを物理アドレスにマッピングし、前記選択されたユニットが前記１つの転送ユニットに置換され、前記選択されたユニットが別の前記少なくとも１つの転送ユニットになったことを示すステップとをさらに含む、請求項５に記載のメモリ管理方法。
【請求項７】
書込まれていない物理メモリ場所のみにデータを書込むことが可能であり、連続メモリ場所のゾーンを同時に消去可能なメモリのためのメモリ管理方法であって、
前記メモリを各々が少なくとも１つのゾーンを含む複数のユニットに編成するステップと、
各ユニットを複数のブロックに編成するステップとを含み、前記ブロックの各々は複数の連続物理メモリ場所からなり、
仮想アドレスを物理アドレスにマッピングする第１の表を確立するステップと、
複数のページ−アドレス可能ブロックとして編成された前記第１の表を前記メモリに記憶するステップと、
ランダムアクセスメモリ内に、ページを、前記メモリ内にストアされた前記ページ−アドレス可能ブロックの物理アドレスにマッピングする第２の表を記憶するステップとを含み、
前記メモリの仮想アドレスにデータを書込む際には
（ａ）  前記仮想アドレスからページアドレスを引出すステップと、
（ｂ）  前記ページアドレスを前記メモリのページ−アドレス可能ブロックにマッピングするステップと、
（ｃ）  前記ページ−アドレス可能ブロックを読出すステップと、
（ｄ）  前記ページ−アドレス可能ブロックに基づき、前記仮想アドレスを物理アドレスにマッピングするステップとを含み、
（ｅ）  前記物理アドレスの前記ブロックが活性書込状態であれば
（１）  前記データを前記メモリの非書込ブロックアドレスに書込むステップと、
（２）  前記ページ−アドレス可能ブロックを変更して前記第１の表が仮想アドレスをステップ（ｅ）（１）で前記データが書込まれた非書込ブロックの物理アドレスにマッピングするようにさせるステップと、
（３）  ステップ（ｅ）（２）からの変更されたページ−アドレス可能ブロックを前記メモリ内の非書込物理ブロック場所に書込むステップと、
（４）  前記ランダムアクセスメモリ内に記憶された前記第２の表を更新してこれが変更されたページ−アドレス可能ブロックのページアドレスを前記非書込物理ブロック場所にマッピングするようにさせるステップとを含み、
前記メモリの仮想アドレスからデータを読出す際には
（ａ）  前記仮想アドレスからページアドレスを引出すステップと、
（ｂ）  前記ページアドレスを前記メモリ内のページ−アドレス可能ブロックにマッピングするステップと、
（ｃ）  前記ページ−アドレス可能ブロックを読出すステップと、
（ｄ）  前記ページ−アドレス可能ブロックに基づき、前記仮想アドレスを物理アドレスにマッピングするステップと、
（ｅ）  前記メモリの前記物理アドレスから前記データを読出すステップとを含む、メモリ管理方法。
【請求項８】
前記ユニットのすべてのブロックが書込まれていない前記メモリの少なくとも１つの転送ユニットを確立するステップと、
前記少なくとも１つの転送ユニット以外の、消去されるべき選択されたユニットを周期的に識別するステップと、
前記選択されたユニット内の各書込ブロックを読出すステップと、
前記選択されたユニットの各書込ブロックを前記少なくとも１つの転送ユニットに書込むステップと、
前記１つの転送ユニットのブロックの状態を示す割当表を更新してすぐ前の書込ステップで書込まれたブロックの状態を書込と示すステップと、
前記選択されたユニットを消去するステップと、
仮想アドレスを物理アドレスにマッピングするための前記第１および第２の表を更新して、前記選択されたユニットが前記１つの転送ユニットで置換され、前記選択されたユニットが別の前記少なくとも１つの転送ユニットになったことを示すステップとをさらに含む、請求項７に記載のメモリ管理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、フラッシュメモリに情報をストアし、これを取出すための改良されたシステムに関し、より特定的にはフラッシュメモリに書込まれるデータを編成し、管理するシステムに関する。
【０００２】
【従来の技術】
当業者には認められるように、フラッシュタイプのフローティングゲートトランジスタを含む電気的消去可能なプログラマブル読出専用メモリ（ＥＥＰＲＯＭ）が当該分野で説明されており、現在市場で入手可能である。これらのいわゆるフラッシュメモリは、その機能および性能の点でＥＰＲＯＭメモリと類似した不揮発性メモリであり、メモリのブロックを消去する回路内プログラマブル動作を可能にするというさらなる機能を有する。フラッシュメモリでは、以前に書込まれているメモリの領域を、その領域を前もってブロック消去することなく書替えることは慣用ではない。本発明はフラッシュメモリに関して説明されるが、当業者には、その教示がフラッシュメモリと同じ書込、読出および書込前ブロック消去特性を有するデータ記憶装置にも適用できることが理解されるであろう。
【０００３】
典型的なコンピュータシステムでは、オペレーティングシステムプログラムが、そのシステムの一部であるデータ記憶装置のデータ管理を担っている。オペレーティングシステムプログラムとの互換性を達成するために必要かつ通常は十分であるデータ記憶装置の属性は、これがデータ記憶媒体の如何なる位置からもデータを読出すことができ、これにデータを書込むことができることである。したがって、データが以前に書込まれているフラッシュメモリの領域には、この領域をまず消去するまではデータが書込まれ得ないため、フラッシュメモリは典型的な既存のオペレーティングシステムプログラムと互換性がない。
【０００４】
オペレーティングシステムプログラムを変形することなく既存のコンピュータオペレーティングプログラムによってフラッシュメモリを管理することを可能にするソフトウェア製品が先行技術において提案されている。しかしながら、これらの先行技術のプログラムは、フラッシュメモリを「書込１回読出数回」の装置として動作させる。この先行技術のソフトウェア製品は、以前に書込まれているメモリ場所を再利用できない。最終的にすべての場所が書込まれれば、特定のユーザの介入なくさらにメモリを用いることができない。
【０００５】
【発明が解決しようとする課題】
本発明のある目的は、コンピュータオペレーティングシステムにとってフラッシュメモリが如何なるフラッシュメモリ場所からもデータを読出すことができ、これにデータを書込むことができるデータ記憶装置に見えるようにフラッシュメモリへのアクセスを制御し、管理するための方法（すなわちソフトウェア、ハードウェアのファームウェア）の提供である。フラッシュメモリがランダムアクセスメモリをエミュレートすることを可能にし、既存のコンピュータオペレーティングシステムが、エミュレーション方法に依存することなく、標準的なランダムアクセスメモリによって与えられるのと同じ態様で他のすべての必要なサポートを与えることを可能にする方法を提供する。
【０００６】
【課題を解決するための手段】
簡単に言えば、本発明は、書込まれていない物理アドレス場所にデータが連続的に書込まれることを可能にするフラッシュメモリ、仮想マッピングシステムの提供を企図するものである。仮想メモリマップは、メモリ内のデータの場所を追跡するためにフラッシュメモリ物理場所アドレスを関連づける。
【０００７】
フラッシュメモリの物理場所は、バイトのアレイとして編成される。アレイ内の各バイトには、それによってバイトが物理的にアクセス可能となるアドレス番号が割当てられ、これを以下、物理アドレス空間と称する。アレイ内の各バイトは、仮想アドレス空間と称する第２のアドレスを有する。仮想マップと称する表が仮想アドレスを物理アドレスに変換する。ここで、仮想アドレス空間は必ずしも物理アドレス空間と同じサイズではないことに注目されたい。
【０００８】
連続した固定長の物理バイト群は、ブロックからアドレスする。たとえば、ブロックサイズが５１２バイトとすると、物理アドレスが２５６２１１であるバイトは、ブロック５００内のバイト番号２１１である（２５６２１１：５１２＝５００＋２１１）。適切な先行技術のフラッシュメモリ技術を用いて物理的に消去され得る１つ以上の物理的に連続したフラッシュメモリの領域（ゾーンと称する）はユニットを含み、各ユニットは整数個のブロックを含む。
【０００９】
仮想メモリマップとは、第１のエントリが仮想ブロック０に属し、第２のエントリが仮想ブロック１に属するといった具合の表である。表において各仮想ブロックアドレスと関連して、対応する物理アドレスが存在する。フラッシュメモリからの読出動作の際に、コンピュータ生成アドレスが、仮想ブロックアドレスおよびブロック内のバイト場所としてデコードされる。仮想メモリマップは、仮想ブロックアドレスを物理ブロックアドレスに変換するのに用いられる。バイト位置は仮想アドレス空間および物理アドレス空間において同じである。
【００１０】
書込動作の際に、コンピュータ生成アドレスが、やはり仮想ブロックアドレスおよびブロック内のバイト場所として解釈される。仮想メモリマップはこれを物理メモリブロックアドレスに変換する。物理アドレスに対応するフラッシュメモリブロックが現在書込まれていれば、一般にはこの物理アドレスに書込むのは不可能である。したがって、書込まれていないブロックの場所が突き止められ、これに書込まれる。仮想メモリマップは、書込まれていない物理ブロックアドレスが元の仮想アドレスにマッピングされるように変えられ、そのブロックを含むユニットを消去するゾーン消去動作が行なわれるまでは元の物理アドレスは利用不可能なものとして示され、利用不可能なままである。書込動作はブロック全体が書替られることを仮定していることが認められるであろう。これが、コンピュータシステムが通常記憶媒体内のデータにアクセスする態様である。しかしながら、一般には如何なる所望の数のバイトも新しい記憶場所に書込まれ得ることが認められるであろう。
【００１１】
本発明の好ましい実施例では、各ユニットに、そのユニットがフラッシュメモリ内の新しい物理アドレス場所に書替えられる際にも変わらないで維持される論理ユニットアドレスが割当てられる。仮想マップは、物理ユニットアドレスではなく論理ユニットアドレスへの参照を含み、そのためユニット転送中のデータの動きが仮想マップに影響を及ぼさない。
【００１２】
各ユニットは、ユニット内のすべてのブロックの利用マップ、すなわち、もしマッピングされるのであればブロックの仮想アドレス、および空いているブロックを示し、かつ利用不可能なブロックを示す特殊文字を含む。
【００１３】
以前に書込まれているフラッシュメモリの利用不可能なブロックは、利用不可能なブロックを含むメモリユニットをフラッシュメモリ内の確保されている書込まれていない空間に転送することによって再利用される。利用可能なブロックのみが転送動作において書込まれ、そのため書替えられる際に、利用不可能なブロックがあった場所は確保された空間には書替えられず、したがって利用可能である。書替えられた後、元のメモリユニット空間はユニットとしてフラッシュ消去され、したがってそこに後続の転送を行なうことができる書込まれていない確保された空間となる。
【００１４】
さらに、本発明の好ましい実施例では、フラッシュメモリに仮想マップがまずストアされ、ランダムアクセスメモリには小さな二次的な仮想マップしかない。フラッシュメモリ内の仮想マップはブロック単位でストアされ、ページに編成され、そのサイズはブロック内のバイト数とそのバイト数が表わす物理ブロックアドレスの数との積に等しい。二次的ランダムアクセスメモリはページアドレスを含む。所与の仮想アドレスについてデータを読出す際に、アドレスをページサイズで割ることによってページ番号が決定される。その結果は、正しい一次仮想マップブロックを見い出すために二次仮想マップに示される。その余りは、フラッシュメモリ内にストアされた仮想マップに関する必要な物理アドレスを計算するのに用いられる。フラッシュメモリ内の仮想マップを変更するために、変更されたマップが空いたブロックに書込まれ、一次マップ場所の変更を反映するようにランダムアクセスメモリ内の二次マップが変更される。とって代わられたブロックは削除と示される。
【００１５】
上述のおよび他の目的、局面および利点は、図面を参照して、以下の本発明の好ましい実施例の詳細な説明よりさらに理解されるであろう。
【００１６】
【発明の実施の形態】
ここで図面の図１を参照して、典型的なシステムでは、プロセッサ１０がそのオペレーティングシステムソフトウェアとともに、ランダムアクセスメモリ内の特定のアドレス場所からデータを読出し、これにデータを書込む一連の読出および書込コマンドを発行する。当業者には認められるように、ディスクメモリ等のランダムアクセス記憶装置では、データは如何なるアドレス場所にも書込まれ、またはこれから読出すことが可能である。図１のシステムでは、プロセッサ１０は特定のアドレス場所においてブロック単位でフラッシュメモリ１２にデータを書込み、かつこれからデータを読出す。フラッシュメモリ１２のゾーンは消去され得るが、現在書込まれているアドレス場所はゾーン全体が消去されるまで書替えられない。本発明の教示に従えば、フラッシュメモリコントローラ１４は完全に書替可能な仮想アドレス空間を与え、そのためフラッシュメモリ１２はディスクメモリ等のランダムアクセスメモリをエミュレートし、プロセッサオペレーティングシステムソフトウェアは標準的なランダムアクセスメモリに提供するのと同じ態様で、かつフラッシュメモリ１２およびそのコントローラ１４に依存しない態様で、他のすべての必要な動作サポート（たとえばファイスシステム）を与える。典型的なシステムはまた、従来のランダムアクセスメモリ１６を含む。コントローラ１４の機能はソフトウェア、ハードウェアのファームウェアで行なわれてもよく、図面に示されるように物理的に別個のユニットとしては必ずしも存在しないことが理解されるであろう。
【００１７】
ここで図２を参照して、フラッシュメモリの編成の一部が示される。フラッシュメモリは、ここではゾーンＡ、ゾーンＢ等で示されるいくつかのゾーンを有する。各ゾーンは、従来の周知のフラッシュメモリ技術を用いてブロック消去され得るいくつかの連続した物理メモリ場所を含む。ゾーンはユニットとして編成され、ここではそのうちの４つだけが図示されており、図面でユニット♯１、ユニット♯６、ユニットＮ−１、および転送ユニットとして示される。各ユニットは少なくとも１つのゾーンを含み、複数の連続したゾーンを含む。ここでは、各ユニットが２つのゾーン（すなわち、ユニット♯１−ゾーンＡおよびゾーンＢ、ユニット♯２−ゾーンＣおよびゾーンＤ、転送ユニット−ゾーンｘ２および２ｘ）を含むものとして示される。
【００１８】
各ユニットは整数個のアドレス可能なブロックを含み、各ブロックは連続した固定長のバイト群を含む。常に、メモリ１２には書込まれていないユニット（すなわち転送ユニット）が存在し、そのため消去されるべきユニット内の活性ブロックは、そのユニットを消去する前にこの書込まれていないユニットに書込むことができる。
【００１９】
次に図３を参照して、各ユニットは、ブロック番号およびブロック内のオフセットとしてアドレス指定することができる連続するバイトアドレスを含む、整数の数の連続するデータブロック２１を含む。ユニットの各ブロックは、ブロック番号およびブロックでのオフセットによってアドレス指定することができるユニットを有する。各ユニットは、ユニットヘッダ２３と、ユニットの各ブロックの割当状態のマップ２５とを有する。ユニットヘッダ２３は、フォーマット識別子と、ユニットの論理ユニット番号とを含む。ユニット転送の間データが物理的に移動しなければならないため、好ましくは、フラッシュメモリ１２のユニットの物理場所が変わってもユニット番号は変化しないままである。さらに、ヘッダは、システム全体の情報も含み得る。ブロック割当マップ２５は、各ブロックのために、ユニットにおけるそのブロックの状態およびオフセットを示すワードを有する。状態の表示は、「ブロックは空いており書込可能である」、「ブロックは削除され書込不可能である」、「ブロックが割当てられユーザデータを含む」、およびブロックの仮想アドレス（バックポインタ）である。
【００２０】
上述のように、好ましくは、各ユニットには、メモリにおけるユニットの物理位置が変わっても変わらない論理ユニット番号が割当られる。図４に示されるように、コンピュータ１０によって発生されたアドレス２９は、ブロック番号およびブロックオフセットを含む。これらのアドレスはフラッシュコントローラ１４によって仮想アドレスとして解釈され、仮想マップを用いて仮想アドレス空間と物理アドレス空間とを一致させるようにされる。仮想マップはブロックが書替られると変化し、したがって、仮想アドレス空間は動的なものである。なお、いかなる所与の時間にも、仮想アドレス空間における１つまたは複数のブロックが物理アドレス空間にマッピングされていなくてもよく、さらに、物理アドレス空間におけるブロックが書込まていなくてもよくしたがって自由に書込まれ得ることにも注目されたい。
【００２１】
書込まれていないユニット空間へのユニット転送の間データが物理的に動くため、ユニットには、メモリにおけるユニットの物理場所が変わっても変わらない論理ユニット番号が割当られる。２レベルのアドレス変換の第１の段階において、仮想マップ３１はブロック番号を論理ユニットアドレスにマッピングする。物理アドレスが物理ユニット番号に関するアドレスであるのと同様に、論理ユニットアドレスは論理ユニット番号に関するアドレスである。論理ユニット番号は、論理アドレスの高次２進数字であり、ビットシフト動作によって論理アドレスから引出され得る。マップ３１から得られた論理アドレス３３は、ユニット内のブロックのオフセットとともに論理ユニット番号を含む。
【００２２】
論理ユニット表３５は、論理ユニット番号を論理ユニットに関する物理ユニット番号に変換する。この２段階のアドレス変換手順により、ユニットが新しい物理位置に移動したときにマップのブロックアドレスを変える必要がなくなる。
【００２３】
読出動作において、仮想アドレス２９は、たとえば、最初にアドレスブロックにおいて論理ユニット番号およびユニット内のブロックオフセットにマッピングされるブロックアドレスを含む。マップ３５は、ユニット番号３３を、ユニットに関する物理アドレス３７、およびユニット内のブロックのアドレス３７のオフセットにマッピングし、アドレス指定されたデータブロックがこの物理的な場所から読出される。ここで、データは、典型的に行なわれるように、ブロックごとに読取られかつ書込まれると仮定する。もちろん、データは、必要であれば、同じ原理を用いてバイトごとに書込まれかつ読出されてもよい。図５は、この読出動作を説明するためのフロー図である。上述のように、２段階のアドレス変換の第１の段階で、仮想アドレス２９は論理アドレスにマッピングされる（ブロック４０）。第２の段階で、ブロック４１において、論理アドレスはフラッシュメモリの物理アドレスにマッピングされる。ブロック４２においてこの物理アドレスのデータが読出され、これによってこの動作が終了する。
【００２４】
書込動作では、仮想アドレス２９はここでも最初に論理ユニット番号およびユニット内のブロックオフセットにマッピングされる。コントローラ１４のアルゴリズムによって、このユニットに関するブロック割当マップ２５が調べられる。このアドレスに対応するブロックが既に書込まれていれば、対応する物理アドレスでは書込コマンドが実行できない。空きブロックが位置決めされるまで、制御アルゴリズムによって各ユニットに関するブロック割当マップ２５が走査される。最初のユニットアドレスでのブロックマップ２５におけるブロックの状態は割当マップにおいてブロックの削除に変えられ、空きブロックの状態は書込に変えられる。今最初の仮想アドレスが書込動作が行なわれる予定の新しい論理アドレスを指すように、仮想マップ３１が更新される。この論理アドレスは、上述のような態様で物理アドレスにマッピングされ、ブロックがこのアドレスに書込まれる。図６は、この書込動作を説明するためのフロー図である。書込動作では、ブロック４５で仮想アドレス２９が論理ユニットアドレスにマッピングされ、ブロック４６でユニットに関するユニット割当てが調べられる。判定ブロック４７でユニットアドレスが空いていれば、ブロック４８でユニットアドレスは物理アドレスにマッピングされ、ブロック４９でこの物理アドレスにデータが書込まれ、動作が終了する。論理アドレスが空いていなければ（ブロック４７）、ブロック５０で、ユニット表が走査され、ユニット割当表において空きアドレスを位置決めする。ブロック５１でこの新しい論理アドレスは物理アドレスにマッピングされ、ブロック５２でこの物理アドレスにデータが書込まれる。ユニット割当表は、最初のブロックが削除され書込不可能であり、新しいブロックが割当てられユーザデータを含むことを示すように更新される（ブロック５３）。その後、ブロック５４およびブロック５５で、仮想／論理アドレスマップは、最初の仮想アドレスに対応するデータの新しい物理アドレスを指すように更新される。
【００２５】
読出動作および書込動作を制限なく継続させることができるようにするために、物理メモリ空間は周期的に再利用される。上述のように、メモリの少なくとも１つのユニットが、その全体が空きブロックからなりかつ転送ユニットとして働くように、常に確保される。
【００２６】
次に図７を参照して、活性ユニットが選択され（ここでは、ユニット♯Ｍ）、現在マッピングされているすべての活性ブロックが読出されその後転送ユニットに書込まれる。選択されたユニット♯Ｍはその後ブロック消去され、転送ユニットとなり、活性ブロックが書込まれている転送ユニットはこの例ではユニット♯Ｍとなる。図７は、転送動作の前後のユニットの状態を示している。図８は、この転送動作のフロー図である。転送動作において、ブロック６０で転送のためのユニットが選択され、ブロック６１で、選択されたユニットの活性データブロックが読出される。その後、ブロック６２で、これらの活性データブロックは、それらの活性データブロックが最初のユニットで配置されていた場所に対応する、転送ユニットの場所に書込まれる。その後、ブロック６３で、選択された最初のユニットがフラッシュ消去され、ブロック６４で、選択されたユニットが転送ユニットとなり転送ユニットに選択されたユニットのユニット番号が割当てられるように、論理／物理アドレスマップが変えられる。
【００２７】
以上のように説明したシステムには、その内容が自由に更新される仮想マップが必要であり、そのようなマップは従来のランダムアクセスメモリにストアされ得る。しかし、たとえば、ブロックサイズが５１２バイトであると仮定すると、仮想マップが各ブロックのためにエントリを含み、各エントリがたとえば４バイト長（すなわち、４ギガバイトのメモリまでアドレス指定できる長さ）であってもよいため、８０Ｍバイトのフラッシュメモリでは、マップ表をストアするために６４０Ｋバイトのメモリが必要であろう。仮想マップをストアするのに必要なランダムアクセスメモリの量を制限するために、本発明の好ましい実施例では、マップデータの主要部分がフラッシュメモリ１２自体にストアされ、仮想アドレスをコンピュータから一次仮想マップにマッピングする二次仮想マップがメモリ１６のようなランダムアクセスメモリにストアされる。ここで、重要なポイントは、二次仮想マップの構成によって、仮想マップの読出および書込のための手順が、上述のような通常のデータの読出および書込のための手順と同一にされることである。上述の説明におけるユーザデータおよびランダムアクセスメモリにストアされた仮想マップ（すなわち、二次仮想マップ）と同じ態様で扱われる仮想マップ自体は、上述の説明における仮想マップと同等のものである。
【００２８】
本実施例では、仮想マップはフラッシュメモリ１２の負の仮想アドレスにあり、通常の空間は仮想アドレス０で始まる。仮想マップは、フラッシュメモリにある仮想マップを通常のユーザデータと同様に読出しかつ書込むことができるようにするように、仮想マップ自体によって用いられる負のアドレスをマッピングし、それ自体をマッピングする仮想マップの一部分（すなわち、二次仮想マップ）だけがランダムアクセスメモリにある。
【００２９】
簡略化された例では、６０００バイトの仮想マップが１２個の仮想マップブロックにストアされ、その各々のブロックが５１２バイトであると仮定する。アドレスが４バイトであると仮定すると、各ブロックは１２８個の物理アドレスをストアすることができる。したがって、各ブロックは、仮想フラッシュメモリの６４Ｋバイトのアドレスを含む。仮想フラッシュメモリのアドレスからなる各ブロックはページとして考えられ、ランダムアクセスメモリは、アドレスブロックにマッピングされるページアドレス（この例では、４８バイトだけ）をストアする。所与の仮想アドレスからデータを読出す際に、アドレスはページサイズ（６４Ｋバイト）で除算され、アドレスがストアされる一次仮想マップのページブロックにマッピングする二次仮想メモリのページ番号が得られる。仮想メモリページブロックを用いて、特定のフラッシュメモリの物理アドレスにマッピングする手順を、上述の態様で行なうことができる。たとえば、仮想アドレスをページサイズで除算した後、その剰余を仮想メモリブロックサイズ（たとえば、５１２）で除算してフラッシュメモリから読出されるアドレスのアレイに対するインデックスを得ることができる。
【００３０】
所与の仮想アドレスにデータを書込む際に、コンピュータによって発生されたアドレスもページサイズで除算され、フラッシュメモリの二次仮想マップに対するインデックスが得られる。二次仮想マップは、一次仮想マップブロックが読出される一次仮想マップにマッピングし、これは、読出される、アドレス指定された物理ブロックにマッピングするのに用いられる。このブロックは書替えすることができないため、書込みされていないブロックが識別され、そこに、削除として示される最初のデータブロックが上述の態様で書込まれる。フラッシュメモリにある仮想マップを更新するために、本質的に同じ手順がその後に行なわれる。アドレスデータの新しい物理場所を反映するように変形された形の仮想マップブロックは、フラッシュメモリの書込みされていないブロックに書込まれ、古いブロックは削除として示される。ランダムアクセスメモリの二次仮想メモリは、必要に応じて、一次仮想メモリブロックの場所の変化を反映するように変えられる。
【００３１】
図９は、この動作のフロー図である。このプロセスの第１のステップは、ブロック７０で仮想アドレスをページ番号に変換し、ブロック７１で、ページ番号を用いてフラッシュメモリ１２にストアされた仮想マップの関連するページブロックのアドレスをＲＡＭ１６において位置決めすることである。このアドレスでの仮想マップのページブロックは、フラッシュメモリから読出され（ブロック７２）、上述の態様で用いられて、データ読出動作またはデータ書込動作のために仮想アドレスに対応する物理アドレスを位置決めする。データ書込動作では、ブロック７３で仮想マップのページブロックを更新しなければならず、ブロック７４で、更新されたページブロックの仮想マップはフラッシュメモリの空き物理アドレス場所に書込まれる。ブロック７５で、ページブロックの仮想マップが配置されていた最初のフラッシュメモリアドレスが削除として示され、ブロック７６で、ＲＡＭメモリ１６は、更新されたマップに関する仮想／物理マップアドレスを指すように更新される。
【００３２】
仮想マップは、システムの始動の際に容易に再構成することができる。フラッシュメモリにある仮想マップは不揮発性であり、再構成する必要はない。揮発性ランダムアクセスメモリにある二次仮想マップは、始動時に各ユニットの頂部にあるブロック利用マップを走査することによって再構成することができる。仮想アドレスにマッピングされたとして示されたブロックが識別され、それに応じて二次仮想マップが構成される。
【００３３】
以上、本発明を１つの好ましい実施例に関して説明したが、前掲の特許請求の範囲の精神および範囲内で本発明に変形を加えることができることが当業者により認識されるであろう。
【図面の簡単な説明】
【図１】  図１は、本発明の教示に従うシステムの一実施例のシステムの機能的構成要素を示すブロック図である。
【図２】  図２は、本発明の教示に従うフラッシュメモリ編成の１レベルの図的表現である。
【図３】  図３は、ユニットが如何にフォーマット化されるかを示す図的表現である。
【図４】  図４は、コンピュータ生成アドレスが物理アドレスに如何にマッピングされるかを示す図的表現である。
【図５】  図５は、読出動作を示すフロー図である。
【図６】  図６は、書込動作を示すフロー図である。
【図７】  図７は、転送動作の前および後のユニットの状態を示す図的表現である。
【図８】  図８は、転送動作のフロー図である。
【図９】  図９は、仮想−物理マップの大部分がフラッシュメモリ内にストアされる動作を示すフロー図である。
【符号の説明】
１０  プロセッサ、１２  フラッシュメモリ、１４  フラッシュメモリコントローラ、１６  ランダムアクセスメモリ、２１  データブロック、２３  ユニットヘッダ、２５  ブロック割当マップ、２９  仮想アドレス、３１  仮想マップ、３３  論理アドレス、３５  論理ユニット表、３７  物理アドレス
【図１】
0003997130.tif 000002
【図２】
0003997130.tif 000003
【図３】
0003997130.tif 000004
【図４】
0003997130.tif 000005
【図５】
0003997130.tif 000006
【図６】
0003997130.tif 000007
【図７】
0003997130.tif 000008
【図８】
0003997130.tif 000009
【図９】
0003997130.tif 000010