JP2012033002A

JP2012033002A - メモリ管理装置およびメモリ管理方法

Info

Publication number: JP2012033002A
Application number: JP2010172050A
Authority: JP
Inventors: Masanori Miyagawa; 雅紀宮川; Atsushi Kunimatsu; 敦国松; Tsutomu Owa; 勤大輪; Reina Nishino; 玲奈西野
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2010-07-30
Filing date: 2010-07-30
Publication date: 2012-02-16
Also published as: CN102346712A; US20120030413A1; KR101270281B1; KR20120012375A

Abstract

【課題】フラグメンテーションの発生を抑制でき、メモリの有効利用に有利なメモリ管理装置およびメモリ管理方法を提供する。
【解決手段】実施形態によれば、不揮発性半導体メモリ６１〜６ｎと揮発性半導体メモリ５とを備えるメインメモリ６５を管理するメモリ管理装置３であって、前記不揮発性半導体メモリへのデータ書き込み動作の際に、書き込み対象のデータについて、該データのデータ属性により決定される書き込み頻度についての情報２２に基づき、前記不揮発性半導体メモリ上の書き込み領域の振り分けを行う振り分け部７８と、前記振り分けられたデータを、追記方式により前記不揮発性半導体メモリに書き込む制御部７７とを具備することを特徴とするメモリ管理装置。
【選択図】図２

Description

メモリ管理装置およびメモリ管理方法に関する。

例えば、不揮発性半導体メモリと揮発性半導体メモリとをメインメモリとして用いる場合には、データ属性に応じて、データの配置領域を不揮発性半導体メモリとするか、または揮発性半導体メモリとするか決定する方法が提案されている（例えば、特許文献１参照）。不揮発性半導体メモリの一例としては、例えば、ＮＡＮＤ型フラッシュメモリ等が提案されている。揮発性半導体メモリの一例としては、例えば、ＤＲＡＭ（Dynamic Random Access Memory）等が提案されている。

ここで、ＮＡＮＤ型フラッシュメモリ等の不揮発性半導体メモリへのデータ書き込み動作には、「上書き方式」と「追記方式」とが存在する。

「上書き方式」とは、上書き不可能なＮＡＮＤ型フラッシュメモリを疑似的に上書き可能に見せる方式である。この方式では、消去ブロックの任意の位置のデータが更新された場合、その消去ブロックから全てのデータを一旦退避してブロックに消去処理を施してから、再度ブロック単位で更新されたデータを書き込む必要がある。

一方、「追記方式」では、ページ単位のデータ書き込みを行う。この方式では、データが更新された場合、そのデータが存在するブロックページにマーク（無効データ）を付け、更新されたデータは別ブロック（同一ブロックでも可能）の別ページに配置される。

特開２００８−２４２９４４号公報

フラグメンテーションの発生を抑制でき、メモリの有効利用に有利なメモリ管理装置およびメモリ管理方法を提供する。

一態様に係るメモリ管理装置は、不揮発性半導体メモリと揮発性半導体メモリとを備えるメインメモリを管理するメモリ管理装置であって、前記不揮発性半導体メモリへのデータ書き込み動作の際に、書き込み対象のデータについて、該データのデータ属性により決定される書き込み頻度についての情報に基づき、前記不揮発性半導体メモリ上の書き込み領域の振り分けを行う振り分け部と、前記振り分けられたデータを、追記方式により前記不揮発性半導体メモリに書き込む制御部とを具備する。

実施形態に係る情報処理装置の全体構成例を示すシステムブロック図。図１中の処理部におけるブロック選択部を示すブロック図。本実施形態に係るカラーリングテーブルの構成例を示す図。実施形態に係るメモリ管理装置のデータ書き込み動作を示すフロー図。実施形態に係るメモリ管理装置のガーベジコレクション動作を示すフロー図。実施形態に係るデータ書き込み動作後の物理ブロック（ＰＥＢ）を示す図。実施形態に係る更新頻度が高いデータを更新後の物理ブロック（ＰＥＢ）を示す図。比較例に係る上書き方式によるデータ書き込み動作後の物理ブロック（ＰＥＢ）を示す図。比較例に係る上書き方式による更新頻度が高いデータを更新後の物理ブロック（ＰＥＢ）を示す図。本実施形態および比較例におけるダーティ（dirty）領域サイズを示す図。

以下、この発明の実施形態について図面を参照して説明する。尚、この説明においては、全図にわたり共通の部分には共通の参照符号を付す。

［実施形態］
＜１．構成例＞
１−１．全体構成例
まず、図１を用い、この実施形態に係る情報処理装置の全体構成例について説明する。図１は、本実施形態に係る情報処理装置１の構成の一例を示すシステムブロック図である。

図示するように、情報処理装置１は、例えばＳｏＣ（System-on-a-Chip）で構成される。情報処理装置１は、プロセッサＰ１〜Ｐ４、２次キャッシュメモリＬ２、バス２、メモリ管理装置３を備える。

プロセッサＰ１〜Ｐ４は、それぞれが１次キャッシュメモリＬ１−１〜Ｌ１−４、ＭＭＵ４１〜４４を具備する。プロセッサＰ１〜Ｐ４としては、例えばＣＰＵ（Central Processing Unit）が用いられるが、ＭＰＵ（Micro Processor Unit）、ＧＰＵ（Graphic Processor Unit）などのような他の処理ユニットが用いられてもよい。この図１において、プロセッサＰ１〜Ｐ４の数は４つであるが、プロセッサの数は１以上であればよい。

プロセッサＰ１〜Ｐ４は、２次キャッシュメモリＬ２を共有し、バス２を介して、メモリ管理装置３と電気的に接続される。

