第1章并行計算簡介

第一章.并行計算介紹課程性質是高性能計算學科專業(yè)基礎課——常識知識

公共基礎課、專業(yè)基礎課、專業(yè)方向課、專業(yè)選修課在教學計劃中的地位：核心、承上啟下

前導課：高等數(shù)學、離散數(shù)學、程序設計語言、數(shù)據(jù)結構、操作系統(tǒng)、計算機硬件后續(xù)課：高性能算法設計……屬于武術中的“練功”科目

“練武不練功，到頭一場空”教學目標掌握高性能計算基本的常識

對計算機體系結構及其性能充分了解培養(yǎng)初步并行算法設計和并行程序設計能力

算法——程序的靈魂問題求解過程：問題→想法→算法→程序程序設計研究的層次：算法→方法學→語言→工具培養(yǎng)培養(yǎng)并行算法性能分析能力

評價算法、改進算法學習要求循序漸進，切忌心浮氣躁提高課外學習的時間和內容理解科學而不是背誦科學→讀書正確對待考試作習題

華羅庚：“學數(shù)學不做習題等于入寶山而空返”

作實驗

高性能計算學科是一門科學性與工程性并重的學科，表現(xiàn)為理論和實踐緊密結合的特征。

課程介紹參考書籍課程書目：Grama,Gupta,Karypis,andKumar:IntroductiontoParallelComputing(SecondEdition,2003)成績組成理論課成績平時成績

10％~20%：出勤＋作業(yè)＋實驗期中考試成績

40％~50%期末考試成績

40％~50%實驗課成績：出勤＋實驗＋期末成績：百分制有關通過網(wǎng)絡交作業(yè)和實驗的要求將作業(yè)或實驗相關文件壓縮打包上傳，具體要求如下：壓縮包文件命名格式：

<學號><姓名><作業(yè)或實驗說明>

如：00281001王五實驗2

00281001王五第一章作業(yè)不同的實驗和作業(yè)用不同的壓縮包文件上傳，不要合在一個壓縮包文件中；對實驗壓縮包，要求將該次實驗工程所在目錄中的所有文件（要包括目錄,但要刪除其中的debug相關目錄）壓縮，并按如上命名：

00281001王五實驗2.rar將壓縮文件上傳即可；實驗提交和作業(yè)提交地址：1/

提交時用戶名：student密碼：123456

實驗課要求到實驗室上機課件下載地址：

1/

用戶名：zsuzyd密碼：123456

下載請用FTP軟件FileZilla我的QQ:360482583，E-Mail用QQ郵箱（如果沒上線，有問題請留言。）并行計算PART1：基礎概念PART2：并行編程PART3：并行算法和應用大綱PART1：基本概念簡介并行編程平臺并行算法設計的原則并行程序的解析模型PART2：并行編程基于共享地址空間平臺的編程基于消息傳遞平臺的編程大綱PART3：并行算法和應用

稠密矩陣算法

