JPH08506676A - デマンドページド仮想メモリを有するコンピュータワークステーション - Google Patents

Abstract

(57)【要約】 複数のワークステーション（ＷＳ♯１−ＷＳ♯Ｎ）を含むＣＴＯＳ（登録商標）ネットワーク（図１）は、大きな仮想メモリがＣＴＯＳワークステーション（図２）上の複数の同時に動作するアプリケーション（図２のＡ１、Ａ２、Ａ３）の各々に能率的に設けられることを可能にする態様で、透過的にネットワークを介する仮想デマンドページングを提供する。ワークステーション上で動作する各アプリケーションに対しては、割当ページ（図４のＰｇｌ−ＰｇＮ）、および周知のクロックアルゴリズムに基づいて動作する局部クロック（図４）が設けられる。局部的方式および大域的方式の独自の組合せがページ置換えに使用されその結果利用可能なメモリページを大幅に能率よく管理できる。

Description

【発明の詳細な説明】名称 デマンドページド仮想メモリを有するコンピュータワークステーション この発明は、一般的にコンピュータワークステーション中にデマンドページド 仮想メモリを提供するための改良された方法および装置に関する。 現代のワークステーションは、典型的には複数のアプリケーションを一度に実 行することができる。各アプリケーションは通常、そのアプリケーションを実行 するためにそれ自身のメモリを要する。実行中のアプリケーションがワークステ ーションの利用可能なメモリのすべてを使い果たすと、アプリケーションは大抵 終了するようにされ、そのため十分なメモリが利用可能になったときにアプリケ ーションが再実行されることが必要になることがある。複数のアプリケーション を実行するワークステーションにおいておこり得るさらなる問題として、新しい アプリケーションがワークステーションで開始され利用可能なメモリが不十分で あるとき、新しいアプリケーションが実行することを可能にするために、実行中 のアプリケーションが強制的に終了させられかつスワップアウトされることがあ る、ということがある。そのような状況では、ワークステーションは、ユーザが 同時に実行しようと意図するすべてのアプリケーションを実行するに十分なメモ リを提供することが重要になる。結果として、ワークステーションには通常、ワ ークステーションのメモリが利用超過になることなく、ユーザが同時に実行する ことを望むすべてのアプリケーションを実行するに十分な全メモリが提供されな ければならない。 コンピュータワークステーションに利用可能なメモリを増やす１つの既知の方 法は、ワークステーションがワークステーションの主メモリにおいて現在利用可 能でないメモリを使用することを可能にする仮想メモリ構成を提供することであ る。たとえば、ワークステーションの主メモリが予め規定された数のページを記 憶することができ、それらのうちの１つまたはそれ以上が、たとえばワークステ ーションに取付けられたディスクドライブ上に含まれるページとスワップされ得 る、ページング構成を使用することが既知である。ワークステーション上で実行 するアプリケーションがワークステーションの主メモリ中に「存在しない」ペー ジを要求すると、ページフォールトとして一般に知られている状況が起こる。ワ ークステーションのオペレーティングシステムは、「存在しない」ページをディ スクからワークステーションの主メモリのフリーページ（すなわち、現在使用さ れていないページ）中に読取ることによって、このページフォールトを解決する 。ワークステーションがフリーページを有していなければ、「存在しない」ペー ジはワークステーションのメモリ中のページと置換わるようにされる。置換えら れる特定のワークステーションページ は、必要とされそうにないページを置換えのために選ぼうとするアルゴリズムに 基づいて決定される。この目的のための１つの既知のアルゴリズムは、最も長く 使用されていないページに基づいてワークステーションの主メモリ中のページを 置換える「リーストリーセントリーユーズド」（“least recently used ”） （ＬＲＵ）である。このアルゴリズムは典型的には、使用に基づいてページをリ ンクするスタックを提供することによって実現される。 そのような（ＬＲＵ）アルゴリズムの大きな欠点は、実現のためにかなりの処 理オーバヘッドを要することである。さらに、「リーストリーセントリーユーズ ド」アプローチは、実行中のアプリケーションからページが不適当な時間に置換 えられることを引き起こし得るので、このＬＲＵアルゴリズムはワークステーシ ョンが複数のアプリケーションを実行しているときにはうまく動作しない。 別の既知のタイプのページ置換えアルゴリズムは一般的に「クロック」アルゴ リズムと呼ばれ、このアルゴリズムではメモリページは（時計の周りと同様に） 単一の循環リスト状に配置される。クロックポインタ（または針）は、最後に置 換えられたページを指し、かつアルゴリズムが次の置換えページを見つけるため に起動されると時計回りに移動する。ページが置換えのテストを受けるとき、対 応のページテーブルエントリ中のアクセスビットがテストされリセットされる。 ページが最後のテスト以後参照されたこ とがあれば、そのページは現在のワーキングセットの一部であると考えられ、ポ インタは次のページに進む。ページがアクセスされておらず、「ダーティ」でな ければ（すなわちそのバックアップ記憶に書戻される必要がなければ）、それは 置換えに適している。このクロックアルゴリズムはＬＲＵアルゴリズムほどオー バヘッドを要しないが、複数のアプリケーションを同時に実行するワークステー ションに対しては依然としてうまく動作しない。 発明の概要 この発明の目的は、広くは、複数のアプリケーションを実行することができる ワークステーション中にメモリを提供するための改良された方法および装置を提 供することである。 前掲の目的に従ったこの発明のより特定的な目的は、複数のアプリケーション を実行するワークステーションにデマンドページド仮想メモリを提供することで ある。 前掲の目的の１つまたはそれ以上に従ったこの発明の別の目的は、複数のワー クステーションを含むネットワークにおいて接続されたワークステーションにデ マンドページド仮想メモリを提供することである。 前掲の目的の１つまたはそれ以上に従ったこの発明のさらなる目的は、複数の ワークステーションを含むＣＴＯＳネットワーク中にデマンドページド仮想メモ リを提供することである。 前掲の目的を達成する本願発明の特定の好ましい実施例を、ネックワーキング 能力がオペレーティングシステム中に組込まれたワークステーションのＣＴＯＳ ネットワークに適用されたものとして説明する。このタイプのオペレーティング システムは、ユニシスコーポレーション、ペンシルベニア、ブルーべル（Unysis Corporation，Blue Bell，Pennsylvania）から現在入手可能であり、登録商標 ＣＴＯＳ（登録商標）と称する。ＣＴＯＳのハードウェア、ソフトウェア、およ びプログラミングの詳細はユニシスコーポレーションから入手可能である。さら に、ＣＴＯＳの基本的な説明は、Ｅ．Ｉ．ミラー（E．I．MIller）らによる、１ ９９１年、ニュージャージー、エングルウッドクリフ、プレンティスホール（Pr entice Hall，Englewood Cliffs,New Jersey）の Exploring CTOS に見受けられ る。この本の内容はここに援用する。 述べられた好ましい実施例において、仮想デマンドページド仮想メモリがＣＴ ＯＳオペレーティングシステム中のワークステーションに透過的に設けられる。 ワークステーション上で実行する各アプリケーションには割当られたページおよ び局部クロックが与えられる。能率的な非常に大きな仮想メモリを使用するデマ ンドページングが、ワークステーション上で動作する複数のアプリケーションの 各々に境い目なく設けられることを可能にするような形で、局部的方式および大 域的方式の独自の組合せがページ置換え に使用される。さらに、ワークステーションに存在しないページは、サーバにあ るディスクドライブからネットワークを介して透過的に得られる。これは、所望 であればディスクを持たないＣＴＯＳワークステーションの使用を容易にする。 この発明の特定的性質、ならびにその他の目的、特徴、利点、および使用は、 添付図面と関連した好ましい実施例の以下の説明から明らかになるであろう。 図面の簡単な説明 図１は、複数のワークステーションを含むＣＴＯＳクラスタのブロック図であ る。 図２は、この発明に従ったＣＴＯＳワークステーションのデマンドページド仮 想メモリを有するＣＴＯＳワークステーションの好ましい実施例を示すブロック および概略図である。 図３は、図２におけるＣＴＯＳワークステーション上で動作する各アプリケー ションによって使用される典型的なページテーブルを示す図である。 図４は、図２においてＣＴＯＳワークステーション上で動作する各アプリケー ションに設けられた局部クロックの構成を示す図である。 図５は、図４に示された局部クロックの動作を示すフロー図である。 図６は、アプリケーションが「存在しない」メモリペー ジを要求した結果としてのページフォールトの発生を示すフロー図である。 図７は、ページフォールトの発生に応答して起こる動作を示すフロー図である 。 図８は、ページフォールトを引き起こしたアプリケーションがその割当ページ の最大数に達したときにページフォールトがどのように扱われるかを示すフロー 図である。 図９は、ページフォールトを引き起こすアプリケーションがそのページ最大値 に達していないがそのワークステーションが割当可能なページの最大数を使い果 たしてしまったときにページフォールトがどのように扱われるかを示すフロー図 である。 好ましい実施例の説明 図の全てにおいて、同じ参照番号および文字は同じ要素に対応する。 はじめに、図１を参照して、Ｎ個のデスクトップワークステーションＷＳ＃１ …ＷＳ♯Ｎのネットワークを含むＣＴＯＳクラスタが示されており、ワークステ ーションの１つ（たとえば、ＷＳ＃１）がサーバワークステーションとして指定 されているものとする。ＣＴＯＳはこれらのワークステーション上でＩｎｔｅｌ （登録商標）の８０Ｘ８６マイクロプロセッサファミリを使用して動作する。Ｃ ＴＯＳは、ユーザには透過的である組込みネットワーキング能力を有するモジュ ール型メッセージベースのオペレーティ ングシステムである。 図１に示されるＣＴＯＳクラスタは、ＲＳ−４２２／４８５接続を用いた簡単 なバストポロジーＢによって実現される。代替的には、ＣＴＯＳクラスタは、米 国特許第４，９１８，６８８号において説明されたようなツイストペア（電話配 線）を使用して実現され得る。 ＣＴＯＳは非常に小さなカーネル、すなわち基本的演算の一群を有する。ＣＴ ＯＳシステム環境のほとんどはシステムサービスと呼ばれるモジュールからなる 。これらのシステムサービスは、資源（ファイルシステム、通信、など）を管理 し、かつアプリケーションプログラム処理によって、および他のシステムサービ ス処理によって要求されるサービスを提供する。 ＣＴＯＳを実行するシステムは複数のプロセスすなわち実行のスレッドを有す る。プロセスとは、独立した実行のスレッドであって、そのスレッドに必要なハ ードウェアおよびソフトウェアのコンテキストを伴う。メッセージは交換部を介 して１つのプロセスから別のプロセスに渡される。交換部は、プロセスがメッセ ージを受信するのを待ったり、メッセージが処理されるのを待つために置かれた りする郵便箱に似ている。各々のプロセスにはそれが生じるとき交換部を割当て られる。ＣＴＯＳは、最もよく使用されるＣＴＯＳメッセージである特別なタイ プのメッセージ、すなわちサービスの要求を使用する。これらの要求は、所望の システムサービスを特定する要求コードを有する要求ブロックヘッダを含む特別 な定様式メッセージであって、サービスによって必要とされる他の情報すなわち 応答をどこに送るべきか、要求を誰が送っているのかなどの情報もまた伴う。Ｃ ＴＯＳカーネルの助けによって、要求はネットワークを介してユーザまたはアプ リケーションプログラムに対して透過的に移動してどのような特別なサービスを も探しあてる。 ＣＴＯＳワークステーション上で動作するアプリケーションは複数のプロセス を含み得る。たとえば、電子メールアプリケーションは典型的には少なくとも２ つのプロセスを有し得る。一方のプロセスはユーザがメールメッセージを編集す るのを可能にし、他方の処理は到着メールを監視する。これらの電子メールプロ セスは互いにワークステーションマイクロプロセッサの使用をめぐって競合し、 さらに（ワードプロセッサアプリケーションおよびコンパイラアプリケーション などの）他の実行中のアプリケーションからのプロセスとも競合する。ＣＴＯＳ ワークステーションは典型的には一つのマイクロプロセッサ（たとえば、８０４ ８６Ｉｎｔｅｌ（登録商標）プロセッサ）しか含まないので、複数のアプリケー ションが同時にワークステーション上で動作することを可能にするためにプロセ ススケジューリングが必要である。これはＣＴＯＳカーネルスケジューラによっ て行なわれる。ＣＴＯＳ内の各プロセス（実 行のスレッド）は優先順位を割当てられ、かつその優先順位に基づいてマイクロ プロセッサによって実行をスケジュールされる。プロセススケジューリングはイ ベントによって駆動される。プロセスの実行の間に入力／出力イベントなどのイ ベントが起こるときはいつでも、実行中のプロセスは優先順位のより高いプロセ スの犠牲となって、プロセッサの制御を失う。このタイプのスケジューリングは イベント駆動の優先順位付スケジューリングと呼ばれる。 ＣＴＯＳにおいて、オペレーティングシステムに通常関連する機能は、資源を 管理しかつアプリケーションプログラムプロセスおよび他のシステムサービスプ ロセスによって要求されるサービスを提供するシステムサービスによって行なわ れる。それらは前述のメッセージを使用してそれらのアプリケーションプログラ ムクライエントと通信する。 ＣＴＯＳシステムサービスの例として、ディスクファイルのオープンまたはクロ ーズまたはキーボード入力の受け入れが含まれる。それらの標準メッセージベー スのインタフェースのために、システムサービスは所望にしたがってダイナミッ クにロードされたり、置換えられたり、または取除かれたりし得る。ＣＴＯＳオ ペレーティングシステム中にシステムサービスを提供する態様はＣＴＯＳに精通 している当業者には周知である。 ＣＴＯＳの組込みネットワーキングによって可能になる特定の利点は、システ ムサービスがネットワークを介して そのサービスを要求するプロセスに対して透過的に動作し得ることである。たと えば、１つのワークステーション上のアプリケーションプロセスは、システムサ ービスがどこに存在するのかという知識がなくともあるジョブを行なわせる要求 メッセージをシステムサービスに送り出すことができる。サービスがローカルワ ークステーション上に存在しなければ、要求メッセージはネットワークを介して サービスが存在するワークステーションに自動的に送られる。応答メッセージは 同様にして戻ってくる。 先行技術のＣＴＯＳシステムでは、ワークステーション上で動作している各ア プリケーションは、ワークステーションメモリの特定の割当てられたパーティシ ョン中に存在する。加えて、ワークステーションメモリの特定の部分がアプリケ ーションの実行中に使用するために各アプリケーションに割当てられる。仮想デ マンドページングが、８０３８６Ｉｎｔｅｌ（登録商標）（およびそれより後の ）マイクロプロセッサを使用するＣＴＯＳシステム上に設けられ得ることは一般 的に認められてきたが、全体の処理能力が十分強化されるとは考えられていなか ったので、そうしたものは提供されなかった。この発明によって提供される特定 の仮想デマンドページングは他のタイプのオペレーティングシステムにも適用可 能であるが、ＣＴＯＳシステム中に使用されるとき特に有利である。なぜならそ れは複数のアプリケーションを実行しているワークステーションに おけるＣＴＯＳの処理能力をかなり向上させるからである。 この発明に従ったＣＴＯＳワークステーションに仮想デマンドページングを提 供するための好ましい態様がこれから説明される。好ましくは、このページング 能力はシステムサービスとしてＣＴＯＳに与えられ、ワークステーションにて動 作するすべてのアプリケーションによって使用される。この発明に従った仮想デ マンドページングを実現するためにそのようなＣＴＯＳシステムサービスがどの ように設計され得るがはここに与えられる説明から明らかになるであろう。この 目的のために、利用可能なメモリは全てたとえば４ＫＢ（４０００バイト）ペー ジに分割されていると考えることができる。 図２は、主メモリＭおよび局部ディスクＤを有するＣＴＯＳワークステーショ ンＷＳ上で動作する、３つのアプリケーションＡ１、Ａ２およびＡ３、ならびに それらの関連のページを概略的に示す。たとえば、Ａ１はワードプロセッサアプ リケーションプログラムであって、Ａ２は（プログラマによってプログラム開発 に使用されるような）コンパイラアプリケーションプログラムであって、Ａ３は メッセージを送受信するためのメールプログラムであり得る。 各アプリケーション（Ａ１、Ａ２、Ａ３）にはそれぞれのページテーブル（Ｐ １、Ｐ２、Ｐ３）およびそれぞれの局部クロック（Ｃ１、Ｃ２、Ｃ３）が与えら れている。各アプリケーションには典型的にはそれが実行の間に使用し 得る最大数の割当て可能なメモリページが与えられる。たとえば、ワードプロセ ッサアプリケーションプログラムＡ１には最大１００の割当ページが与えられ、 コンパイラアプリケーションプログラムＡ２には最大７０の割当ページが与えら れ、メールアプリケーションプログラムＡ３には最大５０の割当ページが与えら れる。メモリＭが全部で１２０の割当可能なページを有するものとすると、アプ リケーションがその最大数のページを割当てられているかどうかにかかわらず、 いかなるときもすべての実行中のアプリケーションに割当てられるページの合計 は１２０ページを超えることはできない。図２におけるワークステーションＷＳ はまた、ページ割当を把握するためのフリーページリストＦＰＬ、ダーティなペ ージをクリーンにするためのクリーニングキューＣＱ、および相対的なアプリケ ーションアクティビティを示すためのアクティビティキューＡＱを示すことに注 目されたい。これらはさらに以下で説明される。 図３は、各アプリケーションによって使用され得る典型的なページテーブル（ Ｐ１、Ｐ２、Ｐ３）を示す。示されているように、ページテーブル中の各エント リは、割当てられたメモリページを特定するページ特定データｐ_i、ページがそ のアプリケーションによって最後のテスト以来参照されたかどうかを示すアクセ スビットａ_i、およびページがディスクドライブなどのそのソース位置に書戻さ れな ければならない書込データを含むかどうかを示す「ダーティ」ページビットｄ_i を含む。各ページテーブルエントリはまたｏ_iによって示される他の情報も含み 得る。 ＣＴＯＳはアプリケーションが開始するときに、最大数の割当可能なページを アプリケーションに割当てる。ＣＴＯＳはまたその時に置換えが要求されるとき アプリケーションのどのページが置換えられるべきかを決定するのに使用するた めに、アプリケーションのための局部クロックを生成する。そのような局部クロ ックの基本的な構成が図４に概略的に示されており、メモリページｐｇ１、ｐｇ ２、…ｐｇＮがアプリケーションに割当てられたページを示し、かつ時計の周り のように循環リストに配置される。割当メモリページの数がそのアプリケーショ ンの最大割当て可能なページを超えることは許されない。クロックポインタ（ま たは針）ｃｐは最後に置換えられたページを指し、置換え可能なページを探すよ うに局部クロックが起動されると時計回りに進む。 置換え可能なページのための局部クロックサーチの間の動作が図５にフロー図 によって示されている。クロックポインタｃｐが次のページに進むと（ステップ ５００）、対応のページテーブルエントリのアクセスビットａ_iがセットされて いるか否かがテストされ（ステップ５０２）、そのページが最後のテスト以来そ のアプリケーションによって参照されたかどうかを判断する。このアクセスビッ トａ_i がセットされている場合（ステップ５０２）、そのページはそのアプリケーシ ョンの現在アクティブであるワーキングページの１ページであると考えられ、そ のため置換えには適格でない。そのような場合、このアクセスビットａ_iはリセ ットされ（ステップ５０４）、フロー図はそのサーチを続けるためにステップ５ ００に戻る。 一方、次のページのアクセスビットａ_iがステップ５０２においてセットされ ていない場合、ダーティページビットｄ_iがセットされているか否かが調べられ る（ステップ５０６）。ビットｄ_iがセットされておらず、ページがクリーンで ある（すなわち、それはディスクなどのそのソース位置に書戻される必要はない ）ことが示されている場合、ページは置換えに適格であると指定される（ステッ プ５０６）。しかしながら、ステップ５０６において、ビットｄ_iがセットされ 、ページはダーティであると示されている場合、そのページはクリーニングキュ ーＣＱ（図２）上に置かれ、フローはサーチを続けるためにステップ５００に復 帰する。ＣＱにおけるあるページが他に先行してクリーンにされるように、クリ ーニングキューＣＱにおけるページには優先順位が与えられ得る。ページがクリ ーンにされた後、そのそれぞれのアプリケーションのページテーブルにおけるそ のビットｄ_iはリセットされ、ページが現在クリーンであることを示す。 次に説明されるのは、図４および５に関連して上述され たように、実行中のアプリケーションに局部クロックを使用するこの発明に従っ た、大域的および局部的ページ割当方式の組合せの好ましい実施例である。この 目的のために、前述したように、最大１２０の割当可能なページを有するＣＴＯ Ｓワークステーションが、それぞれ割当ページ最大１００、５０、および３０を 有するワードプロセッサアプリケーションＡ１、コンパイラアプリケーションＡ ２、およびメールアプリケーションＡ３を同時に実行していると仮定する。これ らのアプリケーションの３つすべてがワークステーション上で動作しているとき 、アプリケーションの１つはフォアグラウンド（フォアグラウンドアプリケーシ ョンとは、キーボード、および通常ディスプレイスクリーンの少なくとも一部分 を制御するアプリケーションをいう）において動作し、他の２つのアプリケーシ ョンはバックグラウンドで動作していることが理解されるだろう。たとえば、ワ ードプロセッサアプリケーションは、ユーザがキーボードおよびディスプレイを 制御することを可能にするフォアグラウンドで動作し、それによって他のアプリ ケーションが実行していないかのようにワードプロセシング動作を行なうことが できる。コンパイラおよびメールアプリケーションはそのときバックグラウンド で動作しているだろう。たとえば、コンパイラアプリケーションは、ユーザによ って以前に開発された専用プログラムをコンパイルし、一方メールアプリケーシ ョンはメールメッセージを受 取るのを待っていることができる。メールメッセージが到着すると、スクリーン 上でマーカを点滅させることによってユーザにこのメッセージの受信を知らせる ことができる。そうすればユーザは、適切なキーボード入力をすることによって 、メールアプリケーションプログラムに切換え、メッセージを読取ることができ る。その場合メールアプリケーションがフォアグラウンドにあり、一方ワードプ ロセッサアプリケーションはコンパイラアプリケーションとともにバックグラウ ンドで動作していることになる。 図６のフロー図に示されているように、実行中のアプリケーションの１つがメ モリアクセスを要求するときはいつでも、ページテーブルが照合され（ステップ ６００）、アクセスされるべき情報を含むページがアプリケーションの割当てら れたページの１つに存在するかどうかを判断する。ページが存在しているとわか れば（ステップ６０２）、ページはアプリケーションによってアクセスされる（ ステップ６０４）。そうでなければ、ページフォールトが起こり、ページフォー ルトがどのように処理されるかを示す図７のフロー図に動作が進むことが引き起 こされる。 図７に示されているように、ページフォールトの発生は仮想デマンドページン グサービスを引き起こし（ステップ７００）、仮想デマンドページングサービス はフォールトを引き起こしたアプリケーションの実行を中断する（ステップ７０ ２）。この後ページングサービスがアプリケーシ ョンまたはワークステーションいずれかのページ最大値に達したかどうかをチェ ックし判断する（ステップ７０４）。もし達していなければ、ページングサービ スは、フリー（割当てられていない）ワークステーションメモリページ（図２の フリーページリストＦＰＬにおいて示されている）が、フォールトが生じたアプ リケーションに割当てられるようにし、その後に続いて、要求されたページがこ の新しく割当てられたページ中に読込まれ（ステップ７０６）、アプリケーショ ンがその後再開する（ステップ７０８）。ＣＴＯＳシステムが使用されているの で、このページはワークステーションの局部ディスクから、またはネットワーク を介してサーバワークステーションから、透過的に得られるという効果を奏する 。 一方、図８におけるステップ７０４において、アプリケーションまたはワーク ステーションいずれかのページ最大値に達したことがわかると、ページ置換えが 要求され、ページ最大値がアプリケーション（図８）に対してのものであるかワ ークステーション（図９）に対してのものであるかに依存して、図８または図９ に示されたようにページ置換えが行なわれる。図８に示されたアプリケーション ページ最大値に達した状況をまず考える。 図８に示されているように、アプリケーションがその割当ページ最大値に達し た状況に対するページ置換えは、アプリケーションの局部クロックにおける置換 え可能なペー ジのサーチから始まる（ステップ８００）。このサーチは図４および５に関連し て前述されたように達成される。置換え可能なページがアプリケーションの局部 クロックにあることがわかると（ステップ８０２）、アプリケーションによって 要求された「存在しない」ページが（たとえば局部またはサーバディスクから） 得られ、かつ指定された置換え可能なページの中に読込まれ（ステップ８０４） 、それに続いてアプリケーションが再開される（ステップ８０６）。 一方、図７のステップ８０２において、アプリケーションの局部クロックの周 りを１周した後置換え可能なページがないことがわかると、局部クロックの２周 目が開始される（ステップ８０８）。第１周目の間には各ページアクセスビット ａ_iがリセットされたので、第２周目の置換え可能なページのサーチは最初に生 じるクリーンなページ（すなわちｄ_iがセットされていないページ）の発見に基 づく。クリーンなページが発見されると、それは置換え可能なページとして指定 される（ステップ８１０）。フロー図はその後、前述されたステップ８０４およ び８０６に進み、「存在しない」ページが読込まれ、見つけられた置換え可能な ページに置換えられ、アプリケーションが再開する。 図８に示されているように、ステップ８１０によって、アプリケーションの局 部クロックの第２周目の間にクリーンなページが見つけられなかったことが示さ れると、フロ ーはその後ステップ８１２に進み、クリーニングキューＣＱ（図２）内にアプリ ケーションがクリーンにされるのを待ち得るページがあるかどうかが判断される 。もしそうであれば、ページがクリーンにされるまでアプリケーションは待機す る（ステップ８１４）。クリーンにされたページはその後置換え可能であるとし て指定され、フローはその後前述のようにステップ８０４および８０６に進み、 要求された「存在しない」ページが読込まれ、この指定された置換え可能なペー ジに置換えられ、さらにアプリケーションが再開される。しかしながら、ステッ プ８１２によって、アプリケーションが待ち得るクリーンにされるページがない ことが示されると、エラー表示が与えられる。 図９は、（たとえアプリケーションの割当てられたぺージ最大値に達していな いとしても）ワークステーションがその最大数の割当可能なページを使い果たし てしまったためにページフォールトが満たされない、第２のタイプの置換え状況 に対してページ置換えがどのように処理されるかを示す。前の例では、ワークス テーションは最大１２０の割当可能なページを有し、一方でワードプロセッサア プリケーションＡ１には最大１００の割当ページが与えられており、コンパイラ アプリケーションＡ２には最大５０の割当ページが与えられており、さらにメー ルアプリケーションＡ３には最大３０の割当ページが与えられていると仮定され たことが思い出されるであろう。たとえば、アプリケ ーションＡ１、Ａ２、およびＡ３にそれぞれ８０ページ、３０ページ、および１ ０ページが既に割当てられており、さらにワードプロセッサアプリケーションＡ １が「存在しない」ページを要求するためにページフォールトが生じるとすると 、ワークステーションのページ最大値１２０ぺージ（８０＋３０＋１０）に既に 達してしまっているのでワークステーションはこのページフォールトを満たすこ とができない。これは図９が関連しているページ置換え状況のタイプである。 基本的には、図９のフローでは、ページを別のアプリケーションから奪おうと 試みられる。この目的のために、ワークステーションアクティビティキューＡＱ （図２）が第１にチェックされ（ステップ９００）、ワークステーション上で動 作している他のアプリケーションのうちどれが最もアクティブでないかが決定さ れる。説明されている好ましい実施例では、このアクティビティキューＡＱは、 どのアプリケーションに最も長い期間ページフォールトが生じていないかに基づ いて、実行中のアプリケーションを順番に並べるように設計される。たとえば、 ワードプロセッサアプリケーションＡ１に最も近い時点でページフォールトが生 じ、メールアプリケーションＡ３に最も長い期間ページフォールトが生じていな いとすれば、Ａ３が最もアクティブでないアプリケーションであり、その後Ａ２ が続き、最後にＡ１が続く。そのような場合、図９のステップ９０ ０は、Ａ３を最もアクティブでないアプリケーションとして選択し、それからペ ージを奪おうとする。 図９のステップ９０２は、ステップ９００において選択された最もアクティブ でないアプリケーションがフォアグラウンド（すなわち現在ユーザによって使用 されている）状態であるかどうかをチェックし、もしそうであるならば、ページ を奪うために、次にアクティブであるアプリケーションを選ぶ（ステップ９０４ ）。フォアグラウンドアプリケーションを使用しない理由は、フォアグラウンド アプリケーションはそれがフォアグラウンドで使用されるためにそのページへの アクセスをいつ要求するとも限らないからであって、そのためそのページの１つ が奪われるようにされるべきではない。 そのようにしてページが奪われるべきアプリケーションを特定した（ステップ ９００、９０２、９０４）後、図９のフローは選ばれたアプリケーションの局部 クロックに進み（ステップ９０６）、置換え可能なページのサーチを行なうが、 そのサーチは図４、５、７に関連して前述されたものと同じ態様で達成される。 このサーチはさまざまな点で修正されてもよい。たとえば、図９のステップ９０ ６の目的のためには、局部クロックページ置換えサーチは局部クロックの１周の みに限定されてもよい。 置換え可能なページが見つかると（ステップ９０８）、フローはステップ９１ ０に進み、ステップ９０６において 見つけられた置換え可能なページが奪われ、かつページフォールトが生じたアプ リケーションに割当てられる。要求された「存在しない」ページはその後この新 しく割当てられたページ中に読込まれ、ページフォールトが生じたアプリケーシ ョンはその後再開される（ステップ９１２）。 ステップ９０８において置換え可能なページが見つからなければ、別のアプリ ケーションからページを奪う試みが行なわれる（ステップ９１４）。これは好ま しくは、フォアグラウンドアプリケーションではない、その次にアクティブでな いアプリケーションから始まり、置換え可能なページが見つかるまで他のアプリ ケーションへと続けて（ステップ９０６において行なわれた態様と同じ態様で） 他のアプリケーションの局部クロックをサーチすることによって達成される。フ ローはその後９１０に戻り、その奪う動作を完了する。置換え可能なページがま だ見つからなければ（ステップ９１６）、図７に関連して前述されたたように、 ページフォールトが生じたアプリケーションの局部クロックにおいて置換え可能 なページを見つける試みが行なわれる（ステップ９１８）。これも置換え可能な ページを見つけるに至らなければ（ステップ９２０）、エラー表示が与えられる 。代替的には、前述したように、他のアプリケーションに対してもう一度サーチ が行なわれ得る。なぜなら以前に置換え可能でなかったページも置換え可能にな ることがあるからである。そのような繰り返しサーチは、 フォールトが生じたアプリケーションの局部クロックをサーチする前に行なわれ てもよい。 ＣＴＯＳシステムにおいて大域的および局部的仮想デマンドページングが組合 せられた上述の説明は単なる例であることが理解されるべきである。というのも 構成、配置、および用途における多くの変更および変形がこの発明の範囲内で可 能であるからである。たとえば、この発明はＣＴＯＳ以外のオペレーティングシ ステムに適用可能である。また、かなり異なった実現化例およびアルゴリズムが この発明の真の範囲および精神を離れることなく与えられ得る。したがって、こ の発明は添付請求の範囲の範囲内にあるすべての可能な変更および変形を含むと 考えられ得る。

