C语言 操作系统实验 四种调度（时间片轮转法 RR）

 注：

本文是四个调度算法的第一篇算法。

本文是根据CSDN上某一FCFS调度算法魔改来的，所以FCFS的算法不会发到网站。

我是个菜鸡，发文是为了纪念自己完成了代码，以及累计自己的经验。

如有知识错误或者算法有逻辑漏洞请各位大佬高抬贵手。

实验环境：win10、VS2019（C++）

PS：虽然是cpp文件，实际上是披着cpp的c

        运行前，首先要在预处理器上插入_CRT_SECURE_NO_WARNINGS，避免运行错误，在插入前要用;隔开。

        具体位置就在解决方案下面一栏（名字是自己起的），右键属性即可找到。

         这个核心代码相对于之前的最短优先算法SJF来说在判断单元节点到达时间上是一致的，只不过多了等待时间变量wait以及响应比计算函数hrn，内容相对稀少，所以本篇会详细介绍响应比hrn函数以及在SJF中没提到的其他模板函数。

        注：如果想了解SJF算法或是判断单元节点到达时间函数此处为链接：C语言 操作系统实验 四种调度（最短优先算法SJF）_key_149的博客-CSDN博客

        注：如果想了解HRN算法或是算法中链表的模板函数此处为链接：

C语言 操作系统实验 四种调度（最高响应比优先算法 HRN）_key_149的博客-CSDN博客

        前三个调度算法FCSF、FJS、HRN都是通过一定顺序对进程进行排序输出，这也就导致了这三个除了思路意外，代码几乎都能通用，而时间片轮转法不论从思路还是代码都不同于前三个算法，这也导致了时间片RR的程序段需要从头开始整理思路。

        时间片RR算法首先划分时间片的大小，当有进程运行时，其进程的执行时间不超过时间片的大小，当时间片结束后，进程暂停运行，而下一个进程将开始运行，运行时间为时间片大小。直到最后一个进程用完时间片后，再次从第一个进程开始循环运行，直至当前进程运行完毕，进程退出队列。

        这种雨露均沾的做法不会有排序的机会出现，但时间片RR的算法是循环进行，也意味着其可用for循环来做，初始变量假设为0，每轮加上固定的时间片数，直至超过当前单元节点的运行时间，单元节点退出当前链表即可。

核心思路整理完毕，直接上代码：

void timeslicet()//时间片函数
{
	p->tc--;
	if (p->flag ==1)
	{
		p->ts = T;
		p->flag--;
	}
	if (p->tc == 0)
	{
		if (numcopy >= 2)//因循环链表的需求，最后两个链表特殊对待
		{
			first->link = p->link;//将p的下一个节点地址赋值给first的下一个节点
			p->link = NULL;
		}
		if (p->tn % time != 0)
		{
			T = T + p->tn % time;//在时间片内结束增加运行时间
			p->tf = T;//差值
		}
		else
		{
			T = T + time;//刚好在时间片用完时结束
			p->tf = T;
		}
	}
	else
	{
		T = T + time;//进程未运行完时，时间按时间片照常增加
	}
}

        此处tc为当前单元节点所需要的轮数。

        不同进程到达时间不一样，如不记录到达时间，有可能会发生晚到的进程却和提前到的进程在同一轮进行作业，所以需要记录当前的提交时间进行额外判断，此外在计算周转时间时，采用的是完成时间 - 提交时间的算法，所以记录提交时间是非常重要的。在链表连接时没有经过排序，所以单元节点的提交时间参差不齐，等待时间不便计算，故不采用。

        当前圈所需轮数转为空时，即tc == 0;时进入单元节点的输出和摘除阶段，因为循环遍历的原因，链表设置为循环链表，即头结点和尾结点是单向连接的，所以如果输出到只剩最后一个节点了，那其对应的多个指针在释放时会出现野指针的情况。为了避免这种情况出现，设立了if (numcopy >= 2)判断。

        在tc == 0:后first会作为当前节点p的前一个节点，连接p的下一个节点，即first->link = p->link;p->link = NULL:将p的指针域置空作为标记，以便释放。

        在摘出节点p后，应计算其完成时间。完成时间有两种，一种是在时间片内完成的，另一种则是在时间片执行完成时结束的，故需要执行时间 % 时间片计算有没有在时间片内完成的情况发生，T是到前一节点运行结束后的时间，如果当前节点在时间片内结束，则加上执行时间 % 时间片的余值，即T = T + p->tn % time;反之则加上时间片时间即可，T = T + time;

