# Resumen Final Concurrentes

## Principales desafíos de concurrencia:

- **Sincronización:** coordinación temporal entre distintos procesos
- **Comunicación:** datos que necesitan compartir los procesos para cumplir la función del programa.

---
## Corrección y Locks

### Definicion basica:
Que un programa haga lo que tiene que hacer, que cumpla su objetivo, que para un input determinado el output sea el esperado.

### Propiedades
- **Safety:** debe ser verdadera siempre, en todo momento de la ejecución
- **Liveness:** debe ser verdadera eventualmente

#### Safety
- Exclusión mutua: dos procesos no deben intercalar ciertas subsecuencias de instrucciones
- Ausencia de deadlock: un sistema que aún no finalizó debe poder continuar realizando su tarea, es decir, avanzar productivamente. Ejemplo: dos procesos necesitan sincronización, y para eso uno se queda esperando al otro y viceversa, deteniendo el avance total del programa

#### Liveness
- Ausencia de starvation: todo proceso que esté listo para utilizar un recurso debe recibir dicho recurso eventualmente.
- Fairness: igualdad entre los procesos. Un escenario es (débilmente) fair, si en algún estado en el escenario, una instrucción que está continuamente habilitada eventualmente aparece en el escenario. Es débilmente fair porque pedimos que eventualmente se ejecute, de ahí para arriba ya hay distintos niveles de fairness.

### Sección Crítica

Cada proceso se ejecuta en un loop infinito cuyo código puede dividirse en parte crítica y parte no-crítica

#### Especificación
- Exclusión mutua: no deben intercalarse instrucciones de la sección crítica
- Ausencia de deadlock: si dos procesos están tratando de entrar a la sección crítica, eventualmente alguno de ellos debe tener éxito
- Ausencia de starvation: si un proceso trata de entrar a la sección crítica, eventualmente debe tener éxito
- La sección crítica debe progresar (finalizar eventualmente)
- La sección no-crítica no requiere progreso (el proceso puede terminar o entrar en un loop infinito)

### Locks:

Herramienta que nos permite realizar exclusión mutua entre procesos en determinadas regiones del código (secciones críticas).

Existen dos tipos de locks:
- De lectura o compartido: Más de un proceso a la vez puede tener el lock, para tomarlo es necesario que se liberen todos los de escritura
- De escritura o exclusivo: Sólo un proceso a la vez puede tener este tipo de lock, para tomarlo es necesario que se liberen todos

### Semáforos:
Mecanismo para realizar sincronismo entre dos o más procesos, implementado como una construcción de programación concurrente de más alto nivel. Es una herramienta únicamente de sincronismo, no podemos obtener valores del semáforo.

Compuesto por dos campos:
- Un entero no negativo llamado V (contador, NO lo podemos consultar).
- Un set de procesos llamado L.

Tiene dos operaciones atómicas:
- `wait(S)`:

    if V > 0:
	    V -= 1
    else
	    S.L.append(P)
	    P.estado = bloqueado
- `signal(S)`:

if S.L is empty:
S.V += 1
else
P = S.L.remove_random()
P.estado = desbloqueado

  
Invariantes del semáforo:

- `S.V >= 0`
- `S.V = k + #signal(S) - #wait(S)`

#### Problema del Productor-Consumidor utilizando semáforos:
Con buffer infinito la idea es que basta con que el productor señalice al consumidor que el buffer no está vacío

buffer := emptyQueue
notEmpty := semaphore(0, [])

Productor:
dataType d
loop forever:
p1: append(d, buffer)
p2: signal(notEmpty)

Consumidor:
dataType d
loop forever:
q1: wait(notEmpty)
q2: d <- take(buffer)

En cambio, con un buffer acotado tengo que señalizar tambíen al productor que el buffer no está lleno y puede volver a producir

buffer := emptyQueue
notEmpty := semaphore(0, [])
notFull := semaphore(N, [])

Productor:
dataType d
loop forever:
p1: producir()
p2: wait(notFull)
p3: append(d, buffer)
p4: signal(notEmpty)

Consumidor:
dataType d
loop forever:
q1: wait(notEmpty)
q2: d <- take(buffer)
q3: signal(notFull)
q4: consumir(d)

### Barreras:
Permiten sincronizar varios threads en puntos determinados de un cálculo o algoritmo. Esperan a que cierta cantidad de threads lleguen a ese punto para continuar. Los casos de usos típicos son los algoritmos que se ejecutan por "rondas", como los que se usan para calculos numéricos.

