操作系統(tǒng)第2章進(jìn)程管理(藏漢雙語)

1、主講：頭旦才讓主講：頭旦才讓計算機(jī)學(xué)院藏文信息科學(xué)系計算機(jī)學(xué)院藏文信息科學(xué)系第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的描述、控制二進(jìn)程同步、經(jīng)典同步問題三線程及其實現(xiàn)四v 掌握分析進(jìn)程的結(jié)構(gòu)，特征掌握分析進(jìn)程的結(jié)構(gòu)，特征， PCBPCB。v 描述進(jìn)程的基本狀態(tài)及轉(zhuǎn)換規(guī)則與原因。描述進(jìn)程的基本狀態(tài)及轉(zhuǎn)換規(guī)則與原因。v 掌握解決互斥與同步的方法。掌握解決互斥與同步的方法。v 掌握掌握3 3個經(jīng)典問題的解決方法：個經(jīng)典問題的解決方法： 生產(chǎn)者生產(chǎn)者/ /消費(fèi)者問題、消費(fèi)者問題、 讀者讀者/ /寫著問題、寫著問題、 哲學(xué)家進(jìn)餐問題。哲學(xué)家進(jìn)餐問題。通過本章的學(xué)習(xí)通過本

2、章的學(xué)習(xí)，你應(yīng)該學(xué)會以下內(nèi)容：你應(yīng)該學(xué)會以下內(nèi)容：第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的描述、控制二進(jìn)程同步、經(jīng)典同步問題三線程及其實現(xiàn)四P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九個結(jié)點(diǎn)的前趨圖(b) 具有循環(huán)的前趨圖圖圖a所示的前趨關(guān)系為：所示的前趨關(guān)系為：P1-P2，P1-P3，P1-P4，P2-P5，P3-P5，P4-P6，P4-P7，P5-P8，P6-P8，P7-P9，P8-P9對，俺不是我是前趨圖，他不是2.1 .2 程序的順序執(zhí)行程序的順序執(zhí)行 S1: a=x+y; S2: b=a-5; S3: c=b+1;(a) 程序的順

3、序執(zhí)行(b) 三條語句的順序執(zhí)行I1C1P1I2C2P2S1S2S3I1I2I3I4C1C2C3C4P1P2P3P4t2.1 .3 程序并發(fā)執(zhí)行程序并發(fā)執(zhí)行：S1S2S3S42.1 .3 程序并發(fā)執(zhí)行程序并發(fā)執(zhí)行2.1 .3 程序并發(fā)執(zhí)行程序并發(fā)執(zhí)行順序執(zhí)行并發(fā)執(zhí)行一一對應(yīng)一個程序可對應(yīng)多個執(zhí)行獨(dú)占資源，具有封閉性共享資源，不具有封閉性具有無具有無無有直接或間接制約關(guān)系第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的描述、控制二進(jìn)程同步、經(jīng)典同步問題三線程及其實現(xiàn)四2.2 進(jìn)程的描述2.2 進(jìn)程的描述l 2.2.1進(jìn)程的特征 進(jìn)程是動態(tài)的，程序是靜態(tài)的進(jìn)程是動態(tài)的，

4、程序是靜態(tài)的 進(jìn)程是暫時的，程序是永久的進(jìn)程是暫時的，程序是永久的 程序是由多個進(jìn)程運(yùn)行的程序是由多個進(jìn)程運(yùn)行的 進(jìn)程與程序的組成不同進(jìn)程與程序的組成不同 進(jìn)程與程序的對應(yīng)關(guān)系進(jìn)程與程序的對應(yīng)關(guān)系進(jìn)程和程序之間不存在一一對應(yīng)關(guān)系。進(jìn)程和程序之間不存在一一對應(yīng)關(guān)系。一個程序可以對應(yīng)多一個程序可以對應(yīng)多個進(jìn)程；反之，一個進(jìn)程至少要對應(yīng)一個程序，或?qū)?yīng)多個個進(jìn)程；反之，一個進(jìn)程至少要對應(yīng)一個程序，或?qū)?yīng)多個程序，多個進(jìn)程也可對應(yīng)相同的程序。程序，多個進(jìn)程也可對應(yīng)相同的程序。 進(jìn)程具有并發(fā)特征（獨(dú)立性和異步性）進(jìn)程具有并發(fā)特征（獨(dú)立性和異步性）2.2 進(jìn)程的描述l 進(jìn)程和程序的聯(lián)系及區(qū)別進(jìn)程和程序的聯(lián)

