Wprowadzenie do systemów operacyjnych

Cześć, Habr! Chcę przedstawić Wam serię artykułów-przekładów jednej ciekawej literatury — OSTEP. W tym materiale omawiane są dość dogłębnie zasady działania systemów operacyjnych typu unix, a mianowicie — praca z procesami, różnymi planistami, pamięcią i innymi podobnymi komponentami, które składają się na nowoczesny system operacyjny. Oryginał wszystkich materiałów można zobaczyć tutaj tutaj. Proszę pamiętać, że tłumaczenie zostało wykonane w sposób nieprofesjonalny (dosyć luźno), ale mam nadzieję, że ogólny sens zachowałem.

Laboratoria dotyczące tego tematu można znaleźć tutaj:

Inne części:

Możecie również zajrzeć na mój kanał w telegramie =)

Planowanie: Kolejka z wielopoziomowym sprzężeniem zwrotnym

Na tym wykładzie omówimy wyzwania związane z rozwojem jednego z najbardziej znanych podejść do
planowania, które nazywa się Kolejka z wielopoziomowym sprzężeniem zwrotnym (MLFQ). Po raz pierwszy planista MLFQ został opisany w 1962 roku przez Fernando J. Corbató w systemie zwanym
Compatible Time-Sharing System (CTSS). Te prace (w tym późniejsze prace nad
Multics) zostały później zgłoszone do Nagrody Turinga. Planista został
później udoskonalony i przyjął formę, którą można spotkać w
niektórych współczesnych systemach.

Algorytm MLFQ próbuję rozwiązać 2 fundamentalne pokrywające się problemy.
Po pierwsze,, próbuje optymalizować czas obrotu, który, jak omówiliśmy w poprzednim wykładzie, jest optymalizowany metodą uruchamiania na początku kolejki najbardziej
krótkich zadań. Jednak system operacyjny nie wie, jak długo będzie trwał dany proces, a to
jest niezbędna wiedza do działania algorytmów SJF, STCF. Po drugie, MLFQ stara się
uczynić system responsywnym dla użytkowników (na przykład dla tych, którzy siedzą i
wpatrują się w ekran w oczekiwaniu na zakończenie zadania) i tym samym minimalizować czas
reakcji. Niestety, algorytmy takie jak RR zmniejszają czas reakcji, ale bardzo
źle wpływają na metrykę czasu obrotu. Stąd nasze pytanie: Jak zaprojektować
planista, który spełni nasze wymagania, nie mając jednocześnie żadnej wiedzy o
charakterze procesów, w ogóle? Jak planista może nauczyć się charakterystyki zadań,
które uruchamia, aby tym samym podejmować lepsze decyzje o planowaniu?

Sedno problemu: Jak planować zadania bez idealnej wiedzy?
Jak stworzyć planistę, który jednocześnie minimalizuje czas reakcji
dla interaktywnych zadań, nie mając przy tym informacji o
czasie wykonania zadania?

Notatka: uczymy się na podstawie wcześniejszych wydarzeń

Kolejka MLFQ jest doskonałym przykładem systemu, który uczy się na
przeszłych wydarzeniach, aby przewidzieć przyszłość. Podobne podejścia często
występują w systemach operacyjnych (i wielu innych dziedzinach informatyki, w tym w obszarach
przewidywań w hardware i algorytmach buforowania). Takie podejścia
działają, gdy zadania mają fazy zachowań i są tym samym przewidywalne.
Jednak przy tej technice należy zachować ostrożność, ponieważ prognozy mogą być bardzo łatwo
niewłaściwe i prowadzić system do podejmowania gorszych decyzji niż
gdyby nie było żadnej wiedzy.

MLFQ: Podstawowe zasady

Rozważmy podstawowe zasady algorytmu MLFQ. Chociaż istnieje kilka
realizacji tego algorytmu, podstawowe podejścia są podobne.
W realizacji, którą będziemy rozważać, MLFQ będzie miało kilka
oddzielnych kolejek, z których każda będzie miała inny priorytet. W każdej chwili
zadanie gotowe do wykonania znajduje się w jednej z kolejek. MLFQ używa priorytetów,
aby zdecydować, które zadanie uruchomić do wykonania, tzn. zadanie o wyższym
priorytecie (zadanie z kolejki o najwyższym priorytecie) zostanie uruchomione jako pierwsze.
Niewątpliwie w danej kolejce może znajdować się więcej niż jedno zadanie, w ten
sposób będą miały ten sam priorytet. W takim przypadku będzie stosowany mechanizm
RR do planowania uruchomienia wśród tych zadań.
W ten sposób dochodzimy do dwóch podstawowych zasad dla MLFQ:
Zasada 1: Jeśli priorytet(A) > Priorytet(B), zadanie A zostanie uruchomione (B nie).

