試驗(yàn)A4使用動態(tài)優(yōu)先權(quán)地進(jìn)程調(diào)度算法地模擬

1、文檔 實(shí)驗(yàn)四 使用動態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法的模擬 hi.baidu./xi nghui100/blog/item/c41d5c1b325b40d0ad6e75d c.html 1、實(shí)驗(yàn)?zāi)康?通過動態(tài)優(yōu)先權(quán)算法的模擬加深對進(jìn)程概念和進(jìn)程調(diào)度過程的理解。 2、實(shí)驗(yàn)容 (1) 用 C 語言來實(shí)現(xiàn)對 N 個(gè)進(jìn)程采用動態(tài)優(yōu)先算法的進(jìn)程調(diào)度； (2) 每個(gè)用來標(biāo)識進(jìn)程的進(jìn)程控制塊 PCB 用結(jié)構(gòu)來描述，包括以下字段： 進(jìn)程標(biāo)識符 id 進(jìn)程優(yōu)先數(shù) priority ，并規(guī)定優(yōu)先數(shù)越大的進(jìn)程，其優(yōu)先權(quán)越高； 進(jìn)程已占用的CPU 寸間 cputime ； 進(jìn)程還需占用的 CPU 寸寸間 alltime ，當(dāng)進(jìn)

2、程運(yùn)行完畢時(shí)，alltime 變?yōu)?0； 進(jìn)程的阻塞時(shí)間 startblock ，表示當(dāng)進(jìn)程再運(yùn)行 startblock 個(gè)時(shí)間片后， 進(jìn)程將進(jìn)入阻塞狀態(tài)； 進(jìn)程被阻塞的時(shí)間 blocktime，表示已阻塞的進(jìn)程再等待 blocktime 個(gè)時(shí)間 片后，將轉(zhuǎn)換成就緒態(tài) 進(jìn)程狀態(tài) state ； 隊(duì)列指針 next，用來將 PCB 排成隊(duì)列 (3) 優(yōu)先數(shù)改變的原則： 進(jìn)程在就緒隊(duì)列中呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加 1 進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)減 3。 (4)假設(shè)在調(diào)度前，系統(tǒng)中有 5 個(gè)進(jìn)程，它們的初始狀態(tài)如下: ID 0 1 2 3 4 PRIORITY 9 38 30 29 0 CPUTIM

3、E 0 0 0 0 0 ALLTIME 3 3 6 A 4 STARTBLOC P2 -1 -1 -1 -1 BLOCKTIME 3 0 0 0 0 STATE READY READY READY READY READY (5)為了清楚地觀察諸進(jìn)程的調(diào)度過程，程序應(yīng)將每個(gè)時(shí)間片的進(jìn)程的情況顯 示出來，參照的具體格式如下： RUNNING PROG i READY_QUEUE:-id1-id2 BLOCK_QUEUE:-id3-id4 ID 0 1 2 3 4 PRIORITY P0 P1 P2 P3 P4 CPUTIME C0 C1 C2 C3 C4 ALLTIME A0 A1 A2 A3 A

4、4 STARTBLOCK T0 T1 T2 T3 T4 文檔 BLOCKTIME B0 B1 B2 B3 B STATE SO S1 S2 S3 S4 3、思考題 (1)在實(shí)際的調(diào)度中， 除了按調(diào)度算法選擇下一個(gè)執(zhí)行的進(jìn)程外， 還應(yīng)處理哪 些工作？ 隊(duì)列實(shí)現(xiàn)： #in clude #defi ne NULL 0 #defi ne M 10 typedef struct node intid; int pr; int ct; int at; int bt; int sb; struct node *n ext; jd; jd *max(jd *p) jd *max no de=NULL,*p1,

5、*p2,*p3=p; int maxnum; p 仁 p; p2=p; if(p- next=NULL) return NULL; maxnum=p-n ext-pr; while(p1- next!=NULL) p2=p1- n ext; if(max num pr) maxno de=p2; p3=p1; maxnum=p2_pr; p1=p1- n ext; p3-n ext=max no de-n ext; maxno de-n ext=NULL; retur n maxno de; void blocktoready(jd *pblock,jd *pready) jd *p 1= p

6、block,*p3; while(p1- next!=NULL) p3=p1- n ext; if(p3-bt=0) p1- n ext=p3-n ext; p3-n ext=pready-n ext; pready _n ext=p3; p1=p1- n ext; if(p1=NULL) break; void ready(jd *p) jd *p1=p-n ext; while(p1!=NULL) p1-pr+; p1=p1- n ext; void run(jd *p) jd *p1; if(p- next!=NULL) p1=p-n ext; p1_pr=p1_pr-3; p1-at-

7、; 文檔 p1-ct+; void block(jd *p) jd *p1=p-n ext; while(p1!=NULL) p1-bt-; p1=p1- n ext; void run toreadyorblock(jd *prun,jd *pready,jd *pblock) jd *p; if(pru n-n ext=NULL) return; p=pr un_n ext; if(p_at=O) prun-n ext=NULL; else if(p_ct=p_sb) p-n ext=pblock- n ext; pblock- n ext=p; prun-n ext=NULL; else

8、 p-n ext=pready-n ext; pready _n ext=p; prun-n ext=NULL; jd *head(jd pcb,i nt L) int i; for(i=0;iL;i+) prin tf(i nput pcd%d in formati onn ,i); prin tf(PRIORITY:); scan f(%d,&pcbi.pr); prin tf(ALLTIME:); scan f(%d,&pcbi.at); prin tf(STARTBLOCK:); scan f(%d,&pcbi.sb); prin tf(BLOCKTIME:);

9、 scan f(%d,&pcbi.bt); pcbi.id=i; pcbi.ct=O; for(i=0;i next=NULL) prin tf(ttthe queue are empty n); while(p- next!=NULL) p1=p-n ext; prin tf(tt%dt%dt%dt%dt%dt%dn,p1-id,p1-pr,p1-ct,p1-at,p1-sb,p1-bt); p=p-n ext; if(p=NULL) break; int mai n() jd pcbM; jd *pready=(jd *)malloc(sizeof(jd); 文檔 jd *prun

10、=(jd *)malloc(sizeof(jd); jd *pblock=(jd *)malloc(sizeof(jd); int L,i, n=1; pready-n ext=NULL; prun-n ext=NULL; pblock- next=NULL; prin tf(please in put the nu mber of pcb :n ”)； scan f(%d,&L); pready-n ext=head(pcb,L); while(1) prun-n ext=max(pready); run (pru n); ready(pready); block(pblock);

11、prin tf(r unnin g%d every pcb in formatio n:n, n); prin tf(ttidtprtcttattsbtbtn); prin tf(the ready pcb:n); prin t(pready); prin tf(the run pcb:n); prin t(pr un); prin tf(the block pcb:n); prin t(pblock); prin tf(the all pcb:n); for(i=0;in ext=NULL & pblock- next=NULL) break; xt=head(pcb,L); whi

12、le(1) prun-n ext=max(pready); run (pru n); ready(pready); block(pblock); prin tf(r unnin g%d every pcb in formatio n:n, n); prin tf(ttidtprtcttattsbtbtn); prin tf(the ready pcb:n); prin t(pready); prin tf(the run pcb:n); prin t(pr un); prin tf(the block pcb:n); prin t(pblock); prin tf(the all pcb:n)

13、; for(i=0;i next=NULL & pblock- next=NULL) break; xt=head(pcb,L); while(1) 文檔 prun-n ext=max(pready); run (pru n); ready(pready); block(pblock); prin tf(r unnin g%d every pcb in formatio n:n, n); prin tf(ttidtprtcttattsbtbtn); prin tf(the ready pcb:n); prin t(pready); prin tf(the run pcb:n); pri

14、n t(pr un); prin tf(the block pcb:n); prin t(pblock); prin tf(the all pcb:n); for(i=0;i next=NULL & pblock- next=NULL) break; 運(yùn)行結(jié)果： rootlocalhost root# gcc -o a shiya n4.c rootlocalhost root# ./a 數(shù)組實(shí)現(xiàn)： 實(shí)驗(yàn)?zāi)康?通過動態(tài)優(yōu)先權(quán)算法的模擬加深對進(jìn)程概念和進(jìn)程調(diào)度過程的理解。 2、 實(shí)驗(yàn)容： （1） 用 C 語言來實(shí)現(xiàn)對 N 個(gè)進(jìn)程采用動態(tài)優(yōu)先權(quán)優(yōu)先算法的進(jìn)程調(diào)度。 （2） 每個(gè)用來標(biāo)識進(jìn)程

15、的進(jìn)程控制塊 PCB 用結(jié)構(gòu)來描述，包括以下字段： 進(jìn)程標(biāo)識數(shù) ID 進(jìn)程優(yōu)先數(shù) PRIORITY，并規(guī)定優(yōu)先數(shù)越大的進(jìn)程，其優(yōu)先權(quán)越高 進(jìn)程已占用的 CPU 時(shí)間 CUPTIME 進(jìn)程還需占用的 CPU 時(shí)間 ALLTIME。當(dāng)進(jìn)程運(yùn)行完畢時(shí)， ALLTIME 變?yōu)?0 進(jìn)程的阻塞時(shí)間 STARTBLOCK，表示當(dāng)進(jìn)程再運(yùn)行 STARTBLOCK 個(gè)時(shí)間片后，進(jìn)程將 進(jìn)入阻塞狀態(tài)。 進(jìn)程被阻塞的時(shí)間 BLOCKTIME，表示已阻塞的進(jìn)程再等待 BLOCKTIME 個(gè)時(shí)間片后， 將轉(zhuǎn)換成就緒狀態(tài)。 進(jìn)程狀態(tài) STATE. 隊(duì)列指針 NEXT，用來將 PCB 排成隊(duì)列。 （3） 優(yōu)先數(shù)改變的原則

16、： 進(jìn)程在就緒隊(duì)列中呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加 1。 進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)減 3。 （4） 假設(shè)在調(diào)度前，系統(tǒng)中有 5 個(gè)進(jìn)程，它們的初始狀態(tài)如下： ID 0 1 2 3 4 PRIORITY 9 38 30 29 0 CPUTIME 0 0 0 0 0 ALLTIME 3 3 6 3 4 文檔 STARTBLOCK 2 -1 - 1 -1 -1 BLOCKTIME 3 0 0 0 0 STATE READY READY READY READY READY （5）為了清楚地觀察諸進(jìn)程的調(diào)度過程，程序?qū)⒚總€(gè)時(shí)間片的進(jìn)程的情況顯示出來，參照的 具體格式如下： RUNING PROG:i RE

