Hyrje në Sistemet Operative

Hej Habr! Do të doja të sjell në vëmendjen tuaj një seri artikujsh-përkthimesh të një letërsie interesante për mendimin tim - OSTEP. Ky material diskuton mjaft thellë punën e sistemeve operative të ngjashme me unix, domethënë punën me proceset, planifikuesit e ndryshëm, memorien dhe komponentët e tjerë të ngjashëm që përbëjnë një OS modern. Këtu mund të shihni origjinalin e të gjitha materialeve këtu. Ju lutem vini re se përkthimi është bërë në mënyrë joprofesionale (mjaft lirisht), por shpresoj se kam ruajtur kuptimin e përgjithshëm.

Punimet laboratorike mbi këtë temë mund të gjenden këtu:

Pjesë të tjera:

Ju gjithashtu mund të shikoni kanalin tim në telegram =)

Planifikimi: Radha e komenteve me shumë nivele

Në këtë leksion do të flasim për problemet e zhvillimit të një prej qasjeve më të famshme
planifikimi, i cili quhet Radha e komenteve me shumë nivele (MLFQ). Planifikuesi MLFQ u përshkrua për herë të parë në 1962 nga Fernando J. Corbató në një sistem të quajtur
Sistemi i përputhshëm i ndarjes së kohës (CTSS). Këto vepra (përfshirë punën e mëvonshme
Multics) u nominuan më pas për çmimin Turing. Planifikuesi ishte
më pas u përmirësua dhe fitoi pamjen që mund të gjendet tashmë në
disa sisteme moderne.

Algoritmi MLFQ përpiqet të zgjidhë 2 probleme themelore të mbivendosjes.
Së pari, përpiqet të optimizojë kohën e kthimit, e cila, siç diskutuam në leksionin e mëparshëm, optimizohet me metodën e fillimit në fillim të radhës më së shumti.
detyra të shkurtra. Sidoqoftë, OS nuk e di se sa do të zgjasë një proces i caktuar, dhe kjo
njohuritë e nevojshme për funksionimin e algoritmeve SJF, STCF. Në radhë të dytë, MLFQ po përpiqet
e bëjnë sistemin të përgjegjshëm për përdoruesit (për shembull, për ata që ulen dhe
shikoni në ekran duke pritur që detyra të përfundojë) dhe kështu minimizoni kohën
përgjigje. Fatkeqësisht, algoritmet si RR përmirësojnë kohën e përgjigjes, por jashtëzakonisht
kanë një ndikim të keq në metrikën e kohës së kthimit. Prandaj problemi ynë: Si të dizajnojmë
një planifikues që do të plotësojë kërkesat tona pa ditur asgjë
natyra e procesit në përgjithësi? Si mund të mësojë planifikuesi karakteristikat e detyrave,
të cilën ajo e lëshon dhe kështu merr vendime më të mira planifikimi?

Thelbi i problemit: Si të planifikoni vendosjen e detyrave pa njohuri të përsosura?
Si të hartoni një planifikues që minimizon njëkohësisht kohën e përgjigjes
për detyra interaktive dhe në të njëjtën kohë minimizon kohën e kthimit pa e ditur
njohuri për kohën e ekzekutimit të detyrës?

Shënim: ne mësojmë nga ngjarjet e mëparshme

Radha MLFQ është një shembull i shkëlqyer i një sistemi që mëson nga
ngjarjet e kaluara për të parashikuar të ardhmen. Qasje të ngjashme janë shpesh
gjendet në OS (Dhe shumë degë të tjera të shkencës kompjuterike, duke përfshirë degët
parashikimet e harduerit dhe algoritmet e memorizimit). Udhëtime të ngjashme
nxiten kur detyrat kanë faza të sjelljes dhe kështu janë të parashikueshme.
Megjithatë, duhet të keni kujdes me këtë teknikë sepse parashikimet janë shumë të lehta
mund të rezultojë i pasaktë dhe ta shtyjë sistemin të marrë vendime më të këqija se
do të ishte fare pa njohuri.

MLFQ: Rregullat themelore

