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

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

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

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

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

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

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

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

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 修改線程的時(shí)間片大小 在成功為eos添加了時(shí)間片輪轉(zhuǎn)調(diào)度算法后，可以按照下面的步驟修改時(shí)間片的大?。?. 在os lab的“項(xiàng)目管理器”窗口中找到ps/p

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