《实现FCFS和SJF调度算法》由会员分享,可在线阅读,更多相关《实现FCFS和SJF调度算法(12页珍藏版)》请在金锄头文库上搜索。
1、操作系统实验报告操作系统实验报告实验一:作业调度实验一:作业调度学院:学院:软件学院专业:专业:软件工程班级:班级:软件工程 12-01姓名:姓名:*学号:学号:541213460157实验一:作业调度实验一:作业调度 实现 FCFS 和 SJF 调度算法【实验题目实验题目】:编写程序,实现 FCFS 和 SJF 算法,模拟作业调度过程,加深对作业调度的理解。【实验内容实验内容】实现FCFS和SJF调度算法。 数据结构设计(JCB,后备作业队列) 算法实现与模拟(排序、调度) 输出调度结果,展示调度过程并解释【实验要求实验要求】1. 设计作业控制块(JCB)的数据结构 应包含实验必须的数据项,
2、如作业ID、需要的服务时间、进入系统时间、完成时间,以及实验者认为有必要的其他数据项。2. 实现排序算法(将作业排队) 策略1:按“进入系统时间”对作业队列排序(FCFS) 策略2:按“需要的服务时间”对作业队列排序(SJF)3. 实现调度过程模拟(1)每个作业用一个JCB表示,如果模拟FCFS,按策略1将作业排队,如果模拟SJF,按策略2将作业排队(2)选择队首的作业,将其从后备队列移出。(3) (作业运行过程,在本实验中,无需实现,可认为后备队列上的作业一但被调度程序选出,就顺利运行完毕,可以进入第4步)(4)计算选中作业的周转时间(5) 进行下一次调度(去往第2步)4.实现结果输出 输出
3、作业状态表,展示调度过程 初始作业状态(未调度时) 每次调度后的作业状态5.撰写实验报告 包含实验要求中14项内容,要求有设计图(结构图/流程图)和源代码。 注明使用的编程语言和环境。注意事项 实验中注重实现算法本质(先来先服务,短作业优先)。 两个算法可以使用一套程序,差别只在队列的排序方式。 这两个算法也可适用于进程调度。关于作业调度和进程调度的区别,只要求概念上理解清楚,不要求实现。设计设计作业控制块作业控制块(JCB)的的数据结构数据结构 每个作业由一个作业控制块JCB表示,JCB可以包含如下信息:作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下: ty
4、pedef struct jcbchar 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=
5、NULL; 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。,组成一个后备队列等待,总是首先调度等待队列中队首的作业。 本实验采用链表的形式存放各后备队列当中的作业控制块,各个等待的作业按照提交时刻的先后次序排队。当一个作业进入系统时,就为其动态建立一作业控制块(JCB),挂入后备队列尾部。当作业调度时,从后备队列中按某种调度算法选择一作业,让其进入主存以便占用CPU执行。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间,这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。设计
6、图设计图编程语言:编程语言:c+编程环境:编程环境:Visual C+ 6.0程序代码:程序代码:FCFS:#include using namespace std; class Fcfs private: int num10; /作业编号 double arriveTime10; /到达时间 double startTime10; /开始时间,进内存时间 double workTime10; /工作时间 double finishTime10; /完成时间 double cirTime10; /存放每一个作业的周转时间 / double freeTime10; /上一个作业已结束,但下一个作
7、业还未到,存放这一段空闲 时间 public: Fcfs(int n) /n 为作业数目 coutarriveTimei; if(i=0) arriveTimei=0; /默认第一个作业的到达时间为 0 coutworkTimei; if(i=0) startTimei=0; finishTimei=workTimei; /freeTimei=0; else if(arriveTimeifinishTimei-1) /freeTimei=arriveTimei-finishTimei-1;/计算空闲时间,前一个作业已 完成,但后一个作业还没到,中间空闲时间 startTimei=arriveT
8、imei; /由于来的时候前一个作业已完成,则该作业的开始时间即为它的到达 时间 finishTimei=startTimei+workTimei; cirTimei=finishTimei-arriveTimei; /计算平均周转时间 double getAverageCir(int n) /n 为作业数 double averageCir,sumCir=0; for(int i=0;in; Fcfs f=Fcfs(n); f.print(n); return 0; SJF:#include using namespace std; class SJF private: int num10;
9、 /作业编号 double arriveTime10; /到达时间 double startTime10; /开始时间,进内存时间 double workTime10; /工作时间 double finishTime10; /完成时间 double cirTime10; /存放每一个作业的周转时间 public:SJF(int n) /n 为作业数目 int i; coutarriveTimei; if(i=0) arriveTimei=0; /默认第一个作业的到达时间为 0 coutworkTimei; if(i=0) startTimei=0; finishTimei=workTimei;
10、 cirTimei=finishTimei-arriveTimei; else /排序 for(int j=1;jworkTimek+1) double temp; temp=numk; numk=numk+1; numk+1=temp;temp=arriveTimek; arriveTimek=arriveTimek+1; arriveTimek+1=temp; temp=workTimek; workTimek=workTimek+1; workTimek+1=temp; for(i=1;in; SJF f=SJF(n); f.print(n); return 0; 实例截图:实例截图:五
11、个进程,到达时间分别为 5,10,13,20服务时间分别为 6,2,4,6设置选择量 n,当 n=1 时,选择 FCFS当 n=2 时,选择 SJF当 n=3 时,同时分别调用 FCFS 和 SJFn 不为 1 或 2 或 3 时提示错误,重新输入 n;1-FCFS 算法 2-SJF 算法实验总结:实验总结:本次实验题目为作业调度。实现实现 FCFS 和 SJF 调度算法。能初步掌握 FCFS 和 SJF 调度算法。对于 FCFS 和 SJF 调度算法的思路清晰,只是将其转化为代码形式,在脑海中,没有思路。经过查阅资料和与同学们交流,逐渐形成了一定的模块化思路。结合相关程序,在调试程序的过程中,意识到书写格式规范化及其重要性。明白了其中的功能。FCFS 与 SJF各有优缺点。对于 FCFS,当先执行的是长作业时,由于 FCFS 对短作业长时间等待,不利于短作业。对于 SJF,必须预知作业的运行时间,当短作业过多时,则不利于长作业。采用 SJF 算法时,人机无法实现交互。由于没有考虑到作业紧迫性,不能保证作业能够及时得到处理。选择哪一种算法,则根据具体情况而定。