并發(fā)進程主要內(nèi)容一、程序執(zhí)行的順序性二、程序執(zhí)行的并發(fā)性三、與時間有關(guān)的錯誤四、進程的交互：協(xié)作和競爭一、程序執(zhí)行的順序性程序執(zhí)行的順序性（1）程序內(nèi)部的順序性（2）程序外部的順序性程序內(nèi)部的順序性是指一個可獨立調(diào)度的任務(wù)（進程或線程）內(nèi)部的語句、指令或模塊按照程序設(shè)計時規(guī)定的順序執(zhí)行，不因中斷、進程切換以及進程調(diào)度的順序而改變。（1）程序內(nèi)部的順序性語句1語句2語句n…進程程序外部的順序性是指多個相關(guān)任務(wù)（進程或線程）按照事先確定的順序逐個執(zhí)行，完成一個作業(yè)級的任務(wù)。（2）程序外部的順序性進程1進程2進程n…一組順序進程二、程序執(zhí)行的并發(fā)性進程的并發(fā)性是指一組進程的執(zhí)行在時間上是重疊的，即一個進程執(zhí)行的第一條指令是在另一個進程執(zhí)行的最后一條指令完成之前開始的。1、進程的并發(fā)性含義進程的并發(fā)性程序內(nèi)部的并發(fā)性程序外部的并發(fā)性并發(fā)多線程并發(fā)多進程并發(fā)多線程語句a1語句a2語句an…語句a3語句b1語句b2語句bm…語句b3線程1線程2語句a1語句a2語句an…語句a3語句b1語句b2語句bm…語句b3進程1進程2并發(fā)多進程2、并發(fā)程序設(shè)計并發(fā)多線程程序設(shè)計并發(fā)多進程程序設(shè)計（由程序員）把一個程序編制為若干個可同時執(zhí)行的程序模塊的程序設(shè)計方法稱為并發(fā)程序設(shè)計。如果并發(fā)執(zhí)行模塊都屬于一個進程，在進程內(nèi)部執(zhí)行，則稱為并發(fā)多線程程序設(shè)計；若并發(fā)執(zhí)行模塊屬于不同進程，則稱為并發(fā)多進程程序設(shè)計。并發(fā)程序設(shè)計的好處能夠同時啟動多臺設(shè)備操作，充分利用處理器與外圍設(shè)備、外圍設(shè)備與外圍設(shè)備之間的并行工作能力，減少設(shè)備間的等待，提高資源利用率和計算機的工作效率而順序程序設(shè)計則順序操作設(shè)備，設(shè)備利用率較低while(K<Count){receive(PC);output(data[K++])}順序程序while(I<Count){input(data[I++]);send(PC)}while(J<Count){receive(PI);process(data[J++]);send(PO)}順序程序向并發(fā)程序的改造實例輸入程序PIP1=while(I<Count){input(data[I]);process(data[I]);output(data[I]);}計算程序PC輸出程序PO三個并發(fā)程序input(data[1])input(data[2]) process(data[1])input(data[3])process(data[2])output(data[1])input(data[4])process(data[3])output(data[2])input(data[5])process(data[4])output(data[3])process(data[5])output(data[4])output(data[5])三個程序的并發(fā)運行輸入程序PI計算程序PC輸出程序PO3、并發(fā)進程分類無關(guān)的并發(fā)進程一組并發(fā)進程分別在不同的變量集合上操作，一個進程的執(zhí)行與其他并發(fā)進程的進展無關(guān)，即一個并發(fā)進程不會改變另一個并發(fā)進程的變量值。協(xié)作的并發(fā)進程一組并發(fā)進程共享某些變量，一個進程的執(zhí)行可能影響其他并發(fā)進程的執(zhí)行結(jié)果。無合作有合作設(shè)R(pi)={a1,a2,…an}是程序pi在執(zhí)行期間引用的變量集，W(pi)={b1,b2,…bm}是程序pi在執(zhí)行期間改變的變量集，若兩個程序p1、p2的引用變量集與改變變量集交集之和為空集，即R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}，則并發(fā)進程的執(zhí)行與時間無關(guān)。Bernstein條件

并發(fā)進程的執(zhí)行順序是否任意的判定方法S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時序關(guān)系分析設(shè)一個程序PS有如下四條語句：S1S2Bernstein條件應(yīng)用實例順序程序的并行化改造方法S1：a=x+y;S2：b=z+1;前趨圖S1、S2訪問的變量無交集S1、S2為并行關(guān)系S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時序關(guān)系分析S1S2S1：a=x+y;S3：c=a

b;前趨圖S1、S3對變量a一讀一寫，執(zhí)行順序不可顛倒S1、S3為順序關(guān)系S3S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時序關(guān)系分析S1S2S2：b=z+1;S3：c=a

b;前趨圖S2、S3對變量b一讀一寫，執(zhí)行順序不可顛倒S2、S3為順序關(guān)系S3S1：a=x+y;S2：b=z+1;S3：c=a

b;S4：w=c+1;語句執(zhí)行時序關(guān)系分析S1S2S3：c=a

b;S4：w=c+1;前趨圖S3、S4對變量c一讀一寫，執(zhí)行順序不可顛倒S3、S4為順序關(guān)系S3S4S1;S2S3;S4;改造后的并行程序執(zhí)行時序三、與時間有關(guān)的錯誤1、結(jié)果不唯一對數(shù)據(jù)重疊修改導(dǎo)致修改信息丟失，結(jié)果不唯一。例如，多人搶購到一張車票，一票售給多人。當(dāng)合作進程之間等待、喚醒之類的同步信號發(fā)送次序顛倒時，等待進程因錯過了喚醒信號而永遠等待。2、永遠等待例如，歸還資源的進程喚醒尚未等待資源的進程，喚醒信號丟失。四、進程的交互：協(xié)作和競爭并發(fā)進程之間的競爭關(guān)系是由于并發(fā)進程共用一套計算機系統(tǒng)資源引起的，一個進程的執(zhí)行可能影響與其競爭資源的其它進程。1、并發(fā)進程之間的競爭關(guān)系資源競爭產(chǎn)生兩個問題死鎖問題饑餓問題進程直接或間接互相等待對方的資源一些進程總是優(yōu)先于另一些進程FCFS資源分配策略解決進程競爭關(guān)系（間接制約關(guān)系）的手段臨界區(qū)管理可以解決進程互斥問題。進程互斥進程互斥是指若干進程要使用同一共享資源時，任何時刻最多允許一個進程使用，其他要使用該資源的進程必須等待，直到占有資源的進程釋放該資源。解決概念管理工具2、并發(fā)進程之間的協(xié)作關(guān)系某些并發(fā)進程為完成同一任務(wù)而共享某些數(shù)據(jù)，形成協(xié)作關(guān)系協(xié)作進程之間需