JPS6032222B2 - アクセスサ−チ方式 - Google Patents

Description

【発明の詳細な説明】 本発明はアクセスサーチ方式に関し、特に仮想記憶方式
において実空間が必要になったとき不要なべ‐ジァドレ
スを極めて容易に検出することのできるアクセスサーチ
方式に関する。

データ処理装置ではデータの処理能力の向上のために、
主記憶装置の有する記憶装置よりもはるかに大きな論理
記憶領域を定めて、プログラムがこれを使用する、いわ
ゆる仮想記憶方式が使用されている。

この場合補助記憶手段として磁気ディスク等が使用され
ることになる。このような仮想記憶方式では、仮想記憶
領域の仮想空間を主記憶領域の実空間に対応させるため
に、セグメント・テーブルやページテーブル等のマツピ
ング・テーブルが使用される。また、データ処理に際し
て実空間が必要になったとき、現在不必要と思われる仮
想空間を補助記憶装置に退避させ実空間領域を確保する
ことが行なわれているが、このような場合、上記補助記
憶装置に退避すべきページを指示するために参照ビット
を付加しておき、これの有無をサーチすることが行なわ
れている。通常このページの大きさは恋バイト、あるし
、は必バイトであるが、仮想空間が４Ｙバイトの大きさ
の場合には、１ページ巡バイトの場合で１０００頁とな
り、１８仇バイトの大きさの場合には４０００頁にもな
る。

そして、従来では、上記ページテーブル等に付与された
参照ビットをサーチする作業は、ソフトにより行なって
いたので中央処理装置に与える負垣が大きいという欠点
があり、実空間の容量が大きくなって、例えば１８Ｍバ
イト等にもなると、この退避すべきページをサーチする
ためのテーブルサーチ時間が非常に大きくなり、このた
めにデータ処理本来の処理能率に悪影響が生じ、これを
無視することができなくなる。したがって本発明は、こ
のような問題点を改善して、上記のページのサーチをプ
ログラムで行なう代りにハ一日こより能率的に行なうよ
うにしたアクセスサーチ方式を提供することを目的とし
たものである。そしてこのために本発明におけるアクセ
スサーチ方式では、主メモリを複数の区分に設定し、各
区分毎にそれが使用されたことを示す参照データを付与
しこの参照データにもとづき上記設定区分の内容を更新
するようにした主メモリ管理方式において、上記複数の
区分の使用回数が記入され主メモ川こ対する一定アクセ
ス回数毎に上位から下位に少なくとも１ビットシフトさ
れる参照テーブルを有する使用データ保持手段と、主メ
モリに対するアクセス回数を計数するアクセス計数手段
と、上記使用データ保持手段からデータをレベル付けし
てこれより参照データを諸出すようにしたレベル選択競
出手段と、上記使用データ保持手段を読出すためのアド
レスを発生するアドレス発生手段を設け、主メモ川こお
ける新しく利用できる区分をサーチする場合には上記ア
ドレス発生手段によるアドレス情報にもとづき上記使用
データ保持手段を読み出し、この諸出しデータをレベル
選択することにより新しく利用できる区分を決定するよ
うにしたことを特徴とする。先ず本発明の一実施例を詳
述するに先立ち、本発明の概略を第１図について説明す
る。

第１図は、後述するデータ保持回路の参照テーブル１を
具体的に示したものであって、例えば実〆モリに対応す
るページ単位にその使用頻度であるアクセス回数を示す
ものである。

第１図は、実〆モリが０〜ｎページに区分されていると
き、そのページ毎の使用状態を表示したものである。

初期状態では各ページともアクセスされていないので、
アクセス回数はいずれも０であるが、アクセスされるご
とに回数が記入される。そして主メモリの新しく利用で
きる区分を選定する場合に、この参照テーブルを論出し
てその使用頻度の少ないものを選出し、新しく利用でき
るものとするものである。以下本発明の一実施例を第２
図〜第６図にもとづき説明する。

第２図は本発明の一実施例構成を示し、第３図はアドレ
スサーチ回路の構成を示し、第４図イはしベル選択回路
の構成を示し、同口は使用回数シフト状態を示し、第５
図はしベル優先回路の構成を示し、第６図はデータチェ
ック回路の構成を示す。

