【正文】 硬件資源的開銷 ? 頻繁切換進(jìn)程或線程容易引起 Cache顛簸 ? 切換線程本身有代價(jià) ?有用的嘗試 ?運(yùn)行的線程數(shù)量最好低于等于硬件線程數(shù) ?用 OpenMP來做工作 ?使用線程池 ?任務(wù)竊取 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 45 并行程序設(shè)計(jì)的常見問題 ? 競(jìng)爭(zhēng)激烈的鎖 ?優(yōu)先級(jí)倒置 ?如果不是資源搶占式優(yōu)先級(jí)，則有可能一個(gè)低優(yōu)先級(jí)的線程占用了鎖，而高優(yōu)先級(jí)的線程等待并可能錯(cuò)過臨界期限。 mutex unlock()。 sum=sun+1。也就是說鎖實(shí)際上是特殊的信號(hào)量，其資源只有 1個(gè)。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 39 互斥與同步 ? 同步原語 ?信號(hào)量 ?信號(hào)量用于同步 ? 生產(chǎn)者 消費(fèi)者問題（緩沖區(qū)為空，消費(fèi)者不能再消費(fèi)，緩沖區(qū)為滿，生產(chǎn)者不能再生產(chǎn)） – 一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，公用一個(gè)緩沖區(qū) – 一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，公用 n個(gè)環(huán)形緩沖區(qū) – 多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，公用 n個(gè)環(huán)形緩沖區(qū) ? 桌上有一空盤，允許存放一只水果。 } } V(S) { //V操作的定義 ++。 V(mutex)。 ? 活鎖 ? 忙等待的時(shí)候發(fā)生的饑餓 ? 鎖的粒度 ? 鎖的粒度是上鎖后保護(hù)的共享數(shù)據(jù)的多少 ? 減小鎖的粒度可以提高對(duì)共享數(shù)據(jù)訪問的并行性 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 37 互斥與同步 ? 同步原語 ?信號(hào)量 ?信號(hào)量可以表示為一個(gè)整數(shù)，并且被兩個(gè)基本原語操作所界定 : ? P: Proberen，意味著測(cè)試。 ? (3)當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí) ,對(duì)顧客的貸款可推遲支付 ,但總能使顧客在有限的時(shí)間里得到貸款 。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 35 互斥與同步 ? 死鎖 ? 死鎖的避免 ?一個(gè)進(jìn)程序列 {P1,…Pn}是安全的 ,如果對(duì)于其中每一個(gè)進(jìn)程Pi(1=i=n),它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程 Pj(ji)當(dāng)前占有資源量之和 ? 現(xiàn)有 12個(gè)資源供 3個(gè)進(jìn)程共享 ,進(jìn)程 P1總共需要 9個(gè)資源 ,但第一次先申請(qǐng) 2個(gè) 。 – 創(chuàng)建進(jìn)程時(shí)，要求它申請(qǐng)所需的全部資源。 ?資源分配不當(dāng)?shù)取? ?舉例 : 圖書館 ?一個(gè)顧客借了一本書 ?其他人必須等著書被還回來 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 32 互斥與同步 ? 柵障同步 ?如果多個(gè)線程在繼續(xù)向下執(zhí)行前，需要完成各自任務(wù)并達(dá)到某個(gè)新起點(diǎn)，則在此點(diǎn)設(shè)置柵障 ?是用來確保在柵障之前代碼段做的修改在線程要越過柵障繼續(xù)執(zhí)行前全部完成。 ?更好的資源利用 ?線程甚至可以減少單核處理器的延遲。 ?一個(gè)侍者擺放器皿 ? 湯匙、刀子和叉子 ?一個(gè)侍者放玻璃杯 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 23 線程的設(shè)計(jì) ? 為了吞吐量而線程化 ?在固定的時(shí)間內(nèi)完成最多的任務(wù) ?舉例：安排一個(gè)飯局時(shí)候的不同任務(wù)： ?對(duì)多個(gè)侍者的安排： ? 每個(gè)桌子安排一個(gè)侍者。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 21 線程的設(shè)計(jì) ? 為性能而線程化 ?通過將執(zhí)行在并行環(huán)境下的大量的計(jì)算分解開來進(jìn)行應(yīng)用程序的并行化，能夠提高計(jì)算的性能。 ?在一個(gè)應(yīng)用程序中控制并發(fā)功能的執(zhí)行是比較容易的。 ?運(yùn)行（ running）：線程正在被執(zhí)行。 ?當(dāng)一個(gè)線程因調(diào)用系統(tǒng)調(diào)用被阻塞時(shí)，整個(gè)進(jìn)程被阻塞 ?一對(duì)一模型 ?把每個(gè)用戶級(jí)線程影射到一個(gè)內(nèi)核級(jí)線程。 它是操作系統(tǒng)能夠調(diào)度的最小單元 ? 進(jìn)程中可以只有一個(gè)線程串行執(zhí)行，也可以是多個(gè)線程共享資源下并行執(zhí)行。多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 1 東南大學(xué)成賢學(xué)院計(jì)算機(jī)系 多核結(jié)構(gòu)與程序設(shè)計(jì) 楊全勝 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 2 進(jìn)程、線程和并行程序設(shè)計(jì) ? 內(nèi)容 ?進(jìn)程的概念 ?什么是線程 ?線程的設(shè)計(jì) ?互斥與同步 ?并行程序設(shè)計(jì)的常見問題 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 3 進(jìn)程的概念 ? 現(xiàn)代操作系統(tǒng)以進(jìn)程的形式來加載程序 ?進(jìn)程是程序的一次動(dòng)態(tài)執(zhí)行 ?進(jìn)程是資源的擁有者 ? 進(jìn)程是一個(gè)四元組 (P,C,D,S) ?P程序代碼 ?C進(jìn)程控制狀態(tài) ?D進(jìn)程的數(shù)據(jù) ?S進(jìn)程的執(zhí)行狀態(tài) ? 進(jìn)程的特征 ?資源特征，包括程序執(zhí)行所必需的計(jì)算資源 ?執(zhí)行特征，包括在進(jìn)程執(zhí)行過程中動(dòng)態(tài)改變的特征 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 4 進(jìn)程的概念 ? 進(jìn)程的狀態(tài) 非存在 狀態(tài) 就緒狀態(tài) 運(yùn)行狀態(tài) 退出狀態(tài) 掛起狀態(tài) 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 5 進(jìn)程的概念 ? 進(jìn)程間的通信 ?現(xiàn)代操作系統(tǒng)提供基本的系統(tǒng)調(diào)用函數(shù)，允許位于同一臺(tái)處理機(jī)或不同處理機(jī)的多個(gè)進(jìn)程之間相互交流信息 ?表現(xiàn)形式 ? 通信 ? 同步 ? 聚集（歸約） ?實(shí)現(xiàn)方法 ?在共享存儲(chǔ)模式下，通信可以通過操作系統(tǒng)讀 /寫共享緩存來實(shí)現(xiàn)。 ?線程能在進(jìn)程內(nèi)創(chuàng)建其他線程 ?每個(gè)線程有它自己