1、多核程序設(shè)計,參考資料： 1. 多核系列教材編寫組.多核程序設(shè)計.清華大學出版社(第7版),2007.9 2. David B.Kirk,Wen-mei W.Hwu著.陳曙暉,熊淑華譯.大規(guī)模并行處理器編程實踐.清華大學出版社,2010.9 3. Maurice Herlihy,Nir Shavit著.金海,胡侃譯.多處理器編程的藝術(shù).機械工業(yè)出版社,2009.8 4. Richard Gerber, Aart J.C.Bik, Kevin B.Smith等著, 王濤,單久龍,孫廣中譯.軟件優(yōu)化技術(shù)IA-32平臺的高性能手冊(第2版) .電子工業(yè)出版社,2007.4,多核程序設(shè)計,電子書及資料

2、下載：,多核程序設(shè)計,第一章 多核技術(shù)導論,微處理器發(fā)展史,1945年，世界上第一臺全自動電子數(shù)字計算機ENIAC 計算機的發(fā)展按照硬件工藝可以分為 第一代（19461958）：電子管數(shù)字計算機。 第二代（19581964）：晶體管數(shù)字計算機。 第三代（19641971）：集成電路數(shù)字計算機。 第四代(1971年以后）：大規(guī)模集成電路數(shù)字計算機。 微處理器 第一代微處理器(4位)：英特爾4004,8008 第二代微處理器(8位)：采用NMOS工藝,采用匯編語言、BASIC、Fortran編程，使用單用戶操作系統(tǒng)。如英特爾8080,8085。 第三代微處理器(16位)：以1978年英特爾的808

3、6出現(xiàn)為起點。 第四代微處理器(32位)：運算模式包括實模式、保護模式和“虛擬86”。英特爾80386 DX, 80486, Pentium 4,并行計算機,由一組處理單元組成，這組處理單元通過相互之間的通信與協(xié)作，以更快的速度共同完成一項大規(guī)模的計算任務(wù)。 出現(xiàn)背景: 60年代初期，晶體管以及磁芯存儲器的出現(xiàn)，處理單元變得越來越小，存儲器也更加小巧和廉價。出現(xiàn)規(guī)模不大的共享存儲多處理器系統(tǒng)，即大型主機（典型代表：IBM360）。 60 年代末期，同一個處理器開始設(shè)置多個功能相同的功能單元，流水線技術(shù)也出現(xiàn)了，在處理器內(nèi)部的應(yīng)用大大提高了并行計算機系統(tǒng)的性能。 兩個最主要的組成部分 計算節(jié)點

4、節(jié)點間的通信與協(xié)作機制,并行計算機的弗林分類,Flynn根據(jù)指令流和數(shù)據(jù)流的不同組織方式，把計算機系統(tǒng)的結(jié)構(gòu)分為以下四類： 單指令流單數(shù)據(jù)流（Single Instruction stream Single Data stream, SISD） 單指令流多數(shù)據(jù)流（Single Instruction stream Multiple Data stream, SIMD） 多指令流單數(shù)據(jù)流（Multiple Instruction stream Single Data stream, MISD） 多指令流多數(shù)據(jù)流（Multiple Instruction stream Multiple Data

5、stream, MISD）,并行計算機從系統(tǒng)結(jié)構(gòu)角度分類,分布式存儲器的SIMD處理機 含有多個同樣結(jié)構(gòu)的處理單元（PE），通過尋徑網(wǎng)絡(luò)以一定方式互相連接。每個PE有各自的本地存儲器（LM）。 向量超級計算機（共享式存儲器SIMD） 集中設(shè)置存儲器，共享的多個并行存儲器通過對準網(wǎng)絡(luò)與各處理單元PE相連。在處理單元數(shù)目不太大的情況下很理想。 對稱多處理器（SMP） 一個計算機上匯集了一組處理器，各處理器之間共享內(nèi)存子系統(tǒng)以及總線結(jié)構(gòu)。 并行向量處理機（PVP） 使用定制的高帶寬網(wǎng)絡(luò)將向量處理器連向共享存儲器模塊 使用大量的向量寄存器和指令緩沖器 集群計算機 由許多連在一起的獨立計算機組成，像一個

6、單獨集成的計算機資源一樣協(xié)同工作，用來解決大型計算問題。,片上多核處理器架構(gòu),片上多核處理器（Chip Multi-Processor，CMP）就是將多個計算內(nèi)核集成在一個處理器芯片中，從而提高計算能力。 按計算內(nèi)核的對等與否，CMP可分為同構(gòu)多核和異構(gòu)多核 CPU核心數(shù)據(jù)共享與同步的通信機制： 總線共享Cache結(jié)構(gòu)：每個CPU內(nèi)核擁有共享的二級或三級Cache，用于保存比較常用的數(shù)據(jù)，并通過連接核心的總線進行通信。 基于片上互連的結(jié)構(gòu)：每個CPU核心具有獨立的處理單元和Cache，各個CPU核心通過交叉開關(guān)或片上網(wǎng)絡(luò)等方式連接在一起。 給程序開發(fā)者帶來的挑戰(zhàn),典型多核芯片架構(gòu),芯片組對多核

7、的支持固件,固件是一種嵌入到硬件設(shè)備中的軟件。它通常燒寫在flash等介質(zhì)中，可以被當作一個二進制映像文件由用戶從硬件設(shè)備中調(diào)用。 固件是在集成電路只讀存儲器中的計算機程序，是可擦寫可編程芯片，其上的程序可以通過專門的外部硬件進行修改，但是不能被一般的應(yīng)用程序改動。,芯片組對多核的支持固件(續(xù)),BIOS（Basic Input/Output System） 作為系統(tǒng)硬件和操作系統(tǒng)之間的抽象層，主要用來初始化和配置系統(tǒng)的硬件，啟動操作系統(tǒng)以及提供對系統(tǒng)設(shè)備底層的通訊。 BIOS是連接CPU、芯片組和操作系統(tǒng)的固件，是IBM兼容計算機中啟動時調(diào)用的固件代碼。 由兩部分組成:上電自舉即POST（P

8、ower On Self Test）和在線的中斷服務(wù)（主要由legacy 操作系統(tǒng)使用）。 計算機加電時BIOS從flash、PROM或是EPROM中啟動并完成初始化，進行加電自檢，對硬盤，內(nèi)存，顯卡，主板等硬件進行掃描檢查，然后它將自己從BIOS內(nèi)存空間中解壓到系統(tǒng)的內(nèi)存空間中，并開始從那里運行。 正在被以EFI（Extensible Firmware Interface，可擴展固件接口）為代表的新一代技術(shù)所取代。,芯片組對多核的支持固件(續(xù)2),EFI（可擴展固件接口） 在操作系統(tǒng)與平臺固件之間的軟件接口。 EFI規(guī)范定義的接口包括包含平臺信息的數(shù)據(jù)表和啟動時及啟動后的服務(wù)。 EFI啟動管

9、理器被用來選擇裝載操作系統(tǒng)，不再需要專門的啟動裝載器機制輔助。 Framework是一種固件的架構(gòu)，它是EFI固件接口的一種實現(xiàn)，用來完全替代傳統(tǒng)的BIOS。,EFI對多核支持,在Framework中定義了兩類處理器 BSP（boot strap processor），執(zhí)行EFI的初始化代碼，設(shè)置APIC環(huán)境，建立系統(tǒng)范圍的數(shù)據(jù)結(jié)構(gòu)，開始并初始化AP。 AP （application processor），在系統(tǒng)上電或重啟之后，AP會自己進行一個簡單的設(shè)置，然后就等待BSP發(fā)出Startup信號。 Framework在多核計算機中初始化過程如下： SEC：從實模式切換到保護模式，處理不同的重啟

10、事件、對每個處理器進行緩存設(shè)置。 PEI：做盡量少的硬件初始化，而把更多的留給DXE。 DXE：對所有可用的硬件設(shè)備進行初始化，為建立控制臺和啟動操作系統(tǒng)提供必要的服務(wù)。 BDS：建立所需的控制臺設(shè)備，在輸出控制臺上顯示用戶界面。 當系統(tǒng)最后選擇啟動到操作系統(tǒng)時，EFI需要提交包括處理器在內(nèi)的有關(guān)信息。,操作系統(tǒng)對多核處理器的支持方法,調(diào)度與中斷 對任務(wù)的分配進行優(yōu)化。使同一應(yīng)用程序的任務(wù)盡量在一個核上執(zhí)行。 對任務(wù)的共享數(shù)據(jù)優(yōu)化。由于CMP體系結(jié)構(gòu)共享二級緩存，可以考慮改變?nèi)蝿?wù)在內(nèi)存中的數(shù)據(jù)分布，使任務(wù)在執(zhí)行時盡量增加二級緩存的命中率。 對任務(wù)的負載均衡優(yōu)化。當任務(wù)在調(diào)度時，出現(xiàn)了負載不均衡

