JPS638850A

JPS638850A - Ｌｒｕ装置

Info

Publication number: JPS638850A
Application number: JP61152450A
Authority: JP
Inventors: Masaru Uya; 宇屋　優
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1986-06-27
Filing date: 1986-06-27
Publication date: 1988-01-14

Abstract

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

Description

【発明の詳細な説明】産業上の利用分野本発明は、仮想記憶方式を採用したコンピュータのメモ
リ管理システムやＭ　Ｍ　Ｖ　（Ｍｅｍｏ　ｒ　ｙＭａ
ｎａｇｅｍｅｎｔ　Ｖｎｉ　＋）　、　キャラ’／　ユ
／　モリヲ搭載したコンピュータのキャッシュ・コント
ローラなどに用いられるＬ　ＲＵ　（Ｌｅａｓｔ　Ｒｅ
ｃｅｎｔｌｙ　Ｕｓｅｄ）アルゴリズムを実現するＬＲ
Ｕ装置に関するものである。

従来の技術Ｌ　ＲＵ　（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ
Ｊアルゴリズムは、コンピュータの仮想記憶システムの
再配置ポリシー（ｒｅｐｌａｃｅｍｅｎｔ　　ｐｏｌｉ
ｃｙ）の中で最良のアルゴリズムの１つであるが、従来
のコンピュータでは不完全な方法で行なわれていた。メ
イン・メモリに関するページング方式記憶管理の例テハ
、ページ・フレーム・テーブルに参照ビット（ｒｅｆｅ
ｒｅｎｃｅ　ｂｉｔ）を設け、ページ、７１／−ムの中
の命令やデータをアクセスしたときに参照ビットを１”
にセットし、ｏＳが定期的に全ての参照ビットをクリア
する方法がとられる。つま９゜長い間、アクセスされな
かったページ・フレームの参照ビットは′０”になった
ままでいる。ページ・アウトの対象となるのは、対応す
る参照ビットが０”のページ・フレームであり、それ（
又はそれら）のページ・フレームへ必要とされるページ
を外部記憶からページ・インすることになる。

今日、ＬＲＵアルゴリズムを用いたコンピュータの殆ん
どが上述の方法を採用している。

また、他の方法として、ページ・フレームごとにアクセ
スされた回数を記録しておき、ページ・アウト時に最も
回数の少ないページ・フレームをページ・アウト対象に
選ぶ方法であるが、これを応用した実用コンピュータは
例を見ない。

発明が解決しようとする問題点上述の「参照ビット」を利用する方法は、「最も過去に
使用されたページはど今後使用される確率が低いであろ
う」というＬＲＵアルゴリズムを完全に実現していない
ため、どうしても実現されるヒツト率に限界があり、そ
れ以上の向上は望めなかった。次の「アクセス回数」を
記録する方法は、過去のいつかのアクセス頻度の情報に
基づいているため１時刻情報の必要なＬＲＵアルゴリズ
ムは側底実現できなかった。

本発明は上述の様な従来のＬＲＵ装置の不完全なＬＲＵ
機能による低いヒツト率を改善し、真のＬＲＵアルゴリ
ズムを実現して高いヒツト率を得るＬＲＵ装置を提供す
ることを目的とする。

問題点を解決するための手段本発明は、Ｎを２以上の整数とし１等級付けされた相異
なるＮ個の等級データのそれぞれを１つずつ記憶し、そ
れぞれ番地付けされたＮ個の記憶要素と、上記Ｎ個の記
憶要素のＮ個の番地のどの１つの番地をも示すことので
きる入力データと。

