操作系统-3.3-内存(动态分区分配算法&&基本分页存储管理详解）

男娘i 2023-10-03 13:18 28阅读 0赞

#### 文章目录 ####

*  操作系统-3.3-内存
 *   *  5.动态分区分配算法
     *   *  5.1首次适应算法
         *  5.2最佳适应算法
         *  5.3最坏适应算法
         *  5.4邻近适应算法
         *  5.5总结
     *  6.基本分页存储管理
     *   *  6.1把“固定分区分配“改造为”非连续分配版本“
         *  6.2分页存储管理的基本管理
         *  6.3如何实现地址的转换？
         *  6.4逻辑地址结构
         *  6.5页表
         *  6.6总结

## 操作系统-3.3-内存 ##

> 本文内容讲解**动态分区分配算法**和非连续分配管理方式中的**基本分页存储管理**。

### 5.动态分区分配算法 ###

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

#### 5.1首次适应算法 ####

*  **算法思想**：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
 *  **如何实现**：**空闲分区以地址递增的次序排列**。每次分配内存时顺序查找**空闲分区链**（或**空闲分区表**），找到大小能满足要求的第一个空闲分区。

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

#### 5.2最佳适应算法 ####

*  **算法思想**：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
 *  **如何实现**：空闲分区**按容量递增次序链接**。每次分配内存时顺序查找**空闲分区链**（或**空闲分区表**），找到大小能满足要求的第一个空闲分区。
 *  **缺点**：每次都选最小的分区进行分配，会留下越来越多的，很小的，难以利用的内存块。因此这种方法**会产生很多外部碎片。**

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

#### 5.3最坏适应算法 ####

*  **算法思想**：为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
 *  **如何实现**：空闲分区**按容量递减次序链接**。每次分配内存时顺序查找**空闲分区链**（或**空闲分区表**），找到大小能满足要求的第一个空闲分区。
 *  **缺点**：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

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

#### 5.4邻近适应算法 ####

*  **算法思想**：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
 *  **如何实现**：**空闲分区以地址递增的顺序排列**（可排成一个**循环链表**）。每次分配内存时**从上次查找结束的位置开始**查找**空闲分区链**（或**空闲分区表**)，找到大小能满足要求的第一个空闲分区。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 4]

#### 5.5总结 ####

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

### 6.基本分页存储管理 ###

*  **连续分配**：为用户进程分配的必须是一个**连续的内存空间**。
 *  **非连续分配**：为用户进程分配的可以是一些**分散的内存空间**。

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

#### 6.1把“固定分区分配“改造为”非连续分配版本“ ####

> 思考：连续分配方式的缺点

考虑支持多道程序的两种连续分配方式：

1.  **固定分区分配**：缺乏灵活性，会产生大量的内部碎片，内存的利用率很低。
2.  **动态分区分配**：会产生很多外部碎片，虽然可以用“紧凑”技术来处理，但是“紧凑”的时间代价很高。

如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再讲行“紧凑”。

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

基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。**如果把分区大小设置的更小一些，内部碎片会更小，内存利用率会更高。**

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

#### 6.2分页存储管理的基本管理 ####

*  将**内存空间**分为一个个**大小相等的分区**（比如:每个分区4KB），每个分区就是一个“**页框”**，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”）页框号**从0开始**。
 *  将**用户进程的地址空间**也分为**与页框大小相等**的一个个区域，称为“页”或“**页面**”。每个页面也有一个编号，即“**页号**”，页号也是**从0开始**。  
    （注：进程的最后一个页面可能没有一个页框那么大。因此，**页框不能太大，否则可能产生过大的内部碎片**)
 *  操作系统**以页框为单位为各个进程分配**内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的**页面**与内存的**页框**有**一一对应**的关系。  
    各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

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

#### 6.3如何实现地址的转换？ ####

> 进程在内存**连续存放**时，操作系统是如何实现逻辑地址到物理地址的转换的？

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

1.  要算出逻辑地址对应的**页号**。页号=逻辑地址/页面长度
2.  要知道该页号对应**页面在内存中的起始地址**。（操作系统需要用某种数据结构记录进程各个页面的起始位置）
3.  要算出逻辑地址**在页面内的“偏移量”**。页内偏移量=逻辑地址%页面长度
4.  **物理地址=页面始址＋页内偏移量**。

> 我们看个栗子：

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

#### 6.4逻辑地址结构 ####

分页存储管理的逻辑地址结构组成：页号+页面偏移量。

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

#### 6.5页表 ####

为了能知道进程的每个页面在内存中存放的位置，操作系统要**为每个进程建立一个页表**。

1.  一个进程对应一张页表。
2.  进程的每一页对应一个页表项。
3.  每个**页表项**由“**页号**”和“**块号**”组成。
4.  页表记录**进程页面和实际存放的内存块之间的对应关系**。
5.  每个页表项的长度是相同的，**页号是“隐含”的**。

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

#### 6.6总结 ####

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/7b694eb4bff0463ebcf687dd25be978e.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/4d0f76a3553144a88ffabeed1ab965c4.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/714819441874402f9f15ee2ce2748e60.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/8e2531f5c31b4623bb114ad6c074aa12.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/1852201c29b2499a93684e00dad2b38a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/930eb53a1aae41a99355abe703eb68ed.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/7984e3582d654740b2a1921977a6de8d.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/d1296c56f0e14be6b519bb23811fb79c.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/db169e93ba4f48f4a86079d590c36375.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/32975c3631e94d72ac5994e1350e634f.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/90c2458692034310bd628811c5b8f14e.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/d286acc84ce648c3816763e94899cca0.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/d9b8252757944236b7d8de20863de3cf.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/8cfff30c573c4b889d7b66e4c503dcf2.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/af871709ca0e4a26bee042cdaf1f6426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70