廖家龙的博客网站
内存空间的分配与回收
廖家龙 用心听，不照做
  2020-06-30 23:36:00   2024-07-19 09:49:39    3k 字  9 分钟

连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。

系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据，内存中只能有一道用户程序，用户程序独占整个用户区空间

优点：实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护（MS-DOS）

缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器利用率极低（分配给某进程的内存区域中，如果有些部分没有用上，就是“内部碎片”）

固定分区分配

动态分区分配

动态分区分配又称为可变分区分配，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的

假设某计算机内存大小为64MB，系统区8MB，用户区共56MB

  1. 系统要用什么样的数据结构记录内存的使用情况？

  2. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

  3. 如何进行分区的分配与回收操作？（假设系统采用的数据结构是“空闲分区表”）

    1）如何分配？

    2）如何回收？（总之，相邻的空闲分区要合并）

动态分区分配没有内部碎片，但是有外部碎片

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上

外部碎片；是指内存中的某些空闲分区由于太小而难以利用

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑（拼凑）技术来解决外部碎片

动态分区分配算法

在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

  1. 首次适应算法（First Fit）

  2. 最佳适应算法（Best Fit）

  3. 最坏适应算法（Worst Fit）

  4. 邻近适应算法（Next Fit）

⭐️首次适应算法和邻近适应算法比最佳适应算法和最坏适应算法好的一点：不用每次都更新空闲分区链/表的排列顺序，减少开销

❗️综合来看，四种算法中，首次适应算法的效果反而更好

非连续分配管理方式

非连续分配：为用户进程分配的可以是一些分散的内存空间

基本分页存储管理

什么是分页存储

将内存空间分为一个个大小相等的分区，每个分区就是一个“页框”（页框、页帧、内存块、物理块、物理页面），每个页框有一个编号，即“页框号”，页框号从0开始

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系，各个页面不必连续存放，可以放到不相邻的各个页框中

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表，页表通常存在PCB（进程控制块）中

  1. 每个页表项多大，占几个字节？

    页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）

    假设页表中的各页表项从内存地址为X的地方开始连续存放，如何找到页号为i的页表项：X + 3*i

    由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要3*(n+1)B

    注意；页表记录的只是内存块号，而不是内存块的其实地址：J号内存块的起始地址 = J * 内存块大小

  2. 如何通过页表实现逻辑地址到物理地址的转换？（逻辑地址结构可拆分为页号P和页内偏移量W）

基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址

通常会在系统中设置一个页表寄存器PTR，存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块PCB中，当进程被调度时，操作系统内核会把它们放到页表寄存器中

注意：假设页面大小是2的整数幂，设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

CPU第一次访问内存：查页表

CPU第二次访问内存：访问目标内存单元

对页表项大小的进一步探讨：

具有快表的地址变换机构（是基本地址变换机构的改进版本）

什么是快表TLB

快表，又称联想寄存器TLB，是一种访问速度比内存快很多的高速缓存，用来存放最近访问的一部分页表项的副本，可以加速地址变换的速度，与此对应，内存中的页表常称为慢表

❗️TLB不是内存

❗️TLB和普通Cache的区别：TLB中只有一部分页表项的副本，而普通Cache中可能会有其他各种数据的副本

引入快表后，地址的变换过程

刚开始快表是为空的，当访问完慢表后，会把最近使用过的页表项放入快表中，下次若快表命中就不需要再访问内存了：

❗️快表中存放的是页表的一部分副本，因为TLB造价比内存高

局部性原理

两级页表

单极页表存在什么问题，如何解决？

1）页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框

2）根据局部性原理可知：很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没必要让整个页表都常驻内存

第一个问题的解决方法：

两级页表的原理，逻辑地址结构（一级页号、二级页号、页内偏移量）

如何实现地址变换？

第二个问题的解决方法：可以在需要访问页面时才把页面调入内存（虚拟存储技术），可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存

两级页表问题需要注意的几个细节？

  1. 若采用多级页表机制，则各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级

  2. 两级页表的访存次数分析（假设没有快表机构）（N级页表访问一个逻辑地址需要N+1次访存）

    • 第一次访存：访问内存中的页目录表
    • 第二次访存：访问内存中的二级页表
    • 第三次访存：访问目标内存单元

基本分段存储管理

与“分页”最大的区别就是离散分配时所分配地址空间的基本单位不同

什么是分段

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址

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

什么是段表

程序分多个段，各段离散的装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”

如何实现地址变换

