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 =)

Planeerimine: Multi-Level Feedback Queue

Selles loengus räägime ühest tuntud lähenemisviisist
planeerimisele, mida nimetatakse Multi-Level Feedback Queue (MLFQ). Esiteks kirjeldas MLFQ planeerijat 1962. aastal Fernando J. Corbató süsteemis, mida nimetatakse
Compatible Time-Sharing System (CTSS). Need tööd (sealhulgas hilisemad tööd
Multics) esitati hiljem Turingi auhinnale. Planeerijat on
hiljem täiustatud ja see on omandanud kuju, mida võib leida juba
mõnedest kaasaegsetest süsteemidest.

MLFQ algoritm püüab lahendada kahte põhilist, omavahel seotud probleemi.
Esiteks, püüab see optimeerida ümberküljendusaega, mis nagu me vaatasime eelmises loengus, optimeeritakse kõige
lühikeste ülesannete esmakordse paremuse meetodi kaudu. Siiski, opsüsteem ei tea, kui kaua üks või teine protsess kestab, ja see on
vajalik teave SJF, STCF algoritmide toimimiseks. Teiseks, MLFQ püüab
teha süsteemi kasutajate jaoks vastutulelikuks (näiteks neile, kes istuvad ja
vaatavad ekraani, oodates ülesande lõppemist) ja seega minimeerida
reaktsiooniaega. Kahjuks vähendavad sarnased algoritmid nagu RR reaktsiooniaega, kuid mõjutavad väga
halvasti ümberküljendusaega. Seega tekib meil probleem: Kuidas projekteerida
planeerijat, mis vastaks meie nõudmistele, teadmata samas midagi
protsessi olemusest, üldiselt? Kuidas saab planeerija õppida ülesannete omadusi,
mida see käivitab, ja võtta seega paremaid planeerimisotsuseid?

Probleemi tuum: Kuidas planeerida ülesannete seadmist ilma ideaalsete teadmisteta?
Kuidas arendada planeerijat, mis samal ajal minimeerib reaktsiooniaega
interaktiivsetele ülesannetele ja samas minimeerib ümberküljendusaega ilma eelneva
teadmise ülesande täitmise ajast?

Märkus: õpime eelnevate sündmuste põhjal

MLFQ järjekord on suurepärane näide süsteemist, mis õpib
minevikusündmustest, et ennustada tulevikku. Taolised lähenemisviisid esinevad sageli
opsüsteemides (ja paljude teiste informaatika harudes, sealhulgas ennustuse harudes riistvara ja vahemälu algoritmides). Sellised lähenemisviisid
toimivad, kui ülesannetel on käitumise faasid ja seega on need ettearvatavad.
kui ülesannetel on käitumuslikud faasid, on need seega ettearvatavad.
Kuid sellise tehnika kasutamisel tuleb olla ettevaatlik, sest ennustused võivad kergesti osutuda valeeks.
see võib viia süsteemi halvimate otsusteni kui need,
mis oleksid täieliku teadmise puudumisel.

MLFQ: Põhireeglid

Vaadakem MLFQ algoritmi põhireegleid. Kuigi selle algoritmi
realiseerimisi on mitu, on põhisuunad sarnased.
Antud realiseerimisel, mida me käsitleme, on MLFQ-l mitu
erinevat järjekorda, millest igal on erinev prioriteet. Igal hetkel
on täitmisele valmis ülesanne ühes järjekorras. MLFQ kasutab prioriteete,
et otsustada, millist ülesannet täitma asuda, s.t. ülesanne kõrgema
prioriteediga (ülesanne kõrgema prioriteediga järjekorrast) käivitatakse esimesena.
Ilmselgelt võib konkreetses järjekorras olla rohkem kui üks ülesanne, seega
on neil sama prioriteet. Sel juhul kasutatakse
RR mehanismi nende ülesannete täitmise plaanimiseks.
Nii jõuame MLFQ jaoks kahele põhireeglile:
Reegel 1: Kui Prioriteet(A) > Prioriteet(B), käivitatakse ülesanne A (B ei saa).

Reegel 2: Kui Prioriteet(A) = Prioriteet(B), käivitatakse A ja B RR kaudu.
Eeltoodust tulenevalt on MLFQ planeerimise võtmeelemendid

