An Embedded Software Primer

David E. Simon
Chapter 6: Introduction to Real-Time
Operating Systems

1. Tasks and Task States

2. Tasks and Data
3. Semaphores and Shared Data

2
3/12/2006
Tasks and Task States
 A task is the basic building block of software in an RTOS
and is usually a subroutine.
 The RTOS starts a task by specifying its corresponding
subroutine, priority, stack etc.
 The task can have 3 states :-
1. Running – The task code is currently being executed by the
microprocessor. Except in multi-processor systems, only one
task is in running state.
2. Ready – The task is waiting to execute but another task is
currently running.
3. Blocked – The task cannot run even if the microprocessor is
free. It might be waiting for an external event or a response. e.g.
a push-button task stays blocked until the button is pushed.
 Most RTOSs have other states like suspended, waiting,
dormant etc. but these are just sub-divisions of one of the
three states above.

3
3/12/2006
Tasks and Task States (contd.)
The Scheduler
 A scheduler in the RTOS decides which task to run.
 Unlike Unix or Windows the scheduler is simple – the task in the
ready state that has the highest priority will run.
 It is the user’s responsibility to ensure that the highest priority task
doesn’t hog the processor.
 Fig. 6.1 from Simon shows the task states. Also the following
definitions will be assumed:
 Block – move into blocked state
 Run – move into the running state
 Switch – change which task runs
 A few results from the fig. are as follows:
 A task can be blocked only by its own decision and not by the scheduler
or another task. Hence a task can only enter the blocked state from the
running state.
 A task will remain blocked until the event it is waiting for occurs.
 Only a scheduler can move a task to the running state from the ready
state.

4
3/12/2006
Tasks and Task States (contd.)

5
3/12/2006
Tasks and Task States (contd.)
 Some common questions about the scheduler and task states
are :-
How does a scheduler know that a task is blocked or
unblocked?
The task calls RTOS functions to indicate which functions it is
waiting for and if they have happened.
What if all tasks are blocked?
It is the user’s responsibility to ensure this doesn’t happen.
Unless an interrupt or event unblocks a task, tasks will stay in
this state (deadlock).
What if two tasks with same priority are ready?
Depends on the RTOS. Some require distinct priorities, some
time-slice between the 2 tasks.
If a higher priority task unblocks, is the current running task
moved to the ready state right away?
This will happen only if the RTOS is preemptive.
6
3/12/2006
Tasks and Task States (contd.)
Example
The following pseudo-code e.g. (fig. 6.2 Simon) illustrates tasks in RTOS.
// “Button Task”
void vButtonTask () // High priority
{
while (TRUE)
{
!! Block until user pushes a button
!! Quick: respond to the user
}
}

// “Levels Task”
void vLevelsTask () // Low priority
{
while (TRUE)
{
!! Read float levels in tank
!! Calculate average float level

7
3/12/2006
Tasks and Task States (contd.)
!! Do a lot of calculations
!! Select next tank
}
}
 The code is from the underground tank monitoring system.
 Task vLevelsTask uses as much computing time possible to
determine the gasoline level and is hence kept at a lower
priority.
 vButtonTask will pre-empt the lower priority task whenever it
is ready, finish servicing the pushed button, and then block.
 Tasks can be independent of one another in an RTOS.
 To insert the tasks in the RTOS, it must be initialized
(InitRTOS()) tasks must be started and their priorities
specified (StartTask()) and the OS needs to be started
(StartRTOS()).
 Once the OS is started, function never returns.

8
3/12/2006
Tasks and Data
 Each of the tasks have a set of register, a program counter
and a stack.
 Tasks can also communicate using shared (global) variables.
 Fig. 6.6 illustrates this. It is basically the previous underground
tank example code with some additional functions.
 The two tasks share the tankData array

9
3/12/2006
Tasks and Data (contd.)

10
3/12/2006
Tasks and Data (contd.)
Shared-Data Problem
 The above code will have bugs because they are sharing the same variable
and the lower priority task might be pre-empted in the middle of a data write
operation.
 A similar problem occurs when 2 tasks call the same function.

