Real-Time Operating Systems Part 2

Design & Analysis for Embedded & Time-Critical Systems

Dr. Tom Clarke

tjwc - 17-Mar-09

Real-Time Operating Systems

2.1

RTOS Course Structure

1.1 Introduction
Tasks

PART 1 Real-Time
Applications

1.2 Task Control in FreeRTOS

PART 2 - Implementation

Hardware
Background/foreground systems
Interrupts vs tasks

Task states
FreeRTOS API

1.3 Shared Data Access

1.4 Semaphores
Theory and applications

1.6 Synchronisation

Theory and applications

tjwc - 17-Mar-09

2.4 Timing Functions

Clock Tick
Task Delay implementation

1.8 & 1.9 Scheduling Problems

Deadlock, starvation & livelock
Priority inversion

2.3 Context Switching

AVR example
Source code

1.7 Scheduling Theory

Priority scheduling
Round-robin scheduling
RMA, extended RMA, & deadlines

2.2 RTOS Task Lists

Linked List implementation
Bit-mapped task list implementation

1.5 Message Queues

Theory and applications

2.1 Interrupts & Exceptions

2.5 RTOS Objects

Semaphores
Message Queues

Real-Time Operating Systems

2.2

Anatomy of an RTOS
RTOS Design Goals
Portability
Minimise code specific to a given
architecture/compiler

Scalability
Make feature-set configurable, so the
same system can be configured for
very small, or large, systems

Hardware interface
Interrupt handling
Task switching
Clock tick implementation

Scheduling
Communication & Synchronisation
Memory Allocation
Timers & Delay Implementation
tjwc - 17-Mar-09

Performance
Low interrupt-level & task-level latency

Interested in maximum limit, not

average

Low RAM use

Rich Feature-set?
Ways to deal with priority-inversion
Deadline scheduling
Rich set of comms & synch primitives

Real-Time Operating Systems

2.3

Part 2 - RTOS Implementation

Interrupts
Simple foreground/background systems
How the RTOS responds to events
Polling vs timer ISR vs ISR

Interrupt latency
Task or interrupt?

RTOS Implementation
Task lists & scheduler
Linked lists vs bit-mapped array

Pre-emption & context switch

Task creation
RTOS startup

Timing & delays

Clock tick
Delay functions

Calling scheduler from tasks

Semaphores
Queues
tjwc - 17-Mar-09

vTaskIncrementTick()
vPortYieldFromTick()
vPreemptiveTick()
prvCheckDelayedTasks()
vTaskDelay()
vTaskSwitchContext()
portSAVE_CONTEXT()
taskYIELD()
xTaskCreate()
vTaskStartScheduler()
xPortStartScheduler
vPortISRStartFirstTask()
xQueueSend()
prvUnlockQueue()
prvLockQueue()
prvCopyQueueData()
xQueueReceive()

Real-Time Operating Systems

2.4

Lecture 2.1 - Interrupts

There cannot be greater rudeness than to interrupt another in

the current of his discourse
John Locke
Interrupts are the fundamental device which
allows sequential computer programs to
Provide a very fast
respond to real-time events
response to a hardware
Interrupts require hardware support
event
ALL CPUs provide some way of implementing
interrupts
Boundary between hardware & software
support is variable
As a minimum save/switch of PC must be
implemented in hardware

Interrupt processing

Stop code currently executing

Branch to Interrupt Service Routine (ISR)
Execute ISR
Return transparently to previous executing
code

tjwc - 17-Mar-09

Timer timeout
I/O request

Note that ISR is very

different from a task no
state is saved from one
invocation to the next
Can't implement infinite
loop
Can't block

Real-Time Operating Systems

2.5

Interrupt Priority
Three prioritised ISRs
3

2
1
Background code

Time

Microprocessors provide prioritised execution of interrupts

During interrupt priority n, all lower priority interrupts are disabled
Disabled interrupts will be enabled and executed at the first possible time
when the current priority level drops below that of the disabled interrupt

Hardware support can implement branch to the correct ISR for each
interrupt
Vectored priority interrupt controller

Many different combinations of hardware/software possible.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.6

Rate Monotonic Analysis for Interrupts

Prioritised interrupts provide

response to deadlines very
similar to prioritised tasks
implementing jobs

Interrupt priority n
Hardware event initiates
computation

RMA analysis can be used to

determine whether all ISRs will
terminate before next ISR
invocation

ISR n
Cn
Tn

Interrupt
Task

tjwc - 17-Mar-09

Interrupt
n occurs

ISR n
runs

ISR n
returns

Task n
becomes
ready

Task n
runs

Task n
blocks

Real-Time Operating Systems

2.7

Forground/Background System Design

Real-time systems can be implemented without an RTOS using

foreground/background design
Time-critical computation implemented via interrupt-driven ISR
(foreground)
Non-critical computation implemented in background loop
Note only one background loop is possible
Non-critical hardware can be serviced from background loop using polling

Loop length is variable depending on which devices need to be serviced

Worst-case loop length determines latency for polled devices

Advantages
Simple
More efficient than RTOS

Disadvantages
More computation must be implemented in ISR coding more
complex & difficult to debug
Can't use tasks to simplify & modularise design

tjwc - 17-Mar-09

Real-Time Operating Systems

2.8

Polling from Timer interrupts

Interrupt-driven paradigm locates

computation in specific ISRs executed in
response to hardware events

BackgroundLoop()
{
for (;;) {
if (device A is ready) [ Service Device A ];
if (device B is ready) [ Service Device B ];
}
}

Timer-interrupt ISR polls multiple devices

at regular intervals
provides guaranteed response with less
hardware overhead than device-specific
hardware interrupts
Simpler to code than multiple separate ISRs

Timer1_ISR() // device C or D
{
if (device C is ready) [ Service Device C ];
if (device D is ready) [ Service Device D ];
[ update system clock ]
}

Background loop also implements polled

computation but time between successive
polls cannot easily be determined.

DeviceE_ISR()
{
[ Service Device E ]; /*NB polling not needed*/
}

Interrupt-driven computation in ISR trigerred

by hardware event
Response time is limited by CPU-determined
interrupt time + execution time of any higher
or equal priority interrupts

Cf time-interrupt polling & background

loop polling

tjwc - 17-Mar-09

Real-Time Operating Systems

2.9

Response-time: Timer ISR polling vs

background loop

Can use one or more timer ISRs running at different speeds

e.g. 1ms and 10ms to implement half-way house between
polled & interrupt-driven paradigms
1ms interrupt runs higher priority than 10ms interrupt
1ms interrupt provides response-time (latency) of 1ms worst case, but
total length of ISR must be << 1ms
10ms interrupt provides response-time of 10ms worst case. Total
length of ISR must be <<10ms. Note that 10ms ISR execution time is
effectively slowed down by CPU utilisation due to 1ms interrupt (and
other high priority interrupts)

Background loop can be used to implement polled

computation which is not time-critical.
Polling time for background loop is variable and depends on overall
loop period.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.10

Interrupt Latency (1)

The next few slides show how to

work out the maximum (worstcase) latency for code servicing a
device from a device interrupt or
a timer ISR
Interupt Latency is measured
from a hardware event to the
start of the ISR user code
Interrupt performance is often
specified in terms of maximum
allowed latency, and therefore
requires analysis different from
RMA

interrupt
occurs
Latency

E Dev ISR

Lower
level
code

Interrupt entry:
Hardware entry
Save lower level context

tjwc - 17-Mar-09

User
Code

Real-Time Operating Systems

Interrupt return:
Restore lower level context
Hardware return

2.11

Interrupt Latency (2)

In real-time systems the deadline for ISR execution is often stricter than
that used in RMA.
Deadlines are specified as a maximum allowed interrupt latency: delay
from the interrupt being raised to the ISR starting
Worst-case interrupt latency Ln for ISR priority n must be explicitly
calculated by considering:
Delay from non-interrupt code to the first ISR
All ISRs of higher priority than n
Interrupt entry & return time

Best-case latency = E

Ln C E

D4
critical
section
length C

ISR 4 R

i m

( D E R)

i n 1

D3
E

ISR 3 R

D2

ISR 2

ISR 2 latency
C
tjwc - 17-Mar-09

Real-Time Operating Systems

2.12

Polling Latency from Timer Interrupt

The maximum Latency for a

Best
Worst
device polled from timer interrupt
response
response
(LP) is the period of the timer (P)
+ the worst-case difference in
P
timer ISR response-time from
one interrupt to the next.
Lp
Assuming that the timer ISR is
priority n, and using results on
i m
Latency for timer
previous slide
Ln C E
( Di E R)
ISR priority n
Difference also represents timing
i n 1
i m
jitter for sample if I/O time is
LP P Ln E P C
( Di E R)
software controlled

Note that hardware controlled

A/D avoids jitter

Worst case
latency

tjwc - 17-Mar-09

i n 1

Best case
latency
Real-Time Operating Systems

2.13

Interrupts and tasks

In an RTOS devices can still be

handled by interrupts
All interrupts run at a higher
priority than all tasks
ISRs must be written to inform
RTOS that they are executing
(RTOS-dependent mechanism)

NOTE all interrupts are higher in

priority than all tasks
ISRs can handle devices directly
ISRs can signal tasks which then
handle device (next slide)

tjwc - 17-Mar-09

ISR 2

ISR 2

ISRs
ISR 1
increasing
priority

Tasks

Task 3
Task 2

Task 1

Real-Time Operating Systems

2.14

Tasks synchronised to interrupts

ISR for device X can signal

a semaphore to unblock a
waiting device-handler task
Make ISR as short as
possible
time-critical code has
interrupt latency
Rest of code also has task
latency

tjwc - 17-Mar-09

DeviceX_Task

task
latency

DeviceX_ISR
interrupt
latency

total latency of
DeviceX_task

DeviceX_ISR()
{
[ time-critical handler code ]
SemaGiveFromISR(SemaX);
}
DeviceX_Task()
{
for (;;) {
SemaTake(SemaX); /*wait for device*/
[ rest of handler code ]
}
}

