進(jìn)程調(diào)度算法和問題解答

1、實(shí)現(xiàn)操作系統(tǒng)的主要進(jìn)程調(diào)度算法：先來先服務(wù)(FCFS)算法，短進(jìn)程優(yōu)先(SPN)算法和時(shí)間 片輪轉(zhuǎn)(RR)算法。先來先服務(wù)調(diào)度算法(FCFS)該算法采用非剝奪策略，算法按照進(jìn)程提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分派CPU。 當(dāng)前進(jìn)程占用CPU,直到執(zhí)行完或阻塞，才出讓CPU (非搶占方式)。在進(jìn)程喚醒后(如 I/O完成)，并不立即恢復(fù)執(zhí)行，通常等到當(dāng)前進(jìn)程出讓CPUo這是最簡(jiǎn)單的調(diào)度算法， 比較有利于長(zhǎng)進(jìn)程，而不利于短進(jìn)程，有利于CPU繁忙的進(jìn)程，而不利于I/O繁忙的進(jìn)程。短進(jìn)程優(yōu)先調(diào)度算法(SPN)該算法也采用非剝奪策略，對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的進(jìn)程優(yōu)先分派處理機(jī)。通常后來的短進(jìn)程不 搶先正在執(zhí)行

2、的進(jìn)程。相比FCFS算法，該算法可改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間, 縮短進(jìn)程的等待時(shí)間，提高系統(tǒng)的吞吐量。缺點(diǎn)是對(duì)長(zhǎng)進(jìn)程非常不利，可能長(zhǎng)時(shí)間得不到執(zhí) 行，且未能依據(jù)進(jìn)程的緊迫程度來劃分執(zhí)行的優(yōu)先級(jí)，以及難以準(zhǔn)確估計(jì)進(jìn)程的執(zhí)行時(shí)間， 從而影響調(diào)度性能。時(shí)間片輪轉(zhuǎn)算法(RR)該算法采用剝奪策略。讓就緒進(jìn)程以FCFS的方式按時(shí)間片輪流使用CPU的調(diào)度方式， 即將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)將CPU分派給 隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片，時(shí)間片的長(zhǎng)度從幾個(gè)ms到幾百ms。在一個(gè)時(shí)間片結(jié)束 時(shí)，發(fā)生時(shí)鐘中斷，調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通

3、過 上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程，進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU (如阻塞)。 時(shí)間片輪轉(zhuǎn)調(diào)度算法的特點(diǎn)是簡(jiǎn)單易行、平均響應(yīng)時(shí)間短，但不利于處理緊急作業(yè)。在時(shí)間 片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能的影響很大，因此時(shí)間片的大小應(yīng)選擇恰當(dāng)。使用C語言實(shí)現(xiàn)FCFS,SPN,RR算法:#include#include先來先服務(wù)，最短作業(yè)優(yōu)先算法結(jié)構(gòu)體 typedef struct process_FCFSchar name;float arrivetime;char name;float arrivetime;float servetime;float finishtime;float r