メモリ管理装置３は、外部の揮発性半導体メモリ５、不揮発性半導体メモリ６１〜６ｎと電気的に接続されている。プロセッサＰ１〜Ｐ４は、メモリ管理装置３を介して、揮発性半導体メモリ５、不揮発性半導体メモリ６１〜６ｎにアクセス可能である。

プロセッサＰ１〜Ｐ４とメモリ管理装置３とは、バス２によってデータを送受信可能に接続されている。また、例えば、プロセッサＰ１〜Ｐ４とメモリ管理装置３とは、非同期に動作可能であり、プロセッサＰ１〜Ｐ４で処理実行中に、メモリ管理装置３が不揮発性半導体メモリ６１〜６ｎに対してウェアレベリング、ガーベージコレクション、コンパクションを実行することができる。

なお、本実施の形態において、情報処理装置１と、揮発性半導体メモリ５及び不揮発性半導体メモリ６１〜６ｎとは、別チップとされているが、情報処理装置１内に、揮発性半導体メモリ５及び不揮発性半導体メモリ６１〜６ｎが含まれる構成としてもよい。

メモリ管理装置３の内部には、処理部７が備えられている。この処理部７としては、例えばＭＰＵが用いられるが、他の処理ユニットが用いられるとしてもよい。

処理部７は、不揮発性半導体メモリ６１〜６ｎを使用するための種々の処理を、ソフトウェア８に基づいて制御する。本実施形態において、プロセッサＰ１〜Ｐ４と処理部７とで、不揮発性半導体メモリ６１〜６ｎに対する処理を分担して実行するとしてもよい。例えば、ソフトウェア８は、不揮発性半導体メモリ６１〜６ｎに記憶されており、起動時に処理部７によって不揮発性半導体メモリ６１〜６ｎから読み出され、実行される。

揮発性半導体メモリ５と不揮発性半導体メモリ６１〜６ｎは、メインメモリとして使用される。本実施形態では、不揮発性半導体メモリ６１〜６ｎに、十分なメモリ量が確保される。不揮発性半導体メモリ６１〜６ｎのメモリ容量は、揮発性半導体メモリ５よりも大きい。そして、揮発性半導体メモリ５には、例えば、最近アクセスされたデータ、使用頻度の高いデータなどのアクセスされる可能性の高いデータが不揮発性半導体メモリ６１〜６ｎからキャッシュされる。プロセッサＰ１〜Ｐ４が揮発性半導体メモリ５にアクセスする場合に、揮発性半導体メモリ５にアクセス対象のデータが存在しない場合、不揮発性半導体メモリ６１〜６ｎと揮発性半導体メモリ５と間でデータ転送が実行される。このように、揮発性半導体メモリ５と不揮発性半導体メモリ６１〜６ｎとを組み合わせて使用することで、揮発性半導体メモリ５のメモリ容量より大きいメモリ空間がメインメモリとして使用可能となる。

本実施の形態において揮発性半導体メモリ５は、例えば、ＤＲＡＭ（Dynamic Random Access Memory）であるとする。しかしながら、揮発性半導体メモリ５としては、ＤＲＡＭに代えて、ＦＰＭ−ＤＲＡＭ（Fast Page Mode）、ＥＤＯ−ＤＲＡＭ（Extended Data Out DRAM）、ＳＤＲＡＭ（Synchronous DRAM）などのような、コンピュータにおいてメインメモリとして利用されるメモリを用いるとしてもよい。また、ＤＲＡＭ程度の高速ランダムアクセスが可能であり、アクセス可能上限回数に実質的な制限がないのであれば、揮発性半導体メモリ５に代えて、ＭＲＡＭ（Magnetoresistive Random Access Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）などの不揮発性ランダムアクセスメモリが用いられるとしてもよい。

本実施の形態において不揮発性半導体メモリ６１〜６ｎは、例えば、ＮＡＮＤ型フラッシュメモリであるとする。しかしながら、不揮発性半導体メモリ６１〜６ｎは、例えばＮＯＲ型フラッシュメモリなど、他の不揮発性半導体メモリが用いられるとしてもよい。

揮発性半導体メモリ５は、不揮発性半導体メモリ６１〜６ｎよりも小容量（例えば１２８Mbyte〜４GByteなど)だが高速にアクセス可能である。

不揮発性半導体メモリ６１〜６ｎは、揮発性半導体メモリ５よりも大容量(例えば３２GByte〜５１２GByteなど)だがアクセス時間が長い。また、不揮発性半導体メモリ６１〜６ｎは、データの書き込みにおいて、一旦データを消去し、書き込む必要がある。不揮発性半導体メモリ６１〜６ｎは、最大の書き込み回数(例えば１万回や３万回など)に制限があり、その回数を超えると、エラー率が上昇し、デバイスとして正しいデータ書き込みの保証できなくなる場合がある。また、本例の場合、不揮発性半導体メモリ６１〜６ｎに対して、「追記方式」により、データ書き込み動作を行う。

ここで、「追記方式」は、ページ単位でデータ書き込みを行う。この追記方式で、データが更新された場合、そのデータが存在するブロックページにマーク（無効データ）を付け、更新されたデータは別ブロック（同一ブロックでも可能）の別ページに配置される。換言すれば、このような無効データとなった領域を、ダーティ（Dirty）領域（無効データ領域）と称する。

ダーティ（Dirty）領域が増大すると、後述するガーベジコレクション動作がより必要なるため、フラグメンテーションが発生する。換言すると、フラグメンテーションはDirty領域の増加で有効領域が減る現象である。このようなフラグメンテーションが発生するため、ガーベジコレクションを行う。

情報処理装置１では、プロセッサＰ１〜Ｐ４により、ＯＳ９及びアプリケーションなどのソフトウェア１０が実行される。

