LAB1 線程機制和線程調度實現

任務完成情況

任務Y/N

調研Linux的PCB	Y
Exercise1 源代碼閱讀	Y
Exercise2 擴展線程的數據結構	Y
Exercise3 增加全局線程管理機制	Y
Exercise4 源代碼閱讀	Y
Exercise5 實現優先級搶占調度算法	Y
*Chalenge 實現時間片輪轉算法	Y

調研Linux的進程控制塊

五個互斥狀態

狀態描述

TASK_RUNNING	表示進程正在執行，或者已經準備就緒，等待處理機調度
TASK_INTERRUPTIBLE	表示進程因等待某種資源而被掛起（阻塞態），一旦資源就緒，進程就會轉化為TASK_RUNNING態
TASK_UNINTERRUPTIBLE	與TASK_INTERRUPTIBLE狀態類似，同樣表示進程因等待某種資源而阻塞。二者唯一的區別在于：前者可以通過一些信號或者外部中斷來喚醒，而后者只能通過等待的資源就緒被喚醒。這種狀態很少被用到，但是不代表它沒有用，實際上這種狀態很有用，特別是對于驅動刺探相關的硬件過程至關重要。
TASK_STOPPED	進程被停止執行，當進程接收到SIGSTOP、SIGTTIN、SIGTSTP或者SIGTTOU信號之后就會進入該狀態
TASK_TRACED	表示進程被debugger等進程監視，進程執行被調試程序所停止，當一個進程被另外的進程所監視，每一個信號都會讓進城進入該狀態

兩個終止狀態

狀態描述

EXIT_ZOMBIE	僵尸進程是當子進程比父進程先結束，而父進程又沒有回收子進程，釋放子進程占用的資源，此時子進程將成為一個僵尸進程。如果父進退出 ，子進程被init接管，子進程退出后init會回收其占用的相關資源，但如果父進程不退出，子進程所占有的進程ID將不會被釋放，如果系統中僵尸進程過多，會占用大量的PID，導致PID不足，這是僵尸進程的危害，應當避免
EXIT_DEAD	進程正常結束的最終狀態

進程的轉換過程

調度策略

