Paging algorithm

Paging algorithm

"Paging algorithm" is a way to page out the pages in memory.

There are two typical methods.

① FIFO(First In First Out)

This is a way to page out the oldest page.

Suppose there are four empty areas in memory.  The memory will be fulled

when 2, 3, 5 and 8 pages are readed to it.  Next, one area in the memory has

to be emptied if the memory try to read 6 page.  "Page fault" will occur at this

time and 2 page will be paged out and 6 page will be readed.

② LRU(Least Recently Used)

This is a way to page out the page whose time most elapses since

it was last referenced.

One area in the memory has to be emptied if the memory try to read 6 page. 

"Page fault" will occur at this time and 5 page will be paged out and 6 page will be readed.

What is "Page fault"？

The interrupt that occurs when software attempts to read from or write to a virtual memory location that is marked "not present."

-----------------------------------------------------------------

[Japanese]

ページングアルゴリズムについて

ページングアルゴリズムとは、実記憶装置（=メモリ）のページを追い出す

方法です。代表的な方法が 2 つあります。

① FIFO(First In First Out)

最も古くページインされたページをページアウトする方法です。

例えばメモリが4領域あり、最初は何も入っていない状態だとします。

2, 3, 5, 8のページを読み込むと、メモリの4領域が埋まっていきます。

6をメモリに読み込むときに、メモリの1領域を空けなければいけません。

この時にページフォールトが発生し、FIFOの場合はメモリから2をページ

アウトして6をページインします。（2が最も古くページインされたからです）

② LRU(Least Recently Used)

最後に参照されてからの経過時間が最も長いページをページアウトします。

上記①を解説したときと同様に、6をメモリに読み込もうとする時にページ

フォールトが発生し、LRUの場合はメモリから5をページアウトして6を

ページインします。（最後に参照されてから経過時間が最も長いページが5だからです）

ページフォールトとは

プログラムが物理メモリがマップされていない仮想アドレス空間上のページにアクセスしたときにハードウェアが発生する割り込み（または例外）のことです。