17、ADY_QUEUE: -id1-id2 BLOCK_QUEUE: -id3-id4 ID 0 1 2 3 4 PRIORITY P0 P1 P2 P3 P4 CPUTIME C0 C1 C2 C3 C4 ALLTIME A0 A1 A2 A3 A4 STARTBLOCK T0 T1 T2 T3 T4 BLOCKTIME B0 B1 B2 B3 B4 STATE SO S1 S2 S3 S4 #i nclude #in elude using n amespace std; int i;循環(huán)值 int j;還在阻塞或就緒隊(duì)列中的進(jìn)程數(shù) int s; int m; 最大 priority 的 id

18、 struct pcb int id; int p; /priority int cputime; int alltime; int startblock; int blocktime; int state; 0 表示 ready 1 表示 end -1 表示 block ; struct pcb pro5= 0,9,0,323,0, 1,38,03-1,0,0, 2,30,0,6,-1,0,0, 3,29,03-1,0,0, 4,0,0,4,-1,0,0 ; int cha ngestate0() if(pro0.startblock=0) pro0.state=-1; pro0.start

19、block-; return 1; 文檔 if(pro0.blocktime=0) pro0.state=0; return 1; if(pro0.state=0&pro0.startblock!=-1) pro0.startblock-;retur n 1; if(pro0.state=-1 &pro0.blocktime!=0) pro0.blocktime-;retur n 1; int stateO() cha ngestateO(); s=pro0.p; if(pro0.state=-1) s=-100; return s; int maxp() 求出最大 prior

20、ity state0(); int max=s; m=pro0.id; for(i=0;iproi.p) max=proi+1.p; m=proi+1.id; return m; void cha nge() maxp(); int x;/得到 m 現(xiàn)在的數(shù)組編號 for(i=0;ij;i+) proi.p+; for(i=0;ij;i+) if(proi.id=m) x=i; prox.cputime+; 文檔 prox.p=prox.p-4; prox.alltime-; if(prox.alltime=0) prox.state=1; void display。 cha nge(); c

21、outRUNNING PROG:me ndl; n; coutID ; for(i=0;ij;i+) cout.width(10); coutproi.id; coute ndlPRIORITY ; for(i=0;ij;i+) cout.width(10); coutproi.p; coute ndlCPUTIME ; for(i=0;ij;i+) cout.width(10); coutproi.cputime; coute ndlALLTIME ; for(i=0;ij;i+) cout.width(10); coutproi.alltime; coute ndlSTARTBLOCK;

