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

Planeerimine: Mitme taseme tagasisidejärjekord

Selles loengus räägime ühest tuntumaid lähenemisviise
planeerimisele, mida nimetatakse Mitme taseme tagasisidejärjekord (MLFQ). MLFQ planeerijat kirjeldas esmakordselt 1962. aastal Fernando J. Corbató süsteemis, mida kutsuti
Ühilduv ajajagamise süsteem (CTSS). Need uuringud (sh hilisemad tööd
Multicsi üle) said hiljem Turingi auhinna.
Planeerijat on hiljem täiustatud ja sellel on nüüd juba selline välimus,
mida võib leida mõnedes kaasaegsetes süsteemides.

MLFQ algoritm üritab lahendada kahte põhilist, omavahel seotud probleemi.
Esiteks, püüdes optimeerida pöörderaega, mida, nagu me eelmisel loengul arutasime, optimeeritakse lühikeste ülesannete käivitamise meetodi abil järjekorra alguses.
Kuid OS ei tea, kui kaua iga protsess kestab, ja see on
teabeks vajalik, et SJF ja STCF algoritmid töötaksid. Teiseks, MLFQ püüab
muuta süsteemi kasutajatele vastuvõtlikuks (näiteks nende jaoks, kes istuvad ja
kümneid tunde ekraanil oodates, et ülesanne lõpetataks) ja seeläbi vähendada vastamisaega.
Kahjuks sellised algoritmid nagu RR vähendavad vastamisaega, kuid mõjuvad väga.
halvasti ringlusaegade metoodikale. Seetõttu on meie probleem: Kuidas kavandada
planeerimist, mis vastab meie nõuetele ja ei tea midagi nii-öelda protsessi olemusest?
Kuidas suudab planeerija õppida ülesannete omadusi,
mida ta käivitab, ja seeläbi teha paremaid otsuseid planeerimise osas?

Probleemi tuum: Kuidas planeerida ülesannete määramist, ilma et oleks ideaalset teadmist?
Kuidas luua planeerija, mis samal ajal minimeerib vastamisaega
interaktiivsete ülesannete jaoks ja minimeerib ringlusaega ilma eelneva
teadmiseta ülesande täitmise ajast?

Märkus: õpime varasemate sündmuste põhjal.

MLFQ järjekord on suurepärane näide süsteemist, mis õpib
möödunud sündmustest, et ennustada tulevikku. Selliseid lähenemisviise kasutatakse sageli
operatsioonisüsteemides (ja paljus muudes IT-sektorites, sealhulgas ennustuste harudes
riistvaras ja vahemälu algoritmid). Sellised lähenemisviisid
aktiveeruvad, kui ülesannete käitumisfaasid on olemas, muutes need seega ettearvatavaks.
Kuid sellise tehnika kasutamisel tuleb olla ettevaatlik, kuna ennustused võivad väga kergesti
osutuda valedeks ja viia süsteemi halvemate otsuste langetamiseni võrreldes sellega,
kui teadmisi üldse poleks.

MLFQ: Põhireeglid

Vaadakem üle MLFQ algoritmi põhireeglid. Kuigi selle algoritmi
rakendusi on mitmeid, põhialused on sarnased.
Selles rakenduses, mida me kaalume, on MLFQ-l mitu
erinevat järjekorda, igal neist erineva prioriteediga. Igal ajal,
ülesanne, mis on täitmiseks valmis, asub ühes järjekorras. MLFQ kasutab prioriteete,
et määrata, millisest ülesandest alustada, st ülesanne, millel on kõrgem
prioriteet (ülesanne kõrgeima prioriteediga järjekorrast) käivitatakse esimesena.
Muidugi võib konkreetses järjekorras olla rohkem kui üks ülesanne, nii et
nendel on sama prioriteet. Sellisel juhul kasutatakse plaanimist
RR mehhanismi nende ülesannete vahel.
Nii jõuame kahe põhireegli juurde, mis kehtivad MLFQ puhul:
Nii saavutame MLFQ jaoks kaks põhireeglit:

Reegel 1: Kui prioriteet(A) > prioriteet(B), käivitatakse ülesanne A (B ei käivitu).
Reegel 2: Kui prioriteet(A) = prioriteet(B), käivitatakse A ja B RR meetodil.

Eeltoodust lähtuvalt on MLFQ planeerimise võtmeelementideks
prioriteedid. Selle asemel, et määrata igale
ülesandele fikseeritud prioriteet, muutab MLFQ selle prioriteeti sõltuvalt jälgitavast käitumisest.
Näiteks, kui ülesanne pidevalt viibib CPU töölt ootamisel klaviatuurisisende jaoks,
hoiab MLFQ protsessi prioriteedikõrgel tasemel, kuna just nii
peab toimima interaktiivne protsess. Kuid kui ülesanne pidevalt ja
intensiivselt kasutab CPU-d pikka aega, madaldab MLFQ
selle prioriteeti. Sel viisil uurib MLFQ protsesside käitumist nende töö ajal
ja kohandab käitumist.
Joonistame näite, kuidas võiksid järjekorrad välja näha mingil hetkel
ja siis saame midagi sellist:

Antud skeemis on 2 protsessi A ja B kõrgeima prioriteedi järjekorras. Protsess
C on kuskil keskel ja protsess D järjekorra lõpus. Ülaltoodud kohaselt
MLFQ algoritmi kirjelduste kohaselt täidab ajakava ainult kõrgeima prioriteediga
ülesandeid RR järgi, samas kui ülesanded C, D jäävad kõrvale.
Ilmselt ei anna staatiline snapshot täielikku ülevaadet MLFQ toimimisest.
Oluline on mõista, kuidas pilt aja jooksul muutub.

Katse 1: Kuidas muuta prioriteeti

Sel hetkel tuleb otsustada, kuidas MLFQ muudab ülesande prioriteedi taset
(ja seega ülesande positsiooni järjekorras) ülesande elutsükli jooksul. Selle jaoks
on vajalik meeles pidada tööprotsessi: teatud hulk
interaktiivseid ülesandeid lühikese tööajaga (ja seega tihti CPU vabastades)
ja mõned pikad ülesanded, mis kasutavad CPU kogu oma tööaja, samas
kui vastamise aeg sellistele ülesannetele ei ole oluline. Seega saab teha esimese katse
rakendada MLFQ algoritmi järgmiste reeglitega:

Reegel 3: Kui ülesanne siseneb süsteemi, asetatakse see kõrgeima prioriteediga järjekorda.
Reegel 4a: Kui ülesanne kasutab täielikult ette nähtud ajavahemikku, siis selle
prioriteet langetatakse.
Reegel 4b: Kui ülesanne vabastab CPU enne oma ajavahemiku lõppu, siis see
Reegel 4b: Kui Ülesanne vabastab CPU enne oma ajaraami lõppu, siis
jääb endiselt samaks prioriteediks.

Näide 1: Üksik pikalt töötav ülesanne

Nagu näha sel näitel, seatakse ülesanne saabumisel kõrgeimale
prioriteedile. Pärast ajavahemikku 10 ms protsess langeb prioriteedis
planeerija poolt. Pärast järgmist ajavahemikku langeb ülesanne lõpuks
süsteemi madalaimale prioriteedile, kus see jääbki.

Näide 2: Lühikese ülesande saabumine

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

Sellel graafikul on näha stsenaariumi tulemused. Ülesanne A, nagu iga ülesanne,
mis kasutab CPU-d, oli kõige madalamal. Ülesanne B saabub ajal T=100 ja
paigutatakse kõrgema prioriteediga järjekorda. Kuna selle tööaeg on lühike,
võtab see lõpetamiseks aega enne, kui jõuab viimasesse järjekorda.

Sellest näitest järeldub, et algoritmi peamine eesmärk on: kuna algoritm ei
kui ülesanne on pikk või lühike, siis eeldab ta esmajoones, et ülesanne
on lühike ja annab sellele kõrgeima prioriteedi. Kui see tõepoolest on lühike ülesanne, siis
täidetakse see kiiresti; vastasel juhul, kui see on pikk ülesanne, liigub see aeglaselt
prioriteedis alla ja tõestab peagi, et tegemist on tõeliselt pika ülesandega, mis ei
nõua reageerimist.

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

