操作系统存储管理之连续内存分配

操作系统的存储管理做什么

通过处理器、内存和指令 知道,计算机有处理能力,同时计算机还有存储能力,通过这个文章我们也知道在计算机CPU中的寄存器,还有内存和外存等都是计算机的存储介质,不同的存储介质容量、速度和价格都不同。操作系统的一个重要功能就是存储管理,操作系统为了更好管理这些存储介质,也在不断的改进。

计算机中的存储介质

CPU中的存储

处理器、内存和指令 文末我们已经知道Intel 8086处理器中有8个16位的通用寄存器,其中4个可以分成8个8位相互使用不影响的寄存器。不同的CPU,内部构成是不一样的,但是一定存在某些寄存器,这些寄存器就有存储能力。另外我们的CPU中还有一些高速缓存也有存储能力,但是它的使用是由硬件控制的,操作系统不能直接使用它们

内存层次

处理器访问指令和数据,一般过程是在高速缓存中查找,如果没有命中,则访问内存,还未命中(缺页,后面介绍),就会到外存(如硬盘)中去访问。访问内存和外存就需要我们操作系统来控制,操作系统使我们的计算机可以高效的使用我们的存储设备。

连续内存分配

直接分配物理地址

最早的操作系统,启动一个进程后,操作系统直接为该进程分配一块内存上的地址,整个进程运行过程中,CPU从该进程起始内存地址开始,逐步的访问接下来的内存地址,这样该进程就持续的执行。因此,我们在给进程分配内存时,需要将换一个进程的指令分配到一个连续的内存区域内,我们将这个连续的区域称为代码段。另外,我们的程序(进程)还需要处理一些数据,我们也需要将它们存放在内存中,同样需要放在连续的内存区域中,但是这个区域不需要和代码段连续,我们将这个区域称为数据段。内存 的最小访问单位为字节,接下来我们看一个这种情况下程序执行过程访问内存的情形

这个程序的功能是将16个数相加,操作系统为它分配了两个段,一个从0120H开始,存放着代码,一个从0100H开始,存放着数据,分配完毕后,开始从0120H访问指令,第一条指令为:A10001,它的功能是将内存地址0100H中的内容传输到AX寄存器,指令结束后,AX中的值为0005H。第二条指令是03060201,它的功能是将AX中的内容和内存单元0102H里的两个字节相加,结果放在AX寄存器中,由于之前AX中的值为0005H,而内存地址中为00A0H,第二条指令执行后,AX中的值为00A5H。后面的指令和第二条指令相似,最后AX中的数就是内存数据段内的16个16进制数的和。但整个过程当中,无论是对指令的访问还是数据的访问,都是直接使用的真实的内存地址,我们称这个地址为物理地址。这种方式有着严重的缺陷,如果我们在执行这个程序的过程中,有新的程序开始执行,由于内存不足,老的程序被操作系统将数据段内存回收了,然后分配给新的程序,让新的程序执行,新的程序执行结束后,计算机继续执行老的程序,由于刚才数据段已经被回收了,操作系统为它分配了新的数据段,但是由于分配是随机的,这次分配开始地址不再是之前0100H,而是为下图所示的1000H:

那么问题就出现了,旧的程序代码段里存的数据的地址还是之前的物理地址,这时候去访问的数据物理地址有可能就是别的程序的了,那么整个计算机就混乱了。发生这个问题的原因是我们使用了物理地址,这样代码段里面的指令就无法重定位。重定位的问题可以采用逻辑地址物理地址的方式解决,思路是指令提供一个逻辑地址,操作系统将这个逻辑地址转换成物理地址来访问内存,因为内存是连续的,只要操作系统知道这个进程的起始地址,就可以用起始+偏移地址的方式将逻辑地址转换到物理地址

连续内存分配的方法

我们在为程序分配内存时,有不同的方式,操作系统需要维护两个数据结构,一个记录所有进程已分配的内存块,一个记录空闲的块,在新的程序需要分配时,我们可以采用:

最先匹配 分配n个字节,使用第一个可用的空间比n大的空闲块

原理 & 实现

  • 空闲分区列表按地址顺序排序
  • 分配过程时,搜索一个合适的分区
  • 释放分区时,检查是否可与临近的空闲分区合并

优点

  • 简单
  • 在高地址空间有大块的空闲分区

缺点

  • 外部碎片
  • 分配大块时速度较慢
最佳匹配 分配n字节分区时,查找并使用不小于n的最小空闲分区

原理 & 实现

  • 空闲分区列表按照从小到大排序
  • 分配时,查找一个合适的分区
  • 释放时,查找并且合并临近的空闲分区(如果找到)

优点

  • 大部分分配的尺寸较小时,效果很好
  • 可避免大的空闲分区被拆分
  • 可减小外部碎片的大小
  • 相对简单

缺点

  • 外部碎片
  • 释放分区较慢
  • 容易产生很多无用的内碎片
最差匹配 分配n字节,使用尺寸不小于n的最大空闲分区

原理 & 实现

  • 空闲分区列表按由大到小排序
  • 分配时,选最大的分区
  • 释放时,检查是否可与临近的空闲分区合并,进行可能的合并,并调整空闲分区列表顺序

优点

  • 中等大小的分配较多时,效果最好
  • 避免出现太多的小碎片

缺点

  • 释放分区较慢
  • 外部碎片
  • 容易破坏大的空闲分区,因此后续难以分配大的分区

这些分配方式主要是考虑空闲分区是按什么方式排列的,以及查找的开销,以及释放后找合并位置的开销

碎片整理

紧凑

紧凑可以减少外部碎片(两个进程所占内存之间的内存区域),具体就是将等待状态的进程紧凑在一起

分区兑换

将等待状态的进程所占用的内存存储到外存中,然后释放出来供需要的进程使用,进程再执行时再将它对换到内存中

内存分配实例:伙伴系统

伙伴系统的宗旨就是找一块比需要的大,但是又比需要的2倍小的内存块,需要满足这个条件我们可能需要将内存不断的分成两个相等段,直到满足条件。比如我们需要一块2OOK大小的内存,初始时内存共有1Mb的空间,我们需要将它分半,因为它比需要的2倍要大,分完以后有两个512K的段,还是比需要的2倍多,我们再分将其中一个512K的段分半,分成了两个256K的段了,这时我们选择其中一段就要可以了。在伙伴系统中,释放后的段我们需要判断相邻的是否有和它大小一样的,另外合并的两段地址的位置必须是2^(i+1),2^i为块大小。详细分配合并流程如下:

需要的数据结构为一个二维数组,用于存放空闲分区大小和位置。

缺点

连续内存分配除了上面提到的重定位问题,还有诸如下面的这些问题:

  1. 进程可以随意访问整个内存,安全性极低
  2. 内存使用效率低,因为内存直接被分配,如果内存不足时,会释放,多进程交替的情况,会不断的装入装出
  3. 部分碎片可能永远不会被利用
坚持原创分享,您的支持将鼓励我不断前行!