Real-Time Operating Systems

2.15

Lecture 2.1 Summary

Simplest real-time systems are implemented using the

foreground/background model using interrupts and background loop.
Interrupts can be used to provide guaranteed latency & response-time
Interrupts have priority which determines precedence
Interrupt priorities are managed by device-dependent hardware or software.
All CPUs allow individual interrupt sources to be switched on or off which in principle
allows software control of priorities
In practice for speed prioritised interrupts are managed by special hardware in big
systems

I/O operations can be performed:

From hardware-specific interrupt
From timer interrupt (polled)
From background loop (polled)

RMA can be used to determine whether prioritised interrupt deadlines are

met
More precise calculation must add interrupt entry and return times to ISR time
when calculating RMA compute time Ci
Deadline is met if interrupt response-time is less than time between interrupts

tjwc - 17-Mar-09

Real-Time Operating Systems

2.16

Lecture 2.2 Implementing Task Lists

It is easy to go down into Hell; night and day,
the gates of dark Death stand wide; but to climb
back again, to retrace one's steps to the upper
air - there's the rub, the task.
Virgil, Aeneid

tjwc - 17-Mar-09

Real-Time Operating Systems

2.17

Implementing an RTOS: Data Structures

TASKS
Task
Stack

Task
Control
Block

Task
SUSPEND
List

Task
READY
List

Task
DELAYED
List

Current Task Pointer

Task
Stack

tjwc - 17-Mar-09

Task
Control
Block

Task
Control
Block

RTOS Objects

PC

Semaphore
Waiter
List
Semaphore
Control
Block
Real-Time Operating Systems

Registers

PSR

Processor context

Task
Stack

2.18

How is task state recorded?

Possible states:
READY
BLOCKED on timeout (DELAYED)
BLOCKED on EVENT
SUSPENDED

NB - must be simultaneously delayed & blocked on

event to implement semaphore timeouts etc
Need to know
What is the highest priority task in given state?
Are there any tasks in given state?

Need to change state of given task

SOLUTION - Task "lists"
Often implemented as linked lists

tjwc - 17-Mar-09

Real-Time Operating Systems

2.19

Task Lists

Every task links to at

most two distinct lists
READY/DELAYED/SUSP
END List generic list link
Mutually exclusive

READY List
Need to extract the highest
priority task

DELAYED task list

Need to extract all tasks whose
delay-time has elapsed

SUSPENDED list
At most one EVENT list

Need to extract resumed task

event list link

Suspended tasks are

not allowed to wait on
semaphores while
suspended, so they are
removed if necessary
from their EVENT list on
suspension.
tjwc - 17-Mar-09

EVENT lists
Lists for waiters on semaphores
& other objects
A separate list for each object
Need to extract the highest
priority task
Real-Time Operating Systems

2.20

FreeRTOS Lists

Implement generic packages of ordered task lists

Each item in the list has assigned a value
List is ordered by descending value

Implement operations

Insert task in list with value at correct position

Remove task from front of list (largest value)
Remove task from end of list (smallest value)
Remove arbitrary task from list

Use this package to implement all RTOS lists

READY & EVENT lists: sort value = priority
DELAYED List: sort value = wake-up time

Use doubly linked lists to allow quick removal

List nodes are part of Task Control Block
One less level of indirection
Tasks can be in at most two different lists
tjwc - 17-Mar-09

Real-Time Operating Systems

2.21

Task list data structures: doubly-linked

circular list
list:
NumberOf
Items: 2
index: ?

Item:

ListEnd:
itemvalue

itemvalue

itemvalue

next

next

next

previous

previous

previous

owner

owner

container

container

Event
ListItem

Generic
ListItem

TCB
tjwc - 17-Mar-09

Dummy list
item marks
end & start
of circular
list

Real-Time Operating Systems

2.22

List operations - Remove

px

pxp

pxn

O(1) constant time

itemvalue

itemvalue

itemvalue

next

next

next

previous

previous

previous

owner

owner

owner

Remove(px)
container
container
{
pxn = px->next;
pxp = px->previous;
pxn->previous=pxp;
pxp->next=pxn;
px->container->numberofitems--;
px->container = NULL;/* if px matters */
}
tjwc - 17-Mar-09

Real-Time Operating Systems

container
numberofitems

index
itemvalue
next

previous
2.23

List operations - InsertAfter

px

pz

pxn

O(1) constant time

itemvalue

itemvalue

itemvalue

next

next

next

previous

previous

previous

owner

owner

container

container

InsertAfter(px, pz)
owner
{
pxn = px->next;
container
px->next = pz;
pxn->previous=pz;
pz->next=pxn;
pz->previous=px;
pz->container=px->container;
px->container->numberofitems++;
}

numberofitems

index
itemvalue
next

previous
tjwc - 17-Mar-09

Real-Time Operating Systems

2.24

List operations - InsertSorted

Insert new item

px into list pxl in
sorted position

O(list length)
linear time

pxl->listend
3

10

22
15

22

99
22

MAX
101

InsertSorted( px, pxl)

{ /*pxit is list item pointer (iterator)*/
v = px->itemvalue; /*assume v < MAX*/
for( pxit = pxl->listend; pxit->next->itemvalue <= v; pxit = pxit->next ) {
/* There is nothing to do here, we are just iterating to the
wanted insertion position. */
}
InsertAfter( pxit, px);
}
tjwc - 17-Mar-09

Real-Time Operating Systems

2.25

Why doubly-linked circular list?

Doubly-linked list means removing

an item is easy
Circular list means start & end of
list is not a special case
Dummy (sentinel) item means that:

List operations have no special

cases and are simple to implement
Tasks can remove themselves
from lists removal is O(1)
Linked list structure is very flexible
no constraints on task
priorities or number of tasks
List nodes separate allow standard
package of list functions to be
used

Empty list is not a special case

List start/end is marked

Links from list items to list header

needed for header update on
removal of item
Implementing list items as part of
TCB mean that task data structures
can be accessed from list items
and list items accessed from tasks
with no overhead.
tjwc - 17-Mar-09

Advantages

Storage for list nodes is allocated

as part of TCB structure

Disadvantages
Sorted Insertion operation takes
typical time O(length of list)
Extra pointers are an overhead

Real-Time Operating Systems

2.26

Why is time important?

RTOS operations: e.g. tasks waking up and blocking

involve changes to lists
Worst case time for operation is important RTOS
performance characteristic
Deterministic time e.g. time does not depend on what
other tasks are doing is desirable
For this doubly-linked list implementation:
Insert, InsertAfter, InsertStart, InsertEnd, Remove
O(1)=>Deterministic

InsertSorted
Depends on length of list and insert position
Worst case scales as number of tasks in system

tjwc - 17-Mar-09

No list can be longer than total number of tasks

Real-Time Operating Systems

2.27

FreeRTOS lists module

FreeRTOS implements in lists.h a set of doubly linked list

operations, using C functions & macros, which are used throughout
the RTOS
void vListInitialise( xList *pxList )
void vListInsertEnd( xList *pxList, xListItem *pxNewListItem )
void vListInsert( xList *pxList, xListItem *pxNewListItem )
void vListRemove( xListItem *pxItemToRemove )
listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )
listSET_LIST_ITEM_VALUE( pxListItem, xValue )
listGET_LIST_ITEM_VALUE( pxListItem )
listLIST_IS_EMPTY( pxList )
listCURRENT_LIST_LENGTH( pxList )
listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )
listGET_OWNER_OF_HEAD_ENTRY( pxList )
listIS_CONTAINED_WITHIN( pxList, pxListItem )
tjwc - 17-Mar-09

Real-Time Operating Systems

2.28

FreeRTOS Ready List optimisation

The Ready list changes whenever a task becomes READY or

blocked
Efficient implementation is important

Instead of having a single list the ready list is implemented as an

array of lists, indexed by task priority
Number of tasks in each list is smaller (normally only one!)
Correct list for a given task can easily be found
pxReadyTasksLists[]

tjwc - 17-Mar-09

31
30
29
...
1
0

configMAX_PRIORITIES
Doubly
linked
list

Real-Time Operating Systems

2.29

Optimisation (2)

Task Addition is now much faster, but finding the highest priority
ready task means scanning the array to find highest non-empty
location.
Use extra global variable to store top priority currently in ready list
Highest priority task normally from topReadyPriority list
If this is empty search downwards in array until non-empty list is found
Update uxTopReadyPriority

This trades lower cost on access for higher cost on update

Good policy if either the information is accessed more often than it is
changed
Or if calculating the change is quicker than calculating the information
from scratch
31
Often "incremental claculation" is quick
Empty
30
lists
.
2
uxTopReadyPriority
READY
1
tasks
0
tjwc - 17-Mar-09

Real-Time Operating Systems

2.30

MicroC/OS-II Ready List optimisation

MicroC/OS-II uses a
completely different and
clever implementation for all
its priority ordered task lists.
Suppose each task has a
unique priority so tasks
can be identified by their
priority, and the priorities lie in
a small range. We will assume
priority P satisfies: 0 P < 64
Any power of 2 can equally
well be used
One byte stores 8 array
locations
tjwc - 17-Mar-09

A task list can be represented as

a array with 1 location for each
possible priority (and hence
task). Locations set to 1 mean
that tasks are in the list.
Each item in array needs only 1
bit, so pack 8 items into each
byte as shown below
This allows highly efficient
operations

Here tasks 5,4, and 1 are in list

7 6 5 4 3 2 1 0
0 0 1 1 0 0 1 0

Real-Time Operating Systems

2.31

OSRdyTbl

OSRdyTbl

Bit-mapped array: 1 bit per task

Max 8 bytes => 64 bits
1=> task is waiting

[0]

Each row is a single byte,

containing 8 bits with the task
priorities shown in the diagram
Total 8 bytes required for 64 bits of
table
To access bit, first select correct
byte (index 0-7), then select correct
bit
Very space efficient

tjwc - 17-Mar-09

[1]

