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 . 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ë =)
Hyrja në planifikuesin
Esenca e problemit: Si të zhvillohet politika e planifikuesit
Si duhet të zhvillohen kornizat themelore të politikave të planifikuesit? Cilat duhet të jenë supozimet kryesore? Cilat metrika janë të rëndësishme? Cilat teknika janë përdorur në sistemet llogaritëse të hershme?
Supozimet e ngarkesës pune
Para se të diskutojmë politikat e mundshme, në fillim do të bëjmë disa shpërngulje për të thjeshtuar proceset që janë aktivizuar në sistem, të cilat quhen së bashku ngarkesë pune. Duke përcaktuar ngarkesën si një pjesë kritike të ndërtimit të politikave dhe sa më shumë të dini për ngarkesën, aq më cilësore do të jetë politika që mund të shkruani.
Do të bëjmë supozimet e mëposhtme në lidhje me proceset e aktivizuara në sistem, ndonjëherë të quajtura jobs (detyra). Praktikisht të gjitha këto supozime janë jo realiste, por janë të nevojshme për zhvillimin e mendimit.
- Ădo detyrĂ« ekzekutohet pĂ«r tĂ« njĂ«jtĂ«n sasi kohe,
- Të gjitha detyrat vendosen njëkohësisht,
- Detyra e vendosur punon deri në përfundim të saj,
- Të gjitha detyrat përdorin vetëm CPU,
- Koha e ekzekutimit të çdo detyre është e njohur.
Metritë e Planifikuesit
Përveç disa supozimeve mbi ngarkesën, është e nevojshme gjithashtu një instrument për krahasimin e politikave të ndryshme të planifikimit: metritë e planifikuesit. Metrika është thjesht një masë e diçkaje. Ekziston një sasi metrikash që mund të përdoren për të krahasuar planifikuesit.
Si një shembull, do të përdorim metrikën e quajtur koha e kthimit (turnaround time). Koha e kthimit të detyrës përcaktohet si diferenca midis kohës së përfundimit të detyrës dhe kohës së arritjes së saj në sistem.
Tturnaround=TcompletionâTarrival
Duke supozuar se të gjitha detyrat kanë arritur njëkohësisht, atëherë Ta=0 dhe kështu Tt=Tc. Ky vlerë natyrshëm do të ndryshojë kur ne ndryshojmë supozimet e mësipërme.
Metri tjetër është fairness (drejtësi, ndershmëri). Performanca dhe drejtësia shpesh janë karakteristika që veprojnë në kundërshtim në planifikim. Për shembull, planifikuesi mund të optimizojë performancën, por me koston e pritjes në fillimin e detyrave të tjera, duke ulur kështu drejtësinë.
FIRST IN FIRST OUT (FIFO)
Algoritmi më bazik që mund të implementojmë quhet FIFO ose i pari më parë (në), i pari shërbehet (jashtë). Këtë algoritëm ka disa përparësi: është shumë i thjeshtë për tu implementuar dhe i përshtatet të gjitha supozimeve tona, duke e kryer punën mjaft mirë.
Le tĂ« konsiderojmĂ« njĂ« shembull tĂ« thjeshtĂ«. Supozoni se 3 detyra janĂ« vendosur njĂ«kohĂ«sisht. Por supozoni se detyra A ka ardhur pak mĂ« herĂ«t se tĂ« tjerat, kĂ«shtu qĂ« nĂ« listĂ«n e ekzekutimit do tĂ« qĂ«ndrojĂ« pĂ«rpara tĂ« tjerave, ashtu si dhe B nĂ« raport me V. Supozoni se secila prej tyre do tĂ« ekzekutohet pĂ«r 10 sekonda. ĂfarĂ« do tĂ« jetĂ« koha mesatare e ekzekutimit tĂ« kĂ«tyre detyrave nĂ« kĂ«tĂ« rast?
Duke llogaritur vlerat â 10+20+30 dhe duke i ndarĂ« me 3, marrim njĂ« kohĂ« mesatare ekzekutimi pĂ«r programin e barabartĂ« me 20 sekonda.
Tani le të përpiqemi të ndryshojmë supozimet tona. Në veçanti supozimi 1 dhe kështu të mos supozojmë më se çdo detyrë ekzekutohet për të njëjtën periudhë kohe. Si do të sillet FIFO këtë herë?
Siç duket, koha e ndryshme e ekzekutimit të detyrave ndikon në mënyrë të qenësishme në produktivitetin e algoritmit FIFO. Supozoni se detyra A do të ekzekutohet për 100 sekonda, ndërsa B dhe V vazhdojnë të kenë nga 10 secilën.
Siç shihet nga figura, koha mesatare për sistemin do të jetë (100+110+120)/3=110. Ky efekt quhet efekti i karvanit, kur disa konsumatorë afatshkurtër të një burimi do të qëndrojnë në radhë pas një konsumatori të rëndë. Kjo është si një radhë në një dyqan ushqimesh, kur përpara jush është një blerës me një karrocë të plotë. Zgjidhja më e mirë për problemin është të përpiqeni të ndryshoni arken ose thjesht të relaksoheni dhe të merrni frymë thellë.
Punët e Shkurtra më parë
A mund tĂ« zgjidhet ndonjĂ«herĂ« njĂ« situatĂ« e tillĂ« me proceset e rĂ«nda? Sigurisht. NjĂ« tip tjetĂ«r planifikimi quhetPunĂ«t e Shkurtra mĂ« parĂ« (SJF). Algoritmi i tij Ă«shtĂ« gjithashtu mjaft primitiv â siç duket nga emri, detyrat mĂ« tĂ« shkurtra do tĂ« ekzekutohen fillimisht njĂ« pas njĂ«.
Në këtë shembull, rezultati i ekzekutimit të të njëjtave procese do të jetë përmirësimi i kohës mesatare të qarkullimit të programeve dhe ajo do të jetë e barabartë me 50 në vend të 110, që është pothuajse 2 herë më mirë.
Pra ndaj, duke pasur parasysh supozimin qĂ« tĂ« gjitha detyrat arrijnĂ« nĂ« tĂ« njĂ«jtĂ«n kohĂ«, algoritmi SJF duket si algoritmi mĂ« optimal. MegjithatĂ«, supozimet tona ende nuk duken realiste. KĂ«tĂ« herĂ« do tĂ« ndryshojmĂ« supozimin 2 dhe do tĂ« paraqesim se detyrat mund tĂ« arrijnĂ« nĂ« çdo kohĂ«, jo tĂ« gjitha njĂ«herĂ«sh. ĂfarĂ« probleme mund tĂ« sjellĂ« kjo?
Imagjinoni qĂ« detyra A (100s) arrin e para dhe fillon tĂ« ekzekutohet. NĂ« momentin t=10 arrijnĂ« detyrat B dhe C, secila prej tĂ« cilave do tĂ« marrĂ« 10 sekonda. KĂ«shtu, koha mesatare e ekzekutimit Ă«shtĂ« (100+(110-10)+(120-10))/3 = 103. ĂfarĂ« mund tĂ« bĂ«nte planifikuesi pĂ«r tĂ« pĂ«rmirĂ«suar situatĂ«n?
Shortest Time-to-Completion First (STCF)
PĂ«r tĂ« pĂ«rmirĂ«suar situatĂ«n, do tĂ« hiqnim supozimin 3 se programi Ă«shtĂ« i aktivizuar dhe punon deri nĂ« pĂ«rfundim. PĂ«r mĂ« tepĂ«r, do tĂ« na duhet mbĂ«shtetje harduerike dhe siç mund ta keni menduar, do tĂ« pĂ«rdorim njĂ« timer pĂ«r tĂ« ndĂ«rprerĂ« detyrĂ«n nĂ« punĂ« dhe pĂ«r tĂ« ndĂ«rruar kontekstet. KĂ«shtu, planifikuesi mund tĂ« ndĂ«rmarrĂ« diçka nĂ« momentin e mbĂ«rritjes sĂ« detyrave B dhe C â tĂ« ndĂ«rpresĂ« ekzekutimin e detyrĂ«s A dhe tĂ« vendosĂ« pĂ«r t'u pĂ«rpunuar detyrat B dhe C, dhe pas pĂ«rfundimit tĂ« tyre, tĂ« vazhdojĂ« ekzekutimin e procesit A. NjĂ« planifikues i tillĂ« quhet STCFose Preemptive Job First.
Rezultati i këtij planifikuesi do të jetë si në vijim: ((120-0)+(20-10)+(30-10))/3=50. Kështu, ky planifikues bëhet akoma më optimal për detyrat tona.
Metrika Koha e përgjigjes (Response Time)
Pra ndaj, nĂ«se e dimĂ« kohĂ«n e punĂ«s sĂ« detyrave dhe qĂ« kĂ«to detyra pĂ«rdorin vetĂ«m CPU-nĂ«, STCF do tĂ« jetĂ« zgjidhja mĂ« e mirĂ«. Dikur nĂ« ditĂ«t e hershme, kĂ«ta algoritma funksiononin dhe mjaft mirĂ«. MegjithatĂ« tani, pĂ«rdoruesi kalon shumicĂ«n e kohĂ«s pĂ«rpara terminalit dhe pret njĂ« ndĂ«rveprim produktiv dhe interaktiv. KĂ«shtu lindi njĂ« metrikĂ« e re â koha e pĂ«rgjigjes (ndĂ«rgjegjĂ«simi).
Koha e përgjigjes llogaritet si në vijim:
Tresponse=TfirstrunâTarrival
Pra ndaj, për shembullin e mëparshëm, koha e përgjigjes do të jetë si në vijim: A=0, B=0, C=10 (abg=3,33).
Dhe duket se algoritmi STCF nuk Ă«shtĂ« aq i mirĂ« nĂ« situatĂ«n kur 3 detyra arrijnĂ« njĂ«kohĂ«sisht â ai do tĂ« duhet tĂ« presĂ« deri sa detyrat e vogla tĂ« pĂ«rfundojnĂ« plotĂ«sisht. Pra, algoritmi Ă«shtĂ« i mirĂ« pĂ«r metriken e kohĂ«s sĂ« pĂ«rfundimit, por i keq pĂ«r metriken e ndĂ«rveprueshmĂ«risĂ«. Imagjinoni, se ndĂ«rsa jeni ulur para terminalit duke pĂ«rpiqur tĂ« shkruani karaktere nĂ« redaktor, do tĂ« duhet tĂ« prisni mĂ« shumĂ« se 10 sekonda, sepse ndonjĂ« detyrĂ« tjetĂ«r po zĂ« procesorin. Kjo nuk Ă«shtĂ« aspak e kĂ«ndshme.
KĂ«shtu, ne ballafaqohemi me njĂ« problem tjetĂ«r â si mund tĂ« ndĂ«rtojmĂ« njĂ« planifikues qĂ« Ă«shtĂ« i ndjeshĂ«m ndaj kohĂ«s sĂ« pĂ«rgjigjes?
Round Robin
Për të zgjidhur këtë problem, u zhvillua algoritmi Round Robin (RR). Ideja kryesore është mjaft e thjeshtë: në vend që të ekzekutojmë detyrat deri në përfundimin e plotë, ne do ta ekzekutojmë një detyrë për një kohë të caktuar (e njohur si kvant kohe) dhe pastaj do të kalojmë te një detyrë tjetër nga radhët. Algoritmi përsërit këtë deri sa të gjitha detyrat të përfundojnë. Në të njëjtën kohë, koha e punës së programit duhet të jetë e barabartë me një shumës të kohës, gjatë së cilës timeri do ta ndërpresë procesin. Për shembull, nëse timeri ndalon procesin çdo x=10ms, atëherë madhësia e dritares së ekzekutimit të procesit duhet të jetë një shumës e 10 dhe të jetë 10, 20 ose x*10.
Le të marrim një shembull: detyrat A, B, C arrijnë njëkohësisht në sistem dhe secila prej tyre dëshiron të punojë për 5 sekonda. Algoritmi SJF do të ekzekutojë secilën detyrë deri në fund, para se të fillojë një tjetër. Në krahasim, algoritmi RR me madhësinë e dritares së ekzekutimit = 1s do të kalojë nëpër detyra si më poshtë (shih. 4.3):
(SJF Përsëri (Keq për Kohën e Përgjigjes)
(Round Robin (Mirë për Kohën e Përgjigjes)
Koha mesatare e përgjigjes për algoritmin RR (0+1+2) / 3 = 1, ndërsa për SJF (0+5+10) / 3 = 5.
ĂshtĂ« logjike tĂ« supozohet se dritarja e kohĂ«s Ă«shtĂ« njĂ« parameter shumĂ« i rĂ«ndĂ«sishĂ«m pĂ«r RR, sa mĂ« e vogĂ«l tĂ« jetĂ« ajo, aq mĂ« e lartĂ« Ă«shtĂ« koha e pĂ«rgjigjes. MegjithatĂ«, nuk mund ta bĂ«jmĂ« atĂ« shumĂ« tĂ« vogĂ«l, pasi koha pĂ«r tĂ« kaluar kontekstin gjithashtu do tĂ« luajĂ« rolin e saj nĂ« performancĂ«n e pĂ«rgjithshme. NĂ« kĂ«tĂ« mĂ«nyrĂ«, zgjedhja e kohĂ«s sĂ« dritares sĂ« ekzekutimit vendoset nga arkitekti i OS-sĂ« dhe varet nga detyrat qĂ« planifikohen tĂ« ekzekutohen atje. Kalimi i kontekstit nuk Ă«shtĂ« vetĂ«m operacioni shĂ«rbimor qĂ« merr kohĂ« - programi nĂ« ekzekutim operon me shumĂ« gjĂ«ra tĂ« tjera gjithashtu, pĂ«r shembull me keqet e ndryshme dhe nĂ« çdo kalim Ă«shtĂ« e nevojshme tĂ« ruhet dhe rikthehet kjo mjedis, qĂ« gjithashtu mund tĂ« kĂ«rkojĂ« shumĂ« kohĂ«.
RR është një planifikues i shkëlqyer, nëse do të flasim vetëm për matjen e kohës së përgjigjes. Por si do të sillet metrika e kohës së ciklit të detyrës gjatë këtij algoritmi? Të marrim një shembull më lart, kur koha e punës A, B, C = 5s dhe ato mbërrijnë në të njëjtën kohë. Detyra A do të përfundojë në 13, B në 14, C në 15s dhe koha mesatare e ciklit do të jetë 14s. Kështu, RR është algoritmi më i keq për matjen e ciklit.
Me fjalë më të përgjithshme, çdo algoritëm i tipit RR është i ndershëm, ai ndan kohën e punës në CPU në mënyrë të barabartë midis të gjitha proceseve. Dhe kështu, këto metrika konfliktualisht përplasen me njëra-tjetrën.
Kështu, kemi disa algoritma që kundërshtohen dhe megjithatë mbeten disa supozime - që koha e detyrës është e njohur dhe që detyra përdor vetëm CPU-në.
PĂ«rzierja me I/O
Së pari, do të heqim supozimin 4, se procesi përdor vetëm CPU, natyrisht që nuk është kështu dhe proceset mund të lidhen me pajisje të tjera.
Në momentin kur ndonjë proces kërkon një operacion hyrje-dalje (I/O), procesi kalon në gjendjen e bllokuar, duke pritur për përfundimin e I/O. Nëse I/O dërgohet në hard disk, një operacion i tillë mund të zgjasë deri në disa ms ose më shumë, dhe procesori në këtë moment do të jetë i papunë. Në këtë kohë, planifikuesi mund të marrë procesorin nga ndonjë proces tjetër. Zgjidhja tjetër që do të duhet të marrë planifikuesi është - kur procesi do të përfundojë I/O. Kur kjo ndodh, do të ndodhë një ndërprerje dhe OS do ta kthejë procesin që ka kërkuar I/O në gjendjen e gatshme.
Le të shqyrtojmë një shembull me disa detyra. Secila prej tyre ka nevojë për 50ms kohë procesori. Megjithatë, e para do të bëjë akses në I/O çdo 10ms (i cili gjithashtu do të ekzekutohet çdo 10ms). Ndërsa procesi B thjesht përdor 50ms procesor pa I/O.
NĂ« kĂ«tĂ« shembull, do tĂ« pĂ«rdorim planifikuesin STCF. Si do tĂ« sillet planifikuesi nĂ«se e lĂ«shojmĂ« procesin A? Ai do tĂ« veprojĂ« si mĂ« poshtĂ« â fillimisht do tĂ« pĂ«rfundojĂ« plotĂ«sisht procesin A, dhe mĂ« pas procesin B.
Qasja tradicionale pĂ«r zgjidhjen e kĂ«saj problemi Ă«shtĂ« tĂ« interpretojmĂ« çdo nĂ«n-detyrĂ« 10ms tĂ« procesit A si njĂ« detyrĂ« tĂ« veçantĂ«. KĂ«shtu, kur fillojmĂ« me algoritmin STJF, zgjedhja midis detyrĂ«s 50ms dhe detyrĂ«s 10ms Ă«shtĂ« e qartĂ«. MĂ« pas, kur nĂ«n-detyrĂ« A tĂ« pĂ«rfundojĂ«, do tĂ« fillojĂ« procesi B dhe I/O. Pas pĂ«rfundimit tĂ« I/O, do tĂ« merret pĂ«rsĂ«ri vendimi pĂ«r tĂ« nisur procesin 10ms A nĂ« vend tĂ« procesit B. KĂ«shtu qĂ« Ă«shtĂ« e mundur tĂ« realizohet mbivendosja, kur CPU pĂ«rdoret nga njĂ« proces tjetĂ«r, derisa i pari pret I/O. Dhe si rezultat, sistemi shfrytĂ«zohet mĂ« mirĂ« â nĂ« momentin kur proceset interaktive presin I/O, nĂ« procesor mund tĂ« ekzekutohen procese tĂ« tjera.
Orakulli nuk ekziston më
Tani do të përpiqemi të heqim supozimin se koha e ekzekutimit të detyrës është e njohur. Ky është përgjithësisht supozimi më i keq dhe më jokrealist nga e gjithë lista. Në fakt, në sistemet operative mesatare, vetë OS zakonisht di shumë pak për kohën e ekzekutimit të detyrave, si mund të ndërtojmë planifikues pa e ditur se sa kohë do të ekzekutohet detyra? Ndoshta mund të përdorim disa parime RR për të zgjidhur këtë problem?
PĂ«rfundimi
Ne shqyrtuam idetë bazë të planifikimit të detyrave dhe shqyrtuam dy familje planifikuesish. E para nis detyrën më të shkurtër në fillim dhe kështu rrit kohën e qarkullimit, ndërsa e dyta shpërndan ngarkesën në mënyrë të barabartë midis të gjitha detyrave, duke rritur kohën e përgjigjes. Të dy algoritmet janë të këqij atje ku algoritmet e tjera janë të mira. Po ashtu, shqyrtuam si përdorimi paralel i CPU dhe I/O mund të përmirësojë performancën, por nuk e zgjidhëm problemin me parashikimin e OS. Në mbledhjen e ardhshme, ne do të shqyrtojmë një planifikues që shikon në të kaluarën e afërt dhe përpiqet të parashikojë të ardhmen. Ai quhet multi-level feedback queue.
Burimi: habr.com
