Generaliserad processordelning - Generalized processor sharing

Generalized processor sharing ( GPS ) är en idealisk schemaläggningsalgoritm för processchemaläggare och nätverksschemaläggare . Det är relaterat till rättvis-köprincipen som grupperar paket i klasser och delar servicekapaciteten mellan dem. GPS delar denna kapacitet enligt vissa fasta vikter .

Vid processschemaläggning är GPS "en idealiserad schemaläggningsalgoritm som uppnår perfekt rättvisa. Alla praktiska schemaläggare uppskattar GPS och använder den som referens för att mäta rättvisa."

Generaliserad processordelning förutsätter att trafiken är flytande ( oändliga paketstorlekar) och kan delas upp godtyckligt. Det finns flera tjänstediscipliner som spårar GPS-prestandan ganska noggrant, såsom viktad rättvis kö (WFQ), även känd som PGPS (generalised processor sharing).

Berättigande

I ett nätverk som Internet kräver olika applikationstyper olika prestandanivåer. Exempelvis är e-post en verklig applikation för butik och vidarebefordran , men videokonferenser är inte eftersom det kräver låg latens . När paket köas i ena änden av en överbelastad länk har noden vanligtvis viss frihet att bestämma i vilken ordning den ska skicka de köade paketen. Ett exempel på beställning är helt enkelt först till kvarn, vilket fungerar bra om storleken på köerna är små, men kan leda till problem om det finns latenskänsliga paket som blockeras av paket från tuffa applikationer med högre bandbredd.

Detaljer

I GPS konfigureras en schemaläggningshanteringsflöde (även kallad "klasser" eller "sessioner") med en vikt för varje flöde. Sedan säkerställer GPS att med tanke på ett flöde och ett visst tidsintervall så att flödet kontinuerligt är eftersläpt på detta intervall ( dvs kön är aldrig tom), så gäller för något annat flöde följande relation ${\ displaystyle N}$${\ displaystyle w_ {i}}$${\ displaystyle i}$${\ displaystyle (s, t]}$${\ displaystyle i}$${\ displaystyle j}$

${\ displaystyle w_ {j} O_ {i} (s, t) \ geq w_ {i} O_ {j} (s, t)}$

där betecknar mängden bitar av flödet som produceras på intervall . ${\ displaystyle O_ {k} (s, t)}$${\ displaystyle k}$${\ displaystyle (s, t]}$

Sedan kan det bevisas att varje flöde kommer att få åtminstone en hastighet ${\ displaystyle i}$

${\ displaystyle R_ {i} = {\ frac {w_ {i}} {\ sum _ {j = 1} ^ {N} w_ {j}}} R}$

var är serverns hastighet. ${\ displaystyle R}$

Detta är en minimal ränta. Om vissa flöden inte använder sin bandbredd under en viss period delas denna återstående kapacitet av de aktiva flödena med avseende på deras respektive vikter. Tänk till exempel på en GPS-server med . Det första flödet får minst hälften av kapaciteten, medan de andra två bara får 1/4 . Icke desto mindre, om endast det andra och tredje flödet är aktivt under ett visst tidsintervall , kommer de att få var och en av kapaciteten. ${\ displaystyle w_ {1} = 2, w_ {2} = w_ {3} = 1}$${\ displaystyle (s, t]}$

Implementeringar, parametrisering och rättvisa

I GPS, och alla protokoll inspirerade av GPS, lämnas vikten till nätverksadministratören.

Generaliserad processordelning förutsätter att trafiken är flytande, dvs oändligt delbar så att när en applikationstyp har paket i kön, kommer den att få exakt den del av servern som ges med formeln ovan. Trafiken är dock inte flytande och består av paket, möjligen av varierande storlek. Därför är GPS mestadels en teoretisk idé, och flera schemaläggningsalgoritmer har utvecklats för att approximera detta GPS-ideal: PGPS, aka Weighted fair queuing , är den mest kända implementeringen av GPS, men det har vissa nackdelar och flera andra implementeringar har föreslagits , som Deficit round robin eller WF2Q.

GPS betraktas som ett rättvist ideal, och alla dess approximationer "använder det som en referens för att mäta rättvisa." Ändå finns det flera rättvisa åtgärder .

GPS är okänsligt för paketstorlekar, eftersom det antar en flytande modell.

Se även

• Nätverksschemaläggare
• Rättvis kö
• Processordelning
• Vägt rättvis kö
• Underskott runt robin
• Viktad rundrulle
• Statistisk multiplexering
• Rättvisa mått

Referenser