操作系統(tǒng)實(shí)驗(yàn)_先來(lái)先服務(wù)地調(diào)度算法和短作業(yè)優(yōu)先

1、實(shí)用標(biāo)準(zhǔn)文案學(xué)號(hào)P71514032專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)姓名實(shí)驗(yàn)日期2017.10.27教師簽字成績(jī)實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)名稱(chēng)】進(jìn)程調(diào)度算法FCFS、FJF【實(shí)驗(yàn)?zāi)康摹吭诙嗟莱绦蚧蚨嗳蝿?wù)系統(tǒng)中，系統(tǒng)同時(shí)處于就緒態(tài)的進(jìn)程有若干個(gè)。也就是說(shuō)能運(yùn)行的進(jìn)程數(shù)遠(yuǎn)遠(yuǎn)大于處理機(jī)個(gè)數(shù)， 為了使系統(tǒng)中的各進(jìn)程能有條不紊的運(yùn)行，必須選擇某種調(diào)度策略，以選擇一進(jìn)程占用處理機(jī)，所以，要求使用某一種編程語(yǔ)言設(shè)計(jì)實(shí)現(xiàn)模擬單處理機(jī)調(diào)度的算法， 以鞏固和加深處理機(jī)調(diào)度的概念。本實(shí)驗(yàn)要求采用先來(lái)先服務(wù)的調(diào)度算法和短作業(yè)優(yōu)先的調(diào)度算法編寫(xiě)和調(diào)試一個(gè)簡(jiǎn)單的進(jìn)程調(diào)度程序。 通過(guò)本實(shí)驗(yàn)可以加深理解進(jìn)程調(diào)度、 進(jìn)程隊(duì)列的概念。【實(shí)驗(yàn)原理】FCFS

2、調(diào)度算法先來(lái)先服務(wù) (FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法。在進(jìn)程調(diào)度中采用 FCFS 算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)， 使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。文檔大全實(shí)用標(biāo)準(zhǔn)文案SJF調(diào)度算法短作業(yè) (進(jìn)程 )優(yōu)先調(diào)度算法 SJ(P)F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先 (SJF)的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)， 將它們調(diào)入內(nèi)存運(yùn)行?！緦?shí)驗(yàn)內(nèi)容】問(wèn)題分析輸入：進(jìn)程的名稱(chēng)、到達(dá)時(shí)間、服務(wù)時(shí)間輸出：進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間

3、其中對(duì)于任意進(jìn)程有：周轉(zhuǎn)時(shí)間 = 完成時(shí)間 - 到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 = 周轉(zhuǎn)時(shí)間 / 服務(wù)時(shí)間因此，兩個(gè)算法的關(guān)鍵是求完成時(shí)間數(shù)據(jù)結(jié)構(gòu)及函數(shù)說(shuō)明使用的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，進(jìn)程的名稱(chēng)、到達(dá)時(shí)間、服務(wù)時(shí)間、進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間分別對(duì)應(yīng)于一個(gè)數(shù)組，這些數(shù)組長(zhǎng)度相等.struct fcfs/ 定義進(jìn)程的結(jié)構(gòu)體char name10;/ 進(jìn)程名float arrivetime; /到達(dá)時(shí)間float servicetime; /服務(wù)時(shí)間float starttime;/開(kāi)始時(shí)間float finishtime;/完成時(shí)間float zztime;/周轉(zhuǎn)時(shí)間float dqzztime;/

4、帶權(quán)周轉(zhuǎn)時(shí)間;文檔大全實(shí)用標(biāo)準(zhǔn)文案fcfs a100; /結(jié)構(gòu)體數(shù)組函數(shù)說(shuō)明void Finput(fcfs *p,int N) ;/ 輸入函數(shù)，初始化void Fsort(fcfs *p,int N) ;/ 按到達(dá)時(shí)間排序，先到達(dá)排在前面void Fsort2(fcfs *p,int N) ;/ 按進(jìn)程大小排序，先到達(dá)排在前面void F_method(fcfs *p, int N)/ 先來(lái)先服務(wù)算法void F_method2(fcfs *p,int N)/ 短作業(yè)優(yōu)先程序void SJF(fcfs *p,int N)；/短作業(yè)優(yōu)先void FCFS(fcfs *p,int N);/ 先來(lái)

5、先服務(wù)void SJF(fcfs *p,int N)/ 短作業(yè)優(yōu)先void FPrint(fcfs *p,int N)/ 輸出函數(shù)求完成時(shí)間算法1) FCFS 算法流程圖文檔大全實(shí)用標(biāo)準(zhǔn)文案開(kāi)始初始化結(jié)構(gòu)體數(shù)組、初始化進(jìn)程隊(duì)列，當(dāng)前時(shí)間為0對(duì)進(jìn)程數(shù)組按照到達(dá)時(shí)間小到大進(jìn)行排序當(dāng)前時(shí)間是否小于當(dāng)前是當(dāng)前時(shí)間 = 當(dāng)前時(shí)進(jìn)程到達(dá)時(shí)間間 +1否當(dāng)前進(jìn)程的開(kāi)始時(shí)間等于當(dāng)前時(shí)間當(dāng)前進(jìn)程 = 下一個(gè)進(jìn)程當(dāng)前進(jìn)程的結(jié)束時(shí)間等于開(kāi)始時(shí)間+運(yùn)行時(shí)間當(dāng)前時(shí)間 = 當(dāng)前進(jìn)進(jìn)程數(shù)組是否程結(jié)束時(shí)間+1否掃描完畢是結(jié)束2) SJF 算法流程圖文檔大全實(shí)用標(biāo)準(zhǔn)文案開(kāi)始初始化結(jié)構(gòu)體數(shù)組，輸入賦值，當(dāng)前時(shí)間為 0對(duì)進(jìn)程數(shù)組按照

