处理机调度实验报告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/#include#include#include/#define NULL 0#define getpch(type)(type*)malloc(sizeo

6、f(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_t)n*CLOCKS_PER_SEC+clock();while(goalclock();char _keygo()char c;print

7、f(按任意键继续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,1003,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

8、num2=4;PCB pcbdata210=/例题二数据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,C,7,13,13,0,R,1003,D,12,9,9,0,R,;int ready10; /就绪队列，存放进程在pcbdata中的位置int order10; /记录排序使用哪个数值作为排序对象void intput()int i;print

9、f(进程总数为：);scanf(%d,&num);for(i=0;inum;i+)pcbdatai.id=1000+i;printf(输入第%d个进程名：,i+1);scanf(%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.s

10、tate=R;/*调度函数void FCFS()int i,j,temp;double k;for(i=0;inum;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;inum;i+) /按到达时间排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-先来先服务算法调度：非抢占，无时间片-n);temp=pcbdataready0.time_start;for(i=0;inum;i+)printf(

11、第%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,temp,j,k);printf(-所有进程调度完毕-n);void SJF()int i,j,temp,l,temp_num;double k;int time=0;for(i=0;i

12、num1;i+)orderi=pcbdata1i.time_start;readyi=i;for(i=0;inum1;i+) /按到达时间排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-短作业算法调度：非抢占，无时间片-n);int t_ready10;/就绪队列，存放进程在pcbdata中的位置int t_order10; /记录排序使用哪个数值作为排序对象for(i=0;inum1;i+)t_orderi=pcbdata1ready

13、i.time_need;/服务时间作为排序对象t_readyi=readyi;time=order0;for(l=0;lnum1;l+)/判断到达的进程数，用temp_num存放for(i=0;inum&pcbdata1readyi.time_start=time;i+)temp_num=i+1;/把到达的进程按服务时间大小进行排序for(i=0;itemp_num;i+)for(j=i+1;jt_orderj&t_orderj!=0|t_orderi=0)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_readyi=

14、t_readyj;t_readyj=temp;printf(第%d个进程-%s,l+1,pcbdata1t_);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

15、 i,j,temp,l,temp_num;double k;int time=0;for(i=0;inum2;i+)orderi=pcbdata2i.time_start;readyi=i;for(i=0;inum2;i+) /按到达时间排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-高响应比算法调度：非抢占，无时间片-n);int t_ready10;int t_order10;for(i=0;inum2;i+)t_orderi=1;

16、t_readyi=readyi;time=order0;for(l=0;lnum2;l+)/判断到达进程数for(i=0;inum&pcbdata2readyi.time_start=time;i+)temp_num=i+1;for(i=0;itemp_num;i+) /计算已到达进程的优先权if(t_orderi)t_orderi=(time-pcbdata2t_readyi.time_start+ pcbdata2t_readyi.time_need)/pcbdata2t_readyi.time_need;for(i=0;itemp_num;i+) /按优先权排序for(j=i+1;jte

17、mp_num;j+)if(t_orderit_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);time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_ready0.t

18、ime_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;inum;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;inum;i+) /按到达时间排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=ready

19、i;readyi=readyj;readyj=temp;printf(-时间片轮转算法调度：非抢占，时间片大小为2-n);int t_ready10;for(i=0;inum;i+)t_readyi=readyi;time=order0;for(l=0;donenum;l+)/判断到达的进程数for(i=0;inum&pcbdatareadyi.time_start=time;i+)temp_num=i+1;if(time!=order0)/将已使用时间片的进程，即第一个移到队列末尾for(i=1;itemp_num;i+)temp=t_readyi;t_readyi=t_readyi-1;t

20、_readyi-1=temp;if(pcbdatat_ready0.state!=F)printf(第%d个时间片被进程%s使用,l+1,pcbdatat_);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

21、_ready0.time_left=0)printf(进程%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; /进程对应的时间片for(i

22、=0;inum3;i+)orderi=pcbdata3i.time_start;readyi=i;queuei=1;qtimei=0;for(i=0;inum3;i+) /按到达时间排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-多级反馈算法调度：抢占式，时间片大小为2-n);for(i=0;inum3;i+)t_readyi=readyi;time=order0;for(l=0;donenum3;l+)/判断到达的进程数for(i=0

23、;inum3&pcbdata3readyi.time_start=time;i+)temp_num=i+1;if(time!=order0)for(i=0;itemp_num;i+) /按队列优先级排序for(j=1;jqueuej&pcbdata3t_readyj.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.sta

24、te!=F)printf(队列%d中的进程%s占用CPU,queue0, pcbdata3t_);printf(正在运行n );_sleep(1);if(!qtime0) /判断是否有未用完的时间片qtime0=pow(2,queue0);elseprintf(继续使用时间片，);for(i=1;iqtime0;i+)time+;for(j=0;jnum3&pcbdata3readyj.time_startqueuetemp_num2-1& pcbdata3t_ready0.time_left-i0)qtime0-=i;break;if(temp_num!=temp_nu

25、m2&queue0queuetemp_num2-1&pcbdata3t_ready0.time_left-i0)printf(发生抢占，使用时间片%d，剩余时间片%d，返回队列尾部n,i,qtime0);elseprintf(时间片使用完，所需时间%d, pcbdata3t_ready0.time_left);time+;pcbdata3t_ready0.time_used+=pow(2,queue0);pcbdata3t_ready0.time_left-=pow(2,queue0);if(pcbdata3t_ready0.time_left=0)printf(使用时间%d,还需时间%d,进

26、程%s结束n,qtime0, pcbdata3t_ready0.time_left,pcbdata3t_);done+;pcbdata3t_ready0.state=F;elseprintf(使用时间%d,还需时间%d,进程%s进入队列%d就绪n,qtime0,pcbdata3t_ready0.time_left,pcbdata3t_,+queue0);qtime0=0;for(j=1;jname);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);void dis_pcb_all()int i;printf(*当前所有进程状态*n);for(i=0;inum;i+)dis_pcb(&pcbdatai);void dis_ready()int i;printf(当前就绪队列为：);for(i=0;inum-1;i+)printf(%s-,);printf(%sn,pcbdataor