Inleiding tot besturingssystemen

Hé Habr! Ik zou graag een reeks artikelen onder uw aandacht willen brengen - vertalingen van een interessante literatuur naar mijn mening - OSTEP. Dit materiaal bespreekt vrij diepgaand het werk van Unix-achtige besturingssystemen, namelijk het werken met processen, verschillende planners, geheugen en andere soortgelijke componenten waaruit een modern besturingssysteem bestaat. U kunt het origineel van alle materialen hier bekijken hier. Houd er rekening mee dat de vertaling onprofessioneel (vrij vrij) is gemaakt, maar ik hoop dat ik de algemene betekenis heb behouden.

Labwerk over dit onderwerp is hier te vinden:

Andere delen:

Je kunt ook kijken op mijn kanaal op telegram =)

Planning: feedbackwachtrij op meerdere niveaus

In deze lezing zullen we praten over de problemen bij het ontwikkelen van een van de beroemdste benaderingen van
plannen, dat heet Feedbackwachtrij op meerdere niveaus (MLFQ). De MLFQ-planner werd voor het eerst beschreven in 1962 door Fernando J. Corbató in een systeem genaamd
Compatibel Time-Sharing-systeem (CTSS). Deze werken (inclusief later werk aan
Multics) werden vervolgens genomineerd voor de Turing Award. De planner was
vervolgens verbeterd en kreeg het uiterlijk dat je er al in terugvindt
enkele moderne systemen.

Het MLFQ-algoritme probeert twee fundamentele overlappende problemen op te lossen.
In de eerste plaats, probeert het de doorlooptijd te optimaliseren, die, zoals we in de vorige lezing hebben besproken, wordt geoptimaliseerd door de methode om het meest aan het begin van de wachtrij te beginnen
korte taken. Het besturingssysteem weet echter niet hoe lang een bepaald proces zal duren, en dit
noodzakelijke kennis voor de werking van de SJF-, STCF-algoritmen. In de tweede plaats, MLFQ probeert het
het systeem responsief maken voor gebruikers (bijvoorbeeld voor degenen die zitten en
naar het scherm staren terwijl u wacht tot de taak is voltooid) en zo de tijd minimaliseren
antwoord. Helaas verbeteren algoritmen zoals RR de responstijd, maar extreem
hebben een slechte impact op de metriek voor de doorlooptijd. Vandaar ons probleem: hoe te ontwerpen
een planner die aan onze eisen voldoet zonder er iets van te weten
de aard van het proces in het algemeen? Hoe kan de planner de kenmerken van taken leren,
die zij lanceert en zo betere planningsbeslissingen neemt?

De essentie van het probleem: hoe plan je de taakstelling zonder perfecte kennis?
Hoe je een planner ontwerpt die tegelijkertijd de responstijd minimaliseert
voor interactieve taken en minimaliseert tegelijkertijd de doorlooptijd zonder dat u het weet
kennis van de uitvoeringstijd van taken?

Let op: we leren van eerdere gebeurtenissen

De MLFQ-wachtrij is een uitstekend voorbeeld van een systeem waar van leert
gebeurtenissen uit het verleden om de toekomst te voorspellen. Soortgelijke benaderingen zijn vaak het geval
gevonden in OS (en vele andere takken van de informatica, inclusief takken
hardwarevoorspellingen en caching-algoritmen). Soortgelijke reizen
worden geactiveerd wanneer taken gedragsfasen hebben en dus voorspelbaar zijn.
Je moet echter voorzichtig zijn met deze techniek, omdat voorspellingen heel eenvoudig zijn
kan onjuist blijken te zijn en ertoe leiden dat het systeem slechtere beslissingen neemt
zou helemaal zonder kennis zijn.

MLFQ: Basisregels

Laten we eens kijken naar de basisregels van het MLFQ-algoritme. En hoewel implementaties van dit algoritme
Er zijn er verschillende, de basisbenaderingen zijn vergelijkbaar.
In de implementatie waar we naar zullen kijken, zal MLFQ er meerdere hebben
afzonderlijke wachtrijen, die elk een andere prioriteit hebben. Altijd,
een taak die gereed is voor uitvoering staat in één wachtrij. MLFQ maakt gebruik van prioriteiten,
om te beslissen welke taak moet worden uitgevoerd voor uitvoering, d.w.z. taak met hoger
prioriteit (taak uit de wachtrij met de hoogste prioriteit) wordt als eerste gestart
wachtrij.
Natuurlijk kan er meer dan één taak in een bepaalde wachtrij staan
Zij zullen dus dezelfde prioriteit hebben. In dit geval zal het mechanisme worden gebruikt
RR om een run tussen deze taken te plannen.
Zo komen we tot twee basisregels voor MLFQ:

