第三講互斥與同步華軟軟件工程系第3章

主要章節(jié)教學(xué)要求本章目的：講述采用進(jìn)程互斥和同步手段合理地利用共享資源，分析了與時(shí)間有關(guān)的的錯(cuò)誤。然后講述并發(fā)處理中通常需要解決的兩個(gè)問(wèn)題：死鎖和餓死，分析處理死鎖的三種常用方法。教學(xué)目標(biāo)：進(jìn)程間的相互關(guān)系；互斥的概念；互斥的PV操作實(shí)現(xiàn)；同步的概念；同步的實(shí)現(xiàn)。重點(diǎn)與難點(diǎn)：互斥和同步的概念；PV操作；死鎖的防止與避免。專業(yè)術(shù)語(yǔ)：互斥、同步、臨界資源、臨界區(qū)、信號(hào)量、PV操作、原語(yǔ)、進(jìn)程的同步和互斥（1）多道程序環(huán)境下的問(wèn)題全局變量的共享充滿危險(xiǎn)資源的優(yōu)先分配對(duì)于OS來(lái)說(shuō)是困難的（處理不好可能死鎖），因其運(yùn)行過(guò)程的不可再現(xiàn)，程序錯(cuò)誤很難獲得OS至少需要解決的問(wèn)題OS必須能夠跟蹤進(jìn)程（通過(guò)PCB）OS為每個(gè)進(jìn)程分配資源（CPU、MEM、I/O等）OS必須保護(hù)每個(gè)進(jìn)程的相關(guān)信息和資源OS必須保證每個(gè)進(jìn)程的執(zhí)行結(jié)果與其他并發(fā)進(jìn)程執(zhí)行時(shí)的相對(duì)速度無(wú)關(guān)因此就有了合作進(jìn)程（同步）、互斥進(jìn)程、進(jìn)程死鎖、進(jìn)程阻塞等概念進(jìn)程的同步和互斥（2）合作進(jìn)程之間的相互協(xié)調(diào)以完成相關(guān)的操作，稱為進(jìn)程的同步。其實(shí)，互斥關(guān)系也是一種協(xié)調(diào)關(guān)系，從廣義上講，互斥可看成是一種特殊的同步。①只有當(dāng)司機(jī)啟動(dòng)車輛后售票員才能開(kāi)始售票②只有當(dāng)售票員關(guān)好車門后司機(jī)才能開(kāi)始開(kāi)車司機(jī)啟動(dòng)車輛正常行車到站停車售票員關(guān)車門售票開(kāi)車門進(jìn)程的同步和互斥（3）

