Planlægningsalgoritme for den nærmeste færdiggørelsesdato

Nærmeste forfaldsdato ( EDF ) planlægningsalgoritme er en dynamisk planlægningsalgoritme. Bruges i realtidsoperativsystemer til at placere processer i en prioriteret kø . Når en planlægningshændelse opstår (en opgave er afsluttet, en ny opgave er dukket op osv.), søges køen efter den proces, der er tættest på dens deadline. Denne proces er planlagt til at køre næste gang.

Planlægning af nærmeste afslutning er optimal for uniprocessor-forebyggende systemer i følgende forstand: hvis det er muligt at garantere, at et sæt uafhængige opgaver, hver karakteriseret ved et ankomsttidspunkt, et afslutningskrav og en afslutningsfrist inden for deadline, kan garanteres for at fuldføre, så vil EDF-algoritmen også være i stand til at gøre dette.

Ved planlægning af periodiske processer, der har deadlines svarende til deres perioder, bruger planlægningsalgoritmen nærmest afslutning den fulde belastning. Derfor vil planlægningstesten for denne algoritme være [1] :

hvor  er den værst tænkelige eksekveringstid for processer og  er den tilsvarende periode mellem deres ankomstdatoer (forudsat at den er lig med de respektive deadlines).

Det vil sige, at tildeling efter nærmeste afslutningsdato sikrer, at alle deadlines overholdes, så længe det samlede CPU-forbrug ikke overstiger 100%. I forhold til at bruge faste prioriteter sikrer planlægningen af ​​den nærmeste færdiggørelsesdato , at alle deadlines overholdes, når arbejdsbyrden er højere.

Men hvis systemet er overbelastet, vil det sæt af processer, for hvilke deadline vil blive overset, være meget uforudsigeligt (det vil afhænge af den nøjagtige timing og tidspunkt for overbelastningen). Dette er en mærkbar ulempe for systemdesignere i realtid . Derudover er algoritmen svær at implementere i hardware, og der er vanskeligheder med at repræsentere deadlines i forskellige intervaller (deadlines kan ikke tildeles mere præcist end de clock-cyklusser, der bruges til planlægning). Hvis modulær aritmetik bruges til at beregne fremtidige deadlines , skal felter, der gemmer fremtidige deadlines, indeholde mindst værdien "det dobbelte af varigheden af ​​den længste forventede eksekveringstid" + "nu". Derfor er planlægning for den nærmeste færdiggørelsesdato ikke almindelig i realtids industrielle computersystemer.

I stedet bruger de fleste computersystemer i realtid fastprioriteret planlægning. Med en fast prioritet er det nemmere at sikre, at lavt prioriterede processer, når de er overbelastet, vil gå glip af deadlines, mens højprioriterede processer stadig afsluttes til tiden.

Der er blevet lavet en masse forskning i planlægning af færdiggørelse på kort sigt ; det er muligt at beregne den worst-case responstid for processer med denne algoritme, at arbejde med andre typer processer end batch-processer og at bruge servere til overbelastningshåndtering.

Se også

• SCHED DEADLINE  - implementering af opgaveplanlæggeren for det nærmeste afslutningstidspunkt i Linux-kernen

Noter

1. ↑ Jia Xu, David Parnas. Planlægning af processer med udgivelsestider, deadlines, forrang og udelukkelsesrelationer.IEEE-TRANSAKTIONER OM SOFTWARE ENGINEERING, VOL. 16 NR. 3 marts 1990

Litteratur

• Pierre G. Jansen, Sape J. Mullender, Paul JM Havinga, Hans Scholten. Letvægts EDF-planlægning med deadline-arv
• Stankovic, JA Deadline Scheduling for Real-Time Systems: Edf and Related Algoritms. - Springer USA, 1998. - 273 s. — ISBN 9780792382690 .
• Leung, JYT Handbook of Scheduling: Algoritmer, modeller og præstationsanalyse. - CRC Press, 2004. - 1224 s. — ISBN 9780203489802 .