Critiques
Ø 1/2 page critiques of research papers
Ø Due at 10am on the class day (hard deadline)
Ø Email Yehan [Link]@[Link] in plain txt
Ø Back-of-envelop notes - NOT whole essays
Ø Guidelines: [Link]
Ø Critique #1
q D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler, The nesC
Language: A Holistic Approach to Networked Embedded Systems, ACM
Conference on Programming Language Design and Implementation (PLDI),
June 2003.
q Due on 1/30 (Tuesday)
1
IoT Operating Systems
Chenyang Lu
2
TinyOS and nesC
Ø TinyOS: OS for wireless sensor networks.
Ø nesC: programming language for TinyOS.
Chenyang Lu 3
Mica2 Mote
Ø Microcontroller: 7.4 MHz, 8 bit
Ø Memory: 4KB data, 128 KB program
Ø Radio: max 38.4 Kbps
Ø Sensors: Light, temperature, acceleration, acoustic, magnetic…
Ø Power
q <1 week on two AA batteries in active mode
q >1 year battery life on sleep modes!
Ø Contrast to Raspberry Pi:
[Link]
Chenyang Lu 4
Epic Core
3V
I/O (some shared)
RAM 10 KB 8 ADC (12 bit)
2 DAC (12 bit)
Flash 48 KB 1 I2C Unique
2.5 x 2.5 cm 1 JTAG hardware ID
1 1-Wire
TI MSP430 2 SPI
2 UART
CC2420 radio
802.15.4 16 MB
6LoWPAN/IPv6 Clock 4/8 MHz 8 general, 8 Flash memory
interrupt, and 5
special pin
connectors
Typical sleep current 9μA at 3V, radio active ~20mA
5
TelosB
Ø Six major I/O devices
Ø Possible Concurrency
q I2C, SPI, ADC
Ø Energy Management
q Turn peripherals on only when needed
q Turn off otherwise
6
Hardware Constraints
Severe constraints on power, size, and cost à
Ø slow microprocessor
Ø low-bandwidth radio
Ø limited memory
Ø limited hardware parallelism à CPU hit by many interrupts!
Ø manage sleep modes in hardware components
Chenyang Lu 7
Software Challenges
Ø Small memory footprint
Ø Efficiency - power and processing
Ø Concurrency-intensive operations
Ø Diversity in applications & platform à efficient modularity
q Support reconfigurable hardware and software
Chenyang Lu 8
Traditional OS
Ø Multi-threaded
Ø Preemptive scheduling
Ø Threads:
q ready to run;
q executing on the CPU;
q waiting for data. executing
gets
CPU preempted needs
data
gets data
ready waiting
needs data
Chenyang Lu 9
Limitations of Traditional OS
Ø Multi-threaded + preemptive scheduling
q Preempted threads waste memory
q Context switch overhead
Ø I/O
q Blocking I/O: waste memory on blocked threads
q Polling (busy-wait): waste CPU cycles and power
Chenyang Lu 10
Example: Preemptive Priority Scheduling
Ø Each process has a fixed priority (1 highest);
Ø P1: priority 1; P2: priority 2; P3: priority 3.
P3 released
P2 released P1 released
P2 P1 P2 P3
0 10 20 30 40 50 60
time
Chenyang Lu 11
Context Switch
process 1
PC
registers
process 2
CPU
...
memory
Chenyang Lu CSE 467S 12
Existing Embedded OS
Name Code Size Target CPU
pOSEK 2K Microcontrollers
pSOSystem PII->ARM Thumb
VxWorks 286K Pentium -> Strong ARM
QNX Nutrino >100K Pentium II -> NEC
QNX RealTime 100K Pentium II -> SH4
OS-9 Pentium -> SH4
Chorus OS 10K Pentium -> Strong ARM
ARIEL 19K SH2, ARM Thumb
Creem 560 bytes ATMEL 8051
Ø QNX context switch = 2400 cycles on x86
Ø pOSEK context switch > 40 µs
Ø Creem -> no preemption
System architecture directions for network sensors, J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, K. Pister. ASPLOS 2000.
Chenyang Lu 13
TinyOS Solutions
Ø Efficient modularity
q Application= scheduler + graph of components
q Compiled into one executable
q Only needed components are complied/loaded
Ø Concurrency: event-driven architecture
Main (includes Scheduler)
Application (User Components)
Actuating Sensing Communication
Communication
Hardware Abstractions
Modified from D. Culler et al., TinyOS boot camp presentation, Feb 2001
Chenyang Lu 14
Example: Surge
Sur geC
StdControl
BootC Sur geP
StdControl ADC Timer SendMsg Leds
StdControl ADC StdControl Timer StdControl SendMsg Leds
PhotoC Tim erC MultihopC LedsC
Chenyang Lu 15
Typical Application
D. Culler et. Al., TinyOS boot camp presentation, Feb 2001
application sensing application
routing Routing Layer
messaging Messaging Layer
packet Radio Packet
byte Radio Byte (MAC) Temp
photo SW
bit RFM ADC i2c HW
clocks
Chenyang Lu 16
Two-level Scheduling
Ø Events handle interrupts
q Interrupts trigger lowest level events
q Events can signal events, call commands, or post tasks
Ø Tasks perform deferred computations
Ø Interrupts preempt tasks and interrupts
Preempt Tasks
POST FIFO
events
commands
commands
Interrupts
Time
Hardware
Chenyang Lu 17
Multiple Data Flows
Ø Respond quickly: sequence of event/command through the
component graph.
q Immediate execution of function calls
q e.g., get bit out of radio before it gets lost.
Ø Post tasks for deferred computations.
q e.g., encoding.
Ø Events preempt tasks to handle new interrupts.
Chenyang Lu 18
Sending a Message
Timing diagram of event propagation
(step 0-6 takes about 95 microseconds total)
Chenyang Lu 19
Scheduling
Ø Interrupts preempt tasks
q Respond quickly
q Event/command implemented as function calls
Ø Task cannot preempt tasks
q Reduce context switch à efficiency
q Single stack à low memory footprint
q TinyOS 2 supports pluggable task scheduler (default: FIFO).
Ø Scheduler puts processor to sleep when
q no event/command is running
q task queue is empty
Chenyang Lu 20
Space Breakdown…
Code size for ad hoc networking application
3500
Interrupts
3000
Message Dispatch
Initilization
C-Runtime
2500 Scheduler: 144 Bytes code
Light Sensor
Clock Totals: 3430 Bytes code
2000
226 Bytes data
Bytes
Scheduler
1500 Led Control
Messaging Layer
1000 Packet Layer
Radio Interface
500 Routing Application
Radio Byte Encoder
0
D. Culler et. Al., TinyOS boot camp presentation, Feb 2001
Chenyang Lu 21
Power Breakdown…
Active Idle Sleep
CPU 5 mA 2 mA 5 μA
Radio 7 mA (TX) 4.5 mA (RX) 5 μA
EE-Prom 3 mA 0 0
Panasonic
LED’s 4 mA 0 0 CR2354
Photo Diode 200 μA 0 0 560 mAh
Temperature 200 μA 0 0
q LithiumBattery runs for 35 hours at peak load and years at
minimum load!
• That’s three orders of magnitude difference!
q A one byte transmission uses the same energy as approx
11000 cycles of computation.
Chenyang Lu 22
Time Breakdown…
Packet reception
Components work breakdown CPU Utilization Energy (nj/Bit)
AM 0.05% 0.20% 0.33
Packet 1.12% 0.51% 7.58
Radio handler 26.87% 12.16% 182.38
Radio decode thread 5.48% 2.48% 37.2
RFM 66.48% 30.08% 451.17
Radio Reception - - 1350
Idle - 54.75% -
Total 100.00% 100.00% 2028.66
Ø 50 cycle task overhead (6 byte copies)
Ø 10 cycle event overhead (1.25 byte copies)
Chenyang Lu 23
Advantages
Ø Small memory footprint
q Only needed components are complied/loaded
q Single stack for tasks
Ø Power efficiency
q Put CPU to sleep whenever the task queue is empty
q TinyOS 2 (ICEM) provides power management for peripherals.
Ø Efficient modularity
q Event/command interfaces between components
q Event/command implemented as function calls
Ø Concurrency-intensive operations
q Event/command + tasks
Chenyang Lu 24
Critiques
Ø No protection barrier between kernel and applications
Ø No preemptive scheduling à a real-time task may wait for
non-urgent ones
Ø Static linking à cannot change parts of the code dynamically
Ø Virtual memory?
Chenyang Lu 25
nesC
Ø Programming language for TinyOS and applications
Ø Support TinyOS components
Ø Whole-program analysis at compile time
q Improve robustness: detect race conditions
q Optimization: function inlining
Ø Static language
q No function pointer
q No malloc
q Call graph and variable access are known at compile time
Chenyang Lu 26
Application
Ø Interfaces Ø Implementation
q provides interface q module: C behavior
q uses interface q configuration: select & wire
module TimerP {
StdControl Timer provides {
interface StdControl;
TimerP interface Timer;
}
Clock uses interface Clock;
...
}
Chenyang Lu 27
Interface
interface Clock {
command error_t setRate(char interval, char scale);
event error_t fire();
}
interface Send {
command error_t send(message_t *msg, uint16_t length);
event error_t sendDone(message_t *msg, error_t success);
}
interface ADC {
command error_t getData();
event error_t dataReady(uint16_t data);
}
Bidirectional interface supports split-phase operation
Chenyang Lu 28
module SurgeP {
provides interface StdControl;
uses interface ADC;
Module
uses interface Timer;
uses interface Send;
}
implementation {
bool busy;
norace uint16_t sensorReading;
async event result_t [Link]() {
bool localBusy;
atomic {
localBusy = busy;
busy = TRUE;
}
if (!localBusy)
call [Link]();
return SUCCESS;
}
async event result_t [Link](uint16_t data) {
sensorReading = data;
post sendData();
return SUCCESS;
} ...
}
Chenyang Lu 29
Configuration
StdControl Timer
configuration TimerC {
provides {
interface StdControl;
StdControl Timer
interface Timer;
TimerP }
}
Clock
implementation {
components TimerP, HWClock;
StdControl = [Link];
Clock
Timer = [Link];
HWClock
[Link] -> [Link];
TimerC }
Chenyang Lu 30
Example: Surge
Sur geC
StdControl
BootC Sur geP
StdControl ADC Timer SendMsg Leds
StdControl ADC StdControl Timer StdControl SendMsg Leds
PhotoC Tim erC MultihopC LedsC
Chenyang Lu 31
Concurrency
Ø Race condition: concurrent interrupts/tasks update shared variables.
Ø Asynchronous code (AC): reachable from at least one interrupt.
Ø Synchronous code (SC): reachable from tasks only.
Ø Any update of a shared variable from AC is a potential race condition!
Chenyang Lu 32
A Race Condition
module SurgeP { ... }
implementation {
bool busy;
norace uint16_t sensorReading;
async event result_t [Link]() {
if (!busy) {
busy = TRUE;
call [Link]();
}
return SUCCESS;
}
task void sendData() { // send sensorReading
[Link] = sensorReading;
call [Link](&adcPacket, sizeof [Link]);
return SUCCESS;
}
async event result_t [Link](uint16_t data) {
sensorReading = data;
post sendData();
return SUCCESS;
}
Chenyang Lu 33
Atomic Sections
atomic {
<Statement list>
}
Ø Disable interrupt when atomic code is being executed
Ø But cannot disable interrupt for long!
q No loop
q No command/event
q Function calls OK, but callee must meet restrictions too
Chenyang Lu 34
Prevent Race
module SurgeP { ... }
implementation {
bool busy;
norace uint16_t sensorReading;
async event result_t [Link]() {
bool localBusy;
disable atomic {
interrupt
localBusy = busy;
test-and-set
busy = TRUE;
}
enable
interrupt if (!localBusy)
call [Link]();
return SUCCESS;
}
Chenyang Lu 35
nesC Compiler
Ø Race-free invariant: any update of a shared variable
q isfrom SC only, or
q occurs within an atomic section.
Ø Compiler returns error if the invariant is violated.
Ø Fix
q Make access to shared variables atomic.
q Move access to shared variables to tasks.
Chenyang Lu 36
Results
Ø Tested on full TinyOS code, plus applications
q 186 modules (121 modules, 65 configurations)
q 20-69 modules/app, 35 average
q 17 tasks, 75 events on average (per application) - lots of concurrency!
Ø Found 156 races: 103 real
q About 6 per 1000 lines of code!
Ø Fixed races:
q Add atomic sections
q Post tasks (move code to task context)
Chenyang Lu 37
Optimization: Inlining
App Code size Code Data CPU
inlined noninlined reduction size reduction
Surge 14794 16984 12% 1188 15%
Maté 25040 27458 9% 1710 34%
TinyDB 64910 71724 10% 2894 30%
• Inlining improves performance and reduces code size.
• Why?
Chenyang Lu 38
Overhead for Function Calls
Ø Caller: call a function
q Push return address to stack
q Push parameters to stack
q Jump to function
Ø Callee: receive a call
q Pop parameters from stack
Ø Callee: return
q Pop return address from stack
q Push return value to stack
q Jump back to caller
Many overhead instructions
Ø Caller: return for function calls!
q Pop return value
Chenyang Lu 39
Principles Revisited
Ø Support TinyOS components
q Interface, modules, configuration
Ø Whole-program analysis and optimization
q Improve robustness: detect race conditions
q Optimization: function inlining
q More: memory footprint.
Ø Static language
q No malloc, no function pointers
Chenyang Lu 40
Critiques
Ø No dynamic memory allocation
q Bound memory footprint
q Allow offline footprint analysis
q How to size buffer when data size varies dynamically?
Ø Restriction: no “long-running” code in
q command/event handlers
q atomic sections
Chenyang Lu 41
Commercial IoT OS
Ø Contiki: open-source, multi-threaded OS, plain C.
Ø Amazon FreeRTOS: open-source FreeRTOS kernel + libraries to securely
connect devices to AWS cloud services.
Ø Arm Mbed: open-source OS based on an Arm Cortex-M microcontroller.
Ø Android Things: SDK similar to traditional Android mobile development
and involves writing apps using the Android framework and tools.
Ø Windows 10 IoT Core: a version of Windows 10 that is optimized for
smaller devices and that runs on both ARM and x86/x64 devices.
Chenyang Lu 42
Reading
Ø D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler, The nesC
Language: A Holistic Approach to Networked Embedded Systems.
Ø D. Culler, TinyOS: Operating System Design for Wireless Sensor Networks,
Sensors, May 2006.
Ø J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister, System Architecture
Directions for Network Sensors.
Ø P. Levis and D. Gay, TinyOS Programming, 2009.
q Purchase the book online
q Download the first half of the published version for free.
Ø [Link]
Chenyang Lu 43