11、，考慮將較忙處理器中與其他任務(wù)最不相關(guān)的任務(wù)遷移，以達到數(shù)據(jù)的沖突量小。 輸入輸出系統(tǒng) 多核體系處理器中，必須將中斷處理分發(fā)給一組核處理。 存儲管理與文件系統(tǒng) 庫函數(shù)做成非阻塞調(diào)用方式（需要保證數(shù)據(jù)同步的機制） 使用多線程內(nèi)存分配,操作系統(tǒng)對多核處理器的支持方法,多核程序設(shè)計,第二章 并行計算基礎(chǔ),并行計算機體系結(jié)構(gòu),組成并行計算機的各個部分： 節(jié)點（node） 互聯(lián)網(wǎng)絡(luò)（interconnect network） 內(nèi)存 （memory）,內(nèi)存模塊與節(jié)點分離,內(nèi)存模塊位于節(jié)點內(nèi)部,多級存儲體系結(jié)構(gòu),為了解決內(nèi)存墻（memory wall）性能瓶頸問題。 在節(jié)點內(nèi)部的cache稱為二級cache

12、（L2 cache）。 在處理器內(nèi)部更小的cache成為一級cache（L1 cache）。 L1 cache連接CPU寄存器和L2 cache，負責緩存L2 cache中的數(shù)據(jù)到寄存器中。,多級存儲體系結(jié)構(gòu),并行計算機的多級存儲結(jié)構(gòu)主要包括兩個問題： Cache的映射策略，即cache如何從內(nèi)存中取得數(shù)據(jù)進行存儲； 節(jié)點內(nèi)部或者節(jié)點之間內(nèi)存的訪問模式 。 cache原理 cache以cache線為基本單位，每條cache包含L個字，每個字8個字節(jié)。例如，L=4，則表示cache線包含4*8=32個字節(jié)。內(nèi)存空間分割成塊（block），每個塊大小與cache線長度一致，數(shù)據(jù)在內(nèi)存和cache之

13、間的移動以cache線為基本單位 。 For i =1 to M Ai = Ai + 2 * Bi 如果操作數(shù)存在cache中，稱該次訪問是命中的，否則，該次操作是“撲空”的 。,無Cache，訪問內(nèi)存2M次；有cache，訪問內(nèi)存2M/L次,多級存儲體系結(jié)構(gòu),cache的映射策略指的是內(nèi)存塊和cache線之間如何建立相互映射關(guān)系。 直接映射策略（direct mapping strategy） 每個內(nèi)存塊只能被唯一的映射到一條cache線中 K路組關(guān)聯(lián)映射策略 （K-way set association mapping strategy） Cache被分解為V個組，每個組由K條cache線

14、組成，內(nèi)存塊按直接映射策略映射到某個組，但在該組中，內(nèi)存塊可以被映射到任意一條cache線。 全關(guān)聯(lián)映射策略 （full association mapping strategy） 內(nèi)存塊可以被映射到cache中的任意一條cache線。,并行計算機訪存模型,UMA（Uniform Memory Access）模型 物理存儲器被所有節(jié)點共享； 所有節(jié)點訪問任意存儲單元的時間相同； 發(fā)生訪存競爭時，仲裁策略平等對待每個節(jié)點，即每個節(jié)點機會均等； 各節(jié)點的CPU可帶有局部私有高速緩存； 外圍I/O設(shè)備也可以共享，且每個節(jié)點有平等的訪問權(quán)利。 NUMA（Non-Uniform Memory Acces

15、s）模型 物理存儲器被所有節(jié)點共享，任意節(jié)點可以直接訪問任意內(nèi)存模塊； 節(jié)點訪問內(nèi)存模塊的速度不同，訪問本地存儲模塊的速度一般是訪問其他節(jié)點內(nèi)存模塊的3倍以上； 發(fā)生訪存競爭時，仲裁策略對節(jié)點可能是不等價的； 各節(jié)點的CPU可帶有局部私有高速緩存 （cache）； 外圍I/O設(shè)備也可以共享，但對各節(jié)點是不等價的。,并行計算機訪存模型,COMA（Cache-Only Memory Access）模型 各處理器節(jié)點中沒有存儲層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間 利用分布的高速緩存目錄D進行遠程高速緩存的訪問 COMA中的高速緩存容量一般都大于2級高速緩存容量 使用COMA時，數(shù)據(jù)開始時可以任意

