第4講、操作系統(tǒng)-經(jīng)典的IPC問題

第二章進程與線程--經(jīng)典的IPC問題

《操作系統(tǒng)》

四、讀寫者問題目錄二、生產(chǎn)者消費者問題三、哲學(xué)家進餐問題一、信號量四、讀寫者問題目錄二、生產(chǎn)者消費者問題三、哲學(xué)家進餐問題一、信號量Page

4三、進程間通信2.3進程間通信內(nèi)容回顧：忙檢測存在的問題。在用戶空間通過標(biāo)識位的方式實現(xiàn)互斥/同步操作，由于進程間的切換是由OS控制的，有可能會因為切換不當(dāng)，引發(fā)錯誤。忙等的方式會浪費CPU的計算資源。方法：采用信號量的方式，由OS實現(xiàn)互斥/同步操作。Page

5三、進程間通信2.3進程間通信主要設(shè)計思想：如果當(dāng)前進程無法進入臨界區(qū)（當(dāng)前不適合執(zhí)行對共享資源的操作代碼），則由OS幫助，進入阻塞狀態(tài)，放棄CPU。兩個通信原語：sleep與wakeupsleep:引起調(diào)用進程阻塞的系統(tǒng)調(diào)用wakeup：喚醒指定的進程通信原語的實現(xiàn)：信號量Page

6三、進程間通信2.3進程間通信信號量：由E.W.Dijkstra于1965年提出的方法。使用一個整型變量來累計喚醒次數(shù)。主要操作：down():檢查其值是否大于0，如大于0,則減1并繼續(xù)操作，否則，進程阻塞。Up():對信號量執(zhí)行的值增加1，如果有進程在此信號量上睡眠，則喚醒一個進程。Page

7三、進程間通信2.3進程間通信信號量：要求：原子操作：一組相關(guān)聯(lián)的操作要么都不間斷的執(zhí)行，要么都不執(zhí)行。表示方法：P（）/V（），wait()/signal()問題：信號量如何實現(xiàn)？如何保證其操作的原子性？Page

8三、進程間通信2.3進程間通信互斥量：保證進程的串行化操作對于兩個并發(fā)進程，互斥信號量的值域(?)若ＭＵＴＥＸ＝1表示沒有進程進入臨界區(qū)若ＭＵＴＥＸ＝0表示有一個進程進入臨界區(qū)若ＭＵＴＥＸ＝-1表示一個進程進入臨界區(qū)，另一個進程等待進入。Page

9信號量小結(jié)2.3進程間通信信號量：實現(xiàn)進程間的同步例如：先執(zhí)行進程A，A結(jié)束后執(zhí)行進程BSemaphoreSYN=0;ProcessA:Run();Up(SYN);ProcessB:Down(SYN);Run();Page

10信號量小結(jié)2.3進程間通信信號量：實現(xiàn)進程間的互斥例如：進程A與進程B同時想利用同一臺打印機打印文件SemaphoreMUTEX=1;ProcessAorB:Down(&MUTEX);printFile();Up(&MUTEX);Page

11信號量小結(jié)2.3進程間通信信號量：主要用于進程間的控制交互的信息比較簡單對用戶不透明，信號量的使用錯誤可能會導(dǎo)致很嚴重的問題。想法：是否可以設(shè)計一種高級同步機制，來封裝復(fù)雜的信號量機制，用戶在編程時不用考慮它？Page

122.3進程間通信方法一：管程（monitor）是一個由過程、變量及數(shù)據(jù)結(jié)構(gòu)等組成的一個集合，它們組成一個特殊的模塊或軟件包。進程可以在任可需要的時候調(diào)用管程中的過程。任一時刻管理中只能有一個活躍進程。進入管程的互斥是由編譯器負責(zé)的。管程是通過編程語言實現(xiàn)的。管程是一種語言概念，而C語言并不支持它。請注意。三、進程間通信Page

