5 ms·

Isn't there theoretically a risk that one thread could hang indefinitely while accessing (or holding a reference to) the data structure, which would prevent the

Isn't there theoretically a risk that one thread could hang indefinitely while accessing (or holding a reference to) the data structure, which would prevent the epoch from ever advancing and prevent all memory from being reclaimed? (On the other hand, I'm not sure what guarantees GC-based lock-free data structures can make in the same situation.)

aturon 11y ago
Yes. In practice this is extremely unlikely for correct lock-free structures. But you can also protect against it by releasing the epoch on every iteration of the retry loop, rather than just at the outset. (This may be a good idea for other reasons.)
asveikau 11y ago
If I read correctly, you only increment the epoch when the active bits for the current epoch are clear. As long as your stalled thread doesn't clear its active bit at an unsafe time, the epoch will stall with it and you'll be ok. Not entirely sure how a thread is supposed to set its active bit without racing with a guy who just noticed that all active bits are clear. I guess that's why it says "try to increment the epoch" and not "increment it". i.e. it can fail. EDIT: I guess this is why you go two epoch units back and not one. That, combined with the idea that everybody only goes forward in time, would probably do it.
sanjoy_das 11y ago
From the thesis the post linked to: ``` Although limbo lists are accessed using lock-free operations, and garbage collection does not interfere with other mutator processes, this reclamation scheme is not strictly lock-free. For example, a process which stalls for any reason during a shared-memory operation will not observe updates to the epoch count. In this situation the limbo lists will never be reclaimed and memory cannot be reused. Other processes can make progress only until the application reaches its memory limit. This drawback may also affect preemptively-scheduled systems, in which a process may be descheduled in the middle of a shared-memory operation with no guarantee when it will be rescheduled. ```

aturon 11y ago

Yes. In practice this is extremely unlikely for correct lock-free structures. But you can also protect against it by releasing the epoch on every iteration of the retry loop, rather than just at the outset. (This may be a good idea for other reasons.)

asveikau 11y ago

If I read correctly, you only increment the epoch when the active bits for the current epoch are clear. As long as your stalled thread doesn't clear its active bit at an unsafe time, the epoch will stall with it and you'll be ok. Not entirely sure how a thread is supposed to set its active bit without racing with a guy who just noticed that all active bits are clear. I guess that's why it says "try to increment the epoch" and not "increment it". i.e. it can fail. EDIT: I guess this is why you go two epoch units back and not one. That, combined with the idea that everybody only goes forward in time, would probably do it.

sanjoy_das 11y ago

From the thesis the post linked to: ``` Although limbo lists are accessed using lock-free operations, and garbage collection does not interfere with other mutator processes, this reclamation scheme is not strictly lock-free. For example, a process which stalls for any reason during a shared-memory operation will not observe updates to the epoch count. In this situation the limbo lists will never be reclaimed and memory cannot be reused. Other processes can make progress only until the application reaches its memory limit. This drawback may also affect preemptively-scheduled systems, in which a process may be descheduled in the middle of a shared-memory operation with no guarantee when it will be rescheduled. ```