31–40 of 56 posts
Nice writeup, enjoyed reading this. Instead of pointers to string literals, did you consider tokens instead, e.g. a big enum with a matching string table for the consumer? That's what we did in the past in device drivers although for space reasons instead of speed.
Earlier quoted context omitted.
The definition for lock free written there is the same as the one I wrote above. The crucial sentence is found in the second paragraph. Where non-blocking is the umbrella term covering both lock, wait and obstruction free algorithms. "In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads" Neither spin locks nor O…
I think I better understand what "lock-free" means now, thank you for the explanation. I will review what I said in my article and ensure I'm not spreading any misinformation. When I learned of lock-free I was presented with a spin-lock like system as an example, but that is clearly incorrect. The key I guess is that any thread could halt at any point and the other threads are not blocked (within obvious practical li…
"An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress)."
That definitely sounds like locks would be included. I am pretty sure that if my program runs for long enough that descheduled thread will get rescheduled and continue to make progress. And then there is the hand-wavy 'sensible definition of progress' what is that?
If we take an example from a single producer single consumer queue which is certainly non-blocking. With two methods.
// Returns true if o was successfully added to the queue, false otherwise
public boolean enqueue(Object o)
// Returns null if the queue is empty, otherwise returns a FIFO object
public Object dequeue()
If we suspend the producer then the consumer will eventually stop returning objects from dequeue() and just return null. If we suspend the consumer then the producer will eventually start returning false from enqueue(). In either of these cases we could definitely argue that our system has stopped making progress and the definition 'actually enqueue or dequeue some useful thing' seems like a sensible one. But this definition should really just be 'always return from enqueue or dequeue' and this second definition allows us to say our queue is non blocking.
It's pretty hard to pin down what constitutes a 'sensible definition of progress'. For a user space spin lock saying that a thread continues to spin in a tight loop could be a sensible definition of progress, but isn't helpful for our purposes of deciding if an algorithm or data structure is non blocking. This trickiness makes it surprisingly difficult to coherently discuss non-blocking x-free algorithms.
(Luckily, in practice, these algorithms are so much fun that it is worth the difficulty :)
Another approach is just to use two stacks, one for writing and one for flushing. User threads write log lines directly to buffers from an allocator usually via a TLS mediated stream. The use of an allocator avoids locking on system calls during memory allocation and minimizes copying between user code and eventual flush to disc/network. Buffers are written to the write stack using atomic CAS, if no buffers are avail…
Thanks for sharing this technique. Are you aware of any existing open source implementations?
Earlier quoted context omitted.
How would there be many requests? Wouldn't it load the cache line once into the shared state and then spin waiting for the line to be invalidated before reloading?
Honestly, I don't know how this interacts with cache lines. As far as I know, Intel has not released any official details about what the PAUSE instruction does other than that it slows down spin loops to a reasonable rate. The best source I know of for this information is the Intel® 64 and IA-32 Architectures Optimization Reference Manual ( http://www.intel.com/content/dam/www/public/us/en/documents/... ). It is fair…
Coherence wise it won't interfere with other cores and their access to memory.
That said how hyper-threads share CPU resources is a moving target. My understanding through hearsay is that in the past many resources were statically partitioned with hyper-threading enabled, but now things are moving towards allocating resources dynamically which means that a thread wasting resources would be sucking up capacity that could be used by another hyper-thread.
Earlier quoted context omitted.
Thanks for sharing this technique. Are you aware of any existing open source implementations?
Unfortunately no, thus far i have only implemented it in a commercial context as part of a high frequency trading system.
Another approach is just to use two stacks, one for writing and one for flushing. User threads write log lines directly to buffers from an allocator usually via a TLS mediated stream. The use of an allocator avoids locking on system calls during memory allocation and minimizes copying between user code and eventual flush to disc/network. Buffers are written to the write stack using atomic CAS, if no buffers are avail…
Earlier quoted context omitted.
I think I better understand what "lock-free" means now, thank you for the explanation. I will review what I said in my article and ensure I'm not spreading any misinformation. When I learned of lock-free I was presented with a spin-lock like system as an example, but that is clearly incorrect. The key I guess is that any thread could halt at any point and the other threads are not blocked (within obvious practical li…
It's a very tricky collection of definitions. All descriptions of it are a bit vague. For instance under lock-free on wikipedia we read "An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress)." That definitely sounds like locks would be included. I am pretty sure that if my program runs for…
At least in practice the decision to use one or the other would come from variance guarantees. From this view we can define a "practical" meaning to each one.
* blocking: very high variance in operation time
* lock-free: lower average, likely lower variance, but prone to spikes
* wait-free: lowest variance, approaching zero, cannot have spikes
Nice writeup, enjoyed reading this. Instead of pointers to string literals, did you consider tokens instead, e.g. a big enum with a matching string table for the consumer? That's what we did in the past in device drivers although for space reasons instead of speed.
That's essentially what pointers to string literals are. They are indexes into a constant data segment which contains the actual strings.
Question: for these higher-level systems, is it possible to prevent preemption for a very short time? I'm guessing that a userland app can't do that easily but if it could then that would effectively give you larger atomic operations, which can aid in implementing lock-free solutions.