各类作业调度算法

1、各类作业调度算法实验二 作业调度实验一 . 目的要求： 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调 度算法的理解。二. 例题：为单道批处理系统设计一个作业调度程序。 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源 直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足， 它所占用的 CPU时限等因素。作业调度算法：采用先来先服务( FCFS)调度算法，即按作业提交的先后 次序进行调度。总是首先调度在系统中等待时间最长的作业。每个作业由一个作业控制块 JCB表示， JCB可以包含如下信息：作业名、提 交时间、所需的运行时间、所需的资源、作业状态

2、、链指针等等。作业的状态可以是等待 W(Wait) 、运行 R(Run)和完成 F(Finish) 三种状态之 一。每个作业的最初状态总是等待 W。各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中 队首的作业。每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带 权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权 平均周转时间。调度算法的流程图如下图所示。三 . 实习题：1、编写并调试一个单道处理系统的作业等待模拟程序。作业等待算法：分别采用先来先服务（ FCFS），最短作业优先（ SJF）、响 应比高者优先（ HRN）的调度算法。对每种调度算法都

3、要求打印每个作业开始运行时刻、完成时刻、周转时间、 带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各 种算法的优缺点2、编写并调度一个多道程序系统的作业调度模拟程序作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法 进行设计。对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必 须考虑到每个作业的资源要求。3、编写并调试一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于优先级的作业调度。 可以参考课本中的例子自行设计。三 . 实验过程：1、编写并调试一个单道处理系统的作业等待模拟程序。先来先服务（ FCFS）：main.cpp:/* 先来

4、先服作业调度算法模拟*/#include #include #define MAX_SOURCE 1000 / 资源总数（对于单通道的作业调度可以忽略系统 资源问题）using namespace std;struct jobCBstring name;double subtime;/ 提交时间double runtime;/ 运行时间double source;/ 资源char state;/ 进程状态struct jobCB *next; /链指针*ready,*rail,*p;int length;double maxsource;double now_source;double all

5、Ti;/ 总周转时间double allWi;/ 总带权周转时间double time;/ 时钟void init（）time=0;length=0;allTi=0;allWi=0;maxsource=MAX_SOURCE;now_source=0;rail=ready=p=NULL;void destroy()maxsource+=p-source;/ 释放资源 time+=p-runtime;p-state=f;delete p;void running()p-state=r;double Tc = time+ p-runtime;/ 完成时刻double Ti = Tc - p-subt

