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å =)
Planlegging: Tilbakemeldingskø på flere nivåer
I dette foredraget vil vi snakke om problemene med å utvikle en av de mest kjente tilnærmingene til
planlegging, som kalles Tilbakemeldingskø på flere nivåer (MLFQ). MLFQ-planleggeren ble først beskrevet i 1962 av Fernando J. Corbató i et system kalt
Kompatibelt tidsdelingssystem (CTSS). Disse arbeidene (inkludert senere arbeid med
Multics) ble deretter nominert til Turing Award. Planleggeren var
senere forbedret og fått utseendet som allerede finnes i
noen moderne systemer.
MLFQ-algoritmen prøver å løse to grunnleggende overlappende problemer.
Først, prøver den å optimalisere omløpstiden, som, som vi diskuterte i forrige forelesning, er optimalisert av metoden for å starte mest i begynnelsen av køen
korte oppgaver. OS vet imidlertid ikke hvor lenge en bestemt prosess vil kjøre, og dette
nødvendig kunnskap for driften av SJF, STCF algoritmene. Dernest, MLFQ prøver
gjør systemet responsivt for brukere (for eksempel for de som sitter og
stirre på skjermen og venter på at oppgaven skal fullføres) og dermed minimere tiden
respons. Dessverre forbedrer algoritmer som RR responstiden, men ekstremt
ha en dårlig innvirkning på behandlingstidsmålingen. Derav vårt problem: Hvordan designe
en planlegger som vil oppfylle våre krav uten å vite noe om
karakteren av prosessen generelt? Hvordan kan planleggeren lære egenskapene til oppgaver,
som den lanserer og dermed ta bedre planleggingsbeslutninger?
Essensen av problemet: Hvordan planlegge innstillingen av oppgaver uten perfekt kunnskap?
Hvordan designe en planlegger som samtidig minimerer responstiden
for interaktive oppgaver og samtidig minimerer behandlingstiden uten å vite det
kunnskap om oppgavegjennomføringstid?
Merk: vi lærer av tidligere hendelser
MLFQ-køen er et utmerket eksempel på et system som lærer av
tidligere hendelser for å forutsi fremtiden. Lignende tilnærminger er ofte
funnet i OS (Og mange andre grener av informatikk, inkludert grener
maskinvareprediksjoner og hurtigbufferalgoritmer). Lignende turer
utløses når oppgaver har atferdsfaser og dermed er forutsigbare.
Du bør imidlertid være forsiktig med denne teknikken fordi spådommer er veldig enkle
kan vise seg å være feil og føre til at systemet tar dårligere beslutninger enn
ville være uten kunnskap i det hele tatt.
MLFQ: Grunnleggende regler
La oss se på de grunnleggende reglene for MLFQ-algoritmen. Og selv om implementeringer av denne algoritmen
Det er flere, de grunnleggende tilnærmingene er like.
I implementeringen vi skal se på, vil MLFQ ha flere
separate køer, som hver vil ha forskjellig prioritet. Når som helst,
en oppgave klar for utførelse er i én kø. MLFQ bruker prioriteringer,
å bestemme hvilken oppgave som skal kjøres for utførelse, dvs. oppgave med høyere
prioritet (oppgave fra køen med høyest prioritet) vil bli lansert først
kø.
Selvfølgelig kan det være mer enn én oppgave i en gitt kø, så
så de vil ha samme prioritet. I dette tilfellet vil mekanismen bli brukt
RR for å planlegge en kjøring blant disse oppgavene.
Dermed kommer vi til to grunnleggende regler for MLFQ:
- Regel 1: Hvis prioritet (A) > Prioritet (B), vil oppgave A bli lansert (B vil ikke)
- Regel 2: Hvis prioritet(A) = Prioritet(B), startes A&B med RR
Basert på ovenstående, nøkkelelementene for planlegging av MLFQ
er prioriteringer. I stedet for å gi en fast prioritet til hver
oppgave, endrer MLFQ sin prioritet avhengig av den observerte atferden.
For eksempel, hvis en oppgave stadig kaster arbeid på CPU-en mens den venter på tastaturinndata,
MLFQ vil holde prosessprioritet høy fordi det er slik
en interaktiv prosess skal fungere. Hvis tvert imot oppgaven er konstant og
bruker CPU mye over en lang periode, vil MLFQ senke den
En prioritet. Dermed vil MLFQ studere oppførselen til prosesser mens de kjører
og bruksatferd.
La oss tegne et eksempel på hvordan køene kan se ut på et tidspunkt
tid og så får du noe sånt som dette:
I denne ordningen er 2 prosesser A og B i høyest prioritert kø. Prosess
C er et sted i midten, og prosess D er helt på slutten av køen. I følge ovenstående
I henhold til beskrivelsene av MLFQ-algoritmen, vil planleggeren utføre oppgaver bare med den høyeste
prioritet etter RR, og oppgavene C, D vil stå uten arbeid.
Naturligvis vil ikke et statisk øyeblikksbilde gi et fullstendig bilde av hvordan MLFQ fungerer.
Det er viktig å forstå nøyaktig hvordan bildet endres over tid.
Forsøk 1: Hvordan endre prioritet
På dette tidspunktet må du bestemme hvordan MLFQ vil endre prioritetsnivået
oppgaver (og dermed oppgavens plassering i køen) etter hvert som den skrider frem gjennom livssyklusen. Til
dette er nødvendig for å huske på arbeidsflyten: en viss mengde
interaktive oppgaver med kort kjøretid (og dermed hyppig utgivelse
CPU) og flere langvarige oppgaver som bruker CPU hele arbeidstiden, mens
Responstid er ikke viktig for slike oppgaver. Og på denne måten kan du gjøre ditt første forsøk
implementer MLFQ-algoritmen med følgende regler:
- Regel 3: Når en oppgave kommer inn i systemet, plasseres den i køen med den høyeste
- prioritet.
- Regel 4a: Hvis en oppgave bruker hele tidsvinduet som er tildelt den, så er det
- prioritet reduseres.
- Regel 4b: Hvis en oppgave frigir CPU-en før tidsvinduet utløper, vil det
- forblir med samme prioritet.
Eksempel 1: Enkelt langvarig oppgave
Som man ser i dette eksempelet er opptaksoppgaven satt med høyest
prioritet. Etter et tidsvindu på 10 ms, degraderes prosessen i prioritet
planlegger. Etter neste tidsvindu blir oppgaven endelig degradert til
laveste prioritet i systemet, der den forblir.
Eksempel 2: Leverte en kort oppgave
La oss nå se et eksempel på hvordan MLFQ vil prøve å nærme seg SJF. I det
for eksempel to oppgaver: A, som er en langvarig oppgave konstant
opptar CPU og B, som er en kort interaktiv oppgave. Anta
at A allerede hadde jobbet en stund da oppgave B kom.
Denne grafen viser resultatene av scenariet. Oppgave A, som enhver oppgave,
CPU-bruken var helt i bunnen. Oppgave B kommer til tiden T=100 og vil
plassert i køen med høyest prioritet. Siden driftstiden er kort, altså
den vil fullføres før den når den siste køen.
Fra dette eksemplet bør hovedmålet med algoritmen forstås: siden algoritmen ikke gjør det
vet om en oppgave er lang eller kort, så antar han først og fremst at oppgaven
kort og gir den høyeste prioritet. Hvis dette er en veldig kort oppgave, da
det vil bli fullført raskt, ellers hvis det er en lang oppgave, vil den bevege seg sakte
prioritet ned og vil snart bevise at hun virkelig er en lang oppgave som ikke gjør det
krever svar.
Eksempel 3: Hva med I/O?
La oss nå se på et I/O-eksempel. Som det fremgår av regel 4b,
hvis en prosess frigir prosessoren uten å bruke all prosessortiden,
da forblir den på samme prioriteringsnivå. Hensikten med denne regelen er ganske enkel
- hvis den interaktive jobben utfører mange I/O-operasjoner, for eksempel venting
fra brukertasten eller musetrykkene vil en slik oppgave frigjøre prosessoren
før det tildelte vinduet. Vi ønsker ikke å redusere prioritet til en slik oppgave,
og dermed vil den forbli på samme nivå.
Dette eksemplet viser hvordan algoritmen vil fungere med slike prosesser - interaktiv jobb B, som bare trenger CPU i 1 ms før utførelse
I/O-prosess og langvarig jobb A, som bruker all sin tid på å bruke CPU.
MLFQ holder prosess B på høyeste prioritet fordi den fortsetter
slipp CPUen. Hvis B er en interaktiv oppgave, har algoritmen oppnådd
Målet ditt er å kjøre interaktive oppgaver raskt.
Problemer med gjeldende MLFQ-algoritme
I de forrige eksemplene bygde vi en grunnleggende versjon av MLFQ. Og det ser ut til at han
gjør jobben sin godt og ærlig, og fordeler CPU-tiden rimelig mellom
lange oppgaver og tillate korte eller store oppgaver
arbeid med I/O raskt. Dessverre inneholder denne tilnærmingen flere
alvorlige problemer.
Først, problemet med sult: hvis systemet har mange interaktive
oppgaver, så vil de forbruke all CPU-tiden og dermed ikke en eneste på lang tid
oppgaven vil ikke kunne utføres (de sulter).
Dernest, kunne smarte brukere skrive programmene sine slik at
lure planleggeren. Bedrag ligger i å gjøre noe for å tvinge
Planleggeren gir prosessen mer CPU-tid. Algoritme det
beskrevet ovenfor er ganske sårbar for lignende angrep: før tidsvinduet er praktisk talt
avsluttet, må du utføre en I/O-operasjon (for noen, uansett hvilken fil)
og dermed frigjøre CPU. Slik oppførsel vil tillate deg å forbli i det samme
selve køen og igjen få en større prosentandel av CPU-tiden. Hvis du gjør
dette er riktig (for eksempel kjør 99 % av vinduet før du slipper CPUen),
en slik oppgave kan ganske enkelt monopolisere prosessoren.
Endelig kan et program endre oppførselen sin over tid. De oppgavene
som brukte CPU kan bli interaktiv. I vårt eksempel, lignende
oppgaver vil ikke motta den behandlingen de fortjener fra planleggeren slik andre ville
(innledende) interaktive oppgaver.
Spørsmål til publikum: hvilke angrep på planleggeren kan utføres i den moderne verden?
Forsøk 2: Økende prioritet
La oss prøve å endre reglene og se om vi kan unngå problemer med
Fasting. Hva kan vi gjøre for å sikre at relatert
CPU-oppgaver vil få sin tid (selv om ikke lenge).
Som en enkel løsning på problemet kan du foreslå med jevne mellomrom
prioritere alle slike oppgaver i systemet. Det er mange måter
For å oppnå dette, la oss prøve å implementere noe enkelt som et eksempel: oversett
alle oppgaver gis umiddelbart høyeste prioritet, derav den nye regelen:
- Rule5: Etter en viss periode S, flytt alle oppgaver i systemet til den høyeste køen.
Vår nye regel løser to problemer samtidig. Først prosessene
vil garantert ikke sulte: oppgaver som er i høyeste prioritet vil bli delt
CPU-tid i henhold til RR-algoritmen og dermed vil alle prosesser motta
CPU-tid. For det andre, hvis noen prosess som tidligere brukes
bare prosessoren blir interaktiv, den forblir i køen med den høyeste
prioritet etter å ha mottatt en engangs økning i prioritet til høyeste.
La oss se på et eksempel. I dette scenariet bør du vurdere én prosess som bruker
CPU og to interaktive, korte prosesser. Til venstre i figuren viser figuren atferden uten prioritert opprykk, og dermed begynner den langvarige oppgaven å sulte etter at to interaktive oppgaver kommer inn i systemet. I figuren til høyre utføres en prioritetsøkning hver 50 ms og dermed er alle prosesser garantert å motta CPU-tid og vil bli lansert med jevne mellomrom. 50ms i dette tilfellet er tatt som et eksempel; i virkeligheten er dette tallet litt høyere.
Å legge til den periodiske økningstiden S fører åpenbart til
et logisk spørsmål: hvilken verdi skal settes? En av de ærede
systemingeniører John Ousterhout kalte slike mengder i systemer som voo-doo
konstant, siden de på en eller annen måte krevde svart magi for korrekt
stiller ut. Og dessverre har S en slik duft. Hvis du setter verdien også
store - lange oppgaver vil begynne å sulte. Og hvis du setter verdien for lavt,
Interaktive oppgaver vil ikke motta riktig CPU-tid.
Forsøk 3: Bedre regnskap
Nå har vi et annet problem å løse: hvordan ikke
la planleggeren vår bli lurt? Det er de som har skylden for denne muligheten
reglene 4a, 4b, som tillater en jobb å beholde prioritet, og frigjør prosessoren
før den tildelte tiden går ut. Hvordan håndtere dette?
Løsningen i dette tilfellet kan betraktes som en bedre regnskapsføring av CPU-tid på hver
MLFQ nivå. I stedet for å glemme tiden programmet brukte
prosessor for den tildelte perioden, bør den tas i betraktning og lagres. Etter
prosessen har brukt opp sin tilmålte tid, bør den degraderes til neste
prioriteringsnivå. Nå spiller det ingen rolle hvordan prosessen vil bruke tiden sin - hvordan
konstant databehandling på prosessoren eller som et antall samtaler. Dermed,
regel 4 skal skrives om til følgende form:
- Rule4: Etter at en oppgave har brukt opp sin tildelte tid i den gjeldende køen (uansett hvor mange ganger den frigjorde CPU-en), senkes prioriteten til den oppgaven (den flytter seg nedover i køen).
La oss se på et eksempel:
»
Figuren viser hva som skjer hvis du prøver å lure planleggeren, for eksempel
hvis det var med de tidligere reglene 4a, 4b ville resultatet til venstre bli oppnådd. Godt nytt
regelen er resultatet til høyre. Før beskyttelse kan enhver prosess kalle I/O før fullføring og
dominerer altså CPU-en, etter å ha aktivert beskyttelse, uavhengig av oppførsel
I/O vil han fortsatt rykke ned i køen og dermed ikke være i stand til å uærlig
ta over CPU-ressurser.
Forbedring av MLFQ og andre problemer
Med forbedringene ovenfor kommer nye problemer: en av de viktigste
Spørsmål - hvordan parameterisere en slik planlegger? De. Hvor mye skal det være
køer? Hva skal være størrelsen på programvinduet i køen? Hvordan
Programprioritet bør ofte økes for å unngå sult og
ta hensyn til endringen i programatferd? Det finnes ikke noe enkelt svar på disse spørsmålene
svar og kun eksperimenter med belastninger og påfølgende konfigurasjon
planleggeren kan føre til en tilfredsstillende balanse.
For eksempel lar de fleste MLFQ-implementeringer deg tilordne forskjellige
tidsintervaller for ulike køer. Høyprioriterte køer vanligvis
korte intervaller er foreskrevet. Disse køene består av interaktive oppgaver,
veksling mellom som er ganske følsomt og bør ta 10 eller mindre
ms. I kontrast består lavprioriterte køer av langvarige oppgaver som bruker
PROSESSOR. Og i dette tilfellet passer lange tidsintervaller veldig bra (100ms).
I dette eksemplet er det 2 oppgaver som fungerte i høyprioritetskø 20
ms, delt inn i 10ms vinduer. 40ms i midtkøen (20ms vindu) og i lav prioritet
Køtidsvinduet ble 40 ms der oppgavene fullførte arbeidet sitt.
Solaris OS-implementeringen av MLFQ er en klasse med tidsdelingsplanleggere.
Planleggeren vil gi et sett med tabeller som definerer nøyaktig slik den skal
prioriteringen av prosessen endres i løpet av livet, hva skal være størrelsen
tildelt vindu og hvor ofte du trenger å øke oppgaveprioriteringene. Administrator
systemer kan samhandle med denne tabellen og få planleggeren til å oppføre seg
annerledes. Som standard har denne tabellen 60 køer med en gradvis økning
vindusstørrelse fra 20 ms (høy prioritet) til flere hundre ms (lav prioritet), og
også med et løft av alle oppgaver en gang i sekundet.
Andre MLFQ-planleggere bruker ikke en tabell eller noe spesifikt
regler som er beskrevet i denne forelesningen, tvert imot, de beregner prioriteringer vha
matematiske formler. For eksempel bruker FreeBSD-planleggeren en formel for
beregne gjeldende prioritet til en oppgave basert på hvor lang prosessen er
brukt CPU. I tillegg avtar CPU-bruken over tid, og så
Økende prioritering skjer dermed noe annerledes enn beskrevet ovenfor. Dette er sant
kalt forfallsalgoritmer. Siden versjon 7.1 har FreeBSD brukt ULE-planleggeren.
Endelig har mange planleggere andre funksjoner. For eksempel noen
planleggere reserverer de høyeste nivåene for driften av operativsystemet og dermed
Dermed kan ingen brukerprosess få høyeste prioritet i
system. Noen systemer lar deg gi råd for å hjelpe
planleggeren kan prioritere riktig. For eksempel ved å bruke kommandoen fint
du kan øke eller redusere prioritet til en oppgave og dermed øke eller
redusere programmets sjanser for å bruke CPU-tid.
MLFQ: Sammendrag
Vi har beskrevet en planleggingstilnærming kalt MLFQ. Navnet hans
omsluttet av operasjonsprinsippet - den har flere køer og bruker tilbakemelding
for å bestemme oppgaveprioritet.
Den endelige formen for reglene vil være som følger:
- Rule1: Hvis prioritet(A) > Prioritet(B), vil oppgave A bli lansert (B vil ikke)
- Rule2: Hvis prioritet(A) = Prioritet(B), startes A&B med RR
- Rule3: Når en oppgave kommer inn i systemet, plasseres den i den høyeste prioritetskøen.
- Rule4: Etter at en oppgave har brukt opp sin tildelte tid i den gjeldende køen (uansett hvor mange ganger den frigjorde CPU-en), senkes prioriteten til den oppgaven (den flytter seg nedover i køen).
- Rule5: Etter en viss periode S, flytt alle oppgaver i systemet til den høyeste køen.
MLFQ er interessant av følgende grunn - i stedet for å kreve kunnskap om
oppgavens natur på forhånd, algoritmen studerer tidligere oppførsel av oppgaven og settene
prioriteringer deretter. Dermed prøver han å sitte på to stoler samtidig - oppnå produktivitet for små oppgaver (SJF, STCF) og ærlig løpe lenge,
CPU-lastejobber. Derfor vil mange systemer, inkludert BSD og deres derivater,
Solaris, Windows, Mac bruker en eller annen form for algoritme som planlegger
MLFQ som en baseline.
Tilleggsmateriell:
- (databehandling)
Kilde: www.habr.com