1、第5章 并行性：同步和互斥,概述 臨界段 互斥 信號(hào)量 管程 進(jìn)程間的通信,5.1 概 述,并行技術(shù)的發(fā)展 并發(fā)環(huán)境中進(jìn)程間的關(guān)系 進(jìn)程同步 進(jìn)程互斥,一、并行技術(shù)的發(fā)展,多道程序設(shè)計(jì) 多處理器系統(tǒng) 分布式處理系統(tǒng),二、并發(fā)環(huán)境中進(jìn)程間的關(guān)系,間接制約關(guān)系： 源于資源共享 直接制約關(guān)系： 源于進(jìn)程合作,三、進(jìn)程同步,同步關(guān)系： 指散布在不同進(jìn)程中的若干程序片段，它 們的運(yùn)行必須嚴(yán)格按照規(guī)定的某種先后次 序來進(jìn)行，這種先后次序依賴于要完成的 任務(wù)。 同步機(jī)制： 保證這種同步關(guān)系相應(yīng)機(jī)制為同步機(jī)制。,例：一個(gè)用戶作業(yè)：兩個(gè)矩陣求逆后相加,加法進(jìn)程,求逆進(jìn)程,求逆進(jìn)程,進(jìn)程之間有一定的先后執(zhí)行次序,

2、例: 司機(jī) P1 售票員 P2 while (true) while (true) 啟動(dòng)車輛； 關(guān)門； 正常運(yùn)行； 售票； 到站停車； 開門； ,四 、進(jìn)程互斥,互斥關(guān)系：（間接制約） 指散布在不同進(jìn)程中的若干程序片段，當(dāng) 某個(gè)進(jìn)程運(yùn)行其中一個(gè)程序片段時(shí)，其它 進(jìn)程就不能運(yùn)行它們中的任一程序片段， 只能等到該進(jìn)程運(yùn)行完這個(gè)程序片段后才 可運(yùn)行。 互斥可看成是一種特殊的同步關(guān)系。,5.2 臨界段,臨界段的提出 臨界段的互斥要求,一、臨界段的提出,兩個(gè)例子（進(jìn)程的輸出結(jié)果取決于進(jìn)程運(yùn)行的精確時(shí)序） 臨界資源：一次僅能為一個(gè)進(jìn)程使用的 資源。 硬件資源：輸入機(jī)，打印機(jī)。 軟件資源：變量，隊(duì)列，表格。

3、 臨界段：進(jìn)程中訪問共享變量的代碼段。,二、使用臨界段的原則：,有空讓進(jìn)：當(dāng)無進(jìn)程在臨界段時(shí)，任何有權(quán)使用 臨界段的進(jìn)程可進(jìn)入 無空等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界 段 多中擇一：當(dāng)無進(jìn)程在臨界段，而同時(shí)有多個(gè)進(jìn) 程要求進(jìn)入臨界段，只能讓其中之一 進(jìn)入臨界段，其他進(jìn)程須等待 有限等待：任何進(jìn)入臨界段的要求應(yīng)在有限的時(shí) 間內(nèi)得到滿足 讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU， 以使其他進(jìn)程有機(jī)會(huì)使用CPU,5.3 互斥,進(jìn)程互斥的解決方法： 1、互斥的軟件方法 2、互斥的硬件方法,硬件方法,允許在一個(gè)存儲(chǔ)周期內(nèi)測試和修改一個(gè)字的 內(nèi)容，或者交換兩個(gè)字的內(nèi)容，指令的執(zhí)行 不可中斷。 TS

4、指令 SWAP指令 開關(guān)中斷指令,硬件解法 (1) “測試并設(shè)置”TS指令,function TS (var flag: boolean):boolean begin TS:= flag; flag:= true; end;,while TS(lock) do skip; 臨界段 lock ：= false;,硬件解法 (2) “交換”SWAP指令,procedure SWAP ( var a,b:boolean) begin temp:=a; a := b; b: = temp; end,key := true; repeat SWAP(lock,key); until key = fals

