Hi, Preemption has two cases: user preemption and kernel preemption. I have tow questions about them. 1. According to Love, "If the kernel is returning to user-space, it knows it is in a safe quiescent state. In other words, if it is safe to continue executing the current task, it is also safe to pick a new task to execute." What's the meaning of user preemption's safety? How can we deduce safety of schedule from the current task going on? 2. Another statement from Love is that "the kernel can preempt a task running in the kernel so long as it does not hold a lock". Why is it not safe while kernel code holding lock?
On 7 Oct 2011 16:58, "Parmenides" <mobile.parmenides@gmail.com> wrote:
Hi,
Preemption has two cases: user preemption and kernel preemption. I have tow questions about them.
1. According to Love, "If the kernel is returning to user-space, it knows it is in a safe quiescent state. In other words, if it is safe to continue executing the current task, it is also safe to pick a new task to execute." What's the meaning of user preemption's safety? How can we deduce safety of schedule from the current task going on?
2. Another statement from Love is that "the kernel can preempt a task running in the kernel so long as it does not hold a lock". Why is it not safe while kernel code holding lock?
New task pick by scheduler may try to get the same lock resulting in deadlock
_______________________________________________ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
2011/10/8 Chetan Nanda <chetannanda@gmail.com>:
New task pick by scheduler may try to get the same lock resulting in deadlock
It seems that this kind of deadlock may be removed eventually. Suppose that we have a task A, which is holding a spinlock. If A is preempted by task B which try to obtain the same spinlock. Although B has to busy wait, it will end up with be preempted owing to using up its timeslice. Therefore, A has chance to be selected by shechedler and release the spinlock. Then, B will go on when it is selected by the secheduler next time.
On Sat, Oct 8, 2011 at 7:19 PM, Parmenides <mobile.parmenides@gmail.com> wrote:
2011/10/8 Chetan Nanda <chetannanda@gmail.com>:
New task pick by scheduler may try to get the same lock resulting in deadlock
It seems that this kind of deadlock may be removed eventually. Suppose that we have a task A, which is holding a spinlock. If A is preempted by task B which try to obtain the same spinlock. Although B has to busy wait, it will end up with be preempted owing to using up its timeslice. Therefore, A has chance to be selected by shechedler and release the spinlock. Then, B will go on when it is selected by the secheduler next time.
Well, I think that if task B has higher priority than task A, then A would never have the chance to release the lock. thanks, Daniel.
Hi guys, Send to list this time. On Sat, Oct 8, 2011 at 10:09 AM, Daniel Baluta <daniel.baluta@gmail.com> wrote:
On Sat, Oct 8, 2011 at 7:19 PM, Parmenides <mobile.parmenides@gmail.com> wrote:
2011/10/8 Chetan Nanda <chetannanda@gmail.com>:
New task pick by scheduler may try to get the same lock resulting in deadlock
It seems that this kind of deadlock may be removed eventually. Suppose that we have a task A, which is holding a spinlock. If A is preempted by task B which try to obtain the same spinlock. Although B has to busy wait, it will end up with be preempted owing to using up its timeslice. Therefore, A has chance to be selected by shechedler and release the spinlock. Then, B will go on when it is selected by the secheduler next time.
Well, I think that if task B has higher priority than task A, then A would never have the chance to release the lock.
Task A probably should have acquired the spinlock with interrupts and/or preemption disabled, and then it would have never lost control. If task B is also running, then it's running a separate core, and task A will still be able to continue running. -- Dave Hylands Shuswap, BC, Canada http://www.davehylands.com
2011/10/9 Daniel Baluta <daniel.baluta@gmail.com>:
On Sat, Oct 8, 2011 at 7:19 PM, Parmenides <mobile.parmenides@gmail.com> wrote:
Well, I think that if task B has higher priority than task A, then A would never have the chance to release the lock.
Hmm...! Does that mean lower priority tasks never have chances to run when a highest priority task is running? AFAIK, for the old O(1) scheduler, even with higher priority, B eventually will be put into expire array when it using up its timeslice. That cause A has chance to run again. As far as the newer CFS scheduler is concerned, when B's virtual clock is go ahead prior to A, the the scheduler might also select A to run again. So, I think A can release the spin lock eventually.
Hi! On 19:52 Sun 09 Oct , Parmenides wrote:
2011/10/9 Daniel Baluta <daniel.baluta@gmail.com>:
On Sat, Oct 8, 2011 at 7:19 PM, Parmenides <mobile.parmenides@gmail.com> wrote:
Well, I think that if task B has higher priority than task A, then A would never have the chance to release the lock.
Hmm...! Does that mean lower priority tasks never have chances to run when a highest priority task is running? AFAIK, for the old O(1) scheduler, even with higher priority, B eventually will be put into expire array when it using up its timeslice. That cause A has chance to run again. As far as the newer CFS scheduler is concerned, when B's virtual clock is go ahead prior to A, the the scheduler might also select A to run again. So, I think A can release the spin lock eventually.
This is true for "normal" priorities. For real time tasks this is different: The kernel always runs the task with the highest priority. However, a few years ago, a throttle mechanism was implemented because real time tasks occasionally locked up the system. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
Hi! On 00:19 Sun 09 Oct , Parmenides wrote:
2011/10/8 Chetan Nanda <chetannanda@gmail.com>:
New task pick by scheduler may try to get the same lock resulting in deadlock
It seems that this kind of deadlock may be removed eventually. Suppose that we have a task A, which is holding a spinlock. If A is preempted by task B which try to obtain the same spinlock. Although B has to busy wait, it will end up with be preempted owing to using up its timeslice. Therefore, A has chance to be selected by shechedler and release the spinlock. Then, B will go on when it is selected by the secheduler next time.
If you want your tasks to be preemptable while holding locks, I do not recommend busywaiting locks, but rather putting task which tries to aquire a busy lock should to sleep. The task which is holding the lock will then have a chance to run and complete the critical section. In real time systems, the priority of the task holding the lock is usually temporarily increased to the priority of the process trying to aquire the lock. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
On Fri, Oct 07, 2011 at 07:27:12PM +0800, Parmenides wrote:
2. Another statement from Love is that "the kernel can preempt a task running in the kernel so long as it does not hold a lock". Why is it not safe while kernel code holding lock?
If you preempt while a lock is being held, another task could try to acquire the same lock, causing a deadlock. HTH, Jonathan Neuschäfer
Hi! On 19:27 Fri 07 Oct , Parmenides wrote:
Hi,
Preemption has two cases: user preemption and kernel preemption. I have tow questions about them.
1. According to Love, "If the kernel is returning to user-space, it knows it is in a safe quiescent state. In other words, if it is safe to continue executing the current task, it is also safe to pick a new task to execute." What's the meaning of user preemption's safety? How can we deduce safety of schedule from the current task going on?
Basically a task running in userspace in does not hold any kernel locks (see below).
2. Another statement from Love is that "the kernel can preempt a task running in the kernel so long as it does not hold a lock". Why is it not safe while kernel code holding lock?
There are 2 different kind of locks: Those which can be preempted (mutex and semaphores) and those which cannot (spinlocks). Spinlocks do busy waiting until the lock is released. On single cpu systems, the are optimised into enable/disable preemption. Spinlocks have to be used if the data it protects is partly accessed in code paths which have preemption disables for other reasons (e.g. being interrupt handler). This is because otherwise you have a problem if you cannot preempt, but need to aquire a lock which is held by a "thread" which has been preempted. Also spinlocks *can* improve performance, because taking the lock tends be faster if "threads" do not go to sleep while holding the lock. However, it can also to the reverse: reducing responsiveness by running too long without preemption. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
2011/10/8 Michael Blizek <michi1@michaelblizek.twilightparadox.com>:
Hi!
There are 2 different kind of locks: Those which can be preempted (mutex and semaphores) and those which cannot (spinlocks). Spinlocks do busy waiting until the lock is released. On single cpu systems, the are optimised into enable/disable preemption. Spinlocks have to be used if the data it protects is partly accessed in code paths which have preemption disables for other reasons (e.g. being interrupt handler). This is because otherwise you have a problem if you cannot preempt, but need to aquire a lock which is held by a "thread" which has been preempted.
Except for interrupt handler, is there any other code path which cannot be preempted but need to obtain a lock. If not, I think a thread holding a spinlock can disable interrupt when it is in critical section to resolve this problem, rather than disable preemption.
Hi! On 00:24 Sun 09 Oct , Parmenides wrote:
2011/10/8 Michael Blizek <michi1@michaelblizek.twilightparadox.com>:
Hi!
There are 2 different kind of locks: Those which can be preempted (mutex and semaphores) and those which cannot (spinlocks). Spinlocks do busy waiting until the lock is released. On single cpu systems, the are optimised into enable/disable preemption. Spinlocks have to be used if the data it protects is partly accessed in code paths which have preemption disables for other reasons (e.g. being interrupt handler). This is because otherwise you have a problem if you cannot preempt, but need to aquire a lock which is held by a "thread" which has been preempted.
Except for interrupt handler, is there any other code path which cannot be preempted but need to obtain a lock.
AFAIK not, but I am not really sure.
If not, I think a thread holding a spinlock can disable interrupt when it is in critical section to resolve this problem, rather than disable preemption.
Disabling interrupts actually disables preemption as well. Preemption is triggered by a timer interrupt, which cannot arrive in this case. Spinlocks can be aquired both by disabling interrupts (spin_lock_irqsave) or by disabling preemption (spin_lock_bh). However, you cannot use spin_lock_bh if the same spin_lock is aquired in an interrupt handler. spin_lock_bh allows interrupt handlers to be invoked while you are still in the critical section. If the interrupt handler is processed on the same CPU as the critical section, you are stuck in a deadlock. There is a "real time" patchset which reduces spin_lock usage a lot. It replaces many interrupt handlers with code that schedules the real interrupt as a thread. They can then be interrupted and use a normal mutex for synchronisation. However, this increases latency and overhead for interrupts. It depends on the situation whether this is faster or slower. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
Hi Michi, On Sat, Oct 8, 2011 at 11:29 PM, Michael Blizek <michi1@michaelblizek.twilightparadox.com> wrote:
Hi!
On 00:24 Sun 09 Oct , Parmenides wrote:
2011/10/8 Michael Blizek <michi1@michaelblizek.twilightparadox.com>:
Hi!
There are 2 different kind of locks: Those which can be preempted (mutex and semaphores) and those which cannot (spinlocks). Spinlocks do busy waiting until the lock is released. On single cpu systems, the are optimised into enable/disable preemption. Spinlocks have to be used if the data it protects is partly accessed in code paths which have preemption disables for other reasons (e.g. being interrupt handler). This is because otherwise you have a problem if you cannot preempt, but need to aquire a lock which is held by a "thread" which has been preempted.
Except for interrupt handler, is there any other code path which cannot be preempted but need to obtain a lock.
AFAIK not, but I am not really sure.
If not, I think a thread holding a spinlock can disable interrupt when it is in critical section to resolve this problem, rather than disable preemption.
Disabling interrupts actually disables preemption as well. Preemption is triggered by a timer interrupt, which cannot arrive in this case. Spinlocks can be aquired both by disabling interrupts (spin_lock_irqsave) or by disabling preemption (spin_lock_bh). However, you cannot use spin_lock_bh if the same spin_lock is aquired in an interrupt handler. spin_lock_bh allows interrupt handlers to be invoked while you are still in the critical section. If the interrupt handler is processed on the same CPU as the critical section, you are stuck in a deadlock.
Disabling interrupts DOES NOT disable preemption on an SMP machine. It only disables preemption on the core that interrupts are disabled on.
There is a "real time" patchset which reduces spin_lock usage a lot. It replaces many interrupt handlers with code that schedules the real interrupt as a thread. They can then be interrupted and use a normal mutex for synchronisation. However, this increases latency and overhead for interrupts. It depends on the situation whether this is faster or slower.
People often associate real-time with "fast", when in fact real-time really means "deterministic". -- Dave Hylands Shuswap, BC, Canada http://www.davehylands.com
Hi! On 23:53 Sat 08 Oct , Dave Hylands wrote:
Hi Michi,
On Sat, Oct 8, 2011 at 11:29 PM, Michael Blizek <michi1@michaelblizek.twilightparadox.com> wrote: ...
Disabling interrupts actually disables preemption as well. Preemption is triggered by a timer interrupt, which cannot arrive in this case. Spinlocks can be aquired both by disabling interrupts (spin_lock_irqsave) or by disabling preemption (spin_lock_bh). However, you cannot use spin_lock_bh if the same spin_lock is aquired in an interrupt handler. spin_lock_bh allows interrupt handlers to be invoked while you are still in the critical section. If the interrupt handler is processed on the same CPU as the critical section, you are stuck in a deadlock.
Disabling interrupts DOES NOT disable preemption on an SMP machine. It only disables preemption on the core that interrupts are disabled on.
AFAIK there is no "global" preemption disable in linux. This operation would be very slow. There is stop_machine for stuff like module loading, but I guess this is not what you mean. spin_lock_bh also disables preemption only on the local cpu. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
participants (7)
-
Chetan Nanda -
Daniel Baluta -
Dave Hylands -
Jonathan Neuschäfer -
Michael Blizek -
michi1＠michaelblizek.twilightparadox.com
-
Parmenides