1、操作系統課程設計說 明 書學 院： 信息科學與工程學院 一、 理解Nachos模擬的物理機的運行機制31. Sysdep模塊分析（文件）52.中斷模塊分析（文件）103. 時鐘中斷模塊分析（文件）164. 終端設備模塊分析（文件）18二、 理解Nachos中線程運行機制191. 工具模塊分析（文件）202. 線程啟動和調度模塊分析（文件）213. 線程模塊分析（文件）224. 線程調度算法模塊分析（文件）265.Nachos主控模塊分析（文件）276. 同步機制模塊分析（文件）28三、 理解Nachos中支持用戶進程的機制30一、用戶程序空間（文件address.cc, address.h）3

2、5二、系統調用（文件exception.cc, syscall.h, start.s）361、 理解Nachos模擬的物理機的運行機制Machine類用來模擬計算機主機。它提供的功能有：讀寫寄存器。讀寫主存、運行一條用戶程序的匯編指令、運行用戶程序、單步調試用戶程序、顯示主存和寄存器狀態、將虛擬內存地址轉換為物理內存地址、陷入 Nachos 內核等等。Machine類實現方法是在宿主機上分配兩塊內存分別作為虛擬機的寄存器和物理內存。運行用戶程序時，先將用戶程序從 Nachos 文件系統中讀出，寫入模擬的物理內存中，然后調用指令模擬模塊對每一條用戶指令解釋執行。將用戶程序的讀寫內存要求，轉變為對

3、物理內存地址的讀寫。Machine類提供了單步調試用戶程序的功能，執行一條指令后會自動停下來，讓用戶查看系統狀態，不過這里的單步調試是匯編指令級的，需要讀者對R2/3000指令比較熟悉。如果用戶程序想使用操作系統提供的功能或者發出異常信號時，Machine調用系統異常陷入功能，進入Nachos的核心部分。Interrupt類用來模擬硬件中斷系統。在這個中斷系統中，中斷狀態有開，關兩種，中斷類型有時鐘中斷、磁盤中斷、控制臺寫中斷、控制臺讀中斷、網絡發送中斷以及網絡接收中斷。機器狀態有用戶態，核心態和空閑態。中斷系統提供的功能有開/關中斷，讀/寫機器狀態，將一個即將發生中斷放入中斷隊列，以及使機器

4、時鐘前進一步。在Interrupt類中有一個記錄即將發生中斷的隊列，稱為中斷等待隊列。中斷等待隊列中每個等待處理的中斷包含中斷類型、中斷處理程序的地址及參數、中斷應當發生的時間等信息。一般是由硬件設備模擬程序把將要發生的中斷放入中斷隊列。中斷系統提供了一個模擬機器時鐘，機器時鐘在下列情況下前進：l 用戶程序打開中斷l 執行一條用戶指令l 處理機沒有進程正在運行機器時鐘前進時，中斷處理的過程如下圖所示:Nachos中斷處理時機NYNY進行正文切換中斷處理程序要求進行正文切換?開中斷取出隊列中一個應當發生的中斷，調用這個中斷的處理程序去處理中斷中斷隊列中有應當發生的中斷?關中斷中斷系統成為整個Na

5、chos虛擬機的基礎，其它的模擬硬件設備都是建立在中斷系統之上的。在此之上，加上Machine類模擬的指令解釋器，可以實現Nachos的線程管理、文件系統管理、虛擬內存、用戶程序和網絡管理等所有操作系統功能。下圖展示了Nachos系統的整體結構。用 戶 程 序線程管理網絡協議文件系統虛擬內存終端設備時鐘網絡磁盤中 斷 系 統指令解釋和內存模擬Nachos系統的整體結構機器模擬的實現：1. Sysdep模塊分析（文件）Nachos的運行環境可以是多種操作系統，由于每種操作系統所提供的系統調用或函數調用在形式和內容上可能有細微的差別。sysdep模塊的作用是屏蔽掉這些差別。1.1 PoolFile

6、 函數語法：bool PoolFile (int fd)參數：fd:文件描述符，也可以是一個套接字 (socket)功能：測試一個打開文件 fd 是否有內容可以讀，如果有則返回TRUE，否則返回FALSE。當Nachos系統處于IDLE狀態時，測試過程有一個延時，也就是在一定時間范圍內如果有內容可讀的話，同樣返回TRUE。實現：通過 select 系統調用。返回：打開文件是否有內容供讀取。1.2 OpenForWrite 函數語法：int OpenForWrite (char *name)參數：name:文件名功能：為寫操作打開一個文件。如果該文件不存在，產生該文件；如果該文件已經存在，則將該

