1、第3章進程管理操作系統（第三版）操作系統（第三版）操作系統第三版操作系統第三版本章要點本章要點進程的概念線程 進程的控制進程的同步與互斥 進程之間的高級通信進程調度死鎖Windows進程管理操作系統第三版操作系統第三版進程的概念進程的概念 1、前趨圖前趨圖是一個有向無循環圖，每個結點用于表示一條語句、一個程序段或一個進程；結點間的有向邊表示兩個結點之間存在的前趨關系“”。右圖的前趨關系：P1 P2，P1 P3，P1 P4，P2 P5，P3 P5，P3 P6，P4 P6，P5 P7，P6 P7操作系統第三版操作系統第三版2、程序的順序執行和并發執行程序的順序執行例：語句的順序執行。一個程序段中的

2、三個語句: S1：a= x+y S2：b=a+8 S3：c=b-9 其中，語句S2 必須在a被賦值后才能執行，同樣，S3 也只能在b被賦值后才能執行。因此其前趨圖為:S1 S2 S3。程序順序執行時的特征（1）順序性（2）封閉性（3）可再現性操作系統第三版操作系統第三版程序的并發執行程序的并發執行是指多個程序所包含的各項操作可以在同一時間段內同時執行。例：程序段中有四個語句:S1：a=x+1S2：b=y+2 S3：c=a+b S4：d=c+a 可畫出如下圖所示的前趨圖，顯然S1和S2可并發執行操作系統第三版操作系統第三版例：有兩個循環程序A和B，它們共享一個變量n。A和B的程序內容如下：A：

3、S1： n=n+1B： S2： print ( n ) S3： n=0如果A和B以不同的順序運行，可能出現下述三種情況：（程序開始運行前n的值為a）( 1 ) S1S2S3 運行結果為打印出“a+1”且n值為0 ；( 2 ) S2S3S1 運行結果為打印出“a”且n值為1 ；( 3 ) S2S1S3 運行結果為打印出“a”且n值為0 ；操作系統第三版操作系統第三版程序并發執行時的特性l間斷性l通信性l失去封閉性l不可再現性l獨立性操作系統第三版操作系統第三版3 3、進程的定義及特征進程的定義及特征進程（Process）的定義進程是可并發執行的程序段在某個數據集合上的一次運行過程，它是系統進行資

4、源分配和調度的一個獨立單位。 操作系統第三版操作系統第三版進程的特征l動態性 l并發性l獨立性 l異步性l結構特征：系統為每個進程設立一個進程控制塊(PCB)。每個進程實體都是由程序段、相關的數據段和一個進程控制塊三部分組成。進程和程序的區別和聯系進程是一個動態概念，而程序則是一個靜態概念一個程序可以對應一個或多個進程，一個進程至少對應一個或多個程序 程序可作為軟件資源長期保存，進程只是一次執行過程，是暫時存在的 進程是一個能獨立調度并可以和其他進程并發運行的單位，而程序段通常是不能作為獨立調度運行單位的 進程具有并行特征，而程序沒有 操作系統第三版操作系統第三版4 4、進程的進程的狀態及轉換

5、狀態及轉換三種基本狀態就緒狀態執行狀態阻塞狀態操作系統第三版操作系統第三版掛起狀態 掛起會使進程處于靜止狀態（對正在執行的進程暫停執行，對就緒的進程暫時不接受調度，而對阻塞的進程，即使引起阻塞的事件消失，也不能進入就緒隊列）操作系統第三版操作系統第三版5 5、進程進程實體實體進程控制塊PCB（Process Control Block）PCB應包含如下信息:u進程標識符u當前狀態u現場保護區u位置信息u資源清單u進程優先級u通信信息u家族關系操作系統第三版操作系統第三版進程實體 由三部分組成:程序段相關的數據段進程控制塊PCB操作系統第三版操作系統第三版1、線程的基本概念線程（Thread）的

