多核多線程期末考試復(fù)習(xí)完美總結(jié)

1、微處理器發(fā)展史 1945年，世界上第一臺全自動電子數(shù)字計算機ENIAC。 處理器發(fā)展 第一代（19711973）：4 位或 8 位微處理器。代表：8008 第二代（19741977）：集成度提高1-4倍，運算速度提高10-15倍。代表：Z80，8080 第三代（19781984）：16位。代表：8086 第四代(19851992）：32 位微處理器，代表80386 第五代微處理器(19931995 年)，64位數(shù)據(jù)總線，32位地址總線，CPU內(nèi)部采用超標(biāo)量流水線設(shè)計，代表： 奔騰，K5，powerpc 第六代（19932002)：350nm以下工藝微處理器，平行并發(fā)計算而設(shè)計(EPIC)架構(gòu)，

2、代表：安騰 多核時代（2002今）：從2002年超線程技術(shù)開始的多核時代，代表：酷睿2北京科技大學(xué)天津?qū)W院-信息工程系2 2多核概念 單芯片多處理器（Chip Multiprocessors，簡稱CMP），CMP是由美國斯坦福大學(xué)提出的，其將大規(guī)模并行處理器中的SMP（對稱多處理器）集成到同一芯片內(nèi)，各個處理器并行執(zhí)行不同的進(jìn)程。 CMP vs SMT 同時多線程（Simultaneous Multithreading，簡稱SMT），是在單物理核上增加部分硬件資源，映射單物理核為多個物理核的技術(shù)。最早在P4處理器中出現(xiàn)，命名為超線程（Hyper Threading）。 由于CMP結(jié)構(gòu)已經(jīng)被劃分

3、成多個處理器核來設(shè)計，每個核都比較簡單，有利于優(yōu)化設(shè)計，因此更有發(fā)展前途。并行計算的弗林分類 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 Instructi

4、on stream Multiple Data stream, MIMD）北京科技大學(xué)天津?qū)W院-信息工程系多線程技術(shù) 進(jìn)程與線程 程序是指令的有序集合，是一個靜態(tài)的概念。 進(jìn)程是正在被執(zhí)行的程序，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位，是一個動態(tài)的概念。 線程是程序的有序控制流，是被執(zhí)行的指令序列。 線程屬于進(jìn)程，線程運行在進(jìn)程空間內(nèi)。 每個進(jìn)程至少包含一個主線程，負(fù)責(zé)對進(jìn)程進(jìn)行初始化并開始執(zhí)行初始指令，創(chuàng)建其他子線程。北京科技大學(xué)天津?qū)W院-信息工程系數(shù)據(jù)段數(shù)據(jù)段代碼段代碼段堆棧堆棧主線程主線程堆棧堆棧線程線程1堆棧堆棧線程線程Ncilk_spawn and cilk_sync cilk_sp

5、awncilk_spawn (or _Cilk_spawn_Cilk_spawn) gives the runtime permission to run a child function asynchronously. No 2nd thread is created or required! If there are no available workers, then the child will execute as a serial function call. The scheduler may steal the parent and run it in parallel wit

6、h the child function. The parent is not guaranteed to run in parallel with the child. cilk_synccilk_sync (or _Cilk_sync_Cilk_sync) waits for all children to complete.Anatomy of a spawnvoid f()void f() cilk_spawn g(); cilk_spawn g(); work work work work work work cilk_sync; cilk_sync; work work void

7、g()void g() work work work work work work spawning function (parent)continuationspawned function (child)spawnsyncWork Stealingwhen another worker is availablevoid f()void f() cilk_spawn g(); cilk_spawn g(); work work work work work work cilk_sync; cilk_sync; work work void g()void g() work work work

8、 work work work Worker AWorker BWorker ?steal!Intel Parallel AdvisorOffers guidance through the methodology. Annotation Wizard assists with the creation and insertion of Advisor annotations.Intel Parallel Studio 20119 Family of Parallel Programming Models Intel Parallel Advisor parallelism design in

9、novation General Enhancements Supports Visual Studio 2010多線程技術(shù) 進(jìn)程與線程的主要區(qū)別在于： 進(jìn)程擁有獨立的地址空間，而線程和其他線程共享進(jìn)程的地址空間。 進(jìn)程之間的通信可以使用操作系統(tǒng)原語或通過共享存儲空間來實現(xiàn)，而線程使用當(dāng)前程序設(shè)計語言的原語或者通過進(jìn)程共享空間來實現(xiàn)通信。 進(jìn)程上下文的切換是重量級的，進(jìn)程所有狀態(tài)都要保存。而線程之間的切換是輕量級的，只需要保存當(dāng)前寄存器的狀態(tài)。北京科技大學(xué)天津?qū)W院-信息工程系多線程技術(shù) 線程的狀態(tài)及其轉(zhuǎn)換北京科技大學(xué)天津?qū)W院-信息工程系新建新建就緒就緒終止終止執(zhí)行執(zhí)行阻塞阻塞進(jìn)入進(jìn)入調(diào)度調(diào)度超

10、時超時結(jié)束結(jié)束事件發(fā)生事件發(fā)生等待事件等待事件普通普通用戶用戶軟件設(shè)計師軟件設(shè)計師操作系統(tǒng)操作系統(tǒng)設(shè)計師設(shè)計師計算機硬件計算機硬件操作系統(tǒng)操作系統(tǒng)實用程序?qū)嵱贸绦驊?yīng)用程序應(yīng)用程序用戶與操作系統(tǒng)的關(guān)系用戶與操作系統(tǒng)的關(guān)系多核程序開發(fā)流程開始開始1.問題描述問題描述3.確定分解模確定分解模式式2.是否具有并行性是否具有并行性和并行價值和并行價值4.設(shè)計并行算設(shè)計并行算法法5.選取一種編程模型進(jìn)行實現(xiàn)選取一種編程模型進(jìn)行實現(xiàn)6.性能調(diào)優(yōu)性能調(diào)優(yōu)結(jié)束結(jié)束是是否否第二部分第二部分編程模型與實現(xiàn)編程模型與實現(xiàn)第一部分第一部分多核程序設(shè)計多核程序設(shè)計第三部分第三部分性能調(diào)優(yōu)性能調(diào)優(yōu)多核程序設(shè)計 3.分解模式

