存储管理 - ICDE

3.1 存储管理基础

3.1.1 存储管理主要模式

==逻辑地址==：相对地址，即用户程序所使用的地址空间。从0开始编号，有两种形式：一维逻辑地址（地址）；二维逻辑地址（段号：段内地址）

段式程序设计：把一个程序设计成多个段：代码段、数据端、堆栈段等

用户可以自己应用 段覆盖技术 扩充内存空间使用量

==物理地址==：绝对地址，即程序执行所使用的地址空间，处理器执行指令时按照物理地址进行。

主存储器

多道程序设计需要复用主存

按照分区复用：一个程序/程序段占用一个分区
按照页架复用：一个程序/程序段占用多个页架

存储器管理的基本模式

单连续存储管理：一维逻辑地址空间的程序占用一个主存固定分区或可变分区
段式存储管理：段式二维逻辑地址空间的程序占用多个主存可变分区
页式存储管理：一维逻辑地址空间的程序占用多个主存页架区
段页式存储管理：段式二维逻辑地址空间的程序占用多个主存页架区

3.1.2 存储管理的功能

地址转换

地址转换：又称重定位，即把逻辑地址转换为绝对地址
静态重定位：==程序装入内存时==进行地址转换
动态重定位：==在CPU执行程序时==进行地址转换

分配与去配

分配：进程装入主存时，存储管理软件进行具体的主存分配操作，并设置一个表格记录主存空间的分配情况
去配：当某个进程撤离或者主动归还主存资源时，存储管理软件要收回它所占用的全部或者部分存储空间，调整主存分配表信息

主存储器空间的共享

多道程序设计技术使若干个程序同时进入主存储器，各自占用一定数量的存储空间，共同使用一个主存储器，若干个协作进程有共同的主存程序块或者主存数据块

存储保护问题，软硬件协同完成

私有主存区中的信息：可读可写

公共区中的共享信息：看授权

非本进程信息：不可读写

主存储器空间的扩充

存储扩充：磁盘作为主存扩充，只把部分进程或者进程的部分内容装入内存。
- 对换技术：把部分不运行的进程调出
- 虚拟技术：只调入进程的部分内容

3.1.3 虚拟存储器的概念

虚拟存储器

程序局部性原理：指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中

1、原因：

主存容量存在限制，使得用户编写程序受限，多道程序设计道数受限
存在空间局部性和时间局部性，使得某一阶段只需要部分进程内容

2、基本思想：

进程信息全部放在辅存，执行时==随用随调入==
把主存中暂时不用的信息调到辅存上去

3、实现思路：

建立两个地址空间
- （辅存）虚拟地址空间：容纳进程装入
- （主存）实际地址空间：承载进程执行
虚拟存储器是一种地址空间扩展技术，对用户透明，用户编程时以为可以操纵整个内存

4、覆盖与交换

覆盖：按照程序逻辑结构让那些不需要同时执行的程序段共享同一块内存区，使得后面的程序段可以调入内存覆盖前面的程序段。
交换：把处于等待状态的进程换出内存。

3.1.4 存储管理的硬件支撑

存储器的组织层次

存储管理涉及的存储对象：

主存储器
Cache
为了获得更大的虚拟地址空间，存储管理需要对存放在硬盘、固态硬盘、甚至网络硬盘上的虚拟存储器文件进行管理

Cache

1、介于CPU和主存之间的高速缓冲存储器，SRAM组成，接近CPU速度。（主存DRAM）

2、CPU往往需要重复读取同样的数据块，时间局部性和空间局部性

3、组成：高速存储器、联想存储器、地址转换部件、替换逻辑

联想存储器：根据内容进行寻址的存储器。
地址转换部件：通过联想存储器建立目录表以实现快速地址转换。命中时直接访问Cache，未命中时从内存读取放入Cache。
替换部件：在Cache已满时按一定策略进行数据块替换，并修改地址转换部件。

4、组织：L1、L2、L3三级

L1 Cache：数据缓存和指令缓存；内置；32KB-256KB
L2 Cache：内置和外置；512KB—8MB
L3 Cache：多为外置

伙伴系统

伙伴系统，又称buddy算法，是一种固定分区和可变分区折中的主存管理算法
任何尺寸为2ⁱ的空闲块都可以被分为两个尺寸为2^i-1的空闲块，这两个空闲块称作伙伴
SunOS操作系统中首创的基于伙伴系统的slab分配器

分段和分页

分段

分段是信息的物理单位，由源程序的逻辑结构所决定，用户可见
段长可以根据用户需要来规定，段起始地址可以从任何主存地址开始
分段方式下，源程序（段号，段内地址）经连结装配后地址仍保持二维结构
段是不定长连续的

分页

分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见
页长由系统决定，页面只能以页大小的整数倍地址开始
分页方式中，源程序（页号，页内地址）经连结装配后地址变成了一维结构

3.2 单连续分区存储管理

3.2.1 单连续分区存储管理

每个进程占用一个物理上完全连续的存储空间（区域）

单用户连续分区管理存储

主存区域划分为系统区和用户区
设置一个栅栏寄存器界分两个区域，硬件用它在执行时进行地址转换
一般采用静态重定位进行地址转换
硬件实现代价低
适用于单用户单任务操作系统（DOS）

固定分区存储管理

支持多个分区
分区数量固定、大小固定
可用静态重定位
硬件实现代价低
早期OS采用

主存分配：采用主存分配表记录主存的分配信息