図中、１はアドレス・レジスタ、２はデータ保持回路、
３はアドレスサーチ回路、４はシフトクロツク作成回路
、５はしベル選択回路、６はデータチェック回路、７，
８，はオア回路、９は有効アドレス・レジスタ、１０は
更新回路、１１はシーケンス回路、１２はカウンタ、１
３はしベル優先回路、１４一０〜１４−ｎはインバータ
、１５，１６はアンド回路、１７はオア回路、１８はフ
リツプフロツプ、１９はインバータ、２０はアンド回路
、２１はオア回路、２２，２３はアンド回路、２４はオ
ア回路、２５はフリップフロツプ、、２６はインバータ
、２７はアンド回路、２８はオア回路、２９はインバー
タ、３０，３１はアンド回路、３２はフリツプフロツプ
、３３はインバータ、３４はアンド回路、３５はオア回
路、３６はアンド回路、３７は謙出データ保持部、３８
−０〜３８−３はインバータ、３９〜４５はアンド回路
、４６はオア回路である。

アドレス・レジスターは、主メモリに対してアクセスが
行なわれたとき、そのアドレスに対応する、参照テーブ
ル１のページアドレスが記入されるものである。

データ保持回路２は、主メモリのページ区分に対するア
クセス回数が記入された、第１図に示す参照テーブルと
これに対するアクセス回数を記入するアクセス回数計数
回路とシフト回路が設けられている。そして後述するよ
うに、シフト信号ＳＨＩＦＴが印加されたとき、このア
クセス回数を表示するこの表示情報を、上位から下位に
１ビットシフトして表示するものである。アドレスサー
チ回路３は、新しく利用できるページを選択するときに
必要な、参照テーブルを謙出すためのアドレスを作成し
たり、また参照テーブルからデータを読出す場合にこの
データを選別するために必要な選別基準作成指示用の制
御信号を発生するものであり、第３図に示す如く、有効
アドレスシスタ９、更新回路１０およびシーケンス回路
１１を有する。ここで有効アドレスレジスタ９はその前
回に更新されたページアドレスが記入されるレジスタで
ある。更新回路１０は十１カウンタであって、アクセス
サーチ指令であるサーチ信号ＳＥＡＲＣＨが伝達された
ときにこの有効アドレスレジスタ９にセットされたペー
ジアドレスを順次十１してこれを更新するものである。
そしてシーケンス回路１１は、上記サーチ信号ＳＥＡＲ
ＣＨが印加されたとき、上記参照テーブルをサーチして
必要とする新しく利用できるページを検出するための各
種信号を順次発生したり、あるいはこの参照テーブルの
サーチにもとづく信号に応じた各種信号を順次発生する
ものである。

シフトクロック作成回路４は主メモリへのアクセス回数
が一定の回数Ｎ‘こなる度毎にシフト信号ＳＨＩＦＴを
発生してデータ保持回路２およびレベル選択回路５にこ
れを送出し、参照テーブルの表示を下位にシフトさせた
り、またそのレベル選択基準を変更し、参照テーブルを
サーチするための頻度レベルを変えるものである。レベ
ル選択回路５は参照テーブルをアクセスして新しく利用
できるページをサーチする場合に使用されるレベル選択
信号Ｐｏ，Ｐ，，・・・Ｐｎを発生する回路であって、
第４図イに示すように、カウンタ１２およびレベル優先
回路１３を有する。

このカウンター２は参照テーブルをサーチ開始後どの位
連続サーチを行なったかということを示すものであって
、カウンタ１２がオーバフロ−したときオーバフロー信
号ＯＶＲを出力し、サーチするために必要なしベルを１
つ上のレベルに上げるものである。このためしベル優先
回路１３より渡度レベルを示す基準信号Ｐｏ，Ｐ，，Ｐ
２・・・Ｐｎを送出する機能を有する。この場合、最小
の頻度レベルでサーチを行なう信号がＰｏであり、以下
Ｐ，，Ｐ２・・・Ｐｎになるにつれてアクセス頻度のレ
ベルが上がる。そして最上位レベルの基準信号Ｐｎによ
るも新しく利用できるページが検出できない場合にエラ
ーとなりエラー信号ＥＲＲＯＲを出力する。またアクセ
ス頻度は時系列的に最新情報を表示する必要があるため
、主メモリへのアクセス回数が一定回数毎に上記シフト
クロツク作成回路４から印加されるシフト信号ＳＨ『Ｔ
によりそのアクセス回数を示すデータを上位から下位に
１ビットシフトする。すなわち、第４図口に示すように
、あるべ−ジの使用回数が４ビット表示で「０１０１」
と表示されているときに、これを「００１０」と変更し
、時系列的にみてできるだけ最近のアクセス頻度を加味
した表示を行なわせるものである。なお、第４図イにお
けるレベル優先回路１３は、第５図イに示すように構成
されている。