現(xiàn)有進(jìn)程A和B，在某個(gè)系統(tǒng)中共用一臺(tái)打印機(jī)：（1）當(dāng)進(jìn)程A申請(qǐng)到打印機(jī)后，進(jìn)程B申請(qǐng)打印機(jī)時(shí)將被阻塞；（2）直到進(jìn)程A使用完畢，釋放打印機(jī)后，進(jìn)程B才能使用。（3）這種制約關(guān)系稱為間接制約關(guān)系，也為互斥關(guān)系?；コ膺M(jìn)程進(jìn)程的同步和互斥（4）例1：“單車道”公路上發(fā)生的事件進(jìn)程的死鎖解決方法：？進(jìn)程的同步和互斥（5）例2：城市街道交通阻塞現(xiàn)象進(jìn)程的阻塞解決方法：紅綠燈！進(jìn)程的同步和互斥（6）基本概念臨界資源：一次只能有一個(gè)進(jìn)程使用的獨(dú)占資源臨界區(qū)：包含有訪問(wèn)臨界資源的那段代碼（區(qū)）進(jìn)程的同步：合作進(jìn)程之間的執(zhí)行次序上的相互協(xié)調(diào)以完成相關(guān)的操作，稱為進(jìn)程的同步。也可稱：同步方式共享資源的進(jìn)程稱為進(jìn)程的同步。進(jìn)程的互斥：由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。也可稱：異步方式共享資源的進(jìn)程稱為進(jìn)程的互斥。進(jìn)程間互斥的必要條件：多個(gè)進(jìn)程共享同一臨界資源以先來(lái)先使用的異步方式共享進(jìn)程的同步和互斥（7）進(jìn)程的死鎖概念：一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程產(chǎn)生死鎖的原因系統(tǒng)資源不足進(jìn)程推進(jìn)的順序不合理死鎖的預(yù)防與避免運(yùn)行前預(yù)防：破壞死鎖發(fā)生的條件運(yùn)行中的避免，如銀行家算法運(yùn)行中解除,如資源剝奪和進(jìn)程撤消法進(jìn)程的同步和互斥（8）死鎖的一些結(jié)論：參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上的進(jìn)程才可能會(huì)出現(xiàn)死鎖）參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源進(jìn)程死鎖舉例打印機(jī)攝像頭進(jìn)程A進(jìn)程B占有占有等待等待死鎖一旦發(fā)生，將浪費(fèi)系統(tǒng)的大量資源，甚至導(dǎo)致系統(tǒng)崩潰！進(jìn)程的同步、互斥、死鎖、阻塞……等等，存在很多問(wèn)題！OS是如何解決的？！進(jìn)程的同步和互斥（7）饑餓概念：若有三個(gè)進(jìn)程p1，p2，p3，每個(gè)進(jìn)程都要周期地訪問(wèn)資源R。若p1先占有資源，p2和p3都被延遲、等待資源，當(dāng)p1離開(kāi)臨界段時(shí)，p2和p3都可分配到R。假設(shè)p3得到R，在p3完成其臨界段之前，p1又申請(qǐng)得到R，并且如果p1和p3重復(fù)得到R,則p2就不可避免地得不到資源，這時(shí)稱p2處于饑餓狀態(tài)。進(jìn)程的同步和互斥（9）OS的互斥機(jī)制OS的互斥機(jī)制必須滿足的要求：實(shí)現(xiàn)互斥：任何時(shí)刻最多只能一個(gè)進(jìn)程進(jìn)入臨界區(qū)執(zhí)行臨界區(qū)的進(jìn)程不能受其他進(jìn)程干擾進(jìn)程在臨界區(qū)執(zhí)行要有時(shí)間的限制申請(qǐng)進(jìn)入臨界段的進(jìn)程不能被無(wú)限期延遲，也不允許存在死鎖和饑餓當(dāng)臨界資源空閑時(shí)，允許進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)對(duì)于進(jìn)程的相對(duì)速度和數(shù)目，沒(méi)有限制臨界區(qū)的上鎖原語(yǔ)及開(kāi)鎖原語(yǔ)操作對(duì)臨界區(qū)操作，設(shè)置一個(gè)鎖位，假如為WW=0為臨界區(qū)空閑；W=1為臨界區(qū)被占用進(jìn)程進(jìn)入臨界區(qū)必須判斷W，并做相應(yīng)操作開(kāi)鎖原語(yǔ)臨界區(qū)上鎖原語(yǔ)進(jìn)程的同步和互斥（10）上鎖原語(yǔ)…{While(W==1);W=1;}進(jìn)入臨界區(qū)…開(kāi)鎖原語(yǔ)…{W=0;}…實(shí)現(xiàn)臨界區(qū)管理有軟件和硬件兩種方式軟件方法管理臨界區(qū)軟件方法可在共享主存的單處理機(jī)或多處理機(jī)系統(tǒng)中實(shí)現(xiàn)并發(fā)進(jìn)程，實(shí)施依據(jù)是內(nèi)存訪問(wèn)級(jí)別的基本互斥性，即對(duì)內(nèi)存同一位置的同時(shí)訪問(wèn)（讀/寫(xiě)）將被排序，而訪問(wèn)的順序并不預(yù)先指定。不需要硬件、操作系統(tǒng)或程序設(shè)計(jì)語(yǔ)言的任何支持Perterson算法（1981年）為每個(gè)進(jìn)程設(shè)置標(biāo)志flag用于表示該進(jìn)程是否有意訪問(wèn)臨界資源（進(jìn)入臨界區(qū)），又設(shè)置標(biāo)志turn用于表示臨界資源此時(shí)是否有其它進(jìn)程在訪問(wèn)硬件方式管理臨界區(qū)1）禁止中斷法在檢查臨界區(qū)標(biāo)志的兩條指令之前將中斷關(guān)上，臨界區(qū)訪問(wèn)完后系統(tǒng)才打開(kāi)中斷缺點(diǎn)：影響計(jì)算機(jī)效率、不能及時(shí)處理重要程序、對(duì)多CPU系統(tǒng)無(wú)效2）特殊指令法特殊的硬件指令保證幾個(gè)動(dòng)作的原子性——不會(huì)被中斷，不受到其它指令的干擾“測(cè)試并設(shè)置（TestandSet）”指令TS，或者交換（exchange）指令SWAPTS指令功能：Functiontestset(vari:integer):boolean;Begin ifi=0then begin i:=1; testset:=true end elsetestset:=falseend將布爾變量i與臨界區(qū)關(guān)聯(lián)起來(lái)——如果i為真，表示沒(méi)有進(jìn)程在臨界區(qū)內(nèi)，臨界資源可用，并立即將i置為false，即組織其它進(jìn)程進(jìn)入臨界區(qū)，訪問(wèn)臨界資源；若i為假，則表示有其它進(jìn)程進(jìn)入臨界區(qū)，本進(jìn)程需要等待。Exchange指令定義如下：Procedureexchange(varr:register;varm:memory); Vartemp;Begin temp:=m; m:=r; r:=tempEnd.可以用這個(gè)指令交換寄存器和內(nèi)存的內(nèi)容。在此指令執(zhí)行期間，任何訪問(wèn)同一內(nèi)存地址的指令將被阻塞。使用特殊的機(jī)器指令實(shí)現(xiàn)互斥的優(yōu)點(diǎn)：可用于含有任意數(shù)量進(jìn)程的單處理機(jī)或共享主存的多處理機(jī)；比較簡(jiǎn)單，容易驗(yàn)證；可支持多個(gè)臨界段。缺點(diǎn)：在進(jìn)程等待進(jìn)入臨界段時(shí)，將耗費(fèi)處理機(jī)時(shí)間；可能產(chǎn)生饑餓；可能產(chǎn)生死鎖。進(jìn)程的同步和互斥（11）進(jìn)程的同步進(jìn)程的同步問(wèn)題及互斥問(wèn)題多個(gè)進(jìn)程對(duì)于臨界資源的共享，共享方式?jīng)Q定：同步：以同步方式共享臨界資源互斥：以異步方式共享臨界資源同步問(wèn)題：指多個(gè)進(jìn)程的有先后順序的限制協(xié)作進(jìn)程之間一般存在的同步問(wèn)題：前驅(qū)后繼的同步問(wèn)題單緩沖與多緩沖讀寫(xiě)同步問(wèn)題生產(chǎn)者、消費(fèi)者同步問(wèn)題進(jìn)程的互斥是進(jìn)程同步的一種特殊情況。進(jìn)程同步機(jī)制常見(jiàn)的同步機(jī)制有鎖、信號(hào)量、管程和消息傳遞鎖機(jī)制的開(kāi)鎖和關(guān)鎖原語(yǔ)，主要用于解決互斥問(wèn)題，但效率低、浪費(fèi)CPU，加重編程負(fù)擔(dān)1965年E.W.Dijkstra引進(jìn)了比開(kāi)鎖和關(guān)鎖原語(yǔ)的更一般的形式——信號(hào)量與P/V操作來(lái)克服忙碌等待，極大地簡(jiǎn)化了進(jìn)程的同步與互斥管程（monitor），把分散在各進(jìn)程中的臨界區(qū)集中起來(lái)進(jìn)行管理，用數(shù)據(jù)結(jié)構(gòu)抽象表示共享資源，便于用高級(jí)語(yǔ)言寫(xiě)程序，也便于程序正確性驗(yàn)證用信號(hào)量能夠解決的同步問(wèn)題，同樣也可用管程解決信號(hào)量及其P、V操作(1)信號(hào)量機(jī)制概念：是操作系統(tǒng)提供的一種進(jìn)程通信的方式，主要用于進(jìn)程間的同步和互斥信號(hào)量為一2元組（s&q）：信號(hào)量ss為一非負(fù)初值的整型變量s>=0，表示可用資源數(shù)s<0，s的絕對(duì)值表示等待該資源的進(jìn)程數(shù)s值的改變只能通過(guò)系統(tǒng)調(diào)用實(shí)現(xiàn)q為一隊(duì)列:s的等待隊(duì)列，初始狀態(tài)為空隊(duì)列P操作和V操作也可以記為wait()和signal()，wait操作減小信號(hào)量的值，如果信號(hào)量的值為負(fù)，則執(zhí)行wait操作的進(jìn)程被阻塞；signal操作增加信號(hào)量的值，如果信號(hào)量的值不為正數(shù)時(shí)，被wait操作阻塞的進(jìn)程可以解除阻塞。信號(hào)量及其P、V操作(2)信號(hào)量的P、V操作PV操作是荷蘭數(shù)學(xué)教授狄克斯特拉首先提出的，P代表通過(guò)（荷蘭語(yǔ)：passeren)；V代表釋放（荷蘭語(yǔ)：vrijgeven

