Do spisu treści tematu 3

3.3.5 RT-Linux

Spis treści

• Wprowadzenie
• Emulacja przerwań
• Zegar systemowy
• Procesy czasu rzeczywistego i szeregowanie
• Komunikacja między procesami
• Podsumowanie
• Bibliografia

Wprowadzenie

Podstawową cechą komputerowego systemu czasu rzeczywistego jest zdolność do odpowiednio krótkiej reakcji na zdarzenia generowane przez urządzenia zewnętrzne. Typowym zastosowaniem takich systemów są pomiary, sterowanie urządzeniami przemysłowymi, itp.

System operacyjny czasu rzeczywistego to system gwarantujący spełnianie wymogów czasowych związanych z wykonywanymi procesami.

W jądrze Linuxa, począwszy od wersji 2.0.0, zaimplementowano tryby szeregowania dla procesów czasu rzeczywistego, zgodne ze specyfikacją POSIX.1b (Round-Robin oraz FIFO). Nie wystarcza to jednak, aby można było uznać Linux za system czasu rzeczywistego. W zadaniach takich Linux sie, po prostu, nie sprawdza. Wynika to przede wszystkim z: częstego wyłączania przerwań w celu ochrony krytycznych części kodu jądra, opóźnień w procedurach obsługi przerwań, nie dających się przewidzieć opóźnień związanych z pamięcią wirtualną, charakterystki szeregowania procesów i małej częstotliwości zegarów systemowych. Podstawową cechą Linuxa jest to, iż proces znajdujący się trybie jądra nie może zostać wywłaszczony przez inny proces. Upraszcza to znacząco implementację, gdyż nie trzeba przejmować się wielowejściowością (ang. reentrant) funkcji systemowych. Ponieważ wykonanie funkcji systemowej może trwać dość długo, opóźnia to wznowienie procesu realtime i, w efekcie, uniemożliwia odpowiednio szybką reakcję na zdarzenie zewnętrzne.

Z uwagi na duże zapotrzebowanie na ogólnodostępny system operacyjny czasu rzeczywistego podjęto wysiłki nad modernizacją Linuxa. Projekt ten nosi nazwę "A Linux-based Real-Time Operating System", w skrócie: RT-Linux. Dostępny jest tylko dla architektur oparych na procesorach Intela.

Niniejszy opis dotyczy głównie algorytmów szeregowania udostępnianych przez RT-Linux. Krótko opiszę także inne modyfikacje jądra systemu.

Emulacja przerwań

Jednym ze wspomnianych problemów, uniemożliwiających szybką reakcję systemu, jest notoryczne wyłączanie przerwań w kodzie jądra, służące synchronizacji w krytycznych części kodu. Postanowiono całkowicie wyeliminować włączanie i wyłączanie przerwań. Okazało się to możliwe, dzięki bardzo sprytnej metodzie, polegającej na wprowadzeniu warstwy emulacji przechwytującej przerwania sprzętowe. Wszystkie wystąpienia instrukcji cli, sti, iret odpowiedzialnych, odpowiednio: za wyłączanie przerwań, ich włączanie oraz powrót z procedury obsługi przerwania zastąpiono makrodefinicjami: S_CLI, S_STI oraz S_IRET.

Jak to działa? Gdy w standardowym jądrze, w wyniku wykonania instrukcji cli przyjmowanie przerwań zostałoby zablokowane, w "emulatorze" ten fakt jest zapamiętywany przez ustawienie odpowiedniej flagi. Przerwania pozostają nadal włączone. Jeśli w sekcji krytycznej wystąpi przerwanie i flaga jest ustawiona - wykonanie procedury obsługi przerwania zostaje przełożone na później, aż do wykonania instrukcji sti.

Zegar systemowy

