Planowanie monotoniczne z szybkością

W informatyce planowanie monotoniczne z szybkością ( RMS ) to algorytm przydzielania priorytetów stosowany w systemach operacyjnych czasu rzeczywistego (RTOS) z klasą planowania z priorytetem statycznym. Priorytety statyczne są przypisywane zgodnie z czasem trwania cyklu zadania, więc krótszy czas trwania cyklu skutkuje wyższym priorytetem zadania.

Te systemy operacyjne mają na ogół funkcję wywłaszczania i mają deterministyczne gwarancje dotyczące czasu odpowiedzi. Analiza monotoniczna szybkości jest wykorzystywana w połączeniu z tymi systemami w celu zapewnienia gwarancji planowania dla konkretnego zastosowania.

Wstęp

Prosta wersja analizy monotonicznej szybkości zakłada, że ​​wątki mają następujące właściwości:

• Brak współdzielenia zasobów (procesy nie współdzielą zasobów, np . zasobu sprzętowego , kolejki ani żadnego rodzaju semafora blokującego lub nieblokującego ( zajęte-oczekiwanie ))
• Terminy deterministyczne są dokładnie równe okresom
• Priorytety statyczne (zadanie o najwyższym priorytecie statycznym, które można natychmiast uruchomić, wyprzedzi wszystkie inne zadania)
• Priorytety statyczne nadawane według konwencji monotonicznych stawki (zadania o krótszych okresach/terminach otrzymują wyższe priorytety)
• Czasy przełączania kontekstu i inne operacje na wątkach są bezpłatne i nie mają wpływu na model

Jest to model matematyczny zawierający obliczoną symulację okresów w systemie zamkniętym, w którym programy planujące działające w trybie okrężnym i z podziałem czasu nie spełniają w inny sposób potrzeb związanych z planowaniem. Planowanie monotoniczne z szybkością analizuje modelowanie przebiegu wszystkich wątków w systemie i określa, ile czasu potrzeba na spełnienie gwarancji dla zestawu danych wątków.

Optymalność

Przypisanie priorytetu z monotoniczną szybkością jest optymalne przy danych założeniach, co oznacza, że ​​jeśli dowolny algorytm planowania z priorytetem statycznym może dotrzymać wszystkich terminów, to algorytm z monotoniczną szybkością również może to zrobić. Algorytm harmonogramowania terminowo-monotonicznego jest również optymalny przy równych okresach i terminach, właściwie w tym przypadku algorytmy są identyczne; ponadto planowanie monotoniczne terminów jest optymalne, gdy terminy są krótsze niż okresy. Dla modelu zadań, w którym terminy mogą być dłuższe niż okresy, algorytm Audsleya wyposażony w dokładny test planowalności dla tego modelu znajduje optymalne przypisanie priorytetu.

Górne granice wykorzystania

Najmniej górna granica

Liu i Layland (1973) udowodnili, że dla zbioru n zadań okresowych o unikalnych okresach istnieje wykonalny harmonogram, który zawsze będzie dotrzymywał terminów, jeśli wykorzystanie procesora spadnie poniżej określonej granicy (w zależności od liczby zadań). Test planowalności dla RMS to:

${\ Displaystyle U = \ suma _ {i = 1} ^ {n} U_ {i }}=\suma _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({2}^{1/n}-1)}$

gdzie U jest współczynnikiem wykorzystania, C _i jest czasem obliczeń dla procesu i , T _i jest okresem zwolnienia (z ostatecznym terminem o jeden okres późniejszym) dla procesu i , n jest liczbą zaplanowanych procesów. Na przykład U ≤ 0,8284 dla dwóch procesów. Gdy liczba procesów dąży do nieskończoności , wyrażenie to będzie dążyć do:

${\ Displaystyle \ lim _ {n \rightarrow \infty} n ({\ sqrt [{n}] {2}} -1) = \ ln 2\około 0,693147\ldots }$

Dlatego szacunkowo szacuje się $, że RMS może$ wszystkich terminów, jeśli całkowite wykorzystanie procesora jest niż 70%. Pozostałe 30% procesora można przeznaczyć na zadania o niższym priorytecie, które nie są wykonywane w czasie rzeczywistym. W przypadku mniejszych wartości n lub w przypadkach, gdy U jest bliskie tego oszacowania, należy zastosować obliczoną granicę wykorzystania.

