JPH0417525B2 - - Google Patents

Description

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

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

Ｃ 従来の技術 ペーシング・システムは、IBM社発行の出版
物“システム／370の仮想記憶装置入門”（Form
No.GR20−4260−１）に簡単に説明されてい
る。

ページング・システムでは、主記憶装置は、例
えば、数千バイトの単位に分割され、プログラム
またはデータは、この大きさの単位で補助記憶装
置から主記憶装置に転送される。このデータ単位
は“ページ”と呼ばれ、これに対応する主記憶装
置中の物理的記憶単位は“ページ・ロケーシヨ
ン”または“ページ・ブロツク”と呼ばれる。一
般に、ページング・システムは、仮想記憶を実現
するのに使用されるので、“仮想記憶”と“ペー
ジング・システム”という用語は同義に用いられ
ることがある。仮想記憶では、プログラム内のア
ドレスは、プログラムを実際にランする場合に使
用する物理アドレス位置とは無関係である。従つ
て、プログラムは、物理的記憶装置の実際の容量
とは無関係な、大きなアドレス空間で書込みまた
は読取りを行うことができる。

磁気デイスク装置は、本発明を使用するシステ
ムの代表的なＩ／Ｏ記憶装置（補助記憶装置）で
ある。デイスク装置は、例えば１〜100個の環状
トラツクを有する。説明を簡単にするため、各ト
ラツクは１ページのデータを保持し、通常デイス
ク装置と主記憶装置の間ではページ単位の転送が
行なわれるものとする。これは、大抵の場合、本
発明を実現するのに望ましい構成である。

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

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

更に、デイスク・アクセスについては、読取
り・書込みヘツドを現在のトラツク位置からアク
セスすべき次のトラツクに放射状に移動するのに
要する遅延がある。この遅延は“トラツク・シー
ク時間”と呼ばれる。一般に、仮想記憶はかなり
大きいシステムでしか使用されず、またこれらの
システムは非常に高速のトラツク・シークを行な
う高性能のデイスク装置を有する。

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

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

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

Ｅ 問題点を解決するための手段 この点を説明する便宜上、システムの動作を２
つのモードに分割する。どちらのモードにおいて
も、主記憶装置中にある各ページのトラツク・シ
ーク時間のリストが維持され、そしてこのリスト
は新しいページが主記憶装置に転送されるごとに
更新される。第１のモードでは、これらのトラツ
ク・シーク次かの平均値が計算され、基準値と比
較される。この基準値は、デイスク上のページを
再配列することにより相当な程度にまで改善でき
る平均シーク時間を表わすように、予め選択され
ている。平均シーク時間がこの基準値よりも小さ
い限り、システムはデイスク上のページを再配列
することなく、第１のモードで動作する。第２の
モードは、平均値が基準値に達したときに開始さ
れる。第２のモードでは、ページが主記憶装置か
ら追い出される際に、これらのページはデイスク
上で再配列される。主記憶装置中のすべてのペー
ジのリストが維持され、そして主記憶装置に元々
置かれていた各ページが所望のトラツク（当該ペ
ージの将来の取出し動作を有利に行なえるような
トラツク）に再書込みされてしまうまで、このリ
ストから複数のページが選択される。第２のモー
ドの動作が終了すると第１のモードに戻る。

ここで、デイスク上のページが最初は適正に配
列されており、システムが第１のモードで動作し
ている間に新しいプログラムが実行を開始したも
のと仮定する。また、デイスク・アクセスは複数
のデイスク・トラツクにわたつてランダムに分散
しており、そしてその平均トラツク・アクセス時
間が基準時間に達したものと仮定する。若し、こ
れらのトラツク・アドレスがランダムであれば、
ヘツドは、あるデイスク・アクセス動作では内方
に移動し、他のデイスク・アクセス動作では外方
に移動する。すなわち、ヘツド移動距離はあるア
クセスについては短かく、他のアクセスについて
は長くなる。若し、トラツク上の情報を、これら
のトラツクが状来アクセスされるであろう順序で
配列することができれば、ヘツドの移動距離は最
小になるはずである。しかしながら、一般にペー
ジを取り出す順序は未知である。本発明のシステ
スは、デイスクからページが取出される順序は、
これらのページが前に取出された順序と同じであ
る、という仮定に基づいている。

ページを再配列するためのリストは、デイスク
から取出されたページの先入れ先出し式リスト
（待ち行列）である。或るページがデイスクから
取出されると、このページは、待ち行列の末尾に
加えられる。或るページを再配列する場合は、そ
のページは待ち行列の先頭から取出される。ま
た、これらのページが取出されたトラツクを識別
する通常のリストもあり、主記憶装置中のページ
はこの元のセツトのトラツクに戻すことが望まし
い。本発明のシステムがトラツクの再配列を開始
する場合、ページは待ち行列から選択され、そし
てトラツクはそのトラツク番号の順序（低い方か
ら高い方へ、またはその逆）に選択される。従つ
て、これらのページは、前にデイスクから取出さ
れたのと同じ順序でトラツク上に配列されること
になる。

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

ページングを行なうために、アドレス・レジス
タ１４中のアドレスは、主記憶装置１３中のペー
ジ・ブロツクを指定するページ・アドレス２１
と、ページ・ブロツク中のバイトをアドレスする
オフセツト・アドレス２２の２つの部分に区分さ
れる。（システムは更に、セグメント・アドレス
と呼ばれる１組のビツトを有することもあるが、
これらのシステムへの本発明の適用は特に説明し
なくても明白である。）ページング・システムは、
ページ・アドレスしか使用しない。ページ・アド
レスは、ページ・ユツプ・テーブル１５を探索す
ることにより、対応するページデータが置かれて
いる、主記憶装置１３中のページ・ブロツクを識
別する。ベージ・アドレスは、ページ不在ハンド
ラ１７に含まれた他のフアイル・マツプ・テーブ
ルを探索することにより、デイスク上にある同じ
ページのアドレスを識別する。

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

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

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

