内存空间的分配与回收

背景

1. 给进程分配内存空间，操作系统需要记录哪些内存区域分配出去了，哪些还空着；
2. 当进程运行结束后，操作系统如何回收内存空间

1.连续分配管理方式

1.1.单一连续分配

1. 内存只能有一道用户程序，内存分成2块，操作系统区和用户区，用户程序放在用户区
2. 没有外部碎片，因为分配的是整一块，干干净净，容不下第二道程序；但是有内部碎片，因为一道程序可能没那么大
3. 因为是只支持单道程序，可以采用覆盖技术扩充内存

1.2.固定分区分配

1. 支持多道程序，将内存用户空间（一部分是系统空间）划分若干个分区，每个分区只能装一道作业
2. 没有外部碎片，有内部碎片
3. 2种划分方式，分区大小相等，分区大小不相等

1.3.动态分区分配

1. 支持多道程序，在进程进入内存时，动态根据进程大小划分分区

2. 2种数据结构
   空闲分区表
   空闲分区链

3. 进程多大，分区就多大，所以没有内部碎片，但是有外部碎片
   外部碎片可以用紧凑技术解决，比如行李箱，东西放的乱七八糟，有很多碎片空间没办法利用，这个时候把行李箱的东西整理好，这块空间就能放物品了

4. 回收内存分区时，有4种情况
   情况一：回收区的后面有一个相邻的空闲分区
   情况二：回收区的前面有一个相邻的空闲分区
   情况三：回收区的前、后各有一个相邻的空闲分区
   情况四：回收区的前、后都没有相邻的空闲分区
   总之，相连的空闲分区要合并

5. 在动态分区分配方式中， 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
   首次适应算法first fit
   最佳适应算法best fit
   最坏适应算法worst fit
   邻近适应算法next fit

2.非连续分配管理方式

2.1.基本分页存储管理

概念：分页存储就是将内存空间分为一个个大小相等分区，同样进程的逻辑地址空间也是这样划分，然后把进程划分好的每个部分，也叫页或者页面放到内存空间，这样一来怎么知道进程的每个页存放在内存空间哪里呢，所以进程PCB需要记录一张映射表——页表，记录每个页的起始地址

问题1，怎么知道页表每个项占用多少字节
或者这样问，页表项最大的块号是多少
或者这样问，内存物理地址最大多少（内存空间是从0开始编号的）

知道内存大小（大面积）/内存块大小（小面积）=逻辑地址最大编号（个数）

问题2，如何实现地址转换

• 思考，连续分配，也就是进程在内存中连续存放时，操作系统是如何实现逻辑地址到物理地址的转换的
• 思考，非连续分配，也就是进程地址空间分页后，现在操作系统应该怎么实现逻辑地址到物理地址的转换

2.1.1.基本分页存储管理的基本概念

1. 基本分页存储管理的思想：把进程切块（分页），把内存也切块，大小相等，然后把页面塞进内存块中（离散：可以随便放，不用连续）
2. 容易混淆概念
   页框、页帧、内存块、物理块、物理页VS页、页面
   页框号、页帧号、内存块号、物理块号、物理页号VS页号、页面号
3. 页表
   • 页表记录了页面和实际存放的内存块之间的映射关系
   • 一个进程对应一张页表，进程的每一页对应一个页表项（即进程分多少页，页表项就有几项），每个页表项由页号和块号组成
   • 每个页表项的大小是相同的，页号是隐含的
   • i号页表项存放地址=页表开始地址+i*页表项大小（面积/容量）
4. 逻辑地址结构——可拆分为{页号P，页内偏移量W}
   • 页号=逻辑地址/页面大小
     如果知道页号有几位二进制，可以知道一个进程有多少页面
   • 页内偏移量=逻辑地址%页面大小
     如果知道页内偏移量有几位二进制，可以知道一个页面能装多少比特
   • 如果页面大小刚好是2的整数次幂呢？
     • 逻辑地址的拆分更加迅速——如果每个页面大小为 2KB，用二进制数表示逻辑地址，则末尾 K 位 即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为 2 的整数幂，计算机硬件就 可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。
     • 物理地址的计算更加迅速——根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内 存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。
5. 如何实现地址转换
   1. 给出逻辑地址
   2. 计算对应的页号，页内偏移量
   3. 查页表找到页号对应的内存块号
   4. 物理地址 = 页面开始地址+页内偏移量

2.1.2.具有快表的地址变换机构

1. 什么是快表TLB
   快表，又称联想寄存器（TLB， translation lookaside buffer ），是一种访问速度比内存快很多的 高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。 与此对应，内存中的页表常称为慢表。
   

2. 引入快表后，地址的变换过程
   ① CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
   ② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块 号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此， 若快表命中，则访问某个逻辑地址仅需一次访存即可。
   ③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块 号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此， 若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表， 以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）
   由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。 因为局部性原理，一般来说快表的命中率可以达到 90% 以上。

