Story Transcript
09/09/2014
T5-multithreading
1.1
Indice Proceso vs. Flujos Librerías de flujos Comunicación mediante memoria compartida
Condición de carrera
Sección Crítica
Acceso en exclusión mutua
Problemas
Abrazos mortales
1.2
1
09/09/2014
Procesos vs. Flujos Hasta ahora…..
Una única secuencia de ejecución: Sólo 1 Program Counter y una pila
Concurrencia entre procesos, pero dentro de un proceso la ejecución era
secuencial (una única secuencia de instrucciones)
No es posible ejecutar concurrentemente diferentes funciones dentro del mismo proceso
Aunque puedan haber partes del código independientes entre si
1.3
Ejemplo: aplicación cliente-servidor Cliente 1 { .. Cliente 2 Enviar_peticion(); { Esperar_respuesta(); .. Procesar_respuesta(); Enviar_peticion(); … Cliente N Esperar_respuesta(); } { Procesar_respuesta(); .. … Enviar_peticion(); } Esperar_respuesta(); Procesar_respuesta(); … }
DATOS GLOBALES Servidor { While(){ Esperar_peticion(); Preparar_respuesta(); Enviar_respuesta(); } }
Monoproceso: sólo un cliente cada vez Se desaprovecha las ventajas de la concurrencia y del paralelismo Multiproceso: un proceso para cada cliente simultáneo que se quiera atender Ejecución concurrente y/o paralela Pero… Se desaprovechan recursos Replicación innecesaria de estructuras de datos que almacenan los mismos valores, replicación del espacio lógico de memoria, mecanismos para intercambiar información,…
1.4
2
09/09/2014
CASO : aplicación cliente-servidor Cliente 1 { .. Enviar_peticion(); Esperar_respuesta(); Procesar_respuesta(); … } Cliente 2 { .. Enviar_peticion(); Esperar_respuesta(); Procesar_respuesta(); … } Cliente N { .. Enviar_peticion(); Esperar_respuesta(); Procesar_respuesta(); … }
DATOS GLOBALES Servidor { While(){ INICIO_proceso Esperar_peticion(); Preparar_respuesta(); Enviar_respuesta(); FIN_proceso } DATOS GLOBALES DATOS GLOBALES} DATOS GLOBALESServidor Servidor { While(){
Servidor { While(){
{ While(){
DATOS GLOBALES Servidor { While(){
INICIO_proceso INICIO_proceso INICIO_proceso Esperar_peticion(); INICIO_proceso Esperar_peticion(); Esperar_peticion(); Preparar_respuesta(); Preparar_respuesta(); Esperar_peticion(); Preparar_respuesta(); Enviar_respuesta(); Preparar_respuesta(); Enviar_respuesta(); Enviar_respuesta(); FIN_proceso FIN_proceso Enviar_respuesta(); FIN_proceso } } FIN_proceso } } } } } }
1.5
CASO : aplicación servidor Alternativa: procesos multiflujo
Permitir diferentes secuencias de ejecución simultáneas asociadas al mismo proceso
¿Qué necesitamos para describir una secuencia de ejecución?
Pila
Program counter
Valores de los registros
El resto de características del proceso puede ser única (resto del espacio lógico, información sobre los dispositivos, gestión signals, etc)
1.6
3
09/09/2014
Procesos vs. Flujos Los recursos se siguen asignando en su mayoría a los procesos:
Espacio de direcciones
Dispositivos
Pero el SO planifica a nivel de Flujo (cada flujo necesita 1 CPU)
Los flujos de un proceso comparten todos los recursos asignados al
proceso y todas las características
Y cada flujo tiene asociado:
Siguiente instrucción a ejecutar (valor del PC)
Zona de memoria para la pila
Estado de los registros
Un identificador
Proceso tradicional: un sólo flujo de ejecución
1.7
CASO : aplicación cliente-servidor Cliente 1 { .. Enviar_peticion(); Esperar_respuesta(); Procesar_respuesta(); … } Cliente 2 { .. Enviar_peticion(); Esperar_respuesta(); Procesar_respuesta(); … } Cliente N { .. Enviar_peticion(); Esperar_respuesta(); Procesar_respuesta(); … }
DATOS GLOBALES Servidor { While(){ INICIO_FLUJO INICIO_FLUJO Esperar_peticion(); Esperar_peticion(); Preparar_respuesta(); Preparar_respuesta(); Enviar_respuesta(); Enviar_respuesta(); FIN_FLUJO FIN_FLUJO } }
INICIO_FLUJO INICIO_FLUJO INICIO_FLUJO INICIO_FLUJO Esperar_peticion(); Esperar_peticion(); Esperar_peticion(); Esperar_peticion(); Preparar_respuesta(); Preparar_respuesta(); Preparar_respuesta(); Preparar_respuesta(); Enviar_respuesta(); Enviar_respuesta(); Enviar_respuesta(); Enviar_respuesta(); FIN_FLUJO FIN_FLUJO FIN_FLUJO FIN_FLUJO
1.8
4
09/09/2014
Internamente: Procesos vs. Flujos 1 proceso con N flujos 1 PCB
N secuencias del código del proceso que se pueden ejecutar de forma concurrente
En el PCB hay espacio para guardar los contextos de los N flujos
Descripción de memoria –
1 región de código
–
1 región de datos
–
1 región de heap + N pilas (1 por flujo)
1.9
Procesos vs. Flujos
1.10
5
09/09/2014
Internamente: Procesos vs. Flujos Compartición de memoria
Entre procesos
Por defecto la memoria es privada para un proceso y nadie la puede acceder (hay llamadas a sistema que permiten pedir zonas de memoria compartida entre procesos)
Entre flujos Todos los threads pueden acceder a todo el espacio lógico de la tarea a la que pertenecen
Cosas a tener en cuenta en la programación con threads – Cada thread tiene su pila propia donde el compilador reserva espacio para sus variables locales, parámetros, y control de su ejecución –
Todas las pilas también son visibles por todos los flujos
1.11
Utilización de procesos multiflujos Explotar paralelismo y concurrencia Mejorar la modularidad de las aplicaciones Aplicaciones intensivas en E/S
Flujos dedicados sólo a acceder a dispositivos
Aplicaciones servidores
1.12
6
09/09/2014
Ventajas de usar flujos Ventajas de usar varios flujos en lugar de varios procesos
Coste en tiempo de gestión: creación, destrucción y cambio de contexto
Aprovechamiento de recursos
Simplicidad del mecanismo de comunicación: memoria compartida
1.13
Gestión a nivel de usuario: Librerías de flujos Los kernels ofrecen threads, pero su interfaz no es compatible (en general)
como en el caso de los procesos, por eso se definió una interfaz implementada a nivel librería usuario. POSIX threads. POSIX threads (Portable Operating System Interface, definido por IEEE)
Interfaz de gestión de flujos a nivel de usuario
Creación y destrucción
Sincronización
Configuración de la planificación
El API de POSIX es muy potente, dependiendo del kernel la librería
implementa toda la funcionalidad o solo parte de ella
1.14
7
09/09/2014
Servicios de gestión de flujos
Creación
Procesofork() Flujos pthread_create(out Pth_id,in NULL, in function_name, in Pparam)
Identificación Procesos: getpid() Flujos : pthread_self() Finalización
Procesos: exit(exit_code) Flujos:pthread_exit(in Pthexit_code) Sincronización fin de flujo Procesos: waitpid(pid,ending_status, FLAGS)
Flujos:pthread_join(in thread_id, out PPexit_code) Consultad las páginas de man para ver los tipos de datos exactos
1.15
Creación de flujos pthread_create
Crea un nuevo flujo que ejecuta la rutina start_routine pasándole como parámetro arg
#include int pthread_create(pthread_t *th, pthread_attr_t *attr, void *(*start_routine)(void *), void *arg); th: contendrá el identificador del thread attr: características del thread (si NULL se le asignan las características por defecto) start_routine: @ de la rutina que ejecutará el nuevo flujo. Esa rutina puede recibir un sólo argumenteo de tipo void * (nombre de la función) arg: parámetro de la rutina Devuelve un código de error o 0 si ok
1.16
8
09/09/2014
Identificación del flujo pthread_self
Obtiene el identificador del flujo que la ejecuta
#include int pthread_self(void); Devuelve el identificador del thread
1.17
Destrucción de flujos pthread_exit
La ejecuta el flujo que acaba la ejecución
Se pasa como parámetro el valor de retorno del thread
#include int pthread_exit(void *status); status: valor de retorno del thread Devuelve un código de error o 0 si ok
1.18
9
09/09/2014
Sincronización con el fin de un flujo pthread_join Bloquea al flujo que la ejecuta hasta que el flujo indicado acabe y recoge el valor que ha pasado al pthread_exit Provoca la liberación de la estructura de datos asociada al flujo
#include int pthread_join(pthread_t th, void **status); th: identificador del thread al que se espera status: contendrá el parámetro que el flujo th le pasó al pthread_exit. Si NULL se ignora el parámetro del pthread_exit. Devuelve código de error o 0 si ok
1.19
Comunicación mediante memoria compartida Los flujos de un proceso pueden intercambiar información a través de la
memoria que comparten
Accediendo más de uno a las mismas variables
Problema que puede aparecer: condición de carrera (race condition)
Cuando el resultado de la ejecución depende del orden el que se alternen las instrucciones de los flujos (o procesos)
1.20
10
09/09/2014
Ejemplo: race condition int primero = 1 /* variable compartida */
/* flujo 1 */ If (primero) {
/* flujo 2 */ If (primero) { primero --
;
TAREA1
TAREA2
FLUJO 1
FLUJO 2
FLUJO 2
FLUJO 1
FLUJO 1 Y FLUJO 2
--
primero -;
tarea_1(); } else {
tarea_1(); } else {
tarea_2(); }
tarea_2(); }
RESULTADO INCORRECTO La idea del programador era utilizar este booleano para que se ejecutara primero la tarea1 y luego la 2 (pero cada una solo 1 vez) Lo que no tuvo en cuenta es que estas operaciones no son atómicas!!! 1.21
Que tenemos en ensamblador??? haz_tarea: pushl %ebp movl
%esp, %ebp
subl
$8, %esp
movl
primero, %eax
testl %eax, %eax je movl
primero, %eax
subl
$1, %eax
movl
%eax, primero
call jmp
Esto es la resta no es 1 instrucción
tarea1 .L5
.L2: call
Esto es el if no es 1 instrucción
.L2
tarea2
Esto es el else
.L5: leave ret
Que pasa si hay un cambio de contexto después del movl del if al thread 2??? 1.22
11
09/09/2014
¿Qué pasaría?…eax valdrá 1 al volver!! FLUJO 2
FLUJO 1 haz_tarea:
haz_tarea:
pushl %ebp
pushl %ebp
movl
%esp, %ebp
movl
%esp, %ebp
subl
$8, %esp
subl
$8, %esp
movl
primero, %eax
movl
primero, %eax
Cambio!
testl %eax, %eax
testl %eax, %eax
je
je
.L2
.L2
movl
primero, %eax
movl
primero, %eax
subl
$1, %eax
subl
$1, %eax
movl call jmp
%eax, primero tarea1
movl
Cambio!
call
.L5
jmp
.L2:
%eax, primero tarea1 .L5
.L2: call
tarea2
call
.L5:
tarea2
.L5: leave
leave
ret
ret
1.23
Región crítica Región crítica
Líneas de código que contienen condiciones de carrera que pueden provocar resultados erróneos
Líneas de código que acceden a variables compartidas cuyo valor cambia durante la ejecución
Solución
Garantizar el acceso en exclusión mutua a estas regiones de código
¿Evitar cambios de contexto?
1.24
12
09/09/2014
Exclusión mútua
Acceso en exclusión mutua: Se garantiza que el acceso a la región crítica es secuencial Mientras un flujo está ejecutando código de esa región ningún otro flujo lo hará (aunque haya cambios de contexto)
El programador debe: Identificar regiones críticas de su código Marcar inicio y fin de la región usando las herramientas del sistema
El sistema operativo ofrece llamadas a sistema para marcar inicio y fin de región crítica: Inicio: si ningún otro flujo ha pedido acceso a la región crítica se deja que continúe accediendo ,sino se hace que el flujo espere hasta que se libere el acceso a la región crítica Fin: se libera acceso a la región crítica y si algún flujo estaba esperando el permiso para acceder se le permite acceder
1.25
Interfaz pthreads Exc. mutua A considerar:
Cada región crítica se identifica con una variable (global) de tipo pthread_mutex_t, por lo tanto, necesitamos 1 variable de este tipo por región.
Antes de utilizarla, hay que inicializarla, por lo tanto, antes de crear los threads es lo ideal
Función
Descripción
pthread_mutex_init
Inicializa una variable de tipo pthread_mutex_t
pthread_mutex_lock
Bloquea el acceso a una región crítica
pthread_mutex_unlock
Libera el acceso a una región crítica
1.26
13
09/09/2014
Ejemplo: Mutex int primero = 1 /* variables compartida */ pthread_mutex_t rc1; // Nueva, también compartida pthread_mutex_init(& rc1,NULL); // INICIALIZAMOS LA VARIABLE, SOLO 1 VEZ ….. pthread_mutex_lock(& rc1); // BLOQUEO if (primero) { primero --; pthread_mutex_unlock (& rc1); //DESBLOQUEO
tarea_1(); } else { pthread_mutex_unlock(& rc1); //DESBLOQUEO
tarea_2(); }
1.27
Exclusión mútua: consideraciones Cosas que el programador debe tener en cuenta
Las regiones críticas deben ser lo más pequeñas posibles para maximizar la concurrencia
El acceso en exclusión mutua viene determinado por el identificador (variable) que protege el punto de entrada
No hace falta que tengan las mismas líneas de código
Si varias variables compartidas independientes puede ser conveniente protegerlas mediante variables diferentes
1.28
14