Do spisu tresci tematu 2

2.1.1 Tworzenie procesu - algorytm fork




Spis tresci

Wprowadzenie

Funkcja systemowa fork() jest jedna z najwazniejszych funkcji w systemach unixowych, takze w Linuxie. Za jej sprawa, i tylko za jej sprawa, moga sie pojawiac w systemie nowe procesy. Jedynym procesem, ktory jest powolywany do zycia w inny sposob jest proces o numerze (identyfikatorze) 1, czyli init. Jak to sie dzieje dokladnie, dowiesz sie w omowieniu tematu 10.

Z punktu widzenie programisty, fork() jest bardzo prosta funkcja. Wywoluje sie go tak: 

          pid = fork();
i w wyniku dostaje dwie rozne wartosci. Proces macierzysty, ktory wowolal forka, dostaje identyfikator dziecka. Dziecko dostaje w wyniku 0. Dzieki temu procesy moga poznac "ktory jest ktory" bez uciekania sie do sztuczek. Dziecko jest prawie dokladna kopia rodzica - rozni sie tylko tym, co zwraca fork(). Oczywiscie w przypadku niepowodzenia dziecko nie jest tworzone a rodzic otrzymuje informacje o bledzie.

Struktury danych


Wprowadzenie

Wlasciwie wszystkie ponizsze struktury powinny zostac omowione w temacie 1, ale przyda sie spojrzenie na nie z "naszej", forkowej, strony.

fork() wykorzystuje do swoich dzialan glownie systemowa tablice task[NR_TASKS], zadeklarowana w pliku include/linux/sched.h. Jest to "potrojna" struktura danych, bowiem na tablicy tej zaimplementowane sa dwukierunkowe listy (m. in. dla procesow gotowych do wykonania i wszystkich procesow) oraz drzewo genealogiczne. Dzialanie omawianej funkcji fork()sprowadza sie do wpisania nowych informacji do powyzszej tablicy i zapewnienia spojnosci danych po dokonaniu wpisu.

W Linuxie moze byc uruchomionych maksymalnie NR_TASKS procesow. Root moze wszystko - nie ma nakladanych na niego zadnych ograniczen, oprocz powyzszej liczby. Zwykly uzytkownik moze uruchomic maksymalnie MAX_TASKS_PER_USER procesow, ale w systemie musi zawsze zostac przynajmniej MIN_TASKS_LEFT_FOR_ROOT pozycji w tablicy procesow. Odpowiednie wartosci wynosza standardowo: 512, 256, 4 i sa zdefiniowane w pliku include/linux/tasks.h.


Struktura task_struct

Ta struktura to "metryczka" procesu. Zawiera wszystkie informacje o procesie. Oto interesujace nas fragmenty: 

struct task_struct {
        volatile long state;
            /* -1 zombie, 0 spiacy badz gotowy, >0 zatrzymany */

        ...

        struct task_struct *next_task, *prev_task;
        struct task_struct *next_run,  *prev_run;
            /* wskazniki sluzace do implementacji dwukierunkowych kolejek
               procesow gotowych do wykonania i wszystkich procesow */

        ...

        int did_exec:1;       /* czy po forku wykonano exec? */
        int pid;            

        ...

        struct task_struct *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr;
             /* wskazniki do: (oryginalnego) ojca, najmlodszego dziecka,
                starszego i mlodszego rodzenstwa */
        ...

        struct fs_struct *fs;
        struct files_struct *files;
        struct mm_struct *mm;
        struct signal_struct *sig;
             /* wskazniki do struktur, ktorych znaczenie
                opisane jest nizej */
};
Pelna definicja task_struct znajduje sie w include/linux/sched.h.


Struktura files_struct

Struktura files_struct dotyczy informacji o plikach uzywanych przez pojedynczy proces. Jak prawie kazda struktura dotyczaca informacji o procesie, tak i ta zawiera licznik odwolan do niej, umozliwiajac wspoldzielenie struktury przez kilka procesow. Oto pelna definicja: 

