nachos線程通信和調(diào)度分析操作系統(tǒng)課程設(shè)計(jì)

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

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

3、lt;p>　　二、 理解Nachos中線程運(yùn)行機(jī)制19</p><p>　　1. 工具模塊分析（文件list.cc list.h utility.cc utility.h）20</p><p>　　2. 線程啟動(dòng)和調(diào)度模塊分析（文件switch.s switch.h）21</p><p>　　3. 線程模塊分析（文件thread.cc thread.h）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、隊(duì)列的第一項(xiàng)的時(shí)間。這實(shí)際情況下，系統(tǒng)處于Idel狀態(tài)到中斷等待隊(duì)列第一項(xiàng)發(fā)生時(shí)間之間，完全有可能有其它中斷發(fā)生。由于中斷發(fā)生的時(shí)機(jī)不是完全隨機(jī)的，所以在Nachos系統(tǒng)中運(yùn)行的程序，不正確的同步程序也可能正常運(yùn)行，我們?cè)诖诵枰芮凶⒁狻?lt;/p><p>　　Nachos線程運(yùn)行有三種狀態(tài)：</p><p><b>　　Idle狀態(tài)</b></p>&l

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

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

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

23、Nachos會(huì)判斷中斷等待隊(duì)列中是否有</p><p>　　要發(fā)生的中斷，如果有中斷需要發(fā)生，則將該中斷從中斷等待隊(duì)列中刪除，調(diào)用相應(yīng)的中斷處理程序進(jìn)行處理。中斷處理程序是在某種特定的中斷發(fā)生時(shí)被調(diào)用，中斷處理程序的作用包括可以在現(xiàn)有的模擬硬件的基礎(chǔ)上建立更高層次的抽象。比如現(xiàn)有的模擬網(wǎng)絡(luò)是有丟失幀的不安全網(wǎng)絡(luò)，在中斷處理程序中可以加入請(qǐng)求重發(fā)機(jī)制來實(shí)現(xiàn)一個(gè)安全網(wǎng)絡(luò)。</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;// 中斷對(duì)應(yīng)的中斷處理程序</p><p>　　int arg;// 中斷處理程序的參數(shù)</p><p>　　int when;// 中斷發(fā)生的時(shí)機(jī)</p><p>　　IntType type;// 中斷的類型，供調(diào)試用&l

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

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

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

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

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

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

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

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

34、us now);</p><p>　　// 改變當(dāng)前中斷的開關(guān)狀態(tài)，但不前進(jìn)模擬時(shí)鐘</p><p><b>　　};</b></p><p>　　其中，Schedule和 OneTick兩個(gè)方法雖然標(biāo)明是public的，但是除了虛擬機(jī)模擬部分以外的其它類方法是不能調(diào)用這兩個(gè)方法的。將它們?cè)O(shè)置成public的原因是因?yàn)樘摂M機(jī)模擬的其它類方法需要

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

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

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

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

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

40、andler內(nèi)部函數(shù)（見第1行）。為什么不直接用初始化函數(shù)中的timerHandler參數(shù)作為中斷處理函數(shù)呢？因?yàn)槿绻苯邮褂胻imerHandler作為時(shí)鐘中斷處理函數(shù)，第8行是將一個(gè)時(shí)鐘中斷插入等待處理中斷隊(duì)列，一旦中斷時(shí)刻到來，立即進(jìn)行中斷處理，處理結(jié)束后并沒有機(jī)會(huì)將下一個(gè)時(shí)鐘中斷插入到等待處理中斷隊(duì)列。TimerHandler內(nèi)部函數(shù)正是處理這個(gè)問題。當(dāng)時(shí)鐘中斷時(shí)刻到來時(shí)，調(diào)用TimerHandler函數(shù)，其調(diào)用TimerExp

41、ired方法，該方法將新的時(shí)鐘中斷插入到等待處理中斷隊(duì)列中，然后再調(diào)用真正的時(shí)鐘中斷處理函數(shù)。這樣Nachos就可以定時(shí)的收到時(shí)鐘中斷。</p><p>　　那么為什么不將TimerExpired方法作為時(shí)鐘中斷在Timer的初始化函數(shù)中調(diào)用呢？這是由于C++語言不能直接引用一個(gè)類內(nèi)部方法的指針，所以借用TimerHandler內(nèi)部函數(shù)。這也是TimerExpired必須設(shè)計(jì)成public的方法的原因，因?yàn)樗?/p>

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

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

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

