時間片輪轉(zhuǎn)調(diào)度.doc

1、時間片輪轉(zhuǎn)調(diào)度實驗性質(zhì)：設(shè)計建議學時：2學時一、實驗目的l 為eos調(diào)度器添加時間片輪轉(zhuǎn)調(diào)度算法，了解常用調(diào)度算法。二、預備知識閱讀eos實驗指南5.4節(jié)。重點理解eos當前使用的基于優(yōu)先級的搶先式調(diào)度，調(diào)度程序執(zhí)行的過程和時機，以及時間片輪轉(zhuǎn)調(diào)度實現(xiàn)的方法。三、實驗內(nèi)容3.1 準備實驗按照下面的步驟準備實驗：1. 啟動os lab。2. 新建一個eos kernel項目。3. 在“項目管理器”窗口中雙擊floppy.img文件，使用floppyimageeditor工具打開此軟盤鏡像。4. 將本實驗文件夾中的multi.exe文件添加到軟盤鏡像的根目錄中。5. 點擊floppyimageed

2、itor工具欄上的保存按鈕，關(guān)閉該工具。3.2 閱讀multi.exe的源代碼在本實驗文件夾中找到multi.exe的源代碼文件multi.c，使用os lab打開此文件，仔細閱讀此文件中的源代碼。在閱讀的過程中需要注意下面的問題：l 在main函數(shù)中使用threadfunction線程函數(shù)創(chuàng)建了23個新線程。這樣在該應用程序創(chuàng)建的進程中，算上主線程后就會包括24個線程。l 主線程會在控制臺的第0行循環(huán)輸出計數(shù)，其它的線程也會在控制臺的對應行循環(huán)輸出計數(shù)，這樣就可以很方便的觀察各個線程執(zhí)行的情況。l 各個線程在向控制臺輸出時使用“關(guān)中斷”和“開中斷”進行了互斥。原則上在應用程序中是不能使用“關(guān)

3、中斷”和“開中斷”指令的，這里是為了保證各個線程不進行讓權(quán)等待，保證實驗的效果。l 為了保證實驗效果，所有的線程（包括主線程）都是死循環(huán)。也就是說所有的線程都不會結(jié)束執(zhí)行。3.3 執(zhí)行multi.exe按照下面的步驟執(zhí)行multi.exe，查看其運行效果：1. 按f7生成在3.1中創(chuàng)建的eos kernel項目。2. 按f5啟動調(diào)試。3. 在eos控制臺中輸入“a:multi.exe”后按回車。在multi.exe開始執(zhí)行后，觀察其執(zhí)行結(jié)果（如圖1）會發(fā)現(xiàn)multi.exe的執(zhí)行沒有體現(xiàn)其源代碼的設(shè)計意圖。通過之前對multi.c的分析，multi進程中的24個線程應該在控制臺對應的行中不停地

4、輸出字符。而這里只有主線程在運行，其它線程都沒有運行。圖1：不進行時間片輪轉(zhuǎn)調(diào)度時multi.exe的執(zhí)行效果造成上述現(xiàn)象的原因：進程內(nèi)的所有線程在被創(chuàng)建時都采用了默認優(yōu)先級8，這就造成這24個線程的優(yōu)先級都是相同的。而此時eos只實現(xiàn)了基于優(yōu)先級的搶先式調(diào)度算法，還沒有實現(xiàn)時間片輪轉(zhuǎn)調(diào)度算法，所以至始至終都只有主線程在運行，其它具有相同優(yōu)先級的線程都沒有運行。3.4 為eos添加時間片輪轉(zhuǎn)調(diào)度算法3.4.1 要求修改eos內(nèi)核項目ps/sched.c文件中的psproundrobin函數(shù)(第335行)，在其中實現(xiàn)時間片輪轉(zhuǎn)調(diào)度算法。3.4.2 測試方法1. 代碼修改完畢后，按f7生成eos內(nèi)

