操作系统——四种进程调度算法模拟实现（C语言）

一、六种进程调度算法的基本思想

1、先来先服务First-Come-First-Served（FCFS）（作业／进程）调度算法
FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。

2、短作业优先调度算法(Shortest Job First, SJF)
这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。
采用SJF有利于系统减少平均周转时间和平均带权周转时间。

3、高响应比优先调度算法 (Highest Response Ratio Next, HRRN)
按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比R，然后选择其值最大的作业投入运行。R值定义为：
R ＝（已等待时间＋要求运行时间）／要求运行时间
＝1＋已等待时间／要求运行时间
HRRN算法实际上是FCFS算法和SJF算法的折衷。响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的响应比。这就克服了短作业优先的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。

4、时间片轮转Round-Robin（RR）调度算法
进程调度程序总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。

5、高优先级调度算法(Priority Scheduling Algorithm, PSA)
按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法。进程的优先权的设置可以是静态的，也可以是动态的。

6、多级反馈队列调度算法
多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。
例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按FCFS等策略排序，后台采用高优先权的调度算法或者短作业优先的调度算法。

二、四种进程调度算法模拟实现

1、进程调度算法模拟程序设计要求

（1）编写并调试一个模拟的进程调度程序，以深入探讨进程的概念及进程调度算法．

（2）分别采用3种调度算法对五个进程进行调度。每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已用CPU时间、进程状态等等。

（3）每个进程的状态可以是就绪W（Wait）、运行R（Run）、或阻塞B（Block）三种状态之一。每进行一次调度程序都打印一次运行进程、就绪队列、阻塞队列以及各个进程的PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。进程的相关参数即运行时间、I/O需求等自行设定。

2、C语言源代码：

