Ringbuffer , der ( Substantiv, maskulin ) ; Struktur in Programmen

Neulich war mal die Frage nach dem "Ringbuffer" bzw. "Ringpuffer" aktuell, als es um eine Snake Programmiererei am PET ging ( siehe dort Selbstgeschriebene Spiele für die Commodore PET/CBM-Reihe ).

Da sich verschiedentlich Leute schwer damit taten, hier der Versuch einer kurzen Einführung dazu.

Wozu benötigt man soetwas überhaupt ??

Eigentlich benötigt man es nicht, zumindest rein theoretisch sollte es auch ganz ohne solche Konstrukte gehen, aber da Computer nunmal immer chronsich zu langsam waren (und sind) und zudem die Abstimmung der einzelnen Teile eines Rechners sich so erheblich vereinfacht, gibt es eben das Konzept des "Buffers" / "Puffers".

Das besondere am Rinbuffer ist eben nur, daß er in der Vorstellung als ein "Ring" gedacht werden kann. Rein praktisch ist er das natürlich eher nicht, er wird nur so aufgebaut, als wäre er "rund".

Aber erstmal was zu den Puffern.

Diese dienen dazu Daten - irgendwelcher Art - aufzunehmen und für einen relativ kurzen Zeitraum zwischenzuspeichern. Meist sind es auch eher wenige Daten, die so vorgehalten werden - von einigen wenigen Bytes bis zu ein paar Kilobytes. Lediglich bei Grafiken und Datenbanken kann das deutlich größere Werte annehmen. Etwa wenn ein Bild in einer Grafikkarte erst komplett aufgebaut wird und erst nachdem es fertig ist, als Anzeige freigeschaltet und sichtbar wird, dann aber eben komplett. In so einem Fall spricht mn von einem "Double Buffering", da man zweimal den Speicherplatz für die Anzeige bereitstellen können muß - einmal für das angezeigte Bild und dann für den Buffer, in dem gerade das kommende nächste Bild aufgebaut wird.

Noch größere Buffer sind z.B. ganze Server, die Teile des Internets laden und dann lokal zur Verfügung stellen, ohne daß jemand, der dort zugreift, die Daten direkt aus dem Netz laden muß. Das geht dann i.a. schneller und ist natürlich besonders bei z.B. Seiten mit vielen PDFs o.ä. durchaus sinnvoll.

Aber zurück zu den kleineren "Buffern".

Prinzipiell ist ein Buffer nichts anderes als ein freies Stück Speicherbereich. Dieses kann an sich auch irgendwo liegen - sinnigerweise aber natürlich eher im RAM als auf einer Diskette oder Platte, einfach weil RAM schneller ist.

Auf einem 8Bit Homecomputer z.B. als eine reservierte Speichereinheit von z.B. $100 Größe. Also etwa von Adresse $1f00 bis Adresse $1fff. Man hat damit also Platz von $00 beginnend bis zu $ff am Ende , wenn man nur die hinteren beiden Stellen anschaut. Und das sind dann genau 256 Zahlen, die man darin speichern kann.

Man sieht aber schon zwei wichtige Sachen

• der Buffer hat einen Anfang , d.h. eine Startadresse
• der Buffer hat ein Ende , d.h. eine Endadresse

beide zusammen definieren, wie groß der Buffer maximal ist

• der Buffer ist erstmal "linear" und die Speicherstellen sind quasi durchnummeriert von 0 ( $00 ) bis $ff ( 255 )

Möchte man nun Daten in so einen kleinen Speicherbereich schreiben, gibt es dafür verschiedene Ansätze.

Einer wäre etwa, daß man es sich einfach macht und darin eine Kopie von einer anderen Stelle des Speichers anlegt. Dann werden etwa die Werte von z.B. Adresse $1000 bis $10ff dahineinkopiert. Oder etwa der Bereich, in dem der Zeichensatz liegt, und man kann dann die Werte der ASCII Zeichen ändern und - sofern der Videochip das unterstützt - von der neuen Adresse bei $1f00 ausgeben.

