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

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

普通版：一類進(jìn)程作為生產(chǎn)者，生產(chǎn)產(chǎn)品，生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)，消費(fèi)者從緩沖區(qū)中取出產(chǎn)品，需要保證生產(chǎn)者不可以向滿的緩沖區(qū)中添加產(chǎn)品，消費(fèi)者不可以從空的緩沖區(qū)中取出產(chǎn)品。同一時(shí)刻只可以有一個(gè)生產(chǎn)者生產(chǎn)產(chǎn)品或者消費(fèi)者消費(fèi)產(chǎn)品。

升級(jí)版可以實(shí)現(xiàn)同一個(gè)時(shí)刻既有生產(chǎn)者生產(chǎn)產(chǎn)品，又有消費(fèi)者消費(fèi)產(chǎn)品。但是絕對(duì)不可以同一時(shí)刻多個(gè)生產(chǎn)者生產(chǎn)產(chǎn)品或者多個(gè)消費(fèi)者消費(fèi)產(chǎn)品。同時(shí)使用count記錄緩沖區(qū)中產(chǎn)品的數(shù)量。

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

1）生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都以異步方式運(yùn)行， 但它們之間必須保持同步。

2）可利用互斥信號(hào)量$mutex$實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用（不可以同時(shí)既向緩沖區(qū)中放入數(shù)據(jù)，又從緩沖區(qū)中拿出數(shù)據(jù)）；利用資源信號(hào)量empty和full分別表示緩沖池中空緩沖池和滿緩沖池的數(shù)量。 假定這些生產(chǎn)者和消費(fèi)者相互等效

/*

in表示放入數(shù)據(jù)的地址，out表示取出數(shù)據(jù)的地址

buffer[n]：表示大小為n的緩沖池（由多個(gè)緩沖區(qū)組成）

mutex，mutex1，mutex2：互斥型信號(hào)量，初值為1

empty，full：資源型信號(hào)量，empty表示空緩沖區(qū)的數(shù)量，full表示滿緩沖區(qū)的數(shù)量

item：表示一個(gè)數(shù)據(jù)項(xiàng)

*/

Int in=0,out=0;

Item buffer[n];

Semaphore mutex1=1,mutex2 = 1,empty=n,full=0;

//生產(chǎn)者

Void producer(){

do{

生產(chǎn)一個(gè)產(chǎn)品放入nextp;

/*

* 進(jìn)入?yún)^(qū)

* 先申請(qǐng)資源信號(hào)量，在申請(qǐng)互斥信號(hào)量

* mutex1控制同一個(gè)時(shí)間段內(nèi)只能有一個(gè)生產(chǎn)者生產(chǎn)產(chǎn)品

*/

wait(empty);

wait(mutex1);

/*臨界區(qū)*/

buffer[in]=nextp;

in=(in+1) % n;

/*退出區(qū)*/

signal(mutex1);

signal(full);

/*對(duì)計(jì)數(shù)器count的互斥訪問(wèn)*/

wait(mutex);

count++;

signal(mutex);

}while(TRUE)

}

//消費(fèi)者

Void consumer(){

do{

/*進(jìn)入?yún)^(qū)*/

wait(full);

wait(mutex2); //消費(fèi)者對(duì)緩沖區(qū)的互斥訪問(wèn)

/*臨界區(qū)*/

nextc =buffer[out]; //只有一份

out =(out+1) mod n;

/*退出區(qū)*/

signal(mutex2);

signal(empty);

/*對(duì)計(jì)數(shù)器count的互斥訪問(wèn)*/

wait(mutex);

count--;

signal(mutex);

消費(fèi) nextc中的產(chǎn)品;

}while(TRUE)

}

Void main(){

cobegin

proceducer();

consumer();

coend

}

注意：

1）每個(gè)程序的互斥操作wait（）和signal（）必須成對(duì)的出現(xiàn)。

2）輸入進(jìn)程不可以向滿的緩沖池中輸入數(shù)據(jù)，計(jì)算進(jìn)程不可以從空的緩沖池中取數(shù)據(jù)

