Zagadnienia do przedmiotu: Systemy czasu rzeczywistego AiR sem5 1st

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

- Definicja systemu czasu rzeczywistego: System komputerowy jest systemem czasu rzeczywistego jeżeli w sposób jawny zarządza zasobami tak, by spełnić wymagania ograniczeń czasowych;

System, którego przestrzeganie zależności czasowych wpływa ściśle na jego funkcjonalność, wydajność i niezawodność.

Wymagania

- Podstawowym wymaganiem dla systemu operacyjnego czasu rzeczywistego jest określenie najgorszego (najdłuższego) czasu, po jakim urządzenie komputerowe wypracuje odpowiedź po wystąpieniu zdarzenia. Ze względu na to kryterium, systemy operacyjne czasu rzeczywistego dzielą się na dwa rodzaje:

• Twarde - takie, dla których znany jest najgorszy (najdłuższy) czas odpowiedzi, oraz wiadomo jest, że nie zostanie on przekroczony.

• Miękkie - takie, które starają się odpowiedzieć najszybciej jak to możliwe, ale nie wiadomo jest, jaki może być najgorszy czas odpowiedzi.

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.

Rozszerzenie POSIX 1003.1b jest dość powszechnie implementowane, najczęściej przez systemy operacyjne wywodzące się z rodziny UNIX. Jeśli chodzi o inne (jak np. Windows), to bywa różnie. Standard 1003.1b wprowadza wiele ciekawych rzeczy, do których zaliczają się między innymi:

• obsługa sygnałów czasu rzeczywistego

• zegary (ang. timers)

• szeregowanie w oparciu o priorytety

• różne mechanizmy synchronizacyjne jak np. semafory, kolejki itp.

• funkcje blokujące usuwanie stron z pamięci (mechanizm pamięci wirtualnej)

• mechanizmy przekazywania komunikatów

• asynchroniczne operacje wejścia – wyjścia oraz szeregowaniu ich w oparciu o priorytety

Dalsze rozszerzenia standardu POSIX, wprowadzają dodatkowo funkcje wspierające wielowątkowość w ramach jednego procesu.

Tworzenie i kończenie procesów –

///coś mam w zeszycie, jakies instrukcje, może o to chodzi.. ////////////

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.

Sekcja krytyczna (angielskie critical section), fragment kodu, który powinien być wykonany z zachowaniem niepodzielności, tj. jednoetapowo, bez przerwań. Brak ochrony wykonywania sekcji krytycznej może powodować nieokreślone skutki w działaniu oprogramowania. Obsługę sekcji krytycznej organizuje się w procesach np. za pomocą semaforów, które z kolei są wspomagane sprzętowo, np. przez wyłączanie przerwań na czas wykonywania sekcji krytycznej albo za pomocą specjalnych, niepodzielnie wykonywanych rozkazów: zamień (swap) lub testuj i ustaw (test-and-set). Pierwszy z nich zamienia zawartość dwóch komórek pamięci, drugi bada stan komórki i określa jej nową wartość.

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.

Rate Monotonic jest optymalny z pośród wszystkich algorytmów rozwiązujących zadania periodyczne o stałym priorytecie, inaczej mówiąc jeżeli inny algorytm planowania zadań o stałym priorytecie rozwiązuje zbiór zadań G, to Rate Monotonic również go rozwiązuje.

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

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.

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.

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

- Ethernet (właściwości):

Właściwości ethernetu cechuje norma Ieee 802.3 (USA) i Iso8802.3 (norma europejska), normy te określają prędkość transmisji, rodzaje kabli, maksymalny zasięg i inne właściwości.
Każda karta ma swój unikalny adres fizyczny (sprzętowy).

Rozróżniamy następujące odmiany ethernetu:

• ethernet 10 Mbps

• fast ethernet 100 Mbps

• gigabit ethernet 1 Gbps

Standardy te różnią się maksymalną prędkością transmisji oraz maksymalnym zasięgiem sieci.

Ethernet charakteryzuje się niską ceną okablowania i sprzętu, łatwością instalacji i obsługi.

W sieciach ethernet wszystkie komputery podłączone są do wspólnego nośnika transmisji.

- DeviceNet (właściwości):

• Protokół ten używany jest głównie w aplikacjach przemysłowych w automatyce przemysłowej

• Cechy protokołu komunikacyjnego:

- komunikacja jeden do jednego (jeden do wielu), gdzie każdy z produktów DeviceNet może utworzyć lub pobrać wiadomość

- operacje nadrzędne i podrzędne ustawiane jako podopcje w komunikacji jeden do jednego

- urządzenia DeviceNet mogą pracować jako klient, jako serwer lub jako klient-serwer

- zapewnienie adresacji do 64 węzłów(MAC IDs - Media Access Control Identifiers)

- każdy z węzłów ma unikatowy numer portu I/O (16 lub 32 bitowy)

- ControlNet (właściwości):

ControlNet jest szeregową siecią czasu rzeczywistego, która umożliwia

- szybką transmisję danych typu: dane o włączeniu/wyłączeniu, dane komunikacyjne, dane aktualizacyjne dotyczące programowania i konfiguracji, wiadomości typu „każdy z każdym” w obu kierunkach, wykorzystując pojedynczy kanał komunikacyjny.

- ControlNet pozwala wszystkim węzłom w sieci na jednoczesny dostęp do tych samych danych pobieranych z tego samego źródła.

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

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