W praktyce dla $^$ powinien reprezentować najgorszy (tj. najdłuższy) czas obliczeń i ja $} displaystyle {T_{i}}}$${\ displaystyle {$ } powinien reprezentować najgorszy termin (tj. najkrótszy okres), w którym musi nastąpić całe przetwarzanie.

Górna granica dla harmonicznych zestawów zadań

$granicę$$tę$ można złagodzić do maksymalnej możliwej wartości 1,0, jeśli ${\ Displaystyle {T_ {m}} {>} T_ {i}}}$ , gdzie ${\ Displaystyle i = 1... m-1}$ ja , ${\ displaystyle {T_{m}}}$ jest całkowitą wielokrotnością ${\ displaystyle {T_ {i}}}$$który$ nie jest tylko wielokrotnością najkrótszego okresu tego okres każdego zadania jest wielokrotnością wszystkich krótszych okresów. Nazywa się to harmonicznym zestawem zadań. Przykładem może być: ${\ Displaystyle [{T_ {1}}, {T_ {2}}, {T_ {3}}, {T_ {4}}] = [1,3,6,12]}$ . Liu i Layland przyznają, że wyznaczenie harmonijnego zadania nie zawsze jest wykonalne i że w praktyce można zamiast tego zastosować inne środki łagodzące, takie jak buforowanie zadań o miękkich terminach realizacji lub stosowanie podejścia dynamicznego przydzielania priorytetów, aby umożliwić dla wyższej granicy.

Uogólnienie na łańcuchy harmoniczne

Kuo i Mok pokazali, że dla zestawu zadań składającego się z podzbiorów zadań harmonicznych K (znanych jako łańcuchy harmoniczne ) testem najmniejszej górnej granicy jest:

${\ Displaystyle U = \ suma _ {i = 1} ^ {n} {\ Frac {C_ {i}} {T_ { i}}}\równoważnik K({2}^{1/K}-1)}$

W przypadku, gdy żaden okres zadania nie jest całkowitą wielokrotnością drugiego, można uznać, że zestaw zadań składa się z n harmonicznych podzbiorów zadań o rozmiarze 1 i dlatego ${\ displaystyle {K} {=} {n}}$ , co czyni to uogólnienie równoważnym najmniejszej górnej granicy Liu i Laylanda. Kiedy $pełne$ górna granica wynosi 1,0, co oznacza

Granice stochastyczne

Wykazano, że losowo generowany system zadań okresowych zwykle dotrzyma wszystkich terminów, gdy wykorzystanie wynosi 88% lub mniej, jednak fakt ten zależy od znajomości dokładnych statystyk zadań (okresy, terminy), których nie można zagwarantować dla wszystkich zestawów zadań, oraz w niektórych przypadkach autorzy stwierdzili, że wykorzystanie osiągnęło najmniejszą górną granicę przedstawioną przez Liu i Laylanda.

Ograniczenie hiperboliczne

Granica hiperboliczna jest węższym warunkiem wystarczającym dla planowalności niż ten przedstawiony przez Liu i Laylanda:

${\ Displaystyle \ prod _ {i = 1} ^ {n} (U_ {i} +1) \ równoważnik 2$ }

gdzie U _i jest wykorzystaniem procesora dla każdego zadania. Jest to najściślejsza górna granica, jaką można znaleźć, stosując wyłącznie indywidualne współczynniki wykorzystania zadania.

Udostępnianie zasobów

W wielu praktycznych zastosowaniach zasoby są współdzielone, a niezmodyfikowany system RMS będzie narażony na ryzyko inwersji priorytetu i zakleszczenia . W praktyce rozwiązuje się to poprzez wyłączenie wywłaszczania lub dziedziczenie priorytetów . Alternatywne metody polegają na użyciu algorytmów bez blokad lub unikaniu współdzielenia muteksu/semafora między wątkami o różnych priorytetach. Ma to na celu przede wszystkim zapobieganie konfliktom zasobów.

Wyłączenie wywłaszczenia

