同步通信與死鎖

《同步通信與死鎖》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第三章同步、通信與死鎖2010年10月第三章并發(fā)進(jìn)程3.1并發(fā)進(jìn)程3.2臨界區(qū)管理3.3信號(hào)量與PV操作3.4管程3.5進(jìn)程通信3.6死鎖3.7Linux同步機(jī)制和通信機(jī)制3.8Windows2003同步機(jī)制和通信機(jī)制3.1并發(fā)進(jìn)程3.1.1順序程序設(shè)計(jì)3.1.2進(jìn)程的并發(fā)性3.1.3進(jìn)程的交互：協(xié)作和競(jìng)爭(zhēng)進(jìn)程的順序性一個(gè)進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的，一個(gè)進(jìn)程只有當(dāng)一個(gè)操作結(jié)束后，才能開始后繼操作順序程序設(shè)計(jì)是把一個(gè)程序設(shè)計(jì)成一個(gè)順序執(zhí)行的程序模塊，順序的含義不但指一個(gè)程序模塊內(nèi)部，也指兩個(gè)程序模塊之間

2、。順序程序設(shè)計(jì)特點(diǎn)程序執(zhí)行的順序性程序環(huán)境的封閉性程序執(zhí)行結(jié)果的確定性計(jì)算過程的可再現(xiàn)性進(jìn)程的并發(fā)性(1)進(jìn)程執(zhí)行的并發(fā)性：一組進(jìn)程的執(zhí)行在時(shí)間上是重疊的。并發(fā)性舉例：有兩個(gè)進(jìn)程A(a1、a2、a3)和B(b1、b2、b3)并發(fā)執(zhí)行。從宏觀上看，并發(fā)性反映一個(gè)時(shí)間段中幾個(gè)進(jìn)程都在同一處理器上，處于運(yùn)行還未運(yùn)行結(jié)束狀態(tài)。從微觀上看，任一時(shí)刻僅有一個(gè)進(jìn)程在處理器上運(yùn)行。進(jìn)程的并發(fā)性(2)進(jìn)程i1p1ipoo1i2p2o2i3p3o3t1t2t3時(shí)間并行工作i4t4i5P4進(jìn)程的并發(fā)性(3)并發(fā)的實(shí)質(zhì)是一個(gè)處理器在幾

3、個(gè)進(jìn)程之間的多路復(fù)用，并發(fā)是對(duì)有限的物理資源強(qiáng)制行使多用戶共享，消除計(jì)算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。無關(guān)的并發(fā)進(jìn)程并發(fā)進(jìn)程分類：無關(guān)的，交往的。無關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個(gè)進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)。并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時(shí)間無關(guān)的一個(gè)充分條件，又稱為Bernstein條件。Bernstein條件R(pi)={a1,a2,…an}，程序pi在執(zhí)行期間引用的變量集W(pi)={b1,b2,…bm}，程序pi在執(zhí)行期間改變的變量集若兩個(gè)程序的變量集交集

4、之和為空集：R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}則并發(fā)進(jìn)程的執(zhí)行與時(shí)間無關(guān)。Bernstein條件舉例例如，有如下四條語句：S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1于是有：R(S1)={x,y},R(S2)={z}，R(S3)={a,b}，R(S4)={c}；W(S1)={a},W(S2)=，W(S3)={c}，W(S4)={w}。S1和S2可并發(fā)執(zhí)行，滿足Bernstein條件。其他語句并發(fā)執(zhí)行可能會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。交往的并發(fā)

5、進(jìn)程交往的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程共享某些變量，一個(gè)進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的結(jié)果。并發(fā)程序設(shè)計(jì)的優(yōu)點(diǎn)?對(duì)于單處理器系統(tǒng),可讓處理器和各I/O設(shè)備同時(shí)工作,發(fā)揮硬部件的并行能力。?對(duì)于多處理器系統(tǒng),可讓各進(jìn)程在不同處理器上物理地并行，加快計(jì)算速度。?簡(jiǎn)化了程序設(shè)計(jì)任務(wù)。采用并發(fā)程序設(shè)計(jì)的目的充分發(fā)揮硬件的并行性，提高系統(tǒng)效率。硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實(shí)現(xiàn)需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計(jì)。并發(fā)程序設(shè)計(jì)是多道程序設(shè)計(jì)的基礎(chǔ)，多道程序的實(shí)質(zhì)就是把并發(fā)程序設(shè)計(jì)引入到

6、系統(tǒng)中。與時(shí)間有關(guān)的錯(cuò)誤對(duì)于一組交往的并發(fā)進(jìn)程，執(zhí)行的相對(duì)速度無法相互控制，各種與時(shí)間有關(guān)的錯(cuò)誤就可能出現(xiàn)。與時(shí)間有關(guān)錯(cuò)誤的表現(xiàn)形式：結(jié)果不唯一永遠(yuǎn)等待（結(jié)果不唯一）機(jī)票問題//飛機(jī)票售票問題voidT1(){voidT2(){{按旅客訂票要求找到Aj};{按旅客訂票要求找到Aj};intX1=Aj;intX2=Aj;if(X1>=1){if(X2>=1){X1--;X2--;Aj=X1;Aj=X2;{輸出一張票};{輸出一張票};}}elseelse{輸出信息"票已售完"};{輸出信息"票已售完"};}}（永

7、遠(yuǎn)等待）主存管理問題申請(qǐng)和歸還主存資源問題intX=memory;//memory為初始主存容量voidborrow(intB){voidreturn(intB){while(B>X)X=X+B;{進(jìn)程進(jìn)入等待主存資源隊(duì)列};{修改主存分配表};X=X-B;{釋放等主存資源進(jìn)程};{修改主存分配表，進(jìn)程獲得主存資源};}}進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作(1)第一種是競(jìng)爭(zhēng)關(guān)系系統(tǒng)中的多個(gè)進(jìn)程之間彼此無關(guān)系統(tǒng)中的多個(gè)進(jìn)程之間彼此相關(guān)資源競(jìng)爭(zhēng)的兩個(gè)控制問題：一個(gè)是死鎖(Deadlock)問題，一個(gè)是饑餓(Starvation

8、)問題，既要解決饑餓問題，又要解決死鎖問題。進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作(2)進(jìn)程互斥(MutualExclusion)進(jìn)程互斥是指若干個(gè)進(jìn)程因相互爭(zhēng)奪獨(dú)占型資源時(shí)所產(chǎn)生的競(jìng)爭(zhēng)制約關(guān)系。進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作(3)第二種是協(xié)作關(guān)系(1)?某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。?進(jìn)程同步指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個(gè)條件來協(xié)調(diào)它們的活動(dòng)，因?yàn)樾枰谀承┪恢蒙吓哦▓?zhí)行的先后次序而等待、傳遞信號(hào)