7、文件原有的內容刪除。實現：通過 open 系統調用。返回：打開的文件描述符。1.3 OpenForReadWrite 函數語法：int OpenForReadWrite (char *name, bool crashOnError)參數：name:文件名crashOnError:crash標志功能：為讀寫操作打開一個文件。當 crashOnError 標志設置而文件不能讀寫打開時，系統出錯退出。實現：通過 open 系統調用。返回：打開的文件描述符。1.4 Read 函數語法：void Read (int fd, char *buffer, int nBytes)參數：fd:打開文件描述符bu

8、ffer:讀取內容的緩沖區nBytes:需要讀取的字節數功能：從一個打開文件fd中讀取nBytes的內容到buffer緩沖區。如果讀取失敗，系統退出。實現：通過 read系統調用。返回：空。1.5 ReadPartial 函數語法：int ReadPartial (int fd, char *buffer, int nBytes)參數：fd:打開文件描述符buffer:讀取內容的緩沖區nBytes:需要讀取的最大字節數 功能：從一個打開文件fd中讀取nBytes的內容到buffer緩沖區。 實現：通過 read系統調用。 返回：實際讀出的字節數。1.6 WriteFile 函數 語法：void

9、 WriteFile (int fd, char *buffer, int nBytes) 參數：fd:打開文件描述符buffer:需要寫的內容所在的緩沖區nBytes:需要寫的內容最大字節數 功能：將buffer緩沖區中的內容寫nBytes到一個打開文件fd中。 實現：通過 write系統調用。 返回：空1.7 Lseek 函數 語法：void Lseek (int fd, int offset, int whence) 參數：fd:文件描述符offset:偏移量whence:指針移動的起始點 功能：移動一個打開文件的讀寫指針，含義同lseek系統調用；出錯則退出系統。 實現：通過lseek

10、 系統調用。 返回：空。1.8 Tell 函數 語法：int Tell (int fd) 參數：fd:文件描述符 功能：指出當前讀寫指針位置 實現：通過lseek 系統調用。 返回：返回當前指針位置。1.9 Close 函數 語法：void Close (int fd) 參數：fd:文件描述符 功能：關閉當前打開文件fd，如果出錯則退出系統。 實現：通過close系統調用。 返回：空1.10 Unlink 函數 語法：bool Unlink (char *name) 參數：name:文件名 功能：刪除文件。 實現：通過unlink系統調用。 返回：刪除成功，返回TRUE；否則返回FALSE。1

11、.11 OpenSocket 函數 語法：int OpenSocket () 參數：無 功能：申請一個socket。 實現：通過socket系統調用。其中AF_UNIX參數說明使用UNIX內部協議。（Nachos是用SOCKET文件來模擬網絡節點，所以采用UNIX內部協議。向該文件讀寫內容分別代表從該節點讀取內容和向該網絡節點發送內容）SOCK_DGRAM參數說明采用無連接定長數據包型的數據鏈路。 返回：申請到的socket ID。1.12 CloseSocket 函數 語法：void CloseSocket (int sockID) 參數：sockID:socket標識 功能：釋放一個soc

12、ket。 實現：通過close系統調用。 返回：無。1.13 Abort 函數 語法：void Abort () 參數：無 功能：退出系統 (非正常退出)。 實現：通過abort系統調用。 返回：無。1.14 Exit 函數 語法：void Exit (int exitCode) 參數：exitCode:向系統的返回值 功能：退出系統。 實現：通過exit系統調用。 返回：空2.中斷模塊分析（文件）中斷模塊的主要作用是模擬底層的中斷機制。可以通過該模擬機制來啟動和禁止中斷 (SetLevel)；該中斷機制模擬了Nachos系統需要處理的所有的中斷，包括時鐘中斷、磁盤中斷、終端讀/終端寫中斷以及

13、網絡接收/網絡發送中斷。中斷的發生總是有一定的時間。比如當向硬盤發出讀請求，硬盤處理請求完畢后會發生中斷；在請求和處理完畢之間需要經過一定的時間。所以在該模塊中，模擬了時鐘的前進。為了實現簡單和便于統計各種活動所占用的時間起見，Nachos規定系統時間在以下三種情況下前進：執行用戶態指令，時鐘前進是顯而易見的。我們認為，Nachos執行每條指令所需時間是固定的，為一個時鐘單位(Tick)。一般系統態在進行中斷處理程序時，需要關中斷。但是中斷處理程序本身也需要消耗時間，而在關閉中斷到重新打開中斷之間無法非常準確地計算時間，所以當中斷重新打開的時候，加上一個中斷處理所需時間的平均值。當系統中沒有就

