虚存设计关键问题

虚存设计

1. 设计目标
   • 保护
     • 隔离进程之间的错误
   • 虚拟化
     • 用磁盘来扩展物理内存的容量
     • 方便用户进行编程（进程地址空间从0-max）
2. 虚存设计时要考虑的问题
   • 虚实映射
     • 映射机制：分段/分页
     • 映射加速：TLB/TLB Miss/TLB表项数目
     • 映射开销：页大小和页表大小
   • 按需加载和页替换
     • 缺页处理
     • 页替换：替换算法/颠簸/pin和unpin
     • 后备存储：Swap
   • 虚存使用
     • 清零
     • Copy on Write
     • 共享内存

虚存设计问题 —— 虚实映射设计问题

页大小

1. 大页
   • 好处：页表小 且 磁盘I/O高效
   • 不足：内部碎片
     • 进程执行不需要的部分也放进了内存
     • 页可能不满，存在浪费
2. 小页
   • 好处：减少内部碎片
   • 不足：页表大
     • 占用更多的内存
     • 加载时间更长
     • 查找虚页的时间更长
   • 不足：磁盘I/O不够高效
     • 进程加载、页替换

虚存设计问题 —— 页替换设计问题

颠簸

1. 颠簸的概念
   • 频繁发生缺页，运行速度很慢
   • 进程被阻塞，等待页从磁盘取进内存
   • 从磁盘中读入一页_{10ms，执行一条指令}几ns
2. 虚存访问时间
   • 请求平均访问时间 = h*内存访问时间 + (1-h)*磁盘访问时间（h：命中率）
   • 例如：假设内存访问时间 = 100ns，磁盘访问时间 = 10ms，h=0.9
     • 请求平均访问时间 = 0.9*100ns + 0.1*10ms = 1.0009ms
3. 颠簸的原因
   • 进程的工作集 > 可用的物理内存
   • 进程过多，即使单个进程都小于内存
   • 内存没有被很好地回收利用
4. 如何避免
   • 多进程时，哪些工作集放进内存
   • 多进程时，如何分配页

多进程时，哪些工作集放进内存

1. 将进程分为两组
   • 活跃组：工作集加载进内存
   • 不活跃组：工作集不加载进内存
2. 如果确定哪些进程是不活跃的
   • 等待事件（键盘、鼠标等IO设备）
   • 等待资源
   • 典型方法是设定一个等待时间阈值，如果超过了这个阈值则被称为不活跃进程
3. 两种调度器
   • 长期调度器（准入调度器）决定
     • 哪些进程可以同时运行（CPU vs I/O，工作集之和，...）
     • 哪些进程是不活跃的进程，将它们换出到磁盘
     • 哪些进程是活跃的进程，将它们换入到内存
   • 短期调度器（CPU调度器）执行CPU调度算法，决定
     • 把CPU分配给哪个活跃进程

多进程时，如何分配页

1. 多个进程同时运行的时候，替换哪个进程的页框？
   • 全局分配
     • 从所有进程的所有页框中选择
   • 局部分配
     • 只从本进程（发生缺页的进程）的页框中选择
2. 全局分配 vs 局部分配
   • 全局分配
     • 从所有进程的所有页框中选择
     • 可替换其他进程的页框
     • 每个进程运行期间，其内存大小是动态变化的
     • 好处：全局资源调配
     • 坏处：没有隔离，干扰其他进程/收到其他进程的页替换干扰
       • 不能控制各个进程的内存使用量
   • 局部分配
     • 只能从本进程（发生缺页的进程）自己的页框中选择
     • 一个进程运行期间，固定其内存大小不变
       • 页框池：分配给进程的页框的集合，不同进程的页框池大小可不同
     • 好处：隔离，不影响其他进程
     • 坏处：不灵活
       • 进程使用内存频繁会产生颠簸
       • 难以充分利用内存：每个进程对内存的需求不一样

平衡分配

1. 局部分配 + 池大小动态调整
   • 每个进程有自己的页框池（pool）
   • 从自己的池中分配页，且从自己的工作集中替换页
   • 用一种机制来运行时动态调整每个池的大小
     • 初始大小 + 动态调整
2. 进程加载方式：进程换入时
   • 纯粹的按需加载页：加载较慢
   • 预加载：先加载部分页 -> 初始池大小
   • 初始池大小约等于工作集的大小
3. 初始池大小
   • 固定大小：所有进程都一样
   • 平均分配
   • 根据进程大小按照比例分配
4. 动态调整池大小：进程大小变化
   • PFF算法（Page Fault Frequency）
     • 缺页率 PFR：进程每秒产生多少次缺页
     • 对应大多数替换策略，PFR随分配给进程的内存增加而减少
   • 根据进程的PFR来调整分配给它的内存量（pool size）
     • 当PFR高于A，就增加其内存（pool 增大）
     • 当PFR低于B，就缩小其内存（pool 减小）
   • PFR的计算
     • 方法1：只看当前1秒钟内的缺页次数Ri
     • 方法2：求滑动均值
       • 例如 \(PFR_i = (R_i + PFR_{i-1}) / 2\)

后备存储

1. 交换区（Swap Area）
   • 在磁盘上
   • 专门用于存储进程换出页
   • 交换分区（Swap Partition）
     • 用专门的磁盘分区保存专门的换出数据
   • 交换文件
     • 用文件保存换出的数据