6、進(jìn)程運(yùn)行時(shí)間進(jìn)行小到大排序，標(biāo)志位為 0當(dāng)前進(jìn)程為第一個(gè)進(jìn)程當(dāng)前時(shí)間 >當(dāng)前進(jìn)程的到否達(dá)時(shí)間當(dāng)前進(jìn)程標(biāo)志位為 0否是當(dāng)前進(jìn)程開(kāi)始時(shí)間=當(dāng)前時(shí)間結(jié)束時(shí)間 =當(dāng)前時(shí)間 + 運(yùn)行書(shū)劍是否為最后一個(gè)進(jìn)程否是當(dāng)前進(jìn)程標(biāo)志為1所有標(biāo)志位都為 1是結(jié)束當(dāng)前進(jìn)程 = 下一個(gè)當(dāng)前時(shí)間 = 當(dāng)前時(shí)進(jìn)程間 +1否文檔大全實(shí)用標(biāo)準(zhǔn)文案程序#include <stdio.h>struct fcfs/ 定義進(jìn)程的結(jié)構(gòu)體char name10;/ 進(jìn)程名float arrivetime; /到達(dá)時(shí)間float servicetime; /服務(wù)時(shí)間float starttime;/開(kāi)始時(shí)間float fin

7、ishtime;/完成時(shí)間float zztime;/周轉(zhuǎn)時(shí)間float dqzztime;/帶權(quán)周轉(zhuǎn)時(shí)間;floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;fcfs a100;/ 定義先來(lái)先服務(wù)算法進(jìn)程的最大數(shù)量void Finput(fcfs *p,int N)/ 輸入函數(shù)int i;文檔大全實(shí)用標(biāo)準(zhǔn)文案printf("輸入進(jìn)程的名稱(chēng)、到達(dá)時(shí)間、服務(wù)時(shí)間:（例如 : x 0 100）n");for(i=0; i<=N-1; i+)printf("輸入第

8、 %d 進(jìn)程的名稱(chēng)、到達(dá)時(shí)間、服務(wù)時(shí)間:n",i+1);scanf("%s%f%f",&,&pi.arrivetime,&pi.servicetime);/ 輸出函數(shù)void FPrint(fcfs *p,int N)/輸出函數(shù)int k;printf("n執(zhí)行順序 :n");printf("%s",);for(k=1; k<N; k+)printf("-%s",);printf("n進(jìn)程名 t 到達(dá)時(shí)間 t 服務(wù)時(shí)間 t

9、開(kāi)始時(shí)間 t 結(jié)束時(shí)間t 周轉(zhuǎn)時(shí)間 t 帶權(quán)周轉(zhuǎn)時(shí)間 nn");文檔大全實(shí)用標(biāo)準(zhǔn)文案for(k=0; k<=N-1; k+)printf("%st%-.2ftt%-.2ftt%-.2ftt%-.2ftt%-.2ftt%-.2fttnn",,pk.arrivetime,pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime);void Fsort(fcfs *p,int N)/ 按到達(dá)時(shí)間排序，先到達(dá)排在前面for(int i=0; i<=N-1; i+)for(int

10、 j=0; j<=i; j+)if(pi.arrivetime<pj.arrivetime)/進(jìn)行排序，如果先到達(dá)就排在前面fcfs temp;temp=pi;pi=pj;pj=temp; / 運(yùn)行結(jié)果void F_method(fcfs *p, int N)文檔大全實(shí)用標(biāo)準(zhǔn)文案int k;for(k=0; k<=N-1; k+)if(k=0)pk.starttime=pk.arrivetime;/如果是第一個(gè)進(jìn)程，開(kāi)始時(shí)間等于到達(dá)時(shí)間pk.finishtime=pk.arrivetime+pk.servicetime;/結(jié)束時(shí)間等于到達(dá)時(shí)間加上服務(wù)時(shí)間elsepk.star

