代码炼金工坊

操作系统概论-内存管理
April 7, 2021

存储器的层次结构

L0 ~ L2 在 CPU 中。

每一层级的存储器保存来自下一层级的存储器信息。

局部性原理

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

  • 时间局部性
  • 空间局部性

程序的链接和装入

链接:将编译后的目标模块装配成一个可执行程序

链接的分类:

  • 静态链接:程序运行前,用 链接程序 将目标模块链接成一个完整的装入模块
    • 对逻辑地址进行修改
    • 变换外部调用符号
    • 优点:运行速度快
    • 缺点:系统开销大
  • 动态链接:将某些目标模块的链接推迟到这些模块中的函数被调用时才进行

装入方式:

  • 绝对装入方式:编译时产生 物理地址 的目标代码
  • 可重定位装入方式(静态重定位):编译时地址是 逻辑地址 ,装入时通过 重定位 转换为 物理地址
  • 动态运行时装入(动态重定位):程序执行时通过 重定位 转换为 物理地址

连续分配存储管理方式

  • 单一连续分配:任何时刻主存储器 最多只有一个作业
  • 固定分区分配: 具有 上限寄存器下限寄存器 ,每个分区 大小固定不变 ,每个分区可以且仅可以装入一个作业
  • 动态分区分配:分区大小不是预先固定的,按实际需求划分。分区个数也不是预先固定的,按装入作业数决定。

空闲分区链:动态地为每一个分区建立一个结点。分区起始地址,分区大小,指向前一个空闲分区结点的指针,指向后一个空闲分区结点的指针

动态分区分配算法:

  • 首次适应算法:空闲分区链以 地址递增 的顺序链接从链首开始查找,直到找到 第一个满足要求 的空闲分区。从该分区中划出一块内存给进程,剩下的仍留在空闲链中
    • 缺点:碎片多
  • 循环首次适应算法:从 上次找到的 空闲分区的 下一个 空闲分区开始查找。
    • 优点:空闲区分布均匀,查找开销较小
    • 缺点:缺乏大空闲区
  • 最佳适应算法:空闲链以 分区大小递增 的顺序链接从 链首 开始查找,直至找到第一个与进程请求的空间大小 最接近 的空闲分区
    • 优点:提高内存利用率

动态分区的分配流程:

  • 检索空闲分区链
  • 分配空闲分区
  • 将分配给进程的分区起始地址返回给内存分配程序的调用者
  • 修改空闲分区链表

动态分区的回收流程:

  • 释放一块连续的内存区域
  • 如果被释放的区域与其他空闲区相邻,则合并空闲区
  • 修改空闲分区链

基本分页存储管理方式

基本原理

页:将一个进程的 逻辑地址空间 分成若干个大小相等的

页框:将 物理内存空间 分成与页大小相同的若干个 存储块

分页存储:将进程中的若干 分别装入多个 可以不相邻页框

页内碎片:进程 最后一页 一般装不满一个页框,形成页内碎片

页表:实现 从页号到页框号 的映射

逻辑地址结构:页号(P)和页内偏移量(W)。设逻辑地址为 A ,页大小为 L ,则 P=A/L, W=A%L。单位是 Byte 。

分页地址变换机构:

  • 进程执行, PCB 中 页表起始地址页表长度 送 CPU 的页表寄存器
  • CPU 访问某个逻辑单元 A
  • 由分页 地址变换硬件 自动将 A 分为 页号页内偏移 两部分
  • 由硬件检索 页表 , 得到 A 所在的页对应的 页框号
  • 页框号页内偏移地址 送物理地址寄存器,计算 物理地址 。 (物理地址=页框大小x页框号+页内偏移量)

页大小的选择因素:

  • 管理内存开销:较小,划分为较多页,页表过长,占内存;较大,页内碎片大,空间利用率低
  • 内存的利用率:较小,有利于提高内存利用率

快表

键值组成。

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