レベル優先回路１３から出力される頻度レベル基準信号
Ｐｏ，Ｐ，，Ｐ２・・・Ｐｎはいずれか１つのみオンと
なる。そして、第５図口に示すように、そのレベルは、
第４図イにおけるカウンタ１２のオーバフロー信号ＯＶ
Ｆにより上位に移り、シフトクロツク作成回路４からの
シフト信号ＳｍＦＴで下位に移る。そして初期値はフリ
ップフロップ１８が頻度レベル基準信号Ｐｏを出力する
ように設定されている。データチェック回路６は、デー
タ保持回路２に設定された参照テーブルから読出された
使用頻度数にもとづき新しく利用できるページを検出す
るためのものであって、参照テーブルから読出された使
用頻度数がセットされる読出データ保持部３７を有する
。

いまもっとも低いレベル、つまり一度もアクセスされた
ことのないページを検出する場合にはＰ。

を「１」に設定してアンド回路４２をオン状態にする。
この状態でデータ保持回路２から参照テーブルを順次読
出して、その使用回数を謙出データ保持部３７にセット
する。もしも使用回数が０のときは、謙出データ保持部
３７に「００００Ｊがセットされ、インバータ３８一０
〜３８一３はいずれも「１」を出力するので、アンド回
路３９は「１」を出力し、これによりアンド回路４２も
「１」を出力し、オア回路４６から「１」が出力され、
そのときの、第３図に示す有効アドレスレジスタ９にセ
ットされたページ数を読出すことにより、新しく利用で
きるページが選出できる。もしも使用回数０のものが検
出されないときには、アンド回路３９から「１」が出力
されないので、後述するように頻度レベル基準信号Ｐ，
が「１」になり、ァンド回路４３がオン状態になる。こ
の状態で参照テーブルが読出されると、使用頻度が２以
下のものが読出されたとき、読出データ保持部３７には
「００倣」がセットされ、その上位３ビットがオール「
０」のため、アンド回路４０が「１」を出力し、かくし
てアンド回路４３およびオァ回路４６が「１」を出力し
、使用頻度が２以下のレベルでの更新すべきページが選
出されることになる。以下、第２図に示す回路の動作に
ついて説明する。

（１’ いま、データ処理装置の初期状態においてデー
タ保持回路２における参照テーブルには、どの頁の使用
頻度も０なのでオール０が記入され、また、レベル選択
回路５はフリップフロップ１８から頻度レベル基準信号
Ｐｏが出力されるように設定されている。

■ そしてデータ処理装置が動作を開始し主メモリへの
アクセスが行なわれると、そのアクセス先に応じた使用
頻度をデータ保持回路２の参照テーブルに記入するため
に必要なべージに対応するライトアドレスがオア回路７
を経由してアドレスレジスタ１にセットされる。

このとき主メモ川こ対するアクセス信号が、オア回路８
を経由して、このデータ保持回路２にも印加されるため
、上言己アドレスレジス夕１にセットされたページに１
が記入される。そしてこのアクセス信号はシフトクロッ
ク作成回路４にも印加されるので、このシフトクロツク
作成回路４にあるカウンタが主メモリへのアクセス回数
１を計数する。このようにして主メモリへのアクセスが
行なわれる毎にカウンタが十１される。｛３’ このよ
うにしてデータ処理が行なわれているときに「主メモ川
こおける新しく利用できる区分をサーチすることが必要
になったとき、サーチ信号ＳＥＡＲＣＨがアドレスサー
チ回路３に印加される。

