nachos線程通信和調度分析操作系統(tǒng)課程設計

1、<p><b>　　操作系統(tǒng)課程設計</b></p><p><b>　　說 明 書</b></p><p>　　學 院： 信息科學與工程學院 </p><p>　　一、 理解Nachos模擬的物理機的運行機制3</p><p>　　1. Sysdep模塊

2、分析（文件sysdep.cc sysdep.h）5</p><p>　　2.中斷模塊分析（文件interrupt.cc interrupt.h）10</p><p>　　3. 時鐘中斷模塊分析（文件timer.cc timer.h）16</p><p>　　4. 終端設備模塊分析（文件console.cc console.h）18</p>&

3、lt;p>　　二、 理解Nachos中線程運行機制19</p><p>　　1. 工具模塊分析（文件list.cc list.h utility.cc utility.h）20</p><p>　　2. 線程啟動和調度模塊分析（文件switch.s switch.h）21</p><p>　　3. 線程模塊分析（文件thread.cc thread.h）

4、22</p><p>　　4. 線程調度算法模塊分析（文件scheduler.cc scheduler.h）26</p><p>　　5.Nachos主控模塊分析（文件main.cc system.cc system.h）27</p><p>　　6. 同步機制模塊分析（文件synch.cc synch.h）28</p><p>　

5、　三、 理解Nachos中支持用戶進程的機制30</p><p>　　一、用戶程序空間（文件address.cc, address.h）35</p><p>　　二、系統(tǒng)調用（文件exception.cc, syscall.h, start.s）36</p><p>　　理解Nachos模擬的物理機的運行機制</p><p>　　Mac

6、hine類用來模擬計算機主機。它提供的功能有：讀寫寄存器。讀寫主存、運行一條用戶程序的匯編指令、運行用戶程序、單步調試用戶程序、顯示主存和寄存器狀態(tài)、將虛擬內存地址轉換為物理內存地址、陷入 Nachos 內核等等。</p><p>　　Machine類實現方法是在宿主機上分配兩塊內存分別作為虛擬機的寄存器和物理內存。運行用戶程序時，先將用戶程序從 Nachos 文件系統(tǒng)中讀出，寫入模擬的物理內存中，然后調用指令模

7、擬模塊對每一條用戶指令解釋執(zhí)行。將用戶程序的讀寫內存要求，轉變?yōu)閷ξ锢韮却娴刂返淖x寫。Machine類提供了單步調試用戶程序的功能，執(zhí)行一條指令后會自動停下來，讓用戶查看系統(tǒng)狀態(tài)，不過這里的單步調試是匯編指令級的，需要讀者對R2/3000指令比較熟悉。如果用戶程序想使用操作系統(tǒng)提供的功能或者發(fā)出異常信號時，Machine調用系統(tǒng)異常陷入功能，進入Nachos的核心部分。</p><p>　　Interrupt類用

8、來模擬硬件中斷系統(tǒng)。在這個中斷系統(tǒng)中，中斷狀態(tài)有開，關兩種，中斷類型有時鐘中斷、磁盤中斷、控制臺寫中斷、控制臺讀中斷、網絡發(fā)送中斷以及網絡接收中斷。機器狀態(tài)有用戶態(tài)，核心態(tài)和空閑態(tài)。中斷系統(tǒng)提供的功能有開/關中斷，讀/寫機器狀態(tài)，將一個即將發(fā)生中斷放入中斷隊列，以及使機器時鐘前進一步。</p><p>　　在Interrupt類中有一個記錄即將發(fā)生中斷的隊列，稱為中斷等待隊列。中斷等待隊列中每個等待處理的中斷包含

9、中斷類型、中斷處理程序的地址及參數、中斷應當發(fā)生的時間等信息。一般是由硬件設備模擬程序把將要發(fā)生的中斷放入中斷隊列。中斷系統(tǒng)提供了一個模擬機器時鐘，機器時鐘在下列情況下前進：</p><p><b>　　用戶程序打開中斷</b></p><p><b>　　執(zhí)行一條用戶指令</b></p><p>　　處理機沒有進程正在運

10、行</p><p>　　機器時鐘前進時，中斷處理的過程如下圖所示:</p><p>　　中斷系統(tǒng)成為整個Nachos虛擬機的基礎，其它的模擬硬件設備都是建立在中斷系統(tǒng)之上的。在此之上，加上Machine類模擬的指令解釋器，可以實現Nachos的線程管理、文件系統(tǒng)管理、虛擬內存、用戶程序和網絡管理等所有操作系統(tǒng)功能。下圖展示了Nachos系統(tǒng)的整體結構。</p><p&g

11、t;　　Nachos系統(tǒng)的整體結構</p><p><b>　　機器模擬的實現：</b></p><p>　　1. Sysdep模塊分析（文件sysdep.cc sysdep.h）</p><p>　　Nachos的運行環(huán)境可以是多種操作系統(tǒng)，由于每種操作系統(tǒng)所提供的系統(tǒng)調用或函數調用在形式和內容上可能有細微的差別。sysdep模塊的作用是屏蔽

12、掉這些差別。</p><p>　　1.1 PoolFile 函數</p><p>　　1.2 OpenForWrite 函數</p><p>　　1.3 OpenForReadWrite 函數</p><p>　　1.4 Read 函數</p><p>　　1.5 ReadPartial 函數</p>&

13、lt;p>　　1.6 WriteFile 函數</p><p>　　1.7 Lseek 函數</p><p>　　1.8 Tell 函數</p><p>　　1.9 Close 函數</p><p>　　1.10 Unlink 函數</p><p>　　1.11 OpenSocket 函數</p>

14、<p>　　1.12 CloseSocket 函數</p><p>　　1.13 Abort 函數</p><p>　　1.14 Exit 函數</p><p>　　2.中斷模塊分析（文件interrupt.cc interrupt.h）</p><p>　　中斷模塊的主要作用是模擬底層的中斷機制。可以通過該模擬機制來啟動和禁止中

