(完整word版)Nachos中文教程(完整word版)Nachos中文教程PAGEPAGE3PAGE3(完整word版)Nachos中文教程TOC\o"1-5"第一章緒論 1第一節Nachos概述 1一、引言 1二、Nachos教學用操作系統 1第二節Nachos的實驗環境 4一、Nachos的安裝 4二、Nachos的目錄結構 4三、各個部分的編譯運行 4四、應用程序的編譯 5第二章機器模擬 6第一節概述 6第二節機器模擬的實現 101.Sysdep模塊分析（文件） 10PoolFile函數 10OpenForWrite函數 10OpenForReadWrite函數 10Read函數 10ReadPartial函數 11WriteFile函數 11Lseek函數 11Tell函數 11Close函數 11Unlink函數 12OpenSocket函數 12CloseSocket函數 12AssignNameToSocket函數 12DeAssignNameToSocket函數 12PoolSocket函數 12ReadFromSocket函數 13SendToSocket函數 13CallOnUserAbort函數 13Delay函數 13Abort函數 13Exit函數 14RandomInit函數 14Random函數 14AllocBoundedArray函數 14DeallocBoundedArray函數 142.中斷模塊分析（文件） 14PendingInterrupt類XE"Interrupt類" 16Interrupt類XE"Interrupt類" 17內部使用方法 17內部使用函數 18對外接口 183.時鐘中斷模塊分析（文件） 204.終端設備模塊分析（文件） 225.磁盤設備模塊分析（文件） 236.Nachos運行情況統計（文件） 24第三章線程管理XE"線程管理"系統 25第一節進程與線程 25一、進程 251.進程概念 252.進程的狀態及狀態變化 253.進程調度 264.進程之間的同步和互斥 275.進程的實施 286.進程的創建 28二、線程 291.線程概念 292.進程和線程的關系 30第二節Nachos的線程管理XE"線程管理" 31一、Nachos的線程管理XE"線程管理" 31二、Nachos線程管理XE"線程管理"同實際進程管理的不同 33第三節Nachos線程管理XE"線程管理"系統的初步實現 341.工具模塊分析（文件） 342.線程啟動和調度模塊分析（文件） 34ThreadRoot函數 34SWITCH函數 353.線程模塊分析（文件） 35Fork方法 37StackAllocate方法 38Yield方法 39Sleep方法 404.線程調度算法模塊分析（文件） 40Run方法 415.Nachos主控模塊分析（文件） 416.同步機制模塊分析（文件） 42信號量(Semaphore) 42鎖機制 42條件變量 43第四節線程管理XE"線程管理"系統作業 45第五節實現實例 47對線程的改進 47對線程調度的改進 48第四章文件管理系統 51第一節文件管理系統概述 51一、文件 511.文件結構 512.文件訪問 523.文件類型 524.文件屬性 535.文件操作 53二、目錄 541.目錄結構 542.多級目錄結構 553.文件路徑名 554.工作目錄 555.目錄結構的勾連 556.目錄項 56三、UNIX文件系統的實現 561.UNIX文件系統中的主要結構 562.UNIX文件系統存儲資源的分配和回收 58第二節Nachos文件管理系統 61第三節Nachos文件系統的實現 631.同步磁盤分析（文件、） 632.位圖模塊分析（文件、） 643.文件系統模塊分析（文件、） 64生成方法 65Create方法 65Open方法 66Remove方法 664.文件頭模塊分析（文件、） 665.打開文件結構分析（文件、） 67ReadAt方法 67WriteAt方法 686.目錄模塊分析（文件） 68第四節文件管理系統作業 70第五章用戶程序XE"用戶程序"和虛擬內存XE"虛擬內存" 71第一節Nachos對內存、寄存器以及CPU的模擬 711RaiseException方法 742ReadMem方法 743WriteMem方法 744Translate方法 745Run方法 75第二節Nachos用戶進程運行機制 77一、用戶程序XE"用戶程序"空間（文件,） 77生成方法 77InitRegisters方法 78SaveState方法 78RestoreState方法 78二、系統調用（文件,,） 78第三節虛存管理的設計和實現 80一、Nachos存儲管理的改進要求 80二、一個虛擬存儲管理實現的實例 80虛擬存儲系統的總體設計 80缺頁中斷陷入及其調度算法 83虛存的存儲分配 85存儲保護 85實現中的一些細節 85第四節用戶程序XE"用戶程序"和虛擬存儲作業 87第六章Nachos的網絡系統 88第一節Nachos對物理網絡的模擬 88第二節Nachos的郵局協議 91PostalDelivery方法 92Send方法 93第三節網絡部分作業 94第一章 緒論第一節 Nachos概述一、引言計算機操作系統是一門實踐性很強的課程。一般地闡述其工作原理，很可能使本來具體生動的內容變得十分抽象、枯燥并難以理解。解決好理論與實踐相結合的問題是提高操作系統教學質量的關鍵。一門好的操作系統實踐課將使讀者更加形象和深刻地理解課堂中講述的概念、原理和它們的應用。國內外許多著名的大學都在操作系統教學實踐方面作了大量研究，比較突出的有著名計算機專家設計和實現的MINIXXE"MINIX"。MINIX是一個比較完整的操作系統，它的用戶界面類似于UNIX。說它比較完整，是因為它包括了進程管理、文件系統管理XE"文件系統管理"、存儲管理、設備管理以及I/O管理等操作系統的所有重要內容，而且還包含了系統啟動和Shell等實際操作系統不可缺少的部分。由于MINIX較UNIX的出現晚十年，所以在程序風格上較原來的UNIX要好得多，更加結構化和模塊化。包含有3000行注釋的12000行源代碼使整個系統較為容易閱讀和理解。但是MINIX作為教學用操作系統有它的不足之處，就是由于它的目標是一個完整的操作系統，必然要和具體的設備打交道；而且不同的機器指令集需要有不同的編譯器，所以MINIX的移植性并不令人滿意。一個MINIX操作系統需要占據一臺獨立的主機，所以在網絡的配置和實現上比較復雜，讀者需要有一定的實踐經驗才能完成。上海交通大學開發的MOSXE"MOS"操作系統是另一個較成功的教學用操作系統。它是一個小型而功能較齊全的多道程序的操作系統，主要包括作業調度管理和文件系統管理XE"文件系統管理"，建立在一個只包含十幾條指令的指令集虛擬機基礎之上。由于MOS比較簡單，讀者可以非常容易地理解操作系統課程中講述的進程調度和文件系統等部分原理。MOS的不足是過于簡單，不能涵蓋操作系統的大部分功能。MOS的虛擬機指令集是自定義的，沒有現成的編譯器，所以讀者必須直接編寫匯編程序才能在MOS虛擬機上運行。這樣就缺乏開發大型應用程序的能力。但是MOS畢竟給了讀者一個自由發揮的空間，在MOS的基礎上衍生出TOSXE"TOS"等學生自己定義和實現的相對完整的操作系統。二、Nachos教學用操作系統作為教學用操作系統，需要實現簡單并且盡量縮小與實際操作系統之間的差距，所以我們采用Nachos作為操作系統課程的教學實踐平臺。Nachos是美國加州大學伯克萊分校在操作系統課程中已多次使用的操作系統課程設計平臺，在美國很多大學中得到了應用，它在操作系統教學方面具有一下幾個突出的優點：采用通用虛擬機Nachos是建立在一個軟件模擬的虛擬機之上的，模擬了MIPSXE"MIPS"R2/3000XE"R2/3000"的指令集、主存、中斷系統、網絡以及磁盤系統等操作系統所必須的硬件系統。許多現代操作系統大多是先在用軟件模擬的硬件上建立并調試，最后才在真正的硬件上運行。用軟件模擬硬件的可靠性比真實硬件高得多，不會因為硬件故障而導致系統出錯，便于調試。虛擬機可以在運行時報告詳盡的出錯信息，更重要的是采用虛擬機使Nachos的移植變得非常容易，在不同機器上移植Nachos，只需對虛擬機部分作移植即可。采用R2/3000XE"R2/3000"指令集的原因是該指令集為RISC指令集，其指令數目比較少。Nachos虛擬機模擬了其中的63條指令。由于R2/3000指令集是一個比較常用的指令集，許多現有的編譯器如gc++能夠直接將C或C++源程序編譯成該指令集的目標代碼，于是就不必編寫編譯器，讀者就可以直接用C/C++語言編寫應用程序，使得在Nachos上開發大型的應用程序也成為可能。使用并實現了操作系統中的一些新的概念隨著計算機技術和操作系統技術的不斷發展，產生了很多新的概念。Nachos將這些新概念融入操作系統教學中，包括網絡、線程和分布式應用。而且Nachos以線程作為一個基本概念講述，取代了進程在以前操作系統教學中的地位。Nachos的虛擬機使得網絡的實現相當簡單。與MINIXXE"MINIX"不同，Nachos只是一個在宿主機上運行的一個進程。在同一個宿主機上可以運行多個Nachos進程，各個進程可以相互通訊，作為一個全互連網絡的一個節點；進程之間通過Socket進行通訊，模擬了一個全互連網絡。確定性調試比較方便；隨機因素使系統運行更加真實因為操作系統的不確定性，所以在一個實際的系統中進行多線程調試是比較困難的。由于Nachos是在宿主機上運行的進程，它提供了確定性調試的手段。所謂確定性調試，就是在同樣的輸入順序、輸入參數的情況下，Nachos運行的結果是完全一樣的。在多線程調試中，可以將注意力集中在某一個實際問題上，而不受操作系統不確定性的干擾。另外，不確定性是操作系統所必須具有的特征，Nachos采用了隨機因子模擬了真實操作系統的不確定性。簡單而易于擴展Nachos是一個教學用操作系統平臺，它必須簡單而且有一定的擴展余地。Nachos不是向讀者展示一個成功的操作系統，而是讓讀者在一個框架下發揮自己的創造性進行擴展。例如一個完整的類似于UNIX的文件系統是很復雜的，但是對于文件系統來說，無非是需要實現文件的邏輯地址到物理地址的映射以及實現文件inode、打開文件結構、線程打開文件表等重要的數據結構以及維護它們之間的關系。Nachos中具有所有這些內容，但是在很多方面作了一定的限制，比如只有一級索引結構限制了系統中最大文件的大小。讀者可以應用學到的各種知識對文件系統進行擴展，逐步消除這些限制。Nachos在每一部分給出很多課程作業，作為讀者進行系統擴展的提示和檢查對系統擴展的結果。面向對象性Nachos的主體是用C++的一個子集來實現的。目前面向對象語言日漸流行，它能夠清楚地描述操作系統各個部分的接口。Nachos沒有用到面向對象語言的所有特征，如繼承性、多態性等，所以它的代碼就更容易閱讀和理解。以下各章分五個部分講述Nachos的各個部分以及它們的功能。它們是機器模擬、線程管理XE"線程管理"、文件系統管理XE"文件系統管理"、用戶程序XE"用戶程序"和虛擬存儲以及網絡系統。各章的安排是：第二章分析Nachos虛擬機的各個部分，包括中斷系統、定時器、以及一些外部設備，如磁盤、鍵盤和顯示器。Nachos的應用程序將在這個虛擬機上運行。第三章分析Nachos如何實現多線程機制以及Nachos的線程管理XE"線程管理"方法。Nachos沒有借助于屬主UNIX操作系統的多進程機制，而是通過編寫自己的進程圖象切換函數來實現多線程。該部分對Nachos的進程圖象切換函數作了詳細介紹。第四章分析Nachos的文件系統。Nachos原有的文件系統非常簡單，該部分在分析原有文件系統的基礎上提出了對文件系統的擴展要求。第五章介紹用戶程序XE"用戶程序"和虛擬存儲。該部分補充介紹了Nachos對虛擬機內存、寄存器以及CPU的模擬。現有的Nachos系統沒有實現虛擬內存XE"虛擬內存"，當一個用戶進程的邏輯地址空間較大時，就不能在現有Nachos上運行。該部分提出了虛擬內存的概念，并且給出了一個實例。第六章論述了Nachos的網絡系統，Nachos的網絡部分實現了不可靠的定長報文XE"報文"傳送，在此之上需要建立可靠的網絡，并實現網絡應用程序。PAGE50第二節 Nachos的實驗環境一、Nachos的安裝本書的實際實驗環境是LinuxXE"Linux"，Nachos可以運行在內核版本以上的各種Linux版本，包括Slackware和Redhat。編譯器的版本是版本以上。本書附有一張軟盤，磁盤的格式為DOS格式，磁盤上有一個名為“的壓縮文件。學生需要將此文件拷貝到自己的工作目錄下：~/$ mcopya:.并將其解開：~/$ gzip-dc|tarxf-二、Nachos的目錄結構以上操作系統可以發現在工作目錄下生成一個名為的目錄。該目錄中含有：copyright文件Nachos的版權信息readme文件Nachos的readme信息文件Nachos的介紹文檔（Postscript格式）c++example目錄有關C++介紹和實例doc目錄Nachos各個部分介紹和原有的作業要求code目錄Nachos各個部分的源代碼最主要的部分是Nachos的源代碼部分。它的目錄結構是：Makefile文件文件文件Nachos的Makefile文件。當Nachos需要移植到其它系統時，可以修改中的HOST參數machine目錄Nachos虛擬機模擬部分源代碼threads目錄Nachos線程管理XE"線程管理"部分源代碼filesys目錄Nachos文件系統管理XE"文件系統管理"部分源代碼userprog目錄Nachos用戶程序XE"用戶程序"部分源代碼network目錄Nachos網絡管理XE"網絡管理"部分源代碼vm目錄Nachos虛擬內存XE"虛擬內存"管理部分源代碼test目錄一些測試用應用程序bin目錄包含有用戶程序XE"用戶程序"目標碼變換的程序三、各個部分的編譯運行Nachos的各個部分都可以獨立編譯運行，也可以同時編譯各個部分。全部編譯可以采用如下命令： ~/$ make當需要單獨編譯線程管理XE"線程管理"部分時，先進入threads目錄，然后采用如下命令： ~/threads$ makedepend ~/threads$ makenachos實際上，各部分目錄下都有一個Makefile文件，內容大體相同，區別在于一些條件編譯的參數。比如在單獨編譯線程管理XE"線程管理"部分時，文件管理部分就被屏蔽了，這樣讀者讀者就可以專心于線程管理部分的調試。四、應用程序的編譯由于Linux指令集和R2/3000XE"R2/3000"指令集不同，用戶編寫的應用程序用Linux系統中標準gcc編譯后，不能直接在Nachos虛擬機環境下運行。所以需要采用交叉編譯技術。所謂交叉編譯技術是在一個操作系統下將源碼編譯成另一個操作系統的目標碼，這里就是在Linux下通過gcc交叉編譯版本將用戶程序XE"用戶程序"的源碼編譯成R2/3000指令集的目標碼。在Linux中，沒有缺省的交叉編譯工具。讀者可以到上海交通大學計算機系FTP服務器上下載，URL為: ，將解開至/usr/local/目錄下：/# gzip-dc|tarxf-在編譯用戶程序XE"用戶程序"時，用交叉編譯器將源碼編譯成R2/3000XE"R2/3000"指令集的目標代碼，再經過一個簡單的轉換就可以在Nachos虛擬機上運行。注意，在讀者實現虛擬存儲之前，有些應用程序可能會因為使用過多的內存而不能運行。第二章 機器模擬第一節 概述Nachos是建立在一個軟件模擬的虛擬機上的。該虛擬機包括計算機的基本部分：如CPU、主存、寄存器、中斷系統，還包括一些外部設備，如終端設備、網絡以及磁盤系統。現代許多操作系統都是先在軟件模擬的硬件上建立并調試，最后才在真正的硬件上運行。軟件模擬的硬件可靠性比真實的硬件高的多，不會因為硬件故障而導致系統出錯，因而便于調試。模擬的硬件還可以監視程序對硬件的操作，并加以嚴格的限制，在程序誤操作時報告詳盡的出錯信息。這些都是真實硬件難以做到的。用軟件來模擬硬件另一個優點是充分利用了宿主機操作系統的軟件資源，避免了編寫復雜的硬件控制程序。更重要的是提高了程序的可移植性，只要在不同硬件上實現Nachos虛擬機就完成了Nachos的大部分移植工作。我們將Nachos移植到Linux上的工作就受益于這種設計。下面對Nachos的機器模擬部分作概要說明。Nachos是用C++語言中的類來表示各個對象的。其中Machine類XE"Machine類"用來模擬計算機主機。它提供的功能有：讀寫寄存器。讀寫主存、運行一條用戶程序XE"用戶程序"的匯編指令、運行用戶程序、單步調試用戶程序、顯示主存和寄存器狀態、將虛擬內存XE"虛擬內存"地址轉換為物理內存地址、陷入Nachos內核等等。Machine類XE"Machine類"實現方法是在宿主機上分配兩塊內存分別作為虛擬機的寄存器和物理內存。運行用戶程序XE"用戶程序"時，先將用戶程序從Nachos文件系統中讀出，寫入模擬的物理內存中，然后調用指令模擬模塊對每一條用戶指令解釋執行。將用戶程序的讀寫內存要求，轉變為對物理內存地址的讀寫。Machine類提供了單步調試用戶程序的功能，執行一條指令后會自動停下來，讓用戶查看系統狀態，不過這里的單步調試是匯編指令級的，需要讀者對R2/3000XE"R2/3000"指令比較熟悉。如果用戶程序想使用操作系統提供的功能或者發出異常信號時，Machine調用系統異常陷入功能，進入Nachos的核心部分。Interrupt類XE"Interrupt類"用來模擬硬件中斷系統。在這個中斷系統中，中斷狀態有開，關兩種，中斷類型有時鐘中斷、磁盤中斷、控制臺寫中斷、控制臺讀中斷、網絡發送中斷以及網絡接收中斷。機器狀態有用戶態，核心態和空閑態。中斷系統提供的功能有開/關中斷，讀/寫機器狀態，將一個即將發生中斷放入中斷隊列，以及使機器時鐘前進一步。在Interrupt類XE"Interrupt類"中有一個記錄即將發生中斷的隊列，稱為中斷等待隊列。中斷等待隊列中每個等待處理的中斷包含中斷類型、中斷處理程序的地址及參數、中斷應當發生的時間等信息。一般是由硬件設備模擬程序把將要發生的中斷放入中斷隊列。中斷系統提供了一個模擬機器時鐘，機器時鐘在下列情況下前進（詳見第二節對中斷模塊的分析）:用戶程序XE"用戶程序"打開中斷執行一條用戶指令處理機沒有進程正在運行機器時鐘前進時，中斷處理的過程如下圖所示:圖 Nachos中斷處理時機NYNY進行正文切換中斷處理程序要求進行正文切換開中斷取出隊列中一個應當發生的中斷，調用這個中斷的處理程序去處理中斷中斷隊列中有應當發生的中斷關中斷圖 Nachos中斷處理時機NYNY進行正文切換中斷處理程序要求進行正文切換開中斷取出隊列中一個應當發生的中斷，調用這個中斷的處理程序去處理中斷中斷隊列中有應當發生的中斷關中斷所以，在Nachos中只有在時鐘前進時，才會檢查是否有中斷會發生，而Nachos模擬時鐘前進的時機不是任意的，這樣即使打開了中斷，中斷也不能在任意時刻發生。只有在模擬時鐘前進的時候才能處理等待著的中斷。通過以后的敘述我們可以看到，在執行非用戶代碼的大部分時間里，系統不會被中斷。這意味著不正確的同步代碼可能在這個硬件模擬環境下工作正常，而實際上在真正的硬件上是無法正確運行的。在有些中斷處理程序的最后可能要進行正文切換，可以通過調用Interrupt類的一個成員函數來要求時鐘前進的時候進行正文切換。中斷系統還提供關機的功能，當系統中沒有正在運行的進程同時系統中沒有除了時鐘中斷以外的其它中斷時，Nachos結束運行。在這個中斷系統基礎上，Nachos模擬了各種硬件設備，這些設備都是異步設備，依靠中斷來與主機通信。Timer類XE"Timer類"模擬定時器。定時器每隔X個時鐘周期就向CPU發一個時鐘中斷。它是時間片管理必不可少的硬件基礎。它的實現方法是將一個即將發生的時鐘中斷放入中斷隊列，到了時鐘中斷應發生的時候，中斷系統將處理這個中斷，在中斷處理的過程中又將下一個即將發生的時鐘中斷放入中斷隊列，這樣每隔X個時鐘周期，就有一個時鐘中斷發生。由于Nachos是一個軟件模擬的系統，有很多的隨機事件需要通過一定的控制來實現。所以系統中在計算下一個時鐘中斷應發生的時間時，還加入了一些隨機值，使得中斷發生的時間間隔不確定，這樣就與現實的定時器更相似。Console類XE"Console類"模擬的是控制臺設備。當用戶程序XE"用戶程序"向控制臺寫一個字符時，寫程序立即返回，過了給定的時鐘周期后I/O操作完成，控制臺向CPU發一個控制臺寫中斷。但是控制臺是否有用戶輸入可供讀取是隨機的，所以控制臺每隔給定的時鐘周期向CPU發一個控制臺讀中斷，周期性地發中斷的方法與定時器的類似，即先計算下一個控制臺讀中斷將發生的時間，然后將讀中斷放入中斷隊列，等待讀中斷的發生。讀中斷發生后，如果有用戶輸入的話，控制臺讀中斷處理過程將控制臺輸入的字符放入字符緩沖區。當用戶從控制臺讀字符時，把字符緩沖區的內容傳給用戶。控制臺的讀/寫分別用兩個文件來模擬。Disk類XE"Disk類"模擬了物理磁盤，它一次只能接受一個讀寫請求，當讀寫操作完成后向CPU發一個磁盤中斷。該物理磁盤只有一個面，分為幾個磁道，每道又分為幾個扇區。每道的扇區數，每個扇區的存儲容量都是固定的。磁盤的使用者可以讀寫指定的扇區，讀寫單位是一個扇區。模擬磁盤用宿主機文件系統中一個文件來實現，當用戶發出讀寫請求時，Nachos的處理過程如下:從模擬文件中讀出數據或向模擬文件寫入數據。計算磁盤操作需要的時間。磁盤操作時間=移動磁頭尋道的時間+旋轉到讀寫扇區的時間+數據傳送的時間。將一個磁盤讀/寫中斷放入中斷隊列，因為中斷是在操作完成后發生的。所以，中斷發生時間=當前時間+磁盤操作時間。每個Nachos運行時是宿主機上的一個進程，如果在宿主機上運行多個Nachos進程，這些Nachos進程可以組成一個網絡，而每個Nachos進程就是一個網絡節點。Network類XE"Network類"模擬了一個網絡節點。這個網絡節點可以把報文XE"報文"發送到網絡的其他節點上。報文的長度固定，Nachos模擬了在現實網絡中時常發生的報文丟失的情況；但是報文中的內容不會在網絡傳送中被修改破壞。每個網絡節點都有全網絡唯一的“地址”，報文傳送的起始節點、目的節點都是由這個“地址”表示。報文XE"報文"在網絡中的傳遞是用通過Socket（套接口）XE"Socket（套接口）"來實現的。每個節點還有一個可靠性系數，用來模擬報文從這個節點發出后丟失的概率。Network的實現與控制臺類似，每隔一定的時鐘周期，就產生一個網絡接收中斷，網絡接收中斷處理過程是:將下一個網絡接收中斷放入中斷隊列以實現中斷的周期性發生。如果報文XE"報文"緩沖區中已有報文，則返回。讀取套接口，如果沒有報文XE"報文"，則返回。讀取報文XE"報文"，把它放入報文緩沖區。調用本節點自定義的接收處理函數。在現有實現中，報文XE"報文"緩沖區只能存放一個報文，有可能因為報文緩沖區滿而造成報文丟失（上面第2行），可以多設幾個報文緩沖區來減少丟失的可能性。Network類XE"Network類"提供了讓網絡用戶讀取已經收到的報文XE"報文"的成員函數，當報文緩沖區為空時，它返回空，否則從報文緩沖區讀出報文，并將報文緩沖區清空，返回剛讀出的報文。報文XE"報文"發送的過程是:將網絡發送中斷放入中斷隊列。產生一個隨機數。如果這個隨機數大于網絡的可靠性系數，則不發送報文XE"報文"(用來模擬報文丟失)，否則通過套接口將報文發送出去。從以上的敘述中可以看出，中斷系統成為整個Nachos虛擬機的基礎，其它的模擬硬件設備都是建立在中斷系統之上的。在此之上，加上Machine類XE"Machine類"模擬的指令解釋器，可以實現Nachos的線程管理XE"線程管理"、文件系統管理XE"文件系統管理"、虛擬內存XE"虛擬內存"、用戶程序XE"用戶程序"和網絡管理XE"網絡管理"等所有操作系統功能。圖展示了Nachos系統的整體結構。用戶程序線程管理XE"線程管理"網絡協議文件系統虛擬內存XE"虛擬內存"終端設備時鐘網絡磁盤中斷系統指令解釋和內存模擬圖 Nachos系統的整體結構第二節 機器模擬的實現1.Sysdep模塊分析（文件）Nachos的運行環境可以是多種操作系統，由于每種操作系統所提供的系統調用或函數調用在形式和內容上可能有細微的差別。sysdep模塊的作用是屏蔽掉這些差別。PoolFile函數語法：boolPoolFile(intfd)參數：fd: 文件描述符，也可以是一個套接字(socket)功能：測試一個打開文件fd是否有內容可以讀，如果有則返回TRUE，否則返回FALSE。當Nachos系統處于IDLE狀態時，測試過程有一個延時，也就是在一定時間范圍內如果有內容可讀的話，同樣返回TRUE。實現：通過select系統調用。返回：打開文件是否有內容供讀取。OpenForWrite函數語法：intOpenForWrite(char*name)參數：name: 文件名功能：為寫操作打開一個文件。如果該文件不存在，產生該文件；如果該文件已經存在，則將該文件原有的內容刪除。實現：通過open系統調用。返回：打開的文件描述符。OpenForReadWrite函數語法：intOpenForReadWrite(char*name,boolcrashOnError)參數：name: 文件名crashOnError: crash標志功能：為讀寫操作打開一個文件。當crashOnError標志設置而文件不能讀寫打開時，系統出錯退出。實現：通過open系統調用。返回：打開的文件描述符。Read函數語法：voidRead(intfd,char*buffer,intnBytes)參數：fd: 打開文件描述符buffer: 讀取內容的緩沖區nBytes: 需要讀取的字節數功能：從一個打開文件fd中讀取nBytes的內容到buffer緩沖區。如果讀取失敗，系統退出。實現：通過read系統調用。返回：無。注意：這和系統調用read不完全一樣。read系統調用返回的是實際讀出的字節數，而Read函數則必須讀出nBytes，否則系統將退出。如果需要使用同read系統調用相對應的函數，請用ReadPartial。

ReadPartial函數語法：intReadPartial(intfd,char*buffer,intnBytes)參數：fd: 打開文件描述符buffer: 讀取內容的緩沖區nBytes: 需要讀取的最大字節數功能：從一個打開文件fd中讀取nBytes的內容到buffer緩沖區。實現：通過read系統調用。返回：實際讀出的字節數。WriteFile函數語法：voidWriteFile(intfd,char*buffer,intnBytes)參數：fd: 打開文件描述符buffer: 需要寫的內容所在的緩沖區nBytes: 需要寫的內容最大字節數功能：將buffer緩沖區中的內容寫nBytes到一個打開文件fd中。實現：通過write系統調用。返回：無。注意：這和系統調用write不完全一樣。write系統調用返回的是實際寫入的字節數，而WriteFile函數則必須寫入nBytes，否則系統將退出。Lseek函數語法：voidLseek(intfd,intoffset,intwhence)參數：fd: 文件描述符offset: 偏移量whence: 指針移動的起始點功能：移動一個打開文件的讀寫指針，含義同lseek系統調用；出錯則退出系統。實現：通過lseek系統調用。返回：無。Tell函數語法：intTell(intfd)參數：fd: 文件描述符功能：指出當前讀寫指針位置實現：通過lseek系統調用。返回：返回當前指針位置。Close函數語法：voidClose(intfd)參數：fd: 文件描述符功能：關閉當前打開文件fd，如果出錯則退出系統。實現：通過close系統調用。返回：無。

