多级队列调度算法银行家算法.docx
- 文档编号:2572180
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:18
- 大小:72.64KB
多级队列调度算法银行家算法.docx
《多级队列调度算法银行家算法.docx》由会员分享,可在线阅读,更多相关《多级队列调度算法银行家算法.docx(18页珍藏版)》请在冰点文库上搜索。
多级队列调度算法银行家算法
操作系统原理
上
机
报
告
院系:
计算机学院
班级:
191094—16
*******
学号:
***********
二O一一年六月
一:
银行家算法
实验目的:
1、了解并掌握银行家算法的思想;
2、通过编程实现银行家算法;
实验步骤:
1、安全状态:
系统按照某种序列为多个进程分配资源直到最大需求,如果能够保证所有进程全部顺利执行完毕,则称系统是安全的。
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;
gotostep
(2);
(4)若所有进程的finish[i]=true,则系统处于安全状态,否则,处于不安全状态。
5、具体代码实现如下
#definea5
#defineb3
#include
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<5;i++)
{
if(finish[i]==0)
{
for(intj=0;j<3;j++)
Need1[i][j]<=pro[j];
if(j<3)
{
for(intt=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);
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};
intfinish[a]={0,0,0,0,0};
intnum;
while
(1)
{
cout<<"请输入进程序列号:
";
cin>>num;
num--;
cout<<"请输入需要请示的资源序列:
";
cin>>request[0]>>request[1]>>request[2];
for(inti=0;i<3;i++)
{
if(request[i]<=Need[num][i]&&request[i]<=Available[i])continue;
elsebreak;
}
if(i<3)
{
cout<<"该进程阻塞!
"< continue; } else { for(intj=0;j<3;j++) { 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)) { for(intj=0;j<3;j++) { Available[j]=Available[j]+request[j]; Alloc[num][j]=Alloc[num][j]-request[j]; Need[num][j]=Need[num][j]+request[j]; } cout<<"新状态不稳定,资源回收"< } 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->need>piece_time) { clock+=piece_time; p->need-=piece_time; if(s! =NULL)s->next=p->next; q->next=p; p=p->next; q->next->next=NULL; } else { flag++; clock+=p->need; p->need=0; p->turn+=clock; if(flag==1)RQ1=p; s=p; p=p->next; } } while(p! =NULL&&p->need==0) p=p->next; } (2)//Test_of_Priority短进程优先调度 调度思想: 每个进程按进程执行时间长短被赋予一个优先级,进程越短优先级越高,进程越长优先级越低,优先级最高的就绪进程率先被运行。 为了防止高优先级的进程无休止的运行下去,调度程序可以在每一个时钟中断适当降低当前进程的优先级。 如果这时运行进程优先级低于次高优先级进程,则将进行进程切换。 //RQ2采用短进程优先调度算法。 for(i=0;i<5;i++) { q=RQ2; p=(PCB*)malloc(sizeof(PCB)); p->need=max; p->next=NULL; while(q! =NULL) { if(q->need! =0&&q->need q=q->next; } clock+=p->need; p->turn+=clock; p->need=0; } //输出各进程的周转时间 printf("输出各进程的周转时间如下: \n"); p=RQ1; printf("\nRQ1各进程运行时间如下"); while(p! =NULL) { printf("\n%s: %d",p->name,p->turn); p=p->next; } p=RQ2; printf("\nRQ2各进程运行时间如下"); while(p! =NULL) { printf("\n%s: %d",p->name,p->turn); p=p->next; } printf("\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 14 已等待时间 6 5 4 3 2 1 2 3 4 5 7、具体代码实现如下 #definemax10000 #include #include #include typedefstructtag_pcb { charname[8]; intneed; intturn; structtag_pcb*next; }PCB; PCB*RQ1,*RQ2; voidmain() { //各进程运行时间及等待时间 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]; RQ1->turn=wait1[0]; RQ1->next=NULL; p=RQ1; for(i=1;i<5;i++) { q=(PCB*)malloc(sizeof(PCB)); strcpy(q->name,name1[i]); q->need=need1[i]; q->turn=wait1[i]; p->next=q; q->next=NULL; p=p->next; } //RQ2链表的创建 RQ2=(PCB*)malloc(sizeof(PCB)); strcpy(RQ2->name,name2[0]); RQ2->need=need2[0]; RQ2->turn=wait2[0]; RQ2->next=NULL; p=RQ2; for(i=1;i<5;i++) { q=(PCB*)malloc(sizeof(PCB)); strcpy(q->name,name2[i]); q->need=need2[i]; q->turn=wait2[i]; p->next=q; q->next=NULL; p=p->next; } //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->need>piece_time) { clock+=piece_time; p->need-=piece_time; if(s! =NULL)s->next=p->next; q->next=p; p=p->next; q->next->next=NULL; } else { flag++; clock+=p->need; p->need=0; p->turn+=clock; if(flag==1)RQ1=p; s=p; p=p->next; } } while(p! =NULL&&p->need==0) p=p->next; } //RQ2采用短进程优先调度算法。 for(i=0;i<5;i++) { q=RQ2; p=(PCB*)malloc(sizeof(PCB)); p->need=max; p->next=NULL; while(q! =NULL) { if(q->need! =0&&q->need q=q->next; } clock+=p->need; p->turn+=clock; p->need=0; } //输出各进程的周转时间 printf("输出各进程的周转时间如下: \n"); p=RQ1; printf("\nRQ1各进程运行时间如下"); while(p! =NULL) { printf("\n%s: %d",p->name,p->turn); p=p->next; } p=RQ2; printf("\nRQ2各进程运行时间如下"); while(p! =NULL) { printf("\n%s: %d",p->name,p->turn); p=p->next; } printf("\n\n\n"); }8运行情况如下 程序运行结果与所期待的理论值一致 9实验分析及心得体会如下: 通过该程序的设计、编译、实现,我更好地了解银行家算法,循环轮转法,短进程优先调度算法的设计与实现,实验过程中通过调试分析,自己的编程能力有所提高。 一.通过实现银行家算法,我明白了进程之间的关系及资源分配的实质,对于死锁问题的检查,银行家算法简便易行。 在安全性算法中,当安全性算法检测为不安全时,要将资源返还。 安全性算法 设置两个向量: 工作向量pro,它表示系统可提供给进程继续运行所需的各类资源数目,执行安全性算法开始时,pro初值=Available;finish表示系统是否有足够的资源分配给里程,使之运行完成,开始时,finish[i]=0;当有足够资源分配给进程时,令finish[i]=1; (2)从进程集合中找到满足下述条件的进程: finish[i]=0; Need[i]<=pro;若找到执行(3),否则执行(4); (3)当进程Pi获得资源后,顺序执行直到完成,并释放它的资源,执行: Pro=pro+Allocation[i]; finish[i]=1; gotostep (2); (4)若所有进程的finish[i]=1,则系统处于安全状态,否则,处于不安全状态。 二.循环轮转和短程优先算法是一种操作系统的基础模拟,实现原理以及实现过程都不复杂,基本思想如下: (1)循环轮转法: 轮转法将CPU时间划分成若干个短的时间片断(通常小于100ms),将这些时间片断轮流分配给各个就绪进程使用。 如果时间片结束时,进程还没有运行完,则CPU将被剥夺并分配给另一个就绪进程使用;如果进程在时间片结束前阻塞或结束,则CPU理解发生切换。 (2)短进程优先调度: 每个进程按进程执行时间长短被赋予一个优先级,进程越短优先级越高,进程越长优先级越低,优先级最高的就绪进程率先被运行。 为了防止高优先级的进程无休止的运行下去,调度程序可以在每一个时钟中断适当降低当前进程的优先级。 如果这时运行进程优先级低于次高优先级进程,则将进行进程切换。 通过编程对循环轮转法和短进程优先调度算法这两个算法的模拟,自己的编程能力及解决实际问题的能力有所提高,并且对操作系统的工作模式有了更进一步的了解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多级 队列 调度 算法 银行家