Nachos線程通信和調(diào)度分析操作系統(tǒng)課程設(shè)計說明書

1、操作系統(tǒng)課程設(shè)計說 明 書學(xué) 院： 信息科學(xué)與工程學(xué)院 TOC o 1-3 h u HYPERLINK l _Toc13669 一、 理解Nachos模擬的物理機的運行機制 PAGEREF _Toc13669 3 HYPERLINK l _Toc7854 1. Sysdep模塊分析（文件） PAGEREF _Toc7854 5 HYPERLINK l _Toc25559 2.中斷模塊分析（文件） PAGEREF _Toc25559 10 HYPERLINK l _Toc17859 3. 時鐘中斷模塊分析（文件） PAGEREF _Toc17859 16 HYPERLINK l _Toc1189

2、2 4. 終端設(shè)備模塊分析（文件） PAGEREF _Toc11892 18 HYPERLINK l _Toc8435 二、 理解Nachos中線程運行機制 PAGEREF _Toc8435 19 HYPERLINK l _Toc31733 1. 工具模塊分析（文件） PAGEREF _Toc31733 20 HYPERLINK l _Toc27361 2. 線程啟動和調(diào)度模塊分析（文件） PAGEREF _Toc27361 21 HYPERLINK l _Toc6132 3. 線程模塊分析（文件） PAGEREF _Toc6132 22 HYPERLINK l _Toc30243 4. 線程

3、調(diào)度算法模塊分析（文件） PAGEREF _Toc30243 26 HYPERLINK l _Toc29328 5.Nachos主控模塊分析（文件） PAGEREF _Toc29328 27 HYPERLINK l _Toc8913 6. 同步機制模塊分析（文件） PAGEREF _Toc8913 28 HYPERLINK l _Toc8740 三、 理解Nachos中支持用戶進程的機制 PAGEREF _Toc8740 30 HYPERLINK l _Toc24555 一、用戶程序空間（文件address.cc, address.h） PAGEREF _Toc24555 35 HYPERLI

4、NK l _Toc27544 二、系統(tǒng)調(diào)用（文件exception.cc, syscall.h, start.s） PAGEREF _Toc27544 36理解Nachos模擬的物理機的運行機制Machine類 XE Machine類 用來模擬計算機主機。它提供的功能有：讀寫寄存器。讀寫主存、運行一條用戶程序 XE 用戶程序 的匯編指令、運行用戶程序、單步調(diào)試用戶程序、顯示主存和寄存器狀態(tài)、將虛擬內(nèi)存 XE 虛擬內(nèi)存 地址轉(zhuǎn)換為物理內(nèi)存地址、陷入 Nachos 內(nèi)核等等。Machine類 XE Machine類 實現(xiàn)方法是在宿主機上分配兩塊內(nèi)存分別作為虛擬機的寄存器和物理內(nèi)存。運行用戶程序 X

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

6、關(guān)兩種，中斷類型有時鐘中斷、磁盤中斷、控制臺寫中斷、控制臺讀中斷、網(wǎng)絡(luò)發(fā)送中斷以及網(wǎng)絡(luò)接收中斷。機器狀態(tài)有用戶態(tài)，核心態(tài)和空閑態(tài)。中斷系統(tǒng)提供的功能有開/關(guān)中斷，讀/寫機器狀態(tài)，將一個即將發(fā)生中斷放入中斷隊列，以及使機器時鐘前進一步。在Interrupt類 XE Interrupt類 中有一個記錄即將發(fā)生中斷的隊列，稱為中斷等待隊列。中斷等待隊列中每個等待處理的中斷包含中斷類型、中斷處理程序的地址及參數(shù)、中斷應(yīng)當發(fā)生的時間等信息。一般是由硬件設(shè)備模擬程序把將要發(fā)生的中斷放入中斷隊列。中斷系統(tǒng)提供了一個模擬機器時鐘，機器時鐘在下列情況下前進：用戶程序 XE 用戶程序 打開中斷執(zhí)行一條用戶指令處理

7、機沒有進程正在運行機器時鐘前進時，中斷處理的過程如下圖所示:Nachos中斷處理時機NYNY進行正文切換中斷處理程序要求進行正文切換?開中斷取出隊列中一個應(yīng)當發(fā)生的中斷，調(diào)用這個中斷的處理程序去處理中斷中斷隊列中有應(yīng)當發(fā)生的中斷?關(guān)中斷中斷系統(tǒng)成為整個Nachos虛擬機的基礎(chǔ)，其它的模擬硬件設(shè)備都是建立在中斷系統(tǒng)之上的。在此之上，加上Machine類 XE Machine類 模擬的指令解釋器，可以實現(xiàn)Nachos的線程管理 XE 線程管理 、文件系統(tǒng)管理 XE 文件系統(tǒng)管理 、虛擬內(nèi)存 XE 虛擬內(nèi)存 、用戶程序 XE 用戶程序 和網(wǎng)絡(luò)管理 XE 網(wǎng)絡(luò)管理 等所有操作系統(tǒng)功能。下圖展示了Nac