En Rust existe el metodo `is_leader()` que solo se ejecuta en el thread lider, que es aquel que llega último y que por lo tanto levanta la barrera.

### Condition variables
Estructura o herramienta de sincronismo de alto nivel que tiene las siguientes características:
* No guarda ningún valor
* Tiene asociado una cola FIFO
* Consta de tres operaciones atómicas:
    * waitC(cond)
    * signalC(cond)
    * empty(cond)

waitC(cond):
cond.append(p)
p.state := blocked
monitor.releaseLock()

signalC(cond):
if (!empty(cond)):
q = cond.remove()
q.state = ready

empty(cond):
return cond = empty

### Monitores:
Herramientas de sincronización que permite a los hilos tener exclusión mutua y la posibilidad de esperar (block) por que una condición se vuelva falsa. Tienen un mecanismo para señalizar a otros hilos cuando su condición se cumple. Tienen una interfaz pública para que los procesos puedan acceder a las variables internas y un conjunto de condition variables que incorporan sincronismo al monitor.



### Semáforos vs Monitores:


| Semáforo | Monitor | 
| -------- | -------- | 
| `wait()` puede o no bloquear (si es mayor a 0 el contador solo le resta 1)     | `waitC()` siempre bloquea     | 
|`signal()` siempre tiene efecto (suma 1 o saca a un proceso de la cola y lo pone ready)|`signalC()` no tiene efecto si la cola está vacía|
|`signal()` desbloquea un proceso arbitrario|`signalC()` desbloquea el proceso del tope de la cola|
|un proceso desbloqueado con `signal()` puede continuar la ejecución inmediatamente|un proceso desbloqueado con `signalC()` debe esperar que el proceso señalizador deje el monitor|

 


---

## Modelos de concurrencia:
- Estado mutable compartido
- Paralelismo fork-join 
- Canales/mensajes
- Programación asincrónica
- Actores
---
## Estado mutable compartido:
Gran variable global a la que distintos programas secuenciales acceden para leerla y modificarla. coordinación temporal entre distintos procesos. Un concepto clave para este modelo es el de serialización que busca coordinar los procesos para poder acceder a ese estado compartido.
Por más de que los procesos se ejecuten al mismo tiempo, ciertos conjuntos de procedimientos sólo podrán ejecutarse por un solo proceso a la vez. Por ende, si un proceso está ejecutando dicho procedimiento, el resto deberá esperar a que este termine.
Este modelo tiene como principal inconveniente que delega en el programador la responsabilidad de cumplir con los problemas que presenta la concurrencia.

---

## Fork-join
Estilo de paralelización donde el cómputo (task) es partido en sub-cómputos menores independientes entre sí (subtasks). Los resultados de estos se unen (join) para construir la solución al cómputo inicial. Los sub-cómputos son independientes, entonces el cómputo se puede realizar en paralelo.

Ventajas:
- Modelo de concurrencia sin condiciones de carrera (no hay estado compartido)
- Los programas fork-join son determinísticos, los threads están aislados, no dependen uno del otro
- Performance: en el caso ideal es: `t_programa_secuencial / N_threads`

Desventajas:
- Requiere que las unidades de trabajo (tareas) sean aisladas, no todos los problemas se pueden resolver de esta forma.

### Work stealing
Algoritmo usado para hacer scheduling de tareas entre threads y mejorar el balance de trabajo entre estos. Los worker threads inactivos roban trabajo a threads ocupados para realizar balanceo de carga.
- Cada thread tiene su propia cola de dos extremos (deque) donde almacena las tareas listas por ejecutar.
- Cuando un thread termina la ejecución de una tarea, coloca las subtareas creadas al final de la cola.
- Luego, toma la siguiente tarea para ser ejecutada del final de la cola.
- Si la cola está vacía y el thread no tiene más trabajo, tratar de robar tareas del inicio de una cola de otro thread (random).

Al robar tareas del extremo contrario al que cada thread pushea, estaremos repartiendo el trabajo lo máximo posible (ya que estas serán las más largas).

fn count_lines_in_file(file: &str) -> u32 {
let contents = fs::read_to_string(file).unwrap();
contents.lines().count() as u32
}

fn count_lines_in_directory(dir: &str) -> u32 {
let mut total_lines = 0;
let mut handles = vec![];

for entry in fs::read_dir(dir).unwrap() {
let entry = entry.unwrap();
let path = entry.path();
if path.is_dir() {
handles.push(thread::spawn(move || count_lines_in_directory(path.to_str().unwrap())));
} else {
total_lines += count_lines_in_file(path.to_str().unwrap());
}
}

for handle in handles {
total_lines += handle.join().unwrap();
}

total_lines
}

