【正文】 4. For(j=0。jn。j++){ 5. While (choosing[j]) skip。 6. While (number[j]!=0)and 7. (number[j],j)(number[i],i) skip。 8. } Lamport面包店算法 (Cont.) Pi離開 ： number[i]=0： 臨界區(qū)操作 滿足臨界區(qū)管理原則 ? 互斥性 (mutual exclusion) ? 多個進(jìn)程競爭進(jìn)入臨界區(qū)時 , 下述條件之一成立 : (1)一個進(jìn)程抓到最小號 , (2)若干進(jìn)程抓到最小號 . 情形 (1)抓到最小號的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) 。 情形 (2)編號最小抓到最小號的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 其它進(jìn)程將在第一個 while循環(huán)或第二個 while循環(huán)處等待 , 因而滿足互斥性 . ? 進(jìn)展性 (progress) ? 當(dāng)僅有一個進(jìn)程想進(jìn)入臨界區(qū)時 , 該進(jìn)程可以立即進(jìn)入 。 當(dāng)有多個進(jìn)程想進(jìn)入臨界區(qū)時其二元組 (number[i],i)最小的進(jìn)程獲準(zhǔn)進(jìn)入 , 因而確定進(jìn)入臨界區(qū)進(jìn)程的決策將在有限時間內(nèi)確定 . ? 有限等待性 (bounded waiting) ? 對任意一個想要進(jìn)入臨界區(qū)的進(jìn)程 Pi, 設(shè)其抓到號碼為number[i], 按二元組 (number[i],i)次序排在 Pi之前的競爭進(jìn)程數(shù)量是有限的 , 在最壞情況下 Pi將等待 n1個排在其前面的進(jìn)程進(jìn)入并離開臨界區(qū)后獲得進(jìn)入臨界區(qū)的資格 , 因而滿足有限等待性 . 滿足臨界區(qū)管理原則 ? 互斥性 ? 僅當(dāng) flag[i]==in_cs, 且對所有 j!=i, flag[j]!=in_cs時 , 進(jìn)程 Pi才進(jìn)入臨界區(qū)域 , 因而滿足互斥性 . ? 進(jìn)展性 ? 臨界區(qū)空閑時 , 排在序列 turn, turn+1, … , n1,0,1, 2,… ,turn1最前面的申請進(jìn)入臨界區(qū)的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū) , 因而滿足進(jìn)展性 . ? 有限等待性 ? 進(jìn)程離開臨界區(qū)時 ,按循環(huán)次序 turn+1, … , n1,0,1, 2,… ,turn1確定唯一一個競爭進(jìn)程為其后繼 , 所以一個進(jìn)程最多等待 n1個進(jìn)程進(jìn)入并離開臨界區(qū)后一定能進(jìn)入臨界區(qū) , 因而滿足有限等待性 . 進(jìn)程互斥的硬件實(shí)現(xiàn) 1. 硬件提供“測試并建立”指令 int test_and_set(int amp。target){ test_and_set=target。 *target=1。 }. 對一組公共變量， int lock。（初始 =0)。 Pi進(jìn)入： While test_and_set(amp。lock)。 Pi離開： lock=0。 滿足互斥性，進(jìn)展性，不滿足有限等待性。 進(jìn)程互斥的硬件實(shí)現(xiàn) 滿足有限等待性： 全局變量： int waiting[n]。 int lock。 局部變量： int j。 int key。 waiting[i]=1。 key=1。 While(waiting[i]amp。amp。key) key=test_and_set(amp。lock)。 waiting[i]=0。 臨界區(qū) J=(i+1)%n。 While(((j!=i)amp。amp。(!waiting[j])) j=(j+1)%n。 If(j==i) lock=0。 Else waiting[j]=0。 其余部分 進(jìn)程互斥的硬件實(shí)現(xiàn) 2. 硬件提供“交換”指令 void swap(int amp。a,amp。b:boolean){ int temp: boolean。 temp:=*a。 *a:=*b。 *b:=temp。 }。 對 一組公共變量 ： int lock (初始 =0)。 對一個進(jìn)程空間 ： int key。 Pi進(jìn)入 ： key=1。 do swap(amp。lock,amp。key) while (key==1)。 Pi離開 ： lock=0。 Remarks： (1) test_and_set指令和 swap指令是原子的，不可中斷的 (在單 CPU情況下 )。 (2) test_and_set實(shí)際上是：將內(nèi)存中一個單元的內(nèi)容取出，再送一個新值。 (3) swap實(shí)際上是：交換內(nèi)存兩個單元的內(nèi)容 。 3. 硬件提供“關(guān)中斷”和“開中斷”指令 關(guān)中斷 { Critical Region} 開中斷 Remarks: (1) 開關(guān)中斷只在單 CPU系統(tǒng)中有效 。(why?) (2) 影響并發(fā)性。 進(jìn)程同步 進(jìn)程同步的概念 例：司機(jī) 售票員問題 司機(jī)活動： 售票員活動： do{ do{ 啟動車輛 關(guān)車門 正常行駛 售 票 到站停車 開車門 }while(1) }while(1) 進(jìn)程同步的概念 定義 ： 一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點(diǎn)處需要相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為 進(jìn)程同步 。 P1: P2: synchronize 后 先 進(jìn)程同步機(jī)制 ? 定義： 用于實(shí)現(xiàn)進(jìn)程同步的工具稱為同步機(jī)制 （ synchronization mechanism） ? 同步機(jī)制要求： ? 描述能力夠用 。 ? 可實(shí)現(xiàn) 。 ? 高效 。 ? 使用方便 . 典型同步機(jī)制 ? 信號燈與 PV操作 (semaphore and PV operations) ? 管程 (monitor) ? 會合 (rendezvous) ? 條件臨界區(qū) (conditional critical region) ? 路徑表達(dá)式 (path expression) ? 事件 (event,traditional UNIX) 信號燈與 PV操作 , 1965. 信號燈與 PV操作的定義 Typedef semaphore struct{ int value。 PCBpointer queue。 }。 semaphore s。 Remarks: (1) semaphore is predefined data type, (2) s can be declared as needed, eg. semaphore s1,s2。 信號燈變量 PCB PCB PCB Var S:semaphore。 FIFO P操作原語 P操作原語： Procedure P(var s:semaphore) :=。 If 0 Then asleep() End asleep(): (1) 執(zhí)行此操作進(jìn)程的 PCB入 （狀態(tài)改為等待）； (2) 轉(zhuǎn)處理機(jī)調(diào)度程序。 Primitive:: a piece of code uninterruptible V操作原語 V操作原語： Procedure V(var s:semaphore) :=+1。 If =0 Then wakeup() End wakeup() PCB出等待隊列，進(jìn)入就緒隊列（狀態(tài)改為就緒）。 Primitive: a piece of code uninterruptible 規(guī)定和結(jié)論 ? 對于信號燈變量的規(guī)定： ? 必須置一次初值，只能置一次初值，初值 =0。 ? 只能執(zhí)行 P操作和 V操作，所有其它操作非法。 ? 幾個有用的結(jié)論 ： ? 當(dāng) =0時， ； ? 當(dāng) 0時， ||為隊列 ； ? 當(dāng) =1時，可以實(shí)現(xiàn)進(jìn)程互斥； ? 當(dāng) =0時，可以實(shí)現(xiàn)進(jìn)程同步。 用信號燈實(shí)現(xiàn)進(jìn)程互斥 Var mutex: semaphore。 (初值 =1） shared x,y,z:integer。 CR1 CR2 CRn …… 用信號燈實(shí)現(xiàn)進(jìn)程互斥 Var mutex: semaphore。 (初值 =1） shared x,y,z:integer。 P(mutex) P(mutex) P(mutex) CR1 CR2 CRn V(mutex) V(mutex) V(mutex) …… 互斥例子：借書系統(tǒng) ? Var mutex:semaphore。 (initial value is 1) ? 終端 1： 終端 2： ? CYCLE CYCLE ? 等待借書者； 等待借書者； ? IF x=1 Then IF x=1 Then ? Begin Begin ? x:=x1。 x:=x1。 ? ? 借書 借書 ? End End ? Else 無書 。 Else 無書 。 ? End End 互斥例子：借書系統(tǒng) (revisited) V