JPH05216593A - 間接アクセス記憶装置 - Google Patents

Abstract

(57)【要約】 【目的】 書き込み動作を最短時間で完了させることに
より書き込み性能を最適化させると共に読み出し性能を
最適化させること。 【構成】 インテリジェントディスクコントローラ(以
下ＩＤＣ)と組み合わされた回転ディスク記憶メモリか
らなる間接アクセスディスク記憶装置である。このＩＤ
Ｃは、回転ディスクメモリのどの記憶場所が利用可能で
あるかを決定し、他の利用可能な記憶場所のアクセス時
間と比較して最短時間でアクセスできる記憶場所を利用
可能記憶場所の中から選択することにより、データパケ
ットを記憶させるための要求に応答する。ＩＤＣは、そ
の選択を動的に行う。即ち、回転ディスクメモリの記録
ヘッドの現在の位置を監視し、利用可能な記憶場所の記
録を検索して、最適な位置を選択する。ＩＤＣは次いで
そのデータパケットを回転ディスクメモリ上に記憶させ
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、インテリジェントディ
スクコントローラと組み合わされた回転ディスク記憶メ
モリからなる間接アクセスディスク記憶装置に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】従来、
回転ディスク記憶装置のような記憶媒体上にデータを編
成するタスクは、ホストプロセッサのファイルシステム
によって行われて来た。システムレベルのソフトウェア
は大域情報を利用する上で理論的長所があるが、最適化
に対する障害がいくつか残されている。ファイルは、局
所化されたアドレス範囲に入るように個々に最適化され
るが、大域的ロード均衡化(load balancing）またはフ
ァイルシステム配置は、しばしばシステム管理責任者に
委ねられ、このシステム管理責任者はおそらく、ディス
クの低レベル構造を並べ換える「OSF」論理ボリューム
マネージャ(Logical Volume Manager）等のツールを用
いてこれを行うと思われる。さらに、SCSI−II(小型コ
ンピュータシステムインタフェースII）等の新しいディ
スクインタフェースによって抽象ディスクモデルが出さ
れ、ファイルシステムがこの種の決定を行うことがます
ます困難となっている。

【０００３】ファイルシステムは(それがオペレーティ
ングシステムの部分であるか、データベースシステムで
あるか、あるいは他の何らかのアプリケーションである
かにかかわらず）、大域システム状態に関する情報を、
その制御装置より多く有しているということ、及び、こ
の情報が、スケジューリング、データ配置、キャッシュ
記憶、及び先取り(プリフェッチ）方針に関する選択を
改善するために使用すべきものであるということは、従
来技術で知られている。例えば、4.2BSDファイルシステ
ム(McKusick84）は大域情報を利用するが、非矩形ディ
スクを扱うための現在のディスク構造についての知識情
報が欠けている。このようなシステムには、ディスク性
能特性のきめ細かい制御、及びその特性についての改善
された知識情報を、制御装置レベルで得ることができる
という長所が欠如している。

【０００４】ディスク及びディスク制御装置から切り離
されたホストプロセッサは、ディスク制御装置より最適
データレイアウトについての決定能力が劣る。このよう
なホストプロセッサは、ディスク制御装置設計に本来存
在する部分でありかつデータレイアウトに関する正しい
決定にとって極めて重要であるディスクの幾何学諸元及
び性能特性に関する知識情報に欠けるものである。現在
のインタフェース規格の下では、この知識情報をホスト
プロセッサに伝達するのに大きな困難が伴う。ディスク
リソースを割り当てる際のスケジューリング決定にとっ
て重要な現在のディスク状態(現在のヘッド位置を含
む）についての詳細な知識情報は、ホストプロセッサよ
り当然ディスク制御装置で多く得られる。にもかかわら
ず、従来技術においては、スケジューリング決定及びデ
ータ配置決定を行うのにホストプロセッサのファイルシ
ステムを使用することが教示されている。

【０００５】

【課題を解決するための手段】本発明は、「ディスク制
御装置は、最適データ配置決定をファイルシステムより
良好に行うことができるので、データ配置を決定するの
により好適である」という前提に基づく間接アクセスデ
ィスク記憶装置である。本発明の間接アクセスディスク
記憶装置は、インテリジェントコントローラプロセッ
サ、反転テーブル及び、間接機能(indirection)を大き
く活用して、高性能及び信頼性の高い動作という目的を
達成すると共に、ファイルシステムと記憶装置との間の
協動関係を強化する現行のディスクインタフェースに拡
張性を提供するものである。

【０００６】本発明は、ディスク制御装置がメタデータ
更新なしに全ての書き込み動作毎にディスクの内容を並
べ直すことを可能にする。これは、論理アドレスをラベ
ルにマップする割り当て記録として間接機能テーブルを
ディスク制御装置のメモリに保持することによって達成
される。論理アドレスは、データブロックを識別するた
めにホストプロセッサのファイルシステムによって使用
される。ラベルは、データブロックが記憶されているデ
ィスク上の記憶場所を識別するためにディスク制御装置
によって使用される。割り当て記録が失われた場合の故
障回復に備えて、データブロックは、論理アドレス、現
在時刻スタンプ、及びコミット(commit：委任)フラグと
共に、データパケットにパッケージ化してディスク上に
記憶される。パケットにおいてコミットフラグを使用す
ることにより、最小単位の(atomic）のマルチブロック
更新を行うことができる。

【０００７】この間接アクセスディスク記憶装置によ
り、ディスク性能が改善されると共に、大容量記憶装置
に通常固有である待ち時間による性能への影響を少なく
することができる。本発明は、他の利用可能な記憶場所
のアクセス時間に比較して最短の時間でアクセスするこ
とができる利用可能な記憶場所へデータパケットを書き
込む。その結果、書き込み動作が最短時間で完了し、書
き込み性能が最適化される。書き込み性能を最適化する
ことにより、読み出し性能も最適化される。本発明は、
利用可能な記憶場所の最小のプールを維持することによ
り、書き込みの発生時に、すぐ近くのセグメントが利用
可能であることを確実化する。また本発明は、読み出し
性能を改善するために、アイドル期間中にディスク上の
データをリシャッフル(reshuffle)する。

【０００８】本発明のその他の側面及び利点は、本発明
の原理を解説する図面に関連してなされる以下の詳細な
説明により明らかになるであろう。

【０００９】

【実施例】上述のように、本発明は、ホストプロセッサ
のファイルシステムによって使用される論理アドレスを
実ディスクアドレスとしてではなくデータ識別子として
扱い、データを独自の最適化方針に基づきディスク上に
記憶する。これを行うために、本発明では、ホストプロ
セッサの記憶媒体及びオペレーティングシステムとは別
個に、ディスク制御装置のメモリに独自のメタデータ構
造を維持する。これらのメタデータ構造は、頻繁に更新
され、本発明が、利用可能な記憶場所を識別する利用可
能ラベルに、ホストの論理アドレスをマップすることを
可能とする。実マッピングを含む割り当て記録データ構
造337を図４に示す。図５に示す使用記録データ構造317
は、ワード長が回転ディスク記憶装置における記録ヘッ
ドの個数を反映する記録ワードを使用することにより、
利用可能な記憶場所を識別する利用可能ラベルを迅速に
見つけることを可能にする。図６に示すデータパケット
340は、故障回復のために、回転ディスク記憶装置上の
データをカプセル化したものである。

【００１０】一般にホストプロセッサが１ブロックのデ
ータを記憶するよう要求する場合、本発明では、使用記
録データ構造を走査して、他の利用可能な記憶場所のア
クセス時間と比較して最短時間でアクセスすることがで
きる記憶場所を識別する指定ラベルを、利用可能ラベル
の中から選択する。次に、そのデータブロックを含むデ
ータパケットはその選択された記憶場所に記憶される。
そして、その選択された記憶場所を識別する指定ラベル
は、割り当て記録データ構造中における、論理アドレス
によって指定された記憶場所に、記録される。指定ラベ
ルは、以前に割り当て記録データ構造中の論理アドレス
に関連づけられた古いラベルとは全く無関係なものであ
る。データの書き込み後、その論理アドレスと以前に関
連づけられた古いラベルはそれ以降のデータ記憶のため
に利用可能となる。

【００１１】ホストプロセッサからのデータブロックの
ストリームは、データパケットのシーケンスとして書き
込まれる。各パケットには、一塊り(chunk)のデータ、
その論理ブロックアドレス、シーケンス番号、及びその
パケットで最小単位のシーケンスが終わるのかどうかを
示すフラグが含まれる。この特別な情報により、本発明
は、システム障害から回復することができ、複数のブロ
ックオブジェクトについての最小単位の更新を提供する
ことができる。

【００１２】ホストプロセッサからのデータ記憶要求の
直後において記憶場所が必ず利用可能となるように、本
発明では、以降の割り当てのために記憶装置の一部をリ
ザーブする。データ記憶要求の直後に利用可能な記憶場
所が見つかる可能性は、利用可能なセグメントの数が減
少するにつれて減少する。しかしながら、優れた性能を
達成するためにリザーブする必要のある記憶部の容量は
驚くほど僅かである。本発明においては、この記憶装置
のリザーブ率を５パーセントに保った場合に、公称ディ
スクバンド幅の約２分の１の速度で安定したスループッ
トを得ることが可能となる。リザーブ率を50パーセント
に保った場合には、本発明においては、公称ディスクバ
ンド幅に近い速度で安定したスループットを得ることが
可能となる。これらのスループットに関する数値は、転
送されるブロックがシーケンシャルであるかランダムで
あるかには無関係である。

【００１３】図２は実施例の動作をより詳細に図解した
ものである。ディスクコントローラプロセッサ124は、
命令メモリ120に記憶されたプログラム命令を実行する
ことにより動作する。ホストプロセッサ102は、SCSIイ
ンタフェース(小型コンピュータシステムインタフェー
ス）を介してディスクコントローラプロセッサ124と通
信する。ホストシステムは、SCSIインタフェース108を
用いて間接アクセスディスク記憶装置100がデータ101を
記憶するよう要求する。次に、ホストシステムは、論理
アドレス125及びデータブロック127よりなるデータパケ
ットをSCSIインタフェース108を介してディスクコント
ローラプロセッサ124へ送る。

【００１４】その後、ディスクコントローラプロセッサ
124は、図２に示す割り当て命令107を実行する。割り当
て命令は、図１に示す記憶媒体104のどの記憶場所105が
データ記憶に利用可能であるかを判断すると共に、他の
利用可能な記憶場所のアクセス時間と比較して最短時間
でアクセスすることのできる記憶場所を、利用可能な記
憶場所の中から選択する。ディスクコントローラプロセ
ッサ124は、図１に示すように、割り当て命令を実行し
ている間にデータ／ディスクサーボ制御装置150と通信
を行って磁気記録ヘッド106の現在のヘッド位置111を監
視する。ディスクコントローラプロセッサは、現在のヘ
ッド位置111に関するこの情報を用いて、他の利用可能
な記憶場所のアクセス時間と比較して最短時間でアクセ
スすることができる記憶場所を、利用可能な記憶場所の
中から選択する。

【００１５】次に、ディスクコントローラプロセッサ12
4は、記録命令112を実行して、図３に示す記憶媒体104
上の選択された記憶場所113にデータパケットを記録す
る。(割り当て命令107及び記録命令112については、本
実施例の説明の最後の「補足説明Ｉ：メイン疑似コード
リスト」中のルーチンを参照しつつ以降で詳細に説明す
る。）次に、ディスクコントローラプロセッサ124は、
図１に示す制御バス114及びデータバス116を介して適切
な信号をデータ／ディスクサーボ制御装置150に送るこ
とにより、データパケットを記憶媒体104に記憶させ
る。

【００１６】この好適実施例において、記憶媒体104
は、図１に示す複数のプラッタを有する回転ディスクメ
モリである。図３に示す記憶場所105は、プラッタ104の
うちの１つの表面上の同心リングのセグメントよりな
る。各プラッタ共、これと同様の構成を有する。これら
の同心リングはシリンダとして知られている。各々の特
定セグメントは全て、その盤面、シリンダ位置、及び回
転位置によって探し出すことができる。複数の磁気記録
ヘッド106は一つにまとめられ、各プラッタの表面に１
つずつ磁気記録ヘッド106が割り当てられるようになっ
ている。このように一つにまとめられた磁気記録ヘッド
106は、一体的に移動し、プラッタ104の半径方向に走査
する。この一体的な磁気記録ヘッド106が各プラッタの
表面を走査する際にプラッタ104が回転することによ
り、磁気記録ヘッド106が記憶場所105にアクセスするこ
とが可能となる。既に磁気記録ヘッド106のうちの１つ
の真下にある記憶場所であれば、迅速にアクセスするこ
とができる。ある特定の記憶場所が磁気記録ヘッド106
のうちの１つの真下にない場合には、その特定の記憶場
所へのアクセスには、その特定の記憶場所が磁気記録ヘ
ッド106のうちの１つの真下に来るように、ディスクが
回転して磁気記録ヘッドが走査するのを待つ間遅延が生
じる。この遅延のため、現在のヘッド位置111の近くに
ある記憶場所は、現在のヘッド位置111から離れている
記憶場所より比較的短時間でアクセスすることができ
る。この遅延は、待ち時間というさらに大きな概念と関
係がある。

【００１７】ディスク書き込みの前後において、待ち時
間は、ディスク書き込み動作を実行するために費やされ
る時間である。これには、磁気記録ヘッド106を正しい
位置へ移動させるための時間(シーク時間として知られ
ている）と、ディスクが正しい位置へ回転するのに要す
る時間(回転待ちとして知られている）と、データを実
際に転送する時間とが含まれる。この待ち時間の概念
は、種々の回転ディスク記憶装置と共に他の大容量記憶
装置にも適用可能なものである。ディスクコントローラ
プロセッサ124は、磁気記録ヘッド106の現在のヘッド位
置111を監視し、割り当て記録132を検索することによ
り、他の利用可能な記憶場所のアクセス時間と比較して
最短時間でアクセスすることができる記憶場所を、利用
可能な記憶場所の中から選択する。このような配置決定
は動的に行われなければならない。これは、現在のヘッ
ド位置111が、ディスクプラッタ104の回転及び磁気記録
ヘッド106の移動により絶えず変化しているためであ
る。

【００１８】このようにして、本発明によれば、回転デ
ィスク記憶装置に通常固有であるシーク時間及び回転待
ちによる性能への影響を効果的に低減することができ
る。これは延いては待ち時間の性能への影響を小さくす
ることにつながる。本発明は、待ち時間を有する他の大
容量記憶装置にも適用することができる。

【００１９】上述のように、ある所与の瞬間において、
各磁気記録ヘッド106は、或る１つの記憶場所の真上に
位置し、その記憶場所へのアクセスが可能となる。その
ような各瞬間においては、記録ヘッド106群の中のどの
１つを用いてもよく、各プラッタ面が１つの記憶場所を
１セットの記憶場所に提供する。そして、その同じ瞬間
には、その１セット内のどの１つの記憶場所でもアクセ
スすることが可能である。磁気記録ヘッド106が一つに
まとめられているので、そのような１セットの記憶場所
の各要素は、各々対応するプラッタ面に関して同じシリ
ンダ上の同じ回転位置にある。プラッタ104が積み重ね
られているので、そのような１セットの記憶場所の各要
素は、多数のプラッタ104を貫通して縦方向に延びるカ
ラム内に存在する。このため、そのような１セットの記
憶場所は、１カラム群の記憶場所123と呼ばれる。例え
ば、３２ＫＢのトラック、１９のデータ面、及び４ＫＢ
の記憶場所サイズを有するディスクの場合には、１９の
各記憶場所を８カラム群で編成した１５２の記憶場所を
１シリンダ中に有することになる。

【００２０】図５は、記録ワードアレイ325及びラベル
グループ化アドレス索引321を有する使用記録データ構
造317を示すものである。索引中の各ラベルグループ化
アドレスは、図１に示すような或る１カラム群の記憶場
所123に対応する。(図２に示すように、ディスクコント
ローラプロセッサ124は、記憶媒体104上のどの記憶場所
105がデータ記憶に利用可能であり、どの記憶場所がデ
ータ記憶に利用可能でないかを示す使用記録117をデー
タメモリ121中に維持する。）図５は、アレイ325中の各
記録ワードの記憶場所がラベルグループ化アドレスのう
ちの１つによって索引付けされることを示している。こ
のようにして、使用記録データ構造317は、ディスクコ
ントローラプロセッサ124がラベルグループ化アドレス
索引321のうちの１つを用いて記録ワードアレイ325のう
ちの対応する１つを得ることによって使用記録117にア
クセスすることができるように構成される。

【００２１】アレイ325中の各記録ワードは多数のビッ
トポジション327を有する。各ビットポジション327にお
けるエントリは、記憶媒体104の記憶場所105のうちの１
つの利用可能性を示す。各々の記憶場所105はラベルに
よって識別される。各ラベルはラベルグループ化アドレ
ス及びビットポジションよりなる。ラベルのラベルグル
ープ化アドレス部分は記憶場所105のシリンダ位置及び
回転位置を指定する。ラベルのビットポジション部分は
その記憶場所のプラッタ面を指定する。これらのシリン
ダ位置、回転位置、及びプラッタ面部分は、本実施例の
説明の最後の「補足説明Ｉ：メイン疑似コードリスト」
に示す「addr to cyl(request.address)」、「addr
to sect(request.address)」、及び「addr to surf
(request.address)」にそれぞれ対応する。使用記録デ
ータ構造317は、前記「補足説明Ｉ」の次の「補足説明I
I：ページ割り当て構造疑似コードリスト」に示す「fre
e map」に対応する。

【００２２】上述のように、ディスクコントローラプロ
セッサ124は、割り当て命令107を実行して、記憶媒体10
4中のどの記憶場所105がデータ記憶に利用可能であるか
を判断すると共に、他の利用可能な記憶場所のアクセス
時間と比較して最短時間でアクセスすることができる特
定の記憶場所を、利用可能な記憶場所の中から選択す
る。これを実行する際、ディスクコントローラプロセッ
サ124は、現在のヘッド位置111を監視する一方、使用記
録117を検索する検索コード119を実行して、その選択さ
れた記憶場所113を識別する指定ラベルを生成する。検
索コード119は、前記「補足説明Ｉ：メイン疑似コード
リスト」に示す「find free segment()」に対応す
る。

【００２３】検索コード119の実行によって指定ラベル
を生成すると、ディスクコントローラプロセッサは、次
いで記録命令112を実行して、データメモリ121のデータ
バッファ141部に一時記憶されたデータを移動し、デー
タをデータパケット内にカプセル化し、データパケット
全体を記憶媒体104に記憶させる。記録命令112は、前記
「補足説明Ｉ：メイン疑似コードリスト」に示す「do
io(phys req, last)」に対応する。

【００２４】ディスクコントローラプロセッサ124は、
現在時刻133を示す値をデータメモリ121に維持する。こ
の現在時刻133は、データパケットのカプセル化時に、
システム障害の回復のためのバックアップ用として、論
理アドレス125及びデータブロック127と共にデータパケ
ットに入れられる。また、間接アクセスディスク記憶装
置100は、コミットフラグをデータパケットに入れるこ
とにより、任意サイズの最小単位データ更新に備える。
このコミットフラグは、システム障害の回復中に割り当
て記録を復元している際に、下位のシーケンス番号を有
する全ての更新が適用されるべきである、ということを
示す。このコミットフラグはまた、間接アクセスディス
ク記憶装置100が複数の同時トランザクションを行うこ
とを可能にするものである。図６は、データブロック34
3、論理アドレス345、タイムスタンプ347及びコミット
フラグ349を含むデータパケット340を示す。

【００２５】割り当て命令107には、検索コード119の他
に、マッピングコード129と更新コード115も含まれる。
ディスクコントローラプロセッサは、マッピングコード
129を実行することにより、指定ラベルと記憶されてい
るデータ101の論理アドレス125との間の対応関係の割り
当て記録132をデータメモリに121に記憶させる。図４
は、ラベルアレイ311よりなる割り当て記録データ構造3
37を示す。アレイ中の各ラベルの記憶場所は、論理アド
レス索引331によって索引付けされる。このように、割
り当て記録データ構造337は、ディスクコントローラプ
ロセッサ124が論理アドレス125及び論理アドレス索引33
1を用いることにより割り当て記録132にアクセスしてラ
ベルアレイ311に指定ラベルを記憶させることができる
ように、構成される。マッピングコードは、ラベルアレ
イ311中のこの記憶場所に既に古いラベルがあればそれ
を上書きして、指定ラベルを新しいラベルとして記憶さ
せる。マッピングコード129は前記「補足説明Ｉ：メイ
ン疑似コードリスト」に示す「store loge map(start
address, request)」に対応する。

【００２６】データが選択された記憶場所に記憶される
と、ディスクコントローラプロセッサ124は、更新コー
ド115を実行して、その選択された記憶場所113が利用不
可能になったことを示すエントリによって使用記録117
を更新する。これは、指定ラベルのラベルグループ化ア
ドレス部分を用いて、記録ワードアレイ325中の対応す
る記録ワードを探し出すことによって行われる。次に、
指定ラベルのビットポジション部分を用いて、そのエン
トリについての対応する記録ワード中のビットポジショ
ンを探し出す。これは、前記「補足説明Ｉ：メイン疑似
コードリスト」に示す「allocate」によって行われる。

【００２７】更新コード115もまた、論理アドレスを用
いて、マッピングコードが古いラベル上に指定ラベルを
上書きする前に、ラベルアレイ311中の古いラベルを探
し出す。次に、更新コード115は、古いラベルを用い
て、古いラベルによって識別される記憶場所が利用可能
になったことを示すエントリで、使用記録117を更新す
る。これは、古いラベルのラベルグループ化アドレス部
分を用いて、記録ワードアレイ325中における対応する
記録ワードを探し出すことにより行われる。次に、古い
ラベルのビットポジション部分を用いて、そのエントリ
についての対応する記録ワード中のビットポジションを
探し出す。これは、前記「補足説明Ｉ：メイン疑似コー
ドリスト」に示す「free」によって行われる。

【００２８】上述のように、割り当て命令107及び記録
命令112は、ホスト102からのデータを記憶するために、
ディスクコントローラプロセッサ124によって実行され
る。また、間接アクセスディスク記憶装置100は、アイ
ドル期間(ホストが間接アクセスディスク記憶装置100へ
要求を出していない比較的長い期間）中に記憶媒体を再
編成する。これは、ディスクコントローラプロセッサ12
4によって行われ、まず読み取り命令139を実行して記憶
媒体からデータバッファ141へデータ101を転送する。次
に、ディスクコントローラプロセッサ124は割り当て命
令107及び記録命令112を実行して、データバッファ141
中のデータ101を記憶媒体104へ戻す。これについては、
以下に示す「補足説明III：ディスクシャッフリング疑
似コードリスト」において詳細に述べられている。

【００２９】上記で詳細に説明したように、本発明によ
る間接アクセスディスク記憶装置は、ティスク性能を改
善することができ、かつ回転ディスク記憶装置に通常特
有である待ち時間による性能への影響を効果的に低減す
ることができるものである。本発明の上述の好適実施例
の説明から多くの修正態様を得ることが可能なことは明
白であろう。特許請求の範囲は、本発明の思想及び範囲
に入る全ての修正態様を包括することを意図したもので
ある。

【００３０】 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊補足説明Ｉ：メイン疑似コードリスト 読み出し及び書き込み要求がホストからコントローラへ
と送られ、且つマッピングルーチンによって物理ディス
ク位置へとマップされるディスクシステムを想定する。
入力される要求には次のものがある。

【００３１】要求＝タイプ（＝読出し又は書き込み）、
サイズ、アドレス ここで、「サイズ」はバイトで表し、「アドレス」はコ
ントローラによってホストに提示されたアドレススペー
ス内にオフセットされたバイトである。

【００３２】又、物理的装置を制御する要求には次のも
のがある。

【００３３】 *********************************************************************** phys＿req ＝｛読出し、書き込み｝、サイズ、シリンダ、面、セクタ、アドレス 、カウント *********************************************************************** ここで、「サイズ」はバイトで表し、「シリンダ」はア
ーム位置のアドレスであり、「面」はアクセスされるデ
ィスク面を識別し、「セクタ」は前記の面上における回
転位置を識別する。「アドレス」とは要求中の最初の論
理アドレスであり、「カウント」とはＩ／Ｏ要求の順序
付けされた識別子（疑似タイムスタンプ又はシーケンス
番号）である。「アドレス」と「カウント」は、故障に
続くマッピングテーブルの再構成を可能にするためにコ
ミットフラグと共に「do＿io」によって装置のメタデー
タ内に組み込まれる。回復は、パワーアップ時に呼び出
される新しいルーチン「restore ＿map」によって実行
される。

【００３４】「nativ ＿io＿perform」は下記のように
変化する。

【００３５】 *********************************************************************** nativ ＿perform ＿io(request) BEGIN //IOが大きすぎないかチェック。これで最小単位の更新が可能になる。

【００３６】 IF request.size > MAX＿IO＿SIZE THEN err := LARGE ＿IO; return FI last := FALSE WHILE request.size > 0 // 作業がある限り以下を実行する。

【００３７】 DO // 論理から物理への変換 phys＿req : = loge＿map(request) phys＿req.address := request.address phys＿req.count :=global＿count IF request.size = phys＿req.size //これは最後の要求か? THEN do＿io(phys＿req, /* last = */ TRUE) ELSE do＿io(phys＿req, /* last = */ FALSE) FI request.size := request.size - phys＿req.size request.address := request.address + request.address OD IF phys＿req.type = WRITE THEN global＿count := global＿count + 1 free＿list() // フリーとなったセグメントを利用可能にする FI END *********************************************************************** 上記において、「loge＿map」は「io＿map」によって戻
されたものと同じ情報を戻し、「free＿list()」は「do
＿io」によって準備されたセグメントのリストをフリー
にし、「do＿io」は下記のものの修正バージョンであ
る。

【００３８】「io＿map」はセグメントアドレスを実際
のディスク位置へとマップする。

【００３９】 *********************************************************************** io＿map(request) BEGIN phys＿req.cylinder := addr＿to＿cyl(request.address) phys＿req.surface := addr＿to＿surf(request.address) phys＿req.sector := addr＿to＿sect(request.address) //サイズをこのトラック上の最大にセットする phys＿req.size := remaining(phys＿req ) //必要ならば要求されたサイズに短縮する IF phys＿req.size > request.size THEN phys＿req.size := request.size FI phys＿req END *********************************************************************** 上記で、「addr＿to＿cyl」、「addr＿to＿surf」及び
「addr＿to＿sect」は、データの記憶場所を決定する数
学的関数である。「remaining()」は、アドレス指定さ
れたセクタと現在のトラックの終端との間のバイト数を
戻す。この数値は、単一の「do＿io」 トランザクショ
ンに転送可能なデータ量の限界を表す。

【００４０】「Loge＿map」は次のように実行される。

【００４１】 *********************************************************************** loge＿map(request) BEGIN IF request.type = READ THEN loge＿read(request) ELSE loge＿write(request) FI END *********************************************************************** 「Loge＿write」は、ヘッド位置と回転位置との双方に
近接したデータ用の記憶場所を選択し、次に、実際の物
理的な記憶場所を決定するために「io＿map」を呼び出
す。選択された記憶場所が同じトラック上の別のフリー
セグメントの直前にあり、要求が１セグメントよりも長
い場合、「loge＿write」は、フリーセグメントのシー
ケンスが使用し尽くされるか、または要求全体が満たさ
れるまで、セグメントを要求に割り当てる。

【００４２】 *********************************************************************** Loge＿write(request) BEGIN request2 := find＿free＿segment() allocate(request2.address) WHILE request2.size < request.size //作業がある限り以下を実行 DO //割り当てられたセグメントに続くフリーセグメントをチェック segment IF NOT available(next(request2)) THEN break FI allocate(next(request2)) request2.size := request2.size + segment＿size OD store＿loge＿map(request.adress,request2) request2.address := request.address phys＿req := io＿map(request2) // 下記注1を参照 phys＿req END *********************************************************************** 注1:「io＿map」は標準ディスク用に書き込まれるの
で、これは、より高レベルのコードが次のトラックのシ
ークを開始するように、トラックの境界の最後を強化し
ようとする。「Loge」システムでは、この機能はページ
割り当て方針によって暗黙のうちに扱われ、「loge＿wr
ite」及び「loge＿read」は「io＿map」の方針に優先す
る。

【００４３】「allocation()」は、セグメントが割り当
てられたという事実を記録するリソース制御ルーチンで
ある。「available()」は、セグメントが割り当てられ
たかどうかを問い合わせる付随機能である。「next()」
は、その引数を回転的に追従する同じトラック上のセグ
メントを戻す。

【００４４】 *********************************************************************** next(request) BEGIN request2.type := request.type request2.size := segment＿size //アドレスモジュロトラックサイズを前進させる request2.address := (request.size + request.address） //「io＿map」がトラックを横切って前進。これは望ましくない。

【００４５】 IF io＿map(request2).sueface !=io＿map(request).sueface THEN request2.address := request2.address - track＿size(request) FI request2.address END *********************************************************************** 「loge＿read」は、データの記憶場所を決定するために
マッピングテーブルを利用する。前述のように、これ
は、２セグメント以上の転送のためにセグメントを合体
しようとする。

【００４６】 *********************************************************************** loge＿read(request) BEGIN request2.address := get＿loge＿map(request.address) request2.size := segment＿size; //作業がある限り、 //又、次のセグメントがその一部である限り、 WHILE request2.size < request.size AND next(request2) := get＿loge＿map(request.address + request2.size) DO request2.size := request2.size + segment＿size OD phys＿req := io＿map(request2) //上記注1を参照 phys＿req.size := request2.size phys＿req END *********************************************************************** 「loge」マッピングテーブルは、セグメント番号によっ
て索引付けされたセグメントのアレイとして記憶され
る。読み出しはアレイをアクセスするだけの簡単な事で
ある。記憶には２つのステップが含まれる。第１に、セ
グメントに以前割り当てられたセグメントをフリーに
し、第２にアレイ内の値を修正する。

【００４７】 *********************************************************************** address map[0:NBLOCK - 1] free1 = list of address get＿loge＿map(address) BEGIN map[address/segment＿size] END store＿loge＿map(start＿adress, request) BEGIN size := request.size request.size := segment＿size index := start＿adress / segment＿size WHILE size > 0 // 作業がある限り次を実行する DO insert(free1, map[index]) map[index] := request request.address := request.address + segment＿size size := size - segment＿size index := index + 1 OD END *********************************************************************** 「insert」は、リスト内に挿入する標準動作である。
「free＿list」は、IOの完了後に呼び出され、このリス
トをパージする: *********************************************************************** free＿list(list) BEGIN WHILE NOT empty(list) //作業がある限り、 DO free(pop(list)) OD END *********************************************************************** 「pop()」と「empty()」は標準スタック動作である。
「free()」はディスクセグメントの割り当て解除を行
う。

【００４８】「find＿free＿segment()」は「Loge」に
よって用いられるセグメント割り当て方針を実行する。
これは、書き込みヘッドによって到達可能なフリーセグ
メント用の連続的な回転位置を検索し、フリーセグメン
ト用のアドレスを戻す: *********************************************************************** range = first, last list = a list of cylinders to search find＿free＿segment() BEGIN search＿pos := next＿rot(current＿rot＿position) WHILE TRUE //無限ループ、区切りの内部で以下を実行 DO(search ＿loop) avail＿time := rot＿time(search＿pos) range := seek＿range(avail＿time) list := search＿list(range, search＿pos) // リストからアドレスを引き出す WHILE cyl := adress＿get(list) DO //最初のフリーセグメントで停止 IF NOT empty(cyl, rot) THEN surface := first＿elem(cyl, rot) break search＿loop OD search＿pos := next＿rot(search＿pos) OD request.type := WRITE request.size := segment＿size request.address := phys＿to＿seg(cyl, surface, rot) request END *********************************************************************** 「next＿rot()」は、セグメントが記憶される、引数に
続く次の回転記憶場所を生む。「current＿rot＿positi
on」が循環する間、「next＿rot()」は、常にその引数
よりも高い位置を生み、まる１回転だけ異なる２つの異
なる回転位置を別のルーチンが区別することを可能にす
る。「rot＿time」は、装置が所定の回転位置に到達す
るのに必要な時間を生む。「seek＿range」は、所定の
時間内に到達可能である最大及び最小のシリンダを生
む。「search＿list()」は、所定の検索位置に対応し、
特定のシリンダ範囲内にある全てのセグメントアドレス
のリストを作成する。

【００４９】シリンダ範囲内のフリーセグメントが枯渇
すると性能が低下するので、「adress＿get()」が不規
則であることが重要である。これは、乱数生成器を使用
してリストからエレメントを除去することによって達成
できる: *********************************************************************** adress＿get(list) BEGIN target := random＿int(1 to size(list)) address := list[target] delete(list, target) address END *********************************************************************** 「do＿io」で記述されているタスクは次のように実行す
るように修正される。

【００５０】 *********************************************************************** metadata = ecc, count, address, commit (= TRUE or FALSE) do＿io(phys＿req, last) BEGIN metadata.address := phys＿req.address metadata.count := phys ＿req.count metadata.commit := FALSE disk＿seek(phys＿req.cylinder, phys＿req.surface, phys＿req.sector) //最後のioを除いて全てをループし、最後のioを処理する。特に下記のよ うな場合には以下の通り実行する。

【００５１】 WHILE phys＿req.size > sector＿size DO disk＿op(phys＿req.type, data＿buffer, metadata) data ＿buffer＋sector＿size phys＿req.size := phys＿req.size - sector＿size IF mod(phys＿req.size, segment＿size) = 0 THEN // 全てのセグメントの後のアドレスを前進させる metadata.address := metadata.address + 1 FI OD // コミットフラグを最後のI/Oだけにセットする IF last THEN metadata.commit := TRUE FI disk＿op(phys＿req.type, data＿buffer, metadata) data＿buffer := data＿buffer + sector＿size phys＿req.size := phys＿req.size - sector＿size END *********************************************************************** このように、データブロックのブロックアドレスとコミ
ット表明子(signifier)は双方とも個々のセグメントと
共に記憶される。要求の最後のセクタでは、コミット表
明子が真であり、これは、転送がうまく完了したことを
示す。

【００５２】マップは、パワーアップ時に次のように動
作するルーチン「restore ＿map」で初期設定される。

【００５３】 *********************************************************************** mappings = block＿addr, address pending = list of mapping restore＿map() BEGIN FOR i := 0 TO NBLOCK - 1 //mapを空にする DO map[i] := BAD＿BLOCK OD FOR addr := 0 TO NDADDRS - 1 //全ディスクアドレスをフリーにする DO free(i) OD max＿commit := 0 FOR addr := 0 TO NDADDRS - 1 //全ディスクアドレスをチェックする DO metadata := get＿meta＿data(addr) process＿md(metadata, address) 0D FOR i := 0 TO NBLOCK - 1 DO //マップ内の全てのセグメントを割り当て通りにマークする IF map[i] ！= BAD＿BLOCK THEN allocate(i) FI OD END *********************************************************************** 「Get＿meta＿data()」は、特定の高レベルのディスク
アドレス用のメタデータを読み出す。単一のI/O 動作で
メタデータのトラック価値全体を読み出し、以降の要求
のために情報をキャッシュすることは「get ＿meta＿da
ta(」)にとって簡単な最適化である。

【００５４】「Process＿md()」は、メタデータエント
リのリストを走査し、それに従ってマップを更新する。
適正に動作するには、既にコミットされていることが既
知であるマッピング、すなわち既にコミットされている
ことが既知である動作のシーケンス番号よりも小さいシ
ーケンス番号を有するマッピング、または実際のコミッ
トフラグを有するマッピングだけを挿入しなければなら
ない。ＩＯサイズの限界により、未処理の要求のリスト
を実際的に保持する。

【００５５】 *********************************************************************** process＿md(metadata, address) BEGIN IF metadata.count <= max＿commit //既にコミットされている場合 THEN map[metadata.address] := address ELIF metadata.count = max＿commit + 1 AND NOT metadata.commit //countを前進させない THEN plistelm.address := address plistelm.block＿addr := metadata.address insert(pending, plistelm) ELSE // 前進をカウントし、保留リストをフラッシュする WHILE NOT empty(pending) //リスト上の項目 DO map[top(pending).block＿adress] := top(pending).adress pop(pending) OD IF metadata.commit //コミットされたトランザクションをチェック THEN //コミットされ、マップをインストールし、max commitを更新する max＿commit := metadata.count map[metadata.address] := addres ELSE //保留リストに挿入 plistelm.address := address plistelm.block＿addr := metadata.address insert(pending, plistelm) //このトランザクションに先行するようにmax＿commitを更新 max＿commit := metadata.count - 1 FI FI END *********************************************************************** 「top()」、「pop()」、及び「insert()」は標準リスト
動作である。

【００５６】注2:このアルゴリズムは、一つの未処理I/
Oだけをサポートするものであるが、同時I/Oへの汎用化
は簡単である。

【００５７】 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊補足説明II：ページ割り当て構造疑似コードリスト ページ割り当てテーブルは、ディスク構造を反映するよ
うに編成される。各アドレスには単一ビットが割り当て
られる。これらのビットは三次元アレイへと編成され、
シリンダ番号、回転位置及び面番号(前述の物理的要求
の構成要素)によって索引付けされる。待ち時間は主と
してシリンダ番号と回転位置とによって決定されるの
で、ビット自体はワードとして編成され、各ワードは可
能記憶場所の縦のカラムを表す。そこで割り当てテーブ
ルは次のように見える。

【００５８】カラム = ３２ビットの整数 free＿map = カラムの（Ｎシリンダ×Ｎ回転）のアレ
イ これらの構造を操作するルーチンは２つのカテゴリ、す
なわちリソースの制御と検索とに分類される。リソース
制御ルーチンは「allocate」と「free()」である: *********************************************************************** allocate(address) BEGIN segment := address / segment＿size cylinder := segment / segments＿per＿cyl rotation := mod(segment, segments＿per＿track) surface := mod(segment, number＿of＿surfaces) clearbit(free＿map[cylinder][rotation], surface) END free(address) BEGIN segment := address / segment＿size cylinder := segment/segments＿per＿cyl rotation := mod(segment, segments＿per＿track) surface := mod(segment, number＿of＿surfaces) setbit(free＿map[cylinder][rotation], surface) END *********************************************************************** 「setbit()」と「clearbit()」はカラムビット記号列を
面毎に１ビットずつ維持する。

【００５９】更に４つの検索ルーチン、即ち「empt
y()」、「first＿elem()」、「available()」、及び「s
earch＿list()」がある: *********************************************************************** empty(cyl, rot) BEGIN rot := mod(rot, NROT) IF free＿map[cyl]{rot] = 0 // 「=0」はfreeセグメントを含意しない THEN TRUE ELSE FALSE FI END first＿elem(cyl, rot) BEGIN rot :=mod(rot, NROT) column = free＿map[cyl]｛rot] FOR surface = 0 TO NSURFACE - 1 DO IF bit(column, surface) THEN break FI OD surface END search＿list(range, search＿pos) BEGIN list := NULL rposition := search＿pos.sector / sect＿per＿segment FOR cyl = range.first TO range.last DO insert(list, cyl) OD list END available(address) BEGIN segment := address / segment＿size cylinder := segment / segments＿per＿cyl rotation := mod(segment, segments＿per＿track) surface := mod(segment, number＿of＿surface) bit(free＿map[cylinder][rotation], surface) END *********************************************************************** 「bit()」は、ビットがセットされている場合は真に戻
り、セットされていない場合には偽に戻る。

【００６０】 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊補足説明III：ディスクシャッフリング疑似コードリスト アイドル期間中、ディスクは読み出しをより効率良くす
るようにそれ自体の再編成を行う。一対一機能「opt＿s
eg()」が、引数としてブロックを付与されたセグメント
用の最適記憶場所を生み、又、「opt ＿block()」が、
提示された記憶場所が付与された最適ブロックを生むも
のと想定すると、下記のアルゴリズムを用いてディスク
を復元することができる。このアルゴリズムは先ずブロ
ックをそれらの目標シリンダ内に移動させ、次にそれら
の最終行き先へと移動する。

【００６１】 *********************************************************************** shuffle＿disk() BEGIN request. size := segment＿size request. type := READ done := FALSE WHILE NOT done //終了するまでシリンダを集める DO done := TRUE //全てのアドレス FOR request.address FROM 1 TO NBLOCK - 1 DO read＿request := loge＿read(request) cur＿cyl := addr＿to＿cyl(read＿request.address) target := opt＿seg(request) tar＿cyl := addr＿to＿cyl(target) //誤ったシリンダをチェック IF cur＿cyl = tar＿cyl THEN // 適所にあり、継続する ELIF cyl full(tar＿cyl) // 行き先がない THEN done := FALSE ELSE // 新たなシリンダに移動 do＿io(read＿request, FALSE); cyl＿shuffle＿write(request, target); FI OD OD done := FALSE WHILE NOT done DO done := TRUE //全てのブロック FOR request.adress FROM 1 TO NBLOCK - 1 DO read＿request := loge＿read(request) target := opt＿seg(request) //誤ったシリンダをチェックする IF read＿request.address = target THEN // 適所にあり、継続する FI do＿io(read＿request, FALSE); IF available(target) THEN //正しい記憶場所に移動する target＿shuffle＿write(request, target); ELSE done := FALSE //このブロックは誤った記憶場所にある //デッドロックを防止するため、このブロックを移動する cyl＿shuffle＿write(request, target); FI OD OD END target＿shuffle＿write(request, address); BEGIN write＿request.size := segment＿size write＿request.address := address phys＿req := io＿map(write＿request) phys＿req.size := segment＿size old＿adress := get＿loge＿map(address) phys＿req.count := global＿count do＿io(phys＿req, /* last = */ TRUE) global＿count := global＿count + 1 free(old＿adress) END cyl＿shuffle＿write(request, target) BEGIN cyl := addr＿to＿cyl[target] FOR rot FROM 0 TO NROTATION - 1 DO IF NOT empty(free＿map[cyl][rot]) THEN break; FI OD surface :=first＿elem(column) target := phys＿to＿seg(cyl, surface, rot) target＿shuffle＿write(request, target) END *********************************************************************** 「 Opt＿seg()」は、ディスクによって内部的に、又は固
定されたマッピング又はホストからダウンロードされた
マッピングを介して外部的に定義することができる。簡
単なマッピングは、ホストファイルシステムがディスク
を良好にレイアウトすることを想定し、常にシーケンシ
ャル状態を復元しようと試みる、シーケンシャルマップ
ということになる。

【００６２】 *********************************************************************** Opt＿seg(address) BEGIN cylinder := address / logical＿cyl＿size surface := (address % logical＿cyl＿size) / track＿size rot :=(address%track＿size phys＿to＿seg(cyl, surface, rot) END *********************************************************************** 論理シリンダサイズが実際のシリンダサイズよりも小さ
い場合、これは各シリンダ内にフリーセグメントを残
し、ディスクをシーケンシャル編成する。

【００６３】

【発明の効果】本発明は上述のように、他の利用可能な
記憶場所のアクセス時間に比較して最短の時間でアクセ
スすることができる利用可能な記憶場所へデータパケッ
トを書き込むので、書き込み動作が最短時間で完了す
る。これにより、書き込み性能を最適化させると共に読
み出し性能を最適化させることが可能となる。

【図面の簡単な説明】

【図１】ホストプロセッサに接続された本発明による間
接アクセスディスク記憶装置を示す概略図である（１/
２）。

【図２】ホストプロセッサに接続された本発明による間
接アクセスディスク記憶装置を示す概略図である（２/
２）。

【図３】図１に示した間接アクセスディスク記憶装置に
おける選択された記憶場所を示す部分拡大図である。

【図４】図２のデータメモリに示した割り当て記録に対
応する割り当て記録データ構造を示す説明図である。

【図５】図２のデータメモリに示した使用記録に対応す
る使用記録データ構造を示す説明図である。

【図６】図３に示した選択された記憶場所に記憶される
データパケットを示す説明図である。

【符号の説明】

102 ホストプロセッサ 104 記憶媒体 106 磁気記録ヘッド 108 SCSIインタフェース 111 現在のヘッド位置 113 選択された記憶場所 114 制御バス 116 データバス 120 命令メモリ 121 データメモリ 123 １カラム群の記憶場所 124 ディスクコントローラプロセッサ 317 使用記録データ構造 337 割り当て記録データ構造 340 データパケット

Claims (1)

【特許請求の範囲】
1. 【請求項１】データを記憶させるための装置であって、
   この装置が、 複数の記憶場所を有する記憶媒体と、 データパケットを記憶させるための要求に応じて、どの
   記憶場所が利用可能であるかを判定し、他の利用可能な
   記憶場所のアクセス時間と比較して最短時間でアクセス
   できる記憶場所を利用可能記憶場所の中から選択する割
   り当て手段と、 前記記憶媒体上における前記選択された記憶場所に前記
   データパケットを記録する記録手段とからなることを特
   徴とする、間接アクセス記憶装置。