虚拟存储管理（含有详细的页面置换算法）

1. 虚拟存储器的基本概念
(1) 虚拟存储器的引入
局部性原理
a． 空间局限性——程序的顺序执行。
b．时间局限性——循环操作。
虚拟存储器的定义
是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
(2) 虚拟存储器的实现方式——硬件支持
 分页请求系统
 请求分段系统
(3) 虚拟存储器的特征
离散性——内存分配时采用离散的分配方式，且仅在需要调入某部分程序和数据时，才为它申请内存空间。这是其它几个特征的基础。
多次性——一个作业被分成多次地调入内存运行，这是虚拟存储器的最重要特征。
对换性——允许在作业的运行过程中换进、换出。
虚拟性——能够从逻辑上扩充内存的容量，这是虚拟存储器的最重要目标。
2. 请求分页存储管理方式
    在分页系统的基础上，系统提供必要的硬件和软件支持，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。
（1） 硬件支持
页表机制——增加若干项，供换进、换出时参考。
 页号 物理块号 存在位P  访问位A  修改位M  外存地址 
页中断机构——一种特殊的中断
  在指令执行期间产生和处理中断信号。
  一条指令在执行期间，可能产生多次缺页中断。
页面分配
  考虑优先权的分配算法
（1） 页面调入策略
   何时调入页面——预调页和请求调页策略
   何处调入页面——文件区和对换区
   页面调入过程
（2） 页面置换算法
例：系统为进程分配了三个物理块，并考虑以下页面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
a) 最佳置换算法：将永不使用的，或者是在最长时间内不再被访问的页面淘汰。（向后看）
7   0  1  2  0   3  0  4   2  3   0  3  2   1  2   0  1  7  0  1 
7  2  2  2  2  2  2  2  2  2  2  2  2  2  2  7  7  7    
0  0  0  0  0  4  4  4  0  0  0  0  0  0  0  0  0  0    
1  1  1  3  3  3  3  3  3  3  3  1  1  1  1  1  1  1 
缺页率： 6/20=30%
b) 先进先出页面置换算法：选择在内存中驻留时间最久的页面予以淘汰。
7   0  1  2  0   3  0  4   2  3   0  3  2   1  2   0  1  7  0  1
7  2  2  2  2  4  4  4  0  0  0  0  0  0  0  7  7  7    
0  0  0  3  3  3  2  2  2  2  2  1  1  1  1  1  0  0    
1  1  1  1  0  0  0  3  3  3  3  3  2  2  2  2  2  1 
缺页率：12/20=60%
c) 最近最久未使用LRU置换算法: 选择最近最久未使用的页面予以淘汰。（向前看）
7   0  1  2  0   3  0  4   2  3   0  3  2   1  2   0  1  7  0  1 
7  2  2  2  2  4  4  4  0  0  0  1  1  1  1  1  1  1   
0  0  0  0  0  0  0  3  3  3  3  3  3  0  0  0  0  0    
1  1  1  3  3  3  2  2  2  2  2  2  2  2  2  7  7  7  
缺页率：9/20=45%
d) Clock置换算法——LRU近似算法
选择未使用过，又未被修改过的页面（A=0，M=0）淘汰。
根据A ，M(A访问位，M修改位)取值（0，1）的组合将页面分为四类。
3. 请求分段存储管理方式
    在分段系统的基础上，系统提供必要的硬件和软件支持，采用了请求调段的策略，形成段式虚拟存储系统。
(1) 硬件支持
段表机制——增加若干项，供程序换进、换出时参考。
 段号 段长 段的基址 存取方式 存在位P 访问位A 修改位M 增补位 外存地址 
缺段中断机构——一种特殊的中断
    在指令执行期间产生和处理中断信号。
    一条指令在执行期间，可能产生多次缺段中断。
    由于分段是信息的逻辑单位，因此不可能出现一条指令被分割在两个段中的情况，也不会有被传送的一组信息段分割在两个分段中的情况。
    段是不定长的，对缺段中断的处理要比对缺页中断的处理复杂。 有时需拼接，有时需淘汰几个段形成一个合适的空区以便调入所需分段。
 (2) 分段共享与保护
共享段表
 段名 段长 内存始址 状态 外存始址   
 共享进程计数count   
 状态 进程名 进程号 段号 存取控制   
 记录调用共享段的进程信息（不断增减、变化） 
共享段的分配与回收
分段保护