高響應(yīng)比調(diào)度算法

1、淮北師范大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)設(shè)計(jì)報(bào)告操作系統(tǒng)程序設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課題：高響應(yīng)比調(diào)度算法所屬學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)所屬班級：11級計(jì)算機(jī)非師姓 名： 李 志 國輔導(dǎo)老師： 施 漢 琴2014年3月20日目 錄實(shí)驗(yàn)設(shè)計(jì)課題第03頁課程設(shè)計(jì)目的第03頁課程設(shè)計(jì)內(nèi)容第03頁課程設(shè)計(jì)要求第04頁相關(guān)知識介紹第05頁程序功能說明第06頁各段程序說明第07頁設(shè)計(jì)的流程圖第09頁程序執(zhí)行截圖第11頁源程序的代碼第14頁實(shí)驗(yàn)小結(jié)體會第19頁實(shí)驗(yàn)設(shè)計(jì)課題 設(shè)計(jì)題目：采用高響應(yīng)比算法的進(jìn)程調(diào)度程序指導(dǎo)老師：施漢琴課程設(shè)計(jì)目的操作系統(tǒng)課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)重要的教學(xué)環(huán)節(jié)，它為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，將課本上的理論知識

2、和實(shí)際有機(jī)的結(jié)合起來，獨(dú)立分析和解決實(shí)際問題的機(jī)會。 進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識。 培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。 提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計(jì)的能力。 提高學(xué)生分析問題、解決問題以及綜合利用C語言進(jìn)行程序設(shè)計(jì)的能力。課程設(shè)計(jì)內(nèi)容問題分析：在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運(yùn)行得不到保證。于是我們想到了一種辦法解決這個(gè)問題，就是引用動(dòng)態(tài)優(yōu)先權(quán)、并使作業(yè)的優(yōu)先級隨著等待時(shí)間的增加而以速率a提高，長作業(yè)在等待一定的時(shí)間后，必然有機(jī)會分配到處理機(jī)，這樣長作業(yè)也得到了運(yùn)行。由此可見：（1）如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間越

3、短，其優(yōu)先權(quán)越高，因此該算法有利于短作業(yè)。（2）當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)取決與其等待的時(shí)間，等待時(shí)間越長，其優(yōu)先權(quán)越高，因而它實(shí)現(xiàn)的是先來先服務(wù)。（3）對于長作業(yè)，作業(yè)的優(yōu)先權(quán)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高，從而也可以獲得處理機(jī)。 設(shè)計(jì)內(nèi)容：設(shè)計(jì)并實(shí)現(xiàn)一個(gè)采用高響應(yīng)比算法的進(jìn)程調(diào)度演示程序，響應(yīng)比R定義如下：RWT/T1W/T其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間， 為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)W間。 每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。這樣，即使是長作業(yè)，隨著它等待時(shí)間的增加，W/T也就隨著增加，也就有機(jī)會

4、獲得調(diào)度執(zhí)行。 這種算法是介于FCFS和SJF之間的一種折中算法。由于長作業(yè)也有機(jī)會投入運(yùn)行，在同一時(shí)間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRRN方式時(shí)其吞吐量將小于采用SJF法時(shí)的吞吐量。另外，由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。課程設(shè)計(jì)要求1. 每一個(gè)進(jìn)程有一個(gè)PCB，其內(nèi)容可以根據(jù)具體情況設(shè)定。2. 進(jìn)程數(shù)、進(jìn)入內(nèi)存時(shí)間、要求服務(wù)時(shí)間、優(yōu)先級等均可以在界面上設(shè)定3. 可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行進(jìn)程數(shù)、進(jìn)入內(nèi)存時(shí)間、時(shí)間片長度、進(jìn)程優(yōu)先級的初始化4. 可以在運(yùn)行中顯示各進(jìn)程的狀態(tài)：就緒、執(zhí)行 （由于不要求設(shè)置互斥資源與進(jìn)程間的同步關(guān)系，故只有兩種狀態(tài)）

