【文章內(nèi)容簡(jiǎn)介】 tion 把程序當(dāng)中具有共享資源并且對(duì)共享資源進(jìn)行操作的這段程序 ,或者說(shuō)在進(jìn)程中涉及到臨界資源的程序段叫做臨界區(qū) . a=a+1 print(a) a=a1 print(a) P1 P2 P3 If a0 a=a+1。 Else a=a1。 第三章 進(jìn) 程 管 理 2020/11/17 40 程序段 1 程序段 2 程序段 3 共享變量 第三章 進(jìn) 程 管 理 2020/11/17 41 使用臨界區(qū)的原則 有空讓進(jìn) :當(dāng)臨界區(qū)中無(wú)進(jìn)程時(shí) ,任何有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入 無(wú)空等待 :不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū) . 多中選一 :當(dāng)沒(méi)有進(jìn)程在臨界區(qū) ,而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū) , 只能讓其中一個(gè)進(jìn)入臨界區(qū) ,其他進(jìn)程必須等待 . 有限等待 :任何進(jìn)入臨界區(qū)的進(jìn)程要求在有限的時(shí)間內(nèi)得到滿足 . 讓權(quán)等待 :處于等待狀態(tài)的進(jìn)程應(yīng)該放棄占用 CPU,以便使得其他進(jìn)程 有機(jī)會(huì)得到 CPU的使用權(quán) . 第三章 進(jìn) 程 管 理 2020/11/17 42 進(jìn)程互斥的兩種解決方法 .由競(jìng)爭(zhēng)各方平等協(xié)商 .引人一進(jìn)程管理者 ,由管理者來(lái)協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用 . 具體辦法 : 硬件 (當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū) ,就屏蔽所有中斷 ) 軟件 (用編程解決 ,但常常忙等待 ) 第三章 進(jìn) 程 管 理 2020/11/17 43 進(jìn)程互斥的軟件方法 ? 通過(guò)平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟件方法 . ? 軟件方法 [1]: While(free) free=true。 free=false。 臨界區(qū) free:表示臨界區(qū)標(biāo)志 true:有進(jìn)程在臨界區(qū) false:無(wú)進(jìn)程在臨界區(qū) (初值 ) ? 其基本思路：是在進(jìn)入臨界區(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界 區(qū)，則在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志。 ? 問(wèn)題：設(shè)置什么標(biāo)志和如何檢查標(biāo)志。 第三章 進(jìn) 程 管 理 2020/11/17 44 ? 軟件方法 [2]: While( not turn)。 Turn=false 臨界區(qū) turn: true表示 P進(jìn)入臨界區(qū) false表示 Q進(jìn)程臨界區(qū) P: While( turn)。 Turn=true 臨界區(qū) Q: 第三章 進(jìn) 程 管 理 2020/11/17 45 ? 軟件方法 [3]: Pturn=true。 While( qturn)。 Pturn=false 臨界區(qū) Pturn,qturn:初值為 false P進(jìn)入臨界區(qū)的條件 :pturn ∧ not qturn Q進(jìn)入臨界區(qū)的條件 :not Pturn ∧ qturn P: Qturn=true。 While (pturn) Qturn=false 臨界區(qū) Q: 第三章 進(jìn) 程 管 理 2020/11/17 46 例 : 進(jìn)行修改 ... while (flag[1])。 flag[0]=true。 臨界區(qū) 。 flag[0]=false。 進(jìn)程 1 ... while (flag[0])。 flag[1]=true。 臨界區(qū) 。 flag[1]=false。 falg[0] flag[1] ... while (flag[1])。 臨界區(qū) 。 flag[0]=false。 ... while (flag[0])。 臨界區(qū) 。 flag[1]=false。 再進(jìn)行修改 flag[1]=true。 flag[0]=true。 第三章 進(jìn) 程 管 理 2020/11/17 47 ... flag[0]=true。 while (flag[1]) begin flag[0]=false。 wait(5)。 flag[0]=true。 end 臨界區(qū) 。 flag[0]=false。 ... flag[1]=true。 while (flag[0]) begin flag[1]=false。 wait(5)。 flag[1]=true。 end 臨界區(qū) 。 flag[1]=false。 第三章 進(jìn) 程 管 理 2020/11/17 48 ? 軟件方法 [4]:Dekker算法 Pturn,qturn:初值為 false P進(jìn)入臨界區(qū)的條件 :pturn ∧ not qturn Q進(jìn)入臨界區(qū)的條件 :not Pturn ∧ qturn Turn:枚舉類型 ,初值任意 第三章 進(jìn) 程 管 理 2020/11/17 49 While (true) { pturn=true。 while( qturn) { if (turn==2) { pturn=false。 while(turn==2)。 pturn=true。 } } turn=2。 pturn=false。 } 臨界區(qū) P: While (true) { qturn=true。 while( pturn) { if (turn==2) { qturn=false。 while(turn==1)。 qturn=true。 } } turn=1。 qturn=false。 } 臨界區(qū) Q: 第三章 進(jìn) 程 管 理 2020/11/17 50 軟件解決的缺點(diǎn) : ? 忙等待 ? 實(shí)現(xiàn)過(guò)于復(fù)雜 ,需要高的編程技巧 . ? Peterson算法 pturn=true。 turn=2。 while( qturnamp。amp。turn=2)。 Pturn=false 臨界區(qū) P: Qturn=true。 Turn=1。 while (pturnamp。amp。turn=1)。 Qturn=false 臨界區(qū) Q: 第三章 進(jìn) 程 管 理 2020/11/17 51 硬件辦法 [1] ? boolean Ts(boolean *lock) { boolean old。 old=*lock。 *lock=true。 return(old)。 } while Ts (*lock)。 臨界區(qū) lock=false。 “測(cè)試并設(shè)置”指令 第三章 進(jìn) 程 管 理 2020/11/17 52 硬件辦法 [2] Void swap(int *a,int *b) { int temp temp=*a。 *a=*b。 *b=temp。 } key=true。 Do { swap(*lock,key)。 } while(key)。 臨界區(qū) lock=false。 “交換”指令 第三章 進(jìn) 程 管 理 2020/11/17 53 硬件辦法 [3] “開(kāi)關(guān)中斷”指令 進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令 離開(kāi)臨界區(qū)后執(zhí)行：執(zhí)行“開(kāi)中斷”指令 第三章 進(jìn) 程 管 理 2020/11/17 54 進(jìn)程的同步機(jī)制 信號(hào)量及 同步機(jī)制 信號(hào)量及 管程 條件臨界域 路徑表達(dá)式等 (用于集中式系統(tǒng)中 ) 同步機(jī)制應(yīng)滿足的基本要求 1. 描述能力 — 必須能夠詳細(xì)描述出進(jìn)程間這種相互配合以及相互矛盾的關(guān)系 . 2. 可以實(shí)現(xiàn) — 實(shí)現(xiàn)起來(lái)方便 ,這種機(jī)制在一定的機(jī)制或一定的語(yǔ)言上要能夠?qū)嵤?. 3. 效率高 — 不然的話 ,它會(huì)降低系統(tǒng)的并行能力和并行程度 . 4. 使用方便 第三章 進(jìn) 程 管 理 2020/11/17 55 信號(hào)量 (semaphore) 是一個(gè)數(shù)據(jù)結(jié)構(gòu) 。嚴(yán)格說(shuō)來(lái) 它是一個(gè)整型變量 ,能夠刻畫一定程序的狀態(tài) . .信號(hào)量 (semaphore)的定義 struc semaphore { int value。 pointer_pcb queue。 } .信號(hào)量說(shuō)明 Semaphore s。 第三章 進(jìn) 程 管 理 2020/11/17 56 信號(hào)量 ① 互斥的信號(hào)量 : ② 同步的信號(hào)量 : 信號(hào)量的物理意義 ① S0:S表示可用資源的個(gè)數(shù) . ② S=0:S表示無(wú)資源使用 ,也無(wú)等待進(jìn)程 . ③ S0: 表示等待隊(duì)列中進(jìn)程的個(gè)數(shù) S 問(wèn)題 :信號(hào)量的初值不能為負(fù) ,為什么 ? 第三章 進(jìn) 程 管 理 2020/11/17 57 原語(yǔ) :primitive or aic action ? 是由若干機(jī)器指令構(gòu)成的完成某種特定功能的一段程序 ,具有不可 分割性 .即原語(yǔ)的執(zhí)行必須是連續(xù)的 ,在執(zhí)行過(guò)程中不允許被中斷 . 原語(yǔ)實(shí)現(xiàn) :開(kāi)關(guān)中斷 1. 必須置一次且只能設(shè)一次初值 2. 初值不能為負(fù)數(shù) 3. 修改信號(hào)量的值只能由 . 信號(hào)量的使用原則 : 第三章 進(jìn) 程 管 理 2020/11/17 58 / *原語(yǔ) ? P(s) ? { =。 ? if (0) ? { 該進(jìn)程狀態(tài)置為等待態(tài) ? 將該進(jìn)程的 PCB插入相應(yīng)的等待隊(duì)列未尾 。 ? } ? } ? V(s) ? { =+1。 ? if (=0) ? { 喚醒相應(yīng)等待隊(duì)列 ? 改變其狀態(tài)為就緒態(tài) . ? 并將其插入就緒隊(duì)列 . ? } ? } 第三章 進(jìn) 程 管 理 2020/11/17 59 P(mutex) V(mutex) 臨界區(qū) P(mutex) V(mutex) 臨界區(qū) P(mutex) V(mutex) 臨界區(qū) P1 P2 P3 用 第三章 進(jìn) 程 管 理 2020/11/17 60 A和 B共享一臺(tái)打印機(jī) A進(jìn)程 B進(jìn)程 … 打印 … 互斥的例子 : P(s) V(s) … 打印 … P(s) V(s) S=1 第三章 進(jìn) 程 管 理 2020/11/17 61 互斥的例子 : 2. 4個(gè)進(jìn)程 A、 B、 C、 D共享 2臺(tái)打印機(jī) A進(jìn)程 B進(jìn)程 C進(jìn)程 B進(jìn)程 初值 : S=2