prioriteedid. Selle asemel, et määrata igale
ülesandele fikseeritud prioriteet, muudab MLFQ selle prioriteeti vastavalt käitumisele.
Näiteks kui ülesanne pidevalt teeb CPU-le ülesandeid, ootades klaviatuuri sisestust,
hoiab MLFQ protsessi prioriteedi kõrgel, sest just nii
peaks töötama interaktiivne protsess. Kui aga vastupidi, ülesanne kasutab pidevalt ja
intensiivselt CPU-d pika aja jooksul, alandab MLFQ selle
prioriteeti. Seega õpib MLFQ protsesside käitumist nende töö hetkel
ja kohandab käitumist.
Joonistame näite, kuidas võiksid järjekorrad näha välja teatud hetkel
ajast ja selle kohaselt võiks see välja näha midagi sellist:
Antud skeemis on 2 protsessi A ja B kõrgeima prioriteediga järjekorras. Protsess

C on kuskil keskel, ja protsess D on järjekorra lõpus. Nagu eelnevalt kirjeldatud
MLFQ algoritmi kirjeldustes, täidab planeerija ülesandeid ainult kõrgeima prioriteediga.
MLFQ algoritmi kirjeldustes täidab planeerija ülesandeid ainult kõrgeima prioriteediga.
prioriteed vastavalt RR, samas kui ülesanded C, D jäävad kõrvale.
Muidugi ei anna staatiline snapshot täielikku ülevaadet, kuidas MLFQ töötab.
Oluline on mõista, kuidas pilt aja jooksul muutub.

Katse 1: Kuidas muuta prioriteeti

Sel hetkel tuleb otsustada, kuidas MLFQ prioriteedi taset muudab
ülesannete (ja seega ka ülesande positsiooni järjekorras) elu jooksul. Selleks
on oluline meeles pidada töövoogu: teatud arv
interaktiivseid ülesandeid lühikese tööajaga (ja seega sagedaste CPU vabastamistega)
ja mõned pikad ülesanded, millel on täielik CPU kasutus kogu oma tööaja, samas
kui reageerimisaeg nende jaoks ei ole oluline. Nii et saame teha esimese katse
rakendada MLFQ algoritmi järgmiste reeglitega:

Rule3: Kui ülesanne sisene süsteemi, paigutatakse see kõrgeima
prioriteedi järjekorda.
Rule4a: Kui ülesanne kasutab täielikult ette nähtud ajavahemiku, siis selle
prioriteet väheneb.
Rule4b: Kui ülesanne vabastab CPU enne oma ajavahemiku lõppemist, jääb see
enda eelmisele prioriteedile.

Näide 1: Üks pikaajaline ülesanne

Kuna näha on, et sel juhul paigutatakse ülesanne saabudes kõrgeima
prioriteediga. Pärast 10 ms ajavahemikku alandatakse selle prioriteeti
planeerija poolt. Pärast järgmist ajavahemikku alandatakse ülesanne lõpuks
süsteemi madalaimale prioriteedile, kus ta ka jääb.

Näide 2: Lühikese ülesande kaasamine

Nüüd vaatame näidet sellest, kuidas MLFQ püüab läheneda SJF-ile. Selles
näites on kaks ülesannet: A, mis on pikaajaline ülesanne, mis pidevalt
kasutab CPU-d, ja B, mis on lühike interaktiivne ülesanne. Oletame,
et A on juba töötanud mõnda aega, kui ülesanne B saabus.

Selles graafikus on näha olukorra tulemusi. Ülesanne A, nagu iga ülesanne,
millel on CPU kasutus, on kõige madalamal. Ülesanne B saabub hetkel T=100 ja
paigutatakse kõrgeima prioriteediga järjekorda. Kuna selle tööaeg on lühike, siis
lõpetab ta enne, kui jõuab viimasesse järjekorda.

Sellest näitest tuleneb peamine eesmärk algoritmi: kuna algoritm ei
tea, kas ülesanne on pikk või lühike, eeldab ta esialgu, et ülesanne
lühike ja annab sellele kõrgeima prioriteedi. Kui see on tõepoolest lühike ülesanne, siis
täidetakse see kiiresti, vastasel juhul, kui see on pikk ülesanne, siis see liikuda aeglaselt
madalamale prioriteedile ja tõestab peagi, et see on tõeliselt pikaajaline ülesanne, mis ei
nõua vastust.

Näide 3: Mis on sisendi ja väljundi kohta?

