多核體系結(jié)構(gòu)與并行編程模型計(jì)算機(jī)科學(xué)導(dǎo)論第八講ppt課件

1、多核體系構(gòu)造與并行編程模型多核體系構(gòu)造與并行編程模型計(jì)算機(jī)科學(xué)導(dǎo)論第八講計(jì)算機(jī)科學(xué)導(dǎo)論第八講計(jì)算機(jī)科學(xué)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院陳意云陳意課課 程程 內(nèi)內(nèi) 容容 課程內(nèi)容課程內(nèi)容 圍繞學(xué)科實(shí)際體系中的模型實(shí)際圍繞學(xué)科實(shí)際體系中的模型實(shí)際, 程序?qū)嶋H和程序?qū)嶋H和計(jì)算實(shí)際計(jì)算實(shí)際 1. 模型實(shí)際關(guān)懷的問(wèn)題模型實(shí)際關(guān)懷的問(wèn)題 給定模型給定模型M，哪些問(wèn)題可以由模型，哪些問(wèn)題可以由模型M處理處理；如何比較模型的表達(dá)才干；如何比較模型的表達(dá)才干 2. 程序?qū)嶋H關(guān)懷的問(wèn)題程序?qū)嶋H關(guān)懷的問(wèn)題 給定模型給定模型M，如何用模型，如何用模型M處理問(wèn)題處理問(wèn)題

2、包括程序設(shè)計(jì)范型、程序設(shè)計(jì)言語(yǔ)、程序設(shè)包括程序設(shè)計(jì)范型、程序設(shè)計(jì)言語(yǔ)、程序設(shè)計(jì)、方式語(yǔ)義、類型論、程序驗(yàn)證、程序分計(jì)、方式語(yǔ)義、類型論、程序驗(yàn)證、程序分析等析等 3. 計(jì)算實(shí)際關(guān)懷的問(wèn)題計(jì)算實(shí)際關(guān)懷的問(wèn)題給定模型給定模型M和一類問(wèn)題和一類問(wèn)題, 處理該類問(wèn)題需多處理該類問(wèn)題需多少資源少資源講講 座座 提提 綱綱 根本知識(shí)根本知識(shí) 多核體系構(gòu)造、并行編程模型多核體系構(gòu)造、并行編程模型 內(nèi)存一致性模型內(nèi)存一致性模型 嚴(yán)厲一致性模型、順序一致性模型、內(nèi)存一嚴(yán)厲一致性模型、順序一致性模型、內(nèi)存一致性模型的重要性致性模型的重要性 共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 同步、鎖、臨界區(qū)、條件變量、死鎖

3、、數(shù)據(jù)同步、鎖、臨界區(qū)、條件變量、死鎖、數(shù)據(jù)競(jìng)爭(zhēng)競(jìng)爭(zhēng) 音訊傳送并行編程模型音訊傳送并行編程模型 音訊傳送、同步與異步音訊傳送、同步與異步 對(duì)稱多處置器對(duì)稱多處置器 對(duì)稱多處置器的體系構(gòu)造對(duì)稱多處置器的體系構(gòu)造二級(jí)二級(jí)緩存緩存內(nèi)存內(nèi)存總線總線二級(jí)二級(jí)緩存緩存二級(jí)二級(jí)緩存緩存二級(jí)二級(jí)緩存緩存一級(jí)一級(jí)緩存緩存一級(jí)一級(jí)緩存緩存一級(jí)一級(jí)緩存緩存一級(jí)一級(jí)緩存緩存處置器處置器處置器處置器處置器處置器處置器處置器基基 本本 知知 識(shí)識(shí) 必需在必需在處置器的處置器的緩存中找緩存中找到它操作到它操作的大部分的大部分?jǐn)?shù)據(jù)，以數(shù)據(jù)，以保證性能保證性能 經(jīng)過(guò)共享內(nèi)存來(lái)進(jìn)展通訊 幾個(gè)概念的粗略解釋幾個(gè)概念的粗略解釋 義務(wù)

4、：普通性的籠統(tǒng)術(shù)語(yǔ)，指由軟件完成的義務(wù)：普通性的籠統(tǒng)術(shù)語(yǔ)，指由軟件完成的一個(gè)活動(dòng)。例如，矩陣分塊乘就是把矩陣乘一個(gè)活動(dòng)。例如，矩陣分塊乘就是把矩陣乘分成多個(gè)義務(wù)分成多個(gè)義務(wù), 以便于在對(duì)稱多處置器上并行以便于在對(duì)稱多處置器上并行執(zhí)行這些義務(wù)執(zhí)行這些義務(wù) 進(jìn)程：義務(wù)在程序中的對(duì)應(yīng)物，它有本人的進(jìn)程：義務(wù)在程序中的對(duì)應(yīng)物，它有本人的數(shù)據(jù)和代碼，需求在處置器上運(yùn)轉(zhuǎn)直至終了數(shù)據(jù)和代碼，需求在處置器上運(yùn)轉(zhuǎn)直至終了。進(jìn)程是操作系統(tǒng)進(jìn)展資源分配和調(diào)度的獨(dú)。進(jìn)程是操作系統(tǒng)進(jìn)展資源分配和調(diào)度的獨(dú)立單位立單位 線程：是把進(jìn)程細(xì)分出現(xiàn)的實(shí)踐運(yùn)轉(zhuǎn)單位，線程：是把進(jìn)程細(xì)分出現(xiàn)的實(shí)踐運(yùn)轉(zhuǎn)單位，線程是進(jìn)程中一段順序執(zhí)行的語(yǔ)

