Contention resistant non-blocking priority queues | Lars Frydendal Bonnichsen
| | Abstract | This thesis primarily deals with the design and implementation of concurrent data structures, as well as related facilities. Any concurrent data structure may have strictly limited scalability, unless care is taken in their access patterns.
This thesis seeks to investigate ways to reduce these issues, for the specific context of priority queues used for picking tasks in operating systems.
The thesis makes improvements upon a state of the art locking mechanism, to provide up 27 times faster locking, for small data structures. This is in part achieved, by improving a leading backoff scheme, and applying it in a novel fashion. We have designed and implemented a priority queue based on a balanced search tree. The new data structure is based on a new lock-free data structure based on B-trees. To the best of our knowledge, this is the first lock-free B-tree, that does not depend on the presence of a garbage collector. | | Type | Master's thesis [Industrial collaboration] | | Year | 2012 | | Publisher | Technical University of Denmark, DTU Informatics, E-mail: reception@imm.dtu.dk | | Address | Asmussens Alle, Building 305, DK-2800 Kgs. Lyngby, Denmark | | Series | IMM-M.Sc.-2012-21 | | Note | Supervised by Associate Professor Sven Karlsson, ska@imm.dtu.dk, DTU Informatics | | Electronic version(s) | [pdf] | | Publication link | http://www.imm.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Computer Science & Engineering |
|