A concurrent red black tree.
| dc.contributor.advisor | Eterovic S., Yadran | |
| dc.contributor.author | Besa Vial, Juan José | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2012-10-25T12:20:51Z | |
| dc.date.available | 2012-10-25T12:20:51Z | |
| dc.date.issued | 2012 | |
| dc.description | Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2012 | |
| dc.description.abstract | 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. | |
| dc.description.abstract | 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. | |
| dc.identifier.doi | 10.7764/tesisUC/ING/1413 | |
| dc.identifier.uri | https://doi.org/10.7764/tesisUC/ING/1413 | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/1413 | |
| dc.language.iso | en | |
| dc.nota.acceso | Contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject.ddc | 620 | |
| dc.subject.dewey | Ingeniería | es_ES |
| dc.subject.other | Procesamiento electrónico de datos - Procesos distribuidos. | es_ES |
| dc.title | A concurrent red black tree. | es_ES |
| dc.type | tesis de maestría | |
| sipa.codpersvinculados | 68801 | |
| sipa.codpersvinculados | 149083 |
Files
Original bundle
1 - 1 of 1