45、p>　　Nachos線程系統(tǒng)的結(jié)構(gòu)</p><p>　　線程管理系統(tǒng)中，有兩個(gè)與機(jī)器相關(guān)的函數(shù)，正文切換過程依賴于具體的機(jī)器，這是因?yàn)橄到y(tǒng)線程切換是借助于宿主機(jī)的正文切換，正文切換過程中的寄存器保護(hù)，建立初始調(diào)用框架等操作對(duì)不同的處理機(jī)結(jié)構(gòu)是不一樣的。其中一個(gè)函數(shù)是ThreadRoot，它是所有線程運(yùn)行的入口；另一個(gè)函數(shù)是SWITCH，它負(fù)責(zé)線程之間的切換。 Scheduler類用于實(shí)現(xiàn)線程的調(diào)度。它

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

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

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

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

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

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

52、的聯(lián)系，所以這里僅作一個(gè)簡(jiǎn)單的介紹。</p><p>　　List類在Nachos中廣泛使用，它定義了一個(gè)鏈表結(jié)構(gòu)，有關(guān)List的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)如下所示：</p><p>　　class ListElement {//定義了List中的元素類型</p><p><b>　　public:</b></p><p&

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

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

55、);//初始化方法</p><p>　　~List();//析構(gòu)方法</p><p>　　void Prepend(void *item);//將新元素增加在鏈?zhǔn)?lt;/p><p>　　void Append(void *item); //將新元素增加在鏈尾</p><p>　　void *Re

56、move(); //刪除鏈?zhǔn)自夭⒎祷卦撛?lt;/p><p>　　void Mapcar(VoidFunctionPtr func);//將函數(shù)func作用在鏈中每個(gè)元素上</p><p>　　bool IsEmpty();//判斷鏈表是否為空</p><p>　　void SortedInsert(void *item, int s

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

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

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

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

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

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

63、lt;p>　　調(diào)用 StartupPC 函數(shù)；</p><p>　　調(diào)用 InitialPC 函數(shù)；</p><p>　　調(diào)用 WhenDonePC 函數(shù)；</p><p>　　這里我們可以看到，由ThreadRoot入口可以轉(zhuǎn)而運(yùn)行線程所需要運(yùn)行的函數(shù)，從而達(dá)到生成線程的目的。</p><p>　　2.2 SWITCH函數(shù)</

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

65、　保存原運(yùn)行線程的狀態(tài)</p><p>　　恢復(fù)新運(yùn)行線程的狀態(tài)</p><p>　　在新運(yùn)行線程的棧空間上運(yùn)行新線程</p><p>　　3. 線程模塊分析（文件thread.cc thread.h）</p><p>　　Thread類實(shí)現(xiàn)了操作系統(tǒng)的線程控制塊，同操作系統(tǒng)課程中進(jìn)程程管理中的PCB (Process Control Blo

66、ck) 有相似之處。</p><p>　　Thread線程控制類較PCB為簡(jiǎn)單的多，它沒有線程標(biāo)識(shí) (pid)、實(shí)際用戶標(biāo)識(shí) (uid)等和線程操作不是非常有聯(lián)系的部分，也沒有將PCB分成proc結(jié)構(gòu)和user結(jié)構(gòu)。這是因?yàn)橐粋€(gè)Nachos線程是在宿主機(jī)上運(yùn)行的。無論是系統(tǒng)線程和用戶進(jìn)程，Thread線程控制類的實(shí)例都生成在宿主機(jī)而不是生成在虛擬機(jī)上。所以不存在實(shí)際操作系統(tǒng)中proc結(jié)構(gòu)常駐內(nèi)存，而user結(jié)構(gòu)可

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

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

