【文章內(nèi)容簡介】 彼此競爭 ? 雖設(shè)定了執(zhí)行順序，但是不能保證就按照這個順序執(zhí)行，而結(jié)果卻由執(zhí)行的順序決定 ? 是并發(fā)程序中最常見的錯誤（與時間有關(guān)的錯誤） . ? 數(shù)據(jù)競爭 ? 指存儲器訪問沖突的情況 ? 多個線程并發(fā)訪問同一個存儲單元時，至少有一個線程要改變那個單元的值，就會出現(xiàn)數(shù)據(jù)競爭 ? 引發(fā)兩種可能的沖突 : ? 讀 /寫沖突 ? 寫 /寫沖突 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 29 互斥與同步 ? 數(shù)據(jù)競爭 線程 1 線程 2 t=x x=t+1 u=x x=u+2 如果一開始 x=0，那么結(jié)束的時候 x=? 線程 1 線程 2 x+=1 x+=2 a[i]+=1 a[j]+=1 *p+=1 *q+=1 Foo(1) Foo(2) add [edi],1 add [edi],2 注意 : x+=1 編譯成 t=x。 x=t+1 隱含的數(shù)據(jù)競爭 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 30 互斥與同步 ? 互斥 ?臨界區(qū) ?是代碼中訪問（讀和寫）共享變量的那部分代碼 ?多個線程訪問同一個臨界區(qū)的原則： ? 一次最多只能一個線程停留在臨界區(qū)內(nèi) ? 不能讓一個線程無限地停留在臨界區(qū)內(nèi)，否則其他線程將不能進(jìn)入該臨界區(qū) ?互斥 ?線程互斥 是指對于共享資源，在各線程訪問時的排它性 ?舉例：銀行的保管箱 ?維護(hù)人員確?；コ? 進(jìn)入?yún)^(qū) 退出區(qū) 臨界區(qū) 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 31 互斥與同步 ? 同步 ?線程同步 是指線程之間所具有的一種制約關(guān)系，一個線程的執(zhí)行依賴另一線程的消息，當(dāng)它沒有得到另一個線程的消息時應(yīng)該等待，直到消息到達(dá)時才被喚醒 ?使用同步對象來確?；コ?: ?信號量、互斥量、條件變量、讀 /寫鎖、事件和柵障。 ? 一個線程獲得同步對象，其他線程必須等待 ? 當(dāng)獲得同步對象的線程完成，釋放對象，將對象給等待的線程。 ?舉例 : 圖書館 ?一個顧客借了一本書 ?其他人必須等著書被還回來 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 32 互斥與同步 ? 柵障同步 ?如果多個線程在繼續(xù)向下執(zhí)行前，需要完成各自任務(wù)并達(dá)到某個新起點(diǎn)，則在此點(diǎn)設(shè)置柵障 ?是用來確保在柵障之前代碼段做的修改在線程要越過柵障繼續(xù)執(zhí)行前全部完成。 ?線程在柵障的地方暫停 ?當(dāng)所有的線程到達(dá)柵障的時候，所有線程被釋放繼續(xù)執(zhí)行 ?舉例：跑步 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 33 互斥與同步 ? 死鎖 ?當(dāng)兩個線程因為互相等待被對方擁有并且不會釋放的資源而被阻塞的時候，會發(fā)生死鎖。 ?產(chǎn)生死鎖的原因主要是： ?因為系統(tǒng)資源不足。 ?進(jìn)程運(yùn)行推進(jìn)的順序不合適。 ?資源分配不當(dāng)?shù)取? ?死鎖的四個必要條件 : ?互斥條件 ?請求與保持條件 ?不可剝奪條件 ?循環(huán)等待條件 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 34 互斥與同步 ? 死鎖 ?死鎖的預(yù)防 ?破壞 “互斥”條件 ? 在系統(tǒng)里取消互斥。但一般來說“互斥”條件是無法破壞的。 ?破壞“請求與保持”條件 ? 不允許進(jìn)程在已獲得某種資源的情況下，申請其他資源。 – 創(chuàng)建進(jìn)程時，要求它申請所需的全部資源。 – 要求每個進(jìn)程提出新的資源申請前，釋放它所占有的資源。 ?破壞“不可搶占”條件 ? 允許對資源實(shí)行搶奪。 ?破壞“循環(huán)等待”條件 ? 將系統(tǒng)中的所有資源統(tǒng)一編號，進(jìn)程可在任何時刻提出資源申請，但所有申請必須按照資源的編號順序（升序）提出。 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 35 互斥與同步 ? 死鎖 ? 死鎖的避免 ?一個進(jìn)程序列 {P1,…Pn}是安全的 ,如果對于其中每一個進(jìn)程Pi(1=i=n),它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程 Pj(ji)當(dāng)前占有資源量之和 ? 現(xiàn)有 12個資源供 3個進(jìn)程共享 ,進(jìn)程 P1總共需要 9個資源 ,但第一次先申請 2個 。進(jìn)程 P2總共需要 10個資源 .第一次申請 5個 。進(jìn)程P3總共需要 4個資源 ,第一次請求 2個， 1）這樣請求后，系統(tǒng)安全嗎？ 2）如果接著 P1第二次申請 1個，能給它嗎？ ?銀行家算法 ? (1)當(dāng)一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客 。 ? (2) 顧客可以分期貸款 ,但貸款的總數(shù)不能超過最大需求量 。 ? (3)當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時 ,對顧客的貸款可推遲支付 ,但總能使顧客在有限的時間里得到貸款 。 ? (4) 當(dāng)顧客得到所需的全部資金后 ,一定能在有限的時間里歸還所有的資金 . 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 36 互斥與同步 ? 餓死 ? 當(dāng)一個線程正在等一個資源而該資源被其他線程擁有，但由于某種原因這個資源永遠(yuǎn)不能被這個線程使用的時候，發(fā)生 饑餓 （但沒死鎖）。如果等待是永久的，那就是 餓死 。 ? 舉例 ?在使用小文件優(yōu)先的打印系統(tǒng)中一個大文件請求打印。 ? 活鎖 ? 忙等待的時候發(fā)生的饑餓 ? 鎖的粒度 ? 鎖的粒度是上鎖后保護(hù)的共享數(shù)據(jù)的多少 ? 減小鎖的粒度可以提高對共享數(shù)據(jù)訪問的并行性 多核結(jié)構(gòu)與程序設(shè)計 Southeast University 東 南 大 學(xué) 37 互斥與同步 ? 同步原語 ?信號量 ?信號量可以表示為一個整數(shù)，并且被兩個基本原語操