1、題 目 先來先服務FCFS和短作業優先SJF進程調度算法姓名:學口號:專業:學院:指導教師：二零一八年十一月林若寧一、實驗目的模擬單處理器系統的進程調度，分別采用短作業優先和先來先服務的進程調度算法作為 進程設計算法，以加深對進程的概念及進程調度算法的理解.二、實驗內容1.短作業優先調度算法原理短作業優先調度算法，是指對短作業或斷進程優先調度的算法。它們可以分別可以用于作業調度和進程調度。短作業優先調度算法，是從后備隊列中選擇一個或若干個運行時間最 短的作業，將它們調入內存運行。 短進程優先調度算法，是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它使它立即執行并一直執行到完成，或

2、發生某事件而被阻塞放棄處理機時再重新調度。2.先來先服務調度算法原理先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。當在作業調度中采用該算法時，每次調度都是從后備作業隊列中選擇一個或 多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然后放入就緒隊列。在進程調度中采用 FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊 列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞后 才放棄處理機。三、程序設計1.概要設計程序包括主函數、FCFS算法函數、SJF算法函數、輸出函數；主函數流程：輸入文件中

3、的數據一顯示各進程數據一選擇算法一調用相應算法的函數一輸出結果2.算法流程Fcrs憲東憲冊務耳注旅程a井抬個邊愷完電行判針二一個遲遵旳亮 咸曲向是否*于下一a禪的刮容寸同h-午旌握的畀怡時只就 上于走程的兗時亙并枱T個丸程的莽危時間從 它五島的到達時間干媳-IS帶？加，求總的 輻時臥崩諾 取同祐時間求平均周轉時q. 帝權捌轉臨間W調用藥束SJF算法流程圖:化 5. It J. <JI Llt.J、IS涼，屜"11 rtj *', 4rj 'I P'll WAj ，njbtrfz L_ j I I 糾L lUpljllLF丄 11?二 .“直叭 1|_=_

4、s冒JF流程圖;3.詳細設計(1 )定義一個結構體typ edef struct PCBcharjob_id10;/作業IDfloatArr_time;/到達時刻floatFun _time;估計運行時間floatWait_time;/等待時間floatStart_time;開始時刻floatFin_time;/完成時刻floatTur_time;周轉時間floatWTur_time;/帶權周轉時間intOrder;/優先標記list;先來先服務算法函數先來先服務算法void fcfs(list *p ,i nt count)list temp;臨時結構體變量int i;int j;/按到達時

5、刻直接插入排序for(i = 1;i < count;i+) temp = pi;j = i-1;while(temp.Arr_time < pj.Arr_time && j >= 0) pj+1 = pj; -j;pj+1 = temp;for(i = 0;i < count;i+)if(i = 0)pi.Start_time = pi.Arr_time;elsepi.Start_time = pi-1.Fin_time; pi.Wait_time pi.Fin_time pi.Tur_time pi.WTur_time/循環計算各個作業的時間值/開始

6、時刻 = 前一個作業的完成時刻= pi.Start_time - pi.Arr_time;= pi.Start_time + pi.Fun_time;= pi.Fin_time - pi.Arr_time;= pi.Tur_time / pi.Fun_time;/等待 =開始 -到達/完成 =開始 +運行/周轉 =完成 -到達/ 帶權周轉 =周轉 /運行return;3）最短作業優先函數void sjf(list *p,int count) list item;int i = 0;int j = 0;int k = 0; int flag = 0;/結構體變量/最短作業優先算法（ sjf ）/

7、最短運行時間作業的下標/優先級設置float min = 0;float temp;/最短運行時間/開始的時刻temp = p0.Arr_time;/先求出最先到達作業的時刻for(i = 0;i < count;i+)if(temp > pi.Arr_time)temp = pi.Arr_time; k = i;/保存最先到達的作業的時刻/最先到達的作業的下標，默認為p0for(i = 0;i < count;i+)pk.Order = +flag;/ 設置優先級為 1，最高優先級pk.Start_time = temp; pk.Wait_time pk.Fin_time

8、pk.Tur_time pk.WTur_time= temp - pk.Arr_time;= temp + pk.Fun_time;= pk.Fin_time - pk.Arr_time;= pk.Tur_time / pk.Fun_time;/計算各個時間min = 100;temp = pk.Fin_time;業的完成時刻/后一個作業的開始時刻是前一個作for(j = 0;j < count;j+)<=if(pj.Order != 0 | temp - pj.Arr_time <= 0)/ 跳過不滿足條件的 (已設置優先級的 和 到達時刻要晚于前一個作業的完成時刻的)co

9、ntinue;if(min > pj.Fun_time)min = pj.Fun_time;k = j;/ 求出滿足條件最短運行時間的作業的下標/按優先級排序for(i = 1;i < coun t;i+)item = p i;j = i-1;while(item.Order < pj.Order && j >= 0) pj+1 = Pj；T；pj+1 = item;return;四、實驗結果 測試數據:進程名到達時間運行時間A04B13C25D44(1)先來先服務算法調試冋"5:：小血班F樂MftDpbmlfrfv祈円產譜囁娃Sw存層時刻,A

10、 0 4B 1 3C 2 5b 4 *1謂選扌密遜丄:嶄篠鵰估計運行時間瞪用空格F訴九劉達a.aoa運行4.eBaH .土0.800汁始e.aee元成4.e0Q居轉4.B9B帶權周轉i.Baa1.0092.0094.0093.0005. see4.eea3.000B.eoo8.0004. see7.9&0is.eos7.eoe12.9E016.0006.B9B18.90915.9092.EIQ92. BQa3. BQ9s.eeaeaa+均帶權令轉時I日性：2.060900Press anu kev to continue(2 )最短作業優先算法調試關A爲:驀篤侯時劉.怙計主行時間e空格

