FPF和RR调度算法

郑州轻工业学院本科实验报告设计题目：实现FPF和RR调度算法学生姓名：李洋系别：计算机与通信工程学院专业：网络运维班级：13-03学号：521507110314指导教师：吴庆岗2015年11月18日一、实验目的编写程序，实现FPF和RR算法，模拟进程调度过程，加深对作业调度的理解。二、实验内容实现FPF和RR调度算法。–数据结构设计（PCB，进程就绪队列）–算法实现与模拟（排序、调度）–输出调度结果，展示调度过程并解释三、实验要求1.设计进程控制块(PCB)的数据结构–应包含实验必须的数据项，如进程ID、需要的服务时间、进入系统时间、完成时间、周转时间、优先权、进程状态（R-运行，W-等待），以及实验者认为有必要的其他数据项。2.实现排序算法（将就绪队列中的进程排序）–RR：只需在开始时排序，按FCFS策略将进程依次插入就绪队列。开始运行后不再需要排序，按RR策略将每一个刚刚运行完一个时间片的进程插入到队尾。–FPF：每次调度前排序，按计算所得的动态优先权排成有序队列，最高优先权排进程在队首，优先权相同的进程按FCFS策略排队。3.实现RR调度过程模拟①每个进程用一个PCB表示，按FCFS策略排成就绪队列，按照固定的周期循环调度。②选择队首的进程，将其从就绪队列移出，修改其状态为R。③经过一个时间片，如果正在执行的进程没有执行完，修改其状态为W，插入到就绪队列尾部。如果执行完毕，计算其周转时间。④进行下一次调度（去往第②步），直到就绪队列为空。4.实现FPF调度过程模拟①每个进程用一个PCB表示。②计算动态优先权，按优先权高低排入就绪队列，如果相同，则按FCFS排队。系统开始时调度，每个进程结束时进行调度。③选择队首的作业，将其从后备队列移出④计算选中作业的周转时间（进程运行过程，在本实验中，无需实现，可认为就绪队列上的进程一但被调度程序选出，就顺利运行结束）⑤进行下一次调度（去往第②步）5.实现结果输出–输出进程状态表，展示调度过程•初始进程状态（未调度时）•每次调度后的进程状态6.撰写实验报告–包含实验要求中1~4项内容，要求有设计图（结构图/流程图）和源代码。–注明使用的编程语言和环境。注意事项•实验中注重实现算法本质（高优先权优先FPF，时间片轮转RR）。•两个算法可以选做一个，量力而行，鼓励多做。•FPF算法也适用于作业调度。关于作业调度和进程调度的区别，只要求概念上理解清楚，不要求实现。#includestdio.h#includestdlib.hstructPCB{charp_name[20];intp_priority;intp_needTime;intp_runTime;charp_state;structPCB*next;};voidHighPriority();voidRoundRobin();voidInformation();charChoice();structPCB*SortList(PCB*HL);intmain(){Information();charchoice=Choice();switch(choice){case'1':system(cls);HighPriority();break;default:break;}system(pause);return0;}voidInformation(){printf(按回车键进入演示程序);getchar();system(cls);}charChoice(){printf(\n\n);printf(1.演示最高优先数优先算法。);printf(按1继续:);charch=getchar();returnch;system(cls);}voidHighPriority(){structPCB*processes,*pt;//pt作为临时节点来创建链表，使用for语句，限制进程数为5个processes=pt=(structPCB*)malloc(sizeof(structPCB));for(inti=0;i!=5;++i){structPCB*p=(structPCB*)malloc(sizeof(structPCB));printf(进程号No.%d：\n,i);printf(输入进程名：);scanf(%s,p-p_name);printf(输入进程优先数：);scanf(%d,&p-p_priority);printf(输入进程运行时间：);scanf(%d,&p-p_needTime);p-p_runTime=0;p-p_state='W';p-next=NULL;pt-next=p;pt=p;printf(\n\n);}getchar();//接受回车//processes作为头结点来存储链表processes=processes-next;intcases=0;structPCB*psorted=processes;while(1){++cases;pt=processes;//对链表按照优先数排序//psorted用来存放排序后的链表psorted=SortList(psorted);printf(Theexecutenumber:%d\n\n,cases);printf(****当前正在运行的进程是：%s\n,psorted-p_name);psorted-p_state='R';printf(qnamestatesuperndtimeruntime\n);printf(%s\t%c\t%d\t%d\t%d\t\n\n,psorted-p_name,psorted-p_state,psorted-p_priority,psorted-p_needTime,psorted-p_runTime);pt-p_state='W';psorted-p_runTime++;psorted-p_priority--;printf(****当前就绪状态的队列为：\n\n);//pt指向已经排序的队列pt=psorted-next;while(pt!=NULL){printf(qnamestatesuperndtimeruntime\n);printf(%s\t%c\t%d\t%d\t%d\t\n\n,pt-p_name,pt-p_state,pt-p_priority,pt-p_needTime,pt-p_runTime);pt=pt-next;}//pt指向已经排序的链表，判断链表是否有已用时间啊等于需要时间的pt=psorted;structPCB*ap;ap=NULL;//ap指向pt的前一个节点while(pt!=NULL){if(pt-p_needTime==pt-p_runTime){if(ap==NULL){pt=psorted-next;psorted=pt;}elseap-next=pt-next;}ap=pt;pt=pt-next;}if(psorted-next==NULL)break;getchar();}}structPCB*SortList(PCB*HL){structPCB*SL;SL=(structPCB*)malloc(sizeof(structPCB));SL=NULL;structPCB*r=HL;while(r!=NULL){structPCB*t=r-next;structPCB*cp=SL;structPCB*ap=NULL;while(cp!=NULL){if(r-p_prioritycp-p_priority)break;else{ap=cp;cp=cp-next;}}if(ap==NULL){r-next=SL;SL=r;}else{r-next=cp;ap-next=r;}r=t;}returnSL;}