Dublin Core
Title
A concurrent red black tree.
Subject
620
Ingeniería
Procesamiento electrónico de datos - Procesos distribuidos.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2012
La necesidad de tener estructuras de datos capaces de soportar varios procesos ha crecido con la masificación de los computadores multiprocesadores. Las estructuras de datos concurrentes buscan proveer una eficiencia similar a las estructuras de datos secuenciales permitiendo además el acceso concurrente a varios procesos y proveyendo mecanismos de sincronización transparentemente a esos procesos. Los árboles rojo negros son una importante estructura de datos utilizada en muchos sistemas. Lamentablemente ha sido complejo implementar un árbol rojo negro concurrente eficiente para computadores de memoria compartida.
Debido a esto la mayoría de los esfuerzos de investigación han sido dirigidos hacia otras estructuras de datos tipo diccionarios, principalmente skiplists y arboles AVL. En esta tesis presentamos un nuevo tipo de árbol rojo negro concurrente que utiliza técnicas de optimistic concurrency and nuevas operaciones de balance para escalar eficientemente y soportar contención. Nuestro árbol se comporta favorablemente comparado con otros diccionarios similares. En particular, en escenarios de alta contención se comporta hasta 14% mejor que la solución más conocida de los diccionarios concurrentes.
Creator
Besa Vial, Juan José
Date
2012-10-25T12:20:51Z
2012-10-25T12:20:51Z
2012
Contributor
Eterovic S., Yadran
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/1413
https://doi.org/10.7764/tesisUC/ING/1413
https://repositorio.uc.cl/handle/11534/1413