字段	描述	所在調度器類
SCHED_NORMAL	（也叫SCHED_OTHER）用于普通進程，通過CFS調度器實現。SCHED_BATCH用于非交互的處理器消耗型進程。SCHED_IDLE是在系統負載很低時使用	CFS
SCHED_BATCH	SCHED_NORMAL普通進程策略的分化版本。采用分時策略，根據動態優先級(可用nice()API設置），分配 CPU 運算資源。注意：這類進程比上述兩類實時進程優先級低，換言之，在有實時進程存在時，實時進程優先調度。但針對吞吐量優化	CFS
SCHED_IDLE	優先級最低，在系統空閑時才跑這類進程(如利用閑散計算機資源跑地外文明搜索，蛋白質結構分析等任務，是此調度策略的適用者）	CFS
SCHED_FIFO	先入先出調度算法（實時調度策略），相同優先級的任務先到先服務，高優先級的任務可以搶占低優先級的任務	RT
SCHED_RR	輪流調度算法（實時調度策略），后者提供 Roound-Robin 語義，采用時間片，相同優先級的任務當用完時間片會被放到隊列尾部，以保證公平性，同樣，高優先級的任務可以搶占低優先級的任務。不同要求的實時任務可以根據需要用sched_setscheduler()API 設置策略	RT
SCHED_DEADLINE	新支持的實時進程調度策略，針對突發型計算，且對延遲和完成時間高度敏感的任務適用。基于Earliest Deadline First (EDF) 調度算法

Linux與Nachos的異同

Linux中的task_struct

PID

特征信息(name, tID, tgID等)

進程狀態

優先級

通信狀態

現場保護區

資源需求、分配控制信息

進程實體信息

其他（工作單位、工作區、文件信息）

Nachos中的PCB實現

成員變量描述

name	進程名字
status	進程狀態
machineState	寄存器狀態
stackTop	棧頂
stack	棧底

異同

Nachos是一個羽量級的Linux（這么說是不嚴謹的，因為Nachos很多接口和Linux不同，典型例子–Fork())，Nachos很多功能待完善。

Exercise1 源代碼閱讀

main.cc

從注釋可以看出，main()的作用是引導操作系統內核/檢查命令行參數/初始化數據結構/調用測試流程（可選）。

方法描述

DEBUG(char flag, char *format, …)	如果啟用了該標志（flag），則打印一條調試消息。像printf一樣，只是在前面多了一個額外的參數
Initialize(int argc, char **argv)	初始化Nachos全局數據結構。解釋命令行參數，以確定用于初始化的標志。“ argc”是命令行參數的數量（包括名稱）；“ argv”是一個字符串數組，每個命令行參數占argv中的一個位置
ThreadTest()	調用某個測試流程，可以在case中自定義。

ThreadTest.cc

變量/方法描述

testnum	測試編號，可以在命令行中輸入./nachos -q testnum，以執行對應的測試流程
SimpleThread(int which)	循環5次，每次迭代都會讓出CPU給另外一個就緒進程，which是用來標識線程的簡單標志，可用于調試。
ThreadTest1()	通過派生一個線程調用SimpleThread，然后自己調用SimpleThread，在兩個線程交替執行
ThreadTest()	根據testnum調用對應的測試流程

thread.h/thread.cc

宏描述

MachineStateSize	上下文切換時需要保存的CPU寄存器狀態，SPARC和MIPS僅需要10個，而Snake需要18個，為了能夠在每個系統上執行，取值18。
StackSize	線程執行的私有棧空間大小，大小為4096個字(in words, not Bytes）。
ThreadStatus	枚舉了線程的狀態：JUST_CREATED(創建）, RUNNING(執行), READY(就緒），BLOCKED(阻塞)。
STACK_FENCEPOST	將其放在執行堆棧的頂部，以檢測堆棧溢出，值為0xdeadbeef

成員變量/方法描述

stackTop	當前線程的棧頂指針
machineState	棧頂指針所需要的所有寄存器，全部保存在該數組中
Thread::Thread(char *debugName)	初始化線程控制塊，以便我們可以調用Thread::Fork。"threadName"是任意字符串，可用于調試。
Thread::~Thread()	取消分配線程。 注意：當前線程不能直接刪除自身， 由于它仍在堆棧中運行，因此我們還需要刪除它的堆棧。注意：如果這是主線程，則由于未分配堆棧，因此無法刪除堆棧-在啟動Nachos時會自動獲取堆棧。
Thread::Fork(VoidFunctionPtr func, void *arg)	調用(* func)(arg)，允許調用方和被調用方并發執行。注意：盡管定義只允許將單個整數參數傳遞給過程，但是可以通過將多個參數設為結構的字段，并將指針作為“ arg”傳遞給該結構來傳遞多個參數。可以按以下步驟實現：1.分配堆棧2.初始化堆棧，以便對SWITCH的調用將使其運行3.將線程放在就緒隊列中“ func”是要同時運行的過程。“ arg”是要傳遞給該過程的單個參數。
Thread::CheckOverflow()	檢查線程的堆棧，以查看其是否超出了為其分配的空間。注意：Nachos不會捕獲所有堆棧溢出條件。 換句話說，程序可能仍會由于溢出而崩潰。如果得到奇怪的結果（例如沒有代碼的段錯誤），那么可能需要增加堆棧大小。可以通過不在堆棧上放置大型數據結構來避免堆棧溢出。(不要這樣做：void foo（）{int bigArray [10000]; …}
Thread::Finish ()	線程完成分叉過程時，由ThreadRoot調用Thread::Finish。注意：系統不會立即取消分配線程數據結構或執行堆棧，因為線程仍在堆棧中運行！相反，系統設置“ threadToBeDestroyed”，以便一旦系統在其他線程的上下文中運行，Scheduler::Run()將調用析構函數。 注意：該操作為原子操作，禁止中斷。
Thread::Yield ()	如果有其他就緒線程，讓出CPU，再將該線程添加到就緒列表的末尾，以便最終對其進行重新調度。 注意：此操作為原子操作，禁止中斷。
Thread::Sleep ()	放棄CPU，因為當前線程在等待同步變量（信號量，鎖定或條件）時被阻塞。最終，某個線程將喚醒該線程，并將其放回到就緒隊列中，以便可以對其進行重新調度。
Thread::StackAllocate (VoidFunctionPtr func, void *arg)	分配并初始化執行堆棧。堆棧使用ThreadRoot的初始堆棧框架初始化，該框架如下： 啟用中斷 通話(* fun)(carg)調用Thread::Finish

Exercise2 擴展線程的數據結構

為了增加用戶ID和線程ID，在thread.h中新增uID和tID兩個變量，在system.h/system.cc中新增一個大小為128的數組isAllocatable[128],并在initialize()方法中對其初始化為全0，確保每次nachos執行時該數組會被初始化。最后增加一個變量threadCount用于記錄線程數，初始化為0。

維護tID

在Thread::Thread()方法中遍歷isAllocatable數組，將第一個遇到的未分配的線程ID分配給當前線程，同時threadCount增加1。

在Thread::~Thread()方法中將isAllocatable[this->tID]重新置為0，然后令threadCount減少1。

維護uID

與同學討論之后我們認為nachos沒有維護用戶ID的條件，因此我將uID設為一個默認值0。如果要維護uID，應該增加在登錄時輸入用戶名和密碼的功能，并建立用戶名和uID的映射關系。

Exercise3 增加全局線程管理機制

使nachos中最多存在128個線程

在調用thread::thread()方法之前先檢查threadCount的值是否小于128，如果是，代表還能夠繼續分配線程；如果不是，代表已經達到線程數量的最大值，屏幕打印錯誤信息。

仿照Linux中PS命令，增加一個功能TS(Threads Status)，能夠顯示當前系統中所有線程的信息和狀態

算法思想

題目的要求是在terminal中輸入./nacos -TS能夠打印出線程的信息，為了實現這一功能，應該在shell中增加一個"-TS"的判斷。如果用戶輸入了./nacos -TS那么調用TS()方法。但是鑒于現在的能力不足，暫時先用一個TS方法代替，等以后實現了shell之后再來實現這個功能。

定義Thread* threadPtr[128]

在system.h/system.cc中新增一個大小為128的類型為Thread*的數組threadPtr，在initialize()中初始化為NULL。其作用是建立線程指針和tID之間的映射關系(map)。維護方法和isAllocatable類似，在Thread::Thread()方法中，每分配一個tID就讓threadPtr[tID] = this。在Thread::~Thread()方法中令threadPtr[tID] = NULL。

定義TS()方法

在ThreadTest.cc中定義TS()方法，遍歷isAllocatable數組，每當遇到非零的元素時，通過threadPtr找到其對應的線程指針，屏幕打印其對應的uID/tID/name/status。

成果演示

我在threadTest.cc中new了130個線程，然后讓它們交替執行兩次，最后調用TS方法查看線程的信息，在terminal中輸入./nachos -q 2后，執行結果如下：

Exercise4 源代碼閱讀

scheduler.h/scheduler.cc

成員方法描述

Scheduler::Scheduler()	初始化就緒隊列
Scheduler::~Scheduler()	釋放就緒隊列
Scheduler::ReadyToRun (Thread *thread)	將線程加入就緒隊列隊尾
Scheduler::FindNextToRun ()	返回就緒隊列隊首線程，若隊列為空，返回NULL
Scheduler::Run (Thread *nextThread)	將CPU分配給nextThread。保存舊線程的狀態，并加載新線程的狀態，通過調用機器依賴上下文切換例程SWITCH。注意：threadToBeDestroyed是正在等待釋放的線程，因為它們不能自己釋放自己，所以必須通過除自己之外的線程來釋放。
Scheduler::Print()	打印就緒隊列，用于調試

timer.h/timer.cc

成員變量/方法描述

randomize	設置是否需要使用隨機時間片
handler	計時器中斷處理程序
arg	中斷處理函數所需要的參數
Timer::Timer()	初始化一個Timer。包括時間中斷處理函數及其參數，以及一個可選的隨機時間片標記
Timer::TimerExpired()	安排下一次中斷的時間，并調用中斷處理函數
Timer::TimeOfNextInterrupt()	返回時間片大小

在 Timer 的初始化函數中，借用 TimerHandler 成員函數而不直接用初始 化函數中的 timerHandler 參數作為中斷處理函數的原因：如果直接使用 timerHandler 作為時鐘中斷處理函數，一旦中斷時刻到來，立即進行中斷處理，處理結束后來不及將下一個時鐘中斷插入到等待處理中斷隊列。 TimerHandler 內部函數正是處理這個問題。當時鐘中斷時刻到來時，調用 TimerHandler 函數， 其調用 TimerExpired 方法，該方法將新的時鐘中斷插入到等待處理中斷隊列中，然后再調用 真正的時鐘中斷處理函數。這樣 Nachos 就可以定時的收到時鐘中斷。

那么為什么不將TimerExpired方法作為時鐘中斷在Timer的初始化函數中調用呢？這是由于 C++語言不能直接引用一個類成員方法的指針，所以借用 TimerHandler 內部函數。這也是 TimerExpired 必須設計成 public 的方法的原因，因為它要被 TimerHandler 調用。

參考資料：《Nachos中文教程》

在nachos中已經實現了一個模擬計時器Timer，它的作用為：每隔一段時間會產生一次時間中斷。需要注釋掉system.cc里面的if(ramdomyeild)來初始化一個Timer，interrupt.cc::scheduler()方法表明系統會每隔一個時間片來安排一次時間中斷，然后調用時間中斷處理函數。 具體的實現機理：系統初始化一個Timer，調用Interrupt::Schedule來創建一個名為toOccur的延遲中斷對象，并將其插入中斷隊列中，表示在既定的延遲時間之后，會產生中斷，并調用中斷處理函數。在調用了中斷處理函數之后，會將 yieldOnReturn標記設為true，表在中斷處理函數結束之后會在OneTick()方法中執行進程切換。

switch.s

圖源：https://blog.csdn.net/ShiningStarPxx/article/details/7456840

SWITCH函數 Nachos 中系統線程的切換是借助宿主機的正文切換。SWITCH 函數就是完成線程切換的功 能。SWITCH 的語法是這樣的： void SWITCH (Thread *t1, Thread *t2); 其中 t1 是原運行線程指針，t2 是需要切換到的線程指針。線程切換的三步曲是： 保存原線程上下文->恢復新線程的上下文->在新線程的棧空間繼續運行。

參考資料：《Nachos中文教程》

Exercise5 實現優先級搶占調度算法

算法思想

題目要求實現優先級搶占算法，顧名思義，當線程被創建時，應該與currentThread比較，如果優先級高于currentThread，應該剝奪，否則，按照優先級插入readyList。這些修改都應該寫在Scheduler::ReadyToRun方法中。

新增變量/語句

位置新增變量/語句描述

thread.h	prio	線程優先級（值越小代表優先級越高）
Scheduler::ReadyToRun(Thread *thread)	readyList->SortedInsert((void*) thread, thread->getPrio());	先把thread按照優先級插入隊列
Scheduler::ReadyToRun(Thread *thread)	if (thread->getPrio() < currentThread->getPrio()) currentThread->Yield();	如果該線程的優先級高于正在運行的線程，直接搶占，否則什么也不做

成果演示

我修改了SimpleThread的內容，將其改為如果currentThread的priority>0, 那么就會fork一個比它priority小1的線程，將main線程的優先級初始化為7，預期結果：main會fork一個優先級為6的線程，然后被該線程剝奪；然后該線程會fork一個優先級為5的線程，然后被這個優先級為5的線程剝奪，直到fork出一個優先級為0的線程。在terminal中輸入./nachos -q 3可以查看結果。

*Chalenge 實現時間片輪轉算法

算法思想

在Thread類里新增timeSlice時間片成員變量，設為缺省值5，表示我們實現的是固定時間片的時間片輪轉算法，如果要實現可變時間片，那么修改Thread的構造函數即可。并且增設totalRunningTime成員變量，用來表示當前進程的總執行時間，設為缺省值10，表示每個進程都是10個單位時間執行完成（也可以自定義，這樣更貼合實際中作業長短不一的情況）（雖然在實際中某進程的執行時間不可預計，但是在我們的測試中可以將某進程的總執行時間設為缺省值，因為我們的任務是檢查時間片輪轉是否生效）。

可以修改TimerTicks宏來自定義時間片。將TimerTicks的大小設為1，這樣就能實現每個單位時間都會產生中斷，并且在中斷處理函數中會讓當前進程的時間片和總的運行時間都減少1，并且check一下當前進程的時間片是否已經用完，如果用完，那么就進行線程切換。每次中斷之后，系統都會調用OneTick方法來讓系統時間增加10，這是Nachos作者為了方便起見定義每次中斷處理都會花費10的時間（若為用戶指令，則為1）。

新增語句

位置新增變量/語句描述

Thread.h	timeSlice	線程時間片
Thread.h	totalRunningTime	線程的總運行時間
system.cc::TimerInterruptHandler()	currentThread->totalRunningTime–;currentThread->timeSlice–;	當前線程的運行時間和時間片均自減1
system.cc::TimerInterruptHandler()	if (!currentThread->timeSlice){currentThread->timeSlice = 5;interrupt->YieldOnReturn();}	若當前線程時間片用完，重新賦予時間片，并且進行線程切換

成果演示

我在測試函數中new了一個線程，加上main()線程，總共兩個。他們的總運行時間都為10，時間片都是5。系統每隔一個單位時間會產生一次時鐘中斷來check當前線程的時間片是否用完。中斷處理會花費10的單位時間，相當于每隔10的單位時間會check一次，每check一次，當前進程的運行時間就會+1，直到達到它的總運行時間為止，預期結果：每隔5的單位時間會發生一次線程切換（算上中斷處理的時間是50），并且在兩個線程的運行時間達到10時結束。在terminal中輸入./nachos -q 4可查看結果：

困難&解決

收獲及感想

上面的負能量可能比較多，現在開始抒發正能量。

通過本次lab我發現實驗沒有那么難，最困難的事情應該是從零開始寫一個OS。而我們的實驗都是建立在別人的框架之上的，我們要做的就是：閱讀框架->理解框架->添磚加瓦。

這里要分享一下我讀源代碼的方法：先看注釋，了解某個方法是干什么的。然后再看這個方法的實現，理解之后，默寫一遍。對，很多模塊除開注釋也就幾十行，如果你真的理解了，默寫并不困難。如果你都做到了，那么就可以自信地說自己已經理解源代碼了。

理解了源代碼之后，要解決每個exercise基本可以說是信手拈來。

BUGs

1.通過閱讀scheduler.cc中的Run方法我發現了一個nachos的BUG：SWITCH和delete threadToBeDestroyed的順序反了，這樣會導致finish方法調用之后，線程并不會被及時地析構，而系統會進入下一個就緒線程繼續運行，原來的這個線程就被永遠地阻塞！

猜想：要解決這個bug， 需要將SWITCH和delete的順序顛倒，這需要我們提前復制一份threadToBeDestroyed的棧空間，以便delete之后可以用它來給SWITCH使用。

2.Nachos的模擬時間在測試函數無限循環時不會增加，比如說，當我寫下如下語句時,系統時間會停滯.解決辦法：在while中添加一句：interrupt->OneTick()。但是這么做是不妥的，因為OneTick方法是內部硬件的模擬方法，不該直接調用，它的屬性應為private，之所以為public是因為它被硬件模擬代碼直接調用。也就是說OneTick()方法出現在此處是不對的，但是我暫時想不到更好的方法，如果有人能解決這個問題，歡迎交流。

//time-slicing algorithm,in threadTest.cc void mySimlpe2(int dummy) {while (stats->totalTicks < 3000);//當系統時間小于3000時無限循環，在測試中使用無限循環來模擬實際中作業的執行 } void timeSlicingTest() {Thread *t = new Thread("forked", 1);t->Fork(mySimlpe2, 1);mySimlpe2(1); }

參考文獻

Linux進程描述符task_struct結構體詳解–Linux進程的管理與調度（一）

匯編語言入門教程

《Nachos中文教程》

致謝

感謝羅哥在我最沮喪的時候陪伴我安裝vagrant，雖然沒有成功。

感謝陳向群老師多次幫助，感恩。

總結

以上是生活随笔為你收集整理的Nachos LAB1 线程机制和线程调度实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。