性能分析:TLB 命中率

  • 能在 TLB 中找到所需要的页表项时:有效访存时间 = 一次访问 TLB 的时间 + 一次访问内存的时间
  • 不能在 TLB 中找到所需要的页表项时:有效访存时间 = 一次访问 TLB 的时间 + 两次访问内存的时间(一次访问内存页表,一次访问内存读写数据或指令)
  • 有效访存时间定义:(在 TLB 找到所需页表项时间) x 命中率 + (不能在 TLB 中找到所需要的页表项时间) x (1 - 命中率)

两级和多级页表

将页表再分页,形成两级或多级页表,将页表离散地存放在物理内存中。

基于分页的虚拟存储系统

虚拟存储器

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

如何理解请求调入和置换?

请求调入:先将进程的一部分装入内存,其余的部分什么时候需要什么时候请求系统装入。

置换:请求调入时没有足够的内存,由操作系统选择一部分内存中的进程内容移到外存,腾出空间来调入需要装入的内存。

优点:

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

请求分页

最基本、最常用的虚拟存储系统实现方式。

硬件支持

为了实现请求分页,需要: 特殊的页表缺页异常机构 和支持请求分页的 地址变换机构

  • 特殊的页表:标识页是否在内存中、记录页最近被访问的情况、标识页最近是否被修改过、标识页的访问权
  • 缺页异常结构:在访问内存过程中发现缺页时产生缺页异常信号
  • 地址变换:
    • 分页地址变换机构计算出页号和页内偏移地址
    • 查找快表 ,如果找到页号,读出页框号,计算物理地址
    • 若快表无该页信息,转到内存页表中查找 页表 ,如果该页已调入,读出页框号,计算物理地址
    • 如果该页尚未调入内存,则产生 缺页异常 ,请求调入该页,修改页表,重新执行因缺页被中断的指令

页分配策略

最少页框数:保证进程正常运行的所需要的最少页框数。与进程大小无关,取决于 指令的格式、功能和寻址方式

局部置换和全局置换

固定分配和可变分配

页置换算法

最佳置换算法(理论研究):选择 以后永远不会被访问的页 或者 在未来最长时间内不再被访问的页 作为换出页

先进先出置换算法 FIFO (最简单):为每个页记录该页调入内存的时间,选择换出页时,选择 进入内存时间最早的页

最近最久未使用置换算法 LRU (近似最佳):选择 最近最久未使用的页 换出

附加引用位算法:选择附加引用为值最小的换出

简单 Clock 置换算法:选择最近没有被访问的淘汰

改进型 Clock 算法:选择既没有被访问过又没有被修改过的淘汰

最少使用置换算法:选择最近时期内使用次数最少的淘汰

页缓冲算法:将换出页移到空闲页链表中

请求分页系统的性能

缺页率对有效访问时间的影响:有效访问时间与缺页率成正比,缺页率越高,有效访问时间越长,访问效率越低

工作集:引入用于降低缺页率,提高内存访问效率。藕断时间间隔里了,进程实际要访问的页的集合。

抖动:进程数太多,分配到的页框太少。运行进程的大部分时间都在用于页的换入换出,几乎不能完成任何有效果工作状态。

分段存储管理

分段机制的引入

主要是为了 易于实现信息共享

在分段存储管理的系统中,程序员使用 二维 的逻辑地址,一个数用来表示 , 另一个数用来表示 段内偏移

基本原理

进程的地址空间被划分成若干个段。

每个段定义了一组逻辑信息,每个段的大小由相应的逻辑信息组的长度确定,段的大小不一样,每个段的逻辑地址从0开始 ,采用一段 连续的地址空间

系统为每个段分配一个 连续的物理内存区域 ,每个 不同的段可以离散 地放入物理内存不同的区域。

系统为 每个进程建立一张段表 , 段表的每一个表项记录的信息包括 段号,段长和该段的基址 , 段表存放在内存中。