fn main() {
let dir = "/path/to/dir";
let total_lines = count_lines_in_directory(dir);
println!("Total lines: {}", total_lines);
}

---

## Programación Asincrónica:
Modelo de programación concurrente en donde en lugar de usarse threads, se usan tareas intercaladas en el mismo thread o pool de threads. Está pensado principalmente para procesos que van a mantener el CPU inactivo, como operaciones de I/O o de red. No es el modelo adecuado para usar si se necesita hacer cómputo intensivo.

### Conceptos:
* Futures
Estructura que permite ser consultada para saber si terminó o no una tarea mediante un método poll() (modelo piñata). En Rust está representada como un Trait. Cada Future almacena lo necesario para realizar el pedido hecho por la invocación.

trait Future {
type Output;
fn poll(self: Pin<&mut Self>, cx: &mut Context<’_>) -> Poll<Self::Output>;
}

enum Poll<T> {
Ready(T),
Pending,
}

    
- Funciones asíncronas
Devuelven automáticamente el resultado antes de que comience a ejecutar el cuerpo de la función
- Expresiones await
- Tareas (tasks)
    * Mucho más livianas que los threads.
    * Más rápidas de crear que los threads.
    * Más eficiente de pasarle el control a ellas.
    * Menos overhead de memoria.
- Executors (`block_on` y `spawn_local`)
    * El runtime (en Rust se llama executor y no es parte de la std, hay que usar un crate externo) se encarga de crear las tareas e invocar a poll, nosotros como programadores no llamamos a poll. El objetivo final de este modelo es tener el procesador en uso el máximo tiempo posible.
    * `block_on` es una función sincrónica que produce el valor final de la función asincrónica. Es un adaptador del mundo asincrónico al sincrónico.

Este modelo de concurrencia se conoce como un modelo de concurrencia colaborativa, porque las tareas colaboran entre sí compartiendo el hilo de ejecución.

### Ejemplos servidor async

let listener = TcpListener::bind(address).await?;
let mut new_connections = listener.incoming()
while let Some(socket_result) = new_connections.next().await {
let socket = socket_result?;
task::spawn(async move {
let str = String::new();
socket.read_to_string(str).await?;
if(str == "S") {
socket.shutdown().await
}
socket.write_all("CONTINUE").await;
})
}

use std::net::SocketAddr;
use tokio::net::TcpListener;
use tokio::prelude::*;

async fn handle_client(mut stream: TcpStream) {
let mut buffer = [0; 1024];

loop {
let n = match stream.read(&mut buffer).await {
Ok(n) if n == 0 => return,
Ok(n) => n,
Err(e) => {
eprintln!("failed to read from socket; err = {:?}", e);
return;
}
};

if let Err(e) = stream.write_all(&buffer[0..n]).await {
eprintln!("failed to write to socket; err = {:?}", e);
return;
}
}
}

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
let addr: SocketAddr = "127.0.0.1:8080".parse()?;
let mut listener = TcpListener::bind(&addr).await?;

loop {
let (stream, _) = listener.accept().await?;
tokio::spawn(async move {
handle_client(stream).await;
});
}
}

---

## Canales / Mensajes

En el estado mutable compartido nos comunicamos compartiendo memoria, donde cada proceso accede al mismo recurso. En este modelo el recurso compartido está implícito en la comunicación mediante los canales. *"Do not communicate by sharing memory; instead, share memory by communicating."*

- Conectan un proceso emisor con un proceso receptor
- Tienen un nombre
- Son tipados
- Pueden ser sincrónicos o asincrónicos
- Son unidireccionales

Características de los canales en Rust:
- Un canal tiene dos extremos: uno emisor y otro receptor
- Una parte del código invoca métodos sobre el transmisor, con los datos que se quiere enviar
- Otra parte chequea el extremo de recepción por la existencia de mensajes
- Múltiples productores, un consumidor (MPSC)
- Transfiere el ownership del elemento enviado
- Para crear múltiples productores, se clona el extremo de envío

#### Problema del Productor-Consumidor utilizando canales

Productor:
I: Integer
loop forever:
Produce(I)
ch <= I

Consumidor:
I: Integer
loop forever:
ch => I
Consume(I)

Filosofo i:
dummy: Boolean
loop forever:
Think
forks[i] => dummy
forks[i+1] => dummy
Eat
forks[i] <= true
forks[i+1] <= true

Fork i:
dummy: Boolean
loop forever:
forks[i] <= true
forks[i] <= dummy

### Canales de Rust vs Sockets de UNIX