Regel 1: Als prioriteit(A) > Prioriteit(B), wordt taak A gestart (B niet)
Regel 2: Als prioriteit(A) = Prioriteit(B), worden A&B gestart met RR

Op basis van het bovenstaande, de belangrijkste elementen voor het plannen van MLFQ
zijn prioriteiten. In plaats van aan elk een vaste prioriteit te geven
taak, verandert MLFQ zijn prioriteit afhankelijk van het waargenomen gedrag.
Als een taak bijvoorbeeld voortdurend werk naar de CPU gooit terwijl er op toetsenbordinvoer wordt gewacht,
MLFQ zal de procesprioriteit hoog houden, want zo is het
een interactief proces zou moeten werken. Als de taak daarentegen voortdurend en
gebruikt de CPU gedurende een lange periode zwaar, MLFQ zal deze verlagen
een prioriteit. MLFQ zal dus het gedrag van processen bestuderen terwijl ze actief zijn
en gebruiksgedrag.
Laten we een voorbeeld tekenen van hoe de wachtrijen er op een gegeven moment uit kunnen zien
tijd en dan krijg je zoiets als dit:

In dit schema bevinden twee processen A en B zich in de wachtrij met de hoogste prioriteit. Proces
C bevindt zich ergens in het midden en proces D bevindt zich helemaal aan het einde van de wachtrij. Volgens het bovenstaande
Volgens de beschrijvingen van het MLFQ-algoritme zal de planner alleen taken met de hoogste uitvoeren
prioriteit volgens RR, en de taken C en D zullen zonder werk zijn.
Uiteraard geeft een statische momentopname geen volledig beeld van hoe MLFQ werkt.
Het is belangrijk om precies te begrijpen hoe het beeld in de loop van de tijd verandert.

Poging 1: Hoe u de prioriteit kunt wijzigen

Op dit punt moet u beslissen hoe MLFQ het prioriteitsniveau zal wijzigen
taken (en dus de positie van de taak in de wachtrij) terwijl deze door de levenscyclus vordert. Voor
dit is nodig om rekening te houden met de workflow: een bepaald bedrag
interactieve taken met korte looptijden (en dus frequente releases).
CPU) en verschillende langlopende taken die de hele werktijd van de CPU gebruiken
Reactietijd is voor dergelijke taken niet belangrijk. En zo kun je je eerste poging wagen
implementeer het MLFQ-algoritme met de volgende regels:

Regel 3: Wanneer een taak het systeem binnenkomt, wordt deze in de wachtrij met de hoogste geplaatst
prioriteit.
Regel 4a: Als een taak het gehele toegewezen tijdvenster gebruikt, dan wordt deze uitgevoerd
prioriteit wordt verminderd.
Regel 4b: Als een taak de CPU vrijgeeft voordat het tijdvenster is verstreken, dan wordt deze uitgevoerd
blijft dezelfde prioriteit behouden.

Voorbeeld 1: Eén langlopende taak

Zoals u in dit voorbeeld kunt zien, wordt de toelatingstaak met de hoogste ingesteld
prioriteit. Na een tijdvenster van 10 ms wordt het proces in prioriteit gedegradeerd
planner. Na het volgende tijdvenster wordt de taak uiteindelijk gedegradeerd naar
laagste prioriteit in het systeem, waar het blijft.

Voorbeeld 2: Een korte taak afgeleverd

Laten we nu een voorbeeld bekijken van hoe MLFQ SJF zal proberen te benaderen. In dat
bijvoorbeeld twee taken: A, wat voortdurend een langlopende taak is
CPU en B bezetten, wat een korte interactieve taak is. Veronderstellen
dat A al een tijdje aan het werk was toen taak B arriveerde.

Deze grafiek toont de resultaten van het scenario. Taak A, zoals elke taak,
Het CPU-gebruik stond helemaal onderaan. Taak B arriveert op tijdstip T=100 en zal dat ook doen
in de wachtrij met de hoogste prioriteit geplaatst. Omdat de gebruiksduur kort is
het is voltooid voordat het de laatste wachtrij bereikt.

