(57)【要約】  フラッシュメモリ制御方法および制御装置が提供される。フラッシュメモリ制御方法は、フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能が支援される環境において、前記多重ブロック消去機能を考慮して使用可能なブロックリサイクル方式それぞれの費用を算出するステップと、前記算出された費用に基づいて前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択するステップと、前記使用可能なブロックリサイクル方式のうち選択された少なくとも１つを用いて少なくとも１つのブロックを管理するステップとを含む。
2011530758.tif 000002
【特許請求の範囲】
【請求項１】
フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能を支援する消去部と、
前記多重ブロック消去機能が支援される環境において、使用可能なブロックリサイクル方式のうち少なくとも１つを用いて少なくとも１つのブロックを管理する管理部と、
を含むことを特徴とするフラッシュメモリ制御装置。
【請求項２】
前記多重ブロック消去機能を考慮して前記使用可能なブロックリサイクル方式それぞれの費用を算出する費用算出部と、
前記算出された費用に基づいて前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択する選択部と、をさらに含み、
前記管理部は、前記使用可能なブロックリサイクル方式のうち前記選択された少なくとも１つを用いて前記少なくとも１つのブロックを管理することを特徴とする請求項１に記載のフラッシュメモリ制御装置。
【請求項３】
前記管理部は、前記使用可能なブロックリサイクル方式のうち少なくとも１つを用いて前記少なくとも１つのブロックに含まれた少なくとも１つの無効ページのデータを処理することを特徴とする請求項１に記載のフラッシュメモリ制御装置。
【請求項４】
前記複数のブロックは、少なくとも１つのデータブロックまたは少なくとも１つのログブロックを含むことを特徴とする請求項１に記載のフラッシュメモリ制御装置。
【請求項５】
前記費用算出部は、前記同時に消去される複数のブロックの数を考慮して前記使用可能なブロックリサイクル方式それぞれの費用を算出することを特徴とする請求項２に記載のフラッシュメモリ制御装置。
【請求項６】
前記選択部は、前記使用可能なブロックリサイクル方式のうち最小の費用を有する少なくとも１つを選択することを特徴とする請求項２に記載のフラッシュメモリ制御装置。
【請求項７】
前記使用可能なブロックリサイクル方式は、併合演算方式、交換演算方式、複写後交換演算方式、移行演算方式、またはページ消去後複写演算方式のうち少なくとも１つを含むことを特徴とする請求項１に記載のフラッシュメモリ制御装置。
【請求項８】
前記消去部は、前記フラッシュメモリの複数のブロックそれぞれに含まれた複数のページを選択的に消去するページ単位消去機能を支援することを特徴とする請求項１に記載のフラッシュメモリ制御装置。
【請求項９】
第１ブロックおよび第２ブロックを含むフラッシュメモリ制御方法であって、
前記第１ブロックに存在する少なくとも１つの無効ページに記録された除去対象データを選択的に消去するステップと、
前記除去対象データが消去された前記第１ブロックに存在する少なくとも１つの無効ページに、前記第２ブロックに存在する少なくとも１つの有効ページに記録された有効データを複写するステップと、
前記第２ブロックに存在する複数のページに記録されたデータを消去するステップと、
を含むことを特徴とするフラッシュメモリ制御方法。
【請求項１０】
前記第１ブロックに存在する少なくとも１つの無効ページに記録された除去対象データを選択的に消去するステップは、前記第１ブロックに存在する少なくとも１つの無効ページに記録された除去対象データを選択的に消去する時、前記第１ブロックに存在する少なくとも１つの有効ページに記録されたデータが消去されることがある場合、第３ブロックに存在する少なくとも１つのページに前記第１ブロックに存在する少なくとも１つの有効ページに記録されたデータを複写するステップを含むことを特徴とする請求項９に記載のフラッシュメモリ制御方法。
【請求項１１】
前記除去対象データが消去された前記第１ブロックに存在する少なくとも１つの無効ページに、前記第２ブロックに存在する少なくとも１つのページに記録された有効データを複写するステップは、前記第３ブロックに存在する少なくとも１つのページに複写されたデータを前記第１ブロックに存在する複数のページに複写するステップをさらに含むことを特徴とする請求項１０に記載のフラッシュメモリ制御方法。
【請求項１２】
前記第２ブロックに存在する複数のページに記録されたデータを消去するステップは、前記第２ブロックに存在する複数のページに記録されたデータを同時に消去するステップであることを特徴とする請求項９に記載のフラッシュメモリ制御方法。
【請求項１３】
フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能が支援される環境において、前記多重ブロック消去機能を考慮して使用可能なブロックリサイクル方式それぞれの費用を算出するステップと、
前記算出された費用に基づいて前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択するステップと、
前記使用可能なブロックリサイクル方式のうち選択された少なくとも１つを用いて少なくとも１つのブロックを管理するステップと、
を含むことを特徴とするフラッシュメモリ制御方法。
【請求項１４】
前記少なくとも１つのブロックを管理するステップは、前記使用可能なブロックリサイクル方式のうち選択された少なくとも１つを用いて前記少なくとも１つのブロックに含まれた少なくとも１つの無効ページのデータを処理するステップであることを特徴とする請求項１３に記載のフラッシュメモリ制御方法。
【請求項１５】
前記使用可能なブロックリサイクル方式それぞれの費用を算出するステップは、前記同時に消去される複数のブロックの数を考慮して前記使用可能なブロックリサイクル方式それぞれの費用を算出するステップであることを特徴とする請求項１３に記載のフラッシュメモリ制御方法。
【請求項１６】
前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択するステップは、前記使用可能なブロックリサイクル方式のうち最小の費用を有する少なくとも１つを選択するステップであることを特徴とする請求項１３に記載のフラッシュメモリ制御方法。
【請求項１７】
前記使用可能なブロックリサイクル方式は、併合演算方式、交換演算方式、複写後交換演算方式、移行演算方式、またはページ消去後複写演算方式のうち少なくとも１つを含むことを特徴とする請求項１３に記載のフラッシュメモリ制御方法。
【請求項１８】
請求項９に記載の方法を行うためのプログラムが記録されたコンピュータで読み出し可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、フラッシュメモリに存在するブロックに記録されたデータを整理し、前記ブロックをリサイクルする技術に関する。
【背景技術】
【０００２】
フラッシュメモリは、データを電気的に消去（ｅｒａｓｅ）したり、プログラムすることのできる非揮発性メモリであって、データの記録および削除が自由なＲＡＭの長所と電源の供給なくても記録されているデータを格納するＲＯＭの長所を同時に有する。このようなフラッシュメモリは、デジタルカメラ、ＰＤＡ、ＭＰ３プレーヤー、携帯用電話機、移動式の保存媒体などのように多くのアプリケーションで用いられている。
【０００３】
フラッシュメモリは複数のブロックに構成され、複数のブロックそれぞれは複数のページを含む。
【０００４】
フラッシュメモリにおいて、データはページ単位でプログラムすることができる。すなわち、プログラム動作が行われる場合、データはフラッシュメモリに存在するページに順次記録され得る。また、一般的なフラッシュメモリにおいて実際実現上の問題、設計の複雑度の増加などによってデータはブロック単位に消去される。例えば、１つのブロックが２以上のページを含む場合、一般的なフラッシュメモリはブロック全体（２以上のページ全て）に対して消去動作を行なうことがあるが、２以上のページのうちいずれか１つに対して順次消去動作を行なわない。
【０００５】
また、フラッシュメモリは、本来のその場更新（ｉｎ−ｐｌａｃｅ  ｕｐｄａｔｅ）が不可能であるという制約を有する。すなわち、ページＡに記録されたデータに対する更新が必要な場合、更新されたデータは再びページＡにプログラムされることができず、初期化された状態を有するページＢにプログラムされなければならない。
【０００６】
このとき、データの更新回数が増加する場合、過去に用いられたページは無効（ｉｎｖａｌｉｄ）ページになる。したがって、このようなフラッシュメモリを効率的に用いるためには無効ページを適切に収集して初期化することによって、初期化されたブロックを製造しなければならない。無効ページを適切に収集して初期化するために用いられる方式を「ブロックリサイクル方式」という。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の一実施形態に係るフラッシュメモリ制御装置および制御方法は、フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能を支援することによって、ブロックリサイクルに消耗する費用を減少する。
【０００８】
また、本発明の一実施形態に係るフラッシュメモリ制御装置および制御方法は、多重ブロック消去機能を考慮して使用可能なブロックリサイクル方式それぞれの費用を算出し、算出結果に基づいて少なくとも１つのブロックリサイクル方式を選択することによって、ブロックリサイクルに最適化した方式を用いる。
【０００９】
また、本発明の一実施形態に係るフラッシュメモリ制御装置および制御方法は、ブロック単位でないページ単位に基づいて選択的に無効ページに記録された除去対象データを消去することによって、より効率的な新しいブロックリサイクル方式を提供する。
【課題を解決するための手段】
【００１０】
本発明の一実施形態に係る第１ブロックおよび第２ブロックを含むフラッシュメモリ制御方法は、前記第１ブロックに存在する少なくとも１つの無効ページに記録された除去対象データを選択的に消去するステップと、前記除去対象データが消去された前記第１ブロックに存在する少なくとも１つの無効ページに、前記第２ブロックに存在する少なくとも１つの有効ページに記録された有効データを複写するステップと、前記第２ブロックに存在する複数のページに記録されたデータを消去するステップとを含む。
【００１１】
また、本発明の一実施形態に係るフラッシュメモリ制御方法は、フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能が支援される環境において、前記多重ブロック消去機能を考慮して使用可能なブロックリサイクル方式それぞれの費用を算出するステップと、前記算出された費用に基づいて前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択するステップと、前記使用可能なブロックリサイクル方式のうち選択された少なくとも１つを用いて少なくとも１つのブロックを管理するステップとを含む。
【００１２】
また、本発明の一実施形態に係るフラッシュメモリ制御装置は、フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能を支援する消去部と、前記多重ブロック消去機能が支援される環境において、使用可能なブロックリサイクル方式のうち少なくとも１つを用いて少なくとも１つのブロックを管理する管理部とを含む。
【発明の効果】
【００１３】
本発明の一実施形態に係るフラッシュメモリ制御装置および制御方法は、フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能を支援することによって、ブロックリサイクルに消耗する費用を減少させることができる。
【００１４】
また、本発明の一実施形態に係るフラッシュメモリ制御装置および制御方法は、多重ブロック消去機能を考慮して使用可能なブロックリサイクル方式それぞれの費用を算出し、算出結果に基づいて少なくとも１つのブロックリサイクル方式を選択することによって、ブロックリサイクルに最適化された方式を用いることができる。
【００１５】
また、本発明の一実施形態に係るフラッシュメモリ制御装置および制御方法はブロック単位ではないページ単位に基づいて選択的に無効ページに記録された除去対象データを消去することによって、より効率的な新しいブロックリサイクル方式を提供することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に係るブロックに対する併合演算過程を概念的に示す図である。
【図２】本発明の一実施形態に係るブロックに対する交換演算過程を概念的に示す図である。
【図３】本発明の一実施形態に係るブロックに対する複写後交換演算過程を概念的に示す図である。
【図４】本発明の一実施形態に係るブロックに対する移行演算過程を概念的に示す図である。
【図５】本発明の一実施形態に係るページ単位消去機能を支援するページ消去後複写演算過程を概念的に示す図である。
【図６】本発明の一実施形態に係るフラッシュメモリ制御方法において用いられるページ消去後複写演算方式を示した動作フローチャートである。
【図７】本発明の他の実施形態に係るフラッシュメモリ制御方法を示した動作フローチャートである。
【図８】本発明の一実施形態に係るフラッシュメモリ制御装置を示すブロック図である。
【発明を実施するための形態】
【００１７】
以下、本発明に係る好適な実施形態を添付された図面を参照して詳細に説明する。
【００１８】
（ブロックリサイクル方式）
フラッシュメモリをより効率的に用いるため無効ページを適切に収集して初期化しなければならない。このとき、無効ページを適切に収集して初期化するために用いられる方式を「ブロックリサイクル方式」という。
【００１９】
ブロックリサイクル方式は多様に存在することがあり、より具体的には、併合演算方式、交換演算方式、複写後交換演算方式、または移行演算（ｍｉｇｒａｔｉｏｎ  ｏｐｅｒａｔｉｏｎ）方式を含んでもよい。以下は、併合演算方式、交換演算方式、複写後交換演算方式および移行演算方式に対して詳細に説明する。
【００２０】
（１）併合演算方式
図１は、本発明の一実施形態に係るブロックに対する併合演算過程を概念的に示す図である。
【００２１】
図１を参照すれば、フラッシュメモリは、データブロックＢＬＫ０、ログブロックＬＯＧ０、空いているブロックＦＲＥＥ０を含む。ここで、データブロックＢＬＫ０、ログブロックＬＯＧ０、空いているブロックＦＲＥＥ０はそれぞれ４個のページから構成される。
【００２２】
データブロックＢＬＫ０に存在する４個のページには最初に本来のデータが記録され、前記データに対する更新が必要な場合、更新されたデータはログブロックＬＯＧ０に存在するページに記録される。また、ログブロックＬＯＧ０に存在するページに記録されたデータはログブロックＬＯＧ０内で継続的に更新される。
【００２３】
図面符号１１０を参照すれば、データブロックＢＬＫ０で最初のページと３番目のページに記録されたデータは更新されてログブロックＬＯＧ０に記録されたため、捨てられるべき意味のないデータである。ここで、データブロックＢＬＫ０において最初のページと３番目のページを無効（ｉｎｖａｌｉｄ）ページという。ただし、データブロックＢＬＫ０において２番目のページと４番目のページに格納されたデータは意味のあるデータであるため、２番目のページと４番目のページは有効ページである。
【００２４】
また、図面符号１１０において、ログブロックＬＯＧ０の最初のページに記録されたデータは更新されて２番目のページに記録され、３番目のページに記録されたデータは更新されて４番目のページに記録される。結局、ログブロックＬＯＧ０の最初のページおよび３番目のページは無効ページであり、２番目のページおよび４番目のページは有効ページである。
【００２５】
併合演算方式によれば、データブロックＢＬＫ０およびログブロックＬＯＧ０の有効ページに記録されているデータは空いているブロックＦＲＥＥ０のページに複写される。より具体的に、データブロックＢＬＫ０の２番目のページおよび４番目のページに記録されたデータはそれぞれ空いているブロックＦＲＥＥ０の２番目のページおよび４番目のページに複写される。また、ログブロックＬＯＧ０の２番目のページおよび４番目のページに記録されたデータはそれぞれ空いているブロックＦＲＥＥ０の最初のページおよび３番目のページに複写される。結果的に、空いているブロックＦＲＥＥ０には有効ページに記録されていたデータのみが格納されるのであろう。
【００２６】
図面符号１２０を参照すれば、図面符号１１０の空いているブロックＦＲＥＥ０は新しいデータブロックＢＬＫ０になる。すなわち、新しいデータブロックＢＬＫ０には有効ページに記録されていたデータが整理された状態に記録される。このとき、従来におけるデータブロックＢＬＫ０とログブロックＬＯＧ０はブロック単位に全体的に消去される。ただし、本発明の一実施形態によれば、ページ単位に消去動作が行われ、これについては以下で詳細に説明する。
【００２７】
図面符号１３０は従来における（図面符号１１０の）データブロックＢＬＫ０とログブロックＬＯＧ０が消去されることによって初期化されたことを表す。また、従来のデータブロックＢＬＫ０は、新しいログブロックＬＯＧ０になる。また、新しいデータブロックＢＬＫ０は、意味のあるデータのみ格納していることが分かる。結局、併合演算過程によれば、図面符号１１０、１２０および１３０に示された過程によってブロックがリサイクルされていることが分かる。
【００２８】
このとき、データを複写するために求められるページ当たり費用がＣｃｐであり、複写されるページの数が１つのブロックに含まれたページの数とＮｐとして同一であると仮定する。また、ブロックを消去するために求められる費用がＣＥと仮定する。また、併合演算方式を適用することによって得られる空いているページの数はＮｐである。したがって、併合演算方式を適用する場合、１つの空いているページを獲得するために求められる費用は数１のように表してもよい。
【００２９】
【数１】
2011530758.tif 000003
【００３０】
ただし、以下で説明するが、複数のブロックに対して同時に消去動作を行なうことのできる多重ブロック消去機能が支援される場合、数１は変更されなければならない。これに対しては以下で再び説明する。
【００３１】
（２）交換演算方式
リサイクルされなければならないデータブロックに存在する全てのページが無効ページであり、前記データブロックに対応するログブロックに存在する全てのページが有効ページである場合に交換演算方式が適用され得る。
【００３２】
図２は、本発明の一実施形態に係るブロックに対する交換演算過程を概念的に示す図である。
【００３３】
図面符号２１０を参照すれば、データブロックＢＬＫ０に存在する４個のページは全て無効ページであり、ログブロックＬＯＧ０に存在する４個のページは全て有効ページである。このとき、データブロックＢＬＫ０に対して消去が行われる。
【００３４】
図面符号２２０を参照すれば、図面符号２１０のデータブロックＢＬＫ０は消去されたことが分かる。また、図面符号２１０のデータブロックＢＬＫ０は新しいログブロックＬＯＧ０になり、図面符号２１０のログブロックＬＯＧ０が新しいデータブロックＢＬＫ０になる。
【００３５】
交換演算方式によって４個の空いているページが獲得される。一般に、交換演算方式を適用する場合、１つの空いているページを獲得するために求められる費用は数２のように表してもよい。
【００３６】
【数２】
2011530758.tif 000004
【００３７】
（３）複写後交換演算方式
複写後交換演算方式はリサイクルされなければならないデータブロックに対応するログブロックの全てのページが有効ページである場合に適用され得る。
【００３８】
図３は、本発明の一実施形態に係るブロックに対する複写後交換演算過程を概念的に示す図である。
【００３９】
図面符号３１０を参照すれば、データブロックＢＬＫ０は３つの無効ページと１つの有効ページを含む。また、データブロックＢＬＫ０の３つの無効ページに記録されていたデータは更新されてログブロックＬＯＧ０に存在する３つのページに記録されている。複写後交換演算方式によれば、データブロックＢＬＫ０の４番目のページである有効ページに記録されたデータはログブロックＬＯＧ０の空いているページである４番目のページに複写される。
【００４０】
また、図面符号３２０を参照すれば、データブロックＢＬＫ０の４番目のページに記録されたデータがログブロックＬＯＧ０の４番目のページに複写されたため、データブロックＢＬＫ０の４番目のページは無効ページとなる。このとき、データブロックＢＬＫ０は消去される。
【００４１】
また、図面符号３３０を参照すれば、図面符号３１０および３２０のデータブロックＢＬＫ０は消去され、図面符号３１０および３２０のログブロックＬＯＧ０は全て有効ページに構成される。このとき、データブロックＢＬＫ０とログブロックＬＯＧ０は互いに交換されることによって、図面符号３１０および３２０のログブロックＬＯＧ０は新しいデータブロックＢＬＫ０になり、図面符号３１０および３２０のデータブロックＢＬＫ０は新しいログブロックＬＯＧ０になる。
【００４２】
複写後交換演算方式によれば、Ｎｐ個の新たに空いているページを獲得するために複写過程においてｋＣｃｐ（ｋ：複写されるページの数）費用が消耗され、消去過程においてＣＥの費用が消耗されることが分かる。結局、複写後交換演算方式によって１つの新たに空いているページを獲得するために求められる費用は数３のように表してもよい。
【００４３】
【数３】
2011530758.tif 000005
【００４４】
（４）移行演算（ｍｉｇｒａｔｉｏｎ  ｏｐｅｒａｔｉｏｎ）方式
移行演算方式によれば、リサイクルされなければならないデータブロックに対応するログブロックのｋ個の有効ページは空いているブロックのページに複写される。その後、ログブロックは消去される。これによって、消去されたログブロックは新たに空いているブロックになる。
【００４５】
図４は、本発明の一実施形態に係るブロックに対する移行演算過程を概念的に示す図である。
【００４６】
図面符号４１０を参照すれば、ログブロックＬＯＧ０に存在する４個のページのうち３つのページは無効ページであり、１つのページのみが有効ページであることが分かる。このとき、ログブロックＬＯＧ０の４番目のページに記録されているデータは空いているブロックＦＲＥＥ０に存在するページに複写される。
【００４７】
また、図面符号４２０を参照すれば、ログブロックＬＯＧ０の４番目のページに記録されているデータが空いているブロックＦＲＥＥ０に存在するページに複写されたため、ログブロックＬＯＧ０の４番目のページは無効ページと処理される。このとき、ログブロックＬＯＧ０は消去される。
【００４８】
また、図面符号４３０を参照すれば、図面符号４２０のログブロックＬＯＧ０が消去され、新しく空いているブロックＦＲＥＥ０が製造される。
【００４９】
結局、移行演算方式によれば、Ｎｐ（１つのブロックに含まれたページの数）−ｋ（複写されたページの数）個の新たに空いているページが製造されることが分かる。すなわち、Ｎｐ−ｋ個の新たに空いているページを製造するために消去過程においてＣＥの費用が求められ、複写過程においてｋＣｃｐの費用が求められる。したがって、移行演算方式を介して１つの新たに空いているページを獲得するために求められる費用は数４のように表してもよい。
【００５０】
【数４】
2011530758.tif 000006
【００５１】
変換演算、交換演算、交換後複写演算、移行演算方式に対する前述した内容はブロック単位に消去動作が行われる場合に関するものである。ただし、複数のブロックに対して同時に消去動作が行われるか、ページ単位に消去動作が行われる場合、前述したブロックリサイクル方式とは異なる方式が提案され得る。
【００５２】
（ページ消去後複写演算方式）
図５は、本発明の一実施形態に係るページ単位消去機能を支援するページ消去後複写演算過程を概念的に示す図である。
【００５３】
図面符号５１０を参照すれば、ページ単位に消去動作が行われることがあるため、ログブロックＬＯＧ０に存在する無効ページである３番目のページのみが消去される。すなわち、ログブロックＬＯＧ０の有効ページである最初のページ、２番目のページ、４番目のページはそのまま維持され、３番目のページのみが選択的に消去される。
【００５４】
また、図面符号５２０を参照すれば、データブロックＢＬＫ０に存在する有効ページは、ログブロックＬＯＧ０の空いているページに複写される。その後、データブロックＢＬＫ０に存在する有効ページは無効ページとして取り扱われる。
【００５５】
また、図面符号５３０を参照すれば、データブロックＢＬＫ０は消去される。
【００５６】
また、図面符号５４０を参照すれば、図面符号５３０のログブロックＬＯＧ０は有効ページのみを含む。すなわち、図面符号５３０のログブロックＬＯＧ０は新しいデータブロックＢＬＫ０として取り扱われる。
【００５７】
また、図面符号５３０のデータブロックＢＬＫ０は消去されるため、空いているブロックになり、その後、新しいデータブロックＢＬＫ０に対応する新しいログブロックＬＯＧ０として取り扱われる。
【００５８】
ただし、ページ単位に消去動作が行われ得る場合であっても、一回の消去動作が行われる時、消去されなければならない最小限のページの数が１よりも大きい場合があり得る。例えば、最小限に２つまたは３つのページに対して消去動作が行われる場合があり得る。このとき、図面符号５１０のログブロックＬＯＧ０に存在する無効ページのみを消去することは不可能であり、図面符号５１０のログブロックＬＯＧ０に存在する無効ページを消去するためには有効ページを消去せざるを得ない場合が発生する。
【００５９】
このような場合、本発明の一実施形態によれば、消去動作を行う前に消去動作が行われるとき、消去せざるを得ない有効ページを他の空いているページに予め複写しておいてもよい。その後、前記他の空いているページに予め複写されたデータを新しいデータブロックＬＯＧ０に再び複写することによって、消去せざるを得ない有効ページにあるデータを保存することができる。
【００６０】
結局、ページ消去後複写演算方式によれば、無効ページを消去するためにＣＰＥの費用が求められ、ｋ個の有効ページを複写するためにｋＣｃｐの費用が求められる。また、いずれか１つのブロックを消去するためにＣＥの費用が消耗される。また、ページ消去後複写演算方式によって１つの新たに空いているブロックが獲得されるため、得られるページの数はＮｐである。
【００６１】
したがって、ページ消去後複写演算方式によって１つの新たに空いているページを獲得するために求められる費用は数５のように表してもよい。
【００６２】
【数５】
2011530758.tif 000007
【００６３】
ここで、αは無効ページを消去するためには有効ページを消去せざるを得ない場合、さらに必要な複写過程に対応する費用である。
【００６４】
（多重ブロック消去機能が支援される環境において、ブロックリサイクル方式の費用モデル）
前述した実施形態は、消去動作が１つのブロックに対してのみ行われる場合、ブロックリサイクル方式の動作原理および費用について説明した。ただし、本発明の一実施形態によれば、複数のブロックに格納されたデータ（情報）を同時に消去してもよい。このような場合、ブロックリサイクル方式それぞれに対して１つのページを獲得するために求められる費用は修正しなければならない。
【００６５】
以下は、Ｍ個のブロックに対して同時に消去動作が行われると仮定する。
【００６６】
（１）併合演算方式の費用モデル修正
図１と関連する説明および数１において、１つのブロックを消去するために求められる費用がＣＥと仮定したが、Ｍ個のブロックが同時に消去される場合、１つのブロックを消去するために求められる費用はＣＥ／Ｍに減少する。したがって、数１は数６のように修正しなければならない。
【００６７】
【数６】
2011530758.tif 000008
【００６８】
（２）交換演算方式の費用モデル修正
多重ブロック消去機能が支援される環境において、数２は数７のように修正しなければならない。
【００６９】
【数７】
2011530758.tif 000009
【００７０】
（３）複写後交換演算方式の費用モデル修正
多重ブロック消去機能が支援される環境において、数３は数８のように修正しなければならない。
【００７１】
【数８】
2011530758.tif 000010
【００７２】
（４）移行演算方式の費用モデル修正
多重ブロック消去機能が支援される環境において、数４は数９のように修正しなければならない。
【００７３】
【数９】
2011530758.tif 000011
【００７４】
（５）ページ消去後複写演算方式の費用モデル修正
多重ブロック消去機能が支援される環境において、数５は数１０のように修正しなければならない。
【００７５】
【数１０】
2011530758.tif 000012
【００７６】
図６は、本発明の一実施形態に係るフラッシュメモリ制御方法において用いられるページ消去後複写演算方式を示した動作フローチャートである。
【００７７】
図６を参照すれば、本発明の一実施形態に係るページ消去後複写演算方式は、第１ブロックに存在する少なくとも１つの無効ページに記録された除去対象データを選択的に消去する（Ｓ６１０）。ここで、第１ブロックは、データブロックまたはログブロックのうちのいずれか１つであってもよい。
【００７８】
すなわち、ページ消去後複写演算方式は、ページ消去機能が支援される環境で適用され、消去されるページの数は１以上であってもよい。ただし、前記第１ブロックに存在する少なくとも１つの無効ページに記録された除去対象データを選択的に消去する時、前記第１ブロックに存在する少なくとも１つの有効ページに記録されたデータが消去されることが発生し得る。
【００７９】
このとき、本発明の一実施形態に係るページ消去後複写演算方式は、第３ブロックに存在する少なくとも１つのページに前記第１ブロックに存在する少なくとも１つの有効ページに記録されたデータを複写するステップをさらに含んでもよい（図６に図示せず）。
【００８０】
また、本発明の一実施形態に係るページ消去後複写演算方式は、前記除去対象データが消去された前記第１ブロックに存在する少なくとも１つの無効ページに第２ブロックに存在する少なくとも１つの有効ページに記録された有効データを複写する（Ｓ６２０）。
【００８１】
もし、前記第３ブロックに存在する少なくとも１つのページに第１ブロックの有効ページから複写されたデータが存在すれば、前記データは前記第１ブロックに存在するページに複写されてもよい。
【００８２】
また、本発明の一実施形態に係るページ消去後複写演算方式は、前記第２ブロックに存在する複数のページに記録されたデータを消去する（Ｓ６３０）。このとき、一般的にブロック単位に消去動作が行われるため、第２ブロックに存在する複数のページに対して同時に消去動作が行われてもよい。
【００８３】
これによって、第２ブロックは、初期化されることによって空いているブロックになり、再び第２ブロックにはデータがプログラムされる。
【００８４】
図７は、本発明の他の実施形態に係るフラッシュメモリ制御方法を示した動作フローチャートである。
【００８５】
図７を参照すれば、本発明の他の実施形態に係るフラッシュメモリ制御方法は、フラッシュメモリの複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能が支援される環境において、前記多重ブロック消去機能を考慮して使用可能なブロックリサイクル方式それぞれの費用を算出する（Ｓ７１０）。ここで、使用可能なブロックリサイクル方式は、前述したように併合演算方式、交換演算方式、複写後交換演算方式、移行演算方式、またはページ消去後複写演算方式を含んでもよい。
【００８６】
特に、使用可能なブロックリサイクル方式それぞれの費用を算出するステップ（Ｓ７１０）は、前記同時に消去される複数のブロックの数を考慮して前記使用可能なブロックリサイクル方式それぞれの費用を算出するステップであってもよい。
【００８７】
また、本発明の他の実施形態に係るフラッシュメモリ制御方法は、前記算出された費用に基づいて前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択する（Ｓ７２０）。このとき、前記使用可能なブロックリサイクル方式のうち最小の費用を有する少なくとも１つが選択されてもよい。
【００８８】
また、本発明の他の実施形態に係るフラッシュメモリ制御方法は、前記使用可能なブロックリサイクル方式のうち前記選択された少なくとも１つを用いて前記少なくとも１つのブロックを管理する（Ｓ７３０）。ここで、管理とは、選択された方式を用いてデータブロックまたはログブロックなどに対して「ブロックリサイクル」を行うことを意味する。
【００８９】
本発明に係るフラッシュメモリ制御方法は、多様なコンピュータ手段を介して実行することができるプログラム命令形態に具現され、コンピュータ読取可能な記録媒体に記録されることができる。前記コンピュータ読取可能な媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むこともできる。前記媒体に記録されるプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知であり使用可能なものであってもよい。コンピュータ読取可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスクおよび磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、フロプティカルディスクのような磁気−光媒体、およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれる。プログラム命令の例としては、コンパイラによって生成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行され得る高級言語コードを含む。前述したハードウェア装置は、本発明の動作を行うために１つ以上のソフトウェアモジュールとして作動するよう構成されることができ、その逆も同様である。
【００９０】
図８は、本発明の一実施形態に係るフラッシュメモリ制御装置を示すブロック図である。
【００９１】
図８を参照すれば、フラッシュメモリ制御装置は、フラッシュメモリ８１０、消去部８２０、管理部８３０、費用算出部８４０、および選択部８５０を含む。
【００９２】
フラッシュメモリ８１０は複数のブロックに構成され、複数のブロックはデータブロックまたはログブロックを含んでもよい。
【００９３】
また、消去部８２０は、フラッシュメモリ８１０の複数のブロックに格納されたデータを同時に消去する多重ブロック消去機能を支援する。すなわち、消去対象の複数のブロックは同時に消去されてもよい。前述したように、本発明は、多重ブロック消去機能を支援することによって１つのページを獲得するために求められる費用を減少させることができる。
【００９４】
また、管理部８３０は、前記多重ブロック消去機能が支援される環境において、使用可能なブロックリサイクル方式のうち少なくとも１つを用いて少なくとも１つのブロックを管理する。
【００９５】
すなわち、管理部８３０は無効ページのデータを適切に消去し、有効ページのデータを適切に収集して整理することによって、フラッシュメモリ８１０を構成するブロックの使用効率を向上させる。
【００９６】
また、費用算出部８４０は、前記多重ブロック消去機能を考慮して前記使用可能なブロックリサイクル方式それぞれの費用を算出する。
【００９７】
すなわち、前述したように本発明によって提案される費用モデルに応じて、費用算出部８４０は、前記同時に消去される複数のブロックの数を考慮して前記使用可能なブロックリサイクル方式それぞれの費用を算出することができる。
【００９８】
また、選択部８４０は、前記算出された費用に基づいて前記使用可能なブロックリサイクル方式のうち少なくとも１つを選択する。このとき、前記使用可能なブロックリサイクル方式のうち最小の費用を有する少なくとも１つが選択されてもよい。
【００９９】
以上のように、本発明は、たとえ限定された実施形態と図面によって説明したが、本発明は、上記の実施形態に限定されることなく、本発明が属する分野における通常の知識を有する者であれば、このような基材から多様な修正および変形が可能である。
【０１００】
したがって、本発明の範囲は説明された実施形態に限定されて決められてはならず、後述する特許請求の範囲だけでなく、この特許請求の範囲と均等なものなどによって定められなければならない。
【図１】
2011530758.tif 000013
【図２】
2011530758.tif 000014
【図３】
2011530758.tif 000015
【図４】
2011530758.tif 000016
【図５】
2011530758.tif 000017
【図６】
2011530758.tif 000018
【図７】
2011530758.tif 000019
【図８】
2011530758.tif 000020
【国際調査報告】
2011530758.tif 000021
2011530758.tif 000022