排序圖算法離散優(yōu)化問題動態(tài)規(guī)劃快速傅里葉變換并行的動機——從摩爾定律談起摩爾定律：當價格不變時，集成電路（IC）上的晶體管數(shù)目，約每隔24個月（1975年更改為18個月）便會增加一倍，性能也將提升一倍。122023/2/3超級計算機性能計算量綱前綴縮寫基冪含意數(shù)值KiloK103Thousand千MegaM106Million兆，百萬GigaG109Billion千兆，10億TeraT1012Trillion垓，萬億PetaP1015Quadrillion千萬億ExaE1018Quitillion百億億Flops：每秒所執(zhí)行的浮點運算次數(shù)(floating-pointoperationspersecond)目前的PC機運算速度通常在GFlops量級，高性能計算機運算速度則在TFlops至PFlops量級。應用需求計算密集型應用（Computing-intensive)：大型科學工程計算，數(shù)值模擬等。應用領域：石油、氣象、CAD、核能、制藥、環(huán)境監(jiān)測分析、系統(tǒng)仿真等。數(shù)據(jù)密集型應用（Data-intensive)：數(shù)字圖書館，數(shù)據(jù)倉庫，數(shù)據(jù)挖掘，計算可視化等。應用領域：圖書館、銀行、證券、稅務、決策支持系統(tǒng)等。通信密集型應用（Network-intensive)：協(xié)同工作，網(wǎng)格計算，遙控和遠程診斷等。應用領域：網(wǎng)站、信息中心、搜索引擎、電信、流媒體等。應用領域應用需求計算能力需求存儲容量需求生物醫(yī)學蛋白質電子態(tài)的計算藥物發(fā)明中的篩選過程蛋白質折疊100Tflops800Tflops1Pflops30TB200TB1PB航空航天制造發(fā)動機燃燒模擬和機翼設計模擬500Tflops100TB氣候環(huán)境短期天氣預報長期天氣預報局部突發(fā)性災難預報（如洪水、海嘯）20Tflops200Tflops1Pflops10TB100TB500TB核能領域完全等離子分析（包括電子結構分析）核武器數(shù)值模擬天然氣燃燒500Tflops1Pflops1Pflops1PB1PB1PB納米技術復合材料的結構分析和功能預測新材料發(fā)明200Tflops1Pflops400TB2PB天體物理學超新星三維模擬1Pflops1PB國防和國家安全密碼破譯先進武器模擬1Pflops1Pflops1PB1PB各應用對計算能力的需求摩爾定律不能延續(xù)？集成電路（IC）上的晶體管數(shù)目的物理極限半導體行業(yè)演進到22nm或更小尺寸的時候，生產(chǎn)晶體管的工藝快要達到原子理論和量子力學所決定的物理極限。如何延續(xù)摩爾定律？處理器發(fā)展趨勢：單核→多核如何延續(xù)摩爾定律？處理器性能=主頻x單位時鐘周期內的指令執(zhí)行提高處理器性能的兩大途徑增加處理器主頻增加每個時鐘周期內的指令執(zhí)行數(shù)單核處理器提升性能的主要途徑是提升主頻事實：功耗正比于主頻的三次方提升主頻將導致功耗快速增長多核處理器的功耗隨核心數(shù)線性增長每個時鐘周期內的指令執(zhí)行數(shù)正比于核心數(shù)“加核=加性能”處理器功耗正比于

電流x電壓x電壓x主頻主頻正比于電壓處理器發(fā)展趨勢：多核與眾核多核處理器是首個解決能耗問題的方案傳統(tǒng)的處理器架構是針對單線程性能優(yōu)化的，而非效能優(yōu)化大量能源用于優(yōu)化內存?zhèn)鬏?、預測分支等方面的控制電路少量能源供算術及邏輯運算單元（ALU）用于計算增加簡單的ALU單元可以提升效能眾核處理器－大量ALU，少量控制