16、分配，因為在運行時它最終會被遷移到要用到它的地方 NORMA（No-Remote Memory Access）模型 所有存儲器都是私有的； 絕大多數(shù)NORMA都不支持遠程存儲器的訪問； 在DSM中，NORMA就消失了。,并行計算機訪存模型,并行計算機系統(tǒng)的不同訪存模型分類,并行計算模型,SIMD同步并行計算模型 共享存儲的SIMD模型（PRAM模型） PRAM，Parallel Random Access Machine 分布存儲的SIMD模型（SIMD互聯(lián)網(wǎng)絡(luò)模型） MIMD異步并行計算模型 異步PRAM模型 BSP模型 LogP模型 C3模型,SIMD同步并行計算模型,SIMD共享存儲模型

17、（PRAM模型） PRAM-EREW （Exclusive-Read and Exclusive-Write），不允許同時讀和同時寫 PRAM-CREW （Concurrent-Read and Exclusive-Write） ，允許同時讀但不允許同時寫 PRAM-CRCW （Concurrent-Read and Concurrent-Write） ，允許同時讀和同時寫 優(yōu)點： 適合于并行算法的表達、分析和比較； 使用簡單，很多諸如處理器間通信、存儲管理和進程同步等并行計算機的低級細節(jié)均隱含于模型中； 易于設(shè)計算法和稍加修改便可運行在不同的并行計算機上； 有可能加入一些諸如同步和通信等需要

18、考慮的方面。,SIMD分布存儲模型,采用一維線性連接的SIMD模型，簡記為SIMD-LC 采用網(wǎng)孔連接的SIMD模型，簡記為SIMD-MC 采用樹形連接的SIMD模型，簡記為SIMD-TC 采用樹網(wǎng)連接的SIMD模型，簡記為SIMD-MT 采用立方連接的SIMD模型，簡記為SIMD-CC 采用立方環(huán)連接的SIMD模型，簡記為SIMD-CCC 采用洗牌交換連接的SIMD模型，簡記為SIMD-SE 采用蝶形連接的SIMD模型，簡介為SIMD-BF 采用多級互聯(lián)網(wǎng)絡(luò)連接的SIMD模型，簡記為SIMD-MIN,MIMD異步計算模型APRAM模型,APRAM特點: 每個處理器都有其本地存儲器、局部時鐘和

19、局部程序 處理器間的通信經(jīng)過共享全局存儲器 無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令 處理器任何時間依賴關(guān)系需明確地在各處理器的程序中加入同步（路）障（Synchronization Barrier） 一條指令可在非確定但有限的時間內(nèi)完成。 APRAM模型中有四類指令: 全局讀，將全局存儲單元中的內(nèi)容讀入本地存儲器單元中 局部操作，對本地存儲器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲器中 全局寫，將本地存儲器單元中的內(nèi)容寫入全本地存儲器單元中 同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達后才能繼續(xù)執(zhí)行其局部程序,MIMD異步計算模型BSP模型,大同步并行BSP (Bulk

20、 Synchronous Parallel) 模型作為計算機語言和體系結(jié)構(gòu)之間的橋梁，由以下述三個參數(shù)描述分布存儲的并行計算機模型： 處理器/存儲器模塊（下文簡稱處理器） 處理器模塊之間點到點信息傳遞的路由器 執(zhí)行以時間間隔L為周期的路障同步器 特點： 將處理器和路由器分開，強調(diào)了計算任務(wù)和通信任務(wù)的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡(luò)拓撲，又簡化了通信協(xié)議 采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔 在分析BSP模型的性能時，假定局部操作可在一個時間步內(nèi)

21、完成，而在每一超級步中，一個處理器至多發(fā)送或接受h條消息（h-relation）,MIMD異步計算模型LogP,C3模型,LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進行描述。 L:Latency, 表示消息從源到目的在網(wǎng)絡(luò)上的延遲 o:overhead, 表示處理器發(fā)送或接收一條消息消耗在網(wǎng)絡(luò)協(xié)議棧中的開銷 g:gap,表示處理器可連續(xù)進行消息發(fā)送或接收的最小時間間隔 P:Processor, 表示處理器/存儲模塊數(shù) 1/g 對應(yīng)于處理器帶寬,MIMD異步計算模型LogP,C3模型,

22、C3（Computation, Communication, Congestion）模型是一個與體系結(jié)構(gòu)無關(guān)的粗粒度的并行計算模型，旨在能反映計算復雜度，通信模式和通信期間潛在的擁擠等因素對粗粒度網(wǎng)絡(luò)算法的影響。 C3模型強調(diào)用共用的通信操作來開發(fā)粗粒度的并行算法 BSP、LogP模型采用點到點的消息傳遞來進行通信，復雜的通信操作由編程實現(xiàn),并行編程環(huán)境,比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲和數(shù)據(jù)并行： 共享存儲并行編程基于線程級細粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持數(shù)據(jù)的共享存儲，所以并行編程的難度較小，但一般情況下，當處理機個數(shù)較多時，其并行性能明顯不

23、如消息傳遞編程 ； 消息傳遞并行編程基于大粒度的進程級并行，具有最好的可擴展性，幾乎被所有當前流行的各類并行計算機所支持，其具有較好的可擴展性，但是，消息傳遞并行編程只能支持進程間的分布式存儲模式，即各個進程只能支持訪問其局部內(nèi)存空間，而對其他進程的局部內(nèi)存空間的訪問只能通過消息傳遞來實現(xiàn)，因此，學習和使用消息傳遞并行編程的難度均大于共享存儲和數(shù)據(jù)并行這兩種編程模式。,并行編程環(huán)境,比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲和數(shù)據(jù)并行,編程語言與編譯器,在科學計算領(lǐng)域?qū)Σ⑿芯幊讨С忠呀?jīng)取得相當成功的三項技術(shù)： 自動并行化 數(shù)據(jù)并行語言HPF 共享存儲并行編程接口OpenMP,編程語言

24、與編譯器,自動并行 始于20世紀70年代的自動向量化。 20世紀80年代中期，基于依賴分析的向量化工具成熟，成為向量機的標準。 自動化并行本身不足以解決并行程序設(shè)計問題。 此領(lǐng)域的研究重點逐步轉(zhuǎn)向基于語言的策略研究，即從用戶那里獲得更多的信息，同時利用自動并行化技術(shù)來減輕程序設(shè)計的負擔。,編程語言與編譯器,數(shù)據(jù)并行編程：HPF 高性能Fortran(HPF)的思想是使數(shù)據(jù)管理的多數(shù)細節(jié)自動并行化 HPF提供了一個指令集，通過注釋形式的指令來擴展變量類型的說明，能夠?qū)?shù)組的數(shù)據(jù)布局進行相當詳細的控制。 對顯式并行機制的說明相當有限，通過系統(tǒng)而非程序員把任務(wù)分配給處理機。,編程語言與編譯器,共享存

