Tema 3. Gestió CPU / processos

3.1 Processos. Tasques i fils.

Un procés és bàsicament un entorn format per tots els recursos necessaris per a poder executar programes. Des del punt de vista del SO un procés és un objecte més que s’ha de gestionar i al qual s’ha de donar servei.
Per a gestionar els processos i donar-los serveis, el sistema operatiu ha de proporcionar eines o ha de portar a terme accions que permetin aconseguir els objectius següents:
  • Crear i eliminar processos.
  • Garantir que els processos disposin dels recursos necessaris per a avançar en la seva execució.
  • Actuar en casos excepcionals durant l’execució del procés
  • Proporcionar els mecanismes necessaris perquè el processos es comuniquin, ja sigui per intercanviar informació, ja sigui per sincronitzar-se durant l’execució.
  • Mantenir estadístiques sobre el funcionament dels processos.
  • Temporalitzar l’execució d’un procés: fer que un procés s’executi cada cert temps.
  • Altres serveis miscel·lanis.
En aquest apartat fem una introducció a la gestió que el SO porta a terme sobre els processos. Veurem les estructures de dades que representen internament un procés i com diversos processos poden executar-se concurrentment en un únic
processador.   

3.2 Propietats del processos

Quan s'executen diferents processos de forma concurrent a un sistema cada un d'ells necessita que el propi sistema li assigni diferents recursos. El sistema operatiu necessitarà guardar informació de cada procés per poder sincronitzar-los i assignar els recursos de forme coordinada. Per a guardar aquesta innformació del procés s'utilitza una estructura de dades.
L'estructura de dades que emmagatzema aquesta informació reb el nom de Bloc de Control del procés (PCB process control block) i conté per a cada procés, com a mínim, la següent informació:
  • Identificador del procés. És el codi únic que identifica de manera biunívoca cada un dels diferents processos que hi ha en execució en el sistema i que, per tant, ha de ser distingit de manera individual. Aquest identificador normalment és numèric.
  • L’estat del procés. Aquest camp indica l’estat del procés en el moment actual, dins d’unes possibilitats determinades (run, ready, wait...). L’estat d’un procés i el seu significat es descriuen més endavant.
  • El comptador del programa. Aquest camp és fonamental perquè ‘assenyala’ la instrucció que estava a punt de ser executada just en el moment que es produeix una interrupció. Quan el procés pot continuar, ho fa exactament en aquest punt.
  • Els registres interns de la CPU. Són registres utilitzats per tots els processos. Per tant, després d’una interrupció no n’hi ha prou de continuar l’execució del procés en el punt on es va deixar, sinó que també s’ha de trobar un entorn idèntic al que tenia abans de produir-se la interrupció. Per a tenir aquesta possibilitat també hem de guardar el valor dels registres.
  • L’estat de la memòria. És difícil generalitzar sobre el que necessita cada sistema operatiu per a tenir tota la Informació relativa a la memòria de cada procés, però podem donar algunes idees, com ara la quantitat de memòria assignada, el lloc on es troba, el tipus de gestió que se’n fa, les proteccions de cada part, les comparticions, etc.
  • Comptabilitat i estadístiques. Els sistema operatiu obté per a cada procés una sèrie d’informació relativa al comportament de cada usuari. Aquesta informació té un gran valor per als administradors de sistema, però no en té gaire per als usuaris o els programadors.
  • L’estat dels dispositius d’entrada/sortida. Els dispositius d’entrada/sortida assignats, les sol·licituds pendents, els fitxers oberts, etc. també formen part de l’entorn d’execució.
  • El domini de protecció. Aquest camp conté informació dels dominis als quals pertany el procés i dels drets que tenen associats.
  • La planificació de la CPU. En aquest camp s’agrupa informació relativa a la manera com el procés accedeix al processador en concurrència amb els altres processos.
  • Altres informacions. Cada sistema operatiu manté altres informacions particulars en funció de diferents aspectes, com ara el fabricant del sistema operatiu, el tipus d’orientació (treball en temps real, les comunicacions, etc) i també del tipus d’explotació (ús privat, ús públic,etc).
D’acord amb els PCB, el sistema gestiona l’execució dels programes continguts a la memòria dels processos. En els subapartats següents analitzem els principals components d’aquesta gestió tenint en compte les necessitats d’un sistema multiprogramat.

