第二進(jìn)程管理2

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

2、去封閉性 不可再現(xiàn)性不可再現(xiàn)性p1p2ti/ocpu兩個(gè)程序并發(fā)執(zhí)行示意圖觀察者beginrepeat wait for a car through n=n+1untilend報(bào)告者beginrepeat delay print n n=0untilend初始n=n時(shí)不同執(zhí)行序列，結(jié)果各不相同執(zhí)行序列 123程序n=n+1print nn=0print nn=0n=n+1print nn=n+1n=0結(jié)果例子：觀察者與報(bào)告者打印n+1,n=0打印n, n=1打印n, n=02) 進(jìn)程（process）的定義與特征描述：描述：本質(zhì)上來(lái)說一個(gè)進(jìn)程就是一個(gè)執(zhí)行的程序，是一個(gè)具有獨(dú)立功能的程序在一個(gè)數(shù)

3、據(jù)集合上的一次動(dòng)態(tài)執(zhí)行過程，是計(jì)算機(jī)資源的使用主體，擁有獨(dú)立的地址空間。定義：進(jìn)程實(shí)體的定義：進(jìn)程實(shí)體的運(yùn)行過程，是運(yùn)行過程，是os進(jìn)行資源分配和調(diào)度進(jìn)行資源分配和調(diào)度的基本單位。的基本單位。特征特征 結(jié)構(gòu)特征結(jié)構(gòu)特征- 進(jìn)程實(shí)體=程序段+數(shù)據(jù)段+進(jìn)程控制塊(pcb) 動(dòng)態(tài)性動(dòng)態(tài)性- 進(jìn)程是進(jìn)程實(shí)體的一次執(zhí)行過程，進(jìn)程要經(jīng)歷“發(fā)生，發(fā) 展和消亡”的動(dòng)態(tài)變化過程。 并發(fā)性并發(fā)性- 在一個(gè)時(shí)間間隔內(nèi)多個(gè)進(jìn)程同時(shí)運(yùn)行。 獨(dú)立性獨(dú)立性- 獨(dú)立運(yùn)行，獨(dú)立分配資源和獨(dú)立接受調(diào)度。 異步性異步性- 按各自獨(dú)立的不可預(yù)知的速度向前推進(jìn) 程序與進(jìn)程之區(qū)別程序與進(jìn)程之區(qū)別程序程序靜態(tài)永久由程序段組成通過多次執(zhí)行一

4、個(gè)程 序可對(duì)應(yīng)多個(gè)進(jìn)程進(jìn)程進(jìn)程動(dòng)態(tài)有生命周期進(jìn)程實(shí)體通過調(diào)用一個(gè)進(jìn)程可包含多個(gè)程序3) 進(jìn)程的狀態(tài)及其轉(zhuǎn)換 三種基本狀態(tài)及其轉(zhuǎn)換：l 就緒狀態(tài)就緒狀態(tài)-已經(jīng)獲得所需資源，只等待cpu，所有處在就緒狀態(tài)的進(jìn)程排在就緒隊(duì)列上。l 執(zhí)行狀態(tài)執(zhí)行狀態(tài)-正在運(yùn)行中。l 阻塞狀態(tài)阻塞狀態(tài)-進(jìn)程等待某個(gè)事件，如等待i/o完成，等待某個(gè)資源，處于暫停狀態(tài)。所有處在阻塞狀態(tài)的進(jìn)程排在隊(duì)列上(一個(gè)或多個(gè)隊(duì)列)。此外還可以有新建態(tài)和終止態(tài)。v進(jìn)程狀態(tài)的轉(zhuǎn)換新建終止就緒阻塞運(yùn)行創(chuàng)建完畢時(shí)間片用完結(jié)束執(zhí)行選中等待事件等待結(jié)束 具有掛起狀態(tài)的狀態(tài)圖執(zhí)行執(zhí)行活動(dòng)活動(dòng)就緒就緒靜止靜止就緒就緒掛起掛起掛起掛起激活激活靜止靜止阻

