Basic Of Contiki Process 2y1z3i
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3b7i
Overview 3e4r5l
& View Basic Of Contiki Process as PDF for free.
More details w3441
- Words: 1,756
- Pages: 50
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 ed 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 U’s s and program counter at any point in time”
Context switching [2]
Saved all 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)
1
2
3
FreeRTOS context switch Memory View (1)
4
[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
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 ed 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 U’s s and program counter at any point in time”
Context switching [2]
Saved all 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)
1
2
3
FreeRTOS context switch Memory View (1)
4
[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
Related Documents 3m3m1z
Basic Of Contiki Process 2y1z3i
December 2019 33
Basics Of Contiki-os.pdf j1mo
July 2022 0
Basic Concepts Of Process Control 3t251u
November 2019 52
Basic Principles Of Counseling Process 4r1jk
November 2022 0
The Basic Of Process Mapping 1h6y73
May 2020 3