操作系統(tǒng)教程：并發(fā)進程

CH3并發(fā)進程3.1并發(fā)進程3.2臨界區(qū)管理3.3信號量與PV操作3.4管程3.5進程通信3.6死鎖3.7實例研究：Windows2000/XP同步和通信機制3.8實例研究：Linux信號量機制3.1并發(fā)進程3.1.1順序程序設(shè)計3.1.2進程的并發(fā)性3.1.3與時間有關(guān)的錯誤3.1.4進程的交互（InteractionAmongProcesses）：協(xié)作和競爭進程的順序性一個進程在順序處理器上的執(zhí)行是嚴格按序的一個進程只有當(dāng)一個操作結(jié)束后，才能開始后繼操作順序程序設(shè)計(1)順序程序設(shè)計是把一個程序設(shè)計成一個順序執(zhí)行的程序模塊，順序的含義不但指一個程序模塊內(nèi)部，也指兩個程序模塊之間。順序程序設(shè)計(2)順序程序設(shè)計具有如下的特點：程序執(zhí)行的順序性程序環(huán)境的封閉性程序執(zhí)行結(jié)果的確定性計算過程的可再現(xiàn)性順序程序設(shè)計(3)

順序程序設(shè)計的例

while(1){input，process，output}78輸入機處理器磁帶機130150228280300378430450時間處理器利用率：52/(78+52+20)≈35%

順序程序設(shè)計(4)

順序程序設(shè)計串行工作

i1p1o1i2p2o2．．．順序程序設(shè)計(5)

順序程序設(shè)計的優(yōu)缺點順序程序設(shè)計的順序性、封閉性、確定性和再現(xiàn)性給程序的編制、調(diào)試帶來很大方便，其缺點是計算機系統(tǒng)效率不高。進程的并發(fā)性(1)進程執(zhí)行的并發(fā)性：一組進程的執(zhí)行在時間上是重疊的并發(fā)性舉例：例如：有兩個進程A(a1、a2、a3)和B(b1、b2、b3)并發(fā)執(zhí)行進程的并發(fā)性(2)從宏觀上看，并發(fā)性反映一個時間段中幾個進程都在同一處理器上，處于運行還未運行結(jié)束狀態(tài)，從微觀上看，任一時刻僅有一個進程在處理器上運行。進程的并發(fā)性(3)并發(fā)的實質(zhì)是一個處理器在幾個進程之間的多路復(fù)用，并發(fā)是對有限的物理資源強制行使多用戶共享，消除計算機部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。無關(guān)的并發(fā)進程(1)并發(fā)進程分類：無關(guān)的，交往的。無關(guān)的并發(fā)進程：一組并發(fā)進程分別在不同的變量集合上操作，一個進程的執(zhí)行與其他并發(fā)進程的進展無關(guān)。無關(guān)的并發(fā)進程(2)

并發(fā)進程的無關(guān)性是進程的執(zhí)行與時間無關(guān)的一個充分條件，又稱為Bernstein條件。

無關(guān)的并發(fā)進程(3)

Bernstein條件：

R(pi)={a1,a2,…an}，程序pi在執(zhí)行期間引用的變量集

W(pi)={b1,b2,…bm}，程序pi在執(zhí)行期間改變的變量集若兩個程序的變量集交集之和為空集：

R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}

則并發(fā)進程的執(zhí)行與時間無關(guān)。無關(guān)的并發(fā)進程(4)

例如，有如下四條語句：

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í)行可能會產(chǎn)生與時間有關(guān)的錯誤。無關(guān)的并發(fā)進程(5)

兩個無關(guān)的進程并發(fā)執(zhí)行的例處理器利用率：(52+42)/(78+52+20)≈63%78輸入機處理器磁帶機130150228280300378430450時間磁帶機打印機2062170320交往的并發(fā)進程(1)交往的并發(fā)進程：一組并發(fā)進程共享某些變量，一個進程的執(zhí)行可能影響其他并發(fā)進程的結(jié)果。交往的并發(fā)進程(2)