8、hos系統(tǒng)的整體結(jié)構(gòu)。用 戶 程 序線程管理 XE 線程管理 網(wǎng)絡(luò)協(xié)議文件系統(tǒng)虛擬內(nèi)存 XE 虛擬內(nèi)存 終端設(shè)備時鐘網(wǎng)絡(luò)磁盤中 斷 系 統(tǒng)指令解釋和內(nèi)存模擬Nachos系統(tǒng)的整體結(jié)構(gòu)機器模擬的實現(xiàn)：1. Sysdep模塊分析（文件）Nachos的運行環(huán)境可以是多種操作系統(tǒng)，由于每種操作系統(tǒng)所提供的系統(tǒng)調(diào)用或函數(shù)調(diào)用在形式和內(nèi)容上可能有細微的差別。sysdep模塊的作用是屏蔽掉這些差別。1.1 PoolFile 函數(shù)語法：bool PoolFile (int fd)參數(shù)：fd:文件描述符，也可以是一個套接字 (socket)功能：測試一個打開文件 fd 是否有內(nèi)容可以讀，如果有則返回TRUE，否

9、則返回FALSE。當Nachos系統(tǒng)處于IDLE狀態(tài)時，測試過程有一個延時，也就是在一定時間范圍內(nèi)如果有內(nèi)容可讀的話，同樣返回TRUE。實現(xiàn)：通過 select 系統(tǒng)調(diào)用。返回：打開文件是否有內(nèi)容供讀取。1.2 OpenForWrite 函數(shù)語法：int OpenForWrite (char *name)參數(shù)：name:文件名功能：為寫操作打開一個文件。如果該文件不存在，產(chǎn)生該文件；如果該文件已經(jīng)存在，則將該文件原有的內(nèi)容刪除。實現(xiàn)：通過 open 系統(tǒng)調(diào)用。返回：打開的文件描述符。1.3 OpenForReadWrite 函數(shù)語法：int OpenForReadWrite (char *na

10、me, bool crashOnError)參數(shù)：name:文件名crashOnError:crash標志功能：為讀寫操作打開一個文件。當 crashOnError 標志設(shè)置而文件不能讀寫打開時，系統(tǒng)出錯退出。實現(xiàn)：通過 open 系統(tǒng)調(diào)用。返回：打開的文件描述符。1.4 Read 函數(shù)語法：void Read (int fd, char *buffer, int nBytes)參數(shù)：fd:打開文件描述符buffer:讀取內(nèi)容的緩沖區(qū)nBytes:需要讀取的字節(jié)數(shù)功能：從一個打開文件fd中讀取nBytes的內(nèi)容到buffer緩沖區(qū)。如果讀取失敗，系統(tǒng)退出。實現(xiàn)：通過 read系統(tǒng)調(diào)用。返回：空

11、。1.5 ReadPartial 函數(shù)語法：int ReadPartial (int fd, char *buffer, int nBytes)參數(shù)：fd:打開文件描述符buffer:讀取內(nèi)容的緩沖區(qū)nBytes:需要讀取的最大字節(jié)數(shù) 功能：從一個打開文件fd中讀取nBytes的內(nèi)容到buffer緩沖區(qū)。 實現(xiàn)：通過 read系統(tǒng)調(diào)用。 返回：實際讀出的字節(jié)數(shù)。1.6 WriteFile 函數(shù) 語法：void WriteFile (int fd, char *buffer, int nBytes) 參數(shù)：fd:打開文件描述符buffer:需要寫的內(nèi)容所在的緩沖區(qū)nBytes:需要寫的內(nèi)容最大字

12、節(jié)數(shù) 功能：將buffer緩沖區(qū)中的內(nèi)容寫nBytes到一個打開文件fd中。 實現(xiàn)：通過 write系統(tǒng)調(diào)用。 返回：空1.7 Lseek 函數(shù) 語法：void Lseek (int fd, int offset, int whence) 參數(shù)：fd:文件描述符offset:偏移量whence:指針移動的起始點 功能：移動一個打開文件的讀寫指針，含義同lseek系統(tǒng)調(diào)用；出錯則退出系統(tǒng)。 實現(xiàn)：通過lseek 系統(tǒng)調(diào)用。 返回：空。1.8 Tell 函數(shù) 語法：int Tell (int fd) 參數(shù)：fd:文件描述符 功能：指出當前讀寫指針位置 實現(xiàn)：通過lseek 系統(tǒng)調(diào)用。 返回：返回當

13、前指針位置。1.9 Close 函數(shù) 語法：void Close (int fd) 參數(shù)：fd:文件描述符 功能：關(guān)閉當前打開文件fd，如果出錯則退出系統(tǒng)。 實現(xiàn)：通過close系統(tǒng)調(diào)用。 返回：空1.10 Unlink 函數(shù) 語法：bool Unlink (char *name) 參數(shù)：name:文件名 功能：刪除文件。 實現(xiàn)：通過unlink系統(tǒng)調(diào)用。 返回：刪除成功，返回TRUE；否則返回FALSE。1.11 OpenSocket 函數(shù) 語法：int OpenSocket () 參數(shù)：無 功能：申請一個socket。 實現(xiàn)：通過socket系統(tǒng)調(diào)用。其中AF_UNIX參數(shù)說明使用UNIX