11、 任務(wù)分解 數(shù)據(jù)分解 數(shù)據(jù)流分解北京科技大學(xué)天津?qū)W院-信息工程系任務(wù)分解美化美化筑墻筑墻屋頂屋頂疊瓦疊瓦安裝電氣安裝電氣石膏板石膏板外部墻修飾外部墻修飾 示例：建造房屋 許多問題可被理解為在一個核心數(shù)據(jù)結(jié)構(gòu)上的一系列操作。許多問題可被理解為在一個核心數(shù)據(jù)結(jié)構(gòu)上的一系列操作。 結(jié)構(gòu)中的所有元素在計算中被更新或被使用結(jié)構(gòu)中的所有元素在計算中被更新或被使用 數(shù)據(jù)結(jié)構(gòu)被分為連續(xù)的子結(jié)構(gòu)或子區(qū)域。數(shù)據(jù)結(jié)構(gòu)被分為連續(xù)的子結(jié)構(gòu)或子區(qū)域。 Arrays: divide along one or more dimensions Lists: define sublists of discrete element

12、s Graphs: construct subgraphs數(shù)據(jù)分解數(shù)據(jù)分解任務(wù)分解vs數(shù)據(jù)分解 示例：園丁工作包括翻地和除草。 任務(wù)分解：兩個園丁分別完成各自功能，但在工作中也需要項目協(xié)調(diào)，兩個園丁不能對同一個地方又翻地又除草。 數(shù)據(jù)分解：將草坪劃分成兩半，各自完成一半草坪的翻地和除草工作。 在計算領(lǐng)域，采用哪種分解形式更高效取決于問題本身的限制。如果需要修剪草坪的地塊非常小以至于沒必要用兩個人修剪，修剪草坪最好只被分配給一個園丁做，任務(wù)分解是最好的選擇。數(shù)據(jù)分解或許適用于其他的任務(wù)序列，例如當(dāng)修剪草坪完成后，兩個園丁并行地鏟除雜草。北京科技大學(xué)天津?qū)W院-信息工程系數(shù)據(jù)流分解 將一個復(fù)雜的過程

13、劃分成多個任務(wù)，這些任務(wù)按照某種順序執(zhí)行，這種分解方式成為數(shù)據(jù)流分解。例如一個任務(wù)需要另一個任務(wù)的輸出結(jié)果，只有產(chǎn)生輸出結(jié)果的任務(wù)執(zhí)行完畢，這個任務(wù)才能繼續(xù)執(zhí)行。 示例：一個園丁承擔(dān)準(zhǔn)備工具任務(wù)，他要完成為割草機加油，清掃剪刀等工作。直到這些準(zhǔn)備工作就緒后，其他工作才能開始。著名例子是生產(chǎn)者消費者問題。北京科技大學(xué)天津?qū)W院-信息工程系多核程序設(shè)計 4.相關(guān)性分析 解決數(shù)據(jù)依賴關(guān)系可能更復(fù)雜 最簡單的例子是沒有依賴 處理任務(wù)之間的數(shù)據(jù)依賴關(guān)系的戰(zhàn)略： 變量本地化 改造變量 規(guī)約 明確的同步機制北京科技大學(xué)天津?qū)W院-信息工程系多核程序設(shè)計 5.數(shù)據(jù)競爭 明顯表征是內(nèi)存沖突，多個線程同時訪問同一內(nèi)存

14、空間，且至少有一個線程對該內(nèi)存進(jìn)行更新操作。 “搶椅子”游戲 讀寫沖突、寫寫沖突 當(dāng)多個線程訪問同一資源時，需要以某種順序來確保該資源某一時刻只能被一個線程使用，這種對線程的執(zhí)行順序進(jìn)行強制性限制的機制稱為同步。北京科技大學(xué)天津?qū)W院-信息工程系常用的同步機制常用的同步機制 臨界區(qū)（臨界區(qū)（critical section） 信號量（信號量（semaphore） 互斥量（互斥量（mutex） 柵障（柵障（barrier） 鎖的粒度鎖的粒度 死鎖死鎖線程同步線程同步目錄 基本線程技術(shù) Thread類 同步互斥訪問 新特性 concurrent工具包基本線程技術(shù)創(chuàng)建線程 使用java.lang.Th

15、read類或者java.lang.Runnable接口編寫代碼來定義、實例化和啟動新線程 繼承Thread類，重寫run( )方法，然后通過start()方法去啟動線程 實現(xiàn)Runnable接口，重寫run( )方法，然后將其交由Thread去執(zhí)行基本線程技術(shù)Thread類 Thread類實現(xiàn)了Runnable接口 關(guān)鍵屬性 private char name; /線程名字 private int priority; /線程的優(yōu)先級 private boolean daemon = false;/是否是守護(hù)線程 setDeamon(true) private Runnable target;

16、/What will be run public final static int MIN_PRIORITY = 1; public final static int NORM_PRIORITY = 5;/The default priority that is assigned to a thread. public final static int MAX_PRIORITY = 10;Thread類 常用方法 start方法/啟動一個線程當(dāng)調(diào)用start方法后，系統(tǒng)才會開啟一個新的線程來執(zhí)行用戶定義的子任務(wù)，在這個過程中，會為相應(yīng)的線程分配需要的資源 run方法不需要用戶來調(diào)用的，通過st

17、art方法啟動一個線程之后，當(dāng)線程獲得了CPU執(zhí)行時間，便進(jìn)入run方法體去執(zhí)行具體的任務(wù)。 sleep方法/讓線程睡眠一個時間段，讓CPU去執(zhí)行其他的任務(wù) yield方法/交出CPU權(quán)限它跟sleep方法類似，但是調(diào)用yield方法并不會讓線程進(jìn)入阻塞狀態(tài)，而是讓線程回到可運行狀態(tài)，以允許具有相同優(yōu)先級的其他線程獲得運行機會，這一點是和sleep方法不一樣的Thread類 join方法/合并線程A線程中調(diào)用B.join(t)，則A線程會等B線程執(zhí)行t時間后執(zhí)行，若調(diào)用無參join方法，則等待B線程執(zhí)行完后A線程繼續(xù)執(zhí)行，A、B線程合并。 interrupt方法/中斷線程中斷處于阻塞狀態(tài)的線程