5、5. 采用可視化界面，可在進(jìn)程調(diào)度過程中隨時(shí)暫停調(diào)度，查看當(dāng)前進(jìn)程的狀態(tài)以及相應(yīng)的阻塞隊(duì)列6. 有性能比較功能，可比較同一組數(shù)據(jù)在不同調(diào)度算法下的平均周轉(zhuǎn)時(shí)間7. 具有一定的數(shù)據(jù)容錯(cuò)性相關(guān)知識介紹 定義高響應(yīng)比優(yōu)先調(diào)度算法的基本思想是把CPU分配給就緒隊(duì)列中響應(yīng)比最高的進(jìn)程。 基本思想短作業(yè)優(yōu)先調(diào)度算法 + 動(dòng)態(tài)優(yōu)先權(quán)機(jī)制，既考慮作業(yè)的執(zhí)行時(shí)間也考慮作業(yè)的等待時(shí)間，綜合了先來先服務(wù)和最短作業(yè)優(yōu)先兩種算法的特點(diǎn)。原理高響應(yīng)比優(yōu)先調(diào)度算法既考慮作業(yè)的執(zhí)行時(shí)間也考慮作業(yè)的等待時(shí)間，綜合了先來先服務(wù)和最短作業(yè)優(yōu)先兩種算法的特點(diǎn)。該算法中的響應(yīng)比是指作業(yè)等待時(shí)間與運(yùn)行比值，響應(yīng)比公式定義如下：響應(yīng)比 =

6、（等待時(shí)間+要求服務(wù)時(shí)間）/ 要求服務(wù)時(shí)間,即RR=（w+s）/s=1+w/s，因此響應(yīng)比一定是大于1的。如實(shí)例：某系統(tǒng)有3個(gè)作業(yè)，系統(tǒng)確定它們在全部到達(dá)后，再開始采用響應(yīng)比高者優(yōu)先的調(diào)度算法，則它們的調(diào)度順序是什么？各自的周轉(zhuǎn)時(shí)間是什么？作業(yè)號 提交時(shí)間 運(yùn)行時(shí)間1 8.8 1.52 9.0 0.43 9.5 1.0(1)如果都到達(dá)再算的話,等待時(shí)間=最后一個(gè)的提交時(shí)間-該作業(yè)到達(dá)的時(shí)刻1: 9.5-8.8=0.72: 9.5-9=0.53: 0所以響應(yīng)比為（等待時(shí)間+要求服務(wù)時(shí)間）要求服務(wù)時(shí)間=等待時(shí)間/要求服務(wù)時(shí)間+11: 0.7/1.5+1=1.472: 0.5/0.4+1=2.253

7、:1所以2先運(yùn)行,2從9.5開始運(yùn)行到9.9結(jié)束;再以9.9時(shí)刻算響應(yīng)比:1:(9.9-8.8)/1.5+1=1.733:(9.9-9.5)/1+1=1.4所以2執(zhí)行完后1開始執(zhí)行,從9.9執(zhí)行到11.4結(jié)束最后一個(gè)是3:從11.4開始執(zhí)行到12.4結(jié)束(2)如果不是都到達(dá)后才運(yùn)行，那么在8.8時(shí)只有作業(yè)1到達(dá)，所以先運(yùn)行作業(yè)18.8+1.5（運(yùn)行時(shí)間）=10.3到10.3的時(shí)候作業(yè)1完成，此時(shí)作業(yè)2和3都已到達(dá)所以計(jì)算其響應(yīng)比（等待時(shí)間+要求服務(wù)時(shí)間）要求服務(wù)時(shí)間=等待時(shí)間/要求服務(wù)時(shí)間+1作業(yè)2：（10.3-9.0）/0.4+1=4.325作業(yè)3：（10.3-9.5）/1.0+1=1.8所

8、以先運(yùn)行作業(yè)210.3+0.4=10.7到10.7運(yùn)行作業(yè)310.7+1.0=11.7到11.7結(jié)束優(yōu)缺點(diǎn)短作業(yè)與先后次序的兼顧，且不會使長作業(yè)長期得不到服務(wù)響應(yīng)比計(jì)算系統(tǒng)開銷，增加系統(tǒng)開銷。適用場合批處理系統(tǒng)。程序功能說明 程序通過定義調(diào)用函數(shù)，杜如用戶從鍵盤輸入的需要服務(wù)的進(jìn)程的各項(xiàng)參數(shù)，并進(jìn)行調(diào)度算法模擬。首相對讀入的進(jìn)程各個(gè)參數(shù)進(jìn)行保存，而后進(jìn)行判斷是否進(jìn)入內(nèi)存之中，如果在內(nèi)存之中則進(jìn)行高響應(yīng)比優(yōu)先的的方式進(jìn)行排隊(duì)服務(wù)運(yùn)行，如果沒有進(jìn)入內(nèi)存，則進(jìn)程等待。直到所有進(jìn)程服務(wù)運(yùn)行完畢為止。各個(gè)函數(shù)都有各自的功能，相互協(xié)調(diào)進(jìn)行整體函數(shù)功能的實(shí)現(xiàn)。采用響應(yīng)比高者優(yōu)先調(diào)度算法進(jìn)行調(diào)度時(shí)，必須計(jì)算出

