Welcome to Ethan’s Air Garden. This is dedicated to creating a computer technology column that can be read during commutes, meals, or before bed, which is both accessible and in-depth.
The theme of the lecture is “Introduction to Wait-Free Algorithms in C++ Programming,” presented by Daniel Anderson from CMU. This article records and summarizes the lecture and expands on related knowledge.
Keywords: C++, Algorithms, High Concurrency, Lock-Free Algorithms
1. Classification of Concurrency and Advanced Algorithms
The lecture first reviews the basics of concurrent programming and lock-free programming, introducing the vocabulary of progress guarantees used to measure the performance of concurrent algorithms:
-
Blocking: Cannot guarantee progress, as threads may be scheduled out while holding a lock (“going to lunch”), causing other threads to wait indefinitely.
-
Lock-Free: Guarantees that at least one thread in the system can make progress. This means that overall system throughput is guaranteed, but individual operations may “starve,” meaning they could take an arbitrary amount of time to complete.
-
Wait-Free: The “gold standard” of progress. It guarantees that all threads can make progress. Each operation will complete within a bounded number of steps, theoretically ensuring worst-case latency.
Interpretation: Differences in Algorithms
Blocking
Core Idea: When a thread cannot acquire a shared resource, it is suspended (blocked) until the resource is released.
How It Works: Typically implemented using locks (e.g., synchronized, ReentrantLock).
The thread attempts to acquire the lock; if the lock is held by another thread, the current thread is placed in a waiting queue and enters a blocked state.
Lock-Free
Core Idea: Threads are not blocked but instead try to acquire resources through spinning (busy-waiting).
How It Works: Typically implemented using atomic operations (e.g., CAS, Compare-and-Swap).
When threads operate on shared resources, they do not block but continuously retry until successful. Even if multiple threads operate simultaneously, only one thread can successfully modify the resource, while others will retry.
Wait-Free
Core Idea: Each thread can complete its operation in a limited number of steps without waiting for other threads.
How It Works: A stronger form of lock-free.
When a thread performs an operation, it does not need to wait for other threads to release resources and does not need to retry. Each thread’s operation can be completed in a limited time, independent of other threads’ execution.
It may be difficult to understand the implementation ideas of wait-free algorithms now, but we will discuss this later.
2. Motivational Problems and Lock-Free Design
The lecture uses the implementation of a “Sticky Counter” data structure as an example. This counter allows for increments and decrements, but once it reaches zero, it cannot be incremented again (i.e., it is “stuck” at zero). This is a non-fictional example in practical applications, such as the need for this mechanism in the C++ standard library’s std::weak_pointer::lock.
Interpretation: Practical Application of Sticky Counter
Reference counting is widely used in the kernel to manage the lifecycle of objects (such as memory pages, file descriptors, device structures, etc.). The Sticky Counter is well-suited for this scenario to ensure that objects are safely destroyed.
Workflow Example:
Assume the kernel creates a structure struct device *dev representing a hardware device.
Initialization: When the object is created, its reference counter (a sticky counter) is initialized to 1.
dev->ref_count = 1;Acquire Reference (Increment): When another kernel component (such as a driver or file system) needs to use this dev object, it calls a function to increase the reference count. At this point, ref_count becomes 2. This operation ensures that as long as there are components using the object, it will not be destroyed.
sticky_counter_inc(&dev->ref_count);Release Reference (Decrement): When a component is done using the dev object, it calls a function to decrease the reference count. At this point, ref_count returns to 1.
sticky_counter_dec(&dev->ref_count);Final Release (Destruction): When the last component using the object calls sticky_counter_dec, the counter drops to 0. At this point, ref_count becomes 0. The sticky effect triggers: the counter is now fixed at 0. If at this time a faulty or late component tries to acquire a reference to the dev object again and calls sticky_counter_inc:
sticky_counter_inc(&dev->ref_count);Since the counter is already 0, this increment operation will fail. The function may return false or -1, informing the caller that it can no longer acquire a reference.
This is the key point: it prevents operations on an object that has already been (or is about to be) destroyed, thus avoiding use-after-free vulnerabilities, which are among the most common and severe security vulnerabilities in the kernel.
Problems with Lock Implementation: Using mutexes solves thread safety issues but introduces blocking problems, leading to poor performance.
Lock-Free Design Method (Compare-Exchange Loop):
To implement a lock-free counter, atomic types (std::atomic) must be used. The core of lock-free design is the Compare-Exchange Loop (CAS Loop).
-
Read the current state.
-
Calculate the desired new state.
-
Use atomic operation compare_exchange to submit changes, succeeding only if the old state is still the expected value.
-
If it fails, retry (forming a potential unbounded loop).
The CAS Loop algorithm is typically lock-free because a failure of one thread means success for another (the system as a whole is still making progress). However, it is not wait-free, as theoretically, one thread could be “clobbered forever” by other threads, leading to an arbitrary time required for the operation.
Interpretation: Complete Code Comments
class StickyCounter {private: // Use atomic<int> to ensure thread safety std::atomic<int> count_;public: // Constructor, initializes the counter explicit StickyCounter(int initial_value) : count_(initial_value) { } // Decrement operation // Returns the value before decrementing int decrement() { // fetch_sub is an atomic operation, returning the value before the operation int old_value = count_.fetch_sub(1); std::cout << "Decrementing from " << old_value << " to " << (old_value - 1) << std::endl; return old_value; } // Increment operation (core "sticky" logic implemented here) // Returns whether the increment was successful bool increment() { int current = count_.load(); // Read current value // CAS loop, until successful or finds the counter is already 0 while (current > 0) { int new_val = current + 1; // Attempt to update count_ from current to new_val // This is an atomic operation // If count_'s current value is indeed current, update to new_val and return true // Otherwise, update current to the latest value of count_ and return false if (count_.compare_exchange_weak(current, new_val)) { std::cout << "Incrementing from " << (new_val - 1) << " to " << new_val << " - SUCCESS" << std::endl; return true; // Increment successful } // If compare_exchange_weak returns false, the loop continues // At this point, current has been updated to the latest value of count_ // We will check current > 0 again, and if so, retry } // If the loop exits, it means current <= 0 std::cout << "Cannot increment. Counter is already at 0 - FAILED" << std::endl; return false; // Increment failed } // Get current count value int get() const { return count_.load(); }};3. Wait-Free Algorithm Design: Cooperation and Helping
To implement a wait-free algorithm, potential unbounded CAS loops must be eliminated. While atomic read-modify-write (RMW) primitives such as compare_exchange, fetch_add, fetch_sub, and atomic_exchange are still needed, the key is to change the competitive relationship between threads.
The “Helping” Mechanism:
The core idea of wait-free design is cooperation rather than competition. When a thread finds that a data structure is in a state where another operation is ongoing, it does not preempt or block but helps complete that operation before attempting its own.
Metaphor: If the CAS loop in lock-free design is like a group of people trying to pass through a door, with only one person succeeding while others must retry; then the “help” mechanism in wait-free design is like everyone cooperating, ensuring that even if someone stumbles, others will help them up before passing through together, ensuring everyone can pass through the door smoothly within a limited time.
Implementation Details of Wait-Free Sticky Counter:
To implement the helping mechanism, threads need a way to detect and communicate ongoing operations. Since the core difficulty lies in how threads can synchronously determine whether the counter is zero, the lecture introduces the key idea of “stealing bits”:
Steal two bits from a 64-bit counter as flags.
“Is Zero Flag”: The top bit is used to synchronize indicating that the counter is zero; once set, other threads must treat it as zero, even if the actual lower bits are greater than zero.
Linearizability: In a simplified version without read operations, even if the bits in memory show zero, it can be claimed that the decrement operation occurred after the increment operation, because in cases of overlapping operations, external observers cannot prove the order is incorrect.
Interpretation: What is linearizability under parallel semantics?
In concurrent algorithms, operation linearizability means:
For all operations executed on a concurrent data structure (from different threads), we can find a global, linear sequence of operations that satisfies the following two conditions:
Correctness: This linear sequence must be “behaviorally correct.” That is, if these operations were indeed executed in this sequence on a single thread, the final state produced by the data structure and the return values of all operations must be exactly consistent with their results when executed concurrently.
Real-Time Order: This linear sequence must respect the actual occurrence time of each operation. For any two operations A and B, if operation A completely finishes in physical time before operation B starts, then in this linear sequence, A must precede B.
Challenges of Adding Read Operations: If read operations are allowed, they may observe the counter as zero, but then see the counter “resurrected” to one, violating linearizability.
Final Solution (Adding Helping and Help Flag): When a thread (e.g., a read operation) detects that the counter is zero, it helps the ongoing decrement operation set the zero flag. To resolve who will “claim” the responsibility of setting the counter to zero (which is crucial in reference counting, as the claimer is responsible for deleting the object), a second flag, the “Help Flag,” is introduced. The helper sets this flag, and then the thread attempting the decrement operation will clear this Help Flag through an atomic exchange operation, thus claiming to be the thread that sets the counter to zero.
4. Performance Analysis and Conclusion
The lecture emphasizes that performance should not be guessed blindly; theoretical assumptions should be made first, followed by benchmarking to verify.
Benchmark results indicate:
Under workloads with a high number of read operations (high contention), wait-free counters typically exhibit better latency performance.
Under workloads with a high number of write operations (low contention), lock-free algorithms (based on CAS Loop) may outperform when the number of threads is sufficiently high.
Conclusion:
The optimal algorithm depends on the specific workload (read-write ratio, number of threads or cores). Lock-free algorithms can be very fast if CAS loops do not occur.
Summary:
-
Classify algorithms through progress guarantees (Lock-Free vs. Wait-Free).
-
The key technique in wait-free algorithm design is cooperation (Helping).
-
Never guess performance (Don’t just guess and ship it), hypothesize first, then test.