OnDoc
| sign
in
up
~
pub
|
pdf
txt
html
toc
url
|
<<
>>
1
2
3
4
5
6
7
8
~
19
Table of Contents
An optimistic approach to lock-free FIFO queues
Abstract
Introduction
The optimistic queue algorithm
Optimistic synchronization
Performance
The Algorithm in Detail
The optimistic queue data structure
The optimistic queue operations
Updating the prev pointer
The ABA problem and memory integrity
The tagging mechanism
Preventing the ABA problem in the tail and head pointers
Detecting and fixing the ABA problem in the prev pointer
The rolling-over of tags
Preserving memory integrity
Garbage collected languages --- a simple solution
Performance
The benchmarks
The experiments
Empirical results
Correctness proof
Modelling shared memory
Memory management
A concurrent FIFO queue specification
Linearizability proof
Lock-freedom proof
Code in the Java programming language of our new algorithm
Related work
Acknowledgements