分段、分页管理的对比

  1. 页是信息的物理单位，分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的

    段是信息的逻辑单位，分段的主要目的是更好的满足用户需求，一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式的给出段名

  2. 页的大小固定且由系统决定，段的长度却不固定，决定于用户编写的程序

  3. 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址

    分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址

  4. 分段比分页更容易实现信息的共享和保护

    不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的（比如有一个代码段中有很多变量，各进程并发的同时访问可能造成数据不一致）

  5. 访问一个逻辑地址需要几次访存？

    分页（单级页表）：第一次访存查内存中的页表，第二次访存访问目标内存单元，总共两次访存

    分段：第一次访存查内存中的段表，第二次访存访问目标内存单元，总共两次访存。与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度

段页式存储管理

分页、分段的优缺点

分页管理：

  • 优点：内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片
  • 缺点：不方便按照逻辑模块实现信息的共享和保护

分段管理：

  • 优点：很方便按照逻辑模块实现信息的共享和保护
  • 缺点：如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片（分段管理中产生的外部碎片也可以用“紧凑”来解决，只是需要付出较大的时间代价）

分段 + 分页 = 段页式管理

段页式管理的逻辑地址结构

段表、页表

一个进程对应一个段表，一个进程对应多个页表

地址变换

  1. 1. 连续分配管理方式
    1. 1.1. 单一连续分配
    2. 1.2. 固定分区分配
    3. 1.3. 动态分区分配
      1. 1.3.1. 动态分区分配算法
  2. 2. 非连续分配管理方式
    1. 2.1. 基本分页存储管理
      1. 2.1.1. 什么是分页存储
      2. 2.1.2. 页表
      3. 2.1.3. 基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）
      4. 2.1.4. 具有快表的地址变换机构（是基本地址变换机构的改进版本）
        1. 2.1.4.1. 什么是快表TLB
        2. 2.1.4.2. 引入快表后，地址的变换过程
        3. 2.1.4.3. 局部性原理
      5. 2.1.5. 两级页表
        1. 2.1.5.1. 单极页表存在什么问题，如何解决？
        2. 2.1.5.2. 两级页表的原理，逻辑地址结构（一级页号、二级页号、页内偏移量）
        3. 2.1.5.3. 如何实现地址变换？
        4. 2.1.5.4. 两级页表问题需要注意的几个细节？
    2. 2.2. 基本分段存储管理
      1. 2.2.1. 什么是分段
      2. 2.2.2. 什么是段表
      3. 2.2.3. 如何实现地址变换
      4. 2.2.4. 分段、分页管理的对比
    3. 2.3. 段页式存储管理
      1. 2.3.1. 分页、分段的优缺点
      2. 2.3.2. 分段 + 分页 = 段页式管理
      3. 2.3.3. 段页式管理的逻辑地址结构
      4. 2.3.4. 段表、页表
      5. 2.3.5. 地址变换
  1. 1. 连续分配管理方式
    1. 1.1. 单一连续分配
    2. 1.2. 固定分区分配
    3. 1.3. 动态分区分配
      1. 1.3.1. 动态分区分配算法
  2. 2. 非连续分配管理方式
    1. 2.1. 基本分页存储管理
      1. 2.1.1. 什么是分页存储
      2. 2.1.2. 页表
      3. 2.1.3. 基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）
      4. 2.1.4. 具有快表的地址变换机构（是基本地址变换机构的改进版本）
        1. 2.1.4.1. 什么是快表TLB
        2. 2.1.4.2. 引入快表后，地址的变换过程
        3. 2.1.4.3. 局部性原理
      5. 2.1.5. 两级页表
        1. 2.1.5.1. 单极页表存在什么问题，如何解决？
        2. 2.1.5.2. 两级页表的原理，逻辑地址结构（一级页号、二级页号、页内偏移量）
        3. 2.1.5.3. 如何实现地址变换？
        4. 2.1.5.4. 两级页表问题需要注意的几个细节？
    2. 2.2. 基本分段存储管理
      1. 2.2.1. 什么是分段
      2. 2.2.2. 什么是段表
      3. 2.2.3. 如何实现地址变换
      4. 2.2.4. 分段、分页管理的对比
    3. 2.3. 段页式存储管理
      1. 2.3.1. 分页、分段的优缺点
      2. 2.3.2. 分段 + 分页 = 段页式管理
      3. 2.3.3. 段页式管理的逻辑地址结构
      4. 2.3.4. 段表、页表
      5. 2.3.5. 地址变换