1、第二章 進(jìn)程管理,第二章 進(jìn)程管理,2.1進(jìn)程的基本概念,2.2 進(jìn)程控制,2.3 進(jìn)程同步,2.7 線程的基本概念,2.4經(jīng)典進(jìn)程同步問題,2.5管程機(jī)制,2.6進(jìn)程通信,2.1 進(jìn)程的基本概念,1) 程序的順序執(zhí)行與并發(fā)執(zhí)行 前驅(qū)圖 程序的順序執(zhí)行 特征：順序性-操作按程序規(guī)定順序執(zhí)行 封閉性-獨占全機(jī)資源，不受外界影響 可再現(xiàn)性-只要執(zhí)行環(huán)境相同，初始條件相 同，程序反復(fù)執(zhí)行時結(jié)果相同,Pi是Pj的前趨，Pj是Pi的后繼,程序的并發(fā)執(zhí)行,并發(fā)執(zhí)行的特征： 間斷性 失去封閉性 不可再現(xiàn)性,觀察者 begin repeat wait for a car through N=N+1 until

2、 end,報告者 begin repeat delay print N N=0 until end,初始N=n時不同執(zhí)行序列，結(jié)果各不相同,例子：觀察者與報告者,打印n+1,N=0,打印n, N=1,打印n, N=0,2) 進(jìn)程（process）的定義與特征 描述：本質(zhì)上來說一個進(jìn)程就是一個執(zhí)行的程序，是一個具有獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程，是計算機(jī)資源的使用主體，擁有獨立的地址空間。 定義：進(jìn)程實體的運(yùn)行過程，是OS進(jìn)行資源分配和調(diào)度 的基本單位。 特征 結(jié)構(gòu)特征- 進(jìn)程實體=程序段+數(shù)據(jù)段+進(jìn)程控制塊(PCB) 動態(tài)性- 進(jìn)程是進(jìn)程實體的一次執(zhí)行過程，進(jìn)程要經(jīng)歷 “發(fā)生

3、，發(fā) 展和消亡”的動態(tài)變化過程。 并發(fā)性- 在一個時間間隔內(nèi)多個進(jìn)程同時運(yùn)行。 獨立性- 獨立運(yùn)行，獨立分配資源和獨立接受調(diào)度。 異步性- 按各自獨立的不可預(yù)知的速度向前推進(jìn), 程序與進(jìn)程之區(qū)別,3) 進(jìn)程的狀態(tài)及其轉(zhuǎn)換 三種基本狀態(tài)及其轉(zhuǎn)換： 就緒狀態(tài)-已經(jīng)獲得所需資源，只等待CPU，所有處在就緒狀態(tài)的進(jìn)程排在就緒隊列上。 執(zhí)行狀態(tài)-正在運(yùn)行中。 阻塞狀態(tài)-進(jìn)程等待某個事件，如等待I/O完成，等待某個資源，處于暫停狀態(tài)。所有處在阻塞狀態(tài)的進(jìn)程排在隊列上(一個或多個隊列)。 此外還可以有新建態(tài)和終止態(tài)。,進(jìn)程狀態(tài)的轉(zhuǎn)換,新建,終止,就緒,阻塞,運(yùn)行,創(chuàng)建完畢,時間片用完,結(jié)束執(zhí)行,選中,等待事

4、件,等待結(jié)束,具有掛起狀態(tài)的狀態(tài)圖,引起掛起狀態(tài)的原因： 終端用戶的需要-暫停執(zhí)行，查清問題。 父進(jìn)程的需求-考查和修改子進(jìn)程，或要協(xié)調(diào)各子進(jìn)程間的活動。 操作系統(tǒng)的需要-檢查運(yùn)行中資源的使用情 況及進(jìn)行記帳，以便改善系統(tǒng)運(yùn)行的性能。 負(fù)荷調(diào)節(jié)的需要-當(dāng)實時系統(tǒng)中工作負(fù)荷較重影響對實時任務(wù)的控制時，系統(tǒng)把一些不重要的進(jìn)程掛起，以保證系統(tǒng)正常運(yùn)行。,4) 進(jìn)程控制塊（PCB）Process Control Block,PCB：由系統(tǒng)維護(hù)用于記錄進(jìn)程基本情況信息，以對進(jìn)程實施控制與管理的輔助數(shù)據(jù)結(jié)構(gòu)（表）， PCB是進(jìn)程存在與否的唯一標(biāo)志，每個進(jìn)程在系統(tǒng)中都有相應(yīng)的PCB，內(nèi)容隨進(jìn)程的運(yùn)行而動態(tài)改

