实验四带优先级的时间片轮换的进程调度算法的实现.docx
- 文档编号:2185478
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:15
- 大小:18.10KB
实验四带优先级的时间片轮换的进程调度算法的实现.docx
《实验四带优先级的时间片轮换的进程调度算法的实现.docx》由会员分享,可在线阅读,更多相关《实验四带优先级的时间片轮换的进程调度算法的实现.docx(15页珍藏版)》请在冰点文库上搜索。
实验四带优先级的时间片轮换的进程调度算法的实现
实验四带优先级的时间片轮换的进程调度算法的实现
实验四带优先级的时间片轮换的进程调度算法的实现实验学时:
4
实验类型:
设计
实验要求:
必修
一、实验目的
(1)掌握进程状态转换过程
(2)掌握时间片轮转的进程调度算法;
(3)掌握带优先级的进程调度算法;
二、实验内容
(1)自定义PCB的数据结构;
(2)使用带优先级的时间片轮转法调度进程,每运行一个时间片,优先级减半。
(3)命令集
A)create随机创建进程,进程的优先级与所需要的时间片随机决定;
B)round执行1次时间片轮转操作,其方法为运行高优先级队列的第1个,再
降低其优先级,插入到相应的队列中。
C)ps查看当前进程状态
D)sleep命令将进程挂起
E)awake命令唤醒1个被挂起的进程
F)kill命令杀死进程
G)quit命令退出
(4)选用面向对象的编程方法。
三、实验原理或算法
本实验结合了进程状态转换、优先级调度、时间片轮转调度三方面的内容,根据进程状态转换图,设置SLEEP命令,将1个进程挂起,AWAKE命令唤醒1个被挂起的进程(从阻塞状态到就绪状态)。
1)优先级
优先级体现了进程的重要程度或紧迫程度,在大多数现代操作系统中,都采用了优先
级调度策略。
优先级从小到大(如0-127)优先级最高,127最低。
在本实验中按数值大小决定优先级,数值大的优先级高。
2)基于时间片调度
将所有的就绪进程按照先来先服务的原则,排成一个队列,每次调度时,将cpu分配给队首进程,并令其执行一个时间片。
当时间片用完时,由一个计时器发出时钟中断请求,调度程序把此进程终止,把该进程放到队尾。
在该实验中,时间片以100ms为单位(实际的要小得多)。
在调度过程中,需要通过时间函数检测进程的执行时间,当该进程执行时间?
时间片大小时,进行调度。
3)高优先级调度
优先级高的进程优先得到cpu,等该进程执行完毕后,另外的进程才能执行。
4)基于时间片的高优先级调度
在调度算法中,只有处于就绪状态的进程才能被调度,调度算法结合了优先级调度和时间片轮转调度算法,约定:
从最高优先级队列取第1个就绪状态的进程进行调度,时间片到后降低其优先级(降低一半),然后插入到低优先级队列的尾部,每次调度后,显示进程的状态。
四、程序清单
#include
#include
#include
//#include
#include
//定义进程数
#defineLEN10
//定义最高优先级
#defineMAXPIOR3
//定义时间片
#defineQUANTUM2
#definePCBsizeof(structpcb)
structpcb//PCB
{intident;//标识符
intstate;//状态0-就绪,1,运行,2,堵塞
intpior;//优先级,MAXPIOR为最高优先级*/
intlife;//生命期*/
structpcb*next;/*指针*/
}*array[MAXPIOR];
staticintidlist[LEN];/*标识符表*/
intlife=0;/*总生命期初始化为0*/
charstr[20];
charcommand[7][10];
intkilltest=0;
voidinit();
intcreate();
voidkill(intx);
voidprocess();
voidroutine();
voidps();
voidinit()
{
inti=0;
for(i=0;i array[i]=NULL; sprintf(command[0],"quit"); sprintf(command[1],"ps"); sprintf(command[2],"create"); sprintf(command[3],"kill"); sprintf(command[4],"round"); sprintf(command[5],"sleep"); sprintf(command[6],"awake");} intcreate() { inti=0,pior=0; structpcb*p,*q,*s; while(idlist[i]! =0&&i<=LEN-1) i++; if(i==LEN)return-1; idlist[i]=1; srand((unsigned)time(NULL)); pior=rand()%MAXPIOR;//最大优先级设定为0,2的整数 //printf("pior=%d\n",pior); s=(structpcb*)malloc(PCB);//createanodetokeeptheprocessmessege s->ident=i; s->state=0; s->pior=pior; s->life=1+rand()%20;//进程有生命期假设为1,20 s->next=NULL; life=life+(s->life); p=array[pior];//建立同优先级队列(链表) if(p==NULL) array[pior]=s; else { while(p! =NULL) { q=p; p=p->next; } q->next=s; } printf("successcreateprocessid=%d,currentprocessstatedispbelow: \n",s->ident); ps(); //printf("enddisplay\n"); return1; } voidps() {inti=0; structpcb*p; for(i=0;i {p=array[i]; while(p! =NULL) {printf("id: %d,state: %d,pior: %d,life: %d\n",p->ident,p->state,p->pior,p->life); p=p->next; } } } voidsleep(intx) {inti=0,test=0; structpcb*p=NULL,*q=NULL; while(test==0&&i! =MAXPIOR) {p=array[i]; if(i! =MAXPIOR&&p==NULL) { i++;continue; } while(p! =NULL) { if(p->ident==x) { test=1;killtest=1;break; } else { q=p;p=p->next; } } if(test==0)i++; }/*找到X所在指针*/ if(i==MAXPIOR) printf("Invaildprocessnumber."); else if(p->state==2) printf("theprocess%dhasblocked,cannotsleepagain! ",p->ident); else p->state=2; ps(); } voidawake(intx) {inti=0,test=0; structpcb*p=NULL,*q=NULL; while(test==0&&i! =MAXPIOR) {p=array[i]; if(i! =MAXPIOR&&p==NULL) { i++;continue; } while(p! =NULL) { if(p->ident==x) { test=1;killtest=1;break; } else { q=p;p=p->next; } } if(test==0)i++; }/*找到X所在指针*/ if(i==MAXPIOR) printf("Invaildprocessnumber."); else if(p->state==0) printf("theprocess%disreadystate,cannotawakeagain! ",p->ident); else p->state=0; ps(); } voidkill(intx) {inti=0,test=0; structpcb*p=NULL,*q=NULL; while(test==0&&i! =MAXPIOR) {p=array[i]; if(i! =MAXPIOR&&p==NULL) { i++;continue; } while(p! =NULL) { if(p->ident==x) { test=1;killtest=1;break; } else { q=p;p=p->next; } } if(test==0)i++; }/*找到X所在指针*/ if(i==MAXPIOR) printf("Invaildprocessnumber."); else { if(p==array[i]) { array[i]=array[i]->next; idlist[x]=0; free(p); } else { q->next=p->next; idlist[x]=0; life=life-(p->life); free(p); } } } voidprocess()//对输入命令的处理 {inti=0,ii=0; for(i=0;i<7;i++) if(stricmp(str,command[i])==0) break; switch(i) {case0: printf("thankyouforusingtheprogram! \n");exit(0); break; case1: ps(); break; case2: create(); break; case3: { printf("Whichprocessyouwanttokill? \n"); scanf("%d",&ii); kill(ii); break; } case4: routine();break; case5: printf("Whichprocessyouwanttosleep? \n"); scanf("%d",&ii); sleep(ii);break; case6: printf("Whichprocessyouwanttoawake? \n"); scanf("%d",&ii); awake(ii);break; default: printf("Errorcommand.Pleaseinputcreate,ps,kill,sleep,awake,quit\n"); } } voidroutine()//执行一次调度运行,将最高优先级队列的进程运行1个时间片,并降低其优先级 { inti=MAXPIOR-1,pior=0,t; structpcb*pp,*qq,*pr,*r; do { while(i>=0&&array[i]==NULL) i=i--; if(i<0) { printf("NOprocess,pleasecreateit! \n"); return; } pr=r=array[i]; while(r! =NULL&&r->state! =0){pr=r;r=r->next;} i--; } while(r==NULL);//从高优先队列中寻找就绪进程以调度它 printf("Theoneinthehightestpirorprocesswillexecute1quantum.\n"); r->state=1;//进程处于运行状态 printf("processid=%disrunning...",r->ident); for(intk=1;k<600000;k++) for(intk1=1;k1<1000;k1++);//延时 printf("end,changetoreadystate\n"); r->pior=(r->pior)/2; r->state=0;//进程处于就绪状态 if(r->life-QUANTUM>0) { r->life=r->life-QUANTUM;//时间减少QUANTUM life=life-QUANTUM; } else { life=life-r->life; r->life=0; } if(r->life==0)//进程运行完成,KILL它 { printf("theprocess%dissuccessfulrun,andreleaseit! \n",r->ident); kill(r->ident); } else { if(pr==r)//将r结点从原队列中删除 array[i+1]=r->next; else pr->next=r->next; t=r->pior;//将r进程加入到相应低优先级队列中的最后 pp=array[t]; qq=NULL; while(pp! =NULL) { qq=pp;pp=pp->next; } if(qq==NULL)//插入到队尾 array[t]=r; else qq->next=r; r->next=NULL; } printf("after...\n"); ps(); printf("\n1quantumsuccessfulrun! \n"); } //********************************** voidmain() {init(); printf("WelcometotheProcessSchedulingsystem.ThisprogramsimulatetheRound-Robinwith pirorSchedulingalogrithm.\n"); printf("c: \\>"); scanf("%s",str); process(); while(strcmp(str,"quit")! =0) { printf("\nc: \\>"); scanf("%s",str); process(); } } 五、实验结果分析 对算法时间、空间复杂度、结果进行分析。 六、思考题 (1)读懂程序画出算法所用的数据结构简图。 (2)修改routine()函数,使得算法能够模拟运行进程被外界中断或因请求设备而不能运行自动转入阻塞状态并进行调度。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 优先级 时间 轮换 进程 调度 算法 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)