上記Ｎ個の記憶要素からそれぞれ出力された上記Ｎ個の
等級データとを入力して、上記入力データが示す番地の
記憶要素の記憶している等級データを抽出して出力する
抽出手段と、上記Ｎ個の記憶要素に１対１対応して設け
られ、それぞれ対応する記憶要素の記憶している等級デ
ータと上記抽出手段から出力された等級データとを比較
して、前者が後者より等級が低い場合にのみ、昇級指令
信号を出力するＮ個の比較手段と、上記Ｎ個の記憶要素
に１対１対応して設けられ、それぞれ対応する上記比較
手段の出力を入力とし、上記昇級指令信号を受信した場
合には、それぞれ対応する記憶要素に作用して、その記
憶している等級データより１等級高い等級データに記憶
更新させ、反対に上記昇級指令信号を受信しなかった場
合には、それぞれ対応する記憶要素の等級データに変化
を与えないＮ個の更新手段と、上記入力データを入力し
、上記Ｎ個の記憶要素のうち該入力データが示す番地の
記憶要素に作用して、上記等級性けされた相異なるＮ個
の等級データのうち最低の等級の等級データに記憶更新
させる初期化手段と、上記Ｎ個の更新手段と上記初期化
手段の処理が終了した時点で、上記Ｎ個の記憶要素から
出力される等級データを入力し、上記Ｎ個の記憶要素の
うち最高の等級の等級データを記憶している記憶要素を
検出し、この記憶要素の番地を示す出力データを出力す
る検出手段とを具備し、入力データを上記抽出手段に入
力して、上記検出手段に出力される出力データを得るこ
とを特徴とするＬＲＵ装置である。

作　　用本発明は前記した構成によ）、例えば、メイン・メモリ
中のページ・フレームの中で、今回アクセスされたペー
ジ−フレーム・ナンバーに対応した入力データをＬＲＵ
装置に入力することにより。

現在最も過去にアクセスされたページ・フレーム・ナン
バー（ページ・アウト対象）に対応した出力データを即
座に得ることができ、真のＬＲＵアルゴリズムがハード
ウェアで実現できる。

実施例第１図に本発明の実施例におけるＬＲＵ装置の回路図を
示す。本実施例では、理解を容易にするため、記憶要素
の数Ｎを４に設定しである。

まず１本ＬＲＵ装置の応用方法について述べる。

例えば、メイン・メモリのベージング、ＭＭＶの管理す
るＴ　Ｌ　Ｂ　（Ｔｒａｎｓｌａｔｉｏｎ　Ｌｏｏｋ　
ａｓｉｄｅＢｕｆｆｅｒ）の更新、キャッシュ・メモリ
のブロック・スワツピングなどに応用される。

メイン・メモリのページングを例にとる。スワップ対象
となるページ・フレームの数をＮとした場合、ページ・
フレームにそれぞれ対応した数値データ“０”、”、”
２”、・・・・・・、”Ｎ−２”。

”Ｎ−１”をとる入力データＤＩＮ　を設定する。

あるページ・フレームがアクセスされるとそのページ・
フレームに対応した数値を入力データＤｌＮとしてＬＲ
Ｕ装置に入力する。すると、ある一定時間後（応用上、
十分に短い）に、ページ・アウトの対象（候補）となる
最も過去にアクセスされたページ・フレームに対応する
数値データを出力データＤｏＵ丁に得ることができる。

さて、第１図に戻って、１〜４は、データ・ロード信号
入力ＬＤ、カウント・アップ（又はインクリメント〕信
号入力ＩＮＣ，クリア信号ＣＬＲを有するカウンタであ
る。第１図の実施例の場合は、２ビツト・バイナリ−カ
ウンタで実現される。

６は４人力のデータ・セレクタであり、セレクト入力Ｓ
ＥＬに入力される２ビツトのデータＤＩＮ’により　Ｄ
ｏ、Ｄｌ、Ｄ２．Ｄ３に入力される各々２ビツトのデー
タＱ　□　＊　０１　ｒ　０２　、Ｑ　３を選択して出
方端子ＯＵＴに出力Ｑｓとして出方するものである。例
えば、　Ｄ　Ｉ　Ｎ’　＝　”　２”の場合は、Ｑ２→
Ｑ８となる。６〜９は、入力Ａと入力Ｂとを大小比較し
て、判定信号Ｍ０．Ｍ１．Ｍ２．Ｍ３を出力端子Ｂ（Ａ
にそれぞれ出力するマグニチュード・コンノζレータで
ある。入力Ａ〉入力Ｂの場合に、Ｂ（入出力はＨレベル
（高論理レベル）となり、入力Ａ≦大入力の場合には、
Ｂ（入出力はＬレベル（低論理レベル〕となる。１０は
入力り。−Ｄ３にそれぞれ入力されたデータＱ。−Ｑ３
のうち最大のデータの入力している入力Ｄ０〜Ｄ３に対
応した数値データをＯＵＴにＤｏＵτ′として出力する
最大値検出回路である。この最大値検出回路１０の具体
的実施例を第２図に示す。１０１〜１０４は一致比較器
として用いられている２人力ＡＮＤゲートである。