14、內(nèi)部協(xié)議。（Nachos是用SOCKET文件來模擬網(wǎng)絡(luò)節(jié)點，所以采用UNIX內(nèi)部協(xié)議。向該文件讀寫內(nèi)容分別代表從該節(jié)點讀取內(nèi)容和向該網(wǎng)絡(luò)節(jié)點發(fā)送內(nèi)容）SOCK_DGRAM參數(shù)說明采用無連接定長數(shù)據(jù)包型的數(shù)據(jù)鏈路。 返回：申請到的socket ID。1.12 CloseSocket 函數(shù) 語法：void CloseSocket (int sockID) 參數(shù)：sockID:socket標識 功能：釋放一個socket。 實現(xiàn)：通過close系統(tǒng)調(diào)用。 返回：無。1.13 Abort 函數(shù) 語法：void Abort () 參數(shù)：無 功能：退出系統(tǒng) (非正常退出)。 實現(xiàn)：通過abort系統(tǒng)調(diào)用。

15、 返回：無。1.14 Exit 函數(shù) 語法：void Exit (int exitCode) 參數(shù)：exitCode:向系統(tǒng)的返回值 功能：退出系統(tǒng)。 實現(xiàn)：通過exit系統(tǒng)調(diào)用。 返回：空2.中斷模塊分析（文件）中斷模塊的主要作用是模擬底層的中斷機制?？梢酝ㄟ^該模擬機制來啟動和禁止中斷 (SetLevel)；該中斷機制模擬了Nachos系統(tǒng)需要處理的所有的中斷，包括時鐘中斷、磁盤中斷、終端讀/終端寫中斷以及網(wǎng)絡(luò)接收/網(wǎng)絡(luò)發(fā)送中斷。中斷的發(fā)生總是有一定的時間。比如當向硬盤發(fā)出讀請求，硬盤處理請求完畢后會發(fā)生中斷；在請求和處理完畢之間需要經(jīng)過一定的時間。所以在該模塊中，模擬了時鐘的前進。為了實現(xiàn)

16、簡單和便于統(tǒng)計各種活動所占用的時間起見，Nachos規(guī)定系統(tǒng)時間在以下三種情況下前進：執(zhí)行用戶態(tài)指令，時鐘前進是顯而易見的。我們認為，Nachos執(zhí)行每條指令所需時間是固定的，為一個時鐘單位(Tick)。一般系統(tǒng)態(tài)在進行中斷處理程序時，需要關(guān)中斷。但是中斷處理程序本身也需要消耗時間，而在關(guān)閉中斷到重新打開中斷之間無法非常準確地計算時間，所以當中斷重新打開的時候，加上一個中斷處理所需時間的平均值。當系統(tǒng)中沒有就緒進程時，系統(tǒng)處于Idle狀態(tài)。這種狀態(tài)可能是系統(tǒng)中所有的進程都在等待各自的某種操作完成。也就是說，系統(tǒng)將在未來某個時間發(fā)生中斷，到中斷發(fā)生的時候中斷處理程序?qū)⑦M行中斷處理。在系統(tǒng)模擬中，

17、有一個中斷等待隊列，專門存放將來發(fā)生的中斷。在這種情況下，可以將系統(tǒng)時間直接跳到中斷等待隊列第一項所對應(yīng)的時間，以免不必要的等待。當前面兩種情況需要時鐘前進時，調(diào)用OneTick方法。OneTick方法將系統(tǒng)態(tài)和用戶態(tài)的時間分開進行處理，這是因為用戶態(tài)的時間計算是根據(jù)用戶指令為單位的；而在系統(tǒng)態(tài)，沒有辦法進行指令的計算，所以將系統(tǒng)態(tài)的一次中斷調(diào)用或其它需要進行時間計算的單位設(shè)置為一個固定值，假設(shè)為一條用戶指令執(zhí)行時間的10倍。雖然Nachos模擬了中斷的發(fā)生，但是畢竟不能與實際硬件一樣，中斷發(fā)生的時機可以是任意的。比如當系統(tǒng)中沒有就緒進程時，時鐘直接跳到未處理中斷隊列的第一項的時間。這實際情況

18、下，系統(tǒng)處于Idel狀態(tài)到中斷等待隊列第一項發(fā)生時間之間，完全有可能有其它中斷發(fā)生。由于中斷發(fā)生的時機不是完全隨機的，所以在Nachos系統(tǒng)中運行的程序，不正確的同步程序也可能正常運行，我們在此需要密切注意。Nachos線程運行有三種狀態(tài)：Idle狀態(tài)系統(tǒng)CPU處于空閑狀態(tài)，沒有就緒線程可以運行。如果中斷等待隊列中有需要處理的除了時鐘中斷以外的中斷，說明系統(tǒng)還沒有結(jié)束，將時鐘調(diào)整到發(fā)生中斷的時間，進行中斷處理；否則認為系統(tǒng)結(jié)束所有的工作，退出。系統(tǒng)態(tài)Nachos執(zhí)行系統(tǒng)程序。Nachos雖然模擬了虛擬機的內(nèi)存，但是Nachos系統(tǒng)程序本身的運行不是在該模擬內(nèi)存中，而是利用宿主機的存儲資源。這是

19、Nachos操作系統(tǒng)同真正操作系統(tǒng)的重要區(qū)別。用戶態(tài)系統(tǒng)執(zhí)行用戶程序 XE 用戶程序 。當執(zhí)行用戶程序時，每條指令占用空間是Nachos的模擬內(nèi)存。中斷等待隊列是Nachos虛擬機最重要的數(shù)據(jù)結(jié)構(gòu)之一，它記錄了當前虛擬機可以預(yù)測的將在未來發(fā)生的所有中斷。當系統(tǒng)進行了某種操作可能引起未來發(fā)生的中斷時，如磁盤的寫入、向網(wǎng)絡(luò)寫入數(shù)據(jù)等都會將中斷插入到中斷等待隊列中；對于一些定期需要發(fā)生的中斷，如時鐘中斷、終端讀取中斷等，系統(tǒng)會在中斷處理后將下一次要發(fā)生的中斷插入到中斷等待隊列中。中斷的插入過程是一個優(yōu)先隊列的插入過程，其優(yōu)先級是中斷發(fā)生的時間，也就是說，先發(fā)生的中斷將優(yōu)先得到處理。對中斷等待隊列的操