#includeusing namespace std;#define MAXSIZE 30typedef struct PCB {char name[20]; // 进程名称(输入)intarrivetime; //到达时间 (输入)intrunning_time; //服务时间intpriority; //优先级intstart_time; //开始时间intdone_time;//结束时间intcopyRunning_time; //用于时间片轮转float zztime;//记录该进程的周转时间（后期复制用）float dqzztime;//记录该进程的带权周转时间（后期复制用）PCB* next;} Program;typedef struct PCBQueue {PCB* firstProg;PCB* LastProg;int size;} PCBQueue;// 函数声明void print(PCB pro[], int num);//输出每个进程的到达时间 void inputProgram(PCB pro[], int num); //输入所有进程的具体信息 void PrintRunningprogram(PCB *pro);//输出正在运行的进程的信息 void PrintReadyqueue(PCBQueue *ready_queue);//输出就绪队列中的所有进程的信息 void PrintSortOfRunningprogram(PCB pro1[],int num);//输出进程的运行顺序 void CopyProgram(PCB *pro1,PCB *pro2);//将进程pro2的信息复制到进程pro1中 void Queueinit(PCBQueue* queue);//初始化就绪队列 void EnterQueue(PCBQueue* queue, PCB* pro);//将一个进程插入到就绪队列中 PCB* poll(PCBQueue* queue);//将一个进程从就绪队列中删除 void sortWithEnterTime(PCB pro[], int num);//将所有进程按到达时间升序排序 void EnterQueueOfRuntime(PCBQueue *ready_queue,PCB *program);//将一个进程按运行时间长短插入就绪队列 void EnterQueueOfPriority(PCBQueue *ready_queue,PCB *program);//将一个进程按优先级插入就绪队列 void FCFS(PCB pro[], int num);//先来先服务调度算法 void SJF(PCB pro[],int num);//短作业优先调度算法 void HPF(PCB pro[],int num);//高优先级调度算法 void RR(PCB pro[], int num);//时间片轮转调度算法 //具体函数实现 void print(PCB pro[], int num) {int i;for (i = 0; i < num; i++) {printf("%d ", pro[i].arrivetime);}}void inputProgram(PCB pro[], int num) {int i;for (i = 0; i name);printf("\t————————————————————————————————————————————————\n");printf("\t进程名字到达时间服务时间优先级开始时间结束时间周转时间带权周转时间\n");printf("\t%s\t\t%d\t%d\t%d",pro->name,pro->arrivetime,pro->running_time,pro->priority);printf("\t%d\t%d\t %5.2f\t%5.2f\n",pro->start_time,pro->done_time,pro->zztime,pro->dqzztime);printf("\t————————————————————————————————————————————————\n\n");}void PrintReadyqueue(PCBQueue *ready_queue) {PCB *p;p=ready_queue->firstProg->next;if(!p) {printf("\t无进程处于就绪状态！\n");printf("\t————————————————————————————————————————————————\n\n\n");return ;}printf("\t就绪队列：\n");printf("\t————————————————————————————————————————————————\n");printf("\t进程名字到达时间服务时间优先级\n");while(p) {printf("\t%s\t\t%d\t%d\t%d\n",p->name,p->arrivetime,p->running_time,p->priority);p=p->next;}printf("\t————————————————————————————————————————————————\n");printf("\n\n\n");}void PrintSortOfRunningprogram(PCB pro1[],int num) {int i;printf("\t进程运行顺序如下：\n");printf("\t————————————————————————————————————————————————\n");printf("\t进程名字到达时间服务时间优先级开始时间结束时间周转时间带权周转时间\n");for(i=0; iname,pro2->name,sizeof(pro2->name));pro1->arrivetime=pro2->arrivetime;pro1->running_time=pro2->running_time;pro1->priority=pro2->priority;pro1->start_time=pro2->start_time;pro1->done_time=pro2->done_time;pro1->zztime=pro2->zztime;pro1->dqzztime=pro2->dqzztime;}void Queueinit(PCBQueue* queue) {if (queue == NULL) {return;}queue->size = 0;queue->LastProg = (PCB*)malloc(sizeof(PCB));queue->LastProg->next=NULL;//注意加了此句queue->firstProg = queue->LastProg;}void EnterQueue(PCBQueue* queue, PCB* pro) {//加入进程队列queue->LastProg->next = (PCB*)malloc(sizeof(PCB));queue->LastProg = queue->LastProg->next;queue->LastProg->arrivetime = pro->arrivetime;memcpy(queue->LastProg->name, pro->name, sizeof(pro->name));queue->LastProg->priority = pro->priority;queue->LastProg->running_time = pro->running_time;queue->LastProg->copyRunning_time = pro->copyRunning_time;queue->LastProg->start_time = pro->start_time;queue->LastProg->next=NULL;//注意加了此句queue->size++;}PCB* poll(PCBQueue* queue) {PCB *temp;temp = queue->firstProg->next;if (temp == queue->LastProg) {queue->LastProg = queue->firstProg;queue->LastProg->next=NULL;//注意加了此句queue->size--;return temp;}queue->firstProg->next = queue->firstProg->next->next;queue->size--;return temp;}void sortWithEnterTime(PCB pro[], int num) { //将进程按到达时间（arrivetime）全部排序int i,j;PCB temp;for (i = 1; i < num; i++) {for (j = 0; j  pro[j + 1].arrivetime) {temp = pro[j];pro[j] = pro[j + 1];pro[j + 1] = temp;}}}}void EnterQueueOfRuntime(PCBQueue *ready_queue,PCB *program) { //按进程的运行时间，找到就绪队列中的相应位置并插入进去PCB *p,*q;p=ready_queue->firstProg->next;q=ready_queue->firstProg;while(p) {if(p->running_time>program->running_time) {program->next=p;q->next=program;break;}q=p;p=p->next;}if(!p) { //如果就绪队列为空或该进程的运行时间最长，则将其插入到队尾ready_queue->LastProg->next=program;ready_queue->LastProg=program;program->next=NULL;}ready_queue->size++;}void EnterQueueOfPriority(PCBQueue *ready_queue,PCB *program) {PCB *p,*q;p=ready_queue->firstProg->next;q=ready_queue->firstProg;while(p) {if(p->prioritypriority) { //优先级大的先执行program->next=p;q->next=program;break;}q=p;p=p->next;}if(!p) {ready_queue->LastProg->next=program;ready_queue->LastProg=program;program->next=NULL;}ready_queue->size++;}void FCFS(PCB pro[], int num) {int time,done_time;int i,count,tt,pronum;float sum_T_time,sum_QT_time;PCB *curpro,*temp_PCB;printf("\n\t\t\t\t\t先来先服务算法进程调度模拟\n\n");printf("\t————————————————————————————————————————————————\n");count=0;PCB pro2[100];sortWithEnterTime(pro, num);//按照进入到达时间顺序排序PCBQueue* queue = (PCBQueue*)malloc(sizeof(PCBQueue));//定义就绪队列Queueinit(queue);//就绪队列初始化EnterQueue(queue, &pro[0]);//将第一个进程送入就绪队列中time = pro[0].arrivetime;//记录第一个进程的到达时间pronum = 1;//记录当前的进程数量sum_T_time = 0, sum_QT_time = 0; // sum_T_time 记录总的周转时间 ，sum_QT_time 记录总的加权周转时间while (queue->size > 0) {curpro = poll(queue); //从进程队列中取出一个进程if (time arrivetime){time = curpro->arrivetime;}done_time = time + curpro->running_time; //done_time 为该进程的结束时间（开始时间+CPU运行时间）curpro->start_time=time;curpro->done_time=done_time;curpro->zztime = done_time - curpro->arrivetime;//周转时间curpro->dqzztime = curpro->zztime / curpro->running_time;//带权周转时间sum_T_time += curpro->zztime;//sum_T_time总的周转时间更新sum_QT_time += curpro->dqzztime; //sum_T_time总的带权周转时间更新for (tt = time; tt <= done_time && pronum = pro[pronum].arrivetime) {EnterQueue(queue, &pro[pronum]);pronum++;}}CopyProgram(&pro2[count],curpro);PrintRunningprogram(&pro2[count]);count++;if(queue->size!=0) {printf("\t就绪队列：\n");printf("\t————————————————————————————————————————————————\n");printf("\t进程 到达时间服务时间 优先级\n");temp_PCB=queue->firstProg->next;for(i=queue->size; i>0; i--) {printf("\t%s\t%d\t%d\t%d\n",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);temp_PCB=temp_PCB->next;}printf("\t————————————————————————————————————————————————\n");printf("\n\n\n");} else {printf("\t无进程处于就绪状态!\n");printf("\t————————————————————————————————————————————————\n\n\n");}time += curpro->running_time;if (queue->size == 0 && pronum size>0) {curpro=poll(ready_queue);//就绪队列中的队头进程进入CPU中运行if(timearrivetime) { //如果该进程与上一次运行的进程结束时间之间有间隔，则将CPU运行时间变为该进程到达时间time=curpro->arrivetime;}done_time=time+curpro->running_time;curpro->start_time=time;curpro->done_time=done_time;curpro->zztime = done_time - curpro->arrivetime;//周转时间curpro->dqzztime = curpro->zztime / curpro->running_time;//带权周转时间//打印正在运行的进程PrintRunningprogram(curpro);//将curpro的信息复制到pro1[i]中CopyProgram(&pro1[i],curpro);i++;sum_T_time += curpro->zztime;sum_QT_time += curpro->dqzztime;while(pronum<num) { //将在CPU中的进程运行的时间内到达的进程放入就绪队列if(pro[pronum].arrivetimesize==0&&pronumsize>0) {curpro=poll(ready_queue);//就绪队列中的队头进程进入CPU中运行if(timearrivetime) { //如果该进程与上一次运行的进程结束时间之间有间隔，则将CPU运行时间变为该进程到达时间time=curpro->arrivetime;}done_time=time+curpro->running_time;curpro->start_time=time;curpro->done_time=done_time;curpro->zztime = done_time - curpro->arrivetime;//周转时间curpro->dqzztime = curpro->zztime / (curpro->running_time + 0.0);//带权周转时间//打印正在运行的进程PrintRunningprogram(curpro);//将curpro的信息复制到pro1[i]中CopyProgram(&pro1[i],curpro);i++;sum_T_time += curpro->zztime;sum_QT_time += curpro->dqzztime;while(pronum<num) { //将在CPU中的进程运行的时间内到达的进程放入就绪队列if(pro[pronum].arrivetimesize==0&&pronumsize > 0) {curpro = poll(queue);// 从就绪队列中取出一个进程if (time arrivetime) {time = curpro->arrivetime; // 计算开始运行时间}if (timeslice >= curpro->running_time) {// 如果剩余时间小于时间片则此任务完成for (tt = time; tt running_time && pronum = pro[pronum].arrivetime) { // 统计从此任务开始到结束之间有几个进程到达pro[pronum].start_time = tt;EnterQueue(queue, &pro[pronum]);pronum++;}}time += curpro->running_time;curpro->running_time = 0;curpro->done_time = time;T_time = curpro->done_time - curpro->start_time;QT_time = T_time / (curpro->copyRunning_time + 0.0);sum_T_time += T_time;sum_QT_time += QT_time;strcpy(pro2[count].name, curpro->name) ;pro2[count].arrivetime=curpro->arrivetime;pro2[count].running_time= curpro->copyRunning_time;pro2[count].priority=curpro->priority;pro2[count].start_time=curpro->start_time;pro2[count].done_time=curpro->done_time;pro2[count].zztime=T_time;pro2[count].dqzztime=QT_time;count++;printf("\n\t执行完成》》》进程%s！\n",curpro->name);printf("\t————————————————————————————————————————————————\n");if(queue->size!=0) {printf("\t就绪队列：\n");printf("\t————————————————————————————————————————————————\n");printf("\t进程 到达时间服务时间优先级\n");PCB* temp_PCB=queue->firstProg->next;for(i=queue->size; i>0; i--) {printf("\t%s\t%d\t%d\t %d\n",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);temp_PCB=temp_PCB->next;}printf("\t————————————————————————————————————————————————\n\n\n");} else {printf("\t 无进程处于就绪状态！\n");printf("\t————————————————————————————————————————————————\n\n\n");}if (queue->size == 0 && pronum < num) { //防止出现前一个进程执行完到下一个进程到达之间无进程进入pro[pronum].start_time = pro[pronum].arrivetime;EnterQueue(queue, &pro[pronum]);pronum++;}continue;}for (tt = time; tt <= time + timeslice && pronum = pro[pronum].arrivetime) { // 统计从此任务开始到结束之间有几个进程到达pro[pronum].start_time = tt;EnterQueue(queue, &pro[pronum]);pronum++;}}printf("\n\t正在执行》》》进程%s\n",curpro->name);printf("\t————————————————————————————————————————————————\n");if(queue->size!=0) {printf("\t就绪队列：\n");printf("\t————————————————————————————————————————————————\n");printf("\t进程 到达时间服务时间优先级\n");temp_PCB=queue->firstProg->next;for(i=queue->size; i>0; i--) {printf("\t%s\t%d\t%d\t%d\n",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);temp_PCB=temp_PCB->next;}printf("\t————————————————————————————————————————————————\n\n\n");} else {printf("\t 无进程处于就绪状态！\n");printf("\t————————————————————————————————————————————————\n\n\n");}time += timeslice;curpro->running_time -= timeslice;EnterQueue(queue, curpro);//当前程序未完成继续添加到队列中if (queue->size == 0 && pronum < num) { //防止出现前一个进程执行完到下一个进程到达之间无进程进入pro[pronum].start_time = pro[pronum].arrivetime;EnterQueue(queue, &pro[pronum]);pronum++;}}PrintSortOfRunningprogram(pro2,count);printf("\t平均周转时间为:%.2f\n", sum_T_time / num);printf("\t平均带权周转时间为:%.2f\n",sum_QT_time/num);}void menu() {printf("\t\t\t\t\t<>\n");printf("\t\t\t\t\t1.先来先服务算法\n");printf("\t\t\t\t\t2.短进程优先算法\n");printf("\t\t\t\t\t3.高优先级算法\n");printf("\t\t\t\t\t4.时间片轮转算法\n");printf("\t\t\t\t\t5.退出\n");printf("\t\t\t\t\t请选择进程调度算法:");}int main() {int n, t = 1;int proNum,choice;PCB pro[MAXSIZE],temp_pro[MAXSIZE];printf("\n\n\t\t\t\t\t<>\n");printf("\t\t\t\t\t请输入进程的个数：");scanf("%d", &proNum);inputProgram(pro, proNum);while (t) {menu();memcpy(temp_pro, pro, (sizeof(pro) / sizeof(pro[0])) * sizeof(PCB));scanf("%d", &n);while (n  5) {printf("\t\t\t指令不正确，请重新输入指令： ");scanf("%d", &n);}system("cls");switch (n) {case 1: {FCFS(temp_pro, proNum);break;}case 2: {SJF(temp_pro, proNum);break;}case 3: {HPF(temp_pro, proNum);break;}case 4: {RR(temp_pro, proNum);break;}case 5: {t = 0;break;}}getchar();printf("\n\t按任意键继续.......");getchar();system("cls");}system("cls");printf("\n\n\t\t\t\t\t您已成功退出系统！！！\n");return 0;}