Systemy czasu rzeczywistego

Trzy składowe nazwy "system czasu
rzeczywistego"

•System
•Czas
•Rzeczywisty

Systemy czasu rzeczywistego

Zasadniczo rozróżniamy dwa typy systemów
czasu rzeczywistego:

systemy z twardymi ograniczeniami czasowymi
(hard real time)

systemy z miękkimi ograniczeniami czasowymi (soft
real time)

Systemy czasu rzeczywistego

W przypadku systemów czasu rzeczywistego system

musi zapewniać mechanizm, który sprawdza, czy każde

nowe zadanie dostarczone do systemu ma szansę

wykonać się w terminie nie zaburzając terminów

innych zadań oraz tak przydzielać procesor do zadań

już złożonych, aby zagwarantować dotrzymanie przez

te zadania ich terminów.

Systemy czasu rzeczywistego

Jest sprawą oczywistą, że aby poprawnie zaprojektować

system czasu rzeczywistego musimy znać metody

planowania zadań i gwarantowania terminów.

Te metody stanowią teoretyczną podbudowę i muszą

być znane i rozumiane przez każdą osobę która

będzie zajmować się projektowaniem takich systemów.

Tej tematyce jest poświęcony wykład.

Typy systemów sterujących

•Systemy monitorujące

•Systemy kontrolne bez sprzężenia zwrotnego

•Systemy kontrolne ze sprzężeniem zwrotnym

Kontroler RT

Kontrolowany

system

Środowisko

Input

Systemy monitorujące

Środowisko

System RT

Użytkownik

Display

Sensor

Sensor

Sensor

Systemy bez sprzężenia zwrotnego

System RT

Środowisko

Aktuator

Aktuator

Dane

użytkownika

Odczyty

sensorów

Systemy ze sprzężeniem zwrotnym

System RT

Środowisko

Aktuator

Sensor

Dane

użytkownika

Systemy ze sprzężeniem zwrotnym

Poprawny dobór parametrów czasowych jest kluczowy
dla

poprawnego działania systemu.

Przykład:

Ramię robota przesuwane z położenia 0 do położenia 1,
prędkość w punkcie 1 ma być równa 0.

Położenie x=1-exp(-t), t – czas

Prędkość v=exp(-t)

Systemy ze sprzężeniem zwrotnym

Położenie x=1-exp(-t), t – czas

Prędkość v=exp(-t)

Sensor odczytuje z okresem T położenie x ramienia i na
tej podstawie oblicza prędkość, z jaką należy przesuwać
ramię.

Faktycznie obliczane jest np. napięcie podawane na silnik
krokowy napędzający ramię robota, im większe napięcie
tym większa prędkość.

Czy dla każdego T można wysterować ramię robota?

Sprawdzić przykład w Excelu uwzględniając czas
hamowania.

Systemy ze sprzężeniem zwrotnym

Z drugiej strony zbyt częste próbkowanie nie ma sensu:

Przykład: nieustalone stany mechanicznych
przełączników

Częstość próbkowania sygnału może być określona z
wykorzystaniem tw. Nyquista.

Systemy ze sprzężeniem zwrotnym

W niektórych przypadkach nawet poprawne
zaprojektowanie systemu może nie zapewnić jego
kontroli.

Przykład: system używany niezgodnie z przeznaczeniem

Systemy ze sprzężeniem zwrotnym

System wizyjny pociągu

Systemy czasu rzeczywistego

Systemy czasu rzeczywistego, to systemy, przy

konstrukcji których poważnie bierze się pod
uwagę prawa Murphi’ego.

Wymagania:

•

Spełnienie wymagań czasowych

•

Projektowany do spełnienia funkcji przy
maksymalnym możliwym obciążeniu

•

Przewidywalność (co się stanie w momencie
przeciążenia)

•

Odporność na błędy softwarowe i hardwarowe

•

Modularna struktura

Systemy czasu rzeczywistego

Tak więc podstawową cechą systemów czasu
rzeczywistego jest przewidywalność.

Po złożeniu zadania i zaakceptowaniu go przez system
czasu rzeczywistego mamy gwarancję, że zadanie
zostanie wykonane w określonym terminie.

