Szeregowanie procesów w wybranych systemach operacyjnych

Spis treści

• System Mach
• Czym jest system Mach
• Założenia systemu
• Stany wątku
• Zarządzanie wątkami
• System QNX
• Czym jest system QNX?
• Mikrojądro
• Szeregowanie procesów
• Metody szeregowania procesów
• Funkcje modyfikujące szeregowanie i priorytet

System Mach

Czym jest system Mach?

Podstawowym celem twórców systemu Mach było zbudowanie rozproszonego systemu operacyjnego. Dlatego też system Mach zaprojektowano do pracy w systemach komputerowych zawierających od jednego do tysięcy procesorów. Realizacja wspomagania architektury wieloprocesorowej jest tu bardzo elastyczna. Ponadto system ten w łatwy sposób daje się przenosić na komputery o rozmaitej architekturze sprzętowej. Warto zauważyć, że system Mach jest w pełni zgodny z Unix BSD.

Założenia systemu

• Wspomaganie różnych architektur sprzętowych, w tym zestawów wieloprocesorowych typu:
  • UMA: Uniform Memory Access - procesory mają ujednolicony dostęp do pamięci systemu,
  • NUMA: Non-Uniform Memory Access - nieujednolicony dostęp do pamięci, tzn. procesory dzielą pamięć, lecz każdy z nich ma ograniczony dostęp (lub nie ma go wcale) do części pamięci w systemie,
  • NORMA: No Remote Memory Access - brak zdalnego dostępu do pamięci.
• Uproszczona struktura jądra z małą liczbą abstrakcyjnych konstrukcji
• Działanie rozproszone (zapewnia klientowi przezroczystość sieci i dodatkową organizację zewnętrzną i wewnętrzną)
• Możliwość zintegrowanego zarządzania pamięcią oraz komunikacją międzyprocesorową

Stany wątku

Wątek w systemie Mach może znajdować się w jednym z dwóch stanów:

• Wykonywany
  Wątek jest wykonywany przez procesor, znajduje się w kolejce wątków wykonywanych (czeka na przydział procesora) lub jest blokowany w jądrze (np. czeka na obsługę błędu braku strony).
• Zawieszony
  Nie jest wykonywany przez (żaden) procesor, nie czeka też w kolejce wątków wykonywanych.

Zarządzanie wątkami

W systemie Mach zastosowano prostą politykę zarządzania wątkami.

• Wszystkie wątki jednakowo rywalizują o zasoby, w tym również o przydział kwantów czasu
• Każdy wątek ma priorytet równy liczbie całkowitej z przedziału od 0 do 127, obliczonej na podstawie średniej wykładniczej zużytego przez niego czasu procesora (więc najniższy priorytet ma watek, który ostatnio długi czas korzystał z procesora).
• 32 globalne kolejki wykonywanych wątków. Gdy procesor staje się bezczynny, wtedy kolejki te są przeglądane (w porządku priorytetów) w celu wybrania czekających wątków.
• Kolejki lokalne (wykonywanych wątków) związane z procesorami - koordynuje je z kolejkami globalnymi. Wątki w kolejce lokalnej mają bezwzględny priorytet w stosunku do wątków z kolejek globalnych (ponieważ spełniają pewne obowiązki wobec jądra).
• Utrzymywana jest lista procesów bezczynnych.
• Zmienne kwanty czasu (stałe kwanty czasu są nieodpowiedni, ponieważ może się zdarzyć, że wątków do wykonania jest mniej niż procesorów, a przerywanie wykonania wątku jest operacją kosztowną)
• Wątki działające w trybie jądra nie podlegają wywłaszczeniom (wątki w trybie użytkownika mogą być przerywane).

System QNX

Czym jest system QNX?

QNX jest systemem czasu rzeczywistego, co oznacza, że potrafi bez opóźnienia, na bieżąco obsługiwać i przetwarzać informacje, które otrzymuje z klawiatury, myszy, czujników, portów szeregowych itd. Najbardziej istotna jest nie jego - zazwyczaj bardzo duża - szybkość, ale to, że gwarantuje czas, w jakim zostanie wykonane określone zadanie lub zdarzenie zewnętrzne. Ten gwarantowany czas obsługi umożliwia tworzenie programów "przewidywalnych", dających pewność działania nawet podczas dużego napływu informacji. Oprócz tej pewności programista otrzymuje zaawansowane możliwości kierowania kolejnością obsługi (sterowania priorytetem). Systemy tradycyjne (np. MS Windows, Linux) budują zawsze kolejkę zadań do wykonania, ale szybkość ich obsługi nie jest gwarantowana i w dużej mierze ma charakter losowy. Z kolei rozbudowane możliwości definiowania priorytetów pozwalają na zastosowanie QNX jako systemu sterującego automatyką przemysłową, gdzie pewne zdarzenia mają znaczenie krytyczne (np. otwarcie zaworu bezpieczeństwa w zbiorniku przy gwałtownym wzroście ciśnienia czy przemieszczanie celu w systemach sterowania ogniem) i muszą być zawsze obsłużone na czas.

Mikrojądro

QNX zbudowano na podstawie mikrojądra Neutrino, a jego najważniejsza cechą jest to, że jako główna część systemu zajmuje się bardzo niewielką liczbą zadań, a właściwie tylko dwoma: obsługuje kolejkę zadań (tzw. schedule) do wykonania oraz steruje przekazywaniem wiadomości (message passing) między procesami działającymi w systemie. Różni go to znacząco od systemów klasycznych, takich jak Windows czy Linux, gdzie jądro decyduje o wszystkim, co dzieje się w systemie - obsłudze sieci, dostępie do plików, prawie dostępu itd. Samo jądro QNX jest więc niewielkie, a wszystkie usługi związane z plikami czy siecią obsługują cztery osobne procesy:

