【正文】 END。 nextc??buffer[out]。 if then ()。 BEGIN if count=n then ()。 var in, out, count : integer。 136 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者 消費者管程設(shè)計要領(lǐng) ? 循環(huán)緩沖及操作機制 ? 循環(huán)緩沖 buffer: array [0..n1] of item。 signal(empty)。 wait(mutex)。 until false。 buffer[in] ?? nextp。 …… BEGIN 初始化語句序列 END 132 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 管程關(guān)于進程同步互斥的保證 ? 管程特性 ? 數(shù)據(jù)結(jié)構(gòu)與操作代碼的封裝性 ? 管程每次只準許一個進程進入以保證互斥 ? 條件變量 ? 進程同步操作必需設(shè)置原語 wait與 signal ? 為區(qū)別等待原因而引入條件變量 ? 不同條件變量設(shè)有不同進程等待隊列 ? signal操作處理方式 133 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 管程與線程 管程的基本概念 利用管程解決生產(chǎn)者 —消費者問題 線程的基本概念 線程的控制 線程間的同步與通信 線程的實現(xiàn)機制 134 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 基于管程的生產(chǎn)者子程序設(shè)計 producer: Var nextp: item。 putbuf(Bufferj)。 signal()。 125 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 消息緩沖隊列通信機制 接收原語 Procedure Receive(RB) Begin PID ?? InternalNameOfProcess。 insert(,Bufferi)。 ?? 。 // 消息隊列資源信號量 …… End。 // 指向下一緩沖區(qū)的指針 End。 118 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 間接通信方式 ? 信箱 ? 進程間通信有關(guān)共享數(shù)據(jù)結(jié)構(gòu)的中間實體 ? 由操作系統(tǒng)或用戶進程創(chuàng)建 ? 私有 /公有 /共享信箱 ? 可實現(xiàn)實時 /非實時通信 ? 通信原語 ? 信箱的創(chuàng)建和撤銷、消息的發(fā)送和接收 ? 發(fā)送 /接收進程間存在的四種關(guān)系 ? 一對一、多對一、一對多、多對多 119 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程通信 進程通信概念及分類 消息傳遞通信實現(xiàn)方式 消息傳遞系統(tǒng)實現(xiàn)若干問題 消息緩沖隊列通信機制 120 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 消息傳遞系統(tǒng)中的幾個問題 ? 通信鏈路 ? 顯式 /隱式建立（計算機網(wǎng)絡(luò) /單機） ? 點 點或多點連接通信鏈路 ? 單向 /雙向通信鏈路 ? 無容量 /有容量通信鏈路（緩沖區(qū)） ? 消息格式 ? 有消息頭和消息正文構(gòu)成，分定 /變長兩種 ? 進程同步方式 ? 發(fā)送 /接收進程阻塞與否（三種情況） 121 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程通信 進程通信概念及分類 消息傳遞通信實現(xiàn)方式 消息傳遞系統(tǒng)實現(xiàn)若干問題 消息緩沖隊列通信機制 122 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 消息緩沖隊列通信機制 數(shù)據(jù)結(jié)構(gòu) ? 消息緩沖區(qū) type MessageBuffer = record Sender。 signal(empty)。 wait(mutex)。 until false。 buffer[in] ?? nextp。 110 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 第二章 進程管理 進程的基本概念 進程控制 進程同步 經(jīng)典進程同步問題 進程通信 管程與線程 111 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程通信 進程通信概念及分類 消息傳遞通信實現(xiàn)方式 消息傳遞系統(tǒng)實現(xiàn)若干問題 消息緩沖隊列通信機制 112 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程通信概念與實現(xiàn)機制 ? 進程通信概念 ? 指進程之間的信息交換 ? 實現(xiàn)機制 ? 低級進程通信：效率低，操作系統(tǒng)僅提供共享存儲器，通信對用戶不透明和不方便 ? 高級進程通信：能傳送大量數(shù)據(jù)，效率高，進程通信實現(xiàn)細節(jié)由操作系統(tǒng)提供，整個通信過程對用戶透明，通信程序編制簡單 113 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程通信的類型 ? 共享存儲器系統(tǒng) ? 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 ? 基于共享存儲區(qū)的通信方式 ? 消息傳遞系統(tǒng) ? 直接 /間接通信方式 ? 管道通信 ? 管道概念 ? 協(xié)調(diào)機制：互斥、同步、通信前提 114 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 進程通信 進程通信概念及分類 消息傳遞通信實現(xiàn)方式 消息傳遞系統(tǒng)實現(xiàn)若干問題 消息緩沖隊列通信機制 115 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 直接通信方式 ? 通信原語 ? Send(Receiver, message) ? Receive(Sender, message) ? 一個接收進程可與多個發(fā)送進程通信 ? 打印進程 ? Sender無法事先指定 ? 基于進程直接通信原語的應(yīng)用 ? 生產(chǎn)者 消費者通信過程 116 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 基于通信原語的生產(chǎn)者子程序設(shè)計 producer: Var nextp: item。 Ssignal(wmutex, 1)。 …… Ssignal(rMax, 1)。 writern。 writer1。 … 。 until false。 until false。 wait(rmutex)。 if readercount=0 then wait(wmutex)。 writerj 。 … 。 rmutex, wmutex : semphore ?? 1, 1。 Ssignal(chopstick[(i+1)mod 5], chopstick[i])。 … philosophy4。 0 3 2 1 4 0 4 3 2 1 92 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 哲學(xué)家進餐問題剖析 (續(xù) ) ? 上述解決方案在五個哲學(xué)家同時饑餓且各自拿起左邊筷子的情況下會引起死鎖 ? 避免死鎖的三種方法 ① 至多允許四個哲學(xué)家同時進餐，以保證至少有一個哲學(xué)家可以同時拿到兩支筷子而進餐 ② 僅當哲學(xué)家左右兩支筷子均可使用時，才允許他拿筷進餐 ③ 奇數(shù)號哲學(xué)家先拿左筷后拿右筷；而偶數(shù)號哲學(xué)家則相反 0 3 2 1 4 0 4 3 2 1 93 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 哲學(xué)家進餐主程序設(shè)計 Var chopstick: array[0..4] of semphore??(1,1,1,1,1)。 Eat。 consume the item in nextc。 end consumerj: begin repeat Swait(full, mutex)。 buffer[in] ?? nextp。 consume the item in nextc。 nextc??buffer[out]。 until false。 buffer[in] ?? nextp。 parend end 85 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 生產(chǎn)者子程序設(shè)計 produceri: Var nextp: item。 …。 producer i。 in, out: integer ?? 0, 0。 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ū) ? 進程同步 ? 當生產(chǎn)者進程要把所生產(chǎn)的數(shù)據(jù)送入循環(huán)緩沖時，首先應(yīng)檢查是否有空緩沖區(qū)存在，若有，則可向?qū)?yīng)空緩沖區(qū)中投放數(shù)據(jù)，同時通知消費者進程；否則只有等待。 end。 begin wait(e)。 begin wait(d)。 begin wait(c)。 begin wait(b)。 S2。 signal(a)。 臨界區(qū) signal(mutex)。 parend end 71 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 利用 信號量 實現(xiàn)互斥 ? 子程序 process1: begin repeat wait(mutex)。 endfor。 } 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。 end for i:=1 to n do { if (siti) { block()。 66 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 Swait(s1, t1, d1, … , s n , tn, dn)操作 procedure Swait(s1, t1, d1, … , s n , tn, dn) Var s1, s2, … , s n : semphore。當一次需 d個某類臨界資源時，便需要進行 d次 wait(s)操作，這顯然是低效的。 begin for i:=1 to n do si:=si + 1。 ResetPC()。 …… …… ? 對策： 若干個臨界資源的分配采取原子操作方式 63 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 Swait(s1, s2, … , s n)操作 procedure Swait(s1, s2, … , s n) Var s1, s2, … , s n : semphore。 end 62 2022年 10月 23日星期日 北京交通大學(xué)計算機學(xué)院 AND型 信號量集機制的引入 ? 對于多個進程要共享兩個以上的資源的情況，上述機制則可能導(dǎo)致發(fā)生死鎖 ? 例兩個進程 A、 B要求同時訪問共享數(shù)據(jù) C、 D process