Basic of Contiki:
Process and Protothread,
KAE WON CHOI
Outline
Process
Events
Process Scheduler
Context Switching
Protothread
Process
All programs running in Contiki is called Process
Process structure
Process Control Block
Process Thread
Process is switched to another process
Preemptive
Cooperative
Process inside process => subprocess
Process Structure
Process Control Block in Memory
process_list
Process 1
Process 2
Process 3
next
next
next
thread
thread
thread
Function
pointer
Process
Thread
Function
pointer
Process
Thread
Function
pointer
Process
Thread
Process Control Block
core/sys/process.c
Refer to next PCB in linked list of
active processes
Textual name of processes
Thread field, function pointer, points
to the processes thread of the
processes
State of protothread
Process state
Poll is needed
(flag)
Process Thread
Process thread contains the code of processes.
Process thread is single protothread that is invoked from the
processes scheduler.
Example:
Process Programming
PROCESS macro
PROCESS_THREAD macro
PROCESS_BEGIN macro
PROCESS_END macro
Macros for Process
PROCESS macro
PROCESS_THREAD
macro
PT_THREAD: char
PROCESS_BEGIN macro
PROCESS_END macro
core/sys/process.c
process_start
core/sys/process.c
Put the process on the process list
Run the process
exit_process
Inform all processes
that this process will
exit
core/sys/process.c
Post the exit event to
the process exited
Remove the
process from the
process list
call_process
core/sys/process.c
If the process is running.
Run the process thread
If the process is ended or exited,
execute exit_process
Preemptive and Cooperative
Execution
Cooperative
Run sequentially
Example: piece of code
execute regularly by
Contiki system
Illustration [1]
Preemptive
Can run anytime
Interrupt cooperative code
Example: interrupt and real
time timer
[1] https://github.com/contiki-os/contiki/wiki/Processes
Event
Process runs when it receives an event
Two types of events:
(A)
Synchronous Event (A)
a)
Delivered directly when they are posted
b)
Equivalent to a function call
c)
Process that posted the event is blocked
until the receiving process has finished
Asynchronous Event (B)
a)
Delivered to the receiving process some time
after they have been posted
https://github.com/contiki-os/contiki/wiki/Processes#The_Process_Scheduler
(B)
Event Structure & Queue
core/sys/process.c
Type of event
(e.g., PROCESS_EVENT_INIT,
PROCESS_EVENT_MSG)
Data handed over to the
receiving process (void *)
Receiving process
Event queue
process_post_synch
core/sys/process.c
The process is
called
process_post
core/sys/process.c
Put the event into the event
queue
Process Scheduler
Purpose
How?
Invokes processes by calling function that implements process thread
When?
to invoke processes when it is their time to run
In response to an event being posted to a process
Argument
Event identifier
Data (opaque pointer to data)
https://github.com/contiki-os/contiki/wiki/Processes#The_Process_Scheduler
do_event (1)
core/sys/process.c
Take out an event out of the event queue
Move the pointer in
the event queue
do_event (2)
core/sys/process.c
If the event is a broadcast event, it is
delivered to all processes
If the event is not a broadcast
event, it is delivered only to a
receiver
Polling
A poll request is a special type of event.
A process is polled by calling the function process_poll().
Calling this function on a process causes the process to be
scheduled as quickly as possible.
The process is passed a special event that informs the process
that it has been polled.
Polling is the way to make a process run from an interrupt. The
process_poll() function is the only function in the process module
that is safe to call from preemptive mode.
process_poll
core/sys/process.c
Set needspoll
do_poll
core/sys/process.c
Call the process if needs
poll is set
process_run
core/sys/process.c
This function is executed
indefinitely
Call do_poll if there is any
polled process
Call do_event
Context Switching (1)
Context [1]:
the contents of a CPUs registers and program counter at any point in
time
Context switching [2]
Saved all register value may using by process (included Program
Counter and Process Control Block)
Stored first PCB in a stack
Load another PCB (second process) from queues
After second process completed
Load Program Counter, continue first process
[1] http://clinuxpro.com/context-switch
[2] http://en.wikipedia.org/wiki/Context_switch
Context Switching (2)
Illustration Context Switch in General[1]
[1] http://clinuxpro.com/context-switch
Context Switching in FreeRTOS (1)
FreeRTOS context switch
Memory View (1)
[1]
[2]
[3]
[4]
http://www.freertos.org/implementation/a00020.html
http://www.freertos.org/implementation/a00021.html
http://www.freertos.org/implementation/a00022.html
http://www.freertos.org/implementation/a00024.html
Context Switching in FreeRTOS (2)
FreeRTOS context switch
Memory View (2)
5
6
[5] http://www.freertos.org/implementation/a00025.html
[6] http://www.freertos.org/implementation/a00026.html
Problem of thread in embedded
systems
Constraint in network embedded
systems
2k RAM, 60k ROM / 10k RAM, 48
More memory, higher per unit cost
Problem of thread
requires a large memory space for
keeping stacks for each thread.
Programming models for sensor
networks
Earlier : TinyOS (event driven)
Currently: ContikiOS (protothreads)
Event-Driven Model
Event-driven model
Implemented in TinyOS
Using event driven models: TinyOS
can handle high-level concurrency
in a very small amount of space [1]
Shortcomings of event-driven
model
Useful for reactive processing and
interfacing with HW, complicates
sequencing high-level operations
Blocking sequence must be written
in a state-machine style [2]
Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for networked sensors. [ASPLOS 2000]
Levis, S. Madden, D. Gay, J. Polastre, R. Szewczyk, A. Woo, E. Brewer, and D. Culler. The Emergence of Networking Abstractions and Techniques in TinyOS. [NSDI 2004]
Protothread
Protothread
Implemented in ContikiOS
Introduce Protothreads [1]: new programming abstraction
A design between events and threads
Very simple, yet powerful idea
Programming primitive: conditional blocking wait
PT_WAIT_UNTIL(condition)
Sequential flow of control
Protothreads run on a single stack, like the event-driven model
Programming language helps us: if and while
Memory requirements (almost) same as for event-driven
Can be seen as combination of events and thread
From thread: inherited the blocking wait semantics (Compare to traditional thread,
protothreads are very lightweight)
From events: inherited the stacklessness and the low memory overhead
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb
Ali
Protothread Example
Stack in Protothread
Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Advantages of Protothreads
We can replace explicit state machines with protothreads
Use if and while statements instead of state machines
16%-49% reduction of lines of code for rewritten programs
Most explicit state machines replaced
Run-time overhead is small
Radio Sleep Cycle
Radio Sleep Cycle [1]
Hypothetical Sensor Network Protocol
State Machine
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Event-Based Implementation of
RSC
State machine-based implementation
Messy
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Protothread Implementation of
RSC
Code shorter than the event-driven
version
Code uses structured programming
(if and while statements)
Mechanism evident from the code
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Primitive State Machine
Primitive state machines and each implementation in pseudocode using
protothread
sequence
selection
iteration
Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
State machine of Radio Sleep
Cycle
Example radio sleep cycle state machine and related primitive state machine pattern
identified
Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Protothread Implementation (1)
Local Continuations
Low
level mechanism that underpins protothreads
When
a protothread(pt) blocks, the state of pt is stored in local
continuation
Similar
to ordinary continuation but does not capture the program
stack
Only
captures the current state execution inside a single function
(not include the history)
Operations
SET
: state of execution is stored in the local continuation
RESUME
: restore current state later time
Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb
Ali
Protothread Implementation (2)
Local Continuations: C preprocessor implementation main operations
Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Protothread Implementation (3)
Local Continuations: Implemented with the GCC labels as values C extension
Only works with GCC
Local Continuations: Implemented with the C switch statement
GCC and ANSI C protothread memory overhead = 2 bytes
Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Protothread Implementation (4)
int a_protothread(struct pt *pt) {
PT_BEGIN(pt);
int a_protothread(struct pt *pt)
{
switch(pt->lc) { case 0:
PT_WAIT_UNTIL(pt, condition1);
pt->lc = 5; case 5:
if(!condition1) return 0;
if(something) {
if(something) {
PT_WAIT_UNTIL(pt, condition2);
pt->lc = 10; case 10:
if(!condition2) return 0;
}
PT_END(pt);
}
Line numbers}
} return 1;
Protothread Implementation (5)
process_list
Process 1
Process 2
Process 3
next
next
next
pt
pt
pt
thread
thread
thread
Function
pointer
Process
Thread
Function
pointer
Process
Thread
Function
pointer
Process
Thread
Protothread Implementation (6)
PROCESS_THREAD
macro
PROCESS_BEGIN macro
PROCESS_END macro
core/sys/process.c
Protothread Implementation (7)
core/sys/process.c
Yielding in Protothreads
The importance of unconditional blocking wait, PT_YIELD()
PT_YIELD() performs an single unconditional blocking wait that
temporarily blocks the protothread until the next time the protothread is
invoked
Next invocation the protothread continues executing the code following
PT_YIELD() statement (perform similar to stackless coroutines)
core/sys/pt.h
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Hierarchical Protothread (1)
Simple program readily expressed with a single protothread
More complex operations may need to be decomposed in
hierarchical fashion
PT_SPAWN() initializes a child protothread and blocks the current
protothread until the child has either ended with PT_END or exit
with PT_EXIT
Child is scheduled by the parent protothread
Each time the parent protothread is invoked by the underlying
system, the child protothread is invoked through the PT_SPAWN()
statement
Memory state of child protothread is allocated in a local variable
of the parent protothread
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb
Ali
Hierarchical Protothread (2)
Pseudocode for
hierarchical Protothread
example
[1] Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems. Adam Dunkels , Oliver Schmidt, Thiemo Voigt , Muneeb Ali
Hierarchical Protothread (3)
Implementation of PT_SPAWN
pt struct of a
child protothread
processthread
(function) of a child
protothread
core/sys/pt.h
