Hyrja në sistemet operative

Përshëndetje, Habr! Dua të paraqes para jush një seri artikujsh me përkthime nga një letërsi interesante sipas mendimit tim - OSTEP. Ky material shqyrton mjaft thellë funksionimin e sistemeve operativë të ngjashme me UNIX, domethënë - punën me proceset, planifikuesit e ndryshëm, memorien dhe komponentë të tjerë të ngjashëm që përbëjnë një sistem operativ modern. Origjinali i të gjithë materialeve mund ta shihni këtu këtu. Ju lutem, merrni parasysh se përkthimi është realizuar në mënyrë jo profesionale (mjaft lirshëm), por shpresoj se kuptimi i përgjithshëm e kam ruajtur.

Për laboratorët në këtë lëndë mund të gjeni këtu:

Pjesët e tjera:

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

Planifikimi: Multi-Level Feedback Queue

Në këtë ligjëratë do të flasim për problemet e zhvillimit të një nga qasjet më të njohura për
planifikimin, e cila quhet Multi-Level Feedback Queue (MLFQ). Planifikuesi MLFQ u përshkrua për herë të parë në vitin 1962 nga Fernando J. Corbató në sistemin e quajtur
Compatible Time-Sharing System (CTSS). Këto punime (përfshirë punimet e mëvonshme mbi
Multics) më pas u paraqitën për çmimin Turing. Planifikuesi u
përmirësua më vonë dhe mori formën që mund ta gjejmë tashmë në
disa sisteme moderne.

Algoritmi MLFQ përpiqet të zgjidhë 2 probleme themelore të ndërthurura.
Së pari, ai përpiqet të optimizojë kohën e qarkullimit, e cila siç e analizuam në ligjëratën e kaluar, optimizohet me metodën e nisjes në fillim të radhës së
detyrave më të shkurtra. Megjithatë, OS nuk di se sa kohë do të punojë një proces i caktuar, dhe ky është
njohuri e nevojshme për funksionimin e algoritmeve SJF, STCF. Së dyti, MLFQ përpiqet
ta bëjë sistemin reaktiv për përdoruesit (për shembull ata që qëndrojnë dhe
shikojnë në ekran duke pritur për përfundimin e detyrës) dhe kështu minimalizon kohën
e përgjigjes. Fatkeqësisht, algoritmet si RR zvogëlojnë kohën e përgjigjes, por kanë një efekt të keq të jashtëzakonshëm në metrikën e kohës së qarkullimit. Prandaj, problemi ynë është: Si të projektojmë
një planifikues që do të përmbushë kërkesat tona dhe për më tepër të mos dijë asgjë mbi
naturën e procesit, në përgjithësi? Si do të mësojë planifikuesi karakteristikat e detyrave,
që ai nis dhe kështu të marrë vendime më të mira për planifikimin?
Thelbi i problemit: Si të planifikojmë vendosjen e detyrave pa njohuri të përsosur?

Si të zhvillojmë një planifikues që njëkohësisht minimizon kohën e përgjigjes
për detyrat interaktive dhe gjithashtu minimizon kohën e qarkullimit pa dijeni të njohur
për kohën e ekzekutimit të detyrës?
Shënim: mësojmë nga ngjarjet e mëparshme

Rradha 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ë tilla shpesh
shfaqen në OS (dhe shumë industri të tjera në Informatikë, duke përfshirë degët
e parashikimeve në harduer dhe algoritmet e zbatimit). Qasje të tilla
janë efektive, kur detyrat kanë faza sjelljeje dhe kështu janë të parashikueshme.
aktivohet kur detyrat kanë faza të sjelljes dhe kështu janë të parashikueshme.
Megjithatë, me këtë teknikë duhet të jemi të kujdesshëm, sepse parashikimet janë shumë lehtë
mund të jenë të gabuara dhe të çojnë sistemin në marrjen e vendimeve më të këqija se sa
do të ishin pa njohuri fare.

MLFQ: Rregullat Bazë