14、緒進程時，系統處于Idle狀態。這種狀態可能是系統中所有的進程都在等待各自的某種操作完成。也就是說，系統將在未來某個時間發生中斷，到中斷發生的時候中斷處理程序將進行中斷處理。在系統模擬中，有一個中斷等待隊列，專門存放將來發生的中斷。在這種情況下，可以將系統時間直接跳到中斷等待隊列第一項所對應的時間，以免不必要的等待。當前面兩種情況需要時鐘前進時，調用OneTick方法。OneTick方法將系統態和用戶態的時間分開進行處理，這是因為用戶態的時間計算是根據用戶指令為單位的；而在系統態，沒有辦法進行指令的計算，所以將系統態的一次中斷調用或其它需要進行時間計算的單位設置為一個固定值，假設為一條用戶指令

15、執行時間的10倍。雖然Nachos模擬了中斷的發生，但是畢竟不能與實際硬件一樣，中斷發生的時機可以是任意的。比如當系統中沒有就緒進程時，時鐘直接跳到未處理中斷隊列的第一項的時間。這實際情況下，系統處于Idel狀態到中斷等待隊列第一項發生時間之間，完全有可能有其它中斷發生。由于中斷發生的時機不是完全隨機的，所以在Nachos系統中運行的程序，不正確的同步程序也可能正常運行，我們在此需要密切注意。Nachos線程運行有三種狀態：Idle狀態系統CPU處于空閑狀態，沒有就緒線程可以運行。如果中斷等待隊列中有需要處理的除了時鐘中斷以外的中斷，說明系統還沒有結束，將時鐘調整到發生中斷的時間，進行中斷處理

16、；否則認為系統結束所有的工作，退出。系統態Nachos執行系統程序。Nachos雖然模擬了虛擬機的內存，但是Nachos系統程序本身的運行不是在該模擬內存中，而是利用宿主機的存儲資源。這是Nachos操作系統同真正操作系統的重要區別。用戶態系統執行用戶程序。當執行用戶程序時，每條指令占用空間是Nachos的模擬內存。中斷等待隊列是Nachos虛擬機最重要的數據結構之一，它記錄了當前虛擬機可以預測的將在未來發生的所有中斷。當系統進行了某種操作可能引起未來發生的中斷時，如磁盤的寫入、向網絡寫入數據等都會將中斷插入到中斷等待隊列中；對于一些定期需要發生的中斷，如時鐘中斷、終端讀取中斷等，系統會在中斷

17、處理后將下一次要發生的中斷插入到中斷等待隊列中。中斷的插入過程是一個優先隊列的插入過程，其優先級是中斷發生的時間，也就是說，先發生的中斷將優先得到處理。對中斷等待隊列的操作中斷等待隊列某些將會引起中斷的操作系統定期發生的中斷時鐘前進判斷有無中斷發生當時鐘前進或者系統處于Idle狀態時，Nachos會判斷中斷等待隊列中是否有要發生的中斷，如果有中斷需要發生，則將該中斷從中斷等待隊列中刪除，調用相應的中斷處理程序進行處理。中斷處理程序是在某種特定的中斷發生時被調用，中斷處理程序的作用包括可以在現有的模擬硬件的基礎上建立更高層次的抽象。比如現有的模擬網絡是有丟失幀的不安全網絡，在中斷處理程序中可以加

18、入請求重發機制來實現一個安全網絡。2.1 PendingInterrupt類class PendingInterrupt public:PendingInterrupt (VoidFunctionPtr func, int param, int time, IntType kind);VoidFunctionPtr handler;/ 中斷對應的中斷處理程序int arg;/ 中斷處理程序的參數int when;/ 中斷發生的時機IntType type;/ 中斷的類型，供調試用;這個類定義了一個中斷等待隊列中需要處理的中斷。為了方便起見，所有類的數據和成員函數都設置為public的，不需要其

19、它的Get和Set等存取內部數據的函數。初始化函數就是為對應的參數賦值。2.2 Interrupt類class Interrupt public:/ 以下函數是Interrupt的對外接口Interrupt();/ 初始化中斷模擬Interrupt();/ 終止中斷模擬IntStatus SetLevel(IntStatus level);/ 開關中斷，并且返回之前的狀態void Enable();/ 開中斷IntStatus getLevel() return level;/ 取回當前中斷的開關狀態 void Idle(); / 當進程就緒隊列為空時，執行該函數void Halt(); /

