Introduktion til operativsystemer
Hej Habr! Jeg vil gerne henlede din opmærksomhed på en række artikler-oversættelser af en interessant litteratur efter min mening - OSTEP. Dette materiale diskuterer ganske dybt arbejdet med unix-lignende operativsystemer, nemlig arbejde med processer, forskellige skemalæggere, hukommelse og andre lignende komponenter, der udgør et moderne OS. Du kan se originalen af alle materialer her . Bemærk venligst, at oversættelsen er lavet uprofessionelt (ganske frit), men jeg håber, at jeg har bevaret den generelle betydning.
Laboratoriearbejde om dette emne kan findes her:
Andre dele:
Du kan også tjekke min kanal på =)
Introduktion til Scheduler
Essensen af problemet: Hvordan man udvikler en planlægningspolitik
Hvordan skal de underliggende planlægningspolitiske rammer udformes? Hvad bør være de vigtigste antagelser? Hvilke målinger er vigtige? Hvilke grundlæggende teknikker blev brugt i tidlige computersystemer?
Arbejdsbelastningsantagelser
Før vi diskuterer mulige politikker, lad os først lave et par simplificerende uddrag om de processer, der kører i systemet, som tilsammen kaldes arbejdsbyrde. At definere arbejdsbyrden er en kritisk del af byggepolitikker, og jo mere du ved om arbejdsbyrden, jo bedre er den politik, du kan skrive.
Lad os gøre følgende antagelser om de processer, der kører i systemet, nogle gange også kaldet job (opgaver). Næsten alle disse antagelser er ikke realistiske, men nødvendige for udviklingen af tænkning.
- Hver opgave kører lige meget tid,
- Alle opgaver stilles samtidigt,
- Den tildelte opgave fungerer indtil den er færdig,
- Alle opgaver bruger kun CPU,
- Løbetiden for hver opgave er kendt.
Planlægningsmålinger
Ud over nogle antagelser om belastningen er der brug for et andet værktøj til at sammenligne forskellige planlægningspolitikker: planlægningsmålinger. En metrik er bare et mål for noget. Der er en række målinger, der kan bruges til at sammenligne skemalæggere.
For eksempel vil vi bruge en metrik kaldet ekspeditionstid (gennemløbstid). Opgavens behandlingstid er defineret som forskellen mellem opgavens gennemførelsestid og opgavens ankomsttid i systemet.
Tturnaround=Tfærdiggørelse-Tarrival
Da vi antog, at alle opgaver kom på samme tid, så Ta=0 og dermed Tt=Tc. Denne værdi vil naturligvis ændre sig, når vi ændrer ovenstående forudsætninger.
En anden metrik - fairness (retfærdighed, ærlighed). Produktivitet og retfærdighed er ofte modsatrettede egenskaber i planlægningen. Planlæggeren kan for eksempel optimere ydeevnen, men på bekostning af at vente på, at andre opgaver kører, og dermed reducere retfærdigheden.
FØRST IN FØRST UD (FIFO)
Den mest grundlæggende algoritme, som vi kan implementere, kaldes FIFO eller først til mølle (ind), først til mølle (ud). Denne algoritme har flere fordele: den er meget nem at implementere, og den passer til alle vores antagelser og gør arbejdet ganske godt.
Lad os se på et simpelt eksempel. Lad os sige, at der blev sat 3 opgaver samtidigt. Men lad os antage, at opgave A ankom lidt tidligere end alle de andre, så den vil dukke op i udførelseslisten tidligere end de andre, ligesom B i forhold til C. Lad os antage, at hver af dem vil blive udført i 10 sekunder. Hvad vil den gennemsnitlige tid være til at udføre disse opgaver i dette tilfælde?
Ved at tælle værdierne - 10+20+30 og dividere med 3, får vi den gennemsnitlige programudførelsestid svarende til 20 sekunder.
Lad os nu prøve at ændre vores antagelser. Især antagelse 1 og dermed vil vi ikke længere antage, at hver opgave tager lige lang tid at udføre. Hvordan klarer FIFO sig denne gang?
Som det viser sig, har forskellige opgaveudførelsestider en ekstrem negativ indvirkning på FIFO-algoritmens produktivitet. Lad os antage, at opgave A vil tage 100 sekunder at fuldføre, mens B og C stadig vil tage 10 sekunder hver.
Som det fremgår af figuren, vil den gennemsnitlige tid for systemet være (100+110+120)/3=110. Denne effekt kaldes konvoj effekt, når nogle korttidsforbrugere af en ressource vil stå i kø efter en storforbruger. Det er ligesom køen ved købmanden, når der står en kunde foran dig med en fuld vogn. Den bedste løsning på problemet er at prøve at skifte kasseapparatet eller slappe af og trække vejret dybt.
Korteste job først
Er det muligt på en eller anden måde at løse en lignende situation med tunge processer? Sikkert. En anden form for planlægning kaldesKorteste job først (SJF). Dens algoritme er også ret primitiv - som navnet antyder, vil de korteste opgaver blive lanceret først, den ene efter den anden.
I dette eksempel vil resultatet af at køre de samme processer være en forbedring af den gennemsnitlige programgennemløbstid, og den vil være lig med 50 i stedet for 110, hvilket er næsten 2 gange bedre.
For den givne antagelse om, at alle opgaver ankommer på samme tid, ser SJF-algoritmen således ud til at være den mest optimale algoritme. Vores antagelser virker dog stadig ikke realistiske. Denne gang ændrer vi antagelse 2 og forestiller os denne gang, at opgaver kan være til stede når som helst, og ikke alle på samme tid. Hvilke problemer kan dette føre til?
Lad os forestille os, at opgave A (100c) kommer først og begynder at blive udført. Ved t=10 ankommer opgave B og C, som hver vil tage 10 sekunder. Så den gennemsnitlige udførelsestid er (100+(110-10)+(120-10))3 = 103. Hvad kunne planlæggeren gøre for at forbedre dette?
Korteste tid til færdiggørelse først (STCF)
For at forbedre situationen udelader vi antagelse 3 om, at programmet er lanceret og kører indtil det er færdigt. Derudover har vi brug for hardwaresupport, og som du måske kan gætte, vil vi bruge таймер at afbryde en kørende opgave og kontekstskifte. Planlæggeren kan således gøre noget i det øjeblik, opgave B, C ankommer - stoppe med at udføre opgave A og sætte opgave B og C i bearbejdning og, efter deres afslutning, fortsætte med at udføre proces A. En sådan planlægger kaldes STCFeller Forebyggende job først.
Resultatet af denne planlægger vil være følgende resultat: ((120-0)+(20-10)+(30-10))/3=50. Således bliver sådan en planlægger endnu mere optimal til vores opgaver.
Metrisk responstid
Så hvis vi kender opgavernes køretid, og at disse opgaver kun bruger CPU, vil STCF være den bedste løsning. Og en gang i de tidlige tider fungerede disse algoritmer ganske godt. Men brugeren tilbringer nu det meste af sin tid på terminalen og forventer en produktiv interaktiv oplevelse. Således blev en ny metrik født - responstid (respons).
Svartiden beregnes som følger:
Tresponse=Tfirstrun-Tarrival
For det foregående eksempel vil responstiden således være: A=0, B=0, C=10 (abg=3,33).
Og det viser sig, at STCF-algoritmen ikke er så god i en situation, hvor der kommer 3 opgaver på samme tid – den må vente til de små opgaver er helt færdige. Så algoritmen er god for ekspeditionstidsmetrikken, men dårlig for interaktivitetsmetrikken. Forestil dig, hvis du sad ved en terminal og prøvede at skrive tegn i en editor og skulle vente mere end 10 sekunder, fordi en anden opgave tog CPU'en op. Det er ikke særlig behageligt.
Så vi står over for et andet problem - hvordan kan vi bygge en planlægger, der er følsom over for responstid?
Round Robin
En algoritme blev udviklet til at løse dette problem Round Robin (RR). Grundideen er ret simpel: I stedet for at køre opgaver, indtil de er afsluttet, kører vi opgaven i en vis periode (kaldet en tidsudsnit) og skifter derefter til en anden opgave fra køen. Algoritmen gentager sit arbejde, indtil alle opgaver er udført. I dette tilfælde skal programmets køretid være et multiplum af den tid, hvorefter timeren vil afbryde processen. For eksempel, hvis en timer afbryder en proces hver x=10ms, så skal størrelsen af procesudførelsesvinduet være et multiplum af 10 og være 10,20 eller x*10.
Lad os se på et eksempel: ABC-opgaver ankommer samtidigt i systemet, og hver af dem ønsker at køre i 5 sekunder. SJF-algoritmen vil fuldføre hver opgave, før den starter en anden. I modsætning hertil vil RR-algoritmen med et startvindue = 1s gennemgå opgaverne som følger (fig. 4.3):
(SJF igen (dårligt til responstid)
(Round Robin (god til responstid)
Den gennemsnitlige responstid for RR-algoritmen er (0+1+2)/3=1, mens for SJF (0+5+10)/3=5.
Det er logisk at antage, at tidsvinduet er en meget vigtig parameter for RR; jo mindre det er, jo højere er responstiden. Du bør dog ikke gøre det for lille, da kontekstskiftetid også vil spille en rolle for den samlede præstation. Valget af udførelsesvinduetid er således indstillet af OS-arkitekten og afhænger af de opgaver, der er planlagt til at blive udført i den. Skiftkontekst er ikke den eneste serviceoperation, der spilder tid - det kørende program opererer på en masse andre ting, for eksempel forskellige caches, og med hver switch er det nødvendigt at gemme og gendanne dette miljø, hvilket også kan tage en masse tid.
RR er en fantastisk planlægger, hvis vi kun talte om responstid-metrikken. Men hvordan vil opgavens behandlingstidsmåling opføre sig med denne algoritme? Overvej eksemplet ovenfor, når driftstiden for A, B, C = 5s og ankommer på samme tid. Opgave A slutter ved 13, B ved 14, C ved 15 s, og den gennemsnitlige ekspeditionstid vil være 14 s. Således er RR den dårligste algoritme for omsætningsmetrikken.
Mere generelt er enhver RR-type algoritme retfærdig; den deler CPU-tiden ligeligt mellem alle processer. Og derfor er disse målinger konstant i konflikt med hinanden.
Vi har således flere kontrasterende algoritmer og samtidig er der stadig flere forudsætninger tilbage - at opgavetiden er kendt og at opgaven kun bruger CPU'en.
Blanding med I/O
Først og fremmest, lad os fjerne antagelse 4 om, at processen kun bruger CPU'en; naturligvis er dette ikke tilfældet, og processer kan få adgang til andet udstyr.
I det øjeblik en proces anmoder om en I/O-operation, går processen ind i blokeret tilstand og venter på, at I/O'en er fuldført. Hvis I/O sendes til harddisken, kan en sådan operation tage op til flere ms eller længere, og processoren vil være inaktiv i dette øjeblik. I løbet af denne tid kan planlæggeren optage processoren med enhver anden proces. Den næste beslutning, som planlæggeren skal tage, er, hvornår processen vil fuldføre sin I/O. Når dette sker, vil der forekomme en afbrydelse, og operativsystemet vil sætte den proces, der kaldte I/O'en, i klar-tilstand.
Lad os se på et eksempel på flere problemer. Hver af dem kræver 50ms CPU-tid. Den første vil dog få adgang til I/O hver 10 ms (som også vil blive udført hver 10 ms). Og proces B bruger simpelthen en 50ms processor uden I/O.
I dette eksempel vil vi bruge STCF-planlæggeren. Hvordan vil planlæggeren opføre sig, hvis en proces som A startes på den? Han vil gøre følgende: først vil han fuldstændigt udarbejde proces A og derefter proces B.
Den traditionelle tilgang til at løse dette problem er at behandle hver 10 ms underopgave i proces A som en separat opgave. Når man starter med STJF-algoritmen, er valget mellem en 50 ms-opgave og en 10 ms-opgave således oplagt. Derefter, når underopgave A er afsluttet, vil proces B og I/O blive lanceret. Efter at I/O er færdig, vil det være sædvanligt at starte 10ms proces A igen i stedet for proces B. På denne måde er det muligt at implementere overlap, hvor CPU'en bruges af en anden proces, mens den første venter på I/O. Og som et resultat er systemet bedre udnyttet - i det øjeblik, hvor interaktive processer venter på I/O, kan andre processer udføres på processoren.
Oraklet er ikke mere
Lad os nu prøve at slippe af med antagelsen om, at køretiden for opgaven er kendt. Dette er generelt den værste og mest urealistiske antagelse på hele listen. Faktisk ved selve operativsystemet i det gennemsnitlige almindelige OS normalt meget lidt om udførelsestiden for opgaver, så hvordan kan du så bygge en skemalægger uden at vide, hvor lang tid opgaven vil tage at udføre? Måske kunne vi bruge nogle RR-principper til at løse dette problem?
Total
Vi så på de grundlæggende ideer om opgaveplanlægning og så på 2 familier af planlæggere. Den første starter den korteste opgave først og øger dermed ekspeditionstiden, mens den anden rives ligeligt mellem alle opgaver, hvilket øger responstiden. Begge algoritmer er dårlige, hvor den anden families algoritmer er gode. Vi så også på, hvordan parallel brug af CPU og I/O kan forbedre ydeevnen, men løste ikke problemet med OS clairvoyance. Og i den næste lektion vil vi se på en planlægger, der ser ind i den umiddelbare fortid og forsøger at forudsige fremtiden. Og det kaldes multi-level feedback-kø.
Kilde: www.habr.com