プロセッサＰ１〜Ｐ４により、情報処理装置１におけるＯＳ９及びアプリケーションなどのソフトウェア１０が実行される。

ＯＳ９及びソフトウェア１０は、例えば、１次キャッシュメモリＬ１−１〜Ｌ１−４、２次キャッシュメモリＬ２、揮発性半導体メモリ５、不揮発性半導体メモリ６１〜６ｎに記憶されており、情報処理装置１の動作時に、プロセッサＰ１〜Ｐ４により読み出される。

不揮発性半導体メモリ６１〜６ｎの物理アドレス空間分のアクセス頻度情報は、ＯＳ９及びソフトウェア１０によって利用され、テーブル形式で、カラーリングテーブルによりカラーリング情報として管理される。ここで、アクセス頻度情報とは、ページサイズ単位のアクセス頻度を表す。ＯＳ９は、例えば、プログラム自身が持つ特徴、プログラムのtxt領域、stack領域、heap領域、data領域に配置されたデータの区別に基づいてアクセス頻度情報を決定し、カラーリングテーブルを用いて管理する。詳細については、後述する。

１−２．ブロック選択部の構成例
次に、図２を用い、この実施形態に係るメモリ管理装置３が有するブロック選択部の構成例について説明する。

図示するように、本例の場合、ブロック選択部（処理部）７７は、メモリ管理装置３中の処理部（ＭＰＵ）７に配置されている。しかし、この例に限らず、ブロック選択部７７は、ＮＡＮＤフラッシュメモリ６１〜６ｎの図示しないメモリコントローラ上に実装されても良いし、ＭＴＤ（Memory Technology Device）用のＦＳ（File System）（例えば、ＮＡＮＤ型フラッシュメモリ用のファイルシステム）上等に実装されても勿論良い。

ブロック選択部７７は、データ振り分け部７８，ライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ），およびＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）を備え、後述するカラーリングテーブルを元にデータのＮＡＮＤフラッシュメモリ６１〜６ｎ上の書き込み先物理ブロックを選定する。

データ振り分け部７８は、ＮＡＮＤフラッシュメモリ６１〜６ｎへのデータ書き込み動作の際に、書き込み対象のデータについて、該データのデータ属性により決定される書き込み頻度についての情報に基づき、ＮＡＮＤフラッシュメモリ６１〜６ｎ上の書き込み領域の振り分けを行い、データの更新頻度および消去頻度を示す変数に対応して配置されたライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）を選択する。データの更新頻度および消去頻度は、カラーリングテーブルを元に作成される。詳細については、後述する。また、データ振り分け部７８は、ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）についても同様に選択する。詳細については、後述する。

ライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）は、カラーリングテーブルにより算出された更新頻度を表す変数（０〜ｎの範囲）に対応して、ｎ個分だけ配置される。換言すると、各ライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）は、更新頻度を表す変数に対応する。本例の場合、更新頻度を表す変数に対応して、５つのライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）が配置される例を示す。

ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）についても、上記ライトバッファと同様に、カラーリングテーブルに基づいて算出された更新頻度を表す変数に対応して、複数（本例では、３つ）個分配置される。

ブロック選択部７７は、上記構成において、追記方式により、任意のタイミング（ＭＰＵにタスクが割り振られていない時）で、ライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）およびＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）の内容を論理ブロック（ＬＥＢ）に、データの非同期書き込みを行う。尚、ライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）およびＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）の内容を論理ブロック（ＬＥＢ）へ書き込もうとする際、論理ブロック（ＬＥＢ）に空き領域がない場合、各ライトバッファに対応する論理ブロックを交換する。詳細については、後述する動作フローにより詳説する。

１−３．カラーリングテーブルの構成例
次に、図３を用い、この実施形態に係るカラーリングテーブルの構成例の構成例について説明する。カラーリングテーブル２２は、例えば、メインメモリとして用いられる揮発性メモリ５や不揮発性メモリ６１〜６ｎ等に配置されるものである。なお、カラーリングテーブル２２は、例えば、メモリ管理装置３に設けられたＲＡＭ（図示せず）に保持されてもよい。

図示するように、本実施形態に係るカラーリングテーブル２２は、プロセッサＰ１〜Ｐ４の物理アドレス（不揮発性半導体メモリ及び揮発性半導体メモリの論理アドレス）を基に作成されたインデックス毎にカラーリング情報が付与される。ここで、プロセッサＰ１〜Ｐ４は、プロセッサＰ１〜Ｐ４の論理アドレスを、プロセッサＰ１〜Ｐ４の物理アドレス（不揮発性半導体メモリ及び揮発性半導体メモリの論理アドレス）に変換し、メモリ管理装置３に送信する。

カラーリング情報が付与されるデータのデータサイズ単位は、例えば、読み出し、書き込みの最小の単位である。例えば、読み出し、書き込みの最小の単位は、ＮＡＮＤ型フラッシュメモリ６１〜６ｎのページサイズである。以下において、カラーリングテーブル２２によりカラーリング情報が対応付けられるデータのデータサイズはページサイズであるとして説明するが、これに限定されるものではない。カラーリングテーブル２２は、データ毎にカラーリング情報を対応付け、エントリ単位でカラーリング情報を格納する。カラーリングテーブル２２の各エントリには、インデックスが付されている。インデックスとは、データの論理アドレスを基に生成される値である。

