【手続補正書】
【提出日】平成23年6月27日(2011.6.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
記憶装置の区画管理装置において、
区画のサイズを取得する区画サイズ取得手段と、
該区画のサイズを互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表したとき、該和を構成する各２のべき乗と前記区画の割当単位のサイズとの積のサイズの主区域により、そのサイズの順に前記区画を分割することで該区画を区分けし、前記各主区域を２分の１ずつ分割して順次前記区画の割当単位のサイズまで各サイズの区域に区分けし、前記主区域を含む各区域に対応して該各区域のそれぞれの割付状態を示す割付情報を格納する多層区分割付表を生成し、初期化する多層区分割付表生成手段と、
を含む初期化部と、
前記多層区分割付表に格納された前記割付情報に基づいて前記各区域の割付を管理する多層区分管理部と、
を備えることを特徴とする区画管理装置。
【請求項２】
請求項１記載の区画管理装置において、
前記区域のサイズを規定する２のべき乗のべき数を該区域の区分レベルとすると、
前記多層区分割付表は、前記区域の割付情報を、前記区域の区分レベル順、同一区分レベルにおいては前記区域の前記区画内の配置順で格納し、
前記多層区分管理部は、前記割付情報の格納順にしたがって前記割付情報が該当する区域を識別するための識別番号である区分番号を割り振り、該区分番号を用いて前記区域の割付を管理する、
ことを特徴とする区画管理装置。
【請求項３】
請求項２記載の区画管理装置において、
前記多層区分割付表生成手段は、前記主区域の割付情報の初期値として空きであることを示す空き状態を設定し、前記主区域を分割して得られる区域の割付情報の初期値として該区域への割付を行わないことを示す空以外の状態を設定する
ことを特徴とする区画管理装置。
【請求項４】
請求項３記載の区画管理装置において、
前記多層区分管理部は、
サイズを含むファイルあるいはメモリ領域の割付要求を受け付ける割付要求受付手段と、
前記多層区分管理表を参照して、前記割付要求に含まれるサイズである割付要求サイズが、互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表され、前記区分レベルの異なる区域のサイズの和である場合、該区分レベルの最大のものより１つ大きい区分レベルの空区域であって前記割付要求サイズより大きいサイズの一次割付区域を探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とし、前記割付要求に含まれるサイズである割付要求サイズが２のべき乗と前記区画の割当単位のサイズの積で表される場合、該割付要求サイズの空区域を一次割付区域として探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とする空区域探索手段と、
前記一次割付区域のサイズが前記割付要求サイズより大きい場合、該一次割付区域を、前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である二次割付区域と、残りの領域であって前記二次割付区域の区分レベルの異なる区域が割り付けられる区分レベルの順とは逆順で区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記二次割付区域のそれぞれの区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空候補状態を設定する二次割付手段と、
前記割付区分番号を前記ファイルあるいはメモリ領域の割付要求の割り付け結果の１つとして出力する割付区分番号出力手段と、
を備え、
前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域の区分レベルは等しく、前記多層区分割付表において前記区分レベルより１つ上位の区分レベルの区域を２分割したものであることを特徴とする区画管理装置。
【請求項５】
請求項４記載の区画管理装置において、
前記空区域探索手段は、前記一次割付区域の区分レベルで空区域を探索できなかった場合に、前記多層区分割付表の上位の区分レベルの区域に対応する割付状態を参照して上位の区分レベルの空区域を探索して該区域の区分番号を求め、該区分番号の区域である仮割付区域を、前記一次割付区域と残りの領域であって前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記一次割付区域内の区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空状態を設定する仮割付手段を含むことを特徴とする区画管理装置。
【請求項６】
請求項５記載の区画管理装置において、
前記空区域探索手段は、割付要求されたファイルあるいはメモリ領域を割付可能な空状態の区域を探索できなかった場合、前記多層区分割付表から空候補状態の区域を探索することを特徴とする区画管理装置。
【請求項７】
請求項６記載の区画管理装置において、
前記多層区分管理部は、
サイズ及び割付区分番号を含むファイルあるいはメモリ領域の解放要求を受け付ける解放要求受付手段と、
前記解放要求に含まれるサイズである解放要求サイズが、前記区分レベルの異なる区域の和である場合、前記隣接多層区域内の最小の区域の区分番号を求めて該区分番号の指す前記多層区分割付表から割付状態を読み出し、該読み出した割付状態が空または空候補の状態であれば、前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記１つ上位の区分レベルの区域の解放を試み、前記隣接多層区域内の最小の区域の割付状態が使用中であれば、前記二次割付区域内の最小の区域の割付状態を空の状態とする一次割付区域内解放手段と
前記一次割付区域が解放され、その区分番号の指す前記多層区分割付表の割付状態が空の状態になったとき、該一次割付区域と同一の区分レベルであって、１つ上位の区分レベルの区域を２つに分割したときの一方の区域を前記一次割付区域としたときの他方の区域の割付状態を前記多層区分割付表より読み出し、該他方の区域の割付状態が空または空候補の状態であれば、前記一方の区域と他方の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記上位の区分レベルの区域の解放を試み、前記他方の区域の割付状態が使用中であれば、前記一方の区域の割付状態を空の状態とする上位区域解放手段と、
を備えることを特徴とする区画管理装置。
【請求項８】
コンピュータが実行する記憶装置の区画管理方法において、
区画のサイズを取得する区画サイズ取得ステップと、
該区画のサイズを互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表したとき、該和を構成する各２のべき乗と前記区画の割当単位のサイズとの積のサイズの主区域により、そのサイズの順に前記区画を分割することで該区画を区分けする主区分ステップと、
前記各主区域を２分の１ずつ分割して順次前記区画の割当単位のサイズまで各サイズの区域に区分けし、前記主区域を含む各区域に対応して該各区域のそれぞれの割付状態を示す割付情報を格納する多層区分割付表を生成する多層区分割付表生成ステップと、
前記多層区分割付表に格納された前記割付情報に基づいて前記各区域の割付を管理する多層区分管理ステップと、
を実行することを特徴とする区画管理方法。
【請求項９】
請求項８記載の区画管理方法において、
前記区域のサイズを規定する２のべき乗のべき数を該区域の区分レベルとすると、
前記多層区分割付表は、前記区域の割付情報を、前記区域の区分レベル順、同一区分レベルにおいては前記区域の前記区画内の配置順で格納するものであり、
前記多層区分管理ステップは、前記割付情報の格納順にしたがって前記割付情報が該当する区域を識別するための識別番号である区分番号を割り振り、該区分番号を用いて前記区域の割付を管理する、
ことを特徴とする区画管理方法。
【請求項１０】
請求項９記載の区画管理方法において、
前記多層区分割付表生成ステップは、主区域の割付情報の初期値として空きであることを示す空き状態を設定し、前記主区域を分割して得られる区域の割付情報の初期値として該区域への割付を行わないことを示す空以外の状態を設定する、
ことを特徴とする区画管理方法。
【請求項１１】
請求項１０記載の区画管理方法において、
前記多層区分管理ステップは、
サイズを含むファイルあるいはメモリ領域の割付要求を受け付ける割付要求受付ステップと、
前記多層区分管理表を参照して、前記割付要求に含まれるサイズである割付要求サイズが、互いに異なる２のべき乗の和と前記区画の割当単位のサイズの積で表され、前記区分レベルの異なる区域のサイズの和である場合、該区分レベルの最大のものより１つ大きい区分レベルの空区域であって前記割付要求サイズより大きいサイズの一次割付区域を探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とし、前記割付要求に含まれるサイズである割付要求サイズが２のべき乗と前記区画の割当単位のサイズの積で表される場合、該割付要求サイズの空区域を一次割付区域として探索し、該一次割付区域に対応する区分番号を求めて割付区分番号とする空区域探索ステップと、
前記一次割付区域のサイズが前記割付要求サイズより大きい場合、該一次割付区域を、前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である二次割付区域と、残りの領域であって前記二次割付区域の区分レベルの異なる区域が割り付けられる区分レベルの順とは逆順で区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記二次割付区域のそれぞれの区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空候補状態を設定する二次割付ステップと、
前記割付区分番号を前記ファイルあるいはメモリ領域の割付要求の割り付け結果の１つとして出力する割付区分番号出力ステップと、
を備え、
前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域の区分レベルは等しく、前記多層区分割付表において前記区分レベルより１つ上位の区分レベルの区域を２分割したものであることを特徴とする区画管理方法。
【請求項１２】
請求項１１記載の区画管理方法において、
前記空区域探索ステップは、前記一次割付区域の区分レベルで空区域を探索できなかった場合に、前記多層区分割付表の上位の区分レベルの区域に対応する割付状態を参照して上位の区分レベルの空区域を探索して該区域の区分番号を求め、該区分番号の区域である仮割付区域を、前記一次割付区域と残りの領域であって前記区分レベルの順に区分レベルの異なる区域が連続して割り付けられた領域である隣接多層区域とに分割し、前記一次割付区域内の区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に使用中を設定し、前記隣接多層区域を構成する区域に対応する区分番号を求めて該区分番号の対応する前記多層区分割付表の割付状態に空状態を設定する仮割付ステップを含むことを特徴とする区画管理方法。
【請求項１３】
請求項１２記載の区画管理方法において、
前記空区域探索ステップは、割付要求されたファイルあるいはメモリ領域を割付可能な空状態の区域を探索できなかった場合、前記多層区分割付表から空候補状態の区域を探索することを特徴とする区画管理方法。
【請求項１４】
請求項１３記載の区画管理方法において、
前記多層区分管理ステップは、
サイズ及び割付区分番号を含むファイルあるいはメモリ領域の解放要求を受け付ける解放要求受付ステップと、
前記解放要求に含まれるサイズである解放要求サイズが、前記区分レベルの異なる区域の和である場合、前記隣接多層区域内の最小の区域の区分番号を求めて該区分番号の指す前記多層区分割付表から割付状態を読み出し、該読み出した割付状態が空または空候補の状態であれば、前記二次割付区域内の最小の区域と隣接多層区域内の最小の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記１つ上位の区分レベルの区域の解放を試み、前記隣接多層区域内の最小の区域の割付状態が使用中であれば、前記二次割付区域内の最小の区域の割付状態を空の状態とする一次割付区域内解放ステップと
前記一次割付区域が解放され、その区分番号の指す前記多層区分割付表の割付状態が空の状態になったとき、該一次割付区域と同一の区分レベルであって、１つ上位の区分レベルの区域を２つに分割したときの一方の区域を前記一次割付区域としたときの他方の区域の割付状態を前記多層区分割付表より読み出し、該他方の区域の割付状態が空または空候補の状態であれば、前記一方の区域と他方の区域に対応する前記多層区分割付表の割付状態に空または空候補以外の状態を設定するとともに前記上位の区分レベルの区域の解放を試み、前記他方の区域の割付状態が使用中であれば、前記一方の区域の割付状態を空の状態とする上位区域解放ステップと、
を含むことを特徴とする区画管理方法。
【請求項１５】
請求項８乃至請求項１４記載のいずれか１項に記載の区画管理方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１６】
請求項８乃至請求項１４記載のいずれか１項に記載の区画管理方法をコンピュータに実行させるプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１７】
請求項８乃至請求項１４記載のいずれか１項に記載の区画管理方法により前記区画が管理されていることを特徴とする記憶装置。
【請求項１８】
請求項８乃至請求項１４記載のいずれか１項に記載の区画管理方法であって、前記記憶装置は記憶媒体駆動装置と記憶媒体とを含むものであり、前記記憶装置の前記区画は前記記憶媒体の区画である区画管理方法により前記区画が管理されていることを特徴とする記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
図１Ｂは、バディシステムの割付原理を説明する図である。図１Ｂに示すのは、サイズが２３＝８の割当領域４９０とそれに対応するツリー構造体５８０と、ツリー構造体５８０のノードに対応する領域が使用中であるかを示すビットマップ４００である。割当領域４９０は、例えば図１Ａに例示した区画１〜４等である。
ツリー構造体５８０は、割当領域４９０を２分の１のサイズに順次割当単位のサイズまで分割して得られる領域の関係を階層的にモデル化したものである。割当単位のサイズの領域の階層をレベル１とすると、図に示す例では、ルートノードのレベルは４となる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
最初に、あらためて区画の定義を行う。本発明において「区画」とは、図１Ａを参照して説明したように、予め割り当てられた領域であり、最初に割り当てられる領域である。本発明においては、区画は取得済みであることを前提とする。区画は、本発明においては、記憶領域を要求する要求元に対して割り当てられた物理的あるいは論理的な領域であり、要求元及び割付を実行する主体にはファイルシステムであるとかディスクアロケータであるというような制限はない。また、本発明における区画は、外部記憶装置の記憶領域に限らず、例えば後に図２Ｃを参照して説明するデータ格納装置３０８に含まれる各種記憶装置の予め割り当てられた領域とすることができる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
ノード６２０の下位には、リンク７１０で接続されたサイズ１のノード６１０と、リンク７１１で接続されたサイズ１のノード６１１が存在する。同様に、ノード６２１の下位には、リンク７１２で接続されたサイズ１のノード６１２と、リンク７１３で接続されたサイズ１のノード６１３が存在し、ノード６２２の下位には、リンク７１４で接続されたサイズ１のノード６１４と、リンク７１５で接続されたサイズ１のノード６１５が存在し、ノード６２３の下位には、リンク７１６で接続されたサイズ１のノード６１６と、リンク７１７で接続されたサイズ１のノード６１７が存在する。これら８つのノードは区分レベル０の区域の区分に対応する。また、これら８つのノードに対応する区分番号は、ルートノードをノード６８０とするツリーにおける１つ上位の区分レベルである区分レベル１のノードに対応する区分番号の末尾の番号に続く、主区分７８２に対応するツリーのルートノードであって区分レベルが１のノードに対応する区分番号の末尾の番号にさらに続く８〜１５である。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
初期化部１０１は、例えばディスクアロケータあるいはファイルシステムの初期化部のような初期化プログラム２０１からの区画サイズを含む初期化要求を受け付け、データ格納装置３０８を構成する、例えば主記憶装置３０５、外部記憶装置３０６、通信装置を介してアクセスする遠方の記憶装置３０７等（以下、単に記憶装置ということがある。）に割り当てられている区画の多層区分管理情報の初期化を行う。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１５８
【補正方法】変更
【補正の内容】
【０１５８】
ステップＳ１４１３では、区分番号の指す区分対の解放を試み、ステップＳ１４０７に戻る。ステップＳ１４１３の処理の詳細は、後に図１６を参照して説明する。
上述のステップ１４０９の判定で区分レベルは解放区分レベルと等しいと判定されて分岐するステップＳ１４１６以降の処理は、解放区分レベルの区域の解放処理である。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１７８
【補正方法】変更
【補正の内容】
【０１７８】
ステップＳ１６０６では、区分番号の指す多層区分割付表の割付状態に保留を設定し、ステップＳ１６０７で、対の区分番号の指す多層区分割付表の割付状態に保留を設定する。次にステップＳ１６０８で連結要求にありを設定して処理を終了する。これらのステップＳ１６０６〜Ｓ１６０８の処理は、図１４Ｂの例示では、矢印２４１ｃで示す連結要求ありの処理に対応する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１９６
【補正方法】変更
【補正の内容】
【０１９６】
ステップＳ１７１６では、区分番号の指す多層区分割付表の割付状態を保留に設定し、ステップＳ１７１７で、対の区分番号の指す多層区分割付表の割付状態に保留を設定する。次にステップＳ１７１８で連結要求にありを設定して処理を終了する。これらのステップＳ１７１６〜Ｓ１７１８の処理は、図１７Ｂの例示では、矢印２４１ｅ、２４２ｅで示す連結要求の処理に対応する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０２０９
【補正方法】変更
【補正の内容】
【０２０９】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施形態は上記に限ることなく種々の変形が可能であることは当業者に明らかである。また、以上に説明した本発明の実施の形態による区画管理方法、更にその均等物は、それらをコンピュータに実行させるプログラムにより実現可能であることも明らかである。したがって、上記プログラム、及び上記プログラムを記憶したコンピュータ読み取り可能な記憶媒体も、本発明の実施の形態に含まれる。
また、本発明の実施の形態による区画管理方法の各処理の実行手段は、上記プログラムにより、コンピュータ上に実現されることも明らかである。したがって、上記プログラムとコンピュータにより、区画管理装置が実現されることも明らかである。
さらに、本発明の区画管理方法によりその区画が管理される記憶装置は、本発明の実施の形態に含まれる。そして、記憶装置が、記憶媒体駆動装置と記憶媒体からなる場合には、本発明の区画管理方法によりその区画が管理される記憶媒体も本発明の実施の形態に含まれる。以上説明したように、本発明によれば、記憶容量によらず記憶装置を有効にかつ効率的に管理することができる。また、各区分レベルの区域を多層区分割付表及び多層区分管理表を用いて多層的に管理することにより、連続する領域にファイル割付を行うことが可能となる。