Termelő-fogyasztó minta
A termelő-fogyasztó minta a számítástudományban egy konkurens programtervezési minta, ami függetleníti az objektumok létrehozását azok felhasználásától. A minta egy klasszikus szinkronizációs problémát vet fel. Legalább két szál van benne, egy termelő és egy fogyasztó, és van benne egy buffer is. A termelő feladata objektumok létrehozása, és behelyezése a bufferba. A fogyasztó feladata az objektumok kivétele és felhasználása. A probléma abban áll, hogy a buffer nem tud tetszőleges mennyiségű objektumot tárolni, így ha kiürül, vagy megtelik a raktár, akkor az egyik folyamatnak várakoznia kell.
A megoldást a folyamatok kommunikációja jelenti, tipikusan szemaforok közbeiktatásával. A megoldás nem triviális, a naiv megközelítés holtpontot okozhat, amikor is mindkét folyamat a másikra vár, hogy felébressze. A megoldásra több megvalósítás is van.
A minta és a probléma általánosítható több termelőre és fogyasztóra is.
Naiv megvalósítás
[szerkesztés]A konkurens programozásban járatlan programozók gyakran a következő naiv, ám hibás megoldást adják a problémára:
int itemCount = 0;
procedure producer() {
while (true) {
item = produceItem();
if (itemCount == BUFFER_SIZE) {
sleep();
}
putItemIntoBuffer(item);
itemCount = itemCount + 1;
if (itemCount == 1) {
wakeup(consumer);
}
}
}
procedure consumer() {
while (true) {
if (itemCount == 0) {
sleep();
}
item = removeItemFromBuffer();
itemCount = itemCount - 1;
if (itemCount == BUFFER_SIZE - 1) {
wakeup(producer);
}
consumeItem(item);
}
}
A kód felhasználja a sleep és a wakeup könyvtári rutinokat. A globális itemCount a bufferban levő objektumok számát tárolja.
Ez a megoldás azért hibás, mert versenyhelyzetet eredményezhet, ami holtpontot okozhat. Tekintsük a következő lefutást:
- A fogyasztó megnézi az itemCountot; azonban mielőtt aludni menne, elveszik tőle a vezérlést.
- A termelő megkapja a vezérlést, legyárt egy objektumot, beteszi a bufferba, és felkelti a fogyasztót.
- A fogyasztó megkapja a vezérlést, de mivel nem alszik, az ébresztés elvész. A fogyasztó elalszik.
- A termelő megkapja a vezérlést, feltölti a buffert, majd aludni megy.
Mivel a folyamatokat semmi sem billentheti ki az alvásból, a program holtpontba jutott.
Ha a nyelv nem szabályozza kellőképpen a globális változókhoz való konkurens hozzáférést, akkor nem kell kimutatni a versenyhelyzetet, hiszen változót oszt meg szinkronizáció nélkül szálak között.
Megoldás szemaforokkal
[szerkesztés]A szemaforos megoldás két szemafort használ az elveszett jelek problémájának megoldásához, ezek a fillCount és az emptyCount. A fillCount a bufferban levő objektumok számát tartalmazza, míg az emptyCount az üres helyek számát tartja nyilván. Ha az egyik folyamat nulla értékűt próbál csökkenteni, akkor elalszik, de felébred, ha a megfelelő szemafor értéke pozitív (termelő esetén az emptyCount, fogyasztó esetén a fillCount).
semaphore fillCount = 0; // items produced
semaphore emptyCount = BUFFER_SIZE; // remaining space
procedure producer() {
while (true) {
item = produceItem();
down(emptyCount);
putItemIntoBuffer(item);
up(fillCount);
}
}
procedure consumer() {
while (true) {
down(fillCount);
item = removeItemFromBuffer();
up(emptyCount);
consumeItem(item);
}
}
Megoldás monitorokkal
[szerkesztés]Az alábbi pszeudokód monitoros megoldást nyújt a problémára. Mivel a monitorok implicit tartalmazzák a kölcsönös kizárást, a kritikus szakaszt nem kell külön védeni. Ez azt jelenti, hogy ez a megoldás akárhány termelővel és fogyasztóval működik módosítás nélkül. Érdemes megjegyezni, hogy monitorokkal nehezebben áll elő versenyhelyzet, mint szemaforokkal.
monitor ProducerConsumer {
int itemCount;
condition full;
condition empty;
procedure add(item) {
while (itemCount == BUFFER_SIZE) {
wait(full);
}
putItemIntoBuffer(item);
itemCount = itemCount + 1;
if (itemCount == 1) {
notify(empty);
}
}
procedure remove() {
while (itemCount == 0) {
wait(empty);
}
item = removeItemFromBuffer();
itemCount = itemCount - 1;
if (itemCount == BUFFER_SIZE - 1) {
notify(full);
}
return item;
}
}
procedure producer() {
while (true) {
item = produceItem();
ProducerConsumer.add(item);
}
}
procedure consumer() {
while (true) {
item = ProducerConsumer.remove();
consumeItem(item);
}
}
A fenti kódban a while kulcsszót találjuk, amikor teszteljük, hogy a buffer teli van-e. Például több fogyasztó esetén versenyhelyzet adódik, ha a kiürült bufferba új elem került. Egy másik fogyasztó eltávolíthatja az elemet. Előfordulhatna, hogy egyszerre többen próbálnának betenni, vagy kivenni elemet.
Monitorok és szemaforok nélkül
[szerkesztés]Az egy termelő és fogyasztó mintája szorosan kapcsolódik egy cső vagy egy csatorna megvalósításához. Hatékony kommunikációt tesz lehetővé monitorok, szemaforok és mutexek nélkül. Használatuk lelassítja a programot, mivel kezelésük sok időt igényel. A csövek és a csatornák azért népszerűek, mert elkerülik a szinkronizációt. Később erre egy C példát is mutatunk. Jegyezzük meg, hogy:
- Nincs szükség a közös változók atomi kezelésére, ugyanis ezek helyett olyan változókat használnak, amiket egy-egy szál kezel. Az egész túlcsordulás kezelését is lehet korrekt módon kezelni.
- A példa nem küldi aludni a szálakat. A sched_yield() csak azért van, hogy a kód szépen nézzen ki, törölhető. Kontextustól függ, hogy az alvás mellőzése mennyire elfogadható. A szálkönyvtárak rendszerint szemaforokkal vagy feltételváltozókkal kezelik az alvást. Több processzoros környezetben a szálak alvása és felébresztése ritkább, mint az adattokenek átadása, így az adatátadáson végzett atomi műveletek elkerülése előny.
- A példa nem működik több termelővel illetve fogyasztóval, mivel ekkor versenyhelyzet adódik az állapot ellenőrzésekor. Például ha két fogyasztó is úgy találja, hogy a buffer nem üres, akkor mindketten elfogyaszthatják ugyanazt az objektumot, így az elfogyasztott objektumok száma meghaladhatja a megtermeltekét.
- A példa megköveteli, hogy UINT_MAX + 1 maradék nélkül osztható legyen a buffer méretével, különben nem tudja kezelni az egészek túlcsordulását. Különben ugyanis [Count % BUFFER_SIZE] rossz indexet ad a túlcsordulás után, amikor Count az UINT_MAX után nullára vált. Egy alternatív megoldás két Idx változót kezel, egyet a termelő, egyet a fogyasztó számára, és akkor kell őket növelni, amikor a Count változót kellene. Ekkor a növelés formája: Idx = (Idx + 1) % BUFFER_SIZE.
volatile unsigned int produceCount = 0, consumeCount = 0;
TokenType buffer[BUFFER_SIZE];
void producer(void) {
while (1) {
while (produceCount - consumeCount == BUFFER_SIZE)
sched_yield(); /* `buffer` is full */
/* You must update the field in the buffer _before_ incrementing your
* pointer.
*/
buffer[produceCount % BUFFER_SIZE] = produceToken();
++produceCount;
}
}
void consumer(void) {
while (1) {
while (produceCount - consumeCount == 0)
sched_yield(); /* `buffer` is empty */
consumeToken(&buffer[consumeCount % BUFFER_SIZE]);
++consumeCount;
}
}
Források
[szerkesztés]- Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces
Fordítás
[szerkesztés]Ez a szócikk részben vagy egészben a Producer–consumer problem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.