5、塞阻塞活動(dòng)活動(dòng)阻塞阻塞激活激活掛起掛起喚醒喚醒喚醒喚醒阻塞阻塞引起掛起狀態(tài)的原因： 終端用戶的需要終端用戶的需要-暫停執(zhí)行，查清問題。 父進(jìn)程的需求父進(jìn)程的需求-考查和修改子進(jìn)程，或要協(xié)調(diào)各子進(jìn)程間的活動(dòng)。 操作系統(tǒng)的需要操作系統(tǒng)的需要-檢查運(yùn)行中資源的使用情 況及進(jìn)行記帳，以便改善系統(tǒng)運(yùn)行的性能。 負(fù)荷調(diào)節(jié)的需要負(fù)荷調(diào)節(jié)的需要-當(dāng)實(shí)時(shí)系統(tǒng)中工作負(fù)荷較重影響對(duì)實(shí)時(shí)任務(wù)的控制時(shí)，系統(tǒng)把一些不重要的進(jìn)程掛起，以保證系統(tǒng)正常運(yùn)行。4) 進(jìn)程控制塊（pcb）process control block pcb：由系統(tǒng)維護(hù)用于記錄進(jìn)程基本情況信息，以對(duì)進(jìn)程實(shí)施控制與管理的輔助數(shù)據(jù)結(jié)構(gòu)（表）， pcbpcb

6、是是進(jìn)程存在進(jìn)程存在與否的與否的唯一標(biāo)志唯一標(biāo)志. .作用是使多道程序環(huán)境中不能獨(dú)立運(yùn)行的程序成為一個(gè)能獨(dú)立運(yùn)行的基本單位 pcb包含的內(nèi)容包含的內(nèi)容pcb中一般包括進(jìn)程描述信息、處理器狀態(tài)信息、進(jìn)程調(diào)度信息和進(jìn)程控制信息4部分。 具體內(nèi)容見下頁(yè)：進(jìn)程標(biāo)識(shí)符信息處理機(jī)狀態(tài)信息進(jìn)程調(diào)度信息進(jìn)程控制信息內(nèi)部標(biāo)識(shí)符外部標(biāo)識(shí)符通用寄存器指令計(jì)數(shù)器程序狀態(tài)字用戶棧指針進(jìn)程狀態(tài)進(jìn)程優(yōu)先級(jí)事件其它信息程序和數(shù)據(jù)的地址進(jìn)程同步和通信機(jī)制資源清單pcb 將處于同一狀態(tài)的進(jìn)程組織在一起將處于同一狀態(tài)的進(jìn)程組織在一起 同一狀態(tài)的進(jìn)程其pcb成一鏈表，多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的鏈表pcb14pcb2pcb3pcb4pcb

7、5pcb6pcb7pcb8pcb93087901執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針l 索引方式 同一狀態(tài)的進(jìn)程歸入一個(gè)index表（由index指向pcb）， 多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的index表執(zhí)行指針就緒索引表pcb1pcb2pcb3pcb4pcb5pcb6pcb7阻塞索引表就緒表指針阻塞表指針2.2 進(jìn)程控制 進(jìn)程控制進(jìn)程控制：進(jìn)程的創(chuàng)建、撤消，進(jìn)程狀態(tài)轉(zhuǎn)換的控 制。進(jìn)程控制由進(jìn)程控制原語(yǔ)和系統(tǒng)調(diào)用等在os內(nèi)核中實(shí)現(xiàn)，是os進(jìn)程管理的最基本功能。p 進(jìn)程創(chuàng)建p 進(jìn)程終止p 進(jìn)程的阻塞與喚醒p 進(jìn)程的掛起與激活 注：注：內(nèi)核：os的核心層部分，包括中斷處理、時(shí)鐘管理 原語(yǔ)：os內(nèi)核

8、中能完成某特定功能的小程序，其在執(zhí)行期間不允許被分割aa22a21a11a2a1n 進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程圖：描述進(jìn)程之間的創(chuàng)建關(guān)系的有向樹 子進(jìn)程可以繼承父進(jìn)程擁有的資源，撤銷父進(jìn)程時(shí)同時(shí)撤銷其所有子進(jìn)程子進(jìn)程可以繼承父進(jìn)程擁有的資源，撤銷父進(jìn)程時(shí)同時(shí)撤銷其所有子進(jìn)程, 父子進(jìn)程并發(fā)執(zhí)行，父進(jìn)程等待子進(jìn)程執(zhí)行結(jié)束父子進(jìn)程并發(fā)執(zhí)行，父進(jìn)程等待子進(jìn)程執(zhí)行結(jié)束 引起進(jìn)程創(chuàng)建的相關(guān)事件（因素）v用戶登陸（在分時(shí)系統(tǒng)中）v作業(yè)調(diào)度（在批處理系統(tǒng)中）v提供服務(wù)（用戶提出請(qǐng)求）v應(yīng)用請(qǐng)求（用戶程序引發(fā)） 進(jìn)程創(chuàng)建步驟及算法流程（創(chuàng)建原語(yǔ)調(diào)用create() ）a)為新進(jìn)程分配空白pcb表b)初始化pcb，分

