Long

欢迎来到Long的博客站点

内存管理: 存储器抽象之地址空间

1. 前言

在上一篇文章中提到了内存管理的静态重定向,但是,操作起来非常麻烦,需要装载器辨别什么是地址、什么是常数,这无疑将导致程序的装载速度降低,这样程序之间的切换代价太高了。本质原因在前面也提到了,那就是程序是直接操作物理地址空间的,那么,能不能不然程序直接操作物理空间呢?也就是对内存进行抽象,让程序在抽象的内存上面进行操作,这样程序就没有办法有意或者无意的破坏其他程序或者操作系统的空间了。那就是地址空间。

2. 地址空间

地址空间就是一个进程可以进行寻址的一套地址集合,每个进程都有自己的地址空间,这样进程之间就无法访问其他进程的地址了。

2.1 动态重定向(基址寄存器与界限寄存器)

地址空间就是使得每个进程拥有自己的独立空间,一个简单的解决办法就是基址寄存器 + 界限寄存器,但一个程序被加载到内存中的时候,这时装载到基址寄存器和界限寄存器中的值分别是程序被加载内存中的实际地址,界限寄存器为进程的长度。

这样当一个进程需要访问内存的时候,取出一条指令,CPU硬件在把该内存地址发送给内存总线的时候,自动加上基址寄存器的值,同时和界限寄存器中的值进行比较,判断该进程访问的地址是否合法。

比如上一篇文章中的程序a和程序b,对于程序a,基址寄存器的值为0,界限寄存器的值为16384。对于程序b,基址寄存器的值为16384,界限寄存器的值为32768,这样,在执行程序b的jmp 28指令时,硬件判断这条指令时需要加上基址寄存器的值,此时实际执行的指令为 jmp 16423,这样完成了我们的实际需求。

但是,动态重定向有一个问题就是,每次在执行需要访问实际的内存地址的时候,都需要进行加法和比较操作。

3. 交换技术

前面提到的动态重定向技术解决了进程之间地址访问的问题。但是,内存中如果存放了几个程序,其中某个进程终止,另一个程序需要加载到内存中,这就是下面讨论的情况了。注意:这里讨论的程序都是可以放入内存中的,但是,现在的程序,动辄几十MB,有些大型单机游戏几十个GB,显然这是没办法一次性加载到内存中的,同时,如果某个进程被挂起,另一个程序需要被加载到内存当中,但是,此时内存中没有能满足该程序的内存,这时要么该程序等待有空闲的内存,要么将内存中的某些被挂起的进程换出内存。这就需要用到交换技术,将内存中的某些进程换出内存,将磁盘中的程序加载到内存当中。

《内存管理: 存储器抽象之地址空间》

如上图所示,程序A被加载到内存当中,接着是程序B,然后是程序C;然后程序A执行完毕,从内存中换出,接着程序B加载到内存当中,B接着执行完毕,最后程序A再次被调入内存当中执行,在上面的交换过程中,可以看出来,存在空闲的内存空间,这称为内存空洞,同时,如果有连续的两个内存空间空闲,这时候就需要进行内存紧缩。但是,进行内存紧缩通过花费的代价比较高,一般不进行这样的操作,除非必要。

在上面还可以看出来的是,每次程序被加载到内存时,其占据的内存空间都是固定,但是,这样每次加载程序也是非常方便的,操作系统只需要对程序分配固定的空间即可,显然,每个程序所需要使用的内存空间都是固定的,这时不可能的。

一个程序可以使用malloc来动态分配内存空间,如果两个程序分配的空间是相邻的,同时,没有为它们分配空闲的内存空间,这时,如果一个程序增长了空间,必然会踩踏到另一个程序的空间。导致程序直接崩溃。

那么就需要为每个程序分配一块空闲的地址空间,这就引出了现在经常讨论到的进程地址空间问题,因为一个程序可以使用堆空间来申请内存,也可以使用栈来获取临时的空间,那么就可以采用两个需要增长的空间在同一个空闲空间的地方,这样,一个向上增长,一个向上增长。如图所示:
《内存管理: 存储器抽象之地址空间》

这里解释一下上图,在上面这张图中,A-program存放的就是程序A的代码,也就是常说的代码段,在A-data中就是数据段,用于存放程序A的全局数据、常量数据。后面就是分配的空闲区,接下来就是栈段,用于存放A的栈数据,比如局部变量、函数的压栈等等。在空闲区中,允许栈和堆来使用,堆就是位于A-data数据段上面。如果提前分配的空间用完了,就需要将进程放置到一块内存更大的空间中去了。

从上面可以看出来,在为程序分配一块空间时,操作系统是需要知道内存的使用情况的,这样其才能为需要的进程分配内存空间。这时候就需要一定的技术来对内存的使用情况进行记录了。

4. 空闲内存管理

一般有两种情况对内存的使用情况进行管理:位图和空闲区链表。

4.1 使用位图的存储器管理

使用位图进行存储器管理时,首先将内存划分为几个字到几千个字节大小的分配单元,每个单元对应位图中的一位,1表示是该内存已经使用,0表示空闲,或者使用相反的逻辑。一块内存区域和其位图的对应如下图所示:
《内存管理: 存储器抽象之地址空间》
说明:图a中有5个进程被加载到内存当中,白色区域表示已经使用,灰色表示空闲;其对应的位图如图b所示;图c表示同样的内存块使用空闲链表的表示情形。

