短作業(yè)優(yōu)先調(diào)度算法

1、青島理工大學(xué)操作系統(tǒng)課程設(shè)計(jì)報告院（系）：計(jì)算機(jī)工程學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生姓名班級：學(xué)號:題目:短作業(yè)優(yōu)先調(diào)度算法的進(jìn)程調(diào)度程序1起迄日期：設(shè)計(jì)地點(diǎn)：指導(dǎo)教師：2011201年2度第1學(xué)期完成日期:2年01月2日課程設(shè)計(jì)目的進(jìn)行操作系統(tǒng)課程設(shè)計(jì)主要是在學(xué)習(xí)操作系統(tǒng)課程的基礎(chǔ)上，在完成操作系統(tǒng)各部分實(shí)驗(yàn)的基礎(chǔ)上，對操作系統(tǒng)的整體進(jìn)行一個模擬，通過實(shí)踐加深對各個部分的管理功能的認(rèn)識，還能進(jìn)一步分析各個部分之間的聯(lián)系，最后達(dá)到對完整系統(tǒng)的理解。同時，可以提高運(yùn)用操作系統(tǒng)知識解決實(shí)際問題的能力；鍛煉實(shí)際的編程能力、開發(fā)軟件的能力；還能提高調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料以及編寫軟件設(shè)計(jì)文檔的能

2、力。二、課程設(shè)計(jì)內(nèi)容與要求設(shè)計(jì)目的：在多道程序和多任務(wù)系統(tǒng)中，系統(tǒng)內(nèi)同時處于就緒狀態(tài)的進(jìn)程可能有若干個，且進(jìn)程之間也存在著同步與互斥的關(guān)系，要求采用指定的調(diào)度策略，使系統(tǒng)中的進(jìn)程有條不紊地工作，通過觀察諸進(jìn)程的運(yùn)行過程，以鞏固和加深處理機(jī)調(diào)度的概念。2、設(shè)計(jì)要求(多道、單處理機(jī))：每一個進(jìn)程有一個PCB,其內(nèi)容可以根據(jù)具體情況設(shè)定?？梢栽诮缑嬖O(shè)定的互斥資源(包括兩種：輸入設(shè)備與輸出設(shè)備)的數(shù)目進(jìn)程數(shù)、進(jìn)入內(nèi)存時間、要求服務(wù)時間可以在界面上進(jìn)行設(shè)定進(jìn)程之間存在一定的同步與互斥關(guān)系,可以通過界面進(jìn)行設(shè)定,其表示方法如下：進(jìn)程的服務(wù)時間由三段組成：I2C10O5(表示進(jìn)程的服務(wù)時間由2個時間片的輸入

3、,10個時間片的計(jì)算,5個時間片的輸出)進(jìn)程間的同步關(guān)系用一個段表示：W2,表示該進(jìn)程先要等待P2進(jìn)程執(zhí)行結(jié)束后才可以運(yùn)行因此，進(jìn)程間的同步與互斥關(guān)系、服務(wù)時間可以統(tǒng)一用四段表示為：I2C10O5W2可以在運(yùn)行中顯示各進(jìn)程的狀態(tài)：就緒、阻塞、執(zhí)行采用可視化界面,可在進(jìn)程調(diào)度過程中隨時暫停調(diào)度,查看當(dāng)前進(jìn)程的狀態(tài)以及相應(yīng)的阻塞隊(duì)列具有一定的數(shù)據(jù)容錯性三、系統(tǒng)分析與設(shè)計(jì)1、系統(tǒng)分析本系統(tǒng)主要是采用短作業(yè)優(yōu)先算法進(jìn)程的進(jìn)程調(diào)度過程。短作業(yè)優(yōu)先調(diào)度算法,是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。他們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度,短作業(yè)優(yōu)先的調(diào)度算法是從后備隊(duì)列中選擇一個或若干個估計(jì)運(yùn)行時間最短的作業(yè),將他

