時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法C語言模擬實現(xiàn)

時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法C語言模擬實現(xiàn)一、目的和要求

進程調(diào)度是處理機管理的核心內(nèi)容。本實驗要求用高級語言編寫模擬進程調(diào)度程序，以便加深理解有關(guān)進程控制快、進程隊列等概念，并體會和了解優(yōu)先數(shù)算法和時間片輪轉(zhuǎn)算法的具體實施辦法。

二、實驗內(nèi)容

1.設(shè)計進程控制塊PCB的結(jié)構(gòu)，通常應(yīng)包括如下信息：

進程名、進程優(yōu)先數(shù)（或輪轉(zhuǎn)時間片數(shù)）、進程已占用的CPU時間、進程到完成還需要的時間、進程的狀態(tài)、當(dāng)前隊列指針等。

2.編寫兩種調(diào)度算法程序：

優(yōu)先數(shù)調(diào)度算法程序

循環(huán)輪轉(zhuǎn)調(diào)度算法程序

3.按要求輸出結(jié)果。

三、提示和說明

分別用兩種調(diào)度算法對伍個進程進行調(diào)度。每個進程可有三種狀態(tài)；執(zhí)行狀態(tài)（RUN）、就緒狀態(tài)（READY,包括等待狀態(tài)）和完成狀態(tài)（FINISH），并假定初始狀態(tài)為就緒狀態(tài)。

（一）進程控制塊結(jié)構(gòu)如下：

NAME——進程標示符

PRIO/ROUND——進程優(yōu)先數(shù)/進程每次輪轉(zhuǎn)的時間片數(shù)（設(shè)為常數(shù)2）

CPUTIME——進程累計占用CPU的時間片數(shù)

NEEDTIME——進程到完成還需要的時間片數(shù)

STATE——進程狀態(tài)

NEXT——鏈指針

注：

1.為了便于處理，程序中進程的的運行時間以時間片為單位進行計算；

2.各進程的優(yōu)先數(shù)或輪轉(zhuǎn)時間片數(shù)，以及進程運行時間片數(shù)的初值，均由用戶在程序運行時給定。

（二）進程的就緒態(tài)和等待態(tài)均為鏈表結(jié)構(gòu)，共有四個指針如下：

RUN——當(dāng)前運行進程指針

READY——就需隊列頭指針

TAIL——就需隊列尾指針

FINISH——完成隊列頭指針

（三）程序說明

1.在優(yōu)先數(shù)算法中，進程優(yōu)先數(shù)的初值設(shè)為：

50-NEEDTIME

每執(zhí)行一次，優(yōu)先數(shù)減1，CPU時間片數(shù)加1，進程還需要的時間片數(shù)減1。

在輪轉(zhuǎn)法中，采用固定時間片單位（兩個時間片為一個單位），進程每輪轉(zhuǎn)一次，CPU時間片數(shù)加2，進程還需要的時間片數(shù)減2，并退出CPU，排到就緒隊列尾，等待下一次調(diào)度。

2.程序的模塊結(jié)構(gòu)提示如下：

整個程序可由主程序和如下7個過程組成：

（1）INSERT1——在優(yōu)先數(shù)算法中，將尚未完成的PCB按優(yōu)先數(shù)順序插入到就緒隊列中；

（2）INSERT2——在輪轉(zhuǎn)法中，將執(zhí)行了一個時間片單位（為2），但尚未完成的進程的PCB，插到就緒隊列的隊尾；

（3）FIRSTIN——調(diào)度就緒隊列的第一個進程投入運行；

（4）PRINT——顯示每執(zhí)行一次后所有進程的狀態(tài)及有關(guān)信息。

（5）CREATE——創(chuàng)建新進程，并將它的PCB插入就緒隊列；

（6）PRISCH——按優(yōu)先數(shù)算法調(diào)度進程；

（7）ROUNDSCH——按時間片輪轉(zhuǎn)法調(diào)度進程。

主程序定義PCB結(jié)構(gòu)和其他有關(guān)變量。

（四）運行和顯示

程序開始運行后，首先提示：請用戶選擇算法，輸入進程名和相應(yīng)的NEEDTIME值。

每次顯示結(jié)果均為如下5個字段：

name

cputime

needtime

priority

state

注：

1．在state字段中，"R"代表執(zhí)行態(tài)，"W"代表就緒（等待）態(tài)，"F"代表完成態(tài)。

