動(dòng)態(tài)優(yōu)先權(quán)進(jìn)程調(diào)度算法的模擬(共10頁(yè))

1、河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院計(jì)算機(jī)學(xué)院(xuyun)設(shè)計(jì)(shj)性實(shí)驗(yàn)報(bào)告專業(yè)(zhuny):朱文焌 年級(jí)/班級(jí)： 20 xx級(jí)網(wǎng)絡(luò)工程 20152016學(xué)年第一學(xué)期課程名稱操作系統(tǒng)指導(dǎo)教師張倩倩本組成員學(xué)號(hào)姓名朱文焌實(shí)驗(yàn)地點(diǎn)計(jì)算機(jī)與信息工程學(xué)院216實(shí)驗(yàn)時(shí)間2015.11.20項(xiàng)目名稱使用動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法的模擬實(shí)驗(yàn)類型設(shè)計(jì)性實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)動(dòng)態(tài)優(yōu)先權(quán)調(diào)度算法和時(shí)間片輪轉(zhuǎn)調(diào)度算法的模擬加深進(jìn)程概念和進(jìn)程調(diào)度過(guò)程的理解。實(shí)驗(yàn)儀器或設(shè)備一臺(tái)筆記本電腦或者是一臺(tái)臺(tái)式機(jī)總體設(shè)計(jì)（設(shè)計(jì)原理、設(shè)計(jì)方案及流程等）本實(shí)驗(yàn)的目的就是用在Linux下用C語(yǔ)言編程模擬N個(gè)進(jìn)程采用高優(yōu)先權(quán)優(yōu)先（要求采用動(dòng)態(tài)

2、優(yōu)先權(quán)）進(jìn)程調(diào)度算法。已知時(shí)間片輪轉(zhuǎn)算法，可以根據(jù)時(shí)間片輪轉(zhuǎn)的思路加以修改就行了。時(shí)間輪轉(zhuǎn)調(diào)度算法與動(dòng)態(tài)優(yōu)先權(quán)的區(qū)別就是時(shí)間片輪轉(zhuǎn)是在FIFO進(jìn)程調(diào)度的基礎(chǔ)上，隊(duì)列中的進(jìn)程按照進(jìn)入的順序，每個(gè)進(jìn)程每次都執(zhí)行一個(gè)時(shí)間片；如果運(yùn)行完就把該進(jìn)程釋放掉，如果在一個(gè)時(shí)間片內(nèi)未結(jié)束就插到隊(duì)列尾部。而動(dòng)態(tài)優(yōu)先權(quán)進(jìn)程調(diào)度算法就是按照優(yōu)先權(quán)的大小運(yùn)行進(jìn)程，如果一個(gè)時(shí)間片內(nèi)未運(yùn)行完，則將優(yōu)先權(quán)數(shù)減3后再插入到隊(duì)列中（不是隊(duì)尾而是隊(duì)列中的適當(dāng)位置，該位置前面的節(jié)點(diǎn)的優(yōu)先級(jí)數(shù)大于該節(jié)點(diǎn)的優(yōu)先級(jí)數(shù)，后面的節(jié)點(diǎn)的count值小于該節(jié)點(diǎn)的count值）。實(shí)驗(yàn)要求：在Linux下用C語(yǔ)言編程模擬N個(gè)進(jìn)程采用高優(yōu)先權(quán)優(yōu)先（要求

3、采用動(dòng)態(tài)優(yōu)先權(quán)）進(jìn)程調(diào)度算法。為了清楚地觀察每個(gè)進(jìn)程的調(diào)度過(guò)程，程序應(yīng)將每個(gè)時(shí)間片內(nèi)的進(jìn)程情況顯示出來(lái)； 進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志，因此，在模擬算法中每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來(lái)代表，PCB用一結(jié)構(gòu)體表示。包括以下字段：進(jìn)程標(biāo)識(shí)數(shù)id，或者進(jìn)程的名稱name；進(jìn)程優(yōu)先數(shù)priority，并規(guī)定優(yōu)先數(shù)越大的進(jìn)程，其優(yōu)先權(quán)越高；進(jìn)程需要運(yùn)行的CPU時(shí)間ntime；進(jìn)程的運(yùn)行時(shí)間rtime；進(jìn)程(jnchng)狀態(tài)state；隊(duì)列(duli)指針next，用來(lái)將PCB排成隊(duì)列。進(jìn)程在運(yùn)行過(guò)程中其狀態(tài)將在就緒、執(zhí)行、阻塞（可選）、完成幾種狀態(tài)之間轉(zhuǎn)換，同時(shí)進(jìn)程可能處于不同的隊(duì)列中，如就緒隊(duì)

