整套課件：操作系統(tǒng)（第二版）

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

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

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

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

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

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

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

２.分時系統(tǒng)（Ｔｉｍｅ-ｓｈａｒｉｎｇＳｙｓｔｅｍ）所謂“分時”，就是多個用戶對系統(tǒng)資源進(jìn)行時間上的分享。在分時環(huán)境下，一個計算機(jī)系統(tǒng)聯(lián)有若干臺本地或遠(yuǎn)程終端，每個用戶可以在所占用的終端上以人-機(jī)會話的交互方式使用計算機(jī)。故分時系統(tǒng)又稱為多用戶交互式共享系統(tǒng)。分時系統(tǒng)具有以下三個特點：（１）多路性（２）交互性（３）獨(dú)占性

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

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

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

所謂操作系統(tǒng)的程序級接口，就是操作系統(tǒng)與目態(tài)程序之間的接口。當(dāng)執(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ù)的“訪管”指令（ＳＶＣ）或“陷入”指令（ｔｒａｐ）。當(dāng)機(jī)器執(zhí)行ＳＶＣ或ｔｒａｐ指令時將引起訪管中斷，ＣＰＵ狀態(tài)變?yōu)楣軕B(tài)，保留調(diào)用現(xiàn)場，然后去崐執(zhí)行相應(yīng)的某個操作系統(tǒng)程序，當(dāng)該操作系統(tǒng)程序執(zhí)行完畢，經(jīng)中斷機(jī)構(gòu)返回，ＣＰＵ由管態(tài)又復(fù)變?yōu)槟繎B(tài)。目態(tài)程序請求操作系統(tǒng)服務(wù)的唯一途徑就是使用系統(tǒng)調(diào)用命令。操作系統(tǒng)在程序級提供以下幾類功能服務(wù)：（１）進(jìn)程控制（２）文件操作（３）設(shè)備管理（４）信息維護(hù)（５）通信２.作業(yè)控制級接口

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

（１）脫機(jī)級接口即作業(yè)控制語言ＪＣＬ（ＪｏｂＣｏｎｔｒｏｌＬａｎｇｕａｇｅ），由批處理系統(tǒng)提供。ＪＣＬ有兩種形式：一種相當(dāng)于匯編語言，如ＩＢＭ３７０的ＪＣＬ；另一種類似于高級語言，如１９００系列的Ｇｅｏｒｇｅ語言。ＪＣＬ的語句就是控制和服務(wù)命令。在批處理系統(tǒng)的脫機(jī)服務(wù)方式下，用戶把他對系統(tǒng)的服務(wù)請求和對其作業(yè)運(yùn)行的控制意圖事先用ＪＣＬ編寫一份“上機(jī)說明書”并制成作業(yè)控制卡或作業(yè)說明書，隨同程序和數(shù)據(jù)一起提交給計算機(jī)系統(tǒng)。在系統(tǒng)處理作業(yè)時，逐條解釋執(zhí)行ＪＣＬ語句，實現(xiàn)對作業(yè)運(yùn)行的自動控制。在作業(yè)運(yùn)行時，用戶不得再干預(yù)。①作業(yè)標(biāo)識語句ＪＯＢ。ＪＯＢ標(biāo)識一個作業(yè)的開始，它作為作業(yè)卡片迭的第一張。一般格式是：∥ＪＯＢｊｏｂｎａｍｅ［ｐａｒａｍｅｔｅｒｓ］其中：∥表示這是控制卡；ｊｏｂｎａｍｅ為作業(yè)名，由字母打頭的１～８個字符；

