操作系統(tǒng)課件

第一章概論§1電腦系統(tǒng)的層次結(jié)構(gòu)§2操作系統(tǒng)的資源管理觀點§3操作系統(tǒng)的服務(wù)觀點§4操作系統(tǒng)的特性§5操作系統(tǒng)的硬體基礎(chǔ)§6操作系統(tǒng)的裝入與初啟§1電腦系統(tǒng)的層次結(jié)構(gòu)

一個完整的電腦系統(tǒng)是由硬體和軟體兩大部分組成的。硬體(即物理電腦)是系統(tǒng)的基本資源，其主要部件包括：中央處理機(CPU)、主存貯器(簡稱主存或記憶體)、外部存貯器(簡稱外存或輔存，包括磁片和磁帶)、終端(通常由鍵盤*和顯示器組成)、控制臺以及字元印表機等。CPU和記憶體構(gòu)成系統(tǒng)的主機，其他部件統(tǒng)稱為外部設(shè)備(簡稱外設(shè)），或稱為輸入輸出(I／O)設(shè)備。圖１-１電腦系統(tǒng)的抽象層次結(jié)構(gòu)§２操作系統(tǒng)的資源管理觀點２.１支持資源共用的多道程序系統(tǒng)

按照程式在系統(tǒng)中的運行方式，電腦系統(tǒng)分為單道程式系統(tǒng)和多道程序系統(tǒng)*。所謂單道程式系統(tǒng)是指系統(tǒng)只能順序地執(zhí)行用戶程式，即僅當一個用戶程式執(zhí)*行完後，才啟動另一個用戶程式工作，在一個用戶程式運行期間，它獨佔全機崐資源。這樣的系統(tǒng)經(jīng)常出現(xiàn)資源使用不充分和不均衡的現(xiàn)象，當ＣＰＵ工作時*，外設(shè)往往處於閒置狀態(tài)；同樣，當外設(shè)工作時，ＣＰＵ也往往空閒著；外設(shè)*之間亦同樣如此。由於ＣＰＵ的速度遠遠高於外設(shè)，ＣＰＵ的浪費就顯得尤為*嚴重。

多道程序系統(tǒng)的實現(xiàn)需要硬體和軟體的共同支持。在硬體技術(shù)中主要引入了中*斷和通道。所謂中斷，從概念上說是指意外事件或非同步事件對ＣＰＵ的打斷。意*外事件如電源掉電或硬體故障，非同步事件則是無一定時序關(guān)係的隨機事件，例*如外部設(shè)備完成Ｉ／Ｏ傳輸，用戶通過終端發(fā)出命令請求等。一旦意外事件或*非同步事件發(fā)生，中斷部件便向ＣＰＵ發(fā)出中斷請求，暫停ＣＰＵ的當前工作。*通道則是一種專門用於控制外部設(shè)備的簡單處理機，亦稱Ｉ／Ｏ處理機，它聯(lián)*接著主機和外設(shè)，具有向記憶體直接存取數(shù)據(jù)的能力。作為處理機，它執(zhí)行專門*的通道指令，並可獨立於ＣＰＵ，與ＣＰＵ同時工作。當現(xiàn)行程式需要Ｉ／Ｏ*傳輸時，ＣＰＵ只要命令通道去完成就行了，同時ＣＰＵ可以繼續(xù)執(zhí)行現(xiàn)行程*序的後續(xù)工作或執(zhí)行其他程式。

只有當通道控制相應(yīng)的外部設(shè)備完成了指定的*數(shù)據(jù)傳輸任務(wù)後，才通過中斷部件向ＣＰＵ發(fā)出中斷請求，ＣＰＵ立即暫?，F(xiàn)*行程序的執(zhí)行，轉(zhuǎn)去執(zhí)行中斷處理程式?？梢?，中斷和通道技術(shù)的引入，實現(xiàn)*了多部件並行工作，即ＣＰＵ與外設(shè)以及外設(shè)與外設(shè)之間同時工作。利用多部*件並行工作的特性，就可使多道程序同時運行，實現(xiàn)系統(tǒng)資源的共用。支持多*道程式系統(tǒng)的軟體系統(tǒng)需要在多道程序之間合理地分配和回收系統(tǒng)資源,使資源*得到合理有效的利用，使得各個程式能夠有條不紊地運行，這個軟體就是操作系統(tǒng)。２.２操作系統(tǒng)的管理功能１.ＣＰＵ管理２.存貯器管理３.設(shè)備管理４.檔管理５.進程及作業(yè)管理§３操作系統(tǒng)的服務(wù)觀點３.１公共服務(wù)功能（1）程式裝入與執(zhí)行（2）Ｉ／Ｏ操作（３）檔使用（４）作業(yè)運行控制（５）錯誤檢測與處理３.２操作系統(tǒng)的分類

１.批處理系統(tǒng)（ＢａｔｃｈＰｒｏｃｅｓｓｉｎｇＳｙｓ*ｔｅｍ）批處理系統(tǒng)也稱批量系統(tǒng)或作業(yè)流處理系統(tǒng)。所謂批處理意指用戶作業(yè)的成批輸入並處理，即系統(tǒng)將作業(yè)一批一批地輸入系統(tǒng)並暫存在外存中，組成一個後備作業(yè)列隊，每次按一定的調(diào)度原則從後備作業(yè)中挑選一個或多個裝入主機處理，作業(yè)完成後退出主機和後備作業(yè)裝入主機運行均由系統(tǒng)自動實現(xiàn)，從而大大壓縮了兩個作業(yè)之間的轉(zhuǎn)接時間，在系統(tǒng)中形成了一個自動轉(zhuǎn)接的連續(xù)作業(yè)流，當一批作業(yè)運行完後，輸出它們的運行結(jié)果，再接受下一批作業(yè)進入系統(tǒng)處理。然而，在現(xiàn)代批處理系統(tǒng)中，上述“批”的概念已不十分明顯，用戶作業(yè)可被隨時接受進入系統(tǒng)處理，運行結(jié)果也可以隨機輸出，而不必集中成批輸入和輸出，所以批處理的真實含義是指系統(tǒng)對源源不斷的作業(yè)流的連續(xù)處理。

批處理系統(tǒng)的特點是它採用的是脫機服務(wù)方式，即用戶在其作業(yè)運行期間不能在控制臺或終端上請求系統(tǒng)的服務(wù)以直接干預其作業(yè)的運行過程，而必須將其對作業(yè)的控制意圖事先用作業(yè)控制語言編制成作業(yè)說明書或作業(yè)控制卡，這些控制意圖可以是作業(yè)運行時的資源要求、作業(yè)步的執(zhí)行次序、對可能的運行錯誤的處理措施等等。作業(yè)控制卡或作業(yè)說明書連同程式和數(shù)據(jù)一起提交給系統(tǒng)，由系統(tǒng)的作業(yè)控制程式或命令解釋程式解釋執(zhí)行，提供相應(yīng)的各種服務(wù)。批處理系統(tǒng)主要配置在較大的電腦系統(tǒng)上，由於這樣的機器的硬體設(shè)備配置較全，價格較貴，故現(xiàn)代批處理系統(tǒng)多建立在多道程序設(shè)計基礎(chǔ)上，追求的是作業(yè)的大吞吐量和系統(tǒng)資源的充分利用。

２.分時系統(tǒng)（Ｔｉｍｅ-ｓｈａｒｉｎｇＳｙｓｔｅｍ）

所謂“分時”，就是多個用戶對系統(tǒng)資源進行時間上的分享。在分時環(huán)境下，一個電腦系統(tǒng)聯(lián)有若干臺本地或遠程終端，每個用戶可以在所佔用的終端上以人-機會話的交互方式使用電腦。故分時系統(tǒng)又稱為多用戶互動式共用系統(tǒng)。分時系統(tǒng)具有以下三個特點：（１）多路性（２）交互性（３）獨佔性

３即時系統(tǒng)（Ｒｅａｌ-ｔｉｍｅＳｙｓｔｅｍ）

所謂“即時”就是“立即”或“及時”，具體含義是指系統(tǒng)能夠及時回應(yīng)隨機發(fā)生的外部事件，並以足夠快的速度完成對事件的處理。外部事件是指感測器或其他信號測量裝置所採集的現(xiàn)場數(shù)據(jù)或終端用戶提出的服務(wù)請求。即時系統(tǒng)具有如下三個特點：（１）簡單的交互能力（２）及時回應(yīng)（３）高可靠性

４.單用戶互動式系統(tǒng)（ＳｉｎｇｌｅＵｓｅｒＩｎｔｅｒａcｔｉvｅＳｙｓｔｅｍ）

微型電腦的規(guī)模小，價格便宜，對工作環(huán)境要求不高，適宜於個人使用，故也稱為個人電腦（ＰｅｒｓｏｎａｌＣｏｍｐｕｔｅｒ）。為這類電腦設(shè)計的操作系統(tǒng)多為單用戶系統(tǒng)，它不追求系統(tǒng)資源的充分利用，也不講究共用資源，而是強調(diào)個人的特點，注重使用方便。因此，這類操作系統(tǒng)的功能比較簡單，管理功能主要是磁片檔管理和設(shè)備驅(qū)動，服務(wù)方式採用聯(lián)機交互方式，除了提供鍵盤命令服務(wù)外，一些優(yōu)良的系統(tǒng)還提供更為方便靈活的交互手段，例如“菜單”命令、“窗口”顯示，“滑鼠”驅(qū)動。５.網(wǎng)路操作系統(tǒng)（ＮｅｔｗｏｒｋＯＳ）

網(wǎng)路操作系統(tǒng)除了具有基本類型操作系統(tǒng)中所應(yīng)具備的管理功能和服務(wù)功能外，還具有網(wǎng)路管理和服務(wù)功能，這主要包括：①網(wǎng)路資源共用，系統(tǒng)提供資源共用操作供節(jié)點電腦用戶或作業(yè)方便地使用本地的或遠地的其他節(jié)點電腦上的可共用資源。②網(wǎng)路通信，不同節(jié)點電腦的用戶或作業(yè)可以相互交換資訊，系統(tǒng)提供檔傳輸和電子郵件服務(wù)，一個檔可以被傳輸?shù)狡渌?jié)點電腦上，以方便檔共用，用戶也可以發(fā)送一份電子郵件給其他節(jié)點電腦用戶或接受其他節(jié)點電腦用戶發(fā)來的電子郵件，就像打電話一樣方便。③作業(yè)遷移，一個作業(yè)可以從一個節(jié)點電腦上遷移到其他工作負荷較輕或適宜於處理該作業(yè)的節(jié)點電腦上運行。３.３操作系統(tǒng)的服務(wù)介面１.程式級介面

