Sissejuhatus operatsioonisüsteemidesse

Tere, Habr! Soovin esitleda teile huvitavate artiklite tõlgitud seeriat — OSTEP. Käesolevas materjalis uuritakse sügavalt unix-laadsete operatsioonisüsteemide toimimist, nimelt — protsesside, erinevate planeerijate, mälu ja teiste sarnaste komponentide töötamist, mis koosnevad kaasaegsest operatsioonisüsteemist. Kõiki materjale saate näha siin siit. Palun arvestage, et tõlge on tehtud mitteprofessionaalselt (piisavalt vaba), kuid loodan, et üldine mõte on säilinud.

Käesoleva aine laboritöid saab leida siit:

Teised osad:

Ja võite ka külastada minu kanalit Telegramis =)

Sissejuhatus ajastamisse

Probleemi olemus: Kuidas välja töötada ajastamispoliitika
Kuidas peaksid olema välja töötatud ajastamispoliitika alused? Millised peaksid olema peamised eeldused? Millised näitajad on olulised? Milliseid põhitehnikaid kasutati varasemates arvutisüsteemides?

Töökoormuse eeldused

Enne kui arutada võimalikke poliitikaid, teeme esmalt mõned lihtsustavad kõrvalekalded süsteemis käivitatud protsessidest, mida kokku nimetatakse töökoormuseks. Töökoormuse määramine on kriitiline osa poliitikate koostamisest ja mida rohkem te koormusest teate, seda kvaliteetsemat poliitikat te suudate kirjutada.

Teeme järgmised eeldused süsteemis käivitatud protsesside kohta, mida mõnikord nimetatakse töödeks (jobs). Praktiliselt kõik need eeldused ei ole realistlikud, kuid need on mõtte arendamiseks vajalikud.

Iga ülesanne töötab sama kaua,
Kõik ülesanded saadetakse samal ajal,
Saadetud ülesanne töötab kuni selle lõpetamiseni,
Kõik ülesanded kasutavad ainult CPU-d,
Iga ülesande tööaeg on teada.

Ajastamise näitajad

Peale mõningate töökoormuse eelduste on vajalik ka mingi tööriist erinevate ajastamispoliitikate võrdlemiseks: ajastamise näitajad. Näitaja on lihtsalt mingi mõõt mingi asja kohta. On olemas teatud kogus näitajaid, mida saab kasutada ajastajate võrdlemiseks.

Näiteks kasutame näitajat, mida nimetatakse täitmise ajaks (turnaround time). Ülesande täitmise aeg määratakse kui erinevus ülesande lõpetamise aja ja ülesande süsteemi sisenemise aja vahel.

Tturnaround=Tcompletion−Tarrival

Kuna me eeldasime, et kõik ülesanded sisenevad korraga, siis Ta=0 ja seega Tt=Tc. See väärtus muutub loomulikult, kui me muuda mainitud eeldusi.

Teine näitaja on õiglus (õiglus, ausus). Tõhusus ja ausus on sageli vastandlikud omadused planeerimises. Näiteks võib planeerija optimeerida tõhusust, kuid see toob kaasa teiste ülesannete ooteaja, mis omakorda vähendab ausust.

ESIMENE SISSE, ESIMENE VÄLJA (FIFO)

Kõige fundamentaalsem algoritm, mida me saame rakendada, nimetatakse FIFO-ks või first come (in), first served (out). Sellel algoritmil on mitmeid eeliseid: see on väga lihtne rakendada ja vastab kõigile meie eeldustele, täites tööd üsna hästi.

Vaatame lihtsat näidet. Oletame, et kolm ülesannet on samal ajal esitatud. Kuid oletame, et ülesanne A saabus veidi varem kui kõik teised, seega on see täitmise loendis enne teisi, samuti nagu B seoses V-ga. Oletame, et igaühe täitmiseks kulub 10 sekundit. Milline on sel juhul nende ülesannete keskmine täitmise aeg?

Arvutades väärtused — 10+20+30 ja jagades 3-ga, saame keskmiseks täitmise ajaks 20 sekundit.
Nüüd proovime muuta meie eeldusi. Eelkõige eeldust 1 ja mitte enam eeldada, et iga ülesanne täitub sama kaua. Kuidas käitub FIFO sel korral?

Kuidas selgub, et erinevad täitmise ajad mõjutavad FIFO algoritmi efektiivsust äärmiselt negatiivselt. Oletame, et ülesanne A täitub 100 sekundit, samas kui B ja V jäävad ikka 10 sekundile.

Kuna jooniselt on näha, et süsteemi keskmine aeg ilmneb (100+110+120)⁄3=110. Sellist efekti nimetatakse konvoiefektiks, kus mõned lühiajalised ressursikasutajad seisavad järjekorras raskete kasutajate järel. See on sarnaselt järjekorraga toidupoes, kus teie ees on ostja, kellel on täis ostukäru. Parim lahendus probleemile on proovida kassapidajat vahetada või lihtsalt rahuneda ja sügavalt hingata.

