Yntroduksje ta bestjoeringssystemen
Hoi Habr! Ik soe graach bringe jo oandacht in rige fan artikels-oersettingen fan ien nijsgjirrige literatuer yn myn miening - OSTEP. Dit materiaal besprekt frij djip it wurk fan unix-like bestjoeringssystemen, nammentlik wurk mei prosessen, ferskate planners, ûnthâld en oare ferlykbere komponinten dy't in moderne OS foarmje. Jo kinne hjir it orizjineel fan alle materialen sjen . Tink derom dat de oersetting ûnprofesjoneel makke is (hiel frij), mar ik hoopje dat ik de algemiene betsjutting behâlden haw.
Labwurk oer dit ûnderwerp is hjir te finen:
Oare dielen:
Jo kinne ek kontrolearje út myn kanaal op =)
Yntroduksje ta Scheduler
De essinsje fan it probleem: Hoe kinne jo in plannerbelied ûntwikkelje
Hoe moatte de ûnderlizzende beliedskaders foar planner wurde ûntwurpen? Wat moatte de wichtichste oannames wêze? Hokker metriken binne wichtich? Hokker basistechniken waarden brûkt yn iere kompjûtersystemen?
Oannames fan wurkdruk
Foardat wy mooglik belied besprekke, litte wy earst in pear ferienfâldigjende digresjes meitsje oer de prosessen dy't rinne yn it systeem, dy't kollektyf wurde neamd wurkdruk. It definiearjen fan de wurkdruk is in kritysk ûnderdiel fan it bouwen fan belied, en hoe mear jo witte oer de wurkdruk, hoe better it belied dat jo kinne skriuwe.
Litte wy de folgjende oannames meitsje oer de prosessen dy't rinne yn it systeem, soms ek neamd jobs (taken). Hast al dizze oannames binne net realistysk, mar binne nedich foar de ûntwikkeling fan tinken.
- Elke taak rint foar deselde tiid,
- Alle taken wurde tagelyk ynsteld,
- De tawiisde taak wurket oant syn foltôging,
- Alle taken brûke allinich CPU,
- De rinnende tiid fan elke taak is bekend.
Planner Metrics
Neist guon oannames oer de lading, is in oar ark nedich foar it fergelykjen fan ferskate skemabeliedsbelied: plannermetriken. In metrysk is gewoan wat mjitte fan wat. D'r binne in oantal metriken dy't kinne wurde brûkt om planners te fergelykjen.
Bygelyks, wy sille brûke in metrike neamd omrintiid (omrintiid). De omlooptiid fan 'e taak wurdt definiearre as it ferskil tusken de tiid foar foltôging fan' e taak en de oankomsttiid fan 'e taak yn it systeem.
Tturnaround=Tfoltôging-Tarrival
Om't wy oannommen dat alle taken tagelyk kamen, dan Ta = 0 en dus Tt = Tc. Dizze wearde sil fansels feroarje as wy de boppesteande oannames feroarje.
In oare metryske - fairness (reedlikheid, earlikens). Produktiviteit en earlikens binne faak tsjinoerstelde skaaimerken yn planning. Bygelyks, de planner kin de prestaasjes optimalisearje, mar op kosten fan wachtsjen op oare taken om te rinnen, sadat de earlikens ferminderje.
EARST IN EARST OUT (FIFO)
It meast basale algoritme dat wy kinne ymplementearje hjit FIFO of earst komt (yn), earst tsjinne (út). Dit algoritme hat ferskate foardielen: it is heul maklik te ymplementearjen en it past by al ús oannames en docht it wurk frij goed.
Litte wy nei in ienfâldich foarbyld sjen. Litte wy sizze dat 3 taken tagelyk ynsteld binne. Mar lit ús oannimme dat taak A kaam in bytsje earder as alle oaren, dus it sil ferskine yn 'e útfiering list earder as de oaren, krekt as B relatyf oan C. Lit ús oannimme dat elk fan harren sil wurde útfierd foar 10 sekonden. Wat sil de gemiddelde tiid wêze om dizze taken yn dit gefal te foltôgjen?
Troch de wearden te tellen - 10+20+30 en te dielen troch 3, krije wy de gemiddelde programma-útfiertiid gelyk oan 20 sekonden.
Litte wy no besykje ús oannames te feroarjen. Benammen oanname 1 en dus wy sille net langer oannimme dat elke taak duorret deselde tiid om út te fieren. Hoe sil FIFO dizze kear prestearje?
As it docht bliken, hawwe ferskillende útfieringstiden fan taak in ekstreem negative ynfloed op de produktiviteit fan it FIFO-algoritme. Litte wy oannimme dat taak A 100 sekonden nimt om te foltôgjen, wylst B en C elk noch 10 sekonden nimme.
As kin sjoen wurde út de figuer, de gemiddelde tiid foar it systeem sil wêze (100 + 110 + 120) / 3 = 110. Dit effekt wurdt neamd konvoai effekt, doe't guon koarte-termyn konsuminten fan in boarne sil wachtrige nei in swiere konsumint. It is as de rigel by de bakkerij as der in klant foar jo is mei in folle karre. De bêste oplossing foar it probleem is om te besykjen de kassa te feroarjen of te ûntspannen en djip te sykheljen.
Koarste baan earst
Is it mooglik om ien of oare manier op te lossen in ferlykbere situaasje mei swiergewicht prosessen? Wis. In oare soarte fan planning wurdt neamdKoarste baan earst (SJF). It algoritme is ek frij primityf - lykas de namme al fermoeden docht, sille de koartste taken earst, de iene nei de oare, wurde lansearre.
Yn dit foarbyld sil it resultaat fan it útfieren fan deselde prosessen in ferbettering wêze yn 'e gemiddelde programma-omlooptiid en it sil gelyk wêze oan 50 ynstee fan 110, dat is hast 2 kear better.
Dus, foar de opjûne oanname dat alle taken tagelyk oankomme, liket it SJF-algoritme it meast optimale algoritme te wêzen. Us oannames lykje lykwols noch net realistysk. Dizze kear feroarje wy oanname 2 en stel ús dizze kear foar dat taken op elk momint oanwêzich kinne wêze, en net allegear tagelyk. Hokker problemen kin dit liede ta?
Litte wy ús foarstelle dat taak A (100c) earst komt en begjint te wurde útfierd. Op t = 10 komme de taken B en C oan, dy't elk 10 sekonden nimme. De gemiddelde útfieringstiid is dus (100+(110-10)+(120-10))3 = 103. Wat koe de planner dwaan om dit te ferbetterjen?
Shortest Time-to-Completion First (STCF)
Om de situaasje te ferbetterjen, ferlitte wy oanname 3 dat it programma is lansearre en rint oant foltôging. Derneist sille wy hardwarestipe nedich wêze en, lykas jo miskien riede, sille wy brûke timer te ûnderbrekken in rinnende taak en kontekst switching. Sa kin de planner wat dwaan op it momint dat taken B, C oankomme - stopje mei it útfieren fan taak A en set taken B en C yn ferwurking en, nei har foltôging, trochgean mei it útfieren fan proses A. Sa'n planner wurdt neamd STCFof Preemptive Job Earst.
It resultaat fan dizze planner sil it folgjende resultaat wêze: ((120-0)+(20-10)+(30-10))/3=50. Sa wurdt sa'n planner noch optimaal foar ús taken.
Metryske reaksjetiid
Dus, as wy de rinnende tiid fan 'e taken kenne en dat dizze taken allinich CPU brûke, sil STCF de bêste oplossing wêze. En ien kear yn 'e iere tiden wurken dizze algoritmen frij goed. De brûker bringt no it measte fan har tiid troch by de terminal en ferwachtet in produktive ynteraktive ûnderfining. Sa waard in nije metrik berne - reaksjetiid (antwurd).
De reaksjetiid wurdt as folget berekkene:
Tresponse=Tfirstrun−Tarrival
Sa sil foar it foarige foarbyld de antwurdtiid wêze: A=0, B=0, C=10 (abg=3,33).
En it docht bliken dat it STCF-algoritme net sa goed is yn in situaasje dêr't 3 taken tagelyk oankomme - it sil wachtsje moatte oant de lytse taken folslein foltôge binne. Dat it algoritme is goed foar de metryske omlooptiid, mar min foar de ynteraktiviteitsmetrik. Stel jo foar dat jo by in terminal sieten en besykje tekens yn in bewurker te typen en mear dan 10 sekonden moatte wachtsje om't in oare taak de CPU opnaam. It is net hiel noflik.
Dat wy wurde konfrontearre mei in oar probleem - hoe kinne wy in planner bouwe dy't gefoelich is foar reaksjetiid?
Om Robin hinne
In algoritme waard ûntwikkele om dit probleem op te lossen Om Robin hinne (RR). It basisidee is frij simpel: ynstee fan taken út te fieren oant se foltôge binne, sille wy de taak foar in bepaalde perioade útfiere (in tiidslice neamd) en dan oerskeakelje nei in oare taak út 'e wachtrige. It algoritme werhellet syn wurk oant alle taken binne foltôge. Yn dit gefal moat de rinnende tiid fan it programma in mearfâld wêze fan 'e tiid wêrnei't de timer it proses sil ûnderbrekke. Bygelyks, as in timer in proses elke x=10ms ûnderbrekt, dan moat de grutte fan it proses-útfierfinster in mearfâld fan 10 wêze en 10,20 of x*10 wêze.
Litte wy nei in foarbyld sjen: ABC-taken komme tagelyk yn it systeem en elk fan har wol 5 sekonden rinne. It SJF-algoritme sil elke taak foltôgje foardat in oare begjint. Yn tsjinstelling sil it RR-algoritme mei in startfinster = 1s troch de taken gean as folget (fig. 4.3):
(SJF Again (Bad for Response Time)
(Round Robin (Goed foar reaksjetiid)
De gemiddelde reaksjetiid foar it RR-algoritme is (0+1+2)/3=1, wylst foar de SJF (0+5+10)/3=5.
It is logysk om oan te nimmen dat it tiidfinster in heul wichtige parameter is foar RR; hoe lytser it is, hoe heger de reaksjetiid. Jo moatte it lykwols net te lyts meitsje, om't kontekstwikseltiid ek in rol sil spylje yn 'e totale prestaasjes. Sa wurdt de kar foar it útfieringsfinstertiid ynsteld troch de OS-arsjitekt en hinget ôf fan 'e taken dy't pland binne om dêryn út te fieren. It wikseljen fan kontekst is net de ienige tsjinstoperaasje dy't tiid fergriemt - it rinnende programma wurket op in protte oare dingen, bygelyks ferskate caches, en mei elke skeakel is it nedich om dizze omjouwing te bewarjen en te herstellen, dy't ek in protte kin nimme tiid.
RR is in geweldige planner as wy it allinich oer de metryske reaksjetiid hiene. Mar hoe sil de metryske taakomlooptiid mei dit algoritme gedrage? Beskôgje it foarbyld hjirboppe, as de operaasjetiid fan A, B, C = 5s en tagelyk oankomme. Taak A sil einigje op 13, B op 14, C om 15 s en de gemiddelde omlooptiid sil 14 s wêze. Sa is RR it minste algoritme foar de omsetmetrik.
Yn mear algemiene termen is elk RR-type algoritme earlik; it dielt de CPU-tiid gelyk tusken alle prosessen. En sadwaande binne dizze metriken konstant yn konflikt mei elkoar.
Sa hawwe wy ferskate kontrastearjende algoritmen en tagelyk binne der noch ferskate oannames oer - dat de taaktiid bekend is en dat de taak allinich de CPU brûkt.
Mingen mei I/O
Lit ús earst fan alle oanname 4 fuortsmite dat it proses allinich de CPU brûkt; fansels is dit net it gefal en kinne prosessen tagong krije ta oare apparatuer.
Op it momint dat elk proses in I / O-operaasje freget, komt it proses yn 'e blokkearre steat, wachtsjend op' e I / O om te foltôgjen. As I / O wurdt stjoerd nei de hurde skiif, sa'n operaasje kin nimme oant ferskate ms of langer, en de prosessor sil wêze idle op dit stuit. Yn dizze tiid kin de planner de prosessor besette mei elk oar proses. It folgjende beslút dat de planner moat meitsje is wannear't it proses syn I / O sil foltôgje. As dit bart, sil in ûnderbrekking foarkomme en sil it OS it proses dat de I / O neamde yn 'e kleare steat sette.
Litte wy nei in foarbyld fan ferskate taken sjen. Elk fan harren fereasket 50ms CPU-tiid. De earste sil lykwols elke 10ms tagong krije ta I / O (dy't ek elke 10ms sil wurde útfierd). En proses B brûkt gewoan in 50ms-prosessor sûnder I/O.
Yn dit foarbyld sille wy de STCF-planner brûke. Hoe sil de planner him gedrage as in proses lykas A derop wurdt lansearre? Hy sil it folgjende dwaan: earst sil hy proses A folslein útwurkje, en dan proses B.
De tradisjonele oanpak om dit probleem op te lossen is om elke 10 ms subtaak fan proses A as in aparte taak te behanneljen. Dus, as jo begjinne mei it STJF-algoritme, is de kar tusken in taak fan 50 ms en in taak fan 10 ms foar de hân. Dan, as subtaak A foltôge is, sille proses B en I/O wurde lansearre. Nei't de I/O foltôge is, sil it gewoanlik wêze om it 10ms proses A opnij te begjinnen ynstee fan proses B. Op dizze manier is it mooglik om oerlap te ymplementearjen, wêrby't de CPU brûkt wurdt troch in oar proses, wylst de earste wachtet op de I/O. En as gefolch wurdt it systeem better brûkt - op it momint dat ynteraktive prosessen wachtsje op I / O, kinne oare prosessen wurde útfierd op 'e prosessor.
It Oracle is net mear
Litte wy no besykje om de oanname kwyt te reitsjen dat de rinnende tiid fan 'e taak bekend is. Dit is oer it algemien de minste en meast ûnrealistyske oanname op 'e heule list. Yn feite, yn it gemiddelde gewoane OS, it OS sels wit meastentiids heul min oer de útfieringstiid fan taken, dus hoe kinne jo dan in planner bouwe sûnder te witten hoe lang de taak sil nimme om út te fieren? Miskien kinne wy wat RR-prinsipes brûke om dit probleem op te lossen?
It resultaat
Wy seagen nei de basisideeën fan taakplanning en seagen nei 2 famyljes fan planners. De earste begjint earst de koartste taak en fergruttet sa de omlooptiid, wylst de twadde likegoed tusken alle taken ferskuord wurdt, wêrtroch de reaksjetiid fergruttet. Beide algoritmen binne min wêr't algoritmen fan 'e oare famylje goed binne. Wy hawwe ek sjoen op hoe't parallel gebrûk fan CPU en I / O kin ferbetterje prestaasjes, mar net oplosse it probleem mei OS helderziendheid. En yn 'e folgjende les sille wy sjen nei in planner dy't sjocht nei it direkte ferline en besiket de takomst te foarsizzen. En it hjit multi-level feedback wachtrige.
Boarne: www.habr.com