Por Michael Monge M. y Adrián Campos A. – Estudiantes de la carrera de Informática
¿Sabías que las estructuras de datos concurrentes construidos de manera ineficiente pueden bajar el rendimiento de todo el sistema, pues dichas estructuras se encuentran por todo el programa?
Antes que nada, es importante los términos de concurrencia y estructura de datos.
¿Qué es la concurrencia?
La concurrencia se produce cuando varios procesos se ejecutan al mismo tiempo en un solo sistema. Además, no ocurre solamente en un sistema digital, sino que también puede ser un fenómeno natural. En el mundo, en todo momento, están ocurriendo muchas cosas al mismo tiempo. Al usar la concurrencia para supervisar y manejar sistemas, hay que enfrentar este tipo de concurrencia natural.
Al trabajar en la creación de un sistema concurrente, hay que tener en cuenta un sinfín de variables. Entre ellas están el detectar y responder eficientemente a ocurrencias externas que afecten al sistema, asegurándose de que estos acontecimientos sean resueltos en un intervalo mínimo de tiempo.
Las estructuras de datos. ¿Qué son?
Justo como su nombre lo indica, se presenta una “estructura”, es decir, una forma de acomodar u organizar la información; en este caso, una serie de datos. De esta forma se puede buscar, interactuar, manipular, agregar o remover los datos de una manera más eficiente y controlada. Existen múltiples tipos de estructuras de datos para diferentes situaciones, según la forma en que se desee organizar los datos.
A continuación, se mencionan algunas de estas.
• Array: Es una estructura de datos con un tamaño que se define a la hora de su creación. Primordialmente se utiliza cuando se ingresan los datos de manera aleatoria, aunque, por lo general, solo permite ingresar datos de un solo tipo (int, String, boolean, etc.).
• Listas: Igual que los arrays sirven para almacenar información, con la diferencia de que no se establece al inicio el tamaño que la lista va a tener.
• Pila: Son especiales porque solo se pueden agregar o eliminar datos ubicados en la cima de dicha pila, dándole un sentido de orden en la forma de LIFO (Last in First out), que significa que siempre el último dato en entrar a la pila va a ser el primero en salir.
• Cola: Son el opuesto a las pilas, y simulan las filas de la vida real: el primero en llegar es el primero en salir (FIFO).
• Árboles Binarios: En estos se presentan nodos que contienen un valor cada uno, una referencia a un nodo que representa el hijo izquierdo (estos son menores al nodo padre) y, por último, una referencia a otro nodo que corresponde al hijo de la derecha, los cuales son mayores al nodo padre. Con esta organización se vuelve más sencillo realizar búsquedas, pues con solo revisar los valores de los nodos se determina si el dato que se busca es mayor o menor al nodo en que se encuentra en ese momento.
Debido a los cambios recientes de arquitectura, actualmente los servidores de alto rendimiento son tipo Non-Uniform Memory Access (NUMA), o acceso a memoria no uniforme. Estos equipos poseen múltiples sockets para procesadores llamados nodos. Aunque un núcleo de un nodo puede acceder a la memoria de otro nodo, es mucho más rápido acceder localmente y compartir las líneas de cache entre los nodos.
Para poder aprovechar al máximo el NUMA, las estructuras de datos deben tomar en cuenta esta asimetría, y hay que ser consciente del diseño NUMA para poder reducir el retraso en comunicación entre los nodos de una red, y minimizar el acceso remoto al cache.
Unfortunately, there are few NUMA-aware concurrent data structures, and designing new ones is hard. The key challenge is how to deal with contention on the data structure, where simple techniques limit concurrency and scale poorly, while efficient techniques are complex, error-prone, and rigid (Calciu, Sen, Balakrishnan y Aguilera, 2018)
Cuando se necesita utilizar estructuras de datos concurrentes, se hace posible que muchos hilos trabajen con datos comunes en una interfaz de alto nivel con una buena consistencia entre las operaciones que van ocurriendo en los programas. Dichas operaciones pueden ocasionar problemas a la hora de ejecutarlos, ya sea que interrumpan algún proceso que está ocurriendo a la vez o que modifique los valores que devuelva otro proceso. Por eso, es importante tomar las debidas precauciones cuando se realiza la contención de los procesos. Tomando en lo anterior en cuenta, lo más importante en la concurrencia de estructuras de datos es evitar a toda costa el conflicto de la escritura de datos.
MOXIE es el Canal de ULACIT (www.ulacit.ac.cr), producido por y para los estudiantes universitarios, en alianza con el medio periodístico independiente Delfino.cr, con el propósito de brindarles un espacio para generar y difundir sus ideas. Se llama Moxie - que en inglés urbano significa tener la capacidad de enfrentar las dificultades con inteligencia, audacia y valentía - en honor a nuestros alumnos, cuyo “moxie” los caracteriza.
