Szeregowanie w systemie Linux (jądro 2.6)

Informacje wstępne


W systemie Linux, podobnie jak w innych współczesnych systemach operacyjnych (Windows 2000, współczesne implementacje systemów uniksopodobnych) uwzględniono szeregowanie procesów czasu rzeczywistego. Są to rozwiązania spełniające wymagania tzw. łagodnego (tolerancyjnego) czasu rzeczywistego, co znaczy, że system próbuje wykonywać je szybciej niż inne zadania, ale nie gwarantuje ich zakończenia w określonym czasie (przed linią krytyczną). Priorytety dla zadań czasu rzeczywistego (czyli klas SCHED_FIFO i SCHED_RR) są zawsze wyższe — mają mniejsze wartości — niż priorytety zadań zwykłych.

  • Stosowany jest algorytm rotacyjny z wywłaszczaniem, oparty na priorytetach dynamicznych.
  • Wyróżnia 140 poziomów priorytetu związanych z 3 klasami (politykami) szeregowania:
    • SCHED_OTHER — polityka szereg, zwykłych zadań,
    • SCHED_FIFO — polityka szereg, zadań czasu rzeczywistego zgodnie z zasadą FIFO,
    • SCHED_RR — polityka szeregowania zadań czasu rzeczywistego w sposób rotacyjny.
  • Większa wartość oznacza niższy priorytet.

Priorytety procesów zwykłych


Wartość nice ma podobny charakter jak w systemie UNIX. Określa się jako składową statyczną priorytetu. W rzeczywistości nie jest ona liczbową wartością priorytetu, bo jest odwzorowywana na odpowiednią wartość z zakresu 100 – 139. W przeciwieństwie do tradycyjnego rozwiązania w systemie UNIX Linux oferuje zmiennej długości kwant czasu.

  • Priorytet (dynamiczny) składa się z części statycznej i części modyfikowanej przez planistę.
  • Część statyczna definiowana jest przez wartość nice z zakresu od -20 do 19.
  • Priorytet dynamiczny decyduje zarówno o pierwszeństwie w dostępie do procesora jaki i wielkości kwantu czasu (od 10 ms do 200 ms).
  • Preferowane są (nagradzane wyższym priorytetem dynamicznym) zadania ograniczone wejściem-wyjściem.

Priorytety procesów czasu rzeczywistego


W przypadku procesów zwykłych priorytet może się zmieniać, podobnie jak to było w systemie UNIX, ale zasady zmiany są inne. Dlatego ogólnie określa się go jako dynamiczny (chociaż ma również składnik statyczny). Priorytety zadań czasu rzeczywistego nie zmieniają się. Biorąc pod uwagę fakt, że priorytety te są wyższe, niż priorytety procesów zwykłych, istnieje ryzyko, że jeśli proces czasu rzeczywistego otrzyma procesor, zagłodzi inne zadania. Dlatego możliwość zmiany priorytetu (i tym samym strategii szeregowania) w zakresie czasu rzeczywistego zastrzeżona jest dla nadzorcy.

  • Priorytety przydzielane są statycznie (nie zmieniają się) z zakresu od 0 do 99.
  • Priorytety procesów czasu rzeczywistego są zawsze większe od priorytetów zadań zwykłych.
  • Do grupy zadań czasu rzeczywistego mogą być dołączona tylko procesy nadzorcy (użytkownika uprzywilejowanego root).

Odwzorowanie w tablicy priorytetów


Tablica priorytetów obejmuje 140 pozycji o wartościach od 0 (najwyższy priorytet) do 139 (najniższy priorytet). Wartości z zakresu 1 – 99 odpowiadają procesom czasu rzeczywistego, a większe wartości odpowiadają procesom zwykłym i odwzorowane są na odpowiednie wartości nice.

slajd 14

Struktury danych do zarządzania procesami gotowymi