除了时间片函数RR外还有一部分核心思路在主函数的循环中。

	while (ready !=NULL)
	{
		p = ready;
		ready = p->link;//此处ready为下一个节点，first为上一个节点，p为当前节点

		if (T >= p->tr)
		{
			timeslicet(); //此函数将当前节点p从链表中摘除
		}
		else
		{
			T++;//时间每次循环+1
		}


		if (p->tc == 0)
		{
			check();//计算此时刻的周转时间
			disp(p);//输出此节点的值
			numcopy--;
			eti += p->ti;
			ewi += p->wi;
			p->link = NULL;
			running();
			//摘除p后first不动
		}
		else
		{
			first = p;//将first转移至当前节点处（当前没有摘除p）
		}
	}

        如上所示，当ready所指节点不为空时，即当前链表存在时，进行循环遍历，总时间T如果大于等于当前节点的提交时间，则执行时间片函数，否则自增一表示自增一秒的时间，这个判断防止当前时间没到提交时间却能执行的逻辑漏洞。

完整代码如下：

#include 
#include 
#include 

#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0

int num = 0;
int numcopy = 0;
int time = 0;
int T = 0;

struct jcb {
	char name[100];
	int tn;//运行
	int tf;//完成
	int ts;//开始
	int tr;//提交
	int tc;//自己所需转的圈数
	int flag;
	float ti;//周转
	float wi;//带权周转
	struct jcb* link;
}*ready = NULL, * h, * p;
typedef struct jcb JCB;
JCB* first;

void linkpcb()//尾插法将队列连接起来
{
	if (ready == NULL)
	{
		ready = p;
		first = p;
	}
	else
	{
		first->link = p;
		first = p;
	}
}

void timeslicet()//时间片函数
{
	p->tc--;
	if (p->flag ==1)
	{
		p->ts = T;
		p->flag--;
	}
	if (p->tc == 0)
	{
		if (numcopy >= 2)//因循环链表的需求，最后两个链表特殊对待
		{
			first->link = p->link;//将p的下一个节点地址赋值给first的下一个节点
			p->link = NULL;
		}
		if (p->tn % time != 0)
		{
			T = T + p->tn % time;//在时间片内结束增加运行时间
			p->tf = T;//差值
		}
		else
		{
			T = T + time;//刚好在时间片用完时结束
			p->tf = T;
		}
	}
	else
	{
		T = T + time;//进程未运行完时，时间按时间片照常增加
	}
}

void input()
{
	int i;
	printf("n 请输入运行的进程总数目:");
	scanf("%d", &num);
	numcopy = num;//将num的值赋给copy，在链表的最后两个单元节点时有用	
	printf("n 请输入时间片长度:");
	scanf("%d", &time);
	for ( i = 0; i < num; i++)
	{
		p = getpch(JCB);
		printf("n 请输入进程名称:");
		scanf("%s", p->name);
		printf("n 请输入进程提交时间:");
		scanf("%d", &p->tr);
		printf("n 请输入进程运行时间:");
		scanf("%d", &p->tn);
		printf("n");
		p->tf = 0;
		p->ts = 0;
		if (p->tn % time)//判断自己转圈所需的个数，最后一圈转不完的按一圈算
		{
			p->tc = p->tn / time + 1;
		}
		else
		{
			p->tc = p->tn / time;
		}
		p->wi = 0.0f;
		p->ti = 0.0f;
		p->flag = 1;
		p->link = NULL;
		linkpcb();
	}
	first->link = ready;//首尾连接做循环函数
}

void disp(JCB* pr)
{
	printf("%st", pr->name);
	printf("%dt", pr->tr);
	printf("%dt", pr->tn);
	printf("%dt", pr->ts);
	printf("%dt", pr->tf);
	printf("%f  ", pr->ti);
	printf("%ft", pr->wi);
	printf("n");
}

void check()
{
	p->ti = p->tf - p->tr;//周转
	p->wi = p->ti / p->tn;//带权周转
}

void destory()
{
	free(p);//同一单元节点只需要释放一次
	if (numcopy == 0)
	{
		first = NULL;
		ready = NULL;//清空指针，避免野指针出现
	}
}

void running()
{
	if (p->link == NULL)
	{
		destory();
	}
}

int main()
{
	float eti = 0.0;//平均周转时间
	float ewi = 0.0;//平均带权周转时间
	input();
	printf("n 名称 t 提交 t 运行 t 开始 t 完成 t 周转 t 带权周转 n");
	while (ready !=NULL)
	{
		p = ready;
		ready = p->link;//此处ready为下一个节点，first为上一个节点，p为当前节点

		if (T >= p->tr)
		{
			timeslicet(); //此函数将当前节点p从链表中摘除
		}
		else
		{
			T++;//时间每次循环+1
		}


		if (p->tc == 0)
		{
			check();//计算此时刻的周转时间
			disp(p);//输出此节点的值
			numcopy--;
			eti += p->ti;
			ewi += p->wi;
			p->link = NULL;
			running();
			//摘除p后first不动
		}
		else
		{
			first = p;//将first转移至当前节点处（当前没有摘除p）
		}
	}

	eti /= num;
	ewi /= num;
	printf("n该组作业平均周转时间为:%0.2f", eti);
	printf("n该组作业平均带权周转时间为:%0.2f", ewi);
	return 0;

}

        在销毁最后一个单元节点时，由于多个指针出现，需要同事进行释放，否则会出现野指针警告导致程序无法运行。