Le të shohim rregullat themelore të algoritmit MLFQ. Dhe megjithëse zbatimet e këtij algoritmi
Ka disa, qasjet themelore janë të ngjashme.
Në zbatimin që do të shikojmë, MLFQ do të ketë disa
radhë të veçanta, secila prej të cilave do të ketë një prioritet të ndryshëm. Kurdo,
një detyrë e gatshme për ekzekutim është në një radhë. MLFQ përdor prioritetet,
për të vendosur se cilën detyrë të ekzekutohet, d.m.th. detyrë me më të lartë
prioriteti (detyra nga radha me përparësinë më të lartë) do të hapet së pari
radhe.
Sigurisht, mund të ketë më shumë se një detyrë në një radhë të caktuar, kështu që
pra do të kenë të njëjtin prioritet. Në këtë rast, mekanizmi do të përdoret
RR për të planifikuar një vrapim midis këtyre detyrave.
Kështu arrijmë në dy rregulla bazë për MLFQ:

Rregulli 1: Nëse prioriteti (A) > Prioriteti (B), detyra A do të nisë (B jo)
Rregulli 2: Nëse prioriteti (A) = Prioriteti (B), A&B fillojnë duke përdorur RR

Bazuar në sa më sipër, elementët kyç për planifikimin e MLFQ
janë prioritete. Në vend që t'i jepni një përparësi fikse secilit
detyrë, MLFQ ndryshon prioritetin e saj në varësi të sjelljes së vëzhguar.
Për shembull, nëse një detyrë është vazhdimisht në punë në CPU ndërsa pret për hyrjen e tastierës,
MLFQ do ta mbajë prioritetin e procesit të lartë sepse kështu
duhet të funksionojë një proces ndërveprues. Nëse, përkundrazi, detyra është vazhdimisht dhe
përdor shumë CPU-në për një periudhë të gjatë, MLFQ do ta ulë atë
një prioritet. Kështu, MLFQ do të studiojë sjelljen e proceseve ndërsa ato janë duke u ekzekutuar
dhe përdorin sjellje.
Le të nxjerrim një shembull se si mund të duken radhët në një moment
koha dhe pastaj ju merrni diçka si kjo:

Në këtë skemë, 2 procese A dhe B janë në radhën e prioritetit më të lartë. Procesi
C është diku në mes, dhe procesi D është në fund të radhës. Sipas sa më sipër
Sipas përshkrimeve të algoritmit MLFQ, planifikuesi do të ekzekutojë detyra vetëm me më të lartat
prioritet sipas RR, dhe detyrat C, D do të jenë pa punë.
Natyrisht, një fotografi statike nuk do të japë një pamje të plotë se si funksionon MLFQ.
Është e rëndësishme të kuptohet saktësisht se si fotografia ndryshon me kalimin e kohës.

Përpjekja 1: Si të ndryshoni përparësinë

Në këtë pikë ju duhet të vendosni se si MLFQ do të ndryshojë nivelin e prioritetit
detyrat (dhe kështu pozicioni i detyrës në radhë) ndërsa ajo përparon gjatë ciklit të saj jetësor. Për
kjo është e nevojshme për të mbajtur parasysh rrjedhën e punës: një sasi të caktuar
detyra interaktive me kohëzgjatje të shkurtra (dhe rrjedhimisht lëshime të shpeshta
CPU) dhe disa detyra të gjata që përdorin CPU-në gjatë gjithë kohës së tyre të punës, ndërsa
Koha e përgjigjes nuk është e rëndësishme për detyra të tilla. Dhe në këtë mënyrë ju mund të bëni provën tuaj të parë
zbatoni algoritmin MLFQ me rregullat e mëposhtme:

Rregulli 3: Kur një detyrë hyn në sistem, ajo vendoset në radhë me më të lartën
prioritet.
Rregulla 4a: Nëse një detyrë përdor të gjithë dritaren kohore të caktuar për të, atëherë ajo
prioriteti zvogëlohet.
Rregulli 4b: Nëse një Detyrë lëshon CPU-në përpara se të skadojë dritarja e saj kohore, atëherë ajo
mbetet me të njëjtin prioritet.

