最低松弛度優(yōu)先

1、青島理工大學(xué)操作系統(tǒng)課程設(shè)計報告院（系）： 計算機工程學(xué)院 專業(yè)： 軟件工程專業(yè) 學(xué)生姓名: 班級：軟件101班學(xué)號: 題目：采用最低松弛度優(yōu)先調(diào)度的實時系統(tǒng)調(diào)度程序 起迄日期: 2013.7.82013.7.14 設(shè)計地點: 計算機學(xué)院機房 指 導(dǎo) 教 師: 20122013年度 第 2 學(xué)期完成日期: 2013 年 7 月 14 日一、課程設(shè)計目的3二、課程設(shè)計內(nèi)容與要求31、設(shè)計內(nèi)容32、設(shè)計要求3三、系統(tǒng)分析與設(shè)計41、系統(tǒng)分析42、系統(tǒng)設(shè)計：42.1、模塊設(shè)計：42.2、數(shù)據(jù)結(jié)構(gòu)說明：42.3、算法流程圖：5四、系統(tǒng)測試與調(diào)試分析91、系統(tǒng)測試92、調(diào)試分析：11五、用戶手冊115.

2、1使用平臺115.2安裝步驟115.3使用步驟11六、程序清單13七、體會與自我評價19八、參考文獻(xiàn)19九、課程設(shè)計評價19一、課程設(shè)計目的在學(xué)習(xí)操作系統(tǒng)課程的基礎(chǔ)上，在完成操作系統(tǒng)各部分實驗的基礎(chǔ)上，對操作系統(tǒng)的整體進(jìn)行一個模擬，通過實踐加深對各個部分的管理功能的認(rèn)識，還能進(jìn)一步分析各個部分之間的聯(lián)系，最后達(dá)到對完整系統(tǒng)的理解。同時，可以提高運用操作系統(tǒng)知識解決實際問題的能力；鍛煉實際的編程能力、創(chuàng)新能力及團(tuán)隊組織、協(xié)作開發(fā)軟件的能力；還能提高調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料以及編寫軟件設(shè)計文檔的能力。二、課程設(shè)計內(nèi)容與要求 1、設(shè)計內(nèi)容在實時系統(tǒng)中，要保證在指定的時間完成指定的任務(wù)，通常會采用

3、搶占式的調(diào)度方式。要求采用指定的調(diào)度算法，使系統(tǒng)中的任務(wù)能夠按時完成，通過觀察中系統(tǒng)中的搶占點，以鞏固和加深對實時系統(tǒng)調(diào)度算法的理解。2、設(shè)計要求1) 每一個周期性實時任務(wù)必須指定周期長度與執(zhí)行時間2) 可以在界面安排周期性實時任務(wù)的個數(shù)與相關(guān)的指標(biāo)值，又及要求仿真的時間長度3) 系統(tǒng)可又對設(shè)定的任務(wù)條件進(jìn)行檢查，如果無法滿足公式 的要求，則彈出相應(yīng)的錯誤提示，并重新進(jìn)入任務(wù)安排界面4) 可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行周期性實時任務(wù)數(shù)、周期長度、執(zhí)行時間的初始化5) 采用可視化界面，數(shù)據(jù)載入后按最低松弛度算法進(jìn)行調(diào)度，可以在運行中動態(tài)顯示各進(jìn)程的狀態(tài)：就緒、執(zhí)行、完成6) 系統(tǒng)上下

4、文切換時，會暫停調(diào)度，顯示就緒隊列中各任務(wù)的松弛度，按任意鍵后自動運行7) 具有一定的數(shù)據(jù)容錯性三、系統(tǒng)分析與設(shè)計1、系統(tǒng)分析（1）該算法根據(jù)實時任務(wù)的松弛度來確定任務(wù)的優(yōu)先級，任務(wù)的松弛度愈低，其優(yōu)先級愈高，以使之優(yōu)先執(zhí)行。（2）松弛度=必須完成的時間-其本身的運行時間-當(dāng)前時間（3）要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列。（4）該算法主要用于可搶占調(diào)度方式中，當(dāng)一任務(wù)的最低松弛度減為0時，它便立即搶占CPU，以保證按截止時間的要求完成任務(wù)。2、系統(tǒng)設(shè)計：2.1、模塊設(shè)計：主程序所需數(shù)據(jù)的初始化運行中動態(tài)顯示各進(jìn)程的狀態(tài)，畫出調(diào)度圖2.2、數(shù)據(jù)結(jié)構(gòu)說明： public class p

