内存管理

存储器层次

L0 少量快速CPU寄存器
L1-L2一个或多个小型或中型的基于SRAM的高速缓存存储器
L3 大的基于DRAM的主存
L4 慢速但是容量很大的本地磁盘
L5 原创服务器上的磁盘

局部性原理

在一段较短的时间内, 程序的执行仅局限于某个部分, 相应的他所访问的存储空间也局限于某个区域

时间的局部性
- 某条指令一旦被执行, 则不久后该指令可能被再次执行
- 某个数据结构被访问, 那么不久后该数据结构可能被再次访问
空间的局部性
- 一旦程序访问了某个单元, 在不久后, 其附近的单元也将被访问

程序的链接和装入

链接

静态链接
- 任务
  - 对逻辑地址进行修改
  - 变换外部调用符号
- 发生在程序运行前
动态链接
- 将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行

装入

绝对装入方式
可重定位装入方式 (静态重定位)
- 对目标程序中的指令和数据地址的 修改过程 称为重定位
动态运行时装入(动态重定位)
- 需要重定位寄存器

连续内存分配

单一连续分配

内存分为用户区和系统区, 用户区供用户使用, 系统区仅供操作系统使用

适用系统: 单任务, 单用户
理由
- 节省硬件
- 用户独占机器, 对系统的破坏只会是用户自己造成的, 后果不严重, 且系统易于重装

固定分区分配

固定分区将用户空间划分成若干个固定大小的区域, 在每个用户区可以装入一道用户程序

分区方法: 分区大小相等, 分区大小不等
数据结构
- 分区编号
- 分区大小
- 分区起始地址
- 分区状态

动态分区分配

系统初始只有一个大空闲区, 当进程请求空间时, 由系统根据进程的需要的空间大小划分出一片空闲区分配给用户

动态分区分配数据结构

空闲分区表
- 分区编号
- 分区大小
- 分区起始位置
空闲分区链
- 指向前一个节点的指针和后一个节点的指针
- 分区大小
- 分区起始位置

动态分区分配的流程

内存分配
- 空闲分区表
- 空闲分区链
内存回收

连续内存动态分配算法

首次适应法
- 要求空闲分区链必须以地址递增的顺序链接
- 从链首顺序查找, 直到找到第一个能够满足进程大小要求的空闲分区
- 然后按照进程请求内存的大小, 从该分区划出一块内存空间分配给请求者, 余下的空闲分区留在空闲链中
- 缺点: 低地址反复划分产生碎片（内部碎片/内碎片）
循环首次适应法
- 为进程分配内存时, 从上次找到空闲分区的下一个空闲分区开始查找
- 实现: 设置一个起始查找指针, 以指示下一次查找的空闲分区, 并采用循环查找方式
- 优点: 空闲分布均匀, 查找开销较小
- 缺点: 容易使系统缺少大空闲区
最佳适应算法
- 总是把大小和进程所请求的内存空间大厦最接近的空闲分区分配给进程
- 提高内存利用率
- 容易留下难以利用的小空闲区

基本分页存储管理方式

分页存储基本概念

页: 将进程的逻辑地址空间划分成若干个大小相同的片就是页
页框: 将物理内存空间分成与页大小相同的若干个存储块就是页框, 或者页帧
分页存储: 在为进程分配内存时, 以页框为单位将进程中的若干页分别装入多个可以不相邻的页框中
页内碎片: 进程的最后一页一般装不满一个页框, 从而形成了不可利用的碎片, 就是页内碎片
页表: 页表是操作系统为进程建立的数据结构, 页表的作用是实现从页号到页框的映射

分页存储地址结构

页号P(高20位) 页内偏移量W(低12 位)

32位地址
- 0-11位表示页内偏移, n = 12
  - 页大小 = 页框大小 = 4KB
- 12-31位为表示页号
  - 共有1M个页, 表示4G(1M*4K)的逻辑内存地址
计算
- A 为逻辑地址, L 为页大小,
- P = INT(A/L) P 为页号
- W = MOD(A, L) W 为页内偏移量

分页存储地址变换

页号的页表项起始地址
- 页表起始地址 + 页表项长度 * 页号
  - 对应地址中存放者页框号
物理地址
- 页框大小 * 页框号 + 页内偏移量

页大小选择

通用 4 kb
影响选择的因素
- 管理内存的开销
- 内存的利用率

页表实现

页表项的数量 = 可访存大小 / 页大小

页表的实现

直接放在寄存器中
放置在内存中
- CPU读写内存需要访问两次内存
  - 从内存中获取访存单元所在的页框号, 形成物理地址
  - 然后在根据这个物理地址实现对内存的访问读写等操作

快表

快表也称转换后援缓冲 TLB, 是为了提高CPU访存速度, 而采用的专用缓存, 用来存放最近被访问过的页表项

快表组成

键: 页号
值: 页所在的页框号
数量: 64~1024 个