Mechanizm szeregowania w jądrze 2.6 (2.5) został dość istotnie przebudowany w stosunku do rozwiązań wcześniejszych i również rozwiązań stosowanych w innych systemach operacyjnych. Ma to swoje skutki między innymi w strukturach danych. Podobnie, jak w przypadku tradycyjnego systemu UNIX, a także Windows 2000/XP podstawową strukturą jest kolejka priorytetowa, zwana tablicą priorytetów. W przeciwieństwie jednak do systemu UNIX nie ma tu przeliczania priorytetu każdego procesu co określony czas, priorytet dynamiczny wyznaczany jest na bieżąco, np. po zakończeniu kwantu czasu. Takie podejście mogłoby jednak oznaczać głodzenie, bo nowo wyliczony priorytet mógłby być większy niż priorytet innych procesów gotowych i oczekujących już przez dłuższy czas na procesor. W tradycyjnym systemie UNIX tego problemu unikało się w ten sposób, że co sekundę były przeliczane priorytety wszystkich procesów, a w wyniku tego przeliczenia karane były procesy, które dużo korzystały z procesora i nagradzana takie, które dłużej czekały.

W celu niedopuszczenia do głodzenia w systemie Linux stosowane są dwie kolejki priorytetowe. Jedna kolejka jest dla zadań, które mają prawo korzystać z procesora, zwanych zadaniami aktywnymi, a druga jest dla tzw. zadań przeterminowanych, które chwilowo wykorzystały już przydzielone im limity.

Podobnie, jak w systemie UNIX, w celu szybkiej identyfikacji pozycji niepustych w kolejkach priorytetowych, wykorzystywany jest wektor bitowy. W przeciwieństwie jednak do UNIXa, każdy bit odpowiada dokładnie jednej pozycji, czyli jednemu priorytetowi.

  • Tablica priorytetów dla zadań aktywnych — tablica kolejek procesów gotowych, które nie wykorzystały jeszcze kwantu czasu
  • Tablica priorytetów dla zadań przeterminowanych — tablica kolejek procesów gotowych, które wykorzystały kwant czasu
  • Mapa (maska) bitowa dla każdej z tablic, identyfikująca niepuste kolejki w tablicy priorytetowej

Struktury danych do zarządzania procesami gotowymi


Mechanizm szeregowania w jądrze 2.6 (2.5) został dość istotnie przebudowany w stosunku do rozwiązań wcześniejszych i również rozwiązań stosowanych w innych systemach operacyjnych. Ma to swoje skutki między innymi w strukturach danych. Podobnie, jak w przypadku tradycyjnego systemu UNIX, a także Windows 2000/XP podstawową strukturą jest kolejka priorytetowa, zwana tablicą priorytetów. W przeciwieństwie jednak do systemu UNIX nie ma tu przeliczania priorytetu każdego procesu co określony czas, priorytet dynamiczny wyznaczany jest na bieżąco, np. po zakończeniu kwantu czasu. Takie podejście mogłoby jednak oznaczać głodzenie, bo nowo wyliczony priorytet mógłby być większy niż priorytet innych procesów gotowych i oczekujących już przez dłuższy czas na procesor. W tradycyjnym systemie UNIX tego problemu unikało się w ten sposób, że co sekundę były przeliczane priorytety wszystkich procesów, a w wyniku tego przeliczenia karane były procesy, które dużo korzystały z procesora i nagradzana takie, które dłużej czekały.

W celu niedopuszczenia do głodzenia w systemie Linux stosowane są dwie kolejki priorytetowe. Jedna kolejka jest dla zadań, które mają prawo korzystać z procesora, zwanych zadaniami aktywnymi, a druga jest dla tzw. zadań przeterminowanych, które chwilowo wykorzystały już przydzielone im limity.

Podobnie, jak w systemie UNIX, w celu szybkiej identyfikacji pozycji niepustych w kolejkach priorytetowych, wykorzystywany jest wektor bitowy. W przeciwieństwie jednak do UNIXa, każdy bit odpowiada dokładnie jednej pozycji, czyli jednemu priorytetowi.

  • Tablica priorytetów dla zadań aktywnych — tablica kolejek procesów gotowych, które nie wykorzystały jeszcze kwantu czasu
  • Tablica priorytetów dla zadań przeterminowanych — tablica kolejek procesów gotowych, które wykorzystały kwant czasu
  • Mapa (maska) bitowa dla każdej z tablic, identyfikująca niepuste kolejki w tablicy priorytetowej

Wywłaszczenie