2．應(yīng)先顯示"R"態(tài)的，再顯示"W"態(tài)的，再顯示"F"態(tài)的。

3．在"W"態(tài)中，以優(yōu)先數(shù)高低或輪轉(zhuǎn)順序排隊；在"F"態(tài)中，以完成先后順序排隊。viewplaincopytoclipboardprint?/*

操作系統(tǒng)實驗之時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法

By

Visual

C++

6.0

*/

#include

<stdio.h>

#include

<stdlib.h>

#include

<string.h>

typedef

struct

node

{

char

name[20];

/*進程的名字*/

int

prio;

/*進程的優(yōu)先級*/

int

round;

/*分配CPU的時間片*/

int

cputime;

/*CPU執(zhí)行時間*/

int

needtime;

/*進程執(zhí)行所需要的時間*/

char

state;

/*進程的狀態(tài)，W——就緒態(tài)，R——執(zhí)行態(tài)，F(xiàn)——完成態(tài)*/

int

count;

/*記錄執(zhí)行的次數(shù)*/

struct

node

*next;

/*鏈表指針*/

}PCB;

PCB

*ready=NULL,*run=NULL,*finish=NULL;

/*定義三個隊列，就緒隊列，執(zhí)行隊列和完成隊列*/

int

num;

void

GetFirst();

/*從就緒隊列取得第一個節(jié)點*/

void

Output();

/*輸出隊列信息*/

void

InsertPrio(PCB

*in);

/*創(chuàng)建優(yōu)先級隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越高*/

void

InsertTime(PCB

*in);

/*時間片隊列*/

void

InsertFinish(PCB

*in);

/*時間片隊列*/

void

PrioCreate();

/*優(yōu)先級輸入函數(shù)*/

void

TimeCreate();

/*時間片輸入函數(shù)*/

void

Priority();

/*按照優(yōu)先級調(diào)度*/

void

RoundRun();

/*時間片輪轉(zhuǎn)調(diào)度*/

int

main(void)

{

char

chose;

printf("請輸入要創(chuàng)建的進程數(shù)目:\n");

scanf("%d",&num);

getchar();

printf("輸入進程的調(diào)度方法：(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()

/*取得第一個就緒隊列節(jié)點*/

{

run

=

ready;

if(ready!=NULL)

{

run

->state

=

'R';

ready

=

ready

->next;

run

->next

=

NULL;

}

}

void

Output()

/*輸出隊列信息*/

{

PCB

*p;

p

=

ready;

printf("進程名\t優(yōu)先級\t輪數(shù)\tcpu時間\t需要時間\t進程狀態(tài)\t計數(shù)器\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)

/*創(chuàng)建優(yōu)先級隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/

{

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)

/*已經(jīng)搜索到隊尾，則其優(yōu)先級數(shù)最小，將其插入到隊尾即可*/

{

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()

/*優(yōu)先級調(diào)度輸入函數(shù)*/

{

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;

/*設(shè)置其優(yōu)先級，需要的時間越多，優(yōu)先級越低*/

tmp

->round

=

0;

tmp

->count

=

0;

InsertPrio(tmp);

/*按照優(yōu)先級從高到低，插入到就緒隊列*/

}

}

void

TimeCreate()

/*時間片輸入函數(shù)*/

{

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;

/*假設(shè)每個進程所分配的時間片是2*/

tmp

->count

=

0;

InsertTime(tmp);

}

}

void

Priority()

/*按照優(yōu)先級調(diào)度，每次執(zhí)行一個時間片*/

{

int

flag

=

1;

GetFirst();

while(run

!=

NULL)

/*當(dāng)就緒隊列不為空時，則調(diào)度進程如執(zhí)行隊列執(zhí)行*/

{

Output();

/*輸出每次調(diào)度過程中各個節(jié)點的狀態(tài)*/

while(flag)

{

run->prio

-=

3;

/*優(yōu)先級減去三*/

run->cputime++;

/*CPU時間片加一*/

run->needtime--;/*進程執(zhí)行完成的剩余時間減一*/

if(run->needtime

==

0)/*如果進程執(zhí)行完畢，將進程狀態(tài)置為F，將其插入到完成隊列*/

{

run

->state

=

'F';

run->count++;

/*進程執(zhí)行的次數(shù)加一*/

InsertFinish(run);

flag

=

0;

}

else

/*將進程狀態(tài)置為W，入就緒隊列*/

{

run->state

=

'W';

run->count++;

/*進程執(zhí)行的次數(shù)加一*/

InsertT