Køprioritering med simuleret intuition: SRPT, SJF og to-klasse-regler

Den røde tråd

De tre artikler bygger oven på hinanden. Det er en rejse fra den rene, perfekt analyserbare verden mod den rodede, realistiske:

1. Schrage & Miller (1966) M/G/1 Én server, perfekt kendte servicetider, uendelig tålmodige jobs. Her er Shortest Remaining Processing Time (SRPT) beviseligt optimal for middel-flowtid, og der findes lukkede formler.
2. Grosof, Scully & Harchol-Balter (2018) M/G/k Flere servere. SRPT er ikke længere garanteret optimal i værste fald, men forfatterne viser at den er asymptotisk optimal når lasten nærmer sig kapacitet (ρ → 1).
3. Dong & Ibrahim M/GI/s+GI Mange servere, kunder der giver op (abandonment), og støjfulde estimater af servicetiden. Her skifter målet fra flowtid til throughput, og hovedpointen er, at en simpel to-klasse-prioritering kan matche fuld SJF.

Den fælles grundmekanik

Alle tre modeller deler den samme byggeklods: Poisson-ankomster med rate λ, servicetider trukket fra en fordeling, og en scheduling-regel der afgør hvem der får serveren. Forskellen ligger i antal servere, om jobs kan give op, og om vi kender servicetiderne præcist. Vores simulatorer er alle diskret-event-motorer: de hopper fra hændelse til hændelse (ankomst, service-slut, abandonment) og opdaterer systemtilstanden.

Model 1 · M/G/1 og SRPT Schrage & Miller 1966

Schrage & Miller beviste at SRPT minimerer middel-flowtid i M/G/1, og udledte en lukket formel for den. De sammenlignede også FCFS, ikke-præemptiv SPT, og to-klasse-regler. Den interessante intuition fra deres Tabel I: de grove to-klasse-regler henter langt det meste af gevinsten ved blot at skelne "kort" fra "lang". Det er præcis den pointe Dong & Ibrahim genfinder 60 år senere i den langt mere komplekse mange-server-verden.

Simulatoren herunder kører M/G/1 og lader dig vælge disciplin. Den teoretiske SRPT-flowtid beregnes ved numerisk integration af Schrage & Millers formel og tegnes som en stiplet linje. For eksponentielle servicetider med middel 1 reduceres FCFS-flowtiden til 1/(1−ρ), hvilket vi også viser.

Model 2 · M/G/k og SRPT-k Grosof et al. 2018

Med flere servere er SRPT ikke længere optimal i værste fald: Leonardi & Raz konstruerede modeksempler hvor SRPT-k kan være vilkårligt dårligere end optimum. Grosof et al. redder situationen i den stokastiske, høj-last-grænse: de viser at middel-svartiden under SRPT på k servere (hver med fart 1/k) nærmer sig middel-svartiden under SRPT på én hurtig server, når ρ → 1. Da single-server SRPT er optimal, er SRPT-k dermed asymptotisk optimal blandt alle k-server-regler.

Den centrale størrelse: forholdet E[T_SRPT-k] / E[T_SRPT-1] → 1 når ρ → 1. Simulatoren kører begge systemer på den samme ankomststrøm og plotter dette forhold mod lasten, så du ser konvergensen mod 1 (præcis som forfatternes Figur 3.1).

Model 3 · M/GI/s+GI med abandonment og støjfuld SJF Dong & Ibrahim

Nu bliver det realistisk. Mange servere, kunder med endelig tålmodighed der giver op hvis de venter for længe, og kun et støjfuldt estimat af hver kundes servicetid. Når systemet er overbelastet (ρ > 1) er throughput den interessante størrelse: nogle kunder vil uundgåeligt give op, og en god scheduling-regel maksimerer hvor mange der faktisk bliver betjent.

Dong & Ibrahims hovedresultater, som simulatoren genskaber:

• Støjfuld SJF maksimerer throughput blandt alle ikke-præemptive regler der bruger samme estimat.
• En to-klasse-regel matcher SJF. Del kunder i "kort estimat" (under en tærskel τ) og "langt estimat". Prioriter de korte. Asymptotisk er det lige så godt som fuld SJF, men langt nemmere at implementere.
• Mere præcise estimater → højere throughput. Throughput stiger monotont med korrelationen mellem faktisk og forudsagt servicetid. Med meget støj nærmer SJF sig FCFS; med perfekt info nærmer den sig SJF uden støj.

Vi bruger lognormale servicetider med middel 1, ligesom i artiklen. Parameteren α (0 til 1) styrer hvor god prediktionen er: α ≈ 0 er næsten ren støj, α ≈ 1 er næsten perfekt. Simulatoren rapporterer throughput (andel betjent) under FCFS, støjfuld SJF og den to-klasse-regel.