Allerdings: Das ist NICHT unbedingt das, was gemeint ist, wenn es um "Buffer" aus der Abteilung "Ringbuffer" geht, auch wenn bei dem Beispiel natürlich durchaus was gebuffert wird ( der Zeichensatz nämlich ).

Der Unterschied ist, daß ein "echter Buffer" eine dynamische Struktur ist - v.a., was die Daten anbetrifft. Er wird nämlich benutzt um mit minmalem Aufwand ankommende Daten in ihn hineinzuschreiben, um sie ein klein wenig später direkt und unverändert wieder aus ihm auszulesen. Dabei erhalten die Daten ständig eine neue Position im Buffer, je nachdem wie voll dieser bereits ist.

Ein ankommendes Byte kann also im leeren Buffer an Position Null ( $00 ) landen, oder, wenn der Buffer schon halbvoll ist, die Adresse in der Mitte ( bei $80 ) zugewiesen bekommen.

Damit das funktioniert muß der Buffer natürlich "wissen", wo genau ein neues Byte gespeichert werden kann. Er benötigt also Information darüber, an welcher Stelle genau das nächste Byte gebuffert werden soll. Und genau dafür gibt es einen sogenannten Schreib-Zeiger ( Write-Pointer ). Das ist also einfach eine besondere (Speicher-)Stelle, in der man sich den nächsten freien beschreibbaren Platz notiert.

Bei einem leeren Buffer liegt dieser Write-Pointer natürlich erstmal auf Adresse $00.

Kommt nun ein neues Datenbyte an , dann kann dieses direkt an dieser Stelle in den Buffer geschrieben werden.

Damit ist Platz $00 dann "besetzt", was automatisch dazu führt, daß das nächste freie Plätzchen jetzt die $01 wäre - und dementsprechend muß natürlich der Write-Pointer entsprechend auf diese neue Postion gesetzt werden. Also Write-Pointer=Write-Pointer+1 .

LDX $Write-Pointer
LDA $neues-Datenbyte
STA $BufferAnfang,X
INX
... (evtl. mehrmals (loop) )

STX $Write-Pointer


( wäre so die Minimalvariante in 6502 Assembler )

Das Spiel kann man nun eine Weile machen und dadurch alle ankommenden Datenbytes "puffern" - und zwar maximal solange bis der Puffer voll ist. D.h. in dem Beispiel ist bei $ff Ende, Schluß, Fin.

Was dann passiert, kommt drauf an, was man so drumherum programmiert hat. Man könnte etwa den Buffer automatisch vergrößern. Oder man gibt eine Fehlermeldung aus, daß keine Bytes mehr angenommen werden können. Am Besten aber dimensioniert man die Maximalgröße des Buffers so, daß dieser Umstand gar nicht auftreten kann - weil der Buffer immer schnell genug wieder geleert wird.

Die Fehlermeldung eines Buffers kennt JEDER Benutzer eines Rechners, zumindest als ambitionierte Altcomputer-Bastler.

Und zwar in akustischer Form.

Sie tritt nämlich immer dann auf, wenn man den Tastaturbuffer überlastet hat und durch zuviele schnelle Tastendrücke den Buffer gefüllt hat. Dann wird i.a. ja nicht "intelligent" darauf reagiert und der Buffer vergrößert, sondern so ein DOS PC (z.B.) macht dann einfach einen "BEEP" - und teilt damit mit, daß er nicht gewillt ist, so schnell Tastendrücke anzunehmen. Die Fehlerbearbeitung wird so quasi elegant an den User delegiert - der gefälligst ein bißchen Geduld mitzubringen hat.

Interessant ist nun v.a. aber, wie der Puffer seine Daten wieder loswird !

Im Fall einer Tastatur ist das relaitv klar. Die Tastendrücke sollen in der gleichen Reihenfolge, wie sie in den Buffer gekommen sind, da auch wieder rausgelesen werden. Das heißt also, daß das erste geschriebene Byte auch als erstes wieder ausgelesen werden muß. Also im Beispiel die Adresse $00 , weil da ja zuerst geschrieben wurde. Und dann die $01 ... und so weiter.

