第3章 進程與進程管理

1、第3章 進程與進程管理,操作系統（第3版）,第3章 進程與進程管理,3.1 進程的引入 3.2 進程 3.3 進程調度 3.4 線程的基本概念 3.5 Linux的進程與進程管理,3.1 進程的引入,前趨圖的定義 前趨圖（Procedence Graph）是一個有向無循環(huán)圖（DAG）。圖中的每個結點可用于表示一條語句、一個程序段或進程；結點間的有向邊則表示在兩結點之間存在的偏序或前趨關系“”，=(Pi，Pj)| Pi必須在Pj開始前完成 。,3.1 進程的引入,程序順序執(zhí)行 定義 程序在執(zhí)行時，必須按照某種先后次序逐個執(zhí)行，僅當前一操作執(zhí)行完后，才能執(zhí)行后繼操作 程序順序執(zhí)行的特征 程序執(zhí)行的

2、順序性 處理機的操作嚴格按程序規(guī)定的順序執(zhí)行，即只有前一操作結束后才能執(zhí)行后繼操作,3.1 進程的引入,程序執(zhí)行的封閉性 程序一旦開始運行，其執(zhí)行結果不受外界因素的影響 程序執(zhí)行結果的確定性 程序執(zhí)行的結果與它的執(zhí)行速度、時間無關 程序結果的可再現性 程序執(zhí)行時的環(huán)境和初始條件相同，當程序多次重復執(zhí)行時，都將獲得相同的結果,3.1 進程的引入,程序并發(fā)執(zhí)行 定義 在上圖中的輸入程序、計算程序和打印程序三者之間，存在著IiCiPi這樣的前趨關系，以致對一個作業(yè)的輸入、計算和打印三個操作必須順序執(zhí)行，但并不存在PiIi+1關系，因而在對一批程序進行處理時，可使它們并發(fā)執(zhí)行。,3.1 進程的引入,程

3、序并發(fā)執(zhí)行特征 程序執(zhí)行的間斷性 程序執(zhí)行的相互制約將導致并發(fā)程序具有“執(zhí)行暫停執(zhí)行執(zhí)行”這種間斷性的活動規(guī)律 程序執(zhí)行失去封閉性 因多個程序共享系統中的資源，所以某程序在執(zhí)行時必然會受到其他程序的影響,3.1 進程的引入,程序執(zhí)行結果的不可再現性 由于失去了封閉性，也將導致失去其可再現性 資源共享 系統中的硬件資源和軟件資源不再被單個用戶或程序獨占，而為多個用戶或作業(yè)共同使用 程序和計算不再一一對應 程序和計算是兩個不同的概念，在程序并發(fā)執(zhí)行中一個共享程序可對應多個“計算”，程序與“計算”已不再一一對應,3.1 進程的引入,多道程序設計 定義 在采用多道程序設計的計算機系統中，允許多個程序同

4、時進入一個計算機系統的內存儲器并運行，這種讓多個程序同時進入計算機計算的方法稱為多道程序設計。 目的 提高處理器的效率，從而提高整個系統的效率 必須解決的問題 存儲保護與程序浮動 處理器的管理和調度 系統資源的管理和調度,3.2 進程,引入進程的原因 為了使程序在多道程序環(huán)境下能夠并發(fā)執(zhí)行，并對并發(fā)執(zhí)行的程序加以控制和描述，引入進程的概念 程序段、數據段及進程控制塊三部分構成了一個進程的實體 進程的概念 進程的定義 進程是具有獨立功能的可并發(fā)執(zhí)行的程序在一個數據集合上的運行過程，是系統進行資源分配和調度的獨立單位?；蛘哒f，“進程”是進程實體的運行過程。,3.2 進程,程序與進程的區(qū)別與聯系 區(qū)

5、別: 進程是程序的一次執(zhí)行，是一個動態(tài)的概念，程序是完成某個特定功能的指令的有序序列，是一個靜態(tài)的概念 一個進程可以執(zhí)行一個或幾個程序，同一程序也可能由多個進程同時執(zhí)行 進程是系統進行資源分配和調度的一個獨立單位，程序則不是 程序可以作為一種軟件資源長期保存，而進程是程序的一次執(zhí)行過程，它是臨時的，有生命期的 進程是具有結構的 聯系:進程是程序的運行,3.2 進程,進程的特征 動態(tài)性：進程的基本特性。進程是進程實體的執(zhí)行過程； 并發(fā)性:進程的主要特征。多個進程實體同存于內存中，能在一段時間內同時運行； 獨立性：進程實體是一個能獨立運行的基本單位，同時也是系統中獨立獲得資源和獨立調度的基本單位。