9、配資源，填入相關(guān)數(shù)據(jù)c)置pcb狀態(tài)為就緒d)pcb插入就緒隊(duì)列，插入進(jìn)程家族樹n 進(jìn)程終止進(jìn)程終止引起進(jìn)程終止的因素v進(jìn)程正常運(yùn)行結(jié)束v出錯(cuò)或異常結(jié)束v外界干預(yù)，強(qiáng)行終止進(jìn)程終止的步驟及過程（終止原語(yǔ)）a)若被終止進(jìn)程正在執(zhí)行，則釋放cpub)終止（撤消）該進(jìn)程的所有子進(jìn)程c)釋放資源，歸還給父進(jìn)程或系統(tǒng)d)將其pcb從相關(guān)隊(duì)列中摘除，釋放pcbn 進(jìn)程阻塞與喚醒進(jìn)程阻塞與喚醒引起進(jìn)程阻塞（喚醒）的因素引起進(jìn)程阻塞（喚醒）的因素v請(qǐng)求系統(tǒng)服務(wù) （請(qǐng)求得到滿足）v啟動(dòng)某種操作 （操作完成）v等待新數(shù)據(jù)到達(dá) （新數(shù)據(jù)已送達(dá) ）v進(jìn)程完成任務(wù)，暫無(wú)事可做 （又有新任務(wù)）進(jìn)程阻塞的步驟及過程（阻塞或

10、睡眠原語(yǔ)）進(jìn)程阻塞的步驟及過程（阻塞或睡眠原語(yǔ)）a)暫停執(zhí)行，釋放cpub)置再（重新）調(diào)度標(biāo)志c)保存cpu現(xiàn)場(chǎng)信息d)置pcb狀態(tài)為阻塞，pcb插入對(duì)應(yīng)阻塞隊(duì)列進(jìn)程喚醒的步驟及過程（喚醒原語(yǔ)）進(jìn)程喚醒的步驟及過程（喚醒原語(yǔ)）a)將被喚醒進(jìn)程pcb從阻塞隊(duì)列中摘除b)置pcb狀態(tài)為就緒c)將pcb插入就緒隊(duì)列注：阻塞為自行操作，喚醒為他人行為。注：阻塞為自行操作，喚醒為他人行為。2.3 進(jìn)程同步1)進(jìn)程同步和互斥的相關(guān)概念n進(jìn)程同步：多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，必須協(xié)同工作、相互配合，以共同完成一項(xiàng)任務(wù)。n進(jìn)程互斥：由于共享資源所要求的排他性，進(jìn)程間要相互競(jìng)爭(zhēng)，以獲得這些資源的使用

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

12、案：進(jìn)程間存在直接制約和間接制約兩種制約關(guān)系，其中直接制約（同步）是由于進(jìn)程間的相互合作引起的；間接制約（互斥）是由于進(jìn)程間共享臨界資源引起的。 是間接制約，其中書是臨界資源 是間接制約，其中籃球是臨界資源 是直接制約，因?yàn)楦鞯拦ば蛐枰嗷ズ献?是直接制約，因?yàn)閮烧咭残枰献鳎荷唐飞a(chǎn)出來(lái)后才能被消費(fèi)；消費(fèi)后才需要再生產(chǎn)v臨界資源與臨界區(qū)臨界資源與臨界區(qū)（ critical sectioncritical section ） 進(jìn)程的互斥進(jìn)程的互斥（間接作用）（間接作用）由于現(xiàn)在操作系統(tǒng)中的進(jìn)程是并發(fā)執(zhí)行的，各進(jìn)程以自己的速度向前推進(jìn)，所以，運(yùn)行的順序可能是： p1：r1 = count； p2

