一、算法實(shí)現(xiàn)流程圖：
二、實(shí)現(xiàn)思路：
#define q 1 //時(shí)間片
要求：
PCB必須按順序輸入，到達(dá)時(shí)間從小到大。
實(shí)現(xiàn)：
難點(diǎn)在于PCB就否到達(dá)就緒隊(duì)列的處理。
設(shè)標(biāo)識(shí)變量，處理就緒隊(duì)列，隊(duì)列內(nèi)有有效PCB和無效PCB（還未到達(dá)）
剛到達(dá)的PCB與執(zhí)行一次時(shí)間片之后的PCB排序問題：
課本解釋：當(dāng)該進(jìn)程的時(shí)間片耗盡或運(yùn)行完畢時(shí)，系統(tǒng)再次將CRU分配給隊(duì)首進(jìn)程（或新到達(dá)的緊迫進(jìn)程）。由此可保證就緒隊(duì)列中的所有進(jìn)程在一個(gè)確定的時(shí)間段內(nèi)，都能夠獲得一次CPU執(zhí)行。
因此：正確答案應(yīng)該是，新到達(dá)的進(jìn)程放就緒隊(duì)列（有效PCB）隊(duì)首。
執(zhí)行完隊(duì)頭（有效PCB就緒隊(duì)列的對(duì)頭元素）元素后，在插入就緒隊(duì)列，插入到有效PCB就緒隊(duì)列的尾部
時(shí)間計(jì)算：Time(CPU執(zhí)行總時(shí)間)還需要考慮CPU空閑時(shí)間（就緒隊(duì)列內(nèi)有效數(shù)據(jù)為0個(gè)時(shí)，且還有PCB未到達(dá)，就是計(jì)算CPU空閑時(shí)間的時(shí)候）
結(jié)束條件：必須是就緒隊(duì)列內(nèi)沒有PCB（可能存在就緒隊(duì)列內(nèi)含有未到達(dá)PCB）
三、測試
說明：本代碼只是針對(duì)課本給出的例子進(jìn)行編寫，因此會(huì)有很多漏洞?。?br>
也可測試同時(shí)到達(dá)。文章來源：http://www.zghlxwxcb.cn/news/detail-453785.html
四、代碼
（visual studio 2019）文章來源地址http://www.zghlxwxcb.cn/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 //時(shí)間片
/*
待實(shí)現(xiàn)：
PCB必須按順序輸入，到達(dá)時(shí)間從小到大。
思路：
1、新建標(biāo)志變量，是否到達(dá)狀態(tài)
2、處理就緒隊(duì)列，隊(duì)列內(nèi)有有效PCB和無效PCB（還未到達(dá)）
3、處理完隊(duì)頭（有效PCB就緒隊(duì)列的對(duì)頭元素）元素后，在插入就緒隊(duì)列，插入到有效PCB就緒隊(duì)列的尾部
4、結(jié)束條件：必須是就緒隊(duì)列內(nèi)沒有PCB
5、時(shí)間計(jì)算：除了-到達(dá)時(shí)間外，還需要考慮CPU空閑時(shí)間（就緒隊(duì)列內(nèi)有效數(shù)據(jù)為null時(shí)，就是計(jì)算空閑時(shí)間的時(shí)候）
問題：在一個(gè)進(jìn)程運(yùn)行一次時(shí)間片時(shí)，但還未結(jié)束，需要插入就緒隊(duì)列。
是先插入，還是先判斷一些其他進(jìn)程是否到達(dá)。（就緒隊(duì)列順序）
這里采用：先到達(dá)，即先刷新PCB狀態(tài)，在插入運(yùn)行時(shí)間片結(jié)束的PCB。
課本解釋：當(dāng)該進(jìn)程的時(shí)間片耗盡或運(yùn)行完畢時(shí)，系統(tǒng)再次將CRU分配給隊(duì)首進(jìn)程（或新到達(dá)的緊迫進(jìn)程）。由此可保證就緒隊(duì)列
中的所有進(jìn)程在一個(gè)確定的時(shí)間段內(nèi)，都能夠獲得一次CPU執(zhí)行。
因此：正確答案應(yīng)該是，新到達(dá)的進(jìn)程放隊(duì)首。
*/
struct pcb { /* 定義進(jìn)程控制塊PCB */
char state;//進(jìn)程狀態(tài) 就緒 W（Wait）、運(yùn)行R（Run）、或完成F（Finish）
int Atime=0;//到達(dá)時(shí)間，默認(rèn)同一時(shí)間到達(dá)
int ntime;//進(jìn)程運(yùn)行時(shí)間
int rtime;//已用CPU時(shí)間
int TF;//是否為就緒隊(duì)列內(nèi)的有效PCB，默認(rèn)有效
struct pcb* link;
//新建變量：是否到達(dá)的一個(gè)狀態(tài)
char name[10];//進(jìn)程名
}*ready = NULL, * p;
typedef struct pcb PCB;
int h = 0;//執(zhí)行時(shí)間片數(shù)
int Time = 0;//CPU運(yùn)行時(shí)間 利用Time記錄每個(gè)進(jìn)程的完成時(shí)間 (Time-Atime) 是周轉(zhuǎn)時(shí)間
float allAvgTime = 0;//累加所有進(jìn)程的帶權(quán)周轉(zhuǎn)時(shí)間
/* 當(dāng)該進(jìn)程的時(shí)間片耗盡或運(yùn)行完畢時(shí)，將該進(jìn)程插入有效就緒隊(duì)列*/
void sort()
{
PCB* first, * second;
if (ready == NULL||ready->TF==0) /*就緒隊(duì)列為空，或者進(jìn)程重新插入時(shí)，就緒隊(duì)列有效PCB為0，插入隊(duì)首*/
{
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必須按順序輸入，到達(dá)時(shí)間從小到大。*/
/* 建立進(jìn)程控制塊函數(shù)，按順序插入到就緒隊(duì)列中*/
void input()
{
int i, num;
system("cls"); /*清屏*/
printf("\n 請(qǐng)輸入建立的進(jìn)程數(shù)?");
scanf("%d", &num);
for (i = 0; i < num; i++)
{
printf("\n 進(jìn)程號(hào)No.%d:\n", i);
p = getpch(PCB);//申請(qǐng)結(jié)構(gòu)體PCB內(nèi)存空間
printf("\n 輸入進(jìn)程名:");
scanf("%s", &p->name);
printf("\n 輸入進(jìn)程到達(dá)時(shí)間:");
scanf("%d", &p->Atime);
printf("\n 輸入進(jìn)程運(yùn)行時(shí)間:");
scanf("%d", &p->ntime);
p->link = NULL;
p->state = 'w';
p->rtime = 0;
p->TF = 1;
printf("\n");
sort(); //調(diào)用sort函數(shù)，插入p進(jìn)程進(jìn)入ready隊(duì)列
}
}
/*查看就緒隊(duì)列中有多少進(jìn)程*/
int space()
{
int l = 0; PCB* pr = ready;
while (pr != NULL)
{
l++;
pr = pr->link;
}
return(l);
}
/*建立進(jìn)程顯示函數(shù),用于打印當(dāng)前進(jìn)程*/
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");
}
/* 建立進(jìn)程查看函數(shù) */
void check()
{
PCB* pr;
printf("\n **** 當(dāng)前正在運(yùn)行的進(jìn)程是:%s", p->name); /*顯示當(dāng)前運(yùn)行進(jìn)程*/
disp(p);//封裝
pr = ready;
printf("\n ****當(dāng)前就緒隊(duì)列狀態(tài)為:\n"); /*顯示就緒隊(duì)列狀態(tài)*/
while (pr != NULL)
{
disp(pr);//調(diào)用打印
pr = pr->link;
}
}
/*建立進(jìn)程撤消函數(shù)(進(jìn)程運(yùn)行結(jié)束,撤消進(jìn)程)*/
void destroy()
{
allAvgTime = allAvgTime + (float)(Time - p->Atime) / p->ntime;
printf("\n 進(jìn)程 [%s] 已完成.\n周轉(zhuǎn)時(shí)間為[%d ms]\n帶權(quán)周轉(zhuǎn)時(shí)間為[%.2f ms]\n", p->name,Time-p->Atime,(float)(Time - p->Atime)/p->ntime);
free(p);
}
/*在每次調(diào)用running中的sort前，刷新PCB的狀態(tài)（是否到達(dá)）*/
void flushed() {
PCB* traverse, * pre;
traverse = ready;
pre = NULL;
while (traverse != NULL&&traverse->TF==1) {
//只需將未到達(dá)的PCB置為0即可
if (traverse->Atime > Time) {//不應(yīng)該是finish時(shí)間，應(yīng)該是CPU執(zhí)行時(shí)間(h*q 比CPU執(zhí)行時(shí)間略大 暫時(shí)就這樣吧)
traverse->TF = 0;
}
//新到達(dá)的程序(數(shù)組)放就緒隊(duì)列隊(duì)頭
//記錄（front） 記錄第一個(gè)0-->1（left） 循環(huán)遍歷到最后一個(gè)0->1（rigth） 記錄后面鏈表（behind pre->behind)
//再將ready置為（left）
pre = traverse;
traverse = traverse->link;
}
//本程序只考慮一次改變一個(gè)PCB狀態(tài)（簡單）
if (traverse != NULL&& traverse->Atime <= Time) {
traverse->TF = 1;
if (pre != NULL) {
pre->link = traverse->link;
traverse->link = ready;
ready = traverse;
}
}
}
/* 建立進(jìn)程就緒函數(shù)(進(jìn)程運(yùn)行時(shí)間到,置就緒狀態(tài)*/
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;//未利用完時(shí)間片，完成跳出
}
p->state = 'F';
//新建一個(gè)周轉(zhuǎn)時(shí)間（同一時(shí)刻創(chuàng)建，所以周轉(zhuǎn)時(shí)間等于完成時(shí)間） ，記錄完成時(shí)間
// 根據(jù)周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間=帶權(quán)周轉(zhuǎn)時(shí)間
//如果剛好是時(shí)間片的整數(shù)倍，直接 當(dāng)前時(shí)間片*時(shí)間片數(shù)
//如果不是整數(shù)倍 則ntime%時(shí)間片+時(shí)間片
destroy(); /* 調(diào)用destroy函數(shù)*/
}
else
{
Time = Time + q;//未執(zhí)行完畢
p->state = 'w';//就緒
sort(); /*調(diào)用sort函數(shù)，重新插入到就緒隊(duì)列*/
flushed();//每次都要重新判斷是否有PCB到達(dá)， 到達(dá)直接插入隊(duì)首.
}
}
void main() /*主函數(shù)*/
{
int len;
char ch;
input();//建立PCB
len = space();
flushed();//PCB狀態(tài)刷新
while ((len != 0) && (ready != NULL))
{
ch = getchar();
h++;
printf("\n The execute number:%d \n", h);
if (ready->TF == 0) {//就緒隊(duì)列內(nèi)沒有有效PCB
//這里只需加上CPU空閑時(shí)間即可 第一個(gè)無效進(jìn)程的到達(dá)時(shí)間-上一個(gè)完成進(jìn)程的完成（注意是完成）時(shí)間
//Time= Time+(ready->Atime - Time);
Time = ready->Atime;
//將第一個(gè)無效PCB改為有效PCB
ready->TF = 1;
}
else {
p = ready;
ready = p->link;
p->link = NULL;
p->state = 'R';
check();
running();
printf("\n 按任一鍵繼續(xù)......");
ch = getchar();
}
}
printf("\n\n 進(jìn)程已經(jīng)完成.\n");
printf("系統(tǒng)的平均帶權(quán)周轉(zhuǎn)時(shí)間為【%.2f ms】", allAvgTime / len);
ch = getchar();
}
到了這里，關(guān)于“時(shí)間片輪轉(zhuǎn)”調(diào)度算法（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