4、oundtime;進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間float daiquantime; /帶權(quán)周轉(zhuǎn)時(shí)間struct process_FCFS *link;/結(jié)構(gòu)體指針 FCFS;時(shí)間片輪轉(zhuǎn)算法結(jié)構(gòu)體typedef struct stud(char name;進(jìn)程名float arrive;/進(jìn)程到達(dá)時(shí)間float run;進(jìn)程運(yùn)行時(shí)間float rest;運(yùn)行進(jìn)程剩余時(shí)間char *state;進(jìn)程狀態(tài)struct stud *next; 結(jié)構(gòu)體指針 stud;FCFS *p/q,*head=NULL;struct process_FCFS a100;float avrRoundtime

5、;/平均周轉(zhuǎn)時(shí)間float avrDaiquantime;/平均帶權(quán)周轉(zhuǎn)時(shí)間FCFS initial(struct process_FCFS aJnt n);void print(struct process_FCFS aJnt n);void Fcfs(struct process_FCFS a,int n); /FCFS 算法void SPN(struct process_FCFS a,int n);/SPN 算法struct process_FCFS *sortarrivetime(struct process_FCFS aJnt n); 到達(dá)時(shí)間冒泡排序struct process_F

6、CFS *sortservetime(struct process_FCFS a,int n); 服務(wù)時(shí)間冒泡排序struct stud *create(int &a); 初始化創(chuàng)建時(shí)間片輪轉(zhuǎn)算法調(diào)度隊(duì)列void RR(struct stud *head, int &a);/時(shí)間片輪轉(zhuǎn) RR 算法按到達(dá)時(shí)間進(jìn)行冒泡排序struct process_FCFS *sortarrivetime(struct process_FCFS aJnt n)int i,j;struct process_FCFS t;int flag;for(i=l;in;i+)flag=O;for(j=0;jaO+l.arr

7、ivetime)將到達(dá)時(shí)間短的交換到前邊t=aj;aj=aj+l； aj+l=t;flag=l;/ 交換if(flag=O)如果一趟排序中沒發(fā)生任何交換，則排序結(jié)束 break;return a; /返回排序后進(jìn)程數(shù)組按服務(wù)時(shí)間進(jìn)行冒泡排序struct process_FCFS *sortservetime(struct process_FCFS aJnt n)(int i,j;struct process_FCFS t;int flag;for(i=l;in;i+)flag=O;for(j=l;jaj+l.servetime)/ 將到達(dá)時(shí)間短的交換到前邊t=aj;aj=aj+l；aj+l=t

8、;flag=l;/ 交換if(flag=O)/如果一趟排序中沒發(fā)生任何交換，則排序結(jié)束break;)return a; II返回排序后進(jìn)程數(shù)組先來先服務(wù)算法void Fcfs(struct process_FCFS aJnt nzfloat &tl, float &t2) (int i;aO.finishtime=aO.arrivetime+aO.servetime; 完成時(shí)間=到達(dá)時(shí)間-服務(wù)時(shí)間 a0.roundtime=a0.finishtime-a0.arrivetime; 周轉(zhuǎn)時(shí)間=完成時(shí)間-提交時(shí)間 a0.daiquantime=a0.roundtime/a0.servetime;帶

9、權(quán)時(shí)間=周轉(zhuǎn)時(shí)間 /服務(wù)時(shí)間for(i=l;in;i+) if(ai.arrivetimeai-l.finishtime)/當(dāng)前到達(dá)時(shí)間在上一個(gè)作業(yè)結(jié)束時(shí)間之前ai.finishtime=ai-l.finishtime+ai.servetime; 完成時(shí)間=上一個(gè)完成時(shí)間+ 服務(wù)時(shí)間ai.roundtime=ai.finishtime-ai.arrivetime;周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間ai.daiquantime=ai.roundtime/ai,servetime;帶權(quán)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間)else /當(dāng)前到達(dá)時(shí)間在上一個(gè)作業(yè)結(jié)束時(shí)間之后ai.finishtime=ai.arrive

10、time+ai,servetime; ai.roundtime=ai.finishtime-ai.arrivetime; ai.daiquantime=ai.roundtime/ai,servetime; )for(int i=0;in;i+)printf(進(jìn)程名：%c,);printf(到達(dá)時(shí)間:%fzai.arrivetime);printf(服務(wù)時(shí)間:%f,ai.servetime);printf(完成時(shí)間:%f/ai.finishtime);printf(周轉(zhuǎn)時(shí)間:roundtime);printf(帶權(quán)周轉(zhuǎn)時(shí)間:%f/ai.daiquantime);printf(n”)

11、;tl += ai.roundtime;t2 += ai.daiquantime;)短作業(yè)優(yōu)先算法void SPN(struct process_FCFS aJnt nzfloat &tl, float &t2) (int i;aO.finishtime=aO.arrivetime+aO.servetime; 完成時(shí)間=到達(dá)時(shí)間服務(wù)時(shí)間 a0.roundtime=a0.finishtime-a0.arrivetime; 周轉(zhuǎn)時(shí)間=完成時(shí)間提交時(shí)間 a0.daiquantime=a0.roundtime/a0.servetime;帶權(quán)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間for(i=l;in;i+)if(ai

12、.arrivetimeai-l.finishtime)/當(dāng)前到達(dá)時(shí)間在上一個(gè)作業(yè)結(jié)束時(shí)間之前ai.finishtime=ai-l.finishtime+ai.servetime; 完成時(shí)間=上一個(gè)完成時(shí)間 + 服務(wù)時(shí)間ai.roundtime=ai.finishtime-ai.arrivetime;周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間ai.daiquantime=ai.roundtime/ai.servetime;帶權(quán)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間)else /當(dāng)前到達(dá)時(shí)間在上一個(gè)作業(yè)結(jié)束時(shí)間之后ai.finishtime=ai.arrivetime+ai.servetime;ai.roundtime=ai

