(57)【要約】【課題】記憶装置の容量によらず柔軟に領域を区画し管理することが可能であり、また区画にファイルを割り付けるに当たって、効率的な手法により、領域を有効活用することのできる技術を提供する。【解決手段】記憶装置の区画のサイズを互いに異なる２のべき乗の和で表して、和を構成する各２のべき乗のサイズの領域を主区域としたとき、各主区域を２分の１ずつ順次分割したサイズの各サイズの区域に区分けし、主区域を含む各サイズの区域のそれぞれのファイルの割付状態を示す割付情報を格納する割付表を生成する。割付表に格納された割付情報に基づいて区画を管理する。【選択図】図３
2010287066.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置の区画管理装置において、
区画のサイズを取得する区画サイズ取得手段と、
該区画のサイズを互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表したとき、該和を構成する各２のべき乗と前記区画の割当単位のサイズとの積のサイズの主区域により、そのサイズの順に前記区画を分割することで該区画を区分けし、前記各主区域を２分の１ずつ分割して順次前記区画の割当単位のサイズまで各サイズの区域に区分けし、前記主区域を含む各区域に対応して該各区域のそれぞれの割付状態を示す割付情報を格納する多層区分割付表を生成し、初期化する多層区分割付表生成手段と、
を含む初期化部と、
前記多層区分割付表に格納された前記割付情報に基づいて前記各区域の割付を管理する多層区分管理部と、
を備えることを特徴とする区画管理装置。
【請求項２】
請求項１記載の区画管理装置において、
前記区域のサイズを規定する２のべき乗のべき数を該区域の区分レベルとすると、
前記多層区分割付表は、前記区域の割付情報を、前記区域の区分レベル順、同一区分レベルにおいては前記区域の前記区画内の配置順で格納し、
前記多層区分管理部は、前記割付情報の格納順にしたがって前記割付情報が該当する区域を識別するための識別番号である区分番号を割り振り、該区分番号を用いて前記区域の割付を管理する、
ことを特徴とする区画管理装置。
【請求項３】
請求項２記載の区画管理装置において、
前記多層区分割付表生成手段は、前記主区域の割付情報の初期値として空きであることを示す空き状態を設定し、前記主区域を分割して得られる区域の割付情報の初期値として該区域への割付を行わないことを示す空以外の状態を設定する
ことを特徴とする区画管理装置。
【請求項４】
請求項３記載の区画管理装置において、
前記多層区分管理部は、
サイズを含むファイルあるいはメモリ領域の割付要求を受け付ける割付要求受付手段と、
前記多層区分管理表を参照して、前記割付要求に含まれるサイズである割付要求サイズが、互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表され、前記区分レベルの異なる区域のサイズの和である場合、該区分レベルの最大のものより１つ大きい区分レベルの空区域であって前記割付要求サイズより大きいサイズの一次割付区域を探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とし、前記割付要求に含まれるサイズである割付要求サイズが２のべき乗と前記区画の割当単位のサイズの積で表される場合、該割付要求サイズの空区域を一次割付区域として探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とする空区域探索手段と、
前記一次割付区域のサイズが前記割付要求サイズより大きい場合、該一次割付区域を、前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である二次割付区域と、残りの領域であって前記二次割付区域の区分レベルの異なる区域が割り付けられる区分レベルの順とは逆順で区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記二次割付区域のそれぞれの区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空候補状態を設定する二次割付手段と、
前記割付区分番号を前記ファイルあるいはメモリ領域の割付要求の割り付け結果の１つとして出力する割付区分番号出力手段と、
を備え、
前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域の区分レベルは等しく、前記多層区分割付表において前記区分レベルより１つ上位の区分レベルの区域を２分割したものであることを特徴とする区画管理装置。
【請求項５】
請求項４記載の区画管理装置において、
前記空区域探索手段は、前記一次割付区域の区分レベルで空区域を探索できなかった場合に、前記多層区分割付表の上位の区分レベルの区域に対応する割付状態を参照して上位の区分レベルの空区域を探索して該区域の区分番号を求め、該区分番号の区域である仮割付区域を、前記一次割付区域と残りの領域であって前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記一次割付区域内の区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空状態を設定する仮割付手段を含むことを特徴とする区画管理装置。
【請求項６】
請求項５記載の区画管理装置において、
前記空区域探索手段は、割付要求されたファイルあるいはメモリ領域を割付可能な空状態の区域を探索できなかった場合、前記多層区分割付表から空候補状態の区域を探索することを特徴とする区画管理装置。
【請求項７】
請求項６記載の区画管理装置において、
前記多層区分管理部は、
サイズ及び割付区分番号を含むファイルあるいはメモリ領域の解放要求を受け付ける解放要求受付手段と、
前記解放要求に含まれるサイズである解放要求サイズが、前記区分レベルの異なる区域の和である場合、前記隣接多層区域内の最小の区域の区分番号を求めて該区分番号の指す前記多層区分割付表から割付状態を読み出し、該読み出した割付状態が空または空候補の状態であれば、前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記１つ上位の区分レベルの区域の解放を試み、前記隣接多層区域内の最小の区域の割付状態が使用中であれば、前記二次割付区域内の最小の区域の割付状態を空の状態とする一次割付区域内解放手段と
前記一次割付区域が解放され、その区分番号の指す前記多層区分割付表の割付状態が空の状態になったとき、該一次割付区域と同一の区分レベルであって、１つ上位の区分レベルの区域を２つに分割したときの一方の区域を前記一次割付区域としたときの他方の区域の割付状態を前記多層区分割付表より読み出し、該他方の区域の割付状態が空または空候補の状態であれば、前記一方の区域と他方の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記上位の区分レベルの区域の解放を試み、前記他方の区域の割付状態が使用中であれば、前記一方の区域の割付状態を空の状態とする上位区域解放手段と、
を備えることを特徴とする区画管理装置。
【請求項８】
記憶装置の区画管理方法において、
区画のサイズを取得する区画サイズ取得ステップと、
該区画のサイズを互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表したとき、該和を構成する各２のべき乗と前記区画の割当単位のサイズとの積のサイズの主区域により、そのサイズの順に前記区画を分割することで該区画を区分けする主区分ステップと、
前記各主区域を２分の１ずつ分割して順次前記区画の割当単位のサイズまで各サイズの区域に区分けし、前記主区域を含む各区域に対応して該各区域のそれぞれの割付状態を示す割付情報を格納する多層区分割付表を生成する多層区分割付表生成ステップと、
前記多層区分割付表に格納された前記割付情報に基づいて前記各区域の割付を管理する多層区分管理ステップと、
を実行することを特徴とする区画管理方法。
【請求項９】
請求項８記載の区画管理方法において、
前記区域のサイズを規定する２のべき乗のべき数を該区域の区分レベルとすると、
前記多層区分割付表は、前記区域の割付情報を、前記区域の区分レベル順、同一区分レベルにおいては前記区域の前記区画内の配置順で格納するものであり、
前記多層区分管理ステップは、前記割付情報の格納順にしたがって前記割付情報が該当する区域を識別するための識別番号である区分番号を割り振り、該区分番号を用いて前記区域の割付を管理する、
ことを特徴とする区画管理方法。
【請求項１０】
請求項９記載の区画管理方法において、
前記多層区分割付表生成ステップは、主区域の割付情報の初期値として空きであることを示す空き状態を設定し、前記主区域を分割して得られる区域の割付情報の初期値として該区域への割付を行わないことを示す空以外の状態を設定する、
ことを特徴とする区画管理方法。
【請求項１１】
請求項１０記載の区画管理方法において、
前記多層区分管理ステップは、
サイズを含むファイルあるいはメモリ領域の割付要求を受け付ける割付要求受付ステップと、
前記多層区分管理表を参照して、前記割付要求に含まれるサイズである割付要求サイズが、互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表され、前記区分レベルの異なる区域のサイズの和である場合、該区分レベルの最大のものより１つ大きい区分レベルの空区域であって前記割付要求サイズより大きいサイズの一次割付区域を探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とし、前記割付要求に含まれるサイズである割付要求サイズが２のべき乗と前記区画の割当単位のサイズの積で表される場合、該割付要求サイズの空区域を一次割付区域として探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とする空区域探索ステップと、
前記一次割付区域のサイズが前記割付要求サイズより大きい場合、該一次割付区域を、前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である二次割付区域と、残りの領域であって前記二次割付区域の区分レベルの異なる区域が割り付けられる区分レベルの順とは逆順で区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記二次割付区域のそれぞれの区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空候補状態を設定する二次割付ステップと、
前記割付区分番号を前記ファイルあるいはメモリ領域の割付要求の割り付け結果の１つとして出力する割付区分番号出力ステップと、
を備え、
前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域の区分レベルは等しく、前記多層区分割付表において前記区分レベルより１つ上位の区分レベルの区域を２分割したものであることを特徴とする区画管理方法。
【請求項１２】
請求項１１記載の区画管理方法において、
前記空区域探索ステップは、前記一次割付区域の区分レベルで空区域を探索できなかった場合に、前記多層区分割付表の上位の区分レベルの区域に対応する割付状態を参照して上位の区分レベルの空区域を探索して該区域の区分番号を求め、該区分番号の区域である仮割付区域を、前記一次割付区域と残りの領域であって前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記一次割付区域内の区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空状態を設定する仮割付ステップを含むことを特徴とする区画管理方法。
【請求項１３】
請求項１２記載の区画管理方法において、
前記空区域探索ステップは、割付要求されたファイルあるいはメモリ領域を割付可能な空状態の区域を探索できなかった場合、前記多層区分割付表から空候補状態の区域を探索することを特徴とする区画管理方法。
【請求項１４】
請求項１３記載の区画管理方法において、
前記多層区分管理ステップは、
サイズ及び割付区分番号を含むファイルあるいはメモリ領域の解放要求を受け付ける解放要求受付ステップと、
前記解放要求に含まれるサイズである解放要求サイズが、前記区分レベルの異なる区域の和である場合、前記隣接多層区域内の最小の区域の区分番号を求めて該区分番号の指す前記多層区分割付表から割付状態を読み出し、該読み出した割付状態が空または空候補の状態であれば、前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記１つ上位の区分レベルの区域の解放を試み、前記隣接多層区域内の最小の区域の割付状態が使用中であれば、前記二次割付区域内の最小の区域の割付状態を空の状態とする一次割付区域内解放ステップと
前記一次割付区域が解放され、その区分番号の指す前記多層区分割付表の割付状態が空の状態になったとき、該一次割付区域と同一の区分レベルであって、１つ上位の区分レベルの区域を２つに分割したときの一方の区域を前記一次割付区域としたときの他方の区域の割付状態を前記多層区分割付表より読み出し、該他方の区域の割付状態が空または空候補の状態であれば、前記一方の区域と他方の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記上位の区分レベルの区域の解放を試み、前記他方の区域の割付状態が使用中であれば、前記一方の区域の割付状態を空の状態とする上位区域解放ステップと、
を含むことを特徴とする区画管理方法。
【請求項１５】
請求項８から１４記載のいずれか１項に記載の方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１６】
請求項８から１４記載のいずれか１項に記載の方法をコンピュータに実行させるプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置の区画を管理する、区画管理装置、区画管理方法及びプログラムに関する。
【背景技術】
【０００２】
従来から、ハードディスク等の記憶装置に記憶するデータを管理するための方式として、例えばＦＡＴ（File Allocation Tables）やＮＴＦＳ（NT File System）等のファイルシステムが採用されている。
【０００３】
図１Ａは、従来から採用されているハードディスク等の外部記憶装置における区画割付を説明する図である。
図１Ａに示すように、例えば外部記憶装置３０６の記憶領域は、図示しないディスクアロケータ等のユーティリティプログラムにより４つの区画１〜４（１９１，１９２，１９３，１９４）が割り付けられ、それぞれあるファイルシステムに割り当てられている。区画の先頭には区画の管理データを格納した区画管理テーブル１９５ａを備えたマスターブートレコード１９５が配置されている。図１Ａに区画番号３についての区画情報１９６が例示されているように、区画管理テーブル１９５ａは、区画番号１９６ａ、開始位置１９６ｂ、区画サイズ１９６ｃのエントリを含んでいる。区画番号１９６ａには、区画を識別する区画番号が格納されており、図示の例では３である。開始位置には、区画の先頭アドレスの情報が格納されており、図示の例ではその内容は省略している。区画サイズ１９６ｃには、区画の割当単位領域の個数が格納されており、図示の例では５２である。
【０００４】
各区画におけるファイルに対するディスクの割付管理は、それぞれの区画が割り当てられたファイルシステム特有の割付方法に依存するため煩雑であった。例えば、ＦＡＴによれば、割付を行ったブロックを示すリンクリストをファイルごとに保持している。また、ＮＴＦＳによれば、ファイルごとに割付を行ったブロックの開始位置及び連続するブロック数についての情報を保持している。
これらのファイルシステムにおける割付管理の問題を解決するために、例えば、下記特許文献１に開示されているバディシステムに関する技術が提案されている。バディシステムによれば、領域を２ｋからなるサイズごとに分割して割付の管理を行う。仮想記憶方式を使用していないメモリ管理システムでのメモリ領域の割り付けでは、基本的なバディシステムが採用されている。
【０００５】
図１Ｂは、バディシステムの割付原理を説明する図である。図１Ｂに示すのは、サイズが２３＝８の割当領域４９０とそれに対応するツリー構造体５８０と、ツリー構造体５８０のノードに対応する領域が使用中であるかを示すビットマップ４００である。割当領域４９０は、例えば図１Ａに例示した区画１〜４等である。
ツリー構造体５８０は、割当領域４９０を２分の１のサイズに順次割付単位のサイズまで分割して得られる領域の関係を階層的にモデル化したものである。割付単位のサイズの領域の階層をレベル１とすると、図に示す例では、ルートノードのレベルは４となる。
【０００６】
ツリー構造体５８０のルートノード４８０は、点線の矢印で示すように、分割前の割当領域４９０全体の領域（レベル４の領域）に対応し、ノード内に記載された“８”は、対応する割当領域４９０のサイズに相当する。また、括弧内の数字は、同一レベル内の領域を識別するレベル内番号である。
【０００７】
ルートノード４８０にリンク５４０で接続されたノード４４０と、ルートノード４８０にリンク５４１で接続されたノード４４１は割当領域４９０を２分割した領域（レベル３の領域）に対応する。それぞれの領域のサイズは図に示すように４である。
ノード４４０の下位には、リンク５２０で接続されたサイズ２のノード４２０と、リンク５２１で接続されたサイズ２のノード４２１が存在する。同様に、ノード４４１の下位には、リンク５２２で接続されたサイズ２のノード４２２と、リンク５２３で接続されたサイズ２のノード４２３が存在する。これら４つのノードはレベル２の領域に対応する。
【０００８】
ノード４２０の下位には、リンク５１０で接続されたサイズ１のノード４１０と、リンク５１１で接続されたサイズ１のノード４１１が存在する。同様に、ノード４２１の下位には、リンク５１２で接続されたサイズ１のノード４１２と、リンク５１３で接続されたサイズ１のノード４１３が存在し、ノード４２２の下位には、リンク５１４で接続されたサイズ１のノード４１４と、リンク５１５で接続されたサイズ１のノード４１５が存在し、ノード４２３の下位には、リンク５１６で接続されたサイズ１のノード４１６と、リンク５１７で接続されたサイズ１のノード４１７が存在する。これら８つのノードはレベル１の領域に対応する。
ルートノード４８０以外のノードは親ノードの対応する領域を２分割した領域の１つに対応したものとなっている。したがって、各レベルの領域のサイズの総和は、割当領域４９０のサイズに一致する。
【０００９】
図１Ｂに示すビットマップ４００は、点線の矢印で示すように、ツリー構造体５８０の各ノードに対応したビット値を持つものである。ビットマップ４００の、符号４０８で示すレベル４のレベル内番号４０９で示すビット位置のビット値は、レベル４の領域が使用中であるかを示すものであり、符号４０４で示すレベル３のレベル内番号０、１のビット値は、該当する領域が使用中であるかを示している。同様に、符号４０２で示すレベル２のレベル内番号０〜３はレベル２の各領域が使用中であるかを示し、符号４０１で示すレベル１のレベル内番号０〜７はレベル１の各領域が使用中であるかを示している。
【００１０】
図１Ｂに示す例では、レベル４のレベル内番号０、レベル３のレベル内番号０、レベル２のレベル内番号０、レベル１のレベル内番号０にビット“１”が立っており、そのビット位置に対応する領域全体を新たに使用することはできないことを示している。つまり、レベル１のレベル内番号０にその状態を示すように、ノード４１０に対応するサイズ１の領域が使用中であるので、その領域を含むより大きいサイズの領域をそのまま使用することはできないことを示している。
【００１１】
上述のバディシステムによれば、ある大きさのファイル及びメモリ領域を割り付けるとき、その大きさと等しいかそれを超える２ｋからなるサイズの領域の中から空き領域を探して割り付け、解放するときもそのサイズの空き領域群に戻せばよいので、ファイル及びメモリ領域の割り付けと解放及び領域の管理が容易である。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平７−２８６９３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上記のバディシステムによれば、２のべき乗単位で領域を割り付けることから、例えば２．１ＧＢのファイルを割り付けるとき、４ＧＢの領域が必要となり、ファイル割付後のブロックには、データの書き込まれていない領域が生じるにも関わらず、従来のファイルシステムにおいてはその領域に対して更にファイルを追加することができず、領域を有効に使用することができなかった。
また、例えば記憶装置全体の記憶容量が１２７ＧＢであったとしても、記憶領域を要求する要求元に対して割り付ける物理的あるいは論理的な領域である区画について、最大でも６４ＧＢの区画として管理せざるを得なかった。
すなわち、バディシステムによれば、２のべき乗単位で領域を割り付けることからファイル及びメモリ領域の割り付けと解放及び領域の管理が容易ではあるが、２のべき乗サイズの領域から２のべき乗サイズではない領域を取得した場合の残りの領域の管理、及び２のべき乗サイズではない領域から２のべき乗サイズの領域を取得した場合の残りの領域の管理がなされていないため、領域を有効活用できないという課題がある。
【００１４】
そこで本発明は、２のべき乗サイズの領域から２のべき乗サイズではない領域を取得した場合でも、２のべき乗サイズではない領域から２のべき乗サイズの領域を取得した場合でも、残りの領域を管理することが可能であり、また領域管理手段が領域にファイル及びメモリ領域を割り付けるに当たって、効率的な手法により、領域を有効活用することのできる技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明の一つの態様によれば、区画のサイズを取得し、区画のサイズを互いに異なる２のべき乗の和と区画の割当単位のサイズの積で表したとき該和を構成する各２のべき乗のサイズの領域を主区域としてそのサイズの順に区画に連続的に割り付けることで区画を区分けし、主区域を２分の１ずつ順次分割したサイズの各サイズの領域である区域と主区域に対応して、各サイズの区域と主区域のそれぞれのファイル割り付け状態を示す割付情報を格納する多層区分割付表を生成し、多層区分割付表に格納された割付情報に基づいて区域のファイルへの割付を管理する。
【００１６】
また、本発明の別の態様によれば、区域のサイズを規定する２のべき乗のべき数を該区域の区分レベルとすると、多層区分割付表は、区域の割付情報を、区域の区分レベル順、同一区分レベルにおいては区域の区画内の配置順で格納し、割付情報の格納順にしたがって割付情報が該当する区域を識別するための識別番号である区分番号を割り振り、該区分番号を用いて区域の割付を管理する。
【００１７】
また、本発明の別の態様によれば、割付要求されたファイルのサイズが区分レベルの異なる区域のサイズの和である場合、該区分レベルの最大のものより１つ大きい区分レベルの空区域であって割付要求サイズより大きいサイズの一次割付区域を探索し、一次割付区域を、区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である二次割付区域と、残りの領域であって二次割付区域の区分レベルの異なる区域が割り付けられる区分レベルの順とは逆順で区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、二次割付区域のそれぞれの区域に対応する多層区分割付表の割付状態に使用中を設定し、隣接多層区域を構成する区域に対応する多層区分割付表の割付状態に空候補状態を設定する。
【発明の効果】
【００１８】
本発明によれば、区画を２のべき乗サイズの組合せで管理するので任意のサイズの区画を効率的に無駄なく有効に管理することが可能であり、区画を区分した各サイズの区域で割付管理を行うことから、連続する領域に無駄なくファイルの割付がなされることとなるため、領域の有効活用を図ることができる。
【図面の簡単な説明】
【００１９】
【図１Ａ】外部記憶装置における区画割付を説明する図である。
【図１Ｂ】バディシステムの割付原理を説明する図である。
【図２Ａ】本発明の一実施形態における区画管理の概要を説明する図である。
【図２Ｂ】本発明の一実施形態におけるアロケーションシステムのソフトウェア及びハードウェア環境例を説明する図である。
【図２Ｃ】本発明の一実施形態におけるハードウェア構成例を説明する図である。
【図３】本発明の一実施形態における区画サイズに対応した区画の初期化状態例を説明する図である。
【図４Ａ】本発明の一実施形態における区画を初期化する前段の処理フロー例を説明する図である。
【図４Ｂ】本発明の一実施形態における区画を初期化する後段の処理フロー例を説明する図である。
【図４Ｃ】本発明の一実施形態における多層区分割付表を区分レベル毎に初期化する処理フロー例を説明する図である。
【図５】区域の割付を行う処理全体の概略の処理フローを説明する図である。
【図６】割付要求区分レベルの空区域を探索し、空区域の区分番号を取得する処理フロー例を説明する図である。
【図７Ａ】割付要求区分レベルのサイズを含む空区域を探索し、空区域の区分番号を取得する処理フロー例を説明する図である。
【図７Ｂ】割付要求区分レベルに空区域がある場合における区域探索を具体例により説明する図である。
【図７Ｃ】割付要求区分レベルに空区域がない場合における区域探索を具体例により説明する図である。
【図７Ｄ】本発明の一実施形態における区分レベルの末尾番号を取得する処理フロー例を説明する図である。
【図８Ａ】仮割付区域を多層区分し、一次割付区域を得る処理フロー例を説明する図である。
【図８Ｂ】仮割付区域を多層区分し、一次割付区域を得る処理を具体例により説明する図である。
【図９】割付要求区分レベルの空候補区域を探索し、空候補区域の区分番号を取得する処理フロー例を説明する図である。
【図１０Ａ】割付要求区分レベルのサイズを含む空候補区域を探索し、空候補区域の区分番号を取得する処理フロー例を説明する図である。
【図１０Ｂ】割付状態が空候補の仮割付区域を多層区域に区分し、一次割付区域を得る処理フロー例を説明する図である。
【図１１Ａ】一次割付区域を多層区分し、割付要求区分の二次割付区域を得る前段の処理フロー例を説明する図である。
【図１１Ｂ】一次割付区域を多層区分し、割付要求区分の二次割付区域を得る後段の処理フロー例を説明する図である。
【図１１Ｃ】一次割付区域を多層区分し、割付要求区分の二次割付区域を得る処理を、具体例により説明する図である。
【図１２】割付区域を解放し、空区域の連結を試みる処理全体の概略の処理フロー例を説明する図である。
【図１３】区分番号により多層区分管理表を検索し、区分番号に対応する区分レベルを求める処理フロー例を説明する図である。
【図１４Ａ】一次割付区域内に含まれる区域の解放と空区域の連結を試みる処理フロー例を説明する図である。
【図１４Ｂ】一次割付区域内に含まれる区域の解放と空区域の連結を試みる処理を、具体例により、説明する図である。
【図１５】割付区域内の分割割付状況を求めて分割割付状況スタックにプッシュする処理フロー例を説明する図である。
【図１６】区分番号の指す区分対の解放を試みる処理フロー例を説明する図である。
【図１７Ａ】一次割付区域と、隣接する空区域とを連結して上位の区域の割付状態を空とすることを試みる処理フロー例を説明する図である。
【図１７Ｂ】一次割付区域と、隣接する空区域とを連結して上位の区域の割付状態を空とすることを試みる処理を、具体例により、説明する図である。
【図１７Ｃ】区分番号の指す区分対の解放を試みる処理フローを説明する図である。
【図１８Ａ】本発明の一実施形態における区画管理装置の機能ブロック構成例を説明する図である。
【図１８Ｂ】本発明の一実施形態における区域割付手段の機能ブロック構成例を説明する図である。
【図１８Ｃ】本発明の一実施形態における区域解放手段の機能ブロック構成例を説明する図である。
【発明を実施するための形態】
【００２０】
以下、本発明の好適な実施の形態について、図面を参照して詳細に説明する。
図２Ａは、本発明の一実施形態における区画管理の概要を説明する図である。図２Ａを参照して本発明の一実施形態における区画管理の概要を説明するとともに、本発明の区画管理に関する若干の用語の定義を行う。
【００２１】
最初に、あらためて区画の定義を行う。本発明において「区画」とは、図１Ａを参照して説明したように、予め割り当てられた領域であり、最初に割り当てられる領域である。本発明においては、区画は取得済みであることを前提とする。区画は、本発明においては、記憶領域を要求する要求元に対して割り付けられた物理的あるいは論理的な領域であり、要求元及び割付を実行する主体にはファイルシステムであるとかディスクアロケータであるというような制限はない。また、本発明における区画は、外部記憶装置の記憶領域に限らず、例えば後に図２Ｃを参照して説明するデータ格納装置３０８に含まれる各種記憶装置の予め割り当てられた領域とすることができる。
【００２２】
さらにあらためて、本発明でいうメモリ領域の定義を行う。メモリ領域は、区画の領域の割付を要求する要求元から要求され、区画管理装置により要求元に対して割り付けられる区画内の領域である。要求元がファイルシステムであれば、ファイルシステムに割り付けられたメモリ領域はファイルシステムによって、ファイルの格納領域として使われることになる。以下の説明においては、要求元としてファイルシステムを例にあげて説明するので、ファイルを割り付けるという表現や、ファイル及びメモリ領域の割付のような表現を用いる。
【００２３】
「区域」とは、割り当てられた、あるいは割り付けられた領域である。区画は予め割り当てられた領域であるから、区域の１つであり、区域のうちの特定のものである。
区域を、２のべき乗と割当単位領域の積のサイズを有する複数の区域に分割することを「多層区分」という。また、多層区分された区域を「多層区域」という。なお、以下の説明においては、割当単位領域についての言及は省略し、領域のサイズについて、単に２のｎ乗のサイズ等の表記を用いる場合がある。また、表記の簡略化のため、例えば図１Ａの例示の区画番号１９６ａに格納された値３を区画番号１９６ａと呼ぶように、記憶領域に格納されたあるいは設定された値をその記憶領域の名前で呼ぶことがある。
【００２４】
以下、区域についての用語とそれに対応する区画についての用語を対比しながら定義する。
「区分」とは、領域を割り当てる、あるいは領域を分割して割り当てることであり、「割付」ということもある。領域は、区域または区画である。特に、区画のサイズを互いに異なる２のべき乗の和で表したとき該和を構成する各２のべき乗のサイズの領域をそのサイズの順に区画に連続的に割り付けることで区画を区分けすることを「主区分」という。また、主区分により割り付けられた区域を「主区域」という。主区分は、本発明においては、区画に対する初期割付である。以下の説明では、主区域は領域の先頭からサイズの大きいものから順に割り付けられるものとしているが、それとは逆順に、サイズの小さいものから順に割り付けるものとしても本願発明を実施可能であることは、後の説明から当業者には明らかである。
【００２５】
図２Ａの例示では、区画６９０は全体のサイズが１１であり、サイズが２３＝８の主区域６９８、サイズが２１＝２の主区域６９２、及びサイズが２０＝１の主区域６９１に区分されている。いいかえれば、主区域６９８、６９２、６９１が区画６９０に初期割付されている。
区分または主区分による区域または主区域の割付サイズである２のべき乗のべき数を「区分レベル」という。図２Ａに示す主区域６９８、６９２、６９１のそれぞれの区分レベルは３，１，０である。
上記定義された用語により説明すると、本発明の原理である区画管理方法は、区画を、区画の割当単位領域を互いに異なる２のべき乗個割り当てた区域に連続的に区分し、区域を連続的に割り付けたものとして管理する。
【００２６】
図２Ａには、さらに区画６９０の多層区分に対応するツリー構造体群７９０と、ツリー構造体群７９０のノードに対応する割付状態をビットマップに縮退した区域の割付状態を示すビットマップ６００が記述されている。
【００２７】
ツリー構造体群７９０は、主区域６９８を割り付ける主区分に対応するノード６８０をルートノードとするツリー、主区域６９２を割り付ける主区分に対応するノード６２４をルートノードとするツリー、及び主区域６９１を割り付ける主区分に対応するノード６１１０をルートノードとするツリーから構成されている。すなわち、ルートノード６８０は、点線の矢印７８８で示すように、区分レベル３の主区域６９８全体を割り付ける主区分（以下、主区分７８８ということがある。）に対応し、ルートノード６２４は、点線の矢印７８２で示すように、区分レベル１の主区域６９２全体を割り付ける主区分（以下、主区分７８２ということがある。）に対応し、ルートノード６１１０は、点線の矢印７８１で示すように、区分レベル０の主区域６９１全体を割り付ける主区分（以下、主区分７８１ということがある。）に対応する。それぞれのツリーの構造は、図１Ｂに記載されたツリー構造体５８０の構造と２分木ツリーであるという点で類似したものである。
【００２８】
ルートノード６８０内に記載された“８”は、対応する主区域６９８のサイズに相当する。また、括弧内の数字は、区画６９０を各区分レベルの区域毎に多層区分する個々の区分（区分ユニットということがある。）を識別する区分番号である。最大のサイズの主区域６９８に対応する主区分７８８の区分番号は０である。なお、以下においては、区分番号について、その区分番号で識別される区分により区分された区域の区分番号ということがある。すなわち、主区分７８８の区分番号という表現に変えて、主区域６９８の区分番号ということがある。また、ある区分番号の区分ユニットにより区分された区域を、その区分番号の区域ということがある。
【００２９】
ルートノード６８０にリンク７４０で接続されたノード６４０と、ルートノード６８０にリンク７４１で接続されたノード６４１は、主区域６９８を２分割して区分レベル２、サイズが４の区域を割り付ける区分に対応する。それぞれの区分番号は１つ上位の区分レベル３のノードに対応する区分番号の末尾である０に続く１と２である。
【００３０】
ノード６４０の下位には、リンク７２０で接続されたサイズ２のノード６２０と、リンク７２１で接続されたサイズ２のノード６２１が存在する。同様に、ノード６４１の下位には、リンク７２２で接続されたサイズ２のノード６２２と、リンク７２３で接続されたサイズ２のノード６２３が存在する。これら４つのノードは区分レベル１の区域の区分に対応する。また、これら４つのノードに対応する区分番号は、１つ上位の区分レベルである区分レベル２のノードに対応する区分番号の末尾の番号である２に続く３〜６である。
【００３１】
ノード６２０の下位には、リンク７１０で接続されたサイズ１のノード６１０と、リンク７１１で接続されたサイズ１のノード６１１が存在する。同様に、ノード６２１の下位には、リンク７１２で接続されたサイズ１のノード６１２と、リンク７１３で接続されたサイズ１のノード６１３が存在し、ノード６２２の下位には、リンク７１４で接続されたサイズ１のノード６１４と、リンク７１５で接続されたサイズ１のノード６１５が存在し、ノード６２３の下位には、リンク７１６で接続されたサイズ１のノード６１６と、リンク７１７で接続されたサイズ１のノード６１７が存在する。これら８つのノードは区分レベル０の区域の区分に対応する。また、これら８つのノードに対応する区分番号は、ルートノードをノード６８０とするツリーにおける１つ上位の区分レベルである区分レベル１のノードに対応する区分番号の末尾の番号に続く、主区分７８２に対応するツリーのルートノードであって区分レベルが３のノードに対応する区分番号の末尾の番号にさらに続く８〜１５である。
【００３２】
以下同様に、ルートノード６２４にリンク７１８で接続されたノード６１８と、ルートノード６２４にリンク７１９で接続されたノード６１９は主区域６９２を２分割して区分レベル０、サイズ１の区域を割り付ける区分に対応する。
ルートノード６２４の区分番号は、主区分７８８に対応するツリーの区分レベル１のノードに対応する区分番号の末尾６に続く７である。ノード６１８の区分番号は、主区分７８８に対応するツリーの区分レベル０のノードに対応する区分番号の末尾１５に続く１６であり、ノード６１８の区分番号はそれに続く１７である。
また、サイズが１の主区域６９１を割り付ける主区分７８１に対応するツリーは、点線の矢印７８１で示すように、ルートノードであるノード６１１０のみで構成される。ノード６１１０の区分番号は、主区分７８２に対応するツリーの区分レベル０のノードに対応する区分番号の末尾１７に続く１８である。
【００３３】
次に、本発明の一実施の形態による区分番号の性質について説明する。
まず、記憶管理の対象となる区画のサイズが与えられると、そのサイズに応じて主区分が行われ、さらに区分レベル毎に多層区分が行われる。図２Ａの例では、サイズが１１の区画６９０が与えられると、それに対応したツリー構造体群７９０を生成することができる。そして、ツリー構造体群の最上位の区分レベルのノードから下位のノードに向かって、同一区分レベル内では左側を若番として、図２Ａに示すように一意に区分番号を付与することができる。
【００３４】
そして、区分レベル毎の区分番号を管理することにより、区分番号が与えられると、その区分番号で識別される区分ユニットによって区分けされた区域のサイズである区分レベルを求めることができ、さらに、その区分レベルでの先頭の区分番号と当該区分番号との差に基づいて、前記区分ユニットによる割付対象となる区域の区画上の位置を求めることができる。
【００３５】
図２Ａに示すビットマップ６００は、点線の矢印で示すように、ツリー構造体群７８０の各ノードに対応する割付状態をビットマップに縮退したビット値を持つものである。図２Ａの例示では、各ノードに２ビットの値が対応している。ビットマップ６００のビット値については後に詳細に説明する。ここでは、図２Ａの例示については、以下に簡単に説明する。
【００３６】
ビットマップ６００のビット値は、各区分番号を有するノードに対応する区域の初期割付終了時の割付状態を表している。符号６０８で示す区分レベル３のビット位置であって、区分レベル３の区分番号６０９の値が０であるビット位置のビット値００は、区分番号０の区分による区域が空であるのを示すものである。符号６０４で示す区分レベル２のビット位置であって、区分番号１、２のビット値１０は、該当する区域の割付状態が保留であることを示している。同様に、符号６０２で示す区分レベル１の区分番号３〜６をビット位置とするビット値は、該当する区域の割付状態が保留であり、区分番号７をビット位置とするビット値は、該当する区域の割付状態が空であることを示している。また、符号６０１で示す区分レベル０の区分番号８〜１７をビット位置とするビット値は、該当する区域の割付状態が保留であり、区分番号１８をビット位置とするビット値は、該当する区域の割付状態が空であることを示している。
【００３７】
割付状態の空と保留の区別は、割付要求のサイズの空領域を割り付けるときの優先順位に関係する。つまり、実質的に空状態の領域であっても、割付状態が空のものから使用されるようにする。この詳細については、後に説明する。
【００３８】
図２Ｂは、本発明の一実施形態に係るアロケーションシステムのソフトウェア及びハードウェア環境例を説明する図である。アロケーションシステム１００は初期化部１０１と多層区分管理部１０２から構成される。初期化及び多層区分管理については、後に詳細に説明する。
【００３９】
初期化部１０１は、例えばディスクアロケータあるいはファイルシステムの初期化部のような初期化プログラム２０１からの区画サイズを含む初期化要求を受け付け、データ格納装置３０８を構成する、例えば主記憶装置３０５、外部記憶装置３０６、通信装置を介してアクセスする遠方の記憶装置３０７等（以下、単に記憶装置ということがある。）に割り付けられている区画の多層区分管理情報の初期化を行う。
【００４０】
多層区分管理部１０２は、ファイルシステム２０２からの割付要求サイズを含む区域の割付要求により、多層区分管理情報の書込を行うことで区画の区分、すなわち区域の分割割付を実行し、書き込んだ多層区分管理情報を読み出して割付区分番号を含む割付結果をファイルシステム２０２に返す。
【００４１】
ファイルシステム２０２は、アプリケーションプログラム／ＯＳなどのファイルを利用するシステム２００からのファイル操作要求を受け付け、そのファイル操作要求がファイルへの区域の割付を要するものであれば、上述のアロケーションシステム１００の多層区分管理部１０２に割付要求サイズを含む割付要求を行って割付結果を受け取り、割付区分番号としてアロケーションシステム１００の多層区分管理部から返された区分番号を指定してファイル操作システム２０３に対してファイルの操作要求を行う。ファイル操作システム２０３は指定された区分番号により多層区分管理部１０２から割り付けられた区域のアドレスを取得して記憶装置に格納されたファイルに対するファイル操作としてのデータの書込あるいはデータの読出を実行して操作結果をファイルシステム２０２に返す。ファイルシステム２０２はファイル操作システム２０３から返された操作結果をアプリケーションプログラム／ＯＳなどのファイルを利用するシステム２００にファイル操作応答として返す。
【００４２】
ファイルシステム２０２及びファイル操作システム２０３が既存のものであっても、本発明によるアロケーションシステム１００とのインターフェースを調整することにより、本発明によるアロケーションシステム１００が使用可能である。また、アプリケーションプログラム／ＯＳなどのファイルを利用するシステム２００はいうに及ばず、初期化プログラム２０１も同様に既存のものを適用可能である。したがって、これらのプログラム、システムについての説明は省略する。
【００４３】
図２Ｃは、本発明の一実施形態におけるハードウェア構成例を説明する図である。
本発明の一実施形態による記憶装置の区画管理及びファイルへの区域の割付及び解放処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。データ格納装置３０８については、後に説明する区分レベルごとの区域を多層的に管理する多層区分管理表３０９と区分ごとの割付状態を保持する多層区分割付表３１０及び管理対象である区画３１１を含む。図２Ｃに示すように、データ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６、あるいはそれらの組み合わせで実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００４４】
すなわち、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、多層区分割付表３１０及び多層区分管理表３０９は主記憶装置３０５に持ち、区画３１１は外部記憶装置３０６に割り当てられるのが多くの場合と考えられるが、区画が、主記憶装置３０５に割り当てられる場合でも本発明が適用可能であることは、後の説明から明らかである。
図２Ｃの例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。そして、以下の説明においては、一時記憶領域に格納されるあるいは設定されるデータの名前でその一時記憶領域の名前とすることがあり、逆に、一時記憶領域の名前により、その一時記憶領域の格納されるあるいは設定されるデータの名前とすることがある。
【００４５】
次に、図３、図４Ａ〜図４Ｃを参照して、本発明の一実施形態における多層区分管理情報の初期化について説明する。なお、多層区分管理情報の初期化を区画の初期化と表記する場合もある。
【００４６】
図３は、区画サイズに対応した区画の初期化状態例を示す説明図である。
先に図２Ｂの説明において述べたように、区画の初期化は、ファイルシステムに区画が割りつけられたのち、初期化プログラムからのその区画の区画サイズを含む初期化要求を受け付けることにより、アロケーションシステムの初期化部により行われる。図３に示す区画サイズ１２０には、そのファイルシステムに割り付けられ、区画３１１の初期化要求に含まれる区画サイズ“５２”が２進数の形式で表示されており、５２＝２５＋２４＋２２であるから、２ビット目、４ビット目及び５ビット目が“１”である。
【００４７】
この初期化プログラムから受信された区画サイズに応じて区画構成主区分表１３０が作成される。区画構成主区分表１３０は、その添字０〜７で示すように区分レベルに対応する１ビットからなるエントリから構成されており、図３の例示では、区分レベル０から最上位の区分レベル７に対応する８つのエントリを有している。矢印１２２，１２４及び１２５で示すように、区画サイズを２進数形式で表示したときのビット値に応じて、対応する区分レベルのエントリのビット値が設定されている。
【００４８】
図３に示す区画３１１には、区画構成主区分表１３０からの矢印１３５、１３４及び１３２により対応関係が示されているように、区画構成主区分表１３０のビット値が“１”であるエントリに対応する区分レベルのサイズの主区域１８５、１８４及び１８２が初期割付されている。
なお、主区域に対応する区分レベルを主区分レベルということもある。すなわち, 区画構成主区分表１３０は、ビット値１で主区分レベルを表示するものと言える。
【００４９】
多層区分管理表３０９は、図３に示すように、主区分番号管理表３０９ａ、先頭番号管理表３０９ｂ、及び総区分数管理表３０９ｃを含む。主区分番号管理表３０９ａと先頭番号管理表３０９ｂは、その添字０〜７で示すように、区画構成主区分表１３０と同様に区分レベルに対応するエントリから構成されている。主区分番号管理表３０９ａのエントリは主区分番号１１４で構成され、先頭番号管理表３０９ｂのエントリは、先頭番号１１６で構成される。各エントリの値は、区画構成主区分表１３０の値に基づいて、初期化処理において設定される。総区分数管理表３０９ｃには、初期化対象の区画のサイズに対応して区分された区分ユニットの総数である総区分数１１５が設定される。別の言い方をすれば、総区分数１１５には、区分レベル毎に各区分レベルのサイズに区分けされた区域数の総和が設定される。図２Ａの例では、区分番号０〜１８に対応した１９が設定される。図３に示す例では、区分番号０〜１００に対応した１０１が設定されている。
【００５０】
主区分番号１１４には、後に説明する多層区分割付表３１０が、ある区分レベルの主区分に対応するエントリを有するとき、その区分レベルのエントリにその主区分に対応する区分番号を格納し、ある区分レベルでは多層区分割付表３１０が主区分に対応するエントリを有さないとき、その区分レベルのエントリに無意の区分番号として“−１”を格納する。図３の例では、主区分番号１１４の各エントリの値は、上位の区分レベルから、−１，−１，０，３，−１，２２，−１，−１である。
【００５１】
先頭番号１１６は、多層区分割付表３１０の各エントリに一意に対応付けられた区分番号のうち各区分レベルの区分割付表の先頭のエントリに対応付けられた区分番号であり、図３に例示された先頭番号１１６の各エントリの値は、上位の区分レベルから、−１，−１，０，１，４，１０，２３，４９である。これらの値の設定については、後に図４Ａ〜図４Ｃを参照して詳細に説明する。
【００５２】
多層区分割付表３１０は、区画３１１内の領域の割付状態を管理するためのものであり、図２Ａに示す割付ビットマップ６００と同様のものである。ただし、図３に示すように、多層区分割付表３１０には、区分番号１７１に加えてレベル内番号１７２が対応付けられている。多層区分割付表３１０は、初期化処理において、多層区分管理表３０９の値に基づいて生成され、初期設定される。
【００５３】
多層区分割付表３１０は、図の点線の矢印１４０〜１４５に示すように、最下位の区分レベルから区画構成主区分表１３０のビット値が１である最上位の区分レベルまでの各区分レベルに対応した区分割付表１６０〜１６５から構成されている。
各区分割付表のエントリは、そのエントリに該当する区分番号の区域の２ビットの割付状態１７０で構成されている。割付状態のビット値“００”、“０１”、“１０”、“１１”は、それぞれ各区分番号の区域の「空」、「空候補」、「保留」、「使用中」の状態に対応する。これらの状態の意味は後に詳細に説明をするが、割付状態１７０に２ビットを用いることにより、「空候補」を識別することが可能となり、記憶領域を一層無駄なく利用することができる。
【００５４】
また、区分割付表１６０〜１６５の各エントリは、図３の矢印１７５、１７４、１７２に示すように主区分、すなわち主区域に対応するものと、１つ上位の区分レベルの区域を２つに分割する区分、すなわち１つ上位の区分レベルの区域を２つに分割した区域に対応するものとがある。
【００５５】
多層区分割付表３１０の各エントリには、最上位の区分レベルの区分割付表１６５の先頭のエントリから最下位の区分レベルの区分割付表１６０の末尾のエントリまで０からの連続番号である区分番号１７１を対応付けることができる。また、区分割付表毎に、先頭のエントリから末尾のエントリまで、０から始まる連続番号であるレベル内番号１７２を対応付けることができる。先頭番号管理表３０９ｂの先頭番号１１６は、該当する区分レベルにおける区分番号の先頭番号である。
【００５６】
先に図２Ａを参照して説明したように、区画サイズ、すなわち区画構成主区分表が与えられると、多層区分割付表の構成は一意に決定し、区分番号で識別される区分ユニットにより区分けされる区域の区画内の位置とサイズも一意に決定される。
多層区分割付表３１０の初期状態においては、矢印１７５、１７４、１７２に示すように、主区域と対応するエントリの割付状態１７０には空を表示する“００”が、その他のエントリの割付状態には保留を表示する“１０”が初期設定される。したがって、割付状態が空の区域についてみると、区画３１１には、主区域１８５、１８４、１８２が分割割付されており、多層区分割付表３１０で管理される区域のうちで空の区域を設定するという意味で、区画３１１は初期割付される。多層区分割付表３１０の初期設定については、後に図４Ａ〜図４Ｃを参照して詳細に説明する。
【００５７】
なお、上述の区分番号１７１とレベル内番号１７２の番号の付与方法は単なる例示であり、後述のファイルの割付管理が可能なものであれば、例えば先頭の番号を０ではなく１とする、番号の付与順を逆順にする等、種々変形が可能であることは、当業者にとって自明である。
以上説明したとおり、本発明によれば、ファイルシステムに割り当てられた区画３１１は、多層区分割付表３１０を用いて、同一の領域を区分レベルに応じた割付状態１７０により、多層的に管理される。
【００５８】
多層区分割付表３１０を用いた区域の割付は、割付要求のサイズに応じて、ある区分レベルの空区域あるいは異なる区分レベルの連続した空区域の区分番号を多層区分割付表の探索により取得し、その区分番号を使用中にすることにより行われる。空区域がない場合は、空候補の区域を探索する。
図２Ｂに示すように、ファイルの割付要求をしたファイルシステムには使用中とした区分番号が割付区分番号としてアロケーションシステムから返される。ファイル操作システムはこの区分番号を指定したファイル操作要求を受けると多層区分管理部からこの区分番号の区域のアドレス情報を受信する。多層区分管理部は区分番号により多層区分管理表３０９を探索し、区分番号に対応する区域の区分レベルとレベル内番号を取得し、それによりファイルに割り付けられた区域の区画内の位置とサイズを知ることができる。これらの処理については後に詳細に説明する。
【００５９】
次に、図４Ａ、図４Ｂ及び図４Ｃを参照して区画を初期化する処理を説明する。ここで区画を初期化する処理は、具体的には例えば図３に示す多層区分管理表３０９と多層区分割付表３１０の値を初期設定する処理である。以下では、例として多層区分管理表３０９と多層区分割付表３１０を参照して説明する。
【００６０】
図４Ａは、区画を初期化する前段の処理フロー例を説明する図である。
図４Ａに示すように、まず、ステップＳ４０１で、区画の初期化を要求するプログラムから受け取った区画サイズから、区画サイズを２進数形式で表示したときのビット値に応じて区分レベルのエントリのビット値が設定された区画構成主区分表を作成する。
【００６１】
次にステップＳ４０２で、主区分レベルに区画構成主区分表の最上位の区分レベルを設定し、ステップＳ４０３で、総区分数管理表の総区分数に初期値として値０を設定して、ステップＳ４０４に進む。図３に示す例では、区画構成主区分表１３０が作成され、主区分レベルには７が設定される。上述のステップＳ４０２における、区画構成主区分表の最上位の区分レベルが設定される主区分レベルは、先に述べた図示しない一時的記憶領域の１つの例である。
【００６２】
ステップＳ４０４では、主区分レベルの指す区画構成主区分表のビット値を取り出し、ステップＳ４０５で、その取り出したビット値が有意、すなわち値１であるか判定する。
上記取り出したビット値が１でなければステップＳ４０６に分岐し、主区分レベルの指す主区分番号管理表に値“−１”を設定し、次にステップＳ４０７で、主区分レベルの指す先頭番号管理表に値“−１”を設定し、ステップＳ４０８で、主区分レベルを１つ減らしてステップＳ４０４に戻る。
上記ステップＳ４０４〜ステップＳ４０８のループ処理を、ステップＳ４０５で初めて区画構成主区分表のビット値が有意であると判定されるまで繰り返す。図３に示す例では、主区分レベルが５に設定されるまでは区画構成主区分表のビット値は０であるから、このループ処理により、主区分番号管理表３０９ａと先頭番号管理表３０９ｂの区分レベル７と区分レベル６にはともに値“−１”が設定される。
【００６３】
一方、上記取り出したビット値が１であれば、ステップＳ４０９に進み、先頭番号に値“０”を設定し、ステップＳ４１０で、区分数に値“１”を設定して図４Ｂに示すステップＳ４１１に進む。上述のステップＳ４０９の先頭番号及びステップＳ４１０の区分数も、先に述べた図示しない一時的記憶領域の例である。それぞれ、データの名前を一時的記憶領域の名前としている。
【００６４】
図４Ｂは、区画を初期化する後段の処理フロー例を説明する図である。
ステップＳ４１１では、主区分番号に、先頭番号に区分数を加えて１を減じた値を設定する。ステップＳ４１１の最初の処理においては、区分数にはステップＳ４１０の処理により１が設定されており、それ以後の処理においては、後記ステップＳ４２３の処理によりその値が設定されている。
【００６５】
次にステップＳ４１２において、主区分レベルの指す主区分番号管理表に、主区分番号を設定し、ステップＳ４１３で、主区分レベルの指す先頭番号管理表に、先頭番号を設定する。図３の例示におけるステップＳ４１２及びステップＳ４１３の最初の処理では、主区分番号管理表３０９ａと先頭番号管理表３０９ｂの区分レベル５にそれぞれ０が設定される。
【００６６】
次にステップＳ４１４に進み、主区分レベルの指す区分レベルの多層区分割付表の割付状態を初期化する。ステップＳ４１４の処理の詳細は、後に図４Ｃを参照して説明する。
【００６７】
次にステップＳ４１５において、総区分数管理表の総区分数に、ステップＳ４１４で得た区分数を加え、ステップＳ４１６に進む。
ステップＳ４１６では、主区分レベルは最下位の区分レベルか判定し、最下位の区分レベルであれば処理を終了し、最下位の区分レベルでなければステップＳ４１７に分岐する。
ステップＳ４１７では、主区分レベルを１つ減らし、ステップＳ４１８で先頭番号に区分数を加え、ステップＳ４１９で区分数を２倍にしてステップＳ４２０に進む。
【００６８】
ステップＳ４２０では、主区分レベルの指す区分レベルの区画構成主区分表のビット値を取り出し、ステップＳ４２１で、その取り出したビット値が有意、すなわち値１であるか判定する。ステップＳ４２０で取り出した主区分レベルの指す区画構成主区分表のビット値が有意でなければステップＳ４２２に分岐して主区分番号に値“−１”を設定してステップＳ４１２に戻り、有意であれば、ステップＳ４２３に分岐して、区分数に１を加えてステップＳ４１１に戻る。
上記ステップＳ４１１〜ステップＳ４２３のループ処理を、ステップＳ４１６で主区分レベルは最下位の区分レベルであると判定されるまで繰り返す。その際、主区分レベルの指す区分レベルの区画構成主区分表のビットが無為ビット、すなわちそのビット値が“０”であれば、上述のとおり、その区分レベルの主区分番号には値“−１”を設定する。
【００６９】
図３に示す例では、先頭番号管理表３０９ｂの区分レベル４には１が設定され、主区分番号管理表３０９ａの区分レベル４には、ステップＳ４１１の２度目の処理において、先頭番号１と区分数３の和から１を減じた３が設定される。また、先頭番号管理表３０９ｂの区分レベル３には区分レベル４の先頭番号１に区分数３を加えた４が設定され、主区分番号管理表３０９ａの区分レベル４には、ステップＳ４２２の処理において、−１が設定される。以下同様に、主区分番号管理表３０９ａの区分レベル２、１、０には、それぞれ２２、−１、−１が設定される。また、先頭番号管理表３０９ｂの区分レベル２、１、０には、それぞれ１０、２３、４９が設定され、総区分数管理表３０９ｃには、１０１が設定される。
【００７０】
図４Ｃは、本発明の一実施形態における、多層区分割付表を区分レベル毎に初期化する処理フロー例を説明する図である。図４Ｃに例示する処理フローにより、多層区分割付表を構成する最下位の区分レベルから区画構成主区分表のビット値が１である最上位の区分レベルまでの各区分レベルに対応した区分割付表を初期化する。図３の例では、区分割付表１６０〜１６５それぞれの値を図示した値に設定する処理である。図４Ｂに示すステップＳ４１１〜ステップＳ４２３のループ処理を実行する毎に、区分割付表１６５から区分割付表１６０までの区分割付表の初期化が行われ、多層区分割付表３１０の初期化が完了する。  
【００７１】
図４Ｃに示すように、ステップＳ４３１で区分番号に先頭番号を設定し、ステップＳ４３２で末尾番号に先頭番号に区分数を加えて１を減じた値を設定する。ステップＳ４３１及びステップＳ４３２での先頭番号は、図４Ａに示すステップＳ４０９あるいは図４Ｂに示すステップＳ４１８で設定されたものである。また、ステップＳ４３２での区分数は、図４Ａに示すステップＳ４１０もしくは図４Ｂに示すステップＳ４１９あるいはステップＳ４２３で設定されたものである。
【００７２】
ステップＳ４３１とステップＳ４３２の処理は、各区分レベルに対応した区分割付表の先頭の区分番号と末尾の区分番号をそれぞれ設定する処理である。
次にステップＳ４３４において、区分番号と末尾番号は等しいか判定する。区分番号と末尾番号が等しくなければ、ステップＳ４３５で、区分番号の指す多層区分割付表の割付状態に保留を設定し、ステップＳ４３６で、区分番号を１つ増やしてステップＳ４３４に戻り、区分番号と末尾番号は等しいかの判定を繰り返す。このステップＳ４３４〜ステップＳ４３６のループ処理は、処理中の区分レベルに対応した区分割付表の先頭の区分番号から末尾番号の１つ前の区分番号まで、区分番号の指す区分割付表の割付状態に保留を設定する処理である。
【００７３】
一方、ステップＳ４３４において、区分番号と末尾番号は等しいと判定されると、ステップＳ４３７に進み、主区分番号は値“−１”であるか判定する。ここでの主区分番号は、図４Ｂに示すステップＳ４１１あるいはステップＳ４２２で設定されたものである。
【００７４】
ステップＳ４３７で、主区分番号は値“−１”であると判定されると、ステップＳ４３８で区分番号の指す多層区分割付表の割付状態に保留を設定して処理を終了し、ステップＳ４３７で、主区分番号は値“−１”ではないと判定されると、ステップＳ４３９で区分番号の指す多層区分割付表の割付状態に空を設定して処理を終了する。
このステップＳ４３８とステップＳ４３９の処理は、処理中の区分レベルに対応した区分割付表の末尾の区分番号の割付状態を設定する処理である。図３に例示するように、主区域に対応する区分ユニットの区分番号は、その主区域の区分レベルに対応する区分番号の末尾であり、その末尾の区分番号の区分割付表の割付状態は、区分番号０、３、２２の割付状態に見られるように“００”、すなわち空である。そのほかの多層区分割付表の割付状態は、全て“１０”、すなわち保留である。
【００７５】
以上詳細に説明した区画の初期化において、区域の割付状態に「空」のほかに「保留」を導入したのは、連続した大きな空の区域の確保を容易にするためである。例えば図３の例で、ファイルシステムからサイズが１６の区域の割付を要求された場合、空状態の区域である主区域の中から主区域１８４、すなわち区分番号３の区域を選択することができる。もし、保留という割付状態がないと、区分番号１、２の区域も空となり、すると、将来サイズが１６より大きい区域の割付要求が発生する場合に連続する区域を割り付けられるように、区分番号１、２、３の中から区分番号３の区域を選択する手段が区域を有効に利用するために必要になる。しかしその手段は割付状態に「保留」を導入するよりも複雑になる。
【００７６】
なお、本実施の形態においては、「保留」という状態を導入し、それを２ビットの値“１０”で表すが、上述の説明のとおり、区域の割付状態を保留に設定するのはその区域を割付の対象から除くためである。したがって、上述のステップＳ４３８において、区分番号の指す多層区分割付表の割付状態に、その区分番号の区域への割付を行わないことを示す空以外の状態を設定することもできる。
【００７７】
次に、図５〜図１１Ｃを参照して、本発明の一実施形態における多層区分管理情報を用いた区域の割付について説明する。先に図２Ｂの説明において述べたように、区域の割付は、区画の初期化の後、ファイルシステムからの割付要求サイズを含む割付要求を受け付けることにより、アロケーションシステムの多層区分管理部により行われる。
【００７８】
図５は、区域の割付を行う処理全体の概略の処理フロー例を説明する図である。
まず、ステップＳ５０１で、割付要求サイズを設定し、ステップＳ５０２で、割付要求区分レベルとして、割付要求サイズを内包する最小の２のべき乗サイズのべき数を設定する。例えば、割付要求サイズが１１（２進数表示で“０１０１１”）であれば、割付要求区分レベルは、１６（２進数で「１００００」）＝２４のべき数である４が設定される。また割付要求サイズが２のべき乗である８であれば、そのべき数である３が設定される。
【００７９】
次にステップＳ５０３で、多層区分割付表を参照して、割付要求区分レベルの区域のうち、その区域の割付状態が「空」である空区域を探索し、空区域の区分番号を取得する。ステップＳ５０３の処理の詳細については、後に図６を参照して説明する。
【００８０】
ステップＳ５０４で、空状態の区域の区分番号を取得することができたかを判定し、取得できた場合はステップＳ５０７に進み、取得できなかった場合はステップＳ５０５に進む。
ステップＳ５０５では、多層区分割付表を参照して割付要求区分レベルの区域のうち割付状態が「空候補」である空候補区域を探索し、空候補区域の区分番号を取得する。ステップＳ５０５の処理の詳細については、後に図９を参照して説明する。
ステップＳ５０６で、空候補状態の区域を取得することができたか否かを判定し、取得できた場合はステップＳ５０７に移行し、取得できなかった場合は取得失敗として区域割付処理を終了する。
【００８１】
ステップＳ５０７では、ステップＳ５０３の処理で取得した区分番号の区分レベルに対応する区域のサイズがステップＳ５０１で設定した割付要求サイズより大きいか判定する。割付要求サイズが２のべき乗と等しくない、すなわち２進数形式で表示したとき有意のビット位置が複数（この場合の割付要求をマルチビット要求といい、一方、割付要求が２のべき乗に等しいとき、シングルビット要求ということがある。）であれば、取得される区域のサイズは割付要求サイズより大きい。したがって、ステップＳ５０７の判定は、割付要求がマルチビット要求であるかシングルビット要求であるかを判定するものである。
【００８２】
ステップＳ５０７での判定がシングルビット要求であればステップＳ５０９に進み、ステップＳ５０７での判定がマルチビット要求であればステップＳ５０８に分岐する。ステップＳ５０８では、取得した区分番号に対応する一次割付区域を多層区域に区分し、割付要求区分の二次割付区域を得てステップＳ５０９に進む。なお、二次割付で得られる領域は、複数の区域からなる多層区域であるが、以下ではその領域を二次割付区域という。
ステップＳ５０８の処理の詳細については、後に図１１Ａ〜図１１Ｃを参照して説明する。また、一次割付及び二次割付についても後に詳細に説明する。
【００８３】
ステップＳ５０９では、割付結果として、割付区分番号に一次割付された割付区域の区分番号を設定し、処理を終了する。ここで設定された割付区分番号が、図２Ａに示すように、割付結果としてファイルシステムに返される。アロケーションシステムの多層区分管理部は、ファイルシステムに割り付けられた区画の先頭位置から、割付要求されてファイルに割り付けた領域の先頭位置までの相対アドレスを、そのファイルに対応する割付区分番号を用いて多層区分管理表から求めることができる。
【００８４】
次に、図５のステップＳ５０３、ステップＳ５０５及びステップＳ５０８の処理の詳細を説明する。
図６は、図５のステップＳ５０３の処理の詳細を説明するものであり、多層区分割付表より、割付要求区分レベルの空区域を探索し、空区域の区分番号を取得する処理フロー例を説明する図である。
【００８５】
図に示すように、ステップＳ６０１で、多層区分割付表より、割付要求区分レベルのサイズを含む空区域を探索し、空区域の区分番号を取得する。本発明の一実施形態の多層区分管理によれば、割付要求区分レベルの空区域を見つけだすことができない場合でも、割付区分レベルより大きい区分レベルの空区域が存在すればそれを見つけることができる。例えば図３に示す例において、割付要求区分レベルが３の場合、区分レベル３の区分割付表１６３に示すとおり、区分レベル３の区域には空はない。しかし、区分レベル２には区分番号３の空区域が存在し、この区分番号３を取得する。このように、割付区分レベルより大きい区分レベルの空区域を割り付けることを、仮割付ということがある。ステップＳ６０１の詳細については、後に図７Ａ〜図７Ｄを参照して説明する。
【００８６】
次にステップＳ６０２で、ステップＳ６０１の処理において区分番号は取得できたか判定し、取得できていなければ取得失敗を返して処理を終了し、取得できていればステップＳ６０３に進む。
ステップＳ６０３では、ステップＳ６０１の処理で取得した区分番号に係る区分レベル（取得した区分レベル）と割付要求区分レベルが等しいか判定する。この判定は、仮割付が行われたか否かの判定に相当する。取得した区分レベルと割付要求区分レベルが等しければ、取得成功を返して処理を終了し、取得した区分レベルと割付要求区分レベルが等しくない、すなわち仮割付が行われた場合はステップＳ６０４に分岐する。
【００８７】
ステップＳ６０４では、仮割付された仮割付区域を多層区域に区分し、割付要求区分レベルの区分番号の一次割付区域を得る。すなわち、一次割付として割付要求区分レベルのサイズの区域を取得し、その区分番号を取得して、取得成功を返して処理を終了する。ステップＳ６０４の詳細は、後に図８Ａ及び図８Ｂを参照して説明する。
【００８８】
図７Ａは、図６のステップＳ６０１の処理の詳細を説明するものであり、多層区分割付表より、割付要求区分レベルのサイズを含む空区域を探索し、空区域の区分番号を取得する処理フロー例を説明する図である。
【００８９】
図に示すようにステップＳ７０１において、区分レベルに、割付要求区分レベルを設定する。ここで割付要求区分レベルの値は、図５のステップＳ５０２で設定されたものである。
次に、ステップＳ７０２において、先頭番号管理表より、区分レベルの指す先頭番号を取り出す。そして、ステップＳ７０３ａで、区分番号に、取り出した先頭番号を設定し、ステップＳ７０３ｂで、現在処理中である区分レベルの区分割付表の区分番号の末尾の番号を末尾番号に設定する。ステップＳ７０３ｂの処理の詳細は、後に図７Ｄを参照して説明する。
【００９０】
次にステップＳ７０４で、区分番号に設定された値の指す多層区分割付表の割付状態を読み出す。そして、ステップＳ７０５で、読み出した割付状態は空であるかを判定する。ステップＳ７０５の判定において、割付状態が空であると判定されると、ステップＳ７１０に進む。
【００９１】
一方、ステップＳ７０５の判定において、割付状態は空ではないと判定されると、ステップＳ７０６に分岐する。そして、ステップＳ７０６で、区分番号とステップＳ７０３ｂで設定した末尾番号とが等しいかを判定する。区分番号と末尾番号とが等しくない場合は、ステップＳ７０７に分岐し、区分番号を１加算してステップＳ７０４に戻る。以降は同一区分レベル内において区分番号を１ずつ加算してゆき、空状態の区域を検索していく。
【００９２】
ステップＳ７０６において、区分番号と末尾番号が等しいと判定されると、ステップＳ７０８に進み、区分レベルは最上位の区分レベルであるか否かを判定する。区分レベルが最上位の区分レベルである場合、取得失敗を返して処理を終了する。
ステップＳ７０８において区分レベルが最上位の区分レベルでないと判定された場合（区分レベルが最上位の区分レベルよりも下位の区分レベルである場合）は、ステップＳ７０９に進み、区分レベルを１加算してステップＳ７０２に戻る。
【００９３】
ステップＳ７０２に戻ると、上記の処理を繰り返し、１つずつ上位の区分レベルについての多層区分割付表の割付状態を探索していく。探索の結果空状態の区域が得られたときは、ステップＳ７１０に進む。
【００９４】
ステップＳ７１０では、区分番号に設定された値の指す多層区分割付表の割付状態を使用中に設定して処理を終了する。図７Ａの処理結果としては、一時記憶領域である区分番号と区分レベルにそれぞれ設定された値と取得成功あるいは取得失敗を示すデータが検索結果として出力される。
【００９５】
図７Ｂ及び図７Ｃは、図３に示す多層区分管理表３１０を参照して図７Ａに示す空区域の探索処理を具体例により説明する図である。
図７Ｂに示す例は割付要求がマルチビット要求であって割付要求区分レベルで空区域が探索される例である。図に示すように、割付要求サイズ２２０の１ビット目（区分レベル１）と３ビット目（区分レベル３）にビット値１が設定されている。したがって、割付要求区分レベル２３４には、点線の矢印２２４で示すように、区分レベル３の上位の区分レベル４が設定されている。ここまでの設定は、図５のステップＳ５０１とステップＳ５０２の処理で行われる。
【００９６】
次に図の実線の矢印で示す区分レベル４の割付要求２４０により、多層区分割付表３１０の、符号１６４ａを付した割付前の区分レベル４の区分割付表の空探索２４４が行われる。図の例では区分番号１７１が１と２の割付状態が“１１”で使用中であり、区分番号が３の割付状態が“００”で空である。したがって、図の実線の矢印で示すように空区域の取得２７４ａが行われ、符号１６４ｂを付した割付後の区分レベル４の区分割付表に示すように、区分番号１７１が３の割付状態に
“１１”が設定され、使用中であることが表示される。その結果、図の矢印２７４に対応を示すように、区画３１１には、区分レベルが４で区分番号は３の区域が一次割付区域２８０として割り付けられる。
上述の一次割付区域２８０の割付は、図７Ａに示すステップＳ７０４〜ステップＳ７０７のループ処理とステップＳ７１０の処理により実行される。
【００９７】
次に図７Ｃに示す例により割付要求がシングルビット要求であって割付要求区分レベルでは空区域が探索できない場合を説明する。図７Ｃには割付要求サイズ２２０は記載していないが、点線の矢印で示す割付要求２４１ａが割付要求区分レベル１のものであるから、割付要求は１ビット目のみが１のシングルビット要求である。
【００９８】
割付要求区分レベルでは空区域が探索できない場合は、図７Ａに示すフローでは、ステップＳ７０６でステップＳ７０８に分岐し、ステップＳ７０９を経由してステップＳ７０２の戻るループ処理を、上位の区分レベルにおいて空区域を見つけるまで繰り返すことになる。
【００９９】
この繰り返し処理に対応するのが、図７Ｃに示す、下位の区分レベル（図７Ｃにおいては区分レベル１）から順次上位の区分レベルの区分割付表を参照していき、探索した区分レベル内に空状態の区域がない場合に更に上位の区分レベルを探索していく処理である。区分レベル１から順に各区分レベルの区域について先頭番号から順に空状態を探索してゆく。
【０１００】
まず、図の点線の矢印２４１ａで示す割付要求区分レベルである区分レベル１の空区域の探索が要求され、多層区分割付表３１０のうち、区分レベル１の区分割付表１６１の割付状態を区分番号の昇順に先頭番号である区分番号２３から末尾番号である区分番号４８まで空状態を探索（図７Ｃの矢印２４１ｂ参照）してゆく。図に示す例においては、区分番号が末尾番号である４８の区域まで探索しても空状態の区域がないので、図の点線の矢印２４２ａで示す区分レベルを１加算した上位区分である区分レベル２の空区域の探索が要求される。そして、区分レベル２の区分割付表１６２の割付状態を区分番号の昇順に先頭番号である区分番号１０から末尾番号である区分番号２２まで空状態を探索（図７Ｃの矢印２４２ｂ参照）してゆく。区分番号が末尾番号である２２の区域まで探索しても空状態の区域がないので、区分レベルを１加算して上位区分である区分レベル３の空状態の探索が要求される（図７Ｃの矢印２４３ａ参照）。同様に区分レベル３の区分割付表１６３についても先頭番号である区分番号４の区域から末尾番号である区分番号９の区域までの割付状態を順次探索（図７Ｃの矢印２４３ｂ参照）してゆくが、空区域が得られないため、区分レベルを１加算して上位区分である区分レベル４の空区域探索が要求される（図７Ｃの２４４ａ参照）。
図７Ｃの例示では、符号１６４ａを付した割付前の区分レベル４の区分割付表の空区域の探索（図７Ｃの２４４ｂ参照）の結果、区分番号が２の区域が、割付状態が“００”の空区域として得られ、図７Ｃの矢印で示す空取得２４４ｃに対応を示すように、符号１６４ｂを付した割付後の区分レベル４の区分割付表の区分番号２の割付状態が、使用中を表示する“１１”に変更される。すなわち、矢印２４４ｄで示すように、区分番号２の区域が仮割付され、仮割付区域２８０ａとして得られる。
【０１０１】
なお、空区域の探索処理については、上記の区分番号を昇順に探索する方法に限定されるものではなく、任意の探索アルゴリズムを採用してもよい。
次に、現在処理中である区分レベルの区分割付表の区分番号の末尾の番号を取得する処理を説明する。
【０１０２】
図７Ｄは、本発明の一実施形態における、各区分レベルの末尾の区分番号を取得する処理フロー例を説明する図である。
図７Ｄに示すように、ステップＳ７２１で、現在処理中の区分レベルは最下位の区分レベルか判定し、最下位の区分レベルでなければステップＳ７２２に進み、最下位の区分レベルであればステップＳ７２４に進む。
【０１０３】
ステップＳ７２２では、先頭番号管理表より、区分レベルを１つ減らした値の指す先頭番号を取り出し、ステップＳ７２３で、その取り出した先頭番号より１つ減らした値を末尾番号に設定して処理を終了する。
一方、ステップＳ７２４では、総区分数管理表より、総区分数を取り出し、ステップＳ７２５で、その取り出した総区分数より１つ減らした値を末尾番号に設定して処理を終了する。
以上図７Ａ〜図７Ｄを参照して説明した処理により、一次割付領域あるいは仮割付領域が得られる。
【０１０４】
図８Ａは、図６のステップＳ６０４の処理の詳細を説明するものであり、ステップＳ６０１の処理で得られた仮割付区域を多層区分し、割付要求区分レベルの区分番号の一次割付区域を得る処理フロー例を説明する図である。
【０１０５】
先ず、ステップＳ８０１で、先頭番号管理表より、図６のステップＳ６０１で取得した区分レベルの指す先頭番号を取り出す。図８Ａの処理フローは仮割付が行われたことを前提としていることから、取得した区分レベルは割付要求区分より大きい。次にステップＳ８０３で、レベル内番号に、取得した区分番号からステップＳ８０１で取り出した先頭番号を減算して得られる値を設定する。次にステップＳ８０４において、区分レベルに、取得した区分レベルよりも１つ減じた値を設定してステップＳ８０５に進む。
【０１０６】
ステップＳ８０５では、先頭番号管理表より、区分レベルの指す先頭番号を取り出す。そして、ステップＳ８０７で、レベル内番号に、該レベル内番号に設定された値を２倍した値を設定する。この処理は、ある区域に対応する１つ下位の区分レベルにおける区域は、２つずつ存在していることに対応している。
【０１０７】
次にステップＳ８０８で、区分番号に、先頭番号にレベル内番号を加えた値を設定する。ステップＳ８０９では、対の区分番号に、区分番号に１を加算して得られる値を設定する。例えば、ある区分レベルにおけるレベル内番号が「１０」である区域を２分割した１つ下位の区分レベルにおける区域のレベル内番号は「２０」及び「２１」となる。
【０１０８】
次にステップＳ８１０で、区分番号の指す多層区分割付表の割付状態に、使用中を設定し、ステップＳ８１１で、対の区分番号が指す多層区分割付表の割付状態に、空を設定してステップＳ８１２に進む。
【０１０９】
ステップＳ８１２では、区分レベルは割付要求区分レベルよりも大きいかを判定し、大きければステップＳ８１３に分岐して区分レベルに設定された値を１つ減らしてステップＳ８０５に戻る。判定結果が大きくない、すなわち区分レベルは割付要求区分レベルと等しければ、処理を終了する。先に説明したように、取得した区分レベルは割付要求区分より大きい。そして区分レベルを１つずつ減らしながらステップＳ８０５からステップＳ８１３のループ処理を繰り返すことから、ステップＳ８１２で区分レベルが割付要求区分レベルよりも大きくないと判定されるのは、区分レベルが割付要求区分レベルと等しくなったときである。
【０１１０】
以上の処理により、仮割付された区域を多層区分し、一次割付された区域が得られる。上記ステップＳ８０４の処理とステップＳ８０５〜ステップＳ８１３のループ処理は、仮割付された区域からスタートして、区域を１つ下位の区分レベルの２つの区域の対に分割し、若番側の区域の割付状態に使用中を、老番側の区域の割付状態に空を設定するものである。
【０１１１】
本発明の一実施形態によれば、取得した仮割付区域の全体を使用中とすることなく、割付要求区分レベルの区域を仮割付区域の区分番号の若番側に一次割付し、残りの連続領域を空と設定するので、領域を効率的に利用することができる。なお、一次割付を区分番号の若番側とすることに限らず、老番側とすることも可能であることは当業者に明らかである。
【０１１２】
図８Ｂは、図３に示す多層区分管理表３１０を参照して、図８Ａに示す仮割付区域を多層区分して一次割付区域を得る処理を、具体例により、説明する図である。
図８Ｂに示す例は、図７Ｃに例示するものと同様に、割付要求がシングルビット要求のものであり、図７Ｃに示す仮割付区域２８０ａから一次割付区域を取得するものである。
【０１１３】
図８Ｂには、符号２８０ａで一次割付前の割付状態である仮割付区域（区分番号２）が示されている。仮割付区域２８０ａからの矢印２４１で示す、仮割付区域の区分レベル４から区分レベル１までの関係する各区域の区分を要求する多層区分要求により、符号１６４ｂを付した区分レベル４の区分割付表から処理が開始される。区分割付表１６４ｂには、図７Ｃに示すものと同じ割付状態が格納されている。
【０１１４】
割付状態が仮割付により使用中に設定された、区分レベル４の区分割付表１６４ｂの区分番号１７１の値が２でレベル内番号１７２の値が１のエントリからの矢印２７４ａに示す区分要求により、区分レベル３の区分割付表１６３におけるレベル内番号２の区分ユニットの区分けによる区域（以下、「レベル内番号２の区域」のように表記する。）の割付状態に使用中“１１”が設定され、レベル内番号２の区分ユニットと区分対２９３ａを構成するレベル内番号３の区分ユニットの区分けによる区域（以下、「レベル内番号２の区域と区分対２９３ａを構成するレベル内番号３の区域」のように表記する。）の割付状態に空“００”が設定される。この設定処理は、区分レベル３における図８ＡのステップＳ８０５〜ステップＳ８１１の処理で実行される。先頭番号として４が取り出され、図８ＡのステップＳ８０１〜ステップＳ８０３の初期処理によりレベル内番号には１が設定されていることから、ステップＳ８０７でレベル内番号にはそれを２倍した２が設定される。そして、区分番号として、先頭番号４にレベル内番号２を加えた６が求められる。また対の区分番号として７が得られる。
【０１１５】
以下同様に、使用中の区分番号６のエントリに対応して矢印２７３ａに示す区分要求により、区分レベル２の区分割付表１６２におけるレベル内番号４（区分番号１４）の区域の割付状態に使用中“１１”が設定され、レベル内番号４の区域と区分対２９２ａを構成するレベル内番号５（区分番号１５）の割付状態に空“００”が設定される。
一方、区分番号７の割付状態は空に設定されたことから、矢印２７３ｂで対応を示すように、符号２８０ｂを付した一次割付後の仮割付区域に、空状態の区分番号７の区域２８３ｂが割り付けられる。
【０１１６】
次に使用中の区分番号１４のエントリに対応して矢印２７２ａに示す区分要求により、区分レベル１の区分割付表１６１におけるレベル内番号８（区分番号３１）の区域の割付状態に使用中“１１”が設定され、レベル内番号８の区域と区分対２９１ａを構成するレベル内番号９（区分番号３２）の割付状態に空“００”が設定される。そして、区分番号１５の割付状態は空に設定されたことから、矢印２７２ｂで対応を示すように、一次割付後の仮割付区域２８０ｂに、空状態の区分番号１５の区域２８２ｂが割り付けられる。
【０１１７】
多層区分要求は区分レベル１までであるから、矢印２７１ａと矢印２７１ｂでそれぞれ対応を示すように、一次割付後の仮割付区域２８０ｂに、区分番号３１の区域２８１ａが使用中として一次割付され、区分番号３２の区域２８１ｂが空として割り付けられる。
【０１１８】
上述の多層区分により、一次割付後の仮割付区域２８０ｂは、図に示すような使用中の一次割付領域２８１ａと空である区域２８１ｂ、２８２ｂ、２８３ｂからなる、一次割付領域２８１ａに隣接する隣接多層区域２９０ｂに分割される。
【０１１９】
図９は、図５のステップＳ５０５の処理の詳細を説明するものであり、多層区分割付表より、割付要求区分レベルの空候補区域を探索し、空候補区域の区分番号を取得する処理フロー例を説明する図である。空候補は、後に図１１Ａ〜図１１Ｃを参照して説明する、マルチビット要求における一次割付領域を分割して二次割付を行ったときの残りの隣接多層区域を構成する区域の割付状態として設定される。
【０１２０】
空候補区域の探索は空区域の探索と同様に行われ、空候補区域探索の図９に示すフローは、図６に示す空区域探索のフローに対応するものであり、図９のステップＳ９０１〜ステップＳ９０４は、図６に示すステップＳ６０１〜ステップＳ６０４において、空区域を空候補区域と読み替えたものであるので、説明を省略する。
【０１２１】
また、図９のステップＳ９０１の処理の詳細を説明する図１０Ａは、多層区分割付表より、割付要求区分レベルのサイズ以上の空候補区域を探索し、空候補区域の区分番号を取得する処理フローを説明する図であり、図７Ａに示す、多層区分割付表より、割付要求区分レベルのサイズ以上の空区域を探索し、空区域の区分番号を取得する処理フローを説明する図に対応する。図１０ＡのステップＳ１００１〜ステップＳ１００９は、図７Ａのステップ７０５において割付状態は空か判定しているのに対して、ステップＳ１００５で割付状態は空候補か判定しているところで異なるだけであるので、図１０Ａについての説明も省略する。
【０１２２】
また同じく、図９のステップＳ９０４の処理の詳細を説明する図１０Ｂは、ステップＳ９０１の処理で得られた仮割付区域を多層区分し、割付要求区分レベルの区分番号の一次割付区域を取得する処理フローを説明する図であり、図８Ａに示す、図６のステップＳ６０１の処理で得られた仮割付区域を多層区分し、割付要求区分レベルの区分番号の一次割付区域を取得する処理フローを説明する図に対応する。図１０ＢのステップＳ１０２１〜ステップＳ１０３３は、図８Ａのステップ８１１において、対の区分番号が指す多層区分割付表の割付状態に空を設定しているのに対して、ステップＳ１０３１で対の区分番号が指す多層区分割付表の割付状態に空候補を設定しているところで異なるだけであるので、図１０Ｂについての説明も省略する。
【０１２３】
次に、図１１Ａ〜図１１Ｃを参照して、図５のステップＳ５０８の処理を詳細に説明する。
図１１Ａは、取得した区分番号の一次割付区域を多層区域に区分し、割付要求区分の二次割付区域を得る前段の処理フローを説明する図である。
【０１２４】
まず、ステップＳ１１０１で、先頭番号管理表より、取得した一次割付区域の区分レベル（取得区分レベル）が指す先頭番号を取り出し、ステップＳ１１０３で、レベル内番号として、取得した一次割付区域の区分番号から先頭番号を減算した結果を２倍した値を設定する。
【０１２５】
次にステップＳ１１０４で、一次割付区域を分割するために、割付要求サイズから、割付要求サイズを２進数表示したビット値からなる割付構成区分表を作成する。そして、ステップＳ１１０５で、分割区分レベルとして、取得区分レベルから１減算した値を設定する。
【０１２６】
次にステップＳ１１０６で、最小分割区分レベルとして、割付構成区分表のうちビット値が１であるビット位置で且つ下位０ビット目から見て最も下位のビット位置を設定し、図１１ＢのステップＳ１１０７に進む。例えば割付構成区分表のビット値が“１０１０”であるときは、ビット位置１が最小分割区分レベルに設定される。
【０１２７】
図１１Ｂは、取得した区分番号の一次割付区域を多層区分に分割し、割付要求区分の二次割付区域を得る後段の処理フローを説明する図である。
ステップＳ１１０７では、先頭番号管理表より、ステップＳ１１０５で設定した分割区分レベルの指す先頭番号を取り出す。
そしてステップＳ１１０９で、区分番号に、取り出した先頭番号にレベル内番号に設定された値を加えた値を設定し、ステップＳ１１１０で、対の区分番号に、区分番号に１を加えた値を設定する。
【０１２８】
次にステップＳ１１１１で、分割区分レベルの指す割付構成区分表からビット値を取り出し、ステップＳ１１１２で、取り出したビット値が１であるかを判定する。
ステップＳ１１１２において、取り出したビット値が１でない（０である）と判定された場合は、ステップＳ１１１３に分岐し、取り出したビット値が１であると判定された場合は、ステップＳ１１１５に進む。
【０１２９】
ステップＳ１１１３では、区分番号の指す多層区分割付表の割付状態に使用中を設定し、ステップＳ１１１４で、対の区分番号の指す多層区分割付表の割付状態に空候補を設定してステップＳ１１１９に進む。
一方、ステップＳ１１１５では、分割区分レベルはステップＳ１１０６で設定した最小分割区分レベルであるかを判定する。分割区分レベルと最小分割区分レベルとが等しくない場合は、ステップＳ１１１６に分岐し、等しい場合はステップＳ１１２１に進む。
【０１３０】
ステップＳ１１１６では、区分番号の指す多層区分割付表の割付状態に使用中を設定し、ステップＳ１１１７で、対の区分番号の指す多層区分割付表の割付状態に使用中を設定する。次にステップＳ１１１８で、レベル内番号を１加算し、上記のステップＳ１１１９に進む。
ステップＳ１１１９では、レベル内番号を２倍にし、ステップＳ１１２０に進み、分割区分レベルを１つ減らしてステップＳ１１０７に戻る。
【０１３１】
ステップＳ１１１５において分割区分レベルが最小分割区分レベルと等しいと判定されてステップＳ１１２１に進むと、区分番号の指す多層区分割付表の割付状態に使用中を設定し、ステップＳ１１２２で、対の区分番号の指す多層区分割付表の割付状態に空候補を設定して処理を終了する。
【０１３２】
図１１Ｃは、図３に示す多層区分割付表３１０を参照して、図１１Ａ及び図１１Ｂに示す一次割付区域を多層区分し、割付要求区分の二次割付区域を得る処理を、具体例により説明する図である。図１１Ｃに例示するものは、割付要求サイズ２２０に設定された値及び一次割付区域を区分番号３の一次割付区域２８０としていることから、図７Ｂに例示した一次割付に引き続き二次割付を行うものである。
【０１３３】
図７Ｂに示すものと同じく、割付要求サイズを２進数表示した割付要求サイズ２２０の１ビット目と３ビット目のビット値が１である。割付構成区分表２３０は、その下に０〜５で示すように区分レベルに対応する１ビットからなるエントリから構成されており、図１１Ｃの例示では、区分レベル０から最上位の区分レベル５に対応する６つのエントリを有している。図の点線の矢印２２３、２２１で対応を示すように、割付要求サイズを２進数形式で表示したときのビット値に応じて、対応する区分レベルのエントリのビット値が設定されている。ここまでの設定は、図５のステップＳ５０１と図１１ＡのステップＳ１１０４の処理で行われる。
【０１３４】
上述の割付構成区分表２３０のビット値に基づいて、二次割付が実行される。一次割付区域２８０からの矢印２４４で示す一次割付区域の最小分割区分レベルである区分レベル１までの多層区分要求により、符号１６４ｂを付した取得区分レベルである区分レベル４の区分割付表から多層区分が開始される。区分割付表１６４ｂには、図７Ｂに示すものと同じ割付状態が格納されている。
【０１３５】
区分レベル４の区分番号３の区域の区分要求２７４ｃについては、点線の矢印２３３で対応を示すように割付構成区分表２３０の区分レベル３に対応するビット値が１であることから、図１１ＢのステップＳ１１１６とステップＳ１１１７の処理により、区分レベル３の区域であって区分番号３の区域と同一の領域を占める１組の区域に対応する区分対２９３ｂである、区分レベル３の区分割付表１６３におけるレベル内番号４（区分番号８）とレベル内番号５（区分番号９）の双方の区分ユニットの割付状態に使用中を示す“１１”を設定する。
【０１３６】
図１１ＢのステップＳ１１１７に続くステップＳ１１１８の処理によりレベル内番号が１つ増えることから、次には区分レベル３のレベル内番号５（区分番号９）の区域が区分要求２７３ｄの対象となる。点線の矢印２３２で対応を示すように割付構成区分表２３０の区分レベル２に対応するビット値が０であることから、図１１ＢのステップＳ１１１３とステップＳ１１１４の処理により、区分レベル２の区域であって区分番号９の区域と同一の領域を占める１組の区域に対応する区分対２９２ｂである、区分レベル２の区分割付表１６２におけるレベル内番号１０（区分番号２０）の割付状態に使用中を示す“１１”を設定し、レベル内番号１１（区分番号２１）の割付状態に空候補を示す“０１”を設定する。
【０１３７】
次には区分レベル２のレベル内番号１０（区分番号２０）の区域が区分要求２７２ｃの対象となる。点線の矢印２３１で対応を示すように割付構成区分表２３０の区分レベル１に対応するビット値が１であり、かつ区分レベル１が最小分割区分レベルであることから、図１１ＢのステップＳ１１２１とステップＳ１１２２の処理により、区分レベル１の区域であって区分番号２０の区域と同一の領域を占める１組の区域に対応する区分対２９１ｂである、区分レベル１の区分割付表１６１におけるレベル内番号２０（区分番号４３）の割付状態に使用中を示す“１１”を設定し、レベル内番号２１（区分番号４４）の割付状態に空候補を示す“０１”を設定する。
【０１３８】
以上で二次割付に伴う多層区分割付表３１０の更新が完了する。この多層区分割付表３１０の更新により、一次割付区域２８０は、二次割付後の一次割付区域２８０ｃに示すように多層区分される。矢印２７３ｃで対応を示すように、区分レベル３の区分番号８の区域２８３ｃが使用中として割り付けられ、それに連続して、矢印２７１ｃで対応を示すように区分レベル１の区分番号４３の区域２８１ｃが使用中として割り付けられて多層区域として二次割付区域２９０ｃが割り付けられる。一方、矢印２７２ｄで対応を示すように、区分レベル２の区分番号２１の区域２８２ｄが空候補として割り付けられ、それに連続して、矢印２７１ｄで対応を示すように区分レベル１の区分番号４４の区域２８１ｄが空候補として割り付けられ、併せて隣接多層区域２９０ｄとして割り付けられる。二次割付区域２９０ｃでは、区域が区分レベルの降順で割り付けられ、隣接多層区域２９０ｄでは、区域が二次割付区域とは逆順である区分レベルの昇順で割り付けられる。
【０１３９】
二次割付を行った場合でも、割付区分番号として一次割付で取得した区分番号がファイルシステムに返されるが、上記説明から明らかなとおり、一次割付で取得した区分番号（上記例では３）の区域の先頭位置と、二次割付を行った二次割付区域の先頭位置は同一であることから、ファイル操作システムからの区分番号を指定した割付領域のアドレス問い合わせに対応することができる。
なお、上述の説明では、二次割付を区分番号の若番側から行っているが、先に仮割付後の一次割付について述べたように、区分番号の老番側から行うことができることは、当業者に明らかである。
【０１４０】
次に、図１２〜図１７Ｃを参照して、本発明の一実施形態における割付区域の解放について説明する。区域の割付と同様に、ファイルの削除などによる区域の解放処理もアロケーションシステムの多層区分管理部により行われる。
【０１４１】
図１２は、割付区域を解放し、空区域の連結を試みる処理全体の概略の処理フロー例を説明する図である。図１２に示す割付区域の解放処理と空区域の連結により、解放した割付区域を含む区域の割付状態を設定し直して、その区域を再割り付けすることが可能となる。
【０１４２】
図に示すように、ステップＳ１２０１において、区分番号に割付区域番号を設定する。この割付区域番号は、解放の対象となる区域がファイルに割り付けられたときにファイルシステムに返されたものであり、ファイルシステムからの割付区域の解放要求に含ませることができる。また、そのとき併せて割付要求サイズを含ませることもできる。
【０１４３】
次に、ステップＳ１２０２で、設定した区分番号により多層区分管理表を検索して、その区分番号に対応する区分レベルを求める。テップＳ１２０２の処理の詳細については、後に図１３を参照して説明する。
次にステップＳ１２０３に進み、ステップＳ１２０２の処理で区分レベルが求められたかを判定し、求められなかった場合は、処理を終了する。求められた場合は、ステップＳ１２０４に進む。
【０１４４】
ステップＳ１２０４では、解放区分レベルに、ステップＳ１２０２の処理で求められた区分レベルを設定し、ステップＳ１２０５において、連結要求と名付ける一時的記憶領域に、空区域の連結を試みるフラグとしてありを初期設定する。
【０１４５】
次に、ステップＳ１２０６において、区分番号の指す一次割付区域内に含まれる区域の解放と空区域の連結を試みる。元の割付要求がシングルビット要求であれば、ステップＳ１２０１で設定された区分番号の割付状態に空を設定すればステップＳ１２０６の処理は終了する。元の割付要求がマルチビット要求であれば、二次割付が行われており、二次割付領域の解放が行われるだけでなく、隣接多層区域の空候補区域と解放された区域とを連結して上位区分レベルの区域の割付状態を空とすることが試みられる。ステップＳ１２０６の処理の詳細は、後に図１４Ａ、図１４Ｂを参照して説明する。
【０１４６】
次にステップＳ１２０７において、連結要求はありか判定する。ありでなければ処理を終了し、ありであれば、ステップＳ１２０８において、区分番号の指す一次割付区域と隣接する隣接区域とを連結して上位の区域の割付状態を空とすることが試みられる。後の説明から明らかになるが、連結要求がありでステップＳ１２０８に進むのは、ステップＳ１２０６の処理で、一次割付区域が解放された場合である。ステップＳ１２０８の処理の詳細は、後に図１７Ａ、図１７Ｂ及び図１７Ｃを参照して説明する。
【０１４７】
ステップＳ１２０８の処理が終了すると図１２に示す処理は終了する。
図１３は、図１２のステップＳ１２０２の処理の詳細を説明するものであり、区分番号により多層区分管理表を検索し、その区分番号に対応する区分レベルを求める処理フロー例を説明する図である。
【０１４８】
先ず、ステップＳ１３０１で、総区分数管理表より、総区分数を取り出す。そしてステップＳ１３０２で、区分番号は有意かつ総区分数より小さいか判定する。ここで区分番号には、図１２のステップＳ１２０１で割付区域の解放要求元から与えられた割付区分番号が設定されている。ステップＳ１３０２の処理は、この割付区分番号の値が有効な範囲内であるかをチェックするとともに、以下の処理に対して、区分番号に対応する区分レベルの区分ユニットの存在を保証するものである。
【０１４９】
ステップＳ１３０２の判定結果が否定的なものであれば、該当する区分レベルなしを返して処理を終了し、肯定的なものであればステップＳ１３０３に進む。
ステップＳ１３０３では、区分レベルに初期値として多層区分管理表の最上位の区分レベルを設定する。図３に示す例では、区分レベルに７が設定される。
【０１５０】
次に、ステップＳ１３０４で、先頭番号管理表より、区分レベルの指す先頭番号を取り出し、ステップＳ１３０５で、取り出した先頭番号は有意であるかを判定する。先頭番号が有意でない場合はステップＳ１３０６に進み、区分レベルを１つ減らしてステップＳ１３０４に戻る。上述のステップＳ１３０４〜ステップＳ１３０６のループ処理は、最上位の区分レベルから実際に割り当てられた区域の区分レベルの１つ上位の区分レベルまでの区分レベルの判定処理をスキップするものである。
【０１５１】
一方、取り出した先頭番号が有意である場合はステップＳ１３０７に進み、区分レベルは最下位の区分レベルか判定する。区分レベルが最下位の区分レベルであれば、区分レベルありとして最下位の区分レベル０の情報を返して処理を終了する。区分レベルが最下位の区分レベルでなければ、ステップＳ１３０８に進み、先頭番号管理表より、区分レベルを１つ減らした値の指す先頭番号を、次の先頭番号として取り出し、ステップＳ１３０９で、区分番号は次の先頭番号より小さいかを判定する。区分番号は次の先頭番号より小さいと判定された場合は、区分レベルありとして区分レベルを返して処理を終了する。ステップＳ１３０９で、区分番号は次の先頭番号より小さくはないと判定された場合は、ステップＳ１３１０に進み、区分レベルを１つ減らしてステップＳ１３０７に戻る。
【０１５２】
上記のステップＳ１３０７〜ステップＳ１３１０のループ処理を区分レベルを１つずつ減らしながら繰り返し、区分レベルが最下位の区分レベルになる前に、ある区分レベルのステップＳ１３０９の判定において、区分番号が初めて次の区分レベルの先頭番号より小さくなったときの区分レベルが、区分番号の指す区分ユニットに係る区分レベルである。区分番号が次の区分レベルの先頭番号より小さくなる前に、区分レベルが最下位の区分レベルになると、最下位の区分レベル、すなわち区分レベル０が該当する区分レベルとなる。
【０１５３】
次に図１４Ａ、図１４Ｂを参照して、図１２のステップＳ１２０６の処理の詳細を説明する。
図１４Ａは、区分番号の指す一次割付区域内に含まれる区域の解放と空区域の連結を試みる処理フロー例を説明する図である。
【０１５４】
まずステップＳ１４０１において、割付要求サイズより、割付構成区分表を作成する。割付要求サイズは、先に述べたように区域の解放要求をしたファイルシステムの解放要求に含まれるものとすることができる。割付構成区分表は、図１１Ａに示すステップＳ１１０４の処理と同様に作成する。図１１Ａに示すものはマルチビット要求の割付要求についてのものであるが、シングルビット要求の場合ではビット値が１のビット位置が１か所の割付構成区分表が構成されることは明らかである。
【０１５５】
次にステップＳ１４０２において、最小区分レベルに、割付構成区分表の下位０ビット目から見た最初のビット１が立つビット位置を設定する。
ステップＳ１４０５では、割付構成区分表により、割付区域内の分割割付状況を求めて分割割付状況スタックにプッシュし、ステップＳ１４０７に進む。ここで、分割割付状況とは、割付区域を分割割付した区域の区分レベル、区分番号、解放表示である。区分レベルの指す割付構成区分表のビット値が１のときに、解放表示はありとされ、ビット値が０のとき、なしとされる。ステップＳ１４０５の処理の詳細については、後に図１５を参照して説明する。
【０１５６】
ステップＳ１４０７においては、分割割付状況スタックをポップして、区分レベル、区分番号、解放表示を読み出す。
次にステップＳ１４０９において、該読み出した区分レベルは解放区分レベルであるか判定し、区分レベルが解放区分レベルであればステップＳ１４１６に分岐し、解放区分レベルでなければステップＳ１４１１に進む。なお、元の割付要求がシングルビット要求であれば、最初のステップＳ１４０９の判定処理でステップＳ１４１６に分岐することになる。
【０１５７】
ステップＳ１４１１では、ステップＳ１４０７で読み出した解放表示はありを示しているか判定する。解放表示がありであればステップＳ１４１３に進み、解放表示がありでなければステップＳ１４１２に進む。
ステップＳ１４１２では、連結要求はありか判定する。ありであればステップＳ１４１３に進み、ありでなければステップＳ１４０７に戻る。
【０１５８】
ステップＳ１４１３では、区分番号の指す区分対の解放を試み、ステップＳ１４０７に戻る。ステップＳ１４１３の処理の詳細は、後に図１６を参照して説明する。
ステップＳ１４１４では、区分レベルを１つ上位のものとし、ステップＳ１４１５でレベル内番号に、レベル内番号を２で割った商を設定してステップＳ１４０７に戻る。
上述のステップ１４０９の判定で区分レベルは解放区分レベルと等しいと判定されて分岐するステップＳ１４１６以降の処理は、解放区分レベルの区域の解放処理である。
【０１５９】
ステップＳ１４１６では、連結要求はありか判定し、ありでなければ処理を終了し、ありであれば、ステップＳ１４１７において、区分番号の指す多層区分割付表の割付状態を空として処理を終了する。すなわち、マルチビット要求の場合でも、連結要求がありであれば、二次割付区域と隣接多層区域からなる一次割付区域についての割付状態は、ステップＳ１４１７の処理により空に設定される。
【０１６０】
図１４Ｂは、図３に示す多層区分割付表３１０を参照して、図１４Ａ及び後記図１６に示す一次割付区域内に含まれる区域の解放と空区域の連結を試みる処理を、具体例により、説明する図である。
図１４Ｂに示す例は、図１１Ｃに例示するものと同様なマルチビット要求で二次割付された二次割付区域を解放し、隣接区域と連結して上位区分レベルの区域の割付状態に空を設定するものである。したがって、割付要求サイズ２２０と割付構成区分表２３０に設定された値は図１１Ｃに示すものと同じである。
図１４Ｂに示す二次割付後の一次割付区域２８０ｃは、二次割付区域を解放し連結する前の割付状態のものであり、図１１Ｃに示す二次割付後の一次割付区域２８０ｃの空候補であった区分番号２１の区域２８２ｄが使用中となっている。区分番号４４の区域２８１ｄの割付状態は空候補のままである。
【０１６１】
解放と連結の処理は、割付構成区分表２３０のビット値を参照しながら、最小区分レベルである区分レベル１から上位の区分レベルへと順次行われていく。
まず、最小区分レベルである区分レベル１においては、割付構成区分表２３０の対応するビット値は１（点線の矢印２３１ａで対応を示す）である。すなわち、解放表示はありなので、図１４ＡのステップＳ１４１３、すなわち図１６に示す処理が実行される。区分レベル１の解放要求の矢印２５１ａが示すように、区域２８１ｃの解放が保障されていることと、符号１６１ｃを付した解放前の区分レベル１の区分割付表の、区分番号１７１の値が４３でレベル内番号１７２の値が２０の区域と対をなす区分番号４４の区域の割付状態が空候補であることから、後に説明する図１６のステップＳ１６０５での判定が肯定的なものとなり、区分番号４３の区域と区分番号４４の区域からなる区分レベル１の区分対２９１ｃの上位の区分レベルの区域の割付状態に空を設定する連結要求（矢印２４１ｃに示す）がありとされ、符号１６１ｄを付した解放後の区分レベル１の区分割付表に示すように、区分番号４３及び対の区分番号４４の割付状態には保留が設定される。上位区分レベルの区域の空が設定されるとき、その区域に包含される下位の区分レベルの区域の割付状態に保留を設定することは、図３に示す多層区分割付表３１０の初期設定の場合と同様である。
【０１６２】
区分レベル２においては、割付構成区分表２３０の対応するビット値は０（点線の矢印２３２ａで対応を示す）であり、連結要求２４１ｃがありなので矢印２４１ｄに示すように上位の区分の区域である、符号１６２ｃを付した解放前の区分レベル２の区分割付表の区分番号２０の区域の解放要求がされる。区分番号２０の区域と区分対２９２ｃを構成する区分番号２１の区域は使用中なので、図１６のステップＳ１６０５での判定が否定的なものとなり、矢印２４２ｃで示すように、区分番号２０の区域のみ解放され、区分対２９２ｃの割付状態は、符号１６２ｄを付した解放後の区分レベル２の区分割付表に示すように空と使用中になる。また、連結要求はなしとなる。したがって、点線の矢印２４２ｄに示すように区分対２９２ｃの上位の区域であり、符号１６３ｃを付した解放前の区分レベル３の区分割付表に示すように割付状態が使用中の区分番号９の区域は解放されない。
【０１６３】
次に区分レベル３においては、割付構成区分表２３０の対応するビット値は１（点線の矢印２３３ａで対応を示す）であり、区分レベル３の解放要求の矢印２５３ａが示すように、区域２８３ｃが解放される。しかし、先に述べたように、割付状態が使用中の区分番号９の区域は解放されず使用中である。したがって、矢印２４３ｃで示すように、区分番号９の区域と区分対２９３ｃを構成する区分番号８の区域のみ解放され、区分対２９３ｃの割付状態は、符号１６３ｄを付した解放後の区分レベル３の区分割付表に示すように空と使用中になる。また、連結要求はなしとなるので、点線の矢印２４４ｄに示すように区分対２９３ｃの上位の区域であり、符号１６４を付した解放前の区分レベル４の区分割付表に示すように割付状態が使用中の区分番号３の区域は解放されず、割付状態は使用中のままである。
【０１６４】
以上の区域の解放と連結の処理により、二次割付区域を解放した後の割付状態の一次割付区域２８０ｄは、矢印２７３ｅ、２７２ｅ及び点線の矢印２７２ｆで多層区分割付表３１０の割付状態との対応を示すように、区分番号が８で空の区域２８３ｃと区分番号が２０で空の区域２８２ｃ、及び区分番号が２１で使用中の区域２８２ｄに区分される。
【０１６５】
図１５は、図１４ＡのステップＳ１４０５の処理の詳細を説明するものであり、割付構成区分表により、割付区域内の分割割付状況を求めて分割割付状況スタックにプッシュする処理フロー例を説明する図である。
【０１６６】
まず、ステップＳ１５０１で、区分レベルに、図１２に示すステップＳ１２０４で設定した解放区分レベルを設定し、次にステップＳ１５０１ａにおいて、先頭番号管理表より、区分レベルの指す先頭番号を取り出し、ステップＳ１５０１ｂで、レベル内番号に、区分番号から該読み出した管理情報の先頭番号を減じた値を設定してステップＳ１５０２に進む。
【０１６７】
ステップＳ１５０２では、割付構成区分表より区分レベルの指すビット値を解放表示として取り出す。ビット値が１であれば解放表示ありとし、ビット値が０であれば解放表示なしとする。
そして、ステップＳ１５０２ａにおいて、割付区域内の分割割付状況として、区分レベル、区分番号、解放表示を分割割付状況スタックにプッシュする。
【０１６８】
次にステップＳ１５０４に進み、区分レベルは最小区分レベルに等しいか判定する。区分レベルが最小区分レベルよりも大きいと判定されると、ステップＳ１５０４ａに分岐して解放表示はありか判定し、解放表示がありでなければステップＳ１５０６に進み、解放表示がありであれば、ステップＳ１５０５で、レベル内番号に１を加えてステップＳ１５０６に進む。
ステップＳ１５０６では、レベル内番号を２倍にし、ステップＳ１５０７で区分レベルを１つ減らす。さらに、ステップＳ１５０７ａで、先頭番号管理表より、区分レベルの指す先頭番号を取り出し、ステップＳ１５０７ｂで、区分番号に、先頭番号にレベル内番号を加えた値を設定してステップＳ１５０２に戻る。
【０１６９】
上述のステップＳ１５０２〜ステップＳ１５０７ｂのループ処理を、ステップＳ１５０４において区分レベルが最小区分レベルと等しいと判定されるまで繰り返す。ステップＳ１５０４において区分レベルが最小区分レベルと等しいと判定されると、処理を終了する。
【０１７０】
図１４Ｂの例示では、区分番号に３、区分レベルに４、レベル内番号には２が初期設定されており、割付構成区分表の区分レベル４の指すビット値は０であるから、最初に分割割付状況スタックにプッシュされる区分レベル、区分番号、解放表示は、それぞれ４、３、０（解放表示なし）である。
【０１７１】
区分レベル４の処理では、解放表示はなしなので、レベル内番号は２×２＝４に更新される。区分レベルは３に更新されて、区分番号は、区分レベル３の指す先頭番号管理表の先頭番号“４”とレベル内番号“４”の和である“８”に更新される。また、割付構成区分表の区分レベル３の指すビット値は１である。したがって、分割割付状況スタックには、区分レベル、区分番号、解放表示として、それぞれ、３、８、１（解放表示あり）がプッシュされる。
【０１７２】
区分レベル３の処理では、解放表示はありなのでレベル内番号は（４＋１）×２＝１０に更新される。区分レベルは２に更新されて、区分番号は、区分レベル２の指す先頭番号管理表の先頭番号“１０”とレベル内番号“１０”の和である“２０”に更新される。また、割付構成区分表の区分レベル２の指すビット値は０である。したがって、分割割付状況スタックには、区分レベル、区分番号、解放表示として、それぞれ、２、２０、０（解放表示なし）がプッシュされる。
【０１７３】
区分レベル２の処理では、解放表示はなしなのでレベル内番号は１０×２＝２０に更新される。区分レベルは最小区分レベルである１に更新されて、区分番号は、区分レベル１の指す先頭番号管理表の先頭番号“２３”とレベル内番号“２０”の和である“４３”に更新される。また、割付構成区分表の区分レベル１の指すビット値は１である。したがって、分割割付状況スタックには、区分レベル、区分番号、解放表示として、それぞれ、１、４３、１（解放表示あり）がプッシュされる。
【０１７４】
図１４Ｂに示す例は、マルチビット要求で割り付けられた領域を解放するものである。シングルビット要求で割り付けられた領域を解放するのであれば、解放区分レベルと最小区分レベルは等しく、分割割付状況スタックにプッシュされる区分レベル、区分番号、解放表示は１組だけであり、解放表示はありである。
【０１７５】
上述の分割割付状況スタックにプッシュされた分割割付状況としての区分レベル、区分番号、解放表示と、図１２のステップＳ１２０５で空に初期設定され、後記図１６に示す処理により更新される連結要求により、図１４Ｂに例示する割付区域の解放が行われる。
【０１７６】
図１６は、図１４ＡのステップＳ１４１３の処理の詳細を説明するものであり、区分番号の指す区分対の解放を試みる処理フロー例を説明する図である。図１４Ａに示す処理フローのとおり、図１６に示す処理ステップは、分割割付状況スタックを順次ポップすることにより、最小区分レベルから解放区分レベルの１つ下位の区分レベルまでの区分レベル毎に実行される。
【０１７７】
図に示すとおり、まずステップＳ１６０２で、対の区分番号に、区分番号に値１を加算した値を設定してステップＳ１６０４に進み、対の区分番号の指す多層区分割付表の割付状態を読み出し、ステップＳ１６０５で、読み出した割付状態が空または空候補であるか判定する。読み出した割付状態が空または空候補であれば、ステップＳ１６０６に進み、読み出した割付状態が空でも空候補でもなければ、ステップＳ１６０９に分岐する。
【０１７８】
ステップＳ１６０６では、区分番号の指す多層区分割付表の割付状態に保留を設定し、ステップＳ１６０７で、対の区分番号の指す多層区分割付表の割付状態に保留を設定する。次にステップＳ１６０８で連結要求にありを設定して処理を終了する。これらのステップＳ１６０６〜Ｓ２６０８の処理は、図１４Ｂの例示では、矢印２４１ｃで示す連結要求ありの処理に対応する。
【０１７９】
一方、ステップＳ１６０９に分岐した場合は、区分番号の指す多層区分割付表の割付状態に空を設定し、ステップＳ１６１０で、連結要求になしを設定して処理を終了する。この処理は、図１４Ｂの例示では、矢印２４２ｃ、２４３ｃで示す自区域のみ解放の処理に対応する。
【０１８０】
次に図１７Ａ、図１７Ｂ及び図１７Ｃを参照して、図１２のステップＳ１２０８の処理の詳細を説明する。
図１７Ａは、一次割付区域と、隣接する空区域とを連結して上位の区域の割付状態を空とすることを試みる処理フロー例を説明する図である。
【０１８１】
図に示すように、ステップＳ１７０１で、区分レベルに解放区分レベルを設定し、ステップＳ１７０２に進む。
ステップＳ１７０２では、先頭番号管理表より、区分レベルの指す先頭番号を取り出し、ステップＳ１７０３ａにおいて、区分番号に、取り出した先頭番号にレベル内番号を加えた値を設定してステップＳ１７０３ｂに進む。ステップＳ１７０３ａの最初の処理、すなわち解放区分レベルでの処理では、レベル内番号は、図１４Ａに示すステップＳ１４０５の処理の詳細を示す図１５の処理フローのステップＳ１５０１ｂにより設定されている。
【０１８２】
ステップＳ１７０３ｂでは、主区分番号管理表より、区分レベルの指す主区分番号を取り出し、ステップＳ１７０５に進む。
ステップＳ１７０５では、区分番号と主区分番号が等しいか判定する。等しければステップＳ１７１０に分岐し、等しくなければステップＳ１７０６に進む。
ステップＳ１７０６では、区分番号の指す区分対の解放を試みる。ステップＳ１７０６の処理の詳細は、後に図１７Ｃを参照して説明する。
【０１８３】
次にステップＳ１７０７に進み、連結要求はありか判定する。連結要求がありでなければ、図１６のステップＳ１６０５において、対の区分番号の割付状態は空でも空候補でもないと判定されたことを意味するから、区域の連結処理を終了し、連結要求がありであれば、ステップＳ１７０８以降の処理に分岐して上位の区分レベルの区域の連結処理を試みる。
ステップＳ１７０８では、区分レベルを１つ上位のものとし、ステップＳ１７０９に進んで、レベル内番号に、レベル内番号を値２で割った商を設定してステップＳ１７０２に戻る。
【０１８４】
ステップＳ１７０５で、区分番号と主区分番号が等しいと判定された場合に分岐するステップＳ１７１０では、区分番号の指す多層区分割付表の割付状態を空に設定して処理を終了する。区分番号と主区分番号が等しい場合は、図３の例示から明らかなようにその区分番号と対をなす区分番号の区域は存在しないことから、ステップＳ１７１０では、区分番号の指す多層区分割付表の割付状態を空に設定して処理を終了する。
【０１８５】
図１７Ｂは、図３に示す多層区分割付表３１０を参照して、図１７Ａ及び後記図１７Ｃに示す一次割付区域と、隣接する空区域とを連結して上位の区域の割付状態を空とすることを試みる処理を、具体例により、説明する図である。なお、以下の説明では、一次割付区域と、隣接する空区域とを連結して上位の区域の割付状態を空とすることを、単に、連結ということがある。
【０１８６】
図１７Ｂに示す例は、図８Ｂに例示するものと同様なシングルビット要求で一次割付された区域が解放されたので隣接区域と連結して上位区分レベルの区域の割付状態に空を設定するものである。
図１７Ｂには、解放された一次割付区域を連結する前の割付状態の多層区域として、図８Ｂに示す一次割付後の仮割付区域２８０ｂの使用中であった区分番号３１の区域が解放され、空であった区分番号７の区域２８３ｂが使用中となっている多層区域２８０ｅが例示されている。区分番号３２の区域２８１ｂと区分番号１５の区域２８２ｂの割付状態は空のままである。
【０１８７】
連結処理は、解放区分レベルである区分レベル１から、連結処理がそれ以上不可能になる上位の区分レベルへと順次行われていく。すなわち、解放された区分番号３１の区域２８１ａに順次隣接した区域であって使用中でない区域を連結していく。
【０１８８】
まず、図１２に示すステップＳ１２０７の判定が肯定的であったことから、解放された区域２８１ａに対して、矢印２４０ｅに示す連結要求が行われ、解放区分レベルである区分レベル１の処理が行われる。符号１６１ｅを付した区分レベル１の区分割付表の、区分番号１７１の値が３１でレベル内番号１７２の値が８の区域と対をなす区分番号３２の区域の割付状態が空であることから、区分番号３１の区域と区分番号３２の区域からなる区分対２９１ｄの上位の区分レベルの区域の割付状態に空を設定する連結要求（矢印２４１ｅに示す）がありとされ、符号１６１ｆを付した区分レベル１の区分割付表に示すように、区分番号３１及び対の区分番号３２の割付状態には保留が設定される。図１４Ｂの説明においても述べたように、上位区分レベルの区域の空が設定されるとき、その区域に包含される下位の区分レベルの区域の割付状態に保留を設定することは、図３に示す多層区分割付表３１０の初期設定の場合と同様である。
【０１８９】
区分レベル２においては、連結要求がありなので矢印２４１ｆに示すように上位の区分の区域である、符号１６２ｅを付した連結前の区分レベル２の区分割付表の区分番号１４の区域の解放要求がされる。区分番号１４の区域と区分対２９２ｄを構成する区分番号１５の区域は空なので、矢印２４２ｅで示すように連結要求がありとされ、符号１６２ｆを付した連結後の区分レベル２の区分割付表に示すように、区分番号１４及び対の区分番号１５の割付状態には保留が設定される。
【０１９０】
次に区分レベル３においては、連結要求がありなので矢印２４２ｆに示すように上位の区分の区域である、符号１６３ｅを付した連結前の区分レベル２の区分割付表の区分番号６の区域の解放要求がされる。区分番号６の区域と区分対２９３ｄを構成する区分番号７の区域は使用中なので、矢印２４３ｅで示すように区分番号６の区域の割付状態のみが空に設定され、区分対２９３ｄの割付状態は、符号１６３ｆを付した連結後の区分レベル３の区分割付表に示す空と使用中となる。
そして、連結要求はなしであるので、点線の矢印２４３ｆで示すように、上位の区域であり、区分レベル４の区分割付表１６４に示すように割付状態が使用中である区分番号２の区域は解放されずに割付状態は使用中のままである。
【０１９１】
以上の区域の解放と連結の処理により、一次割付区域を隣接する空区域と連結した後の割付状態の多層区域２８０ｆは、矢印２７３ｅ及び点線の矢印２７２ｆで多層区分割付表３１０の割付状態との対応を示すように、区分番号が６で空の区域２８３ｅ及び区分番号が７で使用中の区域２８３ｆに区分される。
【０１９２】
図１７Ｃは、図１７ＡのステップＳ１７０６の処理の詳細を説明するものであり、区分番号の指す区分対の解放を試みる処理フロー例を説明する図である。ここで、区分番号の指す区分対とは、区分番号で識別される区分ユニットの属する区分対という意味であり、後ほど説明するように、その区分番号は若番の方とは限らない。別の言い方をすれば、その区分番号に対応するレベル内番号が偶数とは限らない。
図１７Ａに示す処理フローのとおり、図１７Ｃに示す処理ステップは解放区分レベルから上位の区分レベルの方向に区分レベル毎に実行され、空領域を連結して上位の区分レベルの領域の解放が試みられる。
【０１９３】
図に示すとおり、まずステップＳ１７１１で、レベル内番号は偶数かを判定する。図１７Ｃに示す処理フローは、図１６に示すものと類似するものであるが、先に述べたように、図１７Ａ、つまり図１２のステップＳ１２０８の処理においては、レベル内番号が偶数とは限らない。それは、解放され、空状態となった一次割付区域に対応するレベル内番号は、偶数の場合もあれば、奇数の場合もあるからである。図１７Ｂに示す例では８が設定されているが、図１７Ｂに示す使用中の割付区分番号が７の区域２８３ｆが空となったときには、そのレベル内番号は３であり、奇数である。
【０１９４】
レベル内番号が偶数である場合はステップＳ１７１２で、対の区分番号に、区分番号に値１を加算した値を設定してステップＳ１７１４に進み、奇数である場合はステップＳ１７１３で、対の区分番号に、区分番号から１を減じた値を設定してステップＳ１７１４に進む。
【０１９５】
ステップＳ１７１４では、対の区分番号の指す多層区分割付表の割付状態を読み出し、ステップＳ１７１５で、読み出した割付状態が空または空候補であるか判定する。読み出した割付状態が空または空候補であれば、ステップＳ１７１６に進み、読み出した割付状態が空でも空候補でもなければ、ステップＳ１７１９に分岐する。
【０１９６】
ステップＳ１７１６では、区分番号の指す多層区分割付表の割付状態を保留に設定し、ステップＳ１７１７で、対の区分番号の指す多層区分割付表の割付状態に保留を設定する。次にステップＳ１７１８で区分対の状態表示を空に設定して処理を終了する。これらのステップＳ１７１６〜Ｓ１７１８の処理は、図１７Ｂの例示では、矢印２４１ｅ、２４２ｅで示す連結要求の処理に対応する。
【０１９７】
一方、ステップＳ１７１９に分岐した場合は、区分番号の指す多層区分割付表の割付状態を空に設定し、ステップＳ１７２０で、連結要求になしを設定して処理を終了する。こちらの処理は、図１７Ｂの例示では、矢印２４３ｅで示す自区域のみ解放の処理に対応する。
【０１９８】
なお、本発明の区画管理方法を例えば図２Ｃに例示するデータ処理装置３０１のようなコンピュータに実行させるプログラムにより、本発明に係る区画管理装置をコンピュータ上に構築可能なことは明らかである。
そこで、本発明の区画管理装置に関する、機能ブロック構成例について以下に説明する。
【０１９９】
図１８Ａは、本発明の一実施形態における区画管理装置の機能ブロック構成例を説明する図である。
図に示すように、区画管理装置８００は、大きく分けて、初期化部８１０と多層区分管理部８４０から構成される。初期化部８１０と多層区分管理部８４０は、図２Ｂに例示するアロケーションシステム（初期化部）１０１とアロケーションシステム（多層区分管理部）１０２に相当する。
【０２００】
初期化部８１０は、区画のサイズを取得する区画サイズ取得手段８２０と多層区分割付表生成手段８３０を含む。多層区分割付表生成手段８３０は、区画のサイズを互いに異なる２のべき乗の和と区画の割当単位のサイズの積で表したとき、該和を構成する各２のべき乗と区画の割当単位のサイズとの積のサイズの主区域により、そのサイズの大きさ順に区画を分割することで該区画を区分けし、各主区域を２分の１ずつ分割して順次区画の割当単位のサイズまで各サイズの区域に区分けし、主区域を含む各区域に対応して該各区域のそれぞれの割付状態を示す割付情報を格納する多層区分割付表を生成し、初期化する。この多層区分割付表生成手段８３０の機能は、図４Ａ〜図４Ｃを参照して説明した処理フロー例により実現可能である。
【０２０１】
多層区分管理部８４０は、ファイルまたはメモリ領域の空区域への割付を行う区域割付手段８５０とファイルまたはメモリ領域の割付から割付区域を解放する区域解放手段８６０を含む。
【０２０２】
図１８Ｂは、本発明の一実施形態における区域割付手段の機能ブロック構成例を説明する図である。図に示すように、区域割付手段８５０は、割付要求を受け付ける割付要求受付手段８５１、空区域探索手段８５２、二次割付手段８５３、割付区分番号出力手段を含み、空区域探索手段８５２は、仮割付手段８５７を含む。
【０２０３】
区域割付手段８５０の機能は、図５を参照して説明した処理フロー例により実現可能である。
空区域探索手段８５２は、割付要求に含まれるサイズである割付要求サイズが、互いに異なる２のべき乗の和と区画の割当単位のサイズの積で表され、区分レベルの異なる区域のサイズの和である場合、その区分レベルの最大のものより１つ大きい区分レベルの空区域であって割付要求サイズより大きいサイズの一次割付区域を探索し、割付要求に含まれるサイズである割付要求サイズが２のべき乗と前記区画の割当単位のサイズの積で表される場合、その割付要求サイズの空区域を一次割付区域として探索する。空区域探索手段８５２の機能は、図６、図９に例示する処理フローに対応する。
【０２０４】
空区域探索手段８５２のうち仮割付手段８５７は、一次割付区域の区分レベルで空区域を探索できなかった場合に、多層区分割付表の上位の区分レベルの区域に対応する割付状態を参照して上位の区分レベルの空区域を探索して該区域を仮割付区域として前記多層区分割付表の割付状態を使用中とするとともに、仮割付区域を一次割付区域と残りの領域であって区分レベルの小さいものから順に区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、一次割付区域内の区域に対応する多層区分割付表の割付状態に使用中を設定し、隣接多層区域を構成する区域に対応する多層区分割付表の割付状態に空状態を設定する。仮割付手段８５７の機能は、図７Ａと図８Ａ、図１０Ａと図１０Ｂに例示する処理フローに対応する。
【０２０５】
二次割付手段８５３は、一次割付区域のサイズが割付要求サイズより大きい場合、一次割付区域を、区分レベルの大きいものから順に区分レベルの異なる区域が連続して割り付けられた領域である二次割付区域と、残りの領域であって区分レベルの小さいものから順に区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、二次割付区域のそれぞれの区域に対応する多層区分割付表の割付状態に使用中を設定し、隣接多層区域を構成する区域に対応する前記多層区分割付表の割付状態に空候補状態を設定する。二次割付手段８５３の機能は、図１１Ａ、図１１Ｂに例示する処理フローに対応する。
【０２０６】
図１８Ｃは、本発明の一実施形態における区域解放手段の機能ブロック構成例を説明する図である。図に示すように、区域解放手段８６０は、解放要求を受け付ける解放要求受付手段８５１、一次割付区域内の区域の解放を試みる一次割付区域内解放手段８６２、一次割付区域の区分レベルより大きい区分レベルの区域の解放を試みる上位区域解放手段８６３を含む。
【０２０７】
区域解放手段８６０の機能は図１２に例示する処理フロー例に対応する。
一次割付区域内解放手段８６２は、解放要求に含まれるサイズである解放要求サイズが、区分レベルの異なる区域の和である場合、隣接多層区域内の最小の区域の区分番号を求めてその区分番号の指す多層区分割付表から割付状態を読み出し、読み出した割付状態が空または空候補の状態であれば、二次割付区域内の最小の区域と隣接多層区域内の最小の区域に対応する多層区分割付表の割付状態に保留を設定するとともに１つ上位の区分レベルの区域の解放を試み、隣接多層区域内の最小の区域の割付状態が使用中であれば、二次割付区域内の最小の区域の割付状態を空の状態とする。一次割付区域内解放手段８６２の機能は、図１４Ａに例示する処理フローに対応する。
【０２０８】
上位区域解放手段８６３は、一次割付区域が解放され、その区分番号の指す多層区分割付表の割付状態が空の状態になったとき、一次割付区域と同一の区分レベルであって、１つ上位の区分レベルの区域を２つに分割したときの一方の区域を一次割付区域としたときの他方の区域の割付状態を多層区分割付表より読み出し、他方の区域の割付状態が空または空候補の状態であれば、前記一方の区域と他方の区域に対応する多層区分割付表の割付状態に保留を設定するとともに上位の区分レベルの区域の解放を試み、他方の区域の割付状態が使用中であれば、一方の区域の割付状態を空の状態とする。上位区域解放手段８６３の機能は、図１７Ａに例示する処理フローに対応する。
【０２０９】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施形態は上記に限ることなく種々の変形が可能であることは当業者に明らかである。以上説明したように、本発明によれば、記憶容量によらず記憶装置を有効にかつ効率的に管理することができる。また、各区分レベルの区域を多層区分割付表及び多層区分管理表を用いて多層的に管理することにより、連続する領域にファイル割付を行うことが可能となる。
【符号の説明】
【０２１０】
１００    アロケーションシステム
１１４    主区分番号
１１５    区分数
１１６    先頭番号
１２０    区画サイズ
１３０    区画構成主区分表
１７０    割付状態
１７１    区分番号
１７２    レベル内番号
２００    アプリケーションプログラム／ＯＳ
２０１    初期化プログラム
２０２    ファイルシステム
２０３    ファイル操作システム
２２０    割付要求サイズ
２３０    割付構成区分表
３０１    データ処理装置
３０２    中央処理装置
３０３    キャッシュメモリ
３０４    バス
３０５    主記憶装置
３０６    外部記憶装置
３０７    通信装置
３０８    データ格納装置
３０９    多層区分管理表
３０９ａ  主区分番号管理表
３０９ｂ  先頭番号管理表
３１０    多層区分割付表
３１１    区画
６００    割付ビットマップ
６９０    区画
７９０    ツリー構造体群
８００    区画管理装置
８１０    初期化部
８２０    区画サイズ取得手段
８３０    多層区分割付表生成手段
８４０    多層区分管理部
８５０    区域割付手段
８５１    割付要求受付手段
８５２    空区域探索手段
８５３    二次割付手段
８５４    割付区分番号出力手段
８５７    仮割付手段
８６０    区域解放手段
８６１    解放要求受付手段
８６２    一次割付区域内解放手段
８６３    上位区域解放手段
【図１Ａ】
2010287066.tif 000003
【図１Ｂ】
2010287066.tif 000004
【図２Ａ】
2010287066.tif 000005
【図２Ｂ】
2010287066.tif 000006
【図２Ｃ】
2010287066.tif 000007
【図３】
2010287066.tif 000008
【図４Ａ】
2010287066.tif 000009
【図４Ｂ】
2010287066.tif 000010
【図４Ｃ】
2010287066.tif 000011
【図５】
2010287066.tif 000012
【図６】
2010287066.tif 000013
【図７Ａ】
2010287066.tif 000014
【図７Ｂ】
2010287066.tif 000015
【図７Ｃ】
2010287066.tif 000016
【図７Ｄ】
2010287066.tif 000017
【図８Ａ】
2010287066.tif 000018
【図８Ｂ】
2010287066.tif 000019
【図９】
2010287066.tif 000020
【図１０Ａ】
2010287066.tif 000021
【図１０Ｂ】
2010287066.tif 000022
【図１１Ａ】
2010287066.tif 000023
【図１１Ｂ】
2010287066.tif 000024
【図１１Ｃ】
2010287066.tif 000025
【図１２】
2010287066.tif 000026
【図１３】
2010287066.tif 000027
【図１４Ａ】
2010287066.tif 000028
【図１４Ｂ】
2010287066.tif 000029
【図１５】
2010287066.tif 000030
【図１６】
2010287066.tif 000031
【図１７Ａ】
2010287066.tif 000032
【図１７Ｂ】
2010287066.tif 000033
【図１７Ｃ】
2010287066.tif 000034
【図１８Ａ】
2010287066.tif 000035
【図１８Ｂ】
2010287066.tif 000036
【図１８Ｃ】
2010287066.tif 000037