3.3. L’execució concurrent

A la figura 1 podem veure l’execució concurrent d’un conjunt de processos (P1,P2 i P3) sobre un sistema monoprocessador multiprogramat. En funció de l’escala de temps amb què examinem l’evolució dels processos en el sistema en podem tenir visions diferents.
1) La primera escala de temps, que es veu a la figura 1a, correspon al punt de vista de l’usuari. Aquí l’execució dels tres processos sembla que s’efectua en paral·lel, aparentment cada procés fa servir sempre el processador. Aquesta és la impressió que es vol donar en els sistemes multiusuari: que cada usuari té una bona interactivitat amb el sistema i que l’usuari es troba sol treballant davant la màquina. Però en realitat en un sistema que treballa en modalitat de temps compartit això no és cert.
2) Si mirem el comportament dels processos a una escala més petita de temps veiem que hi ha una multiplexació del processador en el temps (vegeu la figura 1 apartat b). Ampliant la figura 1a (fent un zoom), podem observar que no hi ha una execució real en paral·lel dels processos; només un d’ells està en execució real. Per a aconseguir l’efecte d’execució concurrent es fa una commutació entre els processos que es reparteixen el temps del processador. Aquestes commutacions s’anomenen canvi de context.
3) Finalment, ampliant més la imatge, és a dir, a una escala de temps encara més petita, podem veure el detall de les transicions entre  rocessos o canvi de context (vegeu la figura 1c). Podem observar que ha d’aparèixer un fragment de codi nou per a gestionar la interrupció que provoca el canvi. Per a fer-ho, s’han de dur a terme les operacions següents:
  • Guardar l’estat del processador tal com el tenia el procés P1 en l’instant que s’ha produït la interrupció sobre el seu PCB.
  • Localitzar el PCB del procés P2.
  • Restaurar l’estat del processador guardat en el segon PCB.
L’estat del processador en un instant concret és format pels valors continguts en cadascun dels registres en llenguatge màquina, pel punter a la pila, pel comptador de programa i, en general, per tota la informació que configura un procés.
Els valors concrets d’aquest conjunt de registres en un instant de la vida d’un procés s’anomena context del procés.

3.4. Estats dels processos i transicions entre estats

En un sistema multiprogramat, amb molts processos i un processador, com el que hem descrit en el subapartat anterior, en un moment determinat només hi pot haver un procés en execució, la resta de processos poden estar esperant el seu torn per a accedir al processador o poden estar esperant la finalització d’una operació d’entrada/sortida. Aquesta diversitat de situacions es pot representar amb un diagrama d’estats com el de la figura, on els nodes representen els estats en què els processos poden estar, i els arcs són les accions que fan que un procés canviï d’estat. Ready significa: “Ho tinc tot a punt i estic preparat per a rebre la CPU i treballar”.

 
Quan el sistema acaba de crear un procés, aquest procés es troba en l’estat inicial (1), l’estat ready. El sistema pot sortir d’aquest estat per les dues causes següents:
  • Un esdeveniment extern al propi procés, que pot ser degut a l’acció d’un altre procés mitjançant un senyal de programari, provoca la finalització del procés (2).
  • El gestor li assigna la CPU (3) i el procés comença a executar les seves instruccions i passa a l’estat run.
De l’estat run es pot sortir pels tres motius següents:
  • El procés executa la darrera línia de codi i acaba (4).
  • El procés ha d’esperar un esdeveniment extern. L’exemple més normal és quan es demana una operació d’entrada/sortida (5) i el procés espera que sigui servida*. En aquest cas, el procés passa a l’estat wait i s’espera fins que la petició s’hagi servit.
  • Quan el sistema operatiu treballa en la modalitat de temps compartit, si el procés supera la quota màxima de temps d’ús de CPU que té assignada (6), deixa el processador i torna a l’estat ready.
