JPS619722A - デイスク記憶装置のトラツクでペ−ジを再配列する装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は主記憶装置とディスク装置の間でページ・デー
タを転送するようなページング・システムを有するデー
タ処理システムの改良に係り、更に詳細に説明すれば、
ディスク・トラックをシークする際に読取り・書込みヘ
ッドの移動量が減少するようにディスク上のページを再
配列（ｒｅｏｒｄｅｒ）するシステムに係る。

Ｂ、開示の概要 ページング・システムを有するデータプロセッサにおい
て、トラック・シーク時間のリストが維持される。この
リストの更新は、成るページをデイスク記憶装置から主
記憶装置に転送する場合に行われる。主記憶装置中のペ
ージの平均トラック・シーク時間が計算され、トラック
・シーク時間の基準値と比較される。平均値が基準値に
達する場合、主記憶装置中のページがディスク上で再配
列される。この再配列は、通常のページング・プロセス
中に主記憶装置からページが追い出される際に行われ、
そしてこれらのページは、該ページが最初に主記憶装置
に転送された物理的順序でディスク・トラック上で再配
列される。若し、はぼ同じページが、はぼ同じ順序で再
び取出されるなら、ディスク装置の読取り・書込みヘッ
ドが連続するディスク・アクセスの間に移動する距離は
短縮し、バック・トラッキングが減少する。本発明を実
施するに適したデータ・プロセッサは、ページング・シ
ステムを使用するのに十分な規模を有するが、高速・高
性能のディスク記憶装置を使用するには規模が小さすぎ
る、そのような中規模のデータ・プロセッサである。

Ｃ０従来の技術 ページング・システムは、ＩＢＭ社発行の出版物″シス
テム／３７０の仮想記憶装置入門″（ＦｏｒｍＮｏ、Ｇ
Ｒ２０−４２６０−１）に簡単に説明されている。

ページング・システムでは、主記憶装置は、例えば、数
千バイトの単位に分割され、プログラムまたはデータは
、この大きさの単位で補助記憶装置から主記憶装置に転
送される。このデータ単位は″ページ″と呼ばれ、これ
に対応する主記憶装置中の物理的記憶単位は″ページ・
ロケーション″または″ページ・ブロック″と呼ばれる
。一般に、ページング・システムは、仮想記憶を実現す
るのに使用されるので、″仮想記憶″と″ページング・
システム″という用語は同義に用いられることがある。

仮想記憶では、プログラム内のアドレスは、プログラム
を実際にランする場合に使用する物理アドレス位置とは
無関係である。従って、プログラムは、物理的記憶装置
の実際の容量とは無関係な、大きなアドレス空間で書込
みまたは読取りを行うことができる。

磁気ディスク装置は、本発明を使用するシステムの代表
的なＩ１０記憶装置（補助記憶装置）である。ディスク
装置は、例えば１〜１００個の環状トラックを有する。

説明を簡単にするため、各トラックは１ページのデータ
を保持し、通常ディスク装置と主記憶装置の間ではペー
ジ単位の転送が行なわれるものとする。これは、大抵の
場合。

本発明を実現するのに望ましい構成である。

システムはファイル・マツプ・テーブルを維持し、これ
はプログラムおよびファイルのトラック位置を示す。デ
ータをアクセスする動作中、中央プロセッサは、トラッ
クアドレスをディスク・コントローラに転送する。

各トラックは複数のセクタに分割されており、従って各
セクタは１ページの一部を保持する。完全な１トラツク
をデータ転送の単位として用いると、読取り・書込みヘ
ッドを通過する次のセクタから転送を開始できるという
利点がある。この手法はパロール・モード″と呼ばれ、
読取り・書込みヘッドがトラックの開始点に来るまで待
機することによって生じる遅延を回避する。このような
データ単位に到達するまでの回転遅延は、パトラツク待
ち時間″または″回転待ち時間″と呼ばれる。

更に、ディスク・アクセスについては、読取り・書込み
ヘッドを現在のトラック位置からアクセスすべき次のト
ラックに放射状に移動するのに要する遅延がある。この
遅延は″トラック・シーク時間″と呼ばれる。一般に、
仮想記憶はがなり大き。

いシステムでしか使用されず、またこれらのシステムは
非常に高速のトラック・シークを行なう高性能のディス
ク装置を有する。