13、：r2 = count； p1：r1 = r1 + 1； p1：count = r1； p2：r2 = r2 +1； p2：count = r2；錯(cuò)誤：錯(cuò)誤：p1,p2 p1,p2 執(zhí)行的結(jié)果執(zhí)行的結(jié)果countcount只加了只加了1 1臨界區(qū)臨界區(qū)剩余部分剩余部分進(jìn)入代碼進(jìn)入代碼退出代碼退出代碼dijkstradijkstra在在19651965年提出了三條準(zhǔn)則：年提出了三條準(zhǔn)則：（1 1）每次至多一個(gè)進(jìn)程處于臨界區(qū)）每次至多一個(gè)進(jìn)程處于臨界區(qū)（2 2）若有多個(gè)進(jìn)程同時(shí)要求進(jìn)入它們的臨界區(qū)，應(yīng)該在有）若有多個(gè)進(jìn)程同時(shí)要求進(jìn)入它們的臨界區(qū)，應(yīng)該在有限的時(shí)間內(nèi)讓其中一個(gè)進(jìn)入而不應(yīng)該相互阻塞限的

14、時(shí)間內(nèi)讓其中一個(gè)進(jìn)入而不應(yīng)該相互阻塞（3 3）進(jìn)程在臨界區(qū)中逗留有限時(shí)間）進(jìn)程在臨界區(qū)中逗留有限時(shí)間 臨界區(qū)的訪問臨界區(qū)的訪問n進(jìn)程同步及其應(yīng)遵守的規(guī)則 同步機(jī)制是指為實(shí)現(xiàn)對(duì)臨界資源互斥訪問的機(jī)制。所有的同步機(jī)制都應(yīng)遵循四條準(zhǔn)則： 空閑讓進(jìn)空閑讓進(jìn) 忙則等待忙則等待 有限等待有限等待 讓權(quán)等待讓權(quán)等待（有效利用資源）（有效利用資源） （對(duì)資源互斥訪問）（對(duì)資源互斥訪問） （避免陷入（避免陷入“死等死等”狀態(tài)）狀態(tài)） （避免陷入（避免陷入“忙等忙等”狀態(tài)）狀態(tài)） 2) 信號(hào)量機(jī)制信號(hào)量機(jī)制v整型信號(hào)量v記錄型信號(hào)量vand型信號(hào)量v信號(hào)量集整形信號(hào)量 dijkitra把整型信號(hào)量定義為一個(gè)整型量

15、s。除初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作即p操作wait(s)和v操作signal(s)來(lái)訪問。 wait和signal操作可描述為：wait(s)：while s0 do no-op s:s一1；signal(s)：s:s十1；注意：注意： s表示空閑資源數(shù)，p操作申請(qǐng)一個(gè)資源,v操作釋放一個(gè)資源。 缺點(diǎn): “忙等”，只要s0就不斷測(cè)試，未遵循“讓權(quán)等待” 。 p.v操作必須為原子操作 p.v操作必須成對(duì)出現(xiàn)。記錄型信號(hào)量機(jī)制增加一個(gè)進(jìn)程鏈表l，將等待同一臨界資源的進(jìn)程鏈成鏈表信號(hào)量信號(hào)量ss.v 信號(hào)量的值信號(hào)量的值s.l 信號(hào)量對(duì)應(yīng)資源等待隊(duì)列指針信號(hào)量對(duì)應(yīng)資源等待隊(duì)列指針p p（s

16、s）（）（waitwait（s s） s.v-s.v0 表示某類可用資源的數(shù)量 =0 其絕對(duì)值表示因請(qǐng)求該資源而被阻塞的進(jìn)程數(shù) s.v的初值為1時(shí)，表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量；實(shí)現(xiàn)進(jìn)程間的同步時(shí)，s.v初始值通常設(shè)為0或n。 利用信號(hào)量s和上述p,v操作實(shí)現(xiàn)進(jìn)程互斥時(shí)s.v的初值置為1的過程如下： p1p（s）臨界區(qū)臨界區(qū)1v（s）p2p（s）臨界區(qū)臨界區(qū)2v（s）and型信號(hào)量 將進(jìn)程在整個(gè)運(yùn)行過程中所需要的所有臨界資源，一次性地全部分配給進(jìn)程，待該進(jìn)程使用完后在一起釋放。對(duì)若干個(gè)臨界資源的分配，采取原子操作方式，要么全部分配到進(jìn)程，要么一個(gè)也不分配。信號(hào)量

