Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Semaphores Augmented with a Waiting Array

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Ticket-lock ideas give semaphores fairness and scalable throughput.

desk verdict TWA-Semaphore has a real liveness bug when LongTermThreshold=0, a configuration the paper itself recommends; the core idea is still plausible but the claims need reining in. read the letter →

arxiv 2501.18447 v3 pith:PBPXSEOM submitted 2025-01-30 cs.DC

Dave Dice , Alex Kogan This is my paper · ORCID
classification cs.DC
keywords semaphoresticketlockswaitingarrayscalablesynchronizationmutualexclusionconcurrencycontrolfutexfirst-come-first-served
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that semaphores can be made both fair and scalable by borrowing the ticket-lock idea and then adding a shared hashed waiting array. The first step is the ticket-semaphore, which uses two counters, ticket and grant, to give strict first-come-first-served admission but suffers from global spinning under contention. The second step, the TWA-semaphore, replaces most of that global spinning with semi-local waiting on hashed buckets, so only the thread nearest the front spins on the shared counters. If the central claim holds, the result is a semaphore that is compact, fair in admission order, and degrades far more gracefully than a plain ticket-semaphore as threads pile up.

What carries the argument

The machinery is a pair of counters, ticket and grant, plus a fixed table of wait buckets with a ticket-aware hash. In take, a thread fetch-and-adds the ticket counter to get its admission number; in post, a thread atomically increments grant. The hash adds the semaphore address to 17 times the ticket value and masks the result into a 2048- or 4096-entry table, so consecutive tickets from one semaphore walk through the table and waiting is diffused. Two-phase waiting is governed by a tunable LongTermThreshold: waiters close to the head spin directly on grant, while distant waiters watch a per-bucket UpdateSequence counter for notification. This arrangement concentrates global coherent traffic on at most one thread per semaphore and overlaps handover with staging of the next long-term waiter.

What would settle it

Instrument the waiting array to count how often a bucket holds more than one waiting thread while running semabench with a single semaphore at high thread counts and with many semaphores whose post operations are synchronized so their ticket streams advance in lockstep; if the collision rate grows with thread count or with the number of lockstep semaphores, and throughput falls toward ticket-semaphore levels, the general scalability claim fails.

Watch

Extended reading notes

Core claim

The central claim is that the TWA-Semaphore delivers first-come-first-served, or more precisely first-come-first-enabled, admission order while remaining compact and offering very low latency, because long-term waiters wait on a fixed shared array instead of hammering the semaphore's counters. A thread takes a ticket with fetch-and-add and immediately enters if its ticket is already covered by the grant count; otherwise it spins briefly on grant when it is near the front, and, when it is far from the front, waits on the bucket selected by hashing the semaphore address plus its ticket value. A post increments grant and then pokes the bucket corresponding to the new grant value, staging the successor's successor to shift from long-term to short-term waiting. The benchmark against a ticket-semaphore and the pthread semaphore shows the TWA version matching at low thread counts and pulling ahead as contention rises.

Load-bearing premise

The load-bearing assumption is that collisions in the shared waiting array are rare, meaning that in general only one thread waits on a given bucket at a time; if unrelated semaphores advance tickets in lockstep or the table is too small, the scalability advantage erodes.

Editorial extensions

If this is right

  • A semaphore can be built from two counters and a shared table, with no per-semaphore queue nodes, while still giving ticket-order admission.
  • Under high thread counts the TWA-semaphore's throughput degrades more gracefully than the ticket-semaphore's, because only the front waiter spins on the grant counter.
  • The same transform can be applied to other ticket-based constructs, such as eventcounts and sequencers, to give them the same scalability.
  • Long-term waiters can be blocked in the kernel via futexes or park-unpark without adding per-semaphore kernel objects, because waiting is already dispersed over many addresses.
  • Setting the long-term threshold to zero removes all spinning; tuning it trades handover latency against coherence traffic.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The scalability result is workload-dependent: if many semaphores release in lockstep, their ticket streams can entrain, and the fixed table could produce sustained collisions that push the algorithm back toward global spinning; a stress test with synchronized releases across many semaphores would quantify this.
  • A table sized to the number of logical CPUs, or a hash that rotates through sub-pages of the table, may make the waiting pattern more predictable for streams of consecutive tickets; the paper sketches these variants but does not evaluate them.
  • Because collisions cause spurious wakeups, the waiting-chain design could double as a general address-based waiting service, so the same scalability might transfer to condition variables and other blocking primitives, not just semaphores.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes two semaphore algorithms: Ticket-Semaphore, a direct adaptation of ticket locks, and TWA-Semaphore, which applies the waiting-array idea from the authors' earlier TWA lock to reduce global spinning. The abstract and text claim that TWA-Semaphore is compact, scalable, of extremely low latency, and fair, with first-come-first-served (or, more precisely, first-come-first-enabled) admission order. Additional waiting-chain and monitor-style variants are sketched in Listings 3-5, intended to support futex- or park-based waiting. The evaluation reports median throughput on one Oracle X5-2 machine, comparing TWA-Semaphore with Ticket-Semaphore and with the pthread semaphore.