18、。 stop方法 destroy方法 currentThread靜態(tài)方法用來獲取當(dāng)前線程eg. System.out.println(Thread.currentThread().getName(); System.out.println(Thread.currentThread().getID();線程狀態(tài)轉(zhuǎn)換同步互斥訪問問題引出OUTPUT : Thread-0窗口出售一張，剩余票數(shù): 2Thread-1窗口出售一張，剩余票數(shù): 2Thread-2窗口出售一張，剩余票數(shù): 1Thread-3窗口出售一張，剩余票數(shù): 0Thread-1窗口出售一張，剩余票數(shù): -2Thread-0窗口出售一

19、張，剩余票數(shù): -2 定義：多個進(jìn)程均需要訪問的變量稱為定義：多個進(jìn)程均需要訪問的變量稱為公共變量公共變量( (shared variable) shared variable) ； 定義：訪問共享變量的程序段稱作定義：訪問共享變量的程序段稱作臨界區(qū)臨界區(qū)域域( (critical region),critical region),也稱為臨界段也稱為臨界段( (critical critical section)section)。 臨界區(qū)臨界區(qū) 線程互斥是線程之間所發(fā)生的一種間接性相互作用線程互斥是線程之間所發(fā)生的一種間接性相互作用, ,這種相互作用是進(jìn)程本身不希望的這種相互作用是進(jìn)程本身不希

20、望的, ,也是運行線程感也是運行線程感覺不到的。線程互斥可能發(fā)生在相關(guān)線程之間覺不到的。線程互斥可能發(fā)生在相關(guān)線程之間, ,也可也可能發(fā)生在不相關(guān)進(jìn)程之間。能發(fā)生在不相關(guān)進(jìn)程之間。 互斥量（互斥量（MutexMutex）作為一種互斥設(shè)備，有兩個狀態(tài)，作為一種互斥設(shè)備，有兩個狀態(tài)，上鎖和空閑。同一時刻只能有一個線程能夠?qū)コ馍湘i和空閑。同一時刻只能有一個線程能夠?qū)コ饬考渔i。對于一個已經(jīng)被加鎖的互斥量，當(dāng)另外一量加鎖。對于一個已經(jīng)被加鎖的互斥量，當(dāng)另外一個線程試圖對它加鎖時，該線程會被阻塞，直到該個線程試圖對它加鎖時，該線程會被阻塞，直到該互斥量被釋放?；コ饬勘会尫拧?互斥量是一種鎖，線程對共享

21、資源進(jìn)行訪問之前必互斥量是一種鎖，線程對共享資源進(jìn)行訪問之前必須先獲得鎖，否則，線程保持等待狀態(tài)，直到鎖可須先獲得鎖，否則，線程保持等待狀態(tài)，直到鎖可用，只有其他線程都不占有它時，一個線程才可以用，只有其他線程都不占有它時，一個線程才可以占有它。占有鎖的過程叫做鎖定或者獲得互斥量。占有它。占有鎖的過程叫做鎖定或者獲得互斥量。線程互斥線程互斥 信號量與信號量與PV操作：包括一種稱作信號燈類型的變量以及對操作：包括一種稱作信號燈類型的變量以及對于此種變量所能進(jìn)行的兩個操作：即于此種變量所能進(jìn)行的兩個操作：即P(wait,減量操作減量操作)操作操作和和V（signal,增量操作）操作。增量操作）操作

22、。wait(s) signal(s) s-; s+; if(s 0) if(s = 0) add to S.L; remove from S.L; block(); wakeup(); 信號量使用基本要求信號量使用基本要求: 必需置一次且只能置一次初值必需置一次且只能置一次初值, 而且初值必需為非負(fù)整數(shù)而且初值必需為非負(fù)整數(shù); 只能執(zhí)行只能執(zhí)行P操作和操作和V操作操作, 所有其它操作均是非法的。所有其它操作均是非法的。信號量信號量 線程互斥是線程之間所發(fā)生的一種間接性相互作用線程互斥是線程之間所發(fā)生的一種間接性相互作用, ,這種相互作用是進(jìn)程本身不希望的這種相互作用是進(jìn)程本身不希望的, ,也是

23、運行線程感也是運行線程感覺不到的。線程互斥可能發(fā)生在相關(guān)線程之間覺不到的。線程互斥可能發(fā)生在相關(guān)線程之間, ,也可也可能發(fā)生在不相關(guān)進(jìn)程之間。能發(fā)生在不相關(guān)進(jìn)程之間。 互斥量（互斥量（MutexMutex）作為一種互斥設(shè)備，有兩個狀態(tài)，作為一種互斥設(shè)備，有兩個狀態(tài)，上鎖和空閑。同一時刻只能有一個線程能夠?qū)コ馍湘i和空閑。同一時刻只能有一個線程能夠?qū)コ饬考渔i。對于一個已經(jīng)被加鎖的互斥量，當(dāng)另外一量加鎖。對于一個已經(jīng)被加鎖的互斥量，當(dāng)另外一個線程試圖對它加鎖時，該線程會被阻塞，直到該個線程試圖對它加鎖時，該線程會被阻塞，直到該互斥量被釋放?；コ饬勘会尫?。 互斥量是一種鎖，線程對共享資源進(jìn)行訪問之

