并發(fā)執(zhí)行問(wèn)題

第七講并發(fā)執(zhí)行問(wèn)題

目的與要求：了解并行程序的高級(jí)語(yǔ)言表示與操作系統(tǒng)支持下的實(shí)現(xiàn)；同步與互斥問(wèn)題。重點(diǎn)與難點(diǎn)：并行程序中的同步與互斥作業(yè)：例舉兩個(gè)現(xiàn)實(shí)生活中需要同步與互斥的例子。第4章進(jìn)程同步與通訊、進(jìn)程死鎖并發(fā)的需求操作系統(tǒng)應(yīng)盡量支持用戶態(tài)程序最大限度地并行執(zhí)行。程序設(shè)計(jì)要利用OS對(duì)并行運(yùn)行的支持，安排并行事務(wù)并行執(zhí)行。操作系統(tǒng)核心程序也要盡可能地并發(fā)運(yùn)行4.1并發(fā)程序傳統(tǒng)的串行程序存在著并行成分：

Read(a)；

Read(b)；

c=a+b；

Write(c)Read（a）和Read（b）兩個(gè)語(yǔ)句可并發(fā)執(zhí)行。識(shí)別程序中的并發(fā)成分有兩種方法：程序員寫(xiě)順序程序，用識(shí)別工具識(shí)別并發(fā)成分。再組織使用操作系統(tǒng)的并發(fā)機(jī)制。由程序員識(shí)別并發(fā)成分，用并發(fā)程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)并發(fā)程序，由編譯系統(tǒng)安排并發(fā)；或直接利用操作系統(tǒng)的系統(tǒng)調(diào)用/或高級(jí)并發(fā)程序庫(kù)設(shè)計(jì)并發(fā)程序。并發(fā)程序設(shè)計(jì)語(yǔ)言---并發(fā)語(yǔ)句它是一種高級(jí)語(yǔ)言；語(yǔ)法形式：

ParbeginS1；S2；…Sn；Parend；

Si（i=1，2，…，n）是單個(gè)語(yǔ)句。

Parbegin和Parend之間的語(yǔ)句可以并發(fā)執(zhí)行。并發(fā)語(yǔ)句示例前面那個(gè)串行讀寫(xiě)程序可以改為：

Parbegin read（a）；

read（b）；

Parend；

c=a+b；