Le të shqyrtimi rregullat bazë të algoritmit MLFQ. Edhe pse ekzistojnë disa implementime të këtij algoritmi
qasje themelore janë të ngjashme.
Në implementimin që ne do të shqyrtojmë, në MLFQ do të ketë disa
radhë të veçanta, secila prej të cilave do të ketë përparësi të ndryshme. Në çdo kohë,
detyra, e gatshme për ekzekutim ndodhet në një radhë. MLFQ përdor prioritetet,
për të vendosur se cila detyrë do të ekzekutohet, dmth. detyra me prioritet më të lartë
(detyra nga radhë me prioritet më të lartë) do të ekzekutohet në radhë të parë.
Pa dyshim, në një radhe të caktuar mund të ketë më shumë se një detyrë, kështu
që ato do të kenë të njëjtin prioritet. Në këtë rast do të përdoret mekanizmi
RR për planifikimin e ekzekutimit mes këtyre detyrave.
Kështu arrijmë në dy rregulla themelore për MLFQ:
Rregulli1: Nëse prioriteti(A) > Prioriteti(B), do të ekzekutohet detyra A (B nuk do të ekzekutohet)

Rregulli2: Nëse prioriteti(A) = Prioriteti(B), A dhe B ekzekutohen duke përdorur RR
Duke u bazuar në të mësipërmet, elementët kryesorë për planifikimin MLFQ

janë prioritetet. Në vend që të caktojë një prioritet të fiksuar për çdo
detyrë, MLFQ e ndryshon prioritetin e saj në varësi të sjelljes së vëzhguar.
Për shembull, nëse një detyrë vazhdimisht bllokon punën në CPU duke pritur input nga klaviatura,
MLFQ do të mbajë prioritetin e procesit në një nivel të lartë, sepse kështu
duhet të funksionojë një proces interaktiv. Nëse nga ana tjetër një detyrë përdor vazhdimisht dhe
intensivisht CPU për një periudhë të gjatë, MLFQ do të ulë prioritetin e saj.
Kështu, MLFQ do të studiojë sjelljen e proceseve gjatë punës së tyre
dhe do të shfrytëzojë sjelljet.
Le të vizatojmë një shembull se si mund të duken radhët në një moment të caktuar
të kohës dhe atëherë do të rezultojë diçka si kjo:
Në këtë skemë, 2 procese A dhe B ndodhen në radhën me prioritetin më të lartë. Procesi

C ndodhet diku në mes, ndërsa procesi D në fund të radhës. Sipas përshkrimeve të sipërme
të algoritmit MLFQ, planifikuesi do të ekzekutojë vetëm detyrat me prioritetin më të lartë.
përshkrimeve të algoritmit MLFQ, planifikuesi do të ekzekutojë detyrat vetëm me prioritetin më të lartë.
prioriteti sipas RR, dhe detyrat C, D do të jenë jashtë loje.
Natyrisht, një snapshot statik nuk do të japë një pamje të plotë të mënyrës se si funksionon MLFQ.
Është e rëndësishme të kuptojmë se si ndërron pamja me kalimin e kohës.

Përpjekja 1: Si të ndryshosh prioritetin

Në këtë moment, është e nevojshme të përcaktohet se si MLFQ do të ndryshojë nivelin e prioritetit
të detyrave (dhe kështu pozita e detyrës në radhë) gjatë trajtimit të saj. Për
këtë, është e nevojshme të kemi parasysh procesin e punës: një numër
detyrash interaktive me kohë të shkurtër punimi (dhe kështu lirimin e shpeshtë
të CPU) dhe disa detyra të gjata, të cilat përdorin CPU gjatë gjithë kohës së punës, ndërkohë
koha e përgjigjes për këto detyra nuk ka rëndësi. Dhe kështu mund të bëhet përpjekja e parë
për të implementuar algoritmin MLFQ me rregullat e mëposhtme:

Rregulli 3: Kur një detyrë hyn në sistem, ajo vendoset në radhen me prioritetin më të lartë.
Rregulli 4a: Nëse detyra përdor të gjithë dritaren e saj të caktuar kohore, atëherë prioriteti i saj
ulet.
Rregulli 4b: Nëse detyra lirson CPU përpara se të përfundojë dritarja e saj kohore, atëherë ajo
qëndron me prioritetin e saj të mëparshëm.
Shembulli 1: Një detyrë e gjatë që punon vazhdimisht