5、變，而且PCB處于系統(tǒng)核心，通常不能由應(yīng)用程序直接訪問。作用是使多道程序環(huán)境中不能獨立運(yùn)行的程序成為一個能獨立運(yùn)行的基本單位 PCB包含的內(nèi)容,PCB中一般包括進(jìn)程描述信息、處理器狀態(tài)信 息、進(jìn)程調(diào)度信息和進(jìn)程控制信息4部分。 具體 內(nèi)容見下頁：,進(jìn)程標(biāo)識符信息,處理機(jī)狀態(tài)信息,進(jìn)程調(diào)度信息,進(jìn)程控制信息,內(nèi)部標(biāo)識符,外部標(biāo)識符,通用寄存器指令計數(shù)器程序狀態(tài)字用戶棧指針,進(jìn)程狀態(tài),進(jìn)程優(yōu)先級,事件,其它信息,程序和數(shù)據(jù)的地址,進(jìn)程同步和通信機(jī)制,資源清單,PCB,PCB的組織方式(邏輯結(jié)構(gòu)） 將處于同一狀態(tài)的進(jìn)程組織在一起 鏈接方式 同一狀態(tài)的進(jìn)程其PCB成一鏈表，多個狀態(tài)對應(yīng)多個不同的鏈表,

6、索引方式 同一狀態(tài)的進(jìn)程歸入一個index表（由index指向PCB）， 多個狀態(tài)對應(yīng)多個不同的index表,2.2 進(jìn)程控制,進(jìn)程控制：進(jìn)程的創(chuàng)建、撤消，進(jìn)程狀態(tài)轉(zhuǎn)換的控 制。進(jìn)程控制由進(jìn)程控制原語和系統(tǒng)調(diào)用等在OS內(nèi)核中實現(xiàn)，是OS進(jìn)程管理的最基本功能。 進(jìn)程創(chuàng)建 進(jìn)程終止 進(jìn)程的阻塞與喚醒 進(jìn)程的掛起與激活 注：內(nèi)核：OS的核心層部分，包括中斷處理、時鐘管理 原語：OS內(nèi)核中能完成某特定功能的小程序，其在執(zhí)行期間不 允許被分割,進(jìn)程創(chuàng)建 進(jìn)程圖：描述進(jìn)程之間的創(chuàng)建關(guān)系的有向樹 子進(jìn)程可以繼承父進(jìn)程擁有的資源，撤銷父進(jìn)程時同時撤銷其所有子進(jìn)程, 父子進(jìn)程并發(fā)執(zhí)行，父進(jìn)程等待子進(jìn)程執(zhí)行結(jié)束,

7、引起進(jìn)程創(chuàng)建的相關(guān)事件（因素） 用戶登陸（在分時系統(tǒng)中） 作業(yè)調(diào)度（在批處理系統(tǒng)中） 提供服務(wù)（用戶提出請求） 應(yīng)用請求（用戶程序引發(fā)） 進(jìn)程創(chuàng)建步驟及算法流程（創(chuàng)建原語調(diào)用Create() ） 為新進(jìn)程分配空白PCB表 初始化PCB，分配資源，填入相關(guān)數(shù)據(jù) 置PCB狀態(tài)為就緒 PCB插入就緒隊列，插入進(jìn)程家族樹,進(jìn)程終止 引起進(jìn)程終止的因素 進(jìn)程正常運(yùn)行結(jié)束 出錯或異常結(jié)束 外界干預(yù)，強(qiáng)行終止 進(jìn)程終止的步驟及過程（終止原語） 若被終止進(jìn)程正在執(zhí)行，則釋放CPU 終止（撤消）該進(jìn)程的所有子進(jìn)程 釋放資源，歸還給父進(jìn)程或系統(tǒng) 將其PCB從相關(guān)隊列中摘除，釋放PCB,進(jìn)程阻塞與喚醒 引起進(jìn)程阻塞

8、（喚醒）的因素 請求系統(tǒng)服務(wù) （請求得到滿足） 啟動某種操作 （操作完成） 等待新數(shù)據(jù)到達(dá) （新數(shù)據(jù)已送達(dá) ） 進(jìn)程完成任務(wù)，暫無事可做 （又有新任務(wù)） 進(jìn)程阻塞的步驟及過程（阻塞或睡眠原語） 暫停執(zhí)行，釋放CPU 置再（重新）調(diào)度標(biāo)志 保存CPU現(xiàn)場信息 置PCB狀態(tài)為阻塞，PCB插入對應(yīng)阻塞隊列 進(jìn)程喚醒的步驟及過程（喚醒原語） 將被喚醒進(jìn)程PCB從阻塞隊列中摘除 置PCB狀態(tài)為就緒 將PCB插入就緒隊列 注：阻塞為自行操作，喚醒為他人行為。,2.3 進(jìn)程同步,進(jìn)程同步和互斥的相關(guān)概念 進(jìn)程同步：多個進(jìn)程中發(fā)生的事件存在某種時序關(guān)系，必須協(xié)同工作、相互配合，以共同完成一項任務(wù)。 進(jìn)程互斥：

9、由于共享資源所要求的排他性，進(jìn)程間要相互競爭，以獲得這些資源的使用權(quán)。 臨界資源（獨占資源）：指在一段時間內(nèi)只允許一個進(jìn)程訪問的資源。其中訪問臨界資源所對應(yīng)的程序段叫臨界區(qū)。 注：有些共享資源可以同時訪問則不是臨界資源，如只讀數(shù)據(jù)。,進(jìn)程間的同步 司機(jī)和售票員的同步,正常行駛,開車,到站停車,關(guān)車門,開車門,售票員,售票,司機(jī),進(jìn)程的互斥 互斥使用資源,進(jìn)程A,（阻塞）,請求資源R,進(jìn)程B,請求資源R,R,練習(xí)：進(jìn)程之間存在哪幾種制約關(guān)系？各是什么原因引起的？下列活動分別屬于哪種制約關(guān)系？ 若干同學(xué)去圖書館借書； 兩隊舉行籃球比賽； 流水線生產(chǎn)的各道工序； 商業(yè)生產(chǎn)和社會消費(fèi)。,答案：進(jìn)程間存

10、在直接制約和間接制約兩種制約關(guān)系，其中直接制約（同步）是由于進(jìn)程間的相互合作引起的；間接制約（互斥）是由于進(jìn)程間共享臨界資源引起的。 是間接制約，其中書是臨界資源 是間接制約，其中籃球是臨界資源 是直接制約，因為各道工序需要相互合作 是直接制約，因為兩者也需要合作：商品生產(chǎn)出來后才能被消費(fèi)；消費(fèi)后才需要再生產(chǎn),臨界資源與臨界區(qū)（ critical section ）,進(jìn)程的互斥 （間接作用）,由于現(xiàn)在操作系統(tǒng)中的進(jìn)程是并發(fā)執(zhí)行的，各進(jìn)程以自己的速度向前推進(jìn)，所以，運(yùn)行的順序可能是： P1：R1 = count； P2：R2 = count； P1：R1 = R1 + 1； P1：count =

11、 R1； P2：R2 = R2 +1； P2：count = R2；,錯誤：P1,P2 執(zhí)行的結(jié)果count只加了1,臨界區(qū),剩余部分,進(jìn)入代碼,退出代碼,Dijkstra在1965年提出了三條準(zhǔn)則： （1）每次至多一個進(jìn)程處于臨界區(qū) （2）若有多個進(jìn)程同時要求進(jìn)入它們的臨界區(qū)，應(yīng)該在有限的時間內(nèi)讓其中一個進(jìn)入而不應(yīng)該相互阻塞 （3）進(jìn)程在臨界區(qū)中逗留有限時間,臨界區(qū)的訪問,進(jìn)程同步及其應(yīng)遵守的規(guī)則 同步機(jī)制是指為實現(xiàn)對臨界資源互斥訪問的機(jī)制。所有的同步機(jī)制都應(yīng)遵循四條準(zhǔn)則： 空閑讓進(jìn) 忙則等待 有限等待 讓權(quán)等待,（有效利用資源）,（對資源互斥訪問）,（避免陷入“死等”狀態(tài)）,（避免陷入“忙

12、等”狀態(tài)）,2) 信號量機(jī)制,整型信號量 記錄型信號量 AND型信號量 信號量集,整形信號量 Dijkitra把整型信號量定義為一個整型量s。除初始化外，僅 能通過兩個標(biāo)準(zhǔn)的原子操作即P操作wait(s)和V操作signal(s) 來訪問。 wait和signal操作可描述為： wait(s)：while s0 do no-op s:s一1； signal(s)：s:s十1； 注意： S表示空閑資源數(shù)，P操作申請一個資源,V操作釋放一個資源。 缺點: “忙等”，只要s0就不斷測試，未遵循“讓權(quán)等待” 。 P.V操作必須為原子操作 P.V操作必須成對出現(xiàn)。,記錄型信號量機(jī)制 增加一個進(jìn)程鏈表L，