所謂操作系統(tǒng)的程式級介面，就是操作系統(tǒng)與目態(tài)程式之間的介面。當執(zhí)行中的目態(tài)程式請求操作系統(tǒng)服務(wù)，轉(zhuǎn)而執(zhí)行操作系統(tǒng)程式時，將引起ＣＰＵ執(zhí)行狀態(tài)從目態(tài)變?yōu)楣軕B(tài)，因此，也稱這類介面為狀態(tài)介面。程式級介面由一組系統(tǒng)調(diào)用命令所組成，系統(tǒng)調(diào)用命令就是具有系統(tǒng)調(diào)用編號和其他有關(guān)參數(shù)的“訪管”指令（ＳＶＣ）或“陷入”指令（ｔｒａｐ）。當機器執(zhí)行ＳＶＣ或ｔｒａｐ指令時將引起訪管中斷，ＣＰＵ狀態(tài)變?yōu)楣軕B(tài)，保留調(diào)用現(xiàn)場，然後去崐執(zhí)行相應(yīng)的某個操作系統(tǒng)程式，當該操作系統(tǒng)程式執(zhí)行完畢，經(jīng)中斷機構(gòu)返回，ＣＰＵ由管態(tài)又複變?yōu)槟繎B(tài)。目態(tài)程式請求操作系統(tǒng)服務(wù)的唯一途徑就是使用系統(tǒng)調(diào)用命令。操作系統(tǒng)在程式級提供以下幾類功能服務(wù)：（１）進程控制（２）檔操作（３）設(shè)備管理（４）資訊維護（５）通信２.作業(yè)控制級介面

作業(yè)控制級介面提供的是一組控制和服務(wù)命令，它通常包括以下幾類：系統(tǒng)訪問，資源分配、程式執(zhí)行、檔操作、資訊維護、控制流、操作員專用以及服務(wù)方式轉(zhuǎn)換。這些命令由系統(tǒng)命令處理程式（ＵＮＩＸ中稱Ｓｈｅｌｌ）解釋執(zhí)行。根據(jù)系統(tǒng)的服務(wù)方式，這類介面又可進一步分為脫機級介面和聯(lián)機級（互動式）介面。

（１）脫機級介面即作業(yè)控制語言ＪＣＬ（ＪｏｂＣｏｎｔｒｏｌＬａｎｇｕａｇｅ），由批處理系統(tǒng)提供。ＪＣＬ有兩種形式：一種相當於組合語言，如ＩＢＭ３７０的ＪＣＬ；另一種類似於高級語言，如１９００系列的Ｇｅｏｒｇｅ語言。ＪＣＬ的語句就是控制和服務(wù)命令。在批處理系統(tǒng)的脫機服務(wù)方式下，用戶把他對系統(tǒng)的服務(wù)請求和對其作業(yè)運行的控制意圖事先用ＪＣＬ編寫一份“上機說明書”並製成作業(yè)控制卡或作業(yè)說明書，隨同程式和數(shù)據(jù)一起提交給電腦系統(tǒng)。在系統(tǒng)處理作業(yè)時，逐條解釋執(zhí)行ＪＣＬ語句，實現(xiàn)對作業(yè)運行的自動控制。在作業(yè)運行時，用戶不得再干預。①作業(yè)標識語句ＪＯＢ。ＪＯＢ標識一個作業(yè)的開始，它作為作業(yè)卡片迭的第一張。一般格式是：

∥ＪＯＢｊｏｂｎａｍｅ［ｐａｒａｍｅｔｅｒｓ］其中：∥表示這是控制卡；ｊｏｂｎａｍｅ為作業(yè)名，由字母打頭的１～８個字元；

parameters是可選參數(shù)，它可以是帳號、用戶名、作業(yè)優(yōu)先數(shù)、作業(yè)運行的估計時間等。②執(zhí)行語句ＥＸＥＣ。標誌一個作業(yè)步開始，裝入並啟動可執(zhí)行程式。一般格式是：

∥ＥＸＥＣ［［ＰＧＭ＝］ｐｒｏｇｎａｍｅ］［，ｇｏ］或∥ＥＸＥＣＰＲＯＣ＝ｐｒｏｃｎａｍｅ其中：ｐｒｏｇｎａｍｅ是要裝入執(zhí)行的程式名，若缺省，則把最近連接產(chǎn)生的可執(zhí)行程式裝入執(zhí)行；ｐｒｏｃｎａｍｅ是從過程庫中取出執(zhí)行的程式名；ｇｏ表示調(diào)用連接裝配程式，對編譯產(chǎn)生的目標模組進行連接並裝入運行。③選擇語句ＯＰＴＩＯＮ。描述作業(yè)要求的某些服務(wù)請求。例如，列印程式清單ＬＩＳＴ，列印錯誤表ＥＲＲＳ，連接目標模組ＬＩＮＫ等。一般格式是：