24、前必互斥量是一種鎖，線程對共享資源進(jìn)行訪問之前必須先獲得鎖，否則，線程保持等待狀態(tài)，直到鎖可須先獲得鎖，否則，線程保持等待狀態(tài)，直到鎖可用，只有其他線程都不占有它時，一個線程才可以用，只有其他線程都不占有它時，一個線程才可以占有它。占有鎖的過程叫做鎖定或者獲得互斥量。占有它。占有鎖的過程叫做鎖定或者獲得互斥量。線程互斥線程互斥3333多核概念 單芯片多處理器（Chip Multiprocessors，簡稱CMP），CMP是由美國斯坦福大學(xué)提出的，其將大規(guī)模并行處理器中的SMP（對稱多處理器）集成到同一芯片內(nèi)，各個處理器并行執(zhí)行不同的進(jìn)程。 CMP vs SMT 同時多線程（Simultaneo

25、us Multithreading，簡稱SMT），是在單物理核上增加部分硬件資源，映射單物理核為多個物理核的技術(shù)。最早在P4處理器中出現(xiàn)，命名為超線程（Hyper Threading）。 由于CMP結(jié)構(gòu)已經(jīng)被劃分成多個處理器核來設(shè)計，每個核都比較簡單，有利于優(yōu)化設(shè)計，因此更有發(fā)展前途。兩個處理器 vs. 雙核雙核 兩個核在一個芯片內(nèi)直接連接 多線程和多進(jìn)程自動并行處理 熱量消耗增加的很少 封裝成本降低兩個處理器兩個處理器 兩個分開的芯片通過外在系兩個分開的芯片通過外在系統(tǒng)總線連接統(tǒng)總線連接 需要外在軟件支持需要外在軟件支持 更多的熱量消耗更多的熱量消耗超線程技術(shù)與多核體系結(jié)構(gòu)的區(qū)別兩個線程在支

26、持超線程技術(shù)的處理器上執(zhí)行兩個線程在雙核處理器上并行執(zhí)行兩個線程在雙核處理器上并行執(zhí)行創(chuàng)建線程的創(chuàng)建線程的APIHANDLE CreateThread( LPSECURITY_ATTRIBUTES ThreadAttributes, DWORD StackSize, LPTHREAD_START_ROUTINE StartAddress, LPVOID Parameter, DWORD CreationFlags, LPDWORD ThreadId ); 參數(shù)參數(shù)1：指向：指向SECURITY_ATTRIBUTES結(jié)構(gòu)的指針。該線程內(nèi)核對象的默認(rèn)安全結(jié)構(gòu)的指針。該線程內(nèi)核對象的默認(rèn)安全屬性，設(shè)

27、置為屬性，設(shè)置為NULL。 參數(shù)參數(shù)2：設(shè)定線程可以將多少地址空間用于它自己的：設(shè)定線程可以將多少地址空間用于它自己的堆棧，堆棧，0為默認(rèn)值。為默認(rèn)值。 參數(shù)參數(shù)3：指明要線程執(zhí)行的線程：指明要線程執(zhí)行的線程執(zhí)行函數(shù)執(zhí)行函數(shù)地址。地址。多核程序設(shè)計 5.數(shù)據(jù)競爭 明顯表征是內(nèi)存沖突，多個線程同時訪問同一內(nèi)存空間，且至少有一個線程對該內(nèi)存進(jìn)行更新操作。 “搶椅子”游戲 讀寫沖突、寫寫沖突 當(dāng)多個線程訪問同一資源時，需要以某種順序來確保該資源某一時刻只能被一個線程使用，這種對線程的執(zhí)行順序進(jìn)行強制性限制的機制稱為同步。北京科技大學(xué)天津?qū)W院-信息工程系 例：例：如果一個進(jìn)程有一個共享變量如果一個進(jìn)程

28、有一個共享變量counter，兩個兩個線程線程producer和和consumer，線程線程producer執(zhí)行執(zhí)行counter+，線程線程consumer執(zhí)行執(zhí)行counter-，這兩個這兩個操作都需要多個機器指令來完成，操作都需要多個機器指令來完成，Counter=5counter+ counter-register1=counter register2=counterregister1=register1+1 register2=register2-1counter=register1 counter= register2可能的序列：可能的序列：Producer: register1=

29、counter (register1=5)Producer: register1=register1+1 (register1=6)Consumer: register2=counter (register2=5)Consumer: register2= register2-1 (register2=4)Producer: counter= register1 (counter=6)Consumer: counter= register2 (counter=4)數(shù)據(jù)競爭數(shù)據(jù)競爭 例：一個圖書館管理系統(tǒng)例：一個圖書館管理系統(tǒng), , 連有兩個終端連有兩個終端, , 用戶可通過終端借用戶可通過終端借

30、書書. . 為簡化問題為簡化問題, , 假設(shè)所有用戶借閱的圖書是相同的假設(shè)所有用戶借閱的圖書是相同的. . 設(shè)設(shè)x x代代表圖書的剩余數(shù)量表圖書的剩余數(shù)量, , 為兩個終端用戶服務(wù)的程序為兩個終端用戶服務(wù)的程序 線程同步線程同步常用的同步機制常用的同步機制 臨界區(qū)（臨界區(qū)（critical section） 信號量（信號量（semaphore） 互斥量（互斥量（mutex） 柵障（柵障（barrier） 鎖的粒度鎖的粒度 死鎖死鎖線程同步線程同步同步例子：同步例子：要求要求: (1): (1)關(guān)車門后方能啟動車輛關(guān)車門后方能啟動車輛; ; (2) (2)到站停車后方能開車門到站停車后方能開車門

31、. . 線程同步線程同步 定義：多個進(jìn)程均需要訪問的變量稱為定義：多個進(jìn)程均需要訪問的變量稱為公共變量公共變量( (shared variable) shared variable) ； 定義：訪問共享變量的程序段稱作定義：訪問共享變量的程序段稱作臨界區(qū)臨界區(qū)域域( (critical region),critical region),也稱為臨界段也稱為臨界段( (critical critical section)section)。 臨界區(qū)臨界區(qū) 所有所有n n個進(jìn)程競爭使用一些共享的數(shù)據(jù)。個進(jìn)程競爭使用一些共享的數(shù)據(jù)。 每個進(jìn)程有一個代碼段每個進(jìn)程有一個代碼段, ,稱為臨界區(qū)稱為臨界區(qū),

