04 虚拟内存 | 《操作系统》笔记
这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。
起因
- 在计算机系统中,尤其是在多道程序运行的环境下，可能会出现内存不够用的情况，怎么办?
- 如果是程序太大，超过了内存的容量，可以采用手动的覆盖(overlay)技术，只把需要的指令和数据保存在内存当中
- 如果是程序太多，超过了内存的容量，可以采用自动的交换(swapping)技术，把暂时不能执行的程序送到外存中
- 如果想要在有限容量的内存中，以更小的页粒度为单位装入更多更大的程序，可以采用自动的虚拟存储技术
覆盖技术（程序员完成）
- 目标
- 是在较小的可用内存中运行较大的程序，常用于多道程序系统，与分区存储管理配合使用
- 原理
- 把程序按照其自身逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行
- 必要部分（常用功能）的代码和数据常驻内存
- 可选部分(不常用功能)在其他程序模块中实现，平时存放在外存中，在需要用到时才装入内存
- 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖，即这些模块共用一个分区
- 把程序按照其自身逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行
- 缺点
- 由程序员来把一个大的程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，费时费力，增加了编程的复杂度
- 覆盖模块从外存装入内存，实际上是以时间延长来换取空间节省
交换技术（操作系统完成）
- 目标
- 多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源
- 方法
- 可将暂时不能运行的程序送到外存，从而获得空闲内存空间
- 操作系统把一个进程的整个地址空间的内容保存到外存中（换出，swap out），而将外存中的某个进程的地址空间读入到内存中（换入，swap in）
- 换入换出内容的大小为整个程序的地址空间
- 交换技术实现中的几个问题
- 交换时机的确定
- 只当内存空间不够或有不够的危险时换出
- 交换区的大小
- 必须足够大以存放所有用户进程的所有内存映像的拷贝
- 必须能对这些内存映像进行直接存取
- 程序换入时的重定位
- 换出后再换入的内存位置不一定要在原来的位置上
- 最好采用动态地址映射的方法
- 交换时机的确定
- 覆盖与交换的比较
- 覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构（程序员完成，单位是模块）
- 交换技术是以在内存中的程序大小为单位来进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构（操作系统完成，单位是进程）
- 交换发生在内存中程序与管理程序或操作系统之间，而覆盖则发生在运行程序的内部
虚存技术
- 背景
- 覆盖技术需要程序员自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担
- 交换技术以进程作为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销
- 目标
- 像覆盖技术那样，不是把程序的所有内容都放在内存中，因而能够运行比当前的空闲内存空间还要大的程序；但做得更好，由操作系统自动来完成，无须程序员的干涉
- 像交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间；但做得更好，只对进程的部分内容在内存和外存之间进行交换
程序局部性原理（principle of locality）
- 基本概念
- 程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域
- 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短时期内
- 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内
- 程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的
- 基本特征
- 大的用户空间
- 通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离
- 如 32 位的虚拟地址理论上可以访问 4GB，而可能计算机上仅有 256M 的物理内存，但硬盘容量大于 4GB
- 部分交换
- 与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的
- 不连续性
- 物理内存分配的不连续，虚拟地址空间使用的不连续
- 大的用户空间
- 虚拟页式内存管理
- 大部分虚拟存储系统都采用虚拟页式存储管理技术，即在页式存储管理的基础上增加请求调页和页面置换功能
- 基本思路
- 当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存,而是只装入部分的页面，就可启动程序运行
- 在运行的过程中，如果发现要运行的程序或要访问数据不在内存则向系统发出缺页中断请求，系统在处理这个中断时，将外存相应的页面调入内存，使得该程序能够继续运行
- 缺页中断（Page fault，又名硬错误、硬中断、分页错误、寻页缺失、缺页中断、页故障等）指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由中央处理器的内存管理单元所发出的中断
- 页表表项
- 驻留位
- 表示该页是在内存还是在外存
- 如果该位等于 1，表示该页位于内存当中，即该页表项是有效的
- 如果该位等于 0，表示该页当前还在外存当中，如果访问该页表项，将导致缺页中断
- 保护位
- 表示允许对该页做何种类型的访问，如只读、可读写、可执行等
- 修改位
- 表明此页在内存中是否被修改过
- 当系统回收该物理页面时根据此位来决定是否把它的内容写回外存
- 访问位
- 如果该页面被访问过（包括读操作或写操作），则设置此位
- 表明该页是否经常被访问，如果不是的话则可以置换出去，用于页面置换算法
- 缺页中断处理过程
- 如果在内存中有空闲的物理页面，则分配一物理页帧 f，然后转第 4 步；否则转第 2 步
- 采用某种页面置换算法，选择一个将被替换的物理页帧f，它所对应的逻辑页为 q；如果该页在内存期间被修改过，则需把它写回外存
- 对 q 所对应的页表项进行修改，把驻留位置为 0
- 将需要访问的页 p 装入到物理页面 f 当中
- 修改 p 所对应的页表项的内容，把驻留位置为 1，把物理页帧号置为 f
- 重新运行被中断的指令
- 在何处保存未被映射的页？
- 能够简单地识别在二级存储器中的页
- 交换空间（磁盘或者文件）
- 特殊格式，用于存储未被映射的页面
- 后备存储(backing store)
- 一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中）中的某个位置
- 代码段：映射到可执行二进制文件
- 动态加载的共享库程序段：映射到动态调用的库文件
- 其它段：可能被映射到交换文件(swap file)
- 虚拟内存性能
页面置换算法
- 功能与目标
- 实验设置与评价方法
- 局部页面置换算法
- 最优页面置换算法(OPT, optimal)
- 先进先出算法(FIFO)
- 最近最久未使用算法(LRU, Least Recently Used)
- 时钟页面置换算法(Clock)
- 最不常用算法(LFU, Least Frequently Used)
- Belady 现象
- LRU、FIFO 和 Clock 的比较
- 全局页面置换算法
- 工作集模型
- 工作集页置换算法
- 缺页率置换算法
04 虚拟内存 | 《操作系统》笔记