これにより、第３図に示す如く、シーケンス回路１１は
サーチ開始信号をレベル選択回路５に送出してこれより
頻度レベル基準信号Ｐｏをデータチェック回路６に出力
させるとともに、更新回路１０を動作させる。これによ
り有効アドレスレジスタ９はチェックアドレスとして先
ず初期設定の０を出力し、以下１，２・・・ｎを出力す
ることになる。この０，１…ｎのチェックアドレスは、
オア回路７を経由してアドレスレジスターに順次印加さ
れるので、これによりデータ保持回路２内の参照テーブ
ルが０ページ、１ページ・・・と順次謙出されてその使
用回数がデータチェック回路６の読出データ保持部３７
にセットされる。このとき頻度レベル基準信号Ｐｏが出
力されているのでアンド回路４２がオン状態になってい
る。そして上記参照テーフルから読出された各ページ０
，１，・・・の使用回数が０のものがあるときは、この
謙出データ保持部３７にオール０がセットされるので、
各ィンバータ３８一０〜３８一３はいずれも「１」を出
力し、アンド回路３９は「１」を出力することになる。
そしてこのアンド回路３９からの出力「１」がアンド回
路４２およびオア回路４６を経由してチェックデータ信
号Ｃとなり、アドレスサーチ回路３のシーケンス回路１
１に印加される。これによりそのとき有効アドレスレジ
スタ９に記入されたアドレスが新しく利用できるページ
のサーチアドレスとして出力され、これにもとずき利用
できる領域が識別できる。また、レベル選択回路５に設
けられたカウン夕１２はシーケンス回路１１から伝達さ
れたサーチ開始信号でリセットされる。そしてアドレス
サーチ回路３が参照テーブルをアクセスするアドレスを
出力し、新しく利用できるページをサーチするとき、ア
ドレスを出力しても利用できるページが検出できなかっ
たとき、そのアドレス信号を出力する毎にカウン夕１２
に対する更新信号（十１信号）である次サーチ信号を出
力する。そして参照テーブルの全ページをアクセスした
にもかかわらず利用できるページが検出できなかったと
き、オ−バーフロー信号ＯＶＦを出力する。

そしてレベル優先回路１ ３から出力される頻度レベル
基準信号をレベルアップさせるものである。‘４）しか
しながら、例えばいずれのページも最底１回以上使用さ
れている場合には、上記読出データ保持部３７にオール
０がセットされないため、更新回路１０が十１して最終
ページｎを計数してもアンド回路３９，４２は出力「１
」を生せず、したがってオア回路４６はチェックデータ
信号Ｃを出力しない。

これによりシーケンス回路１１は次サーチ信号をレベル
選択回路６に送出する。このときカウンター２は上記更
新回路１０と同様に参照ページの全ページ数を計数し終
り、オーバーフロー信号ＯＶＦをレベル優先回路１３に
出力する。かくして第５図イに示すように、アンド回路
２２に頻度レベル基準信号Ｐｏと該オーバーフロー信号
ＯＶＦが印加されることになるので、このアンド回路２
２は「１」を出力し、これがオア回路２４を経由してフ
リップフロップ２５のセット端子Ｓに印加される。かく
してフリツプフロツブ２５がセットされて頻度レベル基
準信号Ｐ，を出力する。このとき上記オーバーフロー信
号ＯＶＦにより、フリップフロツプ１８はオア回路２１
を経由してそのリセット端子Ｒに「１」が印加され、頻
度レベル基準信号Ｐｏは落ちることになる。■ かくし
て今度は頻度レベル基準信号Ｐ，が出力され、第６図に
示すように、アンド回路４３がオン状態になる。このよ
うな状態でアドレスサーチ回路３の更新回路１０が動作
してチェックアドレスを発生し、参照テーブルの使用回
数を日頃次読出す。これにより読出データ保持部３７に
セットされた上位３ビットがオール０のとき、すなわち
使用回数が１のページが謙出されたとき、インバータ３
８−０〜３８一２はいずれも「１」を出力するので、ア
ンド回路４０は「１」を出力し、これがアンド回路４３
およびオア回路４６を経由してチェークデータ信号Ｃと
なり、シーケンス回路Ｃに伝達される。これによりシー
ケンス回路１１は更新回路１１の動作を停止させ、その
とき有効アドレスレジスタ９にセットされているページ
アドレスＧを利用できるページのサーチアドレスと出力
し、かつアクセス済信号を該ページに記入し、その後の
サーチ信号により検出されないようにする。そしてレベ
ル選択回路５にも利用できるページの検出を報告し、カ
ウンタ１２を停止させる。そしてサーチの終了を示すサ
ーチヱンド信号ＳＥＡＲＣＨＥＮＤを出力する。

