Hyrje në sistemet operative

Përshëndetje, Habr! Dëshiroj t'ju prezantoj një seri artikujsh-përkthime mbi një literaturë që e konsideroj interesante — OSTEP. Ky material shqyrton në mënyrë të thellë funksionimin e sistemeve operative të ngjashme me Unix, sidomos — menaxhimin e proceseve, planifikuesit e ndryshëm, memorjen dhe komponentë të tjerë të tillë që përbëjnë një sistem operativ modern. Origjinali i të gjitha materialeve mund ta shihni këtu këtu. Ju lutem, mbani në mend se përkthimi është bërë në mënyrë jo profesionale (mjaft e lirë), por shpresoj se e kam ruajtur kuptimin e përgjithshëm.

Laboratorët për këtë lëndë mund t'i gjeni këtu:

Pjesë të tjera:

Po ashtu mund të dëshironi të vizitoni kanalin tim në telegram =)

Planifikimi: Radhë Feedback me Shkallë të Shumfishtë

Në këtë ligjëratë do të flasim për problemet e zhvillimit të një prej qasjeve më të njohura për
planifikim, e cila quhet Radhë Feedback me Shkallë të Shumfishtë (MLFQ). Për herë të parë, planifikuesi MLFQ u përshkrua në vitin 1962 nga Fernando J. Corbató në sistemin, i quajtur
Sistemi i Pjesëve të Kohës të Pajtueshëm (CTSS). Këto punime (përfshirë punimet e mëvonshme mbi
Multics) më vonë u paraqitën për çmimin Turing. Planifikuesi u
përmirësua dhe mori formën që mund të gjejmë tashmë në
disa sisteme moderne.

Algoritmi MLFQ përpiqet të zgjidhë 2 probleme themelore të mbivendosura.
Së pari, ai përpiqet të optimizojë kohën e kthimit, e cila, siç e kemi shqyrtuar në ligjëratën e mëparshme, optimizohet përmes metodës së fillimit në radhë të detyrave më
të shkurtra. Megjithatë, OS nuk di sa gjatë do të punojë një proces i caktuar, dhe kjo
është njohuri e nevojshme për funksionimin e algoritmeve SJF, STCF. Në radhë të dytë, MLFQ përpiqet
të bëjë sistemin reagues për përdoruesit (për shembull, për ata që qëndrojnë dhe
shikojnë ekranin në pritje të përfundimit të detyrës) dhe kështu të minimizojë kohën
e reagimit. Fatkeqësisht, algoritmet si RR zvogëlojnë kohën e reagimit, por janë jashtëzakonisht
të dëmshme për metriken e kohës së kthimit. Prandaj, problemi ynë është: Si të projektosh
një planifikues që do t'i përmbushë kërkesat tona dhe në të njëjtën kohë të mos dijë asgjë për
natyrën e procesit, në përgjithësi? Si mund të mësojë planifikuesi për karakteristikat e detyrave,
të cilat ai aktivizon dhe kështu të marrë vendime më të mira për planifikimin?

Thelbi i problemit: Si të planifikosh caktimin e detyrave pa njohuri të përsosura?
Si të zhvillosh një planifikues që minimizon kohën e reagimit
për detyrat interaktive dhe për më tepër minimizon kohën e kthimit pa njohuri të qarta
për kohën e ekzekutimit të detyrës?

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

Radhë 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
gjen në OS (dhe shumë industri të tjera në informatikë, duke përfshirë degët
e parashikimeve në harduer dhe algoritmet e caching). Qasje të tilla
janë efektive kur detyrat kanë faza sjelljeje dhe kështu janë të parashikueshme.
Megjithatë, me këtë teknikë duhet të jemi të kujdesshëm, sepse parashikimet shumë lehtë
mund të dështojnë dhe të çojnë sistemin në marrjen e vendimeve më të dobëta se sa
do ishin pa njohuri fare.