１００はバイナリ・エンコーダであり、入力０〜３のう
ち、Ｈレベルの入力されている入力に対応したデータを
Ａ１．Ａｏに出力する。例えば、入力０＝入力１＝入力
３＝Ｌレベル、入力２＝Ｈレベルのとき、Ａ１＝Ｈレベ
ル、Ａｏ＝Ｌレベルとなる。ＡＮＤゲート１０１〜１０
４は２ビツト入力り。−Ｄ３うち最大値、即ち３”（２
ビツト入力としては１１Ｂ″）を−数比較して検出する
ものであり、これが入力されたときに限り、Ｈレベルと
なる。例えば、Ｄ。＝″′２”、Ｄ１＝゛１″、Ｄ２＝
”ａ”。

Ｄ３＝″ｏ”　のとき、ＡＮＤゲート１０３のみがＨレ
ベルを出力する。このとき、最大値検出回路１０の出力
ＯＵＴは入力Ｄ２（最大値゛３”が入力）に対応した数
値データ″２”を出力する。

第１図の１１は２ラインー４ライン・デコーダであり、
データＤＩ　Ｎ’を入力して、出力Ｙ０〜Ｙ３のうちい
ずれか一本のみＨレベル（残りは全てＬレベル）とする
。例えば、Ｄ工Ｎ′＝”３”　であれば、Ｙ３のみがＨ
レベルとなる。１２〜１９は２人力ＡＮＤゲートである
。２０．２１は入出力タイミングを調整するためのＤフ
リップ・フロップである。

ＣＬＫｌ、ＣＬＫ２はタイミング・クロック信号であり
、ＬＯＡＤは初期値゛０”〜“３”をカウンタ１〜４に
それぞれロードするためのロード信号である。

ここで１本発明の動作原理について、第４図を参照して
説明する。まず、Ｎ個の記憶要素があり、記憶されるデ
ータとして等吸付けされた等級データを考える。等級デ
ータはＮ種類ある。例えば、Ａ”、Ｂ”、Ｃ”　ｌｌＤ
″、・・・・・・（Ｎ個）テモ、“イ”、口”、”ハ”
、“二”、・・・・・・（Ｎ個）でも良い。ここではＮ
＝４とし１等級データを０”、”１”、“２”、”３”
（”０”を最低、３”を最高等級とする〕とする。記憶
要素には、第４図の如くアドレス＃０〜＃３が付けられ
ている。初期状態ａでは、最左列の如く記憶されている
。ここで、等級データの最高値”３”を記憶している記
憶要素を検出し、そのアドレスに対応（ここではそのも
の）した出力データを出力する検出手段がある（図示せ
ず）。状態ａでは＃３を出力している。さて、入力デー
タとして。

記憶要素のどれか一つに対応した数値データ（アドレス
＃０〜＃３に一致〕が入力されてくる。この入力データ
（ａでは＃２）に対応した記憶要素（アドレス＃２）の
記憶している等級データじ３″”）を抽出して出力する
抽出手段（図示せず）があり、この抽出手段の出力（Ｑ
、とする）と、それぞれの記憶要素の等級データ（Ｑ、
（ｉ＝Ｏ〜２）とする）とを比較する比較手段（図示せ
ず）と、この比較手段の判定結果により、Ｑｉ＜Ｑ、の
場合に限り、＃ｉのアドレスの記憶要素の等級データを
１等級だけ昇級させる更新手段（図示せず）と、上記の
入力データ（ａでは＃２）に対応する記憶要素（＃２）
の等級データ（３”）を最低の等級データ（０”）に記
憶更新させる初期化手段（図示せず）が常に動作してい
る。