13三、信號量小結(jié)2.3進程間通信方法二：消息機制與管程最大的區(qū)別是它是系統(tǒng)調(diào)用而不是語言成分，即是操作系統(tǒng)提供的功能。主要有兩條通信原語實現(xiàn)：send(destination,&mesasage);receive(sourcde,&message);典型的實現(xiàn)方式socket網(wǎng)絡(luò)通信。四、讀寫者問題目錄二、生產(chǎn)者消費者問題三、哲學(xué)家進餐問題一、信號量Page

15一、生產(chǎn)者-消費者問題2.3.5信號量問題指環(huán)王下載進程播放進程本地數(shù)據(jù)緩沖區(qū)Page

16一、生產(chǎn)者-消費者問題2.3.5信號量基本類型一個有限空間的共享緩沖區(qū)，負責(zé)存放貨物一個生產(chǎn)者向緩沖區(qū)中放物品，緩沖區(qū)滿則不能放一個消費者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿Page

17一、生產(chǎn)者-消費者問題2.3.5信號量問題分析生產(chǎn)者與消費者之間的同步操作，生產(chǎn)者放時，消息者不能拿，反之亦然。Page

18一、生產(chǎn)者-消費者問題2.3.5信號量Semaphoreempty=N,full=0;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);insert_item(item);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);item=get_item(item);up(&empty);consume_item(item);}}Page

19一、生產(chǎn)者-消費者問題2.3.5信號量擴展類型一個有限空間的共享緩沖區(qū)，負責(zé)存放貨物多個生產(chǎn)者向緩沖區(qū)中放物品，緩沖區(qū)滿則不能放多個消費者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿Page

20一、生產(chǎn)者-消費者問題2.3.5信號量問題分析多個生產(chǎn)者放時，貨物放在什么地方？多個消費者拿時，拿哪一個貨物？辦法：多個生產(chǎn)者，一個一個放。多個消費者，一個一個拿。Page

21一、生產(chǎn)者-消費者問題2.3.5信號量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=get_item(item);down(&mutex);up(&empty);consume_item(item);}}Page

22一、生產(chǎn)者-消費者問題2.3.5信號量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=insert_item(item);down(&mutex);up(&empty);consume_item(item);}}down(&empty)與down(&mutex)的順序是否可以交換？Page

23一、生產(chǎn)者-消費者問題2.3.5信號量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=insert_item(item);down(&mutex);up(&empty);consume_item(item);}}up(&empty)與up(&mutex)的順序是否可以交換？Page

24一、生產(chǎn)者-消費者問題2.3.5信號量Semaphoreempty=N,full=0,mutex=1;voidproducer(void){intitem;while(TRUE){item=produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);}}voidconsumer(void){intitem;while(TRUE){down(&full);down(&mutex);item=insert_item(item);down(&mutex);up(&empty);consume_item(item);}}四、讀寫者問題目錄二、生產(chǎn)者消費者問題三、哲學(xué)家進餐問題一、信號量Page

26二、哲學(xué)家就餐問題2.5.1信號量問題描述有五個哲學(xué)家圍坐在一圓桌旁，每人面前有一盤通心粉，每兩人之間放一只叉子。每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個哲學(xué)家必須拿到兩只叉子，并且每個人只能直接從自己的左邊或右邊去取叉子Page

27二、哲學(xué)家就餐問題#defineN5voidphilosopher(inti){while(TRUE){think();take_fork(i);take_fork((i+1)%N);eat();put_fork(i);put_fork((i+1)%N);}}注：take_fork,put_fork,是對信號量操作;本算法有什么問題？2.5.1哲學(xué)家就餐問題Page

28二、哲學(xué)家就餐問題2.5.1哲學(xué)家就餐問題問題分析如果每個哲學(xué)家只拿到一把叉子，則會出現(xiàn)“餓死”的現(xiàn)象。解決辦法：問題的根源在于并發(fā)執(zhí)行引起的錯誤，可以把拿叉子的操作串行化。Page

29#defineN5semaphoremutex=1;voidphilosopher(inti){while(TRUE){think();

down(&mutex);take_fork(i);take_fork((i+1)%N);eat();put_fork(i);put_fork((i+1)%N);

up(&mutex);}}注：take_fork,put_fork,是對信號量操作;本算法有什么問題？二、哲學(xué)家就餐問題2.5.1哲學(xué)家就餐問題Page