void Task1 (void)

{
.
.
vCountErrors(9);
.
.
}

void Task1 (void)

{
.
.
vCountErrors(11);
.
.
}

11
3/12/2006
Tasks and Data (contd.)
static int cErrors;

void vCountErrors(int cNewErrors)

{
cErrors +=cNewErrors;
}
 As both tasks call vCountErrors they hence share the
variable cErrors causing potential bugs.
Reentrancy
 A function that can be called by multiple tasks and still work
correctly is called reentrant.
 The 3 rules that determine if a function is reentrant are :-
1. The function must not use variables nonatomically unless they
are stored on the stack of the calling task or are the local
variables of that task.
2. The function must not call functions that are not reentrant
3. It must not use hardware nonatomically.

12
3/12/2006
Tasks and Data (contd.)
Review of C Variable Storage
 The following code (fig. 6.9)shows which variables
are stored in memory instead of stack and can
hence cause problems.
static int static_int;
int public_int;
int initialized =4;
char *string = “Where am I stored?”;
void *vPointer;

void function (int parm, int *parm_ptr)

{
static int static_local;
int local;
.
.
}
13
3/12/2006
Tasks and Data (contd.)
 static_int – stored in memory and hence a shared variable
 public_int – Same as above. However in addition, functions in other C
files can also access this variable.
 intitialized– Ditto.
 string – Same
 vPointer – Same
 parm – stored on stack so will not cause a problem
 parm_ptr – stack. Will not cause problem as long as every task passes a
different value for it.
 static_local – stored in memory. Only difference between it and
static_int is that the other can be accessed by other functions in the C
file while this variable can only be accessed by function.
 local – stack.

14
3/12/2006
Tasks and Data (contd.)
Gray Areas of Reentrancy
 The following code falls in the gray area between reentrant
and nonreentrant functions.
static int errors;
void vCountErrors()
{
++errors;
}
 Where it falls depends on the processor e.g. an 8051 might
translate ++errors as 8-9 assembly instructions in which
case it is nonatomic while an 8086 microprocessor might just
give

INC (errors)
RET

In which case ++errors is atomic making the function

reentrant.
15
3/12/2006
Semaphores and Shared Data
 Semaphores are one way of protecting shared variables.
 Name is derived from the old railroad days when they were
used to share a segment of rail between more than one train.

RTOS Semaphores
 Consider two functions for dealing with the RTOS binary
semaphores – TakeSemaphore and ReleaseSemaphore.
 If a task has called TakeSemaphore to take the semaphore,
any other task calling it will block until the semaphore is
released (ReleaseSemaphore).
 Fig. 6.12 solves the shared-data problem of fig. 6.6 using a
semaphore.

16
3/12/2006
Semaphores and Shared Data (contd.)

17
3/12/2006
Semaphores and Shared Data (contd.)
 With this new setup consider the scenario where
the ‘levels task’ (vCalculateTankLevels) has just
taken the semaphore and is pre-empted by the
higher priority ‘push button’ task.
 The RTOS will move the higher priority task to the running
state.
 When this task tries to lock the semaphore, it will block.
 The OS will then run the task which has the semaphore
(levels task) until it releases it.
 As soon as this happens, the RTOS will switch back to the
higher priority task which is now unblocked.

18
3/12/2006
Semaphores and Shared Data (contd.)
Reentrancy and Semaphores
 The following code shows how a shared function shown before can
be made reentrant by using semaphores.

void Task1(void)
{ .
.
vCountErrors(5);
.
}
void Task2(void)
{ .
.
vCountErrors(10);
.
}

static int cErrors;

static NU_SEMAPHORE semErrors;

19
3/12/2006
Semaphores and Shared Data (contd.)
void vCountErrors (int cNewErrors)
{
NU_Obtain_Semaphore (&semErrors, NU_SUSPEND);
cErrors +=cNewErrors;
NU_Release_Semaphore (&semErrors);
}
 Functions and data structures beginning with “NU” are those used in an RTOS
called Nucleus.