Jeśli przetwarzanie odbywa się w trybie jądra, to wywłaszczenie (przełączenie kontekstu) nie może nastąpić w dowolnym momencie, choć ogólnie jądro systemu Linux jest w pewnych warunkach wywłaszczalne. Wykrycie potrzeby przeszeregowania w trakcie wykonywania kodu jądra (np. w trakcie obsługi przerwania zegarowego) powoduje ustawienie znacznika need_resched i kontynuację przetwarzania w trybie jądra. Dopiero przy powrocie do trybu użytkownika następuje sprawdzenie znacznika podjęcia decyzji o przełączeniu kontekstu.

Wywłaszczenie nastąpi, gdy będzie gotowe zadanie o nie mniejszym priorytecie.

  • Wywłaszczenie procesu w trybie użytkownika może nastąpić przy powrocie z trybu jądra po obsłużeniu przerwania lub zakończeniu wywołania systemowego, gdy znacznik need_resched jest ustawiony.
  • Znacznik jest ustawiany w następujących przypadkach:
    • po upływie kwantu czasu bieżącego (wykonywanego) zadania.
    • po uzyskaniu gotowości przez zadanie o wyższym niż bieżące priorytecie.

Upłynięcie kwantu czasu


Przeliczenie priorytetu i związanego z nim kwantu czasu procesu następuje zaraz po upłynięciu kwantu czasu, a nie w wyniku specjalnej, okresowo uruchamianej procedury. Bardzo często jest tak, że nie wymaga się żadnych specjalnych przeliczeń. Priorytet i kwant czasu procesu pozostają bez zmian. Należy jednak zrobić coś z procesem, który wykorzystał swój kwant, a po przeliczeniu ma dość wyskoki priorytet, żeby dać szansę przetwarzania innym procesom o niższych priorytetach. W większości przypadków proces, który wykorzystał już swój kwant czasu, identyfikowany jest jako przeterminowany i trafia do odpowiedniej tablicy priorytetów. Procesy w tablicy priorytetów dla zadań przeterminowanych nie są uwzględniane przez planistę, jako kandydaci do przydziału procesora, do końca tzw. epoki .

W szczególnych przypadkach proces, który wykorzystał już swój kwant czasu, może trafić ponownie bezpośrednio do tablicy priorytetów dla zadań aktywnych. Zależy to od stopnia interaktywności zadania oraz stanu tablicy priorytetów dla zadań przeterminowanych. Jeśli nie ma zbyt długo oczekujących zadań przeterminowanych a stopień interaktywności wywłaszczanego procesu jest dostatecznie duży, po przeliczeniu priorytetu może on trafić na koniec kolejki właściwej dla swojego priorytetu w tablicy priorytetów dla zadań aktywnych.

Warto podkreślić, że proces, który zażąda operacji wejścia-wyjścia lub z innych powodów wejdzie w stan oczekiwania, nie traci swojego kwantu. Po uzyskaniu gotowości, ma szansę wykorzystać resztę przysługującego mu w danej epoce czasu procesora. Natomiast część kwantu czasu, pozostała do wykorzystania przez proces, jest dzielony na pół w momencie, gdy proces ten tworzy nowy proces (potomny). Połowa kwantu pozostaje więc do dyspozycji procesu macierzystego, a druga połowa jest początkowym kwantem czasu potomka.

  • Po upłynięciu kwantu czasu wykonywanego procesu zwykłego następuje przeliczenie jego priorytetu oraz wyznaczenie następnego kwantu czasu.
  • Jeśli proces charakteryzuje się dużym stopniem interaktywności, a w systemie nie ma zadań przeterminowanych jest on umieszczany na odpowiedniej pozycji w tablicy priorytetów dla zadań aktywnych, w przeciwnym przypadku umieszczany jest tablicy priorytetów dla zadań przeterminowanych.

Zmiana epoki


Zamiana tablic jest operacją bardzo szybką, gdyż polega na zamianie wartości dwóch wskaźników, wskaźnika na tablicę priorytetów dla zadań aktywnych i tablicę priorytetów dla zadań przeterminowanych. Wszystkie przeterminowane zadania stają się ponownie aktywne.

  • Jeśli tablica priorytetów dla zadań aktywnych jest pusta (wszystkie procesy gotowe wykorzystały swój kwant czasu), następuje zmiana epoki.
  • Zmiana epoki oznacza zamianę tablicy priorytetów: tablica priorytetów dla zadań przeterminowanych staję się tablicą dla zadań aktywnych i odwrotnie.

