操作系统4-存储管理

Posted on 2025-05-01

概述

目的

为多道程序的运行提供良好的环境

方便用户使用存储器
提高存储器的利用率
逻辑上扩充存储器容量

基本功能

存储分配和回收
地址变换
存储保护
存储共享
存储器扩充

编译原理基础

源代码转化成进程的三个步骤

编译compile：由编译程序将用户源代码编译成若干个目标模块
链接linking：由链接程序将编译后形成的一组目标模块，以及所需要的苦函数链接在一起
装入loading：由装入程序将装入模块装入到物理内存中

地址和空间

名空间：高级语言常常用符号名来访问某一个单元，将程序中由符号名组成的程序空间称作符号名空间
逻辑空间：源程序经过编译后形成目标程序，这个程序按照0为基址为顺序进行编址，原先用符号名访问的单元用单元号代替，这样目标程序占据一定的地址空间叫做逻辑地址空间
逻辑地址：在逻辑空间中每条指令的地址和指令要访问的操作数地址统称为逻辑地址
内存地址：内存中每个存储单元都有一个编号，称作内存地址
物理空间：所有内存地址构成的集合称为内存空间/物理空间,可进行一维线性地编号
地址映射Mapping：将逻辑地址转换为运行时由机器寻址的物理地址
498f9f12a3a9b94d372446ebe7591dbd

链接

源程序经过编译后得到一组目标模块，再利用链接程序将这组目标模块链接形成装入模块

静态链接：程序运行前，将各个目标模块和他们所需的库函数，链接成一个完整的装配模块之后不再拆开
- 相对地址的修改：每个其实模块用到相对地址，起始地址为0，链接成一个装入模块时要修改成模块的相对地址
- 变换外部引用地址：外部调用符号也相应地变换相对地址
- 缺点：不利于代码共享，不利于模块的独立升级，也可能链接不会执行的模块浪费存储空间和处理机时间
装入时动态链接：装入一个目标模块时，若发生一个外部模块调用时间，将引起装入程序去找出相应的外部模块，装入内存并修改模块的相对地址
- 优点：利于模块的独立升级和模块的共享
- 缺点：可能链接不会执行的模块，装入后不能移动位置
运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，由操作系统去找到该模块并将之装入内存，随后把它链接到调用者模块上
- 优点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

装入

将可装入模块装入内存

地址重定位：将可执行文件的逻辑地址转化为内存物理地址的过程

绝对装入方式
- 在编译时就知道程序将驻留在内存中的具体位置，编译程序产生绝对地址的目标代码
- 优点：实现简单，无须进行逻辑地址到物理地址的变换
- 缺点：程序每次必须装入同一内存区，程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址，不适于多道程序系统
可重定位（静态重定位）方式
- 编译时采用相对地址，即编译器假设是装入到从零开始的内存位置
- 优点：易实现，无需硬件支持
- 缺点：程序重定位后就不能移动，因而不能重新分配内存，不利于内存的有效利用，程序在存储空间中只能连续分配，不能分布在内存的不同区域，难于共享
运行时重定位（动态重定位）装入方式
- 程序的地址转换不是在装入时进行，而是在程序运行时动态进行，需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址，是实现装入的主流方式
- 优点：程序不必连续存放在内存中，可分散存储，可移动；便于共享；对于存储器紧缩、解决碎片问题极其有利
- 缺点：需要硬件支持，实现存储管理的软件算法比较复杂；同一地址，可能多次转换。

需求

在单道程序设计中，内存的使用目的：

供操作系统使用：驻留监控程序，内核
供当前正在执行的程序使用

在多道程序设计中，必须作进一步细分，由于处理器长期空闲，因此必须有效分配内存来保证适当数量的就绪进程可以占用这些可用的处理器时间；

内存管理的功能需求

重定位：进程在内存中进出，放置于不同位置的能力
保护：保护进程的程序和数据不被未授权的进程访问和修改
共享：不损害基本保护的前提下，必须对内存的共享区域进行受控访问
逻辑组织：利于系统和硬件能有效地处理某种某块形式组织的用户程序和数据
物理组织：计算机存储器的两级划分（内存和外存）的移动信息应该由系统负责；