Zegar systemowy w standardowym Linuxie "tyka", jak na potrzeby systemów czasu rzeczywistego, stosunkowo wolno - 100 razy na sekundę. Znaczy to, że 100 razy na sekundę dochodzi do przerwania pracy procesora i przejścia do procedury obsługi przerwania zegarowego (funkcja timer_interrupt() w arch/i386/kernel/time.c). Przerwania tego typu mają miejsce w stałych odstępach czasu (tzw. periodic clocks). Uzyskanie odpowiednio wysokiej dokładności pracy zegara jest kompromisem na rzecz opóźnień związanych z ich obsługą - przerwania kosztują.

W jądrze RT-Linuxa postanowiono wykorzystać specjalny układ zegara Intel 8354 oraz wewnętrzne zegary procesora Pentium. Zegar taki może być zaprogramowany w taki sposób, że po zadanym czasie, określonym z dokładnością do 1 mikrosekundy, generowane jest przerwanie. Dzięki temu narzut związany z przerwaniami jest bardzo mały, gdyż do przerwania dochodzi tylko wtedy, gdy jest potrzebne, a nie ciągle, w stałych odstępach czasu.

Procesy czasu rzeczywistego i szeregowanie

Jest to swoista rewolucja w jądrze Linuxa. Wprowadzono specjalną klasę procesów - realtime tasks. Procesy te cały czas wykonywane są w trybie jądra, współdzieląc z jądrem przestrzeń adresową. Pociąga to za sobą następujące skutki:   

• Szeregowanie procesów pracujących na tym samym poziomie ochrony jest tańsze dzięki programowej, nie sprzętowej, realizacji. Zmiana kontekstu sprowadza się do zapamiętania rejestrów i ich ponownego załadowania. Odpada narzut związany ze zmianą trybu pracy procesora oraz z czyszczeniem rejestrów asoscjacyjnych procesora (chodzi o tzw. TLB, translation lookaside buffer, który musi być unieważniony w momencie zmiany rejestru bazowego układu zarządzającego pamięcią).
     
• Wspólna przestrzeń adresowa godzi w stabilność systemu. Błąd w programie wykonującym się jako proces realtime może doprowadzić do awarii systemu.
     
• Procesy realtime mogą komunikować się i współdzielić dane bezpośrednio.
     
• Rozmiar stosu procesów jest stały - określany w momencie tworzenia procesu.

Do zaimplementowania procesów wykonujących się w trybie jądra skorzystano z cennej cechy Linuxa, polegającej na dynamicznym ładowaniu i usuwaniu tzw. modułów jądra.

Co więcej, fragmenty kodu odpowiedzialne za szeregowanie procesów realtime mogą być także skonfigurowane jako moduły jądra. Umożliwia to użytkownikowi napisanie własnego schedulera i uruchomienie go "w locie", bez potrzeby rekompilacji jądra.
   

Struktura rt_task_struct

Z każdym z procesów realtime związana jest struktura rt_task_struct. Istotne jej pola to:

• state - określa stan procesu. Możliwe stany to:
  
  RT_TASK_READY - proces jest gotowy do wykonania (znajduje się w kolejce procesów gotowych)
  
  RT_TASK_DORMANT - proces wstrzymany; może zostać wznowiony tylko przez inny proces
  
  RT_TASK_DELAYED - dla procesów "okresowych"; wznowienie procesu odłożone jest do chwili określonej przez pole resume_time
     
• priority - wartość priorytetu procesu z zakresu 0...1000000
      
• resume_time - dla procesów "okresowych"; godzina "budzenia" procesu
      
• period - dla procesów "okresowych"; określa odstęp czasu między kolejnymi wznowieniami procesu

Zmienna rt_linux_task

Struktura opisująca "proces" jądra. Jądro wraz ze wszystkimi "zwykłymi" procesami stanowi osobny proces (w odniesieniu do procesów realtime) i ma najniższy priorytet.
     

Zmienna rt_tasks

Wskaźnik na pierwszy proces realtime. Wszystkie procesy, włącznie z rt_linux_task powiązane są w jedną listę, bez względu na ich stan (nie tworzy się osobnej kolejki procesów gotowych).