20、退出系統，并打印狀態void YieldOnReturn();/ 設置中斷結束后要進行進程切換的標志 MachineStatus getStatus() return status; / 返回系統當前的狀態 void setStatus(MachineStatus st) status = st; / 設置系統當前的狀態 void DumpState();/ 調試當前中斷隊列狀態用 void Schedule(VoidFunctionPtr handler, int arg, int when, IntType type);/ 在中斷等待隊列中，增加一個等待中斷 void OneTick();

21、 / 模擬時鐘前進 private:/ 以下是內部數據和內部處理方法 IntStatus level;/ 中斷的開關狀態 List *pending;/ 當前系統中等待中斷隊列bool inHandler;/ 是否正在進行中斷處理標志 bool yieldOnReturn; / 中斷處理后是否需要正文切換標志MachineStatus status;/ 當前虛擬機運行狀態bool CheckIfDue(bool advanceClock);/ 檢查當前時刻是否有要處理的中斷void ChangeLevel(IntStatus old, IntStatus now);/ 改變當前中斷的開關狀態，

22、但不前進模擬時鐘;其中，Schedule和 OneTick兩個方法雖然標明是public的，但是除了虛擬機模擬部分以外的其它類方法是不能調用這兩個方法的。將它們設置成public的原因是因為虛擬機模擬的其它類方法需要直接調用這兩個方法。3. 時鐘中斷模塊分析（文件）該模塊的作用是模擬時鐘中斷。Nachos虛擬機可以如同實際的硬件一樣，每隔一定的時間會發生一次時鐘中斷。這是一個可選項，目前Nachos還沒有充分發揮時鐘中斷的作用，只有在Nachos指定線程隨機切換時，（Nachos -rs參數，見線程管理部分Nachos主控模塊分析）啟動時鐘中斷，在每次的時鐘中斷處理的最后，加入了線程的切換。實

23、際上，時鐘中斷在線程管理中的作用遠不止這些，時鐘中斷還可以用作：l 線程管理中的時間片輪轉法的時鐘控制，（詳見線程管理系統中的實現實例中，對線程調度的改進部分）不一定每次時鐘中斷都會引起線程的切換，而是由該線程是否的時間片是否已經用完來決定。l 分時系統線程優先級的計算（詳見線程管理系統中的實現實例中，對線程調度的改進部分）l 線程進入睡眠狀態時的時間計算可以通過時鐘中斷機制來實現sleep系統調用，在時鐘中斷處理程序中，每隔一定的時間對定時睡眠線程的時間進行一次評估，判斷是否需要喚醒它們。Nachos利用其模擬的中斷機制來模擬時鐘中斷。時鐘中斷間隔由TimerTicks宏決定（100倍Tic

24、k的時間）。在系統模擬時有一個缺陷，如果系統就緒進程不止一個的話，每次時鐘中斷都一定會發生進程的切換（見中TimerInterruptHandler函數）。所以運行Nachos時，如果以同樣的方式提交進程，系統的結果將是一樣的。這不符合操作系統的運行不確定性的特性。所以在模擬時鐘中斷的時候，加入了一個隨機因子，如果該因子設置的話，時鐘中斷發生的時機將在一定范圍內是隨機的。這樣有些用戶程序在同步方面的錯誤就比較容易發現。但是這樣的時鐘中斷和真正操作系統中的時鐘中斷將有不同的含義。不能象真正的操作系統那樣通過時鐘中斷來計算時間等等。是否需要隨機時鐘中斷可以通過設置選項(-rs)來實現。Timer類

25、的實現很簡單，當生成出一個Timer類的實例時，就設計了一個模擬的時鐘中斷。這里考慮的問題是：怎樣實現定期發生時鐘中斷？在Timer的初始化函數中，借用TimerHandler內部函數（見第1行）。為什么不直接用初始化函數中的timerHandler參數作為中斷處理函數呢？因為如果直接使用timerHandler作為時鐘中斷處理函數，第8行是將一個時鐘中斷插入等待處理中斷隊列，一旦中斷時刻到來，立即進行中斷處理，處理結束后并沒有機會將下一個時鐘中斷插入到等待處理中斷隊列。TimerHandler內部函數正是處理這個問題。當時鐘中斷時刻到來時，調用TimerHandler函數，其調用TimerE