Significance. If the algorithm were correct as printed, TWA-Semaphore would be a useful compact FIFO-style semaphore: it preserves the two-counter state of a ticket semaphore, diffuses waiting across a shared array, and is accompanied by a thoughtful discussion of futex, park-unpark, and monitor-style waiting strategies, as well as an explicit acknowledgment of the collision/predictability tradeoff. The paper also includes a direct comparison against an external baseline (pthread), which is a strength. However, as written, the core Listing 2 has a liveness bug that prevents the algorithm from working for more than two concurrent waiters, so the central scalability claim cannot be accepted without correction and re-evaluation.

major comments (3)
  1. [Listing 2; Section 2 (LongTermThreshold discussion)] The notification scheme in SemaPost is shifted by one relative to the admission predicate, so the algorithm is not live even with the default LongTermThreshold=1. Before a post, let Grant=G. SemaTake admits a waiter only when Grant>tx, and it long-term-waits on bucket TWAHash(S,tx) whenever Grant-tx+LongTermThreshold<=0. Hence a waiter with ticket G spins, while a waiter with ticket G+1 is long-term-waiting on bucket G+1. When a post sets Grant=G+1, the waiter with ticket G is admitted and the waiter with ticket G+1 is exactly the one that must be re-awakened to take over the spin role. SemaPost, however, pokes TWAHash(S, g) with g=(G+1)+LongTermThreshold, i.e., bucket G+2 with the default, and the fast-path test g-Ticket.load()>=0 returns without poking when the highest assigned ticket is G+1. Consequently the G+1 waiter is never awakened; with three threads this deadlocks on the first post. The same off-by-one invalidates the explicit statement in Section 2 that setting LongTermThreshold to 0 simply eliminates spinning: with LTT=0 the post pokes bucket G+1 while the waiter needing the wakeup holds ticket G. The notification index should be TWAHash(S, (G+1)+LongTermThreshold-1) and the fast-path cut should be g-Ticket.load()>0. As printed, the benchmark results in Section 3 cannot have been produced by Listing 2.
  2. [Section 3, Figure 1] The performance claim is not supported with the reported methodology. Only a median of 11 runs on one X5-2 machine is shown, without error bars, without any direct latency measurement, and without comparison to a second scalable semaphore baseline; the pthread semaphore is not a scalable FIFO implementation. The abstract's 'extremely low latency' is never measured directly, since the throughput of a critical-section loop conflates handover latency, queueing delay, and post cost. The authors should report per-run dispersion, add at least one additional platform, and include a scalable semaphore baseline, or they should temper the 'state-of-the-art performance at both low and high contention levels' claim in the Conclusion.
  3. [Abstract; Section 'TWA-Semaphore'] The fairness claim is stated in the abstract as 'first-come-first-served (FCFS) admission order', but the text then narrows this to 'first-come-first-enabled'. These are different properties: once a thread is enabled by the grant condition it can be preempted before returning from SemaTake, so a later thread may enter the critical section first. Moreover, no proof or invariant is given even for the weaker first-come-first-enabled property. The argument should at least state the invariant that Grant is monotonically increasing and that SemaTake returns only when Grant>tx, and it should address whether the futex/chain variants in Listings 3-5 preserve this property under hash collisions and spurious wakeups.
minor comments (5)
  1. [Throughout] There are numerous typographical and OCR-like artifacts, including 'Lo ng Te rm Thr es ho ld' in Listing 2, 'MONITOR-MW AIT', 'magntitude', 'semphore', 'taylored', and 'implemeneted'; these should be cleaned before publication.
  2. [Listing 2, TWAHash] TWAHash(S, tx) accepts a uint32_t ticket value while Ticket and Grant are declared as uint64_t; the listing should state the intended truncation behavior or widen the parameter, otherwise the hash changes if ticket values ever reach 2^32.
  3. [Listings 3 and 4, Poke] The assertion assert(e->Gate == 0) in Poke is racy: a concurrent flush can set Gate between the check and the store. Either remove the assertion or justify it under the claimed synchronization discipline.
  4. [Listing 3, WaitElement] Poke reads e->Who, but the WaitElement field is declared as 'who'; as written, the snippet does not compile.
  5. [Section 3] The paper would benefit from stating whether the experimental code is available for reproduction, since the printed listings appear inconsistent with the reported results.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the TWA-Semaphore derivation is a self-contained algorithmic transformation with direct, externally benchmarked evaluation; self-citations are not load-bearing.

