Planeringsalgoritm för närmaste slutdatum

Schemaläggningsalgoritm för närmaste förfallodatum ( EDF ) är en dynamisk schemaläggningsalgoritm. Används i realtidsoperativsystem för att placera processer i en prioriterad kö . När en schemaläggningshändelse inträffar (en uppgift är slutförd, en ny uppgift har dykt upp, etc.), söks kön efter den process som ligger närmast dess deadline. Denna process kommer att köras nästa gång.

Schemaläggning för närmsta slutförande är optimal för förebyggande system för enprocessor i följande mening: om det är möjligt att garantera att en uppsättning oberoende uppgifter, som var och en kännetecknas av en ankomsttid, ett slutförandekrav och en slutförandedeadline, inom deadline, kan garanteras för att slutföra, då kommer EDF-algoritmen också att kunna göra detta.

När du schemalägger periodiska processer som har deadlines som är lika med deras perioder, använder schemaläggningsalgoritmen närmaste slutförande full belastning. Därför kommer schemaläggningstestet för denna algoritm att vara [1] :

var  är den värsta exekveringstiden för processer och  är motsvarande period mellan deras ankomstdatum (förutsatt att den är lika med respektive deadlines).

Det vill säga, tilldelning efter närmaste slutdatum säkerställer att alla deadlines hålls, så länge som den totala CPU-användningen inte överstiger 100%. Jämfört med att använda fasta prioriteringar säkerställer schemaläggning för närmaste slutdatum att alla deadlines hålls när arbetsbelastningen är högre.

Men om systemet är överbelastat, kommer uppsättningen av processer för vilka tidsfristen kommer att missas att vara mycket oförutsägbar (det kommer att bero på den exakta tidpunkten och tiden för överbelastningen.) Detta är en märkbar nackdel för realtidssystemdesigners . Dessutom är algoritmen svår att implementera i hårdvara, och det finns svårigheter att representera deadlines i olika intervall (deadlines kan inte tilldelas mer exakt än de klockcykler som används för schemaläggning). Om modulär aritmetik används för att beräkna framtida deadlines måste fält som lagrar framtida deadlines innehålla minst värdet "dubbelt varaktigheten av den längsta förväntade exekveringstiden" + "nu". Därför är schemaläggning för närmaste slutdatum inte vanligt i industriella datorsystem i realtid.

Istället använder de flesta realtidsdatorsystem schemaläggning med fast prioritet. Med en fast prioritet är det lättare att säkerställa att när de är överbelastade kommer lågprioriterade processer att missa deadlines, medan högprioriterade processer fortfarande kommer att slutföras i tid.

Det har gjorts mycket forskning om planering av färdigställande på kort sikt ; det är möjligt att beräkna värsta tänkbara svarstider för processer med denna algoritm, att arbeta med andra typer av processer än batch-processer och att använda servrar för överbelastningshantering.

Se även

• SCHED DEADLINE  - implementering av uppgiftsschemaläggaren för närmaste slutförandetid i Linux-kärnan

Anteckningar

1. ↑ Jia Xu, David Parnas. Schemaläggningsprocesser med releasetider, deadlines, prioritet och uteslutningsrelationer.IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 16 NEJ. 3 mars 1990

Litteratur

• Pierre G. Jansen, Sape J. Mullender, Paul JM Havinga, Hans Scholten. Lättvikts EDF-schemaläggning med deadline-arv
• Stankovic, JA Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms. - Springer USA, 1998. - 273 sid. — ISBN 9780792382690 .
• Leung, JYT Handbook of Scheduling: Algoritmer, modeller och prestandaanalys. - CRC Press, 2004. - 1224 sid. — ISBN 9780203489802 .