操作系统内存管理——分区、页式、段式管理

1. 内存管理方法

        内存管理主要包括虚地址、地址变换、内存分配和回收、内存扩充、内存共享和保护等功能。 

2. 连续分配存储管理方式

      连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。

2.1 单一连续存储管理

     在这种管理方式中，内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。 2.2 分区式存储管理

       为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。

       分区式存储管理引人了两个新的问题：内碎片和外碎片。

      内碎片是占用分区内未被利用的空间，外碎片是占用分区之间难以利用的空闲分区        为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态       分区式存储管理常采用的一项技术就是内存紧缩 2.2.1 固定分区(nxedpartitioning)。

        固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行       优点：易于实现，开销小。

      缺点主要有两个：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。

2.2.2动态分区(dynamic partitioning)。

        动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有内碎片。但它却引入了另一种碎片 下面列出了几种常用的分区分配算法：

        最先适配法        下次适配法        最佳适配法        最坏适配法  2.3 伙伴系统

        固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。
        伙伴系统规定，无论已分配分区或空闲分区，其大小均为 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 内存紧缩

          内存紧缩：将各个占用分区向内存一端移动，然后将各个空闲分区合并成为一个空闲分区。

        这种技术在提供了某种程度上的灵活性的同时，也存在着一些弊端，例如：对占用分区进行内存数据搬移占用

 

        

                               图8.12

      堆结构的存储管理的分配算法：

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

     释放内存空间执行内存紧缩：

     回收用户释放的空闲块就比较麻烦.由于系统的可利用空间始终是一个绝址连续的存储块，因此回收时必须将所释放的空间块合并到整个堆上去才 能重新使用，这就是”存储策缩”的任务.通常，有两种做法：

      一种是一旦有用户释放存储块即进行回收紧缩，例始，图8.12 (a)的堆，在c串释放存储块时即回收紧缩，例如图8.12 (c)的堆，同时修改串的存储映像成图8.12(d)的状态；

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

                     图8.13  a 紧缩前 b紧缩后

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

      （1)计算占用块的新地址。从最低地址开始巡査整个存储空间，对每一个占用块找到它在紧缩后的新地址。 为此,需设立两个指针随巡查向前移动,这两个指针分别指示占用 块在紧缩之前和之后的原地址和新地址。因此,在每个占用块的第-·个存储单位中，除了 设立长度域(存储该占用换的大小）和标志域(存储区别该存储块是占用块或空闲块的标 志）之外，还需设立一个新地址城，以存储占用块在紧缩后应有的新地址，即建立一张新， 旧地址的对照表m

       (2)修改用户触初始变量表，以便在存储紧缩后用户程序能继续正常运行*。

       (3)检查每个占用块中存储的数据， 若有指向其他存储换的指针，则需作相应修改.

       (4)将所有占用块迁移到新地址走，这实质上是作传送数据的工作。

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

       可见,存储紧缩法比无用单元收集法更为复杂，前者不仅要传送数据（进行占用块迁移），而且还有需要修改所有占用块中的指针值。因此，存储紧缩也是个系统操作，且非不得已就不用。

3. 覆盖和交换技术

 3.1 覆盖技术

        引入覆盖        覆盖技术的原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序必要部分        在任何时候只在内存中保留所需的指令和数据；当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的内存空间；

       如在同一时刻，CPU只能执行B，C中某一条。B，C之间就可以做覆盖。

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

      覆盖的实现方式有两种：以函数库方式实现或操作系统支持。

3.2 交换技术

      交换原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swap in）。

     交换技术优点之一是增加并发运行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比交换技术另一个显著的优点是不影响程序结构。交换技术本身也存在着不足，例如：对换人和换出的控制增加处理器开销；程序整个地址空间都进行对换，没有考虑执行过程中地址访问的统计特性。

3.3 覆盖与交换比较

       1）与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。

       2）交换主要是在进程与作业之间进行，而覆盖则主要在同一作业或进程内进行。 另外覆盖只能覆盖那些与覆盖程序段无关的程序段。

4. 页式和段式存储管理

         在前面的几种存储管理方法中，为进程分配的空间是连续的，使用的地址都是物理地址。如果允许将一个进程分散到许多不连续的空间，就可以避免内存紧缩，减少碎片。基于这一思想，通过引入进程的逻辑地址，把进程地址空间与实际存储空间分离，增加存储管理的灵活性。地址空间和存储空间两个基本概念的定义如下：

地址空间：将源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。地址空间是逻辑地址的集合。

存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址存储空间是物理地址的集合。

根据分配时所采用的基本单位不同，可将离散分配的管理方式分为以下三种：
页式存储管理、段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。

5. 页式存储管理

4.1 基本原理

        将程序的逻辑地址空间划分为固定大小的页        

      页式管理方式的优点是：

       1）没有外碎片，每个内碎片不超过页大比前面所讨论的几种管理方式的最大进步是，

       2）一个程序不必连续存放。

       3）便于改变程序占用空间的大小       缺点是：要求程序全部装入内存，没有足够的内存，程序就不能执行。

4.2 页式管理的数据结构

         在页式系统中进程建立时，操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间，如果允许进程动态地申请空间，操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能，必须记录系统内存中实际的页框使用情况。操作系统还要在进程切换时，正确地切换两个不同的进程地址空间到物理内存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能，         进程页表：完成逻辑页号         

                                 图4-1 页表

        物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况，其数据结构可采用位示图和空闲页链表。

        对于位示图法，即如果该页面已被分配，则对应比特位置1，否置0.

                                  图4-2 页面表

        请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换也可以结合到各进程的        

                                       图4-3 请求表

4.3 页式管理地址变换

来源：FishBear_move_on