Fork


Do strony głównej
Algorytm fork


Spis treści:


Fork dla poczÄ…tkujÄ…cych


Co warto wiedzieć przed rozpoczęciem analizy algorytmu i kodu
źźródłowego


Algorytm fork


Funkcja vfork


Funkcja clone


Dla zainteresowanych


Skomentowany kod źźródłowy


Bibliografia





Fork dla poczÄ…tkujÄ…cych


Fork jest jedną z najważniejszych funkcji
systemowych. Jej zadaniem jest powołanie do życia nowego procesu na zasadzie
relacji rodzic - dziecko. Proces, w którego kodzie znajdzie się wywołanie
tej funkcji, staje sie ojcem nowego procesu.

Wykorzystanie funkcji fork w programie,
a w konsekwencji powstanie nowego procesu następuje w wyniku wykonania
kodu:
pid = fork ();


Po wykonaniu tej instrukcji w systemie będą już istnieć dwa osobne procesy
- ich odróżnienie w programie jest możliwe dzięki wartośści zwracanej przez
funkcję fork - procesowi macierzystemu zwrócony
zostanie identyfikator syna, procesowi potomnemu - zero.  Gdy system
uzna, że nowego procesu nie da się utworzyć (na przykład z powodu braku
pamięci lub przekroczenia limitów na liczbę istniejących procesów), funkcja
fork zwróci wartośść -1
i, oczywiśście, nie powstanie żaden nowy proces.

Początkującym badaczom Linuksa sprawia często problem zrozumienie, w
jaki sposób z jednego powstają nagle dwa procesy, jak skorzystać z istnienia
nowego procesu i jaki kod będzie on wykonywać -
wywołanie funkcji jest
przecież częśścią kodu wcześśniej napisanego i skompilowanego programu.
Możemy jednak przecież już w chwili kompilacji okreśślić kod obu procesów

- "starego" i "nowego", ojca i syna, i rozdzielić je w dowolnej chwili,
wywołując właśśnie funkcję fork, na przykład
tak:
main ()
{ ...
// jakieśś działania naszego programu
  ...
// chcemy, by powstał nowy proces
  switch (fork ())
  { -1:
...
// działania podejmowane w przypadku błędu
- nowy proces nie powstał

     0:
...
// tu umieśścimy kod, który ma wykonać nowo utworzony proces

    default:
...
// tutaj zaśś -  dalszy kod ojca, czyli procesu, który uruchomiliśśmy

  }
}
Jeśśli kod programu, który ma wykonać nowo utworzony proces, jest dla nas
zbyt długi lub z innej przyczyny chcemy go umieśścić w innym miejscu jako
osobny program, to po wywołaniu fork możemy
polecić synowi wykonanie tego wcześśniej napisanego i skompilowanego kodu,
podajÄ…c funkcji exec nazwÄ™ zawierajÄ…cego
go programu.

Wywołanie fork jest jedynym sposobem na
stworzenie nowego procesu w systemie. Wyjatkiem od zasady rozwidlania procesów
jest sposób powstawania procesu wymiany (o identyfikatorze zero), inicjowanego
wewnętrznie przez jądro podczas ładowania systemu do pamięci (po włączeniu
komputera). Jest on przodkiem wszystkich innych procesów działających w
systemie.
 




Co warto wiedzieć przed rozpoczęciem analizy algorytmu i jego
kodu źródłowego


Aby dowiedzieć się, jak działa funkcja fork,
nieobce muszą być Czytelnikowi pojęcia: identyfikator procesu, kontekst
procesu, stan procesu, stos jądra, tablica procesów
- nie ma tu miejsca,
by je wszystkie wyjaśśniać; warto przeczytać wcześniej garśść najważniejszych
informacji o procesach w systemie Linux w jednym z szeroko dostępnych źźródeł
(na przykład w rozdziale 2.2.2 książki Bacha, wymienionej
w bibliografii).

Do zrozumienia kodu funkcji fork niezbędna
jest poza powyższym znajomośść struktur, z jakich korzysta algorytm, co
wiąże się z (choćby podstawową) znajomośścią sposobu, w jaki system przechowuje
informację o procesach oraz jak z tej informacji korzysta. Dla przykładu,
powinieneśś wiedzieć, że każdemu procesowi odpowiada wypełniona struktura
task_struct, zawierajÄ…ca jego podstawowe
dane, a jÄ…dro utrzymuje tablicÄ™ takich struktur, przechowujÄ…c w niej informacjÄ™
o procesach dziaÅ‚ajÄ…cych w systemie.  Opis pól struktury task_struct
i innych, ważnych z punktu widzenia analizy kodu, można znaleźźć w omówieniu
struktur danych; bardziej szczegółowe informacje - bezpośśrednio w komentarzu
do kodu źźródłowego funkcji.

Warto również zdawać sobie sprawę z ograniczeń nakładanych przez system
na rozmiar pewnych struktur i ich liczbę - częśść z nich (na przykład definicję
ograniczenia na liczbę procesów w systemie i maksymalną liczbę zadań, jakie
może uruchomić pojedynczy użytkownik) zawiera plik tasks.h.
 



Algorytm fork
Wejśście:    brak
Wyjśście:    w procesie macierzystym: PID potomka,
                   
w procesie potomnym: 0,
                   
w przypadku błędu (nie powstaje nowy proces): -1

{
przygotuj strukturę, która będzie zawierać informację o nowo utworzonym
procesie, przydziel jej odpowiednią ilośść pamięci;

przydziel pamięć dla stosu jądra nowego procesu (operacje wymagające
przydziału pamięci wykonywane są na początku algorytmu, aby już teraz wykluczyć
ewentualną niemożnośść utworzenia procesu z tak prozaicznej przyczyny jak
brak pamięci);

sprawdźź dostępnośść zasobów jądra, czyli warunków na ograniczenia systemowe
na liczbę procesów w systemie i dla danego użytkownika;

znajdźź wolną pozycję w tablicy procesów;

skopiuj stos jądra procesu macierzystego do przygotowanego w pamięci
miejsca na stos jÄ…dra potomka, by nowy proces mógÅ‚ poprawnie “powrócić
z forka" (to tylko jego złudzenie wywołane
i kontrolowane przez jÄ…dro -
przecież nowy proces dopiero powstaje);

zaznacz, że proces jest w stanie “"tworzony"";

skopiuj dane ze struktury opisujÄ…cej proces macierzysty do struktury
procesu potomnego
- późźniej zmienimy jedynie wartośści tych pól, które
w procesie potomnym są inne niż w procesie macierzystym;

ustal unikatowy identyfikator nowego procesu (pid);

skopiuj od ojca informację o deskryptorach otwartych plików;

skopiuj informację o katalogu procesu oraz masce praw dostępu nadawanych
nowo tworzonym plikom;

skopiuj informację o obsłudze sygnałów;

skopiuj informację dotyczącą struktur pamięci procesu;

ustal “rodzinne" dowiÄ…zania miÄ™dzy nowym procesem a innymi procesami
z drzewa zadań;

wstaw strukturę opisującą nowy proces do tablicy procesów;

rozwidl fizycznie procesy ojca i syna;

if (wykonywany proces jest procesem macierzystym)
{
zmieÅ„ stan potomka na “gotowy do wykonania";
return (pid potomka);
}
else
{
return (0);

            
}
}

W przypadku błędu w którejkolwiek z częśści funkcji, spowodowanej przekroczeniem
ograniczeń systemowych bądźź brakiem pamięci, struktury zainicjowane do
tej pory sÄ… kaskadowo niszczone.
Informacje o szczegółach algorytmu znajdziesz w komentarzu
do kodu źźródłowego funkcji fork.
 



Funkcja vfork


Stworzenie osobnej funkcji do rozwidlania procesów, vforka
właśnie, miało na celu przyspieszenie zakończenia jego wywołania przez
całkowita rezygnację z tworzenia fizycznych kopii stron pamięci procesu
macierzystego. Zakładano przy tym, że proces-dziecko zaraz po powrocie
z vforka wywoła jedną z funkcji exec
- w tym wypadku kopiowanie stron jest po prostu bezcelowe (i
tak zaraz załaduje się nowy program i przed chwilą skopiowane dane zostaną
zamazane). Takie pobożne życzenie (nie sposób bowiem zmusić procesu do
wywołania exec) może jednak doprowadzić do
niebezpieczeństwa - potomek, wykonując się w przestrzeni adresowej ojca
ma dostęp do jego segmentu danych i stosu, może je więc z łatwośścią zmienić.

System, w którym zastosowano vforka, to
Unix BSD - "zwykły" fork w tym systemie fizycznie
kopiował strony procesu macierzystego, nowe rozwiązanie było więc znacznym
usprawnieniem. W Linuksie vfork jest równoważny
forkowi - zarządzanie pamięcią z zastosowaniem
kopiowania dopiero w chwili zapisu do powielonej strony (copy-on-write)
sprawiło, że implementacja osobnej funkcji stała się zbędna.





Funkcja clone


