操作系統(tǒng)課程設(shè)計(jì)——進(jìn)程調(diào)度模擬算法

1、福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院課程設(shè)計(jì)報(bào)告課程名稱：操作系統(tǒng)實(shí)習(xí)題目：進(jìn)程調(diào)度算法模擬姓 名：*系：計(jì)算機(jī)專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年 級(jí)：2011級(jí)學(xué) 號(hào)：*指導(dǎo)教師：*職 稱：*2014年1月16日福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院信息工程類課程設(shè)計(jì)報(bào)告結(jié)果評(píng)定評(píng)語(yǔ)：成績(jī)：指導(dǎo)教師簽字：評(píng)定日期：目 錄1.進(jìn)程調(diào)度算法模擬課程設(shè)計(jì)的目的12.進(jìn)程調(diào)度算法模擬課程設(shè)計(jì)的要求13.進(jìn)程調(diào)度算法模擬課程設(shè)計(jì)報(bào)告內(nèi)容131前言 132進(jìn)程調(diào)度算法模擬設(shè)計(jì)的環(huán)境 133系統(tǒng)流程圖及各模塊 24總結(jié)18參考文獻(xiàn)19參考網(wǎng)站19進(jìn)程調(diào)度算法模擬1.進(jìn)程調(diào)度算法模擬課程設(shè)計(jì)的目的和意義2013-2014學(xué)年，在學(xué)習(xí)

2、了操作系統(tǒng)這門課后，對(duì)當(dāng)中的進(jìn)程調(diào)度算法產(chǎn)生了濃厚的興趣。各種調(diào)度算法，理論上比較好理解。為了加深印象，我決定把各種調(diào)度算法用C語(yǔ)言寫出來(lái)。于是便產(chǎn)生這份從頭到尾都讓我絞盡腦汁的課程設(shè)計(jì)。做這份課程設(shè)計(jì)，對(duì)從事系統(tǒng)開發(fā)的人員來(lái)說(shuō)，是必要的，可以在一定程度上為自己以后的發(fā)展鋪路。雖然用處不是特別明顯，但對(duì)加深系統(tǒng)調(diào)用算法的理解無(wú)疑用處是巨大的。2.進(jìn)程調(diào)度算法模擬課程設(shè)計(jì)的要求1. 用C語(yǔ)言寫出至少兩種進(jìn)程調(diào)度算法。2. 畫出大概流程圖。3. 對(duì)算法過(guò)程出現(xiàn)的bug進(jìn)行調(diào)試。4. 展示最后的算法結(jié)果3.1前言：目前比較常見的幾種進(jìn)程調(diào)度算法有：1. 先到先服務(wù)(FCFS)2. 短進(jìn)程優(yōu)先（非搶占

3、和搶占）算法(SPF)3. 高響應(yīng)比優(yōu)先算法4. 時(shí)間片輪轉(zhuǎn)算法我選出其中三種即先到先服務(wù)，短進(jìn)程優(yōu)先（2種）和時(shí)間片輪轉(zhuǎn)算法進(jìn)行C語(yǔ)言描述以加深對(duì)這三種算法的理解。3.2進(jìn)程調(diào)度算法模擬設(shè)計(jì)的環(huán)境VC+6.0及CodeBlocks，32位計(jì)算機(jī)WIN7操作系統(tǒng)。3.3流程圖定義進(jìn)程結(jié)構(gòu)體：struct Proint num;/進(jìn)程號(hào)int time_in;/進(jìn)程到達(dá)時(shí)間int work_time;/進(jìn)程服務(wù)時(shí)間 int btime;/用于搶占式進(jìn)程優(yōu)先記錄該進(jìn)程開始時(shí)間 int l_w_time;/用于搶占式進(jìn)程優(yōu)先記錄剩余服務(wù)時(shí)間 int end_time; /記錄該進(jìn)程結(jié)束時(shí)間，（需要時(shí)