3）在每個(gè)程序中的多個(gè)wait操作順序不能顛倒，必須先執(zhí)行對(duì)資源信號(hào)量的wait操作，在進(jìn)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。

4）可以使用三個(gè)互斥信號(hào)量mutex、mutex1、mutex2實(shí)現(xiàn)同一時(shí)刻既有生產(chǎn)者生產(chǎn)，又有消費(fèi)者消費(fèi)。

讀者—寫(xiě)著問(wèn)題

該問(wèn)題涉計(jì)兩類進(jìn)程，第一類進(jìn)程是讀進(jìn)程Reader，另一類進(jìn)程是寫(xiě)進(jìn)程Writer，多個(gè)讀進(jìn)程可以同時(shí)讀一個(gè)文件（共享資源），多個(gè)寫(xiě)的進(jìn)程不可以同時(shí)寫(xiě)一個(gè)文件（對(duì)寫(xiě)互斥），并且讀的時(shí)候不能寫(xiě)，寫(xiě)的時(shí)候不能讀（對(duì)讀互斥）。

1）問(wèn)題核心：保證一個(gè)Writer進(jìn)程必須與其他進(jìn)程互斥地訪問(wèn)共享對(duì)象的同步問(wèn)題。

2）只要求讀文件的進(jìn)程稱為“Reader進(jìn)程”，其它進(jìn)程則稱為“Writer進(jìn)程”。

3）允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對(duì)象，但不允許一個(gè)Writer進(jìn)程和其他Reader進(jìn)程或Writer進(jìn)程同時(shí)訪問(wèn)共享對(duì)象（共享對(duì)象并不是臨界資源，因?yàn)樗试S多個(gè)進(jìn)程對(duì)其訪問(wèn)）

/*

記錄型信號(hào)量解決讀者—寫(xiě)者問(wèn)題

rmutex：讀進(jìn)程對(duì)Readcount的互斥

wmutex：writer對(duì)reader和writer的互斥

readcount：表示正在讀的進(jìn)程數(shù)目，只有當(dāng)readcount=0的時(shí)候才需要申請(qǐng)wmutex權(quán)限，大于0的時(shí)候不需要

*/

semaphore rmutex=1, wmutex =1;

int readcount =0;

Void Reader(){

do{

wait(rmutex); //防止多個(gè)reader進(jìn)程對(duì)readcount的訪問(wèn)

if (Readcount==0){ //如果readcount不等于0，表示有進(jìn)程正在進(jìn)行讀操作，絕對(duì)沒(méi)有寫(xiě)操作

wait(wmutex);

}

Readcount ++;

signal(rmutex);

…

讀;

…

wait(rmutex);

Readcount - -;

if (Readcount==0){ //只有等于0的時(shí)候才需要釋放資源，使得寫(xiě)進(jìn)程可以工作

signal(wmutex);

}

signal(rmutex);

}while(TRUE);

}

Void writer(){

do{

wait(wmutex); //申請(qǐng)寫(xiě)權(quán)限的資源

寫(xiě);

signal(wmutex);

}while(TRUE);

}

Void main(){

cobegin

reader(); writer();

Coend

}

利用信號(hào)量集的機(jī)制實(shí)現(xiàn)讀者-寫(xiě)者問(wèn)題

int RN;

semaphore L = RN; //表示讀者的數(shù)量

mx = 1； //對(duì)寫(xiě)者進(jìn)行互斥的訪問(wèn)

void Reader(){

while(true){

Swait(L, 1, 1); //申請(qǐng)一個(gè)讀者進(jìn)程

Swait(mx, 1, 0); //判斷當(dāng)前是否有寫(xiě)者進(jìn)程在寫(xiě)，該出相當(dāng)于一個(gè)開(kāi)關(guān)

operation...

Ssignal(L, 1);

}

}