内存分配（内存分区）

内存分配包括以下：

连续分配：单一连续分配，涉及分区管理，内存扩充（覆盖和对换）
离散分配：涉及对分页式，段式和段页式存储管理
虚拟存储器：涉及请求分页存储，请求分段和段页式虚拟存储

连续分配方式

连续分配

原理：内存划分为系统区和用户区，整个用户区分配一个进程

适用场合：最简单，适合当用户和单任务OS

优点：易于管理

缺点：造成空间的浪费

分区管理

原理：将内存分为一些大小相等或不等的分区，每个应用进程个占用若干个分区，操作系统占用一个分区

特点：适用于多道程序系统和分时系统

内部碎片：占用分区之内未被利用的空间

外部碎片：占用分区之间难以利用的空闲分区

固定分区

原理：将内存划分为大小相等或不等的分区，在每个分区只装入一道程序，分区的划分有OS决定，一旦划分结束，总分区个数保持不变

特点

适用于多道程序系统和分时系统
支持多个进程并发执行

问题

程序可能太大装不到一个分区
内存利用率可能很低，程序小可能也要占用一个分区，形成内部碎片现象；

划分方法：分区大小相同/分区多种大小

分区描述表：通常将分区按大小排队，标明起始地址和分配状态，建立分区描述表

分配算法

对于分区大小相同：使用哪个分区都没关系
对于分区大小不同：最佳匹配（为空闲分区选择最佳任务/根据任务选择最佳空闲分区），或者最坏匹配

存储保护：防止某个作业破坏系统或者其他作业，通常采用界限寄存器实现，每个寄存器都对应两个代表上下限的寄存器用于越界保护；

优点

比单一连续分配方法，提高内存的利用率
可以支持多道程序，无外部碎片
实现简单

缺点

分区数目在系统生成时确定，限制系统中活跃进程的数目；
小作业的内部碎片可能比较大；
作业必须要预先估计自己要占用多大空间；

动态分区

根据进程的实际需要，动态地分配内存空间，因此动态分区的长度和数量是可变的；

使用动态分区的方式，需要维护：

空闲分区表：记录每个空闲分区的情况；
空闲分区链：通过指针的迭代拼接称双向链；

分配算法

首次匹配算法First Fit
- 要求空闲分区链以地址地震的次序链接，在分配内存时，从链首开始顺序查找，知道一个大小满足要求的空闲分区为止；
- 为大作业分配大的内存空间创造了条件
- 低地址空间不断被划分，留下难以利用的小空闲分区，增加查找查找开销
循环匹配算法Next Fit
- 为空闲分区构成循环链表，采用循环查找方式，设置一个开始查寻指针，用于指示下一次起始查询的空闲分区
- 使得内存空闲分布更均匀，减小查找开销
- 缺乏大的空闲分区
- 空闲分区应该按照地址顺序排列
最佳匹配算法Best Fit
- 每次分配内存时，总是能把满足要求又是最小的空闲分区分配给作业
- 产生的外部碎片小
- 碎片太小往往难以利用，造成浪费
- 按容量从小到大排列
最坏适应算法Worst Fit
- 每次满足要求又是最大的空闲分区给作业
- 留下的空闲分区很大方便下一次利用
- 不利于大作业
- 按容量从大到小排列

分区管理

分配：按照算法选择空闲分区，并在空闲分区表删除，添加新产生的空闲分区
回收：当进程运行完毕释放内存时，需合并相邻的空闲分区，形成大的分区
紧凑和动态重定位：将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区

存储保护：上、下界寄存器方法/基址、限长寄存器方法2

优点

支持多道程序
管理方案简单，不需要更多的软硬件开销
实现存储保护的手段比较简单

缺点

主存利用不够充分
无法实现多进程共享存储器的信息（不是分段内存分配都无法实现）
无法实现主村的逻辑扩充，进程的地址空间受物理内存的限制

伙伴系统

