短作业优先调度算法.doc

课程设计报告课程设计题目： 短作业优先(SJF)调度算法模拟 专 业：计算机科学与技术班 级：姓 名： 学 号: 指导教师: 2013年 01 月 09日目录摘要2第一章 概述31.1 课程设计的目的31.2 主要完成的任务31.3 使用的开发工具31.4解决的主要问题3第二章 课程设计的基本概念和原理4第三章 总体设计5第四章 详细设计64.1数据结构64.2具体数据结构和模块设计简要说明64.3 程序相关数据6第五章 短作业优先调度的算法实现9第六章 设计结果及分析16总结20参考文献21评分表22摘要在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。关键字：多道程序 进程调度 短作业优先(SJF)调度算法第一章 概述1.1 课程设计的目的加深对作业概念的理解，掌握短作业优先（SJF）算法，深入了解批处理系统如何组织作业、管理作业和调度作业，了解作业控制块的作用，以及作业控制块的内容和组织方式。进行操作系统课程设计主要是在学习操作系统课程的基础上，在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。1.2 主要完成的任务本次课程设计主要的任务是用C语言来实现对N个进程采用短作业优先算法对进程调度进行模拟。1.3 使用的开发工具Microsoft Visual C+ 6.01.4解决的主要问题随着计算机进入多道程序系统，如何分配CPU资源就成为了操作系统不可避免要面临的一个问题。计算机只有一个CPU，或者只有有限的CPU资源，当系统中有多个进程处于就绪状态，要竞争CPU资源时，操作系统就要负责完成如何分配资源的任务。在操作系统中，由调度程序来完成这一选择分配工作，调度程序所使用的算法即是调度算法，调度算法需要考虑的指标主要有尽量保证CPU资源分配的公平性，按照一定的策略强制执行算法调度；平衡整个计算机系统，尽量保持各部分都正处于忙碌状态。因此短作业优先算法就是一个较好的算法。 第二章 课程设计的基本概念和原理 本次课程设计主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求立即执行，因而可能造成难以预料的后果。因此，在要求比较严格的实时系统中，不宜采用这种调度方式。本课程设计主要是在满足要求多道单处理机的情况下进行短作业的优先调度。第三章 总体设计本次课程设计主要是通过比较各个进程的优先级以及各进程所需要占用的CPU时间来确定哪个作业优先运行，短作业优先调度算法除了能保证优先级更高的作业优先运行外，还能使相同优先级的前提下，所需CPU时间最短的那个作业优先运行，次外，本次课程设计还增加了阻塞时间和被阻塞时间来对个进程的运行加以控制。此次课程设计的总体流程图如下： 图1 总体流程图第四章 详细设计4.1数据结构每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：进程标识数ID；进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高；进程已占用的CPU时间CPUTIME；进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0；进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，进程将进入阻塞状态；进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，进程将转换成就绪状态；进程状态STATE；队列指针NEXT，用来将PCB排成队列。在这个模拟程序中作业控制块PCB的数据结构类型可定义为：Struct PCB /作业控制块 int ID ;/进程编号IDint Priority; /进程优先级随机产生int CPUtime; /进程占用CPU时间int Alltime; /进程还需占用的CPU时间，随机产生int Startblock; /进程的阻塞时间int Blocktime; /进程被阻塞的时间int state; /进程状态struct PCB*next; /结构体指针 4.2具体数据结构和模块设计简要说明（1）短作业优先算法：首先比较各进程的优先级，优先级越大的进程优先执行，在优先级相同的情况下，判断作业的alltime，alltime最小的最先执行，依次按照时间从小到大执行进程。（2）数据结构（见详细设计）（3）主函数模块 4.3 程序相关数据假设在调度前，系统中有5个进程，它们的初始状态如下：ID01234PRIORITY268211CPUTIME00000ALLTIME32631STARTBLOCK2-1-1-1-1BLOCKTIME20000STATEREADYREADYREADYREADYREADY（2）为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来，参照的具体格式如下：RUNNING PROG： iREADY_QUEUE:-id1-id2BLOCK_QUEUE:-id3-id4 ID 01234PRIORITY P0P1P2P3P4CPUTIME C0C1C2C3C4ALLTIME A0 A1A2A3A4STARTBLOCK T0T1T2T3T4BLOCKTIME B0B1B2B3B4STATE S0S1S2S3S4详细流程图如下：NY判断Alltime是否为0结束NY=比较两个进程所需占用的CPU时间前者优先级是小于还是等于后者改变进程相关数值的大小依次执行位于前面的进程交换位置前者大于后者？依次比较相邻两个进程的优先级开始 第5章 短作业优先调度的算法实现/使用短作业优先调度算法的模拟 #include #define N 5void init();void print();int getRunning();void sort();int run(int time);enum STATEReady,Run,Block,RunOut;struct PROCESSint ID; /进程标志数IDint Priority; /进程优先数int Cputime; /进程已占用的CPU时间int Alltime; /进程已占用的CPU时间int Startblock; /进程的阻塞时间int Blocktime; /进程被阻塞的时间enum STATE State; /进程的状态ProcessN;int READYN;int BLOCKN;int RUNOUTN2;int main() / 主函数int Time=0;init();printf(Time:%dn,Time);sort();print();while(1)Time+;getchar();printf(Time:%dn,Time);if(run(Time)break; return 0;void init()int i; for(i=0;i=0)printf(tRUNNING PROG: %dn,getRunning();printf(tREADY_QUEUE:);for(i=0;i=0)printf(-%d,ProcessREADYi.ID);elsebreak; printf(ntBLOCK_QUEUE:);for(i=0;i=0)printf(-%d,ProcessBLOCKi.ID);elsebreak;printf(n=n);printf(IDt);for(i=0;iN;+i)printf(t%d,Processi.ID);printf(nPRIORITY);for(i=0;iN;+i)printf(t%d,Processi.Priority);printf(nCPUTIMEt);for(i=0;iN;+i)printf(t%d,Processi.Cputime);printf(nALLTIMEt);for(i=0;iN;+i)printf(t%d,Processi.Alltime);printf(nSTARTBLOCK);for(i=0;iN;+i)printf(t%d,Processi.Startblock);printf(nBLOCKTIME);for(i=0;iN;+i)printf(t%d,Processi.Blocktime);printf(nSTATEt);for(i=0;iN;+i)switch(Processi.State)case 0:printf(tReady);break;case 1:printf(tRun); if(Processi.Alltime=0)Processi.State=RunOut;else Processi.State=Ready; break;case 2:printf(tBlock);break;case 3:printf(tRunOut);break;printf(n);printf(tRUNOUT LIST:);for(i=0;i=0)printf(-%d(%d),ProcessRUNOUTi0.ID,RUNOUTi1);elseprintf(n);break; printf(n);int getRunning()int i;for(i=0;iN;+i)if(Processi.State=Run)return i;for(i=0;iN;+i)if(Processi.Startblock=0)return i;return -1;void sort()int i,j,k;for(i=0;iN;+i)READYi=-1;BLOCKi=-1;for(i=0;iN;+i)if(Processi.State=Ready|Processi.State=Run) if(Processi.Alltime=0)continue;for(j=0;jN;+j)if(READYj0)READYj=i;break;else if(Processi.PriorityProcessREADYj.Alltime) / 在相邻两个进程优先级相同的情况下，比较各进程所需占用CPU时间的大小 continue;elsefor(k=N-1;kj;-k)READYk=READYk-1;READYj=i;break;else if(Processi.State=Block)for(j=0;jN;+j)if(BLOCKj=ProcessBLOCKj.Blocktime) continue; elsefor(k=N-1;kj;-k)BLOCKk=BLOCKk-1;BLOCKj=i;break;int run(int time) int i,runNum;runNum=READY0;if(runNum0&BLOCK0=0) ProcessrunNum.Alltime-=1;ProcessrunNum.Cputime+=1;ProcessrunNum.State=Run;for(i=0;iN;+i)if(i!=runNum)if(Processi.State=Ready) else if(Processi.State=Block)Processi.Blocktime-=1;if(Processi.Blocktime=0)Processi.State=Ready; if(ProcessrunNum.Alltime=0) for(i=0;iN;+i)if(RUNOUTi0=0)ProcessrunNum.Startblock-=1;if(ProcessrunNum.Startblock=0)ProcessrunNum.State=Block; else if(BLOCK0=0)for(i=0;iN;+i)if(Processi.State=Block)Processi.Startblock=-1;Processi.Blocktime-=1;if(Processi.Blocktime=0)Processi.State=Ready; sort();print();return 0; 第六章 设计结果及分析从程序的运行结果来看，开始应先比较各进程的优先级，优先级越高的进程先执行，执行顺序为0,1,2，由于进程3和4的优先级一样，因此应选一个作业更短的进程运行，进程4比进程3所需占用的CPU时间更少，所以先执行进程4，后执行进程3。从分析结果来看，本次课程设计基本上实现了短作业优先调度算法的模拟，由于短作业优先调度算法与动态优先调度算法类似，我通过在网上找到动态优先调度算法的程序，并且通过看书，查资料，对短作业优先调度思想加以熟悉后，对此程序进行更改以及调试后，最终成功运行了，因此在程序方面没有遇到什么大问题。总结通过本次课程设计，使我对计算机操作系统短作业优先调度算法这一节的知识有了更深的了解 。短作业优先调度算法易于实现，并且效率很高，但是短作业只考虑到短作业的利益，而不顾长作业，这样就可能会使得长作业一直处于等待状态而不能运行。所以，短作业优先算法适用于系统中短作业较多的情况。此外，我对操作系统中的作业调度模拟和短作业优先算法有了更深的认识。并且发现，只看课本上的知识远远不够，只一味学习也根本没用，必须要动手亲自实践，才能真正掌握所学的东西。虽然在这次课程设计过程中，我们也遇到了很多问题，但我们都能保持一个良好的心态，不急不躁，并且能通过请教老师，