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

北华航天工业学院操作系统课程设计报告课程设计题目：处理机调度程序作者所在系部：计算机与遥感信息技术学院作者所在专业：网络工程作者所在班级：B12522作者姓名：梁爽作者学号：20124052204指导教师姓名：刘立媛完成时间：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 动态优先级算法设计 43.5 4 章系统实现 64.1 时间片轮转法实现 64.2 短作业优先算法实现 94.3 动态优先级算法实现 12第 5章系统使用说明 14第 6章课程设计总结 156.1 主要问题及解决办法 156.2 课程设计体会 156.3 自我评定 15参考文献 16第1章绪论在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资 源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运 行，以实现进程并发地执行。1.1 处理机调度功能一般情况下，当占用处理机的进程因为某种请求得不到满足而不得不放弃CPU!入等待状态时，或者当时间片到，系统不得不将 CP价配给就绪队列中另一进程的时候，都要 引起处理机调度。除此之外，进程正常结束、中断处理等也可能引起处理机的调度。因此， 处理机调度是操作系统核心的重要组成部分，它的主要功能如下：(1)记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存 器等现场信息，将这些信息记录在相应的进程控制块中。(2)根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间。(3)收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时 候，保存该进程的现场，并收回处理机。处理机调度的功能中，很重要的一项就是根据一定算法，从就绪队列中选出一个进程 占用CPU行。可见，算法是处理机调度的关键。1.2 处理机调度性能准则处理机调度，有许多不问的调度算法，不同的调度算法具有不同的特性。因此，在介 绍算法之前，先介绍衡量一个算法的基本准则。衡量和比较调度算法性能优劣主要有一下几个因素：(D CPU?用率。CPIM计算机系统中最重要的资源，所以应尽可能使 CPU呆持忙， 使这一资源利用率最高。(2)吞吐量。CPU!行时表示系统正处于工作状态，工作量的大小是以每单位时间所 完成的作业数目来描述的，这就叫吞吐量。(3)周转时间。指从作业提交到作业完成所经过的时间，包括作业等待，在就绪队列 中排队，在处理机上运行以及进行输入/输出操作所花时间的总和。(4)等待时间。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常简单的考察 等待时间。(5)响应时间。指从作业提交到系统作出响应所经过的时间。在交互式系统中，作业 的周转时间并不一定是最好的衡量准则，因此，常常使用另一种度量准则，即响应时间。 从用户观点看，响应时间应该快一点好，但这常常要牺牲系统资源利用率为代价。17第2章系统需求分析FCFS比较有利于长作业SJF比较有利于短作业和优先级调度算法仅对某一类作业有 利，相比之下，它能全面满足不同类型作业的需求，较好实现公平性与资源利用率之间的 平衡。对交互型作业，由于通常较短，这些作业在第一队列规定的时间片内完成，可使用 户感到满意；对短批作业，开始时在第一队列中执行一个时间片就可完成，便可与交互型 作业一样获得快速晌应，否则通常也仅需在第二、第三队列中各执行一个时间片即可完成, 其周转时间仍较短；对长批作业，它们依次在第一至第n个队列中轮番执行，不必担心长时间得不到处理。2.1 时间片轮转调度算法（RR）时间片轮转调度算法的基本思想是：对就绪队列中的每一进程分配一个时间片，时间 片的长度q一般从10ms-1100m小等。把就绪队列看成是一个环状结构，调度程序按时间 片长度q轮流调度就绪队列中的每一进程，使每一进程都有机会获得相同长度的时间占用 处理机运行。时间片轮转调度算法在分时系统中，是一种既简单又有效的调度策略。一个分时系统 有许多终端。终端用户在各自的终端设备上同时使用计算机。如果某个终端用户的程序长 时间地占用处理机，那么其他终端用户的请求就不能得到即时相应。一般说来，终端用户 提出请求后，能在几秒钟内得到响应也就感到满意了。采用时间片轮转算法，可以使系统 即时地相应各终端用户的请求。时间片轮转调度算法的性能极大的依赖于时间片长度q的取值，如果时间片过大。则RR算法就退化为FIFO算法了；反之，如果时间片过小，那么，处理机在各进程之间频繁 转接，处理机时间开销变得很大，而提供给用户程序的时间将大大减少。2.2 短作业优先调度算法（SJF）根据估计运行时间的长短将各个进程排成一个队列（估计运行时间最短的进程放在对 首）每次运行将对首进程投入运行，直道运行结束，将此进程连接到完成队列的队尾。然 后，再将下一个对首投入运行，直到所有的进程都运行完毕。2.3 动态优先级调度算法进程的动态优先级一般根据以下原则确定：根据进程占用有CPU寸间的长短来决定。根据就绪进程等待CPU勺时间长短来决定第3章系统总体设计3.1 系统功能设计本系统实现了处理机调度。总体分为3个模块：时间片轮转法、短作业优先算法、动态优先级算法。如图3-1所示。图3-1系统功能模块图3.2 时间片轮转法设计将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队列地对首进程 并规定它的执行时间(称次时间为时间片)当时间片用完但并未执行时，剥夺该进程的执 行将其连接到完成队列地对尾。然后在将下一个进程投入运行，直到所有的运行完毕。时间片轮转调度算法如图3-2所示。3.3 短作业优先算法设计短作业优先(SJF, Shortest Job First )又称为“短进程优先" SPN(Shortest Process Next);这是对FCFSB法的改进，其目标是减少平均周转时间。根据估计运行时间的长短将各个进程排成一个队列(估计运行时间最短的进程放在对 首)每次运行将对首进程投入运行，直道运行结束，将此进程连接到完成队列的队尾。然 后，再将下一个对首投入运行，直到所有的进程都运行完毕。3.4 动态优先级算法设计动态优先级在时间片轮转法基础上完成。将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队列地对首进程并规定它的执行时间（称次时间为时间片）当时间片用完但并未执行时，剥夺该进程的执 行将其连接到完成队列地对尾。然后在将下一个进程投入运行，直到所有的运行完毕。每个进程的优先级为50-服务时间。数字越小优先级越高，数字越大优先级则越低。优 先级随着等待时间的增长而增高（数字减小）。第4章系统实现4.1时间片轮转法实现将系统中所有的就绪进程按照 FCFS则，排成一个队列。然后轮流执行进程 执行过程如图4-1所示。EM所作系就课程逾计412fi1230De bug灿理机调度上xe -请萍算法,匚间H轮转 Fi作业优先工先来先服享匚碓优先藏工退出 （输入序号后按En快工键确认）1请输入进程总数：3输入进程名转口进程时间片所需间；1 32 43 1进程名优先级轮数tpufl寸间需要时间进程状态计数器20204邛00201W010203R0进程名优先级轮数卬L1B寸间需要时间进程状态计数器30201W010221W020204R0进程名优先线轮数cpuH寸间需要时间进程状至计数器10221W020222W030201 _R0进程名优先级轮数中止寸间需要时间进程状态计额器20222W0J0210F110221R0进程名优先缴轮数opuH寸间需要时间进程状态计数器30210F110230F120222R0请选择算法：1.时间片轮转2.短作业优先工先来先服务.动态优先期0.退出 （输入点号后按Enter键蠲认）掏狗拼音输入法皂:图4-1时间片轮转法时间片轮转法代码如下: typedef struct node char name20; /*int prio; /* int round; /* int cputime; /*CPU int needtime; /* char state; /* int count; /* struct node *next; /*进程的名字*/进程的优先级*/分配CPU的时间片*/执行时间*/进程执行所需要的时间*/ 进程的斗犬态,W-就绪态, 记录执行的次数*/链表指针*/R执彳T态，F一完成态*/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 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 =else while(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;计数器 n");*/in; void InsertTime(PCB *in) /* PCB *fst;将进程插入到就绪队列尾部 */fst = ready;if(ready = NULL) elsein->next = ready;ready = in; while(fst->next != NULL) in ->next = fst ->next; fst ->next = in;void InsertFinish(PCB *in) /* PCB *fst;fst = finish;if(finish = NULL)in->next = finish; else while(fst->next != NULL) in ->next = fst ->next; fst ->next = in; fst = fst->next;将进程插入到完成队列尾部 */finish = in;fst = fst->next;时间片输入函数*/void TimeCreate(int num) /* PCB *tmp;int i;printf(" 输入进程名字和进程时间片所需时间： n");for(i = 0;i < num; i+) if(tmp = (PCB *)malloc(sizeof(PCB)=NULL) perror("malloc");exit(1);scanf("%s",tmp->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短作业优先算法实现短作业优先算法是对FCFST法的改进，其目标是减少平均周转时间。该算法对预计执 行时间短的作业(进程)优先分派处理机。通常后来的短作业不抢先正在执行的作业。执行过程如图4-2所示。E:3所作系统课程设计2014年12月2孙Debug恢理机调度方史请选搽算法,L时间片轮转2随作业优先(输入序号后按Ent,键确认)2话输入作业总数：3话输入进程容、到达时间.服务时间：岬棚：1 2 3)1 2 32 3 3 12run otrder ：3>1>2The process1 5 infcrmation：3.先来先服冢 丸初态优先级0.退出iobnum 3submit1,0run 2.0start 1,0final3.0wait 0.0turnaLround2.012.03.03.00.01.04.023.04.0e.o10.03.07.0The average turnaitrund time ip 4.33请选择算法：L时间片轮转短作业优先工先来先服务就动态优先线0.退出 (输入序号后按EnK工链豳认)撞狗拼音$跌去全：图4-2短作业优先短作业优先算法代码如下:struct sjf int 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;i<N;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<N;k+)printf("->%d",pk.jobnumber);printf("nThe processs information:n");printf("njobnumtsubmittruntstarttfinaltwaittturnaroundn");for(k=0;k<N;k+) h+=pk.turnaroundtime;printf("%dt%-.1ft%-.1ft%-.1ft%-.1ft%-.1ft%-.1ftn",pk.jobnumbe r,pk.submittime,pk.runtime,pk.starttime,pk.finishtime,pk.waittim e,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;i<N;i+)for(j=0;j<=i;j+) if(pi.submittime<pj.submittime) temp=pi;pi=pj;pj=temp;/ 运行void deal(struct sjf *p,int N) int k;for(k=0;k<N;k+)if(k=0) pk.starttime=pk.submittime;pk.finishtime=pk.submittime+pk.runtime;else if(pk.submittime>pk-1.finishtime) pk.starttime=pk.submittime;pk.finishtime=pk.submittime+pk.runtime;else pk.starttime=pk-1.finishtime;pk.finishtime=pk-1.finishtime+pk.runtime;for(k=0;k<N;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;m<N;m+) i=0;if(m=0) pm.finishtime=pm.submittime+pm.runtime;elseif(pm.submittime>pm-1.finishtime) pm.finishtime=pm.submittime+pm.runtime;elsepm.finishtime=pm-1.finishtime+pm.runtime;for(n=m+1;n<N;n+) if(pn.submittime<=pm.finishtime)i+;min=pm+1.runtime;next=m+1;for(k=m+1;k<m+i;k+) if(pk+1.runtime<min)min=pk+1.runtime; next=k+1; temp=pm+1;pm+1=pnext; pnext=temp;deal(p,N);print(p,N);5 .3动态优先级算法实现动态优先级算法中优先级根据进程占用有 CPU寸间的长短来决定，占用时间越长，优 先级越低。优先级随等待时间增加而增长。执行过程如图4-3所示。t :!作系就课程设计2014年12月11230也日尻1口、处理叽调票8（号 一 口 1X请选搔算法：L时间片轮转2,矩作业优先3.先来先服务，动态优先税0.退田 （输入序片后按Ent,迪确认）4请输入进程总数：3输入进程定转进程所需时间，1 1A2 23 4进程名优九及粒数皿加寸间需要时间进程状态计数器24S002见03朝。U4w0149001R0进程名优非及轮数卬笳寸间需要时间进程状态计数器3笆。4W01始010F1248002R0进程名优先皴轮数印证寸间需要时间进程状态计数器245011w11嵌010F1340004R0进程名优先缀轮数寸间需要时间进程状态H粒署343013W114&010F1245011R1进程名优先级轮数cpu时间需要时间进程状态计数器1钝010F1242020F2343。13R1进程名优先级轮数年试寸间需要时间进程状态计数器14G010F124202clF2340022R2进程名优九及轮数切拉寸间需要时间进程状态计数器14G010F1242020F2337031R3珀 1芯珏耳& 曰 L 口 |曰卜轮;3与 上丸tl PJLIAi/口uJqxj LnR/j ，取JiJ几i人潮i U- J2lJ-I（输入序号同施确认）授狗拼音输入法全：V图4-3动态优先级动态优先级算法代码如下：void PrioCreate(int num) /*优先级调度输入函数*/ PCB *tmp;int i;printf(" 输入进程名字和进程所需时间： n");for(i = 0;i < num; i+) if(tmp = (PCB *)malloc(sizeof(PCB)=NULL) perror("malloc");exit(1); scanf("%s",tmp->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派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百m&在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。短作业优先比FCF改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量。缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。动态优先级算法中优先级根据进程占用有CPU寸间的长短来决定，占用时间越长，优先级越低。优先级随等待时间增加而增长。第 6 章 课程设计总结6.1 主要问题及解决办法本次课设在优先级算法上遇到了一些问题，后来通过查阅书籍以及一些专业网站，将优先级依照进程服务时间来设定，服务时间短则优先极高，服务时间长则优先级低。优先级根据等待时间增长而增长。6.2 课程设计体会模拟操作系统处理机调度算法， 最重要的是算法的逻辑， 只有逻辑清晰才能写出合理的算法，使程序简洁明了。一个系统需要简便的界面，良好的程序风格，还有尽量用简单的代码代替相同功能的复杂代码，增强程序可读性。还有，编写代码过程中，需要对代码进行必要的注释。尽量实现代码功能模块化。6.3 自我评定在完成处理机调度算法的实现过程中， 我们遇到了一些问题， 比如怎样运用循环队列，如何设计结构体等等，也积极配合并思考进行解决。整体来说，我们的算法虽然实现了体现进程动态运行变化的过程，但是相对而言比较简单。实验中，我们小组不断讨论对算法进行优化，使得运行结果看起来更容易理解，也达到了处理机调度的功能。做实验让我们对于时间片轮转的思想理解的更加透彻，巩固了理论知识的学习。参考文献1 孟庆昌 .操作系统教程.北京：电子工业出版社， 20042 陈向群，杨芙清.操作系统教程.2 版.北京：北京大学出版社，20063 Gary Nutt 著.操作系统现代观点.晏益慧，译.北京：机械工业出版社， 20044 屠祁，屠立德，等.操作系统基础.3版。北京：清华大学出版社， 20005 哲凤屏，汤子瀛，杨成忠 .计算机操作系统.台湾：儒林图书公司，1994指 导 教 师 评 语 及 设 计 成 绩评 语课程设计成绩：指导教师：日期：年 月一日