伙伴系统是固定分区和动态分区的折中方案；

设计可用的内存块大小为$2^k(L\le k\le U)$字节，整个分配空间被视为$2^U$的块；

对于进程申请$2^{i-1}< p\le 2^i$的空间，可以用以下的递归算法找到大小为$2^i$的块；

查找大小为$2^i$的空闲分区，若找到则分配；
若未找到大小为2i的空闲分区，则查找大小为$2^{i+1}$的空闲分区；
- 若找到，则将该空闲分区划分为相等的两个分区（一对伙伴），其中的一个用于分配，另一个分区加入大小为$2^i$的空闲分区链中；
以此类推

内存扩充

内存扩充：借助大容量辅存在逻辑上实现内存扩充，来解决内存容量不足的问题；
覆盖和交换：需要在较小可用内存运行较大的程序，在任何时候，只在内存中保留所需的指令和数据，当需要时，在从外存中写回内存

覆盖overlay

基本思想:一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。

实现：

将程序的必要部分代码和数据常驻内存；
可选部分在其他程序模块中实现，平时存放在外存中（覆盖文件），需要用到时才装入到内存；
不存在调用关系的模块不必同时装入到内存，可相互覆盖

交换swapping

基本思想：把内存中展示不能运行的进程或者暂时不使用的程序和数据换出到外存上，以腾出足够的内存空间
粒度：

进程交换：解决内存紧张问题，进一步提高内存利用率
页面交换，分段交换：可以支持虚拟存储系统

管理：

外存：对换区比文件区侧重于对换速度
对换区一般采用连续分配

优点：

换入和换出操作由内存管理模块，与程序结构无关

离散分配方式

解决问题

一个进程的分配的内存由多个离散的空间组成

固定分区存在内存碎片
动态分区存在外部碎片
可重定位动态分区的系统开销大

基本单位

分页式存储管理

页面：程序地址空间被划分为若干固定大小的片段
页框：物理内存被划分成相同大小的块

分段存储管理

以段为基本分配单位的存储管理方式

段页式存储管理

段内分页

分页式存储管理

存储管理系统负责用户空间，物理空间的划分编号；
以下是程序空间到物理空间的映射，程序的每一个页分散到物理空间的页；而从每一页看地址都是连续的；

逻辑地址结构转换物理地址
假设对于32位的机器，页面大小为$L=2^{12}$，给定逻辑地址空间的地址为$A$

页号$P=\lfloor \frac{A}{L} \rfloor$：12-31位
页内偏移量$d\in [0,L)$：0-11位

对于16位的机器而言，页号占6位，页内偏移量占10位；

页表则维护每个页面对应的页框信息，即页号和段号的映射

存储在内存
PCB保存页表的起始地址
快表：对页表的使用频度高表项用高速缓存器存储

优点：

存在页内碎片，但是碎片小，内存利用率高
实现了离散分配
无外部碎片

缺点：

需要专门的硬件支持，尤其是快表
不支持动态链接，不易共享

分段存储管理

引入原因：

更自然组织信息：通过段名访问程序段和数据段
信息共享和共享：段是信息的逻辑单位，页只是存放信息的物理单位
动态增长：数据段事先无法知道大小
支持运行时动态链接

组织方式

段：定义一组逻辑信息，段+段内偏移量

对于32位的机器，段号：24-31位，段内偏移量：0-23位

从0开始编址
长度：由段定义的逻辑信息决定
每个逻辑段庄在到一段动态内存区域

段表：记录逻辑段和物理段的对应情况
段号+段长+段首址+控制信息

段表寄存器中存放段表的起始地址和段表长度
检查段号和段内偏移量越界：非法产生越界错误
检查访问控制字段：确定是否合法

优点：

便于模块化设计
便于动态链接
便于共享与保护
无内部碎片

缺点：

地址转换需要硬件支持（段表寄存器）
分段最大尺寸受主存可用空间的限制
有外部碎片

段页式存储管理

分段和分页的比较