3. 局部性原理

   • 时间局部性
     如果执行了程序中的某条指令（访问数据），这条指令（访问数据）有可能马上又会被执行，例如程序代码中的循环
   • 空间局部性
     程序访问某个存储单元后，后面还会访问它附近的存储单元

4. 思考：能否把整个页表都放在快TLB中？
   造价贵，且页表太大没有必要
   既然存不下整个页表，可以选择淘汰一些页表

2.1.3.两级页表/多级页表

1. 单级页表（前面学习的）存在的问题

   • 问题一：所有页表必须连续存放，页表过大的时候面临同样的问题，内存需要划分连续空间，所以有两级分表、三级分表、无限套娃。。。

   • 问题二：在一段时间内并非所有页面都用得到，因此没有必要让整个页表常驻内存

     • 可以在需要访问页面调入内存（虚拟存储技术），然后在页表项添加一个标志位，用于表示该页面是否已经调入内存
     • 如果想要访问的页面不存在内存中，就产生缺页中断（内中断/异常），然后将目标页面从外存调入内存
2. 两级页表
   将页表再分页
   逻辑地址结构变成{一级页号，二级页号，页内偏移量}
   注意几个术语：页目录/外层页表/顶级页表
3. 如何实现地址变换
   1. 按照逻辑地址结构拆分3部分
   2. 从PCB中读出页目录表起始地址，根据一级页号查找页目录表，找到下一级页表在内存中存放的位置
   3. 根据二级页号查表，找到最后的内存块号
   4. 结合页内偏移量得到物理地址
4. 几个细节

   • 多级页表中，各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级（意思就是最后的页目录最好不要超过一个进程分页大小）

   • 多级页表访问内存次数，假设没有快表机构，——N级页表访问一个逻辑地址转换成物理地址需要N+1次访问内存

2.2.基本分段存储管理

1. 什么是分段

   • 内存分配规则，以段为单位进行分配，每个段在内存中占据连续空间，每个段之间不要求相邻

   • 由于是按照逻辑功能模块划分，用户编程更方便，程序的可读性更高

   • 分段系统的逻辑地址结构两部分组成{段号，段内偏移量}

     • 段号的位数决定了单个进程最多可以分成几段
     • 段内偏移量位数决定了每个段的最大长度是多少（内存块比特数）
2. 什么是段表
   • 因为程序代码分成多个段离散装入内存，需要一张表记录每个段（函数代码）的存放位置。另外每个段（函数代码）的长度不一样，也要显式记录
   • 段表的每个段表项长度是相同的，一个段表项大小怎么算呢，首先明确有两个值，一个是段长（看段号的位数有几位），一个是内存块地址（看物理内存多少位）
   • 段号是隐含的，不占存储空间
3. 如何实现地址转换
   0. 段表寄存器{段表的起始地址F，段表的长度M}
   1. 根据逻辑地址得到段号、段内地址
   2. 根据段表寄存器，判断段号是否越界，注意段表长度至少是1，段号是从0开始
   3. 查询段表，找到对应的段表项，当前要找的段表项在段表哪个位置（整个段表保存在内存）F+S*段表项长度（段表项面积）
   4. 段表中有段长（程序函数长度），检查段内地址与之对比是否越界，有则产生越界中断，否则继续执行
   5. 根据段表里的物理内存块地址+段内地址（段内偏移量）得到物理地址
   6. 访问目标内存单元
4. 分段、分页管理的对比
   • 分页对用户不可见，分段对用户可见
   • 分页的地址空间是一维的，分段的地址空间是二维的
   • 分段更容易实现信息的共享和保护（纯代码/可重入代码可以共享，不能被修改的代码称为纯代码或可重入代码）
   • 分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构

2.3.段页式存储管理

1. 分段+分页

   • 将地址空间按照程序自身的逻辑关系划分为若干个段，再将每个段分为大小相等的页面

   • 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存

   • 逻辑地址结构={段号，页号，页内偏移量}

   • 段号的位数决定每个进程最多可以分成几个段

     页号位数决定每个段最大有多少页

     页内偏移量决定了内存块大小是多少

2. 段表、页表
   • 每个段对应一个段表项，段表里的每个项长度相同，由段号、页表长度、页表存放地址组成
   • 每个页对应一个页表项，页表里的每个项长度相同，由页号、页面存放的内存块号组成
3. 如何实现地址转换
   1. 由逻辑地址得到段号、页号、页内偏移量
   2. 段号与段表寄存器中的段长度比较，检查是否越界
   3. 由段表起始地址、段号找到对应的段表项
   4. 根据段表中记录的页表长度，检查页号是否越界
   5. 由段表中的页表起始地址、页号查询页表找到对应页表项
   6. 由页面存放的内存块号、页内偏移量得到最终物理地址
   7. 访问目标单元
4. 访问1个逻辑地址所需访存次数
   • 第一次——查段表、第二次——查页表、第三次——访问目标单元
   • 可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅仅需要一次访存，因为快表不在内存

补充
连续分配意思是内存地址是连续的
非连续分配意思是可以给用户进程分配分散的内存空间