Celem wykładu jest przedstawienie organizacji wewnętrznej jądra systemu operacyjnego [FreeBSD](https://www.freebsd.org), który wyrósł ze źródeł oryginalnego systemu Unix z początku lat '80. FreeBSD znajduje zastosowanie np. w konsolach _Sony Playstation_ i chmurze _Netflix_. W trakcie naszej przygody będziemy zaglądać do pozostałych jąder z rodziny BSD, tj: [OpenBSD](https://www.openbsd.org/), [NetBSD](https://www.netbsd.org/), [DragonFlyBSD](https://www.dragonflybsd.org/). Nauka programowania sterowników dla systemu _FreeBSD_ nie jest częścią tych zajęć.
Na ćwiczeniach będziemy omawiać wybrane podsystemy jądra oraz najciekawsze algorytmy i struktury danych bazując na [źródłach FreeBSD](http://bxr.su/FreeBSD/sys/kern/).
Celem pracowni programistycznej jest otrzymanie małego systemu z prostą uniksową powłoką, kilkoma użytecznymi programami (`grep`, `cat`, `kill`, ...) i edytorem pełnoekranowym. Będziecie uzupełniać wybrane podsystemy istniejącego szkoleniowego systemu operacyjnego:
* sterownik terminala,
* zarządzanie procesami,
* wywołania systemowe,
* system plików,
* komunikacja z użyciem potoków,
* obsługa sygnałów.
**UWAGA!** Zaliczenie tych zajęć jest mocno wskazane do uczestnictwa w projekcie Mimiker.
##### Tematy wykładów
1. Model prostej maszyny:
* model programowy: rejestry i stos,
* tryby pracy procesora,
* rejestry i zasoby uprzywilejowane,
* przerwania: wektor, priorytety, EOI,
* komunikacja z peryferiami i transfery DMA,
* podstawowe peryferia: czasomierz i port szeregowy,
* pułapki i dane o błędach.
2. Organizacja dyspozytora:
* górna i dolna połówka,
* kolejki zadań aktywnych,
* przechowywanie kontekstu zadania,
* dobrowolna zmiana kontekstu,
* blokowanie przerwań i _priority level_,
* algorytm obsługi przerwań i łańcuchy procedur obsługi,
* obsługa pułapek, `trapframe` i poprawianie kontekstu,
* realizacja i blokowanie wywłaszczania.
3. Podstawowe usługi jądra:
* zarządzanie pamięcią,
* struktura opisująca zadanie i jego kontekst,
* globalne struktury planisty i dyspozytora,
* zegara systemowy i mierzenie czasu,
* realizacja sekcji krytycznych,
* blokowanie, usypianie i wznawianie zadań,
* rozruch planisty i zadanie jałowe,
* wątki obsługi przerwań.
4. Obsługa zdarzeń:
* rodzaje kontekstów i snu,
* zegar systemowy `hardclock` i wywłaszczanie,
* kolejki wątków aktywnych `runqueue` i priorytety wątków,
* przełączanie zadań `mi_switch`,
* kolejki wątków uśpionych `sleepqueue`,
* obsługa terminów `callout`,
* główna procedura obsługi przerwań i zdarzenia sprzetowe `intr_event`,
* wątki obsług przerwań `ithread`,
* realizacja wywłaszczania `ast` i `userret`,
* blokowanie wątków `turnstile`,
* tłumaczenie pułapek na sygnały i obsługa błędów,
* implementacja wywołań systemowych `sysent`,
* bezpieczne kopiowanie danych `copyin` i `copyout`.
5. Synchronizacja w systemach jedno i wieloprocesorowych:
* instrukcje atomowe, bariery pamięciowe i blokady wirujące,
* problem fałszywego współdzielenia i przeciążenia magistrali,
* przerwania międzyprocesorowe,
* wyłączanie przerwań i wywłaszczania,
* hierarchia blokad i zabronione konfiguracje,
* projektowanie oprogramowania z użyciem blokad – domeny blokowania,
* usypianie `sleep` i wybudzanie wątków `wakeup`,
* omówienie implementacji `sleepqueue`,
* problem odwrócenia priorytetów i dziedziczenie priorytetów,
* łańcuchowa propagacja priorytetów,
* omówienie implementacji `turnstile`.
6. Środki synchronizacji:
* interfejs blokad `lock`,
* blokady wirujące `MTX_SPIN` i algorytm _back-off_,
* blokady adaptacyjne `MTX_DEF`,
* blokady współdzielone `rwlock` i zapobieganie głodzeniu,
* zmienne warunkowe `cv`,
* blokady wirtualnego systemu plików `lockmgr`,
* strategie korzystania z blokad – zapobieganie zakleszczeniom i współzawodnictwu,
* wykrywanie zakleszczeń z użyciem `witness`.
7. Obsługa terminów i planowanie zadań:
* rejestrowanie i przetwarzanie terminów `callout`,
* omówienie struktury kolejki kalendarzowej,
* klasy szeregowania zadań i algorytm _multilevel feedback queue_,
* klasyczny algorytm szeregowania `sched_4bsd`,
* wyznaczanie średniego obciążenia systemu,
* algorytm dla systemów wieloprocesorowych `sched_ule`,
* problemy z szeregowaniem w systemach wieloprocesorowych,
* topologia systemu i równoważenie obciążenia,
* interfejs planisty `csf`.
8. Zarządzanie procesami:
* zasoby procesu: wątki, przestrzeń adresowa, tablica deskryptorów, kredencjały,
* stan procesu vs. stan wątków,
* struktury przechowujące procesy i ich blokady,
* leniwe kopiowanie przestrzeni adresowej,
* wstrzymywanie wszystkich wątków w procesie,
* ładowanie programów i aktywatory obrazów,
* omówienie implementacji `fork`, `exit` i `execve`.
9. Sygnały, grupy procesów i sesje:
* rejestracja procedur obsługi sygnałów,
* domyślne akcje i właściwości sygnałów,
* wysyłanie sygnałów `psignal` i `pgsignal`,
* dostarczanie sygnałów `postsig` i `sendsig`,
* przygotowanie kontekstu procesu do obsługi sygnału,
* powrót z procedury obsługi sygnału `sigreturn`
* oczekiwanie na zmianę stanu procesu `waitpid`,
* wchodzenie i opuszczanie grupy procesów: `enterpgrp` i `leavepgrp`,
* sesje, lider sesji, terminal sterujący.
10. Zarządzanie tablicą stron:
* rozruch jądra w adresach wirtualnych,
* reprezentacja ramek `vm_page`,
* wprowadzanie `pmap_enter` i usuwanie `pmap_remove` odwzorowań,
* zmiana uprawnień odwzorowań `pmap_protect`,
* przełączanie przestrzeni adresowej `pmap_activate`,
* interakcje z buforem translacji adresów TLB i zestrzeliwanie wpisów (_TLB shootdown_),
* emulowanie bitów `referenced` i `modified`,
* odwzorowania odwrotne `pv_entry`,
* obsługa dużych stron `superpages`.
10. Zarządzanie pamięcią jądra:
* przydział pamięci fizycznej `buddy`,
* reprezentacja przestrzeni adresowej jądra `vm_map`,
* przydział przestrzeni adresowej `vmem`,
* alokator płytowy `slab`,
* algorytm strefowy i zarządzanie `bucket` oraz `keg`,
* omówienie ogólnego algorytmu przydziału pamięci `kmalloc`.
11. Zarządzanie przestrzenią adresową:
* obiekty wspierające `vm_object` – anonimowe nazwane i przesłaniające,
* obsługa błędu strony `vm_fault`,
* odwzorowania prywatne i dzielone,
* programy stronicujące `pager` dla obiektów nazwanych i pamięci anonimowej,
* kompresja łańcuchów odwzorowań przesłaniającyh,
* algorytm zastępowania stron,
* usługa stronicowania `pageout daemon`.
13. Operacje na plikach:
* tablica deskryptorów `filedesc` i reprezentacja plików `file`,
* pliki strumieniowe i o swobodnym dostępie.
* współdzielenie otwartych plików
* interfejs operacji na plikach `fileops`
* punkty wejścia do wirtualnego systemu plików – pliki zwykłe oraz katalogi,
* komunikacja między procesowa – potoki,
* nieblokujące operacje wejścia-wyjścia `select` i `kqueue`.
14. Wirtualny system plików:
* węzły wirtualnego systemu plików `vnode` i `vnodeops`,
* punkty montażowe `mount` i `vfsops`,
* zarządzanie węzłami i buforami,
* tłumaczenie ścieżek na węzły `iname`,
* pamięć podręczna tłumaczenia ścieżek `namecache`,
* buforowanie bloków `bread` i `bwrite`.
