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 . 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ë =)
Hyrje në Scheduler
Thelbi i problemit: Si të zhvillohet një politikë planifikuese
Si duhet të dizajnohen kornizat themelore të politikave të planifikuesit? Cilat duhet të jenë supozimet kryesore? Cilat metrika janë të rëndësishme? Cilat teknika bazë u përdorën në sistemet e hershme kompjuterike?
Supozimet e ngarkesës së punës
Përpara se të diskutojmë politikat e mundshme, le të bëjmë fillimisht disa digresione thjeshtuese rreth proceseve që zhvillohen në sistem, të cilat së bashku quhen ngarkesa e punës. Përcaktimi i ngarkesës së punës është një pjesë kritike e politikave të ndërtimit dhe sa më shumë të dini për ngarkesën e punës, aq më mirë politika që mund të shkruani.
Le të bëjmë supozimet e mëposhtme në lidhje me proceset që ekzekutohen në sistem, të quajtura ndonjëherë edhe Punë (detyrat). Pothuajse të gjitha këto supozime nuk janë realiste, por janë të nevojshme për zhvillimin e mendimit.
- Çdo detyrë funksionon për të njëjtën kohë,
- Të gjitha detyrat vendosen njëkohësisht,
- Detyra e caktuar funksionon deri në përfundimin e saj,
- Të gjitha detyrat përdorin vetëm CPU,
- Koha e ekzekutimit të secilës detyrë është e njohur.
Metrika e Scheduler
Përveç disa supozimeve për ngarkesën, nevojitet një mjet tjetër për krahasimin e politikave të ndryshme të planifikimit: metrikat e planifikuesit. Një metrikë është vetëm një masë e diçkaje. Ekzistojnë një numër metrikash që mund të përdoren për të krahasuar planifikuesit.
Për shembull, ne do të përdorim një metrikë të quajtur koha e kthimit (koha e rrotullimit). Koha e kthimit të detyrës përcaktohet si diferenca midis kohës së përfundimit të detyrës dhe kohës së mbërritjes së detyrës në sistem.
Tturnaround=Tcompletion−Tarrival
Meqenëse supozuam se të gjitha detyrat arritën në të njëjtën kohë, atëherë Ta=0 dhe kështu Tt=Tc. Kjo vlerë do të ndryshojë natyrshëm kur të ndryshojmë supozimet e mësipërme.
Një tjetër metrikë - drejtësi (drejtësia, ndershmëria). Produktiviteti dhe drejtësia janë shpesh karakteristika të kundërta në planifikim. Për shembull, planifikuesi mund të optimizojë performancën, por me koston e pritjes për ekzekutimin e detyrave të tjera, duke ulur kështu drejtësinë.
I PARË NË FIRST OUT (FIFO)
Algoritmi më themelor që mund të zbatojmë quhet FIFO ose i pari hyn (hyri), i pari shërbeu (jashtë). Ky algoritëm ka disa përparësi: është shumë i lehtë për t'u zbatuar dhe i përshtatet të gjitha supozimeve tona dhe e bën punën mjaft mirë.
Le të shohim një shembull të thjeshtë. Le të themi se 3 detyra u vendosën njëkohësisht. Por le të supozojmë se detyra A mbërriti pak më herët se të gjitha të tjerat, kështu që do të shfaqet në listën e ekzekutimit më herët se të tjerët, ashtu si B në krahasim me C. Le të supozojmë se secila prej tyre do të ekzekutohet për 10 sekonda. Sa do të jetë koha mesatare për të përfunduar këto detyra në këtë rast?
Duke numëruar vlerat - 10+20+30 dhe pjesëtuar me 3, marrim kohën mesatare të ekzekutimit të programit të barabartë me 20 sekonda.
Tani le të përpiqemi të ndryshojmë supozimet tona. Në veçanti, supozimi 1 dhe kështu ne nuk do të supozojmë më se çdo detyrë kërkon të njëjtën kohë për t'u ekzekutuar. Si do të jetë FIFO këtë herë?
Siç rezulton, kohë të ndryshme të ekzekutimit të detyrave kanë një ndikim jashtëzakonisht negativ në produktivitetin e algoritmit FIFO. Le të supozojmë se detyra A do të marrë 100 sekonda për t'u përfunduar, ndërsa B dhe C do të marrin akoma 10 sekonda secila.
Siç shihet nga figura, koha mesatare për sistemin do të jetë (100+110+120)/3=110. Ky efekt quhet efekti i kolonës, kur disa konsumatorë afatshkurtër të një burimi do të qëndrojnë në radhë pas një konsumatori të rëndë. Është si linja në dyqan ushqimor kur ka një klient para jush me një karrocë të plotë. Zgjidhja më e mirë e problemit është të përpiqeni të ndryshoni arkën ose të relaksoheni dhe të merrni frymë thellë.
Puna më e shkurtër e para
A është e mundur të zgjidhet disi një situatë e ngjashme me proceset me peshë të rëndë? Sigurisht. Një lloj tjetër planifikimi quhetPuna më e shkurtër e para (SJF). Algoritmi i tij është gjithashtu mjaft primitiv - siç nënkupton edhe emri, detyrat më të shkurtra do të lansohen së pari, njëra pas tjetrës.
Në këtë shembull, rezultati i ekzekutimit të të njëjtave procese do të jetë një përmirësim në kohën mesatare të kthimit të programit dhe do të jetë i barabartë me 50 në vend të 110, e cila është pothuajse 2 herë më e mirë.
Kështu, për supozimin e dhënë se të gjitha detyrat arrijnë në të njëjtën kohë, algoritmi SJF duket të jetë algoritmi më optimal. Megjithatë, supozimet tona ende nuk duken realiste. Këtë herë ne ndryshojmë supozimin 2 dhe këtë herë imagjinojmë që detyrat mund të jenë të pranishme në çdo kohë, dhe jo të gjitha në të njëjtën kohë. Në çfarë problemesh mund të çojë kjo?
Le të imagjinojmë se detyra A (100c) mbërrin së pari dhe fillon të ekzekutohet. Në t=10, mbërrijnë detyrat B dhe C, secila prej të cilave do të marrë 10 sekonda. Pra, koha mesatare e ekzekutimit është (100+(110-10)+(120-10))3 = 103. Çfarë mund të bëjë planifikuesi për ta përmirësuar këtë?
Koha më e shkurtër deri në përfundimin e parë (STCF)
Për të përmirësuar situatën, ne e lëmë jashtë supozimin 3 se programi është nisur dhe funksionon deri në përfundim. Përveç kësaj, ne do të kemi nevojë për mbështetje harduerike dhe, siç mund ta merrni me mend, ne do ta përdorim kohëmatës për të ndërprerë një detyrë në ekzekutim dhe ndërrimi i kontekstit. Kështu, planifikuesi mund të bëjë diçka në momentin që mbërrijnë detyrat B, C - të ndalojë ekzekutimin e detyrës A dhe t'i vendosë detyrat B dhe C në përpunim dhe, pas përfundimit të tyre, të vazhdojë ekzekutimin e procesit A. Një planifikues i tillë quhet STCFose Punë parandaluese së pari.
Rezultati i këtij planifikuesi do të jetë rezultati i mëposhtëm: ((120-0)+(20-10)+(30-10))/3=50. Kështu, një planifikues i tillë bëhet edhe më optimal për detyrat tona.
Koha e përgjigjes metrike
Kështu, nëse e dimë kohën e ekzekutimit të detyrave dhe se këto detyra përdorin vetëm CPU, STCF do të jetë zgjidhja më e mirë. Dhe një herë në kohët e hershme, këto algoritme funksiononin mjaft mirë. Megjithatë, përdoruesi tani kalon pjesën më të madhe të kohës në terminal dhe pret një përvojë interaktive produktive. Kështu lindi një metrikë e re - koha e pergjigjes (përgjigje).
Koha e përgjigjes llogaritet si më poshtë:
Tresponse=Tfirstrun−Tarrival
Kështu, për shembullin e mëparshëm, koha e përgjigjes do të jetë: A=0, B=0, C=10 (abg=3,33).
Dhe rezulton se algoritmi STCF nuk është aq i mirë në një situatë kur mbërrijnë 3 detyra në të njëjtën kohë - do të duhet të presë derisa detyrat e vogla të përfundojnë plotësisht. Pra, algoritmi është i mirë për metrikën e kohës së kthesës, por i keq për metrikën e interaktivitetit. Imagjinoni sikur të jeni ulur në një terminal duke u përpjekur të shkruani karaktere në një redaktues dhe duhet të prisni më shumë se 10 sekonda sepse ndonjë detyrë tjetër po merrte CPU-në. Nuk është shumë e këndshme.
Pra, ne përballemi me një problem tjetër - si mund të ndërtojmë një planifikues që është i ndjeshëm ndaj kohës së përgjigjes?
Garë me sistem qarku
Një algoritëm u zhvillua për të zgjidhur këtë problem Garë me sistem qarku (RR). Ideja bazë është mjaft e thjeshtë: në vend që të ekzekutojmë detyrat derisa ato të përfundojnë, ne do ta ekzekutojmë detyrën për një periudhë të caktuar kohore (e quajtur një pjesë kohore) dhe më pas do të kalojmë në një detyrë tjetër nga radha. Algoritmi përsërit punën e tij derisa të përfundojnë të gjitha detyrat. Në këtë rast, koha e ekzekutimit të programit duhet të jetë shumëfish i kohës pas së cilës kohëmatësi do të ndërpresë procesin. Për shembull, nëse një kohëmatës ndërpret një proces çdo x=10ms, atëherë madhësia e dritares së ekzekutimit të procesit duhet të jetë shumëfish i 10 dhe të jetë 10,20 ose x*10.
Le të shohim një shembull: detyrat ABC mbërrijnë njëkohësisht në sistem dhe secila prej tyre dëshiron të ekzekutojë për 5 sekonda. Algoritmi SJF do të përfundojë çdo detyrë përpara se të fillojë një tjetër. Në të kundërt, algoritmi RR me një dritare lëshimi = 1s do të kalojë nëpër detyrat si më poshtë (Fig. 4.3):
(SJF Përsëri (i keq për kohën e përgjigjes)
(Round Robin (i mirë për kohën e përgjigjes)
Koha mesatare e përgjigjes për algoritmin RR është (0+1+2)/3=1, ndërsa për SJF (0+5+10)/3=5.
Është logjike të supozohet se dritarja kohore është një parametër shumë i rëndësishëm për RR; sa më i vogël të jetë, aq më e lartë është koha e përgjigjes. Megjithatë, nuk duhet ta bëni shumë të vogël, pasi koha e ndërrimit të kontekstit do të luajë gjithashtu një rol në performancën e përgjithshme. Kështu, zgjedhja e kohës së dritares së ekzekutimit vendoset nga arkitekti i OS dhe varet nga detyrat që planifikohen të ekzekutohen në të. Ndërrimi i kontekstit nuk është i vetmi operacion shërbimi që humbet kohë - programi i ekzekutimit funksionon në shumë gjëra të tjera, për shembull, cache të ndryshme, dhe me çdo ndërprerës është e nevojshme të ruhet dhe të rivendoset ky mjedis, i cili gjithashtu mund të marrë shumë koha.
RR është një programues i shkëlqyeshëm nëse do të flisnim vetëm për metrikën e kohës së përgjigjes. Por si do të sillet metrika e kohës së kthimit të detyrës me këtë algoritëm? Konsideroni shembullin e mësipërm, kur koha e funksionimit të A, B, C = 5s dhe arrin në të njëjtën kohë. Detyra A do të përfundojë në 13, B në 14, C në 15 sekonda dhe koha mesatare e kthimit do të jetë 14 sekonda. Kështu, RR është algoritmi më i keq për metrikën e qarkullimit.
Në terma më të përgjithshëm, çdo algoritëm i tipit RR është i drejtë; ai e ndan kohën e CPU-së në mënyrë të barabartë midis të gjitha proceseve. Dhe kështu, këto metrika vazhdimisht bien ndesh me njëra-tjetrën.
Kështu, ne kemi disa algoritme të kundërta dhe në të njëjtën kohë kanë mbetur ende disa supozime - se koha e detyrës është e njohur dhe se detyra përdor vetëm CPU.
Përzierja me I/O
Para së gjithash, le të heqim supozimin 4 se procesi përdor vetëm CPU; natyrisht, nuk është kështu dhe proceset mund të kenë akses në pajisje të tjera.
Në momentin që çdo proces kërkon një operacion I/O, procesi hyn në gjendjen e bllokuar, duke pritur që I/O të përfundojë. Nëse I/O dërgohet në hard disk, atëherë një operacion i tillë mund të zgjasë deri në disa ms ose më shumë, dhe procesori do të jetë i papunë në këtë moment. Gjatë kësaj kohe, planifikuesi mund të pushtojë procesorin me çdo proces tjetër. Vendimi tjetër që planifikuesi do të duhet të marrë është se kur procesi do të përfundojë I/O e tij. Kur kjo të ndodhë, do të ndodhë një ndërprerje dhe OS do të vendosë procesin që thirri I/O në gjendje gatishmërie.
Le të shohim një shembull të disa detyrave. Secila prej tyre kërkon 50 ms kohë CPU. Megjithatë, i pari do të hyjë në hyrje/dalje çdo 10 ms (i cili gjithashtu do të ekzekutohet çdo 10 ms). Dhe procesi B thjesht përdor një procesor 50ms pa I/O.
Në këtë shembull ne do të përdorim planifikuesin STCF. Si do të sillet planifikuesi nëse në të niset një proces si A? Ai do të bëjë sa më poshtë: së pari ai do të përpunojë plotësisht procesin A, dhe më pas do të përpunojë B.
Qasja tradicionale për të zgjidhur këtë problem është trajtimi i çdo nëndetyre 10 ms të procesit A si një detyrë më vete. Kështu, kur filloni me algoritmin STJF, zgjedhja midis një detyre 50 ms dhe një detyre 10 ms është e qartë. Më pas, kur nëndetyra A të përfundojë, procesi B dhe I/O do të nisen. Pasi të përfundojë I/O, do të jetë e zakonshme që procesi A 10ms të fillojë përsëri në vend të procesit B. Në këtë mënyrë, është e mundur të zbatohet mbivendosja, ku CPU përdoret nga një proces tjetër ndërsa i pari pret I/O. Dhe si rezultat, sistemi përdoret më mirë - në momentin kur proceset interaktive janë duke pritur për I/O, proceset e tjera mund të ekzekutohen në procesor.
Orakulli nuk është më
Tani le të përpiqemi të heqim qafe supozimin se koha e ekzekutimit të detyrës është e njohur. Ky është përgjithësisht supozimi më i keq dhe më jorealist në të gjithë listën. Në fakt, në sistemin operativ mesatar të zakonshëm, vetë OS zakonisht di shumë pak për kohën e ekzekutimit të detyrave, kështu që atëherë si mund të ndërtoni një planifikues pa e ditur se sa kohë do të duhet për të ekzekutuar detyrën? Ndoshta ne mund të përdorim disa parime RR për të zgjidhur këtë problem?
Total
Ne shikuam idetë bazë të planifikimit të detyrave dhe shikuam 2 familje të planifikuesve. E para fillon fillimisht detyrën më të shkurtër dhe kështu rrit kohën e kthimit, ndërsa e dyta ndahet midis të gjitha detyrave në mënyrë të barabartë, duke rritur kohën e përgjigjes. Të dy algoritmet janë të këqija ku algoritmet e familjes tjetër janë të mira. Ne shikuam gjithashtu se si përdorimi paralel i CPU dhe I/O mund të përmirësojë performancën, por nuk e zgjidhëm problemin me mprehtësinë e OS. Dhe në mësimin tjetër do të shikojmë një planifikues që shikon në të kaluarën e afërt dhe përpiqet të parashikojë të ardhmen. Dhe quhet radhë reagimesh me shumë nivele.
Burimi: www.habr.com