26、xpired方法，該方法將新的時鐘中斷插入到等待處理中斷隊列中，然后再調用真正的時鐘中斷處理函數。這樣Nachos就可以定時的收到時鐘中斷。那么為什么不將TimerExpired方法作為時鐘中斷在Timer的初始化函數中調用呢？這是由于C+語言不能直接引用一個類內部方法的指針，所以借用TimerHandler內部函數。這也是TimerExpired必須設計成public的方法的原因，因為它要被TimerHandler調用。這樣的方法不僅僅在Timer模擬時鐘中斷中用到，所有需要定期發生的中斷都可以采用這樣的方法，如Nachos需要定期地檢查是否有終端的輸入、網絡是否有發給自己的報文等都是用這種

27、方式實現。詳見 network.cc 以及。TimeOfextInterrupt()方法的作用是計算下一次時鐘中斷發生的時機，如果需要時鐘中斷發生的時機是隨機的，可以在Nachos命令行中設置 rs 選項。這樣，Nachos的線程切換的時機將會是隨機的。但是此時時鐘中斷則不能作為系統計時的標準了。2、 理解Nachos中線程運行機制Nachos中的系統線程和用戶進程宿主機CPU和寄存器虛擬機CPU和寄存器用戶程序系統線程用戶程序系統線程用戶進程用戶程序系統線程系統線程系統線程系統線程Nachos為線程提供的功能函數有:1. 生成一個線程(Fork)2. 使線程睡眠等待(Sleep)3. 結束線

28、程(Finish)4. 設置線程狀態(setStatus)5. 放棄處理機(Yield)線程系統的結構如圖所示:用戶進程信號量條件變量鎖Thread類模擬中斷正文切換線程調度Nachos線程系統的結構線程管理系統中，有兩個與機器相關的函數，正文切換過程依賴于具體的機器，這是因為系統線程切換是借助于宿主機的正文切換，正文切換過程中的寄存器保護，建立初始調用框架等操作對不同的處理機結構是不一樣的。其中一個函數是ThreadRoot，它是所有線程運行的入口；另一個函數是SWITCH，它負責線程之間的切換。 Scheduler類用于實現線程的調度。它維護一個就緒線程隊列，當一個線程可以占用處理機時，就

29、可以調用ReadyToRun方法把這個線程放入就緒線程隊列，并把線程狀態改成就緒態。FindNextToRun方法根據調度策略，取出下一個應運行的線程，并把這個線程從就緒線程隊列中刪除。如果就緒線程隊列為空，則此函數返回空(NULL)。現有的調度策略是先進先出策略(FIFO)，Thread類的對象既用作線程的控制塊，相當于進程管理中的PCB，作用是保存線程狀態、進行一些統計，又是用戶調用線程系統的界面。用戶生成一個新線程的方法是:Thread* newThread = new Thread(New Thread);/ 生成一個線程類newThread-Fork(ThreadFunc，Threa

30、dFuncArg);/ 定義新線程的執行函數及其參數 Fork方法分配一塊固定大小的內存作為線程的堆棧，在棧頂放入ThreadRoot的地址。當新線程被調上CPU時，要用SWITCH函數切換線程圖像，SWITCH函數返回時，會從棧頂取出返回地址，于是將ThreadRoot放在棧頂，在SWITCH結束后就會立即執行ThreadRoot函數。ThreadRoot是所有線程的入口，它會調用Fork的兩個參數，運行用戶指定的函數；Yield方法用于本線程放棄處理機。Sleep方法可以使當前線程轉入阻塞態，并放棄CPU，直到被另一個線程喚醒，把它放回就緒線程隊列。在沒有就緒線程時，就把時鐘前進到一個中斷

31、發生的時刻，讓中斷發生并處理此中斷，這是因為在沒有線程占用CPU時，只有中斷處理程序可能喚醒一個線程，并把它放入就緒線程隊列。線程要等到本線程被喚醒后，并且又被線程調度模塊調上CPU時，才會從Sleep函數返回。有趣的是，新取出的就緒線程有可能就是這個要睡眠的線程。例如，如果系統中只有一個A線程，A線程在讀磁盤的時候會進入睡眠，等待磁盤操作完成。因為這時只有一個線程，所以A線程不會被調下CPU，只是在循環語句中等待中斷。當磁盤操作完成時，磁盤會發出一個磁盤讀操作中斷，此中斷將喚醒A線程，把它放入就緒隊列。這樣，當A線程跳出循環時，取出的就緒線程就是自己。這就要求線程的正文切換程序可以將一個線程