∥ＯＰＴＩＯＮｏｐｔｉｏｎ［,ｏｐｔｉｏｎ…］其中，OPTION,option[,option…]④程式或數(shù)據(jù)定界語句／。用以標誌程式或數(shù)據(jù)的結(jié)束。⑤作業(yè)定界語句／&。用以標識作業(yè)的結(jié)束。此外，還有請求外設(shè)分配，指定磁片，帶標號等語句。下麵是一個簡單的例子：∥ＪＯＢＤＡＶＩＳ∥ＯＰＴＩＯＮＬＩＮＫ∥ＥＸＥＣＰＡＳＣＡＬ；執(zhí)行ｐａｓｃａｌ編譯程序(ｐａｓｃａｌ根源程式）／*

∥ＥＸＥＣＬＩＮＫＥＤＴ；執(zhí)行連接程式∥ＥＸＥＣ；執(zhí)行剛產(chǎn)生的可執(zhí)行程式（數(shù)據(jù)）／*

／&；作業(yè)結(jié)束

（２）聯(lián)機級介面這由一組終端命令(可以是鍵盤命令行、菜單選擇命令、滑鼠驅(qū)動命令）所組成，由分時系統(tǒng)和單用戶互動式系統(tǒng)提供，它向聯(lián)機終端用戶提供了以人-機會話方式請求系統(tǒng)服務(wù)的手段。用戶在終端上每輸入一條命令，系統(tǒng)就隨即解釋執(zhí)行。並把命令的執(zhí)行結(jié)果通過終端及時回饋給用戶，用戶可根據(jù)系統(tǒng)的回饋資訊決定下一步的操作，繼之輸入下一條命令……，如此不斷交互會話，直至作業(yè)完成?？梢姡?lián)機級介面為用戶使用電腦提供了很大的方便，通過交互會話，人和電腦組成了一個閉合系統(tǒng)，可以充分發(fā)揮用戶的主觀能動性，用戶可以對其作業(yè)的運用進行隨機干預，方便靈活地請求系統(tǒng)的各種服務(wù)，從而大大提高了調(diào)試和開發(fā)程式的效率。ｌｏｇｉｎ：ｆｅｎ鍵入用戶名ｐａｓｓｗｏｒｄ：鍵入口令，口令不顯示Ｌａｓｔｌｏｇｉｎ：ＳｔａＦeｂ１７９∶２０∶１１ｏｎｔｔｙｄｌ顯示系統(tǒng)日期資訊（略）％ｐｗｄ詢問當前目錄／ｕｓｒ／ｆｅｎ％ｌｓ－１以長格式列出當前目錄下的所有檔－ｒｗｘｒ－ｘｒ１ｆｅｎ34516Jan239∶10pro1－ｒｗｘｒ－ｘｒ－ｘ１ｆｅｎ1798Fed713∶49

pro２ｄｒｗｘｒ－ｒ－２ｆｅｎ264Ｆｅｄ158∶30fd％ｃｈｍｏｄ７４４ｐｒｏl修改檔的保護方式，不允許同組用戶執(zhí)行

脫機級介面與聯(lián)機級介面，二者並不是截然分開的，一些既支持批處理又支持分時處理的電腦系統(tǒng)同時提供這兩類服務(wù)介面，用戶可以使用ＪＣＬ將其作業(yè)交由系統(tǒng)批處理，也可以使用終端命令直接控制其作業(yè)的運行，而且在作業(yè)的一次運行中可轉(zhuǎn)換使用終端命令和ＪＣＬ,即可將交互作業(yè)（也稱前臺作業(yè)）轉(zhuǎn)為批處理作業(yè)（也稱後臺作業(yè)），反之亦然?！欤床僮飨到y(tǒng)的特性

現(xiàn)代電腦系統(tǒng)多為多道程序系統(tǒng)，這給操作系統(tǒng)的設(shè)計和運行帶來了許多複崐雜問題。它們集中體現(xiàn)在：１併發(fā)性（ｃｏｎｃｕｒｒｅｎｃｙ）２共用性（ｓｈａｒｉｎｇ）３不確定性（ｎｏｎｄｅｔｅｒｍｉｎａｃｙ）§５操作系統(tǒng)的硬體基礎(chǔ)５.１多ＣＰＵ狀態(tài)

ＰＳＷ是ＣＰＵ中的一些特殊寄存器的有序集合，它描述了ＣＰＵ的現(xiàn)行狀態(tài)。所謂ＣＰＵ狀態(tài)通常包括：執(zhí)行狀態(tài)——管態(tài)和目態(tài)；條件碼——反映指令執(zhí)行後的結(jié)果特徵；中斷字——指出發(fā)生了某種中斷；中斷遮罩碼——指出是否允許中斷，有些機器（如ＰＤＰ-１１）使用中斷優(yōu)先順序。有些機器的ＰＳＷ還包括了用來指示下一條要執(zhí)行的指令的程式計數(shù)器（ＰＣ）。５.２中斷機構(gòu)１.中斷概念

所謂中斷，是指當ＣＰＵ正在執(zhí)行某程式時，發(fā)生了某個非同步事件，此時ＣＰＵ可以打斷正在執(zhí)行的程式，轉(zhuǎn)去處理該事件，即執(zhí)行一段處理該事件的有關(guān)程式。被打斷的程式可以在以後某個時間繼續(xù)。中斷的特點是隨機性，發(fā)生中斷的時間或原因與現(xiàn)行程式可以沒有邏輯上的聯(lián)系。這就必須保證現(xiàn)行程式被隨機中斷後能在以後繼續(xù)正確執(zhí)行。把引起中斷的那些事件稱為中斷源，中斷源向ＣＰＵ發(fā)出的請求處理信號謂之中斷請求，發(fā)生中斷時現(xiàn)行程式的暫停點謂之中斷點，ＣPＵ暫?，F(xiàn)行程式而轉(zhuǎn)去回應(yīng)中斷請求的過程謂之中斷回應(yīng)，處理中斷源的程式謂之中斷處理程式，ＣＰＵ執(zhí)行相關(guān)的中斷處理程式謂之中斷處理，而返回中斷點的過程謂之中斷返回。２.中斷類型（１）輸入輸出中斷（２）硬體故障中斷（３）程式中斷（４）訪管中斷（５）外部中斷３.中斷回應(yīng)圖１-３交換程式狀態(tài)字４.中斷處理與中斷返回

中斷機構(gòu)是由硬體和軟體兩部分組成的，硬體實現(xiàn)中斷請求和中斷回應(yīng)，而軟體（操作系統(tǒng)程式）則完成中斷處理和中斷返回。中斷處理就是執(zhí)行中斷處理程式。系統(tǒng)為每類中斷源都預先安排好了相應(yīng)的中斷處理程式，它們的入口地址存於相應(yīng)的新程式狀態(tài)字單元中。中斷返回即ＣＰＵ轉(zhuǎn)去執(zhí)行前面被中斷的程式，這通過執(zhí)行一條“送老ＰＳＷ的特權(quán)指令將老程式狀態(tài)字單元的內(nèi)容送入現(xiàn)行ＰＳＷ寄存器即可。５.３時鐘

（１）在批處理系統(tǒng)中，利用時鐘計數(shù)對用戶作業(yè)使用各類資源的時間進行統(tǒng)計記帳；（２）在分時系統(tǒng)中，用間隔時鐘實現(xiàn)按時間片對各終端用戶輪轉(zhuǎn)服務(wù)；（３）在即時系統(tǒng)中，按要求的時間間隔輸出時間週期信號給一個即時控制設(shè)備；（４）定時喚醒那些要求延遲或在給定時刻執(zhí)行的某個事件，如定時執(zhí)行某個程式；（５）可以幫助系統(tǒng)發(fā)現(xiàn)一個陷入死迴圈的無效作業(yè)；（６）提供絕對時間（年、月、日）。５.４存貯保護

１.界限寄存器方法是在ＣＰＵ中設(shè)置一對界限寄存器，分別存放現(xiàn)行程式在內(nèi)存中的下限地址和上限地址（或存貯長度），每當執(zhí)行訪內(nèi)操作時，硬體將自動檢查被訪問的記憶體地址是否處於界限寄存器所限定的地址範圍內(nèi)，若越出範圍便產(chǎn)生地址越界中斷，表示這是非法訪問。只有操作系統(tǒng)可以訪問全記憶體。

２.存貯保護鍵所謂存貯保護鍵是由若干二進位組成的標誌。一些電腦系統(tǒng)將記憶體劃分成若干定長的存貯塊，並賦予每個存貯塊一個附加的不在編址範圍內(nèi)的存貯保護鍵。當一個作業(yè)進入記憶體時，操作系統(tǒng)賦予它一個唯一的保護鍵碼，並將分配給該作業(yè)的各存貯塊也置成同樣的保護鍵碼。當該作業(yè)被調(diào)度到ＣＰＵ上執(zhí)行時，操作系統(tǒng)同時將其保護鍵碼置入現(xiàn)行ＰＳＷ中“鍵”字段中。此後每當執(zhí)行訪內(nèi)操作時，硬體將先檢查該存貯塊的保護鍵碼與現(xiàn)行ＰＳＷ中的鍵值是否匹配。若匹配才允許訪問。對操作系統(tǒng)程式通常賦予一個特殊的保護鍵碼，如二進位組成的全“０”或全“１”碼，它賦予操作系統(tǒng)可以訪問全記憶體的特權(quán)?！欤恫僮飨到y(tǒng)的裝入和初啟

操作系統(tǒng)進駐記憶體後，首先執(zhí)行操作系統(tǒng)的初啟程序，它完成以下三項工作：（１）對操作系統(tǒng)的全局數(shù)據(jù)結(jié)構(gòu)置初值；（２）為操作系統(tǒng)的某些程式建立進程，這些系統(tǒng)進程在操作系統(tǒng)的整個生存期間不被撤銷；（３）將ＣＰＵ控制轉(zhuǎn)交給操作系統(tǒng)的ＣＰＵ低級調(diào)度（進程調(diào)度）程式。第二章進程及作業(yè)管理§1進程概念§2系統(tǒng)內(nèi)核§3進程控制

§4進程同步§5進程通訊

§6作業(yè)概念§7作業(yè)控制§1進程概念1.1程式的順序執(zhí)行與併發(fā)執(zhí)行在單道程式系統(tǒng)中，程式的執(zhí)行必然具有下述特性：(1)順序性(2)封閉性(3)無關(guān)性(4)可再現(xiàn)性對於多道程序系統(tǒng)，程式的執(zhí)行就有一些新的特性：(1)非同步性(2)競爭性(3)相互制約(4)與速度有關(guān)

設(shè)有兩個迴圈結(jié)構(gòu)的程式A和B，它們共用一個公共變數(shù)n。程式A每執(zhí)行一次迴圈都要作n：＝n＋1操作；程式B在每一次迴圈中列印出n的值，然後將n置0。對此的PASCAL描述如下：cobegin/coend表示併發(fā)結(jié)構(gòu)，其中的程式可以併發(fā)執(zhí)行。由於程式A和B都是非同步執(zhí)行，它們的語句在時間上可能是穿插或交叉執(zhí)行的，故程式A的n:＝n＋1操作既可能在程式B的print(n)和n:＝0操作之前或之後執(zhí)行，也可能在它們之間執(zhí)行(即n:＝n＋1出現(xiàn)在print(n)之後，而在n:＝0之前)。於是，程式的運行可能產(chǎn)生三組不同的執(zhí)行軌跡和結(jié)果(設(shè)在開始某個迴圈之前n＝v)：1.2進程定義(1)進程是一種動態(tài)概念。(2)進程的實體是程式和數(shù)據(jù)集合。(3)進程是可併發(fā)的運行單位。1.3進程的狀態(tài)(1)執(zhí)行狀態(tài)(2)就緒狀態(tài)(3)等待狀態(tài)(4)停止狀態(tài)(5)死鎖狀態(tài)圖2-1進程的生命歷程圖2-2具有掛起狀態(tài)的進程生命歷程1.4進程控制塊圖2-3進程的物理表示PCB包含了進程的描述資訊和控制資訊，通常有如下專案：(1)識別字(2)存貯資訊(3)現(xiàn)行狀態(tài)(4)優(yōu)先數(shù)(5)現(xiàn)場資訊(6)鏈接字(或稱佇列指針)(7)族系關(guān)係(8)資源清單(9)其他PCB的內(nèi)容和大小隨系統(tǒng)不同而異，它不僅和具體系統(tǒng)的管理及控制方法有關(guān)，也和系統(tǒng)規(guī)模的大小有關(guān)。為了便於管理，系統(tǒng)把所有的PCB用適當方式組織起來。一般說來，大致有以下三種組織方式：

(1)線性表方式

(2)索引方式

(3)鏈接方式圖2-4PCB的組織方式圖2-4PCB的組織方式圖2-5進程家族樹§2系統(tǒng)內(nèi)核

把操作系統(tǒng)中的所有程式模組分成兩大類，即進程模組和非進程模組。進程模組是系統(tǒng)進程的程式實體，例如POOLing程式、磁片管理程式、作業(yè)流控制程式等等，它們以進程的形式在系統(tǒng)中併發(fā)運行，執(zhí)行相應(yīng)的系統(tǒng)功能。非進程模組是不以進程形式獨立運行的程式，每個這樣的程式實現(xiàn)系統(tǒng)管理功能的某種相對獨立的基本操作，在教科書中通常稱這類模組為“原語”(Primitive)。原語是機器指令的延伸，一條原語由若干機器指令所組成，有時也稱之為“軟指令”。

所有的原語組成了操作系統(tǒng)的一個核心，稱之為內(nèi)核(Kernel)。從系統(tǒng)層次結(jié)構(gòu)上看，內(nèi)核處於操作系統(tǒng)的最底層，即它是最接近裸機的部分，而且內(nèi)核通常只占整個操作系統(tǒng)代碼中的一小部分，但卻是最頻繁使用的部分，因而內(nèi)核一般常駐記憶體。內(nèi)核中除了涉及CPU管理、存貯器管理、設(shè)備管理、檔管理以及進程管理的各種原語之外，還包括各種中斷處理、收費記帳等程式模組。

中斷處理是內(nèi)核最重要的功能之一。系統(tǒng)中所有中斷都由內(nèi)核回應(yīng)，當內(nèi)核回應(yīng)一個中斷時，它遮罩其他中斷信號，在處理完一個中斷後，它又繼續(xù)回應(yīng)其他中斷。當確定了某個中斷的原因後，內(nèi)核把中斷處理的具體任務(wù)交給專門處理這類中斷的特定進程或程式，這樣就使內(nèi)核能夠及時回應(yīng)連續(xù)不斷發(fā)生的各種中斷。

裸機經(jīng)內(nèi)核擴充後構(gòu)成了電腦系統(tǒng)的第一層“虛擬機”，所有的進程都在這個虛擬機上運行。該虛擬機有三個屬性：

(1)它沒有中斷，面向進程的是一個沒有中斷的運行環(huán)境，因此進程中無需回應(yīng)中斷；

(2)它為每個進程提供了一臺虛擬處理機，每個進程都好象在各自的處理機上順序地執(zhí)行；（３）它為進程提供了強大的指令系統(tǒng),即由機器指令系統(tǒng)和所有原語組成的指令集合?！?進程控制3.1建立、停止及撤銷

一個進程可借助於“建立”原語創(chuàng)建一個新進程，前者為後者的父進程，後者為前者的子進程。建立新進程的工作通常包括：從PCB集合中獲取一個空閒PCB；對該PCB進行初始化；為新進程的數(shù)據(jù)集分配記憶體空間並初始化；為新進程的程式文本分配記憶體空間並裝入該程式；將新進程的PCB插入就緒佇列。在一些系統(tǒng)中(如UNIX)允許子進程在被建立時可以直接繼承父進程的某些特徵和資源，例如優(yōu)先數(shù)、終端、可共用的打開檔等。建立原語可大致描述如下：procedurecreate(pn,pri,res,fn,args);begingetfreepcb(i);ifi=NILthenreturn(NIL);i.id:=pn;i.priority:=pri;i.resources:=res;memallocate(datasetsize,add);ifadd=NILthenbeginpcbrelease(i)return(NIL);end;end;i.dataadd:=add;i.datasize:=datasetsize;datasetinit(i.dataadd,args);filestate(fn,add,size);ifadd=NILthenbeginmemallocate(size,add);ifadd=NILthenbeginmemrelease(i.dataadd,i.datasize);pcbrelease(i);return(NIL);end;read(fn,size,add);end;i.textadd:=add;i.textsize:=size;g:=fn;i.pc=add;i.children:=0;i.parent:=EXE;EXE.children:=EXE.children+1;i.state:＝'ready';i.queue:=RQ;insert(RQ,i);otherinit;return(i);end;

調(diào)用參數(shù)說明如下：pn為新進程的外部名；res為新進程的初始資源，如終端、父進程的打開檔表等；pri為新進程的初始優(yōu)先數(shù)；fn為新進程的執(zhí)行程式文本之檔案名；args是fn的參數(shù)表。

過程getfreepcb從PCB集中獲取一個空閒PCB，返回值i為PCB號。過程memallocate按指定要求分配記憶體空間，返回記憶體區(qū)地址add。過程memrelease和pcbrelease分別釋放指定記憶體區(qū)和PCB。過程datasetinit初始化數(shù)據(jù)區(qū)，並裝入?yún)?shù)表args。過程filestate檢查指定檔的存貯狀態(tài)，若該檔駐在內(nèi)存，則返回其記憶體區(qū)地址add及長度size，同時將該檔的共用計數(shù)加1，這表明新進程將與其它進程共用一個純代碼程式；否則打開該檔，返回檔長度size,add=NIL。過程read讀入指定檔。過程insert(RQ,i)將新進程插入就緒佇列RQ。otherinit表示對PCB的其他項置初值，如消息佇列信號量、進程現(xiàn)場等。EXE是執(zhí)行態(tài)進程的PCB指針，本原語由執(zhí)行態(tài)進程調(diào)用，故執(zhí)行態(tài)進程就是新進程的父進程。本原語最後返回新進程的內(nèi)部號，即PCB號。如果建立失敗，則返回NIL。

