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 =)

Hyrje në planifikuesin

Thelbi i problemit: Si të zhvillohet një politikë planifikuesi
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 themelore janë përdorur në sistemet kompjuterike të hershme?

Supozimet e ngarkesës së punës

Para se të diskutojmë politikat e mundshme, së pari le të bëjmë disa shkëputje thjeshtuese mbi proceset e ekzekutuara në sistem, të cilat së bashku quhen ngarkesa e punës. Duke përcaktuar ngarkesën e punës 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ë do të shkruani.

Le të bëjmë këto supozime mbi proceset që ekzekutohen në sistem, ndonjëherë të quajtura punë (detyra). Praktikisht të gjitha këto supozime janë jo realiste, por janë të nevojshme për zhvillimin e mendjes.

Çdo detyrë ekzekutohet për të njëjtën kohë,
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 punës së çdo detyre është e njohur.

Metrikat e Planifikuesit

Përveç disa supozimeve mbi ngarkesën, është e nevojshme gjithashtu një mjet krahasimi i politikave të ndryshme të planifikimit: metrikat e planifikuesit. Metrika është thjesht një masë e diçkaje. Ekzistojnë disa metrika që mund të përdoren për të krahasuar planifikuesit.

Si shembull, do të përdorim metrikën që quhet koha e kthimit (turnaround time). Koha e kthimit të një detyre përcaktohet si diferenca midis kohës së përfundimit të detyrës dhe kohës së arritjes së detyrës në sistem.

Tturnaround=Tcompletion−Tarrival

Duke supozuar se të gjitha detyrat mbërritën në të njëjtën kohë, atëherë Ta=0 dhe kështu Tt=Tc. Ky vlerë natyrshëm do të ndryshojë kur të ndryshojmë supozimet e lartpërmendura.

Metrika tjetër është drejtësia (drejtësi, ndershmëri). Performanca dhe ndershmëria shpesh janë karakteristika që e kundërshtojnë njëra-tjetrën në planifikim. Për shembull, një planifikues mund të optimizojë performancën, por me çmimin e pritjes për fillimin e detyrave të tjera, duke reduktuar kështu ndershmërinë.

E PARA MË E PARA (FIFO)

Algoritmi më i thjeshtë që mund të implementojmë quhet FIFO ose i pari që vjen (brenda), i pari që shërbehet (jashtë). Ky algoritëm ka disa avantazhe: është shumë i thjeshtë për t'u zbatuar dhe përgjigjet të gjitha supozimeve tona, duke kryer punën mjaft mirë.

Le të shqyrtojmë një shembull të thjeshtë. Supozoni se 3 detyra janë paraqitur në të njëjtën kohë. Por le të supozojmë që detyra A erdhi pak më herët se të tjerat, kështu që në listën e ekzekutimit do të renditet më parë se të tjerat, ashtu si B përballë V. Le të supozojmë se secila prej tyre do të ekzekutohet për 10 sekonda. Cili do të jetë mesatarja e kohës së ekzekutimit të këtyre detyrave?

Duke llogaritur vlerat — 10+20+30 dhe duke e ndarë me 3, do të merrni mesataren e kohës së ekzekutimit të programit që është e barabartë me 20 sekonda.
Tani le të provojmë të ndërojmë supozimet tona. Në veçanti, supozimi 1 dhe kështu nuk do të supozojmë më se çdo detyrë zgjat një kohë të njëjtë. Si do të tregojë veten FIFO këtë herë?

Siç duket, kohët e ndryshme të ekzekutimit të detyrave ndikojnë shumë negativisht në produktivitetin e algoritmit FIFO. Le të supozojmë se detyra A do të zgjasë 100 sekonda, ndërsa B dhe V do të mbeten me nga 10 secila.

Siç shihet nga figura, koha mesatare për sistemin do të jetë (100+110+120)/3=110. Ky efekt quhet efekti i konvojit, kur disa përdorues të shpejtë të një resursi bien në radhë pas një konsumatori të rëndë. Kjo është si një radhë në një dyqan ushqimor, kur përpara jush është një blerës me një karrocë të mbushur. Zgjidhja më e mirë e problemit është të provoni të ndryshoni kasën ose të relaksoheni dhe të fryni thellë.

Shortest Job First

A mund të zgjidhet ndonjëherë një situatë e tillë me procese të rëndë? Sigurisht. Një lloj tjetër planifikimi quhetShortest Job First (SJF). Algoritmi i tij është gjithashtu mjaft primitiv — siç e tregon emri, do të ekzekutohen fillimisht detyrat më të shkurtra njëra pas tjetrës.

Në këtë shembull, rezultati i ekzekutimit të të njëjtave procese do të jetë përmirësimi i mesatares së kohës së përfundimit të programeve dhe ajo do të jetë 50 në vend të 110, që është pothuajse dyfish më mirë.

