第4章 進程及進程管理

1、1 / 71第4章 進程及進程管理4.1 并發(fā)活動進程的引入4.2 進程概念4.3 進程控制4.4 進程的相互制約關系4.5 進程互斥4.6 信號燈和、V操作4.7 進程同步4.8 進程通信4.9 線程2 / 714.1.1 程序的順序執(zhí)行（一）數(shù)據(jù)、操作數(shù)據(jù)：用來表現(xiàn)人們思維對象的抽象概念的物理表現(xiàn)操作：數(shù)據(jù)處理的規(guī)則。3 / 71（二）什么是程序的順序執(zhí)行（二）什么是程序的順序執(zhí)行程序的順序執(zhí)行程序的順序執(zhí)行：4 / 71I1 I2C2C1P1P2作業(yè)1作業(yè)2圖4.1 程序段的順序執(zhí)行5 / 711、順序性：2、封閉性：3、可再現(xiàn)性： （三）順序程序的特點6 / 714.1.24.1.2程

2、序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行并發(fā)環(huán)境：并發(fā)環(huán)境： 在一定時間內物理機器上有兩個或在一定時間內物理機器上有兩個或兩個以上的程序同處于開始運行但兩個以上的程序同處于開始運行但尚未結束的狀態(tài)，并且次序不是事尚未結束的狀態(tài)，并且次序不是事先確定的。先確定的。7 / 71引入并發(fā)的目的：引入并發(fā)的目的： 并發(fā)程序：并發(fā)程序：8 / 71圖4.2 并行計算的先后次序I1I2I3I4C1C2C3P1P29 / 71例：例：圖4.2 10 / 71圖 4.311 / 71并發(fā)執(zhí)行的算法表示：1、語句表示 s0 ; cobegin S1; S2; ; Sn coend; sn+1; 12 / 712.流程圖表示。