9、系統(tǒng)中所有滿足必要條件作業(yè)的響應(yīng)比，從中選擇響應(yīng)比最高的一個(gè)作業(yè)裝入主存儲器分配資源。由于是實(shí)驗(yàn)，所以就將作業(yè)控制塊出隊(duì)，并輸出作業(yè)名代替裝入處存儲器，同時(shí)修改系統(tǒng)的資源數(shù)量。各段程序說明首先進(jìn)行函數(shù)相關(guān)參數(shù)定義，具體函數(shù)如下：struct Pchar name10;float arrivetime;float servicetime;float starttime;float finishtime;float zztime;float dqzztime;定義函數(shù)參數(shù)中進(jìn)程的名字“name”、進(jìn)程到達(dá)的時(shí)間“arrivetime”、進(jìn)程所需服務(wù)時(shí)間“servicetime”、以及處理時(shí)間“st

10、arttime”和完成時(shí)間“finishtime”。Input函數(shù)接收用戶鍵盤輸入的進(jìn)程各個(gè)參數(shù)并作為函數(shù)后期執(zhí)行的引用數(shù)據(jù)，包括進(jìn)程的名稱、到達(dá)時(shí)間、要求服務(wù)時(shí)間。for(i=0;i=N-1;i+)printf(請輸入第%d個(gè)進(jìn)程的進(jìn)程名 : n,i+1);scanf(%s,&);printf(請輸入第%d個(gè)進(jìn)程的到達(dá)時(shí)間 :n,i+1);scanf(%f,&pi.arrivetime);printf(請輸入第%d個(gè)進(jìn)程的要求服務(wù)的時(shí)間 :n,i+1);scanf(%f,&pi.servicetime);由此函數(shù)可實(shí)現(xiàn)對用戶所輸入的數(shù)據(jù)的接收功能。sort(P *p,int N

11、)，run(P *p,int N)函數(shù)實(shí)現(xiàn)對進(jìn)程響應(yīng)比的計(jì)算和排序。首先利用公式“優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間=響應(yīng)時(shí)間/要求服務(wù)時(shí)間”計(jì)算用戶輸入的進(jìn)程的響應(yīng)比，函數(shù)實(shí)現(xiàn)如下：for(int i=0;iN-1;i+)for(int j=i+1;jpj.arrivetime)P temp;temp=pi;pi=pj;pj=temp;int k;for(k=0;k=N-1;k+)if(k=0)pk.starttime=pk.arrivetime;pk.finishtime=pk.arrivetime+pk.servicetime;elsepk.starttime=pk-1.f

12、inishtime;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;計(jì)算的響應(yīng)比進(jìn)行比較，結(jié)果根據(jù)需要進(jìn)行排序響應(yīng)比高的進(jìn)程排在前面，響應(yīng)比低的進(jìn)程排在后面，這樣就可以使響應(yīng)比搞得進(jìn)程獲得較高的優(yōu)先權(quán)，能夠先運(yùn)行。最后通過函數(shù)Grade(P *p,int N)來實(shí)現(xiàn)輸出進(jìn)程在各個(gè)時(shí)間短的運(yùn)行狀況，包括正在運(yùn)行，正在等待和已到達(dá)狀態(tài)。設(shè)計(jì)的流程圖程序設(shè)計(jì)總流程圖：讀取進(jìn)程判

