一.課程概述

1.1.設(shè)計(jì)設(shè)想

程序可以完畢如下操作：創(chuàng)立進(jìn)程：先輸入進(jìn)程的數(shù)目，再■■次輸入每個(gè)進(jìn)程的進(jìn)程名、

運(yùn)行總時(shí)間和優(yōu)先級(jí)，先抵達(dá)的先輸入；進(jìn)程調(diào)度：進(jìn)程創(chuàng)立完畢后就選擇進(jìn)程調(diào)度算法，

并單步執(zhí)行，每次執(zhí)行的成果都從屏幕上輸出來(lái)。

12需求分析

在多道程序環(huán)境下，主存中有著多種進(jìn)程，其數(shù)目往往多于處理機(jī)數(shù)目，要使這多種進(jìn)程可

以并發(fā)地執(zhí)行，這就規(guī)定系統(tǒng)能按某種算法,動(dòng)態(tài)地把處理機(jī)分派給就緒隊(duì)列中的一種進(jìn)程,

使之執(zhí)行。分派處理機(jī)的任務(wù)是由處理機(jī)調(diào)度程序完畢的。由于處理機(jī)是最重:要的計(jì)算機(jī)資

源，提高處理機(jī)的運(yùn)用率及改善系統(tǒng)必(存吐量、響應(yīng)時(shí)間)，在很大程度上取決于處理機(jī)

調(diào)度性能H勺好壞，因而，處理機(jī)調(diào)度便成為操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。本次試驗(yàn)在

VC++6.0環(huán)境下實(shí)現(xiàn)先來(lái)先朋務(wù)調(diào)度算法，短作業(yè)優(yōu)先調(diào)度算法，高優(yōu)先權(quán)調(diào)度算法，時(shí)間

片輪轉(zhuǎn)調(diào)度算法和多級(jí)反饋隊(duì)列調(diào)度算法。

1.3.理論根據(jù)

為了描述和管制進(jìn)程的運(yùn)行，系統(tǒng)為每個(gè)進(jìn)程定義了一種數(shù)據(jù)構(gòu)造一一進(jìn)程控制塊

PCB(ProcessControlBlock),PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程H勺目前狀況以及控

制進(jìn)程運(yùn)行的所有信息，系統(tǒng)總是通過(guò)PCB對(duì)進(jìn)程進(jìn)行控制，亦即，系統(tǒng)是根據(jù)進(jìn)程的PCB

而不是任何別H勺什么而感知進(jìn)程的存在的，PCB是進(jìn)程存在的惟一標(biāo)志。本次課程設(shè)計(jì)用

構(gòu)造體Process替代PCB的功能。

14課程任務(wù)

一、用C語(yǔ)言（或C++）編程實(shí)現(xiàn)操作模擬操作系統(tǒng)進(jìn)程調(diào)度子系統(tǒng)的基本功能：運(yùn)用多

種算:法實(shí)現(xiàn)對(duì)進(jìn)程的模擬調(diào)度。

二、通過(guò)編寫程序?qū)崿F(xiàn)進(jìn)程或作業(yè)先來(lái)先服務(wù)、高優(yōu)先權(quán)、準(zhǔn)時(shí)間片輪轉(zhuǎn)、短作業(yè)優(yōu)先、多

級(jí)反饋隊(duì)列調(diào)度算法，使學(xué)生深入掌握進(jìn)程調(diào)度的概念和算法，加深對(duì)處理機(jī)分派的理

解。

三、實(shí)現(xiàn)顧客界面的開(kāi)發(fā)

1.5.功能模塊分析：

1、進(jìn)程概念：進(jìn)程是被獨(dú)立分派資源日勺最小單位。進(jìn)程是動(dòng)態(tài)概念，必須程序運(yùn)行才有

進(jìn)程的產(chǎn)生。

2、進(jìn)程的狀態(tài)模型：

（1）運(yùn)行：進(jìn)程已獲得處理機(jī)，目前處在運(yùn)行狀態(tài)。

（2）就緒：進(jìn)程已經(jīng)在備好，一旦有處理器就可運(yùn)行。

3、處理機(jī)調(diào)度：在多道程序設(shè)計(jì)系統(tǒng)中，內(nèi)存中有多道程序運(yùn)行，他們互相爭(zhēng)奪處理機(jī)

這?重要的費(fèi)源。處理機(jī)調(diào)度就是從就緒隊(duì)列中，按照?定的算法選擇?種進(jìn)程并將

處理機(jī)分派給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程并發(fā)地執(zhí)行。

4、進(jìn)程調(diào)度算法的功能:

記錄系統(tǒng)中所有進(jìn)程的執(zhí)行狀況

選擇占有處理機(jī)的進(jìn)程

進(jìn)行進(jìn)程的上下文切換

5、進(jìn)程調(diào)度的算法：

（1）先來(lái)先服務(wù)算法：假如中就緒的進(jìn)程排在就緒隊(duì)列的前面，遲就緒的進(jìn)程排在

就緒隊(duì)列的I背面，那么先來(lái)先服務(wù)總是把目前處在就緒隊(duì)列之首的那個(gè)進(jìn)程調(diào)

度到運(yùn)行狀態(tài)。

