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

1、第一章.并行計(jì)算介紹課程性質(zhì)課程性質(zhì) 是高性能計(jì)算學(xué)科專業(yè)基礎(chǔ)課是高性能計(jì)算學(xué)科專業(yè)基礎(chǔ)課常識(shí)知識(shí)常識(shí)知識(shí) 公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課 在教學(xué)計(jì)劃中的地位：核心、承上啟下在教學(xué)計(jì)劃中的地位：核心、承上啟下 前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)、前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)硬件操作系統(tǒng)、計(jì)算機(jī)硬件 后續(xù)課：高性能算法設(shè)計(jì)后續(xù)課：高性能算法設(shè)計(jì) 屬于武術(shù)中的屬于武術(shù)中的“練功練功”科目科目 “練武不練功，到頭一場(chǎng)空練武不練功，到頭一場(chǎng)空”教學(xué)目標(biāo)教學(xué)目標(biāo)掌握高性能計(jì)算基本的常識(shí)掌

2、握高性能計(jì)算基本的常識(shí) 對(duì)計(jì)算機(jī)體系結(jié)構(gòu)及其性能充分了解對(duì)計(jì)算機(jī)體系結(jié)構(gòu)及其性能充分了解培養(yǎng)初步并行算法設(shè)計(jì)和并行程序設(shè)計(jì)能力培養(yǎng)初步并行算法設(shè)計(jì)和并行程序設(shè)計(jì)能力 算法算法程序的靈魂程序的靈魂 問題求解過程：問題問題求解過程：問題想法想法算法算法程序程序 程序設(shè)計(jì)研究的層次：算法程序設(shè)計(jì)研究的層次：算法方法學(xué)方法學(xué)語言語言工具工具培養(yǎng)培養(yǎng)并行算法性能分析能力培養(yǎng)培養(yǎng)并行算法性能分析能力 評(píng)價(jià)算法、改進(jìn)算法評(píng)價(jià)算法、改進(jìn)算法學(xué)習(xí)要求學(xué)習(xí)要求 循序漸進(jìn)，切忌心浮氣躁循序漸進(jìn)，切忌心浮氣躁 提高課外學(xué)習(xí)的時(shí)間和內(nèi)容提高課外學(xué)習(xí)的時(shí)間和內(nèi)容 理解科學(xué)而不是背誦科學(xué)理解科學(xué)而不是背誦科學(xué)讀書讀書 正確

3、對(duì)待考試正確對(duì)待考試 作習(xí)題作習(xí)題 華羅庚：華羅庚：“學(xué)數(shù)學(xué)不做習(xí)題等于入寶山而空返學(xué)數(shù)學(xué)不做習(xí)題等于入寶山而空返” 作實(shí)驗(yàn)作實(shí)驗(yàn) 高性能計(jì)算學(xué)科是一門科學(xué)性與工程性并重的學(xué)高性能計(jì)算學(xué)科是一門科學(xué)性與工程性并重的學(xué)科，表現(xiàn)為理論和實(shí)踐緊密結(jié)合的特征。科，表現(xiàn)為理論和實(shí)踐緊密結(jié)合的特征。 課程介紹 參考書籍 課程書目：Grama,Gupta,Karypis,and Kumar: Introduction to Parallel Computing(Second Edition, 2003)成績組成成績組成 理論課成績理論課成績 平時(shí)成績平時(shí)成績 1020%：出勤作業(yè)實(shí)驗(yàn)：出勤作業(yè)實(shí)驗(yàn) 期中考試

4、成績期中考試成績 4050% 期末考試成績期末考試成績 4050% 實(shí)驗(yàn)課成績：出勤實(shí)驗(yàn)期末實(shí)驗(yàn)課成績：出勤實(shí)驗(yàn)期末 成績：百分制成績：百分制將作業(yè)或?qū)嶒?yàn)相關(guān)文件壓縮打包上傳，具體要求如下：將作業(yè)或?qū)嶒?yàn)相關(guān)文件壓縮打包上傳，具體要求如下：壓縮包文件命名格式：壓縮包文件命名格式： 如：如：00281001王五實(shí)驗(yàn)王五實(shí)驗(yàn)2 00281001王五第一章作業(yè)王五第一章作業(yè)不同的實(shí)驗(yàn)和作業(yè)用不同的壓縮包文件上傳，不要合在一個(gè)壓縮不同的實(shí)驗(yàn)和作業(yè)用不同的壓縮包文件上傳，不要合在一個(gè)壓縮包文件中；包文件中；對(duì)實(shí)驗(yàn)壓縮包，要求將該次實(shí)驗(yàn)工程所在目錄中的所有文件（要對(duì)實(shí)驗(yàn)壓縮包，要求將該次實(shí)驗(yàn)工程所在目錄中的

5、所有文件（要包括目錄包括目錄,但要?jiǎng)h除其中的但要?jiǎng)h除其中的debug相關(guān)目錄）壓縮，并按如上命名：相關(guān)目錄）壓縮，并按如上命名： 00281001王五實(shí)驗(yàn)王五實(shí)驗(yàn)2.rar將壓縮文件上傳即可；將壓縮文件上傳即可；實(shí)驗(yàn)提交和作業(yè)提交地址：實(shí)驗(yàn)提交和作業(yè)提交地址：1/ 提交時(shí)用戶名：提交時(shí)用戶名：student 密碼：密碼：123456 實(shí)驗(yàn)課要求到實(shí)驗(yàn)室上機(jī)實(shí)驗(yàn)課要求到實(shí)驗(yàn)室上機(jī)課件下載地址：課件下載地址： 1/ 用戶名：用戶名： zsuzyd 密碼：密碼：123456 下載請(qǐng)用下載請(qǐng)用FTP軟件軟件FileZilla我的我的Q

