Scheduling
In general, a scheduling scheme provides two features:
1. An algorithm for ordering the use of system
resources (in particular the CPUs)
2. A means of predicting the worst-case behaviour of the system when the scheduling algorithm is applied
= prediction can then be used to confirm the temporal requirements of the application
Scheduling
static vs dynamic
A scheduling scheme can be either:
Static:
* Predictions are performed before execution
Dynamic:
* Run-time decisions are used
Our focus will be on static schemes.
Cyclic executive
task set
fig 1
Problems with Cyclic Executives
All “task” periods must be a multiple of the minor cycle time
The difficulty of incorporating tasks with long periods; the major
cycle time is the maximum period that can be accommodated
without secondary schedules
Sporadic activities are difficult (impossible!) to incorporate
Tasks exist at run-time
Tasks exist at run-time:
supported by real time os or run time
Each task is:
*Runnable (and possible running), or
*Suspended waiting for a timing event – appropriate for periodic tasks
*Suspended waiting for a non-timing event – appropriate for sporadic
tasks
Each task is:
Task-Based Scheduling
Scheduling approaches
* Fixed-Priority Scheduling (FPS)
* Each process has a fixed static property, computed pre-run-time. Most widely used
* Earliest Deadline First (EDF)
* Processes are executed in the order determined by the process’s absolute deadlines.
These are computed at run-time, hence are dynamic.
* Value-Based Scheduling (VBS)
* For dynamically changing priorities for overloaded systems, this often take the form of
assigning a value to each task.
Scheduling Characteristics
Sufficient – pass the test, will meet deadlines
Necessary – fail the test, will indeed lead a deadline
miss at some point during execution
* Exact – Both necessary and sufficient
* Sustainable – system stays schedulable if conditions ‘improve’
Preemption and non-preemption
*With priority-based scheduling, a high-priority task may be released during the execution of a lower priority one
*In a preemptive scheme, there will be an immediate switch to the higher-priority task
*With non-preemption, the lower-priority task will be allowed to complete before the other executes
*Preemptive schemes enable higher-priority tasks to be more reactive, and hence they are preferred
*Schemes such as EDF and VBS can also take on a pre-emptive or non pre-emptive form
Simple task model
The application is assumed to consist of a fixed set of tasks
All tasks are periodic, with known periods
The tasks are completely independent of each other
All system’s overheads, context-switching times and so on are ignored (i.e, assumed to have zero cost)
All tasks have a deadline equal to their period (that is, each task must complete before it is next
released)
All tasks have a fixed worst-case execution time
Standard
Notation
fig 1
Fixed-priority scheduling (FPS)
Rate Monotonic Priority Assignment
* Each task is assigned a (unique) priority based on its period; the shorter the period, the
higher the priority
* i.e, for two tasks i and j,
* Note, priority 1 is the lowest (least) priorityP jPiT jT i
Utilization-Based Analysis
- Using rate monotonic priority ordering and the utilization of each process i : C.i/T.i
- We can derive a test to see if a set of N process can meet their deadlines:
U == sum(i=1, N) C.i/T.i <= N(2^(1/N) - 1)
U <= 0.69 as N-> infinity
Utilization Bounds
N Utilization bound
1 = 100.0%
2 = 82.8%
3 = 78.0%
4 = 75.7%
5 = 74.3%
10 = 71.8%
Approaches 69.3% asymptotically
Example, Task set A
- The combined utilization is 0.82 (or 82%)
- This is above the threshold for three tasks (0.78) and, hence, this task set
fails the utilization test
Example, Task set B
fig 2
* The combined utilization is 0.775
* This is below the threshold for three tasks (0.78) and, hence, this task set
will meet all its deadlines
Example, Task set C
fig 1
* The combined utilization is 1.0
* This is above the threshold for three tasks (0.78), but the task set will meet
all its deadlines
Example, Task set C
Sufficient vs necessary
The test is sufficient but not necessary
* If a process passes the test…
* It will not miss a deadline
Necessary if:
* If it fails the test…
* It may or may not miss deadlines
Worst-case Execution Time (WCET)
-WCET values are critical for all
forms of analysis
* C values or symbol in all the
equations of this chapter
* Known as Timing Analysis
-Found either by static analysis or
measurement
* Static analysis is pessimistic
and hard to undertake with
modern processors with
cache(s), pipelines, out-of-
order execution, branch
prediction etc
* Measurement is potentially
optimistic – was the worst-case
path measured?
-Timing analysis usually
represents each task as a
directed graph of basic blocks (or
basic paths)
Basic Blocks
Once the worst-case time of each basic block is obtained (via measurement or a model of the
processor) then:
Direct graph is collapsed with maximum loop
parameters and worst-case branches assumed to be
taken
example
for i in 1..10 loop
if Cond then
– basic block of cost 100
else
– basic block of cost 10
end if;
end loop;
With no further semantic information must assume total cost is 1005 time units
(10x100 + loop cost of 5 = 1005)
But if Cond can only be true in 3 occasions then cost is 375 time units
(3x100 + 7x10 + loop cost of 5 = 375)
ILP – Integer Linear Programming – and Constraint Satisfaction
programs are being employed to model basic block dependencies
EXERCISES/DISCUSIONS 4: WEEK 37
CHAPTER 4: Scheduling real-time systems
4.1: What is a scheduling scheme in a real-time system?
4.2: What is the difference between static and dynamic scheduling scheme?
4.3:
i) What is a cyclic executive task set? Show an example.
ii) Define the minor and major cycle in a cyclic executive task set.
4.4: There are several different task-based scheduling approaches, describe at least three examples.
4.5: Name the difference between Sufficient and Necessary Scheduling characteristics.
4.6: Give a short description of the Simple Task Model.
4.7: What is rate monotonic priority assignment?
4.8:
i) What defines the utilization used in rate monotonic priority ordering?
ii) What is the utilization bound for a system which uses 5 task set.
iii) Give examples of task set, which fails and not fails the utilization test.
4.9: How is it possible to estimate the Worst-case execution time?