■ しかしながら頻度レベル基準信号がＰ，になっても
利用できるページが検出できないときは更にこれをアッ
プして頻度レベル基準信号をＰ２，Ｐ３・・・とアップ
する。

そして最高レベルの頻度レベル基準信号Ｐｎによるも更
新ページが検出できないとき、レベル優先回路１３はェ
ラ−信号を発生し、これをアドレスサーチ回路３のシー
ケンス回路１１に出力するので、これによりシーケンス
回路１１はサーチェラー信号ＳＥＡＲＣＨＥＲＲＯＲを
発生して、利用できるページが検出できなかったことを
報告する。

このサーチェラー信号ＳＥＡＲＣＨＥＲＲＯＲが発生し
たとき、ソフト的に処理ルーチンが定められていない時
はハード的に処理をする必要がある。

この場合、どのページアドレスも使用できないというこ
とであるので条件は同一である。それ故、例えばハード
的にデータ保持回路およびレベル優先回路をすべてリセ
ットし、全くページを使用していない条件でサーチを開
始して、利用できるページのサーチアドレスを決定すれ
ばよい。‘７｝ また上記｛５｝‘こ記載した如く、頻
度レベル基準信号Ｐ，においてページアドレスＧが検出
されたあとで再び新しく利用できるページを求めるサー
チ信号が伝達されたとき、シーケンス回路１１はサーチ
開始信号をレベル選択回路５のカウンタ１２に印加する
とともに更新回路１０を動作させる。

そしてこの更新回路１０およびカウンタ１２を上記ペー
ジアドレスＧ以降より十１させる。したがってチェック
アドレスとしてはこのページアドレスＧに十１した（Ｇ
＋１）が出力されてアドレスレジスタ１にセットされ、
参照テーブルが頻度レベル基準信号Ｐ，でサーチされる
ことになる。このようにして利用できるページが検出で
きなければ頻度レベル基準信号がＰ，，Ｐ２１・・と順
次アップすることになる。そして上記（６｝と同様の処
理が行なわれる。〔８｝ また上記｛５〕において新し
く利用できるページアドレスＧが検出されたあとサーチ
信号ＳＥＡＲＣＨが伝達されず、その間に主メモリに対
するアクセスが規定回数行なわれたときは、シフトクロ
ック作成回路４からシフト信号ＳＨＩＦＴが出力される
。

これによりデータ保持回路２の参照テーブルに記載され
た使用回数は、上記の如く、１ビットシフトされる。そ
してこのシフト信号ＳＨＩＦＴがレベル選択回路５のレ
ベル優先回路１３にも印加される。このとき上記の如く
ページアドレスＧが検出されたあとサーチが行なわれて
いないので頻度レベル基準信号Ｐ，が出力されている。
したがってこのときシフト信号ＳＨＩＦＴの印加により
、第５図イにおけるアンド回路３０が「１」を出力（こ
のとき頻度レベル基準信号Ｐ２は「０」でありィンバー
タ２６は「１」を出力している）し、オア回路２８を経
由してリセット信号がラツチ２５のリセット端子Ｒに印
加される。かくして頻度レベル基準信号Ｐ，はオフにな
る。またこの頻度レベル基準信号Ｐ，がオフになるに先
立ち、上記シフト信号ＳＨＩＦＴはアンド回路１ ６に
印加される。このとき頻度レベル基準信号Ｐ，はいまだ
オン状態にあるので、アンド回路１６は「１」を出力し
、これがオア回路１７を経由してフリップフロッブ１８
のセット端子に印加され、頻度レベル基準信号Ｐｏがオ
ンになる。かくして主メモ川こ対するアクセス回数があ
る一定値Ｎになる度にシフト信号ＳＨＩＦＴが出力され
、頻度レベル基準信号は１つ下のレベルに下がるが、頻
度レベル基準信号がＰｏの場合には、シフト信号ＳＨＩ
ＦＴが出力され、参照テーブルの使用回数が１ビットシ
フトされてもそのままである。なお、上託しベル優先回
路１３として第５図イに示す回路に代り、第５図′、に
示す回路を使用しても、同様な制御を行なうことができ
る。次にデータ保持回路の構成例を第７図および第８図
について説明する。

