早期分配管理方式

连续分配管理方式

这里我们讲一讲内存空间的分配方式，分为连续分配管理方式和非连续分配管理方式，我们首先学习连续分配管理方式。

连续分配顾名思义就是为用户进程分配的必须是一个连续的内存空间，这里有三种连续分配方式如下：

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据，而用户区存放用户进程相关数据。内存只有一道用户程序，用户程序独占整个用户区空间。

这种方式优点是实现简单，没有外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护（例如早期的PC操作系统MS-DOS）。但是缺点是只能用于单用户，单任务的操作系统中（这显然不适合并发进程），并且有内部碎片，存储器利用率极低。

思考：什么是内、外部碎片，有什么区别？

我们先给出定义：

外部碎片是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。外部碎片是处于任何已分配区域或页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或者其他原因，使得系统无法满足当前申请。多道可变连续分配只有外部碎片。

内部碎片就是已被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间。内部碎片是处于区域内部或页面内部的存储块。占有这些区域或页面的进程不能使用这个存储块。而在进程占有这块存储块时，系统无法利用它。知道进程释放他，或进程结束，系统才有可能利用这个存储块。

所以内外碎片本质区别就是是否已经属于某个被分配的进程。并且外部碎片在操作系统的调整下可以消除，而内部碎片操作系统无权调配管理，只能等待被分配进程结束。

这里我们举一个例子来形象介绍，假设现在有1,2,3,4,5,6六个仓库，当1,2,3,4,5已填满后，4清仓了，那么此时空仓库有4,6，此时来了一批货物大小为2个仓库刚好满足4,6容量之和，但是货物要去连续存储，此时4,6无法使用并且4,6不属于任何一个货物所以4,6形成的就是外部碎片。而现在假设六个仓库都是空的，并且要求货物最小分配空间为间，所以一个仓库只能装一种货物，那么现在有一批2.5间容量的货物装载1-3号仓库，那么3号仓库只装了半间，但是此时再有别的货物也不能装入3号仓库并且此时3号仓库属于第一批货物，并且管理员也不能调整再使用3号仓库了，那么3号仓库剩余的空部分就是内部碎片。–大佬博客

按照上面的介绍我们知道了单一连续分配不会产生外部碎片的原因了，并且这种分配管理方式不用想也知道肯定会产生很大的内部碎片，所以不合理。

固定分区分配

20世纪60年代支持多道程序的系统出现后，为了能在内存中装入多道程序并且这些程序之前互不干扰，于是将整个用户控件划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的。最简单的一种可运行多道程序的内存管理方式，但是显然这种固定大小分区的分配方式很不合理，于是又出现了分区大小不等的分配方式。

分区大小相等：缺乏灵活性，但是很适用于一台计算机控制多个相同对象的场合（比如：钢铁厂有n个相同的炼钢炉，就可以把内存分为n个大小相等的区域存放n个炼钢炉控制程序）

分区大小不等：增加了灵活性，可以满足不同大小的进程需求，根据常在系统中运行的作业大小情况进行划分（比如：划分多个小分区，适量中等区，少量大分区）。

思考：那我们如何知道某个分区i的具体大小是多少？

所以我们需要建立一个数据结构–分区说明表来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小，起始地址，状态（是否已分配）。如下：

当用户程序要装入内存时，由操作系统内核程序根据用户程序的大小检索检索表，从中找到一个满足大小的，未分配的分区，将之分配给该程序，然后修改状态为“已分配”。

这种固定分区分配优点是实现简单，无外部碎片（因为可以调整消除）缺点是当用户程序太大时，可能所有的分区都不能满足需求，此时就不得不采取覆盖技术来解决但是这又会降低性能，并且这种方法肯定是会产生内部碎片的，内存利用率低（无论是大小固定还是大小不等的分区分配方式）。

动态分区分配

动态分区分配又称为可变分区分配，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的，（比如：假设某计算机的内存大小为64MB，系统区8MB，用户区56MB…）

很明显这种方法肯定是没有内部碎片的，解决了固定分区分配的缺陷。

思考：系统需要用什么样的数据结构记录内存的使用情况？

其实和固定分区分配中分区不等大小的方法一样，也是建立表或者链来记录呗，如下：

当然名字还是得换一换的，实际上思路是异曲同工的。一定要注意此时只需要记录空闲连续分配区间的大小和起始地址就可以了。。

思考：当很多个空闲分区都能满足需求时选择哪个分区进行分配？

如在上图中的空闲区域情况时，又来了一个进程5（之所以没有进程1,2,3可能是挂起或者运行完成释放了）大小为4MB，此时所有分区都满足，那么如何分配呢？

