274-内存分区

女爷i 2023-01-13 09:34 195阅读 0赞

## 内存分区 ##

**内存管理最基本的操作是由处理器把程序装入内存中执行。在大部分现代多道程序设计系统中，这往往还涉及一种称为虚拟内存的紧密方案**。  
**虚拟内存又基于分段和分页这两种基本技术或其中的一种**。在考虑虚拟内存技术之前，先考虑一些不涉及虚拟内存的简单技术。其中分区技术曾用于许多已经过时的操作系统中。另外两种技术，简单分页和简单分段，并未在实际中使用过。但在不考虑内存的前提下，先分析这两种技术有助于学习虚拟内存。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 固定分区 ##

在大多数内存管理方案中，可以假定操作系统占据了内存中的某些固定部分，内存的其余部分可供多个用户进程使用。管理用户内存空间的最简单的方案就是把它**分区**，从而形成若干个边界固定的区域。

## 分区大小 ##

**下图显示了固定分区的两种选择。**  
**一种是使用大小相等的分区**，在这种情况下，小于或等于分区大小的任何进程都可以装入到任何可用的分区中。如果所有的分区都满了，并且没有进程处于就绪态或运行态，则操作系统可用换出一个进程的所有分区，并装入另一个进程，使得处理器有事可做。  
**使用大小相等的固定分区有两个难点：**  
1、**程序可能太大而不能放到一个分区中**。在这种情况下，程序员必须使用覆盖技术设计程序，使得在任何时候该程序只有一部分需要放到内存中。当需要的模块不在时，用户程序必须把这个模块装入到程序的分区中，覆盖掉该分区中的任何程序和数据。  
2、**内存的利用率非常低**。任何程序，即使很小，都需要占据一个完整的分区。在下图的例子中，假设存在一个长度小于2MB的程序，当它被换入时，仍占据了一个8MB的分区。由于被装入的数据块小于分区大小，从而导致分区内部有空间浪费，这种现象称为内部碎片。  
**可以通过使用大小不等的分区来缓解这两个问题**，如下图b，但不能完全解决这两个问题。在下图b的例子中，可以容纳大小为16MB的程序而不需要覆盖。小于8MB的分区可用来容纳更小的程序，以产生较少的内部碎片。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

## 放置算法 ##

**对于大小相等的分区策略，进程在内存中的放置非常简单。只要存在可用的分区，进程就可以装入分区**。由于所有的分区大小相等，因而使用哪个分区都没有关系。如果所有的分区都被处于不可运行状态的进程所占据，那么这些进程中的一个必须被换出，从而为新进程让出空间。换出哪一个进程属于**调度问题。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**对于大小不等的分区策略，有两种方法可以把进程分配到分区**。最简单的方法是把每个进程分配到**能够容纳它**的**最小分区**。在这种情况下，每个分区都需要维护一个调度队列，用于保存从这个分区换出的进程，如上图a所示。这种方法的**优点**是：**如果所有进程都按这种方式分配，可以使每个分区内部浪费的空间（内部碎片）最少。**  
**尽管从单个分区的角度来看这种技术是最优的，但从整个系统来看它却不是最佳的**。  
在上图b的例子中，考虑这样的情况，在某个确定的时刻，系统没有大小在12-16MB之间的进程。在这种情况下，即使系统中有一些更小的进程本可以分配到16MB的分区中，但16MB的分区将仍会保持闲置。**因此，一种更可取的方法是为所有进程只提供一个队列，如上图b**。当需要把一个进程装入内存时，选择可以容纳该进程的最小可用分区。如果所有的分区都已经被占据，则必须进行交换。**一般优先考虑换出能容纳新进程的最小分区中的进程，或者考虑一些诸如优先级之类的其他因素，也可以优先选择换出被阻塞的进程，而不是就绪进程。**  
使用大小不等的分区为固定分区带来了一定的**灵活性**。此外，固定分区方案相对比较简单，只需要很小的操作系统软件和处理开销。**但是它也存在以下缺点：**  
1、分区的数目在系统生成阶段已经确定，它限制了系统中活动（没有挂起）进程的数目。  
2、由于分区的大小是在系统生成阶段事先设置的，因而小作业不能有效地利用分区空间。在事先知道所有作业的内存需求的情况下，这种方法也许是合理的，但大多数情况下这种技术是非常低效的。  
目前几乎已经没有说明场合会使用固定分区的方法。使用这种技术的一个成功的操作系统例子是早期的IBM主机操作系统OS/MFT（具有固定任务数的多道程序设计系统）

## 动态分区 ##