Siç shihet në këtë shembull, detyra, kur hyn, vendoset me prioritetin më të lartë.

Pas një dritareje kohe prej 10ms, procesi ulet në prioritet nga planifikuesi.
Pas dritares së ardhshme të kohës, detyra, përfundimisht, ulet në
prioritetin më të ulët në sistem, ku dhe mbetet.
Shembulli 2: Shtimi i një detyre të shkurtër

Tani të shohim një shembull se si MLFQ do të përpiqet të afrojë SJF. Në këtë

shembull, ka dy detyra: A, e cila është një detyrë e gjatë që
përdor vazhdimisht CPU dhe B, e cila është një detyrë e shkurtër interaktive. Le të supozojmë
se A ka punuar për një kohë të caktuar në momentin që ka ardhur detyra B.
Në këtë grafik shihen rezultatet e skenarit. Detyra A, si çdo detyrë,

që përdor CPU del në fund të listës. Detyra B do të mbërrijë në T=100 dhe do të
vendoset në radhen me prioritetin më të lartë. Duke qenë se koha e saj e punës është e shkurtër, ajo
do të përfundojë përpara se të arrijë në radhen e fundit.
Nga ky shembull, duhet kuptuar qëllimi kryesor i algoritmit: përderisa algoritmi nuk

di nëse një detyrë është e gjatë apo e shkurtër, në radhë të parë ai supozon se detyra
do të jetë
e shkurtër dhe i jep prioritetin më të lartë. Nëse është vërtet një detyrë e shkurtër, atëherë
ajo do të kryhet shpejt, përndryshe, nëse është një detyrë e gjatë, do të ecë ngadalë
në prioritetin e poshtëm dhe së shpejti do të tregojë se vërtet është një detyrë e gjatë që nuk
kërkon përgjigje.

Shembulli 3: Çfarë ndodhi me hyrjen-daljen?

Tani shikojmë një shembull me hyrjen-daljen. Siç është thënë në rregullin 4b,
nëse procesi liridon procesorin, pa shfrytëzuar plotësisht kohën e tij të procesorit,
atëherë ai mbetet në nivelin e tij të mëparshëm të prioriteteve. Qëllimi i këtij rregulli është mjaft e thjeshtë
- nëse një detyrë interaktive kryen shumë operacione hyrjeje-daljeje, për shembull, duke pritur
nga përdoruesi të shtypë çelësat ose miun, një detyrë e tillë do të lirojë procesorin
më herët nga koha e caktuar. Ne nuk do të donim ta ulte atë detyrë në prioritet,
dhe kështu ajo do të mbetet në nivelin e saj të mëparshëm.

Ky shembull tregon se si do të funksionojë algoritmi me këto procese - detyrën interaktive B, e cila ka nevojë për CPU vetëm për 1ms para se të kryejë
procesin e hyrjes-daljes dhe detyrën e gjatë A, e cila shfrytëzon të gjithë kohën e saj në CPU.
MLFQ mban procesin B me prioritetin më të lartë, pasi ai vazhdimisht
liron CPU. Nëse B është një detyrë interaktive, atëherë algoritmi në këtë rast ka arritur
qëllimin e tij për të ekzekutuar shpejt detyrat interaktive.

Problemet me algoritmin aktual MLFQ

Në shembujt e mëparshëm kemi ndërtuar një version bazik të MLFQ. Dhe duket se ai
e bën punën e tij mirë dhe me ndershmëri, duke ndarë kohën e procesorit me ndershmëri mes
detyrave të gjata dhe duke lejuar detyrat e shkurtra ose ato që kërkojnë shumë hyrje-dalje
të punojnë shpejt. Fatkeqësisht, kjo qasje ka disa
probleme të rënda.
Së pari, problemi i urisë: nëse në sistem ka shumë
detyra interaktive, ato do të konsumojnë të gjithë kohën e procesorit dhe kështu asnjë detyrë e gjatë
nuk do të ketë mundësi të ekzekutohet (ato janë në uri).

