操作系统原理及应用课件

操作系統原理及應用(Linux)1.1操作系統的地位電腦系統是分層次的，最低層是未配置任何軟體的硬體裸機，硬體之上是軟體，軟體又分為若干層次，最低層是操作系統。操作系統是覆蓋在裸機之上的第一層軟體，它直接控制、管理各種硬體資源。所以操作系統是整個電腦系統的控制管理中心。21.2操作系統的功能操作系統是電腦系統中具有一定功能的軟體系統。操作系統的目標是方便用戶使用電腦系統和提高電腦系統資源利用率。31.2.1提供人機介面1．作業控制級介面作業：用戶上機所作的一系列順序相關的工作。一道作業由若干順序相關的作業步構成。例如，我們上機編程要經歷如下步驟：4

5編輯編譯連接運行根源程式目標程式可執行程式以上作業的工作流程要由用戶按自己的需求進行控制，因此要提供給用戶控制作業工作流程的手段，這是由操作系統提供的，稱為作業級介面。作業級介面由一組用戶可直接使用控制作業運行的命令和命令解釋器構成。該介面又可進一步分為聯機用戶介面和脫機用戶介面。6（1）聯機用戶介面由一組鍵盤字元命令（或滑鼠命令）和命令解釋器組成，使用戶可以聯機交互方式使用電腦。用戶每次鍵入一個合法命令（解釋器能執行的命令），啟動一個作業步；一個作業步運行完畢後，再鍵入下一個命令名，啟動下一個作業步。在一個作業步結束後，若發現錯誤，可以由用戶修正錯誤，然後重新啟動該作業步。用戶可根據作業運行情況隨時進行作業步的調整。7（2）脫機用戶介面操作命令的形式為作業控制語言，用戶以脫機批處理方式使用電腦。用戶對作業流程的控制意圖是利用作業控制語言書寫成一份作業說明書來表達的。上機時，用戶將作業控制說明書交給系統，系統逐條解釋執行說明書中的命令。在這種方式下，用戶一旦提交了作業，作業流程就由操作系統根據作業控制說明書自動控制，用戶無法干預該作業的運行。因此，用戶必須事先設計好作業流程，還要預測作業運行過程中可能出現的錯誤，並給出發生錯誤時的處理方法。82．程式級介面操作系統提供的程式級介面由一組系統功能調用命令以及完成這些命令的程式模組組成。為方便用戶編程，提高編程效率，規範編程，操作系統提供了完成某些通用功能的程式提供用戶在開發應用程式時調用。不同的操作系統提供了不同的系統功能調用以及調用方式。如DOS的系統功能調用主要是進行硬體驅動，以軟中斷INT21H的方式提供。9Windows中的系統功能調用要比DOS豐富，且層次要高，不只局限於硬體驅動，以用戶可在編程語言中使用的應用編程介面函數的方式提供，稱為API——ApplicationProgrammingInterface。使用Windows的API函數，可以提高編程效率，並規範Windows環境下的編程，如可開發具有統一風格的應用程式窗口介面，這會使得軟體用戶能很快熟悉該軟體的窗口介面而不必重新學習。101.2.2管理電腦資源電腦系統中的資源包括硬體資源和軟體資源。硬體資源有：處理機、記憶體、外部設備；軟體資源有：程式和數據。111.處理機管理處理機的任務是運行程式，我們把程式在某個數據對象上的一次運行過程稱為進程，處理機管理又稱為進程管理。在單處理機系統中，程式有兩種運行方式：單道程式順序執行，多道程序併發執行。12單道程式順序執行：要執行的多個程式按一定次序依次執行，一個程式運行完畢才能運行下一個程式，即在一個程式運行期間不插入運行其他程式。這種運行方式的優點是實現簡單，不需要在多個進程之間進行轉換；缺點是資源利用率低。多道程序併發執行：在內存中同時存放多道程序，按一定策略調度多道程序交叉運行，形成“微觀上串行、宏觀上並行”的情況。這使得處理機和設備可以並行工作，當某個進程在進行輸入輸出操作時，可以同時有另一個進程在處理機上進行計算。

132.存儲管理電腦系統採用了馮·諾依曼提出的存儲程式原理，即把要運行的程式先一次性存放在記憶體中，然後由處理機自動從記憶體中依次取出程式指令運行，處理機的運行過程就是不斷地取指令、執行指令循環往復的過程，每次取一條指令，執行一條指令。則記憶體是電腦系統中的重要資源與處理機一起稱為電腦系統中的主機。因此，程式的運行機構不只是處理機，而是由處理機和記憶體構成的主機。14在多道程序環境中，要在內存中同時存放多道程序，則必須對內存進行合理管理以保證程式的順利運行，並提高記憶體的利用率。操作系統提供如下存儲管理功能：（1）記憶體分配（2）地址轉換（3）記憶體保護（4）記憶體擴充153.設備管理設備管理的任務是：接受用戶程式提出的I/O請求，為用戶程式分配I/O設備；使CPU和I/O設備並行操作，提高CPU和I/O設備的利用率；提高I/O速度；方便用戶程式使用I/O設備。為完成以上任務，操作系統的設備管理子系統應該具有設備分配、緩衝管理、設備驅動、設備無關性等功能。

