操作系统试验FCFS和短作业优先SJF调度算法模拟

1、题 目 先来先服务FCFS和短作业优先SJF进程调度算法姓 名：学 号：专 业：学 院：指导教师：林若宁二零一八年十一月一、实验目的模拟单处理器系统的进程调度，分别采用短作业优先和先来先服务的进程调度算法作为 进程设计算法，以加深对进程的概念及进程调度算法的理解.二、实骐内容.短作业优先调度算法原理短作业优先调度算法，是指对短作业或断进程优先调度的算法。它们可以分别可以用于 作业调度和进程调度。短作业优先调度算法，是从后备队列中选择一个或若干个运行时间最 短的作业，将它们调入内存运行。短进程优先调度算法，是从就绪队列中选出一个估计运行 时间最短的进程，将处理机分配给它使它立即执行并一直执行到完

2、成，或发生某事件而被阻 塞放弃处理机时再重新调度。.先来先服务调度算法原理先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可 用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或 多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪 队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队 列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后 才放弃处理机。三、程序设计.概要设计程序包括主函数、FCFS算法函数、SJF算法函数、输出函数；主函数流程：输入

3、文件 中的数据一显示各进程数据一选择算法一调用相应算法的函数一输出结果.算法流程SJF算法流程图:核H3Bl从小列夫X J旭SJF流程图:.详细设计(1)定义一个结构体 typedef stmct PCBcharjob.id10;作业IDfloatAiT_tune;到达时刻floatFun.time;估计运行时间floatWhit_tiine;等待时间floatStaivtiine;开始时刻floatFin_time;完成时刻floatTiu_time;周转时间floatWTur_time;带权周转时间mtOrder;优先标记Hst;(2)先来先服务算法函数void fcfs(list *p,

4、int count) 先来先服务算法 (list temp;临时结构体变量inti;mt j;foi(i= l;i count;i+)按到达时刻直接插入排序(temp = pi;J = 1-1;while(temp.AiT_tiine = 0)-j;pj+l = temp:)for(i = 0;i count;i+)循环计算各个作业的时间值(if(i = 0)pi.Start_tiine = pi.Air_tmie; elsepi.Start_tune = pi-l.Fin_tmie;开始时刻一前一个作业的完成时刻pi.Wait_time = pi.Start_time - pi.An_tim

5、e;等待=开始-到达pi.Fm_time = pi.Stait_time + pi.Fun_tiine;完成一开始+运行pi.Tui_tiine = pi.Fm_time - pi.Air_time;周 转=完成-至 U 达pi.WTu 口 ime = pi.Tur.time / pi.FuiUime;带权周转=周转/运行return:)（3）最短作业优先函数void sjf（list count）最短作业优先算法（sjf）（list item;结构体变量mt i = 0;mtj = 0;mtk = 0;最短运行时间作业的下标mt flag = 0; 优先级设置float niin = 0;最

6、短运行时间float temp;开始的时刻temp = p0. Anytime;先求出最先到达作业的时刻fbi(i = 0;i pi .Anytime)temp = pi.AiT_time; k = i；)保存最先到达的作业的时刻最先到达的作业的下标，默认为p0fbi(i = 0;i count;i+)pk.Order = -H-flag;设置优先级为1,最高优先级=temp - pk.An_time;计算各个时间pk.WaiCtime pk.Fm_time pk.Tur_tmie pk.WTui_timepk.Start_tune = tenip:=temp + pk.Fun_time;=p

7、k.Fm_time - pk.AiT_tiine;=pk.Tui_tiine / pk.Fun_tune;mm= 100;temp = pk.Fiii_time;后一个作业的开始时刻是前一个作业的完成时刻fbr(j = 0J countJ+)if(pj.Order != 0 | temp - pj.ArOime pj.Fun_time) (niiii = pj.Fun_tmie;k = j;求出满足条件最短运行时间的作业的下标) )for(i= l;i count;i+)按优先级排序(item = pi;J = 1-1;while(item.Order = 0)pi+i = pj;-j;) p

8、lj+l =item;return;四、实验结果测试数据：进程名到达时间运行时间A04B13C25D44(1)先来先服务算法调试入入 即司H:chevisfcfssjfDebugfcfssjf.exe上数量：4卜ID,到达时刻，估计运行时间（用空格隔开）:先来先服务算法ID到达运行等待开始完成周转带权周转A0.0004.0000.0000.0004.0004.0001.000B1.0003.0003.0004.0007.0006.0002.000C2.0005.0005.0007.00012.00010.0002.000D4.0004.0008.00012.00016.00012.0003.0

9、00平均周转时间为；8.000000.x x x x x x x X .X xx xx 平均带权周转时间为:2.000000f f X X X X X X XX X X XX XX Xf X X X X X X * X X XX XX、Press any key to continue（2）最短作业优先算法调试司H:chevisfcfssjfDebugfcfssjf.exe*入入4nRnH 30 主星目1 Ik IL-估计运行时间用空格隔开）:最短作业优先算法ID到达运行等待A0.0004.0000.000B1.0003.0003.0004.0004.0003.0002.0005.0009.0

