Re: Do I need a RTOS?

On Wed, 24 Dec 2008 21:26:50 -0600, "eeboy" <jason@xxxxxxxxxxxxxxxx>
wrote:

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.

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.

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

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.

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.

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

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

Yes, I think I'm following.

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

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

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?

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

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?

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.

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

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.

Execute: Increments the RP and calls the function pointed to

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.

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

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.

If I declare the SP, AP and RP static in their respective functions
couldn't that backfire on me?

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

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

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
.

Relevant Pages

  • Re: Do I need a RTOS?
    ... place, everything is empty ... ... the queue and requesting that I always keep some task in the queue. ... It is there that I call the execute function, over and over, pumping ... timer event, of course. ...
    (comp.arch.embedded)
  • Re: Do I need a RTOS?
    ... place, everything is empty ... ... the queue and requesting that I always keep some task in the queue. ... It is there that I call the execute function, over and over, pumping ... with executeand call executeas your basic busy loop in main. ...
    (comp.arch.embedded)
  • Re: While loop style
    ... ; // empty ... > I've a while loop as below, and would like to execute the true expression ... the queue do not provide a isEmpty funtion. ...
    (microsoft.public.vc.language)
  • Re: Keyboard stops working after *lock [Was: 2.6.21-rc2-mm1]
    ... Periodic load table ... Skel QH link element ... queue is empty ...
    (Linux-Kernel)
  • Re: Single producer, "one-shot" work queue implementation, no lock on queue.
    ... usec for just calling execute() directly). ... overhead that's closer to 5nsec than 5usec. ... where there's only a single item in the queue. ... virtual void Execute() = 0; ...
    (comp.programming.threads)