多核多線程技術

多核程序設計

參考資料：1.多核系列教材編寫組.多核程序設計.清華大學出版社,2007.92.DavidB.Kirk,Wen-meiW.Hwu著.陳曙暉,熊淑華譯.大規(guī)模并行處理器編程實踐.清華大學出版社,2010.93.MauriceHerlihy,NirShavit著.金海,胡侃譯.多處理器編程的藝術.機械工業(yè)出版社,2009.84.RichardGerber,AartJ.C.Bik,KevinB.Smith等著,王濤,單久龍,孫廣中譯.軟件優(yōu)化技術——IA-32平臺的高性能手冊(第2版)

.電子工業(yè)出版社,2007.4多核程序設計

電子書及資料下載：

/zh-cn/articles/32067多核程序設計

第一章多核技術導論微處理器發(fā)展史1945年，世界上第一臺全自動電子數(shù)字計算機ENIAC計算機的發(fā)展按照硬件工藝可以分為第一代（1946～1958）：電子管數(shù)字計算機。第二代（1958～1964）：晶體管數(shù)字計算機。第三代（1964～1971）：集成電路數(shù)字計算機。第四代(1971年以后）：大規(guī)模集成電路數(shù)字計算機。微處理器第一代微處理器(4位)：英特爾4004,8008第二代微處理器(8位)：采用NMOS工藝,采用匯編語言、BASIC、Fortran編程，使用單用戶操作系統(tǒng)。如英特爾8080,8085。第三代微處理器(16位)：以1978年英特爾的8086出現(xiàn)為起點。第四代微處理器(32位)：運算模式包括實模式、保護模式和“虛擬86”。英特爾80386DX,80486,Pentium4…微處理器發(fā)展史微處理器發(fā)展史微處理器發(fā)展史并行計算機由一組處理單元組成，這組處理單元通過相互之間的通信與協(xié)作，以更快的速度共同完成一項大規(guī)模的計算任務。出現(xiàn)背景:60年代初期，晶體管以及磁芯存儲器的出現(xiàn)，處理單元變得越來越小，存儲器也更加小巧和廉價。出現(xiàn)規(guī)模不大的共享存儲多處理器系統(tǒng)，即大型主機（典型代表：IBM360）。60年代末期，同一個處理器開始設置多個功能相同的功能單元，流水線技術也出現(xiàn)了，在處理器內(nèi)部的應用大大提高了并行計算機系統(tǒng)的性能。兩個最主要的組成部分計算節(jié)點節(jié)點間的通信與協(xié)作機制并行計算機的弗林分類Flynn根據(jù)指令流和數(shù)據(jù)流的不同組織方式，把計算機系統(tǒng)的結構分為以下四類：單指令流單數(shù)據(jù)流（SingleInstructionstreamSingleDatastream,SISD）單指令流多數(shù)據(jù)流（SingleInstructionstreamMultipleDatastream,SIMD）多指令流單數(shù)據(jù)流（MultipleInstructionstreamSingleDatastream,MISD）多指令流多數(shù)據(jù)流（MultipleInstructionstreamMultipleDatastream,MISD）并行計算機的弗林分類并行計算機系統(tǒng)絕大部分為MIMD系統(tǒng)，包括：并行向量機（PVP，ParallelVectorProcessor）；對稱多處理機（SMP,SymmetricMultiprocessor）；大規(guī)模并行處理機（MPP，MassivelyParallelProcessor）；機群（Cluster）；分布式共享存儲多處理機（DSM，DistributiedSharedMemory）并行計算機從系統(tǒng)結構角度分類分布式存儲器的SIMD處理機含有多個同樣結構的處理單元（PE），通過尋徑網(wǎng)絡以一定方式互相連接。每個PE有各自的本地存儲器（LM）。向量超級計算機（共享式存儲器SIMD）集中設置存儲器，共享的多個并行存儲器通過對準網(wǎng)絡與各處理單元PE相連。在處理單元數(shù)目不太大的情況下很理想。對稱多處理器（SMP）一個計算機上匯集了一組處理器，各處理器之間共享內(nèi)存子系統(tǒng)以及總線結構。并行向量處理機（PVP）使用定制的高帶寬網(wǎng)絡將向量處理器連向共享存儲器模塊使用大量的向量寄存器和指令緩沖器集群計算機由許多連在一起的獨立計算機組成，像一個單獨集成的計算機資源一樣協(xié)同工作，用來解決大型計算問題。并行計算機從系統(tǒng)結構角度分類對稱多處理共享存儲并行機（SMP）內(nèi)存模塊和處理器對稱地分布在互聯(lián)網(wǎng)絡的兩側，內(nèi)存訪問屬典型的均勻訪問模型。并行計算機從系統(tǒng)結構角度分類SMP主要特征對稱共享存儲系統(tǒng)中任何處理器均可直接訪問任何存儲模塊中的存儲單元和I/O模塊，且訪問的延遲、帶寬和訪問成功的概率是一致的。各個處理器之間的地位等價，操作系統(tǒng)可在任意處理器上運行。單一的操作系統(tǒng)映像全系統(tǒng)只有一個操作系統(tǒng)駐留在共享存儲器中，它根據(jù)各個處理器的負載情況，動態(tài)地分配各個進程到各個處理器，并保持各處理器間的負載平衡。局部高速緩存cache及其數(shù)據(jù)一致性每個處理器均配備局部cache，它們可以擁有獨立的局部數(shù)據(jù)，但是這些數(shù)據(jù)必須與存儲器中的數(shù)據(jù)保持一致。低通信延遲各個進程通過讀/寫操作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來完成處理器間的通信，其延遲通常小于網(wǎng)絡通信的延遲。共享總線帶寬所有處理器共享總線的帶寬，完成對內(nèi)存模塊和I/O模塊的訪問。支持消息傳遞、共享存儲并行程序設計并行計算機從系統(tǒng)結構角度分類SMP典型代表SGIPOWERChallengeXL系列并行機（可擴展至36個MIPSR10000微處理器）。COMPAQAlphaserver84005/440（含12個Alpha21264微處理器）。?HP9000/T600（含12個HPPA9000微處理器）。?IBMRS6000/R40（含8個RS6000微處理器）。并行計算機從系統(tǒng)結構角度分類分布共享存儲并行機（DSM）內(nèi)存模塊局部在各個結點內(nèi)部，并被所有結點共享。這樣，可以較好地改善對稱多處理共享存儲并行機的可擴展能力并行計算機從系統(tǒng)結構角度分類DSM主要特征

以結點為單位，每個結點包含一個或多個CPU，每個CPU擁有自己的局部cache，并共享局部存儲器和I/O設備，所有結點通過高性能互聯(lián)網(wǎng)絡相互連接；物理上分布存儲：內(nèi)存模塊分布在各結點中，并通過高性能互聯(lián)網(wǎng)絡相互連接。單一的內(nèi)存地址空間：所有這些內(nèi)存模塊都由硬件進行統(tǒng)一編址，并通過互聯(lián)網(wǎng)絡連接形成了并行機的共享存儲器。非一致內(nèi)存訪問（NUMA）模式：由于遠端訪問必須通過高性能互聯(lián)網(wǎng)絡，而本地訪問只需直接訪問局部內(nèi)存模塊，因此，遠端訪問的延遲一般是本地訪問延遲的3倍以上。單一的操作系統(tǒng)映像：用戶只看到一個操作系統(tǒng)，它可以根據(jù)各結點的負載情況，動態(tài)地分配進程。并行計算機從系統(tǒng)結構角度分類DSM主要特征

基于cache的數(shù)據(jù)一致性：通常采用基于目錄的cache一致性協(xié)議來保證各結點的局部cache數(shù)據(jù)與存儲器中數(shù)據(jù)的一致性。低通信延遲與高通信帶寬：專用的高性能互聯(lián)網(wǎng)絡使得結點間的延遲很小，通信帶寬可以擴展。DSM并行機可擴展到數(shù)百個結點，能提供每秒數(shù)千億次的浮點運算性能。支持消息傳遞、共享存儲并行程序設計。并行計算機從系統(tǒng)結構角度分類DSM典型代表

SGIOrigin–2000、SGIOrigin3800、SGIAltix并行計算機從系統(tǒng)結構角度分類大規(guī)模并行機系統(tǒng)（MPP）大規(guī)模并行機系統(tǒng)是典型的分布存儲系統(tǒng)。并行計算機從系統(tǒng)結構角度分類MPP典型特征

由數(shù)百個乃至數(shù)千個計算結點和I/O結點組成，每個結點相對獨立，并擁有一個或多個微處理器。這些結點配備有局部cache，并通過局部總線或互聯(lián)網(wǎng)絡與局部內(nèi)存模塊和I/O設備相連接。這些結點由局部高性能網(wǎng)卡(NIC)通過高性能互聯(lián)網(wǎng)絡相互連接。它一般采用由多種靜態(tài)拓撲結構耦合而成的混合拓撲結構，其通信延遲和通信帶寬均明顯優(yōu)于機群互聯(lián)網(wǎng)絡。MPP的各個結點均擁有不同的操作系統(tǒng)映像。一般情況下，用戶可以將作業(yè)提交給作業(yè)管理系統(tǒng)，由它負責調(diào)度當前最空閑、最有效的計算結點來執(zhí)行該作業(yè)。各個結點間的內(nèi)存模塊相互獨立，且不存在全局內(nèi)存單元的統(tǒng)一硬件編址。僅支持消息傳遞或者高性能Fortran并行程序設計，不支持全局共享的OpenMP并行程序設計模式。并行計算機從系統(tǒng)結構角度分類機群（cluster）有三個明顯的特征

系統(tǒng)由商用結點構成，每個結點包含2-4個商用微處理器，結點內(nèi)部共享存儲。采用商用機群交換機連接結點，結點間分布存儲。在各個結點上，采用機群Linux操作系統(tǒng)、GNU編譯系統(tǒng)和作業(yè)管理系統(tǒng)。片上多核處理器架構片上多核處理器（ChipMulti-Processor，CMP）就是將多個計算內(nèi)核集成在一個處理器芯片中，從而提高計算能力。按計算內(nèi)核的對等與否，CMP可分為同構多核和異構多核CPU核心數(shù)據(jù)共享與同步的通信機制：總線共享Cache結構：每個CPU內(nèi)核擁有共享的二級或三級Cache，用于保存比較常用的數(shù)據(jù)，并通過連接核心的總線進行通信。基于片上互連的結構：每個CPU核心具有獨立的處理單元和Cache，各個CPU核心通過交叉開關或片上網(wǎng)絡等方式連接在一起。給程序開發(fā)者帶來的挑戰(zhàn)典型多核芯片架構芯片組對多核的支持——固件固件是一種嵌入到硬件設備中的軟件。它通常燒寫在flash等介質(zhì)中，可以被當作一個二進制映像文件由用戶從硬件設備中調(diào)用。固件是在集成電路只讀存儲器中的計算機程序，是可擦寫可編程芯片，其上的程序可以通過專門的外部硬件進行修改，但是不能被一般的應用程序改動。芯片組對多核的支持——固件(續(xù))BIOS（BasicInput/OutputSystem）作為系統(tǒng)硬件和操作系統(tǒng)之間的抽象層，主要用來初始化和配置系統(tǒng)的硬件，啟動操作系統(tǒng)以及提供對系統(tǒng)設備底層的通訊。BIOS是連接CPU、芯片組和操作系統(tǒng)的固件，是IBM兼容計算機中啟動時調(diào)用的固件代碼。由兩部分組成:上電自舉即POST（PowerOnSelfTest）和在線的中斷服務（主要由legacy操作系統(tǒng)使用）。計算機加電時BIOS從flash、PROM或是EPROM中啟動并完成初始化，進行加電自檢，對硬盤，內(nèi)存，顯卡，主板等硬件進行掃描檢查，然后它將自己從BIOS內(nèi)存空間中解壓到系統(tǒng)的內(nèi)存空間中，并開始從那里運行。正在被以EFI（ExtensibleFirmwareInterface，可擴展固件接口）為代表的新一代技術所取代。芯片組對多核的支持——固件(續(xù)2)EFI（可擴展固件接口）在操作系統(tǒng)與平臺固件之間的軟件接口。EFI規(guī)范定義的接口包括包含平臺

信息的數(shù)據(jù)表和啟動時及啟動后的

服務。EFI啟動管理器被用來選擇裝載操

作系統(tǒng)，不再需要專門的啟動裝載

器機制輔助。Framework是一種固件的架構，

它是EFI固件接口的一種實現(xiàn)，用

來完全替代傳統(tǒng)的BIOS。EFI對多核支持在Framework中定義了兩類處理器BSP（bootstrapprocessor），執(zhí)行EFI的初始化代碼，設置APIC環(huán)境，建立系統(tǒng)范圍的數(shù)據(jù)結構，開始并初始化AP。AP（applicationprocessor），在系統(tǒng)上電或重啟之后，AP會自己進行一個簡單的設置，然后就等待BSP發(fā)出Startup信號。Framework在多核計算機中初始化過程如下：SEC：從實模式切換到保護模式，處理不同的重啟事件、對每個處理器進行緩存設置。PEI：做盡量少的硬件初始化，而把更多的留給DXE。DXE：對所有可用的硬件設備進行初始化，為建立控制臺和啟動操作系統(tǒng)提供必要的服務。BDS：建立所需的控制臺設備，在輸出控制臺上顯示用戶界面。當系統(tǒng)最后選擇啟動到操作系統(tǒng)時，EFI需要提交包括處理器在內(nèi)的有關信息。操作系統(tǒng)對多核處理器的支持方法調(diào)度與中斷對任務的分配進行優(yōu)化。使同一應用程序的任務盡量在一個核上執(zhí)行。對任務的共享數(shù)據(jù)優(yōu)化。由于CMP體系結構共享二級緩存，可以考慮改變?nèi)蝿赵趦?nèi)存中的數(shù)據(jù)分布，使任務在執(zhí)行時盡量增加二級緩存的命中率。對任務的負載均衡優(yōu)化。當任務在調(diào)度時，出現(xiàn)了負載不均衡，考慮將較忙處理器中與其他任務最不相關的任務遷移，以達到數(shù)據(jù)的沖突量小。輸入輸出系統(tǒng)多核體系處理器中，必須將中斷處理分發(fā)給一組核處理。存儲管理與文件系統(tǒng)庫函數(shù)做成非阻塞調(diào)用方式（需要保證數(shù)據(jù)同步的機制）使用多線程內(nèi)存分配操作系統(tǒng)對多核處理器的支持方法多核程序設計

