# Struktura jądra UNIX - notatki
###### tags: `notatki` `sju21`

## Motorola 68000
### Rejestry
**Rejestry użytkownika:**
**Rejestr stanu:**

### Tryby pracy procesora
Program wykonywany w **trybie nadzorcy** (ang. *supervisor mode*) ma dostęp do wszystkich zasobów komputera, w tym do wszystkich rejestrów procesora. Dlatego zwykłe programy powinny być wykonywane w **trybie użytkownika**.
**Instrukcje uprzywilejowane** mogą być wykonywane tylko w **trybie nadzorcy**.
Gdyby instrukjce odnoszące się do rejestru stanu procesora były dostępne dla zwykłego użytkownika, mógłby on dowolnie nadpisać rejestr stanu procesora. W szczególności mógłby na przykład ustawić bit $S$, co sprawiłoby przejście procesora w tryb nadzorcy i dałoby programowi pełny dostęp do zasobów kompiutera.
Zmiana z trybu użytkownika na tryb nadzorcy może nastąpić jedynie w wyniku przetwarzania wyjątku lub przerwania. Poprzednia wartość bitu $S$ jest zapisywana, a następnie bit jest ustawiany co oznacza przejście w tryb uprzywilejowany. Po wszystkim przywracana jest stara wartości bitu $S$ i ewentualne przejście w tryb użytkownika (jeżli $S$ był poprzednio zgaszony).
Przejście z trybu nadzorcy do trybu użytkownika może być skutiem wykonania jedynie tych czterech operacji:
1. `RTE`
2. `MOVE to SR`
3. `ANDI to SR`
4. `EORI to SR`

