Planowanie z najmniejszym zapasem czasu

Planowanie z najmniejszym zapasem czasu ( LST ) jest algorytmem dynamicznego planowania priorytetów . Przypisuje priorytety procesom na podstawie ich wolnego czasu . Czas zapasu to ilość czasu pozostałego po zadaniu, jeśli zadanie zostało rozpoczęte teraz. Algorytm ten jest również znany jako „ najpierw najmniej rozluźnienia” . Jego najczęstszym zastosowaniem są systemy wbudowane , zwłaszcza te z wieloma procesorami. Nakłada proste ograniczenie, że każdy proces na każdym dostępnym procesorze ma ten sam czas działania i że poszczególne procesy nie mieć powinowactwo do określonego procesora. To właśnie nadaje mu przydatność do systemów wbudowanych.

Czas wolny

Ten algorytm szeregowania najpierw wybiera te procesy, które mają najmniejszy „luz czasowy”. Slack time definiuje się jako różnicę czasową między ostatecznym terminem, czasem gotowości i czasem pracy.

Bardziej formalnie, czas przerwy dla procesu jest zdefiniowany jako: ${\ displaystyle s}$

${\ Displaystyle s = (dt) -c '}$

gdzie $jest$$terminem$ procesu, $.$ rzeczywistym od rozpoczęcia cyklu i pozostałym czasem

Aplikacje

W algorytmach planowania w czasie rzeczywistym dla zadań okresowych przed zaakceptowaniem sporadycznego zadania z twardym terminem potrzebny jest test akceptacyjny. Jednym z najprostszych testów akceptacyjnych dla pracy sporadycznej jest obliczenie ilości czasu wolnego między czasem zwolnienia a terminem wykonania pracy.

Stosowność

Szeregowanie LST jest najbardziej przydatne w systemach składających się głównie z zadań aperiodycznych, ponieważ nie przyjmuje się żadnych wcześniejszych założeń co do częstości występowania zdarzeń. Główną słabością LST jest to, że nie wybiega w przyszłość i działa tylko na bieżącym stanie systemu. Dlatego podczas krótkiego przeciążenia zasobów systemowych LST może być nieoptymalne. Będzie również nieoptymalny, gdy będzie używany z procesami nieprzerywalnymi. Jednak, podobnie jak najwcześniejszy ostateczny termin , w przeciwieństwie do planowania monotonicznego z szybkością , algorytm ten może być używany do wykorzystania procesora do 100%.

Zobacz też

• Najwcześniejszy ostateczny termin pierwszego planowania - inny algorytm dynamicznego planowania priorytetów, który gwarantuje optymalną przepustowość.