5、rocessprivate string pname;/進(jìn)程名private int period;/周期長度private int cputime;/需要的cpu時間private int remaintime;/剩余需執(zhí)行的時間private int arrivetime;/每個周期的到達(dá)時間private int pnum;/所處周期數(shù)private int laxity;/松弛度private int priority;/優(yōu)先級（1）進(jìn)程名用來標(biāo)識一個進(jìn)程（2）周期長度周期性實時任務(wù)必須有周期長度（3）需要的cpu時間周期性實時任務(wù)必須有每個周期需要的執(zhí)行時間（4）剩余需執(zhí)行的時間用來

6、判斷是否發(fā)生搶占，假設(shè)在按松弛度排序的就緒隊列中，任務(wù)a松弛度最小，任務(wù)b次之，若任務(wù)a需要的cpu時間大于任務(wù)b的松弛度，則在任務(wù)a的這次調(diào)度中會發(fā)生搶占，則任務(wù)a該周期的剩余需執(zhí)行的時間大于0，反之，剩余需執(zhí)行的時間等于0時，則這次調(diào)度過程中不會發(fā)生搶占。（5）每個周期的到達(dá)時間用來進(jìn)行排序，系統(tǒng)要求有一個按松弛度排序的實時任務(wù)就緒隊列，若松弛度相同，則按到達(dá)時間排序。（6）所處周期數(shù)對于周期性實時任務(wù)，應(yīng)該有所處的周期數(shù)，其次，計算松弛度時算任務(wù)必須完成的時間可以用所處周期數(shù)和周期長度相乘得到。（7）松弛度最低松弛度優(yōu)先調(diào)度算法肯定要求計算松弛度。（8）優(yōu)先級同樣也是為了排序使用，在松弛

7、度和到達(dá)時間都相同的時候，按固定的優(yōu)先級進(jìn)行排序，優(yōu)先級在添加實時任務(wù)時動態(tài)生成。2.3、算法流程圖：1、數(shù)據(jù)初始化1.1界面直接添加周期性實時任務(wù)數(shù)是否為空輸出：請輸入周期性實時任務(wù)的個數(shù)所添加任務(wù)數(shù)是否小于周期性實時任務(wù)數(shù)輸出：超出個數(shù)限制new一個process實例，添加到實時任務(wù)數(shù)組pro中，然后將該任務(wù)在兩個listview中顯示所添加任務(wù)數(shù)是否等于周期性實時任務(wù)數(shù)判斷系統(tǒng)是否可調(diào)度清空實時任務(wù)名，周期長度和執(zhí)行時間三個輸入框是否否是是1.2 從文件中讀取數(shù)據(jù)找到需要的文件，點擊打開讀取文件內(nèi)容，new出process實例，添加到數(shù)組，同時在兩個listview中顯示判斷系統(tǒng)是否可調(diào)

8、度2、動態(tài)顯示各進(jìn)程的狀態(tài)和畫出調(diào)度圖把listview2的備注一欄清空初始化一些變量，實例化sortpro，然后對sortpro進(jìn)行排序找到已到達(dá)的松弛度最小的任務(wù)，如果所以任務(wù)都沒到達(dá)，flag=falseflag是否為true找到松弛度最小和次小的任務(wù)，計算duration，并對其加以限制，修改本次被調(diào)度進(jìn)程的remaintime畫出本次調(diào)度的圖形，修改curtime的值根據(jù)remaintime的值修改本次被調(diào)度進(jìn)程在listview2中的顯示信息，更改本次被調(diào)度進(jìn)程的相關(guān)信息重新計算所有任務(wù)的松弛度，更新未被調(diào)度的進(jìn)程在listview2中顯示的信息當(dāng)前時間大于或等于要求仿真的時間長度

