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

Inleiding tot Planner

De essentie van het probleem: hoe ontwikkel je een planningsbeleid?
Hoe moeten de onderliggende beleidskaders voor planners worden ontworpen? Wat zouden de belangrijkste aannames moeten zijn? Welke statistieken zijn belangrijk? Welke basistechnieken werden gebruikt in vroege computersystemen?

Aannames over de werklast

Voordat we mogelijk beleid bespreken, maken we eerst een paar vereenvoudigende uitweidingen over de processen die in het systeem draaien, die gezamenlijk worden genoemd werkdruk. Het definiëren van de werklast is een cruciaal onderdeel van het opstellen van beleid, en hoe meer u weet over de werklast, hoe beter het beleid dat u kunt schrijven.

Laten we de volgende aannames maken over de processen die in het systeem worden uitgevoerd, ook wel genoemd vacatures (taken). Bijna al deze aannames zijn niet realistisch, maar zijn noodzakelijk voor de ontwikkeling van het denken.

Elke taak duurt even lang,
Alle taken worden tegelijkertijd ingesteld,
De toegewezen taak werkt tot de voltooiing ervan,
Alle taken gebruiken alleen CPU,
Van elke taak is de looptijd bekend.

Plannerstatistieken

Naast enkele aannames over de belasting is er nog een ander hulpmiddel nodig om verschillende planningsbeleidsvormen te vergelijken: plannerstatistieken. Een metriek is slechts een maatstaf voor iets. Er zijn een aantal statistieken die kunnen worden gebruikt om planners te vergelijken.

We zullen bijvoorbeeld een metriek gebruiken genaamd doorlooptijd (doorlooptijd). De doorlooptijd van een taak wordt gedefinieerd als het verschil tussen de voltooiingstijd van de taak en de aankomsttijd van de taak in het systeem.

Tturnaround=Tvoltooiing-Aankomst

Omdat we ervan uitgingen dat alle taken tegelijkertijd arriveerden, was Ta=0 en dus Tt=Tc. Deze waarde zal uiteraard veranderen als we de bovenstaande aannames veranderen.

Een andere maatstaf - eerlijkheid (eerlijkheid, eerlijkheid). Productiviteit en eerlijkheid zijn vaak tegengestelde kenmerken bij planning. De planner kan bijvoorbeeld de prestaties optimaliseren, maar dit gaat ten koste van het wachten tot andere taken worden uitgevoerd, waardoor de eerlijkheid wordt verminderd.

EERST IN EERST UIT (FIFO)

Het meest basale algoritme dat we kunnen implementeren heet FIFO of wie het eerst komt (in), het eerst maalt (uit). Dit algoritme heeft verschillende voordelen: het is heel eenvoudig te implementeren, het voldoet aan al onze aannames en doet zijn werk redelijk goed.

Laten we naar een eenvoudig voorbeeld kijken. Laten we zeggen dat er tegelijkertijd 3 taken zijn ingesteld. Maar laten we aannemen dat taak A iets eerder arriveert dan alle andere, zodat deze eerder in de uitvoeringslijst zal verschijnen dan de andere, net zoals B ten opzichte van C. Laten we aannemen dat elk van hen gedurende 10 seconden zal worden uitgevoerd. Wat zal in dit geval de gemiddelde tijd zijn om deze taken te voltooien?

Door de waarden te tellen - 10+20+30 en te delen door 3, krijgen we de gemiddelde uitvoeringstijd van het programma gelijk aan 20 seconden.
Laten we nu proberen onze aannames te veranderen. In het bijzonder aanname 1 en dus gaan we er niet langer van uit dat elke taak evenveel tijd kost om uit te voeren. Hoe zal FIFO deze keer presteren?

Het blijkt dat verschillende taakuitvoeringstijden een extreem negatieve invloed hebben op de productiviteit van het FIFO-algoritme. Laten we aannemen dat het voltooien van taak A 100 seconden duurt, terwijl taak B en C elk nog steeds 10 seconden duren.

Zoals uit de figuur blijkt, zal de gemiddelde tijd voor het systeem (100+110+120)/3=110 zijn. Dit effect wordt genoemd konvooi-effect, wanneer sommige kortetermijnconsumenten van een hulpbron in de rij zullen staan na een grote consument. Het is net als de rij bij de supermarkt als er een klant voor je staat met een volle winkelwagen. De beste oplossing voor het probleem is proberen de kassa te verwisselen of te ontspannen en diep adem te halen.

Kortste baan eerst

Is het mogelijk om een soortgelijke situatie op de een of andere manier op te lossen met zware processen? Zeker. Een ander type planning wordt genoemdKortste baan eerst (SJF). Het algoritme is ook vrij primitief: zoals de naam al aangeeft, worden de kortste taken als eerste gestart, de een na de ander.

