存储器管理知识点总结

存储管理

逻辑地址（相对地址）：用户编程所使用的地址空间

逻辑地址从0开始编号，两种形式：

1. 一维逻辑地址（地址）
2. 二维逻辑地址（段号：段内地址）

段式程序设计

1. 把一个程序设计成多个段
   1. 代码段、数据段、堆栈段等等
2. 用户可以自己应用段覆盖技术扩充内存空间使用量
   1. 这一技术是程序设计技术，不是OS存储管理的功能

物理地址（绝对地址）：程序执行所使用的地址空间

1. 处理器执行指令时按照物理地址进行

主存储器的复用

1. 多道程序设计需要复用主存
2. 按照分区复用：
   1. 主存划分为多个固定/可变尺寸的分区
   2. 一个程序/程序段占用一个分区
3. 按照页架复用：
   1. 主存划分成多个固定大小的页架
   2. 一个程序/程序段占用多个页架

存储管理的基本模式

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

地址转换（重定位）：把逻辑地址转换成绝对地址

1. 静态重定位：在程序装入内存时进行地址转换
   1. 由装入程序执行，早期小型OS使用
2. 动态重定位：在CPU执行程序时进行地址转换
   1. 从效率出发，依赖硬件地址转换机构

主存储器空间的分配与去配

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

主存储器空间的共享

1. 多个进程共享主存储器资源：多道程序设计技术使若干个程序同时进入主存储器，各自占用一定数量的存储空间，共同使用一个主存储器
2. 多个进程共享主存储器的某些区域：若干个协作进程有共同的主存程序块或者主存数据块

存储保护

1. 为避免主存中的多个进程相互干扰，必须对主存中的程序和数据进行保护
   1. 私有主存区中的信息：可读可写
   2. 公共区中的共享信息：根据授权
   3. 非本进程信息：不可读写
2. 这一功能需要软硬件协同完成
   1. CPU检查是否允许访问，不允许则产生地址保护异常，由OS进行相应处理

主存储器空间的扩充

1. 存储扩充：把磁盘作为主存扩充，只把部分进程或进程的部分内容装入内存
   1. 对换技术：把部分不运行的进程调出
   2. 虚拟技术：只调入进程的部分内容
2. 这一工作需要软硬件协作完成
   1. 对换进程决定对换，硬件机构调入
   2. CPU处理到不在主存的地址，发出虚拟地址异常，OS将其调入，重执指令

虚拟存储器思想的提出

主存容量限制带来诸多不便

1. 用户编写程序必须考虑主存容量限制
2. 多道程序设计的道数受到限制

用户编程行为分析

1. 全面考虑各种情况，执行时有互斥性
2. 顺序性和循环性等空间局部性行为
3. 某一阶段执行的时间局部性行为

考虑部分调入进程内容

基本思想

1. 存储管理把进程全部信息放在辅存中，执行时先将其中一部分装入主存，以后根据执行行为随用随调入
2. 如主存中没有足够的空闲空间，存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去

实现思路

1. 需要建立与自动管理两个地址空间
   1. （辅存）虚拟地址空间：容纳进程装入
   2. （主存）实际地址空间：承载进程执行
2. 对于用户，计算机系统具有一个容量大得多的主存空间，即虚拟存储器
3. 虚拟存储器是一种地址空间扩展技术，通常意义上对用户编程是透明的，除非用户需要进行高性能的程序设计

存储管理涉及的存储对象

1. 存储管理是OS管理主存储器的软件部分
2. 为获得更好的处理性能，部分主存程序与数据（特别是关键性能数据）被调入Cache，存储管理需要对其进行管理，甚至包括对联想存储器的管理
3. 为获得更大的虚拟地址空间，存储管理需要对存放在硬盘、固态硬盘、甚至网络硬盘上的虚拟存储器文件进行管理

高速缓存存储器（Cache）

1. Cache是介于CPU和主存储器间的高速小容量存储器，由静态存储芯片SRAM组成，容量较小但比主存DRAM技术更加昂贵而快速，接近于CPU的速度
2. CPU往往需要重复读取同样的数据库，Cache的引入与缓存容量的增大，可以大幅提升CPU内部读取数据的命中率，从而提高系统性能
3. 构成
   1. 高速存储器
   2. 联想存储器：根据内容进行寻址的存储器
   3. 地址转换部件：通过联想存储器建立目录表以实现快速地址转换。命中时直接访问Cache；未命中时从内存读取放入Cache
   4. 替换部件：在缓存已满时按一定策略进行数据块替换，并修改地址转换部件
4. 分级：由于CPU芯片面积和成本，Cache很小。根据成本控制，划分L1，L2，L3三级
   1. L1 Cache：分为数据缓存和指令缓存；内置；成本最高，对CPU的性能影响最大；通常在32KB-256KB之间
   2. L2 Cache：分内置和外置两种，后者性能低一些；通常在512KB-8MB之间
   3. L3 Cache：多为外置，在游戏和服务器领域有效；但对很多应用来说，总线改善比设置L3更加有利于提升系统性能

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