6、Q:360482583，E-Mail用用QQ郵箱郵箱（如果沒上線，有問題請(qǐng)留言。）（如果沒上線，有問題請(qǐng)留言。）并行計(jì)算 PART 1：基礎(chǔ)概念 PART 2：并行編程 PART 3：并行算法和應(yīng)用大綱 PART 1：基本概念p 簡介p 并行編程平臺(tái)p 并行算法設(shè)計(jì)的原則p 并行程序的解析模型 PART 2：并行編程p 基于共享地址空間平臺(tái)的編程p 基于消息傳遞平臺(tái)的編程大綱 PART 3：并行算法和應(yīng)用p 稠密矩陣算法p 排序p 圖算法p 離散優(yōu)化問題p 動(dòng)態(tài)規(guī)劃p 快速傅里葉變換并行的動(dòng)機(jī)從摩爾定律談起 摩爾定律：當(dāng)價(jià)格不變時(shí)，集成電路（IC）上的晶體管數(shù)目，約每隔24個(gè)月（1975年更改

7、為18個(gè)月）便會(huì)增加一倍，性能也將提升一倍。122022-7-5超級(jí)計(jì)算機(jī)性能計(jì)算量綱應(yīng)用需求應(yīng)用需求 計(jì)算密集型應(yīng)用（Computing-intensive)： 大型科學(xué)工程計(jì)算，數(shù)值模擬等。 應(yīng)用領(lǐng)域：石油、氣象、CAD、核能、制藥、環(huán)境監(jiān)測(cè)分析、系統(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)用對(duì)計(jì)算能力的需求各應(yīng)用對(duì)計(jì)算

8、能力的需求摩爾定律不能延續(xù)？ 集成電路（IC）上的晶體管數(shù)目的物理極限 半導(dǎo)體行業(yè)演進(jìn)到22 nm或更小尺寸的時(shí)候，生產(chǎn)晶體管的工藝快要達(dá)到原子理論和量子力學(xué)所決定的物理極限。 如何延續(xù)摩爾定律？處理器發(fā)展趨勢(shì)：單核多核如何延續(xù)摩爾定律？處理器性能 = 主頻x單位時(shí)鐘周期內(nèi)的指令執(zhí)行 提高處理器性能的兩大途徑 增加處理器主頻 增加每個(gè)時(shí)鐘周期內(nèi)的指令執(zhí)行數(shù) 單核處理器提升性能的主要途徑是提升主頻 事實(shí)：功耗正比于主頻的三次方 提升主頻將導(dǎo)致功耗快速增長 多核處理器的功耗隨核心數(shù)線性增長 每個(gè)時(shí)鐘周期內(nèi)的指令執(zhí)行數(shù)正比于核心數(shù) “加核 = 加性能”處理器功耗正比于 電流 x 電壓 x 電壓 x

9、主頻主頻正比于 電壓處理器發(fā)展趨勢(shì)：多核與眾核 多核處理器是首個(gè)解決能耗問題的方案 傳統(tǒng)的處理器架構(gòu)是針對(duì)單線程性能優(yōu)化的，而非效能優(yōu)化 大量能源用于優(yōu)化內(nèi)存?zhèn)鬏?、預(yù)測(cè)分支等方面的控制電路 少量能源供算術(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ì)算平臺(tái)性能增長預(yù)測(cè)超算集群性能指標(biāo)與Linpack HPC計(jì)算能力的衡量指標(biāo)：每秒浮點(diǎn)運(yùn)算次數(shù)FLOPS H P C 性 能 測(cè) 試

10、軟 件 ： L i n p a c k benchmark (High Performance Linpack，HPL) 求解稠密線性方程組的 高斯消元法bAx 超算集群性能指標(biāo)與Linpack(續(xù)） Linpack 的發(fā)展 1970年代-1980年代初 Jack Dongarra, Jim Bunch, Cleve Moler和Gilbert StewartJack DongarraCleve Moler(matlab 創(chuàng)始人)并行算法性能指標(biāo) 可擴(kuò)放性（ Scalability）：隨著計(jì)算設(shè)備數(shù)增加，運(yùn)行時(shí)間減少 主要指標(biāo)：加速比 SUabs為絕對(duì)加速比，tS為串行算法運(yùn)行時(shí)間，tA為并行

11、算法運(yùn)行時(shí)間，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ā)性硬件高并行性 指令操作的高并行性：硬件每個(gè)時(shí)鐘周期提供數(shù)億次并行操作 數(shù)據(jù)交換的高并行性：每一時(shí)刻，支持?jǐn)?shù)億個(gè)數(shù)據(jù)在交換要發(fā)揮硬件的性能，需要超大規(guī)模的計(jì)算問題 軟件的高并發(fā)性部分?jǐn)?shù)據(jù)引自 Cray 公司2012年資料邁向十億億次計(jì)算的4大挑戰(zhàn)（續(xù)） 容錯(cuò)能力 隨著硬件規(guī)模的擴(kuò)大，硬件故障發(fā)生的概率隨之增大 據(jù)統(tǒng)計(jì)，美國橡樹嶺國家實(shí)驗(yàn)室的Jaguar集群