第二章并行計算基礎并行和并發(fā)如果某個系統(tǒng)支持兩個或多個動作（Action）同時存在，那么這個系統(tǒng)就是一個并發(fā)系統(tǒng)如果某個系統(tǒng)支持兩個或多個動作同時執(zhí)行，那么這個系統(tǒng)就是一個并行系統(tǒng)并發(fā)程序可同時擁有兩個或多個線程。如果程序能夠并行執(zhí)行，則一定是運行在多核處理器上，每個線程都將分配到一個獨立的處理器核上?！安⑿小备拍钍恰安l(fā)”概念的一個子集什么是并行計算并行計算（parallelcomputing）是指，在并行機上將一個應用分解成多個子任務，分配給不同的處理器，各個處理器之間相互協(xié)同，并行地執(zhí)行子任務，從而達到加速求解速度，或者求解應用問題規(guī)模的目的。成功開展并行計算，必須具備三個基本條件：并行機并行機至少包含兩臺或兩臺以上處理機，這些處理機通過互連網(wǎng)絡相互連接，相互通信。應用問題必須具有并行度也就是說，應用可以分解為多個子任務，這些子任務可以并行地執(zhí)行。將一個應用分解為多個子任務的過程，稱為并行算法的設計。并行編程在并行機提供的并行編程環(huán)境上，具體實現(xiàn)并行算法，編制并行程序，并運行該程序，從而達到并行求解應用問題的目的。并行計算的目的、目標并行計算技術的主要目的：加速求解問題的速度例如，給定某應用，在單處理器上，串行執(zhí)行需要2周，這個速度對一般的應用而言，是無法忍受的。于是，可以借助并行計算，使用100臺處理器，加速50倍，將執(zhí)行時間縮短為6.72個小時。提高求解問題的規(guī)模例如，在單處理器上，受內(nèi)存資源2GB的限制，只能計算10萬個網(wǎng)格，但是，當前數(shù)值模擬要求計算千萬個網(wǎng)格。于是，也可以借助并行計算，使用100個處理器，將問題求解規(guī)模線性地擴大100倍。并行計算的主要目標：在并行機上，解決具有重大挑戰(zhàn)性計算任務的科學、工程及商業(yè)計算問題，滿足不斷增長的應用問題對速度和內(nèi)存資源的需求。并行計算的研究內(nèi)容并行計算的主要研究內(nèi)容大致可分為四個方面：并行機的高性能特征抽取充分理解和抽取當前并行機體系結構的高性能特征，提出實用的并行計算模型和并行性能評價方法，指導并行算法的設計和并行程序的實現(xiàn)。并行算法設計與分析設計高效率的并行算法，將應用問題分解為可并行計算的多個子任務，并具體分析這些算法的可行性和效果。并行實現(xiàn)技術主要包含并行程序設計和并行性能優(yōu)化。并行應用這是并行計算研究的最終目的。通過驗證和確認并行程序的正確性和效率，進一步將程序發(fā)展為并行應用軟件，應用于求解實際問題。同時，結合實際應用出現(xiàn)的各種問題，不斷地改進并行算法和并行程序。并行計算示例N個數(shù)被分布存儲在P臺處理器，P臺處理器并行執(zhí)行N個數(shù)的累加和。首先，各個處理器累加它們各自擁有的局部數(shù)據(jù)，得到部分和；然后，P臺處理器執(zhí)行全局通信操作，累加所有部分和，得到全局累加和。并行計算機體系結構組成并行計算機的各個部分：節(jié)點（node）構成并行機的基本單位互聯(lián)網(wǎng)絡（interconnectnetwork）內(nèi)存（memory）內(nèi)存模塊與節(jié)點分離內(nèi)存模塊位于節(jié)點內(nèi)部多級存儲體系結構為了解決內(nèi)存墻（memorywall）性能瓶頸問題。在節(jié)點內(nèi)部的cache稱為二級cache（L2cache）。在處理器內(nèi)部更小的cache稱為一級cache（L1cache）。L1cache連接CPU寄存器和L2cache，負責緩存L2cache中的數(shù)據(jù)到寄存器中。多級存儲體系結構并行計算機的多級存儲結構主要包括兩個問題：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之間的移動以cache線為基本單位。Fori=1toMA[i]=A[i]+2*B[i]如果操作數(shù)存在cache中，稱該次訪問是命中的，否則，該次操作是“撲空”的。無Cache，訪問內(nèi)存2M次；有cache，訪問內(nèi)存2M/L次多級存儲體系結構cache的映射策略指的是內(nèi)存塊和cache線之間如何建立相互映射關系。直接映射策略（directmappingstrategy）每個內(nèi)存塊只能被唯一的映射到一條cache線中K－路組關聯(lián)映射策略（K-waysetassociationmappingstrategy）Cache被分解為V個組，每個組由K條cache線組成，內(nèi)存塊按直接映射策略映射到某個組，但在該組中，內(nèi)存塊可以被映射到任意一條cache線。全關聯(lián)映射策略（fullassociationmappingstrategy）內(nèi)存塊可以被映射到cache中的任意一條cache線。并行計算機訪存模型UMA（UniformMemoryAccess）均勻存儲訪問模型物理存儲器被所有節(jié)點共享；所有節(jié)點訪問任意存儲單元的時間相同；發(fā)生訪存競爭時，仲裁策略平等對待每個節(jié)點，即每個節(jié)點機會均等；各節(jié)點的CPU可帶有局部私有高速緩存；外圍I/O設備也可以共享，且每個節(jié)點有平等的訪問權利。NUMA（Non-UniformMemoryAccess）模型物理存儲器被所有節(jié)點共享，任意節(jié)點可以直接訪問任意內(nèi)存模塊；節(jié)點訪問內(nèi)存模塊的速度不同，訪問本地存儲模塊的速度一般是訪問其他節(jié)點內(nèi)存模塊的3倍以上；發(fā)生訪存競爭時，仲裁策略對節(jié)點可能是不等價的；各節(jié)點的CPU可帶有局部私有高速緩存（cache）；外圍I/O設備也可以共享，但對各節(jié)點是不等價的。并行計算機訪存模型COMA（Cache-OnlyMemoryAccess）模型各處理器節(jié)點中沒有存儲層次結構，全部高速緩存組成了全局地址空間利用分布的高速緩存目錄D進行遠程高速緩存的訪問COMA中的高速緩存容量一般都大于2級高速緩存容量使用COMA時，數(shù)據(jù)開始時可以任意分配，因為在運行時它最終會被遷移到要用到它的地方NORMA（No-RemoteMemoryAccess）模型所有存儲器都是私有的；絕大多數(shù)NORMA都不支持遠程存儲器的訪問；在DSM（分布式共享存儲）中，NORMA就消失了。并行計算機訪存模型并行計算機系統(tǒng)的不同訪存模型分類并行計算模型計算模型是對計算機的抽象計算模型為設計、分析和評價算法提供基礎馮·偌依曼機就是一個理想的串行計算模型但現(xiàn)在還沒有一個通用的并行計算模型并行計算模型SIMD同步并行計算模型共享存儲的SIMD模型（PRAM模型）PRAM，ParallelRandomAccessMachine并行隨機存取模型分布存儲的SIMD模型（SIMD互聯(lián)網(wǎng)絡模型）MIMD異步并行計算模型異步PRAM模型BSP模型LogP模型C3模型SIMD同步并行計算模型SIMD共享存儲模型（PRAM模型）是一種抽象的并行計算模型，模型中：假定存在著一個容量無限大的共享存儲器；有有限或無限各功能相同的處理器，且均具有簡單的算術運算和邏輯判斷功能；在任何時刻各處理器均可以通過共享存儲單元交換數(shù)據(jù)。SIMD同步并行計算模型SIMD共享存儲模型（PRAM模型）根據(jù)處理器對共享存儲單元同時讀寫的限制，模型分為：PRAM-EREW（Exclusive-ReadandExclusive-Write），不允許同時讀和同時寫PRAM-CREW（Concurrent-ReadandExclusive-Write），允許同時讀但不允許同時寫PRAM-CRCW（Concurrent-ReadandConcurrent-Write），允許同時讀和同時寫SIMD同步并行計算模型SIMD共享存儲模型（PRAM模型）優(yōu)點：適合于并行算法的表達、分析和比較；使用簡單，很多諸如處理器間通信、存儲管理和進程同步等并行計算機的低級細節(jié)均隱含于模型中；易于設計算法和稍加修改便可運行在不同的并行計算機上；有可能加入一些諸如同步和通信等需要考慮的方面。SIMD同步并行計算模型SIMD共享存儲模型（PRAM模型）控制單元P1LMP2LMPnLM互連網(wǎng)絡全局共享存儲器SIMD-PRAM模型MIMD同步并行計算模型MIMD-PRAM模型控制器1P1LMP2LMPnLM互連網(wǎng)絡全局共享存儲器控制器2控制器nMIMD異步計算模型——APRAM模型APRAM模型特點:每個處理器都有其本地存儲器、局部時鐘和局部程序處理器間的通信經(jīng)過共享全局存儲器無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令處理器任何時間依賴關系需明確地在各處理器的程序中加入同步（路）障（SynchronizationBarrier）一條指令可在非確定但有限的時間內(nèi)完成。APRAM模型中有四類指令:全局讀，將全局存儲單元中的內(nèi)容讀入本地存儲器單元中局部操作，對本地存儲器中的數(shù)執(zhí)行操作，其結果存入本地存儲器中全局寫，將本地存儲器單元中的內(nèi)容寫入全本地存儲器單元中同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達后才能繼續(xù)執(zhí)行其局部程序MIMD異步計算模型——BSP模型大同步并行BSP(BulkSynchronousParallel)模型作為計算機語言和體系結構之間的橋梁，由以下述三個參數(shù)描述分布存儲的并行計算機模型：處理器/存儲器模塊（下文簡稱處理器）處理器模塊之間點到點信息傳遞的路由器執(zhí)行以時間間隔L為周期的路障同步器特點：將處理器和路由器分開，強調(diào)了計算任務和通信任務的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡拓撲，又簡化了通信協(xié)議采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔在分析BSP模型的性能時，假定局部操作可在一個時間步內(nèi)完成，而在每一超級步中，一個處理器至多發(fā)送或接受h條消息（h-relation）MIMD異步計算模型——LogP模型LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信網(wǎng)絡由一組參數(shù)來描述，但它并不涉及到具體的網(wǎng)絡結構，也不假定算法一定要用顯式的消息傳遞操作進行描述。L（Latency）源處理機與目的處理機進行消息（一個或幾個字）通信所需要的等待或延遲時間的上限。o（overhead）處理機準備發(fā)送或準備接受每個消息的時間開銷（包括操作系統(tǒng)核心開銷和網(wǎng)絡軟件開銷），在這段時間里處理機不能執(zhí)行其他操作。g（gap）一臺處理機連續(xù)兩次發(fā)送或連續(xù)兩次接受消息時的最小時間間隔，其倒數(shù)即為處理機的通信帶寬。P（Processor）處理機的個數(shù)。MIMD異步計算模型——LogP模型揭示了分布存儲并行計算機的性能瓶頸，用L、o、g三個參數(shù)刻畫了通信網(wǎng)絡的特性，但屏蔽了網(wǎng)絡拓撲、選路算法和通信協(xié)議等具體細節(jié)參數(shù)g反映了通信帶寬在任何時刻，最多只能有[L/g]條消息從一個處理器傳到另一個處理器，這就是網(wǎng)絡容限，當一臺處理機發(fā)送的消息達到這個容限時，在發(fā)送的消息就會被阻塞；在網(wǎng)絡容限范圍內(nèi)，點到點傳送一條消息的時間為(2*o+L)。設想LogP模型中的L、o、g都為0，那么LogP模型就等同于PRAM模型MIMD異步計算模型——C3模型C3（Computation,Communication,Congestion）模型是一個與體系結構無關的粗粒度的并行計算模型，旨在能反映計算復雜度，通信模式和通信期間潛在的擁擠等因素對粗粒度網(wǎng)絡算法的影響。C3模型強調(diào)用共用的通信操作來開發(fā)粗粒度的并行算法BSP、LogP模型采用點到點的消息傳遞來進行通信，復雜的通信操作由編程實現(xiàn)各種計算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結構SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計算模式同步異步異步異步異步同步方式自動同步路障同步路障同步隱式同步路障同步模型參數(shù)單位時間步d,讀/寫時間B,同步時間p,處理器數(shù)g,帶寬因子l,同步間隔L,通信延遲o,額外開銷g,帶寬因子P,處理器數(shù)l,信包長度s,發(fā)送建立時間h,通信延遲計算粒度細粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫共享變量讀/寫共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間并行編程方法編寫正確的串行程序分析：找出并發(fā)性找出包含獨立計算的熱點（Hotspot）位置。熱點是指一段包含了大量操作的代碼設計與實現(xiàn)：采用線程來實現(xiàn)算法并行算法是適合在并行機上實現(xiàn)的算法測試正確性：檢測并修復在線程化時引入的錯誤性能調(diào)優(yōu)：消除性能瓶頸并行算法分類并行算法根據(jù)運算基本對象的不同可分為：數(shù)值并行算法主要為數(shù)值計算方法而設計的并行算法；非數(shù)值并行算法主要為符號運算而設計的并行算法，如圖論算法、遺傳算法等。并行算法分類根據(jù)并行進程間相互執(zhí)行順序關系的不同可分為：同步并行算法進程間由于運算執(zhí)行順序而必須相互等待的并行算法，如通常的向量算法、SIMD算法、MIMD并行機上進程間需要相互等待通信結果的算法等；異步并行算法進程間執(zhí)行相對獨立，不需要相互等待的一種算法，通常針對消息傳遞MIMD并行機設計，其主要特征是在計算的整個過程中均不需要等待，而是根據(jù)最新消息決定進程的繼續(xù)或終止；獨立并行算法進程間執(zhí)行是完全獨立的，計算的整個過程不需要任何通信。并行算法分類根據(jù)各進程承擔的計算任務粒度的不同，可分為：細粒度并行算法通常指基于向量和循環(huán)級并行的算法；中粒度并行算法通常指基于較大的循環(huán)級并行；大粒度并行算法通常指基于子任務級并行的算法，例如通常的基于區(qū)域分解的并行算法，它們是當前并行算法設計的主流。并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲和數(shù)據(jù)并行：共享存儲并行編程基于線程級細粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持數(shù)據(jù)的共享存儲，所以并行編程的難度較小，但一般情況下，當處理機個數(shù)較多時，其并行性能明顯不如消息傳遞編程；消息傳遞并行編程基于大粒度的進程級并行，具有最好的可擴展性，幾乎被所有當前流行的各類并行計算機所支持，其具有較好的可擴展性。消息傳遞并行編程只能支持進程間的分布式存儲模式，即各個進程只能支持訪問其局部內(nèi)存空間，而對其他進程的局部內(nèi)存空間的訪問只能通過消息傳遞來實現(xiàn)，因此，學習和使用消息傳遞并行編程的難度均大于共享存儲和數(shù)據(jù)并行這兩種編程模式。