Vaatame nüüd näidet sisendi ja väljundi kohta. Nagu on öeldud reeglis 4b,
kui protsess vabastab protsessori, ei kasuta ta täielikult selle protsessoriaega,
siis jääb ta endisele prioriteedile. Selle reegli mõte on üsna lihtne
— kui interaktiivne ülesanne teeb palju sisendi-väljundi operatsioone, näiteks ootab
kasutaja klahvivajutusi või hiireklikke, vabastab see protsessori
varasemalt määratud aknast. Me ei sooviks seda ülesannet prioriteedis alandada,
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 täitmist.
sisend-väljund protsessi ja pika A ülesande, mis kasutab kogu oma aega CPU-d.
MLFQ hoiab protsessi B kõrgeima prioriteediga, kuna see jätkab
CPU vabastamist. Kui B on interaktiivne ülesanne, on algoritm siis saavutanud
oma eesmärgi käivitada interaktiivsed ülesanded kiiresti.

Probleemid praeguse MLFQ algoritmiga

Eelmistes näidetes oleme loonud MLFQ põhiversiooni. Ja tundub, et see
täidab oma tööd hästi ja õiglaselt, jagades protsessoriaega õiglaselt pika
ülesande vahel ning võimaldades lühikestel või sisend-väljundit intensiivselt
kasutavatel ülesannetel kiiresti töötada. Kahjuks sisaldab selline lähenemine mitmeid
tõsiseid probleeme.
Esiteksnälja probleem: kui süsteemis on rohkelt interaktiivseid
ülesandeid, siis tarbivad need kogu protsessoriaega ja seega ei saa ükski pikk
ülesanne võimalust täituda (nad nälgivad).

TeiseksNutikaid kasutajaid võiks kirjutada oma programme nii, et
petta planeerijat. Petmine seisneb millegi sellise tegemises, et sundida
plaanija annab protsessile rohkem protsessoriaega. Algoritm, mis
on eespool kirjeldatud, on sarnaste rünnakute suhtes üsna haavatav: enne
selle ajavahemiku lõppu on vaja sooritada sisendi- või väljundioperatsioon (millele iganes, pole tähtis millele)
ja seeläbi vabastada CPU. Selline käitumine võimaldab jääda samasse
järjekorda ja taas saada suuremat protsessoriteenuse osa. Kui seda teha
korrektne (näiteks täita 99% ajast enne CPU vabastamist),
võib selline ülesanne lihtsalt monopoliseerida protsessori.

Lõpuks võib programm aja jooksul muuta oma käitumist. Need ülesanded,
mis kasutasid CPU-d, võivad muutuda interaktiivseteks. Meie näites ei saa sellised
ülesanded planeerijalt korralikku tähelepanu, kuna nad saaksid teisi
(algseid) interaktiivseid ülesandeid.

Küsimus saalist: milliseid rünnakuid planeerija vastu oli võimalik kaasaegses maailmas teha?

Katse 2: Prioriteedi tõstmine

Proovime reegleid muuta ja vaatame, kas suudame vältida nälgimisega seotud probleeme. Mida me saaksime teha, et tagada, et seotud
nälgimisest. Mida saaksime teha, et tagada, et seotud
CPU ülesanded saavad oma aega (isegi kui see ei ole kaua).
Lihtsaks lahenduseks probleemile võib olla perioodiline
kõigi selliste ülesannete süsteemi prioriteedi tõstmine. On mitmeid viise
selle saavutamiseks, proovime näitena rakendada midagi lihtsat: tõsta
kõik ülesanded kõrgeimasse prioriteeti, seega uus reegel:

Reegel5: Teatud perioodi möödumisel tõsta kõik süsteemi ülesanded kõrgeimasse ootejärjekorda.

Meie uus reegel lahendab kahe probleemi korraga. Esiteks, protsessid
ei jää kindlasti nälga: ülesanded, mis on kõrgeimas ootejärjekorras, jagavad
protsessoriaega RR-algoritmi alusel ja seega saavad kõik protsessid
protsessoriaega. Teiseks, kui mõni protsess, mis varem kasutas
ainult protsessorit, muutub interaktiivseks, siis jääb see ootejärjekorda kõrgeima
prioriteediga pärast seda, kui on korra saanud tõstmise kõrgeimaks.
Vaatame näidet. Selles stsenaariumis vaatame ühte protsessi, mis kasutab