6、 異步性：進程按各自獨立的、不可預知的速度向前推進；或者說，進程按異步方式運行。 結構特征：從結構上看，進程實體是由程序段、數據段及進程控制塊三部分組成，有人把這三部分統稱為“進程映像”。,3.2 進程,進程的基本狀態(tài)及其轉換 進程的三種基本狀態(tài) 就緒狀態(tài) 當進程已分配到除CPU以外的所有必要的資源后，只要能再獲得處理機便可立即執(zhí)行，這時的狀態(tài)稱為就緒狀態(tài) 執(zhí)行狀態(tài) 指進程已獲得處理機，其程序正在執(zhí)行 阻塞狀態(tài) 進程因發(fā)生某種事件（如I/O請求、申請緩沖空間等）而暫停執(zhí)行時的狀態(tài)，亦即進程的執(zhí)行受到阻塞，故稱這種狀態(tài)為阻塞狀態(tài)，有時也稱為“等待”狀態(tài)或“睡眠”狀態(tài)。 思考:剛剛創(chuàng)建的進程應該處

7、于哪種狀態(tài)?,3.2 進程,進程狀態(tài)的轉換 就緒執(zhí)行狀態(tài) 處于就緒狀態(tài)的進程，當進程調度為之分配了處理機后 執(zhí)行阻塞狀態(tài) 正在執(zhí)行的進程因發(fā)生某種事件而無法執(zhí)行 執(zhí)行就緒狀態(tài) 正在執(zhí)行的進程如因時間片用完或一個優(yōu)先權高的進程到來而被暫停執(zhí)行 阻塞就緒狀態(tài) 處于阻塞狀態(tài)的進程，其等待的事件已經發(fā)生 思考:其他狀態(tài)轉換可以存在嗎?,3.2 進程,3.2 進程,進程的掛起狀態(tài) 掛起狀態(tài)的引入 終端用戶的需要 當終端用戶在自己的程序運行期間發(fā)現有可疑問題時，往往希望暫時使自己的進程靜止下來。 父進程的需要 父進程常常希望考察和修改子進程或者當要協調各子進程間的活動 操作系統的需要 操作系統有時需要掛起

8、某些進程，檢查運行中資源的使用情況及進行記賬，以便改善系統運行的性能。,3.2 進程,對換的需要 為了緩解內存緊張的情況，即將內存中處于阻塞狀態(tài)的進程換至輔存上，使進程又處于一種有別于阻塞狀態(tài)的新狀態(tài)。 負荷調節(jié)的需要 進程狀態(tài)的轉換 在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（又稱靜止狀態(tài)）到非掛起狀態(tài)（又稱活動狀態(tài)）的轉換 活動就緒靜止就緒 活動阻塞靜止阻塞 靜止就緒活動就緒 靜止阻塞活動阻塞,3.2 進程,進程控制塊PCB 進程控制塊的作用 進程控制塊記錄進程信息 操作系統是根據進程控制塊PCB來對并發(fā)執(zhí)行的進程進行控制和管理的 PCB是進程存在的唯一標志 思考:進程控制塊應該存放在何處?需要

9、存放在磁盤中嗎? 進程控制塊中的信息 進程標識符信息 進程標識符用于唯一地標識一個進程，通常有外部標識符和內部標識符,3.2 進程,外部標識符。由創(chuàng)建者提供，通常由字母、數字所組成，往往是由用戶（進程）在訪問該進程時使用。 內部標識符。這是為了方便系統使用而設置的。在所有操作系統中都為每一個進程賦予一個惟一的整數作為內部標識符，它通常就是一個進程的序號。 處理機狀態(tài)信息 處理機狀態(tài)信息主要是由處理機各種寄存器中的內容所組成 ：通用寄存器、指令計數器、程序狀態(tài)字PSW、用戶棧指針。 進程調度信息 存放了一些與進程調度和進程對換有關的信息：進程狀態(tài)、進程優(yōu)先級、進程調度所需的其他信息、事件。,3.