12、每4分鐘就會(huì)有內(nèi)存出現(xiàn)錯(cuò)誤。 編程困難 由硬件的復(fù)雜性和軟件的高并發(fā)性要求引起的部分?jǐn)?shù)據(jù)引自 Cray 公司2012年資料計(jì)算機(jī)的基本工作原理存儲(chǔ)程序控制原理所謂程序存儲(chǔ),就是將解題的程序(指令序列)和它要處理的數(shù)據(jù)以二進(jìn)制形式表示，并預(yù)先存放到存儲(chǔ)器中。所謂的程序控制,就是程序運(yùn)行時(shí)計(jì)算機(jī)的控制器按照存儲(chǔ)的程序來控制整個(gè)計(jì)算機(jī)協(xié)調(diào)地完成計(jì)算任務(wù),這就是著名的“存儲(chǔ)程序控制原理” 馮諾依曼計(jì)算機(jī)的基本工作原理 存儲(chǔ)程序控制 (存儲(chǔ)程序與程序控制)程序: 一個(gè)指令序列指令: 可以被計(jì)算機(jī)理解并執(zhí)行的基本操作命令指令與數(shù)據(jù)的存儲(chǔ)運(yùn)行和運(yùn)算：采用二進(jìn)制編碼形式存儲(chǔ)程序：程序和數(shù)據(jù)預(yù)先存放在存儲(chǔ)器內(nèi)程

13、序控制：計(jì)算機(jī)工作時(shí)，CPU依次從存儲(chǔ)器中取出一個(gè)程序中的各條指令（取指令），對(duì)指令的功能進(jìn)行分析（指令譯碼），按指令的功能從內(nèi)存取出數(shù)據(jù)（取數(shù)），對(duì)數(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ī)的工作由程序控制，程序是一個(gè)指令序列，指令是能被計(jì)算機(jī)理解和執(zhí)行的操作命令；(2) 程序(指令)和數(shù)據(jù)均以二進(jìn)制編碼表示，均存放在存儲(chǔ)器中；(3) 存儲(chǔ)器中存放的指令和數(shù)據(jù)按地址進(jìn)行存取 ；(4) 指令是由CPU一條一條順序執(zhí)行的。中央處理器運(yùn)算器和控制器輸入設(shè)備輸出設(shè)備存儲(chǔ)器“存儲(chǔ)程序控制”

14、原理 將問題的解算步驟編制成為程序，程序連同它所處理的數(shù)據(jù)都用二進(jìn)位表示并預(yù)先存放在存儲(chǔ)器中 程序運(yùn)行時(shí)，CPU從內(nèi)存中一條一條地取出指令和相應(yīng)的數(shù)據(jù)，按指令操作碼的規(guī)定，對(duì)數(shù)據(jù)進(jìn)行運(yùn)算處理，直到程序執(zhí)行完畢為止 CPU從內(nèi)存中逐條讀取該程序的指令及相關(guān)的數(shù)據(jù)將指令的運(yùn)算處理結(jié)果送回內(nèi)存保存任務(wù)完成后，將處理得到的全部結(jié)果成批傳送到外存以長久保存外存儲(chǔ)器內(nèi)存儲(chǔ)器CPU任務(wù)啟動(dòng)時(shí)，執(zhí)行該任務(wù)的程序和數(shù)據(jù)從外存成批傳送到內(nèi)存指令1指令2指令k指令n程序數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)m數(shù)據(jù)CPU逐條執(zhí)行指令,按指令 要 求 完 成對(duì) 數(shù) 據(jù) 的 運(yùn)算和處理計(jì)算機(jī)的基本工作原理存儲(chǔ)程序原理存儲(chǔ)程序思想可以概括為以下

15、幾點(diǎn):1. 計(jì)算機(jī)應(yīng)包括運(yùn)算器、存儲(chǔ)器、控制器和輸入/輸出設(shè) 備。計(jì)算機(jī)能夠判斷出存儲(chǔ)器中存放的是指令還是數(shù) 據(jù)，控制器能自動(dòng)執(zhí)行指令，運(yùn)算器能進(jìn)行基本的算術(shù) 運(yùn)算和邏輯運(yùn)算，同時(shí)，操作人員通過輸入/輸出與計(jì)算 機(jī)交換信息。2. 計(jì)算機(jī)內(nèi)部應(yīng)采用二進(jìn)制碼表示指令和數(shù)據(jù)。3. 將編好的程序和原始數(shù)據(jù)送入內(nèi)部存儲(chǔ)器中，然后啟動(dòng) 計(jì)算機(jī)工作，計(jì)算機(jī)就能自動(dòng)讀取和執(zhí)行指令存儲(chǔ)器中央處理器存儲(chǔ)數(shù)據(jù)和指令執(zhí)行指令處理數(shù)據(jù)指令，數(shù)據(jù)處理結(jié)果CPU的任務(wù) CPU的主要任務(wù)是執(zhí)行指令，它按指令的規(guī)定對(duì)數(shù)據(jù)進(jìn)行操作指令是什么？ 指令就是命令，它用來規(guī)定CPU執(zhí)行什么操作。指令是構(gòu)成程序的基本單位，程序是由一連串指

