FIFO ( eng. f irst i n, först ut " först in, först ut ") är ett sätt att organisera och manipulera data med avseende på tid och prioriteringar. Detta uttryck beskriver principen om teknisk bearbetning av kön eller upprätthållande av motstridiga krav genom att effektivisera processen enligt principen först till kvarn (FFS). Den som kommer först serveras först, nästa väntar tills serveringen av den första är avklarad, och så vidare.
Denna princip är analog med beteendet hos personer som står i kö, när människor får service i den ordning de kom in i kön. Samma sak händer till exempel vid en oreglerad korsning, när förare väntar på sin tur att fortsätta köra (det finns ingen "interference on the right"-regel i de amerikanska trafikreglerna, prioritet bestäms enligt FIFO-principen). APP används också som en förkortning för FIFO-operativsystemets schemaläggningsalgoritm, som allokerar CPU-tid till varje process i den ordning som de betjänas.
I en vidare mening är LIFO -abstraktionen ( l ast- i n, först ut " sist in, först ut ") motsatsen till FIFO-abstraktionen. Skillnaden kan bli tydligare om vi tar hänsyn till den mindre vanliga synonymen FILO, som betyder först-in-sist-ut ("först in, sist ut"). I huvudsak är båda abstraktionerna specifika fall av den mer allmänna uppfattningen om listmanipulation. Skillnaden ligger inte i listan (data), utan i regeln för innehållsåtkomst. I det första fallet görs addering till ena änden av listan, och subtrahering från den andra, i det andra fallet görs addering och subtrahering i ena änden. [ett]
I fallet med FIFO kallas listan en kö , i fallet med LIFO , en stack .
En variant av kön är prioritetskön , för vilken namnet FIFO inte kan användas, eftersom bearbetningen av datastrukturen i detta fall sker på ett annat sätt. Köteorin täcker det mer allmänna begreppet en kö, såväl som interaktionen mellan köer, där tjänsten utförs enligt den "strikta FIFO"-principen. Förkortningen FCFS ( först till kvarn , först till kvarn "först till kvarn ") används också för att beteckna denna princip . För produktion är FPFO- alternativet möjligt ( första produkt , först ut ) .
Inom datavetenskap avser termen det sätt på vilket data som behandlas i en kö lagras . Varje element i kön lagras i en ködatastruktur ( inga undantag ). Den första data som läggs till i kön kommer att vara den första som tas bort från den, det vill säga behandlingen utförs sekventiellt i samma ordning som ankomsten.
En typisk datastruktur ser ut så här (exempel i C++ ):
struct fifo_node { struct fifo_node * nästa ; värde_typ värde ; }; klass fifo { fifo_node * front ; fifo_node * tillbaka ; fifo_node * dequeue ( ogiltig ) { fifo_node * tmp = front ; front = front -> nästa ; returnera tmp ; } kö ( värde ) { fifo_node * tempNode = ny fifo_node ; tempNode -> värde = värde ; tillbaka -> nästa = tempNode ; back = tempNode ; } };(För abstrakta datastrukturer, se köer . Se ringbuffert för implementeringsdetaljer .)
Populära Unix-system inkluderar rubrikfilen sys/queue.h i programmeringsspråken C / C++ , som innehåller makron som används i FIFO-köapplikationer.
Kontroverser om begreppen "huvud" och "svans" finns i samband med FIFO-köer. För de flesta görs att lägga till ett nytt element i kön vid dess bakre del, sedan förblir detta element i kön tills det når huvudet och, följaktligen, lämnar kön därifrån. Denna synpunkt motiveras i analogi med köerna av människor som väntar på vissa tjänster, medan i exemplet ovan kan paralleller hittas med termerna "framtill" och "bak". Men vissa människor tror att det nya föremålet kommer in i köns huvud och lämnar det genom svansen, som mat som passerar genom kroppen på en orm. Köer som beskrivs på detta sätt visas där de kan anses vara officiella, till exempel i beskrivningen av operativsystemet GNU/Linux .
I datormiljöer som stöder pipeline- och filtermodeller för interprocesskommunikation är FIFO ett alternativt namn för en namngiven pipe .
Diskkontroller kan använda FIFO-metoden som en algoritm för att schemalägga disk I/O-förfrågningar.
Kommunikationsbryggor , switchar och routrar som används i datornätverk använder FIFO-buffertar för att lagra datapaket när de reser till nästa destination. Vanligtvis används minst en FIFO-struktur för varje nätverksanslutning. Vissa enheter har flera FIFO för samtidiga och oberoende köer av olika typer av information.
FIFO-principen används ofta i elektroniska kretsar för att buffra och kontrollera flödet från hårdvara till mjukvara. I hårdvaruform består en FIFO i grunden av många läs- och skrivpekare, minne och kontrolllogik. Minnesenheten kan vara SRAM , flip-flop, spärr eller någon annan lämplig typ. Större FIFO:er använder vanligtvis en dubbel SRAM-port, där en port används för att skriva och den andra för läsning.
En FIFO är synkron där samma klocka används för både läsning och skrivning. Asynkrona FIFO använder olika klockor för att läsa och skriva. Det finns ett metastabilitetsproblem när du använder asynkrona FIFO:er . Oftast, vid implementering av asynkrona FIFO-pekare, används gråkod (eller någon annan kod där två intilliggande värden på signalskalan skiljer sig med endast en bit) för att säkerställa tillförlitlig generering av flaggan. Vi noterar också att för att generera flaggor i asynkrona FIFO-implementeringar är det nödvändigt att använda aritmetiska pekare. Omvänt, för att generera flaggor i synkrona FIFO-implementeringar, kan antingen den läckande hinkalgoritmen eller samma aritmetiska pekare användas.
Exempel på FIFO-statusflaggan är: full, tom, nästan full, nästan tom, etc.
Den första kända implementeringen av FIFO inom elektronik var av Peter Alfke (1931-2011) 1969 på Fairchild Semiconductor [2] . Även Peter Alfke var direktör för Xilinx .
I hårdvaruenheter används FIFO-principen för synkronisering. Den implementeras ofta som en ringkö och har två pekare:
Initialt är läs- och skrivadresserna båda lika med den första minnespositionen, och FIFO-kön är tom.
FIFO-kön är tom När läsadressregistret kommer ikapp skrivadressregistret avger FIFO-vippan en tom-signal. FIFO-kön full När skrivadressregistret kommer ikapp läsadressregistret avger FIFO-vippan en Full-signal.