進(jìn)程互斥詳解.ppt

1、3.5 進(jìn)程互斥,互斥:兩個(gè)或兩個(gè)以上的進(jìn)程，由于不能同時(shí)使用同一臨界資源，只能是一個(gè)進(jìn)程使用完，另一個(gè)進(jìn)程才能使用。這種現(xiàn)象稱為進(jìn)程互斥。,返回,3.5.1 資源共享所引起的制約 3.5.2 互斥的加鎖實(shí)現(xiàn) 3.5.3 信號(hào)量(semaphore)與 PV原語 3.5.4 用PV原語實(shí)現(xiàn)進(jìn)程互 斥,3.5.1 資源共享引起的制約,3.5.1.1臨界資源 3.5.1.2臨界區(qū)的訪問過程 3.5.1.3進(jìn)程互斥的軟件方法 4.5.1.4進(jìn)程互斥的硬件方法,3.5.1.1臨界資源,多道程序環(huán)境進(jìn)程之間存在資源共享，進(jìn)程的運(yùn)行時(shí)間受影響 臨界資源：把一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。,進(jìn)程間

2、資源訪問沖突 共享變量的修改沖突 操作順序沖突 進(jìn)程間的制約關(guān)系 間接制約：進(jìn)行競(jìng)爭獨(dú)占分配到的部分或全部共享資源，“互斥” 直接制約：進(jìn)行協(xié)作等待來自其他進(jìn)程的信息，“同步”,共享變量的修改沖突,舉例：共享變量x,3.5.1.2臨界區(qū)的訪問過程,臨界區(qū),各進(jìn)程對(duì)于臨界區(qū)資源的操作必須互斥， 互斥執(zhí)行的程序段為臨界區(qū)(critical section),臨界區(qū)(critical section)：進(jìn)程中訪問臨界資源的一段代碼。 進(jìn)入?yún)^(qū)(entry section)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)正在訪問臨界區(qū)標(biāo)志 退出區(qū)(exit sectio

3、n)：用于將正在訪問臨界區(qū)標(biāo)志清除。 剩余區(qū)(remainder section)：代碼中的其余部分。,3.5.1.3進(jìn)程互斥的軟件方法,有兩個(gè)進(jìn)程Pi, Pj，其中的Pi , Pj,算法1：單標(biāo)志,設(shè)立一個(gè)公用整型變量 s：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí) 在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：turn為i時(shí)，進(jìn)程Pi可進(jìn)入； 在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識(shí)：進(jìn)程Pi退出時(shí)，改turn為進(jìn)程Pj的標(biāo)識(shí)j；,缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；,3.5.2互斥的加鎖實(shí)現(xiàn),當(dāng)某個(gè)進(jìn)程進(jìn)入臨界區(qū)后，它

4、將鎖上臨界區(qū)，直到它退出臨界區(qū)為止。 Lock(keys) /keys=0 加鎖 臨界區(qū) Unlock(keys) /keys=1解鎖,3.5.3 信號(hào)量(semaphore),4.4.2.1 信號(hào)量和P、V原語 4.4.2.2 信號(hào)量集,前面的互斥算法都存在問題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，需要一個(gè)地位高于進(jìn)程的管理者來解決公有資源的使用問題。OS可從進(jìn)程管理者的角度來處理互斥的問題，信號(hào)量就是OS提供的管理公有資源的有效手段。 信號(hào)量代表可用資源實(shí)體的數(shù)量。,信號(hào)量和P、V原語,1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)increm

5、ent(verhogen)），是一種卓有成效的進(jìn)程同步機(jī)制。,每個(gè)信號(hào)量s除一個(gè)整數(shù)值s.count（計(jì)數(shù)）外，還有一個(gè)進(jìn)程等待隊(duì)列s.queue，其中的s是阻塞在該信號(hào)量的各個(gè)進(jìn)程的標(biāo)識(shí) 信號(hào)量只能通過初始化和兩個(gè)標(biāo)準(zhǔn)的原語來訪問作為OS核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷 初始化指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)（又稱為資源信號(hào)量）若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對(duì)值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù) 二進(jìn)制信號(hào)量(binary semaphore)：只允許信號(hào)量取0或1值,1. P原語wait(s),-s.count;/-1表示申請(qǐng)一個(gè)資源; if (s.count 0)/表示沒有空閑

6、資源; 調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.queue; 阻塞調(diào)用進(jìn)程; ,用消息wait(消息名）等待合作進(jìn)程發(fā)來消息,2. V原語signal(s),+s.count;/+1表示釋放一個(gè)資源； if (s.count = 0)/表示有進(jìn)程處于阻塞狀態(tài)； 從等待隊(duì)列s.queue中取出一個(gè)進(jìn)程P; 進(jìn)程P進(jìn)入就緒隊(duì)列; ,V原語通常喚醒進(jìn)程等待隊(duì)列中的頭一個(gè)進(jìn)程 用消息signal(消息名）表示向合作進(jìn)程發(fā)去消息,3.5.4 利用信號(hào)量實(shí)現(xiàn)互斥,為臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex(MUTual Exclusion)，其初值為1；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間 必須成對(duì)使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進(jìn)程）；P、V原語不能次序錯(cuò)誤、重復(fù)或遺漏,互斥模型: 進(jìn)程P1 進(jìn)程P2 P(S) P(S) S1 S2 V(S) V(S) 其中信號(hào)量初值:S=1；S1、S2為兩個(gè)互斥程序段。,并發(fā)進(jìn)程之間存在相互制約關(guān)系 “同步“ 進(jìn)程P1 : 進(jìn)程P2: L1:P(S) L2:V(S) 信號(hào)量初值:S=0,進(jìn)程P1 Y:=1; Y:=y+2; V(s1); Z:=y+1; P(s2); Y:=z+y;,進(jìn)程P2 x:=1; x:=x+1; p(s1);