操作系统内存管理

动态分区方式算法复杂，回收空暇分区时须要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。
        伙伴系统规定，不管已分配分区或空暇分区。其大小均为 2 的 k 次幂，k 为整数， l≤k≤m，当中：
        2^1 表示分配的最小分区的大小。
        2^m 表示分配的最大分区的大小。
        通常 2^m是整个可分配内存的大小。 
        如果系统的可利用空间容量为2^m个字。 则系统開始执行时， 整个内存区是一个大小为2^m的空暇分区。在系统执行过中。 因为不断的划分，可能会形成若干个不连续的空暇分区，将这些空暇分区依据分区的大小进行分类。对于每一类具有同样大小的全部空暇分区，单独设立一个空暇分区双向链表。

这样。不同大小的空暇分区形成了k(0≤k≤m)个空暇分区链表。 
       分配步骤：
       当须要为进程分配一个长度为n 的存储空间时:
       首先计算一个i 值，使 2^(i－1) <n ≤ 2^i。
       然后在空暇分区大小为2^i的空暇分区链表中查找。
       若找到，即把该空暇分区分配给进程。
       否则。表明长度为2^i的空暇分区已经耗尽，则在分区大小为2^(i＋1)的空暇分区链表中寻找。
       若存在 2^(i＋1)的一个空暇分区，则把该空暇分区分为相等的两个分区。这两个分区称为一对伙伴，当中的一个分区用于配，   而把还有一个增加分区大小为2^i的空暇分区链表中。
       若大小为2^(i＋1)的空暇分区也不存在，则须要查找大小为2^(i＋2)的空暇分区。 若找到则对其进行两次切割：
              第一次，将其切割为大小为 2^(i＋1)的两个分区。一个用于分配，一个增加到大小为 2^(i＋1)的空暇分区链表中；
              第二次，将第一次用于分配的空暇区切割为 2^i的两个分区。一个用于分配，一个增加到大小为 2^i的空暇分区链表中。
      若仍然找不到，则继续查找大小为 2^(i＋3)的空暇分区，以此类推。
      由此可见。在最坏的情况下，可能须要对 2^k的空暇分区进行 k 次切割才干得到所需分区。
      与一次分配可能要进行多次切割一样。一次回收也可能要进行多次合并，如回收大小为2^i的空暇分区时，若事先已存在2^i的空暇分区时。则应将其与伙伴分区合并为大小为2^i＋1的空暇分区，若事先已存在2^i＋1的空暇分区时，又应继续与其伙伴分区合并为大小为2^i＋2的空暇分区，依此类推。
        在伙伴系统中，其分配和回收的时间性能取决于查找空暇分区的位置和切割、合并空暇分区所花费的时间。与前面所述的多种方法相比較，因为该算法在回收空暇分区时，须要对空暇分区进行合并，所以其时间性能比前面所述的分类搜索算法差。但比顺序搜索算法好。而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。 须要指出的是，在当前的操作系统中，普遍採用的是以下将要讲述的基于分页和分段机制的虚拟内存机制，该机制较伙伴算法更为合理和高效，但在多处理机系统中，伙伴系统仍不失为一种有效的内存分配和释放的方法。得到了大量的应用。

 2.4 内存紧缩
        内存紧缩：将各个占用分区向内存一端移动，然后将各个空暇分区合并成为一个空暇分区。
        这样的技术在提供了某种程度上的灵活性的同一时候，也存在着一些弊端，比如：对占用分区进行内存数据搬移占用CPU时间；假设对占用分区中的程序进行“浮动”。则其重定位须要硬件支持。

        紧缩时机：每一个分区释放后。或内存分配找不到满足条件的空暇分区时。

        堆结构的存储管理的分配算法：
        在动态存储过程中，无论哪个时刻，可利用空间都是-一个地址连续的存储区，在编译程序中称之为"堆"，每次分配都是从这个可利用空间中划出一块。事实上现办法是：设立一个指針，称之为堆指针。始终指向堆的最低（或锻联）地址。当用户申请N个单位的存储块时，堆指针向高地址（或 低地址）称动N个存储单位，而移动之前的堆指针的值就是分配给用户的占用块的初始地址。比如。某个串处理系统中有A、B、C、D这4个串，其串值长度分别為12,6,10和8. 如果堆指针free的初值为零，则分配给这4个串值的存储空间的初始地址分别为0.12.18和 28,如图8.12(a)和（b)所看到的。分配后的堆指针的值为36。

