程序設(shè)計語言原理復(fù)習(xí)-第13章 程序的并發(fā)性和進程交互原語

第13章程序的并發(fā)性和進程交互原語前面章節(jié)我們已多次提到并行（parallel）命令和并發(fā)（concurrent）程序，但主要是討論順序程序。所謂順序程序是指一個程序作業(yè)從起始到終了的每個作業(yè)步驟順次地執(zhí)行完畢。程序員寫程序時就默認(rèn)有一臺順序執(zhí)行的機器，為它排出先后執(zhí)行的動作步（語句）。然而，自然界發(fā)生的事，大多數(shù)是并行的。只是我們在討論之中把它孤立和順序化。這是為了早期計算機昂貴，一臺機器CPU只能順序地執(zhí)行，自然是首先發(fā)展順序計算。在實時控制領(lǐng)域，即使在早期也無法順序化。例如，飛行姿態(tài)控制程序，每時每刻都要計算敵我雙方飛機的速度、高度、方向才能決定控制措施。再如，民航機票發(fā)售系統(tǒng)，各站點售票是同時進行的，既讓乘客隨意訂座還不許賣重了。這都要求多個計算同時平行地執(zhí)行，并協(xié)調(diào)一致。我們稱這種程序為并發(fā)程序（concurrent）。顯然，并發(fā)的前題是并行（平行,parallel）。然而，并發(fā)和并行的概念在不同文獻上也少有出入。本書把“并行”定義為程序可相關(guān)或不相關(guān)平行執(zhí)行，有時僅指不相關(guān)的平行執(zhí)行。“并發(fā)”執(zhí)行必然相關(guān)。由于近年硬件成本大幅度下降。網(wǎng)絡(luò)計算快速發(fā)展，用多臺機器，多個CPU完成一個計算是極普通的事。因而原先人為順序化的順序計算就沒有必要了。而且今后為了利用信息資源，一上機就上網(wǎng)是應(yīng)用計算機主流。并發(fā)程序設(shè)計、并發(fā)語言將成為主流。順序程序倒成了并發(fā)的特例。操作系統(tǒng)本身是一個高度并行的軟件，它本身一般是某種高級順序語言（如C）擴充了一些支持并發(fā)進程低級原語，加上匯編語言編寫而成的。在這個意義上，這些擴充了低級原語的語言就是并發(fā)高級語言。其它更高層的通信機制是建立在這些低級原語上的模塊（相當(dāng)于該語言的庫模塊）語言的機制與特征并沒有擴充，編譯也沒有大改動。完全獨立于操作系統(tǒng)，在高級語言內(nèi)提供全套支持變形程序設(shè)計的并發(fā)，高級程序設(shè)計語言是Ada,因為它要編制機載、彈載的嵌入式程序。這些程序從單板、單片開始，編制監(jiān)控程序（小0.S）連用應(yīng)用程序。這種語言并不多見。因此，研究并發(fā)高級程序設(shè)計語言，勿寧說首先研究并發(fā)程序設(shè)計。搞清了各種并發(fā)模型和通信機制再去看已有語言的擴充就很容易理解和實現(xiàn)了。本章介紹并發(fā)程序設(shè)計的基本概念。并發(fā)程序帶來的問題和要解決的基本問題?；诠蚕碜兞亢突谙鬟f的兩類并發(fā)機制反映了不同物理模型，它們共同要解決的是對共享變量的互斥訪問和進程間如何通信協(xié)調(diào)。本章著重介紹概念和術(shù)語，是下章討論各種并發(fā)機制的基礎(chǔ)。13J基本概念并行程序是同時執(zhí)行兩個或多個程序，在程序執(zhí)行完之前必然有時間上的重疊。我們知道,一個程序的一次執(zhí)行叫做一個進程（process）。研究并發(fā)程序首先要了解進程及其相互作用。程序與進程源程序經(jīng)編譯、連接編輯成為可執(zhí)行代碼。它們是可執(zhí)行的“半成品”，可以作為用戶文件寄存于外存?？梢宰鳛閹煳募拖到y(tǒng)文件。一旦需要則調(diào)入內(nèi)存，然后開始執(zhí)行。進程是個動態(tài)由于設(shè)置了多個變量，使用忙等待設(shè)計的同步并發(fā)程序，比較難讀和理解，作正確性證明也麻煩。再者，忙等待比較浪費處理時間，因為在自旋處理周期中完全可以干點別的什么。最后，忙等待過于低級，程序員要從同步機制選取一直做到實現(xiàn)測試，設(shè)計起來比較麻煩且易出錯。(2)信號燈Dijkstra首先理解到忙等待的低級和設(shè)計麻煩，提出了完整的信號燈(semaphores)理論(1968)。信號燈是一個非負(fù)整值變量So在其上定義了兩個操作P,V(取自荷蘭語字頭，即wait(等待)和signal(示信))。V操作發(fā)信號指示一個事件可以出現(xiàn),P操作延遲所在進程直至某個事件已經(jīng)出現(xiàn)：P(s):awaits>0dos:=s-1; //'await'表達延遲的表示V(s):s:=s+1;P操作的等待(用原語表示)，判斷、設(shè)置信號量一般看作原子操作，一氣呵成?？捎糜布?fù)合指令TS(測試和設(shè)置)實現(xiàn)。信號燈變量s,當(dāng)只有一個資源時取值｛0,1｝就夠了，此時稱為二值信號燈。當(dāng)有多個資源時初始化s等于資源數(shù)，這時稱通用或記數(shù)信號燈。信號燈可保證進程互斥且公平，如下例。例13-4以信號燈實現(xiàn)的兩進程互斥ProgramMUTEX_EXAMPLE;varmutex:Semaphore:=1;processPl::loopP(mutex); 〃入口協(xié)議臨界段；V(mutex); 〃出口協(xié)議Pl的非臨界段；endloop;endpl;processp2::loopP(mutex);臨界段；V(mutex);P2的非臨界段；endloop;end;end.由于P,V均為原子動作，故可以保證互斥且無死鎖。和前述自旋鎖對比，它清楚、簡單、對稱。由于用原語則不用忙等待在等待期間CPU可干別的事。它們至少在進程正文上是公平的。P,V操作很容易擴大到n個進程競爭一個臨界段。也可以將二值信號燈劈開分別實施同步警衛(wèi)功能。以下是生產(chǎn)者/消費者著名問題的同步解。例13-5生產(chǎn)者/消費者的同步與互斥programPRODUCER_CONSUMERvarbuf:TYPE; //任意類型TYPEvarempty:sem:=1,fulksem:=0; 〃兩信號變量初始化processPRODUCERJ]::loopPRODUCER[i]產(chǎn)生一條消息m;〃存入消息m的三個操作〃存入消息m的三個操作//從buf取出消息m的〃三條操作buf:=m;V(full);endloop;end;processCONSUMERloopfetch:P(full);m:=buf;V(empty),CONSUMER[j]消費取出這條消息m;endloop;end;endPRODUCERCONSUMER.本程序有M個生產(chǎn)者，每位每次生產(chǎn)一條消息，只要buf空則存入，否則等待。有N個消費者，每位每次消費一條消息，只要buf中有消息、(以full標(biāo)志)則可進入臨界段，取出資源buf上的信息。信號變量fun,empty的類型為sem,是定義的抽象數(shù)據(jù)類型。當(dāng)程序啟動時M個生產(chǎn)者和N個消費者同時激活。激活的微觀次序由實現(xiàn)定。將信號變量S一分為二(empty,full)簡化了傳遞方向。稱劈分二值信號燈(splitbinarysemaphore)o這個算法保證了互斥，無死鎖。將P,V操作擴充到多進程，多資源(多個臨界段)也是很容易的。例如，我們可實現(xiàn)q個緩沖區(qū)的多生產(chǎn)、消費者問題。其算法如下：例13-6多進程的互斥與同步解programPROD_CONSvarbuf[l...q],mi,mj:TYPE;varfront~0,rear:=0; //buf的下標(biāo)變量varempty:sem:=q,full:sem:=0, //辟分二值信號varmutexD:sem:=1,mutexF:semi=l;processPROD[i:l..M]::loopPROD[i]產(chǎn)生一條消息mideposti:P(empty);P(matexD);buf[rear]:=mi;rear:=rearmodq+1;V(mutexD);V(fall);endloop;end;processCONSloopfetch:P(full);P(mutexF);mj:=buf(front);front:=frontmodq+1;V(matexF)V(empty);CONS[j]消費消息mi;endloop;end;endPROD_CONS.buf的每個元素放一條消息、，它是一個消息隊，裝入的消息放在緩沖區(qū)尾buf[rear],消費的消息從緩沖區(qū)頭buf[front]中取。兩組劈分信號，協(xié)議中是兩次P,V操作。一組劈分信號管進入臨界段(empty,full),另一組劈分信號管開放的是頭還是尾(mLI&utexD,mutexF)o選擇互斥是更為復(fù)雜的同步機制。不僅多進程，多資源，而且某進程只能選定使用某些資源。用P,V操作也可以實現(xiàn)選擇互斥。經(jīng)典的例子是哲學(xué)家就餐問題。例13-6五位哲學(xué)家就餐問題一張圓桌坐了五位哲學(xué)家，如圖13-2所示。桌上放有一大盆通芯粉，但只有五把叉子.而吃通芯粉必須有兩把叉子.一旦據(jù)有兩把叉子的哲學(xué)家就可以吃,否則它只好利用等待的時間思考。如果每人拿一把叉子等待其它人放下叉子，就產(chǎn)生死鎖。通芯粉當(dāng)然是共享資源，但叉子是只有兩個哲學(xué)家共享的資源。每個哲學(xué)家的行為過程即為一進程。第i個進程只和第i和i+1個叉子有關(guān)。故算法如下：programDINING_PHILO:varforks[1..5J:sem:=(5*1);processPHILOSOPHER[i:loopP(forks[i]);P(forks[i+1]);吃通芯粉；V(forks[i|);V(forks[i+1]);思考問題；endloop;end;processPHILOSOPHER[5]::loopP(forks[l]);P(forks[5]);吃通芯粉；V(forks[l]);V(forks[5]);思考問題；endloop;end;endDINING-PHILO.圖13-2哲學(xué)家就餐問題示意圖以上以信號燈實現(xiàn)互斥同步均隱含使用了await等待原語。事實上多數(shù)分時處理的機器，單主機多處理器的機器是用系統(tǒng)調(diào)用并行核(或叫管理程序)實現(xiàn)的。進程創(chuàng)建就緒后將該進程的描述子(descriptor)入隊，即就緒進程表，等待P操作的完成。這樣，進程處于就緒或阻塞狀態(tài)且未運行。此時P,V操作的語義解釋是：P(s):ifs=1thens:=0else置進程于queue中等候V(s):ifqueue!=emptythen從queue中消除一進程，令調(diào)度程序執(zhí)行它elses:=1無忙等待的實現(xiàn)更通用，且可用以實現(xiàn)其它上層機制。核的工作原理圖如圖13-1,它的主要職責(zé)是為進程分配處理器周期。進程在它分配前是阻塞的。當(dāng)然核例程名，調(diào)用細節(jié)因各同步機制和具體機器不盡一致，但原理是一樣的。如果為多處理機或分布式系統(tǒng)寫一個核，就要復(fù)雜一些，就要拿出一個處理器專用于維護就緒表并為其它處理器分配進程。這樣，就緒表的訪問成了共享的，也要保證互斥。于是在就緒表上用忙等待保證互斥。在分布式處理機上，不僅有一個核管理的就緒表。每個點上都得要有自己的核以維持本機的就緒表，進程從一個處理機遷移到另一個上，則置于另一核管理之下，情況就復(fù)雜多了?；谕ㄐ诺脑Z分布式或網(wǎng)絡(luò)上由于沒有共享主存，自旋鎖、信號燈實現(xiàn)起來都不太方便(上段最后已說明)。網(wǎng)絡(luò)提供的通信設(shè)施是交換消息(message)。這樣的系統(tǒng)只能由發(fā)送(send)和接受(receive)消息實現(xiàn)進程交互?；谙⒌倪M程交互一般說來，效率比共享變量的分時或多處理器系統(tǒng)要低。雖然1973年Hanson首先把它用于操作系統(tǒng)。但直到九十年代這類機制的普及應(yīng)用才成為可行。消息是信息傳遞的單元，按shannon的模型，信息源借助信道(channel)向信息目標(biāo)發(fā)送消息。信道成了并發(fā)進程共享的資源。信道是通信網(wǎng)的抽象，泛指進程間通信的路徑。信道由兩個原語訪問:send,receive。當(dāng)某進程向信道發(fā)送一消息，通信就開始了。需要該消息的進程，從信道上接受(獲取)這條消息。數(shù)據(jù)流也隨發(fā)送者傳遞到接受者。同步也就自然實現(xiàn)了，即不發(fā)送沒法接受,發(fā)送了必須接受(那怕暫行存放不處理)，否則丟失。由于信道本身不能存儲，變量只能存放在各個進程中，因而不能共享地訪問，所以也用不著互斥機制。由于只有所在進程能考察變量情況，條件同步編程與基于共享變量的大不相同。程序也不一定非要在一個處理器上執(zhí)行，可以分布在多個處理器上，分布式程序因而得名。反過來，分布式程序卻可在單主機或多路處理器的(分時)系統(tǒng)上執(zhí)行。此時把信道改成共享存儲就可以了。(1)信道與進程消息傳遞利用信道和兩個原語可以實現(xiàn)不同的通信模式。信道即信息(數(shù)據(jù))傳遞的路徑。是網(wǎng)絡(luò)的抽象。在分布式網(wǎng)絡(luò)中信道不同的組合可組成四類不同邏輯功能的進程：?過濾器（filter）進程它是一種數(shù)據(jù)轉(zhuǎn)移器，進程接受數(shù)據(jù)后按需要加工，然后傳出，如同過濾器濾出需要的數(shù)據(jù)，故得名。如果將一系列過濾器首尾相連則形成管道（pipeline）或稱流水線信道。每個進程獨立激活，物理上可分布在網(wǎng)絡(luò)各結(jié)點或多處理器的單主機上。典型過濾器進程均設(shè)原語：receive〈變量表〉from＜源進程,sendv表達式_表＞to＜目的進程,管道信道在操作系統(tǒng)中是最常見的，它把每一個設(shè)備抽象為進程，終端一CPU一打印機，即構(gòu)成運行一個程序的信道，三個進程均為過濾器。當(dāng)驗明消息來源無誤，接受原語將表達式表中的值“賦給”變量表。?客戶/服務(wù)器進程就分布式網(wǎng)絡(luò)而言，它的拓?fù)涫且粋€異質(zhì)結(jié)點的圖。管道通信只是圖上的一條路徑。即數(shù)據(jù)流通過管道跨越各進程。然而就一般圖而言，一個結(jié)點可以有多對一，一對一，一對多，多對多的數(shù)據(jù)流（進程交互）。在實際網(wǎng)絡(luò)應(yīng)用中有一類進程即這種情況:客戶/服務(wù)器，一個客戶（client）進程它要求一個或多個服務(wù)器（server）進程為其服務(wù)，反過來一個服務(wù)器也可以為一到多個客戶服務(wù)。顯而易見，一個發(fā)出服務(wù)要求，一個響應(yīng)要求后，完成服務(wù)，回復(fù)應(yīng)答。通信是雙向的?？蛻?服務(wù)器每完成一次通信客戶方是發(fā)送（請求）接收（應(yīng)答）兩次消息傳遞，服務(wù)器方相反是接受（請求）發(fā)送（應(yīng)答）兩次消息傳遞。這里也有隱含先來先服務(wù)原則。網(wǎng)絡(luò)上的文件服務(wù)器就是非常典型的例子。?對等（peer）進程另一類進程是既是客戶又是服務(wù)器的peer。一組對某進程共同完成（并行地）一個復(fù)雜計算。例如，陣列計算中各結(jié)點上的進程都是peer,它們作相似的部分計算。既發(fā)消息，也接受消息、，協(xié)作完成一計算。非陣列式網(wǎng)絡(luò)上的Peer到Peer的進程交互最能代表網(wǎng)絡(luò)上通信的一般情況。然而，由于算法復(fù)雜到目前還沒有通用的解，是網(wǎng)絡(luò)通信追求的最終目標(biāo)。（2）兩類通信模式無論是哪種進程，通信既可按同步也可按異步實現(xiàn)，所謂同步即兩進程都要執(zhí)行到同步點直接交換數(shù)據(jù)。所謂異步是兩進程誰也不等誰按各自速度執(zhí)行自己進程，就完成了數(shù)據(jù)通信。事實上完全不等待是不可能的，一個進程執(zhí)行到reecive如果沒有任何進程send,它只好等待（跳過receive語句再次空循環(huán)就是忙等待，否則阻塞在receive的等待隊中）。與此相反，一個進程執(zhí)行到send,它總可以把消息發(fā)出去。不是直接發(fā)給接受者就是發(fā)向信道（哪怕沒人接受）。所以，判定是否異步只看含send的進程是否阻塞，等待接受進程的到來。異步通信的實現(xiàn)，可以看作在某個進程中附帶一無限大的郵箱（抽象說也是信道，緩沖時間差）。發(fā)送者按自己進程執(zhí)行，將一條條消息發(fā)到郵箱。而接受者在自己合適的時候處理一條條消息各不相擾，猶如郵遞員給居民投信，可以彼此不見面。如果是服務(wù)器它就將結(jié)果消息投入郵箱回復(fù)到客戶。如果郵箱容量為零，即為同步通信，則非等不可，“見面”交換信息。至于怎樣激活、怎樣等、見面后怎樣分手，各種語言有不同的規(guī)定。到下一章高層通信機制一節(jié)再介紹。13.5小結(jié)并行程序是兩個或多個程序執(zhí)行時，時間上有覆蓋，并行程序間若共享數(shù)據(jù)或有數(shù)據(jù)傳遞,即它們是相關(guān)的，稱并發(fā)程序。程序代碼的一次執(zhí)行叫一個進程。研究程序的并行性即研究進程交互。一個進程執(zhí)行中可處于四種狀態(tài)：就緒、運行、阻塞、終止。控制進程狀態(tài)的操作是激活（創(chuàng)建進程并進入就緒態(tài)）。觸發(fā)（結(jié)束就緒進入運行態(tài)）、中斷（結(jié)束運行進入阻塞態(tài)）。程序設(shè)計語言以這些操作的組合提供原語。并行程序的模式有四種：單指令單數(shù)據(jù)流SISD;單指令多數(shù)據(jù)流SIMD;多指令單數(shù)據(jù)流MISD;多指令多數(shù)據(jù)流MIMD。并發(fā)程序主要研究SIMD,MIMD。原子動作是不可再分成并行子部分的計算機動作。它們粒度大小是相對的，一般以事件（程序的狀態(tài)有了改變）來定義原子動作。進程有三種類型：獨立進程；競爭進程；通信進程。競爭資源和進程通信是并發(fā)程序研究的兩大類問題。并發(fā)程序和順序程序的差別在于：依賴執(zhí)行速度；計算結(jié)果不確定；產(chǎn)生死鎖；得不到執(zhí)行。并發(fā)程序的基本問題是活性（會不會死鎖）公平性（會不會死等）、安全性（會不會出錯）。它們也是并發(fā)程序的基本性質(zhì)?；诠蚕碜兞康倪M程交互的基本問題是對共享資源的互斥訪問和競爭進程間的同步?；诠蚕碜兞康倪M程交互的低級機制有自旋鎖和信號燈。進程據(jù)有運行資源且處于運行中實現(xiàn)的等待稱為忙等待。簡單自旋鎖的忙等待只解決同步協(xié)調(diào)不解決互斥。復(fù)雜自旋鎖不利于編程。信號燈提供P,V操作保留臨界段，P操作隱含延遲以調(diào)整同步。是基于共享變量最基本的機制?？稍谄渖蠘?gòu)造任何進程交互的通信機制?；谕ㄐ诺倪M程可分為四類：過濾器，接受消息加工后發(fā)送出去。客戶，發(fā)送要求服務(wù)的請求，得到已服務(wù)的應(yīng)答。服務(wù)器，接受服務(wù)請求、服務(wù)后給出應(yīng)答。等同，既是客戶又是服務(wù)器，也是雙向的過濾器?；谕ㄐ诺脑Z是：receive<變量-表,fromv源進程〉sendv表達式-表〉to<H的進程,進程原語匹配實現(xiàn)消息傳遞。異步消息傳遞，交互進程間均向信道發(fā)/收消息，彼此可不“見面”?？山柚侧]箱（附在某進程上）實現(xiàn)。同步消息傳遞，信道郵箱容量為零，進程必須“見面”。一般利用原語將快進程延遲到同步點實現(xiàn)。習(xí)題試述順序、并行、并發(fā)程序之同異。順序性是指一個程序作業(yè)從開始到終止的每個作業(yè)步驟，順序地執(zhí)行完畢，并發(fā)程序是指多個計算同時平行的執(zhí)行，并協(xié)調(diào)一致。并發(fā)的前提是并行，并行是指程序可相關(guān)或不相關(guān)串行執(zhí)行。并行程序是兩個或多個程序執(zhí)行時，時間上有覆蓋，并行程序間若共享數(shù)據(jù)或者有數(shù)據(jù)傳遞，即它們是相關(guān)的，稱為并發(fā)程序。并發(fā)程序與順序程序之間的差別在于：依賴執(zhí)行速度；計算結(jié)果確定，產(chǎn)生死鎖；得不到執(zhí)行。試述并發(fā)程序的優(yōu)點、缺點、難點。優(yōu)點：有利于多機，多處理器、分布和網(wǎng)絡(luò)等，提高效率；缺點：依賴執(zhí)行速度；計算結(jié)果不確定，產(chǎn)生死鎖；得不到執(zhí)行。難點：安全性，活性，公平性。客觀世界問題是并發(fā)的且能用順序程序模擬實現(xiàn)，什么情況下用并發(fā)程序什么情況下用順序程序，盡你可能講出理由。何謂同步進程交互。是否兩進程一定要到同步點？怎樣判定一個程序是異步通信。在有分時的機器上編一程序?qū)崿F(xiàn)自旋鎖程序。在有分時的機器上編一程序?qū)崿F(xiàn)信號燈程序。(語言無此功能，可利用操作系統(tǒng)命令)。編一程序，模擬實現(xiàn)五位哲學(xué)家就餐問題，就餐1000人次或打出死鎖信息(語言不限,可利用操作系統(tǒng)命令)。分布式網(wǎng)絡(luò)上進程可分哪四類，能舉出這以外的進程型式嗎？舉出三個實際問題說明它們是哪種進程型式解最好。假定有一個原語startC,插入程序后可拉出一新進程，新進程共享原有變量，start以下創(chuàng)建的變量不共享。將以下矩陣求和的順序程序改成并發(fā)程序，使計算時間盡可能的少。typeMatrixisaray(l..n,l..n)ofFloat;procedureadd(a,b:inMacrix;sum:outMatrix)isbeginforiinl..nloopforjinl..nloopsum(ij):=a(ij)+b(i,j);endloop;endloop;end;在你的設(shè)計中有多少個進程并發(fā)執(zhí)行？什么環(huán)境下本并發(fā)程序比原順序程序快？什么情況下難于判定？寫出一死鎖程序(語言不限)。說明它真是死鎖的。查閱文獻，寫出信號燈的不變式。概念，即程序以一組數(shù)據(jù)的一次執(zhí)行。我們先看看進程在內(nèi)存中的執(zhí)行狀態(tài)及實現(xiàn)過程。就單個進程而言，它有四種狀態(tài)：?就緒?就緒ready運行running阻塞blocked終止terminated執(zhí)行進程。停止本進程執(zhí)行，隨時可恢復(fù)執(zhí)行。停止，且不可恢復(fù)執(zhí)行。除了這四種狀態(tài)而外，控制進程的邏輯操作是激活(activating)觸發(fā)(trigging)和中斷(interrant)。所謂激活是創(chuàng)建一個進程并使之進入就緒或立即運行狀態(tài)。所謂觸發(fā)是使就緒或阻塞狀態(tài)轉(zhuǎn)入運行態(tài)。所謂中斷即使運行的進程轉(zhuǎn)入阻塞或終止態(tài)。然而，這些邏輯操作是機器指令層次上的，在語言層次上借助于各種原語(primitive)或約定實現(xiàn)。所謂原語是程序語言中定義的例程名。例如,早期的操作系統(tǒng)低級原語fork和quit就是用來控制進程狀態(tài)的。一個進程調(diào)用fork例程，則中斷本進程創(chuàng)建新的子進程并執(zhí)行之。一個進程調(diào)用qait,將終止本進程。再如，cobegin-coend或par-end命令，并發(fā)程序的開始執(zhí)行，用某種約定自動激活各個進程，如Ada主控程序開始所有任務(wù)均激活。一個進程終止則自動觸發(fā)阻塞的父進程使之執(zhí)行。在更低的實現(xiàn)層次上中斷分為外部中斷和內(nèi)部中斷(由外部觸發(fā)和本進程觸發(fā))。觸發(fā)中斷后,調(diào)用中斷處理器(interrupthandler)例程，再調(diào)用原語例程，并將原語例程要求創(chuàng)建或終止的例程提交調(diào)度器例程，完成進程控制。其控制流示意圖如下：圖13-1進程執(zhí)行控制流我們把一個進程執(zhí)行中再次創(chuàng)建的進程，稱為子進程。一個進程可多次創(chuàng)建子進程，一次可創(chuàng)建多個子進程。子進程還可以創(chuàng)建子進程。如果被創(chuàng)建的子進程不分配一套資源則稱線程，例如，多CPU機上主進程將大型科學(xué)計算并行分配到各CPU,且共享同一內(nèi)存。如果分配資源，如一般程序進入打印語句，為此要分配打印機、驅(qū)動程序資源，則稱子進程。2并行程序的模式進程是程序執(zhí)行的控制流，眾所周知，代碼執(zhí)行要加工數(shù)據(jù)，與進程執(zhí)行同時存在的還有一個數(shù)據(jù)流。根據(jù)Flynn的分類法：一組可執(zhí)行代碼裝入一個機器內(nèi)存后，以一個CPU,一組數(shù)據(jù)執(zhí)行一次。它屬于SISD執(zhí)行模式(即單指令流單數(shù)據(jù)流的簡寫)。物理上對應(yīng)為單處理器的順序程序。一組可執(zhí)行代碼裝入后，可以依次執(zhí)行多個進程，它屬于SIMD,單指令流多數(shù)據(jù)流。對應(yīng)為單機多處理器的主機或單CPU的分時系統(tǒng)、陣列機組。在多機或多處理器上各有自己的可執(zhí)行代碼。協(xié)同完成一組數(shù)據(jù)的計算，是MISD多指令流單數(shù)據(jù)流系統(tǒng)。對應(yīng)為分布數(shù)據(jù)流機。MIMD則為多指令流多數(shù)據(jù)流系統(tǒng)，對應(yīng)為一般分布式系統(tǒng)(有多個不同的處理機，運行各不相同的進程）。局域網(wǎng)和廣域網(wǎng)就屬于此列。如果網(wǎng)上協(xié)同運行一個程序作業(yè)，則為以MIMD系統(tǒng)實現(xiàn)的并發(fā)程序。這四種模式包括了單機單處理器，單機多處理器，同型多機多處理器（陣列機）和分布式多機多處理器（異質(zhì)機聯(lián)網(wǎng)）的各種物理實現(xiàn)。MISD一般并發(fā)系統(tǒng)不多用，并發(fā)程序主要在SIMD,MIMD上實現(xiàn)。MIMD在實現(xiàn)多機協(xié)作計算時又可以分為兩類：共享存儲和分布式存儲。共享存儲多用于同類多CPU的單機上，所有CPU處理的進程都共享公共的數(shù)據(jù)。這樣，各進程間因數(shù)據(jù)共享而緊密耦合。進程間的關(guān)系最初是主/奴（master/slaver）式，即OS的核只執(zhí)行某個，主，處理器（進程），它統(tǒng)管共享數(shù)據(jù)并派遣任務(wù)到各，奴，處理器的進程。優(yōu)點是設(shè)計控制簡單，缺點是主進程易成瓶頸。當(dāng)今最流行的是對稱多處理器，即OS的核可以執(zhí)行任何處理器，每一處理器都是自調(diào)度（self-scheduling）的，即從待執(zhí)行進程表中取出一個執(zhí)行。它也派送子進程給其他處理器，也接收其它處理器發(fā)出來的子進程，故稱對稱多處理器SMP。并行處理器譜系如圖13-2：圖13.2并行處理器譜系由于分布式存儲是松耦合的計算機群體，它對應(yīng)為多計算機的簇（cluster）,和一組計算機的集合不同之處在于：它們各自的存儲是被大家共享的，它們互連，每個計算機只是''整個”計算機中的一個節(jié)點，是今后高性能、可伸縮、高可靠性計算機的發(fā)展方向。3線程與進程早期計算機一個進程就是一個執(zhí)行的線索，它可以和其它進程交替執(zhí)行，即又開始另一線索。執(zhí)行一個線索是斷斷續(xù)續(xù)的（凍結(jié)、就緒、運行、終止態(tài)等），完全由os調(diào)遣。一個進程可以看作是OS派送的單元（Unitofdispatching）o此外，進程執(zhí)行占有資源（數(shù)據(jù)、設(shè)備、CUP的時間片），所以進程又可以看作資源擁有單元（Unitofresourceownership）。后來發(fā)現(xiàn)，這兩種單元屬性是相互獨立的。在一個資源擁有單元之下可以派生出多個派送單元，即多線執(zhí)行。它們同樣可以交互，這就是線程。線程是共享資源的輕量級進程（lightweightprocess）,它也是有線程執(zhí)行狀態(tài)，也有其靜態(tài)存儲和局部變量。傳統(tǒng)的OS支持單線程的計算模式。單用戶的MS-DOS和多用戶的UNIX就是例子，即使UNIX是多線程交互，每一進程之中只有一線程。如圖13-3左側(cè)圖示。右側(cè)上圖，一個進程多個線程對應(yīng)為Java虛機的計算模式。而當(dāng)今所有OS均發(fā)展為右下角的多進程和多線程的計算模式。正是由于線程具有進程的所有派送特性。當(dāng)不涉及資源派送時，線程交互和進程交互是一樣的。下文討論只談進程交互。4原子動作并發(fā)和抽象一樣可以在不同層次研究它。一個數(shù)據(jù)占據(jù)32位，我們?nèi)缫截愃?，可以從第一位拷貝到?2位。也可以同時拷貝32位（在字位級并發(fā)）。一個表達式有若干項，每項同時計算最后匯總求值（子表達式級并發(fā)）。同樣并發(fā)可以在語句級，程序塊級，程序單元級，模塊級…。在級以下則認(rèn)為是原子的，不再分成子部分并發(fā)執(zhí)行。原子動作是一次“立即”執(zhí)行完的“順序”動作。至于是否真正不再分就不一定了。例如，一般順序程序的輸入/出進程和主進程都是并發(fā)執(zhí)行實現(xiàn)的。如原子動作定義在程序級上，它們也是“立即、順序”地執(zhí)行的。并發(fā)的討論則在此級以上。原子動作在進程內(nèi)完成，一個進程可以有多個原子動作（但不得有半個）。在高級語言層次上，原子動作一般定義在語句級的事件（event）上。所謂事件，是本程序表示的狀態(tài)有了變化。例如，執(zhí)行了賦值語句，作了初始化、調(diào)用、終止…當(dāng)然，事件也是相對的，一個語句對數(shù)據(jù)的加工可以是一個事件，右干語句的一個循環(huán)，也可以是一個事件。例13-1PL/1的多任務(wù)PL/1的并發(fā)進程是任務(wù)TASK,它可以定義語句級的事件。P是一個進程，它并行執(zhí)行Q進程，則P進程的正文可以寫：DECLAREXEVENT*CALLQ（APT）TASK（X）//激活Q事件變量X的一次取值表示一事件，它可取值IN_EXCEPTION（相當(dāng)于true）和TERMINATED（相當(dāng)于false）。當(dāng)P進程執(zhí)行到CALL時激活任務(wù)Q,實參表APT和Q的形參表匹配合,Q進程和P進程并行執(zhí)行。事件變量X調(diào)整兩進程的同步。X變量是P,Q共享的。5進程交互并發(fā)程序主要是研究進程之間的關(guān)系。所謂交互即兩進程有數(shù)據(jù)或操作通信。如甲進程向乙進程發(fā)一條消息送給它數(shù)據(jù)，或觸發(fā)乙進程中另一操作，這叫直接通信。如果甲進程據(jù)有某資源改變了該資源中的數(shù)據(jù)，以后乙進程也據(jù)有該資源，這些改變了的數(shù)據(jù)對乙進程有了影響，這是共享數(shù)據(jù)的間接通信。一般說來，并行進程有三種類型：(1)獨立進程兩進程并行但不相關(guān)。設(shè)進程為事件序列，若有C,K兩并行進程，可表達為CIIK。其中:C={Cl,C2???Cn}K={K1,K2,-Km}獨立進程是兩進程內(nèi)任何事件Ci,Kj的執(zhí)行都不依賴對方。因此與進程執(zhí)行速度無關(guān)，CllK執(zhí)行時在時間上可任意復(fù)蓋，也可以按C;K或K;C或{C1,C2,K,C3,K2…Km…Cn}秩序任意交錯執(zhí)行，均能得到正確結(jié)果。(2)競爭進程兩進程競爭同一資源。設(shè)C,K是兩競爭資源的進程，事件Ci,Kj要使用同一資源r。則必須保證Ci,Kj的互斥訪問(matualexclusion),即兩(訪問)事件時間上沒有復(fù)蓋，同一時間只有一個事件據(jù)有資源r,按Ci；Kj或Kj;Ci次序執(zhí)行均可。我們把據(jù)有并加工資源的代碼單劃出來，叫做臨界段(Criticalsection)。一般說來，這段代碼是同一個，所以Ci中有CS,Kj也有CS。顯然CS兩次執(zhí)行，誰先誰后對各自進程計算結(jié)果是不一樣的。因而CIIK結(jié)果不確定。如果推廣到多個進程競爭同一資源，情況更難預(yù)料。因為各進程輸入的數(shù)據(jù)只有運行時才知道，因而，進入臨界段的時間不確定。此外，為了保證互斥則各進程均設(shè)進出臨界段的協(xié)議。競爭進程一般形式是：Qloop (K):loop入口協(xié)議 入口協(xié)議臨界段 臨界段出口協(xié)議 出口協(xié)議非臨界段 非臨界段endloop endloop入口協(xié)議一般是按所設(shè)共享變量(多為布爾型)判斷能否進入，出口協(xié)議則改置正確值。為確保進程的確定性，利用共享變量“通信”協(xié)調(diào)。(3)通信進程 兩進程有協(xié)議的信息交換。設(shè)C,K定義如前,Ci必須先于Kj(Kj要用到Ci的結(jié)果)的執(zhí)行，即其它事件先后無所謂，一定要保證Ci,Kj的執(zhí)行順序。對于多個進程則有如UNIX和DOS的管道命令：ClIC2I???ICn規(guī)定事件先后。它是通信進程的一種。實現(xiàn)通信的機制有許多種：同步的、異步的；單向的,雙向的；定向的，廣播的。這與環(huán)境提供的運行機制和并發(fā)語言設(shè)計需求有關(guān)。也正是程序并發(fā)性要研究的問題。我們這里只給出初步概念。同步(synchronous)通信指兩進程進度各不相同，但必須同步到達通信點(注意不一定同時，同時是實時(realtime)程序的概念)。若一方未到，另一方等待，直至完成信息交換。交換后各自執(zhí)行各自進程則為單向同步通信。如果交換后,發(fā)送方一直等待接受方執(zhí)行的結(jié)果，拿回結(jié)果后再各自執(zhí)行自己的進程為雙向同步通信。異步(asynchronous)通信一般要借助相當(dāng)大的郵箱。兩進程以各自速度執(zhí)行，發(fā)送方有了信息投入郵箱，并繼續(xù)執(zhí)行自己進程。接受方在認(rèn)為合適時從郵箱獲取信息。一般不競爭郵箱且為單向通信，當(dāng)然也可做成雙向的。定向/廣播式通信所謂定向是發(fā)送方指明接受方。而廣播式通信發(fā)送方只向公共信道發(fā)送信息，任何共享該信道的成員均可接受，所以是異步通信、單向的。并發(fā)程序帶來的問題一般說來，順序程序和并行程序，與程序執(zhí)行的速度無關(guān)，軟件制售商在任何速度的機器開發(fā)出的商品，可以到其它速度的機器上運行而不影響其結(jié)果。并發(fā)程序可不這樣，因而，并發(fā)程序是比較難開發(fā)，測試和移植的。我們先討論它帶來的新問題。(1)速度依賴并發(fā)程序執(zhí)行結(jié)果，取決于順序成分進程執(zhí)行的相對速度。對于并發(fā)且有實時(realtime)要求的程序，執(zhí)行結(jié)果還取決于絕對速度。競爭進程最為明顯的，例如，一個進程對資源r中的變量x求平方；另一進程是對x作加一操作。結(jié)果值可能是(x+l)2(后者快、前者慢)或x2+l(前者快后者慢)。顯然，速度依賴導(dǎo)致結(jié)果不確定。即使是速度相同的多CPU處理機上，輸入/出設(shè)備速度有了小撓動也會影響結(jié)果。并發(fā)程序調(diào)整相對速度的辦法是延遲快進程。把進程掛起來(進入懸置態(tài))待到指定條件滿足才喚醒該進程。其基本原語是：awaitv表達式〉do〈語句I進程〉進程執(zhí)行到本句，測試表達式不滿足則不作do以后的操作。即用原語await實現(xiàn)條件同步。表達式即條件。(2)輸入值依賴同一并發(fā)程序兩組數(shù)據(jù)輸入可能會有很大差別。因為若有一個判斷因值不同跳過一段程序(跳過某個進程)則會打亂原有速度依賴關(guān)系。使執(zhí)行順序難以預(yù)測。使并發(fā)程序難于設(shè)計、測試、修改，就要更多地依賴軟件工程技術(shù)，加強文檔管理。(3)不確定性順序程序兩次同樣值的測試，一般情況下都是一致的。即所說的再現(xiàn)。并發(fā)程序因上述原因往往沒有確定的結(jié)果值。對于有副作用的函數(shù)或表達式這種先后次序的差異影響則更大。所以，軟件工程對副作用比較謹(jǐn)慎，并發(fā)程序是其原因之一。正是由于并發(fā)程序的不確定性。某一系統(tǒng)上測試通過的并發(fā)程序到另一系統(tǒng)上通不過。一組輸入通過另一組數(shù)據(jù)通不過。這是常有的事。即使是同一套系統(tǒng)、同一語言處理器，同樣一組輸入，有時結(jié)果也不一樣。因為這一系統(tǒng)不單運行這一并發(fā)程序，別的作業(yè)也會對程序干撓。只有在完全一致的條件下測試結(jié)果才可以再現(xiàn)。在個別臨界值的情況下，出現(xiàn)間歇再現(xiàn)，所以，并行程序的測試需要高超的技術(shù)。(4)死鎖(deadlock)死鎖是一種狀態(tài)，由于進程對資源有互不相兼容的耍求而使進程無法進展。表現(xiàn)為：受到排斥 進程永遠訪問不到所需資源。循環(huán)等待進程資源分配鏈形成一封閉回路。它雖無明顯把持，但對資源要求通過一組進程最后還是回到自己，不改為先釋放已據(jù)資源，只能死鎖。無占先(nopreemption)進程無法放棄所占的、其它進程需要的資源。所謂占先，只要所據(jù)資源的進程未處于使用狀態(tài)，另一優(yōu)先級高的進程有了要求，則此資源被后者占去。把持(waitandhold)相互以占有對方資源為放棄已占資源的先決條件。解決死鎖的方法：到目前為止還無法保證不出現(xiàn)死鎖狀態(tài)。即使采用無死鎖的通信和同步機制。因為意想不到的條件出了錯也會產(chǎn)生死鎖。解決的方法是：利用工具作靜態(tài)死鎖檢測，可以避免或減少死鎖出現(xiàn)的可能，事前防止。或事前，讓進程同時提出所有需要的資源，消除把持條件，或強行給資源排序，按此順序滿足要求，消除循環(huán)等待條件。或事前，為調(diào)度程序聲明最大的資源需求。少競爭資源死鎖可能也小。好的調(diào)度程序資源稍大即可避免或少出死鎖。一旦出現(xiàn)，最笨的辦法是重新啟動，試換數(shù)據(jù)，找出原因改正之。這是事后重試解決。一旦出現(xiàn)，找出死鎖地點，夭折某些事件或進程，自動從死鎖狀態(tài)恢復(fù)。顯然夭折的損失要求最小。為此，設(shè)置檢測點，一段一段倒轉(zhuǎn)(rollback)查找，直至段分得最小，夭折這個最小段。這對實時程序仍不可取。(5)死等(starvation)相互競爭的進程如果都滿足進入某一資源條件，一般采用排隊的先來先服務(wù)原則。相對最公平，但有的進程占用一種資源時間過長，致使其它資源長期閑置。適當(dāng)?shù)刈屗却梢越夥藕芏嗾紩r少而重要的進程，這樣更公平。于是，除了先來先服務(wù)而外，在調(diào)度例程中約定或在條件中加入優(yōu)先級表來達到此目的。調(diào)度程序則按此優(yōu)先級和先來后到統(tǒng)一調(diào)度。如果優(yōu)先級不當(dāng)就會造成某些進程永遠處于阻塞態(tài)，死等(但不是死鎖)。死等是不公平調(diào)度引起的，解決的辦法是在改變某些進程的優(yōu)先級，在公平性和合理性上作某種折衷。并發(fā)程序的性質(zhì)安全性(safety)和活性(liveness)是一般程序均有的性質(zhì)(程序?qū)傩?。所謂安全性是程序在執(zhí)行期間不會出現(xiàn)異常的結(jié)果。對于順序程序指其最終狀態(tài)是正確的。所謂活性是程序能按預(yù)期完成它的工作。對于順序程序指程序能正常終止。對于并發(fā)程序不僅如此還增加了新解釋。并發(fā)程序的安全性還要保證共享變量的互斥訪問和無死鎖出現(xiàn)。活性指每個進程能得到它所要求的服務(wù)；或進程總能進入臨界段；或送出的消息總能到達目的進程，活性深深受到執(zhí)行機構(gòu)調(diào)度策略的影響。正因為如此，公平性(fairness)也是并發(fā)程序重要性質(zhì)之一。所謂公平是指在有限進展的假設(shè)下沒有一個進程處于死等狀態(tài)。調(diào)度策略如能保證每個無條件的原子功能均能執(zhí)行則稱無條件公平性。在具有條件原子動作時，若條件原子動作能執(zhí)行并依然保持無條件公平性，則為弱公平性。條件原子動作一定能執(zhí)行，則為強公平性。低級并發(fā)機制和并發(fā)原語無論程序設(shè)計語言上層采取何種機制實現(xiàn)程序的并發(fā)，最底層不外乎創(chuàng)建進程(裝入內(nèi)存、初始化使之就緒)；起動執(zhí)行；阻塞(或叫凍結(jié))；停止執(zhí)行；阻塞父進程創(chuàng)建子進程；撤銷進程等六種操作。這六種操作更低層的實現(xiàn)是機器指令。例如，停止和阻塞則利用中斷陷井(trap),在機器指令中填入陷井地址碼。利用開關(guān)指令從一個進程跳到另一個進程。原語是包含這些底層指令的例程。由于支持上層不同的并發(fā)機制，原語為了表述方便不同語言原語的差別在于所選組合指令的不同。例如：'fork/multifork'fork/multifork:quit/joinfwait(e)Isignal(e)?sleep(value)-wakeup(value)cobeginsiIIs2II???IIsncoend"coroutineN?resumeM,send(Exp)to***■received(V)from---合股新創(chuàng)進程回到原進程。等待e為真進入臨界段P操作示信e為真臨界段可執(zhí)行,V操作value滿足使所在進程阻塞value滿足使所在進程喚醒(恢復(fù)執(zhí)行)。開始多個進程si…sn并發(fā)執(zhí)行。指定協(xié)例程No轉(zhuǎn)入?yún)f(xié)例程M。將表達式值送至…進程接受來自…消息，值由變量V傳入。1341基于共享變量的同步機制如前所述，并發(fā)程序中進程交互分兩大類，一為基于共享變量，一為基于消息傳遞。本小節(jié)先介紹基于共享變量的同步機制。我們把加工進程共享變量的一組語句叫做臨界段(criticalsection)。競爭進程競爭進入臨界段。一旦進入就獨享共享變量資源。從安全性而言，這是必須的。為了競爭進程互斥地訪問共享變量。最簡單的辦法是另設(shè)一公共變量指示是否已有進程進入臨界段。為此，早期的并發(fā)程序設(shè)置入口協(xié)議和出口協(xié)議。在協(xié)議中設(shè)置、判明指示變量的值，以求保護臨界段一個時間只有一個進程進入，一般形式見13.1.4(2)。那么不能進入的進程就只好跳到循環(huán)末端，再開始一輪循環(huán)測試。直至用完此資源的進程在其出口協(xié)議中改變了指示變量的值，它才能進入。該進程據(jù)有所有足以運行的資源(占有內(nèi)存，得到CPU的執(zhí)行)周而復(fù)始地測試，實質(zhì)上是在等待進入臨界段。我們把這種等待稱為忙等待(busywait)。(1)忙等待