#include
#define MAX_length 32767 //最大内存空间为32767KB typedef int Status; int n=0;
typedef struct freearea//定义一个空闲区说明表结构 {
int ID; //分区号d long size; //分区大小 long address; //分区地址 int state; //状态 }ElemType;
//---------- 线性表的双向链表存储结构 ------------ typedef struct DuLNode //double linked list {
ElemType data;
struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 }DuLNode,*DuLinkList;
DuLinkList block_first; //头结点 DuLinkList block_last; //尾结点
-6-
Status alloc(int);//内存分配 Status free(int); //内存回收
Status LRU(int,int);//最近最少使用算法 Status NUR(int,int); //最佳适应算法 void show();//查看分配
Status Initblock();//开创空间表
Status Initblock()//开创带头结点的内存空间链表 {
block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.ID=0; block_last->data.state=Free; return OK; }
//----------------------- 分 配 主 存 ------------------------- Status alloc(int ch) {
int ID,request;
-7-
cout<<\请输入作业(分区号)：\cin>>ID;
cout<<\请输入需要分配的主存大小(单位:KB)：\cin>>request;
if(request<0 ||request==0) {
cout<<\分配大小不合适，请重试!\ return ERROR; }
if(ch==2) //最近不用先淘汰算法 {
if(NUR(ID,request)==OK) cout<<\分配成功!\ else cout<<\内存不足，分配失败!\ return OK; }
else //默认最近最少算法 {
if(LRU(ID,request)==OK) cout<<\分配成功!\ else cout<<\内存不足，分配失败!\ return OK; } }
//------------------ 最近不用先淘汰算法 ----------------------- Status LRU(int ID,int request)//传入作业名及申请量 {
//为申请作业开辟新空间且初始化
-8-
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy;
DuLNode *p=block_first->next; while(p) {
if(p->data.state==Free && p->data.size==request) {//有大小恰好合适的空闲块 p->data.state=Busy; p->data.ID=ID; return OK; break; }
if(p->data.state==Free && p->data.size>request) {//有空闲块能满足需求且有剩余\ temp->prior=p->prior; temp->next=p;
temp->data.address=p->data.address; p->prior->next=temp; p->prior=temp;
p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; }
-9-
p=p->next; }
return ERROR; }
//-------------------- 最近不用先淘汰算法 ------------------------ Status NUR(int ID,int request) {
int ch; //记录最小剩余空间
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; DuLNode *q=NULL; //记录最佳插入位置 while(p) //初始化最小空间和最佳位置 {
if(p->data.state==Free &&
(p->data.size>request || p->data.size==request) ) { q=p;
ch=p->data.size-request; break; }
p=p->next; } while(p) {
-10-