_SysLevel indicates whether the system is running
user code or kernel code. When _SysLevel = -1 the current stack
is a task stack. When an interrupt occurs, or the user code
calls a kernel API, _Prolog save
the current context on the stack. Then _Prolog increments
_SysLevel and then switches to the kernel stack if _SysLevel == 0.
Subsequent interrupts, or calls to _Prolog will stack the context on
the kernel stack and increment _SysLevel. Switching to the kernel
stack involves reading the current SP and storing it in the PID
pointed to by _Running. Then the SP is loaded with the top of the
kernel stack.
_Epilog unwinds the kernel stack by
popping off the previous context, decrementing _SysLevel as it goes,
when _SysLevel goes negative it has to swap back to the Process stack.
This is when a context switch actually occurs: If _Running ==
_RunQueue, that means no context switch has been requested and _Epilog
simply restores the registers saved by _Epilog (pointed to by
_RunQueue). If _Running and _RunQueue are different, that means that a
higher priority task became ready to run (either by being queued, or
by the current task being blocked e.g. being removed from the
_RunQueue). In this case _Epilog, again, just restores the context
pointed to by the top of the _RunQueue. The third case is if
_RunQueue == 0, or is empty. That means all tasks are blocked
and the CPU is idle. In this case _Epilog goes to a special task
called the IdleTask. Currently all IdleTask does is put the CPU
to sleep waiting for an interrupt.
The designer of a software system might
choose to have a low priority task that never blocks and call that the
Idle Task. It could halt the CPU or do whatever you want.
As long as it never blocks, the internal IdleTask will never get
executed.
Queue
When processes are ready to execute,
they are placed upon the _RunQueue in inverted priority order.
Priority 0 will be inserted at the head of the queue. If there are
multiple processes with the same priority, subsequent ones will be
inserted behind all other equal processes. As processes run and block
they will be re-queued at the end of the like priority task list and
effectively be round robin scheduled.
A lower priority process can never
interrupt a higher priority process. _Epilog simply looks to the head
of the _RunQueue to pick a new process to run. However, if a lower
priority process owns a resource needed by the higher priority
process, say a semaphore being used to control access to hardware,
then the higher priority process will block until the resource have
been made available.
Once a process is running, it will run
until it is either pre-empted by a higher priority process, or it must
block, waiting for some resource.
Suspending a process
Because a "running" process
may be blocked on a semaphore, and semaphores are not
"known" to the kernel, suspending a process is not as simple
as removing it from the Run Queue. AvrXSuspend marks a process for
suspension and then attempts to remove it from the run queue. If it
succeeds, it then marks it "SUSPENDED" and returns. If it is
not successful, it simply returns. Later, when the process becomes
eligible to be inserted back into the Run Queue if it is marked for
suspension, the procedure _QueuePid will not queue it and will mark it
SUSPENDED. By definition, when _QueuePid attempts to put a task
on the run queue the task cannot be waiting for anything and the
semaphore associated with it will be cleared.
Blocked Tasks
A task is blocked when it is either
suspended or queued onto a semaphore. In other words, not
queued on the RunQueue. Because AvrX is intended for small
systems, only a forward linked list is maintained. This
conserves SRAM by only needing one pointer. Whenever inserting
or deleting something from a queue, AvrX walks the queue to find the
object being removed or the insertion point. In general all
queues (RunQueue, TimerQueue, Semaphores, MessageQueues and Messages)
can have multiple items queued up waiting. In this way a
semaphore becomes a Mutex: if it is owned by a process, all other
processes will queue up waiting for the owner to "Set" the
semaphore, thus releasing the head of the queue. Message queues
can have multiple messages waiting for a receiver, or, multiple
receivers (tasks) waiting for a message. The RunQueue will have
however many tasks are ready to execute, waiting their turn, queued.
As tasks block, or exit or are suspended, the next item in the
RunQueue is then swapped into the CPU and things continue.
Timer Queue
The timer queue is a special case.
It implements a sorted list of adjusted timeouts such that the
interrupt handler is only decrementing the first element at all times.
When it goes to zero, the code then signals the semaphore inside
the TimerQueue element. If a task is waiting on that semaphore,
then it is placed onto the RunQueue. There is a further special
case of TimerMessages, where instead of signaling the task, the
TimerControlBlock is queued onto a message queue
The TimerHandler could have been
implemented as a stand-alone task and timers could have been
implemented as messages. This actually would be pretty powerful
but was not done because of the expense of two context switches (one
for the timer handler task and one for whatever task becomes available
to run) and the expense of another task context (~40 bytes of sram).
AvrX runs three to four tasks comfortably in 512 bytes of SRAM: using
one of those tasks for the timer handler seemed too wasteful.
Fifo Support
AvrXFifo support are simple byte oriented
FIFOs. FIFOs are allocated as byte arrays with a const pointer of
the correct type cast to the array. FIFOs can be static or
automatic, or, allocated from the heap. FIFOs include semaphores
to implement synchornization between tasks or between interrupt handlers
and tasks. The AvrXSerialIO sample code illustrates how this can
be used. Look here for more details
