动态分区分配计算

刺骨的言语ヽ痛彻心扉 2023-09-24 20:37 22阅读 0赞

### 动态分区分配 ###

内存连续分配管理分为：

*  单一连续分配
 *  固定分区分配
 *  动态分区分配（本篇所讲）

#### 首次适应算法（First Fit，FF） ####

该算法又称最先适应算法，要求空闲分区按照首地址递增的顺序排列。

优点：优先使用低地址部分空闲分区，保留了高地址部分的大量空闲分区，有利于大程序或作业的装入。  
缺点：内存的低地址区留下了许多难以利用的很小空闲分区，即内存“碎片”；算法每次都从低地址部分开始查找，这增加了查找可用空闲分区的开销。

注：外碎片是指由于空闲空间太小，以致于无法分配给程序或作业的内存空闲区域，如动态分区分配中存在外碎片； 内碎片是指已经被分配出去，却不能被充分利用的内存空间区域，如固定分区分配中存在内碎片。

#### 循环首次适应算法（Next Fit，NF） ####

空闲分区按照首地址递增的顺序排列。每次内存分配时，不再从表头（或链首）开始查找，而是从上次分配的空闲分区的下一个空闲分区开始顺序查找。

优点：内存的空闲分区分布较均匀，减少查找空闲分区的开销。  
缺点：经多次分配后，内存缺少较大的空闲分区，以分配给较大的程序或作业。

#### 最佳适应算法（Best Fit，BF） ####

或称最优适应算法，该算法要求将空闲分区按从小到大的顺序排列。

优点：较大的空闲分区被尽量的保留下来，有利于大程序或作业的分配。  
缺点：容易产生内存碎片；每次分配后需要更新空闲分区表（链），增加了系统开销；分割后小的空闲分区处于分区表（链）首，增加了查找空闲分区的时间。

#### 最坏适应算法（Worst Fit，WF） ####

又称最差适应算法，该算法空闲分区按从大到小的顺序排列的。

优点：不会产生过多的碎片，有利于中、小程序或作业，且查找效率高。  
缺点：影响大程序或作业的分配。此外，每次分配后需要更新空闲分区表（链），增加了系统开销。

#### 四种算法比较 ####

从搜索速度上看，FF具有最佳性能。

首次适应算法具有最佳性能；空间利用方面，首次适应算法比最佳适应算法好，最坏适应算法最差。

最佳适应算法找到的空闲分区是最佳的，但内存利用率不一定最优；

首次适应算法尽可能利用低地址空间，保证了高地址有较大空闲分区，以分配给较大的程序或作业；

最坏适应算法总是分割大的空闲分区，这有利于中、小程序或作业，但不利于较大的程序或作业。在实际系统中，首次适应算法使用较广泛。

#### 例题 ####

1.在可变分区存储管理下，按地址排列的内存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB 和 15KB。对于下列连续存储区的请求：12KB、10KB、15KB、18KB，试问：使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法，哪个空闲区将被使用？  
![image-1653458857923][]

首次适应算法：  
![image-1653458917723][]

循环首次适应算法：  
![image-1653458959921][]

最佳适应算法：  
![image-1653458991017][]  
![image-1653459007038][]

最坏适应算法：  
![image-1653459029171][]

2.某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0。若分配采用分配空闲区低地址部分的方案，对下述申请序列:  
申请310K，申请100K，释放310K，申请150K，申请40K，申请30K。  
分别采用首次适应算法、最佳适应算法，回答下列问题:  
(1)给出每一步的已分配空间、空闲分区(给出始址，大小)?  
(2)若再申请120K，还能分配这120K存储空间吗?

![image-20230226163614372][] ![image-20230221143940256][]

[image-1653458857923]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-1653458857923.png
[image-1653458917723]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-1653458917723.png
[image-1653458959921]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-1653458959921.png
[image-1653458991017]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-1653458991017.png
[image-1653459007038]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-1653459007038.png
[image-1653459029171]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-1653459029171.png
[image-20230226163614372]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-20230226163614372.png
[image-20230221143940256]: https://sunmingtypora.oss-cn-qingdao.aliyuncs.com/image-20230221143940256.png