Prandaj, për supozimin e dhënë që të gjitha detyrat mbërrijnë në të njëjtën kohë, algoritmi SJF duket si algoritmi më optimal. Megjithatë, supozimet tona ende nuk duken realiste. Tani do të ndryshojmë supozimin 2 dhe këtë herë do të paraqesim se detyrat mund të mbërrijnë në çdo kohë, dhe jo të gjitha njëkohësisht. Në çfarë problemesh mund të çojë kjo?

Imagjinoni që detyra A (100s) mbërrin e para dhe fillon të ekzekutohet. Në momentin t=10 mbërrijnë detyrat B dhe C, secila nga të cilat do të zë 10 sekonda. Prandaj, 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, le të heqim supozimin 3 që programi është ekzekutuar dhe punon deri në përfundim. Për më tepër, do të na nevojitet mbështetja e pajisjeve dhe, siç mund ta keni menduar, do të përdorim numëruesin për të ndërprerë procesin e punës dhe për të ndezur kontekstet. Kështu, planifikuesi mund të ndërmarrë diçka në momentin e pranimit të detyrave B dhe V — të ndalojë ekzekutimin e detyrës A dhe të vendosë për përpunim detyrat B dhe V, dhe pas përfundimit të tyre të vazhdojë me procesin A. Ky lloj planifikuesi quhet STCFose Preemptive Job First.

Rezultati i këtij planifikuesi do të jetë: ((120-0)+(20-10)+(30-10))/3=50. Keshtu, ky planifikues bëhet edhe më optimal për detyrat tona.

Metrika Koha e përgjigjes (Response Time)

Kështu, nëse ne e dimë që koha e punës së detyrave dhe se këto detyra përdorin vetëm CPU-në, STCF do të ishte zgjidhja më e mirë. Dhe dikur në kohët e hershme, këto algoritme punonin dhe mjaft mirë. Megjithatë tani, përdoruesi kalon shumicën e kohës para terminalit dhe pret nga ai një ndërveprim tërheqës dhe efikas. Kështu lindi metrika e re — kohë përgjigjeje (përgjigje).

Koha e përgjigjes llogaritet si vijon:

Tresponse=Tfirstrun−Tarrival

Prandaj, për shembullin e mëparshëm, koha e përgjigjes do të jetë kështu: A=0, B=0, C=10 (abg=3,33).

Dhe rezulton se algoritmi STCF nuk është aq i mirë në situatën kur 3 detyra mbërrijnë njëkohësisht — do të duhet të presë derisa detyrat e vogla të përfundojnë plotësisht. Prandaj, algoritmi është i mirë për metrikën e kohës së kthesës, por i keq për metrikën e ndërveprimit. Imagjinoni se duke qenë pas një terminali, në përpjekje për të shkruar simbole në një editor, do të keni për të pritur më shumë se 10 sekonda, sepse ndonjë detyrë tjetër po zë procesorin. Kjo nuk është shumë e këndshme.

Prandaj, përballohemi me një problem tjetër — si mund të ndërtojmë një planifikues që të jetë i ndjeshëm ndaj kohës së përgjigjes?

Round Robin

Për zgjidhjen e këtij problemi është zhvilluar një algoritëm Round Robin (RR). Ideja kryesore është mjaft e thjeshtë: në vend që të fillojmë detyrat deri në përfundim të plotë, do të nisim një detyrë për një interval të caktuar kohe (të quajtur kuant kohe) dhe pastaj do të kalojmë në një detyrë tjetër nga radhitja. Algoritmi përsërit punën e tij derisa të gjitha detyrat të përfundojnë. Gjatësia e punës së programit duhet të jetë e pjestueshme me kohën kur timer-i do të ndërpresë procesin. Për shembull, nëse timer-i ndërpret procesin çdo x=10ms, atëherë madhësia e dritares së ekzekutimit të procesit duhet të jetë e pjestueshme me 10 dhe të jetë 10, 20 ose x*10.

Le të shqyrtojmë një shembull: Detyrat A, B, C arrin njëkohësisht në sistem dhe secila prej tyre dëshiron të punojë për 5 sekonda. Algoritmi SJF do të ekzekutojë çdo detyrë deri në fund, përpara se të nisë një tjetër. Në kontrast, algoritmi RR me një dritare ekzekutimi=1s do të kalojë përmes detyrave si në vijim (fig. 4.3):