Ｄ０発明が解決しようとする問題点 従って、本発明の目的は、中程度の性能のディ　　゛ス
フ装置を、仮想記憶システムを利用するのに十分な大き
さのシステムで使用できるように、そのトラック・シー
ク時間を短縮することである。従って、本発明はロール
・モードを補完するものであり、これらの２つの手法を
用いてディスクのアクセス時間を改善できる。更に、本
発明はトラッりとページが完全に一致しない多くのシス
テム、またはロール・モードを使用しないシステムでも
有用である。

またあるファイルは、レコードと呼ばれる小単位から成
り、多くの場合、これらのレコードは、例えば、アルフ
ァベット類に順次アクセスされるので、ディスク上に物
理的に同じ順序で配列すると好都合である。このような
状況では、ディスク・ヘッドは、最小限のシーク時間で
、トラックからトラックへ漸次移動できる。他のファイ
ルは、任意の順序でアクセスされることがあり、このよ
うな状況では、一般にシーク時間は長くなり、若し、ト
ラックがランダムにアクセスされたなら、読取り・書込
みヘッドは平均的なシーク動作において全トラックの約
１／３を横切ることになろう。従って、本発明の他の目
的は、ランダムにアクセスされるディスク上のファイル
を再配列して、トラック・アクセスのパターンが順次フ
ァイルのそわとほぼ同等になるようにすることである。

本発明の他の目的は、トラック・シーク時間を短縮する
ようにディスク上のデータを線列することである。

Ｅ０問題点を解決するための手段 この点を説明する便宜上、システムの動作を２つのモー
ドに分割する。どちらのモードにおいても、主記憶装置
中にある各ページのトラック・シーク時間のリストが維
持され、そしてこのリストは新しいページが主記憶装置
に転送されるごとに更新される。第１のモードでは、こ
れらのトラック・シーク時間の平均値が計算され、基準
値と比較される。この基準値は、ディスク上のページを
再配列することにより相当な程度にまで改善できる平均
シーク時間を表わすように、予め選択されている。平均
シーク時間がこの基準値よりも小さい限り、システムは
ディスク上のページを再配列することなく、第１のモー
ドで動作する。第２のモードは、平均値が基準値に達し
たときに開始される。第２のモードでは、ページが主記
憶装置から追い出される際に、これらのページはディス
ク上で再配列される。主記憶装置中のすべてのページの
リストが維持され、そして主記憶装置に元々置かれてい
た各ページが所望のトラック（当該ページの将来の取出
し動作を有利に行なえるようなトラック）に再書込みさ
れてしまうまで、このリストから複数のページが選択さ
れる。第２のモードの動作が終了すると第１のモードに
戻るにこで、ディスク上のページが最初は適正に配列さ
れており、システムが第１のモードで動作している間に
新しいプログラムが実行を開始したものと仮定する。ま
た、ディスク・アクセスは複数のディスク・トラックに
わたってランダムに分散しており、そしてその平均トラ
ック・アクセス時間が基準時間に達したものと仮定する
。若し、これらのトラック・アドレスがランダムであれ
ば、ヘッドは、あるディスク・アクセス動作では内方に
移動し、他のディスク・アクセス動作では外方に移動す
る。すなわち、ヘッドの移動距離はあるアクセスについ
ては短かく、他のアクセスについては長くなる。若し、
トラック上の情報を、これらのトラックが将来アクセス
されるであろう順序で配列することができれば、ヘッド
の移動距離は最少になるはずである。しかしながら、一
般にページを取り出す順序は未知である。本発明のシス
テムは、ディスクからページが取出される順序は、これ
らのページが前に取出された順序と同じである、という
仮定に基づいている。

ページを再配列するためのリストは、ディスクから取出
されたページの先入れ先出し式リスト（待ち行列）であ
る。或、るページがディスクから取出されると、このペ
ージは、待ち行列の末尾に加えられる。成るページを再
配列する場合は、そのページは待ち行列の先頭から取出
される。また、これらのページが取出されたトラックを
識別する通常のリストもあり、主記憶装置中のページは
この元のセットのトラックに戻すことが望ましい。

本発明のシステムがトラックの再配列を開始する場合、
ページは待ち行列から選択され、そしてトラックはその
トラック番号の順序（低い方から高い方へ、またはその
逆）に選択される。従って、これらのページは、前にデ
ィスクから取出されたのと同じ順序でトラック上に配列
されることになる。