Quan un procés surt de l’estat run per a passar a ready o wait, es produeix un canvi de context.
Finalment, els processos tenen dues destinacions possibles quan surten de l’estat wait:
  • Una cap a l’estat ready, quan finalitza l’operació per la qual esperaven (7). Dit d’una altra manera, quan el procés té prou informació i pot continuar. Per exemple, si el procés estava pendent d’una operació d’entrada/sortida i ja ha arribat la informació esperada perquè l’usuari ha polsat una tecla.
  • Una altra, cap a la finalització del procés (8), deguda a un esdeveniment extern al propi procés, com succeïa en l’estat ready.
Per a saber què fa cadascun dels processos i així poder controlar els seus recursos, el sistema operatiu manté unes cues de processos en funció del seu estat. Així, el sistema té una cua de processos preparats (ready) i una de processos en estat d’espera (wait). No podem parlar d’una cua de processos en execució, ja que en entorns monoprocessador només hi ha un procés en execució. D’aquesta manera el procediment del nucli del SO encarregat de la planificació del processador
pot examinar la llista de processos preparats a fi d’assignar el processador al procés que més convingui.

3.5. Creació i destrucció de processos. El cicle de vida d'un procés.

Com hem anat veient en aquesta assignatura, els processos són un més dels objectes que gestiona el SO. A diferència de molts altres objectes, els processos són dinàmics i solen tenir un temps de vida limitat*. En aquest apartat analitzarem el cicle de vida dels processos i les operacions que s’hi relacionen.
Les diferents etapes de la vida d’un procés són les següents:
  • Creació, naixement o inici. En aquesta etapa s’assignen i s’inicialitzen els recursos necessaris per a crear un procés nou.
  • Desenvolupament. Un cop creats, els processos evolucionen a partir de l’execució del programa que contenen. Aquest desenvolupament pot portar-los a modificar els recursos amb els quals s’han constituït inicialment.
  • Destrucció, mort o finalització. Un cop acabada la feina que especifica l’aplicació que s’executa en el marc del procés, el SO destrueix el procés i allibera els recursos que se li havien assignat.
En aquest apartat analitzarem el cicle de vida del procés. Per a fer-ho estudiarem en primer lloc els processos de creació i destrucció d’un procés, a continuació les relacions que hi ha entre aquestes dues accions i, finalment, veurem algunes de les modificacions que es poden fer sobre l’entorn que constitueix un procés durant la seva existència.

3.5.1. La creació i la destrucció de processos.

Els processos són elements dinàmics que es creen, operen durant un interval de temps i es destrueixen. El sistema operatiu és l’encarregat de proporcionar el conjunt de crides necessàries per a portar a terme totes aquestes accions. En aquest subapartat analitzarem les operacions de creació i destrucció de processos.

Creació de processos

La creació d’un procés nou és el resultat de l’execució d’una crida al sistema del tipus crear_procés, que és invocada, com totes les crides, per un procés ja existent.
L’execució de la crida crear_procés comporta la creació d’un entorn d’execució que conté els elements següents:
  • La memòria on residiran el programa, el codi i les dades amb què operarà el  procés.
  • El punt d’entrada des d’on s’executarà el programa que contingui la memòria.
  • L’entorn d’entrada/sortida amb el qual el procés es comunicarà amb l’exterior.
  • Els atributs relacionats amb els dominis de protecció amb els quals el sistema operatiu verificarà la legalitat de les operacions que vulgui efectuar.