Së dyti, përdoruesit e zgjuar mund të shkruajnë programet e tyre në mënyrë që
të mashtronin planifikuesin. Mashtrimi qëndron në bërjen e diçkaje që të detyrojë
planifikuesin të japë më shumë kohë procesor për procesin.
përshkruar më sipër është krejtësisht i ndjeshëm ndaj sulmeve të tilla: para se të skadojë koha praktike
duhet të kryhet operacioni i hyrjes dhe daljes (me ndonjë, pa rëndësi se cilin skedar)
dhe kështu të çlirohet CPU. Një sjellje e tillë do të lejojë që të mbetet në të njëjtën
radhë dhe përsëri të marrë një përqindje më të madhe të kohës së procesorit. Nëse e bën
këto drejtë (për shembull, të ekzekutohet 99% të kohës së dritares para se të çlirohet CPU),
kjo detyrë përfundimisht mund të monopolizojë procesorin.

Së fundi, programa mund të ndryshojë sjelljen e saj me kalimin e kohës. Atëherë detyrat,
të cilat përdorën CPU, mund të bëhen interaktive. Në shembullin tonë, të tilla
detyra nuk do të marrin trajtim të duhur nga planifikuesi, për shkak se do të merrnin të tjera
(fillestare) detyra interaktive.

Pyetja për sallën: cilat sulme ndaj planifikuesit mund të bëheshin në botën moderne?

Përpjekja 2: Rritja e prioritetit

Të provojmë të ndryshojmë rregullat dhe të shohim nëse do të arrijmë të shmangim problemet me
uriturjen. Çfarë mund të bëjmë për të garantuar që detyrat e
CPU të marrin kohën e tyre (edhe nëse nuk është e gjatë).
Si një zgjidhje e thjeshtë për problemin, mund të propozojmë që herë pas here
të rrisim prioritetin e të gjitha këtyre detyrave në sistem. Ekzistojnë shumë mënyra
për ta arritur këtë, le të përpiqemi të zbatojmë si një shembull diçka të thjeshtë: ta kthejmë
menjëherë të gjithë detyrat në prioritetin më të lartë, prandaj rregulli i ri:

Rregulli 5: Pas kalimit të një periudhe S, të gjithë detyrat në sistem të kalojnë në radhën më të lartë.

Rregulli ynë i ri zgjidh dy probleme njëkohësisht. Së pari, proceset
garantojnë se nuk uritën: detyrat që janë në radhë më të lartë do të ndajë
kohën e procesorit sipas algoritmit RR dhe kështu të gjitha proceset do të marrin
kohën e procesorit. Së dyti, nëse ndonjë proces, i cili më parë përdorte
vetëm procesorin, bëhet interaktiv, ai do të mbetet në radhën me prioritet më të lartë
pas që ka marrë një herë rritjen e prioritetit deri në maksimum.
Le të shqyrtojmë një shembull. Në këtë skenar, le të shqyrtojmë një proces që përdor

CPU dhe dy procese interaktive të shkurtra. Në anën e majtë të figurës, figura tregon sjelljen pa rritje të prioritetit, kështu që një detyrë e gjatë fillon të urdhërohet pas mbërritjes në sistem të dy detyrave interaktive. Në figurën e djathtë, çdo 50ms ndodh një rritje e prioritetit dhe kështu të gjitha proceset sigurojnë kohë për procesorin dhe do të fillojnë periodikisht. 50ms në këtë rast është marrë për shembull, realisht ky numër është pak më i madh.
E dukshme është se shtimi i kohës periodike të rritjes S sjell
çështjen e ligjshme: çfarë vlere duhet të vendoset? Një nga inxhinierët e njohur
sistemor John Ousterhout e quante këto vlera në sisteme si voo-doo
konstante, pasi ato në një farë mënyre kërkonin magji të zezë për rregullimin e saktë.
Dhe fatkeqësisht S ka një aromë të tillë. Nëse vendosim vlerën shumë
të lartë — detyrat e gjata do të fillojnë të urdhërohen. Ndërsa nëse vendosim një vlerë shumë të ulët,
detyrat interaktive nuk do të marrin kohën e duhur për procesorin.

