Thanks to everyone for your responses, but judging by the complexity of your responses, I think you misunderstood my question. The main point is this: isn't there a "type" of semaphore usually provided in other OSes which allows multiple tasks to pend on a "single" post? --Randy
Semaphores in DSP/BIOS
Started by ●May 28, 2010
Reply by ●May 28, 20102010-05-28
Reply by ●May 28, 20102010-05-28
On May 28, 5:23�pm, D Yuniskis <not.going.to...@seen.com> wrote:> Hi Tim, > > > > Tim Wescott wrote: > > On 05/28/2010 12:41 PM, Steve Pope wrote: > >> Randy Yates<ya...@ieee.org> �wrote: > > >>> 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? > > Because it isn't an issue of "priorities". �He wants an > explicit interlock between the execution of T1 and T2..TN. > > Either let T1 *start* T2..TN, *resume* them, *or* use > a counting semaphore, event flag, condition variable, mutexes, > etc. as I described in my other post. > > E.g., my Init() task runs at the absolute lowest priority > in the system. �When it is done setting things up, it becomes > the "idle" task.Again, bingo! You've hit it on the head - that's exactly my scenario too. I have an Init() task that needs to run before everything else starts up. --Randy
Reply by ●May 28, 20102010-05-28
Hi Randy, Randy Yates wrote:> On May 28, 2:05 pm, wicore <willi...@hotmail.com> wrote: >> On 28 Maj, 16:24, Randy Yates <ya...@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...@ieee.org % 'Mission (A World Record)',http://www.digitalsignallabs.com%*A New World Record*, ELO >> eh ... call SEM_post(SEM_T1) N times? > > Right, and so modify the task everytime you add a new task? Talk about > inelegant...Some semaphore implementations let you post "N" instances in one call. I.e., pick a very large N :> One advantage of this is T1 can then examine the semaphore's *value* and see if every other task has "successfully pended" on it (if T1 knows how many tasks there are). So, if T1 needs to do something *after* all of the other tasks have passed this "checkpoint", it can do so without requiring another mechanism through which the tasks signal their progress *back* to it. I prefer a sticky flag.
Reply by ●May 28, 20102010-05-28
On 05/28/2010 03:37 PM, Randy Yates wrote:> Thanks to everyone for your responses, but judging by the complexity > of your responses, I think you misunderstood my question. > > The main point is this: isn't there a "type" of semaphore usually > provided in other OSes which allows multiple tasks to pend on a > "single" post?Yes. It's called a 'binary semaphore'. Sometimes it's called an 'event' or a 'flag'. A complete RTOS should have both: many have just one or the other, along with some weasle-word justification for the practice that boils down to "we never need to use the other kind of semaphore and we're lazy, so you don't need to use it either". -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Reply by ●May 28, 20102010-05-28
On 05/28/2010 03:46 PM, Randy Yates wrote:> On May 28, 5:23 pm, D Yuniskis<not.going.to...@seen.com> wrote: >> Hi Tim, >> >> >> >> Tim Wescott wrote: >>> On 05/28/2010 12:41 PM, Steve Pope wrote: >>>> Randy Yates<ya...@ieee.org> wrote: >> >>>>> 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? >> >> Because it isn't an issue of "priorities". He wants an >> explicit interlock between the execution of T1 and T2..TN. >> >> Either let T1 *start* T2..TN, *resume* them, *or* use >> a counting semaphore, event flag, condition variable, mutexes, >> etc. as I described in my other post. >> >> E.g., my Init() task runs at the absolute lowest priority >> in the system. When it is done setting things up, it becomes >> the "idle" task. > > Again, bingo! You've hit it on the head - that's exactly my scenario > too. I have an Init() task that needs to run before everything else > starts up.Is this an RTOS that's integrated into your C environment and comes up "invisibly", or does it need to be called explicitly? If I'm using an RTOS that needs to be started from main() I'll often do all of my initialization there, then kick off the RTOS. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Reply by ●May 28, 20102010-05-28
Tim Wescott <tim@seemywebsite.now> wrote:>On 05/28/2010 01:40 PM, Steve Pope wrote:>> 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. > >You certainly shouldn't hijack the scheduler from a task, or attempt to >micromanage it.Okay>But there are situations where you want to start up >a lower-priority task from a higher-priority one. The case in point >that I can think of is if you have two relatively independent tasks that >work on short queues -- say ADC collection and serial port servicing -- >that will break if you don't do a little bit of work really quickly. If >those tasks feed larger tasks that work on a larger time scale -- say, >respectively, implementing a control rule and parsing what's coming over >the serial link -- then that indicates four tasks to me: hardware >service routines for the ADC and serial (possibly in an ISR, but an ISR >is effectively a really high priority task if you think about it), and >the motor control and the communications stack.>My suspicion is that you would want to have (say) the ADC collection and >motor control in one task with a priority change in the middle,Gack! No.>where I >would want to have separate tasks (truly, in many cases I'd probably >want the ADC collection to be in an ISR, but that's a quibble and a >matter for another thread).I like to view your motor-control example as follows: (1) ADC interrupt causes an ISR task to be performed at a certain priority (P1) (2) Conditionally this task might add a lower-priority (P2) task to the scheduler's queue for that priority (3) When the ISR task returns, the scheduler does one of two things: a) If there is already a P2 task running, it does nothing. The remaining P2 tasks will eventually be run b) If not, it checks the queue for P2, and if non-empty starts the first task in it Now, whether a given RTOS behaves like this, I am unsure. It is how I wrote schedulers a number of times. It would seem to address Randy's problem of not all of T2, T3... ever running, and it avoids doing a blunt-instrument lowering of priority in an ISR. (Which among other difficulties makes the IRS re-entrant!) (Except, now Randy has clarified he was only asking about types of semaphores, not schedulers...)>> 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.>I'm for whatever works, but yes that is what I'm propounding.>> 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?>Yes, a modern RTOS will do so. Some RTOS's are more modern than others >-- I know that MicroC/OS-II has a "one task, one priority" rule, because >in effect the task ID is the priority. But that particular RTOS is >intended to be small and simple.>If you're designing things correctly (and using a decent RTOS) then your >bunch of equal-priority tasks should have enough time to run and having >them all the same priority shouldn't starve any one of them.Yes. I tend to see (or tended to see, before Randy clarified) his issue as he was bypassing the scheduling paradigm to run one task, and so others at that priority were never started. Steve
Reply by ●May 28, 20102010-05-28
Hi Tim, Tim Wescott wrote:> On 05/28/2010 03:37 PM, Randy Yates wrote: >> Thanks to everyone for your responses, but judging by the complexity >> of your responses, I think you misunderstood my question. >> >> The main point is this: isn't there a "type" of semaphore usually >> provided in other OSes which allows multiple tasks to pend on a >> "single" post? > > Yes. It's called a 'binary semaphore'. Sometimes it's called an > 'event' or a 'flag'. A complete RTOS should have both: many have justEvents/flags are different. A semaphore (strictly speaking) is only examined by pending on it. And only modified by posting. An event/flag is something that can freely be examined without "taking it". (i.e., when you "take" a binary semaphore, the next guy -- pending -- has to wait for someone to *post* it). I vary in how I implement these. Sometimes they are "sticky". Like a bit that gets explicitly "set" (asserted) by "someone", "examined" by others (await-ed) or "reset" (released), etc. I.e., the flag has *state*... "memory". Usually, I let events be transitory in nature. Like an "edge" instead of a "level". I.e., if you are waiting for an event *when* it happens, then you "see" it (along with everyoneelse who is waiting). But, if you start waiting for it just *after* it has occurred, you *don't* see it (i.e., you wait for the *next* one to come along). These concepts can be encapsulated in other manifestations. E.g., you can use mailboxes/ports and RPC/IPC to allow events to be distributed (multiprocessor systems) transparently. If, for example, you have the ability to broadcast messages to lists of ports/queues then anything waiting *in* one of those queues (for an anticipated message!) can be "woken up" by sending N copies of a message to that queue. Since the OS presumably already knows how to handle ports being located on different processors, the OS gives you this *distributed* ability "for free".> one or the other, along with some weasle-word justification for the > practice that boils down to "we never need to use the other kind of > semaphore and we're lazy, so you don't need to use it either".<grin> Yup. Usually because they want to trim the size of their kernel or make it easier to handle certain circumstances. These things usually don't take much "extra" to implement so it's annoying when someone "arbitrarily" decides to offer one type of mechanism but not other, similar, ones. Like someone saying "we only use NAND gates; you can *make* anything you want using (an infinite number of) them!" :-/
Reply by ●May 28, 20102010-05-28
On May 28, 11:30�pm, Randy Yates <ya...@ieee.org> wrote:> On May 28, 4:45�pm, Manny <mlou...@hotmail.com> wrote: > > > > > On May 28, 3:24�pm, Randy Yates <ya...@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...@ieee.org � � � � �% 'Mission (A World Record)',http://www.digitalsignallabs.com%*ANew 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 > > Momo, sounds like an elegant solution (I like simple solutions - they > are usually the best). > Can you expound more on what 2/4-phase asynchronous handshaking is and > how you would determine the boolean expressions?For 2/4-phase handshake protocols, look up resources on asynchronous hardware. So yes this is actually logic stuff. This approach is more suited to scenarios when you'r hard-coding things like what I do all the time i.e. no RTOS kernel for maximum performance. And hooking them up with boolean expressions lets you determine priority exactly like logic. Still, I'm pretty sure you can apply same concept even on top of an RTOS. I just happen to like a unified approach in thinking about things which is rightfully grounded in the medium you happen to be working on i.e. digital logic. -Momo
Reply by ●May 29, 20102010-05-29
On Fri, 28 May 2010 16:00:45 -0700, Tim Wescott <tim@seemywebsite.now> wrote:>> The main point is this: isn't there a "type" of semaphore usually >> provided in other OSes which allows multiple tasks to pend on a >> "single" post? > >Yes. It's called a 'binary semaphore'. Sometimes it's called an >'event' or a 'flag'. A complete RTOS should have both: many have justBah, a 'complete RTOS' ?! What is this? Why is having semaphore a measure for the completeness of an RTOS ? -- 42Bastian Do not email to bastian42@yahoo.com, it's a spam-only account :-) Use <same-name>@monlynx.de instead !
Reply by ●May 29, 20102010-05-29
On 05/28/2010 11:22 PM, 42Bastian Schick wrote:> On Fri, 28 May 2010 16:00:45 -0700, Tim Wescott<tim@seemywebsite.now> > wrote: > >>> The main point is this: isn't there a "type" of semaphore usually >>> provided in other OSes which allows multiple tasks to pend on a >>> "single" post? >> >> Yes. It's called a 'binary semaphore'. Sometimes it's called an >> 'event' or a 'flag'. A complete RTOS should have both: many have just > > Bah, a 'complete RTOS' ?! What is this? Why is having semaphore a > measure for the completeness of an RTOS ? >Because I said so, before you weighed in. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
