Name
Abstract | ||
|---|---|---|
We introduce the notion of a k-FIFO queue which may dequeue elements out of FIFO order up to a constant k≥0. Retrieving the oldest element from the queue may require up to k+1 dequeue operations (bounded lateness), which may return elements not younger than the k+1 oldest elements in the queue (bounded age) or nothing even if there are elements in the queue. A k-FIFO queue is starvation-free for finite k where k+1 is what we call the worst-case semantical deviation (WCSD) of the queue from a regular FIFO queue. The WCSD bounds the actual semantical deviation (ASD) of a k-FIFO queue from a regular FIFO queue when applied to a given workload. Intuitively, the ASD keeps track of the number of dequeue operations necessary to return oldest elements and the age of dequeued elements. We show that a number of existing concurrent algorithms implement k-FIFO queues whose WCSD are determined by configurable constants independent from any workload. We then introduce so-called Scal queues, which implement k-FIFO queues with generally larger, workload-dependent as well as unbounded WCSD. Since ASD cannot be obtained without prohibitive overhead we have developed a tool that computes lower bounds on ASD from time-stamped runs. Our micro- and macrobenchmarks on a state-of-the-art 40-core multiprocessor machine show that Scal queues, as an immediate consequence of their weaker WCSD, outperform and outscale existing implementations at the expense of moderately increased lower bounds on ASD. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33078-0_20 | ICA3PP |
Keywords | Field | DocType |
concurrent fifo queue,unbounded wcsd,regular fifo queue,oldest element,scal queue,constant k,dequeue operation,finite k,k-fifo queue,so-called scal queue,lower bound | FIFO (computing and electronics),Multilevel queue,Computer science,Parallel computing,Queue,Multiprocessing,Priority queue,Fork–join queue,Queue management system,Double-ended queue,Distributed computing | Conference |
Citations | PageRank | References |
14 | 0.69 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| christoph m kirsch | 1 | 526 | 49.50 |
| Hannes Payer | 2 | 204 | 16.35 |
| Harald Röck | 3 | 60 | 4.96 |
| Ana Sokolova | 4 | 254 | 18.88 |