5、e; 臨界區(qū) lock:=false;,硬件解法 (3) “開關(guān)中斷”指令,進(jìn)入臨界區(qū)前執(zhí)行： 執(zhí)行“關(guān)中斷”指令 離開臨界區(qū)后執(zhí)行： 執(zhí)行“開中斷”指令,5.4 信號(hào)量,信號(hào)量概念 信號(hào)量及同步原語 信號(hào)量的應(yīng)用,一、信號(hào)量的概念,1、概念：信號(hào)量表示資源的物理實(shí)體，是一個(gè)與隊(duì)列有關(guān)的整體變量，除對(duì)其初始化外，其值僅能由wait和signal兩種不可中斷的操作來改變。 2、對(duì)信號(hào)量S的操作有兩個(gè)：wait 與signal。(又稱同步原語）表示為wait(s),signal(s).,二、信號(hào)量及同步原語,1、信號(hào)量分類 二元信號(hào)量：它允許取值僅為0，1，其初始值為1，主要用于解決進(jìn)程互斥問題。

6、 一般信號(hào)量：取值不限于0和1，其初值為0或?yàn)槟硞€(gè)正整數(shù)n，主要用于進(jìn)程間的同步。 2、同步原語的實(shí)現(xiàn) 同步原語的描述有兩種不同的形式： 阻塞等待方式，忙等待方式。,（1）阻塞等待方式,WAIT（S）,判斷S,進(jìn)程繼續(xù),阻塞該進(jìn)程 將進(jìn)程插入S的等待隊(duì)列L中，重新調(diào)度,SIGNAL（S）,S=S+1,判斷S,進(jìn)程 繼續(xù),喚醒等待隊(duì)列中的一個(gè)進(jìn)程，重新調(diào)度,S0,S0,S=0,S=S-1,S=0,信號(hào)量的數(shù)據(jù)結(jié)構(gòu),(將信號(hào)量定義進(jìn)一步擴(kuò)充） type s = record value : integer ; L : pointer to PCB; 指向等待隊(duì)列的指針 end,一般信號(hào)量上的同步原

7、語wait(s) : s.value := s.value -1; if s.value 0 then begin Insert ( CALLER , s.L); Block (CALLER ) ; end,一般信號(hào)量上的同步原語signal(s) : if s.value =1 then begin remove (s.L , id) ; wakeup (id) ; end,二元信號(hào)量上的同步原語waitB(s) : if s.value =1 then s.value = 0 else beginInsert ( CALLER , s.L) ;Block ( CALLER ); end,二

8、元信號(hào)量上的同步原語signalB(s) : if L.queue is empty then s.value = 1 else beginRemove ( s.L , id) ;wakeup ( id ); end,(2)忙等待方式,一般信號(hào)量的同步原語 二元信號(hào)量的同步原語 WAIT（S） WAITB（S）,S0,SS-1,N,S=0,SS-1,N,SIGNAL（S） SIGNALB（S）,S S-1 S S-1,Y,Y,信號(hào)量定義為整型變量,Wait(s): while s = 0 do skip; s:= s-1; signal(s): s := s+1;,忙等待方式和阻塞方式的差別在

9、于不會(huì) 出現(xiàn) 負(fù)值。 阻塞等待方式適用于單處理機(jī)方式。 忙等待方式適用于多處理機(jī)方式。,(3)關(guān)于同步原語的討論 1) 信號(hào)量的物理含義： S0表示有S個(gè)資源可用 S=0表示無資源可用 S0則 | S | 表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù) wait(S):表示申請(qǐng)一個(gè)資源 signal(S)表示釋放一個(gè)資源。 信號(hào)量的初值應(yīng)該大于等于0,2)wait,signal操作必須成對(duì)出現(xiàn)，有一個(gè)wait操作就一定有一個(gè)signal操作 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程 當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn) 如果wait(S1)和wait(S2)兩個(gè)操作在一起， 那么wait操作的順序至關(guān)重要,而兩個(gè)sig

10、nal 操作無關(guān)緊要,3）同步原語的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 簡單，而且表達(dá)能力強(qiáng) 缺點(diǎn)： 不夠安全；同步原語使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜,例：同步原語使用不當(dāng)會(huì)造成死鎖,A進(jìn)程B進(jìn)程 WAIT(S1) WAIT(S2) WAIT(S2) WAIT(S1) SIGNAL(S2) SIGNAL(S1) SIGNAL(S1) SIGNAL(S2),3、同步原語的不可分割性,信號(hào)量上的同步原語應(yīng)該是原子的操作 保證進(jìn)程間互斥地使用同步原語 整體操作、不可分割、也就是不可打斷其執(zhí)行或者說不可中斷,三、信號(hào)量應(yīng)用,1、用信號(hào)量實(shí)現(xiàn)進(jìn)程間的互斥 2、用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步,1、用信號(hào)量實(shí)現(xiàn)進(jìn)