9、停止計時，顯示調(diào)度完成四、系統(tǒng)測試與調(diào)試分析1、系統(tǒng)測試l 測試方法：黑盒測試l 測試技術(shù)：功能測試它是從使用者的角度來編寫的，它關(guān)注系統(tǒng)提供的功能特征及其不同的處理條件；測試功能的不同處理流程（包括正常處理的和異常處理）；一個功能測試用例僅用于測試一個功能，一個功能可能需要多個功能測試用例來覆蓋。l 測試數(shù)據(jù)： （1） 課本例子（存在搶占的情況）輸入：周期性實時任務(wù)的個數(shù)：2第一個實時任務(wù)(實時任務(wù)名，周期長度，執(zhí)行時間)：A,20,10第二個實時任務(wù)(實時任務(wù)名，周期長度，執(zhí)行時間)：B,50,25輸出結(jié)果：（2） 不存在搶占輸入：周期性實時任務(wù)的個數(shù)：3第一個實時任務(wù)(實時任務(wù)名，周期長

10、度，執(zhí)行時間)：A,20,10第二個實時任務(wù)(實時任務(wù)名，周期長度，執(zhí)行時間)：B,50,10第三個實時任務(wù)(實時任務(wù)名，周期長度，執(zhí)行時間)：C,50,15輸出結(jié)果：（3） 系統(tǒng)不可調(diào)度輸入：周期性實時任務(wù)的個數(shù)：2第一個實時任務(wù)(實時任務(wù)名，周期長度，執(zhí)行時間)：A,20,10第二個實時任務(wù)(實時任務(wù)名，周期長度，執(zhí)行時間)：B,30,20 輸出結(jié)果：提示：系統(tǒng)不可調(diào)度l 測試報告：（1） 課本例子（存在搶占的情況）測試結(jié)果：（2） 不存在搶占的例子測試結(jié)果：（3） 系統(tǒng)不可調(diào)度測試結(jié)果：測試說明測試名稱采用最低松弛度優(yōu)先調(diào)度的實時系統(tǒng)調(diào)度程序測試目的驗證采用最低松弛度優(yōu)先調(diào)度的實時系統(tǒng)調(diào)

11、度程序調(diào)度的正確性測試技術(shù)功能測試測試方法黑盒測試法測試用例測試內(nèi)容系統(tǒng)所實現(xiàn)的最低松弛度優(yōu)先算法的正確性測試步驟輸入周期性實時任務(wù)的個數(shù)，每個任務(wù)的實時任務(wù)名，周期長度和執(zhí)行時間（存在搶占）輸入周期性實時任務(wù)的個數(shù)，每個任務(wù)的實時任務(wù)名，周期長度和執(zhí)行時間（不存在搶占）輸入周期性實時任務(wù)的個數(shù)，每個任務(wù)的實時任務(wù)名，周期長度和執(zhí)行時間（系統(tǒng)不可調(diào)度）測試數(shù)據(jù)2a,20,10;b,50,253a,20,10;b,50,10;c,50,152a,20,10;b,30,20預(yù)期結(jié)果得出正確的調(diào)度圖得出正確的調(diào)度圖給出相應(yīng)的提示信息測試結(jié)果與預(yù)期相符與預(yù)期相符與預(yù)期相符2、調(diào)試分析：開始調(diào)試算法，在

12、排序的時候一直有一個空引用異常，提示未將對象引用設(shè)置到對象的實例。是因為沒有實例化按松弛度排序的那個數(shù)組，根本上還是自己編程比較少的原因，平時學(xué)習(xí)語言的時候應(yīng)該注意要多練習(xí)。還有就是排序交換數(shù)據(jù)的時候出了點兒問題，還是因為編程不熟練的問題。還有一個費了好長時間的問題就是暫停調(diào)度時，按任意鍵繼續(xù)的問題，解決這個問題的時候在網(wǎng)上找了好長時間，網(wǎng)上沒有現(xiàn)成的答案，有的也是控制臺下按任意鍵繼續(xù)的問題。自己添加了一個窗體的鍵盤事件，可是一直沒有成功觸發(fā)這個事件，后來知道是焦點的問題，先得讓窗體獲得焦點，按任意鍵才能觸發(fā)那個事件。最后調(diào)試的比較多的就是最后動態(tài)顯示的部分，為了顯示的更合理。開始以為還行，后