16、令組成的 指令采用二進(jìn)位表示，大多數(shù)情況下，指令由兩個(gè)部分組成： 操作碼操 作 數(shù) 地 址指出CPU應(yīng)執(zhí)行何種操作的一個(gè)命令詞，例如加、減、乘、除、取數(shù)、存數(shù)等 指出該指令所操作(處理)的數(shù)據(jù)或者數(shù)據(jù)所在位置 舉例: 10 02 06把02存儲(chǔ)單元和06存儲(chǔ)單元中的內(nèi)容相加，和數(shù)保存在02單元CPU的組成CPU的三個(gè)組成部分CPU的主要任務(wù)是執(zhí)行指令，它按照指令的要求完成對(duì)數(shù)據(jù)的運(yùn)算和處理。它主要由三個(gè)部分組成：(1)寄存器組 它由十幾個(gè)甚至幾十個(gè)寄存器組成。 (2)運(yùn)算器用來對(duì)數(shù)據(jù)進(jìn)行加、減、乘、除或者與、或、非等各種基本的算術(shù)運(yùn)算和邏輯運(yùn)算，所以也稱為算術(shù)邏輯部件(ALU)。運(yùn)算器中的AL

17、U可能有多個(gè)，(3)控制器這是CPU的指揮中心。它有一個(gè)指令計(jì)數(shù)器，用來存放CPU正在執(zhí)行的指令的地址，控制器中還有一個(gè)指令寄存器，它用來保存當(dāng)前正在執(zhí)行的指令，通過譯碼器解釋該指令的含義，控制運(yùn)算器的操作，記錄CPU的內(nèi)部狀態(tài)等。CPU的結(jié)構(gòu)和任務(wù) CPU主要由運(yùn)算器、控制器和寄存器組3個(gè)部分組成 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)存儲(chǔ)器指 令 指令地址 操作數(shù)地址存放待執(zhí)行指令的地址已經(jīng)啟動(dòng)運(yùn)行的程序和數(shù)據(jù)存放待執(zhí)行的指令并進(jìn)行譯碼完成規(guī)定的運(yùn)算暫存等待處理的數(shù)據(jù)操作命令內(nèi)存