5、系及區(qū)別理解進(jìn)程的實例 想象一位有一手好廚藝的計算機(jī)科學(xué)家正在為他的女兒烘制生日蛋糕。他有做生日想象一位有一手好廚藝的計算機(jī)科學(xué)家正在為他的女兒烘制生日蛋糕。他有做生日蛋糕的食譜，廚房里有所需的原料：面粉、雞蛋、糖、香草汁等等。在這個比喻中，做蛋糕的食譜，廚房里有所需的原料：面粉、雞蛋、糖、香草汁等等。在這個比喻中，做蛋糕的食譜就是程序蛋糕的食譜就是程序( (即用適當(dāng)形式描述的算法即用適當(dāng)形式描述的算法) )，計算機(jī)科學(xué)家就是處理機(jī)，計算機(jī)科學(xué)家就是處理機(jī)(CPU)(CPU)，而做，而做蛋糕的各種原料就是輸入數(shù)據(jù)。進(jìn)程就是廚師閱讀食譜、取來各種原料、以及烘制蛋糕蛋糕的各種原料就是輸入數(shù)據(jù)。進(jìn)程

6、就是廚師閱讀食譜、取來各種原料、以及烘制蛋糕的一系列動作的總和。的一系列動作的總和。 現(xiàn)在假設(shè)計算機(jī)科學(xué)家的兒子哭著跑了進(jìn)來，說他被一只蜜蜂螫了。計算機(jī)科學(xué)家現(xiàn)在假設(shè)計算機(jī)科學(xué)家的兒子哭著跑了進(jìn)來，說他被一只蜜蜂螫了。計算機(jī)科學(xué)家就記錄下他照著食譜做到哪兒了就記錄下他照著食譜做到哪兒了( (保存進(jìn)程的當(dāng)前狀態(tài)保存進(jìn)程的當(dāng)前狀態(tài)) )，然后拿出一本急救手冊，按照，然后拿出一本急救手冊，按照其中的指示處理螫傷。這里，我們看到處理機(jī)從一個進(jìn)程其中的指示處理螫傷。這里，我們看到處理機(jī)從一個進(jìn)程( (做蛋糕做蛋糕) )切換到另一個高優(yōu)先切換到另一個高優(yōu)先級的進(jìn)程級的進(jìn)程( (實施醫(yī)療救治實施醫(yī)療救治)

7、)，每個，每個( (進(jìn)程進(jìn)程) )擁有各自的程序擁有各自的程序( (食譜和急救書食譜和急救書) )。當(dāng)蜜蜂螫傷處。當(dāng)蜜蜂螫傷處理完之后，計算機(jī)科學(xué)家又回來做蛋糕，從他離開時的那一步繼續(xù)做下去。理完之后，計算機(jī)科學(xué)家又回來做蛋糕，從他離開時的那一步繼續(xù)做下去。 這里的關(guān)鍵思想是：一個進(jìn)程是某種類型的一個活動，它有程序、輸入、這里的關(guān)鍵思想是：一個進(jìn)程是某種類型的一個活動，它有程序、輸入、輸出、及狀態(tài)。單個處理機(jī)被若干進(jìn)程共享，它使用某種調(diào)度算法決定何時停輸出、及狀態(tài)。單個處理機(jī)被若干進(jìn)程共享，它使用某種調(diào)度算法決定何時停止一個進(jìn)程的工作，并轉(zhuǎn)而為另一個進(jìn)程提供服務(wù)。止一個進(jìn)程的工作，并轉(zhuǎn)而為另一

