sistemas operativos - departamento lenguajes y …rusman/docencia/so/tema2.pdfconcurrente profesor:...

Sistemas Operativos 25/04/2005

Tema 4: Programación Multihebra 1

Departamento de Lenguajes y Ciencias de la Computación Universidad de Málaga

E.T.I. Informática Gestión

Sistemas OperativosSistemas Operativos

Curso 2004/2005Curso 2004/2005

Tema 2:Introducción a la programación

concurrente

Profesor: Francisco Rus Mansilla

Francisco Rus Mansilla Departamento de Lenguajes y Ciencias de la Computación. Universidad de Málaga 2

SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ÍÍndice de contenidos (I)ndice de contenidos (I)• Introducción a la programación concurrente

– Programación concurrente– Arquitecturas hardware– Estilos de programación– Programación concurrente en sistemas operativos

• Procesos y hebras– Por qué procesos multihebra– Ventajas que aportan las hebras– Sistemas operativos multihebra– Tipos de hebras– Implementación de hebras– Bibliotecas de hebras

• Programación con Procesos– Implementación– Funciones básicas– Otras funciones




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ÍÍndice de contenidos (II)ndice de contenidos (II)

• Programación con Pthreads– Funciones– Ciclo de vida de una hebra– Atributos

• Principios de programación concurrente– Conceptos– Exclusión mutua– Sincronización mediante condiciones– Semáforos

• Problemas clásicos de programación concurrente• Fuentes de información


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

IntroducciIntroduccióónn

• Programación concurrente• Arquitecturas hardware• Estilos de programación• Programación concurrente en sistemas operativos




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ProgramaciProgramacióón concurrenten concurrente

• Un programa concurrente es– Aquél que contiene uno o más procesos que trabajan de forma

conjunta para realizar una determinada tarea

• Dentro del programa concurrente– Cada proceso es un programa secuencial

• Diferencia entre un programa secuencial y uno concurrente– Un programa secuencial tiene un único flujo de ejecución– Un programa concurrente tiene múltiples flujos de control


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ProgramaciProgramacióón concurrenten concurrente

• Los procesos de un programa concurrente interactúan entre sí de dos formas:– Comunicación– Sincronización

• La comunicación se lleva a cabo de dos formas

– Compartiendo memoria– Enviando información por medio de mensajes

• Hay dos tipos básicos de sincronización– Exclusión mutua– Sincronización mediante condiciones




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte ComunicaciComunicacióón mediante memoria n mediante memoria

compartidacompartida• En este esquema

– Los procesos de un programa concurrente se comunican compartiendo un conjunto de variables que son visibles a todos ellos

– Estas variables son accedidas de la misma forma que cualquier otra variable

• Analogía: – Los asistentes a una clase y el contenido de la pizarra

/* Proceso 1 */

if (!impresoraOcupada)impresoraOcupada = true ;

// imprimirimpresoraOcupada = false ;

/* Proceso 2 */



/* Variable compartida */bool impresoraOcupada = false ;


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte ComunicaciComunicacióón mediante paso de n mediante paso de

mensajesmensajes• En este esquema

– Los procesos de un programa concurrente se comunican enviándose información mediante mensajes

– Es el mecanismo que se emplea cuando los procesos no comparten memoria

• Analogía:– Comunicación entre personas mediante correo electrónico

• Los programas concurrentes basados en paso de mensajes– Son más complejos, habitualmente, que los basados en memoria

compartida




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte SincronizaciSincronizacióón mediante exclusin mediante exclusióón n

mutuamutua• En un programa concurrente existen regiones o

secciones críticas– Son trozos de código que sólo los puede ejecutar un único

proceso en un instante dado

• El problema de la exclusión mutua– Es el problema de garantizar que las secciones críticas se

ejecuten de forma mutuamente exclusiva

/* Proceso 1 */



/* Proceso 2 */





SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

SincronizaciSincronizacióón mediante condicionesn mediante condiciones

• La sincronización mediante condiciones – Es el problema de retrasar la ejecución de un proceso hasta que

se cumpla una determinada condición

• Habitualmente,– La sincronización mediante condiciones se combina con la

sincronización mediante exclusión mutua

/* Proceso 1 */

wait if (impresoraOcupada)impresoraOcupada = true ;


/* Proceso 2 */







SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Arquitecturas hardwareArquitecturas hardware

• Tres tipos básicos de arquitecturas– Sistemas monoprocesador– Sistemas multiprocesadores– Sistemas distribuidos

Memoria principal

Cache de nivel 1

Procesador

Arquitectura de un sistema monoprocesador

Cache de nivel 2


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Los sistemas multiprocesadores– Están compuestos por un conjunto de procesadores que acceden

a los módulos de memoria por medio de una red de interconexión

