操作系统复习.陈向群（06-07）（存储管理）

操作系统复习（06-07）

Chapter 06：存储管理概述

关键词

• 地址重定位、逻辑地址、物理地址、存储保护、存储共享、单一连续区、固定分区、覆盖技术、可变分区、页式、段式、虚拟内存、虚拟存储空间、虚拟地址、物理地址、页表/页表项、快表 TLB、驻留集、工作集、页面置换算法、清除策略、交换技术、段页式、Page Fault、加载控制、页缓冲技术、地址转换、地址变换、地址翻译、地址映射

思考题

• 怎样理解 “进程地址空间是对内存的抽象” 这句话？
• 结合课件 21 页的图、 22 页上的图说明采用的是哪一种内存分配算法？
• 课件 32 页上提到紧缩时要考虑的问题包括系统开销和移动时机两方面，请具体说明为什么要考虑这两个问题？
• 采用交换技术后，被换出内存后再换入内存的进程是否必须回到原处？如果不是，通过什么方式(技术或机制)可以做到
• 请给出一种管理磁盘交换区的方案。
• 课件 50 页上提出了两种解决进程空间增长的解决方案，请比较它们。你倾向哪一种解决方案，为什么？

内容

• 连续性 — 离散性
• 驻留性 — 交换性
• 一次性 — 多次性
• 地址重定位：将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址的过程
  • 静态地址重定位：加载到内存时
  • 动态地址重定位：逐条指令执行时
    • MMU

物理内存管理方案

• 空闲物理内存管理
  • 位图、空闲区表（已分配区表）、空闲块链表
• 内存分配算法
  • 首次适配（first fit）
  • 下次适配（next fit）
    • 从上次找到的空闲区处接着查找，其他和首次适配相同
  • 最佳适配（best fit）
  • 最差适配（worst ft）
• 回收问题
  • 合并空闲块
  • 上相邻、下相邻、上下都相邻、上下都不相邻

伙伴系统

• Linux 底层内存管理采用
• 例子
  • 整块分配
  • 只有伙伴才合并
  • 最佳适配

基本内存管理方案

• 单一用户连续区
• 固定分区
• 可变分区
  • 碎片
    • 紧缩技术（memory compaction）：在内存移动程序，将所有小的空闲区合并为较大的空闲区
• 页式
  • 内存块（物理页面、页框、页帧、page frame）
  • 页表、页表项
  • 逻辑地址：页号、页内偏移
  • 内碎片
• 段式
  • 段内连续，段间可以不连续
  • 用户程序地址空间：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名
  • 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定
  • 逻辑地址：段号、段内地址
• 段页式
  • 用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）
  • 每一段有一个页表

内存 “扩充”

• 覆盖技术（Overlaying）：早期操作系统
  • 程序执行过程中，程序的不同部分在内存中相互替代
    • 按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
    • 要求程序各模块之间有明确的调用结构
  • 程序员声明覆盖结构，操作系统完成自动覆盖

• 交换技术（Swapping）
  • 交换区：一般系统会指定一块特殊的磁盘区域作为交换空间（swap space），包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问

Chapter 07：虚拟存储管理

关键词

• 虚拟存储管理、硬件机制（地址转换）、页表/页表项、页错误处理、各种软件策略（读取策略、放置策略、置换策略、驻留集策略、清除策略、装载控制策略）

思考题

• 进程地址空间是对内存的抽象，请解读一下课件第 3 页上的图
• 虚拟内存、虚拟地址空间、虔拟地址、虔拟存储技术四个术语的解释
• 怎样理解操作系统中的资源转换技术？举例说明
• 结合课件 23-24 页的内容和图，梳理一下 CPU 取到虚拟地址并把转换为物理地址的过程
• 课件 30 页的图表示的是什么流程？请总结一下该流程的每一个步骤
• OPT 置换算法的作用是什么？在什么条件下可以实现它？
• 请比较老化算法（Aging）与 LRU 算法
• 课件 36 页上给出了设计页面置换算法时的典型思路:基于过去的行为来预测将来的行为。请列举日常生活中运用这一思路的例子
• 课件第 48 页的置换算法是一种简单的使用特殊硬件实现 LRU 的方法，请解释理由
• 实现工作集模型需要考虑哪些因素？开放性探讨一下：是否可以采用机器学习等方法实现工作集模型？有没有使用场录？利弊各是什么？
• TLB 什么时候刷新？怎么刷新？

内容

• 主要是虚拟页式存储管理
• 概念区分
  • 虚拟内存：物理内存和磁盘
  • 虚拟地址空间：分配给进程的虚拟内存
  • 虚拟地址：虚拟内存中某一位置的地址
  • 虚拟存储技术：当进程运行时，先将其一部分装入内存，另一部分暂时保存在磁盘；当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作
• lazy allocation
• 交换技术
• 请求调页（demand paging）、预先调页（prepaging）
• MMU

• 页表表项设计
  • 页框号
  • 有效位（valid、present）
  • 访问位（referenced、accessed）
  • 修改位（dirty、modified）
  • 保护位：读 / 写 / 执行（protection）

• 多级页表
• 二级页表
  • 页目录
• 四级页表示例

• 反转页表（节省内存）
  • 从物理地址空间出发，系统建立一张页表
  • 页表项记录进程i的某虚拟地址(虚页号) 与页框号的映射关系
  • 虚拟地址翻译：哈希表（拉链法解决冲突问题）
• 地址转换
  • 虚拟页面不在内存、页面非法、或者被保护 \(\Rightarrow\) Page Fault
• 快表 TLB
  • 相联存储器
  • 保存正在运行进程的页表的子集（部分表项）

• TLB 和 高速缓存

• 缺页异常：一种 page fault
• 驻留集管理
  • 固定分配策略、可变分配策略（通过缺页率评估）

页面置换算法

• 置换策略
  • 局部置换策略：缺页进程的驻留集
  • 全局置换策略：内存中所有未锁定的页框
• 置换策略
  • 目标：置换最近最不可能访问的页
  • 局部性原理：基于过去预测未来
• 页框锁定
  • 操作系统核心代码、关键数据结构、I/O 缓冲区

页面置换算法 replacement

理想（最佳、最优）置换算法（OPT）

先进先出页面置换算法（FIFO）

• 页面链表实现

第二次机会置换算法（SCR）

• 按照先进先出算法选择某一页面，检查其访问位 R
  • 如果为 0，则置换该页
  • 如果为 1，则给第二次机会，并将访问位置 0，把该页面放到链表的尾端（新放入一样）

时钟算法（Clock）

• 循环链表
• 不移动页面位置

最近未使用算法（NRU）

• 选择在最近一段时间内未使用过的一页并置换
• 算法
  • 访问位（R）、修改位（M）
  • 分类
    • 第 0 类：无访问，无修改
    • 第 1 类：无访问，有修改
    • 第 2 类：有访问，无修改
    • 第 3 类：有访问，有修改
  • 随机从编号最小的非空类中选择一页置换
• 实现
  • 1. 从指针的当前位置开始，扫描页框缓冲区，选择遇到的第一个页框（r=0；m=0）用于置换（本扫描过程中，对访问位不做任何修改）
  • 2. 如果第 1 步失败，则重新扫描，选择第一个（r=0；m=1）的页框（本次扫描过程中，对每个跳过的页框，将其访问位设置成 0）
  • 3. 如果第 2 步失败，指针将回到它的最初位置，并且集合中所有页框的访问位均为 0。重复第 1 步，并且，如果有必要，重复第 2 步
• 实现的区别就是修改了访问位
  • 如果只跑一次这个算法结果是一样的
• NRU 不带时间戳

最近少使用算法 (LRU)

• LRU 性能接近 OPT
• 实现：时间戳、维护一个访问页的栈
  • 开销大
• 一种硬件实现
  • 访问：行置为 1，列置为 0
  • 置换：把和最小的行替换掉
• 一个例子：页面访问顺序 0, 1, 2, 3, 2, 1, 0, 3, 2, 3

最不经常使用算法（NFU）

• 选择访问次数最少的页面置换
• 实现：
  • 软件计数器，一页一个，初值为 0
  • 每次时钟中断时，计数器加 R
  • 发生缺页中断时，选择计数器值最小的一页置换

老化算法（Aging）

• 改进（模拟LRU）：计数器在加 R 前先右移一位，R 位加到计数器的最左端
• 感觉和 LRU 相似，但是计数器的位数是有限的，会把较早的访问情况冲掉

页面置换例子

• 注意 FIFO 访问已经缓存的页的时候不移动链表（相当于不修改时间戳）

• LRU

• OPT

Belady 现象

• FIFO：当分配给进程的物理页面数增加时，缺页次数反而增加

影响缺页次数的因素