并發(fā)程序設(shè)計的例子

while(1){input，send}while(1){receive，process，send}while(1){receive，output}處理器利用率：（52*n）/（78*n+52+20）=67%78輸入機處理器磁帶機130150228306208286384364時間交往的并發(fā)進程(3)

并行工作

i1p1ipoo1i2p2o2i3p3o3t1t2t3進程時間交往的并發(fā)進程(4)

并發(fā)程序設(shè)計并發(fā)程序設(shè)計是：把一個程序設(shè)計成若干個可同時執(zhí)行的程序模塊的方法。并發(fā)程序設(shè)計的特征：并行性、共享性、制約性、交互性。

交往的并發(fā)進程(5)

并發(fā)程序設(shè)計的優(yōu)點?對于單處理器系統(tǒng),可讓處理器和各I/O設(shè)備同時工作,發(fā)揮硬部件的并行能力。?對于多處理器系統(tǒng),可讓各進程在不同處理器上物理地并行，加快計算速度。?簡化了程序設(shè)計任務(wù)。

交往的并發(fā)進程(6)

采用并發(fā)程序設(shè)計的目的充分發(fā)揮硬件的并行性，提高系統(tǒng)效率。硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實現(xiàn)需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計。并發(fā)程序設(shè)計是多道程序設(shè)計的基礎(chǔ)，多道程序的實質(zhì)就是把并發(fā)程序設(shè)計引入到系統(tǒng)中。交往的并發(fā)進程(7)

與時間有關(guān)的錯誤對于一組交往的并發(fā)進程，執(zhí)行的相對速度無法相互控制，各種與時間有關(guān)的錯誤就可能出現(xiàn)。與時間有關(guān)錯誤的表現(xiàn)形式：結(jié)果不唯一永遠等待

交往的并發(fā)進程(8)

（結(jié)果不唯一）機票問題processTi(i=1,2)

varXi:integer;begin {按旅客定票要求找到Aj}；

Xi:=Aj; ifXi>=1thenbegin

Xi:=Xi-1;Aj:=Xi;{輸出一張票}；end else{輸出票已售完}；end;

交往的并發(fā)進程(9)

（永遠等待）內(nèi)存管理問題procedureborrow(varB:integer)beginifB>xthen{申請進程進入等待隊列等主存資源}

x:=x-B;{修改主存分配表，申請進程獲得主存資源}

end;procedurereturn(varB:integer)beginx:=x+B;{修改主存分配表}{釋放等主存資源的進程}

end;進程的交往：競爭與協(xié)作(1)

并發(fā)進程之間的競爭關(guān)系進程的互斥并發(fā)進程之間的協(xié)作關(guān)系進程的同步

進程的交往：競爭與協(xié)作(2)

第一種是競爭關(guān)系

系統(tǒng)中的多個進程之間彼此無關(guān)系統(tǒng)中的多個進程之間彼此相關(guān)進程的交往：競爭與協(xié)作(3)

資源競爭的兩個控制問題：一個是死鎖(Deadlock)問題，一個是饑餓(Starvation)問題，既要解決饑餓問題，又要解決死鎖問題。進程的交往：競爭與協(xié)作(4)

進程互斥(MutualExclusion)解決進程間競爭關(guān)系(間接制約關(guān)系)的手段。進程互斥指若干進程要使用同一共享資源時，任何時刻最多允許一個進程使用，其他進程必須等待，直到占有資源的進程釋放該資源。進程的交往：競爭與協(xié)作(5)第二種是協(xié)作關(guān)系(1)?某些進程為完成同一任務(wù)需要分工協(xié)作。?進程的同步是解決進程間協(xié)作關(guān)系(直接制約關(guān)系)的手段。進程的交往：競爭與協(xié)作(6)第二種