8、個進(jìn)程提供服務(wù)。理解進(jìn)程的實例主講：頭旦才讓主講：頭旦才讓計算機(jī)學(xué)院藏文信息科學(xué)系計算機(jī)學(xué)院藏文信息科學(xué)系就緒就緒阻塞阻塞執(zhí)行執(zhí)行時間片完時間片完進(jìn)程調(diào)度進(jìn)程調(diào)度分配分配CPUI/O請求請求I/O完成完成圖圖2 25 5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換三種基本狀態(tài)的轉(zhuǎn)換三種基本狀態(tài)的轉(zhuǎn)換l 創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換圖圖2 26 6 進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換 2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換l 被掛起進(jìn)程的特

9、征被掛起進(jìn)程的特征2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換執(zhí)行執(zhí)行活動活動就緒就緒靜止靜止就緒就緒活動活動阻塞阻塞靜止靜止阻塞阻塞激活激活掛起掛起許可許可創(chuàng)建創(chuàng)建終止終止調(diào)度調(diào)度時間片完時間片完激活激活掛起掛起事件發(fā)生事件發(fā)生釋放釋放釋放釋放2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換掛起掛起釋放釋放許可許可2.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)資源（進(jìn)程）信息表：標(biāo)識資源（進(jìn)程）信息表：標(biāo)識+ +描述描述+ +狀態(tài)狀態(tài)+ +指針指針OSOS管理的數(shù)據(jù)結(jié)構(gòu)分為四類：內(nèi)存表、設(shè)備表、文件表、進(jìn)程表管理的數(shù)據(jù)結(jié)構(gòu)分為四類：內(nèi)存表、設(shè)備表、文件表、進(jìn)程表內(nèi)存內(nèi)存設(shè)備設(shè)備文件文件進(jìn)程進(jìn)程內(nèi)存表內(nèi)存表內(nèi)存表進(jìn)程進(jìn)程1進(jìn)程2進(jìn)程3

10、進(jìn)程n進(jìn)程1進(jìn)程實體及所用資源列表進(jìn)程實體及所用資源列表進(jìn)程npid處理機(jī)狀態(tài)處理機(jī)狀態(tài)進(jìn)程狀態(tài)進(jìn)程狀態(tài)優(yōu)先級優(yōu)先級其他信息其他信息程序地址程序地址同步機(jī)制同步機(jī)制資源清單資源清單鏈接指針鏈接指針標(biāo)識標(biāo)識處理機(jī)狀態(tài)處理機(jī)狀態(tài)進(jìn)程調(diào)度信息進(jìn)程調(diào)度信息進(jìn)程控制信息進(jìn)程控制信息2.2.3 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的控制二進(jìn)程同步、經(jīng)典同步問題三線程及其實現(xiàn)四2.3.1 進(jìn)程控制描述2.3.2 進(jìn)程的創(chuàng)建2.3.2 進(jìn)程的創(chuàng)建開始開始查查PCBPCB鏈表鏈表填空表填空表PCBPCB將有關(guān)參數(shù)填入將有關(guān)參數(shù)填入PCBPCB相應(yīng)項相應(yīng)項

11、將將PCBPCB加入就緒隊列加入就緒隊列將將PCBPCB加入進(jìn)程家族或進(jìn)程鏈加入進(jìn)程家族或進(jìn)程鏈創(chuàng)建失敗創(chuàng)建失敗是是無無空表空表2.3.2 進(jìn)程的創(chuàng)建2.3.2 進(jìn)程的創(chuàng)建2.3.3 進(jìn)程的終止2.3.3 進(jìn)程的終止開始開始查進(jìn)程家族或進(jìn)程鏈查進(jìn)程家族或進(jìn)程鏈釋放該進(jìn)程所占有的資源釋放該進(jìn)程所占有的資源釋放該釋放該P(yáng)CBPCB結(jié)構(gòu)本身結(jié)構(gòu)本身出錯處理出錯處理有有無無由此由此PCB嗎嗎該該P(yáng)CB有子進(jìn)程嗎？有子進(jìn)程嗎？返回返回有有無無2.3.4 進(jìn)程的阻塞和喚醒第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的控制二進(jìn)程同步、經(jīng)典同步問題三線程及其實現(xiàn)四v 進(jìn)程同步的主