11、隔開:A a 4B 1 3C 2 bD 4 4_lI 1肩最矩化業優先算疾U HB到達9.093t .oae運行i.oeas.oea開始e.eee4.e0e7E成4.0007.009周轉4.eaeE.BQQ制5周轉i.aees.asB4.8904.0003. seeT.eee±±.000V.B001-750V.WUIb.UktId14. WU平均周蒔時間為;7.750006平均帶權周轉刊間為；1.857590Press any ksu to cnntinnA_五、實驗小結FCFS調度算法有利于 CPU繁忙型的作業，而不利于 I/O繁忙型的作業(進程)。CPU繁忙型作業是指該

12、類作業需要大量的CPU時間進行計算，而很少請求I/O。通常的科學計算便屬于CPU繁忙型作業。I/O繁忙型作業是指 CPU進行處理時需頻繁地請求 I/O O目前的大多數事務處理都屬于I/O繁忙型作業。C 的周轉時間由 10 增至 16，其帶權周轉時間由 2 增至 3.1 。 （進程 ）進入系統的后備隊列 （就緒隊列 ），由于調度程序總是優 ）短作業 （進程），將導致長作業 （進程 ）長期不被調度。（進程 ）會被及時處理。 而用戶又可能會有意或SJ（P）F 調度算法也存在不容忽視的缺點： 該算法對長作業不利，如作業 更嚴重的是，如果有一長作業 先調度那些 （即使是后進來的該算法完全未考慮作業的緊迫

13、程度，因而不能保證緊迫性作業 由于作業 （進程 ）的長短只是根據用戶所提供的估計執行時間而定的， 無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。#include "stdafx.h" #include<stdio.h> #define MAX 100typedef struct PCB charjob_id10;/ 作業 IDfloatArr_time;/到達時刻floatFun_time;/估計運行時間floatWait_time;/等待時間floatStart_time;/開始時刻floatFin_time;/完成時刻floatT

14、ur_time;/周轉時間floatWTur_time;/帶權周轉時間intOrder;/優先標記list;void fcfs(list *p,int count);void sjf(list *p,int count);void print(list *p,int count);void avg(list *p,int count);void fcfs(list *p,int count) list temp;int i;int j;/先來先服務算法/臨時結構體變量for(i = 1;i < count;i+)temp = pi;j = i-1;/按到達時刻直接插入排序while(te

15、mp.Arr_time < pj.Arr_time && j >= 0) pj+1 = pj; -j;pj+1 = temp;for(i = 0;i < count;i+) /循環計算各個作業的時間值if(i = 0)pi.Start_time = pi.Arr_time;elsepi.Start_time = pi-1.Fin_time;/開始時刻 =前一個作業的完成時刻 pi.Wait_time pi.Fin_time pi.Tur_time pi.WTur_time/等待 =開始 -到達/完成 =開始 +運行/周轉 =完成 -到達/ 帶權周轉 =周轉 /

16、運行= pi.Start_time - pi.Arr_time;= pi.Start_time + pi.Fun_time;= pi.Fin_time - pi.Arr_time;= pi.Tur_time / pi.Fun_time;return;void sjf(list *p,int count) list item; int i = 0;int j = 0; int k = 0;int flag = 0; float min = 0; float temp;/結構體變量/最短作業優先算法（ sjf ）/最短運行時間作業的下標/優先級設置/最短運行時間/開始的時刻temp = p0.Ar

17、r_time;/先求出最先到達作業的時刻for(i = 0;i < count;i+) if(temp > pi.Arr_time)temp = pi.Arr_time; k = i;/保存最先到達的作業的時刻/最先到達的作業的下標，默認為p0for(i = 0;i < count;i+)pk.Order = +flag;/ 設置優先級為 1，最高優先級pk.Start_time = temp; pk.Wait_time pk.Fin_time pk.Tur_time pk.WTur_time= temp - pk.Arr_time;= temp + pk.Fun_time;

18、= pk.Fin_time - pk.Arr_time;= pk.Tur_time / pk.Fun_time;/計算各個時間min = 100;temp = pk.Fin_time; 業的完成時刻/后一個作業的開始時刻是前一個作for(j = 0;j < count;j+)if(pj.Order != 0 | temp - pj.Arr_time <= 0)/ 跳過不滿足條件的 (已設置優先級的 和 到達時刻要晚于前一個作業的完成時刻的)<=continue;if(min > pj.Fun_time) min = pj.Fun_time; k = j;/求出滿足條件最

19、短運行時間的作業的下標for(i = 1;i < count;i+) /按優先級排序return;item = pi; j = i-1;while(item.Order < pj.Order && j >= 0) pj+1 = pj;-j;pj+1 = item;void print(list *p,int count)/輸出各個作業的詳細信息int i;printf("*n"); printf("IDt到達t運行t等待t開始t完成t周轉t帶權周轉n");for(i = 0;i < count;i+) printf

20、("%st%.3ft%.3ft%.3ft%.3ft%.3ft%.3ft%.3fn",pi.job_id,pi.Arr_time,pi.Fun_time,pi.Wait_time,pi.Start_time,pi.Fin_time,pi.Tur_time,pi.WTur_time);return;void avg(list *p,int count) /平均周轉/平均帶權周轉float AvgTur1;float AvgTur2;float t1 = 0;float t2 = 0;int i;for(i = 0;i < count;i+)/周轉時間和/帶權周轉和t1 += pi.Tur_time;t2 += pi.WTur_time; AvgTur1 = t1/count;AvgTur2 = t2/count;printf（"n 平均周轉時間為： %ft 平均帶權周轉時間為： %fn",AvgTur1,AvgTur2）;printf(&qu