优先调度算法、先来先服务调度算法.doc

操作系统课程设计(一) 实验题目处理机调度短作业优先调度算法、先来先服务调度算法(二) 试验目的 加深作业概念的理解，深入了解多道程序设计系统中如何组织作业、管理作业和调度作业，加深对作业调度算法的理解。(三)实验环境普通计算机一台，操作系统是WINDOWS，编译环境VC+6.0（四）算法思想及数据结构 1 调度算法作业调度算法的关键是在已有的作业后备队列上按照一定的规则选择一个作业，如何在已有的数据结构上进行操作的问题。短作业优先调度算法（SJF）短作业优先算法总是提交要求运行时间最短的作业，让其进入主存储器以便占用处理器运行先来先服务算法（FCFS）每次提交作业总是选择后备队列的对首作业，实验中用head指向对首JCB。有作业进入系统，则挂入后备队列对尾。对首JCB进入内存后执行，在实验中由于没有真正的内存，我们用程序模拟作业执行，需修改该作业的JCB的相关信息即可，如状态为state置为“R”,开始执行时间tb赋值为当前时间time。（p-state=R;p-tb=time;）该作业执行完成后，需修改其状态位state为“F”，并计算该作业的相关信息：计算周转时间： p-ti=(float)(p-tc-p-ts); 计算带权周转时间：p-wi=(float)(p-ti/p-ntime); 计算平均周转时间 ：eti+=p-ti; 计算带权平均周转时间：ewi+=p-wi; 并输出当前系统中各作业的信息 print(p,m); 提交作业时，从后备队列对首开始向对尾扫描，查找状态为“W”且要求系统运行时间最短的作业，选中将其调入内存。同FCFS算法，在实验中由于没有真正的内存，我们用程序模拟作业执行，需修改该作业的JCB的相关信息。该作业执行完成后，需修改其状态位state为“F”，计算该作业的相关信息和输出当前系统中各作业的信息。2 主要数据结构每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下： typedef struct jcb char name10; /* 作业名 */ char state; /* 作业状态 */ int ts; /* 提交时间 */ float super; /* 优先权 */ int tb; /* 开始运行时间 */ int tc; /* 完成时间 */ float ti; /* 周转时间 */ float wi; /* 带权周转时间 */ int ntime; /* 作业所需运行时间 */ char resource10; /* 所需资源 */ struct jcb *next; /* 结构体指针 */ JCB;JCB *p,*tail=NULL,*head=NULL; 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。本设计采用链表的形式存放各后备队列当中的作业控制块，各个等待的作业按照提交时刻的先后次序排队。当一个作业进入系统时，就为其动态建立一作业控制块（JCB），挂入后备队列尾部。当作业调度时，从后备队列中按某种调度算法选择一作业，让其进入主存以便占用CPU执行。每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。(五) 课程设计内容 每个作业由一个作业控制块JCB表示，JCB包含如下信息：作业名，到达时间，开始运行时间，所需的服务时间，完成时间，周转时间，带权周转时间，作业状态，链指针等。作业的状态可以是等待w，运行R,完成F三种状态之一，每个作业的最初状态总是等待w.1 短作业优先调度算法中的作业控制块的JCBstruct pcbsfString name;int ntime; / 运行所需时间 int rtime; /已运行时间 int btime; /开始时间 int ftime; /完成时间 int totime; /周转时间 struct pcbsf *link;pcbsf *psf; /在短作业优先算法中记录进程 pcbsf *readysf1; /在此算法中用了两个队列此为第一队列的首指针 pcbsf *readysf2;pcbsf *rearsf1; /第一队列尾指针 pcbsf *rearsf2;int countsf=0; /在短作业优先中记录输入的进程数 typedef struct pcb PCB;2 先来先服务调度算法中的作业控制块的JCBstruct pcbfcfsString name;int rtime; /到达时间 int ntime; /服务时间 int btime; /开始时间 int ftime; /完成时间 int totime; /周转时间 FCFS50;pcbfcfs SF10; /用于记录短作业优先算法中的第一个进程 int count=0; /记录输入的进程数 调度算法的流程图：函数的调用关系：调度算法所包含的其它模块：输入模块、排队模块、检查作业调度情况的模块、作业的运行模块，主函数模块等。 以输入模块为例：输入模块void _fastcall TForm1:Button1Click(TObject *Sender)p=getpcb(pcb);p-name1=Edit1-Text;p-super1=StrToInt(Edit2-Text);p-ntime1=StrToInt(Edit3-Text);p-stime1=0;p-rtime1=0;p-state1=W;p-link=NULL;Memo1-Lines-Add(p-name1+t+IntToStr(p-super1)+t+IntToStr(p-ntime1);Edit1-Clear();Edit2-Clear();Edit3-Clear();sort();countsup+;Button2-Enabled=true;此模块用来输入要查询作业的作业名、所需时间。 在模拟作业调度的程序设计中，要完成短作业优先调度、先来先服务调度。首先确定作业控制块的内容，作业控制块的组成方式；然后完成作业调度；最后编写主函数对所作的工作进行测试。 以下为短作业优先调度算法和先来先服务算法的代码部分/*短作业优先调度算法*/void sjf(int m) JCB *min; int i,iden; for(i=0;istate=W&p-tsntimentime) min=p; p=p-next; while(p!=NULL) ; if(iden) i-;coutntime=time no JCB submib.wait.100)coutnruntime is too long.errorendl;cin.get(); else running(min,m); /*先来先服务调度算法*/void fcfs(int m) int i,iden; coutnthe jcb is runing.endl; for(i=0;istate=W&p-tsnext; while(p!=NULL&iden) ; if(iden) i-;coutntime=time no JCB submib.wait.100)coutnruntime is too long.errorendl;cin.get(); else running(p,m); void runjcb(int m) coutnstart running jcb.endl; switch(m) case 1:fcfs(m);break; case 2:sjf(m);break; case 3:hrn(m);break; default:coutnrunjcb error.n;return; 调试分析：执行Project.exe ，屏幕出现作业调度模拟系统，可以方便的执行作业调度，并快速的查看作业执行所需要的时、周转时间、带权周转时间等详细信息1 先来先服务优先调度2 短作业优先调度由图可清晰看出两种调度算发的差别：1. 先来先服务算法比较有利于长作业，而不利于短作业。 2. 短作业优先调度算法对比先来先服务，不论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业。该算法对长作业不利，而且未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。 （六）课程设计总结： 先来先服务算法比较容易实现，但效率低。它没有考虑各个作业运行特性和资源要求的差异。这种算法对短作业不利，短作业执行时间很短，等待较长时间，则带权周转时间很高。短作业优先调度算法也易于实现，且效率比较高。但它只照顾短作业的利益，而不考虑长作业的利益。有可能使长作业长时间等待而不能运行。比较上述算法的运行结果可以看出，短作业优先调度算法的调度性能好些，作业的平均周转时间和平均带权周转时间都比先来先服务算法小一些。如果策略是使周转时间最小，则应采用短作业优先调度算法。这次的课程设计还让我学会了如何把自己不明白的具体的表述出来，如何更好的和老师沟通。使我能够进一步掌握用程序设计语言解决实际问题的方法，在操作当中把所学到的用于实际的编程里去，能够提高分析问题、查阅资料、吸收新知识的能力，在分析解决问题时比以前有了很大的进步，一些常用的知识和一些常规的错误都能够解决。源代码：#include#includeint Num5;float TjTime5;float ZxTime5;float KsTime5;float WcTime5;float ZzTime5;float DqzzTime5;float PjzzTime,PjdqzzTime;void Build()Num1=1; Num2=2; Num3=3; Num4=4;TjTime1=8.00; TjTime2=8.50; TjTime3=9.00; TjTime4=9.50;ZxTime1=2.00; ZxTime2=0.50; ZxTime3=0.10; ZxTime4=0.20;void display() int i;printf(n);printf(作业 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间n); for(i=1;i5;i+) printf(%d% 4.2f% 4.2f% 5.2f% 5.2f% 5.2f% 5.2fn,Numi,TjTimei,ZxTimei,KsTimei,WcTimei,ZzTimei,DqzzTimei); printf(n); printf(平均周转时间 t=%5.3fn平均带权周转时间 w=%5.3fn,PjzzTime,PjdqzzTime); printf(n); printf(n); void FCFS( )/*先来先服务调度算法*/ int j; WcTime0=0; for(j=1;jWcTimej-1) KsTimej=TjTimej; else KsTimej=WcTimej-1; WcTimej=KsTimej+ZxTimej; ZzTimej=WcTimej-TjTimej; DqzzTimej=ZzTimej/ZxTimej; printf(先来先服务调度算法:n); PjzzTime=(ZzTime1+ZzTime2+ZzTime3+ZzTime4)/4; PjdqzzTime=(DqzzTime1+DqzzTime2+DqzzTime3+DqzzTime4)/4;display( ); void ShortFirst( )/*短作业优先调度算法*/ int i,j,k,p=0,q=3; int flat5=0,0,0,0,0; float wctime; KsTime1=TjTime1; WcTime1=KsTime1+ZxTime1; ZzTime1=WcTime1-TjTime1; DqzzTime1=ZzTime1/ZxTime1; wctime=WcTime1; flat1=1; for(k=1;k4;k+) for(i=2;i5;i+) for(j=2;j5;j+) if(ZxTimei=ZxTimej&flati!=1) p+; if(p=q) KsTimei=wctime; WcTimei=KsTimei