25、儲并行編程：OpenMP 由Silicon Graphics領(lǐng)導的工業(yè)協(xié)會推出了OpenMP 是一個與Fortran77和C語言綁定的并行編程接口 OpenMP指令在單機編譯器上被當作注釋而忽略 通過parallel section 指令獲得任務(wù)并行 #pragma omp parallel for 提供了鎖變量用于線程間細粒度同步 是適合于具有一致性訪存的共享存儲計算機的編程接口,并行計算性能評測,并行程序執(zhí)行時間 從并行程序開始執(zhí)行到所有進程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間 （wall clock time）。 加速比性能定律 Amdahl定律 Gustafson定律 Sun和

26、Ni定律 并行程序性能評價方法 浮點峰值性能與實際浮點性能 峰值性能等于CPU內(nèi)部浮點乘加指令流水線條數(shù)、每條流水線每個時鐘周期完成的浮點運算次數(shù)、處理器主頻三者的乘積 實際浮點性能等于并行程序的總的浮點運算次數(shù)和并行程序執(zhí)行時間的比值 數(shù)值效率和并行效率,并行計算性能評測,并行程序執(zhí)行時間 對各個進程，墻上時間可進一步分解為計算CPU時間、通信CPU時間、同步開銷時間、同步導致的進程空閑時間 計算CPU時間：進程指令執(zhí)行所花費的CPU時間，包括程序本身的指令執(zhí)行占用的時間和系統(tǒng)指令花費的時間； 通信CPU時間：進程通信花費的CPU時間； 同步開銷時間：進程同步花費的時間； 進程空閑時間：進程

27、空閑時間是指并行程序執(zhí)行過程中，進程所有空閑時間總和（如進程阻塞式等待其他進程的消息時。此時CPU通常是空閑的，或者處于等待狀態(tài)）,并行計算性能評測,加速比性能定律Amdahl定律 能夠計算并行程序相對于最優(yōu)串行算法在性能提升上的理論最大值他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個關(guān)于程序中這兩部分所占比例以及可加速部分性能加速程度的函數(shù) Amdahl定律: f 表示執(zhí)行程序中串行部分的比例，p表示處理器核的數(shù)量。假設(shè)最優(yōu)串行算法的執(zhí)行時間為一個單位時間（也就是分子為1）。 處理器核在數(shù)量上能夠無限制的增加，但是無限的處理器核卻并不能帶來性能上的無限增長，無論如何，程序性能上

28、的總是有個上限，這個要受限于串行部分所占的比例。,程序性能優(yōu)化,串行程序性能優(yōu)化 是并行程序性能優(yōu)化的基礎(chǔ)，一個好的并行程序首先應(yīng)該擁有良好的單機性能，影響程序單機性能的主要因素是程序的計算流程和處理器的體系結(jié)構(gòu) 調(diào)用高性能庫，比如優(yōu)化的BLAS，F(xiàn)FTW等 選擇適當?shù)木幾g器優(yōu)化選項 合理定義數(shù)組維數(shù) 注意嵌套循環(huán)的順序，盡量改善數(shù)據(jù)訪問的局部性 通用的原則就是盡量使最內(nèi)層循環(huán)的數(shù)據(jù)訪問連續(xù)進行 循環(huán)展開,DO I=1, N D=D+A(I) ENDDO,DO I=1, MOD(N, 4) D=D+A(I) ENDDO DO I=MOD(N, 4)+1, N, 4 D=D+A(I) +A(I+

29、1) +A(I+2) +A(I+3) ENDDO,程序性能優(yōu)化,并行程序性能優(yōu)化 最主要的是選擇好的并行算法和通信模式 減少通信量、提高通信粒度 提高通信粒度的有效方法就是減少通信次數(shù)，盡可能將可以一次傳遞的數(shù)據(jù)合并起來一起傳遞 全局通信盡量利用高效集合通信算法 對于標準的集合通信，如廣播、規(guī)約、數(shù)據(jù)散發(fā)與收集等，盡量調(diào)用MPI標準庫函數(shù) 挖掘算法的并行度，減少CPU空閑等待 具有數(shù)據(jù)相關(guān)性的計算過程會導致并行運行的部分進程空閑等待.在這種情況下，可以考慮改變算法來消除數(shù)據(jù)相關(guān)性,程序性能優(yōu)化,并行程序性能優(yōu)化 負載平衡 動態(tài)調(diào)整負載時要考慮負載調(diào)整的開銷及由于負載不平衡而引起的空閑等待對性能

30、的影響，尋找最優(yōu)負載調(diào)整方案 通信、計算的重疊 讓通信和計算重疊進行，利用計算時間來屏蔽通信時間。實現(xiàn)方法一般基于非阻塞通信，先發(fā)出非阻塞的消息接受或發(fā)送命令，然后處理與收發(fā)數(shù)據(jù)無關(guān)的計算任務(wù)，完成計算后再等待消息收發(fā)的完成。 通過引入重復計算來減少通信，即以計算換通信 由于當前大部分并行計算機的計算速度遠遠大于通信速度，并且在一些情況下，當一個進程計算時，別的進程往往處于空閑等待狀態(tài)，因而適當引入重復計算可以提高程序的總體性能,并行編譯器,并行編譯器大致由三部分組成： 流分析 確定源代碼中數(shù)據(jù)和控制的相關(guān)性 程序優(yōu)化 將代碼變換成與之等效的的更好形式，以挖掘硬件潛力 代碼生成 將代碼從一種描

31、述轉(zhuǎn)換成另一種中間形式的描述,并行編譯器,并行編譯過程,并行編譯器,流分析 要使程序并行地執(zhí)行，首先要進行相關(guān)性分析（Dependency Analysis） 四種相關(guān)形式： 流相關(guān)：從SiSj存在執(zhí)行通路，且Si至少有一個輸出被用作Sj的輸入 反相關(guān)：Sj緊接Si，且Sj的輸出被作為Si的輸入 輸出相關(guān)：兩條語句往相同的變量里寫 控制相關(guān)：語句Sj的執(zhí)行與否依賴于語句Si,并行編譯器,代碼優(yōu)化 代碼向量化（Code Vectorization）: 把標量程序中的由一種可向量化循環(huán)完成的操作變換成向量操作。 代碼并行化（Code Parallelization）:并行代碼的優(yōu)化是將一個程序展開

32、成多線程以同時供多臺處理機并行執(zhí)行，其目的是要減少總的執(zhí)行時間。 代碼生成 并行代碼生成（Code Generation）涉及到將優(yōu)化后的中間形式的代碼轉(zhuǎn)換程可執(zhí)行的具體的機器目標代碼。包括執(zhí)行次序、指令選擇、寄存器分配、負載平衡、并行粒度、代碼調(diào)度以及后優(yōu)化（Postoptimization）等問題。,多核程序設(shè)計,第三章 線程的基本概念,進程,定義：進程是具有一定獨立功能的程序關(guān)于一個數(shù)據(jù)集合的一次運行活動。可表示成四元組（P, C, D, S），其中P是程序代碼，C是進程的控制狀態(tài)，D是進程的數(shù)據(jù)，S是進程的執(zhí)行狀態(tài)。 狀態(tài)： 運行態(tài)(Run): 進程占有處理機資源, 正在運行; 就緒態(tài)