Lühim Töö Esimene

Kas on võimalik sellist olukorda raskete protsessidega kuidagi lahendada? Loomulikult. Teine tüüpi planeerimine on nimetatudLühim Töö Esimene (SJF). Selle algoritm on samuti piisavalt primitiivne — nagu nimest selgub, käivituvad kõigepealt kõige lühemad ülesanded üksteise järel.

Selles näites on sama protsesside käivitamise tulemuseks keskmise programmi pöördeaja paranemine, mis on võrdne 50 asemel 110, mis on praktiliselt kaks korda parem.

Seega, eeldades, et kõik ülesanded saabuvad samal ajal, tundub SJF algoritm olevat kõige optimaalsem algoritm. Ent meie eeldused ei tundu siiski realistlikud. Seekord muudame eeldust 2 ja kujutame ette, et ülesanded võivad saabuda igal ajal, mitte kõik korraga. Millistele probleemidele see võib viia?

Oletame, et ülesanne A (100s) saabub esimesena ja alustab täitmist. Hetkel t=10 saabuvad ülesanded B ja C, kummagi täitmise aeg on 10 sekundit. Seega, keskmine täitmise aeg on (100+(110-10)+(120-10))/3 = 103. Mida võiks planeerija teha, et olukorda parandada?

Lühim täitmise kestus esimesena (STCF)

Olukorra parandamiseks jätame kõrvale eelduse 3, et programm on käivitatud ja töötab lõpuni. Lisaks on meil vaja riistvara tuge ja nagu sa võisid arvata, kasutame me taimerit aktiveerimatöötava ülesande katkestamiseks ja kontekstide vahetamiseks. Seega võib planeerija midagi ette võtta, kui saabuvad ülesanded B ja C — katkestada ülesande A täitmise ja alustada ülesannete B ja C töötlemist ning pärast nende lõpetamist jätkata ülesande A täitmist. Sellist planeerijat nimetatakse STCFvõi Katkestatav töö esimesena.

Selle planeerija töö tulemuseks on järgmine: ((120-0)+(20-10)+(30-10))/3=50. Seega, selline planeerija muutub meie ülesannete jaoks veelgi optimaalsemaks.

Aeg reageerimiseks (Response Time)

Seetõttu, kui teame ülesannete täitmise aega ja et need ülesanded kasutavad ainult CPU-d, on STCF parim lahendus. Kunagi ammu töötasid need algoritmid üsna hästi. Siiski veedab kasutaja nüüd suurema osa ajast terminalis ja ootab tõhusat interaktiivset suhtlemist. Nii sündis uus mõõdik — reaktsiooniaeg ().

Reaktsiooniaeg arvutatakse järgmiselt:

Tresponse=Tfirstrun−Tarrival

Seega, eelneva näite puhul on reaktsiooniaeg järgmine: A=0, B=0, C=10 (abg=3,33).

Selgub, et algoritm STCF ei ole väga hea juhul, kui 3 ülesannet saabuvad korraga — tal tuleb oodata, kuni väiksemad ülesanded on täielikult lõpule viidud. Seega on algoritm hea pöördumisaja mõõdikute jaoks, kuid halb interaktiivsuse mõõdikute jaoks. Kujutage ette, et proovite terminalis sümboleid tekstiredaktorisse sisestada, kuid peate ootama rohkem kui 10 sekundit, kuna mõni teine ülesanne kasutab protsessorit. See pole just meeldiv.

Seega seisame silmitsi teise probleemiga — kuidas saame luua ajakava, mis oleks vastutulelik reageerimise ajale?

Ringkäik

Selle probleemi lahendamiseks on välja töötatud algoritm Ringkäik (RR). Põhimõte on bastante lihtne: selle asemel, et käivitada ülesandeid kuni nende täieliku lõpuleviimiseni, käivitame ülesande teatud ajavahemikuks (mida nimetatakse ajakvotiks) ja seejärel switchime järgmise ülesande juurde queue's. Algoritm kordab oma tööd, kuni kõik ülesanded on lõpule viidud. Samuti peab programmi täitmise aeg olema ajaga, mil timer katkestab protsessi. Näiteks, kui timer katkestab protsessi iga x=10ms, peab protsessi täitmise aken olema 10-iga jagatav ja olema 10, 20 või x*10.

Vaadakem näidet: Ülesanded A, B ja C saabuvad korraga süsteemi ja igaüks neist soovib töötada 5 sekundit. Algoritm SJF täidab iga ülesande lõpuni enne, kui käivitab järgmise. Vastupidiselt algoritmile RR, mille käivitusaeg on 1s, töödeldakse ülesandeid järgmiselt (joonis 4.3):

