線程調度實習報告

1、 線程調度實習報告姓名 李煒 學號 1100012810日期 2014年3月6日目錄 TOC o 1-3 h z u HYPERLINK l _Toc286402948內(nèi)容一：總體概述 PAGEREF _Toc286402948 h 3HYPERLINK l _Toc286402949內(nèi)容二：任務完成情況 PAGEREF _Toc286402949 h 3HYPERLINK l _Toc286402950任務完成列表（Y/N） PAGEREF _Toc286402950 h 3HYPERLINK l _Toc286402951具體Exercise的完成情況 PAGEREF _Toc286402

2、951 h 3HYPERLINK l _Toc286402952內(nèi)容三：遇到的困難以及解決方法 PAGEREF _Toc286402952 h 4HYPERLINK l _Toc286402953內(nèi)容四：收獲及感想 PAGEREF _Toc286402953 h 5HYPERLINK l _Toc286402954內(nèi)容五：對課程的意見和建議 PAGEREF _Toc286402954 h 5HYPERLINK l _Toc286402955內(nèi)容六：參考文獻 PAGEREF _Toc286402955 h 5內(nèi)容一：總體概述這次的實習任務主要是通過對Nachos線程的調度機制來加深對線程調度的理

3、解，因為Nachos本身是沒有很復雜的調度機制的，所以這次實習中需要首先向Nachos添加帶有優(yōu)先級的線程調度算法，之后添加使用時間片調度，來使得線程的調度相對公平。內(nèi)容二：任務完成情況任務完成列表（Y/N）Exercise1Exercise2Exercise3challenge第一部分YYYY具體Exercise的完成情況第一部分Exercise1首先來看windows的線程調度，windows的調度單位就是線程，它采用的時基于動態(tài)優(yōu)先級的、搶占式調度，結合時間配額調整，總是運行最高優(yōu)先級線程。就緒線程會按優(yōu)先級進入相應隊列，系統(tǒng)總是選擇優(yōu)先級最高的就緒線程讓其運行，同一優(yōu)先級的各線程按時間

4、片輪轉進行調度，多處理機系統(tǒng)中允許多個線程并行運行。從這一點來看，有些像多級反饋隊列調度的方法。線程調度的觸發(fā)事件有四種： 一個線程進入就緒狀態(tài)，如一個剛創(chuàng)建的新線程或一個剛剛結束等待狀態(tài)的線程 一個線程由于時間配額用完、從運行狀態(tài)轉入結束狀態(tài)或等待狀態(tài) 一個線程由于調用系統(tǒng)服務而改變優(yōu)先級或被Windows 系統(tǒng)本身改變其優(yōu)先級 一個正在運行的線程改變了它的親合處理機集合Windows使用32個線程優(yōu)先級，分成三類，實時優(yōu)先級，可變優(yōu)先級，系統(tǒng)線程（IDLE）。一個線程用完了自己的時間配額時，如果沒有其它相同優(yōu)先級線程，Windows將重新給該線程分配一個新的時間配額，并繼續(xù)運行。當線程被搶

5、占時，它被放回相應優(yōu)先級的就緒隊列的隊首 處于實時優(yōu)先級的線程在被搶占時，時間配額被重置為一個完整的時間配額 處于動態(tài)優(yōu)先級的線程在被搶占時，時間配額不變，重新得到處理機后將運行直到剩余的時間配額用完如果剛用完時間配額的線程優(yōu)先級降低了，Windows 將尋找一個優(yōu)先級高于剛用完時間配額線程的新設置值的就緒線程如果剛用完時間配額的線程的優(yōu)先級沒有降低，并且有其他優(yōu)先級相同的就緒線程，Windows 將選擇相同優(yōu)先級的就緒隊列中的下一個線程進入運行狀態(tài)，剛用完時間配額的線程被排到就緒隊列的隊尾(即分配一個新的時間配額并把線程狀態(tài)從運行狀態(tài)改為就緒狀態(tài))如果沒有優(yōu)先級相同的就緒線程可運行，剛用完時