【手続補正書】特許法第１８４条の８ 【提出日】１９９４年９月１２日 【補正内容】 得る最大数の割当て可能なメモリページが与えられる。たとえば、ワードプロセ ッサアプリケーションプログラムＡ１には最大１００の割当ページが与えられ、 コンパイラアプリケーションプログラムＡ２には最大７０の割当ページが与えら れ、メールアプリケーションプログラムＡ３には最大５０の割当ページが与えら れる。メモリＭが全部で１２０の割当可能なページを有するものとすると、アプ リケーションがその最大数のページを割当てられているかどうかにかかわらず、 いかなるときもすべての実行中のアプリケーションに割当てられるページの合計 は１２０ページを超えることはできない。図２におけるワークステーションＷＳ はまた、ページ割当を把握するためのフリーページリストＦＰＬ、ダーティなペ ージをクリーンにするためのページクリーニングキューＰＣＱ、および相対的な アプリケーションアクティビティを示すためのアクティビティキューＡＱを示す ことに注目されたい。これらはさらに以下で説明される。 図３は、各アプリケーションによって使用され得る典型的なページテーブル（ Ｐ１、Ｐ２、Ｐ３）を示す。示されているように、ページテーブル中の各エント リは、割当てられたメモリページを特定するページ特定データｐ_i、ページがそ のアプリケーションによって最後のテスト以来参照されたかどうかを示すアクセ スビットａ_i、およびページがディスクドライブなどのそのソース位置に書戻さ れな ければならない書込データを含むかどうかを示す「ダーティ」ページビットｄ_i を含む。各ページテーブルエントリはまたｏ_iによって示される他の情報も含み 得る。 ＣＴＯＳはアプリケーションが開始するときに、最大数の割当可能なページを アプリケーションに割当てる。ＣＴＯＳはまたその時に置換えが要求されるとき アプリケーションのどのページが置換えられるべきかを決定するのに使用するた めに、アプリケーションのための局部クロック（図２のＣ１，Ｃ２，Ｃ３）を生 成する。そのような局部クロックの基本的な構成が図４に概略的に示されており 、メモリページ、つまりアプリケーションに割当てられたｐｇ１、ｐｇ２、…ｐ ｇＮと示されたページが、時計の周りのように循環リストに配置される。割当メ モリページの数がそのアプリケーションの最大割当て可能なページを超えること は許されない。クロックポインタ（または針）ｃｐは最後に置換えられたページ を指し、置換え可能なページを探すように局部クロックが起動されると時計回り に進む。 置換え可能なページのための局部クロックサーチの間の動作が図５にフロー図 によって示されている。クロックポインタｃｐが次のページに進むと（ステップ ５００）、対応のページテーブルエントリのアクセスビットａ_iがセットされて いるか否かかテストされ（ステップ５０２）、そのページが最後のテスト以来そ のアプリケーションによって参照されたかどうかを判断する。このアクセスビッ トａ_i がセットされている場合（ステップ５０２）、そのぺージはそのアプリケーシ ョンの現在アクティブであるワーキングページの１ページであると考えられ、そ のため置換えには適格でない。そのような場合、このアクセスビットａ_iはリセ ットされ（ステップ５０４）、フロー図はそのサーチを続けるためにステップ５ ００に戻る。 一方、次のページのアクセスビットａ_iがステップ５０２においてセットされ ていない場合、ダーティページビットｄ_iがセットされているか否かが調べられ る（ステップ５０６）。ビットｄ_iがセットされておらず、ページがクリーンで ある（すなわち、それはディスクなどのそのソース位置に書戻される必要はない ）ことが示されている場合、ページは置換えに適格であると指定される（ステッ プ５０８）。しかしながら、ステップ５０６において、ビットｄ_iがセットされ 、ページはダーティであると示されている場合、そのページはページクリーニン グキューＰＣＱ（図２）上に置かれ（ステップ５１０）、フローはサーチを続け るためにステップ５００に復帰する。ＰＣＱにおけるあるページが他に先行して クリーンにされるように、ページクリーニングキューＰＣＱにおけるページには 優先順位が与えられ得る。ページがクリーンにされた後、そのそれぞれのアプリ ケーションのページテーブルにおけるそのビットｄ_iはリセットされ、ページが 現在クリーンであることを示す。 次に説明されるのは、図４および５に関連して上述され たように、各々の実行中のアプリケーションに局部クロックを使用するこの発明 に従った、大域的および局部的ページ割当方式の組合せの好ましい実施例である 。この目的のために、前述したように、最大１２０の割当可能なページを有する ＣＴＯＳワークステーションが、それぞれ割当ページ最大１００、５０、および ３０を有するワードプロセッサアプリケーションＡ１、コンパイラアプリケーシ ョンＡ２、およびメールアプリケーションＡ３を同時に実行していると仮定する 。これらのアプリケーションの３つすべてがワークステーション上で動作してい るとき、アプリケーションの１つはフォアグラウンド（フォアグラウンドアプリ ケーションとは、キーボード、および通常ディスプレイスクリーンの少なくとも 一部分を制御するアプリケーションをいう）において動作し、他の２つのアプリ ケーションはバックグラウンドで動作していることが理解されるだろう。たとえ ば、ワードプロセッサアプリケーションＡ１は、ユーザがキーボードおよびディ スプレイを制御することを可能にするフォアグラウンドで動作し、それによって 他のアプリケーションが実行していないかのようにワードプロセシング動作を行 なうことができる。コンパイラおよびメールアプリケーションはそのときバック グラウンドで動作しているだろう。たとえば、コンパイラアプリケーションは、 ユーザによって以前に開発された専用プログラム をコンパイルし、一方メールアプリケーションはメールメッセージを受 ョンまたはワークステーションいずれかのページ最大値に達したかどうかをチェ ックし判断する（ステップ７０４）。もし達していなければ、ページングサービ スは、フリー（割当てられていない）ワークステーションメモリページ（図２の フリーページリストＦＰＬにおいて示されている）が、フォールトが生じたアプ リケーションに割当てられるようにし、その後に続いて、要求されたページがこ の新しく割当てられたページ中に読込まれ（ステップ７０６）、さらにアプリケ ーションがその後再開する（ステップ７０８）。ＣＴＯＳシステムが使用されて いるので、このページはワークステーションの局部ディスクから、またはネット ワークを介してサーバワークステーションから、透過的に得られるという効果を 奏する。 一方、図８におけるステップ７０４において、アプリケーションまたはワーク ステーションいずれかのページ最大値に達したことがわかると、ページ置換えが 要求され、ページ最大値がアプリケーション（図８）に対してのものであるかワ ークステーション（図９）に対してのものであるかに依存して、図８または図９ に示されたようにページ置換えが行なわれる。図８に示されたアプリケーション ページ最大値に達した状況をまず考える。 図８に示されているように、アプリケーションがその割当ページ最大値に達し た状況に対するページ置換えは、アプリケーションの局部クロックにおける置換 え可能なペー ーはその後ステップ８１２に進み、ページクリーニングキューＰＣＱ（図２）内 にアプリケーションがクリーンにされるのを待ち得るページがあるかどうかが判 断される。もしそうであれば、ページがクリーンにされるまでアプリケーション は待機する（ステップ８１４）。クリーンにされたページはその後置換え可能で あるとして指定され、フローはその後前述のようにステップ８０４および８０６ に進み、要求された「存在しない」ページが読込まれ、この指定された置換え可 能なページに置換えられ、さらにアプリケーションが再開される。しかしながら 、ステップ８１２によって、アプリケーションが待ち得るクリーンにされるペー ジがないことが示されると、エラー表示が与えられる。 図９は、（たとえアプリケーションの割当てられたページ最大値に達していな いとしても）ワークステーションがその最大数の割当可能なページを使い果たし てしまったためにページフォールトが満たされない、第２のタイプの置換え状況 に対してページ置換えがどのように処理されるかを示す。前の例では、ワークス テーションは最大１２０の割当可能なページを有し、一方でワードプロセッサア プリケーションＡ１には最大１００の割当ページが与えられており、コンパイラ アプリケーションＡ２には最大５０の割当ページが与えられており、さらにメー ルアプリケーションＡ３には最大３０の割当ページが与えられていると仮定され たことが思い出されるであろう。たとえば、アプリケ ０は、Ａ３を最もアクティブでないアプリケーションとして選択し、それからペ ージを奪おうとする。 図９のステップ９０２は、ステップ９００において選択された最もアクティブ でないアプリケーションがフォアグラウンド（すなわち現在ユーザによって使用 されている）状態であるかどうかをチェックし、もしそうであるならば、ページ を奪うために、次にアクティブであるアプリケーションを選ぶ（ステップ９０４ ）。フォアグラウンドアプリケーションを使用しない理由は、フォアグラウンド アプリケーションはそれがフォアグラウンドで使用されるためにそのページへの アクセスをいつ要求するとも限らないからであって、そのためそのページの１つ が奪われるようにされるべきではない。 そのようにしてページが奪われるべきアプリケーションを特定した（ステップ ９００、９０２、９０４）後、図９のフローは選ばれたアプリケーションの局部 クロックに進み（ステップ９０６）、置換え可能なページのサーチを行なうが、 そのサーチは図４、５、８に関連して前述されたものと同じ態様で達成される。 このサーチはさまざまな点で修正されてもよい。たとえば、図９のステップ９０ ６の目的のためには、局部クロックページ置換えサーチは局部クロックの１周の みに限定されてもよい。 置換え可能なページが見つかると（ステップ９０８）、フローはステップ９１ ０に進み、ステップ９０６において 見つけられた置換え可能なページが奪われ、かつページフォールトが生じたアプ リケーションに割当てられる。要求された「存在しない」ページはその後この新 しく割当てられたページ中に読込まれ、ページフォールトが生じたアプリケーシ ョンはその後再開される（ステップ９１２）。 ステップ９０８において置換え可能なページが見つからなければ、別のアプリ ケーションからページを奪う試みが行なわれる（ステップ９１４）。これは好ま しくは、フォアグラウンドアプリケーションではない、その次にアクティブでな いアプリケーションから始まり、置換え可能なページが見つかるまで他のアプリ ケーションへと続けて（ステップ９０６において行なわれた態様と同じ態様で） 他のアプリケーションの局部クロックをサーチすることによって達成される。フ ローはその後９１０に戻り、その奪う動作を完了する。置換え可能なページがま だ見つからなければ（ステップ９１６）、図８に関連して前述されたたように、 ページフォールトが生じたアプリケーションの局部クロックにおいて置換え可能 なページを見つける試みが行なわれる（ステップ９１８）。これも置換え可能な ページを見つけるに至らなければ（ステップ９２０）、エラー表示が与えられる 。代替的には、前述したように、他のアプリケーションに対してもう一度サーチ が行なわれ得る。なぜなら以前に置換え可能でなかったページも置換え可能にな ることがあるからである。そのような繰り返しサーチは、 【手続補正書】特許法第１８４条の８ 【提出日】１９９５年１月２３日 【補正内容】 請求の範囲 １．相互に接続された複数のワークステーションを含み、あるワークステーシ ョンが複数のアプリケーションを同時に実行することができるネットワークにお いて、 物理メモリを前記ネットワークに設けるステップと、 前記物理メモリを複数のページに分割するステップと、 アプリケーションが動作しているときアプリケーションによって使用可能なペ ージの状態を示すための局部ページテーブルを各アプリケーションに対して設け るステップと、 アプリケーションがその局部ページテーブルに現在存在していないページへの アクセスを要求するときページフォールトを生成するステップと、 ページフォールトを満たすために置換えが要求されるとき置換え可能なページ を特定するステップとを含み、前記特定するステップは、まずページフォールト が生じたアプリケーションの局部ページテーブルをサーチし、もし置換え可能な ページが見つからなければ、その後置換え可能なページを見つけるために別の実 行中のアプリケーションの局部ページテーブルをサーチすることによって行なわ れ、選ぶべき他の実行中のアプリケーションが複数あるとき前記別の実行中のア プリケーションの選択は、どれが最もアクティブでないかに基づいて決定され、 さらに、 前記別のアプリケーションから得られたときの特定された置換え可能なページ を、ページフォールトが生じたアプ リケーションの局部ページテーブルに割当てるステップと、 アクセスされた存在していないページを、特定された置換え可能なページ中に 読込むステップとを含む、方法。 ２．最もアクティブでないアプリケーションは、実行中のアプリケーションの ページフォールト動作に基づいて決定される、請求項１に記載の方法。 ３．最もアクティブでないアプリケーションは、ページフォールトが最も長い 期間で起こっていないアプリケーションに基づいて決定される、請求項１に記載 の方法。 ４．各局部テーブルはクロックアルゴリズムに基づく置換え方式を有する、請 求項１に記載の方法。 ５．前記別のアプリケーションの選択はまた、アプリケーションがバックグラ ウンドで実行しているかフォアグラウンドで実行しているかにも依存している、 請求項１に記載の方法。 ６．前記特定するステップは、前記別のアプリケーションのサーチによっても 置換え可能なページを見つけることができなければさらに実行中のアプリケーシ ョンの局部ページテーブルをサーチするステップを含む、請求項１に記載の方法 。 ７．前記ネットワークはＣＴＯＳネットワークであって、前記ワークステーシ ョンはＣＴＯＳワークステーションである、請求項１に記載の方法。 ８．相互に接続された複数のワークステーションを含み、 ワークステーション間のネットワーキングがオペレーティングシステム中に組込 まれているネットワークにおいて、 前記ネットワークに設けられた物理メモリを含み、前記物理メモリは複数のペ ージに分割され、さらに、 複数のアプリケーションを同時に実行するための少なくともの１つのワークス テーションを含み、前記ワークステーションは前記実行中のアプリケーションに 割当可能な複数のページを含むメモリを有し、 アプリケーションが実行中であるときアプリケーションによって使用可能なペ ージの状態を示すための局部ページテーブルを各アプリケーションに対して設け 、さらに、 アプリケーションがその現在割当てられたページ中に存在しないページへのア クセスを要求するとき、ページフォールトを生成する手段と、 ページフォールトに応答して、ページフォールトが生じたアプリケーションの 局部ページテーブルを最初にサーチし、置換え可能なページが見つからなければ 、その後置換え可能なページを見つけるために別の実行中のアプリケーションの 局部ページテーブルをサーチすることによって、要求された時に置換え可能なペ ージを特定するための手段とを含み、選択すべき他の実行中のアプリケーション が複数あるとき前記別の実行中のアプリケーションの選択はどれが最もアクティ ブでないかに基づいて決定され、さらに、 前記別のアプリケーションから得られたときの特定され た置換え可能なページを、ページフォールトが生じたアプリケーションの局部ペ ージテーブルに割当てるための手段と、 アクセスされた存在しないページを、特定された置換え可能なページ中に読込 むための手段とを含む、組合せ。 ９．最もアクティブでないアプリケーションは実行中のアプリケーションのフ ォールト動作に基づいて決定される、請求項８に記載の発明。 １０．最もアクティブでないアプリケーションは、最も長い期間ページフォー ルトが生じていないアプリケーションに基づいて決定される、請求項８に記載の 発明。 １１．前記存在しないページは、ネットワークを介して別のワークステーショ ンから得られる、請求項８に記載の発明。 １２．各局部テーブルはクロックアルゴリズムに基づいた置換え方式を有する 、請求項８に記載の発明。 １３．前記別のアプリケーションの選択はまた、アプリケーションがフォアグ ラウンドで実行しているかバックグラウンドで実行しているかにも依存している 、請求項８に記載の発明。 １４．最もアクティブでないアプリケーションは、実行中のアプリケーション のページフォールト動作に基づいている、請求項８に記載の発明。 １５．前記ネットワークはＣＴＯＳネットワークであっ て、前記ワークステーションはＣＴＯＳワークステーションである、請求項８に 記載の発明。

