(57)【要約】【課題】データ処理システムにおいてディスクスペースを管理するための変型バデイシステムを提供すること。【解決手段】変型バデイシステムは、ディスク記憶装置のディスクスペースを管理するために適用される。この変型バデイシステムは、最小量のメモリスペースを使用し、ディスクスペース内のイクステントに非常に迅速なアクセスを与える。更に、この変型バデイシステムは、各ノードがディスクスペースのイクステントを表すようなノードのツリー構造を使用している。このツリー構造の各ノードに対する状態ビットを保持するためのビットマップが形成される。このビットマップは、参照の局所性を保持するように構成される。【選択図】図２
2006024238.tif 000002
【特許請求の範囲】
【請求項１】
所与のサイズのディスクスペースをもつディスク記憶装置を備えたデータ処理システムにおいて、ディスクスペースを管理する方法が、
（ａ）ディスクスペースを、最上レベルから最下レベルまでの範囲の多数の次々に減少するレベルのノードを有するツリー構造としてモデリングし、各ノードは、ディスクスペースのイクステントを表し、各レベルごとに、そのレベル内のノードは同様のサイズのイクステントを表し、最下レベル以外の各レベルの各ノードは親ノードであって、この親ノードを、次に続くレベルにおいて兄弟となる子ノードに接続するリンクを有し、子ノードによって表されたイクステントは、親ノードによって表されたイクステントの完全な細分を構成し、これらノードによって表されたイクステントのサイズは各次々のレベルにおいて減少し、そして各次々のレベルごとにノードによって表されたイクステントのサイズの和は、ディスクスペースの所与のサイズに等しく、
（ｂ）各ノードに関する状態情報を、そのノードによって表されたイクステントが少なくとも部分的に割り当てられていると分かっているか否かを指定するビットマップに記憶し、そして
（ｃ）上記ビットマップ及びツリー構造を使用して、ディスクスペースを管理する、という段階を備えたことを特徴とする方法。
【請求項２】
ビットマップ及びツリー構造を使用してディスクスペースを管理するという上記段階は、更に、ノードによって表されたディスクスペースのイクステントを割り当てる段階を含む請求項１に記載の方法。
【請求項３】
ビットマップ及びツリー構造を用いてディスクスペースを管理する上記段階は、１つのノードによって表されたディスクスペースのイクステントを割り当て解除する段階を更に備えた請求項１に記載の方法。
【請求項４】
ディスクスペースの割り当てを、多数の次々に減少するレベルのノードを有するツリー構造としてモデリングする上記段階は、ツリー構造の最上レベルにある単一のノードに、全てのディスクスペースを含むイクステントを表示させる段階を更に備えている請求項１に記載の方法。
【請求項５】
ディスクスペースを、多数の次々に減少するレベルのノードを有するツリー構造としてモデリングする上記段階は、ツリー構造の最下レベルにあるノードのそれぞれに、サイズがディスクセクタであるイクステントを表示させる段階を更に備えた請求項１に記載の方法。
【請求項６】
ビットマップ及びツリー構造を用いてディスクスペースを管理する上記段階は、更に、
（ｉ）ツリー構造においてノードの１つによって表されたディスクスペースのイクステントを割り当てて、情報を保持するようにし、そして
（ii）ビットマップに保持された状態情報を更新して、その割り当てられたイクステントが少なくとも部分的に割り当てられていると分かることを指定するようにする、という段階を備えた請求項１に記載の方法。
【請求項７】
ビットマップ及びツリー構造を用いてディスクスペースを管理する上記段階は、更に、
（ｉ）ツリー構造においてノードの１つによって表されたディスクスペースのイクステントを割り当て解除し、そして
（ii）ビットマップに保持された状態情報を更新して、その割り当て解除されたイクステントノードが少なくとも部分的に割り当てられていると分からないことを指定するようにする、という段階を備えた請求項１に記載の方法。
【請求項８】
所与のサイズのディスクスペースをもつディスク記憶装置を備えたデータ処理システムにおいて、
（ａ）ディスクスペースを、最上レベルから最下レベルまでの範囲の多数の次々に減少するレベルのノードを有するツリー構造としてモデリングし、各ノードは、ディスクスペースのイクステントを表し、各レベルごとに、そのレベル内のノードは同様のサイズのイクステントを表し、最下レベル以外の各レベルの各ノードは親ノードであって、この親ノードを、次に続くレベルにおいて兄弟となる子ノードに接続するリンクを有し、子ノードによって表されたイクステントは、親ノードによって表されたイクステントの完全な細分を構成し、これらノードによって表されたイクステントのサイズは各次々のレベルにおいて減少し、そして各次々のレベルごとにノードによって表されたイクステントのサイズの和は、ディスクスペースの所与のサイズに等しく、
（ｂ）最上レベルで始まって各次々のレベルごとに幅優先形態で続けられるような幅優先形態でノードに対する状態ビットが順序付けされるような順序付けビットマップに各ノードごとに少なくとも１つの状態ビットを記憶し、各ノードの状態ビットは、そのノードによって表されたイクステントが少なくとも部分的に割り当てられていると分かるかどうかを指定するものであり、そして
（ｃ）上記ビットマップ及びツリー構造を使用して、ディスクスペースを管理する、
という段階を備えたことを特徴とする方法。
【請求項９】
ビットマップ及びツリー構造を使用してディスクスペースを管理する上記段階は、更に、ノードの１つによって表されたイクステントを割り当てる段階を備えた請求項８に記載の方法。
【請求項１０】
ビットマップ及びツリー構造を用いてディスクスペースを管理する上記段階は、１つのノードによって表されたディスクスペースのイクステントを割り当て解除する段階を更に備えた請求項８に記載の方法。
【請求項１１】
順序付けされたビットマップに各ノードに対する状態ビットを記憶する上記段階は、更に、順序付けされたビットマップにおいて兄弟ノードに対する状態ビットのすぐ隣にノードに対する状態ビットを記憶するという段階を備えた請求項８に記載の方法。
【請求項１２】
ディスクスペースをツリー構造としてモデリングする上記段階は、更に、ディスクスペースを２進ツリー構造としてモデリングする段階を含む請求項８に記載の方法。
【請求項１３】
ノードのサイズは、各次々のレベルにおいて半分づつ減少する請求項１２に記載の方法。
【請求項１４】
ディスクスペースを、多数の次々に減少するレベルのノードを有するツリー構造としてモデリングする上記段階は、ツリー構造の最上レベルにある単一のノードに、全てのディスクスペースを含むイクステントを表示させる段階を更に含む請求項８に記載の方法。
【請求項１５】
ディスクスペースを、多数の次々に減少するレベルのノードを有するツリー構造としてモデリングする上記段階は、ツリー構造の最下レベルにあるノードのそれぞれに、サイズがディスクセクタであるイクステントを表示させる段階を更に備えた請求項８に記載の方法。
【請求項１６】
所与のサイズのディスクスペースをもつディスク記憶装置を備えたデータ処理システムにおいて、ディスク記憶装置に自由ディスクスペースを位置決めする方法が、
（ａ）ディスクスペースを、最上レベルから最下レベルまでの範囲の多数の次々に減少するレベルのノードを有するツリー構造としてモデリングし、各ノードは、ディスクスペースのイクステントを表し、各レベルごとに、そのレベル内のノードは同様のサイズのイクステントを表し、最下レベル以外の各レベルの各ノードは親ノードであって、この親ノードを、次に続くレベルにおいて兄弟となる子ノードに接続するリンクを有し、子ノードによって表されたイクステントは、親ノードによって表されたイクステントの完全な細分を構成し、これらノードによって表されたイクステントのサイズは各次々のレベルにおいて減少し、そして各次々のレベルごとにノードによって表されたイクステントのサイズの和は、ディスクスペースの所与のサイズに等しく、
（ｂ）各ノードに関する状態情報を、イクステントが少なくとも部分的に割り当てられていると分かっているか否かを指定するビットマップに記憶し、
（ｃ）所望サイズのディスクスペースのイクステントを表すツリー構造におけるノードの選択された１つに対してビットマップの状態情報を検討し、
（ｄ）上記選択されたノードについてのビットマップの状態情報が、その選択されたノードにより表されたイクステントが少なくとも部分的に割り当てられていると分からないことを指定する場合には、（ｉ）その選択されたノードの各兄弟に関してビットマップの状態情報を検討して、その兄弟のいずれかが少なくとも部分的に割り当てられていると分かるかどうか判断し、そして（ii）いずれの兄弟も少なくとも部分的に割り当てられていると分かった場合には、その選択されたノードが自由であると結論する、という段階を備えたことを特徴とする方法。
【請求項１７】
上記選択されたノードについての状態情報が、その選択されたノードにより表されたイクステントが少なくとも部分的に割り当てられていると分かることを指定し、そしてその選択されたノードと同じレベルにおいてツリー構造に付加的なノードが存在する場合には、その選択されたノードと同じレベルにおいてツリー構造の次のノードを選択されたノードとして指定しそして上記段階（ｄ）で始まる方法を繰り返すという段階を更に備えた請求項１６に記載の方法。
【請求項１８】
最上レベルで始まって各次々のレベルのノードごとに幅優先形態で続けるようにツリー構造におけるノードの順序に基づいて幅優先形態でビットマップに状態情報を記憶する段階を更に含む請求項１７に記載の方法。
【請求項１９】
上記次のノードは、上記ビットマップにおいて上記選択されたノードのすぐ隣に状態情報を持つノードである請求項１８に記載の方法。
【請求項２０】
上記次のノードは、ビットマップにおいて上記選択されたノードと同じレベルのノードの中で所定ノードに対する状態情報の最も近くに記憶された状態情報をもつと共に上記方法でまだ検討されていない状態情報をもつノードである請求項１８に記載の方法。
【請求項２１】
少なくとも部分的に割り当てられていると分かった兄弟情報がないことが決定された場合には、その選択されたノードの親ノードに関して上記ビットマップの状態情報を検討して、その親ノードが少なくとも部分的に割り当てられていると分かるかどうか判断し、そしてその親ノードが少なくとも部分的に割り当てられていると分からない場合には、その親ノードを選択されたノードとして指定しそして上記段階（ｄ）で始まる方法を繰り返す、という段階を更に備えた請求項１７に記載の方法。
【請求項２２】
親ノードが少なくとも部分的に割り当てられていると分かると決定された場合には、その選択されたノードと同じレベルにあるツリー構造内の次のノードであって、その選択されたノード及びその選択されたノードの兄弟以外のノードを、選択されたノードとして指定し、そして上記段階（ｄ）で始まる方法を繰り返す、という段階を更に備えた請求項２１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にデータ処理システムに係り、より詳細には、データ処理システムにおいてディスクスペースを管理するための変型バデイシステムに係る。
【背景技術】
【０００２】
ディスク上の自由スペースは、一般に、３つの方法の１つで管理されている。第１の手法においては、ファイルに対するディスクスペースの割り当てが、ファイルに割り当てられたセクタのリンクされたリストによって記述される。第２の手法においては、ディスクスペースのどのセクタが割り当てられたかを監視するようにビットマップが設けられる。ビットマップには各セクタごとにビットが与えられる。セクタに関連したビットの値が、そのセクタが割り当てられたか否かを指定する。第３の手法においては、イクステント（即ち、ディスク上のセクタの隣接セット）において割り当てが行われる。このように、個々のセクタではなくて隣接セクタの範囲でスペースが割り当てられる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明の目的は、データ処理システムにおいてディスクスペースを管理するための変型バデイシステムを提供することにある。
【課題を解決するための手段】
【０００４】
本発明の第１の特徴によれば、所与のサイズのディスクスペースをもつディスク記憶装置を備えたデータ処理システムにおける方法が実施される。この方法においては、ディスクスペースは、多数のレベルのノードを有するツリー構造として最初にディスクスペースをモデリングすることによって管理され、上記レベルは最上レベルから最下レベルまで順次に減少する。各レベルの各ノードは、ディスクスペースのイクステントを表し、そして各レベルごとに、そのレベル内のノードは、同様のサイズのイクステントを表す。ノードによって表されたイクステントのサイズは、レベルの低下と共に減少するが、ノードの数は、レベルの低下と共に増加する。各次々のレベルに対するノードのサイズの和は、所与のサイズのディスクスペースに等しい。各レベルの各ノードはディスクスペースのイクステントを表し、そして各レベルごとに、そのレベル内のノードは、同様のサイズのイクステントを表す。最下レベル以外の各レベルの各ノードは親ノードであって、この親ノードを次に続くレベルにおける子ノードに接続するリンクを有している。子ノードは互いに兄弟となる。子ノードは、親ノードによって表されたイクステントの細分であるイクステントを表す。各ノードに関する状態情報がビットマップに記憶され、そのノードによって表されたイクステントが少なくとも部分的に割り当てられると分かっているか否かについて指定する。ツリー構造のビットマップは、ディスクスペースを管理するのに使用される。
【０００５】
状態情報は、ツリー構造における各ノードごとに少なくとも１つの状態ビットを構成する。ビットマップは、最上レベルで始まって各次々のレベルに対して巾優先形態で続けられるような巾優先形態でノードに対する状態ビットが順序付けされる順序付けビットマップであるのが好ましい。このようにビットマップを順序付けすることは、兄弟ノード及び親ノードに対して参照の局所性を与えることができる。
【発明を実施するための最良の形態】
【０００６】
（実施例）
本発明の好ましい実施例においては、ディスクスペースがノードのツリー構造としてモデリングされ、ツリーの各ノードはディスクスペースのイクステントを表しそしてそれに関連した状態を有している。各ノードの状態情報は、参照の局所性を利用した形態で順序付けされたビットマップに記憶される。このビットマップは、ツリー構造に対応する形態で順序付けされ、兄弟の状態ビットを隣接位置に保持する。本発明の好ましい実施例にツリー構造及びビットマップを使用することにより、自由ディスクスペースを迅速に位置決めして割り当てることができる。更に、ツリー構造及びビットマップを使用することに関連したオーバーヘッドは最小である。というのは、ビットマップ及びツリー構造によってメモリスペースが消費されないからである。
【０００７】
図１は、本発明の好ましい実施例に適したデータ処理システム１０のブロック図である。このデータ処理システム１０は、中央処理ユニット（ＣＰＵ）１２を備え、これはメモリ１４及びディスク記憶装置１６へアクセスする。本発明の好ましい実施例は、以下に詳細に述べる変型バデイシステムを採用することによりディスク記憶装置１６のディスクの自由スペースを管理する。又、データ処理システム１０は、キーボード１８、マウス２０及びビデオディスプレイ２２も備えている。
【０００８】
本発明の好ましい実施例は、メモリ１４に保持されたオペレーティングシステム２４において実施される。本発明は、オペレーティングシステムで実施される必要はなく、オペレーティングシステムと共に機能する個別のコードモジュールで実施されてもよいことが当業者に明らかであろう。図２は、本発明の好ましい実施例の変型バデイシステムを実施するためのツリー構造及びビットマップを構成するようにオペレーティングシステム２４によって実行される段階を示すフローチャートである。図２は、図３及び４と共に説明する。最初に、ディスク記憶装置１６（図１）の使用できるディスクスペースが、図３に示すようなツリー構造に論理的に仕切られる（図２のステップ２６）。このツリー構造３２（図３）の最上レベルは、ツリー構造のルートノード３４である。これは、ディスク記憶装置１６の使用できる全ディスクスペース（即ち、図３では４Ｋ）のイクステントを表している。ツリー構造３２の次のレベルは、ディスクスペースのより小さなイクステントを表すノードを保持する。このノードによって表されたイクステントは、ルートノード３４によって表されたイクステントの完全な細分を構成する。図３に示された例では、ノード３６及び３８は、使用できるディスクスペースの半分のイクステント（即ち、ディスクスペースの使用可能な４Ｋのうちの２Ｋ）を表す。ツリー構造３２の次のレベルは、手前のレベルのノード３６及び３８によって表されたものより小さいイクステントを表すノード４０、４２、４４及び４６を保持する。より詳細には、ノード４０及び４２によって表されたイクステントは、ノード３６によって表されたイクステントの完全な細分を表し、そしてノード４４及び４６によって表されたイクステントは、ノード３８によって表されたイクステントの完全な細分を表す。この最下レベル４０、４２、４４及び４６におけるノードの各々は、サイズが１Ｋであり、ディスク記憶装置１６に使用できる割り当ての最小サイズ単位であるイクステントを表す。
【０００９】
ツリー構造３２のノードの各々は、次々のレベル間でノードを接続する論理的なリンクを含んでいる。例えば、ノード３４は、リンク４７によってノード３６及び３８に接続される。ノード３４は親ノードと称され、ノード３６及び３８は子ノードと称される。構造体３２の各レベルにおいて、子ノードによって表されたイクステントは、親ノードによって表されたイクステントの完全な細分を構成する。ノード３６及び３８は互いに兄弟である。これらの兄弟ノードは、同じイクステント（親ノードによって表された）細分であるイクステントを表すという点でバデイとしても知られている。「バデイシステム」は、バデイ表示法を用いることによってメモリスペースを割り当て／割り当て解除するための公知解決策である。
【００１０】
図３に示されたツリー構造は単なる説明に過ぎず、各親ノードは３つ以上の子ノードを含んでもよいことを理解されたい。
【００１１】
上記ツリー構造３２の各ノード３４、３６、３８、４０、４２、４４及び４６には状態が指定される。この状態はビットで表される。ノードの状態ビットの値「１」は、そのノードにより表されたイクステントが割り当てられるか又は部分的に割り当てられると分かっていることを示している。これに対して、ノードの状態ビットの値「０」は、そのノードにより表されたイクステントが割り当てられるか又は部分的に割り当てられると分からないことを示している。最初に、全てのノードは、その状態ビットが値「０」である。これらの状態ビットは、ツリー構造に基づいて順序付けされたビットマップ４８（図４）に記憶される。このビットマップ４８は、ツリー構造３２（図３）のノードに対する全ての状態ビットを保持する。ビットマップ４８のビットは、ルートノード３４で始めて巾優先形態で順序付けされる。従って、ビットマップ４８のビット１（図４）は、ルートノード３４の状態情報を保持する。ビット２は、ノード３６の状態情報を保持し、そしてビット３は、ノード３８の状態情報を保持する。同様に、ビットマップ４８のビット４は、ノード４０の状態情報を保持し、ビット５、６及び７は、各々、ノード４２、４４及び４６の状態情報を保持する。この構成は、親のビット位置が分かったときに子ノードの状態ビットを迅速に位置決めできるようにしそしてその逆も行うことができる。特に、ノン・リーフノードｎ（その状態ビットがビットマップの位置ｎにある）の場合に、その子供はビットマップにおいて位置２ｎ及び２ｎ＋１となる。
【００１２】
ツリー構造３２及びビットマップ４８を使用するために、オペレーティングシステム２４は、割り当てファンクション、割り当て解除ファンクション、探索ファンクション及びテストファンクションをサポートする。これらファンクションの各々はツリー構造３２のノードに基づいて動作し、これについては以下で詳細に説明する。これらファンクションの説明は、最初にテストファンクションに焦点を合わせる。というのは、テストファンクションは他のファンクションのうちの選択されたファンクションによって使用されるからである。
【００１３】
図５は、２進ツリーの実施に対するテストファンクションによって行われるステップのフローチャートである。このファンクションは、各々Ｎ個の子供を有するＮ進ツリーに対して機能するように形成できることも理解されたい。テストファンクションは、ノードによって表されたイクステントが自由であるか否かをテストする。テストされるべきノードは、パラメータとしてテストファンクションへ通される。オペレーティングシステム２４は、最初に、当該ノードが値「１」の状態ビットを有するかどうかチェックし、この値「１」は、そのノードにより表されたイクステントが割り当てられるか又は部分的に割り当てられると分かっていることを指示するものである（図５のステップ５０）。ノードの状態ビットが値「１」を有する場合は、テストファンクションは、そのノードによって表されたイクステントが自由でないという結果を返送する（図５のステップ５２）。一方、ノードの状態ビットが値「０」を有する場合には、そのノードによって表されたイクステントが自由であるかどうか分からない。ノードは値「０」の状態ビットを有していて、その親又は他の祖先が既に割り当てられているために既に割り当てられていることもあるし、或いはノードによって割り当てられたイクステントが自由の場合もある。テストファンクションは、次いで、ノードがルートノードであるかどうかチェックする（ステップ５４）。ノードがルートノードである場合には、値「０」の状態ビットを有するので、そのノードによって表されたイクステントは自由であり（割り当てることのできる親を持たない）、そしてテストファンクションは、ノードによって表されたイクステントが自由であるという指示を返送する（ステップ５６）。
【００１４】
ノードがルートノードでない場合には、テストファンクションは、兄弟ノードの状態ビットの値を検査する（ステップ５８）。例えば、ノード３６（図３）の状態が検査される場合には、ノード３８が唯一の兄弟ノードであり、ノード３８の状態が図５のステップ５８で検査される。テストファンクションは、いずれかの兄弟ノードが値「１」の状態ビットを有するかどうかチェックする（ステップ６０）。より一般化されたテストファンクションにおいては、値「１」の状態ビットをもつ兄弟が見つかるか、又は兄弟に対する全ての状態ビットが検査されてしまうまで、全ての兄弟ノードに対する状態ビットが検査される。いずれかの兄弟ノードが値「１」の状態ビットを有する場合には、親ノードによって表されたイクステントは完全に割り当てられない。従って、テストファンクションは、当該ノードによって表されたイクステントが自由であるという指示を返送する（ステップ６２）。
【００１５】
全ての兄弟ノードの状態ビットが値「０」をもつ場合には、親ノードを現在ノードとして考え（ステップ６４）そしてステップ５０で始まる前記のステップを繰り返すことにより、プロセスはツリー構造３２を登るように続けられる。
【００１６】
上記したように、オペレーティングシステム２４は、割り当てファンクションをサポートする。この割り当てファンクションは、ディスク記憶装置１６のディスクスペースに自由スペース（即ち、イクステント）を割り当てる。図６は、割り当てファンクションによって実行されるステップのフローチャートである。割り当てられるべきイクステントを表すノードに対する状態ビットには、値「１」が指定される（図６のステップ７６）。次いで、ノードが親ノードをもつかどうかの判断がなされる（ステップ７８）。ノードが親ノードをもたない場合には、それ以上のステップを実行する必要はない。これに対し、ノードが親ノードをもつ場合には、その親ノードの状態ビットの値が検査され、親ノードが割り当てられたか又は部分的に割り当てられたと表示された（即ち、値「１」を有する）かどうか判断される（ステップ８０）。親ノードが割り当てられたか又は部分的に割り当てられたと既に表示された場合には、それ以上のステップを実行する必要はない。しかしながら、親ノードが割り当てられたか又は部分的に割り当てられたと表示されていないときには、親ノードの状態ビットが値「１」をもつように更新されて、親ノードによって表されたイクステントの少なくとも一部分が割り当てられると分かることを指示しなければならない（ステップ８２）。このプロセスは、次いで、親ノードを現在ノードとして考えることによりツリー構造３２を登るように続けられる（ステップ８４）。次いで、ステップ７８で始まる上記ステップが繰り返される。各親ノードの少なくとも一部分が割り当てられているので、ビットマップ４８に保持された状態ビットは、上記ファンクションによって値「１」に更新されねばならない。
【００１７】
又、オペレーティングシステム２４は、ディスク記憶装置１６におけるディスクスペースのイクステントを割り当て解除するファンクションもサポートする。割り当て解除されるべきイクステントを表すノードは、パラメータとして、割り当て解除ファンクションへ通される。図７は、オペレーティングシステム２４によってサポートされる割り当て解除ファンクションのフローチャートである。ノードによって表されたイクステントを割り当て解除すべきときには、そのノードの状態ビットが値「０」をもつように表示される（図７のステップ８６）。そのノードによって表されたイクステントは、親ノードによって表されたイクステントの唯一の部分であるか又は割り当てられた他の祖先によって表されたイクステントであるから、親及び祖先ノードも、値「０」をとるように更新された状態ビットをもつべきであるかどうか判断しなければならない。親ノード及び祖先ノードの状態ビットを更新するプロセスは、ノードがルートノードであるかチェックする（ステップ８８）によって開始される。ノードがルートノードである場合には、親ノードも祖先ノードももたず、それ故、それ以上のステップは必要とされない。これに対して、ノードがルートノードでない場合には、兄弟ノードの状態ビットが検査される（ステップ９０）。いずれかの兄弟ノードの状態ビットが値「１」である（即ち、兄弟ノードの全ての状態ビットが「０」でない）場合は、親ノードの状態ビットを更新することができない。というのは、親ノードが表すイクステントは、少なくとも部分的に割り当てられると分かっているからである。全ての兄弟ノードの状態ビットが値「０」を有する場合には、親ノードによって表されたイクステントは当然自由でなければならない。というのは、子ノードによって表された全てのイクステントが割り当てられないか又は部分的に割り当てられないからである。従って、親ノードの状態ビットは値「０」に変更される（ステップ９２）。このプロセスは、親ノードを現在ノードとして考えそしてステップ８８で始まる上記ステップを繰り返すことにより付加的な祖先ノードに対して続けられる。この形態では、全ての祖先は必要に応じて更新される。
【００１８】
オペレーティングシステム２４は、更に、ツリー構造３２（図３）内の自由ノードを探索する探索ファンクションもサポートする。図８は、この探索ファンクションによって実行されるステップのフローチャートである。探索ファンクションによって実行されるサーチは、所望サイズのイクステントを有するツリーのレベルにおいて次のノードの状態ビットを見ることによって開始される（ステップ９６）。特に、所望量のディスクスペースが、ツリー構造３２のノードによって表されたいずれのイクステントのサイズにも一致しない場合には、必要とされるものよりも大きな最も一致に近いイクステントがステップ９６において選択される。このイクステントのサイズを以下「所望のサイズ」と称する。ディスクスペースの所望サイズイクステントを有するツリーのレベルにおいて、探索ファンクションは、値「０」の状態ビットを有するレベルにノードがあるかどうかを決定する（ステップ９８）。値「０」の状態ビットを有するレベルにノードがない場合には、使用できる所望サイズのイクステントはない。
【００１９】
しかしながら、値「０」の状態ビットを有するレベルにノードがある場合は、そのノードの兄弟ノードが検査され、いずれかの兄弟ノードが値「１」の状態ビットを有するかどうか判断される（ステップ１００）。いずれかの兄弟ノードが値「１」の状態ビットを有する場合には、そのノードによって表されたイクステントが探索ファンクションによって返送され、使用される（ステップ１０２）。一方、全ての兄弟ノードに対する状態ビットが値「１」を有する場合には、親ノードの状態ビットが検査される（ステップ１０４）。特に、親ノードの状態ビットが値「１」をもつかどうかの判断がなされる（ステップ１０６）。親ノードが値「１」の状態ビットをもつ場合には、親ノードをルートとして始まるサブツリーはそれ以上検査される必要がないことに注意されたい（ステップ１０８）。自由ノードのサーチは、ステップ９６で再び続けられる。親ノードの状態ビットが値「１」を有しそして親ノードがルートノードでない場合には（ステップ１１２）、親ノードの兄弟ノードを検査することにより上記ステップがステップ１００で始めて繰り返される。親ノードがルートノードである場合には（ステップ１１２を参照）、探索ファンクションは、現在ノードによって表されたイクステントを自由なものとして返送する（ステップ１１０）。
【００２０】
探索ファンクションの上記説明においては、テストファンクションが探索ファンクションに直接一体化されたことが明らかであろう。テストファンクションと探索ファンクションを一体化すると、テストされねばならない非常に多数のノードの検査をアルゴリズムがスキップできることにより、効率利得を得ることができる。
【００２１】
上記の探索ファンクションは、ツリー構造体のあるレベルにおいて自由な第１イクステントを位置決めするように設計されている。この探索ファンクションに採用された手法を若干変更することにより、ディスクの所与の位置の付近に置かれた自由なイクステントを探すようなファンクションを形成することができる。このような変更は、サーチプロセスが開始する場所で重要である。ツリーのターゲットレベルにおいて第１のイクステントを探すのではなく、この変更された手法は、所望の位置に最も近いノードを最初に探す。おそらく自由であるイクステントをサーチするときは、この変更された手法は、その最も近いノードから外方へ進んで、他の近傍のノードを検査し、そしてその近傍のノードによって表されたイクステントをテストし、それらが自由であるかどうか調べる。見つかった第１の自由なイクステントが、最も近い自由なイクステントである。
【００２２】
好ましい実施例について本発明を説明したが、特許請求の範囲に規定された本発明の範囲から逸脱せずに、その形態及び細部に種々の変更がなされ得ることが当業者に明らかであろう。例えば、本発明に使用されたツリー構造３２は、２進ツリーである必要はない。各親ノードは３つ以上の子ノードを有してもよい。更に、割り当てられた又は部分的に割り当てられた状態が「１」ビット値に関連される必要はなく、「１」ビット値と「０」ビット値の意味を交換してもよい。
【図面の簡単な説明】
【００２３】
【図１】本発明の好ましい実施例に適したデータ処理システムのブロック図である。
【図２】本発明の好ましい実施例を実施するために行われるステップを示すフローチャートである。
【図３】本発明の好ましい実施例に使用されるツリー構造体を示す図である。
【図４】図３のツリー構造体のビットマップを示す図である。
【図５】本発明の好ましい実施例のテストファンクションにおいて実行されるステップを示すフローチャートである。
【図６】本発明の好ましい実施例の割り当てファンクションにおいて実行されるステップを示すフローチャートである。
【図７】本発明の好ましい実施例の割り当て解除ファンクションにおいて実行されるステップを示すフローチャートである。
【図８】本発明の好ましい実施例の探索ファンクションにおいて実行されるステップを示すフローチャートである。
【符号の説明】
【００２４】
１０  データ処理システム
１２  中央処理ユニット
１４  メモリ
１６  ディスク記憶装置
１８  キーボード
２０  マウス
２２  ビデオディスプレイ
２４  オペレーティングシステム
３２  ツリー構造
３４  ルートノード
３６、３８、４０、４２、４４、４６  ノード
４７  リンク
４８  ビットマップ
【図１】
2006024238.tif 000003
【図２】
2006024238.tif 000004
【図３】
2006024238.tif 000005
【図４】
2006024238.tif 000006
【図５】
2006024238.tif 000007
【図６】
2006024238.tif 000008
【図７】
2006024238.tif 000009
【図８】
2006024238.tif 000010