従って、状態ａの場合、入力データ＃３に対応し、Ｑ、
＝”３”となり、Ｑｏじ０”）＜Ｑｓじ３”）＋Ｑ、（
”１”）＜Ｑｓじ３”）、０２じ２”）＜０８じ３”）
となるから、＃０〜＃２の記憶要素内の等級データＱ０
〜Ｑ２はインクリメントされ、ＱｏじＯ”）＋１＜。（
”１’　）　、Ｑｌ（”１″）＋１−＋Ｑ、じ２”）。

Ｑ２じ２”）＋１→Ｑ２（”３”）とな９、＃３の記憶
要素は初期化され、Ｑ３（“３”）−＋Ｑ３（初期化：
′０”）となって、出力データは等級データ゛３”をも
っている＃２の記憶要素に対応して、＃２が出力される
Ｏ状態すに対して入力データ＃１が入力されると、Ｑ８
＝“２”となり、Ｑｏじ１’　）（Ｑ、じ２”ン。

Ｑ３じ０”）〈Ｑ８じ２”）であるから、Ｑｏじ１”）
＋　１−＋Ｑｏ　（”　２”）Ｉｏｌ（”２”）−＋Ｑ
１（初期化：′ｏ”）。

Ｑ２じ３″）：変化せず、Ｑ３じＯ″）＋１→Ｑ３（１
”）となり（状態Ｃ）、出力データは＃２となる。次に
、状態Ｃに対して、入力データ＃２が入力されると、Ｑ
、＝”３”　となり、Ｑｏ（”２”）くＱ８じ３″）。

Ｑｌじ０”）＜Ｑｓ（３”）、Ｑ３じ１″）＜Ｑ、（”
３”）であるから、Ｑｏ（”２″）＋１−伽（ン。じ３
”）、Ｑｌ（”σン十１−もじ１”）、Ｑ２じ３”）−
６（初期化：“０”）。

Ｑ３じ１”）＋１−＋Ｑ３じ２”）となり（状態ｄ）、
出力データは＃０となる。以下、同様の動作をする。

以上、第４図の原理図から分かる様に、入力データ＃０
〜＃３で示した「箱」（記憶要素）の内容（等級データ
〕は無条件でクリア（′０”）され、最新のアクセスで
あることを示す。さらに、状態がａ　−＋　ｂ→・・・
・・・と変化しても、４つの「箱」には、常に０″，“
１”、”２’”，“３”がそれぞれ１個ずつ入９、決し
て重複することはない。

この数字（○”〜″３”〕がアクセスされた「古さ」を
示していて、古い順に３”、”２”。

１″、”０”となるのが分かる。従って、ＬＲＵ装置に
応用する場合には１例えば、メイン・メンＩＪ　Ｏペー
ジφフレーム・ナンバー（あるいは、これに対応した数
値データ）を入力データ（＃０゜＃１．・・・・・・）
として入力すると、出力データにページ・アウト候補（
最も過去にアクセスされたページ・フレーム）のページ
−フレーム自ナンバー（又は対応した数値データ）を即
座に得ることができる。

さて、第１図の各々の構成物は、第４図で述べた要素９
手段の具体的実施例となっている。即ち。

記憶要素とこれに対応する更新手段（インクリメント機
能）を実現するのにカウンタ１〜４が、抽出手段を実現
するのにデータ・セレクタ６が、比較手段を実現するの
にマグニチュード・コンパレータ６〜９が、初期化手段
を実現するのにデコーダ１１が、検出手段を実現するの
に最大値検出回路１０がそれぞれ用いられている。

第３図に、第４図で説明した状態６−＋　ｋ）　−＋　
ｃ→ｄの遷移に対応した第１図の各構成要素のデータ。

信号のタイム・チャートを示す。初めに、ロード信号Ｌ
ＯＡＤが印加（図示せず）され、第１図のカウンタ１〜
４にそれぞれ”０”，“１”，“２”。

３”がロードされ、初期設定される（状態ａ）。

