Re: Do I need a RTOS?

On Tue, 23 Dec 2008 22:31:13 -0600, "eeboy" <jason@xxxxxxxxxxxxxxxx>
wrote:

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. It also seems
'simple' enough that I can write it without investing a great deal of time.
I think I'll use that as my starting point. I am very much in agreement
with your comment on rolling your own. It's always been much more difficult
for me to inherit code or use others code than it is to make my own (within
reason of course). I'll get the benefit of learning how it works and what
it's positive and negative attributes are.

Daring to assume you are responding to me, see replies below:

Just a few questions about implementation of such a scheme...

1) Are there any stats besides the number of items presently in the queue
that would be helpful to maintain?

A singly-linked list of function addresses and delay times is probably
fine, given that I know nothing much more about your application.

2) I would envision using malloc and memcpy to implement the queue. Are
these appropriate (efficient enough) in the embedded world? I would assume
so but...

My own penchant would be to entirely avoid malloc and its ilk.
Instead, I would make an educated guess about how many slots you will
need and allocate them as an array. More efficient, as compilers can
readily convert some of the references to elements to direct memory
references. And you get compile-time errors instead of run-time
errors you would have no idea what to do with if you got them at that
time.

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.

The three queue-head pointers are used to reference the first entry in
their particular queue. All linked entries in the chain, following
the one indicated by the queue-head, belong to that queue until the
first entry of the adjacent queue is seen. If two adjacent queue
heads reference the same entry then the "earlier" queue-head owns an
empty queue. I hope that's plain enough. But just to be certain,
examine the following diagram for clarification.

Sleep ---------------------------------> -> [] -> [] -> [] -
/ |
Ready -------------> -> [] -> [] -> [] - |
/ |
Avail ---> [] -> [] - |
|
^ |
|_________________________________________________|

The queue-head pointers can be advanced in only one direction. For
example, it is illegal to move an entry from the sleep-queue to the
avail-queue by backing up the avail-queue's "head." Instead, the
entry must be moved from the sleep-queue to the ready-queue first, by
advancing the sleep-queue "head." The avail-queue "head" is advanced
when a new entry is inserted into the sleep queue. The ready-queue
"head" is advanced when a function that is ready to execute has been,
in fact, executed. The sleep-queue "head" is advanced when an entry
has timed-out and is now ready to be executed.

A queue is empty when its "head" runs up against the following queue's
"head" (as I already mentioned.) So, the avail-queue is empty when
the avail-queue's "head" is equal to the ready-queue's "head". The
ready-queue "follows" the avail-queue. (Kind of like the scissors
paper rock game.)

If you follow this, so far, it's appropriate to examine the possible
"states" of the three queues to point out an important design issue.
Each queue may be either empty or not empty. With three queues, this
leads to eight states. The following table shows the different
combinations and compares the associated "head" pointers for the
queues with each other. I've used a (+) to indicate a non-empty queue
and a (-) to indicate an empty one.

Sleep Ready Avail Pointer conditions Description of condition
--------------------------------------------------------------------

- - - A==R, R==S, S==A Meaningless
+ - - A==R, R==S, S==A All slots are sleeping
- + - A==R, R==S, S==A All slots are ready to run
- - + A==R, R==S, S==A All slots are available
- + + A<>R, R<>S, S==A No slots are sleeping
+ - + A<>R, R==S, S<>A No slots are ready to run
+ + - A==R, R<>S, S<>A No slots available
+ + + A<>R, R<>S, S<>A No empty queues

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

Also, any recommended books on this subject matter (keeping in mind that I
have zero experience in this realm)?

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.

Jon
.

Relevant Pages

  • 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: Block-ram FIFO in Xilinx
    ... In a BlockRAM implementation, this does not make any sense, for width ... Remember, excessive depth or width has no impact, as long as the FIFO ... reliable generation of the Full and Empty flags at high clock rates. ... I would like to use the queue with different sizes of the data bus. ...
    (comp.arch.fpga)
  • Re: Do I need a RTOS?
    ... Avail slots are by nature empty correct? ... in the avail queue, as I earlier defined them to be. ... head-pointers are equal to each other, the avail-queue is full and the ... decide to execute them is another issue. ...
    (comp.arch.embedded)
  • Re: Block-ram FIFO in Xilinx
    ... Also Din and Dout have the same width. ... reliable generation of the Full and Empty flags at high clock rates. ... I have generated a block-ram based FIFO queue (2 independent clocks, ... I would like to use the queue with different sizes of the data bus. ...
    (comp.arch.fpga)
  • Re: Oops in UHCI when encountering "host controller process error"
    ... the DMA pool allocations are all messed up. ... Skel QH link element ... queue is empty ...
    (Linux-Kernel)