Szeregowanie procesów we współczesnych systemach operacyjnych

  1. Wprowadzenie
  2. Linux
  3. Windows
  4. Bibliografia




Wprowadzenie


Wśród procesów można wyróżnić dwie skrajnie przeciwne grupy:
 Charakterystyka tych grup:

Typ
 wykonują operacje I/O
 czekają w kolejce
 preferują przełączanie kontekstu
 preferują kwanty czasu
Procesy I/O-bound
 często
 często
 częste
 krótkie
Procesy CPU-bound
 rzadko
 rzadko
 rzadkie
 długie

Upodobania tych grup są sprzeczne, więc algorytm szeregujący nigdy nie będzie optymalny jednocześnie dla wszystkich procesów.


Linux


Cechy schedulera jądra 2.6

  1. wybór kolejnego procesu do wykonania w czasie stałym
  2. dobra skalowalność dla architekturach wieloprocesorowych
  3. rozważne równoważenie obciążenia dla systemów wieloprocesorowych
  4. doskonałe działanie aplikacji interaktywnych, nawet przy dużym obciążeniu systemu
  5. łatwe dostrajanie dla własnych potrzeb (np serwerów gdzie nie potrzebna dużej interaktywności)
  6. zagwarantowanie "sprawiedliwego" przydziału procesora - żaden proces nie powinien być głodzony

Podstawowe pojęcia

w jądrze 2.6 wyrówniamy dwie klasy procesów:
policy, priority, timeslice - te terminy oznaczają dokładnie to samo co w jądrze 2.4.
Trzeba jednak zapamiętać że w jądrze 2.6 dla wszystkich priorytetów:
MNIEJSZA wartość priorytetu = WAŻNIEJSZY proces




Strategie szeregowania


W jądrze 2.6, podobnie jak w 2.4 procesy mogą być szeregowane według trzech strategii.

#define SCHED_NORMAL        0
#define SCHED_FIFO        1
#define SCHED_RR       2

SCHED_NORMAL jest odpowidnikiem SCHED_OTHER z jądra 2.4.

Strategie szeregowania dla klas procesów:

Podział priorytetów


Wartość priorytetu to wartość z przedziału [0-139].
Procesy z priorytetem o mniejszej wartości priorytetu dostają procesor wcześniej.

Priorytety [0-99] są przeznaczone dla procesów RT.
Priorytety [100-139] są przeznaczone dla procesów zwyłych.

pp

Kwant czasu - timeslice


Zdefiniowane są następujące makro definicje dotyczące timeslice:
#define MIN_TIMESLICE        (10 * HZ / 1000)
#define DEF_TIMESLICE        (100 * HZ / 1000)
#define MAX_TIMESLICE       (200 * HZ / 1000)

HZ - częstotliwość zagara (tyknięć na sekundę).
JIFFY - jednostka czasu systemowego, 1 jiffy = przedział czasu odpowiadający 1/HZ
MIN_TIMESLICE - minimalny kwant jaki proces może otrzymać
MAX_TIMESLICE - maksymalny kwant jaki proces może otrzymać

Priorytety i kwanty czasu

Każdy proces zwykły posiada dwa priorytety:
priorytet statyczny (pole static_prio w struct task_struct)
priorytet dynamiczny (pole prio w struct task_struct)

Priorytet statczny

Priorytet statyczny procesu jest przechowywany w polu task_struct->static_prio. 
Scheduler nie zmienia tego priorytetu ale respektuje go. Zmienić go może użytkownik poprzez funkcję systemową nice(int).

Wartość nice [-20,19], domyślnie 0.
Wartość static_prio jest wyliczana według wzoru:

#define NICE_TO_PRIO(nice)    (MAX_RT_PRIO + (nice) + 20)

ns

Priorytet dynamiczny

Priorytet dynamiczny procesu jest przechowywany w polu task_struct->prio. 
Jest on oparty na priorytecie statycznym.
Priorytet ten jest używany wewnętrznie przez algoryrm schedulera, tak aby kolejność wykonywania procesów uwzględniała ich interaktywność.
Priorytet dynamiczny jest sumą priorytetu statycznego i pewnego bonusa, który zwiększa priorytet dynamiczny procesom interaktywnym a zmieniejsza procesom CPU-bound.
Bonus, który proces może otrzymać to wartość z przedziału [-5,5]. Procesy interaktywne mogą dostać bonus równy 5, wtedy wartość ich priorytetu zmaleje o 5 (będą ważniejsze).

Funkcja effective_prio

W funkcji effective_prio() wyliczany jest priorytet dynamiczny w taki sposób:
#define CURRENT_BONUS(p)    (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG)

static int effective_prio(task_t *p)
{
    int bonus, prio;

    if (rt_task(p))
        return p->prio;

    bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

    prio = p->static_prio - bonus;

    if (prio < MAX_RT_PRIO)
        prio = MAX_RT_PRIO;
    if (prio > MAX_PRIO-1)
        prio = MAX_PRIO-1;
     
    return prio;
}

Wartość zmiennej sleep_avg, determinuje bonus jaki zostanie przydzielony procesorowi.
Jej wartość odzwierciedla stosunek czasu [ wykonywania / oczekiwania ] procesu - co jest miarą jego interaktywności. Jak zmienia się sleep_avg opisane jest dalej.

Timeslice

Jest to kwant czasu przydzielony procesowi. Pamiętany jest w polu time_slice struktury task_struct. Obliczany jest w taki sposób:
#define BASE_TIMESLICE(p)    (MIN_TIMESLICE + ((MAX_TIMESLICE - MIN_TIMESLICE) * \
                                 (MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO-1)))

static unsigned int task_timeslice(task_t *p)
{
    return BASE_TIMESLICE(p);
}

st

Procesy z mniejszą wartością priorytetu statycznego, dostają procesor na dłużej.
Każdemu procesowi zostanie przydzielony procesor przynajmniej na okres MIN_TIMESLICE.

Struktury schedulera

Struktura prio_array


 struct prio_array {
    unsigned int nr_active;
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
 };

bm

Struktura runqueue

Z każdym procesorem jest związana jedna struktura runqueue.
W runqueue znajdują się procesy gotowe do wykonania.
Podstawowymi składowymi struktury runqueue są dwie tablice typu struct prio_array:

 

rq
struct runqueue {
    spinlock_t lock;

    unsigned long nr_running;
    unsigned long long nr_switches;
    unsigned long expired_timestamp;
    unsigned long nr_uninterruptible;

    task_t *curr;
    task_t *idle;
    struct mm_struct *prev_mm;
    prio_array_t *active;
    prio_array_t *expired;
    prio_array_t arrays[2];
    int best_expired_prio;
    atomic_t nr_iowait;

#ifdef CONFIG_SMP
    unsigned long cpu_load;

    struct sched_domain *sd;
 
    int active_balance;
    int push_cpu;
 
    task_t *migration_thread;
    struct list_head migration_queue;
#endif
 };


Interaktywność

Pole sleep_avg i obliczanie priorytetu dynamiczny


Jak wcześniej zostało powiedziane: wartość priorytetu dynamicznego zależy tylko od zmiennej sleep_avg, która jest miarą interaktywności procesu.
Najbardziej ogólnie: wartość jej jest równa stosunkowi długości dwóch przedziałów czasowych: [ile proces oczekiwał / ile proces się wykonywał].

Ponieważ w jądrze 2.4 gdy wszystkie procesy wykorzystały już swoje kwanty czasu scheduler 'przechodził' po liście wszystkich procesów, więc mógł aktualizował stan procesów oczekujących (w stanie UNITERRUPTIBLE lub INTERRUPTIBLE).
W jądrze 2.6 wszyskie operacje związane z szeregowaniem mają być wykonywane w czasie stałym, więc o przechodzeniu po wszystkich procesach nie ma mowy. Dlatego w task_struct'cie wprowadzono dodatkowe pola które opisują interaktywność procesu:

struct task_struct {
     ...
    unsigned long sleep_avg;
    long interactive_credit;
    unsigned long long timestamp;
    int activated;
    ...
}


