进程模拟调度算法课程设计

1、课程概述1.1. 设计构想程序能够完成以下操作： 创建进程： 先输入进程的数目， 再一次输入每个进程的进程名、 运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法， 并单步执行，每次执行的结果都从屏幕上输出来。1.2. 需求分析在多道程序环境下， 主存中有着多个进程， 其数目往往多于处理机数目， 要使这多个进程能 够并发地执行， 这就要求系统能按某种算法， 动态地把处理机分配给就绪队列中的一个进程， 使之执行。 分配处理机的任务是由处理机调度程序完成的。 由于处理机是最重要的计算机资 源，提高处理机的利用率及改善系统必（吞吐量、响应时间） ，在很大程度上取决于处理机

2、 调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。本次实验在 VC+6.0 环境下实现先来先服务调度算法， 短作业优先调度算法， 高优先权调度算法， 时间 片轮转调度算法和多级反馈队列调度算法。1.3. 理论依据为了描述和管制进程的运行，系统为每个进程定义了一个数据结构进程控制块 PCB（Process Control Block）,PCB 中记录了操作系统所需的、 用于描述进程的当前情况以及控 制进程运行的全部信息， 系统总是通过 PCB 对进程进行控制， 亦即，系统是根据进程的 PCB 而不是任何别的什么而感知进程的存在的， PCB 是进程存在的惟一标志。本次课程设计用

3、结构体 Process 代替 PCB 的功能。1.4. 课程任务一、用 C 语言（或 C+ ）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多 种算法实现对进程的模拟调度。二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、 短作业优先、多 级反馈队列调度算法， 使学生进一步掌握进程调度的概念和算法， 加深对处理机分配的 理解。三、实现用户界面的开发1.5. 功能模块分析：1、进程概念： 进程是被独立分配资源的最小单位。 进程是动态概念， 必须程序运行才有 进程的产生。2、进程的状态模型：（1）运行：进程已获得处理机，当前处于运行状态。（2）就绪：进程已经准备好，一旦有处

4、理器就可运行。3、处理机调度： 在多道程序设计系统中， 内存中有多道程序运行， 他们相互争夺处理机 这一重要的资源。 处理机调度就是从就绪队列中， 按照一定的算法选择一个进程并将 处理机分配给它运行，以实现进程并发地执行。4、进程调度算法的功能：记录系统中所有进程的执行情况选择占有处理机的进程进行进程的上下文切换5、进程调度的算法：（1）先来先服务算法：如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在 就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调 度到运行状态。（2）优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原 则为进程指定一个优先级来表示该

5、进程所享有的确调度优先权。该算法核心是 确定进程的优先级。（3）时间片轮转算法：固定时间片，每个进程在执行一个时间片后，轮到下一进程 执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务。处理 器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预 测。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参 与，有些不需要 （如磁盘控制器的存储过程） 。不需要处理器处理的时候，这部 分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上。经过周 密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就 是时间片轮换。（4）多级反馈队列法： 又

6、称反馈循环队列或多队列策略， 主要思想是将就绪进程分 为两级或多级， 系统相应建立两个或多个就绪进程队列， 较高优先级的队列一 般分配给较短的时间片。 处理器调度先从高级就绪进程队列中选取可占有处理 器的进程， 只有在选不到时， 才从较低 级的就绪进程队列中选取。（5）短作业优先法：对短进程优先调度的算法，它是从后备队列中选择一个或者若 干个进程， 将处理机分配给它， 使它立即执行并一直执行到完成， 或发生某事 件而被阻塞放弃处理机时再重新调度。设计方案2.1先来先服务调度2.1.1算法思想先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执 行。先来先服务调度算法是一种

7、不可抢占的算法， 先进入就绪队列的进程， 先被处理机运行。 一旦一个进程占有了处理机， 它就一直运行下去， 直到该进程完成工作或者因为等待某事件 而不能继续运行时才释放处理机。2.1.2算法流程图图 1. 先来先服务算法流程图2.1.3程序代码#include #include #include typedef struct nodechar name10; /* 进程名 */ int cputime; /* 占用 cpu 时间 */ char starttime5; / 进程开始时间 int needtime; /* 要求运行时间 */ char state; /* 状态 */ struct