Zasada 2: Jeśli priorytet(A) = Priorytet(B), A i B są uruchamiane z użyciem RR.
Na podstawie powyższego, kluczowymi elementami planowania MLFQ

są priorytety. Zamiast przypisywać stały priorytet każdemu
zadaniu, MLFQ zmienia jego priorytet w zależności od obserwowanego zachowania.
Na przykład, jeśli zadanie ciągle przerywa pracę CPU w oczekiwaniu na wejście z klawiatury,
MLFQ utrzyma priorytet procesu na wysokim poziomie, ponieważ w ten sposób
powinien działać interaktywny proces. Jeśli natomiast zadanie ciągle i
intensywnie wykorzystuje CPU przez długi czas, MLFQ obniży jego
priorytet. W ten sposób MLFQ będzie uczyć się zachowania procesów w trakcie ich pracy
i wykorzystywać te zachowania.
Narysujmy przykład, jak mogłyby wyglądać kolejki w pewnym momencie
czasu, a wtedy otrzymalibyśmy coś takiego:
W tym schemacie 2 procesy A i B znajdują się w kolejce o najwyższym priorytecie. Proces

C znajduje się gdzieś pośrodku, a proces D na końcu kolejki. Zgodnie z powyższymi
opisami algorytmu MLFQ, scheduler będzie wykonywał zadania tylko z najwyższym priorytetem.
zgodnie z opisami algorytmu MLFQ, scheduler będzie wykonywał zadania tylko z najwyższym priorytetem
priorytetem zgodnie z RR, a zadania C, D będą z boku.
Oczywiście statyczny zrzut nie odda pełnego obrazu tego, jak działa MLFQ.
Ważne jest zrozumienie, jak dokładnie zmienia się obraz z upływem czasu.

Próba 1: Jak zmieniać priorytet

W tym momencie należy zdecydować, jak MLFQ będzie zmieniać poziom priorytetu
zadań (a tym samym pozycji zadania w kolejce) w trakcie jego cyklu życia. Aby
to zrealizować, trzeba mieć na uwadze proces pracy: pewną liczbę
interaktywnych zadań z krótkim czasem pracy (a więc częste zwalnianie
CPU) i kilka długich zadań, które wykorzystują CPU przez cały czas pracy, przy tym
czas odpowiedzi dla takich zadań nie jest istotny. W ten sposób można podjąć pierwszą próbę
wdrożenia algorytmu MLFQ z następującymi zasadami:

Zasada 3: Gdy zadanie trafia do systemu, jest umieszczane w kolejce o najwyższym
priorytetem.
Zasada 4a: Jeśli zadanie wykorzysta całkowicie przydzielony mu czas, to jego
priorytet jest obniżany.
Zasada 4b: Jeśli zadanie zwolni CPU przed upływem swojego okna czasowego, to
zachowuje dotychczasowy priorytet.

Przykład 1: Pojedyncze długo wykonujące się zadanie

Jak widać w tym przykładzie, zadanie przy przyjęciu jest ustawiane z najwyższym
priorytetem. Po oknie czasowym 10 ms jego priorytet jest obniżany
przez planistę. Po następnym oknie czasowym zadanie ostatecznie obniża się do
najniższego priorytetu w systemie, gdzie pozostaje.

Przykład 2: Pojawiło się krótkie zadanie

Teraz przeanalizujmy przykład, w jaki sposób MLFQ spróbuje zbliżyć się do SJF. W tym
przykładzie występują dwa zadania: A, które jest długo pracującym zadaniem stale
zajmującym CPU oraz B, które jest krótkim zadaniem interaktywnym. Załóżmy,
że A pracowało już jakiś czas w momencie, gdy zadanie B zostało przyjęte.

Na tym wykresie można zobaczyć wyniki scenariusza. Zadanie A, jak każde inne zadanie,
korzystające z CPU, znalazło się na samym dole. Zadanie B przybędzie w czasie T=100 i
zostanie umieszczone w kolejce o najwyższym priorytecie. Ponieważ czas jego pracy jest krótki,
zakończy się zanim dotrze do ostatniej kolejki.