struct files_struct {
        int count;
             /* licznik odwolan do struktury */
        fd_set close_on_exec;
             /* zbior deksryptorow plikow, ktore beda automatycznie
                zamkniete przy wykonywaniu funkcji exec */
        struct file * fd[NR_OPEN];
             /* tablica otwartych plikow procesu */
};
Tutaj mozna obejrzec sobie oryginalna definicje.


Struktura fs_struct

Ta stuktura zawiera informacje o masce praw dostepu dla nowo tworzonych przez uzytkownika plikow (umask), oraz wskazniki do dwoch i-wezlow: wezla naszego katalogu glownego (ktory mozemy zmieniac przez chroot()) oraz katalogu, w ktorym sie aktualnie znajdujemy. Dzieki temu system wie, gdzie jestesmy i nie pozwoli innemu procesowi usunac naszego katalogu aktualnego. Definicja jest krotka: 

struct fs_struct {
        int count;
              /* licznik odwolan do struktury */
        unsigned short umask;
              /* umask uzytkownika */
        struct inode * root, * pwd;
              /* wskazniki do i-wezlow katalogu glownego i aktualnego */
};
a jej oryginalny wyglad mozna znalezc tutaj.


Struktura mm_struct

Ta struktura jest bardzo skomplikowana i powinna byc w calosci omowiona w temacie 4. Dosc powiedziec, ze struktura ta zawiera ona m. in. nastepujace informacje: o aktualnym kontekscie procesu, poczatku i koncu jego segmentu kodu, danych, parametrow wywolania, przekazanego srodowiska shellowego, informacje o segmencie stosu, poczatku tablicy stron, oraz informacje o pamieci wirtualnej procesu. Jedyna interesujaca nas informacja jest to, ze ta struktura takze moze byc wspoldzielona przez kilka procesow (zob. pole count w definicji stuktury).


Struktura signal_struct

Struktura signal_struct to wlasciwie tablica funkcji obslugujacych sygnaly, uzupelniona o dodatkowe, nieistotne dla nas, informacje. Jej pelna definicja jest bardzo krotka: 

struct signal_struct {
        int count;
             /* licznik odwolan do struktury */
        struct sigaction action[32];
             /* tablica akcji podejmowanych po otrzymaniu sygnalu */
};
Strukture sigaction mozna obejrzec tutaj.

Procedury pomocnicze


Wprowadzenie

Ponizsze procedury nie sa bezposrednio dostepne dla programisty. Sa to wlasciwie czesci procedury do_fork() i zdefiniowane sa w pliku kernel/fork.c, oprocz makra SET_LINKS, ktorego definicje mozna znalezc w pliku include/linux/sched.h. Omowione zostana krotka w takiej kolejnosci, w jakiej wystepuja w fork.c. Ich dokladna definicje, czyli typy parametrow i typ zwracanej wartosci, mozna zobaczyc ogladajac zrodla. Funkcje o prefiksie copy_ zwracaja 0 w przypadku sukcesu, -1 w przypadku bledu (najczesciej blad braku pamieci). Wszystkie one umozliwiaja klonowanie - wtedy jest zwykle tylko zwiekszany licznik odwolan do danej struktury.