wartość sleep_avg ulaga zmianom:
sl


W funkcji activate_task wywoływana jest procedura recalc_task_prio, która wyznacza nowy priorytet dynamiczny procesu.

Procedura recalc_task_prio

Procedura ta, aktualizuje pole sleep_avg procesu.
Zauważmy że procesowi nieinteraktywnemu, po obudzeniu nie należy zwiększać sleep_avg tak bardzo jak interaktywnemu, gdyż może to spowodować że procesy interaktywne będą musiały czekać aż ten (nieinteraktywny) skończy swój kwant czasu.
W strukturze task_struct znajduje się pole interactive_credit które odpowiada interaktywności procesy w długiej perspektywie. Wartość tego pola zmienia się tylko o jeden, a istotne wartości określają następujące makro dafinicje:
#define HIGH_CREDIT(p) \
    ((p)->interactive_credit > CREDIT_LIMIT)

#define LOW_CREDIT(p) \
    ((p)->interactive_credit < -CREDIT_LIMIT)


#define INTERACTIVE_SLEEP(p) \
    (JIFFIES_TO_NS(MAX_SLEEP_AVG * \
        (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))

Makro INTERACTIVE_SLEEP(p) definiuje, ile proces powinien spać, aby był uznany za proces interaktywny.

 W tej funkcji ustawiana jest wartość pola sleep_avg, oraz na podstawie jej nowej wartości wyliczany jest nowy priorytet dynamiczny procesu (prio):

  1. Obliczenie sleep_time - czas jaki spędził proces w kolejce
        unsigned long long __sleep_time = now - p->timestamp;
        unsigned long sleep_time;

        if (__sleep_time > NS_MAX_SLEEP_AVG)
            sleep_time = NS_MAX_SLEEP_AVG;
        else
            sleep_time = (unsigned long)__sleep_time;

  2. Sprawdzenie czy proces spełnia takie warunki (jeśli tak to jest uznawany za interaktywny):
            if (p->mm && p->activated != -1 &&
                sleep_time > INTERACTIVE_SLEEP(p))
  3. obliczenie nowego priorytetu dynamicznego prio.
    p->prio = effective_prio(p);



Warto przyjrzeć się warunkowi:
sleep_time > INTERACTIVE_SLEEP(p)
Ta nierówność nigdy nie będzie spełniona dla procesów z odpowiednim niskim priorytetem static_prio: [136-139] (nice
16-19), więc takie procesy nigdy nie będą traktowane jak interaktywne.

Szeregowanie


W jądrze 2.4 procedura schedule pełni dwie podstawowe funkcje:
W jądrze 2.6 zostało to rozdzielone:
W jądrze 2.4 kwant czasy jest wyliczany dopiero po zakończeniu epoki. Nie można tego robić odrazu - po wyczerpaniu przez proces kwantu czasu, gdyż wtedy nie dałoby się rozróżnić procesów które się jeszcze nie wykonywały, od tych które mają już nowy kwant czasu. W jądrze 2.6 odseparowano te dwie grupy, przechowując je w dwóch strukturach: tablica active i tablica expired.
Algorytm schedulra 2.6 polega na przekładaniu procesów z tablicy active do expired, a następnie gdy tablica active jest pusta to role tablic się zamienianiają.

Procedura schedule


wybór następnego procesu jest dokonywany w procedurze schedule:
wyznaczenie kolejnego procesu do wykonania jest wykonywane w czasie O(1)

dzięki strukturom schedulera znalezienie następnego procesu jest szybkie:
  1. na podstawie array->bitmap znajdowany jest indeks idx pierwszej niepustej listy procesów
  2. na zmienną queue przypisywana jest ta lista
  3. wyznaczany jest następny next proces do wykonania - pierwszy na tej liście
    typedef struct task_struct task_t;

    void schedule(){
    {
        ...
        task_t *next;
        prio_array_t *array;
        struct list_head *queue;
        int idx;
        ...
        array = rq->active;
        ...
        idx = sched_find_first_bit(array->bitmap);
        queue = array->queue + idx;
        next = list_entry(queue->next, task_t, run_list);
        ...
    }

Gdy tablica active jest już pusta to ... zamieniamy wskaźniki (active <-> expired):

    array = rq->active;
    if (unlikely(!array->nr_active)) {

        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO;
    }
 

Procedura scheduler_tick


 Jedną z kluczowych części kodu schedulera 2.6 to procedura scheduler_tick.
Procedura jest wywoływana przy każdym przerwaniu pochodzącym od zegara.

Początek kodu procedury to obsługa procesów RT, w przypadku:
void scheduler_tick(int user_ticks, int sys_ticks)
{
    ...
    if (unlikely(rt_task(p))) {

        if ((p->policy == SCHED_RR) && !--p->time_slice) {
            p->time_slice = task_timeslice(p);
            p->first_time_slice = 0;
            set_tsk_need_resched(p);

            dequeue_task(p, rq->active);
            enqueue_task(p, rq->active);
        }
        goto out_unlock;
    }
    ...
}

Zauważmy że jeśli proces ma wysoki priorytet(prio) (będzie wybrany do wykonania przed innymi) to w momencie gdy zostanie przełożony do kolejki expired nie dostanie już procesora przez długi czas (do momentu aż wszystkie aktywne procesy wyczerpią swoje stare kwanty czasu, tablica active będzie pusta i następi zamiana wskaźników na tablice).
Proces z wysokim prio to często proces interaktywny, dlatego jest to inaczej rozwiązane.

Do rozwiązania tego problemu w jądrze 2.6 służą:
  1. procesy interaktywne gdy wyczerpią swój kwant czasu, dostają nowy kwant czasu, i nowy priorytet, ale nie są przekładane do expired, a wkładane spowrtotem do active, jednak w taki sposób, aby nie głodzić innych procesów
  2. kwant procesów interaktywnych jest 'dzielony', tak że procesy nie wykorzystują całego kwantu od razu

Do tego celu zdefiniowane są następujące makra:

Makro TIMESLICE_GRANULARITY (rozdrabnianie kwant)
#ifdef CONFIG_SMP
#define TIMESLICE_GRANULARITY(p)    (MIN_TIMESLICE * \
        (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)) * \
            num_online_cpus())
#else
#define TIMESLICE_GRANULARITY(p)    (MIN_TIMESLICE * \
        (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)))
#endif

Dla procesu bardziej interaktywnego makro TIMESLICE_GRANULARITY zwraca mniejszą wartość.
TIMESLICE_GRANULARITY(p) określa na jakie porcje należy podzielić kwant procesu.

Makro TASK_INTERACTIVE


 Makro rozstrzygające czy proces jest interaktywny:
#define TASK_INTERACTIVE(p)       ((p)->prio <= (p)->static_prio - DELTA(p))

dt
#define DELTA(p)                              (SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA)
#define SCALE(v1,v1_max,v2_max)  (v1) * (v2_max) / (v1_max)
#define INTERACTIVE_DELTA         2


Nierówność makra TASK_INTERACTIVE(p) jest łatwiejsza do spełnienia dla procesów z wyższym priorytetem statycznym. Warto zauważyć że makro opiera się na priorytecie dynamicznym, dlatego ten sam proces może być raz uznany za interaktywny, a innym razem za nieinteraktywny.

Makro EXPIRED_STARVING

Makro rozstrzgające czy procesy w kolejce expired głodują.
#define EXPIRED_STARVING(rq) \
    ((STARVATION_LIMIT && ((rq)->expired_timestamp && \
        (jiffies - (rq)->expired_timestamp >= \
            STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
            ((rq)->curr->static_prio > (rq)->best_expired_prio))


STARVATION_LIMIT jest stałą.
rq->expired_timestamp wartość tego pola:
 jiffies zwraca aktualny czas systemowy.


Najbardziej istotne są dwa warunki:
(jiffies - (rq)->expired_timestamp >= \
            STARVATION_LIMIT * ((rq)->nr_running) + 1)))

sprawdzenie czy najdłużej przebywający proces w tablicy expired, nie przebywa tam zbyt długo (w zależności od liczby procesów gotowych do wykonania w całej kolejce)
(rq)->curr->static_prio > (rq)->best_expired_prio)