20、作中斷等待隊列某些將會引起中斷的操作系統(tǒng)定期發(fā)生的中斷時鐘前進判斷有無中斷發(fā)生當時鐘前進或者系統(tǒng)處于Idle狀態(tài)時，Nachos會判斷中斷等待隊列中是否有要發(fā)生的中斷，如果有中斷需要發(fā)生，則將該中斷從中斷等待隊列中刪除，調(diào)用相應(yīng)的中斷處理程序進行處理。中斷處理程序是在某種特定的中斷發(fā)生時被調(diào)用，中斷處理程序的作用包括可以在現(xiàn)有的模擬硬件的基礎(chǔ)上建立更高層次的抽象。比如現(xiàn)有的模擬網(wǎng)絡(luò)是有丟失幀的不安全網(wǎng)絡(luò)，在中斷處理程序中可以加入請求重發(fā)機制來實現(xiàn)一個安全網(wǎng)絡(luò)。2.1 PendingInterrupt類 XE Interrupt類 class PendingInterrupt public:Pe

21、ndingInterrupt (VoidFunctionPtr func, int param, int time, IntType kind);VoidFunctionPtr handler;/ 中斷對應(yīng)的中斷處理程序int arg;/ 中斷處理程序的參數(shù)int when;/ 中斷發(fā)生的時機IntType type;/ 中斷的類型，供調(diào)試用;這個類定義了一個中斷等待隊列中需要處理的中斷。為了方便起見，所有類的數(shù)據(jù)和成員函數(shù)都設(shè)置為public的，不需要其它的Get和Set等存取內(nèi)部數(shù)據(jù)的函數(shù)。初始化函數(shù)就是為對應(yīng)的參數(shù)賦值。2.2 Interrupt類 XE Interrupt類 class

22、 Interrupt public:/ 以下函數(shù)是Interrupt的對外接口Interrupt();/ 初始化中斷模擬Interrupt();/ 終止中斷模擬IntStatus SetLevel(IntStatus level);/ 開關(guān)中斷，并且返回之前的狀態(tài)void Enable();/ 開中斷IntStatus getLevel() return level;/ 取回當前中斷的開關(guān)狀態(tài) void Idle(); / 當進程就緒隊列為空時，執(zhí)行該函數(shù)void Halt(); / 退出系統(tǒng)，并打印狀態(tài)void YieldOnReturn();/ 設(shè)置中斷結(jié)束后要進行進程切換的標志 Mach

23、ineStatus getStatus() return status; / 返回系統(tǒng)當前的狀態(tài) void setStatus(MachineStatus st) status = st; / 設(shè)置系統(tǒng)當前的狀態(tài) void DumpState();/ 調(diào)試當前中斷隊列狀態(tài)用 void Schedule(VoidFunctionPtr handler, int arg, int when, IntType type);/ 在中斷等待隊列中，增加一個等待中斷 void OneTick(); / 模擬時鐘前進 private:/ 以下是內(nèi)部數(shù)據(jù)和內(nèi)部處理方法 IntStatus level;/ 中斷

24、的開關(guān)狀態(tài) List *pending;/ 當前系統(tǒng)中等待中斷隊列bool inHandler;/ 是否正在進行中斷處理標志 bool yieldOnReturn; / 中斷處理后是否需要正文切換標志MachineStatus status;/ 當前虛擬機運行狀態(tài)bool CheckIfDue(bool advanceClock);/ 檢查當前時刻是否有要處理的中斷void ChangeLevel(IntStatus old, IntStatus now);/ 改變當前中斷的開關(guān)狀態(tài)，但不前進模擬時鐘;其中，Schedule和 OneTick兩個方法雖然標明是public的，但是除了虛擬機模擬

25、部分以外的其它類方法是不能調(diào)用這兩個方法的。將它們設(shè)置成public的原因是因為虛擬機模擬的其它類方法需要直接調(diào)用這兩個方法。3. 時鐘中斷模塊分析（文件）該模塊的作用是模擬時鐘中斷。Nachos虛擬機可以如同實際的硬件一樣，每隔一定的時間會發(fā)生一次時鐘中斷。這是一個可選項，目前Nachos還沒有充分發(fā)揮時鐘中斷的作用，只有在Nachos指定線程隨機切換時，（Nachos -rs參數(shù)，見線程管理 XE 線程管理 部分Nachos主控模塊分析）啟動時鐘中斷，在每次的時鐘中斷處理的最后，加入了線程的切換。實際上，時鐘中斷在線程管理中的作用遠不止這些，時鐘中斷還可以用作：線程管理 XE 線程管理 中