Shembulli 1: Detyrë e vetme afatgjatë

Siç mund të shihet në këtë shembull, detyra e pranimit vendoset me më të lartën
prioritet. Pas një dritareje kohore prej 10 ms, procesi zbret në prioritet
planifikues. Pas dritares së kohës tjetër, detyra më në fund zbret në
prioriteti më i ulët në sistem, ku mbetet.

Shembulli 2: U dha një detyrë e shkurtër

Tani le të shohim një shembull se si MLFQ do të përpiqet t'i afrohet SJF. Në atë
shembull, dy detyra: A, e cila është një detyrë e gjatë në vazhdimësi
duke zënë CPU dhe B, që është një detyrë e shkurtër ndërvepruese. Supozoni
se A kishte punuar tashmë për ca kohë në momentin e mbërritjes së detyrës B.

Ky grafik tregon rezultatet e skenarit. Detyra A, si çdo detyrë,
Përdorimi i CPU-së ishte në fund. Detyra B do të arrijë në kohën T=100 dhe do
vendosur në radhë me prioritet më të lartë. Meqenëse koha e funksionimit të saj është e shkurtër, atëherë
do të përfundojë përpara se të arrijë në radhën e fundit.

Nga ky shembull duhet kuptuar qëllimi kryesor i algoritmit: meqë algoritmi nuk e bën këtë
e di nëse një detyrë është e gjatë apo e shkurtër, atëherë para së gjithash ai supozon se detyra
i shkurtër dhe i jep përparësinë më të lartë. Nëse kjo është një detyrë vërtet e shkurtër, atëherë
do të përfundojë shpejt, përndryshe nëse është një detyrë e gjatë, do të ecë ngadalë
prioritet poshtë dhe së shpejti do të provojë se ajo është me të vërtetë një detyrë e gjatë që nuk e bën
kërkon një përgjigje.

Shembulli 3: Po I/O?

Tani le të shohim një shembull I/O. Siç thuhet në rregullin 4b,
nëse një proces lëshon procesorin pa përdorur të gjithë kohën e tij të procesorit,
atëherë ai mbetet në të njëjtin nivel prioritar. Qëllimi i këtij rregulli është mjaft i thjeshtë
- nëse puna ndërvepruese kryen shumë operacione I/O, për shembull, pritje
nga shtypja e tastit të përdoruesit ose të miut, një detyrë e tillë do të çlirojë procesorin
para dritares së caktuar. Ne nuk do të dëshironim të ulim prioritetin e një detyre të tillë,
dhe kështu do të mbetet në të njëjtin nivel.

Ky shembull tregon se si do të funksionojë algoritmi me procese të tilla - puna interaktive B, e cila ka nevojë vetëm për CPU për 1ms para ekzekutimit
Procesi I/O dhe puna afatgjatë A, e cila e kalon gjithë kohën duke përdorur CPU-në.
MLFQ e mban procesin B në prioritetin më të lartë sepse ai vazhdon
lironi CPU-në. Nëse B është një detyrë ndërvepruese, atëherë algoritmi ka arritur
Qëllimi juaj është të ekzekutoni shpejt detyrat ndërvepruese.

Probleme me algoritmin aktual MLFQ

Në shembujt e mëparshëm kemi ndërtuar një version bazë të MLFQ. Dhe duket se ai
e bën punën e tij mirë dhe me ndershmëri, duke shpërndarë në mënyrë të drejtë kohën e CPU-së
detyra të gjata dhe lejimi i detyrave të shkurtra ose me volum të lartë
punoni në I/O shpejt. Fatkeqësisht, kjo qasje përmban disa
probleme serioze.
Së pari, problemi i urisë: nëse sistemi ka shumë ndërveprues
detyrat, atëherë ata do të konsumojnë të gjithë kohën e procesorit dhe kështu asnjë të vetme për një kohë të gjatë
detyra nuk do të mund të ekzekutohet (ata janë të uritur).

