操作系统课程设计报告 银行家算法+磁盘调度Word格式文档下载.docx
- 文档编号:6623644
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:33
- 大小:407.72KB
操作系统课程设计报告 银行家算法+磁盘调度Word格式文档下载.docx
《操作系统课程设计报告 银行家算法+磁盘调度Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《操作系统课程设计报告 银行家算法+磁盘调度Word格式文档下载.docx(33页珍藏版)》请在冰点文库上搜索。
随着计算机技术发展,计算机已经应用的各个领域,促进了各行各业的发展。
与此同时,人们对计算机的要求也越来越高,其中就包括对计算机操作系统的要求。
人们希望操作系统更加合理配置计算机硬件系统的有限资源,更方便操作计算机硬件系统。
通过模拟,反映了操作系统如何合理有效的管理和分配资源。
1.1课程设计的背景和意义
1.1.1课程设计的理论研究基础
在多道程序系统中,虽可以借助于多个进程的并发执行来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险——多个进程在运行过程中因争夺资源而造成僵持,当进程处于这种僵持状态时,若无外力作用,他们都将无法继续向前推进,即死锁。
而银行家算法是最具代表性的避免死锁的算法。
银行家算法和安全检查算法:
磁盘是可供多个进程共享的设备,当有多个进程都要求访问磁盘时,应采取一种最佳调度算法,以使各进程对磁盘的平均访问时间最小。
由于在访问磁盘的时间中,主要是寻道时间,因此,磁盘调度的目标是使磁盘的平均寻道时间最少。
磁盘调度算法:
1.1.2课程设计的意义
通过课程设计,可以更深入理解操作系统中的部分经典算法,了解操作系统的工作原理。
1.2课程设计环境
编程环境介绍
运行环境:
WindowsXP3或Windows7
工具软件:
MircosoftVisualC++6.0
硬件环境:
处理器1.5GHz以上,内存1GB,显卡256M
第二章需求分析
2.1功能要求
2.1.1银行家算法
2.1.2磁盘调度算法
2.2问题的解决方案
第三章系统设计
3.1数据设计
3.1.1数据结构设计
1.银行家算法的数据结构设计
(1)可用资源向量Available[m],Available[j]=k表示系统中现有Rj类资源K个。
(2)最大需求矩阵Max[n][m],Max[i][j]=K表示进程i需要Rj类资源的最大数目为K个。
(3)分配矩阵Allocation[n][m],Allocation[i][j]=K表示进程i当前已分配得到Rj类资源的数目为K个。
(4)需求矩阵Need[n][m],Need[i][j]=K表示进程i还需要Rj类资源K个。
其满足
Need[i][j]=Max[i][j]-Allocation[i][j]。
(5)Request[n][m],Request[i][j]=K表示进程Pi需要K个Rj类型的资源。
2.磁盘调度算法的数据结构设计
(1)cidao[m],存放存入请求访问的磁道号。
3.1.2数据之间的关系
需求矩阵Need[n][m],Need[i][j]=Max[i][j]-Allocation[i][j]。
3.1.3函数设计
1.银行家算法函数设计
voidInput();
//用于输入的函数
voidOutput();
//用于打印输出表格的函数
voidAlloc();
//试分配给进程i
intSafecheck();
//安全检测函数
voidRedata(inti);
//恢复原来的资源分配状态
Alloc函数,当Pi发出资源请求后,系统按下述步骤进行检查:
(1)如果Request[i][j]<
=Need[i][j],便转向步骤
(2);
否则认为出错,因为它所需要的资源数已经超过它所宣布的最大值。
(2)如果Request[i][j]<
=Available[j],便转向步骤(3);
否则表示尚无足够资源,Pi须等待。
(3)系统试探着把资源分配给进程Pi,并修改下面的数据结构中的数值:
Available[j]=Available[j]-Request[i][j];
Allocation[n][m]=Allocation[n][m]+Request[i][j];
Need[i][j]=Need[i][j]-Request[i][j];
(4)系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。
若安全,才分配,否则本次试探作废,恢复原来的资源分配状态。
Safecheck函数
(1)设置两个向量
工作向量Work[m],表示系统可提供给进程继续运行所需的各类资源数目,在执行安全算法之前,Work=Available;
完成向量Finish[m],表示系统是否有足够的资源分配给进程,使之运新完成。
开始时Finish=-1即不能。
分配完Finish=1
(2)从进程集合中找到一个能满足下述条件的进程:
Finish[i]=-1;
Need[i]<
=Work[j]若找到,执行(3),否则,执行(4)
(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放分配给它的资源,继续
(2);
(4)如果所有进程的Finish[i]=1都满足,表示系统处于安全状态,否则系统处于不安全状态。
2.磁盘调度算法函数设计
int*bubble(intcidao[],intm)//使用冒泡法按从小到大顺序排列
voidFCFS(intcidao[],intm)//先来先服务
voidSSTF(intcidao[],intm)//最短寻道时间优先
voidSCAN(intcidao[],intm)//扫描算法
voidCSCAN(intcidao[],intm)//循环扫描算法
第四章系统实现
4.1数据结构实现
银行家算法数据结构:
intAvailable[3];
//Available三类资源(A,B,C)的可利用量
intSum[3]={10,5,7};
//Sum为各类资源总数
intRequest[3];
//Request三类资源(A,B,C)申请资源量
intMax[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
//三类资源(A,B,C)的最大需求量
intAllocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
//三类资源(A,B,C)已分配量
intNeed[5][3];
//三类资源(A,B,C)进程需求量
4.2函数实现
银行家算法函数实现
voidAlloc()//分配给进程i
{
inti,j;
intflag;
charyes;
do
{
cout<
<
"
进程号(0~4):
;
cin>
>
i;
if(i>
4||i<
0)cout<
进程号不正确,请重输:
endl;
}while(i>
0);
cout<
请求量(3种资源):
for(j=0;
j<
3;
j++)
Request[j];
flag=0;
//初始化为0,即未请求或请求未成功
if(Request[j]<
=Need[i][j])//实际需求量未超过理论需求量
{
if(Request[j]<
=Available[j])//资源足够
flag=1;
//表示请求符合条件,可以分配
else
{
cout<
资源不足,请等待!
return;
}
}
else
cout<
资源超过最大需求量"
flag=0;
return;
}
if(flag==1)//对于符合条件可以分配的进程请求
for(j=0;
j++)//把资源分配给该进程
Available[j]=Available[j]-Request[j];
Allocation[i][j]=Allocation[i][j]+Request[j];
Need[i][j]=Need[i][j]-Request[j];
if(Safecheck()==1)//执行安全检查,此次资源分配后系统处于安全状态
分配安全,是否确定分配(Y):
cin>
yes;
yes=toupper(yes);
if(yes=='
Y'
)
分配成功"
Redata(i);
分配不安全"
Redata(i);
}
intSafecheck()//安全性检查
inti=0,j=0,k=0,flag1,flag2,count=0;
//flag用于描述每次
intqueue[MAX];
intwork[3];
//系统可提供给进程继续运行所需的各类资源数目
intfinish[5];
//-1表示未被执行,1表示已被执行
work[j]=Available[j];
//在执行安全算法开始时,Work=Available
for(i=0;
i<
5;
i++)
finish[i]=-1;
//初始化,均未被执行
flag1=0;
//do```while循环运行标识
for(i=0;
if(finish[i]==-1)//进程未执行,向下进行
for(j=0;
j++)//三种资源都满足才可分配,flag2=1;
否则flag2=0
{
if(Need[i][j]<
=work[j])
flag2=1;
//满足分配条件
else
{
flag2=0;
//表示资源不够
break;
}
}
if(flag2==1)//满足分配条件(三种资源都可以分配)
flag1=1;
//表示有可以分配资源的进程,分配完后重新从头查找
for(j=0;
work[j]=work[j]+Allocation[i][j];
//运行完后回收资源
finish[i]=1;
//表示该进程已经执行完毕
queue[count]=i;
//将进程号存入数组queue中
count++;
break;
}while(flag1);
if(count==5)
分配安全,找到一个安全序列:
count;
queue[i]<
-->
|work|Need|Allocation|work+Allocation|finish|"
|ABC|ABC|ABC|ABC||"
work[i]=Available[i];
k=queue[i];
p"
k<
|"
for(j=0;
"
work[j]<
|"
Need[k][j];
Allocation[k][j]<
|"
work[j]=work[j]+Allocation[k][j];
finish[k]<
return1;
else
分配不安全,本次资源申请不成功!
return0;
voidRedata(inti)//恢复分配
for(intj=0;
Available[j]=Available[j]+Request[j];
Allocation[i][j]=Allocation[i][j]-Request[j];
Need[i][j]=Need[i][j]+Request[j];
数据已恢复初始状态..."
voidFCFS(intcidao[],intm)//先来先服务磁道号数组,个数为m
intnow;
//当前磁道号
intsum=0;
//总寻道长度
intj,i;
floatave;
//平均寻道长度
磁盘请求序列为:
for(i=0;
m;
i++)//按先来先服务的策略输出磁盘请求序列
cidao[i]<
请输入当前的磁道号:
cin>
now;
sum+=abs(cidao[0]-now);
//求绝对值
磁盘扫描序列为:
i++)//输出磁盘扫描序列
for(i=0,j=1;
i++,j++)//求平均寻道长度
sum+=abs(cidao[j]-cidao[i]);
ave=(float)(sum)/(float)(m);
平均寻道长度:
ave<
voidSSTF(intcidao[],intm)//最短寻道时间优先磁道号数组,个数为m
intk=1;
intnow,l,r;
inti,j,sum=0;
cidao=bubble(cidao,m);
//调用冒泡排序算法排序从小到大
now;
if(cidao[m-1]<
=now)//若当前磁道号大于请求序列中最大者,则直接由外向内依次给予各请求服务
for(i=m-1;
i>
=0;
i--)
sum=now-cidao[0];
if(cidao[0]>
=now)//若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务
sum=cidao[m-1]-now;
if(now>
cidao[0]&
&
now<
cidao[m-1])//若当前磁道号大于请求序列中最小者且小于最大者
while(cidao[k]<
now)//确定当前磁道在已排的序列中的位置,后面的算法都用到了,可以直接复制后少量修改,节省时间。
k++;
l=k-1;
r=k;
while((l>
=0)&
(r<
m))//当前磁道在请求序列范围内
{//选择与当前磁道最近的请求给予服务
if((now-cidao[l])<
=(cidao[r]-now))//从当前磁道向前移动
cidao[l]<
sum+=now-cidao[l];
now=cidao[l];
l=l-1;
else//从当前磁道向后移动
cidao[r]<
sum+=cidao[r]-now;
now=cidao[r];
r=r+1;
if(l==-1)//磁头移动到序列的最小号,返回外侧扫描仍未扫描的磁道
for(j=r;
cidao[j]<
sum+=cidao[m-1]-cidao[0];
else//磁头移动到序列的最大号,返回内侧扫描仍未扫描的磁道
for(j=l;
j>
j--)
voidSCAN(intcidao[],intm)//扫描算法先要给出当前磁道号和移动臂的移动方向
intnow,l,r,d;
//d为磁头移动臂移动方向选择
=now)//若当前磁道号大于请求序列中最大者,则直接由外向内依次给予各请求服务,此情况同最短寻道优先
{
=now)//若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务,此情况同最短寻道优先
now)//确定当前磁道在已排的序列中的位置
请输入当前移动臂的移动的方向(1表示向外-->
,0表示向内<
--):
d;
if(d==0)//选择移动臂方向向内,则先向内扫描
//输出向内扫描的序列
j++)//磁头移动到最小号,则改变方向向外扫描未扫描的磁道
//输出向外扫描的序列
sum=now-2*cidao[0]+cidao[m-1];
else//选择移动臂方向向外,则先向外扫描
j--)//磁头移动到最大号,则改变方向向内扫描未扫描的磁道
sum=-now-cidao[0]+2*cidao[m-1];
}
endl
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统课程设计报告 银行家算法+磁盘调度 操作系统 课程设计 报告 银行家 算法 磁盘 调度