并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲和數(shù)據(jù)并行特征消息傳遞共享存儲數(shù)據(jù)并行典型代表MPI,PVMOpenMPHPF可移植性所有主流并行計算機SMP,DSMSMP,DSM,MPP并行粒度進程級大粒度線程級細粒度進程級細粒度并行操作方式異步異步松散同步數(shù)據(jù)存儲模式分布式存儲共享存儲共享存儲數(shù)據(jù)分配方式顯式隱式半隱式學習入門難度較難容易偏易可擴展性好較差一般編程語言與編譯器在科學計算領域?qū)Σ⑿芯幊讨С忠呀?jīng)取得相當成功的三項技術：自動并行化數(shù)據(jù)并行語言HPF共享存儲并行編程接口OpenMP編程語言與編譯器自動并行始于20世紀70年代的自動向量化。20世紀80年代中期，基于依賴分析的向量化工具成熟，成為向量機的標準。自動化并行本身不足以解決并行程序設計問題。此領域的研究重點逐步轉(zhuǎn)向基于語言的策略研究，即從用戶那里獲得更多的信息，同時利用自動并行化技術來減輕程序設計的負擔。依賴分析：搜索確定對同一數(shù)據(jù)結構的哪些引用是訪問同一存儲單元的編程語言與編譯器數(shù)據(jù)并行編程：HPF高性能Fortran(HPF)的思想是使數(shù)據(jù)管理的多數(shù)細節(jié)自動并行化HPF提供了一個指令集，通過注釋形式的指令來擴展變量類型的說明，能夠?qū)?shù)組的數(shù)據(jù)布局進行相當詳細的控制。對顯式并行機制的說明相當有限，通過系統(tǒng)而非程序員把任務分配給處理機。編程語言與編譯器共享存儲并行編程：OpenMP1997年由SiliconGraphics領導的工業(yè)協(xié)會推出了OpenMP是一個與Fortran77和C語言綁定的并行編程接口OpenMP指令在單機編譯器上被當作注釋而忽略通過parallelsection指令獲得任務并行#pragmaompparallelfor…提供了鎖變量用于線程間細粒度同步是適合于具有一致性訪存的共享存儲計算機的編程接口并行計算性能評測并行程序執(zhí)行時間從并行程序開始執(zhí)行到所有進程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間（wallclocktime）。并行計算性能評測并行程序執(zhí)行時間對各個進程，墻上時間可進一步分解為計算CPU時間、通信CPU時間、同步開銷時間、同步導致的進程空閑時間計算CPU時間：進程指令執(zhí)行所花費的CPU時間，包括程序本身的指令執(zhí)行占用的時間（用戶時間）和系統(tǒng)指令花費的時間；通信CPU時間：進程通信花費的CPU時間；同步開銷時間：進程同步花費的時間；進程空閑時間：進程空閑時間是指并行程序執(zhí)行過程中，進程所有空閑時間總和（如進程阻塞式等待其他進程的消息時。此時CPU通常是空閑的，或者處于等待狀態(tài)）并行計算性能評測并行程序性能評價方法浮點峰值性能與實際浮點性能峰值性能等于CPU內(nèi)部浮點乘加指令流水線條數(shù)、每條流水線每個時鐘周期完成的浮點運算次數(shù)、處理器主頻三者的乘積實際浮點性能等于并行程序的總的浮點運算次數(shù)和并行程序執(zhí)行時間的比值數(shù)值效率和并行效率并行計算性能評測并行加速比與效率在處理器資源獨享的前提下，假設某個串行應用程序在某臺并行機單處理器上的執(zhí)行時間為TS，而該程序并行化后，P個進程在P個處理器并行執(zhí)行所需要的時間為TP

