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.