15、斷 (SetLevel)；該中斷機制模擬了Nachos系統(tǒng)需要處理的所有的中斷，包括時鐘中斷、磁盤中斷、終端讀/終端寫中斷以及網絡接收/網絡發(fā)送中斷。</p><p>　　中斷的發(fā)生總是有一定的時間。比如當向硬盤發(fā)出讀請求，硬盤處理請求完畢后會發(fā)生中斷；在請求和處理完畢之間需要經過一定的時間。所以在該模塊中，模擬了時鐘的前進。為了實現簡單和便于統(tǒng)計各種活動所占用的時間起見，Nachos規(guī)定系統(tǒng)時間在以下三種情況下

16、前進：</p><p>　　執(zhí)行用戶態(tài)指令，時鐘前進是顯而易見的。我們認為，Nachos執(zhí)行每條指令所需時間是固定的，為一個時鐘單位(Tick)。</p><p>　　一般系統(tǒng)態(tài)在進行中斷處理程序時，需要關中斷。但是中斷處理程序本身也需要消耗時間，而在關閉中斷到重新打開中斷之間無法非常準確地計算時間，所以當中斷重新打開的時候，加上一個中斷處理所需時間的平均值。</p><

17、;p>　　當系統(tǒng)中沒有就緒進程時，系統(tǒng)處于Idle狀態(tài)。這種狀態(tài)可能是系統(tǒng)中所有的進程都在等待各自的某種操作完成。也就是說，系統(tǒng)將在未來某個時間發(fā)生中斷，到中斷發(fā)生的時候中斷處理程序將進行中斷處理。在系統(tǒng)模擬中，有一個中斷等待隊列，專門存放將來發(fā)生的中斷。在這種情況下，可以將系統(tǒng)時間直接跳到中斷等待隊列第一項所對應的時間，以免不必要的等待。</p><p>　　當前面兩種情況需要時鐘前進時，調用OneTic

18、k方法。OneTick方法將系統(tǒng)態(tài)和用戶態(tài)的時間分開進行處理，這是因為用戶態(tài)的時間計算是根據用戶指令為單位的；而在系統(tǒng)態(tài)，沒有辦法進行指令的計算，所以將系統(tǒng)態(tài)的一次中斷調用或其它需要進行時間計算的單位設置為一個固定值，假設為一條用戶指令執(zhí)行時間的10倍。</p><p>　　雖然Nachos模擬了中斷的發(fā)生，但是畢竟不能與實際硬件一樣，中斷發(fā)生的時機可以是任意的。比如當系統(tǒng)中沒有就緒進程時，時鐘直接跳到未處理中斷

19、隊列的第一項的時間。這實際情況下，系統(tǒng)處于Idel狀態(tài)到中斷等待隊列第一項發(fā)生時間之間，完全有可能有其它中斷發(fā)生。由于中斷發(fā)生的時機不是完全隨機的，所以在Nachos系統(tǒng)中運行的程序，不正確的同步程序也可能正常運行，我們在此需要密切注意。</p><p>　　Nachos線程運行有三種狀態(tài)：</p><p><b>　　Idle狀態(tài)</b></p>&l

20、t;p>　　系統(tǒng)CPU處于空閑狀態(tài)，沒有就緒線程可以運行。如果中斷等待隊列中有需要處理的除了時鐘中斷以外的中斷，說明系統(tǒng)還沒有結束，將時鐘調整到發(fā)生中斷的時間，進行中斷處理；否則認為系統(tǒng)結束所有的工作，退出。</p><p><b>　　系統(tǒng)態(tài)</b></p><p>　　Nachos執(zhí)行系統(tǒng)程序。Nachos雖然模擬了虛擬機的內存，但是Nachos系統(tǒng)程序本身

21、的運行不是在該模擬內存中，而是利用宿主機的存儲資源。這是Nachos操作系統(tǒng)同真正操作系統(tǒng)的重要區(qū)別。</p><p><b>　　用戶態(tài)</b></p><p>　　系統(tǒng)執(zhí)行用戶程序。當執(zhí)行用戶程序時，每條指令占用空間是Nachos的模擬內存。</p><p>　　中斷等待隊列是Nachos虛擬機最重要的數據結構之一，它記錄了當前虛擬機可以預

22、測的將在未來發(fā)生的所有中斷。當系統(tǒng)進行了某種操作可能引起未來發(fā)生的中斷時，如磁盤的寫入、向網絡寫入數據等都會將中斷插入到中斷等待隊列中；對于一些定期需要發(fā)生的中斷，如時鐘中斷、終端讀取中斷等，系統(tǒng)會在中斷處理后將下一次要發(fā)生的中斷插入到中斷等待隊列中。中斷的插入過程是一個優(yōu)先隊列的插入過程，其優(yōu)先級是中斷發(fā)生的時間，也就是說，先發(fā)生的中斷將優(yōu)先得到處理。</p><p>　　當時鐘前進或者系統(tǒng)處于Idle狀態(tài)時，

23、Nachos會判斷中斷等待隊列中是否有</p><p>　　要發(fā)生的中斷，如果有中斷需要發(fā)生，則將該中斷從中斷等待隊列中刪除，調用相應的中斷處理程序進行處理。中斷處理程序是在某種特定的中斷發(fā)生時被調用，中斷處理程序的作用包括可以在現有的模擬硬件的基礎上建立更高層次的抽象。比如現有的模擬網絡是有丟失幀的不安全網絡，在中斷處理程序中可以加入請求重發(fā)機制來實現一個安全網絡。</p><p>　　