32、切換到自己， Nachos的線程正文切換程序SWITCH可以做到這一點，于是A線程實際上并沒有被調下CPU，而是繼續運行下去了。Nachos線程管理系統的初步實現1. 工具模塊分析（文件）工具模塊定義了一些在Nachos設計中有關的工具函數，和整個系統的設計沒有直接的聯系，所以這里僅作一個簡單的介紹。List類在Nachos中廣泛使用，它定義了一個鏈表結構，有關List的數據結構和實現如下所示：class ListElement /定義了List中的元素類型 public: ListElement(void *itemPtr, int sortKey);/初始化方法 ListElement *

33、next;/指向下一個元素的指針 int key; /對應于優先隊列的鍵值 void *item; /實際有效的元素指針;其中，實際有效元素指針是(void *)類型的，說明元素可以是任何類型。class List public:List();/初始化方法List();/析構方法void Prepend(void *item);/將新元素增加在鏈首void Append(void *item); /將新元素增加在鏈尾void *Remove(); /刪除鏈首元素并返回該元素void Mapcar(VoidFunctionPtr func);/將函數func作用在鏈中每個元素上bool IsEm

34、pty();/判斷鏈表是否為空void SortedInsert(void *item, int sortKey);/將元素根據key值優先權插入到鏈中void *SortedRemove(int *keyPtr); /將key值最小的元素從鏈中刪除，/并返回該元素 private: ListElement *first; /鏈表中的第一個元素 ListElement *last;/鏈表中的最后一個元素;其它的工具函數如min和max以及一些同調試有關的函數，這里就不再贅述。2. 線程啟動和調度模塊分析（文件）線程啟動和線程調度是線程管理的重點。在Nachos中，線程是最小的調度單位，在同一時

35、間內，可以有幾個線程處于就緒狀態。Nachos的線程切換借助于宿主機的正文切換，由于這部分內容與機器密切相關，而且直接同宿主機的寄存器進行交道，所以這部分是用匯編來實現的。由于Nachos可以運行在多種機器上，不同機器的寄存器數目和作用不一定相同，所以在中針對不同的機器進行了不同的處理。讀者如果需要將Nachos移植到其它機器上，就需要修改這部分的內容。2.1 ThreadRoot函數Nachos中，除了main線程外，所有其它線程都是從ThreadRoot入口運行的。它的語法是：ThreadRoot (int InitialPC, int InitialArg, int WhenDonePC

36、, int StartupPC)其中，InitialPC指明新生成線程的入口函數地址，InitialArg是該入口函數的參數；StartupPC是在運行該線程是需要作的一些初始化工作，比如開中斷；而WhenDonePC是當該線程運行結束時需要作的一些后續工作。在Nachos的源代碼中，沒有任何一個函數和方法顯式地調用ThreadRoot函數，ThreadRoot函數只有在線程切換時才被調用到。一個線程在其初始化的最后準備工作中調用StackAllocate方法（見本章），該方法設置了幾個寄存器的值（InterruptEnable函數指針，ThreadFinish函數指針以及該線程需要運行函數的

37、函數指針和運行函數的參數） ，該線程第一次被切換上處理機運行時調用的就是ThreadRoot函數。其工作過程是：1. 調用 StartupPC 函數；2. 調用 InitialPC 函數；3. 調用 WhenDonePC 函數；這里我們可以看到，由ThreadRoot入口可以轉而運行線程所需要運行的函數，從而達到生成線程的目的。2.2 SWITCH函數Nachos中系統線程的切換是借助宿主機的正文切換。SWITCH函數就是完成線程切換的功能。SWITCH的語法是這樣的：void SWITCH (Thread *t1, Thread *t2);其中t1是原運行線程指針，t2是需要切換到的線程指針

38、。線程切換的三步曲是：1. 保存原運行線程的狀態2. 恢復新運行線程的狀態3. 在新運行線程的棧空間上運行新線程3. 線程模塊分析（文件）Thread類實現了操作系統的線程控制塊，同操作系統課程中進程程管理中的PCB (Process Control Block) 有相似之處。Thread線程控制類較PCB為簡單的多，它沒有線程標識 (pid)、實際用戶標識 (uid)等和線程操作不是非常有聯系的部分，也沒有將PCB分成proc結構和user結構。這是因為一個Nachos線程是在宿主機上運行的。無論是系統線程和用戶進程，Thread線程控制類的實例都生成在宿主機而不是生成在虛擬機上。所以不存在