17、集 基于p,v只能對(duì)信號(hào)量施以增1或減1的操作，當(dāng)需要n個(gè)資源時(shí)要執(zhí)行n次很低效。于是每次分配之前測(cè)試該資源的數(shù)量是否大于申請(qǐng)的資源數(shù)，通過對(duì)and信號(hào)量機(jī)制進(jìn)行兩方面擴(kuò)充，形成一般化的“信號(hào)量集”機(jī)制。用用p p、v v操作解決進(jìn)程間同步問題操作解決進(jìn)程間同步問題v用用p，v操作實(shí)現(xiàn)進(jìn)程同步的模型操作實(shí)現(xiàn)進(jìn)程同步的模型p1.v(s)p2p(s).12pp p1是p2的前趨，p2是p1的后繼v利用信號(hào)量與利用信號(hào)量與p.vp.v操作實(shí)現(xiàn)生產(chǎn)者操作實(shí)現(xiàn)生產(chǎn)者- -消費(fèi)者進(jìn)程同步消費(fèi)者進(jìn)程同步問題問題生產(chǎn)者消費(fèi)者一次只能放或取一個(gè)產(chǎn)品放產(chǎn)品取產(chǎn)品解答解答：?jiǎn)尉彌_區(qū)、一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者：設(shè)置私

18、用信號(hào)量為s1，s2，初值為1，0生產(chǎn)者進(jìn)程pwhile(true)生產(chǎn)一件產(chǎn)品;p(s1);/*申請(qǐng)一個(gè)空緩沖區(qū)*/放入一件產(chǎn)品；v(s2); /*釋放緩沖區(qū)*/消費(fèi)者進(jìn)程qwhile(true)p(s2); /*申請(qǐng)一個(gè)滿緩沖區(qū)*/拿出一件產(chǎn)品;v(s1);消費(fèi)產(chǎn)品;v用用p，v操作實(shí)現(xiàn)司機(jī)售票員同步操作實(shí)現(xiàn)司機(jī)售票員同步 解答：設(shè)置信號(hào)量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 p，v v操作所實(shí)現(xiàn)的司機(jī)售

19、票員同步過程操作所實(shí)現(xiàn)的司機(jī)售票員同步過程司機(jī)售票員同步過程（續(xù)）司機(jī)售票員同步過程（續(xù)）：注：司機(jī)到站-想繼續(xù)開車阻塞-售票員開車門注：司機(jī)到站-想繼續(xù)開車阻塞-售票員開車 門-想繼續(xù)開車門阻塞司機(jī)售票員同步過程（續(xù)）司機(jī)售票員同步過程（續(xù)）：注：司機(jī)到站-想繼續(xù)開車阻塞-售票員開車 門-想繼續(xù)開車門阻塞-司機(jī)繼續(xù)行車司機(jī)售票員同步過程（續(xù)）司機(jī)售票員同步過程（續(xù)）：用用p p、v v操作解決進(jìn)程間互斥問題操作解決進(jìn)程間互斥問題p(s)v(s)p1p2p3互斥區(qū)互斥區(qū)p(s)p(s)v(s)v(s) （設(shè)信號(hào)量（設(shè)信號(hào)量:s=1:s=1） 申請(qǐng)進(jìn)入申請(qǐng)進(jìn)入臨界區(qū)臨界區(qū)退出退出臨臨界區(qū)界區(qū)v用

20、用p，v操作實(shí)現(xiàn)進(jìn)程互斥的模型操作實(shí)現(xiàn)進(jìn)程互斥的模型v 用用p，v操作解決共享操作解決共享count變量的問題變量的問題執(zhí)行序列：執(zhí)行序列：p2p2執(zhí)行序列：執(zhí)行序列：p2p2（就緒）（就緒）-p1-p1（阻塞）（阻塞）- - 用用p，v操作解決共享操作解決共享count變量的問題（續(xù)）變量的問題（續(xù)）執(zhí)行序列：執(zhí)行序列：p2p2（就緒）（就緒）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞） 用用p，v操作解決共享操作解決共享count變量的問題（續(xù)）變量的問題（續(xù)）執(zhí)行序列：執(zhí)行序列：p2p2（就緒）（就緒）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞）- p2用用p，v

