(57)【要約】【課題】フラッシュメモリ（ＦＭ）を構成する複数個の物理ブロック（ＰＢ）における極端な消去回数（ＥＣ）の偏りと、ＦＭ全体としてのＥＣの増加を抑制する。【解決手段】ＰＢのＥＣの閾値を基に定義されたＰＢのグループ（ＧＰ）毎に、空きＰＢの検索用のテーブルＡと、最も先に論理ブロック（ＬＢ）に割り当てられたＰＢ（最先ＰＢ）の検索用のテーブルＢがある。メモリコントローラは、ＰＢをアクセス対象のＬＢに割り当てるときに、ＥＣの少ないＰＢが属する側のＧＰ（下位側ＧＰ）に対応するテーブルＡの方を優先的に用いて空きＰＢの検索し、検出された空きＰＢが属するＧＰよりも下位側ＧＰに属するＰＢが存在するときには、その空きＰＢが属するＧＰよりも下位側ＧＰに属する最先ＰＢをその下位側ＧＰに対応するテーブルＢを用いて検索し、検出された最先ＰＢ内のデータを上記検出された空きＰＢに転送し、その最先ＰＢをアクセス対象のＬＢに割り当てる。【選択図】図３
2010182266.tif 000002
【特許請求の範囲】
【請求項１】
ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するメモリコントローラであって、
フラッシュメモリを構成するそれぞれの物理ブロックの消去回数を管理する消去回数管理手段と、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、フラッシュメモリを構成する物理ブロックを前記論理ブロックに割り当てるブロック管理手段と、
有効なデータが格納されていない物理ブロックである空きブロックを検索するための空きブロックテーブルを、物理ブロックの消去回数について設けられた１又は複数の閾値を基に定義された物理ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索手段と、
前記論理ブロックに割り当てられている物理ブロックのうちで最も先に前記論理ブロックに割り当てられた物理ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索手段と、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている物理ブロックにホストシステムから与えられるデータを格納するデータ格納手段と、
前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送するデータ転送手段とを備え、
前記アクセス指示に応答して前記ブロック管理手段により物理ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索手段は消去回数の少ない物理ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方を優先的に用いて前記空きブロックの検索を行い、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在しないときに、前記ブロック管理手段は前記空きブロック検索手段により検出された前記空きブロックを前記論理ブロックに割り当て、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在するときに、前記最先ブロック検索手段は前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックを検索し、前記データ転送手段は前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送し、前記ブロック管理手段は前記最先ブロック検索手段により検出された前記最先ブロックを前記論理ブロックに割り当てる、
メモリコントローラ。
【請求項２】
ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するメモリコントローラであって、
フラッシュメモリを構成する物理ブロックを複数個集めた仮想ブロックを複数個形成する仮想ブロック形成手段と、
前記仮想ブロック単位で消去回数を管理する消去回数管理手段と、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、前記仮想ブロックを前記論理ブロックに割り当てるブロック管理手段と、
有効なデータが格納されていない前記仮想ブロックである空きブロックを検索するための空きブロックテーブルを、前記仮想ブロックの消去回数について設けられた１又は複数の閾値を基に定義された前記仮想ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索手段と、
前記論理ブロックに割り当てられている前記仮想ブロックのうちで最も先に前記論理ブロックに割り当てられた前記仮想ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索手段と、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている前記仮想ブロックにホストシステムから与えられるデータを格納するデータ格納手段と、
前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送するデータ転送手段とを備え、
前記アクセス指示に応答して前記ブロック管理手段により前記仮想ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索手段は消去回数の少ない前記仮想ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方を優先的に用いて前記空きブロックの検索を行い、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在しないときに、前記ブロック管理手段は前記空きブロック検索手段により検出された前記空きブロックを前記論理ブロックに割り当て、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在するときに、前記最先ブロック検索手段は前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックを検索し、前記データ転送手段は前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送し、前記ブロック管理手段は前記最先ブロック検索手段により検出された前記最先ブロックを前記論理ブロックに割り当てる、
メモリコントローラ。
【請求項３】
請求項１又は２に記載のメモリコントローラと、このメモリコントローラにより制御される複数個のフラッシュメモリを備えるフラッシュメモリシステム。
【請求項４】
ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するフラッシュメモリの制御方法であって、
フラッシュメモリを構成するそれぞれの物理ブロックの消去回数を管理する消去回数管理ステップと、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、フラッシュメモリを構成する物理ブロックを前記論理ブロックに割り当てるブロック管理ステップと、
有効なデータが格納されていない物理ブロックである空きブロックを検索するための空きブロックテーブルを、物理ブロックの消去回数について設けられた１又は複数の閾値を基に定義された物理ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索ステップと、
前記論理ブロックに割り当てられている物理ブロックのうちで最も先に前記論理ブロックに割り当てられた物理ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索ステップと、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている物理ブロックにホストシステムから与えられるデータを格納するデータ格納ステップと、
前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータを前記空きブロック検索ステップにより検出された前記空きブロックに転送するデータ転送ステップとを備え、
前記アクセス指示に応答して前記ブロック管理ステップにより物理ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索ステップでは消去回数の少ない物理ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方が優先的に用いられる前記空きブロックの検索が行われ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在しないときに、前記ブロック管理ステップでは前記空きブロック検索ステップにより検出された前記空きブロックが前記論理ブロックに割り当てられ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在するときに、前記最先ブロック検索ステップでは前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックが検索され、前記データ転送ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータが前記空きブロック検索ステップにより検出された前記空きブロックに転送され、前記ブロック管理ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックが前記論理ブロックに割り当てられるフラッシュメモリの制御方法。
【請求項５】
ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するフラッシュメモリの制御方法であって、
フラッシュメモリを構成する物理ブロックを複数個集めた仮想ブロックを複数個形成する仮想ブロック形成ステップと
前記仮想ブロック単位で消去回数を管理する消去回数管理ステップと、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、前記仮想ブロックを前記論理ブロックに割り当てるブロック管理ステップと、
有効なデータが格納されていない前記仮想ブロックである空きブロックを検索するための空きブロックテーブルを、前記仮想ブロックの消去回数について設けられた１又は複数の閾値を基に定義された前記仮想ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索ステップと、
前記論理ブロックに割り当てられている前記仮想ブロックのうちで最も先に前記論理ブロックに割り当てられた前記仮想ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索ステップと、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている前記仮想ブロックにホストシステムから与えられるデータを格納するデータ格納ステップと、
前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータを前記空きブロック検索ステップにより検出された前記空きブロックに転送するデータ転送ステップとを備え、
前記アクセス指示に応答して前記ブロック管理ステップにより前記仮想ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索ステップでは消去回数の少ない前記仮想ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方が優先的に用いられる前記空きブロックの検索が行われ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在しないときに、前記ブロック管理ステップでは前記空きブロック検索ステップにより検出された前記空きブロックが前記論理ブロックに割り当てられ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在する場合、前記最先ブロック検索ステップでは前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックが検索され、前記データ転送ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータが前記空きブロック検索ステップにより検出された前記空きブロックに転送され、前記ブロック管理ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックが前記論理ブロックに割り当てられるフラッシュメモリの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリコントローラ及びメモリコントローラを備えるフラッシュメモリシステム、並びにフラッシュメモリの制御方法に関する。
【背景技術】
【０００２】
例えば、特許文献１に開示されているように、フラッシュメモリを用いたメモリシステムでは、フラッシュメモリを構成する複数個の物理ブロックにおいて消去回数に偏りが生じないようにウェアー・レベリング（Wear-leveling）制御が行われている。このウェアー・レベリング制御には、大きくは２つの方式がある。
【０００３】
１つは、書き換えが行われないデータが記憶されている物理ブロックを放置しておき、それ以外の物理ブロックの消去回数又は書き換え回数が平均化されるように制御するウェアー・レベリング制御（ダイナミック・ウェアー・レベリング（Dynamic-wear-leveling）制御方式又はパッシブ・ウェアー・レベリング（Passive-wear-leveling）制御方式と呼ばれている制御方式であり、以下、ダイナミック・ウェアー・レベリングと言う）である。もう一つは、書き換えが行われないデータが記憶されている物理ブロックを含めて、全ての物理ブロックの消去回数又は書き換え回数が平均化されるように制御するウェアー・レベリング制御（スタティック・ウェアー・レベリング（Static-wear-leveling）制御方式又はアクティブ・ウェアー・レベリング（Active-wear-leveling）制御方式と呼ばれている制御方式であり、以下、スタティック・ウェアー・レベリングと言う）である。
【０００４】
ここで、書き換えが行わないデータが記憶されている物理ブロックが少ない場合は、ダイナミック・ウェアー・レベリング制御方式が適している。しかし、書き換えが行われないデータが記憶されている物理ブロックが多い場合は、スタティック・ウェアー・レベリング制御方式が適している。従って、特許文献１には、メモリシステムに記憶されるデータの書き換え頻度に応じて（つまり、書き換えが行われないデータが記憶されている物理ブロックが多いか少ないかに応じて）、ダイナミック・ウェアー・レベリング制御方式、スタティック・ウェアー・レベリング制御方式又はこれらを組み合わせたウェアー・レベリング制御方式のうちのいずれかのウェアー・レベリング制御を行うことが記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１３３６８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述した特許文献１では、ウェアー・レベリング制御方式の選択や条件設定を、ユーザが行うようになっている。しかしながら、メモリシステムに記憶されるデータの書き換え頻度に応じて、適切なウェアー・レベリング制御方式を選択することは、必ずしも容易でない。
【０００７】
そして、ウェアー・レベリング制御方式の選択が適切でなかった場合、スタティック・ウェアー・レベリング制御方式を選択しなかったために消去回数が極端に少ない物理ブロックがウェアー・レベリング制御の対象にならずに放置されることや、スタティック・ウェアー・レベリング制御方式を選択したために物理ブロック間で不必要なデータ転送が行われることがある。また、スタティック・ウェアー・レベリング制御方式において、それぞれの物理ブロックの消去回数が平均的に増加していくように制御すれば、消去回数を平均化するためのデータ転送が増加し、その結果、フラッシュメモリ全体としての消去回数が増加してしまう。このような物理ブロック間でのデータ転送による消去回数の増加は、フラッシュメモリの劣化を加速する。
【０００８】
そこで、本発明は、フラッシュメモリを構成する複数個の物理ブロックにおける極端な消去回数の偏りと、フラッシュメモリ全体としての消去回数の増加を抑制することにより、フラッシュメモリの劣化速度を低減することができるメモリコントローラ、フラッシュメモリシステム、及びフラッシュメモリの制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の第１の観点に従うメモリコントローラは、ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するメモリコントローラであって、
フラッシュメモリを構成するそれぞれの物理ブロックの消去回数を管理する消去回数管理手段と、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、フラッシュメモリを構成する物理ブロックを前記論理ブロックに割り当てるブロック管理手段と、
有効なデータが格納されていない物理ブロックである空きブロックを検索するための空きブロックテーブルを、物理ブロックの消去回数について設けられた１又は複数の閾値を基に定義された物理ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索手段と、
前記論理ブロックに割り当てられている物理ブロックのうちで最も先に前記論理ブロックに割り当てられた物理ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索手段と、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている物理ブロックにホストシステムから与えられるデータを格納するデータ格納手段と、
前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送するデータ転送手段とを備え、
前記アクセス指示に応答して前記ブロック管理手段により物理ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索手段は消去回数の少ない物理ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方を優先的に用いて前記空きブロックの検索を行い、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在しないときに、前記ブロック管理手段は前記空きブロック検索手段により検出された前記空きブロックを前記論理ブロックに割り当て、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在するときに、前記最先ブロック検索手段は前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックを検索し、前記データ転送手段は前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送し、前記ブロック管理手段は前記最先ブロック検索手段により検出された前記最先ブロックを前記論理ブロックに割り当てる。
【００１０】
本発明の第２の観点に従うメモリコントローラは、ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するメモリコントローラであって、
フラッシュメモリを構成する物理ブロックを複数個集めた仮想ブロックを複数個形成する仮想ブロック形成手段と、
前記仮想ブロック単位で消去回数を管理する消去回数管理手段と、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、前記仮想ブロックを前記論理ブロックに割り当てるブロック管理手段と、
有効なデータが格納されていない前記仮想ブロックである空きブロックを検索するための空きブロックテーブルを、前記仮想ブロックの消去回数について設けられた１又は複数の閾値を基に定義された前記仮想ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索手段と、
前記論理ブロックに割り当てられている前記仮想ブロックのうちで最も先に前記論理ブロックに割り当てられた前記仮想ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索手段と、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている前記仮想ブロックにホストシステムから与えられるデータを格納するデータ格納手段と、
前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送するデータ転送手段とを備え、
前記アクセス指示に応答して前記ブロック管理手段により前記仮想ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索手段は消去回数の少ない前記仮想ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方を優先的に用いて前記空きブロックの検索を行い、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在しないときに、前記ブロック管理手段は前記空きブロック検索手段により検出された前記空きブロックを前記論理ブロックに割り当て、
前記空きブロック検索手段により検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在するときに、前記最先ブロック検索手段は前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックを検索し、前記データ転送手段は前記最先ブロック検索手段により検出された前記最先ブロックに格納されているデータを前記空きブロック検索手段により検出された前記空きブロックに転送し、前記ブロック管理手段は前記最先ブロック検索手段により検出された前記最先ブロックを前記論理ブロックに割り当てる。
【００１１】
本発明の第３の観点に従うフラッシュメモリシステムは、上記第１又は第２の観点に従うメモリコントローラと、このメモリコントローラにより制御される複数個のフラッシュメモリとを備える。
【００１２】
本発明の第４の観点に従う方法は、ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するフラッシュメモリの制御方法であって、
フラッシュメモリを構成するそれぞれの物理ブロックの消去回数を管理する消去回数管理ステップと、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、フラッシュメモリを構成する物理ブロックを前記論理ブロックに割り当てるブロック管理ステップと、
有効なデータが格納されていない物理ブロックである空きブロックを検索するための空きブロックテーブルを、物理ブロックの消去回数について設けられた１又は複数の閾値を基に定義された物理ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索ステップと、
前記論理ブロックに割り当てられている物理ブロックのうちで最も先に前記論理ブロックに割り当てられた物理ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索ステップと、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている物理ブロックにホストシステムから与えられるデータを格納するデータ格納ステップと、
前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータを前記空きブロック検索ステップにより検出された前記空きブロックに転送するデータ転送ステップとを備え、
前記アクセス指示に応答して前記ブロック管理ステップにより物理ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索ステップでは消去回数の少ない物理ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方が優先的に用いられる前記空きブロックの検索が行われ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在しないときに、前記ブロック管理ステップでは前記空きブロック検索ステップにより検出された前記空きブロックが前記論理ブロックに割り当てられ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する物理ブロックが存在するときに、前記最先ブロック検索ステップでは前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックが検索され、前記データ転送ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータが前記空きブロック検索ステップにより検出された前記空きブロックに転送され、前記ブロック管理ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックが前記論理ブロックに割り当てられる。
【００１３】
本発明の第５の観点に従う方法は、ホストシステムから与えられるアクセス指示に基づいて、物理ブロック単位で消去が行われるフラッシュメモリに対するアクセスを制御するフラッシュメモリの制御方法であって、
フラッシュメモリを構成する物理ブロックを複数個集めた仮想ブロックを複数個形成する仮想ブロック形成ステップと
前記仮想ブロック単位で消去回数を管理する消去回数管理ステップと、
前記アクセス指示として与えられる論理アドレスが割り当てられているセクタ単位の領域を複数個集めた複数セクタの領域を論理ブロックとして管理し、前記仮想ブロックを前記論理ブロックに割り当てるブロック管理ステップと、
有効なデータが格納されていない前記仮想ブロックである空きブロックを検索するための空きブロックテーブルを、前記仮想ブロックの消去回数について設けられた１又は複数の閾値を基に定義された前記仮想ブロックのグループ毎に有し、それぞれの前記空きブロックテーブルを用いてそれぞれの前記グループに属する前記空きブロックを検索する空きブロック検索ステップと、
前記論理ブロックに割り当てられている前記仮想ブロックのうちで最も先に前記論理ブロックに割り当てられた前記仮想ブロックである最先ブロックを検索するための最先ブロックテーブルを前記グループ毎に有し、それぞれの前記最先ブロックテーブルを用いてそれぞれの前記グループに属する前記最先ブロックを検索する最先ブロック検索ステップと、
前記アクセス指示に基づいてアクセス対象の領域が属する前記論理ブロックを特定し、特定した前記論理ブロックに割り当てられている前記仮想ブロックにホストシステムから与えられるデータを格納するデータ格納ステップと、
前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータを前記空きブロック検索ステップにより検出された前記空きブロックに転送するデータ転送ステップとを備え、
前記アクセス指示に応答して前記ブロック管理ステップにより前記仮想ブロックが前記論理ブロックに割り当てられるときに、前記空きブロック検索ステップでは消去回数の少ない前記仮想ブロックが属する側の前記グループである下位側の前記グループに対応する前記空きブロックテーブルの方が優先的に用いられる前記空きブロックの検索が行われ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在しないときに、前記ブロック管理ステップでは前記空きブロック検索ステップにより検出された前記空きブロックが前記論理ブロックに割り当てられ、
前記空きブロック検索ステップにより検出された前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記仮想ブロックが存在する場合、前記最先ブロック検索ステップでは前記空きブロックが属する前記グループよりも下位側の前記グループに属する前記最先ブロックが検索され、前記データ転送ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックに格納されているデータが前記空きブロック検索ステップにより検出された前記空きブロックに転送され、前記ブロック管理ステップでは前記最先ブロック検索ステップにより検出された前記最先ブロックが前記論理ブロックに割り当てられる。
【発明の効果】
【００１４】
本発明によれば、物理ブロックの消去回数について１又は複数の閾値が設けられ、消去回数がその閾値を越えた物理ブロックの消去回数が抑制されるような制御が行われる。その結果、フラッシュメモリを構成する複数個の物理ブロックにおける極端な消去回数の偏りが抑制されると共に、フラッシュメモリ全体としての消去回数の増加も抑制される。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態に係るフラッシュメモリシステムの概略構成を示すブロック図である。
【図２】論理ブロックと物理ブロックの対応関係を示す図である。
【図３】最先ブロックテーブルにおける優先順位管理を示す説明図である。
【図４】最先ブロックテーブルへの登録に関する説明図である。
【図５】空きブロックテーブルの構成を示す説明図である。
【図６】空きブロックテーブルへの登録に関する説明図である。
【図７】物理ブロックの消去回数の管理と先後管理のための優先順位管理に用いられるテーブルの説明図である。
【発明を実施するための最良の形態】
【００１６】
図１は、本実施の形態に係るフラッシュメモリシステム１を概略的に示すブロック図である。
【００１７】
図１に示すように、フラッシュメモリシステム１は、フラッシュメモリ２と、それを制御するメモリコントローラ３とで構成されている。
【００１８】
フラッシュメモリシステム１は、外部バス１３を介してホストシステム４と接続されている。ホストシステム４は、ホストシステム４の全体の動作を制御するためのＣＰＵ（Central Processing Unit）、フラッシュメモリシステム１との情報の授受を担うコンパニオンチップ等から構成されている。ホストシステム４は、例えば、文字、音声、あるいは画像情報等の種々の情報を処理するパーソナルコンピュータやデジタルスチルカメラをはじめとする各種情報処理装置であってもよい。
【００１９】
メモリコントローラ３は、図１に示すように、マイクロプロセッサ６と、ホストインターフェースブロック７と、ワークエリア８と、バッファ９と、フラッシュメモリインターフェースブロック１０と、ＥＣＣ（Error Correcting Code）ブロック１１と、ＲＯＭ（Read Only Memory）１２とから構成される。メモリコントローラ３は、内部バス１４を介してフラッシュメモリ２と接続されている。これら機能ブロックによって構成されるメモリコントローラ３は、一つの半導体チップ上に集積される。以下、各機能ブロックについて説明する。
【００２０】
ホストインターフェースブロック７は、ホストシステム４との間でデータ、アドレス情報、ステータス情報、外部コマンド等の授受を行う。外部コマンドとは、ホストシステム４がフラッシュメモリシステム１に対して処理の実行を指示するためのコマンドである。ホストシステム４よりフラッシュメモリシステム１に供給されるデータ等は、ホストインターフェースブロック７を介してフラッシュメモリシステム１の内部（例えば、バッファ９）に取り込まれる。また、フラッシュメモリシステム１からホストシステム４に供給されるデータ等は、ホストインターフェースブロック７を介してホストシステム４に供給される。
【００２１】
ホストインターフェースブロック７は、コマンドレジスタＲ１、セクタ数レジスタＲ２及びＬＢＡレジスタＲ３を備えている。コマンドレジスタＲ１、セクタ数レジスタＲ２及びＬＢＡレジスタＲ３には、ホストシステム４から与えられる情報が書き込まれる。コマンドレジスタＲ１には、書き込みコマンド、読み出しコマンド等の外部コマンドが書き込まれる。セクタ数レジスタＲ２には、アクセス対象領域のセクタ数が書き込まれる。ＬＢＡレジスタＲ３には、アクセス対象領域の先頭セクタのＬＢＡ（Logical Block Address）（後述）が書き込まれる。
【００２２】
ワークエリア８は、フラッシュメモリ２の制御に必要なデータを一時的に格納する作業領域であり、複数のＳＲＡＭ（Static Random Access Memory）セルによって構成されて
いる。ワークエリア８には、例えば、論理ブロックと物理ブロックとの対応関係を示したアドレス変換テーブル等が格納される。
【００２３】
バッファ９は、フラッシュメモリ２から読み出したデータを、ホストシステム４が受け取り可能な状態となるまで保持する。また、バッファ９は、フラッシュメモリ２に書き込むデータを、フラッシュメモリ２が書き込み可能な状態となるまで保持する。
【００２４】
フラッシュメモリインターフェースブロック１０は、内部バス１４を介して、フラッシュメモリ２との間でデータ、アドレス情報、ステータス情報、内部コマンド等の授受を行う。ここで、内部コマンドとは、メモリコントローラ３がフラッシュメモリ２に処理の実行を指示するためのコマンドであり、フラッシュメモリ２は、メモリコントローラ３から与えられる内部コマンドに従って動作する。
【００２５】
ＥＣＣブロック１１は、フラッシュメモリ２に書き込むデータに付加される誤り訂正符号（ＥＣＣ：Error Correcting Code）を生成するとともに、読み出したデータに付加されている誤り訂正符号に基づいて、読み出したデータに含まれる誤りを検出・訂正する。
【００２６】
ＲＯＭ１２は、マイクロプロセッサ６による処理の手順を定義するプログラムを格納する不揮発性の記憶素子である。例えば、アドレス変換テーブルの作成等の処理手順を定義するプログラムが格納されている。
【００２７】
マイクロプロセッサ６は、ＲＯＭ１２に記憶されているプログラムに従って、メモリコントローラ３の全体の動作を制御する。例えば、マイクロプロセッサ６は、ＲＯＭ１２から読み出した各種処理を定義したコマンドセットに基づいてフラッシュメモリインターフェースブロック１０に処理を実行させる。
【００２８】
フラッシュメモリ２は、ＮＡＮＤ型フラッシュメモリからなる。ＮＡＮＤ型フラッシュメモリは、レジスタと、複数のメモリセルが２次元的に配列されたメモリセルアレイを備えている。メモリセルアレイは、複数のメモリセル群と、ワード線とを備える。ここで、メモリセル群は、複数のメモリセルが直列に接続されたものである。各ワード線は、メモリセル群の特定のメモリセルを選択するためのものである。このワード線を介して選択されたメモリセルとレジスタとの間で、レジスタから選択されたメモリセルへのデータの書き込み又は選択されたメモリセルからレジスタへのデータの読み出しが行われる。
【００２９】
ＮＡＮＤ型フラッシュメモリでは、データ読み出し動作及びデータ書き込み動作はページ単位で行われ、データ消去動作はブロック（物理ブロック）単位で行われる。物理ブロックは、複数のページ（物理ページ）で構成される。例えば、１個の物理ページは、所定サイズ（例えば２０４８バイト）のユーザ領域と、所定サイズ（例えば６４バイト）の冗長領域とで構成され、１個の物理ブロックが、所定個数（例えば６４個）の物理ページで構成されている。ユーザ領域は、ホストシステム４から与えられるデータを記憶するための領域であり、通常、５１２バイト単位の記憶領域（以下、「論理セクタ領域」と言う）に分割して管理されている。冗長領域は、誤り訂正符号（ＥＣＣ：Error Correcting Code）、論理アドレス情報、ブロックステータス（フラグ）等の付加データを記憶するための領域である。
【００３０】
論理アドレス情報は、物理ブロックと論理ブロックの対応関係を判別するための情報である。ブロックステータス（フラグ）は、物理ブロックの良否を示すフラグである。尚、初期不良の物理ブロックについては、不良ブロック（正常にデータの書き込み等を行うことができない物理ブロック）であることを示すブロックステータス（フラグ）が製造メーカによって書き込まれている。また、この初期不良の物理ブロックを示すブロックステータス（フラグ）を、ユーザ領域に書き込んでいる製造メーカもある。
【００３１】
本実施の形態の書き込み処理では、ホストシステム４によって、コマンドレジスタＲ１に、書き込みコマンドを示すコマンドコードが書き込まれ、セクタ数レジスタＲ２に、書き込むデータのセクタ数が書き込まれ、ＬＢＡレジスタＲ３には、書き込みを開始する先頭データに対応するＬＢＡが書き込まれる。セクタ数レジスタＲ２及びＬＢＡレジスタＲ
３に書き込まれた情報に基づいて、アクセス対象の領域である論理アクセス領域が判別され、その論理アクセス領域が含まれる論理ブロックに対応する物理ブロックにホストシステム４から与えられるデータが書き込まれる。
【００３２】
セクタ数レジスタＲ２及びＬＢＡレジスタＲ３に書き込まれた情報に基づいて判別される論理アクセス領域が複数個の論理ブロックに跨っている場合は、論理アクセス領域が属する論理ブロック毎に領域を分割してデータの書き込み処理が行われる。例えば、論理アクセス領域が２個の論理ブロック（第１の論理ブロックと第２の論理ブロック）に跨っている場合は、第１の論理ブロックに対応する物理ブロックに対する書き込み処理と、第２の論理ブロックに対応する物理ブロックに対する書き込み処理とが行われる。第１の論理ブロックに属する論理アクセス領域に対して書き込むことが指示されたデータは、第１の論理ブロックに対応する物理ブロックに書き込まれる。第２の論理ブロックに属する論理アクセス領域に対して書き込むことが指示されたデータは、第２の論理ブロックに対応する物理ブロックに書き込まれる。
【００３３】
ホストシステム４側のアドレス空間は、セクタ（５１２バイト）単位で分割した領域（以下、「論理セクタ領域」と言う）に付けた通し番号であるＬＢＡ（Logical Block Address）で管理されている。又、複数個の論理セクタ領域で構成された論理ブロックが形成され、この論理ブロックに対して、１個又は複数個の物理ブロックが割り当てられる。
【００３４】
この論理ブロックと物理ブロックの対応関係は、ゾーン単位で管理されることが多い。具体的には、複数個の論理ブロックで１個の論理ゾーンが構成され、この論理ゾーン単位で論理ブロックと物理ブロックの対応関係を示すアドレス変換テーブルの作成処理や更新処理が行われる。
【００３５】
このアドレス変換テーブルの作成処理や更新処理は、通常、ワークエリア８上で行われる。アドレス変換テーブルは、一般に、起動時又はアクセス時に、各物理ブロックの冗長領域に記憶されている論理アドレス情報に基づいて作成されるが、フラッシュメモリ２に格納しておき、必要なときにフラッシュメモリ２から読み出すようにしてもよい。こうすることより、各物理ブロックの冗長領域から論理アドレス情報を読み出してアドレス変換テーブルを作成する場合に比べて、短時間で、アドレス変換テーブルを得ることができる。
【００３６】
また、アドレス変換テーブルをフラッシュメモリ２に格納する場合は、突然の電源遮断に対応するため、常に最新のアドレス変換テーブルがフラッシュメモリ２に格納されているようにすることが好ましい。つまり、論理ブロックと物理ブロックとの対応関係が変化する毎に（つまりワークエリア８上でアドレス変換テーブルが更新される毎に）、最新のアドレス変換テーブルがフラッシュメモリ２に保存されることが好ましい。このアドレス変換テーブルの格納処理も、作成処理や更新処理と同様に論理ゾーン単位で行われる。
【００３７】
図２を参照して、論理ブロックと物理ブロックの対応関係の一例を説明する。
【００３８】
図２に示した例では、ＬＢＡ＃０−＃２０４７９９９からなる２０４８０００個の論理セクタ領域が、フラッシュメモリ２を構成する８１９２個の物理ブロックからなる記憶領域に割り当てられている。
【００３９】
それぞれの物理ブロックは、複数個の論理セクタ領域で構成された論理ブロックに割り当てられる。以下、この論理ブロックに付けられた通し番号を「論理ブロック番号（ＬＢＮ）」と言う。この例では、セクタ単位の論理アドレスであるＬＢＡが連続する２５６個の論理セクタ領域をまとめたものを論理ブロックとしている。つまり、ＬＢＡ＃０−＃２５５の２５６個の論理セクタ領域によりＬＢＮ＃０の論理ブロックが構成され、ＬＢＡ＃２５６−＃５１１の２５６個の論理セクタ領域によりＬＢＮ＃１の論理ブロックが構成されている。このように、ＬＢＡ＃０−＃２０４７９９９の２０４８０００個の論理セクタ領域によりＬＢＮ＃０−＃７９９９の８０００個の論理ブロックが構成されている。
【００４０】
更に、この論理ブロックを複数個まとめたものを論理ゾーンとしている。以下、この論理ゾーンに付けられた通し番号を「論理ゾーン番号（ＬＺＮ）」と言う。この例では、ＬＢＮ＃０−＃７９９９の８０００個の論理ブロックが、ＬＺＮ＃０−＃７の８個の論理ゾーンに対して１０００個ずつ割り当てられている。つまり、ＬＢＮ＃０−＃９９９の論理ブロックがＬＺＮ＃０の論理ゾーンに、ＬＢＮ＃１０００−＃１９９９の論理ブロックがＬＺＮ＃１の論理ゾーンに、ＬＢＮ＃２０００−＃２９９９の論理ブロックがＬＺＮ＃２の論理ゾーンに、以下、同様に、ＬＢＮ＃７０００−＃７９９９の論理ブロックがＬＺＮ＃７の論理ゾーンに割り当てられている。
【００４１】
フラッシュメモリ２を構成する８１９２個の物理ブロックには、固有の物理ブロックアドレス（ＰＢＡ）が付されている。フラッシュメモリ２を構成する物理ブロックには、出荷時からデータの書き込みや消去を正常に行うができない不良ブロックである先天性の不良ブロックと、書き込みや消去を繰返すことにより不良ブロックになった後天性の不良ブロックとがある。フラッシュメモリ２を構成する物理ブロックに含まれる後天性の不良ブロックの個数は、一般に、メーカにより規定されている保証消去回数を超えると顕著に増加する。
【００４２】
また、一般的に使用されているＮＡＮＤ型フラッシュメモリには、ＳＬＣ（single level cell）タイプのメモリセルで構成されているものと、ＭＬＣ（multi level cell）タイプのメモリセルで構成されているものとがある。ＭＬＣタイプのメモリセルで構成されたフラッシュメモリは、一般に、ＳＬＣタイプのメモリセルで構成されたフラッシュメモリに比べデータ保持期間が短く、そのデータ保持期間は、所定の消去回数を超えると顕著に短くなる。従って、ＭＬＣタイプのメモリセルで構成されたフラッシュメモリでは、保証消去回数に達していない物理ブロックであっても、所定の消去回数を超えると、その物理ブロックに格納されているデータの信頼性が低下する。
【００４３】
それぞれの論理ブロックに対応するデータは、その論理ブロックに割り当てられた物理ブロックに格納される。この論理ブロックと物理ブロックとの対応関係は、上述したアドレス変換テーブルによって管理されている。論理ブロックに割り当てる物理ブロックは、有効なデータが格納されていない物理ブロックを検索するためのテーブルである空きブロック検索テーブルを用いて検索される。
【００４４】
フラッシュメモリに格納されているデータを更新するときには、旧データが格納されている物理ブロックと同じ論理ブロックに、有効なデータが格納されていない別の物理ブロックを新たに割り当て、その別の物理ブロックに新データが格納される。そして、全ての旧データが新データで置き換えられたとき、旧データが格納されている物理ブロックは、有効なデータが格納されていない物理ブロック（以下、「無効ブロック」と言う）になる。
【００４５】
つまり、いずれかの論理ブロックに対応するデータが格納されている物理ブロック内の全てのデータが、別の物理ブロックに格納されているデータにより置き換えられたとき、その物理ブロックは無効ブロックになる。尚、無効ブロックの消去処理は、別の物理ブロックに格納されているデータにより全ての有効なデータが置き換えられたときに行われても（つまり、物理ブロックが無効ブロックになったときに行われても）、又は、その無効ブロックが論理ブロックに割り当てられる直前に行われてもよい。
【００４６】
フラッシュメモリに格納されているデータは、通常、更新される毎に格納先の物理ブロックが遷移していく。この格納先の物理ブロックの遷移は、更新頻度が高いデータに関しては多くなり、更新頻度が低いデータに関しては少なくなる。従って、格納されたデータの更新頻度の差異により、それぞれの物理ブロックの消去回数に偏りが生じる。この消去回数の偏りが過度に進行すると、消去回数が多い一部の物理ブロックが、他の物理ブロックよりも早く不良ブロックになったり、他の物理ブロックよりも早くデータ保持期間が著しく短くなったりして好ましいない。
【００４７】
このような問題を回避するため、本発明の一実施形態に係るメモリコントローラ３は、消去回数に閾値を設け、消去回数がその閾値に達した物理ブロックの消去回数の増加が抑制されるような制御を行っている。次に、この制御方法について説明する。
【００４８】
本実施の形態では、消去回数に２つの閾値が設けられ、この閾値に基づいて、フラッシュメモリ２を構成する複数個の物理ブロックが３個のグループに分割される。尚、設定される閾値の数は、適宜に設定される。例えば、３つの閾値により４個のグループに分割されるようにしても、４つの閾値により５個のグループに分割されるようにしても良い（つまり、フラッシュメモリ２を構成する複数個の物理ブロックは、Ｎ個の閾値があれば（Ｎ＋１）個のグループに分割される）。また、閾値の値（閾値となる消去回数）は、フラッシュメモリの特性に応じて適宜設定される。
【００４９】
本実施の形態では、第１の閾値ｍが、第２の閾値ｎより１０００小さい値に設定され、第２の閾値ｎが、データ保持期間の減少が顕著になる消去回数と一致するように設定されている。例えば、消去回数が５０００回を超えるとデータ保持期間の減少が顕著になるフラッシュメモリの場合には、第１の閾値ｍが４０００に、第２の閾値ｎが５０００に設定される。メモリコントローラ３は、この２つの閾値に基づいて、フラッシュメモリ２を構成する複数個の物理ブロックを３個のグループに分割する。つまり、フラッシュメモリ２を構成する複数個の物理ブロックは、消去回数がｍ回未満の物理ブロックが属する第１のグループと、消去回数がｍ回以上ｎ回未満の物理ブロックが属する第２のグループと、消去回数がｎ回以上の物理ブロックが属する第３のグループとに分割される。
【００５０】
本実施の形態では、メモリコントローラ３により、それぞれの物理ブロックを論理ブロックに割り当てた順番の先後が管理される。以下、この管理を「先後管理」と言う。
【００５１】
次に、この先後管理を図３及び図４を参照して説明する。この先後管理は、グループ毎に行われており、第１のグループに属する物理ブロックの先後管理は、図３（ａ）に示した第１の最先ブロックテーブルに基づいて行なわれ、第２のグループに属する物理ブロックの先後管理は、図３（ｂ）に示した第２の最先ブロックテーブルに基づいて行なわれ、第３のグループに属する物理ブロックの先後管理は、図３（ｃ）に示した第３の最先ブロックテーブルに基づいて行なわれる。
【００５２】
この先後管理では、次のような優先順位の管理、すなわち、論理ブロックに対して物理ブロックが新たに割り当てられたときに、新たに割り当てられたその物理ブロックの優先順位が最上位になる優先順位の管理が行われている。従って、論理ブロックに対して先に割り当てられた物理ブロックの方が、優先順位が下位になる。そして、優先順位が最下位の物理ブロックは、論理ブロックに割り当てられている物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに対応する。メモリコントローラ３は、このような優先順位の管理を行うことにより、論理ブロックに割り当てられている物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックを特定することができる。
【００５３】
また、この先後管理はグループ毎に行われているため、第１のグループに属する物理ブロックの先後管理における優先順位が最下位の物理ブロックは、第１のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに対応する。同様に、第２のグループに属する物理ブロックの先後管理における優先順位が最下位の物理ブロックは、第２のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに対応し、第３のグループに属する物理ブロックの先後管理における優先順位が最下位の物理ブロックは、第３のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに対応する。
【００５４】
例えば、図３（ａ）に示した第１の最先ブロックテーブルでは、論理ブロックに割り当てられている物理ブロックのうちで、第１のグループに属する物理ブロックの優先順位が管理されている。この第１の最先ブロックテーブルでは、ＰＢＮ＃３６の物理ブロックの優先順位が最上位になっており、ＰＢＮ＃８５７の物理ブロックの優先順位が最下位になっている。従って、ＰＢＮ＃８５７の物理ブロックが、第１のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに対応する。ここで、第１のグループに属するＰＢＮ＃５２３の物理ブロックが論理ブロックに新たに割り当てられた場合、ＰＢＮ＃５２３の物理ブロックの優先順位が最上位になり、ＰＢＮ＃３６の物理ブロックの優先順位は２番目になる。また、ＰＢＮ＃２３４の物理ブロックが無効ブロックになった場合、又はＰＢＮ＃２３４の物理ブロックに格納されているデータが消去された場合、ＰＢＮ＃２３４の物理ブロックが優先順位の管理対象から外される。つまり、ＰＢＮ＃９９５の物理ブロック、ＰＢＮ＃２３４の物理ブロック、ＰＢＮ＃６４５の物理ブロックという順番であった優先順位が、ＰＢＮ＃９９５の物理ブロック、ＰＢＮ＃６４５の物理ブロックという順番になる。
【００５５】
また、図３（ｂ）に示した第２の最先ブロックテーブルでは、論理ブロックに割り当てられている物理ブロックのうちで、第２のグループに属する物理ブロックの優先順位が管理されている。この第２の最先ブロックテーブルでは、ＰＢＮ＃９３６の物理ブロックの優先順位が最上位になっており、ＰＢＮ＃９７５の物理ブロックの優先順位が最下位になっている。従って、ＰＢＮ＃９５７の物理ブロックが、第２のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに対応する。図３（ｃ）に示した第３の最先ブロックテーブルでは、論理ブロックに割り当てられている物理ブロックのうちで、第３のグループに属する物理ブロックの優先順位が管理されている。この第３の最先ブロックテーブルでは、ＰＢＮ＃９７７の物理ブロックの優先順位が最上位になっており、ＰＢＮ＃１１１１の物理ブロックの優先順位が最下位になっている。尚、第２の最先ブロックテーブル及び第３の最先ブロックテーブルの更新も第１の最先ブロックテーブルの更新と同様に行なわれる。つまり、論理ブロックに対して新たに割り当てられた物理ブロックの優先順位が最上位になり、有効なデータが格納されていない物理ブロックになった場合は、優先順位の管理対象から外される。
【００５６】
本実施の形態では、先後管理がグループ毎に行われているため、メモリコントローラ３は、論理ブロックに対して新たに割り当てられた物理ブロックの消去回数に基づいて、その物理ブロックの登録先となる最先ブロックテーブルを決定する。つまり、図４に示したように、メモリコントローラ３は、論理ブロックに対して新たに割り当てられた物理ブロックの消去回数がｍ回未満の場合、その物理ブロックを第１のグループに対応する第１の最先ブロックテーブルに登録し、その物理ブロックの消去回数がｍ回以上ｎ回未満の場合、その物理ブロックを第２のグループに対応する第２の最先ブロックテーブルに登録し、その物理ブロックの消去回数がｎ回以上の場合、その物理ブロックを第３のグループに対応する第３の最先ブロックテーブルに登録する。
【００５７】
本実施の形態では、論理ブロックに対して割り当てる物理ブロック（つまり、有効なデータが格納されていない物理ブロック）を検索するための空きブロックテーブルもグループ毎に管理されている。この空きブロックテーブルの管理を、図５及び図６を参照して説明する。
【００５８】
図５（ａ）に示した第１の空きブロックテーブル、図５（ｂ）に示した第２の空きブロックテーブル及び図５（ｃ）に示した第３の空きブロックテーブルは、テーブル上のそれぞれのビットがいずれかの物理ブロックに対応しており、それぞれのビットの論理値が、論理ブロックに対して割り当てることが可能な物理ブロックであるか否かを示している。ここで、論理ブロックに対して割り当てることが可能な物理ブロックとは、不良ブロックではない物理ブロックであって、記憶データが消去されている物理ブロック又は有効なデータが格納されていない物理ブロック（無効ブロック）であることを意味する。以下、不良ブロックではない物理ブロックであって、記憶データが消去されている物理ブロック又は有効なデータが格納されていない物理ブロック（無効ブロック）を「空きブロック」と総称する（つまり、記憶データが消去されていない無効ブロックを含めて「空きブロック」と言う）。
【００５９】
本実施の形態では、空きブロックに該当する物理ブロックの論理値を“１”とし、空きブロックに該当しない物理ブロックの論理値を“０”としている。また、第１乃至３の空きブロックテーブルにおいて、一番上の８ビットは下位ビット側から順番に（右側のビットから順番に）ＰＢＡ＃０−＃７の物理ブロックに対応し、上から２番目の８ビットは下位ビット側から順番に（右側のビットから順番に）ＰＢＡ＃８−＃１５の物理ブロックに対応し、上から３番目の８ビットは下位ビット側から順番に（右側のビットから順番に）ＰＢＡ＃１６−＃２４の物理ブロックに対応しており、以下同様に、それぞれビットに対してＰＢＡの順番で物理ブロックが対応している。従って、図５（ａ）に示した第１の空きブロックテーブルの例では、ＰＢＡ＃８の物理ブロック及びＰＢＡ＃１５の物理ブロック等が空きブロックに該当し、図５（ｂ）に示した第２の空きブロックテーブルの例では、ＰＢＡ＃０の物理ブロック等が空きブロックに該当する。
【００６０】
また、空きブロックとなった物理ブロックに対応するビットの論理値が“１”に変更されるときには、第１乃至３の空きブロックテーブルのうちのいずれか１つのテーブル上のビットの論理値だけが“１”に変更される。この変更されるビットが属するテーブルについては、空きブロックとなった物理ブロックの消去回数に基づいて選択される。つまり、図６に示したように、メモリコントローラ３は、空きブロックとなった物理ブロックの消去回数がｍ回未満の場合、第１のグループに対応する第１の空きブロックテーブルが選択され、その物理ブロックの消去回数がｍ回以上ｎ回未満の場合、第２のグループに対応する第２の空きブロックテーブルが選択され、その物理ブロックの消去回数がｎ回以上の場合、第３のグループに対応する第３の空きブロックテーブルが選択される。
【００６１】
第１乃至３の空きブロックテーブルを用いた空きブロックの検索は、通常、ホストシステム４から与えられるデータの書き込み先として指定された論理ブロックに物理ブロックが割り当てられていないとき、又は、その論理ブロックに割り当てられている物理ブロックにホストシステム４から与えられるデータを書き込むための空き領域が無いときに行われる。そして、空きブロックの検索で検出された空きブロックは、ホストシステム４から与えられるデータの書き込み先として指定された論理ブロックに割り当てられ、ホストシステム４から与えられるデータが格納される。
【００６２】
本実施の形態では、消去回数が少ない下位側のグループから消去回数が多い上位側のグループに向かって、第１のグループ、第２のグループ、第３のグループという順番でグループ分けされている。そして、空きブロックを検索するときには、下位側のグループに対応するテーブルが優先的に使用される。つまり、第１のグループに対応する第１の空きブロックテーブルを使用した空きブロックの検索で空きブロックが検出されなかったときに、第２のグループに対応する第２の空きブロックテーブルを使用した空きブロックの検索が行われ、更に、第２のグループに対応する第２の空きブロックテーブルを使用した空きブロックの検索で空きブロックが検出されなかったときに、第３のグループに対応する第３の空きブロックテーブルを使用した空きブロックの検索が行われる。このようにすることにより、空きブロックのうち下位側のグループに属する物理ブロックが優先的に論理ブロック割り当てられる。その結果、上位側のグループに属する物理ブロックの消去回数の増加が抑制される。
【００６３】
しかし、このように下位側のグループに対応するテーブルが優先的に使用されるようにしただけでは、上位側のグループに属する物理ブロックの消去回数の増加が適切に抑制されない場合がある。例えば、下位側のグループに属する物理ブロックに書き換え頻度の低いデータが格納されてしまった場合、上位側のグループに属する物理ブロックの消去回数の増加が適切に抑制されない。このような場合、書き換え頻度の低いデータを上位側のグループに属する物理ブロックに格納されるようにすれば、上位側のグループに属する物理ブロックの消去回数の増加が適切に抑制される。従って、本実施の形態では、空きブロックの検索により空きブロックが検出されたときに、その空きブロックが属するグループよりも下位のグループに属する物理ブロックが存在する場合には、その下位のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックに格納されているデータが、空きブロックの検索により検出された空きブロックに転送される。このデータ転送後に、その転送元の物理ブロックが、空きブロックの検索により検出された空きブロックの代替になる。つまり、その転送元の物理ブロックが、ホストシステム４から与えられるデータの書き込み先として指定された論理ブロックに割り当てられ、ホストシステム４から与えられるデータが格納される。このようなデータ転送が行われることより、上位側のグループに属する物理ブロックに書き換え頻度の低いデータが格納され、上位側のグループに属する物理ブロックの消去回数の増加が効果的に抑制される。
【００６４】
本実施の形態では、下位側のグループから上位側のグループに向かって、第１のグループ、第２のグループ、第３のグループという順番でグループ分けされている。従って、第２のグループに対応する第２の空きブロックテーブル又は第３のグループに対応する第３の空きブロックテーブルを使用した空きブロックの検索により空きブロックが検出された場合に、その空きブロックが属するグループよりも下位のグループに属する物理ブロックが存在することがある。つまり、第２の空きブロックテーブルを使用した空きブロックの検索により空きブロックが検出された場合、第１のグループに属する物理ブロックが、その空きブロックが属するグループよりも下位のグループに属する物理ブロックに該当し、第３の空きブロックテーブルを使用した空きブロックの検索により空きブロックが検出された場合、第１のグループ及び第２のグループに属する物理ブロックが、その空きブロックが属するグループよりも下位のグループに属する物理ブロックに該当する。
【００６５】
例えば、第２の空きブロックテーブルを使用した空きブロックの検索により空きブロックが検出された場合、第１の最先ブロックテーブルを使用した検索（つまり、第１のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックの検索）が行われる。そして、この第１の最先ブロックテーブルを使用した検索により検出された物理ブロック（つまり、第１のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロック）に格納されているデータが、第２の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロック（つまり、第２のグループに属する空きブロック）に転送される。このデータ転送の終了後、転送元の物理ブロック（第１の最先ブロックテーブルを使用した検索により検出された物理ブロック）が論理ブロックに割り当てられ、その転送元の物理ブロックにホストシステム４から与えられるデータが格納される。尚、第１の最先ブロックテーブルに登録されている物理ブロックが存在しない場合には、このデータ転送は行われず、第２の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロックがそのまま使用される。つまり、第２の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロック（つまり、第２のグループに属する空きブロック）が論理ブロックに割り当てられ、その空きブロックにホストシステム４から与えられるデータが格納される。
【００６６】
また、第３の空きブロックテーブルを使用した空きブロックの検索により空きブロックが検出された場合、まず第１の最先ブロックテーブルを使用した検索（つまり、第１のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックの検索）が行われる。そして、この第１の最先ブロックテーブルを使用した検索により検出された物理ブロック（つまり、第１のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロック）に格納されているデータが、第３の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロック（つまり、第３のグループに属する空きブロック）に転送される。このデータ転送の終了後、転送元の物理ブロック（第１の最先ブロックテーブルを使用した検索により検出された物理ブロック）が論理ブロックに割り当てられ、その転送元の物理ブロックにホストシステム４から与えられるデータが格納される。尚、第１の最先ブロックテーブルに登録されている物理ブロックが存在しない場合には、第２の最先ブロックテーブルを使用した検索（つまり、第２のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックの検索）が行われる。そして、この第２の最先ブロックテーブルを使用した検索により検出された物理ブロック（つまり、第２のグループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロック）に格納されているデータが、第３の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロック（つまり、第３のグループに属する空きブロック）に転送される。このデータ転送の終了後、転送元の物理ブロック（第２の最先ブロックテーブルを使用した検索により検出された物理ブロック）が論理ブロックに割り当てられ、その転送元の物理ブロックにホストシステム４から与えられるデータが格納される。尚、第２の最先ブロックテーブルにも登録されている物理ブロックが存在しない場合には、このデータ転送は行われず、第３の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロックがそのまま使用される。つまり、第３の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロック（つまり、第３のグループに属する空きブロック）が論理ブロックに割り当てられ、その空きブロックにホストシステム４から与えられるデータが格納される。
【００６７】
次に、フラッシュメモリ２を構成する物理ブロックの消去回数の管理と先後管理のための優先順位管理の方法を、図７に示した例を参照して説明する。図７に示したテーブルには、ＰＢＡの順番で、各物理ブロックの優先順位リンク番号と消去回数が記載されている。このテーブルには、その物理ブロックより優先順位が１つ上の物理ブロックのＰＢＡと、その物理ブロックより優先順位が１つ下の物理ブロックのＰＢＡが、優先順位リンク番号として書き込まれる。従って、論理ブロックに割り当てられていない物理ブロックについては、優先順位リンク番号が消去される。また、優先順位が最上位の物理ブロックについては、その物理ブロックより優先順位が１つ上の物理ブロックのＰＢＡが書き込まれておらず、優先順位が最下位の物理ブロックについては、その物理ブロックより優先順位が１つ下の物理ブロックのＰＢＡが書き込まれていない。
【００６８】
このテーブルを参照することにより、例えば、ＰＢＡ＃０の物理ブロックの場合、その物理ブロックより優先順位が１つ上の物理ブロックはＰＢＡ＃１１８であり、その物理ブロックより優先順位が１つ下の物理ブロックはＰＢＡ＃５７２であることが分かる。
【００６９】
このテーブルには、各グループの優先順位が最上位の物理ブロックと最下位の物理ブロックのＰＢＡも記載されている。従って、論理ブロックに新たに物理ブロックが割り当てられたときは、優先順位が最上位の物理ブロックが変わるので、優先順位が最上位の物理ブロックを示すＰＢＡの記載が変更される。また、優先順位が最下位の物理ブロックが有効なデータが格納されていない物理ブロックになったときや、優先順位が最下位の物理ブロックに格納されている全てのデータが別のブロックに転送されたときは、優先順位が最下位の物理ブロックが変わるので、優先順位が最下位の物理ブロックを示すＰＢＡの記載が変更される。
【００７０】
例えば、第１のグループに属するＰＢＡ＃５２３の物理ブロックが、論理ブロックに新たに割り当てられた場合、第１のグループに属する優先順位が最上位の物理ブロックを示すＰＢＡが、＃３６から＃５２３に変更される。また、ＰＢＡが＃３６の物理ブロックの優先順位リンク番号として、優先順位が１つ上の物理ブロックを示すＰＢＡである＃５２３が記載される。ＰＢＡが＃５２３の物理ブロックの優先順位リンク番号として、優先順位が１つ下の物理ブロックを示すＰＢＡである＃３６が記載される。
【００７１】
各物理ブロックの消去回数は、各物理ブロックに格納されているデータが消去される毎に更新される。例えば、ＰＢＡが＃０の物理ブロックに格納されているデータが消去された場合には、テーブルに記載されている消去回数が１０００から１００１に変更され、テーブルに記載されている優先順位リンク番号は消去される。また、ＰＢＡ＃１１８の物理ブロックより優先順位が１つ下の物理ブロックは、ＰＢＡ＃５７２の物理ブロックになるので、ＰＢＡ＃１１８の物理ブロックとＰＢＡ＃５７２の物理ブロックの優先順位リンク番号が更新される。つまり、ＰＢＡ＃１１８の物理ブロックの優先順位リンク番号については、優先順位が１つ下の物理ブロックを示すＰＢＡが＃０から＃５７２に変更される。また、ＰＢＡ＃５７２の物理ブロックの優先順位リンク番号については、優先順位が１つ上の物理ブロックを示すＰＢＡが＃０から＃１１８に変更される。
【００７２】
以上、本発明の実施の形態を説明したが、これは本発明の説明のための例示であって、本発明の範囲をこの実施の形態にのみ限定する趣旨ではない。本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。
【００７３】
例えば、上述の実施の形態では、物理ブロック単位で物理ブロックの消去回数の管理、先後管理及び空きブロックテーブルの管理を行っていたが、論理ブロックに対して複数個の物理ブロックで構成された仮想ブロックを割り当てる場合には、これらの管理を仮想ブロック単位で行うようにしてもよい。つまり、それぞれの仮想ブロックを構成する物理ブロックが初期設定等により決められている場合には、同じ仮想ブロックに属する物理ブロックの消去回数は同じなる。また、論理ブロックへの割り当てとデータの消去が仮想ブロック単位で行われるため、先後管理及び空きブロックテーブルの管理も仮想ブロック単位で行うことができる。先後管理を仮想ブロック単位で行う場合には、仮想ブロック単位で上述の優先順位を管理（つまり、優先順位リンク番号を仮想ブロックに付けた通し番号で管理）すればよい。空きブロックテーブルの管理を仮想ブロック単位で行う場合には、テーブル上の各ビットに仮想ブロックを割り当てる（つまり、１つのビットに1個の仮想ブロックを割り当てる）ようにすればよい。
【００７４】
また、第３の空きブロックテーブルを使用した空きブロックの検索により空きブロックが検出されたときに、第１の最先ブロックテーブル及び第２の最先ブロックテーブルのいずれのテーブルにも登録されている物理ブロックが存在しない場合には、第３の最先ブロックテーブルを使用した検索（つまり、第３グループに属する物理ブロックのうちで最も先に論理ブロックに割り当てられた物理ブロックの検索）が行われるようにしてもよい。そして、第３の最先ブロックテーブルを使用した検索により検出された物理ブロックの消去回数が、第３の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロックの消去回数よりも所定回数以上少ない場合には、第３の最先ブロックテーブルを使用した検索により検出された物理ブロックに格納されているデータが、第３の空きブロックテーブルを使用した空きブロックの検索により検出された空きブロックに転送されるようにしてもよい。このようにすることにより、第３グループに属する物理ブロック間で消去回数の差が大きくなることが抑制される。
【００７５】
尚、物理ブロックの消去回数の管理、先後管理及び空きブロックテーブルの管理の方法については、上述の方法以外の方法であってもよい。例えば、先後管理は、最も先に論理ブロックに割り当てられた物理ブロックを特定することができれば、上述の優先順位による管理を用いなくてよい。
【符号の説明】
【００７６】
１…フラッシュメモリシステム、２…フラッシュメモリ、３…メモリコントローラ、６…マイクロプロセッサ
【図１】
2010182266.tif 000003
【図２】
2010182266.tif 000004
【図３】
2010182266.tif 000005
【図４】
2010182266.tif 000006
【図５】
2010182266.tif 000007
【図６】
2010182266.tif 000008
【図７】
2010182266.tif 000009