Sissejuhatus operatsioonisüsteemidesse
Tere Habr! Juhin teie tähelepanu artiklite sarjale-tõlketele ühest minu arvates huvitavast kirjandusest - OSTEP. Selles materjalis käsitletakse üsna põhjalikult unixi-laadsete operatsioonisüsteemide tööd, nimelt tööd protsesside, erinevate ajakavade, mälu ja muude sarnaste komponentidega, mis moodustavad kaasaegse OS-i. Kõikide materjalide originaale näed siit . Pange tähele, et tõlge on tehtud ebaprofessionaalselt (üsna vabalt), kuid loodan, et säilitasin üldise tähenduse.
Selle teema laboritööd leiate siit:
Muud osad:
Võite vaadata ka minu kanalit aadressil =)
Sissejuhatus Schedulerisse
Probleemi olemus: kuidas koostada ajakava poliitikat
Kuidas tuleks kavandada aluseks olevad planeerijapoliitika raamistikud? Millised peaksid olema peamised eeldused? Millised mõõdikud on olulised? Milliseid põhitehnikaid kasutati varajastes arvutisüsteemides?
Töökoormuse eeldused
Enne võimalike poliitikate üle arutlemist tehkem esmalt mõned lihtsustavad kõrvalekalded süsteemis töötavate protsesside kohta, mida ühiselt nimetatakse töökoormus. Töökoormuse määratlemine on ehituspoliitika oluline osa ja mida rohkem te töökoormusest teate, seda paremat poliitikat saate kirjutada.
Teeme järgmised eeldused süsteemis töötavate protsesside kohta, mida mõnikord nimetatakse ka töökohti (ülesanded). Peaaegu kõik need eeldused ei ole realistlikud, kuid on mõtte arendamiseks vajalikud.
- Iga ülesanne kestab sama kaua,
- Kõik ülesanded seatakse korraga,
- Määratud ülesanne töötab kuni selle täitmiseni,
- Kõik toimingud kasutavad ainult protsessorit,
- Iga ülesande täitmise aeg on teada.
Planeerija mõõdikud
Lisaks mõningatele eeldustele koormuse kohta on erinevate ajastamispoliitikate võrdlemiseks vaja teist tööriista: planeerija mõõdikud. Mõõdik on lihtsalt millegi mõõt. Planeerijate võrdlemiseks saab kasutada mitmeid mõõdikuid.
Näiteks kasutame mõõdikut nimega pöördeaeg (tööaeg). Ülesande pöördeaeg on defineeritud kui erinevus ülesande täitmise aja ja ülesande süsteemi saabumise aja vahel.
Tturnaround=Tlõpetamine–Tarrival
Kuna eeldasime, et kõik ülesanded saabusid ühel ajal, siis Ta=0 ja seega Tt=Tc. See väärtus muutub loomulikult, kui muudame ülaltoodud eeldusi.
Teine mõõdik - õiglus (õiglus, ausus). Tootlikkus ja õiglus on planeerimisel sageli vastandlikud omadused. Näiteks võib ajakava optimeerida jõudlust, kuid selle hinnaga, et oodatakse teiste ülesannete käivitamist, vähendades nii õiglust.
FIRST IN FIRST OUT (FIFO)
Kõige elementaarsem algoritm, mida saame rakendada, on FIFO või esimene, kes tuli (sisse), esimene teenin (välja). Sellel algoritmil on mitmeid eeliseid: seda on väga lihtne rakendada ja see sobib meie kõigi eeldustega ning teeb oma tööd üsna hästi.
Vaatame lihtsat näidet. Oletame, et korraga pandi 3 ülesannet. Kuid oletame, et ülesanne A saabus veidi varem kui kõik teised, nii et see ilmub täitmisloendisse varem kui teised, täpselt nagu B suhtes C. Oletame, et iga ülesannet täidetakse 10 sekundit. Kui palju kulub antud juhul nende ülesannete täitmiseks keskmiselt?
Lugedes väärtused - 10+20+30 ja jagades 3-ga, saame keskmiseks programmi täitmisajaks 20 sekundit.
Proovime nüüd oma eeldusi muuta. Eelkõige eeldus 1 ja seega me ei eelda enam, et iga ülesande täitmiseks kulub sama palju aega. Kuidas FIFO seekord hakkama saab?
Nagu selgub, on erinevatel ülesannete täitmise aegadel FIFO algoritmi tootlikkusele äärmiselt negatiivne mõju. Oletame, et ülesande A täitmiseks kulub 100 sekundit, samas kui ülesandel B ja C kulub kumbki 10 sekundit.
Nagu jooniselt näha, saab süsteemi keskmiseks ajaks (100+110+120)/3=110. Seda efekti nimetatakse konvoi efekt, kui mõned ressursi lühiajalised tarbijad seavad järjekorda raske tarbija järel. See on nagu järjekord toidupoes, kui su ees on klient täis käruga. Parim lahendus probleemile on proovida kassaaparaati vahetada või lõõgastuda ja sügavalt hingata.
Esmalt lühim töö
Kas raskekaalu protsessidega on võimalik sarnast olukorda kuidagi lahendada? Kindlasti. Teist tüüpi planeerimist nimetatakseEsmalt lühim töö (SJF). Selle algoritm on samuti üsna primitiivne – nagu nimigi ütleb, käivitatakse üksteise järel kõige lühemad ülesanded.
Selles näites on samade protsesside käitamise tulemuseks programmi keskmise tööaja paranemine ja see on võrdne 50 asemel 110, mis on peaaegu 2 korda parem.
Seega, antud eeldusel, et kõik ülesanded saabuvad samal ajal, tundub SJF-algoritm olevat kõige optimaalsem algoritm. Kuid meie oletused ei tundu endiselt realistlikud. Seekord muudame eeldust 2 ja kujutame ette, et ülesanded võivad olla igal ajal ja mitte kõik korraga. Milliseid probleeme see võib kaasa tuua?
Kujutame ette, et ülesanne A (100c) saabub esimesena ja seda hakatakse täitma. Kui t=10 saabuvad ülesanded B ja C, millest igaüks võtab aega 10 sekundit. Seega on keskmine täitmise aeg (100+(110-10)+(120-10))3 = 103. Mida saaks planeerija selle parandamiseks ette võtta?
Esmalt lühim valmimisaeg (STCF)
Olukorra parandamiseks jätame välja eelduse 3, et programm on käivitatud ja töötab kuni lõpuni. Lisaks vajame riistvaratuge ja nagu võite arvata, kasutame seda taimer jooksuülesande katkestamiseks ja konteksti vahetamine. Seega saab planeerija ülesannete B, C saabumise hetkel midagi ära teha - lõpetada ülesande A täitmise ning panna ülesanded B ja C töötlusse ning pärast nende täitmist jätkata protsessi A täitmist. Sellist planeerijat nimetatakse nn. STCFvõi Ennetav töö kõigepealt.
Selle planeerija tulemus on järgmine: ((120-0)+(20-10)+(30-10))/3=50. Seega muutub selline ajakava meie ülesannete jaoks veelgi optimaalsemaks.
Meetriline reageerimisaeg
Seega, kui teame ülesannete tööaega ja et need ülesanded kasutavad ainult CPU-d, on STCF parim lahendus. Ja kunagi varastel aegadel töötasid need algoritmid üsna hästi. Kuid kasutaja veedab nüüd suurema osa ajast terminalis ja ootab produktiivset interaktiivset kogemust. Nii sündis uus mõõdik - reaktsiooniaeg (vastus).
Reaktsiooniaeg arvutatakse järgmiselt:
Tresponse=Tfirstrun-Tarrival
Seega on eelmise näite puhul reaktsiooniaeg: A=0, B=0, C=10 (abg=3,33).
Ja selgub, et STCF-i algoritm pole nii hea olukorras, kus saabub korraga 3 ülesannet - see peab ootama, kuni väikesed ülesanded on täielikult täidetud. Seega on algoritm hea pöördeaja mõõdiku jaoks, kuid halb interaktiivsuse mõõdiku jaoks. Kujutage ette, kui istuksite terminalis ja prooviksite redaktorisse märke sisestada ja peaksite ootama rohkem kui 10 sekundit, kuna mõni muu ülesanne hõivab protsessorit. See ei ole väga meeldiv.
Seega seisame silmitsi veel ühe probleemiga – kuidas luua reageerimisaja suhtes tundlik ajakava?
Round Robini
Selle probleemi lahendamiseks töötati välja algoritm Round Robini (RR). Põhiidee on üsna lihtne: selle asemel, et käivitada ülesandeid, kuni need on lõpetatud, käivitame ülesande teatud aja (nimetatakse ajalõikeks) ja seejärel lülitame järjekorrast teisele ülesandele. Algoritm kordab oma tööd seni, kuni kõik ülesanded on täidetud. Sel juhul peab programmi tööaeg olema selle aja kordne, mille möödudes taimer protsessi katkestab. Näiteks kui taimer katkestab protsessi iga x=10ms järel, peaks protsessi täitmisakna suurus olema 10 kordne ja olema 10,20 või x*10.
Vaatame näidet: ABC ülesanded saabuvad süsteemi samaaegselt ja igaüks neist soovib töötada 5 sekundit. SJF-algoritm lõpetab iga ülesande enne teise alustamist. Seevastu RR-algoritm käivitusaknaga = 1s läbib ülesanded järgmiselt (joonis 4.3):
(SJF jälle (halb reageerimisaeg)
(Round Robin (sobiv reageerimisajaks)
RR algoritmi keskmine reageerimisaeg on (0+1+2)/3=1, SJF (0+5+10)/3=5.
Loogiline on eeldada, et ajaaken on RR-i jaoks väga oluline parameeter, mida väiksem see on, seda suurem on reaktsiooniaeg. Kuid te ei tohiks seda liiga väikeseks muuta, kuna konteksti vahetamise aeg mängib rolli ka üldises jõudluses. Seega täitmisakna aja valiku määrab OS-i arhitekt ja see sõltub ülesannetest, mida selles plaanitakse täita. Konteksti vahetamine ei ole ainuke aega raiskav teenindusoperatsioon – töötav programm töötab väga paljude muude asjadega, näiteks erinevate vahemäludega ning iga lülitiga on vaja seda keskkonda salvestada ja taastada, mis võib samuti võtta palju aega. aega.
RR on suurepärane planeerija, kui räägiksime ainult reageerimisaja mõõdikust. Kuid kuidas toimib ülesande tööaja mõõdik selle algoritmiga? Vaatleme ülaltoodud näidet, kui A, B, C tööaeg = 5s ja saabub samal ajal. Ülesanne A lõpeb kell 13, B kell 14, C kell 15 sekundit ja keskmine tööaeg on 14 sekundit. Seega on RR käivemõõdiku halvim algoritm.
Üldisemalt öeldes on iga RR-tüüpi algoritm õiglane; see jagab protsessori aja kõigi protsesside vahel võrdselt. Ja seega on need mõõdikud üksteisega pidevalt vastuolus.
Seega on meil mitu vastandlikku algoritmi ja samas on jäänud veel mitu eeldust - et tegumi aeg on teada ja ülesanne kasutab ainult CPU-d.
I/O-ga segamine
Kõigepealt eemaldame eelduse 4, et protsess kasutab ainult CPU-d; loomulikult see nii ei ole ja protsessid pääsevad juurde teistele seadmetele.
Hetkel, kui mis tahes protsess nõuab sisend-/väljundtoimingut, läheb protsess blokeeritud olekusse, oodates sisend-/väljundi lõpetamist. Kui I/O saadetakse kõvakettale, siis võib selline toiming kesta kuni mitu ms või kauem ning protsessor on sel hetkel jõude. Selle aja jooksul võib planeerija hõivata protsessori mis tahes muu protsessiga. Järgmine otsus, mille ajakava koostaja peab tegema, on see, millal protsess lõpetab oma I/O. Kui see juhtub, tekib katkestus ja OS seab protsessi, mis kutsus I/O, valmisolekusse.
Vaatame näidet mitmest probleemist. Igaüks neist nõuab 50 ms CPU aega. Kuid esimene pääseb I/O-le iga 10 ms järel (mida teostatakse samuti iga 10 ms järel). Ja protsess B kasutab lihtsalt 50 ms protsessorit ilma I/Ota.
Selles näites kasutame STCF-i planeerijat. Kuidas käitub planeerija, kui sellel käivitatakse selline protsess nagu A? Ta teeb järgmist: esmalt töötab ta täielikult läbi protsessi A ja seejärel protsessi B.
Traditsiooniline lähenemisviis selle probleemi lahendamiseks on käsitleda protsessi A iga 10 ms alamülesannet eraldi ülesandena. Seega on STJF algoritmiga alustades valik 50 ms ja 10 ms ülesande vahel ilmne. Seejärel, kui alamülesanne A on lõpetatud, käivitatakse protsess B ja I/O. Pärast I/O lõpetamist on tavaks protsessi B asemel uuesti käivitada 10 ms protsess A. Sel viisil on võimalik rakendada kattumist, kus protsessorit kasutab teine protsess, samal ajal kui esimene ootab protsessi B. I/O. Ja tänu sellele on süsteem paremini ära kasutatud – hetkel, kui interaktiivsed protsessid ootavad I/O-d, saab protsessoril käivitada ka teisi protsesse.
Oraaklit enam pole
Nüüd proovime vabaneda eeldusest, et ülesande täitmise aeg on teada. See on üldiselt halvim ja ebarealistlikum oletus kogu nimekirjas. Tegelikult teab OS ise keskmises tavalises OS-is tavaliselt väga vähe ülesannete täitmise ajast, nii et kuidas saate siis koostada planeerijat, teadmata, kui kaua ülesande täitmine aega võtab? Võib-olla saaksime selle probleemi lahendamiseks kasutada mõnda RR-i põhimõtet?
Summaarne
Vaatasime ülesannete ajastamise põhiideid ja vaatasime kahte planeerijate perekonda. Esimene alustab kõige lühema ülesandega esimesena ja suurendab seega tööaega, teine aga rebib kõigi ülesannete vahel võrdselt, suurendades reageerimisaega. Mõlemad algoritmid on halvad, kui teise perekonna algoritmid on head. Vaatasime ka, kuidas CPU ja I/O paralleelne kasutamine võib jõudlust parandada, kuid ei lahendanud OS-i selgeltnägemise probleemi. Ja järgmises õppetükis vaatleme planeerijat, mis vaatab vahetusse minevikku ja püüab ennustada tulevikku. Ja seda nimetatakse mitmetasandiliseks tagasisidejärjekorraks.
Allikas: www.habr.com