Uit dit voorbeeld moet het hoofddoel van het algoritme worden begrepen: aangezien het algoritme dat niet doet
weet of een taak lang of kort is, dan gaat hij er allereerst van uit dat de taak
kort en geeft hieraan de hoogste prioriteit. Als dit een heel korte taak is, dan
het zal snel worden voltooid, anders zal het, als het een lange taak is, langzaam verlopen
prioriteit neer en zal snel bewijzen dat ze inderdaad een lange taak heeft die dat niet doet
vereist een reactie.

Voorbeeld 3: Hoe zit het met I/O?

Laten we nu eens kijken naar een I/O-voorbeeld. Zoals vermeld in regel 4b,
als een proces de processor vrijgeeft zonder alle processortijd te gebruiken,
dan blijft het op hetzelfde prioriteitsniveau. De bedoeling van deze regel is vrij eenvoudig
- als de interactieve taak veel I/O-bewerkingen uitvoert, bijvoorbeeld wachten
door de gebruikerstoets of muisaanslagen zal een dergelijke taak de processor vrijmaken
vóór het toegewezen venster. Wij willen de prioriteit van een dergelijke taak niet verlagen,
en dus zal het op hetzelfde niveau blijven.

Dit voorbeeld laat zien hoe het algoritme met dergelijke processen zal werken: interactieve taak B, die slechts 1 ms CPU nodig heeft voordat deze wordt uitgevoerd
I/O-proces en langlopende taak A, die al zijn tijd besteedt aan het gebruik van de CPU.
MLFQ houdt proces B op de hoogste prioriteit omdat het doorgaat
laat de CPU los. Als B een interactieve taak is, heeft het algoritme dit bereikt
Je doel is om interactieve taken snel uit te voeren.

Problemen met het huidige MLFQ-algoritme

In de voorgaande voorbeelden hebben we een basisversie van MLFQ gebouwd. En het lijkt erop dat hij
doet zijn werk goed en eerlijk, waarbij de CPU-tijd eerlijk wordt verdeeld
lange taken en het toestaan van korte of grote taken
snel aan I/O werken. Helaas bevat deze aanpak er meerdere
serieuze problemen.
In de eerste plaats, het probleem van de honger: als het systeem veel interactief heeft
taken uitvoeren, dan zullen ze alle processortijd in beslag nemen en dus lange tijd geen enkele
de taak zal niet kunnen worden uitgevoerd (ze lijden honger).

In de tweede plaatskonden slimme gebruikers hun programma's zo schrijven
houd de planner voor de gek. Misleiding ligt in het doen van iets om te forceren
De planner geeft het proces meer CPU-tijd. Algoritme dat
hierboven beschreven is behoorlijk kwetsbaar voor soortgelijke aanvallen: voordat het tijdvenster praktisch is
beëindigd, moet u een I/O-bewerking uitvoeren (voor sommigen, ongeacht welk bestand)
en maak zo de CPU vrij. Met dergelijk gedrag kun je hetzelfde blijven
de wachtrij zelf en krijgen opnieuw een groter percentage CPU-tijd. Als je dat doet
dit is correct (voer bijvoorbeeld 99% van de venstertijd uit voordat de CPU wordt vrijgegeven),
een dergelijke taak kan de processor eenvoudigweg monopoliseren.

Ten slotte kan een programma zijn gedrag in de loop van de tijd veranderen. Die taken
waarbij de CPU werd gebruikt, kan interactief worden. In ons voorbeeld vergelijkbaar
Taken krijgen van de planner niet de behandeling die ze verdienen, zoals andere taken wel zouden krijgen
(eerste) interactieve taken.

Vraag voor het publiek: welke aanvallen op de planner kunnen in de moderne wereld worden uitgevoerd?

Poging 2: Prioriteit verhogen

Laten we proberen de regels te veranderen en kijken of we problemen kunnen voorkomen
vasten. Wat kunnen we doen om ervoor te zorgen dat dit verband houdt?
CPU-taken krijgen hun tijd (ook al duurt het niet lang).
Als eenvoudige oplossing voor het probleem kunt u periodiek voorstellen
verhoog de prioriteit van al dergelijke taken in het systeem. Er zijn veel manieren
Laten we, om dit te bereiken, proberen iets eenvoudigs als voorbeeld te implementeren: vertalen
alle taken krijgen onmiddellijk de hoogste prioriteit, vandaar de nieuwe regel:

Rule5: Verplaats na een bepaalde periode S alle taken in het systeem naar de hoogste wachtrij.

