并執(zhí)行問題最新PPT課件

1、并發(fā)執(zhí)行問題最新 第七講第七講 并發(fā)執(zhí)行問題并發(fā)執(zhí)行問題 目的與要求目的與要求：了解并行程序的高級語言了解并行程序的高級語言 表示與操作系統(tǒng)支持下的實現(xiàn)；同步與表示與操作系統(tǒng)支持下的實現(xiàn)；同步與 互斥問題。了解解決互斥問題的軟件算互斥問題。了解解決互斥問題的軟件算 法。法。 重點與難點重點與難點：并行程序中的同步與互斥：并行程序中的同步與互斥 作業(yè)作業(yè)：7，例舉兩個現(xiàn)實生活中需要同步，例舉兩個現(xiàn)實生活中需要同步 與互斥的例子。與互斥的例子。 并發(fā)執(zhí)行問題最新 第四章第四章 進程同步與通訊、進程死鎖進程同步與通訊、進程死鎖 并發(fā)的需求并發(fā)的需求 操作系統(tǒng)利用進程（線程）機制支持用操作系統(tǒng)利用進程

2、（線程）機制支持用 戶態(tài)程序最大限度地并行執(zhí)行。戶態(tài)程序最大限度地并行執(zhí)行。 操作系統(tǒng)核心程序也要盡可能地并發(fā)運操作系統(tǒng)核心程序也要盡可能地并發(fā)運 行行 并發(fā)執(zhí)行問題最新 4.1 4.1 并發(fā)程序并發(fā)程序 傳統(tǒng)的串行程序存在著并行成分傳統(tǒng)的串行程序存在著并行成分 Read (a)Read (a)； Read (b)Read (b)； c = a + bc = a + b； Write (c)Write (c) ReadRead（a a）和）和ReadRead（b b）兩個語句如果不）兩個語句如果不 通過同一輸入設(shè)備則可并發(fā)執(zhí)行通過同一輸入設(shè)備則可并發(fā)執(zhí)行 并發(fā)執(zhí)行問題最新 識別算法中的并發(fā)成分

3、有兩種方法：識別算法中的并發(fā)成分有兩種方法： 程序員寫順序程序，用并行識別工具程序員寫順序程序，用并行識別工具 識別并發(fā)成分。組織使用操作系統(tǒng)的識別并發(fā)成分。組織使用操作系統(tǒng)的 并發(fā)機制。并發(fā)機制。 由程序員識別并發(fā)成分，用并發(fā)程序由程序員識別并發(fā)成分，用并發(fā)程序 設(shè)計語言設(shè)計并發(fā)程序，由編譯系統(tǒng)設(shè)計語言設(shè)計并發(fā)程序，由編譯系統(tǒng) 安排并發(fā)；或直接利用操作系統(tǒng)的系安排并發(fā)；或直接利用操作系統(tǒng)的系 統(tǒng)調(diào)用統(tǒng)調(diào)用/ /或高級并發(fā)程序庫設(shè)計并發(fā)程或高級并發(fā)程序庫設(shè)計并發(fā)程 序。序。 并發(fā)執(zhí)行問題最新 并發(fā)程序設(shè)計語言并發(fā)程序設(shè)計語言 - - 并發(fā)語句并發(fā)語句 是一種高級語言是一種高級語言 語法形式語法

4、形式 Parbegin S1Parbegin S1；S2S2； SnSn； ParendParend； SiSi（i=1i=1，2 2，n n） 是單個語句是單個語句 ParbeginParbegin和和ParendParend之間的語句可以并發(fā)執(zhí)之間的語句可以并發(fā)執(zhí) 行行 并發(fā)執(zhí)行問題最新 并發(fā)語句示例并發(fā)語句示例 前面那個串行讀寫程序可以改為前面那個串行讀寫程序可以改為 ParbeginParbegin readread（a a）；）； readread（b b）；）； ParendParend； c= a+bc= a+b； writewrite（c c）；）； 并發(fā)執(zhí)行問題最新 并發(fā)語句

5、描述手段的優(yōu)缺點并發(fā)語句描述手段的優(yōu)缺點 并發(fā)語句并發(fā)語句Parbegin/ParendParbegin/Parend的結(jié)構(gòu)化特征的結(jié)構(gòu)化特征 非常好非常好 但存在著描述能力不強的缺點，即存在但存在著描述能力不強的缺點，即存在 著用著用Parbegin/ParendParbegin/Parend語句無法描述的并語句無法描述的并 發(fā)優(yōu)先關(guān)系。發(fā)優(yōu)先關(guān)系。 若能輔以其它手段（如本章后續(xù)將介紹若能輔以其它手段（如本章后續(xù)將介紹 的信號量機制），則并發(fā)語句可以大大的信號量機制），則并發(fā)語句可以大大 增加其描述并發(fā)的能力。增加其描述并發(fā)的能力。 并發(fā)執(zhí)行問題最新 并發(fā)程序?qū)崿F(xiàn)并發(fā)程序?qū)崿F(xiàn) 前面是對并發(fā)的

