FIFO ist ein Akronym für Zuerst In, Zuerst, eine mit Weisen verbundene Abstraktion sich zu organisieren und Manipulation von Daten hinsichtlich der Zeit und Priorisierung. Dieser Ausdruck beschreibt den Grundsatz einer Warteschlange, die Technik bearbeitet oder widerstreitende Anforderungen durch die Einrichtung des Prozesses durch das zuerst gekommene, zuerst gediente (FCFS) Verhalten bedient: Wo die Personen die Warteschlange in der Ordnung verlassen, kommen sie, oder das Warten von jemandes bis man an die Reihe kommt an einem Verkehrskontrollsignal an.

FCFS ist auch der Jargon-Begriff für den FIFO Betriebssystemterminplanungsalgorithmus, der jedes Prozess-Zentraleinheitsmal mit der Ordnung gibt, kommen sie. Im breiteren Sinn, die Abstraktion LIFO, oder ist In umgekehrter Reihenfolge das Gegenteil der Abstraktion FIFO Organisation. Der Unterschied ist vielleicht mit dem Betrachten des weniger allgemein verwendeten Synonyms von LIFO, FILO (Bedeutung Zuerst im Letzten) am klarsten. Hauptsächlich sind beide spezifische Fälle einer mehr verallgemeinerten Liste (auf den überall zugegriffen werden konnte). Der Unterschied ist nicht in der Liste (Daten), aber in den Regeln, für auf den Inhalt zuzugreifen. Ein Subtyp trägt zu einem Ende bei, und entfernt sich vom anderen, sein Gegenteil nimmt und stellt Dinge nur auf ein Ende.

Eine Slangschwankung auf ad hoc ist die Annäherung an umziehende Sachen von der Warteschlange als OFFO ins Leben gerufen worden, der Auf dem Feuer Zuerst eintritt.

Eine Vorzugswarteschlange ist eine Schwankung auf der Warteschlange, die für den Namen FIFO nicht qualifiziert, weil es von diesem Datenstruktur-Verhalten nicht genau beschreibend ist. Theorie von Queueing umfasst das mehr Gesamtkonzept der Warteschlange, sowie die Wechselwirkungen zwischen strengen-FIFO Warteschlangen.

Informatik

Datenstruktur

In der Informatik bezieht sich dieser Begriff auf die Weise, wie in einer Warteschlange versorgte Daten bearbeitet werden. Jeder Artikel in der Warteschlange wird in einer Warteschlange (simpliciter) Datenstruktur versorgt. Die ersten zur Warteschlange hinzuzufügenden Daten werden die ersten Daten sein, die zu entfernen sind, dann Erlös folgend in derselben Ordnung bearbeitend. Das ist typisches Verhalten nach einer Warteschlange, aber sieh auch den LIFO und schobern Sie Algorithmen auf.

Eine typische Datenstruktur wird wie aussehen

struct fifo_node

{\

struct fifo_node *next;

Value_type-Wert;

};

Klasse fifo

{\

fifo_node *front;

fifo_node *back;

fifo_node *dequeue (Leere)

{\

fifo_node *tmp = Vorderseite;

Vorderseite = Vorderseite-> als nächstes;

geben Sie tmp zurück;

}\

Warteschlange (Wert)

{\

fifo_node *tempNode = neuer fifo_node;

tempNode-> schätzen = Wert;

zurück-> als nächstes = tempNode;

zurück = tempNode;

}\};</Quelle>

(Für die Information über die abstrakte Datenstruktur, sieh Warteschlange. Für Details einer allgemeinen Durchführung, sieh Kreisförmigen Puffer.)

Populäre Unix Systeme schließen einen sys/queue.h C/C ++ Kopfball-Datei ein, die Makros zur Verfügung stellt, die durch Anwendungen verwendbar sind, die FIFO Warteschlangen schaffen müssen.

Kopf oder Schwanz zuerst

Die Meinungsverschiedenheit über die Begriffe "Kopf" und "Schwanz" besteht in der Verweisung auf FIFO Warteschlangen. Vielen Menschen sollten Sachen in eine Warteschlange am Schwanz eingehen, in der Warteschlange bleiben, bis sie den Kopf erreichen und die Warteschlange von dort verlassen. Dieser Gesichtspunkt wird analog mit Warteschlangen von Leuten gerechtfertigt, die auf eine Art Dienst warten, und passt dem Gebrauch "der Vorderseite" und "zurück" im obengenannten Beispiel an. Andere Leute glauben, dass Gegenstände in eine Warteschlange am Kopf und Erlaubnis am Schwanz auf diese Art des Essens eingehen, das eine Schlange durchführt. Auf diese Weise geschriebene Warteschlangen erscheinen in Plätzen, die herrisch, wie der GNU/Linux Betriebssystem betrachtet werden könnten.

