【文章內(nèi)容簡介】 : semphore。 t1, t2, … , t n, d1, d2, … , d n : integer。 begin if s1 ? t1 and … and s n ? tn then for i:=1 to n do si:=si di。 else blockProcessAndResetPC(sfirstless)。 end for i:=1 to n do { if (siti) { block()。 ResetPC()。 break。 } } if (in) { for i:=1 to n do si :=si－ di。 } 67 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 Ssignal(s1, d1,… ,s n, dn)操作 procedure Ssignal(s1, d1, … , s n , dn) Var s1, s2, … , s n : semphore。 d1, d2, … , d n : integer。 begin for i:=1 to n do si:=si + di。 wakeupAllProcesses(si)。 endfor。 end 68 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 一般信號量集的幾種特殊情況 ? Swait(s, d, d) ? 信號量集中只有一個信號量，但它允許每次申請 d個資源；當(dāng)現(xiàn)有資源少于 d個時，便不予分配 ? Swait(s, 1, 1) ? 此時的信號量集已退化為一般的記錄型信號量 ? Swait(s, 1, 0) ? 一種特殊且很有用的信號量，相當(dāng)于可控開關(guān) ? 當(dāng) s?1時， 允許多個進程進入某特定區(qū)；當(dāng) s變?yōu)?0后 ，將阻止任何 進程進入該特定區(qū) 69 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程同步 并發(fā)進程間制約關(guān)系 臨界資源與臨界區(qū) 進程同步機制準(zhǔn)則 信號量機制 信號量機制應(yīng)用基礎(chǔ) 70 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 利用 信號量 實現(xiàn)互斥 ? 主程序 Var mutex: semphore:=1。 begin parbegin process1。 process2。 parend end 71 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 利用 信號量 實現(xiàn)互斥 ? 子程序 process1: begin repeat wait(mutex)。 臨界區(qū) signal(mutex)。 …… until false。 end process2: begin repeat wait(mutex)。 臨界區(qū) signal(mutex)。 …… until false。 end 72 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 信號量要 描述的前趨關(guān)系示例 S1 S2 S3 S4 S5 S6 a b c d e f g 73 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 利用 信號量 來描述前趨關(guān)系 Var a,b,c,d,e,f,g: semphore:=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。 begin wait(d)。 S5。 signal(g)。 end。 begin wait(e)。 wait(f)。 wait(g)。 S6。 end。 parend end 74 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程同步 并發(fā)進程間制約關(guān)系 臨界資源與臨界區(qū) 進程同步機制準(zhǔn)則 信號量機制 信號量機制應(yīng)用基礎(chǔ) 75 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 作業(yè)題 ? 什么是臨界資源和臨界區(qū)？試舉例說明。并談?wù)勀銓M程同步機制準(zhǔn)則的理解。 ? 試闡述你對整型信號量機制與記錄型信號量機制的完整理解以及 AND型信號量機制與一般信號量集機制的基本思想。 76 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 第二章 進程管理 進程的基本概念 進程控制 進程同步 經(jīng)典進程同步問題 進程通信 管程與線程 77 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 經(jīng)典進程同步問題 生產(chǎn)者 —消費者問題 哲學(xué)家進餐問題 讀者 —寫者問題 78 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者 ? 消費者問題背景 ? 生產(chǎn)者 —消費者問題是相互合作進程關(guān)系的一種抽象 ? 輸入時的輸入進程與計算進程 ? 輸出時的計算進程與輸出進程 ? 生產(chǎn)者 —消費者問題具有很大的代表性和實用價值 ? 計算機系統(tǒng) ?IPO系統(tǒng) 79 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者 ? 消費者問題描述 ? 生產(chǎn)者進程在生產(chǎn)數(shù)據(jù)，并將此數(shù)據(jù)提供給消費者進程消費 ? 為使二者可以并發(fā)執(zhí)行，在它們之間設(shè)置了一個具有 n個緩沖區(qū)的循環(huán)緩沖，生產(chǎn)者進程可以將它所生產(chǎn)的數(shù)據(jù)放入一個緩沖區(qū)中，消費者進程可以從一個緩沖區(qū)中取得一個數(shù)據(jù)消費 ? 異步運行方式及 彼此必須保持同步 80 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 ? 空緩沖區(qū)與滿緩沖區(qū) ? 空緩沖區(qū)是指未投放數(shù)據(jù)或雖曾投放數(shù)據(jù)但對應(yīng)數(shù)據(jù)已被取走的緩沖區(qū) ? 滿緩沖區(qū)則指已投放數(shù)據(jù)且對應(yīng)數(shù)據(jù)尚未被取走的緩沖區(qū) ? 進程同步 ? 當(dāng)生產(chǎn)者進程要把所生產(chǎn)的數(shù)據(jù)送入循環(huán)緩沖時，首先應(yīng)檢查是否有空緩沖區(qū)存在，若有，則可向?qū)?yīng)空緩沖區(qū)中投放數(shù)據(jù)，同時通知消費者進程；否則只有等待。 ? 當(dāng)消費者進程要從循環(huán)緩沖中提取數(shù)據(jù)時，首先應(yīng)檢查是否有滿緩沖區(qū)存在，若有，則從對應(yīng)滿緩沖區(qū)中提取數(shù)據(jù)，并通知生產(chǎn)者進程，否則只有等待。 ? 進程互斥 ? 循環(huán)緩沖是一個臨界資源： 單 /多個生產(chǎn)者 /消費者進程 生產(chǎn)者－消費者問題剖析 81 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者 ? 消費者問題臨界資源剖析 0 n3 n2 n1 1 2 3 … 指針移動方向 輸出指針 out 輸入指針 in 消費者1 消費者2 消費者3 …… 消費者X 生產(chǎn)者 1 生產(chǎn)者 2 生產(chǎn)者 3 …… 生產(chǎn)者 Y 82 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者 ? 消費者程序變量設(shè)計 ? 循環(huán)緩沖表示機制 ? 一維數(shù)組 buffer: array [0..n1] of item。 ? 輸入指針 in ? 指示下一個可以投放數(shù)據(jù)的緩沖區(qū) ? 初始值為 0；變化方式： in ?? (in+1) mod n ? 輸出指針 out ? 指示下一個可以獲取數(shù)據(jù)的緩沖區(qū) ? 初始值為 0；變化方式： out??(out+1) mod n ? nextp/nextc暫存每次要生產(chǎn)或消費的數(shù)據(jù) 83 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者 ? 消費者程序信號量設(shè)計 ? 循環(huán)緩沖的互斥使用 ? 互斥信號量 mutex，初始值為 1 ? 資源信號量 ? empty 表示循環(huán)緩沖中的空緩沖區(qū)的數(shù)量，其初始值為 n ? full 表示循環(huán)緩沖中的滿緩沖區(qū)的數(shù)量，其初始值為 0 84 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者－消費者主程序設(shè)計 Var buffer: array [0..n1] of item。 in, out: integer ?? 0, 0。 mutex, empty, full : semphore ?? 1, n, 0 。 begin parbegin producer1。 …。 producer i。 …。 producer Y。 consumer1。 …。 consumer j。 …。 consumer X。 parend end 85 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者子程序設(shè)計 produceri: Var nextp: item。 begin repeat produce an item in nextp。 wait(empty)。 wait(mutex)。 buffer[in] ?? nextp。 in ?? (in+1) mod n。 signal(mutex)。 signal(full)。 until false。 end 86 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 消費者子程序設(shè)計 consumerj: Var nextc: item。 begin repeat wait(full)。 wait(mutex)。 nextc??buffer[out]。 out ?? (out+1) mod n。 signal(mutex)。 signal(empty)。 consume the item in nextc。 until false。 end 87 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 同步問題程序設(shè)計要領(lǐng) ? 每個并發(fā)子程序關(guān)于互斥信號量的 wait與 signal操作必須在同一子程序中成對出現(xiàn) ? 關(guān)于資源信號量的 wait與 signal操作同樣需成對出現(xiàn)，但可以分別處于不同的并發(fā)子程序中 ? 每個并發(fā)子程序中的多個 wait操作的順序不能顛倒，即資源信號量 wait操作執(zhí)行在前而互斥信號量 wait操作執(zhí)行在后，否則可能引起死鎖 ? 每個并發(fā)子程序中的多個 signal 操作的執(zhí)行順序無關(guān)緊要 ? 非臨界資源訪問操作無需放到臨界區(qū)中 88 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 基于 AND信號量的生產(chǎn) /消費者子程序設(shè)計 produceri: begin repeat produce an item in nextp。 Swait(empty, mutex)。 buffer[in] ?? nextp。 in ?? (in+1) mod n。 Ssignal(mutex, full)。 until false。 end consumerj: begin repeat Swait(full, mutex)。 nextc??buffer[out]。 out ?? (out+1) mod n。 Ssignal(mutex, empty)。 consume the item in nextc。 until false。 end 89 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 經(jīng)典進程同步問題 生產(chǎn)者 —消費者問題 哲學(xué)家進餐問題 讀者 —寫者問題 90 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 哲學(xué)家進餐問題描述 ? 哲學(xué)家進餐問題是典型的同步問題 ? 五個哲學(xué)家共用一張圓桌，分別坐在環(huán)桌均勻擺放的五張椅子上，并全部執(zhí)行同為交替地進行思考和進餐的生活方式 ? 圓桌上放有五支筷子，均勻排放在哲學(xué)家之間的位置上 ? 哲學(xué)家饑餓時便試圖去取用圓桌上最靠近他左右兩端的兩支筷子，且只有在同時拿到兩支筷子時方可進餐，進餐完畢則把筷子放回原處，并繼續(xù)進行思考 91 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 哲學(xué)家進餐問題剖析 (待續(xù) ) ?