21、操作解決共享操作解決共享count變量的問題（續(xù)）變量的問題（續(xù)）執(zhí)行序列：執(zhí)行序列：p2p2（就緒）（就緒）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞）- p2-p1用用p，v操作解決共享操作解決共享count變量的問題（續(xù)）變量的問題（續(xù)）執(zhí)行序列：執(zhí)行序列：p2p2（就緒）（就緒）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞）- p2-p1-p3信號(hào)量變化范圍：信號(hào)量變化范圍：, , , , 即（即（-n-n）用用p，v操作解決共享操作解決共享count變量的問題（續(xù)）變量的問題（續(xù)）2.4 經(jīng)典的進(jìn)程同步問題經(jīng)典的進(jìn)程同步問題l 生產(chǎn)者生產(chǎn)者-消費(fèi)者問題消費(fèi)者問題

22、共享緩沖區(qū)生產(chǎn)指針消費(fèi)指針producer 1producer 2.producer mconsumer 1consumer 2.consumer n滿空指針移動(dòng)方向解析解析：n個(gè)緩沖區(qū)、k個(gè)生產(chǎn)者和m個(gè)消費(fèi)者：增加互斥信號(hào)量mutex，初值為1，并設(shè)s1，s2，初值分別為n和0。生產(chǎn)者進(jìn)程pwhile(true)生產(chǎn)一件產(chǎn)品;p(s1);/*申請(qǐng)一個(gè)空緩沖區(qū)*/p(mutex);放入一件產(chǎn)品；v(mutex);v(s2); /*釋放緩沖區(qū)*/消費(fèi)者進(jìn)程qwhile(true)p(s2); /*申請(qǐng)一個(gè)滿緩沖區(qū)*/p(mutex);拿出一件產(chǎn)品;v(mutex);v(s1);消費(fèi)產(chǎn)品;兩個(gè)p操

23、作交換？l讀者讀者-寫者問題寫者問題 對(duì)共享資源的讀寫操作，任一時(shí)刻“寫者”最多只允許一個(gè)，而“讀者”則允許多個(gè)“讀寫”互斥，“寫寫”互斥，“讀讀”允許 分分 析：寫進(jìn)程之間互斥，訪問時(shí)必須獨(dú)占資源。需設(shè)置析：寫進(jìn)程之間互斥，訪問時(shí)必須獨(dú)占資源。需設(shè)置一個(gè)全局變量對(duì)讀進(jìn)程進(jìn)行計(jì)數(shù)，當(dāng)?shù)谝粋€(gè)讀進(jìn)程開始進(jìn)一個(gè)全局變量對(duì)讀進(jìn)程進(jìn)行計(jì)數(shù)，當(dāng)?shù)谝粋€(gè)讀進(jìn)程開始進(jìn)行訪問時(shí)執(zhí)行行訪問時(shí)執(zhí)行p操作，當(dāng)最后一個(gè)讀進(jìn)程結(jié)束訪問時(shí)執(zhí)行操作，當(dāng)最后一個(gè)讀進(jìn)程結(jié)束訪問時(shí)執(zhí)行v操作。操作。解析：解析：現(xiàn)假設(shè)讀者優(yōu)先。使用readnum對(duì)讀者計(jì)數(shù)，初值為0；mutex是對(duì)readnum進(jìn)行互斥操作的信號(hào)量，初值為1；writ

24、e是寫信號(hào)量，初值為1。讀者進(jìn)程beginp(mutex);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)程beginp(write);write file;v(write);end第一個(gè)讀者來(lái)執(zhí)行p操作最后一個(gè)讀者來(lái)執(zhí)行v操作小結(jié)：信號(hào)量及小結(jié)：信號(hào)量及p.vp.v操作操作v信號(hào)量信號(hào)量（semaphoresemaphore）: :表示資源的實(shí)體，是一個(gè)與隊(duì)表示資源的實(shí)體，是一個(gè)與隊(duì)列有關(guān)

