OS-3-内存管理思维导图模板_ProcessOn思维导图、流程图

内存管理的工作

内存空间分配与回收

内存空间的扩充

存储保护

保证进程在运行中互不干扰

越界时抛出越界异常

一般采用的方法

上下限寄存器

重定位寄存器(基址寄存器)+
界地址寄存器(限长寄存器)

限长寄存器存放最大逻辑地址

基址寄存器存放起始物理地址

允许不连续装入的程序

内存空间的扩充

覆盖技术

程序分段，常用段常驻内存，
不常用段按需调入

内存中

一个固定区

常驻段
一经调入不再调出

若干覆盖区

不常用段

按照程序逻辑，让不可能被同时访问的
程序段共享同一覆盖区（如同级分支）
覆盖区大小为较大者

在进程内进行

只能由程序员声明覆盖关系

交换技术

将部分进程暂时换到外存（挂起），把外存中具备运行条件的进程换入内存

PCB常驻内存

进程被保存在外存的“对换区”

“对换区”

采用连续分配方式，追求换入换出速度

IO速度更快

“文件区”

采用离散分配方式，追求存储空间利用率

在进程间进行

交换时机

进程频繁缺页

换出部分进程

缺页率明显下降

停止换出

系统负荷高

停止换出

交换对象

阻塞态进程

低优先级进程

可能饥饿

驻留时间长的进程

虚拟内存技术

概念

背景：传统的存储管理具有一次性和驻留性的特征

基础

基于局部性原理

空间局部性

时间局部性

高速缓存技术

离散分配

基本特征

多次性

作业无需一次性装入，而是分多次按需调入

对换性

作业运行时无需常驻内存，允许在作业运行过程中将作业换入换出

虚拟性

逻辑上扩充了内存容量，使得用户感受到的内存大于实际

基本功能

页面/段置换功能：不在内存时，向OS请求将目标页/段调入内存

请求换出功能：内存空间不足时，由OS将暂时不用的页/段换出

相对于一般的离散分配，根据基础
技术的选择，虚拟存储实现可分为

请求分页存储管理

请求分段存储管理

请求段页式存储管理

请求分页管理方式的实现

页表机制

OS需要知道页面是否已经调入，以及在外存中的位置

OS需要知道当前要换出的页面是否已经修改过

相比基本页表，此页表称为请求页表

页表项的结构

内存块号

状态位

是否已经调入内存

访问字段

记录被访问次数或上次被访问的时间
为置换算法提供数据参考

修改位

是否已被修改过

外存地址

缺页中断机构

当要访问的页面不在内存中，产生缺页中断，并阻塞。

缺页中断是一种内中断

请求OS的缺页中断程序处理，将目标页面调入内存，将其唤醒，放回就绪队列

若内存有空闲，则直接为页面分配一个空闲块，并改动对应页表项

若内存无空闲，根据置换算法换出一个页面，若其被修改过，则写回外存，
若未被修改，无需写回。然后将该块分配给待调入页面

一条指令可能产生多次缺页中断

只有写指令写入对应页面时才需要修改页表项的修改位，以减少访存
修改也只需修改TLB中的快表项，并在删除快表项时才写回内存。

换入换出速度极慢，大量等待IO，换入换出越多，性能越差

调入内存后，需要修改慢表，并将对应项复制到TLB

地址变换机构

首先检查页号是否越界

快表是否命中

命中，直接访问

未命中，是否在内存中

在，直接访问

不在内存中，调入内存

页面置换算法
追求低缺页率

最佳置换算法OPT

由于无法预测未来访问的页面，不可实现

理论性能最佳

先进先出FIFO

不考虑局部性原理，即使最先调入Cache访问也可能最频繁

实现简单

刚被换出的块很快又被换入，频繁换出换入导致抖动

Belady异常

增加物理内存大小，缺页次数不减反增的现象

只有FIFO会产生此异常

最近最久未使用LRU

每次淘汰最近最久未被访问的页面

考虑了局部性原理，命中率高，但是需要专用硬件支持

若频繁访问的主存块数量大于Cache块数则还是存在抖动

手动计算

自替换处逆向寻找当前内存块，出现最晚的页面被替换

时钟置换算法CLOCK
最近未使用NRU

性能和开销相对均衡

实现

为页面设置一个访问位，通过链接指针将页面链接成环形

访问某页时，设访问位为1