8、 node *next; /* 指针 */PCB;PCB *ready, *run, *finish; / 就绪、执行、结束指针 int N; /进程数量 void print() /输出函数PCB *p;STATUSn);printf( NAME CPUTIME STARTTIME NEEDTIME if(run != NULL)printf( %-10s%-10d%-10s%-10d %cn, run-name, run-cputime, run-starttime, run-needtime,run-state); /* 输出执行的进程的信息 */ p=ready;while(p !=

9、NULL)printf( %-10s%-10d%-10s%-10d %cn,p-name,p-cputime,p-starttime,p-needtime,p-state); /* 输出就绪进程的信息 */p=p-next;p=finish;while(p != NULL)printf( %-10s%-10d%-10s%-10d %cn,p-name, p-cputime,*/*/ready 指针 */p-starttime, p-needtime, p-state); /* 输出结束队列的信息 */ p=p-next;getchar(); /* 使用 getchar() 函数可以让输出时停留

10、画面， 等待人按回车继续 */void insert(PCB *q)/*插入新进程，把进程按进程到来时间大小排序PCB *p1,*s,*r;int b;s=q;/* 指针 s 指向新要插入的进程 */p1=ready; /* 指针 p1 指向原来的进程队列的队首 */ r=p1; /* 使用指针 r 是指向 p1 前面的进程 */ b=1;while(p1!=NULL)&b) if(strcmp(p1-starttime,s-starttime)next; /* 新进程的开始时间大，则 p1 指向下一个进程继续比 elseb=0; if(r!=p1) r-next=s; s-next=p1;

11、/* 新进程找到位置，插在 r 和 p1 之间 */ else s-next=p1; ready=s; /* 新进程的开始时间按最小，插在队首，并修改就绪队首 void create()PCB *p;int i; ready=NULL; run=NULL; finish=NULL;printf(Please enter the name and time and starttime of PCB:n); /* 输入进程名、运行时间和开始时间 */ for(i=0;iname); /* 输入进程名 */ scanf(%d,&p-needtime); /* 输入进程要求运行时间 */ scanf(

12、%s,p-starttime); /输入进程开始时间p-cputime=0;p-state=W; /* 表示就绪队列中未在队首先执行，但也是就绪状态 */ if (ready!=NULL)insert(p); /* 就绪队首不为 NULL ，插入新进程 */else /* 否则先插在 NULL 前 */p-next=ready;ready=p;printf(Display is going to start:n);*n);printf(print();getchar();run=ready; /* 队列排好， run 指向就绪队列队首 */ ready=ready-next; /*ready

13、指向下一个进程 */ run-state=R; /* 队首进程的状态为就绪 */void FCFS() while(run != NULL) run-cputime=run-cputime+run-needtime;run-needtime=0; run-next=finish; finish = run;run-state=E;run = NULL; if(ready != NULL)run = ready; run-state=R; ready=ready-next; print();void main()printf(Please enter the total number of PC

14、B:n); scanf(%d,&N);create(); /* 模拟创建进程，并输入相关信息 */FCFS(); /* 先来先服务调度算法 */2.1.4测试结果及说明首先输入进程个数(为 5 个)，这里命名为 A,B,C,D,E ，然后分别输入运行时间和开始时间所有进程都在队列中，并都处于等待状态其中一个进程执行完毕所有进程都执行完毕2.2优先级调度2.2.1算法思想进程的执行顺序由高优先级到低优先级， 系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。 该算法核心是确定进程的优先 级。2.2.2算法流程图图 2. 优先级调度流程图#include #include

15、#include typedef struct node char name10; /* int prio; /* int cputime; /* int needtime; /* char state; /* struct node *next; /* PCB;PCB *ready,*run,*finish; int N;void prt() /* PCB *p;2.2.3程序代码进程名 */优先数 */占用 cpu 时间 */要求运行时间 */状态*/指针*/* 就绪 执行 结束指针 */输出函数，可以方便看到进程执行的演示 */printf( NAME CPUTIME NEEDTIME

16、PRIORITY STATUSn)if(run!=NULL)printf( %-10s%-10d%-10d%-10d %cn,run-name,run-cputime,run-need time,run-prio,run-state);/* 输出执行的进程的信息 */p=ready;while(p!=NULL)printf( %-10s%-10d%-10d%-10d %cn,p-name,p-cputime,p-needtime, p-prio,p-state); /* 输出就绪进程的信息 */p=p-next; p=finish;while(p!=NULL) printf( %-10s%-1

17、0d%-10d%-10d %cn,p-name,p-cputime,p-needtim e,p-prio,p-state); /* 输出结束队列的信息 */p=p-next; getchar(); /* 使用 getchar() 函数可以让输出时停留画面，等待人按回车 继续*/void insert(PCB *q) /* 插入新进程，把进程按优先数大小排序 */ PCB *p1,*s,*r;int b;s=q; /* 指针 s 指向新要插入的进程 */p1=ready; /* 指针 p1 指向原来的进程队列的队首 */r=p1; /* 使用指针 r 是指向 p1 前面的进程 */ b=1;wh