2. 交换空间分配
   • 静态分配
     • 创建进程时分配，进程结束时回收
     • 大小：进程映像
     • 进程控制块记录交换空间的磁盘地址
     • 绑定：一个虚存页 <-> 一个磁盘页
       • 磁盘页称为shadow page
     • 初始化：两种方法
       • 页换出：进程映像拷贝到交换区
       • 页换入：进程映像加载进内存
     • 缺点：难以增长（栈段/堆）
   • 动态分配
     • 创建进程时不分配
     • 页换出时分配，页换入时回收
     • 虚页和磁盘页不绑定
       • 多次换出，分配不同的磁盘页
     • PTE中记录页的磁盘地址
     • 一个优化：程序text段
       • 直接用磁盘上的可执行文件作为交换区，减少交换区的大小
       • 换出时直接丢弃（只读的），减少不必要的写回
3. 页地址转换
   • PTE： 虚页 -> 页框和磁盘
     • 如果valid bit=1，物理页号pp#
     • 如果valid bit=0，磁盘页号dp#
   • 换出
     • 将PTE和TLB置为无效
     • 把页拷贝到磁盘
     • 将磁盘页号写回PTE
   • 换入
     • 找一个空闲页框（可能触发页替换）
     • 将页从磁盘拷贝到这个页框中
     • 将页框号填入PTE中，并将PTE置为有效

钉住页（pin/unpin）

1. 为什么需要？
   • 有些页需要频繁访问，换出后又会被换入，影响系统性能
   • 数据再内外存间进行传输时，需要传输的页框不能被换出，否则CPU会把新内容写入这些页框
2. 如何设计？
   • 用一个数据结构来记录所有钉住的页
   • 换页算法在替换页时检查该数据结构
     • 如果页被钉住，则不替换它，重新再选择一页

虚存设计问题 —— 页使用设计问题

清零页

1. 将页清零
   • 把页置成全0
   • 堆和栈的数据都要初始化
2. 如何实现
   • 对于堆和栈段中的页，当它们第一次发生page fault时，将他们清零
   • 可以通过一个专门的线程来实现清零
3. 不做页清零可能会引起安全问题

写时复制（Copy-On-Write）

1. 该技术用于创建子进程（fork系统调用）
2. 原理
   • 子进程的地址空间使用其父进程相同的映射
   • 将所有的页置成 read-only
   • 将子进程置成就绪
   • 对于读，可以随意读
   • 对于写，产生page fault
     • 修改PTE，映射到一个新的物理页
     • 将页内容全部拷贝到新物理页
     • 重新运行发生缺页的指令

进程间共享内存

1. 两个进程的页表共享一些物理页
   • 进程间通信
   • 进程间数据共享
2. 涉及问题
   • 共享页的换入换出
     • 可能会影响到多个进程，需要使用pin/unpin钉住页
   • 有共享页的进程的工作集
     • 共享页优先进入工作集
   • 有共享页的进程结束
     • 根据情况确定是否释放共享页

UNIX 和 Linux 的虚存机制

UNIX的地址空间

1. Text段：只读 & 大小不变
2. 数据段
   • 初始化数据
   • 未初始化数据：BSS段
   • Heap区
3. 栈段
4. 内存映射文件（Memory Mapped File）
   • 将一个文件映射进虚存，并像访问内存一样访问文件
   • mmap 和 unmap

BSD4的虚存

1. 物理内存划分
   • Core map(pin): 所有页框的描述信息
   • 内核(pin)
   • 其它页框：给用户进程
2. 页替换
   • 运行换页守护进程(page daemon)，直到有足够的空闲页
   • 早期BSD使用原始的Clock替换算法（FIFO with Second Chance）
   • 后来的BSD使用双表针的Clock算法
   • 如果page daemon找不到足够多的空闲页的话，则运行swapper
     • 寻找idle时间超过20秒及以上的进程
     • 最大的4个进程

Linux的地址空间

1. 32位机的地址空间
   • 3GB 的用户空间
   • 1GB 的内核空间
2. 栈段从3GB位置向下增长
   • 初始时保存进程的环境变量和命令行参数
3. 数据段
   • 大小可变
   • BSS段：未初始化的全局变量
     • 页加载时初始为0
     • zero page: 避免分配大量全0的物理页
4. 系统调用
   • brk(addr) —— change data segment size
   • mmap(addr,len,prot,flags,fd,offset) —— Map a file in
   • unmap(addr,len) —— Unmap a file
5. Linux的地址转换
   • 2.6.11及之后的Linux都是使用4级页表
     • 虚地址划分为5段: GDT UDT MDT PT 和 Offset
     • 如何支持2级页表的MMU（例如Pentium）
       • 通过将UDT和MDT都设置为只有一个表项
6. Linux的物理页分配
   • 伙伴算法
     • 初始时：只有一个段，含全部可用空间
     • 分配空间，m页：找size>=m 且 size最小的段，假设其为n
     • 如果n>=2m，则将该段对分为两个size=n/2的段
     • 重复对分，直到n>=m>n/2
     • 释放空间：m页，如果其伙伴也是空闲的，则不断合并它们，直到找不到空闲伙伴为止
   • 数据结构
     • 空闲链表数组：每条链上的页大小为2的幂
7. Linux的页替换
   • 方法
     • 保持一定数量的空闲页
     • 文件缓存（page cache）使用Clock算法
     • 未使用的共享页使用Clock算法
     • 用户进程的内存使用改进的Clock算法
       • 两条链
       • Active List：所有进程的工作集
       • Inactive List：回收的候选页
       • Refill是将页从active list移动到inactive list