• OS_ENTER_CRITICAL () i OS_EXIT_CRITICAL() blokujące przerwania procesora w jądrze czasu rzeczywistego, np. MicroC/OS-II
• Rodzina prymitywów splx() , która zagnieżdża blokowanie przerwań urządzenia (FreeBSD 5.x/6.x),

Dziedziczenie priorytetowe

• Podstawowy protokół dziedziczenia priorytetów promuje priorytet zadania, które przechowuje zasób, z priorytetem zadania, które żąda tego zasobu w momencie złożenia żądania. Po zwolnieniu zasobu przywracany jest pierwotny poziom priorytetu sprzed promocji. Ta metoda nie zapobiega zakleszczeniom i powoduje blokowanie łańcuchowe . Oznacza to, że jeśli zadanie o wysokim priorytecie uzyskuje dostęp do wielu współużytkowanych zasobów po kolei, może być konieczne oczekiwanie (blokowanie) na zadanie o niższym priorytecie dla każdego z zasobów. Łatka czasu rzeczywistego do jądra Linuksa zawiera implementację tej formuły.

• Protokół pułapu priorytetów ulepsza podstawowy protokół dziedziczenia priorytetów, przypisując każdemu semaforowi priorytet pułapu , który jest priorytetem najwyższego zadania, które kiedykolwiek będzie miało dostęp do tego semafora. Zadanie nie może przejąć sekcji krytycznej o niższym priorytecie, jeśli jego priorytet jest niższy niż priorytet pułapu dla tej sekcji. Metoda ta zapobiega zakleszczeniom i ogranicza czas blokowania maksymalnie do długości jednej sekcji krytycznej o niższym priorytecie. Ta metoda może być nieoptymalna, ponieważ może powodować niepotrzebne blokowanie. Protokół sufitu priorytetowego jest dostępny w pliku Jądro czasu rzeczywistego VxWorks . Jest również znany jako protokół o najwyższym priorytecie szafki (HLP).

Algorytmy dziedziczenia priorytetów można scharakteryzować za pomocą dwóch parametrów. Po pierwsze, czy dziedziczenie jest leniwe (tylko wtedy, gdy jest niezbędne) czy natychmiastowe (zwiększ priorytet przed konfliktem). Drugie to dziedziczenie optymistyczne (zwiększenie o kwotę minimalną) lub pesymistyczne (zwiększenie o kwotę większą niż minimalna):

	pesymistyczny	optymistyczny
natychmiastowy	OS_ENTER_CRITICAL() / OS_EXIT_CRITICAL()	splx() , najwyższa szafka
leniwy		protokół pułapu priorytetów, podstawowy protokół dziedziczenia priorytetów

W praktyce nie ma matematycznej różnicy (pod względem ograniczenia wykorzystania systemu Liu-Laylanda) pomiędzy algorytmami leniwymi i natychmiastowymi, a algorytmy natychmiastowe są bardziej wydajne w implementacji, dlatego są używane w większości praktycznych systemów.

Przykład użycia podstawowego dziedziczenia priorytetów jest związany z „ błądem resetowania Mars Pathfinder ”, który został naprawiony na Marsie poprzez zmianę flag tworzenia semafora, aby umożliwić dziedziczenie priorytetów.

Przerywanie procedur serwisowych

Wszystkie procedury obsługi przerwań (ISR), niezależnie od tego, czy mają ustalony ostateczny termin realizacji w czasie rzeczywistym, czy nie, powinny zostać uwzględnione w analizie RMS w celu określenia możliwości planowania w przypadkach, gdy ISR mają priorytety ponad wszystkimi zadaniami kontrolowanymi przez planistę. ISR może już mieć odpowiedni priorytet zgodnie z zasadami RMS, jeśli jego okres przetwarzania jest krótszy niż w przypadku najkrótszego procesu niezwiązanego z ISR. Jednakże ISR z okresem/terminem dłuższym niż jakikolwiek okres procesu inny niż ISR z krytycznym terminem ostatecznym powoduje naruszenie RMS i uniemożliwia wykorzystanie obliczonych granic do określenia możliwości planowania zestawu zadań.

Łagodzenie ISR o błędnie ustawionych priorytetach