18、ile(p1!=NULL)&b)/* 新进程的优先数 新进程找到位置，插在 r 和 新进程的优先数最大，插在队if(p1-prio=s-prio) r=p1; p1=p1-next; 小，则 p1 指向下一个进程继续比 */ else b=0;if(r!=p1) r-next=s; s-next=p1; /* p1 之间*/else s-next=p1; ready=s; /* 首，并修改就绪队首 ready 指针 */void create() PCB *p;int i;ready=NULL; run=NULL; finish=NULL;printf(Please enter the nam

19、e and time and priority of PCB:n);/* 输入进程名、运行时间和优先级 */ for(i=0;iname); /* 输入进程名 */scanf(%d,&p-needtime); /* 输入进程要求运行时间 */ scanf(%d,&p-prio); /* 输入进程优先数 */ p-cputime=0;p-state=W; /* 表示就绪队列中未在队首先执行，但也是就绪状 态*/if (ready!=NULL) insert(p); /*就绪队首不为 NULL，插入新进程*/否则先插在 NULL前*/else p-next=ready; ready=p; /* p

20、rintf(Display is going to start:n);运行一次 cpu 占用时间加一 */ 运行一次要求运行时间减一 */ 运行一次优先数减一 */ 若要求运行时间为 0 时*/退出队列 */ 为结束进程的队列 */ 修改状态为结束 */ 释放 run 指针 */创建新就绪队列的头指针 */printf(*n); prt(); run=ready; /* 队列排好， run 指向就绪队列队首 */ ready=ready-next; /*ready 指向下一个进程， 这样当进程执行时如 果优先数小于其他的进程，应该先进行优先数最大的进程 */ run-state=R; /* 队

21、首进程的状态为就绪 */ void prio() while(run!=NULL)/*/*/*finish/*/*/* 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=E; run=NULL; if (ready!=NULL) run=ready; run-state=R; ready=ready-next; elseif(ready!=NULL)&(run-

22、prioprio) run-state=W; run-next=NULL; /* insert(run); /* run=ready; /* run-state=R;/* 队首进程的优先数比它下一个小，且下一个进程不为NULL时执行 */队首进程退出进程队列 */ 在进程队列中重新插入原来的队首进程 */ 重新置就绪队列的头指针 */ready=ready-next; prt(); void main() printf(Please enter the total number of PCB:n); scanf(%d,&N);create(); /* 模拟创建进程，并输入相关信息 */ pri

