Auxiliar 8

Spinlocks

Vicente González

Pablo Jaramillo

Contexto

Spinlocks

Herramienta de sincronización primitiva
No depende de un sistema operativo
Igual de potente que el resto!

Creación

int sl = OPEN; // o CLOSED

Bloqueo

spinLock(&sl);

Desbloqueo

spinUnlock(&sl);

How to?

Mutex

int sl = OPEN; // global

// ...

void fun() {
  spinLock(&sl);

  // sección crítica

  spinUnlock(&sl);
}

Condición

int *psl; // global

// ...

void f() {
  // thread que espera
  int sl = CLOSED;
  psl = &sl;

  spinLock(&sl); // espera
  // ...
}

void g() {
  // thread que despierta
  spinUnlock(psl); // despierta
}

Implementación

void spinLock(volatile int *psl) {
  do {
    while (*psl == CLOSED)
      ;
  } while (swap(psl, CLOSED) != OPEN);
}

Problemas

P1 — Lector/escritor

Parte A

La siguiente implementación es incorrecta. Haga un diagrama de threads que muestre que un lector puede entrar junto con un escritor.

void enterRead() {
  if (readers == 0)
    spinLock(&write_lck);
  spinLock(&mutex_lck);
  readers++;
  spinUnlock(&mutex_lck);
}

void enterWrite() {
  spinLock(&write_lck);
}

void exitRead() {
  spinLock(&mutex_lck);
  readers--;
  spinUnlock(&mutex_lck);

  if (readers == 0)
    spinUnlock(&write_lck);
}

void exitWrite() {
  spinUnlock(&write_lck);
}

Parte B

Modifique la solución anterior para que funcione correctamente.

P2 — Función team

Considere una máquina multicore en la que no existe un núcleo de sistema operativo y por lo tanto no hay un scheduler de procesos.

Se necesita formar múltiple equipos de 5 cores cada uno. Para ello, los cores invocan la función team indicando su nombre como argumento. Esta función espera hasta que 5 cores hayan invocado team, retornando un arreglo de 5 strings con los nombres del equipo completo.

Este es un ejemplo del uso de la función team:

int player(char *name) {
  for (;;) {
    char **mTeam = team(name);
    play(mTeam);
    sleep();
  }
}

P2 — Función team

Se debe programar la función team con el siguiente encabezado:

char **team(char *name);

Se dispone de spin-locks y la función coreId(). Necesitará usar variables globales y malloc.

Restricción: Dado que no hay un núcleo de sistema operativo, la única forma válida de esperar a que se forme el equipo es utilizando un spin-lock. Otras formas de busy-waiting no están permitidas. No hay Queues FIFO.

P3 – Propuesto

Considere una máquina con 8 cores físicos que comparten la memoria, sin un núcleo de sistema operativo y por lo tanto no hay scheduler de procesos. A cada core se le asignan inicialmente 100 euros.

Un core puede robar cantidad euros del core número desde invocando la función:

void robar(int desde, int cantidad);

En tal caso se le resta cantidad euros a la tarea desde y se le suman al core que invocó robar. El parámetro cantidad es siempre mayor que cero.

Un primer invariante es que un core no puede almacenar una cantidad negativa de euros. Si el core desde no posee suficiente dinero para robarle cantidad entonces robar debe esperar hasta que el core desde sí posea al menos la cantidad requerida.

El segundo invariante es que en un instante dado el core \(T\) no puede estar esperando robarle \(c\) euros al core \(U\) si \(U\) tiene al menos \(c\) euros. Observe que cuando el core \(T\) lograr robar dinero, varios otros cores pueden estar esperando poder robarle dinero a \(T\). No está especificado en qué orden deben robarle el dinero a \(T\).

Ayuda

Use una matriz m de 8 por 8 punteros a spin-locks. Si m[i][j] no es nulo quiere decir que m[i][j] es la dirección de un spin-lock en el que el core i espera para robarle al core j.

P3 – Propuesto

El siguiente diagrama muestra una situación con 5 threads:

Fin

Ver otras auxiliares