【正文】 } parend 本題中 in和 out不是共享變量 (因?yàn)橹挥幸粋€生產(chǎn)者和一個消費(fèi)者 )，無需互斥訪問。 signal(empty)。 //測試 nextc=buffer[out]。 signal(full)。//測試 buffer[in]=nextp。 //下標(biāo) parbegin process Producer: { ... produce an item in nextp。full=0。 empty=n full=0 133 semaphore empty,full。 } parend 132 生產(chǎn)者 消費(fèi)者問題的第二種特殊情況 一個生產(chǎn)者、一個消費(fèi)者、 n個緩沖區(qū)的 PC問題 n1 5 4 3 2 1 0 P C 循環(huán)緩沖區(qū) … ? 為生產(chǎn)者設(shè)置一個資源信號量 empty， 其初值為生產(chǎn)者的可用資源數(shù) (空緩沖區(qū)的個數(shù) )n， 即empty=n。 signal(empty)。//通知消費(fèi)者 } process Consumer: { wait(full)。//測試 buffer=nextp。 parbegin process Producer: { ... produce an item in nextp。 empty=1。 若有資源可用 ， 則進(jìn)入臨界區(qū) ， 否則阻塞； 3. 同步雙方任一進(jìn)程離開臨界區(qū)后 ， 應(yīng)對合作方 (對方 )的信號量執(zhí)行 signal(對方信號量 )操作 ，以 通知 (若對方處于阻塞狀態(tài) ， 則喚醒它 )對方已有資源可用 (對方已可進(jìn)入臨界區(qū) )。 ★ 當(dāng)緩沖區(qū)滿時，消費(fèi)者可從緩沖區(qū)取出產(chǎn)品進(jìn)行消費(fèi)；當(dāng)緩沖區(qū)空時，消費(fèi)者必須等待 (阻塞 )，待生產(chǎn)者存入產(chǎn)品后將其喚醒后，才能再從緩沖區(qū)取產(chǎn)品。 生產(chǎn)者 消費(fèi)者問題是相互合作進(jìn)程關(guān)系的一種抽象 ， 例如 ， …… 先介紹最簡單的 PC問題 生產(chǎn)者 消費(fèi)者問題從特殊到一般 (從易到難 )可以分 3種形式： ▲ 一個生產(chǎn)者、一個消費(fèi)者、一個緩沖區(qū)的問題； ▲ 一個生產(chǎn)者、一個消費(fèi)者、 n個緩沖區(qū)的問題； ▲ k個生產(chǎn)者、 m個消費(fèi)者、 n個緩沖區(qū)的問題； 128 最簡單的 生產(chǎn)者 消費(fèi)者問題 緩沖區(qū) P C 一個生產(chǎn)者、一個消費(fèi)者、一個緩沖區(qū)的問題如右圖所示。 } parend // 用 parend表示并發(fā)執(zhí)行結(jié)束 126 經(jīng)典進(jìn)程同步問題 ? 生產(chǎn)者 消費(fèi)者問題 ? 讀者 寫者問題 ? 哲學(xué)家進(jìn)餐問題 在多道程序環(huán)境下，進(jìn)程同步問題十分重要，引起了不少學(xué)者對它進(jìn)行研究，由此產(chǎn)生了一系列經(jīng)典的進(jìn)程同步問題，其中較有代表性的是： 通過對這些問題的研究和學(xué)習(xí)，可以幫助我們更好地理解進(jìn)程同步概念及實(shí)現(xiàn)方法。 wait(S56)。 } process P6： { wait(S36)。 執(zhí)行 S5。 signal(S46)。 } process P4： { wait(S24)。 執(zhí)行 S3。 signal(S25)。 執(zhí)行 S2。 signal(S13)。 程序描述如下： 初始化 parbegin // parbegin表示并發(fā)執(zhí)行開始 process P1： { 執(zhí)行 S1。 ==0。 S1 S2 S3 S4 S5 S6 圖 212 前趨圖舉例 P1 P2 P3 P4 P5 P6 125 semaphore S12,S13,S24,S25,S36,S46,S56。 } 臨界區(qū) semaphore S ； int count = 0 ； = 1 ； 【 注意 】 wait (S)和signal (S)必須成對出現(xiàn) 124 利用信號量實(shí)現(xiàn)前趨關(guān)系 【 例 】 利用信號量 ， 描述語句的前趨關(guān)系 （ 見圖 212） 寫出一個可并發(fā)執(zhí)行的程序。 print（ count） 。 signal（ S） 。 wait（ S） 。 兩個進(jìn)程的并發(fā)執(zhí)行可完成對每小時中卡車流量的統(tǒng)計 。 請看下頁的例子 非臨界區(qū) wait(mutex) //進(jìn)入?yún)^(qū) 臨界區(qū) signal(mutex) //退出區(qū) 非臨界區(qū) 123 利用信號量實(shí)現(xiàn)進(jìn)程互斥的簡單例子 ? 某交通路口設(shè)置了一個自動計數(shù)系統(tǒng) ， 該系統(tǒng)由 “ 觀察者 ”進(jìn)程和 “ 報告者 ” 進(jìn)程組成 。 從所有 Si等待隊(duì)列中移出進(jìn)程并置入就緒隊(duì)列。 else 進(jìn)程進(jìn)入第一個遇到的滿足 Siti條件的 Si信號 量隊(duì)列等待，同時將該進(jìn)程的程序計數(shù)器地 址回退，置為 Swait操作處。amp。amp。 從所有 Si等待隊(duì)列中移出進(jìn)程并置入就緒隊(duì)列。 else 進(jìn)程進(jìn)入第一個滿足 Si1條件的 Si信號量隊(duì)列 等待，同時將該進(jìn)程的程序計數(shù)器地址回退， 置為 Swait操作處。amp。amp。 (2022年全國考研試題 ) A． 0、 1 B． 0 C． 2 D． 0 B D 3 119 1. 設(shè)有 n個進(jìn)程使用同一個共享變量，如果最多允許 m(m n)個進(jìn)程同時進(jìn)入相關(guān)臨界區(qū)，則信號量的變化范圍是 。 7. 設(shè)與某資源關(guān)聯(lián)的信號量初值為 3， 當(dāng)前值為 1。 A．可能為 1或 3 B．只能為 1 C．可能為 0、 1或 2 D．可能為 0、 1或 2 作業(yè)中部分題目講解： C 118 3. ， S的兩個組成部分，當(dāng) ， 。加 1和減 1操作的指令序列分別如下所示。 117 作業(yè) 1——進(jìn)程同步 (1) 8. (2022全國試題 )有兩個并發(fā)進(jìn)程 P1和 P2，共享初值為 1的變量 x。 ——資源信號量 。 可見該機(jī)制遵循了“ 讓權(quán)等待 ” 準(zhǔn)則 。 /*喚醒第一個等待的進(jìn)程 */ } P(S) V(S) 中某類資源的數(shù)目。 /* 讓權(quán)等待 */ } void signal (semaphore S ) { = + 1 。 115 wait和 signal操作可用 C/C++語言描述如下： void wait( semaphore S) { = – 1 。 它們以前被稱為 P、 V操作 。 114 記錄型信號量 需要一個用于代表臨界資源數(shù)目的整型變量value；還要一個在該資源上阻塞的隊(duì)列 （ 鏈表 ）指針 L。 ——后邊重點(diǎn)介紹 。 信號量機(jī)制的發(fā)展： ? 整型信號量 ? 記錄型信號量 ? AND型信號量 ? 信號量集 ―忙等 ” ，未遵循 “ 讓權(quán)等待 ” 準(zhǔn)則。 113 信號量機(jī)制 信號量 (Semaphores)機(jī)制是一種卓有成效的進(jìn)程同步工具。 ——不忙碌等待 。 不互相阻塞 。 112 ? 有限等待 ? 讓權(quán)等待 對要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限的時間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入 “ 死鎖 ” 狀態(tài)。 所有同步機(jī)制都應(yīng)遵循如下四條準(zhǔn)則： ? 空閑讓進(jìn) 當(dāng)無進(jìn)程處于臨界區(qū)時 ， 表明臨界資源處于空閑狀態(tài) ， 應(yīng)允許一個請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū) ， 以便有效地利用臨界資源 。 repeat 非臨界區(qū) 進(jìn)入?yún)^(qū) 臨界區(qū) 退出區(qū) 非臨界區(qū) until false 一般結(jié)構(gòu) ―進(jìn) 入 區(qū) ” 和“ 退出區(qū) ” 的不同構(gòu)成方法 ，形成了各種不同的 同步機(jī)制 。 進(jìn)程互斥 ——不允許兩個或兩個以上進(jìn)程同時進(jìn)入 相關(guān)臨界區(qū) 。 為此 ， 每個進(jìn)程在進(jìn)入臨界區(qū)之前 ， 應(yīng)先對欲訪問的臨界資源進(jìn)行檢查 ， 看是否正被訪問 ，如果此刻該資源未被訪問 ， 便可進(jìn)入臨界區(qū)對該臨界資源進(jìn)行訪問 ， 并設(shè)置它正被訪問的標(biāo)志；如果此刻它正被訪問 ，則本進(jìn)程不能進(jìn)入臨界區(qū) 。 不論是硬件臨界資源 ， 還是軟件臨界資源 ， 多個進(jìn)程必須互斥地對它們訪問 。 解決此問題的關(guān)鍵，是應(yīng)將變量 counter作為臨界資源處理，亦即讓生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程互斥地訪問變量 counter。 (生產(chǎn)者保存 counter的新值 6) 最終 counter的值為 6，正確的值應(yīng)是 5，出現(xiàn)了差錯。 (消費(fèi)者將該值減 1變?yōu)?4) counter = register2。 (生產(chǎn)者將該值增 1變?yōu)?6) register2 = counter。 counter = register1； 消費(fèi)者執(zhí)行的操作： register2 = counter ； register2 = register2 1 ； counter = register2； 108 假設(shè)某一時刻 counter的值為 5，生產(chǎn)者和消費(fèi)者同時對 counter操作，按下述順序執(zhí)行： register1 = counter。 但若并發(fā)執(zhí)行時 ， 可能會出現(xiàn)差錯 ，問題在于這兩個進(jìn)程共享變量 counter。 以下是軟件臨界資源的例子。 如，打印機(jī)、磁帶機(jī)、共享變量、隊(duì)列、 …… 104 生產(chǎn)者 消費(fèi)者問題 【 例 】 生產(chǎn)者 消費(fèi)者問題 ——著名的進(jìn)程同步問題 共享變量： 臨界資源 循環(huán)緩沖區(qū) 生產(chǎn)者投放一個產(chǎn)品后，輸入指針 in加 1：in = ( in + 1 ) % n （ n是緩沖區(qū)個數(shù)，整型常量）， in初值為 0； 消費(fèi)者每取出一個產(chǎn)品，輸出指針 out加 1：out = ( out + 1 ) % n， out初值為 0； 引入一個 共享 變量 counter,初值為 0。 進(jìn)程互斥 （ 2）直接制約關(guān)系 源于進(jìn)程間的合作。 進(jìn)程同步的基本概念 信號量機(jī)制 信號量的應(yīng)用 103 進(jìn)程同步的基本概念 1．兩種形式的制約關(guān)系 （ 1）間接制約關(guān)系 間接制約關(guān)系源于資源共享。 ▲ 檢查該進(jìn)程現(xiàn)行狀態(tài)： 102 進(jìn)程同步 ? 由于進(jìn)程的異步性 ， 尤其是它們競爭臨界資源時 ，可能會給系統(tǒng)造成混亂 。 激活過程是： ▲ 將進(jìn)程從外存調(diào)入內(nèi)存； 若是靜止就緒，則改為活動就緒； 若是靜止阻塞，則改為活動阻塞。 ▲ 若該進(jìn)程正在執(zhí)行，則轉(zhuǎn)進(jìn)程調(diào)度程序重新調(diào)度。 100 1．進(jìn)程的掛起 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時 (用戶進(jìn)程請求將自己掛起，或父進(jìn)程請求將子進(jìn)程掛起 )，系統(tǒng)將用掛起原語 suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。 喚醒原語執(zhí)行過程 ： ▲ 將被喚醒進(jìn)程的 PCB從阻塞隊(duì)列移出； ▲ 將其 PCB中進(jìn)程狀態(tài)由 “ 阻塞 ” 改為 “ 就緒 ” ； ▲ 將改 PCB插入到就緒隊(duì)列中。（主動行為） 阻塞（ block）過程： ? 立即停止執(zhí)行； ? 把 PCB中進(jìn)程狀態(tài)由 “ 執(zhí)行 ” 改為 “ 阻塞 ” ； ? 將 PCB插入具有相同事件的阻塞隊(duì)列； ? 轉(zhuǎn)進(jìn)程調(diào)度程序，將處理機(jī)分配給某個就緒進(jìn)程，并進(jìn)行進(jìn)程切換 ——保留被阻塞進(jìn)程的處理機(jī)狀態(tài)（在 PCB中），再按新進(jìn)程的PCB中處理機(jī)狀態(tài)設(shè)置 CPU的環(huán)境。 如 ， 啟動了某 I/O設(shè)備 ， …… ▲ 新數(shù)據(jù)尚未到達(dá) 對于相互合作的進(jìn)程 ， 如果其中一個進(jìn)程需要獲得另一個 （ 合作 ）進(jìn)程提供的數(shù)據(jù)才能運(yùn)行以對數(shù)據(jù)進(jìn)行處理 ， 則只要其所需數(shù)據(jù)尚未到達(dá) ， 該進(jìn)程只有阻塞 （ 等待 ） 。 如 ， 進(jìn)程請求打印機(jī) ， …… 系統(tǒng)往往設(shè)置一些具有特定功能的系統(tǒng)進(jìn)程 ， 每當(dāng)這種進(jìn)程完成任務(wù)后 ， 便把自己阻塞起來以等待新任務(wù)到來 。 (4)將被終止進(jìn)程 （ 它的 PCB） 從所在隊(duì)列中移出 ， 等待其他進(jìn)程來搜索信息 。 若該進(jìn)程還有子孫進(jìn)程 ， 應(yīng)將其所有子孫進(jìn)程終止 ， 以防止它們成為不可控進(jìn)程 。 95 1．引起進(jìn)程終止的事件 ▲ 正常結(jié)束 ▲ 外界干預(yù) ? 越界錯誤 ? 保護(hù)錯 ——試圖訪問不允許訪問的資源或文件 ， 或者以不適當(dāng)方式訪問 ? 非法指令 ? 特權(quán)指令錯 ——用戶程序試圖執(zhí)行只允許 OS執(zhí)行的指令 ? 運(yùn)行超時 ? 等待超時 ? 算術(shù)運(yùn)算錯 ——被 0除 ? I/O故障 ? 操作員或操作系統(tǒng)干 預(yù)（如發(fā)生死鎖） ? 父進(jìn)程請求 ? 父進(jìn)程終止 進(jìn)程的終止 ▲ 異常結(jié)束 常見的異常 結(jié)束事件 96 2．進(jìn)程的終止過程 OS調(diào)用終止原語，按下述過程終止進(jìn)