12、要任務(wù)：使并發(fā)程序的執(zhí)行有可再現(xiàn)性進(jìn)程同步的主要任務(wù)：使并發(fā)程序的執(zhí)行有可再現(xiàn)性兩種形式的制約關(guān)系兩種形式的制約關(guān)系v 間接制約關(guān)系（進(jìn)程互斥）間接制約關(guān)系（進(jìn)程互斥） ：是進(jìn)程共享獨(dú)占型資源而必須互斥執(zhí)行的間接制約關(guān)系。v 直接制約關(guān)系（進(jìn)程同步）直接制約關(guān)系（進(jìn)程同步）：即為完成同一個任務(wù)的諸進(jìn)程間，因需要協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的直接制約關(guān)系。 v 同步與互斥比較同步與互斥比較同同 步步互互 斥斥進(jìn)程-進(jìn)程進(jìn)程-資源-進(jìn)程時間次序上受到某種限制競爭到某一物理資源時不允許進(jìn)程工作相互清楚對方的存在及作用，交換信息不一定清楚其進(jìn)程情況往往指有幾個進(jìn)程共同完成一個任務(wù)往往指

13、多個任務(wù)多個進(jìn)程間通訊制約例：生產(chǎn)與消費(fèi)之間，發(fā)送與接受之間，作者與讀者之間，供者與用者之間例：交通十字路口2.4.1 進(jìn)程同步的基本概念 到站停車到站停車 開開 車車 開車門開車門 關(guān)車門關(guān)車門 售票售票 正常行車正常行車。售票員進(jìn)程售票員進(jìn)程B B司機(jī)進(jìn)程司機(jī)進(jìn)程A A進(jìn)程同步例子司機(jī)操作的規(guī)則：司機(jī)操作的規(guī)則： 只有只有B B關(guān)門后，關(guān)門后，A A才能行駛才能行駛售票員操作的規(guī)則：售票員操作的規(guī)則： 只有只有A A停車后，停車后，B B才能開門，才能開門，B B關(guān)門后，向關(guān)門后，向A A發(fā)開車信號，發(fā)開車信號，A A收到信號才能開收到信號才能開臨界資源（臨界資源（ ）：）：一次只允許一個

14、進(jìn)程使用的資源稱為臨界資源。臨界區(qū)（臨界區(qū)（ ）：）：在每個進(jìn)程中訪問臨界資源的程序段成為臨界區(qū)。臨界資源和臨界區(qū) 空閑讓進(jìn)空閑讓進(jìn)：當(dāng)無進(jìn)程在臨界區(qū)時，任何有權(quán)使用臨界區(qū)的進(jìn)：當(dāng)無進(jìn)程在臨界區(qū)時，任何有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入程可進(jìn)入 忙則等待忙則等待：不允許兩個以上的進(jìn)程同時進(jìn)入臨界區(qū)（互斥）：不允許兩個以上的進(jìn)程同時進(jìn)入臨界區(qū)（互斥） 有限等待有限等待：任何進(jìn)入臨界區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿：任何進(jìn)入臨界區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足（死等）足（死等） 讓權(quán)等待讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPUCPU（忙等）（忙等）同步機(jī)制應(yīng)遵守的原則2.4

15、.3 信號量機(jī)制 Semaphore 整型信號量Wait(S)和和signal(S)操作操作描述如下：描述如下：記錄型信號量：信號量的類型信號量的類型2.4.4 2.4.4 信號量的應(yīng)用信號量的應(yīng)用1.1.利用信號量實現(xiàn)進(jìn)程互斥利用信號量實現(xiàn)進(jìn)程互斥進(jìn)程能互斥訪問臨界資源設(shè)置互斥信號量-mutex初始值=1臨界區(qū)CS置于中間臨界區(qū)CS置于中間Wait(mutex)Wait(mutex)Mutex=1,Mutex=1,兩個進(jìn)程兩個進(jìn)程未進(jìn)入臨界區(qū)未進(jìn)入臨界區(qū)Mutex=0,Mutex=0,一個進(jìn)程進(jìn)入臨界一個進(jìn)程進(jìn)入臨界區(qū)運(yùn)行，另一個等待區(qū)運(yùn)行，另一個等待Mutex=-1,Mutex=-1,一個

