Introduksjon til operativsystemer
Hei Habr! Jeg vil gjerne gjøre deg oppmerksom på en serie artikler-oversettelser av en interessant litteratur etter min mening - OSTEP. Dette materialet diskuterer ganske dypt arbeidet til unix-lignende operativsystemer, nemlig arbeid med prosesser, ulike planleggere, minne og andre lignende komponenter som utgjør et moderne OS. Du kan se originalen av alt materiale her . Vær oppmerksom på at oversettelsen ble gjort uprofesjonelt (ganske fritt), men jeg håper jeg beholdt den generelle betydningen.
Laboratoriearbeid om dette emnet finner du her:
Andre deler:
Du kan også sjekke kanalen min på =)
Introduksjon til Scheduler
Essensen av problemet: Hvordan utvikle en planleggerpolicy
Hvordan bør de underliggende planleggingspolitikkrammene utformes? Hva bør være de viktigste forutsetningene? Hvilke beregninger er viktige? Hvilke grunnleggende teknikker ble brukt i tidlige datasystemer?
Arbeidsbelastningsforutsetninger
Før vi diskuterer mulige retningslinjer, la oss først gjøre noen forenklede digresjoner om prosessene som kjører i systemet, som samlet kalles arbeidsmengde. Å definere arbeidsmengden er en kritisk del av bygningspolicyer, og jo mer du vet om arbeidsbelastningen, jo bedre policy kan du skrive.
La oss gjøre følgende antakelser om prosessene som kjører i systemet, noen ganger også kalt jobber (oppgaver). Nesten alle disse antakelsene er ikke realistiske, men er nødvendige for tankeutvikling.
- Hver oppgave kjører like lang tid,
- Alle oppgaver settes samtidig,
- Den tildelte oppgaven fungerer til den er fullført,
- Alle oppgaver bruker kun CPU,
- Kjøretiden for hver oppgave er kjent.
Planleggerberegninger
I tillegg til noen forutsetninger om belastningen, trengs et annet verktøy for å sammenligne ulike planleggingspolicyer: planleggerberegninger. En metrikk er bare et mål på noe. Det finnes en rekke beregninger som kan brukes til å sammenligne planleggere.
For eksempel vil vi bruke en metrikk kalt behandlingstid (behandlingstid). Oppgavens behandlingstid er definert som forskjellen mellom oppgavens fullføringstid og oppgavens ankomsttid i systemet.
Tturnaround=Tfullføring-Tarrival
Siden vi antok at alle oppgavene kom samtidig, så Ta=0 og dermed Tt=Tc. Denne verdien vil naturligvis endres når vi endrer forutsetningene ovenfor.
En annen beregning - rettferdighet (rettferdighet, ærlighet). Produktivitet og rettferdighet er ofte motstridende egenskaper i planleggingen. Planleggeren kan for eksempel optimalisere ytelsen, men på bekostning av å vente på at andre oppgaver skal kjøre, og dermed redusere rettferdighet.
FØRST INN FØRST UT (FIFO)
Den mest grunnleggende algoritmen som vi kan implementere kalles FIFO eller førstemann til mølla (inn), førstemann til mølla (ut). Denne algoritmen har flere fordeler: den er veldig enkel å implementere og den passer til alle våre forutsetninger og gjør jobben ganske bra.
La oss se på et enkelt eksempel. La oss si at 3 oppgaver ble satt samtidig. Men la oss anta at oppgave A kom litt tidligere enn alle de andre, så den vil vises i utførelseslisten tidligere enn de andre, akkurat som B i forhold til C. La oss anta at hver av dem vil bli utført i 10 sekunder. Hva vil gjennomsnittlig tid være for å fullføre disse oppgavene i dette tilfellet?
Ved å telle verdiene - 10+20+30 og dele på 3, får vi gjennomsnittlig programgjennomføringstid lik 20 sekunder.
La oss nå prøve å endre våre antakelser. Spesielt antakelse 1 og dermed vil vi ikke lenger anta at hver oppgave tar like lang tid å utføre. Hvordan vil FIFO prestere denne gangen?
Som det viser seg, har forskjellige oppgaveutførelsestider en ekstremt negativ innvirkning på produktiviteten til FIFO-algoritmen. La oss anta at oppgave A vil ta 100 sekunder å fullføre, mens B og C fortsatt vil ta 10 sekunder hver.
Som det fremgår av figuren vil gjennomsnittstiden for systemet være (100+110+120)/3=110. Denne effekten kalles konvoi effekt, når noen kortsiktige forbrukere av en ressurs vil stå i kø etter en storforbruker. Det er som i køen i matbutikken når det står en kunde foran deg med full vogn. Den beste løsningen på problemet er å prøve å bytte kassa eller slappe av og puste dypt.
Korteste jobb først
Er det mulig å løse en lignende situasjon med tunge prosesser? Sikkert. En annen type planlegging kallesKorteste jobb først (SJF). Algoritmen er også ganske primitiv - som navnet tilsier, vil de korteste oppgavene bli lansert først, den ene etter den andre.
I dette eksemplet vil resultatet av å kjøre de samme prosessene være en forbedring i den gjennomsnittlige programomløpstiden, og den vil være lik 50 i stedet for 110, som er nesten 2 ganger bedre.
For den gitte antakelsen om at alle oppgaver kommer samtidig, ser SJF-algoritmen ut til å være den mest optimale algoritmen. Våre antakelser virker imidlertid fortsatt ikke realistiske. Denne gangen endrer vi antakelse 2 og ser denne gangen for oss at oppgaver kan være tilstede når som helst, og ikke alle samtidig. Hvilke problemer kan dette føre til?
La oss forestille oss at oppgave A (100c) kommer først og begynner å bli utført. Ved t=10 kommer oppgavene B og C, som hver vil ta 10 sekunder. Så gjennomsnittlig utførelsestid er (100+(110-10)+(120-10))3 = 103. Hva kan planleggeren gjøre for å forbedre dette?
Korteste tid til fullføring først (STCF)
For å bedre situasjonen utelater vi antakelse 3 om at programmet er lansert og kjører til det er ferdig. I tillegg vil vi trenge maskinvarestøtte og, som du kanskje gjetter, vil vi bruke tidsur å avbryte en løpende oppgave og kontekstbytte. Dermed kan planleggeren gjøre noe i det øyeblikket oppgavene B, C ankommer - slutte å utføre oppgave A og sette oppgavene B og C i prosessering og, etter at de er fullført, fortsette å utføre prosess A. En slik planlegger kalles STCFeller Forebyggende jobb først.
Resultatet av denne planleggeren vil være følgende resultat: ((120-0)+(20-10)+(30-10))/3=50. Dermed blir en slik planlegger enda mer optimal for våre oppgaver.
Metrisk responstid
Så hvis vi vet kjøretiden til oppgavene og at disse oppgavene kun bruker CPU, vil STCF være den beste løsningen. Og en gang i de tidlige tider fungerte disse algoritmene ganske bra. Imidlertid tilbringer brukeren nå mesteparten av tiden sin på terminalen og forventer en produktiv interaktiv opplevelse. Dermed ble en ny metrikk født - responstid (respons).
Responstiden beregnes som følger:
Tresponse=Tfirstrun−Ankomst
For det forrige eksempelet vil således responstiden være: A=0, B=0, C=10 (abg=3,33).
Og det viser seg at STCF-algoritmen ikke er så god i en situasjon hvor det kommer 3 oppgaver samtidig – den må vente til de små oppgavene er helt ferdige. Så algoritmen er bra for behandlingstidsmålingen, men dårlig for interaktivitetsmålingen. Tenk deg om du satt ved en terminal og prøvde å skrive inn tegn i en editor og måtte vente i mer enn 10 sekunder fordi en annen oppgave tok opp CPU-en. Det er ikke særlig hyggelig.
Så vi står overfor et annet problem – hvordan kan vi bygge en planlegger som er følsom for responstid?
Round Robin
En algoritme ble utviklet for å løse dette problemet Round Robin (RR). Grunnideen er ganske enkel: i stedet for å kjøre oppgaver til de er fullført, vil vi kjøre oppgaven i en viss tidsperiode (kalt en tidsdel) og deretter bytte til en annen oppgave fra køen. Algoritmen gjentar arbeidet til alle oppgavene er fullført. I dette tilfellet må kjøretiden til programmet være et multiplum av tiden etter hvilken tidtakeren vil avbryte prosessen. For eksempel, hvis en tidtaker avbryter en prosess hver x=10ms, bør størrelsen på prosessutførelsesvinduet være et multiplum av 10 og være 10,20 eller x*10.
La oss se på et eksempel: ABC-oppgaver kommer samtidig inn i systemet og hver av dem ønsker å kjøre i 5 sekunder. SJF-algoritmen vil fullføre hver oppgave før du starter en annen. I motsetning til dette vil RR-algoritmen med et startvindu = 1s gå gjennom oppgavene som følger (fig. 4.3):
(SJF igjen (dårlig for responstid)
(Round Robin (bra for responstid)
Gjennomsnittlig responstid for RR-algoritmen er (0+1+2)/3=1, mens for SJF (0+5+10)/3=5.
Det er logisk å anta at tidsvinduet er en svært viktig parameter for RR; jo mindre det er, jo høyere responstid. Du bør imidlertid ikke gjøre den for liten, siden kontekstbyttetid også vil spille en rolle i den generelle ytelsen. Dermed er valget av utførelsesvindustid satt av OS-arkitekten og avhenger av oppgavene som er planlagt å bli utført i den. Byttekontekst er ikke den eneste tjenesteoperasjonen som kaster bort tid - det kjørende programmet opererer på mange andre ting, for eksempel ulike cacher, og med hver bryter er det nødvendig å lagre og gjenopprette dette miljøet, som også kan ta mye av tid.
RR er en flott planlegger hvis vi bare snakket om responstidsberegningen. Men hvordan vil oppgavens behandlingstidsmåling oppføre seg med denne algoritmen? Tenk på eksempelet ovenfor, når driftstiden til A, B, C = 5s og ankommer samtidig. Oppgave A avsluttes kl 13, B kl 14, C kl 15 og gjennomsnittlig behandlingstid vil være 14 s. Dermed er RR den dårligste algoritmen for omsetningsmetrikken.
Mer generelle termer er enhver RR-type algoritme rettferdig; den deler CPU-tiden likt mellom alle prosesser. Og dermed er disse beregningene konstant i konflikt med hverandre.
Dermed har vi flere kontrasterende algoritmer og samtidig er det fortsatt flere forutsetninger igjen – at oppgavetiden er kjent og at oppgaven kun bruker CPU.
Blanding med I/O
Først av alt, la oss fjerne antakelse 4 om at prosessen bare bruker CPU; Naturligvis er dette ikke tilfelle, og prosesser kan få tilgang til annet utstyr.
I det øyeblikket en prosess ber om en I/O-operasjon, går prosessen inn i blokkert tilstand og venter på at I/O-en skal fullføres. Hvis I/O sendes til harddisken, kan en slik operasjon ta opptil flere ms eller lenger, og prosessoren vil være inaktiv for øyeblikket. I løpet av denne tiden kan planleggeren okkupere prosessoren med en hvilken som helst annen prosess. Den neste avgjørelsen planleggeren må ta er når prosessen skal fullføre sin I/O. Når dette skjer, vil det oppstå et avbrudd og operativsystemet vil sette prosessen som kalte I/O-en i klar-tilstand.
La oss se på et eksempel på flere problemer. Hver av dem krever 50ms CPU-tid. Den første vil imidlertid få tilgang til I/O hver 10 ms (som også vil bli utført hver 10 ms). Og prosess B bruker ganske enkelt en 50ms prosessor uten I/O.
I dette eksemplet vil vi bruke STCF-planleggeren. Hvordan vil planleggeren oppføre seg hvis en prosess som A startes på den? Han vil gjøre følgende: først vil han fullføre prosess A, og deretter prosess B.
Den tradisjonelle tilnærmingen for å løse dette problemet er å behandle hver 10 ms underoppgave i prosess A som en egen oppgave. Når man starter med STJF-algoritmen, er valget mellom en oppgave på 50 ms og en oppgave på 10 ms åpenbart. Deretter, når deloppgave A er fullført, vil prosess B og I/O startes. Etter at I/O er fullført, vil det være vanlig å starte 10ms prosess A igjen i stedet for prosess B. På denne måten er det mulig å implementere overlapping, hvor CPUen brukes av en annen prosess mens den første venter på I/O. Og som et resultat blir systemet bedre utnyttet - i det øyeblikket interaktive prosesser venter på I/O, kan andre prosesser utføres på prosessoren.
Oraklet er ikke lenger
La oss nå prøve å bli kvitt antagelsen om at kjøretiden for oppgaven er kjent. Dette er generelt den verste og mest urealistiske antagelsen på hele listen. Faktisk, i det gjennomsnittlige ordinære operativsystemet, vet operativsystemet i seg selv veldig lite om utførelsestiden for oppgaver, så hvordan kan du da bygge en planlegger uten å vite hvor lang tid oppgaven vil ta å utføre? Kanskje vi kan bruke noen RR-prinsipper for å løse dette problemet?
Total
Vi så på de grunnleggende ideene til oppgaveplanlegging og så på 2 familier av planleggere. Den første starter den korteste oppgaven først og øker dermed behandlingstiden, mens den andre rives mellom alle oppgavene likt, noe som øker responstiden. Begge algoritmene er dårlige der algoritmene til den andre familien er gode. Vi så også på hvordan parallell bruk av CPU og I/O kan forbedre ytelsen, men løste ikke problemet med OS klarsyn. Og i neste leksjon skal vi se på en planlegger som ser inn i den umiddelbare fortiden og prøver å forutsi fremtiden. Og det kalles tilbakemeldingskø på flere nivåer.
Kilde: www.habr.com