5 … … … 2.1.2 空闲分区链 用链头指针将系统中的空闲分区链接起来，构成空闲分区链。每个空闲分区的起始部分存放相应的控制信息(如大小,指向下一空闲分区的指针等).

2.2 模块说明

2.12.1 分区说明表 struct PST

{//partition specification table

int id;//分区号

int addr;//起始地址

int size;//分区长度 Status state;//状态

};

2.2.2 双向链表 struct Node

{//双向链表结点 PST data;

Node *back;//前驱

Node *next;//后继 Node() {

back=NULL; next=NULL; }

Node(int id,int size) {

data.ID=id; data.size=size; back=NULL; next=NULL; } };

2.2.3 最先适应算法

空闲分区（链）按地址递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲

分区表（链）中。

算法特点:优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。

Status FFA(int id,int size) {//head fit algorithm

Node *temp=new Node(id,size); temp->data.state=BUSY; Node *cur=head->next; while(cur) {

if(cur->data.state==FREE&&cur->data.size==size) {//如果空闲块大小刚好与请求大小相等,直接分配 cur->data.ID=id;

cur->data.state=BUSY; return OK; break; }

if(cur->data.state==FREE&&cur->data.size>size) {//如果大于

temp->back=cur->back; temp->next=cur;

cur->back->next=temp;

temp->data.addr=cur->data.addr; cur->back=temp;

cur->data.addr=cur->data.addr+size; cur->data.size=cur->data.size-size; return OK; break; }

cur=cur->next; }

return ERROR; }

2.2.4 最佳适应算法

空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍留在空闲分区表/链中。

算法特点：若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，,从而保留了大的空

闲分区,但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。

Status BFA(int id,int size) {//best fit algorithm

Node *temp=new Node(id,size); temp->data.state=BUSY;

int min;//记录符合满足请求的最小空闲块大小 Node *fit;//指向采用最佳适应算法的插入位置 Node *cur=head->next; while(cur)

{//取得第一个可以分配的位置（不一定是最佳位置） if(cur->data.state==FREE&&cur->data.size>=size) {

fit=cur;

min=cur->data.size-size; break; }

cur=cur->next; }

while(cur) {

if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配

cur->data.state=BUSY; cur->data.ID=id; return OK; break; }

if(cur->data.state==FREE&&cur->data.size>size) {//获取最佳位置

if(cur->data.size-size

min=cur->data.size-size; fit=cur; } }

cur=cur->next; } if(fit)

{//若最佳，插入

temp->back=fit->back; temp->next=fit;

fit->back->next=temp;

temp->data.addr=fit->data.addr; fit->back=temp;

fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; return OK; } else

return ERROR;

}

2.2.5 最坏适应算法

空闲分区表/链按容量大小递减的次序排列。在进行内存分配时，从空闲分区表的首开始顺序查找，直到找到第一个比之大的空闲分区为止。剩下的空闲仍留在空闲分区表/链中。

算法特点：总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。

Status WFA(int id,int size) {//worst fit algorithm

Node *temp=new Node(id,size); temp->data.state=BUSY;

int max;//记录符合满足请求的最小空闲块大小 Node *fit;//指向采用最坏适应算法的插入位置 Node *cur=head->next; while(cur)

{//取得第一个可以分配的位置（不一定是最佳位置） if(cur->data.state==FREE&&cur->data.size>=size) {

fit=cur;

max=cur->data.size-size; break; }

cur=cur->next; }

while(cur) {/*

if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配

cur->data.state=BUSY; cur->data.ID=id; return OK; break; }