方面	分页	分段
从设计目的来看	页是信息的物理单位，分页的目的是实现离散分配，减少内存的外部碎片，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。	段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
从系统实现上看	页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；	而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
从功能实现上看	不易共享和运行时动态链接	易于共享和运行时动态链接
从编址方式来看	分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；	分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

段页式存储管理

采用分段方法组织用户程序，用户程序采用模块化设计，用若干段划分
采用分页方法分配和管理内存，内存分成若干页框，程序每个段风格成若干页后装入内存

逻辑地址：段号s+段内页号p+页内偏移量w

检查段号，段表访问控制字段，页号是否越界
页内偏移量送入物理地址的低端

优点

离散存储
内存利用率高
便于保护和共享，支持动态链接
无外部碎片

缺点

地址转换复杂
有内部碎片

虚拟存储方式

虚拟存储方式由虚拟内存机制实现

虚拟内存

硬件和控制结构

理论依据

常规的存储管理技术：

一次性：需要作业全部装入内存运行
驻留性：作业装入内存后，一直驻留内存直到作业结束
难以满足大作业运行需求和大量作业并发，对于已装入内存的代码利用率低

程序的局部性原理：在一段较短时间内，程序的执行仅局限于某个部分，相应地访问的存储空间也局限于某个区域

时间局限性：下一次指令执行，数据访问集中在较短时间内;
空间局限性：下一次执行指令，数据访问集中在较小的区域；

程序运行特点：

大部分时间顺序执行
即使有跳转，也仍局限在某些函数下
许多循环结构下，少量指令多次执行
对数据结构的操作往往局限于小范围

虚拟内存方案：

将当前要执行的部分页/段读入内存，就可以运行程序
缺页/段时，处理器临时通知；
暂不使用的页/段换出内存；

这表明虚拟内存方案是可行的；

虚拟存储器

功能：

请求调入和置换：从逻辑上对内存容量加以扩充
总容量由内存容量和外存容量之和决定
运行速度接近内存，位成本接近外存

特征

离散性:程序在内存中离散存放
局部性:进程无需全部驻留内存,只需载入必要的进程空间
对换性:允许进程在运行过程中换入、换出
虚拟性:能够从逻辑上扩充内存容量,使用户所看到的内存远大于内存容量

硬件支持：

相当数量的外存
一定容量的内存
请求分页或分段的页表或段表机制
缺页或缺段机构
地址变换机构

常见技术

请求分页存储管理
请求分段存储管理
请求段页式存储管理

较小的页面有利于减少页内零头，但是可能导致页表过大，降低命中率；
较大的页面，内外存交换效率高，但是带来额外开销；
需要一种tradeoff机制；

二级页表

快表TLB

原理：基于局部性原理，提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器（Translation Lookaside Buffer）；

地址转换：

分离提取页面号+页内偏移
检查页面号是否合法，非法报越界错误
根据页面号检索快表
- 若命中，提取页框号，进入5；
- 若未命中，重新检索页表，结果载入快表，替换许久不用的表项
检查访问控制字段，非法则报错
计算物理地址：页框$\times$页面大小+页内

若页表存放在虚存中,则要实现一次页面访问需两次访问 物理内存存

第一次是访问页表,确定所存取页面的物理地址;
第二次根据该地址存取页面数据。

操作系统软件

原理：

建立在分页机制上：页面，页框和页表
请求调页和页面置换功能：部分页面载入内存，对换机制和将页面作为换入换出的基本单位

页表机制

1	<页号><页框号><状态位P><访问字段A><修改位M><外存地址>

状态位：指示该页是否调入内存
访问字段：记录指定时间段的访问次数；
修改位：该页调入内存后是否被修改
外存地址：用于指出该页在外存上的地址

缺页中断机制

每当要访问的页面不在内存中，产生缺页中断，请求OS调入；

在指令执行期间产生和处理中断信号；
一次指令执行期间，可能产生多次缺页中断；
带快表的基本分页地址：
缺页中断处理
页面换出

置换策略

概念

置换策略包括分配页面，调入页面和置换页面的内容