这里我们有以下几种情况（后面会细讲）：

1. 用最大的分区进行分配
2. 用最小的分区进行分配（比较符合正常思维）
3. 用地址最低的部分进行分配

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法对系统性能会有很大的影响，因此人们研究后发明了几种动态分区分配算法（后面讲）。

思考：如何进行分区的分配和回收？

空闲分区分配

首先看分配，这个简单，如果分配后某个分区刚刚好被占据了那么这个表项直接删除就好了。如下图：

5号进程放在了3号空闲分区刚好占满，那么删除3号表项即可。

如果空闲分区分配一定空间后没有被占满，那么就要更新分区大小和起始地址了，如下图：

5号进程放在了1号分区并且从1号分区的头部开始放，那么1号分区并未占满，此时就要更新1号分区，起始地址+4变为12同时大小-4变为16。

分区回收

分区的回收涉及的问题较多，这里我们逐一讨论

情况1：回收区的后面有一个相邻的空闲分区

例如下图：

此时要回收进程4了，那么很明显回收区后面相邻连着空闲分区1，那么此时只需要将后面的空闲分区更新起始地址-4同时分区大小+4就好。这个是两个相邻的空闲分区的合并。

情况2：回收区的前面有一个相邻的空闲分区

例如下图：

进程3完成后回收，此时回收区与前面的2号空闲分区所以合并更新2号分区的分区大小+18=28即可，起始地址此时是不需要变得。

情况3：回收区的前、后各有一个相邻的空闲分区

如下图：

此时比较复杂，需要将回收区和后相邻分配去全部加入到前相邻分配区，此时如上面的进程4被回收，那么回收区+后相邻空闲区的总大小为14都加到前相邻空闲分配区1中，所以此时1号空闲分配区大小为34，同时起始地址还是不变，然后还要将后相邻空闲分区删除表项，即2号分区变为了原先的3号分区。

情况4：回收区的前、后都没有相邻的空闲分区

如下图：

我们可以看到此时如果进程2回收，那么新的回收区就成为了一个新的最靠近低地址的空闲分区，所以加入一个新表项这里是1号分区大小为进程大小14，同时起始地址是28。

我们可以看出动态分区不会有内部碎片，但是会有外部碎片。如果内存中空闲空间的总和本来可以满足某进程的需求，但由于进程需要的是一部分连续的内存空间，因此这些“碎片”不能满足进程的需求，可以通过紧凑（拼凑，Compaction)技术来解决外部碎片。紧凑技术就是操作系统不时地对进程进行移动和整理来达到将几个外部碎片凑成一片连续的分区这需要动态重定位寄存器的支持。

总结

动态分区分配算法

接着前面的思考问题，我们来思考一下对于具有许多个空闲分区都可以容下进程数据时我们应该使用哪种策略选取分区。

首次适应算法

顾名思义，该算法的思想就是每次都从低地址开始查找，找到第一个能满足大小的空闲分区。实现方法就是空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小满足要求的第一个空闲分区。如下图：

那么很明显5号进程会放在1号空闲分区，6号进程会放到2号分区。这种算法没有什么问题，但是缺陷是可能前面有一个非常大的空闲分区可以放入很多很小的进程数据，但是后面有刚刚好可以放进该进程的大小的空闲分区，这样大的空闲分区会优先被使用，最终造成许多小的空闲分区，再来大的进程就放不下了。同时会导致许多小的空闲分区在低地址处排列，每次分配查找还要再经过这些分区，增加了查找的开销。

最佳适应算法

算法思想是由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因为为了保证当大进程到来时也能有连续的大片空间，可以尽可能多地留下大片的空闲区，所以优先使用更小的空闲区，这样就弥补了首次适应算法的缺点。实现方法是空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表）找到大小能满足要求的第一个空闲分区也就是最小的可以容纳该进程的空闲分区（符合人类思维，尽可能不浪费的多放）

加入现在有一个进程6那么显然要放到2号分区这样2号分区就只剩下1MB了就要同时更新到表或链的最前面。我们发现这种方法的缺陷是每次都选更小的分区放最后只会导致很多外部碎片。

最坏适应算法

又称最大适应算法，就是为了解决最佳适应算法的问题而产生的，为了避免留下太多的外部碎片，优先使用最大的连续空闲区，这样分配后剩下的空闲区就不会太小，更方便使用。实现也很简单就是按照容量递减次序排列，每次分配也是顺序查找找到大小能满足要求的第一个空闲分区。

其实我们发现对于首次适应算法如果恰巧大的分区在前面，小的分区在后面，那么实际上就和最适应算法你一样了，所以最坏适应算法的缺陷就是大分区快速被消耗，再来大进程放不下了。

