处理机调度实验报告1

1、深 圳 大 学 实 验 报 告 课程名称： 操作系统 实验项目名称： 处理机调度 学院： 计算机与软件学院 专业： 软件工程 指导教师： 报告人： 学号： 班级： 实验时间： 2013年 5 月 7 日 实验报告提交时间： 2013年 5 月 22 日 教务处制一、实验目的与要求：实验目的: 模拟在单处理器多进程操作系统的CPU调度。帮助学生掌握多种CPU调度算法的知识原理和运作机制。本实验为模拟实验，不要求实现真正的进程创建与进程调度。主要实现各种调度算法。实验要求:1、 阅读理解例程，掌握例程的运作流程。运行例程，理解先来先服务算法的调度原理和运行结果。2、 参考先来先服务算法，尝试实现其

2、他四种调度算法：短作业优先、高响应比、时间片轮转、多级反馈队列。要求至少实现一种算法。a) 除了多级反馈队列，其他算法采用非抢占调度b) 短作业优先算法使用例题一数据或程序内置数据，要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间c) 高响应比算法使用例题二的数据，要求运行结果给出调度顺序、完成时间、周转时间、带权周转时间d) 时间片轮转算法可以使用程序内置数据，要求运行结果给出每个时间片是被哪个进程使用，每个进程完成时，要修改状态并输出提示。e) 多级反馈队列算法使用例题三的数据，要求运行结果给出正确的进程调度顺序和过程描述。二、方法、步骤：(说明程序相关的算法原理或知识内容，程序

3、设计的思路和方法，可以用流程图表述，程序主要数据结构的设计、主要函数之间的调用关系等)先来先服务算法：按到达时间先后，选择最先来的作业最先执行实现思想：对作业的到达时间按大小进行排序，然后按顺序执行短作业优先算法： 在后备队列中，选择服务时间最短的作业最先执行实现思想： 对作业按到达时间排序，接着对到达的作业，即后备队列中的作业按服务时间排序，取服务时间最小的作业最先执行高响应比算法：对作业的优先权（响应时间/要求服务时间）进行计算，对优先权最高的最先执行实现实现： 计算后备队列中作业的优先权，并排序，优先权最高的最先执行时间片轮转算法：将所有就绪进程按先来先服务排成队列，把CPU分配给队首进

4、程，进程只执行一个时间片，时间片用完后，将已使用时间片的进程送往就绪队列的末尾，分配处理机给就绪队列中下一进程实现思想： 将作业按到达时间排序，在后备队列中选择第一个作业，把CPU分配给它，执行一个时间片，时间片用完后，将作业送往后备队列的末尾，把CPU分配给下一个作业，直到所有作业完成多级反馈队列调度算法：设置多个就绪队列，各个队列优先级逐个降低，各个队列时间片逐个增加，优先级越高的队列执行时间片就越短，一般时间片按倍增规则，每个新进程首先进入第一个队列，遵循FCFS，在当前队列的时间片内，进程若能完成，退出，进程若未完成，降级到第二个队列，同样遵循FCFS依次类推，若在第二个队列的时间片内

5、仍未完成，再降级到第三个队列实现思想：设置多个就绪队列，各个队列优先级逐个降低，各个队列时间片逐个增加，优先级越高的队列执行时间片就越短，一般时间片按倍增规则， 例如，第二队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍，整合了时间片、 FCFS、优先级三种机制。三实验过程及内容：(对程序代码进行说明和分析，越详细越好，代码排版要整齐，可读性要高)#include "stdio.h"#include<stdlib.h>/#include<conio.h>#include<time.h>#incl

6、ude<math.h>/#define NULL 0#define getpch(type)(type*)malloc(sizeof(type)typedef struct pcb PCB;struct pcb/定义进程控制块PCBint id; /标示符char name10;/名称int time_start; /到达时间 int time_need; /服务时间int time_left; /剩余运行时间int time_used; /已使用时间char state; /进程状态;/*系统函数void _sleep(int n)clock_t goal;goal=(clock