Zmiana priorytetów dynamicznych


Priorytet dynamiczny dotyczy procesów zwykłych. Dla procesów czasu rzeczywistego priorytet jest ustalony i ewentualnie modyfikowany w wyniku działań nadzorcy, a nie planisty.

W zależności od oceny interaktywności procesu, jego priorytet dynamiczny jest odpowiednio modyfikowany. Wyznaczenie kwantu czasu sprowadza się do przeskalowania wartości priorytetu dynamicznego z przedziału –20 – 19 (albo 100 do 139) na wartość kwantu czasu z przedziału 10 ms do 200 ms z uwzględnieniem proporcjonalności odwrotnej, gdyż mniejsza wartość priorytetu to wyższy poziom preferencji w dostępie do procesora.

  • Początkowy priorytet procesu zwykłego równy jest wartości nice.
  • Wartość priorytetu może zostać zmieniona następująco:
    • zwiększona o 5 dla zadań ograniczonych procesorem (obniżenia priorytetu),
    • zmniejszona o 5 dla zadań ograniczonych wejściem-wyjściem, rozumianych przez domniemanie jako interaktywne,
    • pozostać bez zmian.
  • Proporcjonalnie do priorytetu ustalana jest wielkość kwantu czasu (z zakresu od 10 ms do 200 ms, domyślnie 100 ms).

Ocena interaktywności


W czasie wykonywania procesu (gdy proces korzysta z procesora), każdy takt zegara powoduje zmniejszenie wartości zmiennej sleep_avg o 1. Po obudzeniu procesu w stanie oczekiwania wartość ta jest z kolei zwiększana o czas oczekiwania.

Określanie charakteru aplikacji na podstawie porównywania czasu wykorzystania procesora oraz oczekiwania na zakończenie operacji wejścia-wyjścia może niekiedy prowadzić błędów:

  • Przykład 1: aplikacja multimedialna. Zastosowania multimedialne wymagają na ogół sporej ilości czasu procesora, a mogą być wykorzystywane w bezpośredniej interakcji przez użytkownika.
  • Przykład 2: proces zarządzania bazą danych. Serwer bazy danych może spędzać dużo czasu w oczekiwaniu na wykonanie operacji dyskowych, ale nie wchodzi w bezpośrednią interakcję z użytkownikiem.
    • Miarą interaktywności jest względna długość okresów korzystania z procesora oraz przebywania w stanie oczekiwania.
    • Implementacją takiej koncepcji w systemie Linux jest atrybut procesu sfeep_avg, zmniejszany w czasie wykonywania procesu, a zwiększany po wyjściu ze stanu oczekiwania.
    • Wartość sfeep_avg zmienia się od 0 do MAX_SLEEP_AVG, a wartością domyślna jest 10 ms.

    Planowanie w klasie czasu rzeczywistego


    Planista nie modyfikuje priorytetu procesów czasu rzeczywistego. Jeśli proces taki nie zwolni procesora (i jądra) w wyniku wejścia w stan oczekiwania, wywłaszczenie może nastąpić tylko przez proces o wyższym priorytecie (czyli inny proces czasu rzeczywistego). W przypadku klasy SCHED_RR wywłaszczenie może też nastąpić po upływie kwantu czasu, gdy jest gotowy inny proces o tym samym priorytecie. Jeśli nie ma takiego procesu, proces dotychczas wykonywany otrzymuje kolejny kwant czasu i kontynuuje działanie. Nieodpowiednie użycie klasy priorytetów czasu rzeczywistego może więc skutkować zawłaszczeniem procesora.

    • Na danym poziomie priorytetu najpierw wybierane są procesy klasy SCHED_FIFO.
    • Proces klasy SCHED_FIFO wykonuje się tak długa, aż nie odda procesora lub nie pojawi się proces o wyższym priorytecie.
    • Proces klasy SCHED_RR wykonuje się podobnie jak proces klasy SCHED_FIFO, ale po upływie kwantu czasu oddaje zasoby innemu procesowi o tym samym priorytecie (jeśli taki proces istnieje).