ページ置き換え ＬＲＵ方式

アーキテクチャについてです。

ページ置き換えアルゴリズムにおいて、ＬＲＵは「専用のハードウェアが無いと実装が困難」とありますが何故でしょうか？

メモリ上のページテーブル（ページ枠テーブル・・？）に、アクセスした時刻を添えて記録し、ページフォルト時に一番古いものを検索してページアウトするという風にすれば、ＯＳの仕組みで（ソフトウェア的に）できそうなきがするのですが・・・。

実現は可能でもないが、その古いページ枠の検索に時間がかかかってしまうということでしょうか？

No.1 回答者： bin-chan 回答日時： 2004/12/15 20:27

> メモリ上のページテーブル（ページ枠テーブル・・？）に、アクセスした時刻を添えて記録し

これこそが「専用のハードウェアが無いと実装が困難」の理由では？

メモリ上のアクセスを記録する領域もメモリ上。
従って、メモリ上のアクセスをメモリ上に記録し、そのまたメモリ上のアクセスを・・・。
だからメモリ上のアクセスを記録する仕組みが必要なんだと思います。

この回答への補足

すいません、急に疑問に思ったのですが、ページテーブル事態もページアウトの対象になってしまうと、ページテーブルの意味がなくなってしまうのでは・・

補足日時：2004/12/15 23:21

この回答へのお礼

>メモリ上のアクセスを記録する領域もメモリ上。

とありますが、ページテーブルを管理するのはＯＳで、ページテーブルもカーネル領域にあり、これ自体はページアウトされないものだと決め付けてしまっていました（ユーザ領域のデータのみページアウトされると思い込んでいた）。そうではなかったんですねぇ。

ありがとうございました。

お礼日時：2004/12/15 20:47

No.2 回答者： fortranxp 回答日時： 2004/12/15 20:32

LRUとはLast Recent Usedですねその対抗馬として

FIFOが有る訳でFirst in First outと成っているのですね。
FIFOは前近代的で今は大抵はLRUではないかと。。。。
＞専用のハードって
FIFOはスタックでしょうがLRUは　少し難しいか？

この回答へのお礼

>FIFOはスタック・・・

ですねぇ。ＦＩＦＯならキューを使って、いっぱいになったら先頭に戻って・・ってやれば簡単ですよね。。

ありがとうございました。

お礼日時：2004/12/15 20:50

No.3 ベストアンサー 回答者： hpsk 回答日時： 2004/12/20 00:48

>> #1の方の回答とそのお礼

> ページテーブルを管理するのはＯＳで、ページテーブルもカーネル領域にあり、これ自体はページアウトされないものだと決め付けてしまっていました
いえ、質問者の方の認識でいいと思いますよ。

> LRUとはLast Recent Used
Least Recently Usedでは？

> 実現は不可能でもないが、その古いページ枠の検索に時間がかかかってしまう
それが一番大きな理由でしょう。
質問者さんの方法は一番率直な方法ですが、これをソフトウェアでやるとページ入れ替えのたびに、ページサイズに比例する時間がかかってしまいますよね。
これを高速にやろうとすると、連想メモリのようなハードウェアの支援が必要になるわけです。
あと、「アクセスした時刻」のための領域を何ビット用意するのかも大きな問題です。ページごとに用意する必要があるわけですから。
「率直ではない」方法もありますが（参考URL）、やはりオーバーヘッドの面で厳しいです。

それで、LRUを近似的に実現する方法としてaging方式や時計針のアルゴリズムがあるわけですが、これらはもうご存知でしょうか？

参考URL：http://f.csce.kyushu-u.ac.jp/~furusho/OS_4/OS4.h …

この回答へのお礼

詳しく回答していただきありがとうございます。

> LRUとはLast Recent Used
>Least Recently Usedでは？
おっしゃるとおりでした。＃２の方もそれをご指摘してくれたのですね＾＾；お騒がせいたしました。


>それで、LRUを近似的に実現する方・・・

はい、agingやWSclockは授業で一通り学びました。
他に、アクセスしたごとに参照ビットを1にし、しかし定期的に参照bit(1bit)を定期的に0にリセットする、という簡易的な近似アルゴリズムやNFU(Not Frequently Used)も学びました。一応理解はしたつもりですが、厳密なLRUにするには「ハードウェアのサポートが必要」ということに引っかかってしまっていたのでので。。
専用のハードウェアとしてはやはり連想メモリが必要になってくるんですねぇ。連想メモリ自体もあまり段数を増やせない（あとお金がかかる）ということもなるみたいなので、なかなか実現が難しいということなんですね・・・。

参考にあげていただいたURLも前に見てみたのですが、そのときは何故かリンク切れだったような・・＾＾；
しかしこうしてWSclock等の参考文献も無事見ることができるのでとても助かりました。
こちらの方を改めて読んでみますね。

お礼日時：2004/12/20 15:50