**为了克服固定分区的一些缺点，又出现了一种动态分区方法**。同样，这种方法也已经被很多更先进的内存管理技术所取代。使用该技术的一个重要的操作系统是IBM主机操作系统OS/MVT（具有可变任务数的多道程序设计系统）  
**对于动态分区，分区长度和数目是可变的**。当进程被装入内存时，系统会给它分配一块和它所需容量完全相等的内存空间，不多也不少。如下图所示，它使用64MB的内存。一开始，内存中只有操作系统，如下图a所示。被装入的前三个进程从操作系统结束处开始，分别占据了它们各自所需要的空间大小，如下图b、c、d所示，这样在内存末尾只剩下了一个“洞”，而这个“洞”对第4个进程来说就太小了。在某个时刻，内存中没有一个就绪进程操作系统换出进程2，如下图e所示，这便为装入一个新进程（即进程4）让出了足够的空间，如下图f所示。由于进程4比进程2小，就产生了另外一个小“洞”。然后，在另外一个时刻，内存中没有一个进程是就绪的，但处于就绪挂起状态的进程2是可用的。  
由于内存中没有足够的空间容纳进程2，操作系统换出进程1，如下图g所示，然后换入进程2，如下图h所示。  
**正如下图的例子所示，动态分区方法在开始时是很好的，但它最终会导致在内存中出现许多小的空洞**。随着时间的推移，内存中产生了越来越多的碎片，内存的利用率随之下降。这种现象称为外部碎片，指在所有分区外的存储空间变成越来越多的碎片，这与前面所说的内部碎片正好相对。  
**克服外部碎片的一种技术是压缩**：  
操作系统不时地移动进程，使得进程占用的空间连续，并且所有空闲空间连成一片。例如，在下图h中，压缩将会产生一块长度为16MB的空闲内存空间，足以装入另一个进程。压缩的困难在于它是一个非常费时的过程，并且浪费了处理器时间。注意，压缩需要动态重定位的能力。也就是说，必须能够把程序从内存的一块区域移动另一块区域，而不会使程序中的内存访问无效。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]

## 放置算法 ##

由于内存压缩非常费时，因而操作系统需要巧妙地把进程分配到内存中，塞住内存中的那些“洞”。当把一个进程装入或换入内存时，如果内存中有多个足够大的空闲块，则操作系统必须确定要为此进程分配哪个空闲块。  
可供考虑的有三种放置算法：**最佳适配、首次适配和下次适配**。这三种算法都是在内存中选择等于或大于该进程的空闲块。**差别在于：最佳适配选择与要求的大小最接近的块：首次适配从头开始扫描内存，选择大小足够的第一个可用块；下次适配从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块。**  
如下图a给出了经过多次放置和换出操作之后内存配置的例子。前一次操作在一个22MB的块中创建了一个14MB的分区。下图b给出了为满足一个16MB的分配请求，使用最佳适配、首次适配和下次适配三种放置算法的区别。最佳适配查找所有的可用块列表，最后使用了一个18MB的块，留下了2MB的碎片；首次适配产生了一个6MB的碎片；下次适配产生了一个20MB的碎片。  
各种方法的好坏取决于发生进程交换的次序以及这些进程的大小。但是，还可以得出一些一般性的结论。  
首次适配算法不仅是最简单的，而且通常也是最好和最快的。下次适配算法通常比首次适配的结果要差，它通常会导致在内存的末尾分配空间，导致的结果是通常位于存储空间末尾的最大空闲存储块很快被分裂成小碎片。因此使用下次适配算法可能需要更多次数的压缩。另一方面，首次适配算法会使得内存的前端出现很多小的空闲分区，并且每当进行首次适配查找时，都要经过这些分区。最佳适配算法尽管称为“最佳”，但通常性能却是最差的。这个算法需要查找满足要求的最小块，因而它可能保证产生的碎片尽可能地小。尽管每次存储请求总是浪费最小的存储空间，但结果却使得内存中很快产生许多很小的块，这些块通常很小以至于不能满足任何内存分配请求。**因此，它比其他算法需要更经常地进行内存压缩。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]

## 置换算法 ##

在使用动态分区的多道程序设计系统中，有时候会出现内存中的所有进程都处于阻塞态，并且即使进行了压缩，对一个新的进程仍然没有足够的内存空间。**为避免由于等待一个活动进程解除阻塞状态引起的处理器时间浪费，操作系统将把一个阻塞进程换出内存，给新进程或者处于就绪-挂起状态的进程让出空间。因此，操作系统必须选择要替换哪个进程。**

## 伙伴系统 ##