分配页面：如何为每个进程分配页面
调入页面：何时调入页面，从哪调入页面和调入哪些页面
置换页面：交换区如何组织，换出页面的选择和换出实现

置换算法

概念：选择换出页面的算法
评价标准：页面交换的频率
设计目标：优先换出不再访问的页面和最久不访问的页面
设计原则：基于过于页面访问行为预测将来的页面访问

最优置换算法OPT

基本思想：换出不再访问的页面，换出下次访问距离当前时间最长的页面
评价：

属于理想算法，通过未来页面走向选择被淘汰的页面，可以保证最少的缺页中断次数
需要知道未来访问的顺序，不可能实现，是其他算法的baseline

例子
发生缺页中断次数：9
页面置换次数：6

先进先出算法FIFO

基本思想：换出最早调入内存的页面
实现：采取链表结构
评价：

简单易于实现
未考虑程序的时间局部性原理
存在Belady现象：随着分配的页框数增加，缺页中断次数反而增加

例子
发生缺页中断次数：14
页面置换的次数：11

最近最久未使用算法LRU

基本思想：时间局部性原理
算法：选择最近一段时间最长时间没有被访问过的页面淘汰
实现：寄存器表+双向链表
评价：

性能较好，因为基于时间的局部性原理
开销过大，需要统计页面的访问时间信息，获取最久未使用页面，又是页面数过大，寄存器表不现实；

例子：
发生缺页中断的次数：12
页面置换的次数：9

时钟置换算法CLOCK Not Recently Used

基本思想：对LRU算法的近似，换出最近未访问的页面的NRU算法；
实现：

每个页面设置访问位R，访问时置1
页框内所有页面保存在环形链表中
发生缺页中断时，优先检查表指针指向页面，若R=0，淘汰页面；R=1，清除R位，前向移动指针，找到访问位为0的页面后换出；

评价：

算法简单
性能和置换间的间隔密切相关，过大过小可调整随机选择换出页面
未考虑页面修改情况

对页面修改进行改进：页面分类

最近未被访问，未被修改：最佳淘汰页
最近未被访问，但已被修改
最近被访问，未被修改
最近被访问且被修改

改进实现：

选择1类页面
若失败，寻找第2类页面，并把扫描过的页面访问位置0
若步骤2失败，回到步骤1

缺页率

发生缺页的次数/总访问次数

页面置换算法
页面大小
进程所占的页框数
程序本身

矩阵int a[100][100]以行优先进行存储。有一请求分页存储管理系统,物理内存共有3页,其中1页用来存放程序,其余2页用于存放数据。假设程序已在内存中占1页,其余2页空闲;数组中的元素按行编址存放。

for (i=0; i<=99; i++)
	for (j=0; j<=99; j++)
		a[i][j]=0;
		
for (j=0; j<=99; j++)
	for (i=0; i<=99; i++)
		b[i][j]=0;

假定两个内存页，每页200个数据；

程序A对数组的访问顺序与存储顺序一致，每访问2行数组元素就会产生一次缺页中断，故缺页中断次数为50

程序B对数组的访问顺序与存储顺序不一致，每访问数组元素就会产生一次缺页中断，故缺页中断次数为5000

平均访问时间：$(1-p)m_a+pd_a$

缺页率为$p$
内存访问时间为$m_a$
发生缺页时访问时间为$d_a$

有效访问时间构成：

缺页服务时间
进程重新执行时间
页面调入时间（主要）：寻道时间+旋转时间+数据传送时间

工作集

进程对地址空间的访问不均匀，在确定的时间内，进程往往只访问固定的几个页面；
工作集：在某段时间间隔内，进程实际要访问的页面的集合

进程分配的页框数不能少于工作集大小
不同时刻，进程的工作集大小可能不同，系统根据缺页率动态调整进程的分配页框数

缺页率和物理块数关系

抖动/颠簸thrashing

抖动是虚拟存储的典型问题

页面被频繁地换入换出，缺页率增加
内存有效存取时间加长
系统吞吐量骤减，系统难以完成任务

原因：

