From: Steve Pope on
Randy Yates <yates(a)ieee.org> wrote:

>OK, this may be a stupid question but I'm going to go ahead and ask
>it. I seem to be missing something very basic in the use of semaphores.
>
>The SEM module in DSP/BIOS maintains a non-negative count of the number
>of times it has been "posted". Then when a pend occurs, the process
>either a) blocks if count = 0, or b) decrements count and resumes.
>
>I have one task T1 that must run to completion before other tasks (T2,
>..., TN) run. It *seems* this would be a good use of a semaphore;
>create a semaphore SEM_T1, then have each task T2, ..., TN pend on
>SEM_T1. Then when T1 completes, it posts to SEM_T1.
>
>However, this won't work with DSP/BIOS semaphores. What will happen is
>that the first task that pended, say, T2, will get unblocked when T1
>completes, but since there was only one pend by T1, none of the other
>T3-TN will unblock.
>
>How would you solve this problem in DSP/BIOS?

I find the following very useful in an RTOS:

Partition those tasks which you wish to initiated from interrupt
events into a finite set of priority levels (the fewer the better).

Within each level each task is preceded with common code which
implements the following sequence of operations (which must be made
uninterruptable):

(1) Is there another task of the same level already running?

(2) If so, place the current task at the end of the queue for
this level, and return from interrupt.

(3) If not, lower priority and start running the current task.

And at the end of the task:

(4) Raise priority

(5) If another task for this level is queued, execute it.
Otherwise, if the queue is empty, return from interrupt.

Whether you do this with semaphores is an implementation detail.

What you don't want to do is have tasks queueing or executing other
tasks which are from a _different_ priority level.

Applying this to your example, T1 is higher priority than T2,
T3 etc. which are all at the same (but lower) priority level.

So, when T1 gets to step (3), it lowers priority enough to
enough to allow other T1-level tasks to run - but not T2, T3
etc. tasks. Then after T1 gets to step (5), all tasks queued
at the T2, T3 level can potentially run.

(Note that if another T1 task does interrupt T1, it only
gets queued, it does not pre-empt T1.)

Fundamentally you need a queue of tasks at each priority level,
rather than individual tasks reaching across levels to
start or stop things.

Steve
From: Tim Wescott on
On 05/28/2010 12:41 PM, Steve Pope wrote:
> Randy Yates<yates(a)ieee.org> wrote:
>
>> OK, this may be a stupid question but I'm going to go ahead and ask
>> it. I seem to be missing something very basic in the use of semaphores.
>>
>> The SEM module in DSP/BIOS maintains a non-negative count of the number
>> of times it has been "posted". Then when a pend occurs, the process
>> either a) blocks if count = 0, or b) decrements count and resumes.
>>
>> I have one task T1 that must run to completion before other tasks (T2,
>> ..., TN) run. It *seems* this would be a good use of a semaphore;
>> create a semaphore SEM_T1, then have each task T2, ..., TN pend on
>> SEM_T1. Then when T1 completes, it posts to SEM_T1.
>>
>> However, this won't work with DSP/BIOS semaphores. What will happen is
>> that the first task that pended, say, T2, will get unblocked when T1
>> completes, but since there was only one pend by T1, none of the other
>> T3-TN will unblock.
>>
>> How would you solve this problem in DSP/BIOS?
>
> I find the following very useful in an RTOS:
>
> Partition those tasks which you wish to initiated from interrupt
> events into a finite set of priority levels (the fewer the better).
>
> Within each level each task is preceded with common code which
> implements the following sequence of operations (which must be made
> uninterruptable):
>
> (1) Is there another task of the same level already running?
>
> (2) If so, place the current task at the end of the queue for
> this level, and return from interrupt.
>
> (3) If not, lower priority and start running the current task.
>
> And at the end of the task:
>
> (4) Raise priority
>
> (5) If another task for this level is queued, execute it.
> Otherwise, if the queue is empty, return from interrupt.
>
> Whether you do this with semaphores is an implementation detail.
>
> What you don't want to do is have tasks queueing or executing other
> tasks which are from a _different_ priority level.
>
> Applying this to your example, T1 is higher priority than T2,
> T3 etc. which are all at the same (but lower) priority level.
>
> So, when T1 gets to step (3), it lowers priority enough to
> enough to allow other T1-level tasks to run - but not T2, T3
> etc. tasks. Then after T1 gets to step (5), all tasks queued
> at the T2, T3 level can potentially run.
>
> (Note that if another T1 task does interrupt T1, it only
> gets queued, it does not pre-empt T1.)
>
> Fundamentally you need a queue of tasks at each priority level,
> rather than individual tasks reaching across levels to
> start or stop things.

This sounds way complicated. Are you doing this within the context of
an RTOS? If so, why in heck can't you just use as many fixed priorities
as you need to get the job done?

In general, I've found that if you have to do much (or any) changing of
priorities as a task executes that's an indication that you're confused,
that you're really doing too much with that task, and that you need to
split it up or otherwise refactor your code to better match your
problem. Only if you're accessing one physical resource from multiple
tasks, and you have truly different levels of priority for your
interactions with that resource, do you need to play priority games --
and those are well documented under the "priority inheritance" rubric.

--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
From: Steve Pope on
Tim Wescott <tim(a)seemywebsite.now> wrote:

>On 05/28/2010 12:41 PM, Steve Pope wrote:

>> I find the following very useful in an RTOS:
>>
>> Partition those tasks which you wish to initiated from interrupt
>> events into a finite set of priority levels (the fewer the better).
>>
>> Within each level each task is preceded with common code which
>> implements the following sequence of operations (which must be made
>> uninterruptable):
>>
>> (1) Is there another task of the same level already running?
>>
>> (2) If so, place the current task at the end of the queue for
>> this level, and return from interrupt.
>>
>> (3) If not, lower priority and start running the current task.
>>
>> And at the end of the task:
>>
>> (4) Raise priority
>>
>> (5) If another task for this level is queued, execute it.
>> Otherwise, if the queue is empty, return from interrupt.
>>
>> Whether you do this with semaphores is an implementation detail.
>> [...] Fundamentally you need a queue of tasks at each priority level,
>> rather than individual tasks reaching across levels to
>> start or stop things.

>This sounds way complicated. Are you doing this within the context of
>an RTOS? If so, why in heck can't you just use as many fixed priorities
>as you need to get the job done?

>In general, I've found that if you have to do much (or any) changing of
>priorities as a task executes that's an indication that you're confused,
>that you're really doing too much with that task, and that you need to
>split it up or otherwise refactor your code to better match your
>problem.

Here's what you wrote earlier:

"The real trick is that you want to identify your tasks, prioritize
them, and let the OS do it's job."

I'm saying the same thing, I believe, except perhaps describing what
is being done at a lower level.

The problem as stated was that Randy was trying to use a task
at one priority level to start a lower priority task;
that for me is problematical. Your scheduler (whether part
of the OS or not) should be starting that lower priority task.

We may have a slight difference of philosophy in that you may be
stating to prioritize all tasks (N tasks, N priorities) whereas
I am more in favor of partitioning them into the smallest possible
number of priorities.

By all means use the features of your RTOS to do what I
described above. Assuming those features are there. (They
were not, back when I was working in this area, but I assume
things have vastly improved... a modern RTOS will queue up
equal-priority event-driven tasks and run them sequentially...right?

Steve
From: Manny on
On May 28, 3:24 pm, Randy Yates <ya...(a)ieee.org> wrote:
> OK, this may be a stupid question but I'm going to go ahead and ask
> it. I seem to be missing something very basic in the use of semaphores.
>
> The SEM module in DSP/BIOS maintains a non-negative count of the number
> of times it has been "posted". Then when a pend occurs, the process
> either a) blocks if count = 0, or b) decrements count and resumes.
>
> I have one task T1 that must run to completion before other tasks (T2,
> ..., TN) run.  It *seems* this would be a good use of a semaphore;
> create a semaphore SEM_T1, then have each task T2, ..., TN pend on
> SEM_T1. Then when T1 completes, it posts to SEM_T1.
>
> However, this won't work with DSP/BIOS semaphores. What will happen is
> that the first task that pended, say, T2, will get unblocked when T1
> completes, but since there was only one pend by T1, none of the other
> T3-TN will unblock.
>
> How would you solve this problem in DSP/BIOS?
> --
> Randy Yates                      % "Watching all the days go by...    
> Digital Signal Labs              %  Who are you and who am I?"
> mailto://ya...(a)ieee.org          % 'Mission (A World Record)',http://www.digitalsignallabs.com% *A New World Record*, ELO

If it's of any help, elaborate RTOS-style synchronization used to
confuse me too. At some point, I found that all this malarkey can be
reduced to a combination of 2/4-phase asynchronous handshaking
protocol. Then only thing you have left to do is hook these up with
boolean expressions.

-Momo
From: D Yuniskis on
Hi Steve,

Steve Pope wrote:
> Randy Yates <yates(a)ieee.org> wrote:
>
>> OK, this may be a stupid question but I'm going to go ahead and ask
>> it. I seem to be missing something very basic in the use of semaphores.
>>
>> The SEM module in DSP/BIOS maintains a non-negative count of the number
>> of times it has been "posted". Then when a pend occurs, the process
>> either a) blocks if count = 0, or b) decrements count and resumes.
>>
>> I have one task T1 that must run to completion before other tasks (T2,
>> ..., TN) run. It *seems* this would be a good use of a semaphore;
>> create a semaphore SEM_T1, then have each task T2, ..., TN pend on
>> SEM_T1. Then when T1 completes, it posts to SEM_T1.
>>
>> However, this won't work with DSP/BIOS semaphores. What will happen is
>> that the first task that pended, say, T2, will get unblocked when T1
>> completes, but since there was only one pend by T1, none of the other
>> T3-TN will unblock.
>>
>> How would you solve this problem in DSP/BIOS?
>
> I find the following very useful in an RTOS:
>
> Partition those tasks which you wish to initiated from interrupt
> events into a finite set of priority levels (the fewer the better).
>
> Within each level each task is preceded with common code which
> implements the following sequence of operations (which must be made
> uninterruptable):
>
> (1) Is there another task of the same level already running?
> (2) If so, place the current task at the end of the queue for
> this level, and return from interrupt.
> (3) If not, lower priority and start running the current task.
>
> And at the end of the task:
>
> (4) Raise priority
> (5) If another task for this level is queued, execute it.
> Otherwise, if the queue is empty, return from interrupt.
>
> Whether you do this with semaphores is an implementation detail.
>
> What you don't want to do is have tasks queueing or executing other
> tasks which are from a _different_ priority level.
>
> Applying this to your example, T1 is higher priority than T2,
> T3 etc. which are all at the same (but lower) priority level.

I didn't read that in the OP's initial query at all!
There was no mention of "priority". Rather, there
was a timing dependency of T2..TN on the actions
that T1 performed. T1 can have *any* priority
relative to the other tasks and there can still be
this dependency -- which can be managed with mutexes,
semaphores, event flags, etc.

I.e., if you claim T2 has lower priority than T1, then
what happens if T1 *blocks* for some reason (e.g.,
waiting on a timer). Now, tasks of lower priorities
*can* run (T2, etc.). Yet, the OP explicitly claimed:

"I have one task T1 that must run to completion before
other tasks (T2, ..., TN) run."

Merely rearranging priorities is not going to give the
OP this "guarantee".

See my post re: how to do this with semaphores, event
flags, condition variables, etc.

> So, when T1 gets to step (3), it lowers priority enough to
> enough to allow other T1-level tasks to run - but not T2, T3
> etc. tasks. Then after T1 gets to step (5), all tasks queued
> at the T2, T3 level can potentially run.
>
> (Note that if another T1 task does interrupt T1, it only
> gets queued, it does not pre-empt T1.)
>
> Fundamentally you need a queue of tasks at each priority level,
> rather than individual tasks reaching across levels to
> start or stop things.