Producer-Consumer-Algorithmus, um vollen Puffer zu verwenden

Question

Ich las Galvin OS Buch über Producer Consumer Problem und kam durch dieses Stück Code.

Globale Definitionen

#define BUFFER_SIZE 10 
typedef struct { 
    . . . 
} item; 

int in = 0; 
int out = 0; 

Produzent

while (((in + 1) % BUFFER_SIZE) == out) 
    ; /* do nothing */ 
buffer[in] = next_produced; 
in = (in + 1) % BUFFER_SIZE ; 

Consumer

while (in == out) 
    ; /* do nothing */ 
next_consumed = buffer[out]; 
out = (out + 1) % BUFFER_SIZE; 

Nun ist dies was Galvin Buch sagt:

Dieses Schema höchstens BUFFER_SIZE erlaubt - 1 Eintragungen im Puffer an den gleichzeitig. Wir überlassen es als Übung für Sie, eine Lösung bereitzustellen, in der BUFFER_SIZE-Elemente gleichzeitig im Puffer sein können.

Das ist, was ich gefunden habe. Ist das richtig?

Produzent

buffer[in] = next_produced; //JUST MOVED THIS LINE! 
while (((in + 1) % BUFFER_SIZE) == out) 
    ; /* do nothing */ 
in = (in + 1) % BUFFER_SIZE; 

Consumer

while (in == out) 
    ; /* do nothing */ 
next_consumed = buffer[out]; 
out = (out + 1) % BUFFER_SIZE; 

Ich denke, dies löst, aber ist das richtig? Jede andere bessere Lösung möglich?

Answer 1

In der ursprünglichen Code, wenn in == out es bedeuten könnte, der Puffer ist leer oder voll. Um eine solche Mehrdeutigkeit zu vermeiden, lässt der ursprüngliche Code den Puffer nicht voll werden, wobei immer mindestens ein leerer Gegenstand übrig bleibt.

Ich bin mir nicht sicher, dass Sie dieses Problem mit Ihrer Änderung lösen: Sie können BUFFER_SIZE-Elemente setzen, aber Sie können sie nicht konsumieren. Also, buchstäblich haben Sie es gelöst, aber es wird nicht richtig funktionieren.

Grundsätzlich, um dieses Problem zu lösen, sollten Sie eine zusätzliche Information haben, so dass Sie zwischen einem leeren Puffer und voll unterscheiden können. Es gibt eine Vielzahl von Lösungen für diese, am offensichtlichsten ist es, eine zusätzliche Flagge hinzuzufügen.

Die eleganteste IMO ist in und out Zähler wie zu bedienen, sie wickeln nur den Puffer zugreifen, so:

• wenn in == out - der Puffer leer ist
• wenn abs(in - out) == BUFFER_SIZE - die Puffer voll
• den Puffer zugreifen wir buffer[in % BUFFER_SIZE] oder buffer[out % BUFFER_SIZE]

verwenden sollten wir überlassen Sie es als Übung für Sie, eine vollständige Lösung zu bieten;)