5、句序列。把線程是進(jìn)程中一段順序執(zhí)行的語(yǔ)句序列。把進(jìn)程分成假設(shè)干線程是為了提高進(jìn)程執(zhí)行過(guò)進(jìn)程分成假設(shè)干線程是為了提高進(jìn)程執(zhí)行過(guò)程中的并行性。線程是操作系統(tǒng)調(diào)度的根本程中的并行性。線程是操作系統(tǒng)調(diào)度的根本單位單位 下面未嚴(yán)厲區(qū)分進(jìn)程和線程下面未嚴(yán)厲區(qū)分進(jìn)程和線程基基 本本 知知 識(shí)識(shí) 幾個(gè)概念的粗略解釋幾個(gè)概念的粗略解釋 并行并行(parallel): 多個(gè)可以同時(shí)執(zhí)行的義務(wù)，在多個(gè)可以同時(shí)執(zhí)行的義務(wù)，在多處置器上同時(shí)執(zhí)行多處置器上同時(shí)執(zhí)行 并發(fā)并發(fā)(cuncorrent)：多個(gè)可以同時(shí)執(zhí)行的義務(wù)：多個(gè)可以同時(shí)執(zhí)行的義務(wù)，在單處置器上交錯(cuò)執(zhí)行，在單處置器上交錯(cuò)執(zhí)行并發(fā)是邏輯上同時(shí)發(fā)生，而并行是物理

6、上并發(fā)是邏輯上同時(shí)發(fā)生，而并行是物理上同時(shí)發(fā)同時(shí)發(fā) 生。下面不區(qū)分并行和并發(fā)生。下面不區(qū)分并行和并發(fā)基基 本本 知知 識(shí)識(shí)tABtAB 對(duì)稱多處置器對(duì)稱多處置器 對(duì)稱多處置器的體系構(gòu)造對(duì)稱多處置器的體系構(gòu)造二級(jí)二級(jí)緩存緩存內(nèi)存內(nèi)存總線總線二級(jí)二級(jí)緩存緩存二級(jí)二級(jí)緩存緩存二級(jí)二級(jí)緩存緩存一級(jí)一級(jí)緩存緩存一級(jí)一級(jí)緩存緩存一級(jí)一級(jí)緩存緩存一級(jí)一級(jí)緩存緩存處置器處置器處置器處置器處置器處置器處置器處置器基基 本本 知知 識(shí)識(shí) 多個(gè)高性能處置器多個(gè)高性能處置器可以集成在一塊芯片可以集成在一塊芯片上上基基 本本 知知 識(shí)識(shí) 單核構(gòu)造與多核系統(tǒng)構(gòu)造單核構(gòu)造與多核系統(tǒng)構(gòu)造執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形

7、狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯單核構(gòu)造單核構(gòu)造多處置器構(gòu)造多處置器構(gòu)造執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯CPU形狀形狀中斷邏輯中斷邏輯超線程構(gòu)造超線程構(gòu)造 超線程技術(shù)充分利用執(zhí)行超線程技術(shù)充分利用執(zhí)行單元中的空閑資源，以便在單元中的空閑資源，以便在一樣時(shí)間內(nèi)完成更多任務(wù)一樣時(shí)間內(nèi)完成更多任務(wù) 執(zhí)行單元中的資源：內(nèi)存執(zhí)行單元中的資源：內(nèi)存訪問(wèn)部件、算術(shù)運(yùn)算部件和訪問(wèn)部件、算術(shù)運(yùn)算部件和浮點(diǎn)功能部件等浮點(diǎn)功能部件等基基 本本 知知 識(shí)識(shí) 單核構(gòu)造與多核系統(tǒng)構(gòu)造單核構(gòu)造與多核系統(tǒng)

8、構(gòu)造執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯單核構(gòu)造單核構(gòu)造多處置器構(gòu)造多處置器構(gòu)造執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯CPU形狀形狀中斷邏輯中斷邏輯超線程構(gòu)造超線程構(gòu)造 超線程技術(shù)本質(zhì)上就是多超線程技術(shù)本質(zhì)上就是多個(gè)線程共享一個(gè)執(zhí)行核個(gè)線程共享一個(gè)執(zhí)行核 兩套兩套CPU形狀形狀 +中斷邏輯中斷邏輯是為了順應(yīng)兩個(gè)線程同時(shí)執(zhí)是為了順應(yīng)兩個(gè)線程同時(shí)執(zhí)行的需求行的需求基基 本本 知知 識(shí)識(shí) 單核構(gòu)造與多核系統(tǒng)構(gòu)造單核構(gòu)造與多核系統(tǒng)構(gòu)造共享緩存的多核體系構(gòu)

