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

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

2、le(1) wait(S1) 啟動(dòng)車輛啟動(dòng)車輛正常駕駛正常駕駛 到站停車到站停車 signal(S2)售票員進(jìn)售票員進(jìn)程：程：while(1)關(guān)門(mén)關(guān)門(mén) signal(S1)售票售票 wait(S2)開(kāi)門(mén)開(kāi)門(mén)【例題2】1.用wait、signal操作解決下圖之同步問(wèn)題提示：分別考慮對(duì)緩沖區(qū)S和T的同步，再合并考慮putcopygetst解:設(shè)置四個(gè)信號(hào)量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是由多個(gè)緩沖區(qū)組成的緩沖池，上述算法將如何修改？【例題3】 桌上有一空盤(pán)，最多允許存放一只水果。爸爸可向盤(pán)中放一個(gè)蘋(píng)果或放一個(gè)桔子，兒子專等吃盤(pán)中的桔子，女兒專等吃蘋(píng)果。 試用wait、signal操作實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。分析： 設(shè)置一個(gè)信號(hào)量S表示空盤(pán)子數(shù)，一個(gè)信號(hào)量So表示盤(pán)中桔子數(shù)，一個(gè)信號(hào)量Sa表示盤(pán)中蘋(píng)果數(shù)，初值分別為1，0，0。解: 算法如下：Father

4、() while(1) wait(S); 將水果放入盤(pán)中; if(是桔子)signal(So); else signal(Sa); Son() while(1) wait(So) 取桔子 signal(S); 吃桔子; Daughter() while(1) wait(Sa) 取蘋(píng)果 signal(S); 吃蘋(píng)果; 【例題4】有一個(gè)倉(cāng)庫(kù)，可以存放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的入庫(kù)過(guò)程。解:分析：設(shè)兩個(gè)同步信號(hào)量Sa、Sb，其中：Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫(kù)的

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

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

7、沖區(qū)的大小為1 有一個(gè)發(fā)送進(jìn)程A1 有二個(gè)接收進(jìn)程B1、B2 設(shè)有信號(hào)量Sin1 、Sin2 初值為1 設(shè)有信號(hào)量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);向目標(biāo)前進(jìn)一步: 設(shè)緩沖區(qū)的大小為m 有一個(gè)發(fā)送進(jìn)程A1 有二個(gè)接收進(jìn)程B1、B2 設(shè)有信號(hào)量Sin1 、Sin2 初值為m 設(shè)有信號(hào)量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);到達(dá)目標(biāo) 設(shè)緩沖區(qū)的大小為m 有n1個(gè)發(fā)送進(jìn)程A1.An1 有n2個(gè)接收進(jìn)程B1Bn2 設(shè)有n2個(gè)信號(hào)量Sinn2 初值均為m 設(shè)有n2個(gè)信號(hào)量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ù)印室里有一個(gè)操作員為顧客復(fù)印資料，有5把椅子供顧客休息等待復(fù)印。如果沒(méi)有顧客，則操作員休息。當(dāng)顧客來(lái)到復(fù)印室時(shí)，如果有空椅子則坐下來(lái)，并喚醒復(fù)印操作員；如果沒(méi)有空椅子則必須離開(kāi)復(fù)印室。 信號(hào)量：customers表示正在等待復(fù)印的顧客數(shù)量（不包括正在復(fù)印的顧客）operator記錄正在等候顧客的操作員數(shù)，只有1和0mutex用于對(duì)waiting的訪問(wèn); 變量： waiting表示等待的顧客數(shù)量。它實(shí)際上是customers的一個(gè)副本。之所以使用waiting是因?yàn)闊o(wú)法讀取信號(hào)量的當(dāng)前值。 semaphore customers=0,operator=0,mutex=1;waiting=0；process operator( )/操作員進(jìn)程 while(1) wait(customers); /等待顧客到來(lái)復(fù)??； signal(operator); /通知顧客已經(jīng)完