一個進程一旦被建立便處於就緒狀態(tài)，隨時等候被進程調(diào)度選中並啟動執(zhí)行。一個進程在正常運行結(jié)束後，一般應(yīng)主動終止而進入停止狀態(tài)，同時向父進程發(fā)一“完成”消息，等待父進程撤銷它，這通過調(diào)用“停止”原語實現(xiàn)。停止原語halt的大致描述如下：procedurehalt;beginEXE.state:='stop';send(EXE.parent,'completed');EXE:=NIL;scheduler;end;撤銷原語可大致描述如下：proceduredestory(i);beginifi.state′stop′thenremove(i.queue,i);whilei.children>0dobegini.children:=i.children-1;findchild(i,child);destory(child);end;memrelease(i.dataadd,i.datasize);close(g,t);ift=truethenmemrelease(i.textadd,i.textsize);resrelease(i);pcbrelease(i);end;

其中，過程remove將指定進程移出所屬狀態(tài)佇列；過程findchild尋找指定進程的子進程，返回子進程的內(nèi)部號；過程close關(guān)閉指定檔，若返回值t=true表示關(guān)閉成功，否則表示該檔為共用檔且正被其他進程所使用；過程resrelease釋放除記憶體之外的其他資源。本原語可遞歸調(diào)用，用以實現(xiàn)撤銷指定進程的子孫進程。3.2掛起與啟動