16設備無關性又稱設備獨立性。即用戶編寫的應用程式與實際使用的物理設備無關。用戶編寫的應用程式中不直接指定使用哪臺具體的物理設備，而是使用操作系統提供的邏輯設備，然後由操作系統把用戶程式中使用的邏輯設備映射到具體的物理設備，實施具體的I/O操作。這樣做的一個明顯好處是用戶應用進程的運行不取決於某臺具體物理設備的狀態，而由操作系統為其分配一臺合適的設備完成I/O操作。這樣會避免出現有設備可用但進程卻無法運行的情況。174.檔管理電腦系統中的軟體資源（程式和數據的集合）不是一次性用品，用了一次後就再也不用了，而是要反復利用的，因此要永久保存（相對於記憶體的暫時存儲而言）起來，如銀行中的存貸款數據、學校的學籍管理軟體和學籍數據等等。軟體資源以檔的形式存放在外部存儲介質中，供用戶反復使用。18操作系統中對檔進行管理的子系統稱為檔系統，檔系統的任務是：為用戶提供一種簡便的、統一的存取和管理檔的方法，對用戶而言，按名存取是一種簡便的存取檔的手段；實現檔的共用；維護檔的秘密和安全。19檔管理具體有如下功能：（1）檔存儲空間的管理（2）目錄管理（3）檔操作（4）檔的存取許可權控制根據以上所述操作系統的功能，我們可以給操作系統下一個描述性的定義：操作系統是一個軟體系統，它控制和管理電腦系統內各種硬體和軟體資源，提供用戶與電腦系統之間的介面。201.3操作系統的發展過程1.3.1推動操作系統發展的主要動力1.不斷提高電腦資源利用率的需要2.方便用戶3.器件的不斷更新換代4.電腦體系結構的不斷發展211.3.2無操作系統的電腦系統此時，人們採用手工方式使用電腦，用戶一個挨一個地輪流使用電腦。每個用戶的工作過程大致是：先把程式紙帶（或卡片）裝到輸入機上，然後啟動輸入機把程式和數據輸入電腦記憶體，接著利用控制臺開關啟動程式開始執行。計算結束，用戶取走列印出來的結果，並卸下紙帶.22在這個過程中，需要人工裝卸紙帶、人工控制程式運行。手工操作速度相對於電腦的運行速度而言是很慢的，因此在使用電腦完成某一工作的整個過程中，手工操作時間占了很大的比例，而電腦運行時間所占比例較小，這就形成了明顯的人機矛盾，致使電腦資源利用率很低，從而使電腦工作效率很低。在早期電腦運行速度較慢的時候，這種狀況還是可以容忍的。231.3.3單道批處理系統單道批處理系統在當時稱為監督程式，是操作系統的雛形。監督程式常駐記憶體，在它的控制下，實現了作業的自動過渡，從而去掉了原先的作業過渡時的手工操作。此時，出現了組合語言、高級語言編程工具，每一種語言編譯程序（如組合語言或某種高級語言的編譯程序）、實用程式（如連接程式）都作為監督程式的子例程，當需要用到它們時由監督程式進行調用。24早期的批處理分為聯機批處理和脫機批處理兩種。1.聯機批處理操作員把一批作業裝到輸入設備上（紙帶輸入機/卡片閱讀機），然後由監督程式控制把這批作業輸入到磁帶上，之後在監督程式的控制下，使這批作業一個接一個的連續執行，直至磁帶上的所有作業運行完畢。2526輸入帶主機輸出帶輸入帶讀卡機印表機輸出帶衛星機卡片1.3.4多道批處理系統為了進一步提高資源利用率，從而最終提高系統吞吐量（系統在單位時間內完成的總工作量），在60年代中期引入了多道程序併發執行技術，從而形成了多道批處理系統。多道程序併發執行的基本思想是：在內存中同時存放多道程序，在操作系統的控制下交替執行。在多道批處理系統中，用戶提交的作業都先存放在外存中並排成一個佇列，稱為後備佇列，然後由作業調度程式按一定的策略從後備佇列中選擇若干作業調入記憶體，使它們併發運行，從而共用系統中的各種資源，提高資源利用率，最終提高系統吞吐量。27多道程序併發執行系統的特徵：（1）多道性（2）調度性（3）宏觀上並行，微觀上串行（4）非同步性281.3.5分時系統在分時系統中，雖然若干用戶通過各自的終端共用一臺主機，但是在操作系統的管理下，每個用戶都感覺自己在獨佔一臺主機。分時系統採用的策略是：基於主機的高速運行，分時為終端用戶服務。即主機按一定次序輪流為各終端用戶服務，每個用戶一次僅使用主機很短的一段時間（稱為時間片，毫秒級），在分得的時間片內若用戶沒有完成工作則暫時中斷，將處理機分配給下一個用戶。雖然在一個用戶使用主機時其他用戶處於等待狀態，但是等待的時間很短，用戶感覺不到，從而每個用戶的各次請求都能得到快速回應，給每個用戶的印象是：他獨佔一臺電腦。29分時系統具有以下特徵：（1）多個用戶同時聯機操作（2）各用戶獨立（3）交互性301.3.6即時系統1.即時控制當把電腦用於生產過程的控制，以形成以電腦為中心的控制系統時，系統要求能即時採集現場數據，並對所採集的數據進行及時處理，進而自動地控制相應的執行機構，使某些（個）參數（如溫度、壓力、方位等）能按預定的規律變化。類似地，也可將電腦用於武器的控制，如火炮自動控制系統、飛機的自動駕駛系統，以及導彈的制導系統等。通常把要求進行即時控制的系統稱為即時控制系統。312.即時資訊處理通常，我們把要求對資訊進行即時處理的系統，稱為即時資訊處理系統。該系統由一臺或多臺主機通過通信線路連接成百上千個遠程終端，電腦接收從遠程終端發來的服務請求，對數據進行檢索和處理，並及時將結果回饋給用戶。典型的即時資訊處理系統有：飛機訂票系統、情報檢索即時系統的特徵：（1）及時性（2）可靠性321.3.7微機操作系統1.單用戶單任務操作系統

單用戶單任務是指，只允許一個用戶上機，用戶要運行的多個程式要按一定次序依次執行，不能交替執行。這是最簡單的微機操作系統，代表性產品是：CP/M和MS-DOS。332.單用戶多任務操作系統單用戶多任務是指，只允許一個用戶上機，但是可以併發執行多道程序，從而充分利用系統資源，滿足用戶同時執行多個任務的需求，如一邊打字一邊聽音樂。代表性產品是OS/2和Windows。343.多用戶多任務操作系統微機是面向個人用戶而開發的，所以一般由單個用戶使用，配置單用戶操作系統。但是這並不意味著微機不可由多個用戶同時聯機使用，特別是現在的微機與小型機的差距已經很小，只要在微機上配置多用戶操作系統就可以使微機同時為多個用戶服務。具有代表性的產品是UNIX、LINUX。351.3.8網路操作系統為了實現電腦之間的數據通信和資源共用，把分佈在各處的電腦通過通信線路連接在一起，構成一個系統，這就是電腦網絡。電腦網絡要有一個網路操作系統對整個網路實施管理，並為用戶提供統一的、方便的網路介面。網路操作系統一般建立在各個主機的本地操作系統基礎之上，其功能是：實現網路通信、資源共用和保護，提供網路服務和網路介面。361.3.9分佈式操作系統大量的實際應用要求一個完整的一體化的系統。在分佈式系統中，有一個全局的分佈式操作系統，它負責整個系統的資源分配和調度、任務劃分、資訊傳輸、控制協調等工作，並為用戶提供一個統一的介面。用戶通過這一介面實現所需的操作和使用系統資源，至於操作是在哪一臺電腦上資源是系統的事，用戶不必知道，即系統對用戶是透明的。371.4操作系統的特性併發性共用性非同步性虛擬性其中，併發性是操作系統的最基本的特徵。381.5操作系統的體系結構

一般而言，操作系統有兩種結構：層次結構、微內核結構。1.5.1層次結構層次結構操作系統的設計思想是：按照操作系統各模組的功能和相互依存關係，把系統中的模組分為若干層次，其中任一層（除底層模組）都建立在它下麵一層的基礎上，每一層僅使用其下層所提供的服務。391.5.2微內核結構微內核結構是20世紀90年代發展起來的。其基本思想是：把操作系統中的基本功能模組組織為微內核，其他功能模組儘量放到核外，通過調用微內核來實現。微內核結構是對傳統內核的提煉，它有如下優點：1.簡化內核代碼維護工作2.建構靈活3.安全性高4.方便移植401.6LINUX介紹Linux現在是個人電腦和工作站上的UNIX類操作系統。按照層次結構的觀點，在同一種硬體平臺上面，Linux可以提供和UNIX相同的服務，即相同的用戶級和程式員級介面。同時，Linux絕不是簡化的UNIX。相反，Linux是強有力和具有創新意義的UNIX操作系統。它不僅繼承了UNIX的特徵，而且在許多方面超過了UNIX。作為UNIX類操作系統，它具有下列基本特徵：41（1）是真正的多用戶、多任務操作系統；（2）是符合POSIX標準的系統；（3）提供具有內置安全措施的分層的檔系統；（4）提供shell命令解釋程式和編程語言；（5）提供強大的管理功能，包括遠程管理功能；（6）具有內核的編程介面；（7）具有圖形用戶介面；（8）具有大量有用的實用程式和通信、聯網工具；（9）具有面向螢幕的編緝軟體。422.1進程的基本概念

