多级队列调度算法银行家算法Word文件下载.docx
《多级队列调度算法银行家算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《多级队列调度算法银行家算法Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
=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；
gotostep
（2）;
（4）若所有进程的finish[i]=true，则系统处于安全状态，否则，处于不安全状态。
5、具体代码实现如下
#definea5
#defineb3
#include<
iostream.h>
intDistribution_of_test（int*Available1,intNeed1[5][3],intAlloc[5][3]）
{
intfinish[a]={0,0,0,0,0};
intpro[b];
for（inti=0;
i<
3;
i++）pro[i]=Available1[i];
for（inth=0;
h<
5;
h++）
for（inti=0;
i++）
{
if（finish[i]==0）
{
for（intj=0;
j<
j++）
Need1[i][j]<
=pro[j];
if（j<
3）
{
for（intt=0;
t<
t++）pro[t]=pro[t]+Alloc[i][t];
finish[i]=1;
}
}
}
for（i=0;
if（finish[i]）;
if（i<
5）return（0）;
elsereturn
（1）;
}
voidmain（）
intAvailable[b]={2,3,3};
intAlloc[a][b]={{2,1,2},{4,0,2},{3,0,5},{2,0,4},{3,1,4}};
intNeed[a][b]={{3,4,7},{1,3,4},{0,0,3},{2,2,1},{1,1,0}};
intrequest[3]={0,0,0};
intnum;
while
（1）
{
cout<
<
"
请输入进程序列号:
;
cin>
>
num;
num--;
请输入需要请示的资源序列:
request[0]>
request[1]>
request[2];
if（request[i]<
=Need[num][i]&
&
request[i]<
=Available[i]）continue;
elsebreak;
if（i<
cout<
该进程阻塞!
endl;
continue;
else
for（intj=0;
Available[j]=Available[j]-request[j];
Alloc[num][j]=Alloc[num][j]+request[j];
Need[num][j]=Need[num][j]-request[j];
if（!
Distribution_of_test（Available,Need,Alloc））
Available[j]=Available[j]+request[j];
Alloc[num][j]=Alloc[num][j]-request[j];
Need[num][j]=Need[num][j]+request[j];
新状态不稳定,资源回收"
elsecout<
新状态稳定,资源实际分配!
}
请求序列如下：
a.进程P2请求资源（0，3，4）
b．进程P4请求资源（1，0，1）
c.进程P1请求资源（2，0，1）
d.进程P3请求资源（0，0，2）
预期实验结果如下：
请输入进程序号:
2
请输入需要请求的资源序列:
034
4
101
1
201
3
002
该运行结果与实验预期结果相符,即实现了银行家算法
二：
多级队列调度算法
1.了解进程高度算法的原理及物理变换；
2.掌握简单轮转调度算法和短程优先调度算法，并对两种算法的效率进行简单分析
1.设置好各种队列，两种算法均以链表作为调度队列，因为两种算法均只需要一个队列就能满足调度。
2.第一种算法的思想是采用的轮转调试，第二种采用的是短进程优先算法，确定好算法步骤，进行输入测试。
3设RQ分为RQ1和RQ2，RQ1采用轮转法，时间q=7.
RQ1>
RQ2，RQ2采用短进程优先调度
4、采取的数据结构
typedefstructtag_pcb
charname[8];
intneed;
intturn;
structtag_pcb*next;
}PCB;
5,大体设计思路
（1）/Test_of_Rotation_cycle循环轮转法
轮转法将CPU时间划分成若干个短的时间片断（通常小于100ms），将这些时间片断轮流分配给各个就绪进程使用。
如果时间片结束时，进程还没有运行完，则CPU将被剥夺并分配给另一个就绪进程使用；
如果进程在时间片结束前阻塞或结束，则CPU理解发生切换。
//RQ1采用轮转法
p=RQ1;
intflag=0;
while（p!
=NULL）
{
while（p!
=NULL&
p->
need>
0）
q=p;
while（q->
next!
=NULL）q=q->
next;
if（p->
piece_time）
clock+=piece_time;
p->
need-=piece_time;
if（s!
=NULL）s->
next=p->
q->
next=p;
p=p->
next->
next=NULL;
else
flag++;
clock+=p->
need;
p->
need=0;
turn+=clock;
if（flag==1）RQ1=p;
s=p;
while（p!
need==0）
p=p->
（2）//Test_of_Priority短进程优先调度
调度思想：
每个进程按进程执行时间长短被赋予一个优先级，进程越短优先级越高，进程越长优先级越低，优先级最高的就绪进程率先被运行。
为了防止高优先级的进程无休止的运行下去，调度程序可以在每一个时钟中断适当降低当前进程的优先级。
如果这时运行进程优先级低于次高优先级进程，则将进行进程切换。
//RQ2采用短进程优先调度算法。
for（i=0;
q=RQ2;
p=（PCB*）malloc（sizeof（PCB））;
need=max;
while（q!
if（q->
need!
=0&
q->
need<
need）p=q;
q=q->
clock+=p->
//输出各进程的周转时间
printf（"
输出各进程的周转时间如下:
\n"
）;
printf（"
\nRQ1各进程运行时间如下"
\n%s:
%d"
p->
name,p->
turn）;
p=p->
p=RQ2;
\nRQ2各进程运行时间如下"
\n\n\n"
6测试数据如下
设RQ分为RQ1和RQ2，RQ1采用轮转法，时间q=7.RQ1>
RQ2，RQ2采用短进程优先调度算法。
测试数据如下：
RQ1:
P1-P5,RQ2:
P6-P10
进程
P1
P2
P3
P4
P5
P6
P7
P8
P9
P10
运行时间
16
11
14
13
15
21
18
10
7
已等待时间
6
5
7、具体代码实现如下
#definemax10000
stdio.h>
string.h>
malloc.h>
charname[8];
intneed;
intturn;
structtag_pcb*next;
PCB*RQ1,*RQ2;
{
//各进程运行时间及等待时间
PCB*p,*q,*s=NULL;
inti,clock=0,piece_time=7;
charname1[5][8]={"
p1"
"
p2"
p3"
p4"
p5"
};
charname2[5][8]={"
p6"
p7"
p8"
p9"
p10"
intneed1[5]={16,11,14,13,15},wait1[5]={6,5,4,3,2};
intneed2[5]={21,18,10,7,14},wait2[5]={1,2,3,4,5};
//RQ1链表的创建
RQ1=（PCB*）malloc（sizeof（PCB））;
strcpy（RQ1->
name,name1[0]）;
RQ1->
need=need1[0];
turn=wait1[0];
for（i=1;
q=（PCB*）malloc（sizeof（PCB））;
strcpy（q->
name,name1[i]）;
q->
need=need1[i];
turn=wait1[i];
next=q;
//RQ2链表的创建
RQ2=（PCB*）malloc（sizeof（PCB））;
strcpy（RQ2->
name,name2[0]）;
RQ2->
need=need2[0];
turn=wait2[0];
name,name2[i]）;
need=need2[i];
turn=wait2[i];
//RQ1采用轮转法
}8运行情况如下
程序运行结果与所期待的理论值一致
9实验分析及心得体会如下：
通过该程序的设计、编译、实现，我更好地了解银行家算法，循环轮转法，短进程优先调度算法的设计与实现，实验过程中通过调试分析，自己的编程能力有所提高。
一．通过实现银行家算法，我明白了进程之间的关系及资源分配的实质，对于死锁问题的检查，银行家算法简便易行。
在安全性算法中，当安全性算法检测为不安全时,要将资源返还。
安全性算法
设置两个向量：
工作向量pro，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，pro初值=Available；
finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=0；
当有足够资源分配给进程时，令finish[i]=1；
finish[i]=0；
=pro；
Pro=pro+Allocation[i]；
finish[i]=1；
（4）若所有进程的finish[i]=1，则系统处于安全状态，否则，处于不安全状态。
二．循环轮转和短程优先算法是一种操作系统的基础模拟，实现原理以及实现过程都不复杂，基本思想如下：
（1）循环轮转法：
（2）短进程优先调度：
通过编程对循环轮转法和短进程优先调度算法这两个算法的模拟，自己的编程能力及解决实际问题的能力有所提高，并且对操作系统的工作模式有了更进一步的了解。
升级会员 