第７図はデータ保持回路２の構成を示し、第８図はその
参照テーブルの説明図である。データ保持回路２には複
数段のレジスタＲ３，Ｒ２，Ｒ，，Ｒｏが設けられ、そ
れぞれ参照テーフルが記入されるものである。

そしてそのページに対するアクセスの有無がレジスタＲ
３における参照テーブルに記入され、また主メモリへの
アクセス回数が一定の値Ｎに達する毎にシフトクロツク
作成回路４から発生されるシフト信号ＳＨＩＦＴにより
レジスタＲ３の内容は順次次段のレジスタに転送される
ように構成されている。初期状態では各ページともアク
セスされてし、なし、ので、参照テーブルにはアクセス
の行なわれたことを示す「１」は記入されていない。

そしてこのページ０〜ｎに対してアクセスが行なわれた
とき、第８図イに示すように、レジスタＲ３においてそ
のアクセスされたページに「１」が記入される。そして
主メモリに対するアクセス回数がＮに達するまでに同じ
ページに複数回アクセスが行なわれても「１」のままで
ある。そしてこの主メモリーこ対するアクセス回数がＮ
に達するまでに０ページ〜ｎページがすべて少くとも１
回アクセススされたとき、第８図イのようにレジスタＲ
３の参照テーブルは表示される。そして主メモリに対す
るアクセス回数がＮに達すると、上記の場合と同様に、
シフトクロック作成回路４はシフト信号ＳＨＩＦＴを出
力し、これによりレジスタＲ３の内容はしジス夕Ｒ２に
転記される。そして主メモリに対するアクセス回数が次
のＮ回に達するまでに１ページ〜ｎページがアクセスさ
れたとき、レジスタＲ３，Ｒ２の内容は第８図口に示す
如き状態となる。そして次のＮ回の間に２ページ〜ｎペ
ージがアクセスされたときにはしジスタＲ３，Ｒ２，Ｒ
，の内容は第８図ハに示す如き状態になり、さらに次の
Ｎ回の間に３ページ〜ｎページがアクセスされたとき、
各レジスタＲｏ〜Ｒ３の状態は第８図二に示すようにな
る。この状態で新しく利用できるページをサーチする場
合、まず頻度レベル基準信号ＰｏでレジスタＲ。

の参照テーブルを議出し、アクセスされなかったページ
のサーチを行なうが、上記の如くこの場合には全ページ
が少くとも１回サーチされているので、更新すべきペー
ジは検出できない。そこでカウンタ１２はオーバーフロ
ー信号ＯＶＦを送出し、頻度レベル基準信号Ｐ，により
今度はしジスタＲ，を論出す。そして更新すべきページ
として０ページを検出することができる。第９図はアド
レスサーチ回路３あるいはレベル選択回路５のカゥンタ
部分の他の実施例を示す。

現在の実装された主メモリ空間が４ＭＢとしたとき将来
は聡ＭＢ程度のものの使用が予想される。したがって将
来のことまで考慮したとき、データ保持回路の参照テー
ブルはハード的に実装可能なたとえば１８ＹＢ分に対す
るページ数だけ用意し、これを現在の主メモリ空間が４
Ｍ旧の場合には小伯のところまで使用することが望まし
い。ところがこのような場合、参照テーブルをサーチす
るような場合４ＭＢのところまででよいので、それから
先は現在はカウントする必要はない。それ故このような
カウンタとしては１８ＭＢ分のページ数まで計数できる
ものの、必要に応じて実際に使用される４ＭＢ分のペー
ジ数までの計数を行なうものが希望される。このため、
第９図に示すようにリミット・レジス夕５０と比較回路
５１、インバータ５２、アンド回路５３等により構成さ
れた回路を有効アドレス・レジスタ９′および更新回路
（十１カウンタ）１０′に設ける。