Vaadake nüüd näidet sisendi ja väljundi kohta. Nagu öeldi reeglites 4b,
kui protsess vabastab protsessori, kasutamata täielikult selle protsessoriaega,
siis jääb see endisele prioriteeditasemele. Selle reegli eesmärk on üsna lihtne
— kui interaktiivne ülesanne tegeleb paljude sisendi ja väljundi operatsioonidega, näiteks ootab
kasutajalt klahvivajutust või hiireklõpsu, vabastab see protsessori
enne ettenähtud akna lõppu. Me ei soovi seda ülesannet prioriteedi poolest langetada,
seega jääb see endisele tasemele.

See näide näitab, kuidas algoritm selliste protsessidega töötab — interaktiivne ülesanne B, mis vajab CPU-d ainult 1 ms enne
sisendi ja väljundi protsessi ning pikk ülesanne A, mis kasutab kogu oma aega CPU-d.
MLFQ hoiab ülesande B kõrgeimal prioriteedil, kuna see vabastab pidevalt
CPU-d. Kui B on interaktiivne ülesanne, saavutab algoritm sel juhul
oma eesmärgi käivitada interaktiivsed ülesanded kiiresti.

Praeguste MLFQ algoritmi probleemid

Eelmistes näidetes kirjutasime välja MLFQ põhilise versiooni. Ja tundub, et see
täidab oma tööd hästi ja õiglaselt, jaotades protsessor aega õiglaselt
pikemate ülesannete vahel ja lubades lühemate ülesannete või sisendi-väljundiintensiivsete
ülesannete töötada kiiresti. Kahjuks sisaldab see lähenemine mitmeid
tõsiseid probleeme.
Esiteks, nälja probleem: kui süsteemis on palju interaktiivseid
ülesandeid, siis nad tarbivad kogu protsessori aega ja seega ei saa ükski pikk
ülesanne kunagi töötama (nad nälgivad).

Teiseks, nutikad kasutajad võiksid kirjutada oma programme nii, et
petavad ajakava. Pettus seisneb selles, et teha midagi sellist, et sundida
ajakaavat andma protsessile rohkem protsessor aega. Algselt, mis
üle kirjeldatud on täiesti haavatav sarnaste rünnakute suhtes: enne aja akna praktiliselt lõppemist
tuleb teostada sisse-/väljundoperatsioon (mille tahes failiga, pole tähtis, millega)
ja seeläbi vabastada CPU. Selline käitumine võimaldab jääda samasse
järjekorda ja taas saada suuremat protsessoriaega. Kui seda teha
õigesti (näiteks töötada 99% ajast enne CPU vabastamist)
võib selline ülesanne lihtsalt protsessori monopoliseerida.

Lõpuks võib programm aja jooksul muuta oma käitumist. Need ülesanded,
mis kasutasid CPU-d, võivad muutuda interaktiivseteks. Meie näites sellised
ülesanded ei saa planeerijalt piisavat tähelepanu, nagu nad saaksid teised
(algse) interaktiivsed ülesanded.

Küsimus publikule: milliseid rünnakuid planeerijale oleks saanud kaasa teha tänapäeva maailmas?

Katse 2: Prioriteedi tõstmine

Proovime reegleid muuta ja vaatame, kas saame nälgimisprobleemidest kõrvale hiilida. Mida me saaksime teha, et tagada, et seotud
CPU ülesanded saavad oma aega (isegi kui mitte kaua).
Lihtsana lahendusena võib soovitada aeg-ajalt
kõigi selliste ülesannete prioriteedi tõstmist süsteemis. On mitmeid viise
selle saavutamiseks, proovime näitena midagi lihtsat: tõsta
korraga kõik ülesanded kõrgeimale prioriteedile, sealt uus reegel:
Reegel5

: Pärast teatud perioodi S tõsta kõik ülesanded süsteemis kõrgeimasse järjekorda.Meie uus reegel lahendab kaks probleemid korraga. Esiteks, protsessid

on garanteeritud, et nad ei näljuta: kõrgeima järjekorras olevad ülesanded jagavad
protsessoriaega RR algoritmi kohaselt, ja seega saavad kõik protsessid
protsessoriaega. Teiseks, kui mõni protsess, mis varem kasutas
ainult protsessorit, muutub interaktiivseks, jääb see järjekorda kõrgeima
prioriteediga pärast seda, kui see on kord saanud prioriteedi tõstetud kõrgeimale.
Vaadakem näidet. Selles stsenaariumis vaatleme ühte protsessi, mis kasutab
Vaadates näidet. Selles stsenaariumis vaatame ühte protsessi, mis kasutab