Ｆ、実施例 Ｆｌ、従来の構成要素（第１図） 第１図のデータ処理システムには、従来の構成要素とし
て、 主記憶装置１３中の代表的なページ・ブロック１２、主
記憶装置１３のアドレスを保持するアドレス・レジスタ
１４、アドレス変換およびその関連動作に使用されるペ
ージ・マツプ・テーブルを維持する（通常は主記憶装置
１３とは別個の）記憶装置１５、プログラムおよび他の
構成要素から成るページ不在ハンドラ１７、ならびにデ
ィスク記憶装置およびそのコントローラ１９が含まれて
いる。

ページングを行なうために、アドレス・レジスタ１４中
のアドレスは、主記憶装置１３中のページ・ブロックを
指定するページ・アドレス２１と、ページ・ブロック中
のバイトをアドレスするオフセット・アドレス２２の２
つの部分に区分される。

（システムは更に、セグ４ント・アドレスと呼ばれる１
組のビットを有することもあるが、これらのシステムへ
の本発明の適用は特に説明しなくても明白である。）ペ
ージング・システムは、ページ・アドレスしか使用しな
い。ページ・アドレスは、ページ・マツプ・テーブル１
５を探索することにより、対応するページデータが置か
れている、主記憶装置１３中のページ・ブロックを識別
する。

ページ・アドレスは、ページ不在ハンドラ１７に含まれ
た他のファイル・マツプ・テーブルを探索することによ
り、ディスク上にある同じページのアドレスを識別する
。

主記憶装置１３がアクセスされる場合、アドレス・レジ
スタ１４中のページ・ビットは、ページ・マツプ・テー
ブル１５に送られ、そこで対応するブロック・アドレス
を見つけるための探索引数として使用される。第１図の
ブロック図において、ページ・マツプ・テーブル１５は
、主記憶装置１３中のページ・ブロックごとに１つの行
を有し、また各行のそれぞれの列には複数の情報フィー
ルドが配列されている。これらの１つのフィールド２６
には、ページ・アドレスをブロック・アドレスに変換す
るための情報が保持されている。若し、ページが主記憶
装置１３中にあれば、アドレス一致が検出されて、線２
７のブロック・アドレスと線２８のオフセット・アドレ
スの組合せにより主記憶装置１３が通常の様式でアクセ
スされる。

若し、アドレスされたページが主記憶装置１３中に存在
しなければ、そのページ・アドレスは、線３ｏを介して
ページ不在ハンドラ１７に送られる。この場合、ページ
不在ハンドラ１７は、（ページ・ブロックが利用可能で
ない限り）成るページを主記憶装置１３から追い出すと
ともに、アドレスされたページをディスク記憶装置１９
から取り出す。

追い出すべきページは適当な基準に基いて選択される。

第１図はＦｌＦＯ（先入れ先出し）リストを使用した特
定のシステムを示す。というのは、ＦＩＦＯページング
・システムと本発明のシステムの間には類似性（後述）
が存在するからである。

ＦＩＦＯページング・システムでは、新しいページの識
別子が、待ち行列の末尾に記入される。もちろん、待ち
行列の先頭にあるページは、主記憶装置１３中に最も長
く駐在しているページであり、従って、このページング
・システムでは、追い出すべきページは、待ち行列の先
頭から線３２を介して選択される。第１図において、Ｆ
ＩＦＯリストは、ページ・マツプ・テーブル１５中のフ
ィールド３１として実現されている。ページ不在ハンド
ラ１７は、待ち行列の先頭と末尾を指定するポインタ　
（アドレス）を有する。フィールド３１中の各エントリ
は、待ち行列中の先行エントリを指定するポインタでも
よい。（この場合、最後のエントリは有効なポインタを
持たない。）成るページが追い出される場合、ページ不
在ハンドラ１７にある、待ち行列の先頭を指定するポイ
ンタが更新される。一方、新しいページがロードされる
場合、待ち行列の末尾を指定するポインタが更新され、
またそれまで待ち行列の末尾にあったページが新しいペ
ージに連結される。これらの待ち行列管理動作は通常の
ものであって、いくつかのプログラミング言語で容易に
実現することができる。