，則該并行程序在該并行機上的加速比SP

可定義為：效率定義為：并行計算性能評測加速比性能定律——Amdahl定律能夠計算并行程序相對于最優(yōu)串行算法在性能提升上的理論最大值——他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個關于程序中這兩部分所占比例以及可加速部分性能加速程度的函數(shù)Amdahl定律:f表示執(zhí)行程序中串行部分的比例，p表示處理器核的數(shù)量。假設最優(yōu)串行算法的執(zhí)行時間為一個單位時間（也就是分子為1）。處理器核在數(shù)量上能夠無限制的增加，但是無限的處理器核卻并不能帶來性能上的無限增長，無論如何，程序性能上的總是有個上限，這個要受限于串行部分所占的比例。

并行計算性能評測Amdahl定律告訴我們：可并行計算量占主要比重通過并行化，增加的額外計算量所占比重有限：這些計算量由各個處理器/執(zhí)行內(nèi)核分攤要有足夠的并行度(并行子任務數(shù)量)，實現(xiàn)負載均衡：問題規(guī)模越大，并行度也越大數(shù)據(jù)并行大規(guī)模數(shù)據(jù)處理數(shù)據(jù)規(guī)模與處理器/執(zhí)行內(nèi)核的規(guī)模比率要適當只有上述三個特征都滿足了，采用并行處理技術才有意義程序性能優(yōu)化串行程序性能優(yōu)化

是并行程序性能優(yōu)化的基礎，一個好的并行程序首先應該擁有良好的單機性能，影響程序單機性能的主要因素是程序的計算流程和處理器的體系結構。程序性能優(yōu)化串行程序性能優(yōu)化調(diào)用高性能庫許多著名的高性能數(shù)學程序庫如優(yōu)化的BLAS、FFTW等，由于經(jīng)過廠商或第三方針對特定處理機進行的專門優(yōu)化，其性能一般大大優(yōu)于用戶自行編寫的同樣功能的程序段或子程序。程序性能優(yōu)化串行程序性能優(yōu)化調(diào)用高性能庫

BLAS(BasicLinearAlgebraSubroutines)是一組高質(zhì)量的基本向量、矩陣運算子程序。最早的BLAS是一組Fortran函數(shù)和子程序，后來又發(fā)展了其他語言接口，包括C、Java等。BLAS的官方網(wǎng)址在/blas/國內(nèi)鏡像為/blas/。BLAS的主要貢獻是將高性能代數(shù)計算程序的開發(fā)同針對特定機器的性能優(yōu)化獨立開來：代數(shù)算法程序的開發(fā)者只需要運用適當?shù)姆謮K技術將計算過程變成矩陣、向量的基本運算并調(diào)用相應的BLAS子程序而不必考慮與計算機體系結構相關的性能優(yōu)化問題。線性代數(shù)軟件包如LAPACK、ScaLAPACK等都是基于這一思想設計的。程序性能優(yōu)化串行程序性能優(yōu)化調(diào)用高性能庫

FFTW(TheFastestFourierTransformintheWest)是一個免費的快速富氏變換(FFT)軟件包，開發(fā)者是麻省理工學院的MatteoFrigo和StevenG.Johnson，下載網(wǎng)址：

該軟件包用C語言開發(fā)，其核心技術(編碼生成器)采用面向?qū)ο笳Z言Caml編寫。FFTW能自動適應系統(tǒng)硬件，可移植性很強。它能計算一維和多維離散傅立葉變換，其數(shù)據(jù)類型可以是實型、復型或半復型。該軟件通過方案(plan)和執(zhí)行器(executor)與用戶進行接口，內(nèi)部結構及其復雜性對用戶透明，速度快。內(nèi)部編譯器、代碼生成器利用AST（AbstractSyntaxTree）在運行時生成適合所運行的機器的代碼并自我優(yōu)化。程序性能優(yōu)化串行程序性能優(yōu)化選擇適當?shù)木幾g器優(yōu)化選項現(xiàn)代編譯器在編譯時能夠?qū)Τ绦蜻M行優(yōu)化從而提高所生成的目標代碼的性能。這些優(yōu)化功能通常通過一組編譯選項來控制。比較通用的優(yōu)化選項有“-O”、“-O0”、“-O2”、“-O3”等，“-O0”表示不做優(yōu)化，“-O1”、“-O2”、“-O3”等表示不同級別的優(yōu)化，優(yōu)化級別越高，生成的代碼的性能可能會越好，但采用過高級別的優(yōu)化會大大降低編譯速度，并且可能導致錯誤的運行結果。通常，“-O2”的優(yōu)化被認為安全的。程序性能優(yōu)化串行程序性能優(yōu)化合理定義數(shù)組維數(shù)在進行連續(xù)數(shù)據(jù)訪問時應該使得地址的增量與內(nèi)存體數(shù)的最大公約數(shù)盡量小，特別要避免地址增量正好是體數(shù)的倍數(shù)。注意嵌套循環(huán)的順序，盡量改善數(shù)據(jù)訪問的局部性通用的原則就是盡量使最內(nèi)層循環(huán)的數(shù)據(jù)訪問連續(xù)進行程序性能優(yōu)化串行程序性能優(yōu)化數(shù)據(jù)分塊當處理大數(shù)組時，對數(shù)組、循環(huán)進行適當分塊有助于同時改善訪存的時間和空間局部性。DOI=1,NDOJ=1,NA(I)=A(I)+B(J)ENDDOENDDO對數(shù)組B進行分塊，S為分塊大小，改寫上述程序：DOJ=1,N,SDOI=1,NDOJJ=J,MIN(J+S-1,N)A(I)=A(I)+B(JJ)ENDDOENDDOENDDO當S≥N時，相當于原始循環(huán)；當S=1時相當于交換I和J的循環(huán)順序。根據(jù)cache大小選擇適當?shù)腟值，使得B(J:J+S-1)能夠被容納在cache中，可以改善對數(shù)組B的訪問的時間局部性。程序性能優(yōu)化串行程序性能優(yōu)化循環(huán)展開是另一個非常有效的程序優(yōu)化技術。它除了能夠改善數(shù)據(jù)訪問的時間和空間局部性外，還由于增加了每步循環(huán)中的指令與運算的數(shù)目，亦有助于CPU多個運算部件的充分利用。DOI=1,ND=D+A(I)ENDDO將它進行4步循環(huán)展開的代碼如下：DOI=1,MOD(N,4)D=D+A(I)ENDDODOI=MOD(N,4)+1,N,4D=D+A(I)+A(I+1)+A(I+2)+A(I+3)ENDDO上面的代碼中第一個循環(huán)用于處理N除以4的余數(shù)，第二個循環(huán)是展開后的循環(huán)。程序性能優(yōu)化串行程序：求小于N的全部素數(shù)voidmain(){intnumber;//小于N的素數(shù)個數(shù)； intprimes[n];//從primes[0]–primes[number-1]中存放生成的素數(shù)； inti,j,k; primes[0]=2; for(i=3,j=1;i<n;i++){//從整數(shù)3開始檢查i是否為素數(shù) for(k=0;primes[k]*primes[k]<i;k++)//依次檢查i是否可以被前面的素數(shù)整除 if(i%primes[k]==0)break; if(primes[k]*primes[k]>i){//如果i不能被前面的素數(shù)整除//則將它作為新素數(shù)存入數(shù)組

primes[j]=i; j++; } }}程序性能優(yōu)化并行程序性能優(yōu)化最主要的是選擇好的并行算法和通信模式減少通信量、提高通信粒度提高通信粒度的有效方法就是減少通信次數(shù)，盡可能將可以一次傳遞的數(shù)據(jù)合并起來一起傳遞全局通信盡量利用高效集合通信算法對于標準的集合通信，如廣播、規(guī)約、數(shù)據(jù)散發(fā)與收集等，盡量調(diào)用MPI標準庫函數(shù)挖掘算法的并行度，減少CPU空閑等待具有數(shù)據(jù)相關性的計算過程會導致并行運行的部分進程空閑等待.在這種情況下，可以考慮改變算法來消除數(shù)據(jù)相關性程序性能優(yōu)化并行程序性能優(yōu)化負載平衡必要時使用動態(tài)負載平衡技術，即根據(jù)各進程計算完成的情況動態(tài)地分配或調(diào)整各進程的計算任務。動態(tài)調(diào)整負載時要考慮負載調(diào)整的開銷及由于負載不平衡而引起的空閑等待對性能的影響，尋找最優(yōu)負載調(diào)整方案。通信、計算的重疊讓通信和計算重疊進行，利用計算時間來屏蔽通信時間。實現(xiàn)方法一般基于非阻塞通信，先發(fā)出非阻塞的消息接受或發(fā)送命令，然后處理與收發(fā)數(shù)據(jù)無關的計算任務，完成計算后再等待消息收發(fā)的完成。通過引入重復計算來減少通信，即以計算換通信由于當前大部分并行計算機的計算速度遠遠大于通信速度，并且在一些情況下，當一個進程計算時，別的進程往往處于空閑等待狀態(tài)，因而適當引入重復計算可以提高程序的總體性能。程序性能優(yōu)化并行程序：求小于N的全部素數(shù)pThread_prime并行編譯器并行編譯器大致由三部分組成：流分析確定源代碼中數(shù)據(jù)和控制的相關性程序優(yōu)化將代碼變換成與之等效的的更好形式，以挖掘硬件潛力代碼生成將代碼從一種描述轉(zhuǎn)換成另一種中間形式的描述并行編譯器并行編譯過程并行編譯器流分析要使程序并行地執(zhí)行，首先要進行相關性分析（DependencyAnalysis）四種相關形式：流相關：從Si～Sj存在執(zhí)行通路，且Si至少有一個輸出被用作Sj的輸入反相關：Sj緊接Si，且Sj的輸出被作為Si的輸入輸出相關：兩條語句往相同的變量里寫控制相關：語句Sj的執(zhí)行與否依賴于語句Si并行編譯器代碼優(yōu)化代碼向量化（CodeVectorization）:把標量程序中的由一種可向量化循環(huán)完成的操作變換成向量操作。代碼并行化（CodeParallelization）:并行代碼的優(yōu)化是將一個程序展開成多線程以同時供多臺處理機并行執(zhí)行，其目的是要減少總的執(zhí)行時間。代碼生成并行代碼生成（CodeGeneration）涉及到將優(yōu)化后的中間形式的代碼轉(zhuǎn)換程可執(zhí)行的具體的機器目標代碼。包括執(zhí)行次序、指令選擇、寄存器分配、負載平衡、并行粒度、代碼調(diào)度以及后優(yōu)化（Postoptimization）等問題。多核程序設計

