1 CONCURRENCY Overview n Concurrency n How do we make things happen at the right times? MCU Hardware & Software for Concurrency n CPU executes instructions from one or more threads of execution
n Specialized hardware peripherals add dedicated concurrent processing n DMA - transferring data between memory and peripherals n Watchdog timer n Analog interfacing n Timers n Communications with other devices n Detecting external signal events n Peripherals use interrupts to notify CPU of events Concurrent Hardware & Software Operation Software Hardware Software Hardware Software
Time
n Embedded systems rely on both MCU hardware peripherals
and software to get everything done on time CPU Scheduling n MCU’s Interrupt system provides a basic scheduling approach for CPU n “Run this subroutine every time this hardware event occurs” n Is adequate for simple systems
n More complex systems need to support multiple concurrent
independent threads of execution n Use task scheduler to share CPU n Different approaches to task scheduling
n How do we make the processor responsive? (How do we
make it do the right things at the right times?) n If we have more software threads than hardware threads, we need to share the processor. Definitions TRelease Other processing Ttask Scheduler Task or ISR Code Latency Response Time Time
n TRelease(i) = Time at which task (or interrupt) i requests service/is
released/is ready to run n TLatency (i) = Delay between release and start of service for task i n TResponse(i) = Delay between request for service and completion of service for task i n TTask(i) = Time needed to perform computations for task i n TISR(i) = Time needed to perform interrupt service routine i Scheduling Approaches n Rely on MCU’s hardware interrupt system to run right code n Event-triggered scheduling with interrupts n Works well for many simple systems
n Use software to schedule CPU’s time
n Static cyclic executive n Dynamic priority n Without task-level preemption n With task-level preemption Event-Triggered Scheduling using Interrupts n Basic architecture, useful for simple low-power devices n Very little code or time overhead n Leverages built-in task dispatching of interrupt system n Can trigger ISRs with input changes, timer expiration, UART data reception, analog input level crossing comparator threshold n Function types n Main function configures system and then goes to sleep n If interrupted, it goes right back to sleep n Only interrupts are used for normal program operation n Example: bike computer n Int1: wheel rotation n Int2: mode key n Int3: clock n Output: Liquid Crystal Display Bike Computer Functions ISR 1: ISR 2: ISR 3: Reset Wheel rotation Mode Key Time of Day Timer Configure timer rotations++; mode++; cur_time ++; inputs and if (rotations> mode = mode % lcd_refresh--; outputs R_PER_MILE/10) { NUM_MODES; if (lcd_refresh==0) { tenth_miles++; return from interrupt; convert tenth_miles cur_time = 0; rotations = 0; and display rotations = 0; } convert speed tenth_miles = 0; speed = and display circumference/ if (mode == 0) while (1) { (cur_time – prev_time); convert cur_time sleep; compute avg_speed; and display } prev_time = cur_time; else return from interrupt convert avg_speed and display lcd_refresh = LCD_REF_PERIOD } A More Complex Application
n GPS-based Pothole Alarm and Moving Map
n Sounds alarm when approaching a pothole n Display’s vehicle position on LCD n Also logs driver’s position information n Hardware: GPS, user switches, speaker, LCD, flash memory Application Software Tasks
n Dec: Decode GPS sentence to find current vehicle position.
n Check: Check to see if approaching any pothole locations. Takes longer as the number of potholes in database increases. n Rec: Record position to flash memory. Takes a long time if erasing a block. n Sw: Read user input switches. Run 10 times per second n LCD: Update LCD with map. Run 4 times per second
Dec Check Rec Sw LCD Time How do we schedule these tasks? n Task scheduling: Deciding which Dec task should be run now Check n Two fundamental questions n Do we run tasks in the same Rec order every time? Sw n Yes: Static schedule (cyclic executive, round-robin) LCD n No: Dynamic, prioritized schedule n Can one task preempt another, or must it wait for completion? n Yes: Preemptive n No: Non-preemptive (cooperative, run-to-completion) Static Schedule (Cyclic Executive) Dec Check Rec S LCD Dec w
n Pros n Very simple n Cons while (1){ n Always run the same schedule, Dec(); regardless of changing conditions and Check(); relative importance of tasks. Rec(); n All tasks run at same rate. Changing Sw(); rates requires adding extra calls to the function. LCD(); n Maximum delay is sum of all task run } times. Polling/execution rate is 1/ maximum delay. Static Schedule Example GPS Data Checking Arrives complete Response Time
Rec S LCD Dec Check
w
n What if we receive GPS position right after Rec starts
running? n Delays n Have to wait for Rec, Sw, LCD before we start decoding position with Dec. n Have to wait for Rec, Sw, LCD, Dec, Check before we know if we are approaching a pothole! Dynamic Scheduling n Allow schedule to be computed on-the-fly n Based on importance or something else n Simplifies creating multi-rate systems
n Schedule based on importance
n Prioritization means that less important tasks don’t delay more important ones
n How often do we decide what to run?
n Coarse grain – After a task finishes. Called Run-to- Completion (RTC) or non-preemptive n Fine grain – Any time. Called Preemptive, since one task can preempt another. Dynamic RTC Schedule GPS Data Checking Arrives complete Response Time
Rec Dec Check
n What if we receive GPS position right after Rec starts
running? n Delays n Have to wait for Rec to finish before we start decoding position with Dec. n Have to wait for Rec, Dec, Check before we know if we are approaching a pothole Task State and Scheduling Rules n Scheduler chooses among Ready tasks for execution based on priority Task is released Ready n Scheduling Rules (ready to run) n If no task is running, Start scheduler starts the highest highest priority ready Waiting priority task ready task n Once started, a task runs until it completes n Tasks then enter waiting state until Task complete Running triggered or released again 18 Dynamic Preemptive Schedule GPS Data Checking Arrives complete
Response Time
Dec Check Rec
n What if we receive GPS position right after Rec starts
running? n Delays n Scheduler switches out Rec so we can start decoding position with Dec immediately n Have to wait for Dec, Check to complete before we know if we are approaching a pothole Comparison of Response Times Static Rec S LCD Dec Check w Dynamic Run-to-Completion Rec Dec Check Dynamic Preemptive Dec Check
n Pros n Preemption offers best response time n Can do more processing (support more potholes, or higher
vehicle speed) n Or can lower processor speed, saving money, power
n Cons n Requires more complicated programming, more memory n Introduces vulnerability to data race conditions Common Schedulers n Cyclic executive - non-preemptive and static
n Run-to-completion - non-preemptive and
dynamic
n Preemptive and dynamic
Cyclic Executive with Interrupts n Two priority levels BOOL DeviceARequest, n main code – background DeviceBRequest, DeviceCRequest; n Interrupts – foreground void interrupt HandleDeviceA(){ /* do A’s urgent work */ n Example of a foreground / ... background system DeviceARequest = TRUE; n Interrupt routines run in } foreground (high priority) void main(void) { n Run when triggered while (TRUE) { if (DeviceARequest) { n Handle most urgent work FinishDeviceA(); n Set flags to request } processing by main loop if (DeviceBRequest) { n Main user code runs in FinishDeviceB(); background } n Uses “round-robin” approach if (DeviceCRequest) { FinishDeviceC(); to pick tasks, takes turns } n Tasks do not preempt each } other } Run-To-Completion Scheduler n Use a scheduler function to run task functions at the right rates n Table stores information per task n Period: How many ticks between each task release n Release Time: how long until task is ready to run n ReadyToRun: task is ready to run immediately n Scheduler runs forever, examining schedule table which indicates tasks which are ready to run (have been “released”) n A periodic timer interrupt triggers an ISR, which updates the schedule table n Decrements “time until next release” n If this time reaches 0, set the task’s Run flag and reload its time with the period n Follows a “run-to-completion” model n A task’s execution is not interleaved with any other task n Only ISRs can interrupt a task n After ISR completes, the previously-running task resumes n Priority is typically static, so can use a table with highest priority tasks first for a fast, simple scheduler implementation. Preemptive Scheduler n Task functions need not run to completion, but can be interleaved with each other n Simplifies writing software n Improves response time n Introduces new potential problems
n Worst case response time for highest priority task
does not depend on other tasks, only ISRs and scheduler n Lower priority tasks depend only on higher priority tasks
24 Task State and Scheduling Rules n Scheduler chooses among Ready tasks for execution based on priority What the Ready task needs happens n Scheduling Rules This is This isn’t n A task’s activities may highest highest lead it to waiting Waiting priority priority (blocked) ready task ready task n A waiting task never gets the CPU. It must be signaled by an ISR Task needs or another task. something Running n Only the scheduler to happen moves tasks between ready and running 25 What’s an RTOS? n What does Real-Time mean? n Can calculate and guarantee the maximum response time for each task and interrupt service routine n This “bounding” of response times allows use in hard-real-time systems (which have deadlines which must be met) n What’s in the RTOS n Task Scheduler n Preemptive, prioritized to minimize response times n Interrupt support n Core Integrated RTOS services n Inter-process communication and synchronization (safe data sharing) n Time management n Optional Integrated RTOS services n I/O abstractions? n memory management? n file system? n networking support? n GUI?? Comparison of Timing Dependence Non-preemptive Non-preemptive Preemptive Static Dynamic Dynamic
Device A ISR Device A ISR Device A ISR Device B ISR Device B ISR Device B ISR Device ... ISR Device ... ISR Device ... ISR Device Z ISR Device Z ISR Device Z ISR
everything at same level (in oval) or above Task 5 Code Task 5 Code
Task 6 Code Task 6 Code
Task 3 Max Stack Comparison of RAM Requirements Non-preemptive Non-preemptive Preemptive Static Dynamic Dynamic
Task 2 Max Stack
Task 1 Max Stack Task 2 Max Stack Task 3 Max Stack Task 4 Max Stack
Task 1 Max Stack
Task 2 Max Stack Task 3 Max Stack Task 4 Max Stack
Task 1 Max Stack
Task 1 Sta/cs Task 1 Sta/cs Task 2 Sta/cs Task 2 Sta/cs Task 3 Sta/cs Task 3 Sta/cs Task 4 Sta/cs Task 4 Sta/cs Task 1 Sta/cs n Preemption requires space for each stack* Task 2 Sta/cs n Need space for all static variables (including Task 3 Sta/cs Task 4 Sta/cs globals) *except for certain special cases References n Slides adopted from Arm Teaching Kits
