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

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

算法如下：司機(jī)進(jìn)程：while(1){wait(S1)啟動(dòng)車輛正常駕駛

到站停車signal(S2)}…售票員進(jìn)程：while(1){關(guān)門signal(S1)售票wait(S2)開門}…【例題2】1.用wait、signal操作解決下圖之同步問題提示：分別考慮對緩沖區(qū)S和T的同步，再合并考慮putcopygetst解:設(shè)置四個(gè)信號(hào)量Sin=1，Sout=0，Tin=1，Tout=0；

put：while（1）{wait(Sin）;將數(shù)放入S;

signal

(Sout);}

copy：while（1）{

wait

(Sout）;

wait

(Tin）;將數(shù)從S取出放入T;

signal

(Tout);

signal

(Sin);}get：while（1）{

wait

(Tout）;將數(shù)從T取走;signal(Tin);}思考題：如果S和T是由多個(gè)緩沖區(qū)組成的緩沖池，上述算法將如何修改？【例題3】桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個(gè)蘋果或放一個(gè)桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用wait、signal操作實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。

分析：設(shè)置一個(gè)信號(hào)量S表示空盤子數(shù)，一個(gè)信號(hào)量So表示盤中桔子數(shù)，一個(gè)信號(hào)量Sa表示盤中蘋果數(shù)，初值分別為1，0，0。解:算法如下：Father(){while(1){

wait(S);將水果放入盤中;if(是桔子)signal(So);elsesignal(Sa);}}Son(){while(1){wait(So)取桔子signal(S);吃桔子;}}Daughter(){while(1){wait(Sa)取蘋果signal(S);吃蘋果;}}【例題4】有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）

每次只能存入一種產(chǎn)品（A或B）（2）

－N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用wait、signal操作描述產(chǎn)品A與B的入庫過程。解:分析：設(shè)兩個(gè)同步信號(hào)量Sa、Sb，其中：Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，初值為M-1。Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，初值為N-1。設(shè)互斥信號(hào)量mutex，初值為1。

B產(chǎn)品入庫進(jìn)程：j=0;while(1){

wait(Sb);wait(mutex);B產(chǎn)品入庫

signal(mutex);signal(Sa);消費(fèi)產(chǎn)品;};A產(chǎn)品入庫進(jìn)程：

i=0;

while(1){

生產(chǎn)產(chǎn)品;

wait(Sa);

wait(mutex);A產(chǎn)品入庫

signal(mutex);

signal(Sb);

};算法如下：例題5

進(jìn)程A1、A2，…An1通過m個(gè)緩沖區(qū)向進(jìn)程B1、B2、…Bn2不斷發(fā)送消息。發(fā)送和接收工作遵循下列規(guī)則：（1）每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫入一個(gè)緩沖區(qū)，緩沖區(qū)大小等于消息長度。（2）對每個(gè)消息，B1，B2，…Bn2都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)。（3）m個(gè)緩沖區(qū)都滿時(shí)，發(fā)送進(jìn)程等待，沒有可讀消息時(shí)，接收進(jìn)程等待。試用wait、signal操作組織正確的發(fā)送和接收工作。分析：每個(gè)緩沖區(qū)只要寫一次但要讀n2次，因此，可以看成n2組緩沖區(qū)，每個(gè)發(fā)送者要同時(shí)寫n2個(gè)緩沖區(qū)，而每個(gè)接收者只要讀它自己的緩沖區(qū)。Sin[n2]=m；表示每個(gè)讀進(jìn)程開始有m個(gè)空緩沖區(qū)。Sout[n2]=0；表示每個(gè)讀進(jìn)程開始有0個(gè)可接收的消息。解：先將問題簡化：設(shè)緩沖區(qū)的大小為1有一個(gè)發(fā)送進(jìn)程A1有二個(gè)接收進(jìn)程B1、B2設(shè)有信號(hào)量Sin[1]、Sin[2]初值為1設(shè)有信號(hào)量Sout[1]、Sout[2]初值為0Bi：while(1){

wait(Sout[i]);

從緩沖區(qū)取數(shù)signal(Sin[i]);}A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

將數(shù)據(jù)放入緩沖區(qū)

signal(Sout[1]);signal(Sout[2]);

}向目標(biāo)前進(jìn)一步:設(shè)緩沖區(qū)的大小為m有一個(gè)發(fā)送進(jìn)程A1有二個(gè)接收進(jìn)程B1、B2設(shè)有信號(hào)量Sin[1]、Sin[2]初值為m設(shè)有信號(hào)量Sout[1]、Sout[2]初值為0Bi：while(1){

wait(Sout[i]);

wait(mutex); 從緩沖區(qū)取數(shù)

signal(mutex);signal(Sin[i]);};A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

wait(mutex);

將數(shù)據(jù)放入緩沖區(qū)

signal(mutex);

signal(Sout[1]);signal(Sout[2]);

}到達(dá)目標(biāo)設(shè)緩沖區(qū)的大小為m有n1個(gè)發(fā)送進(jìn)程A1….An1有n2個(gè)接收進(jìn)程B1…Bn2設(shè)有n2個(gè)信號(hào)量Sin[n2]初值均為m設(shè)有n2個(gè)信號(hào)量Sout[n2]初值均為0Bi：while(1){

wait(Sout[i]);

wait(mutex);

從緩沖區(qū)取數(shù)

signal(mutex);signal(Sin[i]);};Aj:while(1){for(i=1;i<=n2;i++)

wait(Sin[i]);

wait(mutex); 將數(shù)據(jù)放入緩沖區(qū)

signal(mutex);

for(i=1;i<=n2;i++) signal(Sout[2]);}【例題5】復(fù)印室里有一個(gè)操作員為顧客復(fù)印資料，有5把椅子供顧客休息等待復(fù)印。如果沒有顧客，則操作員休息。當(dāng)顧客來到復(fù)印室時(shí)，如果有空椅子則坐下來，并喚醒復(fù)印操作員；如果沒有空椅子則必須離開復(fù)印室。

信號(hào)量：customers表示正在等待復(fù)印的顧客數(shù)量（不包括正在復(fù)印的顧客）operator記錄正在等候顧客的操作員數(shù)，只有1和0mutex用于對waiting的訪問;變量：

waiting表示等待的顧客數(shù)量。它實(shí)際上是customers的一個(gè)副本。之所以使用waiting是因?yàn)闊o法讀取信號(hào)量的當(dāng)前值。semaphorecustomers=0,operator=0,mutex=1;waiting=0；processoperator()//操作員進(jìn)程{while(1){wait(customers);//等待顧客到來復(fù)??；signal(operator);//通知顧客已經(jīng)完成復(fù)印}}processcusotmeri()//顧客進(jìn)程i{wait(mutex);if(waiting<5){waiting++;signal(customers);signal(