Práctica 7: Implementación del Soport a la Exclusión Mutua en Bajo Nivel

1. Objetivos de la sesión de prácticas

Entender la necesidad de la atomicidad y la consistencia
Conocer los mecnaismo hardware de una arquitectura concreta que dan soporte a la aotimicidad y la consistencia
Implementar en ensamblador un mecanismo de sincronización basado en spin-lock que sea energéticamente eficiente

2. Resumen de la práctica

El objetivo principal de esta prática es la implementación de un mecanismo de sincronización para el acceso en exclusión mutua, directamente sobre el nivel de la arquitectura de lenguaje máquina (ALMa), sin utilizar soporte del sistema operativo. La consecución del objetivo require comprender el soport harware necesario para la implementación y conoce las instrucción que dan visibilidad a ese soporte.

Primero se realizaraán algunos ejemplos sencillos que evidencien la necesidad de utilizar instrucciones atómicas y barreras (fences). Posteriormente se implementará una estrategis de spin-lock que finalmente se mejorara para mejorar su eficiencia energética.

3. Atomicidad y Consistencia

3.1 Suma mediante reducción

Una posible estrategia para calcular la suma de todos los componentes de un vector en un multiprocesador es realizar sumas parciales en cada uno de los procesadores y realizar una operación de reducción al terminar para realizar la suma completa. Para evitar problemas de desbalanceo, se pueden ir asignando porciones del vector a los distintos hilos (asumeindo un hilo por procesador) conforme van terminando la porción anterior. El pseudo-código a ejecutar por aparte de cada procesador sería:

Mientras trabjo_siponible:
  Seleccionar_porción
  Sumar_porición
  Sumar_porción en resultado_compartido

Escribe en C++ utilizando std::thread el código para realizar la suma de un vector de elementos sin emplear std::atomic ni std::mutex.

Cuestión. ¿Será correcto el resultado del código anterior? Explica el motivo.

Cuestión. Dado el código ej1-alumono.cpp Analízalo y arréglalo para que sea correcto utilizando funciones de biblioteca. Prueba su correción. Ten en cuenta las opciones de compilación: -lpthread y -mcmodel=large.

3.2 Suma mediante reducción con cuatro hilos y operaciones atómicas

Para resolver los problemas de atomicidad del problema anterior, se pueden emplear operaciones atómicas de ARMv8 como ldxr/stlxr.

Para resolver el problema de la suma incorrecta, vamos a implementar en ensamblador ARMv8 la primitiva fetch_and_add como una función. Esta fucnión leerá el valor de una posición de memoria y lo incrementará de manera atómica.

Escribe el código en ensamblador ARMv8 que podría implementar fetch_and_add, sobre la siguiente base:

 _loop:
       ldaxr oldvalue, [@shared_counter]
       add newvalue, oldvalue, mycount
       stlxr rres, newvalue, [@shared_counter]
       cbnz rres, _loop

Cuestión: Utilizad el código ensamblador escrito para corregir el ejercicio de la sección 3.1 del guión. Probad la corrección de la implementación. ¿Es correcta la suma entre varios hilos con es nuevo código? Cuestión: ¿Cuál sería la diferencia utilizando las instrucciones ldxr/stxr? Nota. Para mezclar en un mismo proyecto lenguaje de alto nivel y lenguaje ensamblador exiten varias alternativas. Se recomienda que escribáis en un fichero aparte, mi_fetch_add.s, la implementación en ensamblador y desde el probrama C++ invoquéis dicha función. Echad un vistazo a los puntos 4 y 5 de la bibliografía. Nota. Para repasar qué hace cada instrucción hemos subido a Moodle un manual de referencia de la arquitectura.

#4. Mutex

En este papartado se va a comprobar cómo pueden utilizarse las intrucciones de load-link/store-conditionalde ARMv8 para implementar un mutex.

4.1 Mutex con spin-lock

El mutex tendrá dos operaciones fundamentales, locky unlock. En la primera, se adquirirá el lock, el cual será liberado en la segunda. Se asumirá que un valor de 1 en la posición de meoria del mutex significa que está adquirido y 0 liberado.

_lock:
      ldaxr value, [@mutex]
      cmp value, #0
      b.ne _lock
      strlxr rres, #1, [@mutex]
      cbnz rrses _lock
_unlock:
      str #0, [@mutex]

Cuestión: Implementad vuestra versión de mutex en ensamblador y utilizarla en el programa de la sección 3.1. Probad la corrección del programa.

Cuestión. ¿Qué sucede cuando un thread intenta entrar en la sección crítica, pero ésta está ocupada? Identifica la secuencia de instrucciones que se ejecuta en ese caso.

Nota. Es posible que necesites instrucciones de barrier adicionales ISB, DMB, DSB.

4.2 Spin-lock energéticamente eficiente (Optativo)

Código tomado de los ejemplos de ARM DS-5

    
    .type _mutex_initialize, "function"
    .cfi_startproc
_mutex_initialize:

    // mark the mutex as unlocked
    mov w1, #0
    str w1, [x0]

    // we are running multi-threaded, so set a non-zero return value (function prototype says use 1)
    mov w0, #1
    ret
    .cfi_endproc

    .type _mutex_acquire, "function"
    .cfi_startproc
_mutex_acquire:

    // send ourselves an event, so we don't stick on the wfe at the top of the loop
    sevl
 
    // wait until the mutex is available
loop:
    wfe
    ldaxr w1, [x0]
    cbnz w1, loop
 
    // mutex is (at least, it was) available - try to claim it
    mov w1, #1
    stxr w2, w1, [x0]
    cbnz w2, loop
 
    // OK, we have the mutex, our work is done here
    ret
    .cfi_endproc

    .type _mutex_release, "function"
    .cfi_startproc
_mutex_release:
    mov w1, #0
    stlr w1, [x0]
    ret
    .cfi_endproc

Cuestión: Identifica dónde entra en modo de ahorro de energía el procesador.

Cuestión: ¿Se entera el Sistema Operativo de que el procesador está en modo bajo consumo?

5. C++ Modelo de memoria (opcional)

Consulta el siguiente enlace para leer el modelo de memoria que expone C++: https://en.cppreference.com/w/c/atomic/memory_order. Podrías hacer una tabla resúmen en la qué muestres qué instrucciones pueden sobrepasar el límite en torno a una primitiva de sincronización de C++ (p.e. lock, unlock, atomics, ...)