18、儲(chǔ)器AC927BALU0 1 2 3 4 5 6 7運(yùn)算器(ALU)與通用寄存器(GPR)運(yùn)算器用來對(duì)數(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速度的幾個(gè)因素CPU主頻 CPU的內(nèi)部頻率(MHz） 。決定了CPU內(nèi)部數(shù)據(jù)傳輸和指令執(zhí)行的每一步所占用的時(shí)間。 主頻越高， CPU

19、的處理速度就越快。 CPU速度 = 主頻 * IPC (每個(gè)時(shí)鐘脈沖出現(xiàn)時(shí)可執(zhí)行的 指令條數(shù)) 主頻為2G的CPU速度主頻為1G的CPU速度的2倍 Intel 的2G主頻CPU的速度AMD的2G主頻CPU的速度CPU總線頻率 CPU的外部頻率(MHz），是CPU和外界交換數(shù)據(jù)的工作頻率。影響CPU速度的幾個(gè)因素Cache容量 Cache容量越大，訪問Cache的命中率就越高，CPU的速度就越快。寄存器、運(yùn)算器的位數(shù) 位數(shù)越多， CPU的運(yùn)算速度越快進(jìn)程概念 進(jìn)程引入進(jìn)程引入： OS需要支持其內(nèi)部的需要支持其內(nèi)部的(正在執(zhí)行的正在執(zhí)行的)程序活動(dòng)，這些活動(dòng)在許程序活動(dòng)，這些活動(dòng)在許多方面都相似，

20、因此將它們抽象為多方面都相似，因此將它們抽象為進(jìn)程進(jìn)程。 活動(dòng)有：內(nèi)存管理、通信、使用I/O設(shè)備、占用/釋放CPU等 程序不能作為資源的擁有者：否則，不同程序不可擁有同一個(gè)互斥程序不能作為資源的擁有者：否則，不同程序不可擁有同一個(gè)互斥資源？但資源？但Word和和Excel都可用打印機(jī)。另外，同一個(gè)程序執(zhí)行多次都可用打印機(jī)。另外，同一個(gè)程序執(zhí)行多次時(shí)會(huì)導(dǎo)致問題：時(shí)會(huì)導(dǎo)致問題：Word運(yùn)行兩次，分別編輯兩個(gè)不同文檔，可同時(shí)在運(yùn)行兩次，分別編輯兩個(gè)不同文檔，可同時(shí)在一臺(tái)打印機(jī)上打印？一臺(tái)打印機(jī)上打??？ 進(jìn)程為了描述程序在并發(fā)執(zhí)行時(shí)對(duì)系統(tǒng)資源的共享使用，所進(jìn)程為了描述程序在并發(fā)執(zhí)行時(shí)對(duì)系統(tǒng)資源的共享使

21、用，所需的一個(gè)需的一個(gè)描述程序執(zhí)行時(shí)動(dòng)態(tài)特征描述程序執(zhí)行時(shí)動(dòng)態(tài)特征的概念的概念 注意：引入多進(jìn)程，提高了對(duì)硬件資源的利用率，但又帶來額外的空間和時(shí)注意：引入多進(jìn)程，提高了對(duì)硬件資源的利用率，但又帶來額外的空間和時(shí)間開銷，增加了間開銷，增加了OS 的復(fù)雜性的復(fù)雜性 進(jìn)程的定義進(jìn)程的定義 一個(gè)具有一定獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的一次動(dòng)態(tài)執(zhí)一個(gè)具有一定獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的一次動(dòng)態(tài)執(zhí)行過程行過程。進(jìn)程狀態(tài) 運(yùn)行狀態(tài)運(yùn)行狀態(tài)(Running)：占用處理機(jī)資源；處于此狀態(tài)：占用處理機(jī)資源；處于此狀態(tài)的進(jìn)程的數(shù)目小于等于的進(jìn)程的數(shù)目小于等于CPU的數(shù)目。的數(shù)目。 在沒有其他進(jìn)程可以執(zhí)行時(shí)（如

22、所有進(jìn)程都在阻塞狀態(tài)），在沒有其他進(jìn)程可以執(zhí)行時(shí)（如所有進(jìn)程都在阻塞狀態(tài)），通常會(huì)自動(dòng)執(zhí)行系統(tǒng)的通常會(huì)自動(dòng)執(zhí)行系統(tǒng)的idle進(jìn)程（相當(dāng)于空操作）。進(jìn)程（相當(dāng)于空操作）。 就緒狀態(tài)就緒狀態(tài)(Ready)：進(jìn)程已獲得除處理機(jī)外的所需資：進(jìn)程已獲得除處理機(jī)外的所需資源，等待分配處理機(jī)資源；只要分配源，等待分配處理機(jī)資源；只要分配CPU就可執(zhí)行。就可執(zhí)行。 可以按多個(gè)優(yōu)先級(jí)來劃分隊(duì)列，如：時(shí)間片用完可以按多個(gè)優(yōu)先級(jí)來劃分隊(duì)列，如：時(shí)間片用完低優(yōu)，低優(yōu)，I/O完成完成中優(yōu)，頁面調(diào)入完成中優(yōu)，頁面調(diào)入完成高優(yōu)高優(yōu) 等待狀態(tài)等待狀態(tài) (waiting ,Blocked阻塞阻塞)：由于進(jìn)程等待某：由于進(jìn)程等待

23、某種條件（如種條件（如I/O操作或進(jìn)程同步），在條件滿足之前無操作或進(jìn)程同步），在條件滿足之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程，也無法運(yùn)行。如：等待程，也無法運(yùn)行。如：等待I/O操作的完成。操作的完成。進(jìn)程同步進(jìn)程同步 背景背景 臨界資源臨界資源 信號(hào)量信號(hào)量 經(jīng)典同步問題經(jīng)典同步問題背景 對(duì)共享數(shù)據(jù)的并發(fā)訪問可能導(dǎo)致數(shù)據(jù)的對(duì)共享數(shù)據(jù)的并發(fā)訪問可能導(dǎo)致數(shù)據(jù)的不一致性不一致性 要保持?jǐn)?shù)據(jù)的一致性，就需要一種保證要保持?jǐn)?shù)據(jù)的一致性，就需要一種保證并發(fā)進(jìn)程的正確執(zhí)行順序的機(jī)制并發(fā)進(jìn)程的正確執(zhí)行順序的機(jī)制臨界資源進(jìn)程間資源訪問沖突進(jìn)程間資

24、源訪問沖突 共享變量的修改沖突共享變量的修改沖突 操作順序沖突操作順序沖突進(jìn)程間的制約關(guān)系進(jìn)程間的制約關(guān)系 間接制約：進(jìn)行競(jìng)爭(zhēng)獨(dú)占分配到的部分或全部共享資源，間接制約：進(jìn)行競(jìng)爭(zhēng)獨(dú)占分配到的部分或全部共享資源，“互斥互斥” 直接制約：進(jìn)行協(xié)作等待來自其他進(jìn)程的信息，直接制約：進(jìn)行協(xié)作等待來自其他進(jìn)程的信息，“同步同步” 臨界資源臨界資源: :一次只允許一個(gè)進(jìn)程使用一次只允許一個(gè)進(jìn)程使用( (訪問訪問) )的資源。如：的資源。如：硬件打印硬件打印機(jī)、磁帶機(jī)等，軟件的消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。機(jī)、磁帶機(jī)等，軟件的消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。硬件或軟件（如外設(shè)、共享代碼段、共享數(shù)據(jù)結(jié)

25、構(gòu)），多個(gè)進(jìn)程在對(duì)其進(jìn)行訪問時(shí)（關(guān)鍵是進(jìn)行寫入或修改），必須互斥地進(jìn)行有些共享資源可以同時(shí)訪問，如只讀數(shù)據(jù)多道程序環(huán)境進(jìn)程之間存在資源共享，進(jìn)程的運(yùn)行時(shí)間受影響信號(hào)量信號(hào)量(Semaphores) 操作系統(tǒng)作為一個(gè)地位高于進(jìn)程的操作系統(tǒng)作為一個(gè)地位高于進(jìn)程的管理者，可管理者，可解決公有資源的使用問題。解決公有資源的使用問題。 操作系統(tǒng)操作系統(tǒng)可從進(jìn)程管理者的角度來處理互斥的可從進(jìn)程管理者的角度來處理互斥的問題，問題，信號(hào)量信號(hào)量就是操作系統(tǒng)提供的管理公有資就是操作系統(tǒng)提供的管理公有資源的有效手段源的有效手段信號(hào)量(續(xù)) 19651965年，荷蘭學(xué)者年，荷蘭學(xué)者DijkstraDijkstra提

