Semaphores in DSP/BIOS
in [DSP]
|
From: D Yuniskis on 28 May 2010 17:23 Hi Tim, Tim Wescott wrote: > On 05/28/2010 12:41 PM, Steve Pope wrote: >> Randy Yates<yates(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. It sets up all of the other tasks in the system, allocates their stacks, heaps, etc. But, each of the other tasks has an interlock that causes them to NOT proceed until I have set up *everything*. I.e., if any task starts to run, it will preempt init() -- since init runs at the lowest priority level -- so, if I let the other tasks run, then init() will never get a chance to finish setting up all of the tasks! I do this in a variety of different ways. - leave the scheduler disabled until after everything is set up (i.e., last thing init() does is start the scheduler). This makes things easy for init() *if* it never needs any feedback from the tasks that it is starting. - let each task immediately preempt init() as soon as it is made ready. Then, after doing whatever housekeeping is required, ensure the task blocks on something that init() ultimately has control over (e.g., a semaphore or event). This lets init() know that the tasks it is creating are starting properly -- else it can take corrective action. When init() has built all of the tasks, it can then signal them all to begin. - create tasks in a dormant state and explicitly enable them from init(). Then, use one of the above scenarios. - subtle/implicit variations on the above (i.e., let each task wait for whatever it needs while init() effectively controls those occurences (e.g., if each task is waiting on different events signalled from IRQs, then init() can just keep interrupts disabled and *know* that all of the tasks will eventually block waiting for the IRQ-driven events that *can't* yet materialize Priorities should be used to decide what activities are "more important" than what *other* activites. > 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.
From: Tim Wescott on 28 May 2010 17:23 On 05/28/2010 02:23 PM, D Yuniskis wrote: > Hi Tim, > > Tim Wescott wrote: >> On 05/28/2010 12:41 PM, Steve Pope wrote: >>> Randy Yates<yates(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. It wasn't clear to me from his original post if that was the case -- I was hoping that he would clarify in that case. > 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. > > It sets up all of the other tasks in the system, allocates > their stacks, heaps, etc. But, each of the other tasks has > an interlock that causes them to NOT proceed until I have > set up *everything*. I.e., if any task starts to run, it will > preempt init() -- since init runs at the lowest priority > level -- so, if I let the other tasks run, then init() will > never get a chance to finish setting up all of the tasks! > > I do this in a variety of different ways. > - leave the scheduler disabled until after everything is > set up (i.e., last thing init() does is start the scheduler). > This makes things easy for init() *if* it never needs any > feedback from the tasks that it is starting. > - let each task immediately preempt init() as soon as it is > made ready. Then, after doing whatever housekeeping is > required, ensure the task blocks on something that init() > ultimately has control over (e.g., a semaphore or event). > This lets init() know that the tasks it is creating are > starting properly -- else it can take corrective action. > When init() has built all of the tasks, it can then signal > them all to begin. > - create tasks in a dormant state and explicitly enable them > from init(). Then, use one of the above scenarios. > - subtle/implicit variations on the above (i.e., let each > task wait for whatever it needs while init() effectively > controls those occurences (e.g., if each task is waiting > on different events signalled from IRQs, then init() can just > keep interrupts disabled and *know* that all of the tasks > will eventually block waiting for the IRQ-driven events > that *can't* yet materialize > > Priorities should be used to decide what activities are > "more important" than what *other* activites. Yes and no. Yes, they should be used to describe what activities are more important, but when you do the scheduling calculations per the RMS algorithm you may find that the algorithm's results change your impression of the 'importance' ordering from what you had originally thought. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
From: Steve Pope on 28 May 2010 17:25 D Yuniskis <not.going.to.be(a)seen.com> wrote: >Because it isn't an issue of "priorities". He wants an >explicit interlock between the execution of T1 and T2..TN. Well, both Tim and I inferred from Randy's post that T1 is, or perhaps should be, higher priority than T2, T3... you're assuming equal priorities with need for an explicit interlock. >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. I believe in the general rule of not using an explicit semaphore or message if your scheduler can handle it. What I don't know is whether DSP/BIOS has a good enough scheduler. Steve
From: D Yuniskis on 28 May 2010 17:34 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. What you need is a mechanism that forces T2..TN to stop and wait until they are *told* to proceed. E.g., create a sticky event flag called "T1_HAS_DONE_HIS_JOB". Then, have T2..TN each do: await(T1_HAS_DONE_HIS_JOB); this causes T2..TN to *block* when/if they get to this line of code (in their respective "programs") and T1 has NOT YET done his job. (I.e., T2..TN can execute all of their own code leading up to this line of code but can't continue past it). 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 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". > > That's a very interesting example. A blocked task normally > caused the next task of the same priority to be scheduled. But, you don't *know* that you have another task of the same priority *available*. None might exist. Or, the other(s) might, coincidentally, be blocking on other things at the same time, etc. If you want a genuine interlock between tasks, install one. This makes the dependency very visible in the code. Otherwise, if you rely on other aspects of the code to *effectively* give you this behavior, then when someone comes along and changes one of those aspects, things suddenly *break* ("Gee, all I did was change the algorithm so T1b would finish it's chores a little quicker. Why did T2 start running before T1a finished??") > Not a task of a lower priority. But it does get interesting > when you have tasks other than the lowest priority subject > to blocking... > >> See my post re: how to do this with semaphores, event >> flags, condition variables, etc. > > Yes, I agree it's needed in the case you describe, but I > am not at all sure the OP was describing this case. And > if so it's the "messier" case.
From: Tim Wescott on 28 May 2010 17:32
On 05/28/2010 01:40 PM, Steve Pope wrote: > 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. You certainly shouldn't hijack the scheduler from a task, or attempt to micromanage it. But there are situations where you want to start unpend 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, 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). > 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. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com |