Implementacja RTLinuksa

Sterownik przerwań

W niezmodyfikowanym jądrze Linuksa wiele fragmentów jądra, głównie sterowniki urządzeń, chroni krytyczne obszary kodu poprzez zablokowanie przerwań instrukcją cli (instrukcja ta ustawia odpowiednią flagę w procesorze). Gdy przerwania są zablokowane, to nadchodzące przerwania nie powodują przejścia do funkcji obsługi przerwania - zamiast tego, są kolejkowane; odpowiednie funkcje zostają wykonane dopiero, kiedy jądro ponownie uruchomi obsługę przerwań, wykonując instrukcję sti (z reguły wywołując funkcję restore_flags(), przywracającą zapisany wcześniej (przed wywołaniem cli) stan procesora).

2229         if (index >= MAX_HWIFS)
2230                 return;
2231         save_flags(flags);      /* all CPUs */
2232         cli();                  /* all CPUs */
2233         hwif = &ide_hwifs[index];
2234         if (!hwif->present)
2235                 goto abort;
2236         for (unit = 0; unit < MAX_DRIVES; ++unit) {
2237                 drive = &hwif->drives[unit];
2238                 if (!drive->present)
2239                         continue;
2240                 if (drive->busy || drive->usage)
2241                         goto abort;
2242                 if (drive->driver != NULL && DRIVER(drive)->cleanup(drive))
2243                         goto abort;
2244         }
2245         hwif->present = 0;
2246         
2247         /*
2248          * All clear?  Then blow away the buffer cache
2249          */
2250         sti();2251         for (unit = 0; unit < MAX_DRIVES; ++unit) {
2252                 drive = &hwif->drives[unit];

W tym kawałku kodu przerwania zostają zablokowane w linijce 2232, i odblokowane w 2250. Jeśli jakieś przerwanie nadejdzie, kiedy wykonywana jest linijka 2232 - jego obsłużenie zostanie opóźnione aż do 2250. Rozwiązanie takie ma bardzo poważną wadę: nie da się wywłaszczyć procesu, który wyłączył przerwania. Co prawda twórcy kernela dbają o to, żeby okresy pracy z wyłączonymi przerwaniami były jak najkrótsze, i w najnowszych wersjach jądra czas ten nie przekracza 80 mikrosekund, jednak do niektórych zastosowań nawet taki czas jest zbyt długi. Co więcej, jako, że jądro jest rozwijane jednocześnie przez wiele osób, i autorem modułu może zostać każdy, istnieje ryzyko, że w wyniku beztroski jakiegoś programisty któraś kolejna wersja jądra będzie spędzać z wyłączonymi przerwaniami czas dłuższy, niż poprzednia - co może spowodować, że kernel przestanie 'nadążać' i popsuć właściwości RT systemu.

RTLinux radzi sobie z tym problemem w genialnie prosty sposób - nie pozwala kernelowi Linuksa na wyłączenie przerwań, emuluje jedynie takie zachowanie. RTCore odbiera wszystkie przerwania, i decyduje, co należy z nimi zrobić.



Zmiany, które muszą być wprowadzone w jądrze Linuksa, dotyczą jedynie cli(), sti() i 'wrapperów' przerwań. Po ich wprowadzeniu, przerwania rozstrzygane są następująco:

Gdy nadchodzi przerwanie:

zostaje wywołana procedura obsługi przerwania RT
procedura ta robi, co należy zrobić dla wątków RT, i sprawdza stan SFIF
o ile SFIF == 0, informacja o przerwaniu zostaje wrzucona do kolejki oczekujących przerwań i następuje powrót z procedury obsługi za pomocą instrukcji iret
o ile SFIF == 1, informacje na stosie zostają odpowiednio zmodyfikowane dla potrzeb linuksowego handlera (tak, żeby wyglądało to na normalne przerwanie), po czym zostaje wywołany odpowiedni 'wrapper'
wrapper uruchamia odpowiednią linuxową procedurę obsługi przerwania nie-RT
procedura robi, co do niej należy, i przekazuje sterowanie z powrotem do wrappera
wrapper sprawdza, czy są jeszcze jakieś zakolejkowane, oczekujące przerwania: jeśli tak, zaczyna je przetwarzać, jeśli nie - wykonuje iret (instrukcję powrotu z obsługi przerwania)

Gdy kernel linuksa wywołuje cli(), specjalna globalna zmienna SFIF zostaje ustawiona na 0 - oznacza to, że kernel nie chce dostawać przerwań.

Gdy kernel linuksa wywołuje sti(), uruchomiona zostaje emulacja wszystkich zakolejkowanych przerwań (o ile jakieś oczekują), po czym zmienna SFIF zostaje ustawiona na 1.

Podobnie blokowane / odblokowywane są poszczególne przerwania.

Uwaga: wątki RT mają pełen dostęp do flagi kontrolującej blokowanie przerwań w procesorze - omijają emulator. Oznacza to, że mogą wyłączać i włączać przerwania do woli, dlatego przy pisaniu ich należy być ostrożnym!

Scheduler

Dzięki temu, że procesy RT mają wspólną przestrzeń adresową, zmiana bieżącego procesu jest bardzo szybka. Scheduler RTLinuksa ładowany jest jako moduł, co umożliwia łatwą zamianę go na inny.

Standardowy scheduler korzysta z priorytetów przydzielonych na stałe wątkom RT (Fixed Priority Scheduler). Wątek RT, który zostaje uruchomiony, nie ma przydzielonego timeslice'a - wykonuje się do momentu, kiedy sam postanowi oddać procesor, albo gdy zostanie wywłaszczony przez wątek o wyższym priorytecie. Scheduler jest uruchamiany jedynie wtedy, gdy rzeczywiście jest potrzebny, a nie co jakiś ustalony przedział czasu - prowadzi to do zmniejszenia narzutu związanego z jego działaniem.

Algorytm działania schedulera jest następujący:

rt_schedule():

spośród gotowych do uruchomienia procesów RT wybieramy ten o największym priorytecie (A)
spośród wstrzymanych wątków RT o priorytecie większym od priorytetu A wybieramy procesów, który powinien być wznowiony najwcześniej (B)
o ile wybrano jakiś proces B, ustawiamy zegar na czas 'budzenia się' B
wznawiamy A


wake_up():

dodaj budzony proces do kolejki gotowych
o ile jego priorytet > priorytet bieżącego, rt_schedule()



O ile mamy do czynienia z procesami okresowymi, dla których deadline = okres (np, coś _musi_ być wykonane co każde 50 ms), można je uporządkować korzystając z Rate Monotonic Algorithm. Algorytm jest prosty - im dany proces ma mniejszy okres, tym większy priorytet powinien mieć. Uzyskane uporządkowanie jest optymalne dla algorytmów szeregowania o stałym priorytecie.

Zbiór procesów na pewno spełni wszystkie deadline'y, jeśli

C₁/T₁ + C₂/T₂ + ... + C_n/T_n  <= n(2^(1/n) - 1)

O lewej stronie można myśleć jako o 'zajętości' procesora, prawa dąży do ln 2 ~= 0.69. Oznacza to, że korzystając z tego algorytmu w pesymistycznym przypadku procesor wykorzystany jest jedynie w 69% (średnio, w 88%)

Inny dostępny scheduler do RTLinuksa korzysta z algorytmu Earliest Deadline First - wybierane są te procesy, których deadline jest najbliższy.

RT FIFO

Do komunikacji między procesami RT, albo między procesem RT i nie-RT służą kolejki FIFO czasu rzeczywistego. Są to urządzenia znakowe - /dev/rft0 ... /dev/rft63 (liczbę kolejek można ustawić przy kompilacji RT-Linuksa, standardowo jest to 64).

Z poziomu programów RT, do obsługi kolejek służą funkcje:

rft_create	- tworzy kolejkę
rft_destroy	- niszczy kolejkę
rft_get		- pobiera dane z kolejki, zwraca błąd, gdy nie ma danych
rft_put		- wkłada dane do kolejki
rft_create_handler	- ustawia funkcję wywoływaną, gdy jest jakaś aktywność w kolejce ze strony nie-RT
rft_create_rt_handler	- ustawia funkcję wywoływaną, gdy jest jakaś aktywność w kolejce ze strony RT

Można też korzystać ze zwykłego interfejsu plików: open, close, read i write

Operacje na kolejkach w procesach RT są nieblokujące. Dzięki temu nie dochodzi do zakleszczeń.

Z poziomu procesów nie-RT dostęp do kolejek jest dokładnie taki, jak do zwykłych plików. Operacje mogą być blokujące albo nieblokujące.

POSIX IO

Jeden z modułów RTLinuksa, posixio, zapewnia ograniczone wsparcie dla operacji wejścia i wyjścia. Zwykła POSIXowa funkcja open, konieczna dla czytania i pisania z / do urządzeń, jest z definicji nie-RT - czas potrzebny na rozwinięcie nazwy pliku, podążanie za symlinkami czy odczytywanie katalogów może trwać dowolnie długo. Dlatego też, funkcja open używana przez RTLinux ma istotne ograniczenie: można nią otwierać jedynie ścieżki postaci /dev/nazwa (to właśnie pozwala na korzystanie z tych funkcji do obsługi kolejek RT FIFO)

Oczywiście, można sobie poradzić z tym problemem w następujący sposób: otworzyć dowolny plik w procesie nie-RT, i wysłać jego zawartość do procesu RT np za pomocą RT-FIFO.

Zegar

Dla sprawnego funkcjonowania systemu RT konieczny jest odpowiednio dokładny zegar - na przykład do uruchamiania schedulera, lub do mierzenia bardzo niewielkich odstępów czasu.

W większości systemów operacyjnych, na przykład w Linuksie, zegar 'tyka' co jakiś ustalony czas (w Linuksie około 100 razy na sekundę). To zdecydowanie za mało do zastosowań RT.

O ile zegar tyka często, dużo czasu procesora zostaje zmarnowane na być może niepotrzebną obsługę przerwań zegarowych; o ile tyka zbyt rzadko, zegar ma niewielką rozdzielczość i dokładne odczekanie ustalonego czasu przez proces może być niemożliwe.

RTLinux radzi sobie z tym problemem poprzez całkowite zlikwidowanie okresowych przerwań zegarowych: kiedy zegar 'tyka', określa się, kiedy powinno nastąpić następne tyknięcie, po czym następuje odpowiednie przeprogramowanie zegara. Pozwala to na precyzyjne odmierzanie czasu, z dokładnością do 1 mikrosekundy - przy zachowaniu niskiego narzutu na operacje związane z zegarem (przeprogramowanie chipa zegara Intel 8354, obecnego w każdym PC, jest dość powolne. Na szczęście procesory od Pentium wzwyż mają wbudowany wewnętrzny zegar o szybkim dostępie).

Na przykład, załóżmy, że proces A chce być zbudzony za 5 ms, a proces B za 23 ms.

o ile korzystamy z zegara periodycznego, tykającego co 10 ms:
	
	w  0 ms zegar tyknie
	w 10 ms zegar tyknie, stwierdzi, że należy obudzić proces A - spóźniając się o 5 ms 
	w 20 ms zegar tyknie
	w 30 ms zegar tyknie, stwierdzi, że należy obudzić proces B - spóźniając się o 7 ms
	

o ile korzystamy z zegara takiego, jak w RTLinuksie:
	
	w  0 ms zegar tyknie, i stwierdzi, że następne tyknięcie powinno nastąpić za 5 ms
	w  5 ms zegar tyknie, stwierdzi, że należy obudzić A, i że następne tyknięcie powinno nastąpić za 18 ms
	w 23 ms zegar tyknie, i stwierdzi, że należy obudzić B
	


W rozwiązaniu z zegarem takim, jak w RTLinuksie, przerwań zegarowych jest mniej a procesy budzone są sprawniej.

Pamięć dzielona

Obsługę pamięci dzielonej do RTLinuksa dodaje moduł mbuff, autorstwa Tomasza Motylewskiego. Umożliwia on zakładanie bloków pamięci, dostęp do których mogą mieć zarówno procesy RT, jak i nie-RT. Obszary dzielone zakładane są w pamięci kernela, dzięki czemu nie mogą zostać wyswapowane z pamięci fizycznej - co umożliwia użycie ich w zastosowaniach RT. Alokowanie bloków korzysta z vmalloc, dlatego też nie wolno go dokonywać w trakcie działania programu RT, tylko przed jego rozpoczęciem (vmalloc może wymusić wyswapowanie części stron z pamięci fizycznej, przez co nie można określić czasu jego zakończenia)