CPU ja kaks interaktiivset, lühikest protsessi. Vasakul pildil on kujutatud käitumist ilma prioriteedi tõstmiseta, mistõttu pikk ülesanne hakkab nälgima pärast kahe interaktiivse ülesande saabumist süsteemi. Pildil paremal tõstetakse prioriteeti iga 50 ms järel, mistõttu kõik protsessid saavad tagatud protsessoriaega ja neid käivitatakse perioodiliselt. 50 ms on antud juhul näitena, tegelikult on see number mõnevõrra suurem.
On ilmne, et perioodilise tõstmise S aja lisamine toob kaasa
loogilise küsimuse: milline väärtus peaks olema seatud? Üks tunnustatud
süsteeminseneridest John Ousterhout nimetas selliseid väärtusi süsteemides voo-doo
konstantideks, kuna nad nõudsid omamoodi musta maagia õiget
seadistamist. Ja kahjuks on S-l sarnane lõhn. Kui seada väärtus liiga
suureks — pikad ülesanded hakkavad nälgima. Ja kui seada liiga madal väärtus,
interaktiivsed ülesanded ei saa vajalikku protsessoriaega.

Katse 3: Parim arvestus

Nüüd on meil veel üks probleem, mida tuleb lahendada: kuidas mitte
lubada meie ajakava petta? Süüdlasteks on
reeglid 4a, 4b, mis võimaldavad ülesandel säilitada prioriteeti, vabastades protsessori
enne määratud aja lõppemist. Kuidas selle probleemiga toime tulla?
Lahenduseks võib olla parim CPU aja arvestus igal
MLFQ tasemel. Selle asemel, et unustada aega, mida programm kasutas
protsessor sealt antud ajavahemikul, tuleks arvestada ja salvestada see. Pärast seda, kui
protsess on kulutanud oma määratud aja, tuleks see alandada järgmisele
prioriteeditasemele. Nüüd ei ole oluline, kuidas protsess oma aega kasutab — kas
püsivalt protsessoril arvutades või kui hulk üleskutseid. Seega,
tuleb reegel 4 kirjutada järgmisesse vormi:

Rule4: Pärast seda, kui ülesanne on kulutanud talle määratud aega praeguses järjekorras (sõltumata sellest, mitu korda ta on protsessorit vabastanud), alandatakse selle ülesande prioriteeti (see liigub järjekorras allapoole).

Vaadakem näidet:
»

Pildil on näidatud, mis juhtub, kui proovida petta ajakava, nagu
kui vanade reeglitega 4a, 4b oleks saadud tulemus vasakul. Uue
reegli - tulemus paremal. Enne kaitset võis iga protsess põhjustada I/O enne lõpetamist ja
seega domineerida CPU-l, pärast kaitse aktiveerimist, olenemata I/O käitumisest,
langetatakse ta ikkagi järjekordade all ja seega ei saa ta ebaausalt
omanikuks saada CPU ressursse.

Parandame MLFQ-d ja teisi probleeme

Ülaltoodud täiustustega tekivad uued probleemid: üks peamine
küsimus on, kuidas sellist ajakava parameetriseerida? St. Kui palju peaks olema
järjekordi? Mis peaks olema programmi tööaeg järjekorra piires? Kui
tihti tuleks programmi prioriteeti tõsta, et vältida näljase seisundi teket ja
arvestada programmi käitumise muutumist? Need küsimused ei oma lihtsat
vastust ja ainult koormuse katsetamine ning järgnevad ajakava konfigureerimine
võivad viia rahuldava tasakaalu saavutamiseni.

Näiteks, enamik MLFQ teostusi võimaldab määrata erinevaid
ajakavasid erinevatele järjekordadele. Kõrge prioriteediga järjekordadele määratakse tavaliselt
lühemad ajavahemikud. Need järjekorrad koosnevad interaktiivsetest ülesannetest,
mille vahel vahetamine on üsna tundlik ja peaks kestma 10 või vähem
ms. Vastupidiselt madala prioriteediga järjekorrad koosnevad pikkadest ülesannetest, mis kasutavad
CPU-d. Ja sel juhul sobivad pikad ajavahemikud väga hästi (100 ms).

