OS之页表全概述
1. 页表如何实现 OS与硬件配合
页表实际上是大数组，index是页号，存的内容是帧号
页表中还有一些bit，用来查找求得的物理地址是否真实存在（因为逻辑地址空间大于物理地址空间），用1表示存在，0表示不存在（resident bit），还有页是否被读过，写过…….
1.1 地址转换实例：
Flags代表页号，Frame
num代表页帧号，通过页号找到页帧号
（4，0）：页号为4，即1 0 0，页内偏移为0，标志位为0，代表物理页帧不存在
（3，1023）：页号为3，即0 1 1，得到页帧号为0 0 1 0 0，即4，标志位为1，物理页帧存在，页内偏移为1023，与页帧内偏移相同，所以得到物理地址为（4，1023）.
Resident bit：标志位，代表当前物理页帧是否存在，1存在，0不存在
0：物理页帧不存在，产生内存访问异常，将程序杀死
1.2 问题：
1.2.1 空间代价
1.若64位计算机，寻址空间为264,页的大小为210,则用264除以210,得2^54,存储量很大（？）
2.地址空间隔离，想让每一个应用程序都有一个页表，很耗空间
时间开销：访问效率小，因页表大，无法放在CPU中，则放在内存里，这样则要两次访问内存，开销大
解决办法：缓存cache；将很大的空间分解为小的空间（多级页表机制……）
1.2.2 时间代价
快表TLB,在CPU中的MMU（内存管理单元）里，是一个缓冲cache，缓冲页表中的内容（将部分查找频率较高的页表项缓存在CPU中）
Key-value对，快速查询机制，并发查找，时间有限所以容量有限，TLB中保存访问频率大的页表项，
key中有p值，value中有f值，
CPU先访问TLB,根据p查找f，若有p的对应项，直接得到物理页帧f，加上偏移量，得到物理位置；若无，CPU查询页表，然后将该项存入TLB
一般而言，TLB的缺失频率较小（访问局部性）
TLB miss后将页表项插入到TLB中：
X86：只需要硬件CPU就可完成
*&%￥（另外某种）：需要OS参与完成
2. 多级页表
2.1 定义
（让页表所占空间尽量小）将页表分层，将对一个很大的表选址改变成对多个页表进行选址。
2.2 描述
将页表的Pagenumber分为两部分，分别表示一级页表的pagenumber和二级页表的pagenumber
CPU已知一级页表的起始地址，将p1作为index，查找p1的页表项
p1中存的值是二级页表的起始地址，映射到二级页表的index
二级页表中存的是Framenumber，一级页表存的二级页表的起始地址加上二级页表的index得到Framenumber，Framenumber加上偏移量，得到物理地址
多了一次寻址，查找，但使得某些不存在映射关系的页表项不占用内存
（如果不存在映射关系，那么在一级页表中的标志位就是0，在一级页表中的页表项就不存在，那么所对应的二级页表pagetable就不需要存了，节省空间）
树状结构，以时间换空间
3. 反向页表
在多级列表中，逻辑空间越大，对应的页表就越多，想尽量使页表数量与逻辑地址没有关系，使页表与物理地址建立关系，即反向页表（反过来以页帧号作为index查找逻辑页号）
3.1 页寄存器
page registers（index是物理页号，即页帧号，存的内容是逻辑页号）实现寄存器的大小只与物理地址的大小有关，与逻辑地址无关，减少寄存器的数量，所占空间少
不受制于逻辑地址空间的限制，且只需要一个表就够了
3.2 存在的问题
如何建立根据页号找到页帧号的机制？
3.2.1 解决
1.关联内存 associative
memony，类似于TLB，依然是通过页号找页帧号，但是开销很大，无法做得很大（实现不佳）
2.基于HashTable
在哈希表中根据pagenumber查找framenumber（利用哈希函数，输入——>输出），用硬件来计算函数使加速，还可以在哈希中加个参数pid标识，表示当前运行的函数，提高效率
Pid and pagenumber得到framenumber
3.2.2 存在的问题
1.hash碰撞，一个input存在多个output，要找到到底是哪个，建立程序的id
2.反向页表要存入内存，内存开销还是很大，要建立类似于TLB来加速
4. 虚拟内存
4.1 起因
对内存的需求增大
利用硬盘等，形成计算机层次结构
操作系统来管理，将一些不常用的数据放入硬盘，常用的放在内存，实现虚拟大内存（需要硬件协同）
早期管理：覆盖技术，交换技术（将整段代码暂时不用的换出去），虚拟存储（以更小的页粒度为单位）
4.2 覆盖技术——实现大的程序在很小的空间里就能实现（发生在一个程序中）
有一部分常驻内存在里面负责管理调度。
可选：要用则导入内存，不用则导出。
相互之间不存在调用关系的函数或模块不必同时装入内存，即可实现共享同一块内存，当哪个模块要用的时候导进去。
A作为常驻区，进行管理。
如果有时间先后，如A先调B再C，则覆盖区0先放B再释放，再放C，0区只要满足大小不小于B and C的最大大小即可。
问题：需要程序员将整个程序分成若干小功能模块
4.3 交换技术——多道程序在内存时，让正在运行的程序获得更多的内存资源（发生在程序之间）
换出：将暂时不运行的程序完全导到硬盘中，将数据写入硬盘。
导入：（OS操作）
问题：交换时机，交换区大小，换出后再换入在内存中的位置不同了（页表，动态地址映射）
开销大
4.4 虚存技术
比覆盖，交换更好
实现覆盖，但由OS自动形成小模块
实现交换，在程序间和程序内都可
程序的局部性原理：在程序执行过程中的一个较短时期，所执行的色指令地址和数据地址分别局限在一个较小区域里。（时间，空间）
时间：指令的当次执行与下次执行，数据的当次访问and下次访问在很短的时间内；
空间：指令and 数据 自己and 临近的在较小区域内。
局部性好则程序执行效率高。
4.4.1 example 1
整型4Byte
一次能放一行进入内存，行优先的存储方式。
虚存技术特征：结合硬盘，实现大的虚拟空间
不能被换入换出的
操作系统内核，Kennel
部分交换
以段，页为单位，不需要换出整个程序
不连续
体现在物理内存分配，虚拟内存使用（由于操作系统将程序某部分换出啥的）
如何实现虚拟页式内存管理
需要访问该页时才将其调入内存中，一次只装入部分程序（产生缺页异常时OS才进行调页）
页面置换：当内存满了就要把暂时不要用的程序换出，避免占用空间，将需要的换入（页面置换算法）
为便于实现虚存管理，在页表中添加一些标记：
1.驻留位（存在位）
即前面的标志位，用于表示物理地址是否真实存在（0 no，1 yes）
当为0，可能物理地址还在外存上……产生缺页中断
2.保护位（限制操作权限）
只读，可读可写，不可执行，等
3.修改位（写）
若这一页被写过，则置1，未被写过，则置0（
若在内存里被写过，则这一夜在内存中与之前在外存中数据不一致，则要将变化后的导入到外存中，然后才进行释放；若修改位置0，表示未进行写操作，数据未变化，直接释放，不需要写回到外存）
4.访问位
该页最近是否被访问（被访置1，未访置0）
（要进行置换时可能会选择未被访问过的页换出）
4.4.2 example 2
左边是逻辑地址空间，共64K，每一页4K，其中所存内容X表示驻留位为0，其余表示为1，右边是物理地址空间。
操作1：将0地址的内容赋给寄存器，页帧号是2，2 X 4096对应8192，可行
操作2：将32780地址内容写到寄存器，而页表显示X，异常
缺页处理过程：
当驻留位为0时，表示发生缺页
此时若内存中还有空闲物理页，将这一页分配给即将过来的页，OS通过地址到硬盘中寻找对应页，将整个页读到内存中分配好的地址处，将页表的驻留位置为1，跳回到刚才异常处继续执行；若内存已无空闲物理空间，则在内存中根据某算法选择一页换出，当然，若换出的这页已经被写过，要将它先写到硬盘上，再换出，再换入，若未被写过，直接换出，然后这一页由被使用状态变为空闲状态，然后后面是一样的过程。
不同的硬盘存储形式：数据文件（大数组），执行程序代码，库的代码和数据，OS在硬盘上开辟swap区，可存放程序在内存运行过程中产生的数据
性能：平均访问时间取决于缺页次数，硬盘读写开销
10*(1-p）：未产生缺页时的时间
5000000p(1+q）：读操作，加上换出时可能要写硬盘，时间也是5ms
5000000p(1-q)+25000000pq=5000000p*(1+q)
使P足够小则效率高（局部性使得缺页次数少）
5.六种页面置换算法
目标：尽可能减少页面换入换出次数
当然，有些页是要常驻内存的，页面锁定
重点关注页，而非其他的
5.1 最优页面置换算法：根据将来的需求来调度（难以实现，作为评价标准）
5.2 先进先出算法（只体现了存在于内存中的时间，没有体现访问次数啥的）
（一开始是以a,b,c,d的顺序放在表中）
5.3 最近最久未使用算法
根据历史推测现在，而最优是根据未来推测现在（局部性）
如何实现（记录时间顺序）：
1.链表
每次访问内存时， 首先在链表中找到相应的页，将它移动到链表的首节点处；若没有在链表中找到，则将该表放到链表的首节点。
2.堆栈
访问页表时，先将页压入栈顶，再在栈中查找，存在则将之前就在栈中的删除（代价大，并不常使用）
5.4 时钟页面置换算法
链表and 栈 页的记录太精确，导致开销较大
当CPU访问某页时，会将页表项对应的access bit置1（由硬件完成），但是软件也可以对其进行操作，实现对页的粗略估计：若位为1，表示最近被访问过，为0，表示最近没被访问，即用bit表示时间信息，粗略但有效。
过程
将页组织一个环形链表，通过指针探测当前指向的页是否是最老的页，是则换出（这里的老是近似的老，没有之前的方法那么精确；通过 access bit 来判断，OS会定期将bit清零，指针不断扫描环形链表，若当前为1，表示近期有访问，若为0，表示近期未访问，则为老的页，换出）
左：Resident bit 表示映射关系是否正确，物理页是否存在
中：access bit
右：页帧号
产生缺页中断，从当前指针指向的页目录项看，access bit为1，则将bit置0（使它变老一点），指针顺时针往下挪一格，直到找到访问位为0的一项，进行替换，并将该位bit置1。
例如：想访问虚拟页为6的内容，则将将虚拟页为1的内容替换掉，将虚拟页为6的内容放到物理页为5的地址里。
第六步：将b的bit置为1，由硬件完成。
5.5 二次机会法
因为操作是分为读操作和写操作的
用Dirty bit表示，若之前被写过，则该位为1，没被写过（只有读操作），该位为0（该设置由硬件完成）
用该位来判断，若为1则还要将该页写到硬盘中去，若为0则不需要再写到硬盘。
用两个位来判断：
若找到两个为都为0，则找到了要被换出的页；
若access bit为0，dirty bit为1，将dirty bit置0，继续往下找；
同理，若access bit为1，dirty bit为0，将access bit置为0；
若两位都为1，将access bit置为0，dirty bit不变。
11——>01——>00——>被替换
10——>00——>被替换
将经常使用的dirty bit这个页有更多的机会留在内存中，减少被写过的页被换出的概率，尽量将只读的页换出，减少访问硬盘次数。
5.6 最不常用算法
效率，硬件资源
（在LFU基础上定期将次数寄存器右移一位？）
Belady现象产生原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此，被它置换出去的页面并不一定是进程不会访问的。
三个物理页帧:9次缺页中断
四个物理页帧:10次
解决:LRU算法
LRU满足栈算法,而FIFO算法不满足
希望访问序列有局部性的特征,算法才能有作用
6. 局部页面置换
程序对物理页帧的需求是可变的，一会多，一会少，所以如果实现物理页帧数目动态变化（动态分配）可提高利用率。
6.1 替换算法
可以有效实现全局页面置换算法
若算法有效，得要求序列有局部性，产生更少的缺页，用工作集模型表现局部性。
6.2 工作集：working site，一个进程当前正在使用的逻辑页面集合。
关键词：
-
当前：在某时间段内
-
逻辑页面集合：正在运行的程序所访问的集合
T表示开始时间， 表示时间段
t+窗口 形成时间段
程序执行过程中，t一直在变，窗口没变，对应的工作集也在变化
6.3 Example
首先起始时间是t1， 为10（从当前往回走），工作集页面有1，2，5，6，7，工作集大小为5.
起始时间为t2，窗口是10，工作集页面为3、4，局部性很好，工作集大小为2.
希望根据工作集大小变化来设定全局的页面置换算法
工作集与常驻集的区别
常驻集：当前执行的程序需要访问的页有哪些已经在内存中
工作集：当前执行的程序整个所需要的页（可能在也可能不在）
希望工作集都在常驻集中。
物理页多或少都不好，必须适中。
通过调整，将不需要的物理页给其他程序，实现全局最优。
7. 全局页面置换
7.1 工作集页置换算法
1.若要替换，则替换不在工作集里的页
2.时间平移，若发现某页不属于工作集窗口，也要将其替换出去。
初始顺序：e d a，后接访问序列
在物理内存中放哪些页取决于是否在工作集窗口内，不在就会被换出，确保内存中有足够的空间来放页。若页被写过还要写入硬盘中去。
（每一次访问都要判断是否换出）
7.2 基于缺页率页面置换算法（PFF）
基于缺页频度，灵活，缺页多，则将常驻集拉长，给予更多物理内存页；缺页少，将常驻集变短，给予更少物理内存页。
缺页率高，则增加工作集，常驻集增大；低，则减少工作集，减少常驻集。
调整工作集算法：调窗口
若产生缺页中断的时间间隔大于阈值，频率小，则将不在该时间段内访问的页都换出去，使程序所需要的工作集减少，压缩常驻集；若时间小于阈值，将缺的页直接放进工作集，使工作集and常驻集变大。
只在缺页中断时将页换出
根据工作集来调整，而局部的…是满了才换出….
8. 抖动
8.1 关键词
工作集：固有属性
常驻集：动态属性
参数：缺页平均时间，内存大小
期望：跑的程序尽量多and系统用率高
8.2 减少抖动
希望缺页平均时间与完成一次缺页的服务时间尽量相等
缺页平均时间除以服务时间，比值越大表示缺页的频度越低，就越好（平均时间长）
在使目前所跑程序尽量多的前提下，OS根据当前CPU的利用率动态调整程序个数，使抖动现象得到改善。
利用率与访问序列，物理页帧大小等有关。