地址转换

可变分区存储管理

固定分区存储管理不够灵活，既不适应大尺寸程序，又存在内存零头，有浪费
可变分区存储管理：允许按照进程实际内存需求动态划分分区，并允许分区个数可变

3.2.2 可变分区存储管理

主存分配表：已分配区表和未分配区表，采用链表结构

分配算法：

最先适配分配算法：空闲分区以地址递增的次序连接，分配内存时顺序查找，找到大小能满足要求的第一个空闲分区
邻近适配分配算法：循环首次适应算法，由首次适应算法演变而成，不同的是，分配内存时从上次查找结束的位置开始继续查找
最优适配分配算法：空闲分区按容量递增的方式形成分区链，找到第一个满足要求的空闲分区
最坏适配分配算法：空闲分区以容量递减的次序连接，找到第一个能满足要求的空闲分区

地址转换

内存零头

固定分区方式会产生内存内零头
可变分区方式会产生内存外零头
分段方式会产生内存外零头
分页方式会产生内存内零头
最优适配算法最容易产生外零头，外零头是不可避免的

移动技术（程序浮动技术）

移动分区以解决内存外零头
需要动态重定位的支撑

3.3 页式存储管理

3.3.1 页式存储管理的基本原理

分页存储器将主存划分成多个大小相等的==页架==
受页架尺寸限制，程序的逻辑地址也自然分成==页==
不同的页可以放在不同的页架中，不需要连续
页表用于维系进程的主存完整性
可用一张位示图来记录主存分配情况

地址转换

页的共享

页式存储管理能够实现多个进程共享程序和数据
数据共享：不同进程可以使用不同页号共享数据页
代码共享：不同进程必须使用相同页号共享代码页（JMP指令在不同页号是做不到的）

3.3.2 页式存储管理的地址转换

转换代价

每次地址转换需要访问两次主存
- 读取页表
- 读写数据
降低存取速度
利用Cache存放部分页表

快表

这种高速存储器是联想存储器，即按内容寻址，而非按照地址寻址

3.3.3 页式虚拟存储管理

把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存中的页，同时进行必要的页面调出。

现代OS的主流存储管理技术

首次只把进程的第一页信息装入主存，称为==请求页式存储管理==

需要扩充页表

原本是：只存放主存块号
现在需要：标志位（主存驻留标志，写回标志，保护标志、引用标志、可移动标志）+主存块号+辅助存储器地址

3.3.4 页面调度

当主存空间已满但是有需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去

页面调度：选择淘汰页的工作
页面调度算法：选择淘汰页的算法
如果页面调度算法设计不当，会出现==抖动/颠簸==现象，即刚被淘汰的页面立即又要调入，如此反复

缺页中断率

定义：不成功访问的次数 / 访问的总次数
影响缺页中断率的因素
- 分配给进程的页架数：可用页架数越多，缺页中断率就越低
- 页面的大小：尺寸越大，缺页中断率就越低
- 用户的程序编制方法
经典例子

调度算法

OPT页面调度算法：理想的调度算法，当要调入新页面时，首先淘汰以后不再访问的页，然后选择距离现在最长时间后再访问的页
- Belady算法，又称最佳算法
- OPT只可模拟，不可实现
先进先出FIFO页面调度算法
- 总是淘汰最先调入主存的那一页（主存驻留时间最长的那一页）
- 思想：模拟的是程序执行的顺序性
- Belady异常：增加可用物理页框的数量会导致更多的缺页异常。
最近最少使用LRU页面调度算法
- 淘汰最近一段时间较久未被访问的那一页
- 思想：那些刚刚被使用过的页面，可能马上还要被用到
- 需要维护特殊队列
- 时间间隔中断，中断时页引用标志位置0
- 地址转换时，页引用标志位置1
- 淘汰页面时，从页引用标志位为0的页中随机淘汰
最不常用LFU页面调度算法
- 淘汰最近一段时间内访问次数最少的页面
- 基于时间间隔中断，给每一页设置一个计数器
- 时间间隔中断发生后，所有计数器清0
- 每访问页1次就给计数器加1
- 选择计数值最小的页面淘汰
时钟CLOCK页面调度算法
- 采用循环队列机制构造页面队列
- 工作流程
  - 页面调入主存和访问主存页面时，引用标志位置1
  - 淘汰页面时，从指针当前指向的页面开始扫描循环队列
    - 遇到引用标志位是1的页面将引用标志位清0
    - 遇到引用标志位是0的页面淘汰，指针推进一步，算法停止
    - 如果引用标志位全部是1，指针会环绕整个循环队列一圈，把碰到的引用标志位清0，指针停在起始位置（开始遍历的位置），并淘汰该页，然后指针向前推进一步
局部最佳页面替换算法（MIN）
- 如果该页面在时间间隔\((t, t+\tau)\)内未被引用，那么就移除；否则该页被保留在进程驻留集中
工作集置换算法（WS）
- ==进程工作集==：在某一段时间间隔内进程运行所需访问的页面集合
  - \(W(t, \Delta)\)表示在时刻\(t-\Delta\)到时刻\(t\)之间所访问的页面集合，进程在时刻\(t\)的工作集
- 实现思想：不向前查看页面引用串，而是基于程序局部性原理向后看
- 定期地从进程驻留集中删去那些不在工作集中的页面。如果页面在时间间隔\((t-\Delta, t)\)内未被引用，就要移除。