Jedną z metod łagodzenia ISR o błędnej priorytetyzacji jest dostosowanie analizy poprzez skrócenie okresu ISR tak, aby był równy najkrótszemu okresowi, jeśli to możliwe. Narzucenie tego krótszego okresu skutkuje ustaleniem priorytetów zgodnym z RMS, ale także skutkuje wyższym współczynnikiem wykorzystania dla ISR, a tym samym dla całkowitego współczynnika wykorzystania, który może nadal znajdować się poniżej dopuszczalnej granicy, a zatem można udowodnić możliwość planowania. $wynoszący$ czas obliczeń i kropkę ${\ displaystyle {T_ {isr}}}$ , wynoszący 4 milisekundy. Jeśli najkrótsze zadanie kontrolowane przez program planujący ma okres $wówczas$ ISR miałby wyższy priorytet, ale niższą szybkość, co narusza RMS Aby udowodnić możliwość planowania, ustaw $oblicz$ współczynnik wykorzystania dla ISR (co również podnosi W tym przypadku $\ Displaystyle {U_ {isr}} {=} C_ {isr}} / {T_ {isr}}}$ zmieni się z ${\ displaystyle {0,5 ms} / {4 ms} {=} 0,125}$ do ${\ displaystyle {0,5 ms} / {1 ms} {=} 0,5}$ . Ten współczynnik wykorzystania zostanie wykorzystany podczas dodawania całkowitego współczynnika wykorzystania dla zestawu zadań i porównania z górną granicą w celu sprawdzenia możliwości planowania. Należy podkreślić, że dostosowanie okresu ISR ma charakter wyłącznie analityczny i że prawdziwy okres ISR pozostaje niezmieniony.

Inną metodą łagodzenia skutków ISR o błędnym priorytecie jest użycie ISR tylko do ustawienia nowego semafora/muteksu podczas przenoszenia czasochłonnego przetwarzania do nowego procesu, któremu przy użyciu RMS nadano odpowiedni priorytet i który będzie blokował nowy semafor/muteks. Przy określaniu możliwości planowania, margines wykorzystania procesora ze względu na aktywność ISR powinien zostać odjęty od najmniejszej górnej granicy. ISR o znikomym wykorzystaniu można zignorować.

Przykłady

Przykład 1

Proces	Czas egzekucji	Okres
P1	1	8
P2	2	5
P3	2	10

W systemie RMS najwyższy współczynnik (tj. najkrótszy okres) ma P2, a zatem miałby najwyższy priorytet, po którym następuje P1 i na końcu P3.

Najmniejsza górna granica

Wykorzystanie będzie następujące: ${\ Displaystyle {\ Frac {1} {8}} + {\ Frac {2} {5}} + {\ Frac {2} {10}} =0,725}$ .

Warunek wystarczający dla procesów, po spełnieniu którego możemy stwierdzić, że system jest planowalny, to: ${\ displaystyle 3 \,}$

$${\ Displaystyle {U_ {lub}} = 3 (2 ^ {\ Frac {1 }{3}}-1)=0,77976>0,693\ldots (0,693{\text{ jest wykorzystywane przez RMS przez }}n=\infty \ldots )}$$

Ponieważ i $.$ stan poniżej najmniejszej górnej granicy jest warunkiem wystarczającym, gwarantuje się, że system będzie

Przykład 2

Proces	Czas egzekucji	Okres
P1	3	16
P2	2	5
P3	2	10

W systemie RMS najwyższy współczynnik (tj. najkrótszy okres) ma P2, a zatem miałby najwyższy priorytet, po którym następuje P3 i na końcu P1.

Najmniejsza górna granica

Korzystając z ograniczenia Liu i Laylanda, jak w przykładzie 1, warunkiem wystarczającym dla procesów, zgodnie z którym możemy stwierdzić, że zestaw zadań można zaplanować, pozostaje: 3 $\ displaystyle 3 \, }$

$${\ Displaystyle {U_ {lub}} = 3 (2 ^ {\ Frac {1} {3}} -1) = 0,77976}$$

Całkowite wykorzystanie będzie wynosić: ${\ Displaystyle {\ Frac {3} {16}} + {\ Frac {2} {5}} + {\ Frac {2} }=0,7875}$ .

Ponieważ $stwierdzono, że$ nie ma gwarancji system będzie możliwy do planowania przez połączenie Liu i Layland

