JPH0546447A - 空き領域検索方法 - Google Patents
空き領域検索方法Info
- Publication number
- JPH0546447A JPH0546447A JP3199085A JP19908591A JPH0546447A JP H0546447 A JPH0546447 A JP H0546447A JP 3199085 A JP3199085 A JP 3199085A JP 19908591 A JP19908591 A JP 19908591A JP H0546447 A JPH0546447 A JP H0546447A
- Authority
- JP
- Japan
- Prior art keywords
- area
- management table
- searched
- management
- search
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0608—Saving storage space on storage systems
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0629—Configuration or reconfiguration of storage systems
- G06F3/0631—Configuration or reconfiguration of storage systems by allocating resources to storage systems
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0673—Single storage device
- G06F3/0674—Disk device
-
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
- G11B27/00—Editing; Indexing; Addressing; Timing or synchronising; Monitoring; Measuring tape travel
- G11B27/10—Indexing; Addressing; Timing or synchronising; Measuring tape travel
- G11B27/19—Indexing; Addressing; Timing or synchronising; Measuring tape travel by using information detectable on the record carrier
- G11B27/28—Indexing; Addressing; Timing or synchronising; Measuring tape travel by using information detectable on the record carrier by using information signals recorded by the same method as the main recording
- G11B27/32—Indexing; Addressing; Timing or synchronising; Measuring tape travel by using information detectable on the record carrier by using information signals recorded by the same method as the main recording on separate auxiliary tracks of the same or an auxiliary record carrier
- G11B27/327—Table of contents
- G11B27/329—Table of contents on a disc [VTOC]
-
- G—PHYSICS
- G11—INFORMATION STORAGE
- G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
- G11B2220/00—Record carriers by type
- G11B2220/20—Disc-shaped record carriers
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Human Computer Interaction (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【目的】スペース効率の低下を招くことなく、記憶装置
の大容量にともなって増加する領域管理テーブル検索オ
ーバヘッドを低減する。 【構成】ディスク１０とディスク上のファイル割当て領
域２０、及びファイル割当て領域２０の使用状況を管理
する管理テーブルとして、前記領域２０を、１ＭＢ単位
に管理する管理テーブル３００と、４ＫＢ単位に管理す
る管理テーブル４００、さらに、管理テーブル３００、
管理テーブル４００を、要求されたファイル容量に応じ
て選択し、必要な空きスペース量検索するスペース検索
プログラム１００により構成される。まず、大管理単位
用テーブル３００で検索し、次に小管理単位用テーブル
４００で検索すると言った階層組合せ検索を実施する。 【効果】記憶装置の容量増加に合わせて、比較的自由
に、大管理単位を設定可能となり、記憶装置の容量増加
に比例して増加する空きスペース検索の為の命令実行オ
ーバヘッドを抑止でき、小容量検索においても、スペー
ス効率の悪化を抑止できる。
の大容量にともなって増加する領域管理テーブル検索オ
ーバヘッドを低減する。 【構成】ディスク１０とディスク上のファイル割当て領
域２０、及びファイル割当て領域２０の使用状況を管理
する管理テーブルとして、前記領域２０を、１ＭＢ単位
に管理する管理テーブル３００と、４ＫＢ単位に管理す
る管理テーブル４００、さらに、管理テーブル３００、
管理テーブル４００を、要求されたファイル容量に応じ
て選択し、必要な空きスペース量検索するスペース検索
プログラム１００により構成される。まず、大管理単位
用テーブル３００で検索し、次に小管理単位用テーブル
４００で検索すると言った階層組合せ検索を実施する。 【効果】記憶装置の容量増加に合わせて、比較的自由
に、大管理単位を設定可能となり、記憶装置の容量増加
に比例して増加する空きスペース検索の為の命令実行オ
ーバヘッドを抑止でき、小容量検索においても、スペー
ス効率の悪化を抑止できる。
Description
【０００１】
【産業上の利用分野】本発明は計算機システムにおける
記憶装置の領域管理に係わり、特に大容量ディスク時代
において、大小さまざまな大きさのファイルを割当てる
為の空き領域検索を効率よく実施するのに好適な空き領
域検索方法に関する。
記憶装置の領域管理に係わり、特に大容量ディスク時代
において、大小さまざまな大きさのファイルを割当てる
為の空き領域検索を効率よく実施するのに好適な空き領
域検索方法に関する。
【０００２】
【従来の技術】記憶装置の一つである磁気ディスク上に
領域を割当てる為の一つの従来技術が、特公平３ー１５
７７５号に述べられている。この従来技術では、ディス
ク（ＤＡＳＤ）上の記憶領域を所定の大きさを単位とす
るブロックに分割し、このブロックを１ビットに対応さ
せたビットマップを用い、前記各ビットの’１’、’
０’にによりＤＡＳＤ上の領域の使用状況を前記ブロッ
ク単位に把握し、ＤＡＳＤ上の空きスペース管理を実施
する。
領域を割当てる為の一つの従来技術が、特公平３ー１５
７７５号に述べられている。この従来技術では、ディス
ク（ＤＡＳＤ）上の記憶領域を所定の大きさを単位とす
るブロックに分割し、このブロックを１ビットに対応さ
せたビットマップを用い、前記各ビットの’１’、’
０’にによりＤＡＳＤ上の領域の使用状況を前記ブロッ
ク単位に把握し、ＤＡＳＤ上の空きスペース管理を実施
する。
【０００３】
【発明が解決しようとする課題】前記従来技術では、前
記ビットマップを用いた方法では、連続する空きスペー
スを検出する場合の、ビット連続数を計数する命令実行
オーバヘッドの問題を指摘し、その解決方法として前記
ビットマップを２種類の変換表を用いてバイト（８ビッ
ト）毎に検索する方法が述べられている。しかし、この
方式においてもビット毎の検索を８ビット毎の検索、す
なわち、高々８倍の効率化止まりであり、将来ＤＡＳＤ
容量が巨大化するにつれ効果が悪くなると言う問題があ
る。
記ビットマップを用いた方法では、連続する空きスペー
スを検出する場合の、ビット連続数を計数する命令実行
オーバヘッドの問題を指摘し、その解決方法として前記
ビットマップを２種類の変換表を用いてバイト（８ビッ
ト）毎に検索する方法が述べられている。しかし、この
方式においてもビット毎の検索を８ビット毎の検索、す
なわち、高々８倍の効率化止まりであり、将来ＤＡＳＤ
容量が巨大化するにつれ効果が悪くなると言う問題があ
る。
【０００４】上記の大容量時代におけるビットマップ検
索オーバヘッドを低減させる最も単純な方法は、前記ビ
ットマップの各ビットに対応させる領域の大きさをＤＡ
ＳＤの容量増加に合わせて、大きくすれば良い。しか
し、この方法は、割当て可能な最小領域の大きさをも大
きくする事になり、大容量領域の割当てには都合が良い
が、小容量領域の割当てでは、ビットマップ上の各ビッ
トに対応させた領域の大きさ分（前記で大きくしたとこ
ろの）は、最低でも割当て領域として消費する事になり
スペース効率の悪化と言った新たな問題が生じる。
索オーバヘッドを低減させる最も単純な方法は、前記ビ
ットマップの各ビットに対応させる領域の大きさをＤＡ
ＳＤの容量増加に合わせて、大きくすれば良い。しか
し、この方法は、割当て可能な最小領域の大きさをも大
きくする事になり、大容量領域の割当てには都合が良い
が、小容量領域の割当てでは、ビットマップ上の各ビッ
トに対応させた領域の大きさ分（前記で大きくしたとこ
ろの）は、最低でも割当て領域として消費する事になり
スペース効率の悪化と言った新たな問題が生じる。
【０００５】本発明の目的は大容量時代における上記の
様な問題を解決しうる効率の良い空きスペース検索を実
現する空き領域領域検索方法を提供する事にある。
様な問題を解決しうる効率の良い空きスペース検索を実
現する空き領域領域検索方法を提供する事にある。
【０００６】
【課題を解決するための手段】本発明では、上記目的を
達成するため以下の手段をもちいる。
達成するため以下の手段をもちいる。
【０００７】（１）複数種の領域管理テーブルを設け、 （２）各領域管理テーブルは、管理単位の大きさが異な
る構成とし、（例えば、前記の従来技術のビットマップ
管理例では、１ビットに対応するＤＡＳＤ上の領域長が
従来程度のビットマップと、同じく１ビットに対応する
領域長がその２倍の物、・・・ｎ倍の物と同一物理領域
に対して、管理単位の異なる複数種のビットマップを設
ける） （３）前記複数種の領域管理テーブルを検索すべき要求
スペース量に応じて選択し、使い分ける。
る構成とし、（例えば、前記の従来技術のビットマップ
管理例では、１ビットに対応するＤＡＳＤ上の領域長が
従来程度のビットマップと、同じく１ビットに対応する
領域長がその２倍の物、・・・ｎ倍の物と同一物理領域
に対して、管理単位の異なる複数種のビットマップを設
ける） （３）前記複数種の領域管理テーブルを検索すべき要求
スペース量に応じて選択し、使い分ける。
【０００８】
【作用】管理単位の異なる複数種の領域管理テーブルを
設け、検索すべき要求スペース量に応じて選択し、使い
分けるようにしたので、 （１）大容量空きスペース検索には大管理単位の管理テ
ーブルを用いて効率良く検索できる（検索すべきエント
リ総数が小）。
設け、検索すべき要求スペース量に応じて選択し、使い
分けるようにしたので、 （１）大容量空きスペース検索には大管理単位の管理テ
ーブルを用いて効率良く検索できる（検索すべきエント
リ総数が小）。
【０００９】（２）従来規模容量の空きスペース検索に
は小管理単位の管理テーブルを用いてスペース効率良く
記憶領域を利用できる。
は小管理単位の管理テーブルを用いてスペース効率良く
記憶領域を利用できる。
【００１０】（３）さらに、大小複数種の領域管理テー
ブルを、大管理単位で検索し、次に小管理単位で検索す
ると言った階層組合せ検索も実施可能であり、大小さま
ざまな空きスペース検索要求に対してもスペース効率を
悪化させる事なく効率良く検索できる。
ブルを、大管理単位で検索し、次に小管理単位で検索す
ると言った階層組合せ検索も実施可能であり、大小さま
ざまな空きスペース検索要求に対してもスペース効率を
悪化させる事なく効率良く検索できる。
【００１１】
【実施例】本発明の実施例を図面を用いて説明する。
図１に実施例における構成を示す。本実施例では、記憶
装置としてディスク（１０）装置を想定し、管理テーブ
ル形式はビットマップとし、以下の大小２つの管理テー
ブを設けた場合について説明する。
図１に実施例における構成を示す。本実施例では、記憶
装置としてディスク（１０）装置を想定し、管理テーブ
ル形式はビットマップとし、以下の大小２つの管理テー
ブを設けた場合について説明する。
【００１２】（１）１ＭＢ単位管理テーブル（３００） 本ビットマップは、１ビットを１ＭＢ(メガバイト)の領
域に対応させる。 （２）４ＫＢ単位管理テーブル（４００） 本ビットマップは、１ビットを４ＫＢ(キロバイト)の領
域に対応させる。 上記の管理テーブルは、ディスク（１０）上に存在す
る。本発明の特徴は、同一領域に対して異なる管理単位
のテーブル（３００、４００）を設けた事にあり、これ
らの管理テーブルは、ビットマップと呼ばれる形式をし
ており、他の構成要素であるスペースを検索プログラム
（１００）により選択使用される。スペース検索プログ
ラム（１００）は、前記ディスク（１０）にファイルを
確保する際、要求ファイルに必要な空きスペースを検索
する為のプログラムである。また、その内部には、前記
管理テーブル（３００、４００）のいづれを用いて空き
スペースを検索するかを判断するための、今回新たに設
けた領域管理テーブル選択部（２００）がある。以上
が、本実施例における主要構成要素である、次に、図２
に示す前記スペース検索プログラム（１００）の処理フ
ローを説明し、その中で前記各構成要素がどのような役
割を担うかについて述べる。
域に対応させる。 （２）４ＫＢ単位管理テーブル（４００） 本ビットマップは、１ビットを４ＫＢ(キロバイト)の領
域に対応させる。 上記の管理テーブルは、ディスク（１０）上に存在す
る。本発明の特徴は、同一領域に対して異なる管理単位
のテーブル（３００、４００）を設けた事にあり、これ
らの管理テーブルは、ビットマップと呼ばれる形式をし
ており、他の構成要素であるスペースを検索プログラム
（１００）により選択使用される。スペース検索プログ
ラム（１００）は、前記ディスク（１０）にファイルを
確保する際、要求ファイルに必要な空きスペースを検索
する為のプログラムである。また、その内部には、前記
管理テーブル（３００、４００）のいづれを用いて空き
スペースを検索するかを判断するための、今回新たに設
けた領域管理テーブル選択部（２００）がある。以上
が、本実施例における主要構成要素である、次に、図２
に示す前記スペース検索プログラム（１００）の処理フ
ローを説明し、その中で前記各構成要素がどのような役
割を担うかについて述べる。
【００１３】図２に示すスペース検索プログラム（１０
０）の処理フローを説明する前に、まず、本発明の特徴
でもある管理テーブル（３００、４００）の構成につい
て、図４、図５を用いてもう少し詳細に述べる。本管理
テーブルは、前述の様にビットマップと呼ばれる形式を
しており、そもそも、ビットマップとは、各ビットにデ
ータ領域を対応させ各ビットの位置がデータ領域の位置
をそのまま表すとともに、各ビットが’１’か’０’か
により対応するデータ領域が空き領域か否かを管理する
ものである。図４に示す前記管理テーブル（３００）
は、各ビットに連続する１ＭＢの大きさのデータ領域を
対応させたものであり、図４では上段にビットパターン
を示し、下段にはビットの列を８ビットづつ纏めたバイ
ト単位の位置を示している（以降の図５も同様に図
示）。一方、図５に示す前記管理テーブル（４００）
は、各ビットに連続する４ＫＢの大きさのデータ領域を
対応させたものであり、両者とも同一ディスク上の同一
領域をマッピングしている。言い換えれば、前記管理テ
ーブル（４００）は、図５に示すように、管理テーブル
（３００）内を詳細に管理する為の、サブ管理テーブル
とも言える。即ち、図５に示した、管理テーブル（４０
０）の１行分（３２バイト分）が、管理テーブル（３０
０）の１ビットに対応し、管理テーブル（４００）の先
頭から８行分（２５６バイト）毎に、管理テーブル（３
００）の各１バイトに対応する構造に成っている。ま
た、本実施例では、前記ビットが’１’の時、対応する
データ領域は使用済みであり、 ’０’の時、対応する
データ領域は空き領域である事を示すものとする。だた
し、管理テーブル（３００）においては、管理単位であ
る１ＭＢが全て未使用の場合にのみビットが’０’であ
り、前記１ＭＢ領域の内いづれかの４ＫＢ単位領域が使
用されている場合にはビットが’１’である。なお、本
実施例における当該ディスクの使用状況は、図４、図５
に示すように、仮定する。次に、前記の様な管理テーブ
ルを用い、ファイルの割当てに必要な空き領域を見つけ
るスペース検索プログラム（１００）の動作を、図２を
用い説明する。本実施例では、スペース検索プログラム
（１００）が起動される時にパラメータとして検索すべ
き空き領域の容量が渡され、起動されると、まず、ステ
ップ１１０でディスク１０上より管理テーブル（３００
および４００）を読み出しメインメモリ（図示せず）上
に置く。次に、ステップ２００で、前記パラメータとし
て渡された検索すべく要求された領域の大きさ（以下検
索スペース量と呼ぶ）と前記各管理テーブル上の管理単
位の大きさを比較し、管理単位が前記検索スペース量以
下で、かつ、最大である該管理テーブルを選択する。こ
の処理は本実施例では管理テーブルの数が２個であるた
め、前記検索スペース量と管理テーブル（３００）の管
理単位である１ＭＢとを比較し、１ＭＢ以上であれば管
理テーブル（３００）を選択し、そうでなければ管理テ
ーブル（４００）を階層的に検索する最初の管理テーブ
ルとして選択する。次に、このステップ２００の判定で
１ＭＢ以上の場合には、ステップ６００以降が実行さ
れ、１ＭＢ未満の場合には、ステップ５００以降が実行
される。まず、ステップ５００の方の動作を先に述べ
る。今、４０ＫＢの大きさのファイル領域を検索すると
仮定すると、ステップ５００の空きスペース検索では、
図５に示した前記管理テーブル（４００）上のビットを
検索し連続する１０個の、’０’を捜す事となる。本実
施では、管理テーブル４００のビットマップそのものの
ビット列検索には、図３に示す最も単純と思われる方式
を用いる事にする。次に、図２の説明に戻り前記ステッ
プ５００の処理を、図３を用いて述べる。なお、この処
理では、前述の様に管理テーブル（４００）上の連続す
る１０個の、’０’であるビットを検索する（すなわ
ち、４０ＫＢの領域を捜す）処理を仮定し説明する。図
３にビットマップ検索処理フローを示すが、本処理フロ
ーでは、説明簡単化のため本実施例で例示したビットマ
ップに対して処理可能な程度に省略してある。図３に示
すように処理が開始されると、まず、ステップ７００に
おいてＳＡＤＤＲに検索開始位置をセットする。この検
索開始位置は管理テーブル４００上の相対バイトアドレ
スで示し、図５に示した先頭のバイト０の位置をセット
する。次に、ステップ７１０で連続する’０’のビット
を計数する為のＣＯＵＮＴのゼロクリアおよび、前記連
続する’０’のビットの先頭バイト内のビット位置を示
す為のＴＯＰをゼロクリアする。その後、ステップ７２
０で前記ＳＡＤＤＲが示す管理テーブル４００上の１バ
イト分のデータをＷＯＲＫにロードし、ステップ７３０
で前記ＷＯＲＫにロードしたデータと１６進数の’Ｆ
Ｆ’とを比較し、前記データを構成するビットが全て’
１’か、すなわち、当該バイト上の各ビットに対応す全
ての領域が使用済みか否かを調べる。この判定におい
て、ＷＯＲＫ＝’ＦＦ’の場合は、使用済み領域であ
り、ステップ７４０、７５０でＣＯＵＮＴ＝０とＳＡＤ
ＤＲを一つ進め管理テーブル４００上の引き続く新たな
バイトに対して、上記説明したステップ７２０からの処
理を繰り返す(図３は繰り返しの上限や、エラーチェッ
クは省略)。上記ステップ７２０からの処理を繰り返す
内に、図５に示す様にバイト３２、３３に’０’のビッ
トが有るため、ＳＡＤＤＲ＝３２となった時に前記ステ
ップ７３０の判定で’ＮＯ’となりステップ７６０以降
の処理が実行され、当該バイト上をビット対応に検索す
る事になる。
０）の処理フローを説明する前に、まず、本発明の特徴
でもある管理テーブル（３００、４００）の構成につい
て、図４、図５を用いてもう少し詳細に述べる。本管理
テーブルは、前述の様にビットマップと呼ばれる形式を
しており、そもそも、ビットマップとは、各ビットにデ
ータ領域を対応させ各ビットの位置がデータ領域の位置
をそのまま表すとともに、各ビットが’１’か’０’か
により対応するデータ領域が空き領域か否かを管理する
ものである。図４に示す前記管理テーブル（３００）
は、各ビットに連続する１ＭＢの大きさのデータ領域を
対応させたものであり、図４では上段にビットパターン
を示し、下段にはビットの列を８ビットづつ纏めたバイ
ト単位の位置を示している（以降の図５も同様に図
示）。一方、図５に示す前記管理テーブル（４００）
は、各ビットに連続する４ＫＢの大きさのデータ領域を
対応させたものであり、両者とも同一ディスク上の同一
領域をマッピングしている。言い換えれば、前記管理テ
ーブル（４００）は、図５に示すように、管理テーブル
（３００）内を詳細に管理する為の、サブ管理テーブル
とも言える。即ち、図５に示した、管理テーブル（４０
０）の１行分（３２バイト分）が、管理テーブル（３０
０）の１ビットに対応し、管理テーブル（４００）の先
頭から８行分（２５６バイト）毎に、管理テーブル（３
００）の各１バイトに対応する構造に成っている。ま
た、本実施例では、前記ビットが’１’の時、対応する
データ領域は使用済みであり、 ’０’の時、対応する
データ領域は空き領域である事を示すものとする。だた
し、管理テーブル（３００）においては、管理単位であ
る１ＭＢが全て未使用の場合にのみビットが’０’であ
り、前記１ＭＢ領域の内いづれかの４ＫＢ単位領域が使
用されている場合にはビットが’１’である。なお、本
実施例における当該ディスクの使用状況は、図４、図５
に示すように、仮定する。次に、前記の様な管理テーブ
ルを用い、ファイルの割当てに必要な空き領域を見つけ
るスペース検索プログラム（１００）の動作を、図２を
用い説明する。本実施例では、スペース検索プログラム
（１００）が起動される時にパラメータとして検索すべ
き空き領域の容量が渡され、起動されると、まず、ステ
ップ１１０でディスク１０上より管理テーブル（３００
および４００）を読み出しメインメモリ（図示せず）上
に置く。次に、ステップ２００で、前記パラメータとし
て渡された検索すべく要求された領域の大きさ（以下検
索スペース量と呼ぶ）と前記各管理テーブル上の管理単
位の大きさを比較し、管理単位が前記検索スペース量以
下で、かつ、最大である該管理テーブルを選択する。こ
の処理は本実施例では管理テーブルの数が２個であるた
め、前記検索スペース量と管理テーブル（３００）の管
理単位である１ＭＢとを比較し、１ＭＢ以上であれば管
理テーブル（３００）を選択し、そうでなければ管理テ
ーブル（４００）を階層的に検索する最初の管理テーブ
ルとして選択する。次に、このステップ２００の判定で
１ＭＢ以上の場合には、ステップ６００以降が実行さ
れ、１ＭＢ未満の場合には、ステップ５００以降が実行
される。まず、ステップ５００の方の動作を先に述べ
る。今、４０ＫＢの大きさのファイル領域を検索すると
仮定すると、ステップ５００の空きスペース検索では、
図５に示した前記管理テーブル（４００）上のビットを
検索し連続する１０個の、’０’を捜す事となる。本実
施では、管理テーブル４００のビットマップそのものの
ビット列検索には、図３に示す最も単純と思われる方式
を用いる事にする。次に、図２の説明に戻り前記ステッ
プ５００の処理を、図３を用いて述べる。なお、この処
理では、前述の様に管理テーブル（４００）上の連続す
る１０個の、’０’であるビットを検索する（すなわ
ち、４０ＫＢの領域を捜す）処理を仮定し説明する。図
３にビットマップ検索処理フローを示すが、本処理フロ
ーでは、説明簡単化のため本実施例で例示したビットマ
ップに対して処理可能な程度に省略してある。図３に示
すように処理が開始されると、まず、ステップ７００に
おいてＳＡＤＤＲに検索開始位置をセットする。この検
索開始位置は管理テーブル４００上の相対バイトアドレ
スで示し、図５に示した先頭のバイト０の位置をセット
する。次に、ステップ７１０で連続する’０’のビット
を計数する為のＣＯＵＮＴのゼロクリアおよび、前記連
続する’０’のビットの先頭バイト内のビット位置を示
す為のＴＯＰをゼロクリアする。その後、ステップ７２
０で前記ＳＡＤＤＲが示す管理テーブル４００上の１バ
イト分のデータをＷＯＲＫにロードし、ステップ７３０
で前記ＷＯＲＫにロードしたデータと１６進数の’Ｆ
Ｆ’とを比較し、前記データを構成するビットが全て’
１’か、すなわち、当該バイト上の各ビットに対応す全
ての領域が使用済みか否かを調べる。この判定におい
て、ＷＯＲＫ＝’ＦＦ’の場合は、使用済み領域であ
り、ステップ７４０、７５０でＣＯＵＮＴ＝０とＳＡＤ
ＤＲを一つ進め管理テーブル４００上の引き続く新たな
バイトに対して、上記説明したステップ７２０からの処
理を繰り返す(図３は繰り返しの上限や、エラーチェッ
クは省略)。上記ステップ７２０からの処理を繰り返す
内に、図５に示す様にバイト３２、３３に’０’のビッ
トが有るため、ＳＡＤＤＲ＝３２となった時に前記ステ
ップ７３０の判定で’ＮＯ’となりステップ７６０以降
の処理が実行され、当該バイト上をビット対応に検索す
る事になる。
【００１４】この処理では、まず、ステップ７６０でル
ープカウンタ(ＬＯＯＰ)を０にセットし、ステップ７７
０、７８０でＬＯＯＰ＝８の判定とＬＯＯＰ＝ＬＯＯＰ
＋１により、当該バイト上の全ビットを検索し終ったか
を、判断する。従って、当該バイト上の全ビットを検索
し終るまでは、前記ステップ７７０の判定は’ＮＯ’と
なりステップ７８０以降が実行され、ステップ７８０は
前記の様にカウンタ(ＬＯＯＰ)を増加させる。次に、ス
テップ７９０でをＷＯＲＫにロードされているデータを
１ビット左にシフトさせ、ステップ８００でシフト後の
ＷＯＲＫの値の正／負を調べる。このステップ８００で
は、ＷＯＲＫの先頭ビットが’１’の場合すなわち、割
当て済みである場合には、ＷＯＲＫの値は負であり、’
０’の場合には、ＷＯＲＫの値は正である事を利用し
て、ビットが’１’か’０’かを調べている。前記図５
に示すのバイト３２は、左端を第０ビットとすると、第
０ビットは’１’であり、上記ステップ８００は’Ｎ
Ｏ’となりステップ８１０が実行される。ステップ８１
０では、連続する’０’のビットの先頭位置を示すため
の変数ＴＯＰ値を、当該ビットの次になる様、仮にセッ
トするとともに、当該ビットの含まれるバイト位置をＢ
ＡＤＤＲにセットする。次に、ステップ８１０で、’
０’連続ビットカウンタ（ＣＯＵＮＴ）を０にする（’
１’のビットが現れると無条件にクリアするようにし
た）。以上のステップ７７０から８２０までの処理を、
管理テーブル４００上の前記バイト３２に対して、最初
に’０のビットが現れるまで繰り返す。すなわち、第２
ビットを処理し、ＬＯＯＰ＝３，ＴＯＰ＝２となった場
合、前記ステップ８００は’ＹＥＳ’となり、ステップ
８３０が実行され、’０’連続ビットカウンタ（ＣＯＵ
ＮＴ）に１を加える。 次に、前記ＣＯＵＮＴの値が空
き領域の大きさを（ＣＯＵＮＴに４ＫＢを掛け算する）
示しており、これが、要求量を満たしたかをステップ８
４０で調べる。 今、ＣＯＵＮＴの値は１であり要求量
（本ケースの説明の冒頭で要求量を４ＫＢ，すなわち、
１０ビット分）を満たしておらず、このステップ８４０
では’ＮＯ’となり、前記ステップ７７０へ処理が戻
る。管理テーブル４００上の前記バイト３２の第２ビッ
ト以降には、’０’のビットが連続しているため、以上
述べたステップ７７０、７８０、７９０、８００、８３
０、８４０が、前記バイト３２の最後のビットに達する
まで繰り返し実行される。すなわち、ＴＯＰ＝２で、Ｌ
ＯＯＰ＝８となった時、前記ステップ７７０で’ＹＥ
Ｓ’となり、前記ステップ７５０にてＳＡＤＤＲが進め
られ、今度は前記管理テーブル４００上のバイト３３に
対して、先程まで述べてきた処理が実行される。これ
を、簡単に説明すると、前記と同様にステップ７２０で
ＷＯＲＫにロードされた前記バイト３３は、ステップ７
３０、７６０、を経て前記ステップ７７０、７８０、７
９０、８００、８３０、８４０のループにより処理さ
れ、ＣＯＵＮＴが１づつ増加される。そして、前記バイ
ト３３の第３ビット（左端を第０ビットとして数えて）
まで処理した時、ＣＯＵＮＴの値が１０となり、ステッ
プ８４０の判定が’ＹＥＳ’となり目的の大きさの空き
領域が検索出来た事になる。この、空き領域は、ステッ
プ８５０に示した様に、管理テーブル４００上の、上記
ＢＡＤＤＲで示すバイト上の上記ＴＯＰで示すビットを
先頭とする、上記ＣＯＵＮＴ個数分のビットに対応する
領域である。以上の様にして、４ＫＢ管理単位の管理テ
ーブル４００を用いたスペース検索（図２のステップ５
００）を実施し、前記図２のステップ１２０に戻る。図
２のステップ１２０では、上記述べた処理で要求を満た
す空き領域が見つかったか否かを判断し、見つからなか
った場合には空き領域不足エラー（ステップ１５０）と
し一連の検索処理を終了する。前記の様に要求を満たす
空き領域が見つかった場合には、ステップ１４０で当該
空き領域に対応する管理テーブル３００および、管理テ
ーブル４００上の各ビットを’１’にして処理を終了す
る。なお、’１’にするビットの位置は前述の様に変数
ＢＡＤＤＲ、ＴＯＰ、ＣＯＵＮＴより求まる（また、本
実施例で仮定した管理テーブルのビットパターンの様
に、一部が使用済みである１ＭＢの領域内から空き領域
を見つけた場合には、管理テーブル３００上のビットは
既に’１’であり、改めてセットする必要はない）。以
上で、検索スペース量が１ＭＢ未満の場合（小容量領域
の検索）の処理説明を終わり、次に、検索スペース量が
１ＭＢ以上の場合（大容量領域の検索）の処理について
述べる。この場合は、前記図２のステップ２００で、ス
テップ６００が実行されるよう判定される。このステッ
プ６００では詳細は後述するが、前記管理テーブル３０
０を用いて大単位で、空き領域候補を検索し、空き領域
候補が見つかると、必要に応じ、管理テーブル４００を
用いて小単位の検索を実施する。ステップ６００の検索
が終ると、以降は最初に説明したステップ５００の場合
と同様に、要求を満たす空き領域が見つかったか否かを
判断（ステップ１３０）し、前述のステップ１４０で当
該空き領域に対応する管理テーブル３００および、管理
テーブル４００上の各ビットを’１’にして処理を終了
する。以上ステップ６００に関する大まかな流れを述べ
たが、次に、上記では詳細な説明を省略したステップ６
００の処理を、図６を用い説明する。以降の説明にあた
り、本実施例では、２０５６ＫＢ（２ＭＢ＋８ＫＢ）の
領域を検索するものと仮定する。図６に示すように、ま
ず、ステップ９１０で変数Ｃ１に検索すべき要求空き量
を、１ＭＢ単位に切り下げ変換した値（管理テーブル３
００上のビット数に換算した事になる）をセットし、Ｃ
２には、同様に切り上げ変換した値をセットする。すな
わち、前記仮定では、検索領域を２ＭＢ＋８ＫＢとした
ので、Ｃ１＝２、Ｃ２＝３がセットされる。次に、図中
９００で示す前記図３で述べた方法により、管理テーブ
ル３００を対象として、１ＭＢ単位に空き領域を検索す
る。この、ステップ９００の処理で、前記図４に示す、
管理テーブル３００のバイト１の第０ビットに達するま
で（バイト０を処理している間）は、前記図３で述べた
様にステップ９００内でループ（ステップ７７０、７８
０、７９０、８００、８１０、８２０のループ）する。
そして、管理テーブル３００のバイト１の第０ビット
（左端を第０ビットとして表す）に達すると、ステップ
９００を抜け、ステップ９２０の判定がなされる。この
時，ＣＯＵＮＴは１でありステップ９２０および、引き
続くステップ９３０の判定は成り立たず、前記バイト１
上の次のビット（第１ビット）が前記ステップ９００で
処理される。この様にして処理が繰り返され、管理テー
ブル３００上のバイト１の第１ビット（左端を第０ビッ
トとして表す）に達すると、ＣＯＵＮＴ＝２（この時，
ＢＡＤＤＲ＝１、ＴＯＰ＝０である）となり、ステップ
９２０の判定が成り立ちステップ９６０以降の処理が実
行される。ステップ９６０ではＣ１＝要求量かを判断す
る、これは、要求量が丁度１ＭＢの倍数である場合のチ
ェックであり、本例示では判定が成り立たずステップ９
６５に進む。以上で、２ＭＢの大きさの領域（ＣＯＵＮ
Ｔ＝２）が空き領域候補として見つかった事になり、以
降の処理では、前記空き領域候補に隣接する８ＫＢの空
き領域が存在するかどうかを、今度は管理テーブル４０
０（４ＫＢ管理単位）を用いて調べる事になる。これ
は、まず、ステップ９６５で、前記２ＭＢの大きさの空
き領域候補に隣接する領域の内、前部に隣接する領域を
以下の様にしてしらべる。前記管理テーブル３００上で
の前記空き候補領域の先頭位置を示すＢＡＤＤＲおよび
ＴＯＰより、管理テーブル４００上の前記前部に隣接す
る領域に対応するバイトの位置を求める。すなわち、Ｂ
ＡＤＤＲを８倍し、ＴＯＰを加算した値を、３２倍し、
１を減じた値が管理テーブル４００上の調べるべきバイ
ト位置である。
ープカウンタ(ＬＯＯＰ)を０にセットし、ステップ７７
０、７８０でＬＯＯＰ＝８の判定とＬＯＯＰ＝ＬＯＯＰ
＋１により、当該バイト上の全ビットを検索し終ったか
を、判断する。従って、当該バイト上の全ビットを検索
し終るまでは、前記ステップ７７０の判定は’ＮＯ’と
なりステップ７８０以降が実行され、ステップ７８０は
前記の様にカウンタ(ＬＯＯＰ)を増加させる。次に、ス
テップ７９０でをＷＯＲＫにロードされているデータを
１ビット左にシフトさせ、ステップ８００でシフト後の
ＷＯＲＫの値の正／負を調べる。このステップ８００で
は、ＷＯＲＫの先頭ビットが’１’の場合すなわち、割
当て済みである場合には、ＷＯＲＫの値は負であり、’
０’の場合には、ＷＯＲＫの値は正である事を利用し
て、ビットが’１’か’０’かを調べている。前記図５
に示すのバイト３２は、左端を第０ビットとすると、第
０ビットは’１’であり、上記ステップ８００は’Ｎ
Ｏ’となりステップ８１０が実行される。ステップ８１
０では、連続する’０’のビットの先頭位置を示すため
の変数ＴＯＰ値を、当該ビットの次になる様、仮にセッ
トするとともに、当該ビットの含まれるバイト位置をＢ
ＡＤＤＲにセットする。次に、ステップ８１０で、’
０’連続ビットカウンタ（ＣＯＵＮＴ）を０にする（’
１’のビットが現れると無条件にクリアするようにし
た）。以上のステップ７７０から８２０までの処理を、
管理テーブル４００上の前記バイト３２に対して、最初
に’０のビットが現れるまで繰り返す。すなわち、第２
ビットを処理し、ＬＯＯＰ＝３，ＴＯＰ＝２となった場
合、前記ステップ８００は’ＹＥＳ’となり、ステップ
８３０が実行され、’０’連続ビットカウンタ（ＣＯＵ
ＮＴ）に１を加える。 次に、前記ＣＯＵＮＴの値が空
き領域の大きさを（ＣＯＵＮＴに４ＫＢを掛け算する）
示しており、これが、要求量を満たしたかをステップ８
４０で調べる。 今、ＣＯＵＮＴの値は１であり要求量
（本ケースの説明の冒頭で要求量を４ＫＢ，すなわち、
１０ビット分）を満たしておらず、このステップ８４０
では’ＮＯ’となり、前記ステップ７７０へ処理が戻
る。管理テーブル４００上の前記バイト３２の第２ビッ
ト以降には、’０’のビットが連続しているため、以上
述べたステップ７７０、７８０、７９０、８００、８３
０、８４０が、前記バイト３２の最後のビットに達する
まで繰り返し実行される。すなわち、ＴＯＰ＝２で、Ｌ
ＯＯＰ＝８となった時、前記ステップ７７０で’ＹＥ
Ｓ’となり、前記ステップ７５０にてＳＡＤＤＲが進め
られ、今度は前記管理テーブル４００上のバイト３３に
対して、先程まで述べてきた処理が実行される。これ
を、簡単に説明すると、前記と同様にステップ７２０で
ＷＯＲＫにロードされた前記バイト３３は、ステップ７
３０、７６０、を経て前記ステップ７７０、７８０、７
９０、８００、８３０、８４０のループにより処理さ
れ、ＣＯＵＮＴが１づつ増加される。そして、前記バイ
ト３３の第３ビット（左端を第０ビットとして数えて）
まで処理した時、ＣＯＵＮＴの値が１０となり、ステッ
プ８４０の判定が’ＹＥＳ’となり目的の大きさの空き
領域が検索出来た事になる。この、空き領域は、ステッ
プ８５０に示した様に、管理テーブル４００上の、上記
ＢＡＤＤＲで示すバイト上の上記ＴＯＰで示すビットを
先頭とする、上記ＣＯＵＮＴ個数分のビットに対応する
領域である。以上の様にして、４ＫＢ管理単位の管理テ
ーブル４００を用いたスペース検索（図２のステップ５
００）を実施し、前記図２のステップ１２０に戻る。図
２のステップ１２０では、上記述べた処理で要求を満た
す空き領域が見つかったか否かを判断し、見つからなか
った場合には空き領域不足エラー（ステップ１５０）と
し一連の検索処理を終了する。前記の様に要求を満たす
空き領域が見つかった場合には、ステップ１４０で当該
空き領域に対応する管理テーブル３００および、管理テ
ーブル４００上の各ビットを’１’にして処理を終了す
る。なお、’１’にするビットの位置は前述の様に変数
ＢＡＤＤＲ、ＴＯＰ、ＣＯＵＮＴより求まる（また、本
実施例で仮定した管理テーブルのビットパターンの様
に、一部が使用済みである１ＭＢの領域内から空き領域
を見つけた場合には、管理テーブル３００上のビットは
既に’１’であり、改めてセットする必要はない）。以
上で、検索スペース量が１ＭＢ未満の場合（小容量領域
の検索）の処理説明を終わり、次に、検索スペース量が
１ＭＢ以上の場合（大容量領域の検索）の処理について
述べる。この場合は、前記図２のステップ２００で、ス
テップ６００が実行されるよう判定される。このステッ
プ６００では詳細は後述するが、前記管理テーブル３０
０を用いて大単位で、空き領域候補を検索し、空き領域
候補が見つかると、必要に応じ、管理テーブル４００を
用いて小単位の検索を実施する。ステップ６００の検索
が終ると、以降は最初に説明したステップ５００の場合
と同様に、要求を満たす空き領域が見つかったか否かを
判断（ステップ１３０）し、前述のステップ１４０で当
該空き領域に対応する管理テーブル３００および、管理
テーブル４００上の各ビットを’１’にして処理を終了
する。以上ステップ６００に関する大まかな流れを述べ
たが、次に、上記では詳細な説明を省略したステップ６
００の処理を、図６を用い説明する。以降の説明にあた
り、本実施例では、２０５６ＫＢ（２ＭＢ＋８ＫＢ）の
領域を検索するものと仮定する。図６に示すように、ま
ず、ステップ９１０で変数Ｃ１に検索すべき要求空き量
を、１ＭＢ単位に切り下げ変換した値（管理テーブル３
００上のビット数に換算した事になる）をセットし、Ｃ
２には、同様に切り上げ変換した値をセットする。すな
わち、前記仮定では、検索領域を２ＭＢ＋８ＫＢとした
ので、Ｃ１＝２、Ｃ２＝３がセットされる。次に、図中
９００で示す前記図３で述べた方法により、管理テーブ
ル３００を対象として、１ＭＢ単位に空き領域を検索す
る。この、ステップ９００の処理で、前記図４に示す、
管理テーブル３００のバイト１の第０ビットに達するま
で（バイト０を処理している間）は、前記図３で述べた
様にステップ９００内でループ（ステップ７７０、７８
０、７９０、８００、８１０、８２０のループ）する。
そして、管理テーブル３００のバイト１の第０ビット
（左端を第０ビットとして表す）に達すると、ステップ
９００を抜け、ステップ９２０の判定がなされる。この
時，ＣＯＵＮＴは１でありステップ９２０および、引き
続くステップ９３０の判定は成り立たず、前記バイト１
上の次のビット（第１ビット）が前記ステップ９００で
処理される。この様にして処理が繰り返され、管理テー
ブル３００上のバイト１の第１ビット（左端を第０ビッ
トとして表す）に達すると、ＣＯＵＮＴ＝２（この時，
ＢＡＤＤＲ＝１、ＴＯＰ＝０である）となり、ステップ
９２０の判定が成り立ちステップ９６０以降の処理が実
行される。ステップ９６０ではＣ１＝要求量かを判断す
る、これは、要求量が丁度１ＭＢの倍数である場合のチ
ェックであり、本例示では判定が成り立たずステップ９
６５に進む。以上で、２ＭＢの大きさの領域（ＣＯＵＮ
Ｔ＝２）が空き領域候補として見つかった事になり、以
降の処理では、前記空き領域候補に隣接する８ＫＢの空
き領域が存在するかどうかを、今度は管理テーブル４０
０（４ＫＢ管理単位）を用いて調べる事になる。これ
は、まず、ステップ９６５で、前記２ＭＢの大きさの空
き領域候補に隣接する領域の内、前部に隣接する領域を
以下の様にしてしらべる。前記管理テーブル３００上で
の前記空き候補領域の先頭位置を示すＢＡＤＤＲおよび
ＴＯＰより、管理テーブル４００上の前記前部に隣接す
る領域に対応するバイトの位置を求める。すなわち、Ｂ
ＡＤＤＲを８倍し、ＴＯＰを加算した値を、３２倍し、
１を減じた値が管理テーブル４００上の調べるべきバイ
ト位置である。
【００１５】具体的には、（１×８＋０）×３２ー１＝
２５５、すなわち、管理テーブル４００上のバイト２５
５（図５）が求まる。 従って、ステップ９６５では、
このバイト２５５の右端より左方向へ連続す’０’のビ
ット数を計数する事により、４ＫＢ領域が１個存在する
事が検知でき、前記２ＭＢの領域と合わせて２ＭＢ＋４
ＫＢの領域が空き領域候補として見つかった事になる。
次に、ステップ９７０で、前記空き領域候補(２ＭＢ＋
４ＫＢ)の大きさが要求容量(２ＭＢ＋８ＫＢ)を満たす
かを調べ、満たしていないので、今度は、前記空き領域
候補の後部に隣接す空き領域を調べるため、ステップ９
７５が実行される。ステップ９７５でも、前記と同様に
管理テーブル４００上のバイト位置を計算する、この場
合には、(ＢＡＤＤＲ×８＋ＴＯＰ＋ＣＯＵＮＴ)×３２
で前記後部隣接バイト位置を計算する。具体的には、
(１×８＋０＋２)×３２＝３２０、すなわち、管理テー
ブル４００上のバイト３２０（図５）を調べればよい。
従って、ステップ９７５では、このバイト３２０の左端
より右方向へ連続す’０’のビット数を計数する事によ
り、４ＫＢ領域が１個存在する事が検知でき、前記空き
領域候補(２ＭＢ＋４ＫＢ)と合わせて２ＭＢ＋４ＫＢ＋
４ＫＢの空き領域が見つかった事になり、ステップ９８
０で要求量を満たしていることを確認し、検索処理を終
える。なお、上記で検索した領域は、ステップ９８５に
示す様に、管理テーブル３００上のＢＡＤＤＲで示すバ
イトのＴＯＰが示すビットを先頭とす２ＭＢの領域と、
その前後に隣接す各４ＫＢの領域である。以上述べた様
に、本実施例では、１ＭＢと４ＫＢの異なる単位の管理
テーブルを設け、１ＭＢ以上の領域検索には１ＭＢ単位
の管理テーブルを用いる事により、検索ビット数が４Ｋ
Ｂ単位の管理テーブルを用いる場合に比べ、２５６分の
１近くに減少し、その分検索に要する命令実行オーバヘ
ッドが低減できる。さらに、４ＫＢ単位の管理テーブル
を併用する事により小さい容量の検索においても、スペ
ース効率の悪化を招くことがない。
２５５、すなわち、管理テーブル４００上のバイト２５
５（図５）が求まる。 従って、ステップ９６５では、
このバイト２５５の右端より左方向へ連続す’０’のビ
ット数を計数する事により、４ＫＢ領域が１個存在する
事が検知でき、前記２ＭＢの領域と合わせて２ＭＢ＋４
ＫＢの領域が空き領域候補として見つかった事になる。
次に、ステップ９７０で、前記空き領域候補(２ＭＢ＋
４ＫＢ)の大きさが要求容量(２ＭＢ＋８ＫＢ)を満たす
かを調べ、満たしていないので、今度は、前記空き領域
候補の後部に隣接す空き領域を調べるため、ステップ９
７５が実行される。ステップ９７５でも、前記と同様に
管理テーブル４００上のバイト位置を計算する、この場
合には、(ＢＡＤＤＲ×８＋ＴＯＰ＋ＣＯＵＮＴ)×３２
で前記後部隣接バイト位置を計算する。具体的には、
(１×８＋０＋２)×３２＝３２０、すなわち、管理テー
ブル４００上のバイト３２０（図５）を調べればよい。
従って、ステップ９７５では、このバイト３２０の左端
より右方向へ連続す’０’のビット数を計数する事によ
り、４ＫＢ領域が１個存在する事が検知でき、前記空き
領域候補(２ＭＢ＋４ＫＢ)と合わせて２ＭＢ＋４ＫＢ＋
４ＫＢの空き領域が見つかった事になり、ステップ９８
０で要求量を満たしていることを確認し、検索処理を終
える。なお、上記で検索した領域は、ステップ９８５に
示す様に、管理テーブル３００上のＢＡＤＤＲで示すバ
イトのＴＯＰが示すビットを先頭とす２ＭＢの領域と、
その前後に隣接す各４ＫＢの領域である。以上述べた様
に、本実施例では、１ＭＢと４ＫＢの異なる単位の管理
テーブルを設け、１ＭＢ以上の領域検索には１ＭＢ単位
の管理テーブルを用いる事により、検索ビット数が４Ｋ
Ｂ単位の管理テーブルを用いる場合に比べ、２５６分の
１近くに減少し、その分検索に要する命令実行オーバヘ
ッドが低減できる。さらに、４ＫＢ単位の管理テーブル
を併用する事により小さい容量の検索においても、スペ
ース効率の悪化を招くことがない。
【００１６】本発明の第２の実施例を図７を用いて説明
する。本実施例では、先に述べた第１の実施例と同じく
記憶装置としてディスク（１０）装置を想定し、管理テ
ーブルも前記の大小２つの管理テーブル（３００、４０
０）が設けられている。第１の実施例と異なるのは、図
７に示す前記スペース検索プログラム（１００）の処理
フローのみである。図７に示す処理フローは、図２と同
様のステップは同一の番号で示しており、太線で示した
ステップ５１０と５２０が本実施例における相違点であ
る。
する。本実施例では、先に述べた第１の実施例と同じく
記憶装置としてディスク（１０）装置を想定し、管理テ
ーブルも前記の大小２つの管理テーブル（３００、４０
０）が設けられている。第１の実施例と異なるのは、図
７に示す前記スペース検索プログラム（１００）の処理
フローのみである。図７に示す処理フローは、図２と同
様のステップは同一の番号で示しており、太線で示した
ステップ５１０と５２０が本実施例における相違点であ
る。
【００１７】本実施例でも、先に述べた第１の実施例と
同じく起動時に、パラメータとして検索すべく要求され
た領域の大きさ（以下検索スペース量と呼ぶ）が渡さ
れ、次に、ステップ１１０が同様に実行される。次に、
ステップ２００で前記パラメータとして渡された検索ス
ペース量に応じて、検索に使用する前記管理テーブルを
一つ選択する。この選択も第１の実施例と同様にして成
される。このステップ２００において管理テーブル（４
００）が選択された場合実施するステップ５００以降の
処理は先に述べた第１の実施例と同じであり簡単化のた
め説明を省略し、もう一方の管理テーブル（３００）が
選択された場合について以下説明する。この場合には、
ステップ５１０で前記渡された検索スペース量を当該管
理テーブル（３００）の管理単位である１ＭＢ単位に切
り上げ、この１ＭＢ単位に切り上げた値を検索すべく要
求された領域の大きさとして、ステップ５２０の空きス
ペース検索処理を前記図３で述べた様に実施する。以降
のステップ１３０に引き続く処理は、第１の実施例で既
に説明済みでありここでは省略する。以上の様にして検
索すべく要求された領域の大きさに応じて複数の管理テ
ーブルの一つを選択し、大容量が要求された時には大き
な管理単位で検索し、小大容量が要求された時には小さ
な単位で検索する事により第１の実施例と同様に効率よ
くスペース検索が実施できる。なお、本実施例の場合に
は渡された検索スペース量を当該管理テーブルの管理単
位に切り上げた量のスペース量を検索するため、当該管
理単位未満の過剰が生じる。これが問題となる場合に
は、先に述べたステップ２００の判定条件に、選択した
当該管理テーブルの管理単位に対して「記検索スペース
量が十分に大きいか」と言う条件を付加するか、第１の
実施例の方法を用いれば良い。
同じく起動時に、パラメータとして検索すべく要求され
た領域の大きさ（以下検索スペース量と呼ぶ）が渡さ
れ、次に、ステップ１１０が同様に実行される。次に、
ステップ２００で前記パラメータとして渡された検索ス
ペース量に応じて、検索に使用する前記管理テーブルを
一つ選択する。この選択も第１の実施例と同様にして成
される。このステップ２００において管理テーブル（４
００）が選択された場合実施するステップ５００以降の
処理は先に述べた第１の実施例と同じであり簡単化のた
め説明を省略し、もう一方の管理テーブル（３００）が
選択された場合について以下説明する。この場合には、
ステップ５１０で前記渡された検索スペース量を当該管
理テーブル（３００）の管理単位である１ＭＢ単位に切
り上げ、この１ＭＢ単位に切り上げた値を検索すべく要
求された領域の大きさとして、ステップ５２０の空きス
ペース検索処理を前記図３で述べた様に実施する。以降
のステップ１３０に引き続く処理は、第１の実施例で既
に説明済みでありここでは省略する。以上の様にして検
索すべく要求された領域の大きさに応じて複数の管理テ
ーブルの一つを選択し、大容量が要求された時には大き
な管理単位で検索し、小大容量が要求された時には小さ
な単位で検索する事により第１の実施例と同様に効率よ
くスペース検索が実施できる。なお、本実施例の場合に
は渡された検索スペース量を当該管理テーブルの管理単
位に切り上げた量のスペース量を検索するため、当該管
理単位未満の過剰が生じる。これが問題となる場合に
は、先に述べたステップ２００の判定条件に、選択した
当該管理テーブルの管理単位に対して「記検索スペース
量が十分に大きいか」と言う条件を付加するか、第１の
実施例の方法を用いれば良い。
【００１８】
【発明の効果】本発明では、管理単位の異なる複数種の
領域管理テーブルを設け、検索すべき要求スペース量に
応じて選択し、使い分けるようにしたので、 （１）大容量空きスペース検索には大管理単位の管理テ
ーブルを用いて効率良く検索できる。
領域管理テーブルを設け、検索すべき要求スペース量に
応じて選択し、使い分けるようにしたので、 （１）大容量空きスペース検索には大管理単位の管理テ
ーブルを用いて効率良く検索できる。
【００１９】（２）小容量の空きスペース検索には小管
理単位の管理テーブルを用いてスペース効率良く記憶領
域を利用できる。
理単位の管理テーブルを用いてスペース効率良く記憶領
域を利用できる。
【００２０】（３）さらに、大小複数種の領域管理テー
ブルを、大管理単位で検索し、次に小管理単位で検索す
ると言った階層組合せ検索も実施可能であり、大小さま
ざまな空きスペース検索要求に対してもスペース効率を
悪化させる事がなくなる。
ブルを、大管理単位で検索し、次に小管理単位で検索す
ると言った階層組合せ検索も実施可能であり、大小さま
ざまな空きスペース検索要求に対してもスペース効率を
悪化させる事がなくなる。
【００２１】したがって、記憶装置の容量増加に合わせ
て、比較的自由に、大管理単位を設定可能となり、記憶
装置の容量増加に比例して増加する空きスペース検索の
為の命令実行オーバヘッドを抑止でき、小容量検索にお
いても、スペース効率の悪化を抑止できる。
て、比較的自由に、大管理単位を設定可能となり、記憶
装置の容量増加に比例して増加する空きスペース検索の
為の命令実行オーバヘッドを抑止でき、小容量検索にお
いても、スペース効率の悪化を抑止できる。
【図１】構成要素を示す図。
【図２】スペース検索プログラムの処理フローを示す
図。
図。
【図３】スペース検索プログラム中のステップ５００の
ビットマップ検索処理フローを示す図。
ビットマップ検索処理フローを示す図。
【図４】１ＭＢ単位のビットマップ管理テーブルを示す
図。
図。
【図５】４ＫＢ単位のビットマップ管理テーブルを示す
図。
図。
【図６】スペース検索プログラム中のステップ６００の
ビットマップ検索処理フローを示す図。
ビットマップ検索処理フローを示す図。
【図７】第２実施例におけるスペース検索プログラムの
処理フローを示す図。
処理フローを示す図。
１０…ディスク装置、２０…ディスク装置上のファイル
割当て領域、１００…ペース検索プログラム、２００…
スペース検索プログラム中の管理テーブル選択部、３０
０…１ＭＢ単位の管理テーブル、４００…４ＫＢ単位の
管理テーブル。
割当て領域、１００…ペース検索プログラム、２００…
スペース検索プログラム中の管理テーブル選択部、３０
０…１ＭＢ単位の管理テーブル、４００…４ＫＢ単位の
管理テーブル。
Claims (6)
- 【請求項１】（ａ）複数の分割サイズの一つにそれぞれ
対応して設けられた管理テーブルの各々に記憶装置内の
同一領域を、その管理テーブルに対応する分割サイズに
より分割して得られる単位領域の各々の使用状況を記憶
し、 （ｂ）該領域内の空き領域を検索する場合、検索すべき
空き領域の総量に応じて該複数の管理テーブルの一つを
選択し、この選択された管理テーブルを用いて、それが
管理する複数の単位領域の内、その総量が上記検索すべ
き総量より小さくない一つ又は複数の使用中でない単位
領域を検索し、 （ｃ）その後、各管理テーブルが管理する単位領域の
内、該検索された一つ又は複数の単位領域に対応する単
位領域の使用状況を書きかえるよう、各管理テーブルを
更新する空き領域検索方法。 - 【請求項２】該複数の分割サイズは、互いに整数倍の関
係にある請求項１記載の空き領域検索方法。 - 【請求項３】該管理テーブルはその各々のエントリを１
ビットで構成するビットマップ形式のテーブルである請
求項１の空き領域検索方法。 - 【請求項４】（ａ）複数の分割サイズの一つにそれぞれ
対応して設けられた管理テーブルの各々に記憶装置内の
同一領域を、その管理テーブルに対応する分割サイズに
より分割して得られる単位領域の各々の使用状況を記憶
し、 （ｂ）その後該領域内の空き領域検索する場合に、該複
数管理テーブルの内の複数の管理テーブルを対応する分
割サイズが大きいものから順に用いて、その検索すべき
総量より小さくない空き領域を検索し、 （ｃ）その後、前記複数の該管理テーブルの各々内の、
該検索された空き領域に対応する単位領域に対する使用
状況を書き換える空き領域検索方法。 - 【請求項５】複数種の前記管理テーブルが各管理テーブ
ル上の各々のエントリを１ビットで構成するビットマッ
プ形式である請求項４の空き領域検索方法。 - 【請求項６】空き領域検索（ｂ）の実行時には、 （ｂ１）まず、検索すべき空き領域の総量と前記複数の
分割サイズとから、該検索すべき総量をこえない分割サ
イズの内、最大の分割サイズに対応する第１の管理テー
ブルを選択し、この第１の管理テーブルを用いて大単位
で該総量の内、該最大分割サイズをこえる総量を有する
空き領域を検索し、 （ｂ２）該総量の内の残りの量を新たに検索すべき総量
とみなして該ステップ（ｂ１）を行う請求項４の空き領
域検索方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3199085A JPH0546447A (ja) | 1991-08-08 | 1991-08-08 | 空き領域検索方法 |
| US07/925,654 US5481702A (en) | 1991-08-08 | 1992-08-07 | Allocation optimization with different block-sized allocation maps |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3199085A JPH0546447A (ja) | 1991-08-08 | 1991-08-08 | 空き領域検索方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0546447A true JPH0546447A (ja) | 1993-02-26 |
Family
ID=16401856
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3199085A Pending JPH0546447A (ja) | 1991-08-08 | 1991-08-08 | 空き領域検索方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5481702A (ja) |
| JP (1) | JPH0546447A (ja) |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0728693A (ja) * | 1993-06-30 | 1995-01-31 | Microsoft Corp | ディスクスペースを管理する変型バデイシステム |
| JPH07182239A (ja) * | 1993-12-24 | 1995-07-21 | Nec Corp | セグメント分割管理システム |
| WO2010143364A1 (ja) * | 2009-06-11 | 2010-12-16 | 株式会社エスグランツ | 区画管理装置、区画管理方法及びプログラム |
| WO2011099284A1 (ja) * | 2010-02-15 | 2011-08-18 | 株式会社エスグランツ | 区画管理装置、区画管理方法及びプログラム |
| JP2011216111A (ja) * | 2011-07-12 | 2011-10-27 | S Grants Co Ltd | 区画管理装置、区画管理方法及びプログラム |
| US9619151B2 (en) | 2009-06-11 | 2017-04-11 | Makoto Yoshioka | Region management apparatus, region management method, and program |
Families Citing this family (30)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100330289B1 (ko) * | 1993-10-18 | 2002-10-04 | 소니 가부시끼 가이샤 | 정보관리방법,데이터기록매체,데이터기록방법,정보검색방법및정보검색장치 |
| US5745749A (en) * | 1994-06-27 | 1998-04-28 | International Business Machines Corp. | Method and system of file version clustering of object blocks using a compiler and database and having a predetermined value |
| US5652864A (en) * | 1994-09-23 | 1997-07-29 | Ibm | Concurrent storage allocations or returns without need to lock free storage chain |
| US5644789A (en) * | 1995-01-19 | 1997-07-01 | Hewlett-Packard Company | System and method for handling I/O requests over an interface bus to a storage disk array |
| US5797033A (en) * | 1995-03-31 | 1998-08-18 | Cirrus Logic, Inc. | Direct memory access for storing and retrieving data based on packet size |
| CA2230859C (en) * | 1995-08-31 | 2002-12-31 | Sand Technology Systems International, Inc. | Memory management system and method |
| US5835959A (en) * | 1995-12-01 | 1998-11-10 | Sand Technology Systems International, Inc. | Memory management system and method using dual indexing structures |
| US5758353A (en) * | 1995-12-01 | 1998-05-26 | Sand Technology Systems International, Inc. | Storage and retrieval of ordered sets of keys in a compact 0-complete tree |
| US6427147B1 (en) | 1995-12-01 | 2002-07-30 | Sand Technology Systems International | Deletion of ordered sets of keys in a compact O-complete tree |
| US5872905A (en) * | 1996-03-14 | 1999-02-16 | Matsushita Electric Industrial Co., Ltd. | Recording area management method, error recovery processing method, and storage apparatus |
| US5778392A (en) * | 1996-04-01 | 1998-07-07 | Symantec Corporation | Opportunistic tile-pulling, vacancy-filling method and apparatus for file-structure reorganization |
| GB2312059B (en) * | 1996-04-12 | 2000-11-15 | Sony Uk Ltd | Data storage |
| JPH10301818A (ja) * | 1997-04-28 | 1998-11-13 | Matsushita Electric Ind Co Ltd | ファイルシステム及びその管理方法 |
| US6182089B1 (en) * | 1997-09-23 | 2001-01-30 | Silicon Graphics, Inc. | Method, system and computer program product for dynamically allocating large memory pages of different sizes |
| US5987479A (en) * | 1997-09-24 | 1999-11-16 | Sony Corporation, Inc. | Large block allocation for disk-based file systems |
| US6018789A (en) * | 1997-11-24 | 2000-01-25 | Western Digital Corporation | Disk drive with cache segment providing adaptively managed chunks |
| US6112211A (en) * | 1997-11-25 | 2000-08-29 | International Business Machines Corporation | Reconfiguration an aggregate file including delete-file space for optimal compression |
| JP3218007B2 (ja) * | 1998-03-20 | 2001-10-15 | 富士通株式会社 | インデックスの管理装置，更新方法及び管理方法並びにコンピュータ読取可能な記憶媒体 |
| US6411770B1 (en) * | 1998-07-02 | 2002-06-25 | Sony Corporation | Data recording method and apparatus |
| JP4067650B2 (ja) * | 1998-07-17 | 2008-03-26 | 株式会社東芝 | データ記録装置およびデータ記録方法 |
| US6804761B1 (en) * | 2000-01-21 | 2004-10-12 | Cisco Technology, Inc. | Memory allocation system and method |
| JP4130076B2 (ja) * | 2001-12-21 | 2008-08-06 | 富士通株式会社 | データベース管理プログラムおよび記録媒体 |
| JP3832341B2 (ja) * | 2001-12-27 | 2006-10-11 | 日本電気株式会社 | メモリプール管理方式 |
| PL351779A1 (en) * | 2002-01-18 | 2003-07-28 | Advanced Digital Broadcast Ltd | Apparatus for storing data and method of subdividing te data storage area |
| US7124272B1 (en) | 2003-04-18 | 2006-10-17 | Symantec Corporation | File usage history log for improved placement of files in differential rate memory according to frequency of utilizations and volatility of allocation space |
| KR100883651B1 (ko) * | 2006-05-18 | 2009-02-18 | 삼성전자주식회사 | 파일을 저장할 디스크의 공간을 할당하는 방법 및 장치 |
| JP2009009545A (ja) * | 2007-01-31 | 2009-01-15 | Hewlett-Packard Development Co Lp | データ処理システム及び方法 |
| US7945587B2 (en) * | 2007-10-10 | 2011-05-17 | Microsoft Corporation | Random allocation of media storage units |
| US8209513B2 (en) * | 2009-11-12 | 2012-06-26 | Autonomy, Inc. | Data processing system with application-controlled allocation of file storage space |
| CN111722802B (zh) * | 2020-06-12 | 2022-07-22 | 苏州浪潮智能科技有限公司 | 一种元数据lsa卷的存储空间分配方法、装置及设备 |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0296213A (ja) * | 1988-10-03 | 1990-04-09 | Nec Corp | 階層ビットマップによる二次記憶管理方法 |
| JPH02252035A (ja) * | 1989-03-24 | 1990-10-09 | Hitachi Ltd | 磁気ディスク内領域のファイルへの割り当て方式 |
| JPH0392941A (ja) * | 1989-09-06 | 1991-04-18 | Hitachi Ltd | 領域管理方式 |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4536837A (en) * | 1982-05-25 | 1985-08-20 | Elxsi | Improved disk file allocation and mapping system utilizing cylinder control blocks and file map having unbalanced tree structure |
| US4908789A (en) * | 1987-04-01 | 1990-03-13 | International Business Machines Corporation | Method and system for automatically assigning memory modules of different predetermined capacities to contiguous segments of a linear address range |
| JP2960415B2 (ja) * | 1987-05-22 | 1999-10-06 | 株式会社日立製作所 | 記憶保護方法および装置 |
| US5129088A (en) * | 1987-11-30 | 1992-07-07 | International Business Machines Corporation | Data processing method to create virtual disks from non-contiguous groups of logically contiguous addressable blocks of direct access storage device |
| US4992935A (en) * | 1988-07-12 | 1991-02-12 | International Business Machines Corporation | Bit map search by competitive processors |
| US5058003A (en) * | 1988-12-15 | 1991-10-15 | International Business Machines Corporation | Virtual storage dynamic address translation mechanism for multiple-sized pages |
| GB8829919D0 (en) * | 1988-12-22 | 1989-02-15 | Int Computer Limited | File system |
| FR2652926B1 (fr) * | 1989-10-06 | 1994-07-08 | Bull Sa | Procede d'exploitation de la memoire dans un systeme informatique du type a adressage virtuel et dispositif pour la mise en óoeuvre dudit procede. |
| US5339411A (en) * | 1990-12-21 | 1994-08-16 | Pitney Bowes Inc. | Method for managing allocation of memory space |
-
1991
- 1991-08-08 JP JP3199085A patent/JPH0546447A/ja active Pending
-
1992
- 1992-08-07 US US07/925,654 patent/US5481702A/en not_active Expired - Fee Related
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0296213A (ja) * | 1988-10-03 | 1990-04-09 | Nec Corp | 階層ビットマップによる二次記憶管理方法 |
| JPH02252035A (ja) * | 1989-03-24 | 1990-10-09 | Hitachi Ltd | 磁気ディスク内領域のファイルへの割り当て方式 |
| JPH0392941A (ja) * | 1989-09-06 | 1991-04-18 | Hitachi Ltd | 領域管理方式 |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0728693A (ja) * | 1993-06-30 | 1995-01-31 | Microsoft Corp | ディスクスペースを管理する変型バデイシステム |
| JPH07182239A (ja) * | 1993-12-24 | 1995-07-21 | Nec Corp | セグメント分割管理システム |
| WO2010143364A1 (ja) * | 2009-06-11 | 2010-12-16 | 株式会社エスグランツ | 区画管理装置、区画管理方法及びプログラム |
| JP2010287066A (ja) * | 2009-06-11 | 2010-12-24 | S Grants Co Ltd | 区画管理装置、区画管理方法及びプログラム |
| US9619151B2 (en) | 2009-06-11 | 2017-04-11 | Makoto Yoshioka | Region management apparatus, region management method, and program |
| WO2011099284A1 (ja) * | 2010-02-15 | 2011-08-18 | 株式会社エスグランツ | 区画管理装置、区画管理方法及びプログラム |
| JP2011204279A (ja) * | 2010-02-15 | 2011-10-13 | S Grants Co Ltd | 区画管理装置、区画管理方法及びプログラム |
| JP2011216111A (ja) * | 2011-07-12 | 2011-10-27 | S Grants Co Ltd | 区画管理装置、区画管理方法及びプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| US5481702A (en) | 1996-01-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0546447A (ja) | 空き領域検索方法 | |
| JP3628032B2 (ja) | コンサーバティブ・スタックとジェネレイショナル・ヒープガーベージ・コレクション用コンピュータシステム及び方法 | |
| US5321834A (en) | Method and system for reclaiming unreferenced computer memory space | |
| US5784699A (en) | Dynamic memory allocation in a computer using a bit map index | |
| US5109336A (en) | Unified working storage management | |
| US6067547A (en) | Hash table expansion and contraction for use with internal searching | |
| JP2858795B2 (ja) | 実記憶割り当て方法 | |
| US6343341B1 (en) | Efficient access to variable-length data on a sequential access storage medium | |
| US7822790B2 (en) | Relative positioning and access of memory objects | |
| JPH05189281A (ja) | 記憶装置のファイル割当て方式 | |
| US10031843B2 (en) | Managing memory in a computer system | |
| CN109977373B (zh) | 标识号分配方法、标识号回收方法及装置 | |
| CN116301614B (zh) | 存储器数据存取方法、系统、设备和存储介质 | |
| CN110163791B (zh) | 数据计算流图的gpu处理方法及装置 | |
| CN116541132A (zh) | 一种间接访问变量栈的管理方法和装置 | |
| EP4134802B1 (en) | Method and apparatus for data access of nand flash file, and storage medium | |
| CN108804571B (zh) | 一种数据存储方法、装置以及设备 | |
| CN117724991B (zh) | 嵌入式系统的动态内存管理方法、系统、终端及存储介质 | |
| CN112003960A (zh) | 工控设备的网络接口管理方法、装置和电子装置 | |
| US20060236065A1 (en) | Method and system for variable dynamic memory management | |
| US7421539B1 (en) | Method and system for concurrent garbage collection and mutator execution | |
| JP4033829B2 (ja) | メモリ管理システム | |
| US7584231B1 (en) | Methods for determining a safe end of scan for generational garbage collection | |
| JP3801176B2 (ja) | メモリ制御方法、記憶装置、制御プログラムおよび可読記録媒体 | |
| CN117435352B (zh) | 一种定长变长数据混合管理的轻量化内存优化分配方法 |