因此。这样的堆结构的存储管理的分配算法很easy，
        释放内存空间运行内存紧缩：
        回收用户释放的空暇块就比較麻烦.因为系统的可利用空间始终是一个绝址连续的存储块。因此回收时必须将所释放的空间块合并到整个堆上去才 能又一次使用，这就是"存储策缩"的任务.通常，有两种做法：
        一种是一旦实用户释放存储块即进行回收紧缩，例始，图8.12 (a)的堆，在c串释放存储块时即回收紧缩，比如图8.12 (c)的堆，同一时候改动串的存储映像成图8.12(d)的状态。

        还有一种是在程序运行过程中不回收用户随时释放的存储块。直到可利用空同不够分配或堆指针指向最高地址时才进行存储紧缩。此时紧缩的目的是将堆中全部的空间块连成一块，即将全部的占用块部集中到 可利用空间的低地地区。而剩余的高地址区成为一整个地继连续的空暇块，如图8.13所看到的。当中（a）为紧缩前的状态，(b)为紧缩后的状态。

        和无用单元收集类似，为实现存储紫编,首先要对占用块进行“标志”。标志算法和无用单元收集类同(存储块的结构可能不同）,其次需进行下列4步雄作：
        1)计算占用块的新地址。

从最低地址開始巡査整个存储空间，对每个占用块找到它在紧缩后的新地址。 为此,需设立两个指针随巡查向前移动,这两个指针分别指示占用 块在紧缩之前和之后的原地址和新地址。因此,在每个占用块的第-·个存储单位中，除了 设立长度域(存储该占用换的大小）和标志域(存储差别该存储块是占用块或空暇块的标 志）之外。还需设立一个新地址城。以存储占用块在紧缩后应有的新地址，即建立一张新， 旧地址的对比表m
        2)改动用户触初始变量表。以便在存储紧缩后用户程序能继续正常执行*。

        3)检查每一个占用块中存储的数据， 若有指向其它存储换的指针。则需作对应改动.
        4)将全部占用块迁移到新地址走，这实质上是作传送数据的工作。

        至此。完毕了存储紧缩的操作。最后,将堆指针赋以新值（即紧缩后的空暇存储区的最低地址）。

        可见,存储紧缩法比无用单元收集法更为复杂。前者不仅要传送数据（进行占用块迁移），并且还有须要改动全部占用块中的指针值。

因此。存储紧缩也是个系统操作，且非不得已就不用。

3. 覆盖和交换技术
3.1 覆盖技术
        引入覆盖 (overlay)技术的目标是在较小的可用内存中执行较大的程序。这样的技术经常使用于多道程序系统之中，与分区式存储管理配合使用。

        覆盖技术的原理：一个程序的几个代码段或数据段，依照时间先后来占用公共的内存空间。将程序必要部分(经常使用功能)的代码和数据常驻内存；可选部分(不经常使用功能)平时存放在外存(覆盖文件)中，在须要时才装入内存。

不存在调用关系的模块不必同一时候装入到内存，从而能够相互覆盖。

        在不论什么时候仅仅在内存中保留所需的指令和数据；当须要其他指令时，它们会装入到刚刚不再须要的指令所占用的内存空间；
        如在同一时刻，CPU仅仅能运行B。C中某一条。B，C之间就能够做覆盖。

 

        覆盖技术的缺点是编程时必须划分程序模块和确定程序模块之间的覆盖关系，添加编程复杂度；从外存装入覆盖文件，以时间延长换取空间节省。

        覆盖的实现方式有两种：以函数库方式实现或操作系统支持。
3.2 交换技术
        交换 (swapping)技术在多个程序并发运行时。能够将临时不能运行的程序（进程）送到外存中。从而获得空暇内存空间来装入新程序（进程），或读人保存在外存中而处于就绪状态的程序。

交换单位为整个进程的地址空间。交换技术经常使用于多道程序系统或小型分时系统中，由于这些系统大多採用分区存储管理方式。与分区式存储管理配合使用又称作“对换”或“滚进／滚出” (roll-in／roll-out)。
        原理：暂停运行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由堵塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。

        交换技术长处之中的一个是添加并发执行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比交换技术还有一个显著的长处是不影响程序结构。

交换技术本身也存在着不足。比如：对换人和换出的控制添加处理器开销；程序整个地址空间都进行对换，没有考虑执行过程中地址訪问的统计特性。
3.3 覆盖与交换比較
        1）与覆盖技术相比，交换不要求程序猿给出程序段之间的覆盖结构。
        2）交换主要是在进程与作业之间进行，而覆盖则主要在同一作业或进程内进行。 另外覆盖仅仅能覆盖那些与覆盖程序段无关的程序段。