多级队列调度算法.doc

操作系统原理
上
机
报
告
院系: 计算机学院
班级: 191094—16
姓名: 熊金莲
学号: 20091003768

二 O 一一年六月
一:银行家算法
实验目的:
1、了解并掌握银行家算法的思想;
2、通过编程实现银行家算法;
实验步骤:
安全状态:系统按照某种序列为多个进程分配资源直到最大需求,如果能够保证所有进程全部顺利执行完毕,则称系统是安全的。
2、采取的数据结构
(1)可利用资源量Available
(2)最大需求矩阵Max
(3)分配矩阵Allocation[i]
(4)需求矩阵Need[i]
(5)请求矩阵Request[i]
3、银行家算法
设request:是Pi进程的请求向量,当Pi发了资源请求后,系统按下述步骤检查:
(1)如果Request[i]<= Need[i],则转向步骤(2);
(2)若Request[i] <=Available,则转向步骤(3);
(3)系统试探性地把要求的资源分配给进程Pi,并修改以下数据结构的值:
Available=Available-Request[i];
Allocation[i]= Allocation[i]+ Request[i];
Need[i]= Need[i]- Request[i];
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态,若安全,才正式将资源分配给Pi进程,完成本次分配;否则,试探性分配作废,恢复原来的资源分配状态,Pi进程进入等待状态。
4、安全性算法
(1)设置两个向量:工作向量work,它表示系统可提供给进程继续运行所需的各类资源数目,执行安全性算法开始时,work初值=Available;finish表示系统是否有足够的资源分配给里程,使之运行完成,开始时,finish[i]=false;当有足够资源分配给进程时,令finish[i]=true;
(2)从进程集合中找到满足下述条件的进程:
finish[i]= false;
Need[i] <= work;若找到执行(3),否则执行(4);
(3)当进程Pi获得资源后,顺序执行直到完成,并释放它的资源,执行:
work= work+ Allocation[i];
finish[i]= true;
go to step(2);
(4)若所有进程的finish[i]= true,则系统处于安全状态,否则,处于不安全状态。
5、具体代码实现如下
#define a 5
#define b 3
#include<>
int Distribution_of_test(int *Available1,int Need1[5][3],int Alloc[5][3])
{
int finish[a]={0,0,0,0,0};
int pro[b];
for(int i=0;i<3;i++) pro[i]=Available1[i];
for(int h=0;h<5;h++)
for(int i=0;i<5;i++)
{
if(finish[i]==0)
{
for(int j=0;j<3;j++)
Need1[i][j]<=pro[j];
if(j<3)
{
for(int t=0;t<3;t++) pro[t]=pro[t]+Alloc[i][t];
finish[i]=1;
}
}
}
for(i=0;i<5;i++)
if(finish[i]);
if(i<5) return(0);
else return(1);
}
void main()
{
int Available[b]={2,3,3};
int Alloc[a][b]={{2,1,2},{4,0,2},{3,0,5},{2,0,4},{3,1,4}};
int Need[a][b]={{3,4,7},{1,3,4},{0,0,3},{2,2,1},{1,1,0}};
int request[3]={0,0,0};
int finish[a]={0,0,0,0,0};
int num;
while(1)
{
cout<<"请输入进程序列号:";
cin>>num;
num--;
cout<<"请输入需要请示的资源序列:";
cin>>request[0]>>request[1]>>request[2];
for(int i=0;i<3;i++)
{
if(request[i]<=Need[num][i]&&request[i]<=Ava