23、o(); /* 优先数调度算法 */2.2.4测试结果及说明优先级调度算法运行情况如图 1，图 2，图 3，图 4 所示图 1. 输入进程块的数量图 2. 输入每个进程的名称、时间、优先级图 3. 输入所有的进程的相关信息图 4. 所有进程调度算法完成2.3 时间片轮转调度2.3.1算法思想所有就绪进程按先来先服务的原则排成一个队列，将新来的进程加到就绪 对列的末尾， 每当执行进程调度时， 总是把处理机分配给队首的进程， 各进程占 用 CPU的时间片相同。 也就是说 CPU的处理时间划分成一个个相同的时间片， 就 绪队列的所有进程轮流运行一个时间片。 当一个时间片结束时， 如果运行进程用 完它

24、的时间片后还未完成，就强迫运行进程让出 CPU，就把它送回到就绪队列的 末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配 给它一时间片，以投入运行。直至所有的进程运行完毕。2.3.2算法流程图2.3.3程序代码#include #include #include typedef struct nodechar name10;/* 进程名 */int count;/* 计数器，判断是否 =时间片的大小 */ int cputime; /* 占用 cpu 时间 */ int needtime; /* 要求运行时间 */char state;/* 状态 */struct nod

25、e *next; /* 指针 */PCB;PCB *ready,*run,*finish,*tail;/* 就绪 执行 结束 尾指针 */int N,round;void prt() /*输出函数，可以方便看到进程执行的演示 */PCB *p;printf( NAME CPUTIME NEEDTIME STATUSn);if(run!=NULL)printf( %-10s%-10d%-10d %cn,run-name,run-cputime,run-needti me,run-state); /* 输出执行的进程的信息 */p=ready;while(p!=NULL)printf( %-10s

26、%-10d%-10d %cn,p-name,p-cputime,p-needtime,p- state);/* 输出就绪进程的信息 */p=p-next;p=finish;while(p!=NULL)printf( %-10s%-10d%-10d %cn,p-name,p-cputime,p-needtime,p- state); /* 输出结束队列的信息 */p=p-next;getchar();void insert(PCB *q) /* 在队尾插入新的进程 */PCB *p;p=ready;while(p-next!=NULL)p=ready-next;tail=p;tail-next=

27、q; q-next=NULL;void create()PCB *p;int i;ready=NULL; run=NULL; finish=NULL;printf(Please enter the name and time of PCB:n);/* 输入进程名、和*/for(i=0;iname);/* 输入进程名 */scanf(%d,&p-needtime); /* 输入进程要求运行时间 */ p-cputime=0;p-state=W;/* 表示就绪队列中未在队首先执行，但也是就绪状态*/if (ready!=NULL) insert(p); /* 就绪队首不为 NULL ，插入新进程

28、*/ else p-next=ready; ready=p; tail=p;printf( printf(n);Display is going to start:*n);prt();getchar();run=ready; /* 队列排好， run 指向就绪队列队首 */ ready=ready-next; /*ready 指向下一个进程 */run-state=R; /* 队首进程的状态为就绪 */void count()while(run!=NULL)run-cputime=run-cputime+1; /* 运行一次 cpu 占用时间加一 */ run-needtime=run-nee

