(57)【要約】【課題】  不揮発性メモリの性能を向上させることができ、論理ページと物理ページとの間のマッピング情報がなくても、演算が要求された論理ページが記録された物理ページのオフセットが分かる不揮発性メモリ管理方法及び装置を提供する。【解決手段】  少なくとも１つの物理ページを含む第１ブロック及び第２ブロックを含む不揮発性メモリ、及び前記第１ブロックで連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するかを判別した結果に応じて、前記第１ブロック及び前記第２ブロックの併合のための演算種類を決定する演算部を含む。【選択図】図１０
2008130088.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの物理ページを含む第１ブロック及び第２ブロックを含む不揮発性メモリと、
前記第１ブロックで連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するかを判別した結果に応じて、前記第１ブロック及び前記第２ブロックの併合のための演算種類を決定する演算部と、を含むことを特徴とする不揮発性メモリ管理装置。
【請求項２】
前記物理ページは、データが記録されるデータ領域と、前記オフセットが記録されるスペア領域と、を含むことを特徴とする請求項１に記載の不揮発性メモリ管理装置。
【請求項３】
前記演算部は、前記論理ページのオフセットが順次的に増加しなかったり、循環しない場合、前記第１ブロック及び前記第２ブロックで有効論理ページをデータが記録されていないフリーブロックにコピーする完全併合を行うことを特徴とする請求項１に記載の不揮発性メモリ管理装置。
【請求項４】
前記演算部は、前記有効論理ページのオフセットが順次的に増加しつつ循環するように、前記有効論理ページを前記フリーブロックにコピーすることを特徴とする請求項３に記載の不揮発性メモリ管理装置。
【請求項５】
前記演算部は、前記各論理ページのオフセットが順次的に増加しつつ循環し、前記第１ブロックで有効論理ページ数と前記第１ブロックの物理ページの総数とが一致しない場合、前記第２ブロックで有効論理ページを前記第１ブロックでデータが記録されていないフリーページにコピーするコピー併合を行うことを特徴とする請求項１に記載の不揮発性メモリ管理装置。
【請求項６】
前記演算部は、前記有効論理ページのオフセットが順次的に増加しつつ循環するように、前記有効論理ページを前記第１ブロックのフリーページにコピーすることを特徴とする請求項５に記載の不揮発性メモリ管理装置。
【請求項７】
前記演算部は、前記各論理ページのオフセットが順次的に増加しつつ循環し、前記第１ブロックで有効論理ページ数と前記第１ブロックに含まれた物理ページの総数とが一致する場合、前記第１ブロックを第３ブロックに移す交換併合を行うことを特徴とする請求項１に記載の不揮発性メモリ管理装置。
【請求項８】
連続した物理ページに記録されている論理ページのオフセットが順次的でかつ循環的に増加するブロックを少なくとも１つ以上含む不揮発性メモリと、
第１論理ページのオフセットとともに読み取り演算要求が入力される入力部と、
前記ブロックで前記第１論理ページのオフセットと同一のオフセットを有する第１物理ページにアクセスした後、前記第１物理ページから獲得した第２論理ページのオフセットに基づいて、前記第１論理ページのオフセットが記録された第２物理ページのオフセットを獲得する演算部と、を含むことを特徴とする不揮発性メモリ管理装置。
【請求項９】
前記物理ページは、データが記録されるデータ領域と、前記オフセットが記録されるスペア領域と、を含むことを特徴とする請求項８に記載の不揮発性メモリ管理装置。
【請求項１０】
前記第２物理ページのオフセットは、前記第１物理ページのオフセットから前記第２論理ページのオフセットを引いた値に、前記第１物理ページのオフセットと前記第１ブロックの総ページ数をそれぞれ足した結果値を、前記総ページ数で割ったときの余りであることを特徴とする請求項８に記載の不揮発性メモリ管理装置。
【請求項１１】
少なくとも１つの物理ページを含む第１ブロック及び第２ブロックを含む不揮発性メモリを管理する方法において、
前記第１ブロックで連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するかを判断するステップと、
前記判断結果に応じて、前記第１ブロック及び前記第２ブロックの併合のための演算種類を決定するステップと、を含むことを特徴とする不揮発性メモリ管理方法。
【請求項１２】
前記物理ページは、データが記録されるデータ領域と、前記オフセットが記録されるスペア領域と、を含むことを特徴とする請求項１１に記載の不揮発性メモリ管理方法。
【請求項１３】
前記決定するステップは、前記論理ページのオフセットが順次的に増加しなかったり、循環しない場合、前記第１ブロック及び前記第２ブロックで有効論理ページをデータが記録されていないフリーブロックにコピーするステップと、
前記第１ブロックと前記第２ブロックを対象に削除演算を行って新しいフリーブロックを生成するステップと、を含むことを特徴とする請求項１１に記載の不揮発性メモリ管理方法。
【請求項１４】
前記コピーするステップは、前記有効論理ページのオフセットが順次的に増加しつつ循環するように、前記有効論理ページを前記フリーブロックに順次的にコピーするステップを含むことを特徴とする請求項１３に記載の不揮発性メモリ管理方法。
【請求項１５】
前記決定するステップは、前記オフセットが順次的に増加しつつ循環し、前記第１ブロックで有効論理ページ数と前記第１ブロックの物理ページの総数とが一致しない場合、前記第２ブロックで有効論理ページを前記第１ブロックでデータが記録されていないフリーページにコピーするステップと、前記第２ブロックを対象に削除演算を行って新しいフリーブロックを生成するステップと、を含むことを特徴とする請求項１１に記載の不揮発性メモリ管理方法。
【請求項１６】
前記コピーするステップは、前記第２ブロックで有効論理ページのオフセットが順次的に増加しつつ循環するように、前記第２ブロックで有効論理ページを整列して前記フリーページにコピーするステップを含むことを特徴とする請求項１５に記載の不揮発性メモリ管理方法。
【請求項１７】
前記決定するステップは、前記オフセットが順次的に増加しつつ循環し、前記第１ブロックで有効論理ページ数と前記第１ブロックに含まれた物理ページの総数とが一致する場合、前記第１ブロックを第３ブロックに移すステップと、前記第２ブロックを対象に削除演算を行って新しいフリーブロックを生成するステップと、を含むことを特徴とする請求項１１に記載の不揮発性メモリ管理方法。
【請求項１８】
連続した物理ページに記録されている論理ページのオフセットが順次的でかつ循環的に増加するブロックを少なくとも１つ以上含む不揮発性メモリを管理する方法において、
第１論理ページのオフセットとともに読み取り演算要求が入力されるステップと、
前記ブロックで前記第１論理ページのオフセットと同一のオフセットを有する第１物理ページにアクセスするステップと、
前記第１物理ページから獲得した第２論理ページのオフセットに基づいて、前記第１論理ページのオフセットが記録された第２物理ページのオフセットを獲得するステップと、を含むことを特徴とする不揮発性メモリ管理方法。
【請求項１９】
前記物理ページは、データが記録されるデータ領域と、前記オフセットが記録されるスペア領域と、を含むことを特徴とする請求項１８に記載の不揮発性メモリ管理方法。
【請求項２０】
前記第２物理ページのオフセットは、前記第１物理ページのオフセットから前記第２論理ページのオフセットを引いた値に、前記第１物理ページのオフセットと前記第１ブロックの総ページ数をそれぞれ足した結果値を、前記総ページ数で割ったときの余りであることを特徴とする請求項１８に記載の不揮発性メモリ管理方法。
【請求項２１】
複数個の物理ページに対応する複数個の物理ページを含むフロックを含む不揮発性メモリを管理する方法において、
前記複数個の論理ページのオフセットが順次的に循環する場合、および前記複数個の論理ページのうち有効な論理ベー時の個数が前記ブロックが含まれる物理ページの総個数と一致する場合のうち少なくとも一つの場合において、交換併合、コピー併合および完全併合のうち何れか一つの併合演算を決定する段階および、
前記決定された併合演算によって併合された少なくとも一つ以上の前記ブロックに対して削除演算を行う段階を含む不揮発性メモリ管理方法。
【請求項２２】
前記複数個の論理ページのオフセットが順次的に循環し、前記有効な論理ページの個数が前記ブロックが含まれる物理ページの総個数と一致する場合、交換併合を行う段階をさらに含む請求項２１に記載の不揮発性メモリ管理方法。
【請求項２３】
前記複数個の論理ページのオフセットが順次的に循環し、前記有効な論理ページの個数が前記ブロックが含まれる物理ページの総個数と一致しない場合、コピー併合を行う段階をさらに含む請求項２１に記載の不揮発性メモリ管理方法。
【請求項２４】
前記複数個の論理ページのオフセットが順次的に循環せず、前記有効な論理ページの個数が前記ブロックを含む物理ページの総個数と一致しない場合、完全併合を行う段階をさらに含む請求項２１に記載の不揮発性メモリ管理方法。
【請求項２５】
前記併合演算は、ユーザが書き込み演算を要請した場合またはフリーブロックの個数が事前指定された個数未満の場合に遂行される請求項２１に記載の不揮発性メモリ管理方法。
【請求項２６】
前記複数個の論理ページのオフセットが順次的に減少し循環する場合、前記完全併合を行う段階をさらに含む請求項２１に記載の不揮発性メモリ管理方法。
【請求項２７】
前記複数個の論理ページのオフセットが前記複数個の物理ページのスペア領域に各々記録される  請求項２１に記載の不揮発性メモリ管理方法。
【請求項２８】
複数個の論理ページに対応する複数個の物理ページを含むブロックを含む不揮発性メモリ、および
前記複数個の論理ページのオフセットが順次的に循環する場合および前記複数個の論理ページのうち有効な論理ページの個数が前記ブロックが含まれる物理ページの総個数と一致する場合のうち少なくとも一つの場合において、交換併合、コピー併合および完全併合のうち何れか一つの併合演算を決定し、前記決定された併合演算によって非業された少なくとも一つ以上の前記ブロックに対して削除演算を行う演算部を含む不揮発性メモリ管理装置。
【請求項２９】
前記演算部は、
前記複数個の論理ページのオフセットが順次的に循環し、前期有効な論理ページの個数が前記ブロックが含まれる物理ページの総個数と一致する場合、交換併合を行う請求項２８に記載の不揮発性メモリ管理装置。
【請求項３０】
前記演算部は、
前記複数個の論理ページのオフセットが順次的に循環し、前記有効な論理ページの個数が前記ブロックが含まれる物理ページの総個数と一致しない場合、コピー併合を行う請求項２８に記載の不揮発性メモリ管理装置。
【請求項３１】
前記演算部は、
前記複数個の論理ページのオフセットが順次的に循環せず、前記有効な論理ページの個数が前記ブロックが含まれる物理ページの総個数と一致しない場合、完全併合を行う請求項２８に記載の不揮発性メモリ管理装置。
【請求項３２】
前記併合演算は、ユーザが書き込み演算を要請した場合、またはフリーブロックの個数が事前指定された個数未満の場合に遂行される請求項２８に記載の不揮発性メモリ管理装置。
【請求項３３】
前記複数個の論理ページのオフセットが順次的に減少しつつ循環する場合、前記完全併合を行う請求項２８に記載の不揮発性メモリ管理装置。
【請求項３４】
前記複数個の論理ページのオフセットは、前記複数個の物理ページのスペア領域に各々記録される請求項２８に記載の不揮発性メモリ管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不揮発性メモリに関し、より詳しくは不揮発性メモリの性能を向上させることができ、論理ページと物理ページとの間のマッピング情報がなくても要求された論理ページが記録された物理ページのオフセットが分かる不揮発性メモリ管理方法及び装置に関する。
【背景技術】
【０００２】
不揮発性メモリは、自由にデータの記録及び削除が可能なラム（ＲＡＭ：Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）の長所と電源供給がなくても格納しているデータを保存するロム（ＲＯＭ：Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）の長所をともに有しており、最近デジタルカメラ、ＰＤＡ、ＭＰ３プレーヤのような携帯用電子機器の格納媒体として広く使われている。
【０００３】
このような不揮発性メモリは、既存のＲＡＭや不揮発性格納装置、マグネティックなどと同様に特定位置に格納されたデータに任意にアクセスできるが、データを修正したり削除する方法においては、既存の格納装置と異なって、削除ブロック（Ｅｒａｓｅ  ｂｌｏｃｋ、以下「ブロック」という）を基本単位にしてアクセスが行われる。
【０００４】
すなわち、以前のデータを修正または削除しようとする場合、該当データを含むブロックを削除した後、データを再記録しなければならない。一例として、文字やアルファベットを１個ずつ修正する代わりに「削除」キーを押して全体単語をすべて削除した後、再修正するのである。
【０００５】
以下、使用する用語のうち物理的に連続したアドレスを有するバイトをセクタというが、セクタ（Ｓｅｃｔｏｒ）は不揮発性メモリに対する読み取り／書き込み演算の基本単位であり、複数のセクタで構成されるブロックは不揮発性メモリで１回の削除演算により消すことができる削除演算の基本単位である。
【０００６】
このような不揮発性メモリでは、記録前削除（ｅｒａｓｅ  ｂｅｆｏｒｅ  ｗｒｉｔｅ）によって不揮発性メモリに記録されたデータの物理アドレス（Ｐｈｙｓｉｃａｌ  Ａｄｄｒｅｓｓ）が変更されても、同一の論理アドレス（Ｌｏｇｉｃａｌ  Ａｄｄｒｅｓｓ）で不揮発性メモリに記録されたデータにアクセスできるように論理―物理マッピング（ｌｏｇｉｃａｌ−ｐｈｙｓｉｃａｌ）方法を支援する。
【０００７】
すなわち、マッピング方法は特定データに対する論理アドレスと物理アドレスとの間のマッピング情報を所定のマッピングテーブル（ｍａｐｐｉｎｇ  ｔａｂｌｅ）を介して管理するものであって、セクタマッピング方法、ブロックマッピング方法が例に挙げられる。
図１Ａは従来のセクタマッピング方法による不揮発性メモリアクセス方法を概略的に示す図面である。
【０００８】
図１Ａに示すように、セクタマッピング方法はマッピングテーブル１０に不揮発性メモリのセクタ単位でマッピング情報を保持して、論理セクタ情報を用いた不揮発性メモリの物理セクタアクセスを可能にするものである。
【０００９】
一例として、所定のデータに対して記録動作要求とともに論理セクタ番号（Ｌｏｇｉｃａｌ  Ｓｅｃｔｏｒ  Ｎｕｍｂｅｒ：ＬＳＮ）が９番に指定されれば、不揮発性メモリアクセス装置ではマッピングテーブル１０を参照してＬＳＮ９番に相応する物理セクタ番号（Ｐｈｙｓｉｃａｌ  Ｓｅｃｔｏｒ  Ｎｕｍｂｅｒ：ＰＳＮ）であるＰＳＮ６番を検索する。
【００１０】
次いで、不揮発性メモリの６番セクタに該当データを記録するが、該当セクタに他のデータが記録されていれば、不揮発性メモリの空いている物理セクタにデータを記録し、マッピングテーブル１０でＬＳＮ９番に相応するＰＳＮを変更させる。
【００１１】
図１Ｂは従来のブロックマッピング方法による不揮発性メモリアクセス方法を概略的に示す図面である。
図１Ｂに示すように、ブロックマッピング方法はマッピングテーブル１１不揮発性メモリのブロック単位でマッピング情報を保持して、論理セクタ情報を論理ブロック情報に変換させた後、論理ブロック情報とオフセット情報を用いた不揮発性メモリの物理セクタアクセスを可能にするものである。
【００１２】
一例として、４つのページが１つのブロックを構成する場合、所定のデータに対して記録動作要求とともにＬＳＮ９番に指定されれば、不揮発性メモリアクセス装置では論理セクタ番号９番の論理ブロック番号（Ｌｏｇｉｃａｌ  Ｂｌｏｃｋ  Ｎｕｍｂｅｒ：ＬＢＮ）９／４＝２を求めた後、マッピングテーブル１１を参照してＬＢＮに相応する物理ブロック番号（Ｐｈｙｓｉｃａｌ  Ｂｌｏｃｋ  Ｎｕｍｂｅｒ：ＰＢＮ）を求める。
【００１３】
このとき、論理ブロックのオフセットと物理ブロックのオフセットとを一致させて算出されたＰＢＮである１番でオフセット１に相応するセクタにデータを記録する。
【００１４】
該当セクタに他のデータが記録されていれば、オフセットを一致させて、不揮発性メモリの空いている物理セクタにデータを記録し、マッピングテーブル１１でＬＢＮ２番に相応するＰＢＮを変更させる。
【００１５】
このような従来のマッピング方法のうちセクタマッピング方法は不揮発性メモリのセクタ単位でマッピング情報を保持するためのマッピング情報が多すぎて実際不揮発性メモリに応用するには難しいという問題点があった。
【００１６】
このような従来技術の問題点を補完するために、多くのマッピング情報を必要としないブロックマッピング方法が使用されている。
【００１７】
特許文献１では、一部ブロックに対してのみマッピング情報を提供し、他のブロックに対しては併合演算を行って論理ページのオフセットと物理ページのオフセットとを一致させることによって、マッピング情報がなくても論理ページが記録された物理ページのオフセットが分かる方法を開示している。
【００１８】
前記技術によれば、コピー併合（ｃｏｐｙ  ｍｅｒｇｅ）演算よりは完全併合（ｆｕｌｌ  ｍｅｒｇｅ）演算が頻繁に要求されるが、前記完全併合演算が行われるためには１つのブロックに対する削除演算及び複数のページに対する書き込み演算が要求される。しかし、このような頻繁な削除／書き込み演算は不揮発性メモリの性能を低下させる原因になる。
【００１９】
従って、完全併合演算の回数を減らすことによって、不揮発性メモリシステムの性能を向上させることができる不揮発性メモリ管理方法及び装置が要求される。
【特許文献１】韓国公開特許第２００２−００９２４８７号公報
【発明の開示】
【発明が解決しようとする課題】
【００２０】
本発明は、不揮発性メモリの管理において、完全併合演算が行われる回数を減らすことによって、不揮発性メモリの性能を向上させることができる方法及び装置を提供するのにその目的がある。
【００２１】
しかし、本発明の目的は以上で言及した目的に制限されず、言及していないさらなる目的は下記により当業者に明確に理解できる。
【課題を解決するための手段】
【００２２】
前記目的を達成するために、本発明の実施形態による不揮発性メモリ管理装置は、少なくとも１つの物理ページを含む第１ブロック及び第２ブロックを含む不揮発性メモリ、及び前記第１ブロックで連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するかを判別した結果に応じて、前記第１ブロック及び前記第２ブロックの併合のための演算種類を決定する演算部を含む。
【００２３】
前記目的を達成するために、本発明の実施形態による不揮発性メモリ管理装置は、連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するブロックを少なくとも１つ以上含む不揮発性メモリ、第１論理ページのオフセットとともに読み取り演算要求が入力される入力部、及び前記ブロックで前記第１論理ページのオフセットと同一のオフセットを有する第１物理ページにアクセスした後、前記第１物理ページから獲得した第２論理ページのオフセットに基づいて、前記第１論理ページのオフセットが記録された第２物理ページのオフセットを獲得する演算部を含む。
【００２４】
また、前記目的を達成するために、本発明の実施形態による不揮発性メモリ管理方法は少なくとも１つの物理ページを含む第１ブロック及び第２ブロックを含む不揮発性メモリを管理する方法において、前記第１ブロックで連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するかを判断するステップ、及び前記判断結果に応じて前記第１ブロック及び前記第２ブロックの併合のための演算種類を決定するステップを含む。
【００２５】
さらに、前記目的を達成するために、本発明の実施形態による不揮発性メモリ管理方法は、連続した物理ページに記録されている論理ページのオフセットが順次的に増加しつつ循環するブロックを少なくとも１つ以上含む不揮発性メモリを管理する方法において、第１論理ページのオフセットとともに読み取り演算要求が入力されるステップ、前記ブロックで前記第１論理ページのオフセットと同一のオフセットを有する第１物理ページにアクセスするステップ、及び前記第１物理ページから獲得した第２論理ページのオフセットに基づいて、前記第１論理ページのオフセットが記録された第２物理ページのオフセットを獲得するステップを含む。
【００２６】
また、前記目的を達成するために、本発明の実施形態による不揮発性メモリ管理方法は、複数個の論理ページに対応する複数個の物理ページを含むブロックを含む不揮発性メモリの管理方法において、前記複数個の論理ページのオフセットが順次的に増加しつつ循環する場合、および前記複数個の論理ページのうち、有効な論理ページの個数が前記ブロックが含む物理ページの総個数と一致する場合のうち、少なくても一の場合において、交換併合、複写併合および完全併合のうち何れか一つの併合演算を決定する段階、および前記決定された併合演算によって併合された少なくとも一つ以上の前記ブロックに対して削除演算を行う段階を含む。
【００２７】
また、前記目的を達成するために、本発明の実施形態による不揮発性メモリ管理装置は、  複数個の論理ページに対応する複数個の物理ページを含むブロックを含む不揮発性メモリ、および前記複数個の論理ページのオフセットを順次的に増加しつつ循環する場合、および前記複数個の論理ページのうち有効な論理ページの個数が前記ブロックが含む物理ページの総個数と一致する場合のうち、少なくても一の場合において、交換併合、複写併合および完全併合のうち何れか一つの併合演算を決定し、前期決定された併合演算によって併合された少なくとも一つ以上の前記ブロックに対して削除演算を行う演算部を含む。
【発明の効果】
【００２８】
前記のような本発明による不揮発性メモリ管理方法及び装置によれば次のような効果が１つあるいはそれ以上ある。
【００２９】
ブロックに含まれる論理ページを整列するとき、論理ページのオフセットが順次的に増加しつつ循環するようにすることによって、完全併合演算が行われる回数を減らすことができ、これによって不揮発性メモリの書き込み演算の速度を向上させることができる効果がある。
【００３０】
物理ページのスペア領域に前記物理ページに記録された論理ページのオフセットを記録することによって、物理ページと論理ページとの間のマッピングが情報なくても要求された論理ページが記録された物理ページのオフセットが分かる。
【発明を実施するための最良の形態】
【００３１】
その他、実施形態の具体的な事項は詳細な説明及び図面に含まれている。
本発明の利点及び特徴、そしてそれらを達成する方法は添付する図面とともに詳細に後述する実施形態を参照すれば明確になる。しかし、本発明は以下に開示される実施形態に限定されず、相異なる多様な形態によって具現でき、単に本実施形態は本発明の開示を完全なものにし、本発明の属する技術分野における通常の知識を有する者に発明の範疇を完全に知らせるために提供するものであって、本発明は請求項の範疇によってのみ定義される。明細書全体にわたって同じ参照符号は同じ構成要素を示す。
【００３２】
以下、添付するブロック図または処理フローチャートに関する図面を参考して本発明の実施形態による不揮発性メモリ管理方法及び装置について説明する。この場合、処理フローチャートの各ブロックとフローチャートの組み合せは、コンピュータプログラムインストラクションによって行われることが理解できる。
【００３３】
これらコンピュータプログラムインストラクションは、汎用コンピュータ、特殊用コンピュータまたはその他プログラム可能なデータプロセシング装備のプロセッサに搭載できるので、コンピュータまたはその他プログラム可能なデータプロセシング装備のプロセッサによって行われるインストラクションはフローチャートブロックで説明する機能を行う手段を生成する。
【００３４】
これらコンピュータプログラムインストラクションは、特定方式で機能を具現するために、コンピュータまたはその他プログラム可能なデータプロセシング装備が備えられるコンピュータによって利用可能または読取可能なメモリに格納できるので、そのコンピュータによって利用可能または読取可能なメモリに格納したインストラクションは、フローチャートブロックで説明する機能を行うインストラクション手段を含む製造品目の生産に用いることができる。また、コンピュータプログラムインストラクションは、コンピュータまたはその他プログラム可能なデータプロセシング装備上に搭載できるので、コンピュータまたはその他プログラム可能なデータプロセシング装備上で一連の動作ステップが行われ、コンピュータで実行されるプロセスを生成してコンピュータまたはその他プログラム可能なデータプロセシング装備の機能を行うインストラクションは、フローチャートブロックで説明する各ステップの機能を実行することもできる。
【００３５】
また、各ブロックは特定した論理的機能を実行するための１つ以上の実行可能なインストラクションを含むモジュール、セグメントまたはコードの一部を表すことができる。また、複数の代替実行例ではブロックで言及した機能が順序から外れて行われ得ることに注目しなければならない。例えば、連続して図示している２つのブロックは、実質的に同時に行われることも可能であり、またはそのブロックが場合によって該当する機能に応じて逆順に行われることも可能である。
【００３６】
図２は本発明の実施形態による不揮発性メモリ管理装置２０の構造を示す図面である。
図示のように、本発明の実施形態による不揮発性メモリ管理装置２０は入力部１００と格納部２００と演算部４００と不揮発性メモリ３００を含んで構成され得る。
【００３７】
入力部１００はユーザから所定の論理ページに対する読み取り／書き込み要求などが入力される。
演算部４００は論理的アドレスに対する書き込み／読み取り要求を物理的アドレスに対する書き込み／読み取り要求に変換する。すなわち、演算部４００はユーザが要求した論理ページに対する要求を不揮発性メモリ３００上の物理的アドレスに変換して書き込み／読み取り演算を行う。
【００３８】
格納部２００は演算部４００が不揮発性メモリ３００にアクセスするのに必要なアクセスコードを格納する。例えば、格納部２００はユーザにより要求された論理的アドレスと不揮発性メモリ３００上の物理的アドレスとの間のマッピング関係を示すマッピングテーブル（未図示）を格納する。このような格納部２００はＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）またはフラッシュメモリ（Ｆｌａｓｈ  ｍｅｍｏｒｙ）など外部メモリを含み得る。
【００３９】
不揮発性メモリ３００はユーザが記録しようとするデータを格納する。不揮発性メモリ３００の構造についてより詳しく説明するために図３を参照する。
【００４０】
図３は図２に示した不揮発性メモリ３００の構造を示す図面である。図３に示すように、不揮発性メモリ３００は複数のページ３２０を含む複数のブロック３１０を含む。
【００４１】
ページは読み取り／書き込み演算の基本単位であって、各ページはデータ領域３３０とスペア領域３４０に区分できる。このとき、データ領域３３０にはデータが格納され、スペア領域３４０には該当物理ページに記録された論理ページのオフセットが記録される。
【００４２】
ブロックは削除演算の基本単位であって、大きくデータブロック、ログブロック及びフリーブロックに区分できる。ここでフリーブロックとは、データが記録されていないブロック、すなわち、空いているブロックを意味する。そしてデータブロックとは、一般データを格納するブロックを意味する。これに対して、ログブロックとは、データブロックに記録されたデータのうち特定部分を修正しようとする場合に割り当てられて、修正内容を記録する用途に活用されるブロックを意味する。従って、ログブロックは図４のように、ただ１つのデータブロックに対応され、対応されるデータブロックの修正されたページを格納する。このため、ログブロックのページはデータブロックのページより優先的に参照できる。以下の説明では、ログブロックで優先的に参照されるページを「有効ページ」といい、物理的に有効データが記録されていても有効ページによってその内容が無視されるページを「無効ページ」という。
【００４３】
図５を参照すれば、前述した不揮発性メモリ３００は論理的に大きくマップ領域５１０、データブロック領域５３０、ログブロック領域５２０及びフリーブロック領域５４０に区分できる。前記マップ領域５１０はアドレス変換情報を格納する。そして、データブロック領域５３０は複数のデータブロックを含み、ログブロック領域５２０は複数のログブロックを含む。フリーブロック領域５４０はデータブロックまたはログブロックに割り当てられるための複数のフリーブロックを含む。図５に示す各領域は不揮発性メモリ３００の論理的な分割を示すものであって、各領域に含まれるデータブロック、ログブロック及びフリーブロックは物理的に互いに連続して存在することもでき、不連続に散在して存在することもできる。
【００４４】
一方、本発明によれば、不揮発性メモリ３００を管理するために「ブロック併合（ｂｌｏｃｋ  ｍｅｒｇｅ）」が行われ得る。ブロック併合とは、データブロックの有効ページ及びログブロックの有効ページを収集して新しいデータブロックを生成し、既存のログブロック及び既存のデータブロックを対象に削除演算を行うことによって、フリーブロックを作り出すことをいう。ブロック併合はログブロックに書き込み可能なフリーページがそれ以上存在しない場合に行うことができる。
【００４５】
ブロック併合の種類には交換併合、コピー併合及び完全併合が例に挙げられるが、ブロック併合が行われるときは、ブロック併合の対象になるブロックの状態に応じて３つのうちいずれか１つが行われ得る。
【００４６】
交換併合は図６のように、ログブロック６１０で連続した物理ページに記録された論理ページのオフセットが順次的に増加しつつ循環し、ログブロック６１０で有効論理ページ数と前記ログブロック６１０に含まれた物理ページの総数とが一致する場合に行われる。交換併合はログブロック６１０をデータブロック６２０に移してアドレス変換情報を更新した後、既存のデータブロック６３０に記録されたデータを削除することによって行われる。すなわち、交換併合ではデータブロック６３０やログブロック６１０に記録されているデータをコピーする過程なくアドレス変換情報のみを更新することによって行われる。このとき、既存のデータブロック６３０は削除可能なブロック（ｅｒａｓａｂｌｅ  ｂｌｏｃｋ）になる。
【００４７】
コピー併合は図７のように、ログブロック７１０で連続した物理ページに記録された論理ページのオフセットが順次的に増加しつつ循環し、ログブロック７１０で有効ページ数とログブロック７１０に含まれた物理ページの総数とが一致しない場合に行われる。コピー併合はデータブロック７００で有効論理ページをログブロックのフリーページにコピーした後、ログブロック７１０を新たなデータブロック（未図示）に移すことによって行われる。このとき、既存のデータブロックは削除可能なブロックになる。
【００４８】
完全併合は図８のように、ログブロック８１０で連続した物理ページに記録された論理ページのオフセットが順次的に増加しなかったり、循環しない場合に行われる。完全併合はフリーブロック８２０が割り当てられた後、ログブロック８１０及び既存のデータブロック８００で有効論理ページが割り当てられたフリーブロック８２０にコピーすることによって行われる。このとき、既存のデータブロック８００と既存のログブロック８１０は削除可能なブロックになる。
【００４９】
次に、図９ないし図１２を参照して、本発明の実施形態による不揮発性メモリ管理方法を説明する。
図９は本発明の実施形態による書き込み演算過程を示すフローチャートである。
【００５０】
ユーザから第１論理ページのオフセットとともに書き込み演算が要求されれば、演算部４００はマッピング情報を参照して、第１論理ページのオフセットに対応する物理ページのオフセットを検索する。次いで、検索された物理ページが使用可能な状態であるかを判断する（Ｓ８１０）。
【００５１】
前記判断結果、該当物理ページが使用可能であれば（Ｓ８１０、はい）、演算部４００は該当物理ページにデータを記録する（Ｓ８６０）。このとき、データは該当ページのデータ領域に記録できる。データ領域にデータが記録されるとき、該当物理ページのスペア領域には第１論理ページのオフセットが記録されるのが好ましい。データの書き込みが完了すれば、演算部４００はマップ領域のマッピング情報を更新する。
【００５２】
前記判断結果、該当物理ページが使用不可であれば（Ｓ８１０、いいえ）、すなわち該当物理ページに既にデータ記録されている状態であれば、演算部４００はフリーページの割り当てが可能であるかを判断する（Ｓ８２０）。
【００５３】
判断結果、フリーページの割り当てが可能であれば（Ｓ８２０、はい）、演算部４００はフリーページを割り当て、割り当てられたフリーページのデータ領域にデータを記録する（Ｓ８６５）と同時に前記フリーページのスペア領域には第１論理ページのオフセットを記録する（Ｓ８６５）。
【００５４】
判断結果、フリーページの割り当てが不可であれば（Ｓ８２０、いいえ）、演算部４００はログブロックの割り当てが可能であるかを判断する（Ｓ８３０）。すなわち、残っているフリーブロック数が十分であるかを判断する。
【００５５】
判断結果、残っているフリーブロック数が十分で新しいログブロックの割り当てが可能であれば（Ｓ８３０、はい）、演算部４００はフリーブロックのうち所定のフリーブロックをログブロックに割り当てる（Ｓ８５０）。そして、割り当てられたログブロックの物理ページにデータを記録する（Ｓ８６０）。このとき、演算部４００は該当物理ページのデータ領域にはデータを記録し、前記物理ページのスペア領域には第１論理ページのオフセットを記録するのが好ましい。データ書き込みが完了すれば、演算部４００はマップ領域のマッピング情報を更新する（Ｓ８７０）。
【００５６】
判断結果、残っているフリーブロック数が不十分で新しいログブロックの割り当てが不可であれば（Ｓ８３０、いいえ）、演算部４００は併合演算を行って新しいフリーブロックを生成し（Ｓ８４０）、前記フリーブロックをログブロックに割り当てる（Ｓ８５０）。そして割り当てられたログブロックの物理ページに書き込みを行った後、演算部４００はマップ領域のマッピング情報を更新する（Ｓ８７０）。
【００５７】
以上、図９を参照して、ユーザから書き込み演算が要求された場合、フリーブロックを生成するための方法の１つとして併合演算が行われるのを説明したが、併合演算は不揮発性メモリのブロック状態が予め指定された基準を満たす場合に自動的に行われ得る。例えば、ユーザから書き込みが要求された場合でなくても、フリーブロック数が予め指定された数未満になる場合に行われ得る。
【００５８】
図１０は本発明の実施形態による併合演算過程を示すフローチャートである。
先ず、演算部４００は併合対象になるログブロックの論理ページ整列状態を確認する。具体的に、前記ログブロックで連続した物理ページのスペア領域を確認し、前記スペア領域に記録されている論理ページのオフセットが順次的に増加しつつ循環しているかを判断する（Ｓ９０１）。ここで順次的に増加しつつ循環するというのは、論理ページのオフセットが順次的に増加すると同時に、オフセットが最大である論理ページとオフセットが最少である論理ページとが互いに連続して存在するのを意味する。
【００５９】
前記Ｓ９０１ステップでの判断結果、図８のように、ログブロックで連続した物理ページに記録された論理ページのオフセットが順次的に増加しなかったり、循環しない場合（Ｓ９０１、いいえ）、演算部４００は該当ログブロックを対象に完全併合を行う。完全併合を行うために演算部４００には先ず新しいフリーブロックが割り当てられる（Ｓ９０８）。次いで、ログブロック及びデータブロックで有効論理ページを前記フリーブロックにコピーする（Ｓ９０９）。このとき、演算部４００は前記有効論理ページをオフセットに応じて順次的に前記フリーブロックにコピーすることによって、前記有効論理ページをすべて前記フリーブロックにコピーしたとき、前記論理ページのオフセットが順次的に増加しつつ循環できるようにする。ログブロック及びデータブロックで有効論理ページがすべて前記フリーブロックにコピーされれば、演算部４００は前記フリーブロックをデータブロックに移した後（Ｓ９１０）、マッピング情報を更新する（Ｓ９１１）。そして、以前のデータブロック及びログブロックを対象に削除演算を行って新しいフリーブロックを生成する（Ｓ９１２）。
【００６０】
一方、前記Ｓ９０１ステップでの判断結果、ログブロックで連続した物理ページに記録された論理ページのオフセットが順次的に増加しつつ循環する場合（Ｓ９０１、はい）、演算部４００は該当ログブロックで有効論理ページ数と該当ログブロックに含まれた物理ページの総数とが一致するかを判断する（Ｓ９０２）。
【００６１】
前記Ｓ９０２ステップでの判断結果、図７のように、該当ログブロックで有効論理ページ数と物理ページの総数とが互いに一致しない場合（Ｓ９０２、いいえ）、演算部４００はコピー併合を行う。コピー併合を行うために演算部４００は先ずログブロックに対応するデータブロックで有効論理ページを前記ログブロックのフリーページに記録する（Ｓ９０３）。このとき、演算部４００は前記有効論理ページを論理ページのオフセットに応じて順次的にログブロックにコピーすることによって、コピー過程が完了した後、前記ログブロックの状態を確認したとき、論理ページのオフセットが順次的に増加しつつ循環できるようにする。コピー過程が完了すれば、演算部４００はログブロックをデータブロックに移し（Ｓ９０４）、マッピング情報を更新する（Ｓ９０５）。次いで、演算部４００は以前のデータブロックに対して削除演算を行うことによって、新しいフリーブロックを生成する（Ｓ９０６）。
【００６２】
前記Ｓ９０２ステップでの判断結果、図６のように、ログブロックで有効論理ページ数と物理ページの総数とが互いに一致する場合（Ｓ９０２、はい）、演算部４００は交換併合を行う。具体的に、演算部４００は該当ログブロックをデータブロックに移した後（Ｓ９０４）、マッピング情報を更新する（Ｓ９０５）。この後、演算部４００は以前のデータブロックに対して削除演算を行うことによって、新しいフリーブロックを生成する（Ｓ９０６）。
【００６３】
次に、図１１は本発明の実施形態による読み取り演算過程を示すフローチャートである。
ユーザから第１論理ページのオフセットとともに読み取り演算が要求されれば、演算部４００は前記第１論理ページのオフセット（以下「第１オフセット」という）と同一のオフセットを有する第１物理ページにアクセスする（Ｓ１０）。
【００６４】
次いで、演算部４００は前記第１物理ページのスペア領域を確認して第２論理ページのオフセット（以下「第２オフセット」という）を獲得する（Ｓ２０）。
【００６５】
この後、演算部４００は前記第２論理ページのオフセットに基づいて前記第１論理ページが記録された第２物理ページのオフセットを獲得する（Ｓ３０）。具体的に、第１オフセットをＸ、第２オフセットをＹ、第１オフセットと第２オフセットの差をＺとし、ブロックに含まれる物理ページの総数をＮとするとき、演算部４００は下記数式１に基づいて第２物理ページのオフセットＸ’を求める。
Ｘ’＝（Ｘ＋Ｚ＋Ｎ）  ｍｏｄ  Ｎ                 （１）
すなわち、演算部４００は第１オフセットと第２オフセットの差Ｚに、第１オフセットＸとブロックに含まれる物理ページの総数Ｎが各々足された結果値を前記物理ページの総個数Ｎで割ったときの余りを求めることによって、第２物理ページのオフセットＸ’を獲得する。
【００６６】
数式（１）によって第２物理ページのオフセットＸ’が獲得されれば、演算部４００は第２物理ページを読み取る（Ｓ４０）。
【００６７】
ここで、図１２を参照して読み取り演算過程について説明する。図１２は本発明の実施形態によるブロックを示す図面である。図１２に示すブロック１２００は総８つの物理ページ（ページ０〜７）を含むことが分かる。そして、各物理ページのスペア領域に論理ページのオフセットが記録されていることが分かる。また、各スペア領域に記録されている論理ページのオフセットは順次的に増加しつつ循環するのが分かる（ページ４に記録された論理ページのオフセットは７であり、ページ５に記録された論理ページのオフセットは０であるため、論理ページのオフセットが循環しているのが分かる）。
【００６８】
このような状態で、オフセットが７である第１論理ページに対する読み取り要求が入力されれば、演算部４００は先ず第１論理ページのオフセットと同一のオフセットを有する第１物理ページにアクセスする。具体的に、第１論理ページのオフセットは７であるため、演算部４００は７というオフセットを有する第１物理ページ、すなわちページ７にアクセスする。
【００６９】
次いで、演算部４００はページ７のスペア領域を確認し、第２論理ページのオフセットＹすなわち２を獲得する。
【００７０】
この後、演算部４００はページ７のスペア領域に記録されている第２論理ページのオフセットＹに基づいて、第１論理ページが記録された第２物理ページのオフセット  Ｘ’を求める。具体的に、演算部４００は数式１に基づいて第２物理ページのオフセット  Ｘ’を求める。図１２の場合、第２物理ページのオフセットＸ’＝（７＋５＋８）  ｍｏｄ  ８＝４であることが分かる。
【００７１】
第２物理ページのオフセットＸ’が獲得されれば、演算部４００は該当ブロック１２００でオフセットが４である物理ページ、すなわち５番目ページを読み取る。図１２において５番目ページであるページ４のスペア領域をみれば、論理ぺージのアドレスとして７が記憶されていることが分かる。
【００７２】
以上のように、本発明による不揮発性メモリ管理方法及び装置を図面を参照して説明したが、本発明は本明細書に開示する実施形態と図面に限定されず、その発明の技術思想の範囲内で当業者によって多様な変形が可能であることは言うまでもない。
【図面の簡単な説明】
【００７３】
【図１Ａ】従来技術によるページマッピング方法を示す図である。
【図１Ｂ】従来技術によるブロックマッピング方法を示す図である。
【図２】本発明の実施形態によるフラッシュメモリ管理装置を示す図である。
【図３】図２に示した不揮発性メモリの構造を示す図である。
【図４】図２に示した不揮発性メモリのデータブロックとログブロックとの間の関係を示す図である。
【図５】図２に示した不揮発性メモリの領域分割を示す図である。
【図６】本発明の実施形態による併合演算のうち交換併合を示す図である。
【図７】本発明の実施形態による併合演算のうちコピー併合を示す図である。
【図８】本発明の実施形態による併合演算のうち完全併合を示す図である。
【図９】本発明の実施形態による書き込み演算過程を示すフローチャートである。
【図１０】本発明の実施形態による併合演算過程を示すフローチャートである。
【図１１】本発明の実施形態による読み取り演算過程を示すフローチャートである。
【図１２】本発明の実施形態による併合演算が行われたブロックを例示する図である。
【符号の説明】
【００７４】
１００      入力部
２００      格納部
３００      不揮発性メモリ
４００      演算部
【図１Ａ】
2008130088.tif 000003
【図１Ｂ】
2008130088.tif 000004
【図２】
2008130088.tif 000005
【図３】
2008130088.tif 000006
【図４】
2008130088.tif 000007
【図５】
2008130088.tif 000008
【図６】
2008130088.tif 000009
【図７】
2008130088.tif 000010
【図８】
2008130088.tif 000011
【図９】
2008130088.tif 000012
【図１０】
2008130088.tif 000013
【図１１】
2008130088.tif 000014
【図１２】
2008130088.tif 000015