13、斷進(jìn)程是否進(jìn)入內(nèi)存對響應(yīng)比排序高的進(jìn)程先運(yùn)行等 待結(jié) 束是否開 始高響應(yīng)比函數(shù)執(zhí)行過程流程圖： 開 始 當(dāng)前作業(yè)為依編號找到的第一個(gè)還未執(zhí)行的作業(yè) 當(dāng)前作業(yè)是最后一個(gè)作業(yè) 當(dāng)前作業(yè)和下一個(gè)還沒執(zhí)行的作業(yè)比較 當(dāng)前作業(yè)在上次作業(yè)被執(zhí)行完之前到達(dá) 同時(shí)到達(dá) 當(dāng)前作業(yè)取較早達(dá)到且響應(yīng)比較高的一個(gè) 當(dāng)前作業(yè)取較早到達(dá)的一個(gè) 當(dāng)前作業(yè)取相應(yīng)比較高的一個(gè) 返回這一次要執(zhí)行的作業(yè)程序執(zhí)行截圖用戶手動(dòng)輸入進(jìn)程的各項(xiàng)信息：確定后程序執(zhí)行輸出如下圖：源程序的代碼#include struct Pchar name10;float arrivetime;float servicetime;float startti

14、me;float finishtime;float zztime;float dqzztime;P a100;void input(P *,int);void Traverse(P *,int);void sort(P *,int);void Grade(P *,int);void main()int N;printf(n);printf(ttt模擬高響應(yīng)比調(diào)度算法n);printf(n);printf(NOW!模擬開始:n);printf(n);printf(請輸入需要服務(wù)的進(jìn)程的個(gè)數(shù):n);scanf(%d,&N);input(a,N);Grade(a,N);void input(P *p

15、,int N)int i;for(i=0;i=N-1;i+)printf(請輸入第%d個(gè)進(jìn)程的進(jìn)程名 : n,i+1);scanf(%s,&);printf(請輸入第%d個(gè)進(jìn)程的到達(dá)時(shí)間 :n,i+1);scanf(%f,&pi.arrivetime);printf(請輸入第%d個(gè)進(jìn)程的要求服務(wù)的時(shí)間 :n,i+1);scanf(%f,&pi.servicetime);void Traverse(P *p,int N)int k;printf(n);printf(n);printf(進(jìn)程運(yùn)行的順序?yàn)?);printf(%s,);for(k=1;k%s,

16、);printf(n);printf(n);printf(進(jìn)程運(yùn)行的詳細(xì)信息如下:n);printf(n);printf(名稱 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 結(jié)束時(shí)間n);for(k=0;k=N-1;k+)printf(%st%-.2ft%-.2ft%-.2ft%-.2ftn,,pk.arrivetime,pk.servicetime,pk.starttime,pk.finishtime);printf(名稱 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間n);for(k=0;k=N-1;k+)printf(%st%-.2ft%-.2ftn,,pk.zztime,pk.dqzztime);

17、void sort(P *p,int N)for(int i=0;iN-1;i+)for(int j=i+1;jpj.arrivetime)P temp;temp=pi;pi=pj;pj=temp;void run(P *p,int N)int k;for(k=0;k=N-1;k+)if(k=0)pk.starttime=pk.arrivetime;pk.finishtime=pk.arrivetime+pk.servicetime;elsepk.starttime=pk-1.finishtime;pk.finishtime=pk-1.finishtime+pk.servicetime;for

18、(k=0;k=N-1;k+)pk.zztime=pk.finishtime-pk.arrivetime;pk.dqzztime=pk.zztime/pk.servicetime;void Grade(P *p,int N)float arrivetime=0;float servicetime=0;float starttime=0;float finishtime=0;float zztime=0;float dqzztime=0;sort(p,N);printf(n);printf(n);for(int m=0 ; mN-1 ; m+)if(m=0)pm.finishtime=pm.arr

19、ivetime+pm.servicetime;printf(在第%-.0f時(shí)刻進(jìn)程信息n,pm.arrivetime);elsepm.finishtime=pm-1.finishtime+pm.servicetime;printf(在第%-.0f時(shí)刻進(jìn)程信息n,pm-1.finishtime);int i=0,n;printf(%s正在運(yùn)行n,);for(n=m+1;n=N-1;n+)if(pn.arrivetime=pm.finishtime)printf(%s進(jìn)程已到達(dá)n,);i+;elseprintf(%s進(jìn)程未到達(dá)n,);for(int l=0;lm;l+)printf(%s進(jìn)程已完成n,);float max=(pm.finishtime-pm+1.arrivetim