Në radhë të dytë, përdoruesit e zgjuar mund të shkruanin programet e tyre në mënyrë që
mashtroj planifikuesin. Mashtrimi qëndron në të bërit diçka për të detyruar
Planifikuesi i jep procesit më shumë kohë CPU. Algoritmi që
i përshkruar më sipër është mjaft i prekshëm ndaj sulmeve të ngjashme: përpara se dritarja kohore të jetë praktikisht
përfundoi, ju duhet të kryeni një operacion I/O (për disa, pavarësisht nga cili skedar)
dhe kështu çlironi CPU-në. Një sjellje e tillë do t'ju lejojë të qëndroni të njëjtë
vetë radha dhe përsëri merrni një përqindje më të madhe të kohës së CPU. Nëse ju bëni
kjo është e saktë (për shembull, ekzekutoni 99% të kohës së dritares përpara se të lëshoni CPU-në),
një detyrë e tillë thjesht mund të monopolizojë procesorin.

Së fundi, një program mund të ndryshojë sjelljen e tij me kalimin e kohës. Ato detyra
e cila përdor CPU-në mund të bëhet ndërvepruese. Në shembullin tonë, të ngjashme
detyrat nuk do të marrin trajtimin që meritojnë nga programuesi siç do të merrnin të tjerët
detyra ndërvepruese (fillestare).

Pyetje për audiencën: çfarë sulmesh ndaj planifikuesit mund të kryhen në botën moderne?

Përpjekja 2: Rritja e prioritetit

Le të përpiqemi të ndryshojmë rregullat dhe të shohim nëse mund të shmangim problemet me të
agjërimi. Çfarë mund të bëjmë për të siguruar që kjo është e lidhur
Detyrat e CPU-së do të marrin kohën e tyre (edhe nëse jo e gjatë).
Si një zgjidhje e thjeshtë për problemin, ju mund të sugjeroni periodikisht
ngre prioritetin e të gjitha detyrave të tilla në sistem. Ka shumë mënyra
Për ta arritur këtë, le të përpiqemi të zbatojmë diçka të thjeshtë si shembull: përkthejmë
të gjitha detyrave u jepet menjëherë përparësia më e lartë, prandaj rregulli i ri:

Rregulli 5: Pas një periudhe të caktuar S, zhvendosni të gjitha detyrat në sistem në radhën më të lartë.

Rregulli ynë i ri zgjidh dy probleme njëherësh. Së pari, proceset
garantohet se nuk do të vdesin nga uria: detyrat që janë në prioritetin më të lartë do të ndahen
Koha e CPU-së sipas algoritmit RR dhe kështu të gjitha proceset do të marrin
Koha e procesorit. Së dyti, nëse ndonjë proces që përdoret më parë
vetëm procesori bëhet interaktiv, ai do të mbetet në radhë me më të lartën
prioritet pas marrjes së një rritje një herë në prioritet në më të lartën.
Le të shohim një shembull. Në këtë skenar, merrni parasysh një proces duke përdorur

CPU dhe dy procese interaktive, të shkurtra. Në të majtë në figurë, figura tregon sjelljen pa promovim prioritar, dhe kështu detyra e gjatë fillon të vdesë pasi dy detyra ndërvepruese mbërrijnë në sistem. Në figurën në të djathtë, një rritje prioriteti kryhet çdo 50 ms dhe kështu të gjitha proceset janë të garantuara të marrin kohën e CPU-së dhe do të lansohen periodikisht. 50ms në këtë rast merret si shembull; në realitet ky numër është pak më i lartë.
Natyrisht, shtimi i kohës së rritjes periodike S çon në
një pyetje logjike: çfarë vlere duhet vendosur? Një nga të nderuarit
Inxhinierët e sistemeve John Ousterhout i quajtën sasi të tilla në sisteme si voo-doo
konstante, pasi ato në një farë mënyre kërkonin magji të zezë për korrektësi
duke ekspozuar. Dhe, për fat të keq, S ka një aromë të tillë. Nëse vendosni edhe vlerën
detyrat e mëdha - të gjata do të fillojnë të vdesin nga uria. Dhe nëse e vendosni vlerën shumë të ulët,
Detyrat ndërvepruese nuk do të marrin kohën e duhur të CPU-së.