4、們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先調(diào)度算法則是從就緒隊(duì)列中選出一個估計(jì)運(yùn)行時間最短的進(jìn)程,將處理機(jī)分配給他,使它立即執(zhí)行并一直執(zhí)行到完成,或發(fā)生某事件而被阻塞放棄處理機(jī)時再度重新調(diào)度。本程序采用了非搶占式短作業(yè)優(yōu)先調(diào)度。而非搶占式這種方式,一旦把處理機(jī)分配給某進(jìn)程后,便讓該進(jìn)程一直執(zhí)行,直至該進(jìn)程完成或發(fā)生某事件而被阻塞時,才再把處理機(jī)分配給其它進(jìn)程,決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單,系統(tǒng)開銷小,適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求立即執(zhí)行,因而可能造成難以預(yù)料的后果。因此,在要求比較嚴(yán)格的實(shí)時系統(tǒng)中,不宜采用這種調(diào)度方式本系統(tǒng)的主要是在滿足要

5、求多道單處理機(jī)的情況下進(jìn)行短作業(yè)的優(yōu)先調(diào)度。本系統(tǒng)在測試時輸入了五個進(jìn)程，按實(shí)驗(yàn)要求如I2C10O5(表示進(jìn)程的服務(wù)時間由2個時間片的輸入,10個時間片的計(jì)算,5個時間片的輸出,5個時間片的計(jì)算組成)的方式輸入,各進(jìn)程的信息如下：(00111)(12122)(24111)（36211）（48101），其中括號內(nèi)第一個數(shù)字代表進(jìn)程標(biāo)識，第二個數(shù)字代表進(jìn)程的到達(dá)時間，第三的字符串則代表的是服務(wù)時間，由此可得五個進(jìn)程的服務(wù)時間分別為3,6,4,5,2。進(jìn)程進(jìn)入內(nèi)存，則按照優(yōu)先級進(jìn)行執(zhí)行進(jìn)程。主要是實(shí)現(xiàn)了進(jìn)程執(zhí)行過程的界面演示以及在暫停演示時各進(jìn)程此時的狀態(tài)，主要包括三種狀態(tài)就緒、執(zhí)行、阻塞。同時，在

6、暫停執(zhí)行時可以查看當(dāng)前時間的阻塞隊(duì)列。其中進(jìn)程執(zhí)行界面的演示過程中用到了坐標(biāo)軸，軸代表時間，軸代表進(jìn)程的標(biāo)志（默認(rèn)進(jìn)程標(biāo)志為0表示進(jìn)程的個數(shù),在計(jì)數(shù)過程中按進(jìn)程的到達(dá)時間開始計(jì)數(shù)），用灰色表示一個時間片，每個進(jìn)程的執(zhí)行過程即可表示為時間片不斷增加的過程。下面是進(jìn)程信息的輸入界面，界面介紹如下：需要錄入的進(jìn)程數(shù)：輸入需要執(zhí)行的進(jìn)程的個數(shù)。保存文件：輸入數(shù)據(jù)后將自動保存進(jìn)程信息，保存在文件中，因此輸入你要保存的文件的名子，或者在輸入進(jìn)程信息時直接輸入已保存的文件名（不包括擴(kuò)展名）便可直接點(diǎn)擊“錄入完畢”按鈕，進(jìn)行后續(xù)操作。輸入設(shè)備數(shù)目：主要是輸入輸入設(shè)備的數(shù)目。輸出設(shè)備數(shù)目：主要是輸入輸出設(shè)備的數(shù)