22、for(i=0;ij;i+) cout.width(10); coutproi.startblock; coute ndlBLOCKTIME ; for(i=0;ij;i+)文檔 cout.width(IO); coutproi.blocktime; coute ndlSTATE ; for(i=0;ij;i+) cout.width(10); coutproi.state; coute ndl; int mai n() j=5;剛開始有 5 個(gè)進(jìn)程 while(j!=0) for(i=0;ij;i+) if(proi.state=1) for(;ij;i+) proi=proi+1; j=j

23、-1; display(); getchar(); 運(yùn)行結(jié)果： rootlocalhost root# g+ -o c c.c rootlocalhost root# ./c RUNNING PROG:1 ID 0 PRIORITY CPUTIME ALLTIME 1 2 10 35 0 1 3 2 1 3 0 3 31 0 6 -1 -1 0 0 0 0STARTBLOCK BLOCKTIME STATE 0 4 30 1 0 0 3 4 -1 -1 0 0 0 文檔 RUNNING PR0G:1 ID 0 1 2 3 4 PRIORITY 11 32 32 31 2 CPUTIME 0 2

24、 0 0 0 ALLTIME 3 1 6 3 4 STARTBLOCK 0 -1 -1 -1 -1 BLOCKTIME 3 0 0 0 0 STATE 0 0 0 0 RUNNING PR0G:1 ID 0 1 2 3 4 PRIORITY 12 29 33 32 3 CPUTIME 0 3 0 0 0 ALLTIME 3 0 6 3 4 STARTBLOCK -1 -1 -1 -1 -1 BLOCKTIME 3 0 0 0 0 STATE 1 0 0 0 RUNNING PR0G:2 ID 0 2 3 4 PRIORITY 13 30 33 4 CPUTIME 0 1 0 0 ALLTIME

25、 3 5 3 4 STARTBLOCK -1 -1 -1 -1 BLOCKTIME 2 0 0 0 STATE 0 0 0 RUNNING PR0G:3 ID 0 2 3 4 PRIORITY 14 31 30 5 CPUTIME 0 1 1 0 ALLTIME 3 5 2 4 STARTBLOCK -1 -1 -1 -1 BLOCKTIME 1 0 0 0 STATE 0 0 0 RUNNING PR0G:2 ID 0 2 3 4 PRIORITY 15 28 31 6 文檔 CPUTIME 0 2 1 0 ALLTIME 3 4 2 4 STARTBLOCK -1 -1 -1 -1 BLO

26、CKTIME 0 0 0 0 STATE -1 0 0 0 RUNNING PROG:3 ID 0 2 3 4 PRIORITY 16 29 28 7 CPUTIME 0 2 2 0 ALLTIME 3 4 1 4 STARTBLOCK -1 -1 -1 -1 BLOCKTIME 0 0 0 0 STATE 0 0 0 RUNNING PROG:2 ID 0 2 3 4 PRIORITY 17 26 29 8 CPUTIME 0 3 2 0 ALLTIME 3 3 1 4 STARTBLOCK -1 -1 -1 -1 BLOCKTIME 0 0 0 0 STATE 0 0 0 RUNNING

27、PROG:3 ID 0 2 3 4 PRIORITY 18 27 26 9 CPUTIME 0 3 3 0 ALLTIME 3 3 0 4 STARTBLOCK -1 -1 -1 -1 BLOCKTIME 0 0 0 0 STATE 0 1 0 RUNNING PROG:2 ID 0 2 4 PRIORITY 19 24 10 CPUTIME 0 4 0 ALLTIME 3 2 4 STARTBLOCK -1 -1 -1 BLOCKTIME 0 0 0 文檔 STATE 0 0 0 RUNNING PR0G:2 ID 0 2 4 PRIORITY 20 21 11 CPUTIME 0 5 0 ALLTIME 3 1 4 STARTBLOCK -1 -1 -1 BLOCKTIME 0 0 0 STATE 0 0 0 RUNNING PR0G:2 ID 0 2 4 PRIORITY 21 18 12 CPUTIME 0 6 0 ALLTIME 3 0 4 STARTBLOCK -1 -1 -1 BLOCKTIME 0 0 0 STATE 0 1 0 RUNNING PROG:0 ID 0 4 PRIORITY 18 13 CPUTIME 1 0 ALLTIME 2