第三章多線程編程方法綜述進程定義：進程是具有一定獨立功能的程序關于一個數(shù)據(jù)集合的一次運行活動。可表示成四元組（P,C,D,S），其中P是程序代碼，C是進程的控制狀態(tài)，D是進程的數(shù)據(jù)，S是進程的執(zhí)行狀態(tài)。狀態(tài)：運行態(tài)(Run):進程占有處理機資源,正在運行;就緒態(tài)(Ready):進程本身具備運行條件,但由于處理機的個數(shù)少于可運行進程的個數(shù),暫未投入運行;等待態(tài)(Wait):

進程本身不具備運行條件，即使分給它處理機也不能運行.進程正等待某一個事件的發(fā)生,如等待某一資源被釋放，等待與該進程相關的I/O傳輸?shù)耐瓿尚盘柕?。進程狀態(tài)間轉(zhuǎn)換當一個就緒進程獲得處理機時,其狀態(tài)由就緒變?yōu)檫\行；當一個運行進程被剝奪處理機時,其狀態(tài)由運行變?yōu)榫途w；當一個運行進程因某事件受阻時,如所申請資源被占用,啟動I/O傳輸未完成,其狀態(tài)由運行變?yōu)榈却划斔却录l(fā)生時,如得到申請資源,I/O傳輸完成,其狀態(tài)由等待變?yōu)榫途w。進程進程控制塊(ProcessControlBlock，PCB):標志進程存在的數(shù)據(jù)結構，其中包含系統(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)都支持程序共享的功能，這就要求代碼是“純”的，即在運行期間不修改自身。數(shù)據(jù)一般包括靜態(tài)變量、動態(tài)堆和動態(tài)棧。進程進程的表示PCB程序PCB代碼數(shù)據(jù)+堆棧系統(tǒng)空間用戶空間（a）（b）進程進程的隊列為實現(xiàn)對進程的管理，系統(tǒng)需要按照某種策略將進程排成若干隊列，由于PCB是進程的代表，因而進程隊列實際上是由進程PCB構成的隊列.因為該隊列通常由鏈的形式實現(xiàn)的，所以也稱PCB鏈。系統(tǒng)中的進程隊列分為如下三類：就緒隊列、等待隊列、運行隊列。進程進程的隊列就緒隊列整個系統(tǒng)一個。所有處于就緒狀態(tài)的進程按照某種組織方式排在這一隊列中。等待隊列每個等待事件一個，當進程等待某一事件時，進入與該事件相關的等待隊列中；當某事件發(fā)生時，與該事件相關的一個或多個進程離開相應的等待隊列，進入就緒隊列。運行隊列在單CPU系統(tǒng)中只有一個，在多CPU系統(tǒng)中每個CPU各有一個，每個隊列中只有一個進程，指向運行隊列頭部的指針被稱作運行指示字。進程進程的類型系統(tǒng)進程——運行操作系統(tǒng)程序，完成操作系統(tǒng)的某些功能；用戶進程——運行用戶程序，直接為用戶服務。進程的特性并發(fā)性：與其它進程一道在宏觀上同時向前推進；動態(tài)性：進程是執(zhí)行中的程序.此外進程的動態(tài)性還體現(xiàn)在如下兩個方面：首先，進程是動態(tài)產(chǎn)生、動態(tài)消亡的；其次，在進程的生存期內(nèi)，其狀態(tài)處于經(jīng)常性的動態(tài)變化之中；獨立性：進程是調(diào)度的基本單位，它可以獲得處理機并參與并發(fā)執(zhí)行；交往性：進程在運行過程中可能會與其它進程發(fā)生直接或間接的相互作用；異步性：每個進程都以其相對獨立、不可預知的速度向前推進；結構性：每個進程有一個控制塊PCB。

進程兩個特征資源特征，包括程序執(zhí)行所必需的計算資源，例如程序代碼、內(nèi)存地址空間、文件系統(tǒng)、I/O設備、程序計數(shù)器、寄存器、?？臻g等執(zhí)行特征，包括在進程執(zhí)行過程中動態(tài)改變的特征，例如指令路徑（即進程執(zhí)行的指令序列）、進程的控制與執(zhí)行狀態(tài)等。進程通訊現(xiàn)代操作系統(tǒng)提供基本的系統(tǒng)調(diào)用函數(shù)，允許位于同一臺處理機或不同處理機的多個進程之間相互交流信息三種表現(xiàn)形式：通信：進程間的數(shù)據(jù)傳遞稱為進程間通信。兩個進程間傳遞的數(shù)據(jù)稱為消息；這種操作稱為消息傳遞同步：同步是使位于相同或不同處理機中的多個進程之間相互等待的操作，它要求進程的所有操作均必須等待到達某個控制狀態(tài)之后才進行。聚集（或規(guī)約）：聚集將位于相同或不同處理機中的多個進程的局部結果綜合起來，通過某種操作，產(chǎn)生一個新的結果，存儲在某個指定的或者所有的進程的變量中。具體實現(xiàn)：在共享存儲環(huán)境中，通過讀/寫操作系統(tǒng)通過的共享數(shù)據(jù)緩存區(qū)來實現(xiàn)在分布式存儲網(wǎng)絡環(huán)境中，通過網(wǎng)絡通信來實現(xiàn)進程通訊

