Wprowadzenie do systemów operacyjnych
Hej Habra! Pragnę zwrócić Państwa uwagę na cykl artykułów-przekładów jednej ciekawej moim zdaniem literatury - OSTEP. Ten materiał dość szczegółowo omawia działanie uniksowych systemów operacyjnych, a mianowicie pracę z procesami, różnymi programami planującymi, pamięcią i innymi podobnymi komponentami, które składają się na nowoczesny system operacyjny. Oryginał wszystkich materiałów można zobaczyć tutaj . Zaznaczam, że tłumaczenie zostało wykonane nieprofesjonalnie (dość swobodnie), ale mam nadzieję, że zachowałem ogólny sens.
Pracę laboratoryjną na ten temat można znaleźć tutaj:
Inne części:
Możesz również sprawdzić mój kanał na =)
Planowanie: wielopoziomowa kolejka opinii
W tym wykładzie omówimy problemy opracowania jednego z najbardziej znanych podejść do
planowanie, tzw Wielopoziomowa kolejka opinii (MLFQ). Harmonogram MLFQ został po raz pierwszy opisany w 1962 roku przez Fernando J. Corbató w systemie zwanym
Zgodny system podziału czasu (CTSS). Prace te (w tym późniejsze prace nad
Multics) zostały następnie nominowane do Nagrody Turinga. Planista był
później ulepszony i uzyskał wygląd, który można już znaleźć
niektóre nowoczesne systemy.
Algorytm MLFQ próbuje rozwiązać 2 podstawowe nakładające się problemy.
Po pierwsze, stara się zoptymalizować czas realizacji, który, jak omawialiśmy w poprzednim wykładzie, optymalizowany jest metodą rozpoczynania od początku kolejki najbardziej
krótkie zadania. Jednak system operacyjny nie wie, jak długo będzie działać dany proces, i to
wiedza niezbędna do obsługi algorytmów SJF, STCF. Po drugie, MLFQ próbuje
sprawić, aby system był responsywny dla użytkowników (na przykład dla tych, którzy siedzą i
wpatrywanie się w ekran w oczekiwaniu na wykonanie zadania) i w ten sposób minimalizowanie czasu
odpowiedź. Niestety algorytmy takie jak RR poprawiają czas reakcji, ale niezwykle
mają zły wpływ na wskaźnik czasu realizacji. Stąd nasz problem: Jak projektować
harmonogram, który spełni nasze wymagania, nie mając o tym zielonego pojęcia
ogólnie charakter procesu? W jaki sposób planista może poznać charakterystykę zadań,
które uruchamia i tym samym podejmować lepsze decyzje planistyczne?
Istota problemu: Jak zaplanować wyznaczanie zadań bez doskonałej wiedzy?
Jak zaprojektować harmonogram, który jednocześnie minimalizuje czas odpowiedzi
do zadań interaktywnych i jednocześnie minimalizuje czas realizacji bez wiedzy
znajomość czasu wykonania zadania?
Uwaga: uczymy się z poprzednich wydarzeń
Kolejka MLFQ jest doskonałym przykładem systemu, z którego się uczy
wydarzenia z przeszłości, aby przewidzieć przyszłość. Podobne podejścia są często
znaleźć w systemie operacyjnym (i wielu innych gałęziach informatyki, w tym gałęziach
przewidywania sprzętowe i algorytmy buforowania). Podobne wycieczki
są wyzwalane, gdy zadania mają fazy behawioralne i dlatego są przewidywalne.
Należy jednak zachować ostrożność przy tej technice, ponieważ przewidywania są bardzo łatwe
może okazać się błędny i skłonić system do podjęcia gorszych decyzji niż
byłby w ogóle pozbawiony wiedzy.
MLFQ: Podstawowe zasady
Przyjrzyjmy się podstawowym zasadom algorytmu MLFQ. I chociaż implementacje tego algorytmu
Jest ich kilka, podstawowe podejścia są podobne.
W implementacji, którą będziemy się przyglądać, MLFQ będzie miało kilka
oddzielne kolejki, z których każda będzie miała inny priorytet. W każdej chwili,
zadanie gotowe do wykonania znajduje się w jednej kolejce. MLFQ wykorzystuje priorytety,
zdecydować, które zadanie uruchomić do wykonania, tj. zadanie z wyższym
priorytet (zadanie z kolejki o najwyższym priorytecie) zostanie uruchomione jako pierwsze
kolejka.
Oczywiście w danej kolejce może znajdować się więcej niż jedno zadanie, tzw
więc będą mieli ten sam priorytet. W takim przypadku zastosowany zostanie mechanizm
RR, aby zaplanować przebieg pomiędzy tymi zadaniami.
W ten sposób dochodzimy do dwóch podstawowych zasad MLFQ:
- Zasada 1: Jeśli priorytet(A) > Priorytet(B), uruchomione zostanie zadanie A (B nie)
- Zasada 2: Jeśli priorytet (A) = Priorytet (B), A i B są uruchamiane przy użyciu RR
Na podstawie powyższego kluczowe elementy planowania MLFQ
są priorytety. Zamiast nadawać każdemu ustalony priorytet
zadania, MLFQ zmienia swój priorytet w zależności od zaobserwowanego zachowania.
Na przykład, jeśli zadanie stale obciąża procesor podczas oczekiwania na wejście z klawiatury,
MLFQ utrzyma wysoki priorytet procesu, ponieważ tak właśnie jest
powinien zadziałać proces interaktywny. Jeśli wręcz przeciwnie, zadanie jest stale i
zużywa procesor intensywnie przez długi czas, MLFQ obniży go
priorytet. Zatem MLFQ będzie badać zachowanie procesów podczas ich działania
i używać zachowań.
Narysujmy przykład, jak mogą wyglądać kolejki w pewnym momencie
czas i wtedy dostajesz coś takiego:
W tym schemacie 2 procesy A i B znajdują się w kolejce o najwyższym priorytecie. Proces
C jest gdzieś pośrodku, a proces D jest na samym końcu kolejki. Zgodnie z powyższym
Zgodnie z opisami algorytmu MLFQ, harmonogram będzie wykonywał zadania tylko z najwyższymi
priorytet według RR, a zadania C, D będą bez pracy.
Oczywiście statyczna migawka nie daje pełnego obrazu działania MLFQ.
Ważne jest, aby dokładnie zrozumieć, jak obraz zmienia się w czasie.
Próba 1: Jak zmienić priorytet
W tym momencie musisz zdecydować, w jaki sposób MLFQ zmieni poziom priorytetu
zadań (a tym samym pozycji zadania w kolejce) w trakcie jego cyklu życia. Dla
jest to konieczne, aby pamiętać o przepływie pracy: pewna ilość
interaktywne zadania z krótkim czasem wykonania (a co za tym idzie częstym wydawaniem
CPU) i kilka długotrwałych zadań, które wykorzystują procesor przez cały czas pracy, podczas gdy
Przy tego typu zadaniach czas reakcji nie jest istotny. W ten sposób możesz podjąć pierwszą próbę
zaimplementuj algorytm MLFQ z następującymi regułami:
- Zasada 3: Kiedy zadanie trafia do systemu, jest umieszczane w kolejce z najwyższym wynikiem
- priorytet.
- Zasada 4a: Jeśli zadanie wykorzystuje całe przydzielone mu okno czasowe, to tak jest
- priorytet jest obniżony.
- Reguła 4b: Jeśli zadanie zwalnia procesor przed wygaśnięciem okna czasowego, to tak
- pozostaje z tym samym priorytetem.
Przykład 1: Pojedyncze, długotrwałe zadanie
Jak widać na tym przykładzie zadanie wstępu jest ustawione na najwyższą wartość
priorytet. Po upływie okna czasowego wynoszącego 10 ms priorytet procesu zostaje obniżony
planista. Po kolejnym oknie czasowym zadanie zostaje ostatecznie zdegradowane do
najniższy priorytet w systemie, gdzie pozostaje.
Przykład 2: Dostarczono krótkie zadanie
Zobaczmy teraz przykład tego, jak MLFQ będzie próbowało zbliżyć się do SJF. W tym
na przykład dwa zadania: A, które jest zadaniem długotrwałym i ciągłym
zajmując procesor i B, co jest krótkim zadaniem interaktywnym. Przypuszczać
że A pracował już przez jakiś czas, zanim przyszło zadanie B.
Ten wykres pokazuje wyniki scenariusza. Zadanie A, jak każde zadanie,
Użycie procesora było na samym dole. Zadanie B dotrze w czasie T=100 i tak się stanie
umieszczone w kolejce o najwyższym priorytecie. Ponieważ jego czas działania jest krótki
zakończy się przed dotarciem do ostatniej kolejki.
Z tego przykładu należy zrozumieć główny cel algorytmu: ponieważ algorytm tego nie robi
wie, czy zadanie jest długie czy krótkie, to przede wszystkim zakłada, że jest to zadanie
krótki i nadaje mu najwyższy priorytet. Jeśli to naprawdę krótkie zadanie, to tak
zostanie ukończone szybko, w przeciwnym razie, jeśli jest to długie zadanie, będzie przebiegać powoli
priorytet w dół i wkrótce udowodni, że rzeczywiście jest to długie zadanie, które tego nie robi
wymaga odpowiedzi.
Przykład 3: A co z we/wy?
Spójrzmy teraz na przykład wejścia/wyjścia. Jak stwierdzono w zasadzie 4b,
jeśli proces zwalnia procesor bez wykorzystania całego jego czasu,
wówczas pozostaje na tym samym poziomie priorytetu. Intencja tej reguły jest dość prosta
- jeśli zadanie interaktywne wykonuje wiele operacji we/wy, na przykład czeka
od naciśnięcia klawisza użytkownika lub myszy, takie zadanie zwolni procesor
przed wyznaczonym oknem. Nie chcielibyśmy obniżać priorytetu takiego zadania,
i tym samym pozostanie na tym samym poziomie.
Ten przykład pokazuje, jak algorytm będzie działał z takimi procesami - zadanie interaktywne B, które potrzebuje procesora tylko przez 1 ms przed wykonaniem
Proces wejścia/wyjścia i długotrwałe zadanie A, które cały czas wykorzystuje procesor.
MLFQ utrzymuje proces B na najwyższym priorytecie, ponieważ trwa
zwolnij procesor. Jeśli B jest zadaniem interaktywnym, algorytm osiągnął
Twoim celem jest szybkie wykonywanie zadań interaktywnych.
Problemy z obecnym algorytmem MLFQ
W poprzednich przykładach zbudowaliśmy podstawową wersję MLFQ. I wygląda na to, że on
wykonuje swoją pracę dobrze i uczciwie, sprawiedliwie dzieląc czas procesora pomiędzy sobą
długich zadań i umożliwienie zadań krótkich lub wymagających dużej objętości
szybko pracuj nad wejściami/wyjściami. Niestety, to podejście zawiera kilka
poważne problemy.
Po pierwsze, problem głodu: jeśli system ma wiele interaktywnych
zadania, to pochłoną one cały czas procesora, a więc ani jednego przez długi czas
zadanie nie będzie możliwe do wykonania (umierają z głodu).
Po drugieinteligentni użytkownicy mogliby w ten sposób pisać swoje programy
oszukać planistę. Oszustwo polega na robieniu czegoś na siłę
Harmonogram zapewnia procesowi więcej czasu procesora. Algorytm to
opisany powyżej jest dość podatny na podobne ataki: przed upływem okna jest praktycznie
zakończył się, musisz wykonać operację we/wy (w przypadku niektórych, niezależnie od pliku)
i w ten sposób zwolnij procesor. Takie zachowanie pozwoli ci pozostać w tym samym
samą kolejkę i ponownie uzyskać większy procent czasu procesora. Jeśli zrobisz
to prawda (na przykład wykonaj 99% czasu okna przed zwolnieniem procesora),
takie zadanie może po prostu zmonopolizować procesor.
Wreszcie program może zmieniać swoje zachowanie w czasie. Te zadania
które korzystały z procesora, mogą stać się interaktywne. W naszym przykładzie podobnie
zadania nie będą traktowane przez planistę tak, jak na to zasługują, tak jak inni
(wstępne) zadania interaktywne.
Pytanie do widzów: jakie ataki na planistę można przeprowadzić we współczesnym świecie?
Próba 2: Zwiększanie priorytetu
Spróbujmy zmienić zasady i zobaczmy, czy uda nam się uniknąć problemów
post. Co możemy zrobić, aby zapewnić powiązanie
Zadania procesora dostaną swój czas (nawet jeśli nie będą długie).
Jako proste rozwiązanie problemu możesz sugerować okresowo
podnieść priorytet wszystkich tego typu zadań w systemie. Jest wiele sposobów
Aby to osiągnąć, spróbujmy na przykład zaimplementować coś prostego: tłumacz
wszystkie zadania otrzymują od razu najwyższy priorytet, stąd nowa zasada:
- Rule5: Po pewnym czasie S przenieś wszystkie zadania w systemie do najwyższej kolejki.
Nasza nowa zasada rozwiązuje dwa problemy na raz. Po pierwsze, procesy
gwarantujemy, że nie umrą z głodu: zadania o najwyższym priorytecie zostaną podzielone
Czas procesora zgodnie z algorytmem RR i tym samym otrzymają wszystkie procesy
Czas procesora. Po drugie, jeśli jakiś proces był wcześniej używany
dopiero procesor stanie się interaktywny, pozostanie w kolejce z najwyższym
priorytet po otrzymaniu jednorazowego podwyższenia priorytetu do najwyższego.
Spójrzmy na przykład. W tym scenariuszu rozważmy użycie jednego procesu
Procesor i dwa interaktywne, krótkie procesy. Po lewej stronie rysunku pokazano zachowanie bez promocji priorytetowej, w związku z czym długotrwałe zadanie zaczyna głodować po przybyciu do systemu dwóch interaktywnych zadań. Na rysunku po prawej stronie zwiększanie priorytetu odbywa się co 50 ms, co gwarantuje, że wszystkie procesy otrzymają czas procesora i będą okresowo uruchamiane. W tym przypadku jako przykład podano 50 ms, w rzeczywistości liczba ta jest nieco wyższa.
Oczywiście, dodając okresowy czas wzrostu S, do czego prowadzi
logiczne pytanie: jaką wartość ustawić? Jeden z wyróżnionych
inżynierowie systemów John Ousterhout nazywali takie wielkości w systemach voo-doo
stałe, ponieważ w jakiś sposób wymagały czarnej magii do poprawnego działania
wystawianie. I niestety S ma taki zapach. Jeśli ustawisz również wartość
duże - długie zadania zaczną głodować. A jeśli ustawisz zbyt niską wartość,
Zadania interaktywne nie otrzymają odpowiedniego czasu procesora.
Próba 3: Lepsza księgowość
Teraz mamy kolejny problem do rozwiązania: jak tego nie robić
pozwolić, aby nasz program planujący dał się oszukać? Winni tej możliwości są ludzie
reguły 4a, 4b, które pozwalają zadaniu zachować priorytet, uwalniając procesor
przed upływem wyznaczonego czasu. Jak sobie z tym poradzić?
Rozwiązanie w tym przypadku można uznać za lepsze rozliczanie czasu procesora na każdym
Poziom MLFQ. Zamiast zapominać, ile czasu program używał
procesora przez wyznaczony okres, należy to uwzględnić i zapisać. Po
proces wyczerpał przydzielony mu czas, należy go zdegradować do następnego
priorytetowy poziom. Teraz nie ma znaczenia, jak proces wykorzysta swój czas – w jaki sposób
ciągłe przetwarzanie na procesorze lub jako liczba połączeń. Zatem,
zasadę 4 należy przepisać do następującej postaci:
- Rule4: Gdy zadanie wykorzysta przydzielony mu czas w bieżącej kolejce (niezależnie od tego, ile razy zwolniło procesor), priorytet tego zadania zostaje obniżony (przechodzi w dół kolejki).
Spójrzmy na przykład:
»
Rysunek pokazuje, co się stanie, jeśli spróbujesz oszukać program planujący, np
gdyby było przy poprzednich zasadach 4a, 4b otrzymalibyśmy wynik po lewej stronie. Szczęśliwy nowy
regułą jest wynik po prawej stronie. Przed zabezpieczeniem każdy proces mógł wywoływać operacje we/wy przed zakończeniem i
w ten sposób zdominują procesor po włączeniu ochrony, niezależnie od zachowania
I/O, nadal będzie przesuwał się w dół w kolejce i tym samym nie będzie mógł tego zrobić nieuczciwie
przejąć zasoby procesora.
Poprawa MLFQ i innych problemów
Wraz z powyższymi ulepszeniami pojawiają się nowe problemy: jeden z głównych
Pytania - jak sparametryzować taki harmonogram? Te. Ile powinno być
kolejki? Jaka powinna być wielkość okna programu w kolejce? Jak
Często należy zwiększać priorytet programu, aby uniknąć głodu i
uwzględnić zmianę w zachowaniu programu? Na te pytania nie ma prostej odpowiedzi
odpowiedź i tylko eksperymenty z obciążeniami i późniejszą konfiguracją
planisty może prowadzić do zadowalającej równowagi.
Na przykład większość implementacji MLFQ umożliwia przypisanie różnych
odstępy czasowe dla różnych kolejek. Zwykle kolejki o wysokim priorytecie
zalecane są krótkie przerwy. Kolejki te składają się z zadań interaktywnych,
przełączanie między nimi jest dość wrażliwe i powinno zająć 10 lub mniej
SM. Natomiast kolejki o niskim priorytecie składają się z długotrwałych zadań, które wykorzystują
PROCESOR. I w tym przypadku bardzo dobrze sprawdzają się długie interwały czasowe (100ms).
W tym przykładzie są 2 zadania, które działały w kolejce 20 o wysokim priorytecie
ms, podzielone na okna 10 ms. 40 ms w środkowej kolejce (okno 20 ms) i przy niskim priorytecie
Okno czasu kolejki wynosiło 40 ms, gdy zadania zakończyły swoją pracę.
Implementacja MLFQ w systemie operacyjnym Solaris to klasa programów planujących współdzielenie czasu.
Planista dostarczy zestaw tabel, które definiują dokładnie tak, jak powinny
priorytet procesu zmienia się w trakcie jego życia, jaka powinna być jego wielkość
przydzielone okno i jak często trzeba podnosić priorytety zadań. Administrator
systemy mogą wchodzić w interakcję z tą tabelą i powodować zachowanie programu planującego
różnie. Domyślnie ta tabela ma 60 kolejek ze stopniowym wzrostem
rozmiar okna od 20 ms (wysoki priorytet) do kilkuset ms (niski priorytet) oraz
również ze zwiększeniem wszystkich zadań raz na sekundę.
Inni planiści MLFQ nie używają tabeli ani żadnych konkretów
reguły opisane w tym wykładzie, wręcz przeciwnie, obliczają priorytety za pomocą
wzory matematyczne. Na przykład program planujący FreeBSD używa formuły dla
obliczyć aktualny priorytet zadania na podstawie długości procesu
używany procesor. Ponadto zużycie procesora maleje z biegiem czasu i tak dalej
Zatem zwiększanie priorytetu przebiega nieco inaczej niż opisano powyżej. To prawda
zwane algorytmami rozpadu. Od wersji 7.1 FreeBSD korzysta z harmonogramu ULE.
Wreszcie wiele programów planujących ma inne funkcje. Na przykład niektórzy
planiści rezerwują najwyższe poziomy dla działania systemu operacyjnego i tym samym
Zatem żaden proces użytkownika nie może otrzymać najwyższego priorytetu w
system. Niektóre systemy umożliwiają udzielanie porad w celu pomocy
planista potrafi prawidłowo ustawić priorytety. Na przykład za pomocą polecenia miło
możesz zwiększyć lub zmniejszyć priorytet zadania, a tym samym zwiększyć lub
zmniejszyć ryzyko wykorzystania czasu procesora przez program.
MLFQ: Podsumowanie
Opisaliśmy podejście do planowania zwane MLFQ. Jego imię
ujęta w zasadę działania - posiada kilka kolejek i korzysta ze sprzężenia zwrotnego
w celu ustalenia priorytetu zadania.
Ostateczna forma zasad będzie następująca:
- Rule1: Jeśli priorytet(A) > Priorytet(B), zostanie uruchomione zadanie A (B nie)
- Rule2: Jeśli priorytet (A) = Priorytet (B), A i B są uruchamiane przy użyciu RR
- Rule3: Kiedy zadanie trafia do systemu, jest umieszczane w kolejce o najwyższym priorytecie.
- Rule4: Gdy zadanie wykorzysta przydzielony mu czas w bieżącej kolejce (niezależnie od tego, ile razy zwolniło procesor), priorytet tego zadania zostaje obniżony (przechodzi w dół kolejki).
- Rule5: Po pewnym czasie S przenieś wszystkie zadania w systemie do najwyższej kolejki.
MLFQ jest interesujące z następującego powodu – zamiast wymagać wiedzy nt
charakter zadania z wyprzedzeniem, algorytm bada przeszłe zachowanie zadania i ustala
odpowiednio priorytety. Próbuje zatem siedzieć na dwóch krzesłach na raz – aby osiągnąć produktywność przy małych zadaniach (SJF, STCF) i szczerze biegać długo,
Zadania obciążające procesor. Dlatego wiele systemów, w tym BSD i jego pochodne,
Solaris, Windows, Mac używają jakiejś formy algorytmu jako harmonogramu
MLFQ jako punkt odniesienia.
Dodatkowe materiały:
- (informatyka)
Źródło: www.habr.com