存储管理
单道程序存储管理¶
内存分为两个区域：系统区和用户区，每次把一个应用程序塞到用户区内存里，以来共享内存。当它运行结束后，操作系统装入一个新的程序把它覆盖。
- 优点：简单、开销小，易于管理，适合于单用户单任务的情形
- 缺点
- 每次只能运行一个程序
- 内存资源的使用效率不高
- 应用程序的 bug 会破坏 OS
- 地址空间有限
如何实现多道存储管理¶
也就是说在内存中同时有多个进程运行。
- 需要考虑的问题
分区存储管理¶
内存分为两大区域：系统区和用户区，用户区又划分为若干分区，一个进程占用一个分区。
- 适合多道程序系统和分时系统，支持多个程序并发执行
固定分区存储管理¶
各个用户分区的个数、位置和大小确定，就固定不变。
- 分区的大小是否相等？
- 程序大小不同，则进程占用空间不同
- 多个小分区，适量中等分区，少量大分区
- 进程个数多于分区个数？
- 增加一个输入队列
如何实现？¶
- 数据结构：设置内存分配表
- 内存分配：先放入输入队列，然后采用最先匹配法，最佳匹配法等算法
- 内存回收：简单
可变分区的实现¶
如何实现可变分区的存储管理技术？
分区链表¶
系统维护一个有序的分区链表，跟踪记录每个内存分区的情况，包括该分区的状态、起始地址、长度等信息。
分区分配算法¶
当一个新进程到来时，需要为它寻找分配某个空闲分区，其大小必须大于或等于该进程的要求。
- 最先匹配法
- 从分区链表的头结点开始向后找，知道找到一个结点长度大于新进程对内存大小的要求的结点
- 下次匹配法
- 和最先匹配法类似，每找到一个合适的结点时，就把当前的位置记录下来，下次从这个位置开始继续往下找
- 最佳匹配法
- 找到与新进程对内存大小要求最接近的空闲分区之中。
- 缺点：分割后剩余的空闲分区将会很小，甚至无法使用
- 最坏匹配法
- 将最大的空闲区切一部分分给请求者
分区回收算法¶
当一个进程运行结束，释放它所占用的分区后，需要将相邻的几个空闲分区合并为一个大的空闲分区
存储管理案例¶
内存中的程序执行¶
进程的地址空间，内存布局是什么样的？
- 全局变量：固定地址，其它源文件可见
- 静态全局变量：固定地址，但只在本文件中可见
- 函数参数：位于栈帧之中，动态创建，动态释放
- 静态局部变量：固定地址，只在本函数中可见
- 普通局部变量：位于栈帧中，只在本函数可见
- 动态申请的内存：位于堆中
这些固定地址的东西放在数据段中，数据段位于代码段和动态堆空间之间。
地址映射¶
物理地址¶
- 把内存分成很多个大小相等的存储单元，每个单元给一个编号，这个编号称为物理地址，可以直接寻址。物理地址的集合称为物理地址空间。
逻辑地址¶
- 也叫相对地址，虚地址
- 用户程序经汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都是相对首地址来编址；
- 不能用逻辑地址在内存中读取信息
地址映射¶
- 需要将用户程序中的逻辑地址转换为运行时有及其直接寻址的物理地址，此过程称为地址映射。
- 静态地址映射：当用户程序被装入内存时，直接对指令代码进行修改，一次性实现到物理地址的转换。
- 动态地址映射：在程序运行过程中，当需要访问内存单元时再来进行地址转换
- 由硬件地址映射机制完成，
- 在程序运行时，硬件自动完成地址映射
存储保护¶
为了防止一个用户程序去访问其它用户程序的内存分区，保护操作系统免受用户程序的破坏。
- 最简单的做法：在基地址寄存器的基础上再增加一个限长寄存器，这两者一起，就定义了进程所在的分区
页式存储管理¶
基本原理¶
- 把物理内存划分成许多个固定大小的内存块，称为物理页面，或页框（page frame）
- 把逻辑地址空间划分为大小相同的块，称为逻辑页面（page）
- 页面大小为 \(2^n\)
- 若要运行一个大小为 \(n\) 个页面的程序，需要有 \(n\) 个空闲的物理页面，这些页面不必是连续的。
需要解决的问题¶
- 用于存储管理的数据结构？
- 当一个进程到来时，如何分配内存？
- 当一个进程运行结束，如何回收内存？
- 当一个进程被加载到内存以后，如何正确运行（地址映射）？
数据结构¶
页表：为每个进程建立一个页表，页表给出逻辑页号和具体内存块号之间的对应关系。
物理页面表：在系统中设立一张物理页面表，用于描述内存空间中，各个物理页面的分配使用状况，一个具体的实现方式为“位示图”
内存的分配与回收¶
内存的分配：
- 计算一个进程需要的页面数 \(N\)，并查看位示图，看看空闲页面够不够
- 若有足够的空闲页面，申请一个页表，其长度为 \(N\)，把页表的起始地址填入 PCB
- 分配 \(N\) 个空闲物理页面，将其编号填入页表
- 修改位示图
内存的回收：
- 就是上面过程的简单逆过程
地址映射¶
- 对于给定的逻辑地址，找到逻辑页面号和页内偏移量
- 查页表
- 计算物理地址
逻辑地址的划分¶
地址的高位部分为页号，低位部分为页内偏移量（所以说页表的大小为 \(2 ^k\)）
- 计算的方法
- 逻辑页号 = 虚地址 / 页大小
- 业内偏移 = 虚地址 % 页大小
- 这和上面那个过程是一样的
页表的具体实现¶
- 页表保存在内存当中
- 放在 kernel 中
- 设置一个页表基址寄存器（Page-Table base register, PTBR），指向页表起始地址
- 设置一个页表长度寄存器（Page-Table length register，PTLR），指示页表大小
每一次访问内存时，都要两次访问内存（页表、数据/指令）。
加快页表的查询速度¶
- 一种特殊的快速查找硬件：TLB（Translation Lookaside Buffer）或称 associative memory。
优缺点¶
- 优点
- 没有外碎片，内碎片大小不超过页面的大小
- 一个程序不必连续存放
- 便于管理
- 缺点
- 程序必须一次性装入内存
- 每个进程都得整一个页表
段式存储管理¶
动机¶
页式存储管理只有一个逻辑地址空间，即一维的线性连续空间。
- 存储保护
- 存储共享
基本原理¶
- 对程序的每个逻辑单元（代码、数据、栈等）设立一个完全独立的地址空间，称为“段”。每个段的内部是一维的线性连续地址，大小可不同。
- 对于物理内存来说，采用可变分区的管理办法
- 当一个程序需要装入内存时，以段为单位进行分配，把每个段装入一个内存分区中，这些分区不必是连续的。
具体实现¶
用户空间地址为二维地址 （段号，段内偏移）。实现方式：
- 地址高端为段号，低端为偏移
- 指令中显式给出段号和段内偏移
段表：系统为每个进程建立一个段表，它给出了进程当中的每一个段和它所对应的内存分区之间的映射关系。段表保存在内存中，同理整两个 STBR 和 STLR，指示段表的起始地址和程序中段的个数
优缺点¶
- 优点
- 程序通过分段来划分多个模块，每个模块可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享
- 一个程序不必连续存放，没有内碎片。
- 缺点
- 程序必须全部装入内存
- 有外碎片
段页式存储管理¶
先把程序划分为段，然后在段内分页
- 以段式存储方案进行内存划分
- 段表记录每个段的页表起始地址和段长，而不是该段所在内存分区的起始地址
- 以页面为单位进行内存分配
- 记录逻辑页面号与物理页面号之间的对应关系
覆盖技术与交换技术¶
问题：内存不够用了怎么办？
- 如果是程序太大，超过了空闲内存的容量，没有办法全部装入内存，在这种情形下，可以采用覆盖技术，只把需要的指令和数据保存在内存中，而把其它的指令和数据保存在外存中。
- 如果是程序个数太多，它们需要的总和超过了内存的容量。在这种情况下，可以采用交换技术，把暂时不能执行的程序送到外存中
- 这两种问题同时出现时，可以采用虚拟存储技术
虚拟存储技术¶
内存可能出现不够用的情况。
理论依据：程序的局部性原理，实际上 TLB， Cache都是局部性原理应用的成功案例
基本思路¶
采用虚拟页式存储管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能。
保存到磁盘上的那部分存储称为 后备存储（backing store），内存物理页面称为 Page frame，磁盘上的页面称为 backing frame（后备页面）
基本原理
在装入程序时，不必把整个程序都装入内存中，而只需要将当前需要执行的那部分页面或段装入到内存，就可以让程序开始执行。
在程序的执行过程中，一方面，如果需要执行的指令或需要访问的数据不在内存中，就称为缺页或缺段，在这种情形下，或产生一个硬件中断，中断处理程序中，CPU通知操作系统将相应的页面或段调入到内存，然后继续执行程序。
同时，操作系统将内存中暂时不需要的页面或段调出去，保存在外存上，从而腾出更多的空闲空间。
虚拟页式存储管理¶
- 大部分虚拟存储系统都采用虚拟页式存储管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能。
概念
- 后备存储
- 后备页面
目的是提供一种错觉：内存的容量好像和内存+磁盘一样大，而且速度和内存一样快。
基本问题
- 如何发现执行的代码或访问的数据不在内存（数据结构）
- 代码或数据什么时候调入内存（调入策略）
- 当一些页要调入内存，而内存没有空闲空间时，将淘汰那些页（淘汰策略）
页表表项
每个页表项包含以下信息：逻辑页号、物理页号、驻留位、保护位、修改位、访问位。
- 驻留位：该页是否在内存
- 保护位：该页允许何种程度的访问
- 修改位：此页在内存中是否被修改过（回收时用）
- 访问位：若该页面被方位过，则设置此位（用于页面置换算法
缺页中断
在地址映射过程中，如果所要访问的逻辑页面 \(p\) 不在内存，则产生缺页中断
- 若内存中有空闲页面，分一页，设为 \(f\)
- 没有空闲页面的话，使用某种页面置换算法选择一个物理页面 \(f\) 它对应的逻辑页面为 \(q\)，看一下修改位，决定是否写回外存
- 对 \(q\) 对应的页表向机型修改，驻留位设为 0
- 把页面 \(p\) 装到 \(f\) 中，修改 \(p\) 对应的页表项的内容，驻留位设为 1，物理页面号设为 \(f\)
- 重新运行被中断的指令（这一过程中，程序计数器不变）
操作系统希望用户进程感觉不到缺页中断的发生，就如上面那个图一样
缺页中断和是一种特殊的中断，和一般的中断存在一些区别
- 在指令执行期间产生和处理缺页中断信号
- 一条指令在执行期间，可能产生多次缺页中断
- 缺页中断返回时，执行产生中断的那一条指令，而一般的中断返回时，执行下一条指令
页面置换算法¶
目标：尽可能减少页面的换进换出次数（最小化缺页中断发生的次数）
最优页面置换算法（Optimal，OPT）
基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次方位之前，还需要等待多长时间，然后从中选择等待时间最长的一，作为被置换的页面
但是事实上，操作系统根本无法知道每一个页面还需要等待多长的时间……
这个玩意的重要用处是和其它算法比较。具体来说，可以在一个模拟器上运行某个程序，并且记录下每一次的页面访问情况，有了这些数据之后，第二遍运行程序时，可以采用 OPT 算法。
最近最久未用算法（Least Recently Used， LRU）
基本思路：当一个缺页中断发生时，从内存中选择在最近一段时间内最久没有被使用过的那个页面，把它干掉
理论依据：程序的局部性原理，近似了 OPT 算法
几种可能的实现方法
- 维护一个页面链表，最近刚用的作为首节点，最久未用的作为尾结点
- 设置一个活动页面栈，当访问某个页面时，把相应的页面号压入栈顶，和链表本质一样
- 每次内存访问时，给相应页面打一个时间戳
- 使用移位寄存器实现 LRU
- 给每个存放在内存的页面设置一个移位寄存器，记录被访问频率
- 每个周期将移位寄存器的值右移一位，将对应页面的访问位的值加到该位寄存器的最左位
- 缺页中断时，找对应移位寄存器值最小的页面即可
最近最少使用算法 LFU
基本思路：当一个缺页中断发生时，选择观察期访问次数最少的那个页面，并把它干掉
实现方法：对每个页面整一个访问计数器，当每一个页面被访问的时候，该页面的访问计数器值加一，发生缺页中断时，干掉计数值最小的那个
先进先出置换算法 FIFO
基本思路：选择在内存中驻留时间最长的页面把它干掉
Warning
这个算法性能较差，调出的页面可能时经常要访问的甚至是刚刚访问过的页面
Belady 现象：一般来说，如果给一个进程更多的物理页面，那么这个进程在运行的时候，应该会出现更少的缺页中断次数。但是有时不是这样，会出现分配的物理页面数增加，而缺页中断次数反而增加的现象
出现 Belady 现象的原因：FIFO 的置换 特征和进程方位内存的动态特征相矛盾，也与置换算法的目标不一致。
置换算法的目标是找未来较少使用的页面，但是 FIFO 干掉的是过去驻留时间最长的页面
时钟页面置换算法 Clock
基本思路： FIFO + 跳过已访问的页面
- 如果一个页面被访问，硬件将其访问位设置为 1，OS 定期清零
- 把各个页面组织成环形链表，把指针指向最老的页面
- 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面。
二次机会法 EClock
基本思路： FIFO + 跳过已经读或写的页面
记：访问位（R），修改位（M）
淘汰策略为：若 \(R|M\) 为 00，立即淘汰，若是 01或10，则置为 00，若为 11， 置为01
工作集模型¶
Question
局部性原理是否成立，如果成立，如何进行定量分析
Note
工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数 \(W(t, \Delta)\) 表示
- \(t\) 当前的执行时刻
- \(\Delta\) 称为工作集窗口
- \(W(t,\Delta)\) 为当前时刻 \(t\) 之前的 \(\Delta\) 窗口中的所有逻辑页面组成的集合
- \(\vert W(t, \Delta) \vert\) 指工作集的大小，即逻辑页面数目
工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。
驻留集
驻留集是指在当前时刻，进程实际驻留在内存当中的逻辑页面集合。