Final 16 de Noviembre de 2017

CAS

1. Explicar compareAndSwap y demostrar que su numero de consenso es $\infty$

2. Desarrollar ReentrantLock que soporte locks recursivos

COMMIT

1. Definir el problema de consenso COMMIT sin fallas

2. Dar una solución

SETUID

Explicar que es el bit de SETUID. Dar un ejemplo de uso.

FIFO Queue

1. Explicar por qué la implementación de una cola FIFO no es correcta.

atomic<int> tail, head = 0;
int capacidad = N;
T[] items = new T[N];
void queue(x){
  assert(!full());
  items[tail.getAndInc() % capacidad] = x;
}
T deque(){
  assert(!empty());
  T x = items[head.getAndInc() % capacidad];
  return x;
}
bool full(){return tail.get() - head.get() == capacity};
bool empty(){return tail.get() - head.get() == 0};

2. Dar una implementación correcta wait-free para 1 productor y 1 consumidor.