| Sockets UNIX | Channels Rust |
| -------- | -------- | 
| Comunicación 1-1    | Múltiples productores, un consumidor
| Se transmiten bytes     | Son tipados     |
| Comunican distintos procesos, incluso en máquinas distintas     | Comunican threads dentro del mismo programa     |
| Pueden ser asincrónicos (UDP) o no (TCP)     | Son asincrónicos     |
| Son bidireccionales     | Son unidireccionales     |


---

## Actores

Al utilizar el modelo de actores en un programa concurrente, estaremos teniendo mucho más encapsulamiento por cada proceso, ya que cada actor guarda su propio contexto (no se comparte memoria entre actores) y el estado de cada actor sólo puede cambiarse a través de mensajes. Esto previene problemas de sincronismo entre threads que podrían ocurrir con otro modelo. A su vez, los actores son mucho más livianos que los threads.

Un actor está compuesto por:
- Una dirección (a donde se le mandan mensajes)
- Una casilla de correo (FIFO). 
 

Características de los actores:
- Son aislados de otros actores: no comparten memoria
- El estado privado solo puede cambiarse a partir de procesar mensajes
- Puede manejar un mensaje por vez
- En un sistema distribuido, la dirección del actor puede una dirección remota

Los actores se comunican entre ellos solamente usando mensajes, los cuales son procesados por los actores de forma asincrónica. Estos mensajes son estructuras simples inmutables.

### Arbitrer: 

Es un thread que crea un event loop por debajo y provee un handler que se usa para enviar mensajes al actor.

- Provee el contexto de ejecución asincrónica para los actores, funciones y futures.
- Alojan el entorno donde se ejecuta el actor.
- Realizan varias tareas: crear un nuevo Thread del SO, ejecutar un event loop, crear tareas asincrónicas en ese event loop.

### Ciclo de vida de los actores:
- Iniciado (started): ya se invocó el método started(), crea el contexto del actor y ya está disponible.
- En ejecución (running): es el estado siguiente, el actor hace su vida y ejecución de handlers para procesar los mensajes. Pueden estar en este estado de forma indefinida.
- Parando (stopping): se llega si se invoca el stop() dentro del actor, si ningún otro actor lo referencia (nadie le puede enviar mensajes) o que no tenga objetos registrados en el contexto, es como un actor vacío o muerto.
- Detenido (stopped): desde el estado anterior no modificó su situación. Es el último estado de ejecución. En este estado se liberan los recursos.


### Ejemplo productor-consumidor

use std::time::Duration;
use actix::prelude::*;

struct Producer {
interval: Duration,
consumer: Addr<Consumer>,
}

impl Actor for Producer {
type Context = Context<Self>;

fn started(&mut self, ctx: &mut Self::Context) {
ctx.run_interval(self.interval, |act, _ctx| {
let num = rand::random::<u32>();
act.consumer.do_send(AddNumber(num));
});
}
}

struct AddNumber(u32);

impl Message for AddNumber {
type Result = ();
}

struct GetSum;

impl Message for GetSum {
type Result = u32;
}

struct Consumer {
sum: u32,
}

impl Actor for Consumer {
type Context = Context<Self>;
}

impl Handler<AddNumber> for Consumer {
type Result = ();

fn handle(&mut self, msg: AddNumber, _ctx: &mut Self::Context) -> Self::Result {
self.sum += msg.0;
}
}

impl Handler<GetSum> for Consumer {
type Result = u32;

fn handle(&mut self, _msg: GetSum, _ctx: &mut Self::Context) -> Self::Result {
self.sum
}
}

fn main() {
let system = System::new();

let consumer = Consumer { sum: 0 }.start();
let _producer = Producer {
interval: Duration::from_secs(1),
consumer,
}
.start();

system.run().unwrap();
}

---

## Exclusión mutua en ambientes distribuidos
La sección crítica tiene que ser ejecutada por un solo proceso a la vez, pero dentro de todos los procesos que tenemos en el sistema, en distintas computadoras.

### Algoritmo centralizado
- Un proceso es elegido como coordinador o líder (existen algoritmos de elección)
- Cuando un proceso quiere entrar a la SC envían un mensaje al coordinador.
- Si no hay ningún proceso en la SC, el coordinador envía OK, si hay, el coordinador no envía respuesta hasta que se libere la SC.

### Algoritmo distribuido
- Cuando un proceso quiere entrar en una sección crítica, construye un mensaje con el nombre de la sección crítica, el número de proceso y el timestamp y se lo envía a todos los procesos.
- Si el que recibe no está en la CS y no quiere entrar, envia OK.
- Si está en la CS, no responde y encola el mensaje. Cuando sale de la SC, envía OK.
- Si quiere entrar en la CS, compara el timestamp y gana el menor.

