Introduction to Periodic Tasks

This material is mostly covered in Chapter 3 of Jane Liu's text.

Jobs

• schedulable unit of work
• allocated processor time and other resources
• periodic task defines an infinite sequence of jobs

Job Release Times, Deadlines, Timing Constraints

• release time = time at which job becomes available for execution
• completion time = time at which execution of job completes
• response time =
  length of time between release and completion times
• deadline (absolute) =
  time by which execution of job is required to complete
• deadline (relative) =
  length of time between release time and absolute deadline
• feasible interval/window =
  time between release time and absolute deadline
• lateness =
  response time - relative deadline
• tardiness =
  max (0, response time - relative deadline)
• slack = laxity =
  remaining time to deadline - remaining compute time

Execution Time of Job, and WCET

• cannot be predicted exactly (is random variable)
• assumed to be constrained by a range [e^-_i,e⁺_i]
• e_i generally stands for the upper bound, known as the
  worst-case-execution time (WCET)
• WCET is needed for theory to work
• an accurate WCET bound is hard to obtain in practice

See notes on measuring absolute event times and durations.

Tasks

• related set of jobs
• normally, the jobs of each task must be executed serially
  (an implicit precedence constraint)
• set of tasks is normally fixed
• except at mode changes
• or in systems with admission control

Periodic Task

models workload typically associated with feedback-loop controller

1. input sensor values
2. compute new actuator values
3. output new actuator values
4. wait until next period
5. go back to (1) and repeat

Periodic task abstraction

Each periodic task is characterized abstractly by three constants:

• period: p_i
• worst-case execution time: e_i
• relative deadline: d_i
  • implicit deadline: d_i=p_i
  • constrained deadline: d_i≤_i
  • unconstrained deadline: arbitrary d_i

utilization of task τ_i, u_i = e_i / p_i

density of task τ_i, u_i = e_i / min(p_i,d_i

Periodic task sets

• finite collection of (independent) periodic tasks
• hyper-period of task set = LCM of all task periods
• execution time e_max = maximum execution time of tasks
• utilization time u_max = maximum utilization of tasks
• utilization time u_sum = sum of utilizations of tasks

Some generalizations of the periodic model

Phasing:

• tasks are in phase if they all have the same first release time
• otherwise, the release times have non-zero offsets

Release-time jitter:

• amount of uncertainty or variation in release time
  e.g., release time may be a range [r^-_i,r⁺_i]
• Complex jobs: may have several subjobs, with precedence constraints

Completion-time jitter is also of interest, but is determined by the scheduler as well as the workload.

Short deadlines can be used to control completion time jitter.

Delayed release times and short deadlines can also be used to force ordering of jobs, to implement precedence constraints.

Liu's Periodic Tasks (called sporadic tasks by most authors)

• period p_i = minimum time between releases of jobs
  • most authors require that periodic tasks have a constant inter-release interval, and use the term "sporadic" for what Liu calls periodic

Liu's Aperiodic and "Sporadic" Tasks

• both have jobs released at random times
  • characterized by distribution of inter-release times
  • release times also called arrival times
• interarrival times may vary widely
• interarrival times and execution times are identically distributed RVs
• aperiodic ↔ soft deadlines
• sporadic ↔ hard deadlines

Liu diverges from most other authors here. The usual convention, which I will follow in this course, is:

• periodic ↔ constant inter-arrival times
• sporadic ↔ lower bound on inter-arrival times
• aperiodic ↔ arbitrary inter-arrival times

Preemptivity

• preemptible job : can be interrrupted and processor assigned to another job, at any time
• non-preemptible job : once started must be completed without assigning processor to any other job

Laxity Type

• hard : deadline or other timing constraint must always be satisfied
• soft : deadline or other timing constraint need not always be satisfied

Schedule

• mapping : (job, time_instant) → processor
• job cannot be assigned to more than one processor at a time
• a processor cannot be assigned more than one job at a time
• a job cannot run before its release time
• the total amount of processing time assigned to a job does not exceed its (actual or maximum) execution time
• all precedence and resource constraints are satisfied

Mapping only covers processors explicitly. Other resources are handled implicitly, by last rule: processor can/should not be assigned unless all other needed resources are also assigned.

Characteristics of Schedules

• feasible : every job completes by its deadline
• optimal : is feasible if there exists any feasible schedule for the same set of job release times and execution times
  • alternatively : minimizes some metric, such as number of missed deadlines, average tardiness, ...

Scheduling Algorithm

• Given set of jobs, creates a schedule
• Work-conserving: never idles a processor while there is a waiting job
• On-line : schedule up to any point in time depends only on jobs released before that time
• Off-line : may make use of knowledge of future job arrival times
• Optimal : finds a feasible schedule iff there exists a feasible schedule

Examples of Scheduling Algorithms

• Fixed task priority
  • Rate monotonic
  • Deadline monotonic
• Earliest deadline first
• Least laxity first
• Shortest remaining processing time first