Z tego przykładu należy zrozumieć główny cel algorytmu: ponieważ algorytm nie
wie, czy zadanie jest długie, czy krótkie, zakłada na początku, że zadanie
krótkie i nadaje mu najwyższy priorytet. Jeśli to naprawdę krótkie zadanie, to
zostanie wykonane szybko, w przeciwnym razie, jeśli to długie zadanie, to będzie powoli postępować
w dół priorytetu i wkrótce udowodni, że jest to naprawdę długie zadanie, które nie
wymaga odpowiedzi.

Przykład 3: A co z wejściem i wyjściem?

Teraz przyjrzyjmy się przykładzie z wejściem i wyjściem. Jak twierdzono w regule 4b,
jeśli proces zwolni procesor, nie wykorzystując w pełni swojego czasu procesora,
to pozostaje na dotychczasowym poziomie priorytetu. Zamysł tej reguły jest dość prosty
— jeśli interaktywne zadanie wykonuje wiele operacji wejścia-wyjścia, na przykład czekając
na naciśnięcia klawiszy lub ruchy myszy, takie zadanie zwolni procesor
wcześniej niż przewidziano. Nie chcielibyśmy obniżać priorytetu takiego zadania,
dlatego pozostaje na dotychczasowym poziomie.

Ten przykład pokazuje, jak będzie działał algorytm z takimi procesami — interaktywne zadanie B, które potrzebuje CPU tylko na 1 ms przed wykonaniem
procesu wejścia-wyjścia i długie zadanie A, które przez cały czas używa CPU.
MLFQ utrzymuje proces B na najwyższym priorytecie, ponieważ cały czas kontynuuje
zwalnianie CPU. Jeśli B jest interaktywnym zadaniem, to algorytm w takim przypadku osiągnie
swój cel, uruchamiając interaktywne zadania szybko.

Problemy z aktualnym algorytmem MLFQ

W poprzednich przykładach zbudowaliśmy podstawową wersję MLFQ. I wydaje się, że
wykonuje swoją pracę dobrze i sprawiedliwie, rozdzielając czas procesora sprawiedliwie między
długimi zadaniami i pozwalając krótkim zadaniom lub zadaniom intensywnie korzystającym
z wejścia-wyjścia działać szybko. Niestety, takie podejście ma kilka
poważnych problemów.
Po pierwsze,, problem głodu: jeśli w systemie jest wiele interaktywnych
zadań, będą one wykorzystywać całe dostępne czas procesora, przez co żadne długie
zadanie nie dostanie szansy na wykonanie (głodują).

Po drugie, sprytni użytkownicy mogą pisać swoje programy w taki sposób, aby
oszukać planista. Oszustwo polega na tym, że zrobić coś, aby zmusić
planistę do przydzielania procesowi więcej czasu procesora. Algorytm, który
opisany powyżej jest całkowicie podatny na tego typu ataki: zanim czas prawie
się skończy, należy wykonać operację wejścia-wyjścia (na jakimkolwiek, nie ważne jakim pliku)
i w ten sposób uwolnić CPU. Takie zachowanie pozwoli pozostać w tej samej
kolejce i ponownie uzyskać większy procent czasu procesora. Jeśli zrobisz
to poprawnie (na przykład, działając przez 99% czasu okna przed zwolnieniem CPU),
taka zadanie może po prostu monopolizować procesor.

Na koniec, program może zmieniać swoje zachowanie w czasie. Te zadania,
które używały CPU, mogą stać się interaktywne. W naszym przykładzie takie
zadania nie otrzymają odpowiedniego traktowania od planisty, tak jak miałyby inne
(początkowe) zadania interaktywne.

Pytanie do sali: jakie ataki na planistę można przeprowadzać w nowoczesnym świecie?

Próba 2: Podniesienie priorytetu

Spróbujmy zmienić zasady i zobaczyć, czy uda się uniknąć problemów z
głodzeniem. Co możemy zrobić, aby zagwarantować, że zadania związane z
CPU otrzymają czas (nawet jeśli nie długi).
Jako proste rozwiązanie problemu można zaproponować okresowe
podnoszenie priorytetu wszystkich takich zadań w systemie. Istnieje wiele sposobów
osiągnięcia tego, spróbujmy wdrożyć jako przykład coś prostego: zmienić
wszystkie zadania na najwyższy priorytet, stąd nowe zasady:

Reguła 5: Po upływie pewnego okresu S przenieść wszystkie zadania w systemie do najwyższej kolejki.

Nasza nowa zasada rozwiązuje dwa problemy na raz. Po pierwsze, procesy
gwarantowanie braku głodzenia: zadania znajdujące się w najwyższej kolejce będą dzielić
czas procesora według algorytmu RR i w ten sposób wszystkie procesy otrzymają
czas procesora. Po drugie, jeśli jakiś proces, który wcześniej używał
tylko procesora, staje się interaktywny, to pozostanie w kolejce z wyższym
priorytetem po tym, jak raz otrzyma podwyższenie priorytetu do najwyższego.
Rozważmy przykład. W tym scenariuszu rozważmy jeden proces, który wykorzystuje

CPU i dwa interaktywne, krótkie procesy. Po lewej stronie na ilustracji widać zachowanie bez podnoszenia priorytetów, w wyniku czego długoterminowe zadanie zaczyna głodować po przybyciu do systemu dwóch interaktywnych zadań. Po prawej stronie na ilustracji priorytet jest podnoszony co 50 ms, dzięki czemu wszystkie procesy mają zapewniony czas procesora i będą okresowo uruchamiane. 50 ms zostało wybrane jako przykład, w rzeczywistości ta liczba jest nieco większa.
Oczywiście, dodanie czasu okresowego podnoszenia S prowadzi do
nieuchronnego pytania: jaka wartość powinna być ustalona? Jeden z uznawanych
inżynierów systemowych John Ousterhout nazywał podobne wartości w systemach voodoo
stałą, ponieważ w pewnym sensie wymagały one czarnej magii do prawidłowego
ustalenia. I, niestety, S ma taką aurę. Jeśli ustawić wartość zbyt
wysoką — długie zadania zaczną głodować. A jeśli ustawić zbyt niską wartość,
interaktywne zadania nie otrzymają odpowiedniego czasu procesora.

Próba 3: Lepsze rozliczenie

Teraz mamy jeszcze jeden problem do rozwiązania: jak nie
pozwolić oszukiwać naszemu planistowi? Winne okazują się
reguły 4a, 4b, które pozwalają zadaniom zachować priorytet, zwalniając procesor
do wygaśnięcia przydzielonego czasu. Jak sobie z tym poradzić?
Rozwiązaniem w tym przypadku może być lepsze rozliczenie czasu CPU na każdym
poziomie MLFQ. Zamiast zapominać czas, który program wykorzystał
procesor w danym przedziale czasowym, należy go uwzględniać i zapisywać. Po tym jak
proces wydał mu przydzielony czas, priorytet należy obniżyć do następnego
poziomu priorytetu. Teraz nie ma znaczenia, jak proces wykorzysta swój czas — czy
konstantnie oblicza na procesorze czy w postaci wielu wywołań. Tak więc,
regułę 4 należy przekształcić w następującą postać:

Reguła 4: Po tym, jak zadanie wykorzystało przydzielony mu czas w aktualnej kolejce (niezależnie od tego, ile razy zwalniało CPU), priorytet takiego zadania jest obniżany (przesuwa się w dół kolejki).

Przyjrzyjmy się przykładom:
»

Na ilustracji widać, co się dzieje, gdy próbujemy oszukać planistę, jak
gdyby zasady 4a, 4b były takie same jak wcześniej, wynik byłby po lewej stronie. Z nową
zasadą — wynik po prawej stronie. Przed włączeniem ochrony każdy proces mógłby wywołać I/O do zakończenia i
tak w ten sposób dominować na CPU, po włączeniu ochrony, niezależnie od zachowania
I/O, będzie on i tak spadał w kolejce w dół i w ten sposób nie będzie mógł nieuczciwie
zdobyć zasobów CPU.

Ulepszamy MLFQ i inne problemy

Z powyższymi usprawnieniami pojawiają się nowe problemy: jednym z głównych
pytań jest — jak parametryzować taki harmonogram? Tzn. Ile powinno być
kolejek? Jaki powinien być rozmiar okna roboczego programu w obrębie kolejki? Jak
często należy podnosić priorytet programu, aby uniknąć głodzenia i
uwzględnić zmianę zachowania programu? Na te pytania nie ma prostych
odpowiedzi i tylko eksperymenty z obciążeniami i późniejsze konfigurowanie
harmonogramu mogą prowadzić do pewnego zadowalającego balansu.

