By the way, here are some questions you might want to ponder. I had originally laid out what appeared to be a very simple arrangement. However: (1) Why did I choose a circular queue for my suggestion to you? (You should be able to find __more__ than just one good reason.) (2) Assuming (1) for whatever reason you may find, why not only have an avail queue and a sleep queue? Why bother with a run queue since, obviously, you may want to run the functions listed there right away and so it will come to pass that they are immediately in the avail queue after running? (Again, you might come up with more than one good reason, here, too.) Think about things a little. The answers to the above, by the way, is not to be directly found in Comer's book that I mentioned in the earlier post. To find these, you must consider just a little bit. Anyway, best of luck. But I've found this technique to be extremely easy to use and understand and remarkably versatile. It works hand and glove with state machines, should you need them, as well. And it can be adapted to pre-emption, if you are so inclined at some point, where you "round-robbin" within the run queue, for example. Anyway, it's very little code, very little data, and big-useful. Jon
Do I need a RTOS?
Started by ●December 23, 2008
Reply by ●December 24, 20082008-12-24
Reply by ●December 24, 20082008-12-24
"eeboy" <jason@jasonorsborn.com> wrote in messge news:Tc2dncCA-4QBqszUnZ2dnUVZ_gqdnZ2d@giganews.com...>I am bringing up my first ARM project (based on LM3S1439) and am looking > for some advice. In my particular target application the processor will be > communicating with several peripherals via SPI (2) and UART, maintaining a > file system, keeping track of time and date as well as performing a lot of > GPIO manipulation. The board is also designed with a few external > communications ports so that future additions can be accommodated. > > I can see lots of wait states in the manipulation of the GPIO. For example > I might have a function that sets a pin, waits for 500ms, then clears a > pin. I could probably get away with software delays at this moment but, > given the fact that the design can scale, I don't want to introduce this > inefficiency now only to have to remove it a few months down the road. > That > 500ms could be precious later on. I have several timers at my disposal but > I can foresee 'running out' in the future. I can think of some elaborate > solutions to this problem but it makes for messy code. > > In general I was thinking I could implement a system tick which generated > an interrupt at a known interval (say 1ms). Upon each tick, I could > examine > counters associated with the periodic tasks to see if they are due for > execution. The random interrupts would be handled by the specific > interrupt > handler for that peripheral (example UART receive). That seems straight > forward to me. However, how best handle (cleanly) the toggling of a pin > after a certain delay? It's not a periodic task. > > Should I use a full blown RTOS? If not how should I structure my > application? I've had a look at FreeRTOS but it looks to be much more than > I need and slightly intimidating. > > Any suggestions? Please feel free to speak to me like a child as I am not > extremely knowledgeable of operating systems or software architecture(I am > a EE). Also, if you can point me to or provide examples that would be > extremely helpful! Help me wrap my brain around this problem. >The FreeRTOS site has a nice tutorial on RTOSes and why and when you need them. Read it, and tell me what you think. In general, if you are doing lots (more than 3) different taskson your MCU which are timing dependent and with different timing requirements than you need an RTOS.
Reply by ●December 24, 20082008-12-24
In message <x7idnZ3HceyMJszUnZ2dnUVZ_uadnZ2d@giganews.com>, eeboy <jason@jasonorsborn.com> writes>2) I would envision using malloc and memcpy to implement the queue. Are >these appropriate (efficient enough) in the embedded world?No.... MISRA-C bans malloc> I would assume >so but... > >Also, any recommended books on this subject matter (keeping in mind that I >have zero experience in this realm)?Read MISRA-C -- \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\ Chris Hills Staffs England /\/\/\/\/ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
Reply by ●December 24, 20082008-12-24
"eeboy" <jason@jasonorsborn.com> wrote in message news:x7idnZ3HceyMJszUnZ2dnUVZ_uadnZ2d@giganews.com...> That was an excellent example! It makes a lot of sense to me and I can't > see any immediate flaws with my intended application in mind.Things to be careful of: + If you are inserting into the list of timers from within an interrupt service routine then you will have to ensure the list remains very short, otherwise the operation will take too long (walking the list). + If you are inserting into the list of timers from outside of an interrupt service routine then you will have to handle the case where a timer interrupt occurs while you are performing the insertion. + If the timer expires, you perform an action, then add yourself to the list of timers again, you will have to ensure that the entire operation occurs within one time slice, otherwise the frequency at which the function is called will be too slow. This is because you are using a relative time (a time from when the function is called) rather than an absolute time. You can change the scheme to use an absolute time instead. (see the difference between the vTaskDelay() and vTaskDelayUntil() functions in FreeRTOS). -- Regards, Richard. + http://www.FreeRTOS.org Designed for microcontrollers. More than 7000 downloads per month. + http://www.SafeRTOS.com Certified by T�V as meeting the requirements for safety related systems.
Reply by ●December 24, 20082008-12-24
eeboy wrote:> I am bringing up my first ARM project (based on LM3S1439) and am looking > for some advice. In my particular target application the processor will be > communicating with several peripherals via SPI (2) and UART, maintaining a > file system, keeping track of time and date as well as performing a lot of > GPIO manipulation. The board is also designed with a few external > communications ports so that future additions can be accommodated. > > I can see lots of wait states in the manipulation of the GPIO. For example > I might have a function that sets a pin, waits for 500ms, then clears a > pin. I could probably get away with software delays at this moment but, > given the fact that the design can scale, I don't want to introduce this > inefficiency now only to have to remove it a few months down the road. That > 500ms could be precious later on. I have several timers at my disposal but > I can foresee 'running out' in the future. I can think of some elaborate > solutions to this problem but it makes for messy code. > > In general I was thinking I could implement a system tick which generated > an interrupt at a known interval (say 1ms). Upon each tick, I could examine > counters associated with the periodic tasks to see if they are due for > execution. The random interrupts would be handled by the specific interrupt > handler for that peripheral (example UART receive). That seems straight > forward to me. However, how best handle (cleanly) the toggling of a pin > after a certain delay? It's not a periodic task. > > Should I use a full blown RTOS? If not how should I structure my > application? I've had a look at FreeRTOS but it looks to be much more than > I need and slightly intimidating. > > Any suggestions? Please feel free to speak to me like a child as I am not > extremely knowledgeable of operating systems or software architecture(I am > a EE). Also, if you can point me to or provide examples that would be > extremely helpful! Help me wrap my brain around this problem. > > Thanks! > >eeboy, Some guidelines I have found true are to use a RTOS when you have a number of asynchronous interrupts, and used a timed loop (as you suggested) when everything is predictable. For example, a RTOS is good when dealing with a pumping station where you are controlling some pumps and valves based on fluid quantity flow or in a tank. You have no idea what the situation will be moment to moment, but the RTOS will let you assign priorities to various tasks and run the most important ones as soon as possible (there are no zero latency interrupts). On the other hand, let's say you were designing an engine controller. You could use a timed loop (and most of them do) to check the mass air flow sensor, the coolant temperature, the battery voltage, and engine position (% revolution), then calculate the plug and injector firing time and duration. Since I don't know your application well enough to advise, you will have to ask yourself which model is closest to your needs. Keep in mind that the RTOS involves more learning time and more over-head, but it is more flexible. Also, some RTOS's do file systems, others don't. Some will work on your processor, others won't. Dave,
Reply by ●December 24, 20082008-12-24
In article <git353$m20$1@news.albasani.net>, legato_summ23 @mailinator.com says...> > "eeboy" <jason@jasonorsborn.com> wrote in messge > news:Tc2dncCA-4QBqszUnZ2dnUVZ_gqdnZ2d@giganews.com... > >I am bringing up my first ARM project (based on LM3S1439) and am looking > > for some advice. In my particular target application the processor will be > > communicating with several peripherals via SPI (2) and UART, maintaining a > > file system, keeping track of time and date as well as performing a lot of > > GPIO manipulation. The board is also designed with a few external > > communications ports so that future additions can be accommodated. > > > > I can see lots of wait states in the manipulation of the GPIO. For example > > I might have a function that sets a pin, waits for 500ms, then clears a > > pin. I could probably get away with software delays at this moment but, > > given the fact that the design can scale, I don't want to introduce this > > inefficiency now only to have to remove it a few months down the road. > > That > > 500ms could be precious later on. I have several timers at my disposal but > > I can foresee 'running out' in the future. I can think of some elaborate > > solutions to this problem but it makes for messy code. > > > > In general I was thinking I could implement a system tick which generated > > an interrupt at a known interval (say 1ms). Upon each tick, I could > > examine > > counters associated with the periodic tasks to see if they are due for > > execution. The random interrupts would be handled by the specific > > interrupt > > handler for that peripheral (example UART receive). That seems straight > > forward to me. However, how best handle (cleanly) the toggling of a pin > > after a certain delay? It's not a periodic task. > > > > Should I use a full blown RTOS? If not how should I structure my > > application? I've had a look at FreeRTOS but it looks to be much more than > > I need and slightly intimidating. > > > > Any suggestions? Please feel free to speak to me like a child as I am not > > extremely knowledgeable of operating systems or software architecture(I am > > a EE). Also, if you can point me to or provide examples that would be > > extremely helpful! Help me wrap my brain around this problem. > > > > The FreeRTOS site has a nice tutorial on RTOSes and why and when you need > them. Read it, and tell me what you think. > > In general, if you are doing lots (more than 3) different taskson your MCU > which are timing dependent and with different timing requirements than you > need an RTOS. > >I would say that's true only if your longest interrupt handler take more time than the timing precision of your most critical task. Otherwise queues filled in the interrupt handler and emptied in a main loop may be sufficient. In a recent project, I managed to count two input frequencies with PPM resolution, store data on an SD card, keep track of a process state machine and respond to user input without an RTOS. It took a while to get a handle on the timer resources of the processor (MSP430), but I don't think an RTOS would have made things any easier. Mark Borgerson
Reply by ●December 24, 20082008-12-24
On Wed, 24 Dec 2008 11:52:22 -0000, "FreeRTOS.org" <noemail@given.com> wrote:>Things to be careful of: > >+ If you are inserting into the list of timers from within an interrupt >service routine then you will have to ensure the list remains very short, >otherwise the operation will take too long (walking the list).A good point to keep in mind, although it remains true that inserting processes that need to be run "soon" will get inserted quite quickly, usually. (There is always the perverse case where you have hundreds of functions to call all at once, I suppose, and earlier than the one being inserted.) And if the function to be inserted needs to be inserted towards the end, chances are that you can afford the time needed to insert it there without>+ If you are inserting into the list of timers from outside of an interrupt >service routine then you will have to handle the case where a timer >interrupt occurs while you are performing the insertion.Not as I helped design the structure, illustrated here. If you look at my layout, each queue owns exactly one pointer. No other function may modify it and there is only one direction the pointer may be moved. The upshot is that there is no need to guard them and no problems created when one function is moving its pointer when the timer event takes place, for example. I wrote a paragraph on this narrow point, alone. I've not had a problem with some actual coding (which I could post), even with timer events (on one application that has been running as an embedded instrument now for ... almost 20 years ... and remains a flagship product, today) at 2us intervals -- which is very fast.>+ If the timer expires, you perform an action, then add yourself to the list >of timers again, you will have to ensure that the entire operation occurs >within one time slice, otherwise the frequency at which the function is >called will be too slow. This is because you are using a relative time (a >time from when the function is called) rather than an absolute time. You >can change the scheme to use an absolute time instead. (see the difference >between the vTaskDelay() and vTaskDelayUntil() functions in FreeRTOS).Yes. That can be an issue. It turns out that with the heart beat set long enough, or with execution rates fast enough, re-inserting with a call at the beginning of the code works without timing jitter. On a processor with 75ns cycle times and 2us timer events, no jitter at all. Scoped output is precise without variation. One just needs to be aware, but not afraid. Jon
Reply by ●December 24, 20082008-12-24
"Mark Borgerson" <mborgerson@comcast.net> wrote in message news:MPG.23bc19f698182a2898968c@news.motzarella.org...> In article <git353$m20$1@news.albasani.net>, legato_summ23 > @mailinator.com says... >> >> "eeboy" <jason@jasonorsborn.com> wrote in messge >> news:Tc2dncCA-4QBqszUnZ2dnUVZ_gqdnZ2d@giganews.com... >> >I am bringing up my first ARM project (based on LM3S1439) and am looking >> > for some advice. In my particular target application the processor will >> > be >> > communicating with several peripherals via SPI (2) and UART, >> > maintaining a >> > file system, keeping track of time and date as well as performing a lot >> > of >> > GPIO manipulation. The board is also designed with a few external >> > communications ports so that future additions can be accommodated. >> > >> > I can see lots of wait states in the manipulation of the GPIO. For >> > example >> > I might have a function that sets a pin, waits for 500ms, then clears a >> > pin. I could probably get away with software delays at this moment but, >> > given the fact that the design can scale, I don't want to introduce >> > this >> > inefficiency now only to have to remove it a few months down the road. >> > That >> > 500ms could be precious later on. I have several timers at my disposal >> > but >> > I can foresee 'running out' in the future. I can think of some >> > elaborate >> > solutions to this problem but it makes for messy code. >> > >> > In general I was thinking I could implement a system tick which >> > generated >> > an interrupt at a known interval (say 1ms). Upon each tick, I could >> > examine >> > counters associated with the periodic tasks to see if they are due for >> > execution. The random interrupts would be handled by the specific >> > interrupt >> > handler for that peripheral (example UART receive). That seems straight >> > forward to me. However, how best handle (cleanly) the toggling of a pin >> > after a certain delay? It's not a periodic task. >> > >> > Should I use a full blown RTOS? If not how should I structure my >> > application? I've had a look at FreeRTOS but it looks to be much more >> > than >> > I need and slightly intimidating. >> > >> > Any suggestions? Please feel free to speak to me like a child as I am >> > not >> > extremely knowledgeable of operating systems or software architecture(I >> > am >> > a EE). Also, if you can point me to or provide examples that would be >> > extremely helpful! Help me wrap my brain around this problem. >> > >> >> The FreeRTOS site has a nice tutorial on RTOSes and why and when you need >> them. Read it, and tell me what you think. >> >> In general, if you are doing lots (more than 3) different taskson your >> MCU >> which are timing dependent and with different timing requirements than >> you >> need an RTOS. >> >> > I would say that's true only if your longest interrupt handler take more > time than the timing precision of your most critical task. Otherwise > queues filled in the interrupt handler and emptied in a main loop may > be sufficient. > > In a recent project, I managed to count two input frequencies with > PPM resolution, store data on an SD card, keep track of a process state > machine and respond to user input without an RTOS. It took a while to > get a handle on the timer resources of the processor (MSP430), but I > don't think an RTOS would have made things any easier.I'm pretty sure it would have, because that's what RTOS's are for: to get tasks with wildly different timing requirements to work smoothly. Sure you can do it yourself with some tricky programming, but a RTOS is much more reliable and results in easier to understand and maintainable code.
Reply by ●December 24, 20082008-12-24
On Wed, 24 Dec 2008 20:03:43 GMT, Jonathan Kirwan <jkirwan@easystreet.com> wrote:>A good point to keep in mind, although it remains true that inserting >processes that need to be run "soon" will get inserted quite quickly, >usually. (There is always the perverse case where you have hundreds >of functions to call all at once, I suppose, and earlier than the one >being inserted.) And if the function to be inserted needs to be >inserted towards the end, chances are that you can afford the time >needed to insert it there.(left a dangling word there, sorry) Also, the issue depends a lot on how many insertions there are, per timer tick. One of the huge advantages of a delta queue is that the timer event can be set VERY FAST, providing excellent resolution, because it only looks at exactly ONE queue entry, ever. Because of this, the price paid for a fast timer and fine-grained resolution is uniquely low. If the number of pending processes/functions isn't too large, there is no real worry. If it is, then you pay more for insertions but you still pay almost zero for each timer tick. One of the things which may be hidden by such a discussion, and which I'd like to bring back onto the top of the table in plain view, is that timer interrupts -- even well crafted ones -- eat up a chunk of time. For example, if you have a timer event once each 100us and if the timer event even when doing nothing more than keeping a counter and checking a few things uses up 10us in its execution, then you are using up 10us out of each 100us, or 10% of the CPU. The beauty of this this arrangement is that the execution time of the timer is kept deterministic (predictable) and short, regardless of the number of functions waiting. Often, that benefit is very helpful. In most of my applications using this technique, I have a modest number of waiting functions (small array to keep, low insertion time) and the arrangement allows incredible timing resolution if I want it. And when that timing resolution isn't needed, it's even better. Of course, I also have a fuller operating system I've written that I use in some applications -- one that permits compile-time configuration of (1) preemption vs cooperation, (2) the use of a real time clock resource (or not), (3) the availability of process/thread quantums, (4) the availability of a sleep queue, (5) process priorities (or not), (6) semaphore queues, (7) process/thread messages, (8) singly or doubly linked queues (memory saving option for micros with less than 100 bytes of RAM, this can be very useful despite the execution time costs), (9) limits on the process/thread queues [I use fixed arrays for generated compiler code efficiency], to name many. It relies upon the compilation process to include or remove entire regions of code, to modify the means it uses to link and unlink queue entries, to include or exclude data space, etc. It can work on very tiny micros requiring as little as three bytes per thread of data space and only a hundred words of code. But the delta queue works for many applications, too, and is very simple to write and understand well. Jon
Reply by ●December 24, 20082008-12-24
Jon, I am a bit confused now... I have the original idea of the delta queue that you presented. I understand it well. Now I am trying to translate that to the setup you present below.>I'd recommend that your array/list be arranged into three semantic >regions -- the head of one "eating" the tail of the next, in a sense. >Every slot in the list should be in one of three conceptual queues >(although they are all in the same physical array): > > (1) the "avail" list of slots that can be used to add a new > function to be called later; > (2) the "sleep" list of functions that are still waiting for > their time to come; and > (3) the "ready" list of functions that have timed out but > have not yet been executed.Avail slots are by nature empty correct? I'll bring this up a bit later...> > Sleep ---------------------------------> -> [] -> [] -> [] - > / | > Ready -------------> -> [] -> [] -> [] - | > / | > Avail ---> [] -> [] - | > | > ^ | > |_________________________________________________| >The way I read the diagram and the text... they don't jive together. This is how I understand it... Say my array is 8 slots long at some arbitrary point in RAM. Address Pointer Task TicksTilExecution ------------------------------------------------------ 0x00020 RP TaskA 0x00021 TaskB 0x00022 SP TaskC 50 0x00023 TaskD 25 0x00024 TaskE 100 0x00025 AP -- 0x00026 -- 0x00027 -- After the two tasks (A and B) execute they disappear, RP now equals SP indicating no running tasks and some time has disappeared from the next sleep task. Assume I've also added another task F. My array now looks like: Address Pointer Task TicksTilExecution ------------------------------------------------------ 0x00020 -- 0x00021 -- 0x00022 RP,SP TaskC 11 0x00023 TaskD 25 0x00024 TaskE 100 0x00025 TaskF 500 0x00026 AP -- 0x00027 -- Assuming I add no more tasks my array would look like this once everything has been executed: Address Pointer Task TicksTilExecution ------------------------------------------------------ 0x00020 -- 0x00021 -- 0x00022 -- 0x00023 -- 0x00024 -- 0x00025 -- 0x00026 AP,RP,SP -- 0x00027 -- It seems efficient... it just looks odd since items don't "push to the top" and the pointers loop around the boundaries. Do I understand right?>As you can see, four of the states are indistinguishable from each >other if the only thing you do is compare pointers. This problem can >easily be resolved by insisting that the avail-queue never be allowed >to become empty (a simpler choice than keeping either of the other two >queues non-empty.) With that assertion made, we can conclude that >when the three queue head-pointers are equal to each other, the >avail-queue is full and the other two queues are empty.I brought up the point of the avail slots being empty earlier because of this paragraph. How do I keep something in an empty slot?>I'd use at least three subroutines to manage the three queues: an >insert function which moves entries from the avail-queue to the >sleep-queue by advancing the head-pointer of the avail-queue; an >execute function which moves entries from the ready-queue to the >avail-queue by advancing the head-pointer to the ready-queue, and the >"Timer" function moves entries from the sleep-queue to the ready-queue >by advancing the head-pointer to the sleep-queue. These three >functions have exclusive access to the head-pointer of the their >respective queues and this design decision is crucial to removing the >need for interrupt masking in order to protect the data structures >from concurrency/re-entrancy problems.From this paragraph I get three functions: Insert: Walks queue between SP and AP to determine appropriate slot to add new task, inserts (and moves others down if necessary) then increments AP Execute: Increments the RP and calls the function pointed to IntHandler (on system tick): Decrements tick count on the task pointed to by the SP, if tick count==0 then increment SP and call Execute function above If I declare the SP, AP and RP static in their respective functions couldn't that backfire on me?>Hmm. I first read the term "delta queue" in a book by Douglas Comer >in 1984 called "Operating System Design - The XINU Approach." Look on >this web page, 2nd item down, for it: > >http://www.cs.purdue.edu/homes/dec/osbooks.html > >There are subsequent books on XINU, but none so clear and easy to read >as the first one.99 cents on Amazon... on its way. :) Thanks!