9、造共享緩存的多核體系構(gòu)造執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU形狀形狀中斷邏輯中斷邏輯多核體系構(gòu)造多核體系構(gòu)造執(zhí)行單元執(zhí)行單元緩緩 存存CPU形狀形狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元CPU形狀形狀中斷邏輯中斷邏輯 多核處置器是把兩個(gè)甚至更多的獨(dú)立執(zhí)行核嵌入到一個(gè)處置器的內(nèi)部，每個(gè)線程都有完好的硬件執(zhí)行環(huán)境，各線程之間實(shí)現(xiàn)了真正意義上的并行基基 本本 知知 識(shí)識(shí) 單核構(gòu)造與多核系統(tǒng)構(gòu)造單核構(gòu)造與多核系統(tǒng)構(gòu)造體系構(gòu)造越來(lái)越復(fù)雜，假設(shè)這些復(fù)雜的特體系構(gòu)造越來(lái)越復(fù)雜，假設(shè)這些復(fù)雜的特征都要反征都要反 映到編程言語(yǔ)中，才干寫出較好利用體系構(gòu)映到編程言語(yǔ)中

10、，才干寫出較好利用體系構(gòu)造優(yōu)點(diǎn)造優(yōu)點(diǎn) 的程序，那么編寫程序?qū)⑹呛芾щy的任務(wù)的程序，那么編寫程序?qū)⑹呛芾щy的任務(wù)需求設(shè)計(jì)好的編程模型并經(jīng)過(guò)編譯器和操需求設(shè)計(jì)好的編程模型并經(jīng)過(guò)編譯器和操作系統(tǒng)作系統(tǒng) 的協(xié)助和支持來(lái)處理的協(xié)助和支持來(lái)處理采用超線程技術(shù)的多核體系構(gòu)造采用超線程技術(shù)的多核體系構(gòu)造執(zhí)行單元執(zhí)行單元緩存緩存CPU形狀形狀中斷邏輯中斷邏輯CPU形狀形狀中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元緩存緩存CPU形狀形狀中斷邏輯中斷邏輯CPU形狀形狀中斷邏輯中斷邏輯基基 本本 知知 識(shí)識(shí) 并行編程模型并行編程模型 是底層體系構(gòu)造與上層運(yùn)用程序之間的橋梁是底層體系構(gòu)造與上層運(yùn)用程序之間的橋梁 向上隱藏并行處置

11、器的細(xì)節(jié)，并向程序員提向上隱藏并行處置器的細(xì)節(jié)，并向程序員提供表達(dá)并行的方法供表達(dá)并行的方法 向下充分利用硬件資源，高效且正確地完成向下充分利用硬件資源，高效且正確地完成運(yùn)用需求運(yùn)用需求 義務(wù)劃分、義務(wù)映射、數(shù)據(jù)分布、通訊和同義務(wù)劃分、義務(wù)映射、數(shù)據(jù)分布、通訊和同步是設(shè)計(jì)并行編程模型時(shí)需求思索的五個(gè)關(guān)步是設(shè)計(jì)并行編程模型時(shí)需求思索的五個(gè)關(guān)鍵要素鍵要素 并行編程模型的另一種說(shuō)法并行編程模型的另一種說(shuō)法 并行編程模型是編寫可被編譯和運(yùn)轉(zhuǎn)的并行并行編程模型是編寫可被編譯和運(yùn)轉(zhuǎn)的并行程序的一種模型程序的一種模型基基 本本 知知 識(shí)識(shí) 并行編程模型的分類并行編程模型的分類 1. 按進(jìn)程交互的機(jī)制來(lái)分按進(jìn)

12、程交互的機(jī)制來(lái)分 共享內(nèi)存模型：進(jìn)程共享可以異步地讀寫的共享內(nèi)存模型：進(jìn)程共享可以異步地讀寫的全局?jǐn)?shù)據(jù)空間全局?jǐn)?shù)據(jù)空間 音訊傳送模型音訊傳送模型: 進(jìn)程經(jīng)過(guò)相互傳送音訊來(lái)交換進(jìn)程經(jīng)過(guò)相互傳送音訊來(lái)交換數(shù)據(jù)數(shù)據(jù) 隱式模型：進(jìn)程之間交互是用戶不可訪問(wèn)的隱式模型：進(jìn)程之間交互是用戶不可訪問(wèn)的 2. 按問(wèn)題分解按問(wèn)題分解 義務(wù)并行：每個(gè)處置器執(zhí)行不同的義務(wù)義務(wù)并行：每個(gè)處置器執(zhí)行不同的義務(wù) 數(shù)據(jù)并行：把大義務(wù)分別成假設(shè)干個(gè)一樣的數(shù)據(jù)并行：把大義務(wù)分別成假設(shè)干個(gè)一樣的子義務(wù)子義務(wù) 3. 內(nèi)存一致性模型內(nèi)存一致性模型 內(nèi)存一致性模型內(nèi)存一致性模型 描畫(huà)的是，在有共享內(nèi)存的多處置器系統(tǒng)上描畫(huà)的是，在有共享內(nèi)