39、實際操作系統中proc結構常駐內存，而user結構可以存放在盤交換區上的情況，將原有的兩個結構合并是Nachos作的一種簡化。Nachos對線程的另一個簡化是每個線程棧段的大小是固定的，為4096-5個字 (word)，而且是不能動態擴展的。所以Nachos中的系統線程中不能使用很大的棧空間，比如：void foo () int buff10000; .可能會不能正常執行，如果需要使用很大空間，可以在Nachos的運行堆中申請：void foo () int *buf = new int10000; .如果系統線程需要使用的棧空間大于規定棧空間的大小，可以修改StackSize宏定義。Thre

40、ad類的定義和實現如下所示：class Thread private:int* stackTop; /當前堆棧指針int machineStateMachineStateSize; /宿主機的運行寄存器 public:Thread(char* debugName);/初始化線程Thread(); /析構方法void Fork(VoidFunctionPtr func, int arg); /生成一個新線程，執行func(arg)void Yield(); /切換到其它線程運行void Sleep(); /線程進入睡眠狀態void Finish(); /線程結束時調用void CheckOver

41、flow(); /測試線程棧段是否溢出void setStatus(ThreadStatus st);/設置線程狀態char* getName() return (name); /取得線程名（調試用）void Print() printf(%s, , name); /打印當前線程名（調試用） private:int* stack;/線程的棧底指針ThreadStatus status;/當前線程狀態char* name;/線程名（調試用）void StackAllocate(VoidFunctionPtr func, int arg);/申請線程的棧空間#ifdef USER_PROGRAMi

42、nt userRegistersNumTotalRegs;/虛擬機的寄存器組 public:void SaveUserState();/線程切換時保存虛擬機寄存器void RestoreUserState();/線程切換時恢復虛擬機寄存器組AddrSpace *space;/線程運行的用戶程序#endif線程狀態有四種，狀態之間的轉換如圖3.6所示：Nachos線程的狀態轉換運行結束等待的事件發生等待某事件發生初始化結束處理機調度運行被迫放棄處理機運行態阻塞態初啟態就緒態初啟態用戶進程在線程切換的時候，除了需要保存宿主機的狀態外，必須還要保存虛擬機的寄存器狀態。UserRegisters數組變

43、量和SaveUserState(), RestoreUserState()方法就是為了用戶進程的切換設計的。Fork 方法 語法：void Fork (VoidFunctionPtr func, int arg) 參數：func:新線程運行的函數arg:func函數的參數 功能：線程初始化之后將線程設置成可運行的。 實現：1. 申請線程棧空間2. 初始化該棧空間，使其滿足SWITCH函數進行線程切換的條件3. 將該線程放到就緒隊列中。 返回：空StackAllocate 方法 語法：void StackAllocate (VoidFunctionPtr func, int arg) 參數：fu