快表下的地址变换过程

CPU 产生分页的逻辑地址页号和页内偏移之后, 将逻辑地址的页号提交给TLB
查找TLB, 如果找到则把该页所在的页框号用于形成物理地址, 否则从内存查找页表, 找到页表项后, 读取页框号, 形成物理地址
TLB中不存在时, 访问完内存后, 将找到的页表项和页框号写入到TLB中

快表进程切换

每次切换进程刷新一次TLB
TLB中添加地址空间标识符 ASID (用来唯一标识进程)
- 确保访问到的页表项的ASID与查找进程的ASID相同

TLB性能分析

命中
- TLB时间 + 访存时间
没有命中
- TLB时间 + 访存时间 * 2

两级页表

将页表再进行分页, 使每个页表的大小与内存页框的大小相同, 并为他们编号, 两级页表无快表需要三次访存

页目录表
- 页表分页放入不同, 不一定相邻的页框中, 为离散分配的页表再建立一张外层页表
- 页目录表中的每一项记录了页表分页所在的页框号
逻辑地址结构
- 页目录表: 存放了每个页表在物理内存中的页框号
- 结构
  - 高位: 页目录号 p1
  - 中位: 页号 p2
  - 低位: 页内偏移地址 d

两级页表寻址

页目录表写入寄存器 - 页表寄存器: 进程切换时, 页目录起始地址被写入的寄存器

逻辑地址A 分离出页目录号 p1, 页号 p2, 页内偏移 d

由页表寄存器和页目录号 p1获得, 页表的页框号页表的页框号所在的物理地址: 页目录起始地址 + p1 * 页表项长度, 根据这个地址找到页表的框号 TODO:

32位两级分页

10位目录页
10位页表索引
12位页内偏移

多级页表

反置页表

为每一个页框设置一个表项, 表项中存放进程和页号
- 进程 + 页号 => 页框
地址映射
- 根据进程和页号找到页框号
- 物理地址 = 页框号 * 页框大小 + 页内偏移地址

空闲页框的管理

位图管理: 位图中每一位对应一个页框: N个页框需要N个二进制位的位图

空闲页框的链表: 每个几点包含页框的地址信息, 指向后面节点的指针和前面节点的指针

基于分页的虚拟存储系统

虚拟存储器

虚拟存储器是指具有 请求调入功能 和 置换功能, 能从逻辑上对 __内存容量 __ 进行扩充的一种存储器系统

虚拟存储器好处

提高内存利用率
提高多道程序度
把逻辑地址空间和物理地址空间分开

虚拟存储特征

离散性 (1)
多次性 (2)
对换性 (3)
虚拟性 (4)
进程可以分散的存储在物理内存中
不必把进程一次性全部装入内存
在内存中的进程可以换出, 以腾出内存空间换入外存中的进程
虚拟存储系统为用户提供了比实际物理内存大的逻辑内存空间 (最重要的目标)

请求分页系统实现

把进程的逻辑地址分成大小相同的页
操作系统创建进程时只把进程的一部分页调入内存,
进程运行过程中访问内存, 若发现访问的页不再内存中, 则产生一个缺页异常信号
系统响应异常, 请求调入缺页, 如果内存已满, 则从内存中选择若干页换出到外存中

请求分页的硬件需求

页表
- 页框号: 存放页的页框号
- 状态位P: 表示页是否在内存中
- 访问字段A: A=1 表示最近被访问
- 修改位M: 是否被修改过
- 保护位: 标记访问权限, 读写/只读
缺页异常机构: 访存发现缺页时产生缺页异常信号
支持请求分页的地址变换机构

页分配策略

最少页框数: 保证进程正常运行所需要的最小页框数
分配置换策略
1. 固定分配局部置换
  - 页框数固定, 进程内部调出分配
2. 可变分配全局置换
  - 进程分配一定数量页框, 操作系统保持一个空闲页框列队, 缺页时从中调出一个页框
  - 空闲列队较低时, 从内存中选择随机一个进程的页调出
3. 可变分配局部置换
  - 默认只从自身调出, 频繁缺页再追加页框
  - 反之不影响缺页率明显增加下, 可以减少某些进程的页框数
分配算法
1. 平均分配算法
2. 按比例分配算法: 进程页数/所有进程的页数总和*页框数
3. 考虑优先权的分配算法

调入页位置 TODO:

对换区调入
- 比从文件区要快
- 进程运行前从文件区复制到对换区
UNIX 方式
- 没有访问过d的页直接从文件区调入
- 换出的页放在对换区, 曾经运行过被换出的页, 从对换区调入
- 共享的页, 如果其他进程已经调入内存, 就不再次调入

置换算法

最佳置换算法
理论研究和对比
先进先出置换算法 FIFO
实现
- 为每个页记录该页调入的时间
- 选择页换出时, 选择进入时间最早的页
- 创建一个FIFO的列队来管理内存中的所有页
  - 队首的页作为换出页
  - 新加入的页加到队尾