CPU ja kaks interaktiivset, lühikest protsessi. Vasakul joonisel on kujutatud käitumist ilma prioriteedi tõstmiseta, mistõttu pikk ülesanne hakkab süsteemi saabudes kahe interaktiivse ülesande tõttu nälgima. Paremal joonisel tõstetakse prioriteeti iga 50 ms järel, tagades, et kõik protsessid saavad garanteeritud protsessori aega ja neid käivitatakse perioodiliselt. 50 ms on antud juhul näitena, tegelikult on see number veidi suurem.
On selge, et perioodilise tõstmise S lisamine toob kaasa
kahtlemata küsimuse: milliseks väärtuseks see peaks olema seadistatud? Üks mainekas
süsteemitehnik John Ousterhout nimetas selliseid suurusi süsteemides voo-doo
konstantideks, kuna nende õigeks seadmiseks oli vajalik teatud määral musta maagiat.
Ja kahjuks on S-l selline iseloom. Kui seada väärtus liiga
suurena, hakkavad pikad ülesanded nälgima. Kui seada liiga madalaks,
ei saa interaktiivsed ülesanded vajalikku protsessori aega.

Katse 3: Parim arvestus

Nüüd on meil veel üks probleem, mida lahendada: kuidas mitte
lubada meie planeerijat petta? Süüdlased selle võimaluse eest on
reeglid 4a, 4b, mis lubavad ülesandel säilitada prioriteeti, vabastades protsessori
enne määratud aja lõppu. Kuidas sellega toime tulla?
Lahendusena võib kiita parimat CPU ajahaldust iga MLFQ taseme korral.
Selle asemel, et unustada, kui palju aega programm protsessorit kasutas
mütsitud aja jooksul, tuleks seda arvesse võtta ja säilitada. Pärast seda, kui
protsess on kasutanud talle antud aega, tuleks selle prioriteeti madaldada järgmisele
tasemele. Nüüd ei ole oluline, kuidas protsess oma aega kasutab — kas
pidevalt protsessoril arvutades või mitmete kutsetega. Seega,
tuleb reegel 4 ümber kirjutada järgmise kujul:

Rule4: Pärast seda, kui ülesanne on kasutanud talle määratud aega praeguses järjekorras (olgu see kui mitu korda ta CPU-d vabastas) selle ülesande prioriteet väheneb (ta liigub järjekorras allapoole).

Vaatame näidet:
»

Kujutisel on näidatud, mis juhtub, kui proovida petta ajakava, nagu
oleks eelnevate reeglite 4a ja 4b puhul, tulemuseks oleks vasakul. Uue
reegliga — tulemus on paremal. Enne kaitset võis iga protsess kutsuda I/O ülesandeid kuni lõpetamiseni ja
seega domineerida CPU-l, pärast kaitse sisselülitamist, sõltumata I/O käitumisest,
ta jääb ikka sabasse ja seega ei saa ebaausalt
ressursse CPU-lt haarata.

Parandame MLFQ ja teised probleemid

Ülaltoodud täiustustega tekivad uued probleemid: üks peamisi
küsimusi on, kuidas sarnast ajakava parameetrites määrata? St. kui palju peaks olema
järjekordi? Milline peaks olema programmi töö akna suurus järjekorras? Kui
tihti tuleks programmi prioriteeti tõsta, et vältida nälgimist ja
arvesse võtta programmi käitumise muutumist? Neile küsimustele ei ole lihtsat
vastust ja ainult koormust eksperimentide ning järgnev konfigureerimine
ajakava võib viia mõningasse rahuldavasse tasakaalu.