例えば、上記メモリ管理装置３，ブロック選択部７７，データ振り分け部７８等は、データを指定する論理アドレスが与えられると、論理アドレスに対応するインデックスにより管理されているエントリを参照してカラーリングテーブル２２中における、データのカラーリング情報を取得する。そして、このカラーリング情報に基づいて、揮発性メモリ（ＤＲＡＭ）５、不揮発性メモリ（多値メモリ（ＭＬＣ：Multi Level Cell），２値メモリ（ＳＬＣ：Single Level Cell））６１〜６ｎの配置を決定する。さらに、上記不揮発性メモリ（多値メモリ（ＭＬＣ：Multi Level Cell），２値メモリ（ＳＬＣ：Single Level Cell））６１〜６ｎ内それぞれで、本例に係るデータ振り分けを行う。詳細については、後述する。

カラーリング情報は、各データのメインメモリ６４上の配置領域を決定する基準として用いられる情報であり、静的カラー情報と、動的カラー情報とを含む。静的カラー情報は、カラーリング情報が付与される当該データの特性（データ属性）に基づいて生成される情報であり、当該データの不揮発性メモリ６１〜６ｎ等におけるデータ配置（書き込み）領域を決定するヒントとなる情報である。動的カラー情報は、データの読み出しと書き込みの回数と頻度の少なくとも一方を含む情報である。

静的カラー情報は、当該データの重要度、静的書き込み頻度を示す値SW_color、静的読み出し頻度を示すSR_color、データ寿命SL_color、データの生成された時刻ST_colorを含む。

重要度とは、データの種類等に基づいて、当該データの重要性を推測して設定される値である。重要度は、例えば、ファイルシステムに保持されるファイルの特性、またはプログラムに一次的に使用される領域の特性により推測される。

静的書き込み頻度SW_colorとは、データの種類等に基づいて、当該データが書き込まれる頻度を推測して設定される値である。例えば、静的書き込み頻度SW_colorは、書き込み頻度が高いと推測されるデータほど、高い値が設定される。本例の場合、上記データ振り分け部７８は、カラーリングテーブル２２中の静的書き込み頻度SW_colorを更新頻度を表す変数として参照し、この変数に基づいてライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）にデータの振り分けを行う。これに限られず、データ振り分け部７８は、静的書き込み頻度SW_colorを更新頻度を表す変数に近似して段階を減らした変数を用い、データ振り分けを行っても良い。

静的読み出し頻度SR_colorとは、データの種類等に基づいて、当該データが読み出される頻度を推測して設定される値である。例えば、静的読み出し頻度SR_colorは、読み出し頻度が高いと推測されるデータほど、高い値が設定される。

データ寿命SL_colorとは、データの種類等に基づいて、当該データが消去されずにデータとして使用される期間（データの寿命）を推測して設定される値である。

静的カラー情報は、データを生成するプログラム（プロセス）により、静的に、予め決められた値である。また、ゲストＯＳが、データのファイル拡張子またはファイルヘッダ等に基づいて、静的カラー情報を予測してもよい。

動的カラー情報は、データの書き込み回数DWC_color、データの読み出し回数DRC_colorを含む。

データの書き込み回数DWC_colorとは、当該データが不揮発性メモリ６１〜６ｎに書き込まれた回数である。

データの読み出し回数DRC_colorとは、当該データが不揮発性メモリ６１〜６ｎから読み出された回数である。メモリ管理装置３は、データの書き込み回数DWC_colorにより、データ毎に、当該データが不揮発性メモリ６１〜６ｎに書き込まれた回数を管理する。データ読み出し回数DRC_colorにより、メモリ管理装置３は、データ毎に、当該データが不揮発性メモリ６１〜６ｎから読み出された回数を管理する。前述のように、不揮発性メモリ６１〜６ｎは、メインメモリとして用いられる。このため、プロセッサＰ１〜Ｐ４で処理されるデータは、不揮発性メモリ６１〜６ｎに書き込まれ、不揮発性メモリ６１〜６ｎから読み出される。

メモリ管理装置３は、データが書き込まれる度に、当該データの書き込み回数DWC_colorをインクリメントする。また、メモリ管理装置３は、データが読み出される度に、当該データの読み出し回数DRC_colorをインクリメントする。

上記のように、データの更新頻度はカラーリングテーブル２２から算出される。なお、本実施形態において、「更新頻度」とは、プロセッサＰ１〜Ｐ４等によりデータが変更（更新）される頻度を意味する。

さらに、本実施形態では、後述するガーベジコレクション動作の際に、カラーリングテーブル２２中の、データの書き込み回数DWC_colorおよびデータ読み出し回数DRC_colorを参照することにより、不揮発性メモリ６１〜６ｎのデータ書き込み、およびデータ読み出しが記録された時刻を参照し、ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）のデータ振り分けを行う。そのため、ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）にて使用する最終アクセス時刻が、カラーリングテーブル２２中の、データの書き込み回数DWC_colorおよびデータ読み出し回数DRC_colorに加えられる。上記最終アクセス時刻には、最後にデータ書き込み、およびデータ読み出しが行われた時刻が記録される。

＜２．データ書き込み動作＞
２−１．データ書き込み動作フロー
次に、図４に沿って、本実施形態に係る情報処理装置のデータ書き込み動作について説明する。

（ステップＳＴ１１）
図示するように、まず、ステップＳＴ１１の際、ブロック選択部７７中のデータ振り分け部７８は、上記図３に示したカラーリングテーブル２２を参照する。より具体的には、本例の場合、データ振り分け部７８は、カラーリングテーブル２２中の静的書き込み頻度SW_colorを更新頻度を表す変数として参照する。

