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å =)
Planlægning: Feedbackkø på flere niveauer
I dette foredrag vil vi tale om problemerne med at udvikle en af de mest berømte tilgange til
planlægning, som kaldes Feedbackkø på flere niveauer (MLFQ). MLFQ-planlæggeren blev først beskrevet i 1962 af Fernando J. Corbató i et system kaldet
Kompatibelt tidsdelingssystem (CTSS). Disse værker (inklusive senere arbejde på
Multics) blev efterfølgende nomineret til Turing Award. Planlæggeren var
efterfølgende forbedret og fået det udseende, der allerede findes i
nogle moderne systemer.
MLFQ-algoritmen forsøger at løse 2 grundlæggende overlappende problemer.
For det første, forsøger den at optimere ekspeditionstiden, som, som vi diskuterede i det forrige foredrag, er optimeret af metoden med at starte i begyndelsen af køen mest
korte opgaver. OS ved dog ikke, hvor længe en bestemt proces vil køre, og dette
nødvendig viden til driften af SJF, STCF algoritmerne. For det andet, MLFQ prøver
gør systemet responsivt for brugerne (for eksempel for dem, der sidder og
stirre på skærmen og venter på, at opgaven er færdig) og dermed minimere tiden
respons. Desværre forbedrer algoritmer som RR responstiden, men ekstremt
have en dårlig indvirkning på ekspeditionstidsmetrikken. Derfor vores problem: Hvordan designer man
en skemalægger, der vil opfylde vores krav uden at vide noget om
karakteren af processen generelt? Hvordan kan planlæggeren lære karakteristika ved opgaver,
som den lancerer og dermed træffe bedre planlægningsbeslutninger?
Essensen af problemet: Hvordan planlægger man indstillingen af opgaver uden perfekt viden?
Hvordan man designer en skemalægger, der samtidig minimerer responstiden
til interaktive opgaver og minimerer samtidig ekspeditionstid uden at vide det
viden om opgavens udførelsestid?
Bemærk: vi lærer af tidligere begivenheder
MLFQ-køen er et glimrende eksempel på et system, der lærer af
tidligere begivenheder for at forudsige fremtiden. Lignende tilgange er ofte
findes i OS (Og mange andre grene af datalogi, herunder grene
hardware-forudsigelser og caching-algoritmer). Lignende ture
udløses, når opgaver har adfærdsfaser og dermed er forudsigelige.
Du bør dog være forsigtig med denne teknik, fordi forudsigelser er meget nemme
kan vise sig at være forkert og få systemet til at træffe værre beslutninger end
ville være uden viden overhovedet.
MLFQ: Grundlæggende regler
Lad os se på de grundlæggende regler for MLFQ-algoritmen. Og selvom implementeringer af denne algoritme
Der er flere, de grundlæggende tilgange ligner hinanden.
I den implementering, vi skal se på, vil MLFQ have flere
separate køer, som hver vil have en forskellig prioritet. Når som helst,
en opgave klar til udførelse er i én kø. MLFQ bruger prioriteter,
at beslutte, hvilken opgave der skal køres til udførelse, dvs. opgave med højere
prioritet (opgave fra køen med højest prioritet) vil blive lanceret først
kø.
Selvfølgelig kan der være mere end én opgave i en given kø, så
så de vil have samme prioritet. I dette tilfælde vil mekanismen blive brugt
RR for at planlægge en kørsel blandt disse opgaver.
Således når vi frem til to grundlæggende regler for MLFQ:
- Regel 1: Hvis prioritet(A) > Prioritet(B), vil opgave A blive lanceret (B vil ikke)
- Regel 2: Hvis prioritet(A) = Prioritet(B), startes A&B ved hjælp af RR
Baseret på ovenstående er nøgleelementerne til planlægning af MLFQ
er prioriteter. I stedet for at give en fast prioritet til hver
opgave, ændrer MLFQ sin prioritet afhængigt af den observerede adfærd.
For eksempel, hvis en opgave konstant kaster arbejde på CPU'en, mens den venter på tastaturinput,
MLFQ vil holde procesprioriteten høj, fordi det er sådan
en interaktiv proces burde fungere. Hvis opgaven derimod konstant er og
bruger CPU meget over en lang periode, vil MLFQ sænke den
en prioritet. Således vil MLFQ studere adfærden af processer, mens de kører
og bruge adfærd.
Lad os tegne et eksempel på, hvordan køerne kan se ud på et tidspunkt
tid og så får du noget som dette:
I denne ordning er 2 processer A og B i den højeste prioritetskø. Behandle
C er et sted i midten, og proces D er helt sidst i køen. Ifølge ovenstående
Ifølge beskrivelserne af MLFQ-algoritmen vil planlæggeren kun udføre opgaver med den højeste
prioritet efter RR, og opgave C, D vil være uden arbejde.
Naturligvis vil et statisk snapshot ikke give et fuldstændigt billede af, hvordan MLFQ fungerer.
Det er vigtigt at forstå præcis, hvordan billedet ændrer sig over tid.
Forsøg 1: Sådan ændrer du prioritet
På dette tidspunkt skal du beslutte, hvordan MLFQ vil ændre prioritetsniveauet
opgaver (og dermed opgavens placering i køen), efterhånden som den skrider frem gennem sin livscyklus. Til
dette er nødvendigt for at huske arbejdsgangen: en vis mængde
interaktive opgaver med kort køretid (og dermed hyppig udgivelse
CPU) og flere langvarige opgaver, der bruger CPU'en hele deres arbejdstid, mens
Svartid er ikke vigtig for sådanne opgaver. Og på denne måde kan du gøre dit første forsøg
implementer MLFQ-algoritmen med følgende regler:
- Regel 3: Når en opgave kommer ind i systemet, placeres den i køen med den højeste
- prioritet.
- Regel 4a: Hvis en opgave bruger hele det tildelte tidsvindue, så er det
- prioritet reduceres.
- Regel 4b: Hvis en opgave frigiver CPU'en, før dens tidsvindue udløber, så er den
- forbliver med samme prioritet.
Eksempel 1: Enkelt langvarig opgave
Som det ses i dette eksempel, er optagelsesopgaven sat med den højeste
prioritet. Efter et tidsvindue på 10 ms, degraderes processen i prioritet
planlægger. Efter næste tidsvindue degraderes opgaven endelig til
laveste prioritet i systemet, hvor det forbliver.
Eksempel 2: Leverede en kort opgave
Lad os nu se et eksempel på, hvordan MLFQ vil forsøge at nærme sig SJF. I det
for eksempel to opgaver: A, som er en langvarig opgave konstant
optager CPU og B, hvilket er en kort interaktiv opgave. Formode
at A allerede havde arbejdet i nogen tid, da opgave B ankom.
Denne graf viser resultaterne af scenariet. Opgave A, som enhver opgave,
CPU-brug var helt i bund. Opgave B vil ankomme til tidspunktet T=100 og vil
placeret i den højeste prioritetskø. Da dens driftstid er kort, altså
den vil fuldføre, før den når den sidste kø.
Ud fra dette eksempel skal hovedmålet med algoritmen forstås: da algoritmen ikke gør det
ved, om en opgave er lang eller kort, så antager han først og fremmest, at opgaven
kort og giver den højeste prioritet. Hvis det er en meget kort opgave, så
det vil blive afsluttet hurtigt, ellers hvis det er en lang opgave, vil den bevæge sig langsomt
prioritet ned og vil snart bevise, at hun faktisk er en lang opgave, der ikke gør det
kræver et svar.
Eksempel 3: Hvad med I/O?
Lad os nu se på et I/O-eksempel. Som det fremgår af regel 4b,
hvis en proces frigiver processoren uden at bruge al dens processortid,
så forbliver den på samme prioritetsniveau. Hensigten med denne regel er ret enkel
- hvis det interaktive job udfører mange I/O-operationer, for eksempel at vente
fra brugertasten eller musetrykkene, vil en sådan opgave frigøre processoren
før det tildelte vindue. Vi vil ikke sænke prioriteten af en sådan opgave,
og dermed vil det forblive på samme niveau.
Dette eksempel viser, hvordan algoritmen vil fungere med sådanne processer - interaktivt job B, som kun behøver CPU i 1 ms før udførelse
I/O-proces og langvarig Job A, som bruger al sin tid på at bruge CPU'en.
MLFQ holder proces B på højeste prioritet, fordi den fortsætter
frigive CPU'en. Hvis B er en interaktiv opgave, så har algoritmen opnået
Dit mål er at køre interaktive opgaver hurtigt.
Problemer med den nuværende MLFQ-algoritme
I de foregående eksempler byggede vi en grundlæggende version af MLFQ. Og det lader til, at han
gør sit arbejde godt og ærligt, og fordeler CPU-tiden rimeligt imellem
lange opgaver og tillader korte eller store opgaver
arbejde på I/O hurtigt. Desværre indeholder denne tilgang flere
alvorlige problemer.
For det første, problemet med sult: hvis systemet har mange interaktive
opgaver, så vil de bruge al processortiden og dermed ikke en eneste i lang tid
opgaven vil ikke kunne udføres (de sulter).
For det andet, kunne smarte brugere skrive deres programmer, så
narre skemalæggeren. Bedrag ligger i at gøre noget for at tvinge
Planlæggeren giver processen mere CPU-tid. Algoritme det
beskrevet ovenfor er ret sårbar over for lignende angreb: før tidsvinduet er praktisk talt
afsluttet, skal du udføre en I/O-operation (for nogle, uanset hvilken fil)
og dermed frigøre CPU'en. Sådan adfærd vil tillade dig at forblive i det samme
selve køen og igen få en større procentdel af CPU-tid. Hvis du gør
dette er korrekt (eksekver f.eks. 99% af vinduestiden, før du frigiver CPU'en),
sådan en opgave kan simpelthen monopolisere processoren.
Endelig kan et program ændre sin adfærd over tid. De opgaver
som brugte CPU'en kan blive interaktiv. I vores eksempel, lignende
opgaver vil ikke modtage den behandling, de fortjener fra planlæggeren, som andre ville
(indledende) interaktive opgaver.
Spørgsmål til publikum: hvilke angreb på planlæggeren kunne udføres i den moderne verden?
Forsøg 2: Stigende prioritet
Lad os prøve at ændre reglerne og se, om vi kan undgå problemer med
faste. Hvad kan vi gøre for at sikre, at relateret
CPU-opgaver vil få deres tid (selvom ikke længe).
Som en simpel løsning på problemet kan du foreslå periodisk
højne prioriteringen af alle sådanne opgaver i systemet. Der er mange måder
For at opnå dette, lad os prøve at implementere noget simpelt som et eksempel: oversæt
alle opgaver får straks højeste prioritet, derfor den nye regel:
- Rule5: Efter en vis periode S flyttes alle opgaver i systemet til den højeste kø.
Vores nye regel løser to problemer på én gang. Først processerne
er garanteret ikke at sulte: opgaver, der er i højeste prioritet, vil blive delt
CPU-tid i henhold til RR-algoritmen og dermed vil alle processer modtage
CPU tid. For det andet, hvis en proces, der tidligere blev brugt
kun processoren bliver interaktiv, den forbliver i køen med den højeste
prioritet efter at have modtaget en engangsforhøjelse af prioritet til den højeste.
Lad os se på et eksempel. I dette scenarie skal du overveje en proces, der bruger
CPU og to interaktive, korte processer. Til venstre i figuren viser figuren adfærden uden prioriteret forfremmelse, og dermed begynder den langvarige opgave at sulte efter, at to interaktive opgaver er kommet i systemet. I figuren til højre udføres en prioritetsforøgelse hver 50 ms og dermed er alle processer garanteret at modtage CPU-tid og vil blive lanceret periodisk. 50ms i dette tilfælde tages som et eksempel; i virkeligheden er dette tal lidt højere.
Det er klart, at tilføjelse af den periodiske stigningstid S fører til
et logisk spørgsmål: hvilken værdi skal sættes? En af de hæderkronede
systemingeniører John Ousterhout kaldte sådanne mængder i systemer som voo-doo
konstant, da de på en eller anden måde krævede sort magi for korrekt
udstiller. Og desværre har S sådan en duft. Hvis du også indstiller værdien
store - lange opgaver vil begynde at sulte. Og hvis du indstiller værdien for lavt,
Interaktive opgaver vil ikke modtage korrekt CPU-tid.
Forsøg 3: Bedre regnskab
Nu har vi et andet problem at løse: hvordan ikke
lade vores planlægger blive narre? Det er de mennesker, der er skyld i denne mulighed
reglerne 4a, 4b, som tillader et job at bevare prioritet, hvilket frigør processoren
inden den fastsatte tid udløber. Hvordan skal man håndtere dette?
Løsningen i dette tilfælde kan betragtes som en bedre opgørelse af CPU-tid på hver
MLFQ niveau. I stedet for at glemme den tid programmet brugte
processor for den tildelte periode, skal den tages i betragtning og gemmes. Efter
processen har brugt sin tildelte tid, bør den degraderes til den næste
prioritetsniveau. Nu er det ligegyldigt, hvordan processen vil bruge sin tid - hvordan
konstant at regne på processoren eller som et antal opkald. Dermed,
regel 4 skal omskrives til følgende form:
- Rule4: Efter at en opgave har brugt sin tildelte tid i den aktuelle kø (uanset hvor mange gange den frigjorde CPU'en), sænkes opgavens prioritet (den flytter ned i køen).
Lad os se på et eksempel:
»
Figuren viser, hvad der sker, hvis du forsøger at narre planlæggeren, f.eks
hvis det var med de tidligere regler 4a, 4b ville resultatet til venstre blive opnået. Glædelig ny
reglen er resultatet til højre. Før beskyttelse kunne enhver proces kalde I/O før færdiggørelse og
dominerer således CPU'en, efter at have aktiveret beskyttelse, uanset adfærd
I/O vil han stadig rykke ned i køen og dermed ikke være i stand til uærligt
overtage CPU-ressourcer.
Forbedring af MLFQ og andre problemer
Med ovenstående forbedringer følger nye problemer: et af de vigtigste
Spørgsmål - hvordan parametrisere en sådan planlægger? De der. Hvor meget skal det være
køer? Hvad skal størrelsen af programvinduet være i køen? Hvordan
Programprioriteten bør ofte øges for at undgå sult og
tage højde for ændringen i programmets adfærd? Der er ikke noget enkelt svar på disse spørgsmål
svar og kun eksperimenter med belastninger og efterfølgende konfiguration
planlægger kan føre til en tilfredsstillende balance.
For eksempel giver de fleste MLFQ-implementeringer dig mulighed for at tildele forskellige
tidsintervaller for forskellige køer. Normalt højprioriterede køer
korte intervaller er ordineret. Disse køer består af interaktive opgaver,
at skifte mellem, hvilket er ret følsomt og bør tage 10 eller mindre
Frk. I modsætning hertil består køer med lav prioritet af langvarige opgaver, der bruger
CPU. Og i dette tilfælde passer lange tidsintervaller meget godt (100ms).
I dette eksempel er der 2 opgaver, der fungerede i højprioritetskø 20
ms, opdelt i 10ms vinduer. 40ms i midterkøen (20ms vindue) og i lav prioritet
Køtidsvinduet blev 40 ms, hvor opgaver afsluttede deres arbejde.
Solaris OS-implementeringen af MLFQ er en klasse af tidsdelingsplanlæggere.
Planlæggeren vil levere et sæt tabeller, der definerer nøjagtigt, som det skal
prioriteringen af processen ændrer sig i løbet af dens liv, hvad skal størrelsen være
tildelt vindue, og hvor ofte du skal hæve opgaveprioriteterne. Administrator
systemer kan interagere med denne tabel og få skemalæggeren til at opføre sig
anderledes. Som standard har denne tabel 60 køer med en gradvis stigning
vinduesstørrelse fra 20 ms (høj prioritet) til flere hundrede ms (lav prioritet), og
også med et boost af alle opgaver en gang i sekundet.
Andre MLFQ-planlæggere bruger ikke en tabel eller nogen specifik
regler, der er beskrevet i dette foredrag, derimod beregner de prioriteringer vha
matematiske formler. For eksempel bruger FreeBSD-planlæggeren en formel for
beregne den aktuelle prioritet af en opgave ud fra, hvor lang processen er
brugt CPU. Derudover falder CPU-forbruget over tid og så
En stigende prioritering sker således noget anderledes end beskrevet ovenfor. Det er rigtigt
kaldet henfaldsalgoritmer. Siden version 7.1 har FreeBSD brugt ULE-planlæggeren.
Endelig har mange planlæggere andre funktioner. For eksempel nogle
planlæggere reserverer de højeste niveauer til driften af operativsystemet og dermed
Ingen brugerproces kan således få højeste prioritet i
system. Nogle systemer giver dig mulighed for at give råd til at hjælpe
planlæggeren kan prioritere korrekt. For eksempel ved at bruge kommandoen rart
du kan øge eller mindske en opgaves prioritet og dermed øge eller
reducere programmets chancer for at bruge CPU-tid.
MLFQ: Resumé
Vi har beskrevet en planlægningstilgang kaldet MLFQ. Hans navn
indesluttet i princippet om drift - den har flere køer og bruger feedback
at bestemme opgaveprioritet.
Den endelige udformning af reglerne vil være som følger:
- Rule1: Hvis prioritet(A) > Prioritet(B), vil opgave A blive lanceret (B vil ikke)
- Rule2: Hvis prioritet(A) = Prioritet(B), startes A&B ved hjælp af RR
- Rule3: Når en opgave kommer ind i systemet, placeres den i den højeste prioritetskø.
- Rule4: Efter at en opgave har brugt sin tildelte tid i den aktuelle kø (uanset hvor mange gange den frigjorde CPU'en), sænkes opgavens prioritet (den flytter ned i køen).
- Rule5: Efter en vis periode S flyttes alle opgaver i systemet til den højeste kø.
MLFQ er interessant af følgende grund - i stedet for at kræve viden om
opgavens art på forhånd studerer algoritmen den tidligere adfærd af opgaven og sætene
prioriteringer i overensstemmelse hermed. Således forsøger han at sidde på to stole på én gang - for at opnå produktivitet til små opgaver (SJF, STCF) og for ærligt at løbe langt,
CPU-indlæsningsjob. Derfor er mange systemer, inklusive BSD og deres derivater,
Solaris, Windows, Mac bruger en form for algoritme som skemalægger
MLFQ som udgangspunkt.
Yderligere materialer:
- (Computing)
Kilde: www.habr.com