The figure ‘model of a real-time system’ shows the three elements of our model of real-time systems. The application system is represented by

  • a task graph which gives the processor time and resource requirements of jobs, their timing constraints and dependencies
  • A resource graph describing the resources available to execute the application system, their attributes and rules governing their use
  • And between these graphs are the scheduling and resource access-control algorithms used by the operating system

Jobs are scheduled and allocated resources according to a chosen set of scheduling algorithms and resource access-control protocols. The scheduler is a module that implements these algorithms.

The scheduler assigns processors to jobs, or equivalently, assigns jobs to processors. A schedule is an assignment by the scheduler of all the jobs in the system on the available processors. For proper execution of job, a schedule must be valid.

A valid schedule is the schedule satisfies the following conditions:

  • Every processor is assigned to at most one job at any
  • Every job is assigned at most one processor at any
  • No job is scheduled before its release
  • Depending on the scheduling algorithms used, the total amount of processor time assigned to every job is equal to its maximum or actual execution time.
  • All the precedence and resource usage constraints are
  • Schedule must be feasible and scheduling algorithms must be

A valid schedule is a feasible schedule if every job completes by its deadline and in general meets its timing constraints. A set of jobs is schedulable according to a scheduling algorithm if when using the algorithm the scheduler always produces a feasible schedule.

A hard real-time scheduling algorithm is optimal if using the algorithm the scheduler always produces a feasible schedule if the given set of jobs has feasible schedules. If an optimal algorithm cannot find a feasible schedule, we can conclude that a given set of jobs cannot feasibly be scheduled by any algorithm.