Përpjekja 3: Kontabilitet më i mirë

Tani kemi një problem tjetër për të zgjidhur: si jo
të lejojë që planifikuesi ynë të mashtrohet? Njerëzit që duhet të fajësohen për këtë mundësi janë
rregullat 4a, 4b, të cilat lejojnë që një punë të ruajë përparësinë, duke çliruar procesorin
para skadimit të kohës së caktuar. Si të merreni me këtë?
Zgjidhja në këtë rast mund të konsiderohet një llogaritje më e mirë e kohës së CPU-së për secilën
Niveli MLFQ. Në vend që të harroni kohën e përdorur nga programi
procesori për periudhën e caktuar, duhet të merret parasysh dhe të ruhet. Pas
procesi ka shfrytëzuar kohën e tij të caktuar, ai duhet të zhvendoset në një tjetër
niveli i prioritetit. Tani nuk ka rëndësi se si procesi do ta përdorë kohën e tij - si
duke llogaritur vazhdimisht në procesor ose si një numër thirrjesh. Kështu,
rregulli 4 duhet të rishkruhet në formën e mëposhtme:

Rregulli 4: Pasi një detyrë të ketë përdorur kohën e saj të caktuar në radhën aktuale (pavarësisht se sa herë ka liruar CPU-në), përparësia e asaj detyre ulet (ajo lëviz poshtë radhës).

Le të shohim një shembull:
»

Figura tregon se çfarë ndodh nëse përpiqeni të mashtroni planifikuesin, si p.sh
nëse do të ishte me rregullat e mëparshme 4a, 4b do të fitohej rezultati në të majtë. Gëzuar e re
rregulli është rezultati në të djathtë. Përpara mbrojtjes, çdo proces mund të thërrasë I/O përpara përfundimit dhe
kështu dominojnë CPU-në, pasi mundësojnë mbrojtjen, pavarësisht nga sjellja
I/O, ai do të vazhdojë të lëvizë poshtë në radhë dhe kështu nuk do të jetë në gjendje të bëjë në mënyrë të pandershme
marrin përsipër burimet e CPU-së.

Përmirësimi i MLFQ dhe problemeve të tjera

Me përmirësimet e mësipërme vijnë probleme të reja: një nga kryesoret
Pyetje - si të parametrizohet një planifikues i tillë? Ato. Sa duhet të jetë
radhët? Sa duhet të jetë madhësia e dritares së programit brenda radhës? Si
Prioriteti i programit shpesh duhet të rritet për të shmangur urinë dhe
merrni parasysh ndryshimin në sjelljen e programit? Nuk ka përgjigje të thjeshtë për këto pyetje
përgjigje dhe vetëm eksperimente me ngarkesa dhe konfigurim pasues
planifikuesi mund të çojë në një ekuilibër të kënaqshëm.

Për shembull, shumica e zbatimeve të MLFQ ju lejojnë të caktoni të ndryshme
intervale kohore për radhë të ndryshme. Radhët me prioritet të lartë zakonisht
janë të përshkruara intervale të shkurtra. Këto radhë përbëhen nga detyra ndërvepruese,
ndërrimi ndërmjet të cilit është mjaft i ndjeshëm dhe duhet të marrë 10 ose më pak
Znj. Në të kundërt, radhët me prioritet të ulët përbëhen nga detyra të gjata që përdorin
CPU. Dhe në këtë rast, intervalet e gjata kohore përshtaten shumë mirë (100 ms).

Në këtë shembull ka 2 detyra që funksionuan në radhën 20 me prioritet të lartë
ms, e ndarë në dritare 10 ms. 40 ms në radhën e mesme (dritarja 20 ms) dhe në prioritetin e ulët
Dritarja e kohës së radhës u bë 40 ms ku detyrat përfunduan punën e tyre.

