Exclusión mutua distribuida
El problema de fondo: en un sistema distribuido no hay memoria compartida ni reloj global, así que no podés usar un semáforo o lock tradicional. La exclusión mutua tiene que resolverse intercambiando mensajes.
a) Algoritmo Centralizado
Un proceso coordinador administra el acceso: pedís permiso, el coordinador te lo concede o te encola, entrás, avisás que saliste.
b) Algoritmo Distribuido (Ricart-Agrawala)
Cada proceso que quiere entrar le manda un pedido con timestamp (Lamport) a todos los demás. Cada uno responde OK salvo que esté en la sección crítica o tenga un pedido con timestamp más viejo pendiente (en ese caso, gana el más viejo). Entrás cuando recibiste el OK de todos.
c) Algoritmo de Anillo con Token
Los procesos forman un anillo lógico. Un token circula por el anillo; solo quien lo tiene puede entrar a la sección crítica.
| Centralizado | Distribuido (Ricart-Agrawala) | Anillo con Token | |
|---|---|---|---|
| Mecanismo | Coordinador único otorga permisos | Todos piden permiso a todos con timestamp | Token circula, solo el dueño entra |
| Mensajes por entrada | Pocos (2 por proceso: pedido + liberación) | Muchos — 2(N-1) por entrada | Depende de dónde está el token |
| Punto único de falla | Sí — el coordinador | No | Sí, indirecto — pérdida de token o caída de un nodo |
| Fairness (orden de llegada) | Sí, orden de llegada | Sí, por los timestamps | No necesariamente — depende de la posición en el anillo |
| Complejidad | Baja | Alta | Baja, pero requiere topología de anillo ya armada |
| Cuándo usarlo | Sistema chico/mediano con servidor confiable (ej: impresora compartida) | Sistema realmente distribuido, sin depender de nadie central (ej: red de sensores) | Redes que ya tienen forma de anillo (ej: línea de producción industrial) |
Elección de líder: Bully vs Ring
El problema que resuelven: cuando el coordinador de un algoritmo centralizado se cae, hay que elegir uno nuevo. No importa cuál gane, solo que se elija exactamente uno.
Algoritmo Bully ("el matón")
Cuando un proceso P nota que el coordinador no responde, manda ELECTION a todos los procesos con ID mayor al suyo. Si nadie responde, P gana. Si alguien mayor responde, ese proceso toma la posta. Siempre gana el de mayor ID.
Algoritmo Ring
Los procesos están en anillo lógico, cada uno solo conoce a su sucesor. El que detecta la caída arma un mensaje ELECTION con su ID y lo pasa. Cada proceso que lo recibe agrega su ID y lo reenvía. Cuando vuelve al que lo inició, se elige al de mayor ID de toda la lista, y ese resultado circula de nuevo para avisarle a todos.
| Bully | Ring | |
|---|---|---|
| Requisito de topología | Red completamente conectada (todos con todos) | Anillo lógico ya armado (cada uno conoce solo a su sucesor) |
| Quién gana | El de mayor ID | El de mayor ID (de toda la lista recorrida) |
| Cantidad de mensajes | Puede ser alta — consulta a todos los mayores | Baja — cada proceso solo habla con su vecino |
| Velocidad | Rápida en redes totalmente conectadas | Más lenta — el mensaje da toda la vuelta al anillo |
| Elecciones simultáneas | Funciona, puede generar más tráfico | Funciona sin problema — convergen al mismo ganador |
| Cuándo usarlo | Red completamente conectada, sin anillo | Red que ya tiene topología de anillo |
Detección de deadlocks: Wait-Die vs Wound-Wait
Ambos usan timestamps (más chico = más viejo) y comparten la regla de fondo: el proceso viejo siempre gana — nunca espera a uno más nuevo, y nunca lo abortan por uno más nuevo. La diferencia está en quién sufre el abort.
| Wait-Die | Wound-Wait | |
|---|---|---|
| ¿Quién decide? | El que pide decide su propio destino | El que pide decide el destino del otro |
| Si el que pide es más viejo | Espera (tiene derecho a esperar) | Gana — hace abortar al que tiene el recurso ("lo hiere") |
| Si el que pide es más nuevo | Se aborta a sí mismo ("muere") | Espera |
| ¿A quién le pasa el abort? | Al que pregunta (si es nuevo) | Al que ya tenía el recurso (si el que pregunta es viejo) |
Busy wait / Race condition / Deadlock / Starvation
| Concepto | Definición | Ejemplo | Clave |
|---|---|---|---|
| Busy wait | Esperar activamente en un bucle sin ceder la CPU | Chequear en un while si una variable se volvió true |
Ineficiente: gasta CPU sin trabajo útil |
| Race condition | Resultado incorrecto por acceso concurrente no controlado | Dos threads incrementan la misma variable sin sincronización | Impredecible, difícil de reproducir |
| Deadlock | Bloqueo mutuo: procesos esperando recursos en ciclo | A espera a B, B espera a A | Nadie avanza (safety) |
| Starvation | Un proceso nunca accede al recurso porque otros lo acaparan | Un thread de baja prioridad nunca es planificado | El sistema progresa, pero ese proceso no (liveness) |
Semáforo vs Monitor / Condition Variable
| Semáforo | Monitor / Condition Variable | |
|---|---|---|
| Estado interno | Un contador entero — solo "¿es mayor a 0?" | Cualquier variable que definas |
¿wait siempre bloquea? |
No, si el contador es >0 pasa directo | Sí, waitC siempre bloquea |
¿signal siempre tiene efecto? |
Sí — siempre suma o despierta a alguien | No — si nadie espera, se pierde sin dejar rastro |
¿A quién despierta signal? |
Un proceso al azar de los bloqueados | El primero de la cola FIFO |
| Qué condición podés esperar | Solo "¿el contador es mayor a 0?" | Cualquier condición arbitraria sobre tu estado |
Todas las primitivas de sincronización juntas
| Primitiva | Nivel | ¿Estado propio? | Exclusión mutua | ¿Bloquea? | Uso principal |
|---|---|---|---|---|---|
| Semáforo | Bajo | Sí (contador + cola) | Sí (si es binario) | Sí | Control de recursos, sincronización simple |
| Mutex | Bajo | No | Sí | Sí (si ocupado) | Proteger sección crítica |
| Lock | Bajo | No | Sí | Sí | Exclusión mutua genérica |
| Condvar | Medio | No (usa mutex externo) | No (depende del mutex) | Sí | Esperar sobre condición arbitraria |
| Monitor | Alto | Sí (encapsulado) | Sí (implícita) | Sí (vía condvars) | Abstracción completa |
| Barrier | Medio | Sí (contador de threads) | No | Sí | Sincronizar puntos de ejecución (todos juntos) |
Modelos de concurrencia
| Modelo | Cómo se comparte el estado | Ventajas | Desventajas | Caso de uso típico |
|---|---|---|---|---|
| Memoria compartida | Threads acceden directamente a las mismas variables | Simple en casos chicos, bajo overhead | Necesita locks explícitos → race conditions, deadlocks | Estructuras de bajo nivel, contadores locales |
| Fork-Join | Sub-tareas trabajan sobre porciones independientes | Muy eficiente para paralelismo de datos, work stealing minimiza sincronización | No sirve para tareas con dependencias/comunicación constante | Divide & conquer paralelo: ordenar arrays, map-reduce |
| Actores | Cada actor tiene estado 100% privado, todo por mensajes | Sin race conditions por diseño, buena escalabilidad y tolerancia a fallos | Overhead de mensajes, posibles deadlocks lógicos entre actores | Sistemas reactivos, backends distribuidos, Actix/Akka/Erlang |
| Pasaje de mensajes (canales) | Comunicación exclusiva por canales | Desacopla productor/consumidor, no hay memoria compartida que proteger | Requiere diseñar bien los canales (buffered o no) | Pipelines de datos, Go (goroutines+channels) |
Control de concurrencia: 2PL vs Timestamps vs OCC
| 2PL | Timestamps | Concurrencia Optimista (OCC) | |
|---|---|---|---|
| Mecanismo | Fase de expansión (toma locks) + fase de contracción (libera locks) | Cada transacción tiene timestamp; se compara al leer/escribir | Ejecuta sin bloquear, valida conflictos recién al commit |
| ¿Usa locks? | Sí | No | No |
| ¿Riesgo de deadlock? | Sí | No (por diseño) | No |
| ¿Riesgo de abortos? | Bajo | Alto si hay mucha contención | Alto si hay mucha contención |
| Mejor con... | Alta contención | Contención media, evitar deadlocks a toda costa | Baja contención (muchas lecturas, pocas escrituras) |
| Ejemplo de uso | Venta de entradas, reserva de mesas/turnos | Sistemas que quieren orden global sin locks | Wiki colaborativa, sistema interno de empresa |
Repaso relámpago
Una o dos líneas por tema — para releer rápido antes del final.
Sincronización (orden temporal) + comunicación (intercambio de datos) entre procesos que se ejecutan intercalados de forma arbitraria.
Memoria compartida (coordinar accesos con locks), fork-join (dividir en tareas independientes), canales/mensajes (comunicación explícita sin memoria compartida), async (concurrencia colaborativa para I/O), actores (estado privado + buzón de mensajes).
Threads comparten heap del proceso, cada uno con su propio stack. Fork-join es determinístico porque las tareas no interactúan hasta el join. Work stealing: cola de doble extremo por thread, el dueño opera en un extremo (LIFO), el que roba saca del otro extremo (FIFO) — minimiza contención.
Tareas livianas, poll nunca bloquea (Ready/Pending), await cede el control sin bloquear el thread, block_on sí bloquea. Sirve para mucho I/O y poco cómputo; no sirve para cómputo intensivo puro.
Safety = "nunca pasa algo malo" (exclusión mutua, ausencia de deadlock). Liveness = "eventualmente pasa algo bueno" (ausencia de starvation, fairness).
3 propiedades — exclusión mutua, ausencia de deadlock (alguien entra), ausencia de starvation (yo en particular entro).
Shared (lectura, conviven entre sí) vs exclusive (escritura, excluye todo). En Rust: lock poisoning protege contra propagar datos corruptos tras un panic con el lock tomado.
Contador V + cola de bloqueados L. wait: resta si V>0, sino bloquea. signal: si hay cola, despierta a uno (no suma al contador); si no hay cola, suma. Invariante: V = k + #signal − #wait, siempre V≥0.
Productor-consumidor (1 o 2 semáforos según buffer infinito/acotado), barbero (3 semáforos, sin garantía de FIFO), filósofos (deadlock por espera circular, se rompe con asimetría), fumadores (semáforos NO alcanzan, hace falta monitor/condvar), lector-escritor (starvation de un lado si no hay política justa — prioridad al escritor o FIFO).
Encapsulan datos + exclusión mutua automática. waitC siempre bloquea y libera el lock (si no, deadlock garantizado). signalC puede perderse si nadie espera — por eso siempre se chequea la condición con while antes de esperar (evita el "lost wakeup").
Grafo bipartito (lugares/transiciones), tokens = estado. I(t)/O(t) = lugares de entrada/salida. Se dispara si M(p) ≥ W(p,t) para todo p de entrada. Arco inhibidor = dispara solo si el lugar de origen tiene 0 tokens. Grafo de alcance = todos los estados posibles.
Centralizado (SPOF, fair, pocos mensajes) / distribuido Ricart-Agrawala (sin SPOF, muchos mensajes) / anillo con token (simple, requiere topología de anillo).
Bully (red completa, gana el de mayor ID) / Ring (anillo lógico, menos mensajes, más lento).
Atómica, consistente, aislada, durable. 5 implementaciones: private workspace (copia privada, rollback trivial), write-ahead log (loguear antes de escribir, permite redo/undo), 2PC (prepare→commit entre varios servicios, protocolo bloqueante si cae el coordinador), 2PL (control de acceso local, riesgo de deadlock), OCC (optimista, bueno con baja contención), timestamps (orden global sin locks).
Centralizado (coordinador arma el grafo de espera, riesgo de falsos deadlocks por desorden de mensajes) / distribuido (probe messages, si vuelve al origen hay ciclo) / Wait-Die y Wound-Wait (el viejo siempre gana, cambia quién sufre el abort).
Unidad de cómputo distribuida. Eventos (RECEIVE/ALARM/IMPULSE), estado σ(x,t), regla (guarda → acción), acción (efecto concreto), comportamiento (conjunto de reglas), conocimiento (lo que se puede inferir del estado global a partir del estado local + historial de mensajes).