os.zip_doneaj3_rainct2_请求分页_请求分页算法_请求分页系统

#include<iostream> #include<stdlib.h> using namespace std; #define Free 0 #define Busy 1 #define OK 1 #define ERROR 0 #define MAX_length 640 struct freepartition { int ID; int size; int address; int state; }; typedef struct node { freepartition data; struct node *prior; struct node *next; } node,*Linklist; Linklist first; Linklist last; int alloc(int); int free(int); int First_fit(int,int); int Best_fit(int,int); void show(); int Initblock(); int Initblock() { first=(Linklist)malloc(sizeof(node)); last=(Linklist)malloc(sizeof(node)); first->prior=NULL; first->next=last; last->prior=first; last->next=NULL; last->data.address=0; last->data.size=MAX_length; last->data.ID=0; last->data.state=Free; return OK; } int allocation(int ch,int ID,int request) { if(request<0 ||request==0) { cout<<"分配大小不合适，请重试！"<<endl; return ERROR; } if(ch==2) { //选择最佳适应算法 if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl; return OK; } else { //首次适应算法 if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl; return OK; } } //------------------ 首次适应算法 ----------------------- int First_fit(int ID,int request) { //传入作业名及申请的空间大小 //为申请作业开辟新空间且初始化 Linklist temp=(Linklist)malloc(sizeof(node)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; node *p=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; } p=p->next; } return ERROR; } //--------------------最佳适应算法------------------------ int Best_fit(int ID,int request) { int ch; //记录最小剩余空间 Linklist temp=(Linklist)malloc(sizeof(node)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; node *p=first->next; node *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) { if(p->data.state==Free && p->data.size==request) { //空闲块大小恰好合适 p->data.ID=ID; p->data.state=Busy; return OK; break; } if(p->data.state==Free && p->data.size>request) { //空闲块大于分配需求 if(p->data.size-request<ch) { //剩余空间比初值还小 ch=p->data.size-request;//更新剩余最小值 q=p;//更新最佳位置指向 } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else { //找到了最佳位置并实现分配 temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.size=ch; return OK; } } //----------------------- 主 存 回 收 -------------------- int free(int ID) { cout<<"释放成功"<<endl; node *p=first; while(p) { if(p->data.ID==ID) { p->data.state=Free; p->data.ID=Free; if(p->prior->data.state==Free && p!=first->next) { //与前面的空闲块相邻 p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; } if(p->next->data.state==Free) { //与后面的空闲块相连 p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next; } break; } p=p->next; } return OK; } //--------------- 显示主存分配情况 ------------------ void show() { node *p=first->next; while(p) { cout<<"分 区 号："; if(p->data.ID==Free) cout<<"Free"<<endl; else cout<<p->data.ID<<endl; cout<<"起始地址："<<p->data.address<<endl; cout<<"分区大小："<<p->data.size<<" KB"<<endl; cout<<"状 态："; if(p->data.state==Free) cout<<"空闲"<<endl; else cout<<"已分配"<<endl; cout<<"--------------"<<endl; p=p->next; } cout<<"**************************"<<endl; } //----------------------- 主 函 数--------------------------- int main() { int ch; //算法选择 while(1) { cout<<"1.首次适应算法2.最佳适应算法3.退出\n"; cout<<"请选择相应的操作："; cin>>ch; switch(ch) { case 1: Initblock(); //开创空间表 allocation(ch,1,130); show(); allocation(ch,2,60); show(); allocation(ch,3,100); show(); free(2); show(); allocation(ch,4,200); show(); free(3); show(); free(1); show(); allocation(ch,5,140); show(); allocation(ch,6,60); show(); allocation(ch,7,50); show(); free(6); show(); break; case 2: Initblock(); //开创空间表 allocation(ch,1,130); show(); allocation(ch,2,60); show(); allocation(ch,3,100); show(); free(2); show(); allocation(ch,4,200); show(); free(3); show(); free(1); show(); allocation(ch,5,140); show(); allocation(ch,6,60); show(); allocation(ch,7,50); show(); free(6); show(); break; case 3: exit(1); break; } } return 0; }