# 四、存储管理
# 1. 内存分配
# 1.1 单一连续分配
内存分为系统区和用户区。系统区给操作系统使用，用户区给一道用户作业使用。
# 特点：
- 管理简单，只需很少的软硬件支持。
- 适用于单用户、单任务的操作系统。
缺点：
- 各类资源的利用率不高。
# 1.2 固定分区分配
内存空间被划分为若干固定大小的区域，每个分区只提供给一个程序使用，互不干扰。
# 1.3 动态分区分配
根据作业大小动态地建立分区，并使分区的大小正好适应作业的需要。
# 1.3.1 数据结构
# 空闲分区表
# 空闲分区链
# 1.3.2 分区算法
# [1] 首次适应算法 FF
- 要求空闲分区按地址递增的次序排列。
- 在进行内存分配时，从空闲分区表（或空闲分区链）首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。
- 然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表（或空闲分区链）中。
- 优先利用内存低地址端，高地址端有大空闲区。但低地址端有许多小空闲分区时会增加查找开销。
# [2] 循环首次适应算法
- 从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足其大小要求的空闲分区为止。
- 然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表（或空闲分区链）中。
- 使存储空间的利用更加均衡，但会使系统缺乏大的空闲分区。
# [3] 最佳适应算法 BF
- 要求空闲分区按容量大小递增的次序排列。
- 从空闲分区表（或空闲分区链）首开始顺序查找，***直到找到第一个能满足其大小要求***的空闲分区为止。
- 能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。
- 保留了大的空闲区。但分割后的剩余空闲区很小。
# [4] 最坏适应算法
- 要求空闲分区按容量大小递减的次序排列。
- 先检查空闲分区表（或空闲分区链）中的第一个空闲分区
- 若第一个空闲分区小于作业要求的大小，则分配失败；
- 否则从该空闲分区中划出与作业大小相等的一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表（或空闲分区链）中。
- 剩下的空闲区比较大，但当大作业到来时，其存储空间的申请往往得不到满足。
# 1.4 可重定位分区分配
# 拼接技术
通过移动把多个分散的小分区拼接成一个大分区，也可称为紧缩(compaction)或紧凑。
- 要耗费大量处理机时间。
# 可重定位分区分配技术
可重定位分区分配算法与动态分区分配算法基本相同，差别仅在于：在这种分配算法中增加了拼接功能。
# 2. 内存回收
[1] 回收分区r上面邻接一个空闲分区
[2] 回收分区r下面邻接一个空闲分区
[3] 回收分区r上面、下面各邻接一个空闲分区
[4] 回收分区r不与任何空闲分区相邻
- 为回收区单独建立一个新表项，填写分区大小及起始地址等信息，并将其加入到空闲分区表(或空闲分区链)中的适当位置。
# 3. 分页存储管理
# 3.1 思想
连续的逻辑地址信息离散地存入到物理的内存当中 —— 映射
# 3.2 解析
逻辑地址A，页面大小为L，则：
- 页号 P = (int) A/L
- 页内偏移 W = A%L
如：A = 3000， L = 2K
则：P = 1， W = 952
# 3.3 页表及存储块表
# 3.4 基本地址变换机构
# 页表寄存器
页表寄存器用来存放页表在内存中的起始地址和页表的长度。
程序未执行时，页表的起始地址和长度存放在PCB中；
当程序执行时，才将页表起始地址和长度存放在页表寄存器中。
# 地址变换过程
# 3.5 具有快表的地址变换机构
# 3.6 多级页表和反置页表
# 为了什么
页表太大，连续空间存放不现实。采用多级页表和反置页表：
- 将页表分成若干较小的片段，离散地存放在内存中；
- 只将当前需要的部分页表项存放在内存，其余存放在磁盘上，需要时再动态调入。
# 多级页表
[1] 页表结构
[2] 地址变换
# 反向页表
- 既要内存又要外存，慢。
# 4. 分段存储管理
将进程逻辑空间划分成若干段（非等分），段的长度由连续逻辑的长度决定。
# 分段与分页的区别
- 信息单位
- 页是信息的物理单位，是为了减少内存碎片及提高内存利用率，是系统管理的需要。
- 段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地满足用户的需要。
- 大小/长度
- 页的大小固定且由系统决定，由硬件把逻辑地址划分为页号和页内地址两部分。
- 段的长度不固定且由用户所编写的程序决定，通常由编译系统在对源程序进行编译时根据信息的性质来划分。
- 地址空间维数
- 分页系统中作业的地址空间是一维的
- 分段系统中作业的地址空间是二维的。
# 5. 段页式存储管理
分页可以有效提高内存利用率，分段可以更好满足用户需求，两者结合，形成段页式存储管理。
# 5.1 思想
先段后页
- 地址空间首先被分成若干个逻辑分段；
- 再将每一段分成若干个大小固定的页面。
- 将主存空间分成若干个和页面大小相同的物理块，对主存的分配以物理块为单位。
# 5.2 结构
# 5.3 地址变换
# 6. 虚拟内存
# 6.1 局部性原理
在程序装入时，不必将其全部读入内存，而只需将当前执行需要的部分放入内容，而将其余部分放在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的信息调入内存，然后继续执行程序。
# 6.2 特性
- 离散性
- 不连续内容分配
- 多次性
- 一个作业分多次装入内存
- 对换性
- 允许运行中换进换出
- 虚拟性
- 逻辑上扩充内存
# 6.3 物质基础
- 有相当数量的外存，足矣存放多个作业；
- 有一定容量的内存；
- 地址变换机构，以动态实现逻辑地址到物理地址的变换。
# 6.4 实现方案
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
# 6.5 请求分页存储管理
# 6.5.1 实现思想
请求分页存储管理方法是在分页存储管理的基础上增加了请求调页和页面置换功能。
实现思想：在作业运行之前只装入当前需要的一部分页面便启动作业运行。
在作业运行过程中，若发现所要访问的页面不在内存，便由硬件产生缺页中断，请求OS将缺页调入内存。
若内存无空闲存储空间，则根据某种置换算法淘汰已在内存的某个页面，以腾出内存空间装入缺页。
# 6.5.2 支持机构
- 页表
- 缺页中断机构
- 地址变换机构
- 请求调页和页面置换软件
# [页表]
- 页号和物理块号：
- 定义同分页存储管理；
- 状态位：
- 表示页面是否在内存中；
- 访问字段：
- 记录页面在一段时间内被访问的次数；
- 或最近已有多长时间未被访问；
- 该字段供置换算法在选择换出页面时参考；
- 修改位：
- 表示页面调入内存后是否被修改过，若被修改，则需要重新写到外存上；
- 外存地址：
- 指出页面在外存是的存放地址；
- 供调入页面时使用。
# [缺页中断和地址变换]
# 6.5.3 页面分配和置换策略
进程运行所需的最少物理块数
- 单地址指令且采用直接寻址
- 至少两块
- 一个存放指令
- 一个存放数据
- 至少两块
- 间接寻址
- 至少三块
页面分配策略
- 固定分配
- 分配给进程的主存块数是固定的，且在进程创建时确定块数；
- 可变分配
- 允许分配给进程的主存块数随进程的执行而改变；
页面置换策略
- 全局置换
- 允许一个进程从全部内存物理块集合中选择淘汰对象；
- 局部置换
- 规定每个进程只能从分配给它的物理块中淘汰对象；
# [1] 固定分配局部置换
基于某种原则为每个进程分配固定数量的物理块，当进程运行中出现缺页时，只能从自己的页面中选择一页换出，然后再调入缺页。
实现这种策略的困难在于：难以确定应为每个进程分配多少个物理块。
# [2] 可变分配全局置换
先为系统中的每个进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程；当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可以是系统中任何一个进程的页面。
这是一种容易实现的页面分配和置换策略，目前已用于若干操作系统中。
# [3] 可变分配局部置换
根据某种原则为每个进程分配一定数量的物理块，当进程发生缺页中断时，只允许从该进程的页面中选出一页换出。如果某进程的缺页率较高，则系统再为该进程分配若干物理块；反之若某进程的缺页率特别低，则系统可适当减少分配给该进程的物理块数。
该算法比较复杂，但性能较好。
# 6.6.4 物理块的分配算法
# [1] 平均分配算法
# [2] 按比例分配算法
- 看进程大小
# [3] 按优先级分配算法
# 6.6.5 页面置换算法
# [最佳置换算法 OPT]
从内存中选择将来最长时间不会使用的页面予以淘汰。
因页面访问的未来顺序很难精确预测，该算法具有理论意义，可以用来评价其他算法的优劣。
# [先进先出置换算法 FIFO]
选择调入主存时间最长的页面予以淘汰。
Belady 现象
在某些情况下，分配给进程的页面数增多，缺页次数反而增加。
原因：
FIFO 算法的置换特征与进程访问内存的动态特征的矛盾的，即被置换的页面并不是不会访问的。
# [最近最久未使用置换算法 LRU]
选择最近一段时间内最长时间没有被访问过的页面予以淘汰。
为此，应赋予每个页面一个访问字段，用于记录页面自上次访问以来所经历的时间
特点:
- LRU 的性能接近于最佳算法，但实现起来还是很困难。
- 因为我们多设置了一个访问字段，并且要经常更新它，导致开销很大。
- 因此，实际中往往采用 LRU 的近似算法。
2 种方法实现 LRU 算法
# ① 链表法
用一个单链表保存当前进程所访问的各页面号，刚使用过的页面放表尾，则表头一定是最近最久未使用的页面。
当分配给进程的物理块未用完时，则将进程装入内存的页面按先后顺序构成一个链表 当进程访问的页面在内存时，将页面从链表中移出放到表尾 当进程访问的页面不在内存时，则发生缺页中断，将表头页面置换
# ② 计数器法
为每个页面配置一个计数器（ Counter ），其初值为0。当进程访问某页时，将计数器的最高位置1，定时器每隔一定时间将计数器右移1位，则数值最小的页是最近最久未使用的页面。
利用 8 位寄存器记录 8 个页面访问情况如下：
从上表可以看出页面 7 是最近最久未使用的页面。
# [第二次机会算法]
该算计将 FIFO 算法与页表中的”引用位“结合起来使用。
当选择页面置换时，先检查 FIFO 页面队列中的队首页面（这是最早进入主存的页面）
- 如果它的引用位为0，那么这个页面既老又没用，淘汰；
- 如果它的引用位为1，说明老当益壮，将引用位改为0并扔到队尾，看成是一个新调入的页面，并将它的装入时间改成当前时间，然后选择下一个 FIFO 页面。
# [简单时钟算法]
△ 上述算法的出队入队很浪费，所以这个算法弄成循环列表，不需要出入队，就是移动指针而已。注意：简单时钟算法在遇到1的时候，不需要把它移动到最后。
将页面排成一个循环队列，类似于时钟表面，并使用一个置换指针。
当发生缺页时，检查指针指向的页面，
- 若其访问位为0则淘汰该页，
- 否则将该页的访问位清0，指针前移并重复上述过程，直到找到访问位为0的淘汰页为止。
最后指针停留在被置换页的下一页上。
如果不需要置换，则指针位置不变。
# [改进的时钟算法]
△ 简单时钟算法中淘汰的时候只考虑了页面的访问情况，没有考虑被淘汰页面的修改情况，因为淘汰一个修改过的页面还需要写磁盘，开销很大。所以改变的时钟算法就顾及到这两个方面了。
设 R 为页面的访问位，U 为页面的修改位，则有四种情况：
- 1类(R=0,U=0)：未被访问又未被修改
- 2类(R=0,U=1)：未被访问但已被修改
- 3类(R=1,U=0)：已被访问但未被修改
- 4类(R=1,U=1)：已被访问且已被修改
- 从指针当前位置开始扫描循环队列，寻找R=0,U=0的页面，将满足条件的第一个页面作为淘汰页。
- 若第1步失败，则开始第2轮扫描，寻找R=0,U=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位R置0。
- 若第2步失败，则将指针返回到开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。
特点：减少了磁盘I/O次数，但算法本身开销增加。
# [最不常用算法]
选择到当前时间为止访问次数最少的页淘汰。
该算法要求为每页设置一个访问计数器，每当页被访问时，该页的访问计数器加1。
发生缺页中断时，淘汰计数值最小的页面，并将所有计数器清零。
# [页面缓冲算法]
页面缓冲置换算法采用FIFO选择被置换页面，选择出的页面不是立即换出，而是放入两个链表之一。
- 空闲链：页面未修改则放入空闲链末尾
- 修改链：页面已修改则放入修改链末尾
当需要访问一个页面时，若该页在上述两个队列中，则只要将该页面从队列中移出，否则用空闲链的第一个物理块装入该页。当修改链中的页面数达到一定值时，再将它们一次写回磁盘，然后将它们加入空闲页面链表中。
# 7. Linux 存储管理
# 7.1 Buddy 内存管理算法
# 7.2 Linux 交换空间
# 概念
- 交换空间 Swap 是磁盘的一个分区
- Linux 物理内存满时，会把一些内存交换至 Swap 空间
- Swap 空间是初始化系统时配置的
# 查看交换空间 —— top
# 作用
- 冷启动内存依赖
- 将不经常使用的内存数据存到 Swap 空间中。
- 系统睡眠依赖
- 睡眠的时候将内存信息存到 Swap 中，启动的时候从 Swap 中恢复，速度更快。
- 大进程空间依赖
# 交换空间与虚拟内存
