操作系统课件

第一章概論§1電腦系統的層次結構§2操作系統的資源管理觀點§3操作系統的服務觀點§4操作系統的特性§5操作系統的硬體基礎§6操作系統的裝入與初啟§1電腦系統的層次結構

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

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

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

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

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

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

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

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

３即時系統（Ｒｅａｌ-ｔｉｍｅＳｙｓｔｅｍ）

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

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

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

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

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

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

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

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

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

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

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

∥ＥＸＥＣＬＩＮＫＥＤＴ；執行連接程式∥ＥＸＥＣ；執行剛產生的可執行程式（數據）／*

／&；作業結束

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

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

脫機級介面與聯機級介面，二者並不是截然分開的，一些既支持批處理又支持分時處理的電腦系統同時提供這兩類服務介面，用戶可以使用ＪＣＬ將其作業交由系統批處理，也可以使用終端命令直接控制其作業的運行，而且在作業的一次運行中可轉換使用終端命令和ＪＣＬ,即可將交互作業（也稱前臺作業）轉為批處理作業（也稱後臺作業），反之亦然。§４操作系統的特性

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

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

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

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

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

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

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

操作系統進駐記憶體後，首先執行操作系統的初啟程序，它完成以下三項工作：（１）對操作系統的全局數據結構置初值；（２）為操作系統的某些程式建立進程，這些系統進程在操作系統的整個生存期間不被撤銷；（３）將ＣＰＵ控制轉交給操作系統的ＣＰＵ低級調度（進程調度）程式。第二章進程及作業管理§1進程概念§2系統內核§3進程控制

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

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

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

(1)線性表方式

(2)索引方式

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

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

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

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

裸機經內核擴充後構成了電腦系統的第一層“虛擬機”，所有的進程都在這個虛擬機上運行。該虛擬機有三個屬性：

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

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

一個進程可借助於“建立”原語創建一個新進程，前者為後者的父進程，後者為前者的子進程。建立新進程的工作通常包括：從PCB集合中獲取一個空閒PCB；對該PCB進行初始化；為新進程的數據集分配記憶體空間並初始化；為新進程的程式文本分配記憶體空間並裝入該程式；將新進程的PCB插入就緒佇列。在一些系統中(如UNIX)允許子進程在被建立時可以直接繼承父進程的某些特徵和資源，例如優先數、終端、可共用的打開檔等。建立原語可大致描述如下：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;

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

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

一個進程一旦被建立便處於就緒狀態，隨時等候被進程調度選中並啟動執行。一個進程在正常運行結束後，一般應主動終止而進入停止狀態，同時向父進程發一“完成”消息，等待父進程撤銷它，這通過調用“停止”原語實現。停止原語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將指定進程移出所屬狀態佇列；過程findchild尋找指定進程的子進程，返回子進程的內部號；過程close關閉指定檔，若返回值t=true表示關閉成功，否則表示該檔為共用檔且正被其他進程所使用；過程resrelease釋放除記憶體之外的其他資源。本原語可遞歸調用，用以實現撤銷指定進程的子孫進程。3.2掛起與啟動

掛起原語suspend和啟動原語activate的調用參數均為進程內部號。它們可描述如下：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;

其中，調用了換出過程swapout將數據集複製到外存交換區並返回相應的地址。進程實體中的執行程式並未被複製到交換區，因為執行程式檔尚在外存並未被撤銷，但仍要回收它所佔用的記憶體空間(若它未被其他進程共用)，這樣做的好處是減少了交換時間。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阻塞與喚醒

進程從執行態到等待態以及從等待態到就緒態的過渡分別是通過阻塞原語block和喚醒原語wakeup實現的。當現行進程需要等待某個事件時，可調用block原語使自己加入到該事件的等待佇列中，調用參數為等待佇列指針。操作系統為每類事件設置一個等待佇列，當某個事件發生時，通過wakeup原語移出相應等待佇列中的某個進程，將其送入應緒佇列，調用參數也是等待佇列指針，下麵是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同步概念

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

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

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

LDR1，countINCR1LDcount,R1

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

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

系統的同步機構對解決臨界區互斥問題應遵循下述準則：(1)當無一進程處於臨界區內時，若有一進程要求進入臨界區，應讓其立即進入-有空讓進；

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

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

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

(5)處於等待進入臨界區的進程應放棄佔用CPU-讓權等待。4.3同步機構1．測試與設置(TestandSet)