定義：進程之間的互斥、同步及信息交換統(tǒng)稱進程通訊(Inter-ProcessCommunication，IPC)低級通訊：將進程互斥與進程同步稱作進程之間的低級通訊；高級通訊：進程之間大數(shù)據(jù)量的傳遞稱作進程之間的高級通訊。

進程通訊的模式進程通訊主要有兩種模式:共享內(nèi)存模式和消息模式。共享內(nèi)存模式相互通訊的進程之間需要有公共內(nèi)存,一組進程向該公共內(nèi)存中寫,另一組進程由該公共內(nèi)存中讀,如此便實現(xiàn)了進程之間的信息傳遞。需要解決兩個問題:為相互通訊的進程之間提供公共內(nèi)存；為訪問公共內(nèi)存提供必要的同步機制。信息傳遞模式（通訊通過兩個基本的系統(tǒng)調(diào)用命令,即發(fā)送命令和接收命令）直接方式間接方式進程通訊的模式直接方式：是指相互通訊的進程之間在通訊時直呼其名,發(fā)送者在發(fā)送時要指定接收者的名字,接收者在接收時要指定發(fā)送者的名字兩種系統(tǒng)調(diào)用形式：對稱形式——通訊形式的特點是一對一的，調(diào)用命令：send(R,M)：將消息M發(fā)給進程R；receive(S,N)：由進程S處接收消息至N。非對稱形式——通訊形式的特點是多對一的，調(diào)用命令：send(R,M)：將消息M發(fā)給進程R；receive(pid,N)：接受消息至N，返回pid為發(fā)送進程標識。信息傳遞兩種途徑：有緩沖途徑無緩沖途徑進程通訊的模式間接方式：是指相互通訊的進程之間在通訊時不是直呼對方名字,而是指明一個中間媒體,即信箱,進程之間通過信箱來實現(xiàn)相互間的通訊.此時,系統(tǒng)所提供的高級通訊原語以信箱取代進程．發(fā)送和接收原語如下：send(MB,M)：將消息M發(fā)送到信箱MB；receive(MB,N)：由信箱MB中接收消息至N。進程的創(chuàng)建與撤銷

進程創(chuàng)建

建立一個PCB，并對其內(nèi)容進行初始化；為該進程分配必要的存儲空間，并加載所要執(zhí)行的程序(在UNIX系統(tǒng)中需要通過另外一個系統(tǒng)調(diào)用execl實現(xiàn))；將PCB送入就緒隊列。進程撤銷完成使命的進程需要終止自己并告知操作系統(tǒng)，系統(tǒng)將對進程進行善后處理(收集進程狀態(tài)信息、通知其父進程等)，之后將收回進程所占有的所有資源(打開文件、內(nèi)存等)，最后撤銷其PCB。，非正常終止也將進入操作系統(tǒng)進行善后處理。線程的概念進程不適合細粒度的共享存儲并行程序設計。線程（thread）是進程上下文（context）中執(zhí)行的代碼序列，又被稱為輕量級進程（lightweightprocess），是進程內(nèi)的一個相對獨立的執(zhí)行流。進程可由單個線程來執(zhí)行，即通常所說的串行執(zhí)行；或者由多個線程來并行執(zhí)行，此時，多個線程將共享該進程的所有資源特征，并可以使用不同的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)度運行的一個獨立單位，有時也稱為活動、路徑或任務。操作系統(tǒng)中引入進程的目的，是為了使多個程序并發(fā)執(zhí)行，以改善資源利用率及提高系統(tǒng)的吞吐量。操作系統(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)點上下文切換速度快：由同一進程中的一個線程切換到另一個線程只需改變寄存器和棧，包括程序和數(shù)據(jù)在內(nèi)的地址空間不變；系統(tǒng)開銷小：創(chuàng)建線程比創(chuàng)建進程所需完成的工作少，因而對于客戶請求，服務器動態(tài)創(chuàng)建線程比動態(tài)創(chuàng)建進程具有更高的響應速度；通訊容易：由于同一進程中的多個線程地址空間共享，一個線程寫到數(shù)據(jù)空間的信息可以直接被該進程中的另一線程讀取，方便快捷；終止一個線程比終止一個進程的代價要小。線程的概念調(diào)度在傳統(tǒng)的操作系統(tǒng)中，CPU調(diào)度和分派的基本單位是進程。而在引入線程的操作系統(tǒng)中，則把線程作為CPU調(diào)度和分派的基本單位，進程則作為資源擁有的基本單位，從而使傳統(tǒng)進程的兩個屬性分開，線程便能輕裝運行，從而顯著地提高系統(tǒng)的并發(fā)性。同一進程中線程的切換不會引起進程切換，從而避免了昂貴的系統(tǒng)調(diào)用。但是在由一個進程中的線程切換到另一進程中的線程時，依然會引起進程切換。線程的概念并發(fā)性

在引入線程的操作系統(tǒng)中，不僅進程之間可以并發(fā)執(zhí)行，而且在一個進程中的多個線程之間也可以并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)的吞吐量。例：在一個未引入線程的單CPU操作系統(tǒng)中，若僅設置一個文件服務進程，當它由于某種原因被封鎖時，便沒有其他的文件服務進程來提供服務。在引入了線程的操作系統(tǒng)中，可以在一個文件服務進程中設置多個服務線程。當?shù)谝粋€線程等待時，文件服務進程中的第二個線程可以繼續(xù)運行；當?shù)诙€線程封鎖時，第三個線程可以繼續(xù)執(zhí)行，從而顯著地提高了文件服務的質(zhì)量以及系統(tǒng)的吞吐量。線程的概念系統(tǒng)開銷

不論是引入了線程的操作系統(tǒng)，還是傳統(tǒng)的操作系統(tǒng)，進程都是擁有系統(tǒng)資源的一個獨立單位，它可以擁有自己的資源。一般地說，線程自己不擁有系統(tǒng)資源（也有一點必不可少的資源），但它可以訪問其隸屬進程的資源。亦即一個進程的代碼段、數(shù)據(jù)段以及系統(tǒng)資源（如已打開的文件、I/O設備等），可供同一進程的其他所有線程共享。線程的概念擁有資源

由于在創(chuàng)建或撤消進程時，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設備等。因此，操作系統(tǒng)所付出的開銷將顯著地大于在創(chuàng)建或撤消線程時的開銷。在進行進程切換時，涉及到整個當前進程CPU環(huán)境的保存環(huán)境的設置以及新被調(diào)度運行的進程的CPU環(huán)境的設置。線程切換只需保存和設置少量寄存器的內(nèi)容，并不涉及存儲器管理方面的操作。因此進程切換的開銷遠大于線程切換的開銷。由于同一進程中的多個線程具有相同的地址空間，致使它們之間的同步和通信的實現(xiàn)也變得比較容易。線程的概念線程的結構線程的概念線程控制塊(ThreadControlBlock，TCB)：線程控制塊是標志線程存在的數(shù)據(jù)結構，其中包含系統(tǒng)對于線程進行管理所需要的全部信息線程的實現(xiàn)方式用戶級線程(UserLevelThread)在用戶層通過線程庫來實現(xiàn)核心級線程(KernelLevelThread)由操作系統(tǒng)直接支持硬件線程(HardwareThread)。硬件線程就是線程在硬件執(zhí)行資源上的表現(xiàn)形式。用戶級線程和內(nèi)核級線程用戶級線程和內(nèi)核級線程用戶級線程庫是用于用戶級線程管理的例程包，支持線程的創(chuàng)建、終止，以及調(diào)度線程的執(zhí)行并保存和恢復線程的上下文，這些操作都在用戶空間進行，無需內(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í)行的并行度。組合模式有的操作系統(tǒng)提供了組合的線程模式，在Solaris中，用戶創(chuàng)建的多個用戶級線程被映射到一些內(nèi)核線程上，內(nèi)核線程的數(shù)目可能少于用戶級線程的數(shù)目。用戶級線程用戶級線程和內(nèi)核級線程用戶級線程優(yōu)點：線程不依賴于操作系統(tǒng)，可以采用與問題相關的調(diào)度策略，靈活性好；同一進程中的線程切換不需進入操作系統(tǒng)，因而實現(xiàn)效率較高；有關線程的所有管理工作都由在用戶級實現(xiàn)的線程庫來支持。用戶級線程缺點：同一進程中的多個線程不能真正并行；由于線程對操作系統(tǒng)不可見，調(diào)度在進程級別，某進程中的一個線程通過系統(tǒng)調(diào)用進入操作系統(tǒng)受阻，該進程的其它線程也不能運行。用戶級線程特征：戶級線程的創(chuàng)建和管理等操作無須內(nèi)核參與，操作更快并行性不高，一個線程被系統(tǒng)阻塞后，整個進程被阻塞用戶級線程和內(nèi)核級線程核心級線程通過系統(tǒng)調(diào)用由操作系統(tǒng)創(chuàng)建，線程的控制結構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)，用戶級線程和內(nèi)核級線程之間的可以有不同的映射方式。多對一模型一對一模型多對多模型多線程的映射模型多對一模型多對一模型把多個用戶級線程映射到一個內(nèi)核級線程。線程的管理在用戶空間實現(xiàn)，所以效率高。當一個線程因調(diào)用系統(tǒng)調(diào)用被阻塞時，整個進程被阻塞。用戶級線程不能在多處理器上并發(fā)執(zhí)行，不支持內(nèi)核級線程的操作系統(tǒng)使用多對一模型。一對一模型一對一模型把每個用戶級線程影射到一個內(nèi)核級線程。當一個線程阻塞時，其他線程仍然可以運行。實例：Windows95/98/NT/2000OS/2多線程的映射模型多對多模型多對多模型將m個用戶級線程影射到n個內(nèi)核級線程，m≥n。用戶可以創(chuàng)建所需要的用戶級線程，通過分配適當數(shù)目的內(nèi)核級線程獲得并發(fā)執(zhí)行的優(yōu)勢并節(jié)省系統(tǒng)資源。例：Solaris2