### Wyjątki
**Wektor wyjątków procesora** to tablica zawierająca adresy na procedury obsługi poszczególnych wyjątków. Tablica ta znajduje sie w przestrzeni adrsowej jądra. Adres odpowiedniego wpisu w tablicy obliczany jest według wzoru: $VBR + 4\cdot exception\_number$
Jest on inicjowany w procedurze [vPortSetupExceptionVector](https://mimiker.ii.uni.wroc.pl/source/xref/FreeRTOS-Amiga/kernel/port.c?r=e5a9f019#108).
Przed wykonaniem procedury przerwania procesor musi:
- Wykonać kopię rejestru stanu proceosra
- Odpowiedznio zmodyfikować rejestr stanu dla obsługi danego przerwania, tj. przejść w tryb uprzywilejowany (ustawić bit $S$) oraz zablokować przerwania od priorytecie niższym lub równym obecnemu przerwaniu (bity $I_{2,1,0}$) ==[?]==
- Uzyskać wektor wyjątków
- Zapisać obecny kontekst procesora ==[?]==
- Załadować nowy kontekst

---
## Jądro systemu operacyjnego
### Zadania jądra
1. Zarządzanie zasobami
- czas procesora
- pamięć operacyjna
- pamięć masowa
- urządzenia I/O
2. Dostarcza abstrakcji programom użytkownika
- pliki
- sygnały
- pamięć wirtualna
3. Reaguje na zdarzenia
- przerwania (urządzenia zewnętrzne)
- wyjątki
- pułapki

Wejście do jądra może nastąpić na dwa sposoby - synchronicznie lub asynchronicznie.
**Asynchroniczne punkty wejścia** to takie, które są niezależne od aktualnie przetwarzanych instrukcji. Pochodzą spoza programu. Są to:
- Przerwania od zegara systemowego
- Przerwania od urządzeń I/O

**Synchroniczne punkty wyjścia** wynikają bezpośrednio z przetwarzanych instrukcji. Należą do nich:
- Pułapki
- Wyjątki proceosora
- Page fault

### Podział jądra na części
**Bottom-half** odpowiada za obsługę przerwań. Kod wykonywany w dolnej połówce musi wykonać się cały za jednym razem. W trakcie powrotu z bh może nastąpić zmiana kontekstu (wywłaszczenie).

**Top-half** odpowiada za obsługę programu użytkownika (wywołania systemowe, błędne instrukcje). Procedura wykonywana w górnej połówce może zostać przerwana, np. może pójść spać w oczekiwaniu na zasób.

W niektórych systemach operacyjnych (np. Linux) terminologia jest odwrotna.

### Stany zadań

digraph G{
  Ready -> Running [label="dispatch"];
  Running -> Ready [label="preemption"];
  Running -> Dead [label="exit"];
  Running -> Blocked [label="block"];
  Blocked -> Ready [label="wakeup"];
  {rank=same; Ready, Running, Dead}
}

- `preemption` - przeewanie zegarowe
- `dispatch` - zmiana kontekstu
- `block` - oczekiwanie na zasób
- `wakeup` - przerwanie sprzętowe
- `exit` - koniec programu lub zabicie procesu

---
## FreeRTOS Amiga
### Procesy
**Scheduler** (planista) to algorytm odpowiadający za zarządzanie czasem procesora, poprzez wybieranie zadania do uruchomienia.
Jednym z prostszych algorytmów planowania jest **round-robin z pirorytetami**. Jądro systemu przechowuje listę kolejek zadań będących w stanie *ready* (po jednej kolejce dla każdego priorytetu). Scheduler wybiera pierwsze zadania z kolejki o najwyższym priorytecie. Jeżeli kolejka jest pusta, sprawdza kolejny priorytet. Jeżeli zadanie zostanie zablokowane, trafia do kolejki *BlockedQ*. Jeżeli nastąpi wywłaszczenie w wyniku przerwania zegarowego, gdy aktualne zadanie jeszcze nie zostało zakończone, trafia ono na koniec kolejki o odpowiednim priorytecie.
A co jeżeli nie byłoby żadnego zadania do wykonania (wszystkie kolejki są puste)?
Nie jest to możliwe.
**Idle Task** (zadanie jałowe) jest specjalnym zadaniem o najniższym priorytecie. Wykonywane jest ono kiedy nie ma innych zadań będących w stanie *ready*. Zadanie to nigdy nie może zostać zablokowane, jednak może ono uśpić procesor, w celu oszczędzania energii.

**Struktura zadania**
**Wybudzanie zadania**
**Blokowanie zadania**
**Zakończenie zadania**
**Synchornizacja bottom i top half**

---
## Organizacja jądra FreeBSD
### Stany oczekującego zadania
- **Brak snu** (*spinlock*, *blokada wirująca*) - polega na aktywnym czekaniu, stałym sprawdzaniu warunku.
- **Sen ograniczony** (*bounded sleep*) - zadanie czeka, aż przyznany zostanie mu czas procesora, aby dokończyć obliczenia; na przykład gdy w momencie wykonywania obsługi przerwania przyjdzie inne przerwanie o wyższym priorytecie, przechodziny w sen ograniczony - nie czekamy na zwolnienie żadnej blokady, po prostu czekamy aż oddany zostanie nam czas procesora.
- **Sen nieograniczony** (*unbounded sleep*) - zadanie oczekuje na zdarzenie zewnętrzne i nie można go wybudzić w żaden inny sposób (np. sygnałem); jest to intencją programisty, który spodziewa się, że zdarzenie nastąpi w niedalekiej przyszłości.
- **Sen nieograniczony przerywalny** (*interruptible*) - jak wyżej, z tą różnicą, że zadanie reaguje na sygnały.

Więcej szczegółów w podręczniku systemowym: [locking(9)](https://www.freebsd.org/cgi/man.cgi?query=locking&sektion=9)

### Kontekst procesora
- **Pełny kontekst** - wszystkie rejestry ogólnego przeznaczenia, rejestr stanu (tryb pracy, maska przerwań) oraz ewentualneinformacje o błędzie (np. adres w przypadku błędu odwołania do pamięci)
- **Skrócony kontekst** - rejestry ogólnego przeznaczenia *caller-saved* oraz rejestr stanu
- **Kontekst translacji adresów** - globalna tablica stron bieżącego procesu

### Przewrwania we FreeBSD
**Wątki przerwań** [ithread(9)](https://www.freebsd.org/cgi/man.cgi?query=ithread&sektion=9) - specjalne wątki jądra o wysokich priorytetach, będące wybudzane w wyniku przyjścia przerwania. Dany wątek skojarzony jest z dokładnie jednym `intr_event`. Po wybudzeniu wątek uruchamia procedury z posortowanej listy. Przed wybudzeniem wywoływana jest procedura `pre_ithread` blokująca odpowiednie przerwania. Podobnie po zakończeniu pracy wołana jest procedura `post_ithread` odblokowująca odpowiednie przerwania.
Wątki przerwań mogą czekać jedynie z użyciem blokad wirujących lub snu ograniczonego.

Obsługa przerwania przebiega w następujący sposób:
1. Procesor wyłącza przerwania
2. Zależnie od trybu w jakim znajdował się procesor w trakcie otrzymania przerwania:
- user: wywoływana jest procedura [`MipsUserIntr`](http://bxr.su/FreeBSD/sys/mips/mips/exception.S#692), a pełny kontekst procesora odkładany jest w [`td_pcb`](http://bxr.su/FreeBSD/sys/sys/proc.h#td_pcb)
- kernel: wywoływana jest procedura [`MipsKernIntr`](http://bxr.su/FreeBSD/sys/mips/mips/exception.S#621), a pełny kontekst procesora odkładany jest na stos jądra
3. Wybierany jest odpowiedni [`intr_event`](http://bxr.su/FreeBSD/sys/sys/interrupt.h#109) skojarzony z danym przerwaniem i wywoływana jest procedura [`intr_event_handle`](http://bxr.su/FreeBSD/sys/kern/kern_intr.c#intr_event_handle)
4. Procedura `filter` znajduje urządzenie wymagające obsługi zdarzenia i zwraca jedną z trzech wartości:
- `FILTER_STRAY`: oznacza to błąd - procedura `filter` nie mogła poradzić sobie z obsługą zdarzenia
- `FILTER_HANDLED`: zdarzenie było na tyle proste, że procedura `filter` sama poradziła sobie z jego obsługą
- `FILTER_SCHEDULE_THREAD`: zdarzenia było złożone i należało wybudzić odpowiedni wątek przerwania, aby je obsłużyć

---
## Obsługa wejścia-wyjścia

### Grupy wywołań systemowych
1. Abstrakcje nad procesorem i pamięcią fizyczną (RAM)
- Procesy
- Grupy procesów
- Sygnały
- Tożsamość
- Pamięć
2. Abstrakcje nad urządzeniamy wejścia-wyjścia:
- Czasomierze
- Operacje I/O
- Deskryptory plików
- Otwieranie plików
- Właściwości plików
- System plików
- Obsługa katalogów
- Bieżący katalog roboczy

### Rodzaje urządzeń
**Urządzenie znakowe** - adresowane bajtowo. Dzielą się na urządzenia ze swobodnym dostępem oraz bez swobodnego dostępu.
**Urządzenie blokowe** - adresowane blokowo, tj. możemy udczytać kolejne $n$ bajtów, zaczynając od adresu podzielnego przez $n$ (gdzie $n$ jest rozmiarem bloku, może się różnić zależnie od urządzenia).

### Sterowniki
**Device** - urządzenie sptrzętowe (stan)
**Driver** - sterownik (kod)
**Device file** - plik urządzenia (znakowego/blokowego). Nie umożliwia swobodnego dostępu (brak `lseek(2)`).

### Pliki
**Deskryptor pliku** jest swego rodzaju uchwytem dla każdego otwartego zasobu plikowego/plikopodobnego. Każdy proces posiada własną **tablicę deskryptorów**, w której deskryptory w postaci numerycznej (takimi posługuje się w programach) skojarzone są z odpowiednimi **wpisami pliku**.

struct file {
    volatile u_int  f_flag;     /* see fcntl.h */
    volatile u_int  f_count;    /* reference count */
    
    void            *f_data;    /* file descriptor specific data */
    struct fileops  *f_ops;     /* File operations */
    struct vnode    *f_vnode;   /* NULL or applicable vnode */
    struct ucred    *f_cred;    /* associated credentials. */
    short           f_type;     /* descriptor type */
    short       f_vnread_flags; /* (f) Sleep lock for f_offset */
    
    ...
    
    off_t       f_offset;
};

Pole `f_type` definiuje do jakiego rodzaju zasobu odnosi się deskryptor. Możliwości są następujące:

#define DTYPE_NONE      0   /* not yet initialized */
#define DTYPE_VNODE     1   /* file */
#define DTYPE_SOCKET    2   /* communications endpoint */
#define DTYPE_PIPE      3   /* pipe */
#define DTYPE_FIFO      4   /* fifo (named pipe) */
#define DTYPE_KQUEUE    5   /* event queue */
#define DTYPE_CRYPTO    6   /* crypto */
#define DTYPE_MQUEUE    7   /* posix message queue */
#define DTYPE_SHM       8   /* swap-backed shared memory */
#define DTYPE_SEM       9   /* posix semaphore */
#define DTYPE_PTS       10  /* pseudo teletype master device */
#define DTYPE_DEV       11  /* Device specific fd type */
#define DTYPE_PROCDESC  12  /* process descriptor */
#define DTYPE_LINUXEFD  13  /* emulation eventfd type */
#define DTYPE_LINUXTFD  14  /* emulation timerfd type */

Parametry każdego wywołania `read(2)` i `write(2)` są w jądrze tłumaczone do struktury `uio(9)`.

struct uio {
  struct iovec * uio_iov;
  int uio_iovcnt;
  off_t uio_offset;
  ssize_t uio_resid;
  enum uio_seg uio_segflg;
  enum uio_rw uio_rw;
  struct thread *uio_td;
};

struct iovec {
  void * iov_base;
  size_t iov_len;
};

---
### Multipleksowane wejście-wyjście
1. nonblocking I/O - proces kręci się w pętli i sprawdza możliwość wykonania operacji I/O na każdym deskryptorze po kolei; jest to bardzo niepraktyczne - zbędnie zużywa czas CPU
2. signal-driven I/O - jeśli na danym deskryptorze pojawi się możliwość wykonania operacji I/O, wyślij sygnał `SIGIO` do procesu; jest to niepraktyczne przy dużej liczbie deskryptorów - proces otrzyma jedynie sygnał, nie będzie jednak wiedział, którego deskryptora on dotyczy, więc będzie musiał sprawdzić wszystkie
3. polling I/O - proces jest usypiany do momentu pojawienia się zdarzenia na deskryptorze z grupy przekazanej jako argument; po wybudzeniu proces ma informacje, którego deskryptora dotyczyło zdarzenie; polling wymaga jednak stworzenia i utrzymania w pamięci dużej struktury danych dla procesu; dodatkowo nie wiadomo ile bajtów chce przeczytać/zapisać proces, więc może zostać niepotrzebnie wyvudzony gdy do odczytania będzie za mało bajtów/nie będzie wystarczająco dużo miejsca do zapisania
4. kernel-event polling - zoptymalizowany polling

**Polling I/O:**

int select(int nfds, fd_set *readfds,
           fd_set *writefds, fd_set *exceptfds,
           struct timeval *timeout);

int poll(struct pollfd fds[], nfds_t nfds,
         int timeout);
         
struct pollfd {
  int fd;
  short events;
  short revents;
};