1、进程调度算法的模拟实现课程设计报告课程名称：操作系统信息工程学院题目： 进程调度算法的模拟实现 一、设计目的本课程设计是学习完“计算机操作系统”课程后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。本课程设计是在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。二、设计内容（1）概述选择一个调度算法，实现处理机
2、调度。设计要求：1）进程调度算法包括：先来先服务算法，时间片轮转算法，短进程优先算法，动态优先级算法。2）可选择进程数量3）本程序包括四种算法，用C或C+语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。（2）设计原理（1）先来先服务算法 FCFS 每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列。（2）时间片轮转法 RR 系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几
3、ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。(3) 短进程优先算法 SPF短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 （4A）动态优先级算法 优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的
4、，以便获得更好的调度性能。 设计思想 首先开辟一个链表空间存放输入的原始作业的数据；然后设计的四种算法分别开辟四个链表空间，以实现不改变输入作业的原始数据就可以同时进行四种算法的调用，以对比四种算法的优劣性。 设计中所包括的函数有：void input();/输入生成HEAD链表函数，用于存放输入作业的所有信息void connect();/连接结点函数void myprintf();/打印我的界面void printftable();/打印作业状态void sortFCFS();/先来先服务复制HEAD并形成先来先服务的headFCFS链表void sortSJF();/短作业优先复制HEA
5、D并形成短作业优先链表headSJFvoid sortHRN();/高响应比函数，包括了执行void sortSUPER();/高优先权函数复制HEAD形成headSUPER链表void choose();/功能及算法选择函数void execute(JCB*p);/执行函数void copynode(JCB*p1,JCB*p2);/复制结点函数void printffinish(JCB*p);/打印一个作业完成时的周转时间等统计 JCB *delenode(JCB *ph,JCB *P);/ 删除并返回结点，用于高响应比算法Void printfall();/打印用过四种算法的周转时间和带权
6、周转时间Void destroy(JCB*P);/销毁函数，释放空间实现重新输入作业（3）详细设计及编码算法使用流程图 1.先来先服务算法对于先到达的进程优先分配CPU，按照先来先服务的原则依次执行各进程。算法： void FCFS() Node *p=head-next; while(p!=NULL) cout执行进程endldata.ID; p=p-next; coutendl; cout所有进程都执行完成next!=NULL) pmin=head2-next; for(p=head2-next;p!=NULL;p=p-next) if(pmin-data.ALLTimep-data.AL
7、LTime) pmin=p; cout执行剩余区间长度最短的进程endldata.ID; for(p=head2;p!=NULL;p=p-next) if(p-next=pmin) p-next=p-next-next; free(pmin); printf(n); printf(所有进程都执行完成。nn); 3，时间片轮转算法按照轮转的次序分配给每个程序一定的时间执行，执行完成后执行后面的进程 ，依次循环执行直到所有进程执行完成。算法： void RR(int m) Node *p; while(head1-next!=NULL) p=head1-next; Node *prep=head1
8、; Node *q; while(p!=NULL) cout执行进程一个时间片data.ID; for(q=head1;q-next!=NULL;q=q-next) if(q-next=p) p-data.ALLTime-=4; p-data.CPUTime+=4; if(p-data.ALLTime=0) cout进程已执行完成data.ID; prep-next=prep-next-next; free(p); p=prep-next; else prep=prep-next; p=p-next; coutendl; cout进入下一次轮转endl; cout所有进程都执行完成next;
9、Node *q=head-next; Node *q0=head; while(q!=NULL) if(q-data.ALLTime=0) cout进程已执行完成endldata.ID; n-; q0-next=q0-next-next; free(q); q=q0-next; else if(q-data.Priorityp-data.Priority) p=q; q0=q0-next; q=q-next; if(n0) action(p); （4）运行结果分析（运行界面截图、输入输出数据说明和分析等）先输入系统进程数，系统自动分配进程先来先服务调度：最短进程调度：时间片轮转调度：动态优先级
10、调度：（5）设计小结课程设计是我们专业课程知识综合应用的实践训练，也是为我们以后的工作夯实基础。通过改程序对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法，短进程优先调度算法，时间片轮转调度算法，动态优先级调度有了更深刻的理解和掌握，使我能够为进程调度选择适当的算法，提高CPU工作效率。进行进程调度程序设计的过程中，得到老师的大力指导和同学的支持，在此向他们表示感谢。经过自己的动手操作和同学老师的指导我成功的做出了课程设计自己感到很高兴。在整个过程中自己也感受到了集体团结的力量，今后无论是在工作还是学习中我都会发样这种精神。（6）参考文献（参考的书籍等，列出书名、作者
11、、出版社及出版时间等，例如：1计算机操作系统(第3版)，汤小丹，西安电子科技大学出版社，2007年7月2C语言程序设计，孟庆昌，人民邮电出版社，2006年4月）源代码：#include#include#include#include#include #define TRUE 1#define FALSE 0#define OK 1typedef struct PCB int ID; int Priority; int CPUTime; int ALLTime; int Status;PCB;typedef PCB Dt;typedef struct Node Dt data; struct N
12、ode *next;Node;Node *head=(Node *)malloc(sizeof(Node);Node *head1=(Node *)malloc(sizeof(Node);Node *head2=(Node *)malloc(sizeof(Node);int n;void create(int n) int i=1; srand(int)time(0); head-next=NULL; Node *q=head; cout 优先数 优先级 CPUTime AllTime Status endl; while(idata.ID=i; p-data.CPUTime=0; p-dat
13、a.Status=0; p-data.Priority=rand()%10+1; p-data.ALLTime=rand()%8+1; cout data.ID data.Priority data.CPUTime data.ALLTime data.Statusnext=NULL; q-next=p; q=q-next; i+; Node *p0=head1; head1-next=NULL; for(q=head-next;q!=NULL;q=q-next) Node *r=(Node *)malloc(sizeof(Node); r-data.ID=q-data.ID; r-data.C
14、PUTime=q-data.CPUTime; r-data.Status=q-data.Status; r-data.Priority=q-data.Priority; r-data.ALLTime=q-data.ALLTime; p0-next=r; r-next=NULL; p0=p0-next; Node *p1=head2; head2-next=NULL; for(q=head-next;q!=NULL;q=q-next) Node *k=(Node *)malloc(sizeof(Node); k-data.ID=q-data.ID; k-data.CPUTime=q-data.C
15、PUTime; k-data.Status=q-data.Status; k-data.Priority=q-data.Priority; k-data.ALLTime=q-data.ALLTime; p1-next=k; k-next=NULL; p1=p1-next; void FCFS() Node *p=head-next; while(p!=NULL) cout执行进程endldata.ID; p=p-next; coutendl; cout所有进程都执行完成next!=NULL) pmin=head2-next; for(p=head2-next;p!=NULL;p=p-next)
16、 if(pmin-data.ALLTimep-data.ALLTime) pmin=p; cout执行剩余区间长度最短的进程endldata.ID; for(p=head2;p!=NULL;p=p-next) if(p-next=pmin) p-next=p-next-next; free(pmin); coutendl; cout所有进程都执行完成next; while(q!=NULL) coutdata.ID执行一个时间片的进程data.Priority=q-data.Priority+1; else q-data.Priority=q-data.Priority-3; if(q-data
17、.ALLTime4) q-data.ALLTime-=4; else q-data.ALLTime=0; q-data.Status=1; q=q-next; void SearchMaxPRI(int m) Node *p=head-next; Node *q=head-next; Node *q0=head; while(q!=NULL) if(q-data.ALLTime=0) coutdata.ID进程已执行完成next=q0-next-next; free(q); q=q0-next; else if(q-data.Priorityp-data.Priority) p=q; q0=q
18、0-next; q=q-next; if(n0) action(p);void RR(int m) Node *p; while(head1-next!=NULL) p=head1-next; Node *prep=head1; Node *q; while(p!=NULL) coutdata.ID执行进程一个时间片next!=NULL;q=q-next) if(q-next=p) p-data.ALLTime-=4; p-data.CPUTime+=4; if(p-data.ALLTime=0) coutdata.ID进程已执行完成next=prep-next-next; free(p);
19、p=prep-next; else prep=prep-next; p=p-next; coutendl; cout进入下一次轮转endl; cout所有进程都执行完成endl;int main() cout请输入系统进程数：n; int m=n; if(n=0) cout此时没有就绪进程endl; else create(n); coutendl; cout先来先服务调度endl; FCFS(); coutendl; cout短进程优先调度endl; SJF(); coutendl; cout动态优先级调度next!=NULL) SearchMaxPRI(m); cout所有进程都执行完成endl; coutendl; cout时间片轮转调度endl; RR(m);