Onze nieuwe regel lost twee problemen tegelijk op. Ten eerste de processen
zullen gegarandeerd niet verhongeren: taken met de hoogste prioriteit worden verdeeld
CPU-tijd volgens het RR-algoritme en dus zullen alle processen ontvangen
CPU-tijd. Ten tweede, als een proces dat eerder werd gebruikt
alleen de processor wordt interactief, deze blijft in de wachtrij met de hoogste staan
prioriteit na ontvangst van een eenmalige verhoging van de prioriteit naar de hoogste.
Laten we eens kijken naar een voorbeeld. Overweeg in dit scenario één proces met behulp van

CPU en twee interactieve, korte processen. Links in de figuur toont de figuur het gedrag zonder prioriteitspromotie, en dus begint de langlopende taak te verhongeren nadat twee interactieve taken in het systeem arriveren. In de afbeelding rechts wordt elke 50 ms een prioriteitsverhoging uitgevoerd. Alle processen krijgen dus gegarandeerd CPU-tijd en worden periodiek gestart. In dit geval wordt als voorbeeld 50 ms genomen; in werkelijkheid ligt dit aantal iets hoger.
Het is duidelijk dat het optellen van de periodieke toenametijd S tot gevolg heeft
een logische vraag: welke waarde moet worden ingesteld? Eén van de vereerde
systeemingenieurs John Ousterhout noemde dergelijke hoeveelheden in systemen voo-doo
constant, omdat ze op de een of andere manier zwarte magie nodig hadden om correct te zijn
exposeren. En helaas heeft S zo'n geur. Als u de waarde ook instelt
grote - lange taken zullen beginnen te verhongeren. En als u de waarde te laag instelt,
Interactieve taken krijgen niet de juiste CPU-tijd.

Poging 3: Betere boekhouding

Nu hebben we nog een probleem dat moet worden opgelost: hoe het niet moet
Laat onze planner zich voor de gek houden? De mensen die verantwoordelijk zijn voor deze mogelijkheid zijn
regels 4a, 4b, die ervoor zorgen dat een taak de prioriteit behoudt, waardoor de processor vrijkomt
voordat de toegewezen tijd is verstreken. Hoe hiermee om te gaan?
De oplossing in dit geval kan worden beschouwd als een betere boekhouding van de CPU-tijd op elk
MLFQ-niveau. In plaats van de tijd te vergeten die het programma gebruikte
processor voor de toegewezen periode, moet er rekening mee worden gehouden en opgeslagen. Na
het proces heeft de toegewezen tijd opgebruikt, het moet worden gedegradeerd naar het volgende
prioriteitsniveau. Nu maakt het niet uit hoe het proces zijn tijd zal gebruiken – hoe
voortdurend computergebruik op de processor of als een aantal oproepen. Dus,
regel 4 moet worden herschreven in de volgende vorm:

Rule4: nadat een taak de toegewezen tijd in de huidige wachtrij heeft opgebruikt (ongeacht hoe vaak de CPU is vrijgemaakt), wordt de prioriteit van die taak verlaagd (deze wordt lager in de wachtrij geplaatst).

Laten we eens kijken naar een voorbeeld:
»

De figuur laat zien wat er gebeurt als je de planner voor de gek probeert te houden, bijvoorbeeld
als het met de vorige regels 4a, 4b zou zijn, zou het resultaat aan de linkerkant worden verkregen. Gelukkig nieuw
de regel is het resultaat aan de rechterkant. Vóór de bescherming kon elk proces I/O aanroepen voordat het voltooid was
domineren dus de CPU, na het inschakelen van bescherming, ongeacht het gedrag
I/O, hij zal nog steeds naar beneden in de wachtrij gaan en kan dus niet oneerlijk handelen
CPU-bronnen overnemen.

Verbetering van MLFQ en andere problemen

Met de bovenstaande verbeteringen komen nieuwe problemen: een van de belangrijkste
Vragen - hoe parametriseer je zo'n planner? Die. Hoeveel moet het zijn
wachtrijen? Hoe groot moet het programmavenster in de wachtrij zijn? Hoe
De programmaprioriteit moet vaak worden verhoogd om hongersnood te voorkomen
rekening houden met de verandering in programmagedrag? Er is geen eenvoudig antwoord op deze vragen
antwoord en experimenteert alleen met belastingen en daaropvolgende configuratie
planner kan tot een bevredigend evenwicht leiden.