13、將等待同一臨界資源的進(jìn)程鏈成鏈表,注意： S.V 0 表示某類可用資源的數(shù)量 =0 其絕對值表示因請求該資源而被阻塞的進(jìn)程數(shù) S.V的初值為1時，表示只允許一個進(jìn)程訪問臨界資源，此時的信號量轉(zhuǎn)化為互斥信號量；實現(xiàn)進(jìn)程間的同步時，S.V初始值通常設(shè)為0或n。 利用信號量S和上述P,V操作實現(xiàn)進(jìn)程互斥時S.V的初值置為1的過程如下：,AND型信號量 將進(jìn)程在整個運(yùn)行過程中所需要的所有臨界資源，一次性地全部分配給進(jìn)程，待該進(jìn)程使用完后在一起釋放。對若干個臨界資源的分配，采取原子操作方式，要么全部分配到進(jìn)程，要么一個也不分配。 信號量集 基于P,V只能對信號量施以增1或減1的操作，當(dāng)需要N個資源時要執(zhí)

14、行N次很低效。于是每次分配之前測試該資源的數(shù)量是否大于申請的資源數(shù)，通過對AND信號量機(jī)制進(jìn)行兩方面擴(kuò)充，形成一般化的“信號量集”機(jī)制。,用P、V操作解決進(jìn)程間同步問題,用P，V操作實現(xiàn)進(jìn)程同步的模型,P1是P2的前趨，P2是P1的后繼,利用信號量與P.V操作實現(xiàn)生產(chǎn)者-消費(fèi)者進(jìn)程同步問題,解答：單緩沖區(qū)、一個生產(chǎn)者和一個消費(fèi)者：設(shè)置私 用信號量為S1，S2，初值為1，0,生產(chǎn)者進(jìn)程P while(true) 生產(chǎn)一件產(chǎn)品; P(S1);/*申請一個空緩沖區(qū)*/ 放入一件產(chǎn)品； V(S2); /*釋放緩沖區(qū)*/ ,消費(fèi)者進(jìn)程Q while(true) P(S2); /*申請一個滿緩沖區(qū)*/ 拿

