Linux

W Linuksie zastosowano jeden z wariantów kolejek priorytetowych ze sprzężeniem zwrotnym oraz mechanizm postarzania procesów.

Procesy podzielone są na trzy klasy (zob. 1.3). Procesy czasu rzeczywistego (klasy SCHED_RR i SCHED_FIFO) mają ustalone priorytety z zakresu od 0 do 99 i mają zawsze wyższy priorytet niż procesy zwykłe. Poniżej omówiony zostanie algorytm dla procesów zwykłych (klasa SCHED_OTHER).

Każdemu procesowi przypisane są następujące wartości:

• counter -- czas pozostały do wykorzystania. Jest to jednocześnie dynamiczny priorytet procesu, 0-80.
• upri -- statyczny priorytet procesu i jednocześnie długość kwantu czasu przyznawanego procesowi, 1-40.

Wartość pola counter jest podawana w jednostkach równych 1/100 s, zatem maksymalny kwant czasu do wykorzystania przez proces wynosi 800 ms. Procesy zasypiające oraz procesy budzone nie są nagradzane w żaden sposób.^5.2 Wszystkie procesy gotowe do wykonania są umieszczone na wspólnej liście. Każdy proces, który zużył swój kwant jest umieszczany na jej końcu:

linux_tqexpired(Process p) {
   move_last_runqueue(p);
     // uwaga: nowy kwant czasu 
     // przyznaje się w innym miejscu
     // zob. linux_select() i all_quanta_expired()
}

Do wykonania wybiera się pierwszy proces ze wszystkich gotowych o największej wartości pola counter:

Process linux_select() {
   Process p, found = NULL;
   int best_pri = -INF;

   for_each_ready_process(p) { // szukanie najlepszego procesu
      pri = p.counter;
         // przełączenie kontekstu też kosztuje,
         // więc nieznacznie promowany jest 
         // proces bieżący, o ile ma jeszcze kwant czasu
      if (p==current && pri>0)
           pri = pri + 1;
      if (pri>best_pri)
         best_pri = pri, found = p;
   }
   if ( best_pri==0 )
          // największy priorytet, czyli najdłuższy znaleziony
          // kwant czasu do wykorzystania jest równy 0, zatem
          // trzeba przyznać nowe kwanty
      all_quanta_expired();
   return found;
}

Jeśli wszystkie procesy gotowe do wykonania zużyły swoje kwanty czasu, to następuje przeliczenie priorytetów wszystkim procesom, także procesom śpiącym. Jest to sposób na postarzanie procesów i podwyższanie priorytetu procesom śpiącym:

all_quanta_expired() {
   for_each_process(p)
      p.counter = p.counter/2 + p.upri;
}

Wartość pola counter procesu p dąży do 2*p.upri.

Jeśli budzony jest proces o priorytecie większym niż proces bieżący, to następuje przeszeregowanie procesów:^5.3

linux_wakeup(Process p) {
   if ( p.counter > current.counter+3 ) // porównanie priorytetów
      need_resched = 1;   // ma zostać wywołana funkcja linux_select()
}

Dokładny opis działania modułu szeregującego Linuksa można znaleźć m. in. w [4], [8], [11], [12].

Największą zaletą algorytmu szeregowania w Linuksie jest jego prostota. Algorytm ten dosyć dobrze radzi sobie w środowisku mało obciążonym oraz pozwala programom zużywającym bardzo niewielkie kwanty czasu na krótkie czasy reakcji -- dzięki mechanizmowi postarzania.

Wadą powyższego algorytmu jest długi czas reakcji w środowisku obciążonym. W takim środowisku procesy zorientowane na wejście-wyjście i zużywające trochę większe kwanty czasu nie są odpowiednio szybko postarzane, przez co szybko spada ich priorytet. Przykładem może być serwer X-Windows, gdy trzeba odświeżyć duży obszar ekranu.

Algorytm Linuksa nie wykorzystuje mechanizmu podwyższania priorytetów procesom budzącym się. Wprowadzenie takiego mechanizmu mogłoby zwiększyć wydajność systemu kosztem skomplikowania kodu jądra.

Należy zaznaczyć, że algorytm Linuksa jest jednym z najprostszych algorytmów zaimplementowanych w dostępnych obecnie systemach operacyjnych. Spełnia on jednak wszystkie postulaty opisane na początku tego podrozdziału (zob.  tutaj).
 

1999-05-21