存储器管理

发表于   |   分类于   |  

前言

存储器是计算机系统的重要组成部分。在理想情况下存储器的速度应当非常快，能跟上处理器的速度，容量大而且价格也非常便宜，但目前无法同时满足这三个条件。这可以说是在存储器领域的CAP理论了。因此如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还能对系统性能有重大影响。

多级存储器结构

在现代的计算机中，存储层次根据具体的功能分工细化为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。越靠近CPU的地方存储介质的访问速度越快，价格越高，相应的容量也越小。如图所示：

在存储层次中，寄存器和主存储器又被称为可执行存储器，相比较于外存，计算机所采用的访问机制与时间均是不同的。进程可以在很少的时钟周期内使用一条load或者store指令对可执行存储器进行访问，但对外存的访问则需要通过I/O设备来实现，其中又涉及到中断、设备驱动程序，以及物理设备的运行，所需时间远远高于对可执行器的访问。

  1. 寄存器：寄存器的访问速度最快，一般以字(word)为单位，比如32位寄存器，64位寄存器。根据功能的不同又可以划分为不同的种类，比如指令寄存器、标志位寄存器、循环控制寄存器、条件操作寄存器、地址转换寄存器、用于栈操作的栈寄存器等，如ax,bx,cx,sp等。

  2. 高速缓存：高速缓存的容量大于或者远大于寄存器，而比主存储器要小不少，但是速度快于主存储器，它与寄存器的存在主要是缓和CPU指令执行的速度与访问内存的速度这一矛盾。根据程序执行的局部性原理，将主存中一些经常访问的程序或数据放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行的速度。在现代的计算机系统中，一般还分为多级高速缓存，如L1、L2、L3 Cache等。

  3. 主存储器：主要来保存进程运行时的程序和数据信息，它是一般意义上的内存。CPU控制部件只能从主存中获取程序和数据，与外部设备的交互也必须通过内存的地址空间来完成。

  4. 磁盘缓存：由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数，从而提高系统的I/O性能。磁盘缓存本身并不是一种实际的存储介质，它只是利用主存中的存储空间，来充当中间人的角色，可以实现成组提交等。

存储器的管理

操作系统的存储管理，负责对可执行存储器的分配、回收以及提供在存储层次间数据移动的管理机制。

内存分配方式

程序执行时需要从外存上被加载到内存才能被OS调度执行，对于内存的分配方式不同，对OS的性能也会产生很大的影响。

单一连续分配

这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。在这种分配方式中，可把内存分为系统区(Kenel Space)和用户区(User Space)，系统区仅提供给OS使用，通常放在内存低地址部分；用户区是指系统区以外的全部内存空间，提供给用户使用。

固定分区分配

固定分区式分配是最简单的一种可以运行多道程序的存储管理方式。它是将内存用户空间划分为若干固定大小的区域，每个分区中只装入一道作业，从而实现用户空间的多道作业并发运行。

  1. 划分分区的方法：分区大小相等，即使所有的内存分区大小相等，其缺点是缺乏灵活性。大了空间浪费，小了程序运行不了；分区大小不等，为了克服分区大小相等而缺乏灵活性这个缺点，可把内存划分成含有多个较小分区，适量中等分区以及少量大分区，从而根据程序的大小为之分配适当的分区。
  2. 内存分配：为了便于分配，可以将分区大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（是否分配）。

动态分区分配

动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三个问题。

分区分配中的数据结构

为了实现动态分区分配，系统中必须配置相应的数据结构，用来描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式:

  1. 空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。
  2. 空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针;在分区尾部则设置一后向指针，通 过前、后向链接指针，可将所有的空闲分区链接成一个双向链。

分区分配算法

为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业，或按照起始地址大小排序，或按照分区大小排序。各种分配算法都有优缺点：

  1. 首次适应算法(first fit)：按照起始地址大小升序排序，从链首开始搜索，直到找到大小合适的分区，并按需分配
  2. 循环首次适应算法(next fit)：同首次适应算法，只是不再从链首开始搜索，而是从上一次分配的起始地址开始搜索
  3. 最佳适应算法(best fit)：类似首次适应算法，只是按照分区大小升序排序
  4. 最坏适应算法(worst fit)：与最佳适应算法相反
  5. 快速适应算法(quick fit)：是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。

首次适应算法、循环首次适应算法、最佳适应、最坏适应算法算法一起，称为顺序搜索法。快速适应算法称为分类搜索算法。

分区分配操作

在动态分区存储管理方式中，主要的操作是分配内存和回收内存。

分配内存

系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请 求者;否则(即多余部分超过 size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。如图所示：

回收内存

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插 入点，此时可能出现以下四种情况之一:

  1. 回收区与插入点的前一个空闲分区 F1 相邻接，见图 4-8(a)。此时应将回收区与插入 点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1 的大小。
  2. 回收分区与插入点的后一空闲分区 F2 相邻接，见图 4-8(b)。此时也可将两分区合并， 形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
  3. 回收区同时与插入点的前、后两个分区邻接，见图 4-8(c)。此时将三个分区合并， 使用 F1 的表项和 F1 的首址，取消 F2 的表项，大小为三者之和。
  4. 回收区既不与 F1 邻接，又不与 F2 邻接。这时应为回收区单独建立一新表项，填写 回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

伙伴系统（Linux在大内存分配时，采用了此算法）

固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为 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) 的空闲分区，依此类推。在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。

可重定位的分区分配

简单的说就是先分配，不足时，如果内存碎片的总和大于需要的空间，就再通过移动已经分配了内存空间使其紧凑，从而腾出足够的空间来分配。因此她需要地址转换器等硬件构件的支持。

其他分配方式

哈希分配，对换（swapping)。对换主要是在内存空间不足时，将暂时没有执行的程序或者数据对换至swap分区，从而能加载新的程序与数据。可以含有进程对换，页对换，或者段对换等，一般程序执行过程中尽量避免对换的发生。

离散的分配

如果允许将一个进程直接分散地装入到许多不相邻接的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。如果离散分配的基本单位是页，则称为分页存储管理方式;如果离散分配的基本单位是段，则称为分段存储管理方式。

基本分页存储管理方式

在分页存储管理方式中，如果不具备页面对换功能，则称为基本的分页存储管理方式， 或称为纯分页存储管理方式

  1. 页面和物理块：分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从 0 开始。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如 0#块等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为 “页内碎片”。
  2. 页面大小：在分页系统中的页面其大小应适中。过大可能会导致页表过长，占用更多的空间，也会使对换效率下降，而过大又会增加内存页内碎片等。一般是512B到8KB，且为2的幂大小。
  3. 页表：系统为每个进程建立了一张页面映像表，简称页表。页表中包含了该进程所有的页面以及页面与物理块号的对应关系。
  4. 地址变换机构：能将用户地址空间中的逻辑地址变换为内存空间中的物理地址。

在基于分页的存储管理方式中，随着页表大小的增大，又可以进行多级页表的分页方式。

基本分段存储管理方式

在分段存储管理方式中，如果不具备段对换功能，则称为基本的分段存储管理方式， 或称为纯分段存储管理方式

  1. 分段：作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息，对应一段连续的地址空间。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等。
  2. 段大小：逻辑地址由段号和段内地址构成，在32位的字宽中，最多允许64K个段，每个段的大小最大为64KB。
  3. 段表：系统为每个进程建立一张段映射表，简称 “段表”。段表中包含了段号，以及对应物理分区空间地址。
  4. 地址变换机构：能将用户地址空间中的逻辑地址变换为内存空间中的物理地址。

段页式存储管理

段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段， 再把每个段分成若干个页，并为每一个段赋予一个段名。