進(jìn)程的同步與通信

1、 操作系統(tǒng)設(shè)計系列講座操作系統(tǒng)設(shè)計系列講座 作者：蔣石竹作者：蔣石竹 部門：研發(fā)部硬件二室部門：研發(fā)部硬件二室 郵件地址：郵件地址： 聯(lián)系電話：聯(lián)系電話：82029090-3393 進(jìn)程的同步與通信進(jìn)程的同步與通信 授課提綱授課提綱 第一章 進(jìn)程的同步 1.1 進(jìn)程同步的基本概念 1.2 進(jìn)程同步的常用機(jī)制及案例分析 1.3 經(jīng)典的進(jìn)程同步問題 第二章 進(jìn)程的通信 2.1 進(jìn)程同步與進(jìn)程通信的關(guān)系 2.2 進(jìn)程通信的常用機(jī)制及案例分析 第一章第一章 進(jìn)程的同步進(jìn)程的同步 1.1 進(jìn)程同步的基本概念 1.2 進(jìn)程同步的常用機(jī)制及案例分析 1.3 經(jīng)典的進(jìn)程同步問題 1.1.1 進(jìn)程同步的基本概念

2、之一進(jìn)程同步的基本概念之一 【概念一】 ：進(jìn)程間可能存在的關(guān)系 資源共享關(guān)系 例1：打印機(jī) 相互合作關(guān)系 例1：緩沖區(qū)的讀寫 1.1.2 進(jìn)程同步的基本概念之二進(jìn)程同步的基本概念之二 【概念二】進(jìn)程同步的主要任務(wù) 使并發(fā)執(zhí)行的諸進(jìn)程之間能夠有效地共享資源 和互相合作，從而使程序的執(zhí)行具有可再現(xiàn)性。 1.1.3 進(jìn)程同步的基本概念之三進(jìn)程同步的基本概念之三 【概念三】臨界資源與臨界區(qū) 臨界資源是一次僅允許一個進(jìn)程使用的資源。對 臨界資源的訪問應(yīng)采取互斥方式，實現(xiàn)對資源的 共享。 每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。 保證每個進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，就可以 實現(xiàn)它們對臨界資源的互斥訪問

3、。 1.1.4 進(jìn)程同步的基本概念之四進(jìn)程同步的基本概念之四 【概念四】進(jìn)程同步的四項原則 空閑讓進(jìn) 忙則等待 有限等待 I.讓權(quán)等待 1.1.4 進(jìn)程同步的基本概念之四（續(xù)）進(jìn)程同步的基本概念之四（續(xù)） repeat while turn != i do no_op; critical section turn = j; remainder section until false; 特點：強(qiáng)制兩個進(jìn)程輪流地進(jìn)入臨界區(qū)，可以 保 證每次只允許一個進(jìn)程進(jìn)入臨界區(qū)。 缺點：違反了“空閑讓進(jìn)”原則。 同步算法一 1.1.4 進(jìn)程同步的基本概念之四（續(xù)）進(jìn)程同步的基本概念之四（續(xù)） var boole

4、an flagn repeat while flagj do no_op flagi = true; critical section flagi = false; remainder section until false; 特點：遵循了“空閑讓進(jìn)” 缺點：違背了“忙則等待” 同步算法二 1.1.4 進(jìn)程同步的基本概念之四（續(xù)）進(jìn)程同步的基本概念之四（續(xù)） repeat flagi = ture; while flagj do no_op critical section flagi = false remainder section Until false; 特點：可以有效防止兩個進(jìn)程同時

5、進(jìn)入臨界區(qū)。 缺點：違背“有空讓進(jìn)”和“有限等待”。 同步算法三 1.1.4 進(jìn)程同步的基本概念之四（續(xù)）進(jìn)程同步的基本概念之四（續(xù)） repeat flagi = ture;turn = j; while (flagj and turn=j) do no_op critical section flagi = false remainder section Until false; 特點：即保證了“忙則等待”，又實現(xiàn)了“空閑 讓進(jìn)” 同步算法四 第一章第一章 進(jìn)程的同步進(jìn)程的同步 1.1 進(jìn)程同步的基本概念 1.2 進(jìn)程同步的常用機(jī)制及案例分析 1.3 經(jīng)典的進(jìn)程同步問題 1.2 進(jìn)程同步的

6、常用機(jī)制進(jìn)程同步的常用機(jī)制 整型信號量機(jī)制 記錄型信號量機(jī)制 信號量集機(jī)制 1.2.1 整型信號量機(jī)制整型信號量機(jī)制 整型信號量被定義為一個整型量S。 S的物理意義：資源數(shù)目或請求使用某一資 源的進(jìn)程的個數(shù)。 S = 0 S等于可供并發(fā)進(jìn)程使用的資源數(shù) S 0|S|等于正在等待使用臨界區(qū)的進(jìn)程數(shù)目 1.2.1 整型信號量機(jī)制整型信號量機(jī)制(續(xù)續(xù)) 對S的訪問：兩個原子的操作P操作和V操作 P操作： wait(s) while s= 0 do no_op s = s 1 V操作： signal(s) s = s + 1 整型信號量的缺陷：違背“讓權(quán)等待”原則。 1.2.2 記錄型信號量機(jī)制記錄型