Funkcja find_empty_process()
Funkcja najpierw sprawdza, czy mozna jeszcze w gole uruchomic jakis nowy proces. Sa zadeklarowane dwie wartosci w pliku include/linux/tasks.h: NR_TASKS okreslajaca liczbe zadan w systemie i MAX_TASKS_LEFT_FOR_ROOT. Byla o nic mowa we wprowadzeniu do struktur danych. Jesli nie jestes rootem, a liczba zadan w systemie jest wieksza niz roznica miedzy powyzszymi wartosciami, to funkcja zwraca -EAGAIN. Nastepnie, jesli nie jestes rootem, funkcja sprawdza, czy nie przekroczyles ustalonej dla ciebie liczby zadan. Jesli tak, to zwracane jest -EAGAIN. Na koniec przeszukiwana jest globalna tablica zadan task i zwracany indeks pozycji, ktora ma wartosc NULL. Jesli nie ma wolnej pozycji, to zwracany jest -EAGAIN.
Funkcja get_pid()
Funkcja zwraca unikatowy identyfikator procesu (o ile nie zazadamy klonowania). Nowy pid jest szukany w ten sposob, ze zwiekszamy ostatnio przydzielony pid. Jesli pid ma wartosc wieksza lub rowna 0x8000, czyli 32768, to nowy pid przyjmuje wartosc 1. Nastepnie jest sprawdzane, czy nowy pid nie koliduje z jakimkolwiek pidem, pgrp-idem lub polem session opisu zadania. W tym przypadku brany jest kolejny pid. Przyklad na zastosowanie goto w C. Jesli zadamy klonowania pid-u, to zwracany jest nasz pid (tj. pid ojca).
Funkcja dup_mmap()
Jest wywolywana przez copy_mm(). Kopiuje strony pamieci rodzica do dziecka. Kopiowanie odbywa sie za zasadzie copy-on-write, czyli jest ustawiany odpowiedni bit na stronach i fizyczne kopiowanie stron odbywa sie tylko w przypadku proby zapisu przez ojca lub dziecko czegos na te strony.
Uwaga! Nie mylic tego faktu ze wspoldzieleniem pamieci, kiedy to strony nigdy nie sa kopiowane, a zmiany dokonane w pamieci przez jeden proces sa widoczne dla innego procesu.
Funkcja copy_mm()
Zwykle po przydzieleniu miejsca na strukture opisujace pamiec wywoluje dup_mmap(). Zerowane sa dane statystyczne dotyczace dostepu do pamieci (minor and major page faults). Jesli zadamy klonowania pamieci, to segmenty nie sa kopiowane, ale procesy moga wspoldzielic pamiec. Struktura wtedy nie jest kopiowana, tylko zwieksza sie licznik odwolan do niej.
Funkcja copy_fs()
Kopiuje strukture fs_struct. Zwieksza liczniki i-wezlow katalogu glownego oraz aktualnego. W przypadku braku pamieci, zwraca -1. W przypadku klonowania tylko zwieksza licznik odwolan do struktury.
Funkcja copy_files()
Kopiuje prywatna tablice deskryptorow plikow procesu, zwieksza liczniki odwolan do i-wezlow plikow opisywanych przez deskryptory. Jezeli zadamy klonowania, to tablica deskryptorow nie jest kopiowana, ale wspoldzielona (zwieksza sie licznik odwolan do niej). Liczniki i-wezlow zwiekszaja sie zawsze.
Funkcja copy_sighand()
Kopiuje procedury obslugi poszczegolnych sygnalow. Mozliwe jest takze wspoldzielenie tablicy obslugi sygnalow - wtedy zwieksza sie tylko licznik odwolan do tej tablicy.
Funkcja SET_LINKS()
Makro zapisuje nowy proces na koncu dwukierunkowej listy cyklicznej. Wskaznik na mlodsze rodzenstwo jest ustawiany na NULL, natomiast modyfikowany jest wskaznik na starsze rodzenstwo i wskaznik na mlodsze rodzenstwo w starszym rodzenstwie (to tylko tak zawile napisane). Wskaznik na dziecko w naszym rodzicu jest ustawiany na nas.

Funkcje systemowe


Wprowadzenie

Glowna funkcja jest do_fork(). Istnieje do niej interfejs w postaci trzech funkcji: fork(), vfork() oraz clone(). Biblioteka libc zapewnia, ze fork() z poziomu C wywoluje funkcje sys_fork(), vfork()w Linuxie jest po prostu inna nazwa fork-a, natomiast clone() powoduje wolanie funkcji sys_clone() w jadrze. Obie te funkcje mozna obejrzec tutaj, ich tresc sprowadza sie do odpowiedniego wywolania funkcji do_fork().


Funkcje fork() i vfork()

Funkcja tworzy proces-potomka, ktory rozni sie od rodzica tylko pid-em i ppid-em i faktem, ze informacje statystyczne sa wyzerowane. 

DEFINICJE: pid_t  fork(void)
           pid_t vfork(void)
    WYNIK: identyfikator nowego procesu w procesie-rodzicu,
           0 w procesie-dziecku
           -1, gdy blad: errno = EAGAIN (brak pamieci)