15、出一件產(chǎn)品; V(S1); 消費(fèi)產(chǎn)品; ,用P，V操作實現(xiàn)司機(jī)售票員同步 解答：設(shè)置信號量S車，S門，初值均為0,司機(jī)進(jìn)程 while(true) 正常行駛； 到站停車； V(S門); P(S車); 離站開車； ,售票員進(jìn)程 while(true) 售票； P(S門); 開車門； 關(guān)車門； V(S車); ,注：司機(jī)到站-想繼續(xù)開車阻塞,附：P，V操作所實現(xiàn)的司機(jī)售票員同步過程,司機(jī)售票員同步過程（續(xù)）：,注：司機(jī)到站-想繼續(xù)開車阻塞-售票員開車門,注：司機(jī)到站-想繼續(xù)開車阻塞-售票員開車 門-想繼續(xù)開車門阻塞,司機(jī)售票員同步過程（續(xù)）：,注：司機(jī)到站-想繼續(xù)開車阻塞-售票員開車 門-想繼續(xù)開車

16、門阻塞-司機(jī)繼續(xù)行車,司機(jī)售票員同步過程（續(xù)）：,用P、V操作解決進(jìn)程間互斥問題,（設(shè)信號量:s=1）,申請進(jìn)入臨界區(qū),退出臨界區(qū),用P，V操作實現(xiàn)進(jìn)程互斥的模型,用P，V操作解決共享count變量的問題,執(zhí)行序列：P2,執(zhí)行序列：P2（就緒）-P1（阻塞）-,用P，V操作解決共享count變量的問題（續(xù)）,執(zhí)行序列：P2（就緒）-P1（阻塞）- P3（阻塞）,用P，V操作解決共享count變量的問題（續(xù)）,執(zhí)行序列：P2（就緒）-P1（阻塞）- P3（阻塞）- P2,用P，V操作解決共享count變量的問題（續(xù)）,執(zhí)行序列：P2（就緒）-P1（阻塞）- P3（阻塞）- P2-P1,用P，V操

