Algorytm schedule()

Najważniejsze zmienne stosowane przez schedule():

• prev deskryptor procesu, który był do tej pory aktualny
• next na tą zmienną musi zostać zapisany wskaźnik do deksryptora procesu, który otrzyma procesor w wyniku szeregowania
• c priorytet znalezionego do tej pory najlepszego kandydata na przydział procesora

Algorytm:

1. Jeżeli jesteśmy w obsłudze przerwania to błąd.

   if (in_interrupt()) {
      printk("Scheduling in interrupt\n");
      BUG();
      return;;
   }
   

2. Jeżeli poprzedni proces był procesem czasu rzeczywistego Round Robin przerzuca się go na koniec kolejki oraz jeżeli potrzeba odnawia kwant czasu.

   if (prev->policy == SCHED_RR) {
     if (!prev->counter) {
       prev->counter = NICE_TO_TICKS(prev->nice)        
       move_last_runqueue(prev);
     }
   }
   

3. Jeżeli stan procesu jest różny od TASK_RUNNING to znaczy, że proces ma zostać zablokowany (=usunięty z runqueue). Jednak jeżeli proces jest w stanie TASK_INTERRUPTIBLE i ma jakieś nie obsłużone sygnały, to daje się mu szansę je obsłużyc.

   switch (prev->state) {
     case TASK_INTERRUPTIBLE:
       if (signal_pending(prev)) {
         prev->state = TASK_RUNNING;
         break;
       }
     default:
       del_from_runqueue(prev);
     case TASK_RUNNING:;
   }
   

4. Czyszczenie pola need_resched

    prev->need_resched = 0;
   

5. Pierwszym kandydatem na przydział procesora jest proces idle Ma on jednak bardzo niski priorytet - każdy inny proces z kolejki runqueue będzie miał wyższy priorytet

   next = idle_task(this_cpu);
   c = -1000;
   

6. Jeżeli proces ostatnio wykonywany jest dalej w trybie TASK_RUNNING to jest wybierany jako pierwszy kandydat do procesora zamiast procesu idle.

   if (prev->state == TASK_RUNNING) {
     c = goodness(prev, this_cpu, prev->active_mm);
     next = prev;
   }
   

7. Przeszukanie kolejki runqueue w poszukiwaniu procesu o najwyższym priorytecie. Procesowi temu zostanie przydzielony procesor.

   list_for_each(tmp, &runqueue_head) {
     p = list_entry(tmp, struct task_struct, run_list);
     int weight = goodness(p, this_cpu, prev->active_mm);
     if (weight > c)
     c = weight, next = p;
   }
   

8. Sprawdzenie czy nie zakonczyła się epoka. Jeśli tak, to przydzielenie wszystkim procesom nowych kwantów czasu.

   if (!c)
   {
     struct task_struct *p;
     for_each_task(p)
     p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
     <powrot do punktu 4>
   }
   

   Makro NICE_TO_TICKS jest zdefiniowane następująco:

   #define TICK_SCALE(x)	((x) >> 2)	/* dla procesorow i386 (gdy HZ = 100)*/
   #define NICE_TO_TICKS(nice)	(TICK_SCALE(20-(nice))+1)
   

   A więc może przyjąź wartości od 1 do 11.

9. Jeżeli nowowybrany proces jest tym samym procesem, który do tej pory był aktywny, to nic więcej już nie trzeba robić poza wyzerowaniem flagi SCHED_YIELD.

   if (prev == next) {
     prev->policy &= ~SCHED_YIELD;
     return;
   }
   

10. Rozpoczęcie przełączania procesów

    To zagadnienie jest szerzej omówione w osobnym referacie.