69、</p><p>　　class Thread {</p><p><b>　　private:</b></p><p>　　int* stackTop; //當(dāng)前堆棧指針</p><p>　　int machineState[MachineStateSize]; //宿主機(jī)的運(yùn)行寄存器</

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

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

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

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

74、gt;　　char* name;//線程名（調(diào)試用）</p><p>　　void StackAllocate(VoidFunctionPtr func, int arg);</p><p>　　//申請(qǐng)線程的棧空間</p><p>　　#ifdef USER_PROGRAM</p><p>　　int userRegis

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

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

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

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

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

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

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

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

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

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

85、achos已經(jīng)實(shí)現(xiàn)了Semaphore，它的基本結(jié)構(gòu)如下所示：</p><p>　　class Semaphore {</p><p><b>　　public:</b></p><p>　　void P(); //信號(hào)量的P操作</p><p>　　void V(); //信號(hào)量

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

87、t;</p><p>　　信號(hào)量的私有屬性有信號(hào)量的值，它是一個(gè)閥門。線程等待隊(duì)列中存放所有等待該信號(hào)量的線程。信號(hào)量有兩個(gè)操作：P操作和V操作，這兩個(gè)操作都是原子操作。</p><p><b>　　6.1.1 P操作</b></p><p>　　當(dāng)value等于0時(shí)，</p><p>　　將當(dāng)前運(yùn)行線程放入線程等待隊(duì)列

88、。</p><p>　　當(dāng)前運(yùn)行線程進(jìn)入睡眠狀態(tài)，并切換到其它線程運(yùn)行。</p><p>　　當(dāng)value大于0時(shí)，value--。</p><p><b>　　6.1.2 V操作</b></p><p>　　如果線程等待隊(duì)列中有等待該信號(hào)量的線程，取出其中一個(gè)將其設(shè)置成就緒態(tài)，準(zhǔn)備運(yùn)行。</p><

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

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

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

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

93、鎖機(jī)制的實(shí)現(xiàn)，鎖的基本結(jié)構(gòu)也只給出了部分內(nèi)容，其它內(nèi)容可以視實(shí)現(xiàn)決定。總體來說，鎖有兩個(gè)操作Acquire和Release，它們都是原子操作。</p><p><b>　　6.3條件變量</b></p><p>　　條件變量和信號(hào)量與鎖機(jī)制不一樣，它是沒有值的。（實(shí)際上，鎖機(jī)制是一個(gè)二值信號(hào)量，可以通過信號(hào)量來實(shí)現(xiàn)）當(dāng)一個(gè)線程需要的某種條件沒有得到滿足時(shí)，可以將自己

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

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

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

97、//條件變量名（調(diào)試用）</p><p><b>　　};</b></p><p>　　在現(xiàn)有的Nachos中，沒有給出條件變量的實(shí)現(xiàn)，條件變量的基本結(jié)構(gòu)也只給出了部分內(nèi)容，其它內(nèi)容可以視實(shí)現(xiàn)決定。總體來說，條件變量有三個(gè)操作Wait、Signal以及BroadCast，所有的這些操作必須在當(dāng)前線程獲得一個(gè)鎖的前提下，而且所有對(duì)一個(gè)條件變量進(jìn)行的操作必須建立在同

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

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

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

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

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

103、><p>　　線性頁(yè)面地址轉(zhuǎn)換是一種較為簡(jiǎn)單的方式，即用戶程序的邏輯地址同實(shí)際物理地址之間的關(guān)系是線性的。在作轉(zhuǎn)換時(shí)，給出邏輯地址，計(jì)算出其所在的邏輯頁(yè)號(hào)和頁(yè)中偏移量，通過查詢轉(zhuǎn)換表（實(shí)際上在使用線性頁(yè)面地址轉(zhuǎn)換時(shí)，TranslationEntry結(jié)構(gòu)中的virtualPage是多余的，線性頁(yè)面轉(zhuǎn)換表的下標(biāo)就是邏輯頁(yè)號(hào)），即可以得到實(shí)際物理頁(yè)號(hào)和其頁(yè)中偏移量。在模擬機(jī)上保存有線性頁(yè)面轉(zhuǎn)換表，它記錄的是當(dāng)前運(yùn)行用戶程序

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

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

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

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

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

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

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

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

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

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

114、State方法</p><p>　　目前系統(tǒng)存儲(chǔ)和恢復(fù)用戶程序空間的實(shí)現(xiàn)非常簡(jiǎn)單，這是因?yàn)橄到y(tǒng)一次只能運(yùn)行一個(gè)用戶程序的局限和使用了線性頁(yè)面轉(zhuǎn)換表而決定的。</p><p>　　當(dāng)用戶程序空間初始化之后（設(shè)由space指針指向），真正的啟動(dòng)運(yùn)行過程如下：</p><p>　　space -> InitRegisters();//初始化模擬機(jī)寄存器組<