Përpjekja 3: Rregjistrimi më i mirë

Tani kemi një problem tjetër që duhet të zgjidhim: si të mos
lejojmë që planifikuesi ynë të mashtrohet? Fajtorët për këtë mundësi janë
rregullat 4a, 4b, të cilat lejojnë që detyra të ruajë prioritet, duke çliruar procesorin
deri në skadimin e kohës së ndarë. Si të përballojmë me këtë?
Zgjidhja në këtë rast mund të konsiderohet si regjistrimi më i mirë i kohës CPU në çdo
niveli MLFQ. Në vend që të harrohet koha e përdorur nga programa
për procesorin gjatë intervalit të caktuar, duhet të merret parasysh dhe të ruhet. Pasi që
procesi të ketë shpenzuar kohën e tij të ndarë, duhet të ulet në nivelin e ardhshëm
të prioritetit. Tani nuk ka rëndësi si do ta përdorë procesi kohën e tij — si
duke llogaritur vazhdimisht në procesor ose si një shumë thirrjesh. Kështu,
rregulli 4 duhet të riformulohet në formën e mëposhtme:

Rregulli 4: Pas shpenzimit të kohës së ndarë në radhën aktuale (pavarësisht nga numri i herëve që ka çliruar CPU) prioriteti i atij procesi ulet (ai lëviz poshtë në radhë).

Le të shohim një shembuj:
»

Në figurë është treguar se çfarë ndodh nëse përpiqet të mashtrohet planifikuesi, si
nëse do të ishim me rregullat e mëparshme 4a, 4b do të rezultonte rezultati në të majtë. Me rregullin e ri — rezultati në të djathtë. Deri në mbrojtje, çdo proces mund të shkaktojë I/O deri në përfundim dhe
në këtë mënyrë të dominojë mbi CPU, pas aktivizimit të mbrojtjes, pavarësisht nga sjellja e I/O, ai do të zbresë gjithsesi në radhë poshtë dhe kështu nuk do të mund të kapë padrejtësisht
burimet e CPU-së.
Përmirësimi i MLFQ dhe probleme të tjera
Me përmirësimet e mësipërme kanë lindur probleme të reja: një nga pyetjet kryesore është si të parametrizohet një planifikues i tillë? Pra, sa duhen

ranga? Cili duhet të jetë përmasat e dritares së punës së programit brenda rangut? Sa

shpesh duhet të rritet prioriteti i programit për të shmangur urinë dhe
të marrë parasysh ndryshimin e sjelljes së programit? Për këto pyetje, nuk ka një përgjigje të thjeshtë dhe vetëm eksperimentet me ngarkesa dhe konfigurimi i mëpasshëm
i planifikuesit mund të çojë në një balancim të kënaqshëm.
Për shembull, shumica e realizimeve të MLFQ lejojnë caktimin e intervaleve të ndryshme
të kohës për rangje të ndryshme. Rangjeve me prioritet të lartë zakonisht
u caktuan intervale të shkurtra. Këto rangje përbëhen nga detyra interaktive,
ndërkëmbimi i të cilave është mjaft i ndjeshëm dhe duhet të zgjasë 10 ose më pak

ms. Ndërsa rangjet me prioritet të ulët përbëhen nga detyra të gjata që përdorin
CPU. Dhe në këtë rast, intervalet e gjata të kohës janë shumë të përshtatshme (100ms).
Në këtë shembull ka 2 detyra, të cilat punuan në rangun me prioritet të lartë për 20
ms, të ndara në dritare prej 10ms. 40ms në rangun e mesëm (dritare në 20ms) dhe në rangun me prioritet të ulët
intervali u bë 40ms, ku detyrat e përfunduan punën e tyre.
Realizimi i MLFQ në OS Solaris — një klasë planifikuesish që ndajnë me kohë.

Planifikuesi ofron një set tabelash, të cilat përcaktojnë saktësisht se si duhet
të përputhen prioritetet e procesit gjatë gjithë jetës së tij, cili duhet të jetë përmasat
e dritares ndarëse dhe sa shpesh duhet të rriten prioritetet e detyrës. Administrator

