操作系統(tǒng)試驗(yàn)FCFS和短作業(yè)優(yōu)先SJF調(diào)度算法模擬

1、題 目 先來(lái)先服務(wù)FCFS和短作業(yè)優(yōu)先SJF進(jìn)程調(diào)度算法姓 名：學(xué) 號(hào)：專 業(yè)：學(xué) 院：指導(dǎo)教師：林若寧二零一八年十一月一、實(shí)驗(yàn)?zāi)康哪M單處理器系統(tǒng)的進(jìn)程調(diào)度，分別采用短作業(yè)優(yōu)先和先來(lái)先服務(wù)的進(jìn)程調(diào)度算法作為 進(jìn)程設(shè)計(jì)算法，以加深對(duì)進(jìn)程的概念及進(jìn)程調(diào)度算法的理解.二、實(shí)騏內(nèi)容.短作業(yè)優(yōu)先調(diào)度算法原理短作業(yè)優(yōu)先調(diào)度算法，是指對(duì)短作業(yè)或斷進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別可以用于 作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)運(yùn)行時(shí)間最 短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先調(diào)度算法，是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行 時(shí)間最短的進(jìn)程，將處理機(jī)分配給它使它立即執(zhí)行并一直執(zhí)行到完

2、成，或發(fā)生某事件而被阻 塞放棄處理機(jī)時(shí)再重新調(diào)度。.先來(lái)先服務(wù)調(diào)度算法原理先來(lái)先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可 用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或 多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒 隊(duì)列。在進(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è)計(jì).概要設(shè)計(jì)程序包括主函數(shù)、FCFS算法函數(shù)、SJF算法函數(shù)、輸出函數(shù)；主函數(shù)流程：輸入

3、文件 中的數(shù)據(jù)一顯示各進(jìn)程數(shù)據(jù)一選擇算法一調(diào)用相應(yīng)算法的函數(shù)一輸出結(jié)果.算法流程SJF算法流程圖:核H3Bl從小列夫X J旭SJF流程圖:.詳細(xì)設(shè)計(jì)(1)定義一個(gè)結(jié)構(gòu)體 typedef stmct PCBcharjob.id10;作業(yè)IDfloatAiT_tune;到達(dá)時(shí)刻floatFun.time;估計(jì)運(yùn)行時(shí)間floatWhit_tiine;等待時(shí)間floatStaivtiine;開始時(shí)刻floatFin_time;完成時(shí)刻floatTiu_time;周轉(zhuǎn)時(shí)間floatWTur_time;帶權(quán)周轉(zhuǎn)時(shí)間mtOrder;優(yōu)先標(biāo)記Hst;(2)先來(lái)先服務(wù)算法函數(shù)void fcfs(list *p,

4、int count) 先來(lái)先服務(wù)算法 (list temp;臨時(shí)結(jié)構(gòu)體變量inti;mt j;foi(i= l;i count;i+)按到達(dá)時(shí)刻直接插入排序(temp = pi;J = 1-1;while(temp.AiT_tiine = 0)-j;pj+l = temp:)for(i = 0;i count;i+)循環(huán)計(jì)算各個(gè)作業(yè)的時(shí)間值(if(i = 0)pi.Start_tiine = pi.Air_tmie; elsepi.Start_tune = pi-l.Fin_tmie;開始時(shí)刻一前一個(gè)作業(yè)的完成時(shí)刻pi.Wait_time = pi.Start_time - pi.An_tim

5、e;等待=開始-到達(dá)pi.Fm_time = pi.Stait_time + pi.Fun_tiine;完成一開始+運(yùn)行pi.Tui_tiine = pi.Fm_time - pi.Air_time;周 轉(zhuǎn)=完成-至 U 達(dá)pi.WTu 口 ime = pi.Tur.time / pi.FuiUime;帶權(quán)周轉(zhuǎn)=周轉(zhuǎn)/運(yùn)行return:)（3）最短作業(yè)優(yōu)先函數(shù)void sjf（list count）最短作業(yè)優(yōu)先算法（sjf）（list item;結(jié)構(gòu)體變量mt i = 0;mtj = 0;mtk = 0;最短運(yùn)行時(shí)間作業(yè)的下標(biāo)mt flag = 0; 優(yōu)先級(jí)設(shè)置float niin = 0;最

6、短運(yùn)行時(shí)間float temp;開始的時(shí)刻temp = p0. Anytime;先求出最先到達(dá)作業(yè)的時(shí)刻fbi(i = 0;i pi .Anytime)temp = pi.AiT_time; k = i；)保存最先到達(dá)的作業(yè)的時(shí)刻最先到達(dá)的作業(yè)的下標(biāo)，默認(rèn)為p0fbi(i = 0;i count;i+)pk.Order = -H-flag;設(shè)置優(yōu)先級(jí)為1,最高優(yōu)先級(jí)=temp - pk.An_time;計(jì)算各個(gè)時(shí)間pk.WaiCtime pk.Fm_time pk.Tur_tmie pk.WTui_timepk.Start_tune = tenip:=temp + pk.Fun_time;=p

