(精選word)nachos中文教程

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

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

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