第1章并行計(jì)算簡介

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

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

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

“練武不練功，到頭一場空”教學(xué)目標(biāo)掌握高性能計(jì)算基本的常識

對計(jì)算機(jī)體系結(jié)構(gòu)及其性能充分了解培養(yǎng)初步并行算法設(shè)計(jì)和并行程序設(shè)計(jì)能力

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

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

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

作實(shí)驗(yàn)

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

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

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

40％~50%期末考試成績

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

<學(xué)號><姓名><作業(yè)或?qū)嶒?yàn)說明>

如：00281001王五實(shí)驗(yàn)2

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

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

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

實(shí)驗(yàn)課要求到實(shí)驗(yàn)室上機(jī)課件下載地址：

1/

用戶名：zsuzyd密碼：123456

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

稠密矩陣算法

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

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

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

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

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

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

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

運(yùn)算和邏輯運(yùn)算，同時，操作人員通過輸入/輸出與計(jì)算

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

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

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

指令地址

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

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

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

structprocess*L;//等待信號量的進(jìn)程隊(duì)列

}semaphore;

假設(shè)一些簡單操作:block()阻塞調(diào)用它的進(jìn)程.wakeup(P)喚醒進(jìn)程P.信號量實(shí)現(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);

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

信號量是同步工具在進(jì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表示無資源可用或表示不允許進(jìn)程再進(jìn)入臨界區(qū)；

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

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

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

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

signal(mutex)；signal(mutex)；

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

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

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

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

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

缺點(diǎn)：不夠安全；wait、signal操作使用不當(dāng)會出現(xiàn)死鎖；實(shí)現(xiàn)復(fù)雜。

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

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

Bn-1

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

semaphorefull,empty,mutex;

初值:

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

do{ … produceaniteminnextp …

… addnextptobuffer …

}while(1);無互斥同步

消費(fèi)者進(jìn)程結(jié)構(gòu)（1）

do{

… removeanitemfrombuffertonextc …

… consumetheiteminnextc … }while(1);無互斥同步生產(chǎn)者進(jìn)程結(jié)構(gòu)（2）

do{ … produceaniteminnextp …

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

}while(1);互斥

消費(fèi)者進(jìn)程結(jié)構(gòu)（2）

do{

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

… c