Selles näites on 2 ülesannet, mis töötasid kõrge prioriteediga järjekorras 20
ms, jagatud 10 ms akendeks. 40 ms keskmises järjekorras (aken 20 ms) ja madala prioriteediga
järjekorras on ajavahemik saanud 40 ms, kus ülesanded lõpetasid oma töö.

MLFQ teostus Solaris OS-is on ajakavade klass, mis jagavad aega.
Ajakava pakub komplekti tabeleid, mis määravad täpselt, kuidas protsessi prioriteet
eluea jooksul muutub, kui suur peab olema eraldatud aken ja kui tihti tuleb tõsta ülesande prioriteeti. Süsteemi
administraator võib selle tabeliga suhelda ja sundida ajakava käituma
teistmoodi. Vaikimisi on selles tabelis 60 järjekorda, mille akna suurus suureneb järk-järgult
20 ms (kõrge prioriteedi) kuni mitme sajani ms (madala prioriteedi), ja
akna suurust 20 ms (kõrge prioriteet) kuni mitme sajani ms (madalaim prioriteet), ja
ka kõiki ülesandeid sekundis.

Teised MLFQ ajakavade nimed ei kasuta tabelit või mingeid spetsiifilisi
reegleid, mis on kirjeldatud selles loengus, vastupidi, nad arvutavad prioriteedid, kasutades
matemaatilisi valemeid. Näiteks jaotab ajakava FreeBSD valemi
jooksva ülesande prioriteedi arvutamiseks tuginedes sellele, kui palju protsessor
kasutas CPU-d. Lisaks, CPU kasutamine aja jooksul laguneb, ja seega
prioriteedi tõstmine toimub veidi teistmoodi, kui ülaltoodud. Need on nii-öelda
lagunemise algoritmid. Alates versioonist 7.1 kasutab FreeBSD ajastust ULE.

Lõpuks, paljud ajakavad omavad muid omadusi. Näiteks, mõned
ajakavad reserveerivad kõrgeimad tasemed operatsioonisüsteemi töötamiseks ja seega
ei saa ükski kasutajaprotsess saada kõrgeimat prioriteeti
süsteemis. Mõned süsteemid võimaldavad anda näpunäiteid, et aidata
ajakava määrata prioriteete õigesti. Näiteks, käsu abil nice
on võimalik suurendada või vähendada ülesande prioriteeti ja seega tõsta või
alandada programmi võimalusi protsessorijaoks.

MLFQ: Kokkuvõte

Oleme kirjeldanud ajakava lähenemist, mida nimetatakse MLFQ. Selle nimi
peitub tööpõhimõttes - see sisaldab mitmeid järjekordi ja kasutab tagasisidet
ülesande prioriteedi määratlemiseks.
Reeglite lõplik nägemus on järgmine:

Reegel1: Kui prioriteet(A) > Prioriteet(B), käivitatakse ülesanne A (B ei käivitu)
Reegel2: Kui prioriteet(A) = Prioriteet(B), A ja B käivitatakse RR
Reegel3: Kui ülesanne tuleb süsteemi, paigutatakse see kõrgeima prioriteediga järjekorda.
Rule4: Pärast seda, kui ülesanne on kulutanud talle määratud aega praeguses järjekorras (sõltumata sellest, mitu korda ta on protsessorit vabastanud), alandatakse selle ülesande prioriteeti (see liigub järjekorras allapoole).
: Pärast teatud perioodi S tõsta kõik ülesanded süsteemis kõrgeimasse järjekorda.Meie uus reegel lahendab kaks probleemid korraga. Esiteks, protsessid

MLFQ on huvitav järgmise põhjuse tõttu - selle asemel, et nõuda ülesande
looduse eelnevat tundmist, uurib algoritm ülesande varasemaid käitumisi ja määrab
prioriteedid vastavalt. Nii proovib see istuda korraga kahel toolil - saavutada
tõhusust väikeste ülesannete jaoks (SJF, STCF) ja õiglaselt käivitada pikki,
CPU-d koormavaid ülesandeid. Seetõttu kasutavad paljud süsteemid, sealhulgas BSD ja nende derivatiivid,
Solaris, Windows, Mac, teatud vormi algoritmist MLFQ alusena.