7、目。進(jìn)入內(nèi)存的時間：表示進(jìn)程的到達(dá)時間。要求服務(wù)時間：進(jìn)程的服務(wù)時間由四段組成：（表示進(jìn)程的服務(wù)時間由個時間片的輸入，1個0時間片的計(jì)算，5個時間片的輸出），按此格式輸入信息，如若沒有其中一步如沒有計(jì)算這一步表示有0個時間片的計(jì)算，服務(wù)時間可以表示為1以此格式輸入進(jìn)程的服務(wù)時間?！颁浫氲?個數(shù)據(jù)“按鈕：當(dāng)你輸入完畢第一個數(shù)據(jù)時，點(diǎn)擊此按鈕，進(jìn)入第二個進(jìn)程數(shù)據(jù)信息的錄入?！颁浫胪戤呥M(jìn)行演示“按鈕：當(dāng)你將所有進(jìn)程的信息輸入完畢后點(diǎn)擊此按鈕。進(jìn)入演示界面進(jìn)行演示?！巴顺觥鞍粹o：在執(zhí)行此界面的任何時刻均可點(diǎn)擊此按鈕，退出此界面。錄入完畢點(diǎn)擊按鈕“錄入完畢進(jìn)行執(zhí)行”后便會彈出進(jìn)程的執(zhí)行演示界面如下：右上

8、角帶顏色的三個矩形分別表示進(jìn)程的執(zhí)行狀態(tài)，藍(lán)色矩形代表進(jìn)程正在執(zhí)行，綠色矩形代表進(jìn)程已經(jīng)執(zhí)行完成，紅色矩形則代表進(jìn)程受到阻塞?！伴_始演示“按鈕：點(diǎn)擊此按鈕則開始演示進(jìn)程的執(zhí)行過程?！皶和Ｑ菔尽鞍粹o：點(diǎn)擊此按鈕則暫停進(jìn)程的演示過程?！爸匦麻_始“按鈕：點(diǎn)擊此按鈕則重新演示進(jìn)程的執(zhí)行過程?！巴顺鼋缑妗鞍粹o：點(diǎn)擊此按鈕則退出演示界面?！安榭醋枞?duì)列”按鈕：在點(diǎn)擊“暫停演示”按鈕之后，點(diǎn)擊此按鈕，可查看此時的阻塞隊(duì)列。1、系統(tǒng)設(shè)計(jì)本調(diào)度算法在設(shè)計(jì)的時候主要運(yùn)用了四個類庫。類庫主要是包括了要運(yùn)用到得相關(guān)類有三個，類主要是聲明了進(jìn)程的相關(guān)屬性以及方法結(jié)構(gòu)體，和類主要是對進(jìn)程相關(guān)屬性進(jìn)行處理。類庫主要是實(shí)現(xiàn)短

9、作業(yè)優(yōu)先調(diào)度，同樣包括三個類，類主要是實(shí)現(xiàn)對阻塞隊(duì)列的處理，類主要是實(shí)現(xiàn)按進(jìn)程的優(yōu)先級進(jìn)行排序?qū)崿F(xiàn)進(jìn)程的短作業(yè)優(yōu)先調(diào)度，類主要是為了實(shí)現(xiàn)進(jìn)程執(zhí)行演示的方便設(shè)計(jì)的一個類，它聲明了一個數(shù)組，將每個時刻的進(jìn)程作為數(shù)組元素放入數(shù)據(jù)組中。類庫主要是對演示界面的處理，里面包括一個類這個類主要是完成對演示界面所運(yùn)用到得坐標(biāo)軸的實(shí)現(xiàn)。最后一個類庫為短作業(yè)優(yōu)先調(diào)度演示程序，主要包含了和兩個類，這兩個類主要是實(shí)現(xiàn)程序界面的設(shè)計(jì)，以及相關(guān)控件事件的連接以及實(shí)現(xiàn)。在本程序中主要運(yùn)用的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，如數(shù)組主要使用了存放進(jìn)來的進(jìn)程（存放順序按進(jìn)程的到達(dá)時間，為方便描述一下均簡寫為），數(shù)組用來存放阻塞隊(duì)列，是將進(jìn)程按短作

