Yntroduksje ta bestjoeringssystemen
Hoi Habr! Ik soe graach bringe jo oandacht in rige fan artikels-oersettingen fan ien nijsgjirrige literatuer yn myn miening - OSTEP. Dit materiaal besprekt frij djip it wurk fan unix-like bestjoeringssystemen, nammentlik wurk mei prosessen, ferskate planners, ûnthâld en oare ferlykbere komponinten dy't in moderne OS foarmje. Jo kinne hjir it orizjineel fan alle materialen sjen . Tink derom dat de oersetting ûnprofesjoneel makke is (hiel frij), mar ik hoopje dat ik de algemiene betsjutting behâlden haw.
Labwurk oer dit ûnderwerp is hjir te finen:
Oare dielen:
Jo kinne ek kontrolearje út myn kanaal op =)
Planning: Multi-Level Feedback Queue
Yn dizze lêzing sille wy prate oer de problemen fan it ûntwikkeljen fan ien fan 'e meast ferneamde oanpak foar
planning, dat hjit Multi-Level Feedback Queue (MLFQ). De MLFQ scheduler waard foar it earst beskreaun yn 1962 troch Fernando J. Corbató yn in systeem neamd
Kompatibel Time-Sharing System (CTSS). Dizze wurken (ynklusyf lettere wurken oan
Multics) waarden dêrnei nominearre foar in Turing Award. De planner wie
dêrnei ferbettere en krige it uterlik dat al te finen is yn
guon moderne systemen.
It MLFQ-algoritme besiket 2 fûnemintele oerlappende problemen op te lossen.
Earst, it besiket de omlooptiid te optimalisearjen, dy't, lykas wy besprutsen yn 'e foarige lêzing, wurdt optimalisearre troch de metoade om te begjinnen oan' e kop fan 'e wachtrige meast
koarte taken. It OS wit lykwols net hoe lang dit of dat proses sil rinne, en dit
nedige kennis foar de wurking fan SJF, STCF algoritmen. Twad, MLFQ besiket
meitsje it systeem responsyf foar brûkers (bygelyks foar dyjingen dy't sitte en
stjer nei it skerm wylst wachtsje op de taak om te foltôgjen) en sa minimalisearje de tiid
antwurd. Spitigernôch ferbetterje algoritmen lykas RR reaksjetiid, mar ekstreem
hawwe in min effekt op de omlooptiid metryske. Dêrom ús probleem: Hoe ûntwerpe
planner dy't sil foldwaan oan ús easken en tagelyk witte neat oer
de aard fan it proses, yn it algemien? Hoe kin de planner de skaaimerken fan taken leare,
dy't it lansearret en dus bettere plannen besluten meitsje?
De essinsje fan it probleem: Hoe kinne jo de ynstelling fan taken planne sûnder perfekte kennis?
Hoe kinne jo in planner ûntwerpe dy't tagelyk de reaksjetiid minimalisearret
foar ynteraktive taken en tagelyk minimearret omlooptiid sûnder te witten
kennis fan taak útfiering tiid?
Opmerking: learje fan eardere eveneminten
De MLFQ-wachtrige is in poerbêst foarbyld fan in systeem dat wurdt traind op
ferline eveneminten om de takomst te foarsizzen. Sokke oanpak binne faak
fûn yn it OS (En in protte oare tûken yn kompjûterwittenskip, ynklusyf tûken
hardwarefoarsizzingen en cachingalgoritmen). Similar kuiertochten
trigger as taken gedrachsfazen hawwe en dus foarsisber binne.
Men moat lykwols foarsichtich wêze mei dizze technyk, om't foarsizzingen tige maklik binne.
kin blike te wêzen ferkeard en liede it systeem te nimmen slimmer besluten as
soe hielendal sûnder kennis wêze.
MLFQ: Basisregels
Beskôgje de basisregels fan it MLFQ-algoritme. En hoewol de ymplemintaasjes fan dit algoritme
der binne ferskate, de basis oanpak binne fergelykber.
Yn 'e ymplemintaasje dy't wy sille beskôgje, sil MLFQ ferskate hawwe
aparte wachtrijen, elk fan dat sil hawwe in oare prioriteit. Wannear dan ek,
de taak klear foar útfiering is yn deselde wachtrige. MLFQ brûkt prioriteiten,
om te besluten hokker taak te rinnen foar útfiering, d.w.s. taak mei hegere
prioriteit (in taak út 'e wachtrige mei de heechste prioriteit) wurdt lansearre by de earste
rigel.
Fansels kinne d'r mear as ien taak yn in bepaalde wachtrige wêze, dus
sadat se sille hawwe deselde prioriteit. Yn dit gefal sil it meganisme brûkt wurde
RR foar lansearring planning ûnder dizze taken.
Sa komme wy by twa basisregels foar MLFQ:
- Regel 1: As prioriteit (A) > Prioriteit (B), sil taak A wurde lansearre (B sil net)
- Regel 2: As prioriteit (A) = Prioriteit (B), wurde A&B begon mei RR
Op grûn fan it boppesteande binne de kaai eleminten foar it plannen fan in MLFQ
binne prioriteiten. Yn stee fan elk in fêste prioriteit te jaan
taak feroaret MLFQ syn prioriteit ôfhinklik fan it waarnommen gedrach.
Bygelyks, as in taak konstant stopet op 'e CPU wylst wachtet op toetseboerdynfier,
MLFQ sil de prosesprioriteit heech hâlde, om't dat is hoe
ynteraktyf proses moat wurkje. As, krekt oarsom, de taak is hieltyd en
is CPU yntinsyf foar in lange perioade, MLFQ sil downgrade it
in prioriteit. Sa sil MLFQ it gedrach fan prosessen studearje op it stuit dat se rinne.
en gebrûk gedrach.
Litte wy in foarbyld tekenje fan hoe't de wachtrigen der op in stuit útsjen kinne
tiid en dan krije jo sa'n ding:
Yn dit skema steane 2 prosessen A en B yn 'e wachtrige mei de heechste prioriteit. Proses
C is earne yn 'e midden, en proses D is oan' e ein fan 'e wachtrige. Neffens it boppesteande
beskriuwingen fan it MLFQ-algoritme, sil de planner allinich taken útfiere mei de heechste
prioriteit neffens RR, en taken C, D sil wêze sûnder wurk.
Natuerlik sil in statyske momintopname gjin folslein byld jaan fan hoe't MLFQ wurket.
It is wichtich om krekt te begripen hoe't de ôfbylding oer de tiid feroaret.
Poging 1: Hoe feroarje de prioriteit
Op dit punt moatte jo beslute hoe't MLFQ it prioriteitsnivo sil feroarje
taak (en dus de posysje fan 'e taak yn 'e wachtrige) yn syn libbenssyklus. Foar
hjirfan moatte jo de workflow yn gedachten hâlde: in bepaald bedrach
ynteraktive taken mei koarte rinnende tiden (en dus faak frijlitting
CPU) en ferskate lange taken dy't de CPU al har wurktiid brûke, wylst
reaksjetiid foar sokke taken is net wichtich. En sa kinne jo de earste poging meitsje
ymplemintearje it MLFQ-algoritme mei de folgjende regels:
- Rule3: As in taak yn it systeem komt, wurdt it yn 'e wachtrige pleatst mei de heechste
- prioriteit.
- Rule4a: As in taak syn hiele tiidfinster brûkt, dan is it
- de prioriteit wurdt ferlege.
- Rule4b: As in taak de CPU frijlitte foardat syn tiidfinster ferrint, dan is it
- bliuwt mei deselde prioriteit.
Foarbyld 1: Single langrinnende taak
Lykas jo yn dit foarbyld kinne sjen, is de taak by talitting ynsteld mei de heechste
prioriteit. Nei in tiidfinster fan 10ms wurdt it proses yn prioriteit downgraded.
planner. Nei it folgjende tiidfinster wurdt de taak úteinlik degradearre nei
leechste prioriteit yn it systeem, dêr't it bliuwt.
Foarbyld 2: Oppakt in koarte taak
Litte wy no in foarbyld sjen fan hoe't MLFQ sil besykje SJF te benaderjen. Yn dat
bygelyks, twa taken: A, dat is in lange-rinnende taak konstant
besette CPU en B, dat is in koarte ynteraktive taak. Stel
dat A al in skoft oan it wurk wie doe't taak B oankaam.
Dizze grafyk toant de resultaten fan it senario. Taak A, lykas elke taak,
it brûken fan de CPU wie op 'e boaiem. Taak B sil oankomme op tiid T = 100 en sil
pleatst yn de wachtrige mei de heechste prioriteit. Om't de rinnende tiid koart is,
it sil foltôgje foardat it de lêste wachtrige berikt.
Ut dit foarbyld moatte jo it haaddoel fan it algoritme begripe: om't it algoritme net docht
in lange taak of in koarte ken, dan giet er earst fan út dat de taak
koart en jout it de heechste prioriteit. As it echt in koarte taak is, dan
it sil fluch rinne, oars as it in lange taak is, sil it stadich bewege
yn prioriteit omleech en sil gau bewize dat se is yndie in lange taak dy't net
freget in reaksje.
Foarbyld 3: Hoe sit it mei I/O?
Litte wy no nei in I/O-foarbyld sjen. Lykas sein yn regel 4b,
as in proses de prosessor frijlit sûnder syn prosessortiid folslein te hawwen brûkt,
dan bliuwt it op itselde prioriteitsnivo. De bedoeling fan dizze regel is frij simpel.
- as de ynteraktive baan fiert in protte I / O, bygelyks, wachtsje op
fan de brûker toetsoanslagen of mûs, sa'n taak sil befrije de prosessor
foar it tawiisde finster. Wy wolle sa'n prioriteitstaak net weilitte,
en sa bliuwt it op itselde nivo.
Dit foarbyld lit sjen hoe't it algoritme soe wurkje mei sokke prosessen - ynteraktive taak B, dy't allinich de CPU nedich hat foar 1ms foar it útfieren
I / O proses en in lange baan A, dy't brûkt de CPU hiele tiid.
MLFQ hâldt proses B op 'e heechste prioriteit as it trochgiet
frijlitte de CPU. As B in ynteraktive taak is, dan is it algoritme yn dit gefal berikt
it doel is om ynteraktive taken fluch te starten.
Problemen mei it hjoeddeistige MLFQ-algoritme
Yn 'e foarige foarbylden hawwe wy in basisferzje fan MLFQ boud. En it liket derop dat hy
docht syn wurk goed en earlik, ferdieling CPU tiid frij tusken
lange taken en it tastean fan koarte taken as taken dy't swier tagonklik binne
nei I/O om fluch te ferwurkjen. Spitigernôch befettet dizze oanpak ferskate
serieuze problemen.
Earst, it probleem fan honger: as it systeem sil hawwe in protte ynteraktyf
taken, se sille ferbrûke alle CPU tiid en dus net ien lang
de taak sil net kinne wurde útfierd (se binne úthongere).
Twad, kinne tûke brûkers har programma's skriuwe sadat
gek de planner. De bedrog leit yn it dwaan fan wat om te twingen
planner om it proses mear CPU-tiid te jaan. It algoritme dat
hjirboppe beskreaun is frij kwetsber foar sokke oanfallen: foardat de tiid finster is praktysk
oer, moatte jo in I / O-operaasje útfiere (foar guon, nettsjinsteande hokker bestân)
en sa de CPU frijmeitsje. Sokke gedrach sil tastean jo te bliuwen yn itselde
de wachtrige sels en wer krije in grutter persintaazje fan CPU tiid. As dien
dit is korrekt (bgl. 99% fan 'e finstertiid útfiere foardat jo de CPU loslitte),
sa'n taak kin gewoan monopolisearje de prosessor.
Uteinlik kin in programma syn gedrach oer de tiid feroarje. Dy taken
dat brûkte de CPU kin wurden ynteraktyf. Yn ús foarbyld, fergelykber
taken sille gjin goede behanneling krije fan 'e planner, lykas oaren soene
(orizjinele) ynteraktive taken.
Fraach oan it publyk: hokker oanfallen op 'e planner kinne wurde makke yn' e moderne wrâld?
Poging 2: Ferheegje de prioriteit
Lit ús besykje te feroarjen de regels en sjen oft wy kinne foarkomme problemen mei
úthongering. Wat kinne wy dwaan om te soargjen dat ferbân
CPU-taken sille har tiid krije (sels as net lang).
As in ienfâldige oplossing foar it probleem kinne jo periodyk foarstelle
fergrutsje de prioriteit fan al sokke taken yn it systeem. Der binne in protte manieren
om dit te berikken, litte wy besykje wat ienfâldich te realisearjen as foarbyld: oersette
alle taken tagelyk op de heechste prioriteit, dus de nije regel:
- Regel5: Nei guon perioade S, oerdrage alle taken yn it systeem nei de heechste wachtrige.
Us nije regel lost twa problemen tagelyk op. Earst, de prosessen
garandearre net úthongere: taken yn 'e heechste wachtrige sille diele
prosessor tiid neffens de RR algoritme en dus alle prosessen sille ûntfange
prosessor tiid. Twad, as guon proses dat earder brûkt
allinnich de prosessor wurdt ynteraktyf, it sil bliuwe yn 'e wachtrige mei de heechste
prioriteit nei it ûntfangen fan in ympuls oan de heechste prioriteit ien kear.
Beskôgje in foarbyld. Yn dit senario, beskôgje in inkele proses mei help
CPU en twa ynteraktive, koarte prosessen. Oan de linkerkant yn de figuer, de figuer toant it gedrach sûnder prioriteit ympuls, en dus de lange rinnende taak begjint te hongerjen nei twa ynteraktive taken komme op it systeem. Yn 'e figuer oan' e rjochterkant wurdt elke 50ms in prioriteitferheging útfierd en dus wurde alle prosessen garandearre om prosessortiid te ûntfangen en wurde periodyk begon. 50ms wurdt yn dit gefal as foarbyld nommen, yn werklikheid is dit oantal wat heger.
It is fanselssprekkend dat de tafoeging fan de periodike opkomsttiid S ta liedt
logyske fraach: hokker wearde moat wurde ynsteld? Ien fan de goed fertsjinne
systeemingenieurs John Ousterhout neamde ferlykbere hoemannichten yn systemen as voo-doo
konstante, sûnt se yn guon wize nedich swarte magy foar de korrekte
bleatstean oan. En, spitigernôch, S hat sa'n smaak. As jo de wearde ek ynstelle
grut - lange taken sille úthongere. En as jo it te leech sette,
ynteraktive taken sille net ûntfange goede CPU tiid.
Poging 3: Better Accounting
No hawwe wy noch ien probleem op te lossen: hoe net
tastean om cheat ús planner? De skuldigen foar dizze mooglikheid binne
regels 4a, 4b dy't tastean in baan te hâlden syn prioriteit troch in frijmeitsje de prosessor
foar it ferstriken fan 'e tawiisde tiid. Hoe om te gean mei it?
De oplossing yn dit gefal kin wurde beskôge as in bettere boekhâlding fan CPU-tiid op elk
MLFQ nivo. Yn stee fan it ferjitten fan de tiid it programma brûkt
prosessor foar it tawiisd ynterval, moatte jo rekken hâlde en bewarje it. Efter
it proses hat syn tawiisde tiid brûkt, it moat wurde degradearre nei de folgjende
prioriteit nivo. No makket it net út hoe't it proses syn tiid sil brûke - hoe
konstant berekkenjen op 'e prosessor of as in set fan oproppen. Dus,
regel 4 moat sa herskreaun wurde:
- Regel4: Nei't in taak syn tawiisde tiid yn 'e aktuele wachtrige brûkt hat (nettsjinsteande hoefolle kearen it de CPU befrijde), wurdt de prioriteit fan sa'n taak fermindere (it beweecht de wachtrige del).
Litte wy nei in foarbyld sjen:
»
De figuer lit sjen wat der bart as jo besykje de planner te ferrifeljen lykas
as it wie mei de foarige regels 4a, soe 4b wêze it resultaat oan de linkerkant. Mei nij
de regel is it resultaat is oan de rjochterkant. Foarôfgeand oan beskerming, elk proses koe belje I / O foar foltôging en
dus dominearje de CPU, nei it ynskeakeljen fan beskerming, nettsjinsteande it gedrach
I / O, hy sil noch gean del yn 'e wachtrige en dus sil net by steat wêze om ûnearlik
oernimme CPU boarnen.
Ferbetterjen fan MLFQ en oare problemen
Mei de boppesteande ferbetterings ûntsteane nije problemen: ien fan 'e wichtichste
fragen - hoe kinne jo sa'n planner parameterisearje? Dy. Hoefolle moat wêze
wachtrige? Wat moat de grutte wêze fan it programmafinster yn 'e wachtrige? Hoe
programma moat faak wurde prioriteit om foar te kommen hongersneed en
om rekken te hâlden mei de feroaring yn it gedrach fan it programma? Foar dizze fragen is d'r gjin ienfâldich
antwurd en allinich eksperiminten mei loads en folgjende konfiguraasje
planner kin liede ta wat befredigjend lykwicht.
Bygelyks, de measte MLFQ-ymplemintaasjes kinne jo ferskate tawize
tiid slots foar ferskate queues. Wachtrijen mei hege prioriteit binne meastentiids
koarte yntervallen. Dizze wachtrigen besteane út ynteraktive taken,
wikseljen tusken dat is frij gefoelich en moat nimme 10 of minder
ms. Yn tsjinstelling besteane wachtrijen mei lege prioriteit út langrinnende taken dy't brûke
CPU. En yn dit gefal passe lange tiidintervallen tige goed (100ms).
Yn dit foarbyld binne d'r 2 taken dy't wurke hawwe yn wachtrige 20 mei hege prioriteit
ms ferdield yn 10ms finsters. 40ms yn 'e middelste wachtrige (20ms finster) en yn' e wachtrige mei lege prioriteit
wachtrige tiid finster waard 40ms dêr't de taken foltôge harren wurk.
De ymplemintaasje fan MLFQ yn it Solaris OS is in klasse fan time-sharing planners.
De planner sil in set tabellen leverje dy't krekt definiearje hoe't it moat
feroarje de prioriteit fan it proses yn de rin fan syn libben, wat moat wêze de grutte
finster dat moat wurde tawiisd en hoe faak de taakprioriteiten ferheegje. Behearder
systeem kin ynteraksje mei dizze tabel en meitsje de planner gedrage
oars. Standert hat dizze tabel 60 wachtrijen mei in stadige ferheging
finster grutte út 20ms (hege prioriteit) oan ferskate hûnderten ms (leechste prioriteit), en
ek mei de ympuls fan alle taken ien kear in sekonde.
Oare MLFQ-planners brûke gjin tabel of in spesifike
de regels dy't beskreaun yn dit haadstik, krekt oarsom, se berekkenje prioriteiten mei help
wiskundige formules. Bygelyks, de planner yn FreeBSD brûkt in formule foar
berekkenjen fan de hjoeddeiske taak prioriteit basearre op hoefolle it proses
brûkte de CPU. Dêrneist rotte CPU-gebrûk oer de tiid, en dus
Sadwaande komt tanimmende prioriteit wat oars foar as hjirboppe beskreaun. Dit is wier
neamd ferfal algoritmen. Fanôf ferzje 7.1 brûkt FreeBSD de ULE-planner.
Uteinlik hawwe in protte planners oare funksjes. Bygelyks, guon
planners reservearje hegere nivo's foar de wurking fan it bestjoeringssysteem en dus
Sa kin gjin brûkersproses de heechste prioriteit krije yn
systeem. Guon systemen kinne jo advys jaan om te helpen
de planner om korrekt te prioritearjen. Bygelyks, mei help fan it kommando nice
jo kinne de prioriteit fan in taak ferheegje of ferminderje en sadwaande fergrutsje of ferminderje
ferminderje de kânsen fan it programma foar CPU tiid.
MLFQ: Gearfetting
Wy hawwe beskreaun in planning oanpak neamd MLFQ. Syn namme
konkludearre yn it prinsipe fan operaasje - it hat ferskate wachtrijen en brûkt feedback
in taak prioritearje.
De definitive foarm fan 'e regels sil as folgjend wêze:
- Regel1: As prioriteit (A) > Prioriteit (B), sil taak A útfiere (B sil net)
- Regel2: As prioriteit (A) = Prioriteit (B), wurde A&B begon mei RR
- Regel3: As in taak yn it systeem komt, wurdt it yn 'e wachtrige mei heechste prioriteit pleatst.
- Regel4: Nei't in taak syn tawiisde tiid yn 'e aktuele wachtrige brûkt hat (nettsjinsteande hoefolle kearen it de CPU befrijde), wurdt de prioriteit fan sa'n taak fermindere (it beweecht de wachtrige del).
- Regel5: Nei guon perioade S, oerdrage alle taken yn it systeem nei de heechste wachtrige.
MLFQ is nijsgjirrich foar de folgjende reden - ynstee fan fereaskje kennis oer
aard fan 'e taak foarôf, it algoritme leart it ferline gedrach fan' e taak en sets
prioriteiten neffens. Sa besiket er tagelyk op twa stuollen te sitten - prestaasje te berikken foar lytse taken (SJF, STCF) en earlik lange rinnen,
CPU-laden banen. Dêrom binne in protte systemen, ynklusyf BSD en har derivaten,
Solaris, Windows, Mac brûke ien of oare foarm fan algoritme as de planner
MLFQ as basisline.
Oanfoljende materialen:
- (berekkenje)
Boarne: www.habr.com