【文章內(nèi)容簡(jiǎn)介】 e semaphore = record value : integer。 queue: list of process。 end。 procedure P (var s: semaphore)。 begin := – 1。 if 0 then W()。 end。 procedure V (var s: semaphore)。 begin := + 1。 if = 0 then R()。 end。 信號(hào)量與 PV操作 當(dāng)信號(hào)量代表某個(gè)物理資源時(shí)，關(guān)于記錄型信號(hào)量和 PV操作的三個(gè)推論 –若 ，則該值代表實(shí)際還可以使用的物理資源數(shù)量 –若 ，則其絕對(duì)值代表 中等待該物理資源的進(jìn)程數(shù)目 – P操作意味著請(qǐng)求一個(gè)資源（可能被阻塞）， V操作意味著釋放一個(gè)資源（喚醒被阻塞的進(jìn)程） 信號(hào)量與 PV操作 二元信號(hào)量 –記錄型信號(hào)量的一個(gè)特例，其 value分量?jī)H能取值為 0或 1 – BP(s)： if = 1 then = 0 else w()。 – BV(s)： if is empty then := 1 else R()。 –表達(dá)能力等同與一般的記錄型信號(hào)量（稍有差別） 信號(hào)量與 PV操作 采用記錄型信號(hào)量實(shí)現(xiàn)互斥 – 與硬件指令實(shí)現(xiàn)的區(qū)別， P,V操作只對(duì)信號(hào)量測(cè)試一次（等待），而 TS指令需要反復(fù)測(cè)試（忙等待） – 實(shí)現(xiàn)互斥的一般形式： var mutex: semaphore。 mutex := 1。 cobegin … process Pi begin … P(mutex)。 臨界區(qū)； V(mutex)。 … end。 … coend。 信號(hào)量與 PV操作 記錄型信號(hào)量與 PV操作解決售票問(wèn)題 var A: Array[1..m] of integer。 mutex: semaphore。 mutex := 1。 cobegin … process Pi var Xi : integer。 begin L1: 按旅客要求找到對(duì)應(yīng)的 A[j]。 P(mutex)。 Xi := A[j]。 if Xi = 1 then begin Xi := Xi 1。 A[j] := Xi。 V(mutex)。 輸出一張票； end else begin V(mutex)。 提示票已售完； end。 goto L1。 end。 … coend. 信號(hào)量與 PV操作 記錄型信號(hào)量與 PV操作解決售票問(wèn)題 (改進(jìn)方案 ) var A: Array[1..m] of integer。 s: Array[1..m] of semaphore。 s[j] := 1。 cobegin … process Pi var Xi : integer。 begin L1: 按旅客要求找到對(duì)應(yīng)的 A[j]。 P(s[j])。 Xi := A[j]。 if Xi = 1 then begin Xi := Xi 1。 A[j] := Xi。 V(s[j])。 輸出一張票； end else begin V(s[j])。 提示票已售完； end。 goto L1。 end。 … coend. 信號(hào)量與 PV操作 五個(gè)哲學(xué)家吃通心面（面條）問(wèn)題 – 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌子中央有一盤通心面，每人面前有一只空盤子，每?jī)扇酥g放一把叉子。每個(gè)哲學(xué)家思考、饑餓，然后想吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，規(guī)定每人只能直接從其左邊或右邊去取叉子 信號(hào)量與 PV操作 五個(gè)哲學(xué)家吃通心面（面條）問(wèn)題解決 – 叉子是共享資源，需要互斥訪問(wèn) 引入五個(gè)記錄型互斥信號(hào)量 每個(gè)哲學(xué)家吃之前，先對(duì)其左右兩個(gè)叉子所對(duì)應(yīng)的信號(hào)量 P操作，吃完后，對(duì)其進(jìn)行 V操作 – 上述解決方法，將有可能出現(xiàn)所有哲學(xué)家都吃不到通心面而餓死的問(wèn)題（相互等待） 至多允許四個(gè)哲學(xué)家同時(shí)吃 奇數(shù)號(hào)先取左手邊叉子，偶數(shù)號(hào)先取右手邊叉子 每個(gè)哲學(xué)家取到手邊得兩把叉子才吃，否則，一把也不取 信號(hào)量與 PV操作 記錄型信號(hào)量解決生產(chǎn)者 消費(fèi)者問(wèn)題 –單個(gè)生產(chǎn)者和單個(gè)消費(fèi)者問(wèn)題 –單一產(chǎn)品的多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者問(wèn)題 –多類產(chǎn)品的多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者問(wèn)題 信號(hào)量與 PV操作 單個(gè)生產(chǎn)者和單個(gè)消費(fèi)者問(wèn)題 –生產(chǎn)者與消費(fèi)者的同步問(wèn)題 引如兩個(gè)信號(hào)量， empty, full解決進(jìn)程間同步問(wèn)題，取代 counter計(jì)數(shù)器 empty指示生產(chǎn)者是否可以向緩沖區(qū)放入產(chǎn)品 full指示消費(fèi)者是否可從緩沖區(qū)獲得產(chǎn)品 先生產(chǎn)，后消費(fèi)， = k, = 0 生產(chǎn)者， P(empty) 、生產(chǎn)、 V(full) 消費(fèi)者， P(full)、消費(fèi)、 V(empty) 信號(hào)量與 PV操作 單一產(chǎn)品的多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者問(wèn)題 –生產(chǎn)者與消費(fèi)者之間的同步問(wèn)題 同單個(gè)生產(chǎn)者和單個(gè)消費(fèi)者問(wèn)題 –多個(gè)生產(chǎn)者之間互斥訪問(wèn) in指針的問(wèn)題 –多個(gè)消費(fèi)者之間互斥訪問(wèn) out指針的問(wèn)題 引入 mutex信號(hào)量，解決互斥問(wèn)題 –既有同步又有互斥信號(hào)量的情況下，原則上，用于互斥信號(hào)量上的 P操作總在后面執(zhí)行 信號(hào)量與 PV操作 多類產(chǎn)品的多生產(chǎn)者和多消費(fèi)者問(wèn)題 –一個(gè)緩沖區(qū)長(zhǎng)度為 1的多類產(chǎn)品的多生產(chǎn)者和多消費(fèi)者問(wèn)題 –引入 3個(gè)信號(hào)量 sp，允許放入盤子，初值是緩沖器長(zhǎng)度 sg1, 初值為 0，允許消費(fèi)第一類產(chǎn)品 sg2, 初值為 0，允許消費(fèi)第二類產(chǎn)品 信號(hào)量與 PV操作 讀者 寫者問(wèn)題 –有兩類并發(fā)進(jìn)程，讀進(jìn)程與寫進(jìn)程，共享一個(gè)文件，為防止出錯(cuò)，要求： 1）允許多個(gè)讀進(jìn)程同時(shí)對(duì)文件讀； 2）只允許一個(gè)寫進(jìn)程寫信息； 3）寫進(jìn)程在沒(méi)有寫完成之前不允許讀； 4）寫之前應(yīng)該讓所有已經(jīng)在讀或?qū)懙倪M(jìn)程操作完成。 –引入一個(gè)計(jì)數(shù)器和兩個(gè)信號(hào)量解決此問(wèn)題 int rc, 讀進(jìn)程計(jì)數(shù)器 W，允許寫信號(hào)量，初值為 1 mutex，互斥訪問(wèn) rc計(jì)數(shù)器信號(hào)量，初值為 1 讀者優(yōu)先的讀者 寫者問(wèn)題 var rc: integer。 w, mutex: semaphore。 rc := 0。 w := 1。 mutex := 1。 procedure read begin P(mutex)。 rc := rc +1。 if rc = 1 then P(W)。 V(mutex)。 讀文件； P(mutex)。 rc := rc – 1。 if rc = 0 then V(w)。 V(mutex)。 end。 procedure wite begin P(w)。 寫文件； V(w)。 end。 讀者 寫者問(wèn)題的進(jìn)一步思考 讀者優(yōu)先的解決方法，可能會(huì)出現(xiàn)寫進(jìn)程無(wú)限期被推遲的情況，為解決此問(wèn)題，可考慮： –公平的讀者 寫者問(wèn)題 –寫者優(yōu)先的讀者 寫者問(wèn)題 – pthread提供了讀寫鎖 pthread_rwlock_t，對(duì)應(yīng)哪種實(shí)現(xiàn)？ 讀者 寫者近似公平的解決方法 二元信號(hào)量實(shí)現(xiàn)一般信號(hào)量（錯(cuò)誤） typedef struct semaphore { int value。 binary_semaphore wait, mutex。 wait = 0。 mutex = 1。 }。 Semaphore S。 P(S): BP()。 。 if ( 0) { ① BV()。 ② BP()。 } else BV()。 V(S): BP()。 ++ 。 if ( = 0) { ① BV()。 } BV()。 二元信號(hào)量實(shí)現(xiàn)一般信號(hào)量（正確） typedef struct semaphore { int value。 binary_semaphore wait, mutex。 wait = 0。 mutex = 1。 }。 Semaphore S。 P(S): BP()。 。 if ( 0) { BV()。 BP()。 } BV()。 V(S): BP()。 ++ 。 if ( = 0) { BV()。 } else BV()。 信號(hào)量與 PV操作 (理發(fā)師問(wèn)題 ) 理發(fā)師問(wèn)題 – 理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和 n把供等候理發(fā)的顧客坐的椅子。如果沒(méi)有顧客，理發(fā)師就在理發(fā)椅上睡覺(jué)。當(dāng)一個(gè)顧客到來(lái)后，他必須叫醒理發(fā)師。如果理發(fā)師正在理發(fā)時(shí)又有顧客到來(lái)，那么，如果有空椅子可坐，顧客就坐下來(lái)等待，否則離開理發(fā)店。 – 引入 3個(gè)信號(hào)量和一個(gè)控制變量 int waiting, 等候理發(fā)師的顧客數(shù)，初值為 0 customer, 是否有人需要理發(fā)，初值為 0 barbers，是否有理發(fā)師可以理發(fā)，初值為 0 mutex，互斥信號(hào)量，初值為 1 信號(hào)量與 PV操作 (理發(fā)師問(wèn)題 ) var waiting: integer。 customers, barbers, mu