York 2014
image/svg+xml
York 2014
2014-03-04
Andreas Haas
##
/
##
MASTER SLIDE
University of York, March 2014
Fairness vs. Correctnessin a Concurrent FIFO Queue
Mike Dodds
University of York
Andreas Haas
University of Salzburg
Christoph M. Kirsch
University of Salzburg
time
b
deq
a
deq
b
enq
a
enq
time
b
deq
a
deq
b
enq
a
enq
correct wrt. FIFO
incorrect wrt. FIFO
time
b
deq
a
deq
b
enq
a
enq
time
b
deq
a
deq
b
enq
a
enq
linearizable wrt. FIFO
linearizable wrt. FIFO
linearization points
time
b
deq
c
deq
b
enq
a
enq
time
c
deq
a
deq
b
enq
a
enq
linearizable wrt. FIFO
not linearizable wrt. FIFO
c
enq
c
enq
deq
a
b
deq
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
linearizable wrt. FIFO
find and remove the oldest elementfirst
a|1
b|3
c|2
unordered buffer
deq
deq
deq
contention
elements withtimestamps
time
b
enq
a
enq
c
enq
a|1
b|3
c|2
unordered buffer
because a will be removed by the otherdequeue
because a will be removed by the otherdequeue
time
deq
deq
deq
b
enq
a
enq
c
enq
a
c
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 old enough elementis found, the oldest 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
oldestelement in thebuffer
removedout-of-order:not linearizablewrt. FIFO
b
time
b
enq
a
enq
c
enq
a|1
b|3
c|2
unordered buffer
deq
deq
deq
contention
time
b
enq
a
enq
c
enq
a|1
b|1
c|1
unordered buffer
deq
deq
deq
concurrent enqueues allow faster dequeues
time
b
enq
a
enq
c
enq
artificial extensioncan creates more"concurrent" enqueues
a|
b|
c|
unordered buffer
1:3
2:5
4:6
unordered
unordered
ordered
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
MS Queue
TS Queue without optimization
TS Queue with fair optimization
TS Queue with interval optimization (delay=15us)
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
MS Queue
TS Queue without optimization
TS Queue with fair optimization
TS Queue with interval optimization (delay=15us)
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
MS Queue
TS Queue without optimization
TS Queue with fair optimization
TS Queue with interval optimization (delay=20us)
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/