26、的時間片輪轉(zhuǎn)法的時鐘控制，（詳見線程管理系統(tǒng)中的實現(xiàn)實例中，對線程調(diào)度的改進部分）不一定每次時鐘中斷都會引起線程的切換，而是由該線程是否的時間片是否已經(jīng)用完來決定。分時系統(tǒng)線程優(yōu)先級的計算（詳見線程管理 XE 線程管理 系統(tǒng)中的實現(xiàn)實例中，對線程調(diào)度的改進部分）線程進入睡眠狀態(tài)時的時間計算可以通過時鐘中斷機制來實現(xiàn)sleep系統(tǒng)調(diào)用，在時鐘中斷處理程序中，每隔一定的時間對定時睡眠線程的時間進行一次評估，判斷是否需要喚醒它們。Nachos利用其模擬的中斷機制來模擬時鐘中斷。時鐘中斷間隔由TimerTicks宏決定（100倍Tick的時間）。在系統(tǒng)模擬時有一個缺陷，如果系統(tǒng)就緒進程不止一個的話，每

27、次時鐘中斷都一定會發(fā)生進程的切換（見中TimerInterruptHandler函數(shù)）。所以運行Nachos時，如果以同樣的方式提交進程，系統(tǒng)的結(jié)果將是一樣的。這不符合操作系統(tǒng)的運行不確定性的特性。所以在模擬時鐘中斷的時候，加入了一個隨機因子，如果該因子設(shè)置的話，時鐘中斷發(fā)生的時機將在一定范圍內(nèi)是隨機的。這樣有些用戶程序 XE 用戶程序 在同步方面的錯誤就比較容易發(fā)現(xiàn)。但是這樣的時鐘中斷和真正操作系統(tǒng)中的時鐘中斷將有不同的含義。不能象真正的操作系統(tǒng)那樣通過時鐘中斷來計算時間等等。是否需要隨機時鐘中斷可以通過設(shè)置選項(-rs)來實現(xiàn)。Timer類 XE Timer類 的實現(xiàn)很簡單，當生成出一個T

28、imer類的實例時，就設(shè)計了一個模擬的時鐘中斷。這里考慮的問題是：怎樣實現(xiàn)定期發(fā)生時鐘中斷？在Timer的初始化函數(shù)中，借用TimerHandler內(nèi)部函數(shù)（見第1行）。為什么不直接用初始化函數(shù)中的timerHandler參數(shù)作為中斷處理函數(shù)呢？因為如果直接使用timerHandler作為時鐘中斷處理函數(shù)，第8行是將一個時鐘中斷插入等待處理中斷隊列，一旦中斷時刻到來，立即進行中斷處理，處理結(jié)束后并沒有機會將下一個時鐘中斷插入到等待處理中斷隊列。TimerHandler內(nèi)部函數(shù)正是處理這個問題。當時鐘中斷時刻到來時，調(diào)用TimerHandler函數(shù)，其調(diào)用TimerExpired方法，該方法將新

29、的時鐘中斷插入到等待處理中斷隊列中，然后再調(diào)用真正的時鐘中斷處理函數(shù)。這樣Nachos就可以定時的收到時鐘中斷。那么為什么不將TimerExpired方法作為時鐘中斷在Timer的初始化函數(shù)中調(diào)用呢？這是由于C+語言不能直接引用一個類內(nèi)部方法的指針，所以借用TimerHandler內(nèi)部函數(shù)。這也是TimerExpired必須設(shè)計成public的方法的原因，因為它要被TimerHandler調(diào)用。這樣的方法不僅僅在Timer模擬時鐘中斷中用到，所有需要定期發(fā)生的中斷都可以采用這樣的方法，如Nachos需要定期地檢查是否有終端的輸入、網(wǎng)絡(luò)是否有發(fā)給自己的報文 XE 報文 等都是用這種方式實現(xiàn)。詳見

30、 network.cc 以及。TimeOfextInterrupt()方法的作用是計算下一次時鐘中斷發(fā)生的時機，如果需要時鐘中斷發(fā)生的時機是隨機的，可以在Nachos命令行中設(shè)置 rs 選項。這樣，Nachos的線程切換的時機將會是隨機的。但是此時時鐘中斷則不能作為系統(tǒng)計時的標準了。理解Nachos中線程運行機制Nachos中的系統(tǒng)線程和用戶進程宿主機CPU和寄存器虛擬機CPU和寄存器用戶程序系統(tǒng)線程用戶程序系統(tǒng)線程用戶進程用戶程序系統(tǒng)線程系統(tǒng)線程系統(tǒng)線程系統(tǒng)線程Nachos為線程提供的功能函數(shù)有:生成一個線程(Fork)使線程睡眠等待(Sleep)結(jié)束線程(Finish)設(shè)置線程狀態(tài)(set

31、Status)放棄處理機(Yield)線程系統(tǒng)的結(jié)構(gòu)如圖所示:用戶進程信號量條件變量鎖Thread類模擬中斷正文切換線程調(diào)度Nachos線程系統(tǒng)的結(jié)構(gòu)線程管理 XE 線程管理 系統(tǒng)中，有兩個與機器相關(guān)的函數(shù)，正文切換過程依賴于具體的機器，這是因為系統(tǒng)線程切換是借助于宿主機的正文切換，正文切換過程中的寄存器保護，建立初始調(diào)用框架等操作對不同的處理機結(jié)構(gòu)是不一樣的。其中一個函數(shù)是ThreadRoot，它是所有線程運行的入口；另一個函數(shù)是SWITCH，它負責線程之間的切換。 Scheduler類用于實現(xiàn)線程的調(diào)度。它維護一個就緒線程隊列，當一個線程可以占用處理機時，就可以調(diào)用ReadyToRun方法