電路單位能耗性能比多核處理器更高代表產(chǎn)品：GPU高性能計算機（HPC）計算能力的發(fā)展在高性能計算領域，摩爾定律仍在延續(xù)：多節(jié)點集群的計算能力不斷攀升領先的計算平臺性能增長預測超算集群性能指標與LinpackHPC計算能力的衡量指標：每秒浮點運算次數(shù)FLOPSHPC性能測試軟件：Linpackbenchmark(HighPerformanceLinpack，HPL)求解稠密線性方程組的高斯消元法超算集群性能指標與Linpack(續(xù)）Linpack的發(fā)展1970年代-1980年代初JackDongarra,JimBunch, CleveMoler和GilbertStewartJackDongarraCleveMoler(matlab創(chuàng)始人)并行算法性能指標可擴放性（

Scalability）：隨著計算設備數(shù)增加，運行時間減少主要指標：加速比SUabs為絕對加速比，tS為串行算法運行時間，tA為并行算法運行時間，n為計算問題的規(guī)模，p為所用的計算設備數(shù)。并行算法性能指標（續(xù)）邁向十億億次計算的4大挑戰(zhàn)能耗問題大規(guī)模計算集群的能耗巨大，成為硬件設計的主要約束必須降低單位計算能力的能耗迫使硬件架構發(fā)生重大改變：如多核、眾核和混合架構并發(fā)性硬件高并行性指令操作的高并行性：硬件每個時鐘周期提供數(shù)億次并行操作數(shù)據(jù)交換的高并行性：每一時刻，支持數(shù)億個數(shù)據(jù)在交換要發(fā)揮硬件的性能，需要超大規(guī)模的計算問題軟件的高并發(fā)性部分數(shù)據(jù)引自Cray公司2012年資料邁向十億億次計算的4大挑戰(zhàn)（續(xù)）容錯能力隨著硬件規(guī)模的擴大，硬件故障發(fā)生的概率隨之增大據(jù)統(tǒng)計，美國橡樹嶺國家實驗室的Jaguar集群每4分鐘就會有內存出現(xiàn)錯誤。編程困難由硬件的復雜性和軟件的高并發(fā)性要求引起的部分數(shù)據(jù)引自Cray公司2012年資料計算機的基本工作原理存儲程序控制原理所謂程序存儲,就是將解題的程序(指令序列)和它要處理的數(shù)據(jù)以二進制形式表示，并預先存放到存儲器中。所謂的程序控制,就是程序運行時計算機的控制器按照存儲的程序來控制整個計算機協(xié)調地完成計算任務,這就是著名的“存儲程序控制原理”馮●諾依曼計算機的基本工作原理

存儲程序控制—(存儲程序與程序控制)程序:一個指令序列指令:可以被計算機理解并執(zhí)行的基本操作命令指令與數(shù)據(jù)的存儲運行和運算：采用二進制編碼形式存儲程序：程序和數(shù)據(jù)預先存放在存儲器內程序控制：計算機工作時，CPU依次從存儲器中取出一個程序中的各條指令（取指令），對指令的功能進行分析（指令譯碼），按指令的功能從內存取出數(shù)據(jù)（取數(shù)），對數(shù)據(jù)進行運算處理（運算）并保存運算結果，直到取到并執(zhí)行了停機指令為止。至此完成程序的一次運行。計算機的基本工作原理馮·諾依曼計算機的結構與原理(1)計算機的工作由程序控制，程序是一個指令序列，指令是能被計算機理解和執(zhí)行的操作命令；(2)程序(指令)和數(shù)據(jù)均以二進制編碼表示，均存放在存儲器中；(3)存儲器中存放的指令和數(shù)據(jù)按地址進行存取；(4)指令是由CPU一條一條順序執(zhí)行的。中央處理器運算器和控制器輸入設備輸出設備存儲器“存儲程序控制”原理將問題的解算步驟編制成為程序，程序連同它所處理的數(shù)據(jù)都用二進位表示并預先存放在存儲器中程序運行時，CPU從內存中一條一條地取出指令和相應的數(shù)據(jù)，按指令操作碼的規(guī)定，對數(shù)據(jù)進行運算處理，直到程序執(zhí)行完畢為止②CPU從內存中逐條讀取該程序的指令及相關的數(shù)據(jù)④將指令的運算處理結果送回內存保存⑤任務完成后，將處理得到的全部結果成批傳送到外存以長久保存外存儲器內存儲器CPU①任務啟動時，執(zhí)行該任務的程序和數(shù)據(jù)從外存成批傳送到內存指令1指令2指令k指令n程序數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)m數(shù)據(jù)③CPU逐條執(zhí)行指令,按指令要求完成對數(shù)據(jù)的運算和處理計算機的基本工作原理存儲程序原理存儲程序思想可以概括為以下幾點:1.計算機應包括運算器、存儲器、控制器和輸入/輸出設