Na przykład większość implementacji MLFQ pozwala na przydzielanie różnych
okresów czasu różnym kolejk, Dla kolejek o wysokim priorytecie zwykle
przydzielane są krótkie interwały. Kolejki te składają się z zadań interaktywnych,
przełączanie między którymi jest dość wrażliwe i powinno zajmować 10 lub mniej
ms. W przeciwieństwie do tego kolejki o niskim priorytecie składają się z długich zadań, które używają
CPU. I w tym przypadku długie interwały czasowe pasują bardzo dobrze (100 ms).

W tym przykładzie są 2 zadania, które pracowały w wysokoprioritetowej kolejce przez 20
ms, podzielone na okna po 10 ms. 40 ms w średniej kolejce (okno 20 ms) a w niskopriorytetowej
kolejce czas okna wynosił 40 ms, gdzie zadania zakończyły swoją pracę.

Implementacja MLFQ w systemie operacyjnym Solaris — klasa harmonogramów, które dzielą czas.
Harmonogram zapewnia zestaw tabel, które dokładnie definiują, jak powinien
zmieniać się priorytet procesu w trakcie jego życia, jaki powinien być rozmiar
przydzielanego okna i jak często należy podnosić priorytety zadania. Administrator
systemu może wchodzić w interakcję z tą tabelą i zmuszać harmonogram do zachowania
inaczej. Domyślnie w tej tabeli znajduje się 60 kolejek z stopniowym zwiększeniem
rozmiaru okna z 20 ms (wysoki priorytet) do kilku setek ms (niski priorytet), a
także z boostem wszystkich zadań raz na sekundę.

Inne planery MLFQ nie używają tabeli ani konkretnych
reguł, które są opisane w tej wykładzie, przeciwnie, obliczają priorytety za pomocą
formuł matematycznych. Tak, na przykład planista w FreeBSD używa formuły do
obliczania bieżącego priorytetu zadania, opierając się na tym, ile proces
zużył CPU. Dodatkowo, użycie CPU z czasem podlega dekrecji, i w ten
sposób podwyższenie priorytetu odbywa się nieco inaczej, niż opisano powyżej. To tak
zwane algorytmy decay. Od wersji 7.1 w FreeBSD używa się planisty ULE.

W końcu, wiele planerów ma inne cechy. Na przykład niektóre
plany zarezerwują najwyższe poziomy dla pracy systemu operacyjnego, w ten
sposób żaden proces użytkownika nie może uzyskać najwyższego priorytetu w
systemie. Niektóre systemy pozwalają na udzielanie wskazówek, aby pomóc
planerowi prawidłowo ustawić priorytety. Na przykład, za pomocą polecenia miły
można zwiększać lub zmniejszać priorytet zadania, a tym samym podnosić lub
obniżać szanse programu na czas procesora.

MLFQ: Podsumowanie

Opisaliśmy podejście do planowania, które nazywa się MLFQ. Jego nazwa
wiąże się z zasadą działania — posiada kilka kolejek i wykorzystuje sprzężenie zwrotne
do określenia priorytetu zadania.
Ostateczny zestaw zasad będzie następujący:

Reguła 1: Jeśli priorytet(A) > Priorytet(B), włączone zostanie zadanie A (B nie będzie)
Reguła 2: Jeśli priorytet(A) = Priorytet(B), A i B są uruchamiane z użyciem RR
Reguła 3: Gdy zadanie trafia do systemu, jest umieszczane w kolejce o najwyższym priorytecie.
Reguła 4: Po tym, jak zadanie wykorzystało przydzielony mu czas w aktualnej kolejce (niezależnie od tego, ile razy zwalniało CPU), priorytet takiego zadania jest obniżany (przesuwa się w dół kolejki).
Reguła 5: Po upływie pewnego okresu S przenieść wszystkie zadania w systemie do najwyższej kolejki.

MLFQ jest interesujące z następującego powodu — zamiast wymagać znajomości
natury zadania z góry, algorytm uczy się z przeszłego zachowania zadania i ustawia
priorytety stosownie. W ten sposób stara się usiąść na dwóch krzesłach — osiągnąć
wydajność dla małych zadań (SJF, STCF) i sprawiedliwie uruchamiać długie,
obciążające CPU zadania. Dlatego wiele systemów, w tym BSD i ich pochodne,
Solaris, Windows, Mac używa jako planera pewnej formy algorytmu