Sissejuhatus operatsioonisüsteemidesse

Tere, Habr! Soovin tutvustada teile artiklite seeriat, mis on tõlkinud minu arvates huvitavat kirjandust — OSTEP. Selles materjalis käsitletakse sügavalt unix-sarnaste operatsioonisüsteemide toimimist, sealhulgas protsesside, erinevate planeerijate, mäluhalduse ja muude sarnaste komponentide töötamise aspekte, mis moodustavad tänapäeva operatsioonisüsteemi. Originaali kõiki materjale saate vaadata siit: siin. Palun arvestage, et tõlge on tehtud mitteprofessionaalselt (piisavalt vabalt), kuid loodan, et olen põhisisu säilitanud.

Laboritööd selle aine kohta leiate siit:

Teised osad:

Lisaks võite minna minu kanalile Telegraam =)

Planeerija sissejuhatus

Probleemi olemus: Kuidas välja töötada planeerimise poliitika
Kuidas peaksid olema kujundatud planeerimise poliitikate põhiraamid? Millised peaksid olema peamised eeldused? Millised on olulised mõõdikud? Milliseid põhitehnikaid on varasemates arvutisüsteemides kasutatud?

Koormuse eeldused

Enne võimalike poliitikate arutamist teeme esmalt mõned üldistavad tähelepanekud süsteemis käivitatud protsesside kohta, mida koos nimetatakse koormuseks.Määratledes koormust kui poliitikate koostamise kriitilist osa, saate te kirjutada kvaliteetseid poliitikaid, mida rohkem te koormusest teate.

Teeme järgmised eeldused süsteemis käitatud protsesside kohta, mida mõnikord nimetatakse ka töödeks. (ülesanded). Praktikas ei ole peaaegu ükski neist eeldustest realistlik, kuid need on mõttearendamiseks vajalikud.

Iga ülesanne toimub sama kaua,
Kõik ülesanded käivitatakse samaaegselt,
Käivitatud ülesanne töötab kuni selle lõpetamiseni,
Kõik ülesanded kasutavad ainult CPU-d,
Iga ülesande tööaeg on teada.

Planeerija mõõdikud

Mõningate koormushinnangute kõrval on vajalik ka erinevate planeerimispoliitikate võrdlemiseks mingisugune tööriist: planeerijate metoodika. Metoodika on lihtsalt mingi mõõtmisviis millelegi. On olemas mitmeid metoodikaid, mida saab kasutada planeerijate võrdlemiseks.

Näitena kasutame metoodikat, mida nimetatakse täitmisajaks (turnaround time). Ülesande täitmise aeg määratletakse kui erinevus ülesande valmimise ja ülesande süsteemi saabumise aja vahel.

Tturnaround=Tcompletion−Tarrival

Kuna oletame, et kõik ülesanded saabusid ühel ja samal ajal, siis Ta=0 ning seega Tt=Tc. See väärtus muutub loomulikult, kui muudame ülaltoodud oletusi.

Teine metoodika on fairness (õiglus). Tootlikkus ja õiglus on planeerimises sageli vastandlikud omadused. Näiteks võib planeerija optimeerida tootlikkust, kuid teiste ülesannete käivitamise ooteaja arvelt, mistõttu kannatab õiglus.

FIRST IN FIRST OUT (FIFO)

Kõige lihtsam algoritm, mida saame kasutada, nimetatakse FIFO-ks või kes tuleb (sisse), see läheb (välja) esimesena. Sellel algoritmil on mitmeid eeliseid: see on väga lihtne rakendada ja sobib kõigi meie eelduste alla, tehes tööd üsna hästi.

Vaadakem lihtsat näidet. Oletame, et 3 ülesannet esitati samaaegselt. Kuid oletame, et ülesanne A tuli veidi varem kui kõik teised, seega on see teostamisnimekirjas esikohal, täpselt nagu B on suhte V. Oletame, et igaühe täitmine kestab 10 sekundit. Mis siis on nende ülesannete keskmine täitmise aeg?

Arvutades väärtused — 10+20+30 ja jagades selle 3-ga, saame programmi keskmiseks täitmise ajaks 20 sekundit.
Nüüd proovime muuta oma eeldusi. Eelkõige muutsime eeldust 1 ja seega ei eelda enam, et iga ülesanne kestab võrdse aja. Kuidas käitub FIFO seekord?

Kuid selgub, et erinevad ülesannete täitmise ajad mõjutavad FIFO algoritmi tööviljakust äärmiselt negatiivselt. Oletame, et ülesanne A kestab 100 sekundit, samas kui B ja V jäävad mõlemad 10 sekundi pikkuseks.

Kuna joonisel on näha, et keskmine aeg süsteemis on (100+110+120)/3=110. Seda efekti nimetatakse konvoiefektiks, kus mõned lühiajalised ressursikasutajad seisavad pikaajalise kasutaja järel. See on nagu järjekord poe kassas, kus teie ees on klient täis ostukäru. Parim lahendus probleemile on proovida vahetada kassat või lihtsalt rahuneda ja sügavalt hingata.

