DMTM 2014
image/svg+xml
DMTM 2014
2014-01-22
Andreas Haas
##
/
##
MASTER SLIDE
DMTM Workshop, January 2014
Fairness vs. Linearizabilityin a Concurrent FIFO Queue
Mike Dodds
University of York
Andreas Haas
University of Salzburg
Christoph M. Kirsch
University of Salzburg
linearization points
time
time
linearizable wrt. FIFO
not linearizable wrt. FIFO
linearizability can be achieved at the expense of performance
b
deq
a
deq
b
enq
a
enq
b
deq
a
deq
b
enq
a
enq
time
deq
a
b
deq
c
deq
b
enq
a
enq
c
enq
time
b
deq
a
deq
c
deq
b
enq
a
enq
c
enq
removedout-of-order
returnedout-of-order:not fair
linearizability may come at theexpense of fairness
linearizable wrt. FIFO
not linearizable wrt. FIFO
linearizable wrt. FIFO
a|1
b|3
c|2
unordered buffer
find and remove the oldest elementfirst
deq
deq
deq
contention
elements withtimestamps
a|1
b|3
c|2
unordered buffer
time
deq
deq
deq
b
enq
a
enq
c
enq
a
c
because a will be removed by the otherdequeue
because a will be removed by the otherdequeue
c|2
b
a|1
b|3
c|2
deq
deq
deq
unordered buffer
1
2
3
not fair if adequeue getsinterrupted
what happens when an enqueuegets delayed?
?
a|1
b|3
c|2
deq
deq
deq
unordered buffer
≤1
≤2
≤3
fair: if one dequeueis slow, another onewill return its elementearlier
if no young enough elementis found, the youngest available element is removed
not linearizable wrt. FIFO, but quiescently consistent
a|1
b|3
c|2
unordered buffer
time
deq
deq
deq
b
enq
a
enq
c
enq
c
a
≤1
≤2
≤3
2≤2
1≤3
youngestelement in thebuffer
removedout-of-order:not linearizablewrt. FIFO
b
FIFO Queue
Producer 1
Producer 2
Producer n
Consumer 1
Consumer 2
Consumer n
1:a
1:b
1:z
2:a
2:z
n:a
n:b
n:z
...
...
...
?:?
?:?
?:?
?:?
?:?
?:?
?:?
?:?
...
...
...
artificialdelay to controlcontention
1 millionelements
1 millionelements
...
...
0
1000
2000
3000
4000
5000
6000
2
10
20
30
40
50
60
70
80
operations per ms (more is better)
number of threads
gnuplot_plot_1
MS Queue
gnuplot_plot_2
TS Queue without optimization
gnuplot_plot_3
TS Queue with fair optimization
0
1000
2000
3000
4000
5000
6000
2
10
20
30
40
50
60
70
80
operations per ms (more is better)
number of threads
gnuplot_plot_1
MS Queue
gnuplot_plot_2
TS Queue without optimization
gnuplot_plot_3
TS Queue with fair optimization
The examples suggest that linearizability may come at the expense of performance and fairness.
Depending on the application linearizability may or may notbe the right correctness condition for concurrent FIFO queues.
Thank You
For more information about the queue implementations see http://scal.cs.uni-salzburg.at/