一、算法实现流程图：
二、实现思路：
#define q 1 //时间片
要求：
PCB必须按顺序输入，到达时间从小到大。
实现：
难点在于PCB就否到达就绪队列的处理。
设标识变量，处理就绪队列，队列内有有效PCB和无效PCB（还未到达）
刚到达的PCB与执行一次时间片之后的PCB排序问题：
课本解释：当该进程的时间片耗尽或运行完毕时，系统再次将CRU分配给队首进程（或新到达的紧迫进程）。由此可保证就绪队列中的所有进程在一个确定的时间段内，都能够获得一次CPU执行。
因此：正确答案应该是，新到达的进程放就绪队列（有效PCB）队首。
执行完队头（有效PCB就绪队列的对头元素）元素后，在插入就绪队列，插入到有效PCB就绪队列的尾部
时间计算：Time(CPU执行总时间)还需要考虑CPU空闲时间（就绪队列内有效数据为0个时，且还有PCB未到达，就是计算CPU空闲时间的时候）
结束条件：必须是就绪队列内没有PCB（可能存在就绪队列内含有未到达PCB）
三、测试
说明：本代码只是针对课本给出的例子进行编写，因此会有很多漏洞！！
也可测试同时到达。文章来源：https://www.toymoban.com/news/detail-453785.html
四、代码
（visual studio 2019）文章来源地址https://www.toymoban.com/news/detail-453785.html
#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#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();
}
到了这里，关于“时间片轮转”调度算法（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