– Esta red suele ser un bus o un conmutador de barras cruzadas (crossbar)

Procesador

Arquitectura de un sistema multiprocesador

Cache

Procesador

Cache

Memoria Memoria

Red de interconexión




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Los sistemas distribuidos– Difieren de los multiprocesadores en que cada procesador tiene

su propia memoria local – Se suelen denominar redes cuando la red de interconexión es

una red de área local (LAN) o de área extensa (WAN)

Procesador

Arquitectura de un sistema distribuido

Cache

Procesador

Cache

Memoria

Red de interconexión

Memoria


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Estilos de programaciEstilos de programacióónn

• Se pueden distinguir tres estilos de programación, que permiten desarrollar tres tipos de aplicaciones diferentes– Programación concurrente– Programación distribuida– Programación paralela

• Estas disciplinas no son excluyentes




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Programación concurrente– Es la disciplina que estudia la programación de procesos

concurrentes – Aunque se suele aplicar al contexto en el que los procesos se

comunican mediante memoria compartida• Ejemplos de aplicaciones:

– Sistemas de ventanas – Sistemas operativos


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Programación distribuida– Es la rama de la programación concurrente que se centra en el

estudio de la programación sobre sistemas distribuidos– Los procesos se comunican mediante paso de mensajes

• Ejemplos de aplicaciones:– Sistemas de ficheros en red– Servidores Web– Bases de datos para reserva de billetes

• Es habitual que los componentes de un sistema distribuido sean a su vez programas concurrentes




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Programación paralela– A veces se considera un sinónimo de programación concurrente– Se utiliza el término computación paralela cuando se utiliza un

computador paralelo con el fin de• resolver un problema más rápidamente,• resolver un problema mayor en un mismo tiempo, o• resolver un problema de mayor tamaño

• Ejemplos de aplicaciones– Computaciones científicas que modelan y simulan el clima, el

movimiento de las mareas, etc.– Procesamiento de imágenes– Problemas de optimización combinatoria


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ParadigmasParadigmas

• La mayoría de las aplicaciones concurrentes utilizan cinco tipos de soluciones, o paradigmas– Paralelismo iterativo– Paralelismo recursivo– Productores y consumidores– Clientes y servidores– Paralelismo entre iguales (peer parallelism)




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Paralelismo iterativo– Aplicación habitual: computación científica paralela (ejemplo:

producto de matrices)

• Paralelismo recursivo– Aplicación habitual: ordenación, optimización combinatoria,

juegos (ejemplo: ajedrez)

• Productores y consumidores– Aplicación habitual: procesos que generan datos que han de usar

otros procesos (ejemplo: tuberías en UNIX)

• Clientes y servidores– Aplicación habitual: sistemas distribuidos (ejemplo:

navegadores y servidores Web)


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Paralelismo entre iguales– Aplicación habitual: programas distribuidos paralelos (ejemplo:

producto de matrices distribuidos)




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte ProgramaciProgramacióón concurrente en sistemas n concurrente en sistemas

operativosoperativos• La programación concurrente tiene su origen en

los sistemas operativos• Surge como solución a un problema:

– Maximizar el uso de la capacidad de procesamiento de los sistemas informáticos

• Evolución

1960

1970

1990

Procesamiento por lotes

Multiprogramación o multitareaReparto de tiempo (time slicing)

Tiempo compartido (time sharing)

MultiprocesamientoProcesamiento distribuido


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Procesos y hebrasProcesos y hebras

• Hasta mediados de los años 80, para los sistemas operativos los procesos son entidades que:– Presentan una actividad dentro del sistema operativo (son las

entidades activas)– Su flujo de ejecución es secuencial– Su ejecución la planifica el sistema operativo– Se ejecutan en un espacio de direcciones– Solicitan y usan los recursos del sistema operativo

Proceso tradicional:Un flujo de ejecución secuencial

Recursos

Flujo de ejecución




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Por quPor quéé procesos procesos multihebramultihebra

• Inconvenientes de este modelo de proceso– Son entidades costosas de crear y manipular– Compartir recursos entre procesos es complejo y costoso

• Solución adoptada:– Generalizar el concepto de proceso, de forma que a cada

proceso se le pueda asociar más de una actividad de procesamiento

Proceso actual:Varios flujos de ejecución concurrentes

Recursos

Flujos de ejecución


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Separación de conceptos– Un proceso es un entorno de ejecución sobre el que se ejecutan

una o varias hebras (threads)– Una hebra es una entidad que presenta una actividad

• A un proceso se asocia– Espacio de direcciones– Variables globales– Ficheros abiertos

• A una hebra se asocia– Registro contador de programa– Pila– Estado (listo, ejecución, bloqueado)




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• A este tipo de procesos se le denomina multihebra(multithreaded process)