44、nc:新線程運行的函數arg:func函數的參數 功能：為一個新線程申請棧空間，并設置好準備運行線程的條件。 實現：void Thread:StackAllocate (VoidFunctionPtr func, int arg)stack = (int *) AllocBoundedArray(StackSize * sizeof(int);/申請線程的棧空間stackTop = stack + StackSize - 4;/設置棧首指針*(-stackTop) = (int)ThreadRoot;/線程準備好運行后進行線程切換，會切換到ThreadRoot函數。ThreadRoot函數/將

45、會開中斷，并調用func(arg)成為一個獨立的調度單位。*stack = STACK_FENCEPOST;/設置棧溢出標志 machineStatePCState = (int) ThreadRoot;/設置PC指針，從ThreadRoot開始運行 machineStateStartupPCState = (int) InterruptEnable; machineStateInitialPCState = (int) func; machineStateInitialArgState = arg; machineStateWhenDonePCState = (int) ThreadFini

46、sh;/以上是為ThreadRoot作好準備，ThreadRoot將分別調用InterruptEnable，/func(arg)和ThreadFinish。 返回：空4. 線程調度算法模塊分析（文件）該模塊的作用是進行線程的調度。在Nachos系統中，有一個線程就緒隊列，其中是所有就緒線程。調度算法非常簡單，就是取出第一個放在處理機運行即可。由于Nachos中線程沒有優先級，所以線程就緒隊列是沒有優先級的。讀者可以在這一點上進行加強，實現有優先級的線程調度。4.1 Run方法語法：void Run (Thread *nextThread)參數：nextThread:需要切換運行的線程功能：當前

47、運行強制切換到nextThread就緒線程運行實現：1. 如果是用戶線程，保存當前虛擬機的狀態2. 檢查當前運行線程棧段是否溢出。（由于不是每時每刻都檢查棧段是否溢出，所以這時候線程的運行可能已經出錯）3. 將nextThread的狀態設置成運行態，并作為currentThread現運行線程（在調用Run方法之前，當前運行線程已經放入就緒隊列中，變成就緒態）（以上是運行在現有的線程棧空間上，以下是運行在nextThread的棧空間上）4. 切換到nextThread線程運行5. 釋放threadToBeDestroyed線程需要棧空間（如果有的話）6. 如果是用戶線程，恢復當前虛擬機的狀態 返

48、回：空5.Nachos主控模塊分析（文件）該模塊是整個Nachos系統的入口，它分析了Nachos的命令行參數，根據不同的選項進行不同功能的初始化設置。選項的設置如下所示：一般選項：-d:顯示特定的調試信息-rs:使得線程可以隨機切換-z:打印版權信息和用戶進程有關的選項：-s:使用戶進程進入單步調試模式-x:執行一個用戶程序-c:測試終端輸入輸出和文件系統有關的選項：-f:格式化模擬磁盤-cp:將一個文件從宿主機拷貝到Nachos模擬磁盤上-p:將Nachos磁盤上的文件顯示出來-r:將一個文件從Nachos模擬磁盤上刪除-l:列出Nachos模擬磁盤上的文件-D:打印出Nachos文件系統

49、的內容-t:測試Nachos文件系統的效率和網絡有關的選項：-n:設置網絡的可靠度（在0-1之間的一個小數）-m:設置自己的HostID-o:執行網絡測試程序6. 同步機制模塊分析（文件）線程的同步和互斥是多個線程協同工作的基礎。Nachos提供了三種同步和互斥的手段：信號量、鎖機制以及條件變量機制，提供三種同步互斥機制是為了用戶使用方便。在同步互斥機制的實現中，很多操作都是原子操作。Nachos是運行在單一處理器上的操作系統，在單一處理器上，實現原子操作只要在操作之前關中斷即可，操作結束后恢復原來中斷狀態。6.1 信號量 ( Semaphore )Nachos已經實現了Semaphore，它

50、的基本結構如下所示：class Semaphore public:void P(); /信號量的P操作void V(); /信號量的V操作 private:int value; /信號量值 ( =0)List *queue; /線程等待隊列;信號量的私有屬性有信號量的值，它是一個閥門。線程等待隊列中存放所有等待該信號量的線程。信號量有兩個操作：P操作和V操作，這兩個操作都是原子操作。6.1.1 P操作1. 當value等于0時，1.1. 將當前運行線程放入線程等待隊列。1.2. 當前運行線程進入睡眠狀態，并切換到其它線程運行。2. 當value大于0時，value-。 V操作1. 如果線程等待

51、隊列中有等待該信號量的線程，取出其中一個將其設置成就緒態，準備運行。2. value+;6.2 鎖機制鎖機制是線程進入臨界區的工具。一個鎖有兩種狀態，BUSY和FREE。當鎖處于FREE態時，線程可以取得該鎖后進入臨界區，執行完臨界區操作之后，釋放鎖；當鎖處于BUSY態時，需要申請該鎖的線程進入睡眠狀態，等到鎖為FREE態時，再取得該鎖。鎖的基本結構如下所示：class Lock public:Lock(char* debugName); /初始化方法Lock();/析構方法char* getName() return name; /取出鎖名（調試用）void Acquire(); /獲得鎖方

52、法void Release(); /釋放鎖方法bool isHeldByCurrentThread();/判斷鎖是否為現運行線程擁有 private:char* name;/鎖名（調試用）;在現有的Nachos中，沒有給出鎖機制的實現，鎖的基本結構也只給出了部分內容，其它內容可以視實現決定。總體來說，鎖有兩個操作Acquire和Release，它們都是原子操作。6.3條件變量條件變量和信號量與鎖機制不一樣，它是沒有值的。（實際上，鎖機制是一個二值信號量，可以通過信號量來實現）當一個線程需要的某種條件沒有得到滿足時，可以將自己作為一個等待條件變量的線程插入所有等待該條件變量的隊列；只要條件一旦滿足，該線程就會被喚醒繼續運行。條件變量總是和鎖機制一同使用，它的基本結構如下：class Condition public:Condition(char* debugName);/初始化方法Condition();/析構方法char* getName() return (name); /取出條件變量名（調試用）void Wait(Lock *conditionLock); /線程進入等待 void Signal(Lock *conditionLock); /喚醒一個等待該條件變量線程void Broadcast(L