Met de meeste MLFQ-implementaties kunt u bijvoorbeeld verschillende toewijzen
tijdsintervallen voor verschillende wachtrijen. Wachtrijen met hoge prioriteit meestal
korte intervallen zijn voorgeschreven. Deze wachtrijen bestaan uit interactieve taken,
het omschakelen daartussen is behoorlijk gevoelig en zou 10 of minder moeten duren
Mevr. Wachtrijen met een lage prioriteit bestaan daarentegen uit langlopende taken die gebruikmaken van
CPU. En in dit geval passen lange tijdsintervallen heel goed (100 ms).

In dit voorbeeld zijn er twee taken die werkten in wachtrij 2 met hoge prioriteit
ms, verdeeld in vensters van 10 ms. 40 ms in de middelste wachtrij (20 ms-venster) en in de lage prioriteit
Het wachtrijtijdvenster werd 40 ms, waarbij taken hun werk voltooiden.

De Solaris OS-implementatie van MLFQ is een klasse time-sharing-planners.
De planner zorgt voor een set tabellen die precies definiëren zoals het hoort
de prioriteit van het proces verandert in de loop van zijn leven, wat de omvang zou moeten zijn
toegewezen venster en hoe vaak u de taakprioriteiten moet verhogen. Beheerder
systemen kunnen met deze tabel communiceren en ervoor zorgen dat de planner zich gedraagt
anders. Standaard heeft deze tabel 60 wachtrijen met een geleidelijke toename
venstergrootte van 20 ms (hoge prioriteit) tot enkele honderden ms (lage prioriteit), en
ook met een boost van alle taken één keer per seconde.

Andere MLFQ-planners gebruiken geen tabel of iets specifieks
regels die in deze lezing worden beschreven, integendeel, ze berekenen prioriteiten met behulp van
wiskundige formules. De FreeBSD-planner gebruikt bijvoorbeeld een formule voor
bereken de huidige prioriteit van een taak op basis van hoe lang het proces duurt
gebruikte CPU. Bovendien neemt het CPU-gebruik in de loop van de tijd af, enzovoort
Het verhogen van de prioriteit gebeurt dus enigszins anders dan hierboven beschreven. Dit is waar
zogenaamde vervalalgoritmen. Sinds versie 7.1 gebruikt FreeBSD de ULE-planner.

Ten slotte hebben veel planners nog andere functies. Sommige bijvoorbeeld
planners reserveren de hoogste niveaus voor de werking van het besturingssysteem en dus
Geen enkel gebruikersproces kan dus de hoogste prioriteit krijgen
systeem. Bij sommige systemen kunt u advies geven om te helpen
de planner kan correct prioriteiten stellen. Gebruik bijvoorbeeld het commando mooi
u kunt de prioriteit van een taak verhogen of verlagen en zo verhogen of verlagen
verklein de kans dat het programma CPU-tijd gebruikt.

MLFQ: Samenvatting

We hebben een planningsaanpak beschreven, genaamd MLFQ. Zijn naam
ingesloten in het werkingsprincipe - het heeft verschillende wachtrijen en maakt gebruik van feedback
taakprioriteit bepalen.
De uiteindelijke vorm van de regels zal als volgt zijn:

Rule1: Als prioriteit(A) > Prioriteit(B), wordt taak A gestart (B niet)
Rule2: Als prioriteit(A) = Prioriteit(B), worden A&B gestart met RR
Rule3: Wanneer een taak het systeem binnenkomt, wordt deze in de wachtrij met de hoogste prioriteit geplaatst.
Rule4: nadat een taak de toegewezen tijd in de huidige wachtrij heeft opgebruikt (ongeacht hoe vaak de CPU is vrijgemaakt), wordt de prioriteit van die taak verlaagd (deze wordt lager in de wachtrij geplaatst).
Rule5: Verplaats na een bepaalde periode S alle taken in het systeem naar de hoogste wachtrij.

MLFQ is interessant om de volgende reden - in plaats van dat er kennis over vereist
aard van de taak vooraf bestudeert het algoritme het gedrag van de taak en sets in het verleden
prioriteiten dienovereenkomstig. Zo probeert hij op twee stoelen tegelijk te zitten - om productiviteit te bereiken voor kleine taken (SJF, STCF) en eerlijk lang te rennen,
CPU-ladende taken. Daarom zijn veel systemen, waaronder BSD en hun derivaten,
Solaris, Windows en Mac gebruiken een of andere vorm van algoritme als planner
MLFQ als basislijn.

Aanvullende materialen:

Bron: www.habr.com

Besturingssystemen: drie eenvoudige stukken. Deel 5: Planning: feedbackwachtrij op meerdere niveaus (vertaling)