LECTURELECTURE-2 BASICS OF REAL-TIME REALSCHEDULING
1/26/2012
CmpE-522
Adeel Pasha, LUMS, 2011-12
Evolution of Embedded Systems
70% of all processors built today are destined for embedded systems
Example:
HTCs HD2 uses Qualcomm 1 GHz processor HTC s Samsung I9100 Galaxy: Dual-core 1.2 GHz ARM Cortex-A9
Why? y
Moores law Transistor is cheaper => Processor is cheaper Couldnt imagine putting a PKR.10,000 processor in a PKR. 20,000 microwave oven
Now embedded processor < PKR. 1000 Now, PKR
1/26/2012 CmpE-522 2
Adeel Pasha, LUMS, 2011-12
What is Real-Time? Real
Real-Time means quantitative notion of time There is a physical mean to measure time Th i h i l i
Say, a physical clock Example: A chemical plant p p
Logical Time: qualitative notion of time
D Described with event ordering such as b f ib d ith t d i h before, after, d i ft during, succeeds, precedes Example: Query from a web-server or data-base
Does a real-time system have all notions quantitative?
No!! But at least some parts have quantitative notion of time
1/26/2012 CmpE-522 3
Adeel Pasha, LUMS, 2011-12
Safety and Reliability
Safety-critical
Safety can only be ensured through increased reliability Standard reliability criterion for a flight-control computer?
1 failure per 109 (I Giga) flying hours
How to achieve Reliability?
Error avoidance Error detection and recovery Fault-tolerance Built-In Self Test (BIST) Triple Modular Redundancy (TMR)
1/26/2012
C1 V O T I N G
C2
C3
CmpE-522 4
TAXONOMY OF REALREAL-TIME TASKS
1/26/2012
CmpE-522
Adeel Pasha, LUMS, 2011-12
Types of RT Tasks
100%
Deadline
Utility
Hard RT task
Response Time
Considered failed if deadline is surpassed Collision detection & avoidance tasks for a robot
Firm RT task
Th There i a d fi d deadline is defined d dli
But failure to meet deadline doesnt mean system failure
Vid streaming Video t i Temperature monitoring using sensor networks
1/26/2012
CmpE-522
Adeel Pasha, LUMS, 2011-12
Types of RT Tasks
Deadline 100%
Soft RT task
Utility 0
The timing constraints are not absolute
Average response time is measured
Response Time
Internet connectivity (in general), web browsing
Non-RT task
Gi me an example! Give l !
1/26/2012
CmpE-522
Adeel Pasha, LUMS, 2011-12
Events in RT-System RT
Stimulus Events
Generated by environment and used by system , p Periodic, Aperiodic
Response Events
Produced by system and used by environment
Example: dial tone reception on lifting the receiver dial-tone
Stimulus: detaching the hand-set receiver R Response: di l t dial-tone generation ti
1/26/2012 CmpE-522 8
Adeel Pasha, LUMS, 2011-12
Types of Timing Constraints
Delay constraint
Minimum time (delay) must pass b/w two events
delay
t 0
t(e1)
delay
t(e2)
Deadline constraint
Maximum permissible separation b/ two events b/w should not be surpassed
t 0
t(e1)
deadline
t(e2)
deadline
Duration constraint
An event must occur for a certain duration of time
1/26/2012 CmpE-522 9
Adeel Pasha, LUMS, 2011-12
Modeling Timing Constraints: EFSM
Deadline Constraints
Stimulus-Response (S-R) Type
Also called Performance Constraint
Await Dial DialTone Await 1st Digit
Dial-Tone/ Set Timer (30s)
Receiver Lifted/ Set Timer (3s)
Timer Expired/ Beeping
Await Receiver Replacement
10
1/26/2012
CmpE-522
Adeel Pasha, LUMS, 2011-12
Modeling Timing Constraints
Deadline Constraints
Response-Stimulus (R-S) Type
Await 2nd Digit
Await t Digit 1st Di i
1st Digit/ Set Timer (3s)
Dial-Tone/ Set Timer (30s)
Timer Expired/ Beeping
Await Receiver Replacement
11
1/26/2012
CmpE-522
Adeel Pasha, LUMS, 2011-12
Modeling Timing Constraints
Deadline Constraints
Stimulus-Stimulus (S-S) Type
Await 3rd Digit Di it
Await 2nd Digit
2nd Digit/ Set Timer (3s)
1st Digit/ Set Timer (3s)
Timer Expired/ Beeping
Await Receiver Replacement
CmpE-522 12
1/26/2012
Adeel Pasha, LUMS, 2011-12
Modeling Timing Constraints:
Deadline Constraints
Response-Response (R-R) Type
Await RingBack Tone Await Call Pick UP Pick-UP
Ring-Back/ Set Timer (1 min)
Ring-Tone to Callee/ Set Timer (3s)
Timer Expired/ Beeping
Await Receiver Replacement
1/26/2012
CmpE-522
13
Adeel Pasha, LUMS, 2011-12
Modeling Timing Constraints:
Delay Constraints
Stimulus-Stimulus (S-S) Type
Timer Expired Await 2nd Digit Di i Await 3rd Digit
2nd Digit/Beeping 1st Digit/ Set Timer (50ms)
Await Receiver Replacement
1/26/2012
CmpE-522
14
REALREAL-TIME TASK SCHEDULING
1/26/2012
CmpE-522
15
Adeel Pasha, LUMS, 2011-12
Important Notions
Task Instance
E er time an event happens, it triggers a response Every e ent ha ens tri ers res nse
A piece of code has to be run, etc. Mostly periodic, but could be aperiodic
Ti(j) Jth instance of Ti
The most common are deadline-constrained tasks Relative vs. Absolute Deadline
Absolute: Measured with the help of a real clock R l Relative: referenced to some other event f d h
1/26/2012 CmpE-522 16
Adeel Pasha, LUMS, 2011-12
Important Notions
Relative Deadline of Ti =di
Absolute Deadline of Ti (1) = i + di
i Ti (1)
0
Arrival or activation of Ti (1)
Ti (2)
1/26/2012
CmpE-522
17
Adeel Pasha, LUMS, 2011-12
Important Notions
Task Precedence
If a task must complete before the second task to start g Its recurring Defines partial ordering among tasks
T1 T3
T4
T2
1/26/2012
CmpE-522
18
Adeel Pasha, LUMS, 2011-12
Important Notions
Data Sharing g
Tasks often need to share data p p g p g Example: A temperature sensing and processing node Data sharing can imply a task precedence
But there can be task precedence without data sharing p g And there can be data sharing among concurrent tasks
T1 T3
T4
T2
1/26/2012 CmpE-522 19
TASK CLASSIFICATION
1/26/2012
CmpE-522
20
Adeel Pasha, LUMS, 2011-12
Periodic Task (Ti) = (i,ei,pi,di) (
Example: Track correction task in a rocket Ti = (2000ms, 8ms, 80ms, 50ms)
di
pi
ei
i Ti (1)
0
Arrival or activation of Ti (1)
Ti (2)
= Phase or First Activation Date e = Worst Case Execution Time (WCET)
1/26/2012
p = Period d = Deadline
CmpE-522 21
Adeel Pasha, LUMS, 2011-12
Sporadic Task (Ti) = (ei,gi,di)
No fixed period Random arrival R d i l
Ti = (ei,gi,di) e = WCET d = deadline g = minimum separation b/w two instances
Instances cant overlap
E.g. SOS call from an aircraft
Aperiodic Task (Ti) = (ei,gi=0,di) =0,d
Same as sporadic but g can be 0
i.e. occurrences can overlap
1/26/2012 CmpE-522 22
Adeel Pasha, LUMS, 2011-12
Schedule for Lab Weeks Only
Day Tuesday Thursday Thursday y Friday Time 4:00 pm to 5:50 pm 4:00 pm to 5:50 pm 10:00 am to 11:50 am 10:00 am to 11:50 am Student Category MS MS BS BS Venue LAB3 LAB3 LAB3 LAB3
Pre/post-Labs can be done during any free slot available to students in-between the lab sessions
1/26/2012
CmpE-522
23
Adeel Pasha, LUMS, 2011-12
24/1 Intro 3rd Week 9/2 Lab1 L b1 (PIC18F452) 28/2 Resource Sharing in MP 15/3 Mid term 10/4 HW Accelerators 13th Week 26/4 FPGA Lab3
26/1 RT Scheduling RT-Scheduling 14/2 Dynamic Scheduling Algos 1/3 Commercial RTOS 27/3 RT Comm. 12/4 Commercial Embedded Platforms
h 14th Week 1/5 FPGA Lab4
31/1 Static Scheduling Algos 16/2 Resource R Sharing 7th Week 6/3 Lab3 (Mini6410) 29/3 RT Databases 12th Week 17/4 Lab5 (TS7200)
h 14th Week 4/5 FPGA Lab5 1/26/2012
2/2 Mem-mapped I/Os GPIO I/Os, etc. 5th Week 21/2 Linux D Device L Drivers 7th Week 8/3 Lab3 (Mini6410) 10th Week 3/4 4 Lab4 (TS7200) 12th Week 19/4 FPGA Lab1
3rd Week 7/2 Lab1 (PIC18F452) 5th Week 23/2 Lab2 L b2 (Mini6410) 13/3 RT Comm. 10th Week 5/4 4 Lab4 (TS7200) 13th Week 24/4 FPGA Lab2
CmpE-522
24