MLFQ: Rregullat Bazike

Le të shqyrtojmë rregullat bazike të algoritmit MLFQ. Dhe megjithëse ekzistojnë disa realizime të këtij algoritmi, qasjet bazike janë të ngjashme.
Në atë realizim që do të shqyrtojmë, në MLFQ do të ketë disa
radhë të veçanta, secila prej të cilave do të ketë prioritet të ndryshëm. Në çdo moment,
detyra që është gati për ekzekutim ndodhet në një radhë. MLFQ përdor prioritetet,
për të vendosur se cila detyrë do të aktivizohet për ekzekutim, pra detyra me prioritet më të lartë
(detyra nga radhë me prioritet më të lartë) do të aktivizohet e para.
Pa dyshim, në një radhë 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 ekzekutimeve midis këtyre detyrave.
Kështu arrijmë në dy rregulla bazike për MLFQ:

Rregulli 1: Nëse prioriteti(A) > Prioriteti(B), do të aktivizohet detyra A (B nuk do të aktivizohet)
Rregulli 2: Nëse prioriteti(A) = Prioriteti(B), A dhe B do të aktivizohen duke përdorur RR

Duke marrë parasysh të mësipërmet, elementët kyç 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ë sjelljeve të vëzhguara.
Për shembull, nëse një detyrë vazhdimisht hedh punë në CPU në pritje të inputit nga tastiera,
MLFQ do të ruajë prioritetin e procesit në një nivel të lartë, sepse kështu
duhet të punojë një proces interaktiv. Nëse ndodhin përkundrazi, një detyrë vazhdimisht dhe
intensivisht përdor CPU për një periudhë të gjatë, MLFQ do të ulë prioritetin e saj.
Kështu, MLFQ do të mësojë sjelljen e proceseve gjatë punës së tyre
dhe do të përdorë sjelljet.
Le të ilustrojmë një shembull se si mund të duken radhët në një moment të caktuar
kohe, dhe kështu do të kemi diçka të tillë:

Në këtë skemë, 2 procese A dhe B ndodhen në radhën me prioritetin më të lartë. Procesi
C është diku në mes, ndërsa procesi D është në fund të radhës. Sipas përshkrimeve të lartë
të algoritmit MLFQ, planifikuesi do të ekzekutojë detyrat vetëm me prioritetin më të lartë sipas RR, ndërsa detyrat C, D do të jenë të papunë.
приоритетом согласно RR, а задачи C,D будут не у дел.
Sigurisht, një snapshot statik nuk do të ofrojë një panoramë të plotë mbi mënyrën si funksionon MLFQ.
Është e rëndësishme të kuptohet se si ndryshon pamja në kalim të kohës.

Përpjekja 1: Si të ndryshojmë prioritetin

Në këtë moment, duhet të vendoset se si MLFQ do të ndryshojë nivelin e prioritetit
të punës (dhe kështu pozita e punës në radhë) gjatë gjithë ciklit të saj të jetës. Për
këtë është e nevojshme të mbahen mend proceset: një numër i caktuar
i detyrave interaktive me kohë të shkurtër të punës (dhe kështu çlirimi i shpeshtë i
CPU) dhe disa detyra të gjata që e shfrytëzojnë CPU-në gjatë gjithë kohës së tyre të punës, ndërkohë
koha e përgjigjes për këto detyra nuk është e rëndësishme. Dhe kështu mund të bëhet përpjekja e parë
për të realizuar algoritmin MLFQ me rregullat e mëposhtme:

Rregulli 3: Kur një detyrë hyn në sistem, ajo vendoset në radhën me prioritetin më të lartë.
prioritet.
Rregulli 4a: Nëse detyra përdor plotësisht dritaren e saj të caktuar të kohës, atëherë prioriteti i saj
ulet.
Rregulli 4b: Nëse detyra çliron CPU-në përpara skadimit të dritares së saj të kohës, atëherë ajo
mbetet me prioritetin e njëjtë.

