A Study of Concurrent Data Structures

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/179842
Download file(s):
File Description SizeFormat 
179842.pdfFulltext1.84 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: A Study of Concurrent Data Structures
Authors: Li, Bo
Abstract: This Master thesis studies four concurrent data structures but emphasizes on two concurrent tree data structures, in particular concurrent search trees. We have studied two concurrent search trees - concurrent AVL tree and concurrent counting-based tree (CBTree) and two concurrent queues - lock-free concurrent queue and two-lock concurrent queue. We implemented two variants of concurrent CBTree as well as the two concurrent queues. The optimistic concurrency control mechanism used in the concurrent tree data structures is called hand-over-hand optimistic validation. We further evaluated the implementations of the data structures coded in Java. The evaluations we done on an Intel workstation with Linux platform running 24 hardware threads. Furthermore, the advantages and drawbacks of these data structures are analyzed. Our study shows that CBTree should be implemented with some special mechanisms to achieve a better performance. Thus, this thesis achieves to present important explorations towards better implementation of concurrent search trees.
Keywords: Informations- och kommunikationsteknik;Data- och informationsvetenskap;Information & Communication Technology;Computer and Information Science
Issue Date: 2013
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/179842
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.