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

第第二十页目录TOC\o"1-3"\u目录 11．设计题目与要求 21.1设计目的 21.2设计要求 22．总体设计思想 22.1总体设计思想 23．功能设计 43.1数据结构设计 43.2程序清单 43.3运行结果 74.设计心得 95.参考资料 9附录 10程序源代码： 10一．设计题目与要求课题：理机调度模拟程序：选择一个调度算法，实现处理机调度。1.设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。2.设计要求：1）进程调度算法包括：时间片轮转法，短作业优先算法，最高响应比优先算法。2）可选择进程数量3）本程序包括三种算法，可用C语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数及每个进程的运行时间，每个进程的优先数由随机函数产生且优先数随等待时间而变化，执行，显示结果。二．总体设计思想(1)进程的创建：由系统为某个进程设置一个进程控制块PCB，用于对进程进行控制和管理。进程任务完成，由系统收回其PCB，该进程便消亡。(2)进程的三种状态：运行、就绪、完成。进程的三种状态可以通过设计三个链队列来实现：finish为完成队列的头指针，ready为就绪队列的头指针，tail为循环轮转法队列的尾指针。因为每一时刻，CPU只能运行一个进程，所以运行队列只有一个run指针指向当前运行进程。(3)进程调度的功能：按照一定的策略从就绪队列的多个进程中选取一个进程，使其获得CPU而运行。①动态优先数调度算法：思想：为每一个进程设一个优先数，它总是把处理机给就绪队列中具有最高优先级的进程。初始的进程优先数是随机产生的，随着进程的运行对优先数进行调整，每次运行时都是从就绪队列中选取优先数最大的进程运行，所以将就绪队列按照优先数的大小从高到低排序，这样，每次取对首进程即可。将进程按优先数的大小排列在就绪队列中，每次选取就绪队列中优先权最高的进程首先占用处理机。优先数由随机函数产生进程最初的优先数。优先数的动态变化：进程每执行一次优先数-1。优先数随着进程的执行进行调整，每次执行时都从就绪队列中选取优先数最大的进程投入运行。②时间片轮转调度算法：思想：将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队列的队首进程，并规定它的执行时间（称此时间为时间片），当时间片用完但并未执行结束时，剥夺该进程的执行，将其链接到就绪队列的队尾，等待下一次的选择。将就绪队列的队首指针投入运行。③短作业优先调度算法（不可剥夺式的）思想：根据估计运行时间的长短，将各个进程排成一个就绪队列（估计运行时间最短的进程排在队首），每次运行将队首进程投入运行，直到运行结束，将此进程连接到完成队列的队尾。然后，再将下一个队首进程投入运行，直到所有的进程都运行完毕。三．功能设计1.数据结构设计PCB结构体：typedefstructnode{charname[10];/*进程时间轮转时间片*/intpid;/*进程的标号*/intprio;/*优先级*/intround;/*时间片*/intcputime;/*进程占用cpu的时间*/intruntime;/*进程运行所用的时间*/intwaittime;/*进程的等待时间*/intlength;/*进程的长度*/intcount;/*计数器*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB ;PCB结构体用于标识进程的创建与撤消。链指针：PCB*finish,*ready,*tail,*run;.Finish：完成队列的首指针，用于标识完成队列；Ready：就绪队列的首指针，用于标识就绪队列；；Run：运行队列的首指针，用于标识运行队列；；Tail：循环轮转队列的尾指针；2.程序清单（1）Create1（），create2（），create3（）分别为创建进程的函数Create1（）：按照优先级调度算法创建进程，用户输入进程名及进程所需的时间后，创建每个进程的PCB，将每个进程的PCB调用函数insert1（）按照优先数从高到低排列到就绪队列中。create2（）：按照时间片调度算法创建进程，用户输入进程名及进程所需的时间后，创建每个进程的PCB，将每个进程的PCB调用函数insert2（）将每个进程PCB按照输入的先后顺序插入到就绪队列的末尾。create3（）：按照短作业优先调度算法创建进程，用户输入进程名及进程所需的时间后，创建每个进程的PCB，将每个进程的PCB调用函数insert3（）：按照作业估计执行时间的长短从高到低排列到就绪队列中。就绪队列创建好后，将队列当中的第一个PCB变为运行态“R”，将run指针指向它，ready指针后移，作为就绪队列的新头指针，然后调用调度算法。注意每个时刻只能有一个进程处于运行态。（2）insert1（），insert2（），insert3（）分别为插入函数这三个函数完成的是就绪队列的创建和管理。①insert1（）的功能是将未完成且优先数小于其它进程的PCB按进程优先数的顺序插入到就绪队列中去。②insert2（）的功能是将执行了一个时间片且还未完成的进程的PCB插入到就绪队列的队尾。③insert3（）的功能是将未完成且作业的执行时间小于其它进程的PCB按进程的作业的执行时间的长短插入到就绪队列中去。（3）priority（）优先数调度算法①假定系统有三个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：typedefstructnode{intpid;/*进程的标号*/intprio;/*优先级*/intcputime;/*进程占用cpu的时间*/intruntime;/*进程运行所用的时间*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB;（4）roundrun（）时间片轮转法调度算法①假定系统有三个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：进程名，进程占用cpu的时间，进程到完成还需的时间，时间片，计数器，状态进程名——作为进程的标识，假设三个进程的进程名分别是p1，p2，p3。时间片——时间片轮转循环所需的时间总数。计数器——对进程执行时间进行计数。进程占用cpu的时间——假设进程已经运行的单位时间数，初始值为“0”。状态——有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进程的初始状态都为“就绪”，用“w”表示，当一个进程运行结束后，它的状态为“完成”，用“F”表示，当一个进程正在占用cpu时，它的状态为“运行”状态。②每次运行所设计的时间片轮转调度程序之前，为每个进程任意确定它的“要求运行时间”。③把三个进程按先来先服务的顺序排成循环队列，用指针指出队列连接情况。时间片轮转调度总是选择ready指针指示的进程运行。而是执行：进程到完成还需的时间－1进程占用cpu的时间+1计数器+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。（5）shortjob（）短作业优先法调度算法 ①假定系统有三个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名，进程占用cpu的时间，进程到完成还需的时间，状态进程名——作为进程的标识，假设三个进程的进程名分别为P1，P2，P3。进程占用cpu的时间——假设进程已经运行的单位时间数，初始值为“0”。状态——有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进程的初始状态都为“就绪”，用“w”表示，当一个进程运行结束后，它的状态为“完成”，用“F”表示，当一个进程正在占用cpu时，它的状态为“运行”状态。②在每次运行所设计的短作业优先调度程序之前，为每个进程任意确定它的“要求运行时间”。③为了调度方便，把三个进程按任意给定的作业长短进行排序。用一单元指出队首进程，用指针指出队列的连接情况。每次取对首进程即可。④短作业调度总是选队首进程运行。进程每运行一次，要求运行时间-1进程占用cpu的时间+1来模拟进程的一次运行。⑤进程运行一次后，若要求运行时间〉0，则再将它插入就绪队列（按作业长短插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“完成”（F），且退出队列。⑥若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“完成”状态。⑦在设计的程序中有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化及状态。⑧为三个进程随机确定“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。（6）界面设计：主界面：选择调度算法；子界面：输入进程数，进程名及进程所需的时间；利用c语言中的画图函数及清屏函数设计界面。3．运行结果主界面设计：（1,2,3算法4退出）算法1：动态优先级算法算法2：时间片轮转法算法3：短作业优先法四．心得体会及总结：处理机调度问题实际上是处理机分配问题。只有那些参与竞争处理机所必须的资源都已得到满足的进程才能享受竞争处理机的资格，这时它们处于内存就绪状态。这些必须的资源包括内存、外设及有关数据结构等。作业调度程序必须先调用存储管理、外设管理，分配资源，让它们能有竞争资格。为了提高资源利用率，一部分在内存中处于就绪、等待状态而短期内不能执行进程、作业换出内存，所以外存中除了处于后备状态的作业，还有处于就绪状态的作业。这就需要一定的方法和策略来为这部分作业分配空间。学习完《操作系统原理》课程后，进行的这次全面的综合训练，通过课程设计，使我更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力，并与编程相结合应用于实际中。参考资料[1]宗大华，宗涛，陈吉人著操作系统北京：人民邮电出版社，2009[2]李爱华，程磊著面相对象程序设计（C++语言）北京:清华大学出版社，2010[3]宋晓宇，windows操作系统核心编程实验教程中国铁道出版社[4]张丽芬刘利雄王金玉编著操作系统实验教程清华大学出版社附录：程序源代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>typedefstructnode{charname[10];intprio;intround;intcputime;intneedtime;intcount;charstate;structnode*next;}PCB;PCB*finish,*ready,*tail,*run;intN;firstin(){run=ready;run->state='R';ready=ready->next;}inttimesj(void){inti,xt;time_tt;srand((unsigned)time(&t));xt=rand()%10+1;returnxt;}voidprt1(chara){if(toupper(a)=='1')printf("namecputimeneedtimeprioritystate\n");elseif(toupper(a)=='2')printf("namecputimeneedtimeprioritystate\n");elseprintf("namecputimeneedtimeprioritystate\n");}voidprt2(chara,PCB*q){if(toupper(a)=='1')printf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);elseif(toupper(a)=='2')printf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);elseprintf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);}voidprt(charalgo){PCB*p;prt1(algo);if(run!=NULL)prt2(algo,run);p=ready;while(p!=NULL){prt2(algo,p);p=p->next;}p=finish;while(p!=NULL){prt2(algo,p);p=p->next;}getch();return;}insert1(PCB*q){PCB*p1,*s,*r;intb;s=q;p1=ready;r=p1;b=1;while((p1!=NULL)&&b)if(p1->prio>=s->prio){r=p1;p1=p1->next;}elseb=0;if(r!=p1){r->next=s;s->next=p1;}else{s->next=p1;ready=s;}}insert2(PCB*p2){tail->next=p2;tail=p2;p2->next=NULL;}insert3(PCB*q){PCB*p1,*s,*r;intb;s=q;p1=ready;r=p1;b=1;while((p1!=NULL)&&b)if(p1->needtime<=s->needtime){r=p1;p1=p1->next;}elseb=0;if(r!=p1){r->next=s;s->next=p1;}else{s->next=p1;ready=s;}}voidcreate1(charalg){PCB*p;inti,time,sjt,priost;charna[10];ready=NULL;finish=NULL;run=NULL;printf("Enternameandtimeofprocess\n");printf("\n");for(i=1;i<=N;i++){p=malloc(sizeof(PCB));printf("Entername%d",i);printf(":");scanf("%s",na);printf("Randomtime%d",i);printf(":");sjt=timesj();printf("%d\n",sjt);printf("Randompriority%d",i);printf(":");printf("%d\n",20-sjt);strcpy(p->name,na);p->cputime=0;p->needtime=sjt;p->state='w';p->prio=20-sjt;if(ready!=NULL)insert1(p);else{p->next=ready;ready=p;}}printf("DisplayProcessOfPriority:\n");printf("\n");prt(alg);run=ready;ready=ready->next;run->state='R';}voidcreate2(charalg){PCB*p;inti,time,sjt;charna[10];ready=NULL;finish=NULL;run=NULL;printf("Enternameandtimeofroundprocess\n");printf("\n");for(i=1;i<=N;i++){p=malloc(sizeof(PCB));printf("Entername%d",i);printf(":");scanf("%s",na);printf("Randomtime%d",i);printf(":");sjt=timesj();printf("%d\n",sjt);printf("Randompriority%d",i);printf(":");printf("%d\n",20-sjt);strcpy(p->name,na);p->cputime=0;p->needtime=sjt;p->round=1;p->state='w';p->count=0;p->prio=20-sjt;if(ready!=NULL)insert2(p);else{p->next=ready;ready=p;tail=p;}}printf("DisplayProcessOfRoundrobin\n");printf("\n");prt(alg);run=ready;ready=ready->next;run->state='R';}voidcreate3(charalg){PCB*p;inti,time,sjt;charna[10];ready=NULL;finish=NULL;run=NULL;printf("Enternameandtimeofprocess\n");printf("\n");for(i=1;i<=N;i++){p=malloc(sizeof(PCB));printf("Entername%d",i);printf(":");scanf("%s",na);printf("Randomtime%d",i);printf(":");sjt=timesj();printf("%d\n",sjt);printf("Randompriority%d",i);printf(":");printf("%d\n",20-sjt);strcpy(p->name,na);p->cputime=0;p->needtime=sjt;p->state='w';p->prio=20-sjt;if(ready!=NULL)insert1(p);else{p->next=ready;ready=p;}}printf("DisplayProcessOfPriority:\n");printf("\n");prt(alg);run=ready;ready=ready->next;run->state='R';}priority(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->prio=run->prio-1;if(run->needtime==0){run->next=finish;finish=run;run->state='C';run=NULL;if(ready!=NULL)firstin();}elseif((ready!=NULL)&&(run->prio<ready->prio)){run->state='W';insert1(run);firstin();}prt(alg);}}roundrun(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->count=run->count+1;run->prio=run->prio-1;if(run->needtime==0){run->next=finish;finish=run;run->state='C';run=NULL;if(ready!=NULL)firstin();}elseif(run->count==run->round){run->count=0;if(ready!=NULL){run->state='W';insert2(run);firstin();}}prt(alg);}}shorttask(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->prio=run->prio-1;if(run->needtime==0){run->next=finish;finish=run;run->state='C';run=NULL;if(ready!=NULL)firstin();}elseif((ready!=NULL)&&(run->needtime>ready->needtime)){run->state='W';insert1(run);firstin();}prt(alg);}return;}menu(){charalgo;printf("\n\nCOMPUTEROSWORK\n\n");printf("\n\nBywanghao(Class2)\n\n\n");printf("chooseoneoffollowing:\n");printf("\n1.PRIORITY.\n\n");printf("2.ROUNDROBIN.\n\n");printf("3.SHORTTASK.\n\n");printf("4.EXIT.\n\n\n");printf("\npleaseenteryourchoice:");scanf("%c",&algo);if(algo=='1'){printf("Enterprocessnumber\n");scanf("%d",&N);create1(algo);priority(algo);}elseif(algo=='2'){printf("Enterprocessnumber\n");scanf("%d",&N);create2(algo);roundrun(algo);}elseif(algo=='3'){printf("Enterprocessnumber\n");scanf("%d",&N);create3(algo);shorttask(algo);return;}elseif(algo=='4')exit(0);}main(){while(1){menu();}}毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名：日期：

学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名： 日期：年月日导师签名：日期：年月日

注意事项1.设计（论文）的内容包括：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键词5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4.文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写