2.1.1程式的順序執行及其特徵1．程式的順序執行

程式是人們要電腦完成的一些指令序列，是一個按嚴格次序、順序執行的操作序列，是一個靜態的概念。我們把一個具有獨立功能的程式獨佔處理機，直到最後結束的過程稱為程式的順序執行。2．程式順序執行時的特徵（1）順序性。（2）封閉性。（3）可再現性。432.1.2程式的併發執行及其特徵1．併發執行的概念

所謂程式的併發性，是指多道程序在同一時間間隔內同時發生。程式的併發執行可總結為：一組在邏輯上互相獨立的程式或程式段在執行過程中，其執行時間在客觀上互相重疊，即一個程式段的執行尚未結束，另一個程式段的執行已經開始的一種執行方式。442．程式併發執行時的特徵（1）間斷性程式在併發執行時，由於它們共用系統資源，以及為完成同一項任務而相互合作，致使這些併發執行的程式之間，形成了相互制約的關係。相互制約將導致併發程式具有“執行——暫停——執行”這種間斷性的活動規律。（2）失去封閉性某程式在執行時，必然會受到其他程式的影響。（3）不可再現性在併發環境下，同一個程式執行多次，執行的過程可能不同。用程式作為描述其執行過程以及共用資源的基本單位是不合適的。因此引入了進程作為描述程式的執行過程、共用資源的基本單位。452.1.3進程的定義與特徵1．進程的定義人們對進程下過許多定義。現列舉其中的幾種：（1）進程是程式的一次執行。（2）進程是可以和別的進程併發執行的計算。（3）進程就是一個程式在給定活動空間和初始條件下，在一個處理機上的執行過程。（4）進程是程式在一個數據集合上的運行過程，它是系統進行資源分配和調度的一個獨立單位（5）進程是動態的，有生命週期的活動。內核可以創建一個進程，最終將由內核終止該進程使其消亡。46進程和程式之間的關係

進程和程式是兩個完全不同的概念，但又有密切的聯繫。它們之間的主要區別是：（1）程式是靜態的概念，；而進程則是程式的一次執行過程。它是動態的概念。（2）進程是一個能獨立運行的單位，能與其它進程併發執行；而程式是不能作為一個獨立運行的單位而併發執行的。（3）程式和進程無一一對應的關係。（4）各個進程在併發執行過程中會產生相互制約關係，而程式本身是靜態的，不存在這種非同步特徵。472．進程的特徵從進程與程式的區別可以看出，進程具有如下特徵：（1）動態性動態性是進程最基本的特性。進程由創建而產生，由調度而執行，因得不到資源而暫停執行，以及因撤銷而消亡。（2）併發性這是指多個進程實體，同存於記憶體中，能在一段時間段內同時執行。併發性是進程的重要特徵，同時也是操作系統的重要特徵。提高併發性，可以提高系統的效率。（3）獨立性進程是一個能獨立運行的基本單位，同時也是系統中獨立獲得資源和獨立調度的基本單位。（4）非同步性這是指進程按各自獨立的、不可預知的速度向前推進；或者說，進程按非同步方式運行。（5）結構特徵從結構上看，進程實體是由程式段、數據段及進程控制塊三部分組成，也稱這三部分為進程映像。482.1.4進程的基本狀態及轉換1．進程的三個基本狀態進程通常至少有三種基本狀態：（1）就緒狀態（ready）進程運行所需的外部條件滿足，但因為其他進程已佔用CPU，所以暫時不能運行。（2）執行狀態(running)

外部條件滿足，進程已獲得CPU，其程式正在執行。在單處理機系統中，只有一個進程處於執行狀態。（3）阻塞狀態(blocked)

進程因等待某種事件發生，而暫時不能運行的狀態，稱為阻塞狀態，也稱為等待狀態。系統中處於這種狀態的進程可能有多個，通常將它們排成一個佇列，也有的系統則根據阻塞原因的不同將這些進程排成多個佇列。492．進程狀態的轉換

對於一個系統中處於就緒狀態的進程，在調度程式為之分配了處理機之後，該進程便可執行，相應地，它由就緒態轉變為執行狀態。正在執行的進程也稱為當前進程，如果因分配給它的時間片已用完而被暫停執行時，該進程便由執行狀態又回到就緒狀態；一個處在執行狀態的進程，如果因發生某事件而使進程的執行受阻，使之無法繼續執行，該進程將由執行狀態轉變為阻塞狀態。一個處於阻塞狀態的進程，當它所需的外部事件滿足，它應由阻塞狀態變為就緒狀態。50程執行完成或撤銷阻塞狀態就緒狀態調度用片間時進程創建進等待某事件發生如I/O請求外部事件發生圖2-1進程的基本狀態及轉換圖完513．引入掛起狀態時的進程狀態

所謂掛起狀態，實際上就是一種靜止的狀態。一個進程被掛起後，不管它是否在就緒狀態，系統都不分配給它處理機。在引入掛起狀態後，進程之間的狀態轉換除了四種基本狀態轉換以外，又增加了以下幾種：（1）活動就緒——靜止就緒。（2）活動阻塞——靜止阻塞。（3）靜止就緒——活動就緒。（4）靜止阻塞——活動阻塞。52執行外部事件滿足外掛起啟動掛起掛啟動活動就緒靜止就緒活動阻塞靜止阻塞調度圖2-2具有掛起狀態的進程狀態轉換等部事件外待起部條件滿足完成或撤銷532.1.5Linux進程的狀態

Linux系統的一個任務總體上有以下幾種狀態：（1）運行狀態（running）該狀態對應state取值為TASK_RUNNING。（2）等待狀態（waiting）（3）中斷處理狀態（interruptroutine）此狀態對應state取值TASK_RUNNING。（4）系統調用期間（systemcall）此狀態對應state取值TASK_RUNNING。（5）從系統調用返回（returnfromsystemcall）54（6）就緒態（ready）

處於此狀態的進程正在競爭處理機，但此刻處理機正在為另一個進程服務。此狀態對應state取值TASK_RUNNING。

Linux系統內核在進程控制塊中用state成員描述進程當前的狀態，並明確定義了5種進程狀態。它們分別是：（1）TASK-RUNNING狀態，Linux系統中的運行狀態實際包含了上述基本狀態中的執行和就緒兩種狀態。（2）TASK-INTERRUPTIBLE狀態，可中斷的等待態。進程正在等待某些事件。（3）TASK-UNINTERRUPTIBLE狀態，等待態，不可中斷。（4）TASK-ZOMBIE狀態，僵死態。（5）TASK-STOPPED狀態，暫停態。55

