(57)【特許請求の範囲】
【請求項１】
不揮発性データ保存装置に備わった仮想ファイルシステムの作業スケジューリング方法において、
データ管理のための複数のメタデータ作業が遂行される区間である予備段階を設定する段階であり、前記複数のメタデータ作業は、前記仮想ファイルシステムが管理する複数の単位に対して別々に遂行されるものである、段階と、
前記設定された予備段階内で、前記複数のメタデータ作業を遂行する段階と、
前記設定された予備段階後に、前記仮想ファイルシステムが管理する前記複数の単位に対するデータの入出力作業を遂行する段階とを含み、
前記予備段階を設定する段階は、
前記仮想ファイルシステムが管理する単位別に、前記データの入出力作業のための準備作業の遂行時間を計算する段階と、
前記計算された遂行時間のうち最長の遂行時間によって、前記予備段階を設定する段階とをさらに含む、
ことを特徴とするスケジューリング方法。
【請求項２】
前記データの入出力作業のための準備作業及び複数のメタデータ作業は、
前記遂行されるデータの入出力作業の種類による前記仮想ファイルシステムの準備作業であることを特徴とする請求項１に記載のスケジューリング方法。
【請求項３】
前記仮想ファイルシステムの準備作業は、
前記メタデータの判読／更新、ガーベジコレクション、マッピングテーブルの判読／更新またはユニット消去のうち少なくとも一つ以上を含むことを特徴とする請求項２に記載のスケジューリング方法。
【請求項４】
前記データの入出力作業を遂行する段階は、
前記設定された予備段階後に、前記データの入出力作業を一括的に遂行させることを特徴とする請求項１に記載のスケジューリング方法。
【請求項５】
前記一括的に遂行されるデータの入出力作業は、
インタリービング方式を介して、前記データが入出力された順に遂行されることを特徴とする請求項４に記載のスケジューリング方法。
【請求項６】
前記不揮発性データ保存装置はフラッシュメモリであり、前記仮想ファイルシステムはフラッシュ変換階層であり、前記フラッシュ変換階層が管理する単位は、前記フラッシュメモリのデバイス単位または複数の前記フラッシュメモリを使用するチャンネル単位であることを特徴とする請求項５に記載のスケジューリング方法。
【請求項７】
不揮発性データ保存装置に備わった仮想ファイルシステムの拡張された作業スケジューリング方法において、
データ管理のための複数のメタデータ作業が遂行される区間である予備段階を設定する段階であり、前記複数のメタデータ作業は、前記仮想ファイルシステムが管理する複数の単位に対して別々に遂行されるものである、段階と、
前記設定された予備段階内で、前記複数のメタデータ作業を遂行する段階と、
前記設定された予備段階内の遊休時間に、次の予備段階のメタデータ作業を遂行する段階であり、前記次の予備段階のメタデータ作業は、前記仮想ファイルシステムが管理する単位別に遂行される、段階と、
前記設定された予備段階後に、前記仮想ファイルシステムが管理する前記複数の単位に対するデータの入出力作業を遂行する段階とを含み、
前記予備段階を設定する段階は、
前記仮想ファイルシステムが管理する単位別に、前記データの入出力作業のための準備作業の遂行時間を計算する段階と、
前記計算された遂行時間のうち最長の遂行時間によって、前記予備段階を設定する段階とをさらに含む、
ことを特徴とするスケジューリング方法。
【請求項８】
前記設定された予備段階内の遊休時間は、
前記設定された予備段階の遂行時間から、前記計算された準備作業の遂行時間を減じた時間であることを特徴とする請求項７に記載のスケジューリング方法。
【請求項９】
前記設定された予備段階内の遊休時間に、次の予備段階のメタデータ作業を遂行する段階は、
前記仮想ファイルシステムで管理する単位別に、前記次の予備段階のメタデータ作業の遂行時間を計算し、前記次の予備段階のメタデータ作業を前記遊休時間に配分することによって遂行することを特徴とする請求項８に記載のスケジューリング方法。
【請求項１０】
前記データの入出力作業のための準備作業、複数のメタデータ作業及び前記次の予備段階のメタデータ作業は、
前記遂行されるデータの入出力作業の種類によって、前記メタデータの判読／更新、ガーベジコレクション、マッピングテーブルの判読／更新またはユニット消去のうち少なくとも一つ以上を含むことを特徴とする請求項９に記載のスケジューリング方法。
【請求項１１】
前記データの入出力作業を遂行する段階は、
前記設定された予備段階後に、前記データの入出力作業を一括的に遂行させることを特徴とする請求項７に記載のスケジューリング方法。
【請求項１２】
前記一括的に遂行されるデータ入出力作業は、
インタリービング方式を介して、前記データが入出力された順に遂行されることを特徴とする請求項１１に記載のスケジューリング方法。
【請求項１３】
前記不揮発性データ保存装置はフラッシュメモリであり、前記仮想ファイルシステムはフラッシュ変換階層であり、前記フラッシュ変換階層が管理する単位は、前記フラッシュメモリのデバイス単位または複数の前記フラッシュメモリを使用するチャンネル単位であることを特徴とする請求項１２に記載のスケジューリング方法。
【請求項１４】
フラッシュメモリに備わったフラッシュ変換階層の作業スケジューリング方法において、
前記フラッシュ変換階層の管理単位別にデータの入出力作業のための準備作業の遂行時間を計算する段階と、
前記計算された遂行時間のうち最長の遂行時間によって予備段階を設定する段階と、
前記設定された予備段階で、それぞれの前記フラッシュ変換階層の管理単位別に、前記データの管理のための複数のメタデータ作業を遂行する段階と、
前記設定された予備段階後に、前記データの入出力作業を一括的に遂行する段階とを含むことを特徴とするスケジューリング方法。
【請求項１５】
前記フラッシュ変換階層の管理単位は、
前記フラッシュメモリのデバイス単位または複数の前記フラッシュメモリを使用するチャンネル単位であることを特徴とする請求項１４に記載のスケジューリング方法。
【請求項１６】
前記データの入出力作業のための準備作業及びメタデータ作業は、
前記メタデータの判読／更新、ガーベジコレクション、マッピングテーブルの判読／更新またはユニット消去のうち少なくとも一つ以上を含むことを特徴とする請求項１５に記載のスケジューリング方法。
【請求項１７】
前記設定された予備段階の遂行時間から、前記計算された前記フラッシュ変換階層の管理単位別準備作業の遂行時間を減じて遊休時間を計算する段階と、
前記計算された前記フラッシュ変換階層の管理単位別遊休時間に、前記管理単位別に次の予備段階のメタデータ作業を遂行する段階とをさらに含むことを特徴とする請求項１４に記載のスケジューリング方法。
【請求項１８】
前記計算された前記フラッシュ変換階層の管理単位別遊休時間に、前記管理単位別に次の予備段階のメタデータ作業を遂行する段階は、
前記フラッシュ変換階層で前記管理単位別に、前記次の予備段階のメタデータ作業の遂行時間を計算し、前記次の予備段階のメタデータ作業を前記遊休時間に配分することによって遂行することを特徴とする請求項１７に記載のスケジューリング方法。
【請求項１９】
前記データの入出力作業を一括的に遂行する段階は、
インタリービング方式を介して、前記データが入出力された順に遂行することを特徴とする請求項１４に記載のスケジューリング方法。
【請求項２０】
仮想ファイルシステムを備えた不揮発性データ保存装置において、
前記仮想ファイルシステムは作業スケジューラを備え、
前記作業スケジューラは、
前記仮想ファイルシステムが管理する単位別に、前記データの入出力作業のための準備作業の遂行時間を計算する遂行時間計算部と、
前記計算された遂行時間のうち最長の遂行時間によって予備段階を設定し、前記データの管理のための複数のメタデータ作業を遂行させる第１制御部と、
前記設定された予備段階後に、前記データの入出力作業を一括的に遂行させる第２制御部と
を備える、ことを特徴とする不揮発性データ保存装置。
【請求項２１】
前記第１制御部は、
前記設定された予備段階の遂行時間から、前記計算された前記仮想ファイルシステムの管理単位別準備作業の遂行時間を減じて遊休時間を計算する遊休時間計算部と、
前記計算された前記仮想ファイルシステムの管理単位別遊休時間に、前記管理単位別に次の予備段階のメタデータ作業を遂行させる追加作業部とをさらに備えることを特徴とする請求項２０に記載の不揮発性データ保存装置。
【請求項２２】
請求項１乃至１９の何れか一項に記載の方法を具現するためのプログラムが記録されたコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、作業スケジューリング方法に係り、さらに詳細には、不揮発性データ保存装置に備わった仮想ファイルシステムで、作業スケジュールの予備段階を設定して仮想ファイルシステムの複雑度を低下させ、効率的なインタリービング遂行を可能にする作業スケジューリング方法及びその装置に関する。
【背景技術】
【０００２】
最近、モバイル機器を備えたマルチメディア装置は、主にＭＰ３音響、動映像のような非常に大きなサイズのマルチメディアデータを保存し、これをユーザに提供している。かような機器で使われる保存装置は、大規模な保存空間を提供するので、データを高速で読み取り、かつ使うことができる機能も提供されねばならない。
【０００３】
図１は、フラッシュメモリを利用したＮ−チャンネル／４−ウェイ（way）方式のハードウェア・アーキテクチャを示す図である。
【０００４】
現在、不揮発性データ保存装置のうちフラッシュメモリは、低電力、小型化、少ない発熱、高い安定性などの理由で、多様なモバイル機器の保存装置として使われており、ユーザの要求に合わせて、１つのメモリに保存することができる空間の大きさも高速度に増大している。
【０００５】
しかし、フラッシュメモリは、一般的にのろいプログラミング（write）速度を有しており、これを克服して高速データ入出力をするために、フラッシュメモリ保存装置を構成する多様なハードウェア・アーキテクチャが提案されている。
【０００６】
図１を参照するに、フラッシュメモリ・コントローラ１１０と１つのチャンネルとに連結された４個のフラッシュメモリ１２０の構成を見ることができる。フラッシュメモリ保存装置は、保存容量増加とデータ入出力性能とを向上させるために、図面のように、多数のフラッシュメモリチップを使用する。
【０００７】
フラッシュメモリに対する読み取り／書き込みは、ｉ）メモリセルからデータを記録／判読し、ｉｉ）フラッシュメモリ・コントローラから／にデータ入力／出力する二段階からなる。かような理由で、フラッシュメモリ保存装置に存在するコントローラは、単一データ入出力チャンネルに対して多数のフラッシュメモリチップを連結し、インタリービング方式でデータを入出力する。現在、一般的なフラッシュメモリ標準によれば、単一チャンネルは、最大４、５個のフラッシュメモリチップを使用する場合、それ以上性能向上を期待し難くなるので、２の指数乗でアドレス分配が容易な４−ウェイアーキテクチャが主に使われている。
【０００８】
図２は、前記図１の１つのチャンネル上で、４個のフラッシュメモリの書き込み動作を示すタイミング図であり、図３は、前記図２で１つのページの書き込み動作をさらに詳細に示す図である。
【０００９】
図３から分かるように、１つのページの書き込み動作（２１０）で、一般的に２ＫＢのページ単位を適用するとき、ページセットアップ（setup）時間が５１．２μｓｅｃ（１バイトのセットアップ時間が２５ｎｓｅｃ）であり、プログラミング時間が２００μｓｅｃである。相対的に遅いプログラミング時間を補償するために、大容量のデータは、図１のようなチャンネルの４個のフラッシュメモリ１２０に分散されて保存される。かような従来の技術は、フラッシュメモリでプログラミングが進む間、チャンネル内で遊休（idle）状態にある他のフラッシュメモリでセットアップを遂行し、コントローラの待機時間を最小化する方法で、図２のように、インタリービング方式の高速書き込み(write)動作を遂行する。
【００１０】
図４は、フラッシュメモリを利用したビット帯域（bit  width）拡張方式のハードウェア・アーキテクチャを示す図である。
【００１１】
フラッシュメモリ保存装置の大容量化によって、５つ以上のチップを使用する場合にも発生することがあり、このときに使用できる方法が、大きく分けてビット帯域拡張方式と多重チャンネル方式とのアーキテクチャに区分できる。前記多重チャンネル方式は、前述の１−チャンネル／ｘ−ウェイ（way）の拡張と見ることができ、ビット帯域拡張方式は、図４に図示されているように、２つ以上のフラッシュメモリチップを連結し、同時にデータ伝送する方法である。連結されたチップは、常に同じアドレス領域に対して同時に読み取り／書き込みを遂行せねばならない。
【００１２】
一方、フラッシュメモリは、一般的にページ単位で読み取り／書き込みがなされ、更新のためにさらに記録するためには、まず多数のページにより構成されているブロック単位で消去動作を遂行しなければならない。かような特徴は、一般的な保存装置と異なる特性であり、既存ファイルシステムとの互換性を有するために、ＦＴＬ（Flash  Translation  Layer）という特別のソフトウェア（仮想ファイルシステム）を利用してフラッシュメモリ保存装置を管理し、既存ファイルシステムとの互換性を提供する。ファイルシステムとの互換性のための仮想ファイルシステムは、他の不揮発性データ保存装置の場合にも適用でき、従って、以下で説明する内容は、不揮発性データ保存装置に対して全般的に適用が可能である。
【００１３】
かようなＦＴＬは、前述の複雑なハードウェア・アーキテクチャから一般的にアドレスマッピングテーブル、フリーブロック情報、バッドブロック情報のような多様なメタデータを利用するが、それらは、ほとんどフラッシュメモリ内に保存されている。また、ＦＴＬのメタデータは、フラッシュメモリのコピーバック（copyback）命令が許容される範囲であるデバイス（device）またはプレイン（plain）単位で独立的に保存される。これは、ＦＴＬの重要な作業のうち一つである廃領域収集（garbage  collection）を効率的に遂行するためであり、多数のチップを使用する複雑なアーキテクチャのフラッシュメモリ保存装置は、チップの個数に比例して独立的なメタデータを有することになる。
【００１４】
図５は、単一フラッシュメモリを利用した書き込み要請命令によるＦＴＬの命令語シーケンスのタイミング図である。
【００１５】
前記説明したハードウェア・アーキテクチャ構造でＦＴＬは、ファイルシステムの読み取り／書き込み要請に対してそれぞれのフラッシュメモリに多様な命令（command）を送る。図５で、単一フラッシュメモリチップを使用する保存装置の場合を仮定すれば、ファイルシステムのデータ記録要請５１０（write  request）に対して、ＦＴＬがハードウェアに送る命令は、マップテーブルの判読／更新（map  table  read/update）、ブロック消去（block  erase）、ブロック併合５２１（block  merge）のような多様なＦＴＬメタデータに対する作業（metadata  commands）５２０，５４０と、実際要請したユーザデータの入出力のための命令（data  commands）５３０，５５０に混在されている。
【００１６】
前述のように、高速データ入出力のために多数のチップを使用するフラッシュメモリ保存装置は、フラッシュメモリチップデバイスまたはチャンネル単位で多数の独立的なメタデータが存在することになる。従って、かような構造でファイルシステムのデータ入出力要請により、ＦＴＬは、それぞれのメタデータに対して互いに異なる命令を指示するようになる。すなわち、それぞれの独立的なＦＴＬメタデータごとに互いに異なるメタデータ命令セット（metadata  commands  set）を有し、それぞれの遂行時間も互いに異なる。
【００１７】
従って、実際のユーザデータに対する命令のイッシュ（issue）時間が互いに異なることとなる。すなわち、それぞれのＦＴＬ管理単位ごとに互いに異なる命令スケジュール（作業スケジュール）を有するので、ＦＴＬ管理単位の増加は、ＦＴＬの複雑度を増大する要因になり、ユーザデータのイッシュ時間が異なることにより、大容量のバッファが必要になる。かようなＦＴＬの複雑度増大によって、ＦＴＬのコードサイズが大きくなって、メモリ使用量が増加し、またＣＰＵ（Central  Processing  Unit）の処理時間（processing  time）が延長するなど、リソース使用量の増加につながる。ＦＴＬの処理量増加は、それぞれの命令イッシュに対して遅延時間が発生する可能性が高まり、またユーザデータ入出力命令が特定時点に集中し、ホストと保存装置との間の大容量データ（burst  data）伝送の困難さを発生させ、インタリービングによる性能向上効果を阻害する要因として作用しうる。かような問題点は、結局フラッシュメモリ保存装置のデータ入出力能が低下してしまう結果として現れる。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従って、本発明は、前記のような問題点を解決するために案出されたものであり、本発明では、不揮発性データ保存装置に備わった仮想ファイルシステムで作業スケジュールの予備段階を設定し、仮想ファイルシステムの複雑度を低下させ、効率的なインタリービング遂行の可能な作業スケジューリング方法及びその装置を提供するところに目的がある。
【課題を解決するための手段】
【００１９】
前記のような技術的課題を解決するために、本発明によるスケジューリング方法は、不揮発性データ保存装置に備わった仮想ファイルシステム（virtual  file  system）の作業スケジューリング（command  scheduling）方法において、データ管理のための複数のメタデータ作業が遂行される予備段階（Preparation  phase）を設定する段階と、前記設定された予備段階で、前記複数のメタデータ作業の遂行が終了すれば、前記データの入出力作業を遂行する段階とを含むことを特徴とするスケジューリング方法により達成される。
【００２０】
また、前記設定された予備段階内で、前記複数のメタデータ作業を遂行する段階をさらに含み、前記遂行される複数のメタデータ作業は、前記仮想ファイルシステムが管理する単位別に遂行されることが望ましい。
【００２１】
また、前記予備段階を設定する段階は、前記仮想ファイルシステムが管理する単位別に、前記データ入出力作業のための準備作業の遂行時間を計算する段階と、前記計算された遂行時間のうち最長の遂行時間によって、前記予備段階を設定する段階とをさらに含むことが望ましい。
【００２２】
前記データ入出力作業のための準備作業及び複数のメタデータ作業は、前記データ段階で遂行されるデータの入出力作業の記録または判読の種類による前記仮想ファイルシステムの準備作業であることが望ましく、前記仮想ファイルシステムの準備作業は、前記メタデータの判読／更新、ガーベジコレクション（garbage  collection）、マッピングテーブル判読／更新またはユニット消去（unit  erase）のうち少なくとも一つ以上を含むことがさらに望ましい。
【００２３】
また、前記データ段階を設定し、前記データの入出力作業を遂行する段階は、前記設定された予備段階後に、前記データの入出力作業を一括的に遂行させることが望ましく、前記一括的に遂行されるデータ入出力作業は、インタリービング方式を適用し、前記データが入出力された順に遂行されることがさらに望ましい。
【００２４】
一方、前記不揮発性データ保存装置はフラッシュメモリであり、前記仮想ファイルシステムはフラッシュ変換階層（ＦＴＬ：Flash  Translation  Layer）であり、前記ＦＴＬが管理する単位は、前記フラッシュメモリのデバイス単位または複数の前記フラッシュメモリを使用するチャンネル単位であることが望ましい。
【００２５】
前記の技術的課題を解決するために本発明による拡張された作業スケジューリング方法は、不揮発性データ保存装置に備わった仮想ファイルシステムの拡張された作業スケジューリング（extended  command  scheduling）方法において、データ管理のための複数のメタデータ作業が遂行される予備段階を設定する段階と、前記設定された予備段階内の遊休時間（idle  time）に次の予備段階のメタデータ作業を遂行する段階と、前記設定された予備段階で、前記複数のメタデータ作業及び前記次の予備段階のメタデータ作業の遂行がいずれも終了すれば、前記データの入出力作業を遂行する段階とを含むことを特徴とするスケジューリング方法により達成される。
【００２６】
また、前記設定された予備段階内で、前記複数のメタデータ作業を遂行する段階をさらに含み、前記遂行される複数のメタデータ作業及び前記次の予備段階のメタデータ作業は、前記仮想ファイルシステムが管理する単位別に遂行されることが望ましい。
【００２７】
また、前記予備段階を設定する段階は、前記仮想ファイルシステムが管理する単位別に、前記データ入出力作業のための準備作業の遂行時間を計算する段階と、前記計算された遂行時間のうち最長の遂行時間によって、前記予備段階を設定する段階とをさらに含むことが望ましい。
【００２８】
一方、前記設定された予備段階内の遊休時間は、前記設定された予備段階の遂行時間から、前記計算された仮想ファイルシステムが管理する単位別準備作業の遂行時間を減じた時間であることが望ましく、前記設定された予備段階内の遊休時間に、次の予備段階のメタデータ作業を遂行する段階は、前記仮想ファイルシステムで管理する単位別に、前記次の予備段階のメタデータ作業の遂行時間を計算し、前記次の予備段階のメタデータ作業を前記遊休時間に配分することによって遂行することが望ましい。
【００２９】
また、データ入出力作業のための準備作業、前記複数のメタデータ作業及び前記次の予備段階のメタデータ作業は、前記データ段階で遂行されるデータの入出力作業の記録または判読の種類によって、前記メタデータの判読／更新、ガーベジコレクション、マッピングテーブル判読／更新またはユニット消去のうち少なくとも一つ以上を含むことが望ましい。
【００３０】
前記データ段階を設定し、前記データの入出力作業を遂行する段階は、前記設定された予備段階後に、前記データの入出力作業を一括的に遂行させることが望ましく、前記一括的に遂行されるデータ入出力作業は、インタリービング方式を適用し、前記データが入出力された順に遂行されることがさらに望ましい。
【００３１】
一方、前記不揮発性データ保存装置はフラッシュメモリであり、前記仮想ファイルシステムはＦＴＬであり、前記ＦＴＬが管理する単位は、前記フラッシュメモリのデバイス単位または複数の前記フラッシュメモリを使用するチャンネル単位であることが望ましい。
【００３２】
前記の技術的課題を解決するための本発明によるスケジューリング方法は、フラッシュメモリに備わったＦＴＬの作業スケジューリング方法において、前記ＦＴＬの管理単位別にデータ入出力作業のための準備作業の遂行時間を計算する段階と、前記計算された遂行時間のうち最長の遂行時間によって予備段階を設定する段階と、前記設定された予備段階で、それぞれの前記ＦＴＬの管理単位別に、前記データの管理のための複数のメタデータ作業を遂行する段階と、前記設定された予備段階後に、前記データの入出力作業を一括的に遂行する段階とを含むことを特徴とするスケジューリング方法によっても達成される。
【００３３】
また、前記ＦＴＬが管理する単位は、前記フラッシュメモリのデバイス単位または複数の前記フラッシュメモリを使用するチャンネル単位であることが望ましく、前記データ入出力作業のための準備作業及びメタデータ作業は、前記メタデータの判読／更新、ガーベジコレクション、マッピングテーブル判読／更新またはユニット消去のうち少なくとも一つ以上を含むことが望ましい。
【００３４】
また、前記データ段階を設定し、前記データの入出力作業を一括的に遂行する段階は、インタリービング方式を適用し、前記データが入出力された順に遂行することが望ましい。
【００３５】
一方、前記設定された予備段階の遂行時間から、前記計算された前記ＦＴＬの管理単位別準備作業の遂行時間を減じて遊休時間を計算する段階と、前記計算された前記ＦＴＬの管理単位別遊休時間に、前記管理単位別に次の予備段階のメタデータ作業を遂行する段階とをさらに含むことが望ましく、前記計算された前記ＦＴＬの管理単位別遊休時間に、前記管理単位別に次の予備段階のメタデータ作業を遂行する段階は、前記フラッシュ変化階層で前記管理単位別に、前記次の予備段階のメタデータ作業の遂行時間を計算し、前記次の予備段階のメタデータ作業を前記遊休時間に配分することによって遂行することが望ましい。
【００３６】
前記の技術的課題を解決するための本発明によるスケジューラは、不揮発性データ保存装置に備わった仮想ファイルシステムに対する作業スケジューリング装置において、前記仮想ファイルシステムが管理する単位別に、前記データ入出力作業のための準備作業の遂行時間を計算する遂行時間計算部と、前記計算された遂行時間のうち最長の遂行時間によって、前記予備段階を設定し、データ管理のための複数のメタデータ作業を遂行させる第１制御部と、前記設定された予備段階後に、前記データの入出力作業を一括的に遂行させる第２制御部とを備えることを特徴とするスケジューラにより達成される。
【００３７】
前記第１制御部は、前記設定された予備段階の遂行時間から、前記計算された前記仮想ファイルシステムの管理単位別準備作業の遂行時間を減じて遊休時間を計算する遊休時間計算部と、前記計算された前記仮想ファイルシステムの管理単位別遊休時間に、前記管理単位別に次の予備段階のメタデータ作業を遂行させる追加作業部とをさらに備えることが望ましい。
【００３８】
さらに、前記の課題をなすために、本発明によるスケジューリング方法を具現するためのプログラムが記録されたコンピュータで読み取り可能な記録媒体を備える。
【発明の効果】
【００３９】
メモリ保存装置の大容量化、高速入出力処理を実現するにおいて、多数のフラッシュメモリを使用する場合に、本発明による仮想ファイルシステムの作業スケジューリング方法によれば、仮想ファイルシステム（ＦＴＬ）の構造を単純化し、コードサイズ、リソース使用量を減少できる。またデータ段階で、ホストから入力されたデータを順に記録できるので、正確なインタリービングの効果も期待することができ、大容量のバッファを使用せずともホストと保存装置との間の円滑な大容量データ伝送が可能になる。
【００４０】
また、拡張された作業スケジューリング方法によれば、予備段階内の遊休時間に追加された作業（extra  job）により、次の予備段階で必要な作業があらかじめ遂行できるので、全体的に予備段階の平均所要時間が短縮される効果が現れ、結局、保存装置のデータ入出力能が向上する。
【発明を実施するための最良の形態】
【００４１】
以下、添付された図面を参照しつつ、本発明の望ましい実施例について詳細に説明する。以下で、たとえフラッシュメモリを実施形態として説明しているとしても、それを不揮発性データ保存装置に全般的に適用可能であるということは、これまで説明した通りである。
【００４２】
図６は、本発明の一実施形態による、不揮発性データ保存装置に備わった仮想ファイルシステムの作業スケジューリング方法を示すフローチャートである。図６を参照するに、まず予備段階（preparation  phase）を設定するために、仮想ファイルシステム（ＦＴＬ：Flash  Translation  Layer）が管理する単位別に、前記データ入出力作業のための準備作業の遂行時間を計算する（６１０）。ＦＴＬは、メモリチップデバイスまたは多数のデバイス（ｘ−ウェイ（way））を具備したチャンネル単位で、多数の独立的なメタデータを管理するので、それら管理単位別に、前記データ入出力作業のための準備作業の遂行時間を計算する。実際のユーザデータの入出力作業を遂行するためには、事前に前記管理単位別にデータの入出力作業の種類（記録／判読など）によって予備動作（準備作業）が必要であるが、例えば、マップテーブルの判読／更新（map  table  read/update）、ユニット（ブロック）消去（block  erase）、廃領域収集（併合（merge）、交換（switch）、圧縮（compaction））のような多様なＦＴＬメタデータに対する作業（metadata  commands）が遂行される。ＦＴＬは、かような準備作業の遂行時間を各デバイス別（またはチャンネル別）に計算する。
【００４３】
次に、計算された遂行時間のうち最長の遂行時間によって、前記予備段階を設定する（６２０）。すなわち、他のデバイスを含んで前記計算された準備作業の遂行時間のうち、最長時間の時点を予備段階の時間に設定するのである。予備段階の時間の間は、前述のマップテーブルの判読／更新（map  table  read/update）、ブロック消去（block  erase）、ブロック併合（block  merge）のような多様なＦＴＬメタデータに対する作業が遂行され（６３０）、作業スケジュール（命令スケジュール）管理上、ユーザデータの読み取り／書き込み作業命令は指示されない。
【００４４】
予備段階のメタデータ作業の遂行がいずれも終われば（６４０）、すなわち予備段階が終了すれば、ＦＴＬは、実際のユーザデータの入出力作業を一括的に指示し、読み取り／書き込み作業を遂行する（６５０）。実際のユーザデータの入出力作業が遂行される区間は、前記予備段階に対応してデータ段階（data  phase）で設定される。データ入出力作業が一括的に遂行されるので、インタリービング方式を介して多数のメモリチップまたはチャンネルに分散保存されるユーザデータは、高速で処理されうる。かような式で、ホストのファイルシステムの要請（read/write  request）は、１回以上の予備段階とデータ段階とが反復的に遂行されて完了する。
【００４５】
図７は、本発明の一実施形態による、不揮発性データ保存装置に備わった仮想ファイルシステムの作業スケジューリング方法を示すタイミング図である。図７を参照するに、４個のフラッシュメモリチップまたは４個のチャンネル単位で、ＦＴＬのメタデータが管理される場合を仮定しており、それぞれの予備段階７１０，７３０は、状況により多様な作業（map  table  read/write，garbage  collection，eraseなど）を遂行する命令（do  preparation）７１１によって構成されている。予備段階は、ファイルシステムの論理的ブロック単位（logical  block  unit）または読み取り／書き込み要請単位（read/write  request  unit）で遂行されうる。
【００４６】
また、４個のＦＴＬ管理単位は、互いに異なる準備作業を遂行するようになって、それぞれの所要時間も変わる。最長の時間が必要な１番デバイス（Device）の準備作業７１３が完了すれば、すなわち予備段階が終了すれば、データ段階７２０，７４０が始まる。データ段階では、ユーザデータをホストから入力された（またはバッファに保存された）順に読み取り／書き込みの命令が遂行され、４個のＦＴＬ管理単位は、正確にインタリービングがなされてデータを読んで使うことができる。
【００４７】
このように、作業スケジュールを予備段階７１０，７３０とデータ段階７２０，７４０とに単純化して分けることにより、正確に理論的なインタリービングの効果的な性能を発揮でき、ユーザデータの入出力順序と、作業スケジュール上のユーザデータ命令順序とが一致するようになって、ホストとＦＴＬとの間の大容量伝送が容易になる。
【００４８】
図８は、本発明の他の実施形態による、不揮発性データ保存装置に備わった仮想ファイルシステムの拡張された作業スケジューリング方法を示すフローチャートである。図８を参照しつつ動作過程について述べれば、図６のように、まず仮想ファイルシステムが管理する単位別に、前記データ入出力作業のための準備作業の遂行時間を計算する（８１０）。前記準備作業に利用されるメタデータは、互いに独立的であるから、それぞれの遂行時間もいずれも異なって計算される。従って、それら計算された遂行時間のうち最長の遂行時間に合わせて予備段階を設定し（８２０）、設定された予備段階の時間の間に多様なメタデータ作業を遂行する（８３０）。
【００４９】
このとき、前記管理単位（例えば、デバイス単位）別に計算された準備作業の遂行時間のうち、最長遂行時間と計算されたデバイス、すなわち予備段階の時間の間でずっと準備作業を遂行するデバイスを除外した残りのデバイスは、それぞれのメタデータに対する作業（準備作業）が終了した後で、遊休時間（idle  time）を確保するようになる。かような遊休時間は、予備段階の遂行時間から、それぞれのデバイス別準備作業の遂行時間を減じて求めることができる。ＦＴＬは、このように確保された遊休時間を単純に待機時間（waiting  time）として放置せずに、段階の特性に合う他の作業を遂行する機会とすることができる。従って、拡張された作業スケジューリング方法では、かような遊休時間に、次の予備段階で必要な準備作業をあらかじめ遂行する。
【００５０】
予備段階で必要な準備作業、すなわちメタデータ作業は、典型的にマップテーブル判読やフリーブロックを確保するための廃領域収集作業、データ記録のための前処理作業としてのブロック消去作業などであるから、かような準備作業の遂行時間をあらかじめ計算し、一部を確保された前記遊休時間に合うように配分して遂行することができるのである。かかる過程を介して、各予備段階で遊休時間を節約できるので、単一作業要請（read/write  request）に対する処理時間が短縮される。さらに、多数の要請が連続的に受信される大容量高速データ伝送では、かようなメカニズムにより全体的な入出力処理能がかなり向上しうる。
【００５１】
前記述べた通り、予備段階内の遊休時間の存在可否を判断し（８４０）、前述の次の予備段階のメタデータ作業を遂行し（８５０）、それらメタデータ作業がいずれも終了すれば（８６０）、すなわち予備段階が終われば、実際のユーザデータの入出力作業を遂行する（８７０）。このとき、データの入出力作業は、前記図６で述べたように、いずれも一括的に遂行されるので（データ段階）、正確なインタリービング方式を介し、分散保存されるデータを高速で処理できる。
【００５２】
図９は、本発明の他の実施形態による、不揮発性データ保存装置に備わった仮想ファイルシステムの拡張された作業スケジューリング方法を示すタイミング図である。
【００５３】
前述の図７で、それぞれのＦＴＬ管理単位ごとに準備作業の時間が互いに異なる理由で、それぞれの遊休時間７１２が発生した。図９では、かような遊休時間７１２の間に、次の予備段階で遂行される作業をあらかじめ予測し、そのうち一部作業を遂行する段階（extra  job)を追加し、遊休時間を最小化してメモリ保存装置の読み取り／書き込み能を高める過程を示している。遊休時間に追加された作業には、一般的に与えられた時間によって、ブロック消去（erase）、現在作業のアドレスと隣接したアドレスに対するマップテーブル判読（map  table  read）、フリーブロックを収集するためのガーベジコレクション（garbage  collection）などを例に挙げることができる。すなわち、遊休時間に追加された作業により、全体予備段階の平均所要時間が短縮され、結局メモリ保存装置の読み取り／書き込み処理時間が短縮される。さらに、設計者は、追加される作業に対する多様な政策（extra  job  policy)を樹立し、フラッシュメモリ保存装置の使用目的によって、さらに高いデータ入出力能を導出することも可能である。
【００５４】
図１０は、本発明のさらに他の実施形態による、不揮発性データ保存装置に備わった仮想ファイルシステムに対する作業スケジューリング装置１１００を示す機能ブロック図である。
【００５５】
各ブロック別の動作特性について述べれば、遂行時間計算部１１１０は、ＦＴＬが管理する単位別にデータ入出力作業のための準備作業の遂行時間を計算する。
【００５６】
第１制御部１１２０は、遂行時間計算部１１１０で計算された遂行時間のうち最長の遂行時間によって予備段階を設定し、データ管理のための複数のメタデータ作業を遂行させる。第１制御部１１２０は、設定された予備段階時間から、計算された前記管理単位別準備作業の遂行時間を減じ、遊休時間を計算する遊休時間計算部１１２１と、計算された遊休時間に管理単位別に次の予備段階のメタデータ作業を遂行させる追加作業部１１２２とをさらに含むことができる。
【００５７】
第１制御部１１２０によるメタデータ作業がいずれも終了すれば、第２制御部１１３０は、設定された予備段階後にユーザデータの入出力作業を一括的に遂行させる。
【００５８】
本発明によるスケジューリング方法は、またコンピュータで読み取り可能な記録媒体にコンピュータで読み取り可能なコードとして具現することが可能である。コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み込み可能なデータが保存されるあらゆる種類の記録装置を含む。コンピュータで読み取り可能な記録媒体の例としては、ＲＯＭ（リード  オンリ  メモリ）、ＲＡＭ（ランダム  アクセス  メモリ）、磁気テープ、フロッピー（登録商標）ディスクのようなマグネチック記録媒体や、ＣＤ−ＲＯＭ、光データ保存装置のような光学的判読媒体があって、またキャリアウェーブ（例えば、インターネットを介した伝送）の形態で具現されるものも含む。また、コンピュータで読み取り可能な記録媒体は、ネットワークに連結されたコンピュータシステムに分散され、分散方式でコンピュータで読み取り可能なコードが保存されて実行されうる。
【００５９】
以上、本発明についてその望ましい実施形態を中心に説明した。本発明の属する技術分野で当業者は、本発明の本質的な特性から外れない範囲で変形された形態で具現できるということを理解できるであろう。従って、開示された実施形態は、限定的な観点ではなくして説明的な観点で考慮されるものである。本発明の範囲は、前述の説明ではなくして特許請求の範囲に示されており、それと同等な範囲内にあるあらゆる差異点は、本発明に含まれたと解釈されるのである。
【産業上の利用可能性】
【００６０】
本発明の不揮発性データ保存装置に備わった仮想ファイルシステムの作業スケジューリング方法及び装置は、例えば、メモリ関連の技術分野に効果的に適用可能である。
【図面の簡単な説明】
【００６１】
【図１】フラッシュメモリを利用したＮ−チャンネル／４−ウェイ（way）方式のハードウェア・アーキテクチャを示す図である。
【図２】図１の１つのチャンネル上で、４個のフラッシュメモリの書き込み動作を示すタイミング図である。
【図３】図２で、１つのページの書き込み動作についてさらに詳細に示す図である。
【図４】フラッシュメモリを利用したビット帯域（bit  width）拡張方式のハードウェア・アーキテクチャを示す図である。
【図５】単一フラッシュメモリを利用した書き込み要請命令によるＦＴＬの命令語シーケンスのタイミング図である。
【図６】本発明の一実施形態による、不揮発性データ保存装置に備わったＦＴＬの作業スケジューリング方法を示すフローチャートである。
【図７】本発明の一実施形態による、不揮発性データ保存装置に備わったＦＴＬの作業スケジューリング方法を示すタイミング図である。
【図８】本発明の他の実施形態による、不揮発性データ保存装置に備わったＦＴＬの拡張された作業スケジューリング方法を示すフローチャートである。
【図９】本発明の他の実施形態による、不揮発性データ保存装置に備わったＦＴＬの拡張された作業スケジューリング方法を示すタイミング図である。
【図１０】本発明のさらに他の実施形態による、不揮発性データ保存装置に備わったＦＴＬに対する作業スケジューリング装置を示す機能ブロック図である。
【符号の説明】
【００６２】
１１０      フラッシュメモリ・コントローラ
１２０，４１０    フラッシュメモリ
１１００    作業スケジューリング装置
１１１０    遂行時間計算部
１１２０    第１制御部
１１２１    遊休時間計算部
１１２２    追加作業部
１１３０    第２制御部
【図１】
0005475227.tif 000002
【図２】
0005475227.tif 000003
【図３】
0005475227.tif 000004
【図４】
0005475227.tif 000005
【図５】
0005475227.tif 000006
【図６】
0005475227.tif 000007
【図７】
0005475227.tif 000008
【図８】
0005475227.tif 000009
【図９】
0005475227.tif 000010
【図１０】
0005475227.tif 000011