17、作解決共享count變量的問題（續(xù)）,執(zhí)行序列：P2（就緒）-P1（阻塞）- P3（阻塞）- P2-P1-P3,信號量變化范圍：, 即（-n）,用P，V操作解決共享count變量的問題（續(xù)）,2.4 經(jīng)典的進(jìn)程同步問題,生產(chǎn)者-消費(fèi)者問題,解析：n個緩沖區(qū)、k個生產(chǎn)者和m個消費(fèi)者：增加互斥信號量mutex，初值為1，并設(shè)S1，S2，初值分別為n和0。,生產(chǎn)者進(jìn)程P while(true) 生產(chǎn)一件產(chǎn)品; P(S1);/*申請一個空緩沖區(qū)*/ P(mutex); 放入一件產(chǎn)品； V(mutex); V(S2); /*釋放緩沖區(qū)*/ ,消費(fèi)者進(jìn)程Q while(true) P(S2); /*申請一

18、個滿緩沖區(qū)*/ P(mutex); 拿出一件產(chǎn)品; V(mutex); V(S1); 消費(fèi)產(chǎn)品; ,兩個P操作交換？,讀者-寫者問題 對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個“讀寫”互斥，“寫寫”互斥，“讀讀”允許 分 析：寫進(jìn)程之間互斥，訪問時必須獨占資源。需設(shè)置一個全局變量對讀進(jìn)程進(jìn)行計數(shù)，當(dāng)?shù)谝粋€讀進(jìn)程開始進(jìn)行訪問時執(zhí)行P操作，當(dāng)最后一個讀進(jìn)程結(jié)束訪問時執(zhí)行V操作。,解析：現(xiàn)假設(shè)讀者優(yōu)先。使用readnum對讀者計數(shù)，初值為0；mutex是對readnum進(jìn)行互斥操作的信號量，初值為1；write是寫信號量，初值為1。,讀者進(jìn)程 begin P(mute

19、x); readnum=readnum+1; if (readnum=1) P(write); V(mutex); read file; P(mutex); readnum=readnum1; if (readnum=0) V(write); V(mutex); end,寫者進(jìn)程 begin P(write); write file; V(write); end,第一個讀者來執(zhí)行P操作,最后一個讀者來執(zhí)行V操作,小結(jié)：信號量及P.V操作,信號量（Semaphore）:表示資源的實體，是一個與隊列有關(guān)的整型變量，其值僅能由P、V操作改變。 信號量類型：互斥/公用信號量和同步/私用信號量 互斥信號

