Systemy operacyjne 2020 - listy zadań 0-3

Lista zadań nr 0

Przed rozpoczęciem rozwiązywania zadań warto przeczytać o wstępie do Systemów Operacyjnych i rozdziały 7.8, 7.9, 8.1, 9.7 z CS:APP.

Zadanie 1

Opisz różnice między przerwaniem sprzętowym (ang. hardware interrupt), wyjątkiem procesora (ang. exception) i pułapką (ang. trap). Dla każdego z nich podaj co najmniej trzy przykłady zdarzeń, które je wyzwalają. W jakim scenariuszu wyjątek procesora nie oznacza błędu czasu wykonania programu? Kiedy pułapka jest generowana w wyniku prawidłowej pracy programu?

Wyjątek procesora to klasa, która dzieli się na cztery rodzaje. Są nimi:

• przerwanie sprzętowe wywoływane jest przez sygnał z urządzeń wejścia i wyścia (I/O), są one asynchroniczne, a więc nie są spowodowane przez wykonywanie instrukcji w CPU, a wywoływane przez hardware. Wywołują je akcje takie jak ruszenie myszką (na PS/2), naciśnięcie przycisku, otrzymanie danych z karty sieciowej (i wiele innych spowodowanych przez interakcję z urządzeniami I/O).
  
  
• fault jest wynikiem instrukcji, która może zostać naprawiona przez exception handler - jeśli jest on w stanie ją naprawić, to wraca do instrukcji i wyknouje ją ponownie, w przeciwnym wypadku przekazuje tę instrukcję do aborta. Wywołać go mogą dzielenie przez 0, segmentation fault, page fault.
  
• abort jest wynikiem instrukcji nienaprawialnej. Wywołać go może machine check na hardware, np. w pamięci, magistrali systemowej lub procesorze. W systemach Windows przy aborcie włącza się BSOD.
  
• pułapka (ang. trap) to wyjątek uzyskany celowo (synchroniczny), który jest wynikiem wykonywanej instrukcji. Zdarza się wtedy, gdy user żąda usługi z jądra. Wtedy poprzez specjalne api (wrapper) wywoływany jest system call. Przykładami mogą być fork, execve, exit. Korzysta z nich też każdy debugger, np. dla breakpointów.
  

Różnica między zwykłą funkcją a syscall jest taka, że zwykła funkcja wykonywana jest w user mode, a syscall w kernel mode. Wyjątki asynchroniczne (a więc przerwania sprzętowe) nie powodują przerwania działania programu.

Zadanie 2

Opisz mechanizm obsługi przerwań bazujący na wektorze przerwań (ang. interrupt vector table). Co robi procesor przed pobraniem pierwszej instrukcji procedury obsługi przerwania (ang. interrupt handler) i po natrafieniu na instrukcję powrotu z przerwania? Czemu procedura obsługi przerwania powinna być wykonywana w trybie jądra (ang. kernel mode) i używać stosu odrębnego od stosu użytkownika?

Aby obsłużyć przerwanie, kontroler umieszcza numer na linii adresowej, okręslając które urządzenie wymaga uwagi i ustawia sygnał mający na celu przerwanie pracy procesora.

Sygnał przerwania powoduje, że procesor zatrzymuje operację, którą wykonywał, i zaczyna robić coś innego. Numer na liniach adresowych jest wykorzystywany jako indeks do tabeli znanej jako wektor przerwań i służy do pobrania nowej wartości licznika programu (PC). Zwykle przerwania są numerowane od 0 do 255 (używamy więc 1 bajta). Ta wartość PC wskazuje na początek odpowiedniej procedury obsługi przerwania (zwykle jump, aby zaoszczędzić liczbę wykonywanych instrukcji). Zazwyczaj od tego momentu rozkazy pułapek i przerwań korzystają z tego samego mechanizmu, a często współdzielą ten sam wektor przerwań. Wektor ten może być zaszyty "na sztywno" w sprzęcie lub może znajdować się w dowolnym miejscu pamięci, a rejest procesora wskazuje na jego początek.

Procedura obsługi przerwania to kod mający na celu obsługę konkretnego sygnału żądania przerwania, najczęściej określa je system operacyjny lub BIOS.

Przed uruchomieniem procedury obsługi przerwania sprzęt zawsze zapisuje pewne informacje, ich rodzaj i miejsce zapisu różnią się w zależności od procesora. Całkowitym minimum jest zapisanie PC, dzięki czemu można wznowić przerwany proces. W drugim skrajnym podejściu zapisywane są wszystkie widoczne rejestry, a także wiele rejestrów zewnętrznych.

Wyjątek jest bardzo zbliżony do zwykłej procedury, działa on jednak w trybie jądra, aby mieć dostęp do wszystkich zasobów systemowych. Bez tego np. page fault nie działa, ponieważ wpisuje on na dysk fizyczny, a user mode tego nie może zrobić.

Jeżeli do zapisu wykorzystywany jest stos, może narodzić się problem jakiego stosu użyć. Jeżeli zostanie wykorzystany bieżący stos, może być to stos należący do procesu użytkownika, a wartość wskaźnika stosu może być nieprawidłowa, co doprowadzi do błędu krytycznego, gdy sprzęt podejmie próbę zapisania pewnych słów pod wskazanym adresem. Dlatego korzysta się więc ze stosu jądra, gdyż istnieje wtedy większa szansa na to, że wskaźnik stosu będzie miał prawidłową wartość i będzie wskazywał na stronę dostępną w pamięci. Przełączenie do trybu jądra może jednak wymagać zmiany kontekstu MMU i prawdopodobnie spowoduje utratę ważności dużej części lub całości pamięci podręcznej oraz buforów TLB. Ponowne załadowanie tych danych zwiększa czas obsługi przerwania, przez co przyczyni się do marnotrastwa czasu procesora.

Kiedyś, np. w procesorach Intel 8080 nie używano stosu, a dwa rejestry: jeden systemowy, a drugi do obsługi przerwań.

Tryb jądra (ang. kernel mode) zezwala na zrobienie wszystkiego w systemie, daje dostęp do hardware'u, natomiast tryb użytkownika (ang. user mode) na to nie pozwala, nie możemy np. czytać z pamięci czy do niej zapisywać, uruchomiony kod musi korzystać z API systemu, aby wykonać wspomniane zadania.

Zadanie 3

Bazując na formacie ELF (ang. Executable and Linkable Format) opisz składowe piku wykonywalnego. Czym różni się sekcja od segmentu? Co opisują nagłówki programu? Skąd system operacyjny wie, pod jakim adresem ma umieścić segmenty programu i gdzie położona jest pierwsza instrukcja programu?

• Uzyskanie pliku main.o z pliku main.c bez linkowania:

$ gcc -c main.c

• Wydruk tablicy symboli i nagłówków sesji:

$ readelf -t -s [nazwa].o

Plik relokowalny (ang. relocatable object file) w formacie ELF wygląda w taki sposób:

Rozpoczyna się on 16-bajtową sekwencją zwaną ELF header opisującą wielkość słowa i kolejność bajtów (ang. endianness) systemu, który wygernerował plik. ELF header zawiera również informacje umożliwiające linkerowi spasowanie i zinterpetowanie pliku obiektowego - są to między innymi typ pliku obiektowego, rodzaj architektury, czy rozmiar i liczbę sekcji.

Zwykle plik ELF składa się z następujących sekcji:

Sekcja	Przeznaczenie
.text	Kod maszynowy skompilowanego programu.
.rodata	Dane tylko do odczytu, np. sekwencje znaków niezmienialnych string używanych w funkcji printf oraz tabele skoków dla instrukcji switch.
.data	Zainicjalizowane zmienne globalne oraz static. Lokalne zmienne są trzymane na stosie w trakcie uruchomienia programu (run time) i nie pojawiają się ani w sekcji .data, ani w .bss.
.bss	Niezainicjalizowane zmienne globalne oraz static, włącznie ze zmiennymi zainicjalizowanymi na 0, ta sekcja nie zajmuje miejsca w pliku relokowalnym, jest jedynie placeholderem.
.symtab	Tabela symboli z informacją o funkcjach i zmiennych globalnych, które są zdefiniowane i do których odwołuje się w programie.
.rel.text	Lista lokalizacji z sekcji .text, która zostanie zmodyfikowana w trakcie linkowania tego pliku relokowalnego z innymi. W ogólności instrukcje, które wywołują "zewnętrzne" (ang. external) funkcje lub odwołują się do zmiennych globalnych, będą musiały być zmodyfikowane, jednak funkcje wywoływane lokalnie nie muszą być modyfikowane.
.rel.data	Informacje o relokacji dla zmiennych globalnych, do których występują odwołania lub są zdefiniowane w tym module. W ogólności są to zainicjalizowane zmienne globalne, których wartością początkową jest adres oraz funkcje zdefiniowane "zewnętrznie".
.debug	Lista symboli do debugowania, zawiera lokalne zmienne i definicje typów (typedef), zmienne globalne zdefiniowane przez program i te, do których się odwołuje, jak i oryginalny kod źródłowy w języku C. Aby sekcja ta powstała, należy skompilować program z flagą -g.
.line	Mapowanie pomiędzy liniami z pliku źródłowego a instrukcjami kodu maszynowego z sekcji .text, podobnie pojawia się po użyciu flagi -g.
.strtab	Tablica stringów dla sekcji tabeli symboli .symtab oraz .debug, jak i nazw sekcji w nagłówkach.

Sekcje zawierają informacje potrzebne w trakcie linkowania, a segmenty informacje wykorzystywane w trakcie runtime. Często sobie odpowiadają w pamięci wirtualnej procesu.

System operacyjny wie pod jakim adresem ma umieścić segmenty programu dzięki segment header table. Adres pierwszej instrukcji znajduje się w headerze ELF.

Przykładowy wydruk polecenia readelf -t -s swap.o z jakiegoś zadania z ASKa:

There are 9 section headers, starting at offset 0x1f8:
 
Section Headers:
  [Nr] Name
       Type              Address          Offset            Link
       Size              EntSize          Info              Align
       Flags
  [ 0]
       NULL                   NULL             0000000000000000  0000000000000000  0
       0000000000000000 0000000000000000  0                 0
       [0000000000000000]:
  [ 1] .text
       PROGBITS               PROGBITS         0000000000000000  0000000000000040  0
       000000000000001e 0000000000000000  0                 1
       [0000000000000006]: ALLOC, EXEC
  [ 2] .rela.text
       RELA                   RELA             0000000000000000  0000000000000148  6
       0000000000000060 0000000000000018  1                 8
       [0000000000000040]: INFO LINK
  [ 3] .data
       PROGBITS               PROGBITS         0000000000000000  0000000000000060  0
       0000000000000008 0000000000000000  0                 8
       [0000000000000003]: WRITE, ALLOC
  [ 4] .rela.data
       RELA                   RELA             0000000000000000  00000000000001a8  6
       0000000000000018 0000000000000018  3                 8
       [0000000000000040]: INFO LINK
  [ 5] .bss
       NOBITS                 NOBITS           0000000000000000  0000000000000068  0
       0000000000000004 0000000000000000  0                 4
       [0000000000000003]: WRITE, ALLOC
  [ 6] .symtab
       SYMTAB                 SYMTAB           0000000000000000  0000000000000068  7
       00000000000000c0 0000000000000018  5                 8
       [0000000000000000]:
  [ 7] .strtab
       STRTAB                 STRTAB           0000000000000000  0000000000000128  0
       000000000000001b 0000000000000000  0                 1
       [0000000000000000]:
  [ 8] .shstrtab
       STRTAB                 STRTAB           0000000000000000  00000000000001c0  0
       0000000000000036 0000000000000000  0                 1
       [0000000000000000]:

Zadanie 4

Zapoznaj się z rozdziałami 3.4 i A.2 dokumentu System V Application Binanry Interface AMD64 Architecture Processor Supplement i odpowiedz na następujące pytania:

• W jaki sposób jądro musi przygotować przestrzeń adresową procesu? Co musi się znajdować na stosie w momencie wywołania procedury _start? Do czego służy auxiliary vector? Można go wyświetlić wydając przykładowe polecenie LD_SHOW_AUXV=1 /bin/true.
• W jaki sposób wywołać funkcję jądra? W których rejestrach należy umieścić argumenty? Gdzie można spodziewać się wyników i jak jądro sygnalizuje niepowodzenie wywołania systemowego?

Disclaimer: Warto pamiętać o tym że ABI (Application Binary Interface) i API (Application Programming Interface) to dwie zupełnie różne rzeczy, w ABI są rzeczy takie jak obsługa ramki stosu i inne niskopoziomowe sprawy, a w API są bardziej wysokopoziomowe wywołania, takie jak syscalle do porozumiewania się z innymi programami. ABI x32 pozwala na pracowanie na architekturze 64-bitowej na adresach 32-bitowych, dzięki temu zwiększamy szybkość działania o około 30%.

Przestrzeń adresowa procesu jest przygotowywana w następny sposób: procesor jest resetowany do "czystego" stanu, tzn. wszystkie flagi (CF, ZF, IF, itp.) są wyzerowane.

Auxiliary vector w trakcie uruchamiania programu otrzymuje od systemu operacyjnego informacje o środowisku, w którym ten program będzie działać.

Procedura _start jest entry pointem programu, tzn. adres tego symbolu jest adresem, do którego wykonywany jest skok na początku wykonania programu. Zwykle jest ona zawarta w pliku crt0.o, który zawiera kod startowy dla środowiska C runtime.

syscall to procedura jądra, działa ona podobnie do standardowych funkcji, jednak zamiast jump, używa procedur dla jądra. Jeżeli wynik w %rax będzie w przedziale <-4095, -1>, to syscall zwróci błąd wywołania systemowego.

Zadanie 5

Przypomnij jak wygląda mechanizm tłumaczenia adresów bazujący na wielopoziomowej tablicy stron procesorów z rodziny x86-64. Przedstaw algorytm obliczania adresu fizycznego na podstawie adresu wirtualnego z uwzględnieniem uprawnień dostępu. Jaką rolę w procesie tłumaczenia odgrywa pamięć TLB?

Tłumaczenie adresów to proces znajdowania adresu fizycznego z adresu wirtualnego. Architektura x86-64 używa czteropoziomowej tablicy stron:

63-48	47-39	38-29	29-21	20-12	11-0
	level 4	level 3	level 2	level 1	offset

16 najbardziej znaczących bitów adresu jest nieużywane.

Algorytm translacji dla pojedynczej tabeli stron wygląda następująco:

A dla stron procesów z rodziny x86-64: używamy rejestru %cr3 przechowującego adres fizyczny czwartego poziomu tabeli stron (aby ostatecznie dostać się do adresu, który chcemy). Algorytm ten przebiega w następujący sposób:

1. Używamy %cr3 i indeksu z L4 z wirtualnego adresu aby dotrzeć do poziomu L3 tabeli stron.
2. Używamy adresu tabeli stron L3 i indeksu L3 aby dotrzeć do poziomu L2 tabeli stron.
3. Używamy adresu tabeli stron L2 i indeksu L2 aby dotrzeć do poziomu L1 tabeli stron.
4. Używamy adresu tabeli stron L1 i indeksu L1 aby dotrzeć do żądanego adresu fizycznego.
5. Używamy żądanego adresu fizycznego i przesunięcia (offset) do uzyskania rzeczywistego adresu fizycznego.

Bufor TLB (ang. translation lookaside buffer) (czasami pamięć asocjacyjna) to urządzenie sprzętowe służące do odwzorowywania adresów wirtualnych na fizyczne bez konieczności sięgania do tabeli stron. Zwykle jest ono zlokalizowane wewnątrz jednostki MMU i składa się z niewielkiej liczby pozycji - każda pozycja zawiera informacje dotyczące jednej strony.

Zadanie 6 (rozwiązanie niekompletne)

Uruchom program 1_ls pod kontrolą narzędzia ltrace -S. Na podstawie śladu wykonania programu zidentyfikuj, które z wywołań systemowych są używane przez procedury: opendir, readdir, printf i closedir. Do czego służy wywołanie systemowe brk? Używając debuggera gdb i polecenia catch syscall brk zidentyfikuj, która funkcja używa brk.

Wywołanie systemowe to interfejs pomiędzy wykonywanym programem, a jądrem systemu operacyjnego. Funkcje systemowe wywoływane są przez specjalny mechanizm, wspierany przez dany procesor. Są to między innymi dostęp do systemu plików, komunikacja międzyprocesowa, uruchamianie innych programów, sterowanie urządzeniami systemowymi, obsługiwanie komunikacji sieciowej.

Najpierw robię make w folderze, a później wywołuję poniższe polecenie:

$ ltrace -S ./1_ls libapue/

Na wyjściu otrzymuję mniej więcej taki wydruk (wycięte niepotrzebne linijki):

