(57)【要約】本発明はデジタル記憶装置におけるフラグメンテーション（ファイル・フラグメンテーション及び空き領域フラグメンテーションの両方）を減少させるための方法及びシステムを提供する。このような装置において複数のファイルが削除可能である場合、本発明はデフラグメンテーションを最大限にするためにファイルを選択的に削除することを提案する。この選択はファイル・デフラグメンテーション及び空き領域デフラグメンテーションを最適化することができる。
2004517399.tif 000002
【特許請求の範囲】
【請求項１】
デジタル記憶装置におけるフラグメンテーションを減少させるための方法であって：
削除可能なファイルが複数存在することを決定するステップ；
前記複数のファイルの中からファイルを１つ選択するステップ；及び、
前記選択されたファイルを削除するステップであり、選択されていない他のファイルは削除しないようなステップ；
から構成されることを特徴とする方法。
【請求項２】
請求項１に記載のデジタル記憶装置におけるフラグメンテーションを減少させるための方法において：
前記の選択ステップは、最もフラグメント化されたファイルを削除するために選択するステップから構成されることを特徴とする方法。
【請求項３】
請求項１に記載のデジタル記憶装置におけるフラグメンテーションを減少させるための方法において前記の選択ステップは：
（ａ）どのファイルの削除がファイル・デフラグメンテーション及び空き領域デフラグメンテーションを最適化するかを決定するステップ；及び、
（ｂ）前記の決定されたファイルを削除するために選択するステップ；
から構成されることを特徴とする方法。
【請求項４】
請求項３に記載のデジタル記憶装置におけるフラグメンテーションを減少させるための方法において前記の選択ステップ（ａ）は：
（ｉ）削除可能である各ファイルについて、その削除によるファイル・フラグメンテーションへの影響を算出するサブステップ；
（ｉｉ）削除可能である各ファイルについて、その削除による空き領域フラグメンテーションへの影響を算出するサブステップ；及び、
（ｉｉｉ）前記削除可能なファイルのうち前記サブステップ（ｉ）と（ｉｉ）との和が最も小さいファイルを決定するサブステップ；
から構成されることを特徴とする方法。
【請求項５】
請求項４に記載のデジタル記憶装置におけるフラグメンテーションを減少させるための方法において：
前記サブステップ（ｉｉｉ）の結果から得られたファイルは、ファイルの大きさに応じて標準化されることを特徴とする方法。
【請求項６】
デジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムであって：
削除可能なファイルが複数存在することを決定する手段；
前記複数のファイルの中からファイルを１つ選択する手段；及び、
前記選択されたファイルを削除する手段であり、選択されていない他のファイルは削除しないような手段；
から構成されることを特徴とするシステム。
【請求項７】
請求項６に記載のデジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムであって：
最もフラグメント化されたファイルを削除するために選択する手段から構成されることを特徴とするシステム。
【請求項８】
請求項６に記載のデジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムであって：
どのファイルの削除がファイル・デフラグメンテーション及び空き領域デフラグメンテーションを最適化するかを決定する手段；及び、
前記の決定されたファイルを削除するために選択する手段；
から構成されることを特徴とするシステム。
【請求項９】
請求項８に記載のデジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムにおいて前記ファイル・デフラグメンテーション及び空き領域デフラグメンテーションを最適化するファイルを決定する手段は：
（ｉ）削除可能である各ファイルについて、その削除によるファイル・フラグメンテーションへの影響を算出する手段；
（ｉｉ）削除可能である各ファイルについて、その削除による空き領域フラグメンテーションへの影響を算出する手段；及び、
（ｉｉｉ）前記削除可能なファイルのうち前記の手段（ｉ）と（ｉｉ）との和が最も低いファイルを決定する手段；
から構成されることを特徴とするシステム。
【請求項１０】
請求項９に記載のデジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムであって：
さらにファイルの大きさに応じて前記の手段（ｉｉｉ）で得られたファイルを標準化する手段から構成されることを特徴とするシステム。
【請求項１１】
請求項６に記載のデジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムであって：
デジタル・ビデオレコーダを構成することを特徴とするシステム。
【請求項１２】
コンピュータプログラムであって：
プロセッサに請求項１に記載の方法の実行を促すようにアレンジされたプログラム。
【発明の詳細な説明】
【０００１】
本発明は、フラグメンテーションを減少させる方法及びそのためにアレンジされたシステムに関する。本発明はさらにこれに対応するコンピュータプログラムにも関する。
デジタル記憶装置とは典型的にはデータが記憶されているディスクのことである。本発明はこのような記憶装置であって、データの記憶が一時的でありうる、すなわち記憶されるデータが削除可能であるような記憶装置に関する。
【０００２】
ファイルという形をとるデータは、上記のようなディスクに記憶される際には、ディスク中の各々のファイルがそれぞれ単独でアクセスされうるように記憶される。これらのファイルはディスク上において同心円状にアレンジされるトラックの上に記憶される。ディスクにおいて記憶される特定のファイルの場所についての情報は、別のデータ構造であるディスク・マネージメント・ファイルに記憶される。
【０００３】
ファイルとは１以上のフラグメントという形でディスクに保存される。したがってフラグメントはファイルの全体あるいは一部分を含む。１つの大きなファイルが記憶される際には、いくつかのフラグメントが必要とされうる。ディスクにおける空き領域に応じて、これらのフラグメントはディスク表面に散りばめられている場合がある。ディスクのデータ記憶容量がいっぱいになる寸前である場合は、比較的小さなファイルであっても複数の離れ離れになったフラグメントに分割されなければならない場合がある。
【０００４】
上記のようなファイルのフラグメントの分散配置は、ファイル・フラグメンテーションと呼ばれる。また、これらのフラグメント間にある空き領域の断片化を空き領域フラグメンテーションと呼ぶ。一般に細かくフラグメント化されたディスクにおいては、読解装置が関連するフラグメントをディスク全体から探し当てていかなければならないため読解に長い時間がかかることとなる。これと同様に、細かくフラグメント化されたディスクにおいては、ファイルを保存するのにも長い時間が要される。これは書き込み装置が、ファイル全体を記憶するために必要なフラグメントを時には広い領域に渡って離散している中から探し当てなければならないからである。このファイル・フラグメンテーションと空き領域フラグメンテーションとの両方をあわせてフラグメンテーションと呼ぶ。
【０００５】
このような記憶装置のフラグメンテーションを減少させるためには、例えばＵＳ−Ａ−５，９３０，８２８に開示される方法などのようなさまざまなアプローチが検討されてきた。上記文献に従った提案では、フラグメンテーションを減少させるためにファイルがディスク上を動かし回される。しかしこの操作は多くの時間を要する上にプロセッサに大きな負担をかける。
【０００６】
ファイルシステムを用いるディスクベースのデジタル・ビデオレコーダなどといった最近のデジタル装置においては、ファイルが削除される場合が多い。例えばユーザーは予め削除されるべきファイルを選択する（ウィンドウズ（登録商標）オペレーティング・システム環境における「ごみ箱」に類似する）ことができ、またファイルが一定期間だけ保持されるように注釈されることも可能である。このような注釈は、通常マーカー・フラグによってシステムファイル・マネージャーにおいて記録される。この場合、例えば新しいファイルを保存する場所を作るためなど、削除操作が実行されなければならない際に、削除されてよいファイルが複数存在することもある。
【０００７】
削除操作の実施が要される場合、 （ａ）少なくとも所要の空き領域が作られ；かつ、（ｂ）ファイル・デフラグメンテーション及び空き領域デフラグメンテーション（フラグメンテーションをなくしていく作業）が最適化されるようにファイルを最小限の数だけ永久的に削除することが望ましい。
本発明の課題は、デジタル記憶装置におけるフラグメンテーションを減少させるための方法、システム、及びこれらに対応するコンピュータプログラムを提供することである。
【０００８】
本発明の範囲における請求項１及び４は、フラグメンテーションを減少させるために複数の削除可能なファイルが存在する場合ファイルを選択的に削除するという解決手段を提案する。
【０００９】
本発明の実施における第１形態においては、デジタル記憶装置におけるフラグメンテーションを減少させるための方法であって：
削除可能なファイルが複数存在することを決定するステップ；
前記複数のファイルの中からファイルを１つ選択するステップ；及び、
前記選択されたファイルを削除するステップであり、選択されていない他のファイルは削除しないようなステップ；
から構成されることを特徴とする方法が提供される。
【００１０】
本発明の実施における第２形態においては、デジタル記憶装置におけるフラグメンテーションを減少させるためにアレンジされたシステムであって、削除可能なファイルが複数存在することを決定する手段；前記複数のファイルの中からファイルを１つ選択する手段；及び前記選択されたファイルを削除する手段であり、選択されていない他のファイルは削除しないような手段；から構成されることを特徴とするシステムが提供される。
【００１１】
請求項２及び７は、ファイル・デフラグメンテーションを最適化する好適な方法又は手段を提供する。
【００１２】
請求項３及び８は、ファイル・デフラグメンテーションと空き領域デフラグメンテーションとの両方を最適化する好適な方法を提供する。
【００１３】
請求項４及び９は、ファイル・デフラグメンテーションと空き領域デフラグメンテーションとの両方を最適化するためにどのファイルを選択すべきかを決定する好適な方法又は手段を提供する。
【００１４】
請求項５及び１０は、最適なデフラグメンテーションを決定する際にファイルの大きさを考慮するための好適な方法又は手段を提供する。
【００１５】
請求項１１に記載されるように本発明は、好適にはデジタル・ビデオレコーダとして適用されることが可能である。
【００１６】
請求項１２に記載されるように本発明は、好適にはコンピュータプログラムとして適用されることが可能である。
【００１７】
なお、デジタル記憶装置において複数のファイルが削除対象の候補として注釈され、その中からファイルが選択的削除されることによって効果的なフラグメンテーションの制限が実現されるのである。
以下においては添付の図面を参照に本発明の好適な実施形態を例証として説明する。なお、図２〜４に示されるいくつかの特性は、典型的にはソフトウェアにおいて実装されるものであり、したがってこれらはソフトウェア・モジュール又はオブジェクトなどのソフトウェア・エンティティを表す。
【００１８】
図１は、デジタル・ビデオレコーダ２０におけるメモリ・ディスク１０、及びこのメモリ・ディスク１０におけるファイルを制御するファイル・マネージャー３０を示す。前記のメモリ・ディスク１０は、対応する本発明の好適な実施形態に従ったデジタル・ビデオレコーダを操作するためのコンピュータプログラム４０を有する。
【００１９】
図２は、ファイルの書込み操作のステップを示す。図２で示される符号に対応するステップは以下のようになる：
１００  ディスクに書き込むファイルを選択する；
１０２  ディスク上で利用可能な場所を探す；
１０４  ファイルを所要のクラスターに分割する；
１０６  クラスターをディスクに書き込む；
１０８  ファイル・マネージャー・エントリーを作成する；
１１０  ファイルに削除の注釈をつけるべきか？
１１２  ファイル・マネージャー・エントリーに注釈をつける；
１１４  終了。
【００２０】
ステップ１００においては、１つのファイル（図示せず）がディスク１０に書き込まれるために選択される。例えばユーザー又は自動的保存命令などによって一旦ディスク１０に書き込まれるファイルが選択されると（ステップ１００）、ディスク１０における利用可能な空き領域を探すためにファイル・マネージャー３０の検索が実施される（ステップ１０２）。ここでは、まだディスク１０に充分場所はあるが、この場所はある程度断片に分かれていると仮定する。したがってディスク１０に書き込まれるファイルは、所要の数及び大きさのフラグメントに分割され（ステップ１０４）、その後ディスク１０に書き込まれる（ステップ１０６）。次にファイルの記録を維持するために、ファイル・マネージャー３０においてファイル・マネージャー・エントリーが作成される（ステップ１０８）。この時点でファイルに削除の注釈をつけることが可能であるが、後程このような注釈をつけることも可能である（ステップ１１０）。前記の注釈は典型的にはファイルにおけるファイル・マネージャー・エントリー上のマーカー・フラグによるものである。ファイルに注釈がつけられる場合は、対応するファイル・マネージャー・エントリーにしかるべく注釈がつけられる（ステップ１１２）。ファイルは、一定時間経過後削除されるよう注釈されるか、あるいはユーザーによって削除されるよう選択されることが可能であり、これは例えばユーザーがファイルを（ウィンドウズ（登録商標）オペレーティング・システム環境における）ごみ箱などに入れることなどによって実現される。ディスク１０におけるファイルのセットあるいはサブセットにおいては、あるメカニズムが、ユーザープロフィールに応じてこれらのいくつかのファイルを削除のためにマークすることができる。
【００２１】
したがって、ファイルが削除される際、削除可能なファイルがいくつか存在する場合がある。ファイルは、例えば命令された書き取り操作を実行するためにディスク上に場所を空けなければならないときなどに削除される。あるいはユーザーが空き領域を作るように命令する場合もある。
【００２２】
図３は、本発明の実施形態に従ったファイルの削除操作のステップをフローチャートで示す。図３における符号は以下のようなステップに対応する。
２００  削除操作を作動させる；
２０２  削除可能なファイルが複数存在するか？
２０４  １つのファイルを削除する；
２０６  フラグメンテーションを減少させるために削除するファイルを選択する；
２０８  選択されたファイルを削除する；
２１０  ファイル・マネージャーを更新する。
【００２３】
削除操作が作動されると（ステップ２００）、ファイル・マネージャー３０に対して問い合わせがなされ（ステップ２０２）、削除可能なファイルが複数存在するかが決定される。ファイルは、削除されるよう注釈が付けられている場合において削除可能である。ファイルは書込み操作において要される空き領域を提供することができるときに限って削除されることが可能である。これは複数のファイルの中からいくつかのファイルが削除されなければならない場合もあることを意味する。削除可能なファイルが１つしか存在しない場合はこれが削除され（ステップ２０４）、ファイル・マネージャー３０がこれに応じて更新される（ステップ２１０）。削除可能なファイルが複数存在する場合は、フラグメンテーションを減少させるために１つのファイルが削除されるファイルとして選択される（ステップ２０６）。本発明の実施形態における削除されるファイルを選択するに当たってのオプションは以下に示される。次に前記の選択されたファイルは永久的に削除され（ステップ２０８）、ファイル・マネージャー３０がこれに応じて更新される（ステップ２１０）。
【００２４】
一旦複数のファイルが削除可能であると決定されると、次にファイル・デフラグメンテーション又は空き領域デフラグメンテーションを最適化するために特定のファイルが選択される。削除するテキストファイルを決定するための判断基準はいくつか存在する。そのうちの１つは、削除対象の候補となるファイルの中から最もフラグメント化されているファイルを削除することによってファイル・フラグメンテーションの度合いを最適化する（低下させる）方法である。より好適には、空き領域フラグメンテーションの度合いを低くすることが次に書き込まれるファイルにとって好都合であることから、ファイル・デフラグメンテーションの度合いとともに空き領域デフラグメンテーションの度合いを最適化する方法がある。
【００２５】
前記の最適化は、フラグメントの数のみならずその大きさを考慮することによってより改善されることが可能である。
【００２６】
また、ファイル・フラグメンテーションの度合いと空き領域フラグメンテーションの度合いとの両方を一緒に最適化しようとする割り当て策略及び削除策略を選択することによってより低いフラグメンテーションの度合いが得られる。
【００２７】
次に以下に示される３つのファイルを格納し、かつ多少の空き領域をまだ有する（簡略化された）ファイルシステムを参照されたい。
【００２８】
【外１】
2004517399.tif 000003
ファイルＡは２つのフラグメント、ファイルＢは３つのフラグメントそしてファイルＣは３つのフラグメント、から構成される。空き領域Ｆは２つのフラグメントから構成される。したがってここには合計１０のフラグメントが存在する。
【００２９】
ここでファイルＡ及びファイルＢがファイル・マネージャー３０において注釈されている削除対象の候補であるとし、ファイルＣはそのまま手を付けずに置いておくべきであると仮定すると、削除の対象をファイルＡ又はファイルＢのいずれか１つを選択しなければならない。ここで最もフラグメント化されたファイルを選択した場合は、ファイルＢが削除され、以下に示されるような結果が得られる。
【００３０】
【外２】
2004517399.tif 000004
ファイルＡは２つのフラグメント、ファイルＣは３つのフラグメント、そして空き領域Ｆは４つのフラグメントから構成される。したがってここでのフラグメントの合計は９になる。ここでは空き領域のフラグメンテーションの度合いが高いことから、次に記憶されるファイルもおそらく細かくフラグメント化されると思われる。そこでファイル・フラグメンテーションだけを最適化するのに対してファイル・フラグメンテーションの度合いと空き領域フラグメンテーションの度合いとの両方を最適化した場合、ファイルＡが削除され、以下のような結果が得られる。
【００３１】
【外３】
2004517399.tif 000005
ファイルＢは３つのフラグメント、ファイルＣは３つのフラグメント、そして空き領域Ｆは２つの空き領域から構成され、この合計は８つのフラグメントとなる。さらにここにおいては空き領域のフラグメンテーションの度合いが低いことからおそらく次に記憶されるファイルのフラグメンテーションの度合いも低くなる。
【００３２】
しかし、どの選択オプションを用いるにせよ、削除するファイルの決定は、ファイル・マネージャー３０との問い合わせによって実施される。また削除可能なファイルの集合における１つ１つのファイルについてそのファイルの削除によるファイル・フラグメンテーション及び空き領域フラグメンテーションへの影響が算出される。
【００３３】
上記の選択手順は図４において示され、ここにおける符号はそれぞれ以下のステップに対応する。
４００  各ファイルについてその削除によるファイル・フラグメンテーションへの影響を算出する
４０２  各ファイルについてその削除による空き領域フラグメンテーションへの影響を算出する
４０４  各ファイルについてファイル・フラグメンテーションと空き領域フラグメンテーションとの和を求める
４０６  算出された和をクラスターの数に応じて標準化する
４０８  最適なファイルを選択する
上記において空き領域フラグメンテーションへの影響は、（各ファイルの）削除による空き領域フラグメンテーションの変化を算出することによって得られる（ステップ４０２）。空き領域はファイルの削除によって新たに生じうる（不都合）が、いくつかの空き領域が接続しあって、新たな空き領域を形成する場合がある（好都合）。一般に空き領域の数はファイルの削除によって増加する（すなわち正の変化である）。
【００３４】
次にファイル・フラグメンテーションの変化と空き領域フラグメンテーションの変化との和（常にゼロ又は負の数である）が最も低いファイルが決定される（ステップ４０４）。
【００３５】
このメカニズムは大きなファイルにとってより好適であるため（大きいファイルのほうが統計的に合体しやすいということから）、好ましくはさらにファイルの大きさについての標準化がなされる（ステップ４０６）。これはファイルにおけるクラスターの数で上記の和を割ることによってなされる。その後最適なファイルが選択される（ステップ４０８）。
【００３６】
また別の実施形態においては、ステップ４０４で得られた結果から削除するファイルが選択されることも可能である。
【００３７】
削除可能であるファイルのそれぞれについては、ファイル削除によるファイル・フラグメンテーションへの影響が算出される（ステップ４００）。これはファイルの削除が完了したディスクにおけるフラグメント数の変化であり、削除されるファイルのフラグメント数だけ減少する。すなわちこれは常に負の変化である。
【図面の簡単な説明】
【図１】
デジタル・ビデオレコーダの略図である。
【図２】
ファイルの書込み操作を示すフローチャートである。
【図３】
本発明の実施形態に従ったファイルの削除操作を示すフローチャートである。
【図４】
本発明の実施形態に従ったファイルの選択操作を示すフローチャートである。
【国際公開パンフレット】
2004517399.tif 000006
2004517399.tif 000007
2004517399.tif 000008
2004517399.tif 000009
2004517399.tif 000010
2004517399.tif 000011
2004517399.tif 000012
2004517399.tif 000013
2004517399.tif 000014
2004517399.tif 000015
2004517399.tif 000016
2004517399.tif 000017