具有
能从逻辑上对内存容量加以扩充的的一种存储器系统
不用全部装入实存 只需要在需要的时候，在访问具体页面的时候，才装入
请调：
首先在页表中看在不在，
如果是invalid,则给一个page not found错误
如果valid,但只是不在实际内存，则换入，然后改变页表（改成在实存中）
预调：根据经验事先调入一些
swapper vs pager(以页为单位的lazy swapper)
###Basic Concepts
first reference to a page wiil trap to OS
EAT: effective access time p: page fault rate
EAT = (1-P) * memory access + p * page fault time
page fault time = page fault overhead + swap page out(optional) + swap page in + restart overhead
why is swap out time optional?
如果没有free frame怎么办？
find some pages in memory,but really not in use,swap it out
处于缺页中断时，该进程处于阻塞状态
How do we select a particular replacement algorithm?
In general, we want the one with the lowest page-fault rate.
We evaluate an algorithm by running it on a particular string of memory references and computing the number of page faults. The string of memory references is called a reference string.
Obviously, as the number of frames available increases, the number of page faults decreases.. Of course, adding physical memory increases the number of frames.
example 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 .for a memory with three frames
<font color=red>注意题目问的是replace次数，还是page fault的次数</font>
We can create a FIFO queue to hold all pages in memory. We replace the page at the head of the queue. When a page is brought into memory, we insert it at the tail of the queue
eg:For our example reference string, our three frames are initially empty. The first three references (7, 0, 1) cause page faults and are brought into these empty frames. The next reference (2) replaces page 7, because page 7 was brought in first. Since 0 is the next reference and 0 is already in memory, we have no fault for this reference. The first reference to 3 results in replacement of page 0, since it is now first in line. Because of this replacement, the next reference, to 0, will fault. Page 1 is then replaced by page 0. This process continues as shown in Figure 9.12. Every time a fault occurs, we show which pages are in our three frames. There are fifteen faults altogether.
for some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases.只有FIFO会出现这种现象,后面的算法都不会出现
the algorithm that has the lowest page-fault rate of all algorithms and will never suffer from Belady’s anomaly
Replace the page that will not be used for the longest period of time
eg:For example, on our sample reference string, the optimal page-replacement algorithm would yield nine page faults
The first three references cause faults that fill the three empty frames. The reference to page 2 replaces page 7, because page 7 will not be used until reference 18, whereas page 0 will be used at 5, and page 1 at 14. The reference to page 3 replaces page 1, as page 1 will be the last of the three pages in memory to be referenced again. With only nine page faults, optimal replacement is much better than a FIFO algorithm, which results in fifteen faults. (If we ignore the first three, which all algorithms must suffer, then optimal replacement is twice as good as FIFO replacement.) In fact, no replacement algorithm can process this reference string in three frames with fewer than nine faults.
实现困难，一般做标杆，来衡量其他算法的好坏。
LRU replacement associates with each page the time of that page’s last use.
When a page must be replaced, LRU chooses the page that has not been used for the longest period of time.We can think of this strategy as the optimal page-replacement algorithm looking backward in time, rather than forward.
Like optimal replacement, LRU replacement does not suffer from Belady’s anomaly