Please enable JavaScript.
Coggle requires JavaScript to display documents.
Unidad 3 - Coggle Diagram
Unidad 3
Problema de la
Sección Crítica
Soluciones
fair
:
Ticket
Se reparten números y se espera a que sea el turno.
Número
: indica el siguiente número a ser tomado por el proceso que comienza
Próximo
: Indicar cuál es el siguiente número que tiene que ingresar en este momento en la sección crítica
Turno
[]: Un arreglo de variables turno que indica el proceso y el turno asociado
Desventaja:
El valor de turno y proximo incrementaria a numeraciones muy elevadas
Necesita otra funcion especial: Fetch and add
Bakery
Los procesos se comparan entre ellos
Cada proceso recorre los núm de los demás y se auto asigna uno mayor.
Espera a que su núm sea el menor de los que esperan.
Tie-Breaker TB
Cada proceso tiene una variable para indicar si está dentro de la sección crítica o intentando entrar, y una variable adicional para romper empates
Desventaja:
n-proceso⇒ complejo y costoso en tiempo.
Ordenan el acceso a la sección crítica de acuerdo al orden en que intentaron acceder a la misma
La prop “Eventual entrada” se cumpla sin necesidad de que el scheduler sea fuertemente fair.
Proteger recursos compartidos
Sincronización Barrier (
Barreras
)
Flags y Coordinadores
Procesos:
Coordinador
y
Worker
Variables:
Arribo
y
Continuar
El coordinador se encarga de desbloquear a los procesos para que continuen
Problemas:
La implementacion del coordinador
requiere un procesador extra
El tiempo de ejecución del coordinador es proporcional a n.
Árboles
La raíz del árbol es el
coordinador
Las hojas son los
workers
Arribo
desde las Hojas hacia la Raíz
Continuan
desde Raiz a Hojas
Problemas
Los procesos tienen distintos roles
Triplica el codigo para definir que nodo soy
Worker-Contador Compartido
Se incrementa una variable "
cantidad
"
Hasta que llegan todos los procesos
Problemas
Necesita funcion Fetch and Add
No sirve para multiples iteraciones
Barrera simétrica
Butterfly Barrier
Se utiliza cuando el número de procesos es una potencia de 2.
En la etapa s, un worker sincroniza
con otro a distancia 2^s-1
Los procesos se agrupan en pares y se sincronizan entre si antes de continuar, repitiéndose hasta que todos pasen por todas las etapas.
punto de demora
Sincronizar la ejecución de múltiples procesos
Solución de “
grano fino
”:
Spin Locks
Test and Test and Set
Agrega una verificación
Evita ingresos innecesarios a la función cuando el cerrojo está cerrado, mejorando la eficiencia.
se reduce, pero no desaparece. Cuando lock pasa a false posiblemente todos intenten hacer TS.
Test & Set
Sentencia de máquina atómica de grano fino
Establece un cerrojo (lock), bloqueando el acceso a la sección crítica.
Los procesos siempre ingresan a la función,
hacer “atómico” el await de grano grueso.
Los procesos que utilizan spin locks se quedan iterando en un bucle (spinning) mientras esperan que el lock esté disponible
no controla el orden
de los procesos demorados
Propiedades
Exclusión mutua
Ausencia de Deadlock
Ausencia de Demora Innecesaria
Eventual Entrada
Solución
software
: Sentencias await
No es una sentencia real es pseudo código
Incondicional
SCEnter y SCExit
Condicional
SCEnter
;
while (not B) { S
CExit
;
SCEnter
;
}
S;
SCExit
;
Mejora agregando un delay para darle
la posibilidad a otro proceso a que entre
y cambie el valor de la condición
Solución
hardware
: deshabilitar interrupciones
Solución correcta para una máquina monoprocesador.
Solución de “
grano grueso
”
Sincronización por variables compartidas
Problema de la Sección Crítica
Barreras
Sincronizar la ejecución de múltiples procesos
Locks
Proteger recursos compartidos
Requiere implementar protocolos de E/S de las SC para que los bloques se ejecuten con exclusion mutua
Tecnica Busy waiting
Un proceso chequea repetidamente una condición hasta que sea verdadera
Ventaja: Cualquier procesador
Desventaja: Ineficiente en multiprogramacion
conclusión:
Busy Waiting
Ineficiente
Debido a la competencia entre procesos en una misma UP
Complejos
Diseñar
Uso de las variables de estado y la sincronización