16、進(jìn)程進(jìn)入臨界區(qū)一個進(jìn)程進(jìn)入臨界區(qū)運(yùn)行，另一個阻塞，等待喚醒運(yùn)行，另一個阻塞，等待喚醒2.2.利用信號量實現(xiàn)前趨關(guān)系利用信號量實現(xiàn)前趨關(guān)系 圖 2-14 前趨圖舉例 S4S5S3S1S6S2左圖所示了一個前趨圖，其中S1、S2，S3，S4，S5，S6是最簡單的程序段，為使個程序段能正確執(zhí)行，應(yīng)設(shè)置若干個初始值為“0”的信號量： 信號量S1-S2 aS1-S3 bS2-S4 cS2-s5 dS3-S6 eS4-S6 fS5-S6 g Var a，b，c，d，e，f，g； semaphore =0，0，0，0，0，0，0； begin parbegin begin S1；signal(a)； sig

17、nal(b)；end； begin wait(a)； S2；signal(c)； signal(d)；end； begin wait(b)； S3；signal(e)；end； begin wait(c)；S4；signal(f)；end； begin wait(d)；S5；signal(g)；end； begin wait(e)；wait(f)；wait(g)；S6；end； parend end P(S) ； V(S)； wait(S) ； signal(S) ； S4S5S3S1S6S2abcdegf2.2.利用信號量實現(xiàn)前趨關(guān)系利用信號量實現(xiàn)前趨關(guān)系 2.4.5 2.4.5 管管 程程

18、 機(jī)機(jī) 制制 1. 管程的定義管程的定義 2. 管程由四部分組成：管程由四部分組成： 管程的名稱。 局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說明； 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； 對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。 一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的控制二經(jīng)典的進(jìn)程同步問題三線程及其實現(xiàn)四公共汽車問題公共汽車問題同步同步 到站停車到站停車 開開 車車 開車門開車門 關(guān)車門關(guān)車門 售票售票 正常行車正常行車。售票員進(jìn)程售票員進(jìn)程B B司機(jī)進(jìn)程司機(jī)進(jìn)程A Asemaph

19、ore S1=0；/是否允許司機(jī)啟動汽車semaphore S2=0；/是否允許售票員開門void siji（） /司機(jī)進(jìn)程begin while（1） begin P（S1）;/司機(jī)進(jìn)程暫停，售票員關(guān)車門 啟動車輛； 正常行駛； 到站停車； V（S2）；/激活售票員，允許B開門End；End；void spy（） /售票員進(jìn)程Begin while（1） begin 關(guān)車門； V（S1）；/激活司機(jī)，允許A開車 售票； P（S2）；/等待司機(jī) 開車門； 上下客； end；End；mian （） Begin Siji（）； Spy（）； end.公共汽車問題公共汽車問題同步同步【桔子蘋果問題桔

20、子蘋果問題】 放蘋果發(fā)同步信號S2放桔子發(fā)同步信號S3初始狀態(tài)：同步信號量S1=1，表示盤子為空爸爸桔子或蘋果蘋果桔子女兒兒子女兒等信號S2發(fā)信號S1兒子等信號S3發(fā)信號S1 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果或桔桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果或桔子，兒子專等吃盤子中的桔子，女兒專等吃盤子中的蘋果。用子，兒子專等吃盤子中的桔子，女兒專等吃盤子中的蘋果。用PVPV操作實現(xiàn)他們操作實現(xiàn)他們之間的同步機(jī)制。之間的同步機(jī)制。semaphore S1=1；semaphore S2=0；semaphore S3=0；father（）（）Begin w