32、把這個線程放入就緒線程隊列，并把線程狀態(tài)改成就緒態(tài)。FindNextToRun方法根據(jù)調(diào)度策略，取出下一個應(yīng)運行的線程，并把這個線程從就緒線程隊列中刪除。如果就緒線程隊列為空，則此函數(shù)返回空(NULL)?，F(xiàn)有的調(diào)度策略是先進先出策略(FIFO)，Thread類的對象既用作線程的控制塊，相當于進程管理中的PCB，作用是保存線程狀態(tài)、進行一些統(tǒng)計，又是用戶調(diào)用線程系統(tǒng)的界面。用戶生成一個新線程的方法是:Thread* newThread = new Thread(New Thread);/ 生成一個線程類newThread-Fork(ThreadFunc，ThreadFuncArg);/ 定義新線

33、程的執(zhí)行函數(shù)及其參數(shù) Fork方法分配一塊固定大小的內(nèi)存作為線程的堆棧，在棧頂放入ThreadRoot的地址。當新線程被調(diào)上CPU時，要用SWITCH函數(shù)切換線程圖像，SWITCH函數(shù)返回時，會從棧頂取出返回地址，于是將ThreadRoot放在棧頂，在SWITCH結(jié)束后就會立即執(zhí)行ThreadRoot函數(shù)。ThreadRoot是所有線程的入口，它會調(diào)用Fork的兩個參數(shù)，運行用戶指定的函數(shù)；Yield方法用于本線程放棄處理機。Sleep方法可以使當前線程轉(zhuǎn)入阻塞態(tài)，并放棄CPU，直到被另一個線程喚醒，把它放回就緒線程隊列。在沒有就緒線程時，就把時鐘前進到一個中斷發(fā)生的時刻，讓中斷發(fā)生并處理此中

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

35、正文切換程序SWITCH可以做到這一點，于是A線程實際上并沒有被調(diào)下CPU，而是繼續(xù)運行下去了。Nachos線程管理 XE 線程管理 系統(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;/指

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

37、判斷鏈表是否為空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)度是線程管理 XE 線程管理 的重點。在Nachos中，線程是最小的調(diào)度單位，在同

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

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

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

41、步曲是：保存原運行線程的狀態(tài)恢復(fù)新運行線程的狀態(tài)在新運行線程的?？臻g上運行新線程3. 線程模塊分析（文件）Thread類實現(xiàn)了操作系統(tǒng)的線程控制塊，同操作系統(tǒng)課程中進程程管理中的PCB (Process Control Block) 有相似之處。Thread線程控制類較PCB為簡單的多，它沒有線程標識 (pid)、實際用戶標識 (uid)等和線程操作不是非常有聯(lián)系的部分，也沒有將PCB分成proc結(jié)構(gòu)和user結(jié)構(gòu)。這是因為一個Nachos線程是在宿主機上運行的。無論是系統(tǒng)線程和用戶進程，Thread線程控制類的實例都生成在宿主機而不是生成在虛擬機上。所以不存在實際操作系統(tǒng)中proc結(jié)構(gòu)常駐內(nèi)

42、存，而user結(jié)構(gòu)可以存放在盤交換區(qū)上的情況，將原有的兩個結(jié)構(gòu)合并是Nachos作的一種簡化。Nachos對線程的另一個簡化是每個線程棧段的大小是固定的，為4096-5個字 (word)，而且是不能動態(tài)擴展的。所以Nachos中的系統(tǒng)線程中不能使用很大的?？臻g，比如：void foo () int buff10000; .可能會不能正常執(zhí)行，如果需要使用很大空間，可以在Nachos的運行堆中申請：void foo () int *buf = new int10000; .如果系統(tǒng)線程需要使用的?？臻g大于規(guī)定?？臻g的大小，可以修改StackSize宏定義。Thread類的定義和實現(xiàn)如下所示：cl

43、ass Thread private:int* stackTop; /當前堆棧指針int machineStateMachineStateSize; /宿主機的運行寄存器 public:Thread(char* debugName);/初始化線程Thread(); /析構(gòu)方法void Fork(VoidFunctionPtr func, int arg); /生成一個新線程，執(zhí)行func(arg)void Yield(); /切換到其它線程運行void Sleep(); /線程進入睡眠狀態(tài)void Finish(); /線程結(jié)束時調(diào)用void CheckOverflow(); /測試線程棧段是

44、否溢出void setStatus(ThreadStatus st);/設(shè)置線程狀態(tài)char* getName() return (name); /取得線程名（調(diào)試用）void Print() printf(%s, , name); /打印當前線程名（調(diào)試用） private:int* stack;/線程的棧底指針ThreadStatus status;/當前線程狀態(tài)char* name;/線程名（調(diào)試用）void StackAllocate(VoidFunctionPtr func, int arg);/申請線程的?？臻g#ifdef USER_PROGRAMint userRegisters

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

46、serState(), RestoreUserState()方法就是為了用戶進程的切換設(shè)計的。Fork 方法 語法：void Fork (VoidFunctionPtr func, int arg) 參數(shù)：func:新線程運行的函數(shù)arg:func函數(shù)的參數(shù) 功能：線程初始化之后將線程設(shè)置成可運行的。 實現(xiàn)：申請線程棧空間初始化該?？臻g，使其滿足SWITCH函數(shù)進行線程切換的條件將該線程放到就緒隊列中。 返回：空StackAllocate 方法 語法：void StackAllocate (VoidFunctionPtr func, int arg) 參數(shù)：func:新線程運行的函數(shù)arg:f