内存越大,在将内存划分为一个个分配单元时,位图就越大,同样,分配单元越小,需要的位图也就越大,因为分配单元越小,内存被划分的分配单元的数量也就越多,需要的位图的位数就越多。也就是说,内存的大小和分配单元的大小决定了位图的大小。当一个大小为k个分配单元的程序想要加载到内存中时,操作系统需要在内存中寻找一块足够大的空间来存放该进程,其首先在位图中寻找,在位图中寻找有连续的k个0的位置,这是一个费时的操作,这就是位图的缺点。

4.2 使用链表管理内存

在上图的c中,就是使用链表来对内存进行管理,链表中的每个结点表示一个程序使用内存或者空闲内存的情况,p表示该结点所表示的内存已经被使用,h表示空闲,第一个数字表示起始地址,第二个数字表示长度,最后一个字段表示下一个结点的地址。比如第一个结点,表示该结点所表示的内存空间已经被占用,0表示程序的起始地址,5表示程序的长度。同时,如果一个程序被换出内存,同时该程序旁边有空闲内存,我们可以不用对实际的物理空间进行操作,直接在链表中将两个结点进行合并即可,这样就完成了内存的紧缩操作,非常方便。一个内存被换出内存时,我们需要在链表中找到表示该段内存的结点,在进程的pcb中,有一个字段用于保存一个进程在链表中结点的地址,这样在O(1)的时间内就能找到其对应在链表中的结点。但是,一个程序要加载到内存中,需要在链表中找到一个合适的结点,该结点所表示的空闲内存空间能存放该进程。这样就产生了一系列的算法。

在上面说到了链表中结点的合并,如果需要合并的结点位于空闲结点后面,这时,如果采用单链表,就需要遍历整个链表,所以,应该采用双向链表来记录内存的使用情况。

4.2.1 首次匹配算法

我们知道,一个程序加载内存中,需要为其分配空间的空间,用于栈和堆的增长。这里首次匹配算法就是在链表中寻找第一个足够大的空闲区(只要这个空闲区能容纳进程),如果空闲区的大小和进程的大小刚好相等,就直接使用,如果空闲区大于进程大小,就新产生一个小空闲区。首次匹配算法就是为了避免在链表中多次查找,查找到一个符合条件的空闲区,直接使用。

4.2.2 下次匹配算法

下次匹配算法在每次找到合适的空闲区后,记录找到的位置结点,如果后面还有程序需要加载到内存中,这时,就直接在上次已经找到的位置结点后面进行查找,而不是像首次匹配算法这样每次从结点的开始进行遍历查找。但是,下次匹配算法的性能略低于首次匹配算法。

4.2.3 最佳适配算法

最佳适配算法和首次匹配算法有很大不同,首次匹配算法是只要找到的空闲区大于等于进程需要的空间,就直接拿来用;而最佳适配算法正如名字所言,每次查找的空闲区和进程需要的空间尽量匹配,也就是找到的空闲区的大小尽量接近进程需要的空间。这样就能不要和首次匹配算法那样,重新得到一个新的空闲区,但是,仿真程序表明,最佳适配算法所造成的小的空闲区比首次适配算法更多,其实这也是可以理解的,最佳适配算法指的是最佳,比如有一个程序需要12KB的空间,但是找到了一个13KB空间的空闲区,这时候是可以使用的,算法只是说尽量匹配。这时候将造成1KB的空闲区,很可能这个小空闲区一直都没机会使用,知道前面的进程终止,进行空闲区的合并。

4.2.4 最差适配算法

既然最佳适配算法会造成比较多的小空闲区,那么我们是不是可以每次找到的空闲区都比较大,这样新的空闲区也比较大,可以用于下次使用,这就是最差适配算法,每次找到的空闲区总是最大的可用空闲区。

总结

在上面讨论的情况都是占用空间结点和空闲区结点使用同一个链表,如果把二者进行分离呢,每次需要分配一个内存空间时,从空闲区链表中查找,这样上面的四种算法的性能都有一定程度的提高,但是,这样做是由代价的,比如一个进程终止,此时需要把进程表示的占用区链表结点删除,这在前面说了,非常简单,在该进程的pcb中存有该结点的地址,直接就能删除。但是,每释放一个进程,都需要在空闲区找到一个合适的插入位置,同时检查该进程所占用的区域旁边是否有空闲区,用于空闲区的合并。找到一个合适的插入位置,需要遍历整个链表,因为没有直接的信息来表示该新空闲区结点应该插入到空闲区链表的哪个位置。

如果对空闲区链表按照所能表示的空间大小进行升序排序,那么使用最佳适配和首次匹配算法的性能是最好的,使用下次匹配算法则毫无意义,因为使用下次匹配算法,如果下次要找到的空间小于此时记录的位置,那么其只能使用后面的空间,同时产生一个新的空闲区,之前提到了,这里链表都是采用双向链表的。

还有一种算法,那就是快速适配算法,其思想其实就是分类,将那些常用大小的空闲区组成一张表,这张表的每个表项都存有指向一个固定大小的空闲链表。比如其第一个表项指向大小为4KB的空闲区链表的表头指针,第二个表项指向大小为8KB的空闲区链表的表头指针,如果有一个大小为9KB的空闲区,可以放置在8KB的空闲链表中,也可以单独成一个链表。

同样,可以看成其是一个已经排好序的空闲区链表,在需要往空闲区链表中插入一个结点时,其需要遍历那张表,找到合适的空闲链表进行插入,同时,需要判断其是否可以和其他空闲区进行合并,这时候就需要遍历全部的链表了,因为你不知道其旁边是否有空闲区。如果不进行合并,那将产生非常多的小空闲区,最终导致内存资源不够用。

点赞
  1. panda说道:

    :cowboy: 很强!

发表评论

电子邮件地址不会被公开。