7、信號量機(jī)制 記錄型信號量：整型變量value + 進(jìn)程鏈表L P操作 wait(S) var semaphore S begin S.value = S.value 1 if S.value 0 then block(S, L) end 1.2.2 記錄型信號量機(jī)制（續(xù)）記錄型信號量機(jī)制（續(xù)） V操作 signal(S) var semaphore S begin S.value = S.value + 1; if(S.value = 1 and and Sn = 1 then for i = 1 to n do Si = Si 1 endfor else 阻塞當(dāng)前任務(wù)，直到獲得欠缺的資源全部

8、備齊 endif 1.2.3 信號量集機(jī)制信號量集機(jī)制(續(xù)續(xù)) AND信號量集的V操作 Ssignal(S1, S2, ,Sn) for i = 1 to n do Si = Si + 1 endfor 解除阻塞任務(wù)隊列中可獲得所需全部資源的任務(wù)的阻塞狀 態(tài) 1.2.3 信號量集機(jī)制案例分析信號量集機(jī)制案例分析 Linux的信號量集的介紹 第一章第一章 進(jìn)程的同步進(jìn)程的同步 1.1 進(jìn)程同步的基本概念 1.2 進(jìn)程同步的常用機(jī)制及案例分析 1.3 經(jīng)典的進(jìn)程同步問題 1.3 經(jīng)典的進(jìn)程同步問題經(jīng)典的進(jìn)程同步問題 生產(chǎn)者消費者問題 讀者寫者問題 1.3.1 生產(chǎn)者生產(chǎn)者-消費者問題消費者問題 問

9、題的描述； 利用記錄型信號量的解決方案； 利用AND信號量集的解決方案； 1.3.2 讀者讀者-寫者問題寫者問題 問題的描述； 利用記錄型信號量的解決方案； 授課提綱授課提綱 第一章 進(jìn)程的同步 1.1 進(jìn)程同步的基本概念 1.2 進(jìn)程同步的常用機(jī)制及案例分析 1.3 經(jīng)典的進(jìn)程同步問題 第二章 進(jìn)程的通信 2.1 進(jìn)程同步與進(jìn)程通信的關(guān)系 2.2 進(jìn)程通信的常用機(jī)制及案例分析 第二章進(jìn)程的通信第二章進(jìn)程的通信 2.1 進(jìn)程同步與進(jìn)程通信的關(guān)系 2.2 進(jìn)程通信的常用機(jī)制及案例分析 2.1 進(jìn)程同步與進(jìn)程通信的關(guān)系進(jìn)程同步與進(jìn)程通信的關(guān)系 進(jìn)程通信分為低級通信和高級通信。 低級通信：進(jìn)程之間僅

10、進(jìn)行控制信息的交換。 高級通信：用戶可以直接利用操作系統(tǒng)所提 供的一組通信命令，高效地傳送 大量的數(shù)據(jù)。 進(jìn)程同步屬于低級通信。 第二章進(jìn)程的通信第二章進(jìn)程的通信 2.1 進(jìn)程同步與進(jìn)程通信的關(guān)系 2.2 進(jìn)程通信的常用機(jī)制及案例分析 2.2 進(jìn)程通信的常用機(jī)制進(jìn)程通信的常用機(jī)制 共享存儲器系統(tǒng) 消息傳遞系統(tǒng) 管道通信 2.2.1 共享存儲器系統(tǒng)共享存儲器系統(tǒng) 相互通信的進(jìn)程通過共享數(shù)據(jù)結(jié)構(gòu)和存儲 區(qū)進(jìn)行通信。 共享數(shù)據(jù)結(jié)構(gòu) 共享存儲區(qū) 2.2.1 共享存儲器系統(tǒng)共享存儲器系統(tǒng)案例分析案例分析 Linux的共享內(nèi)存機(jī)制介紹 2.2.2 消息傳遞系統(tǒng)消息傳遞系統(tǒng) 進(jìn)程間的數(shù)據(jù)交換以消息為單位進(jìn)行

11、。程 序員直接利用系統(tǒng)提供的一組通信命令來 實現(xiàn)通信。 因其實現(xiàn)方法不同，可分為： 直接通信方式（消息緩沖機(jī)制） i. 間接通信方式（信箱通信機(jī)制） 2.2.2.1 直接通信方式直接通信方式 關(guān)鍵數(shù)據(jù)結(jié)構(gòu) 發(fā)送原語 接收原語 案例分析 2.2.2.1 直接通信方式直接通信方式關(guān)鍵數(shù)據(jù)結(jié)構(gòu)關(guān)鍵數(shù)據(jù)結(jié)構(gòu) 消息緩沖區(qū) typedef message buffer = record sender；發(fā)送者進(jìn)程標(biāo)識符 size； 消息長度 text； 詳細(xì)征文 next； 指向下一個消息緩沖 區(qū)的指針 end 2.2.2.1 直接通信方式直接通信方式關(guān)鍵數(shù)據(jù)結(jié)構(gòu)續(xù)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)續(xù) PCB中有關(guān)通信的數(shù)據(jù)項