Shembulli 1: Një detyrë e gjatë

Siç shihet në këtë shembull, detyra vendoset me prioritetin më të lartë kur hyn.
Pas dritares së temporare prej 10ms, procesi ulet në prioritet nga
planifikuesi. Pas dritares tjetër të kohës, detyra përfundimisht bie në
prioritetin më të ulët në sistem, ku mbetet.

Shembulli 2: Një detyrë e shkurtër

Tani le të shqyrtojmë një shembull se si MLFQ do të mundohet të afrohet me SJF. Në këtë
shembull ka dy detyra: A, e cila është një detyrë e gjatë e cila 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 kur ka hyrë detyra B.

Në këtë grafik, rezultatet e skenarit janë evidente. Detyra A, ashtu si çdo detyrë,
që përdor CPU përfundon në fund të sistemit. Detyra B do të arrijë në T=100 dhe do të
vendoset në radhën me prioritetin më të lartë. Duke qenë se koha e punës së saj është e vogël, ajo
do të përfundojë para se të arrijë radhën e fundit.

Nga ky shembull mund të kuptohet qëllimi kryesor i algoritmit: pasi algoritmi nuk
di nëse është një detyrë e gjatë apo e shkurtër, ai fillimisht supozon se detyra
është e shkurtër dhe i jep asaj prioritetin më të lartë. Nëse kjo është në të vërtetë një detyrë e shkurtër, ajo
do të përfundojë shpejt; ndryshe, nëse është një detyrë e gjatë, ajo do të lëvizë ngadalë
në prioritetin më të ulët dhe së shpejti do të provohet se është një detyrë të vërtetë e gjatë që nuk
ka nevojë për përgjigje.

Shembulli 3: Si qëndron puna me input-output?

Tani le të shohim një shembull me input-output. Siç është thënë në rregullin 4b,
nëse procesi çliron procesorin pa e përdorur plotësisht kohën e tij të procesorit,
atëherë ai mbetet në nivelin e tij të mëparshëm të prioritetit. Qëllimi i këtij rregulli është mjaft i thjeshtë
- nëse një detyrë interaktive kryen shumë operacione input-output, për shembull, duke pritur
për klikimet e tastierës ose miut nga përdoruesi, një detyrë e tillë do të çlirojë procesorin
më herët se sa dritarja e caktuar. Ne nuk do të donim ta ulnim prioritetin e një detyre të tillë,
dhe kështu ajo do të mbetet në nivelin e saj të mëparshëm.

Ky shembull tregon se si do të punojë algoritmi me këto procese - detyra interaktive B, e cila ka nevojë për CPU vetëm për 1ms para se të kryejë
procesin input-output dhe detyra e gjatë A, e cila e përdor gjithmonë CPU-në.
MLFQ e 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 arrin
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ë variant themelor të MLFQ. Dhe duket se ai
po e bën punën e tij mirë dhe drejt, duke ndarë kohën e procesorit në mënyrë të ndershme mes
detyrave të gjata dhe duke lejuar detyrat e shkurtra ose detyrat që kërkojnë shumë input-output të punojnë shpejt. Fatkeqësisht, ky qasje përmban disa
probleme serioze.
серьезных проблем.
Së pari, problemi i urisë: nëse në sistem ka shumë detyra interaktive, ato do të konsumojnë të gjitha kohën e procesorit dhe kështu asnjë detyrë e gjatë
nuk do të ketë mundësinë të ekzekutohet (ato do të kenë uri).
задание не получит возможности исполняться (они голодают).

