進程同步與通訊

1、第九講 進程同步與通訊目的與要求：掌握信號量解決進程同步互斥問題的方法；掌握進程通信的基本實現(xiàn)方法。重點與難點：信號量的典型應用，通訊實現(xiàn)。作業(yè)：13，14，1514.2.5 進程同步與互斥舉例一、有限緩沖區(qū)問題問題描述：設有n個緩沖區(qū)，一組生產者進程往緩沖區(qū)寫數(shù)據(jù)，一組消費者進程從緩沖區(qū)取數(shù)據(jù)，寫取以一個緩沖區(qū)為單位。說明： 將緩沖池看作是共享數(shù)據(jù)，對緩沖區(qū)的 操作必須是互斥操作。 如果n個緩沖區(qū)全滿，生產者進程必須 等待。 如果緩沖區(qū)全空，消費者進程必須等待。2有限緩沖區(qū)的生產者/消費者問題（生產者和消費者共享一個產品緩沖池）共享N個緩沖區(qū)P1 P2 Pm C1 C2 Cn生產者消費者緩沖

2、池3解：設置以下信號量mutex,初值為1，控制互斥訪問緩沖池。full,初值為0，表示當前緩沖池中滿緩沖區(qū)數(shù)。empty,初值為N，表示當前緩沖池中空緩沖區(qū)數(shù)。 有限緩沖區(qū)生產者/消費者進程描述如下： item表示消息數(shù)據(jù)類型；semaphor full,empty,mutex;item nextp,nextc; 置初值full=0; empty=N; mutex=1; 4 P(empty); P(mutex); get a empty bufferi; bufferi =nextp; add bufferi to full buffer queue; V(full); V(mutex);

3、while(1) Producer（）: do produce an item in nextp; .while(empty=0) ;empty=empty-1;full=full+15 consume the item in nextc; while(1) （兩個P操作可以倒序嗎？） consumer(): do P(full); P(mutex); get a buffer from full buffer queue; nextc=bufferi put bufferi back to empty queue; V(empty); V(mutex);while(full=0) ;full

4、=full-1;empty=empty+16存在共享數(shù)據(jù)A，那些對它進行只讀訪問進程叫Reader；對它進行了寫操作的進程叫Writer。第一類Reader/ Writer問題（并發(fā)極大化）：Reader和Writer爭奪訪問共享數(shù)據(jù)A時，如果已經有Reader訪問A，后續(xù)Reader與后續(xù)Writer比有較高優(yōu)先權。第二類Reader/ Writer問題（數(shù)據(jù)時效）：Reader和Writer爭奪訪問共享數(shù)據(jù)A時，Writer有較高優(yōu)先權。二、Readers/Writers問題7第一類Reader/ Writer問題描述：1、如果當前無進程訪問A，則Reader/ Writer欲訪問即可訪問

5、。2、如果已存在一個Reader正在訪問數(shù)據(jù)，其它欲訪問Reader可馬上訪問（這體現(xiàn)Reader有較高優(yōu)先權）；而欲訪問的Writer必須等待。3、若某個Writer正訪問數(shù)據(jù)，則欲訪問的Reader/ Writer都必須等待。4、當最后一個結束訪問數(shù)據(jù)的Reader發(fā)現(xiàn)有Writer正在等待時，則將其中一個喚醒。5、當某個Writer結束訪問時，若只有Writer在等待，則喚醒某個Writer，若既有Writer也有Reader；則按FIFO或其它原則喚醒一個Writer或所有Reader。8Writer：P（wrt）;寫數(shù)據(jù)AV（wrt）;Reader：P(mutex)； readcou

6、nt=readcount+1; if (readcount=1) P(wrt);V(mutex)；讀數(shù)據(jù)AP（mutex）； readcount=readcount-1; if (readcount=0) V(wrt);V(mutex); 第一類Reader/ Writer問題編程信號量：wrt=1；（用于A的互斥訪問）整型變量：readcount=0（用于reader計數(shù)）信號量：mutex=1；（用于對readcount互斥訪問）9三、哲學家就餐問題 問題描述：五個哲學家五只筷子，哲學家循環(huán)做著思考和吃飯的動作，吃飯程序是：先取左邊筷子，再取右邊筷子，再吃飯，再放筷子。10實現(xiàn)：為每個筷子