15 14 13 12 11 10 9

[2]

23 22 21 20 19 18 17 16

[3]

31 30 29 28 27 26 25 24

[4]

39 38 37 35 35 34 33 32

[5]

47 46 45 44 43 42 41 40

[6]

55 54 53 52 51 50 49 48

[7]

63 62 61 60 59 58 57 56

Real-Time Operating Systems

2.32

Bit-mapped array characteristics

Sorting is not required since each task is recorded at a

position based on priority
Finding highest priority task requires linear search of table
We will see later that this can be very efficient

Inserting or removing a task setting or clearing a bit

at a predefined position in the array determined by the
task priority
This is clearly O(1) and very fast

To speed up the search for highest priority task present

we need one more data structure
See next slide

tjwc - 17-Mar-09

Real-Time Operating Systems

2.33

OSRdyGrp

OSRdyGrp is a
summary byte.
Each bit is the OR of
all the bits in one byte
(row) of OSRdyTbl
This doubles the time
of insert & remove
operations, but they
are still fast.

OSRdyGrp is used to
implement very fast
searching.

tjwc - 17-Mar-09

OSRdyTbl
0
1
2
3
4
5
6
7

Real-Time Operating Systems

2.34

How to find highest non-zero bit in a byte?

Not simple operation

One byte has only 256 distinct
values
Use byte value to index a 256 byte
constant array
Store bit number of highest '1' bit
of index in each array element

Trades space (table size) for faster

task switch time
For small systems table size can
be reduced since it depends on
number of tasks

tjwc - 17-Mar-09

255: 11111111
.....

8:
7:
6:
5:
4:
3:
2:
1:
0:

7
...

00001000
3
00000111
2
00000110
2
00000101
2
00000100
2
00000011
1
00000010
1
00000001
0
00000000 not used
76543210
OSUnMapTbl
index

Real-Time Operating Systems

2.35

Table-driven search for highest priority task

{

y = OSUnMapTbl[OSRdyGrp]; //
x = OSUnMapTbl[OSRdyTbl[y]];//
prio = ( y << 3) + x;
//
//

highest set bit no in OSRdyGrp

highest set bit no in OSRdyTbl[y]
combine x and y to get highest prio
<< 3 is left shift by 3, used for X8

The "highest non-zero bit search" is still quite expensive.

Solution is to remember search results in a constant array OSUnMapTbl[]
8 bits256 possible combinations
256 locations needed in table

O(1) constant time

Result is a number between 7 and 0

Will fit into 1 byte
OSUnMapTbl[] is 256 byte constant array

Each operation 1) & 2) on previous slide is now a byte table lookup

Overall search algorithm is now fast and deterministic time
tjwc - 17-Mar-09

Real-Time Operating Systems

2.36

Bit-mapped array list summary

Advantages
All operations are O(1), and can be very fast if number of
priorities is small
Operation time is independent of number of tasks in lists

Disadvantages
All priorities must be unique
Does not allow round-robin scheduling

Not a problem for many real-time systems

Makes dynamic priority-changing (e.g. to avoid priority inversion)

much more difficult

Does not scale nicely to increased number of tasks

All tables use at least 1 bit per priority level. 216 priorities 8K
bytes per table!
Search algorithm less efficient for larger tables
tjwc - 17-Mar-09

Real-Time Operating Systems

2.37

Lecture 2.2 Summary

Task lists are basic data structure used to control task scheduling
in an RTOS
All RTOS uses task lists for:

READY list
Delayed task list
Event waiting task lists (semaphores etc)
Suspended Task List

Task lists can be implemented in various ways. Two popular are:

Linked lists can be single or doubly-linked.
FreeRTOS uses doubly-linked lists

Bit-mapped array lists

tjwc - 17-Mar-09

Less flexible but can be very fast

Task priority determines unique position in a bit array
Cant have multiple tasks with the same priority!
Does not necessarily scale very well with large number of tasks
Real-Time Operating Systems

2.38

Lecture 2.3 Context Switching

The key to any RTOS is ability to switch between tasks

Two main methods

Co-routine (cooperative) switching
Preemptive switching

This lecture covers task startup and preemptive switching

Implementation is necessarily architecture & compiler-specific

Code is v low-level & must be rewritten for different compiler
Most of code is written in assembler

Context switching involves changes to system stack etc and

therefore throughout this code interrupts must be switched off

Scheduler decides which task should next run and then if

necessary invokes context switching
tjwc - 17-Mar-09

Real-Time Operating Systems

2.39

RTOS Scheduler

Function of scheduler is to decide which of the available READY

tasks should be run next
Scheduler changes pxCurrentTCB

After calling the scheduler the context switch code (see later) can
complete the task switch
Scheduler is called from task level as taskYield() (see later)
FreeRTOS uses priority scheduling with round-robin time-slicing for
tasks of equal priority
All this is implemented using generic doubly-linked list package for
compact code
FreeRTOS uses same doubly-linked list package for other purposes

tjwc - 17-Mar-09

Real-Time Operating Systems

2.40

void vTaskSwitchContext( void )

{
if( uxSchedulerSuspended != ( unsigned portBASE_TYPE ) pdFALSE )
{
/* The scheduler is currently suspended - do not allow a context
switch. */
xMissedYield = pdTRUE;
return;
}
/* Find the highest priority queue that contains ready tasks. */
while(listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopReadyPriority ] ) ) )
{
--uxTopReadyPriority;
}

/* listGET_OWNER_OF_NEXT_ENTRY walks through the list, so the tasks

of the same priority get an equal share of the processor time. */
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB,
&( pxReadyTasksLists[ uxTopReadyPriority ] ) );
vWriteTraceToBuffer();

Tasks & Stack

Task1()
{
f1(10);
}
f1( int a)
{
int b;
.
f2();
}
Task2()
{
..
f3();
.
}

tjwc - 17-Mar-09

Stack top
during
execution
of f2()

f2

Task2
context

f3

f1
Task1

Stack
base
Task1
stack

Real-Time Operating Systems

Task2

Task2
stack

2.42

How is a Task Implemented?

To understand context switch we need to know precisely how a

task is implemented
The next five slides show the FreeRTOS code which creates and
manipulates the RTOS data structures which represent tasks
This code is not very complex, but quite long because it must do am
lot of work
Task creation must work both before the scheduler is started, and
afterwards

Tasks are initially created in a suspended form, before scheduling

is started
Since the RTOS always runs with one running task, the RTOS
startup code must initially move one task to running status &
commence its code.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.43

