Last Time: Debugging

Last Time
Debugging
It s a science use experiments to refine hypotheses about

bugs
It s an art creating effective hypotheses and experiments
and trying them in the right order requires great intuition
Today
u
Advanced threads
Thread example
Implementation review
Design issues
Performance metrics
Thread variations
Example code from Ethernut RTOS
What s an RTOS?
u
Real-Time Operating System
Provides:
Threads
Real-time scheduler
Synchronization primitives
Boot code
Device drivers
Might provide:
Implication is that it can be used to build real-time systems
Memory protection
Virtual memory
Is WinCE an RTOS? Embedded Linux?
Thread Example
u
We want code to do this:

1.
2.
3.
4.
5.
Turn on the wireless network at time t0

Wait until time is t0 + tawake
If communication has not completed, wait until it has
completed or else time is t0 + tawake + twait_max
Turn off radio
Go back to step 1
Threaded vs. Non-Threaded

enum { ON, WAITING, OFF } state;
void radio_wake_thread () {
while (1) {
radio_on();
timer_set (&timer, T_AWAKE);
wait_for_timer (&timer);
timer_set (&timer, T_SLEEP);
if (!communication_complete()) {
timer_set (&wait_timer, T_WAIT_MAX);
wait_cond (communication_complete() ||
timer_expired (&wait_timer));
}
radio_off();
wait_for_timer (&timer);
}
}
void radio_wake_event_handler () {
switch (state) {
case ON:
if (expired(&timer)) {
set_timer (&timer, T_SLEEP);
if (!communication_complete) {
state = WAITING;
set_timer (&wait_timer,
T_MAX_WAIT);
} else {
turn_off_radio();
state = OFF;
}}
break;
case WAITING:
if (communication_complete() ||
timer_expired (&wait_timer)) {
state = OFF;
radio_off();
}
break;
...
Blocking
u
Blocking
How does blocking work?

1.
2.
3.
4.
5.
Ability for a thread to sleep awaiting some event

Like what?
Fundamental service provided by an RTOS
Thread calls a function provided by the RTOS

RTOS decides to block the thread
RTOS saves the thread s context
RTOS makes a scheduling decision
RTOS loads the context of a different thread and runs it
When does a blocked thread wake up?
More Blocking
u
When does a blocked thread wake up?
Why is blocking good?
When some predetermined condition becomes true

Disk block available, network communication needed, timer
expired, etc.
Often interrupt handlers unblock threads
Preserves the contents of the stack and registers

Upon waking up, thread can just continue to execute
Can you get by without blocking?
Yes but code tends to become very cluttered with state

machines
Preemption
u
When does the RTOS make scheduling decisions?
Advantage of preemption: Threads can respond

more rapidly to events
Non-preemptive RTOS: Only when a thread blocks or exits

Preemptive RTOS: every time a thread wakes up or changes
priority
No need to wait for whatever thread is running to reach a

blocking point
Even preemptive threads sometimes have to wait
For example when interrupts are disabled, preemption is

disabled too
More Preemption
u
Preemption and blocking are orthogonal
No blocking, no preemption main loop style

Blocking, no preemption non-preemptive RTOS
Also MacOS < 10
No blocking, preemption interrupt-driven system
Blocking, preemption preemptive RTOS
Thread Implementation
u
TCB thread control block
One per thread

A struct that stores:
Saved registers including PC and SP
Current thread state
All-threads link field
Ready-list / block-list link field
Stack
Dedicated block of RAM per thread
Thread States
Thread invariants
At most one running thread

If there s an idle thread then exactly one running thread
Every thread is on the all thread list
State-based:
Running thread Not on any list
Blocked thread On one blocked list
Active thread On one ready list
Ethernut TCB
struct _NUTTHREADINFO {
NUTTHREADINFO *volatile td_next;
/* Linked list of all threads. */
NUTTHREADINFO *td_qnxt;
/* Linked list of all queued thread. */
u_char td_name[9];
/* Name of this thread. */
u_char td_state;
/* Operating state. One of TDS_ */
uptr_t td_sp;
/* Stack pointer. */
u_char td_priority;
/* Priority level. 0 is highest priority. */
u_char *td_memory;
/* Pointer to heap memory used for stack. */
HANDLE td_timer;
/* Event timer. */
HANDLE td_queue;
/* Root entry of the waiting queue. */
};
#define TDS_TERM
#define TDS_RUNNING
#define TDS_READY
#define TDS_SLEEP
0
1
2
3
/* Thread has exited. */

/* Thread is running. */
/* Thread is ready to run. */
/* Thread is sleeping. */
Scheduler
u
Makes a decision when:
Thread blocks
Thread wakes up (or is newly created)
Time slice expires
Thread priority changes
How does the scheduler make these decisions?
Typical RTOS: Priorities

Typical GPOS: Complicated algorithm
There are many other possibilities
u_char NutThreadSetPriority(u_char level) {

u_char last = runningThread->td_priority;
/* Remove the thread from the run queue and re-insert it with a new
* priority, if this new priority level is below 255. A priotity of
* 255 will kill the thread. */
NutThreadRemoveQueue(runningThread, &runQueue);
runningThread->td_priority = level;
if (level < 255)
NutThreadAddPriQueue(runningThread, (NUTTHREADINFO **) & runQueue);
else
NutThreadKill();
/* Are we still on top of the queue? If yes, then change our status
* back to running, otherwise do a context switch. */
if (runningThread == runQueue) {
runningThread->td_state = TDS_RUNNING;
} else {
runningThread->td_state = TDS_READY;
NutEnterCritical();
NutThreadSwitch();
NutExitCritical();
}
return last;
}
Dispatcher
Low-level part of the RTOS
u Basic functionality:
u
Save state of currently running thread

Important not to destroy register values in the process!
Restore state of newly running thread
What if there s no new thread to run?
Usually there s an idle thread that is always ready to run

In modern systems the idle thread probably just puts the
processor to sleep
Ethernut ARM Context

typedef struct {
u_long csf_cpsr;
u_long csf_r4;
u_long csf_r5;
u_long csf_r6;
u_long csf_r7;
u_long csf_r8;
u_long csf_r9;
u_long csf_r10;
u_long csf_r11;
u_long csf_lr;
} SWITCHFRAME;
/* AKA fp */
void NutThreadSwitch(void) attribute ((naked))

{
/* Save CPU context. */
asm volatile (
/* */
"stmfd sp!, {r4-r11, lr}" /* Save registers. */
"mrs r4, cpsr" /* Save status. */
"stmfd sp!, {r4}" /* */
"str sp, %0" /* Save stack pointer. */
::"m" (runningThread->td_sp) );
/* Select thread on top of the run queue. */
runningThread = runQueue;
runningThread->td_state = TDS_RUNNING;
/* Restore context. */
__asm__ __volatile__(
/* */
"@ Load context"
/* */
"ldr sp, %0"
/* Restore stack pointer. */
"ldmfd sp!, {r4}" /* Get saved status... */
"bic r4, r4, #0xC0"
/* ...enable interrupts */
"msr spsr, r4"
/* ...and save in spsr. */
"ldmfd sp!, {r4-r11, lr}" /* Restore registers. */
"movs pc, lr" /* Restore status and return. */
::"m"(runningThread->td_sp) );
}
Thread Correctness
u
Threaded software can be hard to understand
Like interrupts, threads add interleavings
To stop the scheduler from interleaving two threads:

use proper locking
Any time two threads share a data structure, access to the

data structure needs to be protected by a lock
Thread Interaction Primitives

u
Locks (a.k.a. mutexes)
FIFO queue (a.k.a. mailbox)
Allow one thread at a time into critical section

Block other threads until exit
Threads read from and write to queue
Read from empty queue blocks
Write to empty queue blocks
Message passing
Sending thread blocks until receiving thread has the

message
Similar to mailbox with queue size = 0
Mixing Threads and Interrupts

u
Problem:
Solution 1:
Thread locks do not protect against interrupts

Mutex disables interrupts as part of taking a lock
What happens when a thread blocks inside a mutex?
Solution 2:
Up to the user to disable interrupts in addition to taking a

mutex
Thread Design Issues 1

u
Static threads:
Dynamic threads:
All threads created at compile time

System supports a create new thread and exit thread
calls
Tradeoffs dynamic threads are:
More flexible and user-friendly

Not possible to implement without a heap
A tiny bit less efficient
Much harder to verify / validate

u
Can threads be asynchronously killed?
Alternative: Threads must exit on their own
Tradeoffs asynchronous termination:
Is sometimes very convenient

Raises a difficult question What if killed thread is in a
critical section?
Kill it anyway Data structure corruption
Wait for it to exit Defeats the purpose of immediate
termination
Why do Windows and Linux processes not have this
problem?

Are multiple threads at the same priority permitted?
u Tradeoffs multiple same-priority threads:
u
Can be convenient
Makes data structures a bit more complex and less efficient
Requires a secondary scheduling policy
Round-robin
FIFO
Thread Design Issue 4

u
How to determine thread stack sizes?
Use same methods as for non-threaded systems

Need to know how interrupts and stacks interact
Possibilities
1.
2.
Interrupts use the current thread stack

Interrupts use a special system stack
Thread Performance Metrics

u
Thread dispatch latency
Average care and worst case
System call latency
Average case and worst case
Context switch overhead

u RAM overhead
u
More or less reduces to heap manager overhead
Thread Variation 1
Protothreads are stackless
u Can block, but
u
Blocking is cooperative
All stack variables are lost across a blocking point
Blocking can only occur in the protothread s root function
Tradeoffs protothreads are another design point

between threads and events
Thread Variation 2
u
Preemption thresholds
Every thread has two priorities

P1 regular priority, used to decide when the thread
runs
P2 preemption threshold, used to decide whether
another thread can preempt currently running thread
If P1 == P2 for all threads, degenerates to preemptive
multithreading
If P2 == max priority, degenerates to non-preemptive
scheduling
Key benefits:
Threads that are mutually nonpreemptive can share a stack

Reduces number of context switches
Thread Pros
u
Blocking can lead to clearer software
Preemptive scheduling can lead to rapid response

times
No need to manually save state

Reduces number of ad-hoc state machines
Only in carefully designed systems
Threads compose multiple activities naturally
As opposed to cyclic executives
Thread Cons
u
Correctness
Empirically, people cannot create correct multithreaded

software
Race conditions
Deadlocks
Tough to debug
Performance
Stacks require prohibitive RAM on the smallest systems

Context switch overhead can hurt might end up putting
time critical code into interrupts
Thread Rules
Always write code that is free of data races
u A data race is any variable that is
u
Written by 1 or more threads

Shared between 2 or more threads
Not consistently protected by a lock
For every variable in your code you should be able

to say why there is not a data race on it
Thread Rules
u
You must be clear about
Your locking strategy

Your call graph
Where pointers might be pointing
Would a program be free of data races if you

disabled interrupts before accessing each shared
variable, and enabled afterwards?
Would it be correct?
How long do you hold a lock in general?
Thread Rules
Protect data any time its invariants are broken
u This means you have to know what the invariants
are!
u Examples?
u
Thread Rules
u
Always either:
Acquire only one lock at a time

Usually not practical
Assign a total ordering to locks and acquire them in that
order
Requires coordination across developers
Summary
u
Threads have clear advantages for large systems
Blocking reduces the need to build state machines

Threads simplify composing a system from parts
Threads have clear disadvantages
RAM overhead, for small systems

Correctness issues

Last Time: Debugging

Uploaded by

Copyright:

Available Formats

Last Time: Debugging

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Last Time: Debugging

Uploaded by

Copyright:

Available Formats

Last Time

It s a science use experiments to refine hypotheses about

Example code from Ethernut RTOS

Real-Time Operating System

Implication is that it can be used to build real-time systems

Is WinCE an RTOS? Embedded Linux?

We want code to do this:

Turn on the wireless network at time t0

Threaded vs. Non-Threaded

How does blocking work?

Ability for a thread to sleep awaiting some event

Thread calls a function provided by the RTOS

When does a blocked thread wake up?

When does a blocked thread wake up?

Why is blocking good?

When some predetermined condition becomes true

Preserves the contents of the stack and registers

Can you get by without blocking?

Yes but code tends to become very cluttered with state

When does the RTOS make scheduling decisions?

Advantage of preemption: Threads can respond

Non-preemptive RTOS: Only when a thread blocks or exits

No need to wait for whatever thread is running to reach a

Even preemptive threads sometimes have to wait

For example when interrupts are disabled, preemption is

Preemption and blocking are orthogonal

No blocking, no preemption main loop style

TCB thread control block

One per thread

Dedicated block of RAM per thread

At most one running thread

/* Thread has exited. */

Makes a decision when:

How does the scheduler make these decisions?

Typical RTOS: Priorities

u_char NutThreadSetPriority(u_char level) {

Save state of currently running thread

What if there s no new thread to run?

Usually there s an idle thread that is always ready to run

Ethernut ARM Context

void NutThreadSwitch(void) attribute ((naked))

Threaded software can be hard to understand

Like interrupts, threads add interleavings

To stop the scheduler from interleaving two threads:

Any time two threads share a data structure, access to the

Thread Interaction Primitives

Locks (a.k.a. mutexes)

FIFO queue (a.k.a. mailbox)

Allow one thread at a time into critical section

Sending thread blocks until receiving thread has the

Mixing Threads and Interrupts

Thread locks do not protect against interrupts

Up to the user to disable interrupts in addition to taking a

Thread Design Issues 1

All threads created at compile time

Tradeoffs dynamic threads are:

More flexible and user-friendly

Thread Design Issues 2