Transcript Basics of Real-Time Scheduling

courseware
Basics of Real-Time
Scheduling
Jan Madsen
Informatics and Mathematical Modelling
Technical University of Denmark
Richard Petersens Plads, Building 321
DK2800 Lyngby, Denmark
[email protected]
WAP application
• Tasks:
- send requests to server
- translate data received from server
- render data on display
- operating the user’s control panel
• Why?
- logically different operations
- performed at different rates
Need structure and to perform multiple processes
SoC-MOBINET courseware
Jan Madsen
2
Why use multiple processes?
• Processes introduce structure into the
system design
– understand each process independently
– analyze communication between processes
to determine system behavior
• Timing is easier to specify
• Communication between processes
provide test points
• Suitable for team effort
Processes are a neat way to handle complex systems
SoC-MOBINET courseware
Jan Madsen
3
What is a process?
 A process is a state and a procedure
 State:
 Running
 Suspended
 Deactivated
 Procedure:
 Sequence of separate steps
 A process may interact with its surroundings
SoC-MOBINET courseware
Jan Madsen
4
Process execution
deadline
activation
period
SoC-MOBINET courseware
Jan Madsen
5
Process execution
• Periodic
– the period is the time between successive
executions
– the process rate is the inverse of its period
• Aperiodic
– non-periodic process, typical an event
handler
• Sporadic
– hard real-time aperiodic process
– usually, a minimum interarrival constraint is imposed
SoC-MOBINET courseware
Jan Madsen
6
Example: A software processes
 A process includes:
 code
 memory which belongs to the process
 connections to other processes
 A process is a unique execution of a program
 In most embedded systems, processes never die!
SoC-MOBINET courseware
Jan Madsen
7
Executing on a single CPU
P1 code & data
P2 code & data
PC
P3 code & data
P1 state
registers
P2 state
P3 state
Memory
SoC-MOBINET courseware
Jan Madsen
CPU
8
Execution of multiple processes
• On a single CPU
– A Pentium processor
• On a distributed homogeneous system
– A network of Pentium processors
• On a distributed heterogeneous system
– A network of differing processors (CPUs and
ASICs)
SoC-MOBINET courseware
Jan Madsen
9
About this lecture
 Huge literature on scheduling theory
 Aim is to give an overview of problems and
possible solutions to the multi-task scheduling
problem related to RTOS
 Structure of lecture:
 Some basic concepts and teminology
 Uni-processor scheduling
 Rate-monotonic scheduling
 Earlies-deadlines-first scheduling
 Multi-processor scheduling
SoC-MOBINET courseware
Jan Madsen
10
PART I
Scheduling Terminology and
Basic Concepts
SoC-MOBINET courseware
Jan Madsen
11
Design flow
Partitioning/clustering
Allocation
Break processes to
increase parallelism
Mapping
Scheduling
Communication
PE1
PE2
P3
SoC-MOBINET courseware
P2
Jan Madsen
P2
P3
Cluster processes to
reduce communication
PE2
PE1
P1
P1
P1
P2 & P3
12
Scheduling
2
1
3
3
4
4
scheduling
a
b
SoC-MOBINET courseware
1
2
a
b
os
c
c
Jan Madsen
13
Terminology
•Architecture
•Application
•Scheduling
constraints
Application
Scheduler
Schedule
Architecture
•Constraints
SoC-MOBINET courseware
Jan Madsen
14
Architecture
 Components
 Processors
3
 CPU, DSP, ASIC, ...
 Communication
 Bus, network, ...
 Devices
4
1
2
a
b
os
c
device
 sensor, actuator, display, ...
 Architecture may be fixed
or (re-)configurable
SoC-MOBINET courseware
Jan Madsen
mem
device
15
Application
 Task
 A module which can be envoked to perform a
particular function
 A schedulable entity
2
 Characterized by its:
1
 Timing constraints
3
 Precedence contraints
4
 Exclusion constraints
 Resource requirements
SoC-MOBINET courseware
Jan Madsen
16
Timing constraints
1
r1
s1
e1
d1
T1
r1 = time at which task becomes released (or active)
s1 = time at which task starts its execution
e1 = worst case execution time (WCET)
d1 = deadline, task should complete before this!
T1 = period, minimum time between task releases
SoC-MOBINET courseware
Jan Madsen
17
Task execution
 Periodic
 the period is the time between successive executions
 Aperiodic
 non-periodic task, typical an event handler
 Sporadic
 hard real-time aperiodic task
 typical, a minimum interarrival constraint is imposed
SoC-MOBINET courseware
Jan Madsen
18
Precedence constraints
 pi precede pj if pi must finish before pj begins
 process interrelate with each other to achieve:
 synchronization
 exchange data
pi
pj
pi
pj
blocked
SoC-MOBINET courseware
Jan Madsen
19
Exclusion constraints
 pi exclude pj if no execution of pj is allowed
between the time that pi starts its computation and
the time that pi complete its computation
 Prevent simultaneous access to shared resources
pi
pj
 data
 memory
 devices
pi
pj
pj blocked
SoC-MOBINET courseware
Jan Madsen
20
Resource constraints
 R = r1, r2, …, rm
 Example:
 R(pi) = {r1, r3} resource r1 and r3 is required by pi during
its execution
 may be used to
 implement a critical section
 enforce PE assignment of processes
SoC-MOBINET courseware
Jan Madsen
21
Scheduling approaches
 Classical scheduling theory
 Uniprocessor systems
 RMS
 EDF
 Distributed real-time scheduling
 Deterministic (static) scheduling
 Dynamic scheduling
SoC-MOBINET courseware
Jan Madsen
22
Scheduling
 Allocation
 Determine number and type of processors/resources
 Assignment
 Binding tasks to processors
 Scheduling
 Determine execution order
1
2
a
a
b
b
a
Task view
SoC-MOBINET courseware
Jan Madsen
b
1
2
2
1
Architecture view
23
Scheduling principles
 Off-line
 A scheduler performing its job before the scheduled
system is put into operation
 On-line
 A scheduler performing its job at run-time, when the
system is running
 Typically list-based
 When a task is released (ready) it is placed in a list
 Scheduler select which task from the list to execute next
 Selection based on some criteria – scheduling policy
SoC-MOBINET courseware
Jan Madsen
24
Scheduling areas
 High-level Synthesis:
 fine grained, operation/instruction level
 schedule done off-line
 single time constraint
 Real-time operating systems (RTOS):
 coarse grained, programs/sub-programs
 scheduling done on-line
 multiple time constraints
SoC-MOBINET courseware
Jan Madsen
25
SoC scheduling
 Similarity to RTOS




Time constraints
Context switching
Task synchronization
Task communication
 Difference to RTOS
 Large design space
 Variable granularity
 Wide range of metrics
 Time, power, cost, ...
 Flexibility, reliability, ...
 High degree of optimization
 Dedicated hardware
SoC-MOBINET courseware
Jan Madsen
26
Preemption vs. Non-preemption
 Non-preemptive scheduling
1
2
 Preemptive scheduling
1
2
SoC-MOBINET courseware
Jan Madsen
27
Metrics
 Minimize:
Schedule length
c
w c
i
i
L
max
i
= maxi {e - d }
i
i
d1
p1
p2
SoC-MOBINET courseware
lateness, tardiness
d2
d3 d4
p2
p3 p4
p3 p4
p5
Jan Madsen
d5
p5
p1
28