Page 84 - DCAP608_REAL TIME SYSTEMS

Unit 7: Commonly used Algorithm to Real-time Scheduling

7.5 Summary Notes

 A real-time operating system is a system that schedules execution of tasks in a timely
deterministic manner, and is scalable.

 The scheduler follows a set of algorithms that determine which task executes at each
moment.

 Preemptive priority-based scheduling is a mandatory property of the operating system we
evaluate for use in our application.
 An interrupt is an asynchronous exception of which the source is an internal or external
hardware device.
 Release times and deadlines of jobs are inconsistent with the precedence constraints of the
jobs.
 Effective Release time of a job without predecessors is equal to its given release time.
 Effective Deadline without a successor is equal to its given deadline.
 Priorities can be assigned to jobs according to their deadlines.

 The earlier the deadline, the higher the priority. Such scheduling algorithm is called the
Earliest-Deadline-First (EDF) algorithms.
 The priorities are based on the release times of jobs; the later the release time, the higher
the priority.
 the EDF algorithm can produces a feasible schedule of a set J of jobs with arbitrary release
times and deadlines on a processor if and only if J has feasible schedules.
 Any feasible schedule of J can be systematically transformed into an EDF schedule.

7.6 Keywords

Earliest-Deadline-First (EDF) Algorithm: It is an algorithm that is optimal when used to schedule
jobs on a processor as long as preemption is allowed and jobs do not contend for resources.
Latest Release Time (LRT) Algorithm: This is an algorithm that treats release times as deadlines
and deadlines as release times and schedules the jobs backwards, starting from the latest deadline
of all jobs, in “priority-driven” manner, to the current time.
Real-time Operating System: A real-time operating system is a system that schedules execution
of tasks in a timely deterministic manner, and is scalable.

Real-time Scheduling: It is the form of scheduling that offers a way of predicting the timing
behaviour of complex multi-tasking computer software.
RM Schedulers: These are static and assign the task priority according to the period of the tasks
– they always select the task with the shortest period that is ready to run.

7.7 Review Questions

1. Define the term real-time scheduling.
2. What is effective release times and deadline?

3. What is the limitation of effective deadline?

LOVELY PROFESSIONAL UNIVERSITY 79