操作系统实验-先来先服务的调度算法和短作业优先.docx

1、学号 P71514032 专业 计算机科学与技术 姓名实验日期 2017.10.27 教师签字 成绩实验报告【实验名称】 进程调度算法 FCFS、FJF【实验目的】在多道程序或多任务系统中，系统同时处于就绪态的进程有若干个。也就是说能运行的进程数远远大于处理机个数，为了使系统中的各进程能有条不紊的运行，必须选择某种调度策略，以选择一进程占用处理机，所以，要求使用某一种编程语言设计实现模拟单处理机调度的算法，以巩固和加深处理机调度的概念。本实验要求采用先来先服务的调度算法和短作业优先的调度算法编写和调试一个简单的进程调度程序。通过本实验可以加深理解进程调度、进程队列的概念。【实验原理】FCFS

2、调度算法先来先服务(FCFS)调度算法是一种最简单的调度算法。在进程调度中采用 FCFS 算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。SJF 调度算法短作业(进程)优先调度算法 SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。【实验内容】问题分析输入：进程的名称、到达时间、服务时间输出：进程的完成时间、周转时间、带权周转时间其中对于任意进程有：周转时间=

3、完成时间-到达时间带权周转时间=周转时间/服务时间因此，两个算法的关键是求完成时间数据结构及函数说明使用的数据结构是数组，进程的名称、到达时间、服务时间、进程的完成时间、周转时间、带权周转时间分别对应于一个数组，这些数组长度相等.struct fcfs/定义进程的结构体char name10; /进程名float arrivetime; /到达时间float servicetime; /服务时间float starttime;/开始时间float finishtime;/完成时间float zztime;/周转时间float dqzztime;/带权周转时间;fcfs a100; /结构体数组

4、函数说明void Finput(fcfs *p,int N) ; /输入函数，初始化void Fsort(fcfs *p,int N) ; /按到达时间排序，先到达排在前面void Fsort2(fcfs *p,int N) ; /按进程大小排序，先到达排在前面void F_method(fcfs *p, int N) /先来先服务算法 void F_method2(fcfs *p,int N) /短作业优先程序 void SJF(fcfs *p,int N)； / 短作业优先void FCFS(fcfs *p,int N); /先来先服务void SJF(fcfs *p,int N) /短作

5、业优先void FPrint(fcfs *p,int N) /输出函数求完成时间算法1) FCFS 算法流程图开始初始化结构体数组 、 初始化进程队列 ， 当前时间为 0对进程数组按照到达时间小到大进行排序当前时间是否小于当前进程到达时间当前时间 = 当前时间 + 1当前进程的开始时间等于当前时间当前进程的结束时间等于开始时间 +运行时间进程数组是否扫描完毕当前进程 = 下一个进程结束当前时间 = 当前进程结束时间 + 1是否是否2) SJF 算法流程图开始初始化结构体数组 ， 输入赋值 ， 当前时间为 0对进程数组按照进程运行时间进行小到大排序 ， 标志位为 0当前时间 当前进程的到达时间当

6、前进程为第一个进程当前进程标志位为 0是否为最后一个进程当前进程 = 下一个进程当前时间 = 当前时间 + 1当前进程开始时间= 当前时间结束时间 = 当前时间 + 运行书剑当前进程标志为 1所有标志位都为 1结束是是否否是否否 程序#include struct fcfs/定义进程的结构体char name10; /进程名float arrivetime; /到达时间float servicetime; /服务时间float starttime;/开始时间float finishtime;/完成时间float zztime;/周转时间float dqzztime;/带权周转时间;float

7、arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;fcfs a100;/定义先来先服务算法进程的最大数量void Finput(fcfs *p,int N) /输入函数int i;printf(“输入进程的名称、到达时间、服务时间:（例如: x 0 100）n“);for(i=0; ibj.finishtime)/如果遇到已排序或者未到达的进程跳过continue;else if(pi.servicetimemin_serive)min_serive=pi.servicetime;num=i;stat

8、enum=1; /找到合适的进程并赋值到 Bb+j=pnum;bj.starttime=bj-1.finishtime;bj.finishtime=bj-1.finishtime+bj.servicetime;for(j=0; j=N-1; j+) /求每个进程的信息bj.zztime= bj.finishtime- bj.arrivetime; /周转时间=完成时间-到达时间bj.dqzztime= bj.zztime/ bj.servicetime; /带权周转时间=周转时间/服务时间for(j=0; jN; j+)pj=bj;/先来先服务void FCFS(fcfs *p,int N)F

9、sort(p,N);/对每个进程排序F_method(p,N);FPrint(p,N);void SJF(fcfs *p,int N)F_method2(p,N); FPrint(p,N);int main() /主函数int N;printf(“输入进程数:“);scanf(“%d“,Finput(a,N);printf(“先来先服务n“);FCFS(a,N);printf(“nnn“);printf(“短作业优先n“);SJF(a,N);return 0;【小结或讨论】1.能实现的功能输入进程个数 Num，每个进程到达时间 ArrivalTimei，服务时间 ServiceTimei。采用

10、先来先服务 FCFS 或者短作业优先 SJF 进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计 Num 个进程的平均周转时间和平均带权周转时间。2、FCFS 算法相对于 SJF 算法来说，比较简单，在 FCFS 算法中，主要用到的是队列，按照作业的到达时间来进行排序排序算法。3、SJF 算法中就需要考虑到很多的因素，因为 0 时刻到达的作业肯定第一个执行，然后再考虑剩余的作业的服务时间以决定哪一个作业先执行，但是这是在确保所有剩余的作业都处于就绪状态的情况下。如若不然，还要考虑每一个作业执行完后，有哪些作业进入了排队状态。4、SJF 算法中还要考虑到如若同一时刻进

11、入了多个作业，还要将这若干个作业按照服务时间进行排序，再考虑执行情况。5、无论是 FCFS 还是 SJF 算法，关键都是求完成时间。FCFS 算法执行进程的顺序是由到达时间的先后决定的，SJF 算法的顺序是由服务时间决定的。6、SJF 求完成时间时，应当注意如下情况：A 进程完成完成后，依据服务时间，轮到 B 执行,而 A 的完成时间B 的到达之间，也就是说 A 完成时，B 尚未到达，这种情况下，B 的完成时间=B 的到达时间+B 的服务时间。7、通过本次实验，我对于作业调度的机制，有了进一步的认识，对于相同的作业，不同的调度顺序，会使周转时间以及赋权周转时间产生变化。8、先到先服务算法虽然算法实现较为简便，但是效率上存在一定的问题。短作业优先算法可以大大提高效率方面的问题，但是实现起来较为复杂。