Minst slö tidsplanering
Least slack time ( LST ) schemaläggning är en algoritm för dynamisk prioritetsschemaläggning . Den prioriterar processer baserat på deras slöa tid . Slack time är den tid som är kvar efter ett jobb om jobbet påbörjades nu. Denna algoritm är också känd som minsta slapphet först . Dess vanligaste användning är i inbyggda system , särskilt de med flera processorer. Det ålägger den enkla begränsningen att varje process på varje tillgänglig processor har samma körtid och att individuella processer inte har en affinitet till en viss processor. Det är detta som gör den lämplig för inbyggda system.
Fritid
Denna schemaläggningsalgoritm väljer först de processer som har den minsta "slack time". Slacktid definieras som den tidsmässiga skillnaden mellan deadline, beredskapstiden och körtiden.
Mer formellt definieras slacktiden
där är processtiden, är realtiden sedan cykelns start, och är den återstående beräkningstiden.
Ansökningar
I realtidsschemaläggningsalgoritmer för periodiska jobb krävs ett acceptanstest innan du accepterar ett sporadiskt jobb med en hård deadline. Ett av de enklaste acceptanstesterna för ett sporadiskt jobb är att beräkna mängden slacktid mellan releasetiden och deadline för jobbet.
Lämplighet
LST-schemaläggning är mest användbar i system som huvudsakligen omfattar aperiodiska uppgifter, eftersom inga tidigare antaganden görs om händelsernas förekomsthastighet. Den största svagheten med LST är att den inte ser framåt och fungerar bara på det nuvarande systemtillståndet. Sålunda, under en kort överbelastning av systemresurser, kan LST vara suboptimal. Det kommer också att vara suboptimalt när det används med oavbrutna processer. Men precis som tidigaste deadline först och till skillnad från monoton schemaläggning kan denna algoritm användas för processoranvändning upp till 100 %.
Se även
- Tidigaste deadline första schemaläggning - en annan algoritm för dynamisk prioritetsschemaläggning, som garanterar optimal genomströmning.