进程调度算法的分析与研究.doc

. . . . .合肥经济技术职业学院毕业设计论文（2011 2012学年）论文（设计）题目 进程调度算法的分析及研究 院 系 名 称 电子信息系 专 业 班 级 计算机应用 学 生 姓 名 mm 学 号 mm 指 导 教 师 mm 日期 2012年4月16日目 录摘要3关键词3引言4第一章 进程概述51.1进程调度51.1.1进程的属性51.1.2进程的基本状态51.2进程调度的三种算法6第二章 算法分析72.1先来先服务调度算法72.1.1算法思想72.1.2 算法流程图82.1.3 程序代码82.1.4测试结果122.2优先数调度算法122.2.1算法思想122.2.2算法流程图132.2.3程序代码142.2.4测试结果162.3时间片轮转调度算法172.3.1算法思想172.3.2 算法流程图182.3.3程序代码182.3.4测试结果212.4测试分析22总结23参考文献24进程调度算法的分析与研究摘 要调度也称dispatcher 这是内核的主要职责之一就是决定该轮到哪个任务运行了多数实时内核是基于优先级调算法的每个任务根据其重要程度的不同被赋予一定的优先级基于优先级的调度法指CPU总是让处在就绪态的优先级最高的任务先运行然而究竟何时让高优先级任务掌握CPU的使用权有两种不同的情况这要看用的是什么类型的内核是非占先式还是占先式的内核。进程调度性能的衡量方法可以分为定性和定量两种，在定性衡量方面，首先是调度的安全性。比如，一次进程调度是否可能引起数据结构的破坏等。这要求对调度时机的选择和保存CPU现场十分小心。另外，系统开销也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程的上下文切换，如果调度策略过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调度系统调用较多的情况下，将会造成响应时间大幅度增加。进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的，一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。本文详细地讨论了四种常用进程调度算法的基本思想，并对其进行了分析和评价。关键词：进程 算法 分析 研究引 言进程调度是系统内部的低级调度，进程调度的策略通常有先来先服务算法、时间片轮转算法、最高优先权优先调度算法等。衡量进程调度性能通常需要从定性和定量两个方面来综合考虑。进程调度性能的衡量方法可以分为定性和定量两种，在定性衡量方面，首先是调度的安全性。比如，一次进程调度是否可能引起数据结构的破坏等。这要求对调度时机的选择和保存CPU现场十分小心。另外，系统开销也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程的上下文切换，如果调度策略过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调度系统调用较多的情况下，将会造成响应时间大幅度增加。进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的，一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。第一章 进程概述1.1进程调度无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。1.1.1进程的属性1、多态性 从诞生、运行，直至消灭2、多个不同的进程可以包括相同的程序3、三种基本状态 它们之间可进行转换4、并发性 并发执行的进程轮流占用处理器1.1.2进程的基本状态1、等待态：等待某个事件的完成；2、就绪态：等待系统分配处理器以便运行；3、运行态：占有处理器正在运行。运行态等待态 往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。等待态就绪态 则是等待的条件已满足，只需分配到处理器后就能运行。运行态就绪态 不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。就绪态运行态 系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态。1.2进程调度的三种算法（1）先来先服务算法：如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调度到运行状态。（2）优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。（3）时间片轮转算法：固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务。处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。不需要处理器处理的时候，这部分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上。经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。第二章 算法分析2.1先来先服务调度算法2.1.1算法思想先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。2.1.2 算法流程图开始结束初始化所有JCB，使JCB按作业提交时刻的先后顺序排队时间量T=0调度队首的作业投入运行（更改队首指针，使作业的状态为R，记住作业开始运行的时刻Tb）计算并打印作业的完成时刻Tc，周转时刻Ti，带权周转时刻Wi更改时间量T的值等待队列空？计算并打印这组作业的平均周转时间及带权平均周转时间空不空图21先来先服务算法流程图2.1.3 程序代码#include #include #include typedef struct node char name10; /*进程名*/int cputime; /*占用cpu时间*/char starttime5; /进程开始时间int needtime; /*要求运行时间*/char state; /*状态*/struct node *next; /*指针*/PCB;PCB *ready, *run, *finish; /就绪、执行、结束指针int N; /进程数量void print() /输出函数PCB *p;printf( NAME CPUTIME STARTTIME NEEDTIME STATUSn);if(run != NULL)printf( %-10s%-10d%-10s%-10d %cn,run-name,run-cputime,run-starttime,run-needtime,run-state); /*输出执行的进程的信息*/p=ready;while(p != 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,p-starttime,p-needtime,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;while(p1!=NULL)&b)if(strcmp(p1-starttime,s-starttime)next; /*新进程的开始时间大，则p1 指向下一个进程继续比*/ else b=0; if(r!=p1) r-next=s; s-next=p1; /*新进程找到位置，插在r和p1之间*/elses-next=p1; ready=s; /*新进程的开始时间按最小，插在队首，并修改就绪队首ready指针*/ 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(%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);printf(*n);print(); getchar();run=ready; /*队列排好，run指向就绪队列队首*/ready=ready-next; /*ready指向下一个进程*/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 PCB:n);scanf(%d,&N);create(); /*模拟创建进程，并输入相关信息*/FCFS(); /*先来先服务调度算法*/2.1.4测试结果首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间所有进程都在队列中，并都处于等待状态其中一个进程执行完毕所有进程都执行完毕2.2优先数调度算法2.2.1算法思想进程的执行顺序由高优先级到低优先级，系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。2.2.2算法流程图开始初始化PCB，输入进程信息各进程按优先数从高到低排列就绪队列空？结束就绪队列首进程投入运行时间片到，运行进程已占用CPU时间+1运行进程已占用CPU时间达到所需的运行时间使运行进程的优先数减1，把运行进程插入就绪队列进程完成，撤销该进程图22优先数算法流程图2.2.3程序代码#include #include #include typedef struct node char name10; /*进程名*/ int prio; /*优先数*/ int cputime; /*占用cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/PCB;PCB *ready,*run,*finish; /*就绪 执行 结束指针*/int N;void prt() /*输出函数，可以方便看到进程执行的演示*/ PCB *p; printf( NAME CPUTIME NEEDTIME PRIORITY STATUSn); if(run!=NULL) printf( %-10s%-10d%-10d%-10d %cn,run-name,run-cputime,run-needtime,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%-10d%-10d%-10d %cn,p-name,p-cputime,p-needtime,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; while(p1!=NULL)&b) if(p1-prio=s-prio) r=p1; p1=p1-next; /*新进程的优先数小，则p1 指向下一个进程继续比*/ else b=0; if(r!=p1) r-next=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 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，插入新进程*/ else p-next=ready; ready=p; /*否则先插在NULL前*/ printf( Display is going to start: n); printf(*n); prt(); run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready-next; /*ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程*/ run-state=R; /*队首进程的状态为就绪*/void prio() while(run!=NULL) run-cputime=run-cputime+1; /*运行一次cpu占用时间加一*/ run-needtime=run-needtime-1; /*运行一次要求运行时间减一*/ run-prio=run-prio-1; /*运行一次优先数减一*/ if(run-needtime=0) /*若要求运行时间为0时*/ run-next=finish; /*退出队列*/ finish=run; /*finish为结束进程的队列 */ run-state=E; /*修改状态为结束*/ run=NULL; /*释放run指针*/ if (ready!=NULL) /*创建新就绪队列的头指针*/ run=ready; run-state=R; ready=ready-next; else if(ready!=NULL)&(run-prioprio) /*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/ run-state=W; run-next=NULL; /*队首进程退出进程队列*/ 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(); /*模拟创建进程，并输入相关信息*/ prio(); /*优先数调度算法*/2.2.4测试结果优先级调度算法运行情况如图23，图24，图25，图26所示 图23输入进程块的数量 图24输入每个进程的名称、时间、优先级 图25输入所有的进程的相关信息 图26所有进程调度算法完成2.3时间片轮转调度算法2.3.1算法思想所有就绪进程按先来先服务的原则排成一个队列，将新来的进程加到就绪对列的末尾，每当执行进程调度时，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。也就是说CPU的处理时间划分成一个个相同的时间片，就绪队列的所有进程轮流运行一个时间片。当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。直至所有的进程运行完毕。2.3.2 算法流程图开始结束所有进程是否运行完毕？建立就绪队列时间+1是否有新进程加入就绪队列根据循环轮转算法在就绪队列中查找当前时间片应运行的进程是否有可运行的进程？运行进程并打印进程信息打印“当前没有进程运行”是是否否图27优先数算法流程图2.3.3程序代码#include #include #include typedef struct node char name10; /*进程名*/ int count; /*计数器，判断是否=时间片的大小*/int cputime; /*占用cpu时间*/int needtime; /*要求运行时间*/char state; /*状态*/struct node *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-needtime,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(); void insert(PCB *q) /*在队尾插入新的进程*/ PCB *p;p=ready;while(p-next!=NULL)p=ready-next;tail=p;tail-next=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，插入新进程*/ else p-next=ready; ready=p; tail=p; printf( Display is going to start: n); printf(*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-needtime-1; /*运行一次要求运行时间减一*/run-count=run-count+1; /*运行一次计数器加一*/if(run-needtime=0) /*若要求运行时间为0时*/ run-next=finish; /*退出队列*/finish=run; /*finish为结束进程的队列 */run-state=E; /*修改状态为结束*/run=NULL; /*释放run指针*/if (ready!=NULL) /*创建新就绪队列的头指针*/run=ready; run-state=R; ready=ready-next; elseif(run-count=round) /*如果时间片到*/ 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 nu