進(jìn)程管理解析

1、 在多道程序的環(huán)境中，系統(tǒng)中的多個進(jìn)程可 以并發(fā)執(zhí)行，同時它們又要共享系統(tǒng)中的資源， 這些資源有些是可共享使用的，如磁盤，有些是 以獨占方式使用的，如打印機。由此將會引起一 系列的矛盾，產(chǎn)生錯綜復(fù)雜的相互制約的關(guān)系。 產(chǎn)生這種錯綜復(fù)雜的相互制約關(guān)系的原因有二： 資源共享 進(jìn)程合作 進(jìn)程的相互制約關(guān)系 第1頁/共63頁 2.4 進(jìn)程互斥 2.4.1 互斥的概念 引例： 宿舍電話的使用 打印機的使用 1. 臨界資源：一次僅允許一個進(jìn)程使用的資源 稱為臨界資源。 引例中的電話和打印機都屬于臨界資源。 除此之外，還有內(nèi)存變量、指針、數(shù)組等等也 是臨界資源。 第2頁/共63頁 2、臨界區(qū)： 每個進(jìn)程中訪

2、問臨 界資源的那段程序段稱 為臨界區(qū)（臨界段）。 第3頁/共63頁 互斥 定義定義: : 在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某臨界 區(qū)時，就不允許其它進(jìn)程進(jìn)入，否則就會發(fā)生( 后果)無法估計的錯誤。我們把進(jìn)程之間的這種 相互制約的關(guān)系稱為互斥。 例如：飛機定票系統(tǒng)中的機票庫 第4頁/共63頁 進(jìn)入臨界區(qū)的準(zhǔn)則： (1)每次至多有一個進(jìn)程處于臨界區(qū)； (2)當(dāng)有若干個進(jìn)程欲進(jìn)入臨界區(qū)時，應(yīng)在有限 的時間內(nèi)使其進(jìn)入； (3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時間。 第5頁/共63頁 解決進(jìn)程互斥的最簡單的辦法是加鎖。 在系統(tǒng)中為每個臨界資源設(shè)置一個鎖位， 0 表示資源可用， 1 表示資源已被占用（不可用）。

3、 這樣當(dāng)一個進(jìn)程使用某個臨界資源之前必須完成下列操作： 1、考察鎖位的值； 2、若原來的值是為“0”，將鎖位置為“1”（占用該資源）； 3、若原來值是為“1”，（該資源已被別人占用），則轉(zhuǎn)到1。 當(dāng)進(jìn)程使用完資源后，將鎖位置為“0 ” ，稱為開鎖操 作。 2.4.2 鎖和上鎖、開鎖操作 第6頁/共63頁 第7頁/共63頁 改進(jìn)的算法 第8頁/共63頁 2.4.3 用上鎖原語和開鎖原語實現(xiàn)互斥 設(shè)有兩個進(jìn)程共享 打印機，兩個進(jìn)程中使 用打印機的程序段為臨 界區(qū)。 為保證打印的正確 ，設(shè)置打印機的鎖位 print,其初值為“0”， 表示打印機可用。 第9頁/共63頁 第10頁/共63頁 2.5 信

4、號燈和P、V操作 信號燈的概念是由Dijkstra提出的（1968）。 把互斥的關(guān)鍵概念抽象到信號量這個概念中 ，信號量是一個被保護(hù)的變量，只有P操作、V操 作和一種稱為信號量初始化操作才能訪問和改變 它的值。 2.5.1 信號燈的概念 第11頁/共63頁 信號燈是一個確定的二元組（s,q），s 是一個 具有非負(fù)初值的整型變量，q是一個初始狀態(tài)為 空的隊列。 S代表資源的實體。在實際應(yīng)用中應(yīng)準(zhǔn)確地說 明s的意義和初值，每個信號燈都有一個隊列， 其初始狀態(tài)為空。 信號燈的定義： 第12頁/共63頁 2.5.2 P、V操作 信號燈的值僅能由P、V操作來改變， 對信號燈的P操作記為：P(S)，P操作

5、是一個原 子操作。 對信號燈的V操作記為：V(S), V操作是一個原 子操作。 在實際操作系統(tǒng)中，一般情況下是由機器硬件 提供P、V操作的指令，當(dāng)然是原子操作，若機器 不提供P、V操作的指令，則操作系統(tǒng)提供P、V操 作原語。 第13頁/共63頁 P操作： （1）s值減1； （2）若相減結(jié)果大于等于0， 則進(jìn)程繼續(xù)執(zhí)行； （3）若結(jié)果小于0，則該進(jìn)程 掛起。 注：推起該進(jìn)程包括：保留調(diào) 用進(jìn)程CPU現(xiàn)場；置“等待” 狀態(tài)；入等待隊列；轉(zhuǎn)進(jìn)程調(diào) 度； 第14頁/共63頁 V操作： （1）s值加1； （2）若相加結(jié)果大于0， 進(jìn)程繼續(xù)執(zhí)行； （3）否則，喚醒一個（ 或多個）等待該信號燈的 進(jìn)程，然后

6、本進(jìn)程繼續(xù)執(zhí) 行。 第15頁/共63頁 2.5.3 用信號燈實現(xiàn)進(jìn)程互斥 用兩個進(jìn)程共享打印機的例子 設(shè)信號燈print表示打印機，初值為1， 表示打印機可用(也可理解為有一臺打印機)。 (print也是用于互斥的信號燈，教材上設(shè)置為 mutex。) 第16頁/共63頁 第17頁/共63頁 2.6進(jìn)程同步 2.6.1 同步的例子 引例 1.兩位同學(xué)約 好星期天去東湖， 早上8:00在校門口 ，不見不散。當(dāng)一 個同學(xué)先來到校門 口，要等另一個同 學(xué)，到齊后一道打 的去東湖。 第18頁/共63頁 2.6.2 同步的概念 互斥的概念來自于諸進(jìn)程對獨占使用資源（設(shè) 備）的競爭，同步來源于多個進(jìn)程的合作

7、。在人類 社會中競爭與合作是永恒的。 同步：所謂同步就是并發(fā)進(jìn)程在一些關(guān)鍵點上可能 需要相互等待與互通消息，這樣的相互制約關(guān)系稱 為進(jìn)程同步。 第19頁/共63頁 2.6.3 用信號燈實現(xiàn)進(jìn)程的同步 在操作系統(tǒng)中，同步有各種各樣，但歸納起來 有兩類： 諸進(jìn)程合作完成某工作的邏輯順序； 對系統(tǒng)資源的共享。如兩個進(jìn)程共享一個緩沖區(qū) 完成謄抄問題 第20頁/共63頁 （一）合作進(jìn)程的執(zhí)行次序 用進(jìn)程流圖來描述諸進(jìn)程合作完成某一任務(wù) 的次序，其規(guī)則如下： 第21頁/共63頁 用信號燈及P、V操作來描述左圖 1、說明進(jìn)程的同步關(guān)系 進(jìn)程P1、P2可并行執(zhí)行，P3的執(zhí) 行必須等待P1、P2都完成后才能開

8、始執(zhí)行。 2、設(shè)置信號燈，說明含義、初值。 s13 = 0 表示進(jìn)程P1尚未執(zhí)行完成； s23 = 0 表示進(jìn)程P2尚未執(zhí)行完成； 第22頁/共63頁 第23頁/共63頁 思考1 司機進(jìn)程： while(1) 啟動車輛 正常駕駛 到站停車 售票員進(jìn)程： while(1) 關(guān)門 售票 開門 用P.V操作解決司機與售票員的問題 第24頁/共63頁 解 設(shè)有兩個信號量S1，S2，初值均為0。 司機進(jìn)程： while(1) P(S1) 啟動車輛 正常駕駛 到站停車 V(S2) 售票員進(jìn)程： while(1) 關(guān)門 V(S1) 售票 P(S2) 開門 第25頁/共63頁 (二）共享緩沖區(qū)的合作進(jìn)程的同步

9、 設(shè)有一個緩沖區(qū)buffer，大小為 一個字節(jié)，CP進(jìn)程不斷產(chǎn)生字符， 送buffer，IOP進(jìn)程從buffer中取出字 符打印。如不加控制，會有多種打 印結(jié)果，這取決于這兩個進(jìn)程運行 的相對速度。在這眾多的打印結(jié)果 中，只有CP、IOP進(jìn)程的運行剛好 匹配的一種是對的，其它均為錯誤 ，并且不能重現(xiàn)。 第26頁/共63頁 要保證打印結(jié)果的正確， CP、IOP必須遵循以下同步規(guī) 則： (1)當(dāng)CP把結(jié)果送入buffer后， IOP才能從buffer中取，否則 IOP必須等待； (2)當(dāng)IOP從buffer中取走數(shù)據(jù) 后，CP才能將新產(chǎn)生數(shù)據(jù)送 buffer，否則也必須等待。 解決這個問題的步驟：

10、 (1)分析問題，弄清楚 同步關(guān)系； (2)設(shè)置信號燈，說明 含義、初值； (3)寫出程序描述。 第27頁/共63頁 第28頁/共63頁 思考2 用P.V操作解決下圖之同步問題 提示：分別考慮對緩沖區(qū)S和T的同步，再 合并考慮 getcopyput st 第29頁/共63頁 解 設(shè)置四個信號量Sin=1，Sout=0，Tin=1，Tout=0； get： while（1） P(Sin）; 將數(shù)放入S; V(Sout); copy： while（1） P(Sout）; P(Tin）; 將數(shù)從S取出放入T; V(Tout); V(Sin); put： while（1） P(Tout）; 將數(shù)從T取

11、走; V(Tin); 第30頁/共63頁 思考3 桌上有一空盤，最多允許存放一只水果。爸 爸可向盤中放一個蘋果或放一個桔子，兒子專等 吃盤中的桔子，女兒專等吃蘋果。 試用P、V操作實現(xiàn)爸爸、兒子、女兒三個并 發(fā)進(jìn)程的同步。 提示：設(shè)置一個信號量表示可否向盤中放水果， 一個信號量表示可否取桔子，一個信號量表示可 否取蘋果。 第31頁/共63頁 解 設(shè)置三個信號量S,So,Sa ，初值分別為 1，0，0。分別表示可否向盤中放水果， 可否取桔子，可否取蘋果。 第32頁/共63頁 Father() while(1) p(S); 將水果放入盤中將水果放入盤中; if(是桔是桔 子子)v(So); els

12、e v(Sa); Son() while(1) p(So) 取桔子取桔子 v(S); 吃桔子吃桔子; Daughter() while(1) p(Sa) 取蘋果取蘋果 v(S); 吃蘋果吃蘋果; 第33頁/共63頁 吃水果問題 桌上有一只盤子，每次只能放一個水果， 爸爸專向盤中放蘋果，媽媽專向盤中放桔子， 兒子專等吃盤里的桔子，女兒專等吃盤里的蘋 果。只要盤子空，則爸爸或媽媽可向盤中放水 果，僅當(dāng)盤中有自己需要的水果時，兒子或女 兒可從中取出，請給出四人之間的同步關(guān)系， 并用P、V操作實現(xiàn)四人正確活動的程序。 第34頁/共63頁 四人之間的關(guān)系 爸爸，媽媽要互斥使用盤子，所以兩者 之間是互斥關(guān)

13、系； 爸爸放的蘋果，女兒吃，所以兩者是同 步關(guān)系； 媽媽放的桔子，兒子吃，所以兩者也是 同步關(guān)系。 第35頁/共63頁 semaphore s,sa,so=1,0,0; father () while(1) P(s); put an apple; V(sa); son () while(1) P(so); get an orange; V(s); mother () while(1) P(s); put an orange; V(so); daught () while(1) P(sa); get an apple; V(s); 設(shè)信號量設(shè)信號量s表示是否有表示是否有 空盤子，信號量空盤子，信

14、號量sa表示表示 兒子能否取蘋果，兒子能否取蘋果，so表表 示女兒能否取桔子示女兒能否取桔子 第36頁/共63頁 2.6.4 生產(chǎn)者消費者問題 假定緩沖區(qū)buffer是一 個有界緩沖區(qū)，可存放n個 數(shù)據(jù)，同時假定有n個CP進(jìn) 程不斷地產(chǎn)生數(shù)據(jù)，并送 buffer；有m個IOP進(jìn)程從緩 沖區(qū)中取數(shù)據(jù)打印。 在我們生活中有很多這 樣的例子。 第37頁/共63頁 對于生產(chǎn)者進(jìn)程：產(chǎn)生一個數(shù)據(jù)，當(dāng)要送入緩沖區(qū) 時，要檢查緩沖區(qū)是否已滿，若未滿，則可將數(shù)據(jù) 送入緩沖區(qū)，并通知消費者進(jìn)程；否則，等待； 對于消費者進(jìn)程：當(dāng)它去取數(shù)據(jù)時，要看緩沖區(qū)中 是否有數(shù)據(jù)可取，若有則取走一個數(shù)據(jù)，并通知生 產(chǎn)者進(jìn)程，否

15、則，等待。 這種相互等待，并互通信息就是典型的進(jìn)程同 步。同時，緩沖區(qū)是個臨界資源，因此，諸進(jìn)程對 緩沖區(qū)的操作程序是一個共享臨界區(qū)，因此，還有 個互斥的問題。 第38頁/共63頁 第39頁/共63頁 第40頁/共63頁 圖書館閱覽室問題 假定閱覽室最多可同時容納100個人閱讀，讀者 進(jìn)入時，必須在閱覽室門口的一個登記表上登記， 內(nèi)容包括姓名、座號等，離開時要撤掉登記內(nèi)容。 用P、V操作描述讀者進(jìn)程的同步算法。 (分析：讀者有任意多個，但進(jìn)入閱覽室閱讀最多為 100人，為此可設(shè)一個信號量s，代表空座位的數(shù)目 ；另登記表為臨界資源，需設(shè)一個用于互斥的信號 量mutex,防止2個及以上的讀者進(jìn)程同

16、時對此表訪問 。對于每個讀者的動作包括進(jìn)入、閱讀、離開。) 第41頁/共63頁 int s=100, mutex=1; readeri() (i=1,2,k) while(1) P(s); P(mutex); 查登記表，置某座位為占用； V(mutex); reading; P(mutex); 查登記表，置某座位為空; V(mutex); V(s); 第42頁/共63頁 讀者寫者問題 有十個讀者和兩個編輯同時處理一篇文章， 對于讀操作是可以同時進(jìn)行的，若有讀者正在讀 這篇文章，編輯就不能工作，若編輯正在處理這 篇文章，讀者就不能作讀操作，編輯與編輯的工 作也是互斥的，試用信號燈及P、V操作寫出

17、讀者 與編輯之間協(xié)同工作的程序描述。 第43頁/共63頁 分析： 允許多個讀者同時執(zhí)行讀操作 不允許讀者、寫者同時操作 不允許多個寫者同時操作 如果讀者來： 1）無讀者、寫者，新讀者可以讀 2）有寫者等，但有其它讀者正在讀，則新讀者 也可以讀 3）有寫者寫，新讀者等 如果寫者來： 1）無讀者，新寫者可以寫 2）有讀者，新寫者等待 3）有其它寫者，新寫者等待 第44頁/共63頁 讀者/寫者問題的解法 設(shè)兩個信號量mutex=1，mutex1=1 另設(shè)一個全局變量readcount =0 mutex用于讀者和寫者、寫者和寫者之間的 互斥 readcount表示正在讀的讀者數(shù)目 mutex1用于對r

18、eadcount 這個臨界資源的互 斥訪問 第45頁/共63頁 第46頁/共63頁 哲學(xué)家就餐問題 有五個哲學(xué)家圍坐在一圓桌旁，每人面前有 碗飯，每兩人之間放一只筷子；每個哲學(xué)家的行 為是思考，感到饑餓，然后吃飯；為了吃飯，每 個哲學(xué)家必須拿到兩只筷子，并且每個人只能直 接從自己的左邊或右邊去取筷子。 第47頁/共63頁 設(shè)fork5為5 個信號量，初值為均1 Philosopheri： while (1) 思考； P(forki); P(fork(i+1) % 5)； 進(jìn)食； V(forki); V(fork(i+1) % 5)； 解 第48頁/共63頁 以上解法會出現(xiàn)死鎖 為防止死鎖發(fā)生可

19、采取的措施： 最多允許4個哲學(xué)家同時去拿左邊的筷子 僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允 許他拿筷子 給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿 左邊的筷子，偶數(shù)號的哲學(xué)家則反之 分析 第49頁/共63頁 設(shè)fork5為5 個信號量，初值為均1；設(shè)置信號 量S限制同時進(jìn)餐的哲學(xué)家的數(shù)目，初值為4 Philosopheri： while (1) 思考； P(S); P(forki); P(fork(i+1) % 5)； 進(jìn)食； V(forki); V(fork(i+1) % 5)； V(S); 第50頁/共63頁 設(shè)有兩個生產(chǎn)者進(jìn)程A、B和一個銷售者進(jìn) 程，他們共享一個無限大的倉庫，生產(chǎn)者

20、每次 循環(huán)生產(chǎn)一個產(chǎn)品，然后入庫供銷售者銷售； 銷售者每次循環(huán)從倉庫中取出一個產(chǎn)品進(jìn)行銷 售。如果不允許同時入庫，也不允許邊入庫邊 出庫，而且要求生產(chǎn)A產(chǎn)品和B產(chǎn)品的件數(shù)滿足 以下關(guān)系： mBAn的件數(shù)的件數(shù) - 其中n、m是正整數(shù)，但對倉庫中A產(chǎn)品和B 產(chǎn)品的件數(shù)無上述要求。 第51頁/共63頁 分析： 生產(chǎn)者和消費者不能同時將產(chǎn)品入庫和出 庫，倉庫是一個臨界資源； 兩個生產(chǎn)者之間必須同步，產(chǎn)品件數(shù)之差 大于m時A等待，小于-n時B等待； 生產(chǎn)者和銷售者之間必須同步，只有當(dāng)生 產(chǎn)者產(chǎn)出產(chǎn)品并入庫后，才能進(jìn)行銷售。 設(shè)互斥信號量mutex=1;SA表示當(dāng)前允許A生 產(chǎn)產(chǎn)品的數(shù)量，初值為m；SB

21、表示當(dāng)前允許B 生產(chǎn)產(chǎn)品的數(shù)量，初值為n;資源信號量S表示倉 庫中產(chǎn)品的數(shù)量，初值為0. 第52頁/共63頁 nain() int mutex=1,SA=m,SB=n,S=0; cobegin A(); B(); C(); coend C() P(S); P(mutex); 一個產(chǎn)品出庫； V(mutex); 銷售一個產(chǎn)品; 第53頁/共63頁 A() P(SA); 生產(chǎn)一個產(chǎn)品A; V(SB); P(mutex); A產(chǎn)品入庫； V(mutex); V(S); B() P(SB); 生產(chǎn)一個產(chǎn)品B; V(SA); P(mutex); B產(chǎn)品入庫； V(mutex); V(S); 第54頁/共

22、63頁 解決進(jìn)程互斥的最簡單的辦法是加鎖。 在系統(tǒng)中為每個臨界資源設(shè)置一個鎖位， 0 表示資源可用， 1 表示資源已被占用（不可用）。 這樣當(dāng)一個進(jìn)程使用某個臨界資源之前必須完成下列操作： 1、考察鎖位的值； 2、若原來的值是為“0”，將鎖位置為“1”（占用該資源）； 3、若原來值是為“1”，（該資源已被別人占用），則轉(zhuǎn)到1。 當(dāng)進(jìn)程使用完資源后，將鎖位置為“0 ” ，稱為開鎖操 作。 2.4.2 鎖和上鎖、開鎖操作 第55頁/共63頁 2.4.3 用上鎖原語和開鎖原語實現(xiàn)互斥 設(shè)有兩個進(jìn)程共享 打印機，兩個進(jìn)程中使 用打印機的程序段為臨 界區(qū)。 為保證打印的正確 ，設(shè)置打印機的鎖位 print,其初值為“0”， 表示打印機可用。 第56頁/共63頁 信號燈是一個確定的二元組（s,q），s 是一個 具有非負(fù)初值的整型變量，q是一個初始狀態(tài)為 空的隊列。 S代表資源的實體。在實