6、定義進程既是資源分配的基本單位，又是可以獨立調度執行的基本單位，這是進程的兩個基本屬性。為了減少操作系統對進程處理的開銷，提高系統中進程并發執行的程度， 20世紀80年代中期，人們引入了線程（Thread）的概念。線程有時也被稱為輕量進程（Light Weight Process簡稱LWP）。在引入線程的操作系統中，人們把進程的兩個屬性分開處理，將進程作為系統資源分配的單位，但不作為處理機調度的單位，而是在進程中創建一個或多個線程，它們并發執行，作為處理機調度的基本單位。 線程線程操作系統第三版操作系統第三版線程實體線程是一個可獨立運行的實體。在一個進程實體中可以包含一個或多個線程實體。當一個

7、進程開始執行時，根據需要可以創建一個或多個線程，線程也可以創建它的子線程。每一個線程有一個線程控制塊TCB，用來記錄線程的標識符、執行時的寄存器和堆棧等現場狀態信息。此外，每個線程有自己的堆棧（系統棧或用戶棧）和寄存器(用來存儲線程內的局部變量，但不能存儲其它線程的相關變量)。堆棧、寄存器和線程的TCB共同構成線程實體。線程的類型內核級線程用戶級線程操作系統第三版操作系統第三版擁有資源調度切換通信關系系統開銷和并發性 動態性構成2、線程與進程的比較操作系統第三版操作系統第三版在Windows NT/2000/XP系統中線程的狀態： 就緒狀態(Ready)備用狀態(Standby)運行狀態(Ru

8、nning)等待狀態(Waiting)轉換狀態(Transition)終止狀態(Terminated)初始化狀態(Initialized)3、線程的狀態與轉換操作系統第三版操作系統第三版4、Windows XP系統的進程和線程使用“任務管理器” 查看進程的相關信息 在計算機的鍵盤上同時按住Ctrl+Alt+Del三鍵，啟動Windows任務管理器，用鼠標單擊“進程”選項卡，顯示關于計算機上正在運行的進程的信息。使用“系統監視器”查看進程和線程的相關信息 單擊“開始”運行輸入perfmon.msc來啟動；或者單擊“開始”“所有程序” “管理工具” “性能”來啟動操作系統第三版操作系統第三版進程的

9、控制進程的控制1、創建和撤銷進程圖 一個進程可以創建 另一個新進程 進程的創建 由進程創建原語實現進程的撤銷 由進程撤銷原語實現操作系統第三版操作系統第三版2、阻塞與喚醒進程的阻塞 如果正在執行的進程期待的某一事件尚未發生時，該進程調用阻塞原語把自己轉到阻塞狀態進程的喚醒 當被阻塞的進程期待的某一事件發生時，由“喚醒進程”調用喚醒原語，將該阻塞進程喚醒 操作系統第三版操作系統第三版3、掛起與激活進程的掛起 當由于用戶進程或父進程的請求以及其它原因需要把某進程掛起時，系統使用掛起原語將該進程掛起 進程的激活 當由于用戶進程或父進程的請求以及其它原因需要把某進程激活時，系統使用激活原語將該進程激活

10、 操作系統第三版操作系統第三版在多道程序系統中，由于資源共享與進程合作，使進程之間可能產生兩種形式的制約關系: （1）間接相互制約 （2）直接相互制約 1、基本概念 臨界資源與臨界區 臨界資源（Critical Resource）是指在一段時間內只允許一個進程訪問的資源。 臨界區（Critical Section）是指進程中訪問臨界資源的那段代碼。 進程同步與互斥進程同步與互斥操作系統第三版操作系統第三版進程的互斥系統對臨界區的調度原則空閑讓進忙則等待有限等待讓權等待喚醒等待進程進程的同步 進程的同步是指并發進程之間存在一種制約關系，一個進程的執行依賴另一個進程的消息，當一個進程沒有得到另一個