備。計算機能夠判斷出存儲器中存放的是指令還是數(shù)

據(jù)，控制器能自動執(zhí)行指令，運算器能進行基本的算術

運算和邏輯運算，同時，操作人員通過輸入/輸出與計算

機交換信息。2.計算機內部應采用二進制碼表示指令和數(shù)據(jù)。3.將編好的程序和原始數(shù)據(jù)送入內部存儲器中，然后啟動

計算機工作，計算機就能自動讀取和執(zhí)行指令存儲器中央處理器存儲數(shù)據(jù)和指令執(zhí)行指令處理數(shù)據(jù)指令，數(shù)據(jù)處理結果CPU的任務CPU的主要任務是執(zhí)行指令，它按指令的規(guī)定對數(shù)據(jù)進行操作指令是什么？指令就是命令，它用來規(guī)定CPU執(zhí)行什么操作。指令是構成程序的基本單位，程序是由一連串指令組成的指令采用二進位表示，大多數(shù)情況下，指令由兩個部分組成：操作碼操作數(shù)地址指出CPU應執(zhí)行何種操作的一個命令詞，例如加、減、乘、除、取數(shù)、存數(shù)等指出該指令所操作(處理)的數(shù)據(jù)或者數(shù)據(jù)所在位置

舉例:100206把02存儲單元和06存儲單元中的內容相加，和數(shù)保存在02單元CPU的組成CPU的三個組成部分CPU的主要任務是執(zhí)行指令，它按照指令的要求完成對數(shù)據(jù)的運算和處理。它主要由三個部分組成：(1)寄存器組它由十幾個甚至幾十個寄存器組成。(2)運算器用來對數(shù)據(jù)進行加、減、乘、除或者與、或、非等各種基本的算術運算和邏輯運算，所以也稱為算術邏輯部件(ALU)。運算器中的ALU可能有多個，(3)控制器這是CPU的指揮中心。它有一個指令計數(shù)器，用來存放CPU正在執(zhí)行的指令的地址，控制器中還有一個指令寄存器，它用來保存當前正在執(zhí)行的指令，通過譯碼器解釋該指令的含義，控制運算器的操作，記錄CPU的內部狀態(tài)等。CPU的結構和任務CPU主要由運算器、控制器和寄存器組3個部分組成CPU的任務：取指令并完成指令所規(guī)定的操作寄存器組運算器中央處理器指令計數(shù)器指令寄存器控制器數(shù)據(jù)程序指令1指令2指令k指令n數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)m數(shù)據(jù)內存儲器指令

指令地址

操作數(shù)地址存放待執(zhí)行指令的地址已經(jīng)啟動運行的程序和數(shù)據(jù)存放待執(zhí)行的指令并進行譯碼完成規(guī)定的運算暫存等待處理的數(shù)據(jù)操作命令~~~~內存儲器AC927BALU01234567運算器(ALU)與通用寄存器(GPR)運算器用來對數(shù)據(jù)進行各種算術或邏輯運算，所以稱為算術邏輯部件(ALU)，參加ALU運算的操作數(shù)通常來自通用寄存器GPR，運算結果也送回GPRSTORER1內存地址C例3：存數(shù)指令9例2：加法指令ADDR1R3R5(3＃寄存器內容與5＃寄存器內容相加，并把和數(shù)寫入1＃寄存器)例1:取數(shù)指令LOADR3內存地址ALOADR5內存地址B27362793636通用寄存器GPR影響CPU速度的幾個因素CPU主頻

