【文章內(nèi)容簡介】 配給進(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。 endfor else AND同步（或稱同時(shí) wait操作）： 2022/2/17 87 Ssignal(S1,S2,… ,Sn) for i:=1 to n do Si:=Si+1 remove all the process waiting in the queue associated with Si intothe ready queue. endfor。 2022/2/17 88 ? 一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理 ? 一般信號(hào)量集的基本思路就是在 AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語操作中完成所有的資源申請(qǐng) 2022/2/17 89 ? 進(jìn)程對(duì)信號(hào)量 Si的 下限值為 ti（表示信號(hào)量的判斷條件，要求 Si = ti；即當(dāng)資源數(shù)量低于 ti時(shí)，便不予分配） 占用值為 di（表示資源的申請(qǐng)量，即 Si = Si di） ? 對(duì)應(yīng)的 P、 V原語格式為： – Swait(S1, t1, d1。 ...。 Sn, tn, dn)。 – Ssignal(S1, d1。 ...。 Sn, dn)。 設(shè)置： 2022/2/17 90 在信號(hào)量集機(jī)制中， Swait操作描述如下，其中 S為信號(hào)量 ， d為需求量， t為下限值。 Swait(S1,t1,d1,…,Sn,tn,dn) if S1≥ t1 and …and Sn ≥ tn then for i:=1 to n do Si:=Sidi。 endfor else … endif Ssignal(S1,d1,…,Sn,dn) for i:=1 to n do Si:=Si+di。 … endfor。 2022/2/17 91 “信號(hào)量集”的幾種特殊情況： （ 1） Swait(S,d,d)。 （ 2） Swait(S,1,1)。蛻化為一般的記錄型信號(hào)量（ S1)或 互斥信號(hào)量（ S=1）。 （ 3） Swait(S,1,0)。當(dāng) S≥ 1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)； 當(dāng) S變?yōu)?0時(shí)，將阻止任何進(jìn)程進(jìn)入特定區(qū)。相當(dāng)于一個(gè)可 控開關(guān)。 2022/2/17 92 信號(hào)量的應(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 利用記錄型信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程 可描述如下： var mutex:semaphore:=1。 begin parbegin process1:begin repeat wait(mutex)。 cs signal(mutex)。 remainder section until false end 2022/2/17 94 wait(mutex)。 cs signal(mutex)。 remainder section until false end parend process 2:begin repeat 注： wait和 signal必須成對(duì)出現(xiàn) 2022/2/17 95 設(shè)有兩個(gè)并發(fā)執(zhí)行的進(jìn)程 P1和 P2， 要求 P1中的語句 S1先于 P2中的 S2執(zhí)行。 設(shè)一公共信號(hào)量 s，初值為 0。 在進(jìn)程 P1中：用 S1； signal(s)。 在進(jìn)程 P2中：用 wait(s)。S2。 S1 S2 S3 S4 S5 S6 a b c d e f g 2022/2/17 96 begin wait(d)。S5。signal(g)。end。 begin wait(e)。wait(f)。wait(g)。S6。end。 parend end var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0。 begin parbegin begin S1。signal(a)。signal(b)。end。 begin wait(a)。S2。signal(c)。signal(d)。end。 begin wait(b)。S3。signal(e)。end。 begin wait( c )。S4。signal(f)。end。 2022/2/17 97 管程機(jī)制 信號(hào)量機(jī)制的不足：每個(gè)要訪問臨界資源的進(jìn)程必須自備 同步操作 wait(s)和 signal(s) 例子： 錯(cuò)誤 1 在利用互斥信號(hào)量 mutex實(shí)現(xiàn)進(jìn)程互斥時(shí)，將 wait(s)和 signal(s)顛倒，即 signal(mutex)。 cs。 wait(mutex)。 這樣可能會(huì)有幾個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。 2022/2/17 98 錯(cuò)誤 2 在實(shí)現(xiàn)進(jìn)程互斥時(shí)，將程序中的 signal(mutex)誤寫為 wait(mutex),即 wait(mutex)。 cs。 wait(mutex)。 這樣可能會(huì)發(fā)生死鎖。 基于上述情況，提出了 管程 (Monitors） 概念。 2022/2/17 99 1. 管程的定義 系統(tǒng)中的所有硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)加 以抽象地描述，即用 少量信息和對(duì)該資源所執(zhí)行的操作 來表征該資源，而忽略了它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。 如，一個(gè) FIFO隊(duì)列，可用其隊(duì)長、隊(duì)首和隊(duì)尾以及在該隊(duì) 列上所執(zhí)行的一組操作來描述。 2022/2/17 100 管程由三部分組成： （ 1）局部于管程的共享變量說明 （ 2）對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程 （ 3）對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語句。 管程的定義：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能 為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操 作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。 管程：一種同步機(jī)制 2022/2/17 101 管程的形式 TYPE monitor_name = MONITOR。 共享變量說明 PROCEDURE 過程名（形參表）； 過程局部變量說明； BEGIN 語句序列； END。 ...... 2022/2/17 102 FUNCTION 函數(shù)名（形參表）：值類型； 函數(shù)局部變量說明； BEGIN 語句序列； END。 ...... BEGIN 共享變量初始化語句序列； END。 2022/2/17 103 共享數(shù)據(jù) 一組操作進(jìn)程 初始化代碼 條件（不忙）隊(duì)列 進(jìn)入隊(duì)列 管程的示意圖 2022/2/17 104 說明：局部于管程的數(shù)據(jù)結(jié)構(gòu)， 僅能被局部于管程的過程所訪問； 反之，局部于管程的過程也僅能 訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。 可以把管程看作是圍墻。 2022/2/17 105 管程的三個(gè)主要的特性： （一）模塊化，一個(gè)管程是一個(gè)基本程序單位，可以單獨(dú)編譯 （二）抽象數(shù)據(jù)類型，管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對(duì)數(shù)據(jù)進(jìn)行操作的代碼 （三）信息隱藏，管程是半透明的，管程中的外部過程（函數(shù)）實(shí)現(xiàn)了某些功能，至于這些功能是怎樣實(shí)現(xiàn)的，在其外部則是不可見的 2022/2/17 106 管程有如下幾個(gè)要素： （一）管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量 （二）為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入 （三）管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)以及相應(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 管程：等待隊(duì)列 （ 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)程同步問題？ ? 先寫出對(duì)問題的初步描述（用漢語，流程） ? 問題中存在的關(guān)系（互斥、同步，各有幾種） ? 問題的初始狀態(tài)（用于信號(hào)量初值的設(shè)置） ? 把 P、 V操作放到合適的位置 2022/2/17 110 本節(jié)主要內(nèi)容： 生產(chǎn)者 —— 消費(fèi)者問題 哲學(xué)家進(jìn)餐問題 讀者 —— 寫者問題 本節(jié)學(xué)習(xí)目標(biāo)：掌握三個(gè)經(jīng)典進(jìn)程同步問題所 解決的同步問題；理解并會(huì)分析三個(gè)經(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)者。 生產(chǎn)者和消費(fèi)者必須同步 。 設(shè)置一緩沖池用來暫存產(chǎn)品； 互斥問題： 緩沖池屬于臨界資源，對(duì)緩沖池的操作必須互斥進(jìn)行； 2022/2/17 112 同步問題： 生產(chǎn)者進(jìn)程不能往 “ 滿 ” 的緩沖區(qū)中放產(chǎn)品，設(shè)置信號(hào)量為 empty, 消費(fèi)者進(jìn)程不能從 “ 空 ” 的緩沖區(qū)中取產(chǎn)品，設(shè)置信號(hào)量 full. empty和 full分別表示緩沖池中空緩沖區(qū)上數(shù)量和滿緩沖區(qū)的數(shù)量。 2022/2/17 113 消費(fèi)者 生產(chǎn)者 單緩沖 －消費(fèi)者 問題 2022/2/17 114 P(生產(chǎn)者）： while (true) { 生產(chǎn)一個(gè)產(chǎn)品 。 P(empty) 。 送產(chǎn)品到緩沖區(qū) 。 V(full)。 }。 Q（消費(fèi)者）： while (true) { P(full)。 從緩沖區(qū)取產(chǎn)品 。 V(empty)。 消費(fèi)產(chǎn)品 。 }。 empty初值為 1， full初值為 0 2022/2/17 115 ......P Q放消息 取消息nn 個(gè)緩沖區(qū)(Buffer)ij2022/2/17 116 多個(gè)緩沖區(qū)的生產(chǎn)者 消費(fèi)者問題 (1) P： i = 0。 while (true) { 生產(chǎn)產(chǎn)品 。 P(empty)。 往 Buffer [i]放產(chǎn)品 。 V(full)。 i = (i+1) % n。 }。 Q： j = 0。 while (true) { P(full)。 從 Buffer[j]取產(chǎn)品 。 V(empty)。 消費(fèi)產(chǎn)品 。 j = (j+1) % n。 }。 2022/2/17 117 【 思考題 】 要不要對(duì)緩沖區(qū)（臨界資源）進(jìn)行互斥操作？ 存在問題 ： 1)會(huì)造成多個(gè)生產(chǎn)者向同一個(gè)緩沖區(qū) 放產(chǎn)品； 2)會(huì)造成多個(gè)消費(fèi)者從同一個(gè)緩沖區(qū) 取產(chǎn)品 2022/2/17 118 Q： j = 0。 while (true) { P(full)。 P(mutex)。 從 Buffer[j]取產(chǎn)品 。 V(mutex)。 V(empty)。 消費(fèi)產(chǎn)品 。 j = (j+1) % n。 }。 P： i = 0。