【文章內(nèi)容簡介】 _semaphore。 void P_B(B_semaphore S){ if (==true) =false。 else{ 把該進程放入 。 block( )。 } } void V_B(B_semaphore S){ if(==NULL) =true。 else{ 從 Q。 wakeup(Q)。 } } 信號量的一般應用 1．用信號量實現(xiàn)進程互斥 打印機分配表的互斥使用 Pa: Pb: … … P(mutex) P(mutex) 分配打印機 釋放打印機 （讀寫分配表） （讀寫分配表） V(mutex) V(mutex) … … 用信號量實現(xiàn)進程互斥 利用信號量實現(xiàn)互斥的一般模型是： 進程 P1 進程 P2 … 進程 Pn … … … P(mutex)。 P(mutex)。 P(mutex)。 臨界區(qū) 臨界區(qū) 臨界區(qū) V(mutex)。 V(mutex)。 V(mutex)。 … … … 用信號量實現(xiàn)進程互斥 ● 注意點： ① 在每個程序中用于實現(xiàn)互斥的 P(mutex)和 V(mutex)必須成對 出現(xiàn)，即先做 P，進入臨界區(qū)；后做 V，退出臨界區(qū)。 ② 互斥信號量 mutex的 初值 一般為 1。 2． 用信號量實現(xiàn)進程簡單同步 對緩沖區(qū)的同步使用問題 簡單供者和用者對緩沖區(qū)的使用關系 用信號量實現(xiàn)進程簡單同步 ? 供者和用者間要交換兩個消息： 緩沖區(qū)空 緩沖區(qū)滿 ? 設置兩個信號量： S1表示緩沖區(qū)是否空（ 0表示不空， 1表示空）。 S2表示緩沖區(qū)是否滿（ 0表示不滿， 1表示滿）。 規(guī)定 S1和 S2的初值分別為 1和 0 用信號量實現(xiàn)進程簡單同步 供者進程 用者進程 L1: P(S1) L2: … 啟動讀卡機 P(S2) 。 … 從緩沖區(qū)取出信息 收到輸入結(jié)束中斷 V(S1)。 V(S2)。 加工并且存盤 goto L1。 goto L2。 用信號量實現(xiàn)進程簡單同步 用 P和 V操作實現(xiàn) 同步 時應注意如下三點： ① 分析進程間的制約關系，確定信號量種類。 ② 信號量的初值與相應資源的數(shù)量有關，也與 P, V操作在程序代碼中出現(xiàn)的位置有關。 ③ 同一信號量的 P, V操作要 “ 成對 ” 出現(xiàn)，但是，它們分別出現(xiàn)在不同的進程代碼中。 經(jīng)典進程同步問題 1．生產(chǎn)者 消費者問題 ? 生產(chǎn)者 :能產(chǎn)生并釋放資源的進程 ? 消費者 :單純使用（消耗）資源的進程 ? 問題表述 一 組 生產(chǎn)者進程和一 組 消費者進程（設每組有多個進程）通過緩沖區(qū)發(fā)生聯(lián)系。生產(chǎn)者進程將生產(chǎn)的產(chǎn)品（數(shù)據(jù)、消息等統(tǒng)稱為產(chǎn)品）送入緩沖區(qū)，消費者進程從中取出產(chǎn)品。 假定緩沖區(qū)共有 N個，不妨把它們設想成一個環(huán)形緩沖池。 生產(chǎn)者 消費者問題 生產(chǎn)者 消費者問題環(huán)形緩沖池 它們應滿足如下同步條件 ： ① 任一時刻所有生產(chǎn)者存放產(chǎn)品的單元數(shù)不能超過緩沖區(qū)的總?cè)萘浚?N）。 ② 所有消費者取出產(chǎn)品的總量不能超過所有生產(chǎn)者當前生產(chǎn)產(chǎn)品的總量。 生產(chǎn)者 消費者問題 ● 設緩沖區(qū)的編號為 0～ N1， in和 out分別是生產(chǎn)者進程和消費者進程使用的指針，指向下面可用的緩沖區(qū)，初值都是 0。 ● 設置三個信號量： ? full：表示放有產(chǎn)品的緩沖區(qū)數(shù)，其初值為 0。 ? empty：表示可供使用的緩沖區(qū)數(shù)，其初值為 N。 ? mutex：互斥信號量，初值為 1，表示各進程互斥進入臨界區(qū)，保證任何時候只有一個進程使用緩沖區(qū)。 生產(chǎn)者 消費者問題 生產(chǎn)者進程 Producer： 消費者進程 Consumer： while(TRUE) { while(TRUE){ P(empty)。 P(full)。 P(mutex)。 P(mutex)。 產(chǎn)品送往 buffer(in)。 從 buffer(out)中取出產(chǎn)品； in=(in+1)mod N。 out=(out+1)mod N。 /*以 N為模 */ /*以 N為模 */ V(mutex)。 V(mutex)。 V(full)。 V(empty)。 } } 2．讀者 寫者問題 讀者 寫者問題也是一個著名的進程互斥訪問有限資源的同步問題。例如，一個航班預訂系統(tǒng)有一個大型數(shù)據(jù)庫，很多競爭進程要對它進行讀、寫。允許多個進程同時讀該數(shù)據(jù)庫，但是在任何時候如果有一個進程寫（即修改）數(shù)據(jù)庫，那么就不允許其他進程訪問它 —— 既不允許寫，也不允許讀。 讀者 寫者問題 ● 信號量設置： ▲ 讀互斥信號量 rmutex 初值為 1 ▲ 寫互斥信號量 wmutex 初值為 1 rmutex：讀者互斥地訪問 readcount wmutex：保證一個寫者與其他讀者 /寫者互斥地訪問共享資源 ★ 讀計數(shù)器 readcount，整型變量，初值為 0。 讀者 寫者問題 讀者 Readers while(TRUE){ P(rmutex)。 readcount=readcount+1。 if(readcount==1) P(wmutex)。 V(rmutex)。 執(zhí)行讀操作 P(rmutex)。 readcount=readcount1。 if(readcount==0) V(wmutex)。 V(rmutex)。 使用讀取的數(shù)據(jù) } 寫者 Writers while(TRUE) { P(wmutex)。 執(zhí)行寫操作 V(wmutex)。 } ▲ 這個算法隱含讀者的優(yōu)先級高于寫者 3．哲學家進餐問題 五位哲學家圍坐在一張圓桌旁進餐，每人面前有一只碗，各碗之間分別有一根筷子。每位哲學家在用兩根筷子夾面條吃飯前獨自進行思考，感到饑餓時便試圖占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能強行從鄰座手中拿過筷子，而且必須用兩根筷子進餐；餐畢，要把筷子放回原處并繼續(xù)思考問題。 哲學家進餐問題 哲學家進餐問題 =========================================== define N 5 define LEFT (i1)%N define RIGHT (i+1)%N define THINKING 0 define HUNGRY 1 define EATING 2 typedef struct{ /* 定義結(jié)構(gòu)型信號量 */ int value。 struct PCB *list。 }semaphore。 int state[N]。 semaphore mutex=1。 /* 互斥進入臨界區(qū) */ semaphore s[N]。 /* 每位哲學家一個信號量 */ 哲學家進餐問題 void philosopher(int i) { while(TRUE){ think()。 /* 哲學家在思考問題 */ take_chopstick(i)。 /* 拿到兩根筷子或者等待 */ eat()。 /* 進餐 */ put_chopstick(i)。 /* 把筷子放回原處 */ } } void take_chopstick(int i) { P(mutex)。 state[i]=HUNGRY。 test(i)。 /* 試圖拿兩根筷子 */ V(mutex)。 P(s[i])。 } 哲學家進餐問題 void put_chopstick(int i) { P(mutex)。 state[i]=THINKING。 test(LEFT)。 /* 查看左鄰，現(xiàn)在能否進餐 */ test(RIGHT)。 /* 查看右鄰，現(xiàn)在能否進餐 */ V(mutex)。 } void test(int i) { if(state[i]==HUNGRY amp。amp。 state[LEFT]!=EATING amp。amp。 state[RIGHT]!=EATING) { state[i]=EATING。 V (s[i] )。 } } =============================================== 打瞌睡的理發(fā)師 4． 打瞌睡的理發(fā)師問題 理發(fā)店有一名理發(fā)師 ， 一把理發(fā)椅和幾把座椅 ， 等待理發(fā)者可坐在上面 。 如果沒有顧客到來 ， 理發(fā)師就坐在理發(fā)椅上打盹 。 當顧客到來時 ，就喚醒理發(fā)師 。 如果顧客到來時理發(fā)師正在理發(fā) ， 該顧客就坐在椅子上排隊；如果滿座了 ， 他就離開這個理發(fā)店 ， 到別處去理發(fā) 。 打瞌睡的理發(fā)師問題 理發(fā)師和每位顧客都分別是一個進程 =======================