2.1.1 Tworzenie procesu - algorytm fork (2024)

Spis tresci

• Wprowadzenie
• Struktury danych: wprowadznie, task_struct, files_struct, fs_struct, mm_struct, signal_struct
• Procedury pomocnicze: wprowadzenie, find_empty_process(), get_pid(), dup_mmap(), copy_mm(), copy_fs(), copy_files(), copy_sighand(), makro SET_LINKS()
• Funkcje systemowe: wprowadzenie, fork() oraz vfork(), clone() - wsparcie dla watkow, implementacja - do_fork(),
• Bibliografia
• Pytania i odpowiedzi

Wprowadzenie

Funkcja systemowa fork() jest jedna z najwazniejszych funkcjiw systemach unixowych, takze w Linuxie. Za jej sprawa, i tylko zajej 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();

Struktury danych

Wprowadzenie

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

fork() wykorzystuje do swoich dzialan glownie systemowatablice 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. dlaprocesow gotowych do wykonania i wszystkich procesow) oraz drzewo genealogiczne.Dzialanie omawianej funkcji fork()sprowadza sie do wpisanianowych informacji do powyzszej tablicy i zapewnienia spojnosci danych podokonaniu wpisu.

W Linuxie moze byc uruchomionych maksymalnie NR_TASKSprocesow. Root moze wszystko - nie ma nakladanych na niego zadnychograniczen, oprocz powyzszej liczby. Zwykly uzytkownik moze uruchomic maksymalnie MAX_TASKS_PER_USER procesow, ale w systemiemusi zawsze zostac przynajmniej MIN_TASKS_LEFT_FOR_ROOTpozycji 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 oprocesie.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 */};

Struktura files_struct

Struktura files_struct dotyczy informacji o plikach uzywanychprzez pojedynczy proces. Jak prawie kazda struktura dotyczaca informacjio procesie, tak i ta zawiera licznik odwolan do niej, umozliwiajacwspoldzielenie 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 */};

Struktura fs_struct

Ta stuktura zawiera informacje o masce praw dostepu dla nowo tworzonychprzez uzytkownika plikow (umask), oraz wskazniki do dwoch i-wezlow:wezla naszego katalogu glownego (ktory mozemy zmieniac przezchroot()) oraz katalogu, w ktorym sie aktualnie znajdujemy.Dzieki temu system wie, gdzie jestesmy i nie pozwoli innemu procesowi usunacnaszego 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 */};

Struktura mm_struct

Ta struktura jest bardzo skomplikowana i powinna byc w calosci omowiona wtemacie 4. Dosc powiedziec, ze struktura tazawiera ona m. in. nastepujace informacje: o aktualnym kontekscie procesu, poczatku i koncu jego segmentukodu, danych, parametrow wywolania, przekazanego srodowiska shellowego,informacje o segmencie stosu, poczatku tablicy stron, oraz informacje opamieci wirtualnej procesu. Jedyna interesujacanas informacja jest to, ze ta struktura takze moze byc wspoldzielonaprzez kilka procesow (zob. pole count wdefinicjistuktury).

Struktura signal_struct

Struktura signal_struct to wlasciwie tablica funkcjiobslugujacych sygnaly, uzupelniona o dodatkowe, nieistotne dla nas,informacje.Jej pelnadefinicja jest bardzo krotka:

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

Procedury pomocnicze

Wprowadzenie

Ponizsze procedury nie sa bezposrednio dostepne dla programisty. Sa towlasciwie czesci procedury do_fork() i zdefiniowane saw pliku kernel/fork.c,oprocz makra SET_LINKS, ktorego definicje mozna znalezc wpliku include/linux/sched.h. Omowione zostana krotka w takiejkolejnosci, w jakiej wystepuja w fork.c. Ich dokladnadefinicje, czyli typy parametrow i typ zwracanej wartosci, moznazobaczyc ogladajac zrodla. Funkcje o prefiksie copy_ zwracaja0 w przypadku sukcesu, -1 w przypadku bledu (najczesciej blad brakupamieci). Wszystkie one umozliwiaja klonowanie - wtedy jest zwykle tylkozwiekszany licznik odwolan do danej struktury.

Funkcja find_empty_process()

