“时间片轮转”调度算法（C语言）

一、算法实现流程图：

二、实现思路：

#define q 1 //时间片
要求：
PCB必须按顺序输入，到达时间从小到大。

实现：
难点在于PCB就否到达就绪队列的处理。

设标识变量，处理就绪队列，队列内有有效PCB和无效PCB（还未到达）

刚到达的PCB与执行一次时间片之后的PCB排序问题：
课本解释：当该进程的时间片耗尽或运行完毕时，系统再次将CRU分配给队首进程（或新到达的紧迫进程）。

由此可保证就绪队列中的所有进程在一个确定的时间段内，都能够获得一次CPU执行。

因此：正确答案应该是，新到达的进程放就绪队列（有效PCB）队首。

执行完队头（有效PCB就绪队列的对头元素）元素后，在插入就绪队列，插入到有效PCB就绪队列的尾部

时间计算：Time(CPU执行总时间)还需要考虑CPU空闲时间（就绪队列内有效数据为0个时，且还有PCB未到达，就是计算CPU空闲时间的时候）
结束条件：必须是就绪队列内没有PCB（可能存在就绪队列内含有未到达PCB）

三、测试

说明：本代码只是针对课本给出的例子进行编写，因此会有很多漏洞！！
也可测试同时到达。

四、代码

（visual studio 2019）

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h" 
#include  
#include  
#define getpch(type) (type*)malloc(sizeof(type)) //快速malloc
#define NULL 0 
#define q 1 //时间片
/*
待实现：
PCB必须按顺序输入，到达时间从小到大。

	思路：
	1、新建标志变量，是否到达状态 
	2、处理就绪队列，队列内有有效PCB和无效PCB（还未到达）
	3、处理完队头（有效PCB就绪队列的对头元素）元素后，在插入就绪队列，插入到有效PCB就绪队列的尾部
	4、结束条件：必须是就绪队列内没有PCB
	5、时间计算：除了-到达时间外，还需要考虑CPU空闲时间（就绪队列内有效数据为null时，就是计算空闲时间的时候）

	问题：在一个进程运行一次时间片时，但还未结束，需要插入就绪队列。

	是先插入，还是先判断一些其他进程是否到达。
（就绪队列顺序）
	这里采用：先到达，即先刷新PCB状态，在插入运行时间片结束的PCB。


	课本解释：当该进程的时间片耗尽或运行完毕时，系统再次将CRU分配给队首进程（或新到达的紧迫进程）。
由此可保证就绪队列
	中的所有进程在一个确定的时间段内，都能够获得一次CPU执行。

	因此：正确答案应该是，新到达的进程放队首。

*/
struct pcb { /* 定义进程控制块PCB */
	char state;//进程状态 就绪 W（Wait）、运行R（Run）、或完成F（Finish）
	int Atime=0;//到达时间，默认同一时间到达
	int ntime;//进程运行时间
	int rtime;//已用CPU时间
	int TF;//是否为就绪队列内的有效PCB，默认有效
	struct pcb* link;
	//新建变量：是否到达的一个状态  
	char name[10];//进程名
}*ready = NULL, * p;
typedef struct pcb PCB;
int h = 0;//执行时间片数
int Time = 0;//CPU运行时间 利用Time记录每个进程的完成时间   (Time-Atime) 是周转时间
float allAvgTime = 0;//累加所有进程的带权周转时间

/* 当该进程的时间片耗尽或运行完毕时，将该进程插入有效就绪队列*/
void sort()
{
	PCB* first, * second;
	if (ready == NULL||ready->TF==0) /*就绪队列为空，或者进程重新插入时，就绪队列有效PCB为0，插入队首*/
	{
		p->link = ready;
		ready = p;
	}
	else /*尾插 只能插入到有效PCB的后面*/
	{
		first = ready;
		second = first->link;
		while (second != NULL&&second->TF==1)
		{
			first = first->link;
			second = second->link;
		}
		p->link = second;
		first->link = p;
	}
}

/*PCB必须按顺序输入，到达时间从小到大。
*/
/* 建立进程控制块函数，按顺序插入到就绪队列中*/
void input()
{
	int i, num;
	system("cls"); /*清屏*/
	printf("\n 请输入建立的进程数?");
	scanf("%d", &num);
	for (i = 0; i < num; i++)
	{
		printf("\n 进程号No.%d:\n", i);
		p = getpch(PCB);//申请结构体PCB内存空间
		printf("\n 输入进程名:");
		scanf("%s", &p->name);
		printf("\n 输入进程到达时间:");
		scanf("%d", &p->Atime);
		printf("\n 输入进程运行时间:");
		scanf("%d", &p->ntime);
		p->link = NULL;
		p->state = 'w';
		p->rtime = 0;
		p->TF = 1;
		printf("\n");
		sort(); //调用sort函数，插入p进程进入ready队列
	}
}