）PV操作執(zhí)行P操作申請(qǐng)信號(hào)量（執(zhí)行條件），V操作釋放信號(hào)量（釋放條件）PV操作將改變屬于共享變量的信號(hào)量PV操作是原語(yǔ)實(shí)現(xiàn)，不可中斷信號(hào)量及其P、V操作(3)P操作原語(yǔ)算法—請(qǐng)求資源或條件P(s){s--;if(s<0){

保留調(diào)用進(jìn)程的CPU現(xiàn)場(chǎng);

將該進(jìn)程插入s的等待隊(duì)列q;

置該進(jìn)程為等待態(tài);

轉(zhuǎn)進(jìn)程調(diào)度;}}信號(hào)量及其P、V操作(4)V操作原語(yǔ)算法—釋放資源或條件V(s){s++;if(s<=0){

移出s等待隊(duì)列q中的第一個(gè)進(jìn)程;

將該進(jìn)程插入就緒隊(duì)列;

置該進(jìn)程為就緒態(tài);}}信號(hào)量及其P、V操作(5)用PV操作實(shí)現(xiàn)進(jìn)程互斥設(shè)臨界資源的信號(hào)量為s，各進(jìn)程涉及臨界區(qū)操作如下：用PV操作實(shí)現(xiàn)進(jìn)程同步設(shè)某臨界資源的執(zhí)行條件信號(hào)量為s1、釋放條件信號(hào)量為s2，則進(jìn)程的臨界操作為：P(s1)；臨界區(qū)；V(s2)；P(s2)；臨界區(qū)；V(s1)；P(s)；臨界區(qū)；V(s)；1．互斥問(wèn)題舉例某車站售票廳有20個(gè)窗口，任何時(shí)刻最多可容納20名購(gòu)票者進(jìn)入，當(dāng)售票廳中少于20名購(gòu)票者時(shí)，則廳外的購(gòu)票者可立即進(jìn)入，否則需在廳外等待。若把一個(gè)購(gòu)票者看作是一個(gè)進(jìn)程，請(qǐng)用P、V操作管理這些并發(fā)進(jìn)程，要求（1）在主函數(shù)中給出信號(hào)量的定義和初值；（2）給出一個(gè)購(gòu)票者進(jìn)程的同步算法；（3）給出當(dāng)購(gòu)票者最多不超過(guò)n（設(shè)n>20）個(gè)時(shí)，信號(hào)量可能的變化范圍。（1）main（）{intmutex=20;cobeginp1();p2();p3();…pn();coend}1．互斥問(wèn)題舉例（2）購(gòu)票者i的算法

pi(){P(mutex);

進(jìn)入售票廳占有一個(gè)窗口購(gòu)票；

V(mutex);}(3)信號(hào)量mutex的取值范圍為-(n-20)<=mutex<=20,其物理含義是：當(dāng)mutex=20時(shí)，表示售票廳內(nèi)沒(méi)有購(gòu)票者進(jìn)入，20個(gè)窗口都是空閑的；當(dāng)mutex=0時(shí)，表示售票廳內(nèi)已經(jīng)進(jìn)入了20個(gè)購(gòu)票者，每個(gè)窗口都被分配，沒(méi)有等待的購(gòu)票者；當(dāng)mutex=-(n-20)，表示一共有n個(gè)購(gòu)票者，其中20個(gè)購(gòu)票者已經(jīng)進(jìn)入廳內(nèi)，還有n-20個(gè)購(gòu)票者在廳外等待。所以，當(dāng)mutex為負(fù)數(shù)時(shí)，其絕對(duì)值表示等待進(jìn)程的個(gè)數(shù)。進(jìn)程同步經(jīng)典問(wèn)題1．生產(chǎn)者-消費(fèi)者問(wèn)題E.W.Dijkstra把廣義同步問(wèn)題抽象成“生產(chǎn)者-消費(fèi)者問(wèn)題”（produce-consumerproblem）模型生產(chǎn)者-消費(fèi)者問(wèn)題：n個(gè)生產(chǎn)者進(jìn)程和m個(gè)消費(fèi)者進(jìn)程，連接在一塊長(zhǎng)度為k個(gè)單位的有界緩沖區(qū)上（故此問(wèn)題又稱有界緩沖問(wèn)題）。其中，Pi和Cj都是并發(fā)進(jìn)程，只要緩沖區(qū)未滿，生產(chǎn)者Pi生產(chǎn)的產(chǎn)品就可送入緩沖區(qū)；只要緩沖區(qū)不空，消費(fèi)者進(jìn)程Cj就可從緩沖區(qū)取走并消耗產(chǎn)品P1,p2,…,pnc1,c2,…,cn12…i…n生產(chǎn)者-消費(fèi)者問(wèn)題示意圖在并發(fā)環(huán)境下生產(chǎn)者、消費(fèi)者進(jìn)程訪問(wèn)緩沖區(qū)的速度不協(xié)調(diào)、不匹配——不同步，或者沒(méi)有做到互不影響地使用、更新緩沖區(qū)——互斥，所以會(huì)出現(xiàn)運(yùn)行錯(cuò)誤甚至是死鎖信號(hào)量機(jī)制解決多個(gè)生產(chǎn)者-消費(fèi)者、共享多個(gè)緩沖區(qū)的生產(chǎn)者-消費(fèi)者問(wèn)題Main()互斥分析：設(shè)互斥信號(hào)量mutex，初值為1.表示一次只{intfull=0;能進(jìn)一個(gè)生產(chǎn)者或消費(fèi)者進(jìn)程。

intempty=n;同步分析：生產(chǎn)者進(jìn)程的執(zhí)行條件是緩沖區(qū)中有空，設(shè)

intmutex=1;同步信號(hào)量empty，初值為n（有n個(gè)緩沖區(qū)），請(qǐng)求資

cobegin

源時(shí)執(zhí)行；消費(fèi)者進(jìn)程的執(zhí)行條件是緩沖區(qū)有產(chǎn)品，設(shè)

produceri();同步信號(hào)量full，初值為0，請(qǐng)求資源時(shí)執(zhí)行P（full）；

consumerj();生產(chǎn)者進(jìn)程釋放的條件是緩沖區(qū)中有產(chǎn)品，釋放資源執(zhí)行V(full)coend}；消費(fèi)者進(jìn)程釋放的條件是緩沖區(qū)有空，釋放資源執(zhí)行V(empty)producer_i(){//某個(gè)生產(chǎn)者進(jìn)程

while(生產(chǎn)未完成){

生產(chǎn)一個(gè)產(chǎn)品；

P(empty); //申請(qǐng)空緩沖區(qū)

P(mutex); //申請(qǐng)互斥使用緩沖區(qū)產(chǎn)品放入緩沖；//臨界區(qū)

V(mutex);//釋放臨界資源

V(full);}}consumer_j(){{//某個(gè)消費(fèi)者進(jìn)程

while(還要繼續(xù)消費(fèi)){P(full);//請(qǐng)求緩沖區(qū)有數(shù)可寫(xiě)條件

P(mutex);//請(qǐng)求進(jìn)入臨界區(qū)從緩沖區(qū)中取一個(gè)產(chǎn)品；//臨界區(qū)

V(mutex);//釋放臨界資源V(empty);//釋放緩沖區(qū)有空可讀條件消費(fèi)產(chǎn)品;}}信號(hào)量及其P、V操作(8)管程的引入臨界區(qū)的“上鎖”“開(kāi)鎖”操作都由用戶編寫(xiě)，加重了用戶負(fù)擔(dān)所有同步原語(yǔ)分散在程序代碼中，系統(tǒng)無(wú)法有效控制和管理這些同步原語(yǔ)用戶編程時(shí)難免會(huì)發(fā)生不正確使用同步原語(yǔ)操作的錯(cuò)誤。管程的概念管程是面向?qū)ο蟪绦蛟O(shè)計(jì)中的一種特殊對(duì)象，它將所使用的信號(hào)量以及對(duì)信號(hào)量的操作原語(yǔ)，封裝在一個(gè)對(duì)象內(nèi)部，這種針對(duì)信號(hào)量的對(duì)象稱為管程。信號(hào)量及其P、V操作(8)管程是一種并發(fā)性的結(jié)構(gòu)，它包括用于分配一個(gè)特定的共享資源或一組共享資源的數(shù)據(jù)和過(guò)程，管程由三部分組成：（1）局部于管程的共享變量說(shuō)明；（2）對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程；（3）對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。管程的基本特性只能通過(guò)管程中的過(guò)程而不能用其他外部過(guò)程訪問(wèn)其局部數(shù)據(jù)變量，這稱為信息掩蔽。進(jìn)程通過(guò)調(diào)用管程的過(guò)程，才能進(jìn)入管程訪問(wèn)共享數(shù)據(jù)每一時(shí)刻只能有一個(gè)進(jìn)程真正進(jìn)入管程內(nèi)部使用相應(yīng)系統(tǒng)資源，其它進(jìn)程必須等待，直至管程再次可用用管程實(shí)現(xiàn)同步CWait(C)：等待操作，調(diào)用進(jìn)程在條件C上掛起，并使管程成為可用。CSignal(C)：發(fā)信號(hào)操作，在條件C上被CWait掛起的進(jìn)程被再次執(zhí)行。如果有這樣的進(jìn)程，就選擇其中一個(gè)執(zhí)行，否則就什么都不做。見(jiàn)P89頁(yè)例子管程結(jié)構(gòu)示意管程與進(jìn)程的區(qū)別：管程把共享變量上的同步操作集中起來(lái)，而臨界區(qū)卻分散在每個(gè)進(jìn)程中；管程是為管理共享資源而建立的，進(jìn)程主要是為實(shí)現(xiàn)系統(tǒng)并發(fā)性而引入的；管程被進(jìn)程調(diào)用，管程和調(diào)用它的進(jìn)程不能并行工作，而進(jìn)程之間能并行工作，并發(fā)性是其固有特性；管程是語(yǔ)言或操作系統(tǒng)的組成部分，不必創(chuàng)建或撤銷，而進(jìn)程有生命周期2．讀者-寫(xiě)者問(wèn)題——兩組并發(fā)進(jìn)程，讀者和寫(xiě)者，共享一個(gè)文件F，要求：允許多個(gè)讀者進(jìn)程同時(shí)讀文件只允許一個(gè)寫(xiě)者進(jìn)程寫(xiě)文件任何一個(gè)寫(xiě)者進(jìn)程在完成寫(xiě)操作之前不允許其它讀者或?qū)懻吖ぷ鲗?xiě)者執(zhí)行寫(xiě)操作前，應(yīng)讓已有的寫(xiě)者和讀者全部退出兩種解決方法：讀者優(yōu)先和寫(xiě)者優(yōu)先消息傳遞的間接通信方式是指發(fā)送進(jìn)程與接收進(jìn)程之間通過(guò)郵箱來(lái)進(jìn)行通信，發(fā)送進(jìn)程將消息發(fā)送到郵箱，接收進(jìn)程