13、.finishtime-ai.arrivetime;ai.daiquantime=ai.roundtime/ai.servetime;)for(int i=0;in;i+)printf(進(jìn)程名:%cM,);printf(到達(dá)時(shí)間:%fzai.arrivetime);printf(服務(wù)時(shí)間:servetime);printf(完成時(shí)間:%f,a.finishtime);printf(周轉(zhuǎn)時(shí)間:roundtime);printf(帶權(quán)周轉(zhuǎn)時(shí)間:%fzai.daiquantime);printfCV);tl += ai.roundtime;t2 += ai.daiquantime;打印

14、輸出函數(shù)void print(struct process_FCFS a,int n)(int i;for(i=0;in;i+)printf(進(jìn)程名：%);printf(到達(dá)時(shí)間:%fzai.arrivetime);printf(服務(wù)時(shí)間:%f/ai.servetime);printf(完成時(shí)間：%fzai.finishtime);printf(周轉(zhuǎn)時(shí)間:%f/ai.roundtime);printf(帶權(quán)周轉(zhuǎn)時(shí)間:%f/ai.daiquantime);printf(n)；初始化創(chuàng)建調(diào)度隊(duì)列struct stud *create(int &a)(int i;struct st

15、ud *head, *rear,*p,*q,*t;head=rear=NULL;for(i=0;iname);printf(到達(dá)時(shí)間:);scanf (%f, &p-a rr i ve);printf(“服務(wù)時(shí)間:);scanf(%f,&p-run);p-rest = p-run;p-state = ready;if(rear = NULL)head = p;p-next = NULL;rear = p;)elset= NULL;q = head;while(q & q-arrive arrive)t = q；q = q-next;) if(q = head)p-next = head; he