邻近适应算法

弥补首次适应算法的查找开销大的缺陷，这个算法思想是每次都从上次查找结束的位置开始向两侧检索就能解决上述问题，哪侧先找到大小合适的就放下该进程，所以是双向链表。

首次适应算法每次都要从头查找，每次都必须需要先检索低地址的小分区。但是这种规则决定了当低地址有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会有可能把高地址部分的大分区空闲出来，所以首次适应算法有可能会出现最坏适应算法的缺点即外部碎片多但同时也可能出现最佳适应算法的优点即合理利用空间。

而邻近适应算法的规则可能导致无论低地址，高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大小分区更可能被使用，划分为许多小分区，最后导致无大分区可用，所以综合四种算法来看，首次适应算法的效果反而更好。

思考：四种分配算法的异同？

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

我们先看一个图：

我们可以看出此节我们就开始讲解非连续分配管理方式了，这里只是一种一个小部分而已。非连续分配就是为用户进程分配的可以是一些分散的内存空间。

地址空间

我们先回忆一下什么是地址空间，我们知道地址分为两种逻辑地址（相对地址）和物理地址（绝对地址）两者有一定的映射关系。

但是我们发现这种存储只能连续存储，这很不方便，所以引出了分页存储的概念。

分页存储

我们将内存空间分为一个个大小相等的分区（比如每个分区为4KB），那么每个内存分区就是一个“页框”（页框=页帧=物理块=物理页面）。每个页框都有一个编号，即“页框号“（页框号=页帧号=内存块号=物理块号=物理页号），页框从0开始编号。

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

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

注意进程的最后一个页面可能没有一个页框那么大，也就是说分页存储有可能产生内部碎片，因此页框不能设置的太大，否则可能产生过大的内部碎片造成浪费。

思考：固定分区分配（分区大小相等）和分页存储的区别？

我们第一想法一定是这个和分区大小相等的固定分区分配好像，实际上思路就是差不多的，只不过是前者是一个小空间里放一个作业，所以作业/进程还是连续分配的，并且分区大小无论是多大都有可能会放不下更大的进程并且内部碎片会很大，而现在分页存储类似于将作业分块离散存储在许多的小分区中，所以作业/进程本身是不连续的且相应的无论作业/进程多大理论上都可以放下（只不过是会分成许多页面存储在许多页框中)并且内部碎片在一定的页框大小时是很小可控的。

思考：那么我们怎么知道每个页面存放在了内存的那个页框中呢？

所以我们同样需要建表来说明–页表

页表

每个进程都会被分为许多页面存放在许多同样数量的页框中，所以每个进程都要有一张的页表，所以页面一般存放在PCB中，所以页表会一直在内存中（毕竟PCB是一直在内存中）直至该进程销毁。

所以一个进程对应一个页表，进程的每个页面对应一个页表项，每个页表项由“页号”和“块号”组成。页表记录着进程页面和实际存放的页框之间的映射关系。每个页表项的长度是相同的。

思考：每个页表项多大？占几个字节？

首先我们要走出误区，表项的个数只是和页面页框数量一样，但是大小不同，页框大小和页表表项没有直接关系，我们先看一下两者的区别。页框是存储数据的单位，而页表表项是存储页框号和页面号的单位。所以页框大小是人为划分的，但是一旦内存大小和页框大小确定了，那么页表表项也就确定了。比如下题：

假设某个系统物理内存大小为4GB，页面大小是4KB，则每个页表项至少应该为多少字节？

首先内存大小为4GB也就是2^32字节，页面大小实际上等于页框大小，所以页面页框的大小都是4KB=2^12字节，所以一共可以有2^32/2^12=2^20个页框(页面当然也就是2^20个），编号为0~2^20-1，所以一共会有2^20个页表项并且编号至少需要20bit来表示，又因为一个字节为8bit,多以至少需要3个字节来表示。所以一个页表项为3B，一个页框或页面为4KB。

并且页表项肯定是连续的，假设页表中的页表项从地址为X的地方开始连续存放，那么第i号页表项的地址就是X+3*i,同时第i个页面的存储地址就是第i号页表项中所对应的块号。并且我们发现页号是隐含的，所以页号不占用存储空间，一个页表项所占空间就是块号所占的空间，页号就好像数组的键值一样是隐含不占用空间的。

并且还要注意，块号记录的不是页框的起始地址，而只是页框号，又因为0号页框号的起始地址就是0，所以j号内存块的起始地址就是j*内存块大小。

思考：如何实现地址的转换？

我们回忆一下在连续存储时，操作系统有三种策略实现地址转换（绝对装入，静态重定位，动态重定位)。现在是分页离散存储，我们如何找到逻辑地址所对应的物理地址呢？我们知道虽然各个页面是离散存放的，但是页面内部是连续存放的。