Cadascun d’aquest elements de l’entorn s’haurà d’especificar al sistema perquè aquest pugui crear un procés nou. L’especificació d’aquests elements es pot fer de les dues maneres següents:
a) De manera explícita, amb els paràmetres de la crida al sistema que crea el procés.
b) De manera implícita, fent que el sistema prengui uns valors per defecte.
Normalment, els sistemes combinen les dues alternatives: obliguen a especificar alguns d’aquest elements mitjançant els paràmetres de la crida, i en deixen uns altres amb valors per defecte.
Un altre aspecte que cal tenir en compte és la relació que hi ha entre l’entorn des d’on s’executa la crida al sistema que donarà lloc al nou procés i l’entorn nou que es crearà. Per a veure aquesta relació més clarament partim del fet, ja esmentat, que els processos són creats pel sistema operatiu a petició d’altres processos.
Aquesta situació fa que els processos es puguin mirar des del punt de vista de la descendència, en què els processos tenen relacions de parentiu com ara la de pare i fill. En aquest àmbit podem parlar dels conceptes d’herència entre processos i de sincronització entre processos pare i fill.
Un cop creat el procés, el sistema li dóna un nom (generalment un nombre dins d’un espai lineal) amb el qual podrà ser referenciat en accions de control i manipulació, tant des d’altres processos com directament des del SO. Aquest nom ha de ser únic per a cada procés, no tan sols durant la vida del procés al qual fa referència, sinó durant tota la vida del sistema.    
La finalitat del fet de tenir un nom únic per a cada procés durant tota la vida del  sistema és evitar confusions i mals funcionaments del SO a causa de la reutilització de noms. Per exemple, imaginem dos processos (procés A i procés B) que col·laboren i se sincronitzen mitjançant senyals gràcies al fet que coneixen els seus identificadors. Si un (el procés B) acaba de manera imprevista i el seu identificador és reutilitzat per a crear un altre procés, aleshores el procés A s’està sincronitzant amb un procés que té un identificador B, que no és el procés amb el
qual s’havia previst una comunicació. El resultat pot ser que cap dels dos processos no funcioni correctament o, el que és més problemàtic, que s’hagi obert un forat en la protecció del sistema.
Així doncs, una possible estructura de la crida crear_procés podria ser:
Id_procés = crear_procés(entorn_mem,nom_prog,punt_execució,entorn_E/S,entorn_domini).
Amb aquesta solució, si el punt d’execució del procés fill fos una còpia del del pare, tal com ja hem comentat, el valor de retorn de crear_procés hauria de ser diferent en funció de si el procés és el pare o el fill.

Destrucció de processos.

La destrucció d’un procés comporta la destrucció de l’entorn que el cons    titueix i l’alliberament dels recursos que tenia assignats.
La destrucció d’un procés per part del sistema pot ser conseqüència d’alguna de les situacions següents:
a) L’execució de la crida al sistema destruir_procés específica per a aquest motiu. En la majoria de sistemes aquesta crida provoca la destrucció del procés que la invoca, i no pot ser dirigida a d’altres processos.
b) El mal funcionament del procés destruït. Si el sistema detecta que un procés no funciona correctament i efectua operacions no permeses, el destrueix. Aquestes operacions solen estar associades a les excepcions provocades per accions com ara: accedir a posicions de memòria que no es tenen assignades, executar instruccions privilegiades o efectuar operacions aritmètiques incorrectes com, per exemple, una divisió per zero, etc.
c) L’efecte lateral de l’execució, per part d’un altre procés, d’una crida al sistema diferent de la crida destruir_procés, que provoca una excepció sobre el procés que és destruït.
Ara ens centrarem exclusivament en el primer punt: la destrucció d’un procés com a resultat de l’execució de la crida al sistema destruir_procés. Les dues últimes situacions les veurem més endavant.
Tot procés, quan finalitza sense incidents l’execució del programa que emmagatzema, ha de ser destruït. Aquesta destrucció només pot ser el resultat de l’execució de la crida destruir_procés. Per tal que es porti a terme la destrucció, el compilador insereix automàticament, de manera transparent per al programador, la crida destruir_procés al sistema com a última instrucció del programa. De manera addicional, el programador pot incloure invocacions a la crida destruir_procés per a provocar la finalització del procés en situacions controlades pel programa.
La crida per a destruir un procés podria ser, doncs, la següent:
Estat = destruir_procés(id_procés).

3.6. Planificador

Tot sistema operatiu gestiona els diferents processos de l'ordinador. En un instant determinat, a l'ordinador poden existir diversos processos a punt per a la seva execució. Però només un d'ells es podrà executar (un a cada processador). És per això que una part del sistema operatiu ha de gestionar, d'una manera equitativa, quin procés s'ha d'executar a cada moment. El component del sistema operatiu que s'encarrega d'assignar els recursos de manera que s'aconseguiexin complir els objectius especificats és el planificador (Scheduller).
Tota la informació dels processos, que necessita el planificador, es troba a les diferents llistes de BCP's: Execució (Run), Espera(Wait) i A punt(Ready).
Existeixen 3 tipus de planificador, en funció del termini temporal de la planificació:
  • Planificadors a curt plaç
  • Planificadors a mig plaç
  • Planificadors a llarg plaç