Hvad simulatorerne lærer dig

• Den grove regel er overraskende god. Både Schrage-Miller (M/G/1) og Dong-Ibrahim (mange servere) viser, at to klasser henter næsten hele gevinsten. Du kan se det selv: i Model 1 ligger SPT tæt på SRPT ved moderat last; i Model 3 ligger to-klasse tæt på fuld SJF, og afstanden er mindst når estimaterne er støjfulde (det realistiske tilfælde).
• Asymptotik virker, men kan være langsom. I Model 2 nærmer forholdet sig 1 når ρ → 1, og konvergensen er hurtigere for små k. Det er hele pointen i Grosof et al. (de simulerer helt op til ρ = 0.9975).
• Støj koster, men graciøst. I Model 3 falder throughput glat fra "SJF uden støj" mod "FCFS" når α falder. Forringelsen er øvre begrænset af gabet mellem de to.

Nøglebegreber

Scheduling-discipliner

• FCFS (First-Come-First-Served): ingen brug af servicetid. Alle ikke-spildende regler der ignorerer servicetid har samme middel-flowtid som FCFS (men andre højere momenter). Se Schrage & Miller (1966), s. 679.
• SPT (Shortest Processing Time): ikke-præemptiv, vælg det korteste ventende job. Den optimale ikke-præemptive regel. Beskrevet via Phipps i Schrage & Miller (1966), s. 671.
• SRPT (Shortest Remaining Processing Time): præemptiv, serveren arbejder altid på jobbet med mindst resterende arbejde. Bevist optimal for middel-flowtid i M/G/1 i Schrage (1968); flowtidsformlen kommer fra Schrage & Miller (1966).
• SJF (Shortest Job First): den ikke-præemptive slægtning til SRPT, brugt af Dong & Ibrahim fordi præemption ofte er praktisk umulig i servicesystemer (man afbryder ikke en kunde midt i en samtale). Se Dong & Ibrahim, afsnit 1.

Systemstørrelser

• Trafikintensitet ρ = λ/(s·µ). Forholdet mellem ankommende arbejde og servicekapacitet. Under 1 er systemet stabilt uden abandonment; over 1 kræver det abandonment for stabilitet. Defineret i Dong & Ibrahim, afsnit 3.1.
• Flowtid / svartid (response time). Tid fra ankomst til færdig service. Ved Little's lov er middel-antal-i-systemet = λ × middel-flowtid, så at minimere flowtid er det samme som at minimere kølængden. Se Schrage & Miller (1966), s. 670.
• Throughput. Rate af kunder der faktisk bliver betjent (ikke giver op). Det relevante mål i overbelastede systemer med abandonment. Dong & Ibrahim, afsnit 1.3.
• Abandonment / reneging. Kunder har endelig tålmodighed og forlader køen hvis ventetiden overstiger deres tålmodighedstid. Modelleret med en patience-fordeling F. Dong & Ibrahim, afsnit 3.1.

Analyseteknikker

• Tagged-job / busy-period-argument. Følg ét "mærket" job og udtryk dets ventetid via en travl-periode. Grundstenen i Schrage & Millers M/G/1-udledning; Grosof et al. udvider den til multiserver via begrebet virtual work (Grosof et al. 2018, afsnit 2).
• Heavy-traffic-grænse (ρ → 1). I lav last domineres svartid af servicetid (uafhængig af reglen); i høj last domineres den af ventetid. Derfor analyseres optimalitet i grænsen ρ → 1. Grosof et al. 2018, afsnit 1.
• Fluid-grænse for mange servere. Når antal servere → ∞ kollapser den komplekse stokastiske beskrivelse til deterministiske flydende ligninger. Dong & Ibrahim bygger på fluid-grænser for prioritetskøer med reneging fra Atar et al. (2014).
• State-space collapse. I grænsen bliver det fulde SJF-system uskelneligt fra en simpel to-klasse-prioritetskø. Dong & Ibrahim, Lemma 5.
• Positiv regressionsafhængighed / PQD-orden. Det matematiske mål for "hvor godt estimatet er". Højere korrelation mellem faktisk og forudsagt servicetid giver højere throughput. Dong & Ibrahim, Theorem 2 og afsnit 5.

Hvorfor multiserver er svært

Mange-server-køer er ikke order-conserving og under SRPT-k ikke work-conserving, så de klassiske single-server-argumenter (som tagged-job-metoden) overføres ikke direkte. Det er grunden til at multiserver-SRPT var et åbent problem i årtier. Se Grosof et al. (2018), afsnit 1, og Dong & Ibrahim, afsnit 1.2.

Videre læring

Bøger

• Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Cambridge, 2013). Den bedste indgang til scheduling og kø-teori for praktikere; selve referencebogen Grosof et al. bruger til SRPT-1-ventetiden. Kapitlerne om M/G/1-scheduling og SRPT er direkte relevante for Model 1.
• Shaked & Shanthikumar, Stochastic Orders (Springer, 2007). Slå PQD-ordenen op (kapitel 9) for at forstå Dong & Ibrahims afhængighedsresultater.

Artikler at læse i rækkefølge

1. Start med Schrage & Miller (1966): den er gammel, klar og fuld af intuition. Tabel I/II giver præcis den "to klasser er nok"-fornemmelse.
2. Læs derefter Grosof et al. (2018) (den korte konference-version her, eller den fulde IFIP-version) for virtual-work-tricket.
3. Slut med Dong & Ibrahim for den moderne mange-server-historie med støj og abandonment.
4. Som baggrund: Scully, Harchol-Balter & Scheller-Wolf (2018) "SOAP: One Clean Analysis of All Age-Based Scheduling Policies" giver en samlet ramme for hele familien af alders-baserede regler.

Øvelser med simulatorerne ovenfor

• Verificér Schrage-Miller-formlen. I Model 1, sæt CV² = 1 og kør SRPT for ρ = 0.5, 0.7, 0.9. Sammenlign med den stiplede teorikurve. Hvor mange jobs skal du bruge før den empiriske værdi er inden for 1 %?
• Find heavy-traffic-skiftet. I Model 1, øg CV². FCFS eksploderer; hvordan klarer SRPT sig? Det illustrerer hvorfor variabilitet er FCFS' fjende men SRPT's ven.
• Mål konvergenshastigheden. I Model 2, sammenlign konvergens-kurven for k = 4 og k = 30. Hvilken når hurtigst forholdet 1.1?
• Genskab "to klasser er nok". I Model 3, kør α-kurven. Bekræft at gabet mellem to-klasse og fuld SJF er mindst ved lav α (støjfulde estimater) — det praktisk vigtige tilfælde.
• Test abandonment-følsomhed. I Model 3, varier tålmodighed 1/θ ved fast ρ. Hvordan ændrer det throughput-rangordningen mellem reglerne?

Online

• Down (2019), "Open problem: size-based scheduling with estimation errors", Stochastic Systems — det åbne problem som Dong & Ibrahim adresserer; god kontekst for hvorfor støj er svært.
• Scully, Grosof & Mitzenmacher (2021), "Uniform bounds for scheduling with job size estimates", arXiv:2110.00633 — single-server-behandling af præcis det støj-problem du møder i Model 3.

Kilder

1. Schrage, L. E. & Miller, L. W. (1966). The Queue M/G/1 with the Shortest Remaining Processing Time Discipline. Operations Research 14(4), 670–684. jstor.org/stable/168730
2. Schrage, L. (1968). Letter to the Editor — A Proof of the Optimality of the Shortest Remaining Processing Time Discipline. Operations Research 16(3), 687–690.
3. Grosof, I., Scully, Z. & Harchol-Balter, M. (2018). SRPT for Multiserver Systems. Performance Evaluation Review 46(2), 9–11 (full version: IFIP Performance 2018). Performance Evaluation 127, 154–175.
4. Dong, J. & Ibrahim, R. Shortest-Job-First Scheduling in Many-Server Queues with Impatient Customers and Noisy Service-Time Estimates. (Working paper; bygger på Dong & Ibrahim 2021, Management Science 67(12), 7708–7718.)
5. Atar, R., Kaspi, H. & Shimkin, N. (2014). Fluid Limits for Many-Server Systems with Reneging under a Priority Policy. Mathematics of Operations Research 39(3), 672–696.
6. Leonardi, S. & Raz, D. (2007). Approximating Total Flow Time on Parallel Machines. Journal of Computer and System Sciences 73(6), 875–891.
7. Scully, Z., Harchol-Balter, M. & Scheller-Wolf, A. (2018). SOAP: One Clean Analysis of All Age-Based Scheduling Policies. Proc. ACM Meas. Anal. Comput. Syst. 2(1), 1–30.
8. Down, D. G. (2019). Open Problem — Size-Based Scheduling with Estimation Errors. Stochastic Systems 9(3), 295–296.
9. Scully, Z., Grosof, I. & Mitzenmacher, M. (2021). Uniform Bounds for Scheduling with Job Size Estimates. arXiv:2110.00633.
10. Harchol-Balter, M. (2013). Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press.
11. Shaked, M. & Shanthikumar, J. G. (2007). Stochastic Orders. Springer.
12. Little, J. D. C. (1961). A Proof for the Queuing Formula L = λW. Operations Research 9, 383–387.