26、出的信號(hào)量機(jī)制是一種卓有成提出的信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工具，在長期廣泛的應(yīng)用中，信號(hào)量機(jī)制又得效的進(jìn)程同步工具，在長期廣泛的應(yīng)用中，信號(hào)量機(jī)制又得到了很大的發(fā)展，它從整型信號(hào)量機(jī)制發(fā)展到記錄型信號(hào)量到了很大的發(fā)展，它從整型信號(hào)量機(jī)制發(fā)展到記錄型信號(hào)量機(jī)制，進(jìn)而發(fā)展為機(jī)制，進(jìn)而發(fā)展為“信號(hào)集信號(hào)集”機(jī)制?，F(xiàn)在信號(hào)量機(jī)制已廣泛機(jī)制?，F(xiàn)在信號(hào)量機(jī)制已廣泛應(yīng)用于應(yīng)用于OSOS中。中。一種不需要忙等待的同步工具一種不需要忙等待的同步工具. 每個(gè)信號(hào)量每個(gè)信號(hào)量s除一個(gè)除一個(gè)整數(shù)值整數(shù)值s.value（計(jì)數(shù)）外，還有一個(gè)（計(jì)數(shù)）外，還有一個(gè)進(jìn)進(jìn)程等待隊(duì)列程等待隊(duì)列s.L 。 信號(hào)量只能通過信號(hào)

27、量只能通過初始化初始化和和兩個(gè)標(biāo)準(zhǔn)的原語操作兩個(gè)標(biāo)準(zhǔn)的原語操作來訪問來訪問作為作為OS核心代碼執(zhí)行，核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷不受進(jìn)程調(diào)度的打斷 初始化初始化指定一個(gè)非負(fù)整數(shù)值，表示指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)空閑資源總數(shù)（又稱為（又稱為資源信號(hào)量資源信號(hào)量）若為非負(fù)值表示）若為非負(fù)值表示當(dāng)前的空閑資源數(shù)當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對(duì)值表示若為負(fù)值其絕對(duì)值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù)當(dāng)前等待臨界區(qū)的進(jìn)程數(shù) “二值信號(hào)量二值信號(hào)量(binary semaphore)：只允許信號(hào)量取：只允許信號(hào)量取0或或1值值信號(hào)量實(shí)現(xiàn) 定義定義typedef struct int value; s