Damit das schön klappt, benötigt man noch ein zweites Element - nämlich einen Pointer zum Lesen , den Read-Pointer. Dieser merkt sich also die Speicherstelle an der das nächste Byte ausgelesen werden kann.

Wir haben also jetzt

einen Buffer mit Anfang und Ende , der linear durchadressiert ist

und dazu zwei extra Speicherstellen irgendwo anders, in denen man sich die Postionen für Lesen bzw. Schreiben merkt ( eben Read- und Write-Pointer ).

Und damit kann man nun verschiedene Sachen machen.

Die Variante von eben - nämlich, daß man Daten aufsteigend da hineinschreibt, den Write-Pointer immer um 1 erhöht und wenn dann mal genug Zeit ist, den Lese-Pointer benutzt und bei $00 beginnend dann in einem schnellen Rutsch alle ( bzw. möglichst viele ) Datenbytes wieder ausliest - ist nur eine Möglichkeit.

Bei dieser würde man solange Daten auslesen, bis man den Write-Pointer "eingeholt" hat. An dieser Position weiß man dann, daß der Buffer komplett gelesen ist.

Und hier ist es dann auch sinnvoll, den Write-Pointer ( und den Lese-Pointer natürlich auch ) wieder auf den Startwert zurückzusetzen.

Dabei ist es noch nicht einmal nötig, die Daten aus dem Speicher zu entfernen. Diese können auch einfach im Buffer stehen bleiben. Allerdings, wenn es um Sicherheit geht, sind die dann auch von da auslesbar ! Dürfte aber bei Snake Spielen keine Rolle spielen ...

So eine Struktur hat ja eine wichtige Eigenschaft - die Daten die zuerst im Buffer landen, werden als erste auch wieder ausgelesen. Nämlich $00 wird zuerst geschrieben, dann wird $01 geschrieben, dann $02 usf. Der Lesevorgang beginnt aber ebenfalls bei $00 und läuft über $01, $02 usw.

Nach dieser Eigenschaft heißt eine derartige Form von Buffer: FIFO

das steht für " first in - first out " und beschreibt einfach nur, was da also passiert mit den gepufferten Bytes.

Die andere interesante Variante die Bytes auszulesen, beginnt gewissermaßen einfach auf der anderen Seite des Buffers.

Nachdem man den Buffer mit ein paar Bytes bereits gefüllt hat, fängt man einfach direkt beim zuletzt geschriebenen Byte an und liest dieses wieder aus. Da dadurch dann dieser Speicherplatz wieder "frei" geworden ist im Buffer, kann dabei auch automatisch der Write-Pointer wieder einen Platz nach unten gesetzt werden.

Es werden die Bytes also "von hinten" bzw. "anders herum" wieder eingesammelt. Das Byte was zuletzt in den Buffer geschrieben wurde, wird als erstes wieder ausgelesen.

Und darum benennt sich dieser Modus: LIFO

was für " last in - first out " steht. Ganz einfach.

Allerdings taugt sowas naturgemäß nicht, um z.B. Tastendrücke zu speichern, weil ja alles in umgekehrter Reihenfolge wieder augelesen wird. Aber um z.B. ganze Grafikbildschirmzeilen umzukopieren oder Texte im Speicher an andere Stellen zu kopieren, taugt es durchaus. Als Nebeneffekt eignet es sich auch um z.B. Grafiken zu spiegeln.

Und: es hat den Vorteil, daß man i.P. ja auch mit nur einem Pointer auskommen kann. Da der Write-Pointer ja immer auch automatisch die Stelle anzeigt an der das erste Byte wieder ausgelesen wird, benötigt man nicht zwei Pointer. Man muß dann halt einfach nur aufpassen, daß man bei Erreichen des Bufferendes nicht weiterschreibt und beim Auslesen die $00 nicht unterschreitet.