這是一種借助一條硬體指令TestandSet(簡記TS)來實現互斥的同步機構。許多電腦中都提供了這種指令，在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指令的執行是不可分割的，利用TS指令可以簡單而有效地實現互斥。其方法是為每個臨界資源設置一個布爾變數lock(鎖)，其初值為falsc，當lock值為false表示鎖打開，臨界資源未被使用，進程可進入臨界區；反之則表示鎖關閉，進程不能進入。於是用TS指令實現互斥的進程的程式結構為：varkey:blooean;begin…key:=true;whilekeydoTS(lock,key); （１′）

CS(臨界區)；

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

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

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

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

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

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

當一進程在值不大於0的信號量s上執行P操作時，將在迴圈語句while上陷入忙等待，直到其他進程在該信號量s上執行V操作後，解除它的等待。不難看出這種形式的P、V操作完全可用硬體指令來實現。(2)讓權等待方式的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

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

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

基於環形緩衝池的生產者與消費者關係的形式描述，設：

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

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

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

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．讀者與寫者關係

設某航空公司有2個售票處，它們通過遠程終端訪問設在公司總部的航空訂票系統，並要查詢或修改系統中記錄所有班機當前訂票數的資料庫B。設Bi為某班機的當前訂票數，P1和P2分別代表2個售票處的售票進程，R1和R2為進程執行時使用的工作寄存器。由於售票進程併發執行，且各自訪問資料庫B的時間是隨機的，故有可能出現下麵的訪問序列(假定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為臨界資源，因此寫者應該互斥。讀者進程與寫者進程的一般結構：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管程概念

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

(1)局部於該管程的共用數據，這些數據表示了相應資源的狀態；

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

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

cedure/function-entry-name的調用語句，都將自動保證其按如下方式執行：

P(mutex);

執行相應的過程或函數

V(mutex);其中，mutex是關於相應管程的互斥信號量，初值為1。管理環形緩衝池的管程結構。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負責執行將數據寫入某個緩衝塊的操作；過程get負責執行從某個緩衝塊讀取數據的操作。empty和full被定義為兩個條件變數，對應於緩衝池滿和緩沖池空條件等待佇列。任一進程都必須通過調用管程ringbuffer來使用環形緩衝池，生產者進程調用其中的put過程，消費者進程調用get過程§5進程通訊5.1消息緩衝通訊

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

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

sender:消息發送者名

size:消息長度

text:消息正文

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

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

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

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

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

(11)接收消息原語receive(a)進程可調用本原語摘取消息佇列中的一則消息,調用參數a為接收者在自己的記憶體工作區內準備複製消息的接收區地址。圖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檔進行讀寫操作過程中要對發送進程和接收進程實施正確的同步和互斥，以確保通訊的正確性。接收進程讀pipe時，若發現pipe為空，則進入等待狀態。一旦有發送進程對該pipe執行寫操作時便喚醒等待進程。不論是讀或寫pipe時，都要考慮資訊傳送的另一方是否存在。在讀pipe時，若發現無資訊可讀，則在進入等待態之前先檢查pipe的寫入端是否已關閉，若已關閉，則不必等待。在寫pipe時也要先檢查讀出端是否已關閉，若已關閉，則按出錯處理。進程在關閉pipe檔的寫入或讀出端時，應喚醒等待寫或讀該pipe檔的進程。為了防止兩個進程同時讀、寫一個pipe，須為每個pipe設置互斥標誌。pipe通訊機構中的同步與互斥都由系統自動進行，對用戶是透明的。pipe通訊的實質是利用外存來進行數據通訊，故具有傳送數據量大的優點，但通訊速度較慢。§6作業概念

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

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

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

(2)調用記帳程式，核算作業的運行費用。

(3)輸出作業記帳收費資訊以及作業正常或異常終止資訊。

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

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

§2調度的功能、時機及方式

§3調度原則與評估標準§4調度演算法§5調度的實現§１調度級別

１.高級調度

即作業調度。它決定允許哪些作業可參與競爭ＣＰＵ和其他系統資源，從狀態觀點，就是將一個或一批作業從後備狀態變為運行狀態。一個作業一旦被高級

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

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

３低級調度

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

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

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

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

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

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

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

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

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

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

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

通常，用Ｔ來衡量不同調度演算法對同一作業流或同一進程集的調度性能，用Ｗ來衡量不同進程調度演算法對同一進程集的調度性能，而用Ｔ′來衡量同一調度演算法對不同作業流或不同進程集的調度性能。§４調度算法４.１先來先服務ＦＣＦＳ

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

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

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

ＦＣＦＳ演