操作系統(tǒng)原理實驗報告

操作系統(tǒng)原理期末試驗匯報最早截止優(yōu)先（EDF）算法和最低松弛度優(yōu)先（LLF）算法C語言模擬姓名：學號：指導老師：專業(yè)：試驗目標：加深對實時調度了解，加深對最早截止優(yōu)先算法和最低松弛度優(yōu)先算法了解，將C語言學習應用到實踐。試驗內容：本試驗用C語言對兩種實時調度系統(tǒng)進行了模擬。分時調度系統(tǒng)主要是實現進程或任務調度合理分配，既能合理分配任務，又能滿足用戶對響應時間要求。當任務為實時任務時，即當對任務完成截止時間有要求時，分時系統(tǒng)便不能滿足要求。實時調度是能滿足實時任務對截止時間要求任務。實時調度單處理器對進程有以下要求：i為進程第幾次到來腳標，C為進程處理時間，P為進程周期時間。最早截止時間優(yōu)先（EDF）算法是依照任務截止時間來確定任務優(yōu)先級。截止時間愈早，優(yōu)先級愈高。該算法要求在系統(tǒng)中保持一個實時任務就緒隊列，該隊列按各任務截止時間早晚排序。具備最早截止時間任務排在最前面，最先分配四處理機。可用于搶占式調度和非搶占式調度，可用于周期性實時任務和非周期性實時任務。本試驗中用C語言對最早截止優(yōu)先算法用于搶占式周期實時任務情況進行了模擬。最低松弛度優(yōu)先（LLF）算法是依照任務緊急（或松弛）程度，來確定任務優(yōu)先級。任務緊急程度愈高，為該任務所賦予優(yōu)先級就愈高，使之優(yōu)先執(zhí)行。在實現該算法時要求系統(tǒng)中有一個按松弛度排序實時任務就緒隊列，松弛度最低任務排在隊列最前面，被優(yōu)先調度。松弛度計算方法以下：任務松弛度=必須完成時間-其本身運行時間-當前時間。其中其本身運行時間指任務運行結束還需多少時間，假如任務已經運行了一部分，則：其本身運行時間=任務處理時間-任務已經運行時間。本試驗用C語言對最低松弛度優(yōu)先算法進行了模擬?？傮w設計：1.最早截止優(yōu)先算法：本程序模擬兩個任務同時到來時，進程依據最早截止優(yōu)先算法分配情況。定義了以下變量：IntT，模擬時間，T<=100；Floatm,判斷所要處理任務是否滿足單機處理限制條件；IntA，B，任務A,B抵達時間，主要用途是計算任務A,B截止時間。截止時間=抵達時間+周期時間；IntcycA,cycB,任務A，B周期時間，是需要用戶輸入信息；IntserveA,serveB,任務A，B處理時間,是需要用戶輸入信息；Inta,b,任務A，B下標，即標識任務A,B是第幾次到來，第幾次執(zhí)行，第幾次結束；Intnuma,numb,標識任務Ai,Bi累計執(zhí)行時間，當numa=serveA時，任務A完成，當numb=serveB時，任務B完成。依照最早截止優(yōu)先算法規(guī)則，進程調度過程中有以下五種情況：任務A,B同時到來，比較二者截止時間，截止時間早執(zhí)行，截止時間晚阻塞；進程A順利執(zhí)行完成，判斷是否有需要執(zhí)行進程B，假如有，執(zhí)行；進程B順利執(zhí)行完成，判斷是否有需要執(zhí)行進程A，假如有，執(zhí)行；進程A執(zhí)行過程中，有新進程B產生，比較正在執(zhí)行進程A和新產生進程B截止時間，執(zhí)行截止時間早，阻塞截止時間晚；進程B執(zhí)行過程中，有新進程A產生，比較正在執(zhí)行進程B和新產生進程A截止時間，執(zhí)行截止時間早，阻塞截止時間晚。判斷是否滿足單機實時系統(tǒng)限制條件判斷是否滿足單機實時系統(tǒng)限制條件否退出流程圖以下：否退出是是A,B同時產生，比較截止時間，執(zhí)行截止時間早，阻塞截止時間晚A,B同時產生，比較截止時間，執(zhí)行截止時間早，阻塞截止時間晚執(zhí)行A，阻塞B執(zhí)行B，阻塞A執(zhí)行A，阻塞B執(zhí)行B，阻塞AB順利執(zhí)行完，執(zhí)行可執(zhí)行AB執(zhí)行過程中產生新A,判斷是阻塞B還是繼續(xù)執(zhí)行BB順利執(zhí)行完，執(zhí)行可執(zhí)行AB執(zhí)行過程中產生新A,判斷是阻塞B還是繼續(xù)執(zhí)行BA順利執(zhí)行完，執(zhí)行可執(zhí)行BA執(zhí)行過程中產生新B,判斷是阻塞A還是繼續(xù)執(zhí)行A等候新進程到來執(zhí)行A執(zhí)行B，阻塞A執(zhí)行B，阻塞A執(zhí)行A等候新進程到來執(zhí)行A執(zhí)行B，阻塞A執(zhí)行B，阻塞A執(zhí)行A，阻塞B執(zhí)行A，阻塞B等候新進程到來執(zhí)行B等候新進程到來執(zhí)行B直到T>100，結束。所以本程序寫了五個if語句，實現以上五種情況對進程執(zhí)行控制。if(numa==serveA)//進程A完成 {numa=serveA+1;printf("當T=%d時",T);printf("進程A%d結束\n",a);if(numb<serveB)//假如B沒執(zhí)行完，執(zhí)行B {printf("調用進程B%d\n",b);kb=1; }ka=0; }if(numb==serveB)//進程B完成{numb=serveB+1;printf("當T=%d時",T);printf("進程B%d結束\n",b);if(numa<serveA)//假如進程A沒執(zhí)行完，執(zhí)行A {printf("調用進程A%d\n",a);ka=1; }kb=0;}if(T%cycA==0&&T%cycB==0)//兩個進程同時產生{A=B=T;++a;++b;printf("當T=%d時,進程A%d和進程B%d同時產生，此時，",T,a,b);if(A+cycA<=B+cycB)//最終期限比較 {printf("調用進程A%d，阻塞進程B%d\n",a,b);ka=1;kb=0; }else {printf("調用進程B%d，阻塞進程A%d\n",b,a);ka=0;kb=1; }numa=numb=0;}if(T%cycA==0&&T%cycB!=0)//新A任務產生{A=T;printf("當T=%d時",T);printf("進程A%d產生",++a);numa=0;if(numb<serveB)//進程B沒有完成if(B+cycB>A+cycA)//若進程B最早截止時間大于進程A，執(zhí)行A，阻塞B {printf("進程A%d執(zhí)行。\n",a);ka=1;kb=0; }else//若進程B最早截止時間小于等于進程A,執(zhí)行Bprintf("進程B%d繼續(xù)執(zhí)行。\n",b);//else//假如進程B完成,執(zhí)行A {printf("進程A%d執(zhí)行。\n",a);ka=1; }}if(T%cycA!=0&&T%cycB==0)//新任務B產生{B=T;printf("當T=%d時",T);printf("進程B%d產生，",++b);numb=0;if(numa<serveA)if(B+cycB>=A+cycA)printf("進程A%d繼續(xù)執(zhí)行。\n",a);else {printf("進程B%d執(zhí)行。\n",b);kb=1;ka=0; }else {printf("進程B%d執(zhí)行。\n",b);kb=1; }}2.最低松弛度算法：本程序模擬兩個任務同時到來時，進程依據最低松弛度優(yōu)先算法分配情況。定義了以下變量：IntT，模擬時間，T<=100；Floatm,判斷所要處理任務是否滿足單機處理限制條件；IntcycA,cycB,任務A，B周期時間，是需要用戶輸入信息；IntserveA,serveB,任務A，B處理時間,是需要用戶輸入信息；Inta,b,任務A，B下標，即標識任務A,B是第幾次到來，第幾次執(zhí)行，第幾次結束；Intnuma,numb,標識任務Ai,Bi累計執(zhí)行時間，當numa=serveA時，任務A完成，當numb=serveB時，任務B完成。用來計算進程當期松弛度：松弛度=cyc*i-(serve-num)-T.依照最早截止優(yōu)先算法規(guī)則，進程調度過程中有以下五種情況：任務A,B同時到來，比較二者松弛度，松弛度小優(yōu)先執(zhí)行；進程A順利執(zhí)行完成，判斷是否有需要執(zhí)行進程B，假如有，執(zhí)行；進程B順利執(zhí)行完成，判斷是否有需要執(zhí)行進程A，假如有，執(zhí)行；進程A執(zhí)行過程中，B松弛度降為0，若此時A松弛度大于0，優(yōu)先執(zhí)行B，阻塞A;進程B執(zhí)行過程中，A松弛度降為0，若此時B松弛度大于0，優(yōu)先執(zhí)行A，阻塞B。判斷是否滿足單機實時系統(tǒng)限制條件判斷是否滿足單機實時系統(tǒng)限制條件否退出流程圖以下：否退出是是A,B同時產生，比較松弛度，執(zhí)行松弛度小A,B同時產生，比較松弛度，執(zhí)行松弛度小執(zhí)行A，阻塞B執(zhí)行B，阻塞A執(zhí)行A，阻塞B執(zhí)行B，阻塞AB順利執(zhí)行完，執(zhí)行可執(zhí)行AB執(zhí)行過程中A松弛度降為0,判斷是阻塞B還是繼續(xù)執(zhí)行BB順利執(zhí)行完，執(zhí)行可執(zhí)行AB執(zhí)行過程中A松弛度降為0,判斷是阻塞B還是繼續(xù)執(zhí)行BA順利執(zhí)行完，執(zhí)行可執(zhí)行BA執(zhí)行過程中B松弛度降為0,判斷是阻塞A還是繼續(xù)執(zhí)行A等候新進程到來執(zhí)行A執(zhí)行B，阻塞A執(zhí)行B，阻塞A執(zhí)行A等候新進程到來執(zhí)行A執(zhí)行B，阻塞A執(zhí)行B，阻塞A執(zhí)行A，阻塞B執(zhí)行A，阻塞B等候新進程到來執(zhí)行B等候新進程到來執(zhí)行B直到T>100，程序結束。所以本程序寫了五個if語句，實現以上五種情況對進程執(zhí)行控制。if(numa==serveA)//進程A完成 {numa=0;printf("當T=%d時",T);printf("進程A%d結束\n",a); a++;if(numb<serveB&&cycA*a-(serveA-numa)-T>cycB*b-(serveB-numb)-T)//假如B最低松弛度小 {printf("調用進程B%d\n",b);kb=1; } elseif(T<cycA*a)//假如下一個A進程還沒到 {printf("調用進程B%d\n",b);kb=1; }ka=0; }if(numb==serveB)//進程B完成{numb=0;printf("當T=%d時",T);printf("進程B%d結束\n",b); b++;if(numa<serveA&&cycA*a-(serveA-numa)-T<cycB*b-(serveB-numb)-T)//假如A進程最低松弛度小 {printf("調用進程A%d\n",a);ka=1; } elseif(T<cycB*b)//假如下一個B進程還沒到 {printf("調用進程A%d\n",a);ka=1; }kb=0;}if(T%cycA==0&&T%cycB==0)//兩個進程同時產生{numa=numb=0;printf("當T=%d時,進程A%d和進程B%d同時產生，此時，",T,a,b);if(cycA*a-(serveA-numa)-T<=cycB*b-(serveB-numb)-T) {printf("調用進程A%d，阻塞進程B%d\n",a,b);ka=1;kb=0; }else {printf("調用進程B%d，阻塞進程A%d\n",b,a);ka=0;kb=1; }}if(cycA*a-(serveA-numa)-T==0)//A最低松弛度為0,優(yōu)先處理{printf("當T=%d時",T);printf("進程A%d松弛度為0",a);if(numb<serveB)//進程B沒有完成if(cycB*b-(serveB-numb)-T>0)//若進程B最低松弛度比A大，執(zhí)行A {printf("進程A%d執(zhí)行。\n",a);ka=1;kb=0; }else//若進程B最低松弛度小于等于進程A，執(zhí)行Bprintf("進程B%d繼續(xù)執(zhí)行。\n",b);else//假如進程B完成，執(zhí)行A {printf("進程A%d執(zhí)行。\n",a);ka=1; }}if(cycB*b-(serveB-numb)-T==0)//B最低松弛度為0{printf("當T=%d時",T);printf("進程B%d松弛度為0，",b);if(numa<serveA)if(cycA*a-(serveA-numa)-T<=0)printf("進程A%d繼續(xù)執(zhí)行。\n",a);else {printf("進程B%d執(zhí)行。\n",b);kb=1;