full rationale

No significant circularity. The paper's derivation chain is an algorithmic transformation: Ticket-Semaphore uses fetch_add on Ticket and magnitude comparison against Grant (Listing 1), and TWA-Semaphore (Listing 2) replaces long-term global spinning with a hashed waiting array, borrowing from prior TWA lock work [4,5]. The FCFS claim follows directly from wait-free fetch_add ticket order and monotonic Grant, not from a fitted parameter or from the claim itself. The performance evaluation compares against pthread and Ticket-Semaphore with no fitted model; the admitted collision sensitivity is a stated limitation, not a circular input. Self-citations [4,5,8] are to prior published work by the authors, but the semaphore result does not reduce to those citations: correctness arguments are given in the listings, and the waiting-chain variant cites an external pop-stack construction [2]. No equation is defined in terms of the target claim, and no prediction is statistically forced by a fit. The LTT=0 configuration concern raised elsewhere is a liveness/correctness issue, not a circularity issue.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

No new entities are introduced. The waiting array, buckets, and wait chains are inherited from the authors' prior TWA work and standard park-unpark/futex facilities. The ticket-semaphore is a restatement of Reed-Kanodia sequencer/eventcount.

free parameters (3)
  • LongTermThreshold = 1 (default)
    Threshold for switching between global spinning and semi-local waiting via the waiting array. The paper states the optimal value is platform-specific (Listing 2).
  • TableSize = 2048 (Listing 2), 4096 (Listings 3-5)
    Size of the shared waiting array, marked as a tunable parameter and chosen as 'proportional to the number of logical CPUs'; affects collision rate and cache behavior.
  • TWAHash multiplier constant = 17
    Multiplication constant in TWAHash(), chosen ad hoc to be coprime with the table size and to spread adjacent ticket values across cache lines; no empirical tuning is reported.
assumptions (4)
  • domain assumption The underlying atomic fetch-and-add primitive is wait-free and linearizable, preserving ticket order.
    Used to justify strict FCFS admission (Section 'Ticket-Semaphore').
  • domain assumption 64-bit Ticket and Grant counters will not overflow during the lifetime of the program (less than 200 years at 1 increment/ns).
    Section 'Ticket-Semaphore' overflow argument for magnitude-based comparisons.
  • ad hoc to paper Hash collisions in the waiting array are rare enough that at most one thread waits on a bucket at a time.
    Load-bearing for scalability; the paper itself flags in Section 3 that collisions from unrelated threads/locks can reduce predictability, and Listing 2 states 'we expect in general... only one thread waits on a given bucket'.
  • domain assumption The hardware cache-coherence protocol and PAUSE behavior make short-term global spinning cheaper than long-term waiting.
    Section 'Waiting Strategies' motivates the threshold design; no quantitative model is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Semaphores Augmented with a Waiting Array." pith.science (2026). https://pith.science/paper/PBPXSEOM

@misc{pith2026250118447,
  author       = {Pith},
  title        = {Pith review of: Semaphores Augmented with a Waiting Array},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PBPXSEOM}},
  note         = {Machine review of arXiv:2501.18447}
}
read the original abstract

Semaphores are a widely used and foundational synchronization and coordination construct used for shared memory multithreaded programming. They are a keystone concept, in the sense that most other synchronization constructs can be implemented in terms of semaphores, although the converse does not generally hold. Semaphores and the quality of their implementation are of consequence as they remain heavily used in the Linux kernel and are also available for application programming via the pthreads programming interface. We first show that semaphores can be implemented by borrowing ideas from the classic ticket lock algorithm. The resulting "ticket-semaphore" algorithm is simple and compact (space efficient) but does not scale well because of the detrimental impact of global spinning. We then transform "ticket-semaphore" into the "TWA-semaphore" by the applying techniques derived from the "TWA - Ticket Locks Augmented with a Waiting Array" algorithm, yielding a scalable semaphore that remains compact and has extremely low latency.

Figures

Figures reproduced from arXiv: 2501.18447 by the authors.