Faktycznie chcielibyśmy, aby systemy czasu
rzeczywistego były niezawodne nawet w
przypadku awarii sprzętu lub oprogramowania.

Spełnienie tego wymagania jest możliwe poprzez
zapewnienie nadmiarowego sprzętu uruchamianego w
przypadku awarii sprzętu podstawowego poprzez
składową systemu tzw. watchdoga.

Systemy czasu rzeczywistego

Tak więc podstawową cechą systemów czasu
rzeczywistego jest przewidywalność.

Po złożeniu zadania i zaakceptowaniu go przez system
czasu rzeczywistego mamy gwarancję, że zadanie
zostanie wykonane w określonym terminie.

Faktycznie chcielibyśmy, aby systemy czasu
rzeczywistego były niezawodne nawet w
przypadku awarii sprzętu lub oprogramowania.

Spełnienie tego wymagania jest możliwe poprzez
zapewnienie nadmiarowego sprzętu uruchamianego w
przypadku awarii sprzętu podstawowego poprzez
składową systemu tzw. watchdoga.

Systemy czasu rzeczywistego

Aby analizować planowalność dla określonego
zbioru zadań musimy najpierw przyjąć jakiś
model systemu czasu rzeczywistego.

Składowe systemu:

•zadania periodyczne
•zadania sporadyczne
•zadania aperiodyczne

Parametry czasowe zadań

Parametry czasowe zadań:

•czas złożenia (arrival time) a

•czas wykonania (computation time) C

•termin (deadline) d

•względny termin D

•czas startu (start time) s

•czas zakończenia (finishing time) f

•opóźnienie (lateness) L=f-d

•czas przekroczenia terminu (exceeding time)
E=max(0,L)

•zapas czasu w chwili złożenia (laxity, slack time) X=d-
a-C

Slack jest faktycznie funkcją czasu X=X(t) jeżeli
zadanie się wykonuje, to jego slack wynosi X(t)=d-t-
c(t), gdzie c(t) to ilość czasu CPU potrzebna do
zakończenia wykonywania zadania

Parametry czasowe zadań

Kolejnym parametrem czasowym jest rodzaj
rozkładu czasów między złożeniami:

•procesy periodyczne (faza procesu, okres procesu,
czas wykonania, terminy są ustalone)
•aperiodyczne a

i+1

>a

i

•sporadyczne a

i+1

>a

i

+T

Więzy kolejności wykonania

Więzy kolejności wykonania specyfikuje się poprzez
podanie skierowanego acyklicznego grafu, w którym
zadania są reprezentowane przez węzły, a relacje
kolejności przez łuki.

Graf kolejności narzuca relację częściowego
uporządkowania w zbiorze zadań.

Więzy kolejności wykonania

Przykład:
Celem systemu jest rozpoznanie rodzaju obiektów
poruszających się na taśmie w celu np uruchomienia
robota sortującego. Rozpoznanie opiera się na odczycie
z dwóch kamer.

Dostęp do zasobów

Aby zapewnić integralność danych, dostęp do zasobów
dzielonych musi następować na zasadzie wzajemnego
wykluczania.

Nieprawidłowy dostęp

Prawidłowy dostęp

Dostęp do zasobów

Standardowe semafory POSIX mają dwie wady:

•mogą prowadzić do zakleszczenia

•czas blokowania jest nieograniczony (odwrócenie
priorytetów)

żądanie zasobu
szarego

żądanie zasobu
czarnego

Dostęp do zasobów

Standardowe semafory POSIX mają dwie wady:

•mogą prowadzić do zakleszczenia

•czas blokowania jest nieograniczony (odwrócenie
priorytetów)

żądanie zasobu
szarego

Plan

Zdefiniowanie więzów czasowych, kolejności
wykonania i dostępu do zasobów to krok konieczny
przed skonstruowaniem planu wykonania.

Plan to odwzorowanie

takie, że



k

jest wykonywane

procesor jest bezczynny

Plan

Mamy dane trzy zbiory:
zbiór zadań J={J1,J2,J3....,Jn}
zbiór procesorów P={P1,P2,...Pm}
zbiór zasobów R={R1,R2,...Rs}
Ponadto mamy DAG określający więzy kolejności i
więzy czasowe.