32、,在那兒共享在那兒共享數(shù)據(jù)被訪問。數(shù)據(jù)被訪問。 問題問題: :保證當(dāng)一個進(jìn)程正在臨界區(qū)執(zhí)行時，沒有另保證當(dāng)一個進(jìn)程正在臨界區(qū)執(zhí)行時，沒有另外的進(jìn)程進(jìn)入臨界區(qū)執(zhí)行。外的進(jìn)程進(jìn)入臨界區(qū)執(zhí)行。 解決臨界區(qū)問題需滿足解決臨界區(qū)問題需滿足 互斥：假定進(jìn)程互斥：假定進(jìn)程PiPi在其臨界區(qū)內(nèi)執(zhí)行，其他任何線程將被排在其臨界區(qū)內(nèi)執(zhí)行，其他任何線程將被排斥在自己的臨界區(qū)之外斥在自己的臨界區(qū)之外. . 有空讓進(jìn)：臨界區(qū)沒有線程執(zhí)行，有些線程需要進(jìn)入臨界區(qū)，有空讓進(jìn)：臨界區(qū)沒有線程執(zhí)行，有些線程需要進(jìn)入臨界區(qū)，不能無限期地延長下一個要進(jìn)入臨界區(qū)進(jìn)程的等待時間不能無限期地延長下一個要進(jìn)入臨界區(qū)進(jìn)程的等待時間. . 有

33、限等待：在一個線程提出進(jìn)入臨界區(qū)的請求和該請求得到有限等待：在一個線程提出進(jìn)入臨界區(qū)的請求和該請求得到答復(fù)的時間內(nèi)，其他線程進(jìn)入臨界區(qū)前的等待時間必須是有答復(fù)的時間內(nèi)，其他線程進(jìn)入臨界區(qū)前的等待時間必須是有限的。限的。臨界區(qū)臨界區(qū)臨界區(qū)const int n = /* number of threads */;void P(int i)while(true)entercritical(i); 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)/* critical sectioin */臨界區(qū)臨界區(qū)exitcritical(i); 退出區(qū)退出區(qū)/* remainder */ 剩留區(qū)剩留區(qū) 線程互斥是線程之間所發(fā)生的一種間接性相互作

34、用線程互斥是線程之間所發(fā)生的一種間接性相互作用, ,這種相互作用是進(jìn)程本身不希望的這種相互作用是進(jìn)程本身不希望的, ,也是運行線程感也是運行線程感覺不到的。線程互斥可能發(fā)生在相關(guān)線程之間覺不到的。線程互斥可能發(fā)生在相關(guān)線程之間, ,也可也可能發(fā)生在不相關(guān)進(jìn)程之間。能發(fā)生在不相關(guān)進(jìn)程之間。 互斥量（互斥量（MutexMutex）作為一種互斥設(shè)備，有兩個狀態(tài)，作為一種互斥設(shè)備，有兩個狀態(tài)，上鎖和空閑。同一時刻只能有一個線程能夠?qū)コ馍湘i和空閑。同一時刻只能有一個線程能夠?qū)コ饬考渔i。對于一個已經(jīng)被加鎖的互斥量，當(dāng)另外一量加鎖。對于一個已經(jīng)被加鎖的互斥量，當(dāng)另外一個線程試圖對它加鎖時，該線程會被阻塞

35、，直到該個線程試圖對它加鎖時，該線程會被阻塞，直到該互斥量被釋放?；コ饬勘会尫拧?互斥量是一種鎖，線程對共享資源進(jìn)行訪問之前必互斥量是一種鎖，線程對共享資源進(jìn)行訪問之前必須先獲得鎖，否則，線程保持等待狀態(tài)，直到鎖可須先獲得鎖，否則，線程保持等待狀態(tài)，直到鎖可用，只有其他線程都不占有它時，一個線程才可以用，只有其他線程都不占有它時，一個線程才可以占有它。占有鎖的過程叫做鎖定或者獲得互斥量。占有它。占有鎖的過程叫做鎖定或者獲得互斥量。線程互斥線程互斥無互斥量 可能的輸出：A Hello oneB Hello oneB Hello twoA Hello two創(chuàng)建線程的創(chuàng)建線程的APIHANDLE

36、CreateThread( LPSECURITY_ATTRIBUTES ThreadAttributes, DWORD StackSize, LPTHREAD_START_ROUTINE StartAddress, LPVOID Parameter, DWORD CreationFlags, LPDWORD ThreadId ); 參數(shù)參數(shù)4：傳遞給創(chuàng)建線程的：傳遞給創(chuàng)建線程的參數(shù)參數(shù)。 參數(shù)參數(shù)5：如果值為：如果值為0，線程創(chuàng)建后可以立即執(zhí)行。，線程創(chuàng)建后可以立即執(zhí)行。 參數(shù)參數(shù)6：存放新線程的：存放新線程的ID，對線程，對線程ID不感興趣可設(shè)置不感興趣可設(shè)置NULL。線程執(zhí)行函數(shù)線程執(zhí)行函

37、數(shù)MyThreadStart(LPVOID p)即為線程執(zhí)行函數(shù)，函數(shù)名自擬。即為線程執(zhí)行函數(shù)，函數(shù)名自擬。l釋放操作系統(tǒng)資源釋放操作系統(tǒng)資源在程序結(jié)束前要清除線程及其所占資源在程序結(jié)束前要清除線程及其所占資源l線程退出調(diào)用函數(shù)：線程退出調(diào)用函數(shù)：BOOL CloseHandle(HANDLE hObject);線程退出線程退出l等待函數(shù)：等待函數(shù)： DWORD WaitForSingleObject( HANDLE hHandle, DWORD dwMilliseconds );參數(shù)參數(shù)1：hHandle表示一個能夠支持已通知表示一個能夠支持已通知/未通知狀態(tài)的內(nèi)未通知狀態(tài)的內(nèi)核對象；核對象