6、ime;/ 周转时间double Wi = Ti/p-runtime;/ 带权周转时间周转时间timecoutn 作业name 信息： endl;coutn 录入时间 运行时间 开始运行的时刻 完成时刻 带权周转时间 endl;coutnsubtimet runtimet tTct Ti tWiendl;allTi+=Ti;allWi+=Wi;destroy();void display()coutnendl;for(int i=0; inext;p-state = r;running();coutnsource;/ 分配资源给作业if (maxsource=now_source ) if(r

7、eady=NULL)ready=rail=p;elserail-next=p;rail=p;length +;else now_source-=p-source;/ 回退 cout 没有足够资源！ endl; return;void input()int n;-endl;cout-先来先服作业调度算法模拟cout 请输入作业数 : n;for(int i = 0; i n; i+)p = new jobCB;cout 当前作业录入时间： time; coutp-name;coutp-runtime;coutp-source;p-state = w; p-subtime = time;time+

8、;p-next = NULL; in_queue();int main()init();input();display();coutn 这组作业的平均周转时间为 : allTi / lengthendl; coutn 这组作业的带权平均周转时间为 : allWi / lengthendl; return 0; (程序测试运行结果在附件里)短作业优先( SJF) :main.cpp:/* 短作业优先作业调度算法模拟*/#include #include #define MAX_SOURCE 1000using namespace std;struct jobCBstring name;doubl

9、e subtime;/ 提交时间double runtime;/ 运行时间double source;/ 资源char state;/ 进程状态struct jobCB *next; /链指针*ready,*rail,*p;int length;double maxsource; /资源总数， 对于单通道作业调度， 资源部分可以去掉 (由 于当时写多道时是在单道上直接修改的，所以这里多道部分仍然在) double now_source; / 当前资源double allTi;/ 总周转时间double allWi;/ 总带权周转时间double time;/ 时钟void init()time

10、=0;length=0;allTi=0;allWi=0;maxsource=MAX_SOURCE;now_source=0;rail=ready=p=NULL;void destroy()Maxsource+=p-source;/ 释放资源 time+=p-runtime;p-state=f;delete p;void running()p-state=r;double Tc = time+ p-runtime;/ 完成时刻double Ti = Tc - p-subtime;/ 周转时间double Wi = Ti/p-runtime;/ 带权周转时间周转时间timecoutn 作业name

11、 信息： endl;coutn 录入时间 运行时间 开始运行的时刻 完成时刻 带权周转时间 endl;coutnsubtimet runtimet tTct Ti tWiendl;allTi+=Ti;allWi+=Wi;destroy();void display()coutnendl;for(int i=0; inext;p-state = r; running();coutnsource;/ 分配资源给作业 jobCB *q1,*q2;if(maxsource=now_source)if(ready=NULL)ready=rail=p;elseif(p-runtimeruntime)p-n

12、ext=ready; ready=p;else q1=ready;q2=ready-next;while(q2!=NULL)if(q2-runtimep-runtime)p-next=q2;q1-next=p;flag=1;q1=q2;q2=q2-next;if(flag=0) q1-next=p;length +;elsenow_source-=p-source;/ 回退cout 没有足够资源！ endl;return;void input()int n;cout - 短作业优先作业调度算法模拟 -endl;cout 请输入作业数 : n;for(int i = 0; i n; i+)p =

13、 new jobCB;cout 当前作业录入时间： time;coutp-name;coutp-runtime;coutp-source;p-state = w;p-subtime = time;time+;p-next = NULL;in_queue();int main()init();input();display();coutn 这组作业的平均周转时间为 : allTi / lengthendl; coutn 这组作业的带权平均周转时间为 : allWi / lengthendl; return 0; (程序测试运行结果在附件里)响应比高者优先( HRN)：main.cpp:/* 响应

14、比高优先作业调度算法模拟*/#include #include #include #define MAX_SOURCE 1000using namespace std;struct jobCBstring name;double subtime;/ 提交时间double runtime;/ 运行时间double source;/ 资源char state;/ 进程状态struct jobCB *next; /链指针*p;list jobqueue; /声明作业调度队列，使用 STL list :iterator it;int length;double maxsource;double now

15、_source;double allTi;/ 总周转时间double allWi;/ 总带权周转时间double time;/ 时钟double inputfinishtime;/ 输入结束时间void init()time=0;length=0;allTi=0;allWi=0;inputfinishtime=0;maxsource=MAX_SOURCE;now_source=0;p=NULL;void destroy()maxsource+=p-source;time+=p-runtime;p-state=f;void running()p-state=r;double Tc = time+

16、 p-runtime;/ 完成时刻double Ti = Tc - p-subtime;/ 周转时间double Wi = Ti/p-runtime;/ 带权周转时间coutn 作业name 信息： endl;coutn 录入时间 运行时间 开始运行的时刻 带权周转时间 响应比 endl;coutnsubtimet runtimet tTct Ti tsubtime)/p-runtime+1endl;标准模板库）的 list完成时刻 周转时间timetWiallTi+=Ti;allWi+=Wi; destroy();void display()coutnendl;for(int i=0; is

17、tate = r;running();coutnsource;/ 分配资源给作业 if(maxsource=now_source)jobqueue.push_back(p);length +;elsenow_source-=p-source;/ 回退 cout 没有足够资源！ (inputfinishtime-subtime)/runtime /coutsubtime)/p-runtimesubtime)/p-runtime;bool compare(jobCB *first,jobCB *second) / 用于 list 排序的 compare 函数 if(makeout_ResR(fir

18、st)makeout_ResR(second) return true; else return false;void input()int n;cout- 响应比优先作业调度算法模拟 -endl;cout 请输入作业数 : n;inputfinishtime=n*1;for(int i = 0; i n; i+)p = new jobCB;cout 当前作业录入时间： time;coutp-name; coutp-runtime;coutp-source;p-state = w; p-subtime = time; time+; p-next = NULL; in_queue();jobqu

19、eue.sort(compare); int main() init();input();display();coutn 这组作业的平均周转时间为 : allTi / lengthendl;coutn 这组作业的带权平均周转时间为 : allWi / lengthendl; return 0; (程序测试运行结果在附件里)2、编写并调度一个多道程序系统的作业调度模拟程序。采用基于先来先服务的调度算法：(程序源码在 1中已粘贴， 1 中不需要用 到 source 部分)3、编写并调试一个多道程序系统的作业调度模拟程序。作业调度算法：采用基于优先级的作业调度。main.cpp:/* 短作业优先作业

20、调度算法模拟*/#include #include #define MAX_SOURCE 1000using namespace std;struct jobCBstring name;double subtime;/提交时间double runtime;/运行时间double source;/ 资源int priority;/ 优先级char state;/ 进程状态struct jobCB *next; / 链指针 *ready,*rail,*p;int length;double maxsource;double now_source;double allTi;/ 总周转时间 doubl

21、e allWi;/ 总带权周转时间 double time;/ 时钟 void init()time=0;length=0;allTi=0;allWi=0;maxsource=MAX_SOURCE; now_source=0;rail=ready=p=NULL;void destroy()maxsource+=p-source; time+=p-runtime;p-state=f;delete p;void running()完成时刻p-state=r;double Tc = time+ p-runtime;/double Ti = Tc - p-subtime;/周转时间double Wi = Ti/p-runtime;/带权周转时间周转时间timecoutn 作业 name信息： endl;coutn 录入时间 运行时间 开始运行的时刻 完成时刻 带权周转时间 优先级 endl;coutnsubtimet runtimettTct Ti tWi tpriorityendl;allTi+=Ti;allWi+=Wi;destroy();void display()coutnendl;for(int i=0; inext;p-state = r;running();cou