signed portBASE_TYPE xTaskCreate( pdTASK_CODE pvTaskCode,

const signed portCHAR * const pcName, unsigned portSHORT usStackDepth,
void *pvParameters, unsigned portBASE_TYPE uxPriority, xTaskHandle *pxCreatedTask )
{
signed portBASE_TYPE xReturn;
tskTCB * pxNewTCB;
static unsigned portBASE_TYPE uxTaskNumber = 0;

/* Allocate the memory required by the TCB and stack for the new task.
checking that the allocation was successful. */
pxNewTCB = prvAllocateTCBAndStack( usStackDepth );
if( pxNewTCB != NULL )
{
portSTACK_TYPE *pxTopOfStack;

/* Setup the newly allocated TCB with the initial state of the task. */

prvInitialiseTCBVariables( pxNewTCB, usStackDepth, pcName, uxPriority );

/* Calculate the top of stack address. This depends on whether the

stack grows from high memory to low (as per the 80x86) or visa versa.
portSTACK_GROWTH is used to make the result positive or negative as
required by the port. */

#if portSTACK_GROWTH < 0

{
pxTopOfStack = pxNewTCB->pxStack + ( pxNewTCB->usStackDepth - 1 );
}
#else
{
pxTopOfStack = pxNewTCB->pxStack;
}
#endif

FreeRTOS Task
Creation

/* Initialize the TCB stack to look as if the task was already running, but had been interrupted
by the scheduler. The return address is set to the start of the task function. Once the stack
has been initialised the top of stack variable is updated. */

pxNewTCB->pxTopOfStack = pxPortInitialiseStack( pxTopOfStack, pvTaskCode, pvParameters );

/* We are going to manipulate the task queues to add this task to a

ready list, so must make sure no interrupts occur. */
portENTER_CRITICAL();
{

uxCurrentNumberOfTasks++;
if( uxCurrentNumberOfTasks == ( unsigned portBASE_TYPE ) 1 )
{

/* As this is the first task it must also be the current task. pxCurrentTCB = pxNewTCB*/
/* This is the first task to be created so do the preliminary initialisation required.
We will not recover if this call fails, but we will report the failure. */
}
else
{

prvInitialiseTaskLists();

/* If the scheduler is not already running, make this task the current task
if it is the highest priority task to be created so far. */
if( xSchedulerRunning == pdFALSE )
{
if( pxCurrentTCB->uxPriority <= uxPriority )
{
pxCurrentTCB = pxNewTCB;
}
}

FreeRTOS Task
Creation (2)

/* Remember the top priority to make context switching faster. Use

the priority in pxNewTCB as this has been capped to a valid value. */
if ( pxNewTCB->uxPriority > uxTopUsedPriority ) {
uxTopUsedPriority = pxNewTCB->uxPriority;
}

/* Add a counter into the TCB for tracing only. */

pxNewTCB->uxTCBNumber = uxTaskNumber;
uxTaskNumber++;
prvAddTaskToReadyQueue( pxNewTCB );
xReturn = pdPASS;

}
portEXIT_CRITICAL();
} else {
xReturn = errCOULD_NOT_ALLOCATE_REQUIRED_MEMORY;
}
if( xReturn == pdPASS ) {
if( ( void * ) pxCreatedTask != NULL ) {

/* Pass the TCB out - in an anonymous way. The calling function/

task can use this as a handle to delete the task later if required.*/

*pxCreatedTask = ( xTaskHandle ) pxNewTCB;

if( xSchedulerRunning != pdFALSE ) {

/* If the created task is higher priority than the current task then it should run now. */

if( pxCurrentTCB->uxPriority < uxPriority ) {

taskYIELD();
}

}
return xReturn;

FreeRTOS Task
Creation (3)

void vTaskStartScheduler( void )

{
portBASE_TYPE xReturn;

FreeRTOS Startup

/* Add the idle task at the lowest priority. */

xReturn = xTaskCreate( prvIdleTask, ( signed portCHAR * ) "IDLE",

tskIDLE_STACK_SIZE, (void *) NULL, tskIDLE_PRIORITY, (xTaskHandle *) NULL );

if( xReturn == pdPASS )
{

/* Interrupts are turned off here, to ensure a tick does not occur before or
during the call to xPortStartScheduler(). The stacks of the created tasks
contain a status word with interrupts switched on so interrupts will automatically
get re-enabled when the first task starts to run.*/
xSchedulerRunning = pdTRUE;
xTickCount = ( portTickType ) 0;

/*Setting up the timer tick is hardware specific and in the portable interface. */
if( xPortStartScheduler() )
{

/* Should not reach here as if scheduler is running function will not return. */
}
else
{

/* Should only reach here if a task calls xTaskEndScheduler(). */

}

FreeRTOS Startup
Portable Code
portBASE_TYPE xPortStartScheduler( void )
{

/* Start the timer that generates the tick ISR. */

prvSetupTimerInterrupt();
/* Start the first task. This is done from portISR.c as ARM mode
must be used. */
vPortISRStartFirstTask();

/* Should not get here! */

}

return 0;

void vPortISRStartFirstTask( void )

{

/* Simply start the scheduler. This is included here as it can only be

called from ARM mode. */

portRESTORE_CONTEXT();

Stack changes on context switching

Stack top
during
execution
of f2()

Task1
stack

f2

Task2
stack

Task2
context

f3

Task2 stack
top when
suspended
Stack top
on restart
of f3()

Task1
Stack top
when
suspended

Task2
stack

Task2
context

f3

f1
Task2

1: save current context on

Task1() stack
2: restore Task2() context
from Task2() stack
tjwc - 17-Mar-09

Task1
context

f2

f1
Stack Task1
base

Task1
stack

1
PC
R0
.
R15
PSW

Stack Task1
base

Real-Time Operating Systems

Task2

CPU context

2.49

FreeRTOS 8086 Task switching in detail

As well as context switching, task switching involves

some additional work changing RTOS state to reflect
the task change
We will go through the task switch process in detail for
the simple case of an AVR architecture CPU
This illustrates the necessary steps in a simple form

ARM code is more messy because ARM ISA shadow

registers complicate things
FreeRTOS is designed so that maximum possible
amount of work can be done in C
Of course the actual context switch can't be done in a high level
language

tjwc - 17-Mar-09

Real-Time Operating Systems

2.50

Tick interrupt

We will consider the

case of a task TaskA()
which is executing when
a system clock tick
interrupt happens.
The interrupt results in a
higher priority task
TaskB() waking up &
preempting execution.
The overall result is a
task switch.

The SAVE_CONTEXT &

RESTORE_CONTEXT
macros do the difficult
part of the work.
tjwc - 17-Mar-09

/* Interrupt Service Routine for the RTOS tick. */

void SIG_OUTPUT_COMPARE1A( void )
{
vPortYieldFromTick();
asm volatile ( "reti" );
}
/*--------------------------------------*/
Compiled "naked" with nothing saved by compiler

void vPortYieldFromTick( void )

{
portSAVE_CONTEXT();
vTaskIncrementTick(); /* wakes up TaskB() */
vTaskSwitchContext(); /* schedules TaskB()*/
portRESTORE_CONTEXT();
asm volatile ( "ret" ); return to ISR
}
/*--------------------------------------*/

Real-Time Operating Systems

2.51

0: AVR CPU context in TaskA()

8 bits

pxCurrentTCB

TaskA
TCB

32
registers

R0 (A)
R1 (A)
R30 (A)
R31 (A)

TaskA
Code

LDI R0,0
LDI, R1,1
ADD R0, R1

SREG (A)
RTOS state

PCH (A)

PCL (A)

SPH (A)

SPL (A)

TaskA
data

16 bits
NB AVR has downward-growing stack!
tjwc - 17-Mar-09

Real-Time Operating Systems

TaskA
Stack

8 bits
2.52

1: CPU context after Tick Interrupt

8 bits

32
registers

R0 (A)
R1 (A)
R30 (A)
R31 (A)

Timer ISR
JSR vPortYieldfromTick

PUSH R0
MOV R0, SR
PUSH R0

SREG (A)
PCH (A)

PCL (A)

SPH (A)

SPL (A)

16 bits

tjwc - 17-Mar-09

start of
SAVECONTEXT
macro

TaskA
Stack

TaskA
data
PCL
PCH

8 bits
Real-Time Operating Systems

2.53

2: CPU context after portSAVE_CONTEXT()

8 bits

32
registers

PCH (A)
SPH (A)

R1 (A)

Timer
ISR

SAVE

R30 (A)
R31 (A)

PCL (A)
SPL (A)

16 bits

TaskA
Stack
TaskA
data

PCL (A)
PCH (A)
PCL (ISR)
PCH (ISR)
R0 (A)
SREG (A)
R1 (A)
.
R31 (A)

PUSHed by
interrupt
PUSHed by
function call
Pushed by
SAVE_CONTEXT()

Copy of SP (A)
tjwc - 17-Mar-09

TaskA TCB

pxCurrentTCB
Real-Time Operating Systems

2.54

3: RTOS tick time increment

At this point the entire context of taskA has been pushed onto
TaskA stack
It can be retrieved later via the stored SP in taskA TCB

The ISR is still executing, using TaskA stack extra items can be
pushed temporarily without harming the stored context any
change in SP now will not affect TaskA stored SP
vTaskIncrementTick() will alter system time and, we assume,
wake up TaskB
TaskB moved to READY list

vTaskSwitchContext() will see that TaskB is now the highest

priority task in the READY list and select it as the next task.
pxCurrentTCB := TaskB TCB

tjwc - 17-Mar-09

Real-Time Operating Systems

2.55

4: Start of portRESTORE_CONTEXT()
8 bits

32
registers

R1 (A)

MOV SPL,R0
MOV SPH, R1 TaskB

R30 (A)
R31 (A)

PCH
SPH (B)

Timer
ISR

PCL
SPL (B)

16 bits
Copy of SP (B)
tjwc - 17-Mar-09

TaskB TCB

Stack

TaskB
data

PCL (B)
PCH (B)
PCL (ISR)
PCH (ISR)
R0 (B)
SREG (B)
R1 (B)
.
R31 (B)

PUSHed by
interrupt
PUSHed by
function call
Pushed by
SAVE_CONTEXT()

pxCurrentTCB
Real-Time Operating Systems

2.56

5: End of portRESTORE_CONTEXT()
8 bits

32
registers

R0 (B)
R1 (B)
R30 (B)
R31 (B)
SREG (B)

PCH

PCL

SPH (B)

SPL (B)

Timer
ISR
RET
RETI

TaskB
Stack

TaskB
data
PCL (B)
PCH (B)
PCL (ISR)
PCH (ISR)

PUSHed by
interrupt
PUSHed by
function call

16 bits
8 bits
tjwc - 17-Mar-09

Real-Time Operating Systems

2.57

6: Restart of taskB
8 bits

32
registers

R0 (B)
R1 (B)
R30 (B)
R31 (B)
SREG (B)

PCH (B)

PCL (B)

SPH (B)

SPL (B)

Timer
ISR

Final instruction
Of ISR

RET
SUB R0,R1

Next TaskB instr

TaskB
data

TaskB
Stack

16 bits
8 bits
tjwc - 17-Mar-09

Real-Time Operating Systems

2.58

AVR portSAVE_CONTEXT
; interrupts are disabled on entry
; PCH,PCL are pushed onto stack by interrupt
push
r0
;push r0 first to allow SREG to be loaded
in
r0, __SREG_
; r0 := SREG
push
r0
; push SREG
push
r1
clr
r1
; needed since compiler expects 0 in r1
push
r2
Push all
; push r3-r29
other
push
r30
registers
push
r31
lds
r26, pxCurrentTCB ;x := pxCurrentTCB
lds
r27, pxCurrentTCB + 1
in
r0, 0x3d
;r0 := SPL
st
x+, r0
;[x]:=r0, x := x+1
in
r0, 0x3e
;r0 := SPH
st
x+, r0
;[x]:=r0, x := x+1

/* C code here expects r1=0 */

tjwc - 17-Mar-09

Real-Time Operating Systems

2.59

RTOS state during task switch

The RTOS data structures that have changed during

the task switch are:
pxCurrentTCB always points to current task TCB
Changes from TaskA to TaskB

pxReadyTasksLists[] TaskB is added to ready list

See lecture 2.2 For implementation of READY lists

TaskA TCB: SP is updated to correct value for saved TaskA

context

tjwc - 17-Mar-09

Real-Time Operating Systems

2.60

Porting the RTOS context switch

The code which saves & restores context is written in assembler &
depends on CPU, and (to a lesser extent) compiler.
The ARM7 port has very convoluted save & restore code because
ARM processor switches to a different IRQ-mode stack while
processing an interrupt. The saved PC must be extracted from this
stack and saved on the Task stack.
ARM code will be shown here with detailed description of how
the ARM stacks are managed during portSAVE_CONTEXT()
Restore operation (not shown here) is very similar but in reverse

tjwc - 17-Mar-09

Real-Time Operating Systems

2.61

ARM CPU context after IRQ interrupts TaskA

TASK A SP

R0
R1
.
R12
SP R13^
LR R14^
PC R15
TaskA
registers
(System
mode)
CPSR

tjwc - 17-Mar-09

STM/LDM instructions can transfer

either system mode or current
(IRQ) mode registers
^ indicates system mode
R0-R12 are shared
SP R13
LR R14
IRQ mode
shadow
registers

IRQ stack
TaskA
Return address

SPSR

Real-Time Operating Systems

2.62

ARM7 portSAVE_CONTEXT()
STMDB
STMDB
NOP
SUB
LDMIA

SP!, {R0}
SP,{SP}^

STMDB
MOV
LDMIA

R0!, {LR}
LR, R0
SP!, {R0}

/* Push the return address onto the TaskA stack.*/

/* Now we have saved LR can use as SP for TaskA stack.*/
/* Pop R0 so we can save it onto the system mode stack*/

STMDB
NOP
SUB
MRS
STMDB

LR,{R0-LR}^

/* Push all the system mode registers onto the task stack*/

LR, LR, #60

R0, SPSR
LR!, {R0}

/* Adjust stack pointer */

/* Push the SPSR (saved TaskA PSR) onto the task stack.*/

LDR
LDR
STMDB

R0, =ulCriticalNesting
R0, [R0]
LR!, {R0}

LDR
LDR
STR

R0, =pxCurrentTCB
R1, [R0]
LR, [R1]

SP, SP, #4
SP!,{R0}

tjwc - 17-Mar-09

/* Store R0 on IRQ stack temporarily as we need to use it*/

/* Set R0 to point to the task stack pointer.*/

See next slide

Real-Time Operating Systems

2.63

Messing with ARM stacks

On entry ARM SP (R13) points to IRQ-mode stack this is a shadow
register
STMDB

SP!, {R0}

Push R0 on IRQ stack temporarily

as we need to use a register

STMDB SP,{SP}^

Store user-mode SP on IRQ stack.

dont change stack pointer ARM does
not allow a push from user-mode SP

NOP

wait for result

pipelining

SUB

SP, SP, #4

LDMIA SP!,{R0}

tjwc - 17-Mar-09

- needed because of

decrement stack pointer by one item

to complete push of user-mode SP
pop user-mode SP from IRQ stack
into R0
Real-Time Operating Systems

2.64

Lecture 2.3 Summary

Context-switch is implemented at interrupt-level this allows

interrupts to wake up a task
Multiple nested interrupts must unwind to the outermost before the
task-switch is implemented
All user interrupts that wake RTOS tasks must call RTOS code at
entry & exit to inform RTOS

Task-level switch is handled by software interrupt, followed by

interrupt-level switch
Context-switch involves saving & restoring register values to (from)
task stacks, and changing RTOS current task info.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.65

Lecture 2.3 Review Questions

tjwc - 17-Mar-09

Real-Time Operating Systems

2.66

Lecture 2.4 FreeRTOS Timing functions

High resolution timing in an RTOS requires use of a

dedicated hardware interval timer, with interrupt to signal
timeout
Highly system-specific, not part of this course

All RTOS provide lower resolution timing functions

based on a clock-tick interrupt.
Typically 1ms
Period may be configured but should be >> clock tick processing
time

Implementation of clock-tick requires:

Update system clock
Wake up tasks which are waiting on a delay or timeout

tjwc - 17-Mar-09

Real-Time Operating Systems

2.67

Overview: FreeRTOS Source Organisation

FreeRTOS
tasks.c

Also croutine.c for

non-preemptive
scheduling

Core task control code

list.c
Core list package

queue.c
Queue package

Portable
Arm-Keil port
port.c task-level
portable code
portisr.c ISR level
portable code
portmacro.h portable
macro function definitions
tjwc - 17-Mar-09

Include
tasks.h interface to tasks.c
list.h interface to lists.c
queue.h interface to queue.c
FreeRTOS.h includes:
projdefs.h basic definitions

including port specification

portable.h portable definitions

One file for all ports includes

correct portmacro.h

Contains any other stuff

FreeRTOSconfig.h

App-specific definitions

Real-Time Operating Systems

2.68

Overview: FreeRTOS Task States

Task state

Eventlist

Genericlist

READY

no

ReadyList

Waiting on Queue

Queue Waiter list

DelayedTaskList

Waiting on Queue

Queue Waiter list

SuspendedTaskList

Delayed

no

DelayedTaskList

Suspended

no

SuspendedTaskList

xTicksToWait = portMAX_DELAY

=> no timeout

tjwc - 17-Mar-09

Real-Time Operating Systems

2.69

Overview of clock-tick code

System-specific code sets up hardware timer to
provide an interrupt at clock tick frequency
(1000Hz).
Timer ISR performs clock tick operations:

1. Save current task context

2. vTaskIncrementTick()
Perform clock tick processing (inline function to reduce
entry/exit overhead)

3. Call Scheduler
4. Restore selected task context
5. Return from interrupt to selected task
tjwc - 17-Mar-09

Real-Time Operating Systems

2.70

Clock-tick operation

vTaskIncrementTick() -- Clock tick

processing
1. Increment system clock
2. prvChkDelayedTasks()
Check all delayed tasks for possible wakeup
implemented as macro for highest speed

tjwc - 17-Mar-09

Real-Time Operating Systems

2.71

ARM port of timer ISR (in portISR.c)

This is the code used for preemptive scheduling

The actual C code is different from this (conditional compilation) if
RTOS is configured for nonpreemptive scheduling
void vPreemptiveTick( void ) __task
{

/* Save the context of the current task. */

portSAVE_CONTEXT();
/* Increment the tick count - this may make a delayed task ready to run.*/
vTaskIncrementTick();

/* Find the highest priority task that is ready to run. */

vTaskSwitchContext();
/* Ready for the next interrupt. */

T0IR = portTIMER_MATCH_ISR_BIT;
VICVectAddr = portCLEAR_VIC_INTERRUPT;

/* Restore the context of the highest priority task that is ready to run. */
}

portRESTORE_CONTEXT();

tjwc - 17-Mar-09

Real-Time Operating Systems

2.72

Delayed Clock Ticks

FreeRTOS clock tick code must

deal with delayed ticks
When the scheduler is disabled
(preemption lock) clock ticks (which
cause tasks to wake up) are not
executed
They are recorded for later execution

When the scheduler is enabled again

any clock-ticks recorded are executed
immediately as delayed ticks

vTaskSuspendAll()
xTaskResumeAll()

This may wake up tasks, cause

preemption, etc.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.73

Data Structures used by FreeRTOS clock tick

uxMissedTicks
xTickCount
pxDelayedTaskList
pxOverflowDelayedTaskList
uxSchedulerSuspended

pxReadyTasksLists[0]
pxReadyTasksLists[1]
pxReadyTasksLists[2]
.

tjwc - 17-Mar-09

Ready Queue:
Array of task lists
indexed by task priority
See prvAddTaskToReadyQueue()

Real-Time Operating Systems

2.74

inline void vTaskIncrementTick( void )

{
if ( uxSchedulerSuspended == pdFALSE )
{
++xTickCount;
/* increment system clock */
if( xTickCount == ( portTickType ) 0 ) {
[ deal with tick count overflow see 2.77]
}

Normal
Case

/* See if this tick has made a timeout expire.*/

prvCheckDelayedTasks();/*Real work,(next slide)*/

} else { /* if scheduler is suspended */
++uxMissedTicks;
Scheduler locked
[ tick hook ]
} /* end if */
if (uxMissedTicks==0) { /* if tick hook needed */
[ tick hook ]
#if ( configUSE_TICK_HOOK == 1 )
}
{
extern void vApplicationTickHook( void );
vApplicationTickHook();

}
#endif

#define prvCheckDelayedTasks()
{
register tskTCB *pxTCB;

\
\
\
\
while ( ( pxTCB = ( tskTCB * ) listGET_OWNER_OF_HEAD_ENTRY(
\
pxDelayedTaskList ) ) != NULL )
\
{
\
if(xTickCount < listGET_LIST_ITEM_VALUE(&(pxTCB->xGenericListItem) ) ) \
{
\
break; /*this item and all after will wake up in the future, so exit */ \
}
\
vListRemove( &( pxTCB->xGenericListItem ) );/*remove from delayed task list*/\
/* Is the task waiting on an event also? */
\
if( pxTCB->xEventListItem.pvContainer )
\
{
\
/* if so remove it from the event waiters list as well
\
vListRemove( &( pxTCB->xEventListItem ) );
\
}
\
/* add task to ready queue for possible scheduling */
\
prvAddTaskToReadyQueue( pxTCB );
\
}
\
}

Tick count overflow

If ( xTickCount == ( portTickType ) 0 )
{
xList *pxTemp;

/* Tick count has overflowed so we need to swap the delay lists.

If there are any items in pxDelayedTaskList here then there is
an error! */

pxTemp = pxDelayedTaskList;
pxDelayedTaskList = pxOverflowDelayedTaskList;
pxOverflowDelayedTaskList = pxTemp;

tjwc - 17-Mar-09

Real-Time Operating Systems

2.77

#if ( INCLUDE_vTaskDelay == 1 )

TaskDelay API function

void vTaskDelay( portTickType xTicksToDelay )

{
portTickType xTimeToWake;
signed portBASE_TYPE xAlreadyYielded = pdFALSE;

/* A delay time of zero just forces a reschedule. */

if( xTicksToDelay > ( portTickType ) 0 )
{
vTaskSuspendAll();
[ Delay the current task see next slide ]
xAlreadyYielded = xTaskResumeAll();
}

/* Force a reschedule if xTaskResumeAll has not

already done so, we may have put ourselves to sleep.*/

if( !xAlreadyYielded )
{
taskYIELD();
}

#endif

A task that is removed from the event list while the scheduler is
suspended will not get placed in the ready list or removed from the
blocked list until the schedule is resumed. This task cannot be in an
event list as it is the currently executing task.

/* Calculate the time to wake - this may overflow but this is

not a problem. */
xTimeToWake = xTickCount + xTicksToDelay;

/* We must remove ourselves from the ready list before adding

ourselves to the blocked list as the same list item is used for
both lists. */

vListRemove( ( xListItem * ) &( pxCurrentTCB->xGenericListItem ) );

/* The list item will be inserted in wake time order. */

listSET_LIST_ITEM_VALUE( &( pxCurrentTCB->xGenericListItem ), xTimeToWake );

if( xTimeToWake < xTickCount )
{

/* Wake time has overflowed. Place this item in the overflow list. */

vListInsert( ( xList * ) pxOverflowDelayedTaskList,

( xListItem * ) &( pxCurrentTCB->xGenericListItem ) );

else
{

Delaying the current task

/* The wake time has not overflowed, so we use normal list. */

vListInsert( ( xList * ) pxDelayedTaskList,

( xListItem * ) &( pxCurrentTCB->xGenericListItem ) );

TaskResumeAll() API function

NB TaskSuspendAll() increments
uxSchedulerSuspended and does nothing else!

signed portBASE_TYPE xTaskResumeAll( void )

{
It is possible that an ISR caused a task to be removed from an event
register tskTCB *pxTCB;
signed portBASE_TYPE
list while the scheduler was suspended. If this was the case then the
xAlreadyYielded = pdFALSE; removed task will have been added to the xPendingReadyList. Once
{

portENTER_CRITICAL();

--uxSchedulerSuspended;

the scheduler has been resumed it is safe to move all the pending
ready tasks from this list into their appropriate ready list.

if( uxSchedulerSuspended == ( unsigned portBASE_TYPE ) pdFALSE )

{
if( uxCurrentNumberOfTasks > ( unsigned portBASE_TYPE ) 0 )
{
portBASE_TYPE xYieldRequired = pdFALSE;
/* Move any readied tasks from the pending list into the appropriate ready list. */
while( ( pxTCB = ( tskTCB * ) listGET_OWNER_OF_HEAD_ENTRY(
( ( xList * )&xPendingReadyList ) ) ) != NULL )
{
vListRemove( &( pxTCB->xEventListItem ) );
vListRemove( &( pxTCB->xGenericListItem ) );
prvAddTaskToReadyQueue( pxTCB );

/* If we have moved a task that has a priority higher than

the current task then we should yield. */
if( pxTCB->uxPriority >= pxCurrentTCB->uxPriority )
{
xYieldRequired = pdTRUE;
Contd next slide
}

if( uxMissedTicks > ( unsigned portBASE_TYPE ) 0 ) {

while( uxMissedTicks > ( unsigned portBASE_TYPE ) 0 )
{
If any ticks occurred while the scheduler
vTaskIncrementTick(); was suspended then they should be processed
--uxMissedTicks;
now. This ensures the tick count does not
}
slip, and that any delayed tasks are resumed
at the correct time.

/* As we have processed some ticks it is appropriate to yield

to ensure the highest priority task that is ready to run is
the task actually running. */
xYieldRequired = pdTRUE;

if( ( xYieldRequired == pdTRUE ) || ( xMissedYield == pdTRUE ) )

{
xAlreadyYielded = pdTRUE;
xMissedYield = pdFALSE;
taskYIELD();
}

}
portEXIT_CRITICAL();

return xAlreadyYielded;

Calling the scheduler from task API

taskYIELD() is the FreeRTOS macro that invokes the

scheduler
Called from task level
Performs task switch to new task if current task is not highest
priority ready task
Typically called from task code that has just altered task state:
taskYIELD() return means
Either no task-switch
Or the task has suspended and woken up again

taskYIELD can be called from inside or outside a critical

section, on return the critical section will be as before though
if task switch happened interrupts will be enabled while the task
is suspended & therefore criticality broken
Implemented as a software interrupt (simulates real interrupt)
tjwc - 17-Mar-09

Real-Time Operating Systems

2.82

Other techniques: Method 1

MicroC/OS-II uses a different strategy to

implement task delay, which avoids having to
consider task overflow
Each delayed task is put on the delayed task list with
a field that indicates "time to wakeup" = wakeup
time current time
Order of tasks in list is not significant
"time to wakeup" precision can be shorter than system
clock precision, so reducing TCB size (e.g. 2 bytes instead
of 4 bytes)

The clock tick chains through the entire delayed task

list decrementing each "time to wakeup"
If "time to wakeup" = 0 then wake up task
tjwc - 17-Mar-09

Real-Time Operating Systems

2.83

This strategy has the big disadvantage

that the clock-tick code is proportional
to number of delayed tasks
Typically all of the tasks in a system may
be delayed (except the running task) since
blocking on events has an optional
timeout.
This makes clock tick processing high
overhead

tjwc - 17-Mar-09

Real-Time Operating Systems

2.84

Other Techniques: method 2

Method 2: eliminate possibility of overflow

A 64 bit integer for portTickType would mean that with
any possible tick rates overflow will take more than 100
years
Ok to ignore overflow & so simplify the code?
Computing or comparing time delay requires a 64 bit
subtraction
TCB size is larger

tjwc - 17-Mar-09

Real-Time Operating Systems

2.85

Lecture 2.4 - Summary

FreeRTOS divides source into port-independent & port-specific

files
Clock tick ISR implements system clock, task delays & timeouts.
System clock is incremented once per clock tick
Basic function to wake up tasks in delayed task list whose wakeup
time is equal to that of system clock
Future clock ticks can be stacked up for later execution when
scheduling is locked.
System clock overflow is dealt with via an overflow delayed task
list
This is necessitated by possibility of wrap-around in system clock
making time ordering incorrect
Alternative solution is to store time-till-wakeup with each task that is in
delayed task list.
Cleaner, but makes clock tick considerably slower if there are many
delayed tasks

tjwc - 17-Mar-09

Real-Time Operating Systems

2.86

Lecture 2.5 RTOS Objects

The framework we have already examined makes it easy to write

RTOS code that implements synchronisation & communication
operations. We will look at algorithms for implementing two
common constructs which illustrate the principles.
Use FreeRTOS as concrete example

Objects considered:
Semaphores
Message Queues

Implementing new objects is one of the easier RTOS design

problems.
Most of the code event lists of waiting tasks is common to all
objects and can be reused.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.87

Semaphore Implementation

Semaphore is implemented using a variable to indicate the number of

tokens held by the semaphore
Semaphore Take operation
Decrement this value, or if it is zero suspend the taking task

Semaphore Give operation

Increment this value, or if there are waiting tasks (and therefore the token count
= 0) wake up the highest priority such leaving token count unchanged.

Semaphore Create operation

Allocate semaphore control block

Set initial number of tokens

Counting & binary semaphore can have identical implementation only

difference is initial token value

Semaphore timeouts
A Taking task can specify optional timeout to be used if it blocks
Waking from timeout returns from Take operation with timeout return value
tjwc - 17-Mar-09

Real-Time Operating Systems

2.88

Semaphore Event States

Each arrow
corresponds to
some semaphore
code inside
SemaGive() or
SemaTake() which
must execute.
2a is made up of
SemaGive() from
signalling task +
SemaTake() from
unblocked task
2b is made up of
clock interrupt code
+ SemaTake() from
unblocked task

tjwc - 17-Mar-09

Task not
waiting

(1) Task
waits on
semaphore

(3) Task is
scheduled
to run

Real-Time Operating Systems

Task
waiting

(2b)
Timeout

ISR

(2a)
Signal

Task is
ready to
run &
re-starting

2.89

Pseudocode: Semaphore Creation &

Semaphore Control Block
typedef struct {
int count; /*number of tokens*/
taskList eventWaiterList;
} semaSCB;

Semaphore Control Block

semaSCB *SemaCreate( int initialCount);

{
semaSCB *s = [ allocate memory block size of semaSCB ];
s->count=initialCount;
[ initialise empty Task list on s->eventwaiterList ]
return s;
}

tjwc - 17-Mar-09

Real-Time Operating Systems

2.90

Pseudocode: Semaphore Take

Int SemaTake( semaSCB *s, int timeout);
{
int rc;
[ enter critical section ]
if (s->count > 0) {
s->count--;
[ exit critical section ]
return semaTAKE_OK;
}
currentTCB->wakeupCode = semaTIMEOUT; /* set default value */
[ remove current task from READY list ]
1 [ add current task to s->EventWaiterList ]
[ add current task to DelayedTasksList with timeout delay ]
[ exit critical section ]
taskYIELD() /*task switch is certain */
2 return currentTCB->wakeupCode;
}
tjwc - 17-Mar-09

Real-Time Operating Systems

2.91

Pseudocode Semaphore Give

void SemaGive( semaSCB *s, int timeout);
{
tskTCB *tcb;
[ enter critical section ]
tcb = [ extract highest priority task in s->eventWaitersList ]
if ( tcb == NULL] ) {
s->count++;
[ exit critical section ]
} else {
tcb->wakeupCode=semaEVENT_WAKE;
[ remove tcb from DelayedTasksList ]
[ add tcb to READY list ]
2a
[ exit critical section ]
taskYIELD() ;
/*preempt to run the woken task

if necessary*/

tjwc - 17-Mar-09

Real-Time Operating Systems

2.92

Semaphore Implementation Notes

A task waiting on a semaphore must know whether it was woken up

from timeout or (as normal) from a semaphore Give.
Use a return value from the SemaTake() API function
The necessary information cannot be stored in the SCB since more than one
waiting task could be woken up before any of the woken tasks execute.
Therefore must use a dedicated field in the Task Control Block
Providing information about whether return was immediate or after waiting is not
normally necessary, but done here for completeness.

The size of the return code could be shorter than an int to reduce TCB size
on 8-bit systems. For simplicity this is ignored here

The semaphore count could be one or two bytes only to save space
in the SCB.
If there is any possibility of semaphore count overflow this should be
detected by the SemaGive() API function and result in an error code returned
Not implemented, for simplicity, here.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.93

FreeRTOS Semaphores

In line with a minimal footprint policy FreeRTOS

implements binary semaphores only, using the existing
queue mechanism with queue size 0 (i.e. no space is
used for the queue items)
A queue length 1 implements a binary semaphore
Queue items represent tokens held by the semaphore
To initialise queue with token count of 1 it is necessary to call
xQueueSend() once during initialisation.

Could queues be used to implement counting

semaphores?
How would they be initialised?

tjwc - 17-Mar-09

Real-Time Operating Systems

2.94

FreeRTOS Message Queues

A message queue must suspend & wake up tasks in a similar way

to a semaphore.
It must also support a FIFO data structure for the queue itself
We will look at the precise C code used by FreeRTOS to
implement message queues.
The FreeRTOS code depends on code to implement task lists. This is
NOT described here in detail.

FreeRTOS queues allow either sending or receiving tasks to block

The code for basic send & receive functions therefore has separate
cases depending on queue state.
Queue can block SEND if full, and RECEIVE if empty.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.95

Queue Event States

Each arrow
corresponds to some
code inside
QueueSend() and/or
QueueReceive() which
must execute.
2Sa is made up of
QueueReceive() from
signalling task
2Sb is made up of
clock interrupt code
QueueSend() from
unblocked task

2S is followed by 3S,
in which QueueSend()
returns
tjwc - 17-Mar-09

(1S) Task Sends to a

full queue
Task not
waiting

(1R) Task Receives

from empty queue
ISR Receive
ISR Send

Task
waiting

(2Sb,2Rb)
Timeout
(3S, 3R) Task
is scheduled
to run

Real-Time Operating Systems

(2Sa) Receive
(2Ra) Send

Task is
ready to
run &
re-starting

2.96

Simple Pseudocode
xQueueSend(message)
This code works, but has a
{
[ enter critical section ]
very long critical section which
if ( [ queue is full ] ) {
disables interrupts. Alternative:
if (xTicksToWait > 0) {
use separate queue-locks to
[ delete task from ready list ]
protect queue buffer from
1S
[ add task to queue event waiter list ]
interrupts
[ add task to delayed tasks list ]
taskYIELD()
}
}
taskYield() will result in task
if [ queue is full ] {
switch since current task is no
[ exit critical section ]
longer READY
[
return
error
]
3S
} else { /*there is room on queue*/
[ copy message to queue ]
[ update queue pointers ]
2Ra [ wake up the highest priority receiving task ]
}
[ exit critical section ]
[ return OK ]
}
tjwc - 17-Mar-09

Real-Time Operating Systems

2.97

Analysis

This code has a subtle

problem, illustrated here.
QueueReceive() may
terminate early with a
failure when two different
tasks are both reading the
same Queue.
This is because waking up
a task and the task
picking up the message
can be separated in time.
There is an identical
problem with two senders
blocking on a full Queue.
V4.05 FreeRTOS has this
behaviour
tjwc - 17-Mar-09

1. Queue is initially empty

2. TaskB (Prio=1) calls QueueReceive()
and blocks waiting for a message
3. TaskA (Prio=3) wakes up & runs

4. TaskA (Prio=3) sends a message to the

queue, this wakes up TaskB
5. TaskA continues to run & wakes up
TaskC (prio=2)
6. When TaskA blocks, TaskC runs, and
calls QueueReceive(). It gets the
previously posted message in the
queue.
7. When TaskC blocks, TaskB runs &

expects to find a message, but finds

none & QueueReceive() returns with an
error.
Real-Time Operating Systems

2.98

typedef struct QueueDefinition

{
signed portCHAR *pcHead;
signed portCHAR *pcTail;

Message FIFO

Queue Data Structures

/*< Points to the beginning of the queue storage area. */
/*< Points to the byte at the end of the queue storage area.
Once more byte is allocated than necessary to store the
queue items, this is used as a marker. */

signed portCHAR *pcWriteTo; /*< Points to the free next place in the storage area. */
signed portCHAR *pcReadFrom; /*< Points to the last place that a queued item was read from.*/

/*< List of tasks that are

this queue. Stored in
Waiter Lists
xList xTasksWaitingToReceive; /*< List of tasks that are
this queue. Stored in
xList xTasksWaitingToSend;

blocked
priority
blocked
priority

waiting to post onto

order. */
waiting to read from
order. */

unsigned portBASE_TYPE uxMessagesWaiting;/*< The number of items currently in the queue. */

unsigned portBASE_TYPE uxLength;
/*< The length of the queue defined as the

Queue Sizes

number of items it will hold, not the number of bytes.*/

unsigned portBASE_TYPE uxItemSize; /*< The size of each items that the queue will hold. */
signed portBASE_TYPE xRxLock;

Locks

signed portBASE_TYPE xTxLock;

} xQUEUE;

/*< Indicates if one or more items received from the queue

(removed from the queue) while the queue was locked.
Set to queueUNLOCKED when the queue is not locked. */
/*< Indicates if one or more items transmitted to the queue
(added to the queue) while the queue was locked.
Set to queueUNLOCKED when the queue is not locked. */

Queue Locks

QueueSend & QueueReceive can allow ISRs as long as these do

not disturb event lists of waiters
Queue operations from ISR must be allowed to send/receive items
Solution
Separate send/receive of item from consequent waking task
When queue is locked allow items to be added/removed but delay any
task wakeup
When queue is unlocked check if item was added (removed) and if so
wake one task.

What if more than one message posted from ISRs?

Only one task will be woken

OK if only one task waits on queue
OK if both items on queue should be received by same task
Does not allow two tasks to wake and receive one item each
FreeRTOS ignores this case!

tjwc - 17-Mar-09

Real-Time Operating Systems

2.100

Queue data structures

Queue
item
storage

xQUEUE

Task list
Task list

pcHead
pcReadFrom
pcWriteTo
pcTail
uxMessagesWaiting
uxLength
uxItemSize
xTxLock
xTasksWaitingToReceive
xRxLock
xTasksWaitingToSend

item posted from ISR while Q locked

queue locked
queue unlocked
tjwc - 17-Mar-09

3
items
in
queue

>queueUNLOCKED+1
queueUNLOCKED+1
queueUNLOCKED
Real-Time Operating Systems

2.101

#define prvCopyQueueData( pxQueue, pvItemToQueue )

{
memcpy( ( void * ) pxQueue->pcWriteTo, pvItemToQueue,
(unsigned) pxQueue->uxItemSize );
++( pxQueue->uxMessagesWaiting );
pxQueue->pcWriteTo += pxQueue->uxItemSize;
if( pxQueue->pcWriteTo >= pxQueue->pcTail )
{
pxQueue->pcWriteTo = pxQueue->pcHead;
}
Macro that copies an item into the queue. This is done by
}
copying the item byte for byte, not by reference. Updates
the queue state to ensure it's integrity after the copy.

\
\
\
\
\
\
\
\
\
\

#define prvLockQueue( pxQueue )

{
taskENTER_CRITICAL();
++( pxQueue->xRxLock );
++( pxQueue->xTxLock );
taskEXIT_CRITICAL();
}
Macro to mark a queue as locked. Locking a queue
prevents an ISR from accessing the queue event lists.

\
\
\
\
\
\

prvUnlockQueue() - 1
While the queue is locked ISR queue operations
may change data buffers and the queue pointers,
but not the event lists.
This function unlocks the queue, and alters event
queues waking up (one) task if necessary.
static signed portBASE_TYPE prvUnlockQueue(xQueueHandle pxQueue)
{
signed portBASE_TYPE xYieldRequired = pdFALSE;
/* THIS FUNCTION MUST BE CALLED
WITH THE SCHEDULER SUSPENDED. */
[ unlock Tx Queue, waking a receive task if necessary ]
[ unlock RxQueue, waking a send task if necessary ]

return xYieldRequired; /*if any task of higher priority than

current has been woken, return pdTRUE*/

taskENTER_CRITICAL();
{
--( pxQueue->xTxLock ); /*unlock the queue */

/* See if data was added to the queue while it was locked. */

if( pxQueue->xTxLock > queueUNLOCKED ) { /*data was added */
pxQueue->xTxLock = queueUNLOCKED;

/* Data was posted while the queue was locked. Are any tasks
blocked waiting for data to become available? */

if( !listLIST_IS_EMPTY( &( pxQueue->xTasksWaitingToReceive ) ) )

{ /* If so unblock one of the waiting tasks */

/* Tasks that are removed from the event list will get added to
the pending ready list as the scheduler is still suspended. */
if( xTaskRemoveFromEventList(
&( pxQueue->xTasksWaitingToReceive ) ) != pdFALSE )
{

/* The task waiting has a higher priority so record that a

context switch is required. */
xYieldRequired = pdTRUE;

prvUnlockQueue() - 2

}
} /* end if !listLIST_IS_EMPTY()*/ Code to process outstanding
Tx operations

}
taskEXIT_CRITICAL();

RxLock code is similar

signed portBASE_TYPE xQueueSend( xQueueHandle pxQueue,

const void *pvItemToQueue, portTickType xTicksToWait )
{
signed portBASE_TYPE xReturn;
Timeout: 0 no waiting allowed
vTaskSuspendAll();
prvLockQueue( pxQueue );
if( prvIsQueueFull( pxQueue ) ) { /* If the queue is full we may have to block. */
/* The queue is full - do we want to block or just leave without posting? */
if( xTicksToWait > ( portTickType ) 0 )
{
vTaskPlaceOnEventList( &( pxQueue->xTasksWaitingToSend ), xTicksToWait );
taskENTER_CRITICAL();
taskYIELD may exit critical section
{
if new task did not suspend in one
prvUnlockQueue( pxQueue );
Note that CS will be resumed with
if( !xTaskResumeAll() )
this task
1S
{
taskYIELD(); /* this will result in a context switch */
}
3S
vTaskSuspendAll();
prvLockQueue( pxQueue );
XQueueSend() - 1
}
taskEXIT_CRITICAL();
} /* end (xTicksToWait > 0)
} /* end if prvIsQueueFull(pxQueue) */ Send a message from a task to

a Queue

/* When we are here it is possible that we unblocked as space became

available on the queue. It is also possible that an ISR posted to the
queue since we left the critical section, so it may be that again there
is no space. This would only happen if a task and ISR post onto the
same queue. */
taskENTER_CRITICAL();
{
if( pxQueue->uxMessagesWaiting < pxQueue->uxLength )
{
3S

/* There is room in the queue, copy the data into the queue. */
prvCopyQueueData( pxQueue, pvItemToQueue );
xReturn = pdPASS;

/* Update the TxLock count so prvUnlockQueue knows to check for

tasks waiting for data to become available in the queue. */
++( pxQueue->xTxLock );

}
else
{
xReturn = errQUEUE_FULL;
}

}
taskEXIT_CRITICAL();

XQueueSend() - 2
Send a message from a task to
a Queue

/* We no longer require exclusive access to the queue.

prvUnlockQueue
will remove any tasks suspended on a receive if either this function
or an ISR has posted onto the queue. */
if( prvUnlockQueue( pxQueue ) )
{

/* Resume the scheduler - making ready any tasks that were woken
by an event while the scheduler was locked. Resuming the
scheduler may cause a yield, in which case there is no point
yielding again here. */
if( !xTaskResumeAll() )
{
taskYIELD();
}

3S

}
else
{

XQueueSend() - 3

Send a message from a task to

a Queue

/* Resume the scheduler - making ready any tasks that were woken
by an event while the scheduler was locked. */

}
}

xTaskResumeAll();

return xReturn;

FreeRTOS QueueReceive()

QueueReceive() is an exact parallel to QueueSend(), with full

queue & empty queue reversed and message removed instead of
added.
Compare the code with that for QueueSend()
Note that the message copy is done with C library block copy
function memcpy() in this case, rather than a separately defined
macro function.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.108

signed portBASE_TYPE xQueueReceive( xQueueHandle pxQueue,

void *pvBuffer, portTickType xTicksToWait )
{
signed portBASE_TYPE xReturn;
vTaskSuspendAll();
prvLockQueue( pxQueue );
/* If there are no messages in the queue we may have to block. */
if( prvIsQueueEmpty( pxQueue ) ) {
if( xTicksToWait > ( portTickType ) 0 ) {
vTaskPlaceOnEventList( &( pxQueue->xTasksWaitingToReceive ),
xTicksToWait );
taskENTER_CRITICAL();
{
prvUnlockQueue( pxQueue );
if( !xTaskResumeAll() ) {
taskYIELD();
}
XQueueReceive() - 1
vTaskSuspendAll();
prvLockQueue( pxQueue );
Task receive a message from a
}
queue
taskEXIT_CRITICAL();
}
}

taskENTER_CRITICAL();
{
if( pxQueue->uxMessagesWaiting > ( unsigned portBASE_TYPE ) 0 ) {
pxQueue->pcReadFrom += pxQueue->uxItemSize;
if( pxQueue->pcReadFrom >= pxQueue->pcTail )
{
pxQueue->pcReadFrom = pxQueue->pcHead;
}
--( pxQueue->uxMessagesWaiting );
memcpy( ( void * ) pvBuffer, ( void * ) pxQueue->pcReadFrom,
( unsigned ) pxQueue->uxItemSize );

/* Increment the lock count so prvUnlockQueue knows to check for

tasks waiting for space to become available on the queue. */
++( pxQueue->xRxLock );
xReturn = pdPASS;

}
else
{
xReturn = pdFAIL;
}

}
taskEXIT_CRITICAL();

XQueueReceive() - 2

Task receive a message from a

queue

/* We no longer require exclusive access to the queue. */

if( prvUnlockQueue( pxQueue ) )
{
if( !xTaskResumeAll() )
{
taskYIELD();
}
}
else
{
xTaskResumeAll();
}
}

return xReturn;

XQueueReceive() - 3
Task receive a message from a
queue

ISR Queue Send (1)

signed portBASE_TYPE xQueueSendFromISR( xQueueHandle pxQueue,
const void *pvItemToQueue, signed portBASE_TYPE xTaskPreviouslyWoken )
{

/* Similar to xQueueSend, except we don't block if there is no room in the

queue. Also we don't directly wake a task that was blocked on a queue
read, instead we return a flag to say whether a context switch is required
or not (i.e. has a task with a higher priority than us been woken by this
post). */
if( pxQueue->uxMessagesWaiting < pxQueue->uxLength )
{
prvCopyQueueData( pxQueue, pvItemToQueue );

/* code to wake up task, if required, or record future wakeup */

see next slide

}
}

return xTaskPreviouslyWoken;

/* If the queue is locked we do not alter the event list. This will
be done when the queue is unlocked later. */
if( pxQueue->xTxLock == queueUNLOCKED )
{

/* We only want to wake one task per ISR, so check that a task has
not already been woken. */

if ( !xTaskPreviouslyWoken )
{
if ( !listLIST_IS_EMPTY( &( pxQueue->xTasksWaitingToReceive ) ) )
{
if ( xTaskRemoveFromEventList(&( pxQueue->xTasksWaitingToReceive ))
!= pdFALSE )
{

/* The task waiting has a higher priority so record that a

context switch is required. */

return pdTRUE;

}
} else /* the queue is locked */
{

ISR Queue Send (2)

/* Increment the lock count so the task that unlocks the queue
knows that data was posted while it was locked. */

++( pxQueue->xTxLock );

Lecture 2.5 - Summary

FreeRTOS implements a single, very flexible, message queue

object
Semaphores are special case of message queue

Message queues can block both on sending and receiving data,

and implement both FIFO and LIFO queueing.
The mechanism for waking up tasks is complex, and has a bug in
early versions (<4.1) of FreeRTOS which can lead to unexpected
early timeouts. This is fixed in later versions with a recovery loop
which detects the bad timeout and suspends again.
The semantics in FreeRTOS for waking multiple receiving tasks
from interrupts is unusual
It is assumed only one task should be woken even if multiple
messages are posted.

tjwc - 17-Mar-09

Real-Time Operating Systems

2.114

Lecture 2.6 Writing an RTOS

Writing is not necessarily something to be ashamed of, but do it in

private and wash your hands afterwards.
Robert Heinlein

We have now covered all that is necessary for complete

RTOS implementation
Clock tick and ISR-> task context switch
Tasks lists & scheduler

Priority-based preemptive scheduling essential

Co-routines possible?
round-robin time-slicing possible?
EDF etc possible?

Task->task context switch (taskYield)

Task delay
Wait on object (message queue, semaphore)
Memory allocation
RTOS can use different allocation algorithms
Lecture 1.2 gives an example

Critical section implementation

Interrupt lock
Preemption (scheduler) lock
tjwc - 17-Mar-09

Real-Time Operating Systems

2.115

Design Aims Revisited

Portability
Minimise code specific to a given architecture/compiler

Scalability
Make feature-set configurable, so the same system can be
configured for very small, or large, systems

Performance
Low interrupt-level & task-level latency
Interested in maximum limit, not average

Small RAM & ROM footprint

Rich Feature-set?
Ways to deal with priority-inversion
Deadline scheduling
Rich set of comms & synch primitives

tjwc - 17-Mar-09

Real-Time Operating Systems

2.116

Overview: FreeRTOS design

FreeRTOS has very minimal port-specific code

Interrupt enable/disable
Context switch
Task startup stack initialisation

FreeRTOS is highly configurable

Size of system clock is adjustable (32/16/8 bits).
Kernel API functions can be individually omitted

Task suspend
Message Queue write from ISR
TaskDelay()
TaskDelayUntil()

FreeRTOS aim is to be clean and have a very small footprint

Reuse generic tasks lists throughout RTOS
Reuse generic queues as semaphores

Optimised linked list implementation leads to fast & flexible task

lists
Ready list is optimised with array based on priorties
Task lists are doubly linked for efficient task removal

FreeRTOS has fairly small feature-set

tjwc - 17-Mar-09

Real-Time Operating Systems

2.117

Common RTOS Design Decisions

Write RTOS in C
Use C preprocessor to switch
features on/off
Use C macros for efficient
implementation of hardwaredependent primitives

Use global memory space

ignore hardware memory
management
Appropriate for small & mediumsized embedded systems

Use a single periodic timer

interrupt "clock tick" to provide
RTOS timing functions
Aids portability machinedependent code is localised

Use dynamic task creation

Use priority-based preemptive
scheduling
Provide (at least) semaphores,
message queues

Implement RTOS objects, tasks,

semaphores, etc, via control
blocks as C structures:
TCB task control block
SCB semaphore control block

tjwc - 17-Mar-09

Real-Time Operating Systems

2.118

Lecture 2.6 Conclusion

Analysis
Real-time introduces a wide variety of
problems
RMA is best quantitative technique to
ensure correctness- works with
prioritised system
Liveness problems are a big issue in
real-time systems which can only be
addressed through careful attention at
application design stage
Deadlock crucial but straightforward
Starvation easy to mend but more
difficult to detect
Livelock even more difficult to detect
Priority inversion must be fully
understood. A variety of RTOSspecific solutions are available

tjwc - 17-Mar-09

Implementation
RTOS implementation is still relatively
immature, with competing methods for
the various internal functions
Unlike other OS, scalability is
essential, with ability to run on both
very resource-constrained systems
and relatively large systems a merit
To achieve this RTOS must be
configurable with code size dependent
on selected feature-set
RTOS can relatively easily be ported
to new architectures port depends
on details of CPU, C compiler, and
assembler.
It is sometimes possible to use inline
assembly code embedded in C
functions and avoid using a separate
assembler

Real-Time Operating Systems

2.119

Exam

One compulsory question with many small parts (40 marks)

Three optional questions, must complete two (30 marks each)
Exam notes will be published on the first day of the Summer Term and
should be studied before the exam
They will contain background material & C code specific to exam questions
They will contain all relevant reference material on FreeRTOS API

Types of question:
Analysis of given RTS
RMA & extended RMA
liveness analysis

Use of API primitives to implement synchronisation & communication

Pseudocode
C code with correct use of API

RTOS implementation

Compare & contrast different implementations of specific constructs

Explain precisely operation of specific RTOS code in given situation
Write pseudocode for implementation of specific RTOS constructs
Write pseudocode for and/or analyse foreground/background implementations of RTS

Something relating to your coursework

tjwc - 17-Mar-09

Real-Time Operating Systems

2.120