Funkcja najpierw sprawdza, czy mozna jeszcze w gole uruchomic jakisnowy proces. Sa zadeklarowane dwie wartosci w pliku include/linux/tasks.h: NR_TASKS okreslajaca liczbezadan w systemie i MAX_TASKS_LEFT_FOR_ROOT. Byla o nic mowa wewprowadzeniu do struktur danych.Jesli nie jestesrootem, a liczba zadan w systemie jest wieksza niz roznica miedzy powyzszymiwartosciami, to funkcja zwraca -EAGAIN. Nastepnie, jesli nie jestesrootem, funkcja sprawdza, czy nie przekroczyles ustalonej dla ciebie liczbyzadan. Jesli tak, to zwracane jest -EAGAIN. Na koniec przeszukiwanajest globalna tablica zadan task i zwracany indeks pozycji, ktorama wartosc NULL. Jesli nie ma wolnej pozycji, to zwracany jest-EAGAIN.

Funkcja get_pid()

Funkcja zwraca unikatowy identyfikator procesu (o ile nie zazadamyklonowania). Nowy pid jest szukany w ten sposob, ze zwiekszamy ostatnioprzydzielony pid. Jesli pid ma wartosc wieksza lub rowna 0x8000, czyli32768, to nowy pid przyjmuje wartosc 1. Nastepnie jest sprawdzane, czy nowypid nie koliduje z jakimkolwiek pidem, pgrp-idem lub polemsession 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 dodziecka. Kopiowanie odbywa sie za zasadzie copy-on-write, czylijest ustawiany odpowiedni bit na stronach i fizyczne kopiowanie stron odbywasie tylko w przypadku proby zapisu przez ojca lub dziecko czegos na testrony.
Uwaga! Nie mylic tego faktu ze wspoldzieleniem pamieci, kiedyto strony nigdy nie sa kopiowane, a zmiany dokonane w pamieci przez jedenproces sa widoczne dla innego procesu.

Funkcja copy_mm()

Zwykle po przydzieleniu miejsca na strukture opisujace pamiec wywolujedup_mmap(). Zerowane sa dane statystyczne dotyczace dostepu do pamieci (minor and major page faults). Jesli zadamy klonowania pamieci, to segmenty nie sakopiowane, ale procesy moga wspoldzielic pamiec. Struktura wtedy nie jestkopiowana, tylko zwieksza sie licznik odwolan do niej.

Funkcja copy_fs()

Kopiuje strukture fs_struct. Zwieksza liczniki i-wezlowkatalogu glownego oraz aktualnego. W przypadku braku pamieci, zwraca -1. Wprzypadku klonowania tylko zwieksza licznik odwolan do struktury.

Funkcja copy_files()

Kopiuje prywatna tablice deskryptorow plikow procesu, zwieksza licznikiodwolan do i-wezlow plikow opisywanych przez deskryptory. Jezeli zadamy klonowania,to tablica deskryptorow nie jest kopiowana, ale wspoldzielona (zwieksza sielicznik odwolan do niej). Liczniki i-wezlow zwiekszaja sie zawsze.

Funkcja copy_sighand()

Kopiuje procedury obslugi poszczegolnych sygnalow. Mozliwe jesttakze wspoldzielenie tablicy obslugi sygnalow - wtedy zwieksza sie tylkolicznik 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 wskaznikna 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 interfejsw postaci trzech funkcji: fork(), vfork() orazclone(). Biblioteka libc zapewnia, ze fork() z poziomu C wywoluje funkcje sys_fork(),vfork()w Linuxie jest po prostu inna nazwafork-a, natomiast clone() powoduje wolaniefunkcji sys_clone() w jadrze. Obie te funkcje mozna obejrzectutaj, ich tresc sprowadza sie do odpowiedniego wywolania funkcjido_fork().

Funkcjefork() i vfork()

Funkcja tworzy proces-potomka, ktory rozni sie od rodzica tylkopid-em i ppid-em i faktem, ze informacjestatystyczne 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)

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 onwrite, a fork() kopiowal fizycznie pamiec procesumacierzystego. vfork()nie kopiowal pamieci i dziecko dzialalow przestrzeni adresowej rodzica. Projektanci zakladali, ze bezposrednio povfork() zostanie wykonana jedna z funkcji exec.W Linuxie fork() nie kopiuje fizycznie segmentowpamieci, zaznacza tylko, ze przy modyfikacji beda musialy byc skopiowane. Dokladniej to zagadnienie jest omowione w rodziale o zarzadzaniu pamiecia. Zatemfork() ogranicza sie jedynie do skopiowania kilku struktursystemowych i dzieki temu jest wykonywany szybko. W Linuxievfork() jest tym samym co fork().