Zbatimi i Solaris OS i MLFQ është një klasë e programuesve të ndarjes së kohës.
Planifikuesi do të sigurojë një grup tabelash që përcaktojnë saktësisht siç duhet
prioriteti i procesit ndryshon gjatë rrjedhës së jetës së tij, cila duhet të jetë madhësia
dritaren e caktuar dhe sa shpesh ju duhet të ngrini prioritetet e detyrave. Administratori
sistemet mund të ndërveprojnë me këtë tabelë dhe të bëjnë që planifikuesi të sillet
ndryshe. Si parazgjedhje, kjo tabelë ka 60 radhë me një rritje graduale
madhësia e dritares nga 20 ms (përparësi e lartë) në disa qindra ms (përparësi e ulët), dhe
gjithashtu me një nxitje të të gjitha detyrave një herë në sekondë.

Planifikuesit e tjerë të MLFQ nuk përdorin një tabelë ose ndonjë specifik
rregullat që përshkruhen në këtë leksion, përkundrazi, llogaritin prioritetet duke përdorur
formulat matematikore. Për shembull, programuesi FreeBSD përdor një formulë për
llogaritni prioritetin aktual të një detyre bazuar në sa kohë është procesi
CPU e përdorur. Përveç kësaj, përdorimi i CPU-së zbehet me kalimin e kohës, dhe kështu
Kështu, rritja e prioritetit ndodh disi ndryshe nga ajo e përshkruar më sipër. Kjo eshte e vertetë
të quajtura algoritme të kalbjes. Që nga versioni 7.1, FreeBSD ka përdorur planifikuesin ULE.

Së fundi, shumë planifikues kanë veçori të tjera. Për shembull, disa
planifikuesit rezervojnë nivelet më të larta për funksionimin e sistemit operativ dhe kështu
Kështu, asnjë proces përdoruesi nuk mund të marrë përparësinë më të lartë në
sistemi. Disa sisteme ju lejojnë të jepni këshilla për të ndihmuar
planifikuesi mund të vendosë saktë prioritetet. Për shembull, duke përdorur komandën bukur
ju mund të rrisni ose ulni përparësinë e një detyre dhe kështu të rrisni ose
zvogëloni shanset e programit për të përdorur kohën e CPU-së.

MLFQ: Përmbledhje

Ne kemi përshkruar një qasje planifikimi të quajtur MLFQ. Emri i tij
i mbyllur në parimin e funksionimit - ka disa radhë dhe përdor reagime
për të përcaktuar prioritetin e detyrës.
Forma përfundimtare e rregullave do të jetë si më poshtë:

Rregulli 1: Nëse prioriteti (A) > Prioriteti (B), detyra A do të nisë (B jo)
Rregulli 2: Nëse prioriteti (A) = Prioriteti (B), A&B fillojnë duke përdorur RR
Rregulli 3: Kur një detyrë hyn në sistem, ajo vendoset në radhën e prioritetit më të lartë.
Rregulli 4: Pasi një detyrë të ketë përdorur kohën e saj të caktuar në radhën aktuale (pavarësisht se sa herë ka liruar CPU-në), përparësia e asaj detyre ulet (ajo lëviz poshtë radhës).
Rregulli 5: Pas një periudhe të caktuar S, zhvendosni të gjitha detyrat në sistem në radhën më të lartë.

MLFQ është interesante për arsyen e mëposhtme - në vend që të kërkojë njohuri rreth
natyra e detyrës paraprakisht, algoritmi studion sjelljen e mëparshme të detyrës dhe vendos
prioritetet në përputhje me rrethanat. Kështu, ai përpiqet të ulet në dy karrige njëherësh - të arrijë produktivitetin për detyra të vogla (SJF, STCF) dhe të vrapojë me ndershmëri gjatë,
Punë të ngarkimit të CPU-së. Prandaj, shumë sisteme, duke përfshirë BSD dhe derivatet e tyre,
Solaris, Windows, Mac përdorin një formë algoritmi si planifikues
MLFQ si bazë.

Materialet shtesë:

Burimi: www.habr.com

Sistemet Operative: Tre Pjesë të Lehta. Pjesa 5: Planifikimi: Radha e komenteve me shumë nivele (përkthim)