淘汰某页时，访问位为0则换出，若是1，
则置为0，且暂不换出，检查下一页面。

由于内存被组织为环形，第二轮扫描必有0，因此淘汰一个页面最多只需两轮扫描

改进时钟置换算法
淘汰最多扫描四轮

优先淘汰未修改过的页面(修改位为0)

第一轮尝试找到未访问，未修改(0,0)
本轮不修改任何标志位

第二轮尝试找到未访问，修改过(0,1)
本轮只修改访问标志位

修改使(1,0)变回(0,0)

第三轮尝试找到未访问，未修改(0,0)
本轮不修改任何标志位

第二轮尝试找到未访问，修改过(0,1)

必然存在

页面分配策略

驻留集

请求分页存储管理中，给进程分配的物理块集合

驻留集过小，缺页频繁

驻留集过大，并发度下降，资源利用率降低

页面分配、置换策略

固定分配局部置换

驻留集大小固定，且页面置换只能是自己的页面

固定分配不可能全局置换

可变分配全局置换

驻留集大小可变，且页面置换可以来自
其他位置甚至其他进程

换入时若无空闲块，选择一个未锁定的页面换出内存

缺页时就进程多分配了一个物理块

OS锁定部分重要的不可换出的页面，如OS的数据

可变分配局部置换

缺页率高，增加物理块

缺页率降低，减少物理块

调入页面的时机

预调页策略

一次调入若干相邻的页面

一般只用于进程首次调入时，由程序员指出需要调入

请求调页

IO开销大，缺页时调入

从何处调入页面

有足够的对换区空间

从对换区调入

无足够的对换区空间

凡不会被修改的，从文件区调入(不会再写回)

凡可能被修改的，写回对换区

UNIX方式

未使用过的页面，从文件区调入

换出时写回对换区，以后再从对换区调入

抖动

频繁的页面调度称为抖动(换入后马上换出，换出后马上换入)

物理块不足

工作集

某段时间间隔内，进程实际访问的页面的集合

OS根据窗口尺寸计算工作集

工作集越小，局部性越好

OS可以监控进程的运行，统计出进程的工作集大小，从而指导驻留集的大小

驻留集一般不小于工作集

基本概念

内存

缓和外存和CPU的速度矛盾

存放待运行的程序

地址

用于标记程序存放的位置

常见的数量单位

B

K-,M-2,G-2

进程运行的基本原理

指令工作原理

操作数OP

操作数

地址

寻址方式

地址

逻辑地址

程序生成时，指令指明的是逻辑地址
即相对于起始地址的地址（相对地址）

物理地址

执行过程中实际访问的地址（绝对地址）

从代码到程序

编译

将源代码编译为汇编代码

汇编

将汇编代码转换为机器指令

链接

将目标文件生成装入模块，此时才有逻辑地址

装入

将装入模块装入内存，此时才形成物理地址

三种装入策略

绝对装入

如果编译器知道程序会装入的内存地址
编译器可以直接产生绝对的目标代码

一般由编译器完成，单道程序阶段，还没有OS的概念

可重定位装入
(静态重定位)

装入内存时，由OS根据实际装入地址，
将所有逻辑地址重定位为物理地址

装入内存时，必须一次性分配要求的空间
不能分配时，不能装入该作业

适用于早期多道批处理系统

动态运行时装入
(动态重定位)

运行程序过程中，当需要访问地址时，
将逻辑地址和起始地址相加得到物理地址

需要一个重定位寄存器，存放装入模块存放的起始位置

允许程序在内存中移动

可将程序离散地分配到存储区中

可以向用户提供比存储空间大得多的地址空间

三种链接策略

静态链接

运行前将目标模块和所需库函数
连接成完整可执行文件

装入时动态链接

在装入内存时链接所有目标模块和所需库函数

运行时动态链接

运行时根据需要将模块调入内存并链接

内存空间分配与回收

任务

记录内存的分配情况

确定程序的装入位置

回收结束进程的资源

连续分配管理方式

单一连续分配
MS-DOS

内存分为系统区和用户区

进程独占用户区

不支持多道程序

不存在外部碎片，但是有内部碎片

分配了但没用到称为内部碎片

固定分区分配

用户区被分为了固定大小的分区

分区大小可以相等也可以不等

需要建立分区说明表

表项包含编号、大小、
起始地址、分配状态

实现简单、无外部碎片，有内部碎片

动态分区分配
可变分区分配

