Semaphores in DSP/BIOS
in [DSP]
|
From: Tim Wescott on 28 May 2010 17:38 On 05/28/2010 02:34 PM, D Yuniskis wrote: > Hi Steve, > > Steve Pope wrote: >> D Yuniskis <not.going.to.be(a)seen.com> wrote: >> >>>> 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. >> >> Yes, I'm saying don't do this. If you want T1 to complete >> before T2, then T1 should be higher priority -- if that >> is workable. > > But priority isn't the issue here. What the OP appears to > be claiming is there is something that needs to be done > *by* T1 before T2..TN can run. E.g., maybe T1 sets up the > interrupt system that the others will rely on. Or etc. If that's the case then Randy does, indeed, want to use semaphores. Having a bunch of stuff pend on one thing can be done with binary events of certain styles (basically ones that you can explicitly pend on without changing their state, then explicitly change their state). Or you can get this behavior from a counting semaphore with a "pend-and-post" operation, or you can have one semaphore for each of the subsidiary tasks (ick). > If T2..TN *literally* can't run until T1 is done, then > T1 should be the thiing that *starts* T2..TN -- directly > or indirectly (i.e., T1 can signal T0 that it has done it's > job and T0 can then "start" T2..TN) I.e. if the OS supports it have T1 actually call the start_task routine for the other tasks? Kinda kludgy, but it may work. (other comments snipped) -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
From: D Yuniskis on 28 May 2010 18:21 Hi Tim, Tim Wescott wrote: > On 05/28/2010 02:34 PM, D Yuniskis wrote: >> If T2..TN *literally* can't run until T1 is done, then >> T1 should be the thiing that *starts* T2..TN -- directly >> or indirectly (i.e., T1 can signal T0 that it has done it's >> job and T0 can then "start" T2..TN) > > I.e. if the OS supports it have T1 actually call the start_task routine > for the other tasks? Kinda kludgy, but it may work. It depends on what situation the OP is trying to address. When I read his post, what ran through my mind was system startup (or, SUBsystem startup). I.e., T1 sets up things that T2..TN *need* BEFORE they can run. As if T1 was the "init()" routine for this system/subsystem. In which case, *someone* has to "start_task()" so why not put that where it makes sense (if, indeed, T1 is setting up this system/subsystem)? Or, it T0 is really the init routine, then let T0 start T1 and *wait* for T1's completion -- before T0 proceeds to start T2..TN. <shrug> Again, depends on what the OP intends. My point is to make hard dependencies very obvious in the code lest they get optimized away at some future date...
From: Randy Yates on 28 May 2010 18:28 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...
From: Randy Yates on 28 May 2010 18:30 On May 28, 4:45 pm, Manny <mlou...(a)hotmail.com> wrote: > 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 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?
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 |