Gestió de processos

Relacionat: Sistemes operatius, Linux, Gestió de memòria, Gestió de E/S, Processos en Linux

Un dels mòduls més importants d'un sistema operatiu és la d'administrar els processos i tasques del sistema de còmput. En aquesta secció es revisaran dos temes que componen o concerneixen a aquest mòdul: la planificació del processador i els problemes de concurrència.

La multiprogramació és un dels èxits més útils dels SO. La majoria dels programes s'executen molt més ràpid del que necessita un ésser humà. Per això, un sistema operatiu multiprogramació, pot anar alternant diferents processos sense que l'usuari percebi un menor rendiment. La gestió dels processos concurrents pot efectuar-se de moltes maneres, les detallaré en aquest tema. De l'eficiència d'aquesta gestió depèn gran part del rendiment real de l'ordinador. La gestió de processos ha intercalar els temps d'execució de manera que el processador estigui el més ocupat possible i els processos tinguin temps de resposta raonables. A més, ha d'implementar una política que estableixi un repartiment equitatiu i amb prioritats de la CPU i uns mecanismes de bloqueig mutu dels processos i de comunicació entre ells.

Concepte de procés

Un procés és un programa en execució. Per a existir necessita recursos: Memòria, E/S, CPU.

Un procés té en memòria:

• Codi
• Dades (variables, globals i memòria dinàmica)
• Pila (paràmetres i variables de subrutines)

Els sistemes operatius s'engarreguen de donar recursos als processos de manera justa i maximitzant l'utilització dels recursos.

El SO ha de disposar d'informació sobre cada procés o recurs. Per això construeix unes taules amb informació sobre cada entitat que administra (memòria, dispositius, fitxers, recursos i processos)

Les taules de memòria s'encarreguen de la gestió de la memòria principal i de la virtual. Part de la memòria la reserva al SO i la resta està disponible per als processos. Les taules de memòria ha de guardar la informació següent:

• Assignació de memòria principal als processos
• Assignació de memòria secundària als processos
• Dades de protecció i d'accés a memòria compartida
• Informació per a la gestió de memòria virtual

Les taules d'entrada i eixida (E/S) són utilitzades pel sistema operatiu per administrar els dispositius i canals d'E/S. un dispositiu pot estar disponible o assignat a un procés. El SO ha de conèixer l'estat del dispositiu i la posició de memòria que s'usa com a origen o destinació de la transferència d'E/S.

Les taules d'arxiu ofereixen informació sobre la posició en memòria secundària d'arxius. El seu estat actual i altres atributs.

BCP o Bloc Control de Procés.

Per a cada procés, el SO guarda el seu estat i altres informacions que s'han de mantindre mentre no estiga en execució:

• Estat actual (preparat, en espera...)
• Registres de la CPU (contador de programa ...)
• Informació de planificador (id, prioritat...)
• Apuntadors a les zones de memòria
• Informació de comptabilitat (temps consumit...)
• Informació de E/S (dispositius que espera, fitxers)
• Altres coses

El processos els crea el sistema operatiu. Per a crear-los, el sistema crea el BCP, reserva espai en memòria per al procés i carrega del disc dur el codi i les dades. A continuació el clava en la cola de preparats. Per tant, per a crear un procés, cal fer una cridada al sistema. En els sistemes Unix es pot fer amb fork o amb exec. La diferència és que exec executa un programa indicar i fork crea un procés idèntic al pare que l'ha cridat. Els processos tenen un procés pare indicat pel PPID, mentre que el seu identificador es diu PID. Si fem pstree en un sistema Linux podem vorer gràficament l'arbre de processos.

La unitat bàsica d'utilització de la CPU es denomina com Fil. Els fils s'executen en l'entorn d'una Tasca. Un procés és una tasca amb un sol fil. Un fil pertanyent a un grup té el mateix cost de planificació que un procés, però pot ser implementat a nivell de biblioteques d'usuari o recolzats pel nucli. Els fils tenen els mateixos recursos que el procés que els conté, mentre que dos processos no tenen accés als mateixos recursos.

El sistema operatiu guarda una estructura de dades en forma de cua en la qual hi ha la llista de processos que necessiten temps de CPU. La gestió d'aquesta cua és la part més important d'aquest tema.

En Linux podem vorer part de la informació del PCB o BCP anant a /proc/<pid>/ Aquests fitxers els crea el kernel per a cada procés. Si volem interpretar-los, podem executar $ man proc [1].

Més informació: Processos en Linux

