Post on 03-Oct-2015
2 - Procesos e hilos
ProcesosEs el concepto/abstraccin ms importante en los sist. op.Proporcionan la capacidad de operar (pseudo)concurrentementeToda computadora moderna puede hacer varias cosas a la vezDa al usuario la ilusin de paralelismo: muchos procesos corriendo al mismo tiempo:
Pseudoparalelismo -> una CPUMultiprocesadores -> varias CPUs
Procesos: El modelo de procesosUn proceso es un programa secuencial corriendo en una unidad de ejecucin (virtual o real) incluyendo los valores actuales del PC, registros, variables,...Cada proceso tiene su propia CPU virtual para ejecutarEn realidad la CPU conmuta de un proceso a otro
-> multiprogramacin=>Cuando el Sist. Op. realiza multiplexado temporal debe guardar
el estado del proceso:
registrospilaespacio de direccion.
file descriptorvariables de entornoseales
Procesos: El modelo de procesosEj: dos procesos corriendo en una mquina con una CPU
P1
Cant.
de
instr
uccio
nes
TiempoPeticina disco[P0]
Lectura a disco
Lo que ocurre en la mquina
P0
Procesos: El modelo de procesosEj: dos procesos corriendo en una mquina con una CPU
P1Ca
nt. d
e ins
truc
cione
sTiempo
Peticina disco[P0]
Fin detiempo
[P1]
Excede quantum
Lo que ocurre en la mquina
P0
Procesos: El modelo de procesosEj: dos procesos corriendo en una mquina con una CPU
P1
Cant.
de
instr
uccio
nes
TiempoPeticina disco[P0]
Fin detiempo
[P1]
Usode red[P0]
Envo de mensaje
Lo que ocurre en la mquina
P0
Procesos: El modelo de procesosEj: dos procesos corriendo en una mquina con una CPU
P1
Cant.
de
instr
uccio
nes
TiempoPeticina disco[P0]
Fin detiempo
[P1]
Usode red[P0]
Lo que ocurre en la mquina
P0
Procesos: El modelo de procesosEj: dos procesos corriendo en una mquina con una CPU
P1
Lo que uno ve
P0
Procesos: El modelo de procesosObservar:
La velocidad con que el proceso realiza su ejecucin no es uniformeEl orden en el que se intercalan las instrucciones de P0 y P1 no est definido
=>La forma en que se ejecutan ambos procesos no es fcilmente reproducible
Por consiguiente:
Los procesos no deben programarse con presuposiciones temporales
Procesos: El modelo de procesosObservar:
La velocidad con que el proceso realiza su ejecucin no es uniformeEl orden en el que se intercalan las instrucciones de P0 y P1 no est definido
=>La forma en que se ejecutan ambos procesos no es fcilmente reproducible
Por consiguiente:
Los procesos no deben programarse con presuposiciones temporales
Comparar con un programa secuencial/determinista
Procesos: El modelo de procesosObservar:
La velocidad con que el proceso realiza su ejecucin no es uniformeEl orden en el que se intercalan las instrucciones de P0 y P1 no est definido
=>La forma en que se ejecutan ambos procesos no es fcilmente reproducible
Por consiguiente:
Los procesos no deben programarse con presuposiciones temporales
Si fuera necesario (ej: sist. de tiempo real) se requieren medidas especiales y
sistemas operativos especiales
Procesos: CreacinSistemas simples -> Todos los procesos se crean al principioSistemas de propsitos generales
-> se necesita una forma de crear y terminar procesosCuatro eventos posibles determinan la creacin de un proceso:1. Inicializacin del sistema2.Un proceso en ejecucin realiza una
llamada al sistema para crear un nuevo proceso
3.El usuario pide crear un nuevo proceso4.Se inicia un nuevo trabajo en batch
Procesos: CreacinSistemas simples -> Todos los procesos se crean al principioSistemas de propsitos generales
-> se necesita una forma de crear y terminar procesosCuatro eventos posibles determinan la creacin de un proceso:1. Inicializacin del sistema2.Un proceso en ejecucin realiza una
llamada al sistema para crear un nuevo proceso
3.El usuario pide crear un nuevo proceso4.Se inicia un nuevo trabajo en batch
Al bootear, el SO crea muchos procesosForeground -> procesos que interactan directamente con el usuarioBackground:- no estn asociados a un usuario en particular- tienen funcionalidad especfica- daemons (mal traducidos como demonios)- Ej:- Proc. que acepta e-mail entrante- o que acepta solicitudes de requerimientos de pginas web (ej: apache)
- o que acepta conexiones entrantes de internet (ej: inetd)
- o el spooler de la impresora (ej: cupsd)
ps -ax
Procesos: CreacinSistemas simples -> Todos los procesos se crean al principioSistemas de propsitos generales
-> se necesita una forma de crear y terminar procesosCuatro eventos posibles determinan la creacin de un proceso:1. Inicializacin del sistema2.Un proceso en ejecucin realiza una
llamada al sistema para crear un nuevo proceso
3.El usuario pide crear un nuevo proceso4.Se inicia un nuevo trabajo en batch
Crear nuevos procesos para que colaboren entre ellos.Particularmente til si los procesos son bastante independientes entre s.Ej:
ls -R * | sort | uniq -d
Procesos: CreacinSistemas simples -> Todos los procesos se crean al principioSistemas de propsitos generales
-> se necesita una forma de crear y terminar procesosCuatro eventos posibles determinan la creacin de un proceso:1. Inicializacin del sistema2.Un proceso en ejecucin realiza una
llamada al sistema para crear un nuevo proceso
3.El usuario pide crear un nuevo proceso4.Se inicia un nuevo trabajo en batch
Sistemas interactivos:- doble click o- escribiendo un comando en una
terminalEn ambos casos se inicia un nuevo proceso y se ejecuta el proceso seleccionado
Procesos: CreacinSistemas simples -> Todos los procesos se crean al principioSistemas de propsitos generales
-> se necesita una forma de crear y terminar procesosCuatro eventos posibles determinan la creacin de un proceso:1. Inicializacin del sistema2.Un proceso en ejecucin realiza una
llamada al sistema para crear un nuevo proceso
3.El usuario pide crear un nuevo proceso4.Se inicia un nuevo trabajo en batch
Solo en sistemas batch (por lotes)Cuando el SO decide que tiene recursos suficientes para iniciar otro trabajo, crea un proceso y ejecuta el siguiente trabajo en la cola
Procesos: CreacinTcnicamente, en todos los casos un proceso existente efecta la llamada al sistema para crear un nuevo procesoEsta llamada al sistema
pide al SO crear un nuevo proceso eindica que programa correr sobre este
UNIX
Windows -> Slo una llamada: CreatProcess + 10 parmetrosEn ambos casos los espacios de direcciones de padre e hijo son disjuntos
forkexecve
->->
crea una copia exacta del proceso que llamallamada por el proceso hijo para ejecutar un nuevo programa
!"#
Procesos: CreacinTcnicamente, en todos los casos un proceso existente efecta la llamada al sistema para crear un nuevo procesoEsta llamada al sistema
pide al SO crear un nuevo proceso eindica que programa correr sobre este
UNIX
Windows -> Slo una llamada: CreatProcess + 10 parmetrosEn ambos casos los espacios de direcciones de padre e hijo son disjuntos
forkexecve
->->
crea una copia exacta del proceso que llamallamada por el proceso hijo para ejecutar un nuevo programa
!"#
incluyendo variables de entorno,
archivos abiertos, espacio de direccionamiento, etc.
Esto se hace para compartir.En particular permite compartir file descriptors y redireccionarlos apropiadamente antes del execve.
Ej: ls -R * | sort | uniq -d
Procesos: CreacinTcnicamente, en todos los casos un proceso existente efecta la llamada al sistema para crear un nuevo procesoEsta llamada al sistema
pide al SO crear un nuevo proceso eindica que programa correr sobre este
UNIX
Windows -> Slo una llamada: CreatProcess + 10 parmetrosEn ambos casos los espacios de direcciones de padre e hijo son disjuntos
forkexecve
->->
crea una copia exacta del proceso que llamallamada por el proceso hijo para ejecutar un nuevo programa
!"#
En UNIX, el espacio de direccionamiento se copia.
(En algunos UNIX: copy on write)
En Windows, los espacios de direccionamiento del padre y del hijo
son distintos.
Procesos: Terminacin
involuntaria
Normal:Ej: exit(0), Quit del men
Errnea:Ej: gcc test.c, pero test.c no existe -> exit(4)
voluntaria
Error causado por el proceso:Ej: divisin por 0, referencia a una dir. de mem. inexistente
Matado por otro proceso: killEj: killall mozilla.bin.
Terminacin
Procesos: JerarquaUNIX:
Jerrquico: se mantiene la estructura padre-hijo segn creacinVer con pstreeTiene cierta utilidad para manejar grupo de procesos
Windows:No hay jerarquaSlo existe un token especial (handle) que se retorna al padre en la creacin, pero este puede cederlo a otro proceso
Procesos: JerarquaUNIX:
Jerrquico: se mantiene la estructura padre-hijo segn creacinVer con pstreeTiene cierta utilidad para manejar grupo de procesos
Windows:No hay jerarquaSlo existe un token especial (handle) que se retorna al padre en la creacin, pero este puede cederlo a otro proceso
dargenio@russell:~$ pstreeinit!"!acpid #!apache2!!!10*[apache2] #!3*[automount] #!cron #!dnsmasq #!fail2ban-server!!!8*[{fail2ban-serve}] #!6*[getty] #!klogd #!mailmanctl!!!8*[python] #!master!"!pickup $ #!qmgr $ %!tlsmgr #!mysqld_safe!"!logger $ %!mysqld!!!17*[{mysqld}] #!portmap #!rpc.idmapd #!rpc.mountd #!rpc.statd #!rpc.yppasswdd #!rpc.ypxfrd #!sensord #!sshd!"!sshd!!!sshd!!!bash!!!ssh $ %!sshd!!!sshd!!!bash!!!pstree #!syslogd #!udevd!!!2*[udevd] #!ypbind!!!2*[{ypbind}] %!ypserv
Procesos: Estado de los procesosSupongamos dos procesos que estn interactuando entre sEj: cat cap1.txt cap2.txt cap2.txt | grep abracadabraSi cat produce ms lento de lo que grep consume,
grep debe esperar aunque la CPU est a su disposicinEn este caso grep queda bloqueado.Un proceso que est listo para ejecutar puede que no lo haga porque hay otro proceso haciendo uso de la CPU.Notar:
bloqueado ! listo
Suspensin inherente al problema
Tecnicalidad del sistema(#CPU < #proc. listos p/ejecutar)
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particular
Ejecutando
Bloqueado Listo
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particularEl proceso en ejecucin requiere algn evento para
continuar (ej: el arribo de un dato de entrada)
Ejecutando
Bloqueado Listo
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particular
El scheduler determina que el proceso
en ejecucin debe dejar la CPU (ej: se acab el quantum)
Ejecutando
Bloqueado Listo
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particular
La CPU se libera y un proceso en la cola de listos
retoma la ejecucin. El criterio para elegir el proceso en la cola de listos depende de la poltica
de scheduling.Ejecutando
Bloqueado Listo
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particularSe produjo el evento esperado. El
proceso est ahora listo para ejecutar (ej: ya se produjo la entrada) Ejecutando
Bloqueado Listo
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particular
Lgicamente, los estados ejecutando y listo son similares: en ambos casos el
proceso est dispuesto a ejecutar
En cambio, si el proceso est bloqueado,
ste no puede ejecutar an si la CPU est ociosa.
Ejecutando
Bloqueado Listo
Procesos: Estado de los procesosUn proceso puede estar en 3 estados:
Ejecutando: usando la CPU en este instanteListo: puede ejecutarse pero no hay CPU disponibleBloqueado: imposibilitado de ejecutar hasta la ocurrencia de algn evento particular
Ejecutando
Bloqueado Listo
La forma en la que se administran estas
dos transiciones es tarea del planificador de procesos o
scheduler
Procesos: Estado de los procesosModelo en capas
Procesos
Scheduler
Procesos: ejecutan programas de usuarios, o son parte
del sistema y se encargan de brindar servicios a los programas usuarios o
de administrar recursos
Scheduler (o Planificador): da la ilusin de mltiples CPU
Procesos: ImplementacinSe implementa a travs de tablas de procesosTabla de procesos -> arreglos o listas:
una entrada por procesocada entrada es un bloque de control de proceso (PCB: process control block)el PCB contiene la info del estado del proceso->Todo lo que necesita guardarse cuando el proceso cambia de
ejecutando a listo o bloqueado para luego poder recomenzar a ejecutar como si nunca hubiera sido detenido
Procesos: ImplementacinContenido tpico del PCB
Depende del procesador y del sistema
operativo
Hilos (Threads)Sistemas operativos tradicionales->cada proceso tiene un espacio de dir. y un slo hilo de controlHay situaciones en las que es conveniente tener varios hilos de ejecucin en el mismo espacio de direccionamiento.Como si fueran procesos (casi) separados excepto que comparten el espacio de direccionamiento.
Por qu queremos esto?Ejemplos?
Hilos: UsoPor qu queremos hilos?Para manejar muchas actividades al mismo tiempo
Y no tenemos a los procesos para esto?
Hilos: UsoPor qu queremos hilos?Para manejar muchas actividades al mismo tiempo
Adems:Permite computar concurrentemente compartiendo datosComo comparten (casi) todo:
es mucho ms simple crear y destruir hilosel context switch es mucho ms rpido que en los procesos
Ejecutan con mejor desempeo si hay mucha actividad I/O bound (permite solapar actividades)Si hay mltiples CPUs => verdadero paralelismo
hasta 100 veces ms rpido que en procesos
Hilos: UsoPor qu queremos hilos?Para manejar muchas actividades al mismo tiempo
Adems:Permite computar concurrentemente compartiendo datosComo comparten (casi) todo:
es mucho ms simple crear y destruir hilosel context switch es mucho ms rpido que en los procesos
Ejecutan con mejor desempeo si hay mucha actividad I/O bound (permite solapar actividades)Si hay mltiples CPUs => verdadero paralelismo
hasta 100 veces ms rpido que en procesos
Ej: Word podra manipular 5 hilos simultneamente:1. prepaginado2. impresin3. spell checking4. backup automtico5. hilo principal
Hilos: UsoPor qu queremos hilos?Para manejar muchas actividades al mismo tiempo
Adems:Permite computar concurrentemente compartiendo datosComo comparten (casi) todo:
es mucho ms simple crear y destruir hilosel context switch es mucho ms rpido que en los procesos
Ejecutan con mejor desempeo si hay mucha actividad I/O bound (permite solapar actividades)Si hay mltiples CPUs => verdadero paralelismo
hasta 100 veces ms rpido que en procesos
Ej: Word podra manipular 5 hilos simultneamente:1. prepaginado2. impresin3. spell checking4. backup automtico5. hilo principal
Ej: Servidor web de algn sitio.idea simple: tener una cach en memoria con las pginas solicitadas ms frecuentemente
Hilos: UsoPor qu queremos hilos?Para manejar muchas actividades al mismo tiempo
Adems:Permite computar concurrentemente compartiendo datosComo comparten (casi) todo:
es mucho ms simple crear y destruir hilosel context switch es mucho ms rpido que en los procesos
Ejecutan con mejor desempeo si hay mucha actividad I/O bound (permite solapar actividades)Si hay mltiples CPUs => verdadero paralelismo
hasta 100 veces ms rpido que en procesos
Ej: Word podra manipular 5 hilos simultneamente:1. prepaginado2. impresin3. spell checking4. backup automtico5. hilo principal
Ej: Servidor web de algn sitio.idea simple: tener una cach en memoria con las pginas solicitadas ms frecuentemente
Hilos: El modelo de hilosEl modelo de procesos se basa en dos conceptos independientes:
agrupacin de recursosejecucin
Podramos enfocarnos slo en el hilo de ejecucin del procesoPara el hilo de ejecucin slo es relevante:
el contador del programa,los registros de la CPU, yla pila de ejecucin
Hilos: El modelo de hilosEl modelo de procesos se basa en dos conceptos independientes:
agrupacin de recursosejecucin
Podramos enfocarnos slo en el hilo de ejecucin del procesoPara el hilo de ejecucin slo es relevante:
el contador del programa,los registros de la CPU, yla pila de ejecucin
registra cual es la instruccin que se ejecutar a
continuacin
contiene las variables de trabajo actuales
contiene el historial de llamadas a procedimientos pendientes a
lo largo de la ejecucin
los recursos que el proceso necesita para
funcionarHilos: El modelo de hilos
El modelo de procesos se basa en dos conceptos independientes:agrupacin de recursosejecucin
Podramos enfocarnos slo en el hilo de ejecucin del procesoPara el hilo de ejecucin slo es relevante:
el contador del programa,los registros de la CPU, yla pila de ejecucin
los recursos que el proceso necesita para
funcionar
El hilo y su proceso son conceptos distintos y pueden tratarse por separado
Hilos: El modelo de hilos
Los procesos se usan para para agrupar recursosLos hilos son las entidades planificadas para ejecutar en la CPU
=>Los hilos permiten mltiples ejecuciones en un nico proceso dentro del mismo entorno del proceso.
El hilo y su proceso son conceptos distintos y pueden tratarse por separado
n hilos en 1 procesoes comparable a
n procesos en 1 CPU
los hilos comparten espacio de direcciones,
archivos, etc.
los procesos comparten mem. fsica, disco,
y otros recursos.
Hilos: El modelo de hilos
Los procesos se usan para para agrupar recursosLos hilos son las entidades planificadas para ejecutar en la CPU
=>Los hilos permiten mltiples ejecuciones en un nico proceso dentro del mismo entorno del proceso.
El hilo y su proceso son conceptos distintos y pueden tratarse por separado
n hilos en 1 procesoes comparable a
n procesos en 1 CPU
Hilos: El modelo de hilosLos hilos alternan su ejecucin de la misma manera que los procesos
=> mismo diagrama de estados
Cul es entonces la diferencia?
Ejecutando
Bloqueado Listo
Los hilos comparten Exclusivo de cada hiloEspacio de direccionamiento Contador de programaVariables globales RegistrosArchivos abiertos PilaProcesos hijos EstadoAlarmas pendientesSeales y manejadores de sealesInformacin administrativa
Hilos: El modelo de hilosLos hilos alternan su ejecucin de la misma manera que los procesos
=> mismo diagrama de estados
Cul es entonces la diferencia?
Ejecutando
Bloqueado Listo
Los hilos comparten Exclusivo de cada hiloEspacio de direccionamiento Contador de programaVariables globales RegistrosArchivos abiertos PilaProcesos hijos EstadoAlarmas pendientesSeales y manejadores de sealesInformacin administrativa
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = ? }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = ? }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 2 }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 2 }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 2 }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
P0: x := x+1;
P1: x := x+1;
{ x = 0 }
{ x = ? }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
Estas instrucciones pueden no realizarse de
manera atmica (indivisible)
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = ?x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = 0x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = 1x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = 1x = 1
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = ?x = 1
El scheduler cambia de proceso
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = 1x = 1
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = 2x = 1
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }
{ x = ? }
MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
AX = 2x = 2
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = ?x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = 0x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = 1x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = ?x = 0
EL SCHEDULER DECIDE CAMBIAR DE PROCESO
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = 0x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = 1x = 0
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = 1x = 1
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 2 }
AX = 1x = 1
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 1 }
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 1 x = 2}
Hilos: El modelo de hilos
P0: x := 1;
P1: x := 2;
{ x = 0 }
{ x = 1 x = 2}
Esto se denomina condicin de carrera
{ x = 0 }MOV AX, xADD AX, 1MOV x, AX
MOV AX, xADD AX, 1MOV x, AX
{ x = 1 x = 2}
Conclusin:el scheduler es MANDINGA
en persona!!
Hilos: El modelo de hilos
P0: x := 2; x := x+2;
P1: x := 1; x := x+1;
{ x = 0 }
{ x = ? }
Cul es la postcondicin si las instrucciones son atmicas?
Y si no lo son?
Queda como ejercicio
Hilos: El modelo de hilosPor lo tanto: No hay proteccin entre hilosPorque:
1. es imposible, y2. no debera ser necesario!
Mientras que los procesos son hostiles entre ellos, compitiendo por recursos,los hilos cooperan entre s para llevar a cabo una tarea comn.Para lograr una cooperacin adecuada los hilos necesitan sincronizarse apropiadamente
Lo posponemos para la prxima clase
Hilos: El modelo de hilosEs importante tener en cuenta que cada hilo tiene su propia pilaSi esto no fuera as entonces estamos en problemas:
P0: call Foo(x);
P1: call Faa(y);
Pila
Hilos: El modelo de hilosEs importante tener en cuenta que cada hilo tiene su propia pilaSi esto no fuera as entonces estamos en problemas:
P0: call Foo(x);
P1: call Faa(y);
xdir ret Foo
Pila
1. P0 llama al procedimiento Foo(x)2.CS durante la ejecucin de Foo
* CS = Context Switch
Hilos: El modelo de hilosEs importante tener en cuenta que cada hilo tiene su propia pilaSi esto no fuera as entonces estamos en problemas:
P0: call Foo(x);
P1: call Faa(y); y
dir ret Faax
dir ret FooPila
1. P0 llama al procedimiento Foo(x)2.CS durante la ejecucin de Foo3.P1 llama al procedimiento Faa(y)4.CS durante la ejecucin de Faa
* CS = Context Switch
Hilos: El modelo de hilosEs importante tener en cuenta que cada hilo tiene su propia pilaSi esto no fuera as entonces estamos en problemas:
P0: call Foo(x);
P1: call Faa(y); y
dir ret Faax
dir ret Foo1. P0 llama al procedimiento Foo(x)2.CS durante la ejecucin de Foo3.P1 llama al procedimiento Faa(y)4.CS durante la ejecucin de Faa5.El proc. Foo finaliza y retorna
Pila
Cmo queda la pila ahora?* CS = Context Switch
Hilos: El modelo de hilosEs importante tener en cuenta que cada hilo tiene su propia pilaSi esto no fuera as entonces estamos en problemas:
P0: call Foo(x);
P1: call Faa(y);
xdir ret Foo
Pila P0
ydir ret Faa
Pila P1
La historia de la ejecucin es local a cada hilo
Hilos: El modelo de hilosOperaciones:
thread_create
thread_exit
thread_join
thread_yield
Crea un nuevo hilo (usualmente con un parmetro)Habitualmente no hay relacin padre-hijoRetorna un identificador del nuevo hilo.
Termina el hilo llamante
Espera hasta que un hilo especfico (dado como parmetro) termine
Se entrega voluntariamente al scheduler dando la posibilidad a otros hilos de ejecutar
Hilos: El modelo de hilosProblemas:
si un hilo de un proceso con mltiples hilos hace un fork, el proceso hijo deber tambin tener los mismos mltiples hilos?
si no => no funcionar como el padresi s => qu pasara con los hilos bloqueados a la espera de una entrada (ej: de teclado o de red)?
Estructuras de datos compartidas. Ej: Qu pasara si un hilo cierra un archivo mientras otro hilo an lo est leyendo?Funciones de biblioteca no reentrantes
Hilos: Implementacin en espacio de usuario
Una biblioteca se encarga de manipular los hilos:
Tabla de hilos (PC, SP, registros, estado, etc.)Sistema en tiempo de ejecucin (Run-time system)
Si un hilo se bloquea => llama al run-time syst.El run-time syst. planifica entonces un nuevo hilo y se encarga del cambio de contexto
El scheduler no sabe de la existencia de mltiples hilos y maneja al proceso de la misma manera que si tuviera un slo hilo
Hilos: Implementacin en espacio de usuarioVentajas:
Se puede implementar en cualquier SO (no necesita soportar hilos)No necesita de trap al kernel para cambiar de hiloContext switch de hilos es muy rpidoSchedulers customizados
Desventajas:Llamadas bloqueantes: si es una syst. call directa=> trap al kernel y cambio de proceso: Inaceptable
Usar jackets/wrappers sobre la syst. call:- hacen uso de la syst. call select- requiere de reimplementacin de partes de las bibliotecas
Como no hay interrupciones de reloj es imprescindible la entrega voluntaria del control (thread_yield)
Problema semejante si ocurre un
fallo de pgina
Hilos: Implementacin en espacio de kernel
Creacin/terminacin de hilos a travs de syst. calls al kernelToda llamada potencialmente bloqueante debe implementarse por medio de syst. calls al kernelCuando un hilo se bloquea, el kernel puede elegir si continuar con un hilo del mismo proceso o de otroLas desventajas de antes desaparecenPero los costos de los syst. calls son sustancialmente mayores
Una nica tabla de hilos (en lugar de una por proceso)Misma informacin que antes pero en espacio de kernel
Hilos: Implementacin en espacio de kernel
Creacin/terminacin de hilos a travs de syst. calls al kernelToda llamada potencialmente bloqueante debe implementarse por medio de syst. calls al kernelCuando un hilo se bloquea, el kernel puede elegir si continuar con un hilo del mismo proceso o de otroLas desventajas de antes desaparecenPero los costos de los syst. calls son sustancialmente mayores
Una nica tabla de hilos (en lugar de una por proceso)Misma informacin que antes pero en espacio de kernelImplementacin
en espacio de usuario: el run-time system continuar ejecutando hilos del mismo proceso hasta que se acaben
los hilos disponibles o el kernel le quite la CPU
Comunicacin entre procesosPara qu?
compartir ysincronizar
Tres cosas involucradas:Como hacer transferencia de info. entre procesos (o hilos)Asegurar que los procesos no se molesten cuando realizan ciertas actividades crticasAsegurar la secuencialidad apropiada cuando haya dependencias
Lo que veremos a continuacin asume memoria compartida pero se aplica tambin a procesos (los procesos tambin pueden compartir recursos!)
Comunicacin entre procesosPara qu?
compartir ysincronizar
Tres cosas involucradas:Como hacer transferencia de info. entre procesos (o hilos)Asegurar que los procesos no se molesten cuando realizan ciertas actividades crticasAsegurar la secuencialidad apropiada cuando haya dependencias
Lo que veremos a continuacin asume memoria compartida pero se aplica tambin a procesos (los procesos tambin pueden compartir recursos!)
Fcil
Ej: dos puntos de ventas vendiendo el ltimo
pasaje de avin
Ej: Un proc. produce info. que otro debe imprimir.
Menos obvio
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
4 J15 J26 J3789
out = 4in = 7
Buffer circular
Qu hace esto?Anda bien?
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
4 J15 J26 J3789
out = 4in = 7
Buffer circular
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Cmo termina la ejecucin?
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
out = 4in = 7
Buffer circular
4 J15 J26 J37 J489
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Cmo termina la ejecucin?
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
out = 4in = 7
Buffer circular
4 J15 J26 J37 J589
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Cmo termina la ejecucin?
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
Buffer circular
out = 4in = 8
4 J15 J26 J37 J589
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Cmo termina la ejecucin?
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
Buffer circular
out = 4in = 9
4 J15 J26 J37 J58 Basura9
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Cmo termina la ejecucin?
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
Buffer circular
out = 4in = 9
4 J15 J26 J37 J58 Basura9
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Hola. Soy yo, MANDINGA.
Otra vez
Comunicacin e/proc.: Condiciones de carreraEj: Spooler de la impresora
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }
struct spl { buf : *job[MAX]; out : int; in: int; }Proc_A: ...A1: spl->buf[in] = J4;A2: spl->in ++; ...
Proc_B: ...B1: spl->buf[in] = J5;B2: spl->in ++; ...
Buffer circular
out = 4in = 9
4 J15 J26 J37 J58 Basura9
Consideremos la secuencia de planificacin:A1 B1 B2 A2
Una condicin de carrera es una situacin donde dos o ms proceso (o hilos)
deben leer o escribir en un rea compartida y el resultado final depende de qu proceso
ejecuta y cundo lo hace
Debuggear programas con condiciones de carrera es extremadamente frustrante.
Debido al no-determinismo, los test corren bien la mayora de las veces y los errores son muy
difciles de reproducir.
Hola. Les dije que soy
MANDINGA?
Comunicacin e/proc.: Regiones crticasCmo evitar las condiciones de carrera?=> Prohibir que ms de un proceso acceda al recurso compartido al
mismo tiempoEs decir: Se necesita exclusin mutua:
Si un proc. accede al recurso compartido los otros quedan excluidos.La parte del programa que accede al recurso compartido se denomina regin crtica.
Comunicacin e/proc.: Regiones crticasCmo evitar las condiciones de carrera?=> Prohibir que ms de un proceso acceda al recurso compartido al
mismo tiempoEs decir: Se necesita exclusin mutua:
Si un proc. accede al recurso compartido los otros quedan excluidos.La parte del programa que accede al recurso compartido se denomina regin crtica.
Ej: la variable compartida, el spooler de la impresora.
P0: do true -> RNC0 Inicio RC0 RC0 Fin RC0 od
P1: do true -> RNC1 Inicio RC1 RC1 Fin RC1 od
Tpicamente analizaremos programas con esta pinta.La idea es tratar de construir el cdigo que implemente Inicio RC y Fin RC para asegurar exclusin mutua de las RCi
Comunicacin e/proc.: Regiones crticasCmo evitar las condiciones de carrera?=> Prohibir que ms de un proceso acceda al recurso compartido al
mismo tiempoEs decir: Se necesita exclusin mutua:
Si un proc. accede al recurso compartido los otros quedan excluidos.La parte del programa que accede al recurso compartido se denomina regin crtica.
Ej: la variable compartida, el spooler de la impresora.
P0: do true -> RNC0 Inicio RC0 RC0 Fin RC0 od
P1: do true -> RNC1 Inicio RC1 RC1 Fin RC1 od
Tpicamente analizaremos programas con esta pinta.La idea es tratar de construir el cdigo que implemente Inicio RC y Fin RC para asegurar exclusin mutua de las RCi
Una solucin obvia es no permitir a ningn proceso entrar a la regin crtica, o que slo uno
tenga derecho a hacerlo.
!!!???
Comunicacin e/proc.: Regiones crticasPara obtener una buena solucin se necesitan las siguientes cuatro condiciones:1. A lo sumo un proceso est dentro
de la RC2.No hace suposiciones respecto de la
velocidad de la CPU3.Ningn proceso fuera de su RC
puede bloquear el acceso de otro proceso a su RC
4.Un proceso que desee entrar a su RC deber hacerlo en algn momento.
Comunicacin e/proc.: Regiones crticasPara obtener una buena solucin se necesitan las siguientes cuatro condiciones: Requerimiento de seguridad (safety - nada malo va a pasar)
Ya lo vimos
Requerimiento de progreso
Requerimiento de equidad(fairness)
1. A lo sumo un proceso est dentro de la RC
2.No hace suposiciones respecto de la velocidad de la CPU
3.Ningn proceso fuera de su RC puede bloquear el acceso de otro proceso a su RC
4.Un proceso que desee entrar a su RC deber hacerlo en algn momento.
Comunicacin e/proc.: Regiones crticasPara obtener una buena solucin se necesitan las siguientes cuatro condiciones: Requerimiento de seguridad (safety - nada malo va a pasar)
Ya lo vimos
Requerimiento de progreso
Requerimiento de equidad(fairness)
1. A lo sumo un proceso est dentro de la RC
2.No hace suposiciones respecto de la velocidad de la CPU
3.Ningn proceso fuera de su RC puede bloquear el acceso de otro proceso a su RC
4.Un proceso que desee entrar a su RC deber hacerlo en algn momento. Requerimientos de vitalidad
(liveness - algo bueno va a pasar)
Comunicacin e/proc.: Regiones crticasPara obtener una buena solucin se necesitan las siguientes cuatro condiciones: Requerimiento de seguridad (safety - nada malo va a pasar)
Ya lo vimos
Requerimiento de progreso
Requerimiento de equidad(fairness)
1. A lo sumo un proceso est dentro de la RC
2.No hace suposiciones respecto de la velocidad de la CPU
3.Ningn proceso fuera de su RC puede bloquear el acceso de otro proceso a su RC
4.Un proceso que desee entrar a su RC deber hacerlo en algn momento. Requerimientos de vitalidad
(liveness - algo bueno va a pasar)
Cmo logramos esto?
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Deshabilitar interrupciones:Inicio RC = CLI (clear interrupt)Fin RC = STI (set interrupt)
Sin interrupciones nadie puede detener al proceso. En particularno hay interrupciones de reloj (no hay quantum que valga!)no hay interrupciones de solicitud a disco
Problemas:Qu pasa si un proc. no hace Fin RC? y si quiere hacer E/S?Si hay ms de una CPU el mtodo no andaNo permite la ejecucin de las RNC de los otros procesos
P0: do true -> RNC0 CLI RC0 STI od
P1: do true -> RNC1 CLI RC1 STI odFunciona?
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Deshabilitar interrupciones:Inicio RC = CLI (clear interrupt)Fin RC = STI (set interrupt)
Sin interrupciones nadie puede detener al proceso. En particularno hay interrupciones de reloj (no hay quantum que valga!)no hay interrupciones de solicitud a disco
Problemas:Qu pasa si un proc. no hace Fin RC? y si quiere hacer E/S?Si hay ms de una CPU el mtodo no andaNo permite la ejecucin de las RNC de los otros procesos
P0: do true -> RNC0 CLI RC0 STI od
P1: do true -> RNC1 CLI RC1 STI od
Esto slo es conveniente para el kernel, por ej: durante la actualizacin de la
cola de listos del scheduler
Viola equidad, seguridad (si CPU>1), y tantas otras cosas
No funciona
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Variable candado:Init:Inicio RC:
Fin RC:
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0: do true -> A1 RNC0 A2 do (lock==1) -> skip od A3 lock = 1 A4 RC0 A5 lock = 0 od
P1: do true -> B1 RNC1 B2 do (lock==1) -> skip od B3 lock = 1 B4 RC1 B5 lock = 0 od
lock = 0do (lock == 1) -> skip odlock = 1lock = 0
(Intento de) solucin por software
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Variable candado:Init:Inicio RC:
Fin RC:
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0: do true -> A1 RNC0 A2 do (lock==1) -> skip od A3 lock = 1 A4 RC0 A5 lock = 0 od
P1: do true -> B1 RNC1 B2 do (lock==1) -> skip od B3 lock = 1 B4 RC1 B5 lock = 0 od
lock = 0do (lock == 1) -> skip odlock = 1lock = 0
Funciona?
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Variable candado:Init:Inicio RC:
Fin RC:
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0: do true -> A1 RNC0 A2 do (lock==1) -> skip od A3 lock = 1 A4 RC0 A5 lock = 0 od
P1: do true -> B1 RNC1 B2 do (lock==1) -> skip od B3 lock = 1 B4 RC1 B5 lock = 0 od
lock = 0do (lock == 1) -> skip odlock = 1lock = 0
Contraejemplo: A1 B1 A2 B2 A3 B3 A4 B4
No funciona
Viola seguridad (condicin 1)
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Alternancia estricta:Init:Inicio RC:Fin RC:
{ turn == 0 }{ turn == 0 }{ turn == 0 }P0: do true -> A1 RNC0 A2 do (turn!=0) -> skip od A3 RC0 A4 turn = (turn + 1) % 2 od
P1: do true -> B1 RNC1 B2 do (turn!=1) -> skip od B3 RC1 B4 turn = (turn + 1) % 2 od
turn = 0do (turn != ID) -> skip odturn = (turn+1)%CANT_PROC
Funciona?
Usa una variable turn para alternar los turnos en que los
procesos acceden a la RC
Se puede ver que garantiza la exclusin
mutua (cond. 1)
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Alternancia estricta:Init:Inicio RC:Fin RC:
{ turn == 0 }{ turn == 0 }{ turn == 0 }P0: do true -> A1 RNC0 A2 do (turn!=0) -> skip od A3 RC0 A4 turn = (turn + 1) % 2 od
P1: do true -> B1 RNC1 B2 do (turn!=1) -> skip od B3 RC1 B4 turn = (turn + 1) % 2 od
turn = 0do (turn != ID) -> skip odturn = (turn+1)%CANT_PROC
Funciona?
Viola progreso (cond. 3)
Usa una variable turn para alternar los turnos en que los
procesos acceden a la RC
Se puede ver que garantiza la exclusin
mutua (cond. 1)
Consideremos la secuencia:A1 A2 A3 A4 A1 A2 A2 A2 B1 (tarda y se acaba el quantum) A2 A2 A2 ...
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Alternancia estricta:Init:Inicio RC:Fin RC:
{ turn == 0 }{ turn == 0 }{ turn == 0 }P0: do true -> A1 RNC0 A2 do (turn!=0) -> skip od A3 RC0 A4 turn = (turn + 1) % 2 od
P1: do true -> B1 RNC1 B2 do (turn!=1) -> skip od B3 RC1 B4 turn = (turn + 1) % 2 od
turn = 0do (turn != ID) -> skip odturn = (turn+1)%CANT_PROC
Consideremos la secuencia:A1 A2 A3 A4 A1 A2 A2 A2 B1 (tarda y se acaba el quantum) A2 A2 A2 ...
Busy waiting
Debera evitarse: desperdicia CPU
Locks que usan busy waiting se llaman
spin locks
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Algoritmo de Peterson:En 1959, Edsger W. Dijkstra plante el problema de exclusin mutua en el Departamento de Computacin del Matematisch Centrum (Amsterdam).
Bsicamente solicitaba las mismas condiciones que planteamos antes.Los colegas proponan soluciones que Dijkstra demostraba incorrectasCada nueva solucin era ms compleja y a Dijkstra le costaba ms encontrar los contraejemplosHasta que Dijkstra se pudri y cambi las reglas: quien trajera una solucin deba tambin traer la demostracin de su correccinTheodorus J. Dekker propuso entonces una solucin para 2 procesos con demostracin y todo
Mezclaba la idea de locks y turno de los algoritmos anterioresEn 1965, Dijkstra la pudo generalizar a N procesosEn 1981, G.L. Peterson simplific este algoritmo
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Algoritmo de Peterson:En 1959, Edsger W. Dijkstra plante el problema de exclusin mutua en el Departamento de Computacin del Matematisch Centrum (Amsterdam).
Bsicamente solicitaba las mismas condiciones que planteamos antes.Los colegas proponan soluciones que Dijkstra demostraba incorrectasCada nueva solucin era ms compleja y a Dijkstra le costaba ms encontrar los contraejemplosHasta que Dijkstra se pudri y cambi las reglas: quien trajera una solucin deba tambin traer la demostracin de su correccinTheodorus J. Dekker propuso entonces una solucin para 2 procesos con demostracin y todo
Mezclaba la idea de locks y turno de los algoritmos anterioresEn 1965, Dijkstra la pudo generalizar a N procesosEn 1981, G.L. Peterson simplific este algoritmo
And then something profound and lovely happened. By analyzing by what structure of argument the proof obligations could be met, Dekker designed within a few
hours the solution together with its correctness argument
An no existan las tcnicas de clculo de programa o de verificacin!
(R.W. Floyd introduce el primer clculo para programas secuenciales en 1967)
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Algoritmo de Peterson (para 2 procesos):
{ turn == 0 && want == [false, false] }{ turn == 0 && want == [false, false] }{ turn == 0 && want == [false, false] }P0:do true -> RNC0 want[0] = true turn = 1 do (want[1] && turn==1) -> skip od RC0 want[0] = falseod
P1:do true -> RNC1 want[1] = true turn = 0 do (want[0] && turn==0) -> skip od RC1 want[1] = falseod
Init: turn = 0; want = [false, false]Inicio RC: want[i] = true
turn = 1-ido (want[1-i] && turn==1-i) -> skip od
Fin RC: want[i] = false
turn contiene el nro de proceso que tiene prioridad
want[i] indica si el proceso i quiere ingresar a la RC
Funciona
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Algoritmo de Peterson (para 2 procesos):
{ turn == 0 && want == [false, false] }{ turn == 0 && want == [false, false] }{ turn == 0 && want == [false, false] }P0:do true -> RNC0 want[0] = true turn = 1 do (want[1] && turn==1) -> skip od RC0 want[0] = falseod
P1:do true -> RNC1 want[1] = true turn = 0 do (want[0] && turn==0) -> skip od RC1 want[1] = falseod
Init: turn = 0; want = [false, false]Inicio RC: want[i] = true
turn = 1-ido (want[1-i] && turn==1-i) -> skip od
Fin RC: want[i] = false
Lgica de Owicki-Gries: provee una forma de razonar semejante a la lgica de Hoare (pero para programas concurrentes)
[OPT: Programacin Concurrente, Blanco&Wolovick]
Programas de estado finito como este pueden verificarse
automticamente (ej: model checking)[Ingeniera del software II]
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Algoritmo de Peterson:Ejercicios:
Observar que no sufre de retraso innecesario como el de alternancia estricta. Mostrar que P0 puede entrar varias veces aunque P1 no progrese.El algoritmo es muy delicado: intercambiar las asignaciones en Inicio RCarruina el algoritmo => dar una ejecucion que lo muestreDar una demostracin de que este algoritmo funciona [Difcil!!]Generalizar a N procesos
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Instruccin Test & Set Lock (TSL):La solucin de la variable candado no funciona porque el scheduler puede interrumpir entre inspeccin y cerrado del candado.Si las dos operaciones se realizaran de manera atmica (indivisible)
=> S funcionaraEsto requiere de una ayuda del hardware (y van...):
TSL RX, lock RX ! locklock ! 1registro memoria
La CPU garantiza que el scheduler no interrumpe entre medio
de la ejecucin de ambas instrucciones
{
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Instruccin Test & Set Lock (TSL):Init: lock = 0Inicio RC: do test_set(&lock) -> skip odFin RC: lock = 0
En C sera algo como:int test_set(int *lock) { register int rx; asm(TSL rx, lock); return( rx );}
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0:do true -> RNC0 do test_set(&lock) -> skip od RC0 lock = 0od
P1:do true -> RNC1 do test_set(&lock) -> skip od RC1 lock = 0od
Con N procesos se resuelve de la misma
manera
Instruccin Test & Set Lock (TSL):Supongamos que hay dos regiones crticas donde en una se modifica la tabla de procesos y en la otra los files descriptors:
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0:do true -> ... do test_set(&lock) -> skip od p.id = tb_alloc(proc_tb,pcb) lock = 0 ... do test_set(&lock) -> skip od fd = tb_get(fd_tb,fid) lock = 0 ...od
P1:do true -> ... do test_set(&lock) -> skip od p.id = tb_alloc(proc_tb,pcb) lock = 0 ... do test_set(&lock) -> skip od fd = tb_get(fd_tb,fid) lock = 0 ...od
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Qu observan?
Instruccin Test & Set Lock (TSL):Supongamos que hay dos regiones crticas donde en una se modifica la tabla de procesos y en la otra los files descriptors:
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0:do true -> ... do test_set(&lock) -> skip od p.id = tb_alloc(proc_tb,pcb) lock = 0 ... do test_set(&lock) -> skip od fd = tb_get(fd_tb,fid) lock = 0 ...od
P1:do true -> ... do test_set(&lock) -> skip od p.id = tb_alloc(proc_tb,pcb) lock = 0 ... do test_set(&lock) -> skip od fd = tb_get(fd_tb,fid) lock = 0 ...od
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Bloqueo al cuete!
Instruccin Test & Set Lock (TSL):Supongamos que hay dos regiones crticas donde en una se modifica la tabla de procesos y en la otra los files descriptors:
{ lock1 == 0 && lock2 == 0 }{ lock1 == 0 && lock2 == 0 }{ lock1 == 0 && lock2 == 0 }P0:do true -> ... do test_set(&lock1) -> skip od p.id = tb_alloc(proc_tb,pcb) lock1 = 0 ... do test_set(&lock2) -> skip od fd = tb_get(fd_tb,fid) lock2 = 0 ...od
P1:do true -> ... do test_set(&lock1) -> skip od p.id = tb_alloc(proc_tb,pcb) lock1 = 0 ... do test_set(&lock2) -> skip od fd = tb_get(fd_tb,fid) lock2 = 0 ...od
Comunicacin e/proc.: Regiones crticasExclusin mutua con espera ocupada (busy waiting)
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Tanto Peterson como TSL funcionan correctamentePero -> busy waiting
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0: do true ->A1 RNC0A2 do test_set(&lock) -> skip odA3 RC0A4 lock = 0 od
P1: do true ->B1 RNC1B2 do test_set(&lock) -> skip odB3 RC1B4 lock = 0 od
A1 A2 A3 B1 B2 B2 B2 B2 A4 A1 A2 A3 B2 B2 B2 B2 B2 A4 A1 A2 A3 B2 B2 B2 B2
! " # ! " # ! " #
Desperdicio de tiempo de CPU
Consideremos la siguiente secuencia de ejecucin:
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Tanto Peterson como TSL funcionan correctamentePero -> busy waiting
{ lock == 0 }{ lock == 0 }{ lock == 0 }P0: do true ->A1 RNC0A2 do test_set(&lock) -> skip odA3 RC0A4 lock = 0 od
P1: do true ->B1 RNC1B2 do test_set(&lock) -> skip odB3 RC1B4 lock = 0 od
A1 A2 A3 B1 B2 B2 B2 B2 B2 B2 B2 B2 B2 B2 B2 B2 B2 ..... !!!!!
Problema de inversin de prioridades
Ocurre lo mismo en schedulers no apropiativos y
suponiendo que P0 realiza E/S en la ejecucin de la RC
Supongamos que el scheduler considera prioridades: Que pasa?Peor => inanicin y deadlock:Supongamos que P1 tiene ms prioridad que P0:
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Lo mejor es bloquear el proceso en lugar de desperdiciar CPU:Se proponen dos tipos de primitivas nuevas:sleep(queue) wakeup(queue)
Recodemos el ejemplo del spooler de la impresora:Que pasa cuando el buffer se llena? y cuando se vaca?
Problema abstracto: Productores y ConsumidoresHay productores y consumidores de datos transferidos a travs de un buffer de tamao NSi el buffer se llena, los productores deben esperar para producir Si el buffer se vaca, los consumidores deben esperar para consumir
duerme al proceso encolndolo en queuedespierta un proceso en la cola queue (lo pasa de bloqueado a listo)
->->
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 0qp = []qc = []
Comienza ejecutando el consumidor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 0qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 0qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 0qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 0qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 1qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 1qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 1qp = []qc = []
El consumidor excede su tiempoContina ejecutando el productor
El consumidor an no est encolado!
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 1qp = []qc = []
El productor excede su tiempoContina ejecutando el consumidor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 1qp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = 2qp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = ...qp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = Nqp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = Nqp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = Nqp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
Funciona?
count = Nqp = []qc = [Cons]
El consumidor se bloqueaContina ejecutando el productor
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
No funciona
count = Nqp = [Prod]qc = [Cons]
El productor se bloquea=> Deadlock!
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
No funciona
count = Nqp = [Prod]qc = [Cons]
Se podra arreglar pero:esa solucin valdra para mltiples productores y consumidores?An as existen posibles condiciones de carreras en el uso del
buffer sin solucionar.
Comunicacin e/proc.: Regiones crticasSincronizacin bloqueante
Implementacin para un productor y un consumidor{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }{ count == 0 && empty(qp) && empty(qc) }
Productor:do true -> d = produce_item() if (count == N) -> sleep(qp) fi buf_insert(b,d) count = count + 1 if (count == 1) -> wakeup(qc) fiod
Consumidor:do true -> if (count == 0) -> sleep(qc) fi d = buf_remove(b) if (count = N-1) -> wakeup(qp) fi count = count - 1 consume_item(d)od
count: cant. datos en el bufferb: buffer con instrucciones para insertar (buf_insert) y quitar (buf_remove) datosqp, qc: colas donde se duermen los productores y consumidores, respect.
No funciona
count = Nqp = [Prod]qc = [Cons]
Tratemos de enternder por qu surge el problema Este modelo de sleep/wakeup no se
acord que ya haba hecho un wakeup.En general, no cuenta la cantidad de wakeup hechos
Comunicacin e/proc.: Regiones crticasSemforos [Dijkstra 1965]
Es un tipo abstracto de datos que consta de una variable entera y dos operaciones.La variable cuenta cuantos wakeups se efectuaronOperaciones (sem es la variable):
P(sem) :
V(sem) :
si sem ! 1 => decrementa semsi sem = 0 => se bloqueasi hay procesos bloqueados => desbloquea unosi no => incrementa sem
{{
A veces se bloquea
Nunca se bloquea
P es por probeer te verlagen (intentar decrementar)y V es por verhogen (incrementar)
Comunicacin e/proc.: Regiones crticasSemforos
Solucin de Productores/Consumidores con 3 semforos:full -> cuenta la cantidad de lugares ocupados en el bufferempty -> cuenta la cantidad de lugares vacos del buffermutex -> asegura la exclusin mutua del buffer
{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }Productor: do true -> d = produce_item() P(empty) P(mutex) buf_insert(b,d) V(mutex) V(full) od
Consumidor: do true -> P(full) P(mutex) d = buf_remove(b) V(mutex) V(empty) consume_item(d) od
Comunicacin e/proc.: Regiones crticasSemforos
Solucin de Productores/Consumidores con 3 semforos:full -> cuenta la cantidad de lugares ocupados en el bufferempty -> cuenta la cantidad de lugares vacos del buffermutex -> asegura la exclusin mutua del buffer
{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }Productor: do true -> d = produce_item() P(empty) P(mutex) buf_insert(b,d) V(mutex) V(full) od
Consumidor: do true -> P(full) P(mutex) d = buf_remove(b) V(mutex) V(empty) consume_item(d) od
En particular, mutex es un semforo que slo manipula dos
estados: bloqueado o desbloqueado. Este tipo de semforos se denomina
semforo binario o mutex.
Comunicacin e/proc.: Regiones crticasSemforos
Implementacin de semforos en kernelConsideramos dadas las dos llamadas al sistema sleep y wakeuptypedef struct { int count; queue q; // cola de hilos del semforo } Semaphore;
typedef struct { int count; queue q; // cola de hilos del semforo } Semaphore;
void P(Semaphore s) { Deshab. interrup. if (s->count > 0) { s->count --; Hab. interrup. } else { Add(s->q, current_thread); Hab. interrup. sleep(); }}
void V(Semaphore s) { Deshab. interrup. if (isEmpty(s->q)) { s->count ++; } else { thread = RemoveFirst(s->q); wakeup(thread); } Hab. interrup.}
Comunicacin e/proc.: Regiones crticasSemforos
Implementacin de semforos en kernelConsideramos dadas las dos llamadas al sistema sleep y wakeuptypedef struct { int count; queue q; // cola de hilos del semforo } Semaphore;
typedef struct { int count; queue q; // cola de hilos del semforo } Semaphore;
void P(Semaphore s) { Deshab. interrup. if (s->count > 0) { s->count --; Hab. interrup. } else { Add(s->q, current_thread); Hab. interrup. sleep(); }}
void V(Semaphore s) { Deshab. interrup. if (isEmpty(s->q)) { s->count ++; } else { thread = RemoveFirst(s->q); wakeup(thread); } Hab. interrup.}
Opiniones?
Solo funciona en mquinas de una
sola CPU
Para mltiples core usar TSL o XCHG.No queda otra que busy waiting, pero notar
que es muy localizado.
Comunicacin e/proc.: Regiones crticasSemforos
Implementacin de mutexes en espacio de usuario.Mucho ms eficiente
mutex_lock: TSL RX, mutex | copiar mutex a registro y setear mutex en 1 CMP RX, #0 | mutex era 0? JZE ok | si era 0, mutex estaba libre => return CALL thread_yield | si no, mutex est ocupada => ceder la CPU JMP mutex_lock | intentar otra vezok: RET | retornar; ingreso a la regin crtica
mutex_unlock: MOVE mutex, #0 | guardar 0 en mutex RET | retornar
Comunicacin e/proc.: Regiones crticasMonitores
{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }
Productor: do true -> d = produce_item() P(empty) P(mutex) buf_insert(b,d) V(mutex) V(full) od
Consumidor: do true -> P(mutex) P(full) d = buf_remove(b) V(mutex) V(empty) consume_item(d) od
Funciona?
Comunicacin e/proc.: Regiones crticasMonitores
{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }{ full == 0 && empty == N && mutex == 1 }
Productor: do true -> d = produce_item() P(empty) P(mutex) buf_insert(b,d) V(mutex) V(full) od
Consumidor: do true -> P(mutex) P(full) d = buf_remove(b) V(mutex) V(empty) consume_item(d) od
Los semforos son (an) primitivas de bajo nivelErrores sutiles pueden producir deadlocks o condiciones de carrera
Ej: Olvidarse un V, disponer las primitivas en orden incorrecto,...
No funciona
Deadlock!
Comunicacin e/proc.: Regiones crticasMonitores
Se necesitan construcciones de alto nivel que brinden una buena abstraccin a estos mtodos de sincronizacin:Monitores [Hoare 74, Brinch Hansen 75]Coleccin de procedimientos (y funciones), variables y estructura de datos agrupados en un mdulo con una forma especial de sincronizacin
=> TAD sincronizadoLos procesos pueden llamar a los procedimientos del monitor cuando lo deseenPero no pueden acceder directamente a las estructura de datos y variables internas del monitor
Slo un proceso puede estar activo en el monitor a cada instante
Muy importante
Comunicacin e/proc.: Regiones crticasMonitores
Productor: do true -> d = produce_item() syncBuff.insert(d) od
Consumidor: do true -> d = syncBuff.remove(b) consume_item(d) od
Productores/Consumidores:monitor syncBuff int count = 0 buffer b = [] condvar full, empty procedure insert(d:Data){ if count == N -> wait(full) fi buf_insert(b,d) count = count + 1 if count == 1 -> signal(empty) fi } function remove() data { if count == 0 -> wait(empty) fi result = buf_remove(b) count = count - 1 if count == N-1 -> signal(full) fi return(result) }end monitor
Comunicacin e/proc.: Regiones crticasMonitores
Productores/Consumidores:monitor syncBuff int count = 0 buffer b = [] condvar full, empty procedure insert(d:Data){ if count == N -> wait(full) fi buf_insert(b,d) count = count + 1 if count == 1 -> signal(empty) fi } function remove() data { if count == 0 -> wait(empty) fi result = buf_remove(b) count = count - 1 if count == N-1 -> signal(full) fi return(result) }end monitor
Todos los procedimientos y funciones se ejecutan en exclusin mutua
Levanta la exclusin mutua y duetme al proceso
encolndolo en fullDespierta a un
proceso encolado en full (si es que hay)
Varias polticas para signal:despierta y continua ejecutandodespierta y espera [Hoare]despierta y termina [Brinch Hansen]
Variables de condicin:
definen una cola de procesos
Comunicacin e/proc.: Regiones crticasMonitores
Productores/Consumidores:monitor syncBuff int count = 0 buffer b = [] condvar full, empty procedure insert(d:Data){ if count == N -> wait(full) fi buf_insert(b,d) count = count + 1 if count == 1 -> signal(empty) fi } function remove() data { if count == 0 -> wait(empty) fi result = buf_remove(b) count = count - 1 if count == N-1 -> signal(full) fi return(result) }end monitor
Todos los procedimientos y funciones se ejecutan en exclusin mutua
Levanta la exclusin mutua y duetme al proceso
encolndolo en fullDespierta a un
proceso encolado en full (si es que hay)
Varias polticas para signal:despierta y continua ejecutandodespierta y espera [Hoare]despierta y termina [Brinch Hansen]
Atencin!La correccin depende
de esta poltica
Variables de condicin:
definen una cola de procesos
Las implementaciones existentes (como en Java), no responden exactamente a las
aqu explicadas
Comunicacin e/proc.: Regiones crticasOtros modos de sincronizacin
Pasaje de mensajesSin memoria compartidaNo existen condiciones de carreraUsualmente para comunicar distintas mquinas
BarrerasSincroniza mltiples procesos
Lo van a ver en Redes y Sistemas Distribuidos y en Ingeniera del Software II
Comunicacin e/proc.: Problemas clsicos
Fili: do true -> pensar comer od
La actividad de un filsofo es:
Para comer debe tener los dos tenedores
que estn a su lado
Los tenedores son recursos compartidos. Hay que administrarlos apropiadamente
Los filsofos comensales [Dijkstra 1965]
Comunicacin e/proc.: Problemas clsicos
Fili: do true -> pensar tomar_tenedor(i) tomar_tenedor((i+1)%5) comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
Funciona?
Los filsofos comensales [Dijkstra 1965]
Comunicacin e/proc.: Problemas clsicos
Fili: do true -> pensar tomar_tenedor(i) tomar_tenedor((i+1)%5) comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
No funciona
Deadlock!
Los filsofos comensales [Dijkstra 1965]
Comunicacin e/proc.: Problemas clsicosLos filsofos comensales [Dijkstra 1965]Fili: do true -> pensar done = false do !done -> tomar_tenedor(i) if tenedor_disponible (i) then tomar_tenedor((i+1)%5) done = true else dejar_tenedor(i) fi od comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
Funciona?
Comunicacin e/proc.: Problemas clsicosLos filsofos comensales [Dijkstra 1965]Fili: do true -> pensar done = false do !done -> tomar_tenedor(i) if tenedor_disponible (i) then tomar_tenedor((i+1)%5) done = true else dejar_tenedor(i) fi od comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
Funciona?
Comunicacin e/proc.: Problemas clsicosLos filsofos comensales [Dijkstra 1965]Fili: do true -> pensar done = false do !done -> tomar_tenedor(i) if tenedor_disponible (i) then tomar_tenedor((i+1)%5) done = true else dejar_tenedor(i) fi od comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
Funciona?
Comunicacin e/proc.: Problemas clsicosLos filsofos comensales [Dijkstra 1965]Fili: do true -> pensar done = false do !done -> tomar_tenedor(i) if tenedor_disponible (i) then tomar_tenedor((i+1)%5) done = true else dejar_tenedor(i) fi od comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
Funciona?
Comunicacin e/proc.: Problemas clsicosLos filsofos comensales [Dijkstra 1965]Fili: do true -> pensar done = false do !done -> tomar_tenedor(i) if tenedor_disponible (i) then tomar_tenedor((i+1)%5) done = true else dejar_tenedor(i) fi od comer dejar_tenedor(i) dejar_tenedor((i+1)%5) od
Funciona?
Comunicacin e/proc.: Problemas clsicosLos filsofos com