（2）優(yōu)先數(shù)算法：即進(jìn)程的執(zhí)行次序由高優(yōu)先級(jí)到低優(yōu)先級(jí)。系統(tǒng)或顧客按某種原

則為進(jìn)程指定一種優(yōu)先級(jí)來(lái)表達(dá)該進(jìn)程所享有確實(shí)調(diào)度優(yōu)先權(quán)。該算法關(guān)鍵是

確定進(jìn)程H勺優(yōu)先級(jí)。

（3）時(shí)間片輪轉(zhuǎn)算法：固定期間片，每個(gè)進(jìn)程在執(zhí)行一種時(shí)間片后，輪到下一進(jìn)程

執(zhí)行，懂得所有的進(jìn)程執(zhí)行完畢。處理器同一種時(shí)間只能處理一種任務(wù)。處理

瑞在處理多任務(wù)的時(shí)候，就要看祈求的時(shí)間次序，假如時(shí)間?致，就要進(jìn)行預(yù)

測(cè)。挑到一種任務(wù)后，需要若干環(huán)節(jié)才能做完，這些環(huán)節(jié)中有些需要處理器參

與，有些不需要［如磁盤控制器的存儲(chǔ)過(guò)程）。不需要處理器處理的時(shí)候，這部

分時(shí)間就要分派給其他的進(jìn)程。本來(lái)的進(jìn)程就要處在等待打勺時(shí)間段上。通過(guò)周

密分派時(shí)間，宏觀上就象是多種任務(wù)一起運(yùn)行同樣，但微觀上是有先后的，就

是時(shí)間片輪換。

（4）多級(jí)反饋隊(duì)列法：又稱反饋循環(huán)隊(duì)列或多隊(duì)列方略，羽要思想是將就緒進(jìn)程分

為兩級(jí)或多級(jí)，系統(tǒng)對(duì)應(yīng)建立兩個(gè)或多種就緒進(jìn)程隊(duì)列，較高優(yōu)先級(jí)口勺隊(duì)列一

般分派給較短的時(shí)間片。處理器調(diào)度先從高級(jí)就緒進(jìn)程隊(duì)列中選用可占有處理

器的進(jìn)程，只有在選不屆時(shí)，才從較低級(jí)的就緒進(jìn)程隊(duì)列中選用。

（5）短作'也優(yōu)先法：對(duì)短進(jìn)程優(yōu)先調(diào)度的算法，它是從后備隊(duì)列中選擇一種或者若

干個(gè)進(jìn)程，將處理機(jī)分派給它，使它立即執(zhí)行并一直執(zhí)行到完畢，或發(fā)生某事

件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。

二.設(shè)計(jì)方案

2.1.先來(lái)先服務(wù)調(diào)度

.算法思想

先來(lái)先服務(wù)調(diào)度算法的思想是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序調(diào)度并分派處理機(jī)執(zhí)

行。先來(lái)先服務(wù)調(diào)度算法是一種不可搶占的算法，先進(jìn)入就緒隊(duì)列的進(jìn)程，先被處理機(jī)運(yùn)行。

一旦一種進(jìn)程占有了處理機(jī)，它就一直運(yùn)行下去，直到該進(jìn)程完畢工作或者由于等待某事件

而不能繼續(xù)運(yùn)行時(shí)才釋放處理機(jī)。

.算法流程圖

圖I.先來(lái)先服務(wù)算法流程圖

?程序代碼

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedefstructnode

charname[IOJ;/*進(jìn)程名

intcputime;/*占用cpu時(shí)間

charstarttime[5];〃進(jìn)程開(kāi)始時(shí)間

intneedtime;規(guī)定運(yùn)行時(shí)間

charstate;/*狀態(tài)*/

structnode"next;/*指針*/

}PCB;

PCB*ready,*run,*finish;〃就緒、執(zhí)行、結(jié)束指針

intN;〃進(jìn)程數(shù)量

voidprint()〃輸出函數(shù)