### Algoritmo token-ring
- Es una topología o manera de conectar los procesos en red de forma tal que se comunican formando virtualmente un anillo, es decir, cada proceso tiene comunicaciones punto a punto con dos procesos, uno de quien recibe mensajes y otro a quien le envía.
- Al iniciar, el proceso 0 recibe un token que va circulando por el anillo.
- Sólo el proceso que tiene el token puede entrar a la SC.
- Cuando el proceso sale de la SC, continúa circulando el token.
- El proceso no puede entrar a otra SC con el mismo token, tiene que esperar a que el token dé la vuelta.

---

## Algoritmos de elección en ambientes distribuidos
Varios algoritmos requieren de un coordinador con un rol especial (ej: algoritmos de exclusión mutua centralizada). Por lo general no importa cuál, sólo que haya alguno. Se asume: todos los procesos tienen un ID único, se ejecuta un proceso por máquina y conocen el número de los demás procesos. El objetivo: cuando la elección comienza, concluye con un elegido.

### Algoritmo Bully
Cuando un proceso P nota que el coordinador no responde, inicia el proceso de elección:
- P envía el mensaje ELECTION a todos los procesos que tengan número mayor
- Si nadie responde, P gana la elección y es el nuevo coordinador
- Si contesta algún proceso con número mayor, éste continúa con el proceso y P no hace nada más
- El proceso continúa hasta que todos excepto uno se rinden, el proceso disponible de número mayor es el único que queda
- El nuevo coordinador se anuncia con un mensaje COORDINATOR
- Cuando un proceso que se había caído vuelve a la red, inicia una elección. Si es el de nro. mayor, va a ser el coordinador

### Algoritmo ring
- Los procesos están ordenados lógicamente; cada uno conoce todo el anillo
- Cuando un proceso nota que el coordinador falló, arma un mensaje ELECTION que contiene su número de proceso y lo envía al sucesor. Si el sucesor no responde, se lo manda al sucesor de este y así hasta localizar un proceso que esté corriendo
- El proceso que recibe el mensaje, agrega su número de proceso a la lista dentro del mensaje y lo envía al sucesor
- Cuando el proceso original recibe el mensaje, lo cambia a COORDINATOR y lo envía. El nuevo coordinador es el proceso de mayor número de la lista. La lista se mantiene para informar el nuevo anillo
- Cuando este mensaje finaliza la circulación, se elimina del anillo
- Si dos procesos se dan cuenta al mismo tiempo que el coordinador está caído, ambos empiezan el proceso ELECTION y van a terminar mandando dos mensajes COORDINATOR con el mismo resultado y misma lista de procesos

---

## Transacciones

### Premisas del modelo de transacciones:
- El sistema está conformado por un conjunto de procesos independientes; cada uno puede fallar aleatoriamente (las transacciones vienen a solucionar este problema)
- Los errores en la comunicación son manejados transparentemente por la capa de comunicación.
- Storage estable:
    - Se implementa con discos
    - La probabilidad de perder los datos es extremadamente pequeña

### Primitivas:
- **BEGIN TRANSACTION**: marca el inicio de la transacción.
- **END TRANSACTION**: finalizar la transacción y tratar de hacer commit.
- **ABORT TRANSACTION**: finalizar forzosamente la transacción y restaurar los valores anteriores
- **READ**: leer datos de un archivo u otro objeto
- **WRITE**: escribir datos a un archivo u otro objeto

### Propiedades (ACID):
- **Atomic (atómica)**: Para el mundo exterior la transacción es indivisible, o sucede por completo en un instante o no sucede.
- **Consistent (consistente)**: los invariantes del sistema deben respetarse antes y después de la transacción (puede violarse temporalmente durante la transacción pero no es visible para los demás)
- **Isolated (aislada)**: las transacciones concurrentes no se afectan entre sí, el resultado final debe ser como si se hubieran ejecutado una detrás de la otra en algún orden
- **Durable (durable)**: una vez que se commitean los cambios, son permanentes (la excepción a esto son las transacciones anidadas, si la transacción padre hiciera abort, va a tener que hacer abort de todas, incluso de las que ya habían commiteado los hijos)

### Implementaciones:

#### Private workspace
Al iniciar una transacción, el proceso recibe una copia de todos los archivos a los cuales tiene acceso. Hasta que hace commit, el proceso trabaja con la copia, no con el original,  así que los demás no ven estos cambios. Al hacer commit, se persisten los cambios.
Desventaja: extremadamente costoso copiar todo, pero se pueden hacer optimizaciones

