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 29 May 2010 14:08 Tim Wescott <tim(a)seemywebsite.now> writes: > On 05/28/2010 03:46 PM, Randy Yates wrote: >> 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. > > 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. Oh, so you want to know what's REALLY going on? ... :) Yes, I had my initialization initially in main() also. The problem is that one of the things that needs initializing uses the SPI bus, and the processor is so damned fast (2 ns instruction cycle) some type of delay is required between SPI bus transactions. So instead of attempting to write a delay routine, whose accuracy in this day and age is going to be subject to things like compiler optimization flags, code cache hits, etc., I thought it would be much more elegant to utilize the OS's TSK_sleep() function (which is based on hardware timer ticks). So, even though my Init() task was running at the highest priority, the TSK_sleep() calls block and allow lower-priority tasks to run. Hence my need for a "gating" semaphore. -- Randy Yates % "My Shangri-la has gone away, fading like Digital Signal Labs % the Beatles on 'Hey Jude'" mailto://yates(a)ieee.org % http://www.digitalsignallabs.com % 'Shangri-La', *A New World Record*, ELO
From: Randy Yates on 29 May 2010 14:23 Tim Wescott <tim(a)seemywebsite.now> writes: > 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". Ha! I hear ya' Tim. Well, it turns out DSP/BIOS _does_ have a "binary semaphore." The problem is, it's not the type of binary semaphore I need. From the DSP/BIOS API Reference Manual for SEM_pendBinary(): SEM_pendBinary and SEM_postBinary are for use with binary semaphores. These are semaphores that can have only two states: available and unavailable. They can be used to share a single resource between tasks. They can also be used for a basic signaling mechanism, where the semaphore can be posted multiple times and a subsequent call to SEM_pendBinary clears the count and returns. Binary semaphores do not keep track of the count; they simply track whether the semaphore has been posted or not. [...] If the semaphore count is non-zero (available), SEM_pendBinary sets the count to zero (unavailable) and returns TRUE. If the semaphore count is zero (unavailable), SEM_pendBinary suspends execution of this task until SEM_post is called or the timeout expires. So what I need is not something that can handle multiple posts and one pend, but rather something that can handle multiple pends and one post! -- Randy Yates % "And all you had to say Digital Signal Labs % was that you were mailto://yates(a)ieee.org % gonna stay." http://www.digitalsignallabs.com % Getting To The Point', *Balance of Power*, ELO
From: Randy Yates on 29 May 2010 14:43 Hi Folks, I just realized what would probably be the best solution given the semaphores available in DSP/BIOS. Initialize the semaphore to a 1. Then SEM_pend() on the semaphore at the beginning of the Init() task (this assumes the Init() task runs first at startup), and SEM_post() on the semaphore at the end of the Init() task. As before, all other tasks SEM_pend() on the semaphore, then as soon as the pend is released, post to the same semaphore. This way, if any other tasks run between Init() begin and Init() end, they will block since the pend at the beginning of Init() will have taken the semaphore. And at the end of Init, the pend will allow the first pending task to unblock, it's pend allows the next pending task to unblock, etc., until task N is unblocked and when it posts the semaphore will be left at a 1, ready for the next "resource block" (if any). -- Randy Yates % "How's life on earth? Digital Signal Labs % ... What is it worth?" mailto://yates(a)ieee.org % 'Mission (A World Record)', http://www.digitalsignallabs.com % *A New World Record*, ELO
From: Nils on 29 May 2010 15:14 Randy Yates 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? Hi Randy, I've read the posts you've wrote about DspBios over the past few weeks. Seems like you're currently starting to use it.. If so: You should take a look at the software interrupts. For me they are the swiss army knife of process synchronization. DspBios on it's own already offers a lot, but there are things that you can't directly do with it. One practical example that I once had to deal with: I was gluing together different third party libraries. One was writing it's result to a mailbox, the other one was posting a semaphore. How do you write a consumer task that starts processing results as soon as one of the conditions occur? DspBios does not has as pre-canned solution. My first solution was built upon tasks. I had one helper-task waiting for the mailbox, another helper-task waiting one on the semaphore and both threads signaled a event to a third thread, my consumer. Sounds like a straight forward design, but it didn't worked as expected. My helper threads worked inside the task environment, so it happened that for example my first helper thread read the data from the mailbox and unblocked my consumer-thread, but the consumer thread never started because there was something higher priority running inside one of the third party libraries. Software interrupts solved the problem for me. They life outside the scheduler, so a software interrupt preempts any task. This lets you post multiple semaphores without getting interrupted, it lets you check mailboxes, semaphores and each other blocking DspBios primitive. You can also post semaphores and unblock tasks inside software interrupts. They are much leaner than tasks. You can raise them with conditions (counting or masking). Also they don't block hardware interrupts in any way.. As said: For non trivial scheduling problems a swiss army knife. And easy to use.. Cheers and and have fun, Nils
From: Randy Yates on 29 May 2010 17:45
<sigh> again a few mistakes: > [...] > And at the end of Init, the POST will allow the > first pending task to unblock, it's POST allows the next pending task to > unblock, etc., until task N is unblocked and when it posts the semaphore > will be left at a 1, ready for the next "resource block" (if any). -- Randy Yates % "How's life on earth? Digital Signal Labs % ... What is it worth?" mailto://yates(a)ieee.org % 'Mission (A World Record)', http://www.digitalsignallabs.com % *A New World Record*, ELO |