《os進(jìn)程同步》課件

軟件技術(shù)基礎(chǔ)制作主講段景山段景山處理機(jī)管理進(jìn)程的同步1精選課件ppt處理機(jī)的管理功能分為：進(jìn)程的描述進(jìn)程的控制進(jìn)程的同步進(jìn)程的通信進(jìn)程的調(diào)度處理機(jī)管理2精選課件ppt第三章進(jìn)程的同步與通信第二篇操作系統(tǒng)進(jìn)程的同步關(guān)系進(jìn)程的同步原則信號量進(jìn)程的通信3精選課件ppt進(jìn)程的同步進(jìn)程同步問題的提出進(jìn)程異步推進(jìn)可能造成混亂混亂可能導(dǎo)致不可再現(xiàn)進(jìn)程同步目標(biāo)維持進(jìn)程并發(fā)性以提高系統(tǒng)效率進(jìn)程執(zhí)行異步（斷續(xù)）資源的非封閉（共享）結(jié)果不可再現(xiàn)進(jìn)程同步進(jìn)程間相互合作資源有效共享結(jié)果可再現(xiàn)4精選課件ppt進(jìn)程的同步關(guān)系3.1進(jìn)程同步的基本概念進(jìn)程間的兩種主要關(guān)系臨界資源與臨界區(qū)進(jìn)程同步必須遵循的原則3.1.1進(jìn)程間的兩種主要關(guān)系進(jìn)程間的關(guān)系與進(jìn)程間的獨(dú)立性進(jìn)程間的關(guān)系是在進(jìn)程間相對獨(dú)立的前提下發(fā)展的獨(dú)立獲得資源獨(dú)立調(diào)度5精選課件ppt進(jìn)程間的同步關(guān)系（一）正常行車到站停車開車售票開車門關(guān)車門司機(jī)售票員合作合作檢查車況維持秩序6精選課件ppt獲得打印數(shù)據(jù)進(jìn)程間的同步關(guān)系（二）打印進(jìn)程1打印進(jìn)程2打印打印互斥獲得打印數(shù)據(jù)7精選課件ppt進(jìn)程間的同步關(guān)系（三）計算進(jìn)程打印進(jìn)程計算結(jié)果送到Buffer從Buffer中取數(shù)Buffer互斥完成數(shù)據(jù)計算打印通知打印進(jìn)程打印通知計算進(jìn)程送下一個數(shù)合作8精選課件ppt進(jìn)程間的同步關(guān)系相互合作競爭資源司機(jī)與售票員多個打印者計算者與打印者9精選課件ppt正常行車到站停車開車售票開車門關(guān)車門司機(jī)售票員同步同步到站停車否是檢查車況維持秩序否關(guān)車門是10精選課件ppt同步實現(xiàn)初探（二）打印進(jìn)程1打印進(jìn)程2打印打印互斥獲得打印數(shù)據(jù)獲得打印數(shù)據(jù)打印機(jī)可用？設(shè)置打印機(jī)為不可用是否打印機(jī)可用？設(shè)置打印機(jī)為不可用是否11精選課件ppt同步實現(xiàn)初探（三）計算進(jìn)程打印進(jìn)程計算結(jié)果送到Buffer從Buffer中取數(shù)Buffer互斥互斥向打印進(jìn)程發(fā)信號通知其從Buffer里取數(shù)Buffer空？否是完成數(shù)據(jù)計算打印向計算進(jìn)程發(fā)信號通知其向Buffer送數(shù)Buffer空？否是合作12精選課件ppt進(jìn)程間的同步關(guān)系進(jìn)程同步時面臨的兩種主要關(guān)系相互合作競爭資源司機(jī)與售票員多個打印者計算者與打印者事件、設(shè)備等抽象為資源對進(jìn)程間關(guān)系的處理變?yōu)閷Y源的訪問方式13精選課件ppt臨界資源3.1.2臨界資源與臨界區(qū)(1)臨界資源一次只允許一個進(jìn)程訪問的資源資源狀態(tài)為臨界：0或1(2)臨界區(qū)每個進(jìn)程用于訪問臨界資源的那段程序同類臨界區(qū)：同類資源的臨界區(qū)進(jìn)入?yún)^(qū)退出區(qū)最簡單的資源14精選課件ppt臨界區(qū)進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)........................阻塞等待資源釋放改變資源狀態(tài)釋放資源喚醒等待進(jìn)程進(jìn)程1進(jìn)程215精選課件ppt同步四原則3.1.3同步機(jī)制應(yīng)遵循的原則空閑讓進(jìn)忙則等待有限等待讓權(quán)等待16精選課件ppt同步原則進(jìn)程同步應(yīng)遵循的原則空閑讓進(jìn)當(dāng)資源空閑時，應(yīng)當(dāng)允許訪問資源的進(jìn)程進(jìn)入臨界區(qū)忙則等待當(dāng)資源被占用時，應(yīng)使申請訪問該資源的進(jìn)程等待，等待使用者歸還資源兩個基本原則，必須遵循17精選課件ppt同步原則進(jìn)程同步應(yīng)遵循的原則讓權(quán)等待在進(jìn)程等待資源時，從執(zhí)行態(tài)轉(zhuǎn)為阻塞態(tài)，應(yīng)當(dāng)讓出CPU的使用權(quán)。系統(tǒng)將把CPU分配給其它進(jìn)程使用，以提高系統(tǒng)效率有限等待系統(tǒng)應(yīng)保證等待的進(jìn)程能在有限的時間內(nèi)獲得資源，繼續(xù)執(zhí)行，以防止無限等待浪費(fèi)該進(jìn)程已占用的資源18精選課件ppt鎖機(jī)制3.1.4臨界資源鎖機(jī)制例：商場的試衣間是互斥資源是臨界資源是共享資源每個顧客必須遵循以下過程使用試衣間：靠鎖實現(xiàn)資源的共享管理觀察鎖狀態(tài)關(guān)鎖使用試衣間開鎖19精選課件ppt鎖機(jī)制臨界資源鎖機(jī)制鎖鎖變量L每個進(jìn)程必須按照以下過程操作資源L=1關(guān)閉狀態(tài)，資源忙L=0打開狀態(tài)，資源空閑抽象L=1臨界區(qū)L=0……20精選課件ppt鎖機(jī)制實現(xiàn)一種簡單的鎖操作實現(xiàn)voidlock(L){check: if(L==1) gotocheck; else L=1;}voidunlock(L){ L=0;}21精選課件ppt鎖機(jī)制實現(xiàn)............check:if(L==1){ gotocheck;elseL=1;臨界區(qū)L進(jìn)程1進(jìn)程2unlock(L);......check:if(L==1){ gotocheck;elseL=1;臨界區(qū)unlock(L);......0101022精選課件ppt鎖操作模型鎖操作的一般模型Pi：......lock(L)C(i)unlock(L).........Pj：......lock(L)C(j)unlock(L).........C(i)：Pi的臨界區(qū)Pi：進(jìn)程i23精選課件ppt出了問題的鎖............check:if(L==1){ gotocheck;elseL=1;臨界區(qū)unlock(L);......check:if(L==1){ gotocheck;elseL=1;臨界區(qū)unlock(L);......出現(xiàn)問題的鎖進(jìn)程1進(jìn)程2L01尚未執(zhí)行問題出在？判斷狀態(tài)后改變狀態(tài)前被打斷24精選課件ppt鎖機(jī)制實現(xiàn)關(guān)鎖操作不可被打斷用原語實現(xiàn)關(guān)鎖操作關(guān)鎖操作在一個指令周期內(nèi)完成（1）引入TS的操作（2）采用“exchange”(swap)指令利用特殊硬件機(jī)制和指令，使關(guān)鎖操作在一個指令周期內(nèi)完成（3）與中斷控制相結(jié)合實現(xiàn)鎖操作在執(zhí)行原語過程中關(guān)閉中斷軟件方法硬件方法25精選課件pptTS鎖TS寄存器，各進(jìn)程一個TS＝0L==0？TS＝1L＝1TS＝0？1個指令周期內(nèi)完成26精選課件ppt鎖與中斷通過開、關(guān)中斷，保證關(guān)鎖操作不被打斷L==0？L＝1關(guān)中斷開中斷開中斷是否27精選課件ppt鎖操作特點(diǎn)鎖操作的特點(diǎn)：實現(xiàn)了進(jìn)程互斥訪問臨界資源。不遵循讓權(quán)等待原則?！Φ萀==0？L＝1關(guān)中斷開中斷開中斷是否28精選課件ppt信號量機(jī)制3.2進(jìn)程同步的信號量機(jī)制（semaphore）經(jīng)典信號量、記錄型信號量、信號量集3.2.1信號量機(jī)制的基本概念（1）信號量信號量是對具體物理資源的抽象不同類的資源用不同名稱的信號量代表同類資源的個數(shù)用>0的信號量值表示信號量值為0或1的信號量表示臨界資源信號量是比鎖更高級的資源抽象方式29精選課件ppt經(jīng)典信號量（2）經(jīng)典信號量的P，V操作資源的申請與釋放－－原語信號量：SP（s）s<=0?s=s-1NYV（s）s=s+1申請一個資源釋放一個資源忙等臨界區(qū)/資源訪問區(qū)30精選課件ppt信號量機(jī)制類型3.2.2三種信號量機(jī)制（1）經(jīng)典信號量（2）記錄型信號量（3）信號量集（4）一般信號量集機(jī)制31精選課件ppt記錄型信號量（2）記錄型信號量引入進(jìn)程阻塞機(jī)制在信號量里增加對阻塞進(jìn)程的紀(jì)錄typedefstructSemaphore{ intvalue; process_list*list;}semaphore;資源個數(shù)阻塞進(jìn)程（PCB）隊列32精選課件ppt紀(jì)錄型信號量的P，V操作P(s)s.value=s.value-1s.value<0?本進(jìn)程獲得一個資源臨界區(qū)/資源訪問區(qū)本進(jìn)程進(jìn)入s.list隊列，進(jìn)入阻塞狀態(tài)NYV(s)s.value=s.value+1s.value<=0?將s.list中第一個進(jìn)程喚醒，NY33精選課件ppt紀(jì)錄型信號量機(jī)制特點(diǎn)：s.value的含義大于0等于0小于0是否遵循讓權(quán)等待？阻塞隊列，阻塞機(jī)制記錄型信號量特點(diǎn)34精選課件ppt紀(jì)錄型信號量機(jī)制特點(diǎn)：進(jìn)程對資源訪問的過程：原語保證p（），v（）操作都是原語保證不出現(xiàn)“鎖不住”資源的現(xiàn)象記錄型信號量特點(diǎn)......P(s)進(jìn)入臨界區(qū)V(s)......s為0時進(jìn)程會進(jìn)入阻塞狀態(tài)35精選課件ppt記錄型信號量特點(diǎn)紀(jì)錄型信號量機(jī)制特點(diǎn)：主動阻塞與被動喚醒P(s)s.value=s.value-1s.value<0?本進(jìn)程獲得一個資源臨界區(qū)/資源訪問區(qū)本進(jìn)程進(jìn)入s.list隊列，進(jìn)入阻塞狀態(tài)NYV(s)s.value=s.value+1s.value<=0?將s.list中第一個進(jìn)程喚醒，NY喚醒后的進(jìn)程從這里開始36精選課件ppt信號量集（3）信號量集引入原因基本思想流程37精選課件ppt信號量集引入原因P1（S1）；P1（S2）；P2（S2）；P2（S1）；進(jìn)程1進(jìn)程2系統(tǒng)推進(jìn)過程為P1（S1）；P2（S2）；P2（S1）；P1（S2）；進(jìn)程2阻塞進(jìn)程1阻塞S1S2進(jìn)程1和進(jìn)程2都無法繼續(xù)推進(jìn)出現(xiàn)死鎖。。。。。。V(S2);V(S1);V(S1);V(S2);38精選課件ppt信號量集基本思想基本思想將多次對多個信號量的申請改為一次，用一個原子操作完成進(jìn)程要么一次獲得所有的資源，要么一個也申請不到不會存在互相等待的局面信號量集SP（S1，S2，S3……Sn）39精選課件ppt信號量集流程信號量集流程SP（S1，S2，S3……Sn）S1>＝1?S2>＝1?。。。S1=S1－1；S2=S2－1；……Sn=Sn－1；NN本進(jìn)程進(jìn)入Si<1的第一個Si的阻塞隊列中，并將進(jìn)程的程序指針設(shè)到SP（）的開頭40精選課件ppt信號量集流程信號量集流程SV（S1，S2，S3……Sn）S1=S1＋1；S2=S2＋1；……Sn=Sn＋1；將Si隊列中第一個等待進(jìn)程喚醒41精選課件ppt信號量集流程P1（S1）；P1（S2）；進(jìn)程1P2（S2）；P2（S1）；進(jìn)程2SP1（S1,S2）SP2（S1,S2）SP1（S1,S2）SP2（S1,S2）系統(tǒng)推進(jìn)SP1（S1,S2）SP2（S1,S2）或42精選課件ppt一般信號量集（4）一般信號量集引入原因更靈活基本思想si：各信號量ti：申請下限ti>0時，可進(jìn)行資源預(yù)留di：申請個數(shù)一次可申請一種資源的多個SP（S1,t1,d1,……Sn,tn,dn)43精選課件ppt資源競爭3.3經(jīng)典進(jìn)程同步問題資源競爭時的進(jìn)程同步對競爭資源的互斥訪問…P（s）臨界區(qū)V（s）進(jìn)程1進(jìn)程2……P（s）臨界區(qū)V（s）…P（s）訪問資源V（s）狀態(tài)：狀態(tài)：喚醒就緒執(zhí)行就緒執(zhí)行阻塞44精選課件ppt相互合作時的進(jìn)程同步保證進(jìn)程間的前驅(qū)、后繼關(guān)系相互合作司機(jī)進(jìn)程正常行車到站停車V（停車）喝茶P（關(guān)車門）正常行車售票P（停車）開車門關(guān)車門V（關(guān)車門）售票售票員進(jìn)程同步點(diǎn)同步點(diǎn)V（s）P（s）前驅(qū)后繼信號量初值為045精選課件ppt公用與私用信號量公用信號量：私用信號量：一組進(jìn)程共享，都可進(jìn)行P、V操作用于進(jìn)程間資源的競爭擁有信號量的進(jìn)程只對信號量進(jìn)行P操作V操作由其他進(jìn)程進(jìn)行用于進(jìn)程間的合作P（s）V（s）訪問資源P（s）V（s）訪問資源進(jìn)程1：進(jìn)程2：P（s）V（s）后繼進(jìn)程：前驅(qū)進(jìn)程：46精選課件ppt經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題生產(chǎn)者——消費(fèi)者問題讀者——寫者問題哲學(xué)家進(jìn)餐問題47精選課件ppt生產(chǎn)者消費(fèi)者問題3.3.1生產(chǎn)者——消費(fèi)者問題問題描述:有多個生產(chǎn)者在生產(chǎn)消息有多個消費(fèi)者在消費(fèi)消息消費(fèi)者消費(fèi)的是生產(chǎn)者生產(chǎn)的消息48精選課件ppt生產(chǎn)者消費(fèi)者問題消息緩沖池生產(chǎn)者產(chǎn)生的消息放入緩沖池內(nèi)；消費(fèi)者從緩沖池內(nèi)取走消息消費(fèi)；消費(fèi)者消費(fèi)后的空白消息塊放進(jìn)空白緩沖池內(nèi)供生產(chǎn)者使用。生產(chǎn)者消費(fèi)者消息緩沖池空白塊緩沖池2312149精選課件ppt生產(chǎn)者消費(fèi)者算法分析算法分析兩類進(jìn)程：生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程（1）進(jìn)程間的關(guān)系生產(chǎn)者生產(chǎn)消息后消費(fèi)者消費(fèi)消費(fèi)者消費(fèi)后的空白緩沖塊由生產(chǎn)者生產(chǎn)消息P（s）V（s）后繼進(jìn)程：前驅(qū)進(jìn)程：P（s）V（s）后繼進(jìn)程：前驅(qū)進(jìn)程：P（full）V（full）生產(chǎn)者：消費(fèi)者：生產(chǎn)者：消費(fèi)者：P（empty）V（empty）50精選課件ppt生產(chǎn)者消費(fèi)者算法分析（2）隊列的操作兩個共享隊列：消息緩沖隊列空白緩沖隊列多個進(jìn)程共享一個隊列是否需要保護(hù)消息緩沖池空白塊緩沖池生產(chǎn)者放入消息取空白塊生產(chǎn)者消費(fèi)者消費(fèi)者取走消息放空白塊51精選課件ppt生產(chǎn)者消費(fèi)者算法分析入隊操作newmsg->next=msglist->head;msglist->head=newmsg;msglist->headnewmsg52精選課件ppt隊列操作同時入隊進(jìn)程1進(jìn)程2newmsg1->next=msglist->head;msglist->head=newmsg1;msglist->headnewmsg1newmsg2兩個message都掛到了隊列上就緒執(zhí)行就緒執(zhí)行newmsg2->next=msglist->head;msglist->head=newmsg2;53精選課件ppt出了問題的隊列操作同時入隊進(jìn)程1進(jìn)程2newmsg1->next=msglist->head;msglist->head=newmsg1;msglist->headnewmsg1newmsg2隊列操作過程需要互斥進(jìn)行就緒執(zhí)行就緒執(zhí)行newmsg2->next=msglist->head;msglist->head=newmsg2;54精選課件ppt出了問題的隊列操作同時入隊進(jìn)程1進(jìn)程2newmsg1->next=msglist->head;msglist->head=newmsg1;msglist->headnewmsg1newmsg2就緒執(zhí)行就緒執(zhí)行newmsg2->next=msglist->head;msglist->head=newmsg2;55精選課件ppt生產(chǎn)者消費(fèi)者算法分析進(jìn)程間的關(guān)系生產(chǎn)者生產(chǎn)消息后消費(fèi)者消費(fèi)的合作關(guān)系消費(fèi)者消費(fèi)后的空白緩沖塊由生產(chǎn)者生產(chǎn)消息的合作關(guān)系進(jìn)程間在隊列操作上的互斥關(guān)系P（s）V（s）訪問資源P（s）V（s）訪問資源進(jìn)程1：進(jìn)程2：P（mutex）V（mutex）P（mutex）V（mutex）操作隊列操作隊列56精選課件ppt生產(chǎn)者消費(fèi)者算法分析信號量full：私有信號量empty：私有信號量mutex：公用信號量隊列full_list：消息隊列empty_list：空白塊隊列57精選課件ppt生產(chǎn)者消費(fèi)者算法流程生產(chǎn)者產(chǎn)生一個消息；申請一個空白緩沖區(qū)；從空白隊列中取一個空白緩沖區(qū)；申請隊列操作的互斥；釋放隊列操作的互斥；在空白緩沖區(qū)內(nèi)填充消息消息放入消息隊列申請隊列操作的互斥；釋放隊列操作的互斥；釋放一個消息信號消費(fèi)者申請一個消息申請隊列操作的互斥；釋放隊列操作的互斥從消息隊列中取一個消息；消費(fèi)消息將消息清空為空白空白塊放入空白隊列申請隊列操作的互斥；釋放隊列操作的互斥；釋放一個空白塊信號58精選課件pptvoidproducer(){while(1){create(msg);P(empty);P(mutex);buffer=pop(empty_list)；V(mutex);fill_buffer(buffer,msg);P(mutex);push(full_list,buffer);V(mutex);V(full);}}semaphorefull={0,NULL};semaphoreempty={n,NULL};semaphoremutex={1,NULL};voidconsumer(){while(1){P(full);P(mutex);msg=pop(full_list)；V(mutex);consume(msg);fill_zero(msg);P(mutex);push(empty_list,msg);V(mutex);V(empty);}}59精選課件ppt生產(chǎn)者消費(fèi)者算法小結(jié)小結(jié)：在分析進(jìn)程同步問題中，逐個分析進(jìn)程間的關(guān)系是關(guān)鍵不管多復(fù)雜的關(guān)系，總能歸結(jié)為兩種基本關(guān)系（競爭與合作），總是這兩種關(guān)系的組合不管公用還是私用，信號量的使用必須成對出現(xiàn)思考多個生產(chǎn)者之間是什么關(guān)系，需要特別的實現(xiàn)嗎？多個消費(fèi)者之間是什么關(guān)系，需要特別的實現(xiàn)嗎？60精選課件ppt讀者寫者問題3.3.2讀者——寫者問題 （ReaderandWriter）問題描述一個數(shù)據(jù)紀(jì)錄，有多個進(jìn)程進(jìn)行讀操作，另一些進(jìn)程進(jìn)行修改操作（Reader）（Writer）讀寫策略允許多個進(jìn)程同時進(jìn)行讀操作——讀不互斥不允許多于一個進(jìn)程進(jìn)行寫操作——寫互斥不允許讀寫操作同時進(jìn)行——讀寫互斥61精選課件ppt讀者寫者問題分析讀者寫者讀操作寫操作p（mutex）v（mutex）p（mutex）v（mutex）寫者之間互斥讀者與寫者之間互斥讀者之間互斥62精選課件ppt哲學(xué)家問題3.3.3哲學(xué)家進(jìn)餐問題問題描述五位哲學(xué)家圍桌而坐哲學(xué)家在思考問題時不需要任何資源，思考完問題后進(jìn)入進(jìn)餐態(tài)。每人必須獲得左右兩支筷子才能進(jìn)餐思考思考思考思考思考準(zhǔn)備進(jìn)餐進(jìn)餐準(zhǔn)備進(jìn)餐進(jìn)餐63精選課件ppt哲學(xué)家問題分析死鎖思考思考思考思考思考準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐思考p（left_stick）p（right_stick)v（right_stick)v（left_stick）eat64精選課件ppt管程機(jī)制3.4管程機(jī)制（自學(xué)）3.4.1引入原因過多信號量的使用，容易造成死鎖3.4.2管程的基本概念把數(shù)據(jù)及其上的一組操作看作一個整體——管程3.4.3管程組成局部于管程的局部變量局部于管程的數(shù)據(jù)初值設(shè)置在數(shù)據(jù)上的一組操作65精選課件ppt管程機(jī)制3.4