Linux任務狀態轉換圖

運行態從系統調用返回中斷例程系統調用等待就緒調度中斷用戶態系統態圖2-3Linux任務狀態轉換圖2.2進程的描述

進程實體通常是由程式、數據集合和PCB這三部分構成，也稱為“進程映象”。

PCB程式部分數據集合57圖2-4進程的一般組成模型2.2.1進程控制塊PCB

PCB集中反映一個進程的動態特徵，當系統創建了一個新進程時，就為它建立一個PCB；當進程終止後，系統回收其PCB，該進程在系統中就不存在了。所以，PCB是進程存在的惟一標誌。可以按照功能將PCB分成四個組成部分：進程識別字、處理機狀態、進程調度資訊、進程控制資訊。581．進程識別字進程識別字用於惟一地標識一個進程。一個進程通常有兩種識別字：（1）進程內部識別字。（2）進程外部識別字。2．處理機狀態：由各種寄存器中的內容組成。3．進程調度資訊（1）進程狀態。（2）進程優先順序。（3）進程調度所需要的其他資訊。（4）事件，或阻塞原因。4．進程控制資訊，包括：（1）程式和數據的地址；（2）進程同步和通信機制；（3）資源清單；（4）鏈接指針。592.2.2進程控制塊的組織方式各進程的PCB有如下幾種組織方式：線性方式、鏈接方式和索引方式。1．線性方式將各進程的PCB依次放入一個表中，結構如下圖所示。PCB1PCB2PCB3……PCBn-1PCBn60圖2-5PCB的線性組織方式2．鏈接方式

鏈接方式是經常採用的方式。其原理是：按照進程的不同狀態分別將其放在不同的佇列。Linux操作系統就是應用這種進程控制塊組織方式。運行佇列指針就緒佇列指針PCBPCBPCB0阻塞佇列1指針阻塞佇列2指針PCB0PCBPCBPCB0PCBPCBPCB0圖2-6PCB鏈接佇列示意圖613．索引方式系統根據所有進程的狀態建立幾張索引表。阻塞索引表就緒索引表執行指針就緒表指針阻塞表指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7圖2-7PCB索引結構示意圖622.2.3Linux進程的PCBLinux系統中的進程稱為任務。該系統的進程控制塊PCB用一個稱為task-struct的結構體來描述，Linux系統PCB包含以下資訊：1．進程描述資訊（1）進程標識號（pid，processidentifier）（2）用戶和組標識（userandgroupidentifier）（3）連接資訊（Links）2．進程控制資訊（1）進程當前狀態（2）調度資訊（3）記時資訊（4）通信資訊63Linux支持典型的UNIX進程間通信機制——信號、管道，也支持SystemⅤ通信機制——共用記憶體、信號量和消息佇列。3．進程資源資訊記錄了與該進程有關的記憶體的各種地址和資料、檔系統以及打開檔的資訊等等。4．CPU現場資訊642.3進程控制

所謂進程控制，就是系統使用一引起具有特定功能的程式段來創建、撤銷進程以及完成進程各狀態間的轉換，從而達到多進程高效率併發執行和協調、實現資源共用的目的。原語：把系統態下執行的某些具有特定功能並且不可被中斷的程式段稱為原語。原語的特點是：系統程式、不可被中斷。系統在創建、撤銷一個進程以及要改變進程的狀態時，都要調用相應的程式段來完成這些功能。用於進程控制的原語有：創建原語、撤銷原語、阻塞原語、喚醒原語等。652.3.1進程的創建與終止1．進程的創建導致進程創建的事件有：用戶登錄、作業調度、為用戶提供服務等。創建原語Creat()，通過下述步驟創建一個進程。（1）申請空白PCB。（2）為新進程分配資源。（3）初始化進程控制塊。（4）將新建進程插入就緒態佇列。2．進程的終止過程在進程中，操作系統調用進程終止原語，終止本進程。過程如下：（1）根據被終止進程的識別字，從PCB佇列中檢索出該進程的PCB，從中讀出該進程的狀態。。（2）若被終止進程正處於執行狀態，應立即終止該進程的執行，該進程被終止後應重新進程調度。（3）檢查該進程有無子孫進程，若有，則應將其所有子孫進程終止。（4）釋放終止的進程所佔有的資源，將其歸還它的父進程或者系統。（5）將被終止的進程從它的PCB佇列中移出。663．進程阻塞與進程喚醒

進程狀態的轉換需要通過進程之間的同步或通信機構來實現，也可直接使用“阻塞原語”和“喚醒原語”來實現。（1）進程的阻塞當一個進程所等待的某一事件尚未發生時，該進程調用阻塞原語block()將自己阻塞，轉換為等待狀態。（2）進程的喚醒處於等待狀態的進程，只有當該進程所等待的外部事件發生時，才由發生該事件的進程調用喚醒原語wakeup()將它喚醒。672.3.2幾個相關的Linux系統調用

在Linux系統中，系統向用戶提供了一些對進程進行控制的系統調用。常用的有：1．fork()系統調用

Linux利用fork()系統調用創建一個新進程。2．Exec系統調用利用exec系統調用執行另一個程式。3．exit()系統調用父進程在創建子進程時，應在進程的末尾寫一條exit，使子進程自我終止。4．wait系統調用將調用進程掛起，直至其子進程因暫停或終止而發來軟中斷信號為止。682.3.3進程的阻塞與喚醒

實現進程的執行狀態到等待狀態，又由等待狀態到就緒狀態轉換的兩種原語，分別為阻塞原語與喚醒原語。入口保存該進程的CPU現場字置該進程的狀態阻塞進程PCB進入等待佇列轉進程調度入口從等待佇列取被喚醒進程將被喚醒進程置為就緒態被喚醒進程插入就緒佇列轉進程調度或返回圖2-8阻塞原語的實現圖2-9喚醒原語的實現692.4進程的同步與互斥2.4.1臨界資源的概念1．臨界資源

兩個或兩個以上的進程不能同時使用的資源為臨界資源。臨界資源可能是一些獨佔設備，如印表機、磁帶機等；也可能是一些共用變數、表格、鏈表等。702．臨界區

每個進程中訪問臨界資源的那段代碼稱為臨界區。在臨界區前面增加一段用於進行檢查的代碼，把這段代碼稱為進入區；相應地，在臨界區後面再加一段用於退出臨界區的代碼，稱為退出區。進程中除去上述進入區和退出區，其他部分的代碼，稱為剩餘區。這樣，可將一個訪問臨界資源的進程描述如下：repeat

