PART 2
Schedulability Analysis
22
Schedulability Analysis
Introduction
v Schedulability - NP-hard if there are any resources
dependencies
n provide a necessary and sufficient schedulability
condition
n Find a schedule if it is easy to do
n Stuck in the middle somewhere
v SA is to determine whether a specific set of tasks or a
set of tasks satisfying certain constraints can be
successfully scheduled (completing execution of every
task by its specified deadline) (Cheng, 2002).
v Schedulability test (ST) is used to validate that a given
application can satisfy its specified deadlines when
scheduled according to a specific scheduling algo.
23
Schedulability Analysis
Introduction
v 3 basic approaches of ST
1. Processor utilization analysis
2. Processor workloads analysis
3. Response time analysis
24
³
Schedulability Analysis
Processor Utilization Analysis
v ST 1 : EDF - Given a set of n independent, preemptable, &
periodic tasks on a uniprocessor such that Di ³>= Ti &
that their periods are exact (integer) multiples of each
other. A necessary & sufficient condition for feasible
scheduling of this task set is:
n
Ci
U =å £1
i =1 T i
v ST 2 : RM - Given a set of n independent, preemptable, &
periodic tasks on a uniprocessor. A necessary &
sufficient condition for feasible scheduling of this task
set is:
n 1
Ci
U =å £ n (2 n - 1)
i =1 T i
25
³
Schedulability Analysis
Processor Workload Analysis
v ST 3 : RM - Let
i
é t ù
W i (t ) = åC k ê ú.0 < t £ T i
k =1 êT k ú
The following inequality wi(t) £ t hold for any time
instant t chosen as follows:
êT i ú
t = kT j , j = 1......i , k = 1..... ê ú
êëT j úû
iff task Ji is schedulable. If Di <> Ti, we replace Ti
by min(Di, Ti) in the above expression.
26
Schedulability Analysis
Response Time Analysis
v ST 4 : RM - A task i is schedulable if Ri <= Di , where
é R ix ù
R i
x +1
= Ci + å ê úC j
j Îhp ( i ) ê T j ú
27
SA of a Mobile Robot Systems
Scheduling mobile robotic tasks
v Scheduling theory assumes that RTS consists of:
1. A set of computational tasks to be performed.
v The computational tasks in the AMR obtained using
2. A run-time scheduler which controls task execution at
any given moment.
v Support using a RTOS µcos-II - portable, ROMable,
scalable, preemptive real-time, multitasking kernel
for microprocessors and microcontrollers.
3. A set of shared resources shared by the task. Hw & SW
SHARING.
28
SA of a Mobile Robot Systems
Scheduling mobile robotic tasks
v Resource sharing mostly due to hardware sharing.
SW COMPONENTS
Motor Control HRI Poster
Distance
Baterry Sensors Motor Speed
Driver Encoder Driver
Driver Control
AD Motor Direction DA LCD Switches
Init IR Driver Init Init
Driver Driver Driver Driver Driver
ON BOARD 8255 External IO 8255x2
GPIO
PORT PORT PORT PORT PORT PORT
PORT A PORT B PORT C A1 B1 C1 A2 B2 C2
4 2 2
6
4 6
ADC (10) DAC (2)
6 1 1 2 2
BATTERY
IR (4) MOTOR (2) LCD Switches
SENSOR
ENCODER
(2)
DISTANCE
SENSOR
HW COMPONENTS
29
Processor Utilization Analysis
SA of a Mobile Robot Systems
MobileRobot
MotorControlKanan
actualSpeedKanan
EncoderKanan PIDKanan MotorKiri
actualSpeed actualSpeed
controlSignal controlSignal
desiredSpeed
desiredSpeedKanan
MotorControlKiri
actualSpeedKiri
EncoderKiri PIDKiri MotorKiri
actualSpeed actualSpeed
controlSignal controlSignal
desiredSpeed
desiredSpeedKiri
Avoid Behavior
HRI
Set Avoid Bumper Sensor actualSpeedKiri
desiredSpeedKiri
Behavior
obstHit obstHit actualSpeedKanan
desiredSpeedKanan desiredSpeedKiri
desiredSpeedKanan
Task Ti Ci Ui
MotorControlKanan 50 12
MotorControlKiri 50 12
AvoidBehavior 250 20
MobileRobot 300 10
HRI 500 125
30
Processor Utilization Analysis
SA of a Mobile Robot Systems
MobileRobot
MotorControlKanan
actualSpeedKanan
EncoderKanan PIDKanan MotorKiri
actualSpeed actualSpeed
controlSignal controlSignal
desiredSpeed
desiredSpeedKanan
MotorControlKiri
actualSpeedKiri
EncoderKiri PIDKiri MotorKiri
actualSpeed actualSpeed
controlSignal controlSignal
desiredSpeed
desiredSpeedKiri
Avoid Behavior
HRI
Set Avoid Bumper Sensor actualSpeedKiri
desiredSpeedKiri
Behavior
obstHit obstHit actualSpeedKanan
desiredSpeedKanan desiredSpeedKiri
desiredSpeedKanan
Task Ti Ci Ui U(n)
MotorControlKanan 50 12 0.24 1.00
MotorControlKiri 50 12 0.48 0.828
AvoidBehavior 250 20 0.56 0.779
MobileRobot 300 10 0.59 0.756
HRI 500 125 0.84 0.743 31
Response Time Analysis
v Step1: Compute the first approximation
v Step 2: Calculate the next approximation
v Step 3: Determine if the approximation is the
answer.
Condition 1: If (an+1 is less than or equal to Di)
and (an+1 is not equal to an), then repeat Step 2.
Condition 2: If an+1 is greater than Di, then event ai
misses its deadline.
Condition 3: an+1 is equal to an, the technique
terminates and an is the response time.
32
Response Time Analysis
SA of a Mobile Robot Systems
33
Response Time Analysis
SA of a Mobile Robot Systems
Task Period (ms) WCET (ms) Ri
MobileRobot 50 1 1
Motorctrl_left 50 20 21
Motorctrl_right 50 20 41
Subsumption 200 1 42
Avoid 300 17 100
Cruise 300 1 143
Manrobotintf 500 16 200
v Step1: Compute the first approximation
i
a0 = å C j
j =1
a0=1+20+20+1 = 42
34
Response Time Analysis
SA of a Mobile Robot Systems
v Step 2: Calculate the next approximation
i -1 é an ù
a n+1 = Ci + å ê úC j
j =1 ê T j ú
3 é
a0 ù
a1 = 1 + å ê úC j
j =1 ê T j ú
é 42 ù é 42 ù é 42 ù
a1 = 1 + ê ú1 + ê ú 20 + ê ú 20
ê 50 ú ê 50 ú ê 50 ú
a=1+1+20+20 = 42
v Step 3: Determine if the approximation is the answer.
Condition 1 & 2 (False): Since (a1 is less than 200), (a1 is
equal to a0) & 42ms <200ms
Condition 3 (True): (a1 is equal to a0), the techniques
terminates, WCRT is 42ms & task Subsumption is schedulable.
35
Response Time Analysis
Example 2
Task Period (ms) WCET (ms) Deadline
e1 100 40 100
e2 150 40 150
e3 350 100 350
v Step1: Compute the first approximation
i
a0 = å C j = 100 + 40 + 40 = 180
j =1
v Step2: Calculate the next approximation
é a0 ù
2 Step 3: Determine if the
a1 = C3 + å ê úC j approximation is the answer.
j =1 ê T j ú
Condition 1 (True): Since (a0 is
é180 ù é180 ù less than 350) and (a1 is not
a1 = 100 + ê ú 40 + ê ú 40 = 260 equal to a1), repeat step 2.
ê100 ú ê150 ú 36
Response Time Analysis
Example 2
v Step 2: Calculate the next approximation
2 é
a1 ù
a2 = 100 + å ê úC j
j =1 ê T j ú
é 260 ù é 260 ù
a2 = 100 + ê ú 40 + ê ú 40 = 300
ê 100 ú ê 150 ú
v Step 3: Determine if the approximation is the answer.
Condition 1 (True): Since (a2 is less than 350) and (a2 is equal to
a1), repeat Step 2
v Step 2: Calculate the next approximation
2 é a2 ù Step 3: Determine if the
a3 = 100 + å ê úC j approximation is the answer.
j =1 ê T j ú
Condition 3 (True): Since (a3 is less
é 300 ù é 300 ù than 350) and (a3 is equal to a2), the
a3 = 100 + ê ú 40 + ê ú 40 = 300 techniques terminates
ê 100 ú ê 150 ú WCRT is 300ms. Since 300ms
<350ms, task a3 is schedulable.
37
Processor Utilization Analysis
SA of a Mobile Robot Systems
v RMA verification is to check whether the entire
components involved in the composition meet their
deadlines.
v Timing results of the mobile robot case study.
Task Period (ms) WCET (ms) Ri
MobileRobot 50 1 1
Motorctrl_left 50 20 21
Motorctrl_right 50 20 41
Subsumption 200 1 42
Avoid 300 17 100
Cruise 300 1 143
Manrobotintf 500 16 200
Di = Ti
38
SA of a Mobile Robot Systems
Scheduling mobile robotic tasks using RMA
v In this example:
1. RM theory was applied to the problem of scheduling of
AMR systems.
2. This approach allows:
v Clear separation of analysis of logical correctness
and timing correctness
v To follow SE principle and simplified the
component-based software development and and
allows addition, modification, and deletion of tasks
or components.
39
Schedulability Analysis
Class Exercise
Consider three periodic tasks with the following arrival times
(S), computation times (c) and periods (p=t and d)
(which are equal to their respective relative deadlines):
J1: S1 = 0, c1= 2, p1 = d1 = 5.
J2: S2 = 1, c2 = 1, p2 = d2 =5 and
J3: S3 = 2, c3 = 2, p3 = d3 = 20.
v Use the following techniques to perform the schedulability
analysis of the above tasks. Assume Fixed-priority
Scheduling (Preemptive) using RMA
1. Sketch a timeline (Using as state above)
2. Processor utilization analysis (all S are 0)
3. Response time analysis (all S are 0) for J3
40
Schedulability Analysis
Team Assisted Individualization (TAI)
TAI is a Combination of cooperative learning and
individualized instruction.
1. Small group, are Formed composed of students of varying
ability. (your group)
2. Each student Works on individualized unit of instruction.
3. Team members use answer sheets to check each others'
work, they are responsible For ensuring that all team
members are ready to take the final test for this topic.
4. Discussion and peer tutoring take place for members of a
group. Students are required to ask for team assistance
before going to a teacher.
5. Each group need to show the output of the TAI activities in
in padlet. 41