7、設一把鎖（信號量，初值為1）每個哲學家是一個進程。共享數(shù)據(jù)結構為semaphore chopstick5； 第i個進程描述為(i=0, ,4)doP（chopsticki）；/ 取左邊筷子;P（chopstick(i+1)% 5）； / 取右邊筷子;Eat； / 放左邊筷子;V（chopsticki）；/ 放右邊筷子; V（chopstick(i+1) %5）； Think；while(1)；(這可能導致死鎖)114.3 消息傳遞原理 兩種基本進程通訊方法：1、共享存儲（Shared-memory）：相互通訊的進程有共享存儲區(qū).進程間可以通過直接讀寫共享存儲區(qū)的變量來交互數(shù)據(jù)，同步與互斥在并發(fā)

8、程序設計時安排進入程序。操作系統(tǒng)提供這樣的共享存儲區(qū)及同步互斥工具。2、消息傳遞(message-passing)：通過操作系統(tǒng)的相應系統(tǒng)調用進行消息傳遞通訊。12消息傳遞系統(tǒng)調用語句的一般形式:發(fā)送消息：Send(destination,&message);接收消息：Receive(source,&message)。消息傳遞方法1、直接通訊法基本思想：進程在發(fā)送和接收消息時直接指明接收者或發(fā)送者進程ID。缺點：必須指定接收進程ID。（UNIX的信號機制類似這種形式）4.3.1消息傳遞通訊原理13舉例：（UNIX中兩進程利用信號通訊）。Process A kill(1040, SIGUSR1)

9、; #向1040號進程發(fā)送 一個SIGUSR1信號。Process B Signal(SIGUSR1,func);#當收到SIGUSR1信 號時，就執(zhí)行func(),如果SIGUSR1 信號未到，則系統(tǒng)登記func函數(shù)， 待其信號到時再調用執(zhí)行。142、間接通訊法（信箱命名法）基本思想：系統(tǒng)為每個信箱設一個消息隊列，消息發(fā)送和接收都指向該消息隊列。 缺點：必須有一個通訊雙方共享的一個邏輯消息隊列（UNIX的IPC消息傳遞機制屬于這種形式），使用時消息發(fā)送者約定寫方式打開信箱,消息接受者約定讀方式打開信箱或同時讀寫打開。優(yōu)點：很容易建立雙向通訊鏈(只要對信箱說明為讀寫打開)。 154.3.2 進

10、程消息傳遞通訊示例直接通訊消息系統(tǒng)，兩個基本操作為：send(&A)：&A指向含接收者pid和消息正文的空間。Receive(&A)：&A指向緩沖區(qū)用于接收消息，該系統(tǒng)調用函數(shù)返回值是消息發(fā)送者pid。實現(xiàn)：系統(tǒng)有一空閑緩沖區(qū)池，每個進程有一個消息緩沖隊列。緩沖區(qū)用于存放消息及消息發(fā)送者pid和消息鏈(用pid定位進程PCB表)。Senders pid消息正文下一消息鏈消息緩沖區(qū)16每個進程的消息隊列存放發(fā)送給該進程的消息，隊列頭存于PCB中，同時在PCB中設一互斥信號量mutex(初值為1)和信號量Sm（初值為0），Sm用于記錄消息隊列中的消息數(shù)。.mutexSm.Senders pidte

11、xtSenders pidtextReceivers PCB message messageHptr17Send(&A): New(&p)；從空緩沖區(qū)隊列得一個buffer . 置senders pid； 將A中消息送buffer p； 獲得A中Receivers pid； P(mutex)； 將buffer p掛入相應的消息隊列； V(Sm)； V(mutex)；18Receive(&A)： P(Sm)； P(mutex)； 從本進程的消息隊列取一個buffer f； V(mutex)； 從buffer f中取得消息正文送A,并得到 senders pid作為Receive( )的返回值；. dispose(f)；#釋放buffer f到空緩沖隊列