Semaphores in DSP/BIOS
in [Embedded]
|
Prev: Hiring Jr / Sr Embedded Firmware Developer -Toronto -Apply CanadaLocal Candidates Only
Next: Base 10 exponent of a float
From: Randy Yates on 28 May 2010 18:32 On May 28, 5:08 pm, D Yuniskis <not.going.to...(a)seen.com> wrote: > Hi Steve, > > > > Steve Pope wrote: > > 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? > > > 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. PS: I "solved" this problem, albeit inelegantly (since it only works for the scenario in which the semaphore is used only once), by performing a SEM_post() immediately after the SEM_pend() in each task that was pending. --Randy
From: Randy Yates on 28 May 2010 18:37 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
From: Randy Yates on 28 May 2010 18:44 On May 28, 12:30 pm, D Yuniskis <not.going.to...(a)seen.com> wrote: > 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 Hi don, You've hit it on the head. This is exactly the kind of answer I was looking for. In fact I did implement your second (?) solution (although I came up with it before reading it here). The last suggestion is also quite good - alas there are some toolchain/ build issues associated with creating tasks dynamically, hence the scenario I proposed. Thanks for showing me I'm not completely out of it! --Randy
From: Randy Yates on 28 May 2010 18:46 On May 28, 5:23 pm, D Yuniskis <not.going.to...(a)seen.com> wrote: > Hi Tim, > > > > Tim Wescott wrote: > > On 05/28/2010 12:41 PM, Steve Pope wrote: > >> Randy Yates<ya...(a)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
From: D Yuniskis on 28 May 2010 18:57
Hi Randy, Randy Yates wrote: > On May 28, 2:05 pm, wicore <willi...(a)hotmail.com> wrote: >> 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? > > 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. |