（ステップＳＴ１２）
続いて、ステップＳＴ１２の際、データ振り分け部７８は、参照したカラーリングテーブル２２に基づき、更新頻度を表す変数を算出する。より具体的には、データ振り分け部７８は、参照した上記静的書き込み頻度SW_colorに基づき、更新頻度を表す変数（本例の場合、変数：０〜４）を算出する。しかしながら、本例の場合に限られず、データ振り分け部７８は、静的書き込み頻度SW_colorを更新頻度を表す変数に近似して段階を減らした変数を算出しても良い。例えば、上記静的書き込み頻度SW_colorを更新頻度を表す変数に近似して段階を減らした変数とは、４つの第１〜第４ライトバッファが配置され、変数が０〜７となった場合に、変数０〜１を第１ライトバッファ、変数２〜３を第２ライトバッファ、変数４〜５を第３ライトバッファ、変数６〜７を第４ライトバッファにそれぞれ段階を減らした変数を言う。

（ステップＳＴ１３）
続いて、ステップＳＴ１３の際、データ振り分け部７８は、上記ステップＳＴ１２において算出した更新頻度を表す変数に基づいて、この変数に対応するライトバッファを決定する。
本例の場合、データ振り分け部７８は、上記ステップＳＴ１２において算出された更新頻度を表す変数（０〜４）に基づいて、変数（０〜４）に対応するライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）を決定する。更新頻度を表す変数（０〜４）は、本例の場合、順次変数が大きくなるほど更新頻度が低くなる、とする。そのため、変数（０〜４）に対応するライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）は、順次更新頻度が低くなる。即ち、本例の場合では、ライトバッファＡ（ＬＡ）に、最も更新頻度が高いデータが振り分けられる。

（ステップＳＴ１４）
続いて、ステップＳＴ１４の際、ブロック選択部７７は、ライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）に対応する、論理ブロック（ＬＥＢ）の空き領域が十分か否か、について判定する。

（ステップＳＴ１５）
続いて、ステップＳＴ１５の際、ブロック選択部７７は、上記ステップＳＴ１４の際に論理ブロック（ＬＥＢ）の空き領域が十分でない（Ｎｏ）と判定された場合、対応する論理ブロック（ＬＥＢ）を変更し、再び上記ステップＳＴ１４に戻る。

（ステップＳＴ１６）
続いて、ステップＳＴ１６の際、ブロック選択部７７は、上記ステップＳＴ１４の際に論理ブロック（ＬＥＢ）の空き領域が十分である（Ｙｅｓ）と判定された場合、「追記方式」により、論理ブロック（ＬＥＢ）にライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）に振り分けられたデータの書き込み指示を行う（Ｅｎｄ）。

尚、続いて、論理ブロック（ＬＥＢ）に追記方式にて書き込まれたデータは、図示しない論理物理変換テーブルが参照されることにより、不揮発性メモリ６１〜６ｎの対応する物理アドレスの物理ブロックに、同様の「追記方式」により書き込まれる。

以上のように、書き込み対象のデータについて、書き込み対象のデータのデータ属性により決定される書き込み頻度についての情報に基づき、不揮発性半導体メモリ６１〜６ｎ上の書き込み領域を振り分ける。

２−２．ガーベジコレクション動作フロー
次に、図５に沿って、本実施形態に係る情報処理装置のガーベジコレクション動作について説明する。

本実施形態では、データのガーベジコレクション（ＧＣ：Garbage collection）についても、上記カラーリングテーブル２２を用いてデータ振り分けを行い、追記方式にてデータ書き込みを行う。ここで、「追記方式」で書き込まれたデータが更新された場合、そのデータが存在するブロックページにマーク（無効データ）を付け、更新されたデータは別ブロック（同一ブロックでも可能）の別ページに配置される。換言すれば、このような無効データとなった領域は、ダーティ（Dirty）領域となる。そこで、論理ブロック（ＬＥＢ）中のダーティ（Dirty）領域が増加した場合、ガーベジコレクションにより、無効データとなっていない有効データを、他の論理ブロック（ＬＥＢ）へ追記方式で書き込むように指示し、移動させる。この結果、Dirty領域が増えている論理ブロック（ＬＥＢ）を消去対象とし、Dirty領域が増えている論理ブロックを再利用可能とする処理である。ガーベジコレクション動作により、不揮発性メモリ６１〜６ｎの有効利用な領域が増加するので、フラグメンテーションを更に改善することができる。
本例の場合、このガーベジコレクション動作は、メモリ管理装置３中の処理部（ＭＰＵ）７が、アイドル状態の際に起動するものである。
（ステップＳＴ２１）
図示するように、まず、ステップＳＴ２１の際、ブロック選択部７７中のデータ振り分け部７８は、情報処理装置システム１の全体のDrity領域が、閾値以上か否かを判定する。情報処理装置システム１の全体のDrity領域が、閾値以上でないと判定された場合（Ｎｏ）、ガーベジコレクション動作は必要でないと判定され、この動作を終了する（Ｅｎｄ）。この際の閾値は、必要に応じて変更可能なものである。より具体的には、データ振り分け部７８は、例えば、不揮発性メモリ６１〜６ｎの全体のうちDrity領域が、５０パーセント以上か否かにより判定する。

（ステップＳＴ２２）
続いて、ステップＳＴ２２の際、上記ステップＳＴ２１において情報処理装置システム１の全体のDrity領域が閾値以上であると判定された場合（Ｙｅｓ）、データ振り分け部７８は、メインメモリ中のDirty領域の論理ブロック（ＬＥＢ）を検索する。より具体的には、データ振り分け部７８は、例えば、データが存在する論理ブロックのリストを不揮発性メモリ６１〜６ｎ上に確保し、このリストのエントリに対応する論理ブロックを線形に探索する。

（ステップＳＴ２３）
続いて、ステップＳＴ２３の際、データ振り分け部７８は、カラーリングテーブル２２を参照することにより、ガーベジコレクション対象のデータの最終アクセス時刻を参照する。より具体的には、カラーリングテーブル２２中の、データの書き込み回数DWC_colorおよびデータ読み出し回数DRC_colorを参照することにより、ガーベジコレクション対象のデータのデータ書き込み、およびデータ読み出しが記録された時刻を参照する。

