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

順序程序設計的例

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

順序程序設計(4)

順序程序設計串行工作

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

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

并發進程的無關性是進程的執行與時間無關的一個充分條件，又稱為Bernstein條件。

無關的并發進程(3)

Bernstein條件：

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

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

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

則并發進程的執行與時間無關。無關的并發進程(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)={b}，W(S3)={c}，W(S4)={w}。

S1和S2可并發執行，滿足Bernstein條件。其他語句并發執行可能會產生與時間有關的錯誤。無關的并發進程(5)

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

并發程序設計的例子

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

并行工作

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

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

交往的并發進程(5)

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

交往的并發進程(6)

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

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

交往的并發進程(8)

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

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

Xi:=Aj; ifXi>=1thenbegin

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

交往的并發進程(9)

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

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

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

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

并發進程之間的競爭關系進程的互斥并發進程之間的協作關系進程的同步

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

第一種是競爭關系

系統中的多個進程之間彼此無關系統中的多個進程之間彼此相關進程的交往：競爭與協作(3)

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

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