Re: Do I need a RTOS?

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

Relevant Pages

  • Re: Overflow of FE SMTP email queues, is this normal?
    ... Badmail and the Pickup folders are also empty. ... When I pull up message properties using "Find now" on one of the queues ... and there is no data in the sender field. ...
    (microsoft.public.exchange.admin)
  • Re: Lot of QUEUE in SMTP
    ... I need to switch the anonymous and Basic Authentication OFF... ... > Having a lot of domains listed in the queues is not, per-se, a bad ... > Are all these queues empty? ...
    (microsoft.public.exchange2000.general)
  • Re: Out of petrol
    ... The petrol station just off junction 15 has already run out, ... >> and the bod on Sainsburys told me one tank was already empty and the ... Alton [only 20-ish miles from Godalming] had ... no signs of any queues at Saisnbury or BP, when I went in to - among other ...
    (uk.rec.motorcycles)
  • Re: No out-going email?
    ... yeah I found the Queues folder after I sent this message. ... How does the smart-host know to pick up the messages? ... Does exchange know ... waiting to go out or if it's empty and I've lost my messages? ...
    (microsoft.public.exchange2000.general)