Version: Next
内存管理
操作系统要在内存层面管理啥：
- 负责 内存空间的分配与回收
- 内存空间的扩展——虚拟内存技术
- 地址转换：让程序员只关注逻辑地址，而逻辑地址到物理地址的转换由操作系统负责
- 绝对装入：编译时产生绝对地址（编译器完成、当年还没操作系统）
- 可重定位装入：装入时将逻辑地址转换为物理地址（早期多道批处理操作系统）
- 动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位寄存器（现代操作系统）
- 内存保护：不能越界访问、不同进程之间不能互相侵入彼此的内存空间，更不用说操作系统本身也是在内存上跑的，不能被别人乱访问。通过
重定位寄存器和界地址寄存器实现 -> 相当于基址+变址
内存空间扩充技术
覆盖（不咋用了）
程序的大小远超计算机实际物理内存的大小
- 将程序分为多个
段（模块）：常用的段常驻内存，不常用的在需要时调入内存- 内存中分为 一个
固定区和 若干个覆盖区- 需要常驻内存的段放在
固定区中，调入后就不再调出(除非运行结束)- 比方说
if - else中分别调用了一个方法，那么可以用较大的那个方法申请内存空间，因为它们两个方法不会同时执行，就节省了空间- 从
物理内存的角度看，就好像物理内存被扩展了- 缺点：操作系统无法提前知道程序的这种调用结构，必须由程序员提前声明，对用户不透明，增加了编程负担
交换（对换）
思想：当内存空间紧张时，系统将内存中某些进程暂时
换出到外存，把外存中某些已具备运行条件的进程换入内存（进程在内存和磁盘间动态调度）
- 对应操作系统中级调度：进程挂起到磁盘上
在磁盘的什么位置存储被换出的进程
- 具有对换功能的操作系统中，通常把磁盘空间分为
文件区和对换区两部分
文件区：主要用于存放文件，主要追求存储空间利用率，因此对文件区空间的管理采用离散分配方式对换区：空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。主要追求换入换出速度，因此通常采用连续分配方式（文件管理知识）- 对换区的 IO 速度比文件区快
什么时候交换
- 内存吃紧、系统负荷大时
应该换出哪些进程
- 可优先换出阻塞进程
- 可换出优先级低的进程
- 为了防止优先级低的进程再重新调入内存后又很快被调出，有的操作系统还会考虑进程在内存中的驻留时间
- PCB 必须常驻内存
虚拟存储技术
看之后的笔记
内存空间的分配与回收
连续分配管理方式
分类
- 连续分配管理方式
- 非连续管理分配方式
- 基本分页存储管理
- 基本分段存储管理
- 段页式存储管理
单一连续分配（老古董）
该方式下：内存被分为
系统区和用户区
- 系统区通常位于内存低地址部分，用于存放操作系统相关数据
- 用户区用于存放用户进程相关数据
- 同一时刻，内存中只能有
一道用户程序，用户程序独占整个用户区空间
固定分区分配
划分固定大小的分区
- 每个分区中只能装入一道作业
- 最早、最简单的一种可运行多道程序的内存管理方式
- 也可以 将分区大小设置为不相等的：则需要用
分区说明表来实现各个分区的分配和回收，每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）- 实现简单，
无外部碎片；程序太大时，只能用覆盖技术解决，会产生内部碎片
动态分区分配
又称
可变分区分配
- 不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的
- 用什么数据结构记录内存使用情况？哪些空闲空间应当优先分配？如何进行分区的分配与回收？
空闲分区表或空闲分区链，记录了分区号、分区大小、起始地址、状态- 四种动态分区分配算法
- 在空闲分区表上做操作，增删改
内部碎片与外部碎片
动态分区分配没有内部碎片，但有外部碎片
- 内部碎片：分配给某进程的内存区域中，有些部分没用上
- 外部碎片：内存中某些空闲分区由于太小难以利用（标记清除算法的那种碎片），解决就是用标记整理，在操作系统术语中叫做 紧凑/拼凑
四种动态分区分配算法
如果当前存在多个分区都能满足需求，应当选择哪个分区进行分配
首次适应算法（First Fit）
- 思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
- 实现：空闲分区以地址递增的方式排序。每次分配内存时顺序查找
空闲分区表，找到第一个空闲分区即可最佳适应算法（Best Fit）
- 思想：为了保证
大进程到来时能找到连续的大片空间，可以尽可能多地留下大片的空闲区域，即先把较小的空闲区分配出去- 实现：空闲分区以容量递增的方式排序。每次分配内存时，顺序查找
空闲分区表，找到大小能够满足要求的第一个空闲分区- 缺点：会产生越来越多的内存外部碎片
最坏适应算法（Worst Fit）
- 思想：为了解决
最佳适应算法产生的大量内存外部碎片，可以在每次分配时优先使用最大的连续空间- 实现：空闲分区以容量递减的方式排序
- 缺点：大进程容易找不到足够的连续内存空间
邻近适应算法（Next Fit）
- 思想：首次适应算法每次都从链头（表头）开始查找，可能会导致低地址部分出现很多零碎空闲分区，而每次查找时都要经过这些分区。如果每次都从上次查找结束的位置开始检索，就能解决上述问题
- 实现：空闲分区以地址递增的顺序排列（可用一个循环链表）。每次分配内存时，从上次查找结束位置开始查找，找到大小能满足要求的第一个空闲分区
- 缺点：无论低地址、高地址的空闲分区都有相同的概率被使用，可能导致整个内存上都存在零碎外部碎片，导致连续的大内存空间变少
| 算法 | 思想 | 分区排列顺序 | 优点 | 缺点 |
|---|---|---|---|---|
| 首次适应 | 从头到尾找合适分区 | 地址递增 | 综合性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序 | |
| 最佳适应 | 优先使用更小的分区，保留大分区 | 容量递增 | 大片连续内存 | 产生很多外部小碎片，算法开销大，回收分区后可能需要对空闲分区队列重新排序 |
| 最坏适应 | 优先使用大分区 | 空间递减 | 可以减少零碎的小内存空间 | 大分区容易被用完，不利于大进程，算法开销大 |
| 邻近适应 | 首次适应的变种，每次从上次查找结束的位置开始查找 | 地址递增+循环结构 | 不用每次都从低地址小分区开始检索，算法开销小 | 会使高地址的大分区也经常被使用，整个内存上的连续大内存减少 |
连续分配方式的缺点
固定分区分配的缺点
- 缺乏灵活性，产生大量内部碎片，内存利用率很低
动态分区分配的缺点
- 产生外部碎片，虽然可以用
紧凑（整理）算法处理，但是时间代价很高连续分配方式缺点的本质
- 规定了进程在内存中的存储必须是
连续的- 解决：如果能将进程分散的装入到内存的不相邻区域，就能更加充分的利用内存空间，无需再进行整理操作
非连续分配管理方式——基本分页存储管理
为用户进程分配分散的内存空间
对固定分区分配进行改造
- 假设固定分区分配一个区域的大小为 10MB
- 对于一个 23MB 的进程，则可以将其拆分为 10MB、10MB、3MB，然后分开存储到固定分区分配的分区中（这些分区不必连续）
- 但 3MB 的区域会产生 7MB 的内部碎片
- 可以进一步缩小固定分区的大小，就能减少内部碎片的大小
- 这就是基本分页存储管理的思想——把内存分为一个个相等的小分区，再按照分区大小把进程拆分为一个个小部分
基本分页存储管理的概念
- 将内存分区分为一个个 大小相等的分区
- 每个分区称为一个
页框或页帧、内存块、物理块- 每个
页框有一个编号——页框号（内存块号、页帧号、物理块号）页框号从0开始- 对于用户进程：
- 将用户进程的地址空间分割为与页框大小相等的一个个区域，称为
页、或页面- 每个页面也有编号，即
页号，从0开始- 一个进程的最后一个页面，可能并没有页框那么大，因此页框不能太大，否则就会产生内部碎片
- 操作系统 以页框为单位为每个进程分配内存空间。进程的每个页面分别存入一个页框中
进程的页面与内存的页框一一对应- 各个页面不必连续存放，也不必按先后顺序，可以放到不相邻的页框中
地址转换（思想：为什么页大小要区 2 的次幂）
将进程地址空间
分页后，操作系统该如何实现逻辑地址到物理地址的转换？
- 基址变址寻址
- 假设每
页大小为 50B；逻辑地址为 80 的单元应当在 页面1 中；页面1 的起始地址为 450，则逻辑地址为 80 的内存单元应当对应 页面1 中偏移量为 30 的内存单元
- 逻辑地址 / 页大小 = 页号（再去找到对应页的页框号（内存块号））
- 逻辑地址 % 页大小 = 偏移量
- 基于二进制的简易计算方法
- 取
页大小为2的次幂- 对于二进制表示的逻辑地址
- 低位就是页面内的偏移量，对于
2 的 K 次幂字节的页大小，末尾 K 位就是偏移量- 剩余高位就是页号
- 确定页号对应的起始地址——
页表
- 为每个进程创建一个页表；进程的每一页对应一个页表项；每个
页表项由页号和块号（页框号）组成- 页表记录
进程页面->实际内存块（页框）之间的对应关系- 每个页表项的长度相同，页号是隐含的
- 假设某系统物理内存大小为 4GB、页大小为 4KB，则每个页表项至少应该为多少字节？
- 2^32 / 2^12 -> 2的20次方 -> 20bit
- 16 < 20 < 24，因此至少需要 24bit -> 3字节 —— 每个页表项 3 字节
- 各个页表项（对应一个页框）在内存中连续存放，则假设
整个页表的起始地址= X，那么M 号页对应的内存地址为X + 3M，即页表项（页框实际起始地址）地址=页表起始地址+页号*页表项长度（页框大小）注意：一般的计算机内存以 1个字节即 8bit 为最小单元- 对于有 n 个页的用户进程，则该进程的页表总空间为 3n 字节
- 页表本身的存储也是在分页管理方式下的，如果页框大小为 4K，一个内存块号需要 3字节 表示，那么一个页框可以存放 4096 / 3 = 1365 个页表项（内存块号）又因为 4096 % 3 = 1，不能整除，会产生 1 字节碎片，所以实际中会用
4字节表示一个内存块号，这是为了查询页表方便，4096 / 4 = 1024 可以整除
基本地址变换机构（硬件）
用于实现逻辑地址到物理地址转换的一组硬件机构
- 可借助
页表将逻辑地址转换为物理地址- 通常会在系统中设置一个
页表寄存器 PTR Page Table Register
- 存放页表在内存中的
起始地址F和页表长度M- 进程未执行时，页表的起始地址、页表长度 存放在
进程控制块 PCB中；进程被调度时，操作系统内核将它们加载到页表寄存器中- 找到内存块号后，最终的物理地址 = 页框号 * 页大小 + 偏移量，在 二进制计算机下，可以通过
内存块号（页框号）拼接页面内偏移量形成一个新的二进制地址实现，结果就是最终物理地址
例：页面大小 1K 字节，页号2 对应内存块号为 8，将逻辑地址 2500 转换为物理地址
- 2500 = 2048 + 452 -> 页面2 偏移 452 单元
- 8 1k + 452 = 8k + 452 = 1024 8 + 452 = 8644
- 建议计算法：8 拼上 452 -> 1000 _ 01 1100 0100B -> 8644D
具有快表的地址变换机构
- 局部性原理
- 比如用循环体频繁访问一个数组或者集合，那对应的代码段和数据段就会被频繁访问
- 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能再次执行；对于数据同理
- 空间局部性：一旦程序访问了某个内存单元，那么在不久之后，其附近的存储单元也很有可能被访问
- 什么是
快表TLB
- 又称为
联想寄存器 TLB，是一种 访问速度比内存快很多 的告诉缓存寄存器，用来存放当前访问的若干页表项，以加速地址转换的过程，相应的，内存中的页表常称为慢表- 引入快表后，地址的变换过程
- 快表命中，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元 -> 若快表命中，则访问某个逻辑地址
仅需一次访问即可- 快表未命中，则需要访问内存中的页表（慢表），找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，则访问某个逻辑单元需要
两次访问，找到页表项后，应同时将其存入快表，以便后面可能的再次访问，但若快表已满，则必须按照一定的算法对旧的页表项进行替换- 由于查询快表的速度比查询页表的速度快很多（缓存 VS 内存），因此只要命中快表，就可以节省很多时间
- 根据局部性原理，快表的命中率一般
> 90%- 例：假设某系统使用基本分页存储管理，并采用具有快表的地址变换机构，访问一次快表耗时 1us，访问一次内存耗时 100us，若快表命中率为 90%，那么访问一个逻辑地址的平均耗时为多少？
- 默认的两种情况：一次快表 -> 访问最终物理地址 或者 快表未命中 -> 内存去查慢表 -> 慢表项目更新到快表 -> 访问最终物理地址
- (1 + 100) x 0.9 + (100 + 1 + 100) x 0.1 = 111
- 对于慢表快表查询同时开始的系统，则 (1 + 100) x 0.9 + (100 + 100) x 0.1 = 110.9
- 对比：对于没有快表的系统，访问一个逻辑地址对应的物理内存地址耗时必定为 100+100=200us
地址变换过程 访问一个逻辑地址的访问次数 基本地址变换机构 1.算页号、页内偏移量
2.检查页号合法性
3.查页表，找到页面存放的内存块号
4.根据内存块号与页内偏移量得到物理地址
5.访问目标内存单元两次访问 具有快表的地址变换机构 1.算页号、页内偏移量
2.检查页号合法性
3.查快表，若命中即可知道页面存放的内存块号，直接跳到5.
4.未命中，查页表，找到页面存放的内存块号，并将页表项复制到快表中
5.根据内存块号与页内偏移量得到物理地址
6.访问目标内存单元快表命中，只需 一次访问
快表未命中，需要两次访问
两级页表
单级页表存在的问题
- 对于支持 32位 逻辑地址，采用分页存储管理，页面大小 4KB，页表项长度为 4B 的计算机
- 问题一：需要为每个进程专门分配
2 ^ 10 = 1024个连续的页框来存放它的页表，即连续的 4MB 空间，页表要求的内存空间，可能分配不出来- 问题二：根据局部性原理，很多时候，进程在一段时间内只需访问某几个页面就可以正常运行，没有必要让整个页表常驻内存（在需要访问页面时才把页面调入内存——
虚拟存储技术）
两级页表的原理、逻辑地址机构
- 将页表分组，使每个内存块刚好可以放入一个分组
- 例如：对于页面大小 4KB、每个页表项 4B，每个页面可存放 1K 个页表项，因此每 1K 个连续的页表项为一组，每组正好占用一个内存块（页框），再将各组离散的存放到各个内存块中）
- 由此，需要为离散分配的页表再建立一张页表（页表的页表），称为
页目录表、或外层页表、顶层页表
两级页表访问需要注意的细节
- 若采用多级页表机制，则各页表的大小不能超过一个页面
- 例：假设某系统按字节编址，采用 40 位逻辑地址，页面大小为 4KB，页表项大小为 4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位
- 先看第二空：4KB = 2^12 -> 12位
- 再看第一空：每个页面可以存放的页表项： 4KB / 4 = 2^12 / 2^2 = 2^10 = 1024 个页表项
- 各级页表的大小不能超过一个页面（本题 4KB，即不能超过 1024 个页表项）
- 40位 - 12位 -> 28位用来表示页号，12位表示页内偏移量
- 问题转换为： 2^28 需要几个 2^10 相乘，显然 需要3个 2^10 相乘达到 2^30 的空间范围 ->
三级页表，并且将 28 位表示的页号分为一级页号 8bit，二级页号 10bit，三级页号 10bit- 两级页表的访存次数分析（假设没有快表机构）
- 第一次访问：内存中的顶级页表（页表的页表 或称 页目录表）
- 第二次访问：访问内存中的二级页表（还可以继续套娃）
- 第三次访问：访问目标内存单元
- 结论：多级页表的访存次数（无快表机构） -> N 级页表需要 N+1 次访存
非连续分配管理方式——基本分段存储管理
与
分页最大的区别在于——离散分配时所分配地址空间的基本单位不同
分段与段表
分段
- 进程的地址空间：按照程序 自身的逻辑关系划分为若干个段，每个段有一个
段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编制- 内存分配规则：以
段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻- 为了编程方便，使用的是
段名编程；在编译期间段名被转换为段号，计算机实际使用段号实现物理内存的访问- 最终：逻辑地址由
段名+段内地址（偏移量）组成（如 32 位计算机，假设 16-32 位表示段号，0-15 为表示偏移量）注意
- 段号的位数决定了每个进程最多可以分多少段
- 段内地址位数决定了每个段的最大长度
例：对于 32位 计算机，若系统按字节寻址，则段号 16bit，因此系统中每个进程最多有 2^16 = 64K 个段，每个段内最大长度为 2^16 = 64KB
段表
- 程序分多个段，各段离散的装入内存，需要能从物理内存中找到个逻辑段的存放位置，因此需要为每个进程建立一张段映射表：
段表- 每一个段对应段表中的一个段表项，其中记录了该段在内存中的
起始位置（基址）和段长- 结构：段号 | 段长 | 基址
- 段表项的长度是相同的
- 例：假设逻辑地址结构为 段号16bit、段内16bit，因此用 16bit 可以表示最大段长；物理内存 4GB （32bit 可以表示完），因此让每个段表项占 16 + 32 = 48bit，即 6B
- 由于段表项长度相同，因此 段号可以隐含，不占存空间
- 若段表存放的起始地址为 M，则 K 号段对应的段表项存放的地址为 M + 6*K
分段、分页管理对比
页是信息的物理单位：分页的主要目的是为了实现离散分配，提高内存利用率，分页仅仅是操作系统管理上的需要，完全是系统行为，对用户不可见段是信息的逻辑单位：分段的主要目的是为了更好的满足用户需求，一个段通常包含一组属于一个逻辑模块的信息，分段对用户是可见的，用户编程时需要显示地给出段名
- 页的大小固定且由系统决定，段的长度不固定，决定于用户编写的程序
分页的用户进程 地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址分段的用户进程 地址空间是二维的，程序员在标识一个地址时，要给出段名+段内偏移量
分段比分页更容易实现信息的共享和保护
- 共享：
- 不同进程的段表中，放一个相同的段表项，指向相同的段；
- 对于分页，一段在逻辑上为整体的代码（比如一个生产者代码），可能会被一分为二存到两个不同的页上，要共享就得共享两个页，但两个页上还存在其他代码（逻辑上分离，物理上耦合）
- 保护：类似
访问一个逻辑地址需要的访存次数
分页（单级页表）：两次
- 第一次：查询内存中的页表
- 第二次：访问内存单元
分段：两次
- 第一次：访问内存中的段表
- 第二次：访问内存单元
与分页类似，可以引入
段表快表机构，将近期访问过的段表项存入快表中，这样可以只访问一次
非连续分配管理方式——段页式存储管理
分页、分段方式的最大优缺点
| 优点 | 缺点 | |
|---|---|---|
| 分页 | 内存利用率高，不会产生外部碎片，只会有少量页内碎片 | 不方便按逻辑模块实现信息共享、保护 |
| 分段 | 很方便按照逻辑模块实现信息共享、保护 | 如果段长过大，为其分配连续内存空间不方便，并且容易产生外部碎片 |
分段 + 分页
将进程按照逻辑模块分段，再将各个段分页
- 逻辑地址结构：
31 - 16 16 - 12 11 - 0 段号 页号 页内偏移量
- 相当于把
分段的段内偏移量拆分为页号 + 页内偏移量注意
- 段号的位数决定了每个进程最多可以分几个段
- 页号位数决定了每个段最大有多少页
- 页内偏移量决定了页面大小、内存块大小是多少
- 段页式中：
分段对用户是可见的；分页对用户不可见，系统根据段内地址自动划分页号和页内偏移量
段页式管理的地址结构是二维的
段表、页表
段表
- 每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表其实地址）组成，每个段表项长度相等，段号是隐含的
页表长度（前一列段号隐藏） 页表存储块号（内存块、页框） 2 1 ... ...
- 通过段表内的页表存储块号，找到对应页表
页表
内存块号（前一列页号隐藏） h
- 假设某段，段长为 7KB，计算机分页的页大小为 4KB，那么这个段中就有两个页，一个 4KB、一个 3KB：页表的长度取决于段的长度，不同的段长度不同，所以对应的页表长度不同
- 正常需要访问三次内存，如果引入快表机制，依然只需要访问一次