掛起原語suspend和啟動原語activate的調(diào)用參數(shù)均為進程內(nèi)部號。它們可描述如下：proceduresuspend(i);begini.state:=ifi.state=′ready′then′readys′else′waiteds′;swapout(i.dataadd,i.datasize,add);i.swapadd:=add;memrelease(i.dataadd,i.datasize);close(g,t);ift=truethenmemrelease(i.textadd,i.textsize);end;

其中，調(diào)用了換出過程swapout將數(shù)據(jù)集複製到外存交換區(qū)並返回相應(yīng)的地址。進程實體中的執(zhí)行程式並未被複製到交換區(qū)，因為執(zhí)行程式檔尚在外存並未被撤銷，但仍要回收它所佔用的記憶體空間(若它未被其他進程共用)，這樣做的好處是減少了交換時間。procedureactivate(i);beginmemallocate(i.datasize,add);ifadd=NIL

thenreturn(false);swapin(i.swapadd,i.datasize,add);i.dataadd:=add;filestate(g,add,size);ifadd=NILthenbeginmemallocate(size,add);ifadd=NILthenbeginmemrelease(i.dataadd,i.datasize);return(false);end;read(g,size,add);end;i.textadd:=add;i.state:=ifi.state=′readys′then′ready′else′waited′;return(true);end;3.3阻塞與喚醒

進程從執(zhí)行態(tài)到等待態(tài)以及從等待態(tài)到就緒態(tài)的過渡分別是通過阻塞原語block和喚醒原語wakeup實現(xiàn)的。當現(xiàn)行進程需要等待某個事件時，可調(diào)用block原語使自己加入到該事件的等待佇列中，調(diào)用參數(shù)為等待佇列指針。操作系統(tǒng)為每類事件設(shè)置一個等待佇列，當某個事件發(fā)生時，通過wakeup原語移出相應(yīng)等待佇列中的某個進程，將其送入應(yīng)緒佇列，調(diào)用參數(shù)也是等待佇列指針，下麵是block原語和wakeup原語的類PASCAL語言描述：procedureblock(q);beginsave(EXE);EXE.state:=′waited′;EXE.queue:=q;insert(q,EXE);EXE:=NIL;scheduler;endprocedurewakeup(q);beginoutqueue(q,i);i.state:=ifi.state=′waited′then′ready′else′readys′;i.queue:=RQ;insert(RQ,i);end;§4進程同步4.1同步概念

對同步與互斥的上述解釋表明，它們的實質(zhì)都是對進程在執(zhí)行時序上的某種限制。因此，可把它們歸結(jié)為：併發(fā)進程在執(zhí)行時序上的相互制約關(guān)係。這就是廣義同步概念。故在廣義上，互斥是一種特殊的同步。4.2臨界區(qū)

併發(fā)進程可以共用系統(tǒng)中的各種資源，但是系統(tǒng)中某些資源具有一次只允許一個進程所使用的屬性，我們稱這樣的資源為臨界資源。換言之，若有一進程正在使用某臨界資源，那麼其他欲使用該資源的進程必須等待，只有當佔有者釋放後，其他進程才能使用。也就是說，共用臨界資源的進程必須互相排斥。

許多物理設(shè)備都屬於臨界資源，如輸入機、印表機、磁帶機等。還有許多可以被幾個進程所修改的共用變數(shù)(如公共變數(shù)、數(shù)據(jù)、表格、佇列等)也是臨界資源。例如，進程A和B共用一個公共變數(shù)count,都要對count執(zhí)行“count:=count+1”操作，但是在許多電腦上完成這一操作，實際上是由三條指令來實現(xiàn)的，如：

LDR1，countINCR1LDcount,R1

由於進程A和B非同步前進，故A、B中相同的這個指令串可能在逐條指令基礎(chǔ)上交叉執(zhí)行，比如產(chǎn)生序列：

A:LDR1,countA:INCR1B:LDR1,countA:LDcount,R1B:INCR1B:LDcount,R1count經(jīng)A、B訪問後，只加了1，而不是所希望的2。為了防止發(fā)生這種與時間有關(guān)的錯誤，變數(shù)count必須按臨界資源處理。

系統(tǒng)的同步機構(gòu)對解決臨界區(qū)互斥問題應(yīng)遵循下述準則：(1)當無一進程處於臨界區(qū)內(nèi)時，若有一進程要求進入臨界區(qū)，應(yīng)讓其立即進入-有空讓進；

(2)當已有進程在臨界區(qū)內(nèi)時，其他欲進入臨界區(qū)的進程必須等待-無空等待；

(3)當無一進程處於臨界區(qū)，而同時有多個進程要求進入臨界區(qū)，且僅讓其中之一進入，其他則等待-多中擇一；

(4)任一進程進入臨界區(qū)的要求應(yīng)在有限時間滿足-有限等待；

(5)處於等待進入臨界區(qū)的進程應(yīng)放棄佔用CPU-讓權(quán)等待。4.3同步機構(gòu)1．測試與設(shè)置(TestandSet)

這是一種借助一條硬體指令TestandSet(簡記TS)來實現(xiàn)互斥的同步機構(gòu)。許多電腦中都提供了這種指令，在IBM370中稱TS指令，在Z8000中稱TSET指令，在Intel8086/8088中稱XCHG指令。TS指令的功能可用PASCAL語言描述如下：procedureTS(vara,b:boolean);vartemp:boolean;begintemp:=a;a:=b; （１）

b:=tempend或

functionTS(varb:boolean):boolean;beginTS:=b;b:=true （２）

endvTS指令的執(zhí)行是不可分割的，利用TS指令可以簡單而有效地實現(xiàn)互斥。其方法是為每個臨界資源設(shè)置一個布爾變數(shù)lock(鎖)，其初值為falsc，當lock值為false表示鎖打開，臨界資源未被使用，進程可進入臨界區(qū)；反之則表示鎖關(guān)閉，進程不能進入。於是用TS指令實現(xiàn)互斥的進程的程式結(jié)構(gòu)為：varkey:blooean;begin…key:=true;whilekeydoTS(lock,key); （１′）

CS(臨界區(qū))；

lock:=false;…end或begin…whileTS(lock)doskip;CS; （２′）

lock:=false;…end2．信號量和P、V操作

荷蘭的著名電腦科學家Dijkstra把互斥的關(guān)鍵含義抽象成信號量(semaphore)概念，並引入在信號量上的P、V操作作為同步原語(P和V分別是荷蘭文的“等待”和“發(fā)信號”兩詞的首字母)。信號量是個被保護的量，只有P、V操作和信號量初始化操作才能訪問和改變它的值，Dijkstra把信號量s定義為一個非負整型量。把信號量s上的P操作P(s)定義為：若s>0，則s值減1，否則執(zhí)行進程等待，直到其他進程對s進行V操作。把信號量s上的V操作V(s)定義為：s值加1，若有進程在s上等待，則喚醒其中一個進程。

信號量和P、V操作原語可構(gòu)成“阻塞-喚醒”同步機構(gòu)：當一個進程對值為0的信號量執(zhí)行P操作時便被阻塞以等待某個事件的出現(xiàn)；在另一進程檢測到該事件發(fā)生時，通過執(zhí)行V操作喚醒被阻塞的進程。在實現(xiàn)該同步機構(gòu)時，可採取“忙等待”方式也可採取“讓權(quán)等待”方式。在忙等待方式下，被阻塞進程在不主動放棄處理機的情況下忙碌等待著其他進程來喚醒它，顯然這不利於處理機的有效利用。讓權(quán)等待方式，即當執(zhí)行進程必須在某信號量上等待時，就將該進程變?yōu)榈却隣顟B(tài)，並將其插入與此信號量相關(guān)的等待佇列中，以讓出處理機給其他就緒進程。在單機系統(tǒng)中普遍採用讓權(quán)等待方式。而在多機系統(tǒng)中，為減少進程狀態(tài)變換而引起的開銷，可採取忙等待方式。另外，在具體實現(xiàn)時通常要對Dijkstra的原定義進行改進。(1)忙等待方式的P、V操作。

vars:integer;P(s):whiles≤0doskip;s:=s-1；

V(s):s:=s+1;

當一進程在值不大於0的信號量s上執(zhí)行P操作時，將在迴圈語句while上陷入忙等待，直到其他進程在該信號量s上執(zhí)行V操作後，解除它的等待。不難看出這種形式的P、V操作完全可用硬體指令來實現(xiàn)。(2)讓權(quán)等待方式的P、V操作。採取這種方式需要對原信號量定義進一步擴充，把信號量由整型量擴充成為記錄形式：

