Inleiding tot bedryfstelsels
Haai Habr! Ek wil graag 'n reeks artikels-vertalings van een interessante literatuur na my mening onder u aandag bring - OSTEP. Hierdie materiaal bespreek redelik diep die werk van unix-agtige bedryfstelsels, naamlik werk met prosesse, verskeie skeduleers, geheue en ander soortgelyke komponente waaruit 'n moderne bedryfstelsel bestaan. Jy kan die oorspronklike van alle materiaal hier sien . Neem asseblief kennis dat die vertaling onprofessioneel (heel vrylik) gemaak is, maar ek hoop ek het die algemene betekenis behou.
Laboratoriumwerk oor hierdie onderwerp kan hier gevind word:
Ander dele:
Jy kan ook na my kanaal kyk by =)
Beplanning: Veelvlakkige terugvoerwaglys
In hierdie lesing sal ons praat oor die probleme van die ontwikkeling van een van die bekendste benaderings tot
beplanning, wat genoem word Multivlakterugvoerwaglys (MLFQ). Die MLFQ-skeduleerder is vir die eerste keer in 1962 deur Fernando J. Corbató beskryf in 'n stelsel genaamd
Versoenbare tyddeelstelsel (CTSS). Hierdie werke (insluitend latere werke oor
Multics) is daarna genomineer vir 'n Turing-toekenning. Die skeduleerder was
daarna verbeter en die voorkoms verkry wat reeds in gevind kan word
sommige moderne stelsels.
Die MLFQ-algoritme probeer om 2 fundamentele oorvleuelende probleme op te los.
Eerstens, dit probeer om die omkeertyd te optimaliseer, wat, soos ons in die vorige lesing bespreek het, geoptimaliseer word deur die metode om aan die hoof van die tou te begin
kort take. Die bedryfstelsel weet egter nie hoe lank hierdie of daardie proses sal loop nie, en dit
nodige kennis vir die werking van SJF, STCF algoritmes. Tweedens, MLFQ probeer
maak die stelsel responsief vir gebruikers (byvoorbeeld vir diegene wat sit en
staar na die skerm terwyl jy wag vir die taak om te voltooi) en verminder dus die tyd
reaksie. Ongelukkig verminder algoritmes soos RR reaksietyd, maar
het 'n slegte uitwerking op die omkeertyd-metriek. Vandaar ons probleem: Hoe om te ontwerp
skeduleerder wat aan ons vereistes sal voldoen en terselfdertyd niks van weet nie
die aard van die proses, in die algemeen? Hoe kan die skeduleerder die kenmerke van take leer,
wat dit loods en dus beter skeduleringsbesluite neem?
Die kern van die probleem: Hoe om die opstel van take te beplan sonder perfekte kennis?
Hoe om 'n skeduleerder te ontwerp wat terselfdertyd reaksietyd verminder
vir interaktiewe take en verminder terselfdertyd omkeertyd sonder om te weet
kennis van taakuitvoeringstyd?
Let wel: leer uit vorige gebeure
Die MLFQ-tou is 'n uitstekende voorbeeld van 'n stelsel waarop opgelei word
gebeure in die verlede om die toekoms te voorspel. Sulke benaderings is dikwels
gevind in die bedryfstelsel (En baie ander takke in rekenaarwetenskap, insluitend takke
hardeware voorspellings en caching algoritmes). Soortgelyke staptogte
sneller wanneer take gedragsfases het en dus voorspelbaar is.
’n Mens moet egter versigtig wees met hierdie tegniek, want voorspellings is baie maklik.
kan verkeerd blyk te wees en die stelsel lei om slegter besluite te neem as
sou enigsins sonder kennis wees.
MLFQ: Basiese Reëls
Oorweeg die basiese reëls van die MLFQ-algoritme. En hoewel die implementering van hierdie algoritme
daar is verskeie, die basiese benaderings is soortgelyk.
In die implementering wat ons sal oorweeg, sal MLFQ verskeie hê
aparte rye, wat elkeen 'n ander prioriteit sal hê. Enige tyd,
die taak gereed vir uitvoering is in dieselfde tou. MLFQ gebruik prioriteite,
om te besluit watter taak om vir uitvoering uit te voer, m.a.w. taak met hoër
prioriteit ('n taak uit die tou met die hoogste prioriteit) sal by die eerste geloods word
tou.
Natuurlik kan daar meer as een taak in 'n spesifieke tou wees, dus
dus sal hulle dieselfde prioriteit hê. In hierdie geval sal die meganisme gebruik word
RR vir bekendstellingsbeplanning onder hierdie take.
So kom ons by twee basiese reëls vir MLFQ:
- Reël 1: As prioriteit (A) > Prioriteit (B), sal taak A loop (B sal nie)
- Reël 2: As prioriteit(A) = Prioriteit(B), word A&B begin deur RR te gebruik
Op grond van bogenoemde is die sleutelelemente vir die beplanning van 'n MLFQ
is prioriteite. In plaas daarvan om 'n vaste prioriteit aan elkeen te gee
taak, MLFQ verander sy prioriteit na gelang van die waargenome gedrag.
Byvoorbeeld, as 'n taak voortdurend op die SVE stop terwyl daar vir sleutelbordinvoer gewag word,
MLFQ sal die prosesprioriteit hoog hou, want dit is hoe
interaktiewe proses moet werk. As, inteendeel, die taak is voortdurend en
is SVE-intensief vir 'n lang tydperk, sal MLFQ dit afgradeer
'n prioriteit. MLFQ sal dus die gedrag van prosesse bestudeer op die tydstip wat hulle loop.
en gebruik gedrag.
Kom ons teken 'n voorbeeld van hoe die toue een of ander tyd kan lyk
tyd en dan kry jy so iets:
In hierdie skema is 2 prosesse A en B in die tou met die hoogste prioriteit. Proses
C is iewers in die middel, en proses D is heel aan die einde van die tou. Volgens bogenoemde
beskrywings van die MLFQ-algoritme, sal die skeduleerder slegs take met die hoogste uitvoer
prioriteit volgens RR, en take C, D sal sonder werk wees.
Natuurlik sal 'n statiese momentopname nie 'n volledige prentjie gee van hoe MLFQ werk nie.
Dit is belangrik om presies te verstaan hoe die prentjie oor tyd verander.
Poging 1: Hoe om die prioriteit te verander
Op hierdie stadium moet jy besluit hoe MLFQ die prioriteitsvlak sal verander
taak (en dus die posisie van die taak in die tou) gedurende sy lewensiklus. Vir
hiervan moet jy die werkvloei in gedagte hou: 'n sekere hoeveelheid
interaktiewe take met kort looptye (en dus gereelde vrystelling
CPU) en verskeie lang take wat die SVE al hul werkstyd gebruik, terwyl
reaksietyd vir sulke take is nie belangrik nie. En so kan jy die eerste poging aanwend
implementeer die MLFQ-algoritme met die volgende reëls:
- Reël 3: Wanneer 'n taak die stelsel binnekom, word dit in die tou met die hoogste geplaas
- prioriteit.
- Reël4a: As 'n taak sy hele tydvenster gebruik, dan is dit
- die prioriteit word verlaag.
- Reël4b: As 'n taak die SVE vrystel voordat sy tydvenster verstryk, dan is dit
- bly met dieselfde prioriteit.
Voorbeeld 1: Enkele langlopende taak
Soos u in hierdie voorbeeld kan sien, is die taak by toelating opgestel met die hoogste
prioriteit. Na 'n tydvenster van 10 ms, word die proses in prioriteit afgegradeer.
skeduleerder. Na die volgende tydvenster word die taak uiteindelik afgegradeer na
laagste prioriteit in die stelsel, waar dit bly.
Voorbeeld 2: Het 'n kort taak opgetel
Kom ons kyk nou na 'n voorbeeld van hoe MLFQ SJF sal probeer benader. Daarin
byvoorbeeld, twee take: A, wat voortdurend 'n langlopende taak is
beset CPU en B, wat 'n kort interaktiewe taak is. Veronderstel
dat A reeds geruime tyd aan die gang was toe taak B aangekom het.
Hierdie grafiek toon die resultate van die scenario. Taak A, soos enige taak,
die gebruik van die SVE was heel onder. Taak B sal op tyd T=100 aankom en sal
geplaas in die hoogste prioriteit tou. Aangesien die looptyd kort is,
dit sal voltooi voordat dit die laaste tou bereik.
Uit hierdie voorbeeld behoort jy die hoofdoel van die algoritme te verstaan: aangesien die algoritme dit nie doen nie
'n lang taak of 'n kort een ken, dan neem hy eerstens aan dat die taak
kort en gee dit die hoogste prioriteit. As dit regtig 'n kort taak is, dan
dit sal vinnig uitvoer, anders as dit 'n lang taak is, sal dit stadig beweeg
in prioriteit af en sal binnekort bewys dat sy inderdaad 'n lang taak is wat dit nie doen nie
vereis 'n reaksie.
Voorbeeld 3: Wat van I/O?
Kom ons kyk nou na 'n I/O-voorbeeld. Soos vermeld in reël 4b,
as 'n proses die verwerker vrystel sonder dat sy verwerkertyd ten volle gebruik is,
dan bly dit op dieselfde prioriteitsvlak. Die bedoeling van hierdie reël is redelik eenvoudig.
- as die interaktiewe werk baie I/O uitvoer, byvoorbeeld wag vir
van die gebruiker se toetsaanslagen of muis, sal so 'n taak die verwerker bevry
voor die toegewese venster. Ons wil nie so 'n prioriteitstaak weglaat nie,
en dus sal dit op dieselfde vlak bly.
Hierdie voorbeeld wys hoe die algoritme met sulke prosesse sal werk - interaktiewe taak B, wat slegs die SVE vir 1 ms benodig voordat dit uitgevoer word
I/O proses en 'n lang werk A, wat die SVE die hele tyd gebruik.
MLFQ hou proses B op die hoogste prioriteit soos dit aanhou
los die SVE. As B 'n interaktiewe taak is, dan het die algoritme in hierdie geval bereik
die doel daarvan is om interaktiewe take vinnig te begin.
Probleme met die huidige MLFQ-algoritme
In die vorige voorbeelde het ons 'n basiese weergawe van MLFQ gebou. En dit blyk dat hy
doen sy werk goed en regverdig, en versprei SVE tyd redelik tussenin
lang take en om kort take of take toe te laat wat baie toeganklik is
na I/O om vinnig te verwerk. Ongelukkig bevat hierdie benadering verskeie
ernstige probleme.
Eerstens, Die probleem van honger: as die stelsel sal baie interaktiewe
take, sal hulle al die SVE-tyd verbruik en dus nie 'n enkele lank nie
die taak sal nie kans kry om uitgevoer te word nie (hulle is honger).
Tweedens, kan slim gebruikers hul programme skryf sodat
flous die skeduleerder. Die bedrog lê daarin om iets te doen om te dwing
skeduleerder om die proses meer SVE-tyd te gee. Die algoritme wat
hierbo beskryf is redelik kwesbaar vir sulke aanvalle: voor die tydvenster is prakties
oor, moet jy 'n I / O-bewerking uitvoer (vir sommige, maak nie saak watter lêer nie)
en sodoende die SVE vry te maak. Sulke gedrag sal jou toelaat om in dieselfde te bly
die tou self en kry weer 'n groter persentasie SVE tyd. Indien gedoen
dit is korrek (bv. hardloop 99% van die venstertyd voordat die SVE vrygestel word),
so 'n taak kan eenvoudig die verwerker monopoliseer.
Laastens kan 'n program sy gedrag oor tyd verander. Daardie take
wat die SVE gebruik het, kan interaktief word. In ons voorbeeld, soortgelyk
take sal nie behoorlike behandeling van die skeduleerder ontvang nie, soos ander sou
(oorspronklike) interaktiewe take.
Vraag aan die gehoor: watter aanvalle op die skeduleerder kan in die moderne wêreld gemaak word?
Poging 2: Verhoog die prioriteit
Kom ons probeer om die reëls te verander en kyk of ons probleme daarmee kan vermy
verhongering. Wat kan ons doen om te verseker dat verwante
SVE-take sal hul tyd kry (selfs al is dit nie lank nie).
As 'n eenvoudige oplossing vir die probleem, kan jy periodiek voorstel
verhoog die prioriteit van al sulke take in die stelsel. Daar is baie maniere
om dit te bereik, kom ons probeer om iets eenvoudig te implementeer as 'n voorbeeld: vertaal
alle take gelyktydig tot die hoogste prioriteit, vandaar die nuwe reël:
- Reël5: Na 'n sekere tydperk S, dra alle take in die stelsel oor na die hoogste tou.
Ons nuwe reël los twee probleme tegelyk op. Eerstens, die prosesse
gewaarborg om nie honger te ly nie: take in die hoogste tou sal deel
verwerker tyd volgens die RR-algoritme en dus sal alle prosesse ontvang
verwerker tyd. Tweedens, as 'n proses wat voorheen gebruik is
net die verwerker word interaktief, dit sal in die tou bly met die hoogste
prioriteit nadat hy een keer 'n hupstoot tot die hoogste prioriteit ontvang het.
Oorweeg 'n voorbeeld. In hierdie scenario, oorweeg 'n enkele proses met behulp van
SVE en twee interaktiewe, kort prosesse. Aan die linkerkant in die figuur wys die figuur die gedrag sonder prioriteitsverhoging, en dus begin die langlopende taak honger ly nadat twee interaktiewe take op die stelsel aangekom het. In die figuur aan die regterkant word elke 50ms 'n prioriteitverhoging uitgevoer en dus is alle prosesse gewaarborg om verwerkertyd te ontvang en sal periodiek begin word. 50ms in hierdie geval word as voorbeeld geneem, in werklikheid is hierdie getal ietwat hoër.
Dit is duidelik dat die byvoeging van die periodieke stygtyd S tot lei
logiese vraag: watter waarde moet gestel word? Een van die welverdiende
stelselingenieurs John Ousterhout het na soortgelyke hoeveelhede in stelsels as voo-doo verwys
konstant, aangesien hulle op een of ander manier swart magie benodig het vir die korrekte
blootstelling. En ongelukkig het S so 'n geur. As jy ook die waarde stel
groot - lang take sal honger ly. En as jy dit te laag stel,
interaktiewe take sal nie behoorlike SVE-tyd ontvang nie.
Poging 3: Beter Rekeningkunde
Nou het ons nog een probleem om op te los: hoe om nie
toelaat om ons skeduleerder te kul? Die skuldiges vir hierdie moontlikheid is
reëls 4a, 4b wat toelaat dat 'n werk sy prioriteit behou deur die verwerker vry te maak
voor die verstryking van die toegewese tyd. Hoe om dit te hanteer?
Die oplossing in hierdie geval kan beskou word as 'n beter rekeningkunde van SVE tyd op elk
MLFQ vlak. In plaas daarvan om die tyd wat die program gebruik het, te vergeet
verwerker vir die toegewese interval, moet jy dit in ag neem en stoor. Na
die proses sy toegelate tyd opgebruik het, moet dit na die volgende gedegradeer word
prioriteitsvlak. Nou maak dit nie saak hoe die proses sy tyd sal gebruik nie – hoe
voortdurend op die verwerker of as 'n stel oproepe te bereken. Dus,
reël 4 moet soos volg herskryf word:
- Reël4: Nadat 'n taak sy toegewese tyd in die huidige tou opgebruik het (ongeag hoeveel keer dit die SVE bevry het), word die prioriteit van so 'n taak verminder (dit beweeg af in die tou).
Kom ons kyk na 'n voorbeeld:
»
Die figuur wys wat gebeur as jy die skeduleerder probeer mislei
as dit met die vorige reëls 4a was, sou 4b die resultaat aan die linkerkant wees. Met nuwe
die reël is die resultaat is aan die regterkant. Voor beskerming kan enige proses I/O oproep voor voltooiing en
oorheers dus die SVE, nadat beskerming geaktiveer is, ongeag die gedrag
I/O, sal hy steeds afgaan in die ry en sal dus nie oneerlik kan wees nie
SVE-hulpbronne oorneem.
Verbetering van MLFQ en ander kwessies
Met bogenoemde verbeterings ontstaan nuwe probleme: een van die belangrikste
vrae - hoe om so 'n skeduleerder te parameteriseer? Dié. Hoeveel moet wees
toue? Wat moet die grootte van die programvenster binne die tou wees? Hoe
program moet dikwels geprioritiseer word om hongersnood te vermy en
om die verandering in die gedrag van die program in ag te neem? By hierdie vrae is daar geen eenvoudig nie
reaksie en eksperimenteer slegs met vragte en daaropvolgende konfigurasie
skeduleerder kan lei tot 'n mate van bevredigende balans.
Byvoorbeeld, die meeste MLFQ-implementerings laat jou toe om verskillende toe te ken
tydgleuwe vir verskillende toue. Hoë prioriteit toue is gewoonlik
kort tussenposes. Hierdie toue bestaan uit interaktiewe take,
wissel tussen wat redelik sensitief is en 10 of minder behoort te neem
me. Daarteenoor bestaan lae-prioriteit toue uit langlopende take wat gebruik
SVE. En in hierdie geval pas lang tydintervalle baie goed (100ms).
In hierdie voorbeeld is daar 2 take wat in hoë prioriteit tou 20 gewerk het
ms verdeel in 10ms vensters. 40ms in die middelste tou (20ms venster) en in die lae prioriteit tou
toutydvenster het 40ms geword waar die take hul werk voltooi het.
Die implementering van MLFQ in die Solaris OS is 'n klas tyddeelskeduleerders.
Die skeduleerder sal 'n stel tabelle verskaf wat presies definieer hoe dit moet
verander die prioriteit van die proses in die loop van sy lewe, wat moet die grootte wees
venster wat toegeken moet word en hoe gereeld taakprioriteite verhoog moet word. Administrateur
stelsel kan met hierdie tabel in wisselwerking tree en die skeduleerder laat optree
anders. By verstek het hierdie tabel 60 toue met 'n geleidelike toename
venstergrootte van 20 ms (hoë prioriteit) tot 'n paar honderd ms (laagste prioriteit), en
ook met die hupstoot van alle take een keer per sekonde.
Ander MLFQ-skeduleerders gebruik nie 'n tabel of enige spesifieke nie
die reëls wat in hierdie hoofstuk beskryf word, inteendeel, hulle bereken prioriteite deur gebruik te maak van
wiskundige formules. Byvoorbeeld, die skeduleerder in FreeBSD gebruik 'n formule vir
die huidige taakprioriteit te bereken op grond van hoeveel die proses
het die SVE gebruik. Daarbenewens vrot SVE-gebruik met verloop van tyd, en dus
Die prioriteitsverhoging is dus ietwat anders as hierbo beskryf. Dit is waar
vervalalgoritmes genoem. Vanaf weergawe 7.1 gebruik FreeBSD die ULE skeduleerder.
Ten slotte, baie beplanners het ander kenmerke. Byvoorbeeld, sommige
skeduleers reserveer hoër vlakke vir die werking van die bedryfstelsel en dus
Geen gebruikerproses kan dus die hoogste prioriteit kry nie
stelsel. Sommige stelsels laat jou toe om raad te gee om te help
die skeduleerder om korrek te prioritiseer. Gebruik byvoorbeeld die opdrag lekker
jy kan die prioriteit van 'n taak verhoog of verlaag en sodoende verhoog of verminder
verminder die kanse van die program vir SVE tyd.
MLFQ: Opsomming
Ons het 'n beplanningsbenadering genaamd MLFQ beskryf. Sy naam
gesluit in die beginsel van werking - dit het verskeie toue en gebruik terugvoer
om 'n taak te prioritiseer.
Die finale vorm van die reëls sal soos volg wees:
- Reël1: As prioriteit (A) > Prioriteit (B), sal taak A loop (B sal nie)
- Reël2: As prioriteit(A) = Prioriteit(B), word A&B begin deur RR te gebruik
- Reël3: Wanneer 'n taak die stelsel binnekom, word dit in die hoogste prioriteit-tou geplaas.
- Reël4: Nadat 'n taak sy toegewese tyd in die huidige tou opgebruik het (ongeag hoeveel keer dit die SVE bevry het), word die prioriteit van so 'n taak verminder (dit beweeg af in die tou).
- Reël5: Na 'n sekere tydperk S, dra alle take in die stelsel oor na die hoogste tou.
MLFQ is interessant om die volgende rede - in plaas daarvan om kennis oor te vereis
aard van die taak vooraf, die algoritme leer die vorige gedrag van die taak en stelle
prioriteite dienooreenkomstig. So, hy probeer om op twee stoele tegelyk te sit - om prestasie te behaal vir klein take (SJF, STCF) en eerlik te hardloop lange,
SVE-laai take. Daarom, baie stelsels, insluitend BSD en hul afgeleides,
Solaris, Windows, Mac gebruik een of ander vorm van algoritme as die skeduleerder
MLFQ as 'n basislyn.
Bykomende materiale:
- (Computing)
Bron: will.com