21、hile(1) Begin P(S1);/等待水果盤中有空位等待水果盤中有空位 將水果放入盤中將水果放入盤中 if (是是蘋果蘋果) then V(S2); else V(S3); end；End；daughter( ) begin while(1) begin P(S2);/等待盤中放了蘋果等待盤中放了蘋果 取出蘋果；取出蘋果； V(S1);/，置盤中無水果，通知，置盤中無水果，通知爸爸可以放爸爸可以放 end；End；【桔子蘋果問題桔子蘋果問題】 son( ) begin while(1) begin P(S3);/等待盤中放了桔子等待盤中放了桔子 取出桔子；取出桔子； V(S1); /置

22、盤中無置盤中無水果，通知水果，通知爸爸爸可以放爸可以放 End；End；獨(dú)木橋問題獨(dú)木橋問題互斥互斥semaphore s=1； /s代表對橋的獨(dú)占控制void e2w（） /由東向西 while（1） P（s）； pass（）； V（s）；【例例】一條小河上有一座獨(dú)木橋，規(guī)定每次只允許一個人過橋。一條小河上有一座獨(dú)木橋，規(guī)定每次只允許一個人過橋?，F(xiàn)河?xùn)|和河西都有人在等待過橋，如果把每個過橋者看做一個進(jìn)現(xiàn)河?xùn)|和河西都有人在等待過橋，如果把每個過橋者看做一個進(jìn)程，為保證安全，用信號量和程，為保證安全，用信號量和P P、V V操作來管理。操作來管理。void w2e（） /由西向東 while（1

23、） P（s）； pass（）； V（s）； semaphore S1=1； /S1代表東邊的人先過橋semaphore S2=0； /S2代表西邊的人先讓東邊人過橋void e2w（） /由東向西 while（1） P（S1）； pass（）； V（S2）；獨(dú)木橋問題獨(dú)木橋問題同步同步v 要求：兩邊輪流過橋，以保證公平性；且東邊的人先過橋要求：兩邊輪流過橋，以保證公平性；且東邊的人先過橋void w2e（） /由西向東 while（1） P（S2）； pass（）； V（S1）；看電影問題看電影問題 有有3 3個網(wǎng)友，未曾謀面，他們相約去看電影，費(fèi)用個網(wǎng)友，未曾謀面，他們相約去看電影，費(fèi)用AA

24、AA制，條件是制，條件是3 3個人必須都到電影院的時候才能買票進(jìn)入，如果缺一個人，就害個人必須都到電影院的時候才能買票進(jìn)入，如果缺一個人，就害怕有危險，取消活動。試用信號量和怕有危險，取消活動。試用信號量和P P、V V操作描述操作描述3 3個人的行為。個人的行為。（請同學(xué)們思考一下，再看具體做法。）（請同學(xué)們思考一下，再看具體做法。） 這個問題看起來可能沒有頭緒，但問題倒是十分的簡單明顯，這個問題看起來可能沒有頭緒，但問題倒是十分的簡單明顯，那就是每個人到達(dá)電影院的時候，必須通知另外那就是每個人到達(dá)電影院的時候，必須通知另外2 2個人自己已經(jīng)到個人自己已經(jīng)到達(dá)（可以打電話或發(fā)手機(jī)短息告知喲）

25、，而且自己買票的行為取決達(dá)（可以打電話或發(fā)手機(jī)短息告知喲），而且自己買票的行為取決于另外于另外2 2個人確實已經(jīng)到達(dá)。那么我們這里使用個人確實已經(jīng)到達(dá)。那么我們這里使用6 6個信號量，來控制個信號量，來控制整個事情的流程。整個事情的流程。semaphore S12=0； /表示第1個人告知第2個人自己已到達(dá)semaphore S13=0； /表示第1個人告知第3個人自己已到達(dá)semaphore S21=0； /表示第2個人告知第1個人自己已到達(dá)semaphore S23=0； /表示第2個人告知第3個人自己已到達(dá)semaphore S31=0； /表示第3個人告知第1個人自己已到達(dá)semaph