Funkcja jest bezargumentowa. Funkcja nie zwraca nigdy ENOMEM.

Intencja, jaka przyswiecala wprowadzeniu funkcji vfork() byly oszczednosci czasowe i pamieciowe. Funkcja ta pojawila sie w systemie BSD, gdy nie bylo mozliwe stosowanie techniki copy on write, a fork() kopiowal fizycznie pamiec procesu macierzystego. vfork()nie kopiowal pamieci i dziecko dzialalo w przestrzeni adresowej rodzica. Projektanci zakladali, ze bezposrednio po vfork() zostanie wykonana jedna z funkcji exec. W Linuxie fork() nie kopiuje fizycznie segmentow pamieci, zaznacza tylko, ze przy modyfikacji beda musialy byc skopiowane. Dokladniej to zagadnienie jest omowione w rodziale o zarzadzaniu pamiecia. Zatem fork() ogranicza sie jedynie do skopiowania kilku struktur systemowych i dzieki temu jest wykonywany szybko. W Linuxie vfork() jest tym samym co fork().


Wsparcie dla watkow - funkcja clone()

Funkcja ta umozliwia w pelni wykorzystanie mocy do_fork-a. Umozliwia klonowanie, czyli wspoldzielenie, przez ojca i potomka pewnych zasobow (jednego lub wielu) - pamieci, tablicy deskryptorow, tablicy obslugi sygnalow a nawet - uwaga! - idetyfikatora. W ten sposob, trzeba przyznac - bardzo sprytny, sa wspomagane w Linuxie watki. Jednak aby funkcje mozna bylo wywolac (domyslnie jest ona niedostepna), trzeba skompilowac jadro ze zdefiniowanym symbolem CLONE_ACTUALLY_WORKS_OK. 

DEFINICJA: pid_t clone(void *sp, unsigned long flags)
    WYNIK: identyfikator nowego procesu w procesie-rodzicu,
           0 w procesie-dziecku
           -1, gdy blad: errno = EAGAIN (brak pamieci)
                                 ENOSYS (nie ma wkompilowanej
                                          tej funkcji w jadro)
Jesli sp jest rozne od NULL, to wskaznik ten jest uzywany jako poczatkowy wskaznik stosu dziecka. Pole flags okresla, co chcemy klonwac, a najmlodszy bajt mowi, jakie sygnaly wyslemy do ojca podczas naszej smierci. Wywolanie clone(0,SIGCHLD|COPYVM) jest rownowazne fork-owi.


Implementacja - funkcja do_fork()

Funkcja jest 'porzadna', tj. sprzata po sobie w razie jakiegokolwiek niepowodzenia. Efekt ten jest uzyskany poprzez skoki do odpowiednich fragmentow kodu. Zwalnianie pamieci odbywa sie w kolejnosci odwrotnej do jej przydzialu, co nie tylko upraszcza implementacje sprzatanie, ale jest takze, tak sie przynajmnie wydaje, bezpieczniejsze.

Najpierw alokowana jest pamiec na strukture task_struct, do ktorej wskaznik zostanie umieszczony potem w tablicy procesow. Nastepnie jest przydzielana pamiec na stos jadra, a potem wyszukiwany za pomoca find_empty_process() wolny indeks w tablicy procesow. Potem fork() inicjuje wartosci struktury nowego procesu. Zaznaczany jest miedzy innymi fakt, ze proces jest nowy i nie wykonal jeszcze exec-a, oraz, ze procesu nie mozna wyrzucic z pamieci oraz go przerwac. Przyznawany jest pid procesu i inicjowany zegar. Po takiej wstepnej inicjacji proces jest wstawiany do tablicy procesow, a za pomoca makra SET_LINKS tworzone sa dowiazania do przodkow i sasiadow w tablicy procesow.