24、2.1 PendingInterrupt類</p><p>　　class PendingInterrupt {</p><p><b>　　public:</b></p><p>　　PendingInterrupt (VoidFunctionPtr func, int param, int time, IntType kind);</

25、p><p>　　VoidFunctionPtr handler;// 中斷對應的中斷處理程序</p><p>　　int arg;// 中斷處理程序的參數</p><p>　　int when;// 中斷發(fā)生的時機</p><p>　　IntType type;// 中斷的類型，供調試用&l

26、t;/p><p><b>　　};</b></p><p>　　這個類定義了一個中斷等待隊列中需要處理的中斷。為了方便起見，所有類的數據和成員函數都設置為public的，不需要其它的Get和Set等存取內部數據的函數。初始化函數就是為對應的參數賦值。</p><p>　　2.2 Interrupt類</p><p>　　cl

27、ass Interrupt {</p><p>　　public:// 以下函數是Interrupt的對外接口</p><p>　　Interrupt();// 初始化中斷模擬</p><p>　　~Interrupt();// 終止中斷模擬</p><p>　　IntStatus SetLevel(IntSta

28、tus level);</p><p>　　// 開關中斷，并且返回之前的狀態(tài)</p><p>　　void Enable();// 開中斷</p><p>　　IntStatus getLevel() {return level;}</p><p>　　// 取回當前中斷的開關狀態(tài)</p><p>　　voi

29、d Idle(); // 當進程就緒隊列為空時，執(zhí)行該函數</p><p>　　void Halt(); // 退出系統(tǒng)，并打印狀態(tài)</p><p>　　void YieldOnReturn();// 設置中斷結束后要進行進程切換的標志</p><p>　　MachineStatus getStatus() { return status; }&

30、lt;/p><p>　　// 返回系統(tǒng)當前的狀態(tài)</p><p>　　void setStatus(MachineStatus st) { status = st; }</p><p>　　// 設置系統(tǒng)當前的狀態(tài)</p><p>　　void DumpState();// 調試當前中斷隊列狀態(tài)用</p><p>　

31、　void Schedule(VoidFunctionPtr handler, int arg, int when, IntType type);// 在中斷等待隊列中，增加一個等待中斷</p><p>　　void OneTick(); // 模擬時鐘前進</p><p>　　private:// 以下是內部數據和內部處理方法</p&g

32、t;<p>　　IntStatus level;// 中斷的開關狀態(tài)</p><p>　　List *pending;// 當前系統(tǒng)中等待中斷隊列</p><p>　　bool inHandler;// 是否正在進行中斷處理標志</p><p>　　bool yieldOnReturn; // 中斷處理后是否需要正文切換標志

33、</p><p>　　MachineStatus status;// 當前虛擬機運行狀態(tài)</p><p>　　bool CheckIfDue(bool advanceClock);</p><p>　　// 檢查當前時刻是否有要處理的中斷</p><p>　　void ChangeLevel(IntStatus old, IntStat

34、us now);</p><p>　　// 改變當前中斷的開關狀態(tài)，但不前進模擬時鐘</p><p><b>　　};</b></p><p>　　其中，Schedule和 OneTick兩個方法雖然標明是public的，但是除了虛擬機模擬部分以外的其它類方法是不能調用這兩個方法的。將它們設置成public的原因是因為虛擬機模擬的其它類方法需要

35、直接調用這兩個方法。</p><p>　　3. 時鐘中斷模塊分析（文件timer.cc timer.h）</p><p>　　該模塊的作用是模擬時鐘中斷。Nachos虛擬機可以如同實際的硬件一樣，每隔一定的時間會發(fā)生一次時鐘中斷。這是一個可選項，目前Nachos還沒有充分發(fā)揮時鐘中斷的作用，只有在Nachos指定線程隨機切換時，（Nachos -rs參數，見線程管理部分Nachos主控模塊

36、分析）啟動時鐘中斷，在每次的時鐘中斷處理的最后，加入了線程的切換。實際上，時鐘中斷在線程管理中的作用遠不止這些，時鐘中斷還可以用作：</p><p>　　線程管理中的時間片輪轉法的時鐘控制，（詳見線程管理系統(tǒng)中的實現實例中，對線程調度的改進部分）不一定每次時鐘中斷都會引起線程的切換，而是由該線程是否的時間片是否已經用完來決定。</p><p>　　分時系統(tǒng)線程優(yōu)先級的計算（詳見線程管理系統(tǒng)

37、中的實現實例中，對線程調度的改進部分）</p><p>　　線程進入睡眠狀態(tài)時的時間計算</p><p>　　可以通過時鐘中斷機制來實現sleep系統(tǒng)調用，在時鐘中斷處理程序中，每隔一定的時間對定時睡眠線程的時間進行一次評估，判斷是否需要喚醒它們。</p><p>　　Nachos利用其模擬的中斷機制來模擬時鐘中斷。時鐘中斷間隔由TimerTicks宏決定（100倍

38、Tick的時間）。在系統(tǒng)模擬時有一個缺陷，如果系統(tǒng)就緒進程不止一個的話，每次時鐘中斷都一定會發(fā)生進程的切換（見system.cc中TimerInterruptHandler函數）。所以運行Nachos時，如果以同樣的方式提交進程，系統(tǒng)的結果將是一樣的。這不符合操作系統(tǒng)的運行不確定性的特性。所以在模擬時鐘中斷的時候，加入了一個隨機因子，如果該因子設置的話，時鐘中斷發(fā)生的時機將在一定范圍內是隨機的。這樣有些用戶程序在同步方面的錯誤就比較容易

39、發(fā)現。但是這樣的時鐘中斷和真正操作系統(tǒng)中的時鐘中斷將有不同的含義。不能象真正的操作系統(tǒng)那樣通過時鐘中斷來計算時間等等。是否需要隨機時鐘中斷可以通過設置選項(-rs)來實現。</p><p>　　Timer類的實現很簡單，當生成出一個Timer類的實例時，就設計了一個模擬的時鐘中斷。這里考慮的問題是：怎樣實現定期發(fā)生時鐘中斷？</p><p>　　在Timer的初始化函數中，借用TimerH