Comunicació entre processos

La comunicació entre processos, en anglès IPC (Inter-process Communication) és una funció bàsica dels sistemes operatius. Els processos poden comunicar-se entre si a través de compartir espais de memòria, ja siguin variables compartides o buffers, o a través de les eines proveïdes per les rutines d'IPC. La IPC proveeix un mecanisme que permet als processos comunicar-se i sincronitzar entre si, normalment a través d'un sistema de baix nivell de pas de missatges que ofereix la xarxa subjacent.

La comunicació pot simplement ser qüestió de deixar que un altre procés sàpiga que ha passat algun esdeveniment, o pot implicar la transferència de dades d'un procés a un altre.

senyals

El mecanisme estàndard per informar a un procés que ha produït un esdeveniment és el senyal. Es poden enviar senyals d'un procés a un altre però sense enviar informació. Els senyals no necessiten ser generades per un altre procés, també pot ser generada pel nucli.

Linux també implementa un mecanisme de semàfors. Un procés pot esperar un semàfor tan fàcilment com s'espera un senyal.

Pas de dades entre processos

El mecanisme de canonada (pipe) estàndard permet a un procés fill heretar un canal de comunicació amb el seu pare, les dades que s'escriuen en un extrem de la canonada es llegeixen en l'altre. També defineix un conjunt de serveis per a treball en xarxa que poden enviar fluxos de dades tant a processos locals com remots.

Hi ha un altre mètode que és la memòria compartida que ofereix una forma extremadament ràpida de comunicar quantitats grans o petites de dades; qualsevol dada escrit per un procés en una regió de memòria compartida pot ser llegit per qualsevol altre procés que hagi mapejat aquesta regió en el seu espai d'adreces.

Freedesktop

Per comunicació entre aplicacions gràfiques existeix D-Bus, usat per GNOME i KDE entre altres. Permet fàcilment comunicar unes aplicacions amb altres o controlar qualsevol element d'una interfície gràfica des de consola a amb un programa fet a aquest efecte.

Tabla de métodos de IPC

(Tret de la wikipedia)

Método	Provisto por (sistema operativo u otro ambiente )
Archivo	Todos los sistemas operativos.
Señal	La mayoría de los Sistemas Operativos; algunos, como Windows, solo implementan señales en las librerías de C run-time de C y actualmente no proveen soportes paro su uso como técnica de IPC.
Socket	La mayoría de los sistemas operativos.
Tubería / Pipes	Todos los sistemas POSIX.
Named pipe	Todos los sistemas POSIX.
Semáforo	Todos los sistemas POSIX.
Memoria compartida	Todos los sistemas POSIX.
Mensajes	Usado en el paradigma MPI, Java RMI, CORBA y otros.
Mapa de Memoria	Todos los sistemas POSIX. Windows también es apto para esta técnica, las APIs usadas son específicas de esta plataforma.
Cola de Mensajes	La mayoría de los Sistemas Operativos.
puertos	Algunos Sistemas Operativos.

Planificació del processador

La planificació del processador es refereix a la manera o tècniques que es fan servir per decidir quant temps d'execució i quan se li assignen a cada procés del sistema en un sistema multitasca. Òbviament, si el sistema és Monotarea no hi ha molt decidir, però en la resta dels sistemes és crucial per al bon funcionament del sistema.

Un procés es defineix com un programa en execució. Un programa pot necessitar de diversos processos per dur a terme la seva funció, però per contra, un procés tan només fa referència a un sol programa. Pensem en Word. Si enviem a imprimir alguna cosa mentre el programa s'actualitza ia més l'enviament l'ordre de guardar el document actual, Word necessitarà tres processos per dur a terme les tasques encomanades:

• El primer enviarà el document a la cua d'impressió.
• El segon manté una comunicació amb el dispositiu de xarxa pe mantenir la seva transferència.
• El tercer necessita accedir al disc dur per guardar la informació en memòria no volàtil.

És el planificador el que ordena i planifica els processos perquè realitzin de forma el més eficient possible.

Nivells de planificació

En els sistemes de planificació generalment s'identifiquen tres nivells:

• El nivell alt decideix que treballs (conjunt de processos) són candidats a convertir-se en processos competint pels recursos del sistema.
• El nivell intermedi decideix que processos es suspenen o reprenen per aconseguir certes metes de rendiment
• El nivell baix és el que decideix que procés, dels quals ja estan llestos (i que en algun moment pas pels altres dos planificadors) és a qui li toca ara estar executant-se en la unitat central de processament.

