第四章 存储器管理 4.3 连续分配存储管理方式

一、单一连续分配

    内存分为两个区域：系统区，用户区。

    应用程序装入到用户区，可使用用户区全部空间。内存中仅驻留一道用户程序，整个用户区为一个用户独占。

二、固定分区分配

    1.将内存用户空间划分为若干个固定大小的区域，每个区域称为一个分区，在每个分区中只装入一道作业。分区大小可以相等可以不等。

    2.分区说明表：指出可用于分配的分区数以及每个区的大小、起始地址及状态 。

    3.作业装入内存时，内存分配程序检索分区说明表。

    从中找出一个尚未使用的满足大小要求的分区分配给该作业，然后修改分区的状态。

    如果找不到合适的分区就拒绝为该作业分配内存。

    4.内零头：内存中已分配给用户但未被利用的区域称

三、动态分区分配

    根据进程的实际需要，动态地为之分配连续的内存空间。即分区的边界可以移动，分区的大小是可变的 。

    1.分区分配中数据结构

    空闲分区表

    空闲分区链

    2.分区分配操作——分配内存和回收内存

    3.分区分配算法

1. 最佳适应算法(Best fit: BF) 

        将存储空间中所有的空白区按其大小递增的顺序链接起来，组成一空白区链。  

        寻找大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的零头最小。

        优点： 选中合适的分区，不会对大分区进行切割，保留的大分区可以满足大作业的需求。 

        缺点：

        ①在每次分配时，总是产生最小的空白区。因此，经过一段时期后，存储空间中可能留许多这样的空白区，由于其太小而无法使用。

        ②：在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。 所以，这种算法乍看起来是最佳的，其实则不然。 

    B.最坏适应算法(Worst fit: WF)

        为了支持这个算法的实现，空白块应以大小递减的顺序链接起来。

        在为作业选择存储区域时，总是寻找最大的空白区。

        优点：在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的

        缺点：由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足

    C.首次适应算法(First Fit: FF) 

        每个空白区按其在存储空间中地址递增的顺序链在一起。

        在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块。

        选择的空白区被分成两部分。一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。

        优点：

        算法简单，查找速度快；

        留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。                 

        缺点：

        常常利用一个大的空白区适应小作业的请求，从而留下一些较小的无法用的空白区，在低地址部分会积累大量外零头，存储空间利用率不高；

        由于所有的请求都是从空白区链的始端开始查找，因而这些小而无用的空白区集中在这个链的前端，相应地，一些较大空白区在链的尾端才能发现，这种情况将使找到合适空白区的速度降低。 

    D.下次适应算法(Next fit: NF)

        首次适应算法的一种变形，故也被称为带旋转指针的首次适应算法。

        把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。

    E.快速适应算法（Quik fit:QF)

        将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。 这样，系统中存在多个空闲分区链表。

        在内存中设立一张管理索引表，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。

        分配过程：根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可。

    F.伙伴系统

        在伙伴系统中，可用内存块的大小为 2^k (1≤k≤m)

        2¹表示分配的最小块的尺寸：2Byte

        2^m表示分配的最大块的尺寸，通常是可供分配的整个内存空间的大小。

        进程请求大小为n的存储空间时：

        ①计算一个 i 值：使 2^i－1 < n ≤ 2ⁱ，在空闲分区大小为 2ⁱ 的空闲分区链表中查找。    

        ②若找到，即把该空闲分区分配给进程。  

        ③否则，表明长度为2i的空闲分区已经耗尽，在分区大小为2^i＋1的空闲分区链表中寻找

        ④若找到大小为2^i＋1 的空闲分区，把该空闲分区分为相等的两个分区，其中一个用于分配，另一个加入分区大小为 2ⁱ 的空闲分区链表中。

        ⑤否则继续查找大小为2i＋2 的空闲分区…… 

        释放内存的过程：

        把释放的块放入空闲块数组，合并满足条件的空闲块

        合并条件：大小相同；地址相邻；低地址空闲块的起始地址位数为2ⁱ⁺¹

    E.哈希算法

四、可重定位分区分配——解决外零头的问题

     1.紧凑

    将内存中的所有作业进行移动，使它们全都相邻接，把原来分散的多个小分区合成一个大分区。

    为了提高内存利用率，系统在运行过程中经常需要进行“紧凑”。需要对作业中的某些地址部分和地址常数等进行调整。 一个较实用且可行的办法是采用动态重定位技术。

    2.动态重定位技术

    动态重定位机制需要硬件的支持， 即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。 

    程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。