Ievads operÄtÄjsistÄmÄs
Äau Habr! Es vÄlos vÄrst jÅ«su uzmanÄ«bu uz vienas, manuprÄt, interesantas literatÅ«ras - OSTEP - rakstu sÄriju-tulkojumiem. Å ajÄ materiÄlÄ diezgan dziļi aplÅ«kots unix lÄ«dzÄ«gu operÄtÄjsistÄmu darbs, proti, darbs ar procesiem, dažÄdiem plÄnotÄjiem, atmiÅu un citiem lÄ«dzÄ«giem komponentiem, kas veido modernu OS. Visu materiÄlu oriÄ£inÄlus varat apskatÄ«t Å”eit . LÅ«dzu, Åemiet vÄrÄ, ka tulkojums tika veikts neprofesionÄli (diezgan brÄ«vi), bet es ceru, ka es saglabÄju vispÄrÄjo nozÄ«mi.
Laboratorijas darbus par Å”o tÄmu var atrast Å”eit:
Citas daļas:
Varat arÄ« apskatÄ«t manu kanÄlu vietnÄ =)
Ievads plÄnotÄjÄ
ProblÄmas bÅ«tÄ«ba: KÄ izstrÄdÄt plÄnotÄja politiku
KÄ bÅ«tu jÄizstrÄdÄ pamatÄ esoÅ”Äs plÄnotÄja politikas struktÅ«ras? KÄdiem jÄbÅ«t galvenajiem pieÅÄmumiem? KÄdi rÄdÄ«tÄji ir svarÄ«gi? KÄdas pamatmetodes tika izmantotas agrÄ«nÄs skaitļoÅ”anas sistÄmÄs?
Darba slodzes pieÅÄmumi
Pirms apspriest iespÄjamÄs politikas, vispirms izdarÄ«sim dažas vienkÄrÅ”ojoÅ”as atkÄpes par sistÄmÄ strÄdÄjoÅ”ajiem procesiem, kurus kopÄ sauc darba slodze. Darba slodzes noteikÅ”ana ir bÅ«tiska veidoÅ”anas politikas sastÄvdaļa, un, jo vairÄk jÅ«s zinÄt par darba slodzi, jo labÄku politiku varat uzrakstÄ«t.
IzdarÄ«sim Å”Ädus pieÅÄmumus par sistÄmÄ strÄdÄjoÅ”ajiem procesiem, kurus dažreiz sauc arÄ« par darba vietas (uzdevumi). GandrÄ«z visi Å”ie pieÅÄmumi nav reÄli, bet nepiecieÅ”ami domas attÄ«stÄ«bai.
- Katrs uzdevums tiek izpildÄ«ts vienÄdu laiku,
- Visi uzdevumi tiek iestatīti vienlaicīgi,
- Uzdotais uzdevums darbojas lÄ«dz tÄ pabeigÅ”anai,
- Visi uzdevumi izmanto tikai centrÄlo procesoru,
- Katra uzdevuma izpildes laiks ir zinÄms.
PlÄnotÄja metrika
Papildus dažiem pieÅÄmumiem par slodzi ir nepiecieÅ”ams vÄl viens rÄ«ks dažÄdu plÄnoÅ”anas politiku salÄ«dzinÄÅ”anai: plÄnotÄja metrika. Metrika ir tikai kaut kÄds mÄrs. Ir vairÄki rÄdÄ«tÄji, ko var izmantot, lai salÄ«dzinÄtu plÄnotÄjus.
PiemÄram, mÄs izmantosim metriku ar nosaukumu apgrozÄ«juma laiks (apgrozÄ«juma laiks). Uzdevuma izpildes laiks tiek definÄts kÄ starpÄ«ba starp uzdevuma izpildes laiku un uzdevuma ieraÅ”anÄs laiku sistÄmÄ.
Tturnaround=TpabeigÅ”ana-nonÄkÅ”ana
TÄ kÄ mÄs pieÅÄmÄm, ka visi uzdevumi ieradÄs vienlaicÄ«gi, tad Ta=0 un lÄ«dz ar to Tt=Tc. Å Ä« vÄrtÄ«ba dabiski mainÄ«sies, mainot iepriekÅ” minÄtos pieÅÄmumus.
VÄl viens rÄdÄ«tÄjs - taisnÄ«gums (taisnÄ«gums, godÄ«gums). ProduktivitÄte un godÄ«gums plÄnoÅ”anÄ bieži ir pretÄjas Ä«paŔības. PiemÄram, plÄnotÄjs var optimizÄt veiktspÄju, taÄu uz citu uzdevumu izpildes gaidÄ«Å”anas rÄÄ·ina, tÄdÄjÄdi samazinot godÄ«gumu.
FIRST IN FIRST OUT (FIFO)
VisvienkÄrÅ”Äko algoritmu, ko varam ieviest, sauc par FIFO vai pirmais ienÄcÄjs, pirmais. Å im algoritmam ir vairÄkas priekÅ”rocÄ«bas: to ir ļoti viegli ieviest, tas atbilst visiem mÅ«su pieÅÄmumiem un veic darbu diezgan labi.
ApskatÄ«sim vienkÄrÅ”u piemÄru. PieÅemsim, ka vienlaikus tika uzstÄdÄ«ti 3 uzdevumi. Bet pieÅemsim, ka uzdevums A ieradÄs nedaudz agrÄk par visiem pÄrÄjiem, tÄpÄc tas parÄdÄ«sies izpildes sarakstÄ agrÄk nekÄ citi, tÄpat kÄ B attiecÄ«bÄ pret C. PieÅemsim, ka katrs no tiem tiks izpildÄ«ts 10 sekundes. KÄds bÅ«s vidÄjais laiks Å”o uzdevumu veikÅ”anai Å”ajÄ gadÄ«jumÄ?
Saskaitot vÄrtÄ«bas - 10+20+30 un dalot ar 3, iegÅ«stam vidÄjo programmas izpildes laiku, kas vienÄds ar 20 sekundÄm.
Tagad mÄÄ£inÄsim mainÄ«t savus pieÅÄmumus. KonkrÄti, 1. pieÅÄmums, un tÄdÄjÄdi mÄs vairs neuzskatÄ«sim, ka katra uzdevuma izpildei nepiecieÅ”ams tikpat daudz laika. KÄ FIFO veiksies Å”oreiz?
KÄ izrÄdÄs, dažÄdi uzdevumu izpildes laiki ÄrkÄrtÄ«gi negatÄ«vi ietekmÄ FIFO algoritma produktivitÄti. PieÅemsim, ka uzdevuma A izpildei bÅ«s nepiecieÅ”amas 100 sekundes, savukÄrt B un C uzdevumam joprojÄm bÅ«s nepiecieÅ”amas 10 sekundes.
KÄ redzams attÄlÄ, vidÄjais laiks sistÄmai bÅ«s (100+110+120)/3=110. Å o efektu sauc konvoja efekts, kad daži resursa Ä«stermiÅa patÄrÄtÄji stÄvÄs rindÄ pÄc smagÄ patÄrÄtÄja. Tas ir kÄ rinda pie pÄrtikas preÄu veikala, kad jÅ«su priekÅ”Ä ir klients ar pilniem groziem. LabÄkais problÄmas risinÄjums ir mÄÄ£inÄt nomainÄ«t kases aparÄtu vai atpÅ«sties un dziļi elpot.
Vispirms Ä«sÄkais darbs
Vai ir iespÄjams kaut kÄ atrisinÄt lÄ«dzÄ«gu situÄciju ar smagajiem procesiem? Noteikti. Cits plÄnoÅ”anas veids tiek sauktsVispirms Ä«sÄkais darbs (SJF). ArÄ« tÄ algoritms ir visai primitÄ«vs ā kÄ jau nosauca nosaukums, tad viens pÄc otra vispirms tiks palaisti Ä«sÄkie uzdevumi.
Å ajÄ piemÄrÄ to paÅ”u procesu izpildes rezultÄts bÅ«s vidÄjÄ programmas izpildes laika uzlabojums, un tas bÅ«s vienÄds ar 50, nevis 110, kas ir gandrÄ«z 2 reizes labÄks.
TÄdÄjÄdi pie dotÄ pieÅÄmuma, ka visi uzdevumi ierodas vienlaicÄ«gi, SJF algoritms Ŕķiet optimÄlÄkais algoritms. TomÄr mÅ«su pieÅÄmumi joprojÄm neŔķiet reÄli. Å oreiz mÄs mainÄm 2. pieÅÄmumu un Å”oreiz iedomÄjamies, ka uzdevumi var bÅ«t klÄt jebkurÄ laikÄ, nevis visi vienlaicÄ«gi. Pie kÄdÄm problÄmÄm tas var novest?
IedomÄsimies, ka uzdevums A (100c) pienÄk pirmais un tiek sÄkts izpildÄ«t. Pie t=10 pienÄk uzdevumi B un C, katrs no tiem aizÅems 10 sekundes. TÄtad vidÄjais izpildes laiks ir (100+(110-10)+(120-10))3 = 103. Ko plÄnotÄjs varÄtu darÄ«t, lai to uzlabotu?
Vispirms Ä«sÄkais laiks lÄ«dz pabeigÅ”anai (STCF)
Lai uzlabotu situÄciju, mÄs izlaižam 3. pieÅÄmumu, ka programma ir uzsÄkta un darbojas lÄ«dz pabeigÅ”anai. TurklÄt mums bÅ«s nepiecieÅ”ams aparatÅ«ras atbalsts, un, kÄ jÅ«s varÄtu nojaust, mÄs to izmantosim taimeris lai pÄrtrauktu skrieÅ”anas uzdevumu un konteksta maiÅa. TÄdÄjÄdi plÄnotÄjs var kaut ko darÄ«t brÄ«dÄ«, kad pienÄk uzdevumi B, C - pÄrtraukt uzdevuma A izpildi un nodot uzdevumus B un C apstrÄdÄ un pÄc to pabeigÅ”anas turpinÄt procesa A izpildi. Å Äds plÄnotÄjs tiek saukts STCFvai PreventÄ«vs darbs vispirms.
Å Ä« plÄnotÄja rezultÄts bÅ«s Å”Äds: ((120-0)+(20-10)+(30-10))/3=50. TÄdÄjÄdi Å”Äds plÄnotÄjs kļūst vÄl optimÄlÄks mÅ«su uzdevumiem.
Metriskais reakcijas laiks
TÄdÄjÄdi, ja mÄs zinÄm uzdevumu izpildes laiku un to, ka Å”ie uzdevumi izmanto tikai centrÄlo procesoru, STCF bÅ«s labÄkais risinÄjums. Un kÄdreiz agrÄkos laikos Å”ie algoritmi darbojÄs diezgan labi. TomÄr tagad lietotÄjs lielÄko daļu sava laika pavada terminÄlÄ« un sagaida produktÄ«vu interaktÄ«vu pieredzi. TÄdÄjÄdi radÄs jauna metrika - reakcijas laiks (atbilde).
Reakcijas laiks tiek aprÄÄ·inÄts Å”Ädi:
Tresponse=TfirstrunāTarrival
TÄdÄjÄdi iepriekÅ”ÄjÄ piemÄrÄ reakcijas laiks bÅ«s: A=0, B=0, C=10 (abg=3,33).
Un izrÄdÄs, ka STCF algoritms nav tik labs situÄcijÄ, kad pienÄk 3 uzdevumi vienlaicÄ«gi ā bÅ«s jÄgaida lÄ«dz mazie uzdevumi bÅ«s pilnÄ«bÄ izpildÄ«ti. TÄtad algoritms ir labs apgrozÄ«juma laika metrikai, bet slikts interaktivitÄtes metrikai. IedomÄjieties, ja jÅ«s sÄdÄtu pie terminÄļa un mÄÄ£inÄtu ievadÄ«t rakstzÄ«mes redaktorÄ un jums jÄgaida vairÄk nekÄ 10 sekundes, jo kÄds cits uzdevums aizÅem CPU. Tas nav Ä«paÅ”i patÄ«kami.
TÄtad mÄs saskaramies ar citu problÄmu - kÄ mÄs varam izveidot plÄnotÄju, kas ir jutÄ«gs pret reakcijas laiku?
Round robin
Å Ä«s problÄmas risinÄÅ”anai tika izstrÄdÄts algoritms Round robin (RR). Pamatideja ir pavisam vienkÄrÅ”a: tÄ vietÄ, lai palaistu uzdevumus, lÄ«dz tie ir pabeigti, mÄs izpildÄ«sim uzdevumu noteiktu laika periodu (sauktu par laika ŔķÄli) un pÄc tam pÄrslÄgsimies uz citu uzdevumu no rindas. Algoritms atkÄrto savu darbu, lÄ«dz visi uzdevumi ir pabeigti. Å ajÄ gadÄ«jumÄ programmas darbÄ«bas laikam jÄbÅ«t vairÄkkÄrtÄjam laikam, pÄc kura taimeris pÄrtrauks procesu. PiemÄram, ja taimeris pÄrtrauc procesu ik pÄc x=10 ms, procesa izpildes loga lielumam ir jÄbÅ«t 10 reizinÄjumam un jÄbÅ«t 10,20 vai x*10.
ApskatÄ«sim piemÄru: ABC uzdevumi sistÄmÄ ierodas vienlaicÄ«gi un katrs no tiem vÄlas darboties 5 sekundes. SJF algoritms pabeigs katru uzdevumu, pirms sÄks citu. Turpretim RR algoritms ar palaiÅ”anas logu = 1s veiks uzdevumus Å”Ädi (4.3. att.):
(Atkal SJF (slikts reakcijas laikam)
(Round Robin (piemÄrots reakcijas laikam)
VidÄjais reakcijas laiks RR algoritmam ir (0+1+2)/3=1, savukÄrt SJF (0+5+10)/3=5.
Ir loÄ£iski pieÅemt, ka laika logs ir ļoti svarÄ«gs RR parametrs; jo mazÄks tas ir, jo lielÄks ir reakcijas laiks. TomÄr nevajadzÄtu to padarÄ«t pÄrÄk mazu, jo konteksta pÄrslÄgÅ”anas laikam bÅ«s arÄ« nozÄ«me kopÄjÄ veiktspÄjÄ. TÄdÄjÄdi izpildes loga laika izvÄli nosaka OS arhitekts un tÄ ir atkarÄ«ga no uzdevumiem, kurus tajÄ plÄnots izpildÄ«t. Konteksta pÄrslÄgÅ”ana nav vienÄ«gÄ servisa darbÄ«ba, kas tÄrÄ laiku - palaistÄ programma darbojas ar daudzÄm citÄm lietÄm, piemÄram, dažÄdÄm keÅ”atmiÅÄm, un ar katru slÄdzi ir jÄsaglabÄ un jÄatjauno Ŕī vide, kas arÄ« var aizÅemt daudz laiks.
RR ir lielisks plÄnotÄjs, ja mÄs runÄjam tikai par reakcijas laika metriku. Bet kÄ uzdevuma izpildes laika metrika darbosies ar Å”o algoritmu? Apsveriet iepriekÅ” minÄto piemÄru, kad darbÄ«bas laiks A, B, C = 5s un ierodas tajÄ paÅ”Ä laikÄ. A uzdevums beigsies plkst. 13, B - plkst. 14, C - plkst. 15, un vidÄjais izpildes laiks bÅ«s 14 s. TÄdÄjÄdi RR ir sliktÄkais algoritms apgrozÄ«juma rÄdÄ«tÄjam.
VispÄrÄ«gÄk runÄjot, jebkurÅ” RR tipa algoritms ir godÄ«gs; tas sadala CPU laiku vienÄdi starp visiem procesiem. TÄdÄjÄdi Å”ie rÄdÄ«tÄji pastÄvÄ«gi konfliktÄ viens ar otru.
TÄdÄjÄdi mums ir vairÄki kontrastÄjoÅ”i algoritmi un tajÄ paÅ”Ä laikÄ joprojÄm ir palikuÅ”i vairÄki pieÅÄmumi - ka uzdevuma laiks ir zinÄms un uzdevums izmanto tikai centrÄlo procesoru.
SajaukŔana ar I/O
PirmkÄrt, noÅemsim 4. pieÅÄmumu, ka process izmanto tikai centrÄlo procesoru; dabiski, ka tas tÄ nav, un procesi var piekļūt citam aprÄ«kojumam.
BrÄ«dÄ«, kad kÄds process pieprasa I/O darbÄ«bu, process nonÄk bloÄ·ÄtÄ stÄvoklÄ«, gaidot, kamÄr I/O tiks pabeigts. Ja I/O tiek nosÅ«tÄ«ts uz cieto disku, tad Å”Äda darbÄ«ba var ilgt pat vairÄkas ms vai ilgÄk, un procesors Å”ajÄ brÄ«dÄ« bÅ«s dÄ«kstÄvÄ. Å ajÄ laikÄ plÄnotÄjs var aizÅemt procesoru ar jebkuru citu procesu. NÄkamais lÄmums, kas plÄnotÄjam bÅ«s jÄpieÅem, ir tad, kad process pabeigs savu I/O. Kad tas notiks, notiks pÄrtraukums, un OS iestatÄ«s procesu, kas izsauca I/O, gatavÄ«bas stÄvoklÄ«.
ApskatÄ«sim vairÄku uzdevumu piemÄru. Katrs no tiem prasa 50 ms CPU laika. TomÄr pirmais piekļūs I/O ik pÄc 10 ms (kas arÄ« tiks izpildÄ«ts ik pÄc 10 ms). Un process B vienkÄrÅ”i izmanto 50 ms procesoru bez I/O.
Å ajÄ piemÄrÄ mÄs izmantosim STCF plÄnotÄju. KÄ plÄnotÄjs rÄ«kosies, ja tajÄ tiks palaists tÄds process kÄ A? ViÅÅ” rÄ«kosies Å”Ädi: vispirms viÅÅ” pilnÄ«bÄ izstrÄdÄs procesu A un pÄc tam procesu B.
TradicionÄlÄ pieeja Ŕīs problÄmas risinÄÅ”anai ir apstrÄdÄt katru procesa A 10 ms apakÅ”uzdevumu kÄ atseviŔķu uzdevumu. TÄdÄjÄdi, sÄkot ar STJF algoritmu, izvÄle starp 50 ms uzdevumu un 10 ms uzdevumu ir acÄ«mredzama. PÄc tam, kad apakÅ”uzdevums A ir pabeigts, tiks palaists process B un I/O. PÄc ievades/izvades pabeigÅ”anas bÅ«s ierasts no jauna palaist 10 ms procesu A, nevis procesu B. TÄdÄ veidÄ ir iespÄjams Ä«stenot pÄrklÄÅ”anos, kur CPU izmanto cits process, kamÄr pirmais gaida I/O. Un rezultÄtÄ sistÄma ir labÄk noslogota - brÄ«dÄ«, kad interaktÄ«vie procesi gaida I/O, uz procesora var tikt izpildÄ«ti citi procesi.
OrÄkula vairs nav
Tagad mÄÄ£inÄsim atbrÄ«voties no pieÅÄmuma, ka ir zinÄms uzdevuma izpildes laiks. Tas parasti ir sliktÄkais un nereÄlÄkais pieÅÄmums visÄ sarakstÄ. Faktiski vidÄjÄ parastajÄ operÄtÄjsistÄmÄ pati OS parasti ļoti maz zina par uzdevumu izpildes laiku, tÄpÄc kÄ tad jÅ«s varat izveidot plÄnotÄju, nezinot, cik ilgi uzdevums tiks izpildÄ«ts? VarbÅ«t mÄs varÄtu izmantot dažus RR principus, lai atrisinÄtu Å”o problÄmu?
Kopsavilkums
MÄs apskatÄ«jÄm uzdevumu plÄnoÅ”anas pamatidejas un apskatÄ«jÄm 2 plÄnotÄju Ä£imenes. Pirmais vispirms sÄk Ä«sÄko uzdevumu un tÄdÄjÄdi palielina izpildes laiku, bet otrais tiek sadalÄ«ts starp visiem uzdevumiem vienÄdi, palielinot reakcijas laiku. Abi algoritmi ir slikti, ja otras Ä£imenes algoritmi ir labi. MÄs arÄ« apskatÄ«jÄm, kÄ paralÄla CPU un I/O izmantoÅ”ana var uzlabot veiktspÄju, taÄu neatrisinÄjÄm problÄmu ar OS gaiÅ”redzÄ«bu. Un nÄkamajÄ nodarbÄ«bÄ mÄs apskatÄ«sim plÄnotÄju, kas ieskatÄs tuvÄkajÄ pagÄtnÄ un mÄÄ£ina paredzÄt nÄkotni. Un to sauc par daudzlÄ«meÅu atsauksmju rindu.
Avots: www.habr.com