Unlink函數語法：boolUnlink(char*name)參數：name: 文件名功能：刪除文件。實現：通過unlink系統調用。返回：刪除成功，返回TRUE；否則返回FALSE。OpenSocket函數語法：intOpenSocket()參數：無功能：申請一個socket。實現：通過socket系統調用。其中AF_UNIX參數說明使用UNIX內部協議。（Nachos是用SOCKET文件來模擬網絡節點，所以采用UNIX內部協議。向該文件讀寫內容分別代表從該節點讀取內容和向該網絡節點發送內容）SOCK_DGRAM參數說明采用無連接定長數據包型的數據鏈路。返回：申請到的socketID。CloseSocket函數語法：voidCloseSocket(intsockID)參數：sockID: socket標識功能：釋放一個socket。實現：通過close系統調用。返回：無。AssignNameToSocket函數語法：voidAssignNameToSocket(char*socketName,intsockID)參數：socketName: socket文件名sockID: socket標識功能：將一個文件名和一個socket標識聯系起來，于是將一個SOCKET文件同一個Nachos進程連接起來，使宿主機上該Nachos進程成為一個網絡節點。實現：通過bind系統調用。返回：無。DeAssignNameToSocket函數語法：voidDeAssignNameToSocket(char*socketName)參數：socketName: socket文件名功能：將一個文件名刪除，實際上是和相應的socket標識脫離關系。實現：通過unlink系統調用。返回：無。PoolSocket函數語法：boolPoolSocket(intsockID)參數：socketID: socket標識功能：查詢一個socket是否有內容可以讀取。實現：調用PoolFile。在UNIX中socket標識和普通的文件標識沒有本質的區別，可以采用相同的方式操作；Nachos中的網絡收發信息的模擬實際上是文件操作。返回：socket中有內容，返回TRUE；否則返回FALSE。ReadFromSocket函數語法：voidReadFromSocket(intsockID,char*buffer,intpacketSize)參數：socketID: socket標識buffer: 讀取內容的暫存空間packetSize: 讀取數據包的大小功能：從一個socket標識中讀取packetSize大小的數據包，放在buffer緩沖中。實現：通過recvfrom系統調用。返回：無。SendToSocket函數語法：voidSendToSocket(intsockID,char*buffer,intpacketSize,char*toName)參數：socketID: socket標識buffer: 發送內容的暫存空間packetSize: 發送數據包的大小toName: 要接收數據包的Nachos虛擬機模擬網絡文件的文件名功能：向socket標識中發送packetSize大小的數據包。實現：通過sendto系統調用。Nachos的網絡處理中斷程序會檢查和自己相連的模擬網絡SOCKET文件中是否有內容可讀。當Nachos需要向其它節點發送信息時，需要指明其它節點的地址，實際上就是和其它節點相連的模擬網絡SOCKET文件名。返回：無。CallOnUserAbort函數語法：voidCallOnUserAbort(VoidNoArgFunctionPtrfunc)參數：func: 函數指針功能：設定一個函數，在用戶強制退出系統時調用。實現：通過signal系統調用。返回：無。Delay函數語法：voidDelay(intseconds)參數：seconds: 需要延遲的秒數功能：系統延遲一定的時間。實現：通過sleep系統調用。返回：無。Abort函數語法：voidAbort()參數：無功能：退出系統(非正常退出)。實現：通過abort系統調用。返回：無。Exit函數語法：voidExit(intexitCode)參數：exitCode: 向系統的返回值功能：退出系統。實現：通過exit系統調用。返回：無。RandomInit函數語法：voidRandomInit(unsignedseed)參數：seed: 隨機數產生魔數功能：初始化隨機數發生器。實現：通過srand系統調用。返回：無。Random函數語法：intRandomInit()參數：無功能：產生一個隨機整數。實現：通過rand系統調用。返回：產生的隨機整數。AllocBoundedArray函數語法：char*AllocBoundedArray(intsize)參數：size: 需要申請的空間大小功能：申請一個受保護的存儲空間。實現：通過mprotect的系統調用，申請一塊比size較大的空間，并且在要申請空間兩頭區域的屬性設置成不可訪問；當用戶使用不當時（使用到受保護范圍之外時），系統會接收到SIGSEGV信號。不是每個操作系統都支持這樣的內存申請，如果支持的話，對監測內存的使用是否恰當非常有用。返回：申請成功后指針，該指針指向可以訪問的申請空間，而不是指向受限區域的開始。DeallocBoundedArray函數語法：voidDeallocBoundedArray(char*ptr,intsize)參數：ptr: 要釋放空間的指針size: 申請的空間大小功能：將受保護的存儲空間釋放。實現：通過mprotect系統調用；釋放的空間包括頭尾受限區域，所以必須知道原來申請區域的大小。返回：無。2. 中斷模塊分析（文件）中斷模塊的主要作用是模擬底層的中斷機制。可以通過該模擬機制來啟動和禁止中斷(SetLevel)；該中斷機制模擬了Nachos系統需要處理的所有的中斷，包括時鐘中斷、磁盤中斷、終端讀/終端寫中斷以及網絡接收/網絡發送中斷。中斷的發生總是有一定的時間。比如當向硬盤發出讀請求，硬盤處理請求完畢后會發生中斷；在請求和處理完畢之間需要經過一定的時間。所以在該模塊中，模擬了時鐘的前進。為了實現簡單和便于統計各種活動所占用的時間起見，Nachos規定系統時間在以下三種情況下前進：執行用戶態指令執行用戶態指令，時鐘前進是顯而易見的。我們認為，Nachos執行每條指令所需時間是固定的，為一個時鐘單位(Tick)。重新打開中斷一般系統態在進行中斷處理程序時，需要關中斷。但是中斷處理程序本身也需要消耗時間，而在關閉中斷到重新打開中斷之間無法非常準確地計算時間，所以當中斷重新打開的時候，加上一個中斷處理所需時間的平均值。就緒隊列中沒有進程當系統中沒有就緒進程時，系統處于Idle狀態。這種狀態可能是系統中所有的進程都在等待各自的某種操作完成。也就是說，系統將在未來某個時間發生中斷，到中斷發生的時候中斷處理程序將進行中斷處理。在系統模擬中，有一個中斷等待隊列，專門存放將來發生的中斷。在這種情況下，可以將系統時間直接跳到中斷等待隊列第一項所對應的時間，以免不必要的等待。當前面兩種情況需要時鐘前進時，調用OneTick方法。OneTick方法將系統態和用戶態的時間分開進行處理，這是因為用戶態的時間計算是根據用戶指令為單位的；而在系統態，沒有辦法進行指令的計算，所以將系統態的一次中斷調用或其它需要進行時間計算的單位設置為一個固定值，假設為一條用戶指令執行時間的10倍。雖然Nachos模擬了中斷的發生，但是畢竟不能與實際硬件一樣，中斷發生的時機可以是任意的。比如當系統中沒有就緒進程時，時鐘直接跳到未處理中斷隊列的第一項的時間。這實際情況下，系統處于Idel狀態到中斷等待隊列第一項發生時間之間，完全有可能有其它中斷發生。由于中斷發生的時機不是完全隨機的，所以在Nachos系統中運行的程序，不正確的同步程序也可能正常運行，我們在此需要密切注意。Nachos線程運行有三種狀態：Idle狀態系統CPU處于空閑狀態，沒有就緒線程可以運行。如果中斷等待隊列中有需要處理的除了時鐘中斷以外的中斷，說明系統還沒有結束，將時鐘調整到發生中斷的時間，進行中斷處理；否則認為系統結束所有的工作，退出。系統態 Nachos執行系統程序。Nachos雖然模擬了虛擬機的內存，但是Nachos系統程序本身的運行不是在該模擬內存中，而是利用宿主機的存儲資源。這是Nachos操作系統同真正操作系統的重要區別。用戶態系統執行用戶程序XE"用戶程序"。當執行用戶程序時，每條指令占用空間是Nachos的模擬內存（見第五章）。Nachos需要處理的中斷種類有：TimerInt:時鐘中斷DiskInt:磁盤（讀/寫）中斷ConsoleWriteInt:終端寫中斷ConsoleReadInt:終端讀終端NetworkSentInt:網絡發送中斷NetworkRecvInt:網絡接收中斷中斷等待隊列是Nachos虛擬機最重要的數據結構之一，它記錄了當前虛擬機可以預測的將在未來發生的所有中斷。當系統進行了某種操作可能引起未來發生的中斷時，如磁盤的寫入、向網絡寫入數據等都會將中斷插入到中斷等待隊列中；對于一些定期需要發生的中斷，如時鐘中斷、終端讀取中斷等，系統會在中斷處理后將下一次要發生的中斷插入到中斷等待隊列中。中斷的插入過程是一個優先隊列的插入過程，其優先級是中斷發生的時間，也就是說，先發生的中斷將優先得到處理。圖 對中斷等待隊列的操作中斷等待隊列某些將會引起中斷的操作系統定期發生的中斷時鐘前進判斷有無中斷發生圖 對中斷等待隊列的操作中斷等待隊列某些將會引起中斷的操作系統定期發生的中斷時鐘前進判斷有無中斷發生當時鐘前進或者系統處于Idle狀態時，Nachos會判斷中斷等待隊列中是否有要發生的中斷，如果有中斷需要發生，則將該中斷從中斷等待隊列中刪除，調用相應的中斷處理程序進行處理。圖是中斷等待隊列的操作示意圖。中斷處理程序是在某種特定的中斷發生時被調用，中斷處理程序的作用包括可以在現有的模擬硬件的基礎上建立更高層次的抽象。比如現有的模擬網絡是有丟失幀的不安全網絡，在中斷處理程序中可以加入請求重發機制來實現一個安全網絡。PendingInterrupt類XE"Interrupt類"classPendingInterrupt{public:PendingInterrupt(VoidFunctionPtrfunc,intparam,inttime,IntTypekind);VoidFunctionPtrhandler; 時鐘中斷模塊分析（文件）該模塊的作用是模擬時鐘中斷。Nachos虛擬機可以如同實際的硬件一樣，每隔一定的時間會發生一次時鐘中斷。這是一個可選項，目前Nachos還沒有充分發揮時鐘中斷的作用，只有在Nachos指定線程隨機切換時，（Nachos-rs參數，見線程管理XE"線程管理"部分Nachos主控模塊分析）啟動時鐘中斷，在每次的時鐘中斷處理的最后，加入了線程的切換。實際上，時鐘中斷在線程管理中的作用遠不止這些，時鐘中斷還可以用作：線程管理XE"線程管理"中的時間片輪轉法的時鐘控制，（詳見線程管理系統中的實現實例中，對線程調度的改進部分）不一定每次時鐘中斷都會引起線程的切換，而是由該線程是否的時間片是否已經用完來決定。分時系統線程優先級的計算（詳見線程管理XE"線程管理"系統中的實現實例中，對線程調度的改進部分）線程進入睡眠狀態時的時間計算可以通過時鐘中斷機制來實現sleep系統調用，在時鐘中斷處理程序中，每隔一定的時間對定時睡眠線程的時間進行一次評估，判斷是否需要喚醒它們。Nachos利用其模擬的中斷機制來模擬時鐘中斷。時鐘中斷間隔由TimerTicks宏決定（100倍Tick的時間）。在系統模擬時有一個缺陷，如果系統就緒進程不止一個的話，每次時鐘中斷都一定會發生進程的切換（見中TimerInterruptHandler函數）。所以運行Nachos時，如果以同樣的方式提交進程，系統的結果將是一樣的。這不符合操作系統的運行不確定性的特性。所以在模擬時鐘中斷的時候，加入了一個隨機因子，如果該因子設置的話，時鐘中斷發生的時機將在一定范圍內是隨機的。這樣有些用戶程序XE"用戶程序"在同步方面的錯誤就比較容易發現。但是這樣的時鐘中斷和真正操作系統中的時鐘中斷將有不同的含義。不能象真正的操作系統那樣通過時鐘中斷來計算時間等等。是否需要隨機時鐘中斷可以通過設置選項(-rs)來實現。Timer類XE"Timer類"定義和實現如下所示：classTimer{public:Timer(VoidFunctionPtrtimerHandler,intcallArg,booldoRandom); 終端設備模塊分析（文件）該模塊的作用是模擬實現終端的輸入和輸出。包括兩個部分，即鍵盤的輸入和顯示輸出。終端輸入輸出的模擬是異步的，也就是說當發出終端的輸入輸出請求后系統即返回，需要等待中斷發生后才是真正完成了整個過程。Console類XE"Console類"定義和實現如下所示：classConsole{public:Console(char*readFile,char*writeFile,VoidFunctionPtrreadAvail,VoidFunctionPtrwriteDone,intcallArg); .系統通過定期的讀終端中斷來判斷終端是否有內容供讀取，如果有則讀出；如果沒有，下一次讀終端中斷繼續判斷。讀出的內容將一直保留到GetChar將其讀走。對寫終端來說：PutChar->WriteDone->PutChar->WriteDone->...系統發出一個寫終端命令PutChar，模擬系統將直接向終端輸出文件寫入要寫的內容，但是對Nachos來說，整個寫的過程并沒有結束，只有當寫終端中斷來到后整個寫過程才算結束。5.磁盤設備模塊分析（文件）磁盤設備模擬了一個物理磁盤。Nachos用宿主機中的一個文件來模擬一個單面物理磁盤，該磁盤由道組成，每個道由扇區組成，而每個扇區的大小是固定的。和實際的物理磁盤一樣，Nachos以扇區為物理讀取/寫入的最小單位，每個扇區有唯一的扇區地址，具體的計算方法是： track*SectorsPerTrack+offset該物理磁盤是一個異步的物理磁盤，同終端設備和網絡設備一樣，當系統發出讀磁盤的請求，立即返回，只有具體的磁盤終端到來的時候，整個過程才算結束。Disk類XE"Disk類"的定義和實現如下所示：classDisk{public:Disk(char*name,VoidFunctionPtrcallWhenDone,intcallArg); Nachos運行情況統計（文件）在本章的最后部分，我們要說明的是對Nachos運行情況進行統計的類Statistics。這并不屬于機器模擬的一部分，但是為了幫助讀者了解自己設計的操作系統的各種運行情況。Statistics類中包含的各種統計項是非常有價值的。Statistics類的定義和實現如下：classStatistics{public:inttotalTicks; 進程概念進程是操作系統中最基本也是最重要的概念之一，它表示程序在給定數據集上的一次執行活動。通常情況下，一個計算機系統（無論是單機還是多機系統）同時存在的進程數大于計算機系統所有的CPU數。（由于Nachos模擬的是單機系統，所以以下都以單機系統為例）但是每個CPU在一個瞬時只能運行一個進程。所以CPU會在多個進程之間切換。在任一時刻，系統中有若干進程處在起點和終點之間，這些進程被認為是在運行著，這就是我們所說的并發處理。系統運行過程中，通常有多個進程同時存在，它們各自執行的指令序列，對系統資源和服務的需求以及狀態的變化往往互不相同、千變萬化而難以預測。同時還可能接收到需要立即處理的中斷信號。而中斷信號發生的時間以及頻繁程度與系統中許多經常變換著的不確定因素有關。所以每個進程在一種不可預測的次序中交替前進。操作系統內部動作的不可預測、不可重復就是操作系統的不確定性。2.進程的狀態及狀態變化進程是程序的一次執行活動，它是一種動態的概念，而這種動態在宏觀上表現為狀態的變化。進程在運行中，有三種基本狀態：運行態：進程分配到處理機運行。就緒態：進程已經可以在處理機上運行，只是暫時沒有分配到處理機。阻塞態：進程因等待某一個事件發生而暫時不能調度上處理機運行。一個系統中的進程在一定條件下可以在這三種狀態之間轉換。一般有四種類型的轉換。如圖所示：運行態->就緒態進程占用CPU運行了一段時間，但是沒有運行結束。為使各就緒進程能比較平衡地共享CPU，此時調度程序需要將其它就緒進程調度上處理機運行，于是原來占據處理機的進程成為就緒態，等待下一次被調度上處理機運行。就緒態->運行態進程處于就緒態，調度程序總是有機會將其調度上處理機，于是該進程從就緒態轉為運行態，并從上一次運行的中斷點繼續運行。運行態->阻塞態進程運行過程中可能因等待某種事件發生而暫時停止，比如等待一次鍵盤事件或者磁盤輸入輸出。進程進入阻塞態時，調度程序會調度一個就緒態進程上處理機運行。阻塞態->就緒態當進程進入阻塞態之前等待發生的事件業已發生，則該進程從阻塞態轉為就緒態，于是它可以再被調度上處理機繼續運行。除了個別進程外，一般進程都需要經歷這三種狀態，并在這三種狀態中反復變換直至運行終止。圖 進程的狀態轉換等待的事件發生就緒態運行態阻塞態被迫放棄處理機等待某事件發生處理機調度運行圖 進程的狀態轉換等待的事件發生就緒態運行態阻塞態被迫放棄處理機等待某事件發生處理機調度運行3.進程調度進程調度程序的優劣取決于其調度算法，在不同應用的操作系統中，調度算法的重點各不相同，這里給出一般進程調度的原則：調度程序必須公平，確保每個進程都有機會使用系統的資源，不會出現由于一直分配不到資源而出現進程“餓死”的現象。充分利用系統的各項資源，尤其是CPU資源。不會出現有進程處于就緒態，而CPU處于空閑狀態的現象。一定的系統吞吐率，在單位時間內執行完成的進程數越大越好。合理的系統響應時間。對于有交互功能的進程，用戶的等待時間要短。能夠反映用戶的不同類型以及他們對有關作業運行優先程度的要求。合理的系統開銷。進程調度分為非搶占式調度和搶占式調度。非搶占式調度就是進程在運行過程中不會切換到其它進程運行，除非其主動放棄處理機或者運行結束。由于進程的運行有不可預見性，有可能一個進程會占用處理機達幾個小時，甚至一個編寫錯誤的進程會一直占用處理機不放。為了確保沒有一個進程單獨運行的時間太長，幾乎所有的計算機系統都內置了時鐘，周期性地進行時鐘中斷，在每一次時鐘中斷時，由進程調度程序負責判斷是否有就緒進程比正在運行的進程更加適合占用CPU。如果有這類進程則進行進程調度，這樣的調度稱為搶占式調度。通用操作系統一般采用搶占式調度，這樣才能體現以上所說的進程調度原則。進程調度的算法一般有以下幾種：循環輪轉調度在循環輪轉調度中，每個進程都被安排了一個運行時間段限制，叫做時間片。如果一個進程在其時間片結束時仍沒有運行結束，CPU便被搶占并被調度執行其它進程。如果進程在其時間片結束之前已經阻塞或完成，則操作系統當即切換CPU到其它進程運行。輪轉調度比較簡單，在系統中只需要維護一個就緒進程的列表。如圖所示：在圖(a)中，當前運行的進程是B進程，當B進程運行的時間片用完，調度程序將緊接的F進程調度上處理機，成為當前運行進程，而B進程被調度到就緒進程表的最后。圖 進程循環輪轉調度(b)(a)FDGAFDGABB圖 進程循環輪轉調度(b)(a)FDGAFDGABB循環輪轉調度中的一個重要問題是時間片的長短。由于進程切換需要一定的系統開銷，包括保護和恢復現場等，將時間片設置過短會導致引起過多的進程切換而降低處理機效率；但是如果時間片設置過長，將引起用戶響應時間比較長。在不同要求的操作系統中實現的時間片長短是不一樣的。某些系統還實現了多時間片調度，以滿足不同的需要優先權調度優先權調度法按照進程執行任務的輕重緩急，給每個進程一個調度優先權。系統在切換時，在所有就緒進程中選擇優先權最高的進程調度上處理機運行。優先權調度法分成靜態優先權調度法和動態優先權調度法。靜態優先權調度法如果在創建進程時就確定了進程的優先權，而且在進程的運行過程中除設置外不會經常改變，那么這樣的調度方法稱為靜態優先權調度法。靜態優先權的確定方法有如下幾種：按進程的類型確定：一般系統進程的優先權高于用戶進程；進程在核心態下運行時的優先權高于在用戶態下運行的優先權；前臺進程的優先權高于后臺進程；實時性要求高的進程的優先權高于實時性要求低的進程的優先權。按進程提交的時間次序確定：一般先提交的進程優先權較高。按作業要求的資源類型和數量確定：一般要求資源較少的進程有較高的優先權，這樣有助于提高系統的吞吐量。動態優先權調度法進程優先權在進程創建后如果不是固定的，而是根據系統中的運行狀態不斷變化的。這樣的優先調度稱為動態優先權調度。一般動態優先權調度算法的優先權計算的原則是：連續占用處理機時間長的進程，優先權相應降低。在進程切換調度時這種進程被調度上處理機的機會較少。在較長時間未使用處理機或者雖然頻繁使用處理機，但每次使用時間很短的進程，進程優先權較高。在進程切換調度時，這種進程被調度占用處理機的機會增加。動態優先權的系統開銷比較大，系統開銷一方面取決于動態優先數計算的復雜程度，另一方面也與計算的頻繁度有關。在計算優先權時機的選擇上，一般至少在一定的時間間隔重新計算當前運行進程的優先權以及一些有可能調度上處理機的進程的優先權，而不是將系統中所有的進程之優先權都重新計算。4.進程之間的同步和互斥同一個計算機系統中的進程不是完全孤立的，它們之間存在著相互依賴，相互制約的關系。某些進程相互協作，共同完成某種任務；同時，它們又互相競爭使用系統的有限資源。進程的這些關系意味著進程之間需要相互通訊，這表現為同步和互斥兩個方面。兩個進程之間的同步是指一個進程達到某一運行點后，除非另一進程完成了某些操作，否則就不得不停下來等待這些操作的完成。系統中存在有這樣的資源，它一次只能分配給一個進程使用。這樣的資源稱為臨界資源。當一個進程使用該資源時，其它進程必須等待該進程釋放它之后，才會獲得該資源的占有權。進程之間的這種關系叫做互斥。進程之間可以共享某些數據，對這些共享數據的操作往往也必須是互斥的。與互斥有關的程序段稱為臨界區，針對同一臨界資源進行操作的程序段稱為同類臨界區。鎖機制、信號量以及條件變量是實現同類臨界區同步和互斥的三種常用方法。5.進程的實施進程由四個部分組成：程序（正文段）、數據（數據段）、進程的運行棧（棧段）以及進程控制塊（PCB）。正文段描述了進程所要完成的功能，一般不能修改，所以正文段可以被多個進程共享，又稱共享正文段；數據段中是要完成功能所需要的數據，而且這部分數據需要使用不隨進程運行而變化的存儲控件，一般而言，數據段不能被共享；棧段是進程運行的附加空間，記錄了該進程運行的一部分狀態，不能被共享；進程控制塊包含了進程的描述信息和控制信息，是進程動態特性的集中反映。在一個最簡單的操作系統中，進程控制塊至少要保存以下信息：正文段、數據段以及棧段的位置進程的狀態進程的運行現場：在一個多進程的系統中，一個準備就緒狀態的被選擇切換上處理機運行時，應該從它上次運行的暫停點開始。這樣才能保證進程運行的正確性。為此在進程控制塊中設置運行現場部分，它保存進程上次退出處理機時的各硬件寄存器（一般包括程序計數器、程序狀態字以及各種通用寄存器中）的值。對于一個復雜的系統，進程控制塊中還需要保存其它一些信息，包括進程運行的各項統計數據等。6.進程的創建很多操作系統的進程結構如同樹狀。以UNIX為例，每個進程都可以創建若干子進程。整個操作系統中的進程樹型結構理論上可以不斷延伸。一個進程創建了子進程，它被稱為該子進程的父親。父親創建子進程的基本任務是為新進程構造一個可以運行的環境，包括正文段、數據段和運行的初始棧，以及子進程的進程控制結構，并且保證能夠使子進程作為一個可被獨立調度的進程。UNIX創建子進程的基本方式是：除了與進程狀態、標識以及與時間有關的少數控制項外，子進程復制或共享父進程的圖象。子進程復制了父進程的進程圖象后，就和父進程一樣有了自己的正文段（雖然是與父進程共享）、數據段、一個獨立的PC指針以及自己獨立的運行棧，可以獨立運行。我們將進程所運行的空間稱為地址空間，進程PC指針和運行棧看作一個線索，那么子進程和父進程一樣擁有各自的地址空間和而且各有一個運行線索。二、線程1.線程概念我們經常通過生成子進程的方式去完成相關而又獨立的任務。比如一個文件服務器，它接收讀寫文件的請求并將所需數據傳入或傳出，為了提高性能，服務器將最近傳送的數據放入緩存，以便在需要時重復使用。當有請求到達時，為了處理的獨立性，該進程就要生成一個子進程去完成這一請求。當多個請求到達時，就需要生成多個子進程。這種處理方法比較簡單明了，但是也有不少問題：創建子進程以及在進程之間切換的開銷比較大。進程之間共享緩存和進程和進行通信雖然可以使用操作系統提供的很多進程通信機制，包括共享內存段等。但是也有系統開銷大，效率偏低的問題。為了解決這些問題，提出了線程的概念。見圖；(b)(a)圖 進程和線程PC指針線程進程計算機系統計算機系統(b)(a)圖 進程和線程PC指針線程進程計算機系統計算機系統圖(a)計算機系統中共運行了三個進程，各自有自己的地址空間和運行線索。如果這三個進程的地址空間是完全可以共享的，所不同的只是運行的線索（例如在文件服務器中），那是否可以將三個進程的地址空間完全合一呢？這就是圖(b)所描繪的線程。圖(b)中只有一個進程，但該進程中包含有三個運行線索。每個運行線索各有自己的PC指針和運行棧空間，嚴格按照自己的順序進行。同進程調度一樣，在某個時刻單機系統中只能有一個線程在運行。引入線程之后，線程即成為調度程序可以調度的最小單位，但是如果在同一進程中的不同線程之間進行調度切換，那么系統開銷將顯著降低。對線程的調度算法隨操作系統的不同而異。線程的引入還為同族線程的數據共享提供了便利。只要系統提供基本的同步互斥操作，例如鎖和信號量，同族線程就可以方便地對數據區實施共享，相對于同族進程必須通過操作系統核心共享數據操作就簡單得多了。同族線程間對共享數據的管理任務從系統內核移到了用戶程序XE"用戶程序"上，既減輕了核心的負擔，又給程序員編寫一些共享程序提供了方便。現代操作系統使用線程并不僅僅針對用戶程序XE"用戶程序"，線程思想還可滲入到核心的各個部分。系統內核把每一個系統調用看作來自用戶端的服務請求，經過一些必要的處理后，就產生一個新線程去執行具體的操作。這些線程共享了核心的地址空間，可以直接訪問核心的公用數據。這樣做有兩個明顯的好處：⑴簡化了系統內核，加快了內核對系統調用的響應速度；⑵簡化了核心態下的狀態保存。這些思想是一些微內核操作系統的主體思想。2.進程和線程的關系在引入線程機制后，進程不再是單一的動態實體，而是由兩部分組成：各線程活動的環境，包括：統一的地址控件、全局變量、打開文件和計時器等。若干個線程，它們是進程中的活動部分，也是處理機的調度單位，而進程不再是處理機的最小調度單位。一個進程中的所有線程在同一地址空間中活動，共享該地址空間中的全局變量，共享打開文件和計時器等。它們總是相互協作，各自承擔一個作業中的某個部分。與傳統的進程相似，線程具有狀態的變化。通常，這些狀態是：運行、阻塞、就緒或終止。表 與進程和線程有關的主要信息表線程控制信息進程控制信息程序計數器運行棧寄存器集子線程運行狀態地址空間全局變量打開文件子進程計時器線程第二節 Nachos的線程管理XE"線程管理"一、Nachos的線程管理XE"線程管理"Nachos的第一個需要擴充的部分是線程管理XE"線程管理"。Nachos提供了一個基本的線程管理系統和一個同步互斥機制信號量的實現。讀者在此基礎上完成鎖和條件變量等另兩種同步互斥機制并對現有的線程機制進行一些加強。然后利用這些同步原語解決一些并發性問題。例