（ステップＳＴ２４）
続いて、ステップＳＴ２４の際、データ振り分け部７８は、上記ステップＳＴ２３の際に参照した最終アクセス時刻により、更新可能性を予測する。より具体的には、本例の場合、参照した最終アクセス時刻により、３つの更新可能性（大，中，小）を予測する。
例えば、このステップＳＴ２４の際における本例の場合の上記３つの更新可能性は、以下のように判定される。
＜更新可能性の予測方法例＞
最終更新時刻が１日以上前の場合：更新可能性小
最終更新時刻が１２時間以上前の場合：更新可能性中
それ以外の場合：更新可能性大
（ステップＳＴ２５）
続いて、ステップＳＴ２５の際、データ振り分け部７８は、上記ステップＳＴ２３の際に更新可能性”大”と予測された場合には、ＧＣ用ライトバッファＡ（ＬＡ）を選択する。

（ステップＳＴ２６）
続いて、ステップＳＴ２６の際、データ振り分け部７８は、上記ステップＳＴ２３の際に更新可能性”中”と予測された場合には、ＧＣ用ライトバッファＢ（ＬＢ）を選択する。

（ステップＳＴ２７）
続いて、ステップＳＴ２７の際、データ振り分け部７８は、上記ステップＳＴ２３の際に更新可能性”小”と予測された場合には、ＧＣ用ライトバッファＣ（ＬＣ）を選択する。

（ステップＳＴ２８）
続いて、ステップＳＴ２８の際、ブロック選択部７７は、ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）に対応する論理ブロック（ＬＥＢ）の空き領域が十分か否かを判定する。

（ステップＳＴ２９）
続いて、ステップＳＴ２９の際、ブロック選択部７７は、上記ステップＳＴ２８においてＧＣ用ライトバッファＡ〜Ｃに対応する論理ブロック（ＬＥＢ）の空き領域が十分でないと判定された場合（Ｎｏ）、対応する論理ブロック（ＬＥＢ）を変更する。

（ステップＳＴ３０）
続いて、ステップＳＴ３０の際、ブロック選択部７７は、上記ステップＳＴ２８においてＧＣ用ライトバッファＡ〜Ｃに対応する論理ブロック（ＬＥＢ）の空き領域が十分あると判定された場合（Ｙｅｓ）、同様に、追記方式により、論理ブロック（ＬＥＢ）にＧＣ用ライトバッファＡ〜Ｃに振り分けられたデータの書き込みを行って、この動作を終了する（Ｅｎｄ）。

尚、続いて、論理ブロック（ＬＥＢ）に追記方式にて書き込まれたデータは、図示しないメモリコントローラにより、論理物理変換テーブルを参照することにより、不揮発性メモリ６１〜６ｎの対応する物理アドレスの物理ブロックに、同様の追記方式により書き込まれる。

上記のように、本実施形態では、ガーベジコレクション動作の際に、カラーリングテーブル２２を参照することにより、最後にアクセスされた時刻から、今後アクセスされる可能性を予測した上で、移動先の論理ブロック（ＬＥＢ）を決定することができる。最後にアクセスされた時刻が最近なものほど、今後更新される可能性が高いと判断することができるからである。そのため、上記本例に係る追記方式のデータ書き動作に加えた、このガーベジコレクション動作によって、不揮発性メモリ６１〜６ｎの有効利用な領域が増加するので、フラグメンテーションを更に改善することができる。
＜３．作用効果＞
本実施形態に係るメモリ管理装置およびメモリ管理方法によれば、少なくとも下記（１）乃至（２）の効果が得られる。

（１）フラグメンテーションの発生を抑制でき、メモリの有効利用に有利である。

上記のように、本例に係るメモリ管理装置３は、データ書き込み動作の際に、データ振り分け部７８が、カラーリングテーブル２２を参照することによるデータの属性から、データの更新頻度を予測し、変数に基づいて、この変数に対応するライトバッファを決定する（ＳＴ１３）。尚、変数に対応するライトバッファを決定する際には、データの更新頻度に限らず、データの消去頻度等でも良い。

本例の場合、データ振り分け部７８は、上記ステップＳＴ１２において算出された更新頻度を表す変数（０〜４）に基づいて、変数（０〜４）に対応するライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）を決定する。更新頻度を表す変数（０〜４）は、本例の場合、順次変数が大きくなるほど更新頻度が低くなるとする。そのため、変数（０〜４）に対応するライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）は、順次更新頻度が低くなる。即ち、本例の場合では、ライトバッファＡ（ＬＡ）が、最も更新頻度が高いデータが振り分けられる。

さらに、メモリ管理装置３は、「追記方式」により、論理ブロック（ＬＥＢ）にライトバッファＡ〜Ｅ（ＬＡ〜ＬＥ）に振り分けられたデータの書き込みを行う（ＳＴ１６）。

その結果、不揮発性メモリ６１〜６ｎには、対応する物理アドレスの物理ブロック（ＰＥＢ）に、同様の追記方式により、更新頻度に応じたデータがブロックごとに集合して書き込まれる。

例えば、本例に係る追記方式によるデータ書き込み後の物理ブロック（ＰＥＢ）は、図６のように示される。

図示するように、物理ブロック１（ＰＥＢ１）には、更新頻度が低いデータＢ１〜Ｂ３が、物理アドレスＰＡＡ００〜ＰＡＡ１１にそれぞれ書き込まれている。

物理ブロック２（ＰＥＢ２）には、更新頻度が低いデータＢ４が、物理アドレスＰＡＡ００に書き込まれている。

物理ブロック３（ＰＥＢ３）は、空き物理ブロックである。