7、k.Fm_time - pk.AiT_tiine;=pk.Tui_tiine / pk.Fun_tune;mm= 100;temp = pk.Fiii_time;后一個(gè)作業(yè)的開始時(shí)刻是前一個(gè)作業(yè)的完成時(shí)刻fbr(j = 0J countJ+)if(pj.Order != 0 | temp - pj.ArOime pj.Fun_time) (niiii = pj.Fun_tmie;k = j;求出滿足條件最短運(yùn)行時(shí)間的作業(yè)的下標(biāo)) )for(i= l;i count;i+)按優(yōu)先級(jí)排序(item = pi;J = 1-1;while(item.Order = 0)pi+i = pj;-j;) p

8、lj+l =item;return;四、實(shí)驗(yàn)結(jié)果測(cè)試數(shù)據(jù)：進(jìn)程名到達(dá)時(shí)間運(yùn)行時(shí)間A04B13C25D44(1)先來(lái)先服務(wù)算法調(diào)試入入 即司H:chevisfcfssjfDebugfcfssjf.exe上數(shù)量：4卜ID,到達(dá)時(shí)刻，估計(jì)運(yùn)行時(shí)間（用空格隔開）:先來(lái)先服務(wù)算法ID到達(dá)運(yùn)行等待開始完成周轉(zhuǎn)帶權(quán)周轉(zhuǎn)A0.0004.0000.0000.0004.0004.0001.000B1.0003.0003.0004.0007.0006.0002.000C2.0005.0005.0007.00012.00010.0002.000D4.0004.0008.00012.00016.00012.0003.0

9、00平均周轉(zhuǎn)時(shí)間為；8.000000.x x x x x x x X .X xx xx 平均帶權(quán)周轉(zhuǎn)時(shí)間為:2.000000f f X X X X X X XX X X XX XX Xf X X X X X X * X X XX XX、Press any key to continue（2）最短作業(yè)優(yōu)先算法調(diào)試司H:chevisfcfssjfDebugfcfssjf.exe*入入4nRnH 30 主星目1 Ik IL-估計(jì)運(yùn)行時(shí)間用空格隔開）:最短作業(yè)優(yōu)先算法ID到達(dá)運(yùn)行等待A0.0004.0000.000B1.0003.0003.0004.0004.0003.0002.0005.0009.0

10、0011.000開始0-0007.75000047完成周轉(zhuǎn)帶權(quán)周轉(zhuǎn)4.0004.0001.0007.0006.0002.00011.0007.0001.75016.00014.0002.8000 0 00 0 0平均周轉(zhuǎn)時(shí)間為:平均帶權(quán)周轉(zhuǎn)時(shí)間為：1-887500Press any key to continue五、實(shí)驗(yàn)小結(jié)FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于IO繁忙型的作業(yè)（進(jìn)程）。CPU繁忙型作業(yè)是指該類作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求LOo通常的 科學(xué)計(jì)算便屬于CPU繁忙型作業(yè)。LO繁忙型作業(yè)是指CPU進(jìn)行處理時(shí)需頻繁地請(qǐng)求I/O。目前的大多數(shù)事務(wù)處理都屬于LO

11、 繁忙型作業(yè)。SJ（P）F調(diào)度算法也存在不容忽視的缺點(diǎn)：該算法對(duì)長(zhǎng)作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16,其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3。 更嚴(yán)重的是，如果有一長(zhǎng)作業(yè)（進(jìn)程）進(jìn)入系統(tǒng)的后備隊(duì)列（就緒隊(duì)列），由于調(diào)度程序總是優(yōu) 先調(diào)度那些（即使是后進(jìn)來(lái)的）短作業(yè)（進(jìn)程），將導(dǎo)致長(zhǎng)作業(yè)（進(jìn)程）長(zhǎng)期不被調(diào)度。該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。由于作業(yè)（進(jìn)程）的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或 無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。#include Hstdafx.hn#iiicludedefi