• En un proceso multihebra– Todas las hebras comparten todos los recursos del proceso– Las hebras de un proceso se comunican mediante memoria

compartida

• Al contrario de lo que ocurre entre procesos distintos– El sistema operativo no tiene que preocuparse de que las hebras

de un proceso interfieran entre sí


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Ventajas que aportan las hebrasVentajas que aportan las hebras

• Los procesos multihebra aportan las siguientes ventajas:– Solapamiento de operaciones de entrada/salida y computación

dentro de un mismo proceso– Multiprocesamiento– Una hebra consume menos recursos y requiere un coste de

manipulación menor que un proceso– Existen aplicaciones concurrentes cuya estructura se amolda de

forma natural a un esquema multihebra




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Sistemas operativos Sistemas operativos multihebramultihebra

• La mayoría de los sistemas operativos actuales son multihebra– Solaris – Linux– Windows NT/2000– MacOS X


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Tipos de hebrasTipos de hebras

• Hay dos tipos de hebras– Las hebras que se ejecutan en el espacio de usuario– Las hebras que se ejecutan en el espacio del núcleo

Núcleo

Espacio de

usuario

Hebras de usuario

Hebras de núcleo

Procesos

Espacio del

núcleo




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón de hebrasn de hebras

• Existen varias formas de hacer corresponder las hebras de usuario con las hebras de núcleo– Muchas-a-Una– Una-a-Una– Muchas-a-Muchas

• Cada una estas formas da lugar, respectivamente, a un esquema de implementación diferente– Implementación a nivel de usuario– Implementación a nivel de núcleo– Implementación híbrida


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón a nivel de usuarion a nivel de usuario

• Características– Correspondencia Muchas-a-Una– Todas las hebras de usuario de un proceso se vinculan a una

única hebra del núcleo

Núcleo

Espacio de

usuario

Hebras de usuario

Hebras de núcleo

Procesos

Espacio del

núcleo




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón a nivel de usuarion a nivel de usuario

• Ventajas– Gestión de hebras eficiente– Esquema empleado en sistemas operativos no multihebra

• Inconvenientes– Si una hebra se bloquea, se bloquea todo el proceso– No permite multiprocesamiento

• Ejemplos– La biblioteca de procesos de peso ligero (LWP o light weighted

processes) del sistema operativo SunOS– Los sistemas operativos actuales no admiten este esquema (ver

implementaciones híbridas)


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón a nivel de nn a nivel de núúcleocleo

• Características– Correspondencia Una-a-Una– Cada hebra de usuario se vincula a una única hebra del núcleo

Núcleo

Espacio de

usuario

Hebras de usuario

Hebras de núcleo

Procesos

Espacio del

núcleo




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón a nivel de nn a nivel de núúcleocleo

• Ventajas– Permite obtener todos los beneficios de aportan las hebras

• Inconvenientes– Gestión de hebras más costosa que en el caso de la

implementación a nivel de usuario– Número máximo de hebras teóricamente inferior al de una

implementación a nivel de usuario

• Ejemplos de sistemas– Windows NT/2000– Linux


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón hn hííbridabrida

• Características– Correspondencia Muchas-a-Muchas– Existe varias formas de vincular las hebras de usuario con las

hebras del núcleo

Núcleo

Espacio de

usuario

Hebras de usuario

Hebras de núcleo

Procesos

Espacio del

núcleo




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón hn hííbridabrida

• Ventajas– Combina las ventajas de la implementación a nivel de usuario