次に状態すにおいて、入力データＤＩＮじ１”ンはタイ
ミング・クロックＣＬＫ１の立ち上シエッジでＤ７リツ
プ・フロップ２０にラッチされ、ｐＩＮ’（“１”）を
出力する（時刻ｔＡ）。ラッチされた入力データＤＩＮ
’　（”　１”）により、データ・セレクタ６はカウン
タ１〜４の出力Ｑ０〜Ｑ３うち、“１”に対応したＱｌ
（２”）をセレクトし、Ｑ、じ２”）を出力する（時刻
ｔＳ）。コンパレータ６〜９はそれぞれ、Ｑｏじ１”）
くＱ８じ２”）。

Ｑｌ（”２”）＜Ｏｓじ２”）＋Ｑ２じ３”）＜Ｑ８じ
２”）。

Ｑ３じ０°’）＜Ｑ、（”２”°）を判定し、それぞれ
。

Ｍ０＝″Ｈ”（高論理レベル）、Ｍ、＝”Ｌ”（低論理
レベル）ｒ　Ｍ２＝”Ｌ”２Ｍ３＝”Ｈ”　を出力する
。一方。

入力データＤＩＮ’じ１”）を入力したデコーダ１１は
、Ｙｏ＝″Ｌ”　、Ｙ１＝”Ｈ”、Ｙ２＝″Ｌ″、Ｙ３
＝″Ｌ″を出力する。ＡＮＤゲート１２〜１９を利用し
て。

Ｍｏ−Ｍ３．Ｙ０〜Ｙ３をタイミング・クロックＣＬＫ
２で打ち抜いて１ｍ０〜ｍ３ｓＶｏ−１３を得る（時刻
１０）。

カウンタ１〜４は、それぞれｍ０〜ｍ３の立ち上がりエ
ツジでインクリメントされ、７０−７３の立ち上がシエ
ッジでクリアされ、その出力は、それぞれＱ−１″→″
２″、Ｑ−″２”−＋”Ｏ”　、Ｑ２＝’３’ｏ−１− →″３”、Ｑ３＝“０”→”１”となる（時刻ｔＤ）。

変化後の００〜Ｑ３の中で、最大の等級データ”３”を
検出する最大値検出器１０により、Ｑ２が検出され、出
力データｐ　　　／＝“２”　が得られる（時刻ＵＴｔＨ）。これをタイミング・クロックＣＬＫ１　の次の
タイミングでＤフリップ・７０ツブ２１にラッチして、
出力データＤｏＵＴ＝″２”を得る（時刻ｔ　ｙ　）。

以後のサイクルも全く同様に動作するものである。

第１図の実施例で、入力データＤＩＮ　と出力データＤ
ＯＵＴの入出力タイミングを合わせるためのタイミング
・クロックＣＬＫ１とＤフリップ・フロップ２０，２１
．さらに、タイミング０クロツクＣＬＫ２とＡＮＤゲー
ト１２〜１９は、外部とのタイミングを合わせるための
ものであり、本発明の実現にとって本質的なものではな
い。

なお、当然のことながら、第１図実施例では、記憶要素
の個数Ｎ＝４の場合を示したが、もちろんこれに限定さ
れることなく、２以上のいかなる数の記憶要素ででも実
現可能である。

発明の詳細な説明したように、本発明によれば、真のＬＲＵアルゴ
リズムを実行するＬＲＵ装置を得ることが出来、しかも
回路構成も簡単で動作速度も速い装置が実現できて１種
々の仮想記憶管理機構を有するコンピュータなどに応用
すれば高いヒツト率を得ることができて極めて価値の高
いものである。

【図面の簡単な説明】

第１図は本発明における一実施例のＬＲＵ装置の具体的
回路図、第２図は第１図の最大値検出回路１０の具体的
実施例を示す図、第３図は第１図の各部の動作波形図、
第４図は本発明の動作原理を説明するための図である。１〜４・・・・・・カウンタ、５・・・・・・データ・
セレクタ、６〜９・・・・・・マグニチュードφコンパ
レータ、１０・・・・・・最大値検出器、１１・・・・
・・デコーダ、１０１〜１０４・・・・・・ＡＮＤゲー
ト、１０ｏ・・・・・・エンコーダ。代理人の氏名　弁理士　中　尾　敏　男　ほか１名第２
図第４図

Claims