25、的整型變量，其值僅能由列有關(guān)的整型變量，其值僅能由p p、v v操作改變。操作改變。v信號(hào)量類型信號(hào)量類型：互斥互斥/ /公用信號(hào)量和同步公用信號(hào)量和同步/ /私用信號(hào)量私用信號(hào)量互斥信號(hào)量互斥信號(hào)量: :用于實(shí)現(xiàn)進(jìn)程間的互斥。初值通常設(shè)用于實(shí)現(xiàn)進(jìn)程間的互斥。初值通常設(shè)為為1 1，它所聯(lián)系的一組并行進(jìn)程均可對(duì)它實(shí)施，它所聯(lián)系的一組并行進(jìn)程均可對(duì)它實(shí)施p p、v v操作。操作。同步信號(hào)量：同步信號(hào)量：用于實(shí)現(xiàn)進(jìn)程間的同步，初始值通常用于實(shí)現(xiàn)進(jìn)程間的同步，初始值通常設(shè)為設(shè)為0 0或或n n，允許擁有它的進(jìn)程對(duì)其實(shí)施，允許擁有它的進(jìn)程對(duì)其實(shí)施p p操作。操作。v 對(duì)對(duì)p p，v v操作的使用應(yīng)注意：

26、操作的使用應(yīng)注意：p p原語(yǔ)相當(dāng)于原語(yǔ)相當(dāng)于進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)操作，操作，v v相當(dāng)于相當(dāng)于退出區(qū)退出區(qū)操作；遺操作；遺忘忘p p不能保證互斥訪問，遺忘不能保證互斥訪問，遺忘v v不能在使用后將資源不能在使用后將資源釋放給其他等待的進(jìn)程；釋放給其他等待的進(jìn)程； p p，v v操作都是操作都是成對(duì)出現(xiàn)成對(duì)出現(xiàn)的：的：互斥操作時(shí)，它們?cè)谕贿M(jìn)程中；同步操作時(shí)，它互斥操作時(shí)，它們?cè)谕贿M(jìn)程中；同步操作時(shí)，它們處于不同的進(jìn)程。們處于不同的進(jìn)程。在進(jìn)程中，在進(jìn)程中，p p操作的位置和次序至關(guān)重要。一般情況操作的位置和次序至關(guān)重要。一般情況下，對(duì)下，對(duì)互斥互斥信號(hào)量的信號(hào)量的p p操作操作在后在后。而。而v v

27、操作沒有特別操作沒有特別的限制。的限制。練習(xí)題1.設(shè)有一個(gè)作業(yè)有三個(gè)進(jìn)程組成，這三個(gè)進(jìn)程必須按如下所示的次序運(yùn)行，試用p,v操作表達(dá)三個(gè)進(jìn)程的同步關(guān)系。 t1t2t32. 用p,v操作實(shí)現(xiàn)下述問題的解。桌子上有一個(gè)盤子，可以存放一個(gè)水果。父親總是放蘋果到盤子里，而母親總是放香蕉到盤子里，但一次只能有一個(gè)人成功放入水果，若放入的是香蕉則允許兒子吃，女兒必須等待；若放入盤子的是蘋果則允許女兒吃，兒子必須等待。 2.5 進(jìn)程通信 低級(jí)通信低級(jí)通信：只傳送少量數(shù)據(jù)，且對(duì)用戶不透明高級(jí)通信高級(jí)通信：可傳送大量信息、數(shù)據(jù)，由o.s提供通信手段 并實(shí)施，對(duì)用戶來(lái)說透明1) 高級(jí)進(jìn)程通信類型高級(jí)進(jìn)程通信類型p

28、共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng)p消息傳遞系統(tǒng)消息傳遞系統(tǒng)p管道通信系統(tǒng)管道通信系統(tǒng)n 共享存儲(chǔ)器系統(tǒng)通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)行通信。可分為：通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)行通信?？煞譃椋?基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 例如：生產(chǎn)者-消費(fèi)者問題。屬低級(jí)通信 基于共享存儲(chǔ)區(qū)的通信方式基于共享存儲(chǔ)區(qū)的通信方式 共享非格式化的存儲(chǔ)區(qū)，公用的地址空間。屬高級(jí)通信方式。n 消息傳遞系統(tǒng)進(jìn)程間的數(shù)據(jù)交換以進(jìn)程間的數(shù)據(jù)交換以格式化格式化的的消息消息(measege)為單位，通過為單位，通過利用利用os提供的通信原語(yǔ)進(jìn)行通信，可分為：提供的通信原語(yǔ)進(jìn)行通信，可分為： 直接

