【文章內(nèi)容簡介】 ? 間接相互制約 (源于資源共享） 50 1). 直接相互制約：發(fā)生在相關(guān)進(jìn)程之間 send receive P1: P2: 2). 間接相互制約：發(fā)生在任何進(jìn)程之間 R P2 P1 hold wait 51 2 臨界資源 臨界資源： 一段時間內(nèi)只允許一個進(jìn)程訪問的資源 要求 ：各進(jìn)程必須互斥訪問臨界資源。 原因： 例如 生產(chǎn)者－消費者進(jìn)程 生產(chǎn)者進(jìn)程（ producer) 消費者進(jìn)程（ consumer) { … { … 放產(chǎn)品 取產(chǎn)品 counter:=counter+1。 counter:=counter1。 … … } } 52 機(jī)器語言形式為：生產(chǎn)者進(jìn)程 counter:=counter+1。 1 register1:=counter。 2 register1:=register1+1。 3 counter:=register1 消費者 進(jìn)程 counter:=counter1。 4 register2:=counter。 5 register2:=register21。 6 counter:=register2 由于生產(chǎn)者和消費者并發(fā)運行，且共享變量counter，造成： 可能性 A B C D 其他 CPU執(zhí)行順序 123456 456123 124536 451263 … Counter初值 5 5 5 4 6 … 正確 正確 不正確 不正確 不正確 53 3 臨界區(qū) ? 臨界區(qū)：每個進(jìn)程中訪問臨界資源的代碼稱為 臨界區(qū)。 ? 進(jìn)入?yún)^(qū)：檢查臨界資源是否正在被使用。 ? 退出區(qū)：將臨界資源使用標(biāo)志恢復(fù)，釋放臨界 資源。 ? 剩余區(qū)： 保證進(jìn)程互斥的進(jìn)入臨界區(qū)，從而保證互斥訪 問臨界資源 54 臨界區(qū) (CS)：每個進(jìn)程中訪問臨界資源的那段代碼 生產(chǎn)者進(jìn)程（ producer) 消費者進(jìn)程（ consumer) { … { … 放產(chǎn)品 取產(chǎn)品 counter:=counter+1。－ (CS) counter:=counter1。(CS) … … } } 為了實現(xiàn)對臨界資源的互斥訪問，應(yīng)保證各進(jìn)程互斥的進(jìn)入臨界區(qū)。 55 4 同步機(jī)制應(yīng)遵循的規(guī)則： ? 空閑讓進(jìn)， ? 忙則等待， ? 有限等待， ? 讓權(quán)等待。 56 ? P操作相當(dāng)于申請資源，而 V操作相當(dāng)于釋放資源。所以要記住以下幾個關(guān)鍵字： ? P操作 ?申請資源 ? V操作 ?釋放資源 信號量機(jī)制 57 ? PV操作的含義： PV操作是由 P操作原語和 V操作原語組成（原語是不可中斷的過程），對信號量進(jìn)行操作，具體定義如下： ? P（ S）：①將信號量 S的值減 1，即 S=S?1； ? ②如果 S?0，則該進(jìn)程繼續(xù)執(zhí)行；否則該進(jìn)程置為等待狀態(tài)，排入等待隊列。 ? V（ S）：①將信號量 S的值加 1，即 S=S+1； ? ②如果 S0，則該進(jìn)程繼續(xù)執(zhí)行；否則釋放隊列中第一個等待信號量的進(jìn)程。 58 一個生產(chǎn)者，一個消費者，公用一個緩沖區(qū) 好又多一分 店 伊利牛奶生產(chǎn)廠家件 生產(chǎn)一個產(chǎn)品 取出一個產(chǎn)品 59 ? empty—— 表示緩沖區(qū)是否為空，初值為 1。 ? full—— 表示緩沖區(qū)中是否為滿，初值為 0。 生產(chǎn)者進(jìn)程 while(TRUE) { 生產(chǎn)一個產(chǎn)品 。 P(empty)。 產(chǎn)品送往 Buffer。 V(full)。 } 消費者進(jìn)程 while(TRUE) { P(full)。 從 Buffer取出一個產(chǎn)品 。 V(empty)。 消費該產(chǎn)品 。 } 60 ? 信號量機(jī)制 是一種卓有成效的 進(jìn)程同步工具，被廣泛應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)，以及計 算機(jī)網(wǎng)絡(luò)中。 信號量機(jī)制 61 （１） 信號量的含義 。信號量是一個用來實現(xiàn)進(jìn)程同步的整型或記錄型變量，除了初始化外，對它只能執(zhí)行 wait和 signal這兩種原子操作。 在學(xué)習(xí)時，應(yīng)了解對信號量的 wait和 signal操作分別是如何實現(xiàn)的，整型信號量存在著什么不足之處，記錄型信號量是如何解決整型信號量的不足的。 62 （ ２） 信號量的物理意義 。 一個信號量 S通常對應(yīng)于一類臨界資源。 在學(xué)習(xí)時，必須理解 有什么特殊的含義，而每次 wait和 signal操作又分別意味著什么，故必須分別對。 63 （３） 用信號量實現(xiàn)互斥。 為了實現(xiàn)進(jìn)程對臨界資源的互斥訪問，需為每類臨界資源設(shè)置一初值為 1的互斥信號量 mutex。 在學(xué)習(xí)時，應(yīng)清楚在進(jìn)入臨界區(qū)前或退出臨界區(qū)后應(yīng)對 mutex分別執(zhí)行什么操作，為什么對mutex的 wait和 signal操作必須成對出現(xiàn)，如少了其中的 wait操作或 signal操作，會對互斥算法產(chǎn)生什么樣的影響。 64 （４） 用信號量實現(xiàn)前趨關(guān)系。 為實現(xiàn)前趨關(guān)系 Pi→ Pj，可為它們設(shè)置一個初值為0的信號量 S。 在學(xué)習(xí)時，應(yīng)清楚對 S的 wait操作和 signal操作應(yīng)分別安排在什么位置，同時必須注意 wait(S)操作和 signal(S)操作也必須成對出現(xiàn)。 65 信號量的分類： 整型信號量 （ integer semaphore)：信號 量是整數(shù)。 記錄型信號量 （ record semaphore)：每 個信號量 s除一個整數(shù)值 （計數(shù)） 外，還有一個進(jìn)程等待隊列 ，其中是阻 塞在該信號量的各個進(jìn)程的標(biāo)識 66 整型信號量 ? 最初由 Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作wait(s)和 signal(s)來訪問，分別稱為 P和 V操作。 ? wait(s): while s=0 do no_op。 ? s:=s1。 ? ? signal(s): s:=s+1 ? if s=0 then wakeup(P1)。 ? 67 記錄型信號量 ? 在整型信號量中的 wait(s)，只要 s=0則會不停地測試，該機(jī)制不遵循 “ 讓權(quán)等待 ” 的準(zhǔn)則，記錄型的信號量描述如下： ? type semaphore = record ? Value :integer。 ? L: list of process。 ? end 68 相應(yīng)的 wait(s)和 signal(s)操作