处理机调度程序-操作系统课程设计报告

北 华 航 天 工 业 学 院操作系统课程设计报告课程设计题目： 处理机调度程序 作者所在系部： 计算机与遥感信息技术学院作者所在专业： 网络工程 作者所在班级： B12522 作 者 姓 名 ： 梁爽 作 者 学 号 ： 指导教师姓名： 刘立媛 完 成 时 间 ： 2015.1.5 北华航天工业学院教务处制课程设计任务书课题名称处理机调度程序完成时间2015.1.5指导教师刘立媛职称助教学生姓名梁爽班级B12522总体设计要求和技术要点处理机调度程序：选择一个调度算法，实现处理机调度。设计要求：主界面可灵活选择某算法，且以下算法都要实现：1、时间片轮转法2、短作业优先算法3、动态优先级算法执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，运行时间，优先数（由随机函数产生），执行，显示结果。工作内容及时间进度安排时间：此次课程设计时间为两周，第18、19周，共40学时。分四个阶段完成：1.分析设计阶段：明确设计要求，找出实现方法。这一阶段在第1天完成。2.编码调试阶段：根据设计分析方案编写代码，然后调试该代码，实现课题要求的功能。这一阶段在第2-8天完成。3.总结报告阶段：总结设计工作，撰写课程设计报告，这一阶段在第8-9天完成。4.考核阶段：这一阶段在第10天完成。地点：计算机与遥感信息技术学院实验室课程设计成果1与设计内容对应的软件程序2课程设计报告书摘 要计算机自从1946年第一台真正意义上的数字电子计算机ENIAC 的诞生以来，已经经历了1854年1890年、1890年20世纪早期、20世纪中期、20世纪晚期现在四个阶段，每一个阶段的发展都发生了质与量的突飞猛进。然而，计算机的发展只是代表了硬件的提升，对于软件，操作系统的发展更加引人注目。操作系统（OS）是管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统是控制其他程序运行，管理系统资源并为用户提供操作界面的系统软件的集合。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统的型态非常多样，不同机器安装的OS可从简单到复杂，可从手机的嵌入式系统到超级电脑的大型操作系统。目前微机上常见的操作系统有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。操作系统的不断提升对于计算机整体性能的提高有着至关重要的作用。操作系统对于各个方面的要求都不得不提到效率的问题，计算机系统的处理机调度便变得尤为重要。处理机调度的效率甚至可能成为提高计算机处理速度的瓶颈。处理机调度就是对系统的资源做出合理的分配，因而，提高处理机的调度算法也变得尤为重要。关键词：操作系统 处理机调度 系统资源目 录第1章 绪 论11.1 处理机调度功能11.2 处理机调度性能准则1第2章 系统需求分析32.1 时间片轮转调度算法32.2 短作业优先调度算法32.3 动态优先级调度算法3第3章 系统总体设计43.1 系统功能设计43.2 时间片轮转法设计43.3 短作业优先算法设计43.4 动态优先级算法设计4第4章 系统实现64.1 时间片轮转法实现64.2 短作业优先算法实现94.3 动态优先级算法实现12第5章 系统使用说明14第6章 课程设计总结156.1 主要问题及解决办法156.2 课程设计体会156.3 自我评定15参考文献16第1章 绪 论在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。1.1 处理机调度功能一般情况下，当占用处理机的进程因为某种请求得不到满足而不得不放弃CPU进入等待状态时，或者当时间片到，系统不得不将CPU分配给就绪队列中另一进程的时候，都要引起处理机调度。除此之外，进程正常结束、中断处理等也可能引起处理机的调度。因此，处理机调度是操作系统核心的重要组成部分，它的主要功能如下：（1）记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息，将这些信息记录在相应的进程控制块中。（2）根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间。（3）收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候，保存该进程的现场，并收回处理机。处理机调度的功能中，很重要的一项就是根据一定算法，从就绪队列中选出一个进程占用CPU运行。可见，算法是处理机调度的关键。1.2 处理机调度性能准则处理机调度，有许多不问的调度算法，不同的调度算法具有不同的特性。因此，在介绍算法之前，先介绍衡量一个算法的基本准则。衡量和比较调度算法性能优劣主要有一下几个因素：（1）CPU利用率。CPU是计算机系统中最重要的资源，所以应尽可能使CPU保持忙，使这一资源利用率最高。（2）吞吐量。CPU运行时表示系统正处于工作状态，工作量的大小是以每单位时间所完成的作业数目来描述的，这就叫吞吐量。（3）周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。（4）等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察等待时间。（5）响应时间。指从作业提交到系统作出响应所经过的时间。在交互式系统中，作业的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即响应时间。从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。第2章 系统需求分析 FCFS比较有利于长作业SJF比较有利于短作业和优先级调度算法仅对某一类作业有利，相比之下，它能全面满足不同类型作业的需求，较好实现公平性与资源利用率之间的平衡。对交互型作业，由于通常较短，这些作业在第一队列规定的时间片内完成，可使用户感到满意；对短批作业，开始时在第一队列中执行一个时间片就可完成，便可与交互型作业一样获得快速晌应，否则通常也仅需在第二、第三队列中各执行一个时间片即可完成，其周转时间仍较短；对长批作业，它们依次在第一至第n个队列中轮番执行，不必担心长时间得不到处理。2.1 时间片轮转调度算法（RR）时间片轮转调度算法的基本思想是：对就绪队列中的每一进程分配一个时间片，时间片的长度q一般从10ms-1100ms不等。把就绪队列看成是一个环状结构，调度程序按时间片长度q轮流调度就绪队列中的每一进程，使每一进程都有机会获得相同长度的时间占用处理机运行。时间片轮转调度算法在分时系统中，是一种既简单又有效的调度策略。一个分时系统有许多终端。终端用户在各自的终端设备上同时使用计算机。如果某个终端用户的程序长时间地占用处理机，那么其他终端用户的请求就不能得到即时相应。一般说来，终端用户提出请求后，能在几秒钟内得到响应也就感到满意了。采用时间片轮转算法，可以使系统即时地相应各终端用户的请求。时间片轮转调度算法的性能极大的依赖于时间片长度q的取值，如果时间片过大。则RR算法就退化为FIFO算法了；反之，如果时间片过小，那么，处理机在各进程之间频繁转接，处理机时间开销变得很大，而提供给用户程序的时间将大大减少。2.2 短作业优先调度算法（SJF）根据估计运行时间的长短将各个进程排成一个队列（估计运行时间最短的进程放在对首）每次运行将对首进程投入运行，直道运行结束，将此进程连接到完成队列的队尾。然后，再将下一个对首投入运行，直到所有的进程都运行完毕。2.3 动态优先级调度算法进程的动态优先级一般根据以下原则确定：根据进程占用有CPU时间的长短来决定。根据就绪进程等待CPU的时间长短来决定。16第3章 系统总体设计3.1 系统功能设计 本系统实现了处理机调度。总体分为3个模块：时间片轮转法、短作业优先算法、动态优先级算法。如图3-1所示。处理机调度程序时间片轮转法短作业优先算法动态优先级算法图3-1 系统功能模块图3.2 时间片轮转法设计将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队列地对首进程并规定它的执行时间（称次时间为时间片）当时间片用完但并未执行时，剥夺该进程的执行将其连接到完成队列地对尾。然后在将下一个进程投入运行，直到所有的运行完毕。时间片轮转调度算法如图3-2所示。3.3 短作业优先算法设计短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。根据估计运行时间的长短将各个进程排成一个队列（估计运行时间最短的进程放在对首）每次运行将对首进程投入运行，直道运行结束，将此进程连接到完成队列的队尾。然后，再将下一个对首投入运行，直到所有的进程都运行完毕。3.4 动态优先级算法设计动态优先级在时间片轮转法基础上完成。将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队列地对首进程并规定它的执行时间（称次时间为时间片）当时间片用完但并未执行时，剥夺该进程的执行将其连接到完成队列地对尾。然后在将下一个进程投入运行，直到所有的运行完毕。每个进程的优先级为50-服务时间。数字越小优先级越高，数字越大优先级则越低。优先级随着等待时间的增长而增高（数字减小）。YN开始结束初始化PCB输入进程插到队列中队列为空分配时间片运行进程把进程插入队尾运行时间已达到所需的运行时间完成图3-2 时间片轮转法第4章 系统实现4.1 时间片轮转法实现将系统中所有的就绪进程按照FCFS原则，排成一个队列。然后轮流执行进程。执行过程如图4-1所示。图4-1 时间片轮转法时间片轮转法代码如下：typedef struct node char name20; /*进程的名字*/ int prio; /*进程的优先级*/ int round; /*分配CPU的时间片*/ int cputime; /*CPU执行时间*/ int needtime; /*进程执行所需要的时间*/ char state; /*进程的状态，W就绪态，R执行态，F完成态*/ int count; /*记录执行的次数*/ struct node *next; /*链表指针*/ PCB; PCB *ready=NULL,*run=NULL,*finish=NULL; void Clear()ready=NULL;run=NULL;finish=NULL;void GetFirst() /*取得第一个就绪队列节点*/ run = ready;if(ready!=NULL) run -state = R;ready = ready -next; run -next = NULL; void Output() /*输出队列信息*/ PCB *p;p = ready;printf(进程名t优先级t轮数tcpu时间t需要时间t进程状态t计数器n); while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; p = finish; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; p = run; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; void InsertPrio(PCB *in) /*创建优先级队列，规定优先数越小，优先级越低*/ PCB *fst,*nxt;fst = nxt = ready; if(ready = NULL)in-next = ready;ready = in; else if(in -prio = fst -prio)in-next = ready; ready = in; elsewhile(fst-next != NULL) nxt = fst;fst = fst-next; if(fst -next = NULL) in -next = fst -next;fst -next = in; else nxt = in; in -next = fst; void InsertTime(PCB *in) /*将进程插入到就绪队列尾部*/ PCB *fst;fst = ready; if(ready = NULL)in-next = ready;ready = in; elsewhile(fst-next != NULL) fst = fst-next;in -next = fst -next;fst -next = in; void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/ PCB *fst;fst = finish;if(finish = NULL)in-next = finish;finish = in; elsewhile(fst-next != NULL)fst = fst-next; in -next = fst -next;fst -next = in; void TimeCreate(int num) /*时间片输入函数*/ PCB *tmp;int i;printf(输入进程名字和进程时间片所需时间：n); for(i = 0;i name); getchar(); scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 0; tmp -round = 2; tmp -count = 0; InsertTime(tmp); void RoundRun() /*时间片轮转调度算法*/ int flag = 1;GetFirst(); while(run != NULL)Output(); while(flag)run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) run -state = F; InsertFinish(run); flag = 0; else if(run-count = run-round) run-state = W; run-count = 0; InsertTime(run); flag = 0; flag = 1; GetFirst(); 4.2 短作业优先算法实现短作业优先算法是对FCFS算法的改进，其目标是减少平均周转时间。该算法对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。执行过程如图4-2所示。图4-2 短作业优先短作业优先算法代码如下：struct sjfint jobnumber;float submittime;float runtime;float starttime;float finishtime;float waittime;float turnaroundtime;temp;static struct sjf stM;void input(struct sjf *p,int N)int i;printf(请输入进程名、到达时间、服务时间：n(例如：1 2 3)n);for(i=0;iN;i+)scanf(%d%f%f,&pi.jobnumber,&pi.submittime,&pi.runtime);void print(struct sjf *p,int N)int k;float h=0,g;printf(run order:);printf(%d,p0.jobnumber); for(k=1;k%d,pk.jobnumber); printf(nThe processs information:n); printf(njobnumtsubmittruntstarttfinaltwaittturnaroundn); for(k=0;kN;k+) h+=pk.turnaroundtime; printf(%dt%-.1ft%-.1ft%-.1ft%-.1ft%-.1ft%-.1ftn,pk.jobnumber,pk.submittime,pk.runtime,pk.starttime,pk.finishtime,pk.waittime,pk.turnaroundtime); g=h/N; printf(nThe average turnaround time is %-.2fn,g);/按提交时间从小到大排序void sort1(struct sjf *p,int N)int i,j;for(i=0;iN;i+)for(j=0;j=i;j+)if(pi.submittimepj.submittime)temp=pi;pi=pj;pj=temp;/运行void deal(struct sjf *p,int N)int k;for(k=0;kpk-1.finishtime)pk.starttime=pk.submittime;pk.finishtime=pk.submittime+pk.runtime;elsepk.starttime=pk-1.finishtime;pk.finishtime=pk-1.finishtime+pk.runtime;for(k=0;kN;k+)pk.turnaroundtime=pk.finishtime-pk.submittime; pk.waittime=pk.starttime-pk.submittime; void sort2(struct sjf *p,int N)int next,m,n,k,i;float min;sort1(p,N);for(m=0;mpm-1.finishtime)pm.finishtime=pm.submittime+pm.runtime;elsepm.finishtime=pm-1.finishtime+pm.runtime; for(n=m+1;nN;n+) if(pn.submittime=pm.finishtime) i+; min=pm+1.runtime; next=m+1; for(k=m+1;km+i;k+) if(pk+1.runtimemin)min=pk+1.runtime;next=k+1; temp=pm+1; pm+1=pnext; pnext=temp;deal(p,N);print(p,N); 4.3 动态优先级算法实现动态优先级算法中优先级根据进程占用有CPU时间的长短来决定，占用时间越长，优先级越低。优先级随等待时间增加而增长。执行过程如图4-3所示。图4-3 动态优先级动态优先级算法代码如下：void PrioCreate(int num) /*优先级调度输入函数*/ PCB *tmp; int i;printf(输入进程名字和进程所需时间：n); for(i = 0;i name); getchar(); scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 50 - tmp-needtime; tmp -round = 0; tmp -count = 0; InsertPrio(tmp); void Priority() /*按照优先级调度，每次执行一个时间片*/ int flag = 1;GetFirst();while(run != NULL) Output(); while(flag) run-prio -= 3; run-cputime+; run-needtime-; if(run-needtime = 0) run -state = F; run-count+; InsertFinish(run); flag = 0; else run-state = W; run-count+; InsertTime(run); flag = 0; flag = 1; GetFirst(); 第5章 系统使用说明本系统初步模拟了处理机调度的几种基本算法：时间片轮转法、短作业优先、动态优先级。时间片轮转法将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执