13、存的多處置器系統(tǒng)上，在它們讀寫共享內(nèi)存操作的能夠執(zhí)行順序，在它們讀寫共享內(nèi)存操作的能夠執(zhí)行順序中，哪些順序是正確的中，哪些順序是正確的 內(nèi)存一致性模型是了解并行程序語(yǔ)義的一個(gè)內(nèi)存一致性模型是了解并行程序語(yǔ)義的一個(gè)關(guān)鍵關(guān)鍵 為確保寫出正確的并行程序，程序員必需準(zhǔn)為確保寫出正確的并行程序，程序員必需準(zhǔn)確了解并行程序的語(yǔ)義確了解并行程序的語(yǔ)義 隨著多核處置器的廣泛運(yùn)用，并行程序設(shè)計(jì)隨著多核處置器的廣泛運(yùn)用，并行程序設(shè)計(jì)曾經(jīng)由一種特殊的、只需少數(shù)高端技術(shù)人才曾經(jīng)由一種特殊的、只需少數(shù)高端技術(shù)人才掌握的技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的根本技藝掌握的根本技藝內(nèi)存

14、一致性模型內(nèi)存一致性模型 嚴(yán)厲一致性原子一致性模型嚴(yán)厲一致性原子一致性模型任何對(duì)內(nèi)存位置任何對(duì)內(nèi)存位置x的讀操作，得到的是最的讀操作，得到的是最近一次對(duì)近一次對(duì) x的寫操作所寫入的值的寫操作所寫入的值 單處置器遵守嚴(yán)厲一致性單處置器遵守嚴(yán)厲一致性 下面下面, P1和和P2是處置器是處置器, x是共享變量是共享變量, 初值初值是是0。 W(x)1表示表示: 把把1寫到寫到x中；中；R(x)3表示表示: 讀取讀取x,得值得值3 P1: W(x)1 P1: W(x)1 P2: R(x)1 R(x)1 P2: R(x)0 R(x)1 P1: W(x)1 P2: R(x)0 R(x)1ttt 左邊不符合

15、嚴(yán)厲一致性 多處置器+共享內(nèi)存時(shí), 會(huì)出現(xiàn)讀寫或?qū)憣懖僮鞯臎_突 順序一致性模型順序一致性模型 比嚴(yán)厲一致性弱的模型比嚴(yán)厲一致性弱的模型 在多處置器共享內(nèi)存情況下，每個(gè)處置器執(zhí)在多處置器共享內(nèi)存情況下，每個(gè)處置器執(zhí)行的單個(gè)線程嚴(yán)厲按照程序規(guī)定的順序逐語(yǔ)行的單個(gè)線程嚴(yán)厲按照程序規(guī)定的順序逐語(yǔ)句地進(jìn)展內(nèi)存訪問(wèn)操作句地進(jìn)展內(nèi)存訪問(wèn)操作 比順序一致性還弱的統(tǒng)稱為弱內(nèi)存模型不比順序一致性還弱的統(tǒng)稱為弱內(nèi)存模型不同情況有不同稱號(hào)同情況有不同稱號(hào) 大多數(shù)程序員假定并行程序的運(yùn)轉(zhuǎn)滿足順序大多數(shù)程序員假定并行程序的運(yùn)轉(zhuǎn)滿足順序一致一致 性，但現(xiàn)實(shí)中幾乎一切的并行程序都在某種性，但現(xiàn)實(shí)中幾乎一切的并行程序都在某種弱

16、內(nèi)存弱內(nèi)存 模型下運(yùn)轉(zhuǎn)，而且不同的并行言語(yǔ)和處置器模型下運(yùn)轉(zhuǎn)，而且不同的并行言語(yǔ)和處置器的內(nèi)存的內(nèi)存 模型不同模型不同內(nèi)存一致性模型內(nèi)存一致性模型 順序一致性模型順序一致性模型 例：互斥運(yùn)用臨例：互斥運(yùn)用臨 界區(qū)的并行線程界區(qū)的并行線程 假設(shè)兩個(gè)線程嚴(yán)厲按照給出的語(yǔ)句順序逐假設(shè)兩個(gè)線程嚴(yán)厲按照給出的語(yǔ)句順序逐條執(zhí)行，條執(zhí)行， 那么它們能實(shí)現(xiàn)互斥功能，由于那么它們能實(shí)現(xiàn)互斥功能，由于r1和和r2不能不能夠同時(shí)為夠同時(shí)為0現(xiàn)實(shí)中，編譯器和處置器內(nèi)部進(jìn)展的現(xiàn)實(shí)中，編譯器和處置器內(nèi)部進(jìn)展的優(yōu)化都會(huì)導(dǎo)優(yōu)化都會(huì)導(dǎo) 致內(nèi)存操作的實(shí)踐順序和代碼中的語(yǔ)句順序致內(nèi)存操作的實(shí)踐順序和代碼中的語(yǔ)句順序不一致不一致,