10、0011.000开始0-0007.75000047完成周转带权周转4.0004.0001.0007.0006.0002.00011.0007.0001.75016.00014.0002.8000 0 00 0 0平均周转时间为:平均带权周转时间为：1-887500Press any key to continue五、实验小结FCFS调度算法有利于CPU繁忙型的作业，而不利于IO繁忙型的作业（进程）。CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求LOo通常的 科学计算便属于CPU繁忙型作业。LO繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于LO

11、 繁忙型作业。SJ（P）F调度算法也存在不容忽视的缺点：该算法对长作业不利，如作业C的周转时间由10增至16,其带权周转时间由2增至3。 更严重的是，如果有一长作业（进程）进入系统的后备队列（就绪队列），由于调度程序总是优 先调度那些（即使是后进来的）短作业（进程），将导致长作业（进程）长期不被调度。该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或 无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。#include Hstdafx.hn#iiicludedefi

12、ne MAX 100 typedef stmct PCBcharjob.id10;作业IDfloatAiT_tiine;到达时刻floatFun.time;估计运行时间floatWhijtinie;等待时间floatStart_time;开始时刻floatFin_time;完成时刻floatTui_tmie;周转时间floatWTur_time;带权周转时间mtOrder;优先标记Hst;void fcfs(list *p,int count);void priiit(list *p,int count);void avg(list *p,int count);void fcfs(list *

13、pjnt count)先来先服务算法(list temp;临时结构体变量inti;intj;for(i = l;i count;i-H-)按到达时刻直接插入排序(temp = pi;while(temp.AiT_tiine = 0)pi+U = plj;-j;pj+l=teinp;)for(i = 0;i count;i+)循环计算各个作业的时间值(if(i = 0) /pi.Start_tiine = pi.Aii_tmie; elsepi.Stait_tmie = pi-l.Fin_tmie;开始时刻一前一个作业的完成时刻pi.Wait_time = pi.Start.time - pi.

14、Anytime;等待=开始-到达pi.Fm_time = pi.Stait_time + pi.Fun_tiine;完成一开始+运行pi.Tui_tiine = pi.Fm_time - pi.Air_time;周 转=完成-至 U 达pi.WTur_time = pi.TuOmie / pi.Fun.tmie;带权周转=周转/运行retuni:最短作业优先算法（sjf）最短运行时间作业的下标优先级设置最短运行时间开始的时刻list item;mt i = 0;mtj=0;mt k = 0;hit flag = 0:float niin = 0; float temp;结构体变量temp =

15、p0. Anytime;先求出最先到达作业的时刻保存最先到达的作业的时刻最先到达的作业的下标，默认为p0fbi(i = 0;i count;i+)temp = pi. Anytime; k = i;)fbi(i = 0;i count;i+)pk.Order = -H-flag;设置优先级为1,最高优先级pk.Start_tiine = tenip:pk.WaiCtime pk.Fm_time pk.Tur_tmie pk.WTui_time=temp - pk.An_time;计算各个时间=temp + pk.Fun_time;=pk.Fin_tinie - pk.AiT_tiine;=pk

16、.Tui_tiine / pk.Fun_tiine;niui= 100;temp = pk.Fin_time;后一个作业的开始时刻是前一个作业的完成时刻fbr(j = 0J countJ+)if(pj.Order != 0 | temp - pj.ArOime pj.Fun_time) ( niiii = pj.Fun_tmie; k = j;/求出满足条件最短运行时间的作业的下标) for(i = l;i count;i-H-)按优先级排序item = pi;J 7；while(item.Order = 0)pU+i = pj;-j;pj+l =item;return:)输出各个作业的详细信

17、息mt i;printfC* * *iiH), pnntf（-IDt到达t运行t等待t开始t完成t周转t带权周转W） fbi(i = 0;i count;i+)pnntf(M%st%.3ft%3ft%3ft%3ft%.3ft%.3ft%.3fii,pi.job_id,pi.Air_tuiie.pi.Fun_tiine.p i.Wait_.time,pi.Stai-t_time,pi.Fm_time,pi.Tui_time.pi.WTur_tmie);return:void avg(list *p,int count)(float AvgTurl;平均周转float AvgTur2;平均带权周转

18、float tl = 0;float t2 = 0;inti;周转时间和带权周转和fbi(i = 0;i count;i-H-) (tl +=pi.Tui_time;t2 += pi.WTui_time;AvgTiu 1 = tl/count;AvgTui2 = t2/count;pnntf（”n平均周转时间为：%ft平均带权周转时间为：%fn,AvgTurlAvgTui2）;return:mt(list stMAX;iiitjob_count = 0;mt flag = 1;mt i = 0;最多可以一百个作业作业数量算法标记pillltf(”请输入作业数量：) scanf(H%d,&job_count);piuitf（”请输入作业ID,到达时刻，估计运行时间（用空格隔开）：sc