33、(Ready): 進程本身具備運行條件, 但由于處理機的個數(shù)少于可運行進程的個數(shù), 暫未投入運行; 等待態(tài)(Wait): 進程本身不具備運行條件，即使分給它處理機也不能運行. 進程正等待某一個事件的發(fā)生, 如等待某一資源被釋放，等待與該進程相關(guān)的I/O傳輸?shù)耐瓿尚盘柕取?進程,狀態(tài)間轉(zhuǎn)換 當一個就緒進程獲得處理機時, 其狀態(tài)由就緒變?yōu)檫\行； 當一個運行進程被剝奪處理機時, 其狀態(tài)由運行變?yōu)榫途w； 當一個運行進程因某事件受阻時, 如所申請資源被占用, 啟動I/O傳輸未完成, 其狀態(tài)由運行變?yōu)榈却?當所等待事件發(fā)生時, 如得到申請資源, I/O傳輸完成, 其狀態(tài)由等待變?yōu)榫途w。,進程,進程控制塊

34、(Process Control Block，PCB):標志進程存在的數(shù)據(jù)結(jié)構(gòu)，其中包含系統(tǒng)對進程管理需要的全部信息。,進程標識 用戶標識 進程狀態(tài) 調(diào)度參數(shù) 現(xiàn)場信息 家族聯(lián)系 程序地址 當前打開文件 消息隊列指針 資源使用情況 進程隊列指針,進程,進程的組成 進程控制塊：由于進程控制塊中包含程序的地址信息，通過它可以找到程序在內(nèi)存或外存的存放地址，也就找到了整個進程. PCB存于系統(tǒng)空間，只有操作系統(tǒng)能夠?qū)ζ浯嫒?，用戶程序不能訪問. 實際上用戶甚至感覺不到PCB的存在； 程序：進程的“軀體”，其中包括代碼和數(shù)據(jù)兩個部分. 現(xiàn)代操作系統(tǒng)都支持程序共享的功能，這就要求代碼是“純”的，即在運行期

35、間不修改自身。數(shù)據(jù)一般包括靜態(tài)變量、動態(tài)堆和動態(tài)棧。,進程,進程的表示,PCB,程序,PCB,代碼,數(shù)據(jù) + 堆棧,系統(tǒng)空間,用戶空間,（a）,（b）,進程,進程的隊列 為實現(xiàn)對進程的管理，系統(tǒng)需要按照某種策略將進程排成若干隊列，由于PCB是進程的代表，因而進程隊列實際上是由進程PCB構(gòu)成的隊列. 因為該隊列通常由鏈的形式實現(xiàn)的，所以也稱PCB鏈 。系統(tǒng)中的進程隊列分為如下三類：就緒隊列 、等待隊列、運行隊列。,進程,進程的隊列 就緒隊列 整個系統(tǒng)一個. 所有處于就緒狀態(tài)的進程按照某種組織方式排在這一隊列中. 等待隊列 每個等待事件一個，當進程等待某一事件時，進入與該事件相關(guān)的等待隊列中；當某

36、事件發(fā)生時，與該事件相關(guān)的一個或多個進程離開相應(yīng)的等待隊列，進入就緒隊列. 運行隊列 在單CPU系統(tǒng)中只有一個，在多CPU系統(tǒng)中每個CPU各有一個，每個隊列中只有一個進程，指向運行隊列頭部的指針被稱作運行指示字.,進程,進程的類型 系統(tǒng)進程 運行操作系統(tǒng)程序，完成操作系統(tǒng)的某些功能； 用戶進程運行用戶程序，直接為用戶服務(wù)。 進程的特性 并發(fā)性：與其它進程一道在宏觀上同時向前推進 ； 動態(tài)性：進程是執(zhí)行中的程序. 此外進程的動態(tài)性還體現(xiàn)在如下兩個方面：首先，進程是動態(tài)產(chǎn)生、動態(tài)消亡的；其次，在進程的生存期內(nèi)，其狀態(tài)處于經(jīng)常性的動態(tài)變化之中 ； 獨立性：進程是調(diào)度的基本單位，它可以獲得處理機并參與

37、并發(fā)執(zhí)行 ； 交往性：進程在運行過程中可能會與其它進程發(fā)生直接或間接的相互作用 ； 異步性：每個進程都以其相對獨立、不可預知的速度向前推進 ； 結(jié)構(gòu)性：每個進程有一個控制塊PCB 。,進程,兩個特征 資源特征，包括程序執(zhí)行所必需的計算資源，例如程序代碼、內(nèi)存地址空間、文件系統(tǒng)、I/O設(shè)備、程序計數(shù)器、寄存器、棧空間等 執(zhí)行特征，包括在進程執(zhí)行過程中動態(tài)改變的特征，例如指令路徑（即進程執(zhí)行的指令序列）、進程的控制與執(zhí)行狀態(tài)等。,進程間通信,現(xiàn)代操作系統(tǒng)提供基本的系統(tǒng)調(diào)用函數(shù)，允許位于同一臺處理機或不同處理機的多個進程之間相互交流信息 三種表現(xiàn)形式： 通信：進程間的數(shù)據(jù)傳遞稱為進程間通信。 兩個進

38、程間傳遞的數(shù)據(jù)稱為消息；這種操作稱為消息傳遞 同步：同步是使位于相同或不同處理機中的多個進程之間相互等待的操作，它要求進程的所有操作均必須等待到達某個控制狀態(tài)之后才進行。 聚集（或規(guī)約）：聚集將位于相同或不同處理機中的多個進程的局部結(jié)果綜合起來，通過某種操作，產(chǎn)生一個新的結(jié)果，存儲在某個指定的或者所有的進程的變量中。 具體實現(xiàn)： 在共享存儲環(huán)境中，通過讀/寫操作系統(tǒng)通過的共享數(shù)據(jù)緩存區(qū)來實現(xiàn) 在分布式存儲網(wǎng)絡(luò)環(huán)境中，通過網(wǎng)絡(luò)通信來實現(xiàn),進程的創(chuàng)建與撤銷,進程創(chuàng)建 建立一個PCB，并對其內(nèi)容進行初始化； 為該進程分配必要的存儲空間，并加載所要執(zhí)行的程序(在UNIX系統(tǒng)中需要通過另外一個系統(tǒng)調(diào)用e

39、xecl實現(xiàn))； 將PCB送入就緒隊列。 進程撤銷 完成使命的進程需要終止自己并告知操作系統(tǒng)，系統(tǒng)將對進程進行善后處理(收集進程狀態(tài)信息、通知其父進程等)，之后將收回進程所占有的所有資源(打開文件、內(nèi)存等)，最后撤銷其PCB 。，非正常終止也將進入操作系統(tǒng)進行善后處理 。,線程的概念,進程不適合細粒度的共享存儲并行程序設(shè)計。 線程（thread）是進程上下文（context）中執(zhí)行的代碼序列，又被稱為輕量級進程（light weight process），是進程內(nèi)的一個相對獨立的執(zhí)行流。 進程可由單個線程來執(zhí)行，即通常所說的串行執(zhí)行；或者由多個線程來并行執(zhí)行，此時，多個線程將共享該進程的所有資