• Process Manager - odpowiedzialny za zarządzanie aktywnymi zadaniami
• Filesystem Manager - odpowiedzialny za operacje związane z systemem plików
• Device Manager - odpowiedzialny za sterowniki urządzeń
• Network Manager - odpowiedzialny za obsługę sieci.

Warto zauważyć, że te procesy systemowe nie mają żadnej uprzywilejowanej pozycji, a ich lista nie jest raz na zawsze zamknięta. Programiści mogą tworzyć własne usługi systemowe.

Szeregowanie procesów

Każdy z procesów wykonywanych w systemie QNX ma przyporządkowany priorytet który jest liczbą z przedziału 0 - do 31. Priorytet 31 jest najwyższy a 0 najniższy. Funkcja procedury szeregującej - wybranie ze zbioru procesów gotowych procesu który ma być teraz wykonywany. Procedura szeregująca jest aktywowana gdy:

1. Wystąpiło przerwanie zegarowe - proces bieżący wykorzystał przydzielony mu kwant czasu.
2. Wystąpiło przerwanie od urządzenia zewnętrznego - proces zablokowany na operacji wejścia /wyjścia stał się gotowy.
3. Proces bieżący wykonał wywołanie systemowe na skutek którego inny proces stał się gotowy.
4. Proces bieżący dobrowolnie oddał procesor lub zakończył się.
5. Proces bieżący naruszył mechanizm ochrony procesora co spowodowało przerwanie wewnętrzne procesora.

W systemie zawsze wykonywany jest proces gotowy o najwyższym priorytecie. Takich procesów może być jednak więcej niż jeden. Szeregowanie wywłaszczające (ang. preemptive scheduling) polega na tym, że jeśli proces P2 o wyższym priorytecie niż aktualnie wykonywany proces P1 stanie się gotowy, to proces P2 bezzwłocznie otrzymuje procesor a proces P1 jest wywłaszczany (ang. preeempted) i zawieszany.

Metody szeregowania procesów

Na każdym z priorytetów może obowiązywać jedna z trzech strategii szeregowania:

1. Szeregowanie karuzelowe (ang. Round Robin scheduling)
   Proces wykonywany jest aż do czasu gdy:
   • Samoistnie zwolni procesor.
   • Zostanie wywłaszczony przez proces o wyższym priorytecie.
   • Wyczerpie swój kwant czasu (ang. timeslice).
   
   
2. Szeregowanie FIFO (ang. FIFO scheduling)
   Proces wykonywany jest aż do czasu gdy:
   • Samoistnie zwolni procesor.
   • Zostanie wywłaszczony przez proces o wyższym priorytecie.
   Gdy procesy wykonywane z tym samym priorytetem stosują algorytm FIFO i operują na pewnym niepodzielnym zasobie, wzajemne wykluczanie zapewnione jest automatycznie. Nie ma potrzeby stosowania dodatkowych mechanizmów ochronnych np. semaforów.
   
   
3. Szeregowanie adaptacyjne (ang. Adaptive scheduling)
   Szeregowanie adaptacyjne przebiega według następujących zasad:
   • Gdy proces wyczerpie swój kwant czasu i nie zablokuje się sam, jego priorytet obniżany jest o 1. Zjawisko to nazywane jest redukcją priorytetu (ang. priority decay).
   • Gdy proces sam się zablokuje, przywracany jest mu początkowy priorytet.
   • Gdy proces nie zostanie wybrany do wykonania po 1 sekundzie priorytet jego zwiększany jest o 1.
   Szeregowanie adaptacyjne jest domyślną strategią szeregowania dla procesów uruchamianych zinterpretera poleceń (ang. shell).

Funkcje modyfikujące szeregowanie i priorytet

System dostarcza niezbędnych funkcji do zmiany i testowania priorytetu procesów i strategii szeregowania. Ustawienie priorytetu wykonuje się za pomocą funkcji

Znaczenie parametrów: pid to PID procesu któremu zmieniamy priorytet (gdy 0 to chodzi o proces bieżący), zaś prio to nowy priorytet z zakresu od 1 do 29 dla użytkownika root, od 1 do 19 dla innego użytkownika. Funkcja zwraca poprzedni priorytet procesu (gdy > 0) lub błąd (gdy -1).

Przy tworzeniu procesu potomnego priorytet i metoda szeregowania jest dziedziczona z procesumacierzystego. Do testowania priorytetu służy funkcja

gdzie pid to PID procesu którego priorytet testujemy. Funkcja zwraca priorytet procesu (gdy > 0) lub błąd (gdy -1)

Ustawienie metody szeregowania

Testowanie metody szeregowania:

#include &ltsys.sched.h>
void main(void)(
    struct sched_param param;

    int prio, alg;
    // Ustawienie strategii szeregowania i priorytetu
    param.sched_priority = 11;
    sched_setscheduler(0, SCHED_RR,& param);
    // Testowanie strategii szeregowania i priorytetu
    prio = getprio(0);
    printf(„Priorytet wynosi: %d\n”,prio);
    alg = sched_getscheduler(0);
    printf(„Startegia szeregowania: %d\n”,alg);
}