Al sistema operatiu poden coexistir els tres planificadors, encara que nosaltres considerarem el planificador com un sol component del sistema. La tasca principal del planificador serà determinar quin o quins processos han de passar a estat d'execució (Run) d'entre tots els processos candidats que es trobin a punt (Ready).
El planificador és particular de cada sistema operatiu, però en linies generals el funcionament és idèntic als diferents sistemes.

La selecció del següent procés a executar no es realitza de manera aleatòria, sino que el planificador decidirà quin procés canvia el seu estat a Execució seguint el seu algorisme de planificació. L'elecció de l'algorisme de planificació dependrà de les característiques desitjades del sistema i dels criteris decidits al moment del seu disseny.

La majora de sistemes operatius i processadors actuals són multifil (Multihebra o HT HyperThreading). La gestió de les diferents fils es realitza de la mateixa manera que hem comentat fins ara, amb la diferència que la gestió es realitza a nivell de fils enlloc de fer-ho a nivell de procés.

3.6.1. Sincronització entre processos

La sincronització entre els processos ha de permetre que els processos s'executin seguint l'ordre corresponent i sense interferències entre ells.  
Es parla de fase o secció crítica quan dos o més processos comparteixen dades (variables a memòria) que han de consultar i/o modificar en diferents instants de temps. 
Per exemple: si un procés modifica una variable de memòria i a continuació canvia el seu estat a actiu (Ready). El següent procés actiu modifica el valor de la mateixa variable. Quan el procés inicial torna a executar-se el valor de la variable no és el valor esperat pel procés. Això pot crear conflictes entre els processos i errors durant l'execució dels programes.

El sistema operatiu ha de sincronitzar els processos per a que s'executin a l'ordre previst.

3.6.2. Algorismes de planificació


3.6.2.1 FCFS / FIFO

FCFS (First Come First Serve), FIFO (First In First Out) són els diferents noms de l'algorisme on el primer que arriba és el primer que es despatxa. Com la cua de la gent que espera el seu torn a la caixa del supermercat o la cua del que espera el seu torn al banc.

Per a cada procés el sistema operatiu ha de coneixer el seu cicle d'arribada i la quantitat de cicles de UCP que necessita. 

   Cicle d'arribda Cicles d'UCP 
Procés A 0 4
Procés B 2 3
Procés C  4 4
Procés D  6 2

A l'esquema d'execució següent es pot veure com s'executarien els processos amb l'algorisme de planificació FIFO. Cada fila representa un procés diferent i cada columna els diferents cicles d'execució.

 Cicles ->  0 1 2 10  11  12  13  14  15       
 Procés A  A  X  F                            
 Procés B      A      I  X                      
 Procés C          A        X  F              
 Procés D              A            I          
A -> cicle d'arribada, I -> cicle d'inici, X-> cicle d'execució normal F -> cicle de finalització

Comentaris
És important destacar que un procés no es pot iniciar mai al mateix cicle d'arribada, ja que no es pot executar fins que el planificador decideixi quin dels processos en estat a punt (Ready) passarà a executar-se.
Els processos A i B comencen l'execució al cicle següent de l'arribada, cosa que no passa als processos C i D, que han d'esperar la finalització dels processos anteriors per poder començar la seva execució. C i D ténen cicles d'espera que no fan res fins que el planificador els assigna temps de UCP.
Els cicles d'Inici i Fi de cada procés només s'han marcat per recordar que durant aquests cicles el sistema operatiu ha de realitzar tasques addicionals.

A la taula següent es pot veure el cicle d'inici i fi de cada procés.
   Cicle d'arribda Cicles d'UCP   Cicle
Inici
 Cicle Fi
Procés A 0 4  1  4
Procés B 2 3  5  7
Procés C  4 4  8  11
Procés D  6 2  12  13
El temps d'execució d'un procés vendrà donat per la diferència del seu cicle de fi i el seu cicle d'arribada. Es pot veure fàcilment que no sempre coincideix amb el temps d'UCP. I el temps que el procés no s'executa però es troba a la llista de processos a punt (ready) reb el nom de temps d'espera.
Temps d'execució = Cicle de Fi - Cicle d'arribada
Temps d'espera = Temps d'execució - Cicles d'UCP