11、進程的消息時應等待，直到消息到達才被喚醒 操作系統第三版操作系統第三版進程同步機制進程同步就是多個相關進程在執行次序上的協調。用于保證這種同步關系的相應機制稱為進程同步機制。進程同步機制可以用硬件方法實現，也可以用軟件方法實現。常見的進程同步機制有鎖機制、信號量機制、管程機制等。操作系統第三版操作系統第三版2、鎖機制進程進入臨界區的操作按三步進行：加鎖操作。執行臨界區程序開鎖操作 開、關中斷 (單CPU系統) 使用CPU的硬件中斷標志位作為臨界區的鎖 lock和unlock原語 取值只能是0或1。為0表示資源可以使用，為1表示資源已被占用。加鎖原語lock（）描述為： while(=1)； =

12、1； 開鎖原語unlock（）：0操作系統第三版操作系統第三版3、信號量機制 實現中應注意的問題 整型信號量記錄型信號量AND型“信號量集”機制 一般“信號量集”機制 整型信號量信號量的應用 實現進程互斥 實現進程同步 描述前趨關系 操作系統第三版操作系統第三版4、管程機制管程的引入把所有進程對某一臨界資源的使用進行集中控制，為每個共享資源設立一個專門的管程，統一管理各進程對該資源的訪問 。管程的定義一個管程定義了一個數據結構和能為并發進程調用的在該數據結構上的一組操作，這組操作能同步進程和改變管程中的數據。管程的主要特點模塊化抽象數據類型信息封裝操作系統第三版操作系統第三版5、經典進程同步問

13、題生產者消費者問題 item Buffern; /*緩沖池有n個緩沖區，用來放產品 */semaphore empty=n; /* 空緩沖區的數量*/semaphore full= 0; /* 滿緩沖區的數量 */semaphore mutex= 1; /* 互斥訪問緩沖區 */int in = 0, out = 0; /* 放入/取出緩沖區指針 */main ( )cobeginproducer( );/*生產者*/consumer( ); /*消費者*/coend producer( ) while(TRUE) 生產一件產品;P(empty); /* 申請空緩沖區，如沒有則等待 */P(m

14、utex); /* 有空緩沖區，進程互斥使用緩沖區 */Bufferin = 把產品放在這里; /* 把生產的產品放在緩沖區*/in = (in + 1) % n;/* 輸入指針調整，為下次放入作準備 */V(mutex);/* 釋放緩沖區，若有其它進程等待則喚醒之 */V(full); /* 滿緩沖區的數量加1 */consumer( ) while(TRUE) P(full);P(mutex);從這里取出產品 = Bufferout;out = (out + 1) % n;V(mutex);V(empty);消費這件產品; 操作系統第三版操作系統第三版讀者寫者問題int rc = 0; /

15、* 讀進程的數量 */semaphore wmutex= 1, rmutex= 1;main ( )cobeginreader( ); /*讀者進程*/writer( ); /*寫者進程*/coend reader( )while(TRUE)P(rmutex); /*等待無人讀rc時再繼續*/rc+; /*讀者進程數量加1*/if (rc = 1) P(wmutex); /* 只有自己一個讀者進程時，測試是否有寫者進程 */V(rmutex);讀文件;P(rmutex);rc-; /*讀完后讀者進程數量減1*/if (rc = 0) V(wmutex); /*沒有讀者進程，允許寫*/V(rmu

16、tex); writer( )while(TRUE) P(wmutex);寫文件;V(wmutex); 操作系統第三版操作系統第三版進程之間的信息交換稱為進程通信，用IPC（Inter-Process Communication）表示。并發進程為了能夠協同工作，必須互相交換信息，但交換的信息量可大可小。進程間只能交換少量信息的通信被稱為低級通信。進程間大批量數據信息的交換被稱為高級通信，通常簡稱為進程通信。 進程間高級通信方式可分為三大類 共享存儲器系統 消息傳遞系統 共享文件方式（管道通信） 進程通信進程通信操作系統第三版操作系統第三版1、共享存儲器系統 (Shared-Memory Sys

17、tem)基于共享數據結構的通信方式基于共享存儲區的通信方式 2、消息傳遞系統 ( Message passing system ) 直接通信方式（消息緩沖通信機制） 間接通信方式（信箱通信方式） 消息傳遞系統的特點 3、共享文件方式 （Shared File）（管道通信）管道：用于連接一個讀進程和一個寫進程，以實現它們之間通信的共享文件管道按FIFO方式傳送大量數據，且只能單向傳送數據操作系統第三版操作系統第三版1、調度的基本概念 高級、中級、低級調度 高級調度（High Level scheduling） 低級調度（Low Level Scheduling） 中級調度（Intermediat

