【正文】 en a := a +1 else a:= a1 P3 互斥 進(jìn)程的互斥 一個具體的例子： 2022/2/17 72 臨界資源互斥訪問： 例如： A,B兩個程序共享變量 n， A對 n執(zhí)行加 1操作， B對 n執(zhí)行減 1操作，用機(jī)器語言實現(xiàn)： A： register1:=n。（ a2） n:= register1。 因此必須 互斥地 訪問 n。(b1) register2:= register21。(b3) 2022/2/17 74 一個程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作 或者 ： 把每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。 Exit section Remainder section。 進(jìn)入?yún)^(qū) 臨界區(qū) 退出區(qū) 2022/2/17 76 4. 同步機(jī)制應(yīng)遵循的原則 ? 空閑讓進(jìn) ? 忙則等待 ? 有限等待 ? 讓權(quán)等待 2022/2/17 77 信號量機(jī)制 ? 信號量機(jī)制是行之有效的 進(jìn)程同步工具 ? 學(xué)習(xí)時注意： 1）各種信號量的定義 2）信號量的應(yīng)用：解決同步問題和互斥問題 2022/2/17 78 整型信號量定義為一個整型量，除 初始化外 ，僅能通過兩 個標(biāo)準(zhǔn)的原子操作 wait(s)和 signal(s)來訪問，通常稱為 P、 V操作 wait(s):while s=0 do no_op s:=s1。 2022/2/17 79 2）信號量的使用： (1)必須置一次且只能置一次初值 ,并且初值不能為負(fù)數(shù) （ 2）只能執(zhí)行 P、 V操作 整型信號量的 缺點(diǎn) ： 未遵循同步機(jī)制的 “ 讓權(quán)等待 ” 1） P、 V操作為原語操作 說明： 2022/2/17 80 記錄型信號量機(jī)制的提出是為了解決整型信號量機(jī)制 不遵循“ 讓權(quán)等待” 這一準(zhǔn)則。 L:list of process。 begin :=。 begin :=+1。 end 注意這個條件 注意這個條件 2022/2/17 82 1) 信號量的物理含義： 信號量的初值應(yīng)該大于等于 0 S0表示有 S個資源可用 S=0表示無資源可用 P(S):表示申請一個資源 V(S)表示釋放一個資源。因此設(shè) 兩個互斥的信號量 Dmutex和 Emutex，令初值為 1。 wait(Emutex)。 wait(Dmutex)。 process B: wait(Emutex)。 process B: wait(Dmutex)。 2022/2/17 85 將進(jìn)程在整個運(yùn)行過程中需要的所有資源，一次性全部 地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。 AND同步機(jī)制的基本思想是： 2022/2/17 86 place the process in the waiting queue associated with the first Si found with Si1,and set the program count of this process to the beginning of Swait operation endif Swait(S1,S2,…,Sn) if S1≥ 1 and …and Sn ≥ 1 then for i:=1 to n do Si:=Si1。 2022/2/17 88 ? 一般信號量集是指同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的信號量處理 ? 一般信號量集的基本思路就是在 AND型信號量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語操作中完成所有的資源申請 2022/2/17 89 ? 進(jìn)程對信號量 Si的 下限值為 ti（表示信號量的判斷條件，要求 Si = ti；即當(dāng)資源數(shù)量低于 ti時，便不予分配） 占用值為 di（表示資源的申請量，即 Si = Si di） ? 對應(yīng)的 P、 V原語格式為： – Swait(S1, t1, d1。 Sn, tn, dn)。 ...。 設(shè)置： 2022/2/17 90 在信號量集機(jī)制中， Swait操作描述如下，其中 S為信號量 ， d為需求量， t為下限值。 endfor else … endif Ssignal(S1,d1,…,Sn,dn) for i:=1 to n do Si:=Si+di。 2022/2/17 91 “信號量集”的幾種特殊情況： （ 1） Swait(S,d,d)。蛻化為一般的記錄型信號量（ S1)或 互斥信號量（ S=1）。當(dāng) S≥ 1時，允許多個進(jìn)程進(jìn)入某特定區(qū)； 當(dāng) S變?yōu)?0時，將阻止任何進(jìn)程進(jìn)入特定區(qū)。 2022/2/17 92 信號量的應(yīng)用 用 P、 V操作解決進(jìn)程間互斥問題 P(mutex) V(mutex) P1 P2 P3 互斥區(qū) P(mutex) P(mutex) V(mutex) V(mutex) 2022/2/17 93 利用記錄型信號量實現(xiàn)進(jìn)程互斥的進(jìn)程 可描述如下： var mutex:semaphore:=1。 cs signal(mutex)。 cs signal(mutex)。 設(shè)一公共信號量 s，初值為 0。 在進(jìn)程 P2中：用 wait(s)。 S1 S2 S3 S4 S5 S6 a b c d e f g 2022/2/17 96 begin wait(d)。signal(g)。 begin wait(e)。wait(g)。end。 begin parbegin begin S1。signal(b)。 begin wait(a)。signal(c)。end。S3。end。S4。end。 cs。 這樣可能會有幾個進(jìn)程同時進(jìn)入臨界區(qū)。 cs。 這樣可能會發(fā)生死鎖。 2022/2/17 99 1. 管程的定義 系統(tǒng)中的所有硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)加 以抽象地描述，即用 少量信息和對該資源所執(zhí)行的操作 來表征該資源，而忽略了它們的內(nèi)部結(jié)構(gòu)和實現(xiàn)細(xì)節(jié)。 2022/2/17 100 管程由三部分組成： （ 1）局部于管程的共享變量說明 （ 2）對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程 （ 3）對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。 管程：一種同步機(jī)制 2022/2/17 101 管程的形式 TYPE monitor_name = MONITOR。 ...... 2022/2/17 102 FUNCTION 函數(shù)名（形參表）：值類型； 函數(shù)局部變量說明； BEGIN 語句序列； END。 2022/2/17 103 共享數(shù)據(jù) 一組操作進(jìn)程 初始化代碼 條件（不忙）隊列 進(jìn)入隊列 管程的示意圖 2022/2/17 104 說明：局部于管程的數(shù)據(jù)結(jié)構(gòu)， 僅能被局部于管程的過程所訪問； 反之，局部于管程的過程也僅能 訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。 2022/2/17 105 管程的三個主要的特性： （一）模塊化，一個管程是一個基本程序單位，可以單獨(dú)編譯 （二）抽象數(shù)據(jù)類型，管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進(jìn)行操作的代碼 （三）信息隱藏，管程是半透明的，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的 2022/2/17 106 管程有如下幾個要素： （一）管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量 （二）為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入 （三）管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊以及相應(yīng)的等待及喚醒操作 2022/2/17 107 管程和進(jìn)程的異同點(diǎn)： （ 1）設(shè)置進(jìn)程和管程的目的不同 （ 2）系統(tǒng)管理數(shù)據(jù)結(jié)構(gòu) 進(jìn)程： PCB 管程：等待隊列 （ 3）管程被進(jìn)程調(diào)用 （ 4）管程是操作系統(tǒng)的固有成分，無創(chuàng)建和撤消 2022/2/17 108 利用管程解決生產(chǎn)者、消費(fèi)者問題 ? 首先定義管程 ? （ 1） put(item) ? （ 2） get(item) 2022/2/17 109 經(jīng)典進(jìn)程的同步問題 P58 包括： 生產(chǎn)者－消費(fèi)者問題、讀者－寫者問題、 哲學(xué)家進(jìn)餐問題 問題：如何描述進(jìn)程同步問題？ ? 先寫出對問題的初步描述（用漢語，流程） ? 問題中存在的關(guān)系（互斥、同步，各有幾種） ? 問題的初始狀態(tài)（用于信號量初值的設(shè)置） ? 把 P、 V操作放到合適的位置 2022/2/17 110 本節(jié)主要內(nèi)容： 生產(chǎn)者 —— 消費(fèi)者問題 哲學(xué)家進(jìn)餐問題 讀者 —— 寫者問題 本節(jié)學(xué)習(xí)目標(biāo)：掌握三個經(jīng)典進(jìn)程同步問題所 解決的同步問題；理解并會分析三個經(jīng)典進(jìn)程 同步問題，重點(diǎn)掌握生產(chǎn)者 —— 消費(fèi)者問題 2022/2/17 111 生產(chǎn)者－消費(fèi)者問題 描述如下： 有一些進(jìn)程生成產(chǎn)品，稱為生產(chǎn)者；有一些 進(jìn)程使用產(chǎn)品，稱為消費(fèi)者。 設(shè)置一緩沖池用來暫存產(chǎn)品； 互斥問題： 緩沖池屬于臨界資源，對緩沖池的操作必須互斥進(jìn)行； 2022/2/17 112 同步問題： 生產(chǎn)者進(jìn)程不能往 “ 滿 ” 的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為 empty, 消費(fèi)者進(jìn)程不能從 “ 空 ” 的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量 full. empty和 full分別表示緩沖池中空緩沖區(qū)上數(shù)量和滿緩沖區(qū)的數(shù)量。 P(empty) 。 V(full)。 Q（消費(fèi)者）： while (true) { P(full)。 V(empty)。 }。 while (true) { 生產(chǎn)產(chǎn)品 。 往 Buffer [i]放產(chǎn)品 。 i = (i+1) % n。 Q： j = 0。 從 Buffer[j]取產(chǎn)品 。 消費(fèi)產(chǎn)品 。 }。 while (true) { P(full)。 從 Buffer[j]取產(chǎn)品 。 V(empty)。 j = (j+1) % n。 P： i = 0。 P(empty)。 往 Buffer [i]放產(chǎn)品 。 V(full)。 }。 while (true) { P(full)。 從 Buffer[j]取產(chǎn)品 。 V(mutex)。 消費(fèi)產(chǎn)品 。 P： i = 0。 P(empty)。 往 Buffer [i]放產(chǎn)品 。 V(mutex)。 }。 while (true) { P(full)。 從 Buffer[j]取產(chǎn)品 。 V(mutex2)。 消費(fèi)產(chǎn)品 。 自己分析是否存在問題？ P： i = 0。 P(empty)。 往 Buffer [i]放產(chǎn)品 。 V(mutex1)。 }。 buffer:array[0,…,n 1] of item。 begin parbegin producer:begin repeat . . Producer an item in nextp。 wait(mutex)。 in:=(in+1) mod n。 signal(full)。 end 教材的描述： 2022/2/17 122 consumer:begin repeat wait(full)。 nextc:=buffer(out)。 signal(mutex)。 consume the item in nextc。 end parend end 2022