Problem planowania to znalezienie takiego
przyporządkowania procesorów i zasobów zadaniom, aby
spełnić wszystkie ograniczenia czasowe.

Problem w ogólności jest NP-zupełny.

W pewnych warunkach, czasem o praktycznym znaczeniu
można problem przydziału rozwiązać w czasie
wielomianowym. Można rozpatrywać systemy
jednoprocesorowe, brak wywłaszczenia, ustalone priorytety
dla zadań itp.

Klasyfikacja algorytmów planujących

Plan jest dopuszczalny (feasible) jeżeli gwarantuje
dotrzymanie wszystkich terminów.

Zbiór zadań jest planowalny, jeżeli istnieje dla niego
dopuszczalny plan.

Algorytmy bez wywłaszczenia i z wywłaszczeniem:

Klasyfikacja algorytmów planujących

Off-line

On-line

Optymalne

Funkcje używane do mierzenia jakości algorytmu:
Średni czas odpowiedzi:
średnia (fi-ai)
Całkowity czas zakończenia:

max(fi)-

min(ai)
Maksymalne opóźnienie:
max(fi-di)
Maksymalna liczba spóźnionych zadań:

suma

miss(fi)

Heurystyczne

Zwykłe systemy operacyjne

Klasyczne algorytmy szeregujące nie są odpowiednie do
szeregowania zadań czasu rzeczywistego ponieważ nie
gwarantują dotrzymania terminu.

FIFO

niewywłaszczalny, dynamiczny, on-line
bardzo nieprzewidywalny czas wykonania, zależny od czasu przybycia

Zwykłe systemy operacyjne

Klasyczne algorytmy szeregujące nie są odpowiednie do
szeregowania zadań czasu rzeczywistego ponieważ nie
gwarantują dotrzymania terminu.

FIFO

niewywłaszczalny, dynamiczny, on-line
bardzo nieprzewidywalny czas wykonania, zależny od czasu przybycia

Zwykłe systemy operacyjne

Algorytm karuzelowy

Niebezpieczeństwa związane z algorytmem karuzelowym:
skończona długość slice'u czasowego.

Zwykłe systemy operacyjne

Planowanie na podstawie priorytetów:
Przyporządkowujemy priorytety do zadań.
Zadania o wyższym priorytecie mają
pierwszeństwo.

Jeśli priorytet proporcjonalny do odwrotności
czasu złożenia to metoda równoważna FIFO,
jeśli do odwrotności czasu wykonania to SJF.

Problemem jest głodzenie (długi czas
oczekiwania dla jobów o niskim priorytecie) -
ewentualnie można zwiększać priorytet w
zależności od czasu oczekiwania na przydział
procesora.

Zwykłe systemy operacyjne

Algorytmem minimalizującym średni czas
odpowiedzi jest algorytm Shortest Job First.

Przed wstawieniem jobu do kolejki planista
musi znać czas wykonania jobu, który jest
ustalony.

Zwykłe systemy operacyjne

SJF nie jest optymalny:

Zwykłe systemy operacyjne

Niepożądane cechy systemów operacyjnych:

•Skończona liczba priorytetów

•Zastosowanie semaforów może prowadzić do zakleszczenia i
zawieszenia systemu: jeśli zagnieżdżone sekcje krytyczne.

•W systemach czasu rzeczywistego pamięć powinna być
alokowana w sposób statyczny

•Zadania realizowane przez jądro systemu powinny mieć
ograniczony czas działania

Cechy sprzętowe, które są źródłem nieprzewidywalności.

•DMA

•Cache

•Przerwania

Anomalie szeregowania

Rozważmy planowanie tego zbioru na trzech
procesorach priorytety są od najwyższego 1 do
najniższego 9.

Dodajmy jeden więcej procesor.

Zmniejszmy czas wykonania każdego zadania o 1
na trzech procesorach.

Usuńmy wszystkie więzy na trzech procesorach.

Anomalie szeregowania

Dwa razy szybszy procesor dla układu w
którym jest dostęp do wspólnych zasobów:
J1 złożony w czasie 2, wykonuje się na wolnym
procesorze (2,2,2) gdzie pogrubienie oznacza
sekcje krytyczną, termin 9
J2 złożony w czasie 0 wykonuje się na wolnym
procesorze (2,12,2), termin 23.

