Iga \u00fclesande t\u00f6\u00f6aeg on teada.<\/li>\n<\/ol>\nAjastamise n\u00e4itajad<\/h3>\n \n Peale m\u00f5ningate t\u00f6\u00f6koormuse eelduste on vajalik ka mingi t\u00f6\u00f6riist erinevate ajastamispoliitikate v\u00f5rdlemiseks: ajastamise n\u00e4itajad. N\u00e4itaja on lihtsalt mingi m\u00f5\u00f5t mingi asja kohta. On olemas teatud kogus n\u00e4itajaid, mida saab kasutada ajastajate v\u00f5rdlemiseks.<\/p>\n
N\u00e4iteks kasutame n\u00e4itajat, mida nimetatakse t\u00e4itmise ajaks<\/b> (turnaround time). \u00dclesande t\u00e4itmise aeg m\u00e4\u00e4ratakse kui erinevus \u00fclesande l\u00f5petamise aja ja \u00fclesande s\u00fcsteemi sisenemise aja vahel.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Kuna me eeldasime, et k\u00f5ik \u00fclesanded sisenevad korraga, siis Ta=0 ja seega Tt=Tc. See v\u00e4\u00e4rtus muutub loomulikult, kui me muuda mainitud eeldusi.<\/p>\n
Teine n\u00e4itaja on \u00f5iglus<\/b> (\u00f5iglus, ausus). T\u00f5husus ja ausus on sageli vastandlikud omadused planeerimises. N\u00e4iteks v\u00f5ib planeerija optimeerida t\u00f5husust, kuid see toob kaasa teiste \u00fclesannete ooteaja, mis omakorda v\u00e4hendab ausust.<\/p>\nESIMENE SISSE, ESIMENE V\u00c4LJA (FIFO)<\/h3>\n
\n K\u00f5ige fundamentaalsem algoritm, mida me saame rakendada, nimetatakse FIFO-ks v\u00f5i first come (in), first served (out)<\/b>. Sellel algoritmil on mitmeid eeliseid: see on v\u00e4ga lihtne rakendada ja vastab k\u00f5igile meie eeldustele, t\u00e4ites t\u00f6\u00f6d \u00fcsna h\u00e4sti.<\/p>\n
Vaatame lihtsat n\u00e4idet. Oletame, et kolm \u00fclesannet on samal ajal esitatud. Kuid oletame, et \u00fclesanne A saabus veidi varem kui k\u00f5ik teised, seega on see t\u00e4itmise loendis enne teisi, samuti nagu B seoses V-ga. Oletame, et iga\u00fche t\u00e4itmiseks kulub 10 sekundit. Milline on sel juhul nende \u00fclesannete keskmine t\u00e4itmise aeg?<\/p>\n
Kuidas selgub, et erinevad t\u00e4itmise ajad m\u00f5jutavad FIFO algoritmi efektiivsust \u00e4\u00e4rmiselt negatiivselt. Oletame, et \u00fclesanne A t\u00e4itub 100 sekundit, samas kui B ja V j\u00e4\u00e4vad ikka 10 sekundile.<\/p>\n
konvoiefektiks<\/b>, kus m\u00f5ned l\u00fchiajalised ressursikasutajad seisavad j\u00e4rjekorras raskete kasutajate j\u00e4rel. See on sarnaselt j\u00e4rjekorraga toidupoes, kus teie ees on ostja, kellel on t\u00e4is ostuk\u00e4ru. Parim lahendus probleemile on proovida kassapidajat vahetada v\u00f5i lihtsalt rahuneda ja s\u00fcgavalt hingata.<\/p>\nL\u00fchim T\u00f6\u00f6 Esimene<\/h3>\n
\n Kas on v\u00f5imalik sellist olukorda raskete protsessidega kuidagi lahendada? Loomulikult. Teine t\u00fc\u00fcpi planeerimine on nimetatudL\u00fchim T\u00f6\u00f6 Esimene<\/b> (SJF). Selle algoritm on samuti piisavalt primitiivne \u2014 nagu nimest selgub, k\u00e4ivituvad k\u00f5igepealt k\u00f5ige l\u00fchemad \u00fclesanded \u00fcksteise j\u00e4rel.<\/p>\n
50 asemel 110<\/b>, mis on praktiliselt kaks korda parem.<\/p>\n
Seega, eeldades, et k\u00f5ik \u00fclesanded saabuvad samal ajal, tundub SJF algoritm olevat k\u00f5ige optimaalsem algoritm. Ent meie eeldused ei tundu siiski realistlikud. Seekord muudame eeldust 2 ja kujutame ette, et \u00fclesanded v\u00f5ivad saabuda igal ajal, mitte k\u00f5ik korraga. Millistele probleemidele see v\u00f5ib viia?<\/p>\n
L\u00fchim t\u00e4itmise kestus esimesena (STCF)<\/h3>\n \n Olukorra parandamiseks j\u00e4tame k\u00f5rvale eelduse 3, et programm on k\u00e4ivitatud ja t\u00f6\u00f6tab l\u00f5puni. Lisaks on meil vaja riistvara tuge ja nagu sa v\u00f5isid arvata, kasutame me taimerit<\/b> aktiveerimat\u00f6\u00f6tava \u00fclesande katkestamiseks ja kontekstide vahetamiseks<\/b>. Seega v\u00f5ib planeerija midagi ette v\u00f5tta, kui saabuvad \u00fclesanded B ja C \u2014 katkestada \u00fclesande A t\u00e4itmise ja alustada \u00fclesannete B ja C t\u00f6\u00f6tlemist ning p\u00e4rast nende l\u00f5petamist j\u00e4tkata \u00fclesande A t\u00e4itmist. Sellist planeerijat nimetatakse STCF<\/b>v\u00f5i Katkestatav t\u00f6\u00f6 esimesena<\/b>.<\/p>\n
Aeg reageerimiseks (Response Time)<\/h3>\n \n Seet\u00f5ttu, kui teame \u00fclesannete t\u00e4itmise aega ja et need \u00fclesanded kasutavad ainult CPU-d, on STCF parim lahendus. Kunagi ammu t\u00f6\u00f6tasid need algoritmid \u00fcsna h\u00e4sti. Siiski veedab kasutaja n\u00fc\u00fcd suurema osa ajast terminalis ja ootab t\u00f5husat interaktiivset suhtlemist. Nii s\u00fcndis uus m\u00f5\u00f5dik \u2014 reaktsiooniaeg<\/b> ().<\/p>\n
Reaktsiooniaeg arvutatakse j\u00e4rgmiselt:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Seega, eelneva n\u00e4ite puhul on reaktsiooniaeg j\u00e4rgmine: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Selgub, et algoritm STCF ei ole v\u00e4ga hea juhul, kui 3 \u00fclesannet saabuvad korraga \u2014 tal tuleb oodata, kuni v\u00e4iksemad \u00fclesanded on t\u00e4ielikult l\u00f5pule viidud. Seega on algoritm hea p\u00f6\u00f6rdumisaja m\u00f5\u00f5dikute jaoks, kuid halb interaktiivsuse m\u00f5\u00f5dikute jaoks. Kujutage ette, et proovite terminalis s\u00fcmboleid tekstiredaktorisse sisestada, kuid peate ootama rohkem kui 10 sekundit, kuna m\u00f5ni teine \u00fclesanne kasutab protsessorit. See pole just meeldiv.<\/p>\n
Ringk\u00e4ik<\/h3>\n \n Selle probleemi lahendamiseks on v\u00e4lja t\u00f6\u00f6tatud algoritm Ringk\u00e4ik<\/b> (RR). P\u00f5him\u00f5te on bastante lihtne: selle asemel, et k\u00e4ivitada \u00fclesandeid kuni nende t\u00e4ieliku l\u00f5puleviimiseni, k\u00e4ivitame \u00fclesande teatud ajavahemikuks (mida nimetatakse ajakvotiks) ja seej\u00e4rel switchime j\u00e4rgmise \u00fclesande juurde queue's. Algoritm kordab oma t\u00f6\u00f6d, kuni k\u00f5ik \u00fclesanded on l\u00f5pule viidud. Samuti peab programmi t\u00e4itmise aeg olema ajaga, mil timer katkestab protsessi. N\u00e4iteks, kui timer katkestab protsessi iga x=10ms, peab protsessi t\u00e4itmise aken olema 10-iga jagatav ja olema 10, 20 v\u00f5i x*10.<\/p>\n
Vaadakem n\u00e4idet: \u00dclesanded A, B ja C saabuvad korraga s\u00fcsteemi ja iga\u00fcks neist soovib t\u00f6\u00f6tada 5 sekundit. Algoritm SJF t\u00e4idab iga \u00fclesande l\u00f5puni enne, kui k\u00e4ivitab j\u00e4rgmise. Vastupidiselt algoritmile RR, mille k\u00e4ivitusaeg on 1s, t\u00f6\u00f6deldakse \u00fclesandeid j\u00e4rgmiselt (joonis 4.3):<\/p>\n
Keskmine reageerimisaeg algoritmile RR (0+1+2)\/3=1, samas kui SJF puhul (0+5+10)\/3=5.<\/p>\n
On loogiline eeldada, et ajavahemik on RR jaoks v\u00e4ga oluline parameeter \u2014 mida l\u00fchem on see, seda k\u00f5rgem on vastamise aeg. Kuid seda ei tohi teha liiga l\u00fchikeseks, kuna konteksti vahetamine m\u00e4ngib samuti oma osa \u00fcldises j\u00f5udluses. Seet\u00f5ttu m\u00e4\u00e4rab t\u00e4itmise akna valiku OS arhitekt, s\u00f5ltuvalt \u00fclesannetest, mida on plaanis t\u00e4ita. Konteksti vahetamine ei ole ainus abiprotseduur, mis aega kulutab \u2014 k\u00e4ivitatud programm tegeleb paljude muude asjadega, n\u00e4iteks erinevate vahem\u00e4lu s\u00fcsteemidega ning iga vahetamise puhul tuleb seda keskkonda salvestada ja taastada, mis v\u00f5ib samuti n\u00f5uda palju aega.<\/p>\n
RR on suurep\u00e4rane planeerija, kui r\u00e4\u00e4kida vaid vastamise aja m\u00f5\u00f5dikust. Kuid kuidas k\u00e4itub \u00fclesande ringluse m\u00f5\u00f5dik selle algoritmi puhul? Vaadake eespool toodud n\u00e4idet, kus A, B, C t\u00f6\u00f6aeg on 5s ja nad saabuvad samal ajal. \u00dclesanne A l\u00f5petab kell 13, B kell 14, C kell 15 ja keskmine ringluse aeg saab olema 14s. Seega on RR k\u00f5ige halvem algoritm ringluse m\u00f5\u00f5diku jaoks.<\/p>\n
\u00dcldisemalt \u00f6eldes, on iga RR t\u00fc\u00fcpi algoritm aus \u2014 see jagab CPU t\u00f6\u00f6aega v\u00f5rdselt k\u00f5ikide protsesside vahel. Ja seet\u00f5ttu on need m\u00f5\u00f5dikud pidevas konfliktis omavahel.<\/p>\n
Seega on meil mitu vastuolulist algoritmi ja veelgi on m\u00f5ned oletused \u2014 et \u00fclesande aeg on teada ja et \u00fclesanne kasutab ainult CPU-d.<\/p>\n
Segamine I\/O-ga<\/h3>\n \n Esmalt eemaldame oletuse 4, et protsess kasutab ainult CPU-d, mis loomulikult ei ole t\u00f5si, ja protsessid v\u00f5ivad p\u00f6\u00f6rduda ka muude seadmete poole.<\/p>\n
Kohe, kui m\u00f5ni protsess taotleb sisse-\/v\u00e4ljundoperatsiooni, muutub protsess blokeerituks, oodates I\/O l\u00f5petamist. Kui I\/O saadetakse k\u00f5vakettale, v\u00f5ib selline operatsioon kesta mitu ms v\u00f5i kauem, ja sel hetkel on protsessor inaktiveeritud. Selle aja jooksul saab ajakava kasutada protsessorit m\u00f5ne teise protsessiga. J\u00e4rgmine otsus, mille planeerija peab langetama, on see, millal protsess l\u00f5petab oma I\/O. Kui see juhtub, toimub katkestus ja OS viib I\/O taotlenud protsessi valmis olekusse.<\/p>\n
Vaatame mitme \u00fclesande n\u00e4idet. Iga\u00fchel neist on vaja 50 ms protsessori aega. Siiski p\u00f6\u00f6rdub esimene I\/O poole iga 10 ms (mis toimub samuti iga 10 ms). Protsess B kasutab lihtsalt 50 ms protsessorit ilma I\/O-ta.<\/p>\n
Oraaklit enam ei ole.<\/h3>\n \n N\u00fc\u00fcd proovime loobuda eeldusest, et \u00fclesande t\u00f6\u00f6aeg on teada. See on \u00fcldiselt halvim ja ebareaalne eeldus kogu loendist. Tegelikult teavad keskmised tavalised operatsioonis\u00fcsteemid \u00fclesannete t\u00e4itmise aja kohta v\u00e4ga v\u00e4he, kuidas siis luua planeerijat teadmata, kui kaua \u00fclesanne kestab? V\u00f5ib-olla saame kasutada m\u00f5ningaid RR p\u00f5him\u00f5tteid selle probleemi lahendamiseks?<\/p>\n
Kokkuv\u00f5te<\/h3>\n \n Oleme k\u00e4sitlenud p\u00f5hitegevusi \u00fclesannete planeerimise osas ja vaadanud kahte planeerijate perekonda. Esimene k\u00e4ivitab k\u00f5ige l\u00fchema \u00fclesande k\u00f5igepealt, suurendades seel\u00e4bi p\u00f6\u00f6rdeaega, teine aga jaguneb k\u00f5ikide \u00fclesannete vahel \u00fchtlaselt, et suurendada reageerimise aega. M\u00f5lemad algoritmid on halvad seal, kus teise perekonna algoritmid on head. Samuti oleme vaadelnud, kuidas CPU ja I\/O paralleelne kasutamine v\u00f5ib parandada j\u00f5udlust, kuid ei ole siiski lahendanud operatsioonis\u00fcsteemi ennustamise probleemi. J\u00e4rgmises loengus vaatame planeerijat, mis vaatab l\u00e4himinevikku ja p\u00fc\u00fcab tulevikku ennustada. Seda nimetatakse 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