40、andler內部函數（見第1行）。為什么不直接用初始化函數中的timerHandler參數作為中斷處理函數呢？因為如果直接使用timerHandler作為時鐘中斷處理函數，第8行是將一個時鐘中斷插入等待處理中斷隊列，一旦中斷時刻到來，立即進行中斷處理，處理結束后并沒有機會將下一個時鐘中斷插入到等待處理中斷隊列。TimerHandler內部函數正是處理這個問題。當時鐘中斷時刻到來時，調用TimerHandler函數，其調用TimerExp

41、ired方法，該方法將新的時鐘中斷插入到等待處理中斷隊列中，然后再調用真正的時鐘中斷處理函數。這樣Nachos就可以定時的收到時鐘中斷。</p><p>　　那么為什么不將TimerExpired方法作為時鐘中斷在Timer的初始化函數中調用呢？這是由于C++語言不能直接引用一個類內部方法的指針，所以借用TimerHandler內部函數。這也是TimerExpired必須設計成public的方法的原因，因為它要被

42、TimerHandler調用。</p><p>　　這樣的方法不僅僅在Timer模擬時鐘中斷中用到，所有需要定期發(fā)生的中斷都可以采用這樣的方法，如Nachos需要定期地檢查是否有終端的輸入、網絡是否有發(fā)給自己的報文等都是用這種方式實現。詳見 network.cc 以及console.cc。</p><p>　　TimeOfextInterrupt()方法的作用是計算下一次時鐘中斷發(fā)生的時機

43、，如果需要時鐘中斷發(fā)生的時機是隨機的，可以在Nachos命令行中設置 –rs 選項。這樣，Nachos的線程切換的時機將會是隨機的。但是此時時鐘中斷則不能作為系統(tǒng)計時的標準了。</p><p>　　理解Nachos中線程運行機制</p><p>　　Nachos中的系統(tǒng)線程和用戶進程</p><p>　　Nachos為線程提供的功能函數有:</p>&

44、lt;p>　　生成一個線程(Fork)</p><p>　　使線程睡眠等待(Sleep)</p><p>　　結束線程(Finish)</p><p>　　設置線程狀態(tài)(setStatus)</p><p>　　放棄處理機(Yield)</p><p>　　線程系統(tǒng)的結構如圖所示:</p><

45、p>　　Nachos線程系統(tǒng)的結構</p><p>　　線程管理系統(tǒng)中，有兩個與機器相關的函數，正文切換過程依賴于具體的機器，這是因為系統(tǒng)線程切換是借助于宿主機的正文切換，正文切換過程中的寄存器保護，建立初始調用框架等操作對不同的處理機結構是不一樣的。其中一個函數是ThreadRoot，它是所有線程運行的入口；另一個函數是SWITCH，它負責線程之間的切換。 Scheduler類用于實現線程的調度。它

46、維護一個就緒線程隊列，當一個線程可以占用處理機時，就可以調用ReadyToRun方法把這個線程放入就緒線程隊列，并把線程狀態(tài)改成就緒態(tài)。FindNextToRun方法根據調度策略，取出下一個應運行的線程，并把這個線程從就緒線程隊列中刪除。如果就緒線程隊列為空，則此函數返回空(NULL)?，F有的調度策略是先進先出策略(FIFO)，</p><p>　　Thread類的對象既用作線程的控制塊，相當于進程管理中的PCB

47、，作用是保存線程狀態(tài)、進行一些統(tǒng)計，又是用戶調用線程系統(tǒng)的界面。</p><p>　　用戶生成一個新線程的方法是:</p><p>　　Thread* newThread = new Thread("New Thread");// 生成一個線程類</p><p>　　newThread->Fork(ThreadFunc，ThreadFunc

48、Arg);// 定義新線程的執(zhí)行函數及其參數 </p><p>　　Fork方法分配一塊固定大小的內存作為線程的堆棧，在棧頂放入ThreadRoot的地址。當新線程被調上CPU時，要用SWITCH函數切換線程圖像，SWITCH函數返回時，會從棧頂取出返回地址，于是將ThreadRoot放在棧頂，在SWITCH結束后就會立即執(zhí)行ThreadRoot函數。ThreadRoot是所有線程的入口，它會調用Fork的兩個

49、參數，運行用戶指定的函數；Yield方法用于本線程放棄處理機。Sleep方法可以使當前線程轉入阻塞態(tài)，并放棄CPU，直到被另一個線程喚醒，把它放回就緒線程隊列。在沒有就緒線程時，就把時鐘前進到一個中斷發(fā)生的時刻，讓中斷發(fā)生并處理此中斷，這是因為在沒有線程占用CPU時，只有中斷處理程序可能喚醒一個線程，并把它放入就緒線程隊列。</p><p>　　線程要等到本線程被喚醒后，并且又被線程調度模塊調上CPU時，才會從S

50、leep函數返回。有趣的是，新取出的就緒線程有可能就是這個要睡眠的線程。例如，如果系統(tǒng)中只有一個A線程，A線程在讀磁盤的時候會進入睡眠，等待磁盤操作完成。因為這時只有一個線程，所以A線程不會被調下CPU，只是在循環(huán)語句中等待中斷。當磁盤操作完成時，磁盤會發(fā)出一個磁盤讀操作中斷，此中斷將喚醒A線程，把它放入就緒隊列。這樣，當A線程跳出循環(huán)時，取出的就緒線程就是自己。這就要求線程的正文切換程序可以將一個線程切換到自己， Nachos的線程正

51、文切換程序SWITCH可以做到這一點，于是A線程實際上并沒有被調下CPU，而是繼續(xù)運行下去了。</p><p>　　Nachos線程管理系統(tǒng)的初步實現</p><p>　　1. 工具模塊分析（文件list.cc list.h utility.cc utility.h）</p><p>　　工具模塊定義了一些在Nachos設計中有關的工具函數，和整個系統(tǒng)的設計沒有直接

