OS实验-模拟实现首次/最佳/最坏适应算法的内存块分配和回收

编写C语言程序，模拟实现首次/最佳/最坏适应算法的内存块分配和回收，要求每次分配和回收后显示出空闲分区和已分配分区的情况。

假设初始状态下，可用的内存空间为640KB。 #include<bits/stdc++.h> #define ll long long using namespace std;const ll maxn=1e18; const ll minn=-1e18; const ll mod=1000000007; const ll MAX=100005; bool cmp(ll a,ll b){return a>b;} /*拟实现首次/最佳/最坏适应算法的内存块分配和回收，要求每次分配和回收后显示出空闲分区和已分配分区的情况。 假设初始状态下，可用的内存空间为640KB。*/int n; //初始空间 string algin; int pos=1; //记录当前内存块的个数；struct node{int left,right;int vis; //0表示未使用内存；1表示已经使用了内存空间；int work;bool operator < (const node &t) const{return left<t.left;} }node[1010];void opin(int nu,int nulen) //插入 {string FIR="FIR";string BST="BST";string WST="WST";sort(node+1,node+pos+1);if(algin==FIR) //首次{for(int i=1 ; i<=pos ; i++){if(node[i].right-node[i].left>=nulen&&node[i].vis==0){pos++;node[pos].left=node[i].left;node[pos].right=node[pos].left+nulen;node[pos].vis=1;node[pos].work=nu;node[i].left=node[pos].right;cout<<nu<<"的内存分配成功！"<<endl;return ;}}cout<<endl<<nu<<"的内存分配失败！"<<endl;}else if(algin==BST) //最优{vector<int> temp;for(int i=1 ; i<=pos ; i++){if(node[i].right-node[i].left==nulen&&node[i].vis==0) //刚好的时候一定是最优；{node[i].vis=1;node[i].work=nu;cout<<nu<<"的内存分配成功！"<<endl;return ;}else if(node[i].vis==0){temp.push_back(i);}}int len=temp.size();sort(temp.begin(),temp.end()); //升序；for(int i=0 ; i<len ; i++){if(node[temp[i]].right-node[temp[i]].left>nulen){pos++;node[pos].left=node[temp[i]].left;node[pos].right=node[pos].left+nulen;node[pos].vis=1;node[pos].work=nu;node[temp[i]].left=node[pos].right;cout<<nu<<"的内存分配成功！"<<endl;return ;}}cout<<endl<<nu<<"的内存分配失败！"<<endl;}else if(algin==WST) //最坏{vector<int> temp;for(int i=1 ; i<=pos ; i++){if(node[i].vis==0){temp.push_back(i);}}int len=temp.size();sort(temp.begin(),temp.end(),cmp); //降序；for(int i=0 ; i<len ; i++){if(node[temp[i]].right-node[temp[i]].left>=nulen){if(node[temp[i]].right-node[temp[i]].left==nulen) //相等{node[temp[i]].vis=1;node[temp[i]].work=nu;cout<<nu<<"的内存分配成功！"<<endl;return ;}else //大于{pos++;node[pos].left=node[temp[i]].left;node[pos].right=node[pos].left+nulen;node[pos].vis=1;node[pos].work=nu;node[temp[i]].left=node[pos].right;cout<<nu<<"的内存分配成功！"<<endl;return ;}}}cout<<endl<<nu<<"的内存分配失败！"<<endl;} }void opde(int nu) //回收 {sort(node+1,node+pos+1);for(int i=1 ; i<=pos ; i++){if(node[i].work==nu){node[i].vis=0;node[i].work=0;int temp=0;for(int j=i-1 ; j>=1 ; j--) //从后往前找{if(node[j].vis!=0)break;else{node[i].left=node[j].left;node[j].left=n;node[j].right=n;temp++;}}for(int j=i+1 ; j<=pos ; j++) //从前往后找{if(node[j].vis!=0)break;else{node[i].right=node[j].right;node[j].left=n+1;node[j].right=n+1;temp++;}}sort(node,node+pos);pos-=temp;}} }/* void printtest() {sort(node+1,node+pos+1);for(int i=1 ; i<=pos ; i++){cout<<i<<" : "<<node[i].work<<" "<<node[i].left<<" "<<node[i].right<<" "<<node[i].right-node[i].left<<" "<<node[i].vis<<endl;} } */void print() {sort(node+1,node+pos+1);cout<<endl;for(int i=1 ; i<=pos ; i++){cout<<"|<-";for(int j=0 ; j<(node[i].right-node[i].left)/20-5; j++)cout<<" ";if(node[i].vis==0)cout<<"None";elsecout<<"work"<<node[i].work;for(int j=0 ; j<(node[i].right-node[i].left)/20-4; j++)cout<<" ";if(i==pos)cout<<"->|"<<endl;elsecout<<"->";}//底线for(int i=0 ; i<(node[pos].right-node[1].left)/10 ; i++)cout<<"-";cout<<endl;cout<<node[1].left;for(int i=1 ; i<=pos ; i++){for(int j=0 ; j<(node[i].right-node[i].left)/10-3 ; j++)cout<<" ";cout<<node[i].right;}cout<<endl;cout<<endl; }void fi(int n) //初始化 {node[0].left=0;node[0].right=0;node[0].vis=0;node[0].work=0;node[pos].left=node[pos-1].right;node[pos].right=n;node[pos].vis=0;node[pos].work=0;print(); } void init() {cout<<"请输入初始系统空间大小:"<<endl;cin>>n;fi(n);int t;while(1){cout<<"请输入操作：1-插入 2-删除 0-退出"<<endl;cin>>t;if(t==0)break;else if(t==1){cout<<"请输入插入所适应算法：FIR-首次 BST-最佳 WST-最坏："<<endl;cin>>algin;cout<<"请输入需要分配的作业号和大小"<<endl;int nu,nulen;cin>>nu>>nulen;opin(nu,nulen);//printtest();print();}else if(t==2){cout<<"请输入需要回收的作业号"<<endl;int nu;cin>>nu;opde(nu);print();//printtest();}}} int main() {init();return 0; }/* 650 1 FIR 1 100 1 FIR 2 150 1 FIR 3 200 2 2 1 BST 4 100*/

总结

以上是生活随笔为你收集整理的OS实验-模拟实现首次/最佳/最坏适应算法的内存块分配和回收的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。