• 因素
  • 页面置换算法
  • 页面本身的大小
    • 最佳页面大小：\(\sqrt{2se}\)
  • 程序的编制方法
  • 分配给进程的物理页面数
• 颠簸（Thrashing，抖动）
  • 虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动

工作集模型

• 活跃页面
• 工作集 \(W(t,\Delta)\)
  • 该进程在过去的 \(\Delta\) 个虚拟时间单位中使用的虚拟页面集合
• 驻留集：当前时刻，进程实际驻留在内存当中的页框集合
• 思路：找出一个不在工作集中的页面并置换它
  • 判定：每个页表项中有一个字段记录该页面最后一次被访问的时间
• 算法实现
  • 扫描所有页表项，执行操作
  • 1. 如果一个页面的 R 位是 1，则将该页面的最后一次访问时间设为当前时间，将 R 位清零
  • 2. 如果一个页面的 R 位是 0，则检查该页面的访问时间是否在 “当前时间 - T” 之前
    2. [1] 如果是，则该页面为被置换的页面；
    3. [2] 如果不是，记录当前所有被扫描过页面的最后访问时间里面的最小值。扫描下一个页面并重复 (1)、(2)

2. 类似的思想：监视缺页率增减驻留集大小

清除策略

• 保存一定数目的页框供给比使用所有内存并在需要时搜索一个页框有更好的性能
• 一个置换出去但是还未被覆盖的页面，当他再次被访问的时候，直接将其移出空闲缓冲池即可
• 分页守护进程：检查内存状态，保证有大量空闲页框
• 双指针时钟：前指针由分页守护进程控制
• 页缓冲技术
  • 空闲页链表
  • 修改页链表：簇的方式写回（减少 I/O）

加载控制

• 系统并发度：驻留在内存中的进程数目
• 通过调节并发进程数进行系统负载控制
  • 交换到磁盘

内存映射文件

• mmap()
• lazy 读入
• 共享库文件中的共享对象
• 私有的写时拷贝对象

策略与机制分离

• Mach
• 存储管理系统被分为三个部分
  • 底层MMU处理程序（与机器相关）
  • 作为内核一部分的缺页中断处理程序（与机器无关）
  • 运行在用户空间中的外部页面调度程序（策略）

Chapter 07-2：Windows 虚拟内存管理技术

思考题

• 进程虚拟地址空间的大小由谁决定？
• 进程虚拟地址空间的布局由谁确定？
• 创建一个进程，加载相应的可执行文件并且执行的过程是怎样的？
• 当捕获到缺页错误时，操作系统如何知道程序当前所需要的页在可执行文件中的哪一个位置？
• 总结 Windows 自映射机制的实现原理
• 总结 Windows 的物理内存管理

内容

Intel x86 虚拟内存机制

Windows 虚拟内存管理

内存管理器的组成部分

• 工作集管理器（MmWorkingSetManager）
• 进程/栈交换器（KeSwapProcessOrStack）
• 修改页面写出器（MiModifiedPageWriter）
• 映射页面写出器（MiMappedPageWriter）
• 零页线程（MmZeroPageThread）

缺页异常处理

• CPU 翻译的时候发现页表项无效 \(\Rightarrow\) 缺页中断

• 发生缺页中断时， CPU 自动将引发异常时访问的虚拟地址存入寄存器 CR2

• 走中断异常处理流程

• 根据操作系统提供的异常处理程序开始处理

• 页目录与自映射机制

  • 专用寄存器（x86 中为 CR3）用于保存页目录的物理地址

工作集

• 基于工作集模型的页面置换算法

用户空间内存分配方式

• 以页为单位的虚拟内存分配方式
  • 两阶段：保留、提交
  • 如何判断保留/提交
    • 页表可以判断提交，但是无法判断保留
    • VAD 虚拟地址描述符，平衡二叉树
• 内存映射文件
• 内存堆方法
  • 适用于大量的小型内存申请

物理内存管理

• 页框的状态
  • 活动（Active）/ 有效（Valid ）：在工作集中
  • 过渡（Transition）：读入页框 / 从页框写出
  • 空闲（Free）
  • 零初始化（zeroed）：空闲且被零初始化
  • 坏（Bad ）：硬件坏了
  • 后备（standby）：页框内容未修改，invalid、transition，但是内容还在
  • 修改（Modified）：页框内容修改过，invalid、transition，但是内容还在
• 页表与页框号数据库

• 了解每一条线是为什么
  • 进程的工作集出来：页框不够用得回收（看是否被修改）、进程结束