6、間配額的線程將得到一個新的時間配額并繼續(xù)運行下面來看linux的線程調度策略，linux將進程分為下面兩類實時進程 對調度延遲的要求最高，要求立即響應并執(zhí)行 調度策略：FIFO、Round Robin普通進程交互式進程：間或處于睡眠態(tài)，對響應速度要求比較高批處理進程：在后臺執(zhí)行，能夠忍受響應延遲 普通進程調度策略使用CFS，CFS是現(xiàn)在被內(nèi)核采納的調度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區(qū)分交互式進程CFS算法中，每個進程都有一個“虛擬運行時間”表示該進程運行了“多長時間”，而調度器會選擇虛擬運行時間最小的進程來運行虛擬運行時間的計算與進程實際運行時

7、間成正比，而與進程優(yōu)先級成反比CFS以虛擬運行時間作為鍵值構造一棵紅黑樹，從而實現(xiàn)了快速更新和刪除完全公平調度Completely Fair Scheduler，核心思想：根據(jù)進程的優(yōu)先級按比例分配運行時間分配給進程的運行時間 = 調度周期 * 進程權重 / 所有進程權重之和 (公式1)調度周期：將所有處于TASK_RUNNING態(tài)進程都調度一遍的時間CFS對時鐘做抽象，引入了虛擬運行時間vruntime的概念，每個進程有自己的vruntimevruntime = 實際運行時間 * NICE_0_LOAD / 進程權重(公式2)由公式1和2得：vruntime = (調度周期 * 進程權重 /

8、 所有進程總權重) * NICE_0_LOAD / 進程權重= 調度周期 * NICE_0_LOAD / 所有進程總權重從vruntime的角度，分配給所有進程的時間是一樣的CFS算法，每次選擇vruntime最小的進程運行，所有進程的vruntime增長速度宏觀上看是同時推進的CFS 維護了一個以vruntime為順序的紅黑樹，可以快速高效地插入或刪除任務調度器每次選擇最左側結點的進程運行，運行結點從樹中刪除；進程切換時，切換下來的就緒態(tài)進程再重新插入樹中，因為換下來的進程一般vruntime比較大所以會靠近樹的右側；總體來說樹的內(nèi)容從右側遷移到左側以保持平衡。Exercise2Schedu

9、ler.h scheduler.ccScheduler是Nachos的調度器，最重要的功能是選擇下一個能夠運行的線程進行運行，在這個調度器中使用了在第一周中就已經(jīng)看到過的List這個工具類，最重要的有三個函數(shù)，ReadyToRun, FindNextToRun, Run。下面分別來介紹，ReadyToRun函數(shù)負責將一個線程的狀態(tài)設置成READY，并且把它加入到readyList中，也就是說，調用ReadyToRun函數(shù)后，并不代表這個線程就要被運行了，而只是“候補”運行，只有當scheduler在調度時選擇這個線程后，這個線程才會真正運行。FindNextToRun函數(shù)就是很簡單地將鏈表頭部

10、的元素（第一個線程）取出。Run是真正的調度算法，如果是用戶線程，Run函數(shù)首先需要保存當前線程運行的環(huán)境（寄存器），之后檢查是否有棧溢出，然后把參數(shù)中的nextThread設置為要運行的線程，通過換棧來真正使得nextThread運行，之后檢查是不是有運行完的線程，如果有的話就回收資源;最后查看是否需要恢復地址空間。SWITCH.sSWITCH.s中的匯編代碼做的事情主要就是保存原運行線程的狀態(tài)，恢復新運行線程的狀態(tài)，在新運行線程的棧空間上運行新線程List.h List.cc由于第一周的實習中已經(jīng)用過了工具類List，這里就對本次涉及到的部分做一些解釋，在List這個類中，這次需要用到So