4、列、阻塞隊(duì)列（可選）。在兩種調(diào)度算法中，考慮分別可以選擇什么樣的隊(duì)列及如何實(shí)現(xiàn)進(jìn)程的入隊(duì)(r du)、出隊(duì)操作；為了便于處理，優(yōu)先權(quán)調(diào)度每次也僅讓進(jìn)程執(zhí)行一個(gè)時(shí)間片，若在一個(gè)時(shí)間片內(nèi)未運(yùn)行結(jié)束，調(diào)整進(jìn)程優(yōu)先級(jí)將其插入就緒隊(duì)列，進(jìn)行新一輪調(diào)度；優(yōu)先數(shù)改變?cè)瓌t：進(jìn)程每運(yùn)行若一個(gè)時(shí)間單位，優(yōu)先數(shù)減3；進(jìn)程在就緒隊(duì)列中呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加1。（僅供參考，合理即可）優(yōu)先權(quán)調(diào)度中，對(duì)于遇到優(yōu)先權(quán)一致的情況，可采用FCFS策略解決；由于是模擬進(jìn)程調(diào)度，所以，對(duì)被選中的進(jìn)程并不實(shí)際啟動(dòng)運(yùn)行，而是修改進(jìn)程控制塊的相關(guān)信息來(lái)模擬進(jìn)程的一次運(yùn)行；為了清楚地觀察諸進(jìn)程的調(diào)度過(guò)程，程序應(yīng)將每個(gè)時(shí)間片內(nèi)的進(jìn)程的情況顯

5、示出來(lái)，參照格式如下:id cputime needtime priority(count) state0 0 2 48 readysort函數(shù)執(zhí)行流程實(shí)驗(yàn)步驟（包括主要(zhyo)步驟、代碼分析等）#include stdio.h #include #define getpch(type) (type*)malloc(sizeof(type) struct pcb /定義(dngy)進(jìn)程控制塊char name10; /進(jìn)程(jnchng)的名字char state; /進(jìn)程的狀態(tài)int count; /進(jìn)程優(yōu)先級(jí)int ntime; /進(jìn)程運(yùn)行需要的CPU時(shí)間int rtime; /進(jìn)程已

6、運(yùn)行的時(shí)間struct pcb* link; /連接pcb的指針*ready=NULL,*tail=NULL,*p; /就緒隊(duì)列指針，隊(duì)尾指針typedef struct pcb PCB; int slice = 1;PCB *readyMaxProcess; int readyQueNum=0; / 就緒隊(duì)列的進(jìn)程數(shù)量sort() /將進(jìn)程插入到就緒指針 PCB *q;if(ready=NULL) /隊(duì)列為空，將p插入到隊(duì)列中 ready=p; tail=p; else/若就緒隊(duì)列不為空，將p插入到隊(duì)列 if(p-countready-count)/p指針?biāo)腹?jié)點(diǎn)的count值頭的大于隊(duì)列(

7、duli)節(jié)點(diǎn)的count值，將p指針?biāo)腹?jié)點(diǎn)插入到對(duì)頭 p-link=ready; ready=p;else bool m=false; q=ready; /q2=q1-link; while(m=false) if(tail-count=p-count)/若p的count值小于隊(duì)尾指針?biāo)腹?jié)點(diǎn)(ji din)的的count值的話，將p插到隊(duì)尾 tail-link=p;tail=p;p-link=NULL;m=true; else if(q-count=p-count&p-countq-link-count)/若p的count值大于隊(duì)尾指針?biāo)腹?jié)點(diǎn)的的count值的話,將p所指節(jié)點(diǎn)插入(ch

8、 r)到隊(duì)列中指定位置/必須滿足插入位置的前一個(gè)節(jié)點(diǎn)的count值大于p-count,并且滿足插入位置的后一個(gè)節(jié)點(diǎn)的count值小于p-countp-link=q-link; q-link=p; m=true;elseq=q-link;/q2=q2-link; input() int i,num; printf(n 請(qǐng)輸入(shr)進(jìn)程個(gè)數(shù):);scanf(%d,&num); for(i=0;iname); printf(n 請(qǐng)輸入進(jìn)程優(yōu)先權(quán)數(shù):); scanf(%d,&p-count);printf(n 請(qǐng)輸入進(jìn)程運(yùn)行時(shí)間:); scanf(%d,&p-ntime); printf(n);