W nastepnej kolejnosci kopiowana jest informacja o deskryptorach plikow (wywolanie copy_files()) i modyfikowane informacje systemowe. Potem wywolywana jest funkcja copy_fs(), nastepnie kopiowane za pomoca copy_signhand() handlery sygnalow i wreszcie segmenty pamieci ( copy_mm()). Nastepnie dzialajaca na bardzo niskim poziomie funkcja copy_thread() powoduje 'fizyczne rozdzielenie' procesow macierzystego i nowo tworzonego, po czym proces oznaczany jest jako 'swappable' i budzony przez wake_up_process(). copy_thread() powoduje, ze proces potomny ma wrazenie, jakby wykonywal funkcje systemowa fork() i nastepna instrukcja bedzie instrukcja powrotu z wykonania funkcji systemowej z kodem 0. Dzieki temu fork() zwraca w przypadku procesu macierzystego pid dziecka, a w przypadku dziecka - 0.

Kod wake_up_process ogranicza sie do zmiany flagi procesu na TASK_RUNNING oraz ewentualnym dodaniu do kolejki procesow oczekujacych na wykonanie.

W pseudokodzie wyglada to nastepujaco: 

{
   w razie jakichkolwiek niepowodzen zwolnij pamiec i zwroc blad EAGAIN;
   przydziel pamiec na strukture task_struct;
   przydziel pamiec na stos kontekstu jadra;
   znajdz wolne miejsce w tablicy procesow sprawdzajac, czy nie sa
          przekraczane limity;
   skopiuj informacje aktualnego procesu do task_struct nowego procesu
         i w nastepnych krokach zmieniaj te, ktore wymagaja zmian;
   zanotuj informacje, ze nowy proces nie wykonywal exec;
   przydziel identyfikator nowemu procesowi;
   wstaw proces do tablicy procesow, dokonujac odpowiednich manipulacji 
         wskaznikami;
   kopiuj informacje o plikach, systemie plikow, handlerach sygnalow
         i pamieci;
   dokonaj odpowiedniego wpisu na stos jadra dziecka, aby symulowal
         powrot z wywolania funkcji systemowej z wynikiem 0;
   obudz nowy proces-dziecko - wstaw go do kolejki procesow gotowych
         do wykonania;
   wroc z funkcji zwracajac identyfikator dziecka;
}

Bibliografia

  1. Pliki zrodlowe Linuxa:
  2. Maurice J. Bach: Budowa systemu operacyjnego UNIX, wyd. II, WNT 1995, ISBN 83-204-2015-6
  3. Michael K. Johnson: The Linux Kernel Hackers' Guide, Alpha version 0.6

Pytania i odpowiedzi

  1. Jakie znalezione w plikach zrodlowych rozwiazanie programistyczne uwazaja Panstwo za najciekawsze?
     
    Moim zdaniem ciekawym i wartym zapamietania rozwiazaniem programistycznym jest sposob przydzielania i zwalniania pamieci w razie bledu w funkcji do_fork(). Spojrzmy na koniec tej funkcji - sa tam etykiety, do ktorych skacze sie w razie bledu. Zwalnianie pamieci odbywa sie w kolejnosci odwrotnej do jej przydzielania. W ten sposob kod zwalniajacy pamiec jest krotki, przejrzysty i latwy do modyfikacji. Standardowo rzadko stosuje sie tak dokladne 'sprzatanie po sobie', bo Linux zapewnia odlaczanie segmentow pamieci w przypadku zakonczenia programu, jednak do dobrego tonu nalezy zwalnianie wszystkich zasobow. Wymuszal to np. system operacyjny komputera Amiga - pamiec musiala byc zwalniana przez program, inaczej po jakims czasie zaczynalo w systemie brakowac pamieci. Powyzsza procedura to takze przyklad na eleganckie (i przejrzyste!) zastosowanie goto do obslugi sytuacji awaryjnych.

Pytaniem cichym, jak sie domyslam, i przez dlugi czas pozostajacym bez odpowiedzi, bylo westchnienie wspolprowadzacego ze mna cwiczenia Grzeska, ktory pytal sam siebie: "Kiedy ta gadula wreszcie skonczy?". Innych zapytan nie bylo, ale mozna mi je zadawac via e-mail. :-)

Autor: Tomasz Blaszczyk