29、通信方式直接通信方式-信息直接傳遞給接收方。 間接通信方式間接通信方式-發(fā)送進(jìn)程將消息發(fā)送到某種中間實(shí)體 中，接收進(jìn)程從中取得消息。 n 管道通信 工作原理：利用工作原理：利用管道管道進(jìn)行數(shù)據(jù)傳送進(jìn)行數(shù)據(jù)傳送發(fā)送進(jìn)程發(fā)送進(jìn)程pipe文件文件字符流型數(shù)據(jù)字符流型數(shù)據(jù)接收進(jìn)程接收進(jìn)程注：類似生產(chǎn)者注：類似生產(chǎn)者消費(fèi)者問題，要注意同步互斥的控制消費(fèi)者問題，要注意同步互斥的控制2) 消息通信的實(shí)現(xiàn)方法消息通信的實(shí)現(xiàn)方法n消息緩沖通信（直接通信方式）工作原理：進(jìn)程進(jìn)程a進(jìn)程進(jìn)程bpcb（b）send（b，a）receive（b）sender：asize：5text：hello發(fā)發(fā)送送區(qū)區(qū)amqsende

30、r：asize：5text：hellonext：0sender：asize：5text：hello接接收收區(qū)區(qū)b第一消息緩沖區(qū)第一消息緩沖區(qū)abmutexsm相關(guān)數(shù)據(jù)結(jié)構(gòu)消息結(jié)構(gòu)消息結(jié)構(gòu)：消息緩沖隊(duì)列消息緩沖隊(duì)列：pcb中用于消息通信的相關(guān)數(shù)據(jù)項(xiàng)中用于消息通信的相關(guān)數(shù)據(jù)項(xiàng)消息頭消息頭消息消息正文正文發(fā)送進(jìn)程標(biāo)識(shí)符、消息長(zhǎng)度、類型、發(fā)送進(jìn)程標(biāo)識(shí)符、消息長(zhǎng)度、類型、消息隊(duì)列鏈接指針消息隊(duì)列鏈接指針欲發(fā)送的信息數(shù)據(jù)存區(qū)欲發(fā)送的信息數(shù)據(jù)存區(qū)mqmutexsmpcb消息隊(duì)列隊(duì)首指針消息隊(duì)列隊(duì)首指針mq消 息 隊(duì) 列 互 斥 信 號(hào) 量消 息 隊(duì) 列 互 斥 信 號(hào) 量mutex消息隊(duì)列資源信號(hào)量消息隊(duì)列資源信號(hào)量sm（即隊(duì)列消息個(gè)數(shù)計(jì)數(shù)）（即隊(duì)列消息個(gè)數(shù)計(jì)數(shù)）消息緩沖區(qū)鏈成的隊(duì)列，每個(gè)進(jìn)程都有一個(gè)，其隊(duì)首指針存放在對(duì)應(yīng)進(jìn)程的pcb中消息發(fā)送原語(yǔ)和接收原語(yǔ)發(fā)送原語(yǔ)發(fā)送原語(yǔ) send（接收進(jìn)程名，發(fā)送區(qū)首地址）（接收進(jìn)程名，發(fā)送區(qū)首地址）接收原語(yǔ)接收原語(yǔ) receive（接收區(qū)地址）（接收區(qū)地址）注：緩沖隊(duì)列的插入、刪除操作必須采取互斥措施注：緩沖隊(duì)列的插入、刪除操作必須采取互斥措施 發(fā)送原語(yǔ)算法流程發(fā)送原語(yǔ)算法流程 接收原語(yǔ)算法流程接收原語(yǔ)算法流程申請(qǐng)分配一個(gè)空白緩沖區(qū)申請(qǐng)分配一個(gè)空白緩沖區(qū)將數(shù)據(jù)從發(fā)送區(qū)拷貝到緩沖正文區(qū)將數(shù)據(jù)從發(fā)送區(qū)拷貝到緩沖正文區(qū)獲取接收進(jìn)程獲取接收進(jìn)