Usuari:Sergi/Temari/Tema 16 Sistemas operativos: Gestión de procesos.

De Acacha

Dreceres ràpides: navegació, cerca

Contingut

Processos

En informàtica un procés és una instància d'una aplicació que esta essent executada per una computadora. Una aplicació o programa és solament una col·leció passiva d'instruccions que no esdevenen un procés fins que el programa és executat.

Un procés és el conjunt de recursos necessari per executar un programa. Des del punt de vista del sistema operatiu és un recurs més que s'ha de 
gestionar.

Cal destacar també que una sola aplicació o programa pot arribar a executar múltiples processos al mateix temps (per exemple un servidor com Apache pot tenir múltiples processos pendents de rebre peticions de connexió).

La concurrència real de processos (diferents processos executant-se al mateix temps) pot esdevenir de 2 formes diferents:

  • Sistemes operatius multitasca: Els processos aparentment s'executen al mateix temps tot i que realment, en un instant concret de temps, només hi ha un procés que estigui utilitzant la CPU. Un ordinador amb un sol processador executa les instruccions una a una, però pot intercalar diferents processos utilitzant una multiplexació en temps (Time-sharing), procés que a certes velocitats produeix la "il·lusió" que el sistema treballa amb diferents processos al mateix temps. Aquest procés és anomenat concurrència o multiprogramació
  • Sistemes operatius multiprocés: l'única forma de tenir un sistema multiprocés real és tenir més d'una CPU. Els sistemes operatius que suporten treballar amb més d'una CPU a l'hora s'anomenen multiprocés. Aquests sistemes també permeten al mateix temps la concurrència de processos en un mateix processador.

Recursos:

Elements d'un procés

Els sistemes operatius necessiten gestionar els processos i per tant necessiten una estructura de dades per representar tota la informació relativa a un procés del sistema:

El Process Control Block (PCB) o Bloc de Control de Procés (BCP) és l'estructura de dades on s'agrupa tota la informació que necessita conèixer un sistema operatiu sobre un procés.

Cada procés té el seu propi BCP, i aquesta estructura de dades es guardada en memòria durant tot el seu cicle de vida.

