操作系统实验四报告-主存空间分配和回收（含源码）(2)

在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函数是用来整理分区序号的，如在删序号3时，她与前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了；allocation（）是分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）；recovery（）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。

七、源代码

#include #include

#define OK 1 //完成 #define ERROR 0 //出错

typedef int Status;

typedef struct free_table//定义一个空闲区说明表结构 {

int num; //分区序号 long address; //起始地址 long length; //分区大小 int state; //分区状态 }ElemType;

typedef struct Node// 线性表的双向链表存储结构 {

ElemType data;

struct Node *prior; //前趋指针 struct Node *next; //后继指针 }Node,*LinkList;

LinkList first; //头结点 LinkList end; //尾结点

int flag;//记录要删除的分区序号

Status Initblock()//开创带头结点的内存空间链表 {

first=(LinkList)malloc(sizeof(Node)); end=(LinkList)malloc(sizeof(Node)); first->prior=NULL; first->next=end; end->prior=first; end->next=NULL;

6

end->data.num=1; end->data.address=40; end->data.length=600; end->data.state=0; return OK; }

void sort()//分区序号重新排序 {

Node *p=first->next,*q; q=p->next;

for(;p!=NULL;p=p->next) {

for(q=p->next;q;q=q->next) {

if(p->data.num>=q->data.num) {

q->data.num+=1; } } } }

//显示主存分配情况 void show()

{ int flag=0;//用来记录分区序号 Node *p=first; p->data.num=0; p->data.address=0; p->data.length=40; p->data.state=1; sort();

printf(\》主存空间分配情况《\\n\

printf(\ printf(\分区序号\\t起始地址\\t分区大小\\t分区状态\\n\\n\ while(p) {

printf(\ if(p->data.state==0) printf(\空闲\\n\\n\ else printf(\已分配\\n\\n\ p=p->next; }

printf(\}

7

//首次适应算法

Status First_fit(int request) {

//为申请作业开辟新空间且初始化 Node *p=first->next;

LinkList temp=(LinkList)malloc(sizeof(Node)); temp->data.length=request; temp->data.state=1; p->data.num=1; while(p) {

if((p->data.state==0)&&(p->data.length==request)) {//有大小恰好合适的空闲块 p->data.state=1; return OK; break; }

else if((p->data.state==0) && (p->data.length>request)) {//有空闲块能满足需求且有剩余 temp->prior=p->prior; temp->next=p;

temp->data.address=p->data.address; temp->data.num=p->data.num; p->prior->next=temp; p->prior=temp;

p->data.address=temp->data.address+temp->data.length; p->data.length-=request; p->data.num+=1; return OK; break; }

p=p->next; }

return ERROR; }

//最佳适应算法

Status Best_fit(int request) {

int ch; //记录最小剩余空间 Node *p=first;

Node *q=NULL; //记录最佳插入位置

LinkList temp=(LinkList)malloc(sizeof(Node));

8

temp->data.length=request; temp->data.state=1; p->data.num=1;

while(p) //初始化最小空间和最佳位置 {

if((p->data.state==0) && (p->data.length>=request) ) {

if(q==NULL) { q=p;

ch=p->data.length-request; }

else if(q->data.length > p->data.length) { q=p;

ch=p->data.length-request; } }

p=p->next; }

if(q==NULL) return ERROR;//没有找到空闲块 else if(q->data.length==request) {

q->data.state=1; return OK; } else {

temp->prior=q->prior; temp->next=q;

temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp;

q->data.address+=request; q->data.length=ch; q->data.num+=1; return OK; }

return OK; }

//最差适应算法

Status Worst_fit(int request)

9

{

int ch; //记录最大剩余空间 Node *p=first->next;

Node *q=NULL; //记录最佳插入位置

LinkList temp=(LinkList)malloc(sizeof(Node)); temp->data.length=request; temp->data.state=1; p->data.num=1;

while(p) //初始化最大空间和最佳位置 {

if(p->data.state==0 && (p->data.length>=request) ) {

if(q==NULL) {

q=p;

ch=p->data.length-request; }

else if(q->data.length < p->data.length) { q=p;

ch=p->data.length-request; } }

p=p->next; }

if(q==NULL) return ERROR;//没有找到空闲块 else if(q->data.length==request) {

q->data.length=1; return OK; } else {

temp->prior=q->prior; temp->next=q;

temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp;

q->data.address+=request; q->data.length=ch; q->data.num+=1; return OK;

10