Optimizaciones:
- Si lee pero no modifica el archivo, y este no ha sido modificado desde el inicio de la transacción, se puede trabajar con el original sin copiar
- Copiar el índice primero. Cuando se quiere modificar un bloque, se lo copia y se trabaja en esa copia. Al commitear, se cambia el índice para que apunte a este nuevo bloque


#### Writeahead log
Los archivos se modifican in place, pero antes de hacer las modificaciones se las registra en un log escribiendo el nro de transacción y los cambios. Si la transacción es exitosa y se commitea, se registra el commit en el log y no hace falta hacer nada más. Si se aborta la transacción, se hace un rollback yendo de atrás hacia adelante deshaciendo los cambios.
También es útil para recuperarse de crashes. Al reiniciar la compu, se compara lo del log con el valor de las variables y se puede saber si se habían llegado a impactar las actualizaciones.

#### Commit en dos fases
En un sistema distribuido las transacciones pueden involucrar la cooperación de múltiples procesos, cada uno con sus archivos, datos, etc. Un proceso coordinador y otros subordinados.
El coordinador escribe en el log que comienza el protocolo de commit y luego le envía a los demás un mensaje para que preparen el commit. Estos ven si pueden hacerlo, lo escriben en el log y responden. Si todos responden OK, se puede commitear; si no, no. Para ambas lo que se hace es escribir en el log y enviar mensaje a los subordinados. Los procesos que reciben el mensaje, escriben commit en el log y envían finished al coordinador. La escritura en el log sirve para recuperarse si crashea un proceso, sea coordinador o subordinado.

### Control de concurrencia

#### Lockeo en dos fases
- Fase de expansión: se toman todos los locks a usar
- Fase de contracción: se liberan todos los locks (no se pueden tomar nuevos locks)
- Garantiza propiedad serializable para las transacciones
- Si uno no hace cambios hasta tener los locks, no poder obtener un lock se puede manejar liberando todos los demás y probando nuevamente después de un tiempo
- Pueden ocurrir deadlocks, por ejemplo si no todos toman los locks en el mismo orden. Se pueden detectar chequeando si hay ciclos en un grafo de procesos y recursos.
- Strict two-phase locking: la contracción ocurre después del commit. Permite que una transacción siempre lea un valor ya commiteado. Impide cascada de aborts.

#### Concurrencia optimista
El proceso modifica los archivos sin ningún control, esperando que no haya conflictos (no suele haber). Al commitear, se verifica si el resto de las transacciones modificó los mismos archivos desde el comienzo de esta transacción. Si es así, se aborta la transacción. Funciona mejor con private workspaces.
**Ventajas**: Libre de deadlocks y favorece el paralelismo.
**Desventajas**: Rehacer todo puede ser costoso en condiciones de alta carga.

#### Timestamps
- Existen timestamps únicos globales para garantizar orden (ver algoritmo de relojes de Lamport)
- Cada archivo tiene dos timestamps: lectura y escritura y qué transacción commiteada hizo la última operación en cada caso
- Cada transacción al iniciarse recibe un timestamp
- Al intentar acceder a un archivo se compara el timestamp de la transacción con los timestamps del archivo:
    - Si es mayor, la transacción está en orden y se procede con la operación
    - Si es menor es porque otra transacción más joven modificó el archivo, la transacción actual se aborta
- Al commitear se actualizan los timestamps del archivo

En concurrencia optimista la idea era que dos transacciones concurrentes no pudieran modificar el mismo archivo. Acá pueden hacerlo siempre y cuando se respete el orden de las transacciones (nunca una transacción más vieja puede leer algo escrito por una más nueva).

---

## Deadlocks en ambientes distribuidos

Un deadlock es una situación en la que dos o más procesos compiten por recursos limitados y tienen la capacidad de adquirir y retener un recurso, evitando que otros lo usen. En un sistema distribuido, los deadlocks pueden ser más complicados de detectar y resolver debido a la naturaleza descentralizada del sistema. Un grafo de asignación de recursos (RAG) se puede utilizar para prevenir deadlocks al analizar el estado actual del sistema y predecir la ocurrencia de un deadlock. Para evitar un deadlock, el sistema operativo puede evitar cualquiera de las cuatro condiciones necesarias para que se produzca: exclusión mutua, espera y retención, no apropiación y espera circular. Si estas condiciones se cumplen simultáneamente, puede ocurrir un deadlock.

