Task_union
Proces w trybie jądra używa stosu zawartego w segmencie danych jądra, który różni się od stosu używanego w trybie użytkownika. Ścieżki wykonania jądra rzadko używają tego stosu, więc 8KB jest wystarczającym obszarem na stos i deskryptor procesu. Taką strukturę wyrażono za pomocą następującej unii:
union task_union {
struct task_struct task;
unsigned long stack[2048];
};
Rejestr esp jest wskaźnikiem stosu używanym do określenia położenia wierzchołka stosu. W systemach Intela stos zaczyna się na końcu i rozszerza w kierunku początku obszaru pamięci, gdzie znajduje się deskryptor procesu. Zaraz po przełączeniu się z trybu użytkownika do trybu jądra, stos jądra procesu jest pusty i rejestr esp wskazuje na bajt znajdujący się tuż za obszarem pamięci.
free_task_struct() - Funkcja zwraca 8-kilobajtowe obszary pamięci task_union i umieszcza je w pamięci podręcznej do czasu zapełnienia.
alloc_task_struct() - Funkcja ta alokuje obszary pamięci dla task_union o wielkości 8 KB. (Uwaga: Z powodu wydajności jądro przechowuje te 8 KB jako dwa, znajdujące się obok siebie bloki stronicowe, gdzie pierwsza strona jest wyrównana do wielokrotności 213.)
Makro NICE_TO_TICKS
Powyższe makro jest zdefiniowane w następujący sposób:
#define NICE_TO_TICKS(nice) (TICK_SCALE(20-(nice))+1)
Makro TICK_SCALE zależy od wartości zmiennej HZ, gdzie HZ jest stałą, zależną od architektury komputera, określającą częstotliwość przerwań zegara. Dla architektury Intela i386 HZ wynosi 100. Z tego też względu w naszym przypadku makro TICK_SCALE(x) jest zdefiniowane jako x >> 2. Z tego wynika, że zwraca ono wartość ((20-nice) >> 2) + 1.
Przykład:
Jeżeli proces ma wartość nice ustawioną na -20, wtedy:
20-(-20)=40, w systemie binarnym: 101000. Następnie 101000 >> 2 otrzymujemy: 001010 czyli 8+2=10. Jeszcze 10+1=11, czyli dla wartości nice=-20 nasze makro zwróci wartość 11.
Jeżeli proces ma wartość nice ustawioną na 0, wtedy:
20-(0)=20, w systemie binarnym: 010100. Następnie 010100 >> 2 otrzymujemy: 000101 czyli 4+1=5. Jeszcze 5+1=6, czyli dla wartości nice=0 nasze makro zwróci wartość 6
Jeżeli proces ma wartość nice ustawioną na +19, wtedy:
20-(+19)=1, w systemie binarnym: 000001. Następnie 000001 >> 2 otrzymujemy: 000000 czyli 0. Jeszcze 0+1=1, czyli dla wartości nice=+19 nasze makro zwróci wartość 1.
Stąd wniosek, że NICE_TO_TICKS zwraca wartości od +11 do +1.
Funkcja goodness
Funkcja decyduje jak pożądany jest proces. "Ważność" procesu zależy od jego typu: wsadowy, interakcyjny, czy czasu rzeczywistego oraz od aktualnego procesora.
- Jeżeli proces ma ustawioną flagę SCHED_YIELD oznacza to, iż sam dobrowolnie zrezygnował z procesora, z tego względu jego waga jest ustawiana na -1, co jest równoznaczne temu, iż ten proces na pewno nie otrzyma procesora.
- Jeżeli proces jest typu SCHED_OTHER i skończył już swój kwant czasu ustawiana jest mu waga = 0. Natomiast, gdy jego pole
counter jest różne od 0, wagą staje się wartość tego pola. Jednakże w pewnych przypadkach goodness() jest bardziej przychylna dla danego procesu (dodatkowo zwiększa jego wagę), tzn. wtedy, jeżeli proces pracował poprzednio na tym procesorze, waga jego jest dodatkowo zwiększana o stałą wartość równą PROC_CHANGE_PENALTY (ustawioną na stałe na 15); lub też, jeżeli proces ma tą samą przestrzeń adresową co bieżący, jego waga jest zwiększana o 1. Na zakończenie do wagi dodawana jest wartość (20 - nice).
- Jeżeli proces jest procesem czasu rzeczywistego jego wagą staje się 1000 zwiększony o priorytet czasu rzeczywistego, czyli
rt_priority.
Wnioski: Waga dodatnia oznacza, że proces jest dobrym kandydatem na otrzymanie procesora (im wyższa waga tym chętniej przyznajemy CPU), natomiast waga zerowa, bądź ujemna oznacza, że proces nie może otrzymać procesora, gdyż nie ma na to odpowiednich warunków.
Synchronizacja procesów na poziomie jądra
Jak wiadomo, funkcje jądra są wykonywane w następstwie żądań, które mogą być zgłaszane na dwa sposoby:
- proces wykonujący się w trybie użytkownika zgłasza jakiś wyjątek
- urządzenie zewnętrzne wysyła sygnał do programowalnego kontrolera przerwań PIC (ang. Programmable Interrupt Controller) za pomocą linii IRQ, a odpowiednie przerwania są włączone.
Sekwencja instrukcji, wykonywana w trybie jądra w celu obsłużenia żądania, jest nazywana ścieżką wykonania jądra.
Ścieżki wykonania jądra pełnią rolę podobną do procesów, są jednak prostsze. Przede wszystkim nie jest z nimi związany żaden deskryptor, poza tym nie są szeregowane za pomocą jednej funkcji, ale przez wstawienie do kodu jądra sekwencji instrukcji zatrzymujących lub wznawiających ścieżki.
W najlepszym przypadku procesor wykonuje ścieżki wykonania jądra sekwencyjnie, od pierwszej do ostatniej instrukcji. Niestety, jeżeli się zdarzy:
- przełączenie kontekstu;
- wystąpienie przerwania, akurat wtedy gdy procesor wykonywał jakąś ścieżkę wykonania jądra z włączonymi przerwaniami (w tym przypadku jądro pozostawia niedokończoną ścieżkę wykonania jądra i rozpoczyna następną, obsługującą przerwanie);
to procesor musi przeplatać ścieżki wykonania jądra. I tutaj trzeba uważać na struktury danych zawierające kilka powiązanych zmiennych. Wszystkie instrukcje operujące na takiej strukturze trzeba umieścić w jednej sekcji krytycznej.
W Linuksie są wyróżnione cztery techniki synchronizacji:
- niewywłaszczanie procesów w trybie jądra
- operacje niepodzielne
- wyłączanie przerwań
- blokady
Blokady
W systemach jednoprocesorowych Linux oferuje jeden rodzaj blokad, tzw. semafory jądra.
W przypadku gdy ścieżka wykonania jądra chce pobrać zajęty, chroniony przez semafor jądra, zasób, to odpowiedni proces zostanie uśpiony. Zacznie swoje działanie wtedy, gdy zasób stanie się dostępny.
Semafory jądra są obiektami typu struct semaphore [Linux/include/asm-i386/semaphore.h] i mają następujące pola:
atomic_t count - przechowuje wartość całkowitą. Jeżeli jest większa niż 0, oznacza to, że zasób jest dostępny. Jeżeli wartość count jest mniejsza lub równa 0, to zasób jest zajęty. Zmienna typu atomic_t jest strukturą zawierającą jeden atrybut typu int, na której w sposób atomowy są zdefiniowane pewne operacje arytmetyczne.
wait_queue_head_t wait - przechowuje adres kolejki oczekiwania, która zawiera wszystkie uśpione procesy, czekające aktualnie na zasób
int sleepers - zmienna pomocnicza, która mówi ile procesów w danej chwili przejdzie pod semaforem. Jest ona inicjalizowana na 0.
Pole count jest zwiększane, gdy proces chce podnieść semafor, a zmniejszane gdy go opuszcza.
Jeżeli proces chce podnieść semafor, wywołuje funkcję up().
Algorytm up
Najpierw proces zwiększa wartość count i porównuje ją z zerem (porównanie i test są wykonywane atomowo). Jeżeli nowa wartość count jest większa od zera, to w kolejce oczekiwania semafora nie ma żadnego procesu, tak więc proces nic więcej nie robi. W przeciwnym wypadku, (count <=0) budzi pierwszy proces z kolejki procesów czekających na zasób (funkcja wake_up()). Wykonanie funkcji wake_up() jest chronione, tzn. przed wykorzystywaniem elementów kolejki zapamiętywane są flagi oraz wyłączane przerwania, a po zakończeniu działań na kolejce przerwania zostają włączane, a flagi odtwarzane.
void up(semaphore *sem)
{
/* Sekcja krytyczna */
sem->count ++;
if (sem->count <= 0) /* wpp. kolejka oczekiwania jest pusta */
{
/* Koniec sekcji */
Wstaw następny proces z kolejki oczekiwania semafora do kolejki procesów gotowych.
/* Budzenie procesu - funkcja wake_up */
}
}
Jeżeli proces chce opuścić semafor, wywołuje funkcję down().
Algorytm down
Analogicznie jak w funkcji up(), na początku proces zmniejsza wartość count i porównuje ją z zerem (operacja atomowa). Jeżeli nowa wartość count jest większa bądź równa zero, to procesowi udało się przejść pod semaforem i zająć zasób, w przeciwnym wypadku proces zmienia swój stan na TASK_UNINTERRUPTIBLE oraz wstawia się do kolejki wait - procesów czekających na zasób (funkcja add_wait_exclusive() - analogiczna ochrona jak w wake_up(), przy wykonywaniu tej funkcji). Następnie proces wyłącza przerwania (makro spin_lock_irq()) i zwiększa wartość sleepers. Zaczyna wykonywać pętlę. Atomowo zwiększa count o (sleepers - 1) (makro atomic_add_negative()) i sprawdza czy wartość count jest większa bądź równa zero. Jeśli tak, to może pobrać zasób. Ustawia sleepers na 0 (żeby zablokować inne procesy), wychodzi z pętli, odblokowuje przerwania (makro spin_unlock_irq()), usuwa się z kolejki wait (funkcja remove_wait_queue()), zmienia stan na TASK_RUNNING i budzi pierwszy proces z kolejki wait funkcją wake_up(). Jeśli count < 0, to musi zasnąć. Ustawia sleepers na 1, odblokowuje przerwania i wywołuje funkcje schedule(), która go usypia (wywłaszcza). Po obudzeniu powtarza pętlę aż do skutku.
void down(struct semaphore *sem)
{
/* Sekcja krytyczna */
sem->count--;
if (sem->count < 0) /* wpp. udało się przejść pod semaforem */
{
/* Koniec sekcji */
Zmień stan procesu na TASK_UNINTERRUPTIBLE;
Wstaw proces do kolejki oczekiwania semafora. /* add_wait_queue_exclusive() */
Wyłączenie przerwań /* spin_lock_irq() */
sem->sleepers++;
for (;;){
int sleepers = sem->sleepers;
if ((sem->count += sleepers - 1) >= 0)/*!atomic_add_negative(sleepers-1, sem->count)*/
{ /* ktoś podniósł semafor */
sem->sleepers = 0;
break; /* możemy pobrać zasób*/
}
sem->sleepers = 1;
Włączenie przerwań /* spin_unlock_irq() */
schedule(); /* proces zostaje uśpiony */
Zmień stan procesu na TASK_UNINTERRUPTIBLE
Wyłączenie przerwań
} /* for */
Włączenie przerwań
Usuń proces z kolejki oczekiwania semafora /* remove_wait_queue() */
Zmień stan procesu na TASK_RUNNING
Wstaw pierwszy (jeśli jest) proces z kolejki oczekiwania semafora
do kolejki procesów gotowych. /* wake_up() - budzenie procesu */
}
}
Przełączanie kontekstu
W skład kontekstu procesu wchodzą: zawartość rejestrów procesora i przestrzeni adresowej procesu oraz struktury jądra związane z danym procesem. Przełączanie kontekstu polega na zamianie aktualnie wykonującego się procesu.
Sytuacje w jakich dochodzi do przełączania kontekstu to:
- pojawienie się procesu o priorytecie wyższym niż priorytet bieżącego procesu
- zaśnięcie procesu w oczekiwaniu na jakieś zdarzenie
- wykorzystanie przez bieżący proces przydzielonego mu kwantu czasu procesora
- dobrowolna rezygnacja z procesora (wywołanie funkcji
sched_yield())
- zakończenie działania procesu
Z każdym procesorem w systemie jest związana specjalna struktura TSS, określana mianem segmentu stanu zadania. W tej strukturze system przechowuje kontekst aktualnie działającego procesu.
W TSS przechowywane są następujące dane obecnie działającego procesu:
- adresy stosów dla poziomów pracy procesora (pola esp0, ss0 , esp1, ss1, esp2, ss2)
- rejestry ogólnego przeznaczenia (pola eax, ebx, ecx, edx)
- rejestry indeksowe (pola esi, edi)
- rejestry segmentowe(ds,es,fs,gs)
- aktualny stos(ss,esp,ebp)
- adres kolejnej instrukcji (cs, eip)
- flagi(eflags)
- mapa bitowa dostępnych portów we/wy
W deskryptorze procesu jest pole thread typu thread_struct, w którym znajdują się informacje o stanie tego procesu m.in. thread.esp0, esp, eip, fs, gs o znaczeniu analogicznym jak odpowiednie pola w TSS.
Makro switch_to
Makro switch_to() [Linux/include/asm-i386/system.h] wykonuje przełączenie procesów. Używa trzech parametrów oznaczonych jako prev, next i last. prev jest wskaźnikiem do deskryptora procesu, który ma być przełączony do tła, a next jest wskaźnikiem do deskryptora procesu, który ma być wykonywany przez procesor. Makro to jest wywoływane przez funkcję schedule().
Jak działa to makro?
- zapisuje na stosie bieżącego procesu rejestry ESI, EDI, EBP
- przełącza stosy. W polu
prev->thread.esp zapisywana jest bieżąca wartość rejestru ESP, natomiast z next->thread.esp jest odtwarzana wartość tego rejestru, wskazująca na szczyt stosu procesu next w segmencie danych jądra. W tym momencie jądro działa na stosie jądra next, tak więc tutaj następuje przełączenie kontekstu
- w
prev->thread.eip jest zapisywany adres procedury, która powoduje odtworzenie ze stosu umieszczonych tam wartości rejestrów ESI, EDI oraz EBP.
- następnie jest przywracana wartość EIP z
next->thread.eip. Jeżeli proces next nie był jeszcze usypiany to w tym polu będzie adres etykiety ret_from_fork, której adres jest zapisywany w thread.eip procesu zaraz po jego utworzeniu przez funkcje systemową fork().
- wywołanie funkcji
__switch_to(prev, next) [Linux/i386/kernel/process.c], która kończy przełączanie kontekstu.
Jak działa __switch_to()?
- zapisuje stan koprocesora matematycznego.
- załadowuje rejestr esp0 z
next->thread.esp0
- zapamiętuje rejestry FS i GS w
prev.thread
- załadowuje nowe wartości rejestrów FS i GS z
next->thread
- sprawdza czy proces wykonuje się w trybie
debug i jeżeli tak, to ładowane są rejestry debugregs
- ustawiana jest odpowiednia mapa we/wy
Teraz jądro działa już w kontekście nowego procesu.
Po powrocie ze __switch_to() makro switch_to odtwarza wartości rejestrów ESI, EDI, EBP.
Algorytm exec
Zadaniem tego algorytmu jest zastąpienie zawartości pamięci procesu przez nowy program. Algorytm ten załadowuje plik binarny do pamięci i rozpoczyna jego wywołanie, zastępując segment kodu, danych i stosu. W szczególności jeśli procesowi powiedzie się wywołanie funkcji exec, to nie tworzy się nowy proces, tylko ten sam proces działa dalej jednak ma już inny kod oraz podmieniony segment danych i stosu. Nie zmienia mu się PID, dziedziczy wszystkie deskryptory otwartych plików, które nie mają opcji zamykania podczas exec oraz zostaje przywrócona standardowa obsługa sygnałów, chociaż sygnały ignorowane przed wywołaniem funkcji nadal będą ignorowane.
Jednakże algorytm exec wykorzystuje tylko już istniejące funkcje w systemie, służące do ładownia plików binarnych.
Na początku zostaje wywołana funkcja execve(). [Linux/include/asm-i386/unistd.h]
Deklaracja:
static inline int execve(const char *file, char **argv, char **envp);
gdzie:
file - nazwa programu do wykonania
argv - tablica zawierająca argumenty dla programu
envp - tablica zawierająca ustawione zmienne środowiskowe
Funkcja ta wywołuje przerwanie (SYSCALL_VECTOR) i przekazuje swoje parametry do procedury obsługi tego przerwania (sys_call). Z kolei ta procedura uruchamia funkcję sys_execve() [Linux/arch/i386/kernel/process.c], której parametrem jest struktura zawierająca stan rejestrów procesora (struct pt_regs [Linux/include/asm-i386/ptrace.h]).
Funkcja sys_execve() sprawdza, czy podany plik jest wykonywalny i czy nie jest katalogiem lub urządzeniem - jeśli tak zwraca błąd i funkcja exec() na zmiennej errno zapisuje kod błędu.
W przeciwnym wypadku zostaje wywołana funkcja do_execve() z parametrami takimi jak execve(), oraz dodatkowo z parametrem z sys_execve().
Struktura struct linux_binprm [Linux/include/linux/binfmts.h] zawiera m.in. pola:
char buf[128] - tu przechowywanych jest 128 pierwszych znaków ładowanego programu
int e_uid, e_gid - zawierają odpowiednio, efektywny identyfikator użytkownika oraz identyfikator grupy procesu uruchamiającego.
i jest wykorzystywana przez do_execve().
Funkcja do_execve() wykonuje następujące operacje:
- Statycznie alokuje strukturę danych
linux_binprm, która zostanie wypełniona danymi, dotyczącymi nowego pliku wykonywalnego
- Wywołuje funkcję
open_exec() w celu pobrania obiektu pozycji katalogu. W przypadku niepowodzenia zwraca odpowiedni kod błędu.
- Wywołuje funkcję
prepare_binprm(),po to by wypełnić strukturę linux_binprm. Funkcja ta wykonuje operacje:
- Sprawdza, czy prawa pliku umożliwiają jego wykonanie, wpp. zwraca kod błędu.
- Sprawdza, czy plik jest właśnie zapisywany, jeżeli tak zwraca kod błędu.
- Inicjuje pola
e_uid i e_gid struktury linux_binprm, biorąc pod uwagę wartości flag setuid i setgid pliku wykonywalnego. Pola te reprezentują odpowiednie identyfikatory efektywnego użytkownika i grupy.
- Wypełnia pole
buf struktury linux_binprm pierwszymi 128 znakami pliku wykonywalnego. Bajty te zawierają informacje umożliwiające rozpoznanie formatu pliku wykonywalnego.
- Kopiuje ścieżkę dostępu argumentu linii poleceń i zmienne środowiskowe do jednego lub więcej nowo zaalokowanych bloków stronicowych.
- Wywołuje funkcję
search_binary_handler(), która zajmuje się właściwym uruchamianiem programu. Na początku pobiera wskaźnik do początku listy dostępnych formatów dzięki makru formats. Następnie dla każdego formatu próbuje zastosować jego funkcję służącą do ładowania programu (load_binary()), przekazując jej strukturę danych linux_binprm. Przeszukiwanie listy formats kończy się gdy tylko jakaś funkcja load_binary() potwierdzi format wykonywalny pliku.
- Jeżeli format pliku wykonywalnego nie znajduje się na liście
formats, zwalnia wszystkie zaalokowane bloki stronicowe i zwraca kod błędu. Linux nie może rozpoznać formatu pliku wykonywalnego.
- W przeciwnym wypadku ustawia flagę w strukturze procesu mówiącą o tym, że udało się wykonać
exec() i zwraca kod zwrócony przez funkcję load_binary(), związaną z formatem pliku wykonywalnego.
Niektóre błędy jakie może zgłosić funkcja exec():
| | EACCES | | - zabroniony dostęp do pliku |
| | ENOMEM | | - nowy proces wymaga zbyt dużo pamięci |
| | EAGAIN | | - ilość pamięci podczas operacji we/wy jest niewystarczająca |
| | ENOENT | | - błędna ścieżka dostępu do pliku |
