基于優(yōu)先級(jí)的時(shí)間片輪轉(zhuǎn)調(diào)度算法
- PCB結(jié)構(gòu)（Block）
pcb
由此定義如下結(jié)構(gòu)體：
typedef struct Block
{
int processID; // 進(jìn)程號(hào)
int priority; // 優(yōu)先級(jí)
int status; // 狀態(tài)
double arrivalTime; // 到達(dá)時(shí)間
double serviceTime; // 服務(wù)時(shí)間
double runTime; // 已運(yùn)行時(shí)間
struct Block *next; // Next Block
} Block;
- 數(shù)據(jù)結(jié)構(gòu)（隊(duì)列）
隊(duì)列
typedef struct Link
{
struct Block *first; // 指向隊(duì)頭
struct Block *last; // 指向隊(duì)尾
} Link;
隊(duì)列操作函數(shù)：
- initLink：初始化隊(duì)列
void initLink(Link *l)
{
// 分配空間并檢測(cè)是否成功
l->first = l->last = (Block *)malloc(sizeof(Block));
if (!l->first)
{
fprintf(stderr, "Malloc Error!\n");
exit(-1);
}
// 空隊(duì)列
l->first->next = NULL;
l->last->next = NULL;
}
- isEmpty：判斷隊(duì)列是否為空
int isEmpty(Link *l)
{
return l->first->next == NULL? 1: 0;
}
- printLInk：輸出隊(duì)列中所有元素的信息
void printLink(Link *l)
{
Block *p = l->first->next;
// 遍歷隊(duì)列并輸出
printf ("\nProcess ID\tPriority\tArrival Time\tService Time\tRun Time\tStatus\n");
while (p != NULL)
{
printf("\t%d\t%d\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%s\n", \
p->processID, p->priority, p->arrivalTime, \
p->serviceTime, p->runTime, p->status == 0? "ready": "finished");
p = p->next;
}
}
- removeFirst：將隊(duì)列中第一個(gè)元素中的數(shù)據(jù)復(fù)制到給定參數(shù)中（用于返回）蘸秘，并刪除
void removeFirst(Link *l, Block *b)
{
Block *t;
// 空隊(duì)列則直接返回
if (isEmpty(l))
{
return ;
}
// t指向第二個(gè)Block乾胶，用于之后將隊(duì)列接上
t = l->first->next->next;
// 將第一個(gè)Block中的內(nèi)容復(fù)制到b中礁芦，用于返回
b->processID = l->first->next->processID;
b->priority = l->first->next->priority;
b->arrivalTime = l->first->next->arrivalTime;
b->serviceTime = l->first->next->serviceTime;
b->runTime = l->first->next->runTime;
b->status = l->first->next->status;
// 釋放第一個(gè)Block牍帚，并把隊(duì)列接上
free (l->first->next);
l->first->next = t;
}
- append：將新的元素添加到隊(duì)尾
void append(Link *l, Block *b)
{
Block *t;
// 分配空間葫督，并檢測(cè)是否成功
t = (Block *)malloc(sizeof(Block));
if (t == NULL)
{
fprintf(stderr, "Malloc Error!\n");
exit(-1);
}
// 將b中的內(nèi)容復(fù)制到t中
t->processID = b->processID;
t->priority = b->priority;
t->arrivalTime = b->arrivalTime;
t->serviceTime = b->serviceTime;
t->runTime = b->runTime;
t->status = b->status;
// 將t接到隊(duì)尾
t->next = NULL;
l->last->next = t;
l->last = t;
}
- deleteLinkItem：刪除隊(duì)列中指定的元素
void deleteLinkItem(Link *l, Block *target)
{
Block *p, *t;
// 遍歷隊(duì)列牺弄，尋找目標(biāo)Block
p = l->first;
while (p != NULL && p != target)
{
t = p;
p = p->next;
}
// 若存在聋丝，則釋放
if (p != NULL)
{
t->next = p->next;
free(p);
}
}
- sortByArrivalTime：根據(jù)進(jìn)程到達(dá)時(shí)間將隊(duì)列排序（從小到大）
void sortByArrivalTime(Link *l, int order)
{
Block *p, *q, *tp, *tq;
Block *temp, *min, *tmin;
int minArrivalTime;
// 這里使用了選擇排序
tp = tq = l->first;
p = q = l->first->next;
while (p != NULL)
{
// 這個(gè)數(shù)字可以修改的大一點(diǎn)棉姐。。庵楷。
minArrivalTime = 9999;
while (q != NULL)
{
// 尋找最小到達(dá)時(shí)間的Block
if (q->arrivalTime < minArrivalTime)
{
minArrivalTime = q->arrivalTime;
tmin = tq;
min = q;
}
tq = q;
q = q->next;
}
// 若尋找的Block與當(dāng)前Block不是同一個(gè)則交換
if (p != min)
{
tp->next = min;
tmin->next = p;
temp = min->next;
min->next = p->next;
p->next = temp;
}
tp = tq = p;
p = q = p->next;
}
}
- 基于優(yōu)先級(jí)的時(shí)間片輪轉(zhuǎn)調(diào)度算法
- 流程圖
流程圖
- 算法
void RR(Link *l, Link *r)
{
Block *p, *t;
double maxPriority;
double currentTime = 0;
int selected, timeSlice;
// 種下隨機(jī)種子
srand((unsigned)time(NULL));
// 遍歷隊(duì)列
t = p = l->first->next;
while (p != NULL)
{
// 輸出在當(dāng)前時(shí)間已到達(dá)的進(jìn)程Block信息
printf ("\nProcess ID\tPriority\tArrival Time\tService Time\tRun Time\tStatus\n");
selected = 0;
maxPriority = 9999;
while (p != NULL && currentTime >= p->arrivalTime)
{
selected = 1;
printf("\t%d\t%d\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%s\n", \
p->processID, p->priority, p->arrivalTime, \
p->serviceTime, p->runTime, p->status == 0? "ready": "finished");
// 尋找優(yōu)先級(jí)最高的進(jìn)程
if (p->priority < maxPriority)
{
maxPriority = p->priority;
t = p;
}
p = p->next;
}
// 生成隨機(jī)時(shí)間片
timeSlice = rand() % 10;
if (selected)
{
// 運(yùn)行進(jìn)程（模擬）
printf("Current time: %.0lf, Selected process: %d\n", currentTime, t->processID);
t->runTime += timeSlice;
t->priority += 2;
// 若進(jìn)程已經(jīng)結(jié)束罢艾，則將該進(jìn)程添加到完成隊(duì)列，并從當(dāng)前隊(duì)列中刪除
if (t->runTime >= t->serviceTime)
{
t->status = 1;
currentTime += t->serviceTime - (t->runTime - timeSlice);
t->runTime = t->serviceTime;
append(r, t);
deleteLinkItem(l, t);
}
}
else
{
currentTime += timeSlice;
}
// 打印完成隊(duì)列
printLink(r);
t = p = l->first->next;
}
}
- 測(cè)試與結(jié)果
- 測(cè)試數(shù)據(jù)
測(cè)試數(shù)據(jù)
- 測(cè)試結(jié)果
1
2
3
4
5