また、ページ・マツプ・テーブル１５中の各エントリに
設けられた１ビツト・フィールド３４は、成るページ・
ブロックにおける書込み動作により、ディスク上の対応
するデータが陳腐化されるとき（書込みデータと一致し
なくなるとき）、線３５上の信号によってセットされる
。若し、線３７上の信号によって通知されるようにこの
ビットがセットされたならば、ページ不在ハンドラ１７
は、このページが主記憶装置Ｊ３から追い出されるとき
、これをディスクに再書込みする。反対に、若し、主記
憶装置１３のデータが不変（フィールド３４０ビツトが
セラｌ−されない）なら、再書込み動作は不要である。

このシステムは、二次記憶装置におけるページ・データ
の位置を示すファイル・マツプ・テーブルを有している
ので、前記ページを再書込みすべきディスク上の位置は
このテーブルから見つけることができる。別の観点から
説明すれば、追い出されるべきページの主記憶アドレス
とディスク・トラックの位置は、入出力動作を実行する
ルーチンに渡されるのである。

成るページを追い出すことによって主記憶装置１３に空
間が作られた後、ページ不在ハンドラ１７は、ディスク
上のアドレスされたトラックにあるページを取出し、こ
れをページが追い出されたばかりの主記憶装置１３中の
ページ・ブロックにロードする。一層詳細に説明すれば
、ページ不在ハンドラ１７は、該当するページ・アドレ
スをディスク・トラック・アドレスに変換し、このトラ
ンク・アドレスと主記憶装置１３のブロック・アドレス
とを入出カル−チンに渡すのである。トラック・アドレ
スとそれに関連する制御信号に応答して、ディスク装置
１９は、シーク動作を実行し、ディスク・ヘッドを、ア
ドレスされたトラックに位置づける。シーク動作に、は
遅延があり、またディスクが、読取り動作を開始すべき
位置まで回転する間の遅延がある。第１図には、トラッ
ク・アドレスと他の制御情報をディスク・コントローラ
１９に送るための通常の線４１、およびディスク装置１
９と主記憶装置１３の間でデータを転送するための通常
の線４２が示されている。

前述の装置と関連動作は通常のものであり、本発明のシ
ステムを使用できる広範囲にわたる種々のデータ処理シ
ステムと本発明の関連を示すのに適切な範囲に限って説
明したものである。

Ｆ２．再配列装置（第１図） 第１図にはトラック再配列装置４９が示されている。そ
の詳細は第２図に示されている。トランク再配列装置４
９は、各ページごとにトラック・シーク時間を記録する
ための記憶手段を含み、第１図の実施例では、この記憶
手段は記憶装置１５中のフィールド４８として実現され
ている。更に、トラック再配列装置４９は、後述するよ
うに、ページ不在ハンドラ１７の構成要素も含む。

ページ不在ハンドラ１７は、既に説明した通常の動作に
付随して、ディスクのトラック・アドレスを生成し、こ
れを線５１を介してトラック再配列装置４９に送る。ト
ラック再配列装置４９は、このトラック・アドレスを用
いてトラック・シーク時間を生成し、これを線５３を介
してフィールド４８の特定の位置へ記入する。一層詳細
に説明すれば、ページング動作の間にページ不在ハンド
ラ１７によってアドレスされるページ・ブロックに対応
するフィールド４８の位置にトラック・シーク時間が記
入されるのである。ここで、シーク時間は主記憶装置１
３中のページ・ブロックに関連するが、一時的にページ
・ブロックに書込まれているページ情報には関連しない
ことに注意すべきである。成るページが追い出される場
合、前のシーク時間は最新のシーク時間を表わす。

主記憶装置１３から追い出し中のページについて、トラ
ック再配列装置４９は、フィールド４８にあるトラック
・シーク時間を１ＩＡ５４を介して読取る。システムが
再配列モードにある場合、トラック再配列装置４９は、
線５５を介してページ不在ハンドラ１７に再配列信号を
送る。この信号に応答して、ページ不在ハンドラ１７は
、ページが主記憶装置１３から追い出されるとき、ディ
スクを再配列するように動作する。同様に、システムが
再配列モードで動作を開始する場合、トラック再配列装
置４９は、フィールド３４の再書込みビットをセットす
るか、さもなければ、ページ不在ハンドラ１７に、各ペ
ージをディスクに再書込みさせる。再配列の場合、線５
６を介したリセット動作は、主記憶装置１３にある元の
ページ・セットにしか適用されない。再配列の間に新し
いページが取出されると、フィールド３４のビットがリ
セットされ、その後は線３５上の通常の信号によりセッ
トされる。