10、業(yè)優(yōu)先級排序后的數(shù)組，數(shù)組則是某一時刻到達(dá)的所有進(jìn)程所形成的數(shù)組，以上數(shù)組均已進(jìn)程作為數(shù)組元素。短作業(yè)優(yōu)先調(diào)度流程圖如下：短作業(yè)優(yōu)先調(diào)度阻塞隊(duì)列的流程圖如下：進(jìn)程調(diào)度演示流程圖：阻塞隊(duì)列進(jìn)程調(diào)度演示四、系統(tǒng)測試與調(diào)試分析1、系統(tǒng)測試本程序主要是采用功能測試，對程序進(jìn)行的相關(guān)的測試與分析。共輸入五個進(jìn)程信息，輸入設(shè)備和輸出設(shè)備各輸入一個然后分別輸入各進(jìn)程的到達(dá)時間和服務(wù)時間，分別如下：（0111）（2122）（4111）（62111）（8101）。再輸入過程中，進(jìn)程的個數(shù)、到達(dá)時間以及輸入設(shè)備和輸出設(shè)備的個數(shù)分別是整數(shù)，否則將提示輸入錯誤。進(jìn)程的服務(wù)時間必須嚴(yán)格按照要求來填寫，否則將提示輸入錯誤

11、。測試說明測試名稱短作業(yè)優(yōu)先調(diào)度程序測試目的驗(yàn)證系統(tǒng)對短作業(yè)優(yōu)先調(diào)度的過程并演示測試技術(shù)功能測試測試方法黑盒測試法測試用例1測試內(nèi)容進(jìn)程信息的進(jìn)入內(nèi)存的輸入功能測試步驟輸入正確的進(jìn)程信息輸入錯誤的進(jìn)程信息測試數(shù)據(jù)進(jìn)入內(nèi)存時間1進(jìn)入內(nèi)存時間為h預(yù)期結(jié)果可以正常運(yùn)行，可以進(jìn)入下一步驟顯示“輸入信息不正確”測試結(jié)果與預(yù)期結(jié)果一樣與預(yù)期結(jié)果一樣測試用例2測試內(nèi)容進(jìn)程信息的服務(wù)時間的輸入功能測試步驟輸入正確的進(jìn)程信息輸入錯誤的進(jìn)程信息測試數(shù)據(jù)進(jìn)程服務(wù)時間為12C1O1進(jìn)程的服務(wù)時間為2預(yù)期結(jié)果可以正常運(yùn)行，可以進(jìn)入下一步驟顯示“輸入信息不正確”測試結(jié)果與預(yù)期結(jié)果一樣與預(yù)期結(jié)果一樣測試用測試內(nèi)容測試進(jìn)程信

12、息的保存功能測試步驟輸入已測試進(jìn)程信息時保存的正確的文件名輸入不存的在的文件名測試數(shù)據(jù)文件123（123.txt內(nèi)保存已經(jīng)運(yùn)行過進(jìn)程的信息不存在的文件mg例3預(yù)期結(jié)果系統(tǒng)正常運(yùn)行，并能夠正確演示系統(tǒng)不能正常運(yùn)行測試結(jié)果與預(yù)期結(jié)果一樣與預(yù)期結(jié)果一樣由此可得五個進(jìn)程的執(zhí)行順序?yàn)椋?,6,4,5,2。2、調(diào)試分析在調(diào)試本程序時和演示過程中，出現(xiàn)了不少的錯誤。其中在編寫短作業(yè)優(yōu)先調(diào)度算法的代碼中，用到了不少的for循環(huán)以及for循環(huán)的嵌套，在這部分出現(xiàn)了變量的混淆，大括號的缺失或多余，經(jīng)過檢查后改正。在編寫短作業(yè)優(yōu)先算法代碼的時候，出現(xiàn)了思路紊亂，算法思路不清晰，不能夠完成短作業(yè)的優(yōu)先，后經(jīng)請教同學(xué)以