11、程間的互斥,設(shè)置互斥信號(hào)量，賦初值1，表示臨界資源未被使用。 進(jìn)程描述,例 1 設(shè)進(jìn)程P，Q共享一臺(tái)打印機(jī)，打印機(jī)任何時(shí)刻只能被一個(gè)進(jìn)程使用，而不能同時(shí)使用。試用同步原語描述進(jìn)程，保證兩個(gè)進(jìn)程不同時(shí)使用打印機(jī)。,定義信號(hào)量 S ：表示打印機(jī)數(shù)目，初值為1；,進(jìn)程P： wait(s); 使用打印機(jī) signal(s);,例 2 設(shè)n個(gè)進(jìn)程P1，P2，.，Pn共享m臺(tái)打印機(jī)，試用同步原語描述進(jìn)程。定義信號(hào)量 S 進(jìn)程描述,2、用信號(hào)量實(shí)現(xiàn)進(jìn)程間的同步,例1： 同步關(guān)系：P1-P2 定義信號(hào)量 進(jìn)程描述,例2 用同步原語解決司機(jī)與售票員的問題,有父母子女四人圍坐一起吃水果，父親不 斷削蘋果往盆中放，

12、母親不斷削梨往盆中 放，女兒則從盆中取蘋果吃，兒子則從盆 中取梨吃，假如盆中最多只能放N只水果， 試用同步原語協(xié)調(diào)他們的關(guān)系。,四、經(jīng)典的進(jìn)程同步問題,1、生產(chǎn)者和消費(fèi)者問題 2、閱讀者和寫入者問題 3、哲學(xué)家就餐問題,1、生產(chǎn)者和消費(fèi)者問題,消費(fèi)者,生產(chǎn)者,緩沖區(qū),1、生產(chǎn)者和消費(fèi)者問題,由n個(gè)緩沖區(qū)構(gòu)成的一個(gè)緩沖存儲(chǔ)器，每個(gè)緩沖區(qū)可存放一個(gè)數(shù)據(jù)項(xiàng)。 生產(chǎn)者：生產(chǎn)數(shù)據(jù)并將其放入緩沖區(qū)中的進(jìn)程。 消費(fèi)者：消耗并處理緩沖區(qū)中數(shù)據(jù)的進(jìn)程。,（1）設(shè)置信號(hào)量,mutex ：保證對(duì)該緩沖存儲(chǔ)器的互斥執(zhí)行。其初值為1。 E：表示空緩沖區(qū)數(shù)目，其初值為n F：表示滿緩沖區(qū)數(shù)目，其初值為0。,(2) 進(jìn)程同

