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ä . 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 =)
Suunnittelu: Monitasoinen palautejono
Tässä luennossa puhumme ongelmista, jotka liittyvät yhden tunnetuimman lähestymistavan kehittämiseen
suunnittelu, jota kutsutaan Monitasoinen palautejono (MLFQ). MLFQ-aikataulun kuvaili ensimmäisen kerran vuonna 1962 Fernando J. Corbató järjestelmässä ns.
Yhteensopiva Time-Sharing System (CTSS). Nämä teokset (mukaan lukien myöhemmät työt
Multics) nimitettiin myöhemmin Turing-palkinnon saajaksi. Aikatauluttaja oli
Myöhemmin parantunut ja saanut ulkonäön, joka löytyy jo
joitain nykyaikaisia järjestelmiä.
MLFQ-algoritmi yrittää ratkaista 2 perustavanlaatuista päällekkäistä ongelmaa.
Ensiksi, se yrittää optimoida läpimenoaikaa, joka, kuten edellisellä luennolla puhuimme, optimoidaan menetelmällä, joka alkaa jonon kärjestä.
lyhyitä tehtäviä. Käyttöjärjestelmä ei kuitenkaan tiedä, kuinka kauan tämä tai tuo prosessi kestää ja tämä
tarvittava tieto SJF-, STCF-algoritmien toimintaan. Toiseksi, MLFQ yrittää
tehdä järjestelmästä reagoivaksi käyttäjille (esimerkiksi niille, jotka istuvat ja
tuijottaa näyttöä odottaessaan tehtävän valmistumista) ja siten minimoi aika
vastaus. Valitettavasti algoritmit, kuten RR, vähentävät vasteaikaa, mutta
vaikuttaa huonosti läpimenoaikamittariin. Tästä syystä ongelmamme: Kuinka suunnitella
aikataulu, joka täyttää vaatimukset ja samalla ei tiedä mitään
prosessin luonne yleensä? Kuinka ajoittaja voi oppia tehtävien ominaisuudet,
jonka se käynnistää ja siten tehdä parempia aikataulupäätöksiä?
Ongelman ydin: Kuinka suunnitella tehtävien asettaminen ilman täydellistä tietoa?
Kuinka suunnitella ajoitus, joka samanaikaisesti minimoi vasteajan
interaktiivisiin tehtäviin ja samalla minimoi läpimenoajan tietämättään
tieto tehtävien suoritusajasta?
Huomaa: oppia aiemmista tapahtumista
MLFQ-jono on erinomainen esimerkki järjestelmästä, johon on koulutettu
menneitä tapahtumia ennustaakseen tulevaisuutta. Tällaisia lähestymistapoja on usein
löytyy käyttöjärjestelmästä (Ja monilla muilla tietojenkäsittelytieteen aloilla, mukaan lukien haarat
laitteistoennusteet ja välimuistialgoritmit). Samanlaisia matkoja
laukaista, kun tehtävillä on käyttäytymisvaiheita ja ne ovat siten ennustettavissa.
Tämän tekniikan kanssa tulee kuitenkin olla varovainen, koska ennustaminen on erittäin helppoa.
voi osoittautua vääräksi ja saada järjestelmän tekemään huonompia päätöksiä kuin
olisi ilman tietoa ollenkaan.
MLFQ: Perussäännöt
Harkitse MLFQ-algoritmin perussääntöjä. Ja vaikka tämän algoritmin toteutukset
niitä on useita, peruslähestymistavat ovat samanlaisia.
Harkittavassa toteutuksessa MLFQ:lla on useita
erilliset jonot, joilla kullakin on eri prioriteetti. Milloin tahansa,
suoritettavaksi valmis tehtävä on samassa jonossa. MLFQ käyttää prioriteetteja,
päättää, mikä tehtävä ajetaan suoritettavaksi, ts. tehtävä korkeammalla
prioriteetti (tehtävä jonosta, jolla on korkein prioriteetti) käynnistetään ensin
jonottaa.
Tietyssä jonossa voi tietysti olla useampi kuin yksi tehtävä, joten
joten heillä on sama prioriteetti. Tässä tapauksessa mekanismia käytetään
RR käynnistämissuunnitteluun näiden tehtävien joukossa.
Näin pääsemme kahteen MLFQ:n perussääntöön:
- Sääntö 1: Jos prioriteetti(A) > Prioriteetti(B), tehtävä A suoritetaan (B ei)
- Sääntö 2: Jos prioriteetti(A) = Priority(B), A&B aloitetaan käyttämällä RR:tä
Edellä olevan perusteella MLFQ:n suunnittelun avaintekijät ovat
ovat prioriteetteja. Sen sijaan, että antaisi jokaiselle kiinteän prioriteetin
tehtävässä MLFQ muuttaa prioriteettiaan havaitun käyttäytymisen mukaan.
Jos tehtävä esimerkiksi pysähtyy jatkuvasti CPU:ssa odottaessaan näppäimistön syöttämistä,
MLFQ pitää prosessin prioriteetin korkeana, koska näin
interaktiivisen prosessin pitäisi toimia. Jos päinvastoin, tehtävä on jatkuvasti ja
on prosessoriintensiivinen pitkän ajan, MLFQ alentaa sen
prioriteetti. Siten MLFQ tutkii prosessien käyttäytymistä niiden ollessa käynnissä.
ja käyttää käyttäytymismalleja.
Piirretään esimerkki siitä, miltä jonot voivat jossain vaiheessa näyttää
aika ja sitten saat jotain tällaista:
Tässä mallissa 2 prosessia A ja B ovat jonossa korkeimmalla prioriteetilla. Käsitellä asiaa
C on jossain keskellä ja prosessi D on aivan jonon lopussa. Yllä olevan mukaan
MLFQ-algoritmin kuvaukset, ajastin suorittaa vain tehtäviä, joilla on korkein
RR:n mukainen prioriteetti ja tehtävät C, D ovat poissa työstä.
Staattinen tilannekuva ei tietenkään anna täydellistä kuvaa MLFQ:n toiminnasta.
On tärkeää ymmärtää tarkasti, miten kuva muuttuu ajan myötä.
Yritys 1: Kuinka muuttaa prioriteettia
Tässä vaiheessa sinun on päätettävä, kuinka MLFQ muuttaa prioriteettitasoa
tehtävän (ja siten tehtävän sijainnin jonossa) sen elinkaaren aikana. varten
tästä, sinun on pidettävä mielessä työnkulku: tietty määrä
vuorovaikutteisia tehtäviä lyhyillä käyttöajoilla (ja siten usein julkaistavilla
CPU) ja useita pitkiä tehtäviä, jotka käyttävät CPU:ta koko työaikansa
tällaisten tehtävien vasteaika ei ole tärkeä. Ja niin voit tehdä ensimmäisen yrityksen
toteuttaa MLFQ-algoritmi seuraavilla säännöillä:
- Sääntö 3: Kun tehtävä tulee järjestelmään, se asetetaan jonoon, jolla on korkein
- etusijalla.
- Sääntö 4a: Jos tehtävä käyttää koko aikaikkunaansa, se
- prioriteetti on alennettu.
- Sääntö 4b: Jos tehtävä vapauttaa CPU:n ennen kuin sen aikaikkuna umpeutuu, niin se
- pysyy samana prioriteettina.
Esimerkki 1: Yksi pitkäkestoinen tehtävä
Kuten tästä esimerkistä näet, pääsytehtävä on asetettu korkeimmalle
etusijalla. 10 ms:n aikaikkunan jälkeen prosessin prioriteetti lasketaan.
aikatauluttaja. Seuraavan aikaikkunan jälkeen tehtävä on lopulta alennettu
järjestelmän alin prioriteetti, missä se pysyy.
Esimerkki 2: Poimi lyhyen tehtävän
Katsotaanpa nyt esimerkkiä siitä, kuinka MLFQ yrittää lähestyä SJF:ää. Siinä
esimerkiksi kaksi tehtävää: A, joka on pitkään jatkuva tehtävä
vievät CPU:n ja B:n, mikä on lyhyt interaktiivinen tehtävä. Olettaa
että A oli jo ollut käynnissä jonkin aikaa tehtävän B saapuessa.
Tämä kaavio näyttää skenaarion tulokset. Tehtävä A, kuten mikä tahansa tehtävä,
prosessorin käyttö oli aivan alhaalla. Tehtävä B saapuu aikaan T=100 ja tulee
sijoitetaan korkeimman prioriteetin jonoon. Koska käyttöaika on lyhyt,
se valmistuu ennen kuin se saavuttaa viimeisen jonon.
Tästä esimerkistä sinun pitäisi ymmärtää algoritmin päätavoite: koska algoritmi ei
tietää pitkän tai lyhyen tehtävän, niin ensinnäkin hän olettaa, että tehtävä
lyhyt ja antaa sille korkeimman prioriteetin. Jos se on todella lyhyt tehtävä, niin
se suoritetaan nopeasti, muuten, jos se on pitkä tehtävä, se etenee hitaasti
prioriteetti alas ja pian osoittaa, että hän on todella pitkä tehtävä, joka ei
vaatii vastausta.
Esimerkki 3: Entä I/O?
Katsotaanpa nyt I/O-esimerkkiä. Kuten säännössä 4b todetaan,
jos prosessi vapauttaa prosessorin käyttämättä täysin prosessoriaikaansa,
silloin se pysyy samalla prioriteettitasolla. Tämän säännön tarkoitus on melko yksinkertainen.
- jos interaktiivinen työ suorittaa paljon I/O:ta, esimerkiksi odottaa
käyttäjän näppäinpainalluksista tai hiirestä, tällainen tehtävä vapauttaa prosessorin
ennen varattua ikkunaa. Emme haluaisi jättää väliin tällaista ensisijaista tehtävää,
ja siten se pysyy samalla tasolla.
Tämä esimerkki näyttää kuinka algoritmi toimisi tällaisten prosessien kanssa - interaktiivinen tehtävä B, joka tarvitsee CPU:ta vain 1 ms ennen suorittamista
I/O-prosessi ja pitkä työ A, joka käyttää CPU:ta koko ajan.
MLFQ pitää prosessin B korkeimmalla prioriteetilla
vapauttaa CPU. Jos B on interaktiivinen tehtävä, niin algoritmi on tässä tapauksessa saavuttanut
sen tarkoitus on käynnistää interaktiivisia tehtäviä nopeasti.
Ongelmia nykyisessä MLFQ-algoritmissa
Aiemmissa esimerkeissä olemme rakentaneet MLFQ:n perusversion. Ja näyttää siltä, että hän
tekee työnsä hyvin ja oikeudenmukaisesti jakaa suorittimen ajan tasapuolisesti
pitkiä tehtäviä ja sallia lyhyitä tehtäviä tai tehtäviä, jotka ovat raskaasti käytettävissä
I/O:lle käsitelläksesi nopeasti. Valitettavasti tämä lähestymistapa sisältää useita
vakavia ongelmia.
Ensiksi, nälkäongelma: jos järjestelmässä on monia interaktiivisia
tehtäviä, ne kuluttavat kaiken suorittimen ajan eivätkä siis yhtäkään pitkää aikaa
tehtävä ei saa mahdollisuutta suorittaa (he näkevät nälkää).
Toiseksi, älykkäät käyttäjät voisivat kirjoittaa ohjelmansa niin
huijaa aikatauluttaja. Petos on siinä, että tehdään jotain pakottaakseen
ajastin antaa prosessille enemmän CPU-aikaa. Algoritmi joka
edellä kuvattu on melko alttiina tällaisille hyökkäyksille: ennen kuin aikaikkuna on käytännössä
jälkeen, sinun on suoritettava I / O-toiminto (joillekin tiedostoista riippumatta)
ja siten vapauttaa CPU. Tällainen käyttäytyminen antaa sinun pysyä samana
itse jono ja saat taas suuremman prosenttiosuuden suorittimen ajasta. Jos tehty
tämä on oikein (esim. käytä 99 % ikkunaajasta ennen CPU:n vapauttamista),
tällainen tehtävä voi yksinkertaisesti monopolisoida prosessorin.
Lopuksi, ohjelma voi muuttaa käyttäytymistään ajan myötä. Ne tehtävät
jotka käyttivät prosessoria, voivat muuttua interaktiivisiksi. Esimerkissämme samanlainen
tehtäviä ei käsitellä ajoittajalta asianmukaisesti, kuten muut tekisivät
(alkuperäiset) interaktiiviset tehtävät.
Kysymys yleisölle: mitä hyökkäyksiä aikatauluja vastaan nykymaailmassa voitaisiin tehdä?
Yritys 2: Lisää prioriteettia
Yritetään muuttaa sääntöjä ja katsotaan, voimmeko välttää ongelmia
nälkä. Mitä voimme tehdä varmistaaksemme, että se liittyy
CPU-tehtävät saavat aikansa (vaikka ei kauan).
Yksinkertaisena ratkaisuna ongelmaan voit ehdottaa ajoittain
lisätä kaikkien tällaisten tehtävien prioriteettia järjestelmässä. On monia tapoja
Tämän saavuttamiseksi yritetään toteuttaa esimerkkinä jotain yksinkertaista: kääntää
kaikki tehtävät kerralla korkeimpaan prioriteettiin, tästä syystä uusi sääntö:
- Rule5: Siirrä kaikki järjestelmän tehtävät ylimpään jonoon jonkin ajanjakson S jälkeen.
Uusi sääntömme ratkaisee kaksi ongelmaa kerralla. Ensinnäkin prosessit
taatusti ei kuole nälkään: korkeimmassa jonossa olevat tehtävät jaetaan
prosessoriaika RR-algoritmin mukaan ja siten kaikki prosessit vastaanottavat
prosessorin aika. Toiseksi, jos jokin prosessi, jota aiemmin käytettiin
vain prosessori tulee interaktiiviseksi, se pysyy jonossa korkeimman kanssa
etusijalle saatuaan kerran korkeimman prioriteetin korotuksen.
Harkitse esimerkkiä. Harkitse tässä skenaariossa yhden prosessin käyttöä
CPU ja kaksi interaktiivista, lyhyttä prosessia. Kuvan vasemmalla puolella oleva kuva esittää käyttäytymistä ilman prioriteettitehostetta ja näin pitkäkestoinen tehtävä alkaa nälkiintyä kahden interaktiivisen tehtävän saapuessa järjestelmään. Oikeanpuoleisessa kuvassa joka 50 ms suoritetaan prioriteetin korotus ja siten kaikki prosessit taataan vastaanottavan prosessoriaikaa ja ne käynnistetään säännöllisesti. 50 ms tässä tapauksessa otetaan esimerkkinä, todellisuudessa tämä luku on jonkin verran suurempi.
On selvää, että jaksollisen nousuajan S lisääminen johtaa
looginen kysymys: mikä arvo pitäisi asettaa? Yksi hyvin ansaituista
järjestelmäinsinöörit John Outterhout viittasivat vastaaviin määriin järjestelmissä nimellä voo-doo
vakio, koska ne vaativat jollain tavalla mustaa magiaa oikeaan
altistuminen. Ja valitettavasti S:llä on sellainen maku. Jos asetat myös arvon
suuret - pitkät tehtävät näkevät nälkää. Ja jos asetat sen liian alhaiseksi,
interaktiiviset tehtävät eivät saa oikeaa CPU-aikaa.
Yritys 3: Parempi kirjanpito
Nyt meillä on vielä yksi ongelma ratkaistava: kuinka ei
sallitaanko aikataulun huijaaminen? Tämän mahdollisuuden syylliset ovat
säännöt 4a, 4b, jotka sallivat työn säilyttää prioriteettinsa vapauttamalla prosessorin
ennen määrätyn ajan umpeutumista. Miten käsitellä sitä?
Ratkaisuna tässä tapauksessa voidaan pitää parempi CPU-ajan laskenta kussakin
MLFQ-taso. Sen sijaan, että unohtaisit ohjelman käyttämän ajan
prosessori varatulle aikavälille, sinun tulee ottaa se huomioon ja tallentaa. Jälkeen
prosessi on käyttänyt sille varatun ajan, se pitäisi alentaa seuraavaan
prioriteettitaso. Nyt ei ole väliä miten prosessi käyttää aikansa - miten
laskee jatkuvasti prosessorilla tai puheluina. Täten,
sääntö 4 tulee kirjoittaa uudelleen seuraavasti:
- Rule4: Kun tehtävä on käyttänyt sille varatun ajan nykyisessä jonossa (riippumatta siitä, kuinka monta kertaa se vapautti CPU:n), tällaisen tehtävän prioriteetti vähenee (se siirtyy jonossa alaspäin).
Katsotaanpa esimerkkiä:
»
Kuvassa näkyy, mitä tapahtuu, jos yrität huijata ajoittajaa
jos se olisi aiempien sääntöjen 4a kanssa, 4b olisi tulos vasemmalla. Uuden kanssa
sääntö on, että tulos on oikealla. Ennen suojausta mikä tahansa prosessi saattoi kutsua I/O:ta ennen valmistumista ja
hallitsevat siten CPU:ta suojauksen käyttöönoton jälkeen, käyttäytymisestä riippumatta
I/O, hän menee silti alas jonoon eikä näin ollen voi tehdä sitä epärehellisesti
ottaa CPU-resurssit haltuunsa.
MLFQ:n ja muiden ongelmien parantaminen
Yllä olevien parannusten myötä syntyy uusia ongelmia: yksi tärkeimmistä
kysymyksiä - kuinka parametroida tällainen ajastin? Nuo. Kuinka paljon pitäisi olla
jonoja? Minkä kokoinen ohjelmaikkunan pitäisi olla jonossa? Miten
Ohjelma tulee usein asettaa etusijalle nälkään ja nälänhädän välttämiseksi
ottaa huomioon ohjelman käyttäytymisen muutos? Näihin kysymyksiin ei ole yksinkertaista
vastausta ja vain kokeiluja kuormilla ja myöhemmillä konfiguroinneilla
ajoitus voi johtaa tyydyttävään tasapainoon.
Esimerkiksi useimmat MLFQ-toteutukset antavat sinun määrittää erilaisia
aikavälit eri jonoihin. Korkean prioriteetin jonot ovat yleensä
lyhyet välit. Nämä jonot koostuvat interaktiivisista tehtävistä,
joiden välillä vaihtaminen on melko herkkä ja kestää 10 tai vähemmän
neiti. Sitä vastoin matalan prioriteetin jonot koostuvat pitkäkestoisista tehtävistä, jotka käyttävät
PROSESSORI. Ja tässä tapauksessa pitkät aikavälit sopivat erittäin hyvin (100 ms).
Tässä esimerkissä korkean prioriteetin jonossa 2 on 20 tehtävää
ms jaettu 10 ms ikkunoihin. 40 ms keskijonossa (20 ms ikkuna) ja matalan prioriteetin jonossa
Jonoaikaikkunasta tuli 40 ms, jolloin tehtävät suorittivat työnsä.
MLFQ:n käyttöönotto Solaris-käyttöjärjestelmässä on aikajakoisten aikataulujen luokka.
Ajastin tarjoaa joukon taulukoita, jotka määrittelevät tarkalleen, miten sen pitäisi
muuttaa prosessin prioriteettia sen elinkaaren aikana, mikä sen koko pitäisi olla
varattava ikkuna ja kuinka usein tehtäväprioriteettia nostetaan. Järjestelmänvalvoja
järjestelmä voi olla vuorovaikutuksessa tämän taulukon kanssa ja saada ajoittimen käyttäytymään
eri tavalla. Tässä taulukossa on oletusarvoisesti 60 jonoa asteittain kasvavina
ikkunan koko 20 ms (korkea prioriteetti) useisiin satoihin ms (matalin prioriteetti) ja
myös lisäämällä kaikki tehtävät kerran sekunnissa.
Muut MLFQ-aikataulut eivät käytä taulukkoa tai mitään erityistä
tässä luvussa kuvatut säännöt, päinvastoin, ne laskevat prioriteetteja käyttäen
matemaattiset kaavat. Esimerkiksi FreeBSD:n ajastin käyttää kaavaa for
nykyisen tehtävän prioriteetin laskeminen prosessin määrän perusteella
käytti prosessoria. Lisäksi suorittimen käyttö mätänee ajan myötä ja siten
Siten prioriteetin lisäys on jonkin verran erilainen kuin edellä on kuvattu. Tämä on totta
kutsutaan vaimenemisalgoritmeiksi. Versiosta 7.1 lähtien FreeBSD käyttää ULE-aikataulua.
Lopuksi monilla suunnittelijoilla on muita ominaisuuksia. Esimerkiksi jotkut
aikataulut varaavat korkeammat tasot käyttöjärjestelmän toimintaan ja siten
Näin ollen mikään käyttäjäprosessi ei voi saada korkeinta prioriteettia
järjestelmä. Joissakin järjestelmissä voit antaa neuvoja avuksi
ajoittaja priorisoimaan oikein. Esimerkiksi käyttämällä komentoa mukava
voit lisätä tai vähentää tehtävän prioriteettia ja siten lisätä tai vähentää
vähentää ohjelman CPU-ajan mahdollisuuksia.
MLFQ: Yhteenveto
Olemme kuvanneet suunnittelulähestymistavan nimeltä MLFQ. Hänen nimensä
toimintaperiaatteella tehty - siinä on useita jonoja ja se käyttää palautetta
priorisoidaksesi tehtävää.
Sääntöjen lopullinen muoto on seuraava:
- Rule1: Jos prioriteetti(A) > Prioriteetti(B), tehtävä A suoritetaan (B ei)
- Rule2: Jos prioriteetti(A) = Priority(B), A&B aloitetaan käyttämällä RR:tä
- Rule3: Kun tehtävä tulee järjestelmään, se sijoitetaan korkeimman prioriteetin jonoon.
- Rule4: Kun tehtävä on käyttänyt sille varatun ajan nykyisessä jonossa (riippumatta siitä, kuinka monta kertaa se vapautti CPU:n), tällaisen tehtävän prioriteetti vähenee (se siirtyy jonossa alaspäin).
- Rule5: Siirrä kaikki järjestelmän tehtävät ylimpään jonoon jonkin ajanjakson S jälkeen.
MLFQ on kiinnostava seuraavasta syystä - sen sijaan, että se vaatisi tietoa
Tehtävän luonteesta jo etukäteen, algoritmi oppii tehtävän ja joukot aiemman käyttäytymisen
painopisteet vastaavasti. Siten hän yrittää istua kahdella tuolilla kerralla - saavuttaakseen suorituskyvyn pienissä tehtävissä (SJF, STCF) ja ajaakseen rehellisesti pitkiä,
CPU-lataustyöt. Siksi monet järjestelmät, mukaan lukien BSD ja niiden johdannaiset,
Solaris, Windows, Mac käyttävät jonkinlaista algoritmia ajoittajana
MLFQ lähtökohtana.
Lisämateriaalit:
- (laskenta)
Lähde: will.com