memory.cpp

操作系统分页存储管理

//      实验四 主存空间的分配与回收
//   采用首次适应算法(FF)实现主存分配和回收程序
//   采用可变分区存储管理,使用空闲分区链实现主存分配和回收
//   Copyright 2008 , by freedomer

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define getfreearea(type) (type*)malloc(sizeof(type))
#define NULL 0

struct freearealink   /*空闲分区链*/
{int ID;              /*分区序号*/
 int startadr;        /*分区始址*/
 int size;            /*分区大小*/ 
 int state;           /*1表示已分配,0表示空闲*/
 struct freearealink *next,*front;/*前向,后向指针*/
}*LINK,*p;            /*LINK为链表的头*/

typedef struct freearealink FREELINK;

int adr = 40,         /*有40K是系统分区,所以地址从40开始*/
	sumsize = 600;    /*可供用户使用的内存总大小*/

void disp () {        /*显示空闲区表的有关信息*/
	p = LINK;
	printf("\n\n");
	printf("\t|分区号\t|分区始址\t|分区大小\t|分区状态\n");
	printf("\t-------------------------------------------------\n");
	while(p!=NULL) {
		printf("\t|%d\t|%dK\t\t|%dK\t\t|%d\n",p->ID,p->startadr,p->size,p->state);
		p = p->next;
	}
}

void firstfreearea() {  /*初始时的用户可用的空闲区*/
	p=getfreearea(FREELINK);
	LINK = p;
	LINK->front = NULL;
	LINK->next = NULL;
	p->ID = 1;         /*分区号从1开始*/
	p->startadr = adr;
	p->size = sumsize;
	p->state = 0;
	disp();
}

int alloc (int jobsize) { /*根据作业大小分配空间,成功返回1,失败返回0*/
    FREELINK *q;
	p = LINK;			  /*从链头开始遍历*/
	int i;                /*分区ID*/
	while(p!=NULL) {
		if(p->state == 1) /*此分区已被分配*/
			p = p->next;
		else {
			if(p->size > jobsize) {  /*p指向的分区空间足够大*/
				q=getfreearea(FREELINK);/*在链表中p指向那项的后面插入一项q*/
                q->next = p->next;   
                q->front = p;
                if(p->next!=NULL)
					p->next->front=q;
                p->next = q;
                q->startadr = p->startadr+jobsize;/*q指向的是剩余分区*/
                q->size = p->size-jobsize;
                q->state = 0;
                p->size = jobsize;  /*p指向的是被分配出去的分区*/
                p->state = 1;
                sumsize = sumsize - jobsize;
				break;
			}
			else if(p->size == jobsize) {
				p->state = 1;
				sumsize = sumsize - jobsize;
				break;
			}
			else          /*此分区空间不够*/
				p = p->next;
		}
	}
	q = LINK;             /*重新为链编写ID*/
	i = 1;
    while(q!=NULL) {
        q->ID = i;
		i++;
		q = q->next;
	}
	if(p == NULL)
		return 0;
	else
		return 1;
}

int release(int releaseID) {/*根据用户输入的ID号释放对应的作业空间,成功返回1,失败返回0*/
	FREELINK *q,*qfront,*qnext;
	int i;
	q = LINK;
	while(q!=NULL) {        /*找到与输入ID相同的分区,用q指向它*/
		if(q->ID!=releaseID)
			q=q->next;
		else
			break;
    }
	if(q==NULL)             
		return 0;
    else {
		qfront = q->front; /*q的前一个分区*/
		qnext = q->next;   /*q的后一个分区*/
		q->state = 0;      /*q指向的分区的状态标志变为可用*/
        sumsize = sumsize + q->size;
		//通过下面两个if可以将释放区与其相邻的空闲区合并
        //如果有空闲的邻接,会先与低地址,然后才跟高地址合并
		if(qfront!=NULL && qfront->state == 0) {/*释放区低地址邻接*/
			qfront->size = qfront->size + q->size;/*合并*/
			qfront->next = qnext;
			qnext->front = qfront;
			q = qfront;
        }
		if(qnext!=NULL && qnext->state == 0) { /*释放区高地址邻接*/
			q->size = q->size + qnext->size;
			if(qnext->next!=NULL)
				qnext->next->front = q;
			q->next = qnext->next;
        }
		q = LINK;             /*重新为链编写ID*/
		i = 1;
		while(q!=NULL) {
			q->ID = i;
			i++;
	 		q = q->next;
		}
		return 1;
	}
}

void main () {
	int  choosenum = 1,
         jobsize,      /*作业申请大小*/
	     releaseID;    /*释放的区号*/
    firstfreearea();   /*显示初始空闲区情况*/
	while(choosenum!=3){
		printf("\n**1.作业申请.\n**2.作业释放\n**3.退出\n\n");
		scanf("%d",&choosenum);
		if(choosenum==1) {
			printf("作业所申请大小:");
			scanf("%d",&jobsize);
			if(alloc(jobsize)) /*调用函数alloc,分配空间*/
				disp();
			else {
				printf("\n*没有足够的空间,请等待...***\n");
			    disp();
			}
		}
		if(choosenum==2) {
			printf("释放的分区号:");
			scanf("%d",&releaseID);
			if(release(releaseID))/*调用函数release,释放空间*/
				disp();
			else {
				printf("\n*出错!不存在所输入的ID!***");
				disp();
			}
		}
	}
}