【文章內(nèi)容簡介】 用戶進(jìn)程信號量條件變量鎖Thread類模擬中斷正文切換線程調(diào)度Nachos線程系統(tǒng)的結(jié)構(gòu)線程管理系統(tǒng)中，有兩個與機器相關(guān)的函數(shù)，正文切換過程依賴于具體的機器，這是因為系統(tǒng)線程切換是借助于宿主機的正文切換，正文切換過程中的寄存器保護(hù)，建立初始調(diào)用框架等操作對不同的處理機結(jié)構(gòu)是不一樣的。其中一個函數(shù)是ThreadRoot，它是所有線程運行的入口；另一個函數(shù)是SWITCH，它負(fù)責(zé)線程之間的切換。 Scheduler類用于實現(xiàn)線程的調(diào)度。它維護(hù)一個就緒線程隊列，當(dāng)一個線程可以占用處理機時，就可以調(diào)用ReadyToRun方法把這個線程放入就緒線程隊列，并把線程狀態(tài)改成就緒態(tài)。FindNextToRun方法根據(jù)調(diào)度策略，取出下一個應(yīng)運行的線程，并把這個線程從就緒線程隊列中刪除。如果就緒線程隊列為空，則此函數(shù)返回空(NULL)?，F(xiàn)有的調(diào)度策略是先進(jìn)先出策略(FIFO)，Thread類的對象既用作線程的控制塊，相當(dāng)于進(jìn)程管理中的PCB，作用是保存線程狀態(tài)、進(jìn)行一些統(tǒng)計，又是用戶調(diào)用線程系統(tǒng)的界面。用戶生成一個新線程的方法是: Thread* newThread = new Thread(New Thread)。// 生成一個線程類 newThreadFork(ThreadFunc，ThreadFuncArg)。// 定義新線程的執(zhí)行函數(shù)及其參數(shù) Fork方法分配一塊固定大小的內(nèi)存作為線程的堆棧，在棧頂放入ThreadRoot的地址。當(dāng)新線程被調(diào)上CPU時，要用SWITCH函數(shù)切換線程圖像，SWITCH函數(shù)返回時，會從棧頂取出返回地址，于是將ThreadRoot放在棧頂，在SWITCH結(jié)束后就會立即執(zhí)行ThreadRoot函數(shù)。ThreadRoot是所有線程的入口，它會調(diào)用Fork的兩個參數(shù)，運行用戶指定的函數(shù)；Yield方法用于本線程放棄處理機。Sleep方法可以使當(dāng)前線程轉(zhuǎn)入阻塞態(tài)，并放棄CPU，直到被另一個線程喚醒，把它放回就緒線程隊列。在沒有就緒線程時，就把時鐘前進(jìn)到一個中斷發(fā)生的時刻，讓中斷發(fā)生并處理此中斷，這是因為在沒有線程占用CPU時，只有中斷處理程序可能喚醒一個線程，并把它放入就緒線程隊列。線程要等到本線程被喚醒后，并且又被線程調(diào)度模塊調(diào)上CPU時，才會從Sleep函數(shù)返回。有趣的是，新取出的就緒線程有可能就是這個要睡眠的線程。例如，如果系統(tǒng)中只有一個A線程，A線程在讀磁盤的時候會進(jìn)入睡眠，等待磁盤操作完成。因為這時只有一個線程，所以A線程不會被調(diào)下CPU，只是在循環(huán)語句中等待中斷。當(dāng)磁盤操作完成時，磁盤會發(fā)出一個磁盤讀操作中斷，此中斷將喚醒A線程，把它放入就緒隊列。這樣，當(dāng)A線程跳出循環(huán)時，取出的就緒線程就是自己。這就要求線程的正文切換程序可以將一個線程切換到自己， Nachos的線程正文切換程序SWITCH可以做到這一點，于是A線程實際上并沒有被調(diào)下CPU，而是繼續(xù)運行下去了。Nachos線程管理系統(tǒng)的初步實現(xiàn)1. 工具模塊分析（ ）工具模塊定義了一些在Nachos設(shè)計中有關(guān)的工具函數(shù)，和整個系統(tǒng)的設(shè)計沒有直接的聯(lián)系，所以這里僅作一個簡單的介紹。List類在Nachos中廣泛使用，它定義了一個鏈表結(jié)構(gòu)，有關(guān)List的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)如下所示：class ListElement { // 定義了List中的元素類型 public: ListElement(void *itemPtr, int sortKey)。 // 初始化方法 ListElement *next。 // 指向下一個元素的指針 int key。 // 對應(yīng)于優(yōu)先隊列的鍵值 void *item。 // 實際有效的元素指針}。其中，實際有效元素指針是(void *)類型的，說明元素可以是任何類型。class List { public: List()。 // 初始化方法 ~List()。 // 析構(gòu)方法 void Prepend(void *item)。 // 將新元素增加在鏈?zhǔn)?void Append(void *item)。 // 將新元素增加在鏈尾 void *Remove()。 // 刪除鏈?zhǔn)自夭⒎祷卦撛?void Mapcar(VoidFunctionPtr func)。 // 將函數(shù)func作用在鏈中每個元素上 bool IsEmpty()。 // 判斷鏈表是否為空 void SortedInsert(void *item, int sortKey)。 // 將元素根據(jù)key值優(yōu)先權(quán)插入到鏈中 void *SortedRemove(int *keyPtr)。 // 將key值最小的元素從鏈中刪除， // 并返回該元素 private: ListElement *first。 // 鏈表中的第一個元素 ListElement *last。 // 鏈表中的最后一個元素}。其它的工具函數(shù)如min和max以及一些同調(diào)試有關(guān)的函數(shù)，這里就不再贅述。2. 線程啟動和調(diào)度模塊分析（ ）線程啟動和線程調(diào)度是線程管理的重點。在Nachos中，線程是最小的調(diào)度單位，在同一時間內(nèi)，可以有幾個線程處于就緒狀態(tài)。Nachos的線程切換借助于宿主機的正文切換，由于這部分內(nèi)容與機器密切相關(guān)，而且直接同宿主機的寄存器進(jìn)行交道，所以這部分是用匯編來實現(xiàn)的。由于Nachos可以運行在多種機器上，不同機器的寄存器數(shù)目和作用不一定相同。讀者如果需要將Nachos移植到其它機器上，就需要修改這部分的內(nèi)容。 ThreadRoot函數(shù)Nachos中，除了main線程外，所有其它線程都是從ThreadRoot入口運行的。它的語法是：ThreadRoot (int InitialPC, int InitialArg, int WhenDonePC, int StartupPC)其中，InitialPC指明新生成線程的入口函數(shù)地址，InitialArg是該入口函數(shù)的參數(shù)；StartupPC是在運行該線程是需要作的一些初始化工作，比如開中斷；而WhenDonePC是當(dāng)該線程運行結(jié)束時需要作的一些后續(xù)工作。在Nachos的源代碼中，沒有任何一個函數(shù)和方法顯式地調(diào)用ThreadRoot函數(shù)，ThreadRoot函數(shù)只有在線程切換時才被調(diào)用到。一個線程在其初始化的最后準(zhǔn)備工作中調(diào)用StackAllocate方法（），該方法設(shè)置了幾個寄存器的值（InterruptEnable函數(shù)指針，ThreadFinish函數(shù)指針以及該線程需要運行函數(shù)的函數(shù)指針和運行函數(shù)的參數(shù)） ，該線程第一次被切換上處理機運行時調(diào)用的就是ThreadRoot函數(shù)。其工作過程是：1. 調(diào)用 StartupPC 函數(shù)；2. 調(diào)用 InitialPC 函數(shù)；3. 調(diào)用 WhenDonePC 函數(shù)；這里我們可以看到，由ThreadRoot入口可以轉(zhuǎn)而運行線程所需要運行的函數(shù)，從而達(dá)到生成線程的目的。 SWITCH函數(shù)Nachos中系統(tǒng)線程的切換是借助宿主機的正文切換。SWITCH函數(shù)就是完成線程切換的功能。SWITCH的語法是這樣的： void SWITCH (Thread *t1, Thread *t2)。其中t1是原運行線程指針，t2是需要切換到的線程指針。線程切換的三步曲是：1. 保存原運行線程的狀態(tài)2. 恢復(fù)新運行線程的狀態(tài)3. 在新運行線程的?？臻g上運行新線程3. 線程模塊分析（ ）Thread類實現(xiàn)了操作系統(tǒng)的線程控制塊，同操作系統(tǒng)課程中進(jìn)程程管理中的PCB (Process Control Block) 有相似之處。Thread線程控制類較PCB為簡單的多，它沒有線程標(biāo)識 (pid)、實際用戶標(biāo)識 (uid)等和線程操作不是非常有聯(lián)系的部分，也沒有將PCB分成proc結(jié)構(gòu)和user結(jié)構(gòu)。這是因為一個Nachos線程是在宿主機上運行的。無論是系統(tǒng)線程和用戶進(jìn)程，Thread線程控制類的實例都生成在宿主機而不是生成在虛擬機上。所以不存在實際操作系統(tǒng)中proc結(jié)構(gòu)常駐內(nèi)存，而user結(jié)構(gòu)可以存放在盤交換區(qū)上的情況，將原有的兩個結(jié)構(gòu)合并是Nachos作的一種簡化。Nachos對線程的另一個簡化是每個線程棧段的大小是固定的，為40965個字 (word)，而且是不能動態(tài)擴展的。所以Nachos中的系統(tǒng)線程中不能使用很大的?？臻g，比如： void foo () { int buff[10000]。 ...}可能會不能正常執(zhí)行，如果需要使用很大空間，可以在Nachos的運行堆中申請： void foo () { int *buf = new int[10000]。 ...}如果系統(tǒng)線程需要使用的?？臻g大于規(guī)定棧空間的大小，可以修改StackSize宏定義。Thread類的定義和實現(xiàn)如下所示：class Thread { private: int* stackTop。 // 當(dāng)前堆棧指針 int machineState[MachineStateSize]。 // 宿主機的運行寄存器 public: Thread(char* debugName)。 // 初始化線程 ~Thread()。 // 析構(gòu)方法 void Fork(VoidFunctionPtr func, int arg)。 // 生成一個新線程，執(zhí)行func(arg) void Yield()。 // 切換到其它線程運行 void Sleep()。 // 線程進(jìn)入睡眠狀態(tài) void Finish()。 // 線程結(jié)束時調(diào)用 void CheckOverflow()。 // 測試線程棧段是否溢出 void setStatus(ThreadStatus st)。 // 設(shè)置線程狀態(tài) char* getName() { return (name)。 } // 取得線程名（調(diào)試用） void Print() { printf(%s, , name)。 } // 打印當(dāng)前線程名（調(diào)試用） private: int* stack。 // 線程的棧底指針 ThreadStatus status。 // 當(dāng)前線程狀態(tài) char* name。