3、s0s1s2SnSn+113 / 71例4.1 假設一個飛機訂票系統(tǒng)有兩個終端，分別運行進程T1和T2且同處于運行之中，其程序如下(類C代碼）其運行情況如圖3.1所示。T1( ) T2( ) while(未下班） while(未下班） read(x); read(x); if x=1 if x=1 x-; x-; write(x); write(x); Main( ) Cobegin T1( ); T2( ); Coend int x;圖4.44.1.3并發(fā)執(zhí)行的例子14 / 71時間時間 t0t1t2t3t4t5X 1 1 0 0 0 0T1read(x)x- -write(x) T2 re

4、ad(x)write(x)(a)時間時間 t0t1t2t3t4t5X 1 1 1 0 0 0T1read(x) x- - write(x) T2 read(x) x- - write(x)(b)15 / 71結果分析： 按照(a)的序列執(zhí)行時，系統(tǒng)中僅有的一張票售給了一位旅客，這是正確的。 按照(b)的序列執(zhí)行時，盡管T1和T2均無非法操作，但卻把一張票售給了兩位旅客。 在(b)情況下發(fā)生的錯誤，稱為 與時間有關的錯誤。16 / 71特征：（1）失去程序的封閉性（2）程序和計算不再一一對應（3）程序并發(fā)執(zhí)行時存在相互制約關系17 / 714.2 進程概念4.2.1 進程的引入和定義程序的順序執(zhí)

5、行、程序的并發(fā)執(zhí)行特征比較程序的順序執(zhí)行 程序的并發(fā)執(zhí)行1 順序性 1 間斷性2 封閉性 2 失去封閉性3可再現(xiàn)性 3 不可再現(xiàn)性18 / 7119 / 714.2.1 進程的引入 程序并發(fā)執(zhí)行時所產生的一系列新的特點是傳統(tǒng)的靜態(tài)的“程序”的概念，已不足以描述程序的并發(fā)執(zhí)行，為此引入了“進程”的概念。 進程的定義： 一個程序在給定活動空間和初始環(huán)境下，在一個處理機上的執(zhí)行過程。20 / 71定義：定義：ProcessProcess 進程是具有獨立功能的程序關于進程是具有獨立功能的程序關于某個數(shù)據(jù)集合上的一次運行活動，某個數(shù)據(jù)集合上的一次運行活動，是系統(tǒng)進行資源分配和是系統(tǒng)進行資源分配和調度調度

6、的獨立的獨立單位單位2 2、進程的定義、進程的定義21 / 7122 / 7123 / 71系統(tǒng)進程系統(tǒng)進程用戶進程用戶進程（系統(tǒng)進程優(yōu)先于用戶進程（系統(tǒng)進程優(yōu)先于用戶進程) )進程的分類進程的分類: :24 / 714.2.3 進程的狀態(tài)圖圖4.8 4.8 進程狀態(tài)變遷圖進程狀態(tài)變遷圖25 / 71進程狀態(tài)變遷（1）運行狀態(tài)：進程正在處理機上運行的狀態(tài)，該進程已獲得必要的資源，也獲得了處理機，用戶程序正在處理機上運行。（2）阻塞狀態(tài)：進程等待某種事件完成（例如，等待輸入/輸出操作的完成）而暫時不能運行的狀態(tài)，處于該狀態(tài)的進程不能參加競爭處理機，此時，即使分配給它處理機，它也不能運行。（3）就

7、緒狀態(tài)：該進程運行所需的一切條件都得到滿足，但因處理機資源個數(shù)少于進程個數(shù)，所以該進程不能運行，而必須等待分配處理機資源，一旦獲得處理機就立即投入運行。26 / 71狀態(tài)變遷的方向：（1）就緒狀態(tài)變化到運行狀態(tài) 。（2）運行狀態(tài)變化到就緒狀態(tài)。 （3）運行狀態(tài)變化到阻塞狀態(tài)。 （4）阻塞狀態(tài)變化到就緒狀態(tài)。 27 / 714.2.4 進程控制塊 為了刻畫進程的動態(tài)變化，通常把進程表示為由程序段、私有數(shù)據(jù)塊和進程控制塊組成，如圖4.9（a）所示。程序部分描述進程本身所要完成的功能，而“私有數(shù)據(jù)塊”是接受程序規(guī)定操作的一組存儲單元的內容，是操作的對象。進程控制塊是在進程創(chuàng)建時產生的，當進程存在于系

8、統(tǒng)時（運行），進程控制塊就標識了這個進程。如圖4.9（b）所示。 28 / 7129 / 71（1）進程標識符： 進程符號名或內部id號。（2）進程當前狀態(tài)： 本進程目前處于何種狀態(tài)（運行、就緒、等待）。（3）當前隊列指針next： 該項登記了處于同一狀態(tài)的下一個進程的pcb地址。（4）總鏈隊列指針all_q_next： 該項登記了在系統(tǒng)總鏈隊列中，下一個進程的pcb地址。（5）程序開始地址： 該進程的程序將從此地址開始執(zhí)行。（6）進程優(yōu)先級： 反映了進程要求CPU的緊迫程度。（7）CPU現(xiàn)場保護區(qū)： 當進程由于某種原因釋放處理機時，CPU現(xiàn)場信息被保存在pcb的該區(qū)域中。（8）通信信息： 進

9、程間進行通信時所記錄的有關信息。（9）家族聯(lián)系： 指明本進程與家族的聯(lián)系。（10）占有資源清單30 / 71運行就緒等待時間片到進程調度進程創(chuàng)建進程阻塞進程撤消31 / 7131all_q _nextnextnextnextPCBPCBPCBall_q _next總鏈隊列結構32 / 71進程控制塊是進程存在的標志，當系統(tǒng)或父進程創(chuàng)建一個進程時，實際上就是為其建立一個進程控制塊。 進程控制塊既能標識進程的存在，又能刻畫出進程的動態(tài)特征，它是一個進程僅有的被系統(tǒng)真正感知的部分。對操作系統(tǒng)而言，所有進程控制塊將構成并發(fā)執(zhí)行控制和維護系統(tǒng)工作的依據(jù)。進程控制塊的作用：進程控制塊的作用：33 / 71

10、4.3 進程控制 4.3.1 進程控制的概念 4.3.2 進程創(chuàng)建4.3.3 進程撤消4.3.4 進程等待4.3.5 進程喚醒4.3.6 進程延遲 34 / 714.3.1 進程控制的概念一、原語在操作系統(tǒng)中，某些被進程調用的操作，例如隊列操作、對鎖的操作、檢查啟動外設操作等，一旦開始執(zhí)行就不能被中斷，否則就會出現(xiàn)“與時間有關的錯誤”（如例4.1）。原語就是為實現(xiàn)這些操作而設置的。原語是一種特殊的系統(tǒng)調用命令，它可以完成一個特定的功能。其特點是原語執(zhí)行時不可中斷，所以原語操作具有原子性，它是不可再分的。35 / 71用于進程控制的原語用于進程控制的原語1創(chuàng)建原語2撤消原語3阻塞原語4喚醒原語3

11、6 / 714.3.2 進程創(chuàng)建MODULE 4.5 進程創(chuàng)建Creat(name,priority,start-addr) 在總鏈隊列上查找有無同名的進程； if (有同名進程）return (錯誤碼）； 從pcb資源池申請一個空閑的pcb結構； if （無空pcb結構） return(錯誤碼）； 用入口參數(shù)設置pcb內容； 置進程為“就緒”態(tài)； 將新進程的pcb入就緒隊列； 將新進程的pcb入總鏈隊列； return(新進程的pid); 37 / 714.3.3 進程撤消MODULE 4.6 進程撤消kill( ) 由運行指針得當前進程的pid;釋放本進程所占用得資源給父進程； 該進程從總

12、鏈隊列中摘除；釋放此pcb結構；轉進程調度程序； 用途：進程完成任務后撤消自己。38 / 714.3.4 進程等待Susp(進程等待的原因） 保護現(xiàn)行進程的CPU現(xiàn)場到pcb結構中；置該進程為“等待”態(tài)；將該進程pcb插入到指定等待隊列中去；轉進程調度； 用途：當進程需要等待某一事件完成時，它可以調用等待原語把自己掛起。39 / 714.3.5 進程喚醒MODULE 4.8 進程喚醒Wakeup(等待原因） 保護現(xiàn)行進程的CPU現(xiàn)場；置該進程為“就緒”態(tài)；將該進程入就緒隊列；找到該等待隊列原因的隊列指針；for(該隊列上第一個等待的進程） 將該進程移出此等待隊列；置該進程狀態(tài)為“就緒”；將該進

13、程入就緒隊列；轉進程調度； 用途：進程所等待的事件出現(xiàn)時，由發(fā)現(xiàn)者（合作者）用喚醒 原語喚醒它。40 / 714.4 進程的相互制約關系4.4.1 資源共享共享資源的方式由系統(tǒng)統(tǒng)一分配由程序自行使用由系統(tǒng)提供同步協(xié)調工具4.4.2 進程合作合作的方法進程通信41 / 714.5 進程互斥4.5.1 互斥的概念同步：對進程操作的時間順序所加的某種限制?；コ猓和降囊环N，多個操作決不能在同一時 刻執(zhí)行。進程互斥：兩個并行的進程A、B，如果當A進行某個操作時，B不能做這一操作，進程間的這種限制條件稱為進程互斥42 / 71臨界資源：一次僅允許一個進程使用的公共資源。即: 并發(fā)進程對其操作會使其狀態(tài)發(fā)

14、生改變的公共資源。臨界區(qū)/臨界段：進程中對公共變量（或存儲區(qū)）進行修改的程序段。即：在進程中涉及到臨界資源的程序段叫臨界區(qū)。 多個進程的相對于某一個臨界資源的臨界區(qū)稱為相關臨界區(qū) （參看教材P79圖4.13）43 / 71同步準則：1、每次至多有一個進程處于臨界區(qū)。2、進程在臨界區(qū)內僅逗留有限的時間3、當有若干進程欲進入它的臨界區(qū)時，應在有限時間內使進程進入臨界區(qū)。換言之，它們不應相互阻塞而致使彼此都不能進入臨界區(qū)。44 / 714.5.2 鎖和上鎖、開鎖操作 1 閉鎖變量 W= 0 開上鎖原語： 開鎖原語： lock(w) unlock(W) test: if (w為1） goto test

15、; W=0; else w=1; 45 / 714.5.3 用上鎖原語和開鎖原語實現(xiàn)進程互斥MODULE 4.14 進程互斥 main()ppa() ppb() int w=0; cobegin lock(w); lock(w); ppa(); csa ; csb ; PPB(); unlock(w); unlock(w); coend 46 / 71思考題：1. 前述飛機訂票系統(tǒng)例子中的“與時間有關的錯誤如何解決？47 / 714.6. 信號燈和P、V操作4.6.1 信號燈的概念信號燈的概念 信號燈是鐵路交通管理中的一種常用設備，操作系統(tǒng)中使用的信號燈正是從交通管理中引用過來的一個術語。 信

16、號燈是一個確定的二元組（s, q)，s是一個具有非負初值的整型變量，q是一個初始狀態(tài)為空的等待隊列的頭指針。整型變量S代表資源的實體或并發(fā)進程的狀態(tài)，它的值可以改變，以反映資源或并發(fā)進程狀態(tài)的改變。為了對信號等的值進行修改，一般采用稱為P、V操作的一對原語來進行。 S的物理含義為： S 0 時的值是其所代表的資源的可用數(shù)目。 S 0 時的絕對值是等待使用資源的進程數(shù)目。48 / 71P、V操作：信號燈的初值僅能由P、V操作原語加以改變。對信號燈的P、V操作分別記為p(s)、v(s),其功能如下：p(s)v(s) s-; s+; if (s0) if (sp(s)，釋放資源-v(s)6.同一信號

17、量的P 、V 操作要成對出現(xiàn)，除“互斥”情 況外，它們一般分別出現(xiàn)在不同的進程代碼中7. 寫出類C代碼8. 校驗：對同一信號量的p、v操作是否同樣多？ 各進程同步？ 53 / 71MODULE 4.18 Main() int s1=0; /* 化驗單*/ int s2=0; /* 化驗結果*/ cobegin diagnosis()labora(); while (未下班）diagnosis(); 看??； coend v(s1); p(s2);Labora() 開藥方； while (未下班） p(s1); 化驗； v(s2); 54 / 71一、合作進程的執(zhí)行次序圖的連接描述了進程間開始和結

18、束的次序約束，此圖稱為進程流圖。sfs P2fP1P1 P2 P2P3 P3 P4 P455 / 71例：Pa、Pb、Pc為一組合作進程，其進程流圖如圖4.16所示。使用信號燈的P、V操作實現(xiàn)這三個進程的同步。PaPbPc解1：main() int S = 0; /*Pa 結束否*/ cobegin Pa( ) Pb( ) Pc( ) Pa( ); P(s); P(s)Pb( ); v(s); Pc( ); coend 問：此種解法對嗎？56 / 71解2：main() int Sb = 0; /*Pb可開始否*/ int Sc = 0; /*Pc可開始否*/ cobegin Pa( ) Pb

19、( ) Pc( ) Pa( ); P(Sb); P(Sc);Pb( ); v(Sb); Pc( ); v(Sc) coend 57 / 71二、共享緩沖區(qū)的同步CPIOPbuf58 / 71MODULE 4.20Main( ) int Sa = 0; /* buf中的數(shù)據(jù)*/int Sb = 1; /* buf 中的空位置*/cobeginCP( ); IOP( ); coend CP( ) while(未完成) 計算出一個數(shù)據(jù)；P(Sb); 將數(shù)送到緩沖區(qū)中； V(Sa); IOP( ) while(未完成) P(Sa); 從緩沖區(qū)中取一數(shù)； V(Sb); 從打印機上輸出； 59 / 711

20、生產者與消費者問題 Dijkstra把廣義同步問題抽象成一種“生產者與消費者問題”（Producer-consumer-relationship）的抽象模型。事實上，計算機系統(tǒng)中的許多問題都可歸結為生產者與消費者問題，生產者與消費者可以通過一個有界緩沖區(qū)（見圖4.8）聯(lián)系起來，有界緩沖區(qū)由幾個大小相等的緩沖塊組成，每個緩沖塊容納一個產品。每個生產者可不斷地每次往緩沖區(qū)中送一個生產產品，而每個消費者則可不斷地每次從緩沖區(qū)中取出一個產品。 60 / 71.P1p2p3PmC1C2Ck圖圖4.18 4.18 生產者生產者- -消費者問題消費者問題61 / 71下面給出基于有界緩沖區(qū)的生產者與消費者關

21、系的形式描述，設：（1）互斥信號燈mutex：初值為1，用于實現(xiàn)臨界區(qū)互斥。（2）信號燈empty：初值為n，指示空緩沖塊數(shù)目。（3）信號燈full：初值為0，指示滿緩沖塊數(shù)目。（4）整型量i和j初值均為0，i指示第一塊空緩沖塊序號，j指示第一塊滿緩沖塊序號。v其同步算法設計如下： 62 / 71main() int full=0; /*滿緩沖的數(shù)目*/ int empty=n; /*空緩沖的數(shù)目*/ int mutex = 1; /*對有界緩沖區(qū)進行操作的互斥信號燈*/ cobegin producer(); consumer(); coend生產者消費者問題63 / 71生產者消費者問題（

22、續(xù)）Producer( ) consumer( ) while(生產未完成） while(還要消費） p(full);生產一個產品； p(mutex); p(empty); 從緩沖區(qū)中取產品； p(mutex); v(mutex); 送一個產品到緩沖區(qū)； v(empty); v(mutex); v(full); 消費一個產品； 64 / 71例 題用PV操作解決下面問題：司機進程：Repeat啟動車輛；正常行駛；到站停車；Until 售票員進程：Repeat關門；售票；開門；Until 65 / 7165同步要求：先關門，后開車；同步要求：先關門，后開車； 先停車，后開門；先停車，后開門；信號

23、燈：信號燈：S_Door, 初值為初值為0 S_Stop, 初值為初值為0司機進程：司機進程：Begin RepeatP(S_Door);啟動；啟動；駕駛；駕駛；停車；停車；V(S_Stop); Until false;End售票員進程：售票員進程：Begin Repeat關門；關門；V(S_Door);售票；售票；P(S_Door);開門；開門； Until false；End66 / 7166補充題：有十個讀者和兩個編輯同時處理一篇文章，對于讀操作是可以同時進行的；若有讀者正在讀，編輯就不能工作；若編輯正在處理，讀者就不能讀，編輯與編輯的工作也是互斥的，試用信號燈及P、V操作描述讀者與編輯

24、之間協(xié)同工作，并給出類C程序。67 / 7167main（）（） int mutex=1，couter=0； cobegin readi（）；（）；(i=1-10) editerj（）；（）；(j=1,2) coend readi() if(couter = = 0) p(mutex); couter +; 讀文章；讀文章； couter -; if(couter = 0) v(mutex); editerj() p(mutex); 處理文章處理文章; v(mutex); mutexmutex：互斥信：互斥信號燈，初值為號燈，初值為1 1。一種解法，一種解法，正確嗎？正確嗎？68 / 71讀者

25、、編輯問題正解mutex:用于讀者與編輯、編輯與編輯的互斥信號燈，初值為1mutex1:用于對couter操作的互斥的信號燈，初值為1。6869 / 7169main（）（） int mutex1= mutex=1， couter=0； cobegin readi（）；（）； editeri（）；（）； coend readi() p(mutex1); couter +; if (couter = = 1) p(mutex); v(mutex1); 讀文章；讀文章； p(mutex1); couter -; if (couter = 0) v(mutex); v(mutex1); editj(

26、) p(mutex); 處理文章處理文章; v(mutex); 70 / 71(六)線程的基本概念在OS中，進程的引入提高了系統(tǒng)資源的利用率。進一步提高進程的并發(fā)性時產生問題：n進程切換開銷越來越大n進程間通信效率受限n多處理機系統(tǒng)調度71 / 71在只有進程概念的操作系統(tǒng)中進程是：系統(tǒng)資源分配的單位處理器調度的對象在引入線程的操作系統(tǒng)中：n線程是處理機調度的對象；n進程是系統(tǒng)資源的分配單位；n一個進程可同時具有多個線程。72 / 71(六)線程的基本概念1. 什么是線程線程是比進程更小的活動單位，它是進程中的一個執(zhí)行路徑。線程可以這樣來描述：n進程中的一條執(zhí)行路徑；n它有自己私用的堆棧和處理

27、機執(zhí)行環(huán)境；n它與父進程共享分配給父進程的主存；n它是單個進程所創(chuàng)建的許多個同時存在的線程中的一個。73 / 712. 線程的特點n創(chuàng)建一個線程比創(chuàng)建一個進程開銷要小得多。n線程（Thread）是一個動態(tài)的對象，是處理機調度的基本單位，表示一個進程中的一個控制點，執(zhí)行一系列的指令。n實現(xiàn)線程間通信十分方便，因為一個進程創(chuàng)建的多個線程可以訪問整個進程的所有資源，包括共享地址區(qū)域和數(shù)據(jù)，因此，線程間通信比較簡單方便。n在進程內創(chuàng)建多線程，可以提高系統(tǒng)的并行處理能力，加快進程的處理速度。n同一個進程中線程切換簡單。進程中所有線程是共享一個進程圖像的。74 / 71單進單進程程單進單進程程多線多線程程

28、多進程多進程 單線程單線程每個進程只有一個線每個進程只有一個線程程多進程多進程 多線程多線程每個進程只有多個線每個進程只有多個線程程75 / 71線程的實現(xiàn)機制內核線程（內核線程（Kernel-Level Thread）n在OS內核完成創(chuàng)建、撤消、執(zhí)行一個指定的函數(shù)線程。n在支持內核線程OS中，內核維護進程和線程上下文，線程切換由內核完成。處理機分配對象是線程。某個線程因中斷阻塞不影響其它線程的執(zhí)行。n多線程的進程可獲得更多的處理機時間。Windows Server 2003支支持內核線程。持內核線程。用戶線程用戶線程（User-Level Thread）n不依賴OS核心，由應用進程利用線程庫

29、提供創(chuàng)建、同步、調度和管理線程。n由于不需要操作系統(tǒng)支持，任何操作系統(tǒng)都可以支持。甚至單用戶操作系統(tǒng)。76 / 71線程實現(xiàn)的機制 輕量級進程輕量級進程（Light weight process） 由內核支持的用戶線程。一個進程可有一個或多個輕量級進程。每個輕量級進程由一個單獨的內核線程來支持。由于同時提供內核線程控制機制和用戶線程庫，可以很好地把內核線程和用戶線程的優(yōu)點結合起來。77 / 71概述概述消息緩沖通信方式消息緩沖通信方式4.7.4 4.7.4 進程通信進程通信78 / 711 1、概述、概述 P.V P.V操作實現(xiàn)的是進程之間的低級通訊，所以操作實現(xiàn)的是進程之間的低級通訊，所以P.VP.V為為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息換大量信息如果要在進程間傳遞大量信息則要用如果要在進程間傳遞大量信息則要用 Send / Receive Send / Receive原語（高級通訊原語）原語（高級通訊原語）79 / 71共享內存共享內存： 相互通信的進程間設有公共相互通信的進程間設有公共內存，一組進程向該公共內存中寫，另內存，一組進程向該公共內存中寫，另一組進