In der Informatik und Systemtheorie ist First In, First Out (First In , First Out), kurz FIFO , eine Methode zur Organisation der Bearbeitung einer Datenstruktur (oft speziell eines Datenpuffers ), bei der der älteste (erste) Eintrag oder „Kopf“ der Warteschlange zuerst verarbeitet wird.
FIFOs werden für eine Vielzahl von Anwendungen eingesetzt. Je nach Anwendung kann ein FIFO in Hardware als elektronische Logikschaltung oder in Software implementiert werden.
Anwendungen
FIFOs finden in einer Vielzahl von Anwendungen breite Anwendung. Beispielsweise nutzen Festplattencontroller FIFOs als Festplatten-Scheduling- Algorithmus, um die Reihenfolge der Bearbeitung von Festplatten- E/A- Anforderungen festzulegen. [ 1 ] Kommunikationsnetzwerk -Bridges , Switches und Router in Computernetzwerken verwenden FIFOs, um Datenpakete auf dem Weg zu ihrem nächsten Ziel zwischenzuspeichern; typischerweise wird mindestens ein FIFO pro Netzwerkverbindung verwendet. [ 2 ] FIFOs werden im Betriebssystem-Scheduling eingesetzt , um jedem Prozess CPU-Zeit in der Reihenfolge des Bedarfs zuzuweisen . [ 1 ] FIFOs dienen außerdem zum Puffern digitaler Video- und Audiostreams, um den Austausch von Streamdaten zwischen Software oder Hardware (oder beidem) zu ermöglichen, deren Datenraten andernfalls inkompatibel wären.
Software FIFO
Softwarebasierte FIFOs verwenden typischerweise einen Ringpuffer oder eine Listenstruktur . Die meisten Softwareimplementierungen sind nicht threadsicher und benötigen einen Sperrmechanismus, um sicherzustellen, dass die Datenstrukturkette jeweils nur von einem Thread bearbeitet wird.
In Computerumgebungen, die das Pipes-and-Filters -Modell für die Interprozesskommunikation unterstützen , ist FIFO eine andere Bezeichnung für eine Named Pipe .
C++-Sprachbeispiel
Der folgende Code zeigt eine C++ -Implementierung einer verketteten FIFO- Liste . In der Praxis existieren zahlreiche Listenimplementierungen, darunter die in Unix-Systemen verbreiteten Makros aus C sys/queue.h oder die Template-Bibliothek std::list, wodurch die Notwendigkeit entfällt, die Datenstruktur von Grund auf neu zu implementieren.
#include <memory> #include <stdexcept>using namespace std ;template < typename T > class FIFO { struct Node { T value ; shared_ptr < Node > next = nullptr ;Knoten ( T _value ) : Wert ( _value ) {} };shared_ptr <Node> front = nullptr ; shared_ptr <Node> back = nullptr ;public : void enqueue ( T _value ) { if ( front == nullptr ) { front = make_shared <Node> ( _value ) ; back = front ; } else { back- > next = make_shared <Node> ( _value ) ; back = back- > next ; } }T dequeue () { if ( front == nullptr ) throw underflow_error ( "Nichts zum Aus der Warteschlange" );T Wert = front -> Wert ; front = move ( front -> next ); return Wert ; } };Elektronisches FIFO
Elektronische FIFOs werden häufig zur Pufferung und Flusssteuerung zwischen Hardwaregeräten oder zwischen Software- und Hardwaregeräten verwendet, die über endliche Zeiträume mit unterschiedlichen Datenraten arbeiten.
Ein FIFO-Speicher besteht aus zwei Zählern, die als Lese- und Schreibadressregister dienen, einem Speicherarray sowie Status- und Steuerlogik. Der Speicher ist typischerweise zweiportig, um gleichzeitige Lese- und Schreibvorgänge zu ermöglichen, und besteht aus einem Registerfile oder einem zweiportigen RAM (Arbeitsspeicher mit wahlfreiem Zugriff).
Siehe auch
Referenzen
- ^ a b Andrew S. Tanenbaum; Herbert Bos (2015). Moderne Betriebssysteme . Pearson. ISBN 978-0-13-359162-0Die
- ^ James F. Kurose; Keith W. Ross (Juli 2006). Computernetzwerke: Ein Top-Down-Ansatz . Addison-Wesley. ISBN 978-0-321-41849-4Die