11、ttime=pk-1.finishtime;/ 開(kāi)始時(shí)間 = 上一個(gè)一個(gè)進(jìn)程的完成時(shí)間pk.finishtime=pk.starttime+pk.servicetime;/結(jié)束時(shí)間 = 開(kāi)始時(shí)間加上 + 現(xiàn)在進(jìn)程的服務(wù)時(shí)間for(k=0; k<=N-1; k+)/ 求每個(gè)進(jìn)程的信息文檔大全實(shí)用標(biāo)準(zhǔn)文案pk.zztime=pk.finishtime-pk.arrivetime;/ 周轉(zhuǎn)時(shí)間 = 完成時(shí)間 - 到達(dá)時(shí)間pk.dqzztime=pk.zztime/pk.servicetime;/ 帶權(quán)周轉(zhuǎn)時(shí)間 = 周轉(zhuǎn)時(shí)間 / 服務(wù)時(shí)間void F_method2(fcfs *p,int N)

12、/ 短作業(yè)優(yōu)先核心程序int num;int arrive=65535;/ 尋找最早到達(dá)的進(jìn)程int min_serive=65535;/ 尋找最小服務(wù)時(shí)間進(jìn)程int i;fcfs b100;/ 新建一個(gè)，進(jìn)行排序int state100;/設(shè)置 100 個(gè)標(biāo)志位for( i=0; i<N; i+)statei=0;for(i=0; i<N; i+)文檔大全實(shí)用標(biāo)準(zhǔn)文案if(pi.arrivetime<arrive) arrive=pi.arrivetime;num=i;b0=pnum;statenum=1;b0.finishtime=b0.arrivetime+b0.ser

13、vicetime;intj=0;for(int k=1; k<N; k+) min_serive=65535; for(i=0; i<N; i+)if(statei=1|pi.arrivetime>bj.finishtime)/如果遇到已排序或者未到達(dá)的進(jìn)程跳過(guò)continue;elseif(pi.servicetime<min_serive)min_serive=pi.servicetime;num=i;statenum=1;文檔大全實(shí)用標(biāo)準(zhǔn)文案/ 找到合適的進(jìn)程并賦值到 B b+j=pnum; bj.starttime=bj-1.finishtime; bj.fin

14、ishtime=bj-1.finishtime+bj.servicetime;for(j=0; j<=N-1; j+)/ 求每個(gè)進(jìn)程的信息bj.zztime= bj.finishtime- bj.arrivetime;/ 周轉(zhuǎn)時(shí)間= 完成時(shí)間 - 到達(dá)時(shí)間bj.dqzztime= bj.zztime/ bj.servicetime;/ 帶權(quán)周轉(zhuǎn)時(shí)間 = 周轉(zhuǎn)時(shí)間 / 服務(wù)時(shí)間for(j=0; j<N; j+)pj=bj;/ 先來(lái)先服務(wù)void FCFS(fcfs *p,int N)Fsort(p,N);/對(duì)每個(gè)進(jìn)程排序F_method(p,N);FPrint(p,N);文檔大全實(shí)用

15、標(biāo)準(zhǔn)文案void SJF(fcfs *p,int N)F_method2(p,N);FPrint(p,N);int main()/ 主函數(shù)int N;printf("輸入進(jìn)程數(shù) :");scanf("%d",&N);Finput(a,N);printf("先來(lái)先服務(wù) n");FCFS(a,N);printf("nnn");printf("短作業(yè)優(yōu)先 n");SJF(a,N);return 0;文檔大全實(shí)用標(biāo)準(zhǔn)文案【小結(jié)或討論】1.能實(shí)現(xiàn)的功能輸入進(jìn)程個(gè)數(shù)Num ，每個(gè)進(jìn)程到達(dá)時(shí)間Arri

16、valTimei，服務(wù)時(shí)間 ServiceTimei。采用先來(lái)先服務(wù)FCFS 或者短作業(yè)優(yōu)先SJF 進(jìn)程調(diào)度算法進(jìn)行調(diào)度，計(jì)算每個(gè)進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，并且統(tǒng)計(jì)Num 個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。2、FCFS 算法相對(duì)于 SJF 算法來(lái)說(shuō)，比較簡(jiǎn)單，在FCFS 算法中，主要用到文檔大全實(shí)用標(biāo)準(zhǔn)文案的是隊(duì)列，按照作業(yè)的到達(dá)時(shí)間來(lái)進(jìn)行排序排序算法。3、SJF 算法中就需要考慮到很多的因素，因?yàn)? 時(shí)刻到達(dá)的作業(yè)肯定第一個(gè)執(zhí)行，然后再考慮剩余的作業(yè)的服務(wù)時(shí)間以決定哪一個(gè)作業(yè)先執(zhí)行，但是這是在確保所有剩余的作業(yè)都處于就緒狀態(tài)的情況下。如若不然，還要考慮每一個(gè)作業(yè)執(zhí)行完后，有哪些作業(yè)進(jìn)入了排隊(duì)狀態(tài)。4、SJF 算法中還要考慮到如若同一時(shí)刻進(jìn)入了多個(gè)作業(yè)，還要將這若干個(gè)作業(yè)按照服務(wù)時(shí)間進(jìn)行排序，再考慮執(zhí)行情況。5、無(wú)論是 FCFS 還是 SJF 算法，關(guān)鍵都是求完成時(shí)間。 FCFS 算法執(zhí)行進(jìn)程的順序是由到達(dá)時(shí)間的先后決定的，SJF 算法的順序是由服務(wù)