}
//主函数voidmain()
{
intflag;version();initial();flag=readData();if(flag==1)
{FIFO();
init();privilege();init();
timer();
}
}
(3)运行结果:
输入进程流文件名1.txt即可得出以下输出结果:
实验二银行家算法
一、实验目的
死锁会引起计算机工作僵死,因此操作系统中必须防止。
本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序,了解死锁产生的条件和原因,并采用银行家算法有效地防止死锁的发生,以加深对课堂上所讲授的知识的理解。
二、实验要求
设计有n个进程共享m个系统资源的系统,进程可动态的申请和释放资源,系统按各进程的申请动态的分配资源。
系统能显示各个进程申请和释放资源,以及系统动态分配资源的过程,便于用户观察和分析;
三、数据结构
1.可利用资源向量Available ,它是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源的数目,其初始值是系统中所配置的该类全部可用资源数目。
其数值随该类资源的分配和回收而动态地改变。
如果Available(j)=k,标是系统中现有Rj类资源k个。
2.最大需求矩阵Max,这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
如果Max(i,j)=k,表示进程i需要Rj类资源的最大数目为k。
3.分配矩阵Allocation,这是一个n×m的矩阵,它定义了系统中的每类资源当前一分配到每一个进程的资源数。
如果Allocation(i,j)=k,表示进程i当前已经分到Rj类资源的数目为k。
Allocationi表示进程i的分配向量,有矩阵Allocation的第i行构成。
4.需求矩阵Need,这是一个n×m的矩阵,用以表示每个进程还需要的各类资源的数目。
如果Need(i,j)=k,表示进程i还需要Rj类资源k个,才能完成其任务。
Needi表示进程i的需求向量,由矩阵Need的第i行构成。
上述三个矩阵间存在关系:
Need(i,j)=Max(i,j)-Allocation(i,j);
四、银行家算法
Requesti是进程Pi的请求向量。
Requesti(j)=k表示进程Pi请求分配Rj类资源k个。
当Pi发出资源请求后,系统按下述步骤进行检查:
1.如果Requesti≤Need,则转向步骤2;否则,认为出错,因为它所请求的资源数已超过它当前的最大需求量。
2.如果Requesti≤Available,则转向步骤3;否则,表示系统中尚无足够的资源满足Pi的申请,Pi必须等待。
3.系统试探性地把资源分配给进程Pi,并修改下面数据结构中的数值:
Available=Available-Requesti
Allocationi=Allocationi+Requesti
Needi=Needi-Requesti
4.系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
如果安全才正式将资源分配给进程Pi,以完成本次分配;否则,将试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
假定系统有5个进程(p0,p1,p2,p3,p4)和三类资源(A,B,C),各种资源的数量分别为10,5,7,在
T0时刻的资源分配情况如下图:
Max Allocation Need Available
ABC A B C A B C ABC
P0 7 5 3 0 1 0 7 4 3 3 3 2
(2 3 0)
P1
3
2
2
2
0
0
1
2
2
(3
0
2)
(0
2
0)
P2
9
0
2
3
0
2
6
0
0
P3
2
2
2
2
1
1
0
1
1
P4
4
3
3
0
0
2
4
3
1
五、安全性算法
1.设置两个向量。
Work:
它表示系统可提供给进程继续运行的各类资源数目,它包含m个元素,开始执行安全性算法时,Work=Available。
Finish:
它表示系统是否有足够的资源分配给进程,使之运行完成,开始Finish(I)=false;当有足够资源分配给进程Pi时,令Finish(i)=true;
2.从进程集合中找到一个能满足下述条件的进程。
Finish(i)==false;
Needi≤work;
如找到则执行步骤3;否则,执行步骤4;
3.当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行
Work=work+AllocationiFinish(i)=true;转向步骤2;
4.若所有进程的Finish(i)都为true,则表示系统处于安全状态;否则,系统处于不安全状态。
六、 系统流程图
开始
输入资源数m, 及各类资源总数,初始
输入进程数
结束
Y
i≤n
N
N
max≤资源
Y
i加1
输入进程i的最大需求向量
初始化need
提示错误重新
该进程的Need
N
输入该进程的资源请求量
Y
Need矩阵为
N
任选一个进程作为
该进程已运行
所有进程运行
调用银行家算法,及安全性算法,完成分配,
Y
七.银行家算法程序代码
#include#include#includeusingnamespacestd;
typedefstructMax1 //资源的最大需求量
{
intm_a;intm_b;intm_c;
}Max;
typedefstructAllocation1 //已分配的资源数
{
inta_a;inta_b;inta_c;
}Allocation;
typedefstructNeed1 //还需要的资源数
{
intn_a;intn_b;intn_c;
}Need;
structAvailable1 //可利用的资源量
{
}q;
intav_a;intav_b;intav_c;
structpr //定义一个结构
{
charname;
Maxmax;
Allocationallocation;
Needneed;
intfinishflag;
}p[5];
charna[5];
//********************************************voidinit() //读入文件"1.txt"
{
cout<<"各进程还需要的资源数NEED:
"<FILE*fp;
fp=fopen("1.txt","r+");//打开文件"1.txt"for(inti=0;i<5;i++)
{
fscanf(fp,"%c,%d,%d,%d,%d,%d,%d\n",&p[i].name,&p[i].max.m_a,&p[i].max.m_b,&p[i].max.m_c,&p[i].allocation.a_a,&p[i].allocation.a_b,&p[i].allocation.a_c);
p[i].need.n_a=p[i].max.m_a-p[i].allocation.a_a;p[i].need.n_b=p[i].max.m_b-p[i].allocation.a_b;p[i].need.n_c=p[i].max.m_c-p[i].allocation.a_c;
cout<
"<
}
fclose(fp); //关闭文件
}
//***********************************************intfenpei()//分配资源
{
cout<<"Available:
";
cout<for(intj=0;j<5;j++)p[j].finishflag=0;
while(finishcnt<5)
{
for(inti=0;i<5;i++)
{
if(p[i].finishflag==0&&q.av_a>=p[i].need.n_a&&q.av_b>=p[i].need.n_b&&q.av_c>=p[i].need.n_c)
{
q.av_a+=p[i].allocation.a_a;q.av_b+=p[i].allocation.a_b;q.av_c+=p[i].allocation.a_c;p[i].finishflag=1;finishcnt++;na[k++]=p[i].name;
break;
}
}
count++;//禁止循环过多if(count>5)return0;
}
return1;
}
//****************************************************intshq() //申请资源
{
intm=0,i=0,j=0,k=0; //m为进程号;i,j,k为申请的三类资源数
cout<<"请输入进程号和请求资源的数目!
"<cout<<"如:
进程号资源ABC"<>m>>i>>j>>k;
if(i<=p[m].need.n_a&&j<=p[m].need.n_b&&k<=p[m].need.n_c)
{
if(i<=q.av_a&&j<=q.av_b&&k<=q.av_c)
{
}
else
}
else
p[m].allocation.a_a+=i;p[m].allocation.a_b+=j;p[m].allocation.a_c+=k;
p[m].need.n_a=p[m].max.m_a-p[m].allocation.a_a;p[m].need.n_b=p[m].max.m_b-p[m].allocation.a_b;p[m].need.n_c=p[m].max.m_c-p[m].allocation.a_c;
cout<<"各进程还需要的资源数NEED:
"<<'\n';for(intw=0;w<5;w++)
cout<
"<
<<""<
cout<<"Request>Available让进程"<cout<<"Request>Need,让进程"<return0;
}
//********************************************voidmain()
{
intflag;charc;
cout<<" /********银 行 家 算 法********/ "<cout<<"确认已经在\"1.txt\"文档中正确输入各进程的有关信息后按回车键"<init();
q.av_a=10; //各种资源的数量q.av_b=5;
q.av_c=7;
while(flag)
{
for(inti=0;i<5;i++)
{
q.av_a-=p[i].allocation.a_a;q.av_b-=p[i].allocation.a_b;q.av_c-=p[i].allocation.a_c;
}
if(fenpei())
{
cout<<"这样配置资源是安全的!
"<cout<<"其安全序列是:
";for(intk=0;k<5;k++)cout<<"-->"<cout<<"有进程发出Request请求向量吗?
(EnteryorY)"<c=getch();if(c=='y'||c=='Y')
{
if(shq())continue;elsebreak;
}
elseflag=0;
}
else
{flag=0;
cout<<"不安全!
!
!
"<}
}
八.运行结果
一. 实验目的
实验三 存储管理
存储管理的主要功能之一是合理地分配空间。
请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。
二. 实验内容
(1)通过计算不同算法的命中率比较算法的优劣。
同时也考虑了用户内存容量对命中率的影响。
页面失效次数为每次访问相应指令时,该指令所对应的页不在内存中的次数。
命中率=1-页面失效次数
页地址流长度
在本实验中,假定页面大小为1k,用户虚存容量为32k,用户内存容量为4页到32页。
(2)produce_addstream通过随机数产生一个指令序列,共320条指令。
A、指令的地址按下述原则生成:
1)50%的指令是顺序执行的
2)25%的指令是均匀分布在前地址部分
3)25%的指令是均匀分布在后地址部分
B、具体的实施方法是:
1)在[0,319]的指令地址之间随机选取一起点m;
2)顺序执行一条指令,即执行地址为m+1的指令;
3)在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’;
4)顺序执行一条指令,地址为m’+1的指令
5)在后地址[m’+2,319]中随机选取一条指令并执行;
6)重复上述步骤1)~5),直到执行320次指令
C、将指令序列变换称为页地址流
在用户虚存中,按每k存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第0条~第9条指令为第0页(对应虚存地址为[0,9]);
第10条~第19条指令为第1页(对应虚存地址为[10,19]);
。
。
。
第310条~第319条指令为第31页(对应虚存地址为[310,319]);按以上方式,用户指令可组成32页。
(3)计算并输出下属算法在不同内存容量下的命中率。
1)先进先出的算法(FIFO);
2)最近最少使用算法(LRU);
3)最佳淘汰算法(OPT);
4)最少访问页面算法(LFR);其中3)和4)为选择内容
三. 系统框图
开 始
生成地址流
N
1≤S≤4
Y
是否用其他算
法继续
N
结束
Msize≤32
Y
S=?
1
2
3
4
LFU()
LRU()
FIFO()
OPT()
用户内存空间msize=2
提示出错,重新输入
输入算法号S
形成地址页号
Msize加1
四.页面置换算法程序代码:
#include#include#include
constintMAXSIZE=1000;//定义最大页面数constintMAXQUEUE=3;//定义页框数typedefstructnode
{intloaded;inthit;
}page;
pagepages[MAXQUEUE];//定义页框表intqueue[MAXSIZE];
intquantity;//初始化结构函数voidinitial()
{
inti;for(i=0;i{
pages[i].loaded=-1;pages[i].hit=0;}
for(i=0;i{
queue[i]=-1;
}
quantity=0;
}//初始化页框函数voidinit()
{
inti;for(i=0;i{
pages[i].loaded=-1;pages[i].hit=0;
}
}//读入页面流voidreadData()
{
FILE*fp;
charfname[20];inti;
cout<<"请输入页面流文件名:
";cin>>fname;if((fp=fopen(fname,"r"))==NULL)
{
}
else
{
cout<<"错误,文件打不开,请检查文件名";
while(!
feof(fp))
{
fscanf(fp,"%d",&queue[quantity]);quantity++;
}
}
cout<<"读入的页面流:
";for(i=0;i{
cout<}
}//FIFO调度算法
vo