Więcej o firmie ELESOFTROM

Firma ELESOFTROM specjalizuje się w wykonywaniu i naprawianiu oprogramowania dla sterowników mikroprocesorowych.

Posiadamy ponad 10-letnie doświadczenie w tej dziedzinie.

W realizowanych projektach stawiamy na niezawodność i wydajność programów.

Naprawa oprogramowania

Oprogramowanie na zamówienie


Strona główna

Pełna oferta

Doświadczenie

O firmie

Kontakt


DioneOS - RTOS dla urządzeń embedded

Firma ELESOFTROM opracowała system RTOS dla procesorów ARM Cortex-M3 oraz msp430.

System jest zoptymalizowany pod względem wydajności, dzięki czemu uzyskano krótki czas przełączania pomiędzy wątkami.
System dostarcza elementy (np. semafory, mutexy, timery, kolejki itp.) niezbędne do tworzenia wielowątkowego firmware'u.

Wersja dla Cortexa została całkowicie przetestowana przy pomocy środowiska do automatycznego testowania.

Przeczytaj więcej:

Strona o systemie DioneOS

Niezawodność

Wydajność

Dokumentacja DioneOSa

Prezentacje n.t. DioneOS


^ Blog index    << Przerwania w ARM Cortex-M3    >> Jak zbudować projekt C++ Buildera pod Eclipse (wersja uproszczona)

Maszyny stanowe - opis zachowania systemu

2013-11-27    dr inż. Piotr Romaniuk

Spis treści

Opis zachowania systemu
Maszyna stanowa
Naiwna implementacja zachowania (tak nie robić!)
Jak stworzyć model zachowania w postaci maszyny stanowej
Prosta implementacja maszyny stanowej
Maszyna stanowa - lepsza implementacja
Więcej maszyn stanowych
Definiowanie róźnych typów maszyn
Oddzielenie definicji od wykorzystania (framework, biblioteka)
Manager maszyn stanowych i maszyna stanowa jako aktywny obiekt
Generatory kodu i translatory
Linki

Opis zachowania systemu

Rozważmy system, którego zachowanie zależy od tego co działo się z nim w przeszłości - można powiedzieć, że ma on jakąś pamięć. W jego historii jego stan zmienia się pod wpływem zdarzeń wejściowych, a w każdym stanie może on na te same wartości na wejściu odpowiadać w różny sposób. Nie wprost przemycone zostało tu, że rozważania dotyczą systemów z czasem dyskretnym. W przypadku urządzeń embedded często powstaje potrzeba zaprogramowania tego typu zachowania, np. przy implementacji protokołów komunikacyjnych, czy software'owych sterowników urządzeń wymagających zachowania sekwencji operacji podczas interakcji z hardwarem.

Do opisania, a także do późniejszej implementacji, takiego systemu nadaje się maszyna stanowa. Jest ona zazwyczaj przedstawiana w postaci diagramu, co ma niebagatelne znaczenie dla czytelności opisu i szybkości przekazania informacji o zachowaniu układu. Jasny, zrozumiały i jednoznaczny opis pozwala uniknąć nieporozumień przy przejściu od projektu do implemetacji. Po napisaniu kodu, w trakcie testowania łatwo jest również zweryfikować czy jest on zgodny z modelem.

Istnieje wiele standardów ilustrowania maszyn stanowych, różnią się one zazwyczaj formą graficzną. Jednym z najbardziej rozpowszechnionych jest UML (Unified Modeling Language).

Maszyna stanowa

Zacznijmy od modelu maszyny stanowej (a w zasadzie metamodelu, bo opisuje on model). Maszynę stanową można przedstawić jako kompozycję następujących elementów:
- stany [states],
- przejścia [transitions],
- wyzwalacze [triggers],
- warunki [conditions],
- akcje [actions],


Przykład diagramu maszyny stanowej

Przyjmijmy, że maszyna stanowa może być w danym momencie tylko w jednym stanie. Stany są ze sobą połączone przejściami (strzałki na powyższym diagramie), symbolizującymi możliwość zmiany stanu (stan - zaokrąglone prostokąty) z chwilą pojawienia się odpowiedniego zdarzenia (np. sig_timer). Podczas przejścia może być wykonana akcja (np. blink() ).

