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.