Closes #770 (requested: make UnboundedWSQ safe for concurrent push without external locking).

Problem

Every push to an overflow buffer acquires a std::mutex, incurring a futex syscall on Linux or SRWLock contention on Windows, plus potential thread parking. The steal path is already lock-free via CAS on _top. Every task spill pays kernel overhead that every steal does not.

// Before: kernel-weight lock on every push
struct Buffer {
  std::mutex mutex;
  UnboundedWSQ<Node*> queue;
};

Solution

Replace the external std::mutex with a per-queue std::atomic_flag spinlock (_resize_lock) inside UnboundedWSQ. Remove the mutex from Buffer entirely.

push acquires the flag with test_and_set(acquire) and _mm_pause spinning, writes the item to the array slot, advances _bottom with a release store, then clears the flag. Total time under lock: one array slot write plus one atomic store, measured in nanoseconds on an uncontended cache line.

resize acquires the same flag before allocating and copying. Since both operations hold the same flag, resize can never observe a slot that a pusher has claimed but not yet written.

steal, pop, and steal_with_feedback are the original Chase-Lev algorithm, completely unchanged.

// After: spinlock held for nanoseconds, steal path untouched
struct Buffer {
  UnboundedWSQ<Node*> queue;  // push internally serialized via _resize_lock
};

Key design insight

Items are written to the array before _bottom is advanced. A stealer that loads _bottom with acquire synchronizes with the pusher's _bottom.store(release) via the C++ release-sequence rule. By the time any stealer sees the new _bottom value, the item is already visible. No spin-wait is needed. No null sentinel is needed. No slot clearing after consumption is needed.

Why fully lock-free push is not viable with dynamic resize

Three approaches were implemented and stress-tested before reaching this design. Each fails due to a structural race between the array pointer and concurrent writes.

Attempt 1: CAS on _bottom, re-read _array in steal.
The pusher CAS-claims slot b, then loads _array and writes to it. A resize can install a new array after the CAS but before the write. The resize copies null for slot b (nothing written yet) into the new array. The pusher writes to the old array. The stealer loads the new array and sees null at slot b forever.

Attempt 2: Resize spins on null slots before copying.
Resize spin-waits for each null slot to become non-null before copying it. But after resize publishes the new array, the pusher re-reads _array and now holds a pointer to the new array, writing its item there. Resize is spinning on the old array waiting for a write that went to the new one. Deadlock.

Attempt 3: Stable-write loop.
After writing, the pusher checks if _array changed and rewrites if so. A second resize can occur between the check and the rewrite, installing a third array that copied null from the second. The stealer reads the third array and sees null.

Root cause: resize and multi-producer push share the array pointer. Any operation that reads the pointer and then writes based on that read can be invalidated by a resize between the read and the write. Mutual exclusion on the write path is structurally required. The steal path has no such constraint and remains lock-free.

Spinlock contention profile

The spinlock contends in exactly two situations:

1. Two pushers arrive simultaneously. One spins for nanoseconds while the other completes its write. This is the hot-path case.
2. A pusher and a resize arrive simultaneously. This occurs at most O(log N) times over the queue lifetime, where N is the total items ever pushed.

The steal path never touches the spinlock.

Changes

taskflow/core/wsq.hpp

• Added std::atomic_flag _resize_lock member.
• push(T): acquire spinlock, resize if needed, write item, _bottom.store(release), release.
• bulk_push(I, N): acquire spinlock, resize loop until N items fit, write N items, _bottom.store(release), release.
• steal(), pop(), steal_with_feedback(): unchanged from original Chase-Lev.
• Removed Array::clear() and null-sentinel machinery.

taskflow/core/executor.hpp

• Removed std::mutex mutex from Buffer.
• Removed std::scoped_lock in _spill and _bulk_spill.
• All steal paths, the notifier protocol, and executor shutdown are unchanged.

unittests/test_mpmc_wsq.cpp (new)

• 11 stress tests covering multi-producer contention, resize under contention, burst bulk_push, near-empty thrashing, mixed bulk and single push, deadlock detection, executor integration, and shutdown.

Test results

All tests pass with zero warnings under MSVC /W4 /WX /std:c++20 /O2.

The stress tests cover interleavings the existing regression suite cannot reach because those tests were written for single-producer semantics:

• PurePushContention: 16 threads, 1 million items each, uniqueness verified after drain.
• ConcurrentPushSteal: 8 producers, 8 stealers, 10 million items, completeness and uniqueness verified.
• ResizeUnderContention: queue starts at capacity 8, 4 producers and 4 stealers force dozens of array doublings under concurrent access.
• BurstBulkPush: single bulk_push of 1 million items with 15 simultaneous stealers, 5 rounds. Models the OpenTimer workload.
• NearEmptyThrashing: 8 stealers race on a queue with one item at a time, 100,000 iterations.
• MixedBulkAndSinglePush: 4 bulk_push threads and 4 single-push threads compete on the same _bottom, 5 million total items.
• ResizeLockNoDeadlock: 8 threads push without stealers consuming, forcing continuous resize. Timeout fires if the spinlock deadlocks.
• ExecutorIntegration: tf::Executor with 10,000 root tasks each spawning 100 sub-tasks, 5 rounds.
• ShutdownDuringPushSteal: executor destroyed while tasks are being pushed and stolen. Verifies clean shutdown.