was ist Unterschied zwischen Ringspeicher und Fifo?
Wasserprinz schrieb: > was ist Unterschied zwischen Ringspeicher und Fifo? Weißt du, was FIFO heißt? "First In - First Out" Daran kannst du dir schon die Wirkungsweise erklären. Der FIFO ist linear. Bestimmte Anzahl Speicherplätze. Wird von einer Seite gefüllt und von der anderen gelesen. Ringspeicher ist eben ein Ring. Kein Anfang und kein Ende. Es gibt einen Schreibzeiger und einen Lesezeiger.
Wasserprinz schrieb: > was ist Unterschied zwischen Ringspeicher und Fifo? Der Begriff "FIFO" ist exakt definiert: Was zuerst reinkommt, kommt zuerst raus. Nicht mehr und nicht weniger. Der Begriff "Ringspeicher" wird unterschiedlich genutzt: a.) Als Synonym zu Fifo. b.) Als ein Detail einer konkreten FIFO-Implementation oder anderer Funktionalität. c.) Als zyklischer Speicher, bei dem alte Einträge durch neue ersetzt werden. Beim "Ringspeicher" muss man immer aufpassen, was der Autor meint bzw. den Kontext mit einbeziehen.
Wasserprinz schrieb: > was ist Unterschied zwischen Ringspeicher und Fifo? Das ist wie die Frage nach dem Unterschied zwischen einer Straße und einer Autobahn. Klar, auch die Autobahn ist eine Straße. Sie ist darüber hinaus so ziemlich die beste denkbare Inkarnation einer Straße. Ganz ähnlich ist das mit FIFO vs. Ringspeicher. Ein Ringspeicher ist so ziemlich die effizienteste Implementierung für einen FIFO. Das ist schon alles.
Die Frage ist: Was passiert, wenn FIFO oder Ringspeicher voll sind? Ringspeicher: Erster Wert wird überschrieben FIFO: Letzter wert wird verworfen
Wasserprinz schrieb: > Was ist denn besser - ein Fifo oder ein Rinkspeicher? Ein Ringpuffer. http://de.wikipedia.org/wiki/Ringpuffer#Implementierung_als_Ringpuffer
so implementiere ich immer einen FIFO als Ringspeicher:
1 | #define FIFO_SIZE 8
|
2 | |
3 | struct { |
4 | uint8 r; |
5 | uint8 w; |
6 | myDataType d[FIFO_SIZE]; |
7 | } fifo = { 0, 0, { } }; |
8 | |
9 | |
10 | int isEmpty(void) { |
11 | return fifo.r == fifo.w; |
12 | }
|
13 | |
14 | int isFull(void) { |
15 | return (fifo.w + 1) % FIFO_SIZE == fifo.r; |
16 | }
|
17 | |
18 | void put(myDataType d) { |
19 | fifo.d[fifo.w] = d; |
20 | fifo.w = (fifo.w + 1) % FIFO_SIZE; |
21 | }
|
22 | |
23 | myDataType get(void) { |
24 | myDataType d = fifo.d[fifo.r]; |
25 | fifo.r = (fifo.r + 1) % FIFO_SIZE; |
26 | return d; |
27 | }
|
Bei einer FIFO-Größe von n = 2 hoch x ist es am efferentesten, da die Modulu-Operation durch eine Bit-Maskierung ersetzt werden kann. Maximal kann man n - 1 Einträge speichern. Würde man ihn ganz voll machen, gäbe es keinen unterschied zwischen voll und leer Bedingung.
:
Bearbeitet durch User
Wasserprinz schrieb: > Aber was ist, wenn beide Zeiger aufeiander liegen? Dann gibts ein paar Monate später ein paar Zeigerkinder,
Was ist besser? Die Antwort ist eine neue Frage: Was ist dir wichtiger? Werden beim FiFo die neu dazugekommenen Werte nicht rechtzeitig abgeholt, werden diese neuen Werte irgendwann den gesamten Speicherraum vollschreiben und dann ALLE möglichen (!) Tabellen und Variablen im Speicher verändern. Das Programm macht dann nur noch Blödsinn und schmiert irgendwann ab. Wird der Rigspeicher nicht rechtzeitig ausgelesen, fehlen ein paar Werte in der Abfolge der dazugekommenen Werte. Das Programm macht Fehler, weil die Daten aus dem Ringspeicher Lücken haben, läuft aber sonst stabil.
Oldie schrieb: > Werden beim FiFo die neu dazugekommenen Werte nicht rechtzeitig > abgeholt, werden diese neuen Werte irgendwann den gesamten > Speicherraum vollschreiben und dann ALLE möglichen (!) Tabellen > und Variablen im Speicher verändern. > Das Programm macht dann nur noch Blödsinn und schmiert > irgendwann ab. Passiert nur bei Leuten, die nicht programmieren können. Andere implementieren ein FIFO full Signal, und sorgen dafür, dass ein FIFO nicht voller als voll werden kann.
@Oldie Deine Erklärung benennt Probleme einer falschen oder unvollständigen SW-Implementierung eines FIFO. Es gibt Fifo-Rams aber auch als HW-Bauteile. Und dort ist es so, wie bereits beschrieben wurde: Ist der Speicher voll, so ist jeder weitere Schreibzyklus unschädlich, wird aber nicht ausgeführt, d.h. der einzuschreibende Datenwert geht verloren. Hierbei wird NICHTS bestehendes im Speicher überschrieben. SW-Implementierungen sollten das auch so machen, wenn sie sich "Fifo" nennen. Hier Link auf Tabelle mit vielen Fifo-Rams http://www.mouser.de/Semiconductors/Memory/FIFO/_/N-488uv Und hier konkret beispielhaft ein Bauteil mit 1 k x 9 Bit , das "7202" , ein eher einfaches und langsames Bauteil, aber eben mit überschaubarem Datenblatt: http://www.idt.com/document/dst/720072017202-datasheet Gruss
Erich schrieb: > Es gibt Fifo-Rams aber auch als HW-Bauteile Fifo ist ja auch eine rein funktionelle Beschreibung. Die Warteschlange am Flughafenschalter ist auch ein FIFO, zumindest wenn sich alle benehmen können. In Software ist ein Ringspeicher eine gute Implementierungsmöglichkeit (im Flughafen eher nicht), man kann es aber auch beliebig anders lösen, solange die FIFO-Eigenschaft gegeben ist. Was in einem Hardware-FIFO drinsteckt, weis man meistens nicht, aber ich schätze kein Ringspeicher. Georg
Georg schrieb: > Was in einem Hardware-FIFO drinsteckt, weis man meistens nicht, aber ich > schätze kein Ringspeicher. Selbstverständlich doch. Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren? http://electrosofts.com/verilog/fifo.html
Joe F. schrieb: > Selbstverständlich doch. > Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren? Und selbstverständlich doch. Es gibt durchaus in Hardware implementierte FIFOs auf Basis von Schieberegistern, z.B. bei Speicheroszilloskopen und insbesondere natürlich bei Kommunikationsschnittstellen.
Joe F. schrieb: > Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren? Was in diesem Fall eine einfache Shiftoperation wäre. Da ist die Frage was einfacher zu bauen ist und was man braucht bzw will. Die Anforderungen entscheiden wesentlich was man nimmt. Das wiederum entscheidet wesentlich was produziert wird. Eine einheitliche Bauform mehrfach auf dem DIE anzuornen und simpel in Reihe zu schalten ist einfacher als die Speicherzellen durch einen Schreib- und einen Lesezeiger zu Adresieren und dann, in Relation zur Shiftoperation gesehen, entsprechend komplex darauf zuzugreifen. Der Ring hat also nicht nur Vorteile. Was besser oder einfacher ist, hängt unter anderem von der Verwendung ab. Ferner lohnt sich bei sehr kleinen FiFos der zusätzliche Aufwand für den Ringspeicher eher weniger.
Angehängte Dateien:
-
Fifo.png
90 KB
Joe F. schrieb: > Selbstverständlich doch. > Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren? Wie man nur immer so sicher sein kann, dass die eigene Meinung die einzig richtige ist. Siehe Bild, da rippeln die Daten durch. Georg
Was ein sehr schönes Beispiel für einen kleinen FiFo ist. Bei dieser Größenordnung überlegt man sich zwei mal ob man den größeren Aufwand für den Ring betreibt. Das kann man machen, aber ohne weiteren Druck / Bedarf ist es oft nicht nötig.
FIFO <> Schieberegister! Auch wenn das Ding nicht 1 sondern 8(9) Bit breit ist: wenn ich einen Wert schreibe, dann will ich den auch gleich wieder lesen können und nicht warten, bis die Schlange voll ist.
Das ist ein besonderer FiFo der eines Lesezeigers oder einer Alternative Bedarf um diese Aufgabe zu erfüllen (siehe weitere Anforderungen). Ein Schiebergister ist auch ein FiFo, aber eine andere Implementierung mit anderen Zusatzeigenschaften als der Ringpuffer. Oft will man zwar das was Du da schreibst, es ist aber nicht immer die Grundanforderung. Wenn Texas Instruments, dessen Datenblatt habe ich halt zuerst vom 74S722 erwischt, das Ding FiFo nennt, so werden die das wohl nicht völlig aus der Luft gegriffen haben. ;-) Das Ding heißt FiFo. First in First out. Es heißt nicht First in at once out on demand. Und auch das könnte man anders als einen Ringspeicher realisieren, beispielsweise als ein Shiftspeicher mit Lesezeiger, welcher dem ersten Datum folgt und ohne Schreibzeiger. Oft baut man in der konkreten Realisierung einer Lösung weitere Eigenschaften in die Lösung mit ein. Diese werden dadurch aber nicht Bestandteil der Problemstellung. Daher sollte an das auch nicht als selbstverständlich mit einbeziehen. Ein konkreter FiFo hat konkrete Eigenschaften je nach Realisierung. Die Klasse der FiFos hat ihren Namen aber von der Aufgabenstellug und allgemeinen Anforderung. Wird nur die FiFo-Eigenschaft gefordert ist die Bandbreite der Lösungsmöglichkeiten weiter als nur dieser eine Weg.
:
Bearbeitet durch User
Genau FIFO, nicht First n times In, then First Out. Natürlich ist ein (seriell in/seriell out) Schieberegister auch ein FIFO, aber eben ein sehr spezielles. FIFO's benutzt man um Geschwingigkeitsunterschiede zwischen verschiedenen Baugruppen auszugleichen. Wenn die eine Seite kontinuierlich 1Mb/s aufnehmen kann, aber die andere Seite Bursts von 10Mb/s liefert. Wichtig ist nur, daß die Dauerrate unter 1Mb/s bleibt und ein Burst immer in den FIFO paßt. Und sobald was drinsteht muß es auch rauszulesen sein.
Bastler schrieb: > FIFO's benutzt man um Geschwingigkeitsunterschiede zwischen > verschiedenen Baugruppen auszugleichen. Dies ist eine Anwendungsmöglichkeit. Es handelt sich aber nicht um die Definition des FIFOs.
Bastler schrieb: > FIFO <> Schieberegister! Niemand hat behauptet, dass es sich um ein- und dasselbe handelt. Es ist jedoch möglich, bestimmte Formen von FIFOs mit Hilfe entsprechender Schieberegister zu implementieren. > Auch wenn das Ding nicht 1 sondern 8(9) Bit breit ist: wenn ich einen > Wert schreibe, dann will ich den auch gleich wieder lesen können und > nicht warten, bis die Schlange voll ist. Es ist völlig irrelevant, was DU willst. Der Rest der Welt wird sich mit Sicherheit nicht Deinen Wünschen anpassen. Die Definition von FIFO besagt ausschließlich, dass die zuerst geschriebenen Daten gelesen werden. Weitere Aussagen folgen nicht unmittelbar aus der Definition. Insbesondere folgt auch nicht unmittelbar aus der Definition, dass das Schreiben und Lesen überlappend stattfinden dürfen. Dass natürlich für konkrete Anwendungsfälle noch weitere Anforderungen an den FIFO gestellt werden müssen, ist hingegen offensichtlich, z.B. simultanes Lesen und Schreiben. Und es gibt auch FIFO-Implementationen, die dies auch erfüllen.
Bastler schrieb: > Genau FIFO, nicht First n times In, then First Out. Natürlich ist ein > (seriell in/seriell out) Schieberegister auch ein FIFO, aber eben ein > sehr spezielles. Richtig. Dieses FiFo arbeitet so und ist damit ein spezielles FiFo. Das Gleiche gilt für deine spezielle Anforderung. Diesen beiden und dem Ringpuffer ist die generelle FiFo-Eigenschaft gemein. Also sind das alles FiFos, aber für unterschiedliche Aufgaben konstruiert und damit auch nicht immer gleichsam gut geeignet. Es ist nur die FiFo-Eigenschaft durch den Begriff gefordert. Weitere Eigenschaften können hinzukommen, müssen aber nicht.! Du beschreibst die Anwendung in der ein Datenstrom mit einer mittleren Datenrate X und schnellen Bursts auf ein anderes "Medium" mit einer für X ausreichend hohen mittleren Daterate übertragen werden soll, welches aber nicht notwendig die Bursts ausreichend schnell verarbeiten kann. Das ist eine mögliche Problemstellung. Weitere Beispiele: PIN-Eingabe am Handy oder Bankautomaten etc. Befehlseingabe in der Shell Beides wäre mit einem Shift-FiFo Lösbar. Allerding bietet dieses keine Korrekturmöglichkeit. Die Eingabe müßte komplett neu erfolgen. Läßt man dies außer Acht, so lautet hier die Kernanforderung: Sammle die Eingabedaten und liefere sie (dann) in richtiger Reihenfolge ab. Darin ist kein Verbot einer Latenz, eines zeitlichen Versatzes, enthalten. Manchmal ist der zeitliche Versatz sogar gefordert um das Gegenteil von deiner Anforderung zu erreichen. Daten werden langsam gesammelt und dann in einem Rutsch abgeholt. Zu Modemzeiten hat an den Empfangspuffer oft manuell konfiguriert. Da wurde nicht jedes Byte einzelnd abgeholt. Dann gab es noch den Block-Mode bei Festplatten. Daten wurden (langsam) von der Scheibe gelesen und dann in einen Burst weitergeschckt, um den Bus nur kurz zu belegen und die Anzahl der Transfers gering zu halten. Es gibt mit Sicherheit auch noch andere, bessere Beispiele für den Shift-FiFo. Ich hab nur gerade keines im Kopf parat.
:
Bearbeitet durch User
Hier sind ja Super-Schlaumeier unterwegs, die FiFos nur als Vorschul-kompatible Implementation in Form eines Ringspeichers o.ä. kennen. Bei Stack-Overflow (ein originärer FiFo-Effekt) wird dann wohl nach Mama gerufen! Hier wurde nach den Vor- und Nachteilen von FiFo und Ringspeicher (Nichts anderes angegeben: Also die Ur-Implementation!) gefragt - nicht nach gezähmten Varianten, die sie nicht mehr unterscheidbar machen!
Oldie schrieb: > Bei Stack-Overflow (ein originärer FiFo-Effekt) wird dann wohl > nach Mama gerufen! Was meinst du damit? Ich hoffe nicht das, was da steht.
Georg schrieb: > Was in einem Hardware-FIFO drinsteckt, weis man meistens nicht, aber ich > schätze kein Ringspeicher. Jeder RAM kann zusammen mit einem Adresszähler als Ringspeicher der Länge 2^n verwendet werden, wobei n die Anzahl der verwendeten Adressbits ist.
Ich glaube nicht, daß er das mit Hardware-FiFo meinte, sondern eher einen einzelnen IC oder einen in einem größeren IC integrierten FiFo
Hätte ich mir doch blos nicht diese Schieberegisterschaltung angeschaut!
Ist doch alles ok. Dadurch wurde das Thema vertieft und man weiß nun, daß es viele unterschiedliche FiFo-Implementierungen gibt, zu denen auch Ringspeicher und Schieberegister gehören.
Angehängte Dateien:
-
Fifo2.png
52 KB
Bastler schrieb: > Hätte ich mir doch blos nicht diese Schieberegisterschaltung angeschaut! Offensichtlich hat niemand diese Schaltung verstanden - meinst du das? Es ist eben kein normales Schieberegister: hat man ein Wort reingeladen, so wird Output Ready und man kann mit dem Auslesetakt das erste reingeladene Wort bereits auslesen, und nicht wie bei einem Schieberegister erst nach 16 Takten. Also ist es genau das, was der TO unter FIFO versteht (was nichts dran ändert, dass ein einfaches Schieberegister auch ein FIFO im weiteren Sinn ist). Siehe beigefügtes Timing Diagramm. Zugegebenerweise handelt es sich nicht um eine besonders einfache Schaltung. Georg
Ich sehe da was anderes. Das ist ein Schieberegister mit getrenntem "In" und "Out" Takt. Erst wenn alle 16 drin stehen, kommt auch was raus. So sagt das zumindest das Diagramm. Aber was soll's. Ist eh uninteressant. Wer verbaut schon noch so was.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.