9、p-rtime=0;p-state=w; p-link=NULL; sort(); /將進(jìn)程p插入就緒隊(duì)列ready中 printf(n 請(qǐng)輸入時(shí)間片大小:);scanf(%d,&slice); /獲得就緒隊(duì)列中進(jìn)程的個(gè)數(shù)int space() PCB* pr=ready; while(pr!=NULL) readyQueNum+; pr=pr-link; return(readyQueNum); /顯示進(jìn)程disp(PCB * pr) printf(nqname tstate tcount tndtime truntime n); printf(|%st,pr-name); printf(|

10、%ct,pr-state); printf(|%dt,pr-count); printf(|%dt,pr-ntime); printf(|%dt,pr-rtime); printf(n); /顯示當(dāng)前運(yùn)行進(jìn)程和就緒隊(duì)列(duli)中進(jìn)程的信息check() PCB* pr; printf(n * 當(dāng)前正在(zhngzi)運(yùn)行的進(jìn)程是:%s,readyMaxProcess-name); disp(readyMaxProcess); pr=ready; printf(n *當(dāng)前就緒隊(duì)列(duli)狀態(tài)為:n); while(pr!=NULL) pr-count+;disp(pr); pr=pr-l

11、ink; /撤銷進(jìn)程destroy() printf(n 進(jìn)程 %s 已完成.n,readyMaxProcess-name); free(readyMaxProcess); /readyQueNum-; /使當(dāng)前進(jìn)程運(yùn)行一個(gè)時(shí)間片，若結(jié)束則撤銷，否則插入就緒隊(duì)列隊(duì)尾running() int tempt=0;tempt = readyMaxProcess-ntime - readyMaxProcess-rtime;if(temptslice)readyMaxProcess-rtime+=slice; elsereadyMaxProcess-rtime+=tempt;check();if(rea

12、dyMaxProcess-rtime=readyMaxProcess-ntime) destroy(); else readyMaxProcess-count=readyMaxProcess-count-3;readyMaxProcess-state=w; p=readyMaxProcess;/再將隊(duì)頭節(jié)點(diǎn)(ji din)readyMaxProcess插入到隊(duì)列時(shí)，現(xiàn)將賦給另一個(gè)指針psort(); main() int len,h=0; input(); /輸入進(jìn)程并形成就緒(jix)隊(duì)列l(wèi)en=space(); /獲得就緒隊(duì)列(duli)中進(jìn)程的個(gè)數(shù)while(len!=0)&(ready

13、!=NULL) /若就緒隊(duì)列不為空 len=space();h+;printf(n The execute number:%d n,h);readyMaxProcess=ready; /將指向隊(duì)優(yōu)先級(jí)最大的節(jié)點(diǎn)的指針指向隊(duì)頭節(jié)點(diǎn)ready=ready-link; /改變對(duì)頭指針readyMaxProcess-link=NULL; /將優(yōu)先級(jí)最大的進(jìn)程從隊(duì)列中分裂出來(lái)readyMaxProcess-state=R; running(); printf(nn 所有進(jìn)程已經(jīng)完成.n); 進(jìn)程名/進(jìn)程屬性運(yùn)行所需時(shí)間ntime進(jìn)程的優(yōu)先權(quán)數(shù)進(jìn)程a108進(jìn)程b95進(jìn)程c69實(shí)驗(yàn)結(jié)果七、結(jié)果分析(fnx)

14、與總結(jié)這個(gè)(zh ge)實(shí)驗(yàn)最主要就是理解(lji)動(dòng)態(tài)優(yōu)先權(quán)數(shù)調(diào)度算法的原理，利用c語(yǔ)言程序完成該過(guò)程的模擬。在編寫該程序的時(shí)候采用了很多方法（如雙向鏈表），但是都比較復(fù)雜，所以轉(zhuǎn)向了在時(shí)間片輪轉(zhuǎn)的基礎(chǔ)上改進(jìn)的方法。最主要的思想就是進(jìn)程進(jìn)隊(duì)列，二次插入或者多次插入隊(duì)列均采用按照優(yōu)先權(quán)大小的順序查找插入的適當(dāng)位置?？梢苑譃槿N情況:1、直接插入到對(duì)頭。2、插入到隊(duì)尾。3、插入到隊(duì)列中間。第一種必須滿足進(jìn)程的優(yōu)先級(jí)大于隊(duì)頭結(jié)點(diǎn)的優(yōu)先級(jí)；第二種是進(jìn)程的優(yōu)先級(jí)必須小于或者等于隊(duì)尾結(jié)點(diǎn)的優(yōu)先級(jí)數(shù)；第三種結(jié)點(diǎn)的值小于或者等于頭結(jié)點(diǎn)的優(yōu)先級(jí)數(shù)，并且大于隊(duì)尾結(jié)點(diǎn)的優(yōu)先級(jí)數(shù)。經(jīng)過(guò)多次的調(diào)試程序，多次的失敗，但是并未失去信心，知道得到正確的結(jié)果。付出可能會(huì)有收獲，但不付