Zagadnienia do przedmiotu: Systemy czasu rzeczywistego AiR sem5 1st

1. Definicja sytemu czasu rzeczywistego, wymagania funkcjonalne Syst. Cz. Rz.a

to urządzenie techniczne, którego wynik i efekt działania jest zależny od chwili wypracowania tego wyniku. Istnieje wiele różnych definicji naukowych takiego systemu. Ich wspólną cechą jest zwrócenie uwagi na równoległość w czasie zmian w środowisku oraz obliczeń realizowanych na podstawie stanu środowiska. Z tego wyścigu dwóch stanów: zewnętrznego i wewnętrznego, wynikają kryteria ograniczające czas wypracowywania wyniku.

Systemy czasu rzeczywistego najczęściej buduje się w oparciu o komputery, jednak nie jest to konieczne – można tym pojęciem określić np. regulator pneumatyczny.

wymagania

1. RTOS musi być wielowątkowy i wywłaszczalny

2. w momencie gdy OS nie jest oparty na dedlinach, musi istnieć pojęcie priorytetu wątku.

3. OS musi wspierać mechanizm przewidywalnej synchronizacji wątków

4. musi istnieć dziedziczenie priorytetów

5. zachowanie OS powinno być znane

Należy dokładnie oszacować parametry czasowe tj. :

1. opóźnienie przerwań (czas od wygenerowania przerwania do rozpoczęcia wykonywania zadania) – musi być przewidywalne. Wartość ta zależy od liczb jednocześnie oczekujących przerwań.

2. dla każdego przerwania systemowego – maksymalny czas, jaki zajmujemy. Czas powinien być przewidywalny i niezależny od liczby obiektów w systemie.

3. maksymalny czas na jaki OS i sterowniki maskują przerwania.

1. Systemy operacyjne Cz.Rz., przykłady.

przykłady

1. sekwencja awaryjnego wyłączania silnika rakietowego

2. system zbierania danych (np. informacji o opadzie deszczu)

3. system kontrolny ABS w samochodzie

4. system dostarczania paliwa do silników samolotu

5. odtwarzanie plików mpeg

6. kontroler serwomechanizmu

7. systemy podtrzymywania życia w szpitalu

1. Stany procesów, graf stanu procesów.

Graf stanów procesów

1. Biblioteka POSIX: tworzenie procesów. Akcje podejmowane przy kończeniu procesów.

POSIX to odpowiedź na próby standaryzacji różnych odmian systemu operacyjnego Unix. Prace nad tym standardem rozpoczęto ok. roku 1985, a kierowało nimi stowarzyszenie IEEE. Dlatego POSIX znany jest również pod nazwą IEEE 1003. Nad dalszym rozwojem standardu sprawuje pieczę The Open Group we współpracy z IEEE i firmami komputerowymi takimi jak: IBM, Sun Microsystems, Hewlett-Packard, NEC Corporation, Fujitsu, Hitachi. Kolejne edycje standardu wydawane przez "The Open Group" noszą nazwy Single UNIX Specification, Version x, gdzie x to kolejny numer wersji. Aktualna wersja jest trzecią a pojawiła się w roku 2001. Od roku 2003 jest to norma międzynarodowa ISO/IEC 9945:2003.

Nazwę "POSIX" zaproponował Richard Stallman.

POSIX standaryzuje:

• interfejs programistyczny (API);

• interfejs użytkownika, np. polecenia systemowe takie jak awk, echo, ed;

• właściwości powłoki systemowej.

POSIX dotyczy przede wszystkim systemów klasy UNIX. Implementacje POSIX zawarte zostały w systemach takich jak Mac OS X 10.5, QNX, BeOS i AtheOS / Syllable. GNU/Linux oraz FreeBSDsą w znacznym stopniu lub często nawet w pełni zgodne z tym standardem. Niektóre z dystrybucji Linuksa, np. Linux-FT^[1] czy Unifix Linux^[2], przeszły pomyślnie procedury testowe i uzyskały świadectwo zgodności. Dla użytkowników Microsoft Windows dostępne są środowiska Cygwin i Interix, które umożliwiają w tym systemie korzystanie z POSIX-owego interfejsu programistycznego.

1. Metody komunikacji międzyprocesowej.

Procesy mogą używać różnych sposobów komunikacji,
a najpowszechniejsze z nich to:

• pliki i blokady – najprostsza i najstarsza forma IPC

• sygnały (ang. signals) – w niektórych systemach (jak np. DOS) znane jako przerwania programowe

• semafory (ang. semaphores)