12、typedef PCB = record mq；消息隊列首指針 mutex；消息隊列互斥信號量 sm；消息隊列資源信號量 end 2.2.2.1 直接通信方式直接通信方式發(fā)送原語發(fā)送原語 procedure send(receiver, a) begin getbuf(a.size, i); i.sender = a.sender; i.size = a.size; i.text = a.text; i.next = 0; 2.2.2.1 直接通信方式直接通信方式發(fā)送原語發(fā)送原語(續(xù)續(xù)) getid(PCB set, receiver, j); wait(j.mutex); insert(j.

13、mq, i); signal(j.mutex); signal(j.sm); end 2.2.2.1 直接通信方式直接通信方式接收原語接收原語 procedure receive(b) begin j = internal name; wait(j.sm); wait(j.mutex); remove(j.mq, I); signal(j.mutex); 2.2.2.1 直接通信方式直接通信方式接收原語（續(xù)）接收原語（續(xù)） b.sender = i.sender; b.size = i.size; b.text = i.text; end 2.2.2.1 直接通信方式直接通信方式案例分析案例分

14、析 OSE的Signal通信機(jī)制介紹 2.2.2.2 間接通信方式間接通信方式 信箱的組成 發(fā)送過程 接收過程 信箱的分類 案例分析 2.2.2.2 間接通信方式間接通信方式信箱的組成信箱的組成 信箱頭 信箱的控制信息。根據(jù)不同的信箱機(jī)制的實現(xiàn)， 信箱頭包含的內(nèi)容不同。 信箱體 若干個抽屜，每個抽屜可以存放一封信 2.2.2.2 間接通信方式間接通信方式發(fā)送過程發(fā)送過程 send（N，M）：把信件M送到指定的信箱N中 步驟：步驟： 查找指定信箱N； 若信箱未滿，則把信件M送入信箱且釋放“等信 件”者； 若信箱已滿置發(fā)送信件進(jìn)程為“等信箱”狀態(tài)； 2.2.2.2 間接通信方式間接通信方式接收過程

15、接收過程 receive（N，X）：從指定信箱N中取出一封信，存 放到指定的地址X中 步驟：步驟： 查找指定信箱N； 若信箱中有信，則取出一封信存于X中且釋放 “等信箱”者； 若信箱中無信件則置接收信件進(jìn)程“等信件” 狀態(tài)； 2.2.2.2 間接通信方式間接通信方式信箱的分類信箱的分類 私用信箱 公用信箱 共享信箱 2.2.2.2 間接通信方式間接通信方式案例分析案例分析 VxWorks的Message Queue通信機(jī)制介紹 2.2.3 管道通信管道通信 管道通信的定義 字符流方式的特點 如何協(xié)調(diào)通信 案例分析 2.2.3.1 管道通信的定義管道通信的定義 也稱共享文件方式，基于文件系統(tǒng)，利

16、用 一個打開的共享文件連接兩個相互通信的 進(jìn)程，文件作為緩沖傳輸介質(zhì)。 發(fā)送進(jìn)程發(fā)送進(jìn)程接收進(jìn)程接收進(jìn)程 字符流方式寫入讀出字符流方式寫入讀出 先進(jìn)先出順序先進(jìn)先出順序 2.2.3.2 字符流方式的特點字符流方式的特點 發(fā)送進(jìn)程可以源源不斷的從pipe一端寫入數(shù) 據(jù)流，在規(guī)定的pipe文件的最大長度（如 4096字節(jié)）范圍內(nèi)，每次寫入的信息長度 是可變的 接收進(jìn)程在需要時可以從pipe的另一端讀出 數(shù)據(jù)，讀出單位長度也是可變的 2.2.3.3 如何協(xié)調(diào)通信如何協(xié)調(diào)通信 互斥：互斥：一個進(jìn)程正在對管道進(jìn)行讀/寫操作時，另 一進(jìn)程必須等待。 同步：同步：當(dāng)寫進(jìn)程把一定數(shù)量的數(shù)據(jù)寫入管道后， 便去睡眠等待，直到讀進(jìn)程取走數(shù)據(jù)將其喚醒；