計算機操作系統(tǒng)進程同步算法習(xí)題選課件

1、 進程同步算法習(xí)題課劉揚【例題1】司機進程：司機進程：while(1)while(1) 啟動車輛啟動車輛正常駕駛正常駕駛到站停車到站停車 售票員進程：售票員進程：while(1)while(1) 關(guān)門關(guān)門售票售票開門開門 用用waitwait、signalsignal操作解決司機與售票員的問題操作解決司機與售票員的問題分析：分析： 為保證車輛行駛安全，售票員必須關(guān)好車門，然后通知司機啟動車輛，在行駛過程中售票員不能打開車門，待車到站停穩(wěn)后，司機通知售票員才能打開車門，如此不斷重復(fù)。為此，須設(shè)置兩個信號量S1，S2用來控制司機和售票員的行為，初值都為0。解: 算法如下：司機進程：司機進程：whi

2、le(1) wait(S1) 啟動車輛啟動車輛正常駕駛正常駕駛 到站停車到站停車 signal(S2)售票員進售票員進程：程：while(1)關(guān)門關(guān)門 signal(S1)售票售票 wait(S2)開門開門【例題2】1.用wait、signal操作解決下圖之同步問題提示：分別考慮對緩沖區(qū)S和T的同步，再合并考慮putcopygetst解:設(shè)置四個信號量Sin=1，Sout=0，Tin=1，Tout=0； put： while（1） wait(Sin）; 將數(shù)放入將數(shù)放入S; signal (Sout); copy： while（1） wait (Sout）; wait (Tin）; 將數(shù)從將數(shù)

3、從S取出放入取出放入T; signal (Tout); signal (Sin); get： while（1） wait (Tout）; 將數(shù)從將數(shù)從T取走取走; signal(Tin); 思考題： 如果S和T是由多個緩沖區(qū)組成的緩沖池，上述算法將如何修改？【例題3】 桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用wait、signal操作實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。分析： 設(shè)置一個信號量S表示空盤子數(shù)，一個信號量So表示盤中桔子數(shù)，一個信號量Sa表示盤中蘋果數(shù)，初值分別為1，0，0。解: 算法如下：Father

4、() while(1) wait(S); 將水果放入盤中; if(是桔子)signal(So); else signal(Sa); Son() while(1) wait(So) 取桔子 signal(S); 吃桔子; Daughter() while(1) wait(Sa) 取蘋果 signal(S); 吃蘋果; 【例題4】有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1） 每次只能存入一種產(chǎn)品（A或B）（2） NA產(chǎn)品數(shù)量B產(chǎn)品數(shù)量M。其中，N和M是正整數(shù)。試用wait、signal操作描述產(chǎn)品A與B的入庫過程。解:分析：設(shè)兩個同步信號量Sa、Sb，其中：Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的

5、數(shù)量，初值為M-1。Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，初值為N-1。設(shè)互斥信號量mutex，初值為1。 B產(chǎn)品入庫進程：產(chǎn)品入庫進程： j = 0; while (1) wait(Sb); wait(mutex); B產(chǎn)品入庫產(chǎn)品入庫 signal(mutex); signal(Sa); 消費產(chǎn)品消費產(chǎn)品; ;A產(chǎn)品入庫進程：產(chǎn)品入庫進程：i = 0;while (1) 生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品; wait(Sa); wait(mutex); A產(chǎn)品入庫產(chǎn)品入庫 signal(mutex); signal(Sb); ;算法如下：算法如下：例題5 進程A1、A2， An1通過m個緩沖區(qū)向進程B1、

6、B2、 Bn2不斷發(fā)送消息。發(fā)送和接收工作遵循下列規(guī)則：（1） 每個發(fā)送進程一次發(fā)送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小等于消息長度。（2） 對每個消息，B1，B2， Bn2都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)。（3） m個緩沖區(qū)都滿時，發(fā)送進程等待，沒有可讀消息時，接收進程等待。試用wait、signal操作組織正確的發(fā)送和接收工作。分析：每個緩沖區(qū)只要寫一次但要讀n2次，因此，可以看成n2組緩沖區(qū)，每個發(fā)送者要同時寫n2個緩沖區(qū)，而每個接收者只要讀它自己的緩沖區(qū)。Sinn2=m；表示每個讀進程開始有m個空緩沖區(qū)。Soutn2=0；表示每個讀進程開始有0個可接收的消息。解：先將問題簡化： 設(shè)緩

7、沖區(qū)的大小為1 有一個發(fā)送進程A1 有二個接收進程B1、B2 設(shè)有信號量Sin1 、Sin2 初值為1 設(shè)有信號量Sout1 、Sout2 初值為0Bi： while (1) wait(Souti);從緩沖區(qū)取數(shù)從緩沖區(qū)取數(shù) signal(Sini);A1:while (1) wait(Sin1); wait(Sin2);將數(shù)據(jù)放入緩沖區(qū) signal(Sout1); signal(Sout2);向目標前進一步: 設(shè)緩沖區(qū)的大小為m 有一個發(fā)送進程A1 有二個接收進程B1、B2 設(shè)有信號量Sin1 、Sin2 初值為m 設(shè)有信號量Sout1 、Sout2 初值為0Bi： while (1) w

8、ait(Souti); wait(mutex);從緩沖區(qū)取數(shù)從緩沖區(qū)取數(shù) signal(mutex); signal(Sini);A1:while (1) wait(Sin1); wait(Sin2); wait(mutex);將數(shù)據(jù)放入緩沖區(qū) signal(mutex); signal(Sout1); signal(Sout2);到達目標 設(shè)緩沖區(qū)的大小為m 有n1個發(fā)送進程A1.An1 有n2個接收進程B1Bn2 設(shè)有n2個信號量Sinn2 初值均為m 設(shè)有n2個信號量Soutn2 初值均為0Bi： while (1) wait(Souti); wait(mutex);從緩沖區(qū)取數(shù)從緩沖區(qū)

9、取數(shù) signal(mutex); signal(Sini); ;Aj:while (1) for(i=1;i=n2;i+) wait(Sini); wait(mutex);將數(shù)據(jù)放入緩沖區(qū) signal(mutex); for(i=1;i=n2;i+) signal(Sout2);【例題5】 復(fù)印室里有一個操作員為顧客復(fù)印資料，有5把椅子供顧客休息等待復(fù)印。如果沒有顧客，則操作員休息。當(dāng)顧客來到復(fù)印室時，如果有空椅子則坐下來，并喚醒復(fù)印操作員；如果沒有空椅子則必須離開復(fù)印室。 信號量：customers表示正在等待復(fù)印的顧客數(shù)量（不包括正在復(fù)印的顧客）operator記錄正在等候顧客的操作員數(shù)，只有1和0mutex用于對waiting的訪問; 變量： waiting表示等待的顧客數(shù)量。它實際上是customers的一個副本。之所以使用waiting是因為無法讀取信號量的當(dāng)前值。 semaphore customers=0,operator=0,mutex=1;waiting=0；process operator( )/操作員進程 while(1) wait(customers); /等待顧客到來復(fù)?。?signal(operator); /通知顧客已經(jīng)完