Anem a revisar principalment els planificadors de baix nivell perquè són els que finalment trien al procés en execució.

En un determinat instant el processador només està fent idealment una sola tasca. La tasca en execució té a la seva disposició tots els recursos del sistema. Per evitar que un procés obtingui durant massa temps tots els recursos deixant tot esperant la resta de processos, el planificador estableix un temps màxim de durada en el qual se li assigna l'ús del processador. Un cop finalitzat el temps el planificador col·loca el procés a la cua quedant en espera mentre se li assigna altra vegada el processador. Aquest espai de temps s'anomena quantum.

La durada del quantum presenta en si mateix un seriós problema. Perquè el procés canviï d'estat, cal emmagatzemar les variables amb què aquesta operant i la seva propi estat en memòria per a la posterior represa. Si la mida del quantum és molt petit, les tasques de guardat, càrrega d'estats i variables consumiria un temps en què el processador podria estar realitzant altres processos.

Per contra, si el quantum és molt gran, la cua de processos podria arribar dimensions considerables i determinats processos amb una prioritat alta es veurien perjudicats. L'elecció de la mida del quantum representa una decisió important en la planificació del processador.

Els estats en què es pot trobar un procés depenen del sistema operatiu que s'estigui manejant. Per simplificar l'aprenentatge de la planificació dels processos analitzarem els tres estats més importants d'un procés, la resta es desprenen de algun d'ells.

• En execució. Compta amb tots els recursos que necessita per realitzar la seva tasca i la fa mentre a planificador no l'interrompi o perdi els recursos que necessita.
• Bloquejat (en espera). El procés ha perdut algun dels recursos que li són necessaris per fer la seva tasca. Romandrà així fins que aconsegueixi de nou el recurs perdut.
• Preparat. Es troba llest per a la seva execució però no té permís del planificador. Aquest procés compta amb els recursos disponibles.

El planificador ha de canviar d'estat als processos en funció dels seus característiques, del quantum o de si té o no els recursos necessaris per a la seva execució. Es poden donar les següents transicions:

1. El procés es troba llest per a la seva execució i li toca el torn per passar al processador. En aquest moment el procés compta amb tots els recursos que necessita.

2. Quan un procés es troba en execució però perd algun dels seus recursos i no pot continuar. En aquest moment el planificador l'introduïu a estat bloquejat.

3. Quan un procés en estat bloquejat (li falta algun recurs) ha obtingut tot el que necessita per seguir amb la seva execució. El planificador l'introduïu a estat A punt.

4. Quan un procés es troba en execució i no perd cap dels seus recursos, però ha acabat el temps assignat pel planificador per utilitzar el processador. Passa l'estat A punt.

Objectius de la planificació

Una estratègia de planificació ha de buscar que els processos obtinguin els seus torns de execució apropiadament, conjuntament amb un bon rendiment i minimització de la sobrecàrrega del planificador mateix. En general, es busquen cinc objectius principals:

• Justícia o Imparcialitat: Tots els processos són tractats de la mateixa manera, i en algun moment obtenen el seu torn d'execució o intervals de temps d'execució fins a la seva terminació reeixida.
• Maximitzar la Producció: El sistema ha de finalitzar el major nombre de processos en per unitat de temps.
• Minimitzar el Temps de Resposta: Cada usuari o procés ha d'observar que el sistema els respon consistentment als seus requeriments.
• Evitar l'ajornament indefinit: Els processos han d'acabar en un termini finit de temps.
• El sistema ha de ser predictible: Davant càrregues de treball lleugeres el sistema ha respondre ràpid i amb càrregues pesades ha d'anar degradant gradualment. Un altre punt de vista d'això és que si s'executa el mateix procés en càrregues similars de tot el sistema, la resposta en tots els casos ha de ser similar.

Assignació del torn d'execució

Els algoritmes de la capa baixa per assignar el torn d'execució es descriuen a continuació:

• Per prioritat: Els processos de major prioritat s'executen primer. Si hi ha diversos processos amb la mateixa prioritat, poden executar aquests d'acord al seu ordre d'arribada o per 'round robin' (per torn en cua circular). L'avantatge d'aquest algorisme és que és flexible quant a permetre que certs processos s'executin primer i, fins i tot, per més temps. El seu desavantatge és que pot provocar ajornament indefinit en els processos de baixa prioritat. Per exemple, suposi que hi ha processos de prioritat 20 i processos de prioritat 10. Si durant tot el dia acaben processos de prioritat 20 al mateix ritme que entren altres amb aquesta prioritat, l'efecte és que els de prioritat 10 està esperant per sempre. També fa que el sistema sigui impredictible per als processos de baixa prioritat.
• El treball més curt primer: És difícil de dur a terme perquè es requereix saber o tenir una estimació de quant temps necessita el procés per acabar. Però si se sap, s'executen primer aquells treballs que necessiten menys temps i d'aquesta manera s'obté el millor temps de resposta mitjana per a tots els processos.
• El primer a arribar, primer a executar: És molt simple, els processos reben el seu torn acord arriben. L'avantatge d'aquest algorisme és que és just i no provoca ajornament indefinit. El desavantatge és que no aprofita cap característica dels processos i pot no servir per a un procés de temps real. Per exemple, el temps mitjà de resposta pot ser molt dolent comparat amb l'aconseguit pel del treball més curt primer.
• Round Robin: També anomenada per torn, consisteix a donar a cada procés un interval de temps d'execució, i cada vegada que es venç aquest interval es còpia el context del procés a un lloc segur i se li dóna el seu torn a un altre procés. Els processos estan ordenats en una cua circular. Per exemple, si hi ha tres processos, l'A, B i C, el planificador donaria els seus torns als processos en l'ordre A, B, C, A, B, C. ... L'avantatge d'aquest algorisme és seu simplicitat, és just i no provoca ajornament indefinit.
• El temps restant més curt: És semblant al del treball més curt primer, però aquí s'està calculant en tot moment quant temps li resta per acabar a tots els processos, incloent els nous, i aquell que li quedi menys temps per acabar és escollit per executar. L'avantatge és que és molt útil per a sistemes de temps compartit perquè s'acosta molt al millor temps de resposta, a més de respondre dinàmicament a la longevitat dels processos, la seva desavantatge és que provoca més sobrecàrrega perquè el algorisme és més complex.
• Per política: Una forma d'assignar el torn d'execució és per política, en la qual s'estableix algun reglament específic que el planificador ha de obeir. Per exemple, una política podria ser que tots els processos rebin el mateix temps d'ús de CPU en qualsevol moment. Això vol dir, per exemple, que si hi ha 2 processos i han rebut 20 unitats de temps cada un i en aquest moment entra un tercer procés, el planificador li donarà immediatament el torn d'execució per 20 unitats de temps. Quant tots els processos estan 'parells' en ús de CPU, se'ls aplica 'round robin'.
• Multicoles: Es poden implementar varies coles amb una política distinta cadascuna. Desprès es fa una política comú per a seleccionar a quina cola li toca.

Problemes de Concurrència