38、；參數(shù)參數(shù)2：dwMilliseconds指為了等待該對象變?yōu)橐淹ㄖ獱钪笧榱说却搶ο笞優(yōu)橐淹ㄖ獱顟B(tài)，將等待多長時間。態(tài)，將等待多長時間。l等待終止條件：等待終止條件：過了預(yù)定時間過了預(yù)定時間dwMilliseconds使用使用INFINITE參數(shù)，表示線程永遠(yuǎn)等下去，直到該進(jìn)程中參數(shù)，表示線程永遠(yuǎn)等下去，直到該進(jìn)程中止。止。Waiting for a Threadl等待函數(shù)：等待函數(shù)： DWORD WaitForMultipleObjects(DWORD dwCount, CONST HANDLE *lpHandles, BOOL fWaitAll, DWORD dwMilliseconds

39、);參數(shù)參數(shù)1：dwCount指要讓函數(shù)查看的內(nèi)核對象數(shù)量；指要讓函數(shù)查看的內(nèi)核對象數(shù)量；參數(shù)參數(shù)2：phObjects是指向內(nèi)核對象句柄的數(shù)組的指針；是指向內(nèi)核對象句柄的數(shù)組的指針；參數(shù)參數(shù)3：fWaitAll為為TRUE時，該函數(shù)只有當(dāng)指定的所有內(nèi)時，該函數(shù)只有當(dāng)指定的所有內(nèi)核對象都變?yōu)橐淹ㄖ獱顟B(tài)才返回；為核對象都變?yōu)橐淹ㄖ獱顟B(tài)才返回；為FALSE時，該函數(shù)只時，該函數(shù)只要指定的內(nèi)核對象中有一個變?yōu)橐淹ㄖ獱顟B(tài)即返回；要指定的內(nèi)核對象中有一個變?yōu)橐淹ㄖ獱顟B(tài)即返回；參數(shù)參數(shù)4：dwMilliseconds作用同作用同WaitForSingleObject。Waiting for Many Th

40、read 全局變量全局變量 進(jìn)程中的所有線程均可以訪問所有的全局變量，因而全局進(jìn)程中的所有線程均可以訪問所有的全局變量，因而全局變量成為變量成為Win32多線程通信的最簡單方式。多線程通信的最簡單方式。 事件事件 事件事件(Event)是是WIN32提供的最靈活的線程間同步方式。提供的最靈活的線程間同步方式。 事件存在兩種狀態(tài)：事件存在兩種狀態(tài)： 激發(fā)狀態(tài)激發(fā)狀態(tài)(signaled or true) 未激發(fā)狀態(tài)未激發(fā)狀態(tài)(unsignal or false) 事件可分為兩類：事件可分為兩類： 手動設(shè)置：這種對象只能用程序來手動設(shè)置，在需要該事件或者事手動設(shè)置：這種對象只能用程序來手動設(shè)置，在需

41、要該事件或者事件發(fā)生時，采用件發(fā)生時，采用SetEvent及及ResetEvent來進(jìn)行設(shè)置。來進(jìn)行設(shè)置。 自動恢復(fù)：一旦事件發(fā)生并被處理后，自動恢復(fù)到?jīng)]有事件狀態(tài)，自動恢復(fù)：一旦事件發(fā)生并被處理后，自動恢復(fù)到?jīng)]有事件狀態(tài)，不需要再次設(shè)置。不需要再次設(shè)置。Win32線程同步的實現(xiàn)線程同步的實現(xiàn)l事件對象也屬于內(nèi)核對象，包含一個使用計數(shù)，一個事件對象也屬于內(nèi)核對象，包含一個使用計數(shù)，一個用于指明該事件是一個自動重置的事件還是一個人工用于指明該事件是一個自動重置的事件還是一個人工重置的事件的布爾值，另一個用于指明該事件處于已重置的事件的布爾值，另一個用于指明該事件處于已通知狀態(tài)還是未通知狀態(tài)的布爾

42、值。通知狀態(tài)還是未通知狀態(tài)的布爾值。l有兩種不同類型的事件對象。一種是人工重置的事件，有兩種不同類型的事件對象。一種是人工重置的事件，另一種是自動重置的事件。當(dāng)人工重置的事件得到通另一種是自動重置的事件。當(dāng)人工重置的事件得到通知時，等待該事件的所有線程均變?yōu)榭烧{(diào)度線程。當(dāng)知時，等待該事件的所有線程均變?yōu)榭烧{(diào)度線程。當(dāng)一個自動重置的事件得到通知時，等待該事件的線程一個自動重置的事件得到通知時，等待該事件的線程中只有一個線程變?yōu)榭烧{(diào)度線程。中只有一個線程變?yōu)榭烧{(diào)度線程。事件事件事件事件HANDLE CreateEvent ( LPSECURITY_ATTRIBUTES lpEventAttribu

43、tes, BOOL bManualReset, BOOL bInitialState, LPCSTR lpName); lbManualReset能夠告訴系統(tǒng)是創(chuàng)建一個人工重置能夠告訴系統(tǒng)是創(chuàng)建一個人工重置的事件的事件 （TRUE），還是創(chuàng)建一個自動重置的事件），還是創(chuàng)建一個自動重置的事件（ FALSE ）。）。lbInitialState 指明該事件是要初始化為已通知狀態(tài)指明該事件是要初始化為已通知狀態(tài)（TRUE），還是未通知狀態(tài)（），還是未通知狀態(tài)（FALSE）。）。l調(diào)用調(diào)用SetEvent時，可以將事件改為已通知狀態(tài)：時，可以將事件改為已通知狀態(tài)：BOOL SetEvent( HAND

44、LE event );l調(diào)用調(diào)用ResetEvent時，可以將該事件改為未通知狀態(tài)：時，可以將該事件改為未通知狀態(tài)：BOOL ResetEvent( HANDLE event );l人工重置事件是指通過人工重置事件是指通過SetEvent和和ResetEvent來設(shè)置來設(shè)置事件的通知狀態(tài)，而自動重置事件的含義是：當(dāng)事件事件的通知狀態(tài)，而自動重置事件的含義是：當(dāng)事件被被SetEvent函數(shù)設(shè)置為已通知狀態(tài)時，在等待事件的函數(shù)設(shè)置為已通知狀態(tài)時，在等待事件的線程中，只有一個線程被恢復(fù)，之后系統(tǒng)自動將事件線程中，只有一個線程被恢復(fù)，之后系統(tǒng)自動將事件置為未通知狀態(tài)。置為未通知狀態(tài)。事件事件Examp

45、le: EventsDWORD WINAPI threadFunc(LPVOID arg) BOOL bFound = bigFind() ; if (bFound) SetEvent(hObj0); / signal data was found bigFound() ; moreBigStuff() ; return 0;HANDLE hObj2; / 0 is event, 1 is threadExample: Main function. . . hObj0 = CreateEvent(NULL, FALSE, FALSE, NULL); hObj1 = CreateThread(N

46、ULL,0,threadFunc,NULL,0,NULL); DWORD waitRet = WaitForMultipleObjects(2, hObj, FALSE, INFINITE); switch(waitRet) case WAIT_OBJECT_0: / event signaled printf(found it!n); WaitForSingleObject(hObj1, INFINITE) ; case WAIT_OBJECT_0+1:/ thread signaled printf(thread donen); break ; default: printf(wait e

47、rror: ret %un, waitRet); break ; OpenMP編程技術(shù)循環(huán)并行化 循環(huán)并行化編譯指導(dǎo)語句的格式#pragma omp parallel for clauseclausefor（index=first;test_expression; increment_expr）body of the loop; parallel關(guān)鍵字將緊跟的程序塊擴展為若干完全等同的并行區(qū)域，每個線程擁有完全相同的并行區(qū)域； 關(guān)鍵字for則將循環(huán)中的工作分配到線程組中，線程組中的每一個線程完成循環(huán)中的一部分內(nèi)容。 OpenMP編程技術(shù)循環(huán)并行化北京科技大學(xué)天津?qū)W院-信息工程系#pragma

48、omp parallel#pragma omp for for (i=0; iN; i+)Do_Work(i);#pragma omp parallel#pragma omp forImplicit barrieri = 0i = 1i = 2i = 3i = 4i = 5i = 6i = 7i = 8i = 9i = 10i = 11#pragma omp parallel#pragma omp for for(i = 0; i 12; i+) ci = ai + bi;OpenMP編程技術(shù)循環(huán)并行化 這兩種方式是等價的：北京科技大學(xué)天津?qū)W院-信息工程系#pragma omp paralle

49、l #pragma omp for for (i=0; i MAX; i+) resi = huge(); #pragma omp parallel for for (i=0; i MAX; i+) resi = huge(); 循環(huán)并行化語句的限制 循環(huán)并行化語句必須是for循環(huán)語句并具有規(guī)范的格式: for （index = start ; index end ; increment_expr） 能夠推測出循環(huán)的次數(shù)，有以下約束 ： 循環(huán)語句中的循環(huán)變量必須是有符號整型； 循環(huán)語句中的比較操作必須是這樣的形式：loop_variable , 或= loop_invariant_intege

50、r； 循環(huán)語句中的第三個表達(dá)式（for循環(huán)的循環(huán)步長）必須是整數(shù)加或整數(shù)減，加減的數(shù)值必須是一個循環(huán)不變量（loop invariant value）； 如果比較操作是或或=，那么循環(huán)變量的值在每次迭代時都必須減少； 循環(huán)必須是單入口、單出口的，循環(huán)內(nèi)部不允許有能夠到達(dá)循環(huán)之外的跳轉(zhuǎn)語句。 簡單循環(huán)的并行化 兩個向量相加，并將計算的結(jié)果保存到第三個向量中，向量的維數(shù)為n。向量相加即向量的各個分量分別相加。 for（int i=0; in; i+） zi = xi + yi; 使用循環(huán)并行化編譯指導(dǎo)語句直接對循環(huán)進(jìn)行并行化 ：#pragma omp parallel forfor（int i=0

51、; in; i+） zi = xi + yi; 但如存在循環(huán)依賴性，則不能直接并行化，實例：for（int i=0; in; i+） zi = zi-1 + xi + yiOpenMP多線程編程基礎(chǔ)多線程編程基礎(chǔ) OpenMP的編程模型以線程為基礎(chǔ)，通過的編程模型以線程為基礎(chǔ)，通過編譯指導(dǎo)編譯指導(dǎo)語句語句來顯示地指導(dǎo)并行化，為編程人員提供了對并來顯示地指導(dǎo)并行化，為編程人員提供了對并行化的完整的控制。行化的完整的控制。 OpenMP 的執(zhí)行模型采用的執(zhí)行模型采用 Fork-Join 的形式的形式 Fork：創(chuàng)建新線程或喚醒已有線程：創(chuàng)建新線程或喚醒已有線程 Join：多線程的匯合：多線程的匯合

52、 OpenMP版本的版本的“Hello World”#include “omp.h”int main（）（） printf（“Hello from serial.n”）; /串行執(zhí)行串行執(zhí)行 printf（“Thread number = %dn”,omp_get_thread_num（）（）; omp_set_num_threads(4); #pragma omp parallel /開始并行執(zhí)行開始并行執(zhí)行 printf（“Hello from parallel. Thread number=%dn”,omp_get_thread_num（）（）; printf（“Hello from s

53、erial again.n”）; return 0;OpenMP編程技術(shù)循環(huán)并行化 循環(huán)并行化編譯指導(dǎo)語句的格式#pragma omp parallel for clauseclausefor（index=first;test_expression; increment_expr）body of the loop; parallel關(guān)鍵字將緊跟的程序塊擴展為若干完全等同的并行區(qū)域，每個線程擁有完全相同的并行區(qū)域； 關(guān)鍵字for則將循環(huán)中的工作分配到線程組中，線程組中的每一個線程完成循環(huán)中的一部分內(nèi)容。 數(shù)據(jù)相關(guān)的概念 如果語句S2與語句S1存在數(shù)據(jù)相關(guān)，那么必然存在以下兩種情況之一： S1在循

54、環(huán)的一次迭代中訪問存儲單元L，而S2在隨后的一次迭代中訪問同一存儲單元，即：循環(huán)迭代相關(guān) ; S1和S2在同一循環(huán)迭代中訪問同一存儲單元L，但S1的執(zhí)行在S2之前，即：非循環(huán)迭代相關(guān) 。 實例： x0 = 0; y0 = 1; #pragma omp parallel for private(k) for (k = 1; k 100; k+) xk = yk-1 + 1; /S1 yk = xk-1 + 2; /S2 循環(huán)嵌套 循環(huán)并行化編譯制導(dǎo)語句可以加在任意一個循環(huán)之前，則對應(yīng)的最近的循環(huán)語句被并行化，其它部分保持不變。 實際上并行化是作用于嵌套循環(huán)中的某一個循環(huán)，其它部分由執(zhí)行到的線程負(fù)

55、責(zé)執(zhí)行。 int i; int j;#pragma omp parallel for private(j)for(i=0;i1;i+)for(j=6;j10;j+)printf(i=%d j=%dn,i,j);int i; int j;for(i=0;i2;i+)#pragma omp parallel forfor(j=6;j10;j+)printf(i=%d j=%dn,i,j);規(guī)約操作的并行化 常見的規(guī)約操作數(shù)組求和 # pragma omp parallel for private(arx,ary,n) reduction(+:a,b) for（i=0;in;i+） a=a+arxi

56、; b=b+aryi; 運算符運算符數(shù)據(jù)類型數(shù)據(jù)類型默認(rèn)初始值默認(rèn)初始值+整數(shù)，浮點整數(shù)，浮點0*整數(shù)，浮點整數(shù)，浮點1-整數(shù)，浮點整數(shù)，浮點0&整數(shù)整數(shù)所有位都開啟，所有位都開啟，0|整數(shù)整數(shù)0整數(shù)整數(shù)0&整數(shù)整數(shù)1|整數(shù)整數(shù)0循環(huán)嵌套 循環(huán)并行化編譯制導(dǎo)語句可以加在任意一個循環(huán)之前，則對應(yīng)的最近的循環(huán)語句被并行化，其它部分保持不變。 實際上并行化是作用于嵌套循環(huán)中的某一個循環(huán)，其它部分由執(zhí)行到的線程負(fù)責(zé)執(zhí)行。 int i; int j;#pragma omp parallel for private(j)for(i=0;i1;i+)for(j=6;j10;j+)printf

57、(i=%d j=%dn,i,j);int i; int j;for(i=0;i2;i+)#pragma omp parallel forfor(j=6;j10;j+)printf(i=%d j=%dn,i,j);控制數(shù)據(jù)的共享屬性 OpenMP 程序在同一個共享內(nèi)存空間上執(zhí)行，線程通信容易，一個線程寫入一個變量，另一個線程可以讀取這個變量來完成線程間的通信。 控制數(shù)據(jù)的共享屬性 全局變量以及程序代碼都是全局共享的；而動態(tài)分配的堆空間也是共享的。 通過threadprivate來明確指出的某一個數(shù)據(jù)結(jié)構(gòu)屬于線程范圍的全局變量。 OpenMP 允許線程保留自己的私有變量不能讓其它線程訪問到。每一個

58、線程會建立變量的私有拷貝，雖然變量名是相同的，實際上在共享內(nèi)存空間內(nèi)部的位置是不同的。 控制數(shù)據(jù)的共享屬性 數(shù)據(jù)作用域子句用來確定數(shù)據(jù)的共享屬性，有下面以下幾個子句 ： shared用來指示一個變量的作用域是共享的； private用來指示一個變量作用域是私有的； firstprivate 和 lastprivate 分別對私有的變量進(jìn)行初始化的操作和最后終結(jié)的操作， firstprivate 將串行的變量值拷貝到同名的私有變量中，在每一個線程開始執(zhí)行的時候初始化一次。 lastprivate將并行執(zhí)行中的最后一次循環(huán)的私有變量值拷貝到同名的串行變量中； default語句用來改變變量的默認(rèn)私

59、有屬性。 在使用作用域子句的時候要遵循如下的一些規(guī)則 ： 作用域子句作用的變量是已經(jīng)申明的有名變量； 作用域子句在作用到類或者結(jié)構(gòu)的時候，必須作用到類或者結(jié)構(gòu)的整體，而不能只作用于類或者結(jié)構(gòu)的一個部分； 一個編譯指導(dǎo)語句能夠包含多個數(shù)據(jù)作用域子句，但變量只能出現(xiàn)在一個作用域子句中，即變量不能既是共享的，又是私有的； 在語法結(jié)構(gòu)上，作用域子句只能作用在出現(xiàn)在編譯指導(dǎo)語句起作用的語句變量部分。另外，可以將作用域子句作用在類的靜態(tài)變量上。控制數(shù)據(jù)的共享屬性 OpenMP 對默認(rèn)情況下，并行區(qū)中所有的變量都是共享的，但有三種例外情況： 在parallel for循環(huán)中，循環(huán)索引變量是私有的； 并行區(qū)中

60、的局部變量是私有的； 所有在private，firstprivate，lastprivate或reduction子句中列出的變量都是私有的。私有化是通過為每個線程創(chuàng)建各個變量的獨立副本來完成的。控制數(shù)據(jù)的共享屬性 reduction聲明可以看作： 保證了對sum的原則操作 多個線程的執(zhí)行結(jié)果通過reduction中聲明的操作符進(jìn)行計算，以加法操作符為例： 假設(shè)sum的初始值為10，reduction（+: sum）聲明的并行區(qū)域中每個線程的sum初始值為0（規(guī)定），并行處理結(jié)束之后，會將sum的初始化值10以及每個線程所計算的sum值相加。 規(guī)約操作的并行化3.1 體系結(jié)構(gòu)無關(guān)的性能調(diào)優(yōu)方法 獨立于體系結(jié)構(gòu)性能優(yōu)化方法主要有：獨