Warto przy opisie forka wspomnieć również
o funkcji clone, posiadającej co prawda własny
(zarezerwowany) numer w tablicy funkcji systemowych, ale domyśślnie niedostępnej
(aby z niej skorzystać, trzeba zrekompilować jądro ze zdefiniowanym symbolem
CLONE_ACTUALLY_WORKS_OK).

Funkcja ta jest rozszerzeniem forka o
mozliwośść klonowania zasobów procesu, czyli udostępnienia synowi takich
zasobów ojca jak segmenty pamięci, tablice deskryptorów plików i obsługi
sygnałów, a nawet identyfikator procesu (pid).

Wywołanie funkcji wymaga podania owych atrybutów klonowania, a także
(opcjonalnie) wskaźźnika stosu dziecka:
pid_t clone (void* sp, unsigned long flags)


sp to właśnie ów wskaźźnik (NULL
wymusza obsługę standardową), zaśś pole flags
zawiera jedno lub wiele poleceń klonowania:


COPYVM - strony pamięci dziecka są kopią stron ojca (z zastosowaniem kopiowania
przy zapisie); jeśśli bit nie ustawiony - dziecko dzieli strony z ojcem;


COPYFD - deskryptory plików dziecka są kopiami deskryptorów ojca, w przeciwnym
przypadku dziecko dzieli deskryptory z ojcem.

Najmłodszy bajt pola okreśśla sygnał wysyłany do rodzica w chwili śśmierci
dziecka.

Jako że funkcja sys_clone realizująca
wywołanie clone korzysta z funkcji do_fork
(patrz: komentarz do kodu źźródłowego),
można używać clone jak standardowego forka
- wywołanie miałoby wówczas postać:
clone (0, SIGCHLD | COPYVM).
 





Dla zainteresowanych


Funkcje systemowe istnieją wewnątrz jądra jako zwykłe funkcje C, z tym,
że ich “"oficjalne"" nazwy poprzedzone sÄ… prefiksem sys_
(to duże uproszczenie, wywołanie wymaga jeszcze skorzystania z makra sys_call,
wyszukujÄ…cego funkcjÄ™ w bibliotece oraz odpowiedniego obsÅ‚użenia parametrów). 
Skorzystanie z forka polega zatem na wywołaniu
funkcji jÄ…dra sys_fork (jednolinijkowej,
plik process.c), która z kolei wywoła właśściwą
treść forka - do_fork

- tak właśśnie nazywa się funkcja zawierająca cały algorytm; nie warto
szukać definicji funkcji nazwanej fork, gdyż
takiej definicji po prostu nie ma.

Po analizie funkcji fork na pewno warto
przeczytać również rozdział dotyczący funkcji exit,
będącej niejako odwrotnośścią forka. Analiza kodu exit
pozwala docenić prostotę forka
i wspomagających go rozwiązań (np. zastosowania makra-pętli for_each_task,
dającej się łatwo zastąpić mądrzejszym algorytmem, ale eliminującej nie
zawsze potrzebne dodatkowe struktury i symetrię w ich wypełnianiu na rzecz
jednorazowego przejrzenia listy zadań w chwili tworzenia procesu).

Bardziej zainteresowanych działaniem vforka
odsyłam na strony 314 i 332 książki Bacha. Można tam znaleźźć
kod i komentarz do programów, wykorzystujących niebezpieczne własnośści
vforka.

Więcej informacji o funkcji clone, dokładny
wykaz plików i parametrów można uzyskać w dokumentacji (man
clone).
 




Bibliografia



Pliki źźródłowe Linuxa:



kernel/fork.c

- definicja funkcji do_fork()
oraz wykorzystywanych przez niÄ… funkcji pomocniczych,


include/linux/sched.h
- definicje wszystkich
najważniejszych z punktu widzenia zarządzania procesami struktur i makr,
w tym struktury task_struct, makr SET_LINKS,
REMOVE_LINKS itp.


include/linux/tasks.h - definicje stalych
odpowiadających za ograniczenia na liczbę uruchomionych procesów;


include/linux/errno.h
- kody błędów systemowych.



Linux Manual



fork (man fork),


clone (man clone).



Maurice J. Bach: Budowa systemu operacyjnego UNIX, wyd.
II, WNT 1995.


Tour of the Linux kernel source by Alessandro Rubini (aktualnie niedostępny
w sieci).


Projekt Linux

- zwłaszcza rozdział
dotyczÄ…cy algorytmu fork autorstwa Tomasza
BÅ‚aszczyka.



Maciej Ogrodniczuk

26 stycznia 1998 r.