52、的聯系，所以這里僅作一個簡單的介紹。</p><p>　　List類在Nachos中廣泛使用，它定義了一個鏈表結構，有關List的數據結構和實現如下所示：</p><p>　　class ListElement {//定義了List中的元素類型</p><p><b>　　public:</b></p><p&

53、gt;　　ListElement(void *itemPtr, int sortKey);//初始化方法</p><p>　　ListElement *next;//指向下一個元素的指針</p><p>　　int key; //對應于優(yōu)先隊列的鍵值</p><p>　　void *item; //實際有效

54、的元素指針</p><p><b>　　};</b></p><p>　　其中，實際有效元素指針是(void *)類型的，說明元素可以是任何類型。</p><p>　　class List {</p><p><b>　　public:</b></p><p>　　List(

55、);//初始化方法</p><p>　　~List();//析構方法</p><p>　　void Prepend(void *item);//將新元素增加在鏈首</p><p>　　void Append(void *item); //將新元素增加在鏈尾</p><p>　　void *Re

56、move(); //刪除鏈首元素并返回該元素</p><p>　　void Mapcar(VoidFunctionPtr func);//將函數func作用在鏈中每個元素上</p><p>　　bool IsEmpty();//判斷鏈表是否為空</p><p>　　void SortedInsert(void *item, int s

57、ortKey);//將元素根據key值優(yōu)先權插入到鏈中</p><p>　　void *SortedRemove(int *keyPtr); //將key值最小的元素從鏈中刪除，</p><p><b>　　//并返回該元素</b></p><p><b>　　private:</b></p><

58、;p>　　ListElement *first; //鏈表中的第一個元素</p><p>　　ListElement *last;//鏈表中的最后一個元素</p><p><b>　　};</b></p><p>　　其它的工具函數如min和max以及一些同調試有關的函數，這里就不再贅述。</p><

59、;p>　　2. 線程啟動和調度模塊分析（文件switch.s switch.h）</p><p>　　線程啟動和線程調度是線程管理的重點。在Nachos中，線程是最小的調度單位，在同一時間內，可以有幾個線程處于就緒狀態(tài)。Nachos的線程切換借助于宿主機的正文切換，由于這部分內容與機器密切相關，而且直接同宿主機的寄存器進行交道，所以這部分是用匯編來實現的。由于Nachos可以運行在多種機器上，不同機器的寄存

60、器數目和作用不一定相同，所以在switch.s中針對不同的機器進行了不同的處理。讀者如果需要將Nachos移植到其它機器上，就需要修改這部分的內容。</p><p>　　2.1 ThreadRoot函數</p><p>　　Nachos中，除了main線程外，所有其它線程都是從ThreadRoot入口運行的。它的語法是：</p><p>　　ThreadRoot (

61、int InitialPC, int InitialArg, int WhenDonePC, int StartupPC)</p><p>　　其中，InitialPC指明新生成線程的入口函數地址，InitialArg是該入口函數的參數；StartupPC是在運行該線程是需要作的一些初始化工作，比如開中斷；而WhenDonePC是當該線程運行結束時需要作的一些后續(xù)工作。在Nachos的源代碼中，沒有任何一個函數和

62、方法顯式地調用ThreadRoot函數，ThreadRoot函數只有在線程切換時才被調用到。一個線程在其初始化的最后準備工作中調用StackAllocate方法（見本章3.4），該方法設置了幾個寄存器的值（InterruptEnable函數指針，ThreadFinish函數指針以及該線程需要運行函數的函數指針和運行函數的參數） ，該線程第一次被切換上處理機運行時調用的就是ThreadRoot函數。其工作過程是：</p>&

63、lt;p>　　調用 StartupPC 函數；</p><p>　　調用 InitialPC 函數；</p><p>　　調用 WhenDonePC 函數；</p><p>　　這里我們可以看到，由ThreadRoot入口可以轉而運行線程所需要運行的函數，從而達到生成線程的目的。</p><p>　　2.2 SWITCH函數</

64、p><p>　　Nachos中系統(tǒng)線程的切換是借助宿主機的正文切換。SWITCH函數就是完成線程切換的功能。SWITCH的語法是這樣的：</p><p>　　void SWITCH (Thread *t1, Thread *t2);</p><p>　　其中t1是原運行線程指針，t2是需要切換到的線程指針。線程切換的三步曲是：</p><p>　

65、　保存原運行線程的狀態(tài)</p><p>　　恢復新運行線程的狀態(tài)</p><p>　　在新運行線程的?？臻g上運行新線程</p><p>　　3. 線程模塊分析（文件thread.cc thread.h）</p><p>　　Thread類實現了操作系統(tǒng)的線程控制塊，同操作系統(tǒng)課程中進程程管理中的PCB (Process Control Blo

66、ck) 有相似之處。</p><p>　　Thread線程控制類較PCB為簡單的多，它沒有線程標識 (pid)、實際用戶標識 (uid)等和線程操作不是非常有聯系的部分，也沒有將PCB分成proc結構和user結構。這是因為一個Nachos線程是在宿主機上運行的。無論是系統(tǒng)線程和用戶進程，Thread線程控制類的實例都生成在宿主機而不是生成在虛擬機上。所以不存在實際操作系統(tǒng)中proc結構常駐內存，而user結構可

67、以存放在盤交換區(qū)上的情況，將原有的兩個結構合并是Nachos作的一種簡化。</p><p>　　Nachos對線程的另一個簡化是每個線程棧段的大小是固定的，為4096-5個字 (word)，而且是不能動態(tài)擴展的。所以Nachos中的系統(tǒng)線程中不能使用很大的?？臻g，比如：</p><p>　　void foo () { int buff[10000]; ...}</p><