11、rtedInsert來代替直接Append這樣的直接插入，而需要有序插入（按照優(yōu)先級），因為Remove函數(shù)本身除去的是鏈表頭的元素，所以可以直接采用。也就是說，雖然在scheduler的實現(xiàn)中沒有使用到list的這個有序鏈表的有序性，但是它確實實現(xiàn)了這個功能，也就為我們在實現(xiàn)優(yōu)先級調度的時候提供了方便。Timer.h timer.cc進到cc文件中首先看到的就是一個很奇怪的TimerHandler函數(shù)，從代碼可以看到，這個函數(shù)其實就是TimerExpired函數(shù)的另一個函數(shù)指針，從注釋中可以看到，這個函數(shù)之所以存在是因為c+不允許指針指向一個類的內(nèi)部函數(shù)，所以這里就對TimerExpired

12、這個函數(shù)包裝了一下，在我最初對時間片的實現(xiàn)中，就試圖調用這個函數(shù)，但是運行出錯，只得放棄了。接下來看構造函數(shù)，比較重要的是時這個timerhandler和randomize參數(shù)，首先說比較簡單的randomize，這個參數(shù)如果被設置為true的話，則下一次終端發(fā)生的時間就會時被隨即算出來的。我們追蹤一下timerhandler的走向，可以看到它下面被interrupt的schedule調用，在這里面又被PendingInterrupt調用，最后到達PendingInterrupt中，從注釋可以看到這個參數(shù)的作用是這個函數(shù)的作用是當中斷發(fā)生時，對這個中斷的處理函數(shù)，特別的，從構造函數(shù)的注釋中看到

13、timerHandler is the interrupt handler for the timer device./It is called with interrupts disabled every time the/the timer expires.所以要想實現(xiàn)時間片調度，那么就必然會用到時鐘中斷，而對于這個中斷的處理就取決于這個handler的實現(xiàn)了，也就是說這個函數(shù)對于時間片調度來說非常重要。TimerExpired的作用也比較簡單，但是卻非常重要，它首先安排下次中斷將要發(fā)生的時間，之后調用中斷處理函數(shù)來處理這次的中斷。TimeOfNextInterrupt的作用就是返回下次中

14、斷發(fā)生距離現(xiàn)在的時間，如果設置了隨即選項，那么就隨即產(chǎn)生一個數(shù)，否則返回100個tick（stats.h中定義的）。Interrput.cc interrupt.h這兩個文件對于時間片調度也是至關重要的，其中的函數(shù)很多，我們只看和本次實習有關的。changeLevel的作用是將中斷的狀態(tài)設置成傳入的參數(shù)的狀態(tài)，setLevel也差不多，但是有一個很大的不同是setLevel中在滿足條件的情況下會調用oneTick函數(shù)，這個函數(shù)也十分重要。它的重要之處在于它會使時鐘前進，也就是說這個函數(shù)控制了時間片的前進。在一次oneTick中，如果是system mode的話就會前進10個tick，并且如果y

15、ieldOnReturn時true的話，那么就會調用yield函數(shù)，也就是說我們在一個時間片用完的時候必須保證yieldOnReturn是true，否則就無法使得線程發(fā)生切換。前面以及說過schedule函數(shù)的作用，接下來是checkifdue函數(shù)，這個函數(shù)從名字就可以看出，是檢查下次中斷發(fā)生的時間是不是到了，如果時間到了的話，就取出中斷鏈表中的第一個元素并且處理它。Exercise3首先，需要給Thread這個類添加上priority（優(yōu)先級）這個屬性，配套的自然就需要修改構造函數(shù)，以及給priority這個屬性配備set和get方法。在沒有優(yōu)先級作為參數(shù)的構造函數(shù)中，需要給這個線程一個默認

