進程調度是處理機管理的核心內容。本實驗要求用高級語言編寫模擬進程調度程序，以便加深理解有關進程控制快、進程隊列等概念，並體會和了解優先數算法和時間片輪轉算法的具體實施辦法。
二、實驗內容
1.設計進程控制塊PCB的結構，通常應包括如下信息：
進程名、進程優先數（或輪轉時間片數）、進程已占用的CPU時間、進程到完成還需要的時間、進程的狀態、當前隊列指針等。
2.編寫兩種調度算法程序：
優先數調度算法程序
循環輪轉調度算法程序
3.按要求輸出結果。
三、提示和說明
分別用兩種調度算法對伍個進程進行調度。每個進程可有三種狀態；執行狀態（RUN）、就緒狀態（READY,包括等待狀態）和完成狀態（FINISH），並假定初始狀態為就緒狀態。
（壹）進程控制塊結構如下：
NAME——進程標示符
PRIO/ROUND——進程優先數/進程每次輪轉的時間片數（設為常數2）
CPUTIME——進程累計占用CPU的時間片數
NEEDTIME——進程到完成還需要的時間片數
STATE——進程狀態
NEXT——鏈指針
註：
1.為了便於處理，程序中進程的的運行時間以時間片為單位進行計算；
2.各進程的優先數或輪轉時間片數，以及進程運行時間片數的初值，均由用戶在程序運行時給定。
（二）進程的就緒態和等待態均為鏈表結構，***有四個指針如下：
RUN——當前運行進程指針
READY——就需隊列頭指針
TAIL——就需隊列尾指針
FINISH——完成隊列頭指針
（三）程序說明
1. 在優先數算法中，進程優先數的初值設為：
50-NEEDTIME
每執行壹次，優先數減1，CPU時間片數加1，進程還需要的時間片數減1。
在輪轉法中，采用固定時間片單位（兩個時間片為壹個單位），進程每輪轉壹次，CPU時間片數加2，進程還需要的時間片數減2，並退出CPU，排到就緒隊列尾，等待下壹次調度。
2. 程序的模塊結構提示如下：
整個程序可由主程序和如下7個過程組成：
（1）INSERT1——在優先數算法中，將尚未完成的PCB按優先數順序插入到就緒隊列中；
（2）INSERT2——在輪轉法中，將執行了壹個時間片單位（為2），但尚未完成的進程的PCB，插到就緒隊列的隊尾；
（3）FIRSTIN——調度就緒隊列的第壹個進程投入運行；
（4）PRINT——顯示每執行壹次後所有進程的狀態及有關信息。
（5）CREATE——創建新進程，並將它的PCB插入就緒隊列；
（6）PRISCH——按優先數算法調度進程；
（7）ROUNDSCH——按時間片輪轉法調度進程。
主程序定義PCB結構和其他有關變量。
（四）運行和顯示
程序開始運行後，首先提示：請用戶選擇算法，輸入進程名和相應的NEEDTIME值。
每次顯示結果均為如下5個字段：
name cputime needtime priority state
註：
1．在state字段中，"R"代表執行態，"W"代表就緒（等待）態，"F"代表完成態。
2．應先顯示"R"態的，再顯示"W"態的，再顯示"F"態的。
3．在"W"態中，以優先數高低或輪轉順序排隊；在"F"態中，以完成先後順序排隊。
view plaincopy to clipboardprint?
/*
操作系統實驗之時間片輪轉算法和優先級調度算法
By Visual C++ 6.0
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
char name[20]; /*進程的名字*/
int prio; /*進程的優先級*/
int round; /*分配CPU的時間片*/
int cputime; /*CPU執行時間*/
int needtime; /*進程執行所需要的時間*/
char state; /*進程的狀態，W——就緒態，R——執行態，F——完成態*/
int count; /*記錄執行的次數*/
struct node *next; /*鏈表指針*/
}PCB;
PCB *ready=NULL,*run=NULL,*finish=NULL; /*定義三個隊列，就緒隊列，執行隊列和完成隊列*/
int num;
void GetFirst(); /*從就緒隊列取得第壹個節點*/
void Output(); /*輸出隊列信息*/
void InsertPrio(PCB *in); /*創建優先級隊列，規定優先數越小，優先級越高*/
void InsertTime(PCB *in); /*時間片隊列*/
void InsertFinish(PCB *in); /*時間片隊列*/
void PrioCreate(); /*優先級輸入函數*/
void TimeCreate(); /*時間片輸入函數*/
void Priority(); /*按照優先級調度*/
void RoundRun(); /*時間片輪轉調度*/
int main(void)
{
char chose;
printf("請輸入要創建的進程數目:\n");
scanf("%d",&num);
getchar();
printf("輸入進程的調度方法：(P/R)\n");
scanf("%c",&chose);
switch(chose)
{
case 'P':
case 'p':
PrioCreate();
Priority();
break;
case 'R':
case 'r':
TimeCreate();
RoundRun();
break;
default:break;
}
Output();
return 0;
}
void GetFirst() /*取得第壹個就緒隊列節點*/
{
run = ready;
if(ready!=NULL)
{
run ->state = 'R';
ready = ready ->next;
run ->next = NULL;
}
}
void Output() /*輸出隊列信息*/
{
PCB *p;
p = ready;
printf("進程名\t優先級\t輪數\tcpu時間\t需要時間\t進程狀態\t計數器\n");
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
p = finish;
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
p = run;
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
}
void InsertPrio(PCB *in) /*創建優先級隊列，規定優先數越小，優先級越低*/
{
PCB *fst,*nxt;
fst = nxt = ready;
if(ready == NULL) /*如果隊列為空，則為第壹個元素*/
{
in->next = ready;
ready = in;
}
else /*查到合適的位置進行插入*/
{
if(in ->prio >= fst ->prio) /*比第壹個還要大，則插入到隊頭*/
{
in->next = ready;
ready = in;
}
else
{
while(fst->next != NULL) /*移動指針查找第壹個別它小的元素的位置進行插入*/
{
nxt = fst;
fst = fst->next;
}
if(fst ->next == NULL) /*已經搜索到隊尾，則其優先級數最小，將其插入到隊尾即可*/
{
in ->next = fst ->next;
fst ->next = in;
}
else /*插入到隊列中*/
{
nxt = in;
in ->next = fst;
}
}
}
}
void InsertTime(PCB *in) /*將進程插入到就緒隊列尾部*/
{
PCB *fst;
fst = ready;
if(ready == NULL)
{
in->next = ready;
ready = in;
}
else
{
while(fst->next != NULL)
{
fst = fst->next;
}
in ->next = fst ->next;
fst ->next = in;
}
}
void InsertFinish(PCB *in) /*將進程插入到完成隊列尾部*/
{
PCB *fst;
fst = finish;
if(finish == NULL)
{
in->next = finish;
finish = in;
}
else
{
while(fst->next != NULL)
{
fst = fst->next;
}
in ->next = fst ->next;
fst ->next = in;
}
}
void PrioCreate() /*優先級調度輸入函數*/
{
PCB *tmp;
int i;
printf("輸入進程名字和進程所需時間：\n");
for(i = 0;i < num; i++)
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)
{
perror("malloc");
exit(1);
}
scanf("%s",tmp->name);
getchar(); /*吸收回車符號*/
scanf("%d",&(tmp->needtime));
tmp ->cputime = 0;
tmp ->state ='W';
tmp ->prio = 50 - tmp->needtime; /*設置其優先級，需要的時間越多，優先級越低*/
tmp ->round = 0;
tmp ->count = 0;
InsertPrio(tmp); /*按照優先級從高到低，插入到就緒隊列*/
}
}
void TimeCreate() /*時間片輸入函數*/
{
PCB *tmp;
int i;
printf("輸入進程名字和進程時間片所需時間：\n");
for(i = 0;i < num; i++)
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)
{
perror("malloc");
exit(1);
}
scanf("%s",tmp->name);
getchar();
scanf("%d",&(tmp->needtime));
tmp ->cputime = 0;
tmp ->state ='W';
tmp ->prio = 0;
tmp ->round = 2; /*假設每個進程所分配的時間片是2*/
tmp ->count = 0;
InsertTime(tmp);
}
}
void Priority() /*按照優先級調度，每次執行壹個時間片*/
{
int flag = 1;
GetFirst();
while(run != NULL) /*當就緒隊列不為空時，則調度進程如執行隊列執行*/
{
Output(); /*輸出每次調度過程中各個節點的狀態*/
while(flag)
{
run->prio -= 3; /*優先級減去三*/
run->cputime++; /*CPU時間片加壹*/
run->needtime--;/*進程執行完成的剩余時間減壹*/
if(run->needtime == 0)/*如果進程執行完畢，將進程狀態置為F，將其插入到完成隊列*/
{
run ->state = 'F';
run->count++; /*進程執行的次數加壹*/
InsertFinish(run);
flag = 0;
}
else /*將進程狀態置為W，入就緒隊列*/
{
run->state = 'W';
run->count++; /*進程執行的次數加壹*/
InsertTime(run);
flag = 0;
}
}
flag = 1;
GetFirst(); /*繼續取就緒隊列隊頭進程進入執行隊列*/
}
}
void RoundRun() /*時間片輪轉調度算法*/
{
int flag = 1;
GetFirst();
while(run != NULL)
{
Output();
while(flag)
{
run->count++;
run->cputime++;
run->needtime--;
if(run->needtime == 0) /*進程執行完畢*/
{
run ->state = 'F';
InsertFinish(run);
flag = 0;
}
else if(run->count == run->round)/*時間片用完*/
{
run->state = 'W';
run->count = 0; /*計數器清零，為下次做準備*/
InsertTime(run);
flag = 0;
}
}
flag = 1;
GetFirst();
}