18、e Level Scheduling） 進程調度方式 非搶占式調度 （Non-Preemptive Mode） 搶占式調度 （Preemptive Mode）進程調度進程調度操作系統第三版操作系統第三版 2、進程調度的實現進程切換 操作系統中的進程調度程序使當前正在執行的進程讓出處理機，選擇另外一個進程占用處理機的過程稱為進程切換，也叫進程上下文切換。進程切換的步驟：首先保存現場然后選擇要運行的程序最后恢復現場操作系統第三版操作系統第三版3、進程的調度算法先來先服務算法（FCFS） FCFS(First Come First Served) 算法也可稱為先進先出算法FIFO(First In

19、First Out)，是最簡單的調度算法，適用于作業調度和進程調度，采用非搶占式調度方式。 最短進程優先算法（SPF） SPF (Shortest Process First ) 算法適用于作業調度和進程調度，采用非搶占式調度方式。最高優先權優先調度算法（FPF）最高優先級優先算法（HPFHighest Priority First） 本算法考慮到緊迫型進程進入系統后能得到優先處理，適用于作業調度和進程調度，是常用的一種調度算法，可以采用非搶占式或搶占式調度方式。操作系統第三版操作系統第三版時間片輪轉算法(RRRound Robin) 前面幾種算法主要用于批處理系統，不能作為分時系統的主要調度

20、算法，因為它無法滿足分時系統中終端對響應時間的要求。在分時系統中，常采用時間片輪轉調度算法，它是搶占式調度算法。該算法又分為簡單輪轉法和多隊列輪轉法兩種。多級反饋隊列算法(Round Robin with Multiple Feedback Queues) 多級反饋隊列調度算法是時間片輪轉算法和優先級調度算法的綜合和發展，是目前公認較好的一種進程調度算法。它采用搶占式調度方式，通過動態調整進程優先級和時間片大小，不必事先估計進程的執行時間，可兼顧多方面的系統目標，是一種考慮全面又靈活實用的調度算法。 操作系統第三版操作系統第三版1、資源可搶占資源和不可搶占資源共享資源和獨享資源（獨占資源） 永

21、久性資源和臨時性資源 進程使用一個資源的順序是：申請資源系統為進程分配資源使用資源釋放資源。如果申請失敗，不同的系統可能采用不同的對策：有的系統中，進程自動被阻塞、等待喚醒；有的系統給申請進程返回錯誤代碼，由申請進程等待一段時間后重試。 死死 鎖鎖操作系統第三版操作系統第三版2、死鎖的產生及原因 死鎖的產生和定義 在一組并發的進程中，如果每個進程都在等待被該組內其它進程所占有的資源，而不釋放自己占有的被其它進程所等待的資源，就會出現僵持局面，導致這些進程因一直得不到所需資源而無法執行，這種現象稱為進程死鎖，這組進程稱為死鎖進程。 死鎖的定義：死鎖是指多個并發的進程競爭資源而形成的一種僵局，若無

22、外力作用，這些進程將永遠不能再向前推進。 產生死鎖的原因 系統競爭臨界資源 進程推進順序不當操作系統第三版操作系統第三版3、產生死鎖的必要條件 互斥條件保持和等待條件 不可搶占條件循環等待條件操作系統第三版操作系統第三版4、解決死鎖的基本策略 鴕鳥策略 l象鴕鳥一樣對死鎖視而不見、不予理睬。 不允許死鎖發生l靜態策略就是預防死鎖 l動態策略就是避免死鎖 允許死鎖發生l檢測和解除 解決死鎖的基本方法有以下三種：預防死鎖避免死鎖檢測和解除死鎖 操作系統第三版操作系統第三版1、使用“任務管理器”實現進程管理 “任務管理器”提供了正在計算上運行的程序和進程的相關信息，也顯示最常用的度量進程性能的單位。