• łącza nienazwane (ang. pipes) – znane też jako łącza komunikacyjne

• łącza nazwane (ang. named pipes) – znane też jako nazwane łącza komunikacyjne

• kolejki komunikatów (ang. message queues)

• pamięć dzieloną (ang. shared memory) – znane też jako segmenty pamięci dzielonej (ang. shared memory segments)

• gniazda dziedziny Uniksa (ang. Unix domain sockets)

1. Semafory, pojęcie oraz ochrona sekcji krytycznej.

Semafory

Semafor jest zmienną przyjmującą (w zależności od rodzaju) wartości całkowite nieujemne lub wartości logiczne. Na semaforze definiujemy dokładnie dwie operacje.

 Semafor ze zbiorem oczekującym:

Czekaj(S) . jeżeli S>0 to S:=S-1 w przeciwnym razie wstrzymaj wykonywanie procesu (proces nazywamy wstrzymanym przez semafor).

Sygnalizuj(S) . jeśli s_ jakie_ procesy wstrzymane przez ten semafor to wznów jeden z nich, w przeciwnym razie S:=S+1

Sekcja krytyczna to ciąg operacji wykonywanych na pewnym zasobie (zwykle pamięci), który

musi być wykonywany w trybie wyłącznym przez tylko jeden z potencjalnie wielu procesów.

Warunki poprawnego rozwiązania sekcji krytycznej:

a) W sekcji krytycznej może być tylko jeden proces, to znaczy instrukcje z sekcji krytycznej

nie mogą być przeplatane.

b) Nie można czynić żadnych założeń, co do względnych szybkości wykonywania

procesów.

c) Proces nie może się zatrzymać w sekcji krytycznej.

d) Zatrzymanie procesu w sekcji lokalnej nie może blokować innym procesom wejścia do

sekcji krytycznej.

e) Każdy proces musi w końcu wejść do sekcji krytycznej.

1. Szeregowanie w Syst. Cz. Rz., algorytmy Rate Monotonic lub Deadline Monotonic i Earliest Deadline First.

Planowanie, zwane również szeregowaniem (szczególnie w kontekście systemów czasu rzeczywistego), oznacza wyznaczenie procesu, który powinien następnie zostać wykonywany na procesorze.

Rate Monotonic (RM) jest algorytmem, który przydziela priorytety do zadań w zależności od ich czasu, w którym trzeba je wykonać, inaczej mówiąc zadania z krótszym okresem mają większy priorytet. Ponieważ okresy mają wartość stałą, priorytety są przydzielane do zadań przed rozpoczęciem ich wykonywania i nie zmieniają się w trakcie działania algorytmu. Wykonywanie obecnego zadania może zostać wstrzymane na rzecz nowego zadania z krótszym okresem. RM gwarantuje, że dany zbiór zadań periodycznych G jest zawsze planowalny, jeżeli współczynnik wykorzystania procesora nie przekracza wartości 0,69.

Earliest Deadline First (EDF) jest algorytmem dynamicznego planowania, który przydziela priorytety w zależności od absolutnego deadline’u zadań. Inaczej mówiąc, zadania z bliższym deadlinem posiadają wyższy priorytet.

EDF dynamicznie przydziela priorytety. Obecnie wykonywane zadanie zostaje wstrzymane, jeżeli jakaś instancja zadania periodycznego z bliższym deadlinem staje się aktywna.

Zauważmy, że EDF nie zakłada niczego odnośnie okresowości zadania a więc może być wykorzystywany również do planowania zadań aperiodycznych.

Zbiór periodycznych zadań jest planowalny przez EDF wtedy i tylko wtedy, gdy:

Przykład dla działania RM (a) i EDF (b):

Współczynnik wykorzystania procesora dla zadań periodycznych przedstawionych w przykładzie wynosi:

To oznacza, że 97% czasu procesora jest wykorzystywane na wykonywanie zadań periodycznych, CPU jest bezczynne przez 3% czasu. Ponieważ U > ln 2, planowalność tych zadań nie może być zagwarantowana przez RM, a jest planowalna przez EDF.

Earliest Deadline First – optymalny algorytm szeregowania zadań wykorzystywany w systemach czasu rzeczywistego, wykorzystujący kolejkę priorytetową do przechowywania zadań i przydzielania ich do wolnych procesów. Za każdym razem, kiedy w systemie pojawi się niezajęty proces (np. jeden z procesów ukończy swoje zadanie), z kolejki priorytetowej zostanie pobrane zadanie o najwyższym priorytecie (najbliższe do swojego deadlinu), a następnie przekazane do wykonania dla procesu[1].