i sistemit mund të ndërveprojë me këtë tabelë dhe ta bëjë planifikuesin të sillet
ndryshe. Në mënyrë të parazgjedhur në këtë tabelë ka 60 rangje me rritje graduale
të përmasave të dritares nga 20ms (prioritet i lartë) deri në disa qindra ms (prioritet i ulët), dhe
të dritares së alokimit dhe sa shpesh duhet të rriten prioritetet e detyrave. Administratori
i sistemit mund të ndërveprojë me këtë tabelë dhe të bëjë që planifikuesi të sillet
ndryshe. Për default, në këtë tabelë ka 60 radhë me rritje të gradualshme
të madhësisë së dritares nga 20ms (prioritet i lartë) deri në disa qindra ms (prioritet i ulët), dhe
po gjithashtu me një përmirësim të gjitha detyrave çdo sekondë.

Planifikuesit e tjerë MLFQ nuk përdorin tabela ose ndonjë rregull të veçantë
të cilat janë përshkruar në këtë leksion, përkundrazi ata llogarisin prioritetet duke përdorur
formula matematike. Për shembull, planifikuesi në FreeBSD përdor një formulë për
të llogaritur prioritetin aktual të detyrës, duke u bazuar në sa CPU
ka përdorur procesi. Në përfundim, përdorimi i CPU me kalimin e kohës fillon të bjerë, dhe kështu
rritja e prioritetit ndodh disi ndryshe nga sa është përshkruar më sipër. Këto janë
të ashtuquajturat algoritme të zvetënimit. Që nga versioni 7.1, në FreeBSD përdoret planifikuesi ULE.

Së fundmi, shumë planifikues kanë karakteristika të tjera. Për shembull, disa
planifikues rezervojnë nivelet më të larta për funksionimin e sistemit operativ dhe kështu,
asnjë proces i përdoruesit nuk do të jetë në gjendje të marrë prioritetin më të lartë në
sistem. Disa sisteme lejojnë që të jepen këshilla për të ndihmuar
planifikuesin të vendosë prioritetet siç duhet. Kështu, për shembull, me ndihmën e komandës nice
mund të rritet ose ulet prioriteti i detyrës dhe kështu të rriten ose
ulet shanset e programit për kohë procesori.

MLFQ: Përfundimet

Ne përshkruam qasjen e planifikimit, e cila quhet MLFQ. Emri i tij
rrjedh nga parimi i funksionimit — ai ka disa radhë dhe përdor feedback
për të përcaktuar prioritetin e detyrës.
Forma përfundimtare e rregullave do të jetë si më poshtë:

Rregulli1: Nëse prioriteti(A) > Prioriteti(B), do të startohet detyra A (B nuk do të)
Rregulli2: Nëse prioriteti(A) = Prioriteti(B), A dhe B startohen duke përdorur RR
Rregulli3: Kur një detyrë vjen në sistem, ajo vendoset në radhën me prioritetin më të lartë.
Rregulli 4: Pas shpenzimit të kohës së ndarë në radhën aktuale (pavarësisht nga numri i herëve që ka çliruar CPU) prioriteti i atij procesi ulet (ai lëviz poshtë në radhë).
Rregulli 5: Pas kalimit të një periudhe S, të gjithë detyrat në sistem të kalojnë në radhën më të lartë.

MLFQ është interesante për arsye të mëposhtme — në vend që të kërkojë njohuri për
natyrën e detyrës përpara, algoritmi studion sjelljen e kaluar të detyrës dhe cakton
prioritetet në përputhje. Kështu ai përpiqet të arrijë një balancë midis dy anëve — për të arritur performancë për detyra të vogla (SJF, STCF) dhe për të startuar në mënyrë të ndershme detyrat e gjata,
të ngarkuara me CPU. Prandaj shumë sisteme, duke përfshirë BSD dhe derivatet e saj,
Solaris, Windows, Mac përdorin si planifikues një formë të algoritmit
MLFQ si një bazë themelore.