Ｆ３．トラック再配列装置の詳細（第２図）トラック再
配列装置４９の詳細を第２図に示す。

現在のトラック・アドレスは線５１を介してレジスタ６
２に記入され、そしてこれはレジスタ６４にシフトされ
て最後のトラック・アドレスとなる。

トラック再配列装置４９は、第２図のユニット６７．６
８および６９から成る演算論理装置を含む。レジスタ６
２および６４の内容はユニット６７に送られ、そこで両
者の値の差を表わす絶対値が得られる。これらの値の一
方を他方から引く場合に形成される符号は、ディスクの
読取り・書込みヘッドが移動した方向に対応するが、ユ
ニット６７では差の絶対値が形成されるにすぎないので
このような情報は捨てられてしまう。

ユニット６７の出力から得られるトラック・シーク時間
は記憶装置１５のフィールド４８に送られ、その特定位
置、すなわちページング動作が行われているページ・ブ
ロックに対応する位置に書込まれる。このトラック・シ
ーク時間は線７０を介してユニット６８にも送られ、該
ユニットはこれに応じて新しい平均シーク時間を計算す
る。計算された平均シーク時間はレジスタ７２に書込ま
れる。ユニット６８は、線５４を介してフィールド４８
から受取った前のシーク時間と、ユニット６７からの新
しいシーク時間と、古い平均シーク時間とを組合せて、
新しい平均シーク時間を計算する。すなわち、線５４上
の古いシーク時間を古り゛平均シーク時間から引き、そ
して新しいシーク時間を古い平均シーク時間に加えるこ
とにより、新しい平均シーク時間を計算するのである。

トラック・シーク時間は、現在のトラック・シーク・コ
マンド中のトラック番号と前のトラック・シーク・コマ
ンド中のトラック番号の間の、差の絶対値として計算す
ることが望ましい。この差が適切であると考えられる所
以は、トラックの番号が順次に付されており、またトラ
ック・シーク時間が、読取り・書込みヘッドが横切るト
ラック数にほぼ直線的に比例するからである。

レジスタ７５は基準シーク時間を保持する。ユニット６
９は、レジスタ７２の現在の（すなわち新しい）平均シ
ーク時間と、レジスタ７５の基準値とを受取り、両者を
比較してディスクを再配列すべきかどうかを表わす出力
信号を線５５に送る。

比較動作の結果は、″より小さい″、パ等しい″、又は
″より大きい″のどれかである。平均値が基準値よりも
小さい場合、出力信号は再配列が行われない″通常モー
ド″を指示し、平均値が基準値よりも大きい場合は、出
力信号は再配列が行われる″゛再配列モード″を指示す
る。平均値と基準値が等しい場合には、どちらか一方を
任意に指示できる′。

本発明の装置についてこれまで説明したように、記憶装
置１５のフィールド４８はトラック数の差を保持し、レ
ジスタ７２はこれらの差の和を保持する。このような状
況では、レジスタ７５の値は、１シ一ク動作の基準時間
とフィールド４８のエントリ数との積になるはずである
。（或いは、これと同等の値を得るためには、レジスタ
７５の基準値を１シ一ク動作の平均時間に対する基準値
とし、そしてレジスタ７２の値をエントリ数で割るよう
にしてもよい。）同様に、ユニット６７の出力で得られ
る新しいシーク時間をフィールド４８のエントリ数で割
り、そしてレジスタ７５の値をエシーク動作の基準時間
とすることができる。通常、記憶装置１５には２進値で
表わすことができるページ・ブロック数があるので１割
算も掛算も単にシフト動作で実行できる。

第２図の装置は、第１図に示したプロセッサ・システム
の汎用の構成要素として実現することが望ましい。レジ
スタ６２および６４は、主記憶装置１３中の汎用の記憶
位置を用いることができ。

そうすればこれらのレジスタとの転送は、高級プログラ
ミング言語で変数値を割当てるのと同じ動作で実行され
る。