68、;p>　　可能會不能正常執(zhí)行，如果需要使用很大空間，可以在Nachos的運行堆中申請：</p><p>　　void foo () { int *buf = new int[10000]; ...}</p><p>　　如果系統(tǒng)線程需要使用的?？臻g大于規(guī)定?？臻g的大小，可以修改StackSize宏定義。</p><p>　　Thread類的定義和實現如下所示：

69、</p><p>　　class Thread {</p><p><b>　　private:</b></p><p>　　int* stackTop; //當前堆棧指針</p><p>　　int machineState[MachineStateSize]; //宿主機的運行寄存器</

70、p><p><b>　　public:</b></p><p>　　Thread(char* debugName);//初始化線程</p><p>　　~Thread(); //析構方法</p><p>　　void Fork(VoidFunctionPtr func, int arg);

71、//生成一個新線程，執(zhí)行func(arg)</p><p>　　void Yield(); //切換到其它線程運行</p><p>　　void Sleep(); //線程進入睡眠狀態(tài)</p><p>　　void Finish(); //線程結束時調用</p><p>　　void C

72、heckOverflow(); //測試線程棧段是否溢出</p><p>　　void setStatus(ThreadStatus st);//設置線程狀態(tài)</p><p>　　char* getName() { return (name); }//取得線程名（調試用）</p><p>　　void Print() { printf(

73、"%s, ", name); }//打印當前線程名（調試用）</p><p><b>　　private:</b></p><p>　　int* stack;//線程的棧底指針</p><p>　　ThreadStatus status;//當前線程狀態(tài)</p><p&

74、gt;　　char* name;//線程名（調試用）</p><p>　　void StackAllocate(VoidFunctionPtr func, int arg);</p><p>　　//申請線程的?？臻g</p><p>　　#ifdef USER_PROGRAM</p><p>　　int userRegis

75、ters[NumTotalRegs];//虛擬機的寄存器組</p><p><b>　　public:</b></p><p>　　void SaveUserState();//線程切換時保存虛擬機寄存器</p><p>　　void RestoreUserState();//線程切換時恢復虛擬機寄存器組<

76、/p><p>　　AddrSpace *space;//線程運行的用戶程序</p><p><b>　　#endif</b></p><p><b>　　}</b></p><p>　　線程狀態(tài)有四種，狀態(tài)之間的轉換如圖3.6所示：</p><p>　　用戶進程在線

77、程切換的時候，除了需要保存宿主機的狀態(tài)外，必須還要保存虛擬機的寄存器狀態(tài)。UserRegisters[]數組變量和SaveUserState(), RestoreUserState()方法就是為了用戶進程的切換設計的。</p><p><b>　　Fork 方法</b></p><p>　　StackAllocate 方法</p><p>　　

78、4. 線程調度算法模塊分析（文件scheduler.cc scheduler.h）</p><p>　　該模塊的作用是進行線程的調度。在Nachos系統(tǒng)中，有一個線程就緒隊列，其中是所有就緒線程。調度算法非常簡單，就是取出第一個放在處理機運行即可。由于Nachos中線程沒有優(yōu)先級，所以線程就緒隊列是沒有優(yōu)先級的。讀者可以在這一點上進行加強，實現有優(yōu)先級的線程調度。</p><p><

79、b>　　4.1 Run方法</b></p><p>　　5.Nachos主控模塊分析（文件main.cc system.cc system.h）</p><p>　　該模塊是整個Nachos系統(tǒng)的入口，它分析了Nachos的命令行參數，根據不同的選項進行不同功能的初始化設置。選項的設置如下所示：</p><p><b>　　一般選項：&

80、lt;/b></p><p>　　-d:顯示特定的調試信息</p><p>　　-rs:使得線程可以隨機切換</p><p>　　-z:打印版權信息</p><p>　　和用戶進程有關的選項：</p><p>　　-s:使用戶進程進入單步調試模式</p><p>　　-x:執(zhí)行一

81、個用戶程序</p><p>　　-c:測試終端輸入輸出</p><p>　　和文件系統(tǒng)有關的選項：</p><p>　　-f:格式化模擬磁盤</p><p>　　-cp:將一個文件從宿主機拷貝到Nachos模擬磁盤上</p><p>　　-p:將Nachos磁盤上的文件顯示出來</p><p

82、>　　-r:將一個文件從Nachos模擬磁盤上刪除</p><p>　　-l:列出Nachos模擬磁盤上的文件</p><p>　　-D:打印出Nachos文件系統(tǒng)的內容</p><p>　　-t:測試Nachos文件系統(tǒng)的效率</p><p><b>　　和網絡有關的選項：</b></p>

83、<p>　　-n:設置網絡的可靠度（在0-1之間的一個小數）</p><p>　　-m:設置自己的HostID</p><p>　　-o:執(zhí)行網絡測試程序</p><p>　　6. 同步機制模塊分析（文件synch.cc synch.h）</p><p>　　線程的同步和互斥是多個線程協(xié)同工作的基礎。Nachos提供了三種同步

84、和互斥的手段：信號量、鎖機制以及條件變量機制，提供三種同步互斥機制是為了用戶使用方便。</p><p>　　在同步互斥機制的實現中，很多操作都是原子操作。Nachos是運行在單一處理器上的操作系統(tǒng)，在單一處理器上，實現原子操作只要在操作之前關中斷即可，操作結束后恢復原來中斷狀態(tài)。</p><p>　　6.1 信號量 ( Semaphore )</p><p>　　N

