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

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