typepsem=semaphoresemaphore=recordvalue:integer;qucue:pointertoWQ;end即信號量s是二元組s(v,q),v是信號量s的值，它是個整型量，q是指向s等待佇列WQ的隊首指針。於是P、V操作可分別描述為：procedurep(s);vars:psem;begins.v:=s.v-1;ifs.v<0thenblock(s.q)endprocedureV(s);vars:psem;begins.v:=s.v+1ifs.v≤0thenwakeup(s.q)end

根據(jù)上述定義，P、V操作的物理意義可這樣來看待。s.v>0表示某類資源的當前可用數(shù)。每執(zhí)行一次P操作意味著請求分配一個單位的資源，因此描述為s.v:=s.v-1;s.v≤0表示該類資源已不能供分配，因此請求資源的進程將被阻塞在等待佇列s.q中，此時s.v的絕對值等於等待佇列s.q中的進程數(shù)。執(zhí)行一次V操作意味著釋放一個單位資源，故描述為.v:=s.v+1，若s.v≤0，表示在等待佇列s.q中有因請求該資源不能滿足而被阻塞的進程，因此喚醒等待佇列s.q中的第一個或優(yōu)先數(shù)最高的進程，允許其使用該資源。4.4信號量的應(yīng)用1．臨界區(qū)的互斥

利用信號量可方便地實現(xiàn)臨界區(qū)的互斥執(zhí)行。此時信號量是公用信號量，它的初值為1，每個進程均可對它施行P、V操作。設(shè)mutex為互斥信號量，其初值為1，表示對應(yīng)的臨界資源R未被佔用。對於每個想使用R的進程，只需把它們的臨界區(qū)CS置於P(mutex)和V(mutex)之間，即可實現(xiàn)互斥。下麵給出這種模型的大致描述：varmutex:psem;procedureprocesslbeginwhiletruedobegin…p(mutex);CS1;V(mutex);…endend;procedureprocess2:…;procedureprocessn:…;beginseminitial(mutex.v,l);cobeginprocess1;process2;…processn;coendend2．合作進程的同步利用信號量同樣可以方便地實現(xiàn)合作進程之間的同步。方法是為某個事件設(shè)置一個信號量event,event.v的初值為0，表示該事件還未發(fā)生，當一進程需要等待event對應(yīng)的事件時執(zhí)行P(event)，如果此時event.v=0，則阻塞該進程，將它掛入event的等待佇列；若event.v=1，則表示事件已發(fā)生，該進程可繼續(xù)執(zhí)行。當某進程完成了event的事件時，立即執(zhí)行V(event)喚醒event等待佇列中的某個進程。我們把信號量event稱為私用信號量，即只有需要等待event相應(yīng)事件發(fā)生的進程或說需要其他某個進程給予合作的進程在event上執(zhí)行P操作，而完成event事件的進程或說提供合作的進程只在event上執(zhí)行V操作。3．生產(chǎn)者與消費者關(guān)係圖2-6環(huán)形緩衝池

基於環(huán)形緩衝池的生產(chǎn)者與消費者關(guān)係的形式描述，設(shè)：

(1)公用信號量mutex:初值為1，用於實現(xiàn)臨界區(qū)互斥；

(2)生產(chǎn)者私用信號量empty:初值為n，指示空緩衝塊數(shù)目；(3)消費者私用信號量full:初值為0，指示滿緩衝塊數(shù)目；

(4)整型量i和j：初值均為0，i指示首空緩衝塊序號，j指示首滿緩衝塊序號。varmutex,empty,full:psem;i,j:integer;buffer:array0…n-1ofstuff;procedureproducer;生產(chǎn)者進程

beginwhiletruedobeginproducenextproduct;P(empty);P(mutex);buffer(i):=product;i:=(i+1)modn;V(mutex);V(full)endend;procedureconsumer;消費者進程

beginwhiletruedobeginP(full);P(mutex)goods:=buffer(j);j:=(j+1)modn;V(mutex);V(empty);consumeproductendend;beginseminitial(mutex^.v,1;empty^.v,n;full^.v,0);i:=j:=0;cobeginproducer;consumer;coendend4．讀者與寫者關(guān)係

設(shè)某航空公司有2個售票處，它們通過遠程終端訪問設(shè)在公司總部的航空訂票系統(tǒng)，並要查詢或修改系統(tǒng)中記錄所有班機當前訂票數(shù)的資料庫B。設(shè)Bi為某班機的當前訂票數(shù)，P1和P2分別代表2個售票處的售票進程，R1和R2為進程執(zhí)行時使用的工作寄存器。由於售票進程併發(fā)執(zhí)行，且各自訪問資料庫B的時間是隨機的，故有可能出現(xiàn)下麵的訪問序列(假定Bi的當前值為x)：P1:R1:=Bi

R1:=R1+1P2:R2:=Bi

R2:=R2+1Bi:=R2

P1:Bi:=R1

可見，Bi的新值是X+1，而不是正確的X+2。這裏的P1和P2均為寫者，顯然，對於寫者Bi為臨界資源，因此寫者應(yīng)該互斥。讀者進程與寫者進程的一般結(jié)構(gòu)：varmutex,wrt:psem;readcount:integer;seminit(mutex.v,1;wrt.v,1);readcount:=0;cobeginprocedurereader;beginP(mutex);readcount:=readcount+1;ifreadcount=1thenP(wrt);V(mutex);readingisperfermed；

P(mutex);readcount:=readcount-1；

ifreadcount=0thenＶ(wrt)；

V(mutex);end;Procedurewriter;begin

Ｐ(wrt);writingisperfermed;V(wrt);end;coend;4.5管程概念

建立管程的基本理由是：由於對臨界區(qū)的執(zhí)行分散在各進程中，這樣不便於系統(tǒng)對臨界資源的控制和管理，也很難發(fā)現(xiàn)和糾正分散在用戶程式中的對同步原語的錯誤使用等問題。為此，應(yīng)把分散的各同類臨界區(qū)集中起來。並為每個可共用資源設(shè)立一個專門的管程來統(tǒng)一管理各進程對該資源的訪問。這樣既便於系統(tǒng)管理共用資源，又能保證互斥訪問。管程主要由兩部分組成：

(1)局部於該管程的共用數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)；

(2)局部於該管程的若干過程，每個過程完成關(guān)於上述數(shù)據(jù)的某種規(guī)定操作。

局部於管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)只能被該管程內(nèi)的過程所訪問，反之，局部於管程內(nèi)的過程只能訪問該管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。因此管程就如同一堵圍牆把關(guān)於某個共用資源的抽象數(shù)據(jù)結(jié)構(gòu)以及對這些數(shù)據(jù)施行特定操作的若干過程圍了起來。任一進程要訪問某個共用資源，就必須通過相應(yīng)的管程才能進入。為了實現(xiàn)對臨界資源的互斥訪問，管程每次只允許一個進程進入其內(nèi)(即訪問管程內(nèi)的某個過程)，這是由編譯系統(tǒng)保證的。例如，併發(fā)PASCAL編譯程序在編譯根源程式時，對每一個形如：

cedure/function-entry-name的調(diào)用語句，都將自動保證其按如下方式執(zhí)行：

P(mutex);

執(zhí)行相應(yīng)的過程或函數(shù)

V(mutex);其中，mutex是關(guān)於相應(yīng)管程的互斥信號量，初值為1。管理環(huán)形緩衝池的管程結(jié)構(gòu)。monitorringbuffer;varrbuffer:array［0..n-1］ofstuff;k,nextempty,nextfull:integer;empty,full:condition;procedureentryput(varproduct:stuff);beginifk=nwait(empty);rbuffer［nextempty］:=product;k:=k+1;nextempty:=(nextempty+1)modn;signal(full);end;procedureentryget(vargoods:stuff);beginifk=0wait(full);goods:=rbuffer［nextfull］;k:=k-1;nextfull:=(nextfull+1)modn;signal(empty);end;begink:=0；

nextempty:=0;nextfull:=0;end;

管程ringbuffer包含兩個局部過程：過程put負責執(zhí)行將數(shù)據(jù)寫入某個緩衝塊的操作；過程get負責執(zhí)行從某個緩衝塊讀取數(shù)據(jù)的操作。empty和full被定義為兩個條件變數(shù)，對應(yīng)於緩衝池滿和緩沖池空條件等待佇列。任一進程都必須通過調(diào)用管程ringbuffer來使用環(huán)形緩衝池，生產(chǎn)者進程調(diào)用其中的put過程，消費者進程調(diào)用get過程§5進程通訊5.1消息緩衝通訊

消息緩衝通訊技術(shù)是由Hansen首先提出的，其基本思想是：根據(jù)生產(chǎn)者與消費者關(guān)係原理，利用記憶體的公用消息緩衝池實現(xiàn)進程之間的資訊交換。(1)公用消息緩衝池buffpool這是一個結(jié)構(gòu)數(shù)組，數(shù)組元素是消息緩衝塊buffblock，即

