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 . 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 =)
Wprowadzenie do planisty
Istota problemu: Jak opracować politykę planisty
Jak powinny być opracowywane podstawowe ramy polityk planisty? Jakie powinny być kluczowe założenia? Jakie metryki są ważne? Jakie podstawowe techniki były stosowane w wczesnych systemach obliczeniowych?
Założenia obciążenia roboczego
Zanim omówimy możliwe polityki, na początek dokonajmy kilku uproszczeń dotyczących procesów uruchamianych w systemie, które razem nazywane są obciążeniem roboczym. Określając obciążenie robocze jako kluczowy element budowania polityk, im więcej wiesz o obciążeniu, tym lepszą politykę będziesz w stanie opracować.
Załóżmy następujące rzeczy na temat procesów uruchamianych w systemie, czasami nazywanych jobs (zadaniami). Praktycznie wszystkie te założenia są nierealistyczne, ale są potrzebne do rozwijania myśli.
- Każde zadanie uruchamiane jest przez ten sam czas,
- Wszystkie zadania są uruchamiane równocześnie,
- Uruchomione zadanie działa do swojego zakończenia,
- Wszystkie zadania wykorzystują tylko CPU,
- Czas działania każdego zadania jest znany.
Metryki planisty
Oprócz pewnych założeń dotyczących obciążenia, konieczne jest także narzędzie do porównywania różnych polityk planowania: metryki planisty. Metryka to po prostu pewna miara czegoś. Istnieje pewna liczba metryk, które można wykorzystać do porównania planistów.
Na przykład, zastosujemy metrykę, która nazywa się czas obrotu (turnaround time). Czas obrotu zadania definiuje się jako różnicę między czasem zakończenia zadania a czasem przyjęcia zadania do systemu.
Tturnaround=Tcompletion−Tarrival
Ponieważ założyliśmy, że wszystkie zadania przybyły w tym samym czasie, to Ta=0, a więc Tt=Tc. Ta wartość naturalnie zmieni się, gdy zmienimy powyższe założenia.
Inna metryka to fairness (sprawiedliwość, uczciwość). Wydajność i uczciwość często są przeciwnymi cechami w planowaniu. Na przykład, planista może optymalizować wydajność, ale kosztem oczekiwania na uruchomienie innych zadań, co z kolei obniża uczciwość.
FIFO (Pierwsze weszło, pierwsze wyszło)
Najbardziej podstawowy algorytm, który możemy zaimplementować, nazywa się FIFO lub first come (in), first served (out). Algorytm ten ma kilka zalet: jest bardzo prosty do wdrożenia i spełnia wszystkie nasze założenia, wykonując pracę całkiem dobrze.
Rozważmy prosty przykład. Załóżmy, że 3 zadania zostały zgłoszone jednocześnie. Ale załóżmy, że zadanie A wpłynęło trochę przed innymi, więc na liście wykonania znajdzie się wcześniej niż inne, podobnie jak B względem V. Załóżmy, że każde z nich będzie trwało 10 sekund. Jakie będzie średnie czas wykonania tych zadań?
Obliczając wartości — 10+20+30 i dzieląc przez 3, otrzymamy średni czas wykonania programu równy 20 sekund.
Teraz spróbujemy zmienić nasze założenia. W szczególności założenie 1 i w ten sposób nie będziemy już zakładać, że każde zadanie trwa tyle samo czasu. Jak w takim razie sprawdzi się FIFO?
Okazuje się, że różne czasy wykonywania zadań mają bardzo negatywny wpływ na wydajność algorytmu FIFO. Załóżmy, że zadanie A będzie trwało 100 sekund, podczas gdy B i V nadal będą trwać 10 sekund każde.
Jak widać na rysunku, średni czas dla systemu wyniesie (100+110+120) / 3 = 110. Taki efekt nazywamy efektem konwoju, kiedy niektórzy krótko czasowi konsumenci jakiegoś zasobu czekają w kolejce za ciężkim konsumentem. To przypomina kolejkę w sklepie spożywczym, gdy przed tobą stoi klient z pełnym wózkiem. Najlepszym rozwiązaniem problemu jest spróbować zmienić kasę lub po prostu zrelaksować się i głęboko oddychać.
Najkrótsze zadanie pierwsze
Czy można jakoś rozwiązać tę sytuację z ciężkimi procesami? Oczywiście. Inny typ planowania nazywa sięNajkrótsze zadanie pierwsze (SJF). Jego algorytm jest również dość prymitywny — jak wskazuje nazwa, pierwsze będą uruchamiane najkrótsze zadania jedno po drugim.
W tym przykładzie wynikiem uruchomienia tych samych procesów będzie poprawa średniego czasu obrotu programów i będzie wynosić 50 zamiast 110, co praktycznie jest 2 razy lepsze.
W związku z tym, przy założeniu, że wszystkie zadania przychodzą w tym samym czasie, algorytm SJF wydaje się być najbardziej optymalnym rozwiązaniem. Niemniej jednak nasze założenia wciąż nie wydają się realistyczne. Tym razem zmienimy założenie 2 i przedstawimy, że zadania mogą przychodzić w dowolnym momencie, a nie wszystkie jednocześnie. Jakie problemy może to spowodować?
Załóżmy, że zadanie A (100s) przychodzi jako pierwsze i zaczyna być realizowane. W momencie t=10 przychodzą zadania B, C, z których każde zajmie 10 sekund. W związku z tym średni czas realizacji to (100+(110-10)+(120-10))/3 = 103. Co mógłby zrobić planer, aby poprawić sytuację?
Najkrótszy czas do zakończenia (STCF)
Aby poprawić sytuację, pomijamy założenie 3, że program jest uruchomiony i działa do zakończenia. Ponadto będziemy potrzebować wsparcia sprzętowego i, jak możecie się domyślić, użyjemy timera do przerywania działającego zadania i przełączania kontekstów. W ten sposób planer może podjąć jakieś działania w momencie przyjścia zadań B, C — przerwać realizację zadania A i zająć się zadaniami B i C, a po ich zakończeniu wznowić realizację procesu A. Taki planer nazywa się STCFlub Preempcja zadań.
Wynikiem działania tego planera będzie taki rezultat: ((120-0)+(20-10)+(30-10))/3=50. Tak więc ten planer staje się jeszcze bardziej optymalny dla naszych zadań.
Metryka czasu odpowiedzi (Response Time)
W związku z tym, jeśli znamy czas realizacji zadań i to, że te zadania korzystają tylko z CPU, STCF będzie najlepszym rozwiązaniem. Kiedyś te algorytmy działały całkiem nieźle. Jednak obecnie użytkownik spędza większość czasu przy terminalu i oczekuje wydajnej interakcji interaktywnej. Tak narodziła się nowa metryka — czas odpowiedzi (reakcji).
Czas odpowiedzi oblicza się w następujący sposób:
Tresponse=Tfirstrun−Tarrival
Dla powyższego przykładu czas odpowiedzi będzie następujący: A=0, B=0, C=10 (abg=3,33).
Okazuje się, że algorytm STCF nie sprawdza się zbyt dobrze w sytuacji, gdy 3 zadania przybywają jednocześnie — musi czekać, aż małe zadania całkowicie się zakończą. Tak więc, algorytm jest dobry pod względem metryki czasu obrotu, ale zły pod względem metryki interaktywności. Wyobraź sobie, że siedząc przy terminalu i próbując wpisać znaki w edytorze, musisz czekać ponad 10 sekund, ponieważ jakieś inne zadanie zajmuje procesor. To nie jest przyjemne.
W ten sposób napotykamy na inny problem — jak możemy zbudować planista, który byłby wrażliwy na czas reakcji?
Round Robin
Aby rozwiązać ten problem, opracowano algorytm Round Robin (RR). Główna idea jest dość prosta: zamiast uruchamiać zadania do całkowitego zakończenia, uruchamiamy zadanie na pewien czas (nazywany kwantem czasu) i następnie przełączamy się na inne zadanie z kolejki. Algorytm powtarza to działanie, aż wszystkie zadania zostaną zakończone. Przy tym czas działania programu musi być wielokrotnością czasu, po którym timer przerwie proces. Na przykład, jeśli timer przerywa proces co x=10ms, to rozmiar okna wykonania procesu powinien być wielokrotnością 10, a także wynosić 10, 20 lub x*10.
Rozważmy przykład: Zagadnienia ABC przybywają jednocześnie do systemu i każde z nich chce pracować przez 5 sekund. Algorytm SJF będzie wykonywał każde zadanie do końca, zanim uruchomi inne. W przeciwieństwie do tego, algorytm RR z oknem uruchamiania = 1 s przechodzi przez zadania w następujący sposób (rys. 4.3):
(SJF Ponownie (Zły dla Czasu Reakcji)
(Round Robin (Dobry dla Czasu Reakcji)
Średni czas reakcji dla algorytmu RR (0+1+2)/3=1, podczas gdy dla SJF (0+5+10)/3=5.
Logic suggests that the time window is a very important parameter for RR; the shorter it is, the higher the response time. However, it cannot be too small either, as the time for context switching will also play a role in overall performance. Thus, the choice of execution window time is set by the OS architect and depends on the tasks that are planned to be executed in it. Context switching is not the only service operation that consumes time — a running program interacts with various caches, and each switch requires saving and restoring this environment, which can also take a considerable amount of time.
RR is an excellent scheduler if we only consider response time metrics. But how will the task turnaround time metric behave with this algorithm? Let's consider the example above, where the run times for A, B, and C are each 5 seconds and they arrive at the same time. Task A will finish at 13 seconds, B at 14 seconds, and C at 15 seconds, resulting in an average turnaround time of 14 seconds. Therefore, RR is the worst algorithm for turnaround metrics.
In broader terms, any RR-type algorithm is fair; it divides CPU run time equally among all processes. Thus, these metrics are constantly in conflict with each other.
Thus, we have several opposing algorithms and still several assumptions remain — that task time is known and that the task only uses the CPU.
Mixing with I/O
First, let's remove assumption 4, that the process only uses CPU; this is naturally not the case, as processes can also interact with other hardware.
At the moment when any process requests an I/O operation, it transitions to a blocked state, waiting for the I/O to complete. If the I/O is sent to the hard drive, such an operation can take several milliseconds or longer, and the CPU will be idle during this time. Meanwhile, the scheduler can assign the CPU to any other process. The next decision the scheduler has to make is when the process will complete its I/O. When this occurs, an interrupt will take place, and the OS will move the process that initiated the I/O back to the ready state.
Rozważmy przykład z kilkoma zadaniami. Każde z nich wymaga 50 ms czasu procesora. Jednak pierwsze z nich co 10 ms będzie korzystać z I/O (które też będzie wykonywane co 10 ms). Proces B po prostu wykorzystuje 50 ms procesora bez I/O.
W tym przykładzie użyjemy planera STCF. Jak zachowa się planer, jeśli uruchomimy na nim proces A? Zareaguje w następujący sposób — najpierw całkowicie wykona proces A, a potem proces B.
Tradycyjne podejście do rozwiązania tego problemu polega na interpretacji każdej 10-ms podzadania procesu A jako odrębnego zadania. W ten sposób, przy uruchamianiu z algorytmem STJF, wybór między zadaniem 50-ms i zadaniem 10-ms jest oczywisty. Gdy podzadanie A zakończy się, uruchomiony zostanie proces B i I/O. Po zakończeniu I/O podjęta zostanie decyzja o ponownym uruchomieniu 10-ms procesu A zamiast procesu B. W ten sposób można zrealizować nakładanie się, gdy CPU jest wykorzystywane przez inny proces, podczas gdy pierwszy oczekuje na I/O. W efekcie system jest lepiej wykorzystywany — w momencie, gdy interaktywne procesy oczekują na I/O, na procesorze mogą być wykonywane inne procesy.
Orakula już nie ma
Teraz spróbujmy pozbyć się założenia, że czas działania zadania jest znany. To generalnie najgorsze i nierealne założenie z całej listy. W rzeczywistości w przeciętnych, zwykłych systemach operacyjnych, sam system operacyjny zazwyczaj bardzo mało wie o czasie wykonywania zadań, jak więc zbudować planer bez wiedzy o tym, ile czasu zadanie będzie się wykonywać? Może moglibyśmy zastosować jakieś zasady RR do rozwiązania tego problemu?
Podsumowanie
Omówiliśmy podstawowe idee planowania zadań i przyjrzeliśmy się 2 rodzinom plannerów. Pierwszy uruchamia najkrótsze zadanie na początku i w ten sposób zwiększa czas obrotu, drugi natomiast równomiernie dzieli czas między wszystkie zadania, zwiększając czas reakcji. Oba algorytmy są słabe tam, gdzie silne są algorytmy z innej rodziny. Omówiliśmy również, jak równoległe wykorzystanie CPU i I/O może poprawić wydajność, ale nie rozwiązaliśmy problemu z przewidywaniem OS. Na kolejnym wykładzie przyjrzymy się planerowi, który spogląda w najbliższą przeszłość i stara się przewidzieć przyszłość, nazywa się on multi-level feedback queue.
Źródło: habr.com