また、ページ・マツプ・テーブル１５中の各エ
ントリに設けられた１ビツト・フイールド３４
は、或るページ・ブロツクにおける書込み動作に
より、デイスク上の対応するデータが陳腐化され
るとき（書込みデータと一致しなくなるとき）、
線３５上の信号によつてセツトされる。若し、線
３７上の信号によつて通知されるようにこのビツ
トがセツトされたならば、ページ不在ハンドラ１
７は、このペーが主記憶装置１３から追い出され
るとき、これをデイスクに再書込みする。反対
に、若し、主記憶装置１３のデータが不変（フイ
ールド３４のビツトがセツトされない）なら、再
書込み動作は不要である。このシステムは、二次
記憶装置におけるページ・データの位置を示すフ
アイル・マツプ・テーブルを有しているので、前
記ページを再書込みすべきデイスク上の位置はこ
のテーブルから見つけることができる。別の観点
から説明すれば、追い出されるべきページの主記
憶アドレスとデイスク・トラツクの位置は、入出
力動作を実行するルーチンに渡されるのである。

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

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

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

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

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

F3 トラツク再配列装置の詳細（第２図） トラツク再配列装置４９の詳細を第２図に示
す。現在のトラツク・アドレスは線５１を介して
レジスタ６２に記入され、そしてこれはレジスタ
６４にシフトされて最後のトラツク・アドレスと
なる。

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

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

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

レジスタ７５は基準シーク時間を保持する。ユ
ニツト６９は、レジスタ７２の現在の（すなわち
新しい）平均シーク時間と、レジスタ７５の基準
値とを受取り、両者を比較してデイスクを再配列
すべきかどうかを表わす出力信号を線５５に送
る。比較動作の結果は、“より小さい”、“等し
い”、又は“より大きい”のどれかである。平均
値が基準値よりも小さい場合、出力信号は再配列
が行われない“通常モード”を指示し、平均値が
基準値よりも大きい場合は、出力信号は再配列が
行われる“再配列モード”を指示する。平均値と
基準値が等しい場合には、どちらか一方を任意に
指示できる。

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

第２図の装置は、第１図に示したプロセツサ・
システムの汎用の構成要素として実現することが
望ましい。レジスタ６２および６４は、主記憶装
置１３中の汎用の記憶位置を用いることができ、
そうすればこれらのレジスタとの転送は、高級プ
ログラミング言語で変数値を割当てるのと同じ動
作で実行される。

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

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

若し、トラツクが最大の不規則性を有していた
なら、ランダムなトラツク数の列の場合と類似の
結果が生じるであろう。このようなランダムなケ
ースでは、平均トラツク・アクセス時間（トラツ
ク数）は、最大値の約33％となろう。このような
結果を理解するには、プレーヤの得点を２つの
“さいころ”の値の差の絶対値とする類似のゲー
ムを考えればよい。（トラツクが異常に配列され
た場合、平均値は、最大値の33％よりも大きくな
るであろう。）ランダムな値は、再配列の間に、
トラツク・アドレスを単にハツシングすることに
より得られる。従つて、最大シーク時間の約25％
の基準値は、実際の開始時の値として適切であろ
う。

基準値は、トラツク・シーク時間を有効に改善
できるように、十分低い値にセツトされる。一
方、基準値が低過ぎれば、システムは、実際に平
均トラツク・シーク時間を改善せずにトラツクを
再配列する。適切な基準時間は、ページ不在処理
要求の形式的な分析から計算できるし、または完
全な試行錯誤によつても選択できる。しかし、ま
ず最良の判断によつて或る基準値を選択し、これ
をシステムの性能によつて調整することが望まし
い。このような調整値は、例えば、トラツク・シ
ーク時間の経過記録に基いて操作員が記入し、次
いでこれをそれ以上は減少しなくなるまで、小刻
みに減少させることができる。代替方法として、
前述の反復手順は、プログラムにより容易に処理
できる。適切な値は、実質的に一定のシステム特
性に依存し、また可変の特性にも依存するので、
或る種の動作についてはシステムを禁止すること
が望ましい。

F5 通常モードへの復帰 再配列動作が待ち行列を通して進行している
間、古いページがデイスクに戻されるにつれて新
しいページが追加される。これらのページのシー
ク時間は、前述のような方法で書込まれる。一般
に、新たに追加されたページの多くは、主記憶装
置１３から追い出され、待ち行列から取除かれ、
次いで主記憶装置１３から再び取出されたページ
である。従つて、元のリストからのページだけを
再配列し、そして元のページが再配列された場合
に再配列プロセスを停止することが望ましい。線
５５の再配列信号は、元のリストの最後のエージ
が主記憶装置１３から追い出され、デイスク上で
再配列されるとき、落とされる。リストの末尾
は、通常のリスト管理手法により認識することが
できる。例えば、デキユーイング（待ち行列から
外す）動作をカウントすることにより、または元
のリストにおける最後のエントリを指定するポイ
ンタをセーブし、これを追い出される各ページの
ポインタと比較することにより、リストの末尾を
認識できる。

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

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

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

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

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

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

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

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

【図面の簡単な説明】

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

Claims (1)

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