物理ブロック４（ＰＥＢ４）には、更新頻度がより高いデータＡ１〜Ａ３が、物理アドレスＰＡＡ００〜ＰＡＡ１１にそれぞれ書き込まれている。

物理ブロック５（ＰＥＢ５）には、更新頻度がより高いデータＡ４が、物理アドレスＰＡＡ００に書き込まれている。

このように、本例に係る追記方式のデータ書き込み動作によれば、更新頻度に応じてデータを不揮発性メモリ６１〜６ｎの物理ブロック（ＰＥＢ）ごとに振り分けることができる。

加えて、本例に係るメモリ管理装置３は、ガーベジコレクション動作の際においても、カラーリングテーブル２２を用いてデータ振り分けを行い（ＳＴ２４）、追記方式にてデータ書き込みを行う（ＳＴ３０）。

上記ステップＳＴ２４の際のカラーリングテーブル２２を用いてデータ振り分けは、参照した最終アクセス時刻により、更新可能性を予測することにより行われる。より具体的には、本例の場合、参照した最終アクセス時刻により、以下の３つの更新可能性（大，中，小）を予測し、ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）にそれぞれ振り分けられる。

その結果、例えば、本例に係るデータＡ（更新頻度が高い）を更新した後の物理ブロック（ＰＥＢ）は、図７のように示される。

図示するように、まず、更新頻度が高いデータＡ１〜Ａ４が固めて振り分けられた物理ブロック４（ＰＥＢ４）および物理ブロック５（ＰＥＢ５）では、データＡ１〜Ａ４が更新されるため、データＡ１〜Ａ４がデータＢ１〜Ｂ４よりもまず先に、別の物理ブロック（ここでは図示せず）に移動される。

続いて、更新頻度が低いデータＢ１〜Ｂ４が固めて振り分けられた物理ブロック１（ＰＥＢ１）および物理ブロック２（ＰＥＢ２）では、データＢ１〜Ｂ４が更新されるため、データＢ１〜Ｂ４がデータＡ１〜Ａ４に続いて、別の物理ブロックに移動される（ここでは図示せず）。

このように、追記方式において、更新頻度に応じて振り分けられたデータが、物理ブロックごとに固まって書き込まれるため、Dirty領域の発生を抑制でき、フラグメンテーションの発生を防止できる。

［比較例］
一方、比較例として、追記方式において、本例のような上記データ属性に基づきデータ振り分けを行わない場合のデータ書き込み後の物理ブロック（ＰＥＢ）は、例えば、図８のように示される。

図示するように、比較例では、更新頻度ごとにデータが振り分けられず、データが物理ブロックに書き込まれる。

そのため、例えば、物理ブロック１（ＰＥＢ１）には、更新頻度が低いデータＢ１，Ｂ２および更新頻度が高いデータＡ１が、物理アドレスＰＡＡ００〜ＰＡＡ１１にランダムに書き込まれている。

物理ブロック２（ＰＥＢ２）には、更新頻度が低いデータＢ３，Ｂ４および更新頻度が高いデータＡ２が、物理アドレスＰＡＡ００等にランダムに書き込まれている。

物理ブロック３（ＰＥＢ３）には、更新頻度が高いデータＡ１のみが、物理アドレスＰＡＡ００に書き込まれている。

物理ブロック４（ＰＥＢ４）には、更新頻度が高いデータＡ４のみが、物理アドレスＰＡＡ１１にランダムに書き込まれている。

物理ブロック５（ＰＥＢ５）は、空き物理ブロックである。

このように、比較例に係るデータ書き込み動作によれば、更新頻度にデータが振り分けられず、物理ブロック（ＰＥＢ）にデータが書き込まれている。

その結果、その後、物理ブロック（ＰＥＢ）にランダム書き込まれたデータは、更新頻度ごとに別のブロックに移動されるため、更新ごとにランダムなDirty領域が発生する。

例えば、比較例に係るデータＡ（更新頻度が高い）を更新した後の物理ブロック（ＰＥＢ）は、図９のように示される。

図示するように、まず、更新頻度が高いデータＡ１〜Ａ４が書き込まれた物理ブロック１〜４（ＰＥＢ１〜ＰＥＢ４）において更新されるため、データＡ１〜Ａ４がデータＢ１〜Ｂ４よりもまず先に、別の物理ブロック（ここでは図示せず）に移動される。
そのため、Dirty領域が増大し、フラグメンテーションが発生する点で不利である。

例えば、図示する比較例では、更新頻度が高いデータＡ１〜Ａ４が更新されると、物理ブロック１，２（ＰＥＢ１，２）中には、２つのDirty領域が増大するため、フラグメンテーションが発生する。このような場合は、続くデータＢ１〜Ｂ４の更新の場合でも同様に発生し得る。

（２）書込み効率（ＷＡ）および情報処理装置１のシステム全体の性能を向上できる。

上記のように、本例に係るメモリ管理装置３は、ガーベジコレクション動作の際においても、カラーリングテーブル２２を用いてデータ振り分けを行い（ＳＴ２４）、追記方式にてデータ書き込みを行う（ＳＴ３０）。

＜更新可能性の予測方法例＞
最終更新時刻が１日以上前の場合：更新可能性小
最終更新時刻が１２時間以上前の場合：更新可能性中
それ以外の場合：更新可能性大
ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）に振り分けられたデータは、上記と同様に、追記方式により不揮発性メモリ６１〜６ｎの物理ブロック（ＰＥＢ）に書き込まれる。

そのため、上記データ書き込み動作に加え、無効データが多い物理ブロック中の有効データを他の物理ブロックに移動し、無効データが多い物理ブロックを消去可能とし、不揮発性メモリ６１〜６ｎ中の有効領域を増やすことができる点で有利である。