1. 主存区域划分为系统区和用户区
2. 设置一个栅栏寄存器界分两个区域，硬件用它在执行时进行存储保护
3. 一般采用静态重定位进行地址转换
   1. 静态重定位：在装入一个作业时，把该作业中程序的指令地址和数据地址全部转换成绝对地址
4. 硬件实现代价低
5. 适用于单用户单任务操作系统，如DOS

可变分区存储管理：按照进程的内存需求来动态划分

基本思想

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

创建一个进程时，根据进程所需主存量查看主存中是否有足够的空闲时间

1. 若有，则按需要量分割一个分区
2. 若无，则令该进程等待主存资源

由于分区大小按照进程实际需要量来确定，因此分区个数是随机变化的

内存分配

1. 最先适应分配算法
2. 邻近适应分配算法
3. 最优适应分配算法
4. 最坏适应分配算法

内存零头

1. 固定分区方式会产生内存内零头，可变分区方式也会随着进程的内存分配产生一些小的不可用的内存分区，称为内存外零头
2. 最优适配算法最容易产生外零头
3. 任何适配算法都不能避免产生外零头

移动技术

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

主存分区表

已分配区情况表

起址	长度	标志
4K	6K	J1
46K	6K	J2
		空
		空
…	…	…

未分配区情况表

起址	长度	标志
10K	36K	未分配
52K	76K	未分配
		空
		空
…	…	…

固定分区存储管理

1. 支持多个分区

2. 分区数量固定

3. 分区大小固定

4. 可用静态重定位

5. 硬件实现代价低

6. 早期OS采用

7. 主存分配表

   分区号	起始地址	长度	占用标志
   1	4K	8K	0
   2	12K	16K	Job1
   3	28K	16K	0
   4	44K	24K	0
   5	68K	24K	Job2
   6	92K	36K	0

页式存储管理

基本原理

1. 分页存储器将主存划分成多个大小相等的页架
2. 受页架尺寸限制，程序的逻辑地址也自然分成页
3. 不同的页可以放在不同页架中，不需要连续
4. 页表用于维系进程的主存完整性

地址

1. 页式存储管理的逻辑地址由两部分组成：页号和单元号
2. 物理地址：页架号和单元号
3. 地址转换可以通过查页表完成

内存分配/去配

1. 用一张位示图来记录主存分配情况
2. 建立进程页表维护主存逻辑完整性

页的共享

1. 页式存储管理能够实现多个进程共享程序和数据
2. 数据共享：不同进程可以使用不同页号共享数据页
3. 程序共享：不同进程必须使用相同页号共享代码页
   1. 共享代码页中的（JMP<页内地址>）指令，使用不同页号是做不到

地址转换代价

1. 页表放在主存：每次地址转换必须访问两次主存
   1. 按页号读出页表中的相应页架号
   2. 按计算出来的绝对地址进行读写
2. 存在问题：降低了存取速度
3. 解决办法：利用Cache存放部分页表

快表：存放在高速存储器中的页表部分

1. 为提供地址转换速度，设置一个专用的高速存储器，用来存放页表的一部分
2. 快表表项：页号，页架号
3. 这种高速存储器是联想存储器，即按照内容寻址，而非按照地址访问·

引入快表后的地址转换代价

1. 假设主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率是90%，平均地址转换代价为（200+40）*90%+（200+200）*10%=256毫微秒
2. 比两次访问主存时间（400毫微秒）下降了36%（（400-256）/400）

基于快表的地址转换流程

1. 按逻辑地址中的页号查快表
2. 若该页已在快表中，则由页架号和单元号形成绝对地址
3. 若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中
4. 当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

多道程序环境下的进程表

1. 进程表中登记了每个进程的页表

2. 进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器

3. 页表控制寄存器

   用户作业名	页表地址	页表长度
   AB	0010	4
   CD	0014	3
   EF	0017	7

页式虚拟存储管理

定义

1. 把进程全部装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存的页，同时进行必要的页面调出
2. 现代OS的主流存储管理技术
3. 首次只把进程第一页信息装入内存，称为请求页式存储管理

页式虚拟存储管理的页表

标志位	主存块号	辅助存储器地址

扩充页表项，指出：

1. 每页的虚拟地址、实际地址
2. 主存驻留地址、写回标志、保护标志、引用标志、可移动标志

实现

1. CPU处理地址
   1. 若页驻留，则获得块号形成绝对地址
   2. 若页不在内存，则CPU发出缺页中断
2. OS处理缺页中断
   1. 若有空闲页架，则根据辅存地址调入页，更新页表与快表等
   2. 若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表

页面调度