CPU利用率低，调度程序增加并发，导致内存不足，缺页，I/O忙碌，CPU空闲
多道程序并发度高，每个进程分配的页框数数目少

抖动的预防

采取局部置换策略：某进程发生缺页时，仅在自己内存空间范围内置换页面，创建新进程不会几张其他进程的内存空间
CPU调度程序采取工作集算法：防止调入过多的新任务，每个进程应具有超过其工作集大小的页框数
L=S准则：发生缺页的平均时间L等于处理缺页故障的平均时间S，此时系统具有最好的并发度
挂起若干进程

请求分页存储管理

优点

存在页内碎片，但碎片相对较小，内存利用率较高
实现了离散分配
无外部碎片
提供了虚拟存储器，使大作业可以在较小的实际内存中运行
并发度高

缺点

必须有相应的硬件支持
不支持动态链接，不易实现共享
可能发生系统抖动现象

原理

建立在基本分段机制上:
- 程序的逻辑地址空间被划分为若干个大小不同的段
- 每个逻辑段装载到一段连续的物理内存区域
- 段表记录逻辑段和物理段的对应情况
引入请求调度和分段置换机制
- 部分逻辑段载入内存
- 对换机制
- 以段作为换入或换出的基本单位

段表机制

段表寄存器地址组成如下：

1	<段号><段长><段首址><存取方式><访问位A><修改位M><状态位P><增补位><外存地址>

访问字段A：用于记录本段在一段时间内被访问的次数
修改位M：表示该段在调入内存是否被修改
状态位P：用于指示本段是否调入内存
增补位：特殊字段，用于表示本段在运行时是否动态增长
外存地址：指示本段在外存中的地址；

缺段中断

每当所要访问的段不在内存时，便产生缺段中断，请求OS 将所缺之段调入内存。

段中断不会发生一条指令被分割在两个段的情况；

地址转换

访问一个段地址[s][w]时，检查三种条件是否发生错误：

w超过段长：报越界错误
存取方式位不符合：触发中断保护
检查段s是否在主存：缺段中断处理

动态链接&链接中断

动态链接实现：请求分段存储管理

程序运行时，只讲主程序段装配好，调入内存，其他段在运行时装配完成；

调用新段时，将新段装配好并链接主段；

段页式虚拟存储技术

建立在段页式存储技术之上
- 程序的逻辑空间划分为若干大小不同的段
- 每个段划分为若干固定大小的页面
- 物理内存划分为若干固定大小的页框
- 页面可以载入任意页框——页表记录载入情况
引入请求调页和页面置换机制
- 部分页面载入内存
- 对换机制
- 以页面作为换入或换出的基本单位
地址变换：先查段表，再查该段的页表

共享和保护

整个系统共享一张共享段表：段本身信息，引用者信息；

共享段表地址组成：

1	<段名><段长><内存地址><状态><外存起始地址><共享进程计数count><状态><进程名><段号><存取控制>

共享段的分配：第一次访问需要分配内存，增加共享段表，修改进程段表，后续访问无需分配内存；

保护：

段号越界检查
段内页号越界检查

其中环保护中，内环可访问外环数据，外环请求内环服务；

概述

目的

基本功能

编译原理基础

地址和空间

链接

装入

需求

内存分配（内存分区）

连续分配方式

连续分配

分区管理

固定分区

动态分区

伙伴系统

内存扩充

覆盖overlay

交换swapping

离散分配方式

解决问题

基本单位

分页式存储管理

分段存储管理

段页式存储管理

虚拟存储方式

虚拟内存

硬件和控制结构

理论依据

虚拟存储器

二级页表

快表TLB

操作系统软件

页表机制

缺页中断机制

置换策略

概念

分类

页面调入

页面换出

页面置换

置换算法

最优置换算法OPT

先进先出算法FIFO

最近最久未使用算法LRU

时钟置换算法CLOCK Not Recently Used

缺页率

工作集

抖动/颠簸thrashing

请求分页存储管理

优点

缺点

原理

段表机制

缺段中断

地址转换

动态链接&链接中断

段页式虚拟存储技术

共享和保护