進入區；臨界區；退出區；剩餘區；untilfalse;712.4.2進程的互斥與同步1．同步與互斥的概念所謂進程互斥，是指多個進程不能同時使用同一個臨界資源CR。即兩個或兩個以上的進程必須互斥地使用臨界資源，或不能同時進入臨界區CS。兩個邏輯上完全獨立、毫無關係的進程，由於競爭同一個資源而相互制約，就稱為進程的互斥。所謂進程同步，是指有協作關係的進程之間，要不斷地調整它們之間的相對速度或執行過程，以保證臨界資源的合理利用和進程的順利執行。實現進程同步的機制稱為進程同步機制。2．同步機制應遵循的規則所有同步機制都應遵循下列準則：（1）空閒讓進。（2）忙則等待。（3）有限等待。（4）讓權等待。722.4.3鎖機制

實現互斥的一種軟體是採用鎖機制，即提供一對上鎖（Lock）和開鎖（UnLock）原語，以及一個鎖變數w（或者是鎖位１個bit）。加鎖及解鎖原語可描述如下：加鎖原語：

Lockw：

L：ifw=1thengotoLElsew:=1開鎖原語：UnLockw：

w：=0;732.4.4信號量機制

申請和釋放臨界資源的兩個原語操作：wait操作和signal操作，有時也稱為Ｐ操作和Ｖ操作。信號量（Semaphore），也叫做信號燈，它是在信號量同步機制中用於實現進程的同步和互斥的有效數據結構。我們可以為每類資源設置一個信號量。它有多種類型的數據結構，即：整型信號量、記錄型信號量、ＡＮＤ型信號量及信號量集等。741．整型信號量

整型信號量的數值表示當前系統中可用的該類臨界資源的數量。如設置整型信號量s，則s的值意義為：s>0，則s的值表示系統中空閑的該類臨界資源的個數；s=0，則表示系統中該類臨界資源剛好全部被佔用，而且沒有進程在等待該臨界資源；s<0，則s的絕對值表示系統中的進程等待該類臨界資源的個數；752．記錄型信號量

記錄型信號量的數據結構由兩部分構成。例如：定義記錄型信號量Ｓ，則：s的值表示系統中可用的該類臨界資源的數量，而Ｌ為進程鏈表指針，指向等待該類資源的PCB佇列。設變數Ｓ為記錄型信號量，則wait（Ｓ）操作和signal（Ｓ）操作的流程如下圖所示：76Wati(S)是Wati(S)s=s-1申請到資源本進程繼續本進程入阻塞佇列s≥0否轉進程調度圖2-10Wait操作原語流是signal(S)s=s+1喚醒一阻塞態進程s≤0否圖2-11signal操作原語流釋放該類資源本進程繼續77申請臨界資源的原語wait操作可描述為：procedurewait(S)

varS:semaphore;

begin

s:=s-1;

ifs≥0then本進程繼續；else{將本進程放入阻塞態佇列；轉進程調度;}

end

釋放臨界資源的原語signal操作可描述為：

proceduresignal(S)

varS:semaphore;

begin

s:=s+1;

ifs≤0then喚醒指針L所指的阻塞態進程；

end

783．ＡＮＤ型信號量

ＡＮＤ同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完成後再一起釋放。只要有一個資源尚未能分配給進程，其他所有可能分配的資源，也不能分配給它。也稱為ＡＮＤ同步。AND型信號量集機制可描述如下：79Swait(S1,S2,…,Sn)

ifSi≥1and…andSn≥1then

fori:=1tondo

Si:=Si-1;

endfor

else

將該進程放入阻塞態佇列；

endif

Ssignal(S1,S2,…,Sn)

fori:=1tondo

Si=Si+1;

喚醒所有因Si不滿足而進入阻塞佇列的進程；

endfor;804．信號量集

信號量集機制的基本思想是：在AND型信號量集的基礎上進行擴充，進程對信號量Si的測試值為ti（用於信號量的判斷，即Si>=ti，表示資源數量低於ti時，便不予分配），佔用值為di（用於信號量的增減，即Si=Si-d1和Si=Si+d1）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般“信號量集”的幾種特定情況：（1）Swait(S,d,d)表示每次申請d個資源，當少於d個時，便不分配；（2）Swait(S,1,1)表示互斥信號量；（3）Swait(S,1,0)作為一個可控開關（當S≥1時，允許多個進程進入臨界區；當S=0時，禁止任何進程進入臨界區）；（4）“信號量集”未必成對使用Swait和Ssignal。如：一起申請，但可以不一起釋放。812.5進程同步問題舉例

2.5.1生產者—消費者問題1．問題的描述

有一批生產者進程在生產產品，並將這些產品提供給消費者進程去消費。為方便生產者進程與消費者進程能併發執行，在兩者之間設置了一個具有n個緩衝區的緩衝池，生產者進程將它所生產的產品放入一個緩衝區中；消費者進程可從一個緩衝區中取走產品去消費。82012……i………n-2n-1

假設初始情況下緩衝池為空，即counter＝０。為在生產者—消費者問題中實現各進程的同步，可設下列信號量：（假設初始情況下沒有進程使用緩衝池，且緩衝池中各緩衝區都是空的。）mutex：互斥使用緩衝池信號量，由於初始情況下無進程使用緩衝池，故初值mutex=１；empty：使用緩衝池中空緩衝區的信號量，由於初始情況下所有緩衝區為空，故初值empty=n；full：使用緩衝池中滿緩衝區的信號量，由於初始情況下沒有緩衝區存放產品，故初值full＝０。

設開始時生產者進程存放產品和消費者進程取產品時，都從第０號緩衝區開始，並設這些生產者和消費者地位相當，只要緩衝池未滿，生產者便可將消息送入緩衝池；只要緩衝池未空，消費者便可從緩衝池中取走一個消息。83inout圖2-12生產者—消費者問題中的緩衝池演算法及程式Var

mutex,empty,full:semaphore∶=1,n,0;／＊定義信號量並賦初值＊／

buffer:array［0,…,n-1］ofitem;

in,out:integer∶=0,0;／＊定義存取指針的初始位置＊／

begin

parbegin

生產者進程proceduer：begin

repeat

…

生產一件產品;

…

wait(empty);

wait(mutex);

將產品放入下一個緩衝區;

in∶=(in+1)modn;

signal(mutex);

signal(full);

untilfalse;

end

84消費者進程consumer：begin

repeat

wait(full);

wait(mutex);

從下一個緩衝區中取走一件產品;

out∶=(out+1)modn;

signal(mutex);

signal(empty);

消費這件產品;

untilfalse;

end

parend

end854．在生產者—消費者問題中應注意：

（１）在每個程式中用於實現互斥的wait(mutex)和signal(mutex)必須成對地出現。（２）對資源信號量empty和full的wait和signal操作，同樣需要成對地出現，但它們分別處於不同的進程中，這樣保證生產者進程和消費者進程的同步及交替執行。（３）在每個進程中，多個wait操作順序不能顛倒，而signal操作的次序是無關緊要的。862.5.2讀者—寫者問題