4、時(shí)監(jiān)測(cè)）int judge;/用于需要時(shí)的標(biāo)記pro10;/進(jìn)程結(jié)構(gòu)體1先到先服務(wù)算法描述：把所有進(jìn)程按到達(dá)先后排序，每次取最先到的進(jìn)程執(zhí)行后淘汰，再取下一個(gè)，直到所有進(jìn)程調(diào)度完畢。主要代碼：void FCFS() /先到先服務(wù)char s = "先到先服務(wù)"printmat(s); PT;int i, j;int min;int t = pro_num;int begin_time = 0x7fff;for(i = 1; i <= pro_num; i+) if(proi.time_in < begin_time) begin_time = proi.time

5、_in;proi.judge = 0;/所有進(jìn)程號(hào)查找標(biāo)志置0，表示還未查找 while(t-) for(i = 1; i <= pro_num; i+) if(proi.judge=0) min = i;/設(shè)其為目前最早到達(dá)的時(shí)間for(j = i+1; j <= pro_num; j+) if(proj.judge = 0 && proj.time_in <= promin.time_in)/該進(jìn)程號(hào)若還未被查找且小于預(yù)設(shè) min = j; promin.judge = 1;/該進(jìn)程號(hào)被查找過(guò) printf(Format2,promin.num,promi

6、n.time_in,promin.work_time,begin_time,begin_time+promin.work_time,begin_time+promin.work_time-promin.time_in); begin_time += promin.work_time; puts(""); printmat(s);puts("");程序截圖：2段進(jìn)程優(yōu)先非搶占算法描述：每次選出最短的進(jìn)程進(jìn)行調(diào)度，調(diào)度完畢則淘汰，直到所有進(jìn)程都調(diào)度完畢；void SJF() /短進(jìn)程優(yōu)先(非搶占) char s = "非搶占短進(jìn)程優(yōu)先"

