(57)【要約】【課題】  ファイルを保存するディスクの空間を割り当てる方法及び装置を提供する。【解決手段】  （ａ）所定基準値以上のサイズを有する空いている区間を組合わせて構成できる第１集合を検索するステップと、（ｂ）第１集合のうち、総サイズがデータのサイズ以上である第２集合を検索するステップと、（ｃ）第２集合のうち、所定基準点からの探索時間が最も短い集合をデータに割り当てるステップと、を含むことを特徴とするデータを記録するためにディスクの空間を割り当てる方法である。これにより、ディスクに存在する空いている区間を基準点からの距離だけでなく、サイズによって変わる探索時間を考慮して空いている空間を割り当てるので、単純に基準点からの距離のみを考慮して割当てる場合より探索時間を短縮させうる。【選択図】      図２
2007310878.tif 000002
【特許請求の範囲】
【請求項１】
データを記録するためにディスクの空間を割り当てる方法において、
（ａ）所定基準値以上のサイズを有する空いている区間を組合わせて構成できる第１集合を検索するステップと、
（ｂ）前記第１集合のうち、総サイズが前記データのサイズ以上である第２集合を検索するステップと、
（ｃ）前記第２集合のうち、所定基準点からの探索時間が最も短い集合を前記データに割り当てるステップとを含むことを特徴とする方法。
【請求項２】
前記（ｂ）ステップで検索された集合がない場合に、
（ｄ）前記基準点から所定範囲内に存在し、前記データのサイズ以上の空いている区間を前記データに割り当てるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
（ｅ）前記基準点から前記所定範囲内に前記データのサイズ以上の空いている区間が存在していない場合に、前記所定範囲外の空いている区間のうち、前記データのサイズ以上の区間を前記データに割り当てるステップをさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】
（ｆ）前記ディスクに前記データのサイズ以上の空いている区間がない場合に、前記ディスクの空いている区間のうち、最大区間を前記データの一部に割り当てるステップをさらに含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記（ｆ）ステップは、
（ｇ）前記割当てられた最大区間が終わる点を新たな基準点とし、前記データのサイズから前記最大区間のサイズを減算した値を新たなデータのサイズとして、前記（ａ）ステップないし前記（ｆ）ステップを再び行うステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記（ｇ）ステップは、
前記ディスクにそれ以上空いている区間が存在していないか、または前記データが成功的に割当てられるまで、前記（ａ）ステップないし前記（ｆ）ステップを反復して行うことを特徴とする請求項５に記載の方法。
【請求項７】
前記ディスクにそれ以上空いている区間が存在していない場合に、エラーメッセージを出力するステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項８】
前記ディスクにそれ以上空いている区間が存在していない場合に、エラーメッセージを出力するステップをさらに含むことを特徴とする請求項６に記載の方法。
【請求項９】
前記（ｂ）ステップは、
（ｂ１）所定範囲の値を有するｉに対して、前記ディスクの空いている区間のうち、サイズが２ｉ個のブロック数以上である区間で構成された集合であるＬｉを生成するステップと、
（ｂ２）前記各ｉに対して、各Ｌｉに属する区間のうち、所定数の区間で構成された集合であるＷｉを生成するステップと、
（ｂ３）前記各ｉに対して、各Ｗｉに属する区間のうち、ｗ個の連続的に位置した区間であるｚｉ１，ｚｉ２，．．．，ｚｉｗで構成しうる集合の集合であるＺｉを生成するステップとを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記（ｃ）ステップは、
（ｃ１）前記各ｉに対して、各Ｚｉに属する集合のうち、最小探索時間を有する第３集合を選択するステップと、
（ｃ２）前記選択された第３集合のうち、最小探索時間を有する集合を選択するステップと、
（ｃ３）前記（ｂ２）ステップで選択された集合に属する空いている区間を前記データに割り当てるステップと、を含むことを特徴とする請求項９に記載の方法：
このとき、ｌ（ｚｉ１）＋ｌ（ｚｉ２）＋．．．＋ｌ（ｚｉｗ）≧ｒｅｑ＿ｌｅｎであり、ｌ（ｚｉ１）＋ｌ（ｚｉ２）＋．．．＋ｌ（ｚｉ（ｗ−１））＜ｒｅｑ＿ｌｅｎであり、ｌ（ｘ）は、区間ｘのサイズ、ｒｅｑ＿ｌｅｎは、前記データのサイズである。
【請求項１１】
ｉ１≦ｉ≦ｉ２であり、
ｉ２＝ｍｉｎ（Ｎ，]ｌｏｇ２（ｒｅｑ＿ｌｅｎ[）、ｉ１＝ｍａｘ（［ｌｏｇ２（ｒｅｑ＿ｌｅｎ）］−Ｃ,０）であることを特徴とする請求項１０に記載の方法：
このとき、ｒｅｑ＿ｌｅｎは、前記データのサイズ、Ｃは、定数、Ｎ＝［ｌｏｇ２（Ｖ／Ｂ）］であり、Ｖは、前記ディスク全体の容量、Ｂは、ファイルシステムのブロックサイズである。また、］［は、元来値をそれ以上の最も近い整数値に上げる数学演算子であり、［］は、元来値をそれ以下の最も近い整数値で数下げをする数学演算子である。
【請求項１２】
前記各Ｗｉは、前記生成された各Ｌｉに属する区間のうち、前記基準点の左側に位置したｕ個の区間であるｌ１，ｌ２，ｌ３，．．．，ｌｕ及び右側に位置したｖ個の区間であるｒ１，ｒ２，ｒ３，．．．，ｒｖで構成されることを特徴とする請求項９に記載の方法：
このとき、ｕ≦］ｒｅｑ＿ｌｅｎ／２ｉ［を満足し、ｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ）≧ｒｅｑ＿ｌｅｎと同時にｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ−１）＜ｒｅｑ＿ｌｅｎであるか、またはｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ）＜ｒｅｑ＿ｌｅｎであり、
ｖ≦］ｒｅｑ＿ｌｅｎ／２ｉ［を満足し、ｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ）≧ｒｅｑ＿ｌｅｎと同時にｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ−１）＜ｒｅｑ＿ｌｅｎであるか、またはｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ）＜ｒｅｑ＿ｌｅｎであり、
ｌ（ｘ）は、区間ｘのサイズ、ｒｅｑ＿ｌｅｎは、前記データのサイズであり、］［は、元来値をそれ以上の最も近い整数値に上げる数学演算子であり、［］は、元来値をそれ以下の最も近い整数値で数下げをする数学演算子である。
【請求項１３】
前記（ｃ）ステップは、
前記基準値を異ならせることによって検索される前記第２集合のグループそれぞれで、前記基準点からの探索時間が最も短い集合を選択するステップと、
前記選択された集合のうち、最も探索時間の短い最適集合を選択するステップと、
前記選択された最適集合の空いている区間に前記データを割り当てるステップと、を含むことを特徴とする請求項１に記載の方法。
【請求項１４】
前記基準点から所定範囲内に存在し、前記データのサイズ以上である空いている区間が複数である場合に、そのうち、前記基準点から最も近い区間を前記データに割り当てることを特徴とする請求項２に記載の方法。
【請求項１５】
前記所定範囲外の空いている区間のうち、前記データのサイズ以上の区間が複数である場合に、そのうち、前記基準点から最も近い区間を前記データに割り当てることを特徴とする請求項３に記載の方法。
【請求項１６】
請求項１ないし１５のうち何れか一項に記載の方法をコンピュータで実行させるための方法を記録したコンピュータで読み取り可能な記録媒体。
【請求項１７】
データを記録するためにディスクの空間を割り当てる装置において、
所定基準値以上のサイズを有する空いている区間を組合わせて構成しうる集合のうち、総サイズが前記データのサイズ以上である集合を検索し、前記検索された集合のうち、所定基準点からの探索時間が最も短い集合を前記データに割り当てる第１アルゴリズムを行う第１アルゴリズム実行部を備えることを特徴とする装置。
【請求項１８】
前記第１アルゴリズムによって検索された集合のない場合に、前記基準点から所定範囲内に存在し、前記データのサイズ以上である空いている区間を前記データに割り当てる第２アルゴリズムを行う第２アルゴリズム実行部をさらに備えることを特徴とする請求項１７に記載の装置。
【請求項１９】
前記第２アルゴリズムは、前記基準点から前記所定範囲内に前記データのサイズ以上である空いている区間が存在していない場合に、前記所定範囲外の空いている区間のうち、前記データのサイズ以上である区間を前記データに割り当てることを特徴とする請求項１８に記載の装置。
【請求項２０】
前記第２アルゴリズムは、前記所定範囲外にも前記データのサイズ以上である空いている区間がなければ、前記ディスクの空いている区間のうち最大区間を前記データの一部に割り当てることを特徴とする請求項１９に記載の装置。
【請求項２１】
前記最大区間が割当てられた場合に、前記最大区間が終わる点を新たな基準点に設定し、前記データのサイズから前記最大区間のサイズを減算した値を新たなデータのサイズに設定して、前記第１アルゴリズム実行部が前記第１アルゴリズムを再び行うように制御する制御部をさらに備えることを特徴とする請求項２０に記載の装置。
【請求項２２】
前記制御部は、前記ディスクにそれ以上空いている区間が存在していないか、または前記データが成功的に割当てられるまで前記制御を反復して行うことを特徴とする請求項２１に記載の装置。
【請求項２３】
前記第２アルゴリズム実行部は、
前記ディスクにそれ以上空いている区間が存在していなければ、エラーメッセージを出力することを特徴とする請求項２０に記載の装置。
【請求項２４】
前記第２アルゴリズム実行部は、
前記ディスクにそれ以上空いている区間が存在していなければ、エラーメッセージを出力することを特徴とする請求項２２に記載の装置。
【請求項２５】
前記第１アルゴリズム実行部は、
所定範囲の値を有するｉに対して、各Ｉごとに前記ディスクの空いている区間のうち、サイズが２ｉ個のブロック数以上である区間で構成された集合であるＬｉを生成するＬｉ生成部と、
前記各ｉに対して各Ｌｉに属する区間のうち、所定数の区間で構成された集合であるＷｉを生成するＷｉ生成部と、
前記各ｉに対して各Ｗｉに属する区間のうち、ｗ個の連続的に位置した区間であるｚｉ１，ｚｉ２，．．．，ｚｉｗで構成しうる集合の集合であるＺｉを生成するＺｉ生成部とを備えることを特徴とする請求項１７に記載の装置。
【請求項２６】
前記各ｉに対して、各Ｚｉに属する集合のうち、最小探索時間を有する集合を選択する第１選択部と、
前記第１選択部で選択された集合のうち、最小探索時間を有する集合を選択する第２選択部と、
前記第２選択部で選択された集合に属する空いている区間を前記データに割り当てる割当部と、を備えることを特徴とする請求項２５に記載の装置：
このとき、ｌ（ｚｉ１）＋ｌ（ｚｉ２）＋．．．＋ｌ（ｚｉｗ）≧ｒｅｑ＿ｌｅｎであり、ｌ（ｚｉ１）＋ｌ（ｚｉ２）＋．．．＋ｌ（ｚｉ（ｗ−１））＜ｒｅｑ＿ｌｅｎであり、ｌ（ｘ）は、区間ｘのサイズ、ｒｅｑ＿ｌｅｎは、前記データのサイズである。
【請求項２７】
ｉ１≦ｉ≦ｉ２であり、
ｉ２＝ｍｉｎ（Ｎ，]ｌｏｇ２（ｒｅｑ＿ｌｅｎ[）、ｉ１＝ｍａｘ（［ｌｏｇ２（ｒｅｑ＿ｌｅｎ）］−Ｃ,０）であることを特徴とする請求項２６に記載の装置：
このとき、ｒｅｑ＿ｌｅｎは、前記データのサイズ、Ｃは、定数、Ｎ＝［ｌｏｇ２（Ｖ／Ｂ）］であり、Ｖは、前記ディスク全体の容量、Ｂは、ファイルシステムのブロックサイズであり、］［は、元来値をそれ以上の最も近い整数値に上げる数学演算子であり、［］は、元来値をそれ以下の最も近い整数値デ数下げをする数学演算子である。
【請求項２８】
前記各Ｗｉは、前記生成された各Ｌｉに属する区間のうち、前記基準点の左側に位置したｕ個の区間であるｌ１，ｌ２，ｌ３，．．．，ｌｕ及び右側に位置したｖ個の区間であるｒ１，ｒ２，ｒ３，．．．，ｒｖで構成されることを特徴とする請求項２６に記載の装置：
このとき、ｕ≦］ｒｅｑ＿ｌｅｎ／２ｉ［を満足し、ｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ）≧ｒｅｑ＿ｌｅｎと同時にｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ−１）＜ｒｅｑ＿ｌｅｎであるか、またはｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ）＜ｒｅｑ＿ｌｅｎであり、
ｖ≦］ｒｅｑ＿ｌｅｎ／２ｉ［を満足し、ｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ）≧ｒｅｑ＿ｌｅｎと同時にｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ−１）＜ｒｅｑ＿ｌｅｎであるか、またはｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ）＜ｒｅｑ＿ｌｅｎであり、
ｌ（ｘ）は、区間ｘのサイズ、ｒｅｑ＿ｌｅｎは、前記データのサイズであり、］［は、元来値をそれ以上の最も近い整数値に上げる数学演算子であり、［］は、元来値をそれ以下の最も近い整数値で数下げをする数学演算子である。
【請求項２９】
前記第１アルゴリズム実行部は、
前記基準値を異ならせることによって検索される前記第２集合のグループそれぞれで前記基準点からの探索時間が最も短い集合を選択し、前記選択された集合のうち最も探索時間の短い最適集合を選択し、前記選択された最適集合の空いている区間に前記データを割り当てることを特徴とする請求項１７に記載の装置。
【請求項３０】
前記第２アルゴリズム実行部は、前記基準点から所定範囲内に存在し、前記データのサイズ以上である空いている区間が複数である場合に、そのうち、前記基準点から最も近い区間を前記データに割り当てることを特徴とする請求項１８に記載の装置。
【請求項３１】
前記第２アルゴリズム実行部は、前記所定範囲外の空いている区間のうち、前記データのサイズ以上である区間が複数である場合に、そのうち、前記基準点から最も近い区間を前記データに割り当てることを特徴とする請求項１９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ファイルシステムに係り、さらに詳細には、ファイルを記録するためのディスクの空間を割り当てる方法及び装置に関する。
【背景技術】
【０００２】
ＦＡＴ、ＸＦＳ、Ｅｘｔ２など現存する多様なファイルシステムが指向する目的のうち一つは、ディスクにファイルを保存する時に、そのファイルを構成するデータを最大限近い所に位置させることである。これは、ディスクヘッドがファイルを読み取る時にかかる探索時間を最小化するためであるが、一つのファイルを構成するデータが近接性を有して保存されるためには、ディスクの空いている空間を適切に割当てねばならない。
【０００３】
図１は、従来の技術によって空いている空間を割り当てる方法を説明するための図である。図１に示されたａないしｊは、それぞれ一つのブロックを表すが、ブロックのサイズは、ファイルシステムによって可変的である。図１で、暗いブロックは、既に他のデータが割当てられたブロックを表し、明るいブロックは、空いているブロックを表す。基準点は、これから保存しようとするデータ（以下、目的データと称す）と関連したデータが最後に保存された位置を表すが、言い換えれば、目的データが保存された場合に、ディスクヘッドが目的データを読み取る直前に位置する場所となる。
【０００４】
直観的に、かつ経験的に、距離が遠いほど探索時間が長くなるので、従来の技術では、基準点から近い所に位置した空いているブロックから割り当て始めて目的データのサイズをカバーするまで空いているブロックを順次に割り当て始める。したがって、図１のように、空いているブロックが位置する場合に、従来の技術によれば、ｄ、ｆ、ｊ、ｊの順に割り当て始める。
【０００５】
しかし、多数のブロックを読み取る場合に、総距離と総探索時間とが必ずしも正比例するものではない。それは、同じサイズのファイルを保存しても、多数の離隔されたブロックに分散して保存することより一つの連続されたブロックに保存する場合に、そのファイルを読み取るための探索時間がさらに短縮されるので、基準点からの距離だけでなく、このような要因も考慮せねばならないためである。多数のブロックに一つのファイルと関連したデータが分散されて保存された場合に、正確な探索時間は、ファイルシステムによる探索曲線によって決定される。したがって、従来の技術によれば、図１のように、例えば、目的データのサイズが二ブロックサイズとするとき、探索曲線によってｉ及びｊを割り当てることが最も短い探索時間を有する場合にも、基準点からの距離のみを考慮して空いている空間を割り当てるので、結局、ｄ、ｆを割り当てて最適化された結果を得られないという問題がある。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、割当てられる空いている区間のサイズによる実際探索時間を考慮してディスクの空間を割り当てる装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記目的を達成するための本発明は、データを記録するためにディスクの空間を割り当てる方法において、（ａ）所定基準値以上のサイズを有する空いている区間を組合わせて構成できる集合のうち、総サイズが前記データのサイズ以上である集合を検索するステップと、（ｂ）前記検索された集合のうち、所定基準点からの探索時間が最も短い集合を前記データに割り当てるステップと、を含むことを特徴とする。
【０００８】
このとき、前記（ａ）ステップで検索された集合がない場合に、（ｃ）前記基準点から所定範囲内に存在し、前記データのサイズ以上である空いている区間を前記データに割り当てるステップをさらに含むことが望ましい。
【０００９】
また、（ｄ）前記基準点から前記所定範囲内に前記データのサイズ以上である空いている区間が存在していない場合に、前記所定範囲外の空いている区間のうち、前記データのサイズ以上である区間を前記データに割り当てるステップをさらに含むことが望ましい。
【００１０】
また、（ｅ）前記所定範囲外にも前記データのサイズ以上である空いている区間がない場合に、前記ディスクの空いている区間のうち最大区間を前記データに割り当て、前記ディスクに空いている区間が存在していない場合にエラーメッセージを出力するステップと、（ｆ）前記（ｄ）ステップで前記最大区間が割当てられた場合に、前記最大区間が終わる点を新たな基準点とし、前記データのサイズから前記最大区間のサイズを減算した値を新たなデータのサイズとして、前記（ａ）ステップないし前記（ｅ）ステップを行うステップとをさらに含むことが望ましい。
【００１１】
また、前記（ａ）ステップないし前記（ｆ）ステップは、前記エラーメッセージが出力されるか、または前記データが成功的に割当てられるまで反復して行うことが望ましい。
【００１２】
また、前記（ｃ）ステップで、前記基準点から所定範囲内に存在し、前記データのサイズ以上である空いている区間が複数である場合に、そのうち、前記基準点から最も近い区間を前記データに割り当てることが望ましい。
【００１３】
また、前記（ｄ）ステップで、前記所定範囲外の空いている区間のうち、前記データのサイズ以上である区間が複数である場合に、そのうち、前記基準点から最も近い区間を前記データに割り当てることが望ましい。
【００１４】
また、本発明は、前記ディスク空間の割り当て方法をコンピュータで実行させるためのコンピュータで読み取り可能な記録媒体を提供する。
【００１５】
また、本発明は、データを記録するためにディスクの空間を割り当てる装置において、所定基準値以上のサイズを有する空いている区間を組合わせて構成できる集合のうち、総サイズが前記データのサイズ以上である集合を検索し、前記検索された集合のうち、所定基準点からの探索時間が最も短い集合を前記データに割り当てる第１アルゴリズムを行う第１アルゴリズム実行部を備えることを特徴とする。
【００１６】
前記ディスク空間の割り当て装置は、前記第１アルゴリズムによって検索された集合がない場合に、前記基準点から所定範囲内に存在し、前記データのサイズ以上である空いている区間を前記データに割り当て、前記基準点から前記所定範囲内に前記データのサイズ以上である空いている区間が存在していない場合に、前記所定範囲外の空いている区間のうち、前記データのサイズ以上である区間を前記データに割り当て、前記所定範囲外にも前記データのサイズ以上である空いている区間がなければ、前記ディスクの空いている区間のうち、最大区間を前記データに割り当て、前記ディスクに空いている区間が存在していない場合に、エラーメッセージを出力する第２アルゴリズムを行う第２アルゴリズム実行部をさらに備えることが望ましい。
【００１７】
また、前記第２アルゴリズムによって前記最大区間が割当てられた場合に、前記最大区間が終わる点を新たな基準点に設定し、前記データのサイズから前記最大区間のサイズを減算した値を新たなデータのサイズに設定して、前記第１アルゴリズム実行部が前記第１アルゴリズムを行うように制御する制御部をさらに備えることが望ましい。
【発明の効果】
【００１８】
本発明によれば、ディスクに存在する空いている区間を基準点からの距離だけでなく、サイズによって変わる探索時間を考慮して空いている空間を割り当てるので、単純に基準点からの距離のみを考慮して割り当てる場合より探索時間を短縮させうる。
【発明を実施するための最良の形態】
【００１９】
以下、添付された図面を参照して、本発明の望ましい実施形態を詳細に説明する。
【００２０】
図２は、本発明によってディスクの空間を割り当てる過程を示すフローチャートである。
【００２１】
ステップ２１０では、第１アルゴリズムを行うが、第１アルゴリズムは、基準点から一定距離内にある一定サイズ以上の空いている区間を利用して割当てを試みる方法であって、これについての詳細な説明は、図３を参照して後述する。ここで、区間は、一つのブロックまたは連続する複数のブロックを意味し、以下、同一である。
【００２２】
ステップ２２０では、第１アルゴリズムによって目的データのための空いている空間が何れも割当てられたかを判断するが、割当てが完了していない場合に、ステップ２３０で第２アルゴリズムを行う。第２アルゴリズムは、サイズの大きい空いている区間を優先的に割り当てる方法であって、これについての詳細な説明は、図４を参照して後述する。もし、第１アルゴリズムによって目的データのための空いている空間が何れも割当てられたら、手順は終了する。
【００２３】
ステップ２４０では、第２アルゴリズムによって目的データの割当てが成功的に完了したか否かを判断し、ステップ２５０では、割当てが成功的に完了していない場合に、ディスクにまだ空いている空間が存在するか否かを判断し、ステップ２６０では、ステップ２５０での判断結果、ディスクにまだ空いている空間が存在する場合に、基準点及び目的データサイズを再設定して、第１アルゴリズムを再び行うための新たな入力値を生成する。このような第１アルゴリズム及び第２アルゴリズムは、目的データのための空いている空間が成功的に割当てられるか、またはディスクにそれ以上目的データを保存しうる空間がなくなるまで、交互に反復して行われる。
【００２４】
図３は、本発明による第１アルゴリズムを行う過程を示すフローチャートである。
【００２５】
一般的に、ほとんどのファイルシステムは、空いている空間についてのメタデータを管理するが、例えば、ＸＦＳでは、Ｂ＋ツリーを利用して空いている空間をその位置及びサイズによって整列して管理する。本発明では、それ以外にもＬｉというメタデータを使用するが、Ｌｉは、所定範囲の値を有するｉに対して、前記ディスクの空いている区間のうち、サイズが２ｉ個のブロック数以上である区間で構成された集合である。すなわち、Ｌ１には、ディスク内で２１個のブロック数以上のサイズを有する空いている区間が含まれる。但し、全てのｉに対してＬｉを生成せず、制限された範囲の値を有するｉに対してＬｉを生成することが経済的な側面で望ましいが、本発明では、ｉ１≦ｉ≦ｉ２であるｉに対してのみＬｉを生成する。
【００２６】
ステップ３１０では、このようなＬｉを生成するが、ここには、ｉ１及びｉ２を決定する過程が含まれる。ｉ１及びｉ２は、ｉの範囲、すなわち、第１アルゴリズムで目的データを割り当てるために組合わせる空いている区間の最小サイズを決定する。
【００２７】
例えば、ｉ２＝ｍｉｎ（Ｎ，]  ｌｏｇ２（ｒｅｑ＿ｌｅｎ）［）、ｉ１＝ｍａｘ（［ｌｏｇ２（ｒｅｑ＿ｌｅｎ）］−Ｃ，０）のように決定しうるが、ｒｅｑ＿ｌｅｎは、目的データのサイズ、Ｃは、定数、Ｎ＝［ｌｏｇ２（Ｖ／Ｂ）］であり、Ｖは、前記ディスク全体の容量、Ｂは、ファイルシステムのブロックサイズである。一方、］［は切上げ、［］は切下げを表す数学演算子である。すなわち、目的データのサイズによってｉの最大値が決定され、定数Ｃによってｉの最小値が決定される。
【００２８】
ステップ３２０では、Ｗｉ、Ｚｉ、Ｍｉを決定する。
【００２９】
Ｗｉは、各ｉに対してＬｉに属する空いている区間のうち、所定数の区間で構成された集合であるが、Ｌｉに属する空いている区間のうち、左側に位置したｕ個の区間及び右側に位置したｖ個の区間で構成される。各ｉに対してＬｉの全ての空いている区間を検索するのは経済的でないので、その検索範囲を制限したものであるが、例えば、ｕは、以下の条件によるようにしうる。
【００３０】
（１）ｕ≦］ｒｅｑ＿ｌｅｎ／２ｉ［
（２）ｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ）≧ｒｅｑ＿ｌｅｎと同時にｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ−１）＜ｒｅｑ＿ｌｅｎであるか、またはｌ（ｌ１）＋ｌ（ｌ２）＋．．．ｌ（ｌｕ）＜ｒｅｑ＿ｌｅｎ
同様に、ｖも、以下の条件によるようにしうる。
【００３１】
（１）ｖ≦］ｒｅｑ＿ｌｅｎ／２ｉ［
（２）ｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ）≧ｒｅｑ＿ｌｅｎと同時にｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ−１）＜ｒｅｑ＿ｌｅｎであるか、またはｌ（ｒ１）＋ｌ（ｒ２）＋．．．ｌ（ｒｖ）＜ｒｅｑ＿ｌｅｎ
前記数学式で、ｌ（ｘ）は、区間ｘのサイズを表す関数である。
【００３２】
すなわち、前記数学式によれば、Ｌｉで基準点を中心に左側に位置した区間のうち、目的データのサイズ以上にする最小数であるｕ個の区間であるｌ１，ｌ２，ｌ３，．．．，ｌｕ及び基準点の右側に位置した区間のうち、目的データのサイズ以上にする最小数であるｖ個の空いている区間であるｒ１，ｒ２，ｒ３，．．．，ｒｖがＷｉを構成する。このとき、ｌｋよりはｌｋ＋１が基準点からさらに遠く離隔された区間である。一方、Ｌｉで基準点の左側に存在する区間の総和のサイズが目的データのサイズより小さくｕを定めることもでき、これは、基準点の右側に存在する空いている区間についても同様である。それは、第１アルゴリズムは、Ｗｉに属する区間を組合わせて目的データ以上の空いている空間を確保して目的データを割り当てることが目的であるが、ｕ個の区間の和が目的データのサイズより小さくても、基準点の右側にあるｖ個の区間と組合わせれば、その総和のサイズが目的データのサイズより大きくなることもあるためである。
【００３３】
Ｚｉは、各ｉに対して、Ｗｉに属する区間のうち、ｗ個の連続的に位置した区間であるｚｉ１，ｚｉ２，．．．，ｚｉｗで構成できる集合の集合である。Ｗｉには、ｕ＋ｖ個の区間があるが、これらのうち、連続的に位置したｗ個の区間で組合わせ可能な集合を何れも含むことがＺｉである。言い換えれば、Ｚｉは、集合の集合である。このとき、ｗは、目的データのサイズ以上である空いている空間のサイズを確保するための最小値である。すなわち、ｌ（ｚｉ１）＋ｌ（ｚｉ２）＋．．．＋ｌ（ｚｉｗ）≧ｒｅｑ＿ｌｅｎであり、ｌ（ｚｉ１）＋ｌ（ｚｉ２）＋．．．＋ｌ（ｚｉ（ｗ−１））＜ｒｅｑ＿ｌｅｎである。
【００３４】
Ｍｉは、各ｉに対してＺｉに属する集合のうち、最小の探索時間を有する集合である。すなわち、前述したように、Ｚｉには、複数の集合がありうるが、そのうち、基準点からの探索時間が最も短い集合がＭｉとなる。言い換えれば、各ｉに対して、Ｗｉに属する区間を組合わせて目的データを何れも割り当てる時に、最適の組合わせが、すなわち、Ｍｉとなる。
【００３５】
ステップ３３０では、各ｉに対して決定したＭｉのうち、最小の探索時間を有する集合を決定する。ステップ３４０では、Ｍｉの最小値が存在するか否かを判断し、ステップ３５０では、Ｍｉの最小値が存在する場合に、該当集合に属する区間を目的データに割り当てる。Ｍｉの最小値が存在していない場合には、Ｗｉに属する全ての区間の総和が目的データのサイズより小さい場合である。本発明によれば、Ｍｉの最小値が存在していない場合、第１アルゴリズムが終了し、第２アルゴリズムが行われる。以下で、第２アルゴリズムについて詳細に説明する。
【００３６】
図４は、本発明による第２アルゴリズムを行う過程を示すフローチャートである。
【００３７】
ステップ４１０では、所定範囲内で目的データサイズ以上である空いている区間を検索する。ここで、所定範囲は、基準点から一定距離内に限定することが望ましい。ステップ４２０では、ステップ４１０での検索が成功したか否かを判断し、ステップ４７０では、ステップ４１０での検索が成功した場合に、検索された区間を目的データに割り当てる。このとき、検索された区間が複数である場合には、探索時間を短縮させるために基準点から最も近い所に位置した区間を割り当てることが望ましい。
【００３８】
ステップ４３０では、ステップ４１０での検索が失敗した場合に、ディスク全体に目的データサイズ以上である空いている区間が存在するか否かを判断し、ステップ４７０では、ステップ４３０での判断結果、ディスク全体に目的データサイズ以上である空いている区間が存在する場合に、該当区間を目的データに割り当てる。この時にも目的データサイズ以上である空いている区間が複数である場合には、探索時間を短縮するために基準点から最も近い所に位置した区間を割り当てることが望ましい。
【００３９】
ステップ４４０では、ステップ４３０での判断結果、ディスク全体に目的データサイズ以上である空いている区間が存在していないと判断された場合に、ディスク全体に区間のサイズと関係なく、空いている区間が存在するか否かを判断する。ステップ４６０では、ステップ４４０での判断結果、空いている区間がない場合にエラーメッセージを出力する。ステップ４５０では、ステップ４４０での判断結果、空いている区間が存在する場合に存在する区間のうち、最大区間を選択し、ステップ４７０では、ステップ４５０で選択した最大区間を目的データの一部に割り当てる。
【００４０】
一方、ステップ４１０では、所定範囲内で目的データサイズ以上である空いている区間を探すために各ブロックを実際に検査せねばならないが、ステップ４３０及びステップ４４０では、直接検査せず、ファイルシステムで管理する目録を参照して容易に分かる。例えば、ＸＦＳでは、空いている空間に関する情報を位置及びサイズによってＢ＋ツリーで管理するので、これを参照して検索しうる。
【００４１】
図５は、本発明によってディスクの空間を割り当てる装置の構造を示すフローチャートである。図５を参照するに、本発明によるディスク空間の割当て装置は、第１アルゴリズム実行部５１０、第２アルゴリズム実行部５２０及び制御部５３０を備える。
【００４２】
第１アルゴリズム実行部５１０は、前述した第１アルゴリズムを行って目的データのための空いている空間を割り当てる。
【００４３】
このような第１アルゴリズム実行部５１０は、Ｌｉ生成部５１１、Ｗｉ生成部５１２、Ｚｉ生成部５１３、第１選択部５１４、第２選択部５１５及び割当部５１６を備える。
【００４４】
Ｌｉ生成部５１１は、ｉ１及びｉ２を決定し、これにより、Ｌｉを生成し、Ｗｉ生成部５１２は、ＬｉからＷｉを生成する。
【００４５】
Ｚｉ生成部５１３は、ＷｉからＺｉを生成し、第１選択部５１４は、各Ｚｉに属する集合のうち、最小探索時間を有する集合を選択する。
【００４６】
第２選択部５１５は、第１選択部５１４で選択された集合のうち、最小探索時間を有する集合を選択し、割当部５１６は、第２選択部５１５で選択した集合に属する区間を目的データに割り当てる。
【００４７】
各パラメータについての説明は、既に前述したことがあるので、ここでは省略する。
【００４８】
第２アルゴリズム実行部５２０は、第１アルゴリズム実行部５１０による割当てが失敗した場合に、第２アルゴリズムを行って目的データのための空いている区間の割当を試み、ディスクにそれ以上空いている空間がない場合に、エラーメッセージを出力する。
【００４９】
制御部５３０は、第２アルゴリズム実行部５２０が目的データ全体について区間を割り当てられず、目的データの一部に対する区間を割り当てた場合に、目的データのサイズから割り当てた区間のサイズを減算した値を新たな目的データのサイズに設定し、割り当てた区間が終わる位置を新たな基準点に設定して第１アルゴリズム実行部５１０に伝達することによって、第１アルゴリズム実行部５１０が新たな入力値を基礎として第１アルゴリズムを行わせる。また、制御部５３０は、第１アルゴリズム実行部５２０によってエラーメッセージが出力されるか、または目的データ全体のための空いている空間が成功的に割当てられるまで前記設定動作を反復することによって、第１アルゴリズム及び第２アルゴリズムを交互に行う。
【００５０】
図６は、本発明の第１実施形態によってディスクの空間を割り当てる方法を説明するための図である。暗い部分は、既に割当てられた空間を表し、明るい部分は、空いている空間を表し、図６に示された部分外の全ての部分は、既に割当てられたと仮定する。図６を参照するに、基準点の左側にそのサイズが１（ブロック）である空いている区間ａ、ｂがあり、基準点の右側にそれぞれサイズが２、４、３（ブロック）である空いている区間ｃ、ｄ、ｅがある。本実施形態では、目的データのサイズが４（ブロック）、Ｃ＝２、Ｎ＝２０であると仮定する。
【００５１】
まず、ｉ２＝ｍｉｎ（２０，]ｌｏｇ２４［）であるので、２となり、ｉ１＝ｍａｘ（［ｌｏｇ２４］−２，０）であるので、０となる。したがって、Ｌ０、Ｌ１、Ｌ２を生成せねばならず、その結果は、次の通りである。
【００５２】
Ｌ２：｛ｄ｝
Ｌ１：｛ｃ，ｄ，ｅ｝
Ｌ０：｛ａ，ｂ，ｃ，ｄ，ｅ｝
ここで、Ｗｉを決定すれば、その結果は、次の通りである。
【００５３】
Ｗ２：｛ｄ｝
Ｗ１：｛ｃ，ｄ｝
Ｗ０：｛ａ，ｂ，ｃ，ｄ｝
次いで、ＷｉからＺｉを決定すれば、その結果は、次の通りである。
【００５４】
Ｚ１：｛ｄ｝
Ｚ２：｛ｃ，ｄ｝、｛ｄ｝
Ｚ３：｛ａ，ｂ，ｃ｝、｛ｂ，ｃ，ｄ｝、｛ｃ，ｄ｝、｛ｄ｝
これから、各ｉ別にＺｉに属する集合のうち、最小の探索時間を有する集合を選択してＭｉを決定し、Ｍｉのうち最小の探索時間を有する集合を決定し、決定された集合に属する区間を目的データに割り当てればよい。
【００５５】
図７は、本発明の第２実施形態によってディスクの空間を割り当てる方法を説明するための図である。暗い部分は、既に割当てられた空間を表し、明るい部分は、空いている空間を表し、図７に示された部分外の全ての部分は、既に割当てられたと仮定する。
【００５６】
また、本実施形態では、目的データのサイズが８、Ｃ＝２、Ｎ＝２０であると仮定する。
【００５７】
ｉ２＝ｍｉｎ（２０，]ｌｏｇ２８［）であるので、３となり、ｉ１＝ｍａｘ（［ｌｏｇ２８］−２，０）であるので、１となる。したがって、Ｌ１、Ｌ２、Ｌ３を生成せねばならず、その結果は、次の通りである。
【００５８】
Ｌ３：ｅｍｐｔｙ
Ｌ２：｛ｄ｝
Ｌ１：｛ｄ｝
ここで、Ｗｉを決定すれば、その結果は、次の通りである。
【００５９】
Ｗ３：ｅｍｐｔｙ
Ｗ２：｛ｄ｝
Ｗ１：｛ｄ｝
次いで、ＷｉからＺｉを決定せねばならないが、Ｗ２及びＷ１で選択できる唯一の区間であるｄのサイズは、目的データのサイズより小さいので、結局、第１アルゴリズムによる割当ては失敗した。したがって、第２アルゴリズムが行われる。
【００６０】
図示したように、ディスク内に目的データのサイズ以上である空いている区間が存在していないので、空いている区間のうち、最大区間である区間ｄが目的データの一部に割当てられる。区間ｄが目的データの一部に割当てられたので、まだ割当てられていない目的データの部分は、１（ブロック）のサイズを有する。したがって、区間ｄが終わる地点を新たな基準点に設定し、１（ブロック）を新たな目的データのサイズに設定して第１アルゴリズムを行えば、ｉ２＝ｍｉｎ（２０，]ｌｏｇ２１［）であるので、０となり、ｉ１＝ｍａｘ（［ｌｏｇ２１］−２，０）であるので、０となる。したがって、Ｌ０を生成すれば、次の通りである。
【００６１】
Ｌ０：｛ａ，ｂ，ｃ｝
これからＷ０を決定すれば、次の通りである。
【００６２】
Ｗ０：｛ｃ｝
これからＺ０を決定すれば、次の通りである。
【００６３】
Ｚ０：｛ｃ｝
したがって、追加的に割り当てる区間は、区間ｃとなるので、結局、本発明によって初期の目的データには、｛ｃ，ｄ｝が割当てられる。
【００６４】
図８は、本発明の第３実施形態によってディスクの空間を割り当てる方法を説明するための図である。図８を参照するに、ディスクの状態は、図７と同じであるが、定数Ｃが、図７とは異なり、３の値を有する。
【００６５】
第１アルゴリズムを行えば、ｉ２＝ｍｉｎ（２０，]ｌｏｇ２８［）であるので、３となり、ｉ１＝ｍａｘ（［ｌｏｇ２８］−３，０）であるので、０となる。したがって、Ｌ０、Ｌ１、Ｌ２、Ｌ３を生成せねばならず、その結果は、次の通りである。
【００６６】
Ｌ３：ｅｍｐｔｙ
Ｌ２：｛ｄ｝
Ｌ１：｛ｄ｝
Ｌ０：｛ａ，ｂ，ｃ，ｄ｝
ここで、Ｗｉを決定すれば、その結果は、次の通りである。
【００６７】
Ｗ３：ｅｍｐｔｙ
Ｗ２：｛ｄ｝
Ｗ１：｛ｄ｝
Ｗ０：｛ａ，ｂ，ｃ，ｄ｝
次いで、ＷｉからＺｉを決定すれば、その結果は、次の通りである。
【００６８】
Ｚ３：ｅｍｐｔｙ
Ｚ２：ｅｍｐｔｙ
Ｚ１：ｅｍｐｔｙ
Ｚ０：｛ａ，ｂ，ｃ，ｄ｝
結局、本実施形態では、｛ａ，ｂ，ｃ，ｄ｝が目的データに割当てられる。
【００６９】
図７の実施形態に対する結果と図８の実施形態に対する結果とを比較すれば、図８では、Ｃの値を２ではない３としてｉの範囲を広げ、それにより、他の結果を得た。したがって、Ｃの値によって結果が変わり、Ｃの値を適切に調節することによって最適化された結果が得られるということが分かる。
【００７０】
図９は、本発明の第４実施形態によってディスクの空間を割り当てる方法を説明するための図である。
【００７１】
本実施形態では、目的データのサイズが１２（ブロック）、Ｃ＝２、Ｎ＝２０であると仮定する。
【００７２】
暗い部分は、既に割当てられた空間を表し、明るい部分は、空いている空間を表し、図９に示された部分外の全ての部分は、既に割当てられたと仮定する。
【００７３】
まず、ｉ２＝ｍｉｎ（２０，]ｌｏｇ２１２［）であるので、４となり、ｉ１＝ｍａｘ（［ｌｏｇ２１２］−２，０）であるので、２となる。したがって、Ｌ２、Ｌ３、Ｌ４を生成せねばならず、その結果は、次の通りである。
【００７４】
Ｌ４：ｅｍｐｔｙ
Ｌ３：｛ｃ｝
Ｌ２：｛ｃ｝
ここで、Ｗｉを決定すれば、その結果は、次の通りである。
【００７５】
Ｗ４：ｅｍｐｔｙ
Ｗ３：｛ｃ｝
Ｗ２：｛ｃ｝
次に、ＷｉからＺｉを決定すれば、その結果は、次の通りである。
【００７６】
Ｚ４：ｅｍｐｔｙ
Ｚ３：ｅｍｐｔｙ
Ｚ２：ｅｍｐｔｙ
したがって、第１アルゴリズムによる割り当ては失敗したので、第２アルゴリズムが行われる。
【００７７】
空いている区間のうち、最大区間である区間ｃが目的データの一部に割当てられる。区間ｃが目的データの一部に割当てられたので、まだ割当てられていない目的データの部分は、４（ブロック）のサイズを有する。したがって、区間ｃが終わる地点を新たな基準点に設定し、４（ブロック）を新たな目的データのサイズに設定して、再び第１アルゴリズムを行えば、ｉ２＝ｍｉｎ（２０，]ｌｏｇ２４[）であるので、２となり、ｉ１＝ｍａｘ（［ｌｏｇ２４］−２，０）であるので、０となる。したがって、Ｌ０、Ｌ１、Ｌ２を生成せねばならず、その結果は、次の通りである。
【００７８】
Ｌ２：ｅｍｐｔｙ
Ｌ１：｛ｂ｝
Ｌ０：｛ａ，ｂ｝
これにより、Ｗｉを決定すれば、次の通りである。
【００７９】
Ｗ２：ｅｍｐｔｙ
Ｗ１：｛ｂ｝
Ｗ０：｛ａ，ｂ｝
このとき、ａとｂとの総和が新たな目的データのサイズである４（ブロック）より小さいので、第１アルゴリズムによる割り当ては失敗した。したがって、再び第２アルゴリズムを行うが、区間ｃは、既に割当てられたので、残りの空いている区間のうち、最大区間である区間ｂが割当てられる。区間ｂが割当てられれば、新たな目的データのサイズは、２となり、残りの唯一の空いている区間は、ａである状態で第１アルゴリズムが行われる。ａ区間のサイズは、新たな目的データのサイズである２より小さいので、再び第２アルゴリズムが行われる。そして、第２アルゴリズムによって区間ａが割当てられた後に第１アルゴリズムが行われるが、それ以上空いている空間がないので、第２アルゴリズムが行われ、第２アルゴリズムによって、結局、エラーメッセージが出力される。
【００８０】
一方、前述した本発明の実施形態は、コンピュータで実行されうるプログラムで作成可能であり、コンピュータで読み取り可能な記録媒体を利用して前記プログラムを動作させる汎用デジタルコンピュータで具現されうる。
【００８１】
前記コンピュータで読み取り可能な記録媒体は、マグネチック記録媒体（例えば、ＲＯＭ、フロッピー（登録商標）ディスク、ハードディスクなど）、光学的判読媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤなど）及びキャリアウェーブ（例えば、インターネットを通じた伝送）のような記録媒体を含む。
【００８２】
以上、本発明についてその望ましい実施形態を中心に説明した。当業者は、本発明が本発明の本質的な特性から逸脱しない範囲で変形された形態で具現されうるということが理解できる。したがって、開示された実施形態は、限定的な観点ではなく、説明的な観点で考慮されねばならない。本発明の範囲は、前述した説明ではなく、特許請求の範囲に表れており、それと同等な範囲内にある全ての差異点は、本発明に含まれたと解釈されねばならない。
【産業上の利用可能性】
【００８３】
本発明は、ファイルシステム関連の技術分野に適用可能である。
【図面の簡単な説明】
【００８４】
【図１】従来の技術によって空いている空間を割り当てる方法を説明するための図である。
【図２】本発明によってディスクの空間を割り当てる過程を示すフローチャートである。
【図３】本発明による第１アルゴリズムを行う過程を示すフローチャートである。
【図４】本発明による第２アルゴリズムを行う過程を示すフローチャートである。
【図５】本発明によってディスクの空間を割り当てる装置の構造図である。
【図６】本発明の第１実施形態によってディスクの空間を割り当てる方法を説明するための図である。
【図７】本発明の第２実施形態によってディスクの空間を割り当てる方法を説明するための図である。
【図８】本発明の第３実施形態によってディスクの空間を割り当てる方法を説明するための図である。
【図９】本発明の第４実施形態によってディスクの空間を割り当てる方法を説明するための図である。
【図１】
2007310878.tif 000003
【図２】
2007310878.tif 000004
【図３】
2007310878.tif 000005
【図４】
2007310878.tif 000006
【図５】
2007310878.tif 000007
【図６】
2007310878.tif 000008
【図７】
2007310878.tif 000009
【図８】
2007310878.tif 000010
【図９】
2007310878.tif 000011