Įvadas į operacines sistemas
Sveiki, Habr! Norėčiau atkreipti jūsų dėmesį į vienos, mano nuomone, įdomios literatūros - OSTEP - straipsnių-vertimų ciklą. Šioje medžiagoje gana nuodugniai aptariamas į unix panašių operacinių sistemų darbas, būtent darbas su procesais, įvairiais planuokliais, atmintimi ir kitais panašiais komponentais, kurie sudaro šiuolaikinę OS. Visų medžiagų originalus galite pamatyti čia . Atkreipkite dėmesį, kad vertimas atliktas neprofesionaliai (gana laisvai), bet tikiuosi, kad išlaikiau bendrą prasmę.
Laboratorinius darbus šia tema galite rasti čia:
Kitos dalys:
Taip pat galite peržiūrėti mano kanalą adresu =)
Planavimas: kelių lygių atsiliepimų eilė
Šioje paskaitoje kalbėsime apie vieno žinomiausių požiūrių kūrimo problemas
planavimas, kuris vadinamas Kelių lygių atsiliepimų eilė (MLFQ). MLFQ planuoklį pirmą kartą 1962 m. aprašė Fernando J. Corbató sistemoje, vadinamoje
Suderinama laiko pasidalijimo sistema (CTSS). Šie darbai (įskaitant vėlesnį darbą
Multics) vėliau buvo nominuoti Turingo apdovanojimui. Planuotojas buvo
vėliau patobulinta ir įgavo tokią išvaizdą, kokią jau galima rasti
kai kurios šiuolaikinės sistemos.
MLFQ algoritmas bando išspręsti 2 esmines persidengiančias problemas.
Pirma, ji bando optimizuoti apyvartos laiką, kuris, kaip aptarėme ankstesnėje paskaitoje, optimizuojamas tokiu būdu, kad daugiausia pradedama eilės pradžioje
trumpos užduotys. Tačiau OS nežino, kiek laiko veiks konkretus procesas, ir tai
reikalingų žinių SJF, STCF algoritmų veikimui. Antra, MLFQ bando
kad sistema reaguotų vartotojams (pavyzdžiui, tiems, kurie sėdi ir
žiūrėti į ekraną ir laukti, kol užduotis bus baigta) ir taip sumažinti laiką
atsakymą. Deja, tokie algoritmai kaip RR pagerina reakcijos laiką, bet nepaprastai
turi neigiamos įtakos apyvartos laiko metrikai. Taigi mūsų problema: kaip kurti
planuotojas, kuris atitiks mūsų reikalavimus nieko nežinodamas
proceso pobūdis apskritai? Kaip planuotojas gali išmokti užduočių ypatybes,
kurią ji paleidžia ir taip priimti geresnius planavimo sprendimus?
Problemos esmė: Kaip planuoti užduočių nustatymą neturint tobulų žinių?
Kaip sukurti planuotoją, kuris tuo pačiu sumažintų atsako laiką
interaktyvioms užduotims atlikti ir tuo pat metu nežinant sumažina apyvartos laiką
žinios apie užduoties vykdymo laiką?
Pastaba: mokomės iš ankstesnių įvykių
MLFQ eilė yra puikus sistemos, iš kurios mokomasi, pavyzdys
praeities įvykiai nuspėti ateitį. Panašūs metodai yra dažnai
rasta OS (ir daugelyje kitų kompiuterių mokslo šakų, įskaitant filialus
aparatinės įrangos prognozės ir talpyklos algoritmai). Panašios kelionės
suveikia, kai užduotys turi elgesio fazes ir todėl yra nuspėjamos.
Tačiau turėtumėte būti atsargūs naudodami šią techniką, nes prognozuoti labai paprasta
gali pasirodyti neteisinga ir paskatinti sistemą priimti blogesnius sprendimus nei
būtų visai be žinių.
MLFQ: pagrindinės taisyklės
Pažvelkime į pagrindines MLFQ algoritmo taisykles. Ir nors šio algoritmo įgyvendinimai
Yra keletas, pagrindiniai metodai yra panašūs.
Diegiant, kurį apžvelgsime, MLFQ turės keletą
atskiros eilės, kurių kiekviena turės skirtingą prioritetą. bet kada,
užduotis, paruošta vykdyti, yra vienoje eilėje. MLFQ naudoja prioritetus,
nuspręsti, kurią užduotį vykdyti, t.y. užduotis su aukštesniu
prioritetas (užduotis iš eilės su didžiausiu prioritetu) bus paleista pirmiausia
eilė.
Žinoma, tam tikroje eilėje gali būti daugiau nei viena užduotis, taigi
todėl jie turės tą patį prioritetą. Tokiu atveju bus naudojamas mechanizmas
RR, kad suplanuotų šių užduočių vykdymą.
Taigi pasiekiame dvi pagrindines MLFQ taisykles:
- 1 taisyklė: jei prioritetas (A) > prioritetas (B), A užduotis bus paleista (B ne)
- 2 taisyklė: jei prioritetas (A) = prioritetas (B), A&B pradedami naudoti naudojant RR
Remiantis tuo, kas išdėstyta pirmiau, pagrindiniai MLFQ planavimo elementai
yra prioritetai. Užuot suteikę kiekvienam fiksuotą prioritetą
užduotį, MLFQ keičia savo prioritetą, priklausomai nuo stebimo elgesio.
Pvz., jei užduotis nuolat apkrauna CPU, kol laukiama klaviatūros įvesties,
MLFQ išlaikys aukštą proceso prioritetą, nes taip
interaktyvus procesas turėtų veikti. Jei priešingai – užduotis nuolat ir
ilgą laiką naudoja daug procesoriaus, MLFQ jį sumažins
prioritetas. Taigi, MLFQ tirs procesų elgesį jiems veikiant
ir naudoti elgesį.
Nubraižykime pavyzdį, kaip tam tikru momentu gali atrodyti eilės
laiko ir tada gausite kažką panašaus:
Šioje schemoje 2 procesai A ir B yra aukščiausio prioriteto eilėje. Procesas
C yra kažkur viduryje, o procesas D yra pačiame eilės gale. Remiantis aukščiau
Pagal MLFQ algoritmo aprašymus, planuotojas vykdys užduotis tik su aukščiausia
prioritetas pagal RR, o užduotys C, D bus nedarbingos.
Natūralu, kad statinis momentinis vaizdas nepateiks išsamaus vaizdo apie tai, kaip veikia MLFQ.
Svarbu tiksliai suprasti, kaip vaizdas keičiasi laikui bėgant.
1 bandymas: kaip pakeisti prioritetą
Šiuo metu turite nuspręsti, kaip MLFQ pakeis prioriteto lygį
užduotis (taigi ir užduoties vietą eilėje), kai ji vyksta per savo gyvavimo ciklą. Dėl
tai būtina norint nepamiršti darbo eigos: tam tikra suma
interaktyvios užduotys su trumpu vykdymo laiku (taigi ir dažnai išleidžiamos
CPU) ir kelios ilgai vykdomos užduotys, kurioms CPU naudojamas visą darbo laiką
Reagavimo laikas tokioms užduotims nėra svarbus. Ir tokiu būdu galite pirmą kartą išbandyti
Įdiekite MLFQ algoritmą pagal šias taisykles:
- 3 taisyklė: kai užduotis patenka į sistemą, ji įtraukiama į eilę su aukščiausia
- prioritetas.
- 4a taisyklė: jei užduotis naudoja visą jai skirtą laiko langą, tada ji
- prioritetas sumažinamas.
- 4b taisyklė: Jei užduotis atleidžia centrinį procesorių nepasibaigus jos laiko langui, tada ji
- išlieka ta pačia pirmenybe.
1 pavyzdys: Viena ilgai trunkanti užduotis
Kaip matyti iš šio pavyzdžio, priėmimo užduotis nustatoma su aukščiausia
prioritetas. Pasibaigus 10 ms laiko langui, proceso prioritetas sumažinamas
planuotojas. Po kito laiko lango užduotis pagaliau pažeminama į
žemiausias prioritetas sistemoje, kur jis išlieka.
2 pavyzdys: atliko trumpą užduotį
Dabar pažiūrėkime, kaip MLFQ bandys priartėti prie SJF. Tuo
Pavyzdžiui, dvi užduotys: A, kuri yra ilgai trunkanti užduotis
užima CPU ir B, o tai yra trumpa interaktyvi užduotis. Tarkime
kad A jau kurį laiką dirbo, kol atėjo užduotis B.
Šioje diagramoje rodomi scenarijaus rezultatai. A užduotis, kaip ir bet kuri užduotis,
CPU naudojimas buvo pačiame apačioje. Užduotis B atvyks laiku T=100 ir bus
patalpintas į aukščiausio prioriteto eilę. Kadangi jo veikimo laikas trumpas, tada
jis bus baigtas nepasiekus paskutinės eilės.
Iš šio pavyzdžio reikėtų suprasti pagrindinį algoritmo tikslą: kadangi algoritmas to nedaro
žino, ar užduotis ilga, ar trumpa, tada pirmiausia daro prielaidą, kad užduotis
trumpas ir suteikia jam didžiausią prioritetą. Jei tai tikrai trumpa užduotis, tada
ji bus atlikta greitai, kitaip jei tai ilga užduotis, ji judės lėtai
prioritetas žemyn ir netrukus įrodys, kad ji iš tiesų yra ilga užduotis, kuri to nedaro
reikalauja atsakymo.
3 pavyzdys: O kaip I/O?
Dabar pažiūrėkime į I/O pavyzdį. Kaip nurodyta 4b taisyklėje,
jei procesas atleidžia procesorių nepanaudodamas viso procesoriaus laiko,
tada jis išlieka tame pačiame prioriteto lygyje. Šios taisyklės tikslas yra gana paprastas
- jei interaktyvus darbas atlieka daug I/O operacijų, pavyzdžiui, laukia
nuo vartotojo klavišo ar pelės paspaudimų tokia užduotis atlaisvins procesorių
prieš skirtą langą. Nenorėtume sumažinti tokios užduoties prioriteto,
ir taip jis išliks tame pačiame lygyje.
Šiame pavyzdyje parodyta, kaip algoritmas veiks su tokiais procesais – interaktyvi užduotis B, kuriai CPU reikia tik 1 ms prieš vykdymą
Įvesties / išvesties procesas ir ilgai veikiantis darbas A, kuris visą laiką praleidžia naudodamas centrinį procesorių.
MLFQ proceso B prioritetas yra aukščiausias, nes jis tęsiasi
atleiskite CPU. Jei B yra interaktyvi užduotis, tada algoritmas pasiektas
Jūsų tikslas yra greitai atlikti interaktyvias užduotis.
Problemos su dabartiniu MLFQ algoritmu
Ankstesniuose pavyzdžiuose sukūrėme pagrindinę MLFQ versiją. Ir atrodo, kad jis
gerai ir sąžiningai atlieka savo darbą, teisingai paskirstydamas procesoriaus laiką
ilgas užduotis ir leidžiant trumpas arba didelės apimties užduotis
greitai dirbti su I/O. Deja, šis metodas apima keletą
rimtų problemų.
Pirma, bado problema: jei sistemoje yra daug interaktyvių
užduotis, tada jie sunaudos visą procesoriaus laiką, taigi, ilgą laiką ne vieną
užduoties nepavyks įvykdyti (jie badauja).
Antra, protingi vartotojai galėtų parašyti savo programas taip
apgauti planuotoją. Apgaulė slypi darant kažką priversti
Planavimo priemonė suteikia procesui daugiau procesoriaus laiko. Algoritmas, kad
aukščiau aprašytas yra gana pažeidžiamas panašių atakų: prieš laiko langą praktiškai
pasibaigė, turite atlikti įvesties / išvesties operaciją (kai kuriems, nesvarbu, koks failas)
ir taip atlaisvinti procesorių. Toks elgesys leis išlikti tame pačiame
pati eilė ir vėl gausite didesnį procesoriaus laiko procentą. Jei taip
tai teisinga (pavyzdžiui, prieš atleidžiant centrinį procesorių paleiskite 99% lango laiko),
tokia užduotis gali tiesiog monopolizuoti procesorių.
Galiausiai programa gali pakeisti savo elgesį laikui bėgant. Tos užduotys
kuris naudojo centrinį procesorių, gali tapti interaktyvus. Mūsų pavyzdyje panašiai
užduočių planuotojas nesulauks tokio gydymo, kokio jos nusipelnė, kaip tai darytų kiti
(pradinės) interaktyvios užduotys.
Klausimas auditorijai: kokios atakos prieš planuotoją galėtų būti įvykdytos šiuolaikiniame pasaulyje?
2 bandymas: prioriteto didinimas
Pabandykime pakeisti taisykles ir pažiūrėkime, ar galime išvengti problemų
pasninkas. Ką galime padaryti, kad tai būtų susiję
CPU užduotys skirs savo laiką (net jei neilgai).
Kaip paprastą problemos sprendimą galite periodiškai pasiūlyti
pakelti visų tokių užduočių prioritetą sistemoje. Yra daug būdų
Norėdami tai pasiekti, pabandykime įgyvendinti ką nors paprasto kaip pavyzdį: išversti
visoms užduotims iš karto suteikiamas aukščiausias prioritetas, todėl nauja taisyklė:
- 5 taisyklė: Po tam tikro laikotarpio S perkelkite visas sistemos užduotis į aukščiausią eilę.
Mūsų nauja taisyklė išsprendžia dvi problemas vienu metu. Pirma, procesai
garantuotai nemirs badu: bus paskirstytos užduotys, kurioms teikiamas didžiausias prioritetas
CPU laikas pagal RR algoritmą ir taip bus gauti visi procesai
CPU laikas. Antra, jei anksčiau naudotas procesas
tik procesorius tampa interaktyvus, jis liks eilėje su didžiausiu
pirmenybę gavus vienkartinį prioriteto padidinimą iki aukščiausio.
Pažiūrėkime į pavyzdį. Pagal šį scenarijų apsvarstykite vieną procesą
CPU ir du interaktyvūs, trumpi procesai. Paveikslo kairėje pusėje parodytas elgesys be prioritetinio paaukštinimo, todėl ilgai vykdoma užduotis pradeda badauti po dviejų interaktyvių užduočių pateikimo į sistemą. Paveikslėlyje dešinėje prioritetas didinamas kas 50 ms, todėl garantuojama, kad visi procesai gaus procesoriaus laiką ir bus periodiškai paleisti. 50 ms šiuo atveju imamas kaip pavyzdys; iš tikrųjų šis skaičius yra šiek tiek didesnis.
Akivaizdu, kad pridedant periodinį padidėjimo laiką S
logiškas klausimas: kokia vertė turėtų būti nustatyta? Vienas iš pagerbtųjų
sistemų inžinieriai Johnas Ousterhoutas tokius sistemose kiekius pavadino voo-doo
pastovus, nes tam tikru būdu jiems reikėjo juodosios magijos
eksponuojant. Ir, deja, S turi tokį kvapą. Jei nustatysite ir vertę
didelės – ilgos užduotys pradės badauti. Ir jei nustatote per mažą vertę,
Interaktyvios užduotys negaus tinkamo procesoriaus laiko.
3 bandymas: geresnė apskaita
Dabar turime išspręsti kitą problemą: kaip to nedaryti
leisti apgauti mūsų planuotoją? Dėl šios galimybės kalti žmonės
4a, 4b taisyklės, kurios leidžia darbui išlaikyti prioritetą, atlaisvinant procesorių
nepasibaigus nustatytam laikui. Kaip su tuo susitvarkyti?
Šiuo atveju sprendimas gali būti laikomas geresniu kiekvieno procesoriaus laiko apskaita
MLFQ lygis. Užuot pamiršę programos naudojimo laiką
procesoriaus skirtą laikotarpį, į jį reikia atsižvelgti ir išsaugoti. Po to
procesas išnaudojo jam skirtą laiką, jis turėtų būti perkeltas į kitą
prioriteto lygis. Dabar nesvarbu, kaip procesas išnaudos savo laiką – kaip
nuolat skaičiuoja procesoriuje arba kaip skambučių skaičius. Taigi,
4 taisyklė turėtų būti perrašyta į tokią formą:
- 4 taisyklė: kai užduotis išnaudoja jai skirtą laiką dabartinėje eilėje (nesvarbu, kiek kartų ji atlaisvino centrinį procesorių), tos užduoties prioritetas sumažinamas (ji juda eilėje žemyn).
Pažiūrėkime į pavyzdį:
»
Paveikslėlyje parodyta, kas atsitiks, jei bandysite apgauti planuotoją, pvz
jei būtų pagal ankstesnes taisykles 4a, 4b, rezultatas būtų gautas kairėje pusėje. Laimingas naujas
taisyklė yra rezultatas dešinėje. Prieš apsaugą bet koks procesas gali iškviesti įvesties / išvesties funkciją prieš baigdamas ir
tokiu būdu dominuoja CPU, įjungus apsaugą, nepriklausomai nuo elgesio
I/O, jis vis tiek judės eilėje žemyn, todėl negalės nesąžiningai
perimti procesoriaus išteklius.
MLFQ ir kitų problemų tobulinimas
Dėl minėtų patobulinimų atsiranda naujų problemų: viena iš pagrindinių
Klausimai – kaip tokį planuoklį parametrizuoti? Tie. Kiek turėtų būti
eilės? Koks turėtų būti programos lango dydis eilėje? Kaip
Programos prioritetas dažnai turėtų būti padidintas, kad būtų išvengta bado ir
atsižvelgti į programos elgesio pokyčius? Į šiuos klausimus paprasto atsakymo nėra
atsakymas ir tik eksperimentai su apkrovomis ir vėlesne konfigūracija
planuotojas gali pasiekti tam tikrą patenkinamą pusiausvyrą.
Pavyzdžiui, dauguma MLFQ diegimų leidžia priskirti skirtingus
laiko intervalai skirtingoms eilėms. Aukšto prioriteto eilės paprastai
nustatomi trumpi intervalai. Šios eilės susideda iš interaktyvių užduočių,
kurių perjungimas yra gana jautrus ir turėtų trukti 10 ar mažiau
ms. Priešingai, žemo prioriteto eiles sudaro ilgai vykdomos užduotys, kurios naudojamos
CPU. Ir šiuo atveju labai tinka ilgi laiko intervalai (100ms).
Šiame pavyzdyje yra 2 užduotys, kurios veikė didelio prioriteto 20 eilėje
ms, padalintas į 10 ms langus. 40 ms vidurinėje eilėje (langas 20 ms) ir žemo prioriteto
Eilės laiko langas tapo 40 ms, kai užduotys baigė savo darbą.
Solaris OS MLFQ diegimas yra laiko pasidalijimo planuotojų klasė.
Planuotojas pateiks lentelių rinkinį, kuris tiksliai apibrėžia taip, kaip turėtų
proceso prioritetas keičiasi jo gyvavimo eigoje, koks turėtų būti dydis
paskirstytas langas ir kaip dažnai reikia pakelti užduočių prioritetus. Administratorius
sistemos gali sąveikauti su šia lentele ir priversti planuotoją veikti
kitaip. Pagal numatytuosius nustatymus šioje lentelėje yra 60 eilių, kurios palaipsniui didėja
lango dydis nuo 20 ms (aukštas prioritetas) iki kelių šimtų ms (žemas prioritetas) ir
taip pat kartą per sekundę padidinus visas užduotis.
Kiti MLFQ planuotojai nenaudoja lentelės ar jokio konkretaus
taisyklės, kurios aprašytos šioje paskaitoje, priešingai, jos apskaičiuoja prioritetus naudodamos
matematines formules. Pavyzdžiui, FreeBSD planuoklis naudoja formulę
apskaičiuokite esamą užduoties prioritetą pagal proceso trukmę
naudotas CPU. Be to, procesoriaus naudojimas laikui bėgant mažėja ir pan
Taigi prioriteto didinimas vyksta kiek kitaip, nei aprašyta aukščiau. Tai yra tiesa
vadinami skilimo algoritmais. Nuo 7.1 versijos FreeBSD naudojo ULE planuoklį.
Galiausiai, daugelis planuotojų turi kitų funkcijų. Pavyzdžiui, kai kurie
planuotojai pasilieka aukščiausius lygius operacinės sistemos veikimui ir taip
Taigi joks vartotojo procesas negali gauti didžiausio prioriteto
sistema. Kai kurios sistemos leidžia jums patarti, kaip padėti
planuotojas gali teisingai nustatyti prioritetus. Pavyzdžiui, naudojant komandą gražus
galite padidinti arba sumažinti užduoties prioritetą ir taip padidinti arba
sumažinti programos galimybes panaudoti procesoriaus laiką.
MLFQ: Santrauka
Aprašėme planavimo metodą, vadinamą MLFQ. Jo vardas
uždaras veikimo principu – turi keletą eilių ir naudoja grįžtamąjį ryšį
nustatyti užduoties prioritetą.
Galutinė taisyklių forma bus tokia:
- 1 taisyklė: jei prioritetas (A) > prioritetas (B), A užduotis bus paleista (B ne)
- 2 taisyklė: Jei prioritetas (A) = prioritetas (B), A&B pradedami naudojant RR
- 3 taisyklė: Kai užduotis patenka į sistemą, ji patenka į aukščiausio prioriteto eilę.
- 4 taisyklė: kai užduotis išnaudoja jai skirtą laiką dabartinėje eilėje (nesvarbu, kiek kartų ji atlaisvino centrinį procesorių), tos užduoties prioritetas sumažinamas (ji juda eilėje žemyn).
- 5 taisyklė: Po tam tikro laikotarpio S perkelkite visas sistemos užduotis į aukščiausią eilę.
MLFQ yra įdomus dėl šios priežasties – užuot reikalavęs žinių apie
Iš anksto, atsižvelgiant į užduoties pobūdį, algoritmas tiria užduoties ir rinkinių praeitį
atitinkamai prioritetus. Taigi jis stengiasi sėdėti ant dviejų kėdžių vienu metu - pasiekti produktyvumą atliekant mažas užduotis (SJF, STCF) ir sąžiningai ilgai bėgti,
CPU pakrovimo darbai. Todėl daugelis sistemų, įskaitant BSD ir jų darinius,
„Solaris“, „Windows“, „Mac“ naudoja tam tikrą algoritmą kaip planuoklį
MLFQ kaip bazinė linija.
Дополнительные mм:
- (skaičiavimas)
Šaltinis: www.habr.com