Contexto
Un Candado es un objeto que garantiza la exclusión mutua, sin embargo, en la práctica ¿qué hacemos si no pudimos obtener el candado? Hay dos opciones:
Esperamos activamente (Peterson, Bakery y Filter dan vueltas en un ciclo while)
Le pedimos al sistema operativo que agende otro hilo (Monitores: Candado Reentrante, Objeto CountDownLatch, Semáforos, etc).
En esta práctica nos vamos a enfocar en los candados que cumplen con el primer punto, a este tipo de candados les conocemos como Spinlocks, son objetos que permiten que los hilos esperen activamente hasta lograr entrar a la sección crítica.
Hasta ahora hemos visto implementaciones de Candados que tienen una relevancia teórica, sin embargo, en la práctica necesitamos eficiencia y lidiar con los hilos que no tienen éxito: lidiar con la contención.
Contención: ocurre cuando múltiples hilos intentan acceder al candado al mismo tiempo, una contención alta implica que son muchos hilos al mismo tiempo y una contención baja implica que solo son algunos.
Es imposible crear candados eficientes para cualquier número de hilos sin operaciones primitivas (testAndSet(), get(), compareAndSet()), en esta práctica se muestran ejemplos de candados que las utilizan. Son herramientas poderosas de sincronización, más poderosas que volatile (Ojo: No podemos utilizar candados porque estamos creando candados, no synchronized). En la teoría veremos porque compareAndSet() es más poderosa que testAndSet() y que simples operaciones de escritura/lectura (write() o read).
Todos los candados utilizan la instrucción var.testAndSet(true) (getAndSet()), esta instrucción reemplaza el valor de la variable \(var\) con \(true\) y devuelve el anterior. \(BackoffLock()\), además, utiliza una ventana de tiempo para aliviar la contención. \(MCSLock()\) y \(CLHLock()\) incorporan una cola para, además de determinar el hilo que puede acceder a la sección critica, formar a los demás y así distribuir aún más la contención.
Ejemplos
En el siguiente link: https://github.com/surindt/FC_CConcurrente/tree/main/Programas_P4
Programa 1 (CounterAtomic): Contador linealizable no bloqueante, utiliza primitivas: getAndIncrement y get
Programa 2 (RunSpin): Programa 2: Programa para medir el tiempo de los siguientes candados:
Lock lock = new TASLock();
Lock lock = new TTASLock();
Lock lock = new BackoffLock();
Lock lock = new MCSLock();
Lock lock = new ALock(numberThreads);
Lock lock = new ReentrantLock();
Lock lock = new CLHLock();
Ejercicios
Entrega en un pdf las respuestas de los ejercicios que no requieran implementarse y añade una breve descripción de los programas que entregas (sus nombres y qué hacen).
Debes realizar un programa en cada ejercicio que indique “Implementar”.
El formato y el medio de entrega los indicará tu ayudante de laboratorio.
Recuerda que debes utilizar Java 21 LTS.
Si no compila utilizando Java 21LTS o si no se entrega la breve descripción de los programas se penalizará.
Tiempo de elaboración:\(\approx\) 2hr
Total de puntos: 100
Si ningún integrante en el equipo tiene una computadora con al menos 8 hilos comuníqueselo a la profesora.
La idea de las implementaciones de spinlocks (programas TASLock(), TTASLock(), BackoffLock(), MCSLock(), ALock(), CLHLock()) es aliviar la Contención distribuyendo a los hilos es distintas variables o dando tiempos fuera. Sin embargo, como investigaron la relación del throughput con el número de hilos en su práctica 2, el que ocupen un spinlock en un sistema dependerá del tamaño de las tareas, del hardware (sus compus), número de cores, la aplicación (si requieren Justicia o no).
Utiliza el programa RunSpin para probar cada uno de los spinlocks, cada integrante en el equipo debe completar la siguiente tabla: (max-1 es el número máximo de hilos en tu compu menos uno)
Tabla comparativa cuando la Tarea es muy breve SpinLocks / Counter TAS TTAS Backoff MCS ALock CLHLock Reentrant Counter Atomic Tiempo de ejecución: 400 tareas con 4 hilos Tiempo de ejecución: 1000 tareas con 4 hilos Tiempo de ejecución: 1000 tareas con max-1 hilos Modificación del método task(lock).
En lugar de incrementar un contador, modifica la función \(task(lock)\) para que los hilos trabajen con una matriz compartida de tamaño \(n \times n\), donde \(n = 10\). Cada hilo deberá asignar valores a la matriz dentro de una sección crítica protegida por \(lock\) y, una vez completada la asignación, imprimir su contenido. Implementa una función separada para la asignación y la impresión de la matriz. Cada integrante del equipo debe completar la siguiente tabla:
Tabla comparativa cuando la Tarea es más pesada SpinLocks / Counter TAS TTAS Backoff MCS ALock CLHLock Reentrant Tiempo de ejecución: 100 tareas con 4 hilos Tiempo de ejecución: 100 tareas con max-1 hilos Escojan al integrante del equipo con mayor número de hilos. ¿Cuáles son las 2 implementaciones más rápidas del inciso 1? ¿A qué crees se debe?
Escojan al integrante con mayor número de hilos. ¿Cuáles son las 2 implementaciones más rápidas del inciso 2? ¿A qué crees se debe?
¿Cuáles son las implementaciones que satisfacen la propiedad de Justicia? (Por el momento ignora ReentrantLock). Argumenta como lo hacen.