Czas dzia\u0142ania ka\u017cdego zadania jest znany.<\/li>\n<\/ol>\nMetryki planisty<\/h3>\n \n Opr\u00f3cz pewnych za\u0142o\u017ce\u0144 dotycz\u0105cych obci\u0105\u017cenia, konieczne jest tak\u017ce narz\u0119dzie do por\u00f3wnywania r\u00f3\u017cnych polityk planowania: metryki planisty. Metryka to po prostu pewna miara czego\u015b. Istnieje pewna liczba metryk, kt\u00f3re mo\u017cna wykorzysta\u0107 do por\u00f3wnania planist\u00f3w.<\/p>\n
Na przyk\u0142ad, zastosujemy metryk\u0119, kt\u00f3ra nazywa si\u0119 czas obrotu<\/b> (turnaround time). Czas obrotu zadania definiuje si\u0119 jako r\u00f3\u017cnic\u0119 mi\u0119dzy czasem zako\u0144czenia zadania a czasem przyj\u0119cia zadania do systemu.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Poniewa\u017c za\u0142o\u017cyli\u015bmy, \u017ce wszystkie zadania przyby\u0142y w tym samym czasie, to Ta=0, a wi\u0119c Tt=Tc. Ta warto\u015b\u0107 naturalnie zmieni si\u0119, gdy zmienimy powy\u017csze za\u0142o\u017cenia.<\/p>\n
Inna metryka to fairness<\/b> (sprawiedliwo\u015b\u0107, uczciwo\u015b\u0107). Wydajno\u015b\u0107 i uczciwo\u015b\u0107 cz\u0119sto s\u0105 przeciwnymi cechami w planowaniu. Na przyk\u0142ad, planista mo\u017ce optymalizowa\u0107 wydajno\u015b\u0107, ale kosztem oczekiwania na uruchomienie innych zada\u0144, co z kolei obni\u017ca uczciwo\u015b\u0107.<\/p>\nFIFO (Pierwsze wesz\u0142o, pierwsze wysz\u0142o)<\/h3>\n
\n Najbardziej podstawowy algorytm, kt\u00f3ry mo\u017cemy zaimplementowa\u0107, nazywa si\u0119 FIFO lub first come (in), first served (out)<\/b>. Algorytm ten ma kilka zalet: jest bardzo prosty do wdro\u017cenia i spe\u0142nia wszystkie nasze za\u0142o\u017cenia, wykonuj\u0105c prac\u0119 ca\u0142kiem dobrze.<\/p>\n
Rozwa\u017cmy prosty przyk\u0142ad. Za\u0142\u00f3\u017cmy, \u017ce 3 zadania zosta\u0142y zg\u0142oszone jednocze\u015bnie. Ale za\u0142\u00f3\u017cmy, \u017ce zadanie A wp\u0142yn\u0119\u0142o troch\u0119 przed innymi, wi\u0119c na li\u015bcie wykonania znajdzie si\u0119 wcze\u015bniej ni\u017c inne, podobnie jak B wzgl\u0119dem V. Za\u0142\u00f3\u017cmy, \u017ce ka\u017cde z nich b\u0119dzie trwa\u0142o 10 sekund. Jakie b\u0119dzie \u015brednie czas wykonania tych zada\u0144?<\/p>\n
Okazuje si\u0119, \u017ce r\u00f3\u017cne czasy wykonywania zada\u0144 maj\u0105 bardzo negatywny wp\u0142yw na wydajno\u015b\u0107 algorytmu FIFO. Za\u0142\u00f3\u017cmy, \u017ce zadanie A b\u0119dzie trwa\u0142o 100 sekund, podczas gdy B i V nadal b\u0119d\u0105 trwa\u0107 10 sekund ka\u017cde.<\/p>\n
efektem konwoju<\/b>, kiedy niekt\u00f3rzy kr\u00f3tko czasowi konsumenci jakiego\u015b zasobu czekaj\u0105 w kolejce za ci\u0119\u017ckim konsumentem. To przypomina kolejk\u0119 w sklepie spo\u017cywczym, gdy przed tob\u0105 stoi klient z pe\u0142nym w\u00f3zkiem. Najlepszym rozwi\u0105zaniem problemu jest spr\u00f3bowa\u0107 zmieni\u0107 kas\u0119 lub po prostu zrelaksowa\u0107 si\u0119 i g\u0142\u0119boko oddycha\u0107.<\/p>\nNajkr\u00f3tsze zadanie pierwsze<\/h3>\n
\n Czy mo\u017cna jako\u015b rozwi\u0105za\u0107 t\u0119 sytuacj\u0119 z ci\u0119\u017ckimi procesami? Oczywi\u015bcie. Inny typ planowania nazywa si\u0119Najkr\u00f3tsze zadanie pierwsze<\/b> (SJF). Jego algorytm jest r\u00f3wnie\u017c do\u015b\u0107 prymitywny \u2014 jak wskazuje nazwa, pierwsze b\u0119d\u0105 uruchamiane najkr\u00f3tsze zadania jedno po drugim.<\/p>\n
50 zamiast 110<\/b>, co praktycznie jest 2 razy lepsze.<\/p>\n
W zwi\u0105zku z tym, przy za\u0142o\u017ceniu, \u017ce wszystkie zadania przychodz\u0105 w tym samym czasie, algorytm SJF wydaje si\u0119 by\u0107 najbardziej optymalnym rozwi\u0105zaniem. Niemniej jednak nasze za\u0142o\u017cenia wci\u0105\u017c nie wydaj\u0105 si\u0119 realistyczne. Tym razem zmienimy za\u0142o\u017cenie 2 i przedstawimy, \u017ce zadania mog\u0105 przychodzi\u0107 w dowolnym momencie, a nie wszystkie jednocze\u015bnie. Jakie problemy mo\u017ce to spowodowa\u0107?<\/p>\n
Najkr\u00f3tszy czas do zako\u0144czenia (STCF)<\/h3>\n \n Aby poprawi\u0107 sytuacj\u0119, pomijamy za\u0142o\u017cenie 3, \u017ce program jest uruchomiony i dzia\u0142a do zako\u0144czenia. Ponadto b\u0119dziemy potrzebowa\u0107 wsparcia sprz\u0119towego i, jak mo\u017cecie si\u0119 domy\u015bli\u0107, u\u017cyjemy timera<\/b> do przerywania dzia\u0142aj\u0105cego zadania i prze\u0142\u0105czania kontekst\u00f3w<\/b>. W ten spos\u00f3b planer mo\u017ce podj\u0105\u0107 jakie\u015b dzia\u0142ania w momencie przyj\u015bcia zada\u0144 B, C \u2014 przerwa\u0107 realizacj\u0119 zadania A i zaj\u0105\u0107 si\u0119 zadaniami B i C, a po ich zako\u0144czeniu wznowi\u0107 realizacj\u0119 procesu A. Taki planer nazywa si\u0119 STCF<\/b>lub Preempcja zada\u0144<\/b>.<\/p>\n
Metryka czasu odpowiedzi (Response Time)<\/h3>\n \n W zwi\u0105zku z tym, je\u015bli znamy czas realizacji zada\u0144 i to, \u017ce te zadania korzystaj\u0105 tylko z CPU, STCF b\u0119dzie najlepszym rozwi\u0105zaniem. Kiedy\u015b te algorytmy dzia\u0142a\u0142y ca\u0142kiem nie\u017ale. Jednak obecnie u\u017cytkownik sp\u0119dza wi\u0119kszo\u015b\u0107 czasu przy terminalu i oczekuje wydajnej interakcji interaktywnej. Tak narodzi\u0142a si\u0119 nowa metryka \u2014 czas odpowiedzi<\/b> (reakcji).<\/p>\n
Czas odpowiedzi oblicza si\u0119 w nast\u0119puj\u0105cy spos\u00f3b:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Dla powy\u017cszego przyk\u0142adu czas odpowiedzi b\u0119dzie nast\u0119puj\u0105cy: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Okazuje si\u0119, \u017ce algorytm STCF nie sprawdza si\u0119 zbyt dobrze w sytuacji, gdy 3 zadania przybywaj\u0105 jednocze\u015bnie \u2014 musi czeka\u0107, a\u017c ma\u0142e zadania ca\u0142kowicie si\u0119 zako\u0144cz\u0105. Tak wi\u0119c, algorytm jest dobry pod wzgl\u0119dem metryki czasu obrotu, ale z\u0142y pod wzgl\u0119dem metryki interaktywno\u015bci. Wyobra\u017a sobie, \u017ce siedz\u0105c przy terminalu i pr\u00f3buj\u0105c wpisa\u0107 znaki w edytorze, musisz czeka\u0107 ponad 10 sekund, poniewa\u017c jakie\u015b inne zadanie zajmuje procesor. To nie jest przyjemne.<\/p>\n
Round Robin<\/h3>\n \n Aby rozwi\u0105za\u0107 ten problem, opracowano algorytm Round Robin<\/b> (RR). G\u0142\u00f3wna idea jest do\u015b\u0107 prosta: zamiast uruchamia\u0107 zadania do ca\u0142kowitego zako\u0144czenia, uruchamiamy zadanie na pewien czas (nazywany kwantem czasu) i nast\u0119pnie prze\u0142\u0105czamy si\u0119 na inne zadanie z kolejki. Algorytm powtarza to dzia\u0142anie, a\u017c wszystkie zadania zostan\u0105 zako\u0144czone. Przy tym czas dzia\u0142ania programu musi by\u0107 wielokrotno\u015bci\u0105 czasu, po kt\u00f3rym timer przerwie proces. Na przyk\u0142ad, je\u015bli timer przerywa proces co x=10ms, to rozmiar okna wykonania procesu powinien by\u0107 wielokrotno\u015bci\u0105 10, a tak\u017ce wynosi\u0107 10, 20 lub x*10.<\/p>\n
Rozwa\u017cmy przyk\u0142ad: Zagadnienia ABC przybywaj\u0105 jednocze\u015bnie do systemu i ka\u017cde z nich chce pracowa\u0107 przez 5 sekund. Algorytm SJF b\u0119dzie wykonywa\u0142 ka\u017cde zadanie do ko\u0144ca, zanim uruchomi inne. W przeciwie\u0144stwie do tego, algorytm RR z oknem uruchamiania = 1 s przechodzi przez zadania w nast\u0119puj\u0105cy spos\u00f3b (rys. 4.3):<\/p>\n
\u015aredni czas reakcji dla algorytmu RR (0+1+2)\/3=1, podczas gdy dla SJF (0+5+10)\/3=5.<\/p>\n
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 \u2014 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.<\/p>\n
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.<\/p>\n
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.<\/p>\n
Thus, we have several opposing algorithms and still several assumptions remain \u2014 that task time is known and that the task only uses the CPU.<\/p>\n
Mixing with I\/O<\/h3>\n \n 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.<\/p>\n
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.<\/p>\n
Rozwa\u017cmy przyk\u0142ad z kilkoma zadaniami. Ka\u017cde z nich wymaga 50 ms czasu procesora. Jednak pierwsze z nich co 10 ms b\u0119dzie korzysta\u0107 z I\/O (kt\u00f3re te\u017c b\u0119dzie wykonywane co 10 ms). Proces B po prostu wykorzystuje 50 ms procesora bez I\/O.<\/p>\n
Orakula ju\u017c nie ma<\/h3>\n \n Teraz spr\u00f3bujmy pozby\u0107 si\u0119 za\u0142o\u017cenia, \u017ce czas dzia\u0142ania zadania jest znany. To generalnie najgorsze i nierealne za\u0142o\u017cenie z ca\u0142ej listy. W rzeczywisto\u015bci w przeci\u0119tnych, zwyk\u0142ych systemach operacyjnych, sam system operacyjny zazwyczaj bardzo ma\u0142o wie o czasie wykonywania zada\u0144, jak wi\u0119c zbudowa\u0107 planer bez wiedzy o tym, ile czasu zadanie b\u0119dzie si\u0119 wykonywa\u0107? Mo\u017ce mogliby\u015bmy zastosowa\u0107 jakie\u015b zasady RR do rozwi\u0105zania tego problemu?<\/p>\n
Podsumowanie<\/h3>\n \n Om\u00f3wili\u015bmy podstawowe idee planowania zada\u0144 i przyjrzeli\u015bmy si\u0119 2 rodzinom planner\u00f3w. Pierwszy uruchamia najkr\u00f3tsze zadanie na pocz\u0105tku i w ten spos\u00f3b zwi\u0119ksza czas obrotu, drugi natomiast r\u00f3wnomiernie dzieli czas mi\u0119dzy wszystkie zadania, zwi\u0119kszaj\u0105c czas reakcji. Oba algorytmy s\u0105 s\u0142abe tam, gdzie silne s\u0105 algorytmy z innej rodziny. Om\u00f3wili\u015bmy r\u00f3wnie\u017c, jak r\u00f3wnoleg\u0142e wykorzystanie CPU i I\/O mo\u017ce poprawi\u0107 wydajno\u015b\u0107, ale nie rozwi\u0105zali\u015bmy problemu z przewidywaniem OS. Na kolejnym wyk\u0142adzie przyjrzymy si\u0119 planerowi, kt\u00f3ry spogl\u0105da w najbli\u017csz\u0105 przesz\u0142o\u015b\u0107 i stara si\u0119 przewidzie\u0107 przysz\u0142o\u015b\u0107, nazywa si\u0119 on multi-level feedback queue.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t