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; }