Zurück zur ersten Variante.

Was - könnte man sich fragen - passiert denn, wenn man in einem FIFO mit dem Write-Pointer das Ende vom Buffer erreicht ? ( $ff )

Ganz einfach: der Puffer ist voll ! Es MUSS eine Fehlermeldung ausgegeben werden. Die Bytes MÜSSEN alle mit den Lesepointer ausgelesen werden. ERST wenn dieser ebenfalls das Ende ( $ff ) erreicht, sind Write- und Read-Pointer gleich auf - und es kann auf den Bufferbeginn zurückgesetzt werden ( $00 ).

Dann ist der Buffer wieder "frei" und kann erneut benutzt werden - solange, bis dieses besondere Ereignis der Puffermaximalfüllung wieder mal erreicht wird.

Die Buffer-Füllerei beginnt damit wieder von vorn, nach gehabtem Muster.

Der Normalfall sollte aber sein, daß der Read-Pointer den Write-Pointer schon eher mal erreicht und so der "Reset" auf den Anfang eher schon gemacht werden kann, denn in der Zeit, die der Write-Pointer am Ende des Buffers verbringt, können keine neuen Datenbytes in den Buffer mehr geschrieben werden. Wohin auch ?? Er ist ja schließlich per definitionem voll. Ärgerlicherweise führt aber genau so etwas zu einem Unterbrechen des eigentlichen Nutzwertes eines Buffer - er buffert ja dann neu ankommende Bytes eben genau NICHT mehr, zumindest solange, bis er komplett ausgelesen ist und die beiden Pointer wieder auf den Anfang gesetzt worden sind.

Bei Grafiken äußert sich soetwas als Ruckeln, beim Sound als Aussetzer, beim Speichern von Daten als "stockende Schreibeinbrüche". Es ist mithin nicht optimal.

Und die Lösung ?? um das zu Verbessern ?

Die einfache Variante heißt wieder - den Buffer solange vergrößern, bis diese Effekte nicht mehr auftreten.

Nun ja - und die andere Variante hat etwas mit einer interessanten Beobachtung zu tun.

Wenn man sich das Bild von eben nochmal anschaut - das, wo der Write-Pointer das Bufferende erreicht - dann kann man da eine interessante Sache am Bufferanfang sehen.

Es ist zwar schon so, daß der Write-Pointer am Ende des Bufferbereiches steht - aber was eigentlich NICHT stimmt ist, daß der Buffer voll ist.

Denn: Ganz am Anfang gibt es ja bereits ausgelesene Bereiche, wo die Bytes einmal geschrieben und einmal gelesen worden sind, der Lese-Pointer schon vorbeigekommen ist.

Diese paar Bytes sind i.P. ja sofort und direkt nutzbar.

Man müßte nur eben den Write-Pointer dorthin positionieren. Und genau das wird auch gemacht.

Statt am Bufferende auf den Lese-Pointer zu warten, wandert der Write-Pointer gewissermaßen über das Ende hinaus und erreicht direkt den Anfang vom Buffer. Er wird also von $ff auf $00 gesetzt - aber natürlich nur, wenn da nicht noch der Lese-Pointer direkt auf $00 steht. Aber wenn der Lese-Pointer auf $10 oder $28 steht, ist das überhaupt kein Problem und $00 bis $0f bzw. $00 bis $27 sind dann beschreibbare, freie Buffer-Felder !

Und genau an dieser Stelle erscheint im übertragenen Sinne der "Oroborus" - die berühmte alte Schlange - auf dem Spielfeld. Das Ende erreicht den Anfang - oder der Anfang das Ende. Je nachdem wie man will. Oder auch Alpha und Omega treffen sich, oder ... ... aber, das führt hier zu weit und wird dann nur mystisch.

So wird erstmal nur der Write-Pointer an den Anfang gesetzt - mit dem RIESEN-Vorteil, daß jetzt weitergebuffert werden kann. Nämlich in die Anfangsfelder.