1. 当主存空间已满而又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去
2. 选择淘汰页的工作称为页面调度
3. 选择淘汰页的算法称为页面调度算法
4. 页面调度算法设计不当，会出现（刚被淘汰的页面立即又要调入，并如此反复）
5. 这种现象称为抖动或颠簸
6. 先进先出FIFO页面调度算法
   1. 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）
   2. 模拟的是程序执行的顺序性，有一定合理性
7. 最近最少用LRU页面调度算法
   1. 淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到
      1. OPT页面调度算法：
         1. 当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页
         2. 该算法由Belady提出，称为Belady算法，又称最佳算法（OPT，Optimal page replacement）
         3. OPT只可模拟，不可实现
   2. 模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性
   3. 严格实现的代价大（需要维持特殊队列）
   4. 模拟实现：
      1. 每页建一个引用标志，供硬件使用
      2. 设置一个时间间隔中断：中断时页引用标志置0
      3. 地址转换时，页引用标志置1
      4. 淘汰页面时，从页引用标志为0z的页中间随机选择
      5. 时间间隔多长是个难点
8. 最不常用LFU页面调度算法
   1. 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
   2. 基于时间间隔中断，并给每一页设置一个计数器
   3. 时间间隔中断发生后，所有计数器清0
   4. 每访问页1次就给计数器加1
   5. 选择计数值最小的页面淘汰
9. 时钟CLOCK页面调度算法
   1. 采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
   2. 队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
   3. 使用页引用标志位
   4. 工作流程：
      1. 页面调入主存时，其引用标志位置1
      2. 访问主存页面时，其引用标志位置1
      3. 淘汰页面时，从指针当前指向的页面开始扫描循环队列
         1. 把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
         2. 把所遇到的引用标志位是0的页面淘汰，指针推进一步

缺页中断率

1. 假定进程P共n页，系统分配页架数m个
2. P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F
3. 缺页中断率定义为：f=F/A
4. 缺页中断率是衡量存储管理性能和用户编程水平的重要依据
5. 影响因素
   1. 分配给进程的页架数：可用页架数越多，则缺页中断率就越低
   2. 页面的大小：页面尺寸越大，则缺页中断率就越低
   3. 用户的程序编制方法：在大数据量情况下，对缺页中断率也有很大影响

   // 程序将数组置为“0”，假定仅分得一个主存页架，页面尺寸为128个字，数组元素按行存放，开始时第一页在主存
   int A[128][128];
   for (int j=0;j<128;j++)for (int i=0;i<128;i++)A[i][j]=0;
   // 每执行一次赋值就要产生一次缺页中断，共产生（128x128-1）次缺页中断int A[128][128];
   for (int i=0;i<128;i++)for (int j=0;j<128;j++)A[i][j]=0;
   // 共产生（128-1）次缺页中断
   

反置页表

提出：

1. 页面及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用
2. 为页式存储管理设置专门硬件机构
3. 内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面
4. 反置页表IPT：MMU用的数据结构

基本设计思想

1. 针对内存中的每个页架建立一个页表，按照块号排序
2. 表项包含：正在访问改页框的进程标识、页号及特征位和哈希链指针等
3. 用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换

页表项

1. 页号：虚拟地址页号
2. 进程标志符：使用该页的进程号（页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页）
3. 标志位：有效、引用、修改、保护的锁定等标志信息
4. 链指针：哈希链

基于反置页表的地址转换过程

1. MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT的一个表目
2. MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页架号，通过拼接位移便可生成物理地址
3. 若遍历整个反置页表中未能找到匹配页表项，说明该页不在内存，产生缺页中断，请求操作系统调入

段式存储管理

段式程序设计

1. 每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的
2. 分段存储器的逻辑地址由两部分组成，段号、单元号

基本思想

1. 段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
2. 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段、附加段），供地址转换使用
3. 存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位

段的共享

1. 通过不同进程段表中的项指向同一个段基址来实现
2. 对共享段的信息必须进行保护，如规定只能独处不能写入，不满足保护条件则产生保护中断

段式虚拟存储管理的基本思想

1. 把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把它们动态装入
2. 段式虚拟存储管理中段的调进调出是由OS自动实现的，对用户透明
3. 与段覆盖技术不同，它是用户控制的主存扩充技术，OS不感知

段表扩充

1. 特征位：00（不在内存）01（在内存）11（共享段）

2. 存取权限：00（可执行）01（可读）11（可写）

3. 扩充位：0（固定长）1（可扩充）

4. 标志位：00（未修改）01（已修改）11（不可移动）

   段号	特征	存取权限	扩充位	标志位	主存始址

段页式存储管理

1. 基本思想
   1. 段式存储管理可以基于页式存储管理实现
   2. 每一段不必占据连续的存储空间，可存放在不连续的主存页架中
   3. 能够扩充为段页式虚拟存储管理
   4. 装入部分段，或者装入段中部分页面