17、使得兩個(gè)條件判別都為真，兩個(gè)線程都進(jìn)入使得兩個(gè)條件判別都為真，兩個(gè)線程都進(jìn)入臨界區(qū)臨界區(qū)內(nèi)存一致性模型內(nèi)存一致性模型x和和y: 共享變量共享變量, 初始初始:x = 0, y = 0 x = 1;y = 1;r1 = y;r2 = x;if (r1= 0)if (r2= 0) critical region critical region 內(nèi)存一致性模型的重要性內(nèi)存一致性模型的重要性 它作為系統(tǒng)實(shí)現(xiàn)和程序員之間的接口，對(duì)處它作為系統(tǒng)實(shí)現(xiàn)和程序員之間的接口，對(duì)處置器體系構(gòu)造的實(shí)現(xiàn)、并行言語(yǔ)的實(shí)現(xiàn)、并置器體系構(gòu)造的實(shí)現(xiàn)、并行言語(yǔ)的實(shí)現(xiàn)、并行程序的開(kāi)發(fā)和驗(yàn)證都有重要意義行程序的開(kāi)發(fā)和驗(yàn)證都有重要意義

18、 以并行言語(yǔ)的設(shè)計(jì)和實(shí)現(xiàn)為例以并行言語(yǔ)的設(shè)計(jì)和實(shí)現(xiàn)為例 編譯器的優(yōu)化算法會(huì)調(diào)整源程序中的內(nèi)存操編譯器的優(yōu)化算法會(huì)調(diào)整源程序中的內(nèi)存操作順序，使得目的程序和源程序的順序不一作順序，使得目的程序和源程序的順序不一致致 目的程序的執(zhí)行順序又能夠被處置器進(jìn)一步目的程序的執(zhí)行順序又能夠被處置器進(jìn)一步改動(dòng)改動(dòng) 并行言語(yǔ)的設(shè)計(jì)和實(shí)現(xiàn)必需思索到這兩種情并行言語(yǔ)的設(shè)計(jì)和實(shí)現(xiàn)必需思索到這兩種情況及其效果的疊加，對(duì)源程序能夠表現(xiàn)出的況及其效果的疊加，對(duì)源程序能夠表現(xiàn)出的行為進(jìn)展準(zhǔn)確描畫(huà)行為進(jìn)展準(zhǔn)確描畫(huà)(并行言語(yǔ)的內(nèi)存模型并行言語(yǔ)的內(nèi)存模型)，便，便于正確編程于正確編程內(nèi)存一致性模型內(nèi)存一致性模型 編程言語(yǔ)內(nèi)存一致性

19、模型的現(xiàn)狀編程言語(yǔ)內(nèi)存一致性模型的現(xiàn)狀由于優(yōu)化算法的多樣性，編程言語(yǔ)內(nèi)存模由于優(yōu)化算法的多樣性，編程言語(yǔ)內(nèi)存模型比體型比體 系構(gòu)造的內(nèi)存模型復(fù)雜系構(gòu)造的內(nèi)存模型復(fù)雜 Gosling等為第一版等為第一版Java言語(yǔ)給出的內(nèi)存一致言語(yǔ)給出的內(nèi)存一致性模型性模型, 無(wú)法支持常用的優(yōu)化算法無(wú)法支持常用的優(yōu)化算法, 是一個(gè)失是一個(gè)失敗的模型敗的模型 Manson等給出的等給出的Java模型，雖被言語(yǔ)新規(guī)范模型，雖被言語(yǔ)新規(guī)范所采用，但模型非?；逎?，是所采用，但模型非常晦澀，是Java言語(yǔ)中最言語(yǔ)中最復(fù)雜部分復(fù)雜部分, 極少有人能正確了解其含義極少有人能正確了解其含義 Boehm和和Adve試圖為試圖為C

20、+提供一個(gè)簡(jiǎn)單的模提供一個(gè)簡(jiǎn)單的模型，但很多地方有歧義或不明晰型，但很多地方有歧義或不明晰內(nèi)存一致性模型內(nèi)存一致性模型共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 運(yùn)用共享內(nèi)存的錯(cuò)誤例子運(yùn)用共享內(nèi)存的錯(cuò)誤例子 并行計(jì)算并行計(jì)算Fibonacci序列下一個(gè)元素的兩個(gè)線序列下一個(gè)元素的兩個(gè)線程程 對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束 下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量int retval; int retval;retval = curr; retval = curr; c

21、urr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 運(yùn)用共享內(nèi)存的錯(cuò)誤例子運(yùn)用共享內(nèi)存的錯(cuò)誤例子 并行計(jì)算并行計(jì)算Fibonacci序列下一個(gè)元素的兩個(gè)線序列下一個(gè)元素的兩個(gè)線程程 對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束 下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量int retval; int retval;retval = curr; retval =

22、curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t111111共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 運(yùn)用共享內(nèi)存的錯(cuò)誤例子運(yùn)用共享內(nèi)存的錯(cuò)誤例子 并行計(jì)算并行計(jì)算Fibonacci序列下一個(gè)元素的兩個(gè)線序列下一個(gè)元素的兩個(gè)線程程 對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束 下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序 顯然結(jié)果顯然結(jié)果 不對(duì)不對(duì) 緣由：緣由： 對(duì)共享變對(duì)共享變 量的訪問(wèn)缺量的訪問(wèn)缺 乏約束乏約束prev和和curr: 初值分為初值分為