opendir("libapue/" <unfinished ...>
SYS_openat(0xffffff9c, 0x7fff476df52f, 0x90800, 0)               = 3
readdir(0x55ae2a86a260 <unfinished ...>
SYS_getdents64(3, 0x55ae2a86a290, 0x8000, -2630)                 = 144
SYS_write(1, "libapue.a\n", 10libapue.a
)                                  = 10
<... puts resumed> )                                             = 10
readdir(0x55ae2a86a260)                                          = 0x55ae2a86a2b0
puts("error.o" <unfinished ...>
SYS_write(1, "error.o\n", 8error.o
)                                     = 8
<... puts resumed> )                                             = 8
readdir(0x55ae2a86a260)                                          = 0x55ae2a86a2d0
puts(".." <unfinished ...>
SYS_write(1, "..\n", 3..
)                                          = 3
<... puts resumed> )                                             = 3
readdir(0x55ae2a86a260)                                          = 0x55ae2a86a2e8
puts("error.c" <unfinished ...>
SYS_write(1, "error.c\n", 8error.c
)                                     = 8
<... puts resumed> )                                             = 8
readdir(0x55ae2a86a260)                                          = 0x55ae2a86a308
puts("." <unfinished ...>
SYS_write(1, ".\n", 2.
)                                           = 2
closedir(0x55ae2a86a260 <unfinished ...>
SYS_close(3)                                                     = 0

Wywnioskować więc można, że przez wywołanie funkcji:

• opendir jest wywoływane SYS_openat
• readdir jest wywoływane SYS_getdents64
• printf jest wywoływane SYS_write
• closedir jest wywoływane SYS_close

Wywołanie systemowe SYS_brk powoduje zmianę wielkości sterty programu, dzięki temu zmieniana jest lokalizacja przerwania programu (koniec segmentu danych procesu). Zwiększenie wartości brk powoduje przydzielenie pamięci do procesu, a jej zmniejszenie zwalnia tę pamięć. Funkcje takie jak malloc, realloc, free niejawnie zmieniają wartość brk.

Po włączeniu 1_ls w gdb i ustawieniu catch syscall brk otrzymamy:

Catchpoint 1 (call to syscall brk), __brk (addr=addr@entry=0x0) 
    at ../sysdeps/unix/sysv/linux/x86_64/brk.c:31
31	../sysdeps/unix/sysv/linux/x86_64/brk.c: No such file or directory.

Zadanie 7 (TODO)

Pod kontrolą narzędzia strace uruchom program 2_cat korzystający bezpośrednio z wywołań systemowych do interakcji ze standardowym wejściem i wyjściem. Pokaż, że program oczekuje naodczyt na deskryptorze pliku 0 i pisze do pliku o deskryptorze 1. Naciśnij kombinację klawiszy CTRL+D kończąc wejściowy strumień danych – co zwróciło read? Zmodyfikuj program tak, by czytał z plikupodanego w linii poleceń. Co się stanie, jeśli przekażesz ścieżkę do katalogu zamiast do pliku regularnego?

Lista zadań nr 1

Przed rozpoczęciem zadań warto przeczytać te PDFy o procesach, API procesów oraz o przestrzeniach adresowych, jak i rozdziały 2.1, 10.3 i 11.4 z Modern Operating Systems.

Zadanie 1

W systemach uniksowych wszystkie procesy są związane relacją rodzic-dziecko. Uruchom polecenie ps -eo user,pid,ppid,pgid,tid,pri,stat,wchan,cmd. Na wydruku zidentyfikuj identyfikator procesu, identyfikator grupy procesów, identyfikator rodzica oraz właściciela procesu. Kto jest rodzicem procesu init? Wskaż, które z wyświetlonych zadań są wątkami jądra. Jakie jest znaczenie poszczególnych znaków w kolumnie STAT? Wyświetl drzewiastą reprezentację hierarchii procesów poleceniem pstree – które z zadań są wątkami?

Każdy proces posiada swojego rodzica (oprócz init, którego rodzicem jest kernel ppid 0), który utworzył dziecko przy pomocy fork(). Każdy proces posiada również swój identyfikator procesu (PID), a więc unikalną liczbę, dzięki której łatwiej jest go zidentyfikować. Identyfikatorem grupy procesów (PGID) oznacza się zbiór jednego lub większej ilości procesów, które mogą razem otrzymywać sygnały. Identyfikator rodzica (PPID) to identyfikator procesu, który za pomocą fork() utworzył procesy dzieci. Właściciel to użytkownik, który uruchomił proces i posiada pełne uprawnienia do kontrolowania ich, np. zatrzymywania lub zabijania. Wątki jądra to wątki wykonujące kod jądra, nie są one powiązane z procesami z przestrzeni użytkownika, nie używają również pamięci użytkownika (gdy dodamy vsz do tabeli polecenia ps -eo ... zobaczymy 0 (KiB) dla procesów root). W kolumnie STAT oznacza je litera I. Wywołanie ps bez argumentów sprawi, że wypisana zostanie lista procesów w bieżącej sesji.

Aby dowiedzieć się jakie znaczenie mają poszczególne znaki w kolumnie STAT, używamy man ps i szukamy tego, co nas interesuje:

PROCESS STATE CODES
   Here are the different values that the s, stat and state output specifiers 
   (header "STAT" or "S") will display to describe the state of a process:

       D    uninterruptible sleep (usually IO)
       I    Idle kernel thread
       R    running or runnable (on run queue)
       S    interruptible sleep (waiting for an event to complete)
       T    stopped by job control signal
       t    stopped by debugger during the tracing
       W    paging (not valid since the 2.6.xx kernel)
       X    dead (should never be seen)
       Z    defunct ("zombie") process, terminated but not reaped by its parent

   For BSD formats and when the stat keyword is used, 
   additional characters may be displayed:

       <    high-priority (not nice to other users)
       N    low-priority (nice to other users)
       L    has pages locked into memory (for real-time and custom IO)
       s    is a session leader
       l    is multi-threaded (using CLONE_THREAD, like NPTL pthreads do)
       +    is in the foreground process group

Wątki jądra można rozpoznąc po vsz mającym wartość 0 (kolejna kolumna w ps wspomniana wcześniej) oraz po tym, że cmd jest w nawiasach kwadratowych, tzn. nie jest znana nazwa polecenia, które je utworzyło. Wątki w pstree można rozpoznać po sposobie zapisu ich nazw: n*[{name}] to grupa n wątków.

Zadanie 2

Do czego służy system plików proc(5) w systemie Linux? Dla wybranego przez siebie procesu o identyfikatorze pid wydrukuj zawartość katalogu /proc/pid. Wyświetl plik zawierający argumenty programu oraz zmienne środowiskowe. Podaj znaczenie następujących pól pliku status: Uid, Gid, Groups, VmPeak, VmSize, VmRSS, Threads, voluntary_ctxt_switches, nonvoluntary_ctxt_switches.

System plików proc(5) to pseudosystem plików, który udostępnia interfejs do struktur danych jądra. Zazwyczaj jest montowany w katalogu /proc i jest montowany tam automatycznie przez system, jednak może być również zamontowany manualnie komendą:

mount -t proc proc /proc

Jest on w większości przeznaczony tylko do odczytu, lecz niektóre pliki umożliwiają modyfikacje zmiennych jądra. Poniższe katalogi zawierają następujące dane:

• /proc/[pid] zawiera informacje związane z procesami o danym pid
• /proc/[tid] zawiera informacje związane z wątkami o danym tid
• /proc/self to link symboliczny przekierowujący do własnego /proc/[pid] procesu
• /proc/thread-self to link symboliczny przekierowujący do własnego /proc/self/task/[tid] wątku

Argumenty programu to parametry przekazane do programu w momencie wywołania tego programu. Są to argc (liczba argumentów włącznie z nazwą polecenia) oraz argv[] (argumenty wraz z nazwą polecenia). Możemy je znaleźć w pliku /proc/[pid]/cmdline.

Zmienne środowiskowe to zmienne, których wartości są ustawiane poza programem: nazwane wartości, przechowywane i zarządzane przez powłokę systemową. Każdy proces posiada swój zestaw zmiennych środowiskowych, które dziedziczy po rodzicu. Znajdują się one w /proc/[pid]/environ.

W pliku /proc/[pid]/status znajduje się większość informacji z /proc/[pid]/stat oraz /proc/[pid]/statm, jednak są w formacie bardziej przystępnym dla ludzi. Ich wybrane pola to:

• Uid oraz Gid przechowują identyfikator użytkownika/grupy rzeczywisty (właściciel procesu), efektywny (zwykle to co real, ale czasem jest to zmieniane, żeby nieuprzywilejowany użytkownik mógł uzyskać dostęp do plików, które mogą zostać otworzone tylko przez root), zapisany (używany gdy proces działa z podwyższonymi uprawnieniami, np. root i musi wykonać pracę na mniejszych uprawnieniach, dzięki czemu może zmienić chwilowo usera) oraz system plików.
• Groups to lista grup uzupełniających dziedziczonych po rodzicu, mówią one jakie uprawnienia ma proces
• VmPeak to największy rozmiar pamięci wirtualnej
• VmSize to bieżący rozmiar pamięci wirtualnej
• VmRSS (virtual memory resident set size), czyli rozmiar zbioru roboczego procesu (pamięci wirtualnej używanej przez proces)
• Threads to liczba wątków w procesie zawierającym ten wątek
• voluntary_ctxt_switches to liczba dobrowolnych zmian kontekstu (np. proces opuszcza CPU, bo nie ma nic do roboty i np. oczekuje na IO)
• nonvoluntary_ctxt_switches to liczba zmian kontekstu wywołanych przez wywłaszczenie procesu.

Zadanie 3

Znajdź pid procesu X-serwera, a następnie używając polecenia pmap wyświetl zawartość jego przestrzeni adresowej. Zidentyfikuj w niej poszczególne zasoby pamięciowe – tj. stos, stertę, segmenty programu, pamięć anonimową, pliki odwzorowane w pamięć. Należy wyjaśnić znaczenie kolumn wydruku!

Aby znaleźć pid, używamy ps ax | grep X - flagi ax odpowiadają kolejno za szukanie w procesach innych użytkowników oraz pośród procesów działających poza terminalem. Następnie potokiem przekazujemy stdout do grep, w którym szukamy X-serwer. Na wyjściu uzyskałem:

1158 tty1     Sl+    0:00 /usr/lib/xorg/Xorg vt1 -displayfd 3 -auth /run/user/118/gdm/Xauthority -background none -noreset -keeptty -verbose 3
1957 tty2     Rl+   20:02 /usr/lib/xorg/Xorg vt2 -displayfd 3 -auth /run/user/1000/gdm/Xauthority -background none -noreset -keeptty -verbose 3

Za pomocą sudo pmap 1158 lub sudo pmap 1957 uzyskujemy zawartość przestrzeni adresowej procesu o danym pid. Tutaj jest przykładowy wydruk tego polecenia.

Stos (stack) jest na samym dole, możemy jednak wywołać sudo less /proc/1957/maps, aby uzyskać dokładny przedział adresów przeznaczony na stos (podobnie działa flaga -X, jednak dostajemy tylko początek stosu):

7ffd05252000-7ffd05273000 rw-p 00000000 00:00 0                          [stack]

Sterta (heap) podobnie nie jest pokazywana w pmap, lecz można ją znaleźć w /proc/[pid]/maps (najlepiej w less wyszukać pattern ?heap):

55e2b66fd000-55e2b8a1a000 rw-p 00000000 00:00 0                          [heap]

Segmenty programu to spójne bloki pamięci o jednolitym przeznaczeniu i atrybutach z punktu widzenia procesu ładowania i uruchamiania programu. Jeden segment może zawierać wiele sekcji (linker odpowiada za sekcje, loader za segmenty). Segment kodu to obszar pamięci zawierający kod maszynowy programu. Segmenty programu są zmapowane do Xorg:

Address           Kbytes     RSS   Dirty Mode  Mapping
000055e2b56a4000     244     168       0 r---- Xorg
000055e2b56e1000    1588    1576       0 r-x-- Xorg
000055e2b586e000     484     192       0 r---- Xorg
000055e2b58e7000      12      12      12 r---- Xorg
000055e2b58ea000      48      48      48 rw--- Xorg

Na podstawie Mode możemy wyznaczyć segment text (r-x-- czyli readable and executable). Pola oznaczone r---- to prawdopodobnie sekcje .rodata, a rw--- to sterta.

Pamięć anonimowa to pamięć niebędąca powiązana z żadnym plikiem ani obiektem. Powszechnym anonimowym mapowaniem jest stos i sterta wspomniane powyżej. Jest ona oznaczona jako [anon].

Pliki odwzorowane w pamięć (ang. memory-mapped file) to segment pamięci wirtualnej mający bezpośrednie mapowanie co do bajta z jakimś plikiem lub zasobem. Dzięki temu unika się stosowania funkcji systemowych na plikach takich jak read() lub write(), gdyż proces adresuje plik bezpośrednio. Plik może być traktowany jak ciągły obszar w pamięci procesu, dostępny poprzez bezpośrednie operacje pobrania i podstawienia wartości. Wszystkie modyfikacje dokonane w pamięci są później zapisywane na dysku. Znaleźć je można w Mapping jako pliki *.so.

Poza tymi sekcjami znajdują się również te:

7ffd053ae000-7ffd053b1000 r--p 00000000 00:00 0                          [vvar]
7ffd053b1000-7ffd053b3000 r-xp 00000000 00:00 0                          [vdso]

vvar zawiera zmienne systemowe takie jak gettimeofday, dzięki czemu syscall działa znacznie szybciej. vdso to biblioteka współdzielona udostępniana przez jądro żeby przyspieszyć wykonywanie pewnym syscalli, które niekoniecznie muszą działać w przestrzeni jądra.

Poszczególne kolumny wydruku pmap [pid] -x oznaczają:

• Address - adres początku
• Kbytes - rozmiar
• RSS - fizyczny rozmiar używanej pamięci
• Dirty - dirty strony w KB
• Mode - uprawnienia rwx (czytanie, pisanie, wykonywanie)
• Mapping - plik na jaki zmapowana jest pamięć lub [anon]/[stack]

Zadanie 4

Używając programu lsof wyświetl zasoby plikopodobne podpięte do procesu przeglądarki firefox. Wyjaśnij znaczenie poszczególnych kolumn wykazu, po czym zidentyfikuj pliki zwykłe, katalogi, urządzenia, gniazda (sieciowe lub domeny uniksowej) i potoki. Przekieruj wyjście z programu lsof, przed i po otwarciu wybranej strony, odpowiednio do plików before i after. Czy poleceniem diff -u before after jesteś w stanie zidentyfikować nowo utworzone połączenia sieciowe?

Zasoby plikopodobne (deskryptor pliku) to zasób mający deskryptor pliku, ale niebędący "prawdziwym" plikiem (np. strumienie stdin, stdout, stderr).

Do znalezienia pid firefox używamy pgrep firefox lub ps -ax | grep firefox (warto pamiętać, że Linux jest case sensitive i firefox =/= Firefox). Ja preferuje pgrep, bo wydruk jest dużo bardziej czytelny.

Mając znaleziony pid procesu, używamy lsof -p [pid] do wyświetlenia zasobów plikopodobnych (poniżej tylko część wydruku):

COMMAND     PID USER   FD      TYPE             DEVICE  SIZE/OFF     NODE NAME
firefox-e 26587  two  cwd       DIR               8,20      4096  3670018 /home/two
firefox-e 26587  two  rtd       DIR               8,20      4096        2 /
firefox-e 26587  two  txt       REG               8,20    228408  7613180 /usr/lib/firefox-esr/firefox-esr
firefox-e 26587  two  mem       REG               8,20  27190832  6298743 /usr/lib/x86_64-linux-gnu/libicudata.so.63.1
firefox-e 26587  two  mem       REG               8,20   1886216  6298748 /usr/lib/x86_64-linux-gnu/libicuuc.so.63.1
firefox-e 26587  two  mem       REG               8,20   2984248  6298744 /usr/lib/x86_64-linux-gnu/libicui18n.so.63.1
firefox-e 26587  two  mem       REG               8,20    186968  6303480 /usr/lib/x86_64-linux-gnu/libsoxr.so.0.1.1
firefox-e 26587  two  mem       REG               8,20    687176  6303506 /usr/lib/x86_64-linux-gnu/libxvidcore.so.4.3

Poszczególne kolumny wydruku to (więcej w dokumentacji):

• COMMAND to polecenie, które uruchomiło proces
• PID to identyfikator procesu
• USER to właściciel procesu
• FD to numer deskryptora pliku lub jedno z poniższych:
  • cwd - bieżący katalog
  • L[nn] - referencje bibliotek (AIX)
  • err - informacja błędu FD (w kolumnie NAME)
  • jld - katalog jail (FreeBSD)
  • ltx - dzielona biblioteka text (kod i dane)
  • M[xx] - pamięć mapowana w hex typu [xx]
  • m86 - DOS Merge mapped file
  • mem - plik zmapowany w pamięci
  • mmap - urządzenie zmapowane w pamięci
  • pd - katalog rodzica
  • rtd - katalog roota
  • tr - kernel trace file (OpenBSD)
  • txt - tekst programu (kod i dane)
  • v86 - VP/ix mapped file
• TYPE to typ węzła powiązanego z plikiem:
  • DIR - katalogi
  • DEL - usunięty plik zmapowany
  • REG - plik zwykły
  • IPv4 - socket IPv4
  • ax25 - socket Linux AX.25
  • inet - Internet domain socket
  • sock - socket of unknown domain
  • unix - UNIX domain socket - służy do wymiany danych pomiędzy procesami
  • x.25 - HP-UX x.25 socket
  • STSO - stream socket (wysyłanie i odbieranie danych)
  • FIFO - specjalny plik (nazwany potok), który jest częścią systemu plików
• DEVICE to numery urządzeń
• SIZE/OFF to rozmiar pliku lub jego offset w bajtach
• NODE to numer węzła lub pliku lokalnego
• NAME to nazwa punktu montowania (ang. mount point) i systemu pliku w którym plik się znajduje.

Po FD następuje jeden ze znaków (r - dostęp do odczytu, w - dostęp do zapisu, u - dostęp do odczytu i zapisu, spacja dla braku trybu bez blokady i - dla nieznanego trybu z blokadą).

Plik zwykły to plik, który ma - w polu trybu (widoczne po ls -l), np. -r--r--r--, w lsof jest oznaczany jako REG.

Katalog (ang. directory) to struktura organizacji danych (specjalny rodzaj pliku), który zawiera referencje do plików lub innych katalogów, w lsof jest oznaczany jako DIR.

Plik urządzenia (ang. device file) to plik służący do komunikacji programu z urządzeniem poprzez używanie jego sterowników przy użyciu syscall wejścia/wyjścia.

Gniazdo (ang. socket) to dwukierunkowy punkt końcowy połączenia, dzięki czemu możliwe jest przesyłanie danych w obie strony. Posiada ono trzy główne właściwości: typ gniazda identyfikujący protokół wymiany danych, lokalny adres i opcjonalny numer portu identyfikujący proces. W lsof oznaczony przez sock, IPv4, unix itp.

Potok (ang. pipe) to mechanizm komunikacji międzyprocesowej umożliwiający wymianę danych pomiędzy dwoma procesami. Odbywa się poprzez połączenie stdout jednego procesu z stdin drugiego. Polega ono na stworzeniu specjalnego pliku, który służy jako łącznik między procesami. W lsof oznaczony jako FIFO.

Identyfikacja nowych połączeń sieciowych odbywa się następująco:

1. Szukamy pid procesu firefox.
2. Wchodzimy na jakąś stronę i robimy lsof -p [pid] > before.
3. Zmieniamy tę stronę na inną stronę i robimy lsof -p [pid] > after.
4. Wywołujemy colordiff before after | grep IPv4 (lub zwykłe diff, ale kolorki są lepsze i bardziej czytelne), można dodać flagę -u, żeby zamiast > i < mieć + i -.

-firefox-e 26587  two   44u     IPv4            1207913       0t0      TCP 192.168.1.93:57190->waw02s08-in-f206.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two   61u     IPv4            1216103       0t0      TCP 192.168.1.93:56562->104.18.165.34:https (ESTABLISHED)
+firefox-e 26587  two   64u     IPv4            1217516       0t0      TCP 192.168.1.93:38430->93.184.220.29:http (ESTABLISHED)
+firefox-e 26587  two   66u     IPv4            1215340       0t0      TCP 192.168.1.93:50266->151.101.193.69:http (ESTABLISHED)
-firefox-e 26587  two   68u     IPv4            1207845       0t0      TCP 192.168.1.93:59768->151.101.1.69:https (ESTABLISHED)
-firefox-e 26587  two   69u     IPv4            1207914       0t0      TCP 192.168.1.93:35178->91.228.74.189:https (ESTABLISHED)
+firefox-e 26587  two   68u     IPv4            1216124       0t0      TCP 192.168.1.93:36126->151.101.193.69:https (ESTABLISHED)
+firefox-e 26587  two   69u     IPv4            1217804       0t0      TCP 192.168.1.93:36240->waw02s17-in-f2.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two   71u     IPv4            1217805       0t0      TCP 192.168.1.93:58634->waw02s08-in-f206.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two   74u     IPv4            1215362       0t0      TCP 192.168.1.93:40126->waw02s18-in-f10.1e100.net:https (ESTABLISHED)
-firefox-e 26587  two   82u     IPv4            1204904       0t0      TCP 192.168.1.93:38624->waw02s18-in-f10.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two   82u     IPv4            1218627       0t0      TCP 192.168.1.93:50552->104.17.79.107:https (ESTABLISHED)
+firefox-e 26587  two   83u     IPv4            1219141       0t0      TCP 192.168.1.93:39258->sof01s12-in-f1.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  130u     IPv4            1217806       0t0      TCP 192.168.1.93:49940->a2-18-14-44.deploy.static.akamaitechnologies.com:https (ESTABLISHED)
-firefox-e 26587  two  144u     IPv4            1205015       0t0      TCP 192.168.1.93:37646->65.9.96.42:https (ESTABLISHED)
+firefox-e 26587  two  144u     IPv4            1215372       0t0      TCP 192.168.1.93:36484->stackoverflow.com:https (ESTABLISHED)
+firefox-e 26587  two  149u     IPv4            1216134       0t0      TCP 192.168.1.93:57004->91.228.74.198:https (ESTABLISHED)
-firefox-e 26587  two  157u     IPv4            1205014       0t0      TCP 192.168.1.93:59368->lg-in-f157.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  154u     IPv4            1216144       0t0      TCP 192.168.1.93:40222->65.9.96.9:https (ESTABLISHED)
+firefox-e 26587  two  155u     IPv4            1218728       0t0      TCP 192.168.1.93:53496->mil02s06-in-f2.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  156u     IPv4            1215390       0t0      TCP 192.168.1.93:53500->mil02s06-in-f2.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  157u     IPv4            1216151       0t0      TCP 192.168.1.93:49504->a104-85-249-211.deploy.static.akamaitechnologies.com:http (ESTABLISHED)
+firefox-e 26587  two  158u     IPv4            1215399       0t0      TCP 192.168.1.93:53504->mil02s06-in-f2.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  159u     IPv4            1216158       0t0      TCP 192.168.1.93:38592->par10s21-in-f195.1e100.net:http (ESTABLISHED)
+firefox-e 26587  two  161u     IPv4            1215420       0t0      TCP 192.168.1.93:44586->waw02s16-in-f1.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  162u     IPv4            1215400       0t0      TCP 192.168.1.93:38400->lg-in-f156.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  164u     IPv4            1219680       0t0      TCP 192.168.1.93:38648->par10s21-in-f195.1e100.net:http (ESTABLISHED)
+firefox-e 26587  two  166u     IPv4            1218798       0t0      TCP 192.168.1.93:53514->mil02s06-in-f2.1e100.net:https (ESTABLISHED)
+firefox-e 26587  two  168u     IPv4            1220643       0t0      TCP 192.168.1.93:46608->nrt20s20-in-f3.1e100.net:https (ESTABLISHED)
-firefox-e 26587  two  173u     IPv4            1205057       0t0      TCP 192.168.1.93:42264->151.101.65.69:https (ESTABLISHED)
-firefox-e 26587  two  194u     IPv4            1210628       0t0      TCP 192.168.1.93:38768->waw02s18-in-f10.1e100.net:https (ESTABLISHED)

Zadanie 5

Wbudowanym poleceniem powłoki time zmierz czas wykonania długo działającego procesu, np. polecenia find /usr. Czemu suma czasów user i sys (a) nie jest równa real (b) może być większa od real? Poleceniem ulimit nałóż ograniczenie na czas wykonania procesów potomnych powłoki tak, by limit się wyczerpał. Uruchom ponownie wybrany program – który sygnał wysłano do procesu?

Czas wykonania to czas spędzony na wykonywaniu zadania. Ograniczenie czasu wykonania to limit czasu przeznaczony na wykonanie zadania.

Wykonajmy polecenie time find /usr. Jego wydrukiem będzie coś takiego:

real	0m7.808s
user	0m0.495s
sys	0m1.676s

Aby dowiedzieć się dlaczego user + sys != real należy wyjaśnić co oznacza każdy z czasów:

• user to czas CPU spędzony w trybie użytkownika podczas wykonywania procesu określonego przez polecenie time
• sys to czas CPU spędzony na wykonywaniu różnych syscall przez jądro, liczony jest tylko dla tego konkretnego procesu
• real to realny czas od uruchomienia procesu do jego zakończenia.

Może dojść do sytuacji, gdzie czas user jest większy od real - dzieje się tak, gdy proces używa kilku rdzeni. Czasy na każdym rdzeniu są wtedy sumowane, dzięki czemu możemy mieć sytuacje takie jak poniższa (wytłumaczenie stąd):

real    0m8.512s
user    0m8.737s
sys     0m1.956s

Ograniczenie czasu wykonania nakładamy przez ulimit -t [sekundy]. Czas ograniczenia liczy się tylko jako user + sys, real może być większy niż nałożony przez nas limit. Proces zostaje zabity sygnałem SIGKILL. Można zobaczyć listę wszystkich limitów poprzez ulimit -a.

Zadanie 6

Napisz program, który będzie prezentował, że pliki procesu są kopiowane przez referencję w trakcie wywołania fork(2). W procesie głównym otwórz plik do odczytu open(2). Czy zamknięcie pliku close(2) w procesie głównym zamyka plik także w dziecku? Czy odczyt z pliku read(2) zmienia pozycję kursora lseek(2) w drugim procesie? Wyjaśnij zachowanie swojego programu!

Przed każdym komunikatem diagnostycznym wypisz pid procesu. W drugiej części zadania należy wydrukować bieżącą pozycję kursora pliku przed operacją odczytu z pliku. Należy wykorzystać dostarczone funkcje opakowujące uniksowe wywołania systemowe z biblioteki libcsapp.

Kopiowanie przez referencję to kopiowanie wskaźnika na obiekt, a nie zawartości obiektu.

Pozycja kursora to offset od początku pliku, od którego następuje czytanie/pisanie.

static void do_read(int fd) {
  pid_t pid;
  pid = Fork();
  if(pid == 0){
    Read(fd,buf,16);
    printf("%d: %ld\n",pid, Lseek(fd,0,SEEK_CUR));
  }
  else{
  	Read(fd,buf,16);
  	printf("%d: %ld\n",pid,Lseek(fd,0,SEEK_CUR));
  }
  exit(0);
}

static void do_close(int fd) {
  int child_status;
  pid_t pid;
  pid = Fork();
  if(pid == 0){
	printf("%d: Closing file %d\n",pid,fd);
	Close(fd);
	exit(0);
  }
  else {
  	Waitpid(pid,&child_status,0);
  	printf("%d: Child status: %d\n",pid,child_status);
  	printf("%d: Cursor position: %ld\n",pid, Lseek(fd,0,SEEK_CUR));
  	Read(fd,buf,16);
  	printf("%d: Reading from file %d: %s\n",pid,fd,buf);  
	exit(0);
  }
}

Po wywołaniu ./fileref read na wyjściu uzyskamy:

4606: 16
0: 32

Dochodzi do kopiowania przez referencję, ponieważ dziecko ma dostęp do tego samego pliku co rodzic.

Możemy zauważyć, że oba procesy korzystają z tego samego kursora, ponieważ końcowa pozycja kursora wynosi

$32$, a w obu procesach odczytujemy

$16$ znaków. Gdyby procesy nie korzystały ze wspólnego kursora, i nie byłoby żadnej innej synchronizacji wyjścia, to dochodziłoby do nadpisywania wyjścia jednego procesu przez wyjście innego. Aktualna pozycja kursora znajduje się w strukturze file description, która znajduje się w jądrze. Po wywołaniu ./fileref close uzyskamy:

0: Closing file 3
5029: Child status: 0
5029: Cursor position: 0
5029: Reading from file 3: Write programs t

Mimo tego, że dziecko zamknęło plik, zanim rodzic zaczął z niego czytać, to nie wystąpił żaden błąd. Oznacza to, że plik rodzica nie został zamknięty. Wynika to z faktu, że każdy proces posiada swój własny file descriptor. Jest to liczba całkowita, która pozwala na komunikację z plikiem. Właśnie dlatego zamknięcie pliku w procesie-dziecku nie powoduje zamknięcia go w rodzicu.

Zadanie 7

Rozwiąż problem

$n$ hetmanów z użyciem fork(2) i waitpid(2). Gdy w

$i$-tym elemencie tablicy board przechowywana jest wartość

$j$ znaczy to, że pozycja

$i$-tego hetmana na szachownicy to

$(i,j)$. Mając niekonfliktujące ustawienie pierwszych

$k-1$ hetmanów po kolei startuj

$n$ podprocesów z proponowanym ustawieniem

$k-tego$ hetmana. Podproces, który wykryje konfliktujące ustawienie hetmanów, ma zakończyć swe działanie. W przeciwnym wypadku zachowuje się jak rodzic dla

$k+1$ hetmana. Podproces, który uzyska prawidłowe ustawienie

$n$ hetmanów, ma wydrukować je na standardowe wyjście. Procedura ndselect wraca wielokrotnie z kolejnymi liczbami z zakresu

$0,...,n-1$.

Linie wydruków plansz z prawidłowymi ustawieniami hetmanów nie mogą się przeplatać.

Uważaj, żeby przez przypadek nie zaprogramować fork bomby! Należy wytłumaczyć działanie programu rysując diagram procesów pokazany na wykładzie.

#include "csapp.h"

#include <pthread.h>
pthread_mutex_t lock;

static int ndselect(int n)
{
   /* TODO: A loop is missing here that spawns processes and waits for them! */
   pid_t pids[8];
   for (int i = 0; i < n; i++)
   {
      pids[i] = Fork();
      if (pids[i] == 0)
      {
         return i;
      }
   }
   for (int i = 0; i < 8; i++)
   {
      waitpid(pids[i], NULL, 0);

   }
   exit(0);
}

static int conflict(int x1, int y1, int x2, int y2)
{
   return x1 == x2 || y1 == y2 || x1 + y1 == x2 + y2 || x1 - y1 == x2 - y2;
}

static void print_line_sep(int size)
{
   for (int i = 0; i < size; ++i)
      printf("+---");
   printf("+\n");
}

static void print_board(int size, int board[size])
{
   pthread_mutex_lock(&lock);

   for (int i = 0; i < size; ++i)
   {
      print_line_sep(size);
      for (int j = 0; j < size; ++j)
         printf("|%s", board[i] == j ? " Q " : "   ");
      printf("|\n");
   }
   print_line_sep(size);
   printf("\n");

   pthread_mutex_unlock(&lock);
}

int main(int argc, char **argv)
{
   if (argc != 2)
      app_error("Usage: %s [SIZE]", argv[0]);

   int size = atoi(argv[1]);

   if (size < 2 || size > 9)
      app_error("Give board size in range from 4 to 9!");

   if (pthread_mutex_init(&lock, NULL) != 0)
   {
      app_error("mutex error");
   }
   int board[size];

   /* TODO: A loop is missing here that initializes recursive algorithm. */
   for (int i = 0; i < size; i++)
   {
      int pos = ndselect(size);
      if (pos == -1)
         exit(0);
      board[i] = pos;
      for (int j = 0; j < i; j++)
      {
         if (conflict(j, board[j], i, board[i]))
            exit(0);
      }
   }

   print_board(size, board);

   return 0;
}

Lista zadań nr 2

Warto przeczytać 10.3 i 11.4 z Modern Operating Systems, 4.6 z Operating Systems: Internals and Design Principles oraz 8, 10 z APUE.

Zadanie 1

Na podstawie rysunku 4.15 z §4.6 (rysunek na 207. stronie, widoczny poniżej) przedstaw stany procesu w systemie Linux. Podaj akcje albo zdarzenia wyzwalające zmianę stanów. Które przejścia mogą być rezultatem działań podejmowanych przez: jądro systemu operacyjnego, kod sterowników, proces użytkownika? Wyjaśnij różnice między snem przerywalnym i nieprzerywalnym. Czy proces może zablokować lub zignorować sygnał SIGKILL?

Można wyróżnić następujące stany procesu w systemie Linux:

• stopped - proces zatrzymany, może zostać wznowiony przez inny proces, np. proces został zatrzymany w trakcie debugowania i wznowiony może być tylko przez debugger
• running state:
  • ready - proces załadowany do pamięci, oczekuje na wykonanie przez CPU
  • executing - proces będący bieżąco wykonywany (a dokładniej jego instrukcje)
• zombie - proces zakończony, jednak dalej znajduje się w tablicy procesów i oczekuje na obsługę zamknięcia przez proces rodzica
• uninterruptible czyli sen nieprzerywalny to stan procesu, w którym proces jest zablokowany i nie obsługuje żadnych sygnałów
• interruptible czyli sen przerywalny to stan procesu, w którym proces jest zablokowany, jednak oczekuje na zdarzenie takie jak koniec operacji I/O, dostępność zasobu lub sygnał z innego procesu

Dwa ostatnie stany różnią się tym, że sen przerywalny reaguje na sygnały, przez które może zostać obudzony, a sen nieprzerywalny nie obsługuje sygnałów.

Poniżej przedstawione przejścia między stanami są wywoływane przez takie zdarzenia/akcje:

Początek	Koniec	Akcja
Ready	Executing	zaplanowanie wykonania procesu przez scheduler, a więc działanie jądra systemu operacyjnego
Executing	Zombie	dobrowolne zakończenie się procesu przez exit() zamknięcie przez system w przypadku deadlocka otrzymanie sygnału SIGKILL lub SIGTERM błąd I/O (sterownik urządzenia)
Executing	Sleep (both)	wydarzenie I/O wybudzane przez jądro sygnał (tylko w przypadku interruptible sleep)
Stopped	Ready	otrzymanie sygnału SIGSTOP lub SIGCONT od procesu użytkownika

Zablokowanie sygnału to określenie na niedostarczenie sygnału do procesu do momentu odblokowania go przez system operacyjny. Proces blokuje sygnał poprzez użycie funkcji:

int sigprocmask(int how, const sigset_t *set, sigset *oldset)

Zignorowanie sygnału to sytuacja, w której nie została zdefiniowana procedura obsługi konkretnego sygnału.

Sygnału SIGKILL nie da się zablokować, a zignorowanie tego sygnału spowoduje zabicie procesu.

Zadanie 2

Wyjaśnij różnice w tworzeniu procesów w systemie Linux (§10.3.3) i WinNT (§11.4.3). Naszkicuj przebieg akcji podejmowanych przez jądro w trakcie obsługi funkcji fork(2) i execve(2). Wyjaśnij jak system uniksowy optymalizuje klonowanie procesów z użyciem kopiowania przy zapisie?

Tworzenie procesu w systemie Linux (jedyna możliwość to fork()):

1. Deskryptor procesu task_struct i obszar użytkownika są tworzone i wypełniane w dużej części na podstawie zawartości odpowiednich struktur procesu rodzica.
2. Proces potomny uzyskuje identyfikator PID, własną mapę pamięci oraz współdzielony dostęp do plików swojego rodzica.
3. Ustawiane są rejestry nowego procesu, a proces staje się gotowy do wykonania.

Tworzenie procesu w systemie WinNT różni się znacząco, wywołuje się tam procedurę CreateProcess, która jako argument przyjmuje nazwę pliku wykonywalnego. Procedura ta tworzy zupełnie nowy proces (a nie klonuje, jak w przypadku Linuxa). Stworzony proces (dziecko) nie otrzymuje kopii pamięci swojego rodzica.

W §10.3.3 (Modern Operating Systems) można znaleźć taki schemat przedstawiający przebieg akcji podejmowanych przez jądro w trakcie obsługi fork(2) oraz execve(2):

Wywołanie fork sprawia, że proces wywołujący przechodzi w tryb jądra oraz tworzy nową strukturę zadania i kilka innych, dodatkowych struktur danych, jak stros trybu jądra czy struktura thread_info. Nowa struktrua zadania, która jest umieszczana w pamięci na pozycji przesuniętej o pewną stałą wartość względem końca stosu danego procesu, reprezentuje szereg parametrów odpowiedniego procesu, w tym adres jego deskryptora. Zdecydowana większość zawartości deksryptora jest kopiowana z procesu rodzica. System operacyjny musi znaleźć dostępny PID i zaktualizować odpowiedni wpis w tablicy indentyfikatorów, aby wskazywał na nową strukturę zadania. Na sam koniec kopiowane są rejestry rodzica do dziecka.

Wywołanie exec sprawia, że jądro na samym początku szuka programu wykonywalnego, następnie sprawdza uprawnienia wykonywania, po czym kopiuje argumenty i środowisko i zwalnia starą przestrzeń adresową, po czym tworzy nową. Argumenty i zmienne środowiskowe są kopiowane na stos, sygnały są zerowane, a rejestry inicjalizowane (wypełnione zerami).

Kopiowanie przy zapisie (ang. copy on write) to technika zarządzania zasobami, która pozwala zoptymalizować klonowanie procesów w systemach uniksowych. Polega ona na odraczaniu kopiowania pamięci rodzica do momentu, w którym jakiś proces próbuje do niej pisać - nowo utworzony proces otrzymuje swoją tablicę stron, jednak wszystkie są oznaczone tylko do odczytu. Gdy proces dziecka próbuje pisać do pamięci, ma miejsce błąd naruszenia reguł ochrony (protection fault). Jądro wydziela wówczas pamięc dla nowej kopii strony dla procesu potomnego i oznacza ją jako dostępną do odczytu i zapisu. Oznacza to, że kopiowane są tylko strony, co do których proces potomny sformułował żądania zapisu.

Zadanie 3

Na podstawie dokumentacji fork(2) (§8.3) i execve(2) (§8.10) wymień najważniejsze zasoby procesu, które są dziedziczone przez (a) proces potomny (b) nowy program załadowany do przestrzeni adresowej. Czemu przed wywołaniem fork należy opróżnić bufory biblioteki stdio(3)? Czemu w trakcie execve jądro przywraca domyślną obsługę wyłapywanych sygnałów?

Wywołując fork proces potomny dziedziczy te właściwości:

• identyfikatory: real user ID, real group ID, effective user ID, effective group ID, supplementary groups ID, process group ID, session ID
• kontrolowany terminal (?)
• flagi set-user-ID oraz set-group-ID
• bieżącą ścieżkę roboczą (pwd) oraz ścieżkę root'a
• maskę sygnału
• deskryptory plików
• środowisko
• przestrzeń adresową
• limit zasobów
• mapy pamięci

Przed jego wywołaniem należy opróżnić bufory stdio, ponieważ chcemy uniknąć kilkukrotnego wypisywania danych.

Nowy program załadowany do przestrzeni adresowej poleceniem execve dziedziczy z procesu wywołującego go następujące właściwości:

• identyfikatory: PID, PPID, real user ID, real group ID, supplementary groups IDs, process group ID
• kontrolowany terminal
• bieżącą ścieżkę roboczą (pwd) oraz ścieżkę root'a
• blokady plików
• maska sygnału procesu, oczekujące symbole
• wartości tms_utime, tms_stime, tms_cutime, tms_cstime

Jądro przywraca domyślną obsługę wyłapywanych sygnałów w trakcie wywołania execve, ponieważ użytkownik sam może zdefiniować sygnały SIGUSR1 i SIGUSR2, które nie powinny być w żaden sposób obsługiwane przez nowy program.

Zadanie 4

Uruchom program xeyes po czym użyj na nim polecenia kill, pkill i xkill. Który sygnał jest wysyłany domyślnie? Przy pomocy kombinacji klawiszy CTRL+Z wyślij xeyes sygnał SIGTSTP, a następnie wznów jego wykonanie. Przeprowadź inspekcję pliku /proc/pid/status i wyświetl maskę sygnałów oczekujących na dostarczenie. Pokaż jak będzie się zmieniać, gdy będziemy wysyłać wstrzymanemu procesowi kolejno: SIGUSR1, SIGUSR2, SIGHUP i SIGINT. Co opisują pozostałe pola pliku status dotyczące sygnałów? Który sygnał zostanie dostarczony jako pierwszy po wybudzeniu procesu?

Spójrzmy na man każdego polecenia, skąd dowiemy się o wysyłanych sygnałach:

• The default signal for kill is TERM.
• pkill will send the specified signal (by default SIGTERM) to eachprocess instead of listing them on stdout.
• xkill (sekcja caveats): This command does not provide any warranty that the application whose connection to the X server is closed will abort nicely, or even abort at all. All this command does is to close the connection to the X server. Many existing applications do indeed abort when their connection to the X server is closed, but some can choose to continue.

Polecenia te wykonuje się w taki sposób:

$ kill [pid]
$ pkill [process name]
$ xkill (po czym wybiera się okno, które zabijamy)

Warto dodać, że po kilkukrotnym uruchomieniu xeyes (np. dla 5 działających procesów jednocześnie) pkill xeyes zabije wszystkie te procesy.ki

Wykonując CTRL+Z wywołujemy sygnał SIGTSTP (lekko się różni od SIGSTOP) na programie xeyes, wznawiamy jego działanie przez fg lub bg (zależy czy chcemy aby działało w tle, czy nie).

Sygnały oczekujące to sygnały, których dostarczenie jest wstrzymane do momentu wyjścia przez proces z nieprzerywalnego snu.

Sygnały SIGUSR1, SIGUSR2, SIGHUP i SIGINT wysyłamy w procedurze kill -[sygnał] [pid]. W pliku /proc/pid/status znajdują się pola dotyczące sygnałów:

• SigQ to pole zawierające dwie liczby które oznaczają liczbę zakolejkowanych sygnałów dla real user ID oraz limit zakolejkowanych sygnałów dla tego procesu,
• SigPnd, ShdPnd to pola z liczbą sygnałów oczekujących na wątek oraz na cały proces,
• SigBlk, SigIgn, SigCgt to maski sygnałów blokowanych, ignorowanych oraz złapanych.

Po uruchomieniu xeyes możemy sprawdzić maski przez cat /proc/[pid]/status, klikamy CTRL+Z, żeby wysłać sygnał SIGTSTP, a następnie wywołujemy kolejno:

$ kill -SIGUSR1 [pid]
$ cat /proc/[pid]/status (to polecenie co każy kolejny kill)
$ kill -SIGUSR2 [pid]
$ kill -SIGHUP [pid]
$ kill -SIGINT [pid]

Jako pierwszy po wybudzeniu procesu wysyłany jest sygnał SIGHUP:

[1]  + 19997 continued  xeyes
[1]  + 19997 hangup     xeyes

Zadanie 5

Uzupełnij program reaper.c prezentujący powstawanie sierot. Proces główny przyjmuje rolę żniwiarza (ang. reaper) przy użyciu prctl(2). Przy pomocy procedury spawn utwórz kolejno procesy syna i wnuka. Następnie osieroć wnuka kończąc działanie syna. Uruchom podproces wywołujący polecenie ps, aby wskazać kto przygarnął sierotę – przykład poniżej (zwróć uwagę na numery grup procesów):

  PID  PPID  PGRP STAT CMD
24886 24643 24886 S+   ./reaper (main)
24888 24886 24887 S    ./reaper (grandchild)
24889 24886 24886 R+   /usr/bin/ps -o pid,ppid,pgrp,stat,cmd

Po udanym eksperymencie należy zabić wnuka sygnałem SIGINT, a następnie po nim posprzątać drukując jego kod wyjścia. Wysłanie SIGINT do procesu głównego jest zabronione! Zauważ, że proces główny nie zna numeru pid wnuka. W rozwiązaniu należy wykorzystać setpgid(2), pause(2), waitpid(2) i kill(2).

Użycie funkcji sleep(3) lub podobnych do właściwego uszeregowania procesów jest zabronione!

Sierota (ang. orphant) to proces, który stracił rodzica, zostaje on "zaadoptowany" przez proces wyżej w hierarchii. Żniwiarz (ang. reaper) to proces, który wyszukuje procesy zombie i odczytuje ich kod wyjścia, a więc wynik zakończenia programu zwracany do środowiska i zapisywany w zmiennej $ w bashu - 0 oznacza sukces, a pozostałe wartości błąd.

#include "csapp.h"

static pid_t spawn(void (*fn)(void))
{
  pid_t pid = Fork();
  if (pid == 0)
  {
    fn();
    printf("(%d) I'm done!\n", getpid());
    exit(EXIT_SUCCESS);
  }
  return pid;
}

static void grandchild(void)
{
  printf("(%d) Waiting for signal!\n", getpid());
  /* TODO: Something is missing here! */
  pause();
  printf("(%d) Got the signal!\n", getpid());
}

static void child(void)
{
  pid_t pid;
  /* TODO: Spawn a child! */
  setpgrp();
  pid = spawn(grandchild);
  printf("(%d) Grandchild (%d) spawned!\n", getpid(), pid);
}

/* Runs command "ps -o pid,ppid,pgrp,stat,cmd" using execve(2). */
static void ps(void)
{
  /* TODO: Something is missing here! */
  char *argv[] = {"ps", "-o", "pid,ppid,pgrp,stat,cmd", NULL};
  // execvp - sprawdza PATH, używa envp = environ
  execvp(argv[0], argv);
}

int main(void)
{
  /* TODO: Make yourself a reaper. */
#ifdef LINUX
  Prctl(PR_SET_CHILD_SUBREAPER, 1);
#endif
  printf("(%d) I'm a reaper now!\n", getpid());

  pid_t pid, pgrp;
  int status;

  /* TODO: Start child and grandchild, then kill child!
   * Remember that you need to kill all subprocesses before quit. */
  printf("(%d) Spawning child\n", getpid());
  pid = spawn(child);
  waitpid(pid, &status, 0);
  printf("(%d) Child quit with %d\n", getpid(), status);
  pgrp = -pid;

  printf("(%d) Spawning ps\n", getpid());
  pid = spawn(ps);
  waitpid(pid, &status, 0);
  printf("(%d) ps quit with %d\n", getpid(), status);

  printf("(%d) Killing grandchild\n", getpid());
  kill(pgrp, SIGINT);
  waitpid(pgrp, &status, 0);
  printf("(%d) Granchild quit with %d\n", getpid(), status);

  return EXIT_SUCCESS;
}

Zadanie 6

Uzupełnij program cycle.c, w którym procesy grają w piłkę przy pomocy sygnału SIGUSR1. Proces główny tworzy

$n$ dzieci. Każde z nich czeka na piłkę, a po jej odebraniu podaje ją do swojego starszego brata. Zauważ, że najstarszy brat nie zna swojego najmłodszego rodzeństwa, ale zna je ojciec – więc należy go wciągnąć do gry! Niech tata rozpocznie grę rzucając piłkę do najmłodszego dziecka. Kiedy znudzi Ci się obserwowanie procesów grających w piłkę możesz nacisnąć CTRL+C co wyśle SIGINT do całej rodziny. Możesz wprowadź do zabawy dodatkową piłkę wysyłając sygnał SIGUSR1 poleceniem kill. Czy piłki ostatecznie skleją się w jedną? W rozwiązaniu należy wykorzystać sigprocmask(2), sigsuspend(2) i kill(2).

Użycie funkcji sleep(3) lub podobnych do właściwego uszeregowania procesów jest zabronione!

#include "csapp.h"
#include "signal.h"

static void signal_handler(int signum, siginfo_t *info, void *data)
{
	if (signum == SIGINT)
	{
		safe_printf("(%d) Screw you guys... I'm going home!\n", getpid());
		_exit(0);
	}
}

static void play(pid_t next, const sigset_t *set)
{
	for (;;)
	{
		printf("(%d) Waiting for a ball!\n", getpid());
		Sigsuspend(set); // tutaj sobie czekamy na sygnal (pilke), zawieszamy proces do otrzymania kolejnego sygnalu
		usleep((300 + random() % 400) * 1000);
		Kill(next, SIGUSR1);
		printf("(%d) Passing ball to (%d)!\n", getpid(), next);
	}
}

int main(int argc, char *argv[])
{
	if (argc != 2)
		app_error("Usage: %s [CHILDREN]", argv[0]);

	int children = atoi(argv[1]);

	if (children < 4 || children > 20)
		app_error("Give number of children in range from 4 to 20!");

	/* Register signal handler for SIGUSR1 */
	struct sigaction action = {.sa_sigaction = signal_handler};
	Sigaction(SIGINT, &action, NULL);
	Sigaction(SIGUSR1, &action, NULL);
     
	sigemptyset(&action.sa_mask); // ustawienie maski na 0
    sigaddset(&action.sa_mask, SIGUSR1); // obsluga sygnalu SIGUSR1 (pilka)
    Sigprocmask(SIG_BLOCK, &action.sa_mask, NULL);

    pid_t next_pid = getpid();

    for (int i = 0; i < children; i++)
    {
        pid_t pid = Fork();

        if (!pid)
            play(next_pid, &action.sa_mask);
        else
            next_pid = pid;
    }

    Kill(next_pid, SIGUSR1);
    play(next_pid, &action.sa_mask);

	
	return EXIT_SUCCESS;
}

Inna wersja tego rozwiązania:

static void play(pid_t next, const sigset_t *set)
{

   for (;;)
   {
      printf("(%d) Waiting for a ball!\n", getpid());
      /* TODO: Something is missing here! */
      sigsuspend(set);

      usleep((300 + random() % 400) * 1000);
      Kill(next, SIGUSR1);
      printf("(%d) Passing ball to (%d)!\n", getpid(), next);
   }
int main(int argc, char *argv[])
{
   if (argc != 2)
      app_error("Usage: %s [CHILDREN]", argv[0]);

   int children = atoi(argv[1]);

   if (children < 4 || children > 20)
      app_error("Give number of children in range from 4 to 20!");

   /* Register signal handler for SIGUSR1 */
   sigset_t mask;
   sigfillset(&mask);
   sigdelset(&mask, SIGINT);

   sigprocmask(SIG_SETMASK, &mask, NULL);

   struct sigaction action = {.sa_sigaction = signal_handler};

   Sigaction(SIGINT, &action, NULL);
   Sigaction(SIGUSR1, &action, NULL);
   int parent_pid = getpid();
   printf("parent pid: %d\n", parent_pid);
   int pids[21];
   /* TODO: Start all processes and make them wait for the ball! */

   sigset_t mask2;
   sigfillset(&mask2);

   sigdelset(&mask2, SIGINT);
   sigdelset(&mask2, SIGUSR1);

   for (int i = 0; i < children; i++)
   {
      pid_t pid = fork();
      if (!pid)
         play(i ? pids[i - 1] : parent_pid, &mask2);
      else
         pids[i] = pid;
   }

   Kill(pids[children - 1], SIGUSR1);
   play(pids[children - 1], &mask2);
   
   return EXIT_SUCCESS;
}

Zadanie 7

Uzupełnij program demand o procedurę obsługi sygnału SIGSEGV. Program ma za zadanie demonstrować przechwytywanie błędów stron, których nie było w stanie obsłużyć jądro SO.

Obsługujemy zakres adresów od ADDR_START do ADDR_END. Pod losowo wybrane wirtualne strony z podanego przedziału zostanie podpięta pamięć wirtualna w trybie tylko do odczytu. Następnie program wygeneruje do zadanego przedziału adresów zapisy, które zakończą się naruszeniem ochrony pamięci.

Po wyłapaniu sygnału SIGSEGV, korzystając z procedur mmap_page i mprotect_page odpowiednio zmapuj brakującą stronę (błąd SEGV_MAPERR) i odblokuj zapis do strony (błąd SEGV_ACCERR). Dostęp do adresów spoza ustalonego zakresu powinien skutkować zakończeniem programu. Należy wtedy ustalić właściwy kod wyjścia tak, jakby proces został zabity sygnałem!

...
Fault at rip=0x55cb50d54389 accessing 0x10003fc0! Make page at 0x10003000 writable.
Fault at rip=0x55cb50d54389 accessing 0x10007bb0! Map missing page at 0x10007000.
...
Fault at rip=0x55cb50d5439c accessing 0x10010000! Address not mapped - terminating!

W procedurze obsługi sygnału można używać tylko procedur wielobieżnych (ang. reentrant) – sprawdź w podręczniku ich listę. Możesz wykorzystać procedurę safe_printf, będącą okrojoną wersją printf. Czemu można ją bezpiecznie wywołać w wnętrza sigsegv_handler?

Adres powodujący błąd strony i rodzaj błędu znajdziesz w argumencie sigsegv_handler o typie siginfo_t, który opisano w podręczniku sigaction(2). Wskaźnik instrukcji, która spowodowała błąd strony, można przeczytać ze struktury przechowującej kontekst procesora uc->uc_mcontext. Odpowiednie definicje znajdują się w pliku nagłówkowym /usr/include/x86_64-linux-gnu/sys/ucontext.h.

Procedury wielobieżne to takie procedury, które mogą być przerwane podczas wykonywania, a później bezpiecznie wznowione.

static void sigsegv_handler(int signum, siginfo_t *info, void *data) {
  ucontext_t *uc = data;

  /* TODO: You need to get value of instruction pointer register from `uc`.
   * Print all useful data from `info` and quit in such a way that a shell
   * reports program has been terminated with SIGSEGV. */

  greg_t rip_addr = uc->uc_mcontext.gregs[17];
  void* access_addr = info->si_addr;
  int err_code = info->si_code;

  if(access_addr > ADDR_START && access_addr < ADDR_END) {
    void* page_addr = (void*)((long)access_addr - ((long)access_addr % PAGE_SIZE));

    if(err_code == 1) {
      safe_printf("Fault at rip=%lx accessing %lx! Map missing page at %lx.\n", (long)rip_addr, (long)access_addr, (long)page_addr);
      mmap_page(page_addr, PROT_WRITE);
    } else if(err_code == 2) {
      safe_printf("Fault at rip=%lx accessing %lx! Make page at %lx writable.\n", (long)rip_addr, (long)access_addr, (long)page_addr);
      mprotect_page(page_addr, PROT_WRITE);
    }
  } else {
    safe_printf("Fault at rip=%lx accessing %lx! Address not mapped - terminating!\n", (long)rip_addr, (long)access_addr);
    exit(11);
  }
}

Lista zadań nr 3

Zadanie 1

W artykule A fork() in the road skrytykowano wywołanie fork(2). Na podstawie sekcji 4 publikacji przedstaw pobieżnie argumentację autorów przeciwko fork. Następnie opowiedz jak posix_spawn(3) pomagają zniwelować niektóre z wymienionych wad.

Problemy z fork:

• nie jest już prosty, specyfikacja POSIX wymienia 25 specjalnych przypadków kopoiwania stanu rodzica do procesu dziecka, są to między innymi file locks, timery, asynchroniczne operacje IO, tracing i inne. Dodatkowo, wiele flag wpływa na zachowanie fork w kwestii:
  • mapowania pamięci (flagi madvise Linuxa: MADV_DONTFORK, MADV_DOFORK, MADV_WIPEONFORK). madvise() to wywołanie systemowe informujące system pamięci wirtualnej systemu operacyjnego o planowanym sposobie użycia danego obszaru pamięci;
  • deskryptorów plików (O_CLOEXEC - dzieci nie dziedziczą deskryptorów plików, FD_CLOEXEC - zamknij plik po wywołaniu funkcji z rodziny exec);
  • wątków (pthread_atfork rejestruje fork handlery, które mają zostać wykonane podczas wywołania fork w kontekście wątku, który wywołał fork);
• nie składa się (?), fork duplikuje całą przestrzeń adresową: klasycznym przykładem jest bufor IO, który musi być flushowany przez użytkownika;
• nie jest thread-safe, tzn. dziecko utworzone przez fork ma jedynie jeden wątek. Możliwe jest, że przestrzeń adresowa dziecka nie będzie spójną kopią przestrzeni rodzica, np. gdy jeden wątek dokonuje alokacji pamięci i posiada blokadę sterty, a inny wątek wywoła fork, alokacja pamięci w nowym dziecku będzie niemożliwa gdyż będzie ono czekało na oblokowanie, które nigdy nie nastąpi. malloc nie jest bezpieczny w połączeniu z fork;
• jest niebezpieczny, dziecko dziedziczy wszystkie uprawnienia po rodzicu a programista jest odpowiedzialny za usunięcie wszystkich rzeczy, np. deskryptorów plików, których dziecko nie potrzebuje. fork łamie zasadę najmniejszego uprzywilejowania;
• jest powolny, przeglądarka Chrome doświadcza czasów fork rzędu 100ms, a słaba wydajność powoduje, że posix_spawn nie wykorzystuje zazwyczaj fork, a Solaris implementuje spawn jako natywne wywołanie systemowe;
• nie jest skalowalny, sposobem do stworzenia skalowalnego systemu jest unikanie niepotrzebnego dzielenia, jednak sforkowany proces dzieli wszystko ze swoim rodzicem;
• prowadzi do przesadnej alokacji pamięci, gdy duży proces wywołuje fork, należy stworzyć wiele mapowań stron copy-on-write, które prawdopodobnie nigdy nie zostaną zmodyfikowane.

fork jest wygodnym API dla procesów jednowątkowych, które używają mało pamięci, nadaje się on do implementacji powłok, problemem jest to, żę większość programów nie jest powłokami.

posix_spawn(3) tworzy nowy proces dziecko, który wykonuje wskazany plik (łączy ze sobą fork i exec, działa więc podobnie do CreateProcess() z WinNT). API posix_spawn ułatwia refaktoryzację kodu, który zawierał w/w wywołania, które mogły znajdować się w odległych miejscach w kodzie.

Zadanie 2

Zaprezentuj sytuację, w której proces zostanie osierocony. W terminalu uruchom dodatkową kopię powłoki bash. Z jej poziomu wystartuj sleep 1000 jako zadanie drugoplanowe i sprawdź, kto jest jego rodzicem. Poleceniem kill wyślij sygnał SIGKILL do uruchomionej wcześniej powłoki i sprawdź, kto stał się nowym rodzicem procesu sleep. Wyjaśnij przebieg i wyniki powyższego eksperymentu. Wytłumacz zachowanie eksperymentu, gdy zamiast SIGKILL wyślemy powłoce sygnał SIGHUP.

Wskazówka: Uruchom powłokę przy pomocy polecenia strace -e trace=signal.

Proces osierocony to proces, którego rodzic zmarł, a on nadal żyje. Taki proces po zabiciu rodzica zostaje przepięty do init (PID 1), lub innego żniwiarza.

strace -e trace=signal bash # właściwie bash by wystarczył
sleep 1000 &
ps ax -o pid,ppid,command | grep sleep
kill -KILL 0
ps ax -o pid,ppid,command | grep sleep

U mnie nowym rodzicem zostaje PID 2142.

$ cat /proc/2142/cmdline 
/lib/systemd/systemd --user

Przy SIGHUP podobnie, ale SIGHUP zostaje rozesłany przez bash, więc zabije sleepa. Używając info bash możemy uzyskać następującą informację: "The shell exits by default upon receipt of a SIGHUP. Before exiting, an interactive shell resends the SIGHUP to all jobs, running or stopped. Stopped jobs are sent SIGCONT to ensure that they receive the SIGHUP."

Zadanie 3

Wyświetl konfigurację terminala przy pomocy polecenia stty -a i wskaż znaki które (a) sterownik terminala zamienia na sygnały związane z zarządzaniem zadaniami (b) służą do edycji wiersza. Możliwości edycji wiersza zaprezentuj na przykładzie polecenia cat. Następnie uruchom find / i obserwuj zachowanie programu po naciśnięciu kombinacji klawiszy CTRL+S i CTRL+Q – jakie sygnały wysyła sterownik terminala do zadania pierwszoplanowego? Następnie wstrzymaj zadanie pierwszoplanowe sleep 1000 i przy pomocy wbudowanego polecenia powłoki bg przenieś to zadanie do wykonania w tle. Jaki sygnał został użyty do wstrzymania zadania? Na przykładzie programu vi wskaż kiedy program może być zainteresowany obsługą tego sygnału oraz SIGCONT.

Terminal to program pozwalający użytkownikom na uruchomienie powłoki, dzięki czemu umożliwiona jest komunikacja z powłoką.

speed 38400 baud; rows 50; columns 211; line = 0;
intr = ^C; quit = ^\; erase = ^?; kill = ^U; eof = ^D; eol = <undef>;
eol2 = <undef>; swtch = <undef>; start = ^Q; stop = ^S; susp = ^Z; rprnt = ^R;
werase = ^W; lnext = ^V; discard = ^O; min = 1; time = 0;
-parenb -parodd -cmspar cs8 -hupcl -cstopb cread -clocal -crtscts
-ignbrk -brkint -ignpar -parmrk -inpck -istrip -inlcr -igncr icrnl ixon -ixoff
-iuclc -ixany -imaxbel iutf8
opost -olcuc -ocrnl onlcr -onocr -onlret -ofill -ofdel nl0 cr0 tab0 bs0 vt0 ff0
isig icanon iexten echo echoe echok -echonl -noflsh -xcase -tostop -echoprt
echoctl echoke -flusho -extproc

Sygnały związane z zarządzaniem zadaniami:

• intr wysyła sygnał przerwania
• quit wysyła sygnał zamknięcia
• swtch włącza inną warstwę powłoki
• start/stop wznawia/wstrzymuje wyświetlanie
• susp wysyła sygnał stop

Sygnały związane z edycją wiersza (do zaprezentowania z cat):

• erase kasuje ostatni wprowadzony znak,
• kill
• eof wysyła znak końca pliku (końca wejścia)
• eol/eol2 wysyła znak końca wiersza
• werase kasuje ostatnie wprowadzone słowo
• rprnt powtarza bieżący wiersz
• lnext wprowadza kolejny znak w cudzysłowie

Uruchamiając find /, a następnie używając CTRL+S i CTRL+Q można zatrzymać, a następnie wznowić wyświelanie wyjścia. Kombinacje te nie wysyłają żadnego sygnału, są one częścią software flow control. XOFF (czyli ^S) powiadamia proces/urządzenie wysyłające dane, że bufor wejścia jest pełny i nie powinny być już wysyłane żadne dane. Terminal odpowiada za obsługę tych wywołań i jest odpowiedzialny za ich obsługę - może umożliwić dalsze działanie i wysyłanie danych, odrzucenie danych, czy wznowienie po otrzymaniu XON (^Q).

Proces pierwszoplanowy to proces uruchamiany bezpośrednio, na który czekamy aż się zakończy (wywołanie dowolnej komendy bez &). Możemy zobaczyć jego interfejs, "porozumiewać się" z nim na bieżąco, w przeciwieństwie do procesu drugoplanowego.

Teraz uruchamiamy sleep 1000 i wstrzymujemy go (CTRL+Z) sygnałem SIGTSTP. Poleceniem bg możemy je przenieść do działania w tle. W vi/vim wstrzymać proces możemy będąc poza insert mode, a powracamy do niego poleceniem fg, które wywołuje sygnał SIGCONT.

Zadanie 4

Uruchom w powłoce bash polecenie cat - &. Czemu zadanie zostało od razu wstrzymane? Jaki sygnał otrzymało? Zakończ to zdanie wbudowanym poleceniem powłoki kill. Następnie porównaj działanie polecenia cat /etc/shells & przed i po zmianie konfiguracji terminala poleceniem stty tostop. Jaki efekt ma włączenie flagi tostop na zachowanie sterownika terminala?

Zauważ, że powłoka dostaje SIGCHLD w wyniku zmiany stanu procesu potomnego, a nie tylko jego zakończenia, i ewentualnie wybiera grupę pierwszoplanową. Jak przy pomocy waitpid(2) rozróżnić wstrzymanie i kontynuowanie od zakończenia procesu potomnego? Jaka funkcja biblioteki standardowej służy do wyboru grupy pierwszoplanowej?

Program zostaje od razu wstrzymany sygnałem SIGSTOP. Użycie - w miejscu nazwy pliku jest postrzegane przez cat jako synonim do stdin, przez co program zostaje natychmiastowo wstrzymany, jako że nic nie może się wtedy znależć w stdin.

Wbudowane polecenie powłoki to polecenie, które powłoka uruchamia bezpośrednio, bez wywoływania innego programu.

Wywołanie cat /etc/shells & sprawia, że wypisywana jest zawartość całego pliku, a następnie program się kończy. Po zmianie konfiguracji poleceniem stty tostop, do grupy procesów drugoplanowych (bg) próbujących pisać do ich terminala (a dokładniej sesji, w którym zostały one uruchomione) zostaje wysłany sygnał SIGTTOU. Domyślnie zatrzymuje on wszystkie procesy w grupie procesów, jednak w tym przypadku zatrzymuje procesy drugoplanowe, które chcą pisać do terminala, przez co po uruchomieniu cat /etc/shells & nie otrzymamy żadenj informacji poza tym, że proces został wstrzymany. Możemy go jednak wznowić fg i dostaniemy oczekiwany output.

Wywołanie poniższej funkcji:

pid_t waitpid(pid_t pid, int *wstatus, int options);

zapisuje do wstatus dane o zmianie stanu dziecka. Za pomocą makr WIFEXITED(), WIFSTOPPED(), WIFCONTINUED() można dostać informacje o tym, czy dziecko zakończyło się w zwykły sposób, zostało zatrzymane sygnałem, czy też otrzymało SIGCONT i kontynuuje działanie.

(APUE 9.7)
Aby wybrać grupę pierwszoplanową (ang. foreground group), możemy użyć funkcji:

int tcsetpgrp(int fd, pid_t pgrpid);

Ustawiając argument pgrpid na odpowiednią wartość, zmieniamy grupę pierwszoplanową.

Zadanie 5

Procedury setjmp(3) i longjmp(3) z biblioteki standardowej języka C służą do wykonywania nielokalnych skoków. Uproszczone odpowiedniki tych procedur znajdują się w pliku libcsapp/Setjmp.s, a definicja Jmpbuf w pliku include/csapp.h. Wyjaśnij co robią te procedury, a następnie przeprowadź uczestników zajęć przez ich kod. Dlaczego Jmpbuf nie przechowuje wszystkich rejestrów procesora? Czemu Longjmp zapisuje na stos wartość przed wykonaniem instrukcji ret?

W C nie można użyć goto znajdującego się w innej funkcji, dlatego musimy skorzystać z setjmp oraz longjmp. Funkcję setjmp wywołujemy w miejscu, do którego chcemy wrócić (i tam powinna zwrócić 0, jako że wywołaliśmy ją bezpośrednio). W argumencie przekazujemy środowisko env, a więc np. jmpbuffer (typu jmp_buf, zadeklarowanego globalnie). Funkcja longjmp używa danych z env do przekazania kontroli w miejsce, w którym setjmp zostało wywołane i przywraca stos do stanu w czasie wywołania setjmp. Gdy longjmp się powiedzie, program będzie działał dalej i setjmp zwróci wartość drugi raz - będzie to wartość przekazana w argumencie val, a gdy programista przekaże 0 do val, to zwrócone zostanie 1.

Jmpbuf nie przechowuje wszystkich rejestrów procesora, gdyż jest to funkcja taka jak każda inna, dlatego może odrzucić rejestry caller-saved, które przechowują wartości tymczasowe. Dzięki temu nie trzeba ich zapisywać i przywracać.

Longjmp zapisuje na stos wartość %r11, do której wcześniej przypisany był %rip, dzięki temu wiadomo, którą instrukcję należy wykonać po powrocie.

/* Setjmp & longjmp implementation without sigprocmask */
typedef struct {
  long rbx;
  long rbp;
  long r12;
  long r13;
  long r14;
  long r15;
  void *rsp;
  void *rip;
} Jmpbuf[1];

int Setjmp(Jmpbuf env);
noreturn void Longjmp(Jmpbuf env, int val);

_JB_RBX = 0
_JB_RBP = 1 # poczatek stosu
_JB_R12 = 2
_JB_R13 = 3
_JB_R14 = 4
_JB_R15 = 5
_JB_RSP = 6 # biezaca lokalizacja na stosie
_JB_RIP = 7 # wskaznik instrukcji

        .text

        .globl Setjmp
        .type Setjmp,@function

Setjmp: # int Setjmp(Jmpbuf env (%rdi)):
	movq    (%rsp),%r11 # przenosimy adres powrotu do r11 (kopia zapasowa)
	movq    %rbx,(_JB_RBX * 8)(%rdi) # przenosimy rejestry do jmp_buf
	movq    %rbp,(_JB_RBP * 8)(%rdi)
	movq    %r12,(_JB_R12 * 8)(%rdi)
	movq    %r13,(_JB_R13 * 8)(%rdi)
	movq    %r14,(_JB_R14 * 8)(%rdi)
	movq    %r15,(_JB_R15 * 8)(%rdi)
	movq    %rsp,(_JB_RSP * 8)(%rdi)
	movq    %r11,(_JB_RIP * 8)(%rdi)
	xorl	%eax,%eax
	ret
        .size Setjmp, . - Setjmp
        
        .globl Longjmp
        .type Longjmp,@function
Longjmp: # noreturn void Longjmp(Jmpbuf env (%rdi), int val (%esi)):
	movq    (_JB_RBX * 8)(%rdi),%rbx # przywracamy rejestry z jmp_buf
	movq    (_JB_RBP * 8)(%rdi),%rbp
	movq    (_JB_R12 * 8)(%rdi),%r12
	movq    (_JB_R13 * 8)(%rdi),%r13
	movq    (_JB_R14 * 8)(%rdi),%r14
	movq    (_JB_R15 * 8)(%rdi),%r15
	movq    (_JB_RSP * 8)(%rdi),%rsp
	movq    (_JB_RIP * 8)(%rdi),%r11
	movl	%esi,%eax # przenosimy drugi argument do %rax, jesli jest rowny
                         # 0, to zmieniamy go na 1
	testl	%eax,%eax
	jnz	1f # if (!eax) eax = 1; else goto 1;
	incl	%eax
1:	movq	%r11,(%rsp) # umieszczenie starego %rip (z %r11) na stos
	ret
        .size Longjmp, . - Longjmp

Zadanie 6

Uzupełnij program game tj. prostą grę w szybkie obliczanie sumy dwóch liczb. Zadaniem procedury readnum jest wczytać od użytkownika liczbę. Jeśli w międzyczasie przyjdzie sygnał, to procedura ma natychmiast wrócić podając numer sygnału, który przerwał jej działanie. W przeciwnym przypadku zwraca zero i przekazuje wczytaną liczbę przez pamięć pod wskaźnikiem num_p. Twoja implementacja procedury readnum musi wczytać całą linię w jednym kroku! Należy wykorzystać procedury siglongjmp(3), sigsetjmp(3) i alarm(2). Kiedy Twój program będzie zachowywać się poprawnie zamień procedury nielokalnych skoków na longjmp(3) i setjmp(3). Czemu program przestał działać?

static void signal_handler(int signo)
{
     siglongjmp(env, signo);
}

static int readnum(int *num_p)
{
    char line[MAXLINE];
    int n;

    alarm(1);
    n = sigsetjmp(env, 0);

    if(n)
    {
        *num_p = 0;
        return n;
    }
    
    Read(STDIN_FILENO, line, MAXLINE);
    *num_p = atoi(line);
    
    return 0;
}

Problem pojawia się przy longjmp i setjmp, ponieważ w standardzie nie jest określone czy te dwie funkcje zachowują maskę bitów.

Zadanie 7

Program coro wykonuje trzy współprogramy połączone ze sobą w potok bez użycia pipe(2). Pierwszy z nich czyta ze standardowego wejścia znaki, kompresuje białe znaki i zlicza słowa. Drugi usuwa wszystkie znaki niebędące literami. Trzeci zmienia wielkość liter i drukuje znaki na standardowe wyjście.

W wyniku wykonania procedury coro_yield współprogram przekazuje niezerową liczbę do następnego współprogramu, który otrzyma tę wartość w wyniku powrotu z coro_yield. Efektywnie procedura ta implementuje zmianę kontekstu. Taką prymitywną formę wielozadaniowości kooperacyjnej (ang. cooperative multitasking) można zaprogramować za pomocą setjmp(3) i longjmp(3).

Uzupełnij procedurę coro_add tak, by po wznowieniu kontekstu przy pomocy Longjmp wykonała procedurę fn, po czym zakończyła wykonanie współprogramu. Zaprogramuj procedurę coro_switch tak, by wybierała następny współprogram do uruchomienia i przełączała na niego kontekst. Jeśli współprogram przekazał wartość parametru EOF, to należy go usunąć z listy aktywnych współprogramów.

Program używa listy dwukierunkowej TAILQ opisanej w queue(3). Zmienna runqueue przechowuje listę aktywnych współprogramów, running bieżąco wykonywany współprogram, a dispatcher kontekst programu, do którego należy wrócić, po zakończeniu wykonywania ostatniego aktywnego współprogramu.

Wartość EOF możemy przekazać kombinacją CTRL + D.

#include "queue.h"
#include "csapp.h"

#define CORO_STKSIZE 4096
#define CORO_STKALIGN 16 /* As required by SysV ABI ! */

#ifndef EOF
#define EOF (-1)
#endif

#ifndef NOTHING
#define NOTHING (-2)
#endif

typedef struct coro {
  TAILQ_ENTRY(coro) co_link;
  const char *co_name;
  void *co_stack;
  Jmpbuf co_ctx;
} coro_t;

static TAILQ_HEAD(, coro) runqueue = TAILQ_HEAD_INITIALIZER(runqueue);
static coro_t *running;
static Jmpbuf dispatcher;

/* Initialize coroutine stucture with stack. */
static void coro_init(coro_t *co, const char *name) {
  memset(co, 0, sizeof(coro_t));
  co->co_name = name;
  /* Allocates a fresh stack for the coroutine! */
  if (posix_memalign(&co->co_stack, CORO_STKALIGN, CORO_STKSIZE) < 0)
    unix_error("posix_memalign error");
}

/* Detach a stack from coroutine structure. */
static void coro_destroy(coro_t *co) {
  free(co->co_stack);
}

/*
 * Switch between subsequent coroutines.
 *
 * Dead coroutines, i.e. ones that returned EOF, get removed from the run queue.
 * Feed next coroutine (value returned from coro_yield) with the result from
 * previous one (parameter passed to coro_yield).
 * Return to dispatcher if there're no more coroutines to run.
 */
static noreturn void coro_switch(int v) {
  coro_t *curr = running;
  /* TODO: Use description above to implement the body. */
  if(v==EOF)
  {
    TAILQ_REMOVE(&runqueue,curr,co_link);
    if(TAILQ_EMPTY(&runqueue))
    {
      Longjmp(dispatcher,NOTHING);
    }
  }
  if(TAILQ_NEXT(curr,co_link)==NULL)
  {
    running=TAILQ_FIRST(&runqueue);
    Longjmp(TAILQ_FIRST(&runqueue)->co_ctx,v);
  }
  running=TAILQ_NEXT(curr,co_link);
  Longjmp(running->co_ctx,v);
}

/* Save caller context and switch back to next coroutine. */
static int coro_yield(int v) {
  int nv = Setjmp(running->co_ctx);
  if (nv == 0)
    coro_switch(v);
  return nv;
}

/* Configure coroutine context to be executed. */
static void coro_add(coro_t *co, void (*fn)(int)) {
  int v = Setjmp(co->co_ctx);
  if (v) {
    /* This will get executed when coroutine is entered first time. */
    fn(v);
    /* Coroutine must pass EOF to be removed from runqueue! */
    coro_switch(EOF);
  }
  /* Coroutine will be running on its private stack! */
  co->co_ctx->rsp = co->co_stack + CORO_STKSIZE;
  TAILQ_INSERT_TAIL(&runqueue, co, co_link);
}

/* Take first coroutine and feed it with passed value. */
static int coro_run(int v) {
  running = TAILQ_FIRST(&runqueue);
  int nv = Setjmp(dispatcher);
  if (nv == 0)
    Longjmp(running->co_ctx, v);
  return nv;
}

/*
 * Actual coroutines that perform some useful work.
 */

static void func_1(int _) {
  int words = 0;
  char prev_ch = ' ';
  char ch;

  while (Read(0, &ch, 1) > 0) {
    if (isspace(ch)) {
      if (isspace(prev_ch))
        continue;
      words++;
    }
    coro_yield(ch);
    prev_ch = ch;
  }

  if (!isspace(ch))
    words++;

  dprintf(STDERR_FILENO, "\nfunc_1: words = %d\n", words);
}

static void func_2(int ch) {
  int removed = 0;

  while (ch != EOF) {
    if (!isalpha(ch)) {
      removed++;
      ch = NOTHING;
    }
    ch = coro_yield(ch);
  }
 
  dprintf(STDERR_FILENO, "func_2: removed = %d\n", removed);
}

static void func_3(int ch) {
  int printed = 0;

  while (ch != EOF) {
    if (ch != NOTHING) {
      printed++;
      if (islower(ch))
        ch = toupper(ch);
      else if (isupper(ch))
        ch = tolower(ch);
      Write(STDOUT_FILENO, &ch, 1);
    }
    ch = coro_yield(NOTHING);
  }

  dprintf(STDERR_FILENO, "func_3: printed = %d\n", printed);
}

int main(void) {
  coro_t co[3];

  coro_init(&co[0], "func_1");
  coro_init(&co[1], "func_2");
  coro_init(&co[2], "func_3");
  coro_add(&co[0], func_1);
  coro_add(&co[1], func_2);
  coro_add(&co[2], func_3);
  coro_run(NOTHING);
  coro_destroy(&co[0]);
  coro_destroy(&co[1]);
  coro_destroy(&co[2]);

  dprintf(STDERR_FILENO, "Bye, bye!\n");

  return EXIT_SUCCESS;
}