Więzy hiperboliczne

Używając ściślejszej granicy hiperbolicznej w następujący sposób:

${\ Displaystyle \ prod _ {i = 1} ^ {n }(U_{i}+1)=({\frac {3}{16}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10} }+1)=1,995\równ. 2}$

okaże się, że zestaw zadań można zaplanować.

Przykład 3

Proces	Czas egzekucji	Okres
P1	7	32
P2	2	5
P3	2	10

W systemie RMS najwyższy współczynnik (tj. najkrótszy okres) ma P2, a zatem miałby najwyższy priorytet, po którym następuje P3 i na końcu P1.

Najmniejsza górna granica

Korzystając z ograniczenia Liu i Laylanda, jak w przykładzie 1, warunkiem wystarczającym dla procesów, zgodnie z którym możemy stwierdzić, że zestaw zadań można zaplanować, pozostaje: 3 $\ displaystyle 3 \, }$

$${\ Displaystyle {U_ {lub}} = 3 (2 ^ {\ Frac {1} {3}} -1) = 0,77976}$$

Całkowite wykorzystanie będzie wynosić: ${\ Displaystyle {\ Frac {7} }=0,81875}$ .

Ponieważ $ustalono, że$ nie ma gwarancji system będzie możliwy do harmonogramowania przez połączenie Liu i Layland

Więzy hiperboliczne

Używając ściślejszej granicy hiperbolicznej w następujący sposób:

${\ Displaystyle \ prod _ {i = 1} ^ {n} ( U_{i}+1)=({\frac {7}{32}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+ 1)=2,0475}$

Ponieważ określono $, że$ nie ma gwarancji będzie możliwy do zaplanowania w oparciu o granicę hiperboliczną.

Analiza zestawu zadań harmonicznych

Ponieważ $.$ uznać za Zadanie 1 tworzy własny podzbiór zadań harmonicznych. Dlatego liczba podzbiorów zadań harmonicznych K wynosi 2 .

$${\ Displaystyle {U_ {lub, harmoniczna}} = K (2 ^ { \frac {1}{K}}-1)=2(2^{\frac {1}{2}}-1)=0,828}$$

$obliczony$ powyżej całkowity współczynnik wykorzystania (0,81875), ponieważ system można zaplanować.

Zobacz też

• Harmonogramowanie terminowo-monotoniczne
• Deos , system operacyjny czasu rzeczywistego z podziałem czasu i przestrzeni, zawierający działający harmonogram monotoniczny szybkości.
• Dynamiczne planowanie priorytetów
• Najwcześniejszy termin pierwszego harmonogramu
• RTEMS , system operacyjny czasu rzeczywistego o otwartym kodzie źródłowym, zawierający działający harmonogram Monotonic Rate.
• Planowanie (obliczenia)

Dalsza lektura

• Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications , Nowy Jork, Nowy Jork: Springer .
•   Alan Burns i Andy Wellings (2009), Systemy czasu rzeczywistego i języki programowania (wyd. 4), Addison-Wesley, ISBN 978-0-321-41745-9
• Liu, Jane WS (2000), Systemy czasu rzeczywistego , Upper Saddle River, NJ: Prentice Hall , rozdział 6.
• Józef, M.; Pandya, P. (1986), „Znajdowanie czasów odpowiedzi w systemach czasu rzeczywistego”, BCS Computer Journal , 29 (5): 390–395, doi : 10.1093/comjnl/29.5.390 .
•   Sha, Lui; Goodenough, John B. (kwiecień 1990), „Teoria planowania w czasie rzeczywistym i Ada”, IEEE Computer , 23 (4): 53–62, doi : 10.1109/2.55469 , S2CID 12647942

Linki zewnętrzne

• Błąd Mars Pathfinder od Research @ Microsoft
• Co naprawdę wydarzyło się na łaziku marsjalnym Pathfinder autorstwa Mike’a Jonesa z The Risks Digest, tom. 19, wydanie 49
• [1] Rzeczywista przyczyna błędu Mars Pathfinder, podana przez tych, którzy faktycznie się nim zajęli, a nie przez osobę, której firma, a tym samym wartość akcji, zależała od opisu problemu, lub przez osobę, która słyszała, jak ktoś mówił o problemie.