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