47、unc函數(shù)的參數(shù) 功能：為一個新線程申請?？臻g，并設(shè)置好準備運行線程的條件。 實現(xiàn)：void Thread:StackAllocate (VoidFunctionPtr func, int arg)stack = (int *) AllocBoundedArray(StackSize * sizeof(int);/申請線程的?？臻gstackTop = stack + StackSize - 4;/設(shè)置棧首指針*(-stackTop) = (int)ThreadRoot;/線程準備好運行后進行線程切換，會切換到ThreadRoot函數(shù)。ThreadRoot函數(shù)/將會開中斷，并調(diào)用func(arg

48、)成為一個獨立的調(diào)度單位。*stack = STACK_FENCEPOST;/設(shè)置棧溢出標志 machineStatePCState = (int) ThreadRoot;/設(shè)置PC指針，從ThreadRoot開始運行 machineStateStartupPCState = (int) InterruptEnable; machineStateInitialPCState = (int) func; machineStateInitialArgState = arg; machineStateWhenDonePCState = (int) ThreadFinish;/以上是為ThreadRo

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

50、d就緒線程運行實現(xiàn)：如果是用戶線程，保存當前虛擬機的狀態(tài)檢查當前運行線程棧段是否溢出。（由于不是每時每刻都檢查棧段是否溢出，所以這時候線程的運行可能已經(jīng)出錯）將nextThread的狀態(tài)設(shè)置成運行態(tài)，并作為currentThread現(xiàn)運行線程（在調(diào)用Run方法之前，當前運行線程已經(jīng)放入就緒隊列中，變成就緒態(tài)）（以上是運行在現(xiàn)有的線程?？臻g上，以下是運行在nextThread的棧空間上）切換到nextThread線程運行釋放threadToBeDestroyed線程需要?？臻g（如果有的話）如果是用戶線程，恢復(fù)當前虛擬機的狀態(tài) 返回：空5.Nachos主控模塊分析（文件）該模塊是整個Nachos系

51、統(tǒng)的入口，它分析了Nachos的命令行參數(shù)，根據(jù)不同的選項進行不同功能的初始化設(shè)置。選項的設(shè)置如下所示：一般選項：-d:顯示特定的調(diào)試信息-rs:使得線程可以隨機切換-z:打印版權(quán)信息和用戶進程有關(guān)的選項：-s:使用戶進程進入單步調(diào)試模式-x:執(zhí)行一個用戶程序 XE 用戶程序 -c:測試終端輸入輸出和文件系統(tǒng)有關(guān)的選項：-f:格式化模擬磁盤-cp:將一個文件從宿主機拷貝到Nachos模擬磁盤上-p:將Nachos磁盤上的文件顯示出來-r:將一個文件從Nachos模擬磁盤上刪除-l:列出Nachos模擬磁盤上的文件-D:打印出Nachos文件系統(tǒng)的內(nèi)容-t:測試Nachos文件系統(tǒng)的效率和網(wǎng)絡(luò)有

52、關(guān)的選項：-n:設(shè)置網(wǎng)絡(luò)的可靠度（在0-1之間的一個小數(shù)）-m:設(shè)置自己的HostID-o:執(zhí)行網(wǎng)絡(luò)測試程序6. 同步機制模塊分析（文件）線程的同步和互斥是多個線程協(xié)同工作的基礎(chǔ)。Nachos提供了三種同步和互斥的手段：信號量、鎖機制以及條件變量機制，提供三種同步互斥機制是為了用戶使用方便。在同步互斥機制的實現(xiàn)中，很多操作都是原子操作。Nachos是運行在單一處理器上的操作系統(tǒng)，在單一處理器上，實現(xiàn)原子操作只要在操作之前關(guān)中斷即可，操作結(jié)束后恢復(fù)原來中斷狀態(tài)。6.1 信號量 ( Semaphore )Nachos已經(jīng)實現(xiàn)了Semaphore，它的基本結(jié)構(gòu)如下所示：class Semaphore

53、 public:void P(); /信號量的P操作void V(); /信號量的V操作 private:int value; /信號量值 ( =0)List *queue; /線程等待隊列;信號量的私有屬性有信號量的值，它是一個閥門。線程等待隊列中存放所有等待該信號量的線程。信號量有兩個操作：P操作和V操作，這兩個操作都是原子操作。6.1.1 P操作當value等于0時，將當前運行線程放入線程等待隊列。當前運行線程進入睡眠狀態(tài)，并切換到其它線程運行。當value大于0時，value-。 V操作如果線程等待隊列中有等待該信號量的線程，取出其中一個將其設(shè)置成就緒態(tài)，準備運行。value+;6.2

54、 鎖機制鎖機制是線程進入臨界區(qū)的工具。一個鎖有兩種狀態(tài)，BUSY和FREE。當鎖處于FREE態(tài)時，線程可以取得該鎖后進入臨界區(qū)，執(zhí)行完臨界區(qū)操作之后，釋放鎖；當鎖處于BUSY態(tài)時，需要申請該鎖的線程進入睡眠狀態(tài)，等到鎖為FREE態(tài)時，再取得該鎖。鎖的基本結(jié)構(gòu)如下所示：class Lock public:Lock(char* debugName); /初始化方法Lock();/析構(gòu)方法char* getName() return name; /取出鎖名（調(diào)試用）void Acquire(); /獲得鎖方法void Release(); /釋放鎖方法bool isHeldByCurrentThre

55、ad();/判斷鎖是否為現(xiàn)運行線程擁有 private:char* name;/鎖名（調(diào)試用）;在現(xiàn)有的Nachos中，沒有給出鎖機制的實現(xiàn)，鎖的基本結(jié)構(gòu)也只給出了部分內(nèi)容，其它內(nèi)容可以視實現(xiàn)決定?？傮w來說，鎖有兩個操作Acquire和Release，它們都是原子操作。6.3條件變量條件變量和信號量與鎖機制不一樣，它是沒有值的。（實際上，鎖機制是一個二值信號量，可以通過信號量來實現(xiàn)）當一個線程需要的某種條件沒有得到滿足時，可以將自己作為一個等待條件變量的線程插入所有等待該條件變量的隊列；只要條件一旦滿足，該線程就會被喚醒繼續(xù)運行。條件變量總是和鎖機制一同使用，它的基本結(jié)構(gòu)如下：class Co

56、ndition public:Condition(char* debugName);/初始化方法Condition();/析構(gòu)方法char* getName() return (name); /取出條件變量名（調(diào)試用）void Wait(Lock *conditionLock); /線程進入等待 void Signal(Lock *conditionLock); /喚醒一個等待該條件變量線程void Broadcast(Lock *conditionLock);/喚醒等待該條件變量的線程 private: char* name;/條件變量名（調(diào)試用）;在現(xiàn)有的Nachos中，沒有給出條件變量的

57、實現(xiàn)，條件變量的基本結(jié)構(gòu)也只給出了部分內(nèi)容，其它內(nèi)容可以視實現(xiàn)決定?？傮w來說，條件變量有三個操作Wait、Signal以及BroadCast，所有的這些操作必須在當前線程獲得一個鎖的前提下，而且所有對一個條件變量進行的操作必須建立在同一個鎖的前提下。理解Nachos中支持用戶進程的機制Nachos 對內(nèi)存、寄存器以及CPU的模擬Nachos機器模擬很重要的部分是內(nèi)存和寄存器的模擬。Nachos寄存器組模擬了全部32個MIPS XE MIPS 機（R2/3000 XE R2/3000 ）的寄存器，同時加上有關(guān)Nachos系統(tǒng)調(diào)試用的8個寄存器，以期讓模擬更加真實化并易于調(diào)試，對于一些特殊的寄存器

58、說明如下：寄存器名編號描述StackReg29用戶程序 XE 用戶程序 的堆棧指針RetAddrReg31存放過程調(diào)用的返回地址HiReg32存放乘法結(jié)果的高32位LoReg33存放乘法結(jié)果的低32位PCReg34當前PC指針NextPCReg35下一條執(zhí)行語句的PC指針PrevPCReg36上一條執(zhí)行語句的PC指針（調(diào)試用）LoadReg37需要延遲載入的寄存器編號LoadValueReg38需要延遲載入的寄存器值BadAddReg39當出錯陷入（Exception）時用戶程序 XE 用戶程序 的邏輯地址Nachos用宿主機的一塊內(nèi)存模擬自己的內(nèi)存。為了簡便起見，每個內(nèi)存頁的大小同磁盤扇區(qū)的

59、大小相同，而整個內(nèi)存的大小遠遠小于模擬磁盤的大小。由于Nachos是一個教學(xué)操作系統(tǒng)，在內(nèi)存分配上和實際的操作系統(tǒng)是有區(qū)別的。事實上，Nachos的內(nèi)存只有當需要執(zhí)行用戶程序 XE 用戶程序 時用戶程序的一個暫存地，而作為操作系統(tǒng)內(nèi)部使用的數(shù)據(jù)結(jié)構(gòu)不存放在Nachos的模擬內(nèi)存中，而是申請Nachos所在宿主機的內(nèi)存。所以Nachos的一些重要的數(shù)據(jù)結(jié)構(gòu)如線程控制結(jié)構(gòu)等的數(shù)目可以是無限的，不受Nachos模擬內(nèi)存大小的限制。這里需要強調(diào)的是，此處Nachos模擬的寄存器組同Thread類（第三章第三節(jié)）中的machineState數(shù)組表示的寄存器組不同，后者代表的是宿主機的寄存器組，是實際存在

60、的；而前者只是為了運行擁護程序模擬的。在用戶程序 XE 用戶程序 運行過程中，會有很多系統(tǒng)陷入核心的情況。系統(tǒng)陷入有兩大類原因：進行系統(tǒng)調(diào)用陷入和系統(tǒng)出錯陷入。系統(tǒng)調(diào)用陷入在用戶程序進行系統(tǒng)調(diào)用時發(fā)生。系統(tǒng)調(diào)用可以看作是軟件指令，它們有效地彌補了機器硬件指令不足；系統(tǒng)出錯陷入在系統(tǒng)發(fā)生錯誤時發(fā)生，比如用戶程序使用了非法指令以及用戶程序邏輯地址同實際的物理地址映射出錯等情況。不同的出錯陷入會有不同的處理，比如用戶程序邏輯地址映射出錯會引起頁面的重新調(diào)入，而用戶程序使用了非法指令則需要向用戶報告等等。Nachos處理的陷入有：需要注意的是，雖然這里的很多方法和屬性規(guī)定為public的，但是它們只能