Do I need a RTOS?

Well, that's what happens going from concept (easy to avoid thinking about confusing details) to practical implementation (where all those nasty details impinge), I suppose. Sorry about that.

Imagine an array of structures with the structure looking like:

struct q { unsigned char next; // array idx of next entry unsigned char prev; // array idx of previous entry unsigned int delta; // ticks void (*f)( void ); // function to call, when ready };

Something like that, anyway. You can adjust the size of the next and prev pointers, as needed; also the delta value may be arranged as you see fit. I suppose, ditto for f. Anyway, let's discuss something along those lines.

So you have some array:

struct q myq[QMAX];

And queue pointers:

unsigned char sleepq; unsigned char readyq; unsigned char availq;

Initialize those as:

sleepq= readyq= availq= 0;

That's pretty specific and I hope it isn't confusing so far. QMAX is whatever you want, I suppose.

Then initialize each entry in the array so that every entry at 'i' (in other words, myq[i]) is set so that .next=n+1, .prev=n-1, .delta=0, and .f=0.

Obviously, set these, as well:

myq[0].prev= N-1; myq[QMAX-1].next= 0;

(Otherwise, you haven't got it circularly arranged.)

I hope all this is specific enough. The above case has all three pointers pointing to the same place, so that means that they are all in the avail queue, as I earlier defined them to be.

Yes, when RP == SP then "No slots are ready to run."

Yes, I think I'm following.

Pretty much. When all the pointers are equal, the avail queue is full and the other two are defined as empty. A queue is empty when its "head" runs up against the following queue's "head."

Sounds like you are working it the way I have in the past, if I'm following you.

Hmm? Everything from AP up until RP is free. What do you mean "keep something in an empty slot?" If all the pointers point to the same place, everything is empty ... by definition.

Insert adds a new entry into the sleep-queue. I don't know if you care to do this, but it is possible for you to shut down the timer when there are no sleep queue entries. If you decide to do that, the timer must be restarted when a new entry is inserted into an empty sleep-queue.

Actually the insert code is made still simpler, due to the required assumption that there is always space in the avail queue. (If you remember, I wrote, "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."

Besides, making sure there is an extra array entry is cheap and having the insert code shorter and faster is a very good thing.

The insertion function is a bit more complicated than the other two. The other queues simply advance their head-pointers, as needed. It is not necessary to change the ordering of the circularly-linked entries to perform their functions. However, this routine must not only move an entry from the avail-queue to the sleep-queue, but it may also be required to re-order entries in the sleep queue. I think I talked about this, earlier. But as you know, you need to insert the next process/thread in the right place. The other queues have it very easy, by comparison. So maybe it is a doubly-good thing that you assume there is always space in the avail queue.

The insert routine may only modify the availq variable. The other two head-pointers may not be changed by insert. This fact requires some insertions, those that must be placed at the head of the sleep-queue, to be performed without changing the head-pointer to the sleep-queue. (Vital, to make sure the structures do NOT require special guarding from interrupts.) So keep that in mind when writing this routine.

This routine executes the functions that were placed in the ready queue by the timer's interrupt handler. As each function is executed, the queue is updated to move that entry into the avail-queue. How you decide to execute them is another issue. You might simply execute all of those with .delta == 0, removing each in sequence, until a .delta != 0 entry is found. Or you might come up with another method -- perhaps firing off only one per timer interval (but then you'd need to guard the timer's decrement process so that it doesn't decrement an entry that is already zero and you'd pay a small price in terms of timing jitter.) Your call, really.

The execute routine may only modify the readyq variable. As before, the other two head-pointers may not be changed.

Hmm.

The timer event (interrupt) routine "awakens" any sleeping routines in the queue that have used up their delay time by moving them from the sleep-queue to the ready-queue. This is done by advancing the sleep-queue's head-pointer, sleepq. (As I mentioned before, you might want to consider adding a feature where an empty sleep-queue causes the timer to be turned off.)

The timer routine may only modify the sleepq variable. The other two head-pointers may not be changed here, following the paradigm earlier expressed.

However... you said, "call Execute function above" at some point. I ... well, I wouldn't necessarily do that there. What I often arrange is that there is ... in main() ... a busy loop. Something like:

for ( ; ; ) execute();

It is there that I call the execute function, over and over, pumping processes out. This is why I said you also might not want to always fire out the processes right away in the timer, itself. Or even in bursts when all their .delta's == 0. Instead, fire off one at a time with execute() and call execute() as your basic busy loop in main.

Just a possibility to consider.

I set them up as global for the three functions we discussed and also an initialize routine (which should be called when main() starts.)

Geez, that is cheap. Definitely get a copy. It is VERY readable -- in fact, you will rarely see something that nicely spoken for someone who wants to understand a nice, clear O/S design and hasn't a lot of experience with operating systems. I recommend it to anyone doing embedded work.

Jon

Ha! Ok.... my confusion here was all based on the definition of empty. When you said empty I was thinking that you were referring to no tasks in the queue and requesting that I always keep some task in the queue. However, in fact, you are simply stating that the queue length (QMAX) needs to be chosen such that it is sufficiently large to handle the worst case. In other words... there must always be a hole in the available queue.

I thought about having the main loop call the execute function but I had two concerns:

1) If I call execute, I can not utilize the sleep pointer in comparison to the ready pointer (ie: do until RP==SP) to determine if anything needs execution. I guess this isn't a concern because I could simply look for .delta ==0. 2) The more idle tasks that I stuff in my main loop the more my queue execution precision declines. Is it your intention that the only thing in my main loop be the execute function?

I do see the drawback of calling execute from within the ISR though. It doesn't allow me to immediately respond to other interrupts coming in and that could be troublesome if the function I am to execute is of substantial length.

In a somewhat related question, at what point do you draw the line for implementing a software delay (burn cycles) versus implementing some sort of call back with the method described above.

For example, I might have a situation where I must wait 20ms after writing to an external Flash memory device or perhaps a 300ms to wait after initializing an external delay. Where/how do you determine where to draw the line?

Ok... I think I have a clear picture. I'll get busy on implementing but I am sure I'll have more questions at some point.

Thanks again!

Yes. Always. Solves problems.

I'm not following the above point. In fact, I do use RP == SP for that determination. If they are equal, there is nothing to run.

For those applications where small timing jitter is important, yes. That's all there is. The idea here is "pump" execution when you have a moment to do so. Just let the timer move processes to the ready queue, but don't force their execution right away. That allows you a lot more control about _when_. If you "force" execution on the basis of the timer event, which can be fine too, then things start getting a little more complicated when you need to hold things back for some critical moment, should one arise. You can always call it from the timer event, of course. But making it a separate function has value, too.

One of the things this saves you from is having to deal with pre-emption or setting up separate stacks for co-routines/processes, while still having pretty good precision on your timing. One of the nice advantages of the delta queue is that there is only one entry to examine so it is very, very fast. This permits excellent resolution in time if you want it (by setting up a faster clock event), moving an entry from the sleep queue to the run queue. And if your for(;;) execute(); loop is no more than that, your variation in starting such functions is rather small on most micros. If done in the timer event, it's extremely predictable as moving the run queue head forward one position is ... very fast and consistent. Of course, if you have several queued up with .delta=0 and ready to be moved and run.. then you cannot run them all together at once.

In practice, it's just something to be aware of, but not overly concerned about. Usually, I know almost to a microsecond how long each function requires (or, at least, its maximum extent in time) and what its periodic timing is supposed to be. The rest is just a matter of setting it up in the first place and just letting them run.

It isn't a panacea, though.

Yes.

What would the callback do for you?

If you don't have anything else to do, then there is no issue. Just wait, I suppose. But there is no reason why other functions might not be scheduled to run at other times. For flash transactions, where there are necessary delays as well, you can keep a queue within that module that tracks pending operations and have it schedule itself, appropriately. If there is a delay to be done, it just schedules its next event after the delay. Since no other module even cares about the queue of flash transactions except perhaps to add some more to it, they can be doing their thing in between. But the flash module will be sleeping on the queue until some delay has taken place and before going on to the next transaction to be done.

Maybe I didn't understand your point, though.

And I didn't say NOT to perform the execute() from your timer event. Just suggested that you should keep in mind you don't necessarily have to do that and that it can actually be better sometimes not to do that. If you know enough about your scheduled functions to know it won't be an issue, do it. I have had things like a serial eeprom module driven hard by the timer interrupt; performing exactly one state transition and then exiting. Ran in the background without any problems. But I knew that each state transition was short, too. It's really up to you.

You can also just do some work between calls to execute(), too. If you really do need pre-emption, though, or want to benefit from the clean coding that can take place when threads have separate stacks of their own, you may want to consider an operating system of a more traditional form -- cooperative or pre-emptive. I have to admit it is very risky quarterbacking some project I know nothing much about. So all this I've discussed may not be right for you.

If I'm around (and I haven't been for quite some time), I'll respond.

No problem.

Jon

I guess it depends. If you can do all those things within individual time slots without fear of missing a beat then, yes, it may be easier to do without an RTOS. However, if you need to make a state-machine to get the timing to work then I'd opt for an RTOS. Writing to Flash, for example, is ussually slow. As is sending and receiving through a UART. If you also need to do some high-speed sampling, then RTOS'es are ussually a benefit.

Usenet readers generally have the ability to quote material from answered messages. This enables the resultant message to be understandable. You need to realize that Usenet is a 'best efforts' delivery system, and that nothing is guaranteed. There is no reason to assume that your readers have read, or ever will be able to read, previous messages.

See some of the following: (taming google) (newusers)

--
Merry Christmas, Happy Hanukah, Happy New Year
 Joyeux Noel, Bonne Annee, Frohe Weihnachten
Chuck F (cbfalconer at maineline dot net)

Which is a silly attitude. Often malloc functions are the only way to provide efficient use of limited memory. The critical thing is that the user is aware of the ways in which malloc can fail, and what the causes can be, and take appropriate steps. For example, if all malloc allocations are always of the same size, most faults are impossible. At the same time, with proper use, you will always be aware of a malloc failure.

--
Merry Christmas, Happy Hanukah, Happy New Year
 Joyeux Noel, Bonne Annee, Frohe Weihnachten
Chuck F (cbfalconer at maineline dot net)

That depends on the definition of 'high speed sampling'. I was doing

12 channels at 120Hz by sampling at every timer tick with the MSP430. That took about 20% of the CPU bandwidth with 4X oversampling. The interrupt service routine put the data into a dual-port memory where another processor fetched it, buffered it, and wrote it to hard disk. Average current consumption over several months was about 14mA. (somewhat less most of the time, about 300mA for a few seconds when writing to the hard disk every 15 minutes or so.) 12 channels at 120Hz is not really high speed sampling----but the megabytes add up when you do it continuously for several months. (Oceanographers love to collect all the data they can get----when it costs tens of thousands of dollars per day to get to the equatorial Pacific and set a mooring, then come back and pick it up months later, they tend to collect as much data as possible and let the grad students sort out the good stuff afterwards.)

For really high-speed sampling, say 200Ksamples/sec, I don't know that an RTOS would be much help. On smaller/slower processors, a task switch every 5 microseconds may not leave much time for other tasks.

If 'high speed' means about 1KSamples/second, an RTOS may be quite handy, particularly if you have multiple channels with different sampling rates. However, I've also done 1KHz sampling with an interrupt handler and a very simple state machine.

Mark Borgerson

One might. But using the idea that a state-machine is required to get timing done wouldn't be a reason to force the issue.

On instruments that have been running around the world and have been, in some incarnation or another (various products in product lines) doing that since around 1993, I've used state machines hooked to a timer interrupt to handle serial eeprom updates, synchronous communications with a DSP, and keyboard and display updates. No "RTOS" involved. Oh, and it also handled precise time delays in the main code for determining update rates and proper averaging for the consumer applications expecting measurements at certain intervals.

What an operating system (and I'm loathe to use the phrase 'real time' in front of it, because of the abuse of that term) might have done for me in aspects of the above case is to have made state machines become simpler straight-line code that is often less mystical to an outsider who didn't sit down and design the code. A state machine for running a flash driver or serial eeprom driver isn't hard to develop -- it almost falls out of the timing diagrams on data sheets -- but it's not entirely clear code to another person without good documentation, that includes the data sheet at hand as well as programmer-mentality used in developing the state machine.

But it doesn't mean an RTOS is right. Any operating system developed for a broader marketplace (whether open code and free, open code and proprietary, shareware, commercial, or any other "property" concept) will have many facets included with it that you don't need for your application. Those facets, if not able to be compiled out, are included in the application and take up space, code and data, if nothing else. Likely, they will add execution time as well as code bug risks. And if you are doing certain medical applications, often adding much more work in terms of exercising every corner of them. They add learning curves, not infrequently, too. And because of bright lines of demarcation in their design, they may unnaturally force code development along lines that one wouldn't have wanted to choose had they been able to custom-code the operating system for their needs.

Broad-based operating systems have a cost on many scales. Sometimes, they are well worth their weight. But a state machine getting the timing right is far down on my list of reasons to go looking for one.

And...? Is that all it takes to get you to use someone else's operating system designed for who knows how broad a range of interests?

Cripes. UART communications has been one of those things I would have never, ever brought up as a reason to use an O/S. If bidirectional, the traditional approach is to use two upper-level routines and two lower-level routines, one upper and lower for each of outbound and inbound characters. The upper and lower halves are decoupled from each other through what is commonly known as a buffer. Standard fair, really. And no operating system involved. Just your garden variety "device driver" concept, which works as well within an RTOS as for an application without an RTOS involved. It's just plain "a good idea" everywhere.

Hardly. One of my instruments samples at rates as fast as 650ns. The A/D converter is bit-banged, too, to operate it. That means there is no specialized hardware there -- it is entirely software raising and lowering control lines and grabbing data from it, instruction by instruction. The variability in operating those lines is 5ns (driven by the processor's own datasheet) and the software itself supports a precise resolution in timing of 75ns -- one instruction cycle. The application requires a range of sampling that goes from 650ns to as long as 50us, so we are talking of about 100:1 range in sampling time. No RTOS. Measurement rates, summarizing the gathered data, occur at fixed intervals that are set at compile-time, but usually on the order of from 1Hz to 10Hz.

The delta queue method I had been talking about here, in fact, was applied in this application, almost trivially. No RTOS. Note that here we are talking about quite a wide range of timing requirements, including millisecond timings for eeprom and flash and UART, tens of milliseconds for keyboard debounce, nanosecond timings for ADC, all the way up to roughly 1-10Hz for the end user. So quite a span in timing. No RTOS.

On the other hand, I've written my own compile-time customizable oeprating system, too, which includes options to include or exclude a real-time clock, process quantums, process priorities, sleep queues, semaphore queues, process messaging, per process exception handling, cooperative or preemptive switches, and so on. And I didn't do that just for my health. So I do understand the value of an operating system and I'm not trying to argue there is no value to them for an application. Just that I don't see where you draw your lines comparing much to where I draw mine.

--
I'm not sure, of course, but it seems you are far too easily tipped in
that direction by the least problem.  Your earlier comment, "that's
what RTOS's are for: to get tasks with wildly different timing
requirements to work smoothly" is way off the mark I see.  It is truly
quite trivial to handle widely different timings _without_ an RTOS
hauled into the picture, in fact.  The reasoning should turn on
solving somewhat different problems than what you seem to imagine.

(Perhaps we'll even get to those areas of application space where I
see them having good value.  But there is too much dross in the
conversation to go there right now.)

Jon

I always advocate using the right tools for the job - sometimes that is with an RTOS, sometimes without. I like using some of these 'automated' state machine paradigms, when that suites the job. However, while I can cut the grass with scissors, it would work, I would always choose to use a lawn mower if the lawn was more than one foot square.

I often give talks where one of the subjects is when an RTOS is useful and when not, and having multiple state machines to control fast and slow device (especially if nested) is one indicatation that an RTOS might be the best solution. In the same talk I take a piece of LCD code that I downloaded from the net which is implemented as a state machine - then first ask the class to tell me how it works (nobody has got it right yet), followed by asking how it would need changing if the LCD controller changed and worked at twice the speed (nobody has got it right yet). Finally we convert the state machine to a piece of sequential code that uses the services of the RTOS.

I have not actually done the counting, but would guess there was a lines of code ratio of about 5 to 1, and the RTOS solution is so simple you could not mistake how it worked because all the timing information is abstracted away. The RTOS solution is also very maintainable - especially if you had to maintain it when somebody else had written it. Plus the RTOS solution is many more times efficient as it does not repeatedly call a state machine when there is nothing to do or just to click through a timing state - plus the RTOS solution allows messages to be written to the LCD from multiple tasks without the application writer even having to consider it - plus the RTOS solution allows messages to be written to the LCD from interrupts without the application writer having to consider mutual exclusion - plus .......... The original state machine solution did work though, but I would guess it took ages to write and even longer to debug.

Despite being the author of a kernel I provide it for free so I have no vested interest in going around saying "though shalt always use an RTOS", but in the example you give I would suggest it would have been so much simpler - maybe not if it was the first time you had been confronted with an RTOS, but definitely after you were familiar with the concepts and methods used. Using an RTOS would also not prevent you from using high priority interrupts (that are not affected by critical sections) to perform other timing critical bits of functionality.

--
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.

John,

it sounds like you have your head in the sand.

I found a problem in the bright line drawn by the person I responded to, regarding when an operating system is appropriate. I haven't made any judgments, though, about whether or not some specific application, one where I haven't much knowledge about, should or should not use an operating system.

Here, you do exactly what I don't want to do. In fact, you start out almost declaring that I decided to use a scissors to cut a lawn, when that was hardly the case at all. But I will stop short of arguing with you, since you have no idea what processor I was using or other important aspects of the project which bounded my choices. Suffice it that I've written more than one operating system before (including a widely used, large scale time-sharing system) and at the time had that very handy compile-time configurable operating system I already mentioned -- which I assure you would have been far more appropriate to the application than FreeRTOS would have been in that circumstance.

And I chose not to use it, for reasons you cannot possibly know about here.

It really depends on a lot of other factors, though. What I didn't agree with Legato about was that "that's what RTOS's are for: to get tasks with wildly different timing requirements to work smoothly."

That isn't what they are made for -- not in my mind, anyway. And it doesn't rise very high on my list of considerations why I'd choose to use one.

However, you talk about "multiple state machines ... especially if nested." Then we are on to a different subject. On that point, ... it depends.

One of the reasons I don't like state machines is that they can easily wind up obfuscating some otherwise rather simple concept. One usually needs global variables (or static ones, anyway) to keep track of the current state of the machine so that the next invocation can start from there. That can be simply handled, for sets of trivial states, or it can get nasty-looking. So the clarity of the code depends and, thus, the appropriateness of the tool as well. But where you have a separate stack for a thread, for example, much of that "getting back to where you were, last time" goes away and the code can be very much simpler to read and maintain. I definitely appreciate the semantics of threads and processes.

Anyway, separate issues. I don't want to belabor all this. I entered this area for one original reason -- to offer the idea of delta queues to a poster, with a willingness to dig into quite specific details as needed -- and for another off-hand one where I disagreed with the statement, "that's what RTOS's are for: to get tasks with wildly different timing requirements to work smoothly." Exploring all of the various boundaries where operating systems, state machines, and a bevy of other ideas may or may not be appropriate and debating those edges from varying perspectives is a matter of a book, perhaps.. or several of them. I'm not prepared to go there, right now.

For now, my contributions will be limited to delta queues and my disagreement about the way Legato chose to write "that's what RTOS's are for." I don't think that's their purpose.

I don't find much disagreement with the broader aspects of your comments here. Broadly, I much prefer the clarity of threads and processes. But that's broadly speaking. I can provide specific cases that would argue well that a state machine is clearer, maintainable, and far less prone to programming mistakes. But I just don't want to get that deeply into the details right now -- it's way beyond the reach I am willing to go in the near term. So if you can't imagine such cases, then for now we'll just have to disagree.

I think a skilled programmer can pretty much argue that green is red and that blue is pink, if they've a mind to do that. But the fact remains that there are times and places for each of a rather wide variety of tool selections.

Just so you understand me, as I earlier pointed out I didn't write operating systems for my health -- I needed their benefits or else others did and I understood the reasons why. I'm not attacking the idea of operating systems, generally, nor FreeRTOS specifically. I just don't want anyone imagining that this is a true line of demarcation that always applies: "that's what RTOS's are for: to get tasks with wildly different timing requirements to work smoothly."

It simply isn't the line to be drawn. So far as I am concerned, anyway.

Jon

I would say: no, you don't need an RTOS. You need to think like the EE you are and design a synchronous state-machined system that implements your functionality.

I'd recommend a so-called round-robin (or, more fancily, co-operative multitasking). Implement a tight endless loop that a) deals with necessary background tasks, such as maintaining timers, and b) monitors states - e.g. flags set by timers or interrupts, or events set by other tasks. Never pend - i.e. never wait with sleeps, but by maintaining state machines and returning to the main loop - all calls *must* return within whatever latency you care to define. (There are many possible refinements to this idea, in terms of balancing high- and low-priority tasks, loop latency, responsiveness, etc, but they're now under your direct control.) Again, think in terms of a clock and synchronous state transitions.

A *huge* advantage of this approach is synchronicity - as with hardware logic design, you don't have to worry about races and mutexes, since all your active tasks can be effectively atomic.(And it becomes easy enough to measure real CPU usage.) You *do*, however, need to actively limit the runtime of each call.

HTH, in haste,

Steve

--

If the 500ms needs to be exact, consider achieving this by hardware linkage. It's not generally a good idea to do h/w IO in interrupts, but so long as it has no side-effects (a read-modify-write needs to be atomic), it can be done.

Anything done by a main loop, whether cooperative or pre-emptive, is only as exact as the lengthiest route from iteration to iteration.

Steve

--

Not at all

Then deviate... in writing giving reason for this specific case in your project

--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

In message , Jonathan Kirwan writes

Hi Jon,

Your interpretation is correct.

--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

I'm not sure I understand your last sentence. Are you saying that it is not a good idea to use interupts to service hardware such as UARTS, SPI devices or other hardware I/O devices?

Mark Borgerson