wartość rq->best_expired_prio jest równa maksymalnej wartości priorytetu statycznego procesu przebywającego w expired. To makro powoduje uwzględnienie preferencji użytkownika. Priorytet o niższym priorytecie statycznym nigdy nie będzie włożony ponownie do activeexpired, jeśli w expired znajduje proces o wyższym priorytecie statycznym - niezależnie od ich priorytetów dynamicznych.


Dalsza część kodu scheduler_tick wykorzystuje te makra:
  1. kwant czasu zostaje zmniejszony i sprawdzony zostaje warunek czy procesowi skończył się jego kwant czasu:
    if (!--p->time_slice)

    1. tak:
      1. usunięcie procesu z kolejki
      2. ustawiona zostaje flaga need_resched
      3. przypisany zostaje procesowi nowy priorytet dynamiczny i nowy kwant czasu
      4. jeśli pole rq->expired_timestamp nie zostało jeszcze ustawione (obsługujemy pierwszy proces od zamiany wskaźników) to przypisujemy na to pole aktualny czas
      5. jeśli proces nie jest interaktywny lub procesy w expired są głodzone to proces trafia do tablicy expired wpp trafia do tablicy active
        {
                dequeue_task(p, rq->active);
                set_tsk_need_resched(p);
                p->prio = effective_prio(p);
                p->time_slice = task_timeslice(p);

                p->first_time_slice = 0;

                if (!rq->expired_timestamp)
                    rq->expired_timestamp = jiffies;

                if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
                    enqueue_task(p, rq->expired);
                    if (p->static_prio < rq->best_expired_prio)
                        rq->best_expired_prio = p->static_prio;
                } else
                    enqueue_task(p, rq->active);
        }



    2. nie:
      1. sprawdzamy czy proces jest interaktywny i czy jego kwant czasu powinien być dzielony
        1. jeśli tak: przekładamy go do odpowiedniej kolejki i ustawiamy flagę NEED_RESCHED
        2. jeśli nie: proces będzie się dalej wykonywał
          {
                   if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
                      p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
                      (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
                      (p->array == rq->active)) {

                      dequeue_task(p, rq->active);
                      set_tsk_need_resched(p);
                      p->prio = effective_prio(p);
                      enqueue_task(p, rq->active);
          }

Funkcja systemowa sys_sched_yield


Funkcja sched_yield pozwala procesowi zrezygnować z procesora.
W jądrze 2.4 wywołanie tej funkcji powoduje:
 W jądrze 2.6 jest inaczej:

sc

Szeregowanie globalne

Scheduler 2.6 pozwala szeregować procesy nie tylko dla maszyn jednoprocesorowych. Możliwe jest szeregowanie procesów na:

Struktury danych

W kodzie planisty używane są dwie struktury związane z globalnym szeregowaniem procesów:

nm

Struktura sched_domain


Struktury sched_domain tworzą hierarchię odpowiadającą architekturze komputera. Obiekty znajdujące się wyżej w hierarchii zawierają informacje dotyczącą większej liczby procesorów.
struct sched_domain {
    struct sched_domain *parent;
    struct sched_group *groups;  
    cpumask_t span;        
    unsigned long min_interval; 
    unsigned long max_interval;  
    unsigned int busy_factor; 
    unsigned int imbalance_pct;   
    unsigned long long cache_hot_time;
    unsigned int cache_nice_tries;  
    unsigned int per_cpu_gain;  
    int flags; 

    unsigned long last_balance; 
    unsigned int balance_interval; 
    unsigned int nr_balance_failed;
};
   
Najważniejsze pola:
 pozostałe pola odpowiadają za politykę szeregowania tej domeny:

Struktura sched_group


Struktura reprezentuje grupy procesorów, wchodzących w skład domeny, jest wykorzystywana przy równoważeniu obciążenia w ramach domeny. Równoważenie obciązenia w domenie polega na równoważeniu obciążenia między grupia tej domeny.
struct sched_group {
   struct sched_group *next; /* Must be a circular list */
   cpumask_t cpumask;
   unsigned long cpu_power;
};


Procedura rebalance_tick

W scheduler_tick wywoływana jest funkcja rebalance_tick, która ma sprawdzić czy potrzebne jest zrównoważenie obciążenia.
Funkcja ta uaktualnia this_rq->cpu_load, i przechodzi po wszystkich domenach w górę hierarchii, sprawdzając jak długo nie było wykonywane zrównoważenie. Jeśli wystarczająco długo, to wywoływana jest funkcja load_balance dla tej domeny.

Funkcja load_balance

Funkcja ta wykonuje równoważenie grup w domenie.
Równoważenie grup polega na znalezieniu najbardziej obciążonej grupy (w ramach domeny). Jeśli jest to grupa do której należy procesor wykonujący ten kod to równoważenie nie jest wykonywane, wpp znaleziona zostaje najbardziej obciążona kolejka w tej najbardziej obciążonej grupie. Z tej znalezionej kolejki zostają przeniesione zadania do obecnej kolejki (związanej z procesorem który wykonuje ten kod), o ile spełniają odpowiednie warunki - funkcja move_tasks.
  1. w ramach domeny zostaje znaleziona najbardziej zajęta grupa:
        group = find_busiest_group(sd, this_cpu, &imbalance, idle);

  2. wśród kolejek (procesorów) należących do tej grupy zostaje znaleziona najbardziej zajęta kolejka:
        busiest = find_busiest_queue(group);

  3. jeśli w znalezionej kolejce są procesy to:
  4. jeśli nie udało się przenieść żadnego procesu, to zostaje obudzony wątek systemowy (migration_thread). Wcześniej zostają ustwione informacje (flaga busiest->active_balance, busiest->push_cpu) dla tego wątku.
        if (!nr_moved) {
        ...
                spin_lock(&busiest->lock);
                if (!busiest->active_balance) {
                    busiest->active_balance = 1;
                    busiest->push_cpu = this_cpu;
                    wake = 1;
                }
                spin_unlock(&busiest->lock);
                if (wake)
                    wake_up_process(busiest->migration_thread);
        ...
        }

Funkcja move_tasks


static int move_tasks(runqueue_t *this_rq, int this_cpu, runqueue_t *busiest,
              unsigned long max_nr_move, struct sched_domain *sd,
              enum idle_type idle)

Przenosi maksymalnie max_nr_move procesów z kolejki busiest do this_rq. Przenoszenie procesu jest drogie (np. utrata cache'u), dlatego funkcja move_tasks rozpatruje je w odpowiedniej kolejności, i przenosi tylko te spełniające pewne warunki.
  1. wybierana jest tablica z której będą przenoszone procesy: jeśli jest jakikolwiek proces w expired to wybierana jest tablica expired, wpp wybierana jest active. Preferowana jest tablica expired, gdyż jest duże prawdopodobieństwo, że w cache'u nie ma już zasobów procesów znajdujących się w tej tablicy.
  2. najpierw rozpatrywane są procesy z większym priorytetem (ważniejsze), jeśli proces:
  3. dopóki nie zostanie przeniesione max_nr_move powtarzane są kroki 2,3.
  4. jeśli zostało przeniesionych mniej niż max_nr_move procesów, była używana tablica expired, i tablica active nie jest pusta to wykonywane są kroki od 2, ale używając tablicy active.

Skalowalność

    W jądrze 2.4 jest jedna wspólna kolejka wszystkich procesów:
    W jądrze 2.6 każdy procesor ma własną kolejkę procesów, a globalne szeregowanie polega na równoważeniu obciążenia procesorów. Interakcja między procesorami jest niewielka, dlatego skalowalność jest dobra.

sc
   
      


Testy: 2.4 vs 2.6

Hackbench

1w
8w

Skalowalność


g18

t9





Windows

Podstawowe pojęcia

Proces

Proces to kontener z zasobami używanymi podczas wykonywania instancji programu. Na najwyższym poziomie abstrakcji można powiedzieć, że składa się on z:

Wątek

Wątek to jednostka w ramach procesu jaką Windows szereguje wśród zadań wykonawczych. Wątek musi zawierać: Rejestry, stosy i TLS są nazywane kontekstem wątku a ich postać zależy silnie od platformy, na jakiej jest zainstalowany Windows. Informację o kontekście uzyskujemy funkcją z WinAPI GetThreadContext.

Włókno


Włókno bywa nazywane lekkim wątkiem i pozwala aplikacji na szeregowanie włąsnych wątków samodzielnie zamiast zdawać się na globalny scheduler. Włókna są niewidzialne dla kernela ponieważ działają wyłącznie w trybie użytkownika. W odróżnieniu od wątku włókno nie zaczyna się od razu wykonywać po utworzeniu - musi być uruchomione.

Zadanie

Nazywalny i zabezpieczalny obiekt, do którego dostęp może być dzielony. Ma on na celu kontrolę określonych atrybutów procesów związanych z tym obiektem i jego podstawową funkcjonalnością jest umożliwienie operowania na grupach procesów jak na jedności. Obiekt ponadto rejestruje podstawowe statystyki i informacje związane ze zgrupowanymi w nim procesami.

Anatomia procesu

Struktury danych

Główną strukturą związaną z procesem jest blok EPROCESS. Jest on wraz ze związanymi z nim strukturami (oprócz PEB - process environment block) przechowywany w pamięci systemowej. PEB jest przechowywany w przestrzeni adresowej procesu, ponieważ zawiera informacje modyfikowane przez działający w trybie użytkownika kod. Oprócz tego windowsowski proces zarządzający procesami i konsolą (Csrss) utrzymuje dodatkową strukturę dla każdego procesu (KPROCESS block = PCB) i moduł zarządzający wykonywaniem kodu w trybie jądra (Win32k.sys) także utrzymuje pewną strukturę, tworzoną w momencie wywołania przez wątek funkcji zaimplementowanej w jądrze.

Uproszczony schemat EPROCESS block:

eprocess

Uproszczony schemat KPROCESS block:

kprocess

Uproszczony schemat PEB:
peb 
Zmienna Typ Opis
PsActiveProcessHead Głowa kolejki Głowa listy bloków procesów.
PsIdleProcess EPROCESS Blok procesu idle
PsInitialSystemProcess Wskaźnik na EPROCESS Wskaźnik na blok procesu inicjacyjnego, zawierającego wątki systemowe.
PspCreateProcessNotifyRoutine Tablica wskaźników Tablica wskaźników wywoływanych przy tworzeniu/kasowaniu procesu.
PspCreateProcessNotifyRoutineCount DWORD Liczba zarejestrowanych procedur powiadamiania procesu.
PspLoadImageNotifyRoutine Tablica napisów Tablica napisów do procedur wywoływanych przy ładowaiu obrazu.
PspLoadImageNotifyRoutineCount DWORD Liczba zarejestrowanych procedur ładowania obrazu.
PspCidTable Wskaźnik do HANDLE_TABLE Tablica odnośników do ID procesów i wątków.


Niektóre liczniki wykonawcze

Nie wymieniono związanych z pamięcią i obsługą I/O.
Obiekt: licznik Funkcja
Process: % Privileged Time Procent czasu jaki wątki tego procesu działają w trybie jądra w określonym przedziale czasu.
Process: % Processor Time Procent czasu procesora, jaki zużyły wątki tego procesu (suma Privileged Time i User Time)
Process: % User Time Procent czasu jaki wątki tego procesu działają w trybie użytkownika w określonym przedziale czasu.
Process: Elapsed Time Czas od momentu utworzenia procesu.
Process: ID Process Identyfikator procesu.
Process: Creating Process ID ID procesu-rodzica.
Process: Thread Count Liczba wątków w procesie.
Process: Handle Count Suma wszystkich odnośników otwartych w ramach procesu.

Związane z procesami funkcje WinAPI

CreateProcess, CreateProcessAsUser, CreateProcessWithLogonW, CreateProcessWithTokenW, OpenProcess, ExitProcess, TerminateProcess, FlushInstructionCache, GetProcessTimes, GetExitCodeProcess, GetCommandLine, GetCurrentProcess, GetCurrentProcessId, GetProcessVersion, GetStartupInfo, GetEnvironmentStringsm, GetEnvironmentVariable, Get/SetProcessShutdownParameters, GetGuiResources.

Anatomia wątku

Struktury danych

Na poziomie systemu operacyjnego wątek jest reprezentowany przez executive thread (ETHREAD) block. Jest on wraz ze związanymi z nim strukturami (oprócz TEB - thread environment block) przechowywany w pamięci systemowej. TEB jest przechowywany w przestrzeni adresowej procesu, ponieważ zawiera informacje modyfikowane przez działający w trybie użytkownika kod. Oprócz tego windowsowski proces zarządzający procesami i konsolą (Csrss) utrzymuje dodatkową strukturę dla każdego procesu (KTHREAD block ) i moduł zarządzający wykonywaniem kodu w trybie jądra (Win32k.sys) także utrzymuje pewną strukturę ( W32THREAD), tworzoną w momencie wywołania przez wątek funkcji zaimplementowanej w jądrze i wskazywaną przez ETHREAD.

Uproszczony schemat ETHREAD block:

ethread

Uproszczony schemat KTHREAD block:
kthread

Uproszczony schemat TEB block:
TEB

Zmienne jądra

Zmienna Typ Opis
PspCreateThreadNotifyRoutine Tablica wskaźników. Tablica funkcji uruchamianych przy rozpoczęciu/zakończeniu wątku.
PspCreateThreadNotifyRoutineCount DWORD Liczba zarejestrowanych funkcji do obsługi powiadamiania..
PspCreateProcessNotifyRoutine Tablica wskaźników. Wskaźniki wskazują na procedury uruchamiane podczas tworzenia i kończnia procesu.


Niektóre liczniki wykonawcze


Obiekt: licznik Funkcja
Process: Priority Base Zwraca priorytet podstawowy (nowe wątki są z takim tworzone) procesu.
Thread: % Privileged Time Procent czasu jaki wątkek ten działa w trybie jądra w określonym przedziale czasu.
Thread: % Processor Time Procent czasu procesora, jaki zużył ten wątek (suma Privileged Time i User Time).
Thread: % User Time Procent czasu jaki wątkek tego procesu działaja w trybie użytkownika w określonym przedziale czasu.
Thread: Context Switches/Sec Zwraca liczbę przełączeń kontekstu na sekundę.
Thread: Elapsed Time Czas od momentu utworzenia wątku.
Thread: ID Thread Czas od momentu utworzenia procesu.
Thread: ID Process Identyfikator wątku.
Thread: Priority Base Aktualny priorytet podstawowy.
Thread: Priority Current Obecny dynamiczny priorytet wątku.
Thread: Start Address Początkowy adres wirtualny wątku.
Thread: Thread State Liczba 0-7 opisująca aktualny stan wątku.
Thread: Thread Wait Reason Liczba 0-19 uzasadniająca aktualny stan wątku.

Związane z wątkami funkcje WinAPI

CreateThread, CreateRemoteThread, OpenThread, ExitThread, TerminateThread, GetExitCodeThread, GetThreadTimes, GetCurrentProcess, GetCurrentProcessId, GetThreadId, Get/SetThreadContext, GetThreadSelectorEntry.

Szeregowanie wątków

Przegląd

Windows implementuje system szeregujący oparty na priorytetach, wywłaszczający, gwarantujący najbardziej uprzywilejowanemu gotowemu priorytetowi dostęp do procesora, z takim zastrzeżeniem, że wątek wybrany do obsługi może być ograniczony przez dostępność preferowanych/dozwolobych procesorów (zjawisko zwane powinowactwem).Domyślnie każdy wątek może być obsługiwany przez każdy procesor, ale można to ustawienie zmienić za pomocą SetThreadAffinityMask lub SetProcessAffinityMask bądź ustawiając maskę powinowactwa w nagłówku obrazu w strukturze PEB.

Gdy wątek otrzymuje przydział procesora, może działać przez kilka jednostek czasu, nazwanych kwantem. Po tym czasie inny wątek o tym samym priorytecie otrzymuje przydział. Ze względu na własność wywłaszczania (gdy dochodzi wątek o wyższym priorytecie), może się zdarzyć, że wątek nie wykorzysta swojego kwantu albo nawet go nie napocznie!

Kod szeregujący wątki w Windowsie jest zaimplementowany w kernelu. Nie ma procedury czy modułu, który możnaby nazwać schedulerem - kod jest rozproszony po całym jądrze. Procedury realizujące funkcjonalność szeregowania nazywane są zbiorczo schedulerem, któy korzysta z "dyspozytorium" (dispatcher database). Zmiana obsługiwanego wątku wiąże się ze zmianą kontekstu i zachowywaniem np. rejestrów procesora.

Szeregowanie dotyczy wątków. Procesy są traktowane jako kontenery z zasobami i przy przydziale mocy obliczeniowej wątkom nie ma znaczenia jakich procesów są to wątki.

Poziomy priorytetów

Jądro Windowsa rozróżnia 32 poziomy priorytetów (im większa liczba tym większa ważność):
thr1
Mamy zatem 16 poziomów czasu rzeczywistego, 15 poziomów zmiennych i jeden poziom systemowy(zero page thread - wątek trybu kernel-mode (wątek nr 0 w procesie System), zerujący określone strony pamięci).
Generalnie występują 2 perspektywy: priorytety WinAPI i jądra systemu. WinAPI wpierw dzieli procesy według klas, do jakich należą w momencie stworzenia (Real-time, High, Above Normal, Normal, Below Normal i Idle), a następnie według względych priorytetów poszczególnych wątków w tych procesach (Time-critical, Highest, Above-normal, Normal, Below-normal, Lowest i Idle). thr2
Podczas gdy proces ma pojedynczą podstawową wartość priorytetu, wątek ma dwie: obecną i podstawową. Szeregownaie jest czynione w oparciu o obecną. System może przejściowo zwiększać priorytety w zakresie priorytetów zmiennych, natomiast priorytety czasu rzeczywistego są stałe czyli proces ma taki sam priorytet podstawowy jak i obecny.
Podstawowy priorytet wątku jest dziedziczony po podstawowym priorytecie procesu, a proces domyślnie dziedziczy po podtsawowym priorytecie procesu tworzącego, choć można nakazać podczas tworzenia przyjąć inny priorytet.

Poziomy przerwań vs. poziomy priorytetów

Windows wprowadza także priorytety przerwań (Interrupt Request Levels = IRQLs), co schematycznie przedstawiono na poniższych rysunkach:
irqls_x86

irqls_x64
W lewej kolumnie są priorytety wątków (im większa liczba tym większa ważność priorytetu). Jak widać, zwykle są one uruchamiane na poziomie IRQL 0 lub 1 (wątki z trybu user-mode zawsze mają priorytet 0). Tylko asynchroniczne wywołania procedur w trybie kernel-mode operują na poziomie 1 i w razie potrzeby mogą zwiększyć IRQL np. w celu wykonania funkcji systemowej związanej z szeregowaniem wątków.

Stany wątków

Na poniższym schemacie pokazano możliwe stany, w jakich może być wątek w systemie Windows 2000/XP:
ts
Kolejne stany to:
Diagram stanów dla systemu Windows Server 2003 jest ukazany poniżej. Główna różnica w porównaniu z poprzednim to stan deferred ready, używany do procesów wybranych do działania na konkretnym procesorze, lecz jeszcze nie zaszeregowanych (minimalizacja czasu blokady dyspozytorium).
ts2

Dyspozytorium

W celu podejmowania decyzji związanych z szeregowaniem wątków, jądro utrzymuje zbiór danych nazywanych zbiorczo dyspozytorium. Służy ono do zapamiętywania, które wątki czekają na wykonanie i który procesor wykonuje jaki wątek.
dsp

W systemie Windows Server 2003 każdy procesor ma własną kolejkę:
dsp2

Ready queues (KiDispatcherReadyListHead) zawierają wątki w stanie Ready, czekające na uszeregowanie do wykonania. Istnieje osobna kolejka dla każdego z priorytetów. Aby przyspieszyć wybór wątku do wykonania bądź wywłaszczenia, Windows utrzymuje 32-bitową maskę (KiReadySummary), gdzie każdy bit oznacza czy jest coś w kolejce o tym priorytecie.

Zmienne jądra

Zmienne systemowe trybu kernel-mode związane z szeregowaniem na systemach jednoprocesorowych:
Zmienna Typ Opis
KiReadySummary Maska (32 bity) Maska poziomów priorytetów mających co najmniej jeden wątek.
KiDispatcherReadyListHead Tablica 32 list Głowy kolejek.

Kwanty czasu

Kwant czasu jest to ilość jednostek czasu, jaką wątek otrzymuje na wykonanie zanim zanim Windows sprawdzi czy istanieje inny wątek o tym samym priorytecie oczekujący na wykonanie. Gdy nie ma, wątek otrzymuje kolejny kwant i wykonuje się dalej. W Windows 2000 Professional i XP wątek wykonuje się domyślnie przez 2 przedziały czasowe, zaś w Windows Server przez 12 - oszczędza się na zmianie kontekstu. Długość przedziału zależy od platformy i Hardware Abstrat Layer a nie jądra systemu. Dla większości systemów x86 jednoprocesorowych jest rzędu 10ms, a dla wieloprocesorowych rzędu 15ms.

Kwantowa rachunkowość

Każdy wątek ma kwant zapamiętywany w kernel precess block i w każdym nowym interwale czasowym jest on zmniejszany. Wewnętrznie, jednostka czasu jest trzymana potrojona tj. Windows 2000/XP mają kwant 6=2*3, Zś Windows Server 36=12*3. Przerwanie zegara wywołuje procedurę zmniejszjącą kwant o 3. Powód tej komplikacji to np. możliwość zmniejszania kwantu o 1 jednostkę przy funkcji typu wait u procesów mających priorytet aktualny mniejszy niż 16 i podstawowy mniejszy niż 14 - w ten sposób tylko oczekując stracą one swój kwant.

Zwiększanie kwantowości

Aż do Windows NT 4.0 proces przechodzący na pierwszy plan miał zwiększany priorytet o 2 i wzrost ten utrzymywał się do czasu gdy choć jeden wątek tego procesu był operował w oknie pierwszoplanowym. Powodowało to czasem nieporządane głodzenie ważnych procesów działąjących w tle.W Windows NT 4.0 Workstation wprowadzono inne roziwązanie - potrojenie kwantu czasu dla procesów pierwszoplanowych.
Roziązanie to jest stosowane w przypadku ustawienia optymalizacji w "Performance Options" na Programs/Applications, nie zaś na (domyślną dla Windows Server) Background Services.

Ustawienia kwantowości

Typowo proces pierwszoplanowy dostaje 3 razy większy kwant czasu niż proces działający w tle. TO ustawienie można jednak zmienić w Rejestrze: klucz HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\Win32PrioritySeparation składa się z 3 dwubitowych pól (od lewej):
  1. short/long - 1 - long, 2 - short, 0/3 - default (long dla W2003, short dla W2k, WXP);
  2. variable/fixed - czy zmieniać kwanty dla procesów pierwszoplanowych (1 - tak, 2 - nie, 0/3 - default - fixed dla W2003, variable dla W2k, WXP);
  3. foreground quantum boost - (wartość przechowywana w zmiennej jądra PsPrioritySeparation) wartosci 0, 1, 2 indeksujące tablicę PspForegroundQuantum używaną przy przydzielaniu kwantów procesom pierwszoplanowym (pierwsza pozycja w tablicy odpowiada wartości kwantu dla procesów drugoplanowych);
Można wybierać pomiędzy kwantami 2-jednostkowymi a 12-jednostkowymi także za pomocą ustawień przez okienka dialogowe. Np. w W2k My Computer>Properties>Advanced tab>Performance Options, ześ w Windows 2003/XP: My Computer>Properties>Advanced tab>Performance section>Settings>Advanced tab>Processor Scheduling.

Taktyki szeregowania

Dobrowolne przełączenie

Wątek może zwolnić dobrowolnie procesor przez przejście w stan oczekiwania na coś dzięki użyciu funkcji typu wait. Kwant czasu dla procesu nie jest resetowany tylko zmniejszany o 1/3 kwantu (tj. 1 jednostkę - pamietamy, że wewnętrznie kwant składa się z 3 jednostek).
svo

Wywłaszczenie

W tym scenariuszu wątek jest wywłaszczany, gdyż skończyło się oczekiwanie wątku o wyższym priorytecie lub zostały dokonane odpowiednie zmiany w priorytetach wątków. Wątki z trybu user-mode mogą wywłaszczać także te z trybu kernel-mode. Decydujący jest priorytet. Wywłaszczony wątek jest umieszczany na początku stosownej kolejki:
spr

Koniec przydzielonego kwantu

Gdy wątkowi aktywnemu skończy się kwant, Windows określa czy jego priorytet nie powinien ulec zmniejszeniu i czy inny wątek ma byc zaszeregowany do procesora. se

Zakończenie

Gdy wątek kończy działanie jest usuwany z kolejki wątków. Jeśli nie ma otwartych dowiązań, to wszsytkie struktury z nim związane są deallokowane.

Przełączanie kontekstu

Zmienianie kontekstu zależy od architektury komputera, ale typowo wymaga zapisywania i ładowania następujących danych: wskaźnika instrukcji, wskaźników na stosy jądra i urzytkownika powiązane z wątkiem, wskaźnika do przestrzeni adresowej, w któejj działa wątek (process's page table directory). Jądro zapisuje te informacje ze starego procesu zapisując je w starym procesie (na stosie kernel-mode i uaktualniając stary KTHREAD block). Gdy nowy wątek jest w innym procesie, ładuje adresy z page table directorydo specjalnengo rejestru procesora, aby uzyskać jego (wątku) przestrzeń adresową.

Zwiększanie priorytetów

W pięciu przypadkach Windows może zwiększyć priorytet wątku:
  1. Po zakończeniu operacji I/O
    Wartość zwiększenia priorytetu jest ustalana przez stareownik urządzenia i zwiększenie jest aplikowane do priorytetu podstawowego. Po wyczerpaniu przydziału czasu priorytet zmniejsza się o 1 i cały cykl powtarza się aż do osiągnięcia przez proces priorytetu podstawowego.
    svv
  2. Po odczekaniu na zdarzenie bądź semafor.
    Wątek, który oczekiwał na zdarzenie bądź semafor ma zwiększany priorytet o 1 (względem podstawowego), przy czym stosuje się to do wątków o priorytetach aktualnych <15. Po upływie przydzielonego czasu priorytet zmniejsza się.
    Specjalne zwiększenie stosuje się w przypadku wydarzeń opisanych przez funkcję NtSetEventBoostPriority i KeSetEventBoostPriority. Może być ono w pewnych sytuacjach większe, ale jest anulowane po upłynięciu przydziału czasu (dodatkowo jeśli kwant czasu wątku był <4, jest on zwiększany do 4).
  3. Gdy proces z pierwszego planu zakończył funkcję typu wait.
    Zwiększenie to wynosi tyle, ile aktualna wartość PsPrioritySeparation i ma na celu zwiększenie interaktywności systemu.
  4. Gdy wątki GUI sie budzą z powodu aktywności okienek.
    Wątki wybudzane z powodu aktywności okienka otrzymują zwiększenie priorytetu o 2 - ma to na celu zwiększenie interaktywności.
  5. Proces gotowy do działania nie działał od dłuższego czasu.
    Aby w takiej sytuacji zapobiec głodzeniu, raz na sekundę wątek systemowy balance set manager przegląda kolejki procesów gotowych i jeśli znajdzie proces czekający od ok. 4s, zwiększa jego priorytet do wartości 15. Na Windows 2000/XP wartość kwantu czasu takiego procesu podwaja się, natomiast na Windows Server 2003 jest ustawiana na 4 jednostki - po upływie przydziału kwantowość i priorytety są przywracane do poprzednich wartości. W jednym przebiegu balance set manager skanuje co najwyżej 16 elementów kolejki ready i doładowuje co najwyżej 10 wątków. Gdy nie oznacza to sprawdzenia całej kolejki, zapamiętuje gdzie skończył i przy następnym przebiegu zaczyna od nowego miejsca.

Systemy wieloprocesorowe

Na systemach jednoprocesorowych mamy zagwarantowane, że wątek o najwyższym priorytecie będzie wykonywany. Na systemach wieloprocesorowych, że będzie wykonywany gdzieś (nie koniecznie zostaną uwzględnione preferencje).

Wieloprocesorowe dyzpozytorium

W systemach W2k i WXP są 2 wirujące blokady, natomiast w Windows Server każdy procesor ma swoją tablicę list i nie ma potrzeby unikać konfliktu z dostępem do niej. Sama struktura dyspozytorium została przedstawiona wcześniej. W Windows Server 2003 poprawiono także mechanizmy zmiany kontekstu w stosunku do Windows 2000/XP.

Procesory wielowątkowe

Gdy wybierany jest procesor do obsługi wątku, jeśli istnieje procesor fizyczny mający wszystkie procesory logiczne niezajęte, wybierany jest właśnie ten procesor do obsługi wątku. Ponadto, procesory logiczne w przeciwieństwie do fizycznych nie są liczone w warunkach licencyjnych firmy Microsoft (Windows XP Home Edition obsługuje 1 procesor fizyczny, ale gdy jest on wielowątkowy, mechanizm ten zostnie użyty).

Systemy NUMA

W systemie NUMA (nonuniform memory access), obsługiwanym przez Windows XP i Windows Server 2003, procesory są grupowane w jednostki nazywane węzłami. Każdy węzeł ma własne procesory i dodatkową pamięć, dużo szybszą w dostępie od ogólnodostępnej. Jądro przechowuje informacje o węźle w strukturze KNODE., zaś wskaźniki na te struktury są w tablicy KeNodeBlock. Aplikacje optymalizowane pod NUMA działające pod Windows ustawiają procesowi powinowactwo tak, by możliwie ograniczyć jego wykonanie do pojedynczego węzła.

Powinowactwo (affinity)

Każy wątek ma maskę powinowactwa, określającą dozwolone dla niego procesory. Jest ona dziedziczona po procesie i może być zmieniania przez aplikację dla lepszego wykonywania wątku.
Windows nie przesunie działającego wątku na inny procesor tylko z powodu tego, że mógłby działać gdzie indziej a stał się gotowy proces wątek mogący działać tylko na tym zajętym procesorze.
Zwykle optymalnie jest pozwolić systemowi Windows decydować o przydziale procesorów i nie ustawiać po swojemu maski powinowactwa.

Najlepszy i ostatni procesor

Każdy wątek w kernel thread block ma zapamiętaną preferencję dotyczącą idealnego procesora i procesora ostatnio używanego. Preferencje są rozdzielane domyślnie w ten sposób, że kolejne wątki w danym procesie przypisuje się do kolejnych procesorów. Podział taki zakłada równocenność wątków, więc aplikacja może uznać to za nieoptymalne i ustawić inne preferencje. Na systemach wielowątkowych kolejny nalepszy procesor (przy przydziale automatycznym) to pierwszy procesor logiczny na kolejnym fizycznym. W systemach NUMA domyślnie procesy są przydzielane do kolejnych węzłów, zaś wątki rozdzielane w obrębie węzłów.

Algorytmy szeregowania dla wielu procesorów

Wybór procesora, gdy są wolne procesory

Kryteria przydziału malejąco pod względem istotności (gdy są wolne procesory): procesor najlepszy (preferowany), procesor poprzedni, procesor aktualny (na którym wykonywany jest kod przydziału procesora).
W Windows 2000 jeśli żaden z powyżej wymienionych procesorów nie może obsłużyć aktualnie nowego wątku, wybór jest dokonywany przez skanowanie maski wolnych procesorów, w kierunku rosnących numerów procesorów.
W Windows XP i Windows Server 2003 wybór jest bardziej zawiły. Najpierw zbiór wolnych procesorów jest ustawiany zgodnie z maską powinowactwa. Jeśli mamy do czynienia z systemem NUMA i są wolne procesory w węźle zawierającym preferowny procesor, lista wolnych procesorów jest ograniczana do tych właśnie - jeśli jednak lista wolnych procesorów staje się wtedy pusta redukcja nie jest dokonywana. Następnie, jeśli w systemie działają procesory wielowątkowe i jest procesor fizyczny z wszystkimi procesorami logicznymi wolnymi, lista wolnych procesorów jest ograniczana do tychże - jeśli lista wynikowa jest pusta, redukcja nie jest dokonywana. Jeśli obecny procesor (zajmujący się właśnie schedulingiem) znajduje się w otrzymanym zbiorze, jest on przydzielany wątkowi. Jeśli aktualny procesor nie jest w wynikowym zbiorze, ale system jest wielowątkowy i istnieje wolny procesor logiczny w procesorze fizycznym zawierającym najlepszy procesor dla danego wątku, lista wolnych procesorów jest ograniczana do tychże wolnych procesorów logicznych. W przeciwnym przypadku sprawdzane są (i ew. zostawiane na liście wolnych) na podobnej zasadzie procesory logiczne na procesorze ostatnio obsługującym wątek. Z pozostawionej listy eliminuje się (o ile nie opróżni jej to) procesory w stanie uśpionym. Z pozostałych na końcu procesorów wybiera się ten o najmniejszym numerze.

Wybór procesora, gdy nie ma wolnych procesorów

W pierwszej kolejności sprawdzany jest priorytet wątku aktualnie wykonywanego na procesorze idealnym, żeby sprawdzić, czy można go wydziedziczyć. W Windows 2000 maska powinowactwa wątku może wykluczyć procesor idealny z rozważań, choć sytuacja taka nie może zajść w Windows XP. W takim przypadku Windows 2000 wybiera procesor ostatnio obsługujący dany wątek. Jeśli i jego nie ma ustawionego w masce powinowactwa, wybierany jest procesor o możliwie najwyższym numerze. Jeśli najlepszy procesor ma już wątek, który będzie wykonywany następny ale posiada on priorytet niższy od priorytetu przydzielanego właśnie wątku, nowy wątek zostaje ustawiony przed starym. Następuje także sprawdzenie, czy można wydziedziczyć wątek aktualnie wykonywany.
Windows nie patrzy na priorytety obecnych i następnych wątków na wszystkich procesorach. Zatem nie ma gwarancji, że będą na raz działać wszystkie wątki o maksymalnych (z obecnych wśród wątkó występujących w danej chwili w systemie) priorytetach, ale będzie działał ten o największym.
Jeśli wątek nie może być wykonany natychmiast, jest wstawiany do kolejki "ready". W przypadku Windows Server 2003 jest to zawsze kolejka dla procesora najlepszego.

Wybór wątku dla danego procesora

W sytuacjach takich, jak: wywołanie przez wątek funkcji typu wait, obniżenie się priorytetu wątku, zmiana jego powinowactwa czy zrzeczenie się procesora, Windows musi znaleźć dla tego procesora nowy wątek. Na systemach jednoprocesorowych wybrany jest pierwszy wątek z niepustej kolejki oczekujących o możliwie wysokim priorytecie. Na systemach wieloprocesorowych taktyka jest nieco inna.
Przeszukiwana jest niepusta kolejka o możliwie wysokim priorytecia i wyszukiwany jest wątek, który spełnia choć jeden z następujących warunków: ostatnio był obsługiwany przez ten właśnie procesor, jego preferowanym procesorem jest ten procesor, jest w stanie "ready" przez dłużej niż 3 takty zegara, ma priorytet >=24. Gdy nie ma takich wątków, Windows bierze głowę listy.
Ponieważ w Windows 2003 każdy procesor ma własną listę wątków oczekujących na uruchomienie na tym procesorze, w przypadku gdy wszystkie kolejki "ready" są puste uruchamiany jest wątek idle. Rozpczyna on skanowanie kolejek innych procesorów w poszukiwaniu wątków, któe można by na danym procesorze wykonać. W systemach NUMA wątek idle przeszukuje wpierw kolejki dla procesorów w tym samym węźle.
 

Związane z szeregowaniem funkcje WinAPI

Suspend/ResumeThread, Get/SetPriorityClass, Get/SetThreadPrioritym, Get/SetProcessAffinityMask, SetThreadAffinityMask, SetInformationJobObject, GetLogicalProcessorInformation, Get/SetThreadPriorityBoost, SetThreadIdealProcessor, Get/SetProcessPriorityBoost, SwitchToThread, Sleep, SleepEx.
 

Funkcje Win32 API (Windows 9x/NT)

AttachThreadInput Przekierowanie wejścia z jednego wątku do drugiego.
CancelWaitableTimer Deaktywacja timera oczekiwania.
ConvertThreadToFiber Przemienia aktualny wątek na włókno.
CreateEvent Tworzy zdarzenie.
CreateFiber Tworzy włókno.
CreateMutex Tworzy mutexa.
CreateProcess Tworzy proces, wątek i rozpoczyna proces
CreateProcessAsUser Tworzy proces i wątek w kontekście bezpieczeństwa danego użytkownika.
CreateRemoteThread Tworzy wątek uruchamiany w przestrzeni adresowej innego procesu.
CreateSemaphore Tworzy semafor.
CreateThread Tworzy i rozpoczyna wątek.
CreateWaitableTimer Tworzy licznik oczekiwania.
DeleteCriticalSection Kasuje nieaktywną sekcję krytyczną.
DeleteFiber Kasuje włókno.
DuplicateHandle Kopiuje dowiązanie do jakiegoś obiektu tak, by mógł on być wykorzystany przez inny proces.
EnterCriticalSection Sprawdza czy można wejść do sekcji krytycznej i jeśli tak to wchodzi.
ExitProcess Kończy proces wraz z wszystkimi wątkami i zwraca kod zakończenia.
ExitThread Kończy wątek.
GetCurrentFiber Zwraca aktualne włókno dla danego wątku.
GetCurrentProcess Zwraca dowiązanie do aktyalneo procesu.
GetCurrentProcessId Zwraca ID aktualnego procesu.
GetCurrentThread Zwraca dowiązanie do aktualnego wątku.
GetCurrentThreadID Zwraca ID aktualnego wątku.
GetExitCodeProcess Zwraca kod danego procesu (może byś użyta do sprawdzania czy proces się zakończył).
GetExitCodeThread Zwraca kod zakończenia danego wątku (może być użyta do sprawdzenia czy dany wątek się zakończył).
GetFiberData Zwraca dane powiązane z włóknem.
GetPriorityClass Zwraca priorytet danego procesu.
GetProcessAffinityMask Zwraca affinity mask(maska przydziału procesorów do procesu).
GetProcessHeap Zwraca dowiązanie do stosu procesu.
GetProcessHeaps Zwraca listę dowiązań do wszystkich stosów procesora.
GetProcessPriorityBoost Podaje zwiększenie priorytetu procesu.
GetProcessShutdownParameters Podaje parametry zakońvczenia procesu.
GetProcessTimes Podaje czas wykonywania procesu.
GetProcessVersion Zwraca wersję Windows, jakiej oczekuje proces.
GetProcessWorkingSize Zwraca rozmiar zbioru roboczego dla procesu.
GetQueueStatus Zwraca stan wejściowy kolejki wątków.
GetThreadContext Pobiera kontekst wątku.
GetThreadPriority Pobiera prorytet wątku.
GetThreadPriorityBoost Zwraca zwiększenie priorytetu wątku.
GetThreadSelectorEntry Zwraca lokalną tablicę deskryptoró.
GetThreadTimes Zwraca czas wykonywania wątku.
InitializeCriticalSection Konstruuje sekcję krytyczną.
InterlockedCompareExchange Porównuje wartości zsynchronizowaych longów.
InterlockedDecrement Zmniejsza zsynchronizowanego longa.
InterlockedExchange Zmienia wartość na zsynchronizowanego longa.
InterlockedExchangeAdd Doadaje wartość do zsynchronizowanego longa.
InterlockedIncrement Zwiększa wartość zsynchronizowanego longa.
LeaveCriticalSection Koniec sekcji krytycznej.
MsgWaitForMultipleObjects Sprawdza kiedy i zy wszystkie podane obiekty otzrymały określony sygnał.
MsgWaitForMultipleObjectsEx Jak MsgWaitForMultipleObjects ale np. zakończenie operacji I/O lub wywałanie APC też powoduje powrót z funkcji.
OpenEvent Zwraca dowiązanie do zdarzenia.
OpenMutex Zwraca dowiązanie do mutexa.
OpenProcess Zwraca dowiązanie do procesu.
OpenSemaphore Zwraca dowiązanie do semafora.
OpenWaitableTimer Zwraca dowiązanie do licznika oczekiwania.
PulseEvent Przestaw wyrażenie z niesygnalizowanego na sygnalizowane i z powrotem.
QueueUserAPC Kolejkuje asynchroniczne wywołania procedur do kolejki APC wątku.
RaiseException Zgłoś wyjątek.
ReadProcessMemory Czyta z pamieci adresowej procesu.
RegisterHotKey Tworzy skrót klawiszowy dla danego wątku.
ReleaseMutex Zwalnia mutex.
ReleaseSemaphore Zwalnia semafor.
ResetEvent Ustawia zdarzenia jako niesygnalizowane.
ResumeThread Wznawia wykonanie zawieszonego wątku.
SetEvent Ustawia zdarzenie jako sygnalizowane.
SetPriorityClass Ustawia priorytet procesu.
SetProcessAffinityMask Ustawia afinity mask dla procesu.
SetProcessPriorityBoost Ustawia zwiększenie priorytetu dla procesu.
SetProcessShutdownParameters Ustawia parametry zakończenia procesu.
SetProcessWorkingSetSize Ustawia rozmiar zbioru roboczego dla procesu.
SetThreadAffinityMask Ustawia affinity mask dla wątku.
SetThreadContext Ustawia kontekst wątku.
SetThreadIdealProcessor Ustawia preferowany procesor dla wątku.
SetThreadPriority Ustawiwa priorytet wątku.
AttachThreadInput ble
SetThreadPriorityBoost Ustawia zmianę priorytetu wątku.
SetUnhandledEceptionFilter Ustawia funkcję obsługi nieprzechwytywanych wyjątków.
SetWaitableTimer Ustawia licznik oczekiwań.
SignalObjectAndWait Wysyłą sygnał do obiektu i czeka.
Sleep Zawiesza wykonanie wątku na milisekundy.
SleepEx Jak Sleep ale zakończenie I/O lub wywołanie APC też powoduje zakończenie.
SuspendThread Zawiesza wątek.
SwitchToFiber Szereguje włókno do wykoania.
TerminateProcess Konczy proces.
TerminateThread Konczy wątek.
TlsAlloc Alokuje TLS.
TlsFree Dealokuje TLS.
TlsGetValue Odczytuje dane z TLS.
TlsSetValue Zapisuje dane do TLS.
TryEnterCriticalSection Próbuje skorzystać z sekcji krytycznej.
UnhandledExcvpetionFilter Wywołuje funkcję obsługi nieprzechwytywanych wyjątków.
UnregisterHotKey Oddeklaruj klawisz skrótu.
WaitForInputIdle Czeka aż pojawi się coś na wejściu procesu.
WaitForMultipleObjects Czeka aż pojawi się wyspecyfikowany obiekt.
WaitForMultipleObjectsEx Jak WaitForMultipleObjects ale APC i I/O też kończą.
WaitForSingleObject Czeka na obiekt synchronizacyjny.
UnhandledExcvpetionFilter Jak WaitForSingleObject ale I/O i APC też kończą.
WriteProcessMemory Pisze bezpośrednio do pamięci procesu.

Funkcje i struktury Native API (Windows NT/2000)

Nieudokumentowane funkcje niskopoziomowe. Poniżej przykłady.

Związane z wątkami:
ZWCreateThread, ZWOpenThread, ZWTerminateThread, ZWQueryInformationThread, ZWSetInformationThread, THREADINFOCLASS, ThreadBasicInformation, ThreadPriority, ThreadBasePriority, ThreadAffinityMask, ThreadImpersonationToken, ThreadEnableAlignmentFaultFixup, ThreadEventPair, ThreadQuerySetWin32StartAddress, ThreadZeroTlsCell, ThreadPerformanceCount, ThreadAmILastThread, ThreadIdealProcessor, ThreadPriorityBoost, ThreadSetTlsArrayAddress, ThreadIsIoPending, ThreadHideFromDebugger, ZWSuspendThread, ZWResumeThread, ZWGetContextThread, ZWSetContextThread, ZWQueueApcThread, ZWTestAlert, ZWAlertThread, ZWAlertResumeThread, ZWRegisterThreadTerminatePort, ZWImpersonateThread, ZWImpersonateAnonymousToken.

Związane z procesami:
ZWCreateProcess, ZWOpenProcess, ZWTerminateProcess, ZWQueryInformationProcess, ZWSetInforamtionProcess, PROCESSINFOCLASS, ProcessBasicInformation, ProcessQuotaLimits, ProcessIoCounters, ProcessVmCounters, ProcessTimes, ProcessBasePriority, ProcessRaisePriority, ProcessDebugPort, ProcessExceptionPort, ProcessAccessToken, ProcessDefaultHardErrorMode, ProcessPooledUsageAndLimits, ProcessWorkingSetWatch, ProcessUserModelOPL, ProcessEnbleAlignmentFaultFixup, ProcessPriorityClass, ProcessWx86Information, ProcessHandleCount, ProcessAffinityMask, ProcessPriorityBoost, ProcessDeviceMap, ProcessSessionInformation, ProcessForegroundInformation, ProcessWow64Information, RtlCreateProcessParameters, RtlDestroyProcessParameters, PROCESS_PARAMETERS, RtlCreateQueryDebugBuffer, RtlQueryProcessDebugInformation, RtlDestroyQueryDebugBuffer, DEBUG_BUFFER, DEBUG_MODULE_INFORMATION, DEBUG_HEAP_INFORMATION, DEBUG_LOCK_INFORMATION.

Związane z zadaniami:
ZWCreateJobObject, ZWOpenJobObject, ZWTerminateJobObject, ZWAssignProcessToObject, ZWQueryInformationJobObject, ZWSetInformationJobObject, JOBOBJECTINFOCLASS, JobObjectBasicAccountingInformation, JobObjectBasicLimitInformation, JobObjectBasicProcessIdList, JobObjectBasicUIRestrictions, JobObjectSecurityLimitInformation, JobObjectEndOfJobTimeInformation, JobObjectAssociateCompletionPortInformation, JobObjectBasicAndIoAccountingInformation, JobObjectExtendedLimitInformatio



Bibliografia


Linux




Windows


Informacje i rysunki zamieszczone w powyższym tekście o systemach Windows pochodzą z wymienionych poniżej źródeł. Windows jest nazwą zastrzeżoną należącą do korporacji Microsoft. Autor powyższego tekstu nie ponosi odpowiedzialności za wykorzystanie przedstawionych materiałów.
©2005 Marcin Balcerzak, Adam Busch, Maciek Smoleński