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 =)
Planificació: cua de comentaris multinivell
En aquesta conferència, parlarem dels problemes del desenvolupament d'un dels enfocaments més famosos
planificació, que s'anomena Cua de comentaris multinivell (MLFQ). El planificador MLFQ va ser descrit per primera vegada l'any 1962 per Fernando J. Corbató en un sistema anomenat
Sistema de temps compartit compatible (CTSS). Aquestes obres (incloses les obres posteriors
Multics) van ser nominats posteriorment per als premis Turing. El planificador era
posteriorment va millorar i va adquirir l'aspecte que ja es pot trobar
alguns sistemes moderns.
L'algorisme MLFQ intenta resoldre 2 problemes fonamentals de superposició.
Primer, intenta optimitzar el temps de resposta, que, com hem comentat a la conferència anterior, s'optimitza pel mètode d'inici de la cua més
tasques curtes. Tanmateix, el sistema operatiu no sap quant de temps durarà aquest o aquell procés, i això
coneixements necessaris per al funcionament dels algorismes SJF, STCF. En segon lloc, MLFQ ho intenta
fer que el sistema respongui per als usuaris (per exemple, per a aquells que s'asseuen i
mirar la pantalla esperant que la tasca s'acabi) i així reduir el temps
resposta. Malauradament, algorismes com RR redueixen el temps de resposta, però
tenen un efecte dolent en la mètrica del temps de resposta. D'aquí el nostre problema: Com dissenyar
planificador que complirà els nostres requisits i que al mateix temps no coneixerà res
la naturalesa del procés, en general? Com pot el planificador aprendre les característiques de les tasques,
que llança i així prendre millors decisions de programació?
L'essència del problema: com planificar la configuració de les tasques sense un coneixement perfecte?
Com dissenyar un planificador que minimitzi simultàniament el temps de resposta
per a tasques interactives i al mateix temps minimitza el temps de resposta sense saber-ho
coneixement del temps d'execució de les tasques?
Nota: aprenentatge d'esdeveniments anteriors
La cua MLFQ és un excel·lent exemple d'un sistema que s'entrena
esdeveniments passats per predir el futur. Aquests enfocaments són sovint
es troba al sistema operatiu (i moltes altres branques de la informàtica, incloses les branques
prediccions de maquinari i algorismes de memòria cau). Caminada semblant
es desencadenen quan les tasques tenen fases de comportament i, per tant, són previsibles.
Tanmateix, cal anar amb compte amb aquesta tècnica, perquè les prediccions són molt fàcils.
pot resultar equivocat i portar el sistema a prendre decisions pitjors que
seria sense coneixements.
MLFQ: Regles bàsiques
Vegem les regles bàsiques de l'algorisme MLFQ. I encara que implementacions d'aquest algorisme
n'hi ha diversos, els enfocaments bàsics són semblants.
En la implementació que tindrem en compte, MLFQ en tindrà diverses
cues separades, cadascuna de les quals tindrà una prioritat diferent. En qualsevol moment,
la tasca preparada per a l'execució es troba a la mateixa cua. MLFQ utilitza prioritats,
per decidir quina tasca s'ha d'executar, és a dir. tasca amb més alt
prioritat (una tasca de la cua amb la prioritat més alta) es llançarà en primer lloc
cua.
Per descomptat, hi pot haver més d'una tasca en una cua concreta, per tant
així que tindran la mateixa prioritat. En aquest cas, s'utilitzarà el mecanisme
RR per programar una execució entre aquestes tasques.
Així arribem a dues regles bàsiques per a MLFQ:
- Regla 1: si prioritat (A) > Prioritat (B), la tasca A s'executarà (B no)
- Regla 2: si prioritat(A) = Prioritat(B), A&B s'inicien amb RR
A partir de l'anterior, els elements clau per planificar MLFQ
són prioritats. En lloc de donar una prioritat fixa a cadascun
tasca, MLFQ canvia la seva prioritat en funció del comportament observat.
Per exemple, si una tasca es tanca constantment a la CPU mentre s'espera l'entrada del teclat,
MLFQ mantindrà alta la prioritat del procés perquè és així
El procés interactiu hauria de funcionar. Si, per contra, la tasca és constant i
és intensiu de CPU durant un llarg període, MLFQ el rebaixarà
una prioritat. Així, MLFQ estudiarà el comportament dels processos en el moment en què s'executen.
i utilitzar comportaments.
Dibuixem un exemple de com podrien ser les cues en algun moment
temps i després obteniu alguna cosa com això:
En aquest esquema, 2 processos A i B es troben a la cua amb la prioritat més alta. Procés
C es troba en algun lloc al mig i el procés D es troba al final de la cua. Segons l'anterior
Segons les descripcions de l'algoritme MLFQ, el planificador executarà tasques només amb el més alt
prioritat segons RR, i les tasques C, D estaran sense feina.
Naturalment, una instantània estàtica no donarà una imatge completa de com funciona MLFQ.
És important entendre exactament com canvia la imatge amb el temps.
Intent 1: Com canviar la prioritat
En aquest punt, heu de decidir com canviarà MLFQ el nivell de prioritat
tasques (i, per tant, la posició de la tasca a la cua) a mesura que avança al llarg del seu cicle de vida. Per
això és necessari per tenir en compte el flux de treball: una certa quantitat
tasques interactives amb temps d'execució curts (i, per tant, llançaments freqüents
CPU) i diverses tasques llargues que utilitzen la CPU tot el seu temps de treball, mentre
el temps de resposta per a aquestes tasques no és important. I així pots fer el primer intent
implementeu l'algorisme MLFQ amb les regles següents:
- Regla 3: quan una tasca entra al sistema, es col·loca a la cua amb la més alta
- prioritat.
- Regla 4a: si una tasca utilitza tota la seva finestra de temps, aleshores
- es rebaixa la prioritat.
- Regla 4b: si una tasca allibera la CPU abans que caduqui la seva finestra de temps, aleshores
- continua amb la mateixa prioritat.
Exemple 1: tasca única de llarga durada
Com es pot veure en aquest exemple, la tasca d'admissió s'estableix amb la més alta
prioritat. Després d'un període de temps de 10 ms, el procés es rebaixa amb prioritat.
planificador. Després de la següent finestra de temps, la tasca finalment es rebaixa a
la prioritat més baixa del sistema, on es manté.
Exemple 2: va recollir una tasca breu
Ara vegem un exemple de com MLFQ intentarà apropar-se a SJF. En aquest
exemple, dues tasques: A, que és una tasca de llarga durada constantment
ocupant CPU i B, que és una tasca interactiva curta. Suposem
que A ja feia temps que funcionava quan va arribar la tasca B.
Aquest gràfic mostra els resultats de l'escenari. La tasca A, com qualsevol tasca,
utilitzar la CPU estava a la part inferior. La tasca B arribarà a l'hora T=100 i arribarà
col·locats a la cua de màxima prioritat. Com que el temps d'execució és curt,
es completarà abans d'arribar a l'última cua.
A partir d'aquest exemple, s'ha d'entendre l'objectiu principal de l'algorisme: ja que l'algorisme no ho fa
sap si una tasca és llarga o curta, llavors en primer lloc assumeix que la tasca
curt i li dóna la màxima prioritat. Si realment és una tasca curta, aleshores
es completarà ràpidament, en cas contrari, si és una tasca llarga, es mourà lentament
la prioritat baixa i aviat demostrarà que realment és una tasca llarga que no ho és
requereix una resposta.
Exemple 3: Què passa amb l'E/S?
Ara mirem un exemple d'E/S. Tal com s'indica a la regla 4b,
si un procés allibera el processador sense haver utilitzat completament el seu temps de processador,
llavors es manté al mateix nivell de prioritat. La intenció d'aquesta regla és bastant senzilla.
- si el treball interactiu realitza molta E/S, per exemple, esperant
des de les pulsacions de tecles o del ratolí de l'usuari, aquesta tasca alliberarà el processador
abans de la finestra assignada. No ens agradaria ometre una tasca tan prioritària,
i així es mantindrà al mateix nivell.
Aquest exemple mostra com funcionaria l'algorisme amb aquests processos: la tasca interactiva B, que només necessita la CPU durant 1 ms abans d'executar-se.
Procés d'E/S i treball A de llarga durada, que passa tot el seu temps utilitzant la CPU.
MLFQ manté el procés B amb la màxima prioritat a mesura que continua
allibera la CPU. Si B és una tasca interactiva, llavors l'algorisme en aquest cas ha arribat
el seu propòsit és llançar tasques interactives ràpidament.
Problemes amb l'algorisme MLFQ actual
En els exemples anteriors, hem creat una versió bàsica de MLFQ. I sembla que ell
fa la seva feina bé i de manera justa, distribuint el temps de la CPU de manera justa
tasques llargues i permetre tasques curtes o tasques de gran accés
a E/S per processar ràpidament. Malauradament, aquest enfocament conté diversos
problemes greus.
Primer, el problema de la fam: si el sistema tindrà molts interactius
tasques, consumiran tot el temps de la CPU i, per tant, ni un sol llarg
la tasca no tindrà l'oportunitat de ser executada (estan morint de gana).
En segon lloc, els usuaris intel·ligents podrien escriure els seus programes de manera que
enganyar el planificador. L'engany rau a fer alguna cosa per forçar
planificador per donar al procés més temps de CPU. L'algoritme que
descrit anteriorment és bastant vulnerable a aquests atacs: abans que la finestra de temps sigui pràcticament
després, heu de realitzar una operació d'E/S (per a alguns, no importa quin fitxer)
i així alliberar la CPU. Aquest comportament us permetrà mantenir-vos en el mateix
la cua en si i de nou obteniu un percentatge més gran de temps de CPU. Si ho fas
això és correcte (per exemple, executa el 99% del temps de la finestra abans d'alliberar la CPU),
aquesta tasca pot simplement monopolitzar el processador.
Finalment, un programa pot canviar el seu comportament al llarg del temps. Aquelles tasques
que utilitzava la CPU pot esdevenir interactiu. En el nostre exemple, semblant
les tasques no rebran el tractament adequat per part del planificador, com ho farien altres
(original) tasques interactives.
Pregunta per a l'audiència: quins atacs al programador es podrien dur a terme al món modern?
Intent 2: augmentar la prioritat
Intentem canviar les regles i a veure si podem evitar problemes
la fam. Què podem fer per garantir-ho
Les tasques de la CPU tindran el seu temps (encara que no siguin llargues).
Com a solució senzilla al problema, podeu suggerir periòdicament
augmentar la prioritat de totes aquestes tasques al sistema. Hi ha moltes maneres
per aconseguir-ho, intentem implementar una cosa senzilla com a exemple: traduir
totes les tasques alhora a la màxima prioritat, d'aquí la nova regla:
- Regla5: Després d'un període S determinat, moveu totes les tasques del sistema a la cua més alta.
La nostra nova regla resol dos problemes alhora. En primer lloc, els processos
garantit no morir de gana: les tasques de la cua més alta es compartiran
temps del processador segons l'algorisme RR i, per tant, rebran tots els processos
temps del processador. En segon lloc, si algun procés que s'utilitzava anteriorment
només el processador esdevé interactiu, romandrà a la cua amb el més alt
prioritat després de rebre un augment únic de prioritat a la més alta.
Considereu un exemple. En aquest escenari, considereu un únic procés que utilitza
CPU i dos processos curts i interactius. A l'esquerra de la figura, la figura mostra el comportament sense impuls de prioritat i, per tant, la tasca de llarga durada comença a morir de fam després que arribin dues tasques interactives al sistema. A la figura de la dreta, cada 50 ms es realitza un augment de prioritat i així tots els processos estan garantits per rebre temps de processador i s'iniciaran periòdicament. 50 ms en aquest cas es pren com a exemple, en realitat aquest nombre és una mica més alt.
Òbviament, sumant el temps d'augment periòdic que comporta S
pregunta lògica: quin valor s'ha d'establir? Un dels més merescuts
els enginyers de sistemes John Ousterhout van anomenar aquestes quantitats en sistemes com voo-doo
constant, ja que d'alguna manera requerien màgia negra per al correcte
exposició. I, per desgràcia, S té aquest sabor. Si també estableixes el valor
grans - les tasques llargues començaran a morir de fam. I si configureu el valor massa baix,
les tasques interactives no rebran el temps de CPU adequat.
Intent 3: Millor comptabilitat
Ara tenim un problema més per resoldre: com no
permetre enganyar el nostre planificador? Els culpables d'aquesta possibilitat són
regles 4a, 4b que permeten que un treball mantingui la seva prioritat alliberant el processador
abans que venci el temps assignat. Com fer-hi front?
La solució en aquest cas es pot considerar una millor comptabilitat del temps de CPU en cadascun
Nivell MLFQ. En lloc d'oblidar el temps que va utilitzar el programa
processador durant el període assignat, s'ha de tenir en compte i desar. Després
el procés ha esgotat el temps assignat, s'hauria de baixar al següent
nivell de prioritat. Ara no importa com utilitzarà el procés el seu temps, com
calculant constantment al processador o com un conjunt de trucades. Així,
La regla 4 s'ha de reescriure de la següent manera:
- Regla4: Després que una tasca hagi esgotat el temps assignat a la cua actual (independentment de quantes vegades hagi alliberat la CPU), la prioritat d'aquesta tasca es redueix (es mou per la cua).
Vegem un exemple:
»
La figura mostra què passa si intenteu enganyar el planificador
si fos amb les regles anteriors 4a, 4b seria el resultat a l'esquerra. Amb nou
la regla és que el resultat és a la dreta. Abans de la protecció, qualsevol procés podria trucar a l'E/S abans de la finalització i
dominen així la CPU, després d'habilitar la protecció, independentment del comportament
I/O, encara es mourà cap avall a la cua i, per tant, no podrà fer-ho de manera deshonesta
assumir els recursos de la CPU.
Millorar MLFQ i altres problemes
Amb les millores anteriors apareixen nous problemes: un dels principals
Preguntes: com parametritzar aquest programador? Aquells. Quant hauria de ser
cues? Quina ha de ser la mida de la finestra del programa dins de la cua? Com
Sovint s'hauria d'augmentar la prioritat del programa per evitar la fam i
tenir en compte el canvi en el comportament del programa? Per a aquestes preguntes, no és senzill
resposta i només experiments amb càrregues i configuració posterior
planificador pot conduir a un equilibri satisfactori.
Per exemple, la majoria de les implementacions de MLFQ us permeten assignar diferents
franges horàries per a diferents cues. Les cues d'alta prioritat solen ser
es prescriuen intervals curts. Aquestes cues consisteixen en tasques interactives,
canviar entre els quals és bastant sensible i hauria de prendre 10 o menys
Senyora. En canvi, les cues de baixa prioritat consisteixen en tasques de llarga durada que s'utilitzen
CPU. I en aquest cas, els intervals de temps llargs encaixen molt bé (100 ms).
En aquest exemple, hi ha 2 tasques que han funcionat a la cua d'alta prioritat 20
ms dividit en finestres de 10 ms. 40 ms a la cua mitjana (finestra de 20 ms) i a la cua de baixa prioritat
La finestra de temps de la cua es va convertir en 40 ms on les tasques van completar el seu treball.
La implementació del sistema operatiu Solaris de MLFQ és una classe de programadors de temps compartit.
El planificador proporcionarà un conjunt de taules que defineixen exactament com hauria de ser
la prioritat del procés canvia al llarg de la seva vida, quina hauria de ser la mida
finestra que s'ha d'assignar i amb quina freqüència s'han de plantejar les prioritats de les tasques. Administrador
El sistema pot interactuar amb aquesta taula i fer que el planificador es comporti
diferent. Per defecte, aquesta taula té 60 cues amb un augment gradual
mida de la finestra de 20 ms (prioritat alta) a diversos centenars de ms (prioritat més baixa) i
també amb l'impuls de totes les tasques una vegada per segon.
Altres planificadors de MLFQ no utilitzen una taula ni cap tipus específic
regles que es descriuen en aquesta conferència, al contrari, calculen les prioritats utilitzant
fórmules matemàtiques. Per exemple, el planificador de FreeBSD utilitza una fórmula per
calculant la prioritat de la tasca actual en funció de la quantitat del procés
utilitzava la CPU. A més, l'ús de la CPU es podreix amb el temps i, per tant
Per tant, l'augment de prioritat és una mica diferent del descrit anteriorment. Això és cert
anomenats algorismes de decadència. A partir de la versió 7.1, FreeBSD utilitza el planificador ULE.
Finalment, molts planificadors tenen altres característiques. Per exemple, alguns
els planificadors reserven nivells superiors per al funcionament del sistema operatiu i, per tant
Per tant, cap procés d'usuari pot obtenir la màxima prioritat
sistema. Alguns sistemes us permeten donar consells per ajudar
el planificador pot establir les prioritats correctament. Per exemple, utilitzant l'ordre agradable
pots augmentar o disminuir la prioritat d'una tasca i així augmentar o
reduir les possibilitats del programa de temps de CPU.
MLFQ: resum
Hem descrit un enfocament de planificació anomenat MLFQ. El seu nom
conclou en el principi de funcionament: té diverses cues i utilitza comentaris
per prioritzar una tasca.
La forma final de les normes serà la següent:
- Regla1: Si prioritat (A) > Prioritat (B), s'iniciarà la tasca A (B no)
- Regla2: Si prioritat(A) = Prioritat(B), A&B s'inicien amb RR
- Regla3: Quan una tasca entra al sistema, es col·loca a la cua de prioritat més alta.
- Regla4: Després que una tasca hagi esgotat el temps assignat a la cua actual (independentment de quantes vegades hagi alliberat la CPU), la prioritat d'aquesta tasca es redueix (es mou per la cua).
- Regla5: Després d'un període S determinat, moveu totes les tasques del sistema a la cua més alta.
MLFQ és interessant per la següent raó - en lloc de requerir coneixements sobre
naturalesa de la tasca per endavant, l'algoritme estudia el comportament passat de la tasca i els conjunts
prioritats en conseqüència. Per tant, intenta seure en dues cadires alhora: aconseguir el rendiment per a tasques petites (SJF, STCF) i executar-ne honestament les llargues,
Feines de càrrega de CPU. Per tant, molts sistemes, inclòs BSD i els seus derivats,
Solaris, Windows i Mac utilitzen algun tipus d'algorisme com a programador
MLFQ com a referència.
Materials addicionals:
- (informàtica)
Font: www.habr.com