parameters是可選參數(shù)，它可以是帳號、用戶名、作業(yè)優(yōu)先數(shù)、作業(yè)運(yùn)行的估計時間等。②執(zhí)行語句ＥＸＥＣ。標(biāo)志一個作業(yè)步開始，裝入并啟動可執(zhí)行程序。一般格式是：∥ＥＸＥＣ［［ＰＧＭ＝］ｐｒｏｇｎａｍｅ］［，ｇｏ］或∥ＥＸＥＣＰＲＯＣ＝ｐｒｏｃｎａｍｅ其中：ｐｒｏｇｎａｍｅ是要裝入執(zhí)行的程序名，若缺省，則把最近連接產(chǎn)生的可執(zhí)行程序裝入執(zhí)行；ｐｒｏｃｎａｍｅ是從過程庫中取出執(zhí)行的程序名；ｇｏ表示調(diào)用連接裝配程序，對編譯產(chǎn)生的目標(biāo)模塊進(jìn)行連接并裝入運(yùn)行。③選擇語句ＯＰＴＩＯＮ。描述作業(yè)要求的某些服務(wù)請求。例如，打印程序清單ＬＩＳＴ，打印錯誤表ＥＲＲＳ，連接目標(biāo)模塊ＬＩＮＫ等。一般格式是：∥ＯＰＴＩＯＮｏｐｔｉｏｎ［,ｏｐｔｉｏｎ…］其中，OPTION,option[,option…]④程序或數(shù)據(jù)定界語句／。用以標(biāo)志程序或數(shù)據(jù)的結(jié)束。⑤作業(yè)定界語句／&。用以標(biāo)識作業(yè)的結(jié)束。此外，還有請求外設(shè)分配，指定磁盤，帶標(biāo)號等語句。下面是一個簡單的例子：∥ＪＯＢＤＡＶＩＳ∥ＯＰＴＩＯＮＬＩＮＫ∥ＥＸＥＣＰＡＳＣＡＬ；執(zhí)行ｐａｓｃａｌ編譯程序(ｐａｓｃａｌ源程序）／*∥ＥＸＥＣＬＩＮＫＥＤＴ；執(zhí)行連接程序∥ＥＸＥＣ；執(zhí)行剛產(chǎn)生的可執(zhí)行程序（數(shù)據(jù)）／*／&；作業(yè)結(jié)束

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

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

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

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

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

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

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

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

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

操作系統(tǒng)進(jìn)駐內(nèi)存后，首先執(zhí)行操作系統(tǒng)的初啟程序，它完成以下三項工作：（１）對操作系統(tǒng)的全局?jǐn)?shù)據(jù)結(jié)構(gòu)置初值；（２）為操作系統(tǒng)的某些程序建立進(jìn)程，這些系統(tǒng)進(jìn)程在操作系統(tǒng)的整個生存期間不被撤消；（３）將ＣＰＵ控制轉(zhuǎn)交給操作系統(tǒng)的ＣＰＵ低級調(diào)度（進(jìn)程調(diào)度）程序。第二章進(jìn)程及作業(yè)管理§1進(jìn)程概念§2系統(tǒng)內(nèi)核§3進(jìn)程控制§4進(jìn)程同步§5進(jìn)程通訊§6作業(yè)概念§7作業(yè)控制§1進(jìn)程概念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è)有兩個循環(huán)結(jié)構(gòu)的程序A和B，它們共享一個公共變量n。程序A每執(zhí)行一次循環(huán)都要作n：＝n＋1操作；程序B在每一次循環(huán)中打印出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之前)。于是，程序的運(yùn)行可能產(chǎn)生三組不同的執(zhí)行軌跡和結(jié)果(設(shè)在開始某個循環(huán)之前n＝v)：1.2進(jìn)程定義(1)進(jìn)程是一種動態(tài)概念。(2)進(jìn)程的實體是程序和數(shù)據(jù)集合。(3)進(jìn)程是可并發(fā)的運(yùn)行單位。1.3進(jìn)程的狀態(tài)(1)執(zhí)行狀態(tài)(2)就緒狀態(tài)(3)等待狀態(tài)(4)停止?fàn)顟B(tài)(5)死鎖狀態(tài)圖2-1進(jìn)程的生命歷程圖2-2具有掛起狀態(tài)的進(jìn)程生命歷程1.4進(jìn)程控制塊圖2-3進(jìn)程的物理表示PCB包含了進(jìn)程的描述信息和控制信息，通常有如下項目：(1)標(biāo)識符(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用適當(dāng)方式組織起來。一般說來，大致有以下三種組織方式：

(1)線性表方式

(2)索引方式

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

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

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

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

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

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

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

一個進(jìn)程可借助于“建立”原語創(chuàng)建一個新進(jìn)程，前者為后者的父進(jìn)程，后者為前者的子進(jìn)程。建立新進(jìn)程的工作通常包括：從PCB集合中獲取一個空閑PCB；對該P(yáng)CB進(jìn)行初始化；為新進(jìn)程的數(shù)據(jù)集分配內(nèi)存空間并初始化；為新進(jìn)程的程序文本分配內(nèi)存空間并裝入該程序；將新進(jìn)程的PCB插入就緒隊列。在一些系統(tǒng)中(如UNIX)允許子進(jìn)程在被建立時可以直接繼承父進(jìn)程的某些特征和資源，例如優(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為新進(jìn)程的外部名；res為新進(jìn)程的初始資源，如終端、父進(jìn)程的打開文件表等；pri為新進(jìn)程的初始優(yōu)先數(shù)；fn為新進(jìn)程的執(zhí)行程序文本之文件名；args是fn的參數(shù)表。

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

一個進(jìn)程一旦被建立便處于就緒狀態(tài)，隨時等候被進(jìn)程調(diào)度選中并啟動執(zhí)行。一個進(jìn)程在正常運(yùn)行結(jié)束后，一般應(yīng)主動終止而進(jìn)入停止?fàn)顟B(tài)，同時向父進(jìn)程發(fā)一“完成”消息，等待父進(jìn)程撤銷它，這通過調(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將指定進(jìn)程移出所屬狀態(tài)隊列；過程findchild尋找指定進(jìn)程的子進(jìn)程，返回子進(jìn)程的內(nèi)部號；過程close關(guān)閉指定文件，若返回值t=true表示關(guān)閉成功，否則表示該文件為共享文件且正被其它進(jìn)程所使用；過程resrelease釋放除內(nèi)存之外的其它資源。本原語可遞歸調(diào)用，用以實現(xiàn)撤銷指定進(jìn)程的子孫進(jìn)程。3.2掛起與激活

掛起原語suspend和激活原語activate的調(diào)用參數(shù)均為進(jìn)程內(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ù)集復(fù)制到外存交換區(qū)并返回相應(yīng)的地址。進(jìn)程實體中的執(zhí)行程序并未被復(fù)制到交換區(qū)，因為執(zhí)行程序文件尚在外存并未被撤銷，但仍要回收它所占用的內(nèi)存空間(若它未被其它進(jìn)程共享)，這樣做的好處是減少了交換時間。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阻塞與喚醒

進(jìn)程從執(zhí)行態(tài)到等待態(tài)以及從等待態(tài)到就緒態(tài)的過渡分別是通過阻塞原語block和喚醒原語wakeup實現(xiàn)的。當(dāng)現(xiàn)行進(jìn)程需要等待某個事件時，可調(diào)用block原語使自己加入到該事件的等待隊列中，調(diào)用參數(shù)為等待隊列指針。操作系統(tǒng)為每類事件設(shè)置一個等待隊列，當(dāng)某個事件發(fā)生時，通過wakeup原語移出相應(yīng)等待隊列中的某個進(jìn)程，將其送入應(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進(jìn)程同步4.1同步概念

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

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

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

LDR1，countINCR1LDcount,R1

由于進(jìn)程A和B異步前進(jìn)，故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)的錯誤，變量count必須按臨界資源處理。

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

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

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

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

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

這是一種借助一條硬件指令TestandSet(簡記TS)來實現(xiàn)互斥的同步機(jī)構(gòu)。許多計算機(jī)中都提供了這種指令，在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è)置一個布爾變量lock(鎖)，其初值為falsc，當(dāng)lock值為false表示鎖打開，臨界資源未被使用，進(jìn)程可進(jìn)入臨界區(qū)；反之則表示鎖關(guān)閉，進(jìn)程不能進(jìn)入。于是用TS指令實現(xiàn)互斥的進(jì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操作荷蘭的著名計算機(jī)科學(xué)家Dijkstra把互斥的關(guān)鍵含義抽象成信號量(semaphore)概念，并引入在信號量上的P、V操作作為同步原語(P和V分別是荷蘭文的“等待”和“發(fā)信號”兩詞的首字母)。信號量是個被保護(hù)的量，只有P、V操作和信號量初始化操作才能訪問和改變它的值，Dijkstra把信號量s定義為一個非負(fù)整型量。把信號量s上的P操作P(s)定義為：若s>0，則s值減1，否則執(zhí)行進(jìn)程等待，直到其他進(jìn)程對s進(jìn)行V操作。把信號量s上的V操作V(s)定義為：s值加1，若有進(jìn)程在s上等待，則喚醒其中一個進(jìn)程。

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

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

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

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

利用信號量可方便地實現(xiàn)臨界區(qū)的互斥執(zhí)行。此時信號量是公用信號量，它的初值為1，每個進(jìn)程均可對它施行P、V操作。設(shè)mutex為互斥信號量，其初值為1，表示對應(yīng)的臨界資源R未被占用。對于每個想使用R的進(jìn)程，只需把它們的臨界區(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．合作進(jìn)程的同步利用信號量同樣可以方便地實現(xiàn)合作進(jìn)程之間的同步。方法是為某個事件設(shè)置一個信號量event,event.v的初值為0，表示該事件還未發(fā)生，當(dāng)一進(jìn)程需要等待event對應(yīng)的事件時執(zhí)行P(event)，如果此時event.v=0，則阻塞該進(jìn)程，將它掛入event的等待隊列；若event.v=1，則表示事件已發(fā)生，該進(jìn)程可繼續(xù)執(zhí)行。當(dāng)某進(jìn)程完成了event的事件時，立即執(zhí)行V(event)喚醒event等待隊列中的某個進(jìn)程。我們把信號量event稱為私用信號量，即只有需要等待event相應(yīng)事件發(fā)生的進(jìn)程或說需要其它某個進(jìn)程給予合作的進(jìn)程在event上執(zhí)行P操作，而完成event事件的進(jìn)程或說提供合作的進(jìn)程只在event上執(zhí)行V操作。3．生產(chǎn)者與消費(fèi)者關(guān)系圖2-6環(huán)形緩沖池

基于環(huán)形緩沖池的生產(chǎn)者與消費(fèi)者關(guān)系的形式描述，設(shè)：

(1)公用信號量mutex:初值為1，用于實現(xiàn)臨界區(qū)互斥；(2)生產(chǎn)者私用信號量empty:初值為n，指示空緩沖塊數(shù)目；(3)消費(fèi)者私用信號量full:初值為0，指示滿緩沖塊數(shù)目；

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

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

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個售票處，它們通過遠(yuǎn)程終端訪問設(shè)在公司總部的航空訂票系統(tǒng)，并要查詢或修改系統(tǒng)中記錄所有班機(jī)當(dāng)前訂票數(shù)的數(shù)據(jù)庫B。設(shè)Bi為某班機(jī)的當(dāng)前訂票數(shù)，P1和P2分別代表2個售票處的售票進(jìn)程，R1和R2為進(jìn)程執(zhí)行時使用的工作寄存器。由于售票進(jìn)程并發(fā)執(zhí)行，且各自訪問數(shù)據(jù)庫B的時間是隨機(jī)的，故有可能出現(xiàn)下面的訪問序列(假定Bi的當(dāng)前值為x)：P1:R1:=BiR1:=R1+1P2:R2:=BiR2:=R2+1Bi:=R2P1:Bi:=R1

可見，Bi的新值是X+1，而不是正確的X+2。這里的P1和P2均為寫者，顯然，對于寫者Bi為臨界資源，因此寫者應(yīng)該互斥。讀者進(jìn)程與寫者進(jìn)程的一般結(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í)行分散在各進(jìn)程中，這樣不便于系統(tǒng)對臨界資源的控制和管理，也很難發(fā)現(xiàn)和糾正分散在用戶程序中的對同步原語的錯誤使用等問題。為此，應(yīng)把分散的各同類臨界區(qū)集中起來。并為每個可共享資源設(shè)立一個專門的管程來統(tǒng)一管理各進(jìn)程對該資源的訪問。這樣既便于系統(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ù)施行特定操作的若干過程圍了起來。任一進(jìn)程要訪問某個共享資源，就必須通過相應(yīng)的管程才能進(jìn)入。為了實現(xiàn)對臨界資源的互斥訪問，管程每次只允許一個進(jìn)程進(jì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負(fù)責(zé)執(zhí)行將數(shù)據(jù)寫入某個緩沖塊的操作；過程get負(fù)責(zé)執(zhí)行從某個緩沖塊讀取數(shù)據(jù)的操作。empty和full被定義為兩個條件變量，對應(yīng)于緩沖池滿和緩沖池空條件等待隊列。任一進(jìn)程都必須通過調(diào)用管程ringbuffer來使用環(huán)形緩沖池，生產(chǎn)者進(jìn)程調(diào)用其中的put過程，消費(fèi)者進(jìn)程調(diào)用get過程§5進(jìn)程通訊5.1消息緩沖通訊

消息緩沖通訊技術(shù)是由Hansen首先提出的，其基本思想是：根據(jù)生產(chǎn)者與消費(fèi)者關(guān)系原理，利用內(nèi)存的公用消息緩沖池實現(xiàn)進(jì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進(jìn)程的消息隊列首指針，設(shè)置在PCB中。

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

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

(11)接收消息原語receive(a)進(jìn)程可調(diào)用本原語摘取消息隊列中的一則消息,調(diào)用參數(shù)a為接收者在自己的內(nèi)存工作區(qū)內(nèi)準(zhǔn)備復(fù)制消息的接收區(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兩個進(jìn)程共享一個pipe2.pipe操作的同步與互斥

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

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

從靜態(tài)觀點看，一個作業(yè)由三部分組成，即作業(yè)＝控制命令序列＋程序集＋數(shù)據(jù)集從系統(tǒng)管理角度，一個作業(yè)的主體是控制命令序列，不同的控制命令序列形成了不同的作業(yè)。多道程序系統(tǒng)支持同時運(yùn)行多個用戶的作業(yè)，每個用戶還可以建立多個作業(yè)，所謂系統(tǒng)的道數(shù)即同時運(yùn)行的作業(yè)個數(shù)。作業(yè)有兩種基本類型：脫機(jī)作業(yè)和聯(lián)機(jī)作業(yè)。脫機(jī)作業(yè)包括批處理作業(yè)和后臺作業(yè)，即在批處理環(huán)境下運(yùn)行的作業(yè)和以后臺方式運(yùn)行的作業(yè)。聯(lián)機(jī)作業(yè)包括終端作業(yè)及前臺作業(yè)，即在分時環(huán)境或交互環(huán)境下運(yùn)行的作業(yè)和以前臺方式運(yùn)行的作業(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è)的估計運(yùn)行時間．內(nèi)存需要量．外設(shè)需求．作業(yè)狀態(tài)．作業(yè)類型．鏈接字．其它7作業(yè)控制7.2作業(yè)的運(yùn)行

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

(2)調(diào)用記帳程序，核算作業(yè)的運(yùn)行費(fèi)用。

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

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

在分時環(huán)境下，用戶是以交互會話方式請求系統(tǒng)服務(wù)的，故作業(yè)的建立和運(yùn)行以及對作業(yè)的控制都與批處理作業(yè)略有差異。系統(tǒng)初啟時先建立系統(tǒng)總控進(jìn)程，再由它為每個終端建立一個終端管理進(jìn)程，這相當(dāng)于一個終端上的作業(yè)流控制進(jìn)程。第三章處理機(jī)調(diào)度§1調(diào)度級別§2調(diào)度的功能、時機(jī)及方式§3調(diào)度原則與評估標(biāo)準(zhǔn)§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)檫\(yùn)行狀態(tài)。一個作業(yè)一旦被高級

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

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

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

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

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

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

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

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

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

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

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

（３）平均等待時間進(jìn)程ｉ從進(jìn)入就緒隊列那一時刻ｔir到獲得ＣＰＵ的那一時刻ｔip所經(jīng)歷的時間稱為它的等待時間Ｗi，即