【文章內(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é)計(jì)算機(jī)學(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é)計(jì)算機(jī)學(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時， 允許多個進(jìn)程進(jìn)入某特定區(qū)；當(dāng) s變?yōu)?0后 ，將阻止任何 進(jìn)程進(jìn)入該特定區(qū) 69 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 進(jìn)程同步 并發(fā)進(jìn)程間制約關(guān)系 臨界資源與臨界區(qū) 進(jìn)程同步機(jī)制準(zhǔn)則 信號量機(jī)制 信號量機(jī)制應(yīng)用基礎(chǔ) 70 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 利用 信號量 實(shí)現(xiàn)互斥 ? 主程序 Var mutex: semphore:=1。 begin parbegin process1。 process2。 parend end 71 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 利用 信號量 實(shí)現(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é)計(jì)算機(jī)學(xué)院 信號量要 描述的前趨關(guān)系示例 S1 S2 S3 S4 S5 S6 a b c d e f g 73 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(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é)計(jì)算機(jī)學(xué)院 進(jìn)程同步 并發(fā)進(jìn)程間制約關(guān)系 臨界資源與臨界區(qū) 進(jìn)程同步機(jī)制準(zhǔn)則 信號量機(jī)制 信號量機(jī)制應(yīng)用基礎(chǔ) 75 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 作業(yè)題 ? 什么是臨界資源和臨界區(qū)？試舉例說明。并談?wù)勀銓M(jìn)程同步機(jī)制準(zhǔn)則的理解。 ? 試闡述你對整型信號量機(jī)制與記錄型信號量機(jī)制的完整理解以及 AND型信號量機(jī)制與一般信號量集機(jī)制的基本思想。 76 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 第二章 進(jìn)程管理 進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程同步問題 進(jìn)程通信 管程與線程 77 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 經(jīng)典進(jìn)程同步問題 生產(chǎn)者 —消費(fèi)者問題 哲學(xué)家進(jìn)餐問題 讀者 —寫者問題 78 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 ? 消費(fèi)者問題背景 ? 生產(chǎn)者 —消費(fèi)者問題是相互合作進(jìn)程關(guān)系的一種抽象 ? 輸入時的輸入進(jìn)程與計(jì)算進(jìn)程 ? 輸出時的計(jì)算進(jìn)程與輸出進(jìn)程 ? 生產(chǎn)者 —消費(fèi)者問題具有很大的代表性和實(shí)用價(jià)值 ? 計(jì)算機(jī)系統(tǒng) ?IPO系統(tǒng) 79 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 ? 消費(fèi)者問題描述 ? 生產(chǎn)者進(jìn)程在生產(chǎn)數(shù)據(jù)，并將此數(shù)據(jù)提供給消費(fèi)者進(jìn)程消費(fèi) ? 為使二者可以并發(fā)執(zhí)行，在它們之間設(shè)置了一個具有 n個緩沖區(qū)的循環(huán)緩沖，生產(chǎn)者進(jìn)程可以將它所生產(chǎn)的數(shù)據(jù)放入一個緩沖區(qū)中，消費(fèi)者進(jìn)程可以從一個緩沖區(qū)中取得一個數(shù)據(jù)消費(fèi) ? 異步運(yùn)行方式及 彼此必須保持同步 80 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 ? 空緩沖區(qū)與滿緩沖區(qū) ? 空緩沖區(qū)是指未投放數(shù)據(jù)或雖曾投放數(shù)據(jù)但對應(yīng)數(shù)據(jù)已被取走的緩沖區(qū) ? 滿緩沖區(qū)則指已投放數(shù)據(jù)且對應(yīng)數(shù)據(jù)尚未被取走的緩沖區(qū) ? 進(jìn)程同步 ? 當(dāng)生產(chǎn)者進(jìn)程要把所生產(chǎn)的數(shù)據(jù)送入循環(huán)緩沖時，首先應(yīng)檢查是否有空緩沖區(qū)存在，若有，則可向?qū)?yīng)空緩沖區(qū)中投放數(shù)據(jù)，同時通知消費(fèi)者進(jìn)程；否則只有等待。 ? 當(dāng)消費(fèi)者進(jìn)程要從循環(huán)緩沖中提取數(shù)據(jù)時，首先應(yīng)檢查是否有滿緩沖區(qū)存在，若有，則從對應(yīng)滿緩沖區(qū)中提取數(shù)據(jù)，并通知生產(chǎn)者進(jìn)程，否則只有等待。 ? 進(jìn)程互斥 ? 循環(huán)緩沖是一個臨界資源： 單 /多個生產(chǎn)者 /消費(fèi)者進(jìn)程 生產(chǎn)者－消費(fèi)者問題剖析 81 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 ? 消費(fèi)者問題臨界資源剖析 0 n3 n2 n1 1 2 3 … 指針移動方向 輸出指針 out 輸入指針 in 消費(fèi)者1 消費(fèi)者2 消費(fèi)者3 …… 消費(fèi)者X 生產(chǎn)者 1 生產(chǎn)者 2 生產(chǎn)者 3 …… 生產(chǎn)者 Y 82 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 ? 消費(fèi)者程序變量設(shè)計(jì) ? 循環(huán)緩沖表示機(jī)制 ? 一維數(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)或消費(fèi)的數(shù)據(jù) 83 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者 ? 消費(fèi)者程序信號量設(shè)計(jì) ? 循環(huán)緩沖的互斥使用 ? 互斥信號量 mutex，初始值為 1 ? 資源信號量 ? empty 表示循環(huán)緩沖中的空緩沖區(qū)的數(shù)量，其初始值為 n ? full 表示循環(huán)緩沖中的滿緩沖區(qū)的數(shù)量，其初始值為 0 84 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 生產(chǎn)者－消費(fèi)者主程序設(shè)計(jì) 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é)計(jì)算機(jī)學(xué)院 生產(chǎn)者子程序設(shè)計(jì) 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é)計(jì)算機(jī)學(xué)院 消費(fèi)者子程序設(shè)計(jì) 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é)計(jì)算機(jī)學(xué)院 同步問題程序設(shè)計(jì)要領(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é)計(jì)算機(jī)學(xué)院 基于 AND信號量的生產(chǎn) /消費(fèi)者子程序設(shè)計(jì) 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é)計(jì)算機(jī)學(xué)院 經(jīng)典進(jìn)程同步問題 生產(chǎn)者 —消費(fèi)者問題 哲學(xué)家進(jìn)餐問題 讀者 —寫者問題 90 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 哲學(xué)家進(jìn)餐問題描述 ? 哲學(xué)家進(jìn)餐問題是典型的同步問題 ? 五個哲學(xué)家共用一張圓桌，分別坐在環(huán)桌均勻擺放的五張椅子上，并全部執(zhí)行同為交替地進(jìn)行思考和進(jìn)餐的生活方式 ? 圓桌上放有五支筷子，均勻排放在哲學(xué)家之間的位置上 ? 哲學(xué)家饑餓時便試圖去取用圓桌上最靠近他左右兩端的兩支筷子，且只有在同時拿到兩支筷子時方可進(jìn)餐，進(jìn)餐完畢則把筷子放回原處，并繼續(xù)進(jìn)行思考 91 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 哲學(xué)家進(jìn)餐問題剖析 (待續(xù) ) ?