【操作系统课程设计】Linux环境下使用C语言实现先来先服务调度算法.doc

作业模拟调度实验1 课程设计的目的通过该题目的设计过程，可以初步掌握作业调度的原理、软件开发方法并提高解决实际问题的能力。了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。2 课程设计的开发语言 程序设计所选用的程序设计语言为C语言。3 功能描述 先来先服务算法比较有利于长作业，而不利于短作业。（1）短作业（SJF）的调度算法可以照顾到实际上在所有作业中占很大比例的短作业，使它能比长作业优先执行。SPF优先调度算法：是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。为了和FCFS调度算法进行比较，我们利用FCFS算法中所使用的实例并改用SJ（P）F算法重新调度，再进行性能分析。采用SJF算法后，不论是平均周转时间还是平均带权周转时间都有较明显的改善，尤其是对短作业D，其周转时间由FCFS算法的11降为SJF算法中的3；而平均带权周转时间是从5.5降到1.5。这说明SJF调度算法能有效地降低作业的平均等待时间和提高系统的吐量。短作业优先调度算法对比先来先服务，不论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业。该算法对长作业不利，而且未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。如作业C的周转时间由10增至16，带权周转时间由2增至3.1。更严重的是，如果有一长作业（进程）进入系统的后备队列（就绪队列），由于调度程序总是优先调度那些（即使是后进来的）短作业（进程），将致使长作业（进程）得不到调度。（2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程），会得到及时处理；（3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。 高响应比优先调度算法在批处理系统中，用作作业调度的短作业优先算法是一个比较好的算法。其主要缺点是作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权机制，并使以速率a增加，则长作业在等待一定的时间后，必须有机会分配到处理机。该优先权的变化可描述为：优先权=（等待时间+要求服务时间）/要求服务时间 由于等待时间加上要求服务时间，就是系统对该作业的响应时间，故该优先权又相当于响应比Rp = 等待时间加要求服务时间/要求服务时间=响应时间/要求服务时间由上式可以看出：（1）如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业；（2）当要求服务的时间相同时，作业的优先权决定于其等待时间，因而实现了先来先服务；（3）对于长作业，当其等待时间足够长时，其优先权便可升到很高，从而也可获得处理机。该算法既照顾了短作业，又考虑了作业到达的先后顺序，也不会使作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，再利用该算法时，每要进行调度之前，都需先进行响应应比的计算，这会增加系统的开销。4 方案论证4.1 概要设计假设在单道批处理环境下有四个作业JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法，计算出作业的平均周转时间和带权的平均周转时间 。 作业 i 的周转时间：Ti=Tci-Tsi作业的平均周转时间：T=作业i的带权周转时间：Wi=Ti/Tri作业的平均带权周转时间：W=先来先服务调度算法（FCFS）：每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，这每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可分别用于作业调度和进程调度。该调度算法是从后备（就绪）队列中选择一个或若干个估计运行时间最短的作业（进程），将它们调度内存运行。响应比高者优先（HRN）：每次从后备队列中选择一个或若干个估计响应比最高的作业，将它们调入内存运行。响应比Rp=作业响应时间/运行时间 =作业等待时间+作业运行时间 =1+作业等待时间每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。 4.2 详细设计4.2.1 程序设计过程中的部分算法（1）用类C语言定义相关的数据类型定义头文件：#include <stdio.h>#include <stdlib.h>#define getpch(type) (type*)malloc(sizeof(type)定义结构体：struct worktime float Tb; /作业运行时刻 float Tc; /作业完成时刻 float Ti; /周转时间 float Wi; /带权周转时间;struct jcb /定义作业控制块JCB char name10; /作业名 float subtime; /作业提交时间 float runtime; /作业所需的运行时间 char resource; /所需资源 float Rp; /后备作业响应比 char state; /作业状态 struct worktime wt; struct jcb* link; /链指针*jcb_ready=NULL,*j;（2）各模块伪码void SJFget() / 获取队列中的最短作业 JCB *front,*mintime,*rear; /定义JCB指针 int ipmove=0; mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if(rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime) /队列不空时，给作业排队 front=mintime; mintime=rear; rear=rear->link; ipmove=1; else rear=rear->link; if (ipmove=1) /队首作业完成，后续作业重新排队 front->link=mintime->link; mintime->link=jcb_ready; jcb_ready=mintime;void HRNget() / 获取队列中的最高响应作业 JCB *front,*mintime,*rear; int ipmove=0;/初始化 mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if (rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp) /队尾不空时，作业按运行时间排队 front=mintime; mintime=rear; rear=rear->link; ipmove=1; else rear=rear->link; if (ipmove=1) /队首作业完成，改变指针 front->link=mintime->link; mintime->link=jcb_ready; jcb_ready=mintime;开 始4.2.2 主程序流程图 : 初始化所有的JCB使JCB按作业提交的时刻的先后顺序排队时间量： 调度队首的作业投入运行：（更改队首指针，使作业的状态为R，记住作业开始运行的时刻Tb等）计算并打印运行作业i的完成时刻Tc，周转时间Ti，带权周转时间Wi（完成时刻Tc=开始运行时刻+运行时间周转时间Ti=完成时刻-提交时刻带权周转时间Wi=周转时间÷运行时间）更改时间量T的值（T：=T+作业i的运行时间）队列为空 ?计算并打印这组作业的平均周转时间及带权平均周转时间 结 束 图1 调度算法流程图 图25 运行结果 图3 运行结果6 心得体会 经过一周的努力，我的课程设计基本完成了，这次课程设计培养了我耐心、慎密、全面地考虑问题的能力，从而加快了问题解决的速度、提高了个人的工作效率，以及锻炼围绕问题在短时间内得以解决的顽强意志。在编写程序的过程中，我的能力得到了提高，同时养成了科学、严谨的作风和习惯。为此我要感谢信息学院开设了这门操作系统课程设计，为我们提供了进一步学习算法、操作系统和巩固C语言程序计设这个平台并。同时还要感谢对同一题目进行攻关的同学们给予的帮助，没他们的帮助可能有很多问题我个人不能进行很好的解决。在此我对他们帮助给予衷心的感谢。7 附录#include "stdio.h" #include <stdlib.h> #define getpch(type) (type*)malloc(sizeof(type) struct worktime float Tb; /作业运行时刻 float Tc; /作业完成时刻 float Ti; /周转时间 float Wi; /带权周转时间;struct jcb /*定义作业控制块JCB */ char name10; /作业名 float subtime; /作业提交时间 float runtime; /作业所需的运行时间 char resource; /所需资源 float Rp; /后备作业响应比 char state; /作业状态 struct worktime wt; struct jcb* link; /链指针*jcb_ready=NULL,*j;typedef struct jcb JCB;float T=0;void sort() /* 建立对作业进行提交时间排列函数*/ JCB *first, *second; int insert=0; if(jcb_ready=NULL)|(j->subtime)<(jcb_ready->subtime) /*作业提交时间最短的,插入队首*/ j->link=jcb_ready; jcb_ready=j; T=j->subtime; j->Rp=1; else /* 作业比较提交时间,插入适当的位置中*/ first=jcb_ready; second=first->link; while(second!=NULL) if(j->subtime)<(second->subtime) /*若插入作业比当前作业提交时间短,*/ /*插入到当前作业前面*/ j->link=second; first->link=j; second=NULL; insert=1; Else /* 插入作业优先数最低,则插入到队尾*/ first=first->link; second=second->link; if (insert=0) first->link=j; void SJFget() /* 获取队列中的最短作业 */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime->link; while(rear!=NULL)if(rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime) front=mintime; mintime=rear; rear=rear->link; ipmove=1; else rear=rear->link; if (ipmove=1) front->link=mintime->link; mintime->link=jcb_ready; jcb_ready=mintime;void HRNget() /* 获取队列中的最高响应作业 */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if (rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp) front=mintime; mintime=rear; rear=rear->link; ipmove=1; else rear=rear->link; if (ipmove=1) front->link=mintime->link; mintime->link=jcb_ready; jcb_ready=mintime;void input() /* 建立作业控制块函数*/ int i,num; printf("n 请输入作业数:?"); scanf("%d",&num); for(i=0;i<num;i+) printf("n 作业号No.%d:n",i); j=getpch(JCB); printf("n 输入作业名:"); scanf("%s",j->name); printf("n 输入作业提交时刻:"); scanf("%f",&j->subtime); printf("n 输入作业运行时间:"); scanf("%f",&j->runtime); printf("n"); j->state='w' j->link=NULL; sort(); /* 调用sort函数*/ int space() int l=0; JCB* jr=jcb_ready; while(jr!=NULL) l+; jr=jr->link; return(l); void disp(JCB* jr,int select) /*建立作业显示函数,用于显示当前作业*/ if (select=3) printf("n 作业 服务时间 响应比 运行时刻 完成时刻 周转时间 带权周转时间 n"); else printf("n 作业 服务时间 运行时刻 完成时刻 周转时间 带权周转时间 n"); printf(" |%st",jr->name); printf(" |%.2ft ",jr->runtime); if (select=3) printf(" |%.2f ",jr->Rp); if (j=jr) printf(" |%.2ft",jr->wt.Tb); printf(" |%.2f ",jr->wt.Tc); printf(" |%.2f t",jr->wt.Ti); printf(" |%.2f",jr->wt.Wi); printf("n"); void check(int select) /* 建立作业查看函数 */ JCB* jr; printf("n * 当前正在运行的作业是:%s",j->name); /*显示当前运行作业*/ disp(j,select); jr=jcb_ready; printf("n *当前就绪队列状态为:n"); /*显示就绪队列状态*/ while(jr!=NULL) jr->Rp=(T-jr->subtime)/jr->runtime; disp(jr,select); jr=jr->link; destroy();int destroy() /*建立作业撤消函数(作业运行结束,撤消作业)*/ printf("n 作业 %s 已完成.n",j->name); free(j); void running(JCB* jr) /* 建立作业就绪函数(作业运行时间到,置就绪状态*/ if (T>=jr->subtime) jr->wt.Tb=T; else jr->wt.Tb=jr->subtime; jr->wt.Tc=jr->wt.Tb+jr->runtime; jr->wt.Ti=jr->wt.Tc-jr->subtime; jr->wt.Wi=jr->wt.Ti/jr->runtime; T=jr->wt.Tc;int main() /*主函数*/ int select=0,len,h=0; float sumTi=0,sumWi=0; input(); len=space(); printf("nt1.FCFS 2.SJF 3.HRNnn请选择作业调度算法:?"); scanf("%d",&select); while(len!=0)&&(jcb_ready!=NULL) h+; printf("n 执行第%d个作业 n",h); j=jcb_ready; jcb_ready=j->link; j->link=NULL; j->state='R' running(j); sumTi+=j->wt.Ti; sumWi+=j->wt.Wi; check(select); if (select=2&&h<len-1) SJFget(); if (select=3&&h<len-1) HRNget(); printf("n 按任一键继续.n"); getchar(); getchar(); printf("nn 作业已经完成.n"); printf("t 此组作业的平均周转时间：%.2fn",sumTi/h); printf("t 此组作业的带权平均周转时间：%.2fn",sumWi/h);getchar(); 参考文献1汤子瀛，哲凤屏.计算机操作系统M.西安电子科技大学学出版社.2王清，李光明.计算机操作系统M.冶金工业出版社.3孙钟秀. 操作系统教程M. 高等教育出版社4曾明.  Linux操作系统应用教程M. 陕西科学技术出版社. 5张丽芬，刘利雄.操作系统实验教程M. 清华大学出版社.6孟静， 操作系统教程原理和实例分析M. 高等教育出版社.7周长林，计算机操作系统教程M. 高等教育出版社8张尧学，计算机操作系统教程M，清华大学出版社9任满杰，操作系统原理实用教程M，电子工业出版社