最近最旧未使用 LRU置换算法
算法描述
- 该算法赋予每个页一个访问字段, 用来记录页上一次被访问以来所经历的时间
- 需要选择页换出时, 找到现有页中t最大的页换出
实现
- 寄存器
  - 为每个内存中的页配置一个位移寄存器
  - 页被访问后, 最高位置一
  - 一定时间间隔寄存器右移一位
- 栈
  - 进程刚问页后, 该页页号从栈移出, 压入栈顶, 因此栈顶就是最新访问的编号
  - 栈底则是最近最久未使用的页号
- 计数器
  - 每个页表项增加一个时间字段
其他算法
附加引用位
简单Clock置换
改进型Clock
- 使用情况
- 置换代价
最少使用置换算法
- 访问次数计数器
页缓冲算法

请求分页系统的性能

有效访问时间 = (1-P) * ma + P * 缺页异常时间

P为缺页率, ma为存储器访问时间

Windows 工作集

为了能有效降低缺页率, 从而提高访存的时间效率

进程第一次创建时指定一个最大工作集和一个最小工作集
进程运行小于最大工作集时, 缺页, 系统从空闲页框列队取页框分配给进程
进程页数等于最大工作集时, 缺页, 系统从该进程的页中按FIFO原则换出一个该进程的页
系统空闲页框列队小于一个最低值后, 系统检查所有进程, 对工作在大于最小工作集的进程, 淘汰该进程的一些页, 使其等于最小工作集

抖动

多道程序度太高, 使得运行进程的大部分时间都用于进行页的换入换出, 而几乎不能完成任何有效工作的状态 * 原因: 进程数太多, 每个进程分配到的页框太少

预防抖动:

采取局部置换策略
CPU调度程序中引入工作集算法, 只有当每个进程在内存都有足够大的驻留集时, 才能从外存中调入新的作业
挂起若干程序

分段存储管理

段

把分别存放逻辑上相关的信息, 相互独立的逻辑地址空间称为一个段, 每个段由一个从 0 到最大线性地址的逻辑地址空间组成 * 使用二维地址 * 一个数表示段 * 一个数表示段内偏移 * 包含内容: 一个过程, 数组, 堆栈, 一些数值变量

分段存储优点

方便编程
分段共享
分段保护
动态链接
存储空间的动态增长

基本原理

逻辑地址
- 段号高位16
- 段内偏移低位 16
段表
- 是由操作系统维护的用于支持分段存储管理地址映射的数据结构
- 段表项构成
  - 段号
  - 段基址(起始地址)
  - 段长
地址变换
- 段表寄存器: 保存进程的段表起始地址
- 段表项长度: 一个段表项所占用的字节数
- s号段表项在内存中的起始地址: 段表起始地址+ 段表项长度*段号s
- 段表项获取段基址, 和段界限
  - 如果d小于等于段界限那么s段基址加上段内偏移就是逻辑单元的物理地址
求法
- 已知逻辑单元地址位 s:d
- 段号s为索引再段表中找到s的段表项
- 从段表项中读出段基址和段大小
- 如果d小于等于段大小, 则将段基址和d相加获得逻辑单元的物理单元地址

分段和分页的区别

页是按照物理单位划分的, 分页的引入是为了提高内存的利用率和支持虚拟内存设备
段是按照逻辑单位划分的, 一个段含有一组意义相对完整的信息, 方便编程
页的大小是固定的, 段的大小不固定
分页的地址空间时一维的, 逻辑地址是一个数, 分段的地址空间是二维的, 需要给出两个数:一个段号一个段内偏移

段页式存储

将用户进程的逻辑空间先划分成若干段, 为每个段建立一个页表, 进程以页为单位在物理内存中离散存放每个段中被离散存放的页具有逻辑相关性

系统实现
- 操作系统为每个进程创建一个段表
- 每个段建立一个页表
- 进程段表的每个段表项存放某个段的页表起始地址和页表长度
地址变址
- 地址构成: 段号s 段内偏移d (页号 P 页内偏移W)
- 变换过程
  - 段号s为索引找到段s的段表项, 获得该段页表的的起始地址
  - 通过分页机制从段内偏移d 中分离出页号P和页内偏移W
  - 以段内页号P为索引, 从段s的页表中搜索页号P对应的页表项
  - 从页表项中找到页所在的页框号
  - 由页框号和页内偏移W 获得逻辑地址的物理地址

Linux 伙伴系统

把所有的空闲框分为11个块链表
- 每个链表块分别包含大小为 1 2 4 8 16 32 64 128 256 512 1024个连续的页框
请求一个128个页框的内存, 先在128个页框的链表中检查是否有一个空闲块, 如果没有就找下一个更大的块, 把这个块对半拆分到128 , 中间的空间分离到对于大小的链表里面
目的: 需要为进程分配连续的8KB空间