Figure 1
Figure 1. Semaphore Benchmark 4 Conclusion Our approach allows the construction of simple yet scal￾able semaphores. The exhibit state-of-the-art performance at both low and high contention levels, and are compact, with a highly constrained impact on space. They can be easily taylored to use futexes or parking, making them a practical choice for real-world software. Any structure that uses a lock to protect hash chains Referen… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages

  1. [1]

    Yehuda Afek, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit

    work page

  2. [2]

    Avis and M

    D. Avis and M. Newborn. 1981. On pop-stacks in series. Utilitas Math. 19 (1981), 129–140

    work page 1981

  3. [3]

    Dave Dice. 2015. Malthusian Locks. CoRR abs/1511.06035 (2015). arXiv:1511.06035 http://arxiv.org/abs/1511.06035

    work page Pith review arXiv 2015

  4. [4]

    Dave Dice and Alex Kogan. 2019. TWA – Ticket Locks Augmented with a Waiting Array. In Euro-Par 2019: Parallel Processing . https: //doi.org/10.1007/978-3-030-29400-7_24

    work page doi:10.1007/978-3-030-29400-7_24 2019

  5. [5]

    Dave Dice and Alex Kogan. 2019. TWA – Ticket Locks Augmented with a Waiting Array. (2019). arXiv:1810.01573 [cs.OS]

    work page Pith review arXiv 2019

  6. [6]

    Dave Dice and Alex Kogan. 2020. Fissile Locks. arXiv:2003.05025 [cs.OS] https://arxiv.org/abs/2003.05025

    work page Pith review arXiv 2020

  7. [7]

    Dave Dice and Alex Kogan. 2021. Fissile Locks. In Networked Systems – NETYS. https://doi.org/10.1007/978-3-030-67087-0_13

    work page doi:10.1007/978-3-030-67087-0_13 2021

  8. [8]

    Dave Dice and Alex Kogan. 2021. Ready When You Are: Efficient Con- dition Variables via Delegated Condition Evaluation. arXiv:2105.06961 https://arxiv.org/abs/2105.06961

    work page Pith review arXiv 2021

Show all 18 references
  1. [9]

    Dijkstra

    Edsger W. Dijkstra. undated, 1962 or 1963. Over de sequentialiteit van procesbeschrijvingen. (EWD-35) E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)

    1962

  2. [10]

    Allen B. Downey. 2016.The Little Book of Semaphores. Green Tea Press. https://greenteapress.com/semaphores/LittleBookOfSemaphores. pdf 4 2025-04-23 • Copyright Oracle and or its affiliates

    2016

  3. [11]

    M. J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodin. 1979. Resource allocation with immunity to limited process failure. In 20th Annual Symposium on Foundations of Computer Science (FOCS 1979) . http: //dx.doi.org/10.1109/SFCS.1979.37

    1979 doi

  4. [12]

    Hubertus Franke, Rusty Russel, and Matthew Kirkwood. [n.d.]. Fuss, Futexes and Furwocks: Fast User-level Locking in Linux. https://www. kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf . Ottawa Linux Symposium

    2002

  5. [13]

    Doug Lea. 2005. The java.util.concurrent synchronizer framework. Science of Computer Programming (2005). https://doi.org/10.1016/j. scico.2005.03.007 Special Issue on Concurrency and synchonization in Java programs

    2005 doi

  6. [14]

    Jouni Leppäjärvi. 2008. A pragmatic, historically oriented sur- vey on the universality of synchronization primitives. http: //www.enseignement.polytechnique.fr/informatique/INF431/X09- 2010-2011/AmphiTHC/SynchronizationPrimitives.pdf

    2008

  7. [15]

    Mellor-Crummey and Michael L

    John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithms for Scalable Synchronization on Shared-memory Multiprocessors. ACM Trans. Comput. Syst. (1991). http://doi.acm.org/10.1145/103727.103729

    1991

  8. [16]

    Reed and Rajendra K

    David P. Reed and Rajendra K. Kanodia. 1979. Synchronization with Eventcounts and Sequencers. Commun. ACM (1979). http://doi.acm. org/10.1145/359060.359076

    1979

  9. [17]

    rep ; nop

    U. Verner, A. Mendelson, and A. Schuster. 2017. Extending Amdahl’s Law for Multicores with Turbo Boost. IEEE Computer Architecture Letters (2017). https://doi.org/10.1109/LCA.2015.2512982 5 Appendix : Listings 5 2025-04-23 • Copyright Oracle and or its affiliates Dave Dice and...

    2017

  10. [1994]

    ACM Trans

    A bounded first-in, first-enabled solution to the l-exclusion problem. ACM Trans. Program. Lang. Syst. (1994). https://doi.org/10. 1145/177492.177731

    1994

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.