Johdatus käyttöjärjestelmiin

Hei Habr! Haluan tuoda huomionne artikkelisarjan käännöksiä yhdestä mielestäni mielenkiintoisesta kirjallisuudesta - OSTEP. Tämä materiaali käsittelee melko syvällisesti unix-tyyppisten käyttöjärjestelmien työtä, nimittäin työtä prosessien, erilaisten aikataulujen, muistin ja muiden vastaavien komponenttien kanssa, jotka muodostavat nykyaikaisen käyttöjärjestelmän. Kaikkien materiaalien alkuperäiset näet täältä täällä. Huomaa, että käännös on tehty epäammattimaisesti (melko vapaasti), mutta toivottavasti säilytin yleisen merkityksen.

Aiheen laboratoriotyöt löytyvät täältä:

Muut osat:

Voit myös katsoa kanavaani osoitteessa sähke =)

Johdatus Scheduleriin

Ongelman ydin: Kuinka kehittää ajoituspolitiikka
Miten taustalla olevat ajoituspolitiikkakehykset tulisi suunnitella? Mitkä pitäisi olla keskeiset oletukset? Mitkä mittarit ovat tärkeitä? Mitä perustekniikoita käytettiin varhaisissa laskentajärjestelmissä?

Työkuormitusoletukset

Ennen kuin keskustelemme mahdollisista politiikoista, tehdään ensin muutama yksinkertaistava poikkeama järjestelmässä käynnissä olevista prosesseista, joita kutsutaan yhteisesti ns. työmäärä. Työkuorman määrittäminen on kriittinen osa rakennuskäytäntöjä, ja mitä enemmän tiedät työmäärästä, sitä paremman käytännön voit kirjoittaa.

Tehdään seuraavat oletukset järjestelmässä käynnissä olevista prosesseista, joita joskus myös kutsutaan työpaikat (tehtävät). Lähes kaikki nämä oletukset eivät ole realistisia, mutta ne ovat välttämättömiä ajattelun kehittymiselle.

Jokainen tehtävä kestää saman ajan,
Kaikki tehtävät asetetaan samanaikaisesti,
Määrätty tehtävä toimii sen suorittamiseen asti,
Kaikki tehtävät käyttävät vain prosessoria,
Kunkin tehtävän suoritusaika tunnetaan.

Ajoitusmittarit

Joidenkin kuormitusta koskevien oletusten lisäksi tarvitaan toinen työkalu eri ajoituskäytäntöjen vertailuun: ajoitusmittarit. Mittari on vain jokin mitta jostakin. On olemassa useita mittareita, joita voidaan käyttää ajoittajien vertailuun.

Käytämme esimerkiksi metriikkaa nimeltä läpimenoaika (kiertoaika). Tehtävän läpimenoaika määritellään erona tehtävän valmistumisajan ja tehtävän saapumisajan välillä järjestelmään.

Tturnaround=Tvalmius—Tarrival

Koska oletimme, että kaikki tehtävät saapuivat samaan aikaan, niin Ta=0 ja siten Tt=Tc. Tämä arvo muuttuu luonnollisesti, kun muutamme yllä olevia oletuksia.

Toinen mittari - oikeudenmukaisuus (rehellisyys, rehellisyys). Tuottavuus ja oikeudenmukaisuus ovat usein suunnittelussa vastakkaisia piirteitä. Ajastin voi esimerkiksi optimoida suorituskyvyn, mutta sen kustannuksella, että se odottaa muiden tehtävien suorittamista, mikä vähentää oikeudenmukaisuutta.

FIRST IN FIRST OUT (FIFO)

Perusalgoritmi, jonka voimme toteuttaa, on nimeltään FIFO tai ensin saapunut, ensin palvellut (ulos). Tällä algoritmilla on useita etuja: se on erittäin helppo toteuttaa ja se sopii kaikkiin oletuksiimme ja tekee työn melko hyvin.

Katsotaanpa yksinkertaista esimerkkiä. Oletetaan, että 3 tehtävää asetettiin samanaikaisesti. Mutta oletetaan, että tehtävä A saapui hieman aikaisemmin kuin kaikki muut, joten se ilmestyy suoritusluetteloon aikaisemmin kuin muut, aivan kuten B suhteessa C:hen. Oletetaan, että jokainen niistä suoritetaan 10 sekuntia. Mikä on keskimääräinen aika näiden tehtävien suorittamiseen tässä tapauksessa?