40、源特征，并可以使用不同的CPU，對不同的數(shù)據(jù)進行處理，從而達到提高進程執(zhí)行速度的目的。,線程的概念,在支持多線程的系統(tǒng)中： 進程成為資源分配和保護的實體 線程是被調(diào)度執(zhí)行的基本單元。 進程的資源 包括進程的地址空間，打開的文件和I/O等 屬于同一個進程的線程 共享該進程的代碼段和數(shù)據(jù)段，打開的文件，信號等 還包含各自的線程ID，線程執(zhí)行狀態(tài)，CPU寄存器狀態(tài)和棧,線程的概念,進程和線程的區(qū)別 進程是指程序在一個數(shù)據(jù)集合上運行的過程，是系統(tǒng)進行資源分配和調(diào)度運行的一個獨立單位，有時也稱為活動、路徑或任務(wù)。 操作系統(tǒng)中引入進程的目的，是為了使多個程序并發(fā)執(zhí)行，以改善資源利用率及提高系統(tǒng)的吞吐量。

41、操作系統(tǒng)中再引入線程則是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統(tǒng)具有更好的并發(fā)性。進程是資源的分配單位 。 線程是進程中的一個實體，是被系統(tǒng)調(diào)度和分配的基本單元。每個程序至少包含一個線程，那就是主線程。 線程自己只擁有很少的系統(tǒng)資源（如程序計數(shù)器、一組寄存器和棧），但它可與同屬一個進程的其他線程共享所屬進程所擁有的全部資源。 同一進程中的多個線程之間可以并發(fā)執(zhí)行，從而更好地改善了系統(tǒng)資源的利用率。 線程是CPU的調(diào)度單位 。,線程是“進程中的一條執(zhí)行路徑或線索”或“進程中的一個可調(diào)度實體”,線程的概念,單線程與多線程處理器模型,線程的概念,線程的概念,線程的優(yōu)點 上下文切換速度快：由

42、同一進程中的一個線程切換到另一個線程只需改變寄存器和棧，包括程序和數(shù)據(jù)在內(nèi)的地址空間不變； 系統(tǒng)開銷?。簞?chuàng)建線程比創(chuàng)建進程所需完成的工作少，因而對于客戶請求，服務(wù)器動態(tài)創(chuàng)建線程比動態(tài)創(chuàng)建進程具有更高的響應(yīng)速度； 通訊容易：由于同一進程中的多個線程地址空間共享，一個線程寫到數(shù)據(jù)空間的信息可以直接被該進程中的另一線程讀取，方便快捷 ； 終止一個線程比終止一個進程的代價要小。,線程的概念,調(diào)度 在傳統(tǒng)的操作系統(tǒng)中，CPU調(diào)度和分派的基本單位是進程。而在引入線程的操作系統(tǒng)中，則把線程作為CPU調(diào)度和分派的基本單位，進程則作為資源擁有的基本單位，從而使傳統(tǒng)進程的兩個屬性分開，線程便能輕裝運行，從而顯著地

43、提高系統(tǒng)的并發(fā)性。 同一進程中線程的切換不會引起進程切換，從而避免了昂貴的系統(tǒng)調(diào)用。但是在由一個進程中的線程切換到另一進程中的線程時，依然會引起進程切換。,線程的概念,并發(fā)性 在引入線程的操作系統(tǒng)中，不僅進程之間可以并發(fā)執(zhí)行，而且在一個進程中的多個線程之間也可以并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)的吞吐量。 例：在一個未引入線程的單CPU操作系統(tǒng)中，若僅設(shè)置一個文件服務(wù)進程，當它由于某種原因被封鎖時，便沒有其他的文件服務(wù)進程來提供服務(wù)。在引入了線程的操作系統(tǒng)中，可以在一個文件服務(wù)進程中設(shè)置多個服務(wù)線程。當?shù)谝粋€線程等待時，文件服務(wù)進程中的第二個線程可以

44、繼續(xù)運行；當?shù)诙€線程封鎖時，第三個線程可以繼續(xù)執(zhí)行，從而顯著地提高了文件服務(wù)的質(zhì)量以及系統(tǒng)的吞吐量。,線程的概念,系統(tǒng)開銷 不論是引入了線程的操作系統(tǒng)，還是傳統(tǒng)的操作系統(tǒng)，進程都是擁有系統(tǒng)資源的一個獨立單位，它可以擁有自己的資源。 一般地說，線程自己不擁有系統(tǒng)資源（也有一點必不可少的資源）， 但它可以訪問其隸屬進程的資源。亦即一個進程的代碼段、數(shù)據(jù)段以及系統(tǒng)資源（如已打開的文件、I/O設(shè)備等），可供同一進程的其他所有線程共享。,線程的概念,擁有資源 由于在創(chuàng)建或撤消進程時，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等。因此，操作系統(tǒng)所付出的開銷將顯著地大于在創(chuàng)建或撤消線程時的開銷。

45、在進行進程切換時，涉及到整個當前進程CPU環(huán)境的保存環(huán)境的設(shè)置以及新被調(diào)度運行的進程的CPU環(huán)境的設(shè)置。 線程切換只需保存和設(shè)置少量寄存器的內(nèi)容，并不涉及存儲器管理方面的操作。因此進程切換的開銷遠大于線程切換的開銷。 由于同一進程中的多個線程具有相同的地址空間，致使它們之間的同步和通信的實現(xiàn)也變得比較容易。,線程的概念,線程的結(jié)構(gòu),線程的概念,線程控制塊(Thread Control Block，TCB) ：線程控制塊是標志線程存在的數(shù)據(jù)結(jié)構(gòu)，其中包含系統(tǒng)對于線程進行管理所需要的全部信息,線程的實現(xiàn)方式 用戶級線程(User Level Thread) 在用戶層通過線程庫來實現(xiàn) 核心級線程(K

46、ernel Level Thread) 由操作系統(tǒng)直接支持 硬件線程(Hardware Thread)。 硬件線程就是線程在硬件執(zhí)行資源上的表現(xiàn)形式。,用戶級線程和內(nèi)核級線程,用戶級線程和內(nèi)核級線程,用戶級線程庫 是用于用戶級線程管理的例程包，支持線程的創(chuàng)建、終止，以及調(diào)度線程的執(zhí)行并保存和恢復線程的上下文，這些操作都在用戶空間進行，無需內(nèi)核的支持。 內(nèi)核級線程 所有管理操作都是由操作系統(tǒng)內(nèi)核完成的。內(nèi)核保存線程的狀態(tài)和上下文信息，當一個線程執(zhí)行了引起阻塞的系統(tǒng)調(diào)用時，內(nèi)核可以調(diào)度該進程的其他線程執(zhí)行。在多處理器系統(tǒng)上，內(nèi)核可以分派屬于同一進程的多個線程在多個處理器上運行，提高進程執(zhí)行的并行度

