AN585
A Real-Time Operating System for PICmicro™ Microcontrollers
Why do I Need a Real-Time Kernel?
Author:
Jerry Farmer
Myriad Development Company
Real-time design techniques allow the engineer/
designer to break-up large, complicated problems into
smaller simpler tasks or threads. These more
manageable units of code allow faster response to
important events, while prioritizing the jobs to be done
in a structured well-tested format. The kernel does the
job of keeping the time, the peace between tasks, and
keeping all the tasks’ communication flowing. More
activities can be performed in the same amount of time
by allowing other tasks to work while other tasks are
waiting for some event to occur. Smaller code is also
the result of using State-Driven techniques because
much information is condensed into the state variables
and code structure. If you need an example, look at the
PIC16C54’s “Remote Alarm” code.
INTRODUCTION
Ever dream of having a Real-Time Kernel for the
PIC16CXXX family of microcontrollers? Or ever won-
der what Multitasking or Threads are all about? Then
this article is for you. We will explore how to implement
all of the features of a large Real-Time Multitasking
Kernel in much less space, with more control, and with-
out the large overhead of existing kernels. By planning
ahead, and using the techniques outlined here, you can
build your own fast, light, powerful, flexible real-time
kernel with just the features needed to get the job done.
Included in this article are two large examples: one on
the PIC16C54, and the other on the more powerful
PIC16C64. A “Remote Alarm” is implemented on the
PIC16C54 as an example of a Non-Preemptive Kernel,
with two asynchronous serial input sources capable of
running up to 19,200 Baud along with seven sensors
needing to be debounced as inputs. One more input
line is monitored and causes an internal software
recount. For output, this example has an LED that
shows eight different internal states of the “Remote
Alarm”, blinking at different rates and different
sequences. Last but not least, is an asynchronous
serial output capable of running at 38,400 Baud, pass-
ing the inputs to the next remote alarm station. Several
short and long timers are included to round out the nine
cooperating tasks in this example. Please refer to
Figure 2 and Appendix B.
The second example is implemented on an PIC16C64
featuring an interrupt driven Semi-Preemptive Kernel.
This example has the serial input and output routines of
the first example moved into Interrupt Service Routines
(ISR) for more speed and accuracy. The interrupt capa-
bilities of the PIC16C64 will be explored, and a Real-
Time Multitasking Kernel framework will be developed.
Please refer to Figure 5 and Appendix C.
What is Multitasking Anyway?
This is the appearance of several tasks working at the
same time. Each task thinks that it owns the CPU, but
this appearance is controlled by the kernel. Only one
task can be running at a time, but there is undone work
that can be done by other tasks not blocked.
Multitasking is the orchestration of interrupts, events,
communication, shared data, and timing to get a job
done. Real-Time Programming is just a bunch of ideas,
concepts, and techniques that allow us to divide
problems into units of code that are based on units of
time, or events that drive a task from one state to
another.
1997 Microchip Technology Inc.
DS00585B-page 5-105
AN585
CONCEPTS
We will cover the basic concepts of kernels here so that
we are using the same definitions when talking about
this difficult topic. This article is a very quick survey on
Real-Time Kernel concepts. I hope to get you thinking,
reading more, and hopefully writing RT Operating
Systems for your current and future projects. Many
great books have been written about this very broad
and interesting subject. We will refer to some of these
books which have a different point of view other than
those expressed in this paper.
Shared Resources
Data structures, displays, I/O hardware, and non-reen-
trant routines are a few resource examples. If two or
more tasks use these resources, then they are called
Shared Resources and you must protect them from
being corrupted. They must have only one owner, a
way of telling others to wait, and possibly a waiting list
for future users of that resource. A rare example of a
shared resource is when there exists a critical timing
sequence of input and output operations to control
some hardware. You must disable interrupts before
starting this sequence, and re-enable them upon finish-
ing. Note that Task #1 in the PIC16C64 example is an
example of an “non-reentrant” routine that must be fin-
ished by the current owner before another task can use
it.
Critical Section
A critical section is a shared data structure, or a shared
resource, or a critical time section of code, or a non-re-
entrant section of code that can have only one owner
that is allowed to view/change/use that section at any
one time. These sections must not be interrupted
during the update process. They must be protected so
that other tasks can not get in and change the pointers/
data or modify the hardware at the same time. Remem-
ber that if two tasks can get into a critical section, at the
same time, then data WILL be corrupted. Make sure
that critical sections are small, with time for pending
interrupts to get serviced. Not understanding critical
sections is where the beginning RT programmers get
into the most trouble. Even without interrupts, you must
protect variables that are changing over time, such as
the byte sized variable
xmt_byte
used in the
PIC16C54 example. This variable changes each time
the STATE changes for the Serial Out Task.
Semaphores, and Disabling Interrupts are two of the
techniques used to coordinate between different tasks
wanting to control a critical section. Task #4 is devoted
to the proper feeding of the shared Serial Out Resource
in the PIC16C54 example. Note the use of the binary
semaphore “OState_B” to control Task #4, Task #1,
and the variable
xmt_byte.
There are several more
examples of critical sections in the PIC16C64 example
due to the use of interrupts. We disable interrupts for
very short time periods to protect these areas. Also in
the PIC16C64 example, all critical sections are finished
before checking to see if the kernel wants another task
to start running instead of the current task. We will dis-
cuss in more detail how to protect critical sections later
in this article.
Context Switch/Task Switch
When one task takes over from another, the current val-
ues of the CPU registers for this running task are saved
and the old saved registers for the new task are
restored. The new task continues where it left off. This
is all done by the Context Switch part of the Real-Time
Kernel. Each task usually has a “context switch storage
area”. Each task’s SP (Stack Pointer pointing into its
own stack) is stored there along with all the other
important saved registers. The “Remote Alarm”
example does not need to use a context switch
because all the important registers are properly freed-
up before each task is finished. The PIC16C64
example uses a similar concept, thus keeping the
number of saved registers per task way down. We use
an old concept called “where I came from”. The variable
“FROM” is used to direct the dispatcher to start up the
task where it left off. This is because you cannot manip-
ulate the stack in the PIC16CXXX family. This same
reason is why we have a “Semi-Preemptive” kernel on
the PIC16C64 as an example. By the way, the faster the
context switch is done, the better.
Scheduler
The scheduler is that part of the kernel that decides
which task will run next. We will talk about several
common types in this section. This is where a lot of
thinking should be done before starting your new
project. By understanding the different kinds of
schedulers and what features and problems each type
has, you can match your problem to a creatively styled
scheduler that meets your needs. For example, the
PIC16C54 example shows the recalling of Tasks #1-3
just before a long sequence of code is executed. More
creative ways can also be implemented, but be careful
to allow all tasks to execute in a timely fashion.
Please see Figure 1. Each task must be in “Ready
State" or the "Executing State" to be considered by the
scheduler to get temporary control of the CPU next.
FIGURE 1:
TASK / PROCESS STATE
TRANSITION DIAGRAM
Executing State
ISR State
(Waiting for Events)
(Context Switch)
Ready State
(Events)
Waiting State
DS00585B-page 5-106
1997 Microchip Technology Inc.
AN585
Non-Preemptive Kernel
The Non-Preemptive Kernel is also called a
“Cooperative Kernel” because the tasks only give-up
control when they want/need to in coordination with
other tasks, and events. The “Remote Alarm” example
uses a Non-Preemptive Kernel type, showing that
despite its reputation as being a simple kernel type, a
lot can be done with it. The Non-Preemptive Kernel
type is well suited for the non-interrupt type
PIC16C5Xs. The heart beat of the PIC16C54 example
is the internal TMR0 counter crossing over from a high
value to a low value of the counter. Use the prescaler to
adjust the time units. The very fast tasks continually
read the TMR0 directly comparing the delta of time to
see if it should fire.
Preemptive vs. Non-Preemptive
The Preemptive Kernel is harder to develop, but is eas-
ier to use, and is sometimes used incorrectly. You must
spend more upfront time with the Non-Preemptive Ker-
nel but it is better for more cramped microcontrollers.
You get much better response time between a cause/
event and the response/action for that event with a
Non-Preemptive Kernel. The Preemptive Kernel is
more predictable in the response times, and can be cal-
culated as to the maximum time to complete a given
job. Often the Preemptive Kernel is more expensive.
Reentrancy
In a Preemptive Kernel, two or more tasks may want to
use the same subroutine. The problem is that you can
not control when a task is swapped out and when
another takes its place. Thus, if a subroutine uses only
local or passed variables that are stored only in each
tasks’ stack, then it is call reentrant or a pure routine.
No global variables or hardware may be used in such a
pure routine. A way around this reentrancy requirement
is to treat the whole subroutine as a critical section.
Appendix D is an example of reentrant code segment
as might have been used in the PIC16C54 code
example.
Preemptive Kernel
In a Preemptive Kernel, a running task can be swapped
out for a higher priority task when it becomes ready.
The Preemptive Kernel relies much more on interrupts
as its driving force. The context switch is at the heart of
this type of kernel. To implement a true Preemptive Ker-
nel, you must be able to manipulate the stack. This is
why we implemented a “Semi-Preemptive” kernel on
the PIC16C64, with some of the best features of both
types of kernels. We moved some of the tasks in the
PIC16C54 example into ISRs to handle the I/Os. This
works very well as the ISRs are very short and do most
of the real work in this example. The TIMER0 interrupt
is the heart beat for the PIC16C64 example. You must
have a clock interrupt in order to make a true
Preemptive kernel.
Task Priority
Some tasks are not created equal. Some jobs must be
done on time or data will be lost. Make the tasks that
must get done the highest priority and go down the
scale from there. Some kernels make you have a
different priority for each task. This is a good idea and
requires some thought before coding to make the
design work.
Round Robin Scheduler
When the scheduler finds tasks on the ready queue
that have the same priorities, the scheduler often uses
a technique called Round Robin scheduling to make
sure each task gets its day in the sun. This means more
housekeeping to get it right. This is part of the creative
ways you can tailor the scheduler to fit your needs. In
the PIC16C54 example, all tasks will get to run shortly
after their appointed time. This means that no task will
dominate all others in this simple approach. In the
“olden” days of the first Real-Time Operating Systems
the term was used to mean the same as “time slicing”.
The Preemptive Kernels of today are a major step
forward, with their priority schemes, and intertask
communication capabilities.
Static vs. Dynamic Priorities and Priority
Inversions
For most embedded Real-Time Kernels, both static
priorities and static tasks are used. Dynamic priorities
are sometimes used to solve deadlock and other
complex situations that arise from not understanding
the problem and not understanding Real-Time
Techniques. If the need for dynamic priorities seem to
occur, you should relook at how you divided the prob-
lem, and divide less so as to include the resources in
question under one semaphore. You could divide the
problem more to have more tasks not needing two or
more resources to complete its job, and have the new
tasks talk more together.
1997 Microchip Technology Inc.
DS00585B-page 5-107
AN585
As for Dynamic tasks, you should define the problem so
as to know, ahead of coding, the continuous use of all
tasks. You will need more upfront time in the planning
stage to get all tasks talking, but it is well worth it to
keep Dynamic Priorities and Dynamic Tasking out of
the kernel design.
Priority Inversions is a trick used to get past a poorly
designed system by inverting the priorities to allow
lower tasks to run that were previously blocked. This is
a cheap trick, and is best kept out of a Real-Time Ker-
nel. Use the other techniques outlined in this section to
solve this kind of problem.
Synchronization
Semaphores can be used to synchronize tasks so that
messages can be passed between them. Also tasks
can be started up by semaphores, stopped by
semaphores, or started together. They are the
foundation blocks for Real-Time Programming. Once
you have built a binary semaphore for your kernel, you
can build very complex semaphores to synchronize
anything. In the PIC16C54 example, data from several
sources are passed out the Serial Port Resource.
Task #4 synchronizes the other tasks trying to send
data out and synchronizes with task #1 to get it done.
When task #1 is running, then task #4 can not run until
task #1 is ready for more data to send out.
Semaphores
There are basically two types: binary and counting
semaphores. The binary semaphore allows only one
owner, and all other tasks wanting access are made to
wait. The counting semaphore keeps a list of users that
need access. Semaphores can be used in many ways.
We will illustrate most of them in the following para-
graphs. Note that you can implement counting sema-
phores using binary semaphores.
Intertask Communication
We have touched on this topic already, but for large ker-
nels, one can include more complex communication
methods to pass data/messages between tasks. Much
of the handshaking is done for you inside the kernel.
This takes a lot more space and execution speed to
implement them in a kernel.
Mutual Exclusion
We have touched on the subject of Mutual Exclusion
earlier (a method to exclude other tasks from gaining
access to critical sections). Mutual Exclusion is the
process of excluding others from access to the shared
resources. To make a semaphore is a very complicated
process. The semaphore’s construction must be
atomic. That means that once the process has started,
it can not be interrupted until it has saved the name of
the new owner. From there on, it knows that no one else
can break-in and change owners. We have
implemented a binary semaphore using bits and kernel
functions to mutually exclude access in the PIC16C54
example.
In the PIC16C64 example, we also disable interrupts to
get the same effect. There are at least two good ways
of implementing a binary semaphore. The first and
oldest way was discovered by a Dutch mathematician
named Dekker. We will refer you to a book that talks
more about this algorithm. The second method of
implementing a binary semaphore was also discovered
by another Dutchman named Dijkstra. This method
uses the “testandset” type instruction and is much more
important to us. We used the
dec & jump if not
zero
instruction (see PIC16C64 example).
Event Flags
We implemented Event Flags as simple bits having two
states (on and off). More info can be stored per Event
Flag such as time it was recorded, by who, and who the
event belongs to, and whether data was lost.
Message Mailboxes
This is a nice feature to have if you have the ram space.
Mailboxes allow the designer to pass messages
between tasks, and allows messages to be looked at
when the task is ready, and to reply telling the sender
that the message was received. One message can be
sent to many tasks at the same time.
Message Queues
This again is a very nice feature if you have the execu-
tion time, and the ram to implement them. This feature
is related to Mailboxes, in that you can store several
messages even after reading, to be processed later. If
you want to only operate on the highest prioritized
messages before handling the rest, this is allowed. You
can be very fancy with the Mailboxes and Queues. If
you have them, use them.
Deadlock
Deadlock is a condition where two or more tasks own
resources that other tasks need to complete there
assignment but will not release their own resources
until the other tasks release theirs. Talk about
cooperation. Please read section, "Static vs. Dynamic
Priorities and Priority Inversions" for a discussion about
such problems and ways to solve them. The root of
such problems is not understanding the original
problem.
DS00585B-page 5-108
1997 Microchip Technology Inc.
AN585
Interrupts
Interrupts are one of the best inventions to come along
for solving Real-Time problems. You can get very quick
response to the need, and then go back to what you
were doing. The only problem is that they can and do
happen at the worst times. That means that you must
learn how to turn them on and off to protect your critical
sections. Note that before an interrupt can be handled,
you must save all important registers so that you can
restore them so that the kernel can restart the task
where it left off. This is much like the context switch
issue, but for interrupts, you must always save and
restore. In the PIC16C64 example, the Status, W, and
FSR registers are saved in RAM because of the
interrupt. The PC register is saved onto the stack by
hardware.
ISR Processing Time
ISR (Interrupt Service Routine) Processing Time is
defined as the time an ISR keeps control of the CPU.
This amount of time should be short, and if a lot of
processing needs to be done in a ISR, then break up
the ISR. The new ISR should now just store the new
data and return. Next, create a new task and move the
extra code from the old ISR into the new task.
Remember that the longer you are in one interrupt, the
longer you can not answer another pressing interrupt.
Nesting interrupts are where the interrupt with a higher
priority can interrupt a lower priority interrupt. Care
must be used, as different interrupts may have critical
sections too, and disabling interrupts must be used
here too to protect critical sections. Nesting of
interrupts may not exist on all microcontrollers, such as
the PIC16CXXX family.
Interrupt Latency, Response and Recovery
Interrupt Latency is defined as the largest time period
that interrupts are disabled, plus the time it takes for the
ISR to start to execute.
The Interrupt Response Time is defined for a Non-
Preemptive system as Interrupt Latency plus the
“context saving time.” For a Preemptive system, add
the execution time for the kernel to record the interrupt.
Interrupt Recovery Time for a Non-Preemptive system
is defined as the time to restore the saved context and
for the restarting of the task that was interrupted.
Interrupt Recovery Time for a Preemptive system is the
same as for the Non-Preemptive system plus the time
the kernel takes in the scheduler deciding which task to
run next. These measurements are how most kernels
are compared with each other. The PIC16C64 example
does very well in these measurements. That is
because of the PIC16CXXX processor and that they
are mostly a Non-Preemptive system. You must keep
the time you disable interrupts to a minimum in any ker-
nel you write or any task that you write. You should
break-up long sequences of instructions to allow for
interrupts that are already waiting to execute.
Non-Maskable Interrupts
On some microprocessors, you can enable/disable
selected interrupts, such as on the PICmicro family.
This is a great tool to control the flow of data into the
system and out. Some systems have what is called
Non-Maskable Interrupts. Here you can not turn them
off by software masking. These NMIs as they are call
for short, are used as clock Ticks, because you do not
want problems with complex critical sections on a
interrupt that you can not turn off. The PIC16CXXX
family does not have any NMIs. NMIs are not as useful
as maskable interrupts.
Clock Tick
The Clock Tick, is the heart beat of the system. This is
how the kernel keeps time (relative & absolute). This is
how the kernel is restarted to see if there is a delay that
has finished, so that the task can be moved into the
ready state. In the PIC16C54 example, the Timer0
clock is used. In the PIC16C64 example, Timer0 is
used. You must have a clock interrupt in order to make
a true Preemptive kernel. This is the other reason why
we implemented a Non-Preemptive Kernel on the
PIC16C54 - no clock interrupt.
1997 Microchip Technology Inc.
DS00585B-page 5-109
京公网安备 11010802033920号
EEWORLD
