进程调度算法模拟-

进程调度算法模拟

专业：计算机科学与技术 学号：120602105 姓名：黄凡

实验日期：2014年12月2日

一.算法综述

调度也称dispatcher，这是内核的主要职责之一就是决定该轮到哪个任务运行了多数实时内核是基于优先级调度算法的每个任务根据其重要程度的不同被赋予一定的优先级，基于优先级的调度法指CPU 总是让处在就绪态的优先级最高的任务先运行，然而究竟何时让高优先级任务掌握CPU 的使用权，有两种不同的情况这要看用的是什么类型的内核是非占先式还是占先式的内核一个良好的任务调度算法应该主要体现在以下几个方面： 1.公平保证每个进程得到合理的CPU 时间

2.高效使CPU 保持忙碌状态即总是有进程在CPU 上运行 3.响应时间使交互用户的响应时间尽可能短

4.周转时间使批处理用户等待输出的时间尽可能短 5.吞吐量使单位时间内处理的进程尽可能多

很显然在任何操作系统中这几个目标不可能同时达到所以不同的。 操作系统会在这几个方面中做出相应的取舍从而确定自己的调度算法，常用的处理机调度算法有： 先来先服务FCFS 短作业优先SJF 优先级

时间片轮转法 多级队列法 多级反馈队列法

先来先服务：FCFS 是最简单的CPU 调度算法，即按进程到来的先后次序进行调度，这样在系统中等待时间最长的进程被优先调度，而不管其所需运行时间的长短。

作业优先SJF 算法是指当CPU 可供使用时SJF 算法把CPU 分给需要运行时间最短的进程。

多级队列调度算法：把就绪队列划分成几个单独的队列一般根据进程的某些特性如内存大小和进程类型永久性地把各个进程分别链入其中某一个队列中，每个队列都有自己的调度算法，此外在各个队列之间也要进行调度。通常采用固定优先级的抢占式调度，例如某系统中有5 个队列，各个队列的优先级自上而下降低，只有当前3 个队列中都为空的时候队列4 中的进程才可以运行，而当队列4 中的进程在运行时，如果队列1 中进入了一个就绪进程，则队列4 中的进程要立刻让出CPU 使用权。多级反馈队列法允许进程在各队列间移动，其基本思想是把具有不同CPU工作时间这一特性的进程区分开来，如果一个进程要使用很长的CPU 时间，则应把它移至较低级的队列中，这种方式把I/O 繁忙型和交互式进程放在较高优先级的队列中同样在低优先级队列中长时间等待的进程可以移到较高优先级队列中UNIX 系统采用的是多级反馈队列轮转法。 时间片轮转调度法：round-robin scheduling

当两个或两个以上任务有同样优先级，内核允许一个任务运行事先确定的一段时间叫做时间额度quantum ，然后切换给另一个任务也叫做时间片调度time slicing ，内核在满足以下条件时把CPU 控制权交给下一个任务就绪态的任务， 当前任务已无事可做，当前任务在时间片还没结束时已经完成了。轮转法主要是为分时系统设计的，其中时间片是一个重要的参数不能取的过大或过小，通常为

10 至100ms 数量级，就绪队列可以看成是一个环形队列，CPU 调度程序轮流地把CPU 分给就绪队列中地每个进程，时间长度为一个时间片Linux 操作系统就是采用时间片轮转的调度算法。

二.算法分析

1.先到先服务算法

算法思想：按照进入就绪对列的先后顺序来分配处理机。FCFS采用非剥夺式调度方式，即一旦某个进程占有处理机，就一直运行下去，直到该进程完成其工作或等待某事件而不能继续执行时才释放处理机。

优缺点：利于长作业进程，而不利于短作业进程这是因为若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。有利于CPU繁忙型作业，不利于I/O，忙的作业。

现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。 2.短作业优先算法 算法思想：

优缺点：降低作业的平均等待时间，提高系统吞吐量。对长作业不利；未考虑作业的紧迫程度；对进程估计执行时间难以预测。 3.高优先权优先调度算法

为了考虑作业的紧迫程度，引入了最高优先权调度算法（FPF） 1) 优先权调度算法类型 a) 非抢占式优先权算法

基本原理：系统把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成；或因发生某时间使该进程放弃处理机时，系统才可将处理机重新分配给另一优先权最高的进程。

适用：批处理系统，实时性要求不高的实时系统。 b) 抢占式优先权算法

基本原理：系统把处理机优先权最高的进程，使之执行。若在其执行期间，只要又出现另一个优先权更高的进程，则立即停止当前进程的执行，重新分配处理机给新来的优先权更高的进程。

适用：实时性要求高的实时系统，对性能要求高的批处理和分时系统。 2) 优先权类型 a) 静态优先权

静态优先权是在创建进程的时确定的，且在进程的整个运行期间保持不变。一般，利用某一范围内的整数来表示，如，0~7或0～255中的整数。 b) 动态优先权

是指在创建进程时确定的优先权，在进程的运行期间会发生变化。 4.时间片轮转法 算法思想：

系统将所有就绪进程按FCFS的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为几个毫秒～几百毫秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。

三.算法设计

1.先进先出算法流程图

2时间片转法算法流程图

四.编码实现

1.先进先出算法（源程序） #include #include #include

using namespace std;

struct fcfs{

char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; };

fcfs a[100];

