从第 11 篇笔记开始进入第二章节,也就是存储器管理的相关知识。下面是本篇笔记的思维导图:
存储层次至少具有三级:CPU 寄存器、主存(内存)和辅存(外存)
用户程序在执行前必须先进入内存,具体来说包括以下步骤:
装入模块中指令所涉及的地址是相对地址(逻辑地址),往往并不是装入内存后的实际地址,因此在装入模块装入内存后,需要将原先的相对地址转换成绝对地址(物理地址)。在下面三种装入方式中,对相对地址的处理是不同的。
绝对装入方式:
在单道程序运行环境中,通常可以事先知道程序最终装入内存时的实际地址,所以编译程序产生的目标模块中可以直接使用绝对地址,模块在装入到内存的时候也无需进行地址转换的工作。
静态重定位装入方式:
但在多道程序运行环境中,无法事先知道程序最终装入内存时的实际地址,所以目标模块中只能使用相对地址,所有指令中涉及到的地址都是相对于起始地址 0 来说的。装入模块可以装入到内存的合适位置,并且在装入的时候会进行地址转换(重定位)的工作。
“静态”主要体现在程序装入内存后,在运行期间就不能再移动了,因为一旦移动就意味着需要再次更改物理地址,而地址是无法修改的,这时候就会发生错误。
动态重定位装入方式:
但很多时候,程序在内存中的位置会经常发生改变,比如在外存和内存之间对换。位置不会是一成不变的,这时候就要采用动态重定位装入方式。这种方式并不急于在装入的时候就进行地址转换,而是在程序真正执行的时候才去进行地址转换的工作。
这意味着程序在装入内存后,在运行期间是可以移动的。因为不管移动到哪个内存位置,始终会有一个重定位寄存器用于记录和更新装入模块当前的物理起始地址,逻辑地址只需要和这个物理起始地址相加即可得到物理地址。
在内存分配中有外部碎片和内部碎片的概念:
单一连续分配只适用于单用户、单任务的操作系统中,它会把整个内存区划分为系统区和用户区,一道用户程序就会独占整个用户区,因此存储器的利用率非常低、内部碎片很大(分配了整个用户区,但实际用到的空间并不多)。
固定分区分配适用于多道程序环境,依然是将整个内存区划分为系统区和用户区,但是用户区进一步细分:划分为多个固定大小的分区,一个分区放一个进程。
每个分区的大小可以相等也可以不等:
和前面的分配方式不同,动态分区分配方式要灵活得多,就像日常生活中的按需分配,不是预先划分好,而是进程需要多少内存空间,我们就给它多少内存空间。比如说一开始有 100 的空闲空间,进程 1 进来用了 10,进程 2 进来用了 20,进程 3 进来用了 30,需要多少就给多少,以此类推 …..
但是采用这种分配方式需要考虑的问题是,当一个进程有多个空闲的内存空间可供选择的时候,它应该使用哪个空间呢?比如上面的例子中,进程 2 运行完释放了 20 的内存空间,此时进程 4 进来了,他也需要用到 20 的内存空间,但对他来说,他既可以选择占用进程 2 释放的空间,也可以选择占用后面没被用到的一大片空间。
因此,我们实际上需要用到一种算法来决定进程 4 的选择,而且为了更好地描述内存使用情况,我们也需要像之前那样,维护一张空闲分区表或者一个空闲分区链。
动态分区分配的过程是这样的:
假设进程 X 需要用到 x 大小的内存空间,那么在某种算法下,系统会检索空闲分区表或者空闲分区链,决定将某个空闲分区分配给这个进程。假设这个空闲分区大小为 y(y>x),若 y-x
的值非常地小,甚至小于我们预先设定的一个阈值,那么说明进程可以充分利用这个空闲分区,我们可以将整个分区直接分配给进程;若 y-x
的值大于这个阈值,说明空闲分区无法得到完全的利用,我们可以将整个分区能够被充分利用的那部分(也即 x)划分给进程,而剩下的 y-x
则继续留在空闲分区表或者空闲分区链中。
不过,具体都有哪些算法来决定分区的分配呢?
首次适应 (FF)
将多个空闲分区按照地址递增的顺序排列,每次分配内存的时候顺序查找空闲分区表,找到第一个大小能满足要求的空闲分区。
邻近适应(NF)
邻近适应算法就克服了上述提到的首次适应算法的缺点,它同样是将多个空闲分区按照地址递增的顺序排列,不同的是,每次查找都是从上次查找结束的位置开始查找的
最佳适应(BF)
连续分配的方式规定,为各个进程分配的必须是一块连续的空间,因此对于一块内存空间来说,若它不断被分割,则意味着它能容纳下大进程的可能性越低。为了保证有足够的内存空间可以容纳大进程,基本思想应该是优先利用小的空闲分区,而保留大的空闲分区。
最佳适应算法将空闲分区按照容量递增的顺序排列,每次分配内存的时候顺序查找空闲分区表,找到第一个大小能满足要求的空闲分区。
最坏适应 (WF)
为了克服最佳适应算法的缺点,最坏适应算法规定,将空闲分区按照容量递减的顺序排列,每次分配内存的时候顺序查找空闲分区表,找到第一个大小能满足要求的空闲分区。
最后我们可以来看一张总结图:
总结:
由于动态分区分配不是事先划分好区域,而是“按需分配”,所以不会出现区域划分出去后无法完全得到利用的情况,也即不会产生内部碎片;但是可能出现内存空间太小而无法被分配出去的情况,也即可能产生外部碎片。
当系统很大的时候,内存分区会很多,这时候还采取基于顺序搜索的动态分区分配算法的话,效率并不高。因此出现了基于索引搜索的动态分区分配算法。
快速适应
快速适应算法又叫分类搜索算法,它将空闲分区按照进程常用的空间大小进行分类,比如 2kb 为一类,4 kb 为一类,6 kb 为一类等,对于每一类空闲分区,会有一个单独的空闲分区链表。此外,还会有一张总的管理索引表,索引表的每一个表项对应了一类空闲分区。
在为进程分配分区的时候,首先会根据进程长度,从索引表中找到能容纳它的最小空闲区链表,接着将该链表的第一块分配给进程。
伙伴系统
伙伴系统的具体规则,书里的描述会更完整:
为了更直观地理解,这里用一个例子来说明。
假设系统总的内存为 512 kb,现有进程活动如下:
按照伙伴系统的算法,内存的分配和回收是怎么进行的呢?
首先,一开始肯定是整片空的内存空间:
进程 A 请求 100kb,因为 64<100<128,即 2^6<100<2^7,所以寻找是否有 2^7=128 的空闲分区,当然是没有的(目前只有 512kb),所以寻找是否有 2^8=256 的空闲分区,也没有,所以寻找是否有 2^9=512 的空闲分区,找到了,此时就把 512kb 一分为二:
一半的 256kb 加入到对应的空闲分区链表,一半的 256kb 用于分配,对这一半继续一分为二:
一半的 128kb 加入到对应的空闲分区链表,一半的 128kb 用于分配,这一半对进程 A 来说足够了,于是占用它:
进程 B 请求 50kb,因为 32<50<64,即 2^5<100<2^6,所以寻找是否有 2^6=64 的空闲分区,当然是没有的,所以寻找是否有 2^7=128,找到了,此时就把 128kb 一分为二:
一半的 64kb 加入到对应的空闲分区链表,一半的 64kb 用于分配,这一半对进程 B 来说足够了,于是占用它:
进程 C 请求 100kb,因为 64<100<128,即 2^6<100<2^7,所以寻找是否有 2^7=128 的空闲分区,当然是没有的,所以寻找是否有 2^8=256 的空闲分区,找到了,此时就把 256kb 一分为二:
一半的 128kb 加入到对应的空闲分区链表,一半的 128kb 用于分配,这一半对进程 C 来说足够了,于是占用它:
进程 A 释放 100kb:
进程 D 请求 20kb,因为 16<20<32,即 2^4<100<2^5,所以寻找是否有 2^5=32 的空闲分区,当然是没有的,所以寻找是否有 2^6=64 的空闲分区,找到了,此时就把 64kb 一分为二:
一半的 32kb 加入到对应的空闲分区链表,一半的 32kb 用于分配,这一半对进程 D 来说足够了,于是占用它:
进程 D 释放 20kb,回收 32kb,由于事先已经有一个 32kb,所以此时两个互为伙伴的 32kb 进行合并:
进程 B 释放 50kb,回收 64kb,由于事先已经有一个 64kb,所以此时两个互为伙伴的 64kb 进行合并,形成 128kb,由于事先已经有一个 128kb,所以此时两个互为伙伴的 128kb 进行合并,形成 256kb:
最后补充一个计算伙伴地址的方法:
对于给定的内存块,若它的大小为 2^k,起始地址为 x,那么它的伙伴地址:
x/2^k
为奇数,则伙伴地址为 x - 2^k
x/2^k
为偶数,则伙伴地址为 x + 2^k
哈希算法
前面的两种方法(快速适应和伙伴系统)都是将空闲分区按照大小进行分类,并为每一类建立一个独立的空闲分区链表,再用一个总的索引表进行记录。不过,如果分类过多,则索引表的表项也会过多,这时候搜索索引表的时间开销就会比较大。
因此,哈希算法选择建立一张哈希表(而不是普通的索引表),这张哈希表以空闲分区大小作为关键字,每次需要进行分配的时候,会根据所需空闲分区的大小,通过哈希函数快速计算得到该空闲分区在表中的位置,从而得到对应的空闲分区链表。
动态可重定位分区分配算法与动态分区分配算法基本一致,区别仅在于,它在原有的基础上增加了紧凑功能。
到目前为止,我们所讲的都是连续分配的方式,也就是说,为某个进程分配的必须是一块连续的空间 —— 若多个空闲分区不是相邻的,那么即便它们的大小相加后,已经足以满足进程的需求,也无济于事。为此,可以采用紧凑技术解决这个问题。紧凑技术可以把内存中各个进程进行移动,使得它们都相邻,从而把原先分开的各个空闲分区合并在一起,带来了更大的、可以充分利用的空闲分区:
在这里会发现,每次发生紧凑,各个程序和数据的物理地址就要发生改变。
操作系统系列学习笔记: