Introducere în sistemele de operare
Bună, Habr! Aș dori să vă prezint atenției o serie de articole-traduceri ale unei literaturi care este interesantă în opinia mea - OSTEP. Acest material examinează destul de profund munca sistemelor de operare asemănătoare Unix, și anume lucrul cu procese, diverse programatoare, memorie și alte componente similare care alcătuiesc un sistem de operare modern. Puteți vedea originalul tuturor materialelor aici . Vă rugăm să rețineți că traducerea a fost făcută neprofesionist (destul de liber), dar sper că am păstrat sensul general.
Lucrările de laborator pe acest subiect pot fi găsite aici:
Alte părți:
Puteți verifica și canalul meu la =)
Introducere în Scheduler
Esența problemei: Cum se dezvoltă o politică de planificare
Cum ar trebui concepute cadrele de politică de bază ale planificatorului? Care ar trebui să fie ipotezele cheie? Ce valori sunt importante? Ce tehnici de bază au fost folosite în sistemele de calcul timpurii?
Ipoteze de sarcină de muncă
Înainte de a discuta posibilele politici, să facem mai întâi câteva digresiuni simplificatoare despre procesele care rulează în sistem, care sunt numite colectiv volumul de muncă. Definirea volumului de lucru este o parte esențială a politicilor de construire și, cu cât cunoașteți mai multe despre volumul de muncă, cu atât mai bună este politica pe care o puteți scrie.
Să facem următoarele ipoteze despre procesele care rulează în sistem, uneori numite și de locuri de muncă (sarcini). Aproape toate aceste presupuneri nu sunt realiste, dar sunt necesare pentru dezvoltarea gândirii.
- Fiecare sarcină rulează pentru aceeași perioadă de timp,
- Toate sarcinile sunt setate simultan,
- Sarcina atribuită funcționează până la finalizarea ei,
- Toate sarcinile folosesc numai CPU,
- Timpul de rulare al fiecărei sarcini este cunoscut.
Valorile programatorului
Pe lângă unele ipoteze despre încărcare, este nevoie de un alt instrument pentru compararea diferitelor politici de programare: valorile planificatorului. O metrică este doar o măsură a ceva. Există o serie de valori care pot fi utilizate pentru a compara programatorii.
De exemplu, vom folosi o metrică numită timp de răspuns (timp de răspuns). Timpul de finalizare a sarcinii este definit ca diferența dintre timpul de finalizare a sarcinii și timpul de sosire a sarcinii în sistem.
Tturnaround=Tfinalizare−Sosire
Deoarece am presupus că toate sarcinile au sosit în același timp, atunci Ta=0 și astfel Tt=Tc. Această valoare se va schimba în mod natural atunci când schimbăm ipotezele de mai sus.
O altă măsurătoare - cinste (corectitudine, onestitate). Productivitatea și corectitudinea sunt adesea caracteristici opuse în planificare. De exemplu, planificatorul poate optimiza performanța, dar cu prețul așteptării rulării altor sarcini, reducând astfel corectitudinea.
PRIMUL INTRAT, PRIMUL IEȘIT (FIFO)
Cel mai de bază algoritm pe care îl putem implementa se numește FIFO sau primul venit (intrat), primul servit (ieșit). Acest algoritm are mai multe avantaje: este foarte ușor de implementat și se potrivește tuturor ipotezelor noastre și face treaba destul de bine.
Să ne uităm la un exemplu simplu. Să presupunem că au fost stabilite 3 sarcini simultan. Dar să presupunem că sarcina A a sosit puțin mai devreme decât toate celelalte, așa că va apărea în lista de execuții mai devreme decât celelalte, la fel ca B în raport cu C. Să presupunem că fiecare dintre ele va fi executată timp de 10 secunde. Care va fi timpul mediu pentru finalizarea acestor sarcini în acest caz?
Numărând valorile - 10+20+30 și împărțind la 3, obținem timpul mediu de execuție a programului egal cu 20 de secunde.
Acum să încercăm să ne schimbăm presupunerile. În special, ipoteza 1 și, prin urmare, nu vom mai presupune că fiecare sarcină durează același timp pentru a fi executată. Cum va evolua FIFO de data aceasta?
După cum se dovedește, diferiți timpi de execuție a sarcinilor au un impact extrem de negativ asupra productivității algoritmului FIFO. Să presupunem că sarcina A va dura 100 de secunde pentru a fi finalizată, în timp ce B și C vor dura 10 secunde fiecare.
După cum se poate observa din figură, timpul mediu pentru sistem va fi (100+110+120)/3=110. Acest efect se numește efect de convoi, când unii consumatori pe termen scurt ai unei resurse vor sta la coadă după un consumator greu. Este ca la coada de la magazin când există un client în fața ta cu un cărucior plin. Cea mai bună soluție la problemă este să încerci să schimbi casa de marcat sau să te relaxezi și să respiri adânc.
Cel mai scurt job mai întâi
Este posibil să se rezolve cumva o situație similară cu procese grele? Cu siguranță. Un alt tip de planificare se numeșteCel mai scurt job mai întâi (SJF). Algoritmul său este, de asemenea, destul de primitiv - după cum sugerează și numele, cele mai scurte sarcini vor fi lansate mai întâi, una după alta.
În acest exemplu, rezultatul rulării acelorași procese va fi o îmbunătățire a timpului mediu de executie al programului și va fi egal cu 50 în loc de 110, ceea ce este de aproape 2 ori mai bun.
Astfel, pentru ipoteza dată că toate sarcinile ajung în același timp, algoritmul SJF pare a fi cel mai optim algoritm. Cu toate acestea, presupunerile noastre încă nu par realiste. De data aceasta schimbăm ipoteza 2 și de data aceasta ne imaginăm că sarcinile pot fi prezente în orice moment și nu toate în același timp. La ce probleme poate duce asta?
Să ne imaginăm că sarcina A (100c) ajunge prima și începe să fie executată. La t=10, sosesc sarcinile B și C, fiecare dintre ele va dura 10 secunde. Deci, timpul mediu de execuție este (100+(110-10)+(120-10))3 = 103. Ce ar putea face planificatorul pentru a îmbunătăți acest lucru?
Cel mai scurt timp până la finalizare primul (STCF)
Pentru a îmbunătăți situația, omitem ipoteza 3 că programul este lansat și rulează până la finalizare. În plus, vom avea nevoie de suport hardware și, după cum ați putea ghici, vom folosi timer pentru a întrerupe o sarcină care rulează și schimbarea contextului. Astfel, planificatorul poate face ceva în momentul în care sosesc sarcinile B, C - oprește executarea sarcinii A și pune sarcinile B și C în procesare și, după finalizarea lor, continuă executarea procesului A. Un astfel de planificator se numește STCFsau În primul rând, munca preventivă.
Rezultatul acestui planificator va fi următorul rezultat: ((120-0)+(20-10)+(30-10))/3=50. Astfel, un astfel de planificator devine și mai optim pentru sarcinile noastre.
Timp de răspuns metric
Astfel, dacă știm timpul de rulare al sarcinilor și că aceste sarcini folosesc doar CPU, STCF va fi cea mai bună soluție. Și odată în timpurile timpurii, acești algoritmi au funcționat destul de bine. Cu toate acestea, utilizatorul își petrece acum cea mai mare parte a timpului la terminal și se așteaptă la o experiență interactivă productivă. Astfel s-a născut o nouă metrică - timp de raspuns (raspuns).
Timpul de răspuns se calculează după cum urmează:
Tresponse=Tfirstrun−Tarrival
Astfel, pentru exemplul anterior, timpul de răspuns va fi: A=0, B=0, C=10 (abg=3,33).
Și se dovedește că algoritmul STCF nu este atât de bun într-o situație în care sosesc 3 sarcini în același timp - va trebui să aștepte până când sarcinile mici sunt complet finalizate. Deci algoritmul este bun pentru metrica timpului de răspuns, dar rău pentru metrica de interactivitate. Imaginează-ți dacă stai la un terminal încercând să tastați caractere într-un editor și trebuind să așteptați mai mult de 10 secunde, deoarece o altă sarcină ocupa CPU. Nu este foarte plăcut.
Deci ne confruntăm cu o altă problemă - cum putem construi un planificator care să fie sensibil la timpul de răspuns?
Round Robin
A fost dezvoltat un algoritm pentru a rezolva această problemă Round Robin (RR). Ideea de bază este destul de simplă: în loc să rulăm sarcini până când acestea sunt finalizate, vom rula sarcina pentru o anumită perioadă de timp (numită interval de timp) și apoi vom trece la o altă sarcină din coadă. Algoritmul își repetă munca până când toate sarcinile sunt finalizate. În acest caz, timpul de rulare al programului trebuie să fie un multiplu al timpului după care temporizatorul va întrerupe procesul. De exemplu, dacă un temporizator întrerupe un proces la fiecare x=10ms, atunci dimensiunea ferestrei de execuție a procesului ar trebui să fie un multiplu de 10 și să fie 10,20 sau x*10.
Să ne uităm la un exemplu: sarcinile ABC ajung simultan în sistem și fiecare dintre ele vrea să ruleze timp de 5 secunde. Algoritmul SJF va finaliza fiecare sarcină înainte de a începe alta. În schimb, algoritmul RR cu o fereastră de lansare = 1s va parcurge sarcinile după cum urmează (Fig. 4.3):
(SJF din nou (prost pentru timpul de răspuns)
(Round Robin (bine pentru timpul de răspuns)
Timpul mediu de răspuns pentru algoritmul RR este (0+1+2)/3=1, în timp ce pentru SJF (0+5+10)/3=5.
Este logic să presupunem că fereastra de timp este un parametru foarte important pentru RR; cu cât este mai mică, cu atât timpul de răspuns este mai mare. Cu toate acestea, nu ar trebui să-l faceți prea mic, deoarece timpul de schimbare a contextului va juca, de asemenea, un rol în performanța generală. Astfel, alegerea timpului ferestrei de execuție este stabilită de arhitectul OS și depinde de sarcinile care sunt planificate a fi executate în acesta. Schimbarea contextului nu este singura operațiune de serviciu care pierde timp - programul care rulează funcționează pe o mulțime de alte lucruri, de exemplu, diverse cache-uri, iar cu fiecare comutare este necesar să salvați și să restabiliți acest mediu, ceea ce poate dura și o mulțime de timp.
RR este un planificator grozav dacă am vorbi doar despre metrica timpului de răspuns. Dar cum se va comporta metrica timpului de executie a sarcinii cu acest algoritm? Luați în considerare exemplul de mai sus, când timpul de funcționare al lui A, B, C = 5s și ajunge în același timp. Sarcina A se va încheia la 13, B la 14, C la 15 s, iar timpul mediu de răspuns va fi de 14 s. Astfel, RR este cel mai prost algoritm pentru metrica cifrei de afaceri.
În termeni mai generali, orice algoritm de tip RR este corect; împarte timpul CPU în mod egal între toate procesele. Și, astfel, aceste valori sunt în conflict constant între ele.
Astfel, avem mai mulți algoritmi contrastanți și, în același timp, au mai rămas câteva presupuneri - că timpul sarcinii este cunoscut și că sarcina folosește doar CPU-ul.
Amestecarea cu I/O
În primul rând, să eliminăm ipoteza 4 conform căreia procesul folosește doar CPU; desigur, nu este cazul și procesele pot accesa alte echipamente.
În momentul în care orice proces solicită o operație I/O, procesul intră în starea blocată, așteptând finalizarea I/O-ului. Dacă I/O este trimis pe hard disk, atunci o astfel de operație poate dura până la câțiva ms sau mai mult, iar procesorul va fi inactiv în acest moment. În acest timp, planificatorul poate ocupa procesorul cu orice alt proces. Următoarea decizie pe care programatorul va trebui să o ia este când procesul își va finaliza I/O. Când se întâmplă acest lucru, va apărea o întrerupere și sistemul de operare va pune procesul care a apelat I/O în starea de pregătire.
Să ne uităm la un exemplu de mai multe sarcini. Fiecare dintre ele necesită 50 ms de timp CPU. Totuși, primul va accesa I/O la fiecare 10ms (care va fi, de asemenea, executat la fiecare 10ms). Și procesul B folosește pur și simplu un procesor de 50 ms fără I/O.
În acest exemplu vom folosi programatorul STCF. Cum se va comporta planificatorul dacă un proces precum A este lansat pe el? El va face următoarele: mai întâi va rezolva complet procesul A și apoi procesul B.
Abordarea tradițională pentru a rezolva această problemă este de a trata fiecare subsarcină de 10 ms a procesului A ca o sarcină separată. Astfel, atunci când începem cu algoritmul STJF, alegerea între o sarcină de 50 ms și una de 10 ms este evidentă. Apoi, când subsarcina A este finalizată, procesul B și I/O vor fi lansate. După finalizarea I/O-ului, va fi obișnuit să porniți din nou procesul de 10 ms A în loc de procesul B. În acest fel, este posibilă implementarea suprapunerii, unde CPU este utilizat de un alt proces în timp ce primul așteaptă I/O. Și, ca rezultat, sistemul este mai bine utilizat - în momentul în care procesele interactive așteaptă I/O, alte procese pot fi executate pe procesor.
Oracolul nu mai există
Acum să încercăm să scăpăm de presupunerea că timpul de rulare al sarcinii este cunoscut. Aceasta este, în general, cea mai proastă și mai nerealistă presupunere din întreaga listă. De fapt, într-un sistem de operare obișnuit, sistemul de operare în sine știe de obicei foarte puțin despre timpul de execuție al sarcinilor, așa că atunci cum poți construi un planificator fără să știi cât timp va dura sarcina pentru a fi executată? Poate că am putea folosi niște principii RR pentru a rezolva această problemă?
Total
Ne-am uitat la ideile de bază ale programării sarcinilor și am analizat 2 familii de programatori. Primul începe primul sarcina cea mai scurtă și astfel crește timpul de răspuns, în timp ce al doilea este rupt între toate sarcinile în mod egal, crescând timpul de răspuns. Ambii algoritmi sunt răi în cazul în care algoritmii din cealaltă familie sunt buni. De asemenea, ne-am uitat la modul în care utilizarea paralelă a CPU și I/O poate îmbunătăți performanța, dar nu am rezolvat problema clarviziunii sistemului de operare. Și în lecția următoare ne vom uita la un planificator care se uită în trecutul imediat și încearcă să prezică viitorul. Și se numește coadă de feedback pe mai multe niveluri.
Sursa: www.habr.com