Näiteks võimaldavad enamik MLFQ rakendusi määrata erinevaid
ajava ajava intervallid erinevatele järjekordadele. Kõrge prioriteediga järjekordadele määratakse tavaliselt
lühi intervallid. Need järjekorrad koosnevad interaktiivsest ülesandest,
mille vahetus on üsna tundlik ja peaks võtma 10 või vähem
ms. Vastupidiselt madala prioriteediga järjekorrad koosnevad pikkadest ülesannetest, mis kasutavad
CPU-d. Ja sel juhul sobivad pikad ajaintervallid väga hästi (100 ms).

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

MLFQ rakendamine Solaris OS-is — ajaplaneerijate klassid, mis jagunevad ajaliselt.
Ajaplaneerija pakub komplekti tabeleid, mis määravad täpselt, kuidas peaks
protsessi prioriteet muutuma tema elu jooksul, kui suur peaks olema akna
eraldatud suurus ja kui sageli tuleb tõsta ülesande prioriteete. Süsteemi
administraator võib selle tabeliga suhelda ja sundida ajaplaneeritavat käituma
teisiti. Vaikimisi on selles tabelis 60 järjekorda, mis aeglaselt suurenevad
akna suurusest 20 ms (kõrge prioriteet) kuni mitme sada ms (madalam prioriteet), ja
samuti kõigi ülesannete tõukamine kord sekundis.

Teised MLFQ ajakavajad kasutavad ei tabeleid ega konkreetseid
reegleid, nagu selles loengus kirjeldatud, vastupidi, nad arvutavad prioriteedid, kasutades
matemaatilisi valemeid. Näiteks FreeBSD ajakavaja kasutab valemit
praeguse ülesande prioriteedi arvutamiseks, tuginedes sellele, kui palju protsessor
on CPU-d kasutanud. Lisaks, CPU kasutamine aja jooksul laguneb ja seega
prioriteedi tõstmine toimub mõnevõrra erinevalt, kui eespool kirjeldatud. Need on nii
nn decay algoritmid. Alates versioonist 7.1 kasutatakse FreeBSD-s ULE ajakavajat.

Lõpuks on paljudel ajakavajatel teised omadused. Näiteks mõned
ajakavajad reserveerivad kõrgemad tasemed operatsioonisüsteemi jaoks ja seega
ei saa ükski kasutaja protsess süsteemis kõrgeimat prioriteeti.
Mõned süsteemid võimaldavad anda soovitusi, et aidata
korraldada ülesannete prioriteete. Näiteks käsu abil nice
saab suurendada või vähendada ülesande prioriteeti ja seega tõsta või
langetada programmi võimalusi protsessoriaja saamiseks.

MLFQ: Kokkuvõte

Oleme kirjeldanud planeerimismeetodit, mida nimetatakse MLFQ. Selle nimi
peitub tööpõhimõttes — tal on mitu järjekorda ja ta kasutab tagasisidet
ülesande prioriteedi määramiseks.
Lõplik reeglite kuju on järgmine:

Reegel1: Kui prioriteet(A) > Prioriteet(B), käivitatakse ülesanne A (B ei käivitata)
Reegel2: Kui prioriteet(A) = Prioriteet(B), A ja B käivitatakse RR kasutades
Reegel3: Kui ülesanne jõuab süsteemi, asetatakse see kõrgeima prioriteediga järjekorda.
Rule4: Pärast seda, kui ülesanne on kasutanud talle määratud aega praeguses järjekorras (olgu see kui mitu korda ta CPU-d vabastas) selle ülesande prioriteet väheneb (ta liigub järjekorras allapoole).
Reegel5: Teatud perioodi möödumisel tõsta kõik süsteemi ülesanded kõrgeimasse ootejärjekorda.

MLFQ on huvitav järgmise põhjuse tõttu — selle asemel, et nõuda eelnevat teadmiste omamist
ülesande loomusest, õpib algoritm ülesande varasemat käitumist ja määrab
prioriteedid vastavalt. Nii püüab ta istuda kahes paadis — saavutada tõhusust väikeste ülesannete puhul (SJF, STCF) ja õiglaselt käivitada pikaid,
protsessorit koormavaid ülesandeid. Seetõttu on paljud süsteemid, sealhulgas BSD ja nende tuletised,
Solaris, Windows ja Mac kasutavad ajakava koostamiseks mingit tüüpi algoritmi.
MLFQ kui põhiline alus.