本発明の装置は、システムが通常の動作モードにあって
、ページ不在ハンドラ１７が呼出されるごとに、平均値
と基準値を比較することが望ましい。同様に、平均アク
セス時間は、所定数のページ不在または他の適切な基準
に基づいて計算できる。

Ｆ４．基準値の設定 トラック・シーク時間をトラック数によって定義する場
合、この値は、０から最大値（全トラック数から１を引
いた値）までの範囲に及ぶことがある。ここで注意すべ
きは、基準値がＯにセットされた場合、システムは絶え
ずトランク再配列モードで動作し、一方、基準値が最大
値にセットされた場合は、再配列モードは禁止される、
ということである。基準値は、操作員により、または自
動的に、異なった種類のデータにシステムが適応するよ
うに変更できる。例えば、再配列動作の結果がほんめ僅
かの改善しか生じない場合は、基準値を高くすることが
望ましいであろう。

若し、トラックが最大の不規則性を有していたなら、ラ
ンダムなトラック数の列の場合と類似の結果が生じるで
あろう。このようなランダムなケースでは、平均トラッ
ク・アクセス時間（トラック数）は、最大値の約３３％
となろう。このような結果を理解するには、プレーヤの
得点を２つの１′さいころ″の値の差の絶対値とする類
似のゲームを考えればよい。（トラックが異常に配列さ
れた場合、平均値は、最大値の３３％よりも大きくなる
であろう、）ランダムな値は、再配列の間に。

トラック・アドレスを単にハツシングすることにより得
られる。従って、最大シーク時間の約２５％の基準値は
、実際の開始時の値として適切であろう。

基準値は、トラック・シーク時間を有効に改善できるよ
うに、十分低い値にセットされる。一方。

基準値が低過ぎれば、システムは、実際に平均トラック
・シーク時間を改善せずにトラックを再配列する。適切
な基準時間は、ページ不在処理要求の形式的な分析から
計算できるし、または完全な試行錯誤によっても選択で
きる。しかし、まず最良の判断によって成る基準値を選
択し、これをシステムの性能によって調整することが望
ましい。

このような調整値は１例えば、トラック・シーク時間の
経過記録に基いて操作員が記入し、次いでこれをそれ以
上は減少しなくなるまで、小刻みに減少させることがで
きる。代替方法として、前述の反復手順は、プログラム
により容易に処理できる。適切な値は、実質的に一定の
システム特性に依存し、また可変の特性にも依存するの
で、成る種の動作についてはシステムを禁止することが
望ましい。

Ｆ５．通常モードへの復帰 再配列動作が待ち行列を通して進行している間、古いペ
ージがディスクに戻されるにつれて新しいページが追加
される。これらのページのシーク時間は、前述のような
方法で書込まれる。一般に、新たに追加されたページの
多くは、主記憶装置１３から追い出され、待ち行列から
取除かれ、次いで主記憶装置！１３から再び取出された
ページである。従って、元のリストからのページだけを
再配列し、そして元のページが再配列された場合に再配
列プロセスを停止することが望ましい。線５５の再配列
信号は、元のリストの最後のページが主記憶装置１３か
ら追い出され、ディスク上で再配列されるとき、落とさ
れる。リストの末尾は、通常のリスト管理手法により認
識することができる。

例えば、デキューイング（待ち行列から外す）動作をカ
ウントすることにより、または元のリストにおける最後
のエントリを指定するポインタをセーブし、これを追い
出される各ページのポインタと比較することにより、リ
ストの末尾を認識できる。

システムがページ・リストを再配列している間は、平均
シーク時間を計算しないことが望ましい。

そうすると、再配列動作は、若干のページが再配列され
た後に生じることがある平均アクセス時間の変更とは関
係なく、リスト中の全ページにわたつて行なわれるから
である。代替的に、システムは、再配列モードで連続し
て動作することが可能であり、或いは平均値が改善され
るまで再配列モードで動作することも可能である。

Ｆ６．ＬＲＵ置換アルゴリズム このシステムは、最も長い間使用されなかった（ＬＲＵ
）ページを追い出すページングシステムについても有用
である。一般的に説明すれば、このシステムはＬＲＵア
ルゴリズムに類似する特性を与えるために１ビツト・フ
ィールドを設け、関連するページ・ブロックがアクセス
されたときこのフィールドをセットするようにしている
。ぺ一ジ不在の処理後、これらのビット全部をリセット
することにより、最近に使用されたページのセットと、
そうではない相補的なページのセットとが識別される。