Pfeifen

In Rechenumgebungen, die das Pfeife- und Filtermodell für die Zwischenprozess-Kommunikation unterstützen, ist ein FIFO ein anderer Name für eine genannte Pfeife.

Plattenterminplanung

Plattenkontrolleure können den FIFO als ein Plattenterminplanungsalgorithmus verwenden, um die Ordnung zu bestimmen, Platteneingabe/Ausgabe-Bitten zu bedienen.

Kommunikationen und Netzwerkanschluss

Kommunikationsbrücken, Schalter und in Computernetzen verwendete Router verwenden FIFOs, um Datenpakete im Weg zu ihrem folgenden Bestimmungsort zu halten. Normalerweise wird mindestens eine FIFO Struktur pro Netzverbindung verwendet. Einige Geräte zeigen vielfachen FIFOs für gleichzeitig und unabhängig Schlange stehende verschiedene Typen der Information.

Elektronik

FIFOs werden allgemein in elektronischen Stromkreisen für die Pufferung und Fluss-Kontrolle verwendet, die von der Hardware bis Software ist. In der Hardware-Form besteht ein FIFO in erster Linie aus einer Reihe von gelesenen, und schreiben Sie Zeigestöcke, Lagerung und kontrollieren Sie Logik. Lagerung kann SRAM, Zehensandalen, Klinken oder jede andere passende Form der Lagerung sein. Für FIFOs der nichttrivialen Größe ein Doppelhafen wird SRAM gewöhnlich verwendet, wo ein Hafen für das Schreiben verwendet wird und der andere für das Lesen verwendet wird.

Ein gleichzeitiger FIFO ist ein FIFO, wo dieselbe Uhr sowohl für das Lesen als auch für Schreiben verwendet wird. Ein asynchroner FIFO verwendet verschiedene Uhren, um zu lesen und zu schreiben. Asynchrone FIFOs führen Metastability-Probleme ein.

Eine allgemeine Durchführung eines asynchronen FIFO verwendet einen Code von Gray (oder jeden Einheitsentfernungscode) für das gelesene, und schreiben Sie Zeigestöcke, um zuverlässige Fahne-Generation zu sichern. Ein weiteres Zeichen bezüglich der Fahne-Generation ist, dass man Zeigestock-Arithmetik notwendigerweise verwenden muss, um Fahnen für asynchrone FIFO Durchführungen zu erzeugen. Umgekehrt kann man entweder einen "undichten Eimer" Annäherung oder Zeigestock-Arithmetik verwenden, um Fahnen in gleichzeitigen FIFO Durchführungen zu erzeugen.

Beispiele von FIFO Status-Fahnen schließen ein: voll, leer, fast voll, fast leer, usw.

Der erste bekannte in der Elektronik durchgeführte FIFO wurde von Peter Alfke 1969 an Halbleitern von Fairchild getan. Peter Alfke war ein Direktor an Xilinx.

Voller/leerer FIFO

In der Hardware wird FIFO zu Synchronisationszwecken verwendet. Es wird häufig als eine kreisförmige Warteschlange durchgeführt, und hat so zwei Zeigestöcke:

1. Lesen Sie Adressregister des Zeigestocks/lesen
2. Schreiben Sie Register des Zeigestocks/Schreibadresse

Lesen Sie, und Schreibadressen sind am Anfang sowohl an der ersten Speicherposition als auch an der FIFO Warteschlange ist Leer.

Leerer FIFO: Wenn gelesenes Adressregister bis Schreibadresse-Register reicht, löst der FIFO das Leere Signal aus.

VOLLER FIFO: Wenn Schreibadresse-Register reicht, um Adressregister zu lesen, löst der FIFO das VOLLE Signal aus.

Siehe auch

• LIFO (Letzt in, zuerst)
• GIGO (Müll in, Müll)

Zeichen und Verweisungen

• Cummings u. a. Simulation und Synthese-Techniken für das Asynchrone FIFO Design mit Asynchronen Zeigestock-Vergleichen, das BEHAGLICHE San Jose 2002