In dit voorbeeld zal het resultaat van het uitvoeren van dezelfde processen een verbetering zijn van de gemiddelde doorlooptijd van het programma, en deze zal gelijk zijn aan 50 in plaats van 110, wat bijna 2 keer beter is.

Dus voor de gegeven aanname dat alle taken op hetzelfde moment arriveren, lijkt het SJF-algoritme het meest optimale algoritme. Onze aannames lijken echter nog steeds niet realistisch. Deze keer veranderen we aanname 2 en stellen we ons deze keer voor dat taken op elk moment aanwezig kunnen zijn, en niet allemaal tegelijkertijd. Tot welke problemen kan dit leiden?

Laten we ons voorstellen dat taak A (100c) als eerste arriveert en wordt uitgevoerd. Op t=10 arriveren taken B en C, die elk 10 seconden duren. De gemiddelde uitvoeringstijd is dus (100+(110-10)+(120-10))3 = 103. Wat kan de planner doen om dit te verbeteren?

Kortste tijd tot voltooiing eerst (STCF)

Om de situatie te verbeteren laten we aanname 3 achterwege dat het programma gelanceerd wordt en doorloopt tot het voltooid is. Bovendien hebben we hardware-ondersteuning nodig en, zoals je misschien al vermoedt, zullen we deze gebruiken timer om een lopende taak te onderbreken en contextwisseling. De planner kan dus iets doen op het moment dat de taken B en C arriveren - stoppen met het uitvoeren van taak A en de taken B en C in verwerking zetten en, na voltooiing ervan, doorgaan met het uitvoeren van proces A. Zo'n planner wordt genoemd STCFof Preventieve taak eerst.

Het resultaat van deze planner is het volgende resultaat: ((120-0)+(20-10)+(30-10))/3=50. Zo’n planner wordt dus nog optimaler voor onze taken.

Metrische responstijd

Dus als we de looptijd van de taken kennen en dat deze taken alleen CPU gebruiken, zal STCF de beste oplossing zijn. En vroeger werkten deze algoritmen behoorlijk goed. De gebruiker brengt nu echter het grootste deel van haar tijd door op de terminal en verwacht een productieve interactieve ervaring. Zo werd een nieuwe maatstaf geboren: reactietijd (antwoord).

De responstijd wordt als volgt berekend:

Tresponse=Tfirstrun-Tarrival

Voor het vorige voorbeeld zal de responstijd dus zijn: A=0, B=0, C=10 (abg=3,33).

En het blijkt dat het STCF-algoritme niet zo goed is in een situatie waarin drie taken tegelijkertijd aankomen - het zal moeten wachten tot de kleine taken volledig zijn voltooid. Het algoritme is dus goed voor de metriek voor de doorlooptijd, maar slecht voor de metriek voor interactiviteit. Stel je voor dat je aan een terminal zit en karakters in een editor probeert te typen en meer dan 3 seconden moet wachten omdat een andere taak de CPU in beslag neemt. Het is niet erg prettig.

We worden dus geconfronteerd met een ander probleem: hoe kunnen we een planner bouwen die gevoelig is voor de responstijd?

Round Robin

Om dit probleem op te lossen is een algoritme ontwikkeld Round Robin (RR). Het basisidee is vrij eenvoudig: in plaats van taken uit te voeren totdat ze zijn voltooid, zullen we de taak gedurende een bepaalde periode uitvoeren (een zogenaamde time slice) en dan overschakelen naar een andere taak uit de wachtrij. Het algoritme herhaalt zijn werk totdat alle taken zijn voltooid. In dit geval moet de looptijd van het programma een veelvoud zijn van de tijd waarna de timer het proces onderbreekt. Als een timer bijvoorbeeld elke x=10ms een proces onderbreekt, moet de grootte van het procesuitvoeringsvenster een veelvoud van 10 zijn en 10,20 of x*10 zijn.

Laten we naar een voorbeeld kijken: ABC-taken komen gelijktijdig in het systeem aan en elk ervan wil 5 seconden worden uitgevoerd. Het SJF-algoritme voltooit elke taak totdat deze is voltooid voordat een andere wordt gestart. Het RR-algoritme met een startvenster = 1s zal de taken daarentegen als volgt doorlopen (Fig. 4.3):

