Reference Model for Real-Time Systems

Processors and Resources

• Processors: P_i
  • active
  • has speed attribute
  • usually CPU, could also be signal processor, bus, disk, network link, etc.
• Resources: R_i
  • passive
  • does not have speed
  • accessible by only one job at a time
  • could be lock (mutex, DB lock), memory
  • plentiful resources are usually left out of models

Jobs

• schedulable unit of work
• allocated processor time and other resources

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 =
  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

• 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

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

Task Release Time Models

• jitter = amount of uncertainty or variation in release time
  e.g., release time may be a range [r^-_i,r⁺_i]
• sporadic or aperiodic tasks : have jobs released at random times
  • characterized by distribution of inter-release times
  • release times also called arrival times

Periodic Tasks (Liu Definition)

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.

Aperiodic and Sporadic Tasks (Liu Definitions)

• interarrival times may vary widely
• interarrival times and execution times are identically distributed RVs
• aperiodic ↔ soft deadlines
• sporadic ↔ hard deadlines

Liu differs from most authors here. The usual convention 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