26、ore S32=0； /表示第3個人告知第2個人自己已到達(dá)person1（） V(S12); V(S13); P(S21); P(S31); 買票；看電影問題看電影問題person2（） V(S21); V(S23); P(S12); P(S32); 買票；person3（） V(S31); V(S32); P(S13); P(S23); 買票；哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題 哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題#define N 5 / 哲學(xué)家數(shù)量#define LEFT (i+N-1)%N / i的左鄰居編號#define RIGHT (i+1)%N / i的右鄰居編號#define THINKIN

27、G 0 / 哲學(xué)家在思考#define HUNGRY 1 / 哲學(xué)家饑餓，試圖拿叉子#define EATING 2 / 哲學(xué)家在進(jìn)餐int stateN; / 數(shù)組用來跟蹤記錄每位哲學(xué)家的狀態(tài)semaphore mutex=1; / 互斥進(jìn)入臨界區(qū)，初值為1semaphore sN=0; / 每位哲學(xué)家一個信號量，初值為0void philosopher(int i) / i為哲學(xué)家編號，從0到N-1 while(1) think(); / 哲學(xué)家在思考問題 take_forks(i); / 拿到兩把叉子或者被阻塞 eat(); / 進(jìn)餐 put_ forks(i); / 把叉子放回原處 哲

28、學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題void take_ forks(int i) / i為哲學(xué)家編號，從0到N-1，拿叉子 P(mutex); / 進(jìn)入臨界區(qū) statei=HUNGRY; / 記錄哲學(xué)家i處于饑餓狀態(tài) test(i); / 試圖拿兩把叉子 V(mutex); / 離開臨界區(qū) P(si); / 如果得不到需要的叉子則阻塞void put_ forks(int i) / i為哲學(xué)家編號，從0到N-1，放下叉子 P(mutex); / 進(jìn)入臨界區(qū) statei=THINKING; / 哲學(xué)家就餐完畢，開始思考 test(LEFT); / 查看左鄰，現(xiàn)在能否進(jìn)餐 test(RIGHT); /

29、 查看右鄰，現(xiàn)在能否進(jìn)餐 V(mutex); / 離開臨界區(qū) void test(int i) / i為哲學(xué)家編號，從0到N-1，思考 if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; V(si); 哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題第二章第二章 進(jìn)程描述與控制進(jìn)程描述與控制 程序執(zhí)行一前趨圖和程序執(zhí)行進(jìn)程的控制二經(jīng)典的進(jìn)程同步問題三線程及其實現(xiàn)四v 線程的引入 1. 線程的概念 引入線程主要的原因來自以下四個方面： （1）計算機(jī)網(wǎng)絡(luò)的快速發(fā)展 （2）CPU速度的快速提升 （3）編程模式

30、的變化 （4）業(yè)務(wù)應(yīng)用的需求2.6 2.6 線程（線程（ThreadsThreads）2.6.1 2.6.1 線程的引入線程的引入v 在操作系統(tǒng)中引入進(jìn)程的目的是為了使多個程序并發(fā)執(zhí)行，以提高資在操作系統(tǒng)中引入進(jìn)程的目的是為了使多個程序并發(fā)執(zhí)行，以提高資源的利用率和系統(tǒng)的吞吐量，而在操作系統(tǒng)中引入線程的目的則是為源的利用率和系統(tǒng)的吞吐量，而在操作系統(tǒng)中引入線程的目的則是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統(tǒng)具有更好的并了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統(tǒng)具有更好的并發(fā)性發(fā)性。v 操作系統(tǒng)引入進(jìn)程后，雖然能使程序并發(fā)執(zhí)行，但由于進(jìn)程既是一個可以獨(dú)立調(diào)度的基本單位，同時也是

