3 ms·

You can use RCU to do this, but I'd argue that everything else ends up being more or less a lock by another name (maybe you could do read/write where the read i

You can use RCU to do this, but I'd argue that everything else ends up being more or less a lock by another name (maybe you could do read/write where the read is optimistic, but at least the write side will have some sort of lock). I'm curious what you had in mind?

deleted 5y ago
[deleted]
gpderetta 5y ago
I misplaced my copy of The Art Of Multiprocessor Programming with the details, but with a simple CAS primitive you can build a general N-CAS algorithm and from that implement any algorithm ina a truly wait free way. It will be slow and won't scale, but will indeed be wait free
PaulDavisThe1st 5y ago
Most RCU requires a lock, if only to handle cleaning up the "dead wood" that occurs on every update (write).
- MaxGanzII 5y ago
  Lock-free garbage collection exists and there's quite a body of literature.
  - PaulDavisThe1st 5y ago
    Yeah, I've read a lot of it. It all comes with caveats and potential performance issues.
    - MaxGanzII 5y ago
      Seemed okay to me with regard to caveats. Performance issues -> it's lock-free and scales profoundly better than non-lock-free.
PaulDavisThe1st 5y ago
You can do this sort of thing with write-ordering a "generation counter" that is updated before and after writing a bunch of other data elements. The problem is that it makes the read slow - you have to use a CAS-style loop even to read anything (you must check that the generation counter has the same value before and after reading the other data). It also adds more memory barriers than a simple lock.
- atq2119 5y ago
  This is the mechanism that I had in mind. It's actually a really good one if you have lots of concurrent reads and few writes because there isn't going to be any cacheline ping pong. With a more traditional read-write lock, even the readers write to the cacheline holding the lock, and that's a shared cacheline so it's going to ping pong around. By contrast, the generation counter is read-only to readers. But consider: the generation counter effectively acts as a lock that locks out reader threads while the update takes place. It also serves to lock out other writer threads. So yes, one can call that "lock-free" if one really wants to, but I find it more honest to just admit that it's a custom lock with custom properties.
  - PaulDavisThe1st 5y ago
    It's not lock-free, it's wait-free and therein lies the problem. The reader thread(s) are not locked out - they are free to continue running, endlessly looping waiting for the moment when they can consistently read the pseudo-atomic data. That's quite different behavior than if they used a lock, which they would find already held, and they would sleep.
    - gpderetta 5y ago
      But it is not wait-free, not even non blocking; if I understand your model correctly, a writer blocked in the right moment will prevent a reader to make progress exactly as you described. Edit: with double buffering I guess it would be lock free, but still not wait free as a fast producer can still starve consumers indefinitely. /Pedantic

deleted 5y ago

[deleted]

gpderetta 5y ago

I misplaced my copy of The Art Of Multiprocessor Programming with the details, but with a simple CAS primitive you can build a general N-CAS algorithm and from that implement any algorithm ina a truly wait free way. It will be slow and won't scale, but will indeed be wait free

PaulDavisThe1st 5y ago

Most RCU requires a lock, if only to handle cleaning up the "dead wood" that occurs on every update (write).

MaxGanzII 5y ago
Lock-free garbage collection exists and there's quite a body of literature.
- PaulDavisThe1st 5y ago
  Yeah, I've read a lot of it. It all comes with caveats and potential performance issues.
  - MaxGanzII 5y ago
    Seemed okay to me with regard to caveats. Performance issues -> it's lock-free and scales profoundly better than non-lock-free.

PaulDavisThe1st 5y ago

You can do this sort of thing with write-ordering a "generation counter" that is updated before and after writing a bunch of other data elements. The problem is that it makes the read slow - you have to use a CAS-style loop even to read anything (you must check that the generation counter has the same value before and after reading the other data). It also adds more memory barriers than a simple lock.

atq2119 5y ago
This is the mechanism that I had in mind. It's actually a really good one if you have lots of concurrent reads and few writes because there isn't going to be any cacheline ping pong. With a more traditional read-write lock, even the readers write to the cacheline holding the lock, and that's a shared cacheline so it's going to ping pong around. By contrast, the generation counter is read-only to readers. But consider: the generation counter effectively acts as a lock that locks out reader threads while the update takes place. It also serves to lock out other writer threads. So yes, one can call that "lock-free" if one really wants to, but I find it more honest to just admit that it's a custom lock with custom properties.
- PaulDavisThe1st 5y ago
  It's not lock-free, it's wait-free and therein lies the problem. The reader thread(s) are not locked out - they are free to continue running, endlessly looping waiting for the moment when they can consistently read the pseudo-atomic data. That's quite different behavior than if they used a lock, which they would find already held, and they would sleep.
  - gpderetta 5y ago
    But it is not wait-free, not even non blocking; if I understand your model correctly, a writer blocked in the right moment will prevent a reader to make progress exactly as you described. Edit: with double buffering I guess it would be lock free, but still not wait free as a fast producer can still starve consumers indefinitely. /Pedantic