Laskemalla arvot -10+20+30 ja jakamalla 3:lla, saadaan keskimääräinen ohjelman suoritusaika 20 sekuntia.
Yritetään nyt muuttaa oletuksiamme. Erityisesti oletus 1, joten emme enää oleta, että jokaisen tehtävän suorittaminen vie yhtä paljon aikaa. Miten FIFO pärjää tällä kertaa?

Kuten käy ilmi, erilaiset tehtävän suoritusajat vaikuttavat erittäin negatiivisesti FIFO-algoritmin tuottavuuteen. Oletetaan, että tehtävän A suorittaminen kestää 100 sekuntia, kun taas B:n ja C:n suorittaminen vie vielä 10 sekuntia.

Kuten kuvasta näkyy, järjestelmän keskimääräinen aika on (100+110+120)/3=110. Tätä vaikutusta kutsutaan saattue vaikutus, kun jotkut resurssin lyhytaikaiset kuluttajat joutuvat jonoon raskaan kuluttajan perään. Se on kuin ruokakaupan jono, kun edessäsi on asiakas täynnä kärryjä. Paras ratkaisu ongelmaan on yrittää vaihtaa kassakonetta tai rentoutua ja hengittää syvään.

Lyhyin työ ensin

Onko mahdollista ratkaista vastaava tilanne jotenkin raskaan sarjan prosesseilla? Varmasti. Toinen suunnittelutyyppi on nsLyhyin työ ensin (SJF). Sen algoritmi on myös varsin primitiivinen - kuten nimestä voi päätellä, lyhyimmät tehtävät käynnistetään ensin, yksi toisensa jälkeen.

Tässä esimerkissä samojen prosessien suorittamisen tulos on parannus ohjelman keskimääräisessä läpimenoajassa ja se on yhtä suuri kuin 50 sijasta 110, mikä on melkein 2 kertaa parempi.

Siten annetulle olettamukselle, että kaikki tehtävät saapuvat samaan aikaan, SJF-algoritmi näyttää olevan optimaalinen algoritmi. Olettamuksemme eivät kuitenkaan vieläkään vaikuta realistisilta. Tällä kertaa muutamme oletusta 2 ja tällä kertaa kuvittelemme, että tehtävät voivat olla läsnä milloin tahansa, eivätkä kaikki samaan aikaan. Mihin ongelmiin tämä voi johtaa?

Kuvitellaan, että tehtävä A (100c) saapuu ensin ja sitä aletaan suorittaa. Kohdassa t=10 saapuvat tehtävät B ja C, jotka kumpikin kestävät 10 sekuntia. Keskimääräinen suoritusaika on siis (100+(110-10)+(120-10))3 = 103. Mitä ajoittaja voisi tehdä parantaakseen tätä?

Lyhin valmistumisaika ensin (STCF)

Tilanteen parantamiseksi jätämme pois oletuksen 3, että ohjelma käynnistetään ja jatkuu loppuun asti. Lisäksi tarvitsemme laitteistotukea ja, kuten arvata saattaa, käytämme ajastin keskeyttääksesi käynnissä olevan tehtävän ja kontekstin vaihtaminen. Siten ajoittaja voi tehdä jotain sillä hetkellä, kun tehtävät B, C saapuvat - lopettaa tehtävän A suorittamisen ja laittaa tehtävät B ja C prosessointiin ja niiden valmistuttua jatkaa prosessin A suorittamista. Tällaista ajastinta kutsutaan ns. STCFtai Ennaltaehkäisevä työ ensin.

Tämän suunnittelijan tulos on seuraava: ((120-0)+(20-10)+(30-10))/3=50. Siten tällaisesta aikatauluttajasta tulee vieläkin optimaalinen tehtäviemme kannalta.

Metrinen vasteaika

Näin ollen, jos tiedämme tehtävien suoritusajan ja että nämä tehtävät käyttävät vain CPU:ta, STCF on paras ratkaisu. Ja kerran alkuaikoina nämä algoritmit toimivat melko hyvin. Käyttäjä viettää kuitenkin nyt suurimman osan ajastaan terminaalissa ja odottaa tuottavaa interaktiivista kokemusta. Näin syntyi uusi mittari - vasteaika (vastaus).

Vastausaika lasketaan seuraavasti:

Tresponse=Tfirstrun−Tarrival

Siten edellisessä esimerkissä vasteaika on: A=0, B=0, C=10 (abg=3,33).

Ja käy ilmi, että STCF-algoritmi ei ole niin hyvä tilanteessa, jossa 3 tehtävää saapuu samanaikaisesti - sen on odotettava, kunnes pienet tehtävät on suoritettu kokonaan. Joten algoritmi on hyvä läpimenoaikamittarille, mutta huono interaktiivisuusmittarille. Kuvittele, jos istuisit päätelaitteen ääressä ja yrittäisit kirjoittaa merkkejä editoriin ja joutuisit odottamaan yli 10 sekuntia, koska jokin muu tehtävä vie CPU:ta. Se ei ole kovin mukavaa.

Joten kohtaamme toisen ongelman - kuinka voimme rakentaa aikataulun, joka on herkkä vasteaikaan?

Round Robin

Tämän ongelman ratkaisemiseksi kehitettiin algoritmi Round Robin (RR). Perusidea on melko yksinkertainen: sen sijaan, että suoritettaisiin tehtäviä, kunnes ne on suoritettu, suoritamme tehtävän tietyn ajan (kutsutaan aikaviipaleeksi) ja siirrymme sitten toiseen tehtävään jonosta. Algoritmi toistaa työtään, kunnes kaikki tehtävät on suoritettu. Tässä tapauksessa ohjelman ajoajan on oltava sen ajan monikerta, jonka jälkeen ajastin keskeyttää prosessin. Jos esimerkiksi ajastin keskeyttää prosessin joka x=10ms, prosessin suoritusikkunan koon tulee olla 10:n kerrannainen ja 10,20 tai x*10.

Katsotaanpa esimerkkiä: ABC-tehtävät saapuvat järjestelmään samanaikaisesti ja jokainen niistä haluaa suorittaa 5 sekuntia. SJF-algoritmi suorittaa jokaisen tehtävän ennen uuden aloittamista. Sitä vastoin RR-algoritmi, jossa käynnistysikkuna = 1s, käy läpi tehtävät seuraavasti (kuva 4.3):