6、高級語言描述，要真正前面是對并發(fā)的高級語言描述，要真正 實現(xiàn)并發(fā)執(zhí)行，需要通過操作系統(tǒng)的進實現(xiàn)并發(fā)執(zhí)行，需要通過操作系統(tǒng)的進 程機制。程機制。 操作系統(tǒng)提供操作系統(tǒng)提供進程創(chuàng)建，結(jié)束和同步的進程創(chuàng)建，結(jié)束和同步的 系統(tǒng)調(diào)用系統(tǒng)調(diào)用，可直接提供給用戶編寫并行，可直接提供給用戶編寫并行 程序；或由并行語言編譯器將并發(fā)語言程序；或由并行語言編譯器將并發(fā)語言 的語句轉(zhuǎn)化為對操作系統(tǒng)的系統(tǒng)調(diào)用。的語句轉(zhuǎn)化為對操作系統(tǒng)的系統(tǒng)調(diào)用。 并發(fā)執(zhí)行問題最新 與進程相關(guān)的系統(tǒng)調(diào)用與進程相關(guān)的系統(tǒng)調(diào)用 UnixUnix操作系統(tǒng)利用進程（或線程）支持操作系統(tǒng)利用進程（或線程）支持 并發(fā)執(zhí)行并發(fā)執(zhí)行 它提供了如下系統(tǒng)調(diào)用

7、：它提供了如下系統(tǒng)調(diào)用： forkfork（）：創(chuàng)建一個新進程。該系統(tǒng)調(diào)用執(zhí)（）：創(chuàng)建一個新進程。該系統(tǒng)調(diào)用執(zhí) 行完成后，系統(tǒng)已創(chuàng)建了一個子進程，該子行完成后，系統(tǒng)已創(chuàng)建了一個子進程，該子 進程繼承了父進程的程序空間，復制了父進進程繼承了父進程的程序空間，復制了父進 程的數(shù)據(jù)段和棧段。也就是說不管是父進程程的數(shù)據(jù)段和棧段。也就是說不管是父進程 還是子進程，在占有處理機后，都從還是子進程，在占有處理機后，都從forkfork（）（） 調(diào)用的返回點開始運行，而父進程調(diào)用的返回點開始運行，而父進程forkfork（）（） 調(diào)用的返回值是子進程的進程標識號；子進調(diào)用的返回值是子進程的進程標識號；子進

8、程程forkfork（）調(diào)用的返回值是（）調(diào)用的返回值是0 0。 并發(fā)執(zhí)行問題最新 exitexit（statusstatus）：進程結(jié)束。該系統(tǒng)調(diào)用發(fā)）：進程結(jié)束。該系統(tǒng)調(diào)用發(fā) 出后，操作系統(tǒng)將從系統(tǒng)中刪除調(diào)用出后，操作系統(tǒng)將從系統(tǒng)中刪除調(diào)用exitexit的的 進程，并將進程，并將statusstatus值傳給等待它結(jié)束的父進值傳給等待它結(jié)束的父進 程。程。 waitwait（ N:=N+$100; count:=N; end; Program B: begin M:=count; M:=M-$200; count:=M; end; Parend; 例例3: 3: 對共享變量對共享變量co

9、untcount的互斥訪問的互斥訪問 互斥執(zhí)行互斥執(zhí)行 并發(fā)執(zhí)行問題最新 例例4 4：有限緩沖區(qū)的生產(chǎn)者：有限緩沖區(qū)的生產(chǎn)者/ /消費者問題消費者問題 （生產(chǎn)者和消費者共享一個產(chǎn)品緩沖隊列）（生產(chǎn)者和消費者共享一個產(chǎn)品緩沖隊列） INST NEXT 共享N個緩沖區(qū) P1 P2 Pm C1 C2 Cn INST Nil INST NEXT First INST NEXT First 并發(fā)執(zhí)行問題最新 type item=; # #緩沖區(qū)中數(shù)據(jù)的類型緩沖區(qū)中數(shù)據(jù)的類型 type buffer=record inst: item; next: pointer to buffer; end; var

10、P，C，F(xiàn)irst：pointer to buffer; nextp，nextc：item; First:= nil; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 并發(fā)執(zhí)行問題最新 new(P); # #獲得一空緩沖區(qū)獲得一空緩沖區(qū) P.inst:=nextp;把數(shù)據(jù)送到緩沖區(qū) P.next:=First; First:=P; until false; end; Parbegin Producer： begin repeat produce an item in nextp; . 并發(fā)執(zhí)行問題最新 consume the item in nextc; until false; end; Parend; Consumer