(Opnieuw SJF (slecht voor responstijd)

(Round Robin (goed voor responstijd)

De gemiddelde responstijd voor het RR-algoritme is (0+1+2)/3=1, terwijl voor de SJF (0+5+10)/3=5.

Het is logisch om aan te nemen dat het tijdvenster een zeer belangrijke parameter is voor RR; hoe kleiner het is, hoe hoger de responstijd. Je moet het echter niet te klein maken, omdat de tijd voor het wisselen van context ook een rol zal spelen in de algehele prestaties. De keuze van de uitvoeringsvenstertijd wordt dus bepaald door de OS-architect en hangt af van de taken die daarin moeten worden uitgevoerd. Het wisselen van context is niet de enige serviceoperatie die tijd verspilt - het actieve programma werkt op veel andere dingen, bijvoorbeeld verschillende caches, en bij elke overstap is het noodzakelijk om deze omgeving op te slaan en te herstellen, wat ook veel tijd kan kosten tijd.

RR is een geweldige planner als we het alleen over de responstijdstatistiek hebben. Maar hoe zal de doorlooptijd van de taak zich gedragen met dit algoritme? Beschouw het bovenstaande voorbeeld, wanneer de bedrijfstijd van A, B, C = 5s en op hetzelfde tijdstip arriveert. Taak A eindigt om 13 seconden, B om 14 seconden en C om 15 seconden. De gemiddelde doorlooptijd bedraagt 14 seconden. RR is dus het slechtste algoritme voor de omzetmetriek.

In meer algemene termen is elk algoritme van het RR-type eerlijk; het verdeelt de CPU-tijd gelijkelijk over alle processen. En dus zijn deze statistieken voortdurend in conflict met elkaar.

We hebben dus verschillende contrasterende algoritmen en tegelijkertijd zijn er nog steeds verschillende aannames over: dat de taaktijd bekend is en dat de taak alleen de CPU gebruikt.

Mengen met I/O

Laten we eerst aanname 4 verwijderen dat het proces alleen de CPU gebruikt; dit is uiteraard niet het geval en processen hebben toegang tot andere apparatuur.

Op het moment dat een proces om een I/O-bewerking vraagt, komt het proces in de geblokkeerde toestand en wacht tot de I/O is voltooid. Als I/O naar de harde schijf wordt gestuurd, kan een dergelijke bewerking enkele ms of langer duren, en is de processor op dit moment inactief. Gedurende deze tijd kan de planner de processor met elk ander proces bezighouden. De volgende beslissing die de planner moet nemen is wanneer het proces de I/O zal voltooien. Wanneer dit gebeurt, zal er een interrupt optreden en zal het besturingssysteem het proces dat de I/O heeft aangeroepen in de gereed-status zetten.

Laten we eens kijken naar een voorbeeld van verschillende problemen. Elk van hen vereist 50 ms CPU-tijd. De eerste heeft echter elke 10 ms toegang tot I/O (wat ook elke 10 ms wordt uitgevoerd). En proces B gebruikt eenvoudigweg een processor van 50 ms zonder I/O.

In dit voorbeeld gebruiken we de STCF-planner. Hoe zal de planner zich gedragen als er een proces als A op wordt gestart? Hij gaat het volgende doen: eerst werkt hij proces A volledig uit, en dan proces B.

De traditionele aanpak om dit probleem op te lossen is om elke subtaak van 10 ms van proces A als een afzonderlijke taak te behandelen. Als we dus met het STJF-algoritme beginnen, ligt de keuze tussen een taak van 50 ms en een taak van 10 ms voor de hand. Wanneer subtaak A is voltooid, worden proces B en I/O gestart. Nadat de I/O is voltooid, is het gebruikelijk om proces A van 10 ms opnieuw te starten in plaats van proces B. Op deze manier is het mogelijk om overlap te implementeren, waarbij de CPU door een ander proces wordt gebruikt terwijl het eerste wacht op de IO. En daardoor wordt het systeem beter benut: op het moment dat interactieve processen op I/O wachten, kunnen andere processen op de processor worden uitgevoerd.

Het Orakel is niet meer

Laten we nu proberen af te komen van de veronderstelling dat de looptijd van de taak bekend is. Dit is over het algemeen de slechtste en meest onrealistische veronderstelling op de hele lijst. In het gemiddelde gewone besturingssysteem weet het besturingssysteem zelf meestal heel weinig over de uitvoeringstijd van taken, dus hoe kun je dan een planner bouwen zonder te weten hoe lang het duurt om de taak uit te voeren? Misschien kunnen we enkele RR-principes gebruiken om dit probleem op te lossen?

Totaal

We keken naar de basisideeën van taakplanning en keken naar 2 families van planners. De eerste start eerst de kortste taak en verlengt daarmee de doorlooptijd, terwijl de tweede gelijkmatig over alle taken wordt verdeeld, waardoor de responstijd toeneemt. Beide algoritmen zijn slecht, terwijl algoritmen van de andere familie goed zijn. We hebben ook gekeken naar hoe parallel gebruik van CPU en I/O de prestaties kan verbeteren, maar hebben het probleem met de helderziendheid van het besturingssysteem niet opgelost. En in de volgende les zullen we kijken naar een planner die naar het onmiddellijke verleden kijkt en de toekomst probeert te voorspellen. En het wordt een feedbackwachtrij op meerdere niveaus genoemd.

Bron: www.habr.com

Besturingssystemen: drie eenvoudige stukken. Deel 4: Inleiding tot de planner (vertaling)