操作系统课程设计-优先数调度算法的实现.docx

衡阳师范学院工科课程设计 -操作系统课程设计报告题 目： 优先数调度算法的实现 学 号： 姓 名： 班 级： 14级物联网班 指导教师： 日 期： 2016年 12月 25 目录1.概述21.1设计目的21.2运行环境31.3任务分配32.需求分析42.2题目内容42.2设计思想说明42.3数据结构设计63.算法的设计73.1头文件声明73.2定义各种变量73.3相关函数的定义73.4程序运行流程图103.5方案设计流程图113.6进程控制块PCB结构123.7进程控制块链结构124.实例135.总结146.附录16参考文献241.概述1.1设计目的 在操作系统中调度算法的实质是一种资源的分配，因而调度算法是指“根据系统资源分配策略所规定的资源分配算法”。对于不同的操作系统和系统目标，通常采用不同的调度算法。为了照顾紧迫作业，使之在进入系统后便获得优先处理，引入了最高优先权调度算法。作为进程调度算法时，该算法是把处理机分配给就绪队列优先权最高的进程。这可以分为抢占式优先权算法和非抢占式优先权算法。对于最高优先权调度算法，其关键在于：它是使用静态优先权还是动态优先权，以及如何确定进程的优先权。动态优先权拥有其特有的灵活优点，同时，若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同优先权初值，那么，对于优先权初值低的进程，在等待了足够长的时间后，其优先权便可能升为最高，从而获得处理机。当采用抢占式优先权调度算法时，如果规定当前进程的优先权以一定速率下降，则可防止一个长作业长期垄断处理机。1.2运行环境硬件机器：pc计算机语言：C+（使用自己学习的）编译环境：visual studio 20101.3任务分配 1）理解掌握进程调度实现所涉及到的主要问题：如何组织进程、如何实现处理机调度。进程控制块的作用和结构，进程控制块的链表组织。进程调度程序包含从进程就绪队列选择并摘取进程、给该进程分配处理机。2）设计进程控制块相关数据结构，进程状态跃迁的相关模拟；3）实现优先调度算法模拟程序设计、编码及调试。2.需求分析2.2题目内容编写程序，采用优先权调度算法实现单处理机系统对进程的调度过程。2.2设计思想说明模拟动态优先权算法，在主函数中选择采用抢占式进程调度算法，再调用优先调度算法完成模拟。1.设定系统中有五个进程，每一个进程用一个进程控制块（PCB）表示，队列的每一个结点都是一种结构体，结构体名称定义为进程模块。2.进程控制块包含如下信息：进程编号、需要运行时间、已用CPU时间等等。3.在每次运行设计的处理调度程序之前，由终端输入五个进程的“进入就绪队列时间”和“要求运行时间”。4.进程的进入就绪队列时间及需要的运行时间人为地指定.进程的运行时间以时间片为单位进行计算。5.将五个进程按给定进程的时间片从小到大连成就绪队列，当第一个进程进去的时候，它就执行当前进程，在执行的过程中，可能有另一个进程进入，进入之后，当前的进程就会进行更新，更新它所有的信息，就把它放入运行队列，使当前运行的剩余时间为零，为零之后就把当前的资源释放掉，这时候就从就绪队列里面取出进程的队头，作为当前运行的进程。寻找的过程中，采用的是队列的遍历，每遍历一个进程的时候，就对当前进程的剩余时间进行更新并记录这个队头。6.处理机调度总是选队列首进程运行。进程每运行一次剩余时间减“1”，同时将已运行时间加“1”。7.进程运行一次后，若要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。8.“就绪”状态的进程队列不为空，则重复上面6，7步骤，直到所有进程都成为“结束”状态。9.在设计的程序中有输入语句，输入5个进程的“进入就绪队列时间”和“要求运行时间”，也有显示或打印语句，能显示或打印进程的平均等待时间和平均周转时间。10.最后，为五个进程任意确定一组“进入就绪队列时间”和“要求运行时间”，运行并调试所设计的程序，显示或打印出逐次被选中进程的进程序号。2.3数据结构设计设定系统中有五个进程，每一个进程用一个进程控制块（PCB）表示，队列的每一个结点都是一种结构体，结构体名称定义为进程模块。建立好进程控制模块之后，进程就已按时间片从小到大的顺序排成了就绪队列。typedef struct nodechar name10; /进程标志符int prio; /进程优先数int cputime; /进程占用cpu时间int needtime; /进程到完成还要的时间char state; /进程的状态struct node *next; /链指针PCB;3.算法的设计3.1头文件声明#include/*标准io库*/#include/*该文件包含了C语言标准库函数的定义*/#include/*一种常用的编译预处理指令，在使用到字符数组时需要使用*/3.2定义各种变量char name10; /进程标志符int prio; /进程优先数int cputime; /进程占用cpu时间int needtime; /进程到完成还要的时间char state; /进程的状态struct node *next; /链指针3.3相关函数的定义/优先数的算法插入算法void insert1(PCB *q)PCB *p1,*s,*r;int b;s=q; /待插入的PCB指针p1=ready; /就绪队列头指针r=p1; /r做p1的前驱指针b=1;while(p1!=NULL)&b) /根据优先数确定插入位置if(p1-prio=s-prio)r=p1;p1=p1-next;elseb=0;if(r!=p1) /如果条件成立说明插入在r与p1之间r-next=s;s-next=p1;elses-next=p1; /否则插入在就绪队列的头ready=s;/优先数调度算法void priority(char alg)while(run!=NULL) /当运行队列不空时，有进程正在运行run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-prio=run-prio-3; /每运行一次优先数降低3个单位if(run-needtime=0) /如所需时间为0将其插入完成队列run-next=finish;finish=run;run-state=F; /置状态为完成态run=NULL; /运行队列头指针为空if(ready!=NULL) /如就绪队列不空firstin(); /将就绪队列的第一个进程投入运行else /没有运行完同时优先数不是最大，则将其变为/就绪态插入到就绪队列if(ready!=NULL)&(run-prioprio)run-state=W;insert1(run);firstin(); /将就绪队列的第一个进程投入运行prt(alg); /输出进程PCB信息3.4程序运行流程图图3-13.5方案设计流程图4图3-23.6进程控制块PCB结构进程ID链指针优先数占用CPU时间片数进程所需时间片数进程状态图3-33.7进程控制块链结构图3-44.实例图4-1图4-25.总结这次的程序软件基本上运行成功，这次数据结构课程设计让我感触很深，使我了解到的学习不应该只局限于课本，因为课本上只是很有限的一部分，所涉及的面也是狭窄的。但是怎样在有限的范围内学习到无限的知识呢？那就要懂得自学，懂得充分利用身边的资源。应该说，在这次的课程设计中学到了很多知识，这并不仅仅包括书本上的知识，更重要的是学会了如何去和别人交流，怎样用语言去实现自己的想法，在这个过程中使我懂得了勤学好问的重要性。虽然在我的程序中有一部分是从网上搜索得来的，但我竭力将所获得的信息变成自己的资源。在我动手上机操作的同时，我在了解和看懂的基础上有所改变和创新，但是在我的程序软件中还有部分的不足，需要加以更新。同时，通过这次课程设计，意识到了自己动手实践的弱势，特别是在编程方面，于是我知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。相信通过这次的课程设计，更让我深刻意识到学习中的弱点，同时也找到了克服这些弱点的方法，这也是一笔很大的资源。在以后的时间中，我应该利用更多的时间去上机实验，多编写程序，相信不久后我的编程能力都会有很大的提高。经过这次课程设计，通过对程序的编制，调试和运行，使我熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。这次操作系统的程序设计，对于我来说是一个挑战。我对操作系统的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。6.附录#include#include#includetypedef struct nodechar name10; /进程标志符int prio; /进程优先数int cputime; /进程占用cpu时间int needtime; /进程到完成还要的时间char state; /进程的状态struct node *next; /链指针PCB;PCB *finish,*ready,*tail,*run; /队列指针int N; /进程数/将就绪队列的第一个进程投入运行void firstin()run=ready; /就绪队列头指针赋值给运行头指针run-state=R; /进程状态变为运行态ready=ready-next; /就绪列头指针后移到下一进程/标题输出函数void prt1(char a)printf(进程号 cpu时间 所需时间 优先数 状态n);/进程PCB输出void prt2(char a,PCB *q) /优先数算法输出printf( % -10s% -10d% -10d% -10d %cn,q-name,q-cputime,q-needtime,q-prio,q-state);/输出函数void prt(char algo)PCB *p;prt1(algo); /输出标题if(run!=NULL) /如果运行标题指针不空prt2(algo,run); /输出当前正在运行的PCBp=ready; /输出就绪队列PCBwhile(p!=NULL)prt2(algo,p);p=p-next;p=finish; /输出完成队列的PCBwhile(p!=NULL)prt2(algo,p);p=p-next;getchar(); /按任意键继续/优先数的算法插入算法void insert1(PCB *q)PCB *p1,*s,*r;int b;s=q; /待插入的PCB指针p1=ready; /就绪队列头指针r=p1; /r做p1的前驱指针b=1;while(p1!=NULL)&b) /根据优先数确定插入位置if(p1-prio=s-prio)r=p1;p1=p1-next;elseb=0;if(r!=p1) /如果条件成立说明插入在r与p1之间r-next=s;s-next=p1;elses-next=p1; /否则插入在就绪队列的头ready=s;/优先数创建初始PCB信息void create1(char alg)PCB *p;int i,time;char na10;ready=NULL; /就绪队列头文件finish=NULL; /完成队列头文件run=NULL; /运行队列头文件printf(输入进程号和运行时间：n); /输入进程标志和所需时间创建PCBfor(i=1;iname,na);p-cputime=0;p-needtime=time;p-state=w;p-prio=50-time;if(ready!=NULL) /就绪队列不空，调用插入函数插入insert1(p);elsep-next=ready; /创建就绪队列的第一个PCBready=p;/clrscr();printf( 优先数算法输出信息：n);printf(*n);prt(alg); /输出进程PCB信息run=ready; /将就绪队列的第一个进程投入运行ready=ready-next;run-state=R;/优先数调度算法void priority(char alg)while(run!=NULL) /当运行队列不空时，有进程正在运行run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-prio=run-prio-3; /每运行一次优先数降低3个单位if(run-needtime=0) /如所需时间为0将其插入完成队列run-next=finish;finish=run;run-state=F; /置状态为完成态run=NULL; /运行队列头指针为空if(ready!=NULL) /如就绪队列不空firstin(); /将就绪队列的第一个进程投入运行else /没有运行完同时优先数不是最大，则将其变为/就绪态插入到就绪队列if(ready!=NULL)&(run-prioprio)run-state=W;insert1(run);firstin(); /将就绪队列的第一个进程投入运行prt(alg); /输出进程PCB信息/主函数int main()char algo; /算法标记/clrscr();printf(输入进程数：n);scan