La implementació exacte de cada BCP depèn de cada sistema operatiu però podem considerar que tots els sistemes tindran les següents dades o similars:

  • Identificador del procés (Process Identificator (PID) en anglès).
  • Estat del procés: hi han diferents models d'estats.
  • Comptador de Programa (PC Program Counter): Adreça de la pròxima instrucció a executar.
    • Altres registres del sistema (CPU) necessaries per als canvis de context.
  • Espai d'adreces de memòria del procés
  • Prioritat del procés (en el cas que s'utilitzi)
  • Llista de recursos assignats al procés (descriptors de fitxers, sockets oberts, etc.)
  • Estadístiques del procés.
  • Dades del propietari del procés
  • Permisos assignats.
  • Senyals pendents de ser processades.

Es tracta d'una estructura de dades que emmagatzema les metadades d'un procés necessàries per a la seva administració i com hem comentat aquestes dades poden canviar segons el sistema operatiu (per exemple hi han sistemes operatius on pugui ser interessant coneìxer les dades de quin usuari executa i quan de temps per tal de poder facturar l'ús de màquina)


Recursos:

Fils d'execució

Un fil d'execució és una característica dels sistemes operatius moderns que permet que una aplicació realitzi varies tasques de forma concurrent utilitzant fils d'execució. Els diferents fils comparteixen certs recursos com l'espai de memòria, els arxius oberts, els permisos, etc.

La tècnica de programació amb fils d'execució s'anomena Multithreading i permet simplificar el disenys d'aplicacions concurrents i millor el rendiment de la creació de processos.

Els fils d'execució que comparteixen els mateixos recursos i que son executats per una mateixa aplicació (i usuari) és el que coneixem com a procés.

Cal tenir en compte que el fet que el fils puguin accedir als recursos de la resta de fils "germans" és un problema de seguretat. Cal programar tenint en compte que l'accés a aquests recursos compartits s'haurà de protegir per tal d'evitar comportaments estranys. Pel que fa a la seguretat, tots els fills d'un procés pertanyen a una mateixa aplicació i usuari i per tant se suposa que no s'atacarà a si mateix (tot i que els errors de programació es poden propagar fàcilment)

Cada fil del procés té el seu propi comptador de programa, la seva pròpia pila d'execució i l'estat de la CPU. Un procés amb múltiples fils es considera en execució mentrestant hi ha un fill en execució. Si es finalitza un procés es finalitzen tots els seus fills.

Alguns llenguatges de programació tenen les seves pròpies llibreries per tal d'operar amb fils (Java, Delphi) i altres com C o C++ han d'utilitzar les crides de sistema que donen aquest suport.

Exemples típics de fils són:

  • Aplicacions gràfiques: Un fil s'encarrega de la GUI mentrestant un altre realitza les operacions.
  • Aplicacions client/servidor: el servidor crea un fil per tal de donar resposta a una petició d'un client. Poden haver-hi tants fills com peticions.

En sistemes Unix/Linux tenim dos tipus de llibreries per a threads (fils):

Recursos:

Fils d'execució vs processos

Diferències:

  • Els processos són independents entre ells i en canvi els fils estan relacionats i comparteixen recursos ("són germans bessons"). Quan es crea un procés fill amb fork, el fill és una còpia però és independent del pare.
  • Els canvis de context entre fils són més ràpids que els canvis de context entre processos. Els fils no necessiten crear nous espais de memòria sinó que aprofiten gran part dels ja existents dels seus germans (aproximadament és un ordre de magnitud més ràpid)
  • Els processos són inherentment més segurs que els fils
  • Un procés es pot considerar un procés MonoFil


Sistemes operatius actuals com Linux, Windows NT y OS/2 suporten fils d'execució.

Cicle de vida d'un procés.Estats

Per representar el cicle de vida d'un procés s'acostuma a utilitzar un diagrama d'estats. L'estat en que esta un procés en un instant de temps es guarda com una dada més al BCP del procés.

L'estat del procés depèn en gran part de la seva relació amb la CPU. Tots els sistemes operatius tenen un component anomenat Planificador que és l'encarregat de decidir quin procés s'executa en cada moment. També esta clar que s'haurà d'implementar una cua on emmagatzemar temporalment els processos que esta a l'espera de ser executats.

Hi han diferents models d'estats per als processos però hi han 3 que són els més utilitzats:

Diagrama de 5 estats
  • Model de dos estats: és el model més simple i només diferència entre processos en execució i processos que no s'estan executant. Aquest mòdel funciona bé quan es treballa amb una cua FIFO i una planificació Round Robin o per torn rotatori.

Cada cop que un procés canvia d'un estat d'execució (ús de CPU) a un estat de no execució (wait o ready) és produeix una operació que s'anomena canvi de context. Aquest procés commuta un procés en espera per un procés en execució.

  • Modelo de cinc estats: És el sistema més utilitzat i té en compte que realment els processos no sempre estan preparats per a ser executats. Els processos necessiten de dades per funcionar i sovint aquestes dades s'han d'obtenir de "l'exterior" a través d'operacions d'E/S. Aquestes operacions normalment són d'ordres de magnitud més lentes que la velocitat de la CPU. Els sistemes que disposen de planificació expulsiva permeten que la CPU "expulsi" un procés en execució que esta a l'espera d'una operació d'E/S i permetrà això un ús més eficient de la CPU. Aquest processos passen a una estat normalment anomenat d'espera (wait). Per tant els processos que no s'estan executant poden estar en espera (wait) o llestos (ready). A més s'afegeixen dos estats: Nou i Terminat.

Els estats Nou i Terminat són útils per a la gestió de processos.

Pel que fa a les cues d'espera i han diferents implementacions:

  • Cues FIFO (First In First Out): sistemes on no hi han prioritats
  • Diferents cues una per cada nivell de prioritat: O una sola cua on s'ordenin els elements per la seva prioritat i en cas d'empat per FIFO.
  • Una cua d'espera per cada dispositiu E/S: Aquí s'emmagatzemen els processos en espera d'operacions d'E/S.
  • Model de 7 estats: el fet d'utilitzar un estat en espera pot arribar a augmentar tant la exigència d'espai de memòria (múltiples processos a l'espera) fins al punt d'esgotar la memòria principal. La solució és utilitzar el procés d'intercanvi o swapping. Aquest procés correspon a moure un procés de la memòria principal a la memòria secundària (normalment disc). En aquest casos s'utilitza un nou esta anomenat Suspès

Els estats són per tant:

Els sistemes de multiplexació en temps es van començar a utilitzar per tal de permetre que un procés adormit (a l'espera d'E/S o d'alguna senyal) no monopolitzes l'ús de la CPU i s'optimitzes l'ús de la CPU.


Recursos:

Processos Unix/GNU/Linux

Recursos:

Jerarquia de processos en Unix

En Unix/Linux els processos només es poden executar a partir de processos ja existents fet que comporta que els processo acabin tenint una jerarquia i unes relacions pare/fill.

La crida de sistema que permet en Unix crear un nou procés és fork. Fork crea un procés fill que és una còpia exacte del procés pare i que 
s'executa en paral·lel al procés pare

Dos conceptes:

  • Herència: El procés hereta totes les propietats del pare (de fet és una còpia exacte del seu pare).
  • Sincronització entre processos pare i fill: un procés pare i el seu fill és poden comunicar utilitzar els sistemes que ofereix el sistema per a la comunicació entre processos.

Una de les formes més adequades de veure com funcionen els processos i la seves relacions és veure el funcionament de la línia de comandes de Unix (per exemple bash). En un sistema Linux amb entorn gràfic X-Windows amb Gnome podriem executar:

$ pstree
...
    ├─gnome-terminal─┬─8*[bash]
    │                ├─bash─┬─pstree
    │                │      └─sleep

Com podeu observar la terminal gràfica (aplicació gnome-terminal) és pare de 9 línies de comandes (aplicacions bash), cadascuna s'executa en un pestanya diferent. A una d'aquestes línies de comandes s'estan executant dos processos: pstree i sleep. Això o podem aconseguir executant:

$ sleep 10 &

El ampersand (&) indica que el procés s'executara en segon terme. També podem utilitzar la comanda equivalent

$ bg 


Els sistemes Unix tenen un procés que és el procés pare de tota la resta de processos. Aquest procés s'anomena init i té com identificador de procés (PID) el número 1. Aquesta jerarquia entre processos es pot observar executant la comanda pstree

$ pstree | more
init-+-NetworkManager
     |-NetworkManagerD
     |-acpid
     |-amarokapp-+-ruby

El sistema Unix va assignant el número de PID de forma incremental a mesura que s'executen els processos. La comanda ps ens mostra els processos ordenats per PID:

$ ps aux | more
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root         1  0.0  0.1   2952  1852 ?        Ss   09:07   0:01 /sbin/init

Estats i cicle de vida

Estats dels processos Unix:

  • Running: Esta utilitzant la CPU
  • Waiting: El procés esta esperant un esdeveniment o un recurs d'E/S. Linux diferencia entre dos tipus de processos en espera:
    • Waiting interruptible: Processos que poden ser interromputs per senyals
    • Waiting uninterruptible: Interrupcions de maquinari que no es poden interrompre
  • Stopped: El procés esta aturat segurament per una senyal. Per exemple un procés que esta dent depurat per un debugador.
  • Zombie: és un procés finalitzat però que encara esta la seva estructura de dades en memòria.

Del manual de ps:

D    Uninterruptible sleep (usually IO)
R    Running or runnable (on run queue)
S    Interruptible sleep (waiting for an event to complete)
T    Stopped, either by a job control signal or because it is being
     traced.
W    paging (not valid since the 2.6.xx kernel)
X    dead (should never be seen)
Z    Defunct ("zombie") process, terminated but not reaped by its
           parent.

Crides al sistema

  • Crear un procés; fork()
  • Destruir un procés: exit()
  • Esperar finalització: wait()... espera la finalització d'un fill.

Unix guarda l'estat de finalització dels processos destruïts en el seu PCB en espera que el procés pare reculli aquest estat mitjançant la crida wait. Els processos que estan en aquest estat intermedi entre vius i morts se'ls anomena zombies.

Canvi d'executable:

  • Executar un altre aplicació des de un aplicació concreta: exec() i similars

Manipulació de descriptors de fitxer:

  • Tancar un descriptor de fitxer: close()
  • Assignar un descriptor de fitxers a la taula de descriptors de fitxers d'un procés: dup() assigna un fd a la primera posició lliure de la taula.

Comandes

Consulteu la wiki:

Planificació de processos. Algorismes

El Planificador és la part del sistema operatiu que decideix quin serà l'ordre d'execució dels processos.

Els primers sistemes operatius no tenien planificació exclusiva o preemptiva i no podien fer fora un procés de la CPU per tal que un altre procés amb major prioritat pogués executar-se.

Recursos:

Planificadors i Sistemes operatius

  • Unix: Les primeres implementacions estan basades en nivells de prioritat (40 de -19 a 19) i cues multilevel feedback queue on cada cua és una cua Round Robin on es prioritza els processos curts i els processos d'E/S.
  • Sistemes operatius basats en Windows NT: Utilitza un sistema basat en prioritats (32 nivells) i cues [http://en.wikipedia.org/wiki/Multilevel_feedback_queue multilevel feedback queue. Les primeres versions de Windows i DOS no eren multitasca i les versions Windows 9x no tenien preemptive Scheduling.

Algorismes de planificació

Hi han múltiples algorismes de planificació. En els següents apartat veurem els més importants.

Recursos:

Cues FIFO (First In First Out)

Aquest tipus de sistema equivalen a un sistema sense planificació on els processos s'executen per estricte ordre seqüencial d'execució. Un nom equivalent és First Come First Served (FCFS)

Les estructures de dades dinàmiques Cua s'estudien en més detall al [Usuari:Sergi/Temari/Tema_12_Organizaci%C3%B3n_l%C3%B3gica_de_los_datos._Estructuras_din%C3%A1micas.#Cues | tema 12. Estructures dinàmiques] de les oposicions.

Algorisme Round Robin o per torns (quantums)

La planificació Round Robin és una de les més senzilles i utilitzades. Consisteix en una cua FIFO pero on cada procés no s'executa durant més d'un període de temps prefixat anomenat quantum. D'aquesta manera els processos llargs no poden saturar la cua.

El paràmetre important per dissenyar sistemes RC és la mida del quantum:

  • Quantum gran: Si el quantum és massa gran pot acabar esdevenint un esquema FIFO (i els processos llargs poden bloquejar al curts)
  • Quantum petit: Cal tenir en compte el cost del canvi de context (anomenat overhead). Si el quantum és molt petit, pot empitjorar molt el rendiment del sistema.

Els sistemes operatius utilitzant sistemes complexos que poden modificar el valor del quantum de forma dinàmica.

Recursos:

Algorismes de planificació amb prioritat per nivells

Aquest tipus de sistemes assignen un prioritat a cada procés. Les prioritat és divideixen en nivell de prioritat. Cada nivell sol tenir la seva pròpia cua FIFO i també s'aplica el processament per torns (Round Robin) en cada cua

Amb Unix/Linux tenim la comanda nice per tal de canviar la prioritat d'un procés. La majoria de processos tenen la prioritat 0. Augmentar injustificadament la prioritat d'un procés pot causar que la resta de processos (inclosos processo crítics del sistema) no funcionin correctament.

Multilevel feedback queue

Un dels sistemes més utilitzats (Windows i Unix) és multilevel feedback queue:

Prioritats

  1. Donar preferència als processos curts.
  2. Donar preferència als processos lligats a operacions d'E/S.
  3. Establir ràpidament de quin tipus és un procés i planificar-lo amb coherència al seu tipus.

Normalment s'implementa donant la possibilitat a un nou procés d'executar-se en un sol quantum. Això es fa situant inicialment un procés en un nivell alt de prioritat durant un quantum i si el procés es curt s'executarà aviat i si és llarg s'enviarà a una cua de prioritat inferior i s'executara segons una cua FIFO amb Round Robin.

Concurrència i comunicació entre processos. Seguretat

Seguretat

La majoria de sistemes operatius actuals (una excepció és DOS) impedeixen la comunicació directa entre processos. Aquesta protecció es realitza assignant a cada procés un espai de memòria específic i impedint que els processos puguin accedir a l'espai de memòria de la resta de processos.

En sistemes operatius actuals, els processos només es poden comunicar entre si mitjançant IPC (Inter-process Communication). L'IPC és un mecanisme 
controlat i depenent de cada sistema operatiu que controla la comunicació segura entre processos.

En alguns casos, per exemple en el cas de diferents processos d'un mateix programa executant-se al mateix temps, part de la memòria entre processos pot ser compartida (carrega del programa en memòria) per tal d'estalviar espai. Cada execució d'un mateix programa s'anomena instància del programa.

Conceptes

Condició de carrera. Race Condition

  • Race condition/Condició de carrera: És la situació en que la manipulació simultània d'un recurs per part de 2 o més processos o fils d'execució causa resultats inconsistents.

Secció critica

Exclusió mútua

Interbloqueig, abraçada mortal o deadlock

Inanició de recusos (starvation)

  • Inanició/starvation: condició en la que a un procés se li denega de forma sistemàtica l’accés a un recurs compartit i sense aquest recurs, la tasca a executar no pot ser mai finalitzada.

Operació atòmica (atòmic operation)

  • Operació atòmica: és aquella operació que podem assegurar que es dura a terme en una sola execució de CPU, sense la possibilitat que un altre procés la pugui interrompre a meitat de l'operació.

Exemples

Un dels exemples més bàsics de condició de carrera és el de l'accés i actualització d'un comptador. Suposem que dos processos, T1 i T2, volen actualitzar una variable global i que porta una compte. Les operacions en un ordre correcte podrien ser:

  1. Integer i = 0;
  2. T1 llegeix el valor de i i el guarda en un registre : 0
  3. T1 incrementa el valor de i: (contingut del registre) + 1 = 1
  4. T1 actualitza el valor de la variable 1 en memòria: 1
  5. T2 llegeix el valor de i i el guarda en un registre : 1
  6. T2 incrementa el valor de i: (contingut del registre) + 1 = 2
  7. T1 actualitza el valor de la variable 1 en memòria: 2
  8. Integer i = 2

Però no podem assegurar que aquest serà l'ordre en que s'executaran els processos. Per exemple podria succeir;

  1. Integer i = 0;
  2. T1 llegeix el valor de i i el guarda en un registre : 0
  3. T1 incrementa el valor de i: (contingut del registre) + 1 = 1
  4. T2 llegeix el valor de i i el guarda en un registre : 0
  5. T1 actualitza el valor de la variable 1 en memòria: 1
  6. T2 incrementa el valor de i: (contingut del registre) + 1 = 1
  7. T1 actualitza el valor de la variable 1 en memòria: 1
  8. Integer i = 1

Si el codi d'aquest problema fos:

global int A = 0

task Received()
    i = i + 1
    print i
end task 

Podem dir que la secció crítica és l'operació i = i+ 1. El problema sorgeix pel fet que aquesta operació no és una operació àtomica i per tant abans de finalitzar pot ser interrompuda per un altre procés.

Una solució típica per assegurar la sincronització dels dos processos és utilitzar un mecanisme d'exclusió mútua, que asseguri que la secció crítica sigui executada tota sencera per un sol procés abans de que un altre procés hi pugui accedir. Els mecanismes d'exclusió mútua solen seguir el següent esquema:

// Petició d'accés a la secció crítica
secció crítica
//Alliberament de la secció crítica

Els mecanismes d'exclusió mútua han d'assegurar el següent:

  • L'accés únic a la secció crítica per part d'un procés
  • No fer cap suposició sobre l'ordre o la velocitat d'execució dels processos
  • Garantir que si un procés finalitza o s'atura per qualsevol raó a la secció crítica l'execució continuarà i no es donaran resultats inesperats.
  • Permetre que tots els processos que estan en espera puguin accedir en un temps finit a la secció crítica (evitar la inanició o starvation dels processos)
  • Evitar les situacions d'interbloqueig o deadlock

Mecanismes d'exclusió mútua. Sincronització de processos

La sincronització de processos coordina l'execució de processos o fils d'execució de forma coordinada per tal de completar una tasca en un temps d'execució correcte i sense que es donin resultats no desitjables ni condicions de carrera. Hi ha diferents tipus de sincronització:

  • barrier
  • lock/semaphore
  • thread join
  • mutex
  • non-blocking synchronization
  • synchronous communication operations

Recursos:

Dormir (sleep) i despertar (wakeUP)

Moltes de les solucions de concurrència utilitzant un tipus de solució anomenada d'espera activa. És a dir, el procés que esta en espera d'aconseguir accés a la secció crítica es continua executant i de forma activa comprovant si pot accedir a la secció crítica. Aquest tipus de solucions són ineficients respecte a l'ús de CPU. La solució és utilitzar un sistema amb més estats, on es permeti que un procés es pugui aturar (dormir (sleep)) a l'espera que un altre procés el desperti (wakeUP o també signal).

La millor manera d'entendre aquest model és mitjançant un exemple. L'exemple clàssic és el del problema del Productor/Consumidor. En aquest problema, dos processos (Consumidor i Productor) accedeixen a un mateix espai de memòria. El productor col·loca productes a la memòria i el consumidor els consumeix. La idea és que el consumidor va consumint productes mentre ni hagin i s'atura (sleep) si la memòria esta buida. El productor al seu torn va omplint de productes la memòria fins que aquesta esta plena, moment en que atura (sleep) la seva producció. El productor dorm fins que el consumidor retira algun producte de la cua i el consumidor dorm fins que el productor produeix un nou producte.

La solució a aquest problema són els semàfors.

Semàfors

Un semàfor és una variable entera S que deixant de banda la seva inicialització només es pot incrementar o decrementar utilitzant les operacions  
signal(S) i wait(S) respectivament

Els semàfors van ser inventats per Edsger Dijkstra. Originalment Dijkstra va utilitzar una paraula inventada en holandes (prolaag) que és una combinació de probeer (P) te verlagen (V) (intentar i incrementar).

  • wait(S): decrementa el valor de la variable S i fa passar un procés a la secció crítica si S > 0. o P de provar en l'holandes (idioma de Dijkstra)
  • signal(S): incrementa el valor de S. Aquesta operació també es anomenada despertar (wakeUP) o V de incrementar en holàndes.
Un valor 0 d'un semàfor equival a no passar (vermell) a la secció crítica (no hi han recursos lliure) i un valor major que 0 indica que es pot passar 
(verd) a la secció crítica

Hi ha dos tipus de semàfors:

  • Semàfors binaris o mutex: S només pot prendre els valors 0 o 1
  • Semàfors n-aris: S pren valors de 0 fins a n.

El valor del semàfor és el número d'unitats de recurs que estan disponibles (si només hi ha un recurs, s'utilitza un semàfor binari). Si hi ha n recursos, s'inicialitzarà el semàfor a n. Així cada procés que sol·liciti un recurs, verificarà que el valor del semàfor sigui major que 0; si és així es que existeixen recursos lliures, podrà utilitzar un recurs i decrementar el valor del semàfor. Quant el semàfor arriba a 0, significa que tots els recursos estan ocupats, i els processos que demanen un recurs hauran d'esperar (semàfor torni a ser positiu) a que algun procés deixi d'utilitzar els recursos.

Els semàfors s'utilitzen de la següent forma per tal d'implementar l'exclusió mútua:

Exemple del problema de consumidor/productor amb semàfors:

semaphore full = 0
semaphore empty = BUFFER_SIZE 

procedure producer() {
    while (true) {
        item = produceItem()
        wait(empty)
        putItemIntoBuffer(item)
        signal(full)
    }
 }

procedure consumer() {
    while (true) {
        wait(full)
        item = removeItemFromBuffer()
        signal(empty)
        consumeItem(item)
    }
}
 

Tenim dos semàfors:

  • Un indicant si el BUFFER esta buit
  • Un altre indicant si el buffer esta ple

La majoria de sistemes operatius ofereixen crides de sistema que permeten treballar amb semàfors. En el cas de sistemes POSIX com Unix/Linux disposem de les crides a sistema:

#include <semaphore.h>

sem_init(sem_t ∗sem, int pshared, unsigned int value); 

sem_wait(sem_t ∗sem); 

sem_post(sem_t ∗sem); 

sem_getvalue(sem_t ∗sem, int ∗valp); 

sem_destroy(sem_t ∗sem);


Recursos:

Monitors

Les monitors són estructures de dades utilitzades en llenguatges de programació per sincronitzar processos. Van ser proposats per Hoare i són una forma avançada d'implementar semàfors utilitzada en llenguatges de programació (no existeixen com a crida del sistema dels sistemes operatius)

Recursos:

Problemes típics

Productor/Consumidor

http://en.wikipedia.org/wiki/Producer-consumer_problem http://en.wikipedia.org/wiki/Readers-writers_problem

El barber dorment

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

El problema dels filòsofs dinant

http://es.wikipedia.org/wiki/El_problema_de_los_fil%C3%B3sofos

Els fumadors de cigarretes

http://en.wikipedia.org/wiki/Cigarette_smokers_problem

Exclusió mútua per maquinari

Inhibició d'interrupcions

La majoria de computadores ofereixen una instrucció que permet inhibir les interrupcions de maquinari. Es podrien utilitzar per a l'exclusió mútua de la següent forma:

//inhibir interrupcions
secció crítica
//desinhibir interrupcions

Si s'inhibeixen les interrupcions un procés no pot ser expulsat de la CPU (s'inhibeix també la interrupció que atura un procés en execució cada cert temps - quantum- per donar pas a un altre procés) mentre executa la secció crítica.

Aquest model és perillós i no s'hauria d'utilitzar (ni permetre) en l'espai d'usuari ja que inhibir les interrupcions vol dir deixar el control del sistema a un sol procés.

Operacions test and set (TSL instruction)

És una instrucció de maquinari (instrucció de CPU) que permet implementar semàfors a nivell de maquinari. Permet provar (test) una condició abans d'escriure en una variable global. Si el test no s'acompleix l'actualització de la variable tampoc es duu a terme.

És una mecanisme d'espera ocupada i per tant no és el més eficient i en sistemes amb planificadors amb prioritat es poden arribar a situacions de deadlock.

Recursos:

Operació swap

És una operació de llenguatge màquina que permet intercanviar el continguts de dues paraules de memòria de forma atòmica.

Comunicació entre processos. Inter-Process Communication (IPC)

Inter-process communication IPC o comunicació entre processos són una sèrie de tècniques per a l'intercanvi de dades entre un o més processos o fils d'execució. Els processos poden estar a una mateixa màquina o en màquines remotes connectades a través d'una xarxa de comunicacions.

Les tècniques de comunicació entre processos estan dividides en

Hi han múltiples implementacions per a la comunicació entre processos. Es poden dividir en

Independents de la plataforma:

Dependents de la plataforma o llenguatge de programació:

  • Sistemes POSIX [mmap]:
    • Cues de missatges
    • Semàfors
    • Memòria compartida
  • KDE's Desktop Communications Protocol (DCOP)
  • Microsoft's ActiveX, Component Object Model (COM), Microsoft Transaction Server (COM+), Distributed Component Object Model (DCOM), Dynamic Data Exchange (DDE), Object Linking and Embedding (OLE),MSRPC, .NET Remoting
  • Novell's IPX/SPX.

Taula de mètodes IPC:

Métode Proveït per
Fitxers Tots els sistemes operatius
Senyals La majoria de sistemes operatius; Windows només ho suporta amb la llibreria de C
Socket La majoria de sistemes operatius
Pipe Tots els SO POSIX.
Named pipe Tots els SO POSIX.
Semaphore Tots els SO POSIX.
Memòria compartida Tots els SO POSIX.
Pas de missatges
(no es comparteix res)
Utilitzat per tots els sistemes amb el paradigma d'interfície de pas de missatges, pas de missatges POSIX, CORBA, XML-RPC i SOAP.
memory-mapped file Tots els SO POSIX.;
Cua de missatges La majoria de SO.
Mailbox Alguns SO.

Recursos:

Sistemes POSIX

POSIX és l'acrònim de Portable Operating System Interface i la X té el seu origen en UNIX com a senyal del seu origen. POSIX és una API (application programming interface) que és un estàndard per a la creació de Sistemes operatius portables de la IEEE.

Una traducció aproximada de l'acrònim podria ser "Interfície de Sistema Operatiu Portàtil basat en UNIX".

El terme POSIX va ser suggerit per Richard Stallman en resposta a una demanda de la IEEE.

Posix ofereix múltiples tècniques per a la sincronització i la comunicació de processos.

Semàfors

Senyals

Pipes

Les pipes estableixen un conducte bidireccional (pipe) de comunicació entre dos processos.

Les línies de comandes UNIX/GNU/Linux permeten utilitzar les PIPE directament per encadenar resultats de processos. Per exemple:

$ ps aux | more

Executa ps aux que mostra els processos d'un sistema i envia el resultat a la comanda more (que s'encarrega de mostrar el resultat pàgina a pàgina)

Recursos:

Sockets=

Memòria compartida

Aquest mètode permet l'intercanvi de dades entre processos utilitzant un zona de memòria. La zona de memòria és independent de les zones de memòria de cada procés (per les raons de seguretat comentades anteriorment). Un procés crea la zona de memòria de forma que la reta de processos i puguin accedir.

És un mètode molt ràpid de comunicació (respecte a altres mètodes com les Pipes o els sockets). Una limitació clara és que els processos s'han d'executar a la mateixa màquina.

IPC per memòria compartida s'utilitza bàsicament en sistemes Unix o sistemes operatius que compleixen amb l'estàndard POSIX. POSIX proveïx d'una API anomenada POSIX Shared Memory:

Crida de sistema:

# include sys/mman.h
shm_open() 

Recursos:

Pas de missatges

Posix Threads

Posix també ofereix suport per a threads. Consulteu l'apartat Fils d'execució

Eines de l'usuari