FIFO

FIFO er en forkortelse for First In, First Out, en metode til at organisere og manipulere en databuffer, hvor den ældste post, eller "hoved" i køen, behandles først. Det er analog til behandling af en kø med først til mølle, først til mølle adfærd: hvor folk forlader køen i den rækkefølge, de ankommer.

FCFS er også jargonord for FIFO operativsystemet planlægningsalgoritme, som giver enhver proces CPU-tid i den rækkefølge, hvori det er krævet.

FIFO s modsatte er LIFO, Last-In-First-Out, hvor den yngste indrejse eller 'øverst i stakken' behandles først.

En prioritet kø hverken FIFO eller LIFO, men kan vedtage lignende adfærd midlertidigt eller som standard.

Queueing teori omfatter disse metoder til bearbejdning af datastrukturer, samt interaktioner mellem streng-FIFO køer.

Computer videnskab

Datastruktur

En typisk datastruktur i C ++ sproget vil se sådan ud:

Populære Unix-systemer omfatter en sys / queue.h C / C ++ header fil, der indeholder makroer brugbare ved applikationer, der har brug for at skabe FIFO køer.

Hoved eller hale først

Kontrovers over termer "hoved" og "hale" eksisterer i forhold til FIFO køer. For mange mennesker, bør poster indtaste en kø på halen, forbliver i køen, indtil de når hovedet og forlade køen derfra. Dette synspunkt er begrundet i analogi med køer af folk venter en slags service og paralleller brugen af ​​"front" og "tilbage" i ovenstående eksempel. Andre mennesker tror, ​​at genstande ind en kø på hovedet og forlade halen, på samme måde som fødevarer passerer gennem en slange.

Rør

I computing miljøer, der understøtter rør og filtre model for InterProcess kommunikation, en FIFO er et andet navn for en navngiven pipe.

Disk planlægning

Disk-controllere kan bruge FIFO som en disk planlægning algoritme til at bestemme rækkefølgen på tjenesten disk I / O-anmodninger.

Kommunikation og netværk

Kommunikation broer, switches og routere, der anvendes i Computer netværk bruger FIFOs til at holde datapakker på vej til deres næste destination. Typisk mindst én FIFO struktur bruges pr netværksforbindelse. Nogle enheder har flere FIFO'er til samtidig og uafhængigt kø forskellige typer af information.

Elektronik

FIFOs er almindeligt anvendt i elektroniske kredsløb til buffering og flowkontrol som er fra hardware til software. I sin hardware form en FIFO består primært af et sæt af læse og skrive pegepinde, opbevaring og kontrol logik. Opbevaring kan være SRAM, flip-flops, låse eller enhver anden passende form for opbevaring. For FIFOs af ikke-triviel størrelse, er en dual-port SRAM normalt bruges, når en port er dedikeret til at skrive og den anden til læsning.

En synkron FIFO er en FIFO hvor samme ur bruges til både læsning og skrivning. En asynkron FIFO bruger forskellige ure til læsning og skrivning. Asynkrone FIFOs indføre metastabilitet spørgsmål. En fælles gennemførelse af en asynkron FIFO bruger en Gray kode for læse- og skrive pegepinde at sikre pålidelig flag generation. Et yderligere notat vedrørende flag generation er, at man nødvendigvis skal bruge pointer aritmetik til at generere flag til asynkrone FIFO implementeringer. Omvendt kan man bruge enten en "utæt spand" tilgang eller pointer aritmetik til at generere flag i synkrone FIFO implementeringer.

Eksempler på FIFO statusflag omfatter: fuld, tom, næsten fuld, næsten tom, etc.

Den første kendte FIFO gennemføres i elektronik blev udført af Peter Alfke i 1969 på Fairchild Semiconductors. Peter Alfke var senere en direktør i Xilinx.

FIFO fuld / tom

En hardware FIFO anvendes til synkroniseringsformål. Det er ofte implementeret som en cirkulær kø, og dermed har to pejlemærker:

  • Læs Pointer / Læs Adresse Register
  • Skriv Pointer / skriv Adresse Register

Læse og skrive adresser er oprindeligt både på den første hukommelse placering og FIFO kø er tom.

I begge tilfælde, læse og skrive adresser ender med at blive lige. For at skelne mellem de to situationer, en enkel og robust løsning er at tilføje en ekstra bit for hver læse og skrive adresse som vendes hver gang adressen wraps. Med dette sæt op, er betingelserne:

  0   0
Forrige artikel A1079 vej
Næste artikel Amiga Chip RAM

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha