4 ms·
> Make any data structure wait-free as long as it has a copy constructor I'm going to hazard a guess that in many cases, a simple mutex (or even better, stripe
by banachtarski 7y ago
> Make any data structure wait-free as long as it has a copy constructor
I'm going to hazard a guess that in many cases, a simple mutex (or even better, striped mutexes) will perform better.
- gpderetta 7y agoa simple mutex will never be wait free and as such is never appropriate where a wait free data structure is required (it is not about performance).
- banachtarski 7y agoMaybe not but I can count on one hand the number of times I've truly needed that property. Compare to a try-lock or a timed lock for example.
- wrl 7y agoIn soft/firm/hard real-time, we can't use mutexes at all. Lock/wait-free is our bread and butter.
- banachtarski 7y agoDid you mean to include "soft" there? And I've never heard of "firm" real time.
- chrisseaton 7y ago...but that's not wait free? What happens if a processes crashes or a thread is de-scheduled while holding the lock? Or just isn't scheduled again very quickly?
- eternalban 7y agoGlancing at OP, it appears CX itself uses a RW lock. "Several years ago, when Andreia first came up with the idea that we could use a reader-writer lock to achieve wait-freedom, I though that was crazy, but cool. After joining up forces with Pascal and a lot of work, we were able to turn that into a universal construction, CX." "- wait-freedom can be achieved with locks"
- chrisseaton 7y agoI guess they must be using the lock in a careful way to avoid any contention, or to distribute people who need the lock across many versions of a data structure. That's wouldn't be the same as a 'simple mutex', would it? Which is absolutely not wait-free (even if I don't understand how the OP is using locks.)
- eternalban 7y agoYour original criticism was that a process would crash while holding a lock. I guess we need to wait for the arxiv to come back and read the paper for the details.
- chrisseaton 7y agoYes - a lock can redirect people trying to acquire it, rather than queueing them. So processes need a lock to access a resource, but there are enough resources for everyone to get their own without waiting, and enough that if a process crashes holding one it doesn't cause anyone else to wait. That's not a 'simple mutex' though.