Tidspunktet for hver opgaves udf\u00f8relse er kendt.<\/li>\n<\/ol>\nScheduler-metrikker<\/h3>\n \n Udover nogle antagelser om belastningen er der ogs\u00e5 brug for et v\u00e6rkt\u00f8j til at sammenligne forskellige scheduling-politikker: scheduler-metrikker. En metrik er bare et m\u00e5l for noget. Der findes et antal metrikker, der kan bruges til at sammenligne schedulere.<\/p>\n
Som eksempel vil vi bruge en metrik, der hedder omvendelsestid<\/b> (turnaround time). Omvendelsestiden for en opgave defineres som forskellen mellem afslutningstidspunktet for opgaven og tidspunktet for, hvorn\u00e5r opgaven kom ind i systemet.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Da vi antog, at alle opgaver ankom p\u00e5 \u00e9n gang, er Ta=0 og dermed Tt=Tc. Dette v\u00e6rdien vil naturligvis \u00e6ndre sig, n\u00e5r vi \u00e6ndrer ovenst\u00e5ende antagelser.<\/p>\n
En anden metrik \u2014 fairness<\/b> (retf\u00e6rdighed, \u00e6rlighed). Ydeevne og retf\u00e6rdighed er ofte modstridende egenskaber i planl\u00e6gning. For eksempel kan en planl\u00e6gger optimere ydeevnen, men p\u00e5 bekostning af ventetid for andre opgaver, hvilket reducerer retf\u00e6rdigheden.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n Den mest grundl\u00e6ggende algoritme, vi kan implementere, kaldes FIFO eller first come (in), first served (out)<\/b>. Denne algoritme har flere fordele: den er meget enkel at implementere, og den lever op til alle vores antagelser, hvilket resulterer i en god ydeevne.<\/p>\n
Lad os se p\u00e5 et simpelt eksempel. Antag, at 3 opgaver blev indsendt samtidig. Men lad os antage, at opgave A kom lidt f\u00f8r de andre, s\u00e5 den vil st\u00e5 \u00f8verst p\u00e5 udf\u00f8relseslisten, ligesom B i forhold til V. Antag, at hver af dem vil blive udf\u00f8rt i 10 sekunder. Hvad vil gennemsnitstiden for disse opgaver v\u00e6re?<\/p>\n
Som det viser sig, har forskellige udf\u00f8relsestider for opgaverne en meget negativ indvirkning p\u00e5 produktiviteten af FIFO-algoritmen. Antag, at opgave A vil k\u00f8re i 100 sekunder, mens B og V fortsat k\u00f8rer i 10 sekunder hver.<\/p>\n
konvoieffekten<\/b>, hvor nogle kortvarige forbrugere af en ressource skal st\u00e5 i k\u00f8 bag en tung forbruger. Det ligner en k\u00f8 i supermarkedet, n\u00e5r der er en kunde foran dig med en fyldt vogn. Den bedste l\u00f8sning p\u00e5 problemet er at pr\u00f8ve at skifte kasse eller tage det roligt og tr\u00e6kke vejret dybt.<\/p>\nShortest Job First<\/h3>\n
\n Er der en m\u00e5de at l\u00f8se en s\u00e5dan situation med tunge processer? Selvf\u00f8lgelig. En anden type planl\u00e6gning kaldesShortest Job First<\/b> (SJF). Dets algoritme er ogs\u00e5 ret primitivt - som navnet antyder, vil de korteste opgaver blive k\u00f8rt f\u00f8rst, \u00e9n ad gangen.<\/p>\n
50 i stedet for 110<\/b>, hvilket er praktisk talt dobbelt s\u00e5 godt.<\/p>\n
Derfor, under den givne antagelse om, at alle opgaver ankommer p\u00e5 samme tid, virker SJF-algoritmen som den mest optimale algoritme. Men vores antagelser synes stadig ikke realistiske. Denne gang vil vi \u00e6ndre antagelse 2 og forestille os, at opgaverne kan ankomme n\u00e5r som helst, ikke alle samtidig. Hvilke problemer kan dette f\u00f8re til?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n For at forbedre situationen vil vi droppe antagelse 3 om, at programmet k\u00f8rer og fungerer til det er f\u00e6rdigt. Derudover har vi brug for hardwareunderst\u00f8ttelse, og som du m\u00e5ske har g\u00e6ttet, vil vi bruge en timer<\/b> til at afbryde den k\u00f8rende opgave og skifte kontekster<\/b>. S\u00e5ledes kan planl\u00e6ggeren tage skridt, n\u00e5r opgaverne B, C kommer ind - stoppe udf\u00f8relsen af opgave A og s\u00e6tte opgaverne B og C i behandling, og efter deres afslutning forts\u00e6tte med at k\u00f8re proces A. S\u00e5dan en planl\u00e6gger kaldes STCF<\/b>eller Preemptive Job First<\/b>.<\/p>\n
Metrik Reaktionstid (Response Time)<\/h3>\n \n Derfor, hvis vi kender tiden for opgavernes arbejde og ved, at disse opgaver kun bruger CPU, vil STCF v\u00e6re den bedste l\u00f8sning. Og engang i de tidlige dage fungerede disse algoritmer ganske godt. Men nu bruger brugeren det meste af tiden foran terminalen og forventer et produktivt interaktivt samspil. S\u00e5ledes blev den nye metrik - respons tid<\/b> (reaktionstid) f\u00f8dt.<\/p>\n
Reaktionstid beregnes som f\u00f8lgende:<\/p>\n
Tresponse = Tfirstrun \u2212 Tarrival<\/u><\/p>\n
S\u00e5ledes vil responstiden for det tidligere eksempel v\u00e6re: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Det viser sig, at STCF-algoritmen ikke er s\u00e5 god i situationer, hvor 3 opgaver ankommer samtidig \u2014 den skal vente, indtil de sm\u00e5 opgaver er helt afsluttet. P\u00e5 denne m\u00e5de er algoritmen god til m\u00e5ling af turnaround-tid, men d\u00e5rlig til interaktivitet. Forestil dig, at du, mens du sidder ved terminalen og fors\u00f8ger at indtaste tegn i editoren, skal vente mere end 10 sekunder, fordi en anden opgave optager processoren. Det er ikke s\u00e6rlig behageligt.<\/p>\n
Round Robin<\/h3>\n \n For at l\u00f8se dette problem blev der udviklet en algoritme Round Robin<\/b> (RR). Grundideen er ret enkel: I stedet for at k\u00f8re opgaverne til de er helt afsluttet, vil vi k\u00f8re en opgave i et bestemt tidsrum (kendt som et tidskvant), og derefter skifte til en anden opgave i k\u00f8en. Algoritmen gentager sit arbejde, indtil alle opgaver er afsluttet. Her skal programmet k\u00f8re i intervaller, der er et multiplum af den tid, hvor timeren vil forstyrre processen. For eksempel, hvis timeren underbryder processen hvert x=10 ms, s\u00e5 skal st\u00f8rrelsen af udf\u00f8relsesvinduet v\u00e6re et multiplum af 10 og v\u00e6re 10, 20 eller x*10.<\/p>\n
Lad os overveje et eksempel: Opgaverne ABC ankommer samtidig til systemet, og hver \u00f8nsker at arbejde i 5 sekunder. SJF-algoritmen vil fuldf\u00f8re hver opgave, inden den starter en anden. I mods\u00e6tning til det vil RR-algoritmen med et vindue p\u00e5 1 sekunde gennemg\u00e5 opgaverne p\u00e5 f\u00f8lgende m\u00e5de (se fig. 4.3):<\/p>\n
Den gennemsnitlige responstid for RR-algoritmen (0+1+2) \/ 3 = 1, mens det for SJF (0+5+10) \/ 3 = 5.<\/p>\n
Det er logisk at antage, at tidsvinduet er en meget vigtig parameter for RR; jo mindre det er, desto hurtigere er svartiden. Dog kan det ikke v\u00e6re for lille, da tiden til kontekstskift ogs\u00e5 spiller en rolle i den samlede ydeevne. Valget af udf\u00f8relsestidspunkt bestemmes derfor af OS-arkitekten og afh\u00e6nger af de opgaver, der planl\u00e6gges at blive udf\u00f8rt. Kontekstskift er ikke den eneste operation, der bruger tid \u2014 det k\u00f8rende program h\u00e5ndterer ogs\u00e5 mange andre aspekter, s\u00e5som forskellige caches, og ved hvert skift skal dette milj\u00f8 gemmes og gendannes, hvilket ogs\u00e5 kan kr\u00e6ve meget tid.<\/p>\n
RR er en fremragende planl\u00e6gger, hvis det kun handler om svartidsmetrik. Men hvordan vil opgavens genneml\u00f8bstid opf\u00f8re sig med denne algoritme? Lad os overveje eksemplet ovenfor, hvor A, B og C k\u00f8rer i 5 sekunder og ankommer p\u00e5 samme tid. Opgave A slutter kl. 13, B kl. 14 og C kl. 15, hvilket giver en gennemsnitlig genneml\u00f8bstid p\u00e5 14 sekunder. Dermed er RR den d\u00e5rligste algoritme for genneml\u00f8bsmetrikken.<\/p>\n
Med andre ord er enhver RR-agtig algoritme retf\u00e6rdig; den deler CPU-tiden ligeligt mellem alle processer. P\u00e5 den m\u00e5de er disse metrikker i konstant konflikt med hinanden.<\/p>\n
Derfor har vi flere modsatrettede algoritmer, og der er stadig nogle antagelser \u2014 om at opgavernes tid er kendt, og at opgaven kun bruger CPU.<\/p>\n
Blanding med I\/O<\/h3>\n \n For det f\u00f8rste fjerner vi antagelse 4, at processen kun bruger CPU, hvilket ikke er tilf\u00e6ldet, da processer ogs\u00e5 kan interagere med andet udstyr.<\/p>\n
N\u00e5r en proces anmoder om en input\/output-operation, skifter den til en blokeret tilstand, mens den venter p\u00e5, at I\/O skal afsluttes. Hvis I\/O sendes til harddisken, kan denne operation tage op til flere millisekunder eller l\u00e6ngere, og CPU\u2019en vil v\u00e6re inaktiv i mellemtiden. I denne tid kan planl\u00e6ggeren optage CPU\u2019en med en anden proces. Den n\u00e6ste beslutning planl\u00e6ggeren skal tr\u00e6ffe er, hvorn\u00e5r processen afslutter sin I\/O. N\u00e5r det sker, vil der v\u00e6re et afbrydelse, og OS vil \u00e6ndre den proces, der har anmodet om I\/O, til klar tilstand.<\/p>\n
Lad os se p\u00e5 et eksempel med flere opgaver. Hver enkelt kr\u00e6ver 50 ms processtid. Men den f\u00f8rste vil kalde I\/O hvert 10. ms (som ogs\u00e5 vil k\u00f8re hver 10. ms). Proces B bruger blot 50 ms proces uden I\/O.<\/p>\n
Oraklet er ikke l\u00e6ngere.<\/h3>\n \n Lad os nu fors\u00f8ge at slippe af med antagelsen om, at tidsforbruget for en opgave er kendt. Dette er generelt den v\u00e6rste og mest urealistiske antagelse p\u00e5 listen. Faktisk ved normale operativsystemer generelt meget lidt om, hvor lang tid opgaverne tager at udf\u00f8re. Hvordan kan vi s\u00e5 bygge en planl\u00e6gger uden at vide, hvor lang tid en opgave vil tage? M\u00e5ske kunne vi bruge nogle principper fra RR til at l\u00f8se dette problem?<\/p>\n
Resultat<\/h3>\n \n Vi har gennemg\u00e5et de grundl\u00e6ggende ideer om opgaveplanl\u00e6gning og set p\u00e5 to familier af planl\u00e6ggere. Den f\u00f8rste k\u00f8rer den korteste opgave f\u00f8rst og dermed \u00f8ger genneml\u00f8bstiden, mens den anden deler tiden ligeligt mellem alle opgaver og dermed forbedrer svartiden. Begge algoritmer er d\u00e5rlige, hvor den anden families algoritmer er gode. Vi har ogs\u00e5 set hvordan parallel brug af CPU og I\/O kan forbedre ydelsen, men har ikke l\u00f8st problemet med operativsystemets forudseenhed. I n\u00e6ste session vil vi se p\u00e5 en planl\u00e6gger, der ser i den n\u00e6rmeste fortid og fors\u00f8ger at forudsige fremtiden. Den kaldes 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