En els sistemes de temps compartit (aquells amb diversos usuaris, processos, tasques, treballs que reparteixen l'ús de CPU entre aquests) es presenten molts problemes pel fet que els processos competeixen pels recursos del sistema. Imagini que un procés està escrivint en la unitat de cinta i se li acaba el seu torn d'execució i immediatament després el procés escollit per executar comença a escriure sobre la mateixa cinta. El resultat és una cinta el contingut és un desastre de dades barrejats. Així com la cinta, hi ha una multitud de recursos l'accés ha de ser controlat per evitar els problemes de la concurrència.

Els principals problemes de concurrència es donen en els casos següents:

• Condicions de competència: ocorre quan dos o més processos accedeixen a un recurs compartit sense control, de manera que el resultat combinat d'aquest accés depèn de l'ordre d'arribada. Suposem, per exemple, que un procés necessita utilitzar la cua d'impressió. La cua d'impressió posseeix dos valors: el primer indica la posició que ocupa l'últim arxiu a imprimir i el segon el primer registre que es troba buit per contenir l'arxiu a imprimir. Un Procés A envia el document doc1.doc i l'emmagatzema en la posició Buit. El pas següent seria augmentar el valor de buit perquè apunti a un altre sector de memòria. En aquest precís moment el planificador bloqueja el procés (perquè se li ha acabat el Quantum, per exemple) i la posició buit queda apuntant a l'últim arxiu col · locat a la cua de impressió. Un altre Procés B vol també enviar un document a imprimir i per això llegeix el valor de buit. Col · loca el seu arxiu a imprimir sobreescrivint el col·locat pel Procés A. L'arxiu doc1.doc mai s'imprimirà.

• Ajornament Indefinit o Mort per Inanició: Consisteix en el fet que un o diversos processos mai rebin el suficient temps d'execució per acabar la seva tasca. Per exemple, que un procés ocupi un recurs i el marqui com 'ocupat' i que acabi sense marcar-lo com 'desocupat'. Si algun altre procés demana aquest recurs, ho veurà 'ocupat' i esperarà indefinidament a què es 'desocupi'.

• Condició d'espera Circular: Això passa quan dos o més processos formen una cadena d'espera que els involucra a tots. Per exemple, suposeu que el procés A té assignat el recurs 'cinta' i el procés B té assignat el recurs 'disc'. En aquest moment al procés A se li ocorre demanar el recurs 'Disc' i al procés B el recurs 'cinta'. Es forma una espera circular entre aquests dos processos que es pot evitar traient a la força un recurs a qualsevol dels dos processos.

Els sistemes operatius tenen diverses tècniques que permeten minimitzar aquests problemes. Algunes d'aquestes tècniques que poden usar-se són:

• Assignar recursos amb vista lineal: Això vol dir que tots els recursos estan etiquetats amb un valor diferent i els processos només poden fer peticions de recursos 'cap endavant'. És a dir, que si un procés té el recurs amb etiqueta '5 'no pot demanar recursos la etiqueta sigui inferior a '5'. Amb això s'evita la condició d'ocupar i esperar un recurs.

• Reservar tots els recursos abans d'iniciar el procés: Aquest mecanisme consisteix que el procés demani tots els recursos que necessitarà d'una vegada i el sistema se'ls facilita en la seva totalitat, de cap altra manera llança el seu execució.

• Algorisme del banquer: Aquest algorisme utilitza una taula de recursos per saber quants recursos té de tot tipus. També requereix que els processos informin del màxim de recursos per a ser utilitzades de cada tipus. Quan un procés demana un recurs, l'algorisme verifica si assignant aquest recurs encara li queda altres del mateix tipus perquè algun dels processos en el sistema encara se li pugui donar fins al seu màxim. Si la resposta és afirmativa, el sistema es diu que està en 'estat segur' i s'atorga el recurs. Si la resposta és negativa, es diu que el sistema està en estat insegur i es fa esperar a aquest procés.

Tots aquests mètodes passen per conèixer per endavant la quantitat de recursos que un procés va a necessitar durant la seva execució. Això només passa en molt poques ocasions, de manera que l'ús d'aquestes tècniques es fa de manera poc eficient. Encara que sembli un contrasentit, de vegades la millor manera d'actuar contra una situació de les esmentades anteriorment és no fer res. Aquesta és una de les tècniques que utilitza el sistema operatiu Unix, lliure de tot dubte d'eficiència.

Multiprocessadors

Un ordinador amb molts processadors no només ha de tenir un maquinari preparat perquè diversos processadors puguin treballar al mateix temps. Sinó que ha de comptar amb un SO capaç de gestionar de manera eficient els processos i repartir la càrrega entre els processadors. A més, si un processador falla, ha de poder redistribuir la càrrega entre la resta.

És molt difícil programar pensant en processos paral·lels. Es poden crear fils, però el nivell de paral·lelisme en els programes no s'acosta al desitjable per a un bon rendiment amb un ordinador multiprocessador. Per tant, és tasca del SO, del compilador i del maquinari repartir la feina de la manera més eficient possible.

A més, els costos de planificació afecten el rendiment i el rendiment dels busos pot ser menor en haver més components.

La forma de construir un ordinador multiprocessador pot ser de 3 maneres:

• Feblement acoblats: Cada processador té la seva memòria i E/S.
• Especialitzats: un processador actua de mestre i els especialitzats li ofereixen diferents serveis.
• Fortament acoblats en què tots els processadors comparteixen la memòria i la E/S i es controlen mitjançant el SO. És la forma més complicada d'implementar, però la que proporciona un major rendiment, major fiabilitat i explota realment les possibilitats d'un ordinador multiprocessador.

El problema es presenta quan dos processos que s'executen independentment en dos processadors han d'accedir al mateix espai de memòria. D'acord amb com es soluciona aquest problema podem dividir les arquitectures en dos blocs:

• NUMA: on cada procés té accés i control exclusiu d'una part de la memòria
• SMP: On tots els processos comparteixen la mateixa memòria.

Enllaços

http://jvns.ca/blog/2013/11/29/what-happens-when-you-run-a-unix-program/

http://es.wikipedia.org/wiki/Multitarea_apropiativa

http://elpuig.xeill.net/Members/vcarceler/c1/didactica/apuntes/ud3/na7