write（c）；并發(fā)語(yǔ)句描述手段的優(yōu)缺點(diǎn)并發(fā)語(yǔ)句Parbegin/Parend的結(jié)構(gòu)化特征非常好。但存在著描述能力不強(qiáng)的缺點(diǎn)，即存在著用Parbegin/Parend語(yǔ)句無(wú)法描述的并發(fā)優(yōu)先關(guān)系。若能輔以其他手段（如本章后續(xù)將介紹的信號(hào)量機(jī)構(gòu)），則并發(fā)語(yǔ)句可以大大增加其描述并發(fā)的能力。并發(fā)程序?qū)崿F(xiàn)前面是對(duì)并發(fā)的高級(jí)語(yǔ)言描述，要真正實(shí)現(xiàn)并發(fā)執(zhí)行，需要通過(guò)OS支持的進(jìn)程機(jī)制。OS提供進(jìn)程創(chuàng)建，結(jié)束和同步的系統(tǒng)調(diào)用，可直接提供給用戶編寫(xiě)并行程序；或由并行語(yǔ)言編譯器將并發(fā)語(yǔ)言的語(yǔ)句轉(zhuǎn)化為對(duì)OS的系統(tǒng)調(diào)用。與進(jìn)程相關(guān)的系統(tǒng)調(diào)用UNIX操作系統(tǒng)利用進(jìn)程支持并發(fā)執(zhí)行；它提供了如下系統(tǒng)調(diào)用：fork（）：創(chuàng)建一個(gè)新進(jìn)程。該系統(tǒng)調(diào)用執(zhí)行完成后，系統(tǒng)已創(chuàng)建了一個(gè)子進(jìn)程，該子進(jìn)程繼承了父進(jìn)程的程序空間，復(fù)制了父進(jìn)程的數(shù)據(jù)段和棧段。也就是說(shuō)不管是父進(jìn)程還是子進(jìn)程，在占有處理機(jī)后，都從fork（）調(diào)用的返回點(diǎn)開(kāi)始運(yùn)行，而父進(jìn)程fork（）調(diào)用的返回值是子進(jìn)程的進(jìn)程標(biāo)識(shí)pid；子進(jìn)程fork（）調(diào)用的返回值是0。exit（status）：進(jìn)程結(jié)束。該系統(tǒng)調(diào)用發(fā)出后，操作系統(tǒng)將從系統(tǒng)中刪除調(diào)用exit的進(jìn)程，并將status值傳給等待它結(jié)束的父進(jìn)程。wait（&status）：等待子進(jìn)程結(jié)束。當(dāng)有多個(gè)子進(jìn)程時(shí)，任一個(gè)子進(jìn)程結(jié)束即將控制返回調(diào)用者，并將子進(jìn)程調(diào)用exit（status）時(shí)的status值送到&status指針?biāo)竼卧?。在控制返回調(diào)用者時(shí)，同時(shí)將所等到的子進(jìn)程pid作為wait（）系統(tǒng)調(diào)用函數(shù)的返回值。waitpid（pid，…）：等待pid所指定的進(jìn)程結(jié)束。多進(jìn)程實(shí)現(xiàn)前述的讀寫(xiě)并發(fā)程序pid=fork（）；ifpid==0then{read（b）；

exit（0）；}elseread（a）；return_pid=wait（&status）；c=a+b；write（c）；4.2進(jìn)程的互斥與同步互斥關(guān)系（亦稱間接制約關(guān)系）:

即進(jìn)程間因相互競(jìng)爭(zhēng)使用獨(dú)占型資源（互斥資源）所產(chǎn)生的制約關(guān)系。同步關(guān)系（亦稱直接制約關(guān)系）:

指完成同一任務(wù)的伙伴進(jìn)程間，因需要在某些位置上協(xié)調(diào)它們的工作而相互等待、相互交換信息所產(chǎn)生的制約關(guān)系。4.2.1臨界段問(wèn)題（互斥問(wèn)題）

例1：P1,P2兩進(jìn)程使用同一打印機(jī)。如果不互斥使用會(huì)交叉輸出。Entrycodeexitcode使用打印機(jī)P1Entrycodeexitcode使用打印機(jī)P2Parbegin

ProgramA:beginN:=count;N:=N+$100;count:=N;end;ProgramB:beginM:=count;M:=M+$200;count:=M;end;Parend;例2:對(duì)共享變量count的互斥訪問(wèn)?；コ鈭?zhí)行例3：有限緩沖區(qū)的生產(chǎn)者/消費(fèi)者問(wèn)題（生產(chǎn)者和消費(fèi)者共享一個(gè)產(chǎn)品緩沖隊(duì)列)。INSTNEXT共享N個(gè)緩沖區(qū)P1P2…Pm

C1C2…CnINSTNilINSTNEXTFirstINSTNEXTFirst

typeitem=…;#緩沖區(qū)中數(shù)據(jù)的類型typebuffer=recordinst:item; next:pointertobuffer; end;varP，C，F(xiàn)irst：pointertobuffer;

nextp，nextc：item;First:=nil;

數(shù)據(jù)結(jié)構(gòu)

new(P);#獲得一空緩沖區(qū)

P.inst:=nextp; P.next:=First; First:=P; untilfalse;end;

ParbeginProducer：

begin repeat …produceaniteminnextp;...

… consumetheiteminnextc; … untilfalse; end;

Parend;

Consumer：

beginrepeat whilefirst=nildoskip;#空循環(huán)等

C:=First; first:=first.next;

nextc:=C.inst; dispose(C);#釋放緩沖區(qū)T0：consumerC:=FirstT1：producerP.next:=FirstT2：pr