30#defineN5semaphoremutex=N-1;voidphilosopher(inti){while(TRUE){think();down(&mutex);take_fork(i);take_fork((i+1)%N);eat();put_fork(i);put_fork((i+1)%N);up(&mutex);}}注：take_fork,put_fork,是對信號量操作;二、哲學(xué)家就餐問題2.5.1哲學(xué)家就餐問題本算法有什么問題？Page

31#defineN5#defineLEFT(i+N-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2intstate[N];semaphores[N],mutex=1;voidphilosopher(inti){while(TRUE){think();take_forks(i);eat();put_forks(i);}}二、哲學(xué)家就餐問題voidtake_fork(inti){down(&mutex);state[i]=HUNGRY;test(i);up(&mutex);down(&s[i]);}voidput_fork(inti){down(&mutex);state[i]=THINKING;test(LEFT);test(RIGHT);up(&mutex);down(&s[i]);}voidtest(i){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;up(&s[i]);}}四、讀寫者問題目錄二、生產(chǎn)者消費者問題三、哲學(xué)家進餐問題一、信號量Page

33問題來源1971年，由Courtois等人為數(shù)據(jù)庫訪問建立的模型多個進程可以同時讀數(shù)據(jù)庫中的數(shù)據(jù)。為了保持數(shù)據(jù)的一致性，當(dāng)某一個進程在改寫數(shù)據(jù)庫時，其它進程不允許訪問數(shù)據(jù)庫。三、讀寫者問題2.5.2讀寫者問題Page

34問題描述對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個同時讀三、讀寫者問題2.5.2讀寫者問題Page

35問題分析“讀-寫”互斥“寫-寫”互斥“讀-讀”允許三、讀寫者問題2.5.2讀寫者問題Page

36讀-寫者問題的信號量解法互斥關(guān)系分析讀者和寫者不能同時進入共享數(shù)據(jù)區(qū)多個寫者不能同時進入共享數(shù)據(jù)區(qū)多個讀者可以同時進入共享數(shù)據(jù)區(qū)同步關(guān)系分析讀者進入緩沖區(qū)，寫者必須等待寫者進入緩沖區(qū)，讀者必須等待三、讀寫者問題2.5.2讀寫者問題Page

37讀-寫者問題的信號量解法讀者優(yōu)先：一旦有讀者進入，則后續(xù)讀者均可進入寫者優(yōu)先：只要有寫者等待，則后續(xù)讀者必須等待合理順序：讀者在先來的寫者之后三、讀寫者問題2.5.2讀寫者問題Page

38讀者優(yōu)先的信號量解法三、讀寫者問題2.5.2讀寫者問題Data讀者讀者寫者讀者Page

39三、讀寫者問題2.5.2讀寫者問題semaphorewrt=1,mutex=1;readcount=0;writer(){wait(wrt);//Writingisdonesignal(wrt);}reader(){ wait(mutex); readcount++; if(readcount==1) { wait(wrt); } signal(mutex); //Dothereading wait(mutex); readcount--; if(readcount==0) { signal(wrt); } signal(mutex);}請問上述算法有什么問題？Page

40讀者優(yōu)先的信號量解法當(dāng)讀者的讀取時間及到達速率較快且是一個平滑的流時，有可能會出現(xiàn)寫者“餓死”的情況。如：讀者平均操作時間為2秒，平均1秒到達一個，寫者平均操作時間為5秒。三、讀寫者問題2.5.2讀寫者問題Page

41寫者優(yōu)先的信號量解法三、讀寫者問題2.5.2讀寫者問題Data寫者讀者寫者讀者Page

42三、讀寫者問題intreadcount=0,writecount=0;semaphoremutex_1=1,mutex_2=1,mutex_3=1,w=1,r=1;WRITERP(mutex_2);writecount=writecount+1;if(writecount==1){P(r)；}V(mutex_2);P(w);writingisperformed;V(w);P(mutex_2);writecount=writecount-1;if(writecount==0){V(r)；}V(mutex_2);READERP(mutex_3);P(r);P(mutex_1);readcount=readcount+1;if(readcount==1){P(W);}V(mutex_1);V(r);