Ingångskö

Inom datavetenskap är en ingångskö en samling processer i lagring som väntar på att föras in i minnet för att köra ett program. Inmatningsköer används främst i schemaläggning av operativsystem som är en teknik för att fördela resurser mellan processer. Inmatningsköer gäller inte bara för operativsystem (OS), utan kan också tillämpas för schemaläggning inuti nätverksenheter. Syftet med schemaläggning är att säkerställa att resurserna fördelas rättvist och effektivt; därför förbättrar det systemets prestanda.

I huvudsak är en kö en samling som har data lagt till i det bakre läget och borttaget från det främre läget. Det finns många olika typer av köer, och hur de fungerar kan vara helt olika.

Operativsystem använder först till kvarn, först till kvarn-köer, kortaste återstående tid, fast prioritet förebyggande schemaläggning, round-robin schemaläggning och flernivåköschemaläggning.

Nätverksenheter använder först-in-först-ut-kö, viktad rättvis kö, prioriterad kö och anpassad kö.

Operativ system

I operativsystem laddas processer in i minnet och väntar på att deras tur ska exekveras av den centrala bearbetningsenheten ( CPU). CPU-schemaläggning hanterar processtillstånd och bestämmer när en process ska exekveras nästa gång genom att använda indatakön.

Först till kvarn, först ut

Först till kvarn, först ut-processer tas ut från kön i ordningsföljd som de sätts i kön. Med denna metod behandlas varje process lika. Om det finns två processer med olika prioritet och den lägre prioriterade processen kommer in i kön först, kommer den att exekveras först. Detta tillvägagångssätt kanske inte är idealiskt om olika processer har olika prioriteringar, särskilt om processerna är långa.

Kortaste återstående tid

Metoden med kortast återstående tid försöker förutsäga handläggningstiden för utvecklingar och placerar dem i kön från den minsta till största handläggningstiden. Denna metod uppskattar och förutsäger baserat på tidigare historik. På sikt är dess prestanda inte stabil men förbättrar processväntetiden bättre än först till kvarn.

Fast prioriterad förebyggande schemaläggning

Fast prioritets förebyggande schemaläggningsmetod tilldelar olika prioriteringar till processerna baserat på deras handläggningstid och ordnar dem i kön i prioritetsordning. CPU-serverprocesser från högre till lägre prioritet, och processer som har samma prioritet serveras som först till kvarn, först till kvarn. CPU:n kommer tillfälligt att sluta betjäna lågprioritetsprocess när en process med högre prioritet kommer in i kön.

Round-robin schemaläggning

Round-robin schemaläggningsmetod kommer att ge samma tid för varje process och cykla igenom dem. Denna metod är starkt baserad på mycket tidskrävande för varje process. För kort mycket tid kommer att fragmentera processerna, och för lång mycket tid kommer att öka väntetiden för varje process som ska exekveras. Att välja rätt mycket tid är grunden för denna metod.

Schemaläggning av köer på flera nivåer

Många köer används i Multilevel Queue Scheduling-metoden och varje kö har sin egen schemaläggningsalgoritm. Schemaläggning av köer på flera nivåer är mer komplex jämfört med andra metoder, men det ger flexibilitet för OS att betjäna olika data i komplicerade situationer.

Nätverk

I nätverk är paket nyckelgrunden för schemaläggning. Det finns många olika typer av paket som färdas runt nätverkskärnan varje dag, och de behandlas helt olika. Till exempel har röst- och videopaket högre prioritet än vanliga paket. För att hantera och distribuera paket effektivt använder nätverksenheter också ingångskö för att bestämma vilket paket som ska överföras först.

Först in, först ut kö (FIFO)

I detta läge tas paket ut från kön i den ordning som de kommer från kön. Varje paket behandlas med samma prioritet. Om ett stort paket A kommer före ett litet paket B, måste B fortfarande vänta tills A är helt serverad. Om ett system behandlar varje paket på samma sätt, kan användare uppleva förseningar i överföringen, såsom: röstpaket.

Viktad rättvis kö (WFQ)

Viktad rättvis kö använder min-max-fair-share-algoritmen för att distribuera paket. Minsta rättvisa andel betyder att nätverksoperativsystemet kommer att distribuera lika minsta resurs för varje typ av paket. Den maximala rättvisa andelen innebär att nätverksoperativsystemet kommer att tillhandahålla mer resurser för paket som behöver överföra stora mängder datum i det ögonblicket, men det kommer att ta tillbaka resursen efter överföringen. "Viktad" betyder att schemaläggaren tilldelar vikt för varje typ av paket. Baserat på vikten kommer det att avgöra hur paket ska placeras i kön och serveras. Vanligtvis kommer varje paket att viktas baserat på IP Precedence-fältet från IP-huvudet för varje paket.

Rättvis allokering = (resurskapacitet – resurs redan allokerad) / antal paket

Prioritetskö (PQ)

Prioriterad kö är uppdelad i 4 underköer med olika prioriteringar. Data i varje kö serveras endast när de högre prioriterade köerna är tomma. Om data kommer in i den tomma kön med högre prioritet medan nätverksoperativsystemet överför data från kön med lägre prioritet, kommer nätverksoperativsystemet att hålla data från kön med lägre prioritet och bearbeta data i kön med högre prioritet först. Nätverksoperativsystemet bryr sig inte om hur länge köer med lägre prioritet måste vänta på sin tur eftersom det alltid avslutar varje kö från högsta till lägsta prioritet först innan det går till nästa kö. Inom varje kö vidarebefordras paket baserat på först-in-först-ut-basis.

Anpassad kö (CQ)

Anpassad kö är uppdelad i 17 olika underköer. Den första kön, kö 0, är reserverad för nätverkets OS för att överföra systempaket, de andra 16 köerna är för användardefinierade paket. Användaren kan definiera olika viktiga paket och tilldela dem i varje kö. Varje kö har begränsad storlek och den kommer att tappa alla kommande paket om den når den gränsen. Varje kö betjänas baserat på hur mycket paket som serveras i varje kö. Om den gränsen är uppfylld kommer nätverksoperativsystemet att hålla paket med aktuell kö och betjäna nästa kö tills den kön är tom eller den når sin paketgräns. Om en kö är tom kommer nätverksoperativsystemet att hoppa över den kön och betjäna nästa kö.

Se även

Meddelandekö

Stallings, William (2003). CCIE Praktiska studier Volym II . Cisco Press. ISBN 1-58705-072-2 .
Schemaläggning av operativsystem
Operativsystem - Schemaläggning
OS-schemaläggning och buffring