20、量:用于實現(xiàn)進(jìn)程間的互斥。初值通常設(shè)為1，它所聯(lián)系的一組并行進(jìn)程均可對它實施P、V操作。 同步信號量：用于實現(xiàn)進(jìn)程間的同步，初始值通常設(shè)為0或n，允許擁有它的進(jìn)程對其實施P操作。,對P，V操作的使用應(yīng)注意： P原語相當(dāng)于進(jìn)入?yún)^(qū)操作，V相當(dāng)于退出區(qū)操作；遺忘P不能保證互斥訪問，遺忘V不能在使用后將資源釋放給其他等待的進(jìn)程； P，V操作都是成對出現(xiàn)的：互斥操作時，它們在同一進(jìn)程中；同步操作時，它們處于不同的進(jìn)程。 在進(jìn)程中，P操作的位置和次序至關(guān)重要。一般情況下，對互斥信號量的P操作在后。而V操作沒有特別的限制。,2.5 進(jìn)程通信 低級通信：只傳送少量數(shù)據(jù)，且對用戶不透明 高級通信：可傳送大量信息

21、、數(shù)據(jù)，由O.S提供通信手段 并實施，對用戶來說透明 1) 高級進(jìn)程通信類型 共享存儲器系統(tǒng) 消息傳遞系統(tǒng) 管道通信系統(tǒng),共享存儲器系統(tǒng) 通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)，進(jìn)行通信。可分為： 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 例如：生產(chǎn)者-消費(fèi)者問題。屬低級通信 基于共享存儲區(qū)的通信方式 共享非格式化的存儲區(qū)，公用的地址空間。屬高級通信方式。 消息傳遞系統(tǒng) 進(jìn)程間的數(shù)據(jù)交換以格式化的消息(measege)為單位，通過 利用OS提供的通信原語進(jìn)行通信，可分為： 直接通信方式-信息直接傳遞給接收方。 間接通信方式-發(fā)送進(jìn)程將消息發(fā)送到某種中間實體 中，接收進(jìn)程從中取得消息。,管道通信 工作原理：利用管道

22、進(jìn)行數(shù)據(jù)傳送,注：類似生產(chǎn)者消費(fèi)者問題，要注意同步互斥的控制,2) 消息通信的實現(xiàn)方法 消息緩沖通信（直接通信方式） 工作原理：,相關(guān)數(shù)據(jù)結(jié)構(gòu) 消息結(jié)構(gòu)： 消息緩沖隊列： PCB中用于消息通信的相關(guān)數(shù)據(jù)項,消息緩沖區(qū)鏈成的隊列，每個進(jìn)程都有 一個，其隊首指針存放在對應(yīng)進(jìn)程的PCB中,消息發(fā)送原語和接收原語 發(fā)送原語 send（接收進(jìn)程名，發(fā)送區(qū)首地址） 接收原語 receive（接收區(qū)地址） 注：緩沖隊列的插入、刪除操作必須采取互斥措施, 發(fā)送原語算法流程, 接收原語算法流程,信箱通信（間接通信方式） 工作原理 信箱頭：信箱描述部分 信箱體：數(shù)據(jù)（消息）存放部分 信箱類型：私用信箱 共享信箱 公用信箱,2.6 線程,進(jìn)程特征回顧 進(jìn)程：可獨立運(yùn)行并擁有資源的基本單位，進(jìn)程是可由O.S調(diào)度和分派的基本單位，同時也是可擁有系統(tǒng)資源的獨立單位。 線程的引入 線程：由進(jìn)程