29、dtime-1; /* 运行一次要求运行时间减一 */run-count=run-count+1;/* 运行一次计数器加一 */if(run-needtime=0)run-next=finish; finish=run; run-state=E; run=NULL;if (ready!=NULL) /*若要求运行时间为 0 时*/* 退出队列 */*finish 为结束进程的队列 */* 修改状态为结束 */* 释放 run 指针 */* 创建新就绪队列的头指针 */run=ready; run-state=R; ready=ready-next; elseif(run-count=round

30、)/* 如果时间片到 */run-count=0; /* 计数器置 0*/ if(ready!=NULL) /* 如就绪队列不空 */ run-state=W;insert(run); /* 在进程队列中重新插入原来进程 , 插入队尾 */run=ready;/* 重新置就绪队列的头指针 */run-state=R;ready=ready-next;prt();void main()printf(Please enter the total number of PCB:n);scanf(%d,&N);create(); /* 模拟创建进程，并输入相关信息 */ count(); /* 优先数调

31、度算法 */2.3.4测试结果及说明时间片轮转调度算法运行情况如图 1，图 2，图 3 所示图1 所有的进程都在队列中图 2 其中一个进程执行完毕图 4 所有的进程都执行完毕2.4 多级反馈队列调度2.4.1 算法思想允许进程在队列之间移动。 在系统中设置多个就绪队列， 每个队列对应一个优先级， 第 一个队列的优先级最高， 第二队列次之。 以下各队列的优先级逐步低。 各就绪队列中的进程 的运行时间片不同， 高优先级队列的时间片小， 低优先级队列的时间片大。 进程并非总是固 定在某一队列中， 新进程进入系统后， 被存放在第一个队列的末尾。 如果某个进程在规定的 时间片内没有完成工作， 则把它转入

32、到下一个队列的末尾， 直至进入最后一个队列。 系统先 运行第一个队列中的进程。当第一队列为空时，才运行第二个队列中的进程。依此类推，仅 当前面所有的队列都为空时，才运行最后一个队列中的进程。 当处理器正在第 i 个队列中为 某个进程服务时，又有新进程进入优先级最高的队列（第 1（ i-1）中的任何一个对列） ， 则此新进程要抢占正在运行进程的处理器， 即由调度程序把正在运行的进程放回第 i 队列的 末尾， 把处理器分配给新到的高优先级进程。 除最低优先权队列外的所有其他队列， 均采用 相同的进程调度算法，即按时间片轮转的 FIFO （先进先出）算法。最后一个队列中的进程 按按时间片轮转或 FC

33、FS 策略进行调度。它是综合了 FIFO、 RR 和剥夺式 HPF 的一种进程 调度算法。2.4.2 算法流程图2.4.3 程序代码#include#include #include #define NULL 0typedef struct nodechar name10; /* 进程名 */int num;/* 进程所在队列数 ,也是该队列的时间片 */int cputime;/* 占用 cpu 时间 */int needtime;/* 要求运行时间 */struct node *next; /* 指针 */PCB;PCB *qf1,*ql1;PCB *qf2,*ql2;PCB *qf3,*