(SJF jälle (halb reageerimise ajal)

(Ringkäik (hea reageerimise ajal)

Keskmine reageerimisaeg algoritmile RR (0+1+2)/3=1, samas kui SJF puhul (0+5+10)/3=5.

On loogiline eeldada, et ajavahemik on RR jaoks väga oluline parameeter — mida lühem on see, seda kõrgem on vastamise aeg. Kuid seda ei tohi teha liiga lühikeseks, kuna konteksti vahetamine mängib samuti oma osa üldises jõudluses. Seetõttu määrab täitmise akna valiku OS arhitekt, sõltuvalt ülesannetest, mida on plaanis täita. Konteksti vahetamine ei ole ainus abiprotseduur, mis aega kulutab — käivitatud programm tegeleb paljude muude asjadega, näiteks erinevate vahemälu süsteemidega ning iga vahetamise puhul tuleb seda keskkonda salvestada ja taastada, mis võib samuti nõuda palju aega.

RR on suurepärane planeerija, kui rääkida vaid vastamise aja mõõdikust. Kuid kuidas käitub ülesande ringluse mõõdik selle algoritmi puhul? Vaadake eespool toodud näidet, kus A, B, C tööaeg on 5s ja nad saabuvad samal ajal. Ülesanne A lõpetab kell 13, B kell 14, C kell 15 ja keskmine ringluse aeg saab olema 14s. Seega on RR kõige halvem algoritm ringluse mõõdiku jaoks.

Üldisemalt öeldes, on iga RR tüüpi algoritm aus — see jagab CPU tööaega võrdselt kõikide protsesside vahel. Ja seetõttu on need mõõdikud pidevas konfliktis omavahel.

Seega on meil mitu vastuolulist algoritmi ja veelgi on mõned oletused — et ülesande aeg on teada ja et ülesanne kasutab ainult CPU-d.

Segamine I/O-ga

Esmalt eemaldame oletuse 4, et protsess kasutab ainult CPU-d, mis loomulikult ei ole tõsi, ja protsessid võivad pöörduda ka muude seadmete poole.

Kohe, kui mõni protsess taotleb sisse-/väljundoperatsiooni, muutub protsess blokeerituks, oodates I/O lõpetamist. Kui I/O saadetakse kõvakettale, võib selline operatsioon kesta mitu ms või kauem, ja sel hetkel on protsessor inaktiveeritud. Selle aja jooksul saab ajakava kasutada protsessorit mõne teise protsessiga. Järgmine otsus, mille planeerija peab langetama, on see, millal protsess lõpetab oma I/O. Kui see juhtub, toimub katkestus ja OS viib I/O taotlenud protsessi valmis olekusse.

Vaatame mitme ülesande näidet. Igaühel neist on vaja 50 ms protsessori aega. Siiski pöördub esimene I/O poole iga 10 ms (mis toimub samuti iga 10 ms). Protsess B kasutab lihtsalt 50 ms protsessorit ilma I/O-ta.

Selles näites kasutame STCF planeerijat. Kuidas käitub planeerija, kui me käivitame sellel protsessi A? See teeb järgmist — esmalt täidab see täielikult protsessi A ja seejärel protsessi B.

Traditsiooniline lähenemine selle probleemi lahendamiseks on tõlgendada iga 10 ms alamülesanne protsessist A eraldi ülesandena. Nii et stardiga STJF algoritmiga on valik 50 ms ülesande ja 10 ms ülesande vahel ilmne. Kui alamülesanne A on lõpetatud, käivitub protsess B ja I/O. Pärast I/O lõpetamist on otsustatud uuesti käivitada 10 ms protsess A asemel protsessi B. Nii on võimalik saavutada kattuvus, kus CPU-d kasutab teine protsess, samal ajal kui esimene ootab I/O. Lõppkokkuvõttes on süsteem paremini kasutatud — ajal, mil interaktiivsed protsessid ootavad I/O, saavad protsessoril töötada ka teised protsessid.

Oraaklit enam ei ole.

Nüüd proovime loobuda eeldusest, et ülesande tööaeg on teada. See on üldiselt halvim ja ebareaalne eeldus kogu loendist. Tegelikult teavad keskmised tavalised operatsioonisüsteemid ülesannete täitmise aja kohta väga vähe, kuidas siis luua planeerijat teadmata, kui kaua ülesanne kestab? Võib-olla saame kasutada mõningaid RR põhimõtteid selle probleemi lahendamiseks?

Kokkuvõte

Oleme käsitlenud põhitegevusi ülesannete planeerimise osas ja vaadanud kahte planeerijate perekonda. Esimene käivitab kõige lühema ülesande kõigepealt, suurendades seeläbi pöördeaega, teine aga jaguneb kõikide ülesannete vahel ühtlaselt, et suurendada reageerimise aega. Mõlemad algoritmid on halvad seal, kus teise perekonna algoritmid on head. Samuti oleme vaadelnud, kuidas CPU ja I/O paralleelne kasutamine võib parandada jõudlust, kuid ei ole siiski lahendanud operatsioonisüsteemi ennustamise probleemi. Järgmises loengus vaatame planeerijat, mis vaatab lähiminevikku ja püüab tulevikku ennustada. Seda nimetatakse multi-level feedback queue.

Allikas: habr.com