Währenddessen liest der Lese-Pointer weiterhin fleißig Daten aus.

Dabei müssen auch beide Pointer überhaupt nicht gleichschnell unterwegs sein. Es muß aber schon so sein, daß der Write-Pointer den Lese-Pointer nie überholt. Und andersherum natürlich auch. Was passiert, wenn der Lese-Pointer das Bufferende erreicht ?

Auch er wird von da auf den Beginn gesetzt - und läuft dann dem Write-Puffer wieder hinterher.

Und dieses Spiel wird immer so fortgesetzt.

Und WARUM heißt es nun RINGBUFFER ??

Es ist KEIN Ring ! Aber man kann sich das sehr schön als einen solchen vorstellen. Da aber die Struktur im Speicher trotzdem linear angelegt ist, gibt es eben Anfang und Ende und man muß an genau dem Endpunkt dafür sorgen, daß der Ring geschlossen wird, indem man den jeweiligen Pointer auf den Anfang setzt.

Dann sieht die Struktur irgendwie ungefähr so aus:

.

Wie genau baut man sowas nun auf ?

Das hat Diddl hier schon beschrieben.

Man kann dabei völlig unabhängig voneinander lesen und schreiben. Aber muß dafür natürlich beachten, wo der jeweils andere Pointer steht. Dort im Text wird das das über die Elemente Anzahl geregelt, man könnte aber auch die Pointer direkt vergleichen. Außerdem muß am Ende des Buffers der Pointer nicht nur um +1 erhöht werden sondern an dieser besonderen Stelle auch auf den Bufferanfang gesetzt werden ($00) um den Ringschluß zu erreichen.

SNAKE

Snake ist quasi ein Sonderfall eines Ringbuffers. Das besondere ist, daß man gar kein unabhängiges Schreiben/Lesen benötigt. Man weiß ja schließlich, daß die Schlange eine bestimmte Länge hat und - und nur darum benutzt man das ja dort - daß man pro Runde bzw. pro Animationsbild exakt einen Punkt am Anfang der Schlange setzen will und genau einen Punkt aus der Schlange am Schlangenende löschen will.

Dieses Muster wird nur gestört, wenn die SNAKE etwas frißt, dann ändert sich die Länge und damit der Puffer bzw. die im Puffer benutzte Speichermenge.

Aber für die reine Bewegung schließt man einfach den Ringpuffer und in diesem stehen alle Koorinaten der Schlange. Der Lese-Pointer, im einfachsten Fall, folgt direkt dem Write-Pointer. In genau einem Speicherfeld Abstand.

Der Write-Pointer schreibt, nachdem der Spieler eine Richtungstaste gedrückt hat, die neue Position vom Kopf der SNAKE in den Ringbuffer und rückt dann um eine Position im Ringbuffer vor ( s.o. , WritePointer=WritePointer+1 ). In der nächsten Runde wird er also das jetzt letzte Feld der SNAKE überschreiben. Der Lese-Pointer rückt ebenso eine Postion vor folgt also dem Write-Pointer und liest die jetzt neu gesetzt Koordinate aus. An dieser Stelle wird das Neue Kopfteil der Snake gezeichnet.

Wenn man nun will, daß die Snake auch noch am Ende gekürzt wird, muß man vor dem Schreiben der neu ermittelten Kopfposition, die in diesem Feld liegende Information nutzen, um das Schlangenende dort zu löschen.

Optimal wird das Ganze v.a. dadurch, daß man damit pro Durchgang nur eine einzige Lösch- und eine einzige Zeichenaktion für die Schlange benötigt. Das ist der eigentliche Hauptzeitgewinn dabei. Dies ließe sich auch ohne Ringbuffer erreichen. Der Vorteil des Ringbuffers ist dann v.a., daß man nicht noch zwischendurch innerhalb des Buffers irgendetwas umkopieren muß. Dabei rotiert die Schlange dann gewissermaßen mit einem Byte pro Animationsrunde durch den Ringbuffer.