I write O/S software. (Often, but not continuously as my only job.) it's just part of doing embedded work and always has been. (I have a configurable O/S that I use more often than not, these days. But I don't want to go to the trouble of trying to explain all the features and how to turn them off with #define statements.)
The following points you make are the reason I'm writing:
- Single stack for all tasks
- Global variables for inter-task communication
These things tell me a lot.
One of the more important reasons for separate stacks for threads has to do with isolating and simplifying code and helping make it more maintainable. The local state of a process is retained between switches (whether or not the system is co-operative or pre-emptive.) And this is a very nice advantage. Also, a cooperative switcher is really easy to write (only a tiny bit of assembly to swap stack contexts, usually.) But you say that's not required. So I'm fine with that.
So I'll offer something extremely simple to understand, implement, and use. I've documented it in comments at the top of a source code file I used years ago and I'll let that documentation stand on its own, for now. Feel free to ask questions, though. But I don't think it is hard to follow the concepts applied here. Note that this particular implementation (the code I drew this from) was targeting a SiLabs C8051F061, which is effectively just an 8051 core processor. So any comments about specific instructions are referring to it. Just so you know.
This module provides the operating system for calling functions at timed
points in the measurement cycle. It uses a delta-queue implementation for
a low overhead interrupt routine.
CIRCULAR LIST DESIGN
This module uses a short, singly-linked list to maintain a circular list.
Every slot in the list is in one of three queues:
* the "avail" list of slots that can be used to add a new
function to be called later;
* the "sleep" list of functions that are still waiting for
their time to come; and,
* the "ready" list of functions that have timed out but
have not yet been executed.
Three queue head pointers are included to reference the first entry of
their particular queue. All linked entries in the chain, starting at the
node indicated by the queue-head and following the next node pointer list
one after another until the first entry of the adjacent queue is seen,
belong to that queue. If two adjacent queue heads reference the same
entry, then the "prior" queue is considered to be empty (there is an
exception noted later.)
Examine the following diagram.
Sleep ---------------------------------> ->  ->  ->  -,
Ready -------------> ->  ->  ->  - |
Avail --->  ->  - |
The ready queue is "prior" to the sleep queue, the sleep queue is "prior"
to the avail queue, and the avail queue is prior to the ready queue. This
concept is very much like the scissors-paper-rock game. So if both the
sleep queue and ready queue head pointers reference the same node, then it
is the ready queue that is empty, since the ready queue is "prior" to the
The queue head pointers advance in only one direction.
The avail queue head is advanced forward when an entry is inserted into
the sleep queue. The effect of advancing the avail queue head is to both
remove an entry from the avail queue and add an entry to the sleep queue.
The ready queue head is advanced when a function that is ready to execute
is executed and should be removed from the ready queue. The effect of
advancing the ready queue head is to both remove an entry from the ready
queue and add an entry to the avail queue.
The sleep queue head is advanced when a sleeping function times-out and
becomes ready to run. The effect of advancing the sleep queue head is to
both remove an entry from the sleep queue and to add an entry to the ready
That represents the only three operations permitted. The only case where
node entries may be re-ordered, though, is during insertion. The other
two cases never need to re-order entries within a queue, but only advance
queue head pointers, instead.
So it is illegal to move an entry from the sleep queue to the avail queue
by backing up the avail queue's head. Such an entry must first be moved
from the sleep queue to the ready queue and then from the ready queue to
the avail queue. All nodes must move through the queues in this fashion.
Let's now examine the possible "states" of the three queues to point out
one more 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.
SLEEP QUEUE TIMER DESIGN
The sleep queue is handled as a delta-queue, so that the timer event only
needs to decrement the time for a single entry. Each waiting function in
the sleep queue maintains a "delta" value which contains the number of
timer ticks required _after_ the preceding function in the sleep queue.
Doing recording only deltas, only the first entry on the sleep queue needs
to be examined by the timer event when counting time and deciding if the
function has timed out and needs to be moved to the ready queue.
This means that when inserting a function into the sleep queue, the time
delay initially given must be reduced by the time counts in all earlier,
waiting functions. That's the stored value for that function. Then the
function that follows this newly inserted function must also have it's
delta time adjusted for the remaining delay of the newly inserted one.
So if there were three functions, f1, f2, and f3, waiting for 1000, 1500,
and 2700 timer ticks to pass by then their delay counts would be set to
1000, 500, and 1200, respectively. The timer would examine only the first
entry's value of 1000, counting it down to zero eventually, and then move
it to the ready queue. In doing so, there would only be two more entries,
with 500 and 1200. Then the 500 would count down. When it did, a total
of 1500 counts would have occurred (1000 for the first function and now
another 500.) Etc.
To keep things slightly faster still, a special variable called 'quantum'
holds the counter value for the first sleeping function. So the value of
its remaining time is always in 'quantum' and not in the associated timer
for the node. (It's copied from there when the sleep queue advances.)
Aside from the init routine, there are three additional functions that
operate the queue system:
dqueue_insert() This function inserts functions at the
appropriate point in the sleep queue. This function is
more complex and costs more to execute, since the list
is singly-linked. Besides, it must re-start the timer
if the sleep queue emptied, earlier.
Updates availq (and quantum, sometimes.)
dqueue_execute() This function empties out the ready queue
when called. All functions ready to run are executed once
in a single event and the ready queue is always emptied.
dqueue_ISR() This function times the currently waiting
function and, if it times out, moves it from the sleep
queue to the ready queue. If more than one function
becomes ready at one time, all those ready are moved at
once so that either the sleep queue empties completely or
else a waiting function with time remaining becomes the
current one in the sleep queue.
Updates sleepq (and quantum.)
The dqueue_init() function can be used to re-initialize the system while
it is operating.
Worthy of note is that the basic responsibility for each of the pointers
is divided neatly between the three different routines. The insert
routine does NOT modify readyq or sleepq and it shouldn't. The execute
routine does NOT modify availq or sleepq and it shouldn't. The ISR event
does NOT modify availq or readyq and it shouldn't. Each routine has clear
responsibilities and can depend upon the fact that only they are allowed
to change their respective queue pointers.
As you can see, this really isn't complicated. You can set up how many "avail" slots you require. It's fixed, doesn't change, and doesn't require the use of heap space. Just a fixed, global memory array. The queue holds the address pointer to a function that can be invoked. Only the top of the sleep queue gets a "decrement", so you don't have to worry about other sleeping processes. Once the top of the sleep queue counts down to zero, all functions in the sleep queue are moved to the run queue by a some movement of just one pointer. And then they are run, in-order, until the run queue is empty and the slots are moved back into the avail queue -- again by nothing more than a simple change of a single variable in global memory. The design is bullet-proof and has been used on a number of commercial products which have millions of instrument-years of operation behind them without a single reported bug. It just works.
And it is simple.