Në radhë të dytë, përdoruesit e zgjuar mund të shkruajnë programet e tyre në mënyrë që
të tradhtojnë planifikuesin. Tradhtia qëndron në të bërit diçka që i detyron
planifikuesin të japë procesit më shumë kohë procesori. Algoritmi që
është përshkruar më sipër është mjaft i ndjeshëm ndaj sulmeve të tilla: përpara se dritarja e kohës të përfundojë, është e nevojshme të kryhet një operacion input-output (përndryshe, për çdo skedar pa rëndësi).
кончилось нужно выполнить операцию ввода-вывода (к какому-то, неважно какому файлу)
dhe kështu të lirojmë CPU. Një sjellje e tillë do të lejojë të mbetemi në të njëjtën
rresht dhe sërish të marrim një përqindje më të madhe të kohës së procesorit. Nëse e bëjmë
këtë siç duhet (për shembull, të ekzekutojmë 99% të kohës deri para lirimit të CPU),
një detyrë e tillë thjesht mund të monopolizojë procesorin.

Për më tepër, programi mund të ndryshojë sjelljen e tij me kalimin e kohës. Ato detyra,
të cilat përdornin CPU, mund të bëhen interaktive. Në shembullin tonë, këto
detyra nuk do të marrin trajtimin e duhur nga planifikuesi, ashtu si do të merrnin detyra të tjera
(fillestare) interaktive.

Pyetje për audiencën: cilat sulme 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
uriturjen. Çfarë mund të bëjmë për të siguruar që detyrat e lidhura me
CPU të marrin kohën e tyre (edhe nëse jo për një periudhë të gjatë).
Si një zgjidhje të thjeshtë për problemin, mund të propozojmë që periodikisht
të rrisim prioritetin e të gjitha këtyre detyrave në sistem. Ekzistojnë shumë mënyra
për ta arritur këtë, le të japim si shembull diçka të thjeshtë: të transferojmë
menjëherë të gjitha detyrat në prioritetin më të lartë, dhe kështu rregulli i ri:

Rule5: Pas një periudhe të caktuar S, të transferojmë të gjitha detyrat në sistem në rreshtin më të lartë.

Rregulli ynë i ri zgjidh dy probleme në të njëjtën kohë. Së pari, proceset
garantuar nuk uriten: detyrat në rreshtin më të lartë do të ndajnë
kohën e procesorit sipas algoritmit RR dhe kështu të gjitha proceset do të marrin
kohë procesori. Së dyti, nëse ndonjë proces, i cili më parë përdorte
vetëm procesorin, bëhet interaktiv, ai do të mbetet në rreshtin me prioritet më të lartë pasi të marrë një rritje prioriteti deri në maksimum.
Le të shqyrtojmë një shembull. Në këtë skenar, le të konsiderojmë një proces që përdor
CPU dhe dy procese interaktive të shkurtra. Në anën e majtë të figurës tregohet sjellja pa rritjen e prioritetit, duke treguar se detyra e gjatë fillon të uritet pas mbërritjes së dy detyrave interaktive në sistem. Në figurën e djathtë, çdo 50ms bëhet rritje prioriteti, dhe kështu të gjitha proceset garantohet që të marrin kohë procesori dhe do të ekzekutohen me rregull. 50ms në këtë rast është marrë si shembull, realisht ky numër është pak më i madh.

Është e qartë se shtimi i kohës periodike të rritjes S ngre një
pyetje të natyrshme: çfarë vlere duhet të caktohet? Një nga inxhinierët sistemorë të njohur John Ousterhout e ka quajtur një vlerë të tillë në sistemet si një konstante voo-doo, sepse ata kërkonin një lloj magjie të zezë për t'u caktuar saktësisht.
Dhe, fatkeqësisht, S ka një aromë të tillë. Nëse caktohet një vlerë shumë
të madhe - detyrat e gjata do të fillojnë të uriten. Kurse nëse caktohet një vlerë shumë të vogël,
константа, поскольку они в некотором роде требовали черной магии для корректного
выставления. И, к сожалению S имеет такой аромат. Если выставить значение слишком
большим — долгие задачи начнут голодать. А если выставить слишком низкое значение,
detyrat interaktive nuk do të marrin kohë procesori të mjaftueshme.

Përpjekja 3: Llogaritja më e mirë

Tani kemi një problem tjetër që duhet zgjidhur: si të mos
lejojmë që planifikuesi ynë të mashtrohet? Fajtorët për këtë mundësi rezultojnë
të jenë rregullat 4a, 4b, të cilat lejojnë një detyre të mbajë prioritetin, duke liruar procesorin
para se të përfundojë koha e caktuar. Si mund ta zgjidhim këtë?
Një zgjidhje në këtë rast mund të konsiderohet si llogaritja më e mirë e kohës së CPU në çdo
nivel MLFQ. Në vend që të harrojmë kohën e përdorur nga programi
për ta kaluar procesorin brenda një periudhe të caktuar, duhet ta kemi parasysh dhe ta ruajmë atë. Pasi
procesi të ketë shpenzuar kohën e caktuar, duhet të ulet në nivelin e ardhshëm të prioritetit. Tani është e parëndësishme se si process do të shpenzojë kohën e tij - si
me përllogaritje të vazhdueshme në procesor ose me shumë thirrje. Njësoj,
rruga për të ri-shkruar rregullin 4 është si vijon:
Rule4

: Pasi një detyrë të ketë shpenzuar kohën e caktuar në rreshtin aktual (pavarësisht se sa herë ajo ka liruar CPU) prioriteti i një detyre të tillë ulet (ajo lëviz poshtë në rresht).Le të shohim një shembull:

Në figurë tregohet se çfarë ndodh nëse përpiqemi të mashtrojmë planifikuesin, sikur të ishim me rregullat e mëparshme 4a, 4b, rezultati do të jetë në anën e majtë. Me rregullin e ri - rezultati është në anën e djathtë. Para mbrojtjes, çdo proces mund të thërrasë I/O deri në përfundim dhe
»

На рисунке показано что случается, если попробовать обмануть планировщик, как
если бы было с предыдущими правилами 4a, 4b получится результат слева. С новым
правилом — результат справа. До защиты любой процесс мог вызвать I/O до завершения и
në këtë mënyrë të dominojë mbi CPU, pas aktivizimit të mbrojtjes, pavarësisht nga sjellja e
I/O, ai do të rritet akoma poshtë në rresht, dhe kështu nuk do të mund të bëjë padrejtësi
me burimet e CPU.

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

Me përmirësimet e përmendura më sipër, lindin probleme të reja: një nga pyetjet kryesore
është se si të parametrizohet një planifikues i tillë? P.sh. Sa duhen
rreshta? Cili duhet të jetë madhësia e dritares së punës brenda rreshtit? Si
shpesh duhet të rritet prioriteti i programit për të shmangur urinë dhe
për të marrë parasysh ndryshimin e sjelljes së programit? Për këto pyetje, nuk ka përgjigje të thjeshtë
dhe vetëm eksperimenti me ngarkesat dhe konfigurove pasuese
të planifikuesit mund të sjellë një balancim të kënaqshëm.

P.sh., shumica e implementimeve MLFQ lejojnë caktimin e intervaleve të ndryshme
të kohës për rreshta të ndryshëm. Rreshtat me prioritet të lartë zakonisht
kanë intervale të shkurtra. Këta rreshta përbëhen nga detyra interaktive,
ndërveprimi i të cilave është mjaft i ndjeshëm dhe duhet të zgjasë 10 ose më pak
ms. Në përballje, rreshtat me prioritet të ulët përbëhen nga detyra të gjata, që përdorin
CPU. Dhe në këtë rast, intervalet e gjata funksionojnë shumë mirë (100 ms).

Në këtë shembull ka 2 detyra, të cilat kanë punuar në një rresht me prioritet të lartë për 20
ms, të ndara në dritare prej 10 ms. 40 ms në një rresht të mesëm (dritare prej 20 ms) dhe në rreshtin me prioritet të ulët
dritarja përkohësore është bërë 40 ms, ku detyrat e përfunduan punën e tyre.

Implementimi MLFQ në OS Solaris është një klasë planifikuesish që ndan kohën.
Planifikuesi ofron një set tabelash, të cilat përcaktojnë saktësisht se si duhet
të ndryshojë prioriteti i procesit gjatë jetës së tij, cili duhet të jetë madhësia
e dritares së alokuar dhe sa shpesh duhet të rriten prioritetet e detyrave. Administratori
i sistemit mund të interagojë me këtë tabelë dhe të bëjë që planifikuesi të sillet
ndryshe. Si parazgjedhje, në këtë tabelë janë 60 rreshta me rritje të gradualshme
të madhësisë së dritares nga 20 ms (prioritet i lartë) deri në disa qindra ms (prioritet i ulët), si
edhe me një rritje të të gjitha detyrave çdo sekondë.

Planifikuesit e tjerë MLFQ nuk përdorin tabelën ose ndonjë rregull specifik
të përshkruar në këtë ligjëratë, përkundrazi ata llogarisin prioritetet duke përdorur
formula matematike. P.sh., planifikuesi në FreeBSD përdor një formulë për
llogaritjen e prioritetit aktual të detyrës, bazuar në sa proces
ka përdorur CPU-në. Për më tepër, përdorimi i CPU me kalimin e kohës përkeqësohet, dhe kështu
rritja e prioritetit ndodh disi ndryshe nga sa u përshkrua më parë. Këto janë
algoritmet e ashtuquajtur të decay. Që nga versioni 7.1, në FreeBSD përdoret planifikuesi ULE.

Së fundmi, shumë planifikues kanë veçori të tjera. P.sh., disa
planifikues rezervohen nivelet më të larta për punën e sistemit operativ, kështu
nuk ka ndonjë proces përdorues që mund të marrë prioritetin më të lartë në
sistem. Disa sisteme lejojnë dhënien e këshillave për të ndihmuar
planifikuesin të vendosë prioritetet në mënyrë të saktë. P.sh., 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ën e procesorit.

MLFQ: Përmbledhje

Ne përshkruam një qasje për planifikimin, e cila quhet MLFQ. Emri i tij
e ka rrënjën në parimin e funksionimit - ai ka disa rreshta dhe përdor feedbackun
për të përcaktuar prioritetin e detyrave.
Forma përfundimtare e rregullave do të jetë si më poshtë:

Rule1: Nëse prioriteti(A) > Prioriteti(B), do të aktivizohet detyra A (B nuk do të aktivizohet)
Rule2: Nëse prioriteti(A) = Prioriteti(B), A dhe B aktivizohen duke përdorur RR
Rule3: Kur një detyrë hyn në sistem, ajo vendoset në rreshtin me prioritetin më të lartë.
: Pasi një detyrë të ketë shpenzuar kohën e caktuar në rreshtin aktual (pavarësisht se sa herë ajo ka liruar CPU) prioriteti i një detyre të tillë ulet (ajo lëviz poshtë në rresht).Le të shohim një shembull:
Rule5: Pas një periudhe të caktuar S, të transferojmë të gjitha detyrat në sistem në rreshtin më të lartë.

MLFQ është interesant për arsye të ndryshme - në vend që të kërkonte njohuri rreth
natyrës së detyrës paraprakisht, algoritmi studion sjelljen e kaluar të detyrës dhe përcakton
prioritetet përkatësisht. Në këtë mënyrë përpiqet të arrijë të dyja përfitimet - të sigurojë performancë për detyrat e vogla (SJF, STCF) dhe të aktivizojë në mënyrë të përhershme detyrat e gjata,
të ngarkuara me CPU. Prandaj, shumë sisteme, përfshirë BSD dhe degët e tyre,
Solaris, Windows, Mac përdorin si planifikues një formë të algoritmit
MLFQ si bazë themelore.