47、。 組合模式 有的操作系統(tǒng)提供了組合的線程模式，在Solaris中，用戶創(chuàng)建的多個用戶級線程被映射到一些內(nèi)核線程上，內(nèi)核線程的數(shù)目可能少于用戶級線程的數(shù)目。,用戶級線程,用戶級線程和內(nèi)核級線程,用戶級別線程優(yōu)點： 線程不依賴于操作系統(tǒng)，可以采用與問題相關(guān)的調(diào)度策略，靈活性好； 同一進程中的線程切換不需進入操作系統(tǒng)，因而實現(xiàn)效率較高； 有關(guān)線程的所有管理工作都由在用戶級實現(xiàn)的線程庫來支持。 用戶級別線程缺點： 同一進程中的多個線程不能真正并行； 由于線程對操作系統(tǒng)不可見，調(diào)度在進程級別，某進程中的一個線程通過系統(tǒng)調(diào)用進入操作系統(tǒng)受阻，該進程的其它線程也不能運行 。 用戶級別線程特征： 戶級線程的

48、創(chuàng)建和管理等操作無須內(nèi)核參與，操作更快 并行性不高，一個線程被系統(tǒng)阻塞后，整個進程被阻塞,用戶級線程和內(nèi)核級線程,核心級線程通過系統(tǒng)調(diào)用由操作系統(tǒng)創(chuàng)建，線程的控制結(jié)構(gòu)TCB保存于操作系統(tǒng)空間，線程狀態(tài)轉(zhuǎn)換由操作系統(tǒng)完成，線程是CPU調(diào)度的基本單位。,用戶級線程和內(nèi)核級線程,核心級別線程的優(yōu)點是并發(fā)性好，在多CPU環(huán)境中同一進程中的多個線程可以真正并行執(zhí)行 核心級別線程的缺點是線程控制和狀態(tài)轉(zhuǎn)換需要進入操作系統(tǒng)完成，系統(tǒng)開銷比較大. 特點 并行性高， 多個線程可被同時調(diào)度 充分利用多處理器 創(chuàng)建和管理代價高,用戶級線程和內(nèi)核級線程,多線程的映射模型,對于實現(xiàn)了用戶級線程和內(nèi)核級線程的操作系統(tǒng)，用

49、戶級線程和內(nèi)核級線程之間的可以有不同的映射方式。 多對一模型 一對一模型 多對多模型,多線程的映射模型,多對一模型 多對一模型把多個用戶級線程映射到一個內(nèi)核級線程。 線程的管理在用戶空間實現(xiàn)，所以效率高。 當一個線程因調(diào)用系統(tǒng)調(diào)用被阻塞時，整個進程被阻塞。 用戶級線程不能在多處理器上并發(fā)執(zhí)行，不支持內(nèi)核級線程的操作系統(tǒng)使用多對一模型。,一對一模型 一對一模型把每個用戶級線程影射到一個內(nèi)核級線程。 當一個線程阻塞時，其他線程仍然可以運行。 實例： Windows 95/98/NT/2000 OS/2,多線程的映射模型,多對多模型 多對多模型將m個用戶級線程影射到n個內(nèi)核級線程，mn。 用戶可以創(chuàng)

50、建所需要的用戶級線程，通過分配適當數(shù)目的內(nèi)核級線程獲得并發(fā)執(zhí)行的優(yōu)勢并節(jié)省系統(tǒng)資源。 Examples Solaris 2,多線程的映射模型,線程生命周期,線程的標識 通常用一個整數(shù)來標識一個線程 線程的創(chuàng)建 自動創(chuàng)建從main函數(shù)開始的主線程 調(diào)用函數(shù)庫接口創(chuàng)建一個新的線程（pthread_create） 線程的終止 執(zhí)行完畢，或者調(diào)用了pthread_exit 主線程退出導致整個進程會終止,線程狀態(tài)的轉(zhuǎn)換,線程的狀態(tài) 就緒（ready）：線程等待可用的處理器。 運行（running）：線程正在被執(zhí)行。 阻塞（blocked）：線程正在等待某個事件的發(fā)生（比如I/O的完成，試圖加鎖一個被上鎖

51、的互斥量）。 終止（terminated）：線程從起始函數(shù)中返回或者調(diào)用pthread_exit。,線程的應(yīng)用,許多任務(wù)在邏輯上涉及多個控制流，控制流具有內(nèi)在的并發(fā)性，當其中一些控制流被阻塞時，另外一些控制流仍可繼續(xù)。 在沒有線程支持的條件下，只能采用單進程或多進程模式，單進程不能表達多控制流，多進程開銷大而且在無共享存儲空間的條件下進程間交往困難。 采用多線程一方面可以提高應(yīng)用程序的并行性，另一方面也使程序設(shè)計簡潔明晰。 例如：Word文字編輯工具、Web服務(wù)器等。,多線程程序設(shè)計,為什么要多線程程序設(shè)計 某些應(yīng)用具有內(nèi)在的多個控制流結(jié)構(gòu)，這些控制流具有合作性質(zhì)，需要共享內(nèi)存，采用多線程易于

52、對問題建模，從而得到最自然的解決算法； 在需要多控制流的應(yīng)用中，多線程比多進程在速度上具有絕對優(yōu)勢，統(tǒng)計測試表明，線程的建立速度比進程的建立速度快100倍，進程內(nèi)線程間的切換速度與進程間切換速度也有數(shù)量級之差； 采用多線程可以提高處理機與設(shè)備之間的并行性. 在單控制流情形下，啟動設(shè)備的進程進入核心后將被阻塞，此時該進程的其它代碼也不能執(zhí)行. 若此時無其它可運行程序，處理機將被閑置. 多線程結(jié)構(gòu)在一個線程等待時，其它線程可以繼續(xù)執(zhí)行，從而使設(shè)備和處理機并行工作； 在多核環(huán)境下，多線程可以并行執(zhí)行，既可提高資源利用效率，又可提高進程推進速度。,多線程機制,多核處理器的基本結(jié)構(gòu)是共享存儲的，多線程程