10、2 進程,進程控制信息 程序和數據的地址、 進程同步和通信機制、資源清單、鏈接指針。 PCB的組織方式 - 鏈接方式 把具有相同狀態(tài)的PCB鏈接成一個隊列，這樣可形成就緒隊列、若干個阻塞隊列和空隊列等 - 索引方式 系統根據所有進程的狀態(tài)建立幾張索引表,思考:你認為圖中缺少什么內容嗎?,3.2 進程,進程控制 進程控制的主要任務是創(chuàng)建和撤消進程以及實現進程的狀態(tài)轉換，進程控制一般由操作系統的內核來實現。操作系統內核通常是運行在系統態(tài)的。 操作系統內核 定義 通常，將一些與硬件緊密相關的模塊諸如中斷處理程序、各種常用設備的驅動程序以及運行頻率較高的模塊都安排在緊靠硬件的軟件層次中并使它們常駐內存

11、，以便提高操作系統的運行效率，并對它們加以特殊的保護，把這一部分稱為操作系統的內核,3.2 進程,操作系統內核的功能 中斷處理：中斷處理功能在操作系統中，既是內核的最基本功能，也是整個操作系統賴以活動的基礎，即操作系統的重要活動最終都將依賴于中斷。 進程管理：進程創(chuàng)建、撤消、進程狀態(tài)的轉換 、進程調度等。 資源管理中的基本操作：包括對時鐘、I/O設備和文件系統進行控制和管理的基本操作。 原子操作 所謂原子操作是指：一個操作中的所有動作，要么全做，要么全不做。換言之，原子操作是一個不可分割的操作 內核在執(zhí)行上述操作時，往往是通過執(zhí)行各種原語操作來實現的。,3.2 進程,進程的創(chuàng)建 進程圖 進程圖

12、是用于描述進程家族關系的有向樹 子進程可以繼承父進程所擁有的資源，當子進程撤銷時，應將從父進程那里獲得的資源歸還給父進程；在撤銷父進程時，也必須同時撤銷其所有的子進程 引起創(chuàng)建進程的事件 用戶登錄 作業(yè)調度 提供服務 應用請求,3.2 進程,進程的創(chuàng)建過程 調用進程創(chuàng)建原語create( )創(chuàng)建進程 申請空白PCB 為新進程分配資源 初始化進程控制塊 將新進程插入就緒隊列 思考:前兩步驟是否可以顛倒順序?,3.2 進程,進程的終止 引起進程終止的事件 - 正常結束 - 異常結束 - 外界干預 進程的終止過程 調用進程終止原語destroy( )終止進程 根據被終止進程的標識符從PCB集合中檢索

13、出該進程的PCB，從中讀出該進程的狀態(tài) 若被終止進程正處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行并設置調度標志為真,3.2 進程,若該進程還有子孫進程，還應將其所有子孫進程予以終止 將該進程所擁有的全部資源，或者歸還其父進程或者歸還給系統 釋放進程的PCB 進程的阻塞與喚醒 引起進程阻塞和喚醒的事件 - 請求系統服務 - 啟動某種操作 - 新數據尚未到達 - 無新工作可作,3.2 進程,進程阻塞過程 進程便通過調用阻塞原語block（）把自己阻塞 立即停止當前進程的執(zhí)行 把進程控制塊中的現行狀態(tài)由“執(zhí)行”改為“阻塞”，并把它插入到阻塞隊列 思考:是否轉向進程調度? 進程喚醒過程 調用喚醒原語wake

14、up( )將等待該事件的進程喚醒 把被阻塞進程從等待該事件的阻塞隊列中移出 將其PCB中的現行狀態(tài)由“阻塞”改為“就緒” 然后再將該進程插入到就緒隊列中,3.2 進程,進程的掛起與激活 進程的掛起過程 當出現了引起進程掛起的事件時，系統就利用掛起原語suspend( )將指定進程或處于阻塞狀態(tài)的進程掛起 檢查被掛起進程的狀態(tài)，若正處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進程，則將其改為靜止阻塞 進程保存于外存對換區(qū) 如被掛起的進程正在執(zhí)行，則轉調度程序重新調度,3.2 進程,進程的激活過程 當發(fā)生激活進程的事件時系統將利用激活原語active( )將指定進程激活 將進程從外存調