いま主メモリが４ＭＢの場合には、それに相当するペー
ジ数（例えば狐）をこのリミット・レジスタ５川こセッ
トする。この状態で更新回路１０′を動作羊せ有効アド
レス・レジスタ９′にセットされた値、（例えば０をこ
の更新回路１０′で十１したのち、比較回路５１にてリ
ミット・レジスタ５０にセットされた上記ページ数と比
較する。そしてこれが一致しなければ比較回路５１は０
を出力し、ィンバータ５２は「１」を出力するので、ア
ンド回路５３はオン状態となり、更新回路１０′の出力
はこのアンド回路５３を経由して有効アドレス・レジス
タ９′にセットする。このようにして更新回路１０′の
出力がリミット・レジスタ６０のセットされた値と一致
するまで比較回路５１は「０」を出力するのでアンド回
路５３はオン状態にある。そして更新回路１０′の出力
がリミット・レジスタ５０の値と一致すれば比較回路５
１は「１」を出力し、インバータ５２は「０」を出力し
、アンド回路５３は「０」を出力し、有効アドレス・レ
ジスタ９′は「０」がセットされる、つまり初期状態に
リセットされることになる。そしてこのとき比較回路５
１の出力「１」をオーバーフロー信号ＯＶＦとして使用
することができる。このように構成することにより、あ
らかじめハードを将来のことを予測してこれに対応でき
るものを使用しつつ現在のものに適用することもできる
。勿論リミット・レジスタ５川ま外部よりその内容を自
由に書替えできるように構成すればその効果は更に大き
くなる。また、第７図および第８図の方式では第１０図
に示すような問題がおきることがある。すなわち、第１
０図イに示すように、レベルＰｏで参照テーブルをサー
チした後に、主メモリへのアクセスが行なわれてシフト
が生ずる場合の問題である。

前回のサーチにより有効アドレスレジスタ（ＡＶＲ）６
０がｎ−１ページを指示しているときならば、通常はそ
の位置よりサーチが開始され、次のページをアクセスし
、これによるも利用可能なべージが得られなかったとき
、更新回路は初めの０ページにもどる。そして更新信号
がシーケンス回路から出力されこの更新回路の表示の０
が有効アドレスレジスタ（ＡＶＲ）にセットされるとき
、オーバーフロー信号ＯＶＦ２が出力される。しかしな
がら、このサーチが行なわれる前にシフトが生ずると、
その最後参照テーブルは第１０図口に示すように、０ペ
ージあるいは２ページのところで更新ページが存在して
いるにもかかわらず、これを検出しないことになる。

したがってこのような問題を改善するために、第１１図
に示すようにレベル優先回路１３へのオーバーフロー信
号ＯＶＦをアドレスサーチ回路に設けた更新回路６１か
ら生ずるオーバーフロー信号ＯＶＦ２にもとづき作成す
るとともに例えばＳＲフリップフロツプで構成されるフ
ラグ６４を設け、最後段のレジスタＲｏをサーチしてい
るときにシフトが生じたときこのフラグ６４の出力信号
によりアンド回路６６をオフにし、更新回路６１から出
力されたオーバーフロー信号ＯＶＦ２の伝達を抑制する
ものである。

すなわち、最後段のレジスタＲｏへのサーチが頻度レベ
ル基準信号Ｐｏでサーチされているとき、主メモリへの
アクセス回数が所定値に達し、シフトクロック作成回路
４からシフト信号ＳＨｍＴが伝達されたとき、アンド回
路６２は「１」を出力し、フラグ６４に「１」を記入す
る。

これによりインバー夕６５は「０」を出力し、アンド回
路６６はオフ状態になる。したがってその後に更新回路
６１からオーバーフロー信号ＯＶＦ２が出力され、これ
がアンド回路６３を経由してオーバーフロー信号ＯＶＦ
Ｉとなってアンド回路６６に伝達されても、アンド回路
６６からオーバーフロー信号ＯＶＦは出力されない。し
たがってレベル優先回路１３は、更新回路６１がオーバ
ーフロー信号ＯＶＦ２を出力しても優先レベルが変化す
ることなくＰｏのレベルをそのまま出力する。シーケン
ス回路１１は更新情報を送出し、有効リミットレジスタ
６０には更新回路６１が出力したチェックアドレス０が
セットされ、これによりレジスタＲｏをサーチし、更新
すべきページを検出することができる。以上説明の如く
、本発明によれば新しく利用できる区分の存在をハード
で実行することができ、しかも優先レベルを付与してこ
れを効率的に検出することができるので、データ処理効
率を非常に高めることができる。

