Introduzzjoni għas-Sistemi Operattivi
Ħej Habr! Nixtieq inġib għall-attenzjoni tiegħek sensiela ta' artikli-traduzzjonijiet ta' letteratura waħda interessanti fl-opinjoni tiegħi - OSTEP. Dan il-materjal jiddiskuti pjuttost fil-fond ix-xogħol ta 'sistemi operattivi unix-like, jiġifieri, ix-xogħol ma' proċessi, diversi schedulers, memorja, u komponenti oħra simili li jiffurmaw OS modern. Tista 'tara l-oriġinal tal-materjali kollha hawn . Jekk jogħġbok innota li t-traduzzjoni saret b'mod mhux professjonali (pjuttost liberament), iżda nittama li żammejt it-tifsira ġenerali.
Xogħol tal-laboratorju dwar dan is-suġġett jista’ jinstab hawn:
Partijiet oħra:
Tista 'wkoll tiċċekkja l-kanal tiegħi fuq =)
Introduzzjoni għal Scheduler
L-essenza tal-problema: Kif tiżviluppa politika ta 'scheduler
Kif għandhom jitfasslu l-oqfsa sottostanti tal-politika tal-iskedar? X'għandhom ikunu s-suppożizzjonijiet ewlenin? Liema metriċi huma importanti? Liema tekniki bażiċi ntużaw fis-sistemi tal-kompjuter bikrija?
Assunzjonijiet ta' Xogħol
Qabel ma niddiskutu politiki possibbli, ejja l-ewwel nagħmlu ftit digressjonijiet ta’ simplifikazzjoni dwar il-proċessi li jaħdmu fis-sistema, li kollettivament jissejħu ammont ta' xogħol. Id-definizzjoni tal-piż tax-xogħol hija parti kritika tal-politiki tal-bini, u aktar ma tkun taf dwar il-piż tax-xogħol, aħjar tkun il-politika li tista' tikteb.
Ejja nagħmlu s-suppożizzjonijiet li ġejjin dwar il-proċessi li jaħdmu fis-sistema, xi kultant imsejħa wkoll impjiegi (kompiti). Kważi dawn is-suppożizzjonijiet kollha mhumiex realistiċi, iżda huma meħtieġa għall-iżvilupp tal-ħsieb.
- Kull kompitu jdum għall-istess ammont ta' żmien,
- Il-kompiti kollha huma stabbiliti fl-istess ħin,
- Il-kompitu assenjat jaħdem sat-tlestija tiegħu,
- Il-kompiti kollha jużaw biss CPU,
- Il-ħin tat-tħaddim ta 'kull kompitu huwa magħruf.
Metriċi tal-Iskedatur
Minbarra xi suppożizzjonijiet dwar it-tagħbija, hija meħtieġa għodda oħra biex jitqabblu politiki ta 'skedar differenti: metriċi tal-iskedar. A metrika hija biss xi miżura ta 'xi ħaġa. Hemm numru ta 'metriċi li jistgħu jintużaw biex iqabblu l-iskedarers.
Per eżempju, se nużaw metrika msejħa ħin tat-tibdil (ħin tat-tibdil). Il-ħin tat-tibdil tal-kompitu huwa definit bħala d-differenza bejn il-ħin tat-tlestija tal-kompitu u l-ħin tal-wasla tal-kompitu fis-sistema.
Tturnaround=Ttlestija−Wasla
Peress li aħna assumejna li l-kompiti kollha waslu fl-istess ħin, allura Ta=0 u għalhekk Tt=Tc. Dan il-valur naturalment jinbidel meta nibdlu s-suppożizzjonijiet ta’ hawn fuq.
Metrika oħra - ġustizzja (ġustizzja, onestà). Il-produttività u l-ġustizzja ħafna drabi huma karatteristiċi opposti fl-ippjanar. Pereżempju, l-iskeduler jista 'jottimizza l-prestazzjoni, iżda bl-ispiża ta' stennija għal kompiti oħra biex iseħħu, u b'hekk inaqqas il-ġustizzja.
L-EWWEL LI JIDĦOL L-EWWEL (FIFO)
L-aktar algoritmu bażiku li nistgħu nimplimentaw jissejjaħ FIFO jew l-ewwel jiġi (jidħol), jinqeda l-ewwel (barra). Dan l-algoritmu għandu diversi vantaġġi: huwa faċli ħafna li jiġi implimentat u jaqbel mas-suppożizzjonijiet kollha tagħna u jagħmel ix-xogħol pjuttost tajjeb.
Ejja nħarsu lejn eżempju sempliċi. Ejja ngħidu 3 kompiti ġew stabbiliti fl-istess ħin. Imma ejja nassumu li l-kompitu A wasal ftit qabel mill-oħrajn kollha, għalhekk se jidher fil-lista ta 'eżekuzzjoni aktar kmieni mill-oħrajn, bħal B relattiv għal C. Ejja nassumu li kull wieħed minnhom se jiġi esegwit għal 10 sekondi. X'se jkun iż-żmien medju biex jitlestew dawn il-kompiti f'dan il-każ?
Billi ngħoddu l-valuri - 10 + 20 + 30 u naqsmu bi 3, niksbu l-ħin medju ta 'eżekuzzjoni tal-programm ugwali għal 20 sekonda.
Issa ejja nippruvaw nibdlu s-suppożizzjonijiet tagħna. B'mod partikolari, l-assunzjoni 1 u għalhekk mhux se nibqgħu nassumu li kull kompitu jieħu l-istess ammont ta 'żmien biex jiġi eżegwit. Kif se twettaq il-FIFO din id-darba?
Kif jirriżulta, ħinijiet differenti ta 'eżekuzzjoni tal-kompiti għandhom impatt estremament negattiv fuq il-produttività tal-algoritmu FIFO. Ejja nassumu li l-kompitu A se jieħu 100 sekonda biex jitlesta, filwaqt li B u C xorta se jieħdu 10 sekondi kull wieħed.
Kif jidher mill-figura, il-ħin medju għas-sistema se jkun (100+110+120)/3=110. Dan l-effett jissejjaħ effett konvoj, meta xi konsumaturi għal żmien qasir ta 'riżorsa jkunu fil-kju wara konsumatur tqil. Qisu l-linja fil-ħanut tal-merċa meta jkun hemm klijent quddiemek b’karrettun sħiħ. L-aħjar soluzzjoni għall-problema hija li tipprova tibdel il-cash register jew tirrilassa u tieħu n-nifs profond.
L-Iqsar Impjieg L-Ewwel
Huwa possibbli li b'xi mod issolvi sitwazzjoni simili bi proċessi heavyweight? Żgur. Tip ieħor ta 'ppjanar huwa msejjaħL-Iqsar Impjieg L-Ewwel (SJF). L-algoritmu tiegħu huwa wkoll pjuttost primittiv - kif jimplika l-isem, l-iqsar kompiti se jiġu mnedija l-ewwel, wieħed wara l-ieħor.
F'dan l-eżempju, ir-riżultat tat-tħaddim tal-istess proċessi se jkun titjib fil-ħin medju tat-tibdil tal-programm u jkun ugwali għal 50 minflok 110, li huwa kważi 2 darbiet aħjar.
Għalhekk, għas-suppożizzjoni mogħtija li l-kompiti kollha jaslu fl-istess ħin, l-algoritmu SJF jidher li huwa l-aktar algoritmu ottimali. Madankollu, is-suppożizzjonijiet tagħna għadhom ma jidhrux realistiċi. Din id-darba nibdlu l-assunzjoni 2 u din id-darba nimmaġinaw li l-kompiti jistgħu jkunu preżenti fi kwalunkwe ħin, u mhux kollha fl-istess ħin. Għal liema problemi jista’ jwassal dan?
Ejja nimmaġinaw li l-kompitu A (100c) jasal l-ewwel u jibda jitwettaq. F't=10, jaslu l-kompiti B u C, li kull wieħed minnhom jieħu 10 sekondi. Allura l-ħin medju ta 'eżekuzzjoni huwa (100+(110-10)+(120-10))3 = 103. X'jista' jagħmel l-iskeduler biex itejjeb dan?
L-Iqsar Żmien għat-Tlestija l-Ewwel (STCF)
Sabiex titjieb is-sitwazzjoni, inħallu barra s-suppożizzjoni 3 li l-programm huwa mniedi u jibqa' għaddej sat-tlestija. Barra minn hekk, ser ikollna bżonn appoġġ għall-ħardwer u, kif tista' taħsbu, se nużaw timer biex tinterrompi biċċa xogħol li taħdem u bidla tal-kuntest. Għalhekk, l-iskedar jista 'jagħmel xi ħaġa fil-mument li jaslu l-kompiti B, C - tieqaf teżegwixxi l-kompitu A u tpoġġi l-kompiti B u C fl-ipproċessar u, wara t-tlestija tagħhom, tkompli tesegwixxi l-proċess A. Tali scheduler jissejjaħ STCFjew Impjieg Preemptiv L-Ewwel.
Ir-riżultat ta 'dan il-pjanifikatur se jkun ir-riżultat li ġej: ((120-0)+(20-10)+(30-10))/3=50. Għalhekk, tali scheduler isir saħansitra aktar ottimali għall-kompiti tagħna.
Ħin ta' Rispons Metriku
Għalhekk, jekk nafu l-ħin tal-ħidma tal-kompiti u li dawn il-kompiti jużaw biss CPU, STCF tkun l-aħjar soluzzjoni. U darba fiż-żminijiet bikrija, dawn l-algoritmi ħadmu pjuttost tajjeb. Madankollu, l-utent issa jqatta 'ħafna mill-ħin tagħha fit-terminal u jistenna esperjenza interattiva produttiva. Għalhekk twieldet metrika ġdida - ħin tar-rispons (rispons).
Il-ħin tar-rispons huwa kkalkulat kif ġej:
Tresponse=Tfirstrun−Tarrival
Għalhekk, għall-eżempju preċedenti, il-ħin tar-rispons se jkun: A=0, B=0, C=10 (abg=3,33).
U jirriżulta li l-algoritmu STCF mhuwiex daqshekk tajjeb f'sitwazzjoni fejn 3 kompiti jaslu fl-istess ħin - se jkollu jistenna sakemm il-kompiti żgħar jitlestew kompletament. Allura l-algoritmu huwa tajjeb għall-metrika tal-ħin tat-tibdil, iżda ħażin għall-metrika tal-interattività. Immaġina kieku kont bilqiegħda f'terminal qed tipprova ttajpja karattri f'editur u jkollok tistenna aktar minn 10 sekondi minħabba li xi kompitu ieħor kien qed jieħu s-CPU. Mhuwiex pjaċevoli ħafna.
Allura qed niffaċċjaw problema oħra - kif nistgħu nibnu scheduler li huwa sensittiv għall-ħin tar-rispons?
Round Robin
Ġie żviluppat algoritmu biex issolvi din il-problema Round Robin (RR). L-idea bażika hija pjuttost sempliċi: minflok inħaddmu l-kompiti sakemm jitlestew, aħna se nħaddmu l-kompitu għal ċertu perjodu ta 'żmien (imsejjaħ time slice) u mbagħad naqilbu għal kompitu ieħor mill-kju. L-algoritmu jirrepeti x-xogħol tiegħu sakemm jitlestew il-kompiti kollha. F'dan il-każ, il-ħin tat-tħaddim tal-programm għandu jkun multiplu tal-ħin li warajh it-tajmer jinterrompi l-proċess. Pereżempju, jekk timer jinterrompi proċess kull x=10ms, allura d-daqs tat-tieqa tal-eżekuzzjoni tal-proċess għandu jkun multiplu ta '10 u jkun 10,20 jew x*10.
Ejja nħarsu lejn eżempju: il-kompiti ABC jaslu fl-istess ħin fis-sistema u kull wieħed minnhom irid jaħdem għal 5 sekondi. L-algoritmu SJF se jlesti kull kompitu qabel ma jibda ieħor. B'kuntrast, l-algoritmu RR b'tieqa ta' tnedija = 1s se jgħaddi mill-kompiti kif ġej (Fig. 4.3):
(SJF Għal darb'oħra (Ħażin għall-Ħin ta' Rispons)
(Round Robin (Tajjeb Għall-Ħin ta' Rispons)
Il-ħin medju tar-rispons għall-algoritmu RR huwa (0+1+2)/3=1, filwaqt li għall-SJF (0+5+10)/3=5.
Huwa loġiku li wieħed jassumi li t-tieqa tal-ħin hija parametru importanti ħafna għall-RR; iktar ma tkun iżgħar, iktar ikun għoli l-ħin tar-rispons. Madankollu, m'għandekx tagħmilha żgħira wisq, peress li l-ħin tal-bidla tal-kuntest għandu wkoll rwol fil-prestazzjoni ġenerali. Għalhekk, l-għażla tal-ħin tat-tieqa tal-eżekuzzjoni hija stabbilita mill-perit tal-OS u tiddependi fuq il-kompiti li huma ppjanati li jiġu esegwiti fiha. Il-kuntest tal-bdil mhuwiex l-unika operazzjoni tas-servizz li taħli l-ħin - il-programm li jaħdem jopera fuq ħafna affarijiet oħra, pereżempju, diversi caches, u ma 'kull swiċċ huwa meħtieġ li jiġi ffrankat u restawrat dan l-ambjent, li jista' wkoll jieħu ħafna ħin.
RR huwa Scheduler kbir jekk konna nitkellmu biss dwar il-metrika tal-ħin tar-rispons. Imma kif se jġib ruħu l-metrika tal-ħin tat-tibdil tal-kompitu b'dan l-algoritmu? Ikkunsidra l-eżempju ta 'hawn fuq, meta l-ħin operattiv ta' A, B, C = 5s u jasal fl-istess ħin. It-Task A se jispiċċa f'13, B f'14, C f'15s u l-ħin medju ta' tibdil se jkun 14s. Għalhekk, RR huwa l-agħar algoritmu għall-metrika tal-fatturat.
F'termini aktar ġenerali, kwalunkwe algoritmu tat-tip RR huwa ġust; jaqsam il-ħin tas-CPU b'mod ugwali bejn il-proċessi kollha. U għalhekk, dawn il-metriċi kontinwament f'kunflitt ma 'xulxin.
Għalhekk, għandna diversi algoritmi kontrastanti u fl-istess ħin għad fadal diversi suppożizzjonijiet - li l-ħin tal-ħidma huwa magħruf u li l-kompitu juża biss is-CPU.
Taħlit ma 'I/O
L-ewwelnett, ejja neħħi l-assunzjoni 4 li l-proċess juża biss is-CPU; naturalment, dan mhux il-każ u l-proċessi jistgħu jaċċessaw tagħmir ieħor.
Fil-mument li kwalunkwe proċess jitlob operazzjoni I/O, il-proċess jidħol fl-istat imblukkat, jistenna li l-I/O jitlesta. Jekk I/O jintbagħat lill-hard drive, allura operazzjoni bħal din tista 'tieħu sa diversi ms jew itwal, u l-proċessur ikun idle f'dan il-mument. Matul dan iż-żmien, l-iskeder jista 'jokkupa l-proċessur bi kwalunkwe proċess ieħor. Id-deċiżjoni li jmiss li l-iskeder ikollu jagħmel hija meta l-proċess se jlesti l-I/O tiegħu. Meta jiġri dan, se jseħħ interruzzjoni u l-OS se jpoġġi l-proċess li sejjaħ l-I/O fl-istat lest.
Ejja nħarsu lejn eżempju ta 'diversi problemi. Kull wieħed minnhom jeħtieġ 50ms ta 'ħin CPU. Madankollu, l-ewwel wieħed se jaċċessa I/O kull 10ms (li se jiġi eżegwit ukoll kull 10ms). U l-proċess B sempliċement juża proċessur 50ms mingħajr I/O.
F'dan l-eżempju se nużaw l-iskedar STCF. Kif se jġib ruħu l-iskeder jekk jitnieda proċess bħal A fuqu? Huwa se jagħmel dan li ġej: l-ewwel se jaħdem kompletament il-proċess A, u mbagħad il-proċess B.
L-approċċ tradizzjonali biex tissolva din il-problema huwa li tiġi ttrattata kull subtask ta' 10 ms tal-proċess A bħala kompitu separat. Għalhekk, meta tibda bl-algoritmu STJF, l-għażla bejn kompitu ta '50 ms u kompitu ta' 10 ms hija ovvja. Imbagħad, meta s-subtask A jitlesta, jitniedu l-proċess B u I/O. Wara li jitlesta l-I/O, ikun soltu li jerġa' jibda l-proċess ta' 10ms A minflok il-proċess B. B'dan il-mod, huwa possibbli li tiġi implimentata koinċidenza, fejn is-CPU jintuża minn proċess ieħor waqt li l-ewwel wieħed ikun qed jistenna l- I/O. U bħala riżultat, is-sistema hija utilizzata aħjar - fil-mument meta proċessi interattivi qed jistennew I/O, proċessi oħra jistgħu jiġu eżegwiti fuq il-proċessur.
L-Oraklu m'għadux
Issa ejja nippruvaw neħilsu mis-suppożizzjoni li l-ħin tal-ħidma tal-kompitu huwa magħruf. Din hija ġeneralment l-agħar u l-aktar suppożizzjoni realistika fuq il-lista kollha. Fil-fatt, fl-OS ordinarju medju, l-OS innifsu normalment jaf ftit li xejn dwar il-ħin tal-eżekuzzjoni tal-kompiti, allura kif tista 'tibni Scheduler mingħajr ma tkun taf kemm iddum il-kompitu biex tesegwixxi? Forsi nistgħu nużaw xi prinċipji RR biex insolvu din il-problema?
Total
Ħarsa lejn l-ideat bażiċi tal-iskedar tal-kompiti u ħares lejn 2 familji ta 'schedulers. L-ewwel wieħed jibda l-iqsar kompitu l-ewwel u b’hekk iżid il-ħin tat-tibdil, filwaqt li t-tieni wieħed jitqatta’ bejn il-kompiti kollha ugwalment, u jżid il-ħin tar-rispons. Iż-żewġ algoritmi huma ħżiena fejn l-algoritmi tal-familja l-oħra huma tajbin. Ħarsa wkoll lejn kif l-użu parallel ta 'CPU u I/O jista' jtejjeb il-prestazzjoni, iżda ma solviex il-problema bil-clarvoyance tal-OS. U fil-lezzjoni li jmiss se nħarsu lejn pjanifikatur li jħares lejn il-passat immedjat u jipprova jbassar il-futur. U tissejjaħ kju ta 'rispons f'ħafna livelli.
Sors: www.habr.com