分区大小正好适合进程需要，动态建立分区

数据结构

空闲分区表

表项：分区号、大小、起始地址、状态

空闲分区链

结点结构：指向前后结点的指针
、分区大小、起始地址

空闲分区分配算法

首次适应
FirstFit

每次从低地址开始查找，找到第一个满足需求的空闲分区

低地址部分产生很多碎片

无需排序

临近适应
NextFit

在FirstFit的基础上，可将空闲分区排成循环链表

从上次查找结束的位置开始查找分区

可能导致本来可以利用的低地址小分区浪费，过早用完连续大空间

无需排序

最佳适应
BestFit

将空闲分区按递增排列，找到的第一个满足需求的空闲分区

每次分配，若产生碎片，需重新排序，有一定开销

大量产生碎片

最坏适应
WorstFit

将空闲分区按递减排列，找到的第一个满足需求的空闲分区

每次分配，若产生碎片，需重新排序，有一定开销

对大进程不友好

有外部碎片：内存中空闲分区因太小而无法利用

可以通过“紧凑技术”（挪一下）解决

紧凑时需要修改PCB中的起始地址

分区的分配策略和回收策略如何

回收时，注意空闲分区的合并
不允许出现相邻的空闲分区

非连续分配管理方式
(离散分配管理方式)

基本分页存储管理

背景

块式存储要求数据必须存放在连续的物理块中，这导致了主存利用率的下降

物理块有别称

页框

页帧

物理页面

将进程分为与物理块等大的“页面”(页)，并进行编号，允许离散地存储到主存中
页对用户不可见。

页表（慢表）

页表项

记录逻辑页号和主存块号的对应关系

逻辑页号:主存块号

由于页表项连续存放，页表项的逻辑页号不占字节

页表基址X，页号为i的页表项地址为X+size*i

主存块号不是起始地址，addr=sizePage*块号

通常以页表基址、页表长度形式存储在PCB中

页表项被访问时...
相当于一次访存(慢)

把该项对应的块放入Cache

把该项放入快表

快表TLB
SRAM
相联存储器
专用硬件

快表项

逻辑页号:主存块号

查询成功(命中)...

直接得到主存块号

只需最终访存一次

与Cache的区别

Cache存主存块的副本

快表存页表项的副本(很小)

替换

两级页表
页表的页表
(页目录表)

单级页表的问题

页表很大，占据很多连续页框

基于局部性原理，没必要所有页表都常驻内存

虚拟存储技术

页表项增加一项是否调入内存

缺页中断

将页表拆分为页面，为页面再建立一层页表

又称外层页表、顶级页表

地址结构可以进一步拆分为：一级页号、二级页号、页内地址

多级页表的大小均不能超过一个页面

n级页表访存次数为n+1（不使用TLB）

地址转换

A的物理地址=页面P页号*页面大小+页内偏移量W

页号=

若页面大小为2的n次幂，则地址末n位
为页内地址(偏移量)，其余部分为页号

基本分段存储管理

根据自身逻辑将程序划分为若干(不等大的)段，按段名区分
段名对用户可见，需要显式地给出段名，是二维的编址方式

每段自0编址

允许

LOAD 1,[D]|<A>;

[D]→段号；<A>→段内地址

STORE 1,[X]|<B>;

段内地址长度决定段大小，段号长度决定段数

段表

段表项
对应一个段

段号

默认存在，不占空间

段长

各有不同，必须记录

段基址

地址转换

A的物理地址=逻辑段的段基址+段内地址

单级页表只需要两次访存

一定需要检查地址是否越界

段内地址超出段长则产生越界中断

通过将不同段表的段表项设为相同基址，可以简单地共享代码段

段页式存储管理

背景：分段/分页的优缺点

分页

空间利用率高，无外部碎片，少量页内碎片

不便于按照逻辑模块实现信息共享、保护

分段

段长若过长，为其分配连续空间非常不便
产生外部碎片

信息共享，保护实现简单

分段和分页的结合

先分段，再对段进行分页

地址结构：段号+页号+页内偏移量

段表/页表

段表项：段号(隐含)、页表长度、页表基址

一个进程可能多个页表

页表项：页号(隐含)、块号

用户只需要提供段号和段内地址，页号和页偏移量是自动计算的

地址转换

A的物理地址=逻辑段基址+页地址+页内偏移量

段号和页号都要检查是否越界

不使用快表，需要访存3次

使用快表，只需访存一次