15、入內存，檢查該進程的現行狀態(tài)：若是靜止就緒，便將其改為活動就緒；若為靜止阻塞，便將其改為活動阻塞 假如采用的是搶占調度策略 ，檢查是否要進行重新調度,3.3 進程調度,調度的基本概念 高級、中級和低級調度 一個作業(yè)從提交開始直到完成，往往要經歷三級調度： 高級調度又稱為作業(yè)調度，它決定將哪些在外存上處于后備狀態(tài)的作業(yè)調入主機內存，準備執(zhí)行 低級調度又稱為進程調度。它決定就緒隊列中哪個進程將獲得處理機，并實際執(zhí)行將處理機分配給該進程的操作 在有的系統中，可能增加一中級調度，主要作用是在內存和外存對換區(qū)之間進行進程對換，以解決內存緊張問題,3.3 進程調度,進程調度的功能 進程調度就是系統按照某種

16、算法把CPU動態(tài)地分配給某一就緒進程。進程調度工作是通過進程調度程序來完成的。 進程調度程序的主要功能： 選擇進程占有CPU 進行進程上下文的切換,3.3 進程調度,調度方式 非剝奪方式 分派程序一旦把處理機分配給某進程后便讓它一直運行下去，直到進程完成或發(fā)生某事件（如提出I/O請求）而阻塞時才把處理機分配給另一進程 優(yōu)點：簡單，系統開銷小， 缺點：貌似公正,可能導致系統性能的惡化 剝奪方式 該方式規(guī)定，當一個進程正在運行時，系統可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程 剝奪原則：優(yōu)先權原則、短進程優(yōu)先原則、時間片原則,3.3 進程調度,進程調度算法 先進先出（FIFO）算

17、法 算法：把處理機分配給最先進入就緒隊列的進程 優(yōu)點：易于實現 缺點：表面上公平，服務質量不佳 、對短進程不利 思考:算法實現 最短CPU運行期優(yōu)先調度算法 算法：從就緒隊列中選出“下一個CPU執(zhí)行期”最短的進程，為之分配處理機使之執(zhí)行 優(yōu)點：可獲得較好的調度性能 缺點： 進程的CPU執(zhí)行期難以準確得到、對長進程不利,3.3 進程調度,最高響應比優(yōu)先調度算法 算法：響應比=（等待時間+要求的服務時間）/要求的服務時間 ，每次選取響應比最高的進程調度 優(yōu)點：所以對短進程有利，并且考慮了等待時間 缺點：計算響應比有一定的系統開銷 優(yōu)先級調度算法 算法：將CPU分配給就緒隊列中優(yōu)先級最高的進程 靜態(tài)

18、優(yōu)先級 在進程創(chuàng)建時確立，確定后運行期間保持不變。確立依據有：進程的類型、進程對資源的需求、用戶申請的優(yōu)先級 優(yōu)點：簡單 缺點：不能動態(tài)反映進程特點，系統調度性能差,3.3 進程調度,動態(tài)優(yōu)先級 進程在開始創(chuàng)建時，根據某種原則確定一個優(yōu)先級后，隨著進程執(zhí)行時間的變化，其優(yōu)先級不斷地進行動態(tài)調整 確定依據：根據進程占有的CPU時間的長短來決定，占有時間越長優(yōu)先級越低；根據進程等待CPU的時間來決定，時間越長優(yōu)先級越高,3.3 進程調度,時間片輪轉調度算法 算法：通常用在分時系統，它輪流地調度系統中所有就緒進程，使就緒進程依次獲得一個時間片的運行時間 時間片長短確定遵循原則 既要保證系統各個用戶進

19、程及時地得到響應，又不要由于時間片太短而增加調度的開銷，降低系統的效率,3.3 進程調度,進程依次執(zhí)行時可能發(fā)生的三種情況 進程未用完一個時間片便結束，這時系統應提前進行調度 進程在執(zhí)行過程中提出I/O請求而阻塞，系統應將它放入相應的阻塞隊列并引起調度 進程用完一個時間片后尚未完成。系統應將它重新放到就緒隊列的末尾，等待下次執(zhí)行,3.3 進程調度,3.3 進程調度,前后臺調度算法 算法：該方法用在批處理和分時相結合的系統中。將分時用戶作業(yè)放在前臺，把批處理作業(yè)放在后臺。系統對前臺作業(yè)按照時間片輪轉法進行調度，僅當前臺無作業(yè)時，才把處理機分配給后臺作業(yè)的進程。后臺進程通常按先來先服務方式運行 優(yōu)

20、點：使分時用戶進程得到及時響應，又提高了系統資源的利用率,3.3 進程調度,多級反饋隊列輪轉算法 系統設置多個不同優(yōu)先級的就緒隊列，每次調度總是先調度優(yōu)先級高的隊列，僅當該隊列空時，才調度次高優(yōu)先級隊列。 通常剛創(chuàng)建的進程和因請求I/O未用完時間片的進程排在最高優(yōu)先級隊列，在這個隊列中運行2-3個時間片未完成的進程排列下一個較低優(yōu)先級隊列。 不論什么時候，只要較高優(yōu)先級隊列有進程進入，立即轉進程調度，及時調度較高優(yōu)先級隊列進程。 優(yōu)點：能較好地滿足各類作業(yè)的用戶要求，既能使分時用戶作業(yè)得到滿意的響應，又能使批處理用戶的作業(yè)獲得較合理的周轉時間,3.3 進程調度,3.3 進程調度,進程調度的時機

21、和過程 進程調度的時機 正在執(zhí)行的進程運行完畢 正在執(zhí)行的進程調用阻塞原語將自己阻塞起來進入等待狀態(tài) 在采用搶占式優(yōu)先級調度時，有優(yōu)先級高于正在運行進程的進程進入就緒隊列 在分時系統中時間片已經用完 CPU方式是可剝奪時，就緒隊列中的某個進程 優(yōu)先級變得高于當前運行進程的優(yōu)先級,3.3 進程調度,進程調度的過程 進程調度所依賴的數據結構通常是調度隊列，由于調度的原因不同，在單處理器系統中設置了多種等待隊列 只有就緒隊列中的進程能夠獲得處理器而最終運行，其他隊列中的進程從隊列中出來后，必須進入就緒隊列才能分配處理器 隊列數據結構的建立結構與調度算法密切相關 進程調度算法只是決定哪一個進程將獲得處

22、理機，而將處理機分配給該進程的具體操作是由分派程序完成的,3.3 進程調度,void dispatcher()if (RQ=0) if (EP=0) idler(); else continue;enqueue(RQ,i);if (EP=0) go to L;j=EP;if(i.priorityj.priority), stop(j); j.status=ready; j.sdata=EPdata; enqueue(RQ,j);L:dequeue(RQ,i) i.status=executing; EP=i; else continue; ,例：,3.4 線程,線程的引入 在操作系統中引入進程

23、的目的是為了使多個程序并發(fā)執(zhí)行以改善資源利用率及提高系統的吞吐量； 在操作系統中再引入線程，則是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統具有更好的并發(fā)性,3.4 線程,線程的定義和屬性 線程的定義 在引入線程的操作系統中，線程是進程的一個實體，是被系統獨立調度和分派的基本單位。線程自己基本上不擁有系統資源，只擁有一點在運行中必不可少的資源，但它可與同屬一個進程的其他線程共享進程所擁有的全部資源。 一個線程可以創(chuàng)建和撤銷另一個線程；同一進程中的多個線程之間可以并發(fā)執(zhí)行,3.4 線程,線程的屬性 線程的狀態(tài) 由于線程之間的相互制約，致使線程在運行中也呈現出間斷性。相應地，線程也同樣有就緒

24、、阻塞和執(zhí)行三種基本狀態(tài) 線程的屬性 每個線程有一個惟一的標識符和一張線程描述表，線程描述表記錄了線程執(zhí)行的寄存器和棧等現場狀態(tài) 不同的線程可以執(zhí)行相同的程序,3.4 線程,同一進程中的各個線程共享該進程的內存地址空間 線程是處理器的獨立調度單位，多個線程是可以并發(fā)執(zhí)行的 一個線程被創(chuàng)建后便開始了它的生命周期，直至終止，線程在生命周期內會經歷等待狀態(tài)、就緒態(tài)和運行態(tài)等各種狀態(tài)變化,3.4 線程,引入線程的好處 創(chuàng)建一個新線程花費時間少（結束亦如此） 兩個線程的切換花費時間少 由于同一進程內的線程共享內存和文件，線程之間相互通信無須調用內核，故不需要額外的通信機制，使通信更簡便，信息傳送速度也快 線程能獨立