vatbuffpool:array［0…n-1］ofbuffblock;(2)消息緩衝塊buffblock這是一個記錄結(jié)構(gòu)，包含下列內(nèi)容：

sender:消息發(fā)送者名

size:消息長度

text:消息正文

next:指向消息佇列中的下一個(5)emphead空緩佇列首指針，緩衝池中所有空閒緩衝塊組成一個空緩佇列。

(6)emptail空緩佇列尾指針。

(7)mq進程的消息佇列首指針，設(shè)置在PCB中。

(8)mmutex進程的消息佇列互斥信號量，初值為1，設(shè)置在PCB中。

(9)msyn同步信號量，用於消息佇列中的消息計數(shù)，初值為0，設(shè)置在PCB中。(10)發(fā)送消息原語send(receiver,a)進程可調(diào)用本原語向其他進程發(fā)送一則消息，調(diào)用參數(shù)receiver為接收進程名，a為發(fā)送者在自己的記憶體工作區(qū)內(nèi)存放待發(fā)送消息的記憶體區(qū)地址。

(11)接收消息原語receive(a)進程可調(diào)用本原語摘取消息佇列中的一則消息,調(diào)用參數(shù)a為接收者在自己的記憶體工作區(qū)內(nèi)準備複製消息的接收區(qū)地址。圖2-7是消息緩衝通訊下麵是send原語的類PASCAL語言描述：proceduresend(receiver,a)begingetid(receiver,i);ifi=NILthenreturn(false);P(buffempty);P(buffmutex);k:=emphead;emphead;=buffpool［k］.next;V(buffmutex);buffpool［k］.sender:=a.sender;buffpool［k］.size:=a.size;buffpool［k］.text:=a.text;buffpool［k］.next:=NIL;P(i.mmutex);insert(i.mq,k);V(i.mmutex);V(i.msyn);return(true);end;5.2管道通訊1.pipe的建立和使用方式圖2-8兩個進程共用一個pipe2.pipe操作的同步與互斥

在對pipe檔進行讀寫操作過程中要對發(fā)送進程和接收進程實施正確的同步和互斥，以確保通訊的正確性。接收進程讀pipe時，若發(fā)現(xiàn)pipe為空，則進入等待狀態(tài)。一旦有發(fā)送進程對該pipe執(zhí)行寫操作時便喚醒等待進程。不論是讀或?qū)憄ipe時，都要考慮資訊傳送的另一方是否存在。在讀pipe時，若發(fā)現(xiàn)無資訊可讀，則在進入等待態(tài)之前先檢查pipe的寫入端是否已關(guān)閉，若已關(guān)閉，則不必等待。在寫pipe時也要先檢查讀出端是否已關(guān)閉，若已關(guān)閉，則按出錯處理。進程在關(guān)閉pipe檔的寫入或讀出端時，應(yīng)喚醒等待寫或讀該pipe檔的進程。為了防止兩個進程同時讀、寫一個pipe，須為每個pipe設(shè)置互斥標誌。pipe通訊機構(gòu)中的同步與互斥都由系統(tǒng)自動進行，對用戶是透明的。pipe通訊的實質(zhì)是利用外存來進行數(shù)據(jù)通訊，故具有傳送數(shù)據(jù)量大的優(yōu)點，但通訊速度較慢?！?作業(yè)概念

一個作業(yè)(job)是用戶請求電腦執(zhí)行的一個獨立的程式任務(wù)。一個作業(yè)可能需要執(zhí)行為完成同一任務(wù)的若干個程式，這些程式不僅包括用戶自己編寫的用戶程式，也包括為用戶服務(wù)的系統(tǒng)程式。例如，執(zhí)行編輯程式建立和修改用戶根源程式，執(zhí)行編譯程序編譯根源程式，執(zhí)行用戶目標程式等等，程式是作業(yè)的執(zhí)行文本。程式的操作對象(如變數(shù)、檔等)稱之為作業(yè)的數(shù)據(jù)。一個作業(yè)內(nèi)的各個程式的執(zhí)行結(jié)果有著一定的邏輯聯(lián)繫，各程式按一定的順序執(zhí)行，這謂之作業(yè)的工作流程，它是由用戶定義的。此外，每個作業(yè)的運行都有不同的資源需求，例如，CPU時間，存貯空間的大小，需要印表機列印運行結(jié)果等等。用戶對作業(yè)工作流程的控制意圖以及作業(yè)的資源需求，需要用戶使用操作系統(tǒng)提供的控制命令(作業(yè)控制語言JCL或終端命令)向系統(tǒng)說明。

從靜態(tài)觀點看，一個作業(yè)由三部分組成，即作業(yè)＝控制命令序列＋程式集＋數(shù)據(jù)集從系統(tǒng)管理角度，一個作業(yè)的主體是控制命令序列，不同的控制命令序列形成了不同的作業(yè)。多道程序系統(tǒng)支持同時運行多個用戶的作業(yè)，每個用戶還可以建立多個作業(yè)，所謂系統(tǒng)的道數(shù)即同時運行的作業(yè)個數(shù)。作業(yè)有兩種基本類型：脫機作業(yè)和聯(lián)機作業(yè)。脫機作業(yè)包括批處理作業(yè)和後臺作業(yè)，即在批處理環(huán)境下運行的作業(yè)和以後臺方式運行的作業(yè)。聯(lián)機作業(yè)包括終端作業(yè)及前臺作業(yè)，即在分時環(huán)境或交互環(huán)境下運行的作業(yè)和以前臺方式運行的作業(yè)。作業(yè)=控制命令序列+程式集+數(shù)據(jù)集圖2-9作業(yè)的生命歷程7.1作業(yè)的建立JCB是記錄型數(shù)據(jù)結(jié)構(gòu)，一般包含下列內(nèi)容：．作業(yè)名．作業(yè)優(yōu)先順序．作業(yè)在輸入井中的存放地址及長度．作業(yè)的建立時間．作業(yè)的估計運行時間．記憶體需要量．外設(shè)需求．作業(yè)狀態(tài)．作業(yè)類型．鏈接字．其他7作業(yè)控制7.2作業(yè)的運行

一個後備作業(yè)只有被作業(yè)調(diào)度程式選中後才能進入主機運行，即處於運行狀態(tài)，作業(yè)調(diào)度程式為作業(yè)建立相應(yīng)的作業(yè)進程。7.3作業(yè)的完成與註銷(1)調(diào)用撤銷原語destory撤銷作業(yè)進程，包括回收記憶體及外設(shè)資源、釋放PCB，作業(yè)進程也就隨之消亡。

(2)調(diào)用記帳程式，核算作業(yè)的運行費用。

(3)輸出作業(yè)記帳收費資訊以及作業(yè)正?；虍惓＝K止資訊。

(4)回收JCB，最終註銷該作業(yè)。圖2-10JSCP工作流程7.4JSCP工作流程7.5分時系統(tǒng)的作業(yè)控制

在分時環(huán)境下，用戶是以交互會話方式請求系統(tǒng)服務(wù)的，故作業(yè)的建立和運行以及對作業(yè)的控制都與批處理作業(yè)略有差異。系統(tǒng)初啟時先建立系統(tǒng)總控進程，再由它為每個終端建立一個終端管理進程，這相當於一個終端上的作業(yè)流控制進程。第三章處理機調(diào)度§1調(diào)度級別

§2調(diào)度的功能、時機及方式

§3調(diào)度原則與評估標準§4調(diào)度演算法§5調(diào)度的實現(xiàn)§１調(diào)度級別

１.高級調(diào)度

即作業(yè)調(diào)度。它決定允許哪些作業(yè)可參與競爭ＣＰＵ和其他系統(tǒng)資源，從狀態(tài)觀點，就是將一個或一批作業(yè)從後備狀態(tài)變?yōu)檫\行狀態(tài)。一個作業(yè)一旦被高級

調(diào)度選中，便可獲得所需要的基本記憶體和設(shè)備資源，並被裝入記憶體，此後就以進程形式參與併發(fā)運行，與其它進程競爭ＣＰＵ。換言之，高級調(diào)度決定給哪個作業(yè)分配一臺虛擬處理機，獲得虛擬處理機的作業(yè)將在該虛擬處理機上順序執(zhí)行。從這個意義上說，高級調(diào)度進行的是虛擬處理機的分配，即ＣＰＵ的宏觀調(diào)度，故高級調(diào)度亦稱宏觀調(diào)度。

