参考书籍：《计算机操作系统》第四版 汤小丹等编著
虚拟存储器：指具有调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
请求调入功能：在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序
置换功能：操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段
虚拟存储：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
速度和容量：虚拟存储量的扩大是以牺牲 CPU 工作时间以及内外存交换 时间为代价。
虚拟存储器的容量取决于主存与辅存的容量，最大容量是由计算机的地 址结构决定。
状态位P：表示该页是否已调入内存，供程序访问时参考
访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间，供选择页面换出时参考
修改位M：表示该页在调入内存后是否被修改过，若修改过，则置换该页时需重写该页至外存，供置换页面时参考
外存地址：指出该页在外存上的地址，供调入该页时参考
例：一个采用请求分页存储管理的计算机系统，其内存（实存）容量为256M 字节，虚拟内存容量（给用户的最大地址空间）为 4G 字节，页面大 小为 4K 字节，试问：
实存物理地址应设为多少位？28 位
实存中有多少物理块？64K
实存中最大块号是多少？64K-1
虚存地址应设多少位？32 位
虚拟地址空间最多可以有多少页？1M
页内最大偏移量是多少？4095
在请求分页系统中，外存分成了按离散分配方式存放文件的文件区和按连续分配 方式存放对换页的对换区。进程发出缺页请求时，从何处将缺页调入内存呢？
访问页 面成功（页在内存）次数为 S，缺页（页不在内存）次数为 F，则缺页率为：
f
=
F
F
+
S
f= \frac{F}{F + S}
f=F+SF
刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不久又再次被淘汰出内存，然后又要访问它，如此反复，使得系统把大部分时间用在了页面的调进换出上，这种现象称为抖动。
OPT：Optimal permutation algorithm
选择在最长时间内不再被访问的页面置换出
最佳置换算法是一种理想化的算法，性能最好，实际上这种算法无法实 现，因为页面访问的未来顺序很难精确预测，但可用该算法评价其它算 法的优劣。
例：假定系统为某进程分配了 3 个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时 3 个物理块均为空，计算采用最佳置换算 法时的缺页率？
缺页率：7/12
选择先进入内存的页面予以淘汰
假定系统为某进程分配了3 个物理块， 进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时 3 个物理块均为空，计算采用先进先出置换 算法时的缺页率？
缺页率：9/12
先进先出算法存在一种异常现象，即在某些情况下会出现分配给进程的物理块数增多，缺页次数有时增加，有时减少的奇怪现象，这种现象称为Belady异常现象
LRU：Least recently used
选择最近一段时间最长时间没有被访问过的页面予以淘汰
例： 假定系统为某进程分配了3 个物理块， 进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时 3 个物理块均为空，计算采用最近最久未使 用算法时的缺页率？
缺页率：10/12
寄存器：记录某个进程在内存中各页的使用情况，为每个进程在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3…R2R1R0
每当进程访问某页面时，将该页面对应寄存器的最高位 (Rn−1) 置 1，系统定期 (如 100ms) 将寄存器右移一位并将最高位补 0，如果把 n 位寄存器的数 看作是一个整数，于是寄存器数值最小的页面是最久未使用的页面。
栈：
利用一特殊的栈保存当前使用的页号，每当进程访问某页面时，把被访问 页面移到栈顶，于是栈底的页面就是最久未使用的页面。
LFU：Least frequently used
选择在最近时期使用最少的页面为淘汰页
LFU 置换算法为在内存中的每个页面设置一个移位寄存器来记录该页面 被访问的频率。
每当进程访问某页面时，将该页面对应寄存器的最高位 (Rn−1) 置 1，系统定期 (如 100ms) 将寄存器右移一位并将最高位补 0。在一段时间内，ΣRi最小的页面就是最近最少使用的页面。
LRU 是看时间长短，而 LFU 是看使用频率。
该算法为每页设置一个访问位，并将内存中的所有页链接成一个循环队列。当某页被访问时，其访问位被置1
置换算法在选择一页淘汰时，只需检查页的访问位，如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，再按照FIFO算法检查下一个页面（循环，不是回到队首）
注：上图中插入倒数第二个页面时，物理块2中的2不带星号，图片有误
除须考虑页面的使用情况外，还增加一个因素，即置换代价，这样选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。
由访问位 A 和修改位 M 可以组合成下面四种类型的页面：
1 从指针所指示的当前位置开始扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间 不改变访问位 A。
2 如果第一步失败，开始第二轮扫描，寻找 A=0 且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
3 如果第二步也失败，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步。
页面置换算法的比较
页面缓冲算法：用FIFO算法选择被置换页，选择换出的页不是立即换出，而是放入两个链表之一，如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入以修改页面链表的末尾。
这些空闲页面和已修改页面会在内存中停留一段时间。如果这些页面被再次访问，只需将其从相应链表中移出，就可以返回进程，从而减少一次 I/O 开销。
需调入新页，则将新页读入到空闲页面链表的第一个页面中，然后将其从该链表中移出。
当已修改的页面达到一定数目后，再将它们一起写入磁盘。这样能大大减少 I/O 操作的次数。
内存访问时间 t 约为 100ns(纳秒)=0.1μs (微秒)
缺页中断时间 ϵ 约为 25ms (毫秒) =25000 μs (微秒)
产生抖动的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。
驻留集：指请求分页存储管理中给进程分配的物理页面（块）的集合。
每个进程的驻留集越小，则同时驻留内存的进程就越多，CPU 利用率越高。
进程的驻留集太小的话，则缺页率高，请求调页的开销增大。
抖动的原因：多道程序度过高，导致平均驻留集过小。
工作集是指在某段时间间隔 ∆ 里，进程实际要访问的页面的集合。
把进程在某段时间间隔 ∆ 里，在时间 t 的工作集记为 w(t,∆)，变量 ∆ 称 为工作集“窗口尺寸”。
下图是某进程访问页面的序列和窗口大小分别为3，4，5时的工作集。可将工作集定义为，进程在时间间隔（t-∆，t）中引用页面的集合
如果页面正在使用，它就落在工作集中；如果不再使用，它将不出现在 相应的工作集中。工作集是局部性原理的近似表示。
抖动的预防方法
存取方式：由于应用程序中的段是信息的逻辑单位，可根据该信息的属性对它实施保护，故在段表中增加存取方式字段，如果该字段为两位，则存取属性是只执行、只读和允许读/写
存在位：指示本段是否已调入内存
增补位：表示本段在运行过程中是否做过动态增长
共享段计数count：记录有多少进程正在共享该分段
共享段的分配
当第一个使用共享段的进程提出请求时，由系统为该共享段分配一物理 区，并调入该共享段，同时修改相应的段表（该段的内存地址）和共享 段表，把 count 置为 1 。当其它进程需要调用此段时，不需再调入，只 需修改相应的段表和共享段表，再执行 count :=count+1 操作。
共享段的回收
当共享共享段的某进程不再使用该共享段时，修改相应的段表和共享段 表，执行 count :=count-1 操作。当最后一共享此段的进程也不再需要此 段时，则系统回收此共享段的物理区，同时修改共享段表（删除该表项）。