Lühim töö kõigepealt

Kas on võimalik lahendada sarnane olukord raskete protsessidega? Muidugi. Teine planeerimise tüüp onLühim töö kõigepealt (SJF). Selle algoritm on samuti piisavalt primitiivne — nagu nimigi ütleb, käivituvad esimesena kõige lühemad ülesanded üksteise järel.

Antud näites on nende samade protsesside käivitamise tulemuseks keskmise töötlusaja paranemine ja see on võrdne 50 asemel 110, mis on praktiliselt 2 korda parem.

Seega, antud juhul, et kõik ülesanded saabuvad ühel ja samal ajal, tundub SJF algoritm kõige optimaalsemana. Siiski ei tundu meie eeldused endiselt realistlikud. Seekord muudame eeldust 2 ning kujutame ette, et ülesanded saavad saabuda igal ajal, mitte kõik korraga. Millistele probleemidele see võib viia?

Kujutame ette, et ülesanne A (100s) saabub esimesena ja hakkab täituma. Moment t=10 saabuvad ülesanded B ja C, kummagi täitmine kestab 10 sekundit. Seega on keskmine täitmise aeg (100+(110-10)+(120-10))/3 = 103. Mida võiks ajakava teha, et olukorda paremaks muuta?

Lühim täitmisaeg esimesena (STCF)

Et olukorda parandada, loobume eeldusest 3, et programm käivitub ja töötab lõpuni. Samuti on meil vaja riistvara tuge ja nagu võisite arvata, kasutame me taimerit töös oleva ülesande katkestamiseks ja konteksti vahetamiseks.. Nii saab ajakava teha midagi ülesannete B ja V saabumise hetkest – lõpetada ülesande A täitmine ja tegeleda ülesannetega B ja V ning pärast nende lõpetamist jätkata ülesande A täitmist. Sellist ajakava nimetatakse STCFvõi Eelnev Ülesanne Esiteks.

Selle ajakava töö tulemuseks on selline tulemus: ((120-0)+(20-10)+(30-10))/3=50. Nii muutub selline ajakava meie ülesannete jaoks veelgi optimaalsemaks.

Mõõdik Vastusaeg (Response Time)

Seega, kui me teame ülesannete tööaega ja et need ülesanded kasutavad ainult CPU-d, on STCF parim lahendus. Kunagi ammu töötasid need algoritmid väga hästi. Kuid nüüd veedab kasutaja enamiku ajast terminalis ja ootab sellelt tootlikku interaktiivset suhtlemist. Nii sündis uus mõõdik – vastusaeg (reaktsioon).

Vastusaeg arvestatakse järgmiselt:

Tresponse=Tfirstrun−Tarrival

Seega, eelmise näite puhul on vastusaeg: A=0, B=0, V=10 (abg=3,33).

Ja selgub, et STCF algoritm pole sugugi nii hea olukorras, kus 3 ülesannet saabuvad samal ajal — see peab ootama, kuni väiksed ülesanded on täielikult lõpetatud. Seega on algoritm hea ringlusaega mõõtva metrika jaoks, kuid halb interaktiivsuse mõõtmiseks. Kujutage ette, et istute terminali taga ja proovite redigeerijas sümboleid trükkida, kuid peate ootama üle 10 sekundi, sest mõni teine ülesanne kasutab protsessorit. See pole just meeldiv.

Seega seisame silmitsi teise probleemiga — kuidas saame ehitada ajatundliku planeerija?

Ringkonnaga

Selle probleemi lahendamiseks töötati välja algoritm Ringkonnaga (RR). Peamine idee on üsna lihtne: selle asemel, et käivitada ülesandeid täies mahus, käivitame ülesande teatud ajavahemikuks (nimetatakse ajakvandiks) ja seejärel lülitume järjekorrast järgmisele ülesandele. Algoritm kordab oma tööd, kuni kõik ülesanded on lõpule viidud. Samal ajal peab programmi töötamise aeg olema jagatav ajaga, mil kell peatab protsessi. Näiteks, kui kell peatab protsessi iga x=10 ms järel, peab protsessi täitmise akna suurus olema jagatav 10 ja olema 10, 20 või x*10.

Vaatame näidet: Ülesanded A, B ja C saabuvad süsteemi samaaegselt ning igaüks neist soovib töötada 5 sekundit. Algoritm SJF täidab iga ülesande lõpuni, enne kui lülitub teise. Vastupidiselt algoritmile RR, mille käivitamise aken on 1 s, läbib see ülesandeid järgmisel viisil (joonis 4.3):