13、來換了個例子還發(fā)現(xiàn)了比較多的問題，看來，自己編程序還是要更仔細(xì)。五、用戶手冊5.1使用平臺本系統(tǒng)使用操作系統(tǒng)為win7，需要安裝visual stutio 20105.2安裝步驟本系統(tǒng)無需安裝，只需把exe文件拷貝到電腦上5.3使用步驟圖1：開始運行界面圖2：輸入數(shù)據(jù)圖3：數(shù)據(jù)可從文件中讀取圖4：點擊開始，開始動態(tài)顯示圖5：動態(tài)運行中各進(jìn)程狀態(tài)圖6：調(diào)度結(jié)束六、程序清單最低松弛度優(yōu)先算法：private void timer1_Tick(object sender, EventArgs e) /清空備注中的信息 for (int i = 0; i < pro.Length; i+) li

14、stView2.Itemsi.SubItems4.Text = "" bool flag = true; int duration=0;/本次調(diào)度執(zhí)行的時間 int first=0; int second=0; int ordfirst=0; sortpro=new processpro.Length; for (int i = 0; i < pro.Length; i+) sortproi = new process(proi.Pname,proi.Period,proi.Cputime,proi.Remaintime,proi.Pnum,proi.Arriveti

15、me,proi.Laxity,proi.Priority); process proc = new process(); /對sortpro中的任務(wù)按松弛度從小到大進(jìn)行排序，松弛度相同時按到達(dá)次序先后排序，到達(dá)時間相同時按固定優(yōu)先級排序 /固定優(yōu)先級：在添加任務(wù)時，先添加的任務(wù)優(yōu)先級高 for (int i = 0; i < sortpro.Length - 1; i+) for (int j = i + 1; j < sortpro.Length; j+) if (sortproj.Laxity < sortproi.Laxity) /交換所有屬性信息 proc.Pname

16、 = sortproi.Pname; sortproi.Pname = sortproj.Pname; sortproj.Pname = proc.Pname; else if (sortproj.Laxity = sortproi.Laxity) if (sortproj.Arrivetime < sortproi.Arrivetime) /交換所有屬性信息 proc.Pname = sortproi.Pname; sortproi.Pname = sortproj.Pname; sortproj.Pname = proc.Pname; else if (sortproj.Arrive

17、time = sortproi.Arrivetime) /交換所有屬性信息 if (sortproj.Priority < sortproi.Priority) proc.Pname = sortproi.Pname; sortproi.Pname = sortproj.Pname; sortproj.Pname = proc.Pname; /外層for循環(huán) /找到sortpro中已到達(dá)的松弛度最低的進(jìn)程 for (int i = 0; i < sortpro.Length;i+ ) if (curtime < (sortproi.Pnum - 1) * sortproi.P

18、eriod) if (i != sortpro.Length - 1) continue; else /curtime到最近的周期 curtime = sortpro0.Arrivetime; for (int j = 1; j < sortpro.Length; j+) if (sortproi.Arrivetime < curtime) curtime = sortproi.Arrivetime; /重新計算松弛度 for(int j=0;j<pro.Length;j+) proj.Laxity = proj.Pnum * proj.Period - curtime -

19、proj.Remaintime; for (int j = 0; j < pro.Length; j+) /在listview2中動態(tài)顯示各任務(wù)信息 if (proj.Pnum - 1) * proj.Period < curtime) | (proj.Pnum - 1) * proj.Period = curtime) listView2.Itemsj.SubItems1.Text = proj.Pnum.ToString(); listView2.Itemsj.SubItems2.Text = proj.Laxity.ToString(); listView2.Itemsj.S

