JPH0315775B2 - - Google Patents

Description

【発明の詳細な説明】

(a) 発明の技術分野 本発明は処理装置に接続される直接アクセス記
憶装置の格納状態、特に空きスペースを管理する
ための空きスペース検索方法に関する。 (b) 従来技術と問題点 処理装置に接続される直接アクセス記憶装置
（以後DASDと記入する）は種々の情報が格納さ
れ、しかも不必要であれば消去も行われている。
従つて、このDASD上の空きスペースを管理する
ことが必要である。 このため、DASD上の記憶領域を所定の大きさ
を単位とするブロツクに分割し、このブロツクご
とに１ビツトを対応させたビツトマツプを用い、
未使用のブロツクに対するビツトは‘0'、使用中
のブロツクに対するビツトは‘1'として、DASD
の使用状態を管理している。 従来このビツトマツプから連続する空きスペー
ス即ち‘0'の数を検出するのに、ビツトマツプか
ら１バイト単位でレジスタに順次入力し、これを
左シフトして、シフトアウトされる‘0'、‘1'を
計数することにより、連続した空きスペースを検
知するといつた方法が採用されている。 この従来の空きスペースの検索方法は、１バイ
トを検査するのに、シフト命令と比較命令をそれ
ぞれ８回必要とし、この二つの命令だけで16ステ
ツプを要する。従つて、ビツトマツプを全域にわ
たつて調べるには、命令のステツプ数は非常に大
きなものとなる。そのため、従来方法では、空き
スペースの管理は処理速度が遅いという問題があ
つた。 (c) 本発明の目的 本発明は上記従来の欠点に鑑み、高速に能率よ
く空きスペースの検索を行うことのできる、空き
スペース検索方法を提供することを目的とする。 (d) 発明の構成 本発明は、直接アクセス記憶装置（DASD）
と、その記憶領域の使用状態を示すビツトマツプ
を具備する処理装置において、１つのバイトを最
高位ビツトから見て最初に現れる‘0'の数と、そ
の‘0'のビツト列が最下位ビツトを含むか否か
を、ビツトパターン対応に示す第１の変換表と、
１バイトの最高位ビツトが‘0'の場合には、最高
位ビツトから連続する‘0'のビツト数を、最高位
ビツトが‘1'の場合にはその旨を識別しうる値
を、ビツトパターン対応に示す第２の変換表を設
ける。 但し、上記第２の変換表は、特殊な場合として
最高位ビツトから‘0'が８個連続する場合、即ち
全ビツトが‘0'の場合には、変換値を本来の‘8'
に変えて‘0'としておく。 また、最高位ビツトが‘1'の場合には、その旨
を識別できるように、例えば‘8'以上の値を対応
させておく。 空きスペースの検索に際しては、DASDの使用
状態を示すビツトマツプの所定のバイトを、ま
ず、そのビツトパターンに基づいて第１の変換表
を参照し、対応する変換値を読み出す。変換値が
“０”の場合には、次のバイトに対して同じ処理
を続行する。変換値が“０”と異なる値であれば
処理を停止し、その時のバイトのアドレスを‘0'
を含むバイト列の先頭アドレスとし、その時の変
換値からそのバイトの‘0'の個数と、その‘0'の
ビツト列がLSBを含むか否かを検出する。 LSBを含む場合には、引き続いて、上記先頭
アドレスの次のアドレスのバイトのビツトパター
ンに基づいて第２の変換表を参照し、対応する変
換値を読み出す。その変換値が“０”の場合には
次のアドレスのバイトについて同じ処理を続行
し、変換値が“０”と異なる値の場合には処理を
停止し、その時のバイトのアドレスを‘0'のビツ
ト列の末尾バイトのアドレスとし、その時の変換
値から‘0'を含む最終バイト中のMSBから連続
する‘0'の数を検出し、これらの値から連続する
‘0'の総数を求める。 (e) 本発明の実施例 以下本発明の実施例を図面によつて詳細に説明
する。 第１図は、本発明に係る空きスペース検索方法
の一実施例に用いた処理装置の構成を示すブロツ
ク図、第２図は上記一実施例で用いた第１および
第２の変換表の構成例を示す図、第３図は本実施
例の空きスペース検索方法を示すフローチヤート
である。 第１図において、１は主記憶装置、２は変換表
で、第１の変換表２−１と第２の変換表２−２を
有する。３は中央処理装置（CPU）、４は主記憶
制御部、５は命令制御部、６は演算処理部、６−
１はレジスタ、７は直接記憶装置（DASD）をそ
れぞれ示す。 本実施例は、DASDの使用状態を示すビツトマ
ツプを、第１の変換表２−１を参照して‘0'のビ
ツト列が始まる先頭バイトのアドレスと、そのバ
イト中の‘0'の個数を検出し、次に、第２の変換
表を参照して、‘0'のビツト列が終わる末尾バイ
トのアドレスと、そのバイト中の最高位ビツト
（MSB）から連続する‘0'の個数を検出し、これ
らの値から連続する‘0'の総数とその位置を知
り、空き領域を検索しようとするものである。 ８ビツトからなるバイトのビツトパターンは、
256種類存在する。第２図ａ，ｂは、いずれもこ
の256種類のビツトパターンに対する変換値を示
す表であり、バイトの値を16進数で表した場合の
上位桁を縦軸に、下位桁を横軸にとつてある。 まず第１の変換表２−１を、第２図ａにより説
明する。第１の変換表２−１は、１つのバイトを
最高位ビツトから見て最初に現れる‘0'の数を示
す。例えば、16進数の“CB”というバイトに対
するビツト列は、‘11001011'である。これには
ビツト‘0'が１個以上連続するビツト列は２つ存
在する。第１の変換表２−１は、この‘0'のビツ
ト列のうち、MSBから見て最初に出現するもの
の‘0'の個数を示す。 更に、このMSBから見て最初に出現する‘0'
のビツト列が、最下位ビツト（LSB）を含む場
合には、‘0'の個数を16倍した値を格納してお
き、LSBを含むことを容易に識別できるように
してある。例えば、“80”なるバイトのビツトパ
ターンは、‘10000000'であり、この‘0'の個数
は７個である。これを16進数表示すると“07”で
あるが、16倍した“70”という値を格納してあ
る。このような値にしたのは、１バイト中の‘0'
の個数として出現することはあり得ない値であ
り、また、識別が容易であり、しかも、この値を
４回右シフトすることにより、簡単に真の値を得
られることによる。従つて16倍する以外に、
MSBを‘1'にする等の方法を、LSBを含むこと
を示すために用いることができる。 上記‘0'のビツト列がLSBを含むビツトパター
ンは、全部で８種類のみであり、図に“Ｎ×16”
として示してある。 第２の変換表２−２の基本的な性格は、MSB
から連続する‘0'のビツト数を、ビツトパターン
対応に示す表である。但し、全ビツトが‘0'即ち
16進数の“00”は、本来は“８”であるが、これ
を“０”としてある点、および、MSBが‘1'即
ち“80”以上の値の場合は、本来の値は“０”で
あるが、これを“８”としてある。換言するな
ら、MSBが‘0'の場合には０〜７を、MSBが‘
1'の場合は８を割り付けたものである。 このように構成したのは、本実施例において上
記２つの変換表を用いておこなう処理が、検出し
た変換値が‘0'の場合には、引き続いて次のバイ
トに対して同じ処理を続行し、‘0'以外の値の場
合には、そのバイトに対する変化値とそのバイト
のアドレスを返して処理を停止するためである。
この点につていは後述する。 次にこのように構成した２つの変換表を用いた
本実施例の処理を、第２図ａ，ｂおよび第３図を
参照しながら説明する。 上記２つの変換表を参照して行う本実施例にお
ける変換処理に対する命令を、説明を簡単にする
ため、翻訳テスト命令と称することとする。 この翻訳テスト命令は、検査対象バイトのアド
レスと、変換表を指定して実行する。 従つて、DASDの空き領域を検索するには、ま
ず、空き領域を管理するためのビツトマツプの先
頭アドレスと、第１の変換表２−１を指定して、
上記翻訳テスト命令を実行する。例えば、下記第
１表に示すようなビツトマツプがあるとする。

