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 =)
Wprowadzenie do harmonogramu
Istota problemu: Jak opracować politykę planisty
Jak należy zaprojektować podstawowe ramy polityki planisty? Jakie powinny być kluczowe założenia? Jakie wskaźniki są ważne? Jakie podstawowe techniki stosowano we wczesnych systemach komputerowych?
Założenia dotyczące obciążenia
Zanim omówimy możliwe polityki, zróbmy najpierw kilka upraszczających dygresji na temat procesów zachodzących w systemie, które zbiorczo nazywane są obciążenie pracą. Definiowanie obciążenia pracą jest kluczową częścią tworzenia zasad, a im więcej wiesz o obciążeniu pracą, tym lepszą politykę możesz napisać.
Przyjmijmy następujące założenia dotyczące procesów zachodzących w systemie, czasami tzw Oferty pracy (zadania). Prawie wszystkie z tych założeń nie są realistyczne, ale są niezbędne do rozwoju myślenia.
- Każde zadanie trwa tyle samo czasu,
- Wszystkie zadania są ustawione jednocześnie,
- Przydzielone zadanie działa aż do jego zakończenia,
- Wszystkie zadania korzystają wyłącznie z procesora,
- Czas realizacji każdego zadania jest znany.
Metryki harmonogramu
Oprócz pewnych założeń dotyczących obciążenia potrzebne jest inne narzędzie do porównywania różnych zasad planowania: metryki harmonogramu. Metryka to po prostu miara czegoś. Istnieje wiele metryk, które można wykorzystać do porównania harmonogramów.
Na przykład użyjemy metryki o nazwie czas realizacji (czas realizacji). Czas realizacji zadania definiowany jest jako różnica pomiędzy czasem wykonania zadania a czasem przybycia zadania do systemu.
Tturnaround=Tkoniec-Przybycie
Ponieważ założyliśmy, że wszystkie zadania dotarły w tym samym czasie, to Ta=0 i tym samym Tt=Tc. Wartość ta w naturalny sposób ulegnie zmianie, gdy zmienimy powyższe założenia.
Kolejna metryka – uczciwość (uczciwość, uczciwość). Produktywność i uczciwość są często przeciwstawnymi cechami w planowaniu. Na przykład osoba planująca może zoptymalizować wydajność, ale kosztem oczekiwania na wykonanie innych zadań, co zmniejsza uczciwość.
PIERWSZY NA PIERWSZYM NA PIERWSZYM WYJŚCIU (FIFO)
Najbardziej podstawowy algorytm, jaki możemy wdrożyć, nazywa się FIFO lub kto pierwszy przyszedł (wszedł), pierwszy lepszy (wyszedł). Algorytm ten ma kilka zalet: jest bardzo łatwy w implementacji, spełnia wszystkie nasze założenia i radzi sobie całkiem nieźle.
Spójrzmy na prosty przykład. Załóżmy, że ustawiono 3 zadania jednocześnie. Załóżmy jednak, że zadanie A przybyło nieco wcześniej niż wszystkie pozostałe, więc pojawi się na liście wykonań wcześniej niż pozostałe, podobnie jak B względem C. Załóżmy, że każde z nich będzie wykonywane przez 10 sekund. Jaki będzie średni czas wykonania tych zadań w tym przypadku?
Licząc wartości - 10+20+30 i dzieląc przez 3, otrzymujemy średni czas wykonania programu równy 20 sekund.
Spróbujmy teraz zmienić nasze założenia. W szczególności założenie 1 i dlatego nie będziemy już zakładać, że wykonanie każdego zadania zajmuje tyle samo czasu. Jak FIFO poradzi sobie tym razem?
Jak się okazuje, różne czasy realizacji zadań mają niezwykle negatywny wpływ na produktywność algorytmu FIFO. Załóżmy, że wykonanie zadania A zajmie 100 sekund, natomiast wykonanie zadania B i C zajmie po 10 sekund.
Jak widać na rysunku, średni czas dla systemu będzie wynosić (100+110+120)/3=110. Efekt ten nazywa się efekt konwoju, gdy niektórzy krótkoterminowi konsumenci zasobu ustawiają się w kolejce za dużym konsumentem. To jak kolejka w sklepie spożywczym, gdy przed tobą stoi klient z pełnym wózkiem. Najlepszym rozwiązaniem problemu jest próba zmiany kasy lub zrelaksowanie się i głębokie oddychanie.
Najpierw najkrótsza praca
Czy można w jakiś sposób rozwiązać podobną sytuację za pomocą procesów o dużej wadze? Z pewnością. Inny rodzaj planowania nazywa sięNajpierw najkrótsza praca (SJF). Jego algorytm jest również dość prymitywny – jak sama nazwa wskazuje, najpierw, jedno po drugim, będą uruchamiane najkrótsze zadania.
W tym przykładzie efektem prowadzenia tych samych procesów będzie wydłużenie średniego czasu realizacji programu i będzie ono równe 50 zamiast 110, czyli prawie 2 razy lepiej.
Zatem przy założeniu, że wszystkie zadania docierają w tym samym czasie, algorytm SJF wydaje się najbardziej optymalnym algorytmem. Jednak nasze założenia w dalszym ciągu nie wydają się realistyczne. Tym razem zmieniamy założenie 2 i tym razem wyobraźmy sobie, że zadania mogą występować w dowolnym momencie, a nie wszystkie w tym samym czasie. Do jakich problemów może to prowadzić?
Wyobraźmy sobie, że zadanie A (100c) pojawia się jako pierwsze i zaczyna być wykonywane. W t=10 pojawiają się zadania B i C, każde z nich zajmie 10 sekund. Zatem średni czas wykonania wynosi (100+(110-10)+(120-10))3 = 103. Co planista mógłby zrobić, aby to poprawić?
Najpierw najkrótszy czas do ukończenia (STCF)
Aby poprawić sytuację, pomijamy założenie 3, że program zostaje uruchomiony i będzie działał aż do zakończenia. Oprócz tego będziemy potrzebować wsparcia sprzętowego i jak można się domyślić, z niego skorzystamy timer aby przerwać trwające zadanie i przełączanie kontekstu. Zatem planista może coś zrobić w momencie nadejścia zadań B, C - przerwać wykonywanie zadania A i przekazać zadania B i C do przetwarzania, a po ich zakończeniu kontynuować wykonywanie procesu A. Taki harmonogram nazywa się STCFlub Najpierw praca wyprzedzająca.
Wynikiem tego planisty będzie następujący wynik: ((120-0)+(20-10)+(30-10))/3=50. Tym samym taki harmonogram staje się jeszcze bardziej optymalny dla naszych zadań.
Czas reakcji metryki
Zatem, jeśli znamy czas wykonywania zadań i że zadania te wykorzystują tylko procesor, najlepszym rozwiązaniem będzie STCF. W dawnych czasach algorytmy te działały całkiem dobrze. Jednak użytkownik spędza teraz większość czasu przy terminalu i oczekuje produktywnej interakcji. W ten sposób narodził się nowy miernik – czas odpowiedzi (odpowiedź).
Czas reakcji oblicza się w następujący sposób:
Tresponse=Tfirstrun-Przybycie
Zatem w poprzednim przykładzie czas odpowiedzi będzie wynosił: A=0, B=0, C=10 (abg=3,33).
I okazuje się, że algorytm STCF nie jest już tak dobry w sytuacji, gdy nadeszły 3 zadania w tym samym czasie - będzie musiał poczekać, aż małe zadania zostaną całkowicie wykonane. Zatem algorytm jest dobry w przypadku metryki czasu realizacji, ale zły w przypadku metryki interaktywności. Wyobraź sobie, że siedzisz przy terminalu i próbujesz wpisać znaki do edytora i musisz czekać ponad 10 sekund, ponieważ inne zadanie zajmuje procesor. To nie jest zbyt przyjemne.
Stoimy zatem przed kolejnym problemem – jak zbudować harmonogram wrażliwy na czas odpowiedzi?
Round Robin
Aby rozwiązać ten problem, opracowano algorytm Round Robin (RR). Podstawowa idea jest dość prosta: zamiast uruchamiać zadania do czasu ich zakończenia, uruchomimy zadanie przez określony czas (tzw. przedział czasu), a następnie przełączymy się do innego zadania z kolejki. Algorytm powtarza swoją pracę aż do wykonania wszystkich zadań. W takim przypadku 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, wówczas rozmiar okna wykonania procesu powinien być wielokrotnością 10 i wynosić 10,20 lub x*10.
Spójrzmy na przykład: zadania ABC przychodzą do systemu jednocześnie i każde z nich chce działać przez 5 sekund. Algorytm SJF zakończy każde zadanie przed rozpoczęciem kolejnego. Natomiast algorytm RR z oknem startowym = 1s będzie przechodził przez zadania w następujący sposób (rys. 4.3):
(Znowu SJF (zły czas reakcji)
(Round Robin (dobry ze względu na czas reakcji)
Średni czas odpowiedzi dla algorytmu RR wynosi (0+1+2)/3=1, natomiast dla algorytmu SJF (0+5+10)/3=5.
Logiczne jest założenie, że okno czasowe jest bardzo ważnym parametrem dla RR, im jest ono mniejsze, tym dłuższy jest czas odpowiedzi. Nie należy jednak czynić go zbyt małym, ponieważ czas przełączania kontekstu również będzie odgrywał rolę w ogólnej wydajności. Zatem wybór czasu okna wykonania jest ustalany przez architekta systemu operacyjnego i zależy od zadań, które mają zostać w nim wykonane. Przełączanie kontekstu nie jest jedyną operacją usługi, która marnuje czas - uruchomiony program działa na wielu innych rzeczach, na przykład na różnych pamięciach podręcznych i przy każdym przełączeniu konieczne jest zapisanie i przywrócenie tego środowiska, co również może zająć dużo czasu czas.
RR jest świetnym harmonogramem, jeśli mówimy tylko o metryce czasu odpowiedzi. Ale jak będzie się zachowywać metryka czasu realizacji zadania w przypadku tego algorytmu? Rozważmy powyższy przykład, gdy czas działania A, B, C = 5 s i docierają w tym samym czasie. Zadanie A zakończy się o 13, B o 14, C o 15, a średni czas realizacji wyniesie 14 s. Zatem RR jest najgorszym algorytmem dla metryki obrotu.
Mówiąc bardziej ogólnie, każdy algorytm typu RR jest sprawiedliwy; dzieli czas procesora równo pomiędzy wszystkie procesy. Dlatego te wskaźniki stale są ze sobą sprzeczne.
Mamy zatem kilka kontrastujących ze sobą algorytmów, a jednocześnie pozostało jeszcze kilka założeń – że czas zadania jest znany i że zadanie wykorzystuje tylko procesor.
Mieszanie z wejściami/wyjściami
Przede wszystkim usuńmy założenie 4, że proces wykorzystuje tylko procesor; oczywiście tak nie jest i procesy mogą uzyskać dostęp do innego sprzętu.
W momencie, gdy dowolny proces zażąda operacji we/wy, proces wchodzi w stan zablokowania i oczekuje na zakończenie operacji we/wy. Jeżeli I/O zostanie przesłane na dysk twardy, wówczas taka operacja może zająć nawet kilka ms lub dłużej, a procesor będzie w tym momencie bezczynny. W tym czasie program planujący może zająć procesor dowolnym innym procesem. Następną decyzją, jaką będzie musiał podjąć planista, będzie zakończenie operacji we/wy procesu. Gdy tak się stanie, nastąpi przerwanie i system operacyjny ustawi proces, który wywołał wejście/wyjście, w stan gotowości.
Spójrzmy na przykład kilku zadań. Każdy z nich wymaga 50 ms czasu procesora. Jednak pierwszy z nich będzie miał dostęp do wejść/wyjść co 10 ms (co będzie również wykonywane co 10 ms). Proces B po prostu wykorzystuje procesor 50 ms bez operacji we/wy.
W tym przykładzie użyjemy harmonogramu STCF. Jak zachowa się program planujący, jeśli zostanie uruchomiony na nim proces taki jak A? Wykona następujące czynności: najpierw całkowicie opracuje proces A, a następnie przetworzy proces B.
Tradycyjne podejście do rozwiązania tego problemu polega na traktowaniu każdego podzadania procesu A trwającego 10 ms jako osobnego zadania. Zatem zaczynając od algorytmu STJF, wybór pomiędzy zadaniem 50 ms a zadaniem 10 ms jest oczywisty. Następnie, gdy podzadanie A zostanie ukończone, uruchomiony zostanie proces B i wejście/wyjście. Po zakończeniu operacji we/wy zwyczajowo będzie ponownie uruchamiać proces A trwający 10 ms zamiast procesu B. W ten sposób możliwe jest zaimplementowanie nakładania się, w którym procesor jest używany przez inny proces, podczas gdy pierwszy czeka na We/Wy. Dzięki temu system jest lepiej wykorzystany – w momencie, gdy procesy interaktywne oczekują na wejście/wyjście, na procesorze mogą być wykonywane inne procesy.
Wyroczni już nie ma
Spróbujmy teraz pozbyć się założenia, że znany jest czas wykonania zadania. Jest to generalnie najgorsze i najbardziej nierealistyczne założenie na całej liście. Tak naprawdę w przeciętnym, zwykłym systemie operacyjnym sam system operacyjny zazwyczaj wie bardzo niewiele na temat czasu wykonania zadań, więc jak zatem zbudować harmonogram, nie wiedząc, ile czasu zajmie wykonanie zadania? Być może moglibyśmy zastosować pewne zasady RR, aby rozwiązać ten problem?
Łączny
Przyjrzeliśmy się podstawowym ideom planowania zadań i przyjrzeliśmy się dwóm rodzinom planistów. Pierwsza z nich rozpoczyna najpierw najkrótsze zadanie i tym samym wydłuża czas realizacji, natomiast druga jest rozdarta pomiędzy wszystkimi zadaniami po równo, zwiększając czas reakcji. Obydwa algorytmy są złe, podczas gdy algorytmy drugiej rodziny są dobre. Przyjrzeliśmy się także, jak równoległe użycie procesora i wejść/wyjść może poprawić wydajność, ale nie rozwiązaliśmy problemu dzięki jasnowidzenia systemu operacyjnego. Na następnej lekcji przyjrzymy się planiście, który spogląda w najbliższą przeszłość i próbuje przewidzieć przyszłość. Nazywa się to wielopoziomową kolejką informacji zwrotnej.
Źródło: www.habr.com