1．問題的提出一檔Ｆ可以被多個併發進程共用，將這些訪問該檔的進程按訪問方式分為兩類：一類只能讀共用對象的內容，把這類進程稱為讀進程或讀者；另一類進程則要更新（寫）共用對象檔F，將這些進程稱為寫進程或寫者。試用Wait、Signal操作解決各進程間的同步問題。2．問題的分析顯然，多個讀者同時讀一個共用對象是可以的，然而一個寫者不能與其它任何讀者或寫者同時共用該檔。亦即：在使用共用檔時，一個寫進程與其它所有進程都是互斥的。但多個讀進程之間不存在互斥的現象。如圖2-13所示。87共用檔F寫進程W讀進程R1讀進程Rn…圖2-13

讀者—寫者問題

設讀進程為reader，寫進程為writer。為實現reader與writer進程間的同步與互斥，設如下變數及信號量：

wmutex：互斥使用該共用檔信號量。如：寫進程write與讀進程reader在使用檔時是互斥的；共用檔只有一個，設初始情況未被使用，則初值為1。

readcount：整型變數，表示正在讀的進程個數。初值為0。該變數屬臨界資源。

rmutex：計數器readcount的信號量。因為readcount是一個可被多個reader進程訪問的臨界資源，為此設一信號量。設初始狀態下無進程讀和寫，故rmutex的初值設為1。88

由於多個進程可以同時讀，因此只要有一個reader進程在讀，其他reader進程便不必申請該共用檔，直接讀即可；若無檔在讀，則第一個讀檔的進程必須做申請該檔的操作。只要有read進程在執行，則不允許writer進程去寫。因此，僅當readcount=0,即無reader進程在讀時，reader進程才需要執行wait(wmutex)操作。若wait(wmutex)操作成功，reader進程便可去讀，相應地，做readcount+1操作。同理，僅當reader進程在執行了readcount減1操作後其值為0時，才須執行signal(wmutex)操作，以便讓writer進程寫。893．演算法及程式

讀者—寫者問題可描述如下：Var:rmutex,wmutex:semaphore:=1,1;

Readcount:integer:=0;

begin

parbegin

讀者進程：Reader:begin

repeat

wait(rmutex);

ifreadcount=0thenwait(wmutex);

readcount:=Readcount+1;

signal(rmutex);

90

…

進行讀操作;

…

wait(rmutex);

readcount:=readcount-1;

ifreadcount=0thensignal(wmutex);

signal(rmutex);

untilfalse;

end

寫者進程：writer:begin

repeat

wait(wmutex);

執行寫操作;

signal(wmutex);

untilfalse;

end

parend

end914．注意事項及提示（1）對於寫進程，共用檔是臨界資源；而對於讀進程，該檔不是臨界資源。（2）整型變數readcount是臨界資源，所以在使用前後要進行Wait、Signal操作。

922.5.3哲學家進餐問題1．問題的提出

設有5個哲學家圍坐在一張圓桌前吃飯。桌上有5只筷子，在每人之間放一只。哲學家要吃飯時，只有分別從左、右兩邊都拿到筷子時，才能吃飯。如果筷子已在他人手上，則該哲學家必須等待到他人吃完後才能拿到筷子；任何一個哲學家在自己未拿到兩只筷子吃飯之前，決不放下自己手裏的筷子。試描述5位哲學家吃飯的進程。93圖2-14

哲學家就餐餐問題942．問題分析

放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現對筷子的互斥使用，可以為每一只筷子設置一個信號量，由這五個信號量構成信號量數組：Varchopstick:array［0,…,4］ofsemaphore;

設初始條件下，所有哲學家都未吃，故所有信號量均被初始化為1。3．實現方法

假設每一位哲學家拿筷子的方法都是：先拿起左邊的筷子，再拿起右邊的筷子，則第i位哲學家的活動可描述為：95Pi()beginVarchopstick:array［0,…,4］ofmaphore=[1,1,1,1,1];

repeat

wait(chopstick［i］);

wait(chopstick［(i+1)mod5］); eat;

…

signal(chopstick［i］);

signal(chopstick［(i+1)mod5］);

think;

untilfalse;end96

以上演算法存在一個問題：假設5個哲學家同時拿起左邊的筷子，那麼再去拿右邊的筷子時，就會產生死鎖。下麵給出幾種解決方法。（1）至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，並在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。（2）僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。（3）規定奇數號哲學家先拿他左邊的筷子，然後再去拿右邊的筷子；而偶數號哲學家則相反。最後總會有一位哲學家能獲得兩只筷子而進餐。具體程式段參看實訓教材。974．不產生死鎖的哲學家就餐問題演算法

2.6進程通信

進程間的資訊交換稱為進程通信。通常，進程間的通信分為兩種：控制資訊的傳送與大量資訊的傳送。將進程間控制資訊的交換稱為低級通信，而把進程之間大批量數據的交換稱為高級通信。進程的互斥與同步為低級通信方式，相應地，也稱wait、signal操作為低級的通信原語。僅通過P、V操作或鎖的方法是無法實現進程的高級通信的。高級通信方式可分為三大類：共用記憶體系統、消息傳遞系統和管道通信系統。982.6.1共用記憶體系統1．共用記憶體系統的類型（1）基於共用數據結構的通信方式在這種通信方式中，要使各進程共用某些數據結構，藉以實現各進程間的資訊交換。如在生產者—消費者問題中，就是用有界緩衝區這種數據結構來實現通信的。這種通信方式是低效的，只適用於傳遞相對少量的數據。（2）基於共用存儲區的通信方式。在記憶體中劃出了一塊共用存儲區，各進程可通過對共用存儲區中的數據的讀或寫來實現通信。992．Linux共用存儲區通信的實現（1）共用存儲區的建立利用系統調用shmget()建立一塊共用存儲區。該系統調用將返回該共用存儲區的描述符shmid；若尚未建立，便為進程建立一個指定大小的共用存儲區。（2）共用存儲區的操縱可以用shmctl()系統調用對共用存儲區的狀態資訊進行查詢，如其長度、所連接的進程數、創建者識別字等；也可設置或修改其屬性，如共用存儲區的許可權、當前連接的進程計數等；還可用來對共用存儲區加鎖或解鎖，以及修改共用存儲區識別字等。3.共用存儲區的附接與斷開

在進程已經建立了共用存儲區或已獲得了其描述符後，還須利用系統調用shmat()將該共用存儲區附接到用戶給定的某個進程的虛地址shmaddr上，並指定該存儲區的訪問屬性，即指明該區是只讀，還是可讀可寫。此後，此共用存儲區便成為該進程虛地址空間的一部分。進程可採取與對其他虛地址空間一樣的存取方法來訪問。當進程不再需要該共用存儲區時，再利用系統調用shmdt()把該區與進程斷開。4．幾個相關系統調用共用存儲區通信中常用的系統調用：（1）shmget(key,size,flag)：功能：獲得一個共用存儲區，若成功，其返回值為該共用存儲區的描述符。（2）shmat(id,addr,flag)從邏輯上將一個共用存儲區附接到進程的虛擬地址空間上。（3）shmdt(addr)：把一個共用存儲區從指定進程的虛地址空間斷開。（4）shmctl(id,cmd,buf)對與共享存儲區關聯的各種參數進行操作，從而對共用存儲區進行控制。1022.6.2消息傳遞系統