85、achos已經實現了Semaphore，它的基本結構如下所示：</p><p>　　class Semaphore {</p><p><b>　　public:</b></p><p>　　void P(); //信號量的P操作</p><p>　　void V(); //信號量

86、的V操作</p><p><b>　　private:</b></p><p>　　int value; //信號量值 ( >=0)</p><p>　　List *queue; //線程等待隊列</p><p><b>　　};</b&g

87、t;</p><p>　　信號量的私有屬性有信號量的值，它是一個閥門。線程等待隊列中存放所有等待該信號量的線程。信號量有兩個操作：P操作和V操作，這兩個操作都是原子操作。</p><p><b>　　6.1.1 P操作</b></p><p>　　當value等于0時，</p><p>　　將當前運行線程放入線程等待隊列

88、。</p><p>　　當前運行線程進入睡眠狀態(tài)，并切換到其它線程運行。</p><p>　　當value大于0時，value--。</p><p><b>　　6.1.2 V操作</b></p><p>　　如果線程等待隊列中有等待該信號量的線程，取出其中一個將其設置成就緒態(tài)，準備運行。</p><

89、p><b>　　value++;</b></p><p><b>　　6.2 鎖機制</b></p><p>　　鎖機制是線程進入臨界區(qū)的工具。一個鎖有兩種狀態(tài)，BUSY和FREE。當鎖處于FREE態(tài)時，線程可以取得該鎖后進入臨界區(qū)，執(zhí)行完臨界區(qū)操作之后，釋放鎖；當鎖處于BUSY態(tài)時，需要申請該鎖的線程進入睡眠狀態(tài)，等到鎖為FREE態(tài)時，再

90、取得該鎖。</p><p>　　鎖的基本結構如下所示：</p><p>　　class Lock {</p><p><b>　　public:</b></p><p>　　Lock(char* debugName); //初始化方法</p><p>　　~Lock();

91、//析構方法</p><p>　　char* getName() { return name; }//取出鎖名（調試用）</p><p>　　void Acquire(); //獲得鎖方法</p><p>　　void Release(); //釋放鎖方法</p><p>　　bool isHeldBy

92、CurrentThread();//判斷鎖是否為現運行線程擁有</p><p><b>　　private:</b></p><p>　　char* name;//鎖名（調試用）</p><p><b>　　};</b></p><p>　　在現有的Nachos中，沒有給出

93、鎖機制的實現，鎖的基本結構也只給出了部分內容，其它內容可以視實現決定?？傮w來說，鎖有兩個操作Acquire和Release，它們都是原子操作。</p><p><b>　　6.3條件變量</b></p><p>　　條件變量和信號量與鎖機制不一樣，它是沒有值的。（實際上，鎖機制是一個二值信號量，可以通過信號量來實現）當一個線程需要的某種條件沒有得到滿足時，可以將自己

94、作為一個等待條件變量的線程插入所有等待該條件變量的隊列；只要條件一旦滿足，該線程就會被喚醒繼續(xù)運行。條件變量總是和鎖機制一同使用，它的基本結構如下：</p><p>　　class Condition {</p><p><b>　　public:</b></p><p>　　Condition(char* debugName);//

95、初始化方法</p><p>　　~Condition();//析構方法</p><p>　　char* getName() { return (name); }//取出條件變量名（調試用）</p><p>　　void Wait(Lock *conditionLock); //線程進入等待</p><p>　　

96、void Signal(Lock *conditionLock); //喚醒一個等待該條件變量線程</p><p>　　void Broadcast(Lock *conditionLock);//喚醒等待該條件變量的線程</p><p><b>　　private:</b></p><p>　　char* name;

97、//條件變量名（調試用）</p><p><b>　　};</b></p><p>　　在現有的Nachos中，沒有給出條件變量的實現，條件變量的基本結構也只給出了部分內容，其它內容可以視實現決定。總體來說，條件變量有三個操作Wait、Signal以及BroadCast，所有的這些操作必須在當前線程獲得一個鎖的前提下，而且所有對一個條件變量進行的操作必須建立在同

98、一個鎖的前提下。</p><p>　　理解Nachos中支持用戶進程的機制</p><p>　　Nachos 對內存、寄存器以及CPU的模擬</p><p>　　Nachos機器模擬很重要的部分是內存和寄存器的模擬。Nachos寄存器組模擬了全部32個MIPS機（R2/3000）的寄存器，同時加上有關Nachos系統(tǒng)調試用的8個寄存器，以期讓模擬更加真實化并易于調試

99、，對于一些特殊的寄存器說明如下：</p><p>　　Nachos用宿主機的一塊內存模擬自己的內存。為了簡便起見，每個內存頁的大小同磁盤扇區(qū)的大小相同，而整個內存的大小遠遠小于模擬磁盤的大小。由于Nachos是一個教學操作系統(tǒng)，在內存分配上和實際的操作系統(tǒng)是有區(qū)別的。事實上，Nachos的內存只有當需要執(zhí)行用戶程序時用戶程序的一個暫存地，而作為操作系統(tǒng)內部使用的數據結構不存放在Nachos的模擬內存中，而是申請N

100、achos所在宿主機的內存。所以Nachos的一些重要的數據結構如線程控制結構等的數目可以是無限的，不受Nachos模擬內存大小的限制。</p><p>　　這里需要強調的是，此處Nachos模擬的寄存器組同Thread類（第三章第三節(jié)）中的machineState[]數組表示的寄存器組不同，后者代表的是宿主機的寄存器組，是實際存在的；而前者只是為了運行擁護程序模擬的。</p><p>　

101、　在用戶程序運行過程中，會有很多系統(tǒng)陷入核心的情況。系統(tǒng)陷入有兩大類原因：進行系統(tǒng)調用陷入和系統(tǒng)出錯陷入。系統(tǒng)調用陷入在用戶程序進行系統(tǒng)調用時發(fā)生。系統(tǒng)調用可以看作是軟件指令，它們有效地彌補了機器硬件指令不足；系統(tǒng)出錯陷入在系統(tǒng)發(fā)生錯誤時發(fā)生，比如用戶程序使用了非法指令以及用戶程序邏輯地址同實際的物理地址映射出錯等情況。不同的出錯陷入會有不同的處理，比如用戶程序邏輯地址映射出錯會引起頁面的重新調入，而用戶程序使用了非法指令則需要向用戶報

102、告等等。Nachos處理的陷入有：</p><p>　　需要注意的是，雖然這里的很多方法和屬性規(guī)定為public的，但是它們只能在系統(tǒng)核心內被調用。定義Machine類的目的是為了執(zhí)行用戶程序，如同許多其它系統(tǒng)一樣，用戶程序不直接使用內存的物理地址，而是使用自己的邏輯地址，在用戶程序邏輯地址和實際物理地址之間，就需要一次轉換，系統(tǒng)提供了兩種轉換方法的接口：線性頁面地址轉換方法和TLB頁面地址轉換方法。</p

103、><p>　　線性頁面地址轉換是一種較為簡單的方式，即用戶程序的邏輯地址同實際物理地址之間的關系是線性的。在作轉換時，給出邏輯地址，計算出其所在的邏輯頁號和頁中偏移量，通過查詢轉換表（實際上在使用線性頁面地址轉換時，TranslationEntry結構中的virtualPage是多余的，線性頁面轉換表的下標就是邏輯頁號），即可以得到實際物理頁號和其頁中偏移量。在模擬機上保存有線性頁面轉換表，它記錄的是當前運行用戶程序

104、的頁面轉換關系；在用戶進程空間中，也需要保存線性頁面轉換表，保存有自己運行用戶程序的頁面轉換關系。當其被切換上模擬處理機上運行時，需要將進程的線性頁面轉換表覆蓋模擬處理機的線性頁面轉換表。線性頁面轉換的過程如圖所示。</p><p>　　TLB頁面轉換則不同，TLB轉換頁表是硬件來實現的，表的大小一般較實際的用戶程序所占的頁面數要小，所以一般TLB表中只存放一部分邏輯頁到物理頁的轉換關系。這樣就可能出現邏輯地址轉

105、換失敗的現象，會發(fā)生PageFaultException異常。在該異常處理程序中，就需要借助用戶進程空間的線性頁面轉換表來計算出物理頁，同時TLB表中增加一項。如果TLB表已滿，就需要對TLB表項做LRU替換。使用TLB頁面轉換表處理起來邏輯較線性表為復雜，但是速度要快得多。由于TLB轉換頁表是硬件實現的，所以指向TLB轉換頁表的指針應該是只讀的，所以Machine類一旦實例化，TLB指針值不能改動。</p><p&

106、gt;　　在實際的系統(tǒng)中，線性頁面地址轉換和TLB頁面地址轉換只能二者取一，目前為簡便起見，Nachos選擇了前者，讀者可以自行完成TLB頁面地址轉換的實現。</p><p>　　一、用戶程序空間（文件address.cc, address.h）</p><p>　　Nachos的用戶進程由兩部分組成：核心部分和用戶程序部分。核心部分同一般的系統(tǒng)線程沒有區(qū)別，它共用了Nachos的正文段和

107、數據段，運行在宿主機上；而用戶程序部分則有自己的正文段、數據段和棧段，它存儲在Nachos的模擬內存中，運行在Nachos的模擬機上。在控制結構上，Nachos的用戶進程比系統(tǒng)線程多了以下內容：</p><p>　　int userRegisters[NumTotalRegs];//虛擬機的寄存器組</p><p>　　void SaveUserState();//線程切

108、換時保存虛擬機寄存器組</p><p>　　void RestoreUserState();//線程切換時恢復虛擬機寄存器組</p><p>　　AddrSpace *space;//線程運行的用戶程序</p><p>　　其中，用戶程序空間有AddrSpace類來描述：</p><p>　　class AddrSpa

109、ce {</p><p><b>　　public:</b></p><p>　　AddrSpace(OpenFile *executable);//根據可執(zhí)行文件構成用戶程序空間</p><p>　　~AddrSpace();//析構方法</p><p>　　void InitRegisters();

110、// 初始化模擬機的寄存器組</p><p>　　void SaveState();//保存當前機器頁表狀態(tài)</p><p>　　void RestoreState();//恢復機器頁表狀態(tài)</p><p><b>　　private:</b></p><p>　　Transla

111、tionEntry *pageTable;//用戶程序頁表</p><p>　　unsigned int numPages;//用戶程序的虛頁數</p><p><b>　　};</b></p><p>　　在Linux系統(tǒng)中，使用gcc交叉編譯技術將C程序編譯成R2/3000可以執(zhí)行的目標代碼，通過Nachos提供的coff

112、2noff工具將其轉換成Nachos可以識別的可執(zhí)行代碼格式，拷貝到Nachos的文件系統(tǒng)中才能執(zhí)行。</p><p><b>　　1.1生成方法</b></p><p>　　目前Nachos在運行用戶程序時，有如下的限制：</p><p>　　系統(tǒng)一次只能有運行一個用戶程序，所以目前的線性轉換頁表比較簡單，虛擬頁號同物理頁號完全一樣。當讀者

113、需要加強這部分內容時，需要增加內存分配算法。</p><p>　　系統(tǒng)能夠運行的用戶程序大小是有限制的，必須小于模擬的物理內存空間大小，否則出錯。在虛擬內存實現以后，這部分內容也將做改動。</p><p>　　1.2InitRegisters方法</p><p>　　1.3SaveState方法</p><p>　　1.4Restore

114、State方法</p><p>　　目前系統(tǒng)存儲和恢復用戶程序空間的實現非常簡單，這是因為系統(tǒng)一次只能運行一個用戶程序的局限和使用了線性頁面轉換表而決定的。</p><p>　　當用戶程序空間初始化之后（設由space指針指向），真正的啟動運行過程如下：</p><p>　　space -> InitRegisters();//初始化模擬機寄存器組<