(SJF taas (Bad for Response Time)

(Round Robin (hyvä vasteaika)

Keskimääräinen vasteaika RR-algoritmille on (0+1+2)/3=1, kun taas SJF:n (0+5+10)/3=5.

On loogista olettaa, että aikaikkuna on erittäin tärkeä parametri RR:lle; mitä pienempi se on, sitä korkeampi vasteaika. Sitä ei kuitenkaan pidä tehdä liian pieneksi, koska kontekstin vaihtoaika vaikuttaa myös kokonaissuorituskykyyn. Näin ollen käyttöjärjestelmän arkkitehti määrittää suoritusikkunan ajan, ja se riippuu siinä suoritettavista tehtävistä. Kontekstin vaihtaminen ei ole ainoa aikaa tuhlaava palvelutoiminto - käynnissä oleva ohjelma toimii monilla muilla asioilla, esimerkiksi erilaisilla välimuistilla, ja jokaisella kytkimellä on tarpeen tallentaa ja palauttaa tämä ympäristö, mikä voi myös viedä paljon aika.

RR on loistava aikataulu, jos puhumme vain vasteaikamittarista. Mutta miten tehtävän läpimenoaikamittari käyttäytyy tämän algoritmin kanssa? Tarkastellaan yllä olevaa esimerkkiä, kun A, B, C toiminta-aika = 5s ja saapuvat samaan aikaan. Tehtävä A päättyy klo 13, B klo 14, C klo 15 ja keskimääräinen läpimenoaika on 14 sekuntia. Siten RR on huonoin liikevaihdon metriikan algoritmi.

Yleisemmin sanottuna mikä tahansa RR-tyyppinen algoritmi on oikeudenmukainen; se jakaa suorittimen ajan tasaisesti kaikkien prosessien kesken. Ja näin ollen nämä mittarit ovat jatkuvasti ristiriidassa keskenään.

Näin ollen meillä on useita vastakkaisia algoritmeja ja samalla on vielä jäljellä useita oletuksia - että tehtävän aika on tiedossa ja että tehtävä käyttää vain CPU:ta.

Sekoitus I/O:lla

Ensinnäkin poistetaan oletus 4, että prosessi käyttää vain CPU:ta; näin ei tietenkään ole ja prosessit voivat käyttää muita laitteita.

Kun jokin prosessi pyytää I/O-toimintoa, prosessi siirtyy estettyyn tilaan odottaen I/O:n valmistumista. Jos I/O lähetetään kiintolevylle, tällainen toiminto voi kestää useita ms tai kauemmin, ja prosessori on tällä hetkellä käyttämättömänä. Tänä aikana ajastin voi varata prosessorin millä tahansa muulla prosessilla. Seuraava päätös, joka ajoittajan on tehtävä, on, milloin prosessi suorittaa I/O:n. Kun näin tapahtuu, tapahtuu keskeytys ja käyttöjärjestelmä asettaa I/O:ta kutsuneen prosessin valmiustilaan.

Katsotaanpa esimerkkiä useista tehtävistä. Jokainen niistä vaatii 50 ms CPU-aikaa. Kuitenkin ensimmäinen käyttää I/O:ta 10 ms:n välein (joka myös suoritetaan 10 ms:n välein). Ja prosessi B käyttää yksinkertaisesti 50 ms prosessoria ilman I/O:ta.

Tässä esimerkissä käytämme STCF-aikataulua. Kuinka ajoittaja käyttäytyy, jos siinä käynnistetään A:n kaltainen prosessi? Hän tekee seuraavaa: ensin hän käsittelee kokonaan prosessin A ja sitten prosessin B.

Perinteinen lähestymistapa tämän ongelman ratkaisemiseksi on käsitellä prosessin A jokaista 10 ms:n alitehtävää erillisenä tehtävänä. Näin ollen STJF-algoritmilla aloitettaessa valinta 50 ms tehtävän ja 10 ms tehtävän välillä on ilmeinen. Sitten, kun osatehtävä A on suoritettu, prosessi B ja I/O käynnistetään. I/O:n valmistumisen jälkeen on tapana käynnistää 10 ms:n prosessi A uudelleen prosessin B sijasta. Näin voidaan toteuttaa päällekkäisyys, jossa prosessoria käyttää toinen prosessi, kun ensimmäinen odottaa prosessia. I/O. Ja sen seurauksena järjestelmää hyödynnetään paremmin - sillä hetkellä, kun interaktiiviset prosessit odottavat I/O:ta, prosessorilla voidaan suorittaa muita prosesseja.

Oraakkelia ei enää ole

Yritetään nyt päästä eroon oletuksesta, että tehtävän suoritusaika tiedetään. Tämä on yleensä koko luettelon huonoin ja epärealistisin oletus. Itse asiassa keskimääräisessä tavallisessa käyttöjärjestelmässä käyttöjärjestelmä itse tietää yleensä hyvin vähän tehtävien suoritusajasta, joten kuinka voit sitten rakentaa ajastimen tietämättä kuinka kauan tehtävän suorittaminen kestää? Ehkä voisimme käyttää joitain RR-periaatteita tämän ongelman ratkaisemiseksi?

Koko

Tarkastelimme tehtävien ajoituksen perusideoita ja tarkastelimme kahta aikatauluttajaperhettä. Ensimmäinen aloittaa lyhimmän tehtävän ensin ja pidentää siten läpimenoaikaa, kun taas toinen repeytyy kaikkien tehtävien välillä tasaisesti, mikä lisää vasteaikaa. Molemmat algoritmit ovat huonoja, jos toisen perheen algoritmit ovat hyviä. Tarkastelimme myös, kuinka suorittimen ja I/O:n rinnakkaiskäyttö voi parantaa suorituskykyä, mutta emme ratkaisseet käyttöjärjestelmän selvänäkimisen ongelmaa. Ja seuraavalla oppitunnilla tarkastelemme suunnittelijaa, joka katsoo välittömään menneisyyteen ja yrittää ennustaa tulevaisuutta. Ja sitä kutsutaan monitasoiseksi palautejonoksi.

Lähde: will.com

Käyttöjärjestelmät: Three Easy Pieces. Osa 4: Johdatus ajoittimeen (käännös)