5、核項目。2. 按f5啟動調(diào)試。3. 在eos控制臺中輸入“a:multi.exe”后按回車。應能看到24個線程并發(fā)執(zhí)行的效果，如圖2。圖2：進行時間片輪轉(zhuǎn)調(diào)度時multi.exe的執(zhí)行效果圖3：psproundrobin函數(shù)的流程圖3.4.3 提示l 在eos操作系統(tǒng)運行過程中，tcb指針變量pspcurrentthread始終指向當前線程。所以，當發(fā)生中斷時，pspcurrentthread就指向被中斷的線程。pspcurrentthread的定義參見ps/sched.c的第44行。tcb結(jié)構(gòu)體定義參見ps/psp.h的第58行。l psproundrobin函數(shù)在被調(diào)用時，被中斷線程（ps

6、pcurrentthread指向的線程）的狀態(tài)可能已經(jīng)改變（例如從運行狀態(tài)轉(zhuǎn)變?yōu)榈却隣顟B(tài)）。所以要先判斷一下被中斷線程是否仍處于運行狀態(tài)，只有當被中斷線程處于運行狀態(tài)時才能進行時間片輪轉(zhuǎn)調(diào)度。在psproundrobin中的第一行代碼可以如下：if (null != pspcurrentthread & running = pspcurrentthread-state) / 在此實現(xiàn)時間片輪轉(zhuǎn)調(diào)度算法線程狀態(tài)的定義可以參見ps/psp.h的第93行。l psproundrobin函數(shù)具體的流程可以參考圖3。l 被中斷線程所擁有的時間片保存在pspcurrentthread-remaindert

7、icks中。l 重新為被中斷線程分配時間片時，可以使用頭文件ps/psp.h中第104行的宏定義ticks_of_time_slice，目前為6。注意，此宏定義表示每次給線程分配的時鐘滴答（tick）數(shù)量，多個時鐘滴答組成了線程的時間片。時鐘滴答的大小是由定時器中斷的頻率確定的，目前每秒觸發(fā)100次定時器中斷，所以每個時鐘滴答的大小是10ms。l 在檢查是否存在和被中斷線程優(yōu)先級相同的就緒線程時，只需要掃描32位就緒位圖即可。可以使用下面的代碼作為判斷語句中的布爾表達式：bit_test(pspreadybitmap, pspcurrentthread-priority)bit_test是一個

8、宏定義函數(shù)，其定義參見inc/eosdef.h的第219行。如果存在和被中斷線程優(yōu)先級相同的就緒線程，此函數(shù)返回非0（ture），否則返回0（false）。變量pspreadybitmap是32為就緒位圖，其定義參見ps/sched.c的第28行。l 可以使用下面的代碼將被中斷線程轉(zhuǎn)入就緒狀態(tài)：pspreadythread(pspcurrentthread);函數(shù)pspreadythread的定義參見ps/sched.c的第106行。3.5 修改線程的時間片大小 在成功為eos添加了時間片輪轉(zhuǎn)調(diào)度算法后，可以按照下面的步驟修改時間片的大?。?. 在os lab的“項目管理器”窗口中找到ps/p

9、sp.h文件，并雙擊打開此文件。2. 將ps/psp.h第104行定義的ticks_of_time_slice的值修改為1。4. 按f7生成eos內(nèi)核項目。5. 按f5啟動調(diào)試。3. 在eos控制臺中輸入“a:multi.exe”后按回車。觀察multi.exe執(zhí)行的效果。你還可以按照上面的步驟為ticks_of_time_slice取一些極端值，例如20和100等，分別觀察multi.exe運行的效果。通過分析造成運行效果不同的原因，理解時間片的大小對時間片輪轉(zhuǎn)調(diào)度造成的影響。四、思考與練習l 開始eos只實現(xiàn)了基于優(yōu)先級的搶先式調(diào)度，這導致同優(yōu)先級的線程只能有一個被執(zhí)行。當實現(xiàn)了時間片輪轉(zhuǎn)調(diào)度算法后，同優(yōu)先級的線程就能夠輪流執(zhí)行從而獲得均等的執(zhí)行機會。但是，如果有高優(yōu)先級的線程一直占用cpu，低優(yōu)先級的線程就永遠不會被執(zhí)行，請設(shè)計一種調(diào)度算法來解決此問題，讓低優(yōu)先級的線程也能獲得被執(zhí)行的機會。l eos內(nèi)核時間片大小取60ms（和windows操作系統(tǒng)完全相同），在線程比較多時，就可以觀察出線程輪流執(zhí)行的情況（因為此時一次輪