【表】 このビツトマツプでは、バイト０にはMSB側
に３個の連続した‘0'即ち空きが存在し、バイト
１からバイト３間にかけて14個の‘0'即ち空きが
連続する。 このようなビツトマツプに対して、第１の変換
表を指定して翻訳テスト命令を実行すると、まず
ビツトマツプの先頭バイトに、バイトポインタが
設定される〔第３図(1)参照〕。 上記第１表の先頭バイトの‘11001011'は16進
数にて示すとCBであり、第２図ａに示す第１の
変換表を参照して、変換値として“２”が得られ
る〔第３図(2)参照〕。 このように変換値が“０”以外の値であつた場
合には、検査対象バイトが‘0'を含むことを示
す。つまり、ビツトマツプにおいて空き領域を示
すバイトが検出されたこととなる。 もし、変換値が“０”の場合には、そのバイト
には‘0'即ち空き領域が存在しないので、次のバ
イトに対して、翻訳テスト命令を続行する。そし
て、256バイト全部が“０”であれば〔第３図(3)
参照〕、マツプポインタを256進めて〔第３図(4)参
照〕、次の256バイトに対して翻訳テスト命令を続
行する。 上記の如く変換値が“２”であれば、翻訳テス
ト命令を停止し、このバイト中の‘0'のビツト列
が、次のバイトに連続しているか否かを、変換値
が16より大きいか否かで判定する〔第３図(5)参
照〕。 この例の場合には、変換値が“２”であつて、
16より小さいので、この“２”を第１図に示すレ
ジスタ６−１に入力し、この値を‘0'が連続する
値、つまり空き領域の大きさとして検出〔第３図
(6)参照〕するとともに、このバイトのアドレスを
検出して、処理を終了する。 上記レジスタ６−１の値、即ち“２”は、当該
バイトの一番左側に２個の空き領域のあり、しか
もこの‘0'のビツト列はLSBを含まないこと、つ
まり、次のバイトに連続していないことを示す。 もし変換値が16より大きいもの、例えば
11111000なるバイト〔16進数で“F8”〕の場合に
は、変換値は第２図ａより“３×16”である。こ
の場合には、変換値を16にて割り、その値の
“３”を“０”の個数として、レジスタ６−１に
入力する。〔第３図(7)参照〕。即ち“×16”として
示す値は、上記した如くこのバイトの‘0'のビツ
ト列がLSBを含むこと、即ち次のバイトに‘0'の
ビツト列が連続していることを示す。従つて、こ
の場合には次のバイトを調査することが必要であ
り、マツプポインタを１バイト進めて〔第３図(8)
参照〕、第２の変換表２−２を用いて翻訳テスト
を続行する。 例えば、前述した“F8”に16進数“1B”〔ビツ
ト列は‘00011011'〕が続くとすると、第２図ｂ
より“３”が求まる。 変換値は“０”でないので、翻訳テスト処理は
ここで停止し〔第３図(10)参照〕、変換値が“８”
か否か、つまり、MSBから連続する‘0'のビツ
ト列があるか否かを検査し〔第３図(11)参照〕、
“８”ではないので、MSBから連続する‘0'のビ
ツト列が存在し、その個数は３個である。 そこで、先にレジスタ６−１に格納した“３”
と、第２の変換表から得られた“３”とを加算し
て、空きビツト数として“６”が求まる〔第３図
（13）参照〕。なお、この場合、第２の変換表を用
いた翻訳テスト処理で、変換終了バイトと変換開
始バイトは同一であるので、この２つのバイトの
アドレスの差は“０”であり、第３図（13）の式
の第２項は“０”となる。 上記第３図(11)の検査で、変換値が“８”の場合
には、MSBから連続する‘0'のビツト列が存在
しないことを示すので、変換値を“０”に置き換
えて〔第３図(12)参照〕、第３図（13）の処理をお
こなう。 第３図(10)の検査で、得られた変換値が“０”で
あれば、このバイトは全ビツト‘0'であることを
示し、なお次のバイトに‘0'が続く可能性がある
ので、次のバイトに対して翻訳テスト処理を続行
する。そして、256バイト全部が“０”に変換さ
れた場合には、レジスタ６−１の値に256バイト
分の‘0'の個数、即ち、256×８を加算し、これ
を改めてレジスタ６−２に格納しておき〔第３図
（14）参照〕、マツプポインタを256バイト進めて、
第２の変換表を参照した翻訳テストを、次の256
バイトに対して続行する〔第３図(9)参照〕。 以上述べた如く、本実施例では第１の変換表を
用いて翻訳テスト命令を実行し、‘0'のビツト列
が始まる先頭バイトの位置と、その‘0'の個数を
見出し、この‘0'のビツト列がLSBを含む場合に
は、次のバイトから第２の変換表を用いて再び翻
訳テスト命令を実行し、‘0'のビツト列が終了す
るバイトを検出して、そのアドレスとそのバイト
のMSBから連続する‘0'のビツト数を求め、こ
れらの値から、ビツトマツプにおける‘0'のビツ
ト列の位置と、連続する‘0'のビツト数を検出す
る。 なお、この翻訳テスト命令は、コード変換のた
めに一般的に装備されている命令である。例えば
文字コードとして、ASCIIコードとEBCDICの２
つが主として使用されており、これを相互に変換
する必要がしばしば出現する。翻訳テスト命令は
このような場合に使用されるもので、予め準備さ
れた変換表と変換対象領域の先頭アドレスを指定
して実行することにより、１バイトを１ステツプ
で変換値を検出する事ができる。更にこの命令
は、前述したように、変換値が“０”の場合には
引き続いて次のバイトを処理し、変換値が“０”
以外の場合に、そのバイトのアドレスと変換値を
レジスタに格納して、処理を停止する。 本発明は翻訳テスト命令の上記性質を利用した
ものであつて、第１の変換表は、ビツトパターン
対応に、中に含まれる‘0'の個数を示すようにし
たことにより、‘0'を含むバイトに遭遇すると、
処理を停止して、そのバイト中の‘0'の個数とア
ドレスを返す。従つて、‘0'を含むバイトを１命
令で検知することができる。 第２の変換表は、全ビツトが‘0'の場合には変
換値を“０”とし、それ以外を“０”以外とした
ことにより、この変換表を参照して翻訳テストを
実行した場合に、‘1'を含むバイトを検出すると
処理を停止する。従つて、‘0'のビツト列が終了
するバイトを１命令で検知することができる。全
ビツトが‘0'のときの変換値を“８”の変わりに
“０”としたのは、この場合には‘0'のビツト列
がなお次のバイトに連続する可能性があるので、
処理を続行させるためである。 更に、この変換表において、変換値が“１”な
いし“７”の場合は、MSBから連続して‘0'が
存在し、且つ、そのバイトで‘0'のビツト列が終
了することを示す。また、MSBが‘1'の場合に
は、‘0'を含む場合には出現しない値であつて、
処理を停止できる値とするため、“８”以上の値
としたものである。 このようにしたことにより、従来は１バイトの
値を検出するため、前述したようにシフト命令と
比較命令だけで16ステツプを要したものを、本発
明では２種類の変換表を用いることにより、翻訳
テスト命令を１ステツプで可能となり、この翻訳
テスト命令を利用して、第３図により説明した手
順で高速且つ容易に空き領域を検出できる。 (f) 発明の効果 以上、詳細に説明したように、本発明の空きス
ペース検索方法は、２種類の変換表を用いて高速
に空きスペースの検索が行われ、DASDの記憶領
域を管理するのに利点の多いものである。

