操作系统实验_先来先服务地调度算法和短作业优先

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;/

4、带权周转时间;文档大全实用标准文案fcfs a100; /结构体数组函数说明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);/ 先来

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

6、进程运行时间进行小到大排序，标志位为 0当前进程为第一个进程当前时间 >当前进程的到否达时间当前进程标志位为 0否是当前进程开始时间=当前时间结束时间 =当前时间 + 运行书剑是否为最后一个进程否是当前进程标志为1所有标志位都为 1是结束当前进程 = 下一个当前时间 = 当前时进程间 +1否文档大全实用标准文案程序#include <stdio.h>struct fcfs/ 定义进程的结构体char name10;/ 进程名float arrivetime; /到达时间float servicetime; /服务时间float starttime;/开始时间float fin

7、ishtime;/完成时间float zztime;/周转时间float dqzztime;/带权周转时间;floatarrivetime=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; i<=N-1; i+)printf("输入第

8、 %d 进程的名称、到达时间、服务时间:n",i+1);scanf("%s%f%f",&,&pi.arrivetime,&pi.servicetime);/ 输出函数void FPrint(fcfs *p,int N)/输出函数int k;printf("n执行顺序 :n");printf("%s",);for(k=1; k<N; k+)printf("-%s",);printf("n进程名 t 到达时间 t 服务时间 t

9、开始时间 t 结束时间t 周转时间 t 带权周转时间 nn");文档大全实用标准文案for(k=0; k<=N-1; k+)printf("%st%-.2ftt%-.2ftt%-.2ftt%-.2ftt%-.2ftt%-.2fttnn",,pk.arrivetime,pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime);void Fsort(fcfs *p,int N)/ 按到达时间排序，先到达排在前面for(int i=0; i<=N-1; i+)for(int

10、 j=0; j<=i; j+)if(pi.arrivetime<pj.arrivetime)/进行排序，如果先到达就排在前面fcfs temp;temp=pi;pi=pj;pj=temp; / 运行结果void F_method(fcfs *p, int N)文档大全实用标准文案int k;for(k=0; k<=N-1; k+)if(k=0)pk.starttime=pk.arrivetime;/如果是第一个进程，开始时间等于到达时间pk.finishtime=pk.arrivetime+pk.servicetime;/结束时间等于到达时间加上服务时间elsepk.star

11、ttime=pk-1.finishtime;/ 开始时间 = 上一个一个进程的完成时间pk.finishtime=pk.starttime+pk.servicetime;/结束时间 = 开始时间加上 + 现在进程的服务时间for(k=0; k<=N-1; k+)/ 求每个进程的信息文档大全实用标准文案pk.zztime=pk.finishtime-pk.arrivetime;/ 周转时间 = 完成时间 - 到达时间pk.dqzztime=pk.zztime/pk.servicetime;/ 带权周转时间 = 周转时间 / 服务时间void F_method2(fcfs *p,int N)

12、/ 短作业优先核心程序int num;int arrive=65535;/ 寻找最早到达的进程int min_serive=65535;/ 寻找最小服务时间进程int i;fcfs b100;/ 新建一个，进行排序int state100;/设置 100 个标志位for( i=0; i<N; i+)statei=0;for(i=0; i<N; i+)文档大全实用标准文案if(pi.arrivetime<arrive) arrive=pi.arrivetime;num=i;b0=pnum;statenum=1;b0.finishtime=b0.arrivetime+b0.ser

13、vicetime;intj=0;for(int k=1; k<N; k+) min_serive=65535; for(i=0; i<N; i+)if(statei=1|pi.arrivetime>bj.finishtime)/如果遇到已排序或者未到达的进程跳过continue;elseif(pi.servicetime<min_serive)min_serive=pi.servicetime;num=i;statenum=1;文档大全实用标准文案/ 找到合适的进程并赋值到 B b+j=pnum; bj.starttime=bj-1.finishtime; bj.fin

14、ishtime=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; j<N; j+)pj=bj;/ 先来先服务void FCFS(fcfs *p,int N)Fsort(p,N);/对每个进程排序F_method(p,N);FPrint(p,N);文档大全实用

15、标准文案void SJF(fcfs *p,int N)F_method2(p,N);FPrint(p,N);int main()/ 主函数int N;printf("输入进程数 :");scanf("%d",&N);Finput(a,N);printf("先来先服务 n");FCFS(a,N);printf("nnn");printf("短作业优先 n");SJF(a,N);return 0;文档大全实用标准文案【小结或讨论】1.能实现的功能输入进程个数Num ，每个进程到达时间Arri

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