【操作系統(tǒng)】——經(jīng)典進(jìn)程同步問題

經(jīng)典進(jìn)程同步問題

（1）生產(chǎn)者——消費(fèi)者問題

單生產(chǎn)者——消費(fèi)者問題

1.問題描述

系統(tǒng)中有一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程，生產(chǎn)者進(jìn)程每次生產(chǎn)一個(gè)產(chǎn)品放入緩沖區(qū)；消費(fèi)者進(jìn)程每次從有界緩沖區(qū)中取出一個(gè)產(chǎn)品并使用。生產(chǎn)者和消費(fèi)者共享一個(gè)初始為空、大小為n的緩沖區(qū)。

只有緩沖區(qū)沒滿時(shí)，生產(chǎn)者才能把產(chǎn)品放入緩沖區(qū)，否則必須等待。

只有緩沖區(qū)不空時(shí)，消費(fèi)者才能從緩沖區(qū)中取出產(chǎn)品，否則必須等待。

緩沖區(qū)是臨界資源，各進(jìn)程必須互斥的訪問

2.問題分析

由于緩沖區(qū)是臨界資源必須互斥使用，因此需要設(shè)置一個(gè)互斥信號量mutex，緩沖區(qū)有兩種狀態(tài)：進(jìn)程正在訪問和沒有進(jìn)程正在訪問，因此可以給mutex賦初值為1。

緩沖區(qū)中的大小是生產(chǎn)者和消費(fèi)者都可以進(jìn)行操作的，當(dāng)緩沖區(qū)滿時(shí)，生產(chǎn)者要等待消費(fèi)者取走產(chǎn)品，按一定次序訪問這屬于同步關(guān)系；當(dāng)緩沖區(qū)空時(shí)，消費(fèi)者要等待生產(chǎn)者生產(chǎn)產(chǎn)品，按一定次序訪問這屬于同步關(guān)系，因此需要設(shè)置兩個(gè)同步信號量，full和empty

Semaphore mutex = 1; //互斥信號量實(shí)現(xiàn)對緩沖區(qū)的互斥訪問 Semaphore empty = n; //同步信號量，表示空閑緩沖區(qū)的數(shù)量，初值為有界緩沖區(qū)大小n Semaphore full = 0; //同步信號量，表示產(chǎn)品數(shù)量，也是非空緩沖區(qū)數(shù)量，初值為0

3.偽代碼邏輯實(shí)現(xiàn)