13、及通過畫相關(guān)流程圖得到解決。還有由于對c#的運(yùn)用并不熟練以及對c#的可視化界面的制作不太了解，使自己在做程序過程中遇到了很大的阻力，后經(jīng)過翻看相關(guān)書籍以及請教同學(xué)，解決的這個問題。本程序的演示界面做的很簡陋，只是簡單的實(shí)現(xiàn)了非搶占式的短作業(yè)優(yōu)先調(diào)度，但是在本程序的功能中有一項(xiàng)實(shí)現(xiàn)輸入設(shè)備和輸出設(shè)備只是實(shí)現(xiàn)了設(shè)備數(shù)目的輸入功能，但是沒有實(shí)現(xiàn)設(shè)備之間的互斥問題。因此，本程序無論是在界面還是在功能上均有很大的缺點(diǎn)和不足之處，需要不斷的改進(jìn)和完善。五、用戶手冊1、程序的編寫是在win7系統(tǒng)下的VS2010成的。2、由于電腦系統(tǒng)里已經(jīng)安裝了vs2010此不需要再進(jìn)行安裝。3、使用本程序界面的步驟。（1）

14、運(yùn)行本程序會彈出界面如圖5-1：圖5-1（2）在以上彈出的界面上輸入進(jìn)程的數(shù)目以及保存的文件名和輸入設(shè)備和輸出設(shè)備的數(shù)目然后輸入第一個進(jìn)程的進(jìn)入內(nèi)存的時間和要求服務(wù)的時間。如圖5-2：12S2錄幾第2個埶攥錄瓜芫畢迸行涌示退出進(jìn)入內(nèi)存時間:要徇瞬時間：12“保存文件名:需要錄入的進(jìn)程數(shù)：5戛小的信息輸鋪殳瞥數(shù)目輸出設(shè)備埶目1圖5-2（3）點(diǎn)擊“錄入第1個數(shù)據(jù)12S2錄幾第2個埶攥錄瓜芫畢迸行涌示退出進(jìn)入內(nèi)存時間:要徇瞬時間：12“保存文件名:需要錄入的進(jìn)程數(shù)：5戛小的信息輸鋪殳瞥數(shù)目輸出設(shè)備埶目1圖5-2（3）點(diǎn)擊“錄入第1個數(shù)據(jù)”按鈕，彈出以下窗口，開始輸入第二個數(shù)據(jù)的進(jìn)入內(nèi)存的時間和要求服

15、務(wù)的時間。如若輸入的數(shù)據(jù)格式正確，則會彈出圖5-3：圖5-3點(diǎn)擊確定按鈕，進(jìn)入下一個數(shù)據(jù)的輸入圖2保存文件名:12S輸義殺瞥顫目1每牛的信息進(jìn)入內(nèi)存時間:妾求朋務(wù)時間:錄幾第2個埶搏輸出設(shè)備埶目1需要錄入的逬程數(shù)：5錄人兵畢進(jìn)行謹(jǐn)示退出211圖5-4如此依次輸入所有進(jìn)程的相關(guān)信息，直到所有的進(jìn)程信息都輸入完畢。如若輸入數(shù)據(jù)不正確則會彈出窗口圖5-：5圖點(diǎn)擊確定重新輸入正確的進(jìn)程信息。（4）當(dāng)將所有的進(jìn)程信息都輸入完畢后，點(diǎn)擊“錄入完畢進(jìn)行演示”按鈕則會彈出演示界面圖5-：6圖5-65）點(diǎn)擊開始演示按鈕，進(jìn)程開始執(zhí)行。演示狀態(tài)如圖圖5-76）點(diǎn)擊暫停按鈕，演示暫停，進(jìn)程停止執(zhí)行，此時可查看各進(jìn)程