(SJF Again (Halb vastuse aeg)

(Ringlojale (Hea vastuse aeg)

Algoritmi RR keskmine vastuse aeg (0+1+2)/3=1, samas kui SJF jaoks (0+5+10)/3=5.

On loogiliselt eeldada, et ajakenk on RR jaoks väga oluline parameeter; mida lühem see on, seda kõrgem on vastusaeg. Kuid seda ei tohi ka liiga väikseks teha, kuna konteksti vahetamise aeg mõjutab samuti üldist sooritust. Seega, akna täitmise aeg valitakse OS arhitekti poolt ning see sõltub ülesannetest, mida seal plaanitakse täita. Konteksti vahetamine ei ole ainus teenindusoperatsioon, mis aega kulutab — käivitatud programm tegeleb paljude muude aspektidega, näiteks erinevate vahemäludega, ja iga vahetuse korral tuleb see keskkond talletada ja taastada, mis võib samuti aega võtta.

RR on suurepärane planeerija, kui rääkida ainult vastusaega mõõtvast metrikast. Kuid kuidas käitub ülesande käibe aeg selle algoritmi juures? Vaadakem ülaltoodud näidet, kus A, B, C töötavad 5 sekundit ja saabuvad samal ajal. Ülesanne A lõpetab 13. sekundil, B 14. ja C 15. sekundil, mis annab keskmiseks käibe ajaks 14 sekundit. Seega on RR kõige kehvem algoritm käibe mõõtmise jaoks.

Üldiselt öeldes on iga RR tüüpi algoritm aus, jaotades CPU tööaja võrdselt kõigi protsesside vahel. Seetõttu jäävad need mõõdikud pidevalt konfliktiks.

Seega on meil mitu vastandlikku algoritmi ja samas on veel mitmeid eeldusi — et ülesande tööaeg on teada ja et ülesanne kasutab ainult CPU-d.

Segamine I/O-ga

Esiteks eemaldame eelduse 4, et protsess kasutab ainult CPU-d, mis pole tõsi, kuna protsessid võivad pöörduda ka teiste seadmete poole.

Hetkel, kui mõni protsess taotleb sisendi- ja väljundioperatsiooni, läheb protsess blokeeritud olekusse, oodates I/O lõpetamist. Kui I/O suunatakse kõvakettale, võib see operatsioon kesta isegi mitu ms või kauem, ja sel ajal on CPU ootel. Sel perioodil saab planeerija CPU-d kasutada mõne muu protsessi jaoks. Järgmine otsus, mille planeerija peab tegema, on see, millal protsess lõpetab oma I/O. Kui see juhtub, toimub katkestus ja operatsioonisüsteem viib I/O käivitanud protsessi valmis olekusse.

Vaatame näidet mitmest ülesandest. Igaühel neist on vaja 50 ms protsessoriaega. Kuid esimene pöördub iga 10 ms järel I/O poole (mis toimub samuti 10 ms). Protsess B kasutab lihtsalt 50 ms protsessorit ilma I/O-ta.

Käesolevas näites kasutame STCF planeerijat. Kuidas käitub planeerija, kui käivitame selle protsessi nagu A? See käitub järgmiselt — esmalt töötleb see täielikult protsessi A ja seejärel protsessi B.

Traditsiooniline lähenemine seda probleemi lahendada on tõlgendada iga 10 ms alamülesanne protsessist A kui eraldiseisvat ülesannet. Seega, alustades algoritmiga STJF, on valik 50 ms ülesande ja 10 ms ülesande vahel ilmselge. Kui alamülesanne A lõpetatakse, käivitatakse protsess B ja I/O. Pärast I/O lõpetamist otsustatakse uuesti käivitada 10 ms protsess A asemel protsessi B. Seega on võimalik realiseerida kattuvust, kui CPU-d kasutab teine protsess, samal ajal kui esimene ootab I/O-d. Ja lõpptulemusena on süsteem paremini kasutuses — hetkel, kui interaktiivsed protsessid ootavad I/O-d, võivad protsessoril töötada ka teised protsessid.

Oraakel on kadunud

Proovime nüüd vabaneda eeldusest, et ülesande töötamise aeg on teada. See on üldiselt halvim ja ebareaalne eeldus kogu nimekirjas. Tegelikult teab keskmine tavapärane operatsioonisüsteem tavaliselt väga vähe ülesannete täitmise ajast, kuidas siis ehitada ajastust ilma teadmata, kui kaua ülesanne kestab? Kas me võiksime kasutada mõningaid RR-põhimõtteid selle probleemiga tegelemiseks?

Kokkuvõte

Oleme uurinud ülesannete ajastamise põhiteooriaid ja vaadanud kahte planeerijate peret. Esimene käivitab kõige lühema ülesande esimesena, suurendades seeläbi pöördeaega, teine aga jaotab koormuse kõigi ülesannete vahel võrdselt, parandades reageerimisaega. Mõlemad algoritmid on halvad seal, kus on head teise pereliigi algoritmid. Samuti oleme käsitlenud, kuidas CPU ja I/O paralleelne kasutamine võib tõsta tootlikkust, kuid ei ole lahendanud operatsioonisüsteemi selgeltnägemise probleemi. Järgmises tunnis vaatame planeerijat, mis vaatab lähiajalukku ja proovib tulevikku ette ennustada. See kannab nime mitme taseme tagasiside järjekord.

Allikas: habr.com