28、truct process *L;/等待信號(hào)量的進(jìn)程隊(duì)列等待信號(hào)量的進(jìn)程隊(duì)列 semaphore; 假設(shè)一些簡單操作假設(shè)一些簡單操作:block()阻塞調(diào)用它的進(jìn)程阻塞調(diào)用它的進(jìn)程.wakeup(P) 喚醒進(jìn)程喚醒進(jìn)程P.信號(hào)量實(shí)現(xiàn) 信號(hào)量操作信號(hào)量操作wait定義（也被稱作定義（也被稱作P操作）：操作）：wait(S) :S.value-;if (S.value 0) add this process to S.L;block(); 信號(hào)量操作信號(hào)量操作signal定義（也被稱作定義（也被稱作V操作）操作） ：signal(S) : S.value+;if (S.value 0 表示有表示有

29、S個(gè)資源可用；個(gè)資源可用； S.value=0 表示無資源可用或表示不表示無資源可用或表示不允許進(jìn)程再進(jìn)入臨界區(qū)；允許進(jìn)程再進(jìn)入臨界區(qū)； S.value0 則則|S.value|表示在等待隊(duì)表示在等待隊(duì)列中進(jìn)程的個(gè)數(shù)或表示等待進(jìn)入臨界列中進(jìn)程的個(gè)數(shù)或表示等待進(jìn)入臨界區(qū)的進(jìn)程個(gè)數(shù)。區(qū)的進(jìn)程個(gè)數(shù)。 wait(S)：表示申請(qǐng)一個(gè)資源；表示申請(qǐng)一個(gè)資源；signal(S)表示釋放一個(gè)資源。表示釋放一個(gè)資源。 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 為使多個(gè)進(jìn)程能互斥地訪問某臨界資為使多個(gè)進(jìn)程能互斥地訪問某臨界資源，只需為該資源設(shè)置一個(gè)互斥信號(hào)量源，只需為該資源設(shè)置一個(gè)互斥信號(hào)量mutex,mut

30、ex,并設(shè)其初值為并設(shè)其初值為1 1，然后將各進(jìn)程的，然后將各進(jìn)程的臨界區(qū)臨界區(qū)CSCS置于置于wait(mutex)wait(mutex)和和signal(mutex)signal(mutex)操作之間即可。利用信號(hào)操作之間即可。利用信號(hào)量實(shí)現(xiàn)共享打印機(jī)的量實(shí)現(xiàn)共享打印機(jī)的A A、B B兩進(jìn)程互斥的兩進(jìn)程互斥的類并行類并行PASCALPASCAL程序描述如下：程序描述如下：利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥-1var mutex:=semaphore:=1 var mutex:=semaphore:=1 ；beginbeginparbeginparbeginA:begin B:be

31、ginA:begin B:begin Input datd 1 from I/0 1 Input datd 1 from I/0 1 ； Input datd 2 from I/O 2 Input datd 2 from I/O 2 ； Compute Compute； Compute Compute； wait(mutex) wait(mutex) ； wait(mutex) wait(mutex) ； Print results1 by printer; Print results2 by printer; Print results1 by printer; Print results2

32、 by printer; signal(mutex) signal(mutex) ； signal(mutex) signal(mutex) ； end end end endparendparendend end 利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步 利用信號(hào)量能解決進(jìn)程間的同步問題，利用信號(hào)量能解決進(jìn)程間的同步問題，這里以如圖所示的計(jì)算進(jìn)程這里以如圖所示的計(jì)算進(jìn)程C C和打印進(jìn)和打印進(jìn)程程P P通過緩沖區(qū)通過緩沖區(qū)BufferBuffer傳送數(shù)據(jù)的同步傳送數(shù)據(jù)的同步問題為例說明。問題為例說明。 BufferCP利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步-1C C和和P P兩進(jìn)程基

33、本算法如下：兩進(jìn)程基本算法如下：C C：begin P: begin begin P: begin repeat repeat repeat repeat Compute next number ; take from Buffer ; Compute next number ; take from Buffer ; add to Buffer ; print last number ; add to Buffer ; print last number ; until false until false until false until false end end end end C C和

34、和P P兩進(jìn)程并發(fā)執(zhí)行，必須在執(zhí)行序列上遵循以下規(guī)則，才兩進(jìn)程并發(fā)執(zhí)行，必須在執(zhí)行序列上遵循以下規(guī)則，才能避免錯(cuò)誤。能避免錯(cuò)誤。 只有當(dāng)只有當(dāng)C C進(jìn)程把數(shù)據(jù)送入進(jìn)程把數(shù)據(jù)送入BufferBuffer后，后，P P進(jìn)程才能從進(jìn)程才能從BufferBuffer中取出數(shù)據(jù)來打印，否則中取出數(shù)據(jù)來打印，否則P P進(jìn)程只能等待。進(jìn)程只能等待。 只有當(dāng)只有當(dāng)P P進(jìn)程從進(jìn)程從BufferBuffer中取走數(shù)據(jù)后，中取走數(shù)據(jù)后，C C進(jìn)程才能將新計(jì)進(jìn)程才能將新計(jì)算的數(shù)據(jù)再存入算的數(shù)據(jù)再存入Buffer,Buffer,否則否則C C進(jìn)程也只能等待。進(jìn)程也只能等待。利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步

35、-2 為了實(shí)現(xiàn)進(jìn)程同步，需采用同步信號(hào)為了實(shí)現(xiàn)進(jìn)程同步，需采用同步信號(hào)量。為了滿足第一條同步規(guī)則，設(shè)置量。為了滿足第一條同步規(guī)則，設(shè)置一個(gè)同步信號(hào)量一個(gè)同步信號(hào)量fullfull，它代表的資源它代表的資源是緩沖器滿，它的初值為是緩沖器滿，它的初值為0 0。同樣為了。同樣為了滿足第二條同步規(guī)則，設(shè)置另一個(gè)同滿足第二條同步規(guī)則，設(shè)置另一個(gè)同步信號(hào)量步信號(hào)量emptyempty，它代表的資源是緩沖它代表的資源是緩沖器空，它的初值為器空，它的初值為1 1 。 實(shí)現(xiàn)實(shí)現(xiàn)C C和和P P兩進(jìn)程同步的類兩進(jìn)程同步的類PASCALPASCAL程序：程序：var: empty,full:semaphore:=1

36、,0 var: empty,full:semaphore:=1,0 ； begin begin parbegin parbegin C: begin C: begin repeat repeat Compute next number Compute next number ； wait(empty) wait(empty) ； Add to buffer Add to buffer ； siganl(full) siganl(full) ； until false until false end end P: begin P: begin repeat repeat wait(full) w

37、ait(full) ； Take from Buffer Take from Buffer ； signal(empty) signal(empty) ； Print last number Print last number ； until false until false end end parend parendendendwait、signal操作討論操作討論 wait、signal操作必須成對(duì)出現(xiàn)，有一個(gè)操作必須成對(duì)出現(xiàn)，有一個(gè)wait操作就一操作就一定有一個(gè)定有一個(gè)signal操作。操作。 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程。當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程。 當(dāng)為同步操作時(shí)，

38、則不在同一進(jìn)程中出現(xiàn)。當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)。 如果兩個(gè)如果兩個(gè)wait操作相鄰，那么它們的順序至關(guān)重要，操作相鄰，那么它們的順序至關(guān)重要，而兩個(gè)相鄰的而兩個(gè)相鄰的signal操作的順序無關(guān)緊要。一個(gè)同步操作的順序無關(guān)緊要。一個(gè)同步wait操作與一個(gè)互斥操作與一個(gè)互斥wait操作在一起時(shí)，同步操作在一起時(shí)，同步wait操作操作在互斥在互斥wait操作前。操作前。 wait、signal操作的優(yōu)缺點(diǎn)操作的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)（用（用wait、signal操作可操作可解決任何同步互斥問題。）解決任何同步互斥問題。） 缺點(diǎn)：不夠安全；缺點(diǎn)：不夠安