(SJF Përsëri (Keq për Koha e Përgjigjes)

(Round Robin (Mirë për Koha 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 koha e dritares është një parametr 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ëni atë shumë të vogël, pasi koha për të kaluar mes konteksteve gjithashtu do të luajë rolin e vet në performancën totale. Prandaj, zgjedhja e kohës së dritares së ekzekutimit përcaktohet nga arkitekti i OS-së dhe varet nga detyrat që parashikohen të ekzekutohen aty. Kalimi i konteksteve nuk është operacioni i vetëm që konsumon kohë — programi i ekzekutuar operon edhe me shumë gjëra të tjera, për shembull me cache të ndryshme dhe çdo herë kur ndodh kalimi, është e nevojshme të ruhet dhe të rikthehet kjo mjedis, gjë që gjithashtu mund të kërkojë shumë kohë.

RR është një planifikues i shkëlqyer, nëse do flisnim vetëm për metriken e kohës së përgjigjes. Por si do të sillet metrika e kohës së kthesës së detyrës me këtë algoritm? Le të shqyrtojmë shembullin më sipër, ku koha e punës A, B, C = 5s dhe hyjnë në të njëjtën kohë. Detyra A do të përfundojë në 13, B në 14, C në 15s, dhe koha e mesme e kthesës do të jetë 14s. Pra, RR është algoritmi më i dobët për metrikën e kthesës.

Në fjalë më të përgjithshme, çdo algoritëm i tipit RR është korrekt, ai ndan kohën e përpunimit në CPU në mënyrë të barabartë midis të gjithë proceseve. Kështu, këto metrika përplasen vazhdimisht me njëra-tjetrën.

Kështu, ne kemi disa algoritma në kundërshtim dhe gjithashtu mbeten disa supozime — lidhur me atë se koha e detyrës është e njohur dhe se detyra përdor vetëm CPU-në.

Përzierja me I/O

Së pari, do të heqim supozimin 4, që procesi përdor vetëm CPU-në; natyrisht, kjo nuk është e vërtetë dhe proceset mund të aksesojnë edhe pajisje të tjera.

Në momentin kur një proces kërkon një operacion I/O, procesi kalon në gjendjen e bllokuar, duke pritur për përfundimin e I/O. Nëse I/O dërgohet në diskun e fortë, atëherë një operacion i tillë mund të zgjasë deri në disa ms ose më gjatë, dhe procesori për këtë kohë do të jetë i papunë. Gjatë kësaj kohe, planifikuesi mund ta zë procesorin me ndonjë proces tjetër. Zgjidhja tjetër që do të duhet të marrë planifikuesi është — kur procesi do të përfundojë I/O-në e tij. Kur kjo ndodh, do të ndodhë një ndërprerje dhe OS do të kalojë procesin që ka kërkuar I/O në gjendjen e gatshme.

Të shqyrtojmë një shembull nga disa detyra. Çdo njëra prej tyre kërkon 50ms kohë procesori. Megjithatë, e para do të kontaktojë me I/O çdo 10ms (i cili gjithashtu do të ekzekutohet për 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 aktivizojmë një proces si A? Ai do të procedojë si më poshtë — së pari do të përfundojë plotësisht procesin A, pastaj procesin B.

Qasja tradicionale për zgjidhjen e kësaj problemi është të interpretojë çdo nën-detyrë 10ms të procesit A si një detyrë të veçantë. Në këtë mënyrë, kur fillojmë me algoritmin STJF, zgjedhja midis një detyre 50ms dhe një detyre 10ms është e qartë. Pastaj, kur nën-detyrë A përfundon, do të nisë procesi B dhe I/O. Pas përfundimit të I/O, do të merret vendimi për të nisur përsëri procesin 10ms A në vend të procesit B. Kështu është e mundur të realizohet mbivendosja, kur CPU përdoret nga një proces tjetër, ndërsa i pari pret për I/O. Dhe si rezultat, sistemi përdoret më mirë — në momentin kur proceset interaktive presin I/O, mund të ekzekutohen edhe procese të tjera në procesor.

Oracle nuk është më.

Tani do të përpiqemi të heqim dorë nga supozimi që koha e ekzekutimit të detyrës është e njohur. Kjo në thelb është supozimi më i keq dhe më i pabesueshëm nga i gjithë lista. Në fakt, në sistemet operative mesatare, vetë sistemi operacional zakonisht di shumë pak për kohën e ekzekutimit të detyrave, prandaj si mund të ndërtosh një planifikues pa e ditur se sa kohë do të zgjasë një detyrë? Ndoshta mund të përdorim disa parime të RR për të zgjidhur këtë problem?

Përfundimi

Ne shqyrtuam ide të bazuara për planifikimin e detyrave dhe shqyrtuam dy familje planifikuesish. I pari nis detyrën më të shkurtër fillimisht dhe kështu rrit kohën e përmbushjes, ndërsa tjetri ndan kohën e ekzekutimit në mënyrë të barabartë mes të gjitha detyrave, duke rritur kohën e reagimit. Të dy algoritmet janë të këqij atje ku algoritmet e një familjeje tjetër janë të mira. Po ashtu shqyrtuam si përdorimi paralel i CPU dhe I/O mund të përmirësojë performancën, por nuk zgjidhëm problemin me vizionin e sistemit operativ. Në mësimin e ardhshëm, 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