23、0和和1的共享變量的共享變量int retval; int retval;retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t111111共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 同步同步 同步是對(duì)線程執(zhí)行的順序進(jìn)展強(qiáng)行限制的一同步是對(duì)線程執(zhí)行的順序進(jìn)展強(qiáng)行限制的一種機(jī)制，用來(lái)控制線程執(zhí)行的相對(duì)順序，可種機(jī)制，用來(lái)控制線程執(zhí)行的相對(duì)順序，可以有效處理任何線程之間的沖突，而這些沖以有效處理任何線程之間的沖突，而這些沖突有能夠會(huì)導(dǎo)致線程的執(zhí)行出現(xiàn)異常行為突有

24、能夠會(huì)導(dǎo)致線程的執(zhí)行出現(xiàn)異常行為 簡(jiǎn)言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理簡(jiǎn)言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理共享數(shù)據(jù)共享數(shù)據(jù) 同步機(jī)制同步機(jī)制 信號(hào)量、鎖又可細(xì)分成多種、條件變量信號(hào)量、鎖又可細(xì)分成多種、條件變量、共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 鎖鎖 用來(lái)表達(dá)一種互斥的并行控制戰(zhàn)略用來(lái)表達(dá)一種互斥的并行控制戰(zhàn)略 一個(gè)線程在同一個(gè)時(shí)辰只能運(yùn)用一個(gè)鎖，一一個(gè)線程在同一個(gè)時(shí)辰只能運(yùn)用一個(gè)鎖，一個(gè)鎖至多由一個(gè)線程獲得。鎖有兩個(gè)原子操個(gè)鎖至多由一個(gè)線程獲得。鎖有兩個(gè)原子操作：作： 1. acquire: 等待鎖狀等待鎖狀 態(tài)變?yōu)槲醇討B(tài)變?yōu)槲醇?鎖形狀，然鎖形狀，然 后將其置為后將其置為 已加

25、鎖形狀已加鎖形狀prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev; curr = curr+prev;prev = retval; prev = retval; 共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 鎖鎖 用來(lái)表達(dá)一種互斥的并行控制戰(zhàn)略用來(lái)表達(dá)一種互斥的并行控制戰(zhàn)略 一個(gè)線程在同一個(gè)時(shí)辰只能運(yùn)用一個(gè)鎖，一一個(gè)線程在同一個(gè)時(shí)辰只能運(yùn)用一個(gè)鎖，一個(gè)鎖至多由一個(gè)線程獲得。鎖有兩個(gè)原子

26、操個(gè)鎖至多由一個(gè)線程獲得。鎖有兩個(gè)原子操作：作： 2. release: 將鎖形狀將鎖形狀 由已加鎖變由已加鎖變 為未加鎖為未加鎖prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev; curr = curr+prev;prev = retval; prev = retval;L-release(); L-release(); 共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 臨界區(qū)臨界區(qū)cr

27、itical section指包含有共享變量的一段代碼，這些共享指包含有共享變量的一段代碼，這些共享變量和變量和 多個(gè)線程之間存在相關(guān)關(guān)系多個(gè)線程之間存在相關(guān)關(guān)系多線程編程的主要挑戰(zhàn)在于需求以多個(gè)線多線程編程的主要挑戰(zhàn)在于需求以多個(gè)線程執(zhí)行程執(zhí)行 互斥操作的互斥操作的 方式實(shí)現(xiàn)臨方式實(shí)現(xiàn)臨 界區(qū)，以保界區(qū)，以保 證多個(gè)線程證多個(gè)線程 不會(huì)同時(shí)訪不會(huì)同時(shí)訪 問(wèn)臨界區(qū)問(wèn)臨界區(qū)prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = cu

28、rr;curr = curr+prev; curr = curr+prev;prev = retval; prev = retval;L-release(); L-release(); 條件變量條件變量 例：消費(fèi)者例：消費(fèi)者/消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 一個(gè)典型的同步問(wèn)題一個(gè)典型的同步問(wèn)題 也稱有限緩沖區(qū)問(wèn)題也稱有限緩沖區(qū)問(wèn)題 消費(fèi)者向緩沖區(qū)中寫入消費(fèi)者向緩沖區(qū)中寫入數(shù)據(jù)數(shù)據(jù) 消費(fèi)者從緩沖區(qū)獲得數(shù)消費(fèi)者從緩沖區(qū)獲得數(shù)據(jù)并對(duì)數(shù)據(jù)進(jìn)展操作據(jù)并對(duì)數(shù)據(jù)進(jìn)展操作 消費(fèi)者和消費(fèi)者并行執(zhí)消費(fèi)者和消費(fèi)者并行執(zhí)行行共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型void producer() / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) / 產(chǎn)

29、生下一個(gè)數(shù)據(jù)產(chǎn)生下一個(gè)數(shù)據(jù) / 臨界區(qū)終了臨界區(qū)終了void consumer() / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) / 消費(fèi)下一個(gè)數(shù)據(jù)消費(fèi)下一個(gè)數(shù)據(jù) / 臨界區(qū)終了臨界區(qū)終了 條件變量條件變量右邊是消費(fèi)者線程，條右邊是消費(fèi)者線程，條 件變量件變量C運(yùn)用鎖運(yùn)用鎖L來(lái)完成來(lái)完成 對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì)對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì) 條件變量條件變量C執(zhí)行執(zhí)行3種原子操種原子操 作作LC 的初值為的初值為false 1. wait(L): 釋放本身持有釋放本身持有 的鎖并處于的鎖并處于C的等待隊(duì)列。的等待隊(duì)列。 執(zhí)行終了時(shí)，鎖已被其他執(zhí)行終了時(shí)，鎖已被其他 線程獲得線程獲得共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型

