Iga \u00fclesande t\u00f6\u00f6aeg on teada.<\/li>\n<\/ol>\nPlaneerija m\u00f5\u00f5dikud<\/h3>\n \n M\u00f5ningate koormushinnangute k\u00f5rval on vajalik ka erinevate planeerimispoliitikate v\u00f5rdlemiseks mingisugune t\u00f6\u00f6riist: planeerijate metoodika. Metoodika on lihtsalt mingi m\u00f5\u00f5tmisviis millelegi. On olemas mitmeid metoodikaid, mida saab kasutada planeerijate v\u00f5rdlemiseks.<\/p>\n
N\u00e4itena kasutame metoodikat, mida nimetatakse t\u00e4itmisajaks<\/b> (turnaround time). \u00dclesande t\u00e4itmise aeg m\u00e4\u00e4ratletakse kui erinevus \u00fclesande valmimise ja \u00fclesande s\u00fcsteemi saabumise aja vahel.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Kuna oletame, et k\u00f5ik \u00fclesanded saabusid \u00fchel ja samal ajal, siis Ta=0 ning seega Tt=Tc. See v\u00e4\u00e4rtus muutub loomulikult, kui muudame \u00fclaltoodud oletusi.<\/p>\n
Teine metoodika on fairness<\/b> (\u00f5iglus). Tootlikkus ja \u00f5iglus on planeerimises sageli vastandlikud omadused. N\u00e4iteks v\u00f5ib planeerija optimeerida tootlikkust, kuid teiste \u00fclesannete k\u00e4ivitamise ooteaja arvelt, mist\u00f5ttu kannatab \u00f5iglus.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n K\u00f5ige lihtsam algoritm, mida saame kasutada, nimetatakse FIFO-ks v\u00f5i kes tuleb (sisse), see l\u00e4heb (v\u00e4lja) esimesena<\/b>. Sellel algoritmil on mitmeid eeliseid: see on v\u00e4ga lihtne rakendada ja sobib k\u00f5igi meie eelduste alla, tehes t\u00f6\u00f6d \u00fcsna h\u00e4sti.<\/p>\n
Vaadakem lihtsat n\u00e4idet. Oletame, et 3 \u00fclesannet esitati samaaegselt. Kuid oletame, et \u00fclesanne A tuli veidi varem kui k\u00f5ik teised, seega on see teostamisnimekirjas esikohal, t\u00e4pselt nagu B on suhte V. Oletame, et iga\u00fche t\u00e4itmine kestab 10 sekundit. Mis siis on nende \u00fclesannete keskmine t\u00e4itmise aeg?<\/p>\n
Kuid selgub, et erinevad \u00fclesannete t\u00e4itmise ajad m\u00f5jutavad FIFO algoritmi t\u00f6\u00f6viljakust \u00e4\u00e4rmiselt negatiivselt. Oletame, et \u00fclesanne A kestab 100 sekundit, samas kui B ja V j\u00e4\u00e4vad m\u00f5lemad 10 sekundi pikkuseks.<\/p>\n
konvoiefektiks<\/b>, kus m\u00f5ned l\u00fchiajalised ressursikasutajad seisavad pikaajalise kasutaja j\u00e4rel. See on nagu j\u00e4rjekord poe kassas, kus teie ees on klient t\u00e4is ostuk\u00e4ru. Parim lahendus probleemile on proovida vahetada kassat v\u00f5i lihtsalt rahuneda ja s\u00fcgavalt hingata.<\/p>\nL\u00fchim t\u00f6\u00f6 k\u00f5igepealt<\/h3>\n
\n Kas on v\u00f5imalik lahendada sarnane olukord raskete protsessidega? Muidugi. Teine planeerimise t\u00fc\u00fcp onL\u00fchim t\u00f6\u00f6 k\u00f5igepealt<\/b> (SJF). Selle algoritm on samuti piisavalt primitiivne \u2014 nagu nimigi \u00fctleb, k\u00e4ivituvad esimesena k\u00f5ige l\u00fchemad \u00fclesanded \u00fcksteise j\u00e4rel.<\/p>\n
50 asemel 110<\/b>, mis on praktiliselt 2 korda parem.<\/p>\n
Seega, antud juhul, et k\u00f5ik \u00fclesanded saabuvad \u00fchel ja samal ajal, tundub SJF algoritm k\u00f5ige optimaalsemana. Siiski ei tundu meie eeldused endiselt realistlikud. Seekord muudame eeldust 2 ning kujutame ette, et \u00fclesanded saavad saabuda igal ajal, mitte k\u00f5ik korraga. Millistele probleemidele see v\u00f5ib viia?<\/p>\n
L\u00fchim t\u00e4itmisaeg esimesena (STCF)<\/h3>\n \n Et olukorda parandada, loobume eeldusest 3, et programm k\u00e4ivitub ja t\u00f6\u00f6tab l\u00f5puni. Samuti on meil vaja riistvara tuge ja nagu v\u00f5isite arvata, kasutame me taimerit<\/b> t\u00f6\u00f6s oleva \u00fclesande katkestamiseks ja konteksti vahetamiseks.<\/b>. Nii saab ajakava teha midagi \u00fclesannete B ja V saabumise hetkest \u2013 l\u00f5petada \u00fclesande A t\u00e4itmine ja tegeleda \u00fclesannetega B ja V ning p\u00e4rast nende l\u00f5petamist j\u00e4tkata \u00fclesande A t\u00e4itmist. Sellist ajakava nimetatakse STCF<\/b>v\u00f5i Eelnev \u00dclesanne Esiteks<\/b>.<\/p>\n
M\u00f5\u00f5dik Vastusaeg (Response Time)<\/h3>\n \n Seega, kui me teame \u00fclesannete t\u00f6\u00f6aega ja et need \u00fclesanded kasutavad ainult CPU-d, on STCF parim lahendus. Kunagi ammu t\u00f6\u00f6tasid need algoritmid v\u00e4ga h\u00e4sti. Kuid n\u00fc\u00fcd veedab kasutaja enamiku ajast terminalis ja ootab sellelt tootlikku interaktiivset suhtlemist. Nii s\u00fcndis uus m\u00f5\u00f5dik \u2013 vastusaeg<\/b> (reaktsioon).<\/p>\n
Vastusaeg arvestatakse j\u00e4rgmiselt:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Seega, eelmise n\u00e4ite puhul on vastusaeg: A=0, B=0, V=10 (abg=3,33).<\/p>\n
Ja selgub, et STCF algoritm pole sugugi nii hea olukorras, kus 3 \u00fclesannet saabuvad samal ajal \u2014 see peab ootama, kuni v\u00e4iksed \u00fclesanded on t\u00e4ielikult l\u00f5petatud. Seega on algoritm hea ringlusaega m\u00f5\u00f5tva metrika jaoks, kuid halb interaktiivsuse m\u00f5\u00f5tmiseks. Kujutage ette, et istute terminali taga ja proovite redigeerijas s\u00fcmboleid tr\u00fckkida, kuid peate ootama \u00fcle 10 sekundi, sest m\u00f5ni teine \u00fclesanne kasutab protsessorit. See pole just meeldiv.<\/p>\n
Ringkonnaga<\/h3>\n \n Selle probleemi lahendamiseks t\u00f6\u00f6tati v\u00e4lja algoritm Ringkonnaga<\/b> (RR). Peamine idee on \u00fcsna lihtne: selle asemel, et k\u00e4ivitada \u00fclesandeid t\u00e4ies mahus, k\u00e4ivitame \u00fclesande teatud ajavahemikuks (nimetatakse ajakvandiks) ja seej\u00e4rel l\u00fclitume j\u00e4rjekorrast j\u00e4rgmisele \u00fclesandele. Algoritm kordab oma t\u00f6\u00f6d, kuni k\u00f5ik \u00fclesanded on l\u00f5pule viidud. Samal ajal peab programmi t\u00f6\u00f6tamise aeg olema jagatav ajaga, mil kell peatab protsessi. N\u00e4iteks, kui kell peatab protsessi iga x=10 ms j\u00e4rel, peab protsessi t\u00e4itmise akna suurus olema jagatav 10 ja olema 10, 20 v\u00f5i x*10.<\/p>\n
Vaatame n\u00e4idet: \u00dclesanded A, B ja C saabuvad s\u00fcsteemi samaaegselt ning iga\u00fcks neist soovib t\u00f6\u00f6tada 5 sekundit. Algoritm SJF t\u00e4idab iga \u00fclesande l\u00f5puni, enne kui l\u00fclitub teise. Vastupidiselt algoritmile RR, mille k\u00e4ivitamise aken on 1 s, l\u00e4bib see \u00fclesandeid j\u00e4rgmisel viisil (joonis 4.3):<\/p>\n
Algoritmi RR keskmine vastuse aeg (0+1+2)\/3=1, samas kui SJF jaoks (0+5+10)\/3=5.<\/p>\n
On loogiliselt eeldada, et ajakenk on RR jaoks v\u00e4ga oluline parameeter; mida l\u00fchem see on, seda k\u00f5rgem on vastusaeg. Kuid seda ei tohi ka liiga v\u00e4ikseks teha, kuna konteksti vahetamise aeg m\u00f5jutab samuti \u00fcldist sooritust. Seega, akna t\u00e4itmise aeg valitakse OS arhitekti poolt ning see s\u00f5ltub \u00fclesannetest, mida seal plaanitakse t\u00e4ita. Konteksti vahetamine ei ole ainus teenindusoperatsioon, mis aega kulutab \u2014 k\u00e4ivitatud programm tegeleb paljude muude aspektidega, n\u00e4iteks erinevate vahem\u00e4ludega, ja iga vahetuse korral tuleb see keskkond talletada ja taastada, mis v\u00f5ib samuti aega v\u00f5tta.<\/p>\n
RR on suurep\u00e4rane planeerija, kui r\u00e4\u00e4kida ainult vastusaega m\u00f5\u00f5tvast metrikast. Kuid kuidas k\u00e4itub \u00fclesande k\u00e4ibe aeg selle algoritmi juures? Vaadakem \u00fclaltoodud n\u00e4idet, kus A, B, C t\u00f6\u00f6tavad 5 sekundit ja saabuvad samal ajal. \u00dclesanne A l\u00f5petab 13. sekundil, B 14. ja C 15. sekundil, mis annab keskmiseks k\u00e4ibe ajaks 14 sekundit. Seega on RR k\u00f5ige kehvem algoritm k\u00e4ibe m\u00f5\u00f5tmise jaoks.<\/p>\n
\u00dcldiselt \u00f6eldes on iga RR t\u00fc\u00fcpi algoritm aus, jaotades CPU t\u00f6\u00f6aja v\u00f5rdselt k\u00f5igi protsesside vahel. Seet\u00f5ttu j\u00e4\u00e4vad need m\u00f5\u00f5dikud pidevalt konfliktiks.<\/p>\n
Seega on meil mitu vastandlikku algoritmi ja samas on veel mitmeid eeldusi \u2014 et \u00fclesande t\u00f6\u00f6aeg on teada ja et \u00fclesanne kasutab ainult CPU-d.<\/p>\n
Segamine I\/O-ga<\/h3>\n \n Esiteks eemaldame eelduse 4, et protsess kasutab ainult CPU-d, mis pole t\u00f5si, kuna protsessid v\u00f5ivad p\u00f6\u00f6rduda ka teiste seadmete poole.<\/p>\n
Hetkel, kui m\u00f5ni protsess taotleb sisendi- ja v\u00e4ljundioperatsiooni, l\u00e4heb protsess blokeeritud olekusse, oodates I\/O l\u00f5petamist. Kui I\/O suunatakse k\u00f5vakettale, v\u00f5ib see operatsioon kesta isegi mitu ms v\u00f5i kauem, ja sel ajal on CPU ootel. Sel perioodil saab planeerija CPU-d kasutada m\u00f5ne muu protsessi jaoks. J\u00e4rgmine otsus, mille planeerija peab tegema, on see, millal protsess l\u00f5petab oma I\/O. Kui see juhtub, toimub katkestus ja operatsioonis\u00fcsteem viib I\/O k\u00e4ivitanud protsessi valmis olekusse.<\/p>\n
Vaatame n\u00e4idet mitmest \u00fclesandest. Iga\u00fchel neist on vaja 50 ms protsessoriaega. Kuid esimene p\u00f6\u00f6rdub iga 10 ms j\u00e4rel I\/O poole (mis toimub samuti 10 ms). Protsess B kasutab lihtsalt 50 ms protsessorit ilma I\/O-ta.<\/p>\n
Oraakel on kadunud<\/h3>\n \n Proovime n\u00fc\u00fcd vabaneda eeldusest, et \u00fclesande t\u00f6\u00f6tamise aeg on teada. See on \u00fcldiselt halvim ja ebareaalne eeldus kogu nimekirjas. Tegelikult teab keskmine tavap\u00e4rane operatsioonis\u00fcsteem tavaliselt v\u00e4ga v\u00e4he \u00fclesannete t\u00e4itmise ajast, kuidas siis ehitada ajastust ilma teadmata, kui kaua \u00fclesanne kestab? Kas me v\u00f5iksime kasutada m\u00f5ningaid RR-p\u00f5him\u00f5tteid selle probleemiga tegelemiseks?<\/p>\n
Kokkuv\u00f5te<\/h3>\n \n Oleme uurinud \u00fclesannete ajastamise p\u00f5hiteooriaid ja vaadanud kahte planeerijate peret. Esimene k\u00e4ivitab k\u00f5ige l\u00fchema \u00fclesande esimesena, suurendades seel\u00e4bi p\u00f6\u00f6rdeaega, teine aga jaotab koormuse k\u00f5igi \u00fclesannete vahel v\u00f5rdselt, parandades reageerimisaega. M\u00f5lemad algoritmid on halvad seal, kus on head teise pereliigi algoritmid. Samuti oleme k\u00e4sitlenud, kuidas CPU ja I\/O paralleelne kasutamine v\u00f5ib t\u00f5sta tootlikkust, kuid ei ole lahendanud operatsioonis\u00fcsteemi selgeltn\u00e4gemise probleemi. J\u00e4rgmises tunnis vaatame planeerijat, mis vaatab l\u00e4hiajalukku ja proovib tulevikku ette ennustada. See kannab nime mitme taseme tagasiside j\u00e4rjekord.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