Anomalie szeregowania

Operacja delay()

Przewidywalność

Czasy wykonania zadań są w zadanym przedziale
(Cmin,Cmax).

Przewidywalność wykonania planu:

Minimalny plan: plan wyprodukowany, gdy czasy
wszystkich zadań są minimalne.

Maksymalny plan: plan wyprodukowany, gdy czasy
wszystkich zadań są maksymalne.

Przewidywalność czasu startu

Przewidywalność czasu zakończenia

Przewidywalność

TWIERDZENIE

Wykonanie zbioru wywłaszczalnych zadań o
ustalonych czasach złożenia jest przewidywalne na
jednym procesorze, jeżeli zadania są planowane
algorytmem wykorzystującym priorytety.

Przewidywalność

Załóżmy, że mamy zbiór zadań o ustalonych priorytetach
{J

1

,J

2

,J

3

...J

n

}.

Wykonanie J

1

- zadania o najwyższym priorytecie -

jest przewidywalne. Wg dowolnego schematu
startuje zawsze w momencie złożenia i wykonuje się
w czasie należącym do przedziału (r

1

+C

1,min

, r

1

+C

1,max

).

Załóżmy, że wykonanie zadań J

1

,J

2

,...J

i-1

jest

przewidywalne.

Pokażemy, że wykonanie J

i

jest też przewidywalne tj.

S

min

(J

i

)<=S(J

i

)<=S

max

(J

i

) i f

min

(J

i

)<=f(J

i

)<=f

max

(J

i

).

Przewidywalność

Załóżmy, że czas startu nie jest przewidywalny:

Musi być albo S(J

i

)<S

min

(J

i

) albo S(J

i

)>S

max

(J

i

).

Weźmy przypadek S(J

i

)>S

max

(J

i

).

Czas startu nie może być wcześniejszy od czasu
złożenia czyli:
r

i

<=S

max

(J

i

).

Przewidywalność

Wg dowolnego planu J

i

nie może wystartować dopóki nie

wykonają się wszystkie zadania o priorytecie wyższym, niż J

i

i czasie startu wcześniejszym niż S(J

i

) tzn:

f(J

k

)< =S(J

i

) dla każdego k<i takiego, że r

k

<S(J

i

).

Dla maksymalnego planu mamy:

f

max

(J

k

)<=S

max

(J

i

) dla każdego k<i takiego, że

r

k

<S

max

(J

i

).

Z przewidywalności k<i i nieprzewidywalności Ji mamy:

f(J

k

)<=f

max

(J

k

)<=S

max

(J

i

)<S(J

i

) dla każdego k<i takiego,

że r

k

<S

max

(J

i

).

Przewidywalność

Jeżeli w czasie S

max

(J

i

) J

i

nie startuje,

to albo procesor pozostaje bezczynny,

albo wykonują się zadania o niższym priorytecie, co
jest sprzeczne z założeniami.

Przewidywalność

Weźmy przypadek S(J

i

)<S

min

(J

i

).

Czas startu nie może być wcześniejszy od czasu złożenia
czyli:

r

i

<=S

min

(J

i

).

Dla minimalnego planu mamy:

f

min

(J

k

)<=S

min

(J

i

) dla każdego k<i takiego, że

r

k

<S

min

(J

i

).

Wg dowolnego planu z przewidywalności k<i wynika,
że f(J

k

)>f

min

(J

k

) więc może istnieć takie k, że:

f

min

(J

k

)<=S

min

(J

i

)<f(J

k

) dla pewnego k<i takiego, że

r

k

<S

min

(J

i

).

Przewidywalność

Gdyby wg takiego planu S(J

i

)<S

min

(J

i

) to J

i

musiałoby

zajmować

czas procesora pomimo, że zadanie o wyższym
priorytecie nie

wykonało się, a to jest sprzeczne z założeniem o
planowaniu

wg priorytetów.

Przewidywalność

Z twierdzenia wynika, że możemy dobrze
kontrolować

przewidywalność wykonania gdy są ustalone
priorytety zadań,

zadania wykonują się w sposób wywłaszczalny na
jednym

procesorze i czasy złożenia są ustalone.

Wystarczy wtedy brać pod uwagę maksymalne czasy.