- ***Exclusión mutua:*** Esta condición establece que solo un proceso puede tener acceso a un recurso en un momento dado. Si otro proceso desea acceder al mismo recurso, debe esperar hasta que el proceso que lo tiene lo libere.
- ***Espera y retención**:* Esta condición establece que un proceso puede mantener uno o más recursos mientras espera la asignación de otros recursos.
- ***No apropiación**:* Esta condición establece que un recurso asignado a un proceso no puede ser tomado por la fuerza por otro proceso. El recurso solo puede ser liberado voluntariamente por el proceso que lo tiene.
- ***Espera circular**:* Esta condición establece que debe haber un conjunto de procesos en el que cada proceso está esperando un recurso que está siendo retenido por el siguiente proceso en el conjunto.

### Detección 

#### Algoritmo centralizado
- El proceso coordinador tiene que mantener el grafo de uso de recursos
- Cada proceso tiene su grafo de recursos. Para mantener actualizado el coordinador, los procesos le envían mensajes cuando obtienen/liberan un recurso y el coordinador actualiza el grafo. Otras formas son que no lo hagan todo el tiempo, que sea periódico o sea el coordinador el que pida actualizaciones.
- Problema: los mensajes pueden llegar llegar desordenados y generar falsos deadlocks
- Posible solución: utilizar timestamps globales para ordenar los mensajes (algoritmo de Lamport)


#### Algoritmo distribuido
- Los procesos pueden pedir varios recursos al mismo tiempo, en vez de uno a la vez
- Cuando un proceso debe esperar por un recurso, envía un probe message al proceso que tiene el recurso. El mensaje contiene: id del proceso que se bloquea, id del proceso que envía el mensaje y id del proceso destinatario
- Al recibir el mensaje, si este proceso está esperando a otros, actualiza el id del proceso que envía y el id del destinatario y lo envía a los procesos que tienen el recurso que necesita. Estos otros receptores hacen lo mismo
- Si el mensaje llega al proceso original, tenemos un ciclo en el grafo
- Una forma de romper el deadlock es que el que detecta el ciclo se suicide, pero es un problema si varios aplican el mismo al mismo tiempo porque todos estos se van a suicidar. Otra alternativa es que cada proceso vaya agregando su id y cuando dé toda la vuelta se le pida al de id más alto que se suicide.

### Prevención

#### Algoritmo wait-die
- Se asigna un timestamp único y global a cada transacción al iniciar (algoritmo de Lamport)
- Cuando un proceso A está por bloquearse en un recurso (que tiene otro proceso B), se comparan los timestamps
- Si el timestamp de A es menor (proceso más viejo), espera
- Si no, el proceso aborta la transacción
- Conviene que sea así y no que aborte si es mayor porque es mejor no abortar transacciones que llevan corriendo más tiempo y al darle prioridad a los más viejos se elimina la starvation.
- Siguiendo la cadena de procesos esperando los timestamps siempre aumentan, así que no puede haber ciclos.

