操作系统简明-5.1页表 干货整理

---

页表结构

在现实中，页表存在物理内存里，因此这里就衍生了一系列问题，页表占多大内存？怎么管理这些内存？

问题：
开始，这是一个很稀疏的东西（有很多页），因此要用链表管理，并且要求是个变长，因为进程所需要的内存是变化的
解决：

1. 线性列表
2. 两级列表
3. 反页表：反着做这个映射关系---很老的东西

虚拟内存

这里有两个方向

这里有两个交换方向，我们单独说起

1

页交换算法，这里有两种：

1. 将来很长一段时间不会用到页
2. 交换进来后，没有修改过，我们称之为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
实现：

1. 做一个双向链表或是栈：每访问一次，就压栈。但是每访问一次，都要栈操作，这么做的话，实在是很浪费

2. 做一个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不能直接读磁盘，他要等磁盘的东西读入到内存才可访问（这部分内容由操作系统接管）：

1. 保存寄存器和进程状态
2. 检查发生页错的原因：是合法访问还是非法访问
3. 找到空页：每个座位是内存页，我们要找到空位子才能放进来，如果没有空位（后面会提到）
4. 操作系统给磁盘指令读取页
5. 在等待时，将cpu分配给其他进程（cpu不会等你）
6. 从I/O接收到中断（数据读取完毕，已经存储在内存中）
7. 把valid bit值更新为1

• 有效访问时间：不关心没次访问的时间，如果我有大量的内存访问，p是0~1之间的值，如果是0，永远不会发生页错，如果是1必定会发生页错：
• 在内存上：设100纳秒为访问内存时间
• 在磁盘上：25毫秒=2.5x10^6纳秒
  • 则平均访问时间=100（1-P）+2.5x10^6(1-P)
• 交换到哪里：

1. 磁盘上专门开辟一个空间，叫做交换区
2. 交换到系统盘（文件系统） ---windows经常这么干

• 一些细节
  当页错发生时，我们要有可用的资源，不仅要做也要能替换，还要把修改过的页写回磁盘－－－>使干净页的几率提高
  工作集：每个进程都有页集合，它随着时间会变化（每段时间处理的数据不一样）－－－解决需要频繁处理的页
• thrashing
  当进程越来越多,CPU利用率越来越高,物理内存小于工作集大小
• 花钱多买内存
• 少跑进程