所以如果想要访问逻辑地址A需要以下步骤：

1. 确定逻辑地址A对应的“页号”P
2. 找到P号页面在内存中的起始地址（需要查页表找到内存块号j,起始地址就是j*内存块大小)
3. 确定逻辑地址A的“页内偏移量”W

$$逻辑地址A的物理地址=P号页面在内存中的起始地址+页内偏移量W$$

思考：如何确定逻辑地址对应的页号和页内偏移量？

我们以一道例题来讲解：假设在某个计算机系统中，页面大小时50B，某进程逻辑地址空间大小为200B，则逻辑地址110对应的页号、页内偏移量是多少？

页号=逻辑地址/页面长度（取除法的整数部分）

页内偏移量=逻辑地址%页面长度（取除法的余数部分）

所以上面的题页面号=110/50=2，页内偏移量=110%50=10，所以逻辑地址可以拆分为页号和页内偏移量来表示。接下来我们去页表中寻找页号2所对应的块号j,那么物理地址就是j*50+10。这里我们是用十进制表示的，但是我们知道对于计算机来说，他的操作都是二进制串进行操作，现在我们还是按照这个思路来看一下二进制的表示：

在计算机内部，地址用二进制表示，如果页面大小刚好是2的整数幂，则计算机硬件可以很快就把逻辑地址拆分成页号和页内偏移量，这样自然转换到物理地址也就更快了。如果是2的整数幂，那么假设每个页面的大小为2^K字节，那么用二进制表示逻辑地址时，逻辑地址01串的末尾K为就是页内偏移量，其余部分就是页号。如下：

我们可以看出页面大小为2^12B，所以末尾12位就是黑色部分就是页内偏移量，同时红色的20位就是页号了。

这样我们可以就轻松的对逻辑地址进行拆分转换成物理地址了。又因为内存块的大小=页面大小，且块的起始地址就是页内偏移量为0的地址，所以各个块的地址可以表示为：

同样对于物理地址，假设现在我们通过查询页表得到1号页面存放在了9（1001）号内存块，那么

我们发现前面红色部分就是9的二进制串即内存块号

思考：二进制串中物理地址和逻辑地址的异同点？

我们仔细观察发现逻辑地址和物理地址的表示公式都是如下（前提：页面大小是2的整数幂）：

$$逻辑地址=页面号+页内偏移量$$

$$物理地址=页框号+页内偏移量$$

所以假设现在页面大小为4KB=2^12B=4096B。那么4097的页号就是1，页内偏移量为1，所以逻辑地址二进制串为

并且通过查表得知1号页面存放在9号页框，那么物理地址就是

总结：页面大小刚好是2的整数幂的好处就是

1. 逻辑地址的拆分更加迅速–如果每个页面大小为2^KB，用二进制表示逻辑地址，则末尾K为就是页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为2的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法操作，从而提升了运行速度。
2. 物理地址的计算更加迅速–根据逻辑地址得到的页号，查询页表找到对应存放的页框号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。

逻辑地址结构

实际上通过上面的例题我们已经掌握了逻辑地址的结构和应用，这里再给出严格定义，分页存储管理的逻辑地址结构如下图：

地址结构包括两个部分：前一部分为页号P，后一部分为页内偏移量W。在上图所示的例子中，地址为32位，其中0~11号为“页内偏移量”，或称“页内地址”，12~31位为“页号”。

如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是2^K个内存单元。如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有2^M个页面。所以页面大小<–>页内偏移量位数。

思考：页面大小一般设为什么数比较好？

当然就是2的整数幂啦，因为这样地址转换快，这也是现代操作系统大多的做法。当然考研的题中有些奇葩题（为了考而考）会出现页面大小不是2的整数幂的情况，那就只能按照最原始的公式计算了页号=逻辑地址/页面长度（取除法的整数部分），页内偏移量=逻辑地址%页面长度（取除法的余数部分）。

思考：从上面的结构中我们能否看出一些页号和页内偏移量的规律？

我们可以易知页号简介反映了页框的数量，页内偏移量简介反应了一个页框的大小。那么当一个页框很大时，页内偏移量也就大，K值也就大，那么所占的地址位数也就多，那么相应的页号所占位数32-K也就越小代表着此时页号就下了，也就说明页框数量变少了，其实这很正常，毕竟空间就那么大，一个存储单元变大了，相应的存储单元数量自然就少了。

总结