When is to preempt safe?

When is to preempt safe?

[Parmenides]

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?

When is to preempt safe?

[Chetan Nanda]

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 at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20111007/22fc4089/attachment.html 

When is to preempt safe?

[Jonathan Neuschäfer]

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

When is to preempt safe?

[Michael Blizek]

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

When is to preempt safe?

[Parmenides]

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.

When is to preempt safe?

[Parmenides]

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.

When is to preempt safe?

[Daniel Baluta]

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.

When is to preempt safe?

[Dave Hylands]

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

When is to preempt safe?

[Michael Blizek]

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

When is to preempt safe?

[Michael Blizek]

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

When is to preempt safe?

[Dave Hylands]

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

When is to preempt safe?

[Parmenides]

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.

When is to preempt safe?

[michi1 at michaelblizek.twilightparadox.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

When is to preempt safe?

[michi1 at michaelblizek.twilightparadox.com]

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