(bajo coste de manipulación) con las de la implementación a nivel de núcleo (no limita las posibilidades que permiten las hebras

• Inconvenientes– Modelo de programación complejo cuando la vinculación entre

hebras de usuario y hebras de núcleo es responsabilidad del programador

– Ejemplo: Solaris• En otros sistemas

– La vinculación es automática– Ejemplo: Tru64 (antiguo Digital UNIX)


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Bibliotecas de hebrasBibliotecas de hebras

• Los lenguajes más usados para programar sobre sistemas operativos (C/C++) no incorporan hebras

• Pero puede hacer uso de las hebras del sistema operativo a través de una biblioteca de funciones

• En la actualidad existen dos bibliotecas de hebras de uso mayoritario– Hebras Win32, usadas en los sistemas operativos de 32 bits de

Microsoft– Hebras POSIX (Pthreads), usadas en sistemas UNIX




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Bibliotecas de hebrasBibliotecas de hebras

• Comparación entre hebras Win32 y Pthreads– Windows NT/2000 fue diseñado desde el principio para que

fuese multihebra– En UNIX se ha producido una adaptación de procesos

tradicionales a procesos multihebra• Consecuencia

– En Windows NT/2000 las hebras están integradas de forma natural dentro del sistema

– En UNIX existen conflictos cuando se usan características que están pensadas para procesos tradicionales (ejemplos: bloqueo de ficheros, señales)


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte ProcesosProcesos

• Aspectos de Implementación• Funciones básicas• Otras funciones




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Aspectos de implementaciAspectos de implementacióónn

• La estructura principal para la gestión de procesos es la tabla de procesos– Contiene una entrada por cada proceso

• Cada entrada contiene, entre otra información– El PID y el PPID del proceso– El identificador de usuario real (UID) y efectivo y el

identificador de grupo (GID)– El estado del proceso– Puntero a la tabla de páginas del proceso– Información sobre las señales pendientes de ser enviadas al

proceso, así como máscaras que indican qué señales son aceptadas y cuáles son ignoradas

– Parámetros de planificación


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Aspectos de implementaciAspectos de implementacióónn

• Los procesos se crean a partir de programas que contienen código ejecutable

• Estructura del espacio de direcciones de un proceso:

Datos inicializados de lectura/escritura

Datos inicializados de sólo lectura

Datos sin inicializar

Código

Montículo (Heap)

Pila (Stack)




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Funciones bFunciones báásicassicas

• Operaciones básicas que se pueden realizar con procesos

Espera que un determinado hijo proceso acabewaitpid

Termina un procesoexit

Ejecuta un nuevo programaexec

Espera que un proceso hijo acabewait

Crea un nuevo procesofork

DescripciónLlamada


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Crear un procesoCrear un proceso

• Si la llamada fork() tiene éxito– Se crea un nuevo proceso, denominado proceso hijo– El proceso hijo es una copia del proceso padre

pid_t fork (void)

Devuelve: - El valor –1 en caso de error- El valor 0 al proceso hijo y PID del proceso hijo al proceso padre, en caso de éxito




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• Ejemplo

#include <unistd.h>

main() {pid_t IdentificadorDeProceso ;

printf(“Soy el proceso %d \n”, getpid()) ;printf(“Voy a crear un proceso hijo\”) ;IdentificadorDeProceso = fork() ;

if (IdentificadorDeProceso == -1) printf(“Se ha producido un error al crear el hijo\n”) ;

else if (IdentificadorDeProceso == 0) printf(“Soy el nuevo proceso hijo (%d)\n”, getpid()) ;

else {printf(“Sigo siendo el proceso padre. He creado ”) ;printf(“el proceso %d\n”, IdentificadorDeProceso) ;

} /* else */} /* main */


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• A considerar

– El proceso hijo hereda del padre una copia de su código, datos, pila, descriptores de ficheros abiertos y tabla de señales

– El padre y el hijo se diferencian en sus PID y PPID




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Ejecutar un nuevo programaEjecutar un nuevo programa

int execl, execlp (const char * Ruta const char * Argumento0...const char * ArgumentoN(char *)0

)

int execv, execvp (const char * Rutachar *const ArrayDeArgumentos[]

)

Devuelven:- el valor –1 en caso de error

• La familia de funciones exec()– Reemplazan el código, datos y pila del proceso que las invoca

por el programa ejecutable indicado por Ruta


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• A considerar– execl() es idéntica a execlp(), y execv() es idéntica a execvp(), salvo que execl() y execv() requieren el camino absoluto o relativo para encontrar el fichero ejecutable,mientras que execlp() y execvp() usan la variable de entorno $PATH para encontrar ruta

– Si el fichero ejecutable no se encuentra, se devuelve -1. En caso contrario, el proceso que realiza la llamada reemplaza su código, datos y pila por los del fichero ejecutable y comienza a ejecutar su nuevo código

– Si la ejecución se realiza correctamente, no se devuelve ningún valor




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• A considerar– execl() y execlp() invocan el fichero ejecutable usando

como argumentos las cadenas de caracteres apuntadas por argumento0, argumento1, ..., argn. argumento0 debe ser el nombre del fichero ejecutable, y la lista de argumentos debe de terminar con la cadena vacía NULL ((char *)0)

– execv() y execvp() invocan el fichero ejecutable usando como argumentos un array de cadenas de caracteres apuntado por arrayDeArgumentos. argv[n+1] es NULL y arrayDeArgumentos[0] contiene el nombre del fichero ejecutable


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Esperar a que un hijo termineEsperar a que un hijo termine

• Esta llamada– Provoca la suspensión del proceso hasta que uno de sus hijos

termine

• En la dirección indicada por el argumento– Se devuelve el estado de terminación del proceso hijo, que lo

envía mediante la llamada exit()

– Si la dirección es NULL, no se devuelve nada

pid_t wait (int * EstadoDelProcesoHijo

)

Devuelve:- el valor (pid_t) –1 en caso de error- el PID del proceso hijo, en caso de éxito




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Esperar a que un determinado hijo Esperar a que un determinado hijo

terminetermine

• Esta llamada– Permite que un proceso espere a que acabe un proceso hijo cuyo

PID se indica en el primer argumento– El estado del proceso hijo se devuelve en el segundo argumento

pid_t waitpid (pid_t * IdentificadorDelProcesoHijo int * EstadoDelProcesoHijoint Opciones

)

Devuelve:- el valor (pid_t) –1 en caso de error- el PID del proceso hijo, en caso de éxito


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Esperar a que un determinado hijo Esperar a que un determinado hijo

terminetermine

• A considerar– Si el valor del PID del proceso hijo es –1 y el tercer argumento

es 0, waitpid() se comporta igual que wait()

• El tercer argumento puede tomar varios valores– Por ejemplo, el valor WNOHANG hace que la llamada waitpid()

no se bloquee si el hijo no ha terminado todavía




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Terminar un procesoTerminar un proceso

• La invocación de esta llamada– Provoca el cierre de todos los descriptores de ficheros, devuelve

al sistema los recursos ocupados por el código, datos y pila, y termina el proceso

• El estado del proceso– Es enviado al proceso padre, que lo podrá obtener mediante la

llamada wait() o waitpid()

– Sólo los 8 bits menos significativos son útiles para el proceso padre

void exit (int EstadoDelProcesoHijo

)

Devuelve:- ningún resultado


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Terminar un procesoTerminar un proceso

• A considerar– Si un proceso realiza la llamada exit() permanece en estado

zombie hasta que su padre ejecuta la llamada wait() o waitpid()

– Todos aquellos procesos hijos que sean huérfanos son adoptados por el proceso init (el proceso cuyo PID es 1), que siempre acepta los códigos de terminación de sus proceso hijos




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Otras funciones de gestiOtras funciones de gestióón de procesosn de procesos

• Llamadas para obtener identificadores

El identificador del grupo del procesogetpgrp()

El identificador de la sesión del procesogetsid()

El identificador de usuario efectivogeteuid()

El identificador de grupo efectivogetegid()

El identificador de grupo realgetgid()

El PID del proceso padregetppid()

El identificador de usuario realgetuid()

El PID del procesogetpid()

DevuelveLlamada


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Obtener el valor de una variable de Obtener el valor de una variable de

entornoentorno

• A considerar– El valor de las variables de entorno también se puede obtener a

partir del tercer argumento de la función main()

char * getenv (const char * NombreDeVariableDeEntorno

)

Devuelve:- el valor –1 en caso de error- un puntero al valor de la variable de entorno




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte ProgramaciProgramacióón con n con PthreadsPthreads

• Funciones• Ciclo de vida de una hebra• Atributos


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte ProgramaciProgramacióón con n con PthreadsPthreads. Funciones. Funciones

• Las funciones de la biblioteca Pthreads se dividen en dos grupos– Funciones para gestión de hebras– Funciones para sincronización de hebras

• Funciones básicas de gestión de hebras– Creación pthread_create()– Terminación pthread_exit()– Espera de terminación pthread_join()

• Objetos de sincronización– Mutexes– Variables de condición– Semáforos– Cerrojos de lectura/escritura (rwlocks)




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Ciclo de vida de una hebraCiclo de vida de una hebra

• En su forma más básica, la utilización de una hebra requiere los siguientes pasos– Incluir el fichero de cabecera pthread.h

– Declarar un descriptor

– Crear la hebra

– Terminar la ejecución de la hebra

– Esperar que la hebra termine

#include <pthread.h>

pthread_t idHebra ;

pthread_create(&idHebra, NULL, funcion, argumentos) ;

pthread_exit(valor)

pthread_join(idHebra, NULL)


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Ciclo de vida de una hebraCiclo de vida de una hebra

• Ejemplo: programa simple.c/*/* Programa simple.c: ejemplo de ciclo de vida de una hebra*/#include <pthread.h>#include <stdio.h>

void * codigoHebra(void *parametros) {printf("Soy la hebra\n") ;

} /* codigoHebra */

int main(int argc, char ** argv) {pthread_t idHebra ;int resultado ;

resultado = pthread_create(&idHebra, NULL, codigoHebra, NULL) ;if (resultado != 0) { /* 0 indica exito */

printf("main: error al crear la hebra\n") ;return -1 ;

} /* if */

printf("Soy la hebra principal\n") ;

pthread_join(idHebra, NULL) ;

printf("Fin de la hebra principal\n") ;

} /* main */




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Ciclo de vida de una hebraCiclo de vida de una hebra• Ejemplo: programa simple.c• Compilación del programa

% gcc simple.c -o simple –D_REENTRANT –lpthread

• Ejecución


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Atributos de una hebraAtributos de una hebra

• Una hebra POSIX puede tener atributos– Cuando se crea una hebra, por defecto sus atributos tienen

asignados un valor inicial

• Los atributos afectan, entre otros, a:– Tamaño de la pila

pthread_attr_setstacksize()– Dirección de la pila

pthread_attr_setstackaddr()– Ámbito

pthread_attr_setscope()– Planificación

pthread_attr_setschedpolicy()




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Atributos de una hebraAtributos de una hebra

• Ejemplo de uso de atributos– En Solaris, cuando una hebra se crea, por defecto es una hebra

de usuario. Esto es así porque el atributo que afecta por defecto al ámbito de planificación de una hebra es el proceso

– Para crear una hebra de núcleo, hay que crear la hebra con ámbito de sistema

#include <pthread.h>...pthread_attr_t atributos ; // atributos de la hebrapthread_attr_init(&atributos) ; // inicializacion

// Se establece el atributo de ambitopthread_attr_setscope(&atributos, PTHREAD_SCOPE_SYSTEM) ;

resultado = pthread_create(&idHebra, &atributos, codigoHebra, NULL) ;

...


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Principios de programaciPrincipios de programacióón concurrenten concurrente

• Definición: estado de un programa– El estado de un programa concurrente viene dado por el valor

de las variables del programa en un instante concreto de tiempo– Todo programa comienza en un estado inicial– Cada proceso del programa se ejecuta de forma independiente

• Definición: acción atómica– Los procesos ejecutan secuencias de instrucciones– Cada instrucción se compone de secuencias de una o varias

acciones atómicas– Son acciones que, de forma indivisible, examinan o alteran el

estado del programa




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• Definición: intercalación– La ejecución de un programa concurrente da lugar a la

ejecución intercalada (interleaving) de las secuencias de acciones atómicas ejecutadas por cada proceso

• Definición: historia– Una ejecución concreta de un programa concurrente da lugar a

una historia, que es una secuencia de acciones atómicas S0àS1à ... à Sn

– Una ejecución paralela puede modelarse como una historia secuencial, porque el efecto de ejecutar acciones atómicas en paralelo es equivalente a ejecutarlas en algún orden secuencial


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• Definición: propiedad– Cada ejecución de un programa concurrente produce una

historia– El número de historias posibles para un programa es muy

elevado– El motivo es que existen muchas formas de intercalar las

acciones atómicas de un programa, aunque se parta siempre del mismo estado inicial

– Una propiedad es un atributo del programa que se cumple en cualquier posible historia del mismo

– Existen dos tipos de propiedades: de seguridad y de viveza




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Principios de programaciPrincipios de programacióón n

concurrenteconcurrente• Definición: propiedad de seguridad

– Una propiedad de seguridad (safety property) es aquella que garantiza que el programa nunca entra en un estado no válido

– Un estado no es válido cuando algunas variables de estado tienen un valor incorrecto

– Ejemplos de propiedades: exclusión mutua, ausencia de interbloqueo (deadlock)

• Definición: propiedad de viveza– Una propiedad de viveza (liveness property) es aquella que

garantiza que el programa entrará eventualmente en un estado válido

– Ejemplo de propiedades: terminación de un programa, entrada en una sección crítica


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

El problema de la exclusiEl problema de la exclusióón mutuan mutua

• Características del problema– Existe un conjunto de procesos que repetidamente intentan

ejecutar una sección crítica y después una sección no crítica– La sección crítica ha de ir precedida de un protocolo de entrada

y seguida por un protocolo de salida

/* La estructura de este código es la misma para *//* todos los procesos del programa concurrente */

while (true) {/* protocolo de entrada *//* sección crítica *//* protocolo de salida *//* sección no crítica */

} /* while */




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

El problema de la exclusiEl problema de la exclusióón mutuan mutua• Para tener una solución satisfactoria al problema, los

protocolos de entrada y de salida deben cumplir las siguientes propiedades– Exclusión mutua:

• Sólo un proceso como máximo puede estar a la vez en su sección crítica

– Ausencia de interbloqueo (livelock): • Si dos o más procesos quieren entrar a la vez en sus secciones

críticas, alguno lo conseguirá

– Ausencia de retrasos innecesarios: • En el caso de que únicamente un proceso quiera entrar en la

sección crítica

– Entrada eventual:• Si un proceso intenta entrar en su sección crítica, eventualmente lo

conseguirá


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ExclusiExclusióón mutua con n mutua con PthreadsPthreads

• Para delimitar el acceso a secciones críticas, Pthreads proporciona un objeto de sincronización llamado mutex

/* Ejemplo de sección crítica (SC) usando mutexes de */ /* la biblioteca Pthreads */

#include <pthread.h>bool impresoraOcupada = false ;...pthread_mutex_t mutex ; pthread_mutex_init(&mutex, NULL) ;...

pthread_mutex_lock(&mutex) ; /* entrada en la SC *//* seccion crítica */if (!impresoraOcupada)impresoraOcupada = true ;

pthread_mutex_unlock(&mutex) ; /* salida de la SC */

/* sección no crítica */impresoraOcupada = false ;




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• La sincronización de procesos mediante exclusión mutua permite el acceso a secciones críticas de código– Sin embargo, este mecanismo es insuficiente para resolver otro

problema de sincronización, como es el bloqueo de un proceso a la espera de que se cumpla una determinada condición

• Ejemplo tipo:– El problema de los productores/consumidores, que se

comunican a través de un buffer circular– Un productor no puede insertar elementos si el buffer está lleno– El consumidor no puede extraer elementos si el buffer está

vacío


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Contexto del problema– Un proceso dentro de una sección crítica comprueba si una

condición se cumple– Si se cumple, el proceso continua su ejecución dentro de la

sección crítica– Si no se cumple, el proceso debe esperar hasta que la condición

se cumpla, pero para ello debe abandonar temporalmente la sección crítica

/* Proceso 1 */



/* Proceso 2 */







SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Variables de condiciVariables de condicióón en n en PthreadsPthreads

• El problema de la sincronización mediante condiciones se resuelve en Pthreads mediante el uso de variables de condición

• Una variable de condición es un objeto de sincronización sobre el que se definen dos operaciones básicas– pthread_cond_wait(&cond, &mutex)– pthread_cond_signal(&cond)

• La operación de espera provoca la suspensión de la hebra y la liberación del mutex

• La operación de señalización reanuda la ejecución de la hebra previamente suspendida


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Variables de condiciVariables de condicióón en n en PthreadsPthreads/* Ejemplo de utilización de variables de condición *//* con Pthreads */

#include <pthread.h>bool impresoraOcupada = false ;...pthread_mutex_t mutex ; pthread_mutex_init(&mutex, NULL) ;...pthread_cond_t sePuedeImprimir ;Pthread_cond_init(&sePuedeImprimir) ;...pthread_mutex_lock(&mutex) ; /* entrada en la SC *//* seccion crítica */while (!impresoraOcupada)pthread_cond_wait(&sePuedeImprimir, &mutex) ;

impresoraOcupada = true ;pthread_mutex_unlock(&mutex) ; /* salida de la SC */.../* sección no crítica */...pthread_mutex_lock(&mutex) ; /* entrada en la SC */impresoraOcupada = false ;pthread_cond_signal(&sePuedeImprimir) ;

pthread_mutex_unlock(&mutex) ; /* salida de la SC */




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte SemSemááforosforos

• Un semáforo es un objeto con un valor entero, al que se puede asignar un valor inicial no negativo, y al que solo se puede acceder utilizando dos operaciones atómicas:

• Las definiciones de las operaciones son:

wait o P

y

signal o V

wait (s) {s = s-1;if (s<0)

Bloquear }

signal(s) {s = s + 1;if (s <= 0)

Desbloquear}


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

SemSemááforosforos

• Exclusión mutua con semáforos

• Ejercicio:

semáforo s =1;....

wait(s);/* sección crítica */

signal(s);

/* sección no crítica */

¿Valor de s?

Comparación entre mutex y semáforo




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Problemas clProblemas cláásicos de programacisicos de programacióón n

concurrenteconcurrente

• Existen varios problemas que, ya sea por ser instructivos o por su utilidad en la práctica, se han convertido en problemas clásicos de programación concurrente

• Entre estos problemas están:– Exclusión mutua– El problema de los filósofos– Lectores/Escritores– Productores/consumidores


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte FilFilóósofos comensalessofos comensales

§ piensan y comen alternativamente

§ Para comer necesitan 2 tenedores

§ Sólo se puede coger 1 tenedor a la vez

Los filósofos:




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


• Primera aproximación con semáforos

semáforo tenedor[5] = {1}

.....

void filosofo (int i) {

pensar();wait(tenedor[i]);wait(tenedor[(i+1) mod 5] );comer();signal(tenedor[(i+1) mod 5] );signal(tenedor[i]);

}

INTERBLOQUEO


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre


¿Solución?




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Productores/consumidoresProductores/consumidores

• Definiciones– Sea un buffer circular con una capacidad de MAX_BUF

elementos– Un productor es un proceso o hebra que quiere insertar

elementos en el buffer– Un consumidor es un proceso o hebra que quiere extraer

elementos del buffer

• Enunciado: dado un conjunto de productores y de consumidores que se comunican a través de un buffer común, se deben cumplir dos condiciones– Un productor se ha de bloquear si intenta insertar un elemento

cuando el buffer está lleno– Un consumidor se ha de bloquear si intenta extraer un elemento

cuando el buffer está vacío


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte Productores/consumidoresProductores/consumidores

while (cierto) {producir();wait(huecos);wait(s);añadir();signal(s);signal(datos);

}

while(cierto) {wait(datos);wait(s);coger();signal(s);signal(huecos);consumir();

}

Productor/consumidor con semáforos

semáforo s = 1;semáforo datos = 0;semáforo huecos = MAX_BUF

PRODUCTOR CONSUMIDOR




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

ImplementaciImplementacióón con n con PthreadsPthreads

• Requisitos– Un buffer será una instancia de un tipo abstracto de datos mt_buffer_t. Los elementos del buffer serán números enteros

– Las operaciones del buffer serán seguras desde el punto de vista de su utilización en programas multihebras (thread safe)

– La especificación las operaciones es la siguiente:

.../* funciones para crear y destruir un buffer */int mt_buffer_init(mt_buffer_t *) ;int mt_buffer_destroy(mt_buffer_t *) ;

/* funciones para acceder al buffer */int mt_buffer_insertar(mt_buffer_t *, int) ;int mt_buffer_extraer (mt_buffer_t *, int *) ;int mt_buffer_vacio(mt_buffer_t *, bool *) ;int mt_buffer_lleno(mt_buffer_t *, bool *) ;

...


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Productores/consumidoresProductores/consumidores• Implementación del tipo mt_buffer_t

...

typedef struct {int buffer[MAX_BUF] ;int elemento ; /* Primer elemento del buffer */int hueco ; /* Primer hueco del buffer */int num_elementos ; /* Numero de elementos en el buffer */

pthread_mutex_t mutex ;pthread_cond_t esta_vacio ;pthread_cond_t esta_lleno ;

} mt_buffer_t ;

...




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Productores/consumidoresProductores/consumidores• Implementación de mt_buffer_extraer

int mt_buffer_extraer (mt_buffer_t * buf, int * elemento) {int error ; /* Variable usada en el control de errores */

/** Paso 1: se bloquea el mutex */

error = pthread_mutex_lock(&(buf->mutex)) ;if (error != 0) {/* Error al bloquear el mutex */return error ;

} /* if */

/** Paso 2: se espera hasta que haya algun elemento en el buffer*/

while (buf->num_elementos == 0) {error = pthread_cond_wait(&(buf->esta_vacio), &(buf->mutex)) ;if (error != 0) {/* Error al espera en la variable de condicion esta_vacio */return error ;

} /* if */ } /* while */

/* -----------> sigue */


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


/* <-------------- Viene de atrás *//* * Paso 3: se extrae el elemento*/

*elemento = buf->buffer[buf->elemento] ;buf->elemento = (buf->elemento + 1) % MAX_BUF ;buf->num_elementos -- ;

/** Paso 4: se comprueba si el buffer estaba lleno, y se despierta * a un hipotetico productor que estuviese bloqueado en* esta_lleno*/

if (buf->num_elementos == (MAX_BUF - 1)) pthread_cond_signal(&(buf->esta_lleno)) ;

/** Paso 5: se libera el mutex*/

error = pthread_mutex_unlock(&(buf->mutex)) ;if (error != 0) {/* Error al desbloquear el mutex */return error ;

} /* if */ return 0 ;

} /* mt_buffer_extraer */




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte


• Ficheros:– mt_buffer.h contiene la especificación completa del tipo– mt_buffer.c contiene la implementación– prodcons.c contiene un ejemplo de uso de un buffer

mt_buffer_t por parte de un productor y de un consumidor– linux.mak y solaris.mak son ficheros para compilar los

programas en Linux y Solaris, respectivamente


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Fuentes de informaciFuentes de informacióónn

• Bibliografía• Direcciones en la Web




SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

BibliografBibliografííaa

• UNIX Programación Práctica. Guía para la concurrencia, la comunicación y los Multihilos– Kay A. Robbins, Steven Robbins– Prentice Hall, 1997

• Foundations of Multithreaded, Parallel and Distributed Programming– Gregory R. Andrews– Addison-Wesley, 2000


SO -

Tema

2:In

trod

ucción

a la

prog

ramac

ión

conc

urre

nte

Direcciones en la WebDirecciones en la Web

• Referencia sobre Pthreads, tomada de la Web del OpenGroup– http://www.unix-systems.org/version2/whatsnew/threadsref.html

• Grupo de noticias de programación multihebra– news://comp.programming.threads

• Páginas que contienen enlaces relacionados conPthreads– http://www.cs.iastate.edu/~mayuresh/pthreads.shtml– http://www.humanfactor.com/pthreads/pthreadlinks.html

sistemas operativos - departamento lenguajes y …rusman/docencia/so/tema2.pdfconcurrente profesor:...

Documents