【正文】 者，一個(gè)消費(fèi)者，公用 n個(gè)環(huán)形緩沖區(qū) – 多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，公用 n個(gè)環(huán)形緩沖區(qū) ? 桌上有一空盤，允許存放一只水果。 Wakeup(P)。 } } V(S) { //V操作的定義 ++。 if(0) { 加本線程到 。 V(mutex)。 ? V: Verhogen，意味著增加 – V操作對(duì)信號(hào)量的值加 1，并喚醒那些等待的進(jìn)線程 ?信號(hào)量的物理含義 ? 當(dāng)信號(hào)量 0時(shí)，表示有 ? 當(dāng)信號(hào)量 =0時(shí)，表示所有資源被用，但無(wú)線程等待 ? 當(dāng)信號(hào)量 0時(shí)，表示所有資源被用，且還有||個(gè)線程在等待資源P(mutex)。 ? 活鎖 ? 忙等待的時(shí)候發(fā)生的饑餓 ? 鎖的粒度 ? 鎖的粒度是上鎖后保護(hù)的共享數(shù)據(jù)的多少 ? 減小鎖的粒度可以提高對(duì)共享數(shù)據(jù)訪問(wèn)的并行性 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 37 互斥與同步 ? 同步原語(yǔ) ?信號(hào)量 ?信號(hào)量可以表示為一個(gè)整數(shù)，并且被兩個(gè)基本原語(yǔ)操作所界定 : ? P: Proberen，意味著測(cè)試。如果等待是永久的，那就是 餓死 。 ? (3)當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí) ,對(duì)顧客的貸款可推遲支付 ,但總能使顧客在有限的時(shí)間里得到貸款 。進(jìn)程P3總共需要 4個(gè)資源 ,第一次請(qǐng)求 2個(gè)， 1）這樣請(qǐng)求后，系統(tǒng)安全嗎？ 2）如果接著 P1第二次申請(qǐng) 1個(gè)，能給它嗎？ ?銀行家算法 ? (1)當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就可接納該顧客 。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 35 互斥與同步 ? 死鎖 ? 死鎖的避免 ?一個(gè)進(jìn)程序列 {P1,…Pn}是安全的 ,如果對(duì)于其中每一個(gè)進(jìn)程Pi(1=i=n),它以后尚需要的資源量不超過(guò)系統(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è) 。 ?破壞“不可搶占”條件 ? 允許對(duì)資源實(shí)行搶奪。 – 創(chuàng)建進(jìn)程時(shí)，要求它申請(qǐng)所需的全部資源。但一般來(lái)說(shuō)“互斥”條件是無(wú)法破壞的。 ?資源分配不當(dāng)?shù)取? ?產(chǎn)生死鎖的原因主要是： ?因?yàn)橄到y(tǒng)資源不足。 ?舉例 : 圖書館 ?一個(gè)顧客借了一本書 ?其他人必須等著書被還回來(lái) 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 32 互斥與同步 ? 柵障同步 ?如果多個(gè)線程在繼續(xù)向下執(zhí)行前，需要完成各自任務(wù)并達(dá)到某個(gè)新起點(diǎn)，則在此點(diǎn)設(shè)置柵障 ?是用來(lái)確保在柵障之前代碼段做的修改在線程要越過(guò)柵障繼續(xù)執(zhí)行前全部完成。 x=t+1 隱含的數(shù)據(jù)競(jìng)爭(zhēng) 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 30 互斥與同步 ? 互斥 ?臨界區(qū) ?是代碼中訪問(wèn)（讀和寫）共享變量的那部分代碼 ?多個(gè)線程訪問(wèn)同一個(gè)臨界區(qū)的原則： ? 一次最多只能一個(gè)線程停留在臨界區(qū)內(nèi) ? 不能讓一個(gè)線程無(wú)限地停留在臨界區(qū)內(nèi)，否則其他線程將不能進(jìn)入該臨界區(qū) ?互斥 ?線程互斥 是指對(duì)于共享資源，在各線程訪問(wèn)時(shí)的排它性 ?舉例：銀行的保管箱 ?維護(hù)人員確?；コ? 進(jìn)入?yún)^(qū) 退出區(qū) 臨界區(qū) 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 31 互斥與同步 ? 同步 ?線程同步 是指線程之間所具有的一種制約關(guān)系，一個(gè)線程的執(zhí)行依賴另一線程的消息，當(dāng)它沒(méi)有得到另一個(gè)線程的消息時(shí)應(yīng)該等待，直到消息到達(dá)時(shí)才被喚醒 ?使用同步對(duì)象來(lái)確?；コ?: ?信號(hào)量、互斥量、條件變量、讀 /寫鎖、事件和柵障。 ?更好的資源利用 ?線程甚至可以減少單核處理器的延遲。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 24 線程的設(shè)計(jì) ? 任務(wù)分解（客戶 /服務(wù)器編程模式） ? 數(shù)據(jù)分解（工作組編程模式） ? 數(shù)據(jù)流分解（流水線編程模式） 分解 設(shè)計(jì) 評(píng)論 任務(wù)分解 不同的工作安排不同的線程 常見(jiàn)于有幾個(gè)獨(dú)立的功能的應(yīng)用 數(shù)據(jù)分解 多個(gè)線程針對(duì)數(shù)據(jù)的不同部分執(zhí)行相同的操作 常見(jiàn)于音頻處理、圖像處理和科學(xué)計(jì)算程序中 數(shù)據(jù)流分解 一個(gè)線程的輸出是第二個(gè)線程的輸入 特別注意需要消除啟動(dòng)和關(guān)閉延遲的情況 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 25 線程的設(shè)計(jì) ? 線程化的好處 : ?提高性能 ?能夠使用多核處理器 ?線程共享數(shù)據(jù)會(huì)比較快，因?yàn)樗麄児蚕硐嗤刂房臻g。 ?一個(gè)侍者擺放器皿 ? 湯匙、刀子和叉子 ?一個(gè)侍者放玻璃杯 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 23 線程的設(shè)計(jì) ? 為了吞吐量而線程化 ?在固定的時(shí)間內(nèi)完成最多的任務(wù) ?舉例：安排一個(gè)飯局時(shí)候的不同任務(wù)： ?對(duì)多個(gè)侍者的安排： ? 每個(gè)桌子安排一個(gè)侍者。 ?一個(gè)侍者折疊和放置餐巾。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 21 線程的設(shè)計(jì) ? 為性能而線程化 ?通過(guò)將執(zhí)行在并行環(huán)境下的大量的計(jì)算分解開(kāi)來(lái)進(jìn)行應(yīng)用程序的并行化，能夠提高計(jì)算的性能。 多核結(jié)構(gòu)與程序設(shè)計(jì) Southeast University 東 南 大 學(xué) 20 線程的設(shè)計(jì) ? 為功能而線程化 ?舉例 : ?為了簡(jiǎn)化代碼，為下列部分設(shè)計(jì)不同的線程 ? 輸入、圖形用戶界面、計(jì)算和輸出。 ?在一個(gè)應(yīng)用程序中控制并發(fā)功能的執(zhí)行是比較容易的。 ?終止（ terminated