第三章 存储系统

3.1 无存储器抽象

1. 用户可以直接访问物理内存，不安全
2. 运行多个程序很困难

3.2 地址空间

1. 地址空间的概念
   • 地址空间是一个进程可用于寻址内存的一套地址集合
   • 动态重定位将进程的地址空间和物理内存进行一个简单的映射
2. 交换技术
   • 交换：把一个进程完整调入内存，运行一段时间后存回磁盘
     • 不同的进程一直在交换
     • 内存紧缩：将交换产生的空洞尽量合成大的内存区
     • 动态分配：预留空间
   • 虚拟内存
3. 空闲内存管理（动态分配内存）
   • 使用位图的存储管理
     • 分配单元
   • 使用链表的存储管理
     • 链表中的一个结点或者包含一个进程，或者两个进程间的空闲区
     • 结点包含以下区域：空闲区或进程的指示标志、起始地址、长度和指向下一结点的指针
     • 首次适配算法
     • 下次适配算法
     • 最佳适配算法
     • 最差适配算法
     • 进程与空闲区用两个链表管理

3.3 虚拟内存

1. 虚拟内存的基本思想：每个程序有自己的地址空间，这个空间被分成多个块，每一块被称作一页或页面，每一页有连续的内存范围
2. 分页
   • 当程序运行时会产生的地址成为虚拟地址，它们构成虚拟地址空间
     • 没有虚拟内存的计算机上，系统将虚拟地址送到内存总线上，直接操作物理地址
     • 有虚拟内存的计算机上，系统将虚拟地址送到内存管理单元上（MMU），MMU将其映射到物理内存
   • 虚拟地址空间被分为页面，对应的物理内存单元被称为页框，通常一样大
     • 虚拟内存能比物理内存大，通过设置MMU可以使其完整映射，但不能解决这个问题
     • 页面没有被映射而被访问会引起页面中断陷阱
     • MMU内部
       • 虚拟地址二进制为16位，被分为4位的页号和12位的偏移量，前者表示16个页面，后者可以表示一页4096个全部地址之一
3. 页表（虚拟地址和物理地址的关系）
   • 最简单的映射实现：虚拟地址被分为虚拟页号和偏移量
   • 虚拟页号可以作为页表的索引，页表可以找到页框号，用页框号替换页号与偏移量拼接形成物理地址
   • 页表项的细节
     • 页框号
     • “在/不在”位
     • “保护”：指出允许访问的类型（权限）
     • “修改”/“访问”位：修改过要保存，否则丢弃
     • “禁止被高速缓存”
   • 虚拟内存的本质是建立对物理内存的抽象
4. 加速分页过程
   • 主要问题
     • 映射要很快
     • 如果虚拟地址空间很大，页表也要很大
   • 转换检测缓冲区
     • 大多数程序总是对少量页表进行多次访问
     • 为计算机设置一个小型硬件将虚拟地址直接映射到物理地址，这个硬件被称为转换检测缓冲区/相联存储器（TLB），通常在MMU中
   • 软件TLB管理：由操作系统管理被频繁访问的地址
     • 软失效：访问的页面在内存而不在TLB中
     • 硬失效：访问的页面不在内存不在TLB而在磁盘中
5. 针对大内存的页表
   • 多级页表
     • 避免把全部页表存在内存中
     • PT1、PT2、Offset
   • 倒排页表
     • 实际内存中的每一个页框有一个表项
     • 映射会变得困难，需要倒排而不能用索引直接访问
     • 散列表/TLB

3.4 页面置换算法

1. 发生页面中断时，操作系统要在内存中选择一个页面将其换出内存，腾出空间
2. 最优页面置换算法：置换最不容易被访问的页面（无法实现）
3. 最近未使用页面置换算法：随机地从类编号最小的非空类中选一个淘汰
4. 先进先出页面置换算法
5. 第二次机会页面置换算法：寻找最近的时钟间隔以来没有被访问的页面，是对先进先出页面置换算法的改进
6. 时钟页面置换算法：第二次机会页面置换算法的改进，环形链表
7. 最近最少使用页面置换算法
8. 软件模拟LRU
9. 工作集页面置换算法
10. 工作集时钟页面置换算法

3.5 分页系统中的设计问题

1. 局部分配策略与全局分配策略