Z każdym przejściem związane są:
- stan bieżący [source state],
- stan następny [target state],
- warunek przejścia (musi być spełniony aby przejście było dozwolone),
- wyzwalacz - rodzaj zdarzenia, które prowadzi do zmiany stanu (np. sig_enable na powyższym rysunku).
- akcja - operacja/funkcja wykonywana podczas przejścia (np. blink() na powyższym rysunku).
Zmiana stanu dokonuje się jedynie w momencie pojawienia się zdarzenia.

Naiwna implementacja zachowania (tak nie robić!)
Początkujący programiści nie są świadomi jak wiele wynika z zastosowania maszyn stanowych i implementują zachowanie poprzez zestaw zmiennych i flag, które łącznie określają stan systemu. W wielu miejscach osobno je modyfikują i testują przez warunki if/while. Ignorowana jest również ochrona dostępu do takich zmiennych, co sprawia, że ich modyfikacje i testy nie są atomowe - są krótkie okresy czasu kiedy system ma niespójne dane. Jeśli w takim momencie wywołane będzie przerwanie, które z nich ma korzystać, to o kłopoty jest już łatwo, szczególnie, że problemy występują jakby przypadkowo, niepowtarzalnie - zależy to od wstrzelenia się asynchronicznego przerwania w to miejsce. Tego typu błędy są niezwykle trudne do znalezienia.
Gdy podczas prób okazuje się, że coś nie działa, dodawana jest nowa flaga do sygnalizacji jakiejś odmiany/wersji. Zazwyczaj nie jest też właściwie odróżniany stan od zdarzenia, co prowadzi do strasznego bałaganu a w konsekwencji kodu, który się tylko wykonuje zamiast działać.

Jak stworzyć model zachowania w postaci maszyny stanowej
Aby stworzyć właściwy model maszyny stanowej należy zacząć od wypisania zdarzeń oraz przewidywanych stanów systemu. Potem należy narysować diagram stanów, łącząc stany przejściami, na których należy umieścić zdarzenia wyzwalające i akcje. Może się okazać, że taki diagram jest niewystarczający, trzeba go będzie uzupełnić i sprawdzić, wykonując m.in.:

  • jeśli nie można określić zdarzenia wyzwalającego przejście do stanu i odbywa się ono niejako samoczynnie, to taki stan może być zapewne połączony z poprzednim,
  • jeśli przejście z jednego stanu do drugiego zawiera pewną sekwencję operacji, to może się okazać, że są niezbędne jakieś stany pośrednie, których się jeszcze nie zidentyfikowało,
  • jeśli potrzebne jest odczekanie jakiegoś opóźnienia, należy utworzyć timer (w opowiedniej akcji) i wykorzystać jego zdarzenie o upłynięciu czasu jako przejście do kolejnego stanu,
  • należy unikać zapisywania informacji w innych zmiennych, jedynie zmienna stanu powinna określać jego stan (czasem dodatkowa zmienna jest to nie do uniknięcia),
  • przy projektowaniu należy szukać podobnych zachowań i zamykać je w pojedynczych akcjach,
  • podobnie należy postepować ze stanami i poszukiwać podobnych zachowań cząstkowych (aby to uwzględnić w modelu, może być potrzebne zastosowanie hierarchicznej maszyny stanowej),
  • jeśli zachowanie systemu jest na tyle złożone (być może składa się on z kilku części), że nie jest on zawsze w jednym stanie, oznacza to, że potrzeba wprowadzić dwie (lub więcej) maszyny stanowe - ortogonalne względem siebie i zadbać o ich synchronizację (najlepiej zdarzeniami).

Prosta implementacja maszyny stanowej
W najprostszej postaci maszynę stanową można zakodować w postaci zagnieżdzonych instrukcji switch-case:

int sm_event_handler( struct * event_t ev ){
	switch( state ){
		case STATE_OFF:
			//obsluga zdarzen w stanie OFF
			switch( ev->signal ){
				case SIG_ENABLE:
					sm_transition( STATE_WAITING );
					return 0;
				}
			return -1;
		case STATE_ACTIVATED:
			//obsluga zdarzeń w stanie ACTIVATED
			switch( ev->signal ){
				case SIG_TIMER:
					blink();
					return 0;
				case SIG_MATCH:
					beep();
					return 0;
		...

Czytelność takiego kodu pozostawia wiele do życzenia, podobnie jest z jego efektywnością. Łatwo zauważyć, że zupełnie niepotrzebnie jest wykonywane wielokrotne sprawdzanie czy dany stan jest taki czy inny (case'y w zewnętrznym switch).

Maszyna stanowa - lepsza implementacja
Problemów obecnych w prostej implementacji można łatwo uniknąć, wystarczy zauważyć, że numery kryjące się pod symbolicznymi nazwami stanów (np. STATE_OFF, STATE_ACTIVATED itd) mogą tworzyć zbiór kolejnych liczb naturalnych. Nic nie stoi na przeszkodzie aby je zdefiniować następująco:

typedef enum{ STATE_OFF=0, STATE_ACTIVATED, STATE_WAITING, STATE_DETECTED } state_t;

state_t state = STATE_OFF; //zmienna na stan bieżący, zainicjowana stanem STATE_OFF

Dzięki temu możliwe jest rozbicie jednej funkcji obsługi zdarzeń na oddzielne funkcje dla każdego stanu i umieszczenie wskaźników do tych funkcji w tablicy:

typedef int (*sm_handler_t)( struct event_t * ev );//wskaźnik do funkcji

//tablica wskaźników
sm_handler_t handlers[]={ sm_handler_state_off, 
			  sm_handler_state_activated, 
			  sm_handler_state_waiting,
			  sm_handler_state_detected
			};

Zamiast switch-case należy wywoływać funkcję z tablicy, która jest umieszczona na pozycji wskazywanej przez bieżący stan.

int sm_event_handler( struct event_t* ev ){
//wywołanie funkcji:
	return handlers[ state ](&ev);
}

//definicja pojedynczego handlera
static int sm_handler_state_off( struct event_t * ev )
{
	switch( ev->signal ){
		case SIG_ENABLE:
		sm_transition( STATE_WAITING );
		return 0;
	}
	return -1;
}
//dalej definicje handlerów dla kolejnych stanow
...

Jak widać osiąga się w ten sposób izolację obsługi zdarzeń dla poszczególnych stanów. Kod jest bardziej czytelny i wywoływana jest tylko ta część, która jest związana z bieżącym stanem.

Więcej maszyn stanowych
Powyższe przykłady implementacji ilustrują jedynie pewną technikę, nie pokazują natomiast jak radzić sobie z:
- wieloma instancjami maszyny tego samego typu,
- definiować maszyny stanowe, różnych typów,
aby zobaczyć pewne rozwiązanie można zajrzeć do
implementacji maszyn stanowych w systemie DioneOS. Definiowanie instancji maszyny stanowej można rozwiązać przez wprowadzenie struktury zawierającej wszystkie zmienne, które były dotychczas globalne:

struct state_machine_t{
	sm_handler_t * handlers; //tablica handlerów dla poszczególnych stanów
	int state;	//bieżący stan
	int states_nb;  //liczba stanów
	void * xdata;	//jakieś dodatkowe prywatne dane maszyny stanowej
}

A następnie przekazywać tą strukturę jako argument do funkcji-handlerów i dalej gdzie ważne jest jakiej maszyny dotyczy operacja. Zamieszczony tu opis dotyczy języka C (jeśli używa się C++ jeszcze się to ułatwi: kolejne instancje to po prostu obiekty danej klasy).

int sm_handler_state_off( struct state_machine_t * sm, struct event_t* ev )
{
	switch( ev->signal ){
		case SIG_ENABLE:
			sm_transition( sm, STATE_WAITING );
			return 0;
	return -1;	
}

Definiowanie różnych typów maszyn
Gdy rozważa się definiowanie różnych typów maszyn stanowych, konieczne jest zaplanowanie odpowiedniego nazewnictwa (przestrzeni nazw). Trzeba bowiem zdefiniować stany oraz sygnały dla maszyny każdego rodzaju. Można rozważać wprowadzenie globalnego zbioru sygnałów (jakiś enum) gdzie kolejny nowy typ maszyny dodaje swoje sygnały. Taka implementacja zbiega się z rozwiązaniem, w którym sygnały (tzn. rodzaje zdarzeń) są niezależne od maszyny stanowej i są zbiorem ogólnym.

Można przyjąć konwencję definiowania maszyny nowego typu w osobnym pliku o nazwie związanej z tworzonym typem (takie postępowanie jest wykorzystywane w innych językach programowania). Taki plik zawiera cały niezbędny kod do obsługi maszyny stanowej.

Oddzielenie definicji od wykorzystania (framework, biblioteka)
Im więcej razy wykorzystuje się maszyny stanowe, tym bardziej kusi rozwiązanie, w którym użytkownik nie zajmuje się samodzielną implementacją maszyn stanowych a tylko definiuje specyficzne dla niego elementy albo używa już istniejące typy maszyn. Istnieją rozwiązania (m.in. w
systemie DioneOS) gdzie dostarczany jest framework, który tworzy pewnego rodzaju szablon rozwiązania maszyny stanowej. Może to mieć postać źródeł w języku C, makrodefinicji oraz nagłówków. Programista definiuje maszynę swojego typu z wykorzystaniem tego frameworka definiując jedynie handlery, zdarzenia i stany. W kolejnym kroku, aby wykorzystać jakiś typ powołuje się instancję takiej maszyny stanowej. Można dostrzec tu kolejne poziomy abstrakcji:
poziom rodzaj opis uwagi
L1 META Framework maszyn stanowych zapewnia kod i metody do tworzenia maszyn stanowych
L2 TYPY Typ maszyny implementacja maszyny określonego typu
L3 INSTANCJA Instancja maszyny wykorzystanie, utworzenie instancji maszyny określonego typu

Manager maszyn stanowych i maszyna stanowa jako aktywny obiekt
Funkcja obsługująca zdarzenia to nie wszystko. Aby efektywnie korzystać z maszyn stanowych potrzebna jest jakaś infrastruktura zapewniająca przekazywanie zdarzeń, przydzielanie czasu dla kolejnych maszyn, obsługę utworzenia i niszczenia. Często stosuje się odpowiedni manager, który zajmuje się tymi funkcjami. Warto zwrócić uwagę, że wiekszość rozwiązań bazuje na sposobie działania Run To Completion, co oznacza, że maszyna (handler) działa tak długo, aż wykona obsługę zdarzenia. W tym czasie pozostałe maszyny są wstrzymane. Aby zapewnić, że w tym momencie nie będzie zgubione żadne zdarzenie, stosuje się kolejki gromadzące zdarzenia. Gdy sterowanie wróci do managera i jakieś zdarzenia oczekują na obsłużenie, wywołuje on odpowiedni handler, odpowiedniej maszyny stanowej. W takim przypadku nie jest dozwolone (albo jest niezalecane) blokowanie się w handlerach (oczekiwanie, wykorzystanie funkcji blokujących). Zobacz przykład
managera zastosowanego w systemie DioneOS.

W przypadku, gdy potrzebna jest pseudo-równoległość, można stosować wielowątkowość i budować aktywne obiekty:
- manager może być wielowątkowy i wykorzytywać jeden wątek do wielu maszyn
- maszyna stanowa może posiadać swój wątek (implementacja w postaci aktywnego obiektu).
W takich przypadkach trzeba pamiętać o odpowiedniej ochronie dostępu do współdzielonych danych i starać porozumiewać się z maszynami za pomocą zdarzeń.

Generatory kodu i translatory
Na zakończenie warto wspomnieć o generatorach kodu - programach, które z modelu (np. w UMLu) generują kod jego implementacji. W takim przypadku cała treść handlerów, definicje sygnałów, stanów itp są tworzone automatycznie na podstawie tłumaczenia pliku modelu narysowanego w programie graficznym. Programista jest zwalniany z konieczności implementacji tych rzeczy a musi jedynie dopisać obsługę akcji. Tworzenie takich generatorów do maszyn stanowych należy do doświadczenia pracownika firmy ELESOFTROM (zobacz linki poniżej).

Linki

  1. StarUML - darmowy program do rysowania schematów w UMLu, w tym maszyn stanowych,
  2. Strona standardu UML, specyfikacje do pobrania,
  3. "Translator of Hierarchical State Machine from UML Statechart to the Event Processor Pattern", MIXDES, 2007, str. 684-687, ISBN 83-922632-9-4,
  4. "New Pattern for Implementation of Hierarchical State Machines in the C Language, Optimized for Minimal Execution Time on Microcontrollers", MIXDES, 2008, str. 605-609, ISBN 83-922632-7-8,