void input(fcfs *p,int N) {

int i;

cout

printf(" 请您输入进程的 名字 到达时间 服务时间: (例如: a 0 100)\n\n"); for(i=0;i

void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) {

int k;

printf("\n\n调用先来先服务算法以后进程运行的顺序是: "); printf("%s",p[0].name); for(k=1;k%s",p[k].name);

}

cout

printf("\n 具体进程调度信息:\n");

printf("\t进程名 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间\n");

for(k=0;k

printf("\t%s\t%-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\n",p[k].name,p[k].arrivetime,

p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); }

getchar(); //此处必须要有这个函数，否则就看不到显示器上面的输出，可以看到的结果只是一闪而过的一个框剪 }

void sort(fcfs *p,int N) //排序 {

for(int i=0;i

if(p[i].arrivetime

fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } }

void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //运行阶段 {

int k;

for(k=0;k

if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;}

else {

p[k].starttime=p[k-1].finishtime;

p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} }

for(k=0;k

void FCFS(fcfs *p,int N) { float

arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N);

deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); }

char menu() {

char cse1; while(1) {

system("cls"); fflush(stdin); cout

cout>>>>>>>>>>>迎********* ||"

cout

cout

cout

cout

cout

cout>>>>>>>>>>>>>>>>>>>> ||"

int N;

cout

printf("\t\t>\n");

cout

printf("输入进程数目:"); scanf("%d",&N); input(a,N); FCFS(a,N); cse1=getchar(); system("PAUSE");

return EXIT_SUCCESS; return cse1; } }

int main(){ menu(); }

2时间片轮转算法（源程序） #include #include #include #include

static int id = 0;

int process_num; int current_process;

struct pcb {

char name[20]; int id;

char state; int need_time; int run_time; struct pcb *next;

}*p, *q, *first_pcb = NULL; typedef struct pcb PCB;

/* 排序输出各个进程PCB */ void printSort() {

int i;

q = first_pcb;

for(i = 0; i id) {

printf("|%s/t/t|%d/t/t|%c/t/t|%d/t/t|%d/n", q -> name, q -> id, q -> state, q -> need_time, q -> run_time); i++;

q = first_pcb; } else {

q = q -> next; if(q == NULL) { q = first_pcb; i++; } } } }

/* 调度一次PCB并显示 */ void showPCB() { int i;

first_pcb -> run_time++; first_pcb -> state = 'r';

/* 进程执行完毕，将其清除出链表 */

if((first_pcb -> run_time) == (first_pcb -> need_time)) { current_process--;

printf("进程%s已经运行完毕", first_pcb -> name); system("pause");

first_pcb = first_pcb -> next; if(first_pcb == NULL) {

printf("所有进程都已经运行完毕"); system("pause"); return; }

first_pcb -> state = 'r'; }

system("cls");

/* 显示运行的进程和就绪的进程 */ q = first_pcb -> next;

printf("-------当前运行的进程是：进程%s/n/n", first_pcb -> name);

printf("-------在等待队列的进程是：");

while(q != NULL) {

printf("进程%s ", q -> name);

q = q -> next;

}

/* 显示相应的PCB块 */

printf("/n/n------------------------------进程详细PCB------------------------------------"); printf("/n/n|进程名/t/t|进程ID/t/t|进程状态/t|进程所需时间/t|进程运行时间/n"); printSort();

/* 进行一次时间片轮换调度算法， 将队首的进程放到队尾，之前第二位进程获得cpu时间片 */

q = first_pcb;

while(q -> next != NULL) {

q = q -> next;

}

first_pcb -> state = 'w';

q -> next = first_pcb;

first_pcb = first_pcb -> next;

q -> next -> next = NULL;

printf("/n");

printf("运行调度");

system("pause");

}

/* 将新的PCB块放到链表末尾 */

void pushPCB(int i)

{

q -> next = p;

q = p;

if(i == process_num - 1) q -> next = NULL;

}

/* 建立PCB块并将他们组成一个队列 */

void newPCB()

{

int i;

printf("请输入进程数：");

scanf("%d", &process_num);

q = (PCB*)malloc(sizeof(PCB));

first_pcb = (PCB*)malloc(sizeof(PCB));

for(i = 0; i

system("cls");

p = (PCB*)malloc(sizeof(PCB));

printf("请输入第%d个进程名:", id + 1);

scanf("%s", p -> name);

printf("请输入进程需要的运行时间：");

scanf("%d", &p -> need_time);

p -> id = id++;

p -> run_time = 0;

p -> state = 'w';

if(i == 0) {

first_pcb = q = p;

p -> next = NULL;

}

else pushPCB(i);

}

}

void main()

{

newPCB();

current_process = process_num;

printf("按任意键开始进程调度/n");

system("pause");

while(current_process) {

showPCB();

}

}

五.调试

1.先进先出算法调试

（1）.输入进程组一的进程数

（2）.依次输入进程的名称，到达时间及服务时间

（3）.输入完成后按回车键调用算法得到算法执行的各类信息

2.时间片轮转算法调试

（1）输入进程组一的进程数：

（2）依次输入进程名及所需的服务时间：

（3）程序开始执行

…（按回车键使程序执行完毕）

（5）程序至此执行完毕。

六.总结

比较这四类算法，并无优缺之分，没有最好的算法，只有最适宜此时情况的算法，而怎么选择调度算法呢，我觉得应该参考下列：

1) 如等待时间相同,则要求服务时间愈短,其优先权愈高—SPF。就是短作业优先算法。

2) 如要求服务时间相同,优先权决定于等待时间----FCFS。就是先来先服务算法。

3) 对长作业,若等待时间足够长，优先权也高，也能获得CPU。是本算法的优点，解决了短作业优先算法中，长作业的运行得不到保证的情况。也就是引入该算法的原因。

七.实验心得

通过本次调度算法的实验，我对于四种调度算法的具体实现步骤及其各自的特点有了进一步的认识。由于时间有限，只做了先进先出算法及时间片轮转算法的编程实现，有时间的话会把其他剩下两种也试着做一做。