[科普中国]-动态存储分配

存储分配方式

存储分配所要解决的问题是多道程序之间如何共享主存的存储空间。解决存储分配问题有三种方式：直接存储分配方式、静态存储分配方式、动态存储分配方式。

直接存储分配方式直接存储分配方式要求存储器的可用空间已经确定，且确保各程序所用的地址之间互不重叠。缺点是用户感到不方便，存储器的利用率也不高。

静态存储分配方式静态存储分配方式中。在程序被装入、连接时，才确定它们在主存中的相应位置(物理地址)。系统必须分配其要求的全部存储空间．否则不能装入该用户程序。程序将占据着分配给它的存储空间直到程序结束。该存储空间的位置固定不变，也不能动态地申请存储空间。这种方式无法实现用户对存储空间的动态扩展，而且也不能有效地实现存储器资源的共享。

动态存储分配方式动态存储分配方式是不一次性将整个程序装入到主存中。可根据执行的需要，部分地动态装入。同时，在装入主存的程序不执行时，系统可以收回该程序所占据的主存空间。再者，用户程序装入主存后的位置，在运行期间可根据系统需要而发生改变。此外，用户程序在运行期间也可动态地申请存储空间以满足程序需求。由此可见，动态存储分配方式在存储空间的分配和释放上，表现得十分灵活，现代的操作系统常采用这种存储方式。2

重定位为了实现静态、动态存储分配方式．必须把逻辑地址和物理地址分开井将逻辑地址定位为物理地址。为此，首先耍弄清地址空间和存储空间这两个概念。编译系统总是从零号地址单元开始，为目标程序指令顺序分配地址。这些地址故称为相对地址，相对地址的集合称为逻辑地址空间，简称地址空间。存储空间是指主存中一系列存储信息的物理单元的集合，这些物理单元的编号称为物理地址或绝对地址。由于用户程序的装入而引起地址空间中的相对地址转化为存储空间中的绝对地址的地址变换过程，称为地址重定位。实现地址重定位的方法有两种：静态地址重定位和动态地址重定位。

静态地址重定位静态地址重定位是指用户程序在装入时由装配程序一次完成。即地址变换只是在装入时一次完成，以后不再改变。这种重定位方式实现起来比较简单，在早期多道程序设计中大多采用这种方案：它的缺点是用户程序必须分配一个连续的存储空间，难以实现程序和数据的共享。

动态地址重定位动态地址重定位是在程序执行的过程中，当CPU要对存储器进行访问时，通过硬件地址变换机构，将要访问的程序和数据地址转换成主存地址。

动态地址重定位的优点是：

(1)程序执行时可以在主存中浮动．有利于提高主存的利用率和存储空间使用的灵活性。

(2)有利于程序段的共享实现。当系统提供多个重定位寄存器时，规定某些或某个重定位寄存器作为共享程序段使用，就可实现主存中的相应程序段为多个程序所共享。

(3)为实现虚拟存储管理提供了基础。有了动态地址重定位的概念和技术，程序中的信息块可根据执行时的需要分配在主存中的任何区域，还可以覆盖或交换不再使用的区域，使得程序的逻辑地址空间可比实际的物理存储空间大．从而实现了虚拟存储管理功能。

动态地址重定位的缺点是实现存储器管理的软件比较复杂以及需要附加更多的硬件支持。

动态存储分配的方法首次适应算法(first fit)我们以空闲分区链为例来说明采用 首次适应算法(first fit)时的分配情况。FF 算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。

循环首次适应算法(next fit)该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。

最佳适应算法（Best Fit）算法：将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”。

优点：第一次找到的空闲分区是大小最接近待分配内存作业大小的；

缺点:产生大量难以利用的外部碎片。

最坏适应算法（Worst Fit）算法：与最佳适应算法刚好相反，将空闲分区链的分区按照从大到小的顺序排序形成空闲分区链，每次查找时只要看第一个空闲分区是否满足即可。

优点：效率高，分区查找方便；

缺点：当小作业把大空闲分区分小了，那么，大作业就找不到合适的空闲分区。

快速适应算法(quick fit)该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如 2 KB、4 KB、8 KB 等，对于其它大小的分区，如 7 KB 这样的空闲区，既可以放在 8 KB 的链表中，也可以放在一个特殊的空闲区链表中。该算法的优点是查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。该算法的缺点是在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的作法。3