11、： begin repeat while first=nil do skip; # #空循環(huán)等空循環(huán)等 C:=First; first:=first.next; nextc:=C.inst;取出數(shù)據(jù) dispose(C); # #釋放緩沖區(qū)釋放緩沖區(qū) 并發(fā)執(zhí)行問題最新 T0：consumer C:= First T1：producer P.next:= First T2：producer First:= P T3：consumer First:= First.next 則會發(fā)生生產(chǎn)者加入隊列的緩沖區(qū)丟失則會發(fā)生生產(chǎn)者加入隊列的緩沖區(qū)丟失 臨界資源（critical resource）：一次僅允

12、一次僅允 許一個進程使用的資源許一個進程使用的資源 臨界段（critical section) ：各進程必須互各進程必須互 斥執(zhí)行的程序段。斥執(zhí)行的程序段。 并發(fā)執(zhí)行問題最新 解決臨界段問題的軟件算法必須遵循：解決臨界段問題的軟件算法必須遵循： 準則準則1 1：不能虛設(shè)硬件指令或假設(shè)處理機數(shù)不能虛設(shè)硬件指令或假設(shè)處理機數(shù) 目。目。 準則準則2 2：不能假設(shè)不能假設(shè)n n個進程的相對速度。個進程的相對速度。 準則準則3 3：當一個進程未處于其臨界段時，不當一個進程未處于其臨界段時，不 應阻止其它進程進入臨界段。應阻止其它進程進入臨界段。 準則準則4 4：當若干進程欲進入臨界段時，應能當若干進程欲

13、進入臨界段時，應能 在有限時間內(nèi)選出一個進程進入其臨界段。在有限時間內(nèi)選出一個進程進入其臨界段。 4.2.2 4.2.2 實現(xiàn)互斥的軟件算法實現(xiàn)互斥的軟件算法 進入臨界段之前要申請，獲得批準方可進入；進入臨界段之前要申請，獲得批準方可進入； 退出臨界段之后要聲明，以便其他進程進入。退出臨界段之后要聲明，以便其他進程進入。 并發(fā)執(zhí)行問題最新 協(xié)調(diào)各進程入臨界段的調(diào)度原則： 當無進程處于臨界段時，允許一個進程立即當無進程處于臨界段時，允許一個進程立即 進入臨界段。進入臨界段。 當已有進程進入臨界段時，當已有進程進入臨界段時， 其它試圖進入其它試圖進入 的進程必須等待的進程必須等待 當某進程退出臨界

14、段時，若有等待進入臨界當某進程退出臨界段時，若有等待進入臨界 段的進程，則應選取一個進入臨界段段的進程，則應選取一個進入臨界段。 軟件算法舉例: Pi Pi 表示一個進程表示一個進程 Pj Pj 表示另一個進程表示另一個進程 （i=0, 1i=0, 1； j=1- i j=1- i ） Repeat Entry code exit code Critical section Non-ritical section Until false; 并發(fā)執(zhí)行問題最新 Repeat While turni do skip ; turn= j ; Critical section Non-ritical s

15、ection Until false; 算法算法1 1：設(shè)一個共享的整型變量設(shè)一個共享的整型變量turnturn（0 0，1 1） 表示輪流進入表示輪流進入 不滿足準則不滿足準則3:3:當一個進程未處于其臨界段當一個進程未處于其臨界段 時，不應阻止其它進程進入臨界段。時，不應阻止其它進程進入臨界段。 并發(fā)執(zhí)行問題最新 Repeat While flagj do skip flagi = true； flagi = false； Critical section Non-critical section Until false; 算法算法2 2：設(shè)一個表示進程進入否狀態(tài)的數(shù)組設(shè)一個表示進程進入否

16、狀態(tài)的數(shù)組 Var flagVar flag：array0.1 of booleanarray0.1 of boolean 不滿足互斥要求：當flag初值為0，兩進程 同時執(zhí)行while語句時。 并發(fā)執(zhí)行問題最新 Repeat flagi = true； While flagj do skip； flagi = false； Critical section Non-ritical section Until false; 算法算法3 3：設(shè)一個表示進程狀態(tài)的數(shù)組設(shè)一個表示進程狀態(tài)的數(shù)組 Var flagVar flag：array0.1 of booleanarray0.1 of boole

17、an 不滿足準則不滿足準則4 4：當若干進程欲進入臨界段時，當若干進程欲進入臨界段時， 應能在有限時間內(nèi)選出一個進程進入其臨界應能在有限時間內(nèi)選出一個進程進入其臨界 段。（兩進程同時置段。（兩進程同時置flag)flag) 并發(fā)執(zhí)行問題最新 Repeat flagi = false； Critical section Non-ritical section Until false; 算法算法4 4：在標志置在標志置truetrue的時候注意一下的時候注意一下 對方的狀態(tài)對方的狀態(tài) 不滿足準則不滿足準則 4 4（在此被（在此被 打斷后，對打斷后，對 方進程可能方進程可能 置上置上truetrue） flagi = true； While flagj do begin flagi = false； While flagj do skip； flagi =