Claims (1)

1. 【特許請求の範囲】 １．複数のＣＴＯＳワークステーションを含み、あるワークステーションが複 数のアプリケーションを同時に実行することができるＣＴＯＳネットワークにお いて、 物理メモリを前記ネットワークに設けるステップと、 前記物理メモリを複数のページに分割するステップと、 アプリケーションがその局部ページテーブルに現在存在していないページへの アクセスを要求するときページフォールトを生成するステップと、 ページフォールトを満たすために置換えが要求されるとき置換え可能なページ を特定するステップとを含み、前記特定するステップは、まずページフォールト が生じたアプリケーションから、またはワークステーション上で実行中の別のア プリケーションから、置換え可能なページを特定することを選択的に可能にする 局部的方式および大域的方式を組合せたものに基づいて行われ、さらに、 前記別のアプリケーションから選択されたときの特定された置換え可能なペー ジを、ページフォールトが生じたアプリケーションに割当てるステップと、 アクセスされた存在していないページを、特定された置換え可能なページ中に 読込むステップとを含む、方法。 ２．優先順位を基本にして、局部的置換え方式はクロックアルゴリズムに基づ き、大域的置換え方式は、置換可能なページを別のアプリケーションから奪うこ とに基づく、 請求項１に記載の方法。 ３．前記優先順位は前記ワークステーション上で実行するアプリケーションの 相対アクティビティに依存する、請求項２に記載の方法。 ４．前記優先順位もまた、アプリケーションがバックグラウンドで動作してい るか、フォアグラウンドで動作しているかに依存する、請求項３に記載の方法。 ５．前記置換えは、前記ページフォールトを満たすように要求されるとき実行 中のアプリケーションのどちらが置換え可能なページのためにサーチされるべき かを選択することを含み、選択されたアプリケーションにおける置換え可能なペ ージは、クロックアルゴリズムにしたがって選択される、請求項１に記載の方法 。 ６．前記置換えは、前に選択されたアプリケーションが置換えられ得るページ を有さないとき置換え可能なページをサーチすべく別のアプリケーションを選択 する、請求項５に記載の方法。 ７．複数のＣＴＯＳワークステーションを含み、ワークステーション間のネッ トワーキングがＣＴＯＳオペレーティングシステム中に組込まれているＣＴＯＳ ネットワークにおいて、 前記ネットワークに設けられた物理メモリを含み、前記物理メモリは複数のペ ージに分割され、さらに、 複数のアプリケーションを同時に実行するための少なく ともの１つのワークステーションを含み、前記ワークステーションは前記実行中 のアプリケーションに割当可能な複数のページを含むメモリを有し、 アプリケーションがその現在割当てられたページ中に存在しないページへのア クセスを要求するとき、ページフォールトを生成する手段と、 ページフォールトに応答して、ページフォールトが生じたアプリケーションか ら、またはワークステーション上で実行中の別のアプリケーションから、置換え 可能なページを特定することを選択的に可能にする局部的および大域的置換え方 式を組合せたものに基づいて要求された時に置換え可能なページを特定するため の手段とを含み、さらに、 前記別のアプリケーションから選択されたときの特定された置換え可能なペー ジを、ページフォールトが生じたアプリケーションに割当てるための手段と、 アクセスされた存在しないページを、特定された置換え可能なページ中に読込 むための手段とを含む、組合せ。 ８．前記存在しないページは、ネットワークを介して別のワークステーション から得られる、請求項７に記載の発明。 ９．優先順位を基本にして、局部的置換え方式は、クロックアルゴリズムに基 づき、大域的置換え方式は、置換え可能なページを別のアプリケーションから奪 うことに基づく、請求項７に記載の発明。 １０．前記優先順位は、前記ワークステーション上で実行するアプリケーショ ンの相対アクティビティに依存する、請求項７に記載の発明。 １１．前記優先順位もまた、アプリケーションフォアグラウンドで実行してい るかバックグラウンドで実行しているかに依存する、請求項１０に記載の発明。