![image](https://hackmd.io/_uploads/rJ0maC1nT.png)

#### Algoritmo wound-wait
- Se asigna un timestamp único y global a cada transacción al iniciar (algoritmo de Lamport) 
- Cuando un proceso A está por bloquearse en un recurso (que tiene otro proceso B), se comparan los timestamps
- Si el timestamp de la transacción A es menor (proceso más viejo), se aborta la transacción del proceso B que tiene el recurso, para que el más viejo pueda tomarlo
- Si no, el proceso espera

![image](https://hackmd.io/_uploads/rkGdaRJ3a.png)


Con wait-die se podía dar que el proceso joven luego de abortar intentara inmediatamente empezar la transacción de nuevo, intentar tomar el recurso y tener que abortar, todo así varias veces hasta que el proceso viejo liberara el recurso. Con wound-wait no pasa esto de abortar varias veces, solo una si es un proceso viejo que quiere un recurso que tiene el nuevo.

---

## Ambientes distribuidos

### Entidad
Unidad de cómputo de ambiente informático distribuido, podría ser por ejemplo un proceso, un procesador o un actor, dependiendo de cómo definimos al ambiente distribuido.

### Capacidades
- Cada entidad cuenta con las siguientes capacidades:
- Acceso de lectura y escritura a una memoria local no compartida con otras entidades
    - Registro de estado interno propio de la entidad
    - Registro del valor de entrada
- Procesamiento local: las entidades ejecutan su algoritmo localmente sin comunicarse con otras
- Las entidades tienen que tener la capacidad de preparar, transmitir y recibir mensajes
- Tienen la capacidad de setear y resetear un reloj local

### Eventos externos
La entidad es reactiva, es decir solamente responde a eventos externos, los cuales pueden ser:
- La llegada de un mensaje
- Activación del reloj
- Un impulso espontáneo (algo que haga que la entidad reaccione sin ser un mensaje, como la creación de un nuevo actor)
A excepción del impulso espontáneo, los eventos se generan dentro de los límites del sistema.


### Acción
Secuencia finita e indivisible de operaciones. Es atómica porque se ejecuta sin interrupciones.

### Regla
Es la relación entre el evento que ocurre y el estado en el que se encuentra la entidad cuando ocurre dicho evento, de modo tal que
estado × evento → acción
Ej: tengo un contador en 10 (estado) y llego un mensaje de sumar 1 (evento) entonces emito una alarma (acción)

### Comportamiento
Es el conjunto `B(x)` de todas las reglas que obedece una entidad x
- Para cada posible evento y estado debe existir una única regla `B(x)`

Comportamiento colectivo del sistema distribuido: `B(E) = B(x) : ∀x ∈ E`

El comportamiento colectivo es homogéneo si todas las entidades que lo componen tienen el mismo comportamiento, o sea: ∀x, y ∈ E, B(x) = B(y)
Propiedad: Todo comportamiento colectivo se puede transformar en homogéneo.

### Comunicación

- Una entidad se comunica con otras entidades mediante mensajes (un mensaje es una secuencia finita de bits)
- Puede ocurrir que una entidad sólo pueda comunicarse con un subconjunto del resto de las entidades:
    - N_OUT (x) ⊆ E: conjunto de entidades a las cuales x puede enviarles un mensaje directamente
    - N_IN (x) ⊆ E: conjunto de entidades de las cuales x puede recibir un mensaje directamente

### Axiomas

*Delays de comunicación finitos:* En ausencia de fallas los delays en la comunicación tienen una duración finita

*Orientación local:* Una entidad puede distinguir entre sus vecinos N_OUT y entre sus vecinos N_IN

- Una entidad puede distinguir qué vecino le envía un mensaje
- Una entidad puede enviar un mensaje a un vecino específico

### Restricciones de confiabilidad

- Entrega garantizada: cualquier mensaje enviado será recibido con su contenido intacto
- Confiabilidad parcial: no ocurrirán fallas
- Confiabilidad total: no han ocurrido ni ocurrirán fallas

### Restricciones temporales

- Delays de comunicación acotados: existe una constante ∆ tal que en ausencia de fallas el delay de cualquier mensaje en el enlace es a lo sumo ∆
- Delays de comunicación unitarios: en ausencia de fallas, el delay de cualquier mensaje en un enlace es igual a una unidad de tiempo
- Relojes sincronizados: todos lo relojes locales se incrementan simultáneamente y el intervalo de incremento es constante

### Costo y complejidad

Son las medidas de comparación de los algoritmos distribuidos
- Cantidad de actividades de comunicación
    - Cantidad de transmisiones o costo de mensajes, M
    - Carga de trabajo por entidad y carga de transmisión
- Tiempo
    - Tiempo total de ejecución del protocolo
    - Tiempo ideal de ejecución: tiempo medido bajo ciertas condiciones, como delays de comunicación unitarios y relojes sincronizados

### Conocimiento

Entendemos por conocimiento a la información que cada entidad tiene del ambiente distribuido. Puede ser conocimiento local, como el contenido de la memoria local (que en ausencia de fallas no puede perderse), o conocimiento general sobre la red, como la topología (como están conectadas las entidades entre sí), información métrica de la red (número de nodos, delay, etc.) e información sobre los nodos vecinos. 

### Estados y Configuraciones

- Estado interno de `x` en el instante `t` `σ(x,t)`: contenido de los registros de `x` y el valor del reloj `cx` en el instante `t`
- El estado interno de una entidad cambia con la ocurrencia de eventos

Sea una entidad `x` que recibe el mismo evento en dos ejecuciones distintas, y `σ1` y `σ2` los estados internos, si `σ1` = `σ2` ⇒ el nuevo estado interno de `x` será el mismo en ambas ejecuciones.

---

### Bonus
[🧀](https://cdn.discordapp.com/attachments/376738740502265860/887431022495543306/top1000cheese.webm?ex=65de428b&is=65cbcd8b&hm=6a542a0f54d944dd6ccfaa87b58551b8ba6dc2108bd445059c681d888f29f204&)
[🐝](https://cdn.discordapp.com/attachments/419074439703953411/437179464619786261/beemovie.mp4)