Multiple Semaphores
 RTOSs normally allow the users to have multiple semaphores that are
distinctly identified by a parameter (semErrors in above code) and are
independent of each other.
 This speeds task responses – a high priority task does not have to be blocked
by a lower priority one as long as it is using a different semaphore.
 It is the users responsibility to remember which semaphore protects which
shared data – the OS will not do that.

20
3/12/2006
Semaphores and Shared Data (contd.)
Semaphores as Signaling Devices
 Semaphores can be used to communicate between a task and
another task or an interrupt routine.
 Fig. 6.16 – Simon shows a printer example.
 A task stores formatted reports, to be printed, into memory.
 The printer interrupts after each line, on which the ISR feeds it the
next line.
 This is done by having the task wait on a semaphore after it has
formatted a report. The ISR will release the semaphore once the
report has been printed and the task can start on the next report.
 Note – the semaphore has been initialized as already taken. Hence
the task can only take the semaphore after the first report. This is
acts as initializing the process for the task.

21
3/12/2006
Semaphores and Shared Data (contd.)

22
3/12/2006
Semaphores and Shared Data (contd.)
Semaphores Problems
 Forgetting to take it – Semaphores only work if tasks actually
remember to use them while accessing shared data.
 Forgetting to release the semaphore – This will cause all tasks
using the semaphore to be eventually blocked forever.
 Holding it for too long – Higher priority tasks might loose their
deadlines if some lower priority task holds the semaphore for too
long.
A problem that can happen is if a low priority task C has a semaphore
and a higher priority task B that does not use the semaphore pre-
empts it in between.
Now suppose the highest priority task A comes along and is blocked
on the semaphore. As B has a higher priority than C it will run instead
and might block A for long enough that it misses its deadline.
This is called priority inversion. Some RTOSs temporarily give task
A’s priority to C (and hence prevent B from pre-empting C).
23
3/12/2006
Semaphores and Shared Data (contd.)
 Causing a deadly embrace (deadlock) – The
following code (fig. 6.18) illustrates this problem.
int a,b;
AMXID hSemaphoreA;
AMXID hSemaphoreB;
void Task1 ()
{
ajsmrsv (hSemaphoreA, 0, 0);
ajsmrsv (hSemaphoreB, 0, 0);
a = b;
ajsmrls (hSemaphoreA);
ajsmrls (hSemaphoreB);
}

void Task2 ()
{
ajsmrsv (hSemaphoreB, 0, 0);
ajsmrsv (hSemaphoreA, 0, 0);

24
3/12/2006
Semaphores and Shared Data (contd.)
b = a;
ajsmrls (hSemaphoreB);
ajsmrls (hSemaphoreA);
}

 Functions ajsmrsv (reserve semaphore) and ajsmrls

(release semaphore) are from an RTOS AMX.
 The additional parameters in ajsmrsv are the time-out and
priority.
 Now suppose Task1 has just reserved hSemaphoreA and is
pre-empted by Task2. Task2 reserves hSemaphoreB but
when it tries to reserve hSemaphoreA it is blocked.
 The RTOS switches to Task1 which tries to reserve
hSemaphoreB and is blocked by Task2. Hence the 2 tasks
block each other and are caught in a deadlock.
 Hence use of semaphores should be avoided where possible.

25
3/12/2006
Semaphores and Shared Data (contd.)
Semaphores Variants
 Some systems allow semaphores that can be taken multiple time.
Taking them decrements their count and releasing increments it.
They are hence called counting semaphores
 Semaphores that can only be released by the task that took them are
resource semaphores. Though they prevent shared-data bugs, they
cannot be used for task inter-communication.
 A semaphore that deals with priority inversion is commonly called a
mutex semaphore or mutex (mutually exclusive).

Methods to Protect Shared Data

 The 2 basic methods are disabling interrupts and using semaphores.
 A third method is disabling task switches, but this has no effect on
interrupt routines.
 Note – interrupts are not allowed to take semaphores so they
cannot be used if the data is shared between the task code and the
ISR.

26
3/12/2006