Priority-based Rate Monotonic Scheduling Algorithm

Jest to podstawowy algorytm szeregowania dostępny w RT-Linuxie. Każdy z procesów realtime ma przydzielony unikatowy priorytet (niższa wartość oznacza wyższy priorytet; unikatowość priorytetów nie jest sprawdzana!). Procesom nie przydziela się kwantu czasu na działanie - zakłada się, że procesy realtime same oddadzą procesor. Proces wywłaszczany jest tylko wtedy, gdy pojawia się gotowy proces o wyższym priorytecie. Proces realtime może być procesem "okresowym" - będzie wznawiany w równych odstępach czasu, o ile nie działa proces o wyższym priorytecie.

Schemat algorytmu:

rt_schedule()
{
   for (każdy gotowy proces realtime)
      wybierz proces o najwyższym priorytecie;

   if (wybrano proces)
   {
       for (każdy wstrzymany proces realtime o wyższym priorytecie niż
                                              priorytet wybranego procesu)
          wybierz proces, który powinien być wznowiony najwcześniej;
          
       if (wybrano wstrzymany proces)
           ustaw zegar na czas "budzenia" procesu           
   }
   else
       wybierz "proces" jądra;

   wznów wybrany proces;
}

wake_up()
{
   dodaj proces do kolejki procesów gotowych;

   if (priorytet "budzonego" procesu > priorytet procesu bieżącego)
      rt_schedule();
}
    

Earliest Deadline First Algorithm (EDF)

Jest to jeszcze prostszy algorytm. Wszystkie procesy realtime mają taki sam priorytet, wyższy, oczywiście, niż priorytet procesu "jądra". Do struktury rt_task_struct dodano pole absolute_deadline, określające ostateczny czas wznowienia procesu.

Schemat algorytmu:

rt_schedule()
{
   for (każdy gotowy proces realtime)
      wybierz proces o najmniejszej wartości absolute_deadline;

   if (wybrano proces)
   {
       for (każdy wstrzymany proces                         
             wybierz proces, który powinien być wznowiony najwcześniej; 

       if (wybrano wstrzymany proces)
          ustaw zegar na czas "budzenia" procesu
   }
   else
      wybierz "proces" jądra;

   wznów wybrany proces;
}
   

Funkcje i stałe

• int rt_task_init(RT_TASK *task, void (*fn)(int data), int data, int stack_size, int priority);
  
  Utworzenie nowego procesu realtime. Znaczenie parametrów:
  task - wskaźnik na strukturę rt_task_struct nowego procesu
  fn - funkcja, która zostanie wywołana przez nowo utworzony proces
  data - parametr przekazywany funkcji fn
  stack_size - rozmiar stosu jaki będzie przydzielony procesowi
  priority - priorytet procesu
  
•  int rt_task_make_periodic(RT_TASK *task, RTIME start_time, RTIME period)
  
  Przełączenie procesu w tryb "okresowy". Proces zostanie uruchomiony o czasie start_time i będzie wznawiany co period jednostek czasu
     
• int rt_task_delete(RT_TASK *task)
  
  Usunięcie procesu.
     
• int rt_task_wait(void)
  
  Wstrzymanie wykonywania bieżącego procesu.
     
• int rt_task_suspend(RT_TASK *task)
  
  Wstrzymanie wykonywania wskazanego procesu.
     
• int rt_task_wakeup(RT_TASK *task)
  
  Wznowienie wskazanego procesu.
      
• void rt_use_fp(int flag)
   
  Ustawienie flagi (dla bieżącego procesu) mówiącej czy proces będzie używał koprocesora matematycznego. Ma to wpływ na zachowywany kontekst procesu.
      
• RTIME rt_get_time(void);
  
  Zwraca wartość wewnętrznego zegara RT-Linux. Zegar ten nie jest synchronizowany ze "standardowymi" zegarami jądra Linuxa. Czas wyrażany jest w wewnętrznych jednostkach równych "mniej więcej" 1 mikrosekundzie. (Stała RT_TICKS_PER_SEC określa liczbę tyknięć zegara w czasie sekundy, standardowo wynosi 1193180).
        
  

Komunikacja między procesami

Z procesami realtime związane jest istotne ograniczenie. Proces taki nie może wywoływać żadnej ze standardowych funkcji systemowych jądra. Wynika to z tego, iż (większość) funkcji jądra nie jest wielowejściowa. Proces wykonujący funkcję jądra mógłby zostać wywłaszczony przez inny proces, który mógłby np. wywołać tę samą funkcję systemową. Dlatego wprowadzono specjalny mechanizm komunikacji, nazwany RT-FIFO, pomiędzy procesami realtime a procesem jądra oraz pomiędzy procesami realtime a zwykłymi procesami. Idea działania tego mechanizmu jest bardzo podobna do standardowych łącz FIFO.

Bufory RT-FIFO tworzone są w przestrzeni pamięci jądra. Identyfikowane są przez "globalne" klucze, będące liczbami całkowitymi.

Dostępne operacje na kolejkach RT-FIFO (dla procesów realtime):

• int rtf_create(unsigned int fifo, int size) - utworzenie bufora RT-FIFO o numerze fifo i rozmiarze size
     
• int rtf_destroy(unsigned int fifo)- zlikwidowanie bufora o zadanym numerze
     
• int rtf_resize(unsigned int fifo, int new_size)- zmiana wielkości bufora
      
• int rt_fifo_put(unsigned int fifo, char *buf, int count) - zapisanie count bajtów wskazywanych przez buf (funkcja zwraca -1, gdy bufor się przepełni, wpp zwraca wartość count)
      
• int rt_fifo_get(unsigned int fifo, char *buf, int count) - odczytanie count bajtów z bufora pod adres wskazany przez buf (funkcja zwraca -1, gdy w bufor zawiera mniej niż count bajtów, wpp zwraca count)
        
• int rtf_create_handler(unsigned int fifo, int (*handler)(unsigned int fifo)) - Przypisanie funkcji obsługi do danego bufora. Przekazana funkcja będzie wywoływana każdorazowo, gdy "zwykły" proces dokona operacji odczytu/zapisu na buforze. Argumentem funkcji jest nr bufora.

"Zwykłe" procesy z buforów RT-FIFO mogą korzystać standardowo, tak jak z każdych innych urządzeń znakowych. Dodane urządzenia odpowiadające buforom o kolejnych numerach to: /dev/rtf0, /dev/rtf1, itd.

Podsumowanie

Dzięki bardzo sprytym i stosunkowo niewielkim modyfikacjom udało się z "ospałego" systemu uczynić system czasu rzeczywistego. Jest to kolejny dowód, że Linux jest przemyślanym i dobrze zaprojektowanym systemem. Opisywana wersja RT-Linuxa, 0.5a, znajduje się w stadium alpha, ale mimo to wydaje się być stabilna (autorowi opisu nie udało się "rozłożyć" RT-Linuxa, chyba, że z własnej winy przez doprowadzanie do zagłodzenia). RT-Linux wprowadza nową jakość, czyniąc z Linuxa groźnego konkurenta dla komercyjnych systemów takich jak QNX.
   
Koncepcje wykorzystane w RT-Linuxie przypominają system operacyjny, prawie historycznego już, komputera Amiga - AmigaOS. Jest to wielozadaniowy system, w którym procesy szeregowane są typowym algorytmem Round-Robin. Dzięki temu, iż system ten nie udostępnia pamięci wirtualnej ani ochrony pamięci (wszystkie procesy, jak i jądro działają w tej samej przestrzeni adresowej) doskonale nadaje się do zadań czasu rzeczywistego, w których był bardzo często wykorzystywany.

Bibliografia

1. Pliki źródłowe RT-Linux 0.5a
2. Michael Barabanov A Linux-based Real-Time Operating System
3. Ismael Ripoll Earliest Deadline First Algorithm