ＬＲＵアルゴリズムを有するシステムは、通常は、ペー
ジ待ち行列を維持せず、本発明のシステムでは、別個の
ページ置換待ち行列が再配列動作のために設けられてい
る。トラック・シーク時間は、第１図に示したようなフ
ィールド４８に保持され、このフィールドは前述のよう
に処理される。

この装置は、ディスクが前述のように再配列されている
間は１通常のページ置換動作を禁止する手段を含む。

本発明の更に全般的な理解に資するため、実施例におけ
る待ち行列の機能を説明する。待ち行列は： （ａ）トラック位置のセット （ｂ）再配列されるページのセット （ｃ）ページをディスク上に再配列する場合の物理的順
序 （ｄ）ページを主記憶装置から追い出す時間的順序を定
義する。実施例は、待ち行列のこれらの特性を利用して
、特定の利点を得る。

普通、複数のページが取出された元のトラックの間でこ
れらのページを再配列するのは、都合がよいが、これら
の異なったトラックのセット、例えば、別のディスク、
または、一部分は元のトラック、他の一部分は別個のト
ラックからなるセットの間で再配列されることもある。

再配列は、（平均値が）基準時間に達したときに開始し
、元のページ・セットの各ページが再配列されるまで継
続することが望ましい。しかしながら、再配列は、いつ
でも中断できる。例えば、平均時間が基準時間を下回る
ように改善された場合、中途で中断できる。このような
動作を行なうには、このセットの残りのページは、使用
可能なトラックに割当てられ、すべてのページが確実に
ディスク上に復元されるように必要に応じて再書込みさ
れる。代替的に、再配列すべき元のページ・セットを行
列のサブセットから選択することもできる。

通常、主記憶装置１３中のページを待ち行列の順序で追
い出すことが好都合である。このことは、待ち行列を維
持する動作を簡略化するのが普通だからである。待ち行
列は一般にページ置換のために使用されるので、この手
順はページ置換システムの目的を満たすべきである。し
かしながら、追い出しページを他の適切な基準に基づい
て、そして待ち行列で定義された物理的順序でディスク
上に再配列することもできる。

Ｇ１発明の効果 以上詳述したように、本発明によれば、ページング・シ
ステムを有するデータ処理システムにおいて、ディスク
装置のトラック・シーク時間を著しく短縮できるので、
中程度の性能を有するディスク装置であっても、これを
有利に使用することができる。

【図面の簡単な説明】

第１図は本発明のトラック再配列装置ならびに関連する
構成要素の機能ブロック図、第２図は第１図のトラック
再配列装置の詳細図である。 １２・・・・ページ・ブロック、１３・・・・主記憶装
置、１４・・・・アドレス・レジスタ、１５・・・・記
憶装置、１７・・・・ページ不在ハンドラ、１９・・・
・ディスク記憶装置およびコントローラ、４９・・・・
トラック再配列装置。 第１図 実施例のブロック図 第２図

Claims (1)

1. 【特許請求の範囲】 ディスク記憶装置のトラックと主記憶装置のページ・ブ
   ロックとの間でページを転送するための手段を有するデ
   ータ処理システムにおいて、（ａ）前記ディスク記憶装
   置から前記主記憶装置へ転送されたページの待ち行列を
   維持するための手段（３１）と、 （ｂ）前記ページ・ブロックごとに測定されたトラック
   ・シーク時間のリストを維持するための手段（４８）と
   、 （ｃ）前記ページ・ブロックの平均トラック・シーク時
   間を計算し、該平均トラック・シーク時間と基準トラッ
   ク・シーク時間を比較するとともに、前記平均トラック
   ・シーク時間が前記基準トラック・シーク時間よりも大
   きい場合は再配列信号を供給するための手段（４９）と
   、 （ｄ）前記主記憶装置からのページを書込むために使用
   可能な１組のトラックを識別するリストを含み、前記再
   配列信号に応答して該ページを前記待ち行列中における
   ページの順序に従って該１組のトラックに順次に再書込
   みするための手段（１７）とを備えたことを特徴とする
   、ディスク記憶装置のトラックでページを再配列する装
   置。