【特許請求の範囲】（１）Ｎを２以上の整数とし、等級付けされた相異なる
Ｎ個の等級データのそれぞれを１つずつ記憶し、それぞ
れ番地付けされたＮ個の記憶要素と、上記Ｎ個の記憶要
素のＮ個の番地のどの１つの番地をも示すことのできる
入力データと、上記Ｎ個の記憶要素からそれぞれ出力さ
れた上記Ｎ個の等級データとを入力して、上記入力デー
タが示す番地の記憶要素の記憶している等級データを抽
出して出力する抽出手段と、上記Ｎ個の記憶要素に１対
１対応して設けられ、それぞれ対応する記憶要素の記憶
している等級データと上記抽出手段から出力された等級
データとを比較して、前者が後者より等級が低い場合に
のみ、昇級指令信号を出力するＮ個の比較手段と、上記
Ｎ個の記憶要素に１対１対応して設けられ、それぞれ対
応する上記比較手段の出力を入力とし、上記昇級指令信
号を受信した場合には、それぞれ対応する記憶要素に作
用して、その記憶している等級データより１等級高い等
級データに記憶更新させ、反対に上記昇級指令信号を受
信しなかった場合には、それぞれ対応する記憶要素の等
級データに変化を与えないＮ個の更新手段と、上記入力
データを入力し、上記Ｎ個の記憶要素のうち該入力デー
タが示す番地の記憶要素に作用して、上記等級付けされ
た相異なるＮ個の等級データのうち最低の等級の等級デ
ータに記憶更新させる初期化手段と、上記Ｎ個の更新手
段と上記初期化手段の処理が終了した時点で、上記Ｎ個
の記憶要素から出力される等級データを入力し、上記Ｎ
個の記憶要素のうち最高の等級の等級データを記憶して
いる記憶要素を検出し、この記憶要素の番地を示す出力
データを出力する検出手段とを具備し、入力データを上
記抽出手段に入力して、上記検出手段に出力される出力
データを得ることを特徴とするＬＲＵ装置。（２）Ｎ個の等級データとして、最低の等級データを“
０”、最高の等級データを“Ｎ−１”とするＮ個の数値
データ“０”，“１”，“２”，……，“Ｎ−２”，“
Ｎ−１”を用いることを特徴とする特許請求の範囲第１
項記載のＬＲＵ装置。（２）少なくともＮ個の数値“０”，“１”，“２”，
……，“Ｎ−２”，“Ｎ−１”を表現することのできる
数値データを入力データおよび出力データに用いること
を特徴とする特許請求の範囲第１項記載のＬＲＵ装置。（４）記憶要素およびこれに対応する更新手段として、
少なくともＮ個の数値“０”，“１”，“２”，……，
“Ｎ−２”，“Ｎ−１”をカウント値としてとることが
でき、かつ少なくともカウント・アップ機能、クリア機
能、データ・ロード機能をもつカウンタを用いることを
特徴とする特許請求の範囲第１項記載のＬＲＵ装置。（５）抽出手段として、Ｎ個の記憶要素からそれぞれ出
力されたＮ個の等級データを入力し、入力データをセレ
クト入力として、上記入力データに対応する等級データ
を出力するデータ・セレクタを用いることを特徴とする
特許請求の範囲第１項記載のＬＲＵ装置。（６）比較手段として、マグニチュード・コンパレータ
を用いることを特徴とする特許請求の範囲第１項記載の
ＬＲＵ装置。（７）初期化手段として、入力データを入力し、Ｎ個の
記憶要素に対し、それぞれ対応したＮ個の出力信号を出
力するデコーダを用いることを特徴とする特許請求の範
囲第１項記載のＬＲＵ装置。（８）検出手段が、Ｎ個の記憶要素から出力されたＮ個
の等級データをそれぞれ入力し、入力された等級データ
と数値データ“Ｎ−１”との一致比較して、一致した場
合に一致信号を出力するＮ個の一致比較器と、上記Ｎ個
の一致比較器から出力されたＮ個の一致信号を入力して
、上記出力データを出力するエンコーダとから成ること
を特徴とする特許請求の範囲第１項〜第３項のいずれか
一項記載のＬＲＵ装置。