16、的狀態(tài)圖圖5-8（7）在暫停的情況下，點(diǎn)擊“查看阻塞隊(duì)列”按鈕。則會彈出以下窗口，并顯示此刻的阻塞隊(duì)列。如圖5-：9圖5-9（8）如果想重新演示，可以點(diǎn)擊“重新開始”按鈕。當(dāng)演示完畢后，可以點(diǎn)擊“退出界面”按鈕。退出演示界面。六、程序清單重載的方法程序內(nèi)部使用的進(jìn)入內(nèi)存的時間要求服務(wù)的時間在原有的基礎(chǔ)上添加將中的每個進(jìn)程對象都拼接成一個字符串，存放到文件中將中的每個進(jìn)程對象都拼接成一個字符串，存放到文件中在字符串的最后加上換行的標(biāo)志調(diào)用函數(shù)，實(shí)現(xiàn)存儲將/一個進(jìn)程的轉(zhuǎn)化成對應(yīng)的類為/各個變量賦值阻/塞隊(duì)列的處理函數(shù)變量初始化阻塞隊(duì)列數(shù)組每個算法的執(zhí)行順序給定時間內(nèi)到達(dá)的進(jìn)程阻塞隊(duì)列的下標(biāo)完成的進(jìn)

17、程的最后一個的下標(biāo)完成進(jìn)程的總的服務(wù)時間短作業(yè)優(yōu)先調(diào)度算法首阻先獲取得到執(zhí)行的序列符阻合條件的獲取得到給定時間內(nèi)到達(dá)的進(jìn)程，進(jìn)行阻塞隊(duì)列的計(jì)算獲取已經(jīng)執(zhí)行完了的進(jìn)程的標(biāo)志已經(jīng)執(zhí)行完了的總的服務(wù)時間去除不符合條件的將中的非空值，按照在數(shù)組中的順序，存入阻塞數(shù)組中首/先按照進(jìn)入時間排序，然后根據(jù)服務(wù)時間對排序進(jìn)行調(diào)整按照進(jìn)入時間進(jìn)行排序獲/取前面一段的要求服務(wù)總時間找/到要處理的進(jìn)程數(shù)組，即在前一個進(jìn)程處理時間內(nèi)到達(dá)的進(jìn)程注意空值將中的非空數(shù)據(jù)將作業(yè)大的排在后面，實(shí)現(xiàn)短作業(yè)優(yōu)先將中的非空數(shù)據(jù)，覆蓋中的相應(yīng)位置的數(shù)據(jù)七、體會與自我評價短作業(yè)優(yōu)先調(diào)度算法，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。他們可以分

18、別用于作業(yè)調(diào)度和進(jìn)程調(diào)度，短作業(yè)優(yōu)先的調(diào)度算法是從后備隊(duì)列中選擇一個或若干個估計(jì)運(yùn)行時間最短的作業(yè)，將他們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先調(diào)度算法則是從就緒隊(duì)列中選出一個估計(jì)運(yùn)行時間最短的進(jìn)程，將處理機(jī)分配給他，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時再度重新調(diào)度。本程序采用了非搶占式短作業(yè)優(yōu)先調(diào)度。而非搶占式這種方式，一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時，才再把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造成難以預(yù)料的后果。因此，在要求比較嚴(yán)格的實(shí)時系統(tǒng)中，不宜采用這種調(diào)度方式本系統(tǒng)的主要是在滿足要求多道單處理機(jī)的情況下進(jìn)行短作業(yè)的優(yōu)先調(diào)度。在做課程設(shè)計(jì)的過程中，我漸漸發(fā)現(xiàn)了自己的許多不足之處。比如，對短作業(yè)優(yōu)先調(diào)度的原理了解不透徹，對課本知識掌握不熟練，以至在做的過程中需要不斷的去翻閱資料和課本，大大降低了制作課設(shè)的效率。但正是這樣，通過這次短作業(yè)優(yōu)先調(diào)度課設(shè)，使我更加深刻