２中級調(diào)度中級調(diào)度決定哪些進程可參與競爭ＣＰＵ，從狀態(tài)觀點，就是將進程從活動態(tài)變?yōu)殪o止的掛起態(tài)，或者將進程從掛起態(tài)變?yōu)榫途w態(tài)或等待態(tài)。這主要是為了短期調(diào)整系統(tǒng)負荷，以緩和記憶體使用緊張的矛盾。中級調(diào)度的實質(zhì)是執(zhí)行“掛起”和“啟動”操作；掛起一個進程是把該進程的實體（程式和數(shù)據(jù)）從記憶體遷移到外存的專門區(qū)域，稱為交換區(qū)，並釋放該進程佔用的用戶記憶體區(qū)，這稱為“換出”；反之，啟動一個進程是把該進程的實體從外存交換區(qū)遷移到記憶體，這稱為“換進”。故中級調(diào)度也常稱為進程交換，通常僅用於分時系統(tǒng)。

３低級調(diào)度

即進程調(diào)度。它決定哪個進程可獲得物理ＣＰＵ，從狀態(tài)觀點，就是將某個進程從就緒態(tài)變?yōu)閳?zhí)行態(tài)。被低級調(diào)度選中的進程將實際獲得ＣＰＵ，並可立即在物理ＣＰＵ上執(zhí)行它的程式。因此，低級調(diào)度是處理機三級調(diào)度中的終結(jié)調(diào)度，亦稱ＣＰＵ的微觀調(diào)度。圖３-１處理機的三級調(diào)度§２調(diào)度的功能、時機及方式２.１作業(yè)調(diào)度的功能與時機

（１）按照某種調(diào)度演算法（即調(diào)度策略），根據(jù)系統(tǒng)資源的當前使用情況和後備作業(yè)對資源的需求，挑選一個或多個後備作業(yè)投入運行；（２）為選中的作業(yè)分配基本的記憶體和設(shè)備資源，這通過調(diào)用記憶體分配程式和設(shè)備分配程式來完成；（３）為選中的作業(yè)建立進程，將進程實體裝入記憶體，這通過調(diào)用建立進程原語來實現(xiàn)。

一般來說，在下列情況下將啟動作業(yè)調(diào)度：（１）設(shè)ｍ為系統(tǒng)支持的在主機上運行的最大作業(yè)數(shù)（也稱道數(shù)），ｎ為在主機上運行的當前作業(yè)數(shù)。如果ｎ＜ｍ，且存在後備作業(yè)，則啟動作業(yè)調(diào)度；（２）當一作業(yè)運行終止而被撤銷後，如果存在後備作業(yè)，則立即啟動作業(yè)調(diào)度崐；（３）在分時系統(tǒng)中，當一用戶在某終端上通過交互會話被核準其註冊的登錄作業(yè)名及其口令後，立即啟動作業(yè)調(diào)度。２.２進程調(diào)度的功能與時機

啟動進程調(diào)度的時機可歸結(jié)為：（１）現(xiàn)行進程執(zhí)行完它的當前ＣＰＵ時值時，這包括現(xiàn)行進程執(zhí)行完畢而終止或現(xiàn)行進程因等待某個事件而自行阻塞，此時需要將ＣＰＵ分配給一個新的就緒進程；（２）在採用剝奪調(diào)度方式的系統(tǒng)中，當發(fā)生了某種剝奪事件，例如，當發(fā)生了時間片中斷或有比現(xiàn)行進程具有更高優(yōu)先順序的進程進入了就緒佇列時，此時系統(tǒng)要回收現(xiàn)行進程佔用的ＣＰＵ並進行重新調(diào)度。２.３調(diào)度方式

一進程在ＣＰＵ上的一次連續(xù)執(zhí)行過程稱為該進程的一個ＣＰＵ週期。一個ＣＰＵ週期由進程自我終止。當進程需等待某個事件而進入等待態(tài)時，便終止了它的當前ＣＰＵ週期。待等待事件發(fā)生後，進程將開始下一個ＣＰＵ週期。進程執(zhí)行完畢進入停止狀態(tài)則終止了它的最後一個ＣＰＵ週期。一個進程在其併發(fā)運行過程中通常有若干個離散的且長短不等的ＣＰＵ週期。例如，一進程需要在ＣＰＵ上執(zhí)行的總時間為１ｓ，在１００ｍｓ、４５０ｍｓ、６００ｍｓ的執(zhí)行點處它分別要等待三個事件而暫停執(zhí)行，即該進程有四個分別為１００ｍｓ、３５０ｍｓ、１５０ｍｓ以及４０ｍｓ的ＣＰＵ週期時值。當現(xiàn)行進程執(zhí)行完它的一個ＣＰＵ週期時，系統(tǒng)應(yīng)及時把ＣＰＵ轉(zhuǎn)交給另一個進程去執(zhí)行它的ＣＰＵ週期，這是導致進程調(diào)度的基本原因，也是實現(xiàn)多部件並行和多進程併發(fā)的基本要求。

進程調(diào)度方式包括剝奪式與非剝奪式。在剝奪方式下，當現(xiàn)行進程正在執(zhí)行它的一個ＣＰＵ週期期間，系統(tǒng)有權(quán)強行分割該進程的當前ＣＰＵ時值，即強行剝奪現(xiàn)行進程正佔用的ＣＰＵ，並把ＣＰＵ分配給另一進程，換言之，如果一個進程的一個ＣＰＵ週期可能被分割成兩個或更多個ＣＰＵ週期，則系統(tǒng)採用的是剝奪式調(diào)度。反之，在非剝奪方式下，一個進程一旦獲得ＣＰＵ便一直執(zhí)行下去，直到完成它的當前ＣＰＵ週期，系統(tǒng)才重新調(diào)度，換言之，系統(tǒng)無權(quán)分割進程的任一ＣＰＵ週期?！欤痴{(diào)度原則與評估標準

一般需綜合考慮以下四個基本調(diào)度原則：（１）儘量提高系統(tǒng)的吞吐量，系統(tǒng)吞吐量是指在單位時間內(nèi)完成的平均作業(yè)數(shù)；（２）均衡利用資源，使ＣＰＵ與外設(shè)儘量都保持“忙”狀態(tài)；（３）對所有的作業(yè)都應(yīng)公平，任何一個作業(yè)的完成都不能被無限延遲；（４）如果支持優(yōu)先順序，應(yīng)對優(yōu)先順序高的作業(yè)或進程給予優(yōu)先服務(wù)。

下麵是幾項主要的評估標準：（１）平均周轉(zhuǎn)時間作業(yè)ｉ從提交時刻ｔis到完成時刻ｔic所經(jīng)歷的時間稱為該作業(yè)的周轉(zhuǎn)時間Ｔｉ，即Ｔｉ＝ｔic－ｔis；進程ｉ從進入就緒佇列的時刻ｔir到執(zhí)行完本次ＣＰＵ週期的時刻ｔic稱為該進程的周轉(zhuǎn)時間Ｔi，即Ｔi＝ｔic－ｔir。於是，ｎ個作業(yè)的平均周轉(zhuǎn)時間或ｎ個進程的平均周轉(zhuǎn)時間Ｔ為：

（２）平均帶權(quán)周轉(zhuǎn)時間作業(yè)ｉ的周轉(zhuǎn)時間Ti與其實際運行時間ｔi之比稱為該作業(yè)的帶權(quán)周轉(zhuǎn)時間，即，同樣，進程ｉ的周轉(zhuǎn)時間Ｔｉ與其本次ＣＰＵ週期的時值之比稱為該進程的帶權(quán)周轉(zhuǎn)時間。於是，ｎ個作業(yè)或ｎ個進程的平均帶權(quán)周轉(zhuǎn)時間Ｔ′為：

（３）平均等待時間進程ｉ從進入就緒佇列那一時刻ｔir到獲得ＣＰＵ的那一時刻ｔip

所經(jīng)歷的時間稱為它的等待時間Ｗi，即Ｗi＝ｔip－ｔir，那麼ｎ個進程的平均等待時間Ｗ為：

通常，用Ｔ來衡量不同調(diào)度演算法對同一作業(yè)流或同一進程集的調(diào)度性能，用Ｗ來衡量不同進程調(diào)度演算法對同一進程集的調(diào)度性能，而用Ｔ′來衡量同一調(diào)度演算法對不同作業(yè)流或不同進程集的調(diào)度性能?！欤凑{(diào)度算法４.１先來先服務(wù)ＦＣＦＳ

假定有四個作業(yè)，它們的進入、估計運行和完成時間以及平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間如表３-１所示。

考慮三個進程Ｐ１、Ｐ２和Ｐ３，它們的本次ＣＰＵ週期的時值分別為２１ｍｓ、６ｍｓ和３ｍｓ，且以Ｐ１、Ｐ２Ｐ３的次序處於就緒佇列中，不妨認為它們進入就緒佇列的相對時刻均為０。於是，在ＦＣＦＳ調(diào)度下，其執(zhí)行過程可表示如下：P1P2P30212730

Ｐ１、Ｐ２和Ｐ３的等待時間分別為０、２１和２７，周轉(zhuǎn)時間分別為２１、２７和３０，故它們的平均等待時間和平均周轉(zhuǎn)時間分別為：

ＦＣＦＳ演