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

CH3并發(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.7實(shí)例研究：Windows2000/XP同步和通信機(jī)制3.8實(shí)例研究：Linux信號(hào)量機(jī)制3.1并發(fā)進(jìn)程3.1.1順序程序設(shè)計(jì)3.1.2進(jìn)程的并發(fā)性3.1.3與時(shí)間有關(guān)的錯(cuò)誤3.1.4進(jìn)程的交互（InteractionAmongProcesses）：協(xié)作和競(jìng)爭(zhēng)進(jìn)程的順序性一個(gè)進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的一個(gè)進(jìn)程只有當(dāng)一個(gè)操作結(jié)束后，才能開(kāi)始后繼操作順序程序設(shè)計(jì)(1)順序程序設(shè)計(jì)是把一個(gè)程序設(shè)計(jì)成一個(gè)順序執(zhí)行的程序模塊，順序的含義不但指一個(gè)程序模塊內(nèi)部，也指兩個(gè)程序模塊之間。順序程序設(shè)計(jì)(2)順序程序設(shè)計(jì)具有如下的特點(diǎn)：程序執(zhí)行的順序性程序環(huán)境的封閉性程序執(zhí)行結(jié)果的確定性計(jì)算過(guò)程的可再現(xiàn)性順序程序設(shè)計(jì)(3)

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

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

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

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

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

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

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

無(wú)關(guān)的并發(fā)進(jìn)程(3)

Bernstein條件：

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

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

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

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

例如，有如下四條語(yǔ)句：

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條件。其他語(yǔ)句并發(fā)執(zhí)行可能會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。無(wú)關(guān)的并發(fā)進(jìn)程(5)

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

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

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

并行工作

i1p1ipoo1i2p2o2i3p3o3t1t2t3進(jìn)程時(shí)間交往的并發(fā)進(jìn)程(4)

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

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

并發(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ā)進(jìn)程(6)

采用并發(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ì)引入到系統(tǒng)中。交往的并發(fā)進(jìn)程(7)

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

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

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

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

Xi:=Aj; ifXi>=1thenbegin

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

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

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

x:=x-B;{修改主存分配表，申請(qǐng)進(jìn)程獲得主存資源}

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

end;進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作(1)

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

進(jìn)程的交往：競(jìng)爭(zhēng)與協(xié)作(2)

第一種是競(jìng)爭(zhēng)關(guān)系

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

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

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