From: Randy Yates on
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://yates(a)ieee.org % 'Mission (A World Record)',
http://www.digitalsignallabs.com % *A New World Record*, ELO
From: D Yuniskis on
Hi Randy,

Randy Yates 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?

No idea what DSP/BIOS is so no idea of their implementation
beyond your comments, here, so...

If you want to use a semaphore for this role, you can:
- have T1 post (V) M to SEM_T1 (M >= number of consumers), or
- have T1 post (V) 1 to SEM_T1 and each subsequent consumer
posts (V) 1 as soon as it acquires (P) the semaphore (i.e.,
propagate it immediately to other consumers pending)

You can also use something less complex like a *sticky*
event flag (everyone waits for it to be asserted -- which
is only done by T1). [a non-sticky flag would need to
be propagated by consumers much the same way that the second
solution above works]

Or a condition variable.

Or...

(depends what you have available to you)

A cleaner approach IF T1 IS THE PREREQUISITE FOR [T2..TN]
(i.e., maybe T1 is setting up the environments in which the
other Ti operate?) is for T1 to explicitly start/create those
tasks when it has made the world right for them (i.e., make
this dependancy more explicit and visible)

<shrug>

HTH,
--don
From: Randy Yates on
On May 28, 10:24 am, Randy Yates <ya...(a)ieee.org> wrote:
> completes, but since there was only one pend by T1

Should have been "...since there was only one POST by T1"...
From: wicore on
On 28 Maj, 16:24, 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

eh ... call SEM_post(SEM_T1) N times?

From: Tim Wescott on
On 05/28/2010 07:24 AM, Randy Yates 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?

http://en.wikipedia.org/wiki/Semaphore_%28programming%29

It appears that your T1 has the highest priority of all the other tasks,
since it must run to completion before the others start. If it may
interrupt the others should it gets ready to run while another is
running, then it is, indeed, the highest priority task.

Normally you would deal with this by making T1 the highest priority task
in the OS, and it pend on whatever event makes it ready (i.e. an ADC
read, or a timer tick). That way it'll wake up when it should, do it's
job, and go to sleep. Because it's high priority it'll automatically
trump the other tasks for processor access, and because it pends when
it's done the other tasks will automatically get their chance when it's
done. The semaphore that you have T1 pend on could be a regular binary
semaphore if they are supported, or it could be a counting semaphore
with you taking care about what happens if T1 ever fails to service it
often enough.

You may want to look at the book "The Art of Embedded Programming" by
Jack Ganssle. It looks like he only has one chapter on using real-time
operating systems, so you may have to decide if you want to read that
book or if you want to find a whole book on real-time OS usage (not that
I can find one in a hurry).

Some background: http://en.wikipedia.org/wiki/Real_time_operating_system

I started to try write you a "RTOS usage in a nutshell", but realized
that it would run over 1000 words and take me most of the day -- so I
didn't. You may want to try searching the web, or go straight to
Embedded.com and see if they have any articles on this subject. I know
that just about all that I have learned on the subject of RTOS usage has
come from on-the-job training and from Embedded.com, with just a
smattering of lectures at the Embedded Systems Conference thrown in
(Michael Barr's talk on Rate Monotonic Scheduling is a must-see after
you understand the nuts and bolts of an RTOS; he's got an article on
Embedded.com)

The real trick is that you want to identify your tasks, prioritize them,
and let the OS do it's job. For the most part, an event-driven
real-time application doesn't have a lot of tasks playing with
semaphores: they are posted in the interrupt service routines that
respond to the external events and pended on by the _one_ task that
services that event, and the "task A must pend on task B" stuff is taken
care of with priorities. Only when you are doing something advanced*
like granting access to a serial port to more than one task must you use
counting semaphores, and then you run into all sorts of potential
trouble** that you have to mitigate.

The job of prioritizing the tasks is where Rate Monotonic Scheduling
comes in -- once you strip off all the math explaining what's happening
under the hood, the actual procedure is easy and gives a pretty concrete
yea or nay to whether the underlying assumptions are being met.

I hope this helps.

* I.e. stupid
** Like priority inversion. Which is why those advanced methods are
stupid if you can find a simple way to avoid them, like a _single_ task
that talks on that serial port, and handles messages from or to any
other tasks that may need to talk.

--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com