MindMap Gallery 第三章-内存管理
操作系统详细思维导图,内存管理的基本原理是程序的装入和链接、逻辑地址空间与物理地址空间、内存保护,本图适合计算机相关专业期末复习,考研学习等。
Edited at 2023-10-11 11:40:19Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Projektmanagement ist der Prozess der Anwendung von Fachwissen, Fähigkeiten, Werkzeugen und Methoden auf die Projektaktivitäten, so dass das Projekt die festgelegten Anforderungen und Erwartungen im Rahmen der begrenzten Ressourcen erreichen oder übertreffen kann. Dieses Diagramm bietet einen umfassenden Überblick über die 8 Komponenten des Projektmanagementprozesses und kann als generische Vorlage verwendet werden.
Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Projektmanagement ist der Prozess der Anwendung von Fachwissen, Fähigkeiten, Werkzeugen und Methoden auf die Projektaktivitäten, so dass das Projekt die festgelegten Anforderungen und Erwartungen im Rahmen der begrenzten Ressourcen erreichen oder übertreffen kann. Dieses Diagramm bietet einen umfassenden Überblick über die 8 Komponenten des Projektmanagementprozesses und kann als generische Vorlage verwendet werden.
第三章-内存管理
1. 内存管理的基本原理
i. 程序的装入和链接
源程序到可执行程序的过程(以c为例)
I. 预处理
file.c文件经预处理器处理形成file.i文件(文本文件)
II. 编译
file.c文件经编译器处理形成file.s文件(文本文件)
III. 汇编
file.c文件经汇编器处理形成file.o文件(目标文件,二进制)
IV. 链接
将file.o文件和使用的其它系统静态库由链接器链接成可执行文件
主要完成重定位,即整个程序的完整逻辑空间
链接
1. 静态链接
程序运行前,就将各目标模块及他们所需的库函数链接成完整可执行程序
2. 装入时动态链接
目标模块在装入过程中,采用边装入边链接的方式
3. 运行时动态链接
某些目标模块,只有在程序运行时需要时才链接
程序的装入方式
绝对装入方式
编译时直接将程序的符号地址转换成绝对地址,特点就是程序的逻辑地址与物理地址完全相同,因此不需要修改程序和数据的地址
缺点
只适用于单道程序环境
可重定位装入
重定位
装入模块在内存空间的起始地址一般不会是0,此时就必须将装入模块的指令和数据的相对地址调整成相应内存单元的绝对地址(逻辑地址 目标模块在内存的始址)
静态重定位
重定位发生在装入时,由重定位装入程序一次性完成
特点
1. 作业装入内存时必须分配足够的内存空间,否则不能装入
2. 作业一但装入内存,整个运行期间不在移动,也不能再申请空间
动态运行时装入
也称动态重定位
程序若需在内存中发生移动,则需要动态装入方式
装入程序将装入模块转入内存后,并不立即将装入模块的相对地址转换为绝对地址,而是在程序真正执行时才进行。因此装入内存后的所有程序均是相对地址
需要重定位寄存器(硬件)的支持
存放装入程序的基址
也称基址寄存器
物理地址=寄存器值 相对地址
特点
1. 可以不连续存放程序
2. 程序运行前装入部分代码即可运行,程序执行期间可按需动态申请分配内存
3. 便于程序共享,可以为用户提供一个比存储空间大得多的地址空间
ii. 逻辑地址空间与物理地址空间
逻辑地址空间
逻辑地址(相对地址)
编译后,每个目标模块都是从0开始编址的
链接时顺序将所有模块的相对地址链接成从0开始的新的地址空间
物理地址空间
物理地址
程序和数据在内存中的唯一位置标识
进程运行时执行指令和数据必须使用物理地址从内存(主存)获取
可执行程序装入内存时,必须将逻辑地址转换成物理地址(地址重定位)
内存中物理单元的集合即物理地址空间
iii. 内存保护
设置上下限寄存器
通过重定位寄存器和界地址寄存器(记录进程最大逻辑地址)进行越界检查
2. 管理方式
i. 内外碎片
内碎片
也称内零头
给多少,用多少,没用完,剩下小的就是内碎片
如单一连续分配和固定分区分配
外碎片
也称外零头
用多少,给多少,剩太小,没法用的就是外碎片
如动态分区分配
ii. 连续分配
1. 单一连续分配
系统区与用户区
系统区
仅供OS使用,通常在低地址部分
用户区
优点
1. 无外碎片
2. 可使用覆盖技术
3. 不需要额外内存支持
缺点
1. 有内碎片
2. 适用于单用户,单任务的OS
3. 存储器利用率极低
2. 固定分区分配
将用户内存空间划分为固定大小(可等可不等)的区域,每个分区只装入一道作业
优点
1. 无外碎片
2. 最简单的多道程序存储管理方式
3. 适用控制多个相同对象的控制系统
缺点
1. 有内碎片
2. 程序可能太大而放不下任何一个分区
3. 主存利用率极低
3. 动态分区分配
也称可变分区分配
进程装入时才根据大小动态建立分区,使分区大小适合进程
特点
有外碎片产生
可通过紧凑技术(时不时的对进程进行移动和整理)解决
但需要基址寄存器
动态分区分配策略
1. 首次适应算法
按照空闲分区始址递增的方式排列,从小到大选择首个满足要求的空闲区
特点
不仅最简单,通常也是最好最快的
2. 最佳适应算法
按照空闲分区大小递增的方式排列,从小到大选择首个满足要求的空闲区
特点
需要排序,需要记录空闲分区大小
3. 最坏适应算法
按照空闲分区大小递减的方式排列,从大到小选择首个满足要求的空闲区
特点
需要排序
4. 循环首次适应算法
在首次适应算法的基础上,分配内存时从上次查找结束的位置开始
iii. 非连续分配
1. 基本分页
i. 特点
作业运行时需要全部调入内存才能运行(请求分页作业部分调入即可运行)
ii. 基本思想
将主存空间划分为固定大小的块,作为主存的基本单位。进程以块为单位进行划分,执行时以块为单位申请块空间
特点
只会在存放最后一块的数据时才产生页内碎片
iii. 基本概念
I. 页面和页面大小
页
进程中的块
页框,页帧
均指内存中的块
外存也以同样的方式划分,直接称块
页面大小
页面大小应是2的整数幂
方便地址转换
页面大小应适中,不能太大也不能太小
II. 地址结构
页号(12~31)
地址空间最大允许的页数2^(20)
页内偏移(0~11)
页大小为2^(12)B
注意事项
页号和页内偏移对用户完全透明
虚拟内存的寻址空间只由地址结构(地址寄存器位数)决定,与内外存容量,计算机字长等无关
III. 页表
每个页表项记录了每个页面对应的物理块号
(页号到物理块号的映射)
一般存放在内存
iv. 基本地址变换机构
1. 变换过程
i. 首先将逻辑页号与页表寄存器中的页表长度进行比较,不小于发生越界中断
ii. 其次根据页表寄存器中存放的页表始值找到页表
iii. 再通过页表找到逻辑页号对应的物理块号
iv. 最后通过物理块号和页内偏移相加即得物理地址
2. 注意事项
页地址空间是一维的
只需给出一个整数就能确定物理地址
v. 具有快表的地址变换机构
1. 快表
基本原理
程序的局部性原理
时间局部性
当前被访问的指令,可能马上又要被访问
典例
循环结构
空间局部性
当前访问的指令,其后面的指令可能马上要访问了
典例
程序的顺序执行
高速缓冲存储器,又称相联存储器(TLB)
用来存放当前访问的若干页表项,加速地址变换过程
慢表
主存中的页表
2. 引入快表后的地址变换过程
i. 首先将逻辑页号与快表中的项进行比对,若命中,直接转换
ii. 否则重复基本地址变换机构的变换过程
iii. 注意
访问到内存中页表的页表项后,还需要将其写入到快表当中
若快表已满,则需按置换算法淘汰某项,再装入
iv. 简单计算过程
若命中率为a,访问内存时间为T,访问快表时间为t
平均访问时间avg=a*t (1-a)(T t) T
3. 注意
有些处理机是快表和满表同时查找,若快表中命中则直接终止慢表的查询
vi. 多级页表
需求背景
当进程的逻辑空间较大时,此时的页表也就变得非常的大了,此时就必须为页表再建立页表。即外层页表(下面以两级页表为例进行分析)
两级页表
基本结构
每一个页表项存放的就是各一级页表的的物理块号
硬件要求
需要一个外层页表寄存器来存放两级页表的内存始址和长度
规定
为查询方便,顶级页表最多只能有一个页面
逻辑地址
二级页号
用于找到一级页表的物理块号
一级页号
用于找到对应页的物理块号
页内偏移
优点
1. 加快检索速度
2. 不用存储无用页表项
3. 不用顺序式查找页表项
N级页表特点
N级页表存放的是N-1级页表的位置
N级页表长度不超过一页
2. 基本分段
i. 初衷
为提高内存利用率,方便用户(编程,信息共享与保护,动态增长与动态链接)
ii. 分段
按用户进程中的自然段划分逻辑空间
基本要求
划分段数与用户进程段数一致
每段从0开始编址,分配连续的地址空间
特点
段内有序,段间无序
iii. 段表
每个进程对应一个段表,记录各段在内存中的位置
组成
(段号)
段长
段始址
地址变换机构
1. 变换过程
i. 首先将段号(S)与段表寄存器的段长进行比较,不小于发生越界中断
ii. 然后根据段表寄存器的段始址找到段表位置
iii. 再根据逻辑段号在段表找到对应段的基地址
iv. 最后将段基址b与段内偏移W相加即得物理地址E
2. 硬件支持
段表寄存器
段始址(F)
段长(M)
3. 注意事项
地址空间是二维的
段号(S)
决定段数(2^S)
段内偏移(M)
决定段大小(2^M)
段号和段内偏移必须由用户显式提供(高级语言中由编译程序完成)
(因为段长不确定)
iv. 段共享
两个进程的段表中相应表项指向同一物理空间实现共享
因此,当某个进程在读取段中数据时,必须防止另一进程修改
可重入代码(纯代码)
不能修改的代码
(不属于临界资源)
可反复执行
不能修改的数据和纯代码可以共享
v. 段保护
存取控制
地址越界
若在某一段中,段偏移大于段长,发生越界中断
若段号不小于段长
发生越界中断
3. 段页式
i. 地址结构
1. 段号
2. 页号
3. 页内偏移
ii. 地址变换过程
i. 首先通过段表查到页表始址
ii. 然后通过页表查到页帧号
iii. 由页帧号和页内偏移合成物理地址访存
iii. 硬件支持
段表寄存器
iv. 特点
进程地址空间首先被分成若干逻辑段,每段都有自己的段号,然后将每段分成固定大小的页
内存空间则与分页管理方式一致,分成若干与页面大小相同的存储块,对内存分配以块为单位
每个进程有一张段表,每个段有一张页表
v. 注意事项
地址空间是二维的
访问时必须给出段号和段内地址(实际上类似于分页的逻辑地址)
每次访问数据实际上经历了3次访存
3. 虚拟内存管理
1. 虚拟内存的基本概念
I. 传统存储管理方式的特点
i. 一次性
作业全部装入内存后才能运行
ii. 驻留性
作业装入内存后,就一直驻留在内存当中
II. 虚拟存储器的定义和特征
i. 多次性
作业可多次调入内存
ii. 对换性
允许作业在运行时将换入换出
与交换技术的区别
交换技术调入调出整个进程
(对换技术则只需调入调出某页或段)
iii. 虚拟性
逻辑上扩充内存容量(借助外存空间,显然对换性是其实现的基础)
III. 虚拟内存技术的实现
1. 实现条件
离散分配的内存管理方式
(连续方式导致的大部分内存空间处于空闲)
2. 硬件支持
一定容量的内存和外存
页表/(段表机制)
中断机构
(访问的部分尚未调入内存)
地址变换机构
逻辑地址到物理地址的映射
2. 请求分页
I. 特点
在基本分页管理的基础上,增加了请求调页,页面置换功能
只要求一部分作业调入内存,即可启动运行
II. 页表机制(新增字段)
i. 状态位
记录该页是否调入了内存
(访问时参考)
ii. 访问位(A)
本页被访问的次数或本页最近已有多长时间未被访问
(换出时参考)
iii. 修改位(M)
调入内存后是否被修改
(换出时参考)
iv. 外存地址
物理块号
(调入时参考)
3. 页面置换算法
I. 最佳置换算法(OPT)
换出最久将会使用的页
理想算法,没法实现
II. 先进先出(FIFO)
换出最先进入的页
(就算某页命中了也不影响其先来后到的时间)
Belady现象
(驻留集增大时,命中率反而降低)
(命中后调整换出次序)
III. 最近最久未用(LRU)
换出最久未使用的页
最接近OPT算法
硬件支持
寄存器
栈
IV. 时钟置换算法(CLOCK)
普通时钟置换算法
每帧增加一个使用位u
步骤
i. 刚开始系统会将页面连成一个循环队列,扫描指针指向第一个未被访问的页(这里是1号页)(初始时所有页的u=1)
ii. 依次扫描所有页,将所有页的u置0(因为此时没有u=0的页,没有页可换出)
iii. 第二轮扫描时,1号页的访问位为0,因此将一号页换出
改进型时钟置换算法
再增加一个修改位v
优先级(u>v)
优先级比较(u,v)
(0,0)<(0,1)<(1,0)<(1,1)
步骤
i. 第一轮扫描选择第一个u=0,v=0的帧替换掉
ii. 若i失败,则选择u=0,m=1的帧进行替换,并将跳过的帧的u=0
iii. 若ii失败,重复i和ii
4. 页面分配策略
驻留集
给一个进程分配的物理页框的集合
分配策略
1. 固定分配局部置换
给进程分配固定数目的物理块,使用期间不改变(固定分配)
缺页时只能从该进程的物理块中页面换出
2. 可变分配全局置换
除了给进程分配一定数目的物理块,OS自身也保留一定数目的物理块
某进程发生缺页时,OS可再多为其分配物理块
缺点
盲目给进程增加物理块,导致并发能力下降(系统内进程数目相对减少了)
优点
可以动态增加进程物理块
最易于实现
3. 可变分配局部置换
若进程频繁的缺页,OS可再为其分配若干物理块,直至缺页率稳定;若进程缺页率特别低,OS会适当减少分配给其的物理块(与可变分配全局置换不同之处)
注意事项
没有固定分配全局置换,因为固定分配就说明了进程的驻留集大小是固定的,无法改变
调入页面的时机
1. 预调页
运行前
优点
根据局部性原理,可以一次调入多页
2. 请求调页策略
运行时
缺点
每次只能调入一页
从何处调入页面
重要概念
文件区
离散分配
对换区
连续分配
因此磁盘I/O比文件区更快
何处
对换区空间足够
可全部从对换区调入
因此,进程运行前需将有关文件从文件区复制到对换区
对换区不足
只有文件不被修改,可直接从文件区调入;对于发生修改的部分,应当将他们换出时调到对换区(因为读比写快)
UNIX方式
与进程有关的文件都放在文件区,未运行过的页面都从文件区调入
5. 抖动
又称颠簸
刚被换出的页面马上又被换入内存(频繁的换入换出)
评判标准
若进程的换页时间高于执行时间,则就发生了抖动
主要原因
1. 驻留集太小,进程频繁访问的页数大于驻留集页数
2. 页面置换算法选用不当
6. 工作集
在某段时间间隔内,进程要访问的页面集合
计算上
就是工作集窗口中的不同页面集合
4. 覆盖与交换
1. 覆盖技术
i. 基本思想
i. 将用户空间划分为一个固定区和若干覆盖区。
ii. 覆盖区
放入即将要访问的段
其他放入外存,需要时再调入覆盖区,替换原有的段
iii. 固定区
放入经常活跃的段
iv. 缺陷
当同时运行的代码量高于主存时,仍不能运行
只能更新覆盖区的段,不在覆盖区的段常驻内存
v. 特点
用于同一进程或程序
现已被虚拟技术取代
2. 交换技术
i. 基本思想
换出
将处于等待态态的进程从内存移至辅存
换入
将准备好竞争CPU的进程从辅存移到内存
ii. 特点
用于不同进程或程序
仍普遍应用