[!NOTE]

补充

程序装入和链接

创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

  • 编译：由编译程序将用户源代码编译成若干个目标模块。
  • 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。
  • 装入：由装入程序将装入模块装入内存运行。

程序的链接有以下三种方式：

  • 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。
  • 装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，釆用边装入边链接的链接方式。
  • 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。

能够装入内存任何位置的代码程序必须是可动态链接的，因为动态重定位在运行时完成，而静态重定位装入内存前就完成了。

3.1.1 存储管理的主要模式

逻辑地址

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

段式程序设计

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

物理地址

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

主存储器的复用

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

存储管理的基本模式

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

image-20250519142556128

3.1.2 存储管理的功能

地址转换

  • 地址转换：又称重定位，即把逻辑地址转换成绝对地址
  • 静态重定位：在程序装入内存时进行地址转换
    • 由装入程序执行，早期小型OS使用
  • 动态重地位：在CPU执行程序时进行地址转换
    • 从效率出发，依赖硬件地址转换机构

主存储器空间的共享

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

存储保护

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

主存储器空间的扩充

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

3.1.3 虚拟存储器的概念

[!IMPORTANT]

虚存可行性基础是程序执行的局部性

虚拟存储器的基本思想

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

image-20250519144159569

虚拟存储器的实现思路

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

3.1.4 存储管理的硬件支撑

image-20250519145746826

存储管理是OS管理主存储器的软件部分

Cache的组成

  • 高速存储器
  • 联想存储器 根据内容进行寻址的存储器
  • 地址转换不见
  • 替换逻辑
  • 等

image-20250519150652475

image-20250519150732553

地址转换/存储保护的硬件支撑

image-20250519150900308

3.2.1 单连续分区存储管理

单用户连续分区存储管理

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

image-20250519154103109

固定分区存储管理基本思想

image-20250519154200639

3.2.2 可变分区存储管理

按进程的内存需求来动态划分分区

可变分区方式的内存分配

  • 首次适应法：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。
  • 最佳适应算法：从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。
  • 最坏适应分配算法：要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。
  • 循环首次适应算法：该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头(链首)开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。

image-20250529130418758

可变分区方式会产生内存零头

其中不可用的内存零头称为内存外零头

最优适配算法最容易产生内存外零头

可以通过移动技术解决内存外零头

image-20250519155034574

[!IMPORTANT]

  • 分页：将进程分成若干个大小相等的页框，将进程分成若干个大小相等的页，所以进程最后一个页的空间不会被完全占满（因为无法保证进程大小正好整除页的大小），当被放入内存时，最后一页便产生了内部碎片。

  • 分段：分段类似于动态分区，跟动态分区的原理区别在分段可以不连续。段的数目和大小都是可变的，考虑一种情况，当一个旧的进程退出内存，一个比它小的新的进程被分配到它原来占据的空间，因为无法占满，与下一个进程占据内存之间便产生了一段间隔，便是外部碎片（但跟动态分区不同的是，因为可以不连续，所以两块内存之间如果较大可以继续填充进程，因而只会有较小的外部碎片，动态分区的外部碎片则较大），但是没有内部碎片。

    固定分区：固定分区有两种情况，包括分区大小相等和分区大小不等，在系统生成阶段已经将内存分区完毕，当程序大于所有分区，需要采用覆盖技术将程序一部分放进内存中；当程序小于分区时，也是会占据这一整个分区，则产生了内部碎片，无法利用，造成浪费。

  • 段页式：将用户的地址空间分成若干个段，每个段再分成若干个大小固定相等的页，页的长度等于内存中页框的大小，因为分段可以不连续，再者内部被分为若干个页，所以两块进程占据内存之间不存在外部碎片，但是因为页的存在，仍旧存在内部碎片。

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

  • 分页存储器将主存划分成多个大小相等的页框
  • 程序的地址也自然分成页
  • 不同的页可以放在不同框中，不需要连续
  • 页表用于维系进程的主存完整性

页式存储管理中的地址

  • 页式存储管理的逻辑地址由页号和单元号组成
    • 页号+单元号
  • 物理地址由页框号和单元号组成
    • 页框号+单元号
  • 地址转换通过查页表完成

image-20250519192140043

image-20250519194036198

页的共享

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

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

页式存储管理的地址转换代价

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

页式存储管理的快表

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

多道程序环境下的进程表

  • 进程表中登记了每个进程的页表
  • 进程占用处理器运行时，其页表起始地址和长度送入页表控制寄存器

image-20250519195739411

3.3.3 页式虚拟存储管理

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

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

image-20250519201600822

image-20250519201912152

3.3.4 页面调度

缺页中断率

  • 假定进程P共n页，系统分配页框数m个
  • P运行中成功访问次数为S,不成功访问次数为F,总访问次数A=S+F
  • 缺页中断率定义为：f=F/A
  • 缺页中断率是衡量存储管理性能和用户编程水平的重要依据

页面调度算法

  • OPT页面调度算法
    • 理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页

image-20250519203653762

  • 先进先出FIFO页面调度算法
    • 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页(常驻的除外)

[!NOTE]

Belady现象：

在分页式虚拟存储器管理中，发生缺页时的置换算法采用FIFO（先进先出）算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

image-20250519203709707

  • 最近最少用LRU页面调度算法
    • 淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到

image-20250519203736942

  • 最不常用LFU页面调度算法
    • 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
  • 时钟CLOCK页面调度算法
    • 采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
    • 队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
    • 使用页引用标志位

image-20250519203802623

局部页面替换算法

  • 局部最佳页面替换算法

image-20250519204215662

image-20250519204229466

image-20250519204257935

  • 工作集置换算法

image-20250519204346268

image-20250519204402900

image-20250519204416977

image-20250519204427853

伙伴系统

slab分配器

3.3.5 反置页表

[!IMPORTANT]

页表 把主存分成一块一块的页框，把页框放进页里，所以虚拟地址位数决定页表项数

反置页表 物理地址中存虚拟页框，所以物理地址位数决定页表项数

反置页表IPT是MMU（内存管理单元）用的数据结构

基本设计思想

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

反置页表的页表项

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

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

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

image-20250519210404564

3.4.1 段式存储管理

image-20250519210757898

段的共享

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

3.4.2 段式虚拟存储管理

image-20250519212654655

image-20250519212706005

3.4.3 段页式存储管理

  • 段式存储管理可以基于页式存储管理实现
  • 每一段不必占据连续的存储空间，可存放在不连续的主存页框中
  • 能够扩充为段页式虚拟存储管理
  • 装入部分段，或者装入段中部分页面

image-20250520155046359

image-20250520155058296