16、ad = p;)else if(t = rear) rear-next = p; p-next = NULL; rear = p;)elset-next = p; p-next = q;)(return head;時(shí)間片輪轉(zhuǎn)算法void RR(struct stud *head, int &a)(struct stud *pz*t,*r;float slice = O.Of;float temp = O.Of; 緩存最后一個(gè)正數(shù)restfloat ml = O.Of, m2 = O.Of, nl = O.Of, n2 = O.Of;float sum_zhouzhuan = O.Of, sum

17、_daiquan = O.Of;/所有進(jìn)程總周轉(zhuǎn)時(shí)間，所有進(jìn)程總帶權(quán) 周轉(zhuǎn)時(shí)間float zhouzhuan = O.Of, daiquan = 0.0f; /周轉(zhuǎn)時(shí)間,帶權(quán)周轉(zhuǎn)時(shí)間 float avr_zhouzhuan = O.Of, avr_daiquan = O.Of;printf(請(qǐng)輸入時(shí)間塊大小:“)；scanf(%f”,&slice);while(head != NULL) 隊(duì)列非空，循環(huán)r = p = head;while(p != NULL) 遍歷隊(duì)列，結(jié)束后跳出當(dāng)前循環(huán)t = head;ml += slice;temp = p-rest;p-rest = p-rest -

18、slice; 剩余時(shí)間p-state = running;if(p-rest arrive; 進(jìn)程周轉(zhuǎn)時(shí)間daiquan = zhouzhuan / (p-run); 進(jìn)程帶權(quán)周轉(zhuǎn)時(shí)間sum_zhouzhuan += zhouzhuan;所有進(jìn)程周轉(zhuǎn)時(shí)間之和sum_daiquan += daiquan;p-rest = 0;printf(nn);printf(Hnameta rrivetru ntresttstaten);while(t != NULL)printf(,%dt%ft%ft%ft%sn,t-name/t-arrivezt-run/t-rest/t-state);t = t-nex

19、t;if(p-rest = 0)/*判斷是否刪除結(jié)點(diǎn)*/finishtime +=if(p = head)/*刪除頭結(jié)點(diǎn)*/ (head = p-next;free(p);p = head; else r-next = p-next;p = r-next;r = p；elser= p；p-state = ready;p = p-next;printf(n總周轉(zhuǎn)時(shí)間：)；printf(%f”, sum_zhouzhuan);printf(n總帶權(quán)周轉(zhuǎn)時(shí)間:)；printf(%fnz sum_daiquan);avr_zhouzhuan = sum_zhouzhuan / a;avr_daiqua

20、n = sum_daiquan / a;printf(n平均周轉(zhuǎn)時(shí)間：)；printf(%fzavr_zhouzhuan);printf(n平均帶權(quán)周轉(zhuǎn)時(shí)間：)；printf(%fn,avr_daiquan);主函數(shù)void main()(float tl = O.Of; /總周轉(zhuǎn)時(shí)間float t2 = O.Of; 總帶權(quán)周轉(zhuǎn)時(shí)間float avr_tl = O.Of; /平均周轉(zhuǎn)時(shí)間float avr_t2 = O.Of; 平均帶權(quán)周轉(zhuǎn)時(shí)間int nJ;char select =選擇算法變量標(biāo)識(shí)while (select != e & select != E)不為退出標(biāo)識(shí)，保持循環(huán)prin

21、tfC請(qǐng)選擇算法：na.先來先服務(wù)算法nb.短作業(yè)優(yōu)先算法nc.時(shí)間片輪轉(zhuǎn)算法 ne.退出程序n輸入選擇字符標(biāo)號(hào)：“)；scanf(%c,&select);if (select = a 11 select = A) 先來先服務(wù)算法printf(”nn=先來先服務(wù)算法=nn”);printfl請(qǐng)輸入進(jìn)程數(shù)：“)；scanf(d,&n);for(i=0;in;i+)printf(%d 進(jìn)程名：“,i+1); scanf(%s,&); printf(”到達(dá)時(shí)間：)； scanf(%f,&ai.arrivetime); printf(“服務(wù)時(shí)間:“)； scanf(%f,&ai.serv

22、etime);)sortarrivetime(az n); 冒泡排序Fcfs(a,n,tl,t2); 先來先服務(wù)算法avr_tl = tl / n;avr_t2 = t2 / n;printffXn);printfC呼均周轉(zhuǎn)時(shí)間為：avr_tl);printfC,平均帶權(quán)周轉(zhuǎn)時(shí)間為:%f n“, avr_t2);else if (select = b 11 select = B)短作業(yè)優(yōu)先算法printf(nn=作業(yè)優(yōu)先算法=nn);printfC*請(qǐng)輸入進(jìn)程數(shù)：“);scanf(d,&n);for(i=0;in;i+)printf(%d 進(jìn)程名：“,i+1);scanf(%s,&ai.nam

23、e);printf(”到達(dá)時(shí)間：)；scanf(%f”,&ai.arrivetime);printf(”服務(wù)時(shí)間：)；scanf(%f,&ai.servetime);sortservetime(a, n);冒泡排序SPN(a,n,tl,t2);短作業(yè)優(yōu)先算法avr_tl = tl / n;avr_t2 = t2 / n;printffXn);printfC平均周轉(zhuǎn)時(shí)間為:%f n”, avr_tl);printfC呼均帶權(quán)周轉(zhuǎn)時(shí)間為：%fn, avr_t2);)else if (select = c* | select = C)時(shí)間片輪轉(zhuǎn)算法printf(”nn=時(shí)間片輪轉(zhuǎn)算法=nn”);in

24、t a;printfC請(qǐng)輸入進(jìn)程數(shù):)；scanf(”d”,&a);struct stud *head;head = create(a);RR(head, a);)system(,lpause,);計(jì)算每種算法下的平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間|fcfs先來先J進(jìn)程名到擺時(shí)間完成時(shí)間需要時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間E03331.000000Q07471.750000K1136122.000000R1185173.40000002235214.200000S226324&.。麗麗白A3315285.600000M3365336.600000D43823417.000000J44023618.0000

25、00U44223819.000000F54644110.250000P54934414.66666?X55234715.666667B65755110.200000II66145513.750000L66656012.000000N67266611.000000tlG7536923 .麗麗麗u779418.000000c881236.500000G88?613.166667I992516.600000r99538628.666667平均周轉(zhuǎn)時(shí)間：44.958333平均帶權(quán)周轉(zhuǎn)時(shí)間：12.917361QB C:W i n dtem 2 2c m d. exeI回QB C:Windowssyste

26、m32cmd.exerr時(shí)間片輪轉(zhuǎn)）4程名 到達(dá)時(shí)間完成時(shí)間需要時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1a93904344310.7500001|K18868?14.50800017657515 .麗麗。|o28258016.009000Is25134916.333333rH386583387584ID43623216.000000.1437233i6.snPNaon*43823417.uu(d0U-57?47218.000000IP56135618.666667X562357IB68958316.600000|H67947318.250000|l69。58416.S0k)HUN694G8814.C6G6G7II66736120.333333ii78347619.M0M00H；c85224422.000000G89568714.5000