操作系统---(29)连续分区存储管理之数据结构与主存分配算法
连续分区存储管理
- 实质特点：一个进程装入连续的一块内存空间
- 单分区方式：
内存用户区的全部空间只存放一个进程 - 多分区方式：固定多分区，动态多分区
内存被分为多个分区，每个分区存放一个进程。每瞬间可有多个进程驻留在内存的不同分区中。
数据结构：如何记录各个分区的使用情况
常用的数据结构–1
- 1-主存分配表MAT(Memory Allocation Table)
- 分区号:每个分区都有一个编号,用以区别不同分区。
- 起始地址:分区的起始地址,即首地址。
- 长度:分区的总长，一般以KB为单位。
- 占用标志:记录分区的使用状态。若占用标志为0，表明该分区为空闲，可以进行分配。
- 2-空闲区表/链：记录内存空闲区状况的数据结构
空闲区表/链的使用：
有空闲区链中各空闲区可按地址顺序来排列，也可按尺寸大小来组织。当系统进行内存分配时，进行的处理是:- 通过空闲区链，快速搜索内存的空闲区。
- 从中找出最合适的分区分配出去。
- 将该结点从链上删除。
当需要回收某块被释放的区域时，系统处理过程为 - 按其地址或者大小在链中找到合适的位置。
- 插入一个新结点。
- 若存在相邻的空闲区，则需要的话可将相邻空闲区合并。
主存分配算法
- 首次适应算法First_ Fit
首次适应算法也称为最早适应算法。系统将内存分区按地址递增顺序登记到内存分配表(或其它数据结构)中。
每次进行内存分配时，系统根据进程申请空间的大小，从头到尾顺序扫描内存分配表(或空闲分区表) ,从中找到的第1块能够满足要求的空闲区，就立即分配出去。 - 循环首次适应算法Circle_ First_ Fit
该算法的思想是，每次存储分配总是从上次分配的位置开始，向尾部查找。查到的第1块可满足用户需求的空闲空间，分配给用户。当查到MAT (或空闲链表)的尾部仍然没有合适的，转到头部继续。
MAT有8个分区，其中带阴影的分区是已经被占用的。假设上次分配的是1#分区，则当前的指针位置是2#分区。如果有一个用户请求40KB，则系统将按顺时针方向，找到5#分区分配给用户。 - 最佳适应算法Best_ Fit
在内存分配时，从空闲区表中找到一块满足进程需求的最小空闲区分配给它。
这种做法减少了将大空闲区进行多次分割造成的空间浪费。但容易形成一些很小的碎片无法使用，同样不能提高内存利用率。另外，每次分配时，都要对整个内存区进行从头到尾的搜索，系统开销较大。 - 最坏适应算法Worst_ _Fit
在进行内存分配时，从空闲区表中找到一个满足长度要求的最大空闲区进行分配。
这种算法部分地缓解了由外碎片引起的浪费，适合于中小作业的运行，但对大作业的运行是不利的。与最佳适应算法一样，每次分配需要搜索一遍内存， 效率会受到一定影响。