在消息傳遞系統中，進程間的數據交換，是以格式化的消息（message）為單位的。程式員直接利用系統提供的一組通信命令進行通信。因實現方式的不同分為直接通信方式和間接通信方式。間接通信方式又稱為信箱通信方式。信箱是一種數據結構，邏輯上可分為兩部分：信箱頭和信箱體。信箱頭包含箱體的結構資訊，信箱體由多個格子構成。信箱通信一般是進程之間的雙向通信。1031．直接通信方式

這種通信是固定在一對進程之間。用來發送和接收消息。兩條原語的形式如下：send(B,message);發送一個消息給接收進程B；receive(A,message);接收進程A發來的消息；通常情況下，接收進程可與多個發送進程通信，因此，它不可能事先指定發送進程。對於這樣的應用，在接收進程接收消息的原語中的源進程參數，是完成通信後的返回值，接收原語可表示為：receive(id,message);其中，id為接收消息進程的識別字。2．間接通信方式

間接通信方式又稱為信箱通信方式。信箱是一種數據結構，邏輯上可分為兩部分：信箱頭和信箱體。信箱頭包含箱體的結構資訊，信箱體由多個格子構成，它實際上就是一個有界緩衝池。信箱通信一般是進程之間的雙向通信。如圖2-15所示。

信箱體sendreceivereceivesend進程B信箱頭圖2-15進程的信箱通信方式進程A3．消息緩衝佇列通信機制

（1）消息緩衝佇列通信機制中所用的主要數據結構是消息緩衝區。在設置消息緩衝佇列時，還應添加用於對消息佇列進行操作和實現同步的信號量，並將它們存入進程的PCB中。

當一個發送進程要發送消息時，便形成一個消息，併發送給指定的接收進程。接收進程將所有的消息緩衝區鏈成一個佇列，其佇列首由接收進程PCB中的佇列隊首指針mq來指出。

（2）發送原語（3）接收原語接收進程調用接收原語，從自己的消息緩衝佇列中，選取第一個消息緩衝區，並將其中的數據複製到指定的消息接收區內。

發送進程在發送消息之前，應先在自己的記憶體空間設置一發送區，然後調用發送原語，把消息發送給接收進程。4．Linux系統關於消息傳遞的相關系統調用

（1）msgget(key,flag):功能：獲得一個消息的描述符，該描述符指定一個消息佇列以便用於其他系統調用。（2）msgsnd(id,msgp,size，flag);功能：發送一消息。（3）msgrcv(id,msgp,size,type,flag)功能：接受一消息。（4）msgctl(id,cmd,buf)：功能：查詢一個消息描述符的狀態,設置它的狀態及刪除一個消息描述符。

2.6.3管道通信系統

所謂管道，是指用於連接一個讀進程和一個寫進程，以實現他們之間通信的一個共用檔，又名pipe檔。為了協調雙方的通信，管道機制必須提供以下三方面的協調能力：（1）互斥，即當一個進程正在對pipe執行讀/寫操作時，其他(另一)進程必須等待。（2）同步，指當讀寫進程使用pipe時，需要同步使用。（3）確定對方是否存在，只有確定了對方已存在時，才能進行通信。1092.6.4信號通信機制

1．信號的基本概念每個信號都對應一個正整數常量，即信號編號。信號機制具有以下三方面的功能：（1）發送信號。發送信號的程式用系統調用kill()實現；（2）預置對信號的處理方式。接收信號的程式用signal()來實現預置處理方式；（3）收受信號的進程按事先的規定完成對相應事件的處理。

1102．信號的發送

信號的發送，是指由發送進程把信號送到指定進程的信號域的某一位上。進程用kill()向一個進程或一組進程發送一個信號。3．信號的處理

對軟中斷信號的處理分三種情況進行：（1）如果進程收到的軟中斷是一個已決定要忽略的信號（function=1），進程不做任何處理便立即返回；（2）進程收到軟中斷後便退出（function=0）；（3）執行用戶設置的軟中斷處理程式。4．相關的Linux系統調用（1）kill()功能：向一個或一組進程發送一個軟中斷信號。（2）signal()功能：預置對信號的處理方式，允許調用進程控制軟中斷信號。1122.7線程

線程是比進程更小的能獨立運行的基本單位。2.7.1線程的基本概念線程（thead）是進程中執行運算的最小單位，亦即執行處理機調度的基本單位。在引入線程的操作系統中，可以在一個進程內部進行線程切換，現場保護工作量小。線程與進程的比較：（1）進程是資源分配的基本單位。同一進程的所有線程共用該進程的所有資源。（2）線程是分配處理機的基本單位，它與資源分配無關。（3）一個線程只能屬於一個進程，而一個進程可以有多個線程，但至少有一個線程。（4）線程在執行過程中，需要協作同步。1132.7.2線程的狀態與轉換操作

線程有3種基本狀態，即執行、阻塞和就緒。針對線程的3種基本狀態，存在5種基本操作來轉換線程的狀態。它們是：1．派生（spawn）2．調度（schedule）3．阻塞（Block）4．啟動（unblock）5．結束（Finish）1142.7.3引入線程的好處

引入線程的好處有以下幾點：1．易於調度。2．提高了系統的效率。3．創建一個線程比創建一個進程花費的開銷少，創建速度快。4．有利於發揮多處理器的功能，提高進程的並行性。1152.7.4多線程的實現

多線程機制是指操作系統支持在一個進程內執行多個線程的能力。多種系統支持多線程實現的方式並不完全相同。1．用戶級線程用戶級線程是由用戶應用程式建立的，並由用戶應用程式負責對這些線程進行調度和管理，操作系統內核並不知道有用戶級線程的存在，只對進程進行管理。2．內核級線程內核級線程簡稱為KLT，通常也稱為“純KLT”方法。內核級線程中所有線程的創建、調度和管理全部由操作系統內核負責完成。

3．用戶級線程與核心態線程相結合的模式由於用戶級線程和內核級線程各有其特色，因此，如果將兩種方法結合起來，則可吸取兩者的優點。將兩種方法結合起來的系統稱為多線程的操作系統。內核支持多線程的建立、調度和管理。同時系統中又提供使用線程庫，允許用戶應用程式建立、調度和管理用戶級線程。本章小結