【図面の簡単な説明】

第１図〜第５図イ，口、第６図は本発明の１実施例構成
、第７図、第８図は本発明の他の実施例構成、第９図は
本発明のアドレスサ−チ回路あるいはレベル選択回路に
使用されるカウンタ部分の他の構成、第１０図、第１１
図は本発明の他の実施例構成である。 図中、１はアドレス・レジスタ、２はデータ保持回路、
３はアドレスサーチ回路、４はシフトクロック作成回路
、５はしベル選択回路、６はデータチェック回路、７，
８はオア回路、９は有効アドレス・レジスタ、１０は更
新回路、１１はシーケンス回路、１２はカウンタ、１３
はしベル優先回路、１４一０〜１４一ｎはインバータ、
１５，１６はアンド回路、１７はオア回路、１８はフリ
ツプフロツプ、１９はイン／ゞータ、２０はアンド回路
、２１はオア回路、２２，２３はアンド回路、２４はオ
ア回路、２５はフリツプフロツプ、２６はインバー夕、
２７はアンド回路、２８はオア回路、２９はィンバータ
、３０，３１はアンド回路、３２はフリツプフロップ、
３３はインバー夕、３４はアンド回路、３５はオア回路
、３６はアンド回路、３７は読出データ保持部、３８−
０〜３８−３はインバ−夕、３９〜４５はアンド回路、
４６はオア回路、５０はリミット・レジスタ、５１は比
較回路、６０‘ま有効アドレス・レジスタ、６１は更新
回路、６４はフラグをそれぞれ示す。 オー図 ナ２図 才３図 才４図 矛Ｓ図 キＳ図 寸６図 矛７図 了８図 了ｑ図 汁‘０図 オー１図

Claims (1)

1. 【特許請求の範囲】 １ 主メモリを複数の区分に設定し、各区分毎にそれが
   使用されたことを示す参照データを付与しこの参照デー
   タにもとづき上記設定区分の内容を更新するようにした
   主メモリ管理方式において、上記複数の区分の使用回数
   が記入され主メモリに対する一定アクセス回数毎に上位
   から下位に少なくとも１ビツトシフトされる参照テーブ
   ルを有する使用データ保持手段と、主メモリに対するア
   クセス回数を計数するアクセス計数手段と、上記使用デ
   ータ保持手段からデータをレベル付けしてこれより参照
   データを読出すようにしたレベル選択読出手段と、上記
   使用データ保持手段を読出すためのアドレスを発生する
   アドレス発生手段を設け、主メモリにおける新しく利用
   できる区分をサーチする場合には上記アドレス発生手段
   によるアドレス情報にもとづき上記使用データ保持手段
   を読出し、この読出しデータをレベル選択することによ
   り新しく利用できる区分を決定するようにしたことを特
   徴とするアクセスサーチ方式。 ２ 上記使用データ保持回路内容を読み出すレベル選択
   読出手段において新しく利用できる区分をサーチする回
   数の増大につれレベル選択の頻度レベルが変化すること
   を特徴とする特許請求の範囲第１項記載のアクセスサー
   チ方式。 ３ 上記アドレス発生手段に、リミツトレジスタと比較
   回路と計数手段を設け、リミツトレジスタにセツトされ
   た数値と上記計数手段の計数した値を比較することによ
   りアドレス発生範囲が定められるようにしたことを特徴
   とする特許請求の範囲第１項記載のアクセスサーチ方式
   。 ４ データシフトの信号をレベル選択読出手段の頻度レ
   ベルを変化させることを特徴とした特許請求の範囲第１
   項記載のアクセスサーチ方式。 ５ 新しく利用できる区分が決定した時に対応する区分
   のデータ保持回路にその区分を使用したことを示すデー
   タを書き込むことを特徴とした特許請求の範囲第１項記
   載のアクセスサーチ方式。