34、ql3;/ 定义三个队列的头指针和尾指针int blog1,blog2,blog3; /*分别记录队列 1,、队列 2、队列 3 中进程数 */ void insert(PCB *q,PCB *qf,PCB *ql) q-num+;if(qf=NULL&ql=NULL) / 队列为空qf=ql=q;else/ 队列不为空ql-next=q;ql=q;ql-next=NULL;void create(int n)/ 创建进程，刚来的进程都进入队列 1PCB *p;p=(PCB *)malloc(sizeof(PCB);int i;blog1=blog2=blog3=0; /各队列中进程数均为 0

35、 printf(Please enter the name and needtime of PCB:n);/* 输入进程名和所需时间 */for(i=0;iname);/* 输入进程名 */scanf(%d,&(p-needtime); /* 输入进程要求运行时间 */ p-cputime=0;p-num=0;insert(p,qf1,ql1);blog1+; / 队列中进程数加 1int run(PCB *q,PCB *qf,PCB *ql)PCB *p,*f,*l;/*p=(PCB *)malloc(sizeof(PCB);f=(PCB *)malloc(sizeof(PCB);l=(PC

36、B *)malloc(sizeof(PCB);*/p=q;f=qf;l=ql; if(q-needtimenum) /* 在时间片内完成 */ /q-cputime+=q-needtime; q-needtime=0; free(q);return 0;else /* 不能在时间片内完成 */ /q-cputime+=q-num; q-needtime-=q-num; if(q-numnum+;insert(p,f,l); /进入下一个队列 return 1;void prt() /*输出函数，可以方便看到进程执行的演示*/PCB *p;/p=(PCB *)malloc(sizeof(PCB)

37、;int a;printf( NAME CPUTIME NEEDTIME STATUSn); while(blog10|blog20|blog30)if(blog10) /* 第一个队列不为空 */p=qf1; qf1=qf1-next; p-next=NULL; blog1-;printf( %-10s%-10d%n,p-name,p-needtime); a=run(p,qf2,ql2);if(a=1) blog2+;else if(blog20) /* 第二个队列不为空 */ p=qf2;qf2=qf2-next;p-next=NULL;blog2-;printf( %-10s%-10d

38、%n,p-name,p-needtime);a=run(p,qf3,ql3);if(a=1)blog3+;else if(blog30) /* 第三个队列不为空 */p=qf3;qf3=qf3-next;p-next=NULL;blog3-;printf( %-10s%-10d%n,p-name,p-needtime);a=run(p,qf3,ql3);if(a=1)blog3+; /* 使用 getchar() 函数可以让输出时停留画面，等待人按回车继续*/void main()qf1=ql1=(PCB *)malloc(sizeof(PCB);qf2=ql2=(PCB *)malloc(s

39、izeof(PCB);qf2=ql2=(PCB *)malloc(sizeof(PCB);int n;blog1=blog2=blog3=0;printf( 请输入进程的个数 : );scanf(%d,&n);create(n);prt();2.4.4 测试结果及说明2.5 短作业调度2.5.1算法思想短作业优先调度算法是指对短作业进行调度的算法。 它从后备队列总选择一个或若干 个运行时间最短的作业，将他们调入内存运行。2.5.2算法流程图：短作业优先算法流程图2.5.3程序代码#include #include #include typedef struct nodechar name10;

40、 int cputime; int needtime;char state; struct node *next;/* 进程名 */* 占用 cpu 时间 */ /* 要求运行时间 */ /*状态 */* 指针 */PCB;PCB *ready, *run, *finish; / 就绪、执行、结束指针int N; /进程数量void print() /输出函数PCB *p;printf( NAME CPUTIME NEEDTIME STATUSn); if(run != NULL)printf( %-10s%-10d%-10d %cn, run-name, run-cputime, run-n

41、eedtime,run-state); /* 输出执行的进程的信息 */ p=ready;while(p != NULL)printf( %-10s%-10d%-10d %cn, p-name, p-cputime, p-needtime, p-state);/* 输出就绪进程的信息 */p=p-next;p=finish;while(p != NULL)printf( %-10s%-10d%-10d %cn, p-name, p-cputime, p-needtime, p-state); /* 输出结束队列的信息 */ p=p-next;getchar(); /* 使用 getchar()

42、 函数可以让输出时停留画面， 等待人按回车继续 */void insert(PCB *q)/* 插入新进程，把进程按进程到来时间大小排序*/PCB *p1,*s,*r;int b;s=q;/* 指针 s 指向新要插入的进程 */p1=ready; /* 指针 p1 指向原来的进程队列的队首 */ r=p1;/* 使用指针 r 是指向 p1 前面的进程 */b=1;while(p1!=NULL)&b) if(p1-needtimeneedtime) r=p1; p1=p1-next; /* 新进程的开始时间大，则 p1 指向下一个进程继续比 */ elseb=0;if(r!=p1) r-next

43、=s; s-next=p1; /* 新进程找到位置，插在 r 和 p1 之间 */else s-next=p1; ready=s; /* 新进程的开始时间按最小，插在队首，并修改就绪队首 ready 指针 */ void create()PCB *p; int i; ready=NULL; run=NULL;finish=NULL; printf(Please enter the name and time of PCB:n);/* 输入进程名、运行时间和开始时间 */ for(i=0;iname); /* 输入进程名 */ scanf(%d,&p-needtime); /* 输入进程要求运行时间 */ p-cputime=0;p-state=W;/* 表示就绪队列中未在队首先执行，但也是就绪状态*/if (ready!=NULL)insert(p); /* 就绪队首不为 NULL ，插入新进程 */