7、printmat(s); PT;struct Pro *p,*q,*head;int t_num,t_work_time,t_time_in;head = &pro1;/*按所有進(jìn)程到達(dá)時(shí)間排序*/p = head;while(p - head < pro_num) for(q = p+1; q-head < pro_num; q+) if(q->time_in < p->time_in | (q->work_time < p->work_time && q->time_in = p->time_in) t_n

8、um = p->num,t_time_in = p->time_in,t_work_time = p->work_time; p->num = q->num,p->time_in = q->time_in,p->work_time = q->work_time; q->num = t_num, q->time_in = t_time_in,q->work_time = t_work_time; p+; /*/*找出第一個(gè)執(zhí)行的進(jìn)程，即最先到達(dá)的最短進(jìn)程*/int time = 0;p = head;for(q = head

9、; q < head + pro_num; q+)q->judge = 0;if(q->time_in < p->time_in)p = q;if(q->time_in = p->time_in && q->work_time < p->work_time)p = q;int cnt = pro_num;p = head;while(cnt-)time = time < p->time_in ? p->time_in:time;p->judge = 1;p->begin_time = ti

10、me;time += p->work_time;p->end_time = time;for(q = head; q < head + pro_num; q+)if(p->judge = 1 && q->judge = 0)p = q;else if(p->judge = 0 &&(q->work_time < p->work_time)p = q;for(p = head; p < head+pro_num; p+)printf(Format2,p->num,p->time_in,p-&g

11、t;work_time,p->begin_time,p->end_time,p->end_time-p->time_in);puts("");printmat(s);puts("");3短進(jìn)程優(yōu)先（搶占）算法描述：按時(shí)間疊加，當(dāng)新進(jìn)程到達(dá)時(shí)，判斷如果比當(dāng)前執(zhí)行的進(jìn)程短，則發(fā)生搶占，執(zhí)行完的淘汰，直到所有進(jìn)程都調(diào)度完畢。int find(int pp,int time)int i;for(i = 1; i <= pro_num; i+)if(propp.l_w_time = 0 |( proi.l_w_time != 0 &a

12、mp;& proi.l_w_time < propp.l_w_time && time >= proi.time_in)pp = i;return pp;void test()int i;for(i = 1; i <= pro_num; i+)printf(Format2,proi.num,proi.time_in,proi.work_time,proi.btime,proi.end_time,proi.end_time-proi.time_in);puts("");void SJF2()/搶占式短進(jìn)程優(yōu)先char s = &quo

13、t;搶占式短進(jìn)程優(yōu)先"printmat(s); PT;int i; struct Pro *p,*q;/ 先對(duì)到達(dá)時(shí)間進(jìn)行排序/struct Pro *head = &pro1; int t_num, t_time_in,t_work_time;int time_cnt = 0,time; p = head = &pro1; while(p - head < pro_num) for(q = p+1; q-head < pro_num; q+) if(q->time_in < p->time_in) t_num = p->num,t

14、_time_in = p->time_in,t_work_time = p->work_time; p->num = q->num,p->time_in = q->time_in,p->work_time = q->work_time; q->num = t_num, q->time_in = t_time_in,q->work_time = t_work_time; p+; for(i = 1; i <= pro_num; i+)proi.l_w_time = proi.work_time;time_cnt += pro

15、i.work_time;int pp = 1;time = propp.time_in;while(time_cnt-)propp.l_w_time-;time+;if(propp.l_w_time=0)propp.end_time = time;else;if(propp.btime = 0 && propp.time_in != 0)propp.btime = time-1;else;pp = find(pp,time);test();printmat(s);puts("");4時(shí)間片輪轉(zhuǎn)（以單位1為例）取當(dāng)前已經(jīng)到達(dá)的進(jìn)程，執(zhí)行一個(gè)時(shí)間片，跳轉(zhuǎn)至下一個(gè)

16、已經(jīng)到達(dá)的進(jìn)程，再執(zhí)行一個(gè)時(shí)間片，直到所有進(jìn)程都調(diào)度完畢。void TROT()char *s = "時(shí)間片輪轉(zhuǎn)算法"printmat(s);PT;struct Pro *p,*q,*head;int t_num,t_time_in,t_work_time;head = &pro1;p = head;/*給所有進(jìn)程按到達(dá)時(shí)間排序*/while(p - head < pro_num) for(q = p+1; q-head < pro_num; q+) if(q->time_in < p->time_in) t_num = p->n

17、um,t_time_in = p->time_in,t_work_time = p->work_time; p->num = q->num,p->time_in = q->time_in,p->work_time = q->work_time; q->num = t_num, q->time_in = t_time_in,q->work_time = t_work_time; p+; /*/int time = pro1.time_in;for(p = head; p < head+pro_num; p+)p->ju

18、dge = 0;p->left_work = p->work_time;int flag = 1;for(p = head; flag; p+)if(p->time_in <= time && p->left_work > 0)p->left_work-;if(p->judge = 0)p->judge = 1; p->begin_time = time;if(p->left_work = 0)p->end_time = time+1;else continue;time+;for(q = head; q

19、< head+pro_num; q+)if(q->left_work!=0)break;if(q = head + pro_num)flag = 0;if(p = head + pro_num - 1)/設(shè)從開頭再開始找p = head-1;for(q = head; q < head + pro_num; q+)printf(Format2,q->num,q->time_in,q->work_time,q->begin_time,q->end_time,q->end_time-q->time_in);puts(""

20、;);printmat(s);5高響應(yīng)比優(yōu)先先對(duì)所有進(jìn)程排序，已經(jīng)到達(dá)的進(jìn)程，每次選取響應(yīng)比最高的進(jìn)程進(jìn)行調(diào)度，直到所有進(jìn)程調(diào)度完畢。void FPF()char *s = "高響應(yīng)比優(yōu)先算法"char *ss = "*"printmat(s);PT;struct Pro *p,*q,*head;int t_num,t_time_in,t_work_time;head = &pro1;p = head;/*給所有進(jìn)程按到達(dá)時(shí)間排序*/while(p - head < pro_num) for(q = p+1; q-head < pro

21、_num; q+) if(q->time_in < p->time_in) t_num = p->num,t_time_in = p->time_in,t_work_time = p->work_time; p->num = q->num,p->time_in = q->time_in,p->work_time = q->work_time; q->num = t_num, q->time_in = t_time_in,q->work_time = t_work_time; p+; /*/int time = pro1.time_in;int cnt = pro_num;for(p = head; p < head+pro_num; p+)p->judge = 0;p->left_work = p->work_time;p = he