進程是操作系統中的一個非常重要的概念。進程是程式的一次執行，同時它也是操作系統進行資源分配的單位。進程具有一些特徵，是與程式有根本區別的概念。進程具有動態性、併發性、非同步性、獨立性的特性。反映進程動態性的是進程狀態的變化。進程從創建到被撤銷，要經過一些具有生命狀態的活動。進程的三個基本狀態包括阻塞、就緒、執行，除此之外，不同的操作系統還具有其他一些狀態。進程的狀態轉換由相應的原語來完成。進程的併發執行是指，在同一時間間隔內多個進程同時發生。進程的併發特性反映在進程對資源的競爭以及由資源競爭所引起的對進程執行速度的制約。我們可以通過提高進程的併發性，來提高整個系統的效率。118進程上下文由以下部分組成：進程控制塊、正文段、數據段以及各種寄存器和堆疊中的值。進程控制塊PCB是進程存在的惟一標誌，它包含進程的運行資訊和程式的控制資訊。進程控制塊在內存中的組織方式有：線性方式、鏈接方式和索引方式。對於Linux系統，我們可以通過幾個常用的進程創建和控制的系統調用，實現對進程的控制。119不能被多個進程同時使用的資源稱為臨界資源。將每個進程中訪問臨界資源的那段代碼稱為臨界區。多個進程不能同時進入同一個臨界區，叫做進程之間的互斥；多個進程在使用臨界資源時，表現出來的相互協調、相互合作、互相等待，使得各進程按一定的速度執行的過程稱為進程間的同步。具有同步關係的一組併發進程稱為合作進程。實現進程的互斥和同步，可以用鎖或P、V操作來實現。P操作是申請臨界資源的原語操作，也稱為wait操作；V操作是釋放臨界資源的原語操作，也稱為signal操作。信號量是P、V操作的對象。1203.1分級調度

一個批處理型作業，從進入系統並駐留在外存的後備佇列上開始，直至作業運行完畢，可能要經歷以下三級調度：即作業調度、對換和進程調度。1213.1.1調度的層次1．作業調度

作業調度又稱為高級調度或長調度，用於選擇把外存上處於後備佇列中的哪些作業調入記憶體，並為它們創建進程、分配必要的資源。然後，再將新創建的進程排在就緒佇列上，準備執行。在批處理系統中，需要有作業調度的過程，以便將它們分批地裝入記憶體。無須再配置作業調度機制。在分時系統和即時系統中，通常也不需要作業調度。122

一個作業從提交給電腦系統到執行結束退出系統，一般都要經歷提交、後備、執行和完成等4個狀態。提交狀態：一個作業在其處於從輸入設備進入外部存儲設備的過程稱為提交狀態。後備狀態：也稱為收容狀態。若一個作業的全部資訊已全部被輸入進輸入井，則在它還未被調度去執行之前，該作業處於後備狀態。執行狀態：作業調度程式從後備作業中選取若干個作業到記憶體投入運行。它為被選中作業建立進程並分配必要的資源，這時，這些被選中的作業處於執行狀態。完成狀態：當作業運行完畢，但它所佔用的資源尚未全部被系統回收時，該作業處於完成狀態。1232．對換

又稱交換調度或中級調度。其主要任務是按照給定的原則和策略，將處於外存交換區中的就緒狀態或等待狀態的進程調入記憶體，或把處於記憶體就緒狀態或記憶體等待狀態的進程交換到外存交換區。

1243．進程調度

進程調度又稱為低級調度或微觀調度。其主要任務是按照某種策略和演算法，將處理機分配給一個處於就緒狀態的進程。進程調度可分為下列兩種方式：（1）非搶佔方式：非搶佔方式不允許進程搶佔已經分配出去的處理機。

（2）搶佔方式：搶佔調度方式允許調度程式根據某種原則，暫停某個正在執行的進程，將處理機收回，重新分配給另一個進程。

125完成作業調度預輸入輸入井緩輸出圖３-1作業調度與進程調度作業輸出井就緒運行等待結果126

作業是用戶向電腦提交任務的任務實體。一個作業是指在一次應用業務處理過程中，從輸入開始到輸出結束，用戶要求電腦所做的有關該次業務處理的全部工作。一個作業總是由一個或多個進程組成的。作業分解為進程的過程是：系統首先為一個作業創建一個根進程。然後，在執行作業控制語句時，根據任務要求，系統或根進程為其創建相應的子進程。最後，進行進程調度，為各子進程分配資源和調度各子進程執行，以完成作業要求的工作。3.1.2作業與進程的關係1273.2作業調度

作業調度主要是完成作業從後備狀態到執行狀態的轉換，以及從執行狀態到完成狀態的轉換。1283.2.1作業調度的功能1．記錄系統中各作業的狀態圖３-２作業控制塊ＪＣＢ作業名作業類型計算型管理型圖形設計型資源要求記憶體量外存量外設類型及數量軟體支持工具庫函數當前狀態提交狀態後備態運行態完成資源使用情況進入系統的時間開始執行時間已運行時間記憶體地址外設台數作業的優先順序1292．從後備佇列中挑選出一部分作業投入執行。作業調度程式根據選定的調度演算法，從後備作業佇列中挑選出若干作業去投入執行。

3．為被選中作業做好執行前的準備工作。作業調度程式為選中的作業建立相應的進程，並為這些進程分配它們所需要的系統資源，如分配給它們記憶體、外存、外設等。

4．在作業執行結束時做好善後處理工作。包括輸出作業管理資訊；回收該作業所佔用的資源；撤銷與該作業有關的全部進程和該作業的作業控制塊等等。作業從後備狀態到執行狀態以及從執行狀態到完成狀態的轉換過程如圖３-3所示。

130按調度演算法，從後備作業中選出一作業調用存儲管理、設備管理程式，審核資源要求分配資源調用進程管理程式建立進程進程調度放棄該作業調用存儲管理，設備管理回收分配給該作業的全部資源調用會計程式，計算該作業的執行費用撤銷該作業的所有進程及作業的JCB調度下一個作業後備作業佇列空資源要求能滿足？是

出口否否圖3-3(a)作業從後備狀態到執行狀態(b)作業從執行狀態到完成狀態是1313.2.2調度演算法的評價及準則1．面向用戶的準則2．面向系統的準則1321．面向用戶的準則（1）周轉時間短周轉時間：是指作業被提交給系統開始，到作業終止為止的這段時間間隔，也稱為作業周轉時間。它包括四部分時間：a．作業在外存後備佇列上等待調度的時間。b．進程在就緒佇列上等待進程調度的時間。c．進程佔用CPU執行的時間。d．進程等待I/O操作完成的時間。133作業i的周轉時間Ti可定義為：

Ti=Tei—Tsi其中，Tei為作業i的完成時間，Tsi為作業i的提交時間。平均周轉時間為：T=]作業的周轉時間T與系統為它提供服務的時間（即作業要求運行時間）Ts之比，稱為帶權周轉時間，即：134帶權周轉時間W＝Ｔ／Ts因為周轉時間T=等待時間+運行時間Ts，因此，W也可表示為：W＝1+等待時間／運行時間從公式可以看出，W≤1，即W的最小值為1。可以看出，帶權周轉時間越接近1，則該作業相對等待時間越短，系統性能越高。而平均帶權周轉時間可表示為：W=

135（２）回應時間快

所謂回應時間，是指從用戶提交一個作業請求開始，直至系統首次產生回應為止的時間。它包括三部分時間：從鍵盤輸入的請求資訊傳送到處理機的時間。處理機執行回應處理的時間。將所形成的回應資訊在終端顯示器上顯示出來的時間。（３）截止時間的保證。所謂截止時間，是指某任務必須開始執行的最晚時間，或必須完成的最晚時間。

（４）優先權準則。調度程式根據任務的優先權確定先選中哪個作業。1362．面向系統的準則