20、ubItems3.Text = "就緒" else listView2.Itemsj.SubItems1.Text = "" listView2.Itemsj.SubItems2.Text = "" listView2.Itemsj.SubItems3.Text = "" listView2.Itemsj.SubItems4.Text = "尚未到達(dá)" flag = false; else ordfirst = i; break; /尚未進(jìn)入該周期的for循環(huán) /如果sortpro中所有任務(wù)都沒

21、到達(dá)，則不執(zhí)行if(flag)中的代碼 if (flag) /找到松弛度最低和次低的任務(wù) for (int i = 0; i < pro.Length; i+) if (ordfirst < pro.Length - 1) if (proi.Pname.Equals(sortproordfirst.Pname) first = i; if (proi.Pname.Equals(sortproordfirst + 1.Pname) second = i; else first = i; second = 0; /根據(jù)松弛度次低的任務(wù)的松弛度和松弛度最低的任務(wù)的執(zhí)行時間確定durati

22、on if (profirst.Remaintime <= prosecond.Laxity) duration = profirst.Remaintime; else duration = prosecond.Laxity; /對duration的額外限制，closetime為要求仿真的時間長度 if (curtime + duration) > closetime) duration = closetime - curtime; profirst.Remaintime -= duration; /畫出本次調(diào)度的圖形 for (int y = 0; y < duration

23、; y+) Pen pen; pen=new Pen(Color.FromArgb(colorprofirst.Priority,0,colorprofirst.Priority,1,colorprofirst.Priority,2); grap.DrawLine(pen, (curtime + y) * 2, 0, (curtime + y) * 2, 30); grap.DrawLine(pen, (curtime + y) * 2 + 1, 0, (curtime + y) * 2 + 1, 30); /修改curtime curtime += duration; /動態(tài)修改listvi

24、ew2中的信息 if (profirst.Remaintime = 0) listView2.Itemsfirst.SubItems1.Text = profirst.Pnum.ToString(); listView2.Itemsfirst.SubItems2.Text = "" listView2.Itemsfirst.SubItems3.Text = "完成" listView2.Itemsfirst.SubItems4.Text = "第" + profirst.Pnum + "個周期運行了" + dura

25、tion + "毫秒" /更改本次被調(diào)度任務(wù)的相關(guān)屬性 profirst.Pnum+; profirst.Remaintime = profirst.Cputime; profirst.Arrivetime = (profirst.Pnum - 1) * profirst.Period; else listView2.Itemsfirst.SubItems4.Text = "第" + profirst.Pnum + "個周期運行了" + duration + "毫秒" listView2.Itemsfirst.Su

26、bItems3.Text = "" listView2.Itemsfirst.SubItems2.Text = "" timer1.Enabled = false; display.Text = "上下文切換，按任意鍵繼續(xù)" listView2.Itemssecond.SubItems4.Text = prosecond.Pname + "搶占cpu" /窗體獲得焦點 this.KeyPreview = true; /暫停，等待按任意鍵 this.keybool = true; for (int j = 0; j

27、< pro.Length; j+) /修改所有任務(wù)的松弛度 proj.Laxity = proj.Pnum * proj.Period - curtime - proj.Remaintime; for (int i = 0; i < pro.Length; i+) /顯示本次未被調(diào)度的任務(wù)的狀態(tài) if (i != first) if (proi.Pnum - 1) * proi.Period < curtime) | (proi.Pnum - 1) * proi.Period = curtime) listView2.Itemsi.SubItems1.Text = proi.

28、Pnum.ToString(); listView2.Itemsi.SubItems2.Text = proi.Laxity.ToString(); listView2.Itemsi.SubItems3.Text = "就緒" else listView2.Itemsi.SubItems1.Text = "" listView2.Itemsi.SubItems2.Text = "" listView2.Itemsi.SubItems3.Text = "" listView2.Itemsi.SubItems4.Text = "尚未到達(dá)" /if(flag) /調(diào)度完成條件 if (curtime > this.closetime|curtime=this.closetime) this.timer1.Stop(); if (MessageB