12、ne MAX 100 typedef stmct PCBcharjob.id10;作業(yè)IDfloatAiT_tiine;到達(dá)時(shí)刻floatFun.time;估計(jì)運(yùn)行時(shí)間floatWhijtinie;等待時(shí)間floatStart_time;開始時(shí)刻floatFin_time;完成時(shí)刻floatTui_tmie;周轉(zhuǎn)時(shí)間floatWTur_time;帶權(quán)周轉(zhuǎn)時(shí)間mtOrder;優(yōu)先標(biāo)記Hst;void fcfs(list *p,int count);void priiit(list *p,int count);void avg(list *p,int count);void fcfs(list *

13、pjnt count)先來(lái)先服務(wù)算法(list temp;臨時(shí)結(jié)構(gòu)體變量inti;intj;for(i = l;i count;i-H-)按到達(dá)時(shí)刻直接插入排序(temp = pi;while(temp.AiT_tiine = 0)pi+U = plj;-j;pj+l=teinp;)for(i = 0;i count;i+)循環(huán)計(jì)算各個(gè)作業(yè)的時(shí)間值(if(i = 0) /pi.Start_tiine = pi.Aii_tmie; elsepi.Stait_tmie = pi-l.Fin_tmie;開始時(shí)刻一前一個(gè)作業(yè)的完成時(shí)刻pi.Wait_time = pi.Start.time - pi.

14、Anytime;等待=開始-到達(dá)pi.Fm_time = pi.Stait_time + pi.Fun_tiine;完成一開始+運(yùn)行pi.Tui_tiine = pi.Fm_time - pi.Air_time;周 轉(zhuǎn)=完成-至 U 達(dá)pi.WTur_time = pi.TuOmie / pi.Fun.tmie;帶權(quán)周轉(zhuǎn)=周轉(zhuǎn)/運(yùn)行retuni:最短作業(yè)優(yōu)先算法（sjf）最短運(yùn)行時(shí)間作業(yè)的下標(biāo)優(yōu)先級(jí)設(shè)置最短運(yùn)行時(shí)間開始的時(shí)刻list item;mt i = 0;mtj=0;mt k = 0;hit flag = 0:float niin = 0; float temp;結(jié)構(gòu)體變量temp =

15、p0. Anytime;先求出最先到達(dá)作業(yè)的時(shí)刻保存最先到達(dá)的作業(yè)的時(shí)刻最先到達(dá)的作業(yè)的下標(biāo)，默認(rèn)為p0fbi(i = 0;i count;i+)temp = pi. Anytime; k = i;)fbi(i = 0;i count;i+)pk.Order = -H-flag;設(shè)置優(yōu)先級(jí)為1,最高優(yōu)先級(jí)pk.Start_tiine = tenip:pk.WaiCtime pk.Fm_time pk.Tur_tmie pk.WTui_time=temp - pk.An_time;計(jì)算各個(gè)時(shí)間=temp + pk.Fun_time;=pk.Fin_tinie - pk.AiT_tiine;=pk

16、.Tui_tiine / pk.Fun_tiine;niui= 100;temp = pk.Fin_time;后一個(gè)作業(yè)的開始時(shí)刻是前一個(gè)作業(yè)的完成時(shí)刻fbr(j = 0J countJ+)if(pj.Order != 0 | temp - pj.ArOime pj.Fun_time) ( niiii = pj.Fun_tmie; k = j;/求出滿足條件最短運(yùn)行時(shí)間的作業(yè)的下標(biāo)) for(i = l;i count;i-H-)按優(yōu)先級(jí)排序item = pi;J 7；while(item.Order = 0)pU+i = pj;-j;pj+l =item;return:)輸出各個(gè)作業(yè)的詳細(xì)信

17、息mt i;printfC* * *iiH), pnntf（-IDt到達(dá)t運(yùn)行t等待t開始t完成t周轉(zhuǎn)t帶權(quán)周轉(zhuǎn)W） fbi(i = 0;i count;i+)pnntf(M%st%.3ft%3ft%3ft%3ft%.3ft%.3ft%.3fii,pi.job_id,pi.Air_tuiie.pi.Fun_tiine.p i.Wait_.time,pi.Stai-t_time,pi.Fm_time,pi.Tui_time.pi.WTur_tmie);return:void avg(list *p,int count)(float AvgTurl;平均周轉(zhuǎn)float AvgTur2;平均帶權(quán)周轉(zhuǎn)

18、float tl = 0;float t2 = 0;inti;周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)和fbi(i = 0;i count;i-H-) (tl +=pi.Tui_time;t2 += pi.WTui_time;AvgTiu 1 = tl/count;AvgTui2 = t2/count;pnntf（”n平均周轉(zhuǎn)時(shí)間為：%ft平均帶權(quán)周轉(zhuǎn)時(shí)間為：%fn,AvgTurlAvgTui2）;return:mt(list stMAX;iiitjob_count = 0;mt flag = 1;mt i = 0;最多可以一百個(gè)作業(yè)作業(yè)數(shù)量算法標(biāo)記pillltf(”請(qǐng)輸入作業(yè)數(shù)量：) scanf(H%d,&job_count);piuitf（”請(qǐng)輸入作業(yè)ID,到達(dá)時(shí)刻，估計(jì)運(yùn)行時(shí)間（用空格隔開）：sc