计算机内存管理介绍( 二 ) _内存管理

链表表示法

文章插图

? 将分配单元按照是否闲置链接，P代表这个空间被占用，H代表这个这是一片闲置空间。为了方便遍历查询，每个程序空间的结点接着一个空闲空间的结点每个链表结点还有一个起始地址，与分配单元的大小，用代码表示为

enum Status{P=0,H=1};struct LinkNode{enum Status status;//P表示程序，H表示空闲struct LinkNode *begin_address;//起始地址size_t size;//闲置空间大小struct LinkNode *next;};

特点空间成本：取决于程序数量时间成本：链表不停的遍历速度很慢，同时还要进行链表的插入和删除修改。有一定的容错能力，可以通过程序空间结点和空闲空间结点相互验证。

可变分区的内存分配
OS通过上面两种跟踪方法知道内存空闲容量，而现在操作系统一般都以链表的形式进行内存空闲容量跟踪。如果有新的程序需要读入内存，可变分区就要对空闲的分区进行内存分配。
内存分配使用两张表：已分配分区表和未分配分区表。用C++描述如下:

//未分配分区表struct FreeBlock {int id;// 内存分区号int address;// 该分区的首地址unsigned length;// 分区长度};//已分配分区表struct AllocatedBlock {int id;// 内存分区号int address;// 该分区的首地址int pid;// 进程 IDunsigned length;// 分区长度};

然后OS用双向链表将所有未分配分区表进行串联
struct{FreeBlock data;Node* prior;Node* next;}Node;未分配分区表在整个系统空间上的结构如下：

文章插图

基于顺序搜索的分配算法：这里我们介绍四种基于顺序搜索的寻找空闲存储空间的算法:

首次适应算法（ First Fit ）：每个空白区按其地址顺序连在一起，从这个空白区域链的始端开始查找，选择第一个足以满足请求的空白块。
下次适应算法（ Next Fit ）：将存储空间中空白区构成一个循环链，每次为存储请求查找合适的分区时，总是从上次查找结束的下一个空闲块开始，只要找到一个足够大的空白区，就将它划分后分配出去。
最佳适应算法（ Best Fit ）：为一个作业选择分区时，总是寻找其大小最接近(小于等于)于作业所要求的存储区域。
最坏适应算法（ Worst Fit ）：为作业选择存储区域时，总是寻找最大的空白区。

算法举例！！
系统中空闲分区表如下按照地址递增次序排列，现有三个作业分配申请内存空间100K,30K,7K 。
区号大小地址状态132K20K未分配28K52K未分配3120K60K未分配4331K180K未分配