4 ms·
It's interesting that many people consider lock-free algorithms to be appropriate for real-time programming, but by the formal definitions, lock-free doesn't gu
by pzh 10y ago
It's interesting that many people consider lock-free algorithms to be appropriate for real-time programming, but by the formal definitions, lock-free doesn't guarantee that a particular thread won't be starved or that an operation would finish by a certain amount of time. Maybe in these cases, wait-free would be more appropriate...
- RossBencina 10y ago> Maybe in these cases, wait-free would be more appropriate... In some cases wait-free algorithms are used (e.g. real-time Java queues). There's ongoing research into whether lock-free queues are wait-free in practice.[0] For example, under some reasonable scheduling assumptions, lock-free operations have been shown to have bounded time execution.[1] That's a result for uniprocessors. I'm not aware of a corresponding result for multiprocessors, but I haven't gone looking for a couple of years. There are some leads in the first citation. [0] "Are Lock-Free Algorithms Practically Wait-Free?" http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/06/SC-2.1-K-Censor-Hillel.pdf http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/06... [1] Anderson, J. H. et al. 1997. “Real-Time Computing with LockFree Shared Objects.” ACM Transactions on Computer Systems. 15(2):134–165 https://cs.unc.edu/~anderson/papers/tocs97.pdf https://cs.unc.edu/~anderson/papers/tocs97.pdf