CPU的內部頻率(MHz）。決定了CPU內部數(shù)據(jù)傳輸和指令執(zhí)行的每一步所占用的時間。主頻越高，CPU的處理速度就越快。

CPU速度=主頻*IPC(每個時鐘脈沖出現(xiàn)時可執(zhí)行的

指令條數(shù))

主頻為2G的CPU速度≠主頻為1G的CPU速度的2倍

Intel

的2G主頻CPU的速度≠AMD的2G主頻CPU的速度CPU總線頻率

CPU的外部頻率(MHz），是CPU和外界交換數(shù)據(jù)的工作頻率。影響CPU速度的幾個因素Cache容量

Cache容量越大，訪問Cache的命中率就越高，CPU的速度就越快。寄存器、運算器的位數(shù)位數(shù)越多，CPU的運算速度越快進程概念進程引入：OS需要支持其內部的(正在執(zhí)行的)程序活動，這些活動在許多方面都相似，因此將它們抽象為進程?；顒佑校簝却婀芾?、通信、使用I/O設備、占用/釋放CPU等程序不能作為資源的擁有者：否則，不同程序不可擁有同一個互斥資源？但Word和Excel都可用打印機。另外，同一個程序執(zhí)行多次時會導致問題：Word運行兩次，分別編輯兩個不同文檔，可同時在一臺打印機上打?。窟M程為了描述程序在并發(fā)執(zhí)行時對系統(tǒng)資源的共享使用，所需的一個描述程序執(zhí)行時動態(tài)特征的概念注意：引入多進程，提高了對硬件資源的利用率，但又帶來額外的空間和時間開銷，增加了OS的復雜性進程的定義

一個具有一定獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程。進程狀態(tài)運行狀態(tài)(Running)：占用處理機資源；處于此狀態(tài)的進程的數(shù)目小于等于CPU的數(shù)目。在沒有其他進程可以執(zhí)行時（如所有進程都在阻塞狀態(tài)），通常會自動執(zhí)行系統(tǒng)的idle進程（相當于空操作）。就緒狀態(tài)(Ready)：進程已獲得除處理機外的所需資源，等待分配處理機資源；只要分配CPU就可執(zhí)行。可以按多個優(yōu)先級來劃分隊列，如：時間片用完－>低優(yōu)，I/O完成－>中優(yōu)，頁面調入完成－>高優(yōu)等待狀態(tài)(waiting,Blocked阻塞)：由于進程等待某種條件（如I/O操作或進程同步），在條件滿足之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機分配給該進程，也無法運行。如：等待I/O操作的完成。進程同步背景臨界資源信號量經(jīng)典同步問題背景對共享數(shù)據(jù)的并發(fā)訪問可能導致數(shù)據(jù)的不一致性要保持數(shù)據(jù)的一致性，就需要一種保證并發(fā)進程的正確執(zhí)行順序的機制臨界資源進程間資源訪問沖突共享變量的修改沖突操作順序沖突進程間的制約關系間接制約：進行競爭－－獨占分配到的部分或全部共享資源，“互斥”直接制約：進行協(xié)作－－等待來自其他進程的信息，“同步”臨界資源:一次只允許一個進程使用(訪問)的資源。如：硬件打印機、磁帶機等，軟件的消息緩沖隊列、變量、數(shù)組、緩沖區(qū)等。硬件或軟件（如外設、共享代碼段、共享數(shù)據(jù)結構），多個進程在對其進行訪問時（關鍵是進行寫入或修改），必須互斥地進行－－有些共享資源可以同時訪問，如只讀數(shù)據(jù)多道程序環(huán)境－進程之間存在資源共享，進程的運行時間受影響信號量(Semaphores)操作系統(tǒng)作為一個地位高于進程的管理者，可解決公有資源的使用問題。操作系統(tǒng)可從進程管理者的角度來處理互斥的問題，信號量就是操作系統(tǒng)提供的管理公有資源的有效手段信號量(續(xù))1965年，荷蘭學者Dijkstra提出的信號量機制是一種卓有成效的進程同步工具，在長期廣泛的應用中，信號量機制又得到了很大的發(fā)展，它從整型信號量機制發(fā)展到記錄型信號量機制，進而發(fā)展為“信號集”機制。現(xiàn)在信號量機制已廣泛應用于OS中。一種不需要忙等待的同步工具.每個信號量s除一個整數(shù)值s.value（計數(shù)）外，還有一個進程等待隊列s.L。信號量只能通過初始化和兩個標準的原語操作來訪問－－作為OS核心代碼執(zhí)行，不受進程調度的打斷初始化指定一個非負整數(shù)值，表示空閑資源總數(shù)（又稱為"資源信號量"）－－若為非負值表示當前的空閑資源數(shù)，若為負值其絕對值表示當前等待臨界區(qū)的進程數(shù)“二值信號量(binarysemaphore)"：只允許信號量取0或1值信號量實現(xiàn)定義 typedefstruct{ intvalue;

structprocess*L;//等待信號量的進程隊列

}semaphore;

假設一些簡單操作:block()阻塞調用它的進程.wakeup(P)喚醒進程P.信號量實現(xiàn)信號量操作wait定義（也被稱作P操作）：

wait(S):

S.value--; if(S.value<0){ addthisprocesstoS.L;

block(); }

信號量操作signal定義（也被稱作V操作）：

signal(S):

S.value++; if(S.value<=0){ removeaprocessPfromS.L;

wakeup(P); }信號量用法Shareddata: semaphoremutex;mutex.value=1;//initially

ProcessPi:

do{

wait(mutex);

臨界區(qū) signal(mutex);

剩余區(qū)

}while(1);

利用信號量的互斥實現(xiàn)

信號量是同步工具在進程Pi的A后執(zhí)行Pj中的B信號量flag初始＝0代碼: Pi Pj … …

A

wait(flag)

signal(flag) B……wait、signal操作討論信號量的物理含義

S.value>0表示有S個資源可用；

S.value=0表示無資源可用或表示不允許進程再進入臨界區(qū)；

S.value<0則|S.value|表示在等待隊列中進程的個數(shù)或表示等待進入臨界區(qū)的進程個數(shù)。

wait(S)：表示申請一個資源；signal(S)表示釋放一個資源。

利用信號量實現(xiàn)進程互斥為使多個進程能互斥地訪問某臨界資源，只需為該資源設置一個互斥信號量mutex,并設其初值為1，然后將各進程的臨界區(qū)CS置于wait(mutex)和signal(mutex)操作之間即可。利用信號量實現(xiàn)共享打印機的A、B兩進程互斥的類并行PASCAL程序描述如下：利用信號量實現(xiàn)進程互斥-1varmutex:=semaphore:=1；beginparbeginA:beginB:beginInputdatd1fromI/01；Inputdatd2fromI/O2；Compute……；Compute……；

wait(mutex)；wait(mutex)；Printresults1byprinter;Printresults2byprinter;

signal(mutex)；signal(mutex)；

endendparendend利用信號量實現(xiàn)進程同步利用信號量能解決進程間的同步問題，這里以如圖所示的計算進程C和打印進程P通過緩沖區(qū)Buffer傳送數(shù)據(jù)的同步問題為例說明。

BufferCP利用信號量實現(xiàn)進程同步-1C和P兩進程基本算法如下：C：beginP:beginrepeatrepeatComputenextnumber;takefromBuffer;addtoBuffer;printlastnumber;untilfalseuntilfalseendendC和P兩進程并發(fā)執(zhí)行，必須在執(zhí)行序列上遵循以下規(guī)則，才能避免錯誤。只有當C進程把數(shù)據(jù)送入Buffer后，P進程才能從Buffer中取出數(shù)據(jù)來打印，否則P進程只能等待。只有當P進程從Buffer中取走數(shù)據(jù)后，C進程才能將新計算的數(shù)據(jù)再存入Buffer,否則C進程也只能等待。利用信號量實現(xiàn)進程同步-2為了實現(xiàn)進程同步，需采用同步信號量。為了滿足第一條同步規(guī)則，設置一個同步信號量full，它代表的資源是緩沖器滿，它的初值為0。同樣為了滿足第二條同步規(guī)則，設置另一個同步信號量empty，它代表的資源是緩沖器空，它的初值為1。實現(xiàn)C和P兩進程同步的類PASCAL程序：var:empty,full:semaphore:=1,0；beginparbeginC:beginrepeatComputenextnumber；

wait(empty)；Addtobuffer；

siganl(full)；untilfalseendP:beginrepeat

wait(full)；TakefromBuffer；

signal(empty)；Printlastnumber；untilfalseendparendendwait、signal操作討論wait、signal操作必須成對出現(xiàn)，有一個wait操作就一定有一個signal操作。當為互斥操作時，它們同處于同一進程。當為同步操作時，則不在同一進程中出現(xiàn)。

如果兩個wait操作相鄰，那么它們的順序至關重要，而兩個相鄰的signal操作的順序無關緊要。一個同步wait操作與一個互斥wait操作在一起時，同步wait操作在互斥wait操作前。

wait、signal操作的優(yōu)缺點

優(yōu)點：簡單，而且表達能力強（用wait、signal操作可解決任何同步互斥問題。）

缺點：不夠安全；wait、signal操作使用不當會出現(xiàn)死鎖；實現(xiàn)復雜。

經(jīng)典同步問題有限緩沖區(qū)問題(生產(chǎn)者消費者問題）讀者寫者問題有限緩沖問題生產(chǎn)者-消費者問題生產(chǎn)者-消費者問題是最著名的同步問題，它描述一組生產(chǎn)者（P1

……Pm）向一組消費者（C1……Cq）提供消息。它們共享一個有界緩沖池（boundedbufferpool）,生產(chǎn)者向其中投放消息，消費者從中取得消息，如下圖所示。生產(chǎn)者-消費者問題是許多相互合作進程的一種抽象。有限緩沖問題假定緩沖池中有n個緩沖區(qū)，每個緩沖區(qū)存放一個消息。由于緩沖池是臨界資源，它只允許一個生產(chǎn)者投入消息，或者一個消費者從中取出消息。即生產(chǎn)者之間、生產(chǎn)者與消費者之間、消費者之間都必須互斥使用緩沖池。所以必須設置互斥信號量mutex，它代表緩沖池資源，它的數(shù)值為1。P1PmmC1CqB0B1….…...………

Bn-1

有限緩沖問題生產(chǎn)者和消費者二類進程P和C之間應滿足下列二個同步條件：只有在緩沖池中至少有一個緩沖區(qū)已存入消息后，消費者才能從中提取消息，否則消費者必須等待。只有緩沖池中至少有一個緩沖區(qū)是空時，生產(chǎn)者才能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等待。為了滿足第一個同步條件，設置一個同步信號量full，它代表的資源是緩沖區(qū)滿，它的初始值為0，它的值為n時整個緩沖池滿。同樣為了滿足第二個同步條件，設置另一個同步信號量empty，它代表的資源是緩沖區(qū)空，它的初始值為n，表示緩沖池中所有緩沖區(qū)空。有限緩沖問題定義信號量

semaphorefull,empty,mutex;

初值:

full=0,empty=n,mutex=1n表示緩沖區(qū)個數(shù)生產(chǎn)者進程結構（1）

do{ … produceaniteminnextp …

… addnextptobuffer …

}while(1);無互斥同步

消費者進程結構（1）

do{

… removeanitemfrombuffertonextc …

… consumetheiteminnextc … }while(1);無互斥同步生產(chǎn)者進程結構（2）

do{ … produceaniteminnextp …

wait(mutex); … addnextptobuffer … signal(mutex);

}while(1);互斥

消費者進程結構（2）

do{

wait(mutex); … removeanitemfrombuffertonextc … signal(mutex);

… c