**固定分区和动态分区方案都有缺陷**。固定分区方案限制了活动进程的数目，并且如果可用分区的大小与进程大小非常不匹配，则内存空间的利用率非常低。动态分区的维护特别复杂，并且引入了进行压缩的额外开销。一种更有吸引力的折中方案就是伙伴系统。  
在伙伴系统中，可用内存块的大小为2^k个字，L<=K<=U,  
其中  
**2^L表示分配的最小块的尺寸**  
**2 ^ U表示分配的最大块的尺寸；通常2^U是可供分配的整个内存的大小**  
开始时，可用于分配的整个空间被看作是一个大小为2^U的块。  
如果请求的大小s满足2 ^ U-1<s<=2 ^ U,则分配整个空间。否则，该块被分成两个大小相等的伙伴，大小均为2 ^ U-1。如果有2 ^ U-2<s<=2 ^ U-1，则给该请求分配两个伙伴中的任何一个；否则，其中的一个伙伴又被分成两半。这个过程一直继续直到产生大于或等于s的最小块，并且分配给该请求。在任何时候，伙伴系统中为所有大小为2 ^ i的“洞”维护着一个列表。一个洞可以通过对半分裂从（i+1）列表中移出，并在i列表中产生两个大小为2 ^ i的伙伴。当i列表中的一对伙伴都变成未分配的块时，它们从该i列表中移出，合并成（i+1）列表中的一个块。请求一个大小为k的块并且k满足2 ^ i-1<k<=2^ i时，可使用下面的递归算法找到一个大小为2^i的洞：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**下图给出了一个初始化大小为1MB的例子**。第一个请求A为100KB，需要一个128KB的块。最初的块被划分为两个512KB的伙伴，第一个又被划分成两个256KB的伙伴，并且其中的第一个又划分成两个128KB的伙伴，这两个128KB的伙伴中的一个分配给A。下一个请求B需要256KB的块，因为已经有这样的一个块，随即分配给它。在需要时，这个分裂和合并的过程继续进行。注意，当E被释放时两个128KB的伙伴合并成一个256KB的块，这个256KB的块又立即与它的伙伴合并成一个512KB的块。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**下图给出了一个表示当释放B的请求后的伙伴系统分配情况的二叉树**。叶节点表示内存中的当前分区，如果两个伙伴都是叶节点，则至少有一个必须已经被分配出去了，否则它们将合并成一个更大的块。  
**伙伴系统是一个合理的折中方案，它克服了固定分区和可变分区方案的缺陷**。但在当前的操作系统中，**基于分页和分段机制的虚拟内存更先进**。然而，**伙伴系统**在并行系统中有很多应用\*\*，它是为并行程序分配和释放内存的一种有效方法。\*\*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]

## 重定位 ##

在考虑解决分区技术的缺陷之前，必须先解决与进程在内存中的放置相关的一个遗留问题。当使用如图7.3a所示的固定分区方案时，一个进程可以总是被指定到同一个分区。也就是说，当装入一个新进程时，不论选择哪一个分区，当这个进程以后被换出又换入时，仍旧使用这个分区。 在这种情况下，需要使用一个简单的重定位加载器：当一个进程被首次加载时，代码中的相对内存访问被绝对的内存地址代替，这个绝对地址由进程被加载到的基地址确定。  
对于大小相等的分区（如图7.2所示）以及只有一个进程队列的大小不等的分区（如图7.3b）的情况，一个进程在它的生命周期中可能占据不同的分区。当第一次创建一个进程映像时，它被装入内存中的某个分区。动态分区也存在同样的情况。观察图7.4c和图7.4h，进程2两次被换入时占用了两个不同的内存区域。此外，当使用压缩时，内存中的进程也可能发生移动。因此，进程访问的（指令和数据单元的）位置不是固定的。当进程被换入或者在内存中移动时，指令和数据单元的位置会发生改变。为解决这个问题，需要对几种地址类型进行区分。逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问之前必须把它转换成物理地址。相对地址是逻辑地址的一个特例，是相对于某些已知点（通常是程序的开始处）的存储单元。物理地址或绝对地址是数据在内存中的实际位置。  
**系统采用运行时动态加载的方式把使用相对地址的程序加载到内存**。通常情况下，被加载进程中的所有内存访问都相对于程序的开始点。因此，在执行包括这类访问的指令时，需要一个硬件机制把相对地址转换成物理内存地址。  
**下图给出了实现这类地址转换的一种典型方法。**  
**当进程处于运行态时，一个特殊的处理器寄存器，有时称做基址寄存器，其内容是程序在内存中的起始地址**。**还有一个界限寄存器指明程序的终止位置。当程序被装入内存或该进程的映像被换入时，必须设置这两个寄存器**。在进程的执行过程中会遇到相对地址，包括指令寄存器的内容、跳转或调用指令中的指令地址以及加载和存储指令中的数据地址。每个这样的相对地址都经过处理器的两步操作。首先，基址寄存器中的值加上相对地址产生一个绝对地址；然后，得到的结果与界限寄存器的值相比较，如果这个地址在界限范围内，则继续该指令的执行；否则，向操作系统发出一个中断信号，操作系统必须以某种方式对这个错误做出响应。  
**下图的方案使得程序可以在执行过程中被换入和换出内存**。并且它还提供了每个进程映像根据基址和界限寄存器的内容被隔离开，以免受到其他进程的越权访问。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/ba49de2e2c5a4927b3c6777b10d40a77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20221022/f232930b9fa34a729910ff5acacd2b90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20221022/9e0862f32d6c437e9ff69db6e6280858.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20221022/2b71c0177b044b8e9f7ba0b791f10d62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20221022/7571ec43fd0f4890a611731037982f7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20221022/2b064f52500c4fff80f68569595ef479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20221022/44fe97aa72e0499d8356bdea3ff9228b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20221022/48694d44da204f738be0b325d640fb80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]: /images/20221022/55e796f4fad244acad1942d1e412981e.png