FIFO (Computer und Elektronik)

In Computer und in Systemtheorie, FIFO ist ein Akronym zum als Erster rein, als erster raus (Das erste in ist das erste), eine Methode zur Organisation der Manipulation einer Datenstruktur (häufig, insbesondere a Datenpuffer) wo der älteste (erste) Eintrag oder "Kopf" der Warteschlange, wird zuerst verarbeitet.

Eine solche Verarbeitung ist analog zur Wartung von Menschen in a Warteschlangenbereich auf einen Wer zuerst kommt, mahlt zuerst (FCFS) Basis, d. H. In derselben Sequenz, in der sie am Schwanz der Warteschlange kommen.

FCFS ist auch das Jargon Begriff für das FIFO Betriebssystemplanung Algorithmus, der jedem Prozess verleiht Zentrale Verarbeitungseinheit (CPU) Zeit in der Reihenfolge, in der es verlangt wird.[1] FIFOs Gegenteil ist LIFO, Last-In-First-Out, bei dem zuerst der jüngste Eintrag oder "Top of the Stack" verarbeitet wird.[2] A Prioritätswarteschlange ist weder FIFO noch LIFO, kann aber vorübergehend oder standardmäßig ein ähnliches Verhalten anwenden. Warteschlangenentheorie umfasst diese Verarbeitungsmethoden Datenstrukturensowie Wechselwirkungen zwischen strengen Fifo-Warteschlangen.

Informatik

Darstellung einer FIFO -Warteschlange mit Enqueue- und Dequeue -Operationen.

Abhängig von der Anwendung kann ein FIFO als Hardware -Verschiebungsregister implementiert werden oder verwenden unterschiedliche Speicherstrukturen in der Regel a Rundpuffer oder eine Art von aufführen. Informationen zur abstrakten Datenstruktur finden Sie unter Warteschlange (Datenstruktur). Die meisten Software -Implementierungen einer FIFO -Warteschlange sind nicht Faden sicher und erfordern einen Verriegelungsmechanismus, um zu überprüfen, ob die Datenstrukturkette jeweils nur von einem Faden manipuliert wird.

Der folgende Code zeigt a verlinkte Liste FIFO C ++ Sprachimplementierung. In der Praxis gibt Standardbibliothek STD :: Listenvorlage, und vermeiden Sie die Notwendigkeit der Implementierung der Datenstruktur von Grund auf.70

#enthalten  #enthalten  Verwendung Namespace std; Schablone <Modellname T> Klasse FIFO {   Struktur Knoten {   T Wert;   Shared_ptr<Knoten> nächste = nullptr;   Knoten(T _Wert): Wert(_Wert) {}   };   Shared_ptr<Knoten> Vorderseite = nullptr;   Shared_ptr<Knoten> der Rücken  = nullptr; Öffentlichkeit:   Leere Enqueue(T _Wert) {   wenn (Vorderseite == nullptr) {   Vorderseite = make_shared<Knoten>(_Wert);   der Rücken = Vorderseite;   } anders {   der Rücken->nächste = make_shared<Knoten>(_Wert);   der Rücken = der Rücken->nächste;   }   }   T Dequeue() {   wenn (Vorderseite == nullptr)   Wurf Unterlauf_error("Nichts zu dequeue");   T Wert = Vorderseite->Wert;   Vorderseite = Bewegung(Vorderseite->nächste);      Rückkehr Wert;   } };

In Computerumgebungen, die die unterstützen Pfeifen und Filter Modell für Interprozesskommunikation, ein FIFO ist ein anderer Name für a benannte Pfeife.

Festplattencontroller können das FIFO als nutzen Scheibenplanung Algorithmus zur Bestimmung der Reihenfolge für die Dienstplatte I/o Anfragen, bei denen dies auch durch denselben FCFS -Initialismus wie die zuvor erwähnte CPU -Planung bekannt ist.[1]

Kommunikation Netzwerkbrücken, Schalter und Router benutzt in Computernetzwerke Verwenden Sie FIFOs, um Datenpakete auf der Route zu ihrem nächsten Ziel zu halten. In der Regel wird mindestens eine FIFO -Struktur pro Netzwerkverbindung verwendet. Einige Geräte verfügen über mehrere FIFOs, um verschiedene Arten von Informationen gleichzeitig und unabhängig voneinander anzustellen.[3]