void Writer(){

while(true){

//此處首先申請(qǐng)一個(gè)mx，如果當(dāng)前系統(tǒng)中無(wú)寫(xiě)者進(jìn)程，則該語(yǔ)句必定執(zhí)行成功，Reader進(jìn)程中的

//Swait（mx, 1, 0）便處于關(guān)閉狀態(tài)，只需要等系統(tǒng)中的讀進(jìn)程執(zhí)行完畢，(L, RN，0)執(zhí)行成

//功，打開(kāi)開(kāi)關(guān)即可。

Swait(mx, 1, 1; L, RN, 0);

operation...；

//釋放一個(gè)寫(xiě)進(jìn)程

Ssignal(mx, 1);

}

}

void main(){

cobegin

Reader();

Writer();

coend;

}

哲學(xué)家的進(jìn)餐問(wèn)題

五個(gè)哲學(xué)家共用一張圓桌，分別坐在周?chē)奈鍙堃巫由希谧雷由嫌形逯煌牒臀逯豢曜樱麄兊纳罘绞绞墙惶娴剡M(jìn)行思考和進(jìn)餐。平時(shí)，一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左右最靠近他的筷子，只有在他拿到兩只筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子繼續(xù)思考。

/*

記錄型信號(hào)量解決問(wèn)題

*/

//每一只筷子均為臨界資源

semaphore chopstick[5]={1,1,1,1,1};

//所有的信號(hào)量均被初始化為1，第i位哲學(xué)家的活動(dòng)可描述為：

do{

wait(chopstick[i]); //拿左手的筷子

wait(chopstick[(i+1) mod 5] ); //拿右手的筷子

…

eat;

…

signal(chopstick[i]); //放左手

signal(chopstick[(i +1)mod 5]); //放右手

…

think;

}while(TRUE);

存在的問(wèn)題：假如五位哲學(xué)家同時(shí)饑餓而各自拿起左邊的筷子時(shí)，就會(huì)使五個(gè)信號(hào)量chopstick均為0，當(dāng)他們?cè)僭噲D去拿右邊的筷子時(shí)，都將因無(wú)筷子可拿而無(wú)限等待。進(jìn)入死鎖狀態(tài)。

解決辦法：

**1）**至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢后釋放出他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。

semaphore chopstick[5]={1，1，1，1，1};

semaphore count=4;

void philosopher(int i)

{

while(true)

{

think();

wait(count); //請(qǐng)求進(jìn)入房間進(jìn)餐

wait(chopstick[i]); //請(qǐng)求左手邊的筷子

wait(chopstick[(i+1)%5]); //請(qǐng)求右手邊的筷子

eat();

signal(chopstick[(i+1)%5]); //釋放右手邊的筷子

signal(chopstick[i]); //釋放左手邊的筷子

signal(count); //退出房間釋放信號(hào)量

}

}

**2）**僅當(dāng)哲學(xué)家的左右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。

/*

使用AND型信號(hào)量解決，本質(zhì)當(dāng)同時(shí)擁有兩只筷子的時(shí)候才允許拿起筷子進(jìn)餐

*/

semaphore chopstick[5]={1,1,1,1,1};

Philosopher i

do{

think;

Swait(chopstick[(i+1)mod 5],chopstick[i ]); //同時(shí)分配兩只筷子

eat;

Ssignal(chopstick[(i+1)mod 5], chopstick[i ] ); //同時(shí)放下兩只筷子

}while(TRUE)

**3）**規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號(hào)哲學(xué)家則相反。

semaphore chopstick[5]={1,1,1,1,1};

//第i 位哲學(xué)家的活動(dòng)可描述為：

do{

//奇數(shù)位哲學(xué)家先拿左手的筷子

if i mod 2=1 {

wait(chopstick[ i ]);

wait(chopstick[ ( i +1) mod 5] )

}

//偶數(shù)位哲學(xué)家先拿右手邊的筷子

else

{

wait(chopstick[ ( i +1) mod 5] );

wait(chopstick[ i ])

}

eat;

signal(chopstick[ i ]);

signal(chopstick[(i +1)mod 5]);

…

think;

}while(TRUE)

任務(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)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。