Producer(){ while (1) { 生產(chǎn)一個(gè)產(chǎn)品; P(empty); //消耗一個(gè)空閑緩沖區(qū) P(mutex); 把產(chǎn)品放入緩沖區(qū); V(mutex); V(full); //增加一個(gè)產(chǎn)品 } } Consumer(){ while (1) { 生產(chǎn)一個(gè)產(chǎn)品; P(full); //消耗一個(gè)產(chǎn)品 P(mutex); 把產(chǎn)品放入緩沖區(qū); V(mutex); V(empty); //增加一個(gè)空閑緩沖區(qū) } }

由偽代碼邏輯可以發(fā)現(xiàn)，實(shí)現(xiàn)兩進(jìn)程的同步關(guān)系，是在其中一個(gè)進(jìn)程中執(zhí)行P，另一個(gè)進(jìn)程中執(zhí)行V，（增加一個(gè)產(chǎn)品V(full) ,消耗一個(gè)產(chǎn)品P(full) )

不能交換兩個(gè)P操作的先后順序

多生產(chǎn)者——消費(fèi)者問題

1.問題描述

桌子上有一個(gè)盤子，每次只能向其中放入一個(gè)水果。爸爸只向盤子中放蘋果，媽媽只向盤子中放橘子，兒子專等著吃盤子中的橘子，女兒專等著吃盤子中的蘋果。只有盤子為空時(shí)，爸爸媽媽才能往盤子里放一個(gè)水果。僅當(dāng)盤子中有自己需要的水果時(shí)，兒子或女兒可以從盤子中取出水果。

2.問題分析

盤子相當(dāng)于一個(gè)初始為空，大小為1的緩沖區(qū)。爸爸媽媽分別可以看作生產(chǎn)者進(jìn)程1、生產(chǎn)者進(jìn)程2，兒子可以看作消費(fèi)者進(jìn)程1，女兒可以看作消費(fèi)者進(jìn)程2

互斥關(guān)系：(mutex = 1) 對緩沖區(qū)（盤子）的訪問要互斥地進(jìn)行

同步關(guān)系（一前一后）：

1.父親將蘋果放入盤子后，女兒才能取蘋果

2.母親將橘子放入盤子后，兒子才能取橘子

只有盤子為空時(shí)，父親或母親才能放入水果

3.偽代碼邏輯實(shí)現(xiàn)

semaphore mutex = 1; //實(shí)現(xiàn)互斥訪問盤子(緩沖區(qū)) semaphore apple = 0; //盤子中有幾個(gè)蘋果 semaphore orange = 0; //盤子中有幾個(gè)橘子 semaphore plate = 1; //盤子中還可以放多少個(gè)水果 dad(){ while(1){ 準(zhǔn)備一個(gè)蘋果; P(plate); P(mutex); 把蘋果放入盤子; V(mutex); V(apple); } } mom(){ while(1){ 準(zhǔn)備一個(gè)橘子; P(plate); P(mutex); 把橘子放入盤子; V(mutex); V(orange); } } daughter(){ while(1){ P(apple); P(mutex); 從盤子中取出蘋果; V(mutex); V(plate); 吃蘋果 } } son(){ while(1){ P(orange); P(mutex); 從盤子中取出橘子; V(mutex); V(plate); 吃掉橘子 } }

（2）讀者——寫者問題

1.問題描述

有兩組并發(fā)進(jìn)程:??讀者和寫者,共享一組數(shù)據(jù)區(qū)。

讀者/寫者問題是指保證一個(gè)寫者進(jìn)程必須與其他進(jìn)程互斥訪問共享對象的同步問題

允許多個(gè)讀者同時(shí)執(zhí)行讀操作

不允許讀者、寫者同時(shí)操作

不允許多個(gè)寫者同時(shí)操作

2.問題分析

兩類進(jìn)程：寫進(jìn)程、讀進(jìn)程

互斥關(guān)系：寫進(jìn)程——寫進(jìn)程、寫進(jìn)程——讀進(jìn)程。讀進(jìn)程與讀進(jìn)程不存在互斥關(guān)系。

寫進(jìn)程和任何進(jìn)程都要互斥，設(shè)置一個(gè)互斥信號量rw，在寫者訪問共享文件前后分別執(zhí)行P、V操作，讀者進(jìn)程和寫者進(jìn)程也要互斥，因此讀者訪問共享文件前后也要對rw進(jìn)行P、V操作，但是如果所有讀者進(jìn)程在訪問共享文件之前都進(jìn)行P(rw)操作，那么會(huì)導(dǎo)致各個(gè)讀進(jìn)程之間也無法同時(shí)訪問文件。 該如何解決這個(gè)問題？

P（rw）和V（rw）其實(shí)就是對共享文件的加鎖和解鎖，既然各個(gè)讀進(jìn)程可以同時(shí)訪問文件，而讀進(jìn)程和寫進(jìn)程需要互斥訪問文件，那么就讓第一個(gè)讀進(jìn)程對文件進(jìn)行加鎖，最后一個(gè)讀進(jìn)程對文件解鎖，如何知道是還有幾個(gè)讀進(jìn)程呢？就需要設(shè)置一個(gè)整形變量count來記錄當(dāng)前有幾個(gè)讀進(jìn)程在在訪問文件。

解決上述問題后，我們再來看這一種情況，當(dāng)兩個(gè)讀進(jìn)程并發(fā)來訪問文件時(shí)，有可能第一個(gè)進(jìn)程還沒來的及進(jìn)行count++，第二個(gè)進(jìn)程就就已經(jīng)過了判斷count是否為0的操作了，這個(gè)時(shí)候第二個(gè)進(jìn)程也被阻塞在P(rw)，再次出現(xiàn)了上述問題，該如何解決？ 其實(shí)仔細(xì)分析可知道會(huì)出現(xiàn)這種情況在于對count的判斷和賦值沒辦法保證一致性，即不是原語操作，為了解決這個(gè)問題我們要引入一個(gè)互斥信號量mutex來保證對count的判斷和賦值是一個(gè)互斥的操作。

3.偽代碼邏輯

semaphore rw = 1; //用于實(shí)現(xiàn)對文件的互斥訪問，表示當(dāng)前是否有進(jìn)程在訪問共享文件 int count = 0; // 記錄當(dāng)前有幾個(gè)讀進(jìn)程在訪問文件 semaphore mutex = 1; //用于保證對count變量的互斥訪問 writer(){ while(1){ P(rw); //寫之前"加鎖" 寫文件 V(rw); //寫之后"解鎖" } } reader(){ while(1){ P(mutex); //各進(jìn)程互斥訪問count if(count==0) P(rw); //第一個(gè)讀進(jìn)程負(fù)責(zé)加鎖 count++; //讀進(jìn)程+1 V(mutex); 讀文件 P(mutex); //各進(jìn)程互斥訪問count count--; // 訪問文件的讀進(jìn)程數(shù)-1 if(count == 0) V(rw); //最后一個(gè)讀進(jìn)程負(fù)責(zé)解鎖 V(mutex); } }

在這個(gè)算法中，讀進(jìn)程是優(yōu)先的，如果有一個(gè)讀進(jìn)程正在訪問文件，這個(gè)時(shí)候來了一堆讀進(jìn)程和一個(gè)寫進(jìn)程，那么讀進(jìn)程一直在訪問文件，寫進(jìn)程可能一直等待，發(fā)生”餓死“，如何解決這個(gè)問題？

semaphore rw = 1; //用于實(shí)現(xiàn)對文件的互斥訪問，表示當(dāng)前是否有進(jìn)程在訪問共享文件 int count = 0; // 記錄當(dāng)前有幾個(gè)讀進(jìn)程在訪問文件 semaphore mutex = 1; //用于保證對count變量的互斥訪問 semaphore w = 1 // 實(shí)現(xiàn)寫者優(yōu)先 writer(){ while(1){ P(w) P(rw); //寫之前"加鎖" 寫文件 V(rw); //寫之后"解鎖" V(w); } } reader(){ while(1){ p(w) P(mutex); //各進(jìn)程互斥訪問count if(count==0) P(rw); //第一個(gè)讀進(jìn)程負(fù)責(zé)加鎖 count++; //讀進(jìn)程+1 V(mutex); V(w); 讀文件 P(mutex); //各進(jìn)程互斥訪問count count--; // 訪問文件的讀進(jìn)程數(shù)-1 if(count == 0) V(rw); //最后一個(gè)讀進(jìn)程負(fù)責(zé)解鎖 V(mutex); } }

加入互斥信號量w就可以解決寫者餓死的問題了，當(dāng)一個(gè)讀者在讀文件時(shí)此時(shí)w已經(jīng)被解鎖了，這個(gè)時(shí)候一個(gè)寫者進(jìn)程嘗試訪問文件，先對w進(jìn)行加鎖，然后阻塞在rw，此時(shí)讀者進(jìn)程再來就會(huì)被阻塞在w，等待寫進(jìn)程執(zhí)行。

（3）哲學(xué)家進(jìn)餐問題

1.問題描述

一張圓桌上坐著5名哲學(xué)家，每兩個(gè)哲學(xué)家之間的桌上擺一根筷子，桌子的中間是一碗米飯。哲學(xué)

家們傾注畢生的精力用于思考和進(jìn)餐，哲學(xué)家在思考時(shí)，并不影響他人。只有當(dāng)哲學(xué)家饑餓時(shí)，

才試圖拿起左、右兩根筷子(一根一根地拿起)。如果筷子已在他人手上，則需等待。饑餓的哲

學(xué)家只有同時(shí)拿起兩根筷子才可以開始進(jìn)餐，當(dāng)進(jìn)餐完畢后，放下筷子繼續(xù)思考。

2.問題分析

1.關(guān)系分析。系統(tǒng)中有5個(gè)哲學(xué)家進(jìn)程，5位哲學(xué)家與左右鄰居對其中間筷子的訪問是互斥關(guān)系。

2.整理思路。這個(gè)問題中只有互斥關(guān)系，但與之前遇到的問題不同的是，每個(gè)哲學(xué)家進(jìn)程需要同時(shí)持有兩個(gè)臨界資源才能開始吃飯。如何避免臨界資源分配不當(dāng)造成的死鎖現(xiàn)象，是哲學(xué)家問題的精髓。

3.信號量設(shè)置。定義互斥信號量數(shù)組chopstick[5]={1,1,1,1,1}用于實(shí)現(xiàn)對5個(gè)筷子的互斥訪問。并對哲學(xué)家按0~4編號，哲學(xué)家i左邊的筷子編號為i，右邊的筷子編號為(i+1)%5。

semaphore chopstick[5] = {1,1,1,1,1}; Philosopher i： while (1) { 思考; P(chopstick[i]); P(chopstick[(i+1) % 5]); 進(jìn)食; V(chopstick[i]); V(chopstick[(i+1) % 5]); }

這種解法會(huì)導(dǎo)致死鎖，每個(gè)哲學(xué)家都拿一只筷子然后等待其他人放下筷子

為防止死鎖發(fā)生還可采取的措施：

最多允許4個(gè)哲學(xué)家同時(shí)去拿左邊的筷子；

僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子；

給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之

3.偽代碼邏輯

1.最多允許4個(gè)哲學(xué)家同時(shí)去拿左邊的筷子

semaphore chopstick[5] = {1,1,1,1,1}; semaphore count = 4; //最多允許四位哲學(xué)家同時(shí)進(jìn)餐 Philosopher i： while (1) { 思考; p(count); P(chopstick[i]); //取左 P(chopstick[(i+1) % 5]); //取右 進(jìn)餐; V(chopstick[i]); //放左 V(chopstick[(i+1) % 5]); // 放右 V(count); }

2.僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子；

// 記錄型信號量法 semaphore chopstick[5] = {1,1,1,1,1}; semaphore mutex = 1; //互斥的取筷子 Philosopher i： while (1) { 思考; p(mutex); P(chopstick[i]); //取左 P(chopstick[(i+1) % 5]); // 取右 V(mutex); 進(jìn)餐; V(fchopstick[i]); //放左 V(chopstick[(i+1) % 5]); // 放右 }

//AND信號量法 semaphore chopstick[5] = {1,1,1,1,1}; Philosopher i： while (1) { 思考; Swait(chopstick[(i+1)%5]，chopstick[i]); 進(jìn)餐; Signal(chopstick[(i+1) % 5],chopstick[i]); }

3.給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之

// 記錄型信號量法 semaphore chopstick[5] = {1,1,1,1,1}; Philosopher i： while (1) { 思考; if(i % 2 == 1) { P(chopstick[i]); //取左 P(chopstick[(i+1) % 5]); // 取右 }else{ P(chopstick[(i+1) % 5]); // 取右 P(chopstick[i]); //取左 } 進(jìn)餐; V(chopstick[i]); //放左 V(chopstick[(i+1) % 5]); // 放右 }

任務(wù)調(diào)度

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。