Elektronik

Ein FIFO -Zeitplan

FIFOS werden üblicherweise in verwendet elektronisch Schaltkreise für Pufferung und Durchflussregelung zwischen Hardware und Software. In seiner Hardware -Form besteht ein FIFO hauptsächlich aus einer Reihe von Lesen und Schreiben Zeiger, Speicher- und Steuerlogik. Lagerung kann sein Statischer Zufallszugriffsspeicher (SRAM), Flip Flops, Riegel oder andere geeignete Speicherform. Für FIFOs mit nicht trivialer Größe wird normalerweise ein Dual-Port-SRAM verwendet, bei dem ein Port dem Schreiben und dem anderen dem Lesen gewidmet ist.

Das erste bekannte FIFO in Electronics stammte 1969 von Peter Alfke bei Fairchild Semiconductor.[4] Alfke war später Direktor bei Xilinx.

Synchronizität

Ein synchrones FIFO ist ein FIFO, bei dem dieselbe Uhr sowohl zum Lesen als auch zum Schreiben verwendet wird. Ein asynchrones FIFO verwendet verschiedene Uhren zum Lesen und Schreiben und sie können vorstellen Metastabilität Ausgaben. Eine gemeinsame Implementierung eines asynchronen FIFO verwendet a Graucode (oder ein Einheitsabstandscode) für die Lese- und Schreibzeiger, um eine zuverlässige Flaggenerzeugung zu gewährleisten. Eine weitere Anmerkung zur Flaggenerzeugung ist, dass man notwendigerweise Zeigerarithmetik verwenden muss, um Flags für asynchrone FIFO -Implementierungen zu erzeugen. Umgekehrt kann man entweder a verwenden undichter Kübel Ansatz oder Zeigerarithmetik, um Flags in synchronen FIFO -Implementierungen zu erzeugen.

Eine Hardware -FIFO wird für Synchronisierungszwecke verwendet. Es wird oft als implementiert Rundwarteschlangeund so hat zwei Zeiger:

  • Lesen Sie Zeiger / Lesen Adressregister
  • Schreiben Sie Zeiger- / Schreibadressregister

Statusflaggen

Beispiele für FIFO -Statusflags sind: Voll, leer, fast voll und fast leer. Ein FIFO ist leer, wenn das Lesen gelesen wird Adressregister Erreicht das Schreibadressregister. Ein FIFO ist voll, wenn das Schreibadressregister das Lesadressregister erreicht. Lesen und Schreibadressen befinden sich anfangs sowohl am ersten Speicherort als auch die FIFO -Warteschlange leer.

In beiden Fällen sind die Read- und Schreibadressen gleich. Um zwischen den beiden Situationen zu unterscheiden, besteht eine einfache und robuste Lösung darin, einen zusätzlichen hinzuzufügen bisschen Für jede Lese- und Schreibadresse, die jedes Mal invertiert wird, wenn die Adress umwickelt. Mit dieser Einrichtung sind die Disambigierungsbedingungen:

  • Wenn das Read -Adressregister dem Schreibadressregister entspricht, ist das FIFO leer.
  • Wenn sich die Les- und Schreibadressenregister nur in der Extra unterscheiden höchstwertiges Bit Und der Rest ist gleich, das FIFO ist voll.

Siehe auch

Verweise

  1. ^ a b Andrew S. Tanenbaum; Herbert Bos (2015). Modern Operating Systems. Pearson. ISBN 978-0-13-359162-0.
  2. ^ Kruse, Robert L. (1987) [1984]. Datenstrukturen und Programmdesign (zweite Ausgabe). Joan L. Stone, Kenny Beck, Ed O'Dougherty (Mitarbeiterproduktionsprozess -Mitarbeiter) (Second (HC) Lehrbuch ed.). Englewood Cliffs, New Jersey 07632: Prentice-Hall, Inc. Div. von Simon & Schuster. p. 150. ISBN 0-13-195884-4.{{}}: CS1 Wartung: Standort (Link)
  3. ^ James F. Kurose; Keith W. Ross (Juli 2006). Computernetzwerk: Ein Top-Down-Ansatz. Addison-Wesley. ISBN 978-0-321-41849-4.
  4. ^ "Peter Alfke's Post bei Comp.arch.fpga am 19. Juni 1998".

Externe Links

  • Removi