多線程的映射模型線程生命周期線程的標識通常用一個整數(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的完成，試圖加鎖一個被上鎖的互斥量）。終止（terminated）：線程從起始函數(shù)中返回或者調(diào)用pthread_exit。線程的應用許多任務在邏輯上涉及多個控制流，控制流具有內(nèi)在的并發(fā)性，當其中一些控制流被阻塞時，另外一些控制流仍可繼續(xù)。在沒有線程支持的條件下，只能采用單進程或多進程模式，單進程不能表達多控制流，多進程開銷大而且在無共享存儲空間的條件下進程間交往困難。采用多線程一方面可以提高應用程序的并行性，另一方面也使程序設計簡潔明晰。例：Word文字編輯工具、Web服務器等。多線程程序設計為什么要多線程程序設計某些應用具有內(nèi)在的多個控制流結構，這些控制流具有合作性質(zhì)，需要共享內(nèi)存，采用多線程易于對問題建模，從而得到最自然的解決算法；在需要多控制流的應用中，多線程比多進程在速度上具有絕對優(yōu)勢，統(tǒng)計測試表明，線程的建立速度比進程的建立速度快100倍，進程內(nèi)線程間的切換速度與進程間切換速度也有數(shù)量級之差；采用多線程可以提高處理機與設備之間的并行性.在單控制流情形下，啟動設備的進程進入核心后將被阻塞，此時該進程的其它代碼也不能執(zhí)行.若此時無其它可運行程序，處理機將被閑置.多線程結構在一個線程等待時，其它線程可以繼續(xù)執(zhí)行，從而使設備和處理機并行工作；在多核環(huán)境下，多線程可以并行執(zhí)行，既可提高資源利用效率，又可提高進程推進速度。多線程機制多核處理器的基本結構是共享存儲的，多線程程序設計技術被認為是能夠充分挖掘共享存儲系統(tǒng)性能潛力的最有效的技術。多線程機制的優(yōu)點：創(chuàng)建一個線程比創(chuàng)建一個進程代價要??；線程之間的切換比進程間的切換代價??；充分利用多處理器；數(shù)據(jù)共享；快速響應特性；多線程編程可以使程序更加更加模塊化，簡化程序邏輯。多線程機制在多處理器系統(tǒng)上，如果一個應用具有如下特征，就可以利用多線程技術達到目標：前臺后臺操作；異步處理；需要加速執(zhí)行；模塊化程序結構。多線程環(huán)境下的進程控制語義單線程環(huán)境下的進程控制接口在多線程環(huán)境下語義可能會發(fā)生變化，包括進程創(chuàng)建、進程終止、進程執(zhí)行、信號處理等操作。

進程創(chuàng)建創(chuàng)建進程的系統(tǒng)調(diào)用完成后，被創(chuàng)建的新進程復制調(diào)用進程的內(nèi)容，當進程的一個線程中創(chuàng)建一個子進程，新的進程可以復制整個進程（包括所有線程）也可以只復制調(diào)用線程的內(nèi)容；執(zhí)行新的程序在進程中執(zhí)行新的程序，函數(shù)的語義在多線程環(huán)境下沒有發(fā)生大的變化。exec將會終止所有的線程，用新的程序覆蓋進程的地址空間，并開始執(zhí)行新的程序；多線程環(huán)境下的進程控制語義進程結束在任何一個線程中調(diào)用exit將會結束整個進程，另外從主線程返回也等同于調(diào)用exit而導致進程結束。如果要從線程中退出則調(diào)用專用的線程退出函數(shù)。信號處理信號是UNIX系統(tǒng)中通知進程的重要機制。信號可能是同步的也可能是異步的。發(fā)送給進程的信號在多線程環(huán)境下有多種選擇：發(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í)行counter--，這兩個操作都需要多個機器指令來完成，Counter=5counter++counter--register1=counterregister2=counterregister1=register1+1register2=register2-1counter=register1counter=register2可能的序列：Producer:register1=counter(register1=5)Producer:register1=register1+1(register1=6)Consumer:register2=counter(register2=5)Consumer:register2=register2-1(register2=6)Producer:counter=register1(counter=6)Consumer:counter=register2(counter=4)線程的同步同步：一組進程（線程）,為了協(xié)調(diào)其推進速度,在某些點處需要相互等待與相互喚醒,進程之間這種相互制約的關系稱作進程同步，簡稱同步(synchronization).進程同步是進程之間直接的相互作用形式,是合作進程之間有意識的行為,這種相互作用只發(fā)生在相關的進程之間。進程合作(cooperation)：一組進程，如果它們單獨不能正常進行,但并發(fā)可以正常進行,稱這種現(xiàn)象為進程合作，參與合作的進程稱作合作進程(cooperatingprocess)。線程的同步同步例子：要求:(1)關車門后方能啟動車輛;(2)到站停車后方能開車門.同步機制

同步機制：用于實現(xiàn)進程間同步的工具稱作同步機制，亦稱同步設施(synchronizationmechanism)同步機制應當滿足如下幾個基本要求:描述能力夠用：即用此種同步機制應當能夠描述操作系統(tǒng)及并發(fā)程序設計中所遇到的各種同步問題；可以實現(xiàn)；效率高；使用方便。順序程序程序的順序性包括內(nèi)部順序性和外部順序性。內(nèi)部順序性：對于一個進程來說,它的所有指令是按序執(zhí)行的；外部順序性,對于多個進程來說,所有進程是依次執(zhí)行的。P1活動:a1a2a3a4，P2活動:b1b2b3b4順序執(zhí)行時,有如下兩種情形:情形1:a1a2a3a4b1b2b3b4情形2:b1b2b3b4a1a2a3a4線程的同步順序程序的特性順序性：處理機嚴格按照指令次序依次執(zhí)行，即僅當一條指令執(zhí)行完后才開始執(zhí)行下一條指令；封閉性：程序在執(zhí)行過程中獨占系統(tǒng)中的全部資源，該程序的運行環(huán)境只與其自身動作有關，不受其它程序及外界因素影響；可再現(xiàn)性：程序的執(zhí)行結果與執(zhí)行速度無關，而只與初始條件有關，給定相同的初始條件，程序的任意多次執(zhí)行一定得到相同的執(zhí)行結果.線程的同步并發(fā)程序程序的并發(fā)性含義：內(nèi)部并發(fā)性，對于一個進程來說，它的所有指令可能按序執(zhí)行，也可能不按次序執(zhí)行；外部并發(fā)性：對于多個進程來說，所有進程是交叉(interleave)