7、_t)n*CLOCKS_PER_SEC+clock();while(goal>clock();char _keygo()char c;printf("按任意键继续n");c=getchar();return c;/*用户函数int time_unit=2;int num=5; /实际进程数量PCB pcbdata10=/例程内置数据1000,"A",0,4,4,0,'R',1001,"B",1,3,3,0,'R',1002,"C",2,5,5,0,'R',100

8、3,"D",3,2,2,0,'R',1004,"E",4,4,4,0,'R',;int num1=4;PCB pcbdata110=/例题一数据1000,"Job1",1,9,9,0,'R',1001,"Job2",1,16,16,0,'R',1002,"Job3",1,3,3,0,'R',1003,"Job4",1,11,11,0,'R',;int num2=4;PCB pcbd

9、ata210=/例题二数据1000,"P1",10,8,8,0,'R',1001,"P2",12,12,12,0,'R',1002,"P3",14,4,4,0,'R',1003,"P4",16,6,6,0,'R',;int num3=4;PCB pcbdata310=/例程三数据1000,"A",0,7,7,0,'R',1001,"B",5,4,4,0,'R',1002,"

10、;C",7,13,13,0,'R',1003,"D",12,9,9,0,'R',;int ready10; /就绪队列，存放进程在pcbdata中的位置int order10; /记录排序使用哪个数值作为排序对象void intput()int i;printf("进程总数为：");scanf("%d",&num);for(i=0;i<num;i+)pcbdatai.id=1000+i;printf("输入第%d个进程名：",i+1);scanf("

11、%s",&);printf("输入第%d个进程到达时间：",i+1);scanf("%d",&pcbdatai.time_start);printf("输入第%d个进程服务时间：",i+1);scanf("%d",&pcbdatai.time_need);pcbdatai.time_left=pcbdatai.time_need;printf("n");pcbdatai.time_used=0;pcbdatai.state='R

12、'/*调度函数void FCFS()int i,j,temp;double k;for(i=0;i<num;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;i<num;i+) /按到达时间排序for(j=i+1;j<num;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-先来先服务算法调度：非抢占，无时间片-n");temp=pcbdat

13、aready0.time_start;for(i=0;i<num;i+)printf("第%d个进程-%s,",i+1,);printf("本进程正在运行");_sleep(1);printf("运行完毕n");temp+=pcbdatareadyi.time_need;j=temp-pcbdatareadyi.time_start;k=(float)j/pcbdatareadyi.time_need;printf("完成时间-%d,周转时间-%d,带权周转时间-%.1fn"

14、;,temp,j,k);printf("-所有进程调度完毕-n");void SJF()int i,j,temp,l,temp_num;double k;int time=0;for(i=0;i<num1;i+)orderi=pcbdata1i.time_start;readyi=i;for(i=0;i<num1;i+) /按到达时间排序for(j=i+1;j<num1;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=

15、temp;printf("-短作业算法调度：非抢占，无时间片-n");int t_ready10;/就绪队列，存放进程在pcbdata中的位置int t_order10; /记录排序使用哪个数值作为排序对象for(i=0;i<num1;i+)t_orderi=pcbdata1readyi.time_need;/服务时间作为排序对象t_readyi=readyi;time=order0;for(l=0;l<num1;l+)/判断到达的进程数，用temp_num存放for(i=0;i<num&&pcbdata1readyi.time_start

16、<=time;i+)temp_num=i+1;/把到达的进程按服务时间大小进行排序for(i=0;i<temp_num;i+)for(j=i+1;j<temp_num;j+)if(t_orderi>t_orderj&&t_orderj!=0|t_orderi=0)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_readyi=t_readyj;t_readyj=temp;printf("第%d个进程-%s,",l+1,pcbdata1t_)

17、;printf("正在运行");_sleep(1);printf("运行完毕n");time+=pcbdata1t_ready0.time_need;j=time-pcbdata1t_ready0.time_start;k=(float)j/pcbdata1t_ready0.time_need;t_order0=0;printf("完成时间-%d,周转时间-%d,带权周转时间-%.1fn",time,j,k);printf("-所有进程调度完毕-n");void HRF()int i,j,temp,l,temp_n

18、um;double k;int time=0;for(i=0;i<num2;i+)orderi=pcbdata2i.time_start;readyi=i;for(i=0;i<num2;i+) /按到达时间排序for(j=i+1;j<num2;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-高响应比算法调度：非抢占，无时间片-n");int t_ready10;int t_order10;f

19、or(i=0;i<num2;i+)t_orderi=1;t_readyi=readyi;time=order0;for(l=0;l<num2;l+)/判断到达进程数for(i=0;i<num&&pcbdata2readyi.time_start<=time;i+)temp_num=i+1;for(i=0;i<temp_num;i+) /计算已到达进程的优先权if(t_orderi)t_orderi=(time-pcbdata2t_readyi.time_start+ pcbdata2t_readyi.time_need)/pcbdata2t_rea

20、dyi.time_need;for(i=0;i<temp_num;i+) /按优先权排序for(j=i+1;j<temp_num;j+)if(t_orderi<t_orderj)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_readyi=t_readyj;t_readyj=temp;printf("第%d个进程-%s,",l+1,pcbdata2t_);printf("正在运行");_sleep(1);printf("运行完毕n

21、");time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_ready0.time_need;t_order0=0;printf("完成时间-%d,周转时间-%d,带权周转时间-%.1fn",time,j,k);printf("-所有进程调度完毕-n");void Timeslice()int i,j,temp,l,temp_num;double k;int time=0;int done=0;for(i=0;i<n

22、um;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;i<num;i+) /按到达时间排序for(j=i+1;j<num;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-时间片轮转算法调度：非抢占，时间片大小为2-n");int t_ready10;for(i=0;i<num;i+)t_readyi=readyi;time=order0;for(

23、l=0;done<num;l+)/判断到达的进程数for(i=0;i<num&&pcbdatareadyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)/将已使用时间片的进程，即第一个移到队列末尾for(i=1;i<temp_num;i+)temp=t_readyi;t_readyi=t_readyi-1;t_readyi-1=temp;if(pcbdatat_ready0.state!='F')printf("第%d个时间片被进程%s使用,",l+1,pcbdat

24、at_);printf("正在运行n ");_sleep(1);printf("时间片使用完，所需时间%d,",pcbdatat_ready0.time_left);time+=2;pcbdatat_ready0.time_used+=2;pcbdatat_ready0.time_left-=2;printf("使用时间%d,还需时间%d,",2,pcbdatat_ready0.time_left);/判断进程是否结束if(pcbdatat_ready0.time_left<=0)printf("

25、进程%s结束n",pcbdatat_);done+;pcbdatat_ready0.state='F'elseprintf("进程%s就绪n",pcbdatat_);printf("-所有进程调度完毕-n");void MRLA()int i,j,temp,l,temp_num,temp_num2;double k;int time=0; /系统时间int done=0; /已完成的进程int t_ready10;int queue10; /进程对应的队列int qtime10; /进

26、程对应的时间片for(i=0;i<num3;i+)orderi=pcbdata3i.time_start;readyi=i;queuei=1;qtimei=0;for(i=0;i<num3;i+) /按到达时间排序for(j=i+1;j<num3;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-多级反馈算法调度：抢占式，时间片大小为2-n");for(i=0;i<num3;i+)t_r

27、eadyi=readyi;time=order0;for(l=0;done<num3;l+)/判断到达的进程数for(i=0;i<num3&&pcbdata3readyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)for(i=0;i<temp_num;i+) /按队列优先级排序for(j=1;j<temp_num-i;j+) if(pcbdata3t_readyj-1.state='F'|(queuej-1>queuej&&pcbdata3t_readyj

28、.state!='F')temp=queuej-1;queuej-1=queuej;queuej=temp;temp=t_readyj-1;t_readyj-1=t_readyj;t_readyj=temp;temp=qtimej-1;qtimej-1=qtimej;qtimej=temp;if(pcbdata3t_ready0.state!='F')printf("队列%d中的进程%s占用CPU,",queue0, pcbdata3t_);printf("正在运行n ");_sleep(1);if(

29、!qtime0) /判断是否有未用完的时间片qtime0=pow(2,queue0);elseprintf("继续使用时间片，");for(i=1;i<qtime0;i+)time+;for(j=0;j<num3&&pcbdata3readyj.time_start<=time;j+)temp_num2=j+1;/判断是否有进程进入比本进程更高优先级的队列if(temp_num!=temp_num2&&queue0>queuetemp_num2-1&& pcbdata3t_ready0.time_lef

30、t-i>0)qtime0-=i;break;if(temp_num!=temp_num2&&queue0>queuetemp_num2-1&&pcbdata3t_ready0.time_left-i>0)printf("发生抢占，使用时间片%d，剩余时间片%d，返回队列尾部n",i,qtime0);elseprintf("时间片使用完，所需时间%d,", pcbdata3t_ready0.time_left);time+;pcbdata3t_ready0.time_used+=pow(2,queue0);

31、pcbdata3t_ready0.time_left-=pow(2,queue0);if(pcbdata3t_ready0.time_left<=0)printf("使用时间%d,还需时间%d,进程%s结束n",qtime0, pcbdata3t_ready0.time_left,pcbdata3t_);done+;pcbdata3t_ready0.state='F'elseprintf("使用时间%d,还需时间%d,进程%s进入队列%d就绪n",qtime0,pcbdata3t_ready0.time_lef

32、t,pcbdata3t_,+queue0);qtime0=0;for(j=1;j<temp_num2;j+) /将执行的程序返回队尾排队temp=queuej;queuej=queuej-1;queuej-1=temp;temp=qtimej;qtimej=qtimej-1;qtimej-1=temp;temp=t_readyj;t_readyj=t_readyj-1;t_readyj-1=temp;printf("-所有进程调度完毕-n");int main()int i=0,sch=99;while(sch!=0)printf("n

33、请选择其中一种调度算法：n");printf("(1)先来先服务FCFSn");printf("(2)短作业优先SJFn");printf("(3)高响应比HRFn");printf("(4)时间片轮转Timeslicen");printf("(5)多级反馈队列MRLAn");printf("(0)退出n");printf("请输入上述一个数字：");scanf("%d",&sch);switch(sch)case 1

34、:FCFS();break;case 2:SJF();break;case 3:HRF();break;case 4:Timeslice();break;case 5:MRLA();break;case 0:printf("退出程序n");break;_keygo();return 0;void dis_pcb(PCB * pr)printf("%s的PCB:n",pr->name);printf("标识符-%d,状态-%c,到达时间-%dn",pr->id,pr->state,pr->time_start);printf("服务时间-%d,剩余运行时间-%d,已用时间-%dn",pr->time_need,pr->time_left,pr->time_used);printf("-n&quo