操作系统内存动态分配模拟算法

实验四内存分配算法1.实验目的一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。背景知识：可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。2.实验内容采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。（即输出当时的空闲区说明表及其内存分配表）利用VC++6.0实现上述程序设计和调试操作。3.实验代码#includeiostream#includelistusingnamespacestd;//定义内存的大小constintSIZE=64;//作业结构体，保存作业信息structProject{intnumber;intlength;};//内存块结构体，保存内存块信息structBlock{intaddress;intlength;intbusy;};intfirst_fit(listBlock&,Project,listProject&);//声明首次适配算法函数intbest_fit(listBlock&,Project,listProject&);//声明最佳适配算法函数intnext_fit(listBlock&,Project,listProject&);//声明下次适配算法函数voidswap_out(listBlock&,Project,listProject&);//声明换出作业的函数voidprint_info(listBlock,listProject);//声明打印内存和作业函数intremain_length(listBlock);//声明计算剩余内存的函数intmain(){listBlockB_List;listProjectP_List;Blockm1={1,SIZE,0};B_List.push_back(m1);print_info(B_List,P_List);while(true){cout\n\t\t1.装入作业endl\t\t2.换出作业endl\t\t3.退出\nendl请选择操作：;intchoice;cinchoice;switch(choice){case1://装入作业{cout请选择装入方式：(1.首次适配2.最佳适配3.下次适配)：\n;intc1;cinc1;cout请输入作业号（作业号不能重复）：;intc2;cinc2;cout请输入作业所需内存：;intc3;cinc3;Projectp={c2,c3};if(c1==1){first_fit(B_List,p,P_List);}elseif(c1==2){best_fit(B_List,p,P_List);}elseif(c1==3){next_fit(B_List,p,P_List);}print_info(B_List,P_List);break;}case2://换出作业{cout请选择需换出内存的作业：;intc3;cinc3;Projectp={c3,5};swap_out(B_List,p,P_List);print_info(B_List,P_List);break;}default://退出{return0;}}}}//首次适配intfirst_fit(listBlock&L1,Projectp,listProject&L2){listBlock::iteratori;//遍历列表查找空闲分区for(i=L1.begin();i!=L1.end();i++){//空闲分区大小和作业相同if(p.length==i-length&&i-busy==0){i-busy=p.number;L2.push_back(p);return1;}//空闲分区比作业内存大if(p.lengthi-length&&i-busy==0){i-busy=p.number;intlen=i-length-p.length;i-length=p.length;Blockm={i-address+p.length,len,0};L1.insert(++i,m);i--;L2.push_back(p);return1;}}cout内存不足，作业p.number装入失败endl;return0;}//最佳适配intbest_fit(listBlock&L1,Projectp,listProject&L2){listBlock::iteratori,j;intmin=100000;for(i=L1.begin();i!=L1.end();i++){if(i-length-p.length-1&&i-length-p.lengthmin&&i-busy==0){j=i;//找到大于或等于作业内存的最小空闲内存min=i-length-p.length;}}i=j;//空闲分区大小和作业相同if(min==0){i-busy=p.number;L2.push_back(p);return1;}//空闲分区比作业内存大elseif(min!=100000){i-busy=p.number;intlen=i-length-p.length;i-length=p.length;Blockm={i-address+p.length,len,0};L1.insert(++i,m);i--;L2.push_back(p);return1;}if(i==--L1.end()){cout内存不足，作业p.number装入失败endl;return0;}}//下次适配intnext_fit(listBlock&L1,Projectp,listProject&L2){intpnumber=L2.back().number;listBlock::iteratori;//找到前一次装入的作业位置for(i=L1.begin();i!=L1.end();i++){if(i-busy==pnumber){break;}}for(;i!=L1.end();i++){//空闲分区大小和作业相同if(p.length==i-length&&i-busy==0){i-busy=p.number;L2.push_back(p);return1;}//空闲分区比作业内存大if(p.lengthi-length&&i-busy==0){i-busy=p.number;intlen=i-length-p.length;i-length=p.length;Blockm={i-address+p.length,len,0};L1.insert(++i,m);i--;L2.push_back(p);return1;}if(i==--L1.end()){cout内存不足，作业p.number装入失败endl;return0;}}return0;}//换出作业voidswap_out(listBlock&L1,Projectp,listProject&L2){intpnumber=p.number;listProject::iteratori2;for(i2=L2.begin();i2!=L2.end();i2++){//根据作业号换出作业if((*i2).number==pnumber){L2.erase(i2);break;}}listBlock::iteratori,j,k;for(i=L1.begin();i!=L1.end();i++){if(i-busy==pnumber){i-busy=0;j=i;k=i;if(j!=L1.begin()){j--;//换出作业后前一个空闲区正好能连接if(j-busy==0){i-length+=j-length;i-address=j-address;L1.erase(j);}}k++;//换出作业后后一个空闲区正好能连接if(k-busy==0){i-length+=((*k).length);L1.erase(k);}break;}}}//计算剩余内存intremain_length(listBlockL1){listBlock::iteratori;//当前所有作业占用的总内存intlen=0;for(i=L1.begin();i!=L1.end();i++){if(i-busy!=0)len+=i-length;}returnSIZE-len;}voidprint_info(listBlockL1,listProjectL2){cout\n***********************************************endl;cout总内存：SIZE\t剩余内存：remain_length(L1)endl;listBlock::iteratori;for(i=L1.begin();i!=L1.end();i++){if(i-busy==0){cout首地址：i-address长度：i-length空闲endl;}elsecout首地址：i-address长度：i-length被作业i-busy占用endl;}cout***********************************************endl;cout作业明细(按进入顺序排)：endl;listProject::iteratorj;for(j=L2.begin();j!=L2.end();j++){cout作业号：j-number长度：j-lengthendl;}cout***********************************************endl;}4.运行截图1.初始时内存情况：2.采用首次适配算法依次放入作业1（10），作业2（5）作业3（20）作业4（15）后的内存情况：3.换出作业2后内存情况：4.采用最佳适配算法放入作业5（3）后的内存情况：5.换出作业3采用最佳适配算法放入作业6（13）内存情况：6.采用下次适配算法装入作业7（1）内存情况：5.实验中遇到的问题和解决方法实验的难点在于数据结构的选择和内存分配算法的模拟。由动态内存的分配涉及到频繁的作业的装入和换出，且不一定发生在首尾，感觉不适合数组和向量。由此也想到了用链表，首先想到自己写链表但是感觉比较麻烦，而且实现的效率感觉也不高。想到c++STL里有链表，便调用了。但是对于其中的操作方法例如insert(),erase()等等不是很熟悉，网上也查询了相关的关于STL中List的介绍，直到熟悉了方法的使用。对于算法的模拟，感觉就是先用数据结构模拟内存，然后用list的方法模拟整个过程作业装入，换出等整个过程。