## Struktura jądra Unix 2021 ### Wykład 2: Organizacja jądra ###### tags: `sju21` `presentation` --- ### Czym jest jądro SO? 1. Zarządza zasobami: * czasem procesora(-ów) * pamięcią operacyjną i drugorzędną * dostępem do urządzeń wejścia-wyjścia 2. Dostarcza abstrakcji programom użytkownika: * pliki, sygnały, pamięć wirtualna 3. Reaguje na zdarzenia pochodzące od: * urządzeń zewnętrznych (przerwania) * programów użytkownika (pułapki, wyjątki) --- ### Asynchroniczne punkty wejścia 1. Przerwanie od zegara systemowego: * odebranie czasu procesora bieżącemu zadaniu &rarr; wywłaszczanie * przełącza na inne zadanie 2. Przerwanie od urządzeń wejścia-wyjścia: * wybudza zadania oczekujące na zdarzenie sprzętowe * przełącza na zadanie o wyższym priorytecie, jeśli takie zostało wybudzone --- ### Synchroniczne punkty wejścia 1. Pułapka wywołania systemowego: * realizuje funkcję jądra na rzecz programu użytkownika * modyfikuje kontekst wywołania 2. Wyjątki procesora: * obsługiwane przez jądro; np. pomniejszy błąd strony * błędy aplikacji; np. błąd uprawnień strony, dzielenie przez zero; mogą być zamienione na sygnały --- ### Podział jądra na części Zbiory procedur jądra wykonywane w wyniku: 1. przyjścia przerwania (`bottom-half`); wykonywane w całości za jednym razem; w trakcie powrotu z przerwania można zmienić kontekst &rarr; wywłaszczenie 2. obsługi programu użytkownika (`top-half`); mogą zostać przerwane albo zablokowane w wyniku oczekiwania na zdarzenie lub zasób &rarr; dobrowolna zmiana kontekstu <small>**Uwaga!** Stosujemy terminologię `BSD`, w `Linux` jest na odwrót.</small> --- ### Stan zadań ```graphviz digraph G { {rank=same; Ready Running Dead;} Ready->Running [label = "dispatch"]; Running->Ready [label = "preemption"]; Blocked->Ready [label = "wakeup"]; Running->Blocked [label = "block"]; Running->Dead [label = "exit"] } ``` * `preemption` w wyniku przerwania zegarowego * `dispatch` gdy zmieniamy kontekst * `block` w wyniku oczekiwania * `wakeup` reakcja na przerwanie sprzętowe --- ### Round-robin z priorytetami Dyspozytor zmienia kontekst. Algorytm planowania (ang. _scheduler_) wybiera zadanie do uruchomienia.  <small>Opróżniamy kolejki od najwyższego numeru (`FreeRTOS`).</small> --- ### Synchronizacja części jądra **Obserwacja:** Zmiana kontekstu zachodzi w trakcie `block` i `preemption`, tj. odpowiednio w górnej i dolnej połówce. Podobnie z blokowaniem `block` i wybudzaniem `wakeup` zadania. Wykorzystywane te same struktury danych (`runq` i `sleepq`). **Jak uniknąć wyścigu?** 1. `top-half` &rarr; wyłączyć wszystkie przerwania 2. `bottom-half` &rarr; wyłączyć przerwania o wyższym priorytecie --- ### Synchronizacja w górnej połówce Dwa zadania korzystają z tej samej struktury danych. **Jak poprawnie je zsynchronizować?** 1. Wyłączmy przerwania, aby uniemożliwić zmianę kontekstu. **Wada:** opóźniamy obsługę przerwań. 2. Zapalmy globalny bit `NoSwitch`. Jeśli jest ustawiony przerwania nie będą wykonywać zmiany kontekstu. <small>Jeśli większość procedur wykonywanych w górnej połówce można bezpiecznie przerwać, to **jądro** jest **wywłaszczalne**. To jest trudne do zrobienia!</small> --- ### Struktura zadania Na każde zadanie struktura przechowująca: * wierzchołek stosu zadania; na górze stosu przechowujemy kontekst, jeśli zadanie nie jest w stanie `Running` * priorytet i czas spędzony na procesorze * węzły list `runq` i `sleepq` * stan zadania (patrz: diagram stanów) * licznik ile razy zawołaliśmy `PreemptDisable` * j.w. ale `IntrDisable` (opcjonalnie) --- ### Czy przerwanie ma kontekst? **NIE!** Procedura obsługi przerwania pożycza kontekst, w którym może się wykonać, od zadania, którego wykonanie przerwało. Jakie są tego następstwa? 1. Na stosie każdego zadania musi być wystarczająco dużo miejsca na obsługę przerwania. 2. Przerwanie nie ma własnegoa stosu i stanu, więc nie może wywołać funkcji blokującej. --- ### Przełączanie zadania Z **wyłączonymi przerwaniami** robimy: 1. Jeśli `NoSwitch` to wyjdź. 2. Dodaj `CurTsk` do `runq` / `sleepq`, `CurTsk.state` &larr; `Ready` / `Blocked` (odpowiednio dla wywłaszczenia / zablokowania) 3. `CurTsk` &larr; następne zadanie z `runq` 4. `state` &larr; `Running` <small>`CurTsk` to globalny wskaźnik na bieżąco wykonywane zadanie, `NoSwitch` globalna flaga zabraniająca przełączania zadań.</small> <small>**Obserwacja:** `runq` może być pusta! Co wtedy?</small> --- ### Zadanie jałowe `IdleTask` Nigdy nie może się zablokować i ma najniższy priorytet. Wykonywane, gdy kolejka `runq` pusta. Może uśpić procesor, żeby oszczędzać energię.  --- ### Wybudzanie zadań Obsługa przerwania może wybudzić więcej niż jedno zadanie. Pod dane przerwanie może być podpiętych wiele procedur obsługi. 1. `task` &larr; wyjmij zadanie ze `sleepq` 2. `task.state` &larr; `Ready` 3. włóż `task` do `runq` 4. jeśli `task.prio > CurTsk.prio` to `NeedResched = 1` <small>Globalna flaga `NeedResched` oznacza: zrób zmianę kontekstu przy najbliższej okazji.</small> <small>**Uwaga!** Jeśli wykonywane górnej połówce, to z wyłączonymi przerwaniami!</small> --- ### Blokowanie zadania Wykonanie z **wyłączonymi przerwaniami**: 1. sprawdź czy należy zablokować zadanie? NIE &rarr; pomiń resztę 2. zapisz kontekst na stos 3. przełącz zadanie (zmienia `CurTsk`!) 4. przełącz stos na `CurTsk.sp` 5. odtwórz kontekst --- ### Punkt wejścia do jądra Procedura obsługi przerwania (zał. $SR_{IM}=n$): 1. zapisz kontekst $Ctx$ i przyczynę na stos 2. wykonaj procedurę obsługi 3. wyłącz **wszystkie** przerwania 4. jeśli $Ctx.SR_{IM}=0$ i `NeedResched==1` to: `NeedResched=0`, przełącz zadanie (zmienia `CurTsk`!) i stos na `CurTsk.sp` 5. odtwórz kontekst <small>Procedura obsługi wyjątku/pułapki podobna, ale działa z włączonymi przerwaniami.</small> --- ### Włączanie wywłaszczania Przenalizujmy scenariusz: 1. wyłączamy wywłaszczanie (`NoSwitch=1`) 2. następuje przerwanie zegara systemowego, skończył się kwant czasu `NeedResched=1`, ale przerwanie nie wymienia kontekstu 3. włączamy wywłaszczanie (`NoSwitch=0`) 4. zadanie wykonuje kod dalej (**ŹLE!**) Zadanie w takim przypadku musi zrzec się procesora w punkcie 3. --- ### Zakończenie zadania **Obserwacja:** Nie można usunąć stosu zadania, które przebywa na procesorze. Zmiana stanu na `Dead` i zmiana kontekstu nie wystarcza, żeby usunąć zadanie. Wyciek pamięci! Zadanie musi dodać się do `zombieq` zanim po raz ostatni wywoła zmianę kontekstu. Ktoś inny będzie musiał zwolnić zasoby! --- ### Czy pułapki mogą się zagnieżdżać? 1. `trap:user` &rarr; `trap:kern`? **TAK** `write` &rarr; `sys_write` (`trap:user`), jądro powoduje usterkę strony (`trap:kern`) 2. `trap:*` &rarr; `intr:kern`? **TAK** jądro jest wywłaszczalne, zatem w trakcie obsługi pułapek pozwalamy na przerwania 3. `intr:*` &rarr; `trap:kern`? **NIE** bo procedura obsługi przerwania nie ma własnego kontekstu i nie może iść spać <small>Po dwukropku podano bit `TrapFrame.sr` kontekstu, który został odłożony na stos jądra.</small> ## Pytania ?