31、一個可擁有資源的單位。因此程序并發(fā)執(zhí)行時，系統(tǒng)必須為進(jìn)程的創(chuàng)建、撤銷和切換付出較大的時空開銷。既然這樣，系統(tǒng)中所設(shè)置的進(jìn)程數(shù)目就不宜太多，進(jìn)程切換的頻率也不宜過高，因此它也限制了程序的并發(fā)執(zhí)行程度。2.6.2 2.6.2 線程與進(jìn)程的關(guān)系線程與進(jìn)程的關(guān)系在引入線程的操作系統(tǒng)中線程和進(jìn)程具有以下關(guān)系：v （1）線程是進(jìn)程的一部分，它是進(jìn)程內(nèi)的一個執(zhí)行單元。通常，一個進(jìn)程含有若干個線程，至少也要有一個線程。一個進(jìn)程的多個線程都在進(jìn)程的地址空間里活動。v （2）引入線程的操作系統(tǒng)中，資源分配的對象是進(jìn)程，而不是線程資源分配的對象是進(jìn)程，而不是線程。進(jìn)程仍是擁有資源的一個獨(dú)立單位，它擁有自己的資源，一

32、般地說，線程除有一點(diǎn)必不可少的資源外不擁有系統(tǒng)資源。線程使用的資源是進(jìn)程分到的資源。v （3）引入線程的操作系統(tǒng)中，調(diào)度的基本單位是線程而不是進(jìn)程調(diào)度的基本單位是線程而不是進(jìn)程。即CPU是分給線程的，真正在CPU上執(zhí)行的是線程。2.6.2 2.6.2 線程與進(jìn)程的關(guān)系線程與進(jìn)程的關(guān)系v （4）進(jìn)程之間可以并發(fā)執(zhí)行，而一個進(jìn)程中的這些線程之間亦可并發(fā)執(zhí)行。而且在并發(fā)執(zhí)行過程中，也需要協(xié)作同步。v （5）進(jìn)程調(diào)度，系統(tǒng)要進(jìn)行進(jìn)程上下文的切換，需要系統(tǒng)大量的開銷。v （6）線程調(diào)度，由于同一進(jìn)程內(nèi)的線程共享進(jìn)程的資源，其切換是把線程僅有的一小部分資源變換即可，從而提高了系統(tǒng)的效率。線程切換比進(jìn)程切換

33、快得多。因此有些人把線程又稱為輕型進(jìn)程。v （7）從一個進(jìn)程的線程向另一個進(jìn)程的線程切換，將引起進(jìn)程的上下文切換。v （8）同一進(jìn)程的多線程共享進(jìn)程的所有資源，一個線程可以改變另一個線程的數(shù)據(jù)，而多進(jìn)程機(jī)制則不會產(chǎn)生這個問題。2.6.3 2.6.3 線程的屬性線程的屬性 v 輕型實體。v 獨(dú)立調(diào)度和分派的基本單位。v 可并發(fā)執(zhí)行。v 共享進(jìn)程資源。 (1) 狀態(tài)參數(shù)。 寄存器狀態(tài) 它包括程序計數(shù)器PC和堆棧指針中的內(nèi)容； 堆棧 在堆棧中通常保存有局部變量和返回地址； 線程運(yùn)行狀態(tài) 用于描述線程正處于何種運(yùn)行狀態(tài)； 優(yōu)先級， 描述線程執(zhí)行的優(yōu)先程度； 線程專有存儲器 用于保存線程自己的局部變量拷貝； 信號屏蔽 即對某些信號加以屏蔽。 2.6.4 2.6.4 線程的狀態(tài)線程的狀態(tài)(2) 線程運(yùn)行狀態(tài)。 執(zhí)行狀態(tài)，表示線程正獲得處理機(jī)而運(yùn)行； 就緒狀態(tài)， 指線程已具備了各種執(zhí)行條件，一旦獲得CPU便可執(zhí)行的狀態(tài)； 阻塞狀態(tài)，指線程在執(zhí)行中因某事件而受阻，處于暫停執(zhí)行時的狀態(tài)。 2.6.4 2.6.4 線程的狀態(tài)線程的狀態(tài)2.6.5 2.6.5 多線程多線程OSOS中的進(jìn)程中的進(jìn)程 在多線程OS中，進(jìn)程是作為擁有系統(tǒng)資源的基本單位，通常的進(jìn)程都包含多個線程并為它們提供資源，但此時的進(jìn)程就不再作為一個執(zhí)行的實體。 多線程OS中的進(jìn)程有