39、全；wait、signal操作使用不當(dāng)會(huì)出現(xiàn)死操作使用不當(dāng)會(huì)出現(xiàn)死鎖；實(shí)現(xiàn)復(fù)雜。鎖；實(shí)現(xiàn)復(fù)雜。 經(jīng)典同步問題 有限緩沖區(qū)問題有限緩沖區(qū)問題(生產(chǎn)者消費(fèi)者問題）生產(chǎn)者消費(fèi)者問題） 讀者寫者問題讀者寫者問題有限緩沖有限緩沖問題問題 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問題消費(fèi)者問題 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問題是最著名的同步問題，消費(fèi)者問題是最著名的同步問題，它描述一組生產(chǎn)者（它描述一組生產(chǎn)者（P P1 1 P Pm m）向一向一組消費(fèi)者（組消費(fèi)者（C C1 1C Cq q）提供消息。它們提供消息。它們共享一個(gè)有界緩沖池（共享一個(gè)有界緩沖池（bounded buffer bounded buffer pool

40、pool）, ,生產(chǎn)者向其中投放消息，消費(fèi)者生產(chǎn)者向其中投放消息，消費(fèi)者從中取得消息，如下圖所示。生產(chǎn)者從中取得消息，如下圖所示。生產(chǎn)者- -消消費(fèi)者問題是許多相互合作進(jìn)程的一種抽費(fèi)者問題是許多相互合作進(jìn)程的一種抽象。象。有限緩沖有限緩沖問題問題 假定緩沖池中有假定緩沖池中有n n個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)存放一個(gè)消息。個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)存放一個(gè)消息。由于緩沖池是臨界資源，它只允許一個(gè)生產(chǎn)者投入消息，或由于緩沖池是臨界資源，它只允許一個(gè)生產(chǎn)者投入消息，或者一個(gè)消費(fèi)者從中取出消息。即生產(chǎn)者之間、生產(chǎn)者與消費(fèi)者一個(gè)消費(fèi)者從中取出消息。即生產(chǎn)者之間、生產(chǎn)者與消費(fèi)者之間、消費(fèi)者之間都必須互斥使用緩沖池。所

41、以必須設(shè)置者之間、消費(fèi)者之間都必須互斥使用緩沖池。所以必須設(shè)置互斥信號(hào)量互斥信號(hào)量mutexmutex，它代表緩沖池資源，它的數(shù)值為它代表緩沖池資源，它的數(shù)值為1 1。P1PmmC1CqB0 B1 . . Bn-1 有限緩沖有限緩沖問題問題生產(chǎn)者和消費(fèi)者二類進(jìn)程生產(chǎn)者和消費(fèi)者二類進(jìn)程P P和和C C之間應(yīng)滿足下列二個(gè)同之間應(yīng)滿足下列二個(gè)同步條件：步條件：l 只有在緩沖池中至少有一個(gè)緩沖區(qū)已存入消息后，只有在緩沖池中至少有一個(gè)緩沖區(qū)已存入消息后，消費(fèi)者才能從中提取消息，否則消費(fèi)者必須等待。消費(fèi)者才能從中提取消息，否則消費(fèi)者必須等待。l 只有緩沖池中至少有一個(gè)緩沖區(qū)是空時(shí)，生產(chǎn)者才只有緩沖池中至少

42、有一個(gè)緩沖區(qū)是空時(shí)，生產(chǎn)者才能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等待。能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等待。 為了滿足第一個(gè)同步條件，設(shè)置一個(gè)同步信號(hào)量為了滿足第一個(gè)同步條件，設(shè)置一個(gè)同步信號(hào)量fullfull，它代表的資源是緩沖區(qū)滿，它的初始值為它代表的資源是緩沖區(qū)滿，它的初始值為0 0，它的值為它的值為n n時(shí)整個(gè)緩沖池滿。同樣為了滿足第二個(gè)同時(shí)整個(gè)緩沖池滿。同樣為了滿足第二個(gè)同步條件，設(shè)置另一個(gè)同步信號(hào)量步條件，設(shè)置另一個(gè)同步信號(hào)量emptyempty，它代表的資它代表的資源是緩沖區(qū)空，它的初始值為源是緩沖區(qū)空，它的初始值為n n，表示緩沖池中所有表示緩沖池中所有緩沖區(qū)空。緩沖區(qū)空。有限緩沖有限緩沖問題問題 定義信號(hào)量定義信號(hào)量semaphore full, empty, mutex;初值初值:full = 0, empty = n, mutex = 1 n表示緩沖區(qū)個(gè)數(shù)表示緩沖區(qū)個(gè)數(shù)生產(chǎn)者進(jìn)程結(jié)構(gòu)（1）do produce an item in nextp add nextp to buffer while (1);無互斥同步無互斥同步消費(fèi)者進(jìn)程結(jié)構(gòu)（1）do remove an item from buffer to nextc consume the it