13、步關(guān)系描述,生產(chǎn)者進(jìn)程 消費(fèi)者進(jìn)程,注意：兩個(gè)wait操作順序不能互換。例如：當(dāng) mutex=1, E=0, F=n時(shí)，則對(duì)生產(chǎn)者進(jìn)程：wait(mutex)成功，wait(E)失??；對(duì)消費(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗，形成互鎖。,(2) 進(jìn)程同步關(guān)系描述,生產(chǎn)者進(jìn)程 消費(fèi)者進(jìn)程 注意：wait兩個(gè)操作不能互換。例如：當(dāng) mutex=1, E=0, F=n時(shí)，則對(duì)生產(chǎn)者進(jìn)程：wait(mutex)成功，wait(E)失??；對(duì)消費(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗，形成互鎖。,注意：wait兩個(gè)操作不能互換。例如：當(dāng) mutex=1, E=0, F=

14、n時(shí)，則對(duì)生產(chǎn)者進(jìn)程：wait(mutex)成功，wait(E)失敗；對(duì)消費(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗，形成互鎖。,2、閱讀者和寫入者問題,一個(gè)數(shù)據(jù)集為若干并發(fā)進(jìn)程共享。 閱讀者：要求讀取數(shù)據(jù) 寫入者：要求修改數(shù)據(jù) 要求： 允許多個(gè)閱讀者同時(shí)執(zhí)行讀操作 不允許閱讀者、寫入者同時(shí)操作 不允許多個(gè)寫入者同時(shí)操作,如果閱讀者來： 1）無閱讀者、寫入者，新讀者可以讀 2）有寫入者等，但有其它閱讀者正在讀，則新閱讀者也可以讀 3）有寫入者寫，新閱讀者等 如果寫入者來： 1）無閱讀者、寫入者，新寫入者可以寫 2）有閱讀者，新寫入者等待 3）有其它寫入者，新寫入者等待,（1）信號(hào)

15、量設(shè)置：,mutex: 用于閱讀者互斥地訪問共享變量 wrt: 用于寫入者和其它進(jìn)程互斥地訪問共享變量，初值為1。 readcount 普通整形變量，表示正在讀數(shù)據(jù)的閱讀者個(gè)數(shù) ，初值為0。,wait（mutex） readcount：=readcount+1 IF readcount =1 THEN wait（wrt） signal（mutex） 讀數(shù)據(jù) wait（mutex） readcount ；= readcount -1 IF readcount =0 THEN signal（wrt） signal（mutex）,（2）進(jìn)程 同步關(guān)系描述 閱讀者進(jìn)程,寫入者進(jìn)程,wait（mutex

16、） 寫數(shù)據(jù) signal（wrt）,3、哲學(xué)家就餐問題,有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考 和進(jìn)餐，哲學(xué)家們共用一張圓桌，周圍放有五張椅 子，每人坐一張，在圓桌上有五碗面和五個(gè)叉子。 當(dāng)哲學(xué)家思考時(shí)，他不與同事交談。饑餓時(shí)，便試 圖取用左邊和右邊的叉子，他可能一個(gè)也拿不到， 只有在他拿到兩個(gè)叉子時(shí)，方能就餐，吃完后，放 下叉子又繼續(xù)思考。,（1）信號(hào)量設(shè)置,為每個(gè)叉子設(shè)置信號(hào)量： VAR fork : array0.4 of semaphore 信號(hào)量的初值均為1。,(2)進(jìn)程描述（第I個(gè)哲學(xué)家的活動(dòng) ）,WAIT( forkI) 取左邊的叉子 WAIT(fork(I+1) mod

17、5) 取右邊的叉子 就餐 SIGNAL(forkI) 放下左邊的叉子 SIGNAL(fork(I+1) mod 5) 放下右邊的叉子 思考,五、管程,1、管程的提出 2、管程的定義 3、用管程實(shí)現(xiàn)同步,1、管程的提出 采用信號(hào)量來編寫并發(fā)程序，對(duì)于共享變量及信號(hào)量的操作將被分散于各個(gè)進(jìn)程中,缺點(diǎn)： （）易讀性差，因?yàn)橐私鈱?duì)于一組共享變量及信號(hào)量的操作是否正確，則必須通讀整個(gè)系統(tǒng)或者并發(fā)程序 （2）不利于修改和維護(hù)，因?yàn)槌绦虻木植啃院懿?，所以任一組變量或一段代碼的修改都可能影響全局 （）正確性難以保證，因?yàn)椴僮飨到y(tǒng)或并發(fā)程序通常很大，要保證這樣一個(gè)復(fù)雜的系統(tǒng)沒有邏輯錯(cuò)誤是很難的,2、管程的定義

18、,指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作 管程是管理進(jìn)程間同步的機(jī)制，它保證進(jìn) 程互斥地訪問共享變量，并且提供了一個(gè) 方便的阻塞和喚醒進(jìn)程的機(jī)構(gòu)。,管程的基本特性： 局部于管程的數(shù)據(jù)只能被局部于管程內(nèi)的過程所訪問 一個(gè)進(jìn)程只有通過調(diào)用管程內(nèi)的過程才能進(jìn)入管程訪問共享數(shù)據(jù) 每次只允許一個(gè)進(jìn)程在管程內(nèi)執(zhí)行某個(gè)內(nèi)部過程,管程的四個(gè)組成部分：,管程的四個(gè)組成部分： 名稱 數(shù)據(jù)結(jié)構(gòu)說明 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程/函數(shù) 初始化語句,3、用管程實(shí)現(xiàn)同步,管程中支持同步的組成部分： 局限于管程并僅能從管程內(nèi)進(jìn)行訪問的若干條件變量（Condition） 在條件變量上進(jìn)行操作的兩個(gè)函數(shù)過程 WaitC ( C ) 和SignalC ( C ),WaitC(C):將調(diào)用此函數(shù)的進(jìn)程掛起阻塞在與 該條件變量C相關(guān)的隊(duì)列中，并使 管程成為可用 SignalC(C)：喚醒條件變量C的等待隊(duì)列中 的某個(gè)進(jìn)程；若等待隊(duì)列為空， 則為空操作,5.6 進(jìn)程間的通信,一、進(jìn)程通信的概念 二、進(jìn)程通信的實(shí)現(xiàn) 三、間接通信模式 四、其他通信模式,一、進(jìn)程通信的概念 指在進(jìn)程間交換一定數(shù)量的信息。,信號(hào)量實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊，只能傳遞簡單的信號(hào)，不能傳遞大量信息。如果要在進(jìn)程間傳遞大量信息則要使用通信原語（S