30、void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù)產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)終了臨界區(qū)終了 L-release(); 條件變量條件變量右邊是消費(fèi)者線程，條右邊是消費(fèi)者線程，條 件變量件變量C運(yùn)用鎖運(yùn)用鎖L來(lái)完成來(lái)完成 對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì)對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì) 條件變量條件變量C執(zhí)行執(zhí)行3種原子操種原子操 作作LC 的初值為的初值為false 2. signal(L): 發(fā)信號(hào)，允許發(fā)信號(hào)，允許 等待等待C的一個(gè)線程往下

31、執(zhí)的一個(gè)線程往下執(zhí) 行。該操作終了后，鎖仍行。該操作終了后，鎖仍 然被發(fā)信號(hào)的線程持有然被發(fā)信號(hào)的線程持有共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù)產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)終了臨界區(qū)終了 L-release(); 條件變量條件變量右邊是消費(fèi)者線程，條右邊是消費(fèi)者線程，條 件變量件變量C運(yùn)用鎖運(yùn)用鎖L來(lái)完成來(lái)完成 對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì)對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì) 條件變量條件變量

32、C執(zhí)行執(zhí)行3種原子操種原子操 作作LC 的初值為的初值為false 3. broadcast(L): 發(fā)信號(hào)，發(fā)信號(hào)， 允許一切等待允許一切等待C的線程往的線程往 下執(zhí)行。該操作終了后下執(zhí)行。該操作終了后, 鎖鎖 依然被發(fā)信號(hào)的線程持有依然被發(fā)信號(hào)的線程持有共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù)產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)終了臨界區(qū)終了 L-release(); 消費(fèi)者消費(fèi)

33、者/消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 void producer() void consumer() while(1) while(1) L-acquire(); L-acquire(); / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) / 臨界區(qū)開(kāi)臨界區(qū)開(kāi)場(chǎng)場(chǎng) w h i l e ( L C = = t r u e ) w h i l e ( L C = = f a l s e ) C-wait(L); C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù)產(chǎn)生下一個(gè)數(shù)據(jù)/ 消費(fèi)下一消費(fèi)下一個(gè)數(shù)據(jù)個(gè)數(shù)據(jù) LC = true;LC = false; C-signal(L);C-signal(L); / 臨界區(qū)終了臨界區(qū)終了/ 臨界區(qū)終臨界區(qū)

34、終了了 L-release();L-release() 共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型Conditon C; Lock L;BooL LC = false; 條件變量條件變量條件變量本身本質(zhì)上條件變量本身本質(zhì)上 并沒(méi)有需求檢驗(yàn)的條件并沒(méi)有需求檢驗(yàn)的條件 值，而是運(yùn)用共享數(shù)據(jù)值，而是運(yùn)用共享數(shù)據(jù) 的形狀來(lái)保管線程的條的形狀來(lái)保管線程的條 件值，用于多線程之間件值，用于多線程之間 關(guān)于共享數(shù)據(jù)形狀變化關(guān)于共享數(shù)據(jù)形狀變化 的通訊的通訊 當(dāng)特定條件滿足時(shí)，當(dāng)特定條件滿足時(shí)， 線程等待或者喚醒其他線程等待或者喚醒其他 協(xié)作線程協(xié)作線程共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型void prod

35、ucer() while(1) L-acquire(); / 臨界區(qū)開(kāi)場(chǎng)臨界區(qū)開(kāi)場(chǎng) while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù)產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)終了臨界區(qū)終了 L-release(); 死鎖死鎖當(dāng)一個(gè)線程因等待另一個(gè)線程的資源當(dāng)一個(gè)線程因等待另一個(gè)線程的資源而阻塞，而而阻塞，而 同時(shí)該資源永遠(yuǎn)不會(huì)被釋放同時(shí)該資源永遠(yuǎn)不會(huì)被釋放 自死鎖或遞歸死鎖：線程自死鎖或遞歸死鎖：線程T試圖獲得一個(gè)鎖，試圖獲得一個(gè)鎖，而該鎖已被線程而該鎖已被線程T本人擁有本人擁有 錯(cuò)序死鎖：線程錯(cuò)序死鎖：線程T1占有資源占有資源r1并等

36、待由線程并等待由線程T2占有資源占有資源r2；而線程；而線程T2占有資源占有資源r2并等待并等待由線程由線程T1占有資源占有資源r1 編程中的問(wèn)題：怎樣防止出現(xiàn)死鎖編程中的問(wèn)題：怎樣防止出現(xiàn)死鎖共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 數(shù)據(jù)競(jìng)爭(zhēng)數(shù)據(jù)競(jìng)爭(zhēng)多個(gè)并行線程都訪問(wèn)某個(gè)共享變量多個(gè)并行線程都訪問(wèn)某個(gè)共享變量v，其，其中至少有中至少有 一個(gè)線程修正一個(gè)線程修正v ，并且這些線程沒(méi)有運(yùn)用鎖來(lái)，并且這些線程沒(méi)有運(yùn)用鎖來(lái)控制控制 它們對(duì)它們對(duì)v的訪問(wèn)的訪問(wèn) 在有數(shù)據(jù)競(jìng)爭(zhēng)的場(chǎng)所，各線程對(duì)數(shù)據(jù)的訪問(wèn)在有數(shù)據(jù)競(jìng)爭(zhēng)的場(chǎng)所，各線程對(duì)數(shù)據(jù)的訪問(wèn)次序是不確定的，計(jì)算結(jié)果依賴于這個(gè)次序次序是不確定的，計(jì)算結(jié)果依賴

37、于這個(gè)次序 數(shù)據(jù)競(jìng)爭(zhēng)有時(shí)是共享數(shù)據(jù)和通訊的一種方式數(shù)據(jù)競(jìng)爭(zhēng)有時(shí)是共享數(shù)據(jù)和通訊的一種方式，但多數(shù)情況下屬于程序錯(cuò)誤，但多數(shù)情況下屬于程序錯(cuò)誤 編程中的問(wèn)題：怎樣發(fā)現(xiàn)程序中的數(shù)據(jù)競(jìng)爭(zhēng)編程中的問(wèn)題：怎樣發(fā)現(xiàn)程序中的數(shù)據(jù)競(jìng)爭(zhēng)共享內(nèi)存并行編程模型共享內(nèi)存并行編程模型 音訊傳送音訊傳送 音訊傳送是進(jìn)程之間交換信息的一種方式，音訊傳送是進(jìn)程之間交換信息的一種方式，運(yùn)用共享變量是另一種方式運(yùn)用共享變量是另一種方式 在音訊傳送場(chǎng)所下，由于一個(gè)音訊在被接納在音訊傳送場(chǎng)所下，由于一個(gè)音訊在被接納者接納之前，必需由發(fā)送者發(fā)送，因此隱含者接納之前，必需由發(fā)送者發(fā)送，因此隱含了同步機(jī)制了同步機(jī)制 音訊傳送可以在分布式系

38、統(tǒng)、共享內(nèi)存的多音訊傳送可以在分布式系統(tǒng)、共享內(nèi)存的多處置器系統(tǒng)和單處置器系統(tǒng)中實(shí)現(xiàn)。在分布處置器系統(tǒng)和單處置器系統(tǒng)中實(shí)現(xiàn)。在分布式系統(tǒng)上實(shí)現(xiàn)共享變量有較大難度式系統(tǒng)上實(shí)現(xiàn)共享變量有較大難度 實(shí)現(xiàn)音訊傳送依托兩個(gè)通訊原語(yǔ)：實(shí)現(xiàn)音訊傳送依托兩個(gè)通訊原語(yǔ)：send和和receive音訊傳送并行編程模型音訊傳送并行編程模型 音訊傳送的發(fā)送和接納對(duì)象音訊傳送的發(fā)送和接納對(duì)象 進(jìn)程對(duì)進(jìn)程的傳送：兩個(gè)進(jìn)程不依賴于線程進(jìn)程對(duì)進(jìn)程的傳送：兩個(gè)進(jìn)程不依賴于線程自行進(jìn)展通訊，是最常見(jiàn)的音訊傳送方式自行進(jìn)展通訊，是最常見(jiàn)的音訊傳送方式 進(jìn)程間的傳送：屬于不同進(jìn)程的線程之間進(jìn)進(jìn)程間的傳送：屬于不同進(jìn)程的線程之間進(jìn)展通

39、訊展通訊 進(jìn)程內(nèi)的傳送：屬于同一個(gè)進(jìn)程的線程之間進(jìn)程內(nèi)的傳送：屬于同一個(gè)進(jìn)程的線程之間進(jìn)展通訊進(jìn)展通訊音訊傳送并行編程模型音訊傳送并行編程模型 音訊傳送的同步與異步音訊傳送的同步與異步 同步：音訊發(fā)送后，發(fā)送者必需等待，直到同步：音訊發(fā)送后，發(fā)送者必需等待，直到接納者的呼應(yīng)才干進(jìn)展其他操作接納者的呼應(yīng)才干進(jìn)展其他操作 異步：發(fā)送者不用等待接納者的呼應(yīng)就可以異步：發(fā)送者不用等待接納者的呼應(yīng)就可以繼續(xù)執(zhí)行繼續(xù)執(zhí)行 對(duì)于采用共享存儲(chǔ)模型的系統(tǒng)來(lái)說(shuō)，音訊傳對(duì)于采用共享存儲(chǔ)模型的系統(tǒng)來(lái)說(shuō)，音訊傳送必需是同步的送必需是同步的 對(duì)于采用分布式存儲(chǔ)模型的系統(tǒng)來(lái)說(shuō)，音訊對(duì)于采用分布式存儲(chǔ)模型的系統(tǒng)來(lái)說(shuō)，音訊傳送那么是異步的傳送那么是異步的音訊傳送并行編程模型音訊傳送并行編程模型 用音訊傳送機(jī)制處理消費(fèi)者用音訊傳送機(jī)制處理消費(fèi)者/消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 void producer() void consumer() message pmsg; message cmsg; while (1) while (1) r e c e i