(57)【要約】【課題】  特定のハードウェアに依存しない構成を持つメモリ制御方法および装置を提供する。【解決手段】  メモリを、それぞれ所定サイズを持つ複数のページと、ページを複数含み且つメモリの消去ブロックの整数倍のサイズを持つ複数のセグメントとによる階層的な構成とし、セグメント単位で消去回数を管理するとともに、上位プログラムからのアクセス要求を受けページ単位でメモリ内の記憶領域を指定するメモリ制御方法であって、ＲＡＭ上に所定容量のＲＡＭ領域を確保し、確保されたＲＡＭ領域をセグメントとページによる階層的な構成とみなし、上位プログラムからの論理ページ番号を指定してのアクセス要求を受けて、確保されたＲＡＭ領域に対してページ単位でアクセスを行うエミュレート手順を含むメモリ制御方法を提供する。【選択図】    図２
2006099797.tif 000002
【特許請求の範囲】
【請求項１】
メモリを、それぞれ所定サイズを持つ複数のページと、前記ページを複数含み且つ前記メモリの消去ブロックの整数倍のサイズを持つ複数のセグメントとによる階層的な構成とし、前記セグメント単位で消去回数を管理するとともに、上位プログラムからのアクセス要求を受け前記ページ単位で前記メモリ内の記憶領域を指定するメモリ制御方法であって、
ＲＡＭ上に所定容量のＲＡＭ領域を確保し、前記確保されたＲＡＭ領域を前記セグメントと前記ページによる階層的な構成とみなし、前記上位プログラムからの論理ページ番号を指定してのアクセス要求を受けて、前記確保されたＲＡＭ領域に対して前記ページ単位でアクセスを行うエミュレート手順を含むこと、を特徴とするメモリ制御方法。
【請求項２】
メモリを、それぞれ所定サイズを持つ複数のページと、前記ページを複数含み且つ前記メモリの消去ブロックの整数倍のサイズを持つ複数のセグメントとによる階層的な構成とし、前記セグメント単位で消去回数を管理するとともに、上位プログラムからのアクセス要求を受け前記ページ単位で前記メモリ内の記憶領域を指定するメモリ制御方法であって、
上位プログラムより指定セグメントサイズおよび指定ページサイズを伴う物理フォーマット要求を受け取った場合に、前記メモリ内の前記指定セグメントサイズで規定される全てのセグメントについて、各セグメント内の全消去ブロックを消去する手順と、各セグメントのセグメント管理情報に初期状態に対応する情報を書き込む手順と、から成る物理フォーマット手順と、
前記メモリ内の少なくとも１つのページについて、ページ管理情報にページサイズを含む、ページが有効であることを示す情報を書き込む手順と、
前記メモリ内の有効なページを検索して前記検索されたページのページ管理情報からページサイズを取得する手順と、
を含むことを特徴とするメモリ制御方法。
【請求項３】
前記請求項１または請求項２に記載のメモリ制御方法において、前記メモリの記憶領域は、前記セグメントとセグメント内のオフセットに対応する仮想アドレスで指定されること、を特徴とするメモリ制御方法。
【請求項４】
メモリを、それぞれ所定サイズを持つ複数のページと、前記ページを複数含み且つ前記メモリの消去ブロックの整数倍のサイズを持つセグメントとによる階層的な構成とするとともに、前記セグメントをデータ領域とセグメント管理情報の格納領域に分け、前記ページをデータ領域とページ管理情報の格納領域とに分けた構成であるとみなすことにより、論理ページ番号を指定単位として記憶装置へのアクセスを行う上位プログラムから前記論理ページ番号を指定したアクセス要求を受け取り、受け取った前記論理ページ番号をセグメント番号とオフセットに対応する仮想アドレスに変換するアドレス変換手順を含むこと、を特徴とするメモリ制御方法。
【請求項５】
前記請求項１から請求項４のいずれかに記載のメモリ制御方法をコンピュータで実行するためのソフトウェア。
【請求項６】
前記請求項１から請求項４のいずれかに記載のメモリ制御方法によりメモリの読み書きを制御するメモリ制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリをファイルおよびデータ記憶用途として用いる為のメモリ制御方法および装置に関する。
【背景技術】
【０００２】
情報機器の普及を背景として、フラッシュメモリの利用が拡大している。フラッシュメモリは、電気的に消去および再書き込みができる不揮発性メモリである。フラッシュメモリは、複数の消去ブロックから構成され、消去ブロックを単位として消去する構成であり、また各消去ブロックには数万回程度といわれる消去回数の寿命がある。
【０００３】
また、フラッシュメモリの利用拡大と共に、フラッシュメモリをハードディスクのような外部記憶装置用途として用いるためのファイルシステムの実現が要求されている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
このようなファイルシステムにおいて、メモリアクセスに関する高速化・高信頼化などの要求があるのはもちろんのこと、フラッシュメモリが消去ブロックを消去単位としていること、データが書き込まれた位置に直接上書きをすることができないことなどから、フラッシュメモリを外部記憶装置として用いる為の効率的な制御が要求される。また、フラッシュメモリは様々な情報機器に搭載されることから、ファイルシステムを特定のＣＰＵやＯＳ（Operating System）に依存しないように構成する必要が生じる。
【０００５】
本発明は、このような事情に鑑みてなされた。すなわち本発明の目的は、特定のハードウェアに依存しない構成を持つメモリ制御方法および装置を提供することである。
【課題を解決するための手段】
【０００６】
上記目的を達成するため、本発明に係るメモリ制御方法は、メモリを、それぞれ所定サイズを持つ複数のページと、前記ページを複数含み且つ前記メモリの消去ブロックの整数倍のサイズを持つ複数のセグメントとによる階層的な構成として管理する。さらに、前記セグメント単位で消去回数を管理するとともに、上位プログラムからのアクセス要求を受け前記ページ単位で前記メモリ内の記憶領域を指定するメモリ制御方法とする。さらにこのメモリ制御方法に、ＲＡＭ上に所定容量のＲＡＭ領域を確保し、前記確保されたＲＡＭ領域を前記セグメントと前記ページによる階層的な構成とみなし、前記上位プログラムからの論理ページ番号を指定してのアクセス要求を受けて、前記確保されたＲＡＭ領域に対して前記ページ単位でアクセスを行うエミュレート手順を含める。ＲＡＭで前記メモリをエミュレートし、ソフトウェア開発を容易にする。前記メモリやターゲットのハードウェアがなくてもソフトウェア開発が可能になる。
【０００７】
また、上記目的を達成するため、本発明に係るメモリ制御方法は、メモリを、それぞれ所定サイズを持つ複数のページと、前記ページを複数含み且つ前記メモリの消去ブロックの整数倍のサイズを持つ複数のセグメントとによる階層的な構成として管理する。さらに、前記セグメント単位で消去回数を管理するとともに、上位プログラムからのアクセス要求を受け前記ページ単位で前記メモリ内の記憶領域を指定するメモリ制御方法とする。さらにこのメモリ制御方法に、
上位プログラムより指定セグメントサイズおよび指定ページサイズを伴う物理フォーマット要求を受け取った場合に、前記メモリ内の前記指定セグメントサイズで規定される全てのセグメントについて、各セグメント内の全消去ブロックを消去する手順と、各セグメントのセグメント管理情報に初期状態に対応する情報を書き込む手順と、から成る物理フォーマット手順と、
前記メモリ内の少なくとも１つのページについて、ページ管理情報にページサイズを含む、ページが有効であることを示す情報を書き込む手順と、
前記メモリ内の有効なページを検索して前記検索されたページのページ管理情報からページサイズを取得する手順と、を含める。ページサイズをメモリから取得でき、ページサイズをＲＡＭなどに保持する必要がなくなる。ページサイズを上位プログラムなどの固定値とする必要がなくなり、システムの柔軟性が増す。
【０００８】
また、上述したメモリ制御方法において、前記メモリの記憶領域は、前記セグメントとセグメント内のオフセットに対応する仮想アドレスで指定される。仮想アドレスでメモリにアクセスする構成とすることで、ターゲットのハードウェアに依存しないようにし、本メモリ制御方法を実現したソフトウェアモジュールの移植性を高めることができる。
【０００９】
さらに、上記目的を達成するため、本発明に係るメモリ制御方法は、メモリを、それぞれ所定サイズを持つ複数のページと、前記ページを複数含み且つ前記メモリの消去ブロックの整数倍のサイズを持つセグメントとによる階層的な構成とするとともに、前記セグメントをデータ領域とセグメント管理情報の格納領域に分け、前記ページをデータ領域とページ管理情報の格納領域とに分けた構成であるとみなすことにより、論理ページ番号を指定単位として記憶装置へのアクセスを行う上位プログラムから前記論理ページ番号を指定したアクセス要求を受け取り、受け取った前記論理ページ番号をセグメント番号とオフセットに対応する仮想アドレスに変換するアドレス変換手順を含む。仮想アドレスでメモリにアクセスする構成とすることで、ターゲットのハードウェアに依存しないようにし、本メモリ制御方法を実現したソフトウェアモジュールの移植性を高めることができる。
【発明の効果】
【００１０】
したがって、本発明によれば、特定のハードウェアに依存しない構成を持つメモリ制御方法およびそれを用いた装置を提供することができる。
【発明を実施するための最良の形態】
【００１１】
図１は、本発明の実施形態としての物理記憶デバイスドライバモジュール５（以下、ＰＤＭ５と記す）の位置付けを表している。図１に示すように、アプリケーションプログラム１からのファイルアクセスは、論理ファイルシステムモジュールであるＬＦＭ３によって論理ページ（セクタ）単位のアクセスとされる。つまり、ＬＦＭ３は、ディスク装置の論理セクタをアクセスするように、ＰＤＭ５に対してアクセスを行う。ＬＦＭ３は、ファイルアクセスを、論理ページ番号をアドレス指定単位とするアクセスにする機能を持つ他、主な機能としてＦＡＴ（File Allocation Table）の管理、パーティションの管理などを行う、一般的な論理ファイルシステムモジュールであるものとする。
【００１２】
ＰＤＭ５は、ＬＦＭ３からアクセス要求として指定された論理ページ番号をもとに、ＰＤＭ５内で管理するフラッシュメモリＡ、またはＢ内のセグメント番号とオフセット（物理ページ番号）に対応する仮想アドレスを指定して、下位モジュールのメモリテクノロジドライバモジュール７（以下、MTDM７と記す）に対してアクセス要求を行う。MTDM７は、ＰＤＭ５からの仮想アドレスを、システム内の実メモリアドレスに変換してフラッシュメモリＡ、またはＢにアクセスする機能を提供する。
【００１３】
以下では、ＰＤＭ５が提供するメモリ制御機能を下記の項目順に詳細に説明する。
１．フラッシュメモリの構造化
２．フラッシュメモリ内の物理ページの検索
３．フラッシュメモリへの論理ページ書き込み
４．フラッシュメモリの論理ページ削除
５．フラッシュメモリからの論理ページ読み出し
６．ガベージコレクション（ＧＣ）
７．ウエアレベリング（Wear Leveling）
８．インクリメンタルガベージコレクション（ＩＧＣ）
９．ページ位置のキャッシング
１０．メディアへの書き込み・消去の一時停止
１１．不良ページへの対処
１２．不良セグメントへの対処
１３．書き込みデータのフラッシュメモリとアプリケーションへの適応化
１４．書き込みデータのページごとのフラッシュメモリへの適応化
１５．メディアの物理フォーマット処理
１６．メディアの論理フォーマット処理
１７．メディアのロック・ロック解除
１８．書き込み中の中断からの回復
１９．物理フォーマット・消去中の中断からの回復
２０．物理メモリフルでのデッドロックの回避
２１．ページ割当てマップ（PAM）
２２．自動ガベージコレクション（自動ＧＣ）
２３．ＧＣ開始条件
２４．書き込みデータの適応化
２５．最終割り当てページ位置記憶
２６．最終検索ページ位置記憶
２７．ページデータサイズの自動判定
２８．物理フォーマットの自動判定
２９．ＰＤＭ５における仮想アドレス空間
３０．メモリ待ち時間の自動判定
３１．フラッシュメモリドライバへの特化
３２．ＲＡＭによるフラッシュメモリのエミュレーション
【００１４】
また、本明細書において用いる用語を次のように定義する。
「消去ブロック」: フラッシュメモリが１度に消去するメモリ領域（例えば、NOR型のフラッシュメモリでは64kB, NAND型のフラッシュメモリでは8kB程度である）
「ガベージコレクション（ＧＣ）」: フラッシュメモリ中のデータを書き換える場合、同じ領域に繰り返して書き込むことが不可能なので、別な領域に書き換えデータを書き込む。それを繰り返すと、メモリが古いデータ（無効なデータ）で一杯になるため、消去ブロック中の有効なデータだけを別なユニットにコピーし、その消去ブロックを消去する必要がある。そのコピー・消去処理をガベージコレクションという。
「ウエアレベリング（Wear leveling）」: フラッシュメモリは、消去ブロックごとに消去回数の上限が決っているため、同じユニットを繰り返して使うと、そのユニットの寿命が短くなる。それを防ぐために、各ユニットを平均して使うための処理。
「NOR型フラッシュメモリ」: 1バイト単位でランダムアクセス可能なフラッシュメモリ
「NAND,AND型フラッシュメモリ」: ページ(通常 512+16バイト)単位でアドレスを指定し、1バイトずつシリアルにアクセスするフラッシュメモリ
「ページ」: ＰＤＭ５が扱う最小のデータブロック (通常512バイト)
「物理ページ」: フラッシュメモリ中の物理的順序で規定されるページ。
「論理ページ」: 論理的な番号(論理ページ番号)で指定されるページ。ディスクの論理セクタに対応する。
「セグメント」: ＰＤＭ５が、ガベージコレクション・消去を行う単位。物理ページ、消去ブロックの集合。
【００１５】
なお、以下では、ステップ番号を用いて各処理単位の手順を説明しているが、各処理単位では原則としてステップ番号の若い順に手順が実行されるものとする。同一のステップ番号に「'」「"」などの記号を付加して用いたステップ番号は、条件によって処理内容が変わる場合などを示している。なお、本発明の範囲を逸脱しない範囲で、各処理単位における手順の順序を変える、手順の一部を省くなどの変形を行うことができることはいうまでもない。
【００１６】
１．フラッシュメモリの構造化
ＰＤＭ５は、フラッシュメモリを図２のように構造化して管理する。図２を参照して、ＰＤＭ５におけるフラッシュメモリの構造化について説明する。
フラッシュメモリチップのメモリ領域５０を、等しいサイズを持つ複数の「セグメント」（符号２０）に分割する。ここで、セグメントは次のような性質を持つ。
・各セグメントは、固有の番号「物理セグメント番号」を持つ。
・システム内にメモリチップが複数存在する場合、物理セグメント番号は、システム内で一意に割り当てられる。
・セグメントは、等しいサイズを持つ複数の「ページ」より構成される。
・セグメントは、フラッシュメモリでデータを消去する単位である「消去ブロック」（符号４０）を、１つ以上含む。
・セグメントは、消去ブロックの整数倍の大きさを持つ。
【００１７】
また、各セグメントは、セグメント内に、自セグメントの管理情報(セグメントの状態、消去回数)（符号２１）を持つ。セグメントの管理情報の格納位置は、全セグメントで同じであるものとする。
【００１８】
ＰＤＭ５において、セグメントの状態は次の５種類で管理される。セグメントの状態の定義を以下に示す。
「未使用」: セグメントが未使用である。(メモリの消去直後の状態)
「有効」: セグメントが有効である。(セグメントはフォーマット済みである。ページを読み書き可能である。)
「削除済み」: セグメントは無効である。(セグメント内に有効なデータはない)
「不良」: セグメントは不良である。(セグメントのメモリの大半が不良であるので使用できない)
「予約」: セグメントは予約されている。
【００１９】
図３は、セグメント管理情報２１の一例を示している。図３に示す例において、セグメント管理情報２１には、マジックコード（領域２２）、セグメントの状態管理（領域２３）、および消去回数の管理（領域２４）のための領域が含まれている。マジックコード（領域２２）としては、例えば文字列“ＳＥＧ”を使用することができる。セグメントの状態管理の領域２３では、ｂビット、ｄビット、ｖビット、ｒビットの各ビットによって、それぞれ、セグメントの「不良」、「削除済み」、「有効」、「予約」の各状態を管理する。また、セグメントの消去回数の管理領域２４には、セグメントの消去回数を書き込む。
【００２０】
上位モジュール（ＬＦＭ３など）は、ページサイズを単位として、フラッシュメモリにアクセスし、フラッシュメモリ内のページを「論理ページ番号」で指定する。なお、論理ページ番号は、連続する一意の整数である。ページ（符号３０）は、次のような性質を持つ。
・各ページは、セグメント内で固有な「物理ページオフセット」を持つ。
・物理ページオフセットは、実際には、０から始まるセグメント内のページの通し番号である。
・ページは、物理セグメント番号と物理ページオフセットの組(「物理ページ番号」)で一意に指定される。
・各ページは、ページ内に自ページの管理情報３１(論理ページ番号、ページの状態、拡張情報)と、データを記録する領域３６(「ページデータ」)を持つ（図４参照）。
【００２１】
ページの状態は次の５種類で管理される。ページの状態の定義を以下に示す。
「未使用」: ページが未使用である。(メモリの消去直後の状態)
「有効」: ページが有効である。(ページ内のデータが有効である)
「削除済み」: ページは削除された。(ページ内のデータは更新された)
「不良」: ページは不良である。(ページのメモリが不良であるので使用できない)
「予約」: ページは予約されている。(ページに書き込み中である)
各ページは、拡張情報として、「更新中フラグ」「反転フラグ」を持つ。
【００２２】
図４は、ページの詳細な構成の一例を示している。図４に示す例において、ページ管理情報３１には、マジックコード（領域３２）、ページの状態管理（領域３３）、論理ページ番号（領域３４）、および拡張情報（領域３５）のための領域が含まれている。マジックコード（領域３２）としては、例えば文字列“ＰＡＧＥ”を使用することができる。ページの状態管理の領域３３では、ｂビット、ｄビット、ｖビット、ｒビットの各ビットによって、それぞれ、ページの「不良」、「削除済み」、「有効」、「予約」の各状態を管理する。領域３４には、論理ページ番号を格納する。また、拡張情報の領域３５の、ｕビット、ｉビットの各ビットは、それぞれ、「更新中フラグ」、「反転フラグ」として用いられる。
【００２３】
上記のように、ＰＤＭ５は、ページ・セグメント自体に自分の管理情報を持たせるため、管理情報を「テーブル」として集中させてフラッシュメモリ内に格納する他の方式に比べ、以下のメリットがある。
・テーブル破損によるメモリの管理構造の破壊の危険性が少ない。
・ページ書き換えの際に、書き換える箇所が１箇所で済むため、書き換え速度が高速になる。
【００２４】
２．物理ページの検索
上位モジュールから受け取った論理ページ番号をもとにフラッシュメモリ内のページ(「物理ページ」)にアクセスするために、論理ページ番号から物理ページ番号に変換する必要がある。論理ページ番号から物理ページ番号に変換することは、以下の手順（以下、ページ検索処理と記す）によって達成される。
（手順）
ステップS201. システム中の全セグメントより、状態が「有効」のセグメントを探す。
ステップS202. そのセグメント内で、状態が「有効」のページを探す。
ステップS203. そのページの管理情報より論理ページ番号を読み出し、アクセス対象の論理ページ番号と一致するか調べる。
ステップS204. アクセス対象の論理ページ番号と、ページの管理情報の論理ページ番号が一致するページを見つけるまで、S201-S203を繰り返す。
なお、物理ページの検索には時間がかかるため、ページ情報のキャッシング(後述の「９．ページ位置のキャッシング」参照)を行うことで速度を向上させることができる。
【００２５】
３．フラッシュメモリへの論理ページ書き込み
上位モジュールから論理ページ番号を指定しての書き込み要求があると、ＰＤＭ５は、以下の手順でフラッシュメモリへの書き込み処理を行う。
（手順）
ステップS301. 論理ページ番号により、アクセス対象の物理ページを検索する(上記のページ検索処理による)。
ステップS302. メモリより未使用ページを探し、そのページにアクセス対象の論理ページ番号を割り当て、状態を「予約」にする。
ステップS303. 新しく割り当てたページにデータを書き込む。
ステップS304. (S301でアクセス対象の物理ページが存在していた場合)元の物理ページの「更新中フラグ」を有効にする。
ステップS305. 新しく割り当てたページの状態を「有効」にする。
ステップS306. (S301でアクセス対象の物理ページが存在していた場合) 元の物理ページを削除する(後述の「４．フラッシュメモリの論理ページ削除」参照)。
以下の説明では、アクセス対象の物理ページが存在しない場合のページ書き込み処理を「新規ページ書き込み」、アクセス対象の物理ページが存在する場合のページ書き込み処理（S304,S306が伴う）を「ページ上書き」と表現する。
【００２６】
フラッシュメモリへの書き込み処理を上記のような手順によって行うことで、以下のようなメリットが得られる。
・書き込み中(S301-S305)に中断しても、元のページまたは、新しいページが完全な状態で残る。
・書き込み中(S303-S305の間)に中断された場合、新しいページは「予約」状態で残るため、再起動後、ＧＣ可能である（ＧＣの対象とすることができる）。
・元の物理ページの削除前に中断された場合、古いページの「更新中フラグ」が有効なので、書き込みの中断があったことを知ることができる。同じ論理ページ番号で、「更新中フラグ」が無効なページがある場合、古いページを削除することができる。なお、中断とは、書き込み処理中のシステムの電源断などによる処理の中断をいう。
【００２７】
４． フラッシュメモリの論理ページ削除
上位モジュールから論理ページ番号を指定しての削除要求があると、ＰＤＭ５は、以下の手順でフラッシュメモリのページ削除処理を行う。
（手順）
ステップS401. 論理ページ番号により、アクセス対象の物理ページを検索する(上記のページ検索処理による)。
ステップS402. 物理ページを削除する（S411）。
ここで、フラッシュメモリの物理ページ削除は、下記の手順で行う。
ステップS411. 物理ページの状態を「削除済み」にする。
【００２８】
５． フラッシュメモリからの論理ページ読み出し
上位モジュールから論理ページ番号を指定しての読み出し要求があると、ＰＤＭ５は、以下の手順でフラッシュメモリからの読み出し処理を行う。
（手順）
ステップS501. 論理ページ番号により、アクセス対象の物理ページを検索する(上記のページ検索処理による)。
ステップS502. (S501でアクセス対象の物理ページが存在していた場合) その物理ページのデータを読み出す。
ステップS502'. (S501でアクセス対象の物理ページが存在していない場合) ダミーのデータを読み出す。
【００２９】
６． ガベージコレクション(GC)
フラッシュメモリの空き容量が少なくなった場合、以下の手順で、ガベージコレクションを行う。
（手順）
ステップS601. Wear leveling(後述の「７．ウェアレベリング（Wear Leveling）」参照)の基準により、ガベージコレクション対象のセグメントを探す。
ステップS602. 対象のセグメント内の「有効」のページを探す。これを、「元のページ」とする。
ステップS603. 別なセグメント内に新しいページを割り当て、状態を「予約」とする。これを、「新しいページ」とする。
ステップS604. 新しいページに、元のページのデータと管理情報(ページの状態を除く)をコピーする。
ステップS605. 新しいページの状態を「有効」にする。
ステップS606. 元のページを削除する(S411)。
ステップS607. 対象のセグメント内の全ページが削除済みになるまでS602-S605を繰り返す。
ステップS608. 対象のセグメントの状態を「削除済み」にする。
ステップS609. 対象のセグメントの消去回数をRAMに保存する。
ステップS610. 対象のセグメントを消去する。
ステップS611. 対象のセグメントに管理情報を書き込む。その際、状態を「有効」にし、消去回数を１加算する。
【００３０】
ガベージコレクションを上記の手順で実現することで、以下のようなメリットがある。
・ガベージコレクションでページをコピーする際、ページに含まれる論理ページ番号は変更せずにそのままコピーできるため、他の方式に比べて処理が簡素化され、高速である。
・ガベージコレクションでコピーするのは、ページだけであるので、複数の領域をコピーし、更新する他の方式に比べて高速である。
・ガベージコレクション中(S601-S608)に中断しても、元のページまたは、新しいページが完全な状態で残る。
・ガベージコレクション中断後、「予約」のページを検索することで、不完全なページの存在を知ることができる。
・消去中(S609-S611)に中断しても、他のセグメントはそのままの状態で残る。
・消去中断後、セグメントの状態が「削除済み」のセグメントを検索することで、不完全なセグメントの存在を知ることができる。
・GCを開始する条件の詳細については、後述の「２３．ＧＣ開始条件」にて詳細に説明する。
【００３１】
７．ウェアレベリング（Wear leveling）
Wear levelingは、フラッシュメモリチップの寿命を延ばすため、各消去ブロックの消去回数を平均化する目的で行われる処理である。すわわち、ＰＤＭ５は、新しいページを割り当てる場合およびＧＣ対象のセグメントを検索する際、次の要素を考慮してセグメントを選択するようにする。
・最も消去回数の少ないセグメント
・最も「削除済み」ページの多いセグメント
なお、ＰＤＭ５は、セグメントを消去する前に、セグメントに記憶されているセグメントの消去回数を、RAMに保存しておく。そして、セグメントの消去の完了後、ＰＤＭ５は、RAMに保存しておいた消去回数を１増やしてセグメントに設定する。
【００３２】
Wear levelingの詳細について以下に説明する。
Wear levelingは、ＰＤＭ５において次のような処理のために用いられる。
・新しいページを割り当てるセグメントの選択処理（書き込み処理、ＧＣ）
・ガベージコレクション対象セグメントの選択処理
【００３３】
まず、新しいページを割り当てる場合のWear levelingについて説明する。新しいページを割り当てる場合のWear levelingを、より適正なものにするために考慮される要素は以下のa〜eである。なお、以下の全ての要素を考慮する必要は必ずしも無い。
a. セグメントの消去回数
理由: 
1. Wear levelingは、各セグメントの消去回数を平均化するものであるから、セグメントの消去回数を考慮する必要があるのは明白である。
2. ページ割り当ては将来的に、セグメントの消去を引き起こすから、消去回数の少ないセグメントを選ぶことが、セグメントの消去回数の平均化につながるためである。
b. セグメントの空き率 (空きページ数)
理由: 次のページ割り当ても同じセグメントから行えるようにすることで、処理速度を向上させるためである。
c. セグメントの有効(使用中)ページ数
理由: 有効ページ数が少ないセグメントほど連続してページを割り当てられるため、ページ割り当てを高速化できるためである。
d. セグメントの削除済みページ数
理由: 削除済みページ数の多いセグメントは、GC処理が高速になるので、セグメントを使い切ることで、このセグメントに対する将来のGCを高速化できるためである。
e. 前回割り当てたページのセグメント
理由: セグメントを必ず使い切ることでメモリ使用効率を向上させ、ページ割り当てを高速化できるためである。
【００３４】
Wear leveling（新規割り当て）処理の手順を以下に示す。
（手順）
ステップS700. 前回本処理によって割り当てたセグメントに空きページが存在していたら、そのセグメントを使用する (この時、前回割り当てたページの次から空きページを検索する)。これは、セグメントを使い切るため、高速化のためである。
ステップS701. 空きページが存在し、セグメントの消去回数の少ないセグメントをＭ個見つける。ここでは、一例として最も少ない消去回数をminEcとした場合、消去回数が minEc x 1.1以下であるという条件で、セグメントをさがすものとする。実際に見つかったセグメントの個数をＣ１とする。なお、消去回数の少ないセグメントを選ぶのは、ページ割り当てが将来的なセグメント消去につながるからである。
ステップS702. Ｃ１＞１の場合、 S701で見つかったセグメント中で空きページ数の多い上位M／２個を見つける。実際に見つかったセグメントの個数をＣ２とする。ここで、空きページ数の多いものを選ぶのは、次の割り当ても同じセグメントから行えるようにすることで、処理速度を向上させるためである。なお、空きページ数の多い上位M／２個を見つけるのは一例に過ぎず、Mよりも小さければ特に限定されるものではない。
ステップS703. Ｃ２＞１の場合、任意の１個を対象にする。Ｃ２個のセグメントのうちセグメント番号の最も若いものを対象にしても良い。
なお、以上のWear leveling（新規割り当て）処理において、Ｃｎ（ｎ；１，２）が１となった場合には、そのセグメントを対象として本処理を終了することができる。
【００３５】
次に、ＧＣ対象セグメントを選択する場合のWear levelingについて説明する。なお、ＧＣするかどうかは、事前に決定しているものとする。ＧＣ対象セグメントを選択する場合のWear levelingを、より適正なものにするために考慮される要素は以下のa〜eである。なお、以下の全ての要素を考慮する必要は必ずしも無い。
a. セグメントの消去回数
理由: Wear levelingは、各セグメントの消去回数を平均化するものであるから、セグメントの消去回数を考慮する必要があるのは明白である。
b. セグメントの空き率 (空きページ数)
理由: 空きページの多いセグメントは、まだ書き込み可能であるので、なるべく消去しないほうが、メモリの消去回数が減り、メモリの寿命を延ばすことが可能であるからである。
c. セグメントの有効(使用中)ページ数
理由: 有効ページ数の少ないセグメントは、移動すべきページ数が少ないので、ＧＣ処理が高速になるからである。
d. セグメントの削除済みページ数
理由: 全ページが削除済みのセグメントは、そのままでは使用不能であるので、消去すべきであるし、ページの移動が不要なので、ＧＣ処理が高速になるからである。
e. 近い過去に消去したセグメント
理由: 同じセグメントの連続消去を避けることで、消去回数を平均化させるためである。
【００３６】
Wear leveling（ＧＣ対象決定）処理の手順を以下に示す。
（手順）
ステップS750. 前回ＧＣ(または消去)したセグメントは対象外にする。これは、同じセグメントの連続消去を避けるためである。
ステップS751. 空き(全ページが未使用)でなく、セグメントの消去回数の少ないセグメントＮ個を見つける。ここでは一例として、最も少ない消去回数をminEcとした場合、消去回数が minEc x 1.1以下であるという条件で、セグメントをさがすものとする。実際に見つかったセグメントの個数をＣ２とする。
ステップS752. Ｃ２＞１の場合、S751でみつかったセグメントの中で、全ページが削除済みのセグメントを見つける。ここで、みつかったセグメントの個数をＣ３とする。全ページが削除済みのセグメントは、消去すべきであるし、ＧＣ処理が高速になるからである。
ステップS753. Ｃ３≠０である場合、S752で見つかったセグメントのうちどれか一つをＧＣ対象として決定する。
ステップS753' (強制モード). [Ｃ２>１ かつ Ｃ３==0の場合] S751で見つかったセグメント（Ｃ２）の中で、削除済みページ数が多い順にセグメントＮ／２個を見つける。ここで実際にみつかったセグメントの個数をＣ４とする。なお、削除済みページ数の多い順にセグメント上位N／２個を見つけるのは一例に過ぎず、Nよりも小さければ特に限定されるものではない。
ステップS753''.(通常モード)． [Ｃ２ > 1 かつ Ｃ３==0の場合] S751で見つかったセグメント（Ｃ２）の中で、削除済みページ数が所定値Ｌより大きくかつ削除済みページ数が多い上位Ｎ／２個を見つける。ここで実際にみつかったセグメントの個数をＣ４とする。
ステップS754. Ｃ４ > １の場合、S753またはS753"で見つかったセグメント（Ｃ４）の中で、有効ページ数の少ない順にセグメントＮ／４個を見つける。ここで実際に見つかったセグメントの個数をＣ５とする。なお、有効ページ数の少ないセグメントを選択するのは、有効ページ数の少ないセグメントでは、ＧＣ処理が高速になるからである。ここで、有効ページ数の少ない順にセグメントＮ／４個を見つけるのは一例に過ぎず、Ｎ／２個よりも小さければ特に限定されるものではない。
ステップS755. Ｃ５ > １の場合、S754で見つかったセグメント（Ｃ５）のうち任意の１個をＧＣ対象に決定する。
上記説明で用いた「強制モード」と「通常モード」について説明する。ＧＣ対象決定処理では、ＧＣの実行の契機(ＧＣモードと呼ぶ)によって、若干異なる処理がなされる。ＧＣモードは、通常モードと強制モードの二つがある。
ＧＣの実行時期は、通常、後述の「２３．ＧＣ開始条件」に従って自動的に決定される。これを通常モードと呼ぶ。
また、上位プログラムが、希望した時にＧＣを実行することも可能である。これを強制モードと呼ぶ。
【００３７】
なお、上記のWear leveling（ＧＣ対象決定）処理において、Ｃｎ（ｎ；２〜５）が１となった場合には、そのセグメントをＧＣ対象にして本処理を終了することができる。上記のWear leveling（ＧＣ対象決定）処理に関連する処理として、以下のような処理を行うのが適切である。
・ＧＣ実行前、削除済みページのみのセグメントが存在すれば1個消去する。
・ページ書き込み後、残りの未使用ページ数が所定値P以下の場合、ＧＣ処理を行う。
【００３８】
８．インクリメンタルガベージコレクション(ＩＧＣ)
上位モジュールよりＰＤＭ５に処理(読み出し、書き込みなど)が要求された時点で、以下の手順のうち、１つまたは複数を実行し、ガベージコレクションをバックグラウンドでインクリメンタルに行う。
（手順）
ステップS801. 消去中のセグメントが存在する場合、上位モジュールより要求された処理以外は行わない。(要求された処理を実行するために、フラッシュメモリには消去の一時停止機能が必要である。消去の一時停止機能がない場合、消去が完了するまで、要求処理の実行を遅延する。)
ステップS802. ガベージコレクション対象のセグメントがない場合、ガベージコレクション対象のセグメントをさがし（Wear leveling（ＧＣ対象決定）処理による）、そのセグメントが「ガベージコレクション対象」であることをRAMに格納する。
ステップS803. ガベージコレクション対象のセグメントがある場合、対象のセグメント内のいくつか(1-2個程度)のページを、ガベージコレクションの手順S602-S606に従って、新しいセグメントに移動する。
ステップS804. ガベージコレクション対象のセグメントの全部のページが削除済みになった場合、そのセグメントがガベージコレクション対象であることを解除し、対象のセグメントが「消去中」であることをRAMに格納し、ガベージコレクションの手順S608-S610に従って、セグメントの消去を開始する。
ステップS805. セグメントの消去が終了した場合、ガベージコレクションの手順S611に従って、セグメントを使用可能にし、そのセグメントが消去中であることを解除する。
【００３９】
ＩＧＣの状態遷移図を図５に示す。ＰＤＭ５が、ＬＦＭ３からメディアの使用開始の要求を受けると、ＰＤＭ５は初期化処理を行い、「通常実行中」状態（符号３０１）になる。なお、本システムの場合、メディアとは、フラッシュメモリを指す。「通常実行中」状態（符号３０２）では、ＬＦＭ３からの要求があるごとに、ＧＣすべきか判定し、ＧＣ対象セグメントを検索する。そして、ＧＣ対象セグメントが確定すると、ＬＦＭ３からの要求があるごとにページの移動を行う（「ＩＧＣ実行中」状態（符号３０３））。ページ移動が完了すると、ＬＦＭ３からの要求があるごとに消去の完了をチェックする（「セグメント消去中」状態（符号３０４））。初期状態以外の全状態において、ＬＦＭ３からメディアの使用終了要求を受けると、ＰＤＭ３は所定の後処理を行い、「解放状態」（符号３０５）となる。なお、「セグメント消去中」状態３０４で、消去の完了を待ってもよい。
【００４０】
上記のインクリメンタルガベージコレクションにより、ＯＳのタスク機能を使用せずに、ガベージコレクションを擬似的なバックグラウンド処理として行うことができる。また、消去の一時停止機能を持つメモリを使用した場合、ガベージコレクション実行時の長時間(数秒)の待ちが発生しない。なお、ＩＧＣが有効とされている場合でも、メモリの空き容量が少なくなった場合には、自動ＧＣ（「２２．自動ガベージコレクション」参照）を行う構成とすることが適切である。
【００４１】
９．ページ位置のキャッシング
物理ページの検索を高速化するため、以下の要領でページ位置のキャッシングを行う。まず、RAMに「ページ番号変換キャッシュ」(以下、PNTCと記す)を置く。PNTCは、複数の「ページ番号変換キャッシュエントリ」(以下、PNTCEと記す)より構成される。PNTCEは、次の情報を持つ: 論理ページ番号、物理ページ番号、連続するページ数（任意）、フラグ。PNTCE内の情報の意味を以下に示す。
・論理ページ番号は、エントリの対象とするページの論理ページ番号を示す。
・物理ページ番号は、エントリの対象とするページの物理ページ番号を示す。
・連続ページ数は、エントリの対象とするページから物理ページ番号が連続する、使用中の物理ページの数を示す。
・フラグはキャッシュ制御のために使用される。
なお、PNTCの全エントリは、システム起動時に無効な状態に初期化される。
【００４２】
ページ位置のキャッシング処理の手順を以下に示す。
（手順）
ステップS901. 物理ページの検索(上記のページ検索処理による)の際、初めに、PNTC中に、アクセス対象の論理ページ番号を含むPNTCEがあるか、PNTCEのフラグ、論理ページ番号、物理ページ番号、連続するページ数（任意）をもとに調べる。
ステップS902. PNTCEが存在する場合、対象の物理ページ番号を、PNTCEの物理ページ番号と論理ページ番号から求める。
ステップS902'. PNTCEが存在しない場合、上記のページ検索処理の手順で対象の物理ページ番号を検索し、検索結果の論理ページ番号、物理ページ番号を、PNTCに登録する。
ステップS902'-1. この時、検索結果の物理ページがPNTC中の他のエントリの領域に含まれるなら、そのエントリを更新する。
ステップS903. フラッシュメモリへの書き込み処理やガベージコレクションによって、PNTC中のエントリの状態が変わった場合には、PNTCを更新する。
なお、連続するページ数は任意であり、これを持たない構成も可能である。その場合、ステップS902'-1は不要である。
【００４３】
以上のようにページ位置のキャッシング処理を行うことのメリットとして、次のようなものが挙げられる。
・PNTCは、RAMに置かれ、エントリ数が少なくても良いため、物理ページの検索を高速に、かつ、少ないメモリ使用量で行うことができる。
・PNTCは、全論理ページと物理ページの対応付けを行うものではなく、補助的な情報であるため、使用中の電源断によって内容が失われても、システムがダメージを受けることはない。
【００４４】
１０．メディアへの書き込み・消去の一時停止
アプリケーション（ＡＰ）に対するレスポンスを向上させるため、ＰＤＭ５は、書き込み・消去中のメディアに対するアクセスを行う場合、その時実行している書き込み・消去の一時停止を行う。書き込み・消去の一時停止処理の手順を以下に示す。
（手順）
ステップS1001. アプリケーション(ＡＰ)がＰＤＭ５に対して、メディア(物理ページ)へのアクセス(読み出し、書き込み)を要求する。
ステップS1002. ＰＤＭ５は、対象のページの含まれる物理メモリの状態をMTDM７から取得する。
ステップS1003. メモリが消去中の場合で、メモリが消去の一時中止機能を持ち、アプリケーションが要求するアクセスが、消去中断中に実行可能な場合、ＰＤＭ５は、メモリに対して、消去の一時中止を要求する。
ステップS1004. ＰＤＭ５は、メモリに対して、アプリケーションが要求するアクセスを実行し、終了を待つ。
ステップS1005. ＰＤＭ５は、メモリに対して、書き込みの再開を要求する。
ステップS1003'. メモリが書き込み中の場合で、メモリが書き込みの一時中止機能を持ち、アプリケーションが要求するアクセスが、書き込み中断中に実行可能な場合、ＰＤＭ５は、メモリに対して、書き込みの一時中止を要求する。
ステップS1004'. ＰＤＭ５は、メモリに対して、アプリケーションが要求するアクセスを実行、終了を待つ。
ステップS1005'. ＰＤＭ５は、メモリに対して、書き込みの再開を要求する。
ステップS1003''. メモリが消去・書き込み中の場合で、メモリが消去・書き込みの一時中止機能を持たないか、アプリケーションが要求するアクセスが、消去・書き込み中断中に実行不可能な場合、ＰＤＭ５は、消去・書き込みの終了を待つ。
ステップS1004''. ＰＤＭ５は、メモリに対して、アプリケーションが要求するアクセスを実行し、終了を待つ。
【００４５】
１１．不良ページへの対処
物理ページに書き込んだ情報が正しく読み出せない場合または消去後のデータが初期値にならない場合、そのページを「不良ページ」とする。不良ページの検出は、ページにデータを書き込んだ後、書き込んだデータを読み出し、比較して行う。書き込み時に不良ページを検出した場合、そのページの状態を「不良」にし、新たな物理ページを割り当てて書き込みを行う。以後、ＰＤＭ５において、不良ページは、使用されることはない。
【００４６】
ページの状態の格納部分が不良の場合、次のように対処することで、そのページが不良ページであることを示す。なお、以下の説明において、「bビット」は、それが０の時、そのページが不良であることを示すビットを指す。
・bビットが１にならない(消去後０)場合、そのまま不良ページであることが示される。
・bビットが０にならない(０を書いても１のまま)場合、次のようにして不良ページを示す。
a. マジックコードを異常な値にする。
b. 物理フォーマットの種類を、セグメントまたはセグメント内の他のページと異なる値にする。
c. エラー検出データ(領域が存在する場合)を異常な値にする。
上記説明で用いた「マジックコード」と「エラー検出データ」について説明する。
マジックコードは、領域の種別を示す、数バイト程度のデータであり、領域内の特定の位置に特定の値で格納される（図３、および上記「１．フラッシュメモリの構造化」における図３関連の説明を参照のこと）。領域のマジックコードの存在する位置のデータが、本来のマジックコードの値と等しいかを判定することで、その領域が想定した領域であることを確認することができる。(この際、短いマジックコードでは、本来の領域でないにもかかわらずその領域とみなす誤判定が生じ、長いマジックコードでは、比較のための演算量が増える。)
エラー検出データは、ある領域に格納されたデータブロックに対して特定の演算を行って算出されるデータであり、そのデータブロックの正当性を判定するために用いる。例えば、パリティ、チェックサム、CRC、ECCが挙げられる。(エラー検出データの算出処理を簡単なものにすると、誤ったデータにも関わらず正当なデータとみなす誤判定が生じるため信頼性が低下し、複雑な処理にすると、判定精度や信頼性は向上するが処理速度が低下する。)
【００４７】
１２． 不良セグメントへの対処
セグメント内のほとんどのページが不良になったセグメント、消去に失敗したセグメントを「不良セグメント」とする。ＰＤＭ５において、不良セグメントは、消去・使用されることはない。セグメント情報格納領域が不良の場合、セグメント情報は、次の領域(セグメント内のオフセットが、セグメント情報のサイズから始まる領域)に格納される。ただし、次の領域も不良の場合、次のように対処することで、そのセグメントが不良セグメントであることを示す。(「bビット」は、それが０の時、そのセグメントが不良であることを示すビットを指す)
【００４８】
・bビットが１にならない(消去後０)場合、そのまま不良セグメントであることが示される。
・bビットが０にならない(０を書いても１のまま)場合、次のようにして不良セグメントを示す。
a. マジックコードを異常な値にする。
b. 消去回数を特別な値（例：全て１）にする。
c. 物理フォーマットの種類を、他のセグメントまたはセグメント内のページと異なる値にする。
d. エラー検出データ(領域が存在する場合)を異常な値にする。
【００４９】
１３． 書き込みデータのフラッシュメモリとアプリケーションへの適応化
ＰＤＭ５は、アプリケーションがフラッシュメモリに書き込むデータの性質が、特定の場合(例: ０が多い、１が多い)、データの０を１に、あるいは１を０に反転させてフラッシュメモリに書き込む。具体的には、以下の手順によって行われる。
（手順）
ステップS1301. アプリケーションは、自分の書き込むデータに、０が多いか、１が多いか判断する。
ステップS1302. ０が多い場合かつ、消去後のデータが全て１になるタイプのフラッシュメモリの場合、アプリケーションは、ＰＤＭ５の初期化時に、データ反転を行うように指示する。
ステップS1302'. １が多い場合かつ、消去後のデータが全て０になるタイプのフラッシュメモリの場合、アプリケーションは、ＰＤＭ５の初期化時に、データ反転を行うように指示する。
ステップS1303. ＰＤＭ５は、データをフラッシュメモリに書き込む際、データ反転を行うように指示されている場合には、書き込むデータの各ビットを反転させる。
ステップS1304. ＰＤＭ５は、データをフラッシュメモリから読み出す際、データ反転を行うように指示されている場合には、読み出したデータの各ビットを反転させる。
【００５０】
１４．書き込みデータのページごとのフラッシュメモリへの適応化
アプリケーションがフラッシュメモリに書き込むページのデータの性質が、特定の場合(例: ０が多い、１が多い)、ページデータの０を１に、あるいは１を０に反転させてフラッシュメモリに書き込む。本機能を実現するための手順を、「新規ページ書き込み」、「ページの読み出し」、「ページの上書き」に分けて説明する。
【００５１】
「新規ページ書き込み」の場合、以下の手順を実行する。
ステップS1401. ＰＤＭ５は、ページの最初の書き込みの際、そのページのデータの特徴(０が多いか、１が多いか)を調べる。
ステップS1402. ０が多い場合かつ、消去後のデータが全て１になるタイプのフラッシュメモリの場合、ＰＤＭ５は、そのページのデータ反転を行う。
ステップS1402'. １が多い場合かつ、消去後のデータが全て０になるタイプのフラッシュメモリの場合、ＰＤＭ５は、そのページのデータ反転を行う。
ステップS1403. ＰＤＭ５は、ページデータをフラッシュメモリに書き込む。その際、データ反転を行ったかどうかの情報をページ情報の「反転フラグ」に記録する。
【００５２】
「ページの読み出し」の場合、以下の手順を実行する。
ステップS1431. ＰＤＭ５は、ページを読み出す際、ページ情報の「反転フラグ」に、データ反転を行ったことが示されている場合には、読み出したページのページデータの各ビットを反転させる。
【００５３】
「ページの上書き」の場合、以下の手順を実行する。
ステップS1451. ＰＤＭ５は、ページの上書きの際、元のページの反転フラグを調べる。
ステップS1452. 反転フラグに従って、上書きするページのデータが元のページに上書き可能か調べる。元のページの反転フラグが有効の場合、上書きするデータをそれに合わせて反転させて判定する。
ステップS1453. データが上書き可能なら上書きする。
ステップS1453'. データが上書き不可能なら、上記「ページの新規書き込み」の処理を行う。
ここで、上書き可能であるか否かの判定はフラッシュメモリのタイプに依存し、例えば、上書きにより元のページのビットが、１から０の方向にしか変化しない場合上書き可能であるとする。この場合、元のページのデータ＝０ｘ６７で、書き込むデータ＝０ｘ０４であれば上書き可能と判定される。
【００５４】
１５．メディアの物理フォーマット処理
ＰＤＭ５は、次の手順でメディアを物理フォーマットし、そのメディアをアクセスできるようにする。
（手順）
ステップS1500. アプリケーションは、メディアのセグメントサイズ、ページサイズ、フォーマットの種類を決定し、ＰＤＭ５に物理フォーマットを要求する。
ステップS1501. メディア内の全セグメントに対し、次のS1502-S1504を実行する。
ステップS1502. セグメントに含まれる全消去ブロックを消去する。
ステップS1503. そのセグメントのセグメント情報を書き込む。
ステップS1504. そのセグメントのセグメント情報が正しく書き込めたことを確認する。
ステップS1505. セグメント情報の書き込みに失敗した場合、不良セグメントの処理(「１２．不良セグメントへの対処」参照)を行う。
【００５５】
１６．メディアの論理フォーマット処理
ＬＦＭ３は、メディアを論理フォーマットし、そのメディアをアクセスできるようにする。論理フォーマットの手順はＬＦＭ３に依存するが、ここでは、FATファイルシステムの論理フォーマット処理と、ＤＯＳパーティションの作成処理について説明する。
【００５６】
FATファイルシステムの論理フォーマット処理について説明する。
ＬＦＭ３は、以下の手順で、メディアを論理フォーマットする。
（手順）
ステップS1600. メディアの全容量、セクタサイズ、クラスタサイズ、FAT仕様(FAT12/FAT16/FAT32, VFAT)、FATの数、DOSパーティション作成の有無、他を決定する。
ステップS1601. メディアが物理フォーマットされていることを確認する。
ステップS1602. メディアの全セクタが読めるか確認する。
ステップS1603. メディアにDOSパーティションを作成する。
ステップS1604. メディアにブートセクタ(BPB)を作成する。
ステップS1605. メディアにバックアップブートセクタを作成する。(FAT32のみ)
ステップS1606. メディアにファイルシステム情報を記録する。(FAT32のみ)
ステップS1607. メディアにFATを作成する。
ステップS1608. メディアにルートディレクトリを作成する。
ステップS1609. メディアにラベルを記録する。
ステップS1610. メディアにブートプログラムを記録する（任意）。
【００５７】
DOSパーティションの作成処理について説明する。ＬＦＭ３は、次の手順でDOSパーティションの作成を行う。
（手順）
ステップS1650. パーティション情報(パーティション番号、パーティションタイプ、パーティション開始セクタ番号、パーティションサイズ、他)を決定する。
ステップS1651. メディアが物理フォーマットされていることを確認する。
ステップS1652. 最初の論理セクタにパーティションテーブルが存在するかを確認する。
ステップS1653. パーティションテーブルが存在する場合、指定のパーティション情報が、メディア情報および既存のパーティションと矛盾しないか確認する。
ステップS1653'. パーティションテーブルが存在しない場合、最初の論理セクタにパーティションテーブルを作成する。
ステップS1654. パーティション情報をパーティションテーブルに書き込む。
【００５８】
１７．メディアのロック・ロック解除
ＰＤＭ５は、内部に各メディアのロック情報を保持し、下記の処理を行うことができる。
・アプリケーションからメディアのロックを要求された場合、ＰＤＭ５はロック情報を設定する。
・メディアが既にロック済みの場合、エラーを返す。
・ロックの種類は、例えば、GC、書き込み、消去の3種類とする。
【００５９】
１８．ページ書き込み中の中断からの回復
ページの書き込みが中断された場合、次回のシステム起動時に、次の手順で回復処理を行う。
（手順）
ステッフ゜S1801. 全ページ中で、状態が「有効」で「更新中フラグ」の有効なページ(削除中ページ)について以下を行う。
ステッフ゜S1802. 削除中ページと同じ論理ページ番号を持ち、「更新中フラグ」の無効なページ(上書きしたページ)を探す。
ステッフ゜S1803. 上書きしたページが存在しない場合、何も行わない。
ステッフ゜S1803'. 上書きしたページが存在する場合、削除中ページを削除する。
【００６０】
１９．物理フォーマット・消去中の中断からの回復
セグメントの物理フォーマット・消去が中断された場合、次回のシステム起動時に、次の手順で回復処理を行う。
（手順）
ステッフ゜S1901. 全セグメント中で、状態が「削除済み」か、セグメントヘッダが不正なセグメントを探す。
ステッフ゜S1902. そのセグメントが消去されているか調べる。
ステッフ゜S1903. 消去されていない場合、そのセグメントを消去し、物理フォーマットする。
【００６１】
２０． 物理メモリフルでのデッドロックの回避
物理メモリ（フラッシュメモリ）がフルになることで、以後「何もできない」状態になるのを回避する必要がある。また、ＬＦＭ３から使用する場合、「FATファイルシステムの示す容量」を全部使用できる必要がある。少なくとも、「ファイル削除」は常に可能でなければならない。デッドロックの回避は、ＰＤＭ５が、以下に示す条件で、通常状態、自動GC(または、インクリメンタルGC)状態、書き込み不可状態への移行を行うことによって実現することができる。
【００６２】
A.自動GCなし状態 (通常状態)：空きページ数が予約ページ数以上、かつ、削除済みページの割合が所定値r1未満 (例えばr1= 0.2 〜 0.5程度)
この状態で、書き込み、読み出し、ページ削除、ＧＣ可能とする。
【００６３】
B.自動GC状態：空きページ数が予約ページ数以上、かつ、削除済みページの割合が所定値r1以上
この状態で、書き込み、読み出し、ページ削除、GC可能とする。ただし、書き込みの前にＧＣが行われるものとする。
【００６４】
C.書き込み不可状態 : 空きページ数が予約ページ数未満
この状態で、書き込み不可 (上位には「メディアフル」エラーを返す)、読み出し、ページ削除、ＧＣが可能とする。
【００６５】
２１．ページ割り当てマップ（PAM）
論理ページ番号(lpn)からのページ検索の際、対象のlpnに対応するページの検索には時間がかかる。特に、上記のページ検索処理によれば、ページが存在しない場合には、すべてのページヘッダ（ページ管理情報）を検索することになるので、時間がかかる場合がある。PAMは、ページ検索の際、ページが存在するかどうかの判定を高速化するためのビットマップである。
以下に、PAMの仕様を示す。
・ＰＤＭ５における１ページは、PAMの１エントリ(１ビット)に相当する。
・ページが存在するページのエントリの値が１に、存在しないページのエントリの値は０に(あるいはその逆に)設定される。
・PAMはRAMに格納される。
【００６６】
図６にPAMの模式図を示す。図６に示すように、論理ページ番号０がエントリ４０１に、論理ページ番号７がエントリ４０７というように、論理ページを各エントリに対応させる。図６のPAMを参照することで、論理ページ番号０は存在し、論理ページ７は存在しないことを知り、不必要な検索を省いてページ検索を高速化することができる。
【００６７】
PAMに関するＰＤＭ５の動作は以下のようなものである。
・「PAMの初期化」：ＰＤＭ５は、起動時に物理メモリ中の全ページを検索し、PAMの各エントリを各ページの状態に初期化する。
・「PAMエントリの検索」：lpnに対応するPAMのエントリの値を調べる。
・「PAMエントリのセット」：lpnに対応するPAMのエントリの値を１にする。
・「PAMエントリのリセット」：lpnに対応するPAMのエントリの値を０にする。
【００６８】
以下に、PAMを使用する場合の、ページ書き込み、ページ読み出し、ページ削除、セグメントのフォーマット処理ついての手順を示す。
[ページ書き込み]
ＰＤＭ５は、次に示す手順でページ書き込み処理を行う。
（手順）
ステップS2101. 対象のlpnでPAMを検索し、そのページが存在するかを調べる。
ステップS2102. 存在する場合、ページの上書き処理を行う。
ステップS2102'. 存在しない場合、新規ページ書き込み処理を行い、そのlpnに対応するPAMエントリをセットする。
[ページ読み出し]
ＰＤＭ５は、次に示す手順でページ読み出し処理を行う。
（手順）
ステップS2121. 対象のlpnでPAMを検索し、そのページが存在するかを調べる。
ステップS2122. 存在する場合、ページの読み出し処理を行う。
ステップS2122'. 存在しない場合、ダミーデータの読み出し処理を行う。
[ページ削除]
ＰＤＭ５は、次に示す手順でページ削除処理を行う。
（手順）
ステップS2141. 対象のlpnでPAMを検索し、そのページが存在するかを調べる。
ステップS2142. 存在する場合、ページの削除処理を行う。そのlpnに対応するPAMエントリをリセットする。
ステップS2142'. 存在しない場合、エラーとする。
[セグメントのフォーマット]
ＰＤＭ５は、次に示す手順でセグメントのフォーマットを行う。
（手順）
ステップS2161. そのセグメント中の全有効ページに対して、次のS2162を行う。
ステップS2162. 有効ページのlpnに対応するPAMエントリをリセットする。
【００６９】
ＰＤＭ５において、PAMを用いることのメリットは次のように説明することができる。すなわち、ＰＤＭ５は各ページに記録された論理ページ番号でページを管理し、ページ割り当てテーブル（論理ページ番号−物理ページ番号変換テーブル）を持たない。そのため、ある論理ページ番号のページを検索するには、最悪の場合、全ての有効ページを検索し、期待する論理ページ番号と一致するかを判定しなければならないので、検索速度が低下する可能性がある。特に、対象のページが存在しない場合には、必ずすべての有効なページを検索しなければ分からないので、処理速度が低速になる。上の問題を解決するのが、PAMとPNTCである。
【００７０】
PAMは、全論理ページ番号に対してそのページが存在するかどうかを示すマップである。したがって、PAMを使うことで、ある論理ページ番号のページを検索する際、そのページが存在しないことが即座に分かるので、処理速度が向上する。PNTCは、論理ページ番号とそのページに物理位置の変換情報のキャッシュである。PNTCにより、よく使用されるページの検索速度が向上する。なお、ＰＤＭ５は、前回検索したページの物理位置(ページ先頭の仮想アドレス)をRAMに記憶し、次回その位置から検索を開始することで、連続して書き込まれたページの検索速度を向上させる。
【００７１】
２２．自動ＧＣ
ＰＤＭ５は、物理メモリ領域内の空きページ数が少なくなった場合に、上位プログラムからのＧＣ要求がなくてもＧＣを実行する（自動ＧＣ）。ＰＤＭ５は、自動GCを行うかどうかは、以下の場合に行う。
・ページ書き込み処理の完了後
・ページ削除処理の完了後
【００７２】
２３．ＧＣ開始条件
ＰＤＭ５は、自動ＧＣ、強制ＧＣ（呼び出しプログラム(APなど)が明示的にGCの実行を要求した場合）、インクリメンタルＧＣを開始するかどうかを以下の開始条件にて決定する。開始条件について、それぞれ以下に説明する。
【００７３】
「自動ＧＣの開始条件」
ＰＤＭ５の実行中に、以下のaまたはbが成立した場合 (a, bの順に判定)
a. メモリ中の空きページ数 ≦ しきい値1
(しきい値1の例: １セグメント中のページ数 * 3/2)
b. メモリ中の削除済みページ数 ≧ しきい値2
(しきい値2の例: メモリ中の全ページ数 * 1/5)
【００７４】
「強制ＧＣの開始条件」
呼び出しプログラム(APなど)が明示的にＧＣの実行を要求した場合に、以下のaまたはbが成立した場合 (a, bの順に判定)
a. メモリ中の空きページ数 ≦ しきい値3
(しきい値3の例: メモリ中の全ページ数 * 1/2)
b. メモリ中の削除済みページ数 ≧ しきい値2
(しきい値2の例: メモリ中の全ページ数 * 1/5)
【００７５】
「インクリメンタルＧＣの開始条件」
呼び出しプログラム(APなど)が、ＰＤＭ５に対して処理要求を行うごとに、以下のa, b, cのいずれかが成立した場合 (a, b, cの順に判定)
a. 上記「自動ＧＣの開始条件」の条件
b. 処理要求の回数が一定値の倍数に達し、かつ、上記「強制ＧＣの開始条件」の条件
c. 処理要求の回数が一定値の倍数に達し、かつ、以下のc.1またはc.2が成立した場合 (c.1, c.2の順に判定)
c.1 メモリ中の空きページ数 ≦ しきい値4
(しきい値4の例: メモリ中の全ページ数 * 1/2)
c.2 メモリ中の削除済みページ数 ≧ しきい値2
(しきい値2の例: メモリ中の全ページ数 * 1/5)
なお、ＰＤＭ５は、ページの削除後、そのセグメントのすべてのページが「削除済み」になった場合、そのセグメントのフォーマットを行う。
【００７６】
２４．書き込みデータの適応化
上述の「１３．書き込みデータのフラッシュメモリとアプリケーションへの適応化」、「１４．書き込みデータのページごとのフラッシュメモリへの適応化」にて示した適応化に代えて（または同時に）、ＰＤＭ５は、次のような書き込みデータの適応化を行うことができる。
「新規ページの書き込み時」の手順
ステップS2401. 書き込むデータが、すべてフラッシュメモリの消去後の値(例: 0xff)であるかを調べる。
ステップS2402. S2401がyesの場合、ページデータの書き込みを行わない。
「既存ページの書き込み時」の手順
ステップS2451. 書き込み対象のページデータを読み込む。
ステップS2452. 書き込むデータが、すべて書き込み対象のページデータと同じであるかを調べる。
ステップS2453. S2452がyesの場合、ページデータの書き込みを行わない。
ステップS2452'. 書き込むデータが、すべて書き込み対象のページデータに上書き可能(例: 元= 0x67 -> 新= 0x04)かを調べる。
ステップS2453'. S2452'がyesの場合、ページの新規割り当てや置換を行わず、同じページに上書きする。
以上の、書き込みデータの適応化によるメリットとして次のようなものが挙げられる。
・書き込み済みのデータを書き込まないことで、書き込みを高速化する。
・既存のページにデータを書き込む際、データが上書き可能なら上書きすることで、書き込みを高速化する。
【００７７】
２５．最終ページ割り当て位置記憶
ＰＤＭ５は、上記のWear Levelingなどの新規ページ割り当て処理で割り当てたページの先頭の仮想アドレス（物理ページ番号に相当）をRAMに記憶しておく。そして、次回の新規ページ割り当て処理で、例えば、記憶しておいたページ位置の次の位置から検索を行うことで（ステッフ゜S700参照）、ページ割り当ての高速化を行う。
【００７８】
２６．最終検索ページ位置記憶
ＰＤＭ５は、RAM内に、ページ検索処理で最後に見つかったページの先頭アドレスを格納する領域（lastFoundMemAddr）を確保する。この領域が「無効なアドレス」の場合、その内容が無効であることを示す。
ページの検索時、以下の手順で示す処理を行う。
手順
S2601. lastFoundMemAddrの内容が有効な場合、ページの検索をlastFoundMemAddrから開始する。
S2061'. lastFoundMemAddrの内容が無効な場合、通常の方法でページの検索を行う。
以上の処理により、複数のページが連続して書き込まれている場合、2番目以降のページ検索が非常に高速になる。
【００７９】
２７．ページデータサイズの自動判定
ＰＤＭ５は、以下の手順によって、物理メモリ内のページデータサイズの自動判定を行う。
（手順）
ステップS2701. 物理メモリのフォーマット時に、内容の任意な１ページ（Signature page）を書き込んでおく。Signature pageは、ページ情報は有効であるが、ページデータは任意である。
ステップS2702. 次回以降起動時に、物理メモリ内より、任意の有効な1ページを検索し、そのページ情報より、ページデータサイズを取得する。仮に、ユーザ(アプリケーションプログラム)がメモリに何も書き込んでいない場合でも、Signature pageだけは存在するため、そのページ情報からページデータサイズを取得することができる。
以上のページデータサイズの自動判定処理によって、フラッシュメモリの物理フォーマット(ページデータサイズなど)が分からない場合に、自動的に判定することができる。ページデータサイズをＰＤＭ５やアプリケーションプログラム内で固定値にする必要がなくなり、システムの柔軟性が高まる。
【００８０】
２８．物理フォーマットの自動判定
ＰＤＭ５は、以下の手順で、物理メモリのセグメント情報(物理フォーマット(Compact/Normal), セグメントサイズなど)を自動的に判定する。
（手順）
ステップS2801. 物理メモリのフォーマット後の起動時に、物理メモリ内より、任意の有効な１セグメントを検索し、そのセグメント情報より、物理フォーマットなどの情報を取得する。
以上の物理フォーマットの自動判定処理によって、上位モジュールが、フラッシュメモリの物理フォーマットを記憶する必要がなくなる。セグメントサイズをＰＤＭ５やアプリケーションプログラム内で固定値にする必要がなくなり、システムの柔軟性が高まる。なお、このことによって、ＰＤＭ５をメモリカード用に使う場合、メモリカードを挿すだけで物理フォーマットが分かることになる。
【００８１】
２９．ＰＤＭ５における仮想アドレス空間
ここで、ＰＤＭ５が用いる仮想アドレスについて説明する。実際のターゲットハードウェアに実装されたフラッシュメモリは、実際のアドレス(物理アドレス)でアクセスする必要がある。物理アドレス空間の仕様は多種多様であるため、ＰＤＭ５で直接、物理アドレス空間にアクセスを行うと、ＰＤＭ５本体がハードウェアに依存することになるため、使用するターゲットごとに何らかの変更・修正が必要になる。ＰＤＭ５は、それを解決するため、ＰＤＭ５本体では、フラッシュメモリを、０から始まる、連続したアドレスに存在するものとしてアクセスする。これが、ＰＤＭ５における仮想アドレス空間である。仮想アドレス空間から物理アドレス空間への変換は、メモリドライバ(MTDM７)にて行っている。よって、ＰＤＭ５を様々なターゲットで使用する場合、MTDM７をそのターゲットとメモリに合わせて作成・修正するだけでよい。なお、上述のように、ＰＤＭ５は内部的に、物理ページ番号を使用しているが、これは仮想アドレス空間でのページのアドレスに対応している。
【００８２】
図７は、論理ページとアドレス空間の関係を示している。上位モジュール（ＬＦＭ３）は、ＰＤＭ５に対して論理ページ番号を指定する（符号５１）。ＰＤＭ５は、上述のページ検索処理などにより指定された論理ページ番号の仮想アドレスを決定し、ＭＴＤＭ７に対して仮想アドレスを指定する（符号５３）。MTDM7は、仮想アドレスを物理アドレスに変換してフラッシュメモリをアドレス指定する（符号５５）。このように、ＰＤＭ５自体が、フラッシュメモリのアドレスを仮想的に処理しているため、仮想アドレスと物理アドレスの変換部分(MTDM７)を除けば、ハードウェアが変わってもＰＤＭ５および上位モジュールを全く変更する必要がない。
【００８３】
３０．メモリ待ち時間の自動判定
フラッシュメモリには、「トグルビット」と呼ばれる処理完了を示すフラグがあるものがある。MTDM７（またはＰＤＭ５）の機能として、ある単位時間(数十〜数百ms)に、そのトグルビットのチェックを何回できるかを測定する機能を設ける。これにより、そのシステムの実行速度の目安がわかる。トグルビットのチェックとは、フラッシュメモリに消去または書き込み要求を出した後、フラッシュメモリの同じアドレスを連続して読み出した場合に、特定のビットの値が同じかどうかを調べることである。
【００８４】
フラッシュメモリの消去や書き込みは、時として失敗することがあり、その場合、上のトグルビットを何度チェックしても同じ値にならない。その場合、待ちを止めるタイムアウトを適正に決める必要が生じる。ＯＳの時間管理機能によってタイムアウトを判定すると、オーバヘッドが大きくなる場合がある。逆に、「何回でタイムアウト」という決め打ち方式では、高速なシステムでは誤ってタイムアウトすることがある。それを解決するため、上で測定した、トグルビットのチェック速度とメモリのタイムアウト時間(メモリの仕様によって決まる)より、「何回チェックしたら、タイムアウトであるか」という値を計算し、書き込み・消去待ちの上限時間に使用する。起動時に、そのシステムがメモリ状態をチェックする速度を測定しておいて、実行時のメモリ書き込み・消去時の待ち時間の計算に用いるのが好ましい。
【００８５】
３１．上位モジュールのフラッシュメモリドライバへの特化
ＬＦＭ３のような論理ファイルシステムモジュールが、使用しているメディアがディスクエミュレーションのフラッシュメモリドライバ(ＰＤＭ５)と認識した場合、ファイル削除時に、そのファイルが使用していたセクタ（論理ページ）を削除するように、ドライバ（ＰＤＭ５）に要求する構成とする。なお、ＰＤＭ５は、上述のように、論理ページの削除要求に対して、対応する物理ページのページの状態を削除済みにすることで対処する。このような構成とすることによって、使用しなくなったページが、ＧＣ対象となるので、ＰＤＭ５におけるメモリの空き領域の把握が正確になる。新規ファイル書き込み時に、ページの上書きが起こらないので、書き込み速度が向上する。逆に、このような構成でない場合、上位の論理ファイルシステムモジュールがファイルを削除したとしても、ＰＤＭ５はそのことを認識することができず、次に上位の論理ファイルシステムモジュールがその領域（論理ページ）を使用する時に、ＰＤＭ５の書き込み処理においてページが上書きされることが初めてわかる。この場合、上記本実施形態の構成と比較して、上書き処理の速度の点で不利である。
【００８６】
３２．ＲＡＭによるフラッシュメモリのエミュレーション
ＰＤＭ５は、次に示すようなソフトウェア開発用途としての、ＲＡＭによるフラッシュメモリエミュレーションの機能を持つ。この機能は、ＰＤＭ５を様々なターゲットシステムに合わせたものとして、ソフトウェア開発を行う際に利用することができる。ＲＡＭエミュレーションの手順の例を下記に示す。
（手順）
ステップS3201. 少なくとも想定するフラッシュメモリの容量分、RAMを確保する。
ステップS3202. データ書き込み時、ビットごとに、書き換え可能性の判定を行う。(０から１への変化は不可とする)
ステップS3203. データ読み出し時には、指定されたアドレスから、指定された分だけ読み出す。
ステップS3203. データ消去時には、想定するフラッシュメモリの消去ブロック単位で、データを想定するメモリの初期値(例: 0xff)にする。
【００８７】
以上説明した、本発明の実施形態としてのＰＤＭ５の各機能は、本発明を実現する上でその全てが必ずしも必要ではない。省略や、他の機能での置換を行うことによって、様々な変形を行うことが可能である。ＰＤＭ５およびこれを用いたファイルシステムは、フラッシュメモリのみでなく、書き換えの方向性を持つ他の種類のメモリ素子など、様々なメモリ素子を外部記憶装置として利用する場合にも適用することができる。
【００８８】
本発明の範囲には、以上で説明したメモリ制御方法を実現する、装置やソフトウェアも含まれる。
【００８９】
以上のように本発明によれば、フラッシュメモリを外部記憶装置として効率的に用いることができるとともに、フラッシュメモリの各消去ブロックの消去回数を高い精度で平均化することもできる。
【図面の簡単な説明】
【００９０】
【図１】本発明の実施形態としての物理記憶デバイスシステムモジュールの位置付けを表す図である。
【図２】本発明の実施形態としての物理記憶デバイスシステムモジュールにおけるフラッシュメモリの構造化を示す図である。
【図３】セグメント管理情報の詳細な構成の一例を示す図である。
【図４】ページの詳細な構成の一例を示す図である。
【図５】本発明の実施形態におけるインクリメンタルガベージコレクションの状態遷移図である。
【図６】本発明の実施形態におけるページ割当てマップの模式図である。
【図７】本発明の実施形態における論理ページとアドレス空間の対応を示す図である。
【符号の説明】
【００９１】
１  アプリケーションプログラム（ＡＰ）
３  論理ファイルシステムモジュール（ＬＦＭ）
５  物理記憶デバイスシステムモジュール（ＰＤＭ）
７  ＭＴＤＭ
２０  セグメント
２１  セグメント管理情報
２２，３２  マジックコード
３０  ページ
３１  ページ管理情報
４０  消去ブロック
５０  フラシュメモリのメモリ領域
【図１】
2006099797.tif 000003
【図２】
2006099797.tif 000004
【図３】
2006099797.tif 000005
【図４】
2006099797.tif 000006
【図５】
2006099797.tif 000007
【図６】
2006099797.tif 000008
【図７】
2006099797.tif 000009