Introducció als sistemes operatius
Hola Habr! M'agradaria cridar la vostra atenció una sèrie d'articles-traduccions d'una literatura interessant al meu entendre: OSTEP. Aquest material tracta bastant profundament el treball dels sistemes operatius semblants a Unix, és a dir, el treball amb processos, diversos programadors, memòria i altres components similars que conformen un sistema operatiu modern. Podeu veure l'original de tots els materials aquí . Si us plau, tingueu en compte que la traducció es va fer de manera poc professional (molt lliure), però espero haver conservat el sentit general.
Els treballs de laboratori sobre aquest tema es poden trobar aquí:
Altres parts:
També pots consultar el meu canal a =)
Introducció a Scheduler
L'essència del problema: Com desenvolupar una política de planificador
Com s'han de dissenyar els marcs polítics del programador subjacent? Quins han de ser els supòsits clau? Quines mètriques són importants? Quines tècniques bàsiques es van utilitzar en els primers sistemes informàtics?
Supòsits de càrrega de treball
Abans de parlar de possibles polítiques, primer fem algunes digressions simplificadores sobre els processos que s'executen al sistema, que s'anomenen col·lectivament càrrega de treball. La definició de la càrrega de treball és una part fonamental de la creació de polítiques, i com més sàpigues sobre la càrrega de treball, millor serà la política que pots escriure.
Fem les següents suposicions sobre els processos que s'executen al sistema, de vegades també anomenats llocs de treball (tasques). Gairebé tots aquests supòsits no són realistes, però són necessaris per al desenvolupament del pensament.
- Cada tasca s'executa durant la mateixa quantitat de temps,
- Totes les tasques s'estableixen simultàniament,
- La tasca assignada funciona fins a la seva finalització,
- Totes les tasques només utilitzen CPU,
- Es coneix el temps d'execució de cada tasca.
Mètriques del programador
A més d'algunes hipòtesis sobre la càrrega, cal una altra eina per comparar diferents polítiques de programació: mètriques del planificador. Una mètrica és només una mesura d'alguna cosa. Hi ha una sèrie de mètriques que es poden utilitzar per comparar els programadors.
Per exemple, utilitzarem una mètrica anomenada temps de resposta (temps de resposta). El temps d'execució de la tasca es defineix com la diferència entre el temps de finalització de la tasca i el temps d'arribada de la tasca al sistema.
Tturnaround=Tcompletació−Arribada
Com que vam suposar que totes les tasques arribaven al mateix temps, aleshores Ta=0 i per tant Tt=Tc. Aquest valor canviarà naturalment quan canviem els supòsits anteriors.
Una altra mètrica - justícia (equitat, honestedat). La productivitat i l'equitat són sovint característiques oposades en la planificació. Per exemple, el planificador pot optimitzar el rendiment, però a costa d'esperar que s'executin altres tasques, reduint així l'equitat.
PRIMER EN ENTRAR PRIMER OUT (FIFO)
L'algorisme més bàsic que podem implementar s'anomena FIFO o primer arribat (entrada), primer servit (sortida). Aquest algorisme té diversos avantatges: és molt fàcil d'implementar i s'ajusta a tots els nostres supòsits i fa la feina força bé.
Vegem un exemple senzill. Suposem que es van establir 3 tasques simultàniament. Però suposem que la tasca A ha arribat una mica abans que totes les altres, de manera que apareixerà a la llista d'execució abans que les altres, igual que B en relació amb C. Suposem que cadascuna d'elles s'executarà durant 10 segons. Quin serà el temps mitjà per completar aquestes tasques en aquest cas?
Comptant els valors - 10 + 20 + 30 i dividint per 3, obtenim el temps mitjà d'execució del programa igual a 20 segons.
Ara intentem canviar les nostres suposicions. En particular, el supòsit 1 i, per tant, ja no assumirem que cada tasca triga el mateix temps a executar-se. Com actuarà FIFO aquesta vegada?
Com a resultat, els diferents temps d'execució de tasques tenen un impacte extremadament negatiu en la productivitat de l'algorisme FIFO. Suposem que la tasca A trigarà 100 segons a completar-se, mentre que B i C encara trigaran 10 segons cadascuna.
Com es pot veure a la figura, el temps mitjà del sistema serà (100+110+120)/3=110. Aquest efecte s'anomena efecte comboi, quan alguns consumidors a curt termini d'un recurs fan cua després d'un gran consumidor. És com la fila a la botiga de queviures quan hi ha un client davant teu amb un carro ple. La millor solució al problema és intentar canviar la caixa registradora o relaxar-se i respirar profundament.
El treball més curt primer
És possible resoldre d'alguna manera una situació similar amb processos pesats? Certament. Es diu un altre tipus de planificacióEl treball més curt primer (SJF). El seu algorisme també és força primitiu: com el seu nom indica, les tasques més curtes es llançaran primer, una darrere l'altra.
En aquest exemple, el resultat d'executar els mateixos processos serà una millora en el temps mitjà de resposta del programa i serà igual a 50 en lloc de 110, que és gairebé 2 vegades millor.
Així, per la suposició donada que totes les tasques arriben al mateix temps, l'algoritme SJF sembla ser l'algoritme més òptim. Tanmateix, les nostres suposicions encara no semblen realistes. Aquesta vegada canviem el supòsit 2 i aquesta vegada imaginem que les tasques poden estar presents en qualsevol moment, i no totes alhora. A quins problemes pot comportar això?
Imaginem que la tasca A (100c) arriba primer i comença a executar-se. A t=10, arriben les tasques B i C, cadascuna de les quals trigarà 10 segons. Per tant, el temps d'execució mitjà és (100+(110-10)+(120-10))3 = 103. Què podria fer el planificador per millorar-ho?
Temps més curt per a la finalització primer (STCF)
Per tal de millorar la situació, ometem el supòsit 3 que el programa s'inicia i s'executa fins a la seva finalització. A més, necessitarem suport de maquinari i, com podeu suposar, utilitzarem temporitzador per interrompre una tasca en curs i canvi de context. Així, el planificador pot fer alguna cosa en el moment en què arriben les tasques B, C: deixar d'executar la tasca A i posar les tasques B i C en processament i, després de completar-les, continuar executant el procés A. Aquest programador s'anomena STCFo Primer treball preventiu.
El resultat d'aquest planificador serà el resultat següent: ((120-0)+(20-10)+(30-10))/3=50. Així, aquest programador esdevé encara més òptim per a les nostres tasques.
Temps de resposta mètric
Així, si sabem el temps d'execució de les tasques i que aquestes tasques només utilitzen CPU, STCF serà la millor solució. I una vegada en els primers temps, aquests algorismes van funcionar força bé. Tanmateix, ara l'usuari passa la major part del seu temps al terminal i espera una experiència interactiva productiva. Així va néixer una nova mètrica: temps de resposta (resposta).
El temps de resposta es calcula de la següent manera:
Tresponse=Tfirstrun−Tarrival
Així, per a l'exemple anterior, el temps de resposta serà: A=0, B=0, C=10 (abg=3,33).
I resulta que l'algoritme STCF no és tan bo en una situació en què arriben 3 tasques al mateix temps: s'haurà d'esperar fins que les petites tasques es completin completament. Per tant, l'algoritme és bo per a la mètrica del temps de resposta, però dolent per a la mètrica d'interactivitat. Imagineu-vos si estigueu asseguts a un terminal intentant escriure caràcters en un editor i hagueu d'esperar més de 10 segons perquè alguna altra tasca ocupava la CPU. No és gaire agradable.
Per tant, ens enfrontem a un altre problema: com podem crear un programador sensible al temps de resposta?
Round Robin
Es va desenvolupar un algorisme per resoldre aquest problema Round Robin (RR). La idea bàsica és bastant senzilla: en comptes d'executar les tasques fins que s'acabin, executarem la tasca durant un període de temps determinat (anomenat interval de temps) i després canviarem a una altra tasca de la cua. L'algorisme repeteix el seu treball fins que s'han completat totes les tasques. En aquest cas, el temps d'execució del programa ha de ser un múltiple del temps després del qual el temporitzador interromprà el procés. Per exemple, si un temporitzador interromp un procés cada x=10ms, la mida de la finestra d'execució del procés hauria de ser múltiple de 10 i ser 10,20 o x*10.
Vegem-ne un exemple: les tasques ABC arriben simultàniament al sistema i cadascuna d'elles vol executar-se durant 5 segons. L'algoritme SJF completarà cada tasca abans d'iniciar-ne una altra. En canvi, l'algoritme RR amb una finestra de llançament = 1s seguirà les tasques de la següent manera (Fig. 4.3):
(SJF de nou (mal per al temps de resposta)
(Round Robin (Bo per al temps de resposta)
El temps de resposta mitjà per a l'algorisme RR és (0+1+2)/3=1, mentre que per a l'SJF (0+5+10)/3=5.
És lògic suposar que la finestra de temps és un paràmetre molt important per a RR; com més petit sigui, més gran serà el temps de resposta. Tanmateix, no hauríeu de fer-lo massa petit, ja que el temps de canvi de context també jugarà un paper en el rendiment general. Així, l'elecció del temps de la finestra d'execució la defineix l'arquitecte del sistema operatiu i depèn de les tasques que es planifiquen per executar-hi. El canvi de context no és l'única operació de servei que fa perdre el temps: el programa en execució funciona en moltes altres coses, per exemple, diverses cachés, i amb cada commutador cal desar i restaurar aquest entorn, cosa que també pot prendre moltes temps.
RR és un programador fantàstic si parléssim només de la mètrica del temps de resposta. Però, com es comportarà la mètrica del temps de lliurament de la tasca amb aquest algorisme? Considereu l'exemple anterior, quan el temps de funcionament de A, B, C = 5 s i arriben al mateix temps. La tasca A acabarà a les 13, la B a les 14, la C a les 15 s i el temps mitjà de resposta serà de 14 s. Així, RR és el pitjor algorisme per a la mètrica de rotació.
En termes més generals, qualsevol algorisme de tipus RR és just; divideix el temps de la CPU per igual entre tots els processos. I, per tant, aquestes mètriques entren constantment en conflicte.
Així, tenim diversos algorismes contrastats i, al mateix temps, encara queden diverses suposicions: que es coneix el temps de la tasca i que la tasca només utilitza la CPU.
Barreja amb E/S
En primer lloc, eliminem la suposició 4 que el procés només utilitza la CPU; naturalment, aquest no és el cas i els processos poden accedir a altres equips.
En el moment en què qualsevol procés sol·licita una operació d'E/S, el procés entra a l'estat bloquejat, esperant que finalitzi l'E/S. Si s'envia E/S al disc dur, aquesta operació pot trigar uns quants ms o més, i el processador estarà inactiu en aquest moment. Durant aquest temps, el planificador pot ocupar el processador amb qualsevol altre procés. La següent decisió que haurà de prendre el planificador és quan el procés completarà la seva E/S. Quan això succeeix, es produirà una interrupció i el sistema operatiu posarà el procés que va cridar l'E/S a l'estat llest.
Vegem un exemple de diversos problemes. Cadascun d'ells requereix 50 ms de temps de CPU. Tanmateix, el primer accedirà a E/S cada 10 ms (que també s'executarà cada 10 ms). I el procés B simplement utilitza un processador de 50 ms sense E/S.
En aquest exemple farem servir el programador STCF. Com es comportarà el planificador si s'hi posa un procés com A? Farà el següent: primer treballarà completament el procés A i després el procés B.
L'enfocament tradicional per resoldre aquest problema és tractar cada subtasca de 10 ms del procés A com una tasca independent. Així, quan es comença amb l'algorisme STJF, l'elecció entre una tasca de 50 ms i una de 10 ms és òbvia. Aleshores, quan s'hagi completat la subtasca A, es llançaran el procés B i l'E/S. Un cop finalitzada l'E/S, serà habitual tornar a iniciar el procés A de 10 ms en lloc del procés B. D'aquesta manera, és possible implementar la superposició, on la CPU és utilitzada per un altre procés mentre el primer està esperant el E/S. I com a resultat, el sistema s'utilitza millor: en el moment en què els processos interactius estan esperant E/S, es poden executar altres processos al processador.
L'Oracle ja no existeix
Ara intentem desfer-nos de la suposició que es coneix el temps d'execució de la tasca. Aquesta és, en general, la pitjor i més irreal suposició de tota la llista. De fet, en el sistema operatiu ordinari mitjà, el sistema operatiu en si sol sap molt poc sobre el temps d'execució de les tasques, així que com es pot crear un programador sense saber quant de temps trigarà a executar-se la tasca? Potser podríem utilitzar alguns principis de RR per resoldre aquest problema?
Total
Vam analitzar les idees bàsiques de la programació de tasques i vam analitzar 2 famílies de planificadors. El primer comença la tasca més curta primer i augmenta així el temps de resposta, mentre que el segon es divideix entre totes les tasques per igual, augmentant el temps de resposta. Tots dos algorismes són dolents quan els algorismes de l'altra família són bons. També vam analitzar com l'ús paral·lel de CPU i E/S pot millorar el rendiment, però no vam resoldre el problema amb la clarividència del sistema operatiu. I a la lliçó següent veurem un planificador que mira el passat immediat i intenta predir el futur. I s'anomena cua de comentaris multinivell.
Font: www.habr.com