Wsparcie dla watkow - funkcjaclone()

Funkcja ta umozliwia w pelni wykorzystanie mocy do_fork-a.Umozliwia klonowanie, czyli wspoldzielenie, przez ojca i potomka pewnychzasobow (jednego lub wielu) - pamieci, tablicy deskryptorow, tablicyobslugi sygnalow a nawet - uwaga! - idetyfikatora. W ten sposob, trzebaprzyznac - bardzo sprytny, sa wspomagane w Linuxie watki. Jednakaby funkcje mozna bylo wywolac (domyslnie jest ona niedostepna), trzebaskompilowac jadro ze zdefiniowanym symbolemCLONE_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)

Implementacja - funkcjado_fork()

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

Najpierw alokowana jest pamiec na strukturetask_struct,do ktorej wskaznik zostanie umieszczony potem w tablicy procesow. Nastepniejest przydzielana pamiec na stos jadra, a potem wyszukiwany za pomocafind_empty_process() wolny indeks w tablicy procesow. Potemfork() inicjuje wartosci struktury nowego procesu. Zaznaczany jestmiedzy innymi fakt, ze proces jest nowy i nie wykonal jeszczeexec-a, oraz, ze procesu nie mozna wyrzucic z pamieci oraz goprzerwac. Przyznawany jest pid procesu i inicjowany zegar. Po takiejwstepnej inicjacji proces jest wstawiany do tablicy procesow, a za pomoca makraSET_LINKS tworzone sa dowiazania do przodkow i sasiadow wtablicy procesow.

W nastepnej kolejnosci kopiowana jest informacja o deskryptorach plikow(wywolaniecopy_files()) i modyfikowane informacje systemowe. Potemwywolywana jest funkcjacopy_fs(), nastepnie kopiowane za pomocacopy_signhand() handlery sygnalow i wreszcie segmenty pamieci(copy_mm()). Nastepnie dzialajaca na bardzo niskim poziomie funkcjacopy_thread() powoduje 'fizyczne rozdzielenie' procesowmacierzystego i nowo tworzonego, po czym proces oznaczany jest jako'swappable' i budzony przezwake_up_process(). copy_thread() powoduje, ze proces potomny ma wrazenie, jakby wykonywal funkcje systemowa fork()i nastepna instrukcja bedzie instrukcja powrotu z wykonania funkcjisystemowej z kodem 0.Dzieki temu fork() zwraca wprzypadku procesu macierzystego pid dziecka, a w przypadku dziecka - 0.

Kod wake_up_process ogranicza sie do zmiany flagi procesu naTASK_RUNNING oraz ewentualnym dodaniu do kolejki procesowoczekujacych 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:
   • include/linux/tasks.h - definicje stalych
   • include/linux/sched.h - definicje stalych, struktur i makra SET_LINKS
   • include/asm-i386/signal.h - struktura sigaction
   • kernel/sched.c - funkcja wake_up_process()
   • kernel/fork.c - glowny plik z do_fork() i funkcjami pomocniczymi
   • arch/i386/kernel/process.c - interfejs: funkcje sys_fork() oraz sys_clone()
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 programistyczneuwazaja Panstwo za najciekawsze?
   
   Moim zdaniem ciekawym i wartym zapamietania rozwiazaniem programistycznymjest sposob przydzielania i zwalniania pamieci w razie bledu w funkcji do_fork().Spojrzmy na koniec tej funkcji - sa tam etykiety, do ktorych skacze siew razie bledu. Zwalnianie pamieci odbywa sie w kolejnosci odwrotnej dojej przydzielania. W ten sposob kod zwalniajacy pamiec jest krotki,przejrzysty i latwy do modyfikacji. Standardowo rzadko stosuje sie takdokladne 'sprzatanie po sobie', bo Linux zapewnia odlaczanie segmentowpamieci w przypadku zakonczenia programu, jednak do dobrego tonu nalezyzwalnianie wszystkich zasobow. Wymuszal to np. system operacyjny komputeraAmiga - pamiec musiala byc zwalniana przez program, inaczej po jakims czasiezaczynalo w systemie brakowac pamieci. Powyzsza procedura to takze przykladna eleganckie (i przejrzyste!) zastosowanie goto do obslugisytuacji awaryjnych.

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