【文章內容簡介】 P1 和 P2 間的同步 取用 P 2 計算結果計算 f u n c 1 ( x )進程 P2 算完 f u n c 2 ( y )計算 f u n c 2 ( y )置計算完標志終止進程 P1進程 P2YN第三章 進程管理 2. 進程間的互斥 圖 資源互斥使用例 進程 A① 請求資源 R② 釋放資源 R進程 B② 請求資源 R④ 釋放資源 RR使用 R（阻塞）喚醒分配拒絕第三章 進程管理 又如 ， 設有兩個進程 P P2， 它們共享同一變量 count, P P2 P1： R1∶ =count。 P2: R2∶ =count。 R1∶ =R1+1。 R2∶ =R2+1。 count∶ =R1。 count∶ =R2。 其中， R1 和 R2 是處理機的兩個通用寄存器。 第三章 進程管理 它們可以按各自獨立的速度前進 ， 所以運行的順序也 P1: R1∶ =count。 P2: R2∶ =count。 P1: R1∶ =R1+1。 count∶ =R1。 P2: R2∶ =R2+1。 count∶ =R2。 第三章 進程管理 3. (1) 當有若干進程要求進入它們的臨界區(qū)時 ， 應在有限時間內使一進程進入臨界區(qū) 。 換句話說 ， 它們不應相互等待而致使誰都不能進入 。 (2) 每次最多有一個進程處于臨界區(qū)內 。 (3) 進程在臨界區(qū)內逗留應在有限時間范圍內。 第三章 進程管理 這種方法使用了一個物理實體 ， 稱為鎖 ， 用 W來表示 。鎖有兩種狀態(tài)： W=0 表示鎖已打開； W=1 表示鎖被關閉 。 加鎖原語用 LOCK (W)表示 ， 測試 W， 若 W=1， 表示資源正在使用 ， 繼續(xù)反復測試； 若 W=0， 置 W=1(加鎖 )。 加鎖原語用 LOCK (W)表示 ， L: if W=1 then go to L else W∶ [KG*8]= 1。 開鎖原語用 UNLOCK (W)表示 ， W∶ =0； 第三章 進程管理 于是，兩個進程 P1， P2使用如下程序實施進程的互斥： 進程 P1 進程 P2 LOCK (W) LOCK (W) S1 S2 UNLOCK (W) UNLOCK (W) 其中 S1和 S2分別為進程 P1 和 P2 的臨界區(qū)。 第三章 進程管理 在有些系統(tǒng)中 ， 上述的加鎖 、 開鎖操作可用機器硬件指令完成 。 例如 IBM/370 中就有一條稱為 “ 測試并置位 ”指令 TS。 該指令的功能是按第二操作域指出的地址從主存中取出一個字節(jié) ， 其最高位 (最左邊的位 )為 0 時 ， 置條件碼為 0；否則置條件碼為 1， 并將該字節(jié)的所有位均置 1。 于是加鎖原語 LOCK (W)可用指令 TS W BNZ * 4 第三章 進程管理 來代替 ， 其中 BNZ表示不等于 0 轉移 ， * 4 表示本指令地址減 4(BNZ本身是 4 字節(jié)指令 )。 即當 W不為 0 時轉移到上一條指令 TS繼續(xù)測試 ， 否則停止測試 ， 進入臨界區(qū) 。 請注意 ， 測試 W和置 W=1 是在一個指令周期內完成的 。 開鎖原語 UNLOCK (W) MVI W， X′00′ 來完成， MVI將一個全 0 的字節(jié)送入 W中。 第三章 進程管理 信號量和 P、 V操作 1. 信號量及 P、 V操作 信號量或信號燈 ， 是交通管理中的一種常用設備 。 交通管理人員利用信號燈的顏色 (紅 、 綠 )實現(xiàn)交通管理 。 在操作系統(tǒng)中 ， 信號量是表示資源的實體 ， 是一個與隊列有關的整型變量 ， 其值僅能由 P、 V操作來改變 。 操作系統(tǒng)利用信號量對進程和資源進行控制和管理 。 根據用途不同 ， 分為公用信號量和私用信號量 。 公用信號量通常用于實現(xiàn)進程之間的互斥 ，初值為 1， 它所聯(lián)系的一組并發(fā)進程均可對其實施 P、 V操作；私用信號量一般用于實現(xiàn)進程間的同步 ， 初值為 0 或為某個正整數(shù) n， 僅允許擁有它的進程對其實施 P操作 。 第三章 進程管理 P、 V操作是定義在信號量 S上的兩個操作 ， 其定義如下： P(S)： ① S∶ =S1。 ② 若 S≥0， 則調用 P(S) ③ 若 S0， 則調用 P(S)的進程被阻塞 ， 并把它插入到等 待信號量 S的阻塞隊列中 。 V(S)： ① S∶ =S+1。 ② 若 S0， 則調用 V(S) ③ 若 S≤0， 從等待信號量 S的阻塞隊列中喚醒頭一個進程 ， 然后調用 V(S)的進程繼續(xù)運行 。 第三章 進程管理 P、 V操作可表示為如下兩個過程： Procedure P(Var S:Semaphore)。 begin S∶ =S1。 if S0 then W(S) end。 {P} Procedure V(Var S:Semaphore)。 begin S∶ =S+1。 if S≤0 then R(S) end。 {V} 第三章 進程管理 2. 利用信號量實現(xiàn)進程的互斥 利用信號量可以方便地解決臨界區(qū)問題 。 設 S為兩進程互斥的公用信號量 ， 初值賦予 1， 表明該臨界資源未被占用 。只需把臨界區(qū)的程序段置于 P(S)和 V(S)之間 ， 即可實現(xiàn)兩進程的互斥 。 例如進程 P1 和進程 P2 按如下安排 ， 即可實現(xiàn)互斥： 進程 P1 進程 P2 P(S) P(S) S1 S2 V(S) V(S) 第三章 進程管理 例 1 前面例子中的公用變量 count, 也是一個臨界資源 。 兩個并發(fā)進程對 count的操作必須互斥地執(zhí)行 。 對此 ， 可寫出如下程序： begin count: integer。 S:semaphore。 count∶ =0。 S∶ =1。 cobegin process p1 R1: register。 begin P(S)。 第三章 進程管理 R1∶ =count。 R1∶ =R1+1。 count∶ =R1。 V(S) end。 process P2 R2: register。 begin P(S)。 R2∶ =count。 R2∶ =R2+1。 count∶ =R2。 V(S) end。 coend。 end。 第三章 進程管理 例 2 設一民航航班售票系統(tǒng)有 n個售票處 。 每個售票處通過終端訪問系統(tǒng)中的公用數(shù)據區(qū) ， 假定公共數(shù)據區(qū)中一些單元 xk(k=1, 2, …)分別存放 月 日 次航班的現(xiàn)存票數(shù) 。 設P1， P2， …， Pn表示各售票處的處理進程 ， R1, R2, …, Rn表示各進程執(zhí)行時所用的工作單元 。 用信號量實現(xiàn)進程間互斥的程序如下： begin S: Semaphore。 S∶ =1 cobegin 第三章 進程管理 Process P i(i=1, 2, …, n) begin 按旅客訂票要求找到 xk。 P(S) Ri∶ =xk。 if Ri≥1 then begin Ri∶ =Ri1。 xk∶ =R1。 V(S) end else begin V(S)。 輸出 “ 票已售完 ” end end。 coend。 end。 第三章 進程管理 3. 利用信號量實現(xiàn)進程間的同步 一般來說， 信號量初值為 0， 兩個進程之間的同步模型如下： 進程 P1 進程 P2 L1： P(S) L2： V(S) 第三章 進程管理 例 1 用信號量實現(xiàn)司機和售票員的同步 。 設 S1和 S2分別為司機和售票員的私用信號量 ， 初值均為 0， 則司機和售票員的同步過程描述如下： 第三章 進程管理 例 2 設進程 A、 B是兩個相互合作的進程 ， 共用一個緩沖區(qū) 。 進程 A負責從卡片輸入機讀入卡片送到緩沖區(qū) ， 進程 B取走緩沖區(qū)中的卡片信息進行加工處理 。 進程 A在完成將卡片送入緩沖區(qū)后 ， 給進程 B發(fā)一信號 。 進程 B收到信號后 ， 取走卡片信息進行加工處理 。 反之 ， 進程 B取走卡片信息后 ， 給進程 A發(fā)一信號 ， 進程 A再將卡片信息讀入緩沖區(qū) 。 為此 ， 我們利用兩個私用信號量 S1和 S2， 其初值均為 0， 信號量 S1表示緩沖區(qū)是否有卡片信息 ， 信號量 S2表示緩沖區(qū)信息是否被取走 。 利用 P、 V操作實施進程 A、 B 第三章 進程管理 第三章 進程管理 4. 生產者 — 消費者問題 (ProducerConsumer Problems) 圖 生產者 — 消費者問題 123456…0n 1n2C1C2C3C K…P1P2P3P m…RP第三章 進程管理 了實現(xiàn)上述兩組進程互斥地進入臨界區(qū) ， 我們設置兩個 (1) 公用信號量 S， 初值為 1， 表示沒有進程進入臨界區(qū) ， (2) 私用信號量 S0， 用以表示產品數(shù)目 ， 初值為 0 (3) 私用信號量 Sn， 用以表示可用緩沖區(qū)數(shù) ， 初值為 n 。 生產者 — 消費者進程描述如下： 第三章 進程管理 第三章 進程管理 生產者和消費者可按如下方式并發(fā)執(zhí)行： begin B: array［ 0n1］ of integer。 P, R: integer。 S, S n, S 0: semaphore。 p∶ =R∶ =0 S∶ =1。 S n∶ =n。 S 0∶ =0。 cobegin process producer i(i=1, 2, ……, m) begin L1: produce a product。 P(S n)。