Page 121 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes  Context switch overhead is negligibly small compared with the execution times of the
tasks

 Unlimited priority levels.
 Fixed number of periodic tasks
On each new task creation, application provides its period, execution time, relative deadline and
scheduler does an acceptance test. When tasks are independent, the scheduler can delete any
tasks and add an acceptable task at any time without causing any missed deadline. A
multiprocessor priority-driven system is either dynamic or static. In a static system, all the tasks
are partitioned into subsystems. Each subsystem is assigned to a processor, and tasks on each
processor are scheduled by themselves.

In a dynamic system, job ready for execution are placed in one common priority queue and
dispatched to processors for execution as the processors become available.
The dynamic approach should allow the processors to be more fully utilized on average as the
workload fluctuates. The troublesome problem with dynamic systems is the fact that we often
do not know how to determine their worst-case and best-case performance. That is why most
hard real-time systems built and in use are static when tasks in a static system are independent,
we can consider the tasks on each processor independently of the tasks on the other processors.
The problem of scheduling in multiprocessor and distributed systems is reduced to that of
uniprocessor scheduling.

Self Assessment

Fill in the blanks:

1. When tasks are independent, the ……………… can delete any tasks and add an acceptable
task at any time without causing any missed deadline.
2. When tasks in a ……………… are independent, we can consider the tasks on each processor
independently of the tasks on the other processors.
3. In a ……………… system, job ready for execution are placed in one common priority
queue and dispatched to processors for execution as the processors become available.
4. A ……………… priority-driven system is either dynamic or static.
5. The problem of scheduling in multiprocessor and ……………… is reduced to that of
uniprocessor scheduling.

12.2 Fixed-Priority versus Dynamic-Priority Algorithms

A priority driven scheduler is an on-line scheduler. There is no pre-computation of schedules of
tasks. It assigns priorities to jobs after they are released and places the jobs in a ready job queue
in priority order. Preemption is allowed at any time, as scheduling decision is made whenever
a job is released or completed. At each scheduling decision time, the scheduler updates the ready
job queue and then schedules and executes the job at the head of the queue. Algorithms for
scheduling periodic tasks are classified into two types:
 Fixed Priority
 Dynamic Priority
Fixed Priority algorithm assigns the same priority to all the jobs in each task. Dynamic Priority
algorithm assigns different priorities to the individual jobs in each task.

116 LOVELY PROFESSIONAL UNIVERSITY