Optymalność algorytmu polega na tym, że jeśli EDF nie może uszeregować danego zbioru zadań to żaden algorytm z dynamicznym przydziałem priorytetów nie znajdzie wykonalnego szeregowania oraz w sytuacji gdy każdy algorytm z dynamicznym przydziałem priorytetów potrafi uszeregować dany zbiór zadań to również EDF potrafi. Zbiór zadań jest szeregowalny za pomocą algorytmu EDF wtedy i tylko wtedy, gdy stopień wykorzystania procesora dla danego zbioru zadań wynosi: U < 1. algorytmu EDF wtedy i tylko wtedy, gdy stopień wykorzystania procesora dla danego zbioru zadań wynosi: U < 1.

1. Priorytety oraz problem inwersji priorytetów.

Priorytety :

• Planowanie priorytetowe – wybierany jest proces o najwyższym priorytecie. W tej metodzie występuje problem nieskończonego blokowania (procesu o niskim priorytecie przez procesy o wysokim priorytecie). Stosuje się tu postarzanie procesów, polegające na powolnym podnoszeniu priorytetu procesów zbyt długo oczekujących.

• Planowanie wielopoziomowe – zadania przypisywane są do kolejek szeregowania w zależności od parametru opisującego każde z zadań jakim w praktyce zwykle jest priorytet. Zadania w danej kolejce są następnie szeregowane określonym algorytmem takim jak na przykład FIFO lub round-robin i kierowane do wykonania. Jeśli w danej kolejce nie ma zadań gotowych do wykonywania, planista ponownie dokonuje analizy kolejki ale dla zadań o niższym priorytecie. Zwykle możliwa jest zmiana kolejki w której szeregowane jest zadanie, poprzez zmianę priorytetu zadania.

• Planowanie wieloprocesorowe – na jednakowe lub różne procesory a także całe komputery;

• Planowanie z uwzględnieniem mechanizmów synchronizacji zadań – ze względu na powiązanie zadań różnymi zasobami a nie tylko procesorem, konieczne (w celu uniknięcia problemu zakleszczeń) jest uwzględnienie aspektu dostępu do tych innych zasobów przez szeregowane zadania

Problem inwersji priorytetów :

Istnieje wiele sytuacji, w których inwersja priorytetów może sprawić spore problemy. Jeśli zadanie o wysokim priorytecie ulega zagłodzeniu, może doprowadzić do nieprawidłowego działania systemu lub wywoływać działania zapobiegające uszkodzeniu, takie jak watchdog restartujący cały system. Klasycznym przykładem problemów spowodowanych inwersją priorytetów w systemie czasu rzeczywistego są kłopoty z działaniem lądownika sondy kosmicznej Mars Pathfinder. Inwersja priorytetów może również ograniczyć wydajność systemu. Niektóre zadania mają niski priorytet dlatego, że nie jest dla nich ważna szybka realizacja (np. nie wymagają interakcji użytkownika lub jest to seria zadań w przetwarzaniu wsadowym). Odwrotnie jest natomiast z zadaniami o wysokim priorytecie – te z kolei często wymagają jakiejś interakcji lub pełnią ważną rolę gwarantującą poprawne działanie aktualnie wykorzystywanych elementów systemu. Inwersja priorytetów powoduje to, że wywoływanie zadań o niskim priorytecie blokuje zadania z wysokim priorytetem, co może doprowadzić do utraty stabilności i zawieszeń systemu.

1. Parametry opisu procesów: T-okres wykonywania, D- względny czas zakończenia ,C- czas wykonania w najgorszym przypadku .

Parametry opisu procesów

Każdy proces może być opisany przez następujące parametry:

Okres p (period) tzn. czas pomiędzy kolejnymi zdarzeniami wymagającymi obsługi przez proces termin

d (deadline) w którym zdarzenie musi być obsłużone (od momentu zajścia zdarzenia)

czas t (time) potrzebny procesowi na obsługę zdarzenia

1. Analiza możliwości realizacji szeregowania.

2. Problemy w implementacji Syst. Cz. Rz. w strukturach rozproszonych. Podstawowe właściwości protokołów typu Ethernet, DeviceNet oraz ControlNet.

3. Oprogramowanie narzędziowe do aplikacji Cz. Rz. typu State Flow Chart , przykłady.

4. Przykład realizacji układów regulacji jako zadań typu Cz. Rz.. Implementacja regulatorów.

10.01.2015