16、的優(yōu)先級，暫且設置為0（最高優(yōu)先級，因為list中的排序是從小到大）。之后就需要修改有關調度器Scheduler中的函數(shù)了。首先從插入線程的位置入手，需要從原來的單純使用Append方法改用SortedInsert并且把線程的優(yōu)先級作為第二個參數(shù)傳給這個函數(shù)。而對于FindNextToRun和Run來說，不需要修改，因為List中的Remove函數(shù)本身就是從有序的鏈表中的頭部取元素，也就是優(yōu)先級最高的線程。下面就需要查看Run函數(shù)的調用時機，對于這一點，我用了一個小trick，我修改了scheduler中的Run函數(shù)的signature（增加一個參數(shù)int p），然后觀察make的時候哪些地方

17、會報錯，哪里就調用了Run這個函數(shù)，于是我找到了Thread中的Yield和Sleep兩個函數(shù)。在這兩個函數(shù)中，都是先調用FindNextToRun之后才調用Run的，所以可以保證是從ReadyToRun鏈表中找到優(yōu)先級最高的線程來運行。另外為了測試的方便，我還給thread中的print函數(shù)增加了輸出優(yōu)先級priority的功能。在測試優(yōu)先級調度的時候，我在threadtest里首先讓threadtest1創(chuàng)建5個線程，然后給simplethread增加了一些內(nèi)容，主要就是讓它不停地輸出readylist的信息和調用TS()，當然還要讓它不停地yield，這樣才能給其它線程運行的機會。在創(chuàng)建

18、線程的時候，我賦給這個線程與其創(chuàng)建順序相反的優(yōu)先級，這樣就可以比較明顯地看到優(yōu)先級在線程調度中所起到的作用。測試結果最后表明時正確的，后創(chuàng)建的線程反而會先被運行。Chanlenge：從exercise 2閱讀代碼部分可以看到，要想完成時間片輪轉調度的話，有三個步驟必須完成想辦法使得onetick發(fā)生，這樣時鐘才能前進想辦法調用interrupt的schedule函數(shù)，這樣才能給本線程結束的中斷確定時間想辦法使得中斷發(fā)生時yieldOnReturn的值為true，也就是提前調用yieldOnReturn函數(shù)來設置yieldOnReturn的值為true按照這樣的思路，來完成這項任務，我在sche

19、duler的run函數(shù)中嘗試增加interrupt-schedule（開始的時候想使用timerexpired，但是總是錯誤），在這個文件中增加一個timerinterrupthandler（基本照抄system里面的），因為schedule的任務就是設置下一次中斷發(fā)生的時間而timerinterrpthandler中有了yieldonreturn，所以這樣任務基本上就完成了，至于onetick的調用，只要開關一次中斷即可。于是我在schedule調用的后面加了一對關開中斷的操作。這樣之后進行測試，程序可以跑通，在不添加yield的情況下也能自動輪轉，但是在同時添加了優(yōu)先級的設置后，卻出現(xiàn)了段

20、錯誤。后來在調試代碼的過程中仔細查看，發(fā)現(xiàn)了若干錯誤，比如因為git的使用原因，我原本改對了的threadlist又被恢復成了錯誤的，在system中可以看到如果在啟動nachos之前添加了rs選項的話，會new出一個timer，再去看timer內(nèi)部的代碼，發(fā)現(xiàn)在timer中已經(jīng)又了schedule和yieldonreturn的功能（分別在tiemrexpired和system的timeinterrupthandler里）而因為我又修改了timeofnextinterrupt中else的內(nèi)容，這樣我所說的上面三個條件就都滿足了，因此，實際上不需要在scheduler的run中增加內(nèi)容，而只需要在所以system中在沒有rs選項的情況下自己創(chuàng)建出一個randomized設置為false的timer即可。根據(jù)這樣的思路，我修改了我的代碼，發(fā)現(xiàn)在沒有優(yōu)先級加入時仍然可以跑通，但是加入優(yōu)先級后就會繼續(xù)出現(xiàn)段錯誤。在查看錯誤出現(xiàn)之前的部分結果時我發(fā)現(xiàn)，m