A Study of Concurrent Data Structures

dc.contributor.authorLi, Bo
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T13:13:36Z
dc.date.available2019-07-03T13:13:36Z
dc.date.issued2013
dc.description.abstractThis 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.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/179842
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectInformations- och kommunikationsteknik
dc.subjectData- och informationsvetenskap
dc.subjectInformation & Communication Technology
dc.subjectComputer and Information Science
dc.titleA Study of Concurrent Data Structures
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeComputer systems and networks (MPCSN), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
179842.pdf
Storlek:
1.8 MB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext