3 ms·
Based on [1], thread running inside a critical section cannot be preempted by other threads on the processor. That means deadlock won't happen since nested cri
by ww520 10y ago
Based on [1], thread running inside a critical section cannot be preempted by other threads on the processor. That means deadlock won't happen since nested critical sections are still run by the same thread until it exits the outermost critical section.
Thread halting is a not problem as long as it resumes to complete the critical section. Interrupt can happen. The interrupt state is saved to be handled later, the thread resumes to finish the critical section, and then the saved interrupt is delivered to the interrupt handler. The scheduler is interrupt driven anyway.
Thread killed while inside a critical section can be a real problem, as the critical section is not released, preventing other threads from running on the processor. I'm not sure how Linux handles it, whether it would clean up the critical section when the thread is killed or the killing waits until the critical section has finished.
[1] https://en.wikipedia.org/wiki/Critical_section#Kernel-level_critical_sections https://en.wikipedia.org/wiki/Critical_section#Kernel-level_...
- gpderetta 10y agoA thread can still deadlock with itself with non-recursive mutexes or spinlocks. Also assuming a single CPU system is no longer relevant today. "Thread halting is a not problem as long as it resumes" the whole point of a non blocking algorithm is that it gives guarantees if a thread doesn't resume for whatever reason.
- HenryR 10y agoThe whole point of a non-blocking algorithm is system-wide forward progress. Yes, this is much harder to do if a thread can suspend for an unbounded amount of time, but that's kind of the point of the article: being in the kernel allows you to pull the kind of trick that makes that behaviour a non-issue. (edit: s/per-thread/system-wide, since we're talking about lock-freedom).
- gpderetta 10y agoTechnically non-blocking only guarantees system wide progress. Only wait-free algorithms guarantee per thread progress. Anyway, even controlling preemption and disabling interrupts very much does not make a spinlocked critical section a lock free algorithm. That's not just a theoretical issue. We are dealing right now with a couple of machines where periodically the kflush kernel thread livelocks hard preventing the rest of the system from ever writing a page to disk requiring a hard powercycle.