【文章內(nèi)容簡介】 系統(tǒng)|進程管理 48 ?互斥 ?不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為互斥。 ?臨界區(qū)調(diào)度原則 ?空閑讓進 ?忙則等待 ?有限等待 ?讓權(quán)等待 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 49 ? 互斥的軟件實現(xiàn) 算法 1: 進程 Pi， Pj共享臨界資源 R。 Turn：進程編號。 ? 算法 1： 共享一個公用整型變量 turn void Pi() { …… while (true) { while (turn != i )。 //資源被 j進程用 ， 空轉(zhuǎn) critical section turn = j。 //把資源控制權(quán)交給 j remainder section } } 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 50 ?算法 2： 用數(shù)組代替算法一中的 turn int flag [n] ={0,0… ,0}。 void Pi() { while (true) { for (j=0。jn。j++) if (flag[j]) j=0。 //資源被用 ， 空轉(zhuǎn) flag[i] = 1 。 //讓 i 進程獲得資源 critical section flag[i] = 0 。 //放棄資源控制權(quán) remainder section } } 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 51 ?算法 3： int flag [n] ={0,0… ,0}。 void Pi() { while (true) { flag[i] = 1 。 for (j=0。jn。 j++) if (flag[j]) j=0。 critical section flag[i] = 0 。 remainder section } } 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 52 ?算法 4： 進程共享兩個公用變量 boolean [] flag = new boolean [2]。 int turn =0。 public void P0() { while (true) { flag [0] = true。 turn = 1。 while (flag [1] amp。amp。 turn == 1)； critical section 。 flag [0] = false。 remainder 。 } } public void P1() { while (true) { flag [1] = true。 turn = 0。 while (flag [0] amp。amp。 turn == 0)。 critical section 。 flag [1] = false。 remainder ； } } 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 53 public static void main() { flag [0] = false。 flag [1] = false。 parbegin (P0, P1)。 } 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 54 ?算法 5：對臨界區(qū) S設(shè)置一個變量狀態(tài) W，W=0表示資源可用， W=1表示資源已被占用。 例： Begin integer W = 0 。 Cogegin Begin L1： lock W。 CS1。 Unlock W。 Remainder of process 1。 Goto L1。 End Begin L2： lock W。 CS2。 Unlock W。 Remainder of process 2。 Goto L2。 End Coend End 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 55 ?關(guān)鎖原語 lock W： if W = 1 then begin block(n)。 insert(WL,n)。 scheduler。 end else W = 1。 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 56 ?開鎖原語 unlock W： if WL NULL then begin remove(WL,q)。 status(q) = ―ready‖。 insert(RL,q)。 end else W = 0。 進程同步 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 57 信號量機制及其應(yīng)用 ?整型信號量機制 ?信號量 (sem) sem=0: 表示可供并發(fā)進程使用的資源實體的個數(shù) sem0: 表示正在等待使用臨界區(qū)的進程數(shù) 。 Sem的值只能由 P、 V操作改變 。 P： wait ( s ) V： signal (s ) 按信號量數(shù)值分為二元信號量和一般信號量 。 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 58 ?Wait（ P）和 signal（ V）原語 ?Wait(s) 原語 struct semaphore { int count。 QueueType Queue。 } void wait(s) { 。 if ( 0) { place this process in 。 block this process。 } } 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 59 ?signal原語 void signal(s) { ++。 if ( = 0) { remove a process P from 。 place process P on ready list。 } } 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 60 ?利用信號量實現(xiàn)互斥 public class mutualexclusion { static final int n = number of processes。 semaphore s = new semaphore (1)。 public void P(int i) { while (true) { wait(s)。 critical section 。 signal(s)。 remainder 。 } } public static void main() { parbegin (P(1), P(2), . . ., P(n))。 } } 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 61 ?利用信號量描述前趨關(guān)系 P1： S1 P2： S2 S1—— S2 則設(shè)置信號量 s=0， P1： S1； signal(s)； P2： Wait(s)； S2； 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 62 1 2 3 4 5 6 7 a b c d e f g h 例：根據(jù)前趨圖寫出可并發(fā)執(zhí)行的程序： 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 63 var a,b,c,d,e,f,g,h:semaphore := 0,0,0,0,0,0,0,0。 begin parbegin begin S1。signal(a)。 signal(b)。 signal(c)。 end begin wait(a)。 S2。 signal(d)。 end begin wait(b)。 S3。 signal(e)。 end begin wait(c)。 S4。 signal(f)。 end begin wait(d)。 S5。 signal(g)。 end begin wait(e)。 wait(f)。 S6 。 signal( h)。 end begin wait(g)。 wait(h)。 S7。 end parend end 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 64 ?信號量集機制 ?AND型信號量集機制 ?問題引入 進程 A、 B訪問共享數(shù)據(jù) D和 E 信號量 Dmutex=1， Emutex=1 process A : wait(Dmutex) 。 wait(Emutex) 。 process B : wait(Emutex) 。 wait(Dmutex) 。 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 65 A、 B交替執(zhí)行： process A : wait(Dmutex) 。 則 Dmutex = 0 process B : wait(Emutex) 。 則 Emutex = 0 process A : wait(Emutex) 。 則 Emutex = 1， 阻塞 process B : wait(Dmutex) 。 則 Dmutex = 1， 阻塞 發(fā)生死鎖 。 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 66 ?AND同步機制的思想 Swait(S1,S2,… ,Sn) { if (S1=1 amp。amp。 S2=1 amp。amp。 … amp。amp。 Sn=1) for (i=1。i= n。i++) Si 。 else { 將進程插入第 i（ Si1） 個等待隊列 。 設(shè)置該進程的程序計數(shù)器到 Swait操作的開始 。 } } 信號量機制及其應(yīng)用 CUIT 葉斌 2022/2/5 20:24 操作系統(tǒng)|進程管理 67 Ssignal(S1,S2,… ,Sn)