【図面の簡単な説明】

第１図は本発明の空きスペース検索方法の一実
施例に用いたシステム構成を示すブロツク図、第
２図は上記一実施例の第１および第２の変換表の
構成を示す図、第３図は上記一実施例の空きスペ
ース検索方法のフローチヤートである。 図において、２は変換表、２−１，２−２は第
１および第２の変換表、３は中央処理装置、６−
１はレジスタ、７はDASDをそれぞれ示す。

Claims (1)

1. 【特許請求の範囲】 １ 直接アクセス記憶装置と該直接アクセス記憶
   装置の記憶領域使用状況を記憶領域対応に‘0'ま
   たは‘1'のビツト値で示すビツトマツプを具備す
   る処理装置において、前記ビツトマツプから前記
   直接アクセス記憶装置の空きスペースを検索する
   方法であつて、 ８ビツトからなるビツト列を最高位ビツト側か
   ら見たとき、最初に現れる‘0'が１個以上の連続
   したビツト列の‘0'の数と、その‘0'のビツト列
   が最下位ビツトを含むか否かを、ビツトパターン
   対応に示す第１の変換表と、 前記ビツト列の最高位ビツトが‘0'の場合に
   は、最高位ビツトから連続する‘0'の数が８個の
   ときは“０”を、１ないし７個のときは最高位ビ
   ツトから連続する‘0'の数を、また、最高位ビツ
   トが‘1'の場合にはその旨を、ビツトパターン対
   応に示す第２の変換表を設け、 前記ビツトマツプの指定したアドレスのバイト
   のビツトパターンに基づいて前記第１の変換表か
   ら対応する値を読みだし、読み出した値が“０”
   の場合には次アドレスのバイトについて該処理を
   繰り返し、読み出した値が“０”以外の場合には
   処理を停止し、当該バイトのアドレスを‘0'を含
   むバイト列の先頭アドレスとして記憶するととも
   に、得られた変換値からそのバイト中の‘0'のビ
   ツト列が最下位ビツトを含むか否かを知り、 最下位ビツトを含まない場合には、その変換値
   を連続する‘0'の個数として検出し、 最下位ビツトを含む場合には、前記先頭アドレ
   スの次位のアドレスのバイトのビツトパターンに
   基づいて前記第２の変換表から対応する値を読み
   だし、読み出した値が“０”の場合には、次のア
   ドレスのバイトについて該処理を繰り返し、読み
   出した値が“０”と異なる場合には処理を停止し
   て、その時の検査対象バイトのアドレスを‘0'を
   含むバイト列の最終アドレスとして記憶するとと
   もに、該バイトに対する変換値から該バイト中の
   ‘0'の個数を知り、 これら先頭アドレスおよび最終アドレスのバイ
   ト中の‘0'の個数と、両アドレスの差に基づい
   て、連続する‘0'の個数を求め、 得られた結果から空き領域の大きさおよび該空
   き領域の位置を知ることを特徴とする空きスペー
   ス検索方法。