53、序設(shè)計技術(shù)被認為是能夠充分挖掘共享存儲系統(tǒng)性能潛力的最有效的技術(shù)。 多線程機制的優(yōu)點： 創(chuàng)建一個線程比創(chuàng)建一個進程代價要小 ； 線程之間的切換比進程間的切換代價小 ； 充分利用多處理器 ； 數(shù)據(jù)共享 ； 快速響應(yīng)特性 ； 多線程編程可以使程序更加更加模塊化，簡化程序邏輯 。,多線程機制,在多處理器系統(tǒng)上，如果一個應(yīng)用具有如下特征，就可以利用多線程技術(shù)達到目標： 前臺后臺操作； 異步處理； 需要加速執(zhí)行； 模塊化程序結(jié)構(gòu)。,多線程環(huán)境下的進程控制語義,單線程環(huán)境下的進程控制接口在多線程環(huán)境下語義可能會發(fā)生變化，包括進程創(chuàng)建、進程終止、進程執(zhí)行、信號處理等操作。 進程創(chuàng)建 創(chuàng)建進程的系統(tǒng)調(diào)用完成后

54、，被創(chuàng)建的新進程復制調(diào)用進程的內(nèi)容，當進程的一個線程中創(chuàng)建一個子進程，新的進程可以復制整個進程（包括所有線程）也可以只復制調(diào)用線程的內(nèi)容； 執(zhí)行新的程序 在進程中執(zhí)行新的程序，函數(shù)的語義在多線程環(huán)境下沒有發(fā)生大的變化。Exec將會終止所有的線程，用新的程序覆蓋進程的地址空間，并開始執(zhí)行新的程序；,多線程環(huán)境下的進程控制語義,進程結(jié)束 在任何一個線程中調(diào)用exit將會結(jié)束整個進程，另外從主線程返回也等同于調(diào)用exit而導致進程結(jié)束。如果要從線程中退出則調(diào)用專用的線程退出函數(shù)。 信號處理 信號是unix中系統(tǒng)通知進程的重要機制。信號可能是同步的也可能是異步的。發(fā)送給進程的信號在多線程環(huán)境下有多種選

55、擇： 發(fā)送給引發(fā)信號的線程； 發(fā)送給所有的線程； 發(fā)送個特定的線程； 指定一個線程處理所有的信號。,多線程帶來的問題,由于線程共享同一進程的內(nèi)存空間，多個線程可能需要同時訪問同一個數(shù)據(jù)。 對共享數(shù)據(jù)的并發(fā)訪問可能導致數(shù)據(jù)的不一致性. 如果沒有正確的保護措施，對共享數(shù)據(jù)的訪問會造成數(shù)據(jù)的不一致和錯誤。 競爭條件 若干進程并發(fā)地訪問并且操縱共享數(shù)據(jù)的情況; 共享數(shù)據(jù)的值取決于哪個進程最后完成; 防止競爭條件，并發(fā)進程必須被同步.,線程的同步,例：如果一個進程有一個共享變量counter，兩個線程producer和consumer，線程producer執(zhí)行counter+，線程consumer執(zhí)行c

56、ounter-，這兩個操作都需要多個機器指令來完成，Counter=5 counter+ counter- register1=counter register2=counter register1=register1+1 register2=register2-1 counter=register1 counter= register2 可能的序列： Producer: register1=counter (register1=5) Producer: register1=register1+1 (register1=6) Consumer: register2=counter (regis

57、ter2=5) Consumer: register2= register2-1 (register2=6) Producer: counter= register1 (counter=6) Consumer: counter= register2 (counter=4),順序程序 程序的順序性包括內(nèi)部順序性和外部順序性。 內(nèi)部順序性：對于一個進程來說, 它的所有指令是按序執(zhí)行的； 外部順序性, 對于多個進程來說, 所有進程是依次執(zhí)行的。 P1活動: a1 a2 a3 a4，P2活動: b1 b2 b3 b4 順序執(zhí)行時, 有如下兩種情形: 情形1: a1 a2 a3 a4 b1 b2 b3

58、b4 情形2: b1 b2 b3 b4 a1 a2 a3 a4,線程的同步,順序程序的特性 順序性：處理機嚴格按照指令次序依次執(zhí)行，即僅當一條指令執(zhí)行完后才開始執(zhí)行下一條指令； 封閉性：程序在執(zhí)行過程中獨占系統(tǒng)中的全部資源，該程序的運行環(huán)境只與其自身動作有關(guān)，不受其它程序及外界因素影響； 可再現(xiàn)性：程序的執(zhí)行結(jié)果與執(zhí)行速度無關(guān)，而只與初始條件有關(guān)，給定相同的初始條件，程序的任意多次執(zhí)行一定得到相同的執(zhí)行結(jié)果.,線程的同步,并發(fā)程序 程序的并發(fā)性含義： 內(nèi)部并發(fā)性, 對于一個進程來說, 它的所有指令可能按序執(zhí)行，也可能不按次序執(zhí)行; 外部并發(fā)性: 對于多個進程來說, 所有進程是交叉(interl

59、eave)執(zhí)行的. 例如, 對于上面P1和P2兩個進程來說, 只考慮外部并發(fā)性，具有許多情形 ： 情形1: a1 b1 b2 a2 a3 b3 a4 b4 情形2: b1 b2 a1 a2 a3 b3 b4 a4 并發(fā)進程在其執(zhí)行過程中, 出現(xiàn)哪種交叉情形是不可預知的, 這就是并發(fā)程序帶來的不確定性,線程的同步,并發(fā)程序特性 交叉性：程序并發(fā)執(zhí)行對應(yīng)某一種交叉，不同的交叉可能導致不同的計算結(jié)果，操作系統(tǒng)應(yīng)當保證只產(chǎn)生導致正確結(jié)果的交叉，去除那些可能導致不正確結(jié)果的交叉； 非封閉性：一個進程的運行環(huán)境可能被其它進程所改變，從而相互影響； 不可再現(xiàn)性：由于交叉的隨機性，并發(fā)程序的多次執(zhí)行可能對應(yīng)不同的交叉，因而不能期望重新運行的程序能夠再現(xiàn)上次運行的結(jié)果,線程的同步,例：一個圖書館管理系統(tǒng), 連有兩個終端, 用戶可通過終端借書. 為簡化問題, 假設(shè)所有用戶借閱的圖書是相同的. 設(shè)x代表圖書的剩余數(shù)量, 為兩個終端用戶服務(wù)的程序,線程的同步,線程的同步,常用的同步機制 臨界區(qū)（critical section） 信號量（simphore） 互斥量（mutex） 管程（monitor） 鎖的粒度 死鎖,進程互斥,定義：兩個或兩個以上的進程，不能同時進入關(guān)