3.6.2.2 Roda (Round Robin)

A l'algorisme de roda o Round Robin el sistema assigna de forma rotatòria un temps d'execució a cada procés. Aquest temps d'execució és el mateix per a cada procés i s'assigna de manera seqüencial. Aquest temps reb el nom de quantum.
L'ordre d'assignació del temps es realitza mitjançant una cua FIFO, és a dir, segons l'ordre d'arribada.

Exemple:

   Cicle d'arribda Cicles d'UCP 
Procés A 0 4
Procés B 2 3
Procés C  4 4
Procés D 6 2

En el moment que hi hagi dos o més processos a punt per a la seva execució, el sistema operatiu assignarà el temps de CPU seguint una qua segons l'ordre d'arribada. En aquest cas l'ordre serà: A - B - C - D

 Cicles ->  0 1 2 10  11  12  13  14  15       
 Procés A  A  X    X        F                    
 Procés B      A  I    X        F                  
 Procés C          A    I        X    X          
 Procés D              A                    
A -> cicle d'arribada, I -> cicle d'inici, X-> cicle d'execució normal F -> cicle de finalització

Observacions:
L'ordre de finalització no té perquè coincidir amb l'ordre d'arribada.
En cas que hi hagi molts processos, en proporció els procesos curts tindran major temps d'espera, però si s'analitza en conjunt l'espera estarà repartida entre tots els processos.

   Cicle d'arribda Cicles d'UCP   Cicle
Inici
 Cicle Fi
Procés A 0 4  1  8
Procés B 2 3  3  9
Procés C  4 4  6  13
Procés D  6 2  7  11


3.6.2.3 Prioritat

Amb l'algorisme de prioritat el sistema operatiu assignarà el temps de processador segons la prioritat de cada procés. Quan un procés té assignat temps de CPU només alliberarà aquesta en cas que hi hagi a la llista de processos pendents un altre procés de major prioritat.

Normalment la prioritat ve indicada per un número i quan més petit el número major és la prioritat.

En el cas de 2 processos amb la mateixa prioritat el sistema haurà de decidir quin d'ells canviarà l'estat a execució. Això es pot fer tant utilitzant algorisme FIFO com Round Robin, dependrà del disseny del sistema operatiu.

El sistema operatiu assignarà la prioritat en el moment de creació del procés. Hi haurà casos en que el procés no canviarà de prioritat durant la seva execució, parlarem de prioritat estàtica, en canvi hi haurà altres casos on el procés podrà variar la seva prioritat al llarg de la seva execució, en aquests casos parlarem de prioritat dinàmica.


Exemple:

Ara afegim la columna de prioritat, que l'algorisme utilitzarà per decidir quin és el procés que ha de canviar el seu estat a execució.

   Cicle d'arribda Cicles d'UCP   Prioritat
Procés A 0 4  3
Procés B 2 3  4
Procés C  4 4  1
Procés D 6 2  2

Al següent esquema podem veure l'execució dels processos amb l'algorisme de prioritat.

 Cicles ->  0 1 2 10  11  12  13  14  15       
 Procés A  A  X  X  F                            
 Procés B      A    
           I  X  F          
 Procés C          A X  F                    
 Procés D              A
   F                
A -> cicle d'arribada, I -> cicle d'inici, X-> cicle d'execució normal F -> cicle de finalització

Observacions:
Es pot veure que un procés de més prioritat no pot ser interromput per un altre de menor prioritat. Cosa que si pot passar en cas contrari, encara que no aparegui en aquest cas.
Els processos de baixa prioritat poden allargar molt la seva execució si hi ha processos de més prioritat.

   Cicle d'arribda Cicles d'UCP   Cicle
Inici
 Cicle Fi
Procés A 0 4  1  4
Procés B 2 3  11  13
Procés C  4 4  5  8
Procés D  6 2  9  10


3.6.2.4 Altres: LIFO (Last In First Out), SJF (Shortest Job First)

Existeixen més algorismes de planificació. I normalment els sitemes operatius utilitzen una combinació de més d'un algorisme.

Exercici: Identificar quin o quins algorismes de planificació utilizen Windows i Linux.

ċ
Guillem Mateu,
11 nov. 2008 2:19
Comments