(

PCB*p;

printf("NAMECPUTIMESTARTTIMENEEDTIMESTATUSXn,);

if(run!=NULL)

printf("%-1Os%-K)d%-10s%-10d%c\n",

run->name,

inn->cputime,

run->star(tiinc.

i-un->needtime.

run->statc);/*輸出執(zhí)行H勺進(jìn)程的信息*/

p=ready;

while(p!=NULL)

(

printf("%10s%10d%10s%lOd%c\n",

p->namc,

p->cputime,

p->starttimc.

p->needtime,

p->state);體輸出就緒進(jìn)程的信息*/

p=p->next;

)

p=finish;

while(p!=NULL)

(

printfC%-1Os%-K)d%-10s%-10d%c\n",

p->namc,

p->cputime,

p->starttime,

p->needtime.

p->sta(c);產(chǎn)輸出結(jié)束隊(duì)列的信息*/

p=p->next;

)

getchar();/*使用gelchar。函數(shù)可以讓輸出時(shí)停留畫面，

等待人按回車?yán)^續(xù)列

}

voidinsert(PCB*q)/*插入新進(jìn)程，把進(jìn)程按進(jìn)程到來(lái)時(shí)間大小排序力

]

PCB*pl,*s,*r;

intb;

s=q;/*指針s指向新要插入的進(jìn)程*/

p1=ready;/*指針pl指向本來(lái)的進(jìn)程隊(duì)列日勺隊(duì)首列

r=pl;/*使用指針r是指向pl前面的進(jìn)程*/

b=l;

while((pl!=NULL)&&b)

if(strcmp(p1->stailtime,s->starttime)<0)

(

r=pl;pl=pl->next;

}/*新進(jìn)程H勺開(kāi)始時(shí)間大，則pl指向下一種進(jìn)程繼續(xù)比*/

else

b=0;

if(r*=pD

(

r->next=s;s->next=pl;

}新進(jìn)程找到位置，插在r和pl之間*/

else

(

s->next=pl;rcady=s;

}產(chǎn)新進(jìn)程的開(kāi)始時(shí)間按最小，插在隊(duì)首，并修改就緒隊(duì)首ready指針*/

)

voidcreate()

(

PCB*p;

inti;

rcady=NULL;

run=NULL;

finish=NULL;

printf("PleaseenterthenameandtimeandstalltimeofPCB:\n');

產(chǎn)輸入進(jìn)程名、運(yùn)行時(shí)間和開(kāi)始時(shí)間*/

for(i=0;i<N;i++)

p=(PCB*)malloc(sizeof(PCB));/*為新進(jìn)程開(kāi)辟空間*/

scanf("%s",p->name);/*輸入進(jìn)程名*/

scanf("%d",&p->need(ime):/*輸入進(jìn)程規(guī)定運(yùn)行時(shí)間*/

scanf("%s",pAstarttime);〃輸入進(jìn)程開(kāi)始時(shí)間

p->cpu(imc=O;

p->state='W;/*表達(dá)就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)刃

if(ready!=NULL)

insert(p);/*就緒隊(duì)首不為NULL,插入新進(jìn)程*/

else

{/*否則先插在NULL前*/

p->next=ready;

ready=p;

}

printf("Displayisgoingtostart:\n");

printf(''***********************************************\n”);

print();

gctcharO;

run=ready;/*隊(duì)列排好?run指向就緒隊(duì)列隊(duì)首*/

rcady=rcady->ncxt;/*rcady指I句下一種進(jìn)程*/

run->state='R':/*隊(duì)首在程的狀態(tài)為就緒*/

)

voidFCFS()

(

while(run!=NULL)

(

run->cputimc=run->cputimc+run->nccdtime;

!-un->needtime=O;

run->next=finish;

finish=run;

riin->state='E';

run=NULL;

if(ready!=NULL)

(

run=ready;

run->state='R';

ready=ready->next;

print();

)

voidniain()

(

printf("PleaseenterthetotalnumberofPCB:\n");

scanf("%d",&N);

create();/*模擬創(chuàng)立進(jìn)程，并輸入有關(guān)信息*/

FCFSO;產(chǎn)先來(lái)先服務(wù)調(diào)度算法*/

.測(cè)試成果及闡明

首先輸入進(jìn)程個(gè)數(shù)(為5個(gè))，這里命名為A,B,C,D,E,然后分別輸入運(yùn)行時(shí)間和開(kāi)始時(shí)間

PleaseenterthetotalnumberofPCB：

5

PleaseenterthenameandtineandstarttineofPCB：

A84

B118

C53

D109

E1213

所有進(jìn)程都在隊(duì)列中，并都處在等待狀態(tài)

NAMECPUTIMESTARTTIMENEEDTIMESTATUS

E01312W

C035W

A048U

B0811U

D0910W

其中一種進(jìn)程執(zhí)行完畢

NAMECPUTIMESTARTTIMENEEDTIMESTATUS

C035R

A048W

B0811W

D0910w

E12130E

所有進(jìn)程都執(zhí)行完畢

NAMECPUTIMESTARTTIMENEEDTIMESTATUS

D1090E

B1180E

A840E

C530E

E12130E

2.2.優(yōu)先級(jí)調(diào)度

2.2.1.算法思想

進(jìn)程的執(zhí)行次序由高優(yōu)先級(jí)到低優(yōu)先級(jí)，系統(tǒng)或顧客按某種原則為進(jìn)程指定

一種優(yōu)先級(jí)來(lái)表達(dá)該進(jìn)程所享有確實(shí)調(diào)度優(yōu)先權(quán)。該算法關(guān)鍵是確定進(jìn)程H勺優(yōu)先

級(jí)。

圖2.優(yōu)先級(jí)調(diào)度流程圖

2.2.3.程序代碼

#include<stdio.h>

^include<stdlib.h>

^include<string.h>

typedefstructnode

{charname[10];/*進(jìn)程名*/

intprio;"優(yōu)先數(shù)*/

intcputime;/*占用epu時(shí)間*/

intneedtime;"規(guī)定運(yùn)行時(shí)間*/

charstate;/*狀態(tài)*/

structnode*next;/*指針*/

}PCB;

PCB*ready,*run,*finish;/*就緒執(zhí)行結(jié)束指針*/

intN;

voidprtO/*輸出函數(shù)，可以以便看到進(jìn)程執(zhí)行的演示*/

PCB*p;

printfCNAMECPUTIMENEEDTIMEPRIORITYSTATUS'n");

if(run!-NULL)

printfC%-1Os%-1Od%-1Od%-1Od%c\n〃，run->namc,run->cputimc,run->nced

time,run->prio,run->state);

/*輸出執(zhí)行的進(jìn)程H勺信息*/

p二ready;

while(p!=NULL)

{printf(〃%-1Os%-10d%~1Od%-1Od%c\n”,p->name,p->cputime,p->needtime,

p->prio,p->state);/*輸出就緒進(jìn)程的信息*/

p=p->next;}

p=finish;

while(p!=NULL)

{printf(，z%-1Os%-1Od%-1Od%-1Od%c\n，\p->name,p->cputime,p->needtim

e,p->prio,p->state);/*輸出結(jié)束隊(duì)列的信息*/

p=p->next;}

getcharO;)/*使用getchar()函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車

繼續(xù)*/

voidinsert(PCB*q)/*插入新進(jìn)程，把進(jìn)程按優(yōu)先數(shù)大小排序*/

{PCB*pl,*s,*r;

intb;

s=q；/*指針s指向新要插入的進(jìn)程*/

pl二ready;/*指針pl指向本來(lái)的I進(jìn)程隊(duì)列B'J隊(duì)首*/

r=pl;/*使用指針r是指向pl前面的進(jìn)程*/

b=l;

while((pl!=NULL)&&b)

if(pl->prio>=s->prio){r=pl;pl=pl->next;}/*新進(jìn)程的優(yōu)先數(shù)

小，則pl指向下一種進(jìn)程繼續(xù)比*/

elseb=0;

if(r!=pl){r->nexi=s;s->next=pl;)"新進(jìn)程找到位置，插在r和

pl之間*/

else{s->next=pl;ready=s;}}/*新進(jìn)程時(shí)優(yōu)先數(shù)最大，插在隊(duì)

首，并

修改就緒隊(duì)苜ready指針*/

voidcreate0

{PCB*p;

inti;

ready=NULL;run=NULL;finish;NULL;

printf(?，PleaseenterthenameandtimeandpriorityofPCB:\n");

/*輸入進(jìn)程名、運(yùn)行時(shí)間和優(yōu)先級(jí)*/

for(i-0;i<N;i++)

{p=(PCB*)malloc(sizcof(PCB));/*為新進(jìn)程開(kāi)辟空間*/

scanfp->name);/*輸入進(jìn)程名*/

，，，，

scanf(%d,&p->needtime);/*輸入進(jìn)程規(guī)定運(yùn)行時(shí)間*/

scanf(飛；/*輸入進(jìn)程優(yōu)先數(shù)*/

p->cputimc=O;

p->state=W，;/*表達(dá)就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀

態(tài)*/

if(ready!=NULL)insert(p);/*就緒隊(duì)首不為NULL,插入新進(jìn)程

else{p->next=ready;ready=p;}}/*否則先插在NULL前*/

printf("Displayisgoingtostart:\n");

printf(〃***********************************************\n");

prt();

run=ready;/*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/

ready=ready->next;"ready指向下一種進(jìn)程，這樣當(dāng)進(jìn)程執(zhí)行時(shí)假

如優(yōu)先數(shù)不大于其他H勺進(jìn)程，應(yīng)當(dāng)先進(jìn)行優(yōu)先數(shù)最大的進(jìn)程*/

run->state=，R*;}/*隊(duì)首進(jìn)程的I狀態(tài)為就緒*/

voidprioO

{while(run!=NULL)

{run->cputimc-run->cputimc+l;/*運(yùn)行一次cpu占用時(shí)間加一*/

run->nccdtime=run->needtime-l;/*運(yùn)行一次規(guī)定運(yùn)行時(shí)間減一*/

run->prio=run->prio-l;/*運(yùn)行一次優(yōu)先數(shù)減一*/

if(run->needtime==O)/*若規(guī)定運(yùn)行時(shí)間為0時(shí)*/

{run->next=finish;/*退出隊(duì)列*/

finish=run;"finish為結(jié)束進(jìn)程的隊(duì)列*/

run->state=，E';/*修改狀態(tài)為結(jié)束*/

run二NULL;/*釋放run指針*/

if(ready!=NULL)/*創(chuàng)立.新就緒隊(duì)列口勺頭指針*/

{run=ready;run->state=,;ready:ready-〉nexi;))

if((ready!=NULL)&&(run->prio<ready->prio))

/*隊(duì)首進(jìn)程的優(yōu)先數(shù)比它下一種小，且下一種進(jìn)程不為NULL時(shí)執(zhí)行*/

{run->state=，W*;

run->next=NUI,L;/*隊(duì)首進(jìn)程退出進(jìn)程隊(duì)列*/

insert(run);/*在進(jìn)程隊(duì)列中重新插入本來(lái)口勺隊(duì)首進(jìn)程*/

run=ready;/*重新置就緒隊(duì)列的頭指針*/

run->state=，R';

ready=ready->next;}

prt();}}

voidmainO

{printf(''PleaseenterthetotalnumberofPCB:\n，/);

scanf&N);

createO;/*模擬創(chuàng)立進(jìn)程，并輸入有關(guān)信息*/

prioO;}/*優(yōu)先數(shù)調(diào)度算法*/

2.2.4.測(cè)試成果及闡明

優(yōu)先級(jí)調(diào)度算法運(yùn)行狀況如圖1,圖2,圖3,圖4所示

圖1.輸入進(jìn)程塊/、J數(shù)量

PleaseenterthetotalnumberofPCB：

3

PleaseenterthenameandtineandpriorityofPCB：

圖2.輸入每個(gè)進(jìn)程的名稱、時(shí)間、優(yōu)先級(jí)

PleaseenterthetotalnunberofPCB:

3

PleaseenterthenameandtineandpriorityofPCB：

A

3

3

B

6

圖3.輸入所有的進(jìn)程的有關(guān)信息

國(guó)

■PleaseenterthetotalnumberofPCB：

I：

■PleaseenterthenameandtimeandpriorityofPCB：

A

3

3

B

6

1

c

5

2

Displayisgoingtostart：

NAMECPUTIMENEEDTIMEPRIORITYSTATUS

A033W

C052W

B061W

NAMECPUTIMENEEDTIMEPRIORITYSTATUS

A122R

C052W

B061W

圖4.所有進(jìn)程調(diào)度算法完畢

2.3.時(shí)間片輪轉(zhuǎn)調(diào)度

2.3.1,算法思想

所有就緒進(jìn)程按先來(lái)先服務(wù)的原則排成一種隊(duì)列，將新來(lái)H勺進(jìn)程加到就緒

對(duì)列的末尾，每當(dāng)執(zhí)行進(jìn)程調(diào)度時(shí).，總是把處理機(jī)分派給隊(duì)首的進(jìn)程，各進(jìn)程占

用CPU的時(shí)間片相似。也就是說(shuō)CPUH勺處理時(shí)間劃提成一種個(gè)相似的時(shí)間片，就

緒隊(duì)列的所有進(jìn)程輪番運(yùn)行一種時(shí)間片。當(dāng)?種時(shí)間片結(jié)束時(shí)，假如運(yùn)行進(jìn)程用

完它的時(shí)間片后尚未完畢，就強(qiáng)迫運(yùn)行進(jìn)程讓出CPU,就把它送回到就緒隊(duì)列的

末尾，等待下一次調(diào)度。同步，進(jìn)程調(diào)度又去選擇就緒隊(duì)列中H勺隊(duì)首進(jìn)程，分派

給它一時(shí)間片，以投入運(yùn)行。直至所有的I進(jìn)程運(yùn)行完畢。

2.3.2.算法流程圖

2.3.3.程序代碼

#include<stdio.h>

#includc<stdlib.h>

#include<string.h>

typedefstructnode

{

charname(10];/*進(jìn)程名*/

intcount;/*計(jì)數(shù)器，判斷與否=時(shí)間片的大小*/

intcputinie;/*占用cpu時(shí)間*/

inineedtime;產(chǎn)規(guī)定運(yùn)行時(shí)間*/

charstate;/*狀態(tài)*/

structnode*next;/*指針*/

}PCB;

PCB*ready,*run,*finish,*tail;/*就緒執(zhí)行結(jié)束尾指針刃

intN.round;

voidprt()嚴(yán)輸出函數(shù)，可以以便看到進(jìn)程執(zhí)行H勺演示*/

(

PCB*p;

printf("NAMECPUTIMENEEDTIMESTATUS\n");

if(run!=NULL)

printf("%-1Os%-1Od%-1Od%c\n",run->name,run->cpulime.run->needti

me,run->state);/*輸出執(zhí)行出J進(jìn)程小J信息*/

p=ready;

while(p!=NULL)

{

printf("%-lOs%-1Od%-1Od%c\n",p->name,p->cputinie,p->needtime,p->

state);輸出就緒進(jìn)程的信息*/

p=p->next;

p=finish;

while(p!=NULL)

{

printf("%-lOs%-1(kl%-lOd%c\n",p->namc,p->cputimc.p->nccd(imc.p->

state);/*輸出結(jié)束隊(duì)列的皚息*/

p=p->ncx(;

}

getchar();

}

voidinsert(PCB*q)/*在隊(duì)尾插入新H勺進(jìn)程*/

{

PCB+p;

p=ready;

while(p->next!=NULL)

(

p=ready->next;

tail=p;

tail->ncxt=q;

q->next=NULL;

)

voidcreate()

(

PCB*p;

inti;

rcady=NULL;run=NULL;finish=NULL;

printf("PleaseenterthenameandtimeofPCB:\n");/*輸入進(jìn)程名、和

*/

for(i=0;i<N;i++)

(

p=(PCB*)malloc(sizeof(PC?B));/*為新進(jìn)程開(kāi)辟空間刃

scanf("%s'\p->name);"輸入進(jìn)程名，

scanf("%d".&p->needtime);/*輸入進(jìn)程規(guī)定運(yùn)行時(shí)間*/

p->cputime=O;

p->state='W1;/*表達(dá)就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)刃

if(ready!=NULL)insert(p);尸就緒隊(duì)首不為NULL,插入新進(jìn)程*/

else

p->ncxt=rcady;rcady=p;tail=p;

printf("Displayisgoingtostart:\n");

printf(****云******中************京****************^****\n")；

pr(()；

getcharO;

run=ready;/*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*7

ready=ready->next;/?ready指向下一種進(jìn)程為

run->state='R';

}/*隊(duì)首進(jìn)程的狀態(tài)為就緒*/

voidcount()

while(run!=NULL)

run->cputime=run->cputime+1;/*運(yùn)行一次cpu占用時(shí)間加一*/

run->needtime=run->need(inie-1;/*運(yùn)行一次規(guī)定運(yùn)行時(shí)間減一*/

run->count=n.in->count+1;/*運(yùn)行一次計(jì)數(shù)器加一*/

if(run->nccdtime==O)/*若規(guī)定運(yùn)行時(shí)間為0時(shí)*/

run->ncxt=finish;/*退出隊(duì)列*/

finish=run;/?finish為結(jié)束進(jìn)程的隊(duì)列*/

run->s(ate='E';/*修改狀態(tài)為結(jié)束刃

run=NULL;/*釋放run指針*/

if(readyJ-NULL)/*創(chuàng)立新就緒隊(duì)列的頭指針*/

run=ready;run->state='R';ready=ready->next;

)

)

else

if(run->count==round)/*假如時(shí)間片到*/

(

run->count=0;/*計(jì)數(shù)器置.0*/

if(ready!=NULL)六如就緒隊(duì)列不空，

(

run->state='W';

insert(run);/*在進(jìn)程隊(duì)列中重新插入本來(lái)進(jìn)程，插入

隊(duì)尾刃

run=ready;嚴(yán)重新置就緒隊(duì)列的頭指針*/

run->state='R';

rcady=rcady->ncxt;

)

)

prt()；

)

}

voidmain()

{

printf("PleaseenterthetotalnumberofPC?B:\n");

scanf("%d",&N):

createO；/*模擬創(chuàng)立進(jìn)程，并輸入有關(guān)信息*/

count();產(chǎn)優(yōu)先數(shù)調(diào)度算法號(hào)

)

2.3.4.測(cè)試成果及闡明

時(shí)間片輪轉(zhuǎn)調(diào)度算法運(yùn)行狀況如圖1,圖2,圖3所示

［時(shí)間片輪轉(zhuǎn)調(diào)度，時(shí)間片為：5

1/////////////////////////////////////////////////////////////////////

進(jìn)程名字運(yùn)行共需時(shí)間還需要占用時(shí)間優(yōu)先級(jí)

計(jì)算50453

20201

25252

,第25254

30306

F刖出15155

I//////////////，//////////////////////////////////////////////////////

圖1所有的進(jìn)程都在隊(duì)列中

時(shí)間片輪轉(zhuǎn)調(diào)度，時(shí)間片為：5

皆莓名字運(yùn)行共需時(shí)間還需要占用時(shí)間優(yōu)先級(jí)

1505國(guó)工

50353就緒

2051

25102

25104加筵

30156

進(jìn)程輸出已經(jīng)執(zhí)行完畢，

圖2其中一種進(jìn)程執(zhí)行完畢

|時(shí)間片輪轉(zhuǎn)調(diào)度，時(shí)間片為：5

/////////////////////////////////////////////////////////////////////

所有進(jìn)程都已經(jīng)執(zhí)行完畢？

/////////////////////////////////////////////////////////////////////

圖4所有H勺進(jìn)程都執(zhí)行完畢

2.4.多級(jí)反饋隊(duì)列調(diào)度

算法思想

容許進(jìn)程在隊(duì)列之間移動(dòng)。在系統(tǒng)中設(shè)置多種就緒隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)一種優(yōu)先級(jí)，第

?種隊(duì)列的優(yōu)先級(jí)最高，第二隊(duì)列次之。如下各隊(duì)列的優(yōu)先級(jí)逐漸低。各就緒隊(duì)列中的進(jìn)程

的運(yùn)行時(shí)間片不一樣，高優(yōu)先級(jí)隊(duì)列的時(shí)間片小，低優(yōu)先級(jí)隊(duì)列的時(shí)間片大。進(jìn)程并非總是

固定在某一隊(duì)列中，新進(jìn)程進(jìn)入系統(tǒng)后，被寄存在第一種隊(duì)列的末尾。假如某個(gè)進(jìn)程在規(guī)定

的時(shí)間片內(nèi)沒(méi)有完畢工作，則把它轉(zhuǎn)入到下一種隊(duì)列的末尾，直至進(jìn)入最終一種隊(duì)列。系統(tǒng)

先運(yùn)行第一種隊(duì)列中H勺進(jìn)程。當(dāng)?shù)谝魂?duì)列為空時(shí)，才運(yùn)行第二個(gè)隊(duì)列中的進(jìn)程。依此類推，

僅目前面所有口勺隊(duì)列都為空時(shí)，才運(yùn)行最終一種隊(duì)列中的進(jìn)程當(dāng)處理楷正在第i個(gè)隊(duì)列中

為某個(gè)進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)最高H勺隊(duì)列（第1一（iJ）中H勺任何一種對(duì)列）,

則此新進(jìn)程要搶占正在運(yùn)行進(jìn)程的處理界，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回第i隊(duì)列的

末尾，把處理器分派給新到的高優(yōu)先級(jí)進(jìn)程。除最低優(yōu)先權(quán)隊(duì)列外的所有其他隊(duì)列，均采用

相似H勺進(jìn)程調(diào)度算法，即準(zhǔn)時(shí)間片輪轉(zhuǎn)的FIFO（先進(jìn)先出）算法。最終一種隊(duì)列中的進(jìn)程

按準(zhǔn)時(shí)間片輪轉(zhuǎn)或FCFS方略進(jìn)行調(diào)度。它是綜合了FIFO、RR和剝奪式HPFH勺一種進(jìn)程

調(diào)度算法。

算法流程圖

1

程序代碼

#include<stdio.h>

#include<stdlib.h>

ttinclude<string.h>

#defineNULLO

typedefstructnode

(

charname[)0];產(chǎn)進(jìn)程名*/

intnum:/*進(jìn)程所在隊(duì)列數(shù).也是該隊(duì)列的時(shí)間片*/

intcputime;/*占用cpu時(shí)間刃

in(needtime;/*規(guī)定運(yùn)行時(shí)間

structnode*next;/*指針*/

}PCB;

PCB

PCB*qf2,*ql2;

PCB*qf3,*ql3;〃定義三個(gè)隊(duì)列的頭指針和尾指針

intblogl.blog2,blog3;/*分別記錄隊(duì)列1,、隊(duì)列2、隊(duì)列3中進(jìn)程數(shù)*/

voidinsert(PCB*q,PCB*qf,PCB*ql)

q->num++;

if(qf==NULL&&ql==NULL)

{//隊(duì)列為空

qf=ql=q;

)

else

(〃隊(duì)列不為空

q)->next=q;

ql=q;

}

ql->next=NULL;

)

voidcreate(intn)

{〃創(chuàng)立進(jìn)程，剛來(lái)的進(jìn)程都進(jìn)入隊(duì)列1

PCB*p;

p=(PCB*)malloc(sizeof(PCB));

inti;

blogl=blog2=blog3=0;〃各隊(duì)列中進(jìn)程數(shù)均為0

printf("PleaseenterthenameandneedtimeofPCB:\n");

/*輸入進(jìn)程名和所需時(shí)間*/

for(i=0;i<n;i++)

//p=(PCB*)malloc(sizcof(PCB));/*為新進(jìn)程開(kāi)辟空間*/

scanf("%s",p->name);/*輸入進(jìn)程名*/

scanf("%d'\&(p>nee<ltime));/*輸入進(jìn)程規(guī)定運(yùn)行時(shí)間刊

p->cputime=O;

p->num=O;

insen(p.qfl,qll);

blogl++;〃隊(duì)列中進(jìn)程數(shù)加1

)

)

intrun(PCB*q,PCB*qf,PCB*ql)

(

PCB

/*p=(PCB*)malloc(sizeof(PCB));

f=(PCB*)malIoc(sizeof(PCB));

1=(PCB*)malloc(sizeof(PCB));*/

p=q;

f=qf；

l=ql；

if(q->needUnie<=q->num)停在時(shí)間片內(nèi)完畢刃

(

//q->cputime+=q->needtime;

q>needtime-O;

free(q);

return0;

}

else/*不能在時(shí)間片內(nèi)完畢*/

{

//q->cputime+=q->num;

q->nccdtime-=q->num;

if(q->num<3)

q->num++;

insert(p.f.l);〃進(jìn)入下一種隊(duì)列

return1;

voidprt()戶輸出函數(shù)，可以以便看到進(jìn)程執(zhí)行口勺演示*/

PCB*p;

//p=(PCB*)malloc(sizeof(PCB));

inta;

printf("NAMECPUTIMENEEDTIMESTATUS\"

while(blog1>0||blog2>0||blog3>0)

{

if(blogl>0)/*第一種隊(duì)列不為空號(hào)

(

p=qfl;

qfl=qfl->ncxt;

p->next=NULL;

blogl-;

printf("%-lOs%-1Od%\n".p->name,p->needtime);

a=run(p,qf2,q!2);

if(a==l)

blog2++;

elseif(blog2>0)產(chǎn)第二個(gè)隊(duì)列不為空*/

p=q⑵

qf2=qf2->next;p->next=NULL;

blog2

printf("%-lOs%-1Od%\n",p->name,p->needtime);

a=run(p,qf3,ql3);

if(a==l)

blog3++;

}

elseif(blog3>())/*第三個(gè)隊(duì)列不為空號(hào)

(

P=qf3;

qf3=qf3->next;p->next=NULL;

bk)g3—;

prin(f("%-lOs%-1Od%\n".p->name,p->needtime);

a=run(p,qf3,q!3);

if(a==l)

blog3++;

｝產(chǎn)使用gcichar。函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車?yán)^續(xù)*/

voidmain()

{

qfl=qll=(PCB*)malloc(sizeof(PCB));

qf2=q12=(PCB*)malloc(sizeof(PCB));

qf2=q!2=(PCB*)malloc(sizeof(PCB));

intn;

blogI=blog2=blog3=0;

printf("請(qǐng)輸入進(jìn)程的個(gè)數(shù):

scanf("%d",&n);

create(n);

prt()；

2.4.4測(cè)試成果及闡明

2.5.短作業(yè)調(diào)度

2.5.1.算法思想

短作業(yè)優(yōu)先調(diào)度算法是指對(duì)短作業(yè)進(jìn)行調(diào)度H勺算法。它從后備隊(duì)列總選擇一種或若干

個(gè)運(yùn)行時(shí)間最短的作業(yè)，將他們調(diào)入內(nèi)存運(yùn)行。

2.5.2.算法流程圖：

短作業(yè)優(yōu)先算法流程圖

253.程序代碼

#includc<stdio.h>

#include<stdlib.h>

#include<string.h>

typedefstructnode

charname[10];尸進(jìn)程名*/

intcputime;/*占用cpu時(shí)間*/

intneedtime：/*協(xié)定運(yùn)行時(shí)間*/

charstate;產(chǎn)狀態(tài)*/

structnode*ncxt;/*指針*/

}PCB;

PCB*ready,*run、*finish:〃就緒、執(zhí)行、結(jié)束指針

intN;〃進(jìn)程數(shù)量

voidprint()//輸出函數(shù)

PCB*p;

printf("NAMECPUTIMENEEDTIMESTATUS\n");

if(run!=NULL)

printf("%-IOs%-lOd%-lO<l%c\n".

run->nanic,

n.m->cputime,

run->nccdtime,

run->state);/*輸出執(zhí)行的進(jìn)程的信息*/

p-ready;

while(p!=NULL)

(

printfC%-l0s%-10d%-10d%c\n",

p->name,

p->cpulimc,

p->needtime,

p->state);伸輸出就緒進(jìn)程的信息*/

p=p->next;

)

p=finish;

while(p!=NULL)

{

printf("%-l()s%-l()d%-l()d%c\n",

p->namc,

p->cputime.

p->nccdtimc.

p->state);蘆輸出結(jié)束隊(duì)列口勺信息力

p=p->nex(;

)

getcharO;使用gelchar。函數(shù)可以讓輸出時(shí)停留畫面，

等待人按問(wèn)下繼續(xù)*/

)

voidinser((PCB*q)/*插入新進(jìn)程，把進(jìn)程按進(jìn)程到來(lái)時(shí)間大小排序刃

(

PCB*pl,*s,*r;

intb;

s=q;嚴(yán)指針s指向新耍插入H勺進(jìn)程*/

pl=ready;/*指針pl指向本來(lái)的進(jìn)程隊(duì)列的隊(duì)首*/

r=pl;/小使用指針r是指向pl前面的進(jìn)程

b=l;

while((pl!=NULL)&&b)

if(pI->nee<ltime<s->n￡edtime)

(

r=pl;pl=pl->ncKt;

}/*新進(jìn)程口勺開(kāi)始時(shí)間大，則pl指向下一種進(jìn)程繼續(xù)比*/

else

b=0;

if(r!=pl)

(

r->next-s;s->next-pl;

}/*新進(jìn)程找到位置，插在r和pl之間*/

else

(

s->next=p1;ready=s;

}/*新進(jìn)程的開(kāi)始時(shí)間按最小，插在隊(duì)首，并修改就緒隊(duì)首ready指針可

)

voidcreateO

(

PCB+p;

inti;

ready=NULL;

run=NULL;

finish=NULL;

printf("PleascenterthenameandtimeofPCB:\n");

/*輸入進(jìn)程名、運(yùn)行時(shí)間和開(kāi)始時(shí)間*/

for(i=0;i<N;i++)

p=(PCB*)malloc(sizcof(PCB));/*為新進(jìn)程開(kāi)辟空間*/

scanf("%s",p->name);/*輸入進(jìn)程名*/

scanf("%d".&p>needtime);/*輸入進(jìn)程規(guī)定運(yùn)行時(shí)間*/

p->cputime=O;

p->slate='W;/*表達(dá)就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)刃

if(ready!=NULL)

insert(p);產(chǎn)就緒隊(duì)首不為NULL,插入新進(jìn)程

else

(信否則先插在NULL前*/

p->next=ready;

ready=p;

}

printf("Displayisgoingtostart:5")；

printf("***********************************************\n");

print();

gctchar();

run=ready;/*隊(duì)列排好?run指向就緒隊(duì)列隊(duì)首*/

rcady=rcady->ncxt;/*rcady指向下一種進(jìn)程*/

run->state='R':/*隊(duì)首在程的狀態(tài)為就緒*/

}

voidSJF()

{

while(run!=NULL)

(

run->cputime=run->cputime+run->needtime;

inn->needtime=O;

run->ncxt=finish:

finish=run;

run->staic=,E';

run=NULL;

if(ready!=NULL)

(

run=ready;

run->state='R';

ready=ready->next;

print();

)

voidmain()

printf("PleaseenterthetotalnumberofPCB:\n");

scanf("%d",&N);

create();產(chǎn)模擬創(chuàng)立進(jìn)程，并輸入有關(guān)信息*/

SJF();/*短作業(yè)優(yōu)先調(diào)度算法*/

2.5.4,測(cè)試成果截圖及操作闡明

首先輸入2個(gè)控制進(jìn)程快，分別命名si和s2,并且時(shí)間分別是2和5.短

作業(yè)優(yōu)先調(diào)度算法運(yùn)行狀況如4-7到4-9所示

Pleaseenterthetotalnumber