ここで、ガーベジコレクションが多くなりすぎることは、書込み効率（ＷＡ：Write Amplification）の向上の観点からは、望ましくない。ガーベジコレクションが増大すると、不揮発性メモリ（ＮＡＮＤ型フラッシュメモリ）６１〜６ｎの特性や、システムの実装方式によって発生する書き込みの増分が必要となるため、書込み効率（ＷＡ）が低減するからである。加えて、ガーベジコレクションが多発すると、ガーベジコレクション処理についてＭＭＵ４１〜ＭＭＵ４４を多く使用する必要があり、情報処理装置１のシステム全体の性能劣化につながる。

例えば、上記図９に示した比較例の場合では、上書き方式により、物理ブロック（ＰＥＢ）にデータが書き込まれるため、物理ブロック１，２（ＰＥＢ１、２）に２つのDirty領域が発生する。その結果、Dirty領域の発生のたびに、ガーベジコレクション動作が必要となり、書込み効率（ＷＡ）が低減し、情報処理装置１のシステム全体の性能が劣化する点で、不利である。

これに対して本例では、上記図７に示したように、ＧＣ用ライトバッファＡ〜Ｃ（ＧＣＬＡ〜ＧＣＬＣ）に振り分けられたデータは、追記方式により不揮発性メモリ６１〜６ｎの物理ブロック（ＰＥＢ）に書き込まれるため、Dirty領域の発生を抑制できるから、ガーベジコレクション動作が多くなることもない。その結果、書込み効率（ＷＡ）を向上でき、情報処理装置１のシステム全体の性能を向上できる点で、有利である。

より具体的に、本例および比較例における、Dirty領域サイズは、例えば、図１０のように示される。図１０では、時間（１／１０分）とデータ量（Ｂｙｔｅ）との関係において、実線は本例（上記フラグメンテーション抑制有）の場合を示し、破線は比較例（上記フラグメンテーション抑制無）の場合を示している。ここで、図１０中、time 7［１／１０分］近傍において、いずれもダーティ領域のデータ量が小さくなっているのは、有効データが消去されると、一時的にDirty領域が解放される場合があるからである。

図示するように、いずれの時間（１〜１５［１／１０分］）においても、本例の方が、比較例に比べ、Dirty領域のデータ量を大きく低減できていることは明らかである。

以上、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

３…メモリ管理装置、７…処理部、７７…ブロック選択部、７８…データ振り分け部、ＬＡ〜ＬＥ…ライトバッファ、ＧＣＬＡ〜ＧＣＬＥ…ＧＣ用ライトバッファ、６５…メインメモリ、６１〜６ｎ…不揮発性メモリ、５…揮発性メモリ。

Claims

不揮発性半導体メモリと揮発性半導体メモリとを備えるメインメモリを管理するメモリ管理装置であって、
前記不揮発性半導体メモリへのデータ書き込み動作の際に、書き込み対象のデータについて、該データのデータ属性により決定される書き込み頻度についての情報に基づき、前記不揮発性半導体メモリ上の書き込み領域の振り分けを行う振り分け部と、
前記振り分けられたデータを、追記方式により前記不揮発性半導体メモリに書き込む制御部と
を具備することを特徴とするメモリ管理装置。
前記振り分け部は、前記不揮発性半導体メモリ上のデータのガーベジコレクション動作の際に、ガーベジコレクション対象のデータについて、該データが最終アクセスされた時刻についての情報に基づき、前記不揮発性半導体メモリ上の該データの移動先の振り分けを行い、
前記制御部は、前記振り分けられたデータを、追記方式により前記不揮発性半導体メモリに書き込む、ように更に制御すること
を特徴とする請求項１に記載のメモリ管理装置。
前記データ書き込み動作の際に、前記データ属性により決定される書き込み頻度についての情報に基づき算出される変数に対応して配置される複数のライトバッファを更に具備し、
前記振り分け部は、前記複数のライトバッファに、前記算出された変数に基づいてデータを振り分けること
を特徴とする請求項１または２に記載のメモリ管理装置。
前記ガーベジコレクション動作の際に、前記更新可能性に対応して配置される複数のガーベジ用ライトバッファを更に具備し、
前記振り分け部は、前記更新可能性に基づいて、対応する前記複数のガーベジ用ライトバッファにデータを振り分けること
を特徴とする請求項３に記載のメモリ管理装置。
前記振り分け部は、前記データ属性の情報における静的書き込み頻度を更新頻度を表す変数として用い、または前記静的書き込み頻度を更新頻度を表す変数に近似して段階を減らした変数を用い、前記複数のライトバッファにデータ振り分けを行うこと
を特徴とする請求項２乃至４のいずれか１項に記載のメモリ管理装置。
不揮発性半導体メモリと揮発性半導体メモリとを備えるメインメモリを管理する方法であって、
前記不揮発性半導体メモリへのデータ書き込み動作の際に、書き込み対象のデータについて、該データのデータ属性により決定される書き込み頻度についての情報に基づき、前記不揮発性半導体メモリ上の書き込み領域の振り分けを行う第１ステップと、
前記振り分けられたデータを、追記方式により前記不揮発性半導体メモリに書き込む第２ステップとを具備すること
を特徴とするメモリ管理方法。
前記不揮発性半導体メモリ上のデータのガーベジコレクション動作の際に、ガーベジコレクション対象のデータについて、該データが最終アクセスされた時刻についての情報に基づき、前記不揮発性半導体メモリ上の該データの移動先の振り分けを行う第３ステップと、
前記振り分けられたデータを、追記方式により前記不揮発性半導体メモリに書き込む第４ステップとを更に具備すること
を特徴とする請求項６に記載のメモリ管理方法。