/*查看就绪队列中有多少进程*/
int space()
{
	int l = 0; PCB* pr = ready;
	while (pr != NULL)
	{
		l++;
		pr = pr->link;
	}
	return(l);
}

/*建立进程显示函数,用于打印当前进程*/
void disp(PCB* pr)
{
	printf("\n qname \t state \t Atime \t ndtime  runtime  daoda(0/1) \n");
	printf("|%s\t", pr->name);
	printf("|%c\t", pr->state);
	printf("|%d\t", pr->Atime);
	printf("|%d\t", pr->ntime);
	printf("|%d\t", pr->rtime);
	printf("  |%d\t", pr->TF);
	printf("\n");
}

/* 建立进程查看函数 */
void check()
{
	PCB* pr;
	printf("\n **** 当前正在运行的进程是:%s", p->name); /*显示当前运行进程*/
	disp(p);//封装
	pr = ready;
	printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
	while (pr != NULL)
	{
		disp(pr);//调用打印
		pr = pr->link;
	}
}
/*建立进程撤消函数(进程运行结束,撤消进程)*/
void destroy()
{
	allAvgTime = allAvgTime + (float)(Time - p->Atime) / p->ntime;
	printf("\n 进程 [%s] 已完成.\n周转时间为[%d ms]\n带权周转时间为[%.2f ms]\n", p->name,Time-p->Atime,(float)(Time - p->Atime)/p->ntime);
	free(p);
}

/*在每次调用running中的sort前，刷新PCB的状态（是否到达）*/
void flushed() {

	PCB* traverse, * pre;
	traverse = ready;
	pre = NULL;
	while (traverse != NULL&&traverse->TF==1) {
		//只需将未到达的PCB置为0即可
		if (traverse->Atime > Time) {//不应该是finish时间，应该是CPU执行时间(h*q 比CPU执行时间略大 暂时就这样吧)
			traverse->TF = 0;
		}
			
			//新到达的程序(数组)放就绪队列队头
			//记录（front） 记录第一个0-->1（left）  循环遍历到最后一个0->1（rigth） 记录后面链表（behind  pre->behind)  
			//再将ready置为（left）  
		pre = traverse;
		traverse = traverse->link;
	}

	//本程序只考虑一次改变一个PCB状态（简单）

	if (traverse != NULL&& traverse->Atime <= Time) {
		traverse->TF = 1;
		if (pre != NULL) {
			pre->link = traverse->link;
			traverse->link = ready;
			ready = traverse;
		}
		
	}
}
/* 建立进程就绪函数(进程运行时间到,置就绪状态*/
void running()
{
	(p->rtime)= (p->rtime)+q;
	if (p->rtime >= p->ntime) {
		if (p->rtime == p->ntime) { 
			Time = Time + q;
		}
		else {
			Time = Time + (p->ntime) % q;//未利用完时间片，完成跳出
		}
		p->state = 'F';
		//新建一个周转时间（同一时刻创建，所以周转时间等于完成时间） ，记录完成时间
		// 根据周转时间/服务时间=带权周转时间
		//如果刚好是时间片的整数倍，直接 当前时间片*时间片数 
		//如果不是整数倍 则ntime%时间片+时间片
		destroy(); /* 调用destroy函数*/
	}
	else
	{
		Time = Time + q;//未执行完毕
		p->state = 'w';//就绪
		sort(); /*调用sort函数，重新插入到就绪队列*/
		flushed();//每次都要重新判断是否有PCB到达， 到达直接插入队首.
	}
}


void main() /*主函数*/
{
	int len;
	char ch;
	input();//建立PCB
	len = space();
	flushed();//PCB状态刷新
	while ((len != 0) && (ready != NULL))
	{
		ch = getchar();
		h++;
		printf("\n The execute number:%d \n", h);
		if (ready->TF == 0) {//就绪队列内没有有效PCB
			//这里只需加上CPU空闲时间即可  第一个无效进程的到达时间-上一个完成进程的完成（注意是完成）时间
			//Time= Time+(ready->Atime - Time);
			Time = ready->Atime;

			//将第一个无效PCB改为有效PCB
			ready->TF = 1;
		}
		else {
			p = ready;
			ready = p->link;
			p->link = NULL;
			p->state = 'R';
			check();
			running();
			printf("\n 按任一键继续......");
			ch = getchar();
		}
		
	}
	printf("\n\n 进程已经完成.\n");
	printf("系统的平均带权周转时间为【%.2f ms】", allAvgTime / len);
	ch = getchar();
}