操作系统——四种进程调度算法模拟实现（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语言源代码：

#include
using namespace std;
#define MAXSIZE 30
typedef struct PCB {
	char name[20];             // 进程名称(输入)
	int  arrivetime;           //到达时间 (输入)
	int  running_time;         //服务时间
	int  priority;             //优先级
	int  start_time;           //开始时间
	int  done_time;            //结束时间
	int  copyRunning_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 < num; i++) {
		PCB prog;
		printf("ttttt请输入第%d个进程的名字，到达时间，服务时间，优先级nttttt", i + 1);
		scanf("%s", prog.name);
		scanf("%d", &prog.arrivetime);
		scanf("%d", &prog.running_time);
		prog.copyRunning_time = prog.running_time;
		scanf("%d", &prog.priority);
		pro[i] = prog;
	}
}

void PrintRunningprogram(PCB *pro) {
	printf("t正在执行》》》进程%sn",pro->name);
	printf("t————————————————————————————————————————————————n");
	printf("t进程名字  到达时间  服务时间  优先级  开始时间  结束时间  周转时间  带权周转时间n");
	printf("t%stt%dt%dt%d",pro->name,pro->arrivetime,pro->running_time,pro->priority);
	printf("t%dt%dt   %5.2ft%5.2fn",pro->start_time,pro->done_time,pro->zztime,pro->dqzztime);
	printf("t————————————————————————————————————————————————nn");
}

void PrintReadyqueue(PCBQueue *ready_queue) {
	PCB *p;

	p=ready_queue->firstProg->next;
	if(!p) {
		printf("t无进程处于就绪状态！n");
		printf("t————————————————————————————————————————————————nnn");
		return ;
	}
	printf("t就绪队列：n");
	printf("t————————————————————————————————————————————————n");
	printf("t进程名字  到达时间  服务时间  优先级n");
	while(p) {
		printf("t%stt%dt%dt%dn",p->name,p->arrivetime,p->running_time,p->priority);
		p=p->next;
	}
	printf("t————————————————————————————————————————————————n");
	printf("nnn");
}

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 < num - i; j++) {
			if (pro[j].arrivetime > 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("nttttt先来先服务算法进程调度模拟nn");
	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 < curpro->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 < num; tt++) { //模拟进程的执行过程
			if (tt >= 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%st%dt%dt%dn",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);
				temp_PCB=temp_PCB->next;
			}
			printf("t————————————————————————————————————————————————n");
			printf("nnn");
		} else {
			printf("t无进程处于就绪状态!n");
			printf("t————————————————————————————————————————————————nnn");
		}
		time += curpro->running_time;
		if (queue->size == 0 && pronum < num) {
			//防止出现前一个进程执行完到下一个进程到达之间无进程进入
			EnterQueue(queue, &pro[pronum]);
			pronum++;
		}
	}
	PrintSortOfRunningprogram(pro2,count);
	//Print(pro2,count);
	printf("t平均周转时间为:%.2fn", sum_T_time /num);
	printf("t平均带权周转时间为:%.2fn",sum_QT_time/num);
}

void SJF(PCB pro[],int num) {
	int time,done_time;
	float sum_T_time,sum_QT_time;
	int i,pronum;
	PCBQueue *ready_queue;
	PCB *curpro,pro1[MAXSIZE];

	printf("nttttt短作业优先算法进程调度模拟nn");
	printf("t————————————————————————————————————————————————n");
	sortWithEnterTime(pro, num);
	ready_queue = (PCBQueue*)malloc(sizeof(PCBQueue));
	if(!ready_queue) {
		printf("分配就绪队列头结点空间失败！");
		exit(1);
	}
	Queueinit(ready_queue);
	EnterQueueOfRuntime(ready_queue,&pro[0]);
	time = pro[0].arrivetime;
	pronum = 1;                     //记录当前的进程
	sum_T_time = 0, sum_QT_time = 0;
	i=0;
	while(ready_queue->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(pronumsize==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(pronumsize==0&&pronumsize > 0) {
		curpro = poll(queue);                      // 从就绪队列中取出一个进程
		if (time < curpro->arrivetime) {
			time = curpro->arrivetime;                 // 计算开始运行时间
		}
		if (timeslice >= curpro->running_time) {        // 如果剩余时间小于时间片  则此任务完成
			for (tt = time; tt <= time + curpro->running_time && pronum < num; tt++) {  // 模拟进程的执行过程
				if (tt >= 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("nt执行完成》》》进程%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%st%dt%dt   %dn",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);
					temp_PCB=temp_PCB->next;
				}
				printf("t————————————————————————————————————————————————nnn");
			} else {
				printf("t 无进程处于就绪状态！n");
				printf("t————————————————————————————————————————————————nnn");
			}

			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 < num; tt++) {    //模拟进程的执行过程
			if (tt >= pro[pronum].arrivetime) { // 统计从此任务开始到结束之间有几个进程到达
				pro[pronum].start_time = tt;
				EnterQueue(queue, &pro[pronum]);
				pronum++;
			}
		}

		printf("nt正在执行》》》进程%sn",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%st%dt%dt%dn",temp_PCB->name,temp_PCB->arrivetime,temp_PCB->running_time,temp_PCB->priority);
				temp_PCB=temp_PCB->next;
			}
			printf("t————————————————————————————————————————————————nnn");
		} else {
			printf("t 无进程处于就绪状态！n");
			printf("t————————————————————————————————————————————————nnn");
		}

		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平均周转时间为:%.2fn", sum_T_time / num);
	printf("t平均带权周转时间为:%.2fn",sum_QT_time/num);
}

void menu() {
	printf("ttttt<<-------------操作系统进程调度算法模拟程序----------——>>n");
	printf("ttttt1.先来先服务算法n");
	printf("ttttt2.短进程优先算法n");
	printf("ttttt3.高优先级算法n");
	printf("ttttt4.时间片轮转算法n");
	printf("ttttt5.退出n");
	printf("ttttt请选择进程调度算法:");
}

int main() {
	int n, t = 1;
	int proNum,  choice;
	PCB pro[MAXSIZE],temp_pro[MAXSIZE];

	printf("nnttttt<<-------------进程初始化----------——>>n");
	printf("ttttt请输入进程的个数：");
	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 <= 0 || n > 5) {
			printf("ttt指令不正确，请重新输入指令： ");
			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("nt按任意键继续.......");
		getchar();
		system("cls");
	}
	system("cls");
	printf("nnttttt您已成功退出系统！！！n");

	return 0;
}

（1）输入进程

 （2）先来先服务调度算法（FSFS）

 （3）短作业优先调度算法（SJF）

 （4）高优先级调度算法

（5）时间片轮转调度算法

中间还有进程调度的详细过程图片......... （太多，放一两张）