2022年時間片輪轉(zhuǎn)、最高響應(yīng)比優(yōu)先調(diào)度算法剖析

1、1 學號：課 程 設(shè) 計題目時間片輪轉(zhuǎn)、 最高響應(yīng)比優(yōu)先調(diào)度算法學院計算機科學與技術(shù)專業(yè)班級姓名指導教師吳利軍2013 年1 月14 日精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 13 頁 - - - - - - - - -2 課程設(shè)計任務(wù)書學生姓名：指導教師：吳利軍工作單位：計算機科學與技術(shù)學院題目: 進程調(diào)度模擬設(shè)計時間片輪轉(zhuǎn)、最高響應(yīng)比優(yōu)先調(diào)度算法初始條件：1預備內(nèi)容：閱讀操作系統(tǒng)的

2、處理機管理章節(jié)內(nèi)容，對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解。2實踐準備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù) :（包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1模擬進程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進程的基本信息，如進程名、到達時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2設(shè)計報告內(nèi)容應(yīng)說明： 需求分析； 功能設(shè)計（數(shù)據(jù)結(jié)構(gòu)及模塊說明）； 開發(fā)平臺及源程序的主要部分； 測試用例，運行結(jié)果與運行情況分析；我評價自與總結(jié)：i）你認為你完成的設(shè)計

3、哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；v）對實驗題的評價和改進意見，請你推薦設(shè)計題目。時間安排：設(shè)計安排一周：周1、周 2：完成程序分析及設(shè)計。周 2、周 3：完成程序調(diào)試及測試。周 4、周 5：驗收、撰寫課程設(shè)計報告。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，一律按0 分記）指導教師簽名：年月日系主任（或責任教師）簽名：年月日精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 13 頁 - - -

4、 - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 13 頁 - - - - - - - - -3 1. 需求分析1.1 模擬進程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進程的基本信息，如進程名、到達時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。1.2這個實驗主要是進程調(diào)度模擬設(shè)計，進程調(diào)度有很多方法， 這個課程設(shè)計要求我要使用時間片輪轉(zhuǎn)和最高響應(yīng)比兩中算法，來實現(xiàn)對進程的模擬。首先他要求能夠用兩種方法實現(xiàn)進

5、程調(diào)度，我們需要首先輸出一個選擇程序，來選擇一個調(diào)度算法， 入數(shù)據(jù)來進行運算， 這是我們首先要解決的問題。其次，我們要接近輸入數(shù)據(jù)的存放問題，畢竟我還需要數(shù)據(jù)來進行操作和調(diào)度。我們要用結(jié)構(gòu)體來存放一個進程的相關(guān)信息，例如：進程名字，進程到達時間，進程的運行時間。但是我們在出來進程的時候，還必須要按照一定的順序來處理，所以我們必須要對結(jié)構(gòu)體里存放的進程相關(guān)信息來進行排序。只有經(jīng)過處理過后，才能更容易的實現(xiàn)進程的調(diào)度，同時當不只一個進程的時候，我們還必須設(shè)置用多個地址單元來實驗對輸入的數(shù)據(jù)進行存儲，多個輸入就相當于的鏈表的插入處理，因此我們又必須要對鏈表之間的指針進行處理，這涉及到指針的跳轉(zhuǎn)，我們

6、必須要運用我們所學的知識進行。我們還必須要對程序的輸出進行處理，因為按照實驗要求，我們必須顯示進程調(diào)度隊列；根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。這要求我們要設(shè)計算法，將進程的調(diào)度順序給輸出，從輸出就可以檢查自己的設(shè)計是否是正確的，而響應(yīng)比其實進程的等待時間加上執(zhí)行時間，在除以執(zhí)行時間，得到的結(jié)果就是響應(yīng)比。而最高響應(yīng)比就是沒當一個進程執(zhí)行完成后，在這個時間比較各個時間各個進程的響應(yīng)比，響應(yīng)比最大的就會執(zhí)行， 而其他的進程則繼續(xù)等待， 一直循環(huán)做這個操作，這就是所謂的是最高響應(yīng)比調(diào)度算法。 時間片輪轉(zhuǎn)法就是將cpu 的執(zhí)行時間分成一個個大小相等的時間片，將這些時間片分別執(zhí)行就緒

7、隊列中的進程，時間片用完的進程就會回答就緒隊列的隊尾，等待cpu 的再次執(zhí)行。而周轉(zhuǎn)時間則是完成時間減去提交時間，平均周轉(zhuǎn)時間就是幾個進程的周轉(zhuǎn)時間的平均值。而帶權(quán)周轉(zhuǎn)時間就是周轉(zhuǎn)時間除以執(zhí)行時間。2. 功能設(shè)計2.1 最高響應(yīng)比的功能設(shè)計2.1.1 最高響應(yīng)比的結(jié)構(gòu)體struct zgxyb char name10; float arrivetime; float servicetime; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - -

8、- - - - - - - - 第 3 頁，共 13 頁 - - - - - - - - -4 float starttime; float finishtime; float zztime; float dqzztime; ;2.2.1 時間片的結(jié)構(gòu)體typedefstruct node datatype num,runtime; char name10; / 定義成字符串struct node *next; linknode; 3. 開發(fā)平臺及源程序的主要部分3.1 實驗的開發(fā)平臺visual c+ 6.0 3.2 實驗的主要代碼void input(zgxyb *p,int n) int

9、 i; printf(intput the processs name & arrivetime & servicetime:nfor exmple: a 0 100n); for (i=0;i=n-1;i+) printf(input the %dth processs information:n,i+1); scanf( %s%f%f,&,&pi.arrivetime,&pi.servicetime); void print(zgxyb *p,float arrivetime,float servicetime,float startt

10、ime,float finishtime,floatzztime, float dqzztime,int n) int k; printf(run order:); printf(%s,); for (k=1;k%s ,); printf(nthe processs information:n); printf(nnametarrivetservicetstarttfinishtzztdqzzn); for (k=0;k=n-1;k+) printf(%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftn,,pk.arrive

11、time,pk.servicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 13 頁 - - - - - - - - -5 / 按到達時間排序void sort(zgxyb *p,int n) for ( int i=0;i=n-1;i+) for ( int j=0;j=i;j+

12、) if (pi.arrivetimepj.arrivetime) zgxyb temp; temp=pi; pi=pj; pj=temp; /yun xing jieduan void deal(zgxyb *p,float arrivetime,float servicetime,float starttime,float finishtime,float&zztime, float &dqzztime,int n) int k; for (k=0;k=n-1;k+) if (k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk

13、.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for (k=0;k=n-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime; void zgxyb(zgxyb *p,int n) float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,d

14、qzztime=0; sort(p,n); for ( int m=0;mn-1;m+) 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 13 頁 - - - - - - - - -6 if (m=0) pm.finishtime=pm.arrivetime+pm.servicetime; else pm.finishtime=pm-1.finishtime+pm.servicetime; i

15、nt i=0,n; for (n=m+1;n=n-1;n+) if (pn.arrivetime=pm.finishtime) i+; float max=(pm.finishtime-pm+1.arrivetime)/pm+1.servicetime;/ 第m+1 個的響應(yīng)比int follow=m+1; for ( int k=m+1;km+i;k+) if (maxnum=x; s-runtime=y; /strcpy(s-name,ch);/直接字符串復制for ( int i=0;inamei=chi; r-next=s; r=s; scanf(%d %s %d,&x,&am

16、p;ch,&y); r-next=null; return head; /* 輸出帶頭結(jié)點的單鏈表*/ void print(linklist head) linklist p; p=head-next; printf(list is:n); printf(num name runtimen); while (p) printf(%d%5s%6dn ,p-num,p-name,p-runtime); p=p-next; printf(n ); void main() int g; scanf( %d,&g); 精品學習資料 可選擇p d f - - - - - - - - -

17、- - - - - 第 7 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁，共 13 頁 - - - - - - - - -8 if (g=1) linklist head,pre,p,r; int t,i; head=creatlinklist(); print(head); printf( 請輸入 runtime:); scanf( %d,&t); pre=head; p=head-next; while (p) if (p-runtimet)/* 如果運行時間大于時間片*/ r

18、=p-next; p-runtime=p-runtime-t;/* 將第一個進程的運行時間減去一個時間片的時間*/ while (r-next)/* 將r指向鏈表的最后一個結(jié)點以便用尾插法將p結(jié)點插入到鏈表的最后*/ r=r-next; pre-next=p-next; p-next=null; r-next=p; p=head-next; i=1; while (p) /* 將進程的序號重新從開始設(shè)置一遍*/ p-num=i+; p=p-next; else pre-next=p-next;/* 如果進程運行時間小于時間片，就將第一個進程刪除*/ free(p); p=head-next;

19、i=1; while (p) /* 因為刪了一個進程就需要重新從開始設(shè)置一遍進程的排列序號*/ p-num=i+; p=p-next; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 13 頁 - - - - - - - - -9 print(head);/* 打印進程列表 */ pre=head; p=head-next; else int n; printf(-高響應(yīng)比調(diào)度算法-n); p

20、rintf(input the processs number:n); scanf(%d,&n); input(a,n); zgxyb *c=a; zgxyb(c,n); 4. 運行結(jié)果與運行情況分析程序的第一步選擇最高響應(yīng)比調(diào)度算法，輸入進程輸入3 個，進程名字提交時間運行時間a 2 3 b 3 2 c 3 3 程序的驗證：第一個進程在 2 點提交， 3 個小時的執(zhí)行時間，在2 點沒有別的進程，所以a先執(zhí)行， 5 點執(zhí)行完后，而在5 點執(zhí)行前， b，c 都提交了，所以就要判斷響應(yīng)比，響應(yīng)比是等待時間加上執(zhí)行時間，除以執(zhí)行時間，所以b 的響應(yīng)比是 2，c 的響應(yīng)比是 5/3,所以 b

21、的響應(yīng)比高， b 先執(zhí)行，最后是c 執(zhí)行，周轉(zhuǎn)時間是完成時間減去提交時間， 而帶權(quán)周轉(zhuǎn)時間是周轉(zhuǎn)時間除以執(zhí)行時間。經(jīng)檢驗，平均周轉(zhuǎn)時間 4.67，平均帶權(quán)周轉(zhuǎn)時間是1.67.，經(jīng)檢驗，結(jié)果是正確的。精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁，共 13 頁 - - - - - - - - -10 如果是時間片輪轉(zhuǎn)則運行結(jié)果為：精品學習資料 可選擇p d f - - - - - - - - - -

22、 - - - - 第 10 頁，共 13 頁 - - - - - - - - -精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁，共 13 頁 - - - - - - - - -11 5. 我評價自與總結(jié)5.1 程序好的方面本次實驗的輸入與輸出基本滿足實驗所要求的，最高響應(yīng)比的調(diào)度算法的輸出結(jié)果采用表格的形式的輸出， 比較清晰， 容易看懂， 通過輸出結(jié)果能夠清晰的看出結(jié)果的正確與否。輸入與輸出比較明確，不會出現(xiàn)多種意思。結(jié)構(gòu)比較清晰，不會到處跳轉(zhuǎn)， 容易理解。 指令之間的跳轉(zhuǎn)不會讓人難以理解。最高響應(yīng)比中進程分為兩個狀態(tài)， 等待狀態(tài)和完成狀態(tài)

23、， 當程序完成時候狀態(tài)變成完成狀態(tài)，每次執(zhí)行只會執(zhí)行等待狀態(tài)的進程，不會執(zhí)行完成狀態(tài)的進程。 結(jié)果中還有調(diào)度順序，5.2 從本設(shè)計得到的收獲從本次實驗中， 我學到了較多東西， 首先是結(jié)構(gòu)體的定義和調(diào)用，這次實驗首先遇到的問題結(jié)構(gòu)體的定義和調(diào)用， 之后還涉及到指針的跳轉(zhuǎn)， 鏈表的插入與刪除，因此指針的跳轉(zhuǎn)是必須要飛行清楚明白的，否則就會出現(xiàn)各種錯誤， 最終將需要修改，而且還必須學會子函數(shù)的使用，必須實驗各種子函數(shù)來實現(xiàn)不同的功能，綜合起來才能實現(xiàn)實驗所要求的功能。同時函數(shù)的頭文件也必須要包含多個東西，來適應(yīng)我們的要求， 同時我們還必須根據(jù)要求使用多個全局變量，來實現(xiàn)我們的各種要求。5.4 其他方

24、法對與最高響應(yīng)比的想法：前提設(shè)定：參數(shù)進程隊列按順序排好。設(shè)置一個系統(tǒng)時間變量，記錄當前系統(tǒng)時間調(diào)度算法思路：1.系統(tǒng)時間取得第一個進程的提交時間，并執(zhí)行第一個進程；2.當某進程執(zhí)行完成時，系統(tǒng)時間加上該完成進程的運行時間，并刪除該節(jié)點，若第一個節(jié)點的提交時間就比當前系統(tǒng)時間大或等于，此情況下，需要修改系統(tǒng)時間，且此時第一個進程就是下一個該調(diào)度的進程，否側(cè)，在從頭結(jié)點開始掃描進程隊列，直到某進程提交時間大于等于當前系統(tǒng)時間，先假設(shè)第一個的響應(yīng)比最高，標志指針指向第一個節(jié)點，掃描過程中，記錄當前掃描到的進程的響應(yīng)比，若比記錄值大，則修改記錄值和標志指針。掃描完成后，執(zhí)行標志指針指向的進程，反復執(zhí)

25、行2，直至沒有進程了對于輸入， 輸出的界面也有必要改進一下，是他跟具有整齊性， 不會出現(xiàn)凌亂的情況，在具體細節(jié)上要更加注意， 要用更少的代碼實現(xiàn)更多的功能，占用更少的空間，總之要精益求精。5.5 是題目的評價和建議這次的實驗，讓我對調(diào)度算法有了更加深刻的了解，對應(yīng)編程序也有了更加深刻的理解， 編程序不是一件容易的事情，需要很多的時間來實現(xiàn)和修改，而且實踐對于計算機的學習是很重要的，本次的題目跟我們所學有關(guān)聯(lián)性較大，對我們學習很有用， 題目基本上將我們平時所學習的東西都用到了，雖然每個人側(cè)重點精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁，共 13 頁 - - - - - - - - -精品