操作系统内存动态分配模拟算法.docx
《操作系统内存动态分配模拟算法.docx》由会员分享，可在线阅读，更多相关《操作系统内存动态分配模拟算法.docx（14页珍藏版）》请在冰点文库上搜索。
操作系统内存动态分配模拟算法
实验四存分配算法
1.实验目的
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。
当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。
当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。
主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。
背景知识：
可变分区方式是按作业需要的主存空间大小来分割分区的。
当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。
随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。
2.实验容
采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。
由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
（即输出当时的空闲区说明表及其存分配表）
利用VC++6.0实现上述程序设计和调试操作。
3.实验代码
#include
#include
usingnamespacestd;
//定义存的大小
constintSIZE=64;
//作业结构体，保存作业信息
structProject{
intnumber;
intlength;
};
//存块结构体，保存存块信息
structBlock{
intaddress;
intlength;
intbusy;
};
intfirst_fit（list&,Project,list&）;//声明首次适配算法函数
intbest_fit（list&,Project,list&）;//声明最佳适配算法函数
intnext_fit（list&,Project,list&）;//声明下次适配算法函数
voidswap_out（list&,Project,list&）;//声明换出作业的函数
voidprint_info（list,list）;//声明打印存和作业函数
intremain_length（list）;//声明计算剩余存的函数
intmain（）{
listB_List;
listP_List;
Blockm1={1,SIZE,0};
B_List.push_back（m1）;
print_info（B_List,P_List）;
while（true）
{
cout<<"\n\t\t1.装入作业"<";
intchoice;
cin>>choice;
switch（choice）
{
case1:
//装入作业
{
cout<<"请选择装入方式：
（1.首次适配2.最佳适配3.下次适配）：
\n";
intc1;
cin>>c1;
cout<<"请输入作业号（作业号不能重复）：
";
intc2;
cin>>c2;
cout<<"请输入作业所需存：
";
intc3;
cin>>c3;
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;
cin>>c3;
Projectp={c3,5};
swap_out（B_List,p,P_List）;
print_info（B_List,P_List）;
break;
}
default:
//退出
{
return0;
}
}
}
}
//首次适配
intfirst_fit（list&L1,Projectp,list&L2）{
list:
:
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.lengthlength&&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<<"存不足，作业"<return0;
}
//最佳适配
intbest_fit（list&L1,Projectp,list&L2）{
list:
:
iteratori,j;
intmin=100000;
for（i=L1.begin（）;i!
=L1.end（）;i++）{
if（i->length-p.length>-1&&i->length-p.lengthbusy==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<<"存不足，作业"<return0;
}
}
//下次适配
intnext_fit（list&L1,Projectp,list&L2）{
intpnumber=L2.back（）.number;
list:
:
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.lengthlength&&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<<"存不足，作业"<return0;
}
}
return0;
}
//换出作业
voidswap_out（list&L1,Projectp,list&L2）{
intpnumber=p.number;
list:
:
iteratori2;
for（i2=L2.begin（）;i2!
=L2.end（）;i2++）{
//根据作业号换出作业
if（（*i2）.number==pnumber）{
L2.erase（i2）;
break;
}
}
list:
:
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（listL1）
{
list:
:
iteratori;
//当前所有作业占用的总存
intlen=0;
for（i=L1.begin（）;i!
=L1.end（）;i++）{
if（i->busy!
=0）
len+=i->length;
}
returnSIZE-len;
}
voidprint_info（listL1,listL2）{
cout<<"\n***********************************************"<cout<<"总存：
"<"<list:
:
iteratori;
for（i=L1.begin（）;i!
=L1.end（）;i++）{
if（i->busy==0）{
cout<<"首地址：
"<address<<"长度：
"<length<<"空闲"<}
else
cout<<"首地址：
"<address<<"长度：
"<length<<"被作业"<busy<<"占用"<}
cout<<"***********************************************"<cout<<"作业明细（按进入顺序排）：
"<list:
:
iteratorj;
for（j=L2.begin（）;j!
=L2.end（）;j++）{
cout<<"作业号：
"<number<<"长度：
"<length<}
cout<<"***********************************************"<}
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的方法模拟整个过程作业装入，换出等整个过程。
升级会员 