23、使用任務管理器，可以查看正在運行的程序的狀態，并終止已停止響應的程序。也可以使用多達 15 個參數評估正在運行的進程的活動，查看反映 CPU 和內存使用情況的圖形和數據。查看進程的相關信息終止進程查看進程的優先級更改進程的優先級給處理器指派進程使用“任務管理器” 的其它功能Windows系統的進程管理系統的進程管理操作系統第三版操作系統第三版2、使用Windows XP中的命令行工具實現進程管理Windows XP中的命令行工具tasklist 用來顯示應用程序和本地或遠程系統上運行的相關任 務/進程的列表，執行tasklist /? 顯示詳細的幫助信息。 Windows XP中的命令行工具t

24、askkill TASKKILL /F /IM notepad.exe /T TASKKILL /PID 1630 /PID 1641 /T Windows XP中的命令行工具ntsd命令 NTSD -C Q -P PID 操作系統第三版操作系統第三版習 題1. 畫出下面四條語句的前趨圖：S1：a=x+m；S2：b=y+n；S3：c=a+b；S4：d=c+e。 2. 程序并發執行時有哪些特征？ 3. 程序與進程之間有哪些區別和聯系？4. 進程實體由哪幾個部分組成，進程控制塊的作用是什么? 5. 進程有哪幾種基本狀態？進程是否可從阻塞狀態直接轉換到運行狀態？為什么？ 6. 并發的進程之間相互制約

25、關系有哪兩種形式？請舉例說明。7. 請舉例說明什么是臨界資源、臨界區、進程同步、進程互斥？進程同步與互斥二者之間有何關系？操作系統對臨界區的調度原則是什么？8. 為某臨界區設置一把鎖w，當w=1時，表示關鎖；w=0時，表示開鎖。請寫出開鎖原語和關鎖原語，并利用它們實現進程互斥。9. P、V操作的物理意義是什么？ 在信號量S上執行P、V操作時，S的值發生什么變化？當S0，S=0，S0時，它們的物理意義是什么？ 10. 有三個進程A、B、C，進程A通過一個緩沖區不斷地向進程B、C發送信息，A 每向緩沖區送入一個信息后，必須等進程B、C都取走后才可以發送下一個信息，B、C對A 送入的每一信息各取一次

26、，請用P、V操作實現它們之間的同步工作。操作系統第三版操作系統第三版11. 兩個并發進程的程序如下：int a=9； main( ) cobeginprocess1( );process2( );coend process1( ) while (TRUE) a=a+1； process2( ) while (TRUE) print(a)；a=0； 在process1先執行了二次循環后，process1和process2又并發執行了一次循環，會出現哪幾種情況？a的打印值應該是多少？如果要求process1必須先執行二次循環，然后process1和process2開始并發循環執行，執行時不出現與時

27、間有關的錯誤，如何用PV操作來實現？12. 設有n個進程共享一臨界區，對于下述情況，說明信號量的初值、含義，并用PV操作寫出有關進程的互斥算法：(1)一次只允許一個進程進入臨界區。(2)一次允許m(mn個進程進入臨界區。13. 某計算機機房有40臺計算機，最多可同時容納40個人上機，機房門很窄，每次只允許一個人出入。開始時機房沒有人上機。上機過程為：當機房內有40個人上機時，等待；機房有空位置時，機房門沒有人出入，就進入機房上機。上機完成后，機房門沒有人出入，就離開機房。多個上機進程可以并發執行。請用PV操作實現上機進程的同步算法。14. 請用PV操作寫出下面前趨圖的并發程序。(圖見教材P85)15. 什么是高級、低級和中級調度？