Page 59 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes Some edges in resource graphs represent connectivity between components. These edges are
called accessibility edges. If there is a connection between two CPUs in the computer, then each
CPU is accessible from the other computer and there is an accessibility edge from each computer
to the CPU on the other computer.

5.4 Scheduling Hierarchy

Jobs are scheduled and allocated resources according to a chosen set of scheduling algorithms
and resource access-control protocols. The module which implements these algorithms is called
the scheduler. The scheduler assigns processors to jobs, or jobs to processors. We say that a job
is scheduled in a time interval on a processor if the processor is assigned to the job, and hence the
job executes on the processor, in the interval. The total amount of processor time assigned to a
job according to a schedule is the total length of all the time intervals during which the job is
scheduled on some processor. By a schedule we mean an assignment of all the jobs in the system
on the available processors produced b the scheduler. During this course, we will assume that
the scheduler works correctly. By correctness, we mean that the scheduler produces only valid
schedulers.
A valid schedule satisfies the following conditions.

 Every processor is assigned to at most one job at any time.
 Every job is assigned at most one processor at any time
 No job is scheduled before its release time
 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 satisfied.
We are assuming that jobs do not run in parallel on more than one processor to speed up their
execution.

5.4.1 Feasibility, Optimality and Performance Measures

A valid schedule is a feasible schedule if every job completes by its deadline. We say that a set of
jobs is schedulable according to a scheduling algorithm if when using the algorithms the scheduler
always produces a feasible schedule. A hard real-time scheduling algorithm is optimal if the
algorithms (scheduler) always produce a feasible schedule if the given set of jobs has feasible
schedules. Or, if an optimal algorithm fails to find a feasible schedule, we can conclude that the
given set of jobs cannot feasibly be scheduled by any algorithm.

In the case where all the jobs have the same release time and deadline, the problem of scheduling
the jobs to meet their deadline is in essence the same as that of scheduling to minimize the
completion time of the job which completes last among all jobs. The response time of this job is
the response time of the set of jobs as a whole and is often called the makespan of the schedule.
If the makespan is less than or equal to the length of their feasible interval, the jobs can meet
their deadline.
The most frequently used performance measure of jobs that have soft deadlines is their average
response time. The performance of scheduling algorithms is compared on a given set of jobs
based on the average response times of jobs when scheduled according to them. The smaller the
average time better the job is. In a system that has mixture of hard and soft deadline jobs, the
objective is to minimize the average response time of soft deadline jobs and making sure that all
hard deadline jobs complete in time. Since there is no advantage in completing hard deadline
jobs, we can delay their execution to get a better average response time.

54 LOVELY PROFESSIONAL UNIVERSITY