页表结构
在现实中，页表存在物理内存里，因此这里就衍生了一系列问题，页表占多大内存？怎么管理这些内存？
问题：
开始，这是一个很稀疏的东西（有很多页），因此要用链表管理，并且要求是个变长，因为进程所需要的内存是变化的
解决：
- 线性列表
- 两级列表
- 反页表：反着做这个映射关系---很老的东西
虚拟内存
这里有两个方向
这里有两个交换方向，我们单独说起
1
页交换算法，这里有两种：
- 将来很长一段时间不会用到页
- 交换进来后，没有修改过，我们称之为clean，可以直接删除，如果为脏的，我们不能直接删，要存回去再删除
u==use bit ,d==dirty bit
|磁盘|valid bit|u|d|
|-|-|-|
1 FIFO page replacement
使用先进先出，替换最先进来的页：
假设有三个物理页： 页顺序是1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pages 1, 2, 3 brought in to memory.
Page 1 ejected, page 4 in - 2, 3, 4 in memory.
Page 2 ejected, page 1 in - 3, 4, 1 in memory.
Page 3 ejected, page 2 in - 4, 1, 2 in memory.
Page 4 ejected, page 5 in - 1, 2, 5 in memory.
Pages 1 and 2 accessed in memory.
Page 1 ejected, page 3 in - 2, 5, 3 in memory.
Page 2 ejected, page 4 in - 5, 3, 2 in memory.
Page 5 accessed in memory.
9个页错
解释下：1弹出，4进来，现在的序列是234
但是这种方法不是很好，再页错很多，因此如何避免这个二次页错
2 LRU (Lease Recently Used)
顺序依旧是：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Pages 1, 2, 3, 4 brought in to memory.
Pages 1 and 2 accessed in memory - 3, 4, 1 2 in memory.
Page 3 ejected, page 5 in - 4, 1, 2, 5 in memory.
Pages 1 and 2 accessed in memory.
Page 4 ejected, page 3 in - 5, 1, 2, 3 in memory.
Page 5 ejected, page 4 in - 1, 2, 3, 4 in memory.
Page 1 ejected, page 5 in - 2, 3, 4, 5 in memory.
8个页错
插入5的时候，从5开始倒序检查：214，这几个设为常用，然后替换3
实现：
- 做一个双向链表或是栈：每访问一次，就压栈。但是每访问一次，都要栈操作，这么做的话，实在是很浪费
-
做一个LRU的近似：可以用时间戳的概念来看，这个表走的很慢，由于许多页它的时间戳是一样的，所以它的分辨率很低（2页平分1小时，1页占1小时）
操作每隔一段时间就把他们存起来，然后清零，然后使用时候再设置1
3FIFO with second chance
钟表找下一个是0还是1
- 0：替换
- 1：置为０后找下一个
进一步更改
|磁盘|valid bit|u|d|
|-|-|-|
use = 0, dirty = 0: Best page to replace.
use = 0, dirty = 1: Next best - has not been recently used.
use = 1, dirty = 0: Next best - don't have to write out.
use = 1, dirty = 1: Worst.
在表上转好几圈来找
2
每个页表或者TLB有个valid bit，如果valid bit是1则他是物理内存，如果是0在磁盘
地板块是虚拟页（逻辑上的），我可以踩这些东西，如果在地上，很好可以通过页表访问，但是如果不在地上，某些页在天花板上（物理上的）。我们称之为页错
- page fault：访问页时，他是1，那么非常好，通过映射正常访问，但是如果是0，cpu不能直接读磁盘，他要等磁盘的东西读入到内存才可访问（这部分内容由操作系统接管）：
- 保存寄存器和进程状态
- 检查发生页错的原因：是合法访问还是非法访问
- 找到空页：每个座位是内存页，我们要找到空位子才能放进来，如果没有空位（后面会提到）
- 操作系统给磁盘指令读取页
- 在等待时，将cpu分配给其他进程（cpu不会等你）
- 从I/O接收到中断（数据读取完毕，已经存储在内存中）
- 把valid bit值更新为1
- 有效访问时间：不关心没次访问的时间，如果我有大量的内存访问，p是0~1之间的值，如果是0，永远不会发生页错，如果是1必定会发生页错：
- 在内存上：设100纳秒为访问内存时间
- 在磁盘上：25毫秒=2.5x10^6纳秒
- 则平均访问时间=100（1-P）+2.5x10^6(1-P)
- 交换到哪里：
- 磁盘上专门开辟一个空间，叫做交换区
- 交换到系统盘（文件系统） ---windows经常这么干
- 一